]>
Commit | Line | Data |
---|---|---|
224ce89b WB |
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 <stdint.h> | |
31 | #include "igzip_lib.h" | |
32 | #include "huff_codes.h" | |
33 | ||
34 | extern int decode_huffman_code_block_stateless(struct inflate_state *); | |
35 | extern uint32_t crc32_gzip(uint32_t init_crc, const unsigned char *buf, uint64_t len); | |
36 | ||
37 | /* structure contain lookup data based on RFC 1951 */ | |
38 | struct rfc1951_tables { | |
39 | uint8_t dist_extra_bit_count[32]; | |
40 | uint32_t dist_start[32]; | |
41 | uint8_t len_extra_bit_count[32]; | |
42 | uint16_t len_start[32]; | |
43 | ||
44 | }; | |
45 | ||
46 | /* The following tables are based on the tables in the deflate standard, | |
47 | * RFC 1951 page 11. */ | |
48 | static struct rfc1951_tables rfc_lookup_table = { | |
49 | .dist_extra_bit_count = { | |
50 | 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x02, 0x02, | |
51 | 0x03, 0x03, 0x04, 0x04, 0x05, 0x05, 0x06, 0x06, | |
52 | 0x07, 0x07, 0x08, 0x08, 0x09, 0x09, 0x0a, 0x0a, | |
53 | 0x0b, 0x0b, 0x0c, 0x0c, 0x0d, 0x0d, 0x00, 0x00}, | |
54 | ||
55 | .dist_start = { | |
56 | 0x0001, 0x0002, 0x0003, 0x0004, 0x0005, 0x0007, 0x0009, 0x000d, | |
57 | 0x0011, 0x0019, 0x0021, 0x0031, 0x0041, 0x0061, 0x0081, 0x00c1, | |
58 | 0x0101, 0x0181, 0x0201, 0x0301, 0x0401, 0x0601, 0x0801, 0x0c01, | |
59 | 0x1001, 0x1801, 0x2001, 0x3001, 0x4001, 0x6001, 0x0000, 0x0000}, | |
60 | ||
61 | .len_extra_bit_count = { | |
62 | 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, | |
63 | 0x01, 0x01, 0x01, 0x01, 0x02, 0x02, 0x02, 0x02, | |
64 | 0x03, 0x03, 0x03, 0x03, 0x04, 0x04, 0x04, 0x04, | |
65 | 0x05, 0x05, 0x05, 0x05, 0x00, 0x00, 0x00, 0x00}, | |
66 | ||
67 | .len_start = { | |
68 | 0x0003, 0x0004, 0x0005, 0x0006, 0x0007, 0x0008, 0x0009, 0x000a, | |
69 | 0x000b, 0x000d, 0x000f, 0x0011, 0x0013, 0x0017, 0x001b, 0x001f, | |
70 | 0x0023, 0x002b, 0x0033, 0x003b, 0x0043, 0x0053, 0x0063, 0x0073, | |
71 | 0x0083, 0x00a3, 0x00c3, 0x00e3, 0x0102, 0x0000, 0x0000, 0x0000} | |
72 | }; | |
73 | ||
74 | struct slver { | |
75 | uint16_t snum; | |
76 | uint8_t ver; | |
77 | uint8_t core; | |
78 | }; | |
79 | ||
80 | /* Version info */ | |
81 | struct slver isal_inflate_init_slver_00010088; | |
82 | struct slver isal_inflate_init_slver = { 0x0088, 0x01, 0x00 }; | |
83 | ||
84 | struct slver isal_inflate_stateless_slver_00010089; | |
85 | struct slver isal_inflate_stateless_slver = { 0x0089, 0x01, 0x00 }; | |
86 | ||
87 | struct slver isal_inflate_slver_0001008a; | |
88 | struct slver isal_inflate_slver = { 0x008a, 0x01, 0x00 }; | |
89 | ||
90 | /*Performs a copy of length repeat_length data starting at dest - | |
91 | * lookback_distance into dest. This copy copies data previously copied when the | |
92 | * src buffer and the dest buffer overlap. */ | |
93 | static void inline byte_copy(uint8_t * dest, uint64_t lookback_distance, int repeat_length) | |
94 | { | |
95 | uint8_t *src = dest - lookback_distance; | |
96 | ||
97 | for (; repeat_length > 0; repeat_length--) | |
98 | *dest++ = *src++; | |
99 | } | |
100 | ||
101 | /* | |
102 | * Returns integer with first length bits reversed and all higher bits zeroed | |
103 | */ | |
104 | static uint16_t inline bit_reverse2(uint16_t bits, uint8_t length) | |
105 | { | |
106 | bits = ((bits >> 1) & 0x55555555) | ((bits & 0x55555555) << 1); // swap bits | |
107 | bits = ((bits >> 2) & 0x33333333) | ((bits & 0x33333333) << 2); // swap pairs | |
108 | bits = ((bits >> 4) & 0x0F0F0F0F) | ((bits & 0x0F0F0F0F) << 4); // swap nibbles | |
109 | bits = ((bits >> 8) & 0x00FF00FF) | ((bits & 0x00FF00FF) << 8); // swap bytes | |
110 | return bits >> (16 - length); | |
111 | } | |
112 | ||
113 | /* Load data from the in_stream into a buffer to allow for handling unaligned data*/ | |
114 | static void inline inflate_in_load(struct inflate_state *state, int min_required) | |
115 | { | |
116 | uint64_t temp = 0; | |
117 | uint8_t new_bytes; | |
118 | ||
119 | if (state->read_in_length >= 64) | |
120 | return; | |
121 | ||
122 | if (state->avail_in >= 8) { | |
123 | /* If there is enough space to load a 64 bits, load the data and use | |
124 | * that to fill read_in */ | |
125 | new_bytes = 8 - (state->read_in_length + 7) / 8; | |
126 | temp = *(uint64_t *) state->next_in; | |
127 | ||
128 | state->read_in |= temp << state->read_in_length; | |
129 | state->next_in += new_bytes; | |
130 | state->avail_in -= new_bytes; | |
131 | state->read_in_length += new_bytes * 8; | |
132 | ||
133 | } else { | |
134 | /* Else fill the read_in buffer 1 byte at a time */ | |
135 | while (state->read_in_length < 57 && state->avail_in > 0) { | |
136 | temp = *state->next_in; | |
137 | state->read_in |= temp << state->read_in_length; | |
138 | state->next_in++; | |
139 | state->avail_in--; | |
140 | state->read_in_length += 8; | |
141 | ||
142 | } | |
143 | } | |
144 | } | |
145 | ||
146 | /* Returns the next bit_count bits from the in stream and shifts the stream over | |
147 | * by bit-count bits */ | |
148 | static uint64_t inline inflate_in_read_bits(struct inflate_state *state, uint8_t bit_count) | |
149 | { | |
150 | uint64_t ret; | |
151 | assert(bit_count < 57); | |
152 | ||
153 | /* Load inflate_in if not enough data is in the read_in buffer */ | |
154 | if (state->read_in_length < bit_count) | |
155 | inflate_in_load(state, bit_count); | |
156 | ||
157 | ret = (state->read_in) & ((1 << bit_count) - 1); | |
158 | state->read_in >>= bit_count; | |
159 | state->read_in_length -= bit_count; | |
160 | ||
161 | return ret; | |
162 | } | |
163 | ||
164 | /* Sets result to the inflate_huff_code corresponding to the huffcode defined by | |
165 | * the lengths in huff_code_table,where count is a histogram of the appearance | |
166 | * of each code length */ | |
167 | static void inline make_inflate_huff_code_large(struct inflate_huff_code_large *result, | |
168 | struct huff_code *huff_code_table, | |
169 | int table_length, uint16_t * count, | |
170 | uint32_t max_symbol) | |
171 | { | |
172 | int i, j, k; | |
173 | uint16_t code = 0; | |
174 | uint16_t next_code[MAX_HUFF_TREE_DEPTH + 1]; | |
175 | uint16_t long_code_list[LIT_LEN]; | |
176 | uint32_t long_code_length = 0; | |
177 | uint16_t temp_code_list[1 << (15 - ISAL_DECODE_LONG_BITS)]; | |
178 | uint32_t temp_code_length; | |
179 | uint32_t long_code_lookup_length = 0; | |
180 | uint32_t max_length; | |
181 | uint16_t first_bits; | |
182 | uint32_t code_length; | |
183 | uint16_t long_bits; | |
184 | uint16_t min_increment; | |
185 | uint32_t code_list[LIT_LEN + 2]; /* The +2 is for the extra codes in the static header */ | |
186 | uint32_t code_list_len; | |
187 | uint32_t count_total[17]; | |
188 | uint32_t insert_index; | |
189 | uint32_t last_length; | |
190 | uint32_t copy_size; | |
191 | uint16_t *short_code_lookup = result->short_code_lookup; | |
192 | ||
193 | count_total[0] = 0; | |
194 | count_total[1] = 0; | |
195 | for (i = 2; i < 17; i++) | |
196 | count_total[i] = count_total[i - 1] + count[i - 1]; | |
197 | ||
198 | code_list_len = count_total[16]; | |
199 | if (code_list_len == 0) { | |
200 | memset(result->short_code_lookup, 0, sizeof(result->short_code_lookup)); | |
201 | return; | |
202 | } | |
203 | ||
204 | for (i = 0; i < table_length; i++) { | |
205 | code_length = huff_code_table[i].length; | |
206 | if (code_length > 0) { | |
207 | insert_index = count_total[code_length]; | |
208 | code_list[insert_index] = i; | |
209 | count_total[code_length]++; | |
210 | } | |
211 | } | |
212 | ||
213 | next_code[0] = code; | |
214 | for (i = 1; i < MAX_HUFF_TREE_DEPTH + 1; i++) | |
215 | next_code[i] = (next_code[i - 1] + count[i - 1]) << 1; | |
216 | ||
217 | last_length = huff_code_table[code_list[0]].length; | |
218 | if (last_length > ISAL_DECODE_LONG_BITS) | |
219 | last_length = ISAL_DECODE_LONG_BITS; | |
220 | copy_size = (1 << last_length); | |
221 | ||
222 | /* Initialize short_code_lookup, so invalid lookups process data */ | |
223 | memset(short_code_lookup, 0x00, copy_size * sizeof(*short_code_lookup)); | |
224 | ||
225 | for (k = 0; k < code_list_len; k++) { | |
226 | i = code_list[k]; | |
227 | if (huff_code_table[i].length > ISAL_DECODE_LONG_BITS) | |
228 | break; | |
229 | ||
230 | while (huff_code_table[i].length > last_length) { | |
231 | memcpy(short_code_lookup + copy_size, short_code_lookup, | |
232 | sizeof(*short_code_lookup) * copy_size); | |
233 | last_length++; | |
234 | copy_size <<= 1; | |
235 | } | |
236 | ||
237 | /* Store codes as zero for invalid codes used in static header construction */ | |
238 | huff_code_table[i].code = | |
239 | bit_reverse2(next_code[huff_code_table[i].length], | |
240 | huff_code_table[i].length); | |
241 | ||
242 | next_code[huff_code_table[i].length] += 1; | |
243 | ||
244 | /* Set lookup table to return the current symbol concatenated | |
245 | * with the code length when the first DECODE_LENGTH bits of the | |
246 | * address are the same as the code for the current symbol. The | |
247 | * first 9 bits are the code, bits 14:10 are the code length, | |
248 | * bit 15 is a flag representing this is a symbol*/ | |
249 | ||
250 | if (i < max_symbol) | |
251 | short_code_lookup[huff_code_table[i].code] = | |
252 | i | (huff_code_table[i].length) << 9; | |
253 | ||
254 | else | |
255 | short_code_lookup[huff_code_table[i].code] = 0; | |
256 | ||
257 | } | |
258 | ||
259 | while (ISAL_DECODE_LONG_BITS > last_length) { | |
260 | memcpy(short_code_lookup + copy_size, short_code_lookup, | |
261 | sizeof(*short_code_lookup) * copy_size); | |
262 | last_length++; | |
263 | copy_size <<= 1; | |
264 | } | |
265 | ||
266 | while (k < code_list_len) { | |
267 | i = code_list[k]; | |
268 | huff_code_table[i].code = | |
269 | bit_reverse2(next_code[huff_code_table[i].length], | |
270 | huff_code_table[i].length); | |
271 | ||
272 | next_code[huff_code_table[i].length] += 1; | |
273 | ||
274 | /* Store the element in a list of elements with long codes. */ | |
275 | long_code_list[long_code_length] = i; | |
276 | long_code_length++; | |
277 | k++; | |
278 | } | |
279 | ||
280 | for (i = 0; i < long_code_length; i++) { | |
281 | /*Set the look up table to point to a hint where the symbol can be found | |
282 | * in the list of long codes and add the current symbol to the list of | |
283 | * long codes. */ | |
284 | if (huff_code_table[long_code_list[i]].code == 0xFFFF) | |
285 | continue; | |
286 | ||
287 | max_length = huff_code_table[long_code_list[i]].length; | |
288 | first_bits = | |
289 | huff_code_table[long_code_list[i]].code | |
290 | & ((1 << ISAL_DECODE_LONG_BITS) - 1); | |
291 | ||
292 | temp_code_list[0] = long_code_list[i]; | |
293 | temp_code_length = 1; | |
294 | ||
295 | for (j = i + 1; j < long_code_length; j++) { | |
296 | if ((huff_code_table[long_code_list[j]].code & | |
297 | ((1 << ISAL_DECODE_LONG_BITS) - 1)) == first_bits) { | |
298 | if (max_length < huff_code_table[long_code_list[j]].length) | |
299 | max_length = huff_code_table[long_code_list[j]].length; | |
300 | temp_code_list[temp_code_length] = long_code_list[j]; | |
301 | temp_code_length++; | |
302 | } | |
303 | } | |
304 | ||
305 | memset(&result->long_code_lookup[long_code_lookup_length], 0x00, | |
306 | 2 * (1 << (max_length - ISAL_DECODE_LONG_BITS))); | |
307 | ||
308 | for (j = 0; j < temp_code_length; j++) { | |
309 | code_length = huff_code_table[temp_code_list[j]].length; | |
310 | long_bits = | |
311 | huff_code_table[temp_code_list[j]].code >> ISAL_DECODE_LONG_BITS; | |
312 | min_increment = 1 << (code_length - ISAL_DECODE_LONG_BITS); | |
313 | for (; long_bits < (1 << (max_length - ISAL_DECODE_LONG_BITS)); | |
314 | long_bits += min_increment) { | |
315 | result->long_code_lookup[long_code_lookup_length + long_bits] = | |
316 | temp_code_list[j] | (code_length << 9); | |
317 | } | |
318 | huff_code_table[temp_code_list[j]].code = 0xFFFF; | |
319 | } | |
320 | result->short_code_lookup[first_bits] = | |
321 | long_code_lookup_length | (max_length << 9) | 0x8000; | |
322 | long_code_lookup_length += 1 << (max_length - ISAL_DECODE_LONG_BITS); | |
323 | ||
324 | } | |
325 | } | |
326 | ||
327 | static void inline make_inflate_huff_code_small(struct inflate_huff_code_small *result, | |
328 | struct huff_code *huff_code_table, | |
329 | int table_length, uint16_t * count, | |
330 | uint32_t max_symbol) | |
331 | { | |
332 | int i, j, k; | |
333 | uint16_t code = 0; | |
334 | uint16_t next_code[MAX_HUFF_TREE_DEPTH + 1]; | |
335 | uint16_t long_code_list[LIT_LEN]; | |
336 | uint32_t long_code_length = 0; | |
337 | uint16_t temp_code_list[1 << (15 - ISAL_DECODE_SHORT_BITS)]; | |
338 | uint32_t temp_code_length; | |
339 | uint32_t long_code_lookup_length = 0; | |
340 | uint32_t max_length; | |
341 | uint16_t first_bits; | |
342 | uint32_t code_length; | |
343 | uint16_t long_bits; | |
344 | uint16_t min_increment; | |
345 | uint32_t code_list[DIST_LEN + 2]; /* The +2 is for the extra codes in the static header */ | |
346 | uint32_t code_list_len; | |
347 | uint32_t count_total[17]; | |
348 | uint32_t insert_index; | |
349 | uint32_t last_length; | |
350 | uint32_t copy_size; | |
351 | uint16_t *short_code_lookup = result->short_code_lookup; | |
352 | ||
353 | count_total[0] = 0; | |
354 | count_total[1] = 0; | |
355 | for (i = 2; i < 17; i++) | |
356 | count_total[i] = count_total[i - 1] + count[i - 1]; | |
357 | ||
358 | code_list_len = count_total[16]; | |
359 | if (code_list_len == 0) { | |
360 | memset(result->short_code_lookup, 0, sizeof(result->short_code_lookup)); | |
361 | return; | |
362 | } | |
363 | ||
364 | for (i = 0; i < table_length; i++) { | |
365 | code_length = huff_code_table[i].length; | |
366 | if (code_length > 0) { | |
367 | insert_index = count_total[code_length]; | |
368 | code_list[insert_index] = i; | |
369 | count_total[code_length]++; | |
370 | } | |
371 | } | |
372 | ||
373 | next_code[0] = code; | |
374 | for (i = 1; i < MAX_HUFF_TREE_DEPTH + 1; i++) | |
375 | next_code[i] = (next_code[i - 1] + count[i - 1]) << 1; | |
376 | ||
377 | last_length = huff_code_table[code_list[0]].length; | |
378 | if (last_length > ISAL_DECODE_SHORT_BITS) | |
379 | last_length = ISAL_DECODE_SHORT_BITS; | |
380 | copy_size = (1 << last_length); | |
381 | ||
382 | /* Initialize short_code_lookup, so invalid lookups process data */ | |
383 | memset(short_code_lookup, 0x00, copy_size * sizeof(*short_code_lookup)); | |
384 | ||
385 | for (k = 0; k < code_list_len; k++) { | |
386 | i = code_list[k]; | |
387 | if (huff_code_table[i].length > ISAL_DECODE_SHORT_BITS) | |
388 | break; | |
389 | ||
390 | while (huff_code_table[i].length > last_length) { | |
391 | memcpy(short_code_lookup + copy_size, short_code_lookup, | |
392 | sizeof(*short_code_lookup) * copy_size); | |
393 | last_length++; | |
394 | copy_size <<= 1; | |
395 | } | |
396 | ||
397 | /* Store codes as zero for invalid codes used in static header construction */ | |
398 | huff_code_table[i].code = | |
399 | bit_reverse2(next_code[huff_code_table[i].length], | |
400 | huff_code_table[i].length); | |
401 | ||
402 | next_code[huff_code_table[i].length] += 1; | |
403 | ||
404 | /* Set lookup table to return the current symbol concatenated | |
405 | * with the code length when the first DECODE_LENGTH bits of the | |
406 | * address are the same as the code for the current symbol. The | |
407 | * first 9 bits are the code, bits 14:10 are the code length, | |
408 | * bit 15 is a flag representing this is a symbol*/ | |
409 | if (i < max_symbol) | |
410 | short_code_lookup[huff_code_table[i].code] = | |
411 | i | (huff_code_table[i].length) << 9; | |
412 | else | |
413 | short_code_lookup[huff_code_table[i].code] = 0; | |
414 | } | |
415 | ||
416 | while (ISAL_DECODE_SHORT_BITS > last_length) { | |
417 | memcpy(short_code_lookup + copy_size, short_code_lookup, | |
418 | sizeof(*short_code_lookup) * copy_size); | |
419 | last_length++; | |
420 | copy_size <<= 1; | |
421 | } | |
422 | ||
423 | while (k < code_list_len) { | |
424 | i = code_list[k]; | |
425 | huff_code_table[i].code = | |
426 | bit_reverse2(next_code[huff_code_table[i].length], | |
427 | huff_code_table[i].length); | |
428 | ||
429 | next_code[huff_code_table[i].length] += 1; | |
430 | ||
431 | /* Store the element in a list of elements with long codes. */ | |
432 | long_code_list[long_code_length] = i; | |
433 | long_code_length++; | |
434 | k++; | |
435 | } | |
436 | ||
437 | for (i = 0; i < long_code_length; i++) { | |
438 | /*Set the look up table to point to a hint where the symbol can be found | |
439 | * in the list of long codes and add the current symbol to the list of | |
440 | * long codes. */ | |
441 | if (huff_code_table[long_code_list[i]].code == 0xFFFF) | |
442 | continue; | |
443 | ||
444 | max_length = huff_code_table[long_code_list[i]].length; | |
445 | first_bits = | |
446 | huff_code_table[long_code_list[i]].code | |
447 | & ((1 << ISAL_DECODE_SHORT_BITS) - 1); | |
448 | ||
449 | temp_code_list[0] = long_code_list[i]; | |
450 | temp_code_length = 1; | |
451 | ||
452 | for (j = i + 1; j < long_code_length; j++) { | |
453 | if ((huff_code_table[long_code_list[j]].code & | |
454 | ((1 << ISAL_DECODE_SHORT_BITS) - 1)) == first_bits) { | |
455 | if (max_length < huff_code_table[long_code_list[j]].length) | |
456 | max_length = huff_code_table[long_code_list[j]].length; | |
457 | temp_code_list[temp_code_length] = long_code_list[j]; | |
458 | temp_code_length++; | |
459 | } | |
460 | } | |
461 | ||
462 | memset(&result->long_code_lookup[long_code_lookup_length], 0x00, | |
463 | 2 * (1 << (max_length - ISAL_DECODE_SHORT_BITS))); | |
464 | ||
465 | for (j = 0; j < temp_code_length; j++) { | |
466 | code_length = huff_code_table[temp_code_list[j]].length; | |
467 | long_bits = | |
468 | huff_code_table[temp_code_list[j]].code >> ISAL_DECODE_SHORT_BITS; | |
469 | min_increment = 1 << (code_length - ISAL_DECODE_SHORT_BITS); | |
470 | for (; long_bits < (1 << (max_length - ISAL_DECODE_SHORT_BITS)); | |
471 | long_bits += min_increment) { | |
472 | result->long_code_lookup[long_code_lookup_length + long_bits] = | |
473 | temp_code_list[j] | (code_length << 9); | |
474 | } | |
475 | huff_code_table[temp_code_list[j]].code = 0xFFFF; | |
476 | } | |
477 | result->short_code_lookup[first_bits] = | |
478 | long_code_lookup_length | (max_length << 9) | 0x8000; | |
479 | long_code_lookup_length += 1 << (max_length - ISAL_DECODE_SHORT_BITS); | |
480 | ||
481 | } | |
482 | } | |
483 | ||
484 | /* Sets the inflate_huff_codes in state to be the huffcodes corresponding to the | |
485 | * deflate static header */ | |
486 | static int inline setup_static_header(struct inflate_state *state) | |
487 | { | |
488 | /* This could be turned into a memcpy of this functions output for | |
489 | * higher speed, but then DECODE_LOOKUP_SIZE couldn't be changed without | |
490 | * regenerating the table. */ | |
491 | ||
492 | int i; | |
493 | struct huff_code lit_code[LIT_LEN + 2]; | |
494 | struct huff_code dist_code[DIST_LEN + 2]; | |
495 | ||
496 | /* These tables are based on the static huffman tree described in RFC | |
497 | * 1951 */ | |
498 | uint16_t lit_count[16] = { | |
499 | 0, 0, 0, 0, 0, 0, 0, 24, 152, 112, 0, 0, 0, 0, 0, 0 | |
500 | }; | |
501 | uint16_t dist_count[16] = { | |
502 | 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 | |
503 | }; | |
504 | ||
505 | /* These for loops set the code lengths for the static literal/length | |
506 | * and distance codes defined in the deflate standard RFC 1951 */ | |
507 | for (i = 0; i < 144; i++) | |
508 | lit_code[i].length = 8; | |
509 | ||
510 | for (i = 144; i < 256; i++) | |
511 | lit_code[i].length = 9; | |
512 | ||
513 | for (i = 256; i < 280; i++) | |
514 | lit_code[i].length = 7; | |
515 | ||
516 | for (i = 280; i < LIT_LEN + 2; i++) | |
517 | lit_code[i].length = 8; | |
518 | ||
519 | for (i = 0; i < DIST_LEN + 2; i++) | |
520 | dist_code[i].length = 5; | |
521 | ||
522 | make_inflate_huff_code_large(&state->lit_huff_code, lit_code, LIT_LEN + 2, lit_count, | |
523 | LIT_LEN); | |
524 | make_inflate_huff_code_small(&state->dist_huff_code, dist_code, DIST_LEN + 2, | |
525 | dist_count, DIST_LEN); | |
526 | ||
527 | state->block_state = ISAL_BLOCK_CODED; | |
528 | ||
529 | return 0; | |
530 | } | |
531 | ||
532 | /* Decodes the next symbol symbol in in_buffer using the huff code defined by | |
533 | * huff_code */ | |
534 | static uint16_t inline decode_next_large(struct inflate_state *state, | |
535 | struct inflate_huff_code_large *huff_code) | |
536 | { | |
537 | uint16_t next_bits; | |
538 | uint16_t next_sym; | |
539 | uint32_t bit_count; | |
540 | uint32_t bit_mask; | |
541 | ||
542 | if (state->read_in_length <= ISAL_DEF_MAX_CODE_LEN) | |
543 | inflate_in_load(state, 0); | |
544 | ||
545 | next_bits = state->read_in & ((1 << ISAL_DECODE_LONG_BITS) - 1); | |
546 | ||
547 | /* next_sym is a possible symbol decoded from next_bits. If bit 15 is 0, | |
548 | * next_code is a symbol. Bits 9:0 represent the symbol, and bits 14:10 | |
549 | * represent the length of that symbols huffman code. If next_sym is not | |
550 | * a symbol, it provides a hint of where the large symbols containin | |
551 | * this code are located. Note the hint is at largest the location the | |
552 | * first actual symbol in the long code list.*/ | |
553 | next_sym = huff_code->short_code_lookup[next_bits]; | |
554 | ||
555 | if (next_sym < 0x8000) { | |
556 | /* Return symbol found if next_code is a complete huffman code | |
557 | * and shift in buffer over by the length of the next_code */ | |
558 | bit_count = next_sym >> 9; | |
559 | state->read_in >>= bit_count; | |
560 | state->read_in_length -= bit_count; | |
561 | ||
562 | if (bit_count == 0) | |
563 | next_sym = 0x1FF; | |
564 | ||
565 | return next_sym & 0x1FF; | |
566 | ||
567 | } else { | |
568 | /* If a symbol is not found, perform a linear search of the long code | |
569 | * list starting from the hint in next_sym */ | |
570 | bit_mask = (next_sym - 0x8000) >> 9; | |
571 | bit_mask = (1 << bit_mask) - 1; | |
572 | next_bits = state->read_in & bit_mask; | |
573 | next_sym = | |
574 | huff_code->long_code_lookup[(next_sym & 0x1FF) + | |
575 | (next_bits >> ISAL_DECODE_LONG_BITS)]; | |
576 | bit_count = next_sym >> 9; | |
577 | state->read_in >>= bit_count; | |
578 | state->read_in_length -= bit_count; | |
579 | ||
580 | if (bit_count == 0) | |
581 | next_sym = 0x1FF; | |
582 | ||
583 | return next_sym & 0x1FF; | |
584 | ||
585 | } | |
586 | } | |
587 | ||
588 | static uint16_t inline decode_next_small(struct inflate_state *state, | |
589 | struct inflate_huff_code_small *huff_code) | |
590 | { | |
591 | uint16_t next_bits; | |
592 | uint16_t next_sym; | |
593 | uint32_t bit_count; | |
594 | uint32_t bit_mask; | |
595 | ||
596 | if (state->read_in_length <= ISAL_DEF_MAX_CODE_LEN) | |
597 | inflate_in_load(state, 0); | |
598 | ||
599 | next_bits = state->read_in & ((1 << ISAL_DECODE_SHORT_BITS) - 1); | |
600 | ||
601 | /* next_sym is a possible symbol decoded from next_bits. If bit 15 is 0, | |
602 | * next_code is a symbol. Bits 9:0 represent the symbol, and bits 14:10 | |
603 | * represent the length of that symbols huffman code. If next_sym is not | |
604 | * a symbol, it provides a hint of where the large symbols containin | |
605 | * this code are located. Note the hint is at largest the location the | |
606 | * first actual symbol in the long code list.*/ | |
607 | next_sym = huff_code->short_code_lookup[next_bits]; | |
608 | ||
609 | if (next_sym < 0x8000) { | |
610 | /* Return symbol found if next_code is a complete huffman code | |
611 | * and shift in buffer over by the length of the next_code */ | |
612 | bit_count = next_sym >> 9; | |
613 | state->read_in >>= bit_count; | |
614 | state->read_in_length -= bit_count; | |
615 | ||
616 | if (bit_count == 0) | |
617 | next_sym = 0x1FF; | |
618 | ||
619 | return next_sym & 0x1FF; | |
620 | ||
621 | } else { | |
622 | /* If a symbol is not found, perform a linear search of the long code | |
623 | * list starting from the hint in next_sym */ | |
624 | bit_mask = (next_sym - 0x8000) >> 9; | |
625 | bit_mask = (1 << bit_mask) - 1; | |
626 | next_bits = state->read_in & bit_mask; | |
627 | next_sym = | |
628 | huff_code->long_code_lookup[(next_sym & 0x1FF) + | |
629 | (next_bits >> ISAL_DECODE_SHORT_BITS)]; | |
630 | bit_count = next_sym >> 9; | |
631 | state->read_in >>= bit_count; | |
632 | state->read_in_length -= bit_count; | |
633 | return next_sym & 0x1FF; | |
634 | ||
635 | } | |
636 | } | |
637 | ||
638 | /* Reads data from the in_buffer and sets the huff code corresponding to that | |
639 | * data */ | |
640 | static int inline setup_dynamic_header(struct inflate_state *state) | |
641 | { | |
642 | int i, j; | |
643 | struct huff_code code_huff[CODE_LEN_CODES]; | |
644 | struct huff_code lit_and_dist_huff[LIT_LEN + DIST_LEN]; | |
645 | struct huff_code *previous = NULL, *current, *end; | |
646 | struct inflate_huff_code_small inflate_code_huff; | |
647 | uint8_t hclen, hdist, hlit; | |
648 | uint16_t code_count[16], lit_count[16], dist_count[16]; | |
649 | uint16_t *count; | |
650 | uint16_t symbol; | |
651 | ||
652 | /* This order is defined in RFC 1951 page 13 */ | |
653 | const uint8_t code_length_code_order[CODE_LEN_CODES] = { | |
654 | 0x10, 0x11, 0x12, 0x00, 0x08, 0x07, 0x09, 0x06, | |
655 | 0x0a, 0x05, 0x0b, 0x04, 0x0c, 0x03, 0x0d, 0x02, | |
656 | 0x0e, 0x01, 0x0f | |
657 | }; | |
658 | ||
659 | memset(code_count, 0, sizeof(code_count)); | |
660 | memset(lit_count, 0, sizeof(lit_count)); | |
661 | memset(dist_count, 0, sizeof(dist_count)); | |
662 | memset(code_huff, 0, sizeof(code_huff)); | |
663 | memset(lit_and_dist_huff, 0, sizeof(lit_and_dist_huff)); | |
664 | ||
665 | /* These variables are defined in the deflate standard, RFC 1951 */ | |
666 | hlit = inflate_in_read_bits(state, 5); | |
667 | hdist = inflate_in_read_bits(state, 5); | |
668 | hclen = inflate_in_read_bits(state, 4); | |
669 | ||
670 | if (hlit > 29 || hdist > 29 || hclen > 15) | |
671 | return ISAL_INVALID_BLOCK; | |
672 | ||
673 | /* Create the code huffman code for decoding the lit/len and dist huffman codes */ | |
674 | for (i = 0; i < hclen + 4; i++) { | |
675 | code_huff[code_length_code_order[i]].length = inflate_in_read_bits(state, 3); | |
676 | ||
677 | code_count[code_huff[code_length_code_order[i]].length] += 1; | |
678 | } | |
679 | ||
680 | /* Check that the code huffman code has a symbol */ | |
681 | for (i = 1; i < 16; i++) { | |
682 | if (code_count[i] != 0) | |
683 | break; | |
684 | } | |
685 | ||
686 | if (state->read_in_length < 0) | |
687 | return ISAL_END_INPUT; | |
688 | ||
689 | if (i == 16) | |
690 | return ISAL_INVALID_BLOCK; | |
691 | ||
692 | make_inflate_huff_code_small(&inflate_code_huff, code_huff, CODE_LEN_CODES, | |
693 | code_count, CODE_LEN_CODES); | |
694 | ||
695 | /* Decode the lit/len and dist huffman codes using the code huffman code */ | |
696 | count = lit_count; | |
697 | current = lit_and_dist_huff; | |
698 | end = lit_and_dist_huff + LIT_LEN + hdist + 1; | |
699 | ||
700 | while (current < end) { | |
701 | /* If finished decoding the lit/len huffman code, start decoding | |
702 | * the distance code these decodings are in the same loop | |
703 | * because the len/lit and dist huffman codes are run length | |
704 | * encoded together. */ | |
705 | if (current == lit_and_dist_huff + 257 + hlit) | |
706 | current = lit_and_dist_huff + LIT_LEN; | |
707 | ||
708 | if (current == lit_and_dist_huff + LIT_LEN) | |
709 | count = dist_count; | |
710 | ||
711 | symbol = decode_next_small(state, &inflate_code_huff); | |
712 | ||
713 | if (state->read_in_length < 0) { | |
714 | if (current > &lit_and_dist_huff[256] | |
715 | && lit_and_dist_huff[256].length <= 0) | |
716 | return ISAL_INVALID_BLOCK; | |
717 | return ISAL_END_INPUT; | |
718 | } | |
719 | ||
720 | if (symbol < 16) { | |
721 | /* If a length is found, update the current lit/len/dist | |
722 | * to have length symbol */ | |
723 | count[symbol]++; | |
724 | current->length = symbol; | |
725 | previous = current; | |
726 | current++; | |
727 | ||
728 | } else if (symbol == 16) { | |
729 | /* If a repeat length is found, update the next repeat | |
730 | * length lit/len/dist elements to have the value of the | |
731 | * repeated length */ | |
732 | if (previous == NULL) /* No elements available to be repeated */ | |
733 | return ISAL_INVALID_BLOCK; | |
734 | ||
735 | i = 3 + inflate_in_read_bits(state, 2); | |
736 | ||
737 | if (current + i > end) | |
738 | return ISAL_INVALID_BLOCK; | |
739 | ||
740 | for (j = 0; j < i; j++) { | |
741 | *current = *previous; | |
742 | count[current->length]++; | |
743 | previous = current; | |
744 | ||
745 | if (current == lit_and_dist_huff + 256 + hlit) { | |
746 | current = lit_and_dist_huff + LIT_LEN; | |
747 | count = dist_count; | |
748 | ||
749 | } else | |
750 | current++; | |
751 | } | |
752 | ||
753 | } else if (symbol == 17) { | |
754 | /* If a repeat zeroes if found, update then next | |
755 | * repeated zeroes length lit/len/dist elements to have | |
756 | * length 0. */ | |
757 | i = 3 + inflate_in_read_bits(state, 3); | |
758 | ||
759 | for (j = 0; j < i; j++) { | |
760 | previous = current; | |
761 | ||
762 | if (current == lit_and_dist_huff + 256 + hlit) { | |
763 | current = lit_and_dist_huff + LIT_LEN; | |
764 | count = dist_count; | |
765 | ||
766 | } else | |
767 | current++; | |
768 | } | |
769 | ||
770 | } else if (symbol == 18) { | |
771 | /* If a repeat zeroes if found, update then next | |
772 | * repeated zeroes length lit/len/dist elements to have | |
773 | * length 0. */ | |
774 | i = 11 + inflate_in_read_bits(state, 7); | |
775 | ||
776 | for (j = 0; j < i; j++) { | |
777 | previous = current; | |
778 | ||
779 | if (current == lit_and_dist_huff + 256 + hlit) { | |
780 | current = lit_and_dist_huff + LIT_LEN; | |
781 | count = dist_count; | |
782 | ||
783 | } else | |
784 | current++; | |
785 | } | |
786 | } else | |
787 | return ISAL_INVALID_BLOCK; | |
788 | ||
789 | } | |
790 | ||
791 | if (current > end || lit_and_dist_huff[256].length <= 0) | |
792 | return ISAL_INVALID_BLOCK; | |
793 | ||
794 | if (state->read_in_length < 0) | |
795 | return ISAL_END_INPUT; | |
796 | ||
797 | make_inflate_huff_code_large(&state->lit_huff_code, lit_and_dist_huff, LIT_LEN, | |
798 | lit_count, LIT_LEN); | |
799 | make_inflate_huff_code_small(&state->dist_huff_code, &lit_and_dist_huff[LIT_LEN], | |
800 | DIST_LEN, dist_count, DIST_LEN); | |
801 | ||
802 | state->block_state = ISAL_BLOCK_CODED; | |
803 | ||
804 | return 0; | |
805 | } | |
806 | ||
807 | /* Reads in the header pointed to by in_stream and sets up state to reflect that | |
808 | * header information*/ | |
809 | int read_header(struct inflate_state *state) | |
810 | { | |
811 | uint8_t bytes; | |
812 | uint32_t btype; | |
813 | uint16_t len, nlen; | |
814 | int ret = 0; | |
815 | ||
816 | /* btype and bfinal are defined in RFC 1951, bfinal represents whether | |
817 | * the current block is the end of block, and btype represents the | |
818 | * encoding method on the current block. */ | |
819 | ||
820 | state->bfinal = inflate_in_read_bits(state, 1); | |
821 | btype = inflate_in_read_bits(state, 2); | |
822 | ||
823 | if (state->read_in_length < 0) | |
824 | ret = ISAL_END_INPUT; | |
825 | ||
826 | else if (btype == 0) { | |
827 | inflate_in_load(state, 40); | |
828 | bytes = state->read_in_length / 8; | |
829 | ||
830 | if (bytes < 4) | |
831 | return ISAL_END_INPUT; | |
832 | ||
833 | state->read_in >>= state->read_in_length % 8; | |
834 | state->read_in_length = bytes * 8; | |
835 | ||
836 | len = state->read_in & 0xFFFF; | |
837 | state->read_in >>= 16; | |
838 | nlen = state->read_in & 0xFFFF; | |
839 | state->read_in >>= 16; | |
840 | state->read_in_length -= 32; | |
841 | ||
842 | bytes = state->read_in_length / 8; | |
843 | ||
844 | state->next_in -= bytes; | |
845 | state->avail_in += bytes; | |
846 | state->read_in = 0; | |
847 | state->read_in_length = 0; | |
848 | ||
849 | /* Check if len and nlen match */ | |
850 | if (len != (~nlen & 0xffff)) | |
851 | return ISAL_INVALID_BLOCK; | |
852 | ||
853 | state->type0_block_len = len; | |
854 | state->block_state = ISAL_BLOCK_TYPE0; | |
855 | ||
856 | ret = 0; | |
857 | ||
858 | } else if (btype == 1) | |
859 | ret = setup_static_header(state); | |
860 | ||
861 | else if (btype == 2) | |
862 | ret = setup_dynamic_header(state); | |
863 | ||
864 | else | |
865 | ret = ISAL_INVALID_BLOCK; | |
866 | ||
867 | return ret; | |
868 | } | |
869 | ||
870 | /* Reads in the header pointed to by in_stream and sets up state to reflect that | |
871 | * header information*/ | |
872 | int read_header_stateful(struct inflate_state *state) | |
873 | { | |
874 | uint64_t read_in_start = state->read_in; | |
875 | int32_t read_in_length_start = state->read_in_length; | |
876 | uint8_t *next_in_start = state->next_in; | |
877 | uint32_t avail_in_start = state->avail_in; | |
878 | int block_state_start = state->block_state; | |
879 | int ret; | |
880 | int copy_size; | |
881 | int bytes_read; | |
882 | ||
883 | if (block_state_start == ISAL_BLOCK_HDR) { | |
884 | /* Setup so read_header decodes data in tmp_in_buffer */ | |
885 | copy_size = ISAL_DEF_MAX_HDR_SIZE - state->tmp_in_size; | |
886 | if (copy_size > state->avail_in) | |
887 | copy_size = state->avail_in; | |
888 | ||
889 | memcpy(&state->tmp_in_buffer[state->tmp_in_size], state->next_in, copy_size); | |
890 | state->next_in = state->tmp_in_buffer; | |
891 | state->avail_in = state->tmp_in_size + copy_size; | |
892 | } | |
893 | ||
894 | ret = read_header(state); | |
895 | ||
896 | if (block_state_start == ISAL_BLOCK_HDR) { | |
897 | /* Setup so state is restored to a valid state */ | |
898 | bytes_read = state->next_in - state->tmp_in_buffer - state->tmp_in_size; | |
899 | if (bytes_read < 0) | |
900 | bytes_read = 0; | |
901 | state->next_in = next_in_start + bytes_read; | |
902 | state->avail_in = avail_in_start - bytes_read; | |
903 | } | |
904 | ||
905 | if (ret == ISAL_END_INPUT) { | |
906 | /* Save off data so header can be decoded again with more data */ | |
907 | state->read_in = read_in_start; | |
908 | state->read_in_length = read_in_length_start; | |
909 | memcpy(&state->tmp_in_buffer[state->tmp_in_size], next_in_start, | |
910 | avail_in_start); | |
911 | state->tmp_in_size += avail_in_start; | |
912 | state->avail_in = 0; | |
913 | state->next_in = next_in_start + avail_in_start; | |
914 | state->block_state = ISAL_BLOCK_HDR; | |
915 | } else | |
916 | state->tmp_in_size = 0; | |
917 | ||
918 | return ret; | |
919 | ||
920 | } | |
921 | ||
922 | static int inline decode_literal_block(struct inflate_state *state) | |
923 | { | |
924 | uint32_t len = state->type0_block_len; | |
925 | /* If the block is uncompressed, perform a memcopy while | |
926 | * updating state data */ | |
927 | ||
928 | state->block_state = ISAL_BLOCK_NEW_HDR; | |
929 | ||
930 | if (state->avail_out < len) { | |
931 | len = state->avail_out; | |
932 | state->block_state = ISAL_BLOCK_TYPE0; | |
933 | } | |
934 | ||
935 | if (state->avail_in < len) { | |
936 | len = state->avail_in; | |
937 | state->block_state = ISAL_BLOCK_TYPE0; | |
938 | } | |
939 | ||
940 | memcpy(state->next_out, state->next_in, len); | |
941 | ||
942 | state->next_out += len; | |
943 | state->avail_out -= len; | |
944 | state->total_out += len; | |
945 | state->next_in += len; | |
946 | state->avail_in -= len; | |
947 | state->type0_block_len -= len; | |
948 | ||
949 | if (state->avail_in == 0 && state->block_state != ISAL_BLOCK_NEW_HDR) | |
950 | return ISAL_END_INPUT; | |
951 | ||
952 | if (state->avail_out == 0 && state->type0_block_len > 0) | |
953 | return ISAL_OUT_OVERFLOW; | |
954 | ||
955 | return 0; | |
956 | ||
957 | } | |
958 | ||
959 | /* Decodes the next block if it was encoded using a huffman code */ | |
960 | int decode_huffman_code_block_stateless_base(struct inflate_state *state) | |
961 | { | |
962 | uint16_t next_lit; | |
963 | uint8_t next_dist; | |
964 | uint32_t repeat_length; | |
965 | uint32_t look_back_dist; | |
966 | uint64_t read_in_tmp; | |
967 | int32_t read_in_length_tmp; | |
968 | uint8_t *next_in_tmp; | |
969 | uint32_t avail_in_tmp; | |
970 | ||
971 | state->copy_overflow_length = 0; | |
972 | state->copy_overflow_distance = 0; | |
973 | ||
974 | while (state->block_state == ISAL_BLOCK_CODED) { | |
975 | /* While not at the end of block, decode the next | |
976 | * symbol */ | |
977 | inflate_in_load(state, 0); | |
978 | ||
979 | read_in_tmp = state->read_in; | |
980 | read_in_length_tmp = state->read_in_length; | |
981 | next_in_tmp = state->next_in; | |
982 | avail_in_tmp = state->avail_in; | |
983 | ||
984 | next_lit = decode_next_large(state, &state->lit_huff_code); | |
985 | ||
986 | if (state->read_in_length < 0) { | |
987 | state->read_in = read_in_tmp; | |
988 | state->read_in_length = read_in_length_tmp; | |
989 | state->next_in = next_in_tmp; | |
990 | state->avail_in = avail_in_tmp; | |
991 | return ISAL_END_INPUT; | |
992 | } | |
993 | ||
994 | if (next_lit < 256) { | |
995 | /* If the next symbol is a literal, | |
996 | * write out the symbol and update state | |
997 | * data accordingly. */ | |
998 | if (state->avail_out < 1) { | |
999 | state->read_in = read_in_tmp; | |
1000 | state->read_in_length = read_in_length_tmp; | |
1001 | state->next_in = next_in_tmp; | |
1002 | state->avail_in = avail_in_tmp; | |
1003 | return ISAL_OUT_OVERFLOW; | |
1004 | } | |
1005 | ||
1006 | *state->next_out = next_lit; | |
1007 | state->next_out++; | |
1008 | state->avail_out--; | |
1009 | state->total_out++; | |
1010 | ||
1011 | } else if (next_lit == 256) { | |
1012 | /* If the next symbol is the end of | |
1013 | * block, update the state data | |
1014 | * accordingly */ | |
1015 | state->block_state = ISAL_BLOCK_NEW_HDR; | |
1016 | ||
1017 | } else if (next_lit < 286) { | |
1018 | /* Else if the next symbol is a repeat | |
1019 | * length, read in the length extra | |
1020 | * bits, the distance code, the distance | |
1021 | * extra bits. Then write out the | |
1022 | * corresponding data and update the | |
1023 | * state data accordingly*/ | |
1024 | repeat_length = | |
1025 | rfc_lookup_table.len_start[next_lit - 257] + | |
1026 | inflate_in_read_bits(state, | |
1027 | rfc_lookup_table.len_extra_bit_count[next_lit | |
1028 | - 257]); | |
1029 | next_dist = decode_next_small(state, &state->dist_huff_code); | |
1030 | ||
1031 | if (next_dist >= DIST_LEN) | |
1032 | return ISAL_INVALID_SYMBOL; | |
1033 | ||
1034 | look_back_dist = rfc_lookup_table.dist_start[next_dist] + | |
1035 | inflate_in_read_bits(state, | |
1036 | rfc_lookup_table.dist_extra_bit_count | |
1037 | [next_dist]); | |
1038 | ||
1039 | if (state->read_in_length < 0) { | |
1040 | state->read_in = read_in_tmp; | |
1041 | state->read_in_length = read_in_length_tmp; | |
1042 | state->next_in = next_in_tmp; | |
1043 | state->avail_in = avail_in_tmp; | |
1044 | return ISAL_END_INPUT; | |
1045 | } | |
1046 | ||
1047 | if (look_back_dist > state->total_out) | |
1048 | return ISAL_INVALID_LOOKBACK; | |
1049 | ||
1050 | if (state->avail_out < repeat_length) { | |
1051 | state->copy_overflow_length = repeat_length - state->avail_out; | |
1052 | state->copy_overflow_distance = look_back_dist; | |
1053 | repeat_length = state->avail_out; | |
1054 | } | |
1055 | ||
1056 | if (look_back_dist > repeat_length) | |
1057 | memcpy(state->next_out, | |
1058 | state->next_out - look_back_dist, repeat_length); | |
1059 | else | |
1060 | byte_copy(state->next_out, look_back_dist, repeat_length); | |
1061 | ||
1062 | state->next_out += repeat_length; | |
1063 | state->avail_out -= repeat_length; | |
1064 | state->total_out += repeat_length; | |
1065 | ||
1066 | if (state->copy_overflow_length > 0) | |
1067 | return ISAL_OUT_OVERFLOW; | |
1068 | } else | |
1069 | /* Else the read in bits do not | |
1070 | * correspond to any valid symbol */ | |
1071 | return ISAL_INVALID_SYMBOL; | |
1072 | } | |
1073 | return 0; | |
1074 | } | |
1075 | ||
1076 | void isal_inflate_init(struct inflate_state *state) | |
1077 | { | |
1078 | ||
1079 | state->read_in = 0; | |
1080 | state->read_in_length = 0; | |
1081 | state->next_in = NULL; | |
1082 | state->avail_in = 0; | |
1083 | state->next_out = NULL; | |
1084 | state->avail_out = 0; | |
1085 | state->total_out = 0; | |
1086 | state->block_state = ISAL_BLOCK_NEW_HDR; | |
1087 | state->bfinal = 0; | |
1088 | state->crc_flag = 0; | |
1089 | state->crc = 0; | |
1090 | state->type0_block_len = 0; | |
1091 | state->copy_overflow_length = 0; | |
1092 | state->copy_overflow_distance = 0; | |
1093 | state->tmp_in_size = 0; | |
1094 | state->tmp_out_processed = 0; | |
1095 | state->tmp_out_valid = 0; | |
1096 | } | |
1097 | ||
1098 | int isal_inflate_stateless(struct inflate_state *state) | |
1099 | { | |
1100 | uint32_t ret = 0; | |
1101 | uint8_t *start_out = state->next_out; | |
1102 | ||
1103 | state->read_in = 0; | |
1104 | state->read_in_length = 0; | |
1105 | state->block_state = ISAL_BLOCK_NEW_HDR; | |
1106 | state->bfinal = 0; | |
1107 | state->crc = 0; | |
1108 | state->total_out = 0; | |
1109 | ||
1110 | while (state->block_state != ISAL_BLOCK_FINISH) { | |
1111 | if (state->block_state == ISAL_BLOCK_NEW_HDR) { | |
1112 | ret = read_header(state); | |
1113 | ||
1114 | if (ret) | |
1115 | break; | |
1116 | } | |
1117 | ||
1118 | if (state->block_state == ISAL_BLOCK_TYPE0) | |
1119 | ret = decode_literal_block(state); | |
1120 | else | |
1121 | ret = decode_huffman_code_block_stateless(state); | |
1122 | ||
1123 | if (ret) | |
1124 | break; | |
1125 | if (state->bfinal != 0 && state->block_state == ISAL_BLOCK_NEW_HDR) | |
1126 | state->block_state = ISAL_BLOCK_FINISH; | |
1127 | } | |
1128 | ||
1129 | if (state->crc_flag) | |
1130 | state->crc = crc32_gzip(state->crc, start_out, state->next_out - start_out); | |
1131 | ||
1132 | /* Undo count stuff of bytes read into the read buffer */ | |
1133 | state->next_in -= state->read_in_length / 8; | |
1134 | state->avail_in += state->read_in_length / 8; | |
1135 | ||
1136 | return ret; | |
1137 | } | |
1138 | ||
1139 | int isal_inflate(struct inflate_state *state) | |
1140 | { | |
1141 | ||
1142 | uint8_t *start_out = state->next_out; | |
1143 | uint32_t avail_out = state->avail_out; | |
1144 | uint32_t copy_size = 0; | |
1145 | int32_t shift_size = 0; | |
1146 | int ret = 0; | |
1147 | ||
1148 | if (state->block_state != ISAL_BLOCK_FINISH) { | |
1149 | /* If space in tmp_out buffer, decompress into the tmp_out_buffer */ | |
1150 | if (state->tmp_out_valid < 2 * ISAL_DEF_HIST_SIZE) { | |
1151 | /* Setup to start decoding into temp buffer */ | |
1152 | state->next_out = &state->tmp_out_buffer[state->tmp_out_valid]; | |
1153 | state->avail_out = | |
1154 | sizeof(state->tmp_out_buffer) - ISAL_LOOK_AHEAD - | |
1155 | state->tmp_out_valid; | |
1156 | ||
1157 | if ((int32_t) state->avail_out < 0) | |
1158 | state->avail_out = 0; | |
1159 | ||
1160 | /* Decode into internal buffer until exit */ | |
1161 | while (state->block_state != ISAL_BLOCK_INPUT_DONE) { | |
1162 | if (state->block_state == ISAL_BLOCK_NEW_HDR | |
1163 | || state->block_state == ISAL_BLOCK_HDR) { | |
1164 | ret = read_header_stateful(state); | |
1165 | ||
1166 | if (ret) | |
1167 | break; | |
1168 | } | |
1169 | ||
1170 | if (state->block_state == ISAL_BLOCK_TYPE0) { | |
1171 | ret = decode_literal_block(state); | |
1172 | } else | |
1173 | ret = decode_huffman_code_block_stateless(state); | |
1174 | ||
1175 | if (ret) | |
1176 | break; | |
1177 | if (state->bfinal != 0 | |
1178 | && state->block_state == ISAL_BLOCK_NEW_HDR) | |
1179 | state->block_state = ISAL_BLOCK_INPUT_DONE; | |
1180 | } | |
1181 | ||
1182 | /* Copy valid data from internal buffer into out_buffer */ | |
1183 | if (state->copy_overflow_length != 0) { | |
1184 | byte_copy(state->next_out, state->copy_overflow_distance, | |
1185 | state->copy_overflow_length); | |
1186 | state->tmp_out_valid += state->copy_overflow_length; | |
1187 | state->next_out += state->copy_overflow_length; | |
1188 | state->total_out += state->copy_overflow_length; | |
1189 | state->copy_overflow_distance = 0; | |
1190 | state->copy_overflow_length = 0; | |
1191 | } | |
1192 | ||
1193 | state->tmp_out_valid = state->next_out - state->tmp_out_buffer; | |
1194 | ||
1195 | /* Setup state for decompressing into out_buffer */ | |
1196 | state->next_out = start_out; | |
1197 | state->avail_out = avail_out; | |
1198 | } | |
1199 | ||
1200 | /* Copy data from tmp_out buffer into out_buffer */ | |
1201 | copy_size = state->tmp_out_valid - state->tmp_out_processed; | |
1202 | if (copy_size > avail_out) | |
1203 | copy_size = avail_out; | |
1204 | ||
1205 | memcpy(state->next_out, | |
1206 | &state->tmp_out_buffer[state->tmp_out_processed], copy_size); | |
1207 | ||
1208 | state->tmp_out_processed += copy_size; | |
1209 | state->avail_out -= copy_size; | |
1210 | state->next_out += copy_size; | |
1211 | ||
1212 | if (ret == ISAL_INVALID_LOOKBACK || ret == ISAL_INVALID_BLOCK | |
1213 | || ret == ISAL_INVALID_SYMBOL) { | |
1214 | /* Set total_out to not count data in tmp_out_buffer */ | |
1215 | state->total_out -= state->tmp_out_valid - state->tmp_out_processed; | |
1216 | if (state->crc_flag) | |
1217 | state->crc = | |
1218 | crc32_gzip(state->crc, start_out, | |
1219 | state->next_out - start_out); | |
1220 | return ret; | |
1221 | } | |
1222 | ||
1223 | /* If all data from tmp_out buffer has been processed, start | |
1224 | * decompressing into the out buffer */ | |
1225 | if (state->tmp_out_processed == state->tmp_out_valid) { | |
1226 | while (state->block_state != ISAL_BLOCK_INPUT_DONE) { | |
1227 | if (state->block_state == ISAL_BLOCK_NEW_HDR | |
1228 | || state->block_state == ISAL_BLOCK_HDR) { | |
1229 | ret = read_header_stateful(state); | |
1230 | if (ret) | |
1231 | break; | |
1232 | } | |
1233 | ||
1234 | if (state->block_state == ISAL_BLOCK_TYPE0) | |
1235 | ret = decode_literal_block(state); | |
1236 | else | |
1237 | ret = decode_huffman_code_block_stateless(state); | |
1238 | if (ret) | |
1239 | break; | |
1240 | if (state->bfinal != 0 | |
1241 | && state->block_state == ISAL_BLOCK_NEW_HDR) | |
1242 | state->block_state = ISAL_BLOCK_INPUT_DONE; | |
1243 | } | |
1244 | } | |
1245 | ||
1246 | if (state->crc_flag) | |
1247 | state->crc = | |
1248 | crc32_gzip(state->crc, start_out, state->next_out - start_out); | |
1249 | ||
1250 | if (state->block_state != ISAL_BLOCK_INPUT_DONE) { | |
1251 | /* Save decompression history in tmp_out buffer */ | |
1252 | if (state->tmp_out_valid == state->tmp_out_processed | |
1253 | && avail_out - state->avail_out >= ISAL_DEF_HIST_SIZE) { | |
1254 | memcpy(state->tmp_out_buffer, | |
1255 | state->next_out - ISAL_DEF_HIST_SIZE, | |
1256 | ISAL_DEF_HIST_SIZE); | |
1257 | state->tmp_out_valid = ISAL_DEF_HIST_SIZE; | |
1258 | state->tmp_out_processed = ISAL_DEF_HIST_SIZE; | |
1259 | ||
1260 | } else if (state->tmp_out_processed >= ISAL_DEF_HIST_SIZE) { | |
1261 | shift_size = state->tmp_out_valid - ISAL_DEF_HIST_SIZE; | |
1262 | if (shift_size > state->tmp_out_processed) | |
1263 | shift_size = state->tmp_out_processed; | |
1264 | ||
1265 | memmove(state->tmp_out_buffer, | |
1266 | &state->tmp_out_buffer[shift_size], | |
1267 | state->tmp_out_valid - shift_size); | |
1268 | state->tmp_out_valid -= shift_size; | |
1269 | state->tmp_out_processed -= shift_size; | |
1270 | ||
1271 | } | |
1272 | ||
1273 | if (state->copy_overflow_length != 0) { | |
1274 | byte_copy(&state->tmp_out_buffer[state->tmp_out_valid], | |
1275 | state->copy_overflow_distance, | |
1276 | state->copy_overflow_length); | |
1277 | state->tmp_out_valid += state->copy_overflow_length; | |
1278 | state->total_out += state->copy_overflow_length; | |
1279 | state->copy_overflow_distance = 0; | |
1280 | state->copy_overflow_length = 0; | |
1281 | } | |
1282 | ||
1283 | if (ret == ISAL_INVALID_LOOKBACK || ret == ISAL_INVALID_BLOCK | |
1284 | || ret == ISAL_INVALID_SYMBOL) | |
1285 | return ret; | |
1286 | ||
1287 | } else if (state->tmp_out_valid == state->tmp_out_processed) | |
1288 | state->block_state = ISAL_BLOCK_FINISH; | |
1289 | } | |
1290 | ||
1291 | return ISAL_DECOMP_OK; | |
1292 | } |