1 /**********************************************************************
2 Copyright(c) 2011-2016 Intel Corporation All rights reserved.
4 Redistribution and use in source and binary forms, with or without
5 modification, are permitted provided that the following conditions
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
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.
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 **********************************************************************/
31 #include "igzip_lib.h"
33 #include "huff_codes.h"
34 #include "igzip_checksums.h"
35 #include "igzip_wrapper.h"
36 #include "unaligned.h"
38 #ifndef NO_STATIC_INFLATE_H
39 #include "static_inflate.h"
43 #include <sys/types.h>
44 #include <sys/endian.h>
45 # define bswap_32(x) bswap32(x)
46 #elif defined (__APPLE__)
47 #include <libkern/OSByteOrder.h>
48 # define bswap_32(x) OSSwapInt32(x)
49 #elif defined (__GNUC__) && !defined (__MINGW32__)
50 # include <byteswap.h>
52 # define bswap_32(x) _byteswap_ulong(x)
55 extern int decode_huffman_code_block_stateless(struct inflate_state
*, uint8_t * start_out
);
57 #define LARGE_SHORT_SYM_LEN 25
58 #define LARGE_SHORT_SYM_MASK ((1 << LARGE_SHORT_SYM_LEN) - 1)
59 #define LARGE_LONG_SYM_LEN 10
60 #define LARGE_LONG_SYM_MASK ((1 << LARGE_LONG_SYM_LEN) - 1)
61 #define LARGE_SHORT_CODE_LEN_OFFSET 28
62 #define LARGE_LONG_CODE_LEN_OFFSET 10
63 #define LARGE_FLAG_BIT_OFFSET 25
64 #define LARGE_FLAG_BIT (1 << LARGE_FLAG_BIT_OFFSET)
65 #define LARGE_SYM_COUNT_OFFSET 26
66 #define LARGE_SYM_COUNT_LEN 2
67 #define LARGE_SYM_COUNT_MASK ((1 << LARGE_SYM_COUNT_LEN) - 1)
68 #define LARGE_SHORT_MAX_LEN_OFFSET 26
70 #define SMALL_SHORT_SYM_LEN 9
71 #define SMALL_SHORT_SYM_MASK ((1 << SMALL_SHORT_SYM_LEN) - 1)
72 #define SMALL_LONG_SYM_LEN 9
73 #define SMALL_LONG_SYM_MASK ((1 << SMALL_LONG_SYM_LEN) - 1)
74 #define SMALL_SHORT_CODE_LEN_OFFSET 11
75 #define SMALL_LONG_CODE_LEN_OFFSET 10
76 #define SMALL_FLAG_BIT_OFFSET 10
77 #define SMALL_FLAG_BIT (1 << SMALL_FLAG_BIT_OFFSET)
79 #define DIST_SYM_OFFSET 0
80 #define DIST_SYM_LEN 5
81 #define DIST_SYM_MASK ((1 << DIST_SYM_LEN) - 1)
82 #define DIST_SYM_EXTRA_OFFSET 5
83 #define DIST_SYM_EXTRA_LEN 4
84 #define DIST_SYM_EXTRA_MASK ((1 << DIST_SYM_EXTRA_LEN) - 1)
86 #define MAX_LIT_LEN_CODE_LEN 21
87 #define MAX_LIT_LEN_COUNT (MAX_LIT_LEN_CODE_LEN + 2)
88 #define MAX_LIT_LEN_SYM 512
89 #define LIT_LEN_ELEMS 514
91 #define INVALID_SYMBOL 0x1FFF
92 #define INVALID_CODE 0xFFFFFF
94 #define MIN_DEF_MATCH 3
96 #define TRIPLE_SYM_FLAG 0
97 #define DOUBLE_SYM_FLAG TRIPLE_SYM_FLAG + 1
98 #define SINGLE_SYM_FLAG DOUBLE_SYM_FLAG + 1
99 #define DEFAULT_SYM_FLAG TRIPLE_SYM_FLAG
101 #define SINGLE_SYM_THRESH (2 * 1024)
102 #define DOUBLE_SYM_THRESH (4 * 1024)
104 /* structure contain lookup data based on RFC 1951 */
105 struct rfc1951_tables
{
106 uint8_t dist_extra_bit_count
[32];
107 uint32_t dist_start
[32];
108 uint8_t len_extra_bit_count
[32];
109 uint16_t len_start
[32];
113 /* The following tables are based on the tables in the deflate standard,
114 * RFC 1951 page 11. */
115 static struct rfc1951_tables rfc_lookup_table
= {
116 .dist_extra_bit_count
= {
117 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x02, 0x02,
118 0x03, 0x03, 0x04, 0x04, 0x05, 0x05, 0x06, 0x06,
119 0x07, 0x07, 0x08, 0x08, 0x09, 0x09, 0x0a, 0x0a,
120 0x0b, 0x0b, 0x0c, 0x0c, 0x0d, 0x0d, 0x00, 0x00},
123 0x0001, 0x0002, 0x0003, 0x0004, 0x0005, 0x0007, 0x0009, 0x000d,
124 0x0011, 0x0019, 0x0021, 0x0031, 0x0041, 0x0061, 0x0081, 0x00c1,
125 0x0101, 0x0181, 0x0201, 0x0301, 0x0401, 0x0601, 0x0801, 0x0c01,
126 0x1001, 0x1801, 0x2001, 0x3001, 0x4001, 0x6001, 0x0000, 0x0000},
128 .len_extra_bit_count
= {
129 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
130 0x01, 0x01, 0x01, 0x01, 0x02, 0x02, 0x02, 0x02,
131 0x03, 0x03, 0x03, 0x03, 0x04, 0x04, 0x04, 0x04,
132 0x05, 0x05, 0x05, 0x05, 0x00, 0x00, 0x00, 0x00},
135 0x0003, 0x0004, 0x0005, 0x0006, 0x0007, 0x0008, 0x0009, 0x000a,
136 0x000b, 0x000d, 0x000f, 0x0011, 0x0013, 0x0017, 0x001b, 0x001f,
137 0x0023, 0x002b, 0x0033, 0x003b, 0x0043, 0x0053, 0x0063, 0x0073,
138 0x0083, 0x00a3, 0x00c3, 0x00e3, 0x0102, 0x0103, 0x0000, 0x0000}
148 struct slver isal_inflate_init_slver_00010088
;
149 struct slver isal_inflate_init_slver
= { 0x0088, 0x01, 0x00 };
151 struct slver isal_inflate_reset_slver_0001008f
;
152 struct slver isal_inflate_reset_slver
= { 0x008f, 0x01, 0x00 };
154 struct slver isal_inflate_stateless_slver_00010089
;
155 struct slver isal_inflate_stateless_slver
= { 0x0089, 0x01, 0x00 };
157 struct slver isal_inflate_slver_0001008a
;
158 struct slver isal_inflate_slver
= { 0x008a, 0x01, 0x00 };
160 struct slver isal_inflate_set_dict_slver_0001008d
;
161 struct slver isal_inflate_set_dict_slver
= { 0x008d, 0x01, 0x00 };
163 /*Performs a copy of length repeat_length data starting at dest -
164 * lookback_distance into dest. This copy copies data previously copied when the
165 * src buffer and the dest buffer overlap. */
166 static void inline byte_copy(uint8_t * dest
, uint64_t lookback_distance
, int repeat_length
)
168 uint8_t *src
= dest
- lookback_distance
;
170 for (; repeat_length
> 0; repeat_length
--)
174 static void update_checksum(struct inflate_state
*state
, uint8_t * start_in
, uint64_t length
)
176 switch (state
->crc_flag
) {
178 case ISAL_GZIP_NO_HDR
:
179 case ISAL_GZIP_NO_HDR_VER
:
180 state
->crc
= crc32_gzip_refl(state
->crc
, start_in
, length
);
183 case ISAL_ZLIB_NO_HDR
:
184 case ISAL_ZLIB_NO_HDR_VER
:
185 state
->crc
= isal_adler32_bam1(state
->crc
, start_in
, length
);
190 static void finalize_adler32(struct inflate_state
*state
)
193 state
->crc
= (state
->crc
& 0xffff0000) | (((state
->crc
& 0xffff) + 1) % ADLER_MOD
);
196 static const uint8_t bitrev_table
[] = {
197 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
198 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
199 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
200 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
201 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
202 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
203 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
204 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
205 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
206 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
207 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
208 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
209 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
210 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
211 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
212 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
213 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
214 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
215 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
216 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
217 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
218 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
219 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
220 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
221 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
222 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
223 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
224 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
225 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
226 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
227 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
228 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff,
233 * Returns integer with first length bits reversed and all higher bits zeroed
235 static uint32_t inline bit_reverse2(uint16_t bits
, uint8_t length
)
238 bitrev
= bitrev_table
[bits
>> 8];
239 bitrev
|= bitrev_table
[bits
& 0xFF] << 8;
241 return bitrev
>> (16 - length
);
244 /* Load data from the in_stream into a buffer to allow for handling unaligned data*/
245 static void inline inflate_in_load(struct inflate_state
*state
, int min_required
)
250 if (state
->read_in_length
>= 64)
253 if (state
->avail_in
>= 8) {
254 /* If there is enough space to load a 64 bits, load the data and use
255 * that to fill read_in */
256 new_bytes
= 8 - (state
->read_in_length
+ 7) / 8;
257 temp
= load_u64(state
->next_in
);
259 state
->read_in
|= temp
<< state
->read_in_length
;
260 state
->next_in
+= new_bytes
;
261 state
->avail_in
-= new_bytes
;
262 state
->read_in_length
+= new_bytes
* 8;
265 /* Else fill the read_in buffer 1 byte at a time */
266 while (state
->read_in_length
< 57 && state
->avail_in
> 0) {
267 temp
= *state
->next_in
;
268 state
->read_in
|= temp
<< state
->read_in_length
;
271 state
->read_in_length
+= 8;
277 static uint64_t inline inflate_in_read_bits_unsafe(struct inflate_state
*state
,
282 ret
= (state
->read_in
) & ((1 << bit_count
) - 1);
283 state
->read_in
>>= bit_count
;
284 state
->read_in_length
-= bit_count
;
289 /* Returns the next bit_count bits from the in stream and shifts the stream over
290 * by bit-count bits */
291 static uint64_t inline inflate_in_read_bits(struct inflate_state
*state
, uint8_t bit_count
)
293 /* Load inflate_in if not enough data is in the read_in buffer */
294 inflate_in_load(state
, bit_count
);
295 return inflate_in_read_bits_unsafe(state
, bit_count
);
298 static void inline write_huff_code(struct huff_code
*huff_code
, uint32_t code
, uint32_t length
)
300 huff_code
->code_and_length
= code
| length
<< 24;
303 static int inline set_codes(struct huff_code
*huff_code_table
, int table_length
,
306 uint32_t max
, code
, length
;
307 uint32_t next_code
[MAX_HUFF_TREE_DEPTH
+ 1];
309 struct huff_code
*table_end
= huff_code_table
+ table_length
;
311 /* Setup for calculating huffman codes */
314 for (i
= 2; i
< MAX_HUFF_TREE_DEPTH
+ 1; i
++)
315 next_code
[i
] = (next_code
[i
- 1] + count
[i
- 1]) << 1;
317 max
= (next_code
[MAX_HUFF_TREE_DEPTH
] + count
[MAX_HUFF_TREE_DEPTH
]);
319 if (max
> (1 << MAX_HUFF_TREE_DEPTH
))
320 return ISAL_INVALID_BLOCK
;
322 /* Calculate code corresponding to a given symbol */
323 for (; huff_code_table
< table_end
; huff_code_table
++) {
324 length
= huff_code_table
->length
;
328 code
= bit_reverse2(next_code
[length
], length
);
330 write_huff_code(huff_code_table
, code
, length
);
331 next_code
[length
] += 1;
336 static int inline set_and_expand_lit_len_huffcode(struct huff_code
*lit_len_huff
,
337 uint32_t table_length
,
339 uint16_t * expand_count
,
340 uint32_t * code_list
)
342 int len_sym
, len_size
, extra_count
, extra
;
343 uint32_t count_total
, count_tmp
;
344 uint32_t code
, code_len
, expand_len
;
345 struct huff_code
*expand_next
= &lit_len_huff
[ISAL_DEF_LIT_SYMBOLS
];
346 struct huff_code tmp_table
[LIT_LEN
- ISAL_DEF_LIT_SYMBOLS
];
348 uint32_t next_code
[MAX_HUFF_TREE_DEPTH
+ 1];
350 struct huff_code
*table_end
;
351 struct huff_code
*huff_code_table
= lit_len_huff
;
352 uint32_t insert_index
;
354 /* Setup for calculating huffman codes */
356 count_tmp
= expand_count
[1];
362 for (i
= 1; i
< MAX_HUFF_TREE_DEPTH
; i
++) {
363 count_total
= count
[i
] + count_tmp
+ count_total
;
364 count_tmp
= expand_count
[i
+ 1];
365 expand_count
[i
+ 1] = count_total
;
366 next_code
[i
+ 1] = (next_code
[i
] + count
[i
]) << 1;
369 count_tmp
= count
[i
] + count_tmp
;
371 for (; i
< MAX_LIT_LEN_COUNT
- 1; i
++) {
372 count_total
= count_tmp
+ count_total
;
373 count_tmp
= expand_count
[i
+ 1];
374 expand_count
[i
+ 1] = count_total
;
377 /* Correct for extra symbols used by static header */
378 if (table_length
> LIT_LEN
)
381 max
= (next_code
[MAX_HUFF_TREE_DEPTH
] + count
[MAX_HUFF_TREE_DEPTH
]);
383 if (max
> (1 << MAX_HUFF_TREE_DEPTH
))
384 return ISAL_INVALID_BLOCK
;
386 memcpy(count
, expand_count
, sizeof(*count
) * MAX_LIT_LEN_COUNT
);
388 memcpy(tmp_table
, &lit_len_huff
[ISAL_DEF_LIT_SYMBOLS
],
389 sizeof(*lit_len_huff
) * (LIT_LEN
- ISAL_DEF_LIT_SYMBOLS
));
390 memset(&lit_len_huff
[ISAL_DEF_LIT_SYMBOLS
], 0,
391 sizeof(*lit_len_huff
) * (LIT_LEN_ELEMS
- ISAL_DEF_LIT_SYMBOLS
));
393 /* Calculate code corresponding to a given literal symbol */
394 table_end
= huff_code_table
+ ISAL_DEF_LIT_SYMBOLS
;
395 for (; huff_code_table
< table_end
; huff_code_table
++) {
396 code_len
= huff_code_table
->length
;
400 code
= bit_reverse2(next_code
[code_len
], code_len
);
402 insert_index
= expand_count
[code_len
];
403 code_list
[insert_index
] = huff_code_table
- lit_len_huff
;
404 expand_count
[code_len
]++;
406 write_huff_code(huff_code_table
, code
, code_len
);
407 next_code
[code_len
] += 1;
410 /* Calculate code corresponding to a given len symbol */
411 for (len_sym
= 0; len_sym
< LIT_LEN
- ISAL_DEF_LIT_SYMBOLS
; len_sym
++) {
412 extra_count
= rfc_lookup_table
.len_extra_bit_count
[len_sym
];
413 len_size
= (1 << extra_count
);
415 code_len
= tmp_table
[len_sym
].length
;
417 expand_next
+= len_size
;
421 code
= bit_reverse2(next_code
[code_len
], code_len
);
422 expand_len
= code_len
+ extra_count
;
423 next_code
[code_len
] += 1;
424 insert_index
= expand_count
[expand_len
];
425 expand_count
[expand_len
] += len_size
;
427 for (extra
= 0; extra
< len_size
; extra
++) {
428 code_list
[insert_index
] = expand_next
- lit_len_huff
;
429 write_huff_code(expand_next
, code
| (extra
<< code_len
), expand_len
);
438 static int inline index_to_sym(int index
)
440 return (index
!= 513) ? index
: 512;
443 /* Sets result to the inflate_huff_code corresponding to the huffcode defined by
444 * the lengths in huff_code_table,where count is a histogram of the appearance
445 * of each code length */
446 static void make_inflate_huff_code_lit_len(struct inflate_huff_code_large
*result
,
447 struct huff_code
*huff_code_table
,
448 uint32_t table_length
, uint16_t * count_total
,
449 uint32_t * code_list
, uint32_t multisym
)
453 uint32_t *long_code_list
;
454 uint32_t long_code_length
= 0;
455 uint16_t temp_code_list
[1 << (MAX_LIT_LEN_CODE_LEN
- ISAL_DECODE_LONG_BITS
)];
456 uint32_t temp_code_length
;
457 uint32_t long_code_lookup_length
= 0;
460 uint32_t code_length
;
462 uint16_t min_increment
;
463 uint32_t code_list_len
;
464 uint32_t last_length
, min_length
;
466 uint32_t *short_code_lookup
= result
->short_code_lookup
;
467 int index1
, index2
, index3
;
468 int sym1
, sym2
, sym3
, sym1_index
, sym2_index
, sym3_index
;
469 uint32_t sym1_code
, sym2_code
, sym3_code
, sym1_len
, sym2_len
, sym3_len
;
471 uint32_t max_symbol
= MAX_LIT_LEN_SYM
;
473 code_list_len
= count_total
[MAX_LIT_LEN_COUNT
- 1];
475 if (code_list_len
== 0) {
476 memset(result
->short_code_lookup
, 0, sizeof(result
->short_code_lookup
));
480 /* Determine the length of the first code */
481 last_length
= huff_code_table
[code_list
[0]].length
;
482 if (last_length
> ISAL_DECODE_LONG_BITS
)
483 last_length
= ISAL_DECODE_LONG_BITS
+ 1;
484 copy_size
= (1 << (last_length
- 1));
486 /* Initialize short_code_lookup, so invalid lookups process data */
487 memset(short_code_lookup
, 0x00, copy_size
* sizeof(*short_code_lookup
));
489 min_length
= last_length
;
490 for (; last_length
<= ISAL_DECODE_LONG_BITS
; last_length
++) {
491 /* Copy forward previosly set codes */
492 memcpy(short_code_lookup
+ copy_size
, short_code_lookup
,
493 sizeof(*short_code_lookup
) * copy_size
);
496 /* Encode code singletons */
497 for (index1
= count_total
[last_length
];
498 index1
< count_total
[last_length
+ 1]; index1
++) {
499 sym1_index
= code_list
[index1
];
500 sym1
= index_to_sym(sym1_index
);
501 sym1_len
= huff_code_table
[sym1_index
].length
;
502 sym1_code
= huff_code_table
[sym1_index
].code
;
504 if (sym1
> max_symbol
)
508 short_code_lookup
[sym1_code
] =
509 sym1
| sym1_len
<< LARGE_SHORT_CODE_LEN_OFFSET
|
510 (1 << LARGE_SYM_COUNT_OFFSET
);
513 /* Continue if no pairs are possible */
514 if (multisym
>= SINGLE_SYM_FLAG
|| last_length
< 2 * min_length
)
517 /* Encode code pairs */
518 for (index1
= count_total
[min_length
];
519 index1
< count_total
[last_length
- min_length
+ 1]; index1
++) {
520 sym1_index
= code_list
[index1
];
521 sym1
= index_to_sym(sym1_index
);
522 sym1_len
= huff_code_table
[sym1_index
].length
;
523 sym1_code
= huff_code_table
[sym1_index
].code
;
525 /*Check that sym1 is a literal */
527 index1
= count_total
[sym1_len
+ 1] - 1;
531 sym2_len
= last_length
- sym1_len
;
532 for (index2
= count_total
[sym2_len
];
533 index2
< count_total
[sym2_len
+ 1]; index2
++) {
534 sym2_index
= code_list
[index2
];
535 sym2
= index_to_sym(sym2_index
);
537 /* Check that sym2 is an existing symbol */
538 if (sym2
> max_symbol
)
541 sym2_code
= huff_code_table
[sym2_index
].code
;
542 code
= sym1_code
| (sym2_code
<< sym1_len
);
543 code_length
= sym1_len
+ sym2_len
;
544 short_code_lookup
[code
] =
546 (code_length
<< LARGE_SHORT_CODE_LEN_OFFSET
)
547 | (2 << LARGE_SYM_COUNT_OFFSET
);
551 /* Continue if no triples are possible */
552 if (multisym
>= DOUBLE_SYM_FLAG
|| last_length
< 3 * min_length
)
555 /* Encode code triples */
556 for (index1
= count_total
[min_length
];
557 index1
< count_total
[last_length
- 2 * min_length
+ 1]; index1
++) {
558 sym1_index
= code_list
[index1
];
559 sym1
= index_to_sym(sym1_index
);
560 sym1_len
= huff_code_table
[sym1_index
].length
;
561 sym1_code
= huff_code_table
[sym1_index
].code
;
562 /*Check that sym1 is a literal */
564 index1
= count_total
[sym1_len
+ 1] - 1;
568 if (last_length
- sym1_len
< 2 * min_length
)
571 for (index2
= count_total
[min_length
];
572 index2
< count_total
[last_length
- sym1_len
- min_length
+ 1];
574 sym2_index
= code_list
[index2
];
575 sym2
= index_to_sym(sym2_index
);
576 sym2_len
= huff_code_table
[sym2_index
].length
;
577 sym2_code
= huff_code_table
[sym2_index
].code
;
579 /* Check that sym2 is a literal */
581 index2
= count_total
[sym2_len
+ 1] - 1;
585 sym3_len
= last_length
- sym1_len
- sym2_len
;
586 for (index3
= count_total
[sym3_len
];
587 index3
< count_total
[sym3_len
+ 1]; index3
++) {
588 sym3_index
= code_list
[index3
];
589 sym3
= index_to_sym(sym3_index
);
590 sym3_code
= huff_code_table
[sym3_index
].code
;
592 /* Check that sym3 is writable existing symbol */
593 if (sym3
> max_symbol
- 1)
596 code
= sym1_code
| (sym2_code
<< sym1_len
) |
597 (sym3_code
<< (sym2_len
+ sym1_len
));
598 code_length
= sym1_len
+ sym2_len
+ sym3_len
;
599 short_code_lookup
[code
] =
600 sym1
| (sym2
<< 8) | sym3
<< 16 |
601 (code_length
<< LARGE_SHORT_CODE_LEN_OFFSET
)
602 | (3 << LARGE_SYM_COUNT_OFFSET
);
611 index1
= count_total
[ISAL_DECODE_LONG_BITS
+ 1];
612 long_code_length
= code_list_len
- index1
;
613 long_code_list
= &code_list
[index1
];
614 for (i
= 0; i
< long_code_length
; i
++) {
615 /*Set the look up table to point to a hint where the symbol can be found
616 * in the list of long codes and add the current symbol to the list of
618 if (huff_code_table
[long_code_list
[i
]].code_and_extra
== INVALID_CODE
)
621 max_length
= huff_code_table
[long_code_list
[i
]].length
;
623 huff_code_table
[long_code_list
[i
]].code_and_extra
624 & ((1 << ISAL_DECODE_LONG_BITS
) - 1);
626 temp_code_list
[0] = long_code_list
[i
];
627 temp_code_length
= 1;
629 for (j
= i
+ 1; j
< long_code_length
; j
++) {
630 if ((huff_code_table
[long_code_list
[j
]].code
&
631 ((1 << ISAL_DECODE_LONG_BITS
) - 1)) == first_bits
) {
632 max_length
= huff_code_table
[long_code_list
[j
]].length
;
633 temp_code_list
[temp_code_length
] = long_code_list
[j
];
638 memset(&result
->long_code_lookup
[long_code_lookup_length
], 0x00,
639 sizeof(*result
->long_code_lookup
) *
640 (1 << (max_length
- ISAL_DECODE_LONG_BITS
)));
642 for (j
= 0; j
< temp_code_length
; j
++) {
643 sym1_index
= temp_code_list
[j
];
644 sym1
= index_to_sym(sym1_index
);
645 sym1_len
= huff_code_table
[sym1_index
].length
;
646 sym1_code
= huff_code_table
[sym1_index
].code_and_extra
;
648 long_bits
= sym1_code
>> ISAL_DECODE_LONG_BITS
;
649 min_increment
= 1 << (sym1_len
- ISAL_DECODE_LONG_BITS
);
651 for (; long_bits
< (1 << (max_length
- ISAL_DECODE_LONG_BITS
));
652 long_bits
+= min_increment
) {
653 result
->long_code_lookup
[long_code_lookup_length
+ long_bits
] =
654 sym1
| (sym1_len
<< LARGE_LONG_CODE_LEN_OFFSET
);
656 huff_code_table
[sym1_index
].code_and_extra
= INVALID_CODE
;
659 result
->short_code_lookup
[first_bits
] = long_code_lookup_length
|
660 (max_length
<< LARGE_SHORT_MAX_LEN_OFFSET
) | LARGE_FLAG_BIT
;
661 long_code_lookup_length
+= 1 << (max_length
- ISAL_DECODE_LONG_BITS
);
665 static void inline make_inflate_huff_code_dist(struct inflate_huff_code_small
*result
,
666 struct huff_code
*huff_code_table
,
667 uint32_t table_length
, uint16_t * count
,
671 uint32_t *long_code_list
;
672 uint32_t long_code_length
= 0;
673 uint16_t temp_code_list
[1 << (15 - ISAL_DECODE_SHORT_BITS
)];
674 uint32_t temp_code_length
;
675 uint32_t long_code_lookup_length
= 0;
678 uint32_t code_length
;
680 uint16_t min_increment
;
681 uint32_t code_list
[DIST_LEN
+ 2]; /* The +2 is for the extra codes in the static header */
682 uint32_t code_list_len
;
683 uint32_t count_total
[17], count_total_tmp
[17];
684 uint32_t insert_index
;
685 uint32_t last_length
;
687 uint16_t *short_code_lookup
= result
->short_code_lookup
;
692 for (i
= 2; i
< 17; i
++)
693 count_total
[i
] = count_total
[i
- 1] + count
[i
- 1];
694 memcpy(count_total_tmp
, count_total
, sizeof(count_total_tmp
));
696 code_list_len
= count_total
[16];
697 if (code_list_len
== 0) {
698 memset(result
->short_code_lookup
, 0, sizeof(result
->short_code_lookup
));
702 for (i
= 0; i
< table_length
; i
++) {
703 code_length
= huff_code_table
[i
].length
;
704 if (code_length
== 0)
707 insert_index
= count_total_tmp
[code_length
];
708 code_list
[insert_index
] = i
;
709 count_total_tmp
[code_length
]++;
712 last_length
= huff_code_table
[code_list
[0]].length
;
713 if (last_length
> ISAL_DECODE_SHORT_BITS
)
714 last_length
= ISAL_DECODE_SHORT_BITS
+ 1;
715 copy_size
= (1 << (last_length
- 1));
717 /* Initialize short_code_lookup, so invalid lookups process data */
718 memset(short_code_lookup
, 0x00, copy_size
* sizeof(*short_code_lookup
));
720 for (; last_length
<= ISAL_DECODE_SHORT_BITS
; last_length
++) {
721 memcpy(short_code_lookup
+ copy_size
, short_code_lookup
,
722 sizeof(*short_code_lookup
) * copy_size
);
725 for (k
= count_total
[last_length
]; k
< count_total
[last_length
+ 1]; k
++) {
728 if (i
>= max_symbol
) {
729 /* If the symbol is invalid, set code to be the
730 * length of the symbol and the code_length to 0
731 * to determine if there was enough input */
732 short_code_lookup
[huff_code_table
[i
].code
] =
733 huff_code_table
[i
].length
;
737 /* Set lookup table to return the current symbol concatenated
738 * with the code length when the first DECODE_LENGTH bits of the
739 * address are the same as the code for the current symbol. The
740 * first 9 bits are the code, bits 14:10 are the code length,
741 * bit 15 is a flag representing this is a symbol*/
742 short_code_lookup
[huff_code_table
[i
].code
] = i
|
743 rfc_lookup_table
.dist_extra_bit_count
[i
] << DIST_SYM_EXTRA_OFFSET
|
744 (huff_code_table
[i
].length
) << SMALL_SHORT_CODE_LEN_OFFSET
;
748 k
= count_total
[ISAL_DECODE_SHORT_BITS
+ 1];
749 long_code_list
= &code_list
[k
];
750 long_code_length
= code_list_len
- k
;
751 for (i
= 0; i
< long_code_length
; i
++) {
752 /*Set the look up table to point to a hint where the symbol can be found
753 * in the list of long codes and add the current symbol to the list of
755 if (huff_code_table
[long_code_list
[i
]].code
== 0xFFFF)
758 max_length
= huff_code_table
[long_code_list
[i
]].length
;
760 huff_code_table
[long_code_list
[i
]].code
761 & ((1 << ISAL_DECODE_SHORT_BITS
) - 1);
763 temp_code_list
[0] = long_code_list
[i
];
764 temp_code_length
= 1;
766 for (j
= i
+ 1; j
< long_code_length
; j
++) {
767 if ((huff_code_table
[long_code_list
[j
]].code
&
768 ((1 << ISAL_DECODE_SHORT_BITS
) - 1)) == first_bits
) {
769 max_length
= huff_code_table
[long_code_list
[j
]].length
;
770 temp_code_list
[temp_code_length
] = long_code_list
[j
];
775 memset(&result
->long_code_lookup
[long_code_lookup_length
], 0x00,
776 2 * (1 << (max_length
- ISAL_DECODE_SHORT_BITS
)));
778 for (j
= 0; j
< temp_code_length
; j
++) {
779 sym
= temp_code_list
[j
];
780 code_length
= huff_code_table
[sym
].length
;
781 long_bits
= huff_code_table
[sym
].code
>> ISAL_DECODE_SHORT_BITS
;
782 min_increment
= 1 << (code_length
- ISAL_DECODE_SHORT_BITS
);
783 for (; long_bits
< (1 << (max_length
- ISAL_DECODE_SHORT_BITS
));
784 long_bits
+= min_increment
) {
785 if (sym
>= max_symbol
) {
786 /* If the symbol is invalid, set code to be the
787 * length of the symbol and the code_length to 0
788 * to determine if there was enough input */
789 result
->long_code_lookup
[long_code_lookup_length
+
790 long_bits
] = code_length
;
793 result
->long_code_lookup
[long_code_lookup_length
+ long_bits
] =
795 rfc_lookup_table
.dist_extra_bit_count
[sym
] <<
796 DIST_SYM_EXTRA_OFFSET
|
797 (code_length
<< SMALL_LONG_CODE_LEN_OFFSET
);
799 huff_code_table
[sym
].code
= 0xFFFF;
801 result
->short_code_lookup
[first_bits
] = long_code_lookup_length
|
802 (max_length
<< SMALL_SHORT_CODE_LEN_OFFSET
) | SMALL_FLAG_BIT
;
803 long_code_lookup_length
+= 1 << (max_length
- ISAL_DECODE_SHORT_BITS
);
808 static void inline make_inflate_huff_code_header(struct inflate_huff_code_small
*result
,
809 struct huff_code
*huff_code_table
,
810 uint32_t table_length
, uint16_t * count
,
814 uint32_t *long_code_list
;
815 uint32_t long_code_length
= 0;
816 uint16_t temp_code_list
[1 << (15 - ISAL_DECODE_SHORT_BITS
)];
817 uint32_t temp_code_length
;
818 uint32_t long_code_lookup_length
= 0;
821 uint32_t code_length
;
823 uint16_t min_increment
;
824 uint32_t code_list
[DIST_LEN
+ 2]; /* The +2 is for the extra codes in the static header */
825 uint32_t code_list_len
;
826 uint32_t count_total
[17], count_total_tmp
[17];
827 uint32_t insert_index
;
828 uint32_t last_length
;
830 uint16_t *short_code_lookup
= result
->short_code_lookup
;
834 for (i
= 2; i
< 17; i
++)
835 count_total
[i
] = count_total
[i
- 1] + count
[i
- 1];
837 memcpy(count_total_tmp
, count_total
, sizeof(count_total_tmp
));
839 code_list_len
= count_total
[16];
840 if (code_list_len
== 0) {
841 memset(result
->short_code_lookup
, 0, sizeof(result
->short_code_lookup
));
845 for (i
= 0; i
< table_length
; i
++) {
846 code_length
= huff_code_table
[i
].length
;
847 if (code_length
== 0)
850 insert_index
= count_total_tmp
[code_length
];
851 code_list
[insert_index
] = i
;
852 count_total_tmp
[code_length
]++;
855 last_length
= huff_code_table
[code_list
[0]].length
;
856 if (last_length
> ISAL_DECODE_SHORT_BITS
)
857 last_length
= ISAL_DECODE_SHORT_BITS
+ 1;
858 copy_size
= (1 << (last_length
- 1));
860 /* Initialize short_code_lookup, so invalid lookups process data */
861 memset(short_code_lookup
, 0x00, copy_size
* sizeof(*short_code_lookup
));
863 for (; last_length
<= ISAL_DECODE_SHORT_BITS
; last_length
++) {
864 memcpy(short_code_lookup
+ copy_size
, short_code_lookup
,
865 sizeof(*short_code_lookup
) * copy_size
);
868 for (k
= count_total
[last_length
]; k
< count_total
[last_length
+ 1]; k
++) {
874 /* Set lookup table to return the current symbol concatenated
875 * with the code length when the first DECODE_LENGTH bits of the
876 * address are the same as the code for the current symbol. The
877 * first 9 bits are the code, bits 14:10 are the code length,
878 * bit 15 is a flag representing this is a symbol*/
879 short_code_lookup
[huff_code_table
[i
].code
] =
880 i
| (huff_code_table
[i
].length
) << SMALL_SHORT_CODE_LEN_OFFSET
;
884 k
= count_total
[ISAL_DECODE_SHORT_BITS
+ 1];
885 long_code_list
= &code_list
[k
];
886 long_code_length
= code_list_len
- k
;
887 for (i
= 0; i
< long_code_length
; i
++) {
888 /*Set the look up table to point to a hint where the symbol can be found
889 * in the list of long codes and add the current symbol to the list of
891 if (huff_code_table
[long_code_list
[i
]].code
== 0xFFFF)
894 max_length
= huff_code_table
[long_code_list
[i
]].length
;
896 huff_code_table
[long_code_list
[i
]].code
897 & ((1 << ISAL_DECODE_SHORT_BITS
) - 1);
899 temp_code_list
[0] = long_code_list
[i
];
900 temp_code_length
= 1;
902 for (j
= i
+ 1; j
< long_code_length
; j
++) {
903 if ((huff_code_table
[long_code_list
[j
]].code
&
904 ((1 << ISAL_DECODE_SHORT_BITS
) - 1)) == first_bits
) {
905 if (max_length
< huff_code_table
[long_code_list
[j
]].length
)
906 max_length
= huff_code_table
[long_code_list
[j
]].length
;
907 temp_code_list
[temp_code_length
] = long_code_list
[j
];
912 memset(&result
->long_code_lookup
[long_code_lookup_length
], 0x00,
913 2 * (1 << (max_length
- ISAL_DECODE_SHORT_BITS
)));
915 for (j
= 0; j
< temp_code_length
; j
++) {
916 code_length
= huff_code_table
[temp_code_list
[j
]].length
;
918 huff_code_table
[temp_code_list
[j
]].code
>> ISAL_DECODE_SHORT_BITS
;
919 min_increment
= 1 << (code_length
- ISAL_DECODE_SHORT_BITS
);
920 for (; long_bits
< (1 << (max_length
- ISAL_DECODE_SHORT_BITS
));
921 long_bits
+= min_increment
) {
922 result
->long_code_lookup
[long_code_lookup_length
+ long_bits
] =
924 (code_length
<< SMALL_LONG_CODE_LEN_OFFSET
);
926 huff_code_table
[temp_code_list
[j
]].code
= 0xFFFF;
928 result
->short_code_lookup
[first_bits
] = long_code_lookup_length
|
929 (max_length
<< SMALL_SHORT_CODE_LEN_OFFSET
) | SMALL_FLAG_BIT
;
930 long_code_lookup_length
+= 1 << (max_length
- ISAL_DECODE_SHORT_BITS
);
935 /* Sets the inflate_huff_codes in state to be the huffcodes corresponding to the
936 * deflate static header */
937 static int inline setup_static_header(struct inflate_state
*state
)
939 #ifdef ISAL_STATIC_INFLATE_TABLE
940 memcpy(&state
->lit_huff_code
, &static_lit_huff_code
, sizeof(static_lit_huff_code
));
941 memcpy(&state
->dist_huff_code
, &static_dist_huff_code
, sizeof(static_dist_huff_code
));
944 #ifndef NO_STATIC_INFLATE_H
945 # warning "Defaulting to static inflate table fallback."
946 # warning "For best performance, run generate_static_inflate, replace static_inflate.h, and recompile"
949 struct huff_code lit_code
[LIT_LEN_ELEMS
];
950 struct huff_code dist_code
[DIST_LEN
+ 2];
951 uint32_t multisym
= SINGLE_SYM_FLAG
, max_dist
= DIST_LEN
;
952 /* These tables are based on the static huffman tree described in RFC
954 uint16_t lit_count
[MAX_LIT_LEN_COUNT
] = {
955 0, 0, 0, 0, 0, 0, 0, 24, 152, 112, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
958 uint16_t lit_expand_count
[MAX_LIT_LEN_COUNT
] = {
959 0, 0, 0, 0, 0, 0, 0, -15, 1, 16, 32, 48, 16, 128, 0, 0, 0, 0, 0, 0, 0, 0
961 uint16_t dist_count
[16] = {
962 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
964 uint32_t code_list
[LIT_LEN_ELEMS
+ 2]; /* The +2 is for the extra codes in the static header */
965 /* These for loops set the code lengths for the static literal/length
966 * and distance codes defined in the deflate standard RFC 1951 */
967 for (i
= 0; i
< 144; i
++)
968 lit_code
[i
].length
= 8;
970 for (i
= 144; i
< 256; i
++)
971 lit_code
[i
].length
= 9;
973 for (i
= 256; i
< 280; i
++)
974 lit_code
[i
].length
= 7;
976 for (i
= 280; i
< LIT_LEN
+ 2; i
++)
977 lit_code
[i
].length
= 8;
979 for (i
= 0; i
< DIST_LEN
+ 2; i
++)
980 dist_code
[i
].length
= 5;
982 set_and_expand_lit_len_huffcode(lit_code
, LIT_LEN
+ 2, lit_count
, lit_expand_count
,
985 set_codes(dist_code
, DIST_LEN
+ 2, dist_count
);
987 make_inflate_huff_code_lit_len(&state
->lit_huff_code
, lit_code
, LIT_LEN_ELEMS
,
988 lit_count
, code_list
, multisym
);
990 if (state
->hist_bits
&& state
->hist_bits
< 15)
991 max_dist
= 2 * state
->hist_bits
;
993 make_inflate_huff_code_dist(&state
->dist_huff_code
, dist_code
, DIST_LEN
+ 2,
994 dist_count
, max_dist
);
996 state
->block_state
= ISAL_BLOCK_CODED
;
1001 /* Decodes the next symbol symbol in in_buffer using the huff code defined by
1002 * huff_code and returns the value in next_lits and sym_count */
1003 static void inline decode_next_lit_len(uint32_t * next_lits
, uint32_t * sym_count
,
1004 struct inflate_state
*state
,
1005 struct inflate_huff_code_large
*huff_code
)
1012 if (state
->read_in_length
<= ISAL_DEF_MAX_CODE_LEN
)
1013 inflate_in_load(state
, 0);
1015 next_bits
= state
->read_in
& ((1 << ISAL_DECODE_LONG_BITS
) - 1);
1017 /* next_sym is a possible symbol decoded from next_bits. If bit 15 is 0,
1018 * next_code is a symbol. Bits 9:0 represent the symbol, and bits 14:10
1019 * represent the length of that symbols huffman code. If next_sym is not
1020 * a symbol, it provides a hint of where the large symbols containin
1021 * this code are located. Note the hint is at largest the location the
1022 * first actual symbol in the long code list.*/
1023 next_sym
= huff_code
->short_code_lookup
[next_bits
];
1025 if ((next_sym
& LARGE_FLAG_BIT
) == 0) {
1026 /* Return symbol found if next_code is a complete huffman code
1027 * and shift in buffer over by the length of the next_code */
1028 bit_count
= next_sym
>> LARGE_SHORT_CODE_LEN_OFFSET
;
1029 state
->read_in
>>= bit_count
;
1030 state
->read_in_length
-= bit_count
;
1033 next_sym
= INVALID_SYMBOL
;
1035 *sym_count
= (next_sym
>> LARGE_SYM_COUNT_OFFSET
) & LARGE_SYM_COUNT_MASK
;
1036 *next_lits
= next_sym
& LARGE_SHORT_SYM_MASK
;
1039 /* If a symbol is not found, do a lookup in the long code
1040 * list starting from the hint in next_sym */
1041 bit_mask
= next_sym
>> LARGE_SHORT_MAX_LEN_OFFSET
;
1042 bit_mask
= (1 << bit_mask
) - 1;
1043 next_bits
= state
->read_in
& bit_mask
;
1045 huff_code
->long_code_lookup
[(next_sym
& LARGE_SHORT_SYM_MASK
) +
1046 (next_bits
>> ISAL_DECODE_LONG_BITS
)];
1047 bit_count
= next_sym
>> LARGE_LONG_CODE_LEN_OFFSET
;
1048 state
->read_in
>>= bit_count
;
1049 state
->read_in_length
-= bit_count
;
1052 next_sym
= INVALID_SYMBOL
;
1055 *next_lits
= next_sym
& LARGE_LONG_SYM_MASK
;
1059 static uint16_t inline decode_next_dist(struct inflate_state
*state
,
1060 struct inflate_huff_code_small
*huff_code
)
1067 if (state
->read_in_length
<= ISAL_DEF_MAX_CODE_LEN
)
1068 inflate_in_load(state
, 0);
1070 next_bits
= state
->read_in
& ((1 << ISAL_DECODE_SHORT_BITS
) - 1);
1072 /* next_sym is a possible symbol decoded from next_bits. If bit 15 is 0,
1073 * next_code is a symbol. Bits 9:0 represent the symbol, and bits 14:10
1074 * represent the length of that symbols huffman code. If next_sym is not
1075 * a symbol, it provides a hint of where the large symbols containin
1076 * this code are located. Note the hint is at largest the location the
1077 * first actual symbol in the long code list.*/
1078 next_sym
= huff_code
->short_code_lookup
[next_bits
];
1080 if ((next_sym
& SMALL_FLAG_BIT
) == 0) {
1081 /* Return symbol found if next_code is a complete huffman code
1082 * and shift in buffer over by the length of the next_code */
1083 bit_count
= next_sym
>> SMALL_SHORT_CODE_LEN_OFFSET
;
1084 state
->read_in
>>= bit_count
;
1085 state
->read_in_length
-= bit_count
;
1087 if (bit_count
== 0) {
1088 state
->read_in_length
-= next_sym
;
1089 next_sym
= INVALID_SYMBOL
;
1092 return next_sym
& DIST_SYM_MASK
;
1095 /* If a symbol is not found, perform a linear search of the long code
1096 * list starting from the hint in next_sym */
1097 bit_mask
= (next_sym
- SMALL_FLAG_BIT
) >> SMALL_SHORT_CODE_LEN_OFFSET
;
1098 bit_mask
= (1 << bit_mask
) - 1;
1099 next_bits
= state
->read_in
& bit_mask
;
1101 huff_code
->long_code_lookup
[(next_sym
& SMALL_SHORT_SYM_MASK
) +
1102 (next_bits
>> ISAL_DECODE_SHORT_BITS
)];
1103 bit_count
= next_sym
>> SMALL_LONG_CODE_LEN_OFFSET
;
1104 state
->read_in
>>= bit_count
;
1105 state
->read_in_length
-= bit_count
;
1107 if (bit_count
== 0) {
1108 state
->read_in_length
-= next_sym
;
1109 next_sym
= INVALID_SYMBOL
;
1112 return next_sym
& DIST_SYM_MASK
;
1116 static uint16_t inline decode_next_header(struct inflate_state
*state
,
1117 struct inflate_huff_code_small
*huff_code
)
1124 if (state
->read_in_length
<= ISAL_DEF_MAX_CODE_LEN
)
1125 inflate_in_load(state
, 0);
1127 next_bits
= state
->read_in
& ((1 << ISAL_DECODE_SHORT_BITS
) - 1);
1129 /* next_sym is a possible symbol decoded from next_bits. If bit 15 is 0,
1130 * next_code is a symbol. Bits 9:0 represent the symbol, and bits 14:10
1131 * represent the length of that symbols huffman code. If next_sym is not
1132 * a symbol, it provides a hint of where the large symbols containin
1133 * this code are located. Note the hint is at largest the location the
1134 * first actual symbol in the long code list.*/
1135 next_sym
= huff_code
->short_code_lookup
[next_bits
];
1137 if ((next_sym
& SMALL_FLAG_BIT
) == 0) {
1138 /* Return symbol found if next_code is a complete huffman code
1139 * and shift in buffer over by the length of the next_code */
1140 bit_count
= next_sym
>> SMALL_SHORT_CODE_LEN_OFFSET
;
1141 state
->read_in
>>= bit_count
;
1142 state
->read_in_length
-= bit_count
;
1145 next_sym
= INVALID_SYMBOL
;
1147 return next_sym
& SMALL_SHORT_SYM_MASK
;
1150 /* If a symbol is not found, perform a linear search of the long code
1151 * list starting from the hint in next_sym */
1152 bit_mask
= (next_sym
- SMALL_FLAG_BIT
) >> SMALL_SHORT_CODE_LEN_OFFSET
;
1153 bit_mask
= (1 << bit_mask
) - 1;
1154 next_bits
= state
->read_in
& bit_mask
;
1156 huff_code
->long_code_lookup
[(next_sym
& SMALL_SHORT_SYM_MASK
) +
1157 (next_bits
>> ISAL_DECODE_SHORT_BITS
)];
1158 bit_count
= next_sym
>> SMALL_LONG_CODE_LEN_OFFSET
;
1159 state
->read_in
>>= bit_count
;
1160 state
->read_in_length
-= bit_count
;
1161 return next_sym
& SMALL_LONG_SYM_MASK
;
1166 /* Reads data from the in_buffer and sets the huff code corresponding to that
1168 static int inline setup_dynamic_header(struct inflate_state
*state
)
1171 struct huff_code code_huff
[CODE_LEN_CODES
];
1172 struct huff_code lit_and_dist_huff
[LIT_LEN_ELEMS
];
1173 struct huff_code
*previous
= NULL
, *current
, *end
, rep_code
;
1174 struct inflate_huff_code_small inflate_code_huff
;
1175 uint64_t hclen
, hdist
, hlit
;
1176 uint16_t code_count
[16], lit_count
[MAX_LIT_LEN_COUNT
],
1177 lit_expand_count
[MAX_LIT_LEN_COUNT
], dist_count
[16];
1180 uint32_t multisym
= DEFAULT_SYM_FLAG
, length
, max_dist
= DIST_LEN
;
1181 struct huff_code
*code
;
1185 uint32_t code_list
[LIT_LEN_ELEMS
+ 2]; /* The +2 is for the extra codes in the static header */
1187 /* This order is defined in RFC 1951 page 13 */
1188 const uint8_t code_length_order
[CODE_LEN_CODES
] = {
1189 0x10, 0x11, 0x12, 0x00, 0x08, 0x07, 0x09, 0x06,
1190 0x0a, 0x05, 0x0b, 0x04, 0x0c, 0x03, 0x0d, 0x02, 0x0e, 0x01, 0x0f
1193 if (state
->bfinal
&& state
->avail_in
<= SINGLE_SYM_THRESH
) {
1194 multisym
= SINGLE_SYM_FLAG
;
1195 } else if (state
->bfinal
&& state
->avail_in
<= DOUBLE_SYM_THRESH
) {
1196 multisym
= DOUBLE_SYM_FLAG
;
1199 memset(code_count
, 0, sizeof(code_count
));
1200 memset(lit_count
, 0, sizeof(lit_count
));
1201 memset(lit_expand_count
, 0, sizeof(lit_expand_count
));
1202 memset(dist_count
, 0, sizeof(dist_count
));
1203 memset(code_huff
, 0, sizeof(code_huff
));
1204 memset(lit_and_dist_huff
, 0, sizeof(lit_and_dist_huff
));
1206 /* These variables are defined in the deflate standard, RFC 1951 */
1207 inflate_in_load(state
, 0);
1208 if (state
->read_in_length
< 14)
1209 return ISAL_END_INPUT
;
1211 hlit
= inflate_in_read_bits_unsafe(state
, 5);
1212 hdist
= inflate_in_read_bits_unsafe(state
, 5);
1213 hclen
= inflate_in_read_bits_unsafe(state
, 4);
1215 if (hlit
> 29 || hdist
> 29 || hclen
> 15)
1216 return ISAL_INVALID_BLOCK
;
1218 /* Create the code huffman code for decoding the lit/len and dist huffman codes */
1219 for (i
= 0; i
< 4; i
++) {
1220 code
= &code_huff
[code_length_order
[i
]];
1221 length
= inflate_in_read_bits_unsafe(state
, 3);
1222 write_huff_code(code
, 0, length
);
1223 code_count
[length
] += 1;
1227 inflate_in_load(state
, 0);
1229 for (i
= 4; i
< hclen
+ 4; i
++) {
1230 code
= &code_huff
[code_length_order
[i
]];
1231 length
= inflate_in_read_bits_unsafe(state
, 3);
1232 write_huff_code(code
, 0, length
);
1233 code_count
[length
] += 1;
1237 if (state
->read_in_length
< 0)
1238 return ISAL_END_INPUT
;
1240 if (!flag
|| set_codes(code_huff
, CODE_LEN_CODES
, code_count
))
1241 return ISAL_INVALID_BLOCK
;
1243 make_inflate_huff_code_header(&inflate_code_huff
, code_huff
, CODE_LEN_CODES
,
1244 code_count
, CODE_LEN_CODES
);
1246 /* Decode the lit/len and dist huffman codes using the code huffman code */
1248 current
= lit_and_dist_huff
;
1249 end
= lit_and_dist_huff
+ LIT_LEN
+ hdist
+ 1;
1251 while (current
< end
) {
1252 symbol
= decode_next_header(state
, &inflate_code_huff
);
1254 if (state
->read_in_length
< 0) {
1255 if (current
> &lit_and_dist_huff
[256]
1256 && lit_and_dist_huff
[256].length
<= 0)
1257 return ISAL_INVALID_BLOCK
;
1258 return ISAL_END_INPUT
;
1262 /* If a length is found, update the current lit/len/dist
1263 * to have length symbol */
1264 if (current
== lit_and_dist_huff
+ LIT_TABLE_SIZE
+ hlit
) {
1265 /* Switch code upon completion of lit_len table */
1266 current
= lit_and_dist_huff
+ LIT_LEN
;
1270 write_huff_code(current
, 0, symbol
);
1274 if (symbol
== 0 // No symbol
1275 || (previous
>= lit_and_dist_huff
+ LIT_TABLE_SIZE
+ hlit
) // Dist table
1276 || (previous
< lit_and_dist_huff
+ 264)) // Lit/Len with no extra bits
1280 rfc_lookup_table
.len_extra_bit_count
[previous
- LIT_TABLE_SIZE
-
1282 lit_expand_count
[symbol
]--;
1283 lit_expand_count
[symbol
+ extra_count
] += (1 << extra_count
);
1285 } else if (symbol
== 16) {
1286 /* If a repeat length is found, update the next repeat
1287 * length lit/len/dist elements to have the value of the
1288 * repeated length */
1290 i
= 3 + inflate_in_read_bits(state
, 2);
1292 if (current
+ i
> end
|| previous
== NULL
)
1293 return ISAL_INVALID_BLOCK
;
1295 rep_code
= *previous
;
1296 for (j
= 0; j
< i
; j
++) {
1297 if (current
== lit_and_dist_huff
+ LIT_TABLE_SIZE
+ hlit
) {
1298 /* Switch code upon completion of lit_len table */
1299 current
= lit_and_dist_huff
+ LIT_LEN
;
1303 *current
= rep_code
;
1304 count
[rep_code
.length
]++;
1308 if (rep_code
.length
== 0 // No symbol
1309 || (previous
>= lit_and_dist_huff
+ LIT_TABLE_SIZE
+ hlit
) // Dist table
1310 || (previous
< lit_and_dist_huff
+ 264)) // Lit/Len with no extra
1314 rfc_lookup_table
.len_extra_bit_count
1315 [previous
- lit_and_dist_huff
- LIT_TABLE_SIZE
];
1316 lit_expand_count
[rep_code
.length
]--;
1317 lit_expand_count
[rep_code
.length
+
1318 extra_count
] += (1 << extra_count
);
1321 } else if (symbol
== 17) {
1322 /* If a repeat zeroes if found, update then next
1323 * repeated zeroes length lit/len/dist elements to have
1325 i
= 3 + inflate_in_read_bits(state
, 3);
1327 current
= current
+ i
;
1328 previous
= current
- 1;
1330 if (count
!= dist_count
1331 && current
> lit_and_dist_huff
+ LIT_TABLE_SIZE
+ hlit
) {
1332 /* Switch code upon completion of lit_len table */
1333 current
+= LIT_LEN
- LIT_TABLE_SIZE
- hlit
;
1335 if (current
> lit_and_dist_huff
+ LIT_LEN
)
1336 previous
= current
- 1;
1339 } else if (symbol
== 18) {
1340 /* If a repeat zeroes if found, update then next
1341 * repeated zeroes length lit/len/dist elements to have
1343 i
= 11 + inflate_in_read_bits(state
, 7);
1345 current
= current
+ i
;
1346 previous
= current
- 1;
1348 if (count
!= dist_count
1349 && current
> lit_and_dist_huff
+ LIT_TABLE_SIZE
+ hlit
) {
1350 /* Switch code upon completion of lit_len table */
1351 current
+= LIT_LEN
- LIT_TABLE_SIZE
- hlit
;
1353 if (current
> lit_and_dist_huff
+ LIT_LEN
)
1354 previous
= current
- 1;
1358 return ISAL_INVALID_BLOCK
;
1362 if (current
> end
|| lit_and_dist_huff
[256].length
<= 0)
1363 return ISAL_INVALID_BLOCK
;
1365 if (state
->read_in_length
< 0)
1366 return ISAL_END_INPUT
;
1368 if (set_codes(&lit_and_dist_huff
[LIT_LEN
], DIST_LEN
, dist_count
))
1369 return ISAL_INVALID_BLOCK
;
1371 if (state
->hist_bits
&& state
->hist_bits
< 15)
1372 max_dist
= 2 * state
->hist_bits
;
1374 make_inflate_huff_code_dist(&state
->dist_huff_code
, &lit_and_dist_huff
[LIT_LEN
],
1375 DIST_LEN
, dist_count
, max_dist
);
1377 if (set_and_expand_lit_len_huffcode
1378 (lit_and_dist_huff
, LIT_LEN
, lit_count
, lit_expand_count
, code_list
))
1379 return ISAL_INVALID_BLOCK
;
1381 make_inflate_huff_code_lit_len(&state
->lit_huff_code
, lit_and_dist_huff
, LIT_LEN_ELEMS
,
1382 lit_count
, code_list
, multisym
);
1384 state
->block_state
= ISAL_BLOCK_CODED
;
1389 /* Reads in the header pointed to by in_stream and sets up state to reflect that
1390 * header information*/
1391 static int read_header(struct inflate_state
*state
)
1398 /* btype and bfinal are defined in RFC 1951, bfinal represents whether
1399 * the current block is the end of block, and btype represents the
1400 * encoding method on the current block. */
1402 state
->bfinal
= inflate_in_read_bits(state
, 1);
1403 btype
= inflate_in_read_bits(state
, 2);
1405 if (state
->read_in_length
< 0)
1406 ret
= ISAL_END_INPUT
;
1408 else if (btype
== 0) {
1409 inflate_in_load(state
, 40);
1410 bytes
= state
->read_in_length
/ 8;
1413 return ISAL_END_INPUT
;
1415 state
->read_in
>>= state
->read_in_length
% 8;
1416 state
->read_in_length
= bytes
* 8;
1418 len
= state
->read_in
& 0xFFFF;
1419 state
->read_in
>>= 16;
1420 nlen
= state
->read_in
& 0xFFFF;
1421 state
->read_in
>>= 16;
1422 state
->read_in_length
-= 32;
1424 /* Check if len and nlen match */
1425 if (len
!= (~nlen
& 0xffff))
1426 return ISAL_INVALID_BLOCK
;
1428 state
->type0_block_len
= len
;
1429 state
->block_state
= ISAL_BLOCK_TYPE0
;
1433 } else if (btype
== 1)
1434 ret
= setup_static_header(state
);
1436 else if (btype
== 2)
1437 ret
= setup_dynamic_header(state
);
1440 ret
= ISAL_INVALID_BLOCK
;
1445 /* Reads in the header pointed to by in_stream and sets up state to reflect that
1446 * header information*/
1447 static int read_header_stateful(struct inflate_state
*state
)
1449 uint64_t read_in_start
= state
->read_in
;
1450 int32_t read_in_length_start
= state
->read_in_length
;
1451 uint8_t *next_in_start
= state
->next_in
;
1452 uint32_t avail_in_start
= state
->avail_in
;
1453 int block_state_start
= state
->block_state
;
1458 if (block_state_start
== ISAL_BLOCK_HDR
) {
1459 /* Setup so read_header decodes data in tmp_in_buffer */
1460 copy_size
= ISAL_DEF_MAX_HDR_SIZE
- state
->tmp_in_size
;
1461 if (copy_size
> state
->avail_in
)
1462 copy_size
= state
->avail_in
;
1464 memcpy(&state
->tmp_in_buffer
[state
->tmp_in_size
], state
->next_in
, copy_size
);
1465 state
->next_in
= state
->tmp_in_buffer
;
1466 state
->avail_in
= state
->tmp_in_size
+ copy_size
;
1469 ret
= read_header(state
);
1471 if (block_state_start
== ISAL_BLOCK_HDR
) {
1472 /* Setup so state is restored to a valid state */
1473 bytes_read
= state
->next_in
- state
->tmp_in_buffer
- state
->tmp_in_size
;
1476 state
->next_in
= next_in_start
+ bytes_read
;
1477 state
->avail_in
= avail_in_start
- bytes_read
;
1480 if (ret
== ISAL_END_INPUT
) {
1481 /* Save off data so header can be decoded again with more data */
1482 state
->read_in
= read_in_start
;
1483 state
->read_in_length
= read_in_length_start
;
1484 memcpy(&state
->tmp_in_buffer
[state
->tmp_in_size
], next_in_start
,
1486 state
->tmp_in_size
+= avail_in_start
;
1487 state
->avail_in
= 0;
1488 state
->next_in
= next_in_start
+ avail_in_start
;
1489 state
->block_state
= ISAL_BLOCK_HDR
;
1491 state
->tmp_in_size
= 0;
1497 static int inline decode_literal_block(struct inflate_state
*state
)
1499 uint32_t len
= state
->type0_block_len
;
1500 uint32_t bytes
= state
->read_in_length
/ 8;
1501 /* If the block is uncompressed, perform a memcopy while
1502 * updating state data */
1503 state
->block_state
= state
->bfinal
? ISAL_BLOCK_INPUT_DONE
: ISAL_BLOCK_NEW_HDR
;
1505 if (state
->avail_out
< len
) {
1506 len
= state
->avail_out
;
1507 state
->block_state
= ISAL_BLOCK_TYPE0
;
1510 if (state
->avail_in
+ bytes
< len
) {
1511 len
= state
->avail_in
+ bytes
;
1512 state
->block_state
= ISAL_BLOCK_TYPE0
;
1514 if (state
->read_in_length
) {
1516 memcpy(state
->next_out
, &state
->read_in
, bytes
);
1518 state
->next_out
+= bytes
;
1519 state
->avail_out
-= bytes
;
1520 state
->total_out
+= bytes
;
1521 state
->type0_block_len
-= bytes
;
1524 state
->read_in_length
= 0;
1529 memcpy(state
->next_out
, &state
->read_in
, len
);
1531 state
->next_out
+= len
;
1532 state
->avail_out
-= len
;
1533 state
->total_out
+= len
;
1534 state
->type0_block_len
-= len
;
1536 state
->read_in
>>= 8 * len
;
1537 state
->read_in_length
-= 8 * len
;
1542 memcpy(state
->next_out
, state
->next_in
, len
);
1544 state
->next_out
+= len
;
1545 state
->avail_out
-= len
;
1546 state
->total_out
+= len
;
1547 state
->next_in
+= len
;
1548 state
->avail_in
-= len
;
1549 state
->type0_block_len
-= len
;
1551 if (state
->avail_in
+ bytes
== 0 && state
->block_state
!= ISAL_BLOCK_INPUT_DONE
)
1552 return ISAL_END_INPUT
;
1554 if (state
->avail_out
== 0 && state
->type0_block_len
> 0)
1555 return ISAL_OUT_OVERFLOW
;
1561 /* Decodes the next block if it was encoded using a huffman code */
1562 int decode_huffman_code_block_stateless_base(struct inflate_state
*state
, uint8_t * start_out
)
1566 uint32_t repeat_length
;
1567 uint32_t look_back_dist
;
1568 uint64_t read_in_tmp
;
1569 int32_t read_in_length_tmp
;
1570 uint8_t *next_in_tmp
, *next_out_tmp
;
1571 uint32_t avail_in_tmp
, avail_out_tmp
, total_out_tmp
;
1572 uint32_t next_lits
, sym_count
;
1573 struct rfc1951_tables
*rfc
= &rfc_lookup_table
;
1575 state
->copy_overflow_length
= 0;
1576 state
->copy_overflow_distance
= 0;
1578 while (state
->block_state
== ISAL_BLOCK_CODED
) {
1579 /* While not at the end of block, decode the next
1581 inflate_in_load(state
, 0);
1583 read_in_tmp
= state
->read_in
;
1584 read_in_length_tmp
= state
->read_in_length
;
1585 next_in_tmp
= state
->next_in
;
1586 avail_in_tmp
= state
->avail_in
;
1587 next_out_tmp
= state
->next_out
;
1588 avail_out_tmp
= state
->avail_out
;
1589 total_out_tmp
= state
->total_out
;
1591 decode_next_lit_len(&next_lits
, &sym_count
, state
, &state
->lit_huff_code
);
1594 return ISAL_INVALID_SYMBOL
;
1596 if (state
->read_in_length
< 0) {
1597 state
->read_in
= read_in_tmp
;
1598 state
->read_in_length
= read_in_length_tmp
;
1599 state
->next_in
= next_in_tmp
;
1600 state
->avail_in
= avail_in_tmp
;
1601 return ISAL_END_INPUT
;
1604 while (sym_count
> 0) {
1605 next_lit
= next_lits
& 0xffff;
1606 if (next_lit
< 256 || sym_count
> 1) {
1607 /* If the next symbol is a literal,
1608 * write out the symbol and update state
1609 * data accordingly. */
1610 if (state
->avail_out
< 1) {
1611 state
->write_overflow_lits
= next_lits
;
1612 state
->write_overflow_len
= sym_count
;
1613 next_lits
= next_lits
>> (8 * (sym_count
- 1));
1616 if (next_lits
< 256)
1617 return ISAL_OUT_OVERFLOW
;
1618 else if (next_lits
== 256) {
1619 state
->write_overflow_len
-= 1;
1620 state
->block_state
= state
->bfinal
?
1621 ISAL_BLOCK_INPUT_DONE
: ISAL_BLOCK_NEW_HDR
;
1622 return ISAL_OUT_OVERFLOW
;
1624 state
->write_overflow_len
-= 1;
1629 *state
->next_out
= next_lit
;
1634 } else if (next_lit
== 256) {
1635 /* If the next symbol is the end of
1636 * block, update the state data
1638 state
->block_state
= state
->bfinal
?
1639 ISAL_BLOCK_INPUT_DONE
: ISAL_BLOCK_NEW_HDR
;
1641 } else if (next_lit
<= MAX_LIT_LEN_SYM
) {
1642 /* Else if the next symbol is a repeat
1643 * length, read in the length extra
1644 * bits, the distance code, the distance
1645 * extra bits. Then write out the
1646 * corresponding data and update the
1647 * state data accordingly*/
1648 repeat_length
= next_lit
- 254;
1649 next_dist
= decode_next_dist(state
, &state
->dist_huff_code
);
1651 if (state
->read_in_length
>= 0) {
1652 if (next_dist
>= DIST_LEN
)
1653 return ISAL_INVALID_SYMBOL
;
1655 look_back_dist
= rfc
->dist_start
[next_dist
] +
1656 inflate_in_read_bits(state
,
1657 rfc
->dist_extra_bit_count
1661 if (state
->read_in_length
< 0) {
1662 state
->read_in
= read_in_tmp
;
1663 state
->read_in_length
= read_in_length_tmp
;
1664 state
->next_in
= next_in_tmp
;
1665 state
->avail_in
= avail_in_tmp
;
1666 state
->next_out
= next_out_tmp
;
1667 state
->avail_out
= avail_out_tmp
;
1668 state
->total_out
= total_out_tmp
;
1669 state
->write_overflow_lits
= 0;
1670 state
->write_overflow_len
= 0;
1671 return ISAL_END_INPUT
;
1674 if (state
->next_out
- look_back_dist
< start_out
)
1675 return ISAL_INVALID_LOOKBACK
;
1677 if (state
->avail_out
< repeat_length
) {
1678 state
->copy_overflow_length
=
1679 repeat_length
- state
->avail_out
;
1680 state
->copy_overflow_distance
= look_back_dist
;
1681 repeat_length
= state
->avail_out
;
1684 if (look_back_dist
> repeat_length
)
1685 memcpy(state
->next_out
,
1686 state
->next_out
- look_back_dist
,
1689 byte_copy(state
->next_out
, look_back_dist
,
1692 state
->next_out
+= repeat_length
;
1693 state
->avail_out
-= repeat_length
;
1694 state
->total_out
+= repeat_length
;
1696 if (state
->copy_overflow_length
> 0)
1697 return ISAL_OUT_OVERFLOW
;
1699 /* Else the read in bits do not
1700 * correspond to any valid symbol */
1701 return ISAL_INVALID_SYMBOL
;
1711 void isal_inflate_init(struct inflate_state
*state
)
1715 state
->read_in_length
= 0;
1716 state
->next_in
= NULL
;
1717 state
->avail_in
= 0;
1718 state
->next_out
= NULL
;
1719 state
->avail_out
= 0;
1720 state
->total_out
= 0;
1721 state
->dict_length
= 0;
1722 state
->block_state
= ISAL_BLOCK_NEW_HDR
;
1724 state
->crc_flag
= 0;
1726 state
->hist_bits
= 0;
1727 state
->type0_block_len
= 0;
1728 state
->write_overflow_lits
= 0;
1729 state
->write_overflow_len
= 0;
1730 state
->copy_overflow_length
= 0;
1731 state
->copy_overflow_distance
= 0;
1732 state
->wrapper_flag
= 0;
1733 state
->tmp_in_size
= 0;
1734 state
->tmp_out_processed
= 0;
1735 state
->tmp_out_valid
= 0;
1738 void isal_inflate_reset(struct inflate_state
*state
)
1741 state
->read_in_length
= 0;
1742 state
->total_out
= 0;
1743 state
->dict_length
= 0;
1744 state
->block_state
= ISAL_BLOCK_NEW_HDR
;
1747 state
->type0_block_len
= 0;
1748 state
->write_overflow_lits
= 0;
1749 state
->write_overflow_len
= 0;
1750 state
->copy_overflow_length
= 0;
1751 state
->copy_overflow_distance
= 0;
1752 state
->tmp_in_size
= 0;
1753 state
->tmp_out_processed
= 0;
1754 state
->tmp_out_valid
= 0;
1757 static inline uint32_t fixed_size_read(struct inflate_state
*state
,
1758 uint8_t ** read_buf
, int read_size
)
1760 uint32_t tmp_in_size
= state
->tmp_in_size
;
1762 if (state
->avail_in
+ tmp_in_size
< read_size
) {
1763 memcpy(state
->tmp_in_buffer
+ tmp_in_size
, state
->next_in
, state
->avail_in
);
1764 tmp_in_size
+= state
->avail_in
;
1765 state
->tmp_in_size
= tmp_in_size
;
1766 state
->next_in
+= state
->avail_in
;
1767 state
->avail_in
= 0;
1769 return ISAL_END_INPUT
;
1772 *read_buf
= state
->next_in
;
1774 memcpy(state
->tmp_in_buffer
+ tmp_in_size
, state
->next_in
,
1775 read_size
- tmp_in_size
);
1776 *read_buf
= state
->tmp_in_buffer
;
1777 state
->tmp_in_size
= 0;
1780 state
->next_in
+= read_size
- tmp_in_size
;
1781 state
->avail_in
-= read_size
- tmp_in_size
;
1788 static inline uint32_t buffer_header_copy(struct inflate_state
*state
, uint32_t in_len
,
1789 uint8_t * buf
, uint32_t buf_len
, uint32_t buf_error
)
1791 uint32_t len
= in_len
;
1792 if (len
> state
->avail_in
)
1793 len
= state
->avail_in
;
1795 if (buf
!= NULL
&& buf_len
< len
) {
1796 memcpy(buf
, state
->next_in
, buf_len
);
1797 state
->next_in
+= buf_len
;
1798 state
->avail_in
-= buf_len
;
1799 state
->count
= in_len
- buf_len
;
1803 memcpy(buf
, state
->next_in
, len
);
1804 state
->next_in
+= len
;
1805 state
->avail_in
-= len
;
1806 state
->count
= in_len
- len
;
1811 return ISAL_END_INPUT
;
1815 static inline uint32_t string_header_copy(struct inflate_state
*state
,
1816 char *str_buf
, uint32_t str_len
, uint32_t str_error
)
1818 uint32_t len
, max_len
= str_len
;
1820 if (max_len
> state
->avail_in
|| str_buf
== NULL
)
1821 max_len
= state
->avail_in
;
1823 len
= strnlen((char *)state
->next_in
, max_len
);
1825 if (str_buf
!= NULL
)
1826 memcpy(str_buf
, state
->next_in
, len
);
1828 state
->next_in
+= len
;
1829 state
->avail_in
-= len
;
1830 state
->count
+= len
;
1832 if (str_buf
!= NULL
&& len
== str_len
)
1834 else if (state
->avail_in
<= 0)
1835 return ISAL_END_INPUT
;
1840 if (str_buf
!= NULL
)
1847 static int check_gzip_checksum(struct inflate_state
*state
)
1849 uint64_t trailer
, crc
, total_out
;
1851 uint32_t byte_count
, offset
, tmp_in_size
= state
->tmp_in_size
;
1854 if (state
->read_in_length
>= 8 * GZIP_TRAILER_LEN
) {
1855 /* The following is unecessary as state->read_in_length == 64 */
1856 /* bit_count = state->read_in_length % 8; */
1857 /* state->read_in >>= bit_count; */
1858 /* state->read_in_length -= bit_count; */
1860 trailer
= state
->read_in
;
1861 state
->read_in_length
= 0;
1864 if (state
->read_in_length
>= 8) {
1865 byte_count
= state
->read_in_length
/ 8;
1866 offset
= state
->read_in_length
% 8;
1868 store_u64(state
->tmp_in_buffer
+ tmp_in_size
,
1869 state
->read_in
>> offset
);
1871 state
->read_in_length
= 0;
1873 tmp_in_size
+= byte_count
;
1874 state
->tmp_in_size
= tmp_in_size
;
1877 ret
= fixed_size_read(state
, &next_in
, GZIP_TRAILER_LEN
);
1879 state
->block_state
= ISAL_CHECKSUM_CHECK
;
1883 trailer
= load_u64(next_in
);
1886 state
->block_state
= ISAL_BLOCK_FINISH
;
1889 total_out
= state
->total_out
;
1891 if (trailer
!= (crc
| (total_out
<< 32)))
1892 return ISAL_INCORRECT_CHECKSUM
;
1894 return ISAL_DECOMP_OK
;
1897 static int check_zlib_checksum(struct inflate_state
*state
)
1902 uint32_t byte_count
, offset
, tmp_in_size
= state
->tmp_in_size
;
1905 if (state
->read_in_length
>= 8 * ZLIB_TRAILER_LEN
) {
1906 bit_count
= state
->read_in_length
% 8;
1907 state
->read_in
>>= bit_count
;
1908 state
->read_in_length
-= bit_count
;
1910 trailer
= state
->read_in
;
1912 state
->read_in_length
-= 8 * ZLIB_TRAILER_LEN
;
1913 state
->read_in
>>= 8 * ZLIB_TRAILER_LEN
;
1915 if (state
->read_in_length
>= 8) {
1916 byte_count
= state
->read_in_length
/ 8;
1917 offset
= state
->read_in_length
% 8;
1919 store_u64(state
->tmp_in_buffer
+ tmp_in_size
,
1920 state
->read_in
>> offset
);
1922 state
->read_in_length
= 0;
1924 tmp_in_size
+= byte_count
;
1925 state
->tmp_in_size
= tmp_in_size
;
1928 ret
= fixed_size_read(state
, &next_in
, ZLIB_TRAILER_LEN
);
1930 state
->block_state
= ISAL_CHECKSUM_CHECK
;
1934 trailer
= load_u32(next_in
);
1937 state
->block_state
= ISAL_BLOCK_FINISH
;
1939 if (bswap_32(trailer
) != state
->crc
)
1940 return ISAL_INCORRECT_CHECKSUM
;
1942 return ISAL_DECOMP_OK
;
1945 int isal_read_gzip_header(struct inflate_state
*state
, struct isal_gzip_header
*gz_hdr
)
1947 int cm
, flags
= gz_hdr
->flags
, id1
, id2
;
1948 uint16_t xlen
= gz_hdr
->extra_len
;
1949 uint32_t block_state
= state
->block_state
;
1950 uint8_t *start_in
= state
->next_in
, *next_in
;
1951 uint32_t tmp_in_size
= state
->tmp_in_size
;
1952 uint32_t count
= state
->count
, offset
;
1953 uint32_t hcrc
= gz_hdr
->hcrc
;
1956 /* This switch is a jump table into the function so that decoding the
1957 * header can continue where it stopped on the last call */
1958 switch (block_state
) {
1959 case ISAL_BLOCK_NEW_HDR
:
1961 flags
= UNDEFINED_FLAG
;
1962 if (tmp_in_size
== 0)
1965 ret
= fixed_size_read(state
, &next_in
, GZIP_HDR_BASE
);
1973 gz_hdr
->time
= load_u32(next_in
+ 4);
1974 gz_hdr
->xflags
= *(next_in
+ 8);
1975 gz_hdr
->os
= *(next_in
+ 9);
1977 if (id1
!= 0x1f || id2
!= 0x8b)
1978 return ISAL_INVALID_WRAPPER
;
1980 if (cm
!= DEFLATE_METHOD
)
1981 return ISAL_UNSUPPORTED_METHOD
;
1984 if (flags
& TEXT_FLAG
)
1987 gz_hdr
->flags
= flags
;
1989 if (flags
& EXTRA_FLAG
) {
1990 case ISAL_GZIP_EXTRA_LEN
:
1991 ret
= fixed_size_read(state
, &next_in
, GZIP_EXTRA_LEN
);
1993 state
->block_state
= ISAL_GZIP_EXTRA_LEN
;
1997 xlen
= load_u16(next_in
);
2000 gz_hdr
->extra_len
= xlen
;
2002 case ISAL_GZIP_EXTRA
:
2003 offset
= gz_hdr
->extra_len
- count
;
2005 buffer_header_copy(state
, count
, gz_hdr
->extra
+ offset
,
2006 gz_hdr
->extra_buf_len
- offset
,
2007 ISAL_EXTRA_OVERFLOW
);
2010 state
->block_state
= ISAL_GZIP_EXTRA
;
2014 gz_hdr
->extra_len
= 0;
2017 if (flags
& NAME_FLAG
) {
2018 case ISAL_GZIP_NAME
:
2019 offset
= state
->count
;
2020 ret
= string_header_copy(state
, gz_hdr
->name
+ offset
,
2021 gz_hdr
->name_buf_len
- offset
,
2022 ISAL_NAME_OVERFLOW
);
2024 state
->block_state
= ISAL_GZIP_NAME
;
2029 if (flags
& COMMENT_FLAG
) {
2030 case ISAL_GZIP_COMMENT
:
2031 offset
= state
->count
;
2032 ret
= string_header_copy(state
, gz_hdr
->comment
+ offset
,
2033 gz_hdr
->comment_buf_len
- offset
,
2034 ISAL_COMMENT_OVERFLOW
);
2036 state
->block_state
= ISAL_GZIP_COMMENT
;
2041 if (flags
& HCRC_FLAG
) {
2042 hcrc
= crc32_gzip_refl(hcrc
, start_in
, state
->next_in
- start_in
);
2043 gz_hdr
->hcrc
= hcrc
;
2045 case ISAL_GZIP_HCRC
:
2046 ret
= fixed_size_read(state
, &next_in
, GZIP_HCRC_LEN
);
2048 state
->block_state
= ISAL_GZIP_HCRC
;
2052 if ((hcrc
& 0xffff) != load_u16(next_in
))
2053 return ISAL_INCORRECT_CHECKSUM
;
2056 state
->wrapper_flag
= 1;
2057 state
->block_state
= ISAL_BLOCK_NEW_HDR
;
2058 return ISAL_DECOMP_OK
;
2061 if (flags
& HCRC_FLAG
)
2062 gz_hdr
->hcrc
= crc32_gzip_refl(hcrc
, start_in
, state
->next_in
- start_in
);
2067 int isal_read_zlib_header(struct inflate_state
*state
, struct isal_zlib_header
*zlib_hdr
)
2069 int cmf
, method
, flags
;
2070 uint32_t block_state
= state
->block_state
;
2074 switch (block_state
) {
2075 case ISAL_BLOCK_NEW_HDR
:
2076 zlib_hdr
->dict_flag
= 0;
2077 ret
= fixed_size_read(state
, &next_in
, ZLIB_HDR_BASE
);
2083 flags
= *(next_in
+ 1);
2085 zlib_hdr
->info
= cmf
>> ZLIB_INFO_OFFSET
;
2086 zlib_hdr
->dict_flag
= (flags
& ZLIB_DICT_FLAG
) ? 1 : 0;
2087 zlib_hdr
->level
= flags
>> ZLIB_LEVEL_OFFSET
;
2089 if (method
!= DEFLATE_METHOD
)
2090 return ISAL_UNSUPPORTED_METHOD
;
2092 if ((256 * cmf
+ flags
) % 31 != 0)
2093 return ISAL_INCORRECT_CHECKSUM
;
2095 if (zlib_hdr
->dict_flag
) {
2096 case ISAL_ZLIB_DICT
:
2097 ret
= fixed_size_read(state
, &next_in
, ZLIB_DICT_LEN
);
2099 state
->block_state
= ISAL_ZLIB_DICT
;
2103 zlib_hdr
->dict_id
= load_u32(next_in
);
2106 state
->wrapper_flag
= 1;
2107 state
->block_state
= ISAL_BLOCK_NEW_HDR
;
2113 int isal_inflate_set_dict(struct inflate_state
*state
, uint8_t * dict
, uint32_t dict_len
)
2116 if (state
->block_state
!= ISAL_BLOCK_NEW_HDR
2117 || state
->tmp_out_processed
!= state
->tmp_out_valid
)
2118 return ISAL_INVALID_STATE
;
2120 if (dict_len
> IGZIP_HIST_SIZE
) {
2121 dict
= dict
+ dict_len
- IGZIP_HIST_SIZE
;
2122 dict_len
= IGZIP_HIST_SIZE
;
2125 memcpy(state
->tmp_out_buffer
, dict
, dict_len
);
2126 state
->tmp_out_processed
= dict_len
;
2127 state
->tmp_out_valid
= dict_len
;
2128 state
->dict_length
= dict_len
;
2133 int isal_inflate_stateless(struct inflate_state
*state
)
2136 uint8_t *start_out
= state
->next_out
;
2139 state
->read_in_length
= 0;
2140 state
->block_state
= ISAL_BLOCK_NEW_HDR
;
2141 state
->dict_length
= 0;
2144 state
->total_out
= 0;
2145 state
->hist_bits
= 0;
2146 state
->tmp_in_size
= 0;
2148 if (state
->crc_flag
== IGZIP_GZIP
) {
2149 struct isal_gzip_header gz_hdr
;
2150 ret
= isal_read_gzip_header(state
, &gz_hdr
);
2153 } else if (state
->crc_flag
== IGZIP_ZLIB
) {
2154 struct isal_zlib_header z_hdr
;
2155 ret
= isal_read_zlib_header(state
, &z_hdr
);
2158 if (z_hdr
.dict_flag
)
2159 return ISAL_NEED_DICT
;
2163 while (state
->block_state
!= ISAL_BLOCK_FINISH
) {
2164 if (state
->block_state
== ISAL_BLOCK_NEW_HDR
) {
2165 ret
= read_header(state
);
2171 if (state
->block_state
== ISAL_BLOCK_TYPE0
)
2172 ret
= decode_literal_block(state
);
2174 ret
= decode_huffman_code_block_stateless(state
, start_out
);
2178 if (state
->block_state
== ISAL_BLOCK_INPUT_DONE
)
2179 state
->block_state
= ISAL_BLOCK_FINISH
;
2182 /* Undo count stuff of bytes read into the read buffer */
2183 state
->next_in
-= state
->read_in_length
/ 8;
2184 state
->avail_in
+= state
->read_in_length
/ 8;
2185 state
->read_in_length
= 0;
2188 if (!ret
&& state
->crc_flag
) {
2189 update_checksum(state
, start_out
, state
->next_out
- start_out
);
2190 switch (state
->crc_flag
) {
2192 case ISAL_ZLIB_NO_HDR_VER
:
2193 finalize_adler32(state
);
2194 ret
= check_zlib_checksum(state
);
2197 case ISAL_ZLIB_NO_HDR
:
2198 finalize_adler32(state
);
2202 case ISAL_GZIP_NO_HDR_VER
:
2203 ret
= check_gzip_checksum(state
);
2211 int isal_inflate(struct inflate_state
*state
)
2214 uint8_t *start_out
= state
->next_out
;
2215 uint32_t avail_out
= state
->avail_out
;
2216 uint32_t copy_size
= 0;
2217 int32_t shift_size
= 0;
2220 if (!state
->wrapper_flag
&& state
->crc_flag
== IGZIP_GZIP
) {
2221 struct isal_gzip_header gz_hdr
;
2222 ret
= isal_read_gzip_header(state
, &gz_hdr
);
2226 return ISAL_DECOMP_OK
;
2227 } else if (!state
->wrapper_flag
&& state
->crc_flag
== IGZIP_ZLIB
) {
2228 struct isal_zlib_header z_hdr
;
2229 ret
= isal_read_zlib_header(state
, &z_hdr
);
2233 return ISAL_DECOMP_OK
;
2235 if (z_hdr
.dict_flag
) {
2236 state
->dict_id
= z_hdr
.dict_id
;
2237 return ISAL_NEED_DICT
;
2239 } else if (state
->block_state
== ISAL_CHECKSUM_CHECK
) {
2240 switch (state
->crc_flag
) {
2242 case ISAL_ZLIB_NO_HDR_VER
:
2243 ret
= check_zlib_checksum(state
);
2246 case ISAL_GZIP_NO_HDR_VER
:
2247 ret
= check_gzip_checksum(state
);
2251 return (ret
> 0) ? ISAL_DECOMP_OK
: ret
;
2254 if (state
->block_state
!= ISAL_BLOCK_FINISH
) {
2255 state
->total_out
+= state
->tmp_out_valid
- state
->tmp_out_processed
;
2256 /* If space in tmp_out buffer, decompress into the tmp_out_buffer */
2257 if (state
->tmp_out_valid
< 2 * ISAL_DEF_HIST_SIZE
) {
2258 /* Setup to start decoding into temp buffer */
2259 state
->next_out
= &state
->tmp_out_buffer
[state
->tmp_out_valid
];
2261 sizeof(state
->tmp_out_buffer
) - ISAL_LOOK_AHEAD
-
2262 state
->tmp_out_valid
;
2264 if ((int32_t) state
->avail_out
< 0)
2265 state
->avail_out
= 0;
2267 /* Decode into internal buffer until exit */
2268 while (state
->block_state
!= ISAL_BLOCK_INPUT_DONE
) {
2269 if (state
->block_state
== ISAL_BLOCK_NEW_HDR
2270 || state
->block_state
== ISAL_BLOCK_HDR
) {
2271 ret
= read_header_stateful(state
);
2277 if (state
->block_state
== ISAL_BLOCK_TYPE0
) {
2278 ret
= decode_literal_block(state
);
2280 uint8_t *tmp
= state
->tmp_out_buffer
;
2281 ret
= decode_huffman_code_block_stateless(state
, tmp
);
2288 /* Copy valid data from internal buffer into out_buffer */
2289 if (state
->write_overflow_len
!= 0) {
2290 store_u32(state
->next_out
, state
->write_overflow_lits
);
2291 state
->next_out
+= state
->write_overflow_len
;
2292 state
->total_out
+= state
->write_overflow_len
;
2293 state
->write_overflow_lits
= 0;
2294 state
->write_overflow_len
= 0;
2297 if (state
->copy_overflow_length
!= 0) {
2298 byte_copy(state
->next_out
, state
->copy_overflow_distance
,
2299 state
->copy_overflow_length
);
2300 state
->tmp_out_valid
+= state
->copy_overflow_length
;
2301 state
->next_out
+= state
->copy_overflow_length
;
2302 state
->total_out
+= state
->copy_overflow_length
;
2303 state
->copy_overflow_distance
= 0;
2304 state
->copy_overflow_length
= 0;
2307 state
->tmp_out_valid
= state
->next_out
- state
->tmp_out_buffer
;
2309 /* Setup state for decompressing into out_buffer */
2310 state
->next_out
= start_out
;
2311 state
->avail_out
= avail_out
;
2314 /* Copy data from tmp_out buffer into out_buffer */
2315 copy_size
= state
->tmp_out_valid
- state
->tmp_out_processed
;
2316 if (copy_size
> avail_out
)
2317 copy_size
= avail_out
;
2319 memcpy(state
->next_out
,
2320 &state
->tmp_out_buffer
[state
->tmp_out_processed
], copy_size
);
2322 state
->tmp_out_processed
+= copy_size
;
2323 state
->avail_out
-= copy_size
;
2324 state
->next_out
+= copy_size
;
2326 if (ret
== ISAL_INVALID_LOOKBACK
|| ret
== ISAL_INVALID_BLOCK
2327 || ret
== ISAL_INVALID_SYMBOL
) {
2328 /* Set total_out to not count data in tmp_out_buffer */
2329 state
->total_out
-= state
->tmp_out_valid
- state
->tmp_out_processed
;
2330 if (state
->crc_flag
)
2331 update_checksum(state
, start_out
, state
->next_out
- start_out
);
2335 /* If all data from tmp_out buffer has been processed, start
2336 * decompressing into the out buffer */
2337 if (state
->tmp_out_processed
== state
->tmp_out_valid
) {
2338 while (state
->block_state
!= ISAL_BLOCK_INPUT_DONE
) {
2339 if (state
->block_state
== ISAL_BLOCK_NEW_HDR
2340 || state
->block_state
== ISAL_BLOCK_HDR
) {
2341 ret
= read_header_stateful(state
);
2346 if (state
->block_state
== ISAL_BLOCK_TYPE0
)
2347 ret
= decode_literal_block(state
);
2350 decode_huffman_code_block_stateless(state
,
2357 if (state
->crc_flag
)
2358 update_checksum(state
, start_out
, state
->next_out
- start_out
);
2360 if (state
->block_state
!= ISAL_BLOCK_INPUT_DONE
2361 || state
->copy_overflow_length
+ state
->write_overflow_len
+
2362 state
->tmp_out_valid
> sizeof(state
->tmp_out_buffer
)) {
2363 /* Save decompression history in tmp_out buffer */
2364 if (state
->tmp_out_valid
== state
->tmp_out_processed
2365 && avail_out
- state
->avail_out
>= ISAL_DEF_HIST_SIZE
) {
2366 memcpy(state
->tmp_out_buffer
,
2367 state
->next_out
- ISAL_DEF_HIST_SIZE
,
2368 ISAL_DEF_HIST_SIZE
);
2369 state
->tmp_out_valid
= ISAL_DEF_HIST_SIZE
;
2370 state
->tmp_out_processed
= ISAL_DEF_HIST_SIZE
;
2372 } else if (state
->tmp_out_processed
>= ISAL_DEF_HIST_SIZE
) {
2373 shift_size
= state
->tmp_out_valid
- ISAL_DEF_HIST_SIZE
;
2374 if (shift_size
> state
->tmp_out_processed
)
2375 shift_size
= state
->tmp_out_processed
;
2377 memmove(state
->tmp_out_buffer
,
2378 &state
->tmp_out_buffer
[shift_size
],
2379 state
->tmp_out_valid
- shift_size
);
2380 state
->tmp_out_valid
-= shift_size
;
2381 state
->tmp_out_processed
-= shift_size
;
2386 /* Write overflow data into tmp buffer */
2387 if (state
->write_overflow_len
!= 0) {
2388 store_u32(&state
->tmp_out_buffer
[state
->tmp_out_valid
],
2389 state
->write_overflow_lits
);
2390 state
->tmp_out_valid
+= state
->write_overflow_len
;
2391 state
->total_out
+= state
->write_overflow_len
;
2392 state
->write_overflow_lits
= 0;
2393 state
->write_overflow_len
= 0;
2396 if (state
->copy_overflow_length
!= 0) {
2397 byte_copy(&state
->tmp_out_buffer
[state
->tmp_out_valid
],
2398 state
->copy_overflow_distance
, state
->copy_overflow_length
);
2399 state
->tmp_out_valid
+= state
->copy_overflow_length
;
2400 state
->total_out
+= state
->copy_overflow_length
;
2401 state
->copy_overflow_distance
= 0;
2402 state
->copy_overflow_length
= 0;
2405 if (ret
== ISAL_INVALID_LOOKBACK
|| ret
== ISAL_INVALID_BLOCK
2406 || ret
== ISAL_INVALID_SYMBOL
) {
2407 state
->total_out
-= state
->tmp_out_valid
- state
->tmp_out_processed
;
2411 if (state
->block_state
== ISAL_BLOCK_INPUT_DONE
2412 && state
->tmp_out_valid
== state
->tmp_out_processed
) {
2413 state
->block_state
= ISAL_BLOCK_FINISH
;
2415 switch (state
->crc_flag
) {
2417 case ISAL_ZLIB_NO_HDR_VER
:
2418 finalize_adler32(state
);
2419 ret
= check_zlib_checksum(state
);
2422 case ISAL_ZLIB_NO_HDR
:
2423 finalize_adler32(state
);
2427 case ISAL_GZIP_NO_HDR_VER
:
2428 ret
= check_gzip_checksum(state
);
2433 state
->total_out
-= state
->tmp_out_valid
- state
->tmp_out_processed
;
2436 return (ret
> 0) ? ISAL_DECOMP_OK
: ret
;