]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /********************************************************************** |
2 | Copyright(c) 2011-2016 Intel Corporation All rights reserved. | |
3 | ||
4 | Redistribution and use in source and binary forms, with or without | |
5 | modification, are permitted provided that the following conditions | |
6 | are met: | |
7 | * Redistributions of source code must retain the above copyright | |
8 | notice, this list of conditions and the following disclaimer. | |
9 | * Redistributions in binary form must reproduce the above copyright | |
10 | notice, this list of conditions and the following disclaimer in | |
11 | the documentation and/or other materials provided with the | |
12 | distribution. | |
13 | * Neither the name of Intel Corporation nor the names of its | |
14 | contributors may be used to endorse or promote products derived | |
15 | from this software without specific prior written permission. | |
16 | ||
17 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
18 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
19 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
20 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
21 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
22 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
23 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
24 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
25 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
26 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
27 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
28 | **********************************************************************/ | |
29 | ||
30 | #include "igzip_inflate_ref.h" | |
31 | ||
32 | void inline byte_copy(uint8_t * dest, uint64_t lookback_distance, int repeat_length) | |
33 | { | |
34 | uint8_t *src = dest - lookback_distance; | |
35 | ||
36 | for (; repeat_length > 0; repeat_length--) | |
37 | *dest++ = *src++; | |
38 | } | |
39 | ||
40 | /* | |
41 | * Returns integer with first length bits reversed and all higher bits zeroed | |
42 | */ | |
43 | uint16_t inline bit_reverse2(uint16_t bits, uint8_t length) | |
44 | { | |
45 | bits = ((bits >> 1) & 0x55555555) | ((bits & 0x55555555) << 1); // swap bits | |
46 | bits = ((bits >> 2) & 0x33333333) | ((bits & 0x33333333) << 2); // swap pairs | |
47 | bits = ((bits >> 4) & 0x0F0F0F0F) | ((bits & 0x0F0F0F0F) << 4); // swap nibbles | |
48 | bits = ((bits >> 8) & 0x00FF00FF) | ((bits & 0x00FF00FF) << 8); // swap bytes | |
49 | return bits >> (16 - length); | |
50 | } | |
51 | ||
52 | void inline init_inflate_in_buffer(struct inflate_in_buffer *inflate_in) | |
53 | { | |
54 | inflate_in->read_in = 0; | |
55 | inflate_in->read_in_length = 0; | |
56 | } | |
57 | ||
58 | void inline set_inflate_in_buffer(struct inflate_in_buffer *inflate_in, uint8_t * in_stream, | |
59 | uint32_t in_size) | |
60 | { | |
61 | inflate_in->next_in = inflate_in->start = in_stream; | |
62 | inflate_in->avail_in = in_size; | |
63 | } | |
64 | ||
65 | void inline set_inflate_out_buffer(struct inflate_out_buffer *inflate_out, | |
66 | uint8_t * out_stream, uint32_t out_size) | |
67 | { | |
68 | inflate_out->next_out = out_stream; | |
69 | inflate_out->avail_out = out_size; | |
70 | inflate_out->total_out = 0; | |
71 | } | |
72 | ||
73 | void inline inflate_in_clear_bits(struct inflate_in_buffer *inflate_in) | |
74 | { | |
75 | uint8_t bytes; | |
76 | ||
77 | bytes = inflate_in->read_in_length / 8; | |
78 | ||
79 | inflate_in->read_in = 0; | |
80 | inflate_in->read_in_length = 0; | |
81 | inflate_in->next_in -= bytes; | |
82 | inflate_in->avail_in += bytes; | |
83 | } | |
84 | ||
85 | void inline inflate_in_load(struct inflate_in_buffer *inflate_in, int min_required) | |
86 | { | |
87 | uint64_t temp = 0; | |
88 | uint8_t new_bytes; | |
89 | ||
90 | if (inflate_in->avail_in >= 8) { | |
91 | /* If there is enough space to load a 64 bits, load the data and use | |
92 | * that to fill read_in */ | |
93 | new_bytes = 8 - (inflate_in->read_in_length + 7) / 8; | |
94 | temp = *(uint64_t *) inflate_in->next_in; | |
95 | ||
96 | inflate_in->read_in |= temp << inflate_in->read_in_length; | |
97 | inflate_in->next_in += new_bytes; | |
98 | inflate_in->avail_in -= new_bytes; | |
99 | inflate_in->read_in_length += new_bytes * 8; | |
100 | ||
101 | } else { | |
102 | /* Else fill the read_in buffer 1 byte at a time */ | |
103 | while (inflate_in->read_in_length < 57 && inflate_in->avail_in > 0) { | |
104 | temp = *inflate_in->next_in; | |
105 | inflate_in->read_in |= temp << inflate_in->read_in_length; | |
106 | inflate_in->next_in++; | |
107 | inflate_in->avail_in--; | |
108 | inflate_in->read_in_length += 8; | |
109 | ||
110 | } | |
111 | } | |
112 | ||
113 | } | |
114 | ||
115 | uint64_t inline inflate_in_peek_bits(struct inflate_in_buffer *inflate_in, uint8_t bit_count) | |
116 | { | |
117 | assert(bit_count < 57); | |
118 | ||
119 | /* Load inflate_in if not enough data is in the read_in buffer */ | |
120 | if (inflate_in->read_in_length < bit_count) | |
121 | inflate_in_load(inflate_in, 0); | |
122 | ||
123 | return (inflate_in->read_in) & ((1 << bit_count) - 1); | |
124 | } | |
125 | ||
126 | void inline inflate_in_shift_bits(struct inflate_in_buffer *inflate_in, uint8_t bit_count) | |
127 | { | |
128 | ||
129 | inflate_in->read_in >>= bit_count; | |
130 | inflate_in->read_in_length -= bit_count; | |
131 | } | |
132 | ||
133 | uint64_t inline inflate_in_read_bits(struct inflate_in_buffer *inflate_in, uint8_t bit_count) | |
134 | { | |
135 | uint64_t ret; | |
136 | assert(bit_count < 57); | |
137 | ||
138 | /* Load inflate_in if not enough data is in the read_in buffer */ | |
139 | if (inflate_in->read_in_length < bit_count) | |
140 | inflate_in_load(inflate_in, bit_count); | |
141 | ||
142 | ret = (inflate_in->read_in) & ((1 << bit_count) - 1); | |
143 | inflate_in->read_in >>= bit_count; | |
144 | inflate_in->read_in_length -= bit_count; | |
145 | ||
146 | return ret; | |
147 | } | |
148 | ||
149 | int inline setup_static_header(struct inflate_state *state) | |
150 | { | |
151 | /* This could be turned into a memcpy of this functions output for | |
152 | * higher speed, but then DECODE_LOOKUP_SIZE couldn't be changed without | |
153 | * regenerating the table. */ | |
154 | ||
155 | int i; | |
156 | struct huff_code lit_code[LIT_LEN + 2]; | |
157 | struct huff_code dist_code[DIST_LEN + 2]; | |
158 | ||
159 | /* These tables are based on the static huffman tree described in RFC | |
160 | * 1951 */ | |
161 | uint16_t lit_count[16] = { | |
162 | 0, 0, 0, 0, 0, 0, 0, 24, 152, 112, 0, 0, 0, 0, 0, 0 | |
163 | }; | |
164 | uint16_t dist_count[16] = { | |
165 | 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 | |
166 | }; | |
167 | ||
168 | /* These for loops set the code lengths for the static literal/length | |
169 | * and distance codes defined in the deflate standard RFC 1951 */ | |
170 | for (i = 0; i < 144; i++) | |
171 | lit_code[i].length = 8; | |
172 | ||
173 | for (i = 144; i < 256; i++) | |
174 | lit_code[i].length = 9; | |
175 | ||
176 | for (i = 256; i < 280; i++) | |
177 | lit_code[i].length = 7; | |
178 | ||
179 | for (i = 280; i < LIT_LEN + 2; i++) | |
180 | lit_code[i].length = 8; | |
181 | ||
182 | for (i = 0; i < DIST_LEN + 2; i++) | |
183 | dist_code[i].length = 5; | |
184 | ||
185 | make_inflate_huff_code(&state->lit_huff_code, lit_code, LIT_LEN + 2, lit_count); | |
186 | make_inflate_huff_code(&state->dist_huff_code, dist_code, DIST_LEN + 2, dist_count); | |
187 | ||
188 | return 0; | |
189 | } | |
190 | ||
191 | void inline make_inflate_huff_code(struct inflate_huff_code *result, | |
192 | struct huff_code *huff_code_table, int table_length, | |
193 | uint16_t * count) | |
194 | { | |
195 | int i, j; | |
196 | uint16_t code = 0; | |
197 | uint16_t next_code[MAX_HUFF_TREE_DEPTH + 1]; | |
198 | uint16_t long_code_list[LIT_LEN]; | |
199 | uint32_t long_code_length = 0; | |
200 | uint16_t temp_code_list[1 << (15 - DECODE_LOOKUP_SIZE)]; | |
201 | uint32_t temp_code_length; | |
202 | uint32_t long_code_lookup_length = 0; | |
203 | uint32_t max_length; | |
204 | uint16_t first_bits; | |
205 | uint32_t code_length; | |
206 | uint16_t long_bits; | |
207 | uint16_t min_increment; | |
208 | ||
209 | memset(result, 0, sizeof(struct inflate_huff_code)); | |
210 | ||
211 | next_code[0] = code; | |
212 | ||
213 | for (i = 1; i < MAX_HUFF_TREE_DEPTH + 1; i++) | |
214 | next_code[i] = (next_code[i - 1] + count[i - 1]) << 1; | |
215 | ||
216 | for (i = 0; i < table_length; i++) { | |
217 | if (huff_code_table[i].length != 0) { | |
218 | /* Determine the code for symbol i */ | |
219 | huff_code_table[i].code = | |
220 | bit_reverse2(next_code[huff_code_table[i].length], | |
221 | huff_code_table[i].length); | |
222 | ||
223 | next_code[huff_code_table[i].length] += 1; | |
224 | ||
225 | if (huff_code_table[i].length <= DECODE_LOOKUP_SIZE) { | |
226 | /* Set lookup table to return the current symbol | |
227 | * concatenated with the code length when the | |
228 | * first DECODE_LENGTH bits of the address are | |
229 | * the same as the code for the current | |
230 | * symbol. The first 9 bits are the code, bits | |
231 | * 14:10 are the code length, bit 15 is a flag | |
232 | * representing this is a symbol*/ | |
233 | for (j = 0; j < (1 << (DECODE_LOOKUP_SIZE - | |
234 | huff_code_table[i].length)); j++) | |
235 | ||
236 | result->small_code_lookup[(j << | |
237 | huff_code_table[i].length) + | |
238 | huff_code_table[i].code] | |
239 | = i | (huff_code_table[i].length) << 9; | |
240 | ||
241 | } else { | |
242 | /* Store the element in a list of elements with long codes. */ | |
243 | long_code_list[long_code_length] = i; | |
244 | long_code_length++; | |
245 | } | |
246 | } | |
247 | } | |
248 | ||
249 | for (i = 0; i < long_code_length; i++) { | |
250 | /*Set the look up table to point to a hint where the symbol can be found | |
251 | * in the list of long codes and add the current symbol to the list of | |
252 | * long codes. */ | |
253 | if (huff_code_table[long_code_list[i]].code == 0xFFFF) | |
254 | continue; | |
255 | ||
256 | max_length = huff_code_table[long_code_list[i]].length; | |
257 | first_bits = | |
258 | huff_code_table[long_code_list[i]].code & ((1 << DECODE_LOOKUP_SIZE) - 1); | |
259 | ||
260 | temp_code_list[0] = long_code_list[i]; | |
261 | temp_code_length = 1; | |
262 | ||
263 | for (j = i + 1; j < long_code_length; j++) { | |
264 | if ((huff_code_table[long_code_list[j]].code & | |
265 | ((1 << DECODE_LOOKUP_SIZE) - 1)) == first_bits) { | |
266 | if (max_length < huff_code_table[long_code_list[j]].length) | |
267 | max_length = huff_code_table[long_code_list[j]].length; | |
268 | temp_code_list[temp_code_length] = long_code_list[j]; | |
269 | temp_code_length++; | |
270 | } | |
271 | } | |
272 | ||
273 | for (j = 0; j < temp_code_length; j++) { | |
274 | code_length = huff_code_table[temp_code_list[j]].length; | |
275 | long_bits = | |
276 | huff_code_table[temp_code_list[j]].code >> DECODE_LOOKUP_SIZE; | |
277 | min_increment = 1 << (code_length - DECODE_LOOKUP_SIZE); | |
278 | for (; long_bits < (1 << (max_length - DECODE_LOOKUP_SIZE)); | |
279 | long_bits += min_increment) { | |
280 | result->long_code_lookup[long_code_lookup_length + long_bits] = | |
281 | temp_code_list[j] | (code_length << 9); | |
282 | } | |
283 | huff_code_table[temp_code_list[j]].code = 0xFFFF; | |
284 | } | |
285 | result->small_code_lookup[first_bits] = | |
286 | long_code_lookup_length | (max_length << 9) | 0x8000; | |
287 | long_code_lookup_length += 1 << (max_length - DECODE_LOOKUP_SIZE); | |
288 | ||
289 | } | |
290 | } | |
291 | ||
292 | uint16_t inline decode_next(struct inflate_in_buffer *in_buffer, | |
293 | struct inflate_huff_code *huff_code) | |
294 | { | |
295 | uint16_t next_bits; | |
296 | uint16_t next_sym; | |
297 | ||
298 | next_bits = inflate_in_peek_bits(in_buffer, DECODE_LOOKUP_SIZE); | |
299 | ||
300 | /* next_sym is a possible symbol decoded from next_bits. If bit 15 is 0, | |
301 | * next_code is a symbol. Bits 9:0 represent the symbol, and bits 14:10 | |
302 | * represent the length of that symbols huffman code. If next_sym is not | |
303 | * a symbol, it provides a hint of where the large symbols containin | |
304 | * this code are located. Note the hint is at largest the location the | |
305 | * first actual symbol in the long code list.*/ | |
306 | next_sym = huff_code->small_code_lookup[next_bits]; | |
307 | ||
308 | if (next_sym < 0x8000) { | |
309 | /* Return symbol found if next_code is a complete huffman code | |
310 | * and shift in buffer over by the length of the next_code */ | |
311 | inflate_in_shift_bits(in_buffer, next_sym >> 9); | |
312 | ||
313 | return next_sym & 0x1FF; | |
314 | ||
315 | } else { | |
316 | /* If a symbol is not found, perform a linear search of the long code | |
317 | * list starting from the hint in next_sym */ | |
318 | next_bits = inflate_in_peek_bits(in_buffer, (next_sym - 0x8000) >> 9); | |
319 | next_sym = | |
320 | huff_code->long_code_lookup[(next_sym & 0x1FF) + | |
321 | (next_bits >> DECODE_LOOKUP_SIZE)]; | |
322 | inflate_in_shift_bits(in_buffer, next_sym >> 9); | |
323 | return next_sym & 0x1FF; | |
324 | ||
325 | } | |
326 | } | |
327 | ||
328 | int inline setup_dynamic_header(struct inflate_state *state) | |
329 | { | |
330 | int i, j; | |
331 | struct huff_code code_huff[CODE_LEN_CODES]; | |
332 | struct huff_code lit_and_dist_huff[LIT_LEN + DIST_LEN]; | |
333 | struct huff_code *previous = NULL, *current; | |
334 | struct inflate_huff_code inflate_code_huff; | |
335 | uint8_t hclen, hdist, hlit; | |
336 | uint16_t code_count[16], lit_count[16], dist_count[16]; | |
337 | uint16_t *count; | |
338 | uint16_t symbol; | |
339 | ||
340 | /* This order is defined in RFC 1951 page 13 */ | |
341 | const uint8_t code_length_code_order[CODE_LEN_CODES] = { | |
342 | 0x10, 0x11, 0x12, 0x00, 0x08, 0x07, 0x09, 0x06, | |
343 | 0x0a, 0x05, 0x0b, 0x04, 0x0c, 0x03, 0x0d, 0x02, | |
344 | 0x0e, 0x01, 0x0f | |
345 | }; | |
346 | ||
347 | memset(code_count, 0, sizeof(code_count)); | |
348 | memset(lit_count, 0, sizeof(lit_count)); | |
349 | memset(dist_count, 0, sizeof(dist_count)); | |
350 | memset(code_huff, 0, sizeof(code_huff)); | |
351 | memset(lit_and_dist_huff, 0, sizeof(lit_and_dist_huff)); | |
352 | ||
353 | /* These variables are defined in the deflate standard, RFC 1951 */ | |
354 | hlit = inflate_in_read_bits(&state->in_buffer, 5); | |
355 | hdist = inflate_in_read_bits(&state->in_buffer, 5); | |
356 | hclen = inflate_in_read_bits(&state->in_buffer, 4); | |
357 | ||
358 | /* Create the code huffman code for decoding the lit/len and dist huffman codes */ | |
359 | for (i = 0; i < hclen + 4; i++) { | |
360 | code_huff[code_length_code_order[i]].length = | |
361 | inflate_in_read_bits(&state->in_buffer, 3); | |
362 | ||
363 | code_count[code_huff[code_length_code_order[i]].length] += 1; | |
364 | } | |
365 | ||
366 | if (state->in_buffer.read_in_length < 0) | |
367 | return END_OF_INPUT; | |
368 | ||
369 | make_inflate_huff_code(&inflate_code_huff, code_huff, CODE_LEN_CODES, code_count); | |
370 | ||
371 | /* Decode the lit/len and dist huffman codes using the code huffman code */ | |
372 | count = lit_count; | |
373 | current = lit_and_dist_huff; | |
374 | ||
375 | while (current < lit_and_dist_huff + LIT_LEN + hdist + 1) { | |
376 | /* If finished decoding the lit/len huffman code, start decoding | |
377 | * the distance code these decodings are in the same loop | |
378 | * because the len/lit and dist huffman codes are run length | |
379 | * encoded together. */ | |
380 | if (current == lit_and_dist_huff + 257 + hlit) | |
381 | current = lit_and_dist_huff + LIT_LEN; | |
382 | ||
383 | if (current == lit_and_dist_huff + LIT_LEN) | |
384 | count = dist_count; | |
385 | ||
386 | symbol = decode_next(&state->in_buffer, &inflate_code_huff); | |
387 | ||
388 | if (state->in_buffer.read_in_length < 0) | |
389 | return END_OF_INPUT; | |
390 | ||
391 | if (symbol < 16) { | |
392 | /* If a length is found, update the current lit/len/dist | |
393 | * to have length symbol */ | |
394 | count[symbol]++; | |
395 | current->length = symbol; | |
396 | previous = current; | |
397 | current++; | |
398 | ||
399 | } else if (symbol == 16) { | |
400 | /* If a repeat length is found, update the next repeat | |
401 | * length lit/len/dist elements to have the value of the | |
402 | * repeated length */ | |
403 | if (previous == NULL) /* No elements available to be repeated */ | |
404 | return INVALID_BLOCK_HEADER; | |
405 | ||
406 | i = 3 + inflate_in_read_bits(&state->in_buffer, 2); | |
407 | for (j = 0; j < i; j++) { | |
408 | *current = *previous; | |
409 | count[current->length]++; | |
410 | previous = current; | |
411 | ||
412 | if (current == lit_and_dist_huff + 256 + hlit) { | |
413 | current = lit_and_dist_huff + LIT_LEN; | |
414 | count = dist_count; | |
415 | ||
416 | } else | |
417 | current++; | |
418 | } | |
419 | ||
420 | } else if (symbol == 17) { | |
421 | /* If a repeat zeroes if found, update then next | |
422 | * repeated zeroes length lit/len/dist elements to have | |
423 | * length 0. */ | |
424 | i = 3 + inflate_in_read_bits(&state->in_buffer, 3); | |
425 | ||
426 | for (j = 0; j < i; j++) { | |
427 | previous = current; | |
428 | ||
429 | if (current == lit_and_dist_huff + 256 + hlit) { | |
430 | current = lit_and_dist_huff + LIT_LEN; | |
431 | count = dist_count; | |
432 | ||
433 | } else | |
434 | current++; | |
435 | } | |
436 | ||
437 | } else if (symbol == 18) { | |
438 | /* If a repeat zeroes if found, update then next | |
439 | * repeated zeroes length lit/len/dist elements to have | |
440 | * length 0. */ | |
441 | i = 11 + inflate_in_read_bits(&state->in_buffer, 7); | |
442 | ||
443 | for (j = 0; j < i; j++) { | |
444 | previous = current; | |
445 | ||
446 | if (current == lit_and_dist_huff + 256 + hlit) { | |
447 | current = lit_and_dist_huff + LIT_LEN; | |
448 | count = dist_count; | |
449 | ||
450 | } else | |
451 | current++; | |
452 | } | |
453 | } else | |
454 | return INVALID_BLOCK_HEADER; | |
455 | ||
456 | } | |
457 | ||
458 | if (state->in_buffer.read_in_length < 0) | |
459 | return END_OF_INPUT; | |
460 | ||
461 | make_inflate_huff_code(&state->lit_huff_code, lit_and_dist_huff, LIT_LEN, lit_count); | |
462 | make_inflate_huff_code(&state->dist_huff_code, &lit_and_dist_huff[LIT_LEN], DIST_LEN, | |
463 | dist_count); | |
464 | ||
465 | return 0; | |
466 | } | |
467 | ||
468 | int read_header(struct inflate_state *state) | |
469 | { | |
470 | state->new_block = 0; | |
471 | ||
472 | /* btype and bfinal are defined in RFC 1951, bfinal represents whether | |
473 | * the current block is the end of block, and btype represents the | |
474 | * encoding method on the current block. */ | |
475 | state->bfinal = inflate_in_read_bits(&state->in_buffer, 1); | |
476 | state->btype = inflate_in_read_bits(&state->in_buffer, 2); | |
477 | ||
478 | if (state->in_buffer.read_in_length < 0) | |
479 | return END_OF_INPUT; | |
480 | ||
481 | if (state->btype == 0) { | |
482 | inflate_in_clear_bits(&state->in_buffer); | |
483 | return 0; | |
484 | ||
485 | } else if (state->btype == 1) | |
486 | return setup_static_header(state); | |
487 | ||
488 | else if (state->btype == 2) | |
489 | return setup_dynamic_header(state); | |
490 | ||
491 | return INVALID_BLOCK_HEADER; | |
492 | } | |
493 | ||
494 | void igzip_inflate_init(struct inflate_state *state, uint8_t * in_stream, uint32_t in_size, | |
495 | uint8_t * out_stream, uint64_t out_size) | |
496 | { | |
497 | ||
498 | init_inflate_in_buffer(&state->in_buffer); | |
499 | ||
500 | set_inflate_in_buffer(&state->in_buffer, in_stream, in_size); | |
501 | set_inflate_out_buffer(&state->out_buffer, out_stream, out_size); | |
502 | ||
503 | state->new_block = 1; | |
504 | state->bfinal = 0; | |
505 | } | |
506 | ||
507 | int igzip_inflate(struct inflate_state *state) | |
508 | { | |
509 | /* The following tables are based on the tables in the deflate standard, | |
510 | * RFC 1951 page 11. */ | |
511 | const uint16_t len_start[29] = { | |
512 | 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, | |
513 | 0x0b, 0x0d, 0x0f, 0x11, 0x13, 0x17, 0x1b, 0x1f, | |
514 | 0x23, 0x2b, 0x33, 0x3b, 0x43, 0x53, 0x63, 0x73, | |
515 | 0x83, 0xa3, 0xc3, 0xe3, 0x102 | |
516 | }; | |
517 | const uint8_t len_extra_bit_count[29] = { | |
518 | 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, | |
519 | 0x1, 0x1, 0x1, 0x1, 0x2, 0x2, 0x2, 0x2, | |
520 | 0x3, 0x3, 0x3, 0x3, 0x4, 0x4, 0x4, 0x4, | |
521 | 0x5, 0x5, 0x5, 0x5, 0x0 | |
522 | }; | |
523 | const uint32_t dist_start[30] = { | |
524 | 0x0001, 0x0002, 0x0003, 0x0004, 0x0005, 0x0007, 0x0009, 0x000d, | |
525 | 0x0011, 0x0019, 0x0021, 0x0031, 0x0041, 0x0061, 0x0081, 0x00c1, | |
526 | 0x0101, 0x0181, 0x0201, 0x0301, 0x0401, 0x0601, 0x0801, 0x0c01, | |
527 | 0x1001, 0x1801, 0x2001, 0x3001, 0x4001, 0x6001 | |
528 | }; | |
529 | const uint8_t dist_extra_bit_count[30] = { | |
530 | 0x0, 0x0, 0x0, 0x0, 0x1, 0x1, 0x2, 0x2, | |
531 | 0x3, 0x3, 0x4, 0x4, 0x5, 0x5, 0x6, 0x6, | |
532 | 0x7, 0x7, 0x8, 0x8, 0x9, 0x9, 0xa, 0xa, | |
533 | 0xb, 0xb, 0xc, 0xc, 0xd, 0xd | |
534 | }; | |
535 | ||
536 | uint16_t next_lit, len, nlen; | |
537 | uint8_t next_dist; | |
538 | uint32_t repeat_length; | |
539 | uint32_t look_back_dist; | |
540 | uint32_t tmp; | |
541 | ||
542 | while (state->new_block == 0 || state->bfinal == 0) { | |
543 | if (state->new_block != 0) { | |
544 | tmp = read_header(state); | |
545 | ||
546 | if (tmp) | |
547 | return tmp; | |
548 | } | |
549 | ||
550 | if (state->btype == 0) { | |
551 | /* If the block is uncompressed, perform a memcopy while | |
552 | * updating state data */ | |
553 | if (state->in_buffer.avail_in < 4) | |
554 | return END_OF_INPUT; | |
555 | ||
556 | len = *(uint16_t *) state->in_buffer.next_in; | |
557 | state->in_buffer.next_in += 2; | |
558 | nlen = *(uint16_t *) state->in_buffer.next_in; | |
559 | state->in_buffer.next_in += 2; | |
560 | ||
561 | /* Check if len and nlen match */ | |
562 | if (len != (~nlen & 0xffff)) | |
563 | return INVALID_NON_COMPRESSED_BLOCK_LENGTH; | |
564 | ||
565 | if (state->out_buffer.avail_out < len) | |
566 | return OUT_BUFFER_OVERFLOW; | |
567 | ||
568 | if (state->in_buffer.avail_in < len) | |
569 | len = state->in_buffer.avail_in; | |
570 | ||
571 | else | |
572 | state->new_block = 1; | |
573 | ||
574 | memcpy(state->out_buffer.next_out, state->in_buffer.next_in, len); | |
575 | ||
576 | state->out_buffer.next_out += len; | |
577 | state->out_buffer.avail_out -= len; | |
578 | state->out_buffer.total_out += len; | |
579 | state->in_buffer.next_in += len; | |
580 | state->in_buffer.avail_in -= len + 4; | |
581 | ||
582 | if (state->in_buffer.avail_in == 0 && state->new_block == 0) | |
583 | return END_OF_INPUT; | |
584 | ||
585 | } else { | |
586 | /* Else decode a huffman encoded block */ | |
587 | while (state->new_block == 0) { | |
588 | /* While not at the end of block, decode the next | |
589 | * symbol */ | |
590 | ||
591 | next_lit = | |
592 | decode_next(&state->in_buffer, &state->lit_huff_code); | |
593 | ||
594 | if (state->in_buffer.read_in_length < 0) | |
595 | return END_OF_INPUT; | |
596 | ||
597 | if (next_lit < 256) { | |
598 | /* If the next symbol is a literal, | |
599 | * write out the symbol and update state | |
600 | * data accordingly. */ | |
601 | if (state->out_buffer.avail_out < 1) | |
602 | return OUT_BUFFER_OVERFLOW; | |
603 | ||
604 | *state->out_buffer.next_out = next_lit; | |
605 | state->out_buffer.next_out++; | |
606 | state->out_buffer.avail_out--; | |
607 | state->out_buffer.total_out++; | |
608 | ||
609 | } else if (next_lit == 256) { | |
610 | /* If the next symbol is the end of | |
611 | * block, update the state data | |
612 | * accordingly */ | |
613 | state->new_block = 1; | |
614 | ||
615 | } else if (next_lit < 286) { | |
616 | /* Else if the next symbol is a repeat | |
617 | * length, read in the length extra | |
618 | * bits, the distance code, the distance | |
619 | * extra bits. Then write out the | |
620 | * corresponding data and update the | |
621 | * state data accordingly*/ | |
622 | repeat_length = | |
623 | len_start[next_lit - 257] + | |
624 | inflate_in_read_bits(&state->in_buffer, | |
625 | len_extra_bit_count[next_lit - | |
626 | 257]); | |
627 | ||
628 | if (state->out_buffer.avail_out < repeat_length) | |
629 | return OUT_BUFFER_OVERFLOW; | |
630 | ||
631 | next_dist = decode_next(&state->in_buffer, | |
632 | &state->dist_huff_code); | |
633 | ||
634 | look_back_dist = dist_start[next_dist] + | |
635 | inflate_in_read_bits(&state->in_buffer, | |
636 | dist_extra_bit_count | |
637 | [next_dist]); | |
638 | ||
639 | if (state->in_buffer.read_in_length < 0) | |
640 | return END_OF_INPUT; | |
641 | ||
642 | if (look_back_dist > state->out_buffer.total_out) | |
643 | return INVALID_LOOK_BACK_DISTANCE; | |
644 | ||
645 | if (look_back_dist > repeat_length) { | |
646 | memcpy(state->out_buffer.next_out, | |
647 | state->out_buffer.next_out - | |
648 | look_back_dist, repeat_length); | |
649 | } else | |
650 | byte_copy(state->out_buffer.next_out, | |
651 | look_back_dist, repeat_length); | |
652 | ||
653 | state->out_buffer.next_out += repeat_length; | |
654 | state->out_buffer.avail_out -= repeat_length; | |
655 | state->out_buffer.total_out += repeat_length; | |
656 | ||
657 | } else | |
658 | /* Else the read in bits do not | |
659 | * correspond to any valid symbol */ | |
660 | return INVALID_SYMBOL; | |
661 | } | |
662 | } | |
663 | } | |
664 | state->in_buffer.next_in -= state->in_buffer.read_in_length / 8; | |
665 | state->in_buffer.avail_in += state->in_buffer.read_in_length / 8; | |
666 | ||
667 | return DECOMPRESSION_FINISHED; | |
668 | } |