Line data Source code
1 : /*
2 : * Copyright (C) Matthieu Suiche 2008
3 : *
4 : * All rights reserved.
5 : *
6 : * Redistribution and use in source and binary forms, with or without
7 : * modification, are permitted provided that the following conditions
8 : * are met:
9 : *
10 : * 1. Redistributions of source code must retain the above copyright
11 : * notice, this list of conditions and the following disclaimer.
12 : *
13 : * 2. Redistributions in binary form must reproduce the above copyright
14 : * notice, this list of conditions and the following disclaimer in the
15 : * documentation and/or other materials provided with the distribution.
16 : *
17 : * 3. Neither the name of the author nor the names of its contributors
18 : * may be used to endorse or promote products derived from this software
19 : * without specific prior written permission.
20 : *
21 : * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
22 : * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 : * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
25 : * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 : * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 : * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 : * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 : * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 : * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 : * SUCH DAMAGE.
32 : *
33 : */
34 :
35 : #include "replace.h"
36 : #include "lzxpress.h"
37 : #include "../lib/util/byteorder.h"
38 :
39 :
40 : #define __CHECK_BYTES(__size, __index, __needed) do { \
41 : if (unlikely(__index >= __size)) { \
42 : return -1; \
43 : } else { \
44 : uint32_t __avail = __size - __index; \
45 : if (unlikely(__needed > __avail)) { \
46 : return -1; \
47 : } \
48 : } \
49 : } while(0)
50 :
51 : #define CHECK_INPUT_BYTES(__needed) \
52 : __CHECK_BYTES(uncompressed_size, uncompressed_pos, __needed)
53 : #define CHECK_OUTPUT_BYTES(__needed) \
54 : __CHECK_BYTES(max_compressed_size, compressed_pos, __needed)
55 :
56 0 : ssize_t lzxpress_compress(const uint8_t *uncompressed,
57 : uint32_t uncompressed_size,
58 : uint8_t *compressed,
59 : uint32_t max_compressed_size)
60 : {
61 : /*
62 : * This is the algorithm in [MS-XCA] 2.3 "Plain LZ77 Compression".
63 : *
64 : * It avoids Huffman encoding by including literal bytes inline when a
65 : * match is not found. Every so often it includes a uint32 bit map
66 : * flagging which positions contain matches and which contain
67 : * literals. The encoding of matches is of variable size, depending on
68 : * the match length; they are always at least 16 bits long, and can
69 : * implicitly use unused half-bytes from earlier in the stream.
70 : */
71 : uint32_t uncompressed_pos, compressed_pos;
72 : uint32_t indic;
73 : uint32_t indic_pos;
74 : uint32_t indic_bit, nibble_index;
75 :
76 0 : if (!uncompressed_size) {
77 0 : return 0;
78 : }
79 :
80 0 : uncompressed_pos = 0;
81 0 : compressed_pos = 0;
82 0 : indic = 0;
83 0 : CHECK_OUTPUT_BYTES(sizeof(uint32_t));
84 0 : PUSH_LE_U32(compressed, compressed_pos, 0);
85 0 : compressed_pos += sizeof(uint32_t);
86 0 : indic_pos = 0;
87 :
88 0 : indic_bit = 0;
89 0 : nibble_index = 0;
90 :
91 0 : while ((uncompressed_pos < uncompressed_size) &&
92 : (compressed_pos < max_compressed_size)) {
93 0 : bool found = false;
94 :
95 0 : uint32_t best_len = 2;
96 0 : uint32_t best_offset = 0;
97 :
98 : int32_t offset;
99 :
100 0 : const uint32_t max_offset = MIN(0x2000, uncompressed_pos);
101 : /* maximum len we can encode into metadata */
102 0 : const uint32_t max_len = MIN(0xFFFF + 3, uncompressed_size - uncompressed_pos);
103 :
104 : /* search for the longest match in the window for the lookahead buffer */
105 0 : for (offset = 1; (uint32_t)offset <= max_offset; offset++) {
106 : uint32_t len;
107 :
108 0 : for (len = 0;
109 0 : (len < max_len) && (uncompressed[uncompressed_pos + len] ==
110 0 : uncompressed[uncompressed_pos + len - offset]);
111 0 : len++);
112 :
113 : /*
114 : * We check if len is better than the value found before, including the
115 : * sequence of identical bytes
116 : */
117 0 : if (len > best_len) {
118 0 : found = true;
119 0 : best_len = len;
120 0 : best_offset = offset;
121 0 : if (best_len == max_len) {
122 : /* We're not going to do better than this */
123 0 : break;
124 : }
125 : }
126 : }
127 :
128 0 : if (!found) {
129 : /*
130 : * This is going to literal byte, which we flag by
131 : * setting a bit in an indicator field somewhere
132 : * earlier in the stream.
133 : */
134 0 : CHECK_INPUT_BYTES(sizeof(uint8_t));
135 0 : CHECK_OUTPUT_BYTES(sizeof(uint8_t));
136 0 : compressed[compressed_pos++] = uncompressed[uncompressed_pos++];
137 :
138 0 : indic <<= 1;
139 0 : indic_bit += 1;
140 :
141 0 : if (indic_bit == 32) {
142 0 : PUSH_LE_U32(compressed, indic_pos, indic);
143 0 : indic_bit = 0;
144 0 : CHECK_OUTPUT_BYTES(sizeof(uint32_t));
145 0 : indic_pos = compressed_pos;
146 0 : compressed_pos += sizeof(uint32_t);
147 : }
148 : } else {
149 0 : uint32_t match_len = best_len;
150 :
151 : uint16_t metadata;
152 :
153 0 : match_len -= 3;
154 0 : best_offset -= 1;
155 :
156 : /* Classical meta-data */
157 0 : CHECK_OUTPUT_BYTES(sizeof(uint16_t));
158 0 : metadata = (uint16_t)((best_offset << 3) | MIN(match_len, 7));
159 0 : PUSH_LE_U16(compressed, compressed_pos, metadata);
160 0 : compressed_pos += sizeof(uint16_t);
161 :
162 0 : if (match_len >= 7) {
163 0 : match_len -= 7;
164 :
165 0 : if (!nibble_index) {
166 0 : nibble_index = compressed_pos;
167 :
168 0 : CHECK_OUTPUT_BYTES(sizeof(uint8_t));
169 0 : compressed[nibble_index] = MIN(match_len, 15);
170 0 : compressed_pos += sizeof(uint8_t);
171 : } else {
172 0 : compressed[nibble_index] |= MIN(match_len, 15) << 4;
173 0 : nibble_index = 0;
174 : }
175 :
176 0 : if (match_len >= 15) {
177 0 : match_len -= 15;
178 :
179 0 : CHECK_OUTPUT_BYTES(sizeof(uint8_t));
180 0 : compressed[compressed_pos] = MIN(match_len, 255);
181 0 : compressed_pos += sizeof(uint8_t);
182 :
183 0 : if (match_len >= 255) {
184 : /* Additional match_len */
185 :
186 0 : match_len += 7 + 15;
187 :
188 0 : if (match_len < (1 << 16)) {
189 0 : CHECK_OUTPUT_BYTES(sizeof(uint16_t));
190 0 : PUSH_LE_U16(compressed, compressed_pos, match_len);
191 0 : compressed_pos += sizeof(uint16_t);
192 : } else {
193 0 : CHECK_OUTPUT_BYTES(sizeof(uint16_t) + sizeof(uint32_t));
194 0 : PUSH_LE_U16(compressed, compressed_pos, 0);
195 0 : compressed_pos += sizeof(uint16_t);
196 :
197 0 : PUSH_LE_U32(compressed, compressed_pos, match_len);
198 0 : compressed_pos += sizeof(uint32_t);
199 : }
200 : }
201 : }
202 : }
203 :
204 0 : indic = (indic << 1) | 1;
205 0 : indic_bit += 1;
206 :
207 0 : if (indic_bit == 32) {
208 0 : PUSH_LE_U32(compressed, indic_pos, indic);
209 0 : indic_bit = 0;
210 0 : CHECK_OUTPUT_BYTES(sizeof(uint32_t));
211 0 : indic_pos = compressed_pos;
212 0 : compressed_pos += sizeof(uint32_t);
213 : }
214 :
215 0 : uncompressed_pos += best_len;
216 : }
217 : }
218 :
219 0 : if (indic_bit != 0) {
220 0 : indic <<= 32 - indic_bit;
221 : }
222 0 : indic |= UINT32_MAX >> indic_bit;
223 0 : PUSH_LE_U32(compressed, indic_pos, indic);
224 :
225 0 : return compressed_pos;
226 : }
227 :
228 0 : ssize_t lzxpress_decompress(const uint8_t *input,
229 : uint32_t input_size,
230 : uint8_t *output,
231 : uint32_t max_output_size)
232 : {
233 : /*
234 : * This is the algorithm in [MS-XCA] 2.4 "Plain LZ77 Decompression
235 : * Algorithm Details".
236 : */
237 : uint32_t output_index, input_index;
238 : uint32_t indicator, indicator_bit;
239 : uint32_t nibble_index;
240 :
241 0 : if (input_size == 0) {
242 0 : return 0;
243 : }
244 :
245 0 : output_index = 0;
246 0 : input_index = 0;
247 0 : indicator = 0;
248 0 : indicator_bit = 0;
249 0 : nibble_index = 0;
250 :
251 : #undef CHECK_INPUT_BYTES
252 : #define CHECK_INPUT_BYTES(__needed) \
253 : __CHECK_BYTES(input_size, input_index, __needed)
254 : #undef CHECK_OUTPUT_BYTES
255 : #define CHECK_OUTPUT_BYTES(__needed) \
256 : __CHECK_BYTES(max_output_size, output_index, __needed)
257 :
258 : do {
259 0 : if (indicator_bit == 0) {
260 0 : CHECK_INPUT_BYTES(sizeof(uint32_t));
261 0 : indicator = PULL_LE_U32(input, input_index);
262 0 : input_index += sizeof(uint32_t);
263 0 : if (input_index == input_size) {
264 : /*
265 : * The compressor left room for indicator
266 : * flags for data that doesn't exist.
267 : */
268 0 : break;
269 : }
270 0 : indicator_bit = 32;
271 : }
272 0 : indicator_bit--;
273 :
274 : /*
275 : * check whether the bit specified by indicator_bit is set or not
276 : * set in indicator. For example, if indicator_bit has value 4
277 : * check whether the 4th bit of the value in indicator is set
278 : */
279 0 : if (((indicator >> indicator_bit) & 1) == 0) {
280 0 : CHECK_INPUT_BYTES(sizeof(uint8_t));
281 0 : CHECK_OUTPUT_BYTES(sizeof(uint8_t));
282 0 : output[output_index] = input[input_index];
283 0 : input_index += sizeof(uint8_t);
284 0 : output_index += sizeof(uint8_t);
285 : } else {
286 : uint32_t length;
287 : uint32_t offset;
288 :
289 0 : CHECK_INPUT_BYTES(sizeof(uint16_t));
290 0 : length = PULL_LE_U16(input, input_index);
291 0 : input_index += sizeof(uint16_t);
292 0 : offset = (length >> 3) + 1;
293 0 : length &= 7;
294 :
295 0 : if (length == 7) {
296 0 : if (nibble_index == 0) {
297 0 : CHECK_INPUT_BYTES(sizeof(uint8_t));
298 0 : nibble_index = input_index;
299 0 : length = input[input_index] & 0xf;
300 0 : input_index += sizeof(uint8_t);
301 : } else {
302 0 : length = input[nibble_index] >> 4;
303 0 : nibble_index = 0;
304 : }
305 :
306 0 : if (length == 15) {
307 0 : CHECK_INPUT_BYTES(sizeof(uint8_t));
308 0 : length = input[input_index];
309 0 : input_index += sizeof(uint8_t);
310 0 : if (length == 255) {
311 0 : CHECK_INPUT_BYTES(sizeof(uint16_t));
312 0 : length = PULL_LE_U16(input, input_index);
313 0 : input_index += sizeof(uint16_t);
314 0 : if (length == 0) {
315 0 : CHECK_INPUT_BYTES(sizeof(uint32_t));
316 0 : length = PULL_LE_U32(input, input_index);
317 0 : input_index += sizeof(uint32_t);
318 : }
319 :
320 0 : if (length < (15 + 7)) {
321 0 : return -1;
322 : }
323 0 : length -= (15 + 7);
324 : }
325 0 : length += 15;
326 : }
327 0 : length += 7;
328 : }
329 0 : length += 3;
330 :
331 0 : if (length == 0) {
332 0 : return -1;
333 : }
334 :
335 0 : for (; length > 0; --length) {
336 0 : if (offset > output_index) {
337 0 : return -1;
338 : }
339 0 : CHECK_OUTPUT_BYTES(sizeof(uint8_t));
340 0 : output[output_index] = output[output_index - offset];
341 0 : output_index += sizeof(uint8_t);
342 : }
343 : }
344 0 : } while ((output_index < max_output_size) && (input_index < (input_size)));
345 :
346 0 : return output_index;
347 : }
|
