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 "crc.h"
33 #include "huff_codes.h"
34 #include "igzip_checksums.h"
35 #include "igzip_wrapper.h"
36 #include "unaligned.h"
37
38 #ifndef NO_STATIC_INFLATE_H
39 #include "static_inflate.h"
40 #endif
41
42 extern int
43 decode_huffman_code_block_stateless(struct inflate_state *, uint8_t *start_out);
44 extern struct isal_hufftables hufftables_default; /* For known header detection */
45
46 #define LARGE_SHORT_SYM_LEN 25
47 #define LARGE_SHORT_SYM_MASK ((1 << LARGE_SHORT_SYM_LEN) - 1)
48 #define LARGE_LONG_SYM_LEN 10
49 #define LARGE_LONG_SYM_MASK ((1 << LARGE_LONG_SYM_LEN) - 1)
50 #define LARGE_SHORT_CODE_LEN_OFFSET 28
51 #define LARGE_LONG_CODE_LEN_OFFSET 10
52 #define LARGE_FLAG_BIT_OFFSET 25
53 #define LARGE_FLAG_BIT (1 << LARGE_FLAG_BIT_OFFSET)
54 #define LARGE_SYM_COUNT_OFFSET 26
55 #define LARGE_SYM_COUNT_LEN 2
56 #define LARGE_SYM_COUNT_MASK ((1 << LARGE_SYM_COUNT_LEN) - 1)
57 #define LARGE_SHORT_MAX_LEN_OFFSET 26
58
59 #define SMALL_SHORT_SYM_LEN 9
60 #define SMALL_SHORT_SYM_MASK ((1 << SMALL_SHORT_SYM_LEN) - 1)
61 #define SMALL_LONG_SYM_LEN 9
62 #define SMALL_LONG_SYM_MASK ((1 << SMALL_LONG_SYM_LEN) - 1)
63 #define SMALL_SHORT_CODE_LEN_OFFSET 11
64 #define SMALL_LONG_CODE_LEN_OFFSET 10
65 #define SMALL_FLAG_BIT_OFFSET 10
66 #define SMALL_FLAG_BIT (1 << SMALL_FLAG_BIT_OFFSET)
67
68 #define DIST_SYM_OFFSET 0
69 #define DIST_SYM_LEN 5
70 #define DIST_SYM_MASK ((1 << DIST_SYM_LEN) - 1)
71 #define DIST_SYM_EXTRA_OFFSET 5
72 #define DIST_SYM_EXTRA_LEN 4
73 #define DIST_SYM_EXTRA_MASK ((1 << DIST_SYM_EXTRA_LEN) - 1)
74
75 #define MAX_LIT_LEN_CODE_LEN 21
76 #define MAX_LIT_LEN_COUNT (MAX_LIT_LEN_CODE_LEN + 2)
77 #define MAX_LIT_LEN_SYM 512
78 #define LIT_LEN_ELEMS 514
79
80 #define INVALID_SYMBOL 0x1FFF
81 #define INVALID_CODE 0xFFFFFF
82
83 #define MIN_DEF_MATCH 3
84
85 #define TRIPLE_SYM_FLAG 0
86 #define DOUBLE_SYM_FLAG TRIPLE_SYM_FLAG + 1
87 #define SINGLE_SYM_FLAG DOUBLE_SYM_FLAG + 1
88 #define DEFAULT_SYM_FLAG TRIPLE_SYM_FLAG
89
90 #define SINGLE_SYM_THRESH (2 * 1024)
91 #define DOUBLE_SYM_THRESH (4 * 1024)
92
93 /* structure contain lookup data based on RFC 1951 */
94 struct rfc1951_tables {
95 uint8_t dist_extra_bit_count[32];
96 uint32_t dist_start[32];
97 uint8_t len_extra_bit_count[32];
98 uint16_t len_start[32];
99 };
100
101 /* The following tables are based on the tables in the deflate standard,
102 * RFC 1951 page 11. */
103 static struct rfc1951_tables rfc_lookup_table = {
104 .dist_extra_bit_count = { 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x02, 0x02, 0x03, 0x03, 0x04,
105 0x04, 0x05, 0x05, 0x06, 0x06, 0x07, 0x07, 0x08, 0x08, 0x09, 0x09,
106 0x0a, 0x0a, 0x0b, 0x0b, 0x0c, 0x0c, 0x0d, 0x0d, 0x00, 0x00 },
107
108 .dist_start = { 0x0001, 0x0002, 0x0003, 0x0004, 0x0005, 0x0007, 0x0009, 0x000d,
109 0x0011, 0x0019, 0x0021, 0x0031, 0x0041, 0x0061, 0x0081, 0x00c1,
110 0x0101, 0x0181, 0x0201, 0x0301, 0x0401, 0x0601, 0x0801, 0x0c01,
111 0x1001, 0x1801, 0x2001, 0x3001, 0x4001, 0x6001, 0x0000, 0x0000 },
112
113 .len_extra_bit_count = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x01,
114 0x01, 0x02, 0x02, 0x02, 0x02, 0x03, 0x03, 0x03, 0x03, 0x04, 0x04,
115 0x04, 0x04, 0x05, 0x05, 0x05, 0x05, 0x00, 0x00, 0x00, 0x00 },
116
117 .len_start = { 0x0003, 0x0004, 0x0005, 0x0006, 0x0007, 0x0008, 0x0009, 0x000a,
118 0x000b, 0x000d, 0x000f, 0x0011, 0x0013, 0x0017, 0x001b, 0x001f,
119 0x0023, 0x002b, 0x0033, 0x003b, 0x0043, 0x0053, 0x0063, 0x0073,
120 0x0083, 0x00a3, 0x00c3, 0x00e3, 0x0102, 0x0103, 0x0000, 0x0000 }
121 };
122
123 /*Performs a copy of length repeat_length data starting at dest -
124 * lookback_distance into dest. This copy copies data previously copied when the
125 * src buffer and the dest buffer overlap. */
byte_copy(uint8_t * dest,uint64_t lookback_distance,int repeat_length)126 static void inline byte_copy(uint8_t *dest, uint64_t lookback_distance, int repeat_length)
127 {
128 uint8_t *src = dest - lookback_distance;
129
130 for (; repeat_length > 0; repeat_length--)
131 *dest++ = *src++;
132 }
133
134 static void
update_checksum(struct inflate_state * state,uint8_t * start_in,uint64_t length)135 update_checksum(struct inflate_state *state, uint8_t *start_in, uint64_t length)
136 {
137 switch (state->crc_flag) {
138 case ISAL_GZIP:
139 case ISAL_GZIP_NO_HDR:
140 case ISAL_GZIP_NO_HDR_VER:
141 state->crc = crc32_gzip_refl(state->crc, start_in, length);
142 break;
143 case ISAL_ZLIB:
144 case ISAL_ZLIB_NO_HDR:
145 case ISAL_ZLIB_NO_HDR_VER:
146 state->crc = isal_adler32_bam1(state->crc, start_in, length);
147 break;
148 }
149 }
150
151 static void
finalize_adler32(struct inflate_state * state)152 finalize_adler32(struct inflate_state *state)
153 {
154
155 state->crc = (state->crc & 0xffff0000) | (((state->crc & 0xffff) + 1) % ADLER_MOD);
156 }
157
158 static const uint8_t bitrev_table[] = {
159 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0, 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70,
160 0xf0, 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8, 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8,
161 0x78, 0xf8, 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4, 0x14, 0x94, 0x54, 0xd4, 0x34,
162 0xb4, 0x74, 0xf4, 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec, 0x1c, 0x9c, 0x5c, 0xdc,
163 0x3c, 0xbc, 0x7c, 0xfc, 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2, 0x12, 0x92, 0x52,
164 0xd2, 0x32, 0xb2, 0x72, 0xf2, 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea, 0x1a, 0x9a,
165 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa, 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6, 0x16,
166 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6, 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
167 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe, 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61,
168 0xe1, 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1, 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9,
169 0x69, 0xe9, 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9, 0x05, 0x85, 0x45, 0xc5, 0x25,
170 0xa5, 0x65, 0xe5, 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5, 0x0d, 0x8d, 0x4d, 0xcd,
171 0x2d, 0xad, 0x6d, 0xed, 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd, 0x03, 0x83, 0x43,
172 0xc3, 0x23, 0xa3, 0x63, 0xe3, 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3, 0x0b, 0x8b,
173 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb, 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb, 0x07,
174 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7, 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
175 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef, 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f,
176 0xff,
177
178 };
179
180 /*
181 * Returns integer with first length bits reversed and all higher bits zeroed
182 */
bit_reverse2(uint16_t bits,uint8_t length)183 static uint32_t inline bit_reverse2(uint16_t bits, uint8_t length)
184 {
185 uint32_t bitrev;
186 bitrev = bitrev_table[bits >> 8];
187 bitrev |= bitrev_table[bits & 0xFF] << 8;
188
189 return bitrev >> (16 - length);
190 }
191
192 /* Load data from the in_stream into a buffer to allow for handling unaligned data*/
inflate_in_load(struct inflate_state * state,int min_required)193 static void inline inflate_in_load(struct inflate_state *state, int min_required)
194 {
195 uint64_t temp = 0;
196 uint8_t new_bytes;
197
198 if (state->read_in_length >= 64)
199 return;
200
201 if (state->avail_in >= 8) {
202 /* If there is enough space to load a 64 bits, load the data and use
203 * that to fill read_in */
204 new_bytes = 8 - (state->read_in_length + 7) / 8;
205 temp = load_le_u64(state->next_in);
206
207 state->read_in |= temp << state->read_in_length;
208 state->next_in += new_bytes;
209 state->avail_in -= new_bytes;
210 state->read_in_length += new_bytes * 8;
211
212 } else {
213 /* Else fill the read_in buffer 1 byte at a time */
214 while (state->read_in_length < 57 && state->avail_in > 0) {
215 temp = *state->next_in;
216 state->read_in |= temp << state->read_in_length;
217 state->next_in++;
218 state->avail_in--;
219 state->read_in_length += 8;
220 }
221 }
222 }
223
inflate_in_read_bits_unsafe(struct inflate_state * state,uint8_t bit_count)224 static uint64_t inline inflate_in_read_bits_unsafe(struct inflate_state *state, uint8_t bit_count)
225 {
226 uint64_t ret;
227
228 ret = (state->read_in) & ((1 << bit_count) - 1);
229 state->read_in >>= bit_count;
230 state->read_in_length -= bit_count;
231
232 return ret;
233 }
234
235 /* Returns the next bit_count bits from the in stream and shifts the stream over
236 * by bit-count bits */
inflate_in_read_bits(struct inflate_state * state,uint8_t bit_count)237 static uint64_t inline inflate_in_read_bits(struct inflate_state *state, uint8_t bit_count)
238 {
239 /* Load inflate_in if not enough data is in the read_in buffer */
240 inflate_in_load(state, bit_count);
241 return inflate_in_read_bits_unsafe(state, bit_count);
242 }
243
write_huff_code(struct huff_code * huff_code,uint32_t code,uint32_t length)244 static void inline write_huff_code(struct huff_code *huff_code, uint32_t code, uint32_t length)
245 {
246 huff_code->code_and_length = code | length << 24;
247 }
248
set_codes(struct huff_code * huff_code_table,int table_length,uint16_t * count)249 static int inline set_codes(struct huff_code *huff_code_table, int table_length, uint16_t *count)
250 {
251 uint32_t max, code, length;
252 uint32_t next_code[MAX_HUFF_TREE_DEPTH + 1];
253 int i;
254 struct huff_code *table_end = huff_code_table + table_length;
255
256 /* Setup for calculating huffman codes */
257 next_code[0] = 0;
258 next_code[1] = 0;
259 for (i = 2; i < MAX_HUFF_TREE_DEPTH + 1; i++)
260 next_code[i] = (next_code[i - 1] + count[i - 1]) << 1;
261
262 max = (next_code[MAX_HUFF_TREE_DEPTH] + count[MAX_HUFF_TREE_DEPTH]);
263
264 if (max > (1 << MAX_HUFF_TREE_DEPTH))
265 return ISAL_INVALID_BLOCK;
266
267 /* Calculate code corresponding to a given symbol */
268 for (; huff_code_table < table_end; huff_code_table++) {
269 length = huff_code_table->length;
270 if (length == 0)
271 continue;
272
273 code = bit_reverse2(next_code[length], length);
274
275 write_huff_code(huff_code_table, code, length);
276 next_code[length] += 1;
277 }
278 return 0;
279 }
280
set_and_expand_lit_len_huffcode(struct huff_code * lit_len_huff,uint32_t table_length,uint16_t * count,uint16_t * expand_count,uint32_t * code_list)281 static int inline set_and_expand_lit_len_huffcode(struct huff_code *lit_len_huff,
282 uint32_t table_length, uint16_t *count,
283 uint16_t *expand_count, uint32_t *code_list)
284 {
285 int len_sym, len_size, extra_count, extra;
286 uint32_t count_total, count_tmp;
287 uint32_t code, code_len, expand_len;
288 struct huff_code *expand_next = &lit_len_huff[ISAL_DEF_LIT_SYMBOLS];
289 struct huff_code tmp_table[LIT_LEN - ISAL_DEF_LIT_SYMBOLS];
290 uint32_t max;
291 uint32_t next_code[MAX_HUFF_TREE_DEPTH + 1];
292 int i;
293 struct huff_code *table_end;
294 struct huff_code *huff_code_table = lit_len_huff;
295 uint32_t insert_index;
296
297 /* Setup for calculating huffman codes */
298 count_total = 0;
299 count_tmp = expand_count[1];
300 next_code[0] = 0;
301 next_code[1] = 0;
302 expand_count[0] = 0;
303 expand_count[1] = 0;
304
305 for (i = 1; i < MAX_HUFF_TREE_DEPTH; i++) {
306 count_total = count[i] + count_tmp + count_total;
307 count_tmp = expand_count[i + 1];
308 expand_count[i + 1] = count_total;
309 next_code[i + 1] = (next_code[i] + count[i]) << 1;
310 }
311
312 count_tmp = count[i] + count_tmp;
313
314 for (; i < MAX_LIT_LEN_COUNT - 1; i++) {
315 count_total = count_tmp + count_total;
316 count_tmp = expand_count[i + 1];
317 expand_count[i + 1] = count_total;
318 }
319
320 /* Correct for extra symbols used by static header */
321 if (table_length > LIT_LEN)
322 count[8] -= 2;
323
324 max = (next_code[MAX_HUFF_TREE_DEPTH] + count[MAX_HUFF_TREE_DEPTH]);
325
326 if (max > (1 << MAX_HUFF_TREE_DEPTH))
327 return ISAL_INVALID_BLOCK;
328
329 memcpy(count, expand_count, sizeof(*count) * MAX_LIT_LEN_COUNT);
330
331 memcpy(tmp_table, &lit_len_huff[ISAL_DEF_LIT_SYMBOLS],
332 sizeof(*lit_len_huff) * (LIT_LEN - ISAL_DEF_LIT_SYMBOLS));
333 memset(&lit_len_huff[ISAL_DEF_LIT_SYMBOLS], 0,
334 sizeof(*lit_len_huff) * (LIT_LEN_ELEMS - ISAL_DEF_LIT_SYMBOLS));
335
336 /* Calculate code corresponding to a given literal symbol */
337 table_end = huff_code_table + ISAL_DEF_LIT_SYMBOLS;
338 for (; huff_code_table < table_end; huff_code_table++) {
339 code_len = huff_code_table->length;
340 if (code_len == 0)
341 continue;
342
343 code = bit_reverse2(next_code[code_len], code_len);
344
345 insert_index = expand_count[code_len];
346 code_list[insert_index] = huff_code_table - lit_len_huff;
347 expand_count[code_len]++;
348
349 write_huff_code(huff_code_table, code, code_len);
350 next_code[code_len] += 1;
351 }
352
353 /* Calculate code corresponding to a given len symbol */
354 for (len_sym = 0; len_sym < LIT_LEN - ISAL_DEF_LIT_SYMBOLS; len_sym++) {
355 extra_count = rfc_lookup_table.len_extra_bit_count[len_sym];
356 len_size = (1 << extra_count);
357
358 code_len = tmp_table[len_sym].length;
359 if (code_len == 0) {
360 expand_next += len_size;
361 continue;
362 }
363
364 code = bit_reverse2(next_code[code_len], code_len);
365 expand_len = code_len + extra_count;
366 next_code[code_len] += 1;
367 insert_index = expand_count[expand_len];
368 expand_count[expand_len] += len_size;
369
370 for (extra = 0; extra < len_size; extra++) {
371 code_list[insert_index] = expand_next - lit_len_huff;
372 write_huff_code(expand_next, code | (extra << code_len), expand_len);
373 insert_index++;
374 expand_next++;
375 }
376 }
377
378 return 0;
379 }
380
index_to_sym(int index)381 static int inline index_to_sym(int index) { return (index != 513) ? index : 512; }
382
383 /* Sets result to the inflate_huff_code corresponding to the huffcode defined by
384 * the lengths in huff_code_table,where count is a histogram of the appearance
385 * of each code length */
386 static void
make_inflate_huff_code_lit_len(struct inflate_huff_code_large * result,struct huff_code * huff_code_table,uint32_t table_length,uint16_t * count_total,uint32_t * code_list,uint32_t multisym)387 make_inflate_huff_code_lit_len(struct inflate_huff_code_large *result,
388 struct huff_code *huff_code_table, uint32_t table_length,
389 uint16_t *count_total, uint32_t *code_list, uint32_t multisym)
390 {
391 int i, j;
392 uint16_t code = 0;
393 uint32_t *long_code_list;
394 uint32_t long_code_length = 0;
395 uint16_t temp_code_list[1 << (MAX_LIT_LEN_CODE_LEN - ISAL_DECODE_LONG_BITS)];
396 uint32_t temp_code_length;
397 uint32_t long_code_lookup_length = 0;
398 uint32_t max_length;
399 uint16_t first_bits;
400 uint32_t code_length;
401 uint16_t long_bits;
402 uint16_t min_increment;
403 uint32_t code_list_len;
404 uint32_t last_length, min_length;
405 uint32_t copy_size;
406 uint32_t *short_code_lookup = result->short_code_lookup;
407 int index1, index2, index3;
408 int sym1, sym2, sym3, sym1_index, sym2_index, sym3_index;
409 uint32_t sym1_code, sym2_code, sym3_code, sym1_len, sym2_len, sym3_len;
410
411 uint32_t max_symbol = MAX_LIT_LEN_SYM;
412
413 code_list_len = count_total[MAX_LIT_LEN_COUNT - 1];
414
415 if (code_list_len == 0) {
416 memset(result->short_code_lookup, 0, sizeof(result->short_code_lookup));
417 return;
418 }
419
420 /* Determine the length of the first code */
421 last_length = huff_code_table[code_list[0]].length;
422 if (last_length > ISAL_DECODE_LONG_BITS)
423 last_length = ISAL_DECODE_LONG_BITS + 1;
424 copy_size = (1 << (last_length - 1));
425
426 /* Initialize short_code_lookup, so invalid lookups process data */
427 memset(short_code_lookup, 0x00, copy_size * sizeof(*short_code_lookup));
428
429 min_length = last_length;
430 for (; last_length <= ISAL_DECODE_LONG_BITS; last_length++) {
431 /* Copy forward previously set codes */
432 memcpy(short_code_lookup + copy_size, short_code_lookup,
433 sizeof(*short_code_lookup) * copy_size);
434 copy_size *= 2;
435
436 /* Encode code singletons */
437 for (index1 = count_total[last_length]; index1 < count_total[last_length + 1];
438 index1++) {
439 sym1_index = code_list[index1];
440 sym1 = index_to_sym(sym1_index);
441 sym1_len = huff_code_table[sym1_index].length;
442 sym1_code = huff_code_table[sym1_index].code;
443
444 if (sym1 > max_symbol)
445 continue;
446
447 /* Set new codes */
448 short_code_lookup[sym1_code] = sym1 |
449 sym1_len << LARGE_SHORT_CODE_LEN_OFFSET |
450 (1 << LARGE_SYM_COUNT_OFFSET);
451 }
452
453 /* Continue if no pairs are possible */
454 if (multisym >= SINGLE_SYM_FLAG || last_length < 2 * min_length)
455 continue;
456
457 /* Encode code pairs */
458 for (index1 = count_total[min_length];
459 index1 < count_total[last_length - min_length + 1]; index1++) {
460 sym1_index = code_list[index1];
461 sym1 = index_to_sym(sym1_index);
462 sym1_len = huff_code_table[sym1_index].length;
463 sym1_code = huff_code_table[sym1_index].code;
464
465 /*Check that sym1 is a literal */
466 if (sym1 >= 256) {
467 index1 = count_total[sym1_len + 1] - 1;
468 continue;
469 }
470
471 sym2_len = last_length - sym1_len;
472 for (index2 = count_total[sym2_len]; index2 < count_total[sym2_len + 1];
473 index2++) {
474 sym2_index = code_list[index2];
475 sym2 = index_to_sym(sym2_index);
476
477 /* Check that sym2 is an existing symbol */
478 if (sym2 > max_symbol)
479 break;
480
481 sym2_code = huff_code_table[sym2_index].code;
482 code = sym1_code | (sym2_code << sym1_len);
483 code_length = sym1_len + sym2_len;
484 short_code_lookup[code] =
485 sym1 | (sym2 << 8) |
486 (code_length << LARGE_SHORT_CODE_LEN_OFFSET) |
487 (2 << LARGE_SYM_COUNT_OFFSET);
488 }
489 }
490
491 /* Continue if no triples are possible */
492 if (multisym >= DOUBLE_SYM_FLAG || last_length < 3 * min_length)
493 continue;
494
495 /* Encode code triples */
496 for (index1 = count_total[min_length];
497 index1 < count_total[last_length - 2 * min_length + 1]; index1++) {
498 sym1_index = code_list[index1];
499 sym1 = index_to_sym(sym1_index);
500 sym1_len = huff_code_table[sym1_index].length;
501 sym1_code = huff_code_table[sym1_index].code;
502 /*Check that sym1 is a literal */
503 if (sym1 >= 256) {
504 index1 = count_total[sym1_len + 1] - 1;
505 continue;
506 }
507
508 if (last_length - sym1_len < 2 * min_length)
509 break;
510
511 for (index2 = count_total[min_length];
512 index2 < count_total[last_length - sym1_len - min_length + 1];
513 index2++) {
514 sym2_index = code_list[index2];
515 sym2 = index_to_sym(sym2_index);
516 sym2_len = huff_code_table[sym2_index].length;
517 sym2_code = huff_code_table[sym2_index].code;
518
519 /* Check that sym2 is a literal */
520 if (sym2 >= 256) {
521 index2 = count_total[sym2_len + 1] - 1;
522 continue;
523 }
524
525 sym3_len = last_length - sym1_len - sym2_len;
526 for (index3 = count_total[sym3_len];
527 index3 < count_total[sym3_len + 1]; index3++) {
528 sym3_index = code_list[index3];
529 sym3 = index_to_sym(sym3_index);
530 sym3_code = huff_code_table[sym3_index].code;
531
532 /* Check that sym3 is writable existing symbol */
533 if (sym3 > max_symbol - 1)
534 break;
535
536 code = sym1_code | (sym2_code << sym1_len) |
537 (sym3_code << (sym2_len + sym1_len));
538 code_length = sym1_len + sym2_len + sym3_len;
539 short_code_lookup[code] =
540 sym1 | (sym2 << 8) | sym3 << 16 |
541 (code_length << LARGE_SHORT_CODE_LEN_OFFSET) |
542 (3 << LARGE_SYM_COUNT_OFFSET);
543 }
544 }
545 }
546 }
547
548 index1 = count_total[ISAL_DECODE_LONG_BITS + 1];
549 long_code_length = code_list_len - index1;
550 long_code_list = &code_list[index1];
551 for (i = 0; i < long_code_length; i++) {
552 /*Set the look up table to point to a hint where the symbol can be found
553 * in the list of long codes and add the current symbol to the list of
554 * long codes. */
555 if (huff_code_table[long_code_list[i]].code_and_extra == INVALID_CODE)
556 continue;
557
558 max_length = huff_code_table[long_code_list[i]].length;
559 first_bits = huff_code_table[long_code_list[i]].code_and_extra &
560 ((1 << ISAL_DECODE_LONG_BITS) - 1);
561
562 temp_code_list[0] = long_code_list[i];
563 temp_code_length = 1;
564
565 for (j = i + 1; j < long_code_length; j++) {
566 if ((huff_code_table[long_code_list[j]].code &
567 ((1 << ISAL_DECODE_LONG_BITS) - 1)) == first_bits) {
568 max_length = huff_code_table[long_code_list[j]].length;
569 temp_code_list[temp_code_length] = long_code_list[j];
570 temp_code_length++;
571 }
572 }
573
574 memset(&result->long_code_lookup[long_code_lookup_length], 0x00,
575 sizeof(*result->long_code_lookup) *
576 (1 << (max_length - ISAL_DECODE_LONG_BITS)));
577
578 for (j = 0; j < temp_code_length; j++) {
579 sym1_index = temp_code_list[j];
580 sym1 = index_to_sym(sym1_index);
581 sym1_len = huff_code_table[sym1_index].length;
582 sym1_code = huff_code_table[sym1_index].code_and_extra;
583
584 long_bits = sym1_code >> ISAL_DECODE_LONG_BITS;
585 min_increment = 1 << (sym1_len - ISAL_DECODE_LONG_BITS);
586
587 for (; long_bits < (1 << (max_length - ISAL_DECODE_LONG_BITS));
588 long_bits += min_increment) {
589 result->long_code_lookup[long_code_lookup_length + long_bits] =
590 sym1 | (sym1_len << LARGE_LONG_CODE_LEN_OFFSET);
591 }
592 huff_code_table[sym1_index].code_and_extra = INVALID_CODE;
593 }
594 result->short_code_lookup[first_bits] = long_code_lookup_length |
595 (max_length << LARGE_SHORT_MAX_LEN_OFFSET) |
596 LARGE_FLAG_BIT;
597 long_code_lookup_length += 1 << (max_length - ISAL_DECODE_LONG_BITS);
598 }
599 }
600
make_inflate_huff_code_dist(struct inflate_huff_code_small * result,struct huff_code * huff_code_table,uint32_t table_length,uint16_t * count,uint32_t max_symbol)601 static void inline make_inflate_huff_code_dist(struct inflate_huff_code_small *result,
602 struct huff_code *huff_code_table,
603 uint32_t table_length, uint16_t *count,
604 uint32_t max_symbol)
605 {
606 int i, j, k;
607 uint32_t *long_code_list;
608 uint32_t long_code_length = 0;
609 uint16_t temp_code_list[1 << (15 - ISAL_DECODE_SHORT_BITS)];
610 uint32_t temp_code_length;
611 uint32_t long_code_lookup_length = 0;
612 uint32_t max_length;
613 uint16_t first_bits;
614 uint32_t code_length;
615 uint16_t long_bits;
616 uint16_t min_increment;
617 uint32_t code_list[DIST_LEN + 2]; /* The +2 is for the extra codes in the static header */
618 uint32_t code_list_len;
619 uint32_t count_total[17], count_total_tmp[17];
620 uint32_t insert_index;
621 uint32_t last_length;
622 uint32_t copy_size;
623 uint16_t *short_code_lookup = result->short_code_lookup;
624 uint32_t sym;
625
626 count_total[0] = 0;
627 count_total[1] = 0;
628 for (i = 2; i < 17; i++)
629 count_total[i] = count_total[i - 1] + count[i - 1];
630 memcpy(count_total_tmp, count_total, sizeof(count_total_tmp));
631
632 code_list_len = count_total[16];
633 if (code_list_len == 0) {
634 memset(result->short_code_lookup, 0, sizeof(result->short_code_lookup));
635 return;
636 }
637
638 for (i = 0; i < table_length; i++) {
639 code_length = huff_code_table[i].length;
640 if (code_length == 0)
641 continue;
642
643 insert_index = count_total_tmp[code_length];
644 code_list[insert_index] = i;
645 count_total_tmp[code_length]++;
646 }
647
648 last_length = huff_code_table[code_list[0]].length;
649 if (last_length > ISAL_DECODE_SHORT_BITS)
650 last_length = ISAL_DECODE_SHORT_BITS + 1;
651 copy_size = (1 << (last_length - 1));
652
653 /* Initialize short_code_lookup, so invalid lookups process data */
654 memset(short_code_lookup, 0x00, copy_size * sizeof(*short_code_lookup));
655
656 for (; last_length <= ISAL_DECODE_SHORT_BITS; last_length++) {
657 memcpy(short_code_lookup + copy_size, short_code_lookup,
658 sizeof(*short_code_lookup) * copy_size);
659 copy_size *= 2;
660
661 for (k = count_total[last_length]; k < count_total[last_length + 1]; k++) {
662 i = code_list[k];
663
664 if (i >= max_symbol) {
665 /* If the symbol is invalid, set code to be the
666 * length of the symbol and the code_length to 0
667 * to determine if there was enough input */
668 short_code_lookup[huff_code_table[i].code] =
669 huff_code_table[i].length;
670 continue;
671 }
672
673 /* Set lookup table to return the current symbol concatenated
674 * with the code length when the first DECODE_LENGTH bits of the
675 * address are the same as the code for the current symbol. The
676 * first 9 bits are the code, bits 14:10 are the code length,
677 * bit 15 is a flag representing this is a symbol*/
678 short_code_lookup[huff_code_table[i].code] =
679 i |
680 rfc_lookup_table.dist_extra_bit_count[i] << DIST_SYM_EXTRA_OFFSET |
681 (huff_code_table[i].length) << SMALL_SHORT_CODE_LEN_OFFSET;
682 }
683 }
684
685 k = count_total[ISAL_DECODE_SHORT_BITS + 1];
686 long_code_list = &code_list[k];
687 long_code_length = code_list_len - k;
688 for (i = 0; i < long_code_length; i++) {
689 /*Set the look up table to point to a hint where the symbol can be found
690 * in the list of long codes and add the current symbol to the list of
691 * long codes. */
692 if (huff_code_table[long_code_list[i]].code == 0xFFFF)
693 continue;
694
695 max_length = huff_code_table[long_code_list[i]].length;
696 first_bits = huff_code_table[long_code_list[i]].code &
697 ((1 << ISAL_DECODE_SHORT_BITS) - 1);
698
699 temp_code_list[0] = long_code_list[i];
700 temp_code_length = 1;
701
702 for (j = i + 1; j < long_code_length; j++) {
703 if ((huff_code_table[long_code_list[j]].code &
704 ((1 << ISAL_DECODE_SHORT_BITS) - 1)) == first_bits) {
705 max_length = huff_code_table[long_code_list[j]].length;
706 temp_code_list[temp_code_length] = long_code_list[j];
707 temp_code_length++;
708 }
709 }
710
711 memset(&result->long_code_lookup[long_code_lookup_length], 0x00,
712 2 * (1 << (max_length - ISAL_DECODE_SHORT_BITS)));
713
714 for (j = 0; j < temp_code_length; j++) {
715 sym = temp_code_list[j];
716 code_length = huff_code_table[sym].length;
717 long_bits = huff_code_table[sym].code >> ISAL_DECODE_SHORT_BITS;
718 min_increment = 1 << (code_length - ISAL_DECODE_SHORT_BITS);
719 for (; long_bits < (1 << (max_length - ISAL_DECODE_SHORT_BITS));
720 long_bits += min_increment) {
721 if (sym >= max_symbol) {
722 /* If the symbol is invalid, set code to be the
723 * length of the symbol and the code_length to 0
724 * to determine if there was enough input */
725 result->long_code_lookup[long_code_lookup_length +
726 long_bits] = code_length;
727 continue;
728 }
729 result->long_code_lookup[long_code_lookup_length + long_bits] =
730 sym |
731 rfc_lookup_table.dist_extra_bit_count[sym]
732 << DIST_SYM_EXTRA_OFFSET |
733 (code_length << SMALL_LONG_CODE_LEN_OFFSET);
734 }
735 huff_code_table[sym].code = 0xFFFF;
736 }
737 result->short_code_lookup[first_bits] =
738 long_code_lookup_length | (max_length << SMALL_SHORT_CODE_LEN_OFFSET) |
739 SMALL_FLAG_BIT;
740 long_code_lookup_length += 1 << (max_length - ISAL_DECODE_SHORT_BITS);
741 }
742 }
743
make_inflate_huff_code_header(struct inflate_huff_code_small * result,struct huff_code * huff_code_table,uint32_t table_length,uint16_t * count,uint32_t max_symbol)744 static void inline make_inflate_huff_code_header(struct inflate_huff_code_small *result,
745 struct huff_code *huff_code_table,
746 uint32_t table_length, uint16_t *count,
747 uint32_t max_symbol)
748 {
749 int i, j, k;
750 uint32_t *long_code_list;
751 uint32_t long_code_length = 0;
752 uint16_t temp_code_list[1 << (15 - ISAL_DECODE_SHORT_BITS)];
753 uint32_t temp_code_length;
754 uint32_t long_code_lookup_length = 0;
755 uint32_t max_length;
756 uint16_t first_bits;
757 uint32_t code_length;
758 uint16_t long_bits;
759 uint16_t min_increment;
760 uint32_t code_list[DIST_LEN + 2]; /* The +2 is for the extra codes in the static header */
761 uint32_t code_list_len;
762 uint32_t count_total[17], count_total_tmp[17];
763 uint32_t insert_index;
764 uint32_t last_length;
765 uint32_t copy_size;
766 uint16_t *short_code_lookup = result->short_code_lookup;
767
768 count_total[0] = 0;
769 count_total[1] = 0;
770 for (i = 2; i < 17; i++)
771 count_total[i] = count_total[i - 1] + count[i - 1];
772
773 memcpy(count_total_tmp, count_total, sizeof(count_total_tmp));
774
775 code_list_len = count_total[16];
776 if (code_list_len == 0) {
777 memset(result->short_code_lookup, 0, sizeof(result->short_code_lookup));
778 return;
779 }
780
781 for (i = 0; i < table_length; i++) {
782 code_length = huff_code_table[i].length;
783 if (code_length == 0)
784 continue;
785
786 insert_index = count_total_tmp[code_length];
787 code_list[insert_index] = i;
788 count_total_tmp[code_length]++;
789 }
790
791 last_length = huff_code_table[code_list[0]].length;
792 if (last_length > ISAL_DECODE_SHORT_BITS)
793 last_length = ISAL_DECODE_SHORT_BITS + 1;
794 copy_size = (1 << (last_length - 1));
795
796 /* Initialize short_code_lookup, so invalid lookups process data */
797 memset(short_code_lookup, 0x00, copy_size * sizeof(*short_code_lookup));
798
799 for (; last_length <= ISAL_DECODE_SHORT_BITS; last_length++) {
800 memcpy(short_code_lookup + copy_size, short_code_lookup,
801 sizeof(*short_code_lookup) * copy_size);
802 copy_size *= 2;
803
804 for (k = count_total[last_length]; k < count_total[last_length + 1]; k++) {
805 i = code_list[k];
806
807 if (i >= max_symbol)
808 continue;
809
810 /* Set lookup table to return the current symbol concatenated
811 * with the code length when the first DECODE_LENGTH bits of the
812 * address are the same as the code for the current symbol. The
813 * first 9 bits are the code, bits 14:10 are the code length,
814 * bit 15 is a flag representing this is a symbol*/
815 short_code_lookup[huff_code_table[i].code] =
816 i | (huff_code_table[i].length) << SMALL_SHORT_CODE_LEN_OFFSET;
817 }
818 }
819
820 k = count_total[ISAL_DECODE_SHORT_BITS + 1];
821 long_code_list = &code_list[k];
822 long_code_length = code_list_len - k;
823 for (i = 0; i < long_code_length; i++) {
824 /*Set the look up table to point to a hint where the symbol can be found
825 * in the list of long codes and add the current symbol to the list of
826 * long codes. */
827 if (huff_code_table[long_code_list[i]].code == 0xFFFF)
828 continue;
829
830 max_length = huff_code_table[long_code_list[i]].length;
831 first_bits = huff_code_table[long_code_list[i]].code &
832 ((1 << ISAL_DECODE_SHORT_BITS) - 1);
833
834 temp_code_list[0] = long_code_list[i];
835 temp_code_length = 1;
836
837 for (j = i + 1; j < long_code_length; j++) {
838 if ((huff_code_table[long_code_list[j]].code &
839 ((1 << ISAL_DECODE_SHORT_BITS) - 1)) == first_bits) {
840 if (max_length < huff_code_table[long_code_list[j]].length)
841 max_length = huff_code_table[long_code_list[j]].length;
842 temp_code_list[temp_code_length] = long_code_list[j];
843 temp_code_length++;
844 }
845 }
846
847 memset(&result->long_code_lookup[long_code_lookup_length], 0x00,
848 2 * (1 << (max_length - ISAL_DECODE_SHORT_BITS)));
849
850 for (j = 0; j < temp_code_length; j++) {
851 code_length = huff_code_table[temp_code_list[j]].length;
852 long_bits =
853 huff_code_table[temp_code_list[j]].code >> ISAL_DECODE_SHORT_BITS;
854 min_increment = 1 << (code_length - ISAL_DECODE_SHORT_BITS);
855 for (; long_bits < (1 << (max_length - ISAL_DECODE_SHORT_BITS));
856 long_bits += min_increment) {
857 result->long_code_lookup[long_code_lookup_length + long_bits] =
858 temp_code_list[j] |
859 (code_length << SMALL_LONG_CODE_LEN_OFFSET);
860 }
861 huff_code_table[temp_code_list[j]].code = 0xFFFF;
862 }
863 result->short_code_lookup[first_bits] =
864 long_code_lookup_length | (max_length << SMALL_SHORT_CODE_LEN_OFFSET) |
865 SMALL_FLAG_BIT;
866 long_code_lookup_length += 1 << (max_length - ISAL_DECODE_SHORT_BITS);
867 }
868 }
869
870 static int
header_matches_pregen(struct inflate_state * state)871 header_matches_pregen(struct inflate_state *state)
872 {
873 #ifndef ISAL_STATIC_INFLATE_TABLE
874 return 0;
875 #else
876 uint8_t *in, *hdr;
877 uint32_t in_end_bits, hdr_end_bits;
878 uint32_t bytes_read_in, header_len, last_bits, last_bit_mask;
879 uint64_t bits_read_mask;
880 uint64_t hdr_stash, in_stash;
881 const uint64_t bits_read_prior = 3; // Have read bfinal(1) and btype(2)
882
883 /* Check if stashed read_in_bytes match header */
884 hdr = &(hufftables_default.deflate_hdr[0]);
885 bits_read_mask = (1ull << state->read_in_length) - 1;
886 hdr_stash = (load_le_u64(hdr) >> bits_read_prior) & bits_read_mask;
887 in_stash = state->read_in & bits_read_mask;
888
889 if (hdr_stash != in_stash)
890 return 0;
891
892 /* Check if input is byte aligned */
893 if ((state->read_in_length + bits_read_prior) % 8)
894 return 0;
895
896 /* Check if header bulk is the same */
897 in = state->next_in;
898 bytes_read_in = (state->read_in_length + bits_read_prior) / 8;
899 header_len = hufftables_default.deflate_hdr_count;
900
901 if (memcmp(in, &hdr[bytes_read_in], header_len - bytes_read_in))
902 return 0;
903
904 /* If there are any last/end bits to the header check them too */
905 last_bits = hufftables_default.deflate_hdr_extra_bits;
906 last_bit_mask = (1 << last_bits) - 1;
907
908 if (0 == last_bits) {
909 state->next_in += header_len - bytes_read_in;
910 state->avail_in -= header_len - bytes_read_in;
911 state->read_in_length = 0;
912 state->read_in = 0;
913 return 1;
914 }
915
916 in_end_bits = in[header_len - bytes_read_in] & last_bit_mask;
917 hdr_end_bits = hdr[header_len] & last_bit_mask;
918 if (in_end_bits == hdr_end_bits) {
919 state->next_in += header_len - bytes_read_in;
920 state->avail_in -= header_len - bytes_read_in;
921 state->read_in_length = 0;
922 state->read_in = 0;
923 inflate_in_read_bits(state, last_bits);
924 return 1;
925 }
926
927 return 0;
928 #endif // ISAL_STATIC_INFLATE_TABLE
929 }
930
931 static int
setup_pregen_header(struct inflate_state * state)932 setup_pregen_header(struct inflate_state *state)
933 {
934 #ifdef ISAL_STATIC_INFLATE_TABLE
935 memcpy(&state->lit_huff_code, &pregen_lit_huff_code, sizeof(pregen_lit_huff_code));
936 memcpy(&state->dist_huff_code, &pregen_dist_huff_code, sizeof(pregen_dist_huff_code));
937 state->block_state = ISAL_BLOCK_CODED;
938 #endif // ISAL_STATIC_INFLATE_TABLE
939 return 0;
940 }
941
942 /* Sets the inflate_huff_codes in state to be the huffcodes corresponding to the
943 * deflate static header */
setup_static_header(struct inflate_state * state)944 static int inline setup_static_header(struct inflate_state *state)
945 {
946 #ifdef ISAL_STATIC_INFLATE_TABLE
947 memcpy(&state->lit_huff_code, &static_lit_huff_code, sizeof(static_lit_huff_code));
948 memcpy(&state->dist_huff_code, &static_dist_huff_code, sizeof(static_dist_huff_code));
949 #else
950
951 #ifndef NO_STATIC_INFLATE_H
952 #warning "Defaulting to static inflate table fallback."
953 #warning \
954 "For best performance, run generate_static_inflate, replace static_inflate.h, and recompile"
955 #endif
956 int i;
957 struct huff_code lit_code[LIT_LEN_ELEMS];
958 struct huff_code dist_code[DIST_LEN + 2];
959 uint32_t multisym = SINGLE_SYM_FLAG, max_dist = DIST_LEN;
960 /* These tables are based on the static huffman tree described in RFC
961 * 1951 */
962 uint16_t lit_count[MAX_LIT_LEN_COUNT] = { 0, 0, 0, 0, 0, 0, 0, 24, 152, 112, 0,
963 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
964
965 uint16_t lit_expand_count[MAX_LIT_LEN_COUNT] = { 0, 0, 0, 0, 0, 0, 0, -15, 1, 16, 32,
966 48, 16, 128, 0, 0, 0, 0, 0, 0, 0, 0 };
967 uint16_t dist_count[16] = { 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
968 uint32_t code_list[LIT_LEN_ELEMS +
969 2]; /* The +2 is for the extra codes in the static header */
970 /* These for loops set the code lengths for the static literal/length
971 * and distance codes defined in the deflate standard RFC 1951 */
972 for (i = 0; i < 144; i++)
973 lit_code[i].length = 8;
974
975 for (i = 144; i < 256; i++)
976 lit_code[i].length = 9;
977
978 for (i = 256; i < 280; i++)
979 lit_code[i].length = 7;
980
981 for (i = 280; i < LIT_LEN + 2; i++)
982 lit_code[i].length = 8;
983
984 for (i = 0; i < DIST_LEN + 2; i++)
985 dist_code[i].length = 5;
986
987 set_and_expand_lit_len_huffcode(lit_code, LIT_LEN + 2, lit_count, lit_expand_count,
988 code_list);
989
990 set_codes(dist_code, DIST_LEN + 2, dist_count);
991
992 make_inflate_huff_code_lit_len(&state->lit_huff_code, lit_code, LIT_LEN_ELEMS, lit_count,
993 code_list, multisym);
994
995 if (state->hist_bits && state->hist_bits < 15)
996 max_dist = 2 * state->hist_bits;
997
998 make_inflate_huff_code_dist(&state->dist_huff_code, dist_code, DIST_LEN + 2, dist_count,
999 max_dist);
1000 #endif
1001 state->block_state = ISAL_BLOCK_CODED;
1002
1003 return 0;
1004 }
1005
1006 /* Decodes the next symbol symbol in in_buffer using the huff code defined by
1007 * huff_code and returns the value in next_lits and sym_count */
decode_next_lit_len(uint32_t * next_lits,uint32_t * sym_count,struct inflate_state * state,struct inflate_huff_code_large * huff_code)1008 static void inline decode_next_lit_len(uint32_t *next_lits, uint32_t *sym_count,
1009 struct inflate_state *state,
1010 struct inflate_huff_code_large *huff_code)
1011 {
1012 uint32_t next_bits;
1013 uint32_t next_sym;
1014 uint32_t bit_count;
1015 uint32_t bit_mask;
1016
1017 if (state->read_in_length <= ISAL_DEF_MAX_CODE_LEN)
1018 inflate_in_load(state, 0);
1019
1020 next_bits = state->read_in & ((1 << ISAL_DECODE_LONG_BITS) - 1);
1021
1022 /* next_sym is a possible symbol decoded from next_bits. If bit 15 is 0,
1023 * next_code is a symbol. Bits 9:0 represent the symbol, and bits 14:10
1024 * represent the length of that symbols huffman code. If next_sym is not
1025 * a symbol, it provides a hint of where the large symbols containin
1026 * this code are located. Note the hint is at largest the location the
1027 * first actual symbol in the long code list.*/
1028 next_sym = huff_code->short_code_lookup[next_bits];
1029
1030 if ((next_sym & LARGE_FLAG_BIT) == 0) {
1031 /* Return symbol found if next_code is a complete huffman code
1032 * and shift in buffer over by the length of the next_code */
1033 bit_count = next_sym >> LARGE_SHORT_CODE_LEN_OFFSET;
1034 state->read_in >>= bit_count;
1035 state->read_in_length -= bit_count;
1036
1037 if (bit_count == 0)
1038 next_sym = INVALID_SYMBOL;
1039
1040 *sym_count = (next_sym >> LARGE_SYM_COUNT_OFFSET) & LARGE_SYM_COUNT_MASK;
1041 *next_lits = next_sym & LARGE_SHORT_SYM_MASK;
1042
1043 } else {
1044 /* If a symbol is not found, do a lookup in the long code
1045 * list starting from the hint in next_sym */
1046 bit_mask = next_sym >> LARGE_SHORT_MAX_LEN_OFFSET;
1047 bit_mask = (1 << bit_mask) - 1;
1048 next_bits = state->read_in & bit_mask;
1049 next_sym = huff_code->long_code_lookup[(next_sym & LARGE_SHORT_SYM_MASK) +
1050 (next_bits >> ISAL_DECODE_LONG_BITS)];
1051 bit_count = next_sym >> LARGE_LONG_CODE_LEN_OFFSET;
1052 state->read_in >>= bit_count;
1053 state->read_in_length -= bit_count;
1054
1055 if (bit_count == 0)
1056 next_sym = INVALID_SYMBOL;
1057
1058 *sym_count = 1;
1059 *next_lits = next_sym & LARGE_LONG_SYM_MASK;
1060 }
1061 }
1062
decode_next_dist(struct inflate_state * state,struct inflate_huff_code_small * huff_code)1063 static uint16_t inline decode_next_dist(struct inflate_state *state,
1064 struct inflate_huff_code_small *huff_code)
1065 {
1066 uint16_t next_bits;
1067 uint16_t next_sym;
1068 uint32_t bit_count;
1069 uint32_t bit_mask;
1070
1071 if (state->read_in_length <= ISAL_DEF_MAX_CODE_LEN)
1072 inflate_in_load(state, 0);
1073
1074 next_bits = state->read_in & ((1 << ISAL_DECODE_SHORT_BITS) - 1);
1075
1076 /* next_sym is a possible symbol decoded from next_bits. If bit 15 is 0,
1077 * next_code is a symbol. Bits 9:0 represent the symbol, and bits 14:10
1078 * represent the length of that symbols huffman code. If next_sym is not
1079 * a symbol, it provides a hint of where the large symbols containin
1080 * this code are located. Note the hint is at largest the location the
1081 * first actual symbol in the long code list.*/
1082 next_sym = huff_code->short_code_lookup[next_bits];
1083
1084 if ((next_sym & SMALL_FLAG_BIT) == 0) {
1085 /* Return symbol found if next_code is a complete huffman code
1086 * and shift in buffer over by the length of the next_code */
1087 bit_count = next_sym >> SMALL_SHORT_CODE_LEN_OFFSET;
1088 state->read_in >>= bit_count;
1089 state->read_in_length -= bit_count;
1090
1091 if (bit_count == 0) {
1092 state->read_in_length -= next_sym;
1093 next_sym = INVALID_SYMBOL;
1094 }
1095
1096 return next_sym & DIST_SYM_MASK;
1097
1098 } else {
1099 /* If a symbol is not found, perform a linear search of the long code
1100 * list starting from the hint in next_sym */
1101 bit_mask = (next_sym - SMALL_FLAG_BIT) >> SMALL_SHORT_CODE_LEN_OFFSET;
1102 bit_mask = (1 << bit_mask) - 1;
1103 next_bits = state->read_in & bit_mask;
1104 next_sym = huff_code->long_code_lookup[(next_sym & SMALL_SHORT_SYM_MASK) +
1105 (next_bits >> ISAL_DECODE_SHORT_BITS)];
1106 bit_count = next_sym >> SMALL_LONG_CODE_LEN_OFFSET;
1107 state->read_in >>= bit_count;
1108 state->read_in_length -= bit_count;
1109
1110 if (bit_count == 0) {
1111 state->read_in_length -= next_sym;
1112 next_sym = INVALID_SYMBOL;
1113 }
1114
1115 return next_sym & DIST_SYM_MASK;
1116 }
1117 }
1118
decode_next_header(struct inflate_state * state,struct inflate_huff_code_small * huff_code)1119 static uint16_t inline decode_next_header(struct inflate_state *state,
1120 struct inflate_huff_code_small *huff_code)
1121 {
1122 uint16_t next_bits;
1123 uint16_t next_sym;
1124 uint32_t bit_count;
1125 uint32_t bit_mask;
1126
1127 if (state->read_in_length <= ISAL_DEF_MAX_CODE_LEN)
1128 inflate_in_load(state, 0);
1129
1130 next_bits = state->read_in & ((1 << ISAL_DECODE_SHORT_BITS) - 1);
1131
1132 /* next_sym is a possible symbol decoded from next_bits. If bit 15 is 0,
1133 * next_code is a symbol. Bits 9:0 represent the symbol, and bits 14:10
1134 * represent the length of that symbols huffman code. If next_sym is not
1135 * a symbol, it provides a hint of where the large symbols containing
1136 * this code are located. Note the hint is at largest the location the
1137 * first actual symbol in the long code list.*/
1138 next_sym = huff_code->short_code_lookup[next_bits];
1139
1140 if ((next_sym & SMALL_FLAG_BIT) == 0) {
1141 /* Return symbol found if next_code is a complete huffman code
1142 * and shift in buffer over by the length of the next_code */
1143 bit_count = next_sym >> SMALL_SHORT_CODE_LEN_OFFSET;
1144 state->read_in >>= bit_count;
1145 state->read_in_length -= bit_count;
1146
1147 if (bit_count == 0)
1148 next_sym = INVALID_SYMBOL;
1149
1150 return next_sym & SMALL_SHORT_SYM_MASK;
1151
1152 } else {
1153 /* If a symbol is not found, perform a linear search of the long code
1154 * list starting from the hint in next_sym */
1155 bit_mask = (next_sym - SMALL_FLAG_BIT) >> SMALL_SHORT_CODE_LEN_OFFSET;
1156 bit_mask = (1 << bit_mask) - 1;
1157 next_bits = state->read_in & bit_mask;
1158 next_sym = huff_code->long_code_lookup[(next_sym & SMALL_SHORT_SYM_MASK) +
1159 (next_bits >> ISAL_DECODE_SHORT_BITS)];
1160 bit_count = next_sym >> SMALL_LONG_CODE_LEN_OFFSET;
1161 state->read_in >>= bit_count;
1162 state->read_in_length -= bit_count;
1163 return next_sym & SMALL_LONG_SYM_MASK;
1164 }
1165 }
1166
1167 /* Reads data from the in_buffer and sets the huff code corresponding to that
1168 * data */
setup_dynamic_header(struct inflate_state * state)1169 static int inline setup_dynamic_header(struct inflate_state *state)
1170 {
1171 int i, j;
1172 struct huff_code code_huff[CODE_LEN_CODES];
1173 struct huff_code lit_and_dist_huff[LIT_LEN_ELEMS];
1174 struct huff_code *previous = NULL, *current, *end, rep_code;
1175 struct inflate_huff_code_small inflate_code_huff;
1176 uint64_t hclen, hdist, hlit;
1177 uint16_t code_count[16], lit_count[MAX_LIT_LEN_COUNT], lit_expand_count[MAX_LIT_LEN_COUNT],
1178 dist_count[16];
1179 uint16_t *count;
1180 uint16_t symbol;
1181 uint32_t multisym = DEFAULT_SYM_FLAG, length, max_dist = DIST_LEN;
1182 struct huff_code *code;
1183 uint64_t flag = 0;
1184
1185 int extra_count;
1186 uint32_t code_list[LIT_LEN_ELEMS +
1187 2]; /* The +2 is for the extra codes in the static header */
1188
1189 /* This order is defined in RFC 1951 page 13 */
1190 const uint8_t code_length_order[CODE_LEN_CODES] = { 0x10, 0x11, 0x12, 0x00, 0x08,
1191 0x07, 0x09, 0x06, 0x0a, 0x05,
1192 0x0b, 0x04, 0x0c, 0x03, 0x0d,
1193 0x02, 0x0e, 0x01, 0x0f };
1194
1195 /* If you are given a whole header and it matches the pregen header */
1196 if (state->avail_in > (hufftables_default.deflate_hdr_count + sizeof(uint64_t)) &&
1197 header_matches_pregen(state))
1198 return setup_pregen_header(state);
1199
1200 if (state->bfinal && state->avail_in <= SINGLE_SYM_THRESH) {
1201 multisym = SINGLE_SYM_FLAG;
1202 } else if (state->bfinal && state->avail_in <= DOUBLE_SYM_THRESH) {
1203 multisym = DOUBLE_SYM_FLAG;
1204 }
1205
1206 memset(code_count, 0, sizeof(code_count));
1207 memset(lit_count, 0, sizeof(lit_count));
1208 memset(lit_expand_count, 0, sizeof(lit_expand_count));
1209 memset(dist_count, 0, sizeof(dist_count));
1210 memset(code_huff, 0, sizeof(code_huff));
1211 memset(lit_and_dist_huff, 0, sizeof(lit_and_dist_huff));
1212
1213 /* These variables are defined in the deflate standard, RFC 1951 */
1214 inflate_in_load(state, 0);
1215 if (state->read_in_length < 14)
1216 return ISAL_END_INPUT;
1217
1218 hlit = inflate_in_read_bits_unsafe(state, 5);
1219 hdist = inflate_in_read_bits_unsafe(state, 5);
1220 hclen = inflate_in_read_bits_unsafe(state, 4);
1221
1222 if (hlit > 29 || hdist > 29 || hclen > 15)
1223 return ISAL_INVALID_BLOCK;
1224
1225 /* Create the code huffman code for decoding the lit/len and dist huffman codes */
1226 for (i = 0; i < 4; i++) {
1227 code = &code_huff[code_length_order[i]];
1228 length = inflate_in_read_bits_unsafe(state, 3);
1229 write_huff_code(code, 0, length);
1230 code_count[length] += 1;
1231 flag |= length;
1232 }
1233
1234 inflate_in_load(state, 0);
1235
1236 for (i = 4; i < hclen + 4; i++) {
1237 code = &code_huff[code_length_order[i]];
1238 length = inflate_in_read_bits_unsafe(state, 3);
1239 write_huff_code(code, 0, length);
1240 code_count[length] += 1;
1241 flag |= length;
1242 }
1243
1244 if (state->read_in_length < 0)
1245 return ISAL_END_INPUT;
1246
1247 if (!flag || set_codes(code_huff, CODE_LEN_CODES, code_count))
1248 return ISAL_INVALID_BLOCK;
1249
1250 make_inflate_huff_code_header(&inflate_code_huff, code_huff, CODE_LEN_CODES, code_count,
1251 CODE_LEN_CODES);
1252
1253 /* Decode the lit/len and dist huffman codes using the code huffman code */
1254 count = lit_count;
1255 current = lit_and_dist_huff;
1256 end = lit_and_dist_huff + LIT_LEN + hdist + 1;
1257
1258 while (current < end) {
1259 symbol = decode_next_header(state, &inflate_code_huff);
1260
1261 if (state->read_in_length < 0) {
1262 if (current > &lit_and_dist_huff[256] && lit_and_dist_huff[256].length <= 0)
1263 return ISAL_INVALID_BLOCK;
1264 return ISAL_END_INPUT;
1265 }
1266
1267 if (symbol < 16) {
1268 /* If a length is found, update the current lit/len/dist
1269 * to have length symbol */
1270 if (current == lit_and_dist_huff + LIT_TABLE_SIZE + hlit) {
1271 /* Switch code upon completion of lit_len table */
1272 current = lit_and_dist_huff + LIT_LEN;
1273 count = dist_count;
1274 }
1275 count[symbol]++;
1276 write_huff_code(current, 0, symbol);
1277 previous = current;
1278 current++;
1279
1280 if (symbol == 0 // No symbol
1281 || (previous >= lit_and_dist_huff + LIT_TABLE_SIZE + hlit) // Dist table
1282 || (previous < lit_and_dist_huff + 264)) // Lit/Len with no extra bits
1283 continue;
1284
1285 extra_count =
1286 rfc_lookup_table.len_extra_bit_count[previous - LIT_TABLE_SIZE -
1287 lit_and_dist_huff];
1288 lit_expand_count[symbol]--;
1289 lit_expand_count[symbol + extra_count] += (1 << extra_count);
1290
1291 } else if (symbol == 16) {
1292 /* If a repeat length is found, update the next repeat
1293 * length lit/len/dist elements to have the value of the
1294 * repeated length */
1295
1296 i = 3 + inflate_in_read_bits(state, 2);
1297
1298 if (current + i > end || previous == NULL)
1299 return ISAL_INVALID_BLOCK;
1300
1301 rep_code = *previous;
1302 for (j = 0; j < i; j++) {
1303 if (current == lit_and_dist_huff + LIT_TABLE_SIZE + hlit) {
1304 /* Switch code upon completion of lit_len table */
1305 current = lit_and_dist_huff + LIT_LEN;
1306 count = dist_count;
1307 }
1308
1309 *current = rep_code;
1310 count[rep_code.length]++;
1311 previous = current;
1312 current++;
1313
1314 if (rep_code.length == 0 // No symbol
1315 || (previous >=
1316 lit_and_dist_huff + LIT_TABLE_SIZE + hlit) // Dist table
1317 ||
1318 (previous < lit_and_dist_huff + 264)) // Lit/Len with no extra
1319 continue;
1320
1321 extra_count =
1322 rfc_lookup_table
1323 .len_extra_bit_count[previous - lit_and_dist_huff -
1324 LIT_TABLE_SIZE];
1325 lit_expand_count[rep_code.length]--;
1326 lit_expand_count[rep_code.length + extra_count] +=
1327 (1 << extra_count);
1328 }
1329 } else if (symbol == 17) {
1330 /* If a repeat zeroes if found, update then next
1331 * repeated zeroes length lit/len/dist elements to have
1332 * length 0. */
1333 i = 3 + inflate_in_read_bits(state, 3);
1334
1335 current = current + i;
1336 previous = current - 1;
1337
1338 if (count != dist_count &&
1339 current > lit_and_dist_huff + LIT_TABLE_SIZE + hlit) {
1340 /* Switch code upon completion of lit_len table */
1341 current += LIT_LEN - LIT_TABLE_SIZE - hlit;
1342 count = dist_count;
1343 if (current > lit_and_dist_huff + LIT_LEN)
1344 previous = current - 1;
1345 }
1346
1347 } else if (symbol == 18) {
1348 /* If a repeat zeroes if found, update then next
1349 * repeated zeroes length lit/len/dist elements to have
1350 * length 0. */
1351 i = 11 + inflate_in_read_bits(state, 7);
1352
1353 current = current + i;
1354 previous = current - 1;
1355
1356 if (count != dist_count &&
1357 current > lit_and_dist_huff + LIT_TABLE_SIZE + hlit) {
1358 /* Switch code upon completion of lit_len table */
1359 current += LIT_LEN - LIT_TABLE_SIZE - hlit;
1360 count = dist_count;
1361 if (current > lit_and_dist_huff + LIT_LEN)
1362 previous = current - 1;
1363 }
1364
1365 } else
1366 return ISAL_INVALID_BLOCK;
1367 }
1368
1369 if (current > end || lit_and_dist_huff[256].length <= 0)
1370 return ISAL_INVALID_BLOCK;
1371
1372 if (state->read_in_length < 0)
1373 return ISAL_END_INPUT;
1374
1375 if (set_codes(&lit_and_dist_huff[LIT_LEN], DIST_LEN, dist_count))
1376 return ISAL_INVALID_BLOCK;
1377
1378 if (state->hist_bits && state->hist_bits < 15)
1379 max_dist = 2 * state->hist_bits;
1380
1381 make_inflate_huff_code_dist(&state->dist_huff_code, &lit_and_dist_huff[LIT_LEN], DIST_LEN,
1382 dist_count, max_dist);
1383
1384 if (set_and_expand_lit_len_huffcode(lit_and_dist_huff, LIT_LEN, lit_count, lit_expand_count,
1385 code_list))
1386 return ISAL_INVALID_BLOCK;
1387
1388 make_inflate_huff_code_lit_len(&state->lit_huff_code, lit_and_dist_huff, LIT_LEN_ELEMS,
1389 lit_count, code_list, multisym);
1390
1391 state->block_state = ISAL_BLOCK_CODED;
1392
1393 return 0;
1394 }
1395
1396 /* Reads in the header pointed to by in_stream and sets up state to reflect that
1397 * header information*/
1398 static int
read_header(struct inflate_state * state)1399 read_header(struct inflate_state *state)
1400 {
1401 uint8_t bytes;
1402 uint32_t btype;
1403 uint16_t len, nlen;
1404 int ret = 0;
1405
1406 /* btype and bfinal are defined in RFC 1951, bfinal represents whether
1407 * the current block is the end of block, and btype represents the
1408 * encoding method on the current block. */
1409
1410 state->bfinal = inflate_in_read_bits(state, 1);
1411 btype = inflate_in_read_bits(state, 2);
1412
1413 if (state->read_in_length < 0)
1414 ret = ISAL_END_INPUT;
1415
1416 else if (btype == 0) {
1417 inflate_in_load(state, 40);
1418 bytes = state->read_in_length / 8;
1419
1420 if (bytes < 4)
1421 return ISAL_END_INPUT;
1422
1423 state->read_in >>= state->read_in_length % 8;
1424 state->read_in_length = bytes * 8;
1425
1426 len = state->read_in & 0xFFFF;
1427 state->read_in >>= 16;
1428 nlen = state->read_in & 0xFFFF;
1429 state->read_in >>= 16;
1430 state->read_in_length -= 32;
1431
1432 /* Check if len and nlen match */
1433 if (len != (~nlen & 0xffff))
1434 return ISAL_INVALID_BLOCK;
1435
1436 state->type0_block_len = len;
1437 state->block_state = ISAL_BLOCK_TYPE0;
1438
1439 ret = 0;
1440
1441 } else if (btype == 1)
1442 ret = setup_static_header(state);
1443
1444 else if (btype == 2)
1445 ret = setup_dynamic_header(state);
1446
1447 else
1448 ret = ISAL_INVALID_BLOCK;
1449
1450 return ret;
1451 }
1452
1453 /* Reads in the header pointed to by in_stream and sets up state to reflect that
1454 * header information*/
1455 static int
read_header_stateful(struct inflate_state * state)1456 read_header_stateful(struct inflate_state *state)
1457 {
1458 uint64_t read_in_start = state->read_in;
1459 int32_t read_in_length_start = state->read_in_length;
1460 uint8_t *next_in_start = state->next_in;
1461 uint32_t avail_in_start = state->avail_in;
1462 int block_state_start = state->block_state;
1463 int ret;
1464 int copy_size;
1465 int bytes_read;
1466
1467 if (block_state_start == ISAL_BLOCK_HDR) {
1468 /* Setup so read_header decodes data in tmp_in_buffer */
1469 copy_size = ISAL_DEF_MAX_HDR_SIZE - state->tmp_in_size;
1470 if (copy_size > state->avail_in)
1471 copy_size = state->avail_in;
1472
1473 memcpy(&state->tmp_in_buffer[state->tmp_in_size], state->next_in, copy_size);
1474 state->next_in = state->tmp_in_buffer;
1475 state->avail_in = state->tmp_in_size + copy_size;
1476 }
1477
1478 ret = read_header(state);
1479
1480 if (block_state_start == ISAL_BLOCK_HDR) {
1481 /* Setup so state is restored to a valid state */
1482 bytes_read = state->next_in - state->tmp_in_buffer - state->tmp_in_size;
1483 if (bytes_read < 0)
1484 bytes_read = 0;
1485 state->next_in = next_in_start + bytes_read;
1486 state->avail_in = avail_in_start - bytes_read;
1487 }
1488
1489 if (ret == ISAL_END_INPUT) {
1490 /* Save off data so header can be decoded again with more data */
1491 state->read_in = read_in_start;
1492 state->read_in_length = read_in_length_start;
1493 memcpy(&state->tmp_in_buffer[state->tmp_in_size], next_in_start, avail_in_start);
1494 state->tmp_in_size += avail_in_start;
1495 state->avail_in = 0;
1496 state->next_in = next_in_start + avail_in_start;
1497 state->block_state = ISAL_BLOCK_HDR;
1498 } else
1499 state->tmp_in_size = 0;
1500
1501 return ret;
1502 }
1503
decode_literal_block(struct inflate_state * state)1504 static int inline decode_literal_block(struct inflate_state *state)
1505 {
1506 uint32_t len = state->type0_block_len;
1507 uint32_t bytes = state->read_in_length / 8;
1508 uint64_t read_in;
1509 /* If the block is uncompressed, perform a memcopy while
1510 * updating state data */
1511 state->block_state = state->bfinal ? ISAL_BLOCK_INPUT_DONE : ISAL_BLOCK_NEW_HDR;
1512
1513 if (state->avail_out < len) {
1514 len = state->avail_out;
1515 state->block_state = ISAL_BLOCK_TYPE0;
1516 }
1517
1518 if (state->avail_in + bytes < len) {
1519 len = state->avail_in + bytes;
1520 state->block_state = ISAL_BLOCK_TYPE0;
1521 }
1522 if (state->read_in_length) {
1523 read_in = to_le64(state->read_in);
1524 if (len >= bytes) {
1525 memcpy(state->next_out, &read_in, bytes);
1526
1527 state->next_out += bytes;
1528 state->avail_out -= bytes;
1529 state->total_out += bytes;
1530 state->type0_block_len -= bytes;
1531
1532 state->read_in = 0;
1533 state->read_in_length = 0;
1534 len -= bytes;
1535 bytes = 0;
1536
1537 } else {
1538 memcpy(state->next_out, &read_in, len);
1539
1540 state->next_out += len;
1541 state->avail_out -= len;
1542 state->total_out += len;
1543 state->type0_block_len -= len;
1544
1545 state->read_in >>= 8 * len;
1546 state->read_in_length -= 8 * len;
1547 bytes -= len;
1548 len = 0;
1549 }
1550 }
1551 memcpy(state->next_out, state->next_in, len);
1552
1553 state->next_out += len;
1554 state->avail_out -= len;
1555 state->total_out += len;
1556 state->next_in += len;
1557 state->avail_in -= len;
1558 state->type0_block_len -= len;
1559
1560 if (state->avail_in + bytes == 0 && state->block_state != ISAL_BLOCK_INPUT_DONE)
1561 return ISAL_END_INPUT;
1562
1563 if (state->avail_out == 0 && state->type0_block_len > 0)
1564 return ISAL_OUT_OVERFLOW;
1565
1566 return 0;
1567 }
1568
1569 /* Decodes the next block if it was encoded using a huffman code */
1570 int
decode_huffman_code_block_stateless_base(struct inflate_state * state,uint8_t * start_out)1571 decode_huffman_code_block_stateless_base(struct inflate_state *state, uint8_t *start_out)
1572 {
1573 uint16_t next_lit;
1574 uint8_t next_dist;
1575 uint32_t repeat_length;
1576 uint32_t look_back_dist = 0;
1577 uint64_t read_in_tmp;
1578 int32_t read_in_length_tmp;
1579 uint8_t *next_in_tmp, *next_out_tmp;
1580 uint32_t avail_in_tmp, avail_out_tmp, total_out_tmp;
1581 uint32_t next_lits, sym_count;
1582 struct rfc1951_tables *rfc = &rfc_lookup_table;
1583
1584 state->copy_overflow_length = 0;
1585 state->copy_overflow_distance = 0;
1586
1587 while (state->block_state == ISAL_BLOCK_CODED) {
1588 /* While not at the end of block, decode the next
1589 * symbol */
1590 inflate_in_load(state, 0);
1591
1592 read_in_tmp = state->read_in;
1593 read_in_length_tmp = state->read_in_length;
1594 next_in_tmp = state->next_in;
1595 avail_in_tmp = state->avail_in;
1596 next_out_tmp = state->next_out;
1597 avail_out_tmp = state->avail_out;
1598 total_out_tmp = state->total_out;
1599
1600 decode_next_lit_len(&next_lits, &sym_count, state, &state->lit_huff_code);
1601
1602 if (sym_count == 0)
1603 return ISAL_INVALID_SYMBOL;
1604
1605 if (state->read_in_length < 0) {
1606 state->read_in = read_in_tmp;
1607 state->read_in_length = read_in_length_tmp;
1608 state->next_in = next_in_tmp;
1609 state->avail_in = avail_in_tmp;
1610 return ISAL_END_INPUT;
1611 }
1612
1613 while (sym_count > 0) {
1614 next_lit = next_lits & 0xffff;
1615 if (next_lit < 256 || sym_count > 1) {
1616 /* If the next symbol is a literal,
1617 * write out the symbol and update state
1618 * data accordingly. */
1619 if (state->avail_out < 1) {
1620 state->write_overflow_lits = next_lits;
1621 state->write_overflow_len = sym_count;
1622 next_lits = next_lits >> (8 * (sym_count - 1));
1623 sym_count = 1;
1624
1625 if (next_lits < 256)
1626 return ISAL_OUT_OVERFLOW;
1627 else if (next_lits == 256) {
1628 state->write_overflow_len -= 1;
1629 state->block_state = state->bfinal
1630 ? ISAL_BLOCK_INPUT_DONE
1631 : ISAL_BLOCK_NEW_HDR;
1632 return ISAL_OUT_OVERFLOW;
1633 } else {
1634 state->write_overflow_len -= 1;
1635 continue;
1636 }
1637 }
1638
1639 *state->next_out = next_lit;
1640 state->next_out++;
1641 state->avail_out--;
1642 state->total_out++;
1643
1644 } else if (next_lit == 256) {
1645 /* If the next symbol is the end of
1646 * block, update the state data
1647 * accordingly */
1648 state->block_state =
1649 state->bfinal ? ISAL_BLOCK_INPUT_DONE : ISAL_BLOCK_NEW_HDR;
1650
1651 } else if (next_lit <= MAX_LIT_LEN_SYM) {
1652 /* Else if the next symbol is a repeat
1653 * length, read in the length extra
1654 * bits, the distance code, the distance
1655 * extra bits. Then write out the
1656 * corresponding data and update the
1657 * state data accordingly*/
1658 repeat_length = next_lit - 254;
1659 next_dist = decode_next_dist(state, &state->dist_huff_code);
1660
1661 if (state->read_in_length >= 0) {
1662 if (next_dist >= DIST_LEN)
1663 return ISAL_INVALID_SYMBOL;
1664
1665 look_back_dist =
1666 rfc->dist_start[next_dist] +
1667 inflate_in_read_bits(
1668 state,
1669 rfc->dist_extra_bit_count[next_dist]);
1670 }
1671
1672 if (state->read_in_length < 0) {
1673 state->read_in = read_in_tmp;
1674 state->read_in_length = read_in_length_tmp;
1675 state->next_in = next_in_tmp;
1676 state->avail_in = avail_in_tmp;
1677 state->next_out = next_out_tmp;
1678 state->avail_out = avail_out_tmp;
1679 state->total_out = total_out_tmp;
1680 state->write_overflow_lits = 0;
1681 state->write_overflow_len = 0;
1682 return ISAL_END_INPUT;
1683 }
1684
1685 if (state->next_out - look_back_dist < start_out)
1686 return ISAL_INVALID_LOOKBACK;
1687
1688 if (state->avail_out < repeat_length) {
1689 state->copy_overflow_length =
1690 repeat_length - state->avail_out;
1691 state->copy_overflow_distance = look_back_dist;
1692 repeat_length = state->avail_out;
1693 }
1694
1695 if (look_back_dist > repeat_length)
1696 memcpy(state->next_out, state->next_out - look_back_dist,
1697 repeat_length);
1698 else
1699 byte_copy(state->next_out, look_back_dist, repeat_length);
1700
1701 state->next_out += repeat_length;
1702 state->avail_out -= repeat_length;
1703 state->total_out += repeat_length;
1704
1705 if (state->copy_overflow_length > 0)
1706 return ISAL_OUT_OVERFLOW;
1707 } else
1708 /* Else the read in bits do not
1709 * correspond to any valid symbol */
1710 return ISAL_INVALID_SYMBOL;
1711
1712 next_lits >>= 8;
1713 sym_count--;
1714 }
1715 }
1716 return 0;
1717 }
1718
1719 void
isal_inflate_init(struct inflate_state * state)1720 isal_inflate_init(struct inflate_state *state)
1721 {
1722
1723 state->read_in = 0;
1724 state->read_in_length = 0;
1725 state->next_in = NULL;
1726 state->avail_in = 0;
1727 state->next_out = NULL;
1728 state->avail_out = 0;
1729 state->total_out = 0;
1730 state->dict_length = 0;
1731 state->block_state = ISAL_BLOCK_NEW_HDR;
1732 state->bfinal = 0;
1733 state->crc_flag = 0;
1734 state->crc = 0;
1735 state->hist_bits = 0;
1736 state->type0_block_len = 0;
1737 state->write_overflow_lits = 0;
1738 state->write_overflow_len = 0;
1739 state->copy_overflow_length = 0;
1740 state->copy_overflow_distance = 0;
1741 state->wrapper_flag = 0;
1742 state->tmp_in_size = 0;
1743 state->tmp_out_processed = 0;
1744 state->tmp_out_valid = 0;
1745 }
1746
1747 void
isal_inflate_reset(struct inflate_state * state)1748 isal_inflate_reset(struct inflate_state *state)
1749 {
1750 state->read_in = 0;
1751 state->read_in_length = 0;
1752 state->total_out = 0;
1753 state->dict_length = 0;
1754 state->block_state = ISAL_BLOCK_NEW_HDR;
1755 state->bfinal = 0;
1756 state->crc = 0;
1757 state->type0_block_len = 0;
1758 state->write_overflow_lits = 0;
1759 state->write_overflow_len = 0;
1760 state->copy_overflow_length = 0;
1761 state->copy_overflow_distance = 0;
1762 state->wrapper_flag = 0;
1763 state->tmp_in_size = 0;
1764 state->tmp_out_processed = 0;
1765 state->tmp_out_valid = 0;
1766 }
1767
1768 static inline uint32_t
fixed_size_read(struct inflate_state * state,uint8_t ** read_buf,int read_size)1769 fixed_size_read(struct inflate_state *state, uint8_t **read_buf, int read_size)
1770 {
1771 uint32_t tmp_in_size = state->tmp_in_size;
1772
1773 if (state->avail_in + tmp_in_size < read_size) {
1774 memcpy(state->tmp_in_buffer + tmp_in_size, state->next_in, state->avail_in);
1775 tmp_in_size += state->avail_in;
1776 state->tmp_in_size = tmp_in_size;
1777 state->next_in += state->avail_in;
1778 state->avail_in = 0;
1779
1780 return ISAL_END_INPUT;
1781 }
1782
1783 *read_buf = state->next_in;
1784 if (tmp_in_size) {
1785 memcpy(state->tmp_in_buffer + tmp_in_size, state->next_in, read_size - tmp_in_size);
1786 *read_buf = state->tmp_in_buffer;
1787 state->tmp_in_size = 0;
1788 }
1789
1790 state->next_in += read_size - tmp_in_size;
1791 state->avail_in -= read_size - tmp_in_size;
1792 tmp_in_size = 0;
1793
1794 return 0;
1795 }
1796
1797 static inline uint32_t
buffer_header_copy(struct inflate_state * state,uint32_t in_len,uint8_t * buf,uint32_t buffer_len,uint32_t offset,uint32_t buf_error)1798 buffer_header_copy(struct inflate_state *state, uint32_t in_len, uint8_t *buf, uint32_t buffer_len,
1799 uint32_t offset, uint32_t buf_error)
1800 {
1801 uint32_t len = in_len;
1802 uint32_t buf_len = buffer_len - offset;
1803
1804 if (len > state->avail_in)
1805 len = state->avail_in;
1806
1807 if (buf != NULL && buf_len < len) {
1808 memcpy(&buf[offset], state->next_in, buf_len);
1809 state->next_in += buf_len;
1810 state->avail_in -= buf_len;
1811 state->count = in_len - buf_len;
1812 return buf_error;
1813 } else {
1814 if (buf != NULL)
1815 memcpy(&buf[offset], state->next_in, len);
1816 state->next_in += len;
1817 state->avail_in -= len;
1818 state->count = in_len - len;
1819
1820 if (len == in_len)
1821 return 0;
1822 else
1823 return ISAL_END_INPUT;
1824 }
1825 }
1826
1827 static inline uint32_t
string_header_copy(struct inflate_state * state,char * str_buf,uint32_t str_len,uint32_t offset,uint32_t str_error)1828 string_header_copy(struct inflate_state *state, char *str_buf, uint32_t str_len, uint32_t offset,
1829 uint32_t str_error)
1830 {
1831 uint32_t len, max_len = str_len - offset;
1832
1833 if (max_len > state->avail_in || str_buf == NULL)
1834 max_len = state->avail_in;
1835
1836 len = strnlen((char *) state->next_in, max_len);
1837
1838 if (str_buf != NULL)
1839 memcpy(&str_buf[offset], state->next_in, len);
1840
1841 state->next_in += len;
1842 state->avail_in -= len;
1843 state->count += len;
1844
1845 if (str_buf != NULL && len == (str_len - offset))
1846 return str_error;
1847 else if (state->avail_in <= 0)
1848 return ISAL_END_INPUT;
1849 else {
1850 state->next_in++;
1851 state->avail_in--;
1852 state->count = 0;
1853 if (str_buf != NULL)
1854 str_buf[offset + len] = 0;
1855 }
1856
1857 return 0;
1858 }
1859
1860 static int
check_gzip_checksum(struct inflate_state * state)1861 check_gzip_checksum(struct inflate_state *state)
1862 {
1863 uint64_t trailer, crc, total_out;
1864 uint8_t *next_in;
1865 uint32_t byte_count, offset, tmp_in_size = state->tmp_in_size;
1866 int ret;
1867
1868 if (state->read_in_length >= 8 * GZIP_TRAILER_LEN) {
1869 /* The following is unnecessary as state->read_in_length == 64 */
1870 /* bit_count = state->read_in_length % 8; */
1871 /* state->read_in >>= bit_count; */
1872 /* state->read_in_length -= bit_count; */
1873
1874 trailer = state->read_in;
1875 state->read_in_length = 0;
1876 state->read_in = 0;
1877 } else {
1878 if (state->read_in_length >= 8) {
1879 byte_count = state->read_in_length / 8;
1880 offset = state->read_in_length % 8;
1881
1882 store_le_u64(state->tmp_in_buffer + tmp_in_size, state->read_in >> offset);
1883 state->read_in = 0;
1884 state->read_in_length = 0;
1885
1886 tmp_in_size += byte_count;
1887 state->tmp_in_size = tmp_in_size;
1888 }
1889
1890 ret = fixed_size_read(state, &next_in, GZIP_TRAILER_LEN);
1891 if (ret) {
1892 state->block_state = ISAL_CHECKSUM_CHECK;
1893 return ret;
1894 }
1895
1896 trailer = load_le_u64(next_in);
1897 }
1898
1899 state->block_state = ISAL_BLOCK_FINISH;
1900
1901 crc = state->crc;
1902 total_out = state->total_out;
1903
1904 if (trailer != (crc | (total_out << 32)))
1905 return ISAL_INCORRECT_CHECKSUM;
1906 else
1907 return ISAL_DECOMP_OK;
1908 }
1909
1910 static int
check_zlib_checksum(struct inflate_state * state)1911 check_zlib_checksum(struct inflate_state *state)
1912 {
1913
1914 uint32_t trailer;
1915 uint8_t *next_in;
1916 uint32_t byte_count, offset, tmp_in_size = state->tmp_in_size;
1917 int ret, bit_count;
1918
1919 if (state->read_in_length >= 8 * ZLIB_TRAILER_LEN) {
1920 bit_count = state->read_in_length % 8;
1921 state->read_in >>= bit_count;
1922 state->read_in_length -= bit_count;
1923
1924 trailer = state->read_in;
1925
1926 state->read_in_length -= 8 * ZLIB_TRAILER_LEN;
1927 state->read_in >>= 8 * ZLIB_TRAILER_LEN;
1928 } else {
1929 if (state->read_in_length >= 8) {
1930 byte_count = state->read_in_length / 8;
1931 offset = state->read_in_length % 8;
1932
1933 store_le_u64(state->tmp_in_buffer + tmp_in_size, state->read_in >> offset);
1934 state->read_in = 0;
1935 state->read_in_length = 0;
1936
1937 tmp_in_size += byte_count;
1938 state->tmp_in_size = tmp_in_size;
1939 }
1940
1941 ret = fixed_size_read(state, &next_in, ZLIB_TRAILER_LEN);
1942 if (ret) {
1943 state->block_state = ISAL_CHECKSUM_CHECK;
1944 return ret;
1945 }
1946
1947 trailer = load_le_u32(next_in);
1948 }
1949
1950 state->block_state = ISAL_BLOCK_FINISH;
1951
1952 if (isal_bswap32(trailer) != state->crc)
1953 return ISAL_INCORRECT_CHECKSUM;
1954 else
1955 return ISAL_DECOMP_OK;
1956 }
1957
1958 int
isal_read_gzip_header(struct inflate_state * state,struct isal_gzip_header * gz_hdr)1959 isal_read_gzip_header(struct inflate_state *state, struct isal_gzip_header *gz_hdr)
1960 {
1961 int cm, flags = gz_hdr->flags, id1, id2;
1962 uint16_t xlen = gz_hdr->extra_len;
1963 uint32_t block_state = state->block_state;
1964 uint8_t *start_in = state->next_in, *next_in;
1965 uint32_t tmp_in_size = state->tmp_in_size;
1966 uint32_t count = state->count, offset;
1967 uint32_t hcrc = gz_hdr->hcrc;
1968 int ret = 0;
1969
1970 /* This switch is a jump table into the function so that decoding the
1971 * header can continue where it stopped on the last call */
1972 switch (block_state) {
1973 case ISAL_BLOCK_NEW_HDR:
1974 state->count = 0;
1975 flags = UNDEFINED_FLAG;
1976 if (tmp_in_size == 0)
1977 hcrc = 0;
1978
1979 ret = fixed_size_read(state, &next_in, GZIP_HDR_BASE);
1980 if (ret)
1981 break;
1982
1983 id1 = next_in[0];
1984 id2 = next_in[1];
1985 cm = next_in[2];
1986 flags = next_in[3];
1987 gz_hdr->time = load_le_u32(next_in + 4);
1988 gz_hdr->xflags = *(next_in + 8);
1989 gz_hdr->os = *(next_in + 9);
1990
1991 if (id1 != 0x1f || id2 != 0x8b)
1992 return ISAL_INVALID_WRAPPER;
1993
1994 if (cm != DEFLATE_METHOD)
1995 return ISAL_UNSUPPORTED_METHOD;
1996
1997 gz_hdr->text = 0;
1998 if (flags & TEXT_FLAG)
1999 gz_hdr->text = 1;
2000
2001 gz_hdr->flags = flags;
2002
2003 if (flags & EXTRA_FLAG) {
2004 case ISAL_GZIP_EXTRA_LEN:
2005 ret = fixed_size_read(state, &next_in, GZIP_EXTRA_LEN);
2006 if (ret) {
2007 state->block_state = ISAL_GZIP_EXTRA_LEN;
2008 break;
2009 }
2010
2011 xlen = load_le_u16(next_in);
2012 count = xlen;
2013
2014 gz_hdr->extra_len = xlen;
2015
2016 case ISAL_GZIP_EXTRA:
2017 offset = gz_hdr->extra_len - count;
2018 ret = buffer_header_copy(state, count, gz_hdr->extra, gz_hdr->extra_buf_len,
2019 offset, ISAL_EXTRA_OVERFLOW);
2020
2021 if (ret) {
2022 state->block_state = ISAL_GZIP_EXTRA;
2023 break;
2024 }
2025 } else {
2026 gz_hdr->extra_len = 0;
2027 }
2028
2029 if (flags & NAME_FLAG) {
2030 case ISAL_GZIP_NAME:
2031 offset = state->count;
2032 ret = string_header_copy(state, gz_hdr->name, gz_hdr->name_buf_len, offset,
2033 ISAL_NAME_OVERFLOW);
2034 if (ret) {
2035 state->block_state = ISAL_GZIP_NAME;
2036 break;
2037 }
2038 }
2039
2040 if (flags & COMMENT_FLAG) {
2041 case ISAL_GZIP_COMMENT:
2042 offset = state->count;
2043 ret = string_header_copy(state, gz_hdr->comment, gz_hdr->comment_buf_len,
2044 offset, ISAL_COMMENT_OVERFLOW);
2045 if (ret) {
2046 state->block_state = ISAL_GZIP_COMMENT;
2047 break;
2048 }
2049 }
2050
2051 if (flags & HCRC_FLAG) {
2052 hcrc = crc32_gzip_refl(hcrc, start_in, state->next_in - start_in);
2053 gz_hdr->hcrc = hcrc;
2054
2055 case ISAL_GZIP_HCRC:
2056 ret = fixed_size_read(state, &next_in, GZIP_HCRC_LEN);
2057 if (ret) {
2058 state->block_state = ISAL_GZIP_HCRC;
2059 return ret;
2060 }
2061
2062 if ((hcrc & 0xffff) != load_le_u16(next_in))
2063 return ISAL_INCORRECT_CHECKSUM;
2064 }
2065
2066 state->wrapper_flag = 1;
2067 state->block_state = ISAL_BLOCK_NEW_HDR;
2068 return ISAL_DECOMP_OK;
2069 }
2070
2071 if (flags & HCRC_FLAG)
2072 gz_hdr->hcrc = crc32_gzip_refl(hcrc, start_in, state->next_in - start_in);
2073
2074 return ret;
2075 }
2076
2077 int
isal_read_zlib_header(struct inflate_state * state,struct isal_zlib_header * zlib_hdr)2078 isal_read_zlib_header(struct inflate_state *state, struct isal_zlib_header *zlib_hdr)
2079 {
2080 int cmf, method, flags;
2081 uint32_t block_state = state->block_state;
2082 uint8_t *next_in;
2083 int ret = 0;
2084
2085 switch (block_state) {
2086 case ISAL_BLOCK_NEW_HDR:
2087 zlib_hdr->dict_flag = 0;
2088 ret = fixed_size_read(state, &next_in, ZLIB_HDR_BASE);
2089 if (ret)
2090 break;
2091
2092 cmf = *next_in;
2093 method = cmf & 0xf;
2094 flags = *(next_in + 1);
2095
2096 zlib_hdr->info = cmf >> ZLIB_INFO_OFFSET;
2097 zlib_hdr->dict_flag = (flags & ZLIB_DICT_FLAG) ? 1 : 0;
2098 zlib_hdr->level = flags >> ZLIB_LEVEL_OFFSET;
2099
2100 if (method != DEFLATE_METHOD)
2101 return ISAL_UNSUPPORTED_METHOD;
2102
2103 if ((256 * cmf + flags) % 31 != 0)
2104 return ISAL_INCORRECT_CHECKSUM;
2105
2106 if (zlib_hdr->dict_flag) {
2107 case ISAL_ZLIB_DICT:
2108 ret = fixed_size_read(state, &next_in, ZLIB_DICT_LEN);
2109 if (ret) {
2110 state->block_state = ISAL_ZLIB_DICT;
2111 break;
2112 }
2113
2114 zlib_hdr->dict_id = load_le_u32(next_in);
2115 }
2116
2117 state->wrapper_flag = 1;
2118 state->block_state = ISAL_BLOCK_NEW_HDR;
2119 }
2120
2121 return ret;
2122 }
2123
2124 int
isal_inflate_set_dict(struct inflate_state * state,uint8_t * dict,uint32_t dict_len)2125 isal_inflate_set_dict(struct inflate_state *state, uint8_t *dict, uint32_t dict_len)
2126 {
2127
2128 if (state->block_state != ISAL_BLOCK_NEW_HDR ||
2129 state->tmp_out_processed != state->tmp_out_valid)
2130 return ISAL_INVALID_STATE;
2131
2132 if (dict_len > IGZIP_HIST_SIZE) {
2133 dict = dict + dict_len - IGZIP_HIST_SIZE;
2134 dict_len = IGZIP_HIST_SIZE;
2135 }
2136
2137 memcpy(state->tmp_out_buffer, dict, dict_len);
2138 state->tmp_out_processed = dict_len;
2139 state->tmp_out_valid = dict_len;
2140 state->dict_length = dict_len;
2141
2142 return COMP_OK;
2143 }
2144
2145 int
isal_inflate_stateless(struct inflate_state * state)2146 isal_inflate_stateless(struct inflate_state *state)
2147 {
2148 uint32_t ret = 0;
2149 uint8_t *start_out = state->next_out;
2150
2151 state->read_in = 0;
2152 state->read_in_length = 0;
2153 state->block_state = ISAL_BLOCK_NEW_HDR;
2154 state->dict_length = 0;
2155 state->bfinal = 0;
2156 state->crc = 0;
2157 state->total_out = 0;
2158 state->hist_bits = 0;
2159 state->tmp_in_size = 0;
2160
2161 if (state->crc_flag == IGZIP_GZIP) {
2162 struct isal_gzip_header gz_hdr;
2163
2164 isal_gzip_header_init(&gz_hdr);
2165 ret = isal_read_gzip_header(state, &gz_hdr);
2166 if (ret)
2167 return ret;
2168 } else if (state->crc_flag == IGZIP_ZLIB) {
2169 struct isal_zlib_header z_hdr;
2170
2171 isal_zlib_header_init(&z_hdr);
2172 ret = isal_read_zlib_header(state, &z_hdr);
2173 if (ret)
2174 return ret;
2175 if (z_hdr.dict_flag)
2176 return ISAL_NEED_DICT;
2177 }
2178
2179 while (state->block_state != ISAL_BLOCK_FINISH) {
2180 if (state->block_state == ISAL_BLOCK_NEW_HDR) {
2181 ret = read_header(state);
2182
2183 if (ret)
2184 break;
2185 }
2186
2187 if (state->block_state == ISAL_BLOCK_TYPE0)
2188 ret = decode_literal_block(state);
2189 else
2190 ret = decode_huffman_code_block_stateless(state, start_out);
2191
2192 if (ret)
2193 break;
2194 if (state->block_state == ISAL_BLOCK_INPUT_DONE)
2195 state->block_state = ISAL_BLOCK_FINISH;
2196 }
2197
2198 /* Undo count stuff of bytes read into the read buffer */
2199 state->next_in -= state->read_in_length / 8;
2200 state->avail_in += state->read_in_length / 8;
2201 state->read_in_length = 0;
2202 state->read_in = 0;
2203
2204 if (!ret && state->crc_flag) {
2205 update_checksum(state, start_out, state->next_out - start_out);
2206 switch (state->crc_flag) {
2207 case ISAL_ZLIB:
2208 case ISAL_ZLIB_NO_HDR_VER:
2209 finalize_adler32(state);
2210 ret = check_zlib_checksum(state);
2211 break;
2212
2213 case ISAL_ZLIB_NO_HDR:
2214 finalize_adler32(state);
2215 break;
2216
2217 case ISAL_GZIP:
2218 case ISAL_GZIP_NO_HDR_VER:
2219 ret = check_gzip_checksum(state);
2220 break;
2221 }
2222 }
2223
2224 return ret;
2225 }
2226
2227 int
isal_inflate(struct inflate_state * state)2228 isal_inflate(struct inflate_state *state)
2229 {
2230
2231 uint8_t *start_out = state->next_out;
2232 uint32_t avail_out = state->avail_out;
2233 uint32_t copy_size = 0;
2234 int32_t shift_size = 0;
2235 int ret = 0;
2236
2237 if (!state->wrapper_flag && state->crc_flag == IGZIP_GZIP) {
2238 struct isal_gzip_header gz_hdr;
2239
2240 isal_gzip_header_init(&gz_hdr);
2241 ret = isal_read_gzip_header(state, &gz_hdr);
2242 if (ret < 0)
2243 return ret;
2244 else if (ret > 0)
2245 return ISAL_DECOMP_OK;
2246 } else if (!state->wrapper_flag && state->crc_flag == IGZIP_ZLIB) {
2247 struct isal_zlib_header z_hdr;
2248
2249 isal_zlib_header_init(&z_hdr);
2250 ret = isal_read_zlib_header(state, &z_hdr);
2251 if (ret < 0)
2252 return ret;
2253 else if (ret > 0)
2254 return ISAL_DECOMP_OK;
2255
2256 if (z_hdr.dict_flag) {
2257 state->dict_id = z_hdr.dict_id;
2258 return ISAL_NEED_DICT;
2259 }
2260 } else if (state->block_state == ISAL_CHECKSUM_CHECK) {
2261 switch (state->crc_flag) {
2262 case ISAL_ZLIB:
2263 case ISAL_ZLIB_NO_HDR_VER:
2264 ret = check_zlib_checksum(state);
2265 break;
2266 case ISAL_GZIP:
2267 case ISAL_GZIP_NO_HDR_VER:
2268 ret = check_gzip_checksum(state);
2269 break;
2270 }
2271
2272 return (ret > 0) ? ISAL_DECOMP_OK : ret;
2273 }
2274
2275 if (state->block_state != ISAL_BLOCK_FINISH) {
2276 state->total_out += state->tmp_out_valid - state->tmp_out_processed;
2277 /* If space in tmp_out buffer, decompress into the tmp_out_buffer */
2278 if (state->tmp_out_valid < 2 * ISAL_DEF_HIST_SIZE) {
2279 /* Setup to start decoding into temp buffer */
2280 state->next_out = &state->tmp_out_buffer[state->tmp_out_valid];
2281 state->avail_out = sizeof(state->tmp_out_buffer) - ISAL_LOOK_AHEAD -
2282 state->tmp_out_valid;
2283
2284 if ((int32_t) state->avail_out < 0)
2285 state->avail_out = 0;
2286
2287 /* Decode into internal buffer until exit */
2288 while (state->block_state != ISAL_BLOCK_INPUT_DONE) {
2289 if (state->block_state == ISAL_BLOCK_NEW_HDR ||
2290 state->block_state == ISAL_BLOCK_HDR) {
2291 ret = read_header_stateful(state);
2292
2293 if (ret)
2294 break;
2295 }
2296
2297 if (state->block_state == ISAL_BLOCK_TYPE0) {
2298 ret = decode_literal_block(state);
2299 } else {
2300 uint8_t *tmp = state->tmp_out_buffer;
2301 ret = decode_huffman_code_block_stateless(state, tmp);
2302 }
2303
2304 if (ret)
2305 break;
2306 }
2307
2308 /* Copy valid data from internal buffer into out_buffer */
2309 if (state->write_overflow_len != 0) {
2310 store_le_u32(state->next_out, state->write_overflow_lits);
2311 state->next_out += state->write_overflow_len;
2312 state->total_out += state->write_overflow_len;
2313 state->write_overflow_lits = 0;
2314 state->write_overflow_len = 0;
2315 }
2316
2317 if (state->copy_overflow_length != 0) {
2318 byte_copy(state->next_out, state->copy_overflow_distance,
2319 state->copy_overflow_length);
2320 state->tmp_out_valid += state->copy_overflow_length;
2321 state->next_out += state->copy_overflow_length;
2322 state->total_out += state->copy_overflow_length;
2323 state->copy_overflow_distance = 0;
2324 state->copy_overflow_length = 0;
2325 }
2326
2327 state->tmp_out_valid = state->next_out - state->tmp_out_buffer;
2328
2329 /* Setup state for decompressing into out_buffer */
2330 state->next_out = start_out;
2331 state->avail_out = avail_out;
2332 }
2333
2334 /* Copy data from tmp_out buffer into out_buffer */
2335 copy_size = state->tmp_out_valid - state->tmp_out_processed;
2336 if (copy_size > avail_out)
2337 copy_size = avail_out;
2338
2339 memcpy(state->next_out, &state->tmp_out_buffer[state->tmp_out_processed],
2340 copy_size);
2341
2342 state->tmp_out_processed += copy_size;
2343 state->avail_out -= copy_size;
2344 state->next_out += copy_size;
2345
2346 if (ret == ISAL_INVALID_LOOKBACK || ret == ISAL_INVALID_BLOCK ||
2347 ret == ISAL_INVALID_SYMBOL) {
2348 /* Set total_out to not count data in tmp_out_buffer */
2349 state->total_out -= state->tmp_out_valid - state->tmp_out_processed;
2350 if (state->crc_flag)
2351 update_checksum(state, start_out, state->next_out - start_out);
2352 return ret;
2353 }
2354
2355 /* If all data from tmp_out buffer has been processed, start
2356 * decompressing into the out buffer */
2357 if (state->tmp_out_processed == state->tmp_out_valid) {
2358 while (state->block_state != ISAL_BLOCK_INPUT_DONE) {
2359 if (state->block_state == ISAL_BLOCK_NEW_HDR ||
2360 state->block_state == ISAL_BLOCK_HDR) {
2361 ret = read_header_stateful(state);
2362 if (ret)
2363 break;
2364 }
2365
2366 if (state->block_state == ISAL_BLOCK_TYPE0)
2367 ret = decode_literal_block(state);
2368 else
2369 ret = decode_huffman_code_block_stateless(state, start_out);
2370 if (ret)
2371 break;
2372 }
2373 }
2374
2375 if (state->crc_flag)
2376 update_checksum(state, start_out, state->next_out - start_out);
2377
2378 if (state->block_state != ISAL_BLOCK_INPUT_DONE ||
2379 state->copy_overflow_length + state->write_overflow_len + state->tmp_out_valid >
2380 sizeof(state->tmp_out_buffer)) {
2381 /* Save decompression history in tmp_out buffer */
2382 if (state->tmp_out_valid == state->tmp_out_processed &&
2383 avail_out - state->avail_out >= ISAL_DEF_HIST_SIZE) {
2384 memcpy(state->tmp_out_buffer, state->next_out - ISAL_DEF_HIST_SIZE,
2385 ISAL_DEF_HIST_SIZE);
2386 state->tmp_out_valid = ISAL_DEF_HIST_SIZE;
2387 state->tmp_out_processed = ISAL_DEF_HIST_SIZE;
2388
2389 } else if (state->tmp_out_processed >= ISAL_DEF_HIST_SIZE) {
2390 shift_size = state->tmp_out_valid - ISAL_DEF_HIST_SIZE;
2391 if (shift_size > state->tmp_out_processed)
2392 shift_size = state->tmp_out_processed;
2393
2394 memmove(state->tmp_out_buffer, &state->tmp_out_buffer[shift_size],
2395 state->tmp_out_valid - shift_size);
2396 state->tmp_out_valid -= shift_size;
2397 state->tmp_out_processed -= shift_size;
2398 }
2399 }
2400
2401 /* Write overflow data into tmp buffer */
2402 if (state->write_overflow_len != 0) {
2403 store_le_u32(&state->tmp_out_buffer[state->tmp_out_valid],
2404 state->write_overflow_lits);
2405 state->tmp_out_valid += state->write_overflow_len;
2406 state->total_out += state->write_overflow_len;
2407 state->write_overflow_lits = 0;
2408 state->write_overflow_len = 0;
2409 }
2410
2411 if (state->copy_overflow_length != 0) {
2412 byte_copy(&state->tmp_out_buffer[state->tmp_out_valid],
2413 state->copy_overflow_distance, state->copy_overflow_length);
2414 state->tmp_out_valid += state->copy_overflow_length;
2415 state->total_out += state->copy_overflow_length;
2416 state->copy_overflow_distance = 0;
2417 state->copy_overflow_length = 0;
2418 }
2419
2420 if (ret == ISAL_INVALID_LOOKBACK || ret == ISAL_INVALID_BLOCK ||
2421 ret == ISAL_INVALID_SYMBOL) {
2422 state->total_out -= state->tmp_out_valid - state->tmp_out_processed;
2423 return ret;
2424 }
2425
2426 if (state->block_state == ISAL_BLOCK_INPUT_DONE &&
2427 state->tmp_out_valid == state->tmp_out_processed) {
2428 state->block_state = ISAL_BLOCK_FINISH;
2429
2430 switch (state->crc_flag) {
2431 case ISAL_ZLIB:
2432 case ISAL_ZLIB_NO_HDR_VER:
2433 finalize_adler32(state);
2434 ret = check_zlib_checksum(state);
2435 break;
2436
2437 case ISAL_ZLIB_NO_HDR:
2438 finalize_adler32(state);
2439 break;
2440
2441 case ISAL_GZIP:
2442 case ISAL_GZIP_NO_HDR_VER:
2443 ret = check_gzip_checksum(state);
2444 break;
2445 }
2446 }
2447
2448 state->total_out -= state->tmp_out_valid - state->tmp_out_processed;
2449 }
2450
2451 return (ret > 0) ? ISAL_DECOMP_OK : ret;
2452 }
2453