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