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