4 * XPRESS compression routines.
6 * See the comments in xpress-decompress.c about the XPRESS format.
10 * Copyright (C) 2012, 2013 Eric Biggers
12 * This file is part of wimlib, a library for working with WIM files.
14 * wimlib is free software; you can redistribute it and/or modify it under the
15 * terms of the GNU General Public License as published by the Free
16 * Software Foundation; either version 3 of the License, or (at your option)
19 * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
20 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
21 * A PARTICULAR PURPOSE. See the GNU General Public License for more
24 * You should have received a copy of the GNU General Public License
25 * along with wimlib; if not, see http://www.gnu.org/licenses/.
33 #include "wimlib/assert.h"
34 #include "wimlib/compress.h"
35 #include "wimlib/error.h"
36 #include "wimlib/util.h"
37 #include "wimlib/xpress.h"
45 /* Intermediate XPRESS match/literal representation. */
47 u16 adjusted_len; /* Match length minus XPRESS_MIN_MATCH_LEN */
48 u16 offset; /* Match offset */
49 /* For literals, offset == 0 and adjusted_len is the literal. */
53 * Writes @match, which is a match given in the intermediate representation for
54 * XPRESS matches, to the output stream @ostream.
56 * @codewords and @lens provide the Huffman code that is being used.
59 xpress_write_match(struct xpress_match match,
60 struct output_bitstream *restrict ostream,
61 const u16 codewords[restrict],
62 const u8 lens[restrict])
64 u8 len_hdr = min(match.adjusted_len, 0xf);
65 u8 offset_bsr = bsr32(match.offset);
66 unsigned sym = XPRESS_NUM_CHARS + ((offset_bsr << 4) | len_hdr);
68 bitstream_put_bits(ostream, codewords[sym], lens[sym]);
70 if (match.adjusted_len >= 0xf) {
71 u8 byte1 = min(match.adjusted_len - 0xf, 0xff);
72 bitstream_put_byte(ostream, byte1);
74 bitstream_put_byte(ostream, match.adjusted_len & 0xff);
75 bitstream_put_byte(ostream, match.adjusted_len >> 8);
78 bitstream_put_bits(ostream, match.offset ^ (1U << offset_bsr), offset_bsr);
82 xpress_write_matches_and_literals(struct output_bitstream *ostream,
83 const struct xpress_match matches[restrict],
84 input_idx_t num_matches,
85 const u16 codewords[restrict],
86 const u8 lens[restrict])
88 for (input_idx_t i = 0; i < num_matches; i++) {
89 if (matches[i].offset) {
91 xpress_write_match(matches[i], ostream, codewords, lens);
94 u8 lit = matches[i].adjusted_len;
95 bitstream_put_bits(ostream, codewords[lit], lens[lit]);
98 bitstream_put_bits(ostream, codewords[XPRESS_END_OF_DATA], lens[XPRESS_END_OF_DATA]);
101 struct xpress_record_ctx {
102 freq_t freqs[XPRESS_NUM_SYMBOLS];
103 struct xpress_match *matches;
107 xpress_record_literal(u8 lit, void *_ctx)
109 struct xpress_record_ctx *ctx = _ctx;
111 *(ctx->matches++) = (struct xpress_match) { .offset = 0, .adjusted_len = lit };
115 xpress_record_match(unsigned len, unsigned offset, void *_ctx)
117 struct xpress_record_ctx *ctx = _ctx;
119 XPRESS_ASSERT(len >= XPRESS_MIN_MATCH_LEN);
120 XPRESS_ASSERT(len <= XPRESS_MAX_MATCH_LEN);
121 XPRESS_ASSERT(offset >= XPRESS_MIN_OFFSET);
122 XPRESS_ASSERT(offset <= XPRESS_MAX_OFFSET);
124 unsigned adjusted_len = len - XPRESS_MIN_MATCH_LEN;
125 unsigned len_hdr = min(adjusted_len, 0xf);
126 unsigned sym = XPRESS_NUM_CHARS + ((bsr32(offset) << 4) | len_hdr);
128 XPRESS_ASSERT(sym >= XPRESS_NUM_CHARS);
129 XPRESS_ASSERT(sym < XPRESS_NUM_SYMBOLS);
132 *(ctx->matches++) = (struct xpress_match) { .offset = offset,
133 .adjusted_len = adjusted_len };
136 static const struct lz_params xpress_lz_params = {
137 .min_match = XPRESS_MIN_MATCH_LEN,
138 .max_match = XPRESS_MAX_MATCH_LEN,
139 .max_offset = XPRESS_MAX_OFFSET,
143 .max_lazy_match = 16,
147 /* API function documented in wimlib.h */
149 wimlib_xpress_compress(const void * restrict uncompressed_data,
150 unsigned uncompressed_len,
151 void * restrict compressed_data)
153 u8 *cptr = compressed_data;
154 struct output_bitstream ostream;
156 struct xpress_record_ctx record_ctx;
158 struct xpress_match *matches;
159 input_idx_t *prev_tab;
162 u16 codewords[XPRESS_NUM_SYMBOLS];
163 u8 lens[XPRESS_NUM_SYMBOLS];
164 input_idx_t num_matches;
165 input_idx_t compressed_len;
167 const size_t stack_max = 65536;
169 /* XPRESS requires 256 bytes of overhead for the Huffman code, so it's
170 * impossible to compress 256 bytes or less of data to less than the
173 * +1 to take into account that the buffer for compressed data is 1 byte
174 * smaller than the buffer for uncompressed data.
176 * +4 to take into account that init_output_bitstream() requires at
177 * least 4 bytes of data. */
178 if (uncompressed_len < XPRESS_NUM_SYMBOLS / 2 + 1 + 4)
181 if (uncompressed_len <= stack_max) {
182 matches = alloca(uncompressed_len * sizeof(matches[0]));
183 udata = alloca(uncompressed_len + 8);
184 prev_tab = alloca(uncompressed_len * sizeof(prev_tab[0]));
186 matches = MALLOC(uncompressed_len * sizeof(matches[0]));
187 udata = MALLOC(uncompressed_len + 8);
188 prev_tab = MALLOC(uncompressed_len * sizeof(prev_tab[0]));
189 if (matches == NULL || udata == NULL || prev_tab == NULL) {
190 WARNING("Failed to allocate memory for compression...");
196 /* Copy the data to a temporary buffer, but only to avoid
197 * inconsequential accesses of uninitialized memory in
198 * lz_analyze_block(). */
199 memcpy(udata, uncompressed_data, uncompressed_len);
200 memset(udata + uncompressed_len, 0, 8);
202 /* Determine match/literal sequence to divide the data into. */
203 ZERO_ARRAY(record_ctx.freqs);
204 record_ctx.matches = matches;
205 lz_analyze_block(udata,
208 xpress_record_literal,
213 num_matches = (record_ctx.matches - matches);
215 /* Account for end of data symbol. */
216 record_ctx.freqs[XPRESS_END_OF_DATA]++;
218 /* Build the Huffman code. */
219 make_canonical_huffman_code(XPRESS_NUM_SYMBOLS, XPRESS_MAX_CODEWORD_LEN,
220 record_ctx.freqs, lens, codewords);
222 /* Output the Huffman code as a series of 512 4-bit lengths. */
223 for (i = 0; i < XPRESS_NUM_SYMBOLS; i += 2)
224 *cptr++ = (lens[i] & 0xf) | (lens[i + 1] << 4);
226 /* Output the encoded matches/literals. */
227 init_output_bitstream(&ostream, cptr,
228 uncompressed_len - XPRESS_NUM_SYMBOLS / 2 - 1);
229 xpress_write_matches_and_literals(&ostream, matches,
230 num_matches, codewords, lens);
232 /* Flush any pending data and get the length of the compressed data. */
233 compressed_len = flush_output_bitstream(&ostream);
234 if (compressed_len == ~(input_idx_t)0) {
238 compressed_len += XPRESS_NUM_SYMBOLS / 2;
240 #if defined(ENABLE_XPRESS_DEBUG) || defined(ENABLE_VERIFY_COMPRESSION)
241 /* Verify that we really get the same thing back when decompressing. */
242 if (wimlib_xpress_decompress(compressed_data, compressed_len,
243 udata, uncompressed_len))
245 ERROR("Failed to decompress data we "
246 "compressed using XPRESS algorithm");
252 if (memcmp(uncompressed_data, udata, uncompressed_len)) {
253 ERROR("Data we compressed using XPRESS algorithm "
254 "didn't decompress to original");
262 if (uncompressed_len > stack_max) {
267 return compressed_len;