ceph/src/isa-l/igzip/igzip_inflate_ref.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 "igzip_inflate_ref.h"
  31
  32 void inline byte_copy(uint8_t * dest, uint64_t lookback_distance, int repeat_length)
  33 {
  34         uint8_t *src = dest - lookback_distance;
  35
  36         for (; repeat_length > 0; repeat_length--)
  37                 *dest++ = *src++;
  38 }
  39
  40 /*
  41  * Returns integer with first length bits reversed and all higher bits zeroed
  42  */
  43 uint16_t inline bit_reverse2(uint16_t bits, uint8_t length)
  44 {
  45         bits = ((bits >> 1) & 0x55555555) | ((bits & 0x55555555) << 1); // swap bits
  46         bits = ((bits >> 2) & 0x33333333) | ((bits & 0x33333333) << 2); // swap pairs
  47         bits = ((bits >> 4) & 0x0F0F0F0F) | ((bits & 0x0F0F0F0F) << 4); // swap nibbles
  48         bits = ((bits >> 8) & 0x00FF00FF) | ((bits & 0x00FF00FF) << 8); // swap bytes
  49         return bits >> (16 - length);
  50 }
  51
  52 void inline init_inflate_in_buffer(struct inflate_in_buffer *inflate_in)
  53 {
  54         inflate_in->read_in = 0;
  55         inflate_in->read_in_length = 0;
  56 }
  57
  58 void inline set_inflate_in_buffer(struct inflate_in_buffer *inflate_in, uint8_t * in_stream,
  59                                   uint32_t in_size)
  60 {
  61         inflate_in->next_in = inflate_in->start = in_stream;
  62         inflate_in->avail_in = in_size;
  63 }
  64
  65 void inline set_inflate_out_buffer(struct inflate_out_buffer *inflate_out,
  66                                    uint8_t * out_stream, uint32_t out_size)
  67 {
  68         inflate_out->next_out = out_stream;
  69         inflate_out->avail_out = out_size;
  70         inflate_out->total_out = 0;
  71 }
  72
  73 void inline inflate_in_clear_bits(struct inflate_in_buffer *inflate_in)
  74 {
  75         uint8_t bytes;
  76
  77         bytes = inflate_in->read_in_length / 8;
  78
  79         inflate_in->read_in = 0;
  80         inflate_in->read_in_length = 0;
  81         inflate_in->next_in -= bytes;
  82         inflate_in->avail_in += bytes;
  83 }
  84
  85 void inline inflate_in_load(struct inflate_in_buffer *inflate_in, int min_required)
  86 {
  87         uint64_t temp = 0;
  88         uint8_t new_bytes;
  89
  90         if (inflate_in->avail_in >= 8) {
  91                 /* If there is enough space to load a 64 bits, load the data and use
  92                  * that to fill read_in */
  93                 new_bytes = 8 - (inflate_in->read_in_length + 7) / 8;
  94                 temp = *(uint64_t *) inflate_in->next_in;
  95
  96                 inflate_in->read_in |= temp << inflate_in->read_in_length;
  97                 inflate_in->next_in += new_bytes;
  98                 inflate_in->avail_in -= new_bytes;
  99                 inflate_in->read_in_length += new_bytes * 8;
 100
 101         } else {
 102                 /* Else fill the read_in buffer 1 byte at a time */
 103                 while (inflate_in->read_in_length < 57 && inflate_in->avail_in > 0) {
 104                         temp = *inflate_in->next_in;
 105                         inflate_in->read_in |= temp << inflate_in->read_in_length;
 106                         inflate_in->next_in++;
 107                         inflate_in->avail_in--;
 108                         inflate_in->read_in_length += 8;
 109
 110                 }
 111         }
 112
 113 }
 114
 115 uint64_t inline inflate_in_peek_bits(struct inflate_in_buffer *inflate_in, uint8_t bit_count)
 116 {
 117         assert(bit_count < 57);
 118
 119         /* Load inflate_in if not enough data is in the read_in buffer */
 120         if (inflate_in->read_in_length < bit_count)
 121                 inflate_in_load(inflate_in, 0);
 122
 123         return (inflate_in->read_in) & ((1 << bit_count) - 1);
 124 }
 125
 126 void inline inflate_in_shift_bits(struct inflate_in_buffer *inflate_in, uint8_t bit_count)
 127 {
 128
 129         inflate_in->read_in >>= bit_count;
 130         inflate_in->read_in_length -= bit_count;
 131 }
 132
 133 uint64_t inline inflate_in_read_bits(struct inflate_in_buffer *inflate_in, uint8_t bit_count)
 134 {
 135         uint64_t ret;
 136         assert(bit_count < 57);
 137
 138         /* Load inflate_in if not enough data is in the read_in buffer */
 139         if (inflate_in->read_in_length < bit_count)
 140                 inflate_in_load(inflate_in, bit_count);
 141
 142         ret = (inflate_in->read_in) & ((1 << bit_count) - 1);
 143         inflate_in->read_in >>= bit_count;
 144         inflate_in->read_in_length -= bit_count;
 145
 146         return ret;
 147 }
 148
 149 int inline setup_static_header(struct inflate_state *state)
 150 {
 151         /* This could be turned into a memcpy of this functions output for
 152          * higher speed, but then DECODE_LOOKUP_SIZE couldn't be changed without
 153          * regenerating the table. */
 154
 155         int i;
 156         struct huff_code lit_code[LIT_LEN + 2];
 157         struct huff_code dist_code[DIST_LEN + 2];
 158
 159         /* These tables are based on the static huffman tree described in RFC
 160          * 1951 */
 161         uint16_t lit_count[16] = {
 162                 0, 0, 0, 0, 0, 0, 0, 24, 152, 112, 0, 0, 0, 0, 0, 0
 163         };
 164         uint16_t dist_count[16] = {
 165                 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
 166         };
 167
 168         /* These for loops set the code lengths for the static literal/length
 169          * and distance codes defined in the deflate standard RFC 1951 */
 170         for (i = 0; i < 144; i++)
 171                 lit_code[i].length = 8;
 172
 173         for (i = 144; i < 256; i++)
 174                 lit_code[i].length = 9;
 175
 176         for (i = 256; i < 280; i++)
 177                 lit_code[i].length = 7;
 178
 179         for (i = 280; i < LIT_LEN + 2; i++)
 180                 lit_code[i].length = 8;
 181
 182         for (i = 0; i < DIST_LEN + 2; i++)
 183                 dist_code[i].length = 5;
 184
 185         make_inflate_huff_code(&state->lit_huff_code, lit_code, LIT_LEN + 2, lit_count);
 186         make_inflate_huff_code(&state->dist_huff_code, dist_code, DIST_LEN + 2, dist_count);
 187
 188         return 0;
 189 }
 190
 191 void inline make_inflate_huff_code(struct inflate_huff_code *result,
 192                                    struct huff_code *huff_code_table, int table_length,
 193                                    uint16_t * count)
 194 {
 195         int i, j;
 196         uint16_t code = 0;
 197         uint16_t next_code[MAX_HUFF_TREE_DEPTH + 1];
 198         uint16_t long_code_list[LIT_LEN];
 199         uint32_t long_code_length = 0;
 200         uint16_t temp_code_list[1 << (15 - DECODE_LOOKUP_SIZE)];
 201         uint32_t temp_code_length;
 202         uint32_t long_code_lookup_length = 0;
 203         uint32_t max_length;
 204         uint16_t first_bits;
 205         uint32_t code_length;
 206         uint16_t long_bits;
 207         uint16_t min_increment;
 208
 209         memset(result, 0, sizeof(struct inflate_huff_code));
 210
 211         next_code[0] = code;
 212
 213         for (i = 1; i < MAX_HUFF_TREE_DEPTH + 1; i++)
 214                 next_code[i] = (next_code[i - 1] + count[i - 1]) << 1;
 215
 216         for (i = 0; i < table_length; i++) {
 217                 if (huff_code_table[i].length != 0) {
 218                         /* Determine the code for symbol i */
 219                         huff_code_table[i].code =
 220                             bit_reverse2(next_code[huff_code_table[i].length],
 221                                         huff_code_table[i].length);
 222
 223                         next_code[huff_code_table[i].length] += 1;
 224
 225                         if (huff_code_table[i].length <= DECODE_LOOKUP_SIZE) {
 226                                 /* Set lookup table to return the current symbol
 227                                  * concatenated with the code length when the
 228                                  * first DECODE_LENGTH bits of the address are
 229                                  * the same as the code for the current
 230                                  * symbol. The first 9 bits are the code, bits
 231                                  * 14:10 are the code length, bit 15 is a flag
 232                                  * representing this is a symbol*/
 233                                 for (j = 0; j < (1 << (DECODE_LOOKUP_SIZE -
 234                                                        huff_code_table[i].length)); j++)
 235
 236                                         result->small_code_lookup[(j <<
 237                                                                    huff_code_table[i].length) +
 238                                                                   huff_code_table[i].code]
 239                                             = i | (huff_code_table[i].length) << 9;
 240
 241                         } else {
 242                                 /* Store the element in a list of elements with long codes. */
 243                                 long_code_list[long_code_length] = i;
 244                                 long_code_length++;
 245                         }
 246                 }
 247         }
 248
 249         for (i = 0; i < long_code_length; i++) {
 250                 /*Set the look up table to point to a hint where the symbol can be found
 251                  * in the list of long codes and add the current symbol to the list of
 252                  * long codes. */
 253                 if (huff_code_table[long_code_list[i]].code == 0xFFFF)
 254                         continue;
 255
 256                 max_length = huff_code_table[long_code_list[i]].length;
 257                 first_bits =
 258                     huff_code_table[long_code_list[i]].code & ((1 << DECODE_LOOKUP_SIZE) - 1);
 259
 260                 temp_code_list[0] = long_code_list[i];
 261                 temp_code_length = 1;
 262
 263                 for (j = i + 1; j < long_code_length; j++) {
 264                         if ((huff_code_table[long_code_list[j]].code &
 265                              ((1 << DECODE_LOOKUP_SIZE) - 1)) == first_bits) {
 266                                 if (max_length < huff_code_table[long_code_list[j]].length)
 267                                         max_length = huff_code_table[long_code_list[j]].length;
 268                                 temp_code_list[temp_code_length] = long_code_list[j];
 269                                 temp_code_length++;
 270                         }
 271                 }
 272
 273                 for (j = 0; j < temp_code_length; j++) {
 274                         code_length = huff_code_table[temp_code_list[j]].length;
 275                         long_bits =
 276                             huff_code_table[temp_code_list[j]].code >> DECODE_LOOKUP_SIZE;
 277                         min_increment = 1 << (code_length - DECODE_LOOKUP_SIZE);
 278                         for (; long_bits < (1 << (max_length - DECODE_LOOKUP_SIZE));
 279                              long_bits += min_increment) {
 280                                 result->long_code_lookup[long_code_lookup_length + long_bits] =
 281                                     temp_code_list[j] | (code_length << 9);
 282                         }
 283                         huff_code_table[temp_code_list[j]].code = 0xFFFF;
 284                 }
 285                 result->small_code_lookup[first_bits] =
 286                     long_code_lookup_length | (max_length << 9) | 0x8000;
 287                 long_code_lookup_length += 1 << (max_length - DECODE_LOOKUP_SIZE);
 288
 289         }
 290 }
 291
 292 uint16_t inline decode_next(struct inflate_in_buffer *in_buffer,
 293                             struct inflate_huff_code *huff_code)
 294 {
 295         uint16_t next_bits;
 296         uint16_t next_sym;
 297
 298         next_bits = inflate_in_peek_bits(in_buffer, DECODE_LOOKUP_SIZE);
 299
 300         /* next_sym is a possible symbol decoded from next_bits. If bit 15 is 0,
 301          * next_code is a symbol. Bits 9:0 represent the symbol, and bits 14:10
 302          * represent the length of that symbols huffman code. If next_sym is not
 303          * a symbol, it provides a hint of where the large symbols containin
 304          * this code are located. Note the hint is at largest the location the
 305          * first actual symbol in the long code list.*/
 306         next_sym = huff_code->small_code_lookup[next_bits];
 307
 308         if (next_sym < 0x8000) {
 309                 /* Return symbol found if next_code is a complete huffman code
 310                  * and shift in buffer over by the length of the next_code */
 311                 inflate_in_shift_bits(in_buffer, next_sym >> 9);
 312
 313                 return next_sym & 0x1FF;
 314
 315         } else {
 316                 /* If a symbol is not found, perform a linear search of the long code
 317                  * list starting from the hint in next_sym */
 318                 next_bits = inflate_in_peek_bits(in_buffer, (next_sym - 0x8000) >> 9);
 319                 next_sym =
 320                     huff_code->long_code_lookup[(next_sym & 0x1FF) +
 321                                                 (next_bits >> DECODE_LOOKUP_SIZE)];
 322                 inflate_in_shift_bits(in_buffer, next_sym >> 9);
 323                 return next_sym & 0x1FF;
 324
 325         }
 326 }
 327
 328 int inline setup_dynamic_header(struct inflate_state *state)
 329 {
 330         int i, j;
 331         struct huff_code code_huff[CODE_LEN_CODES];
 332         struct huff_code lit_and_dist_huff[LIT_LEN + DIST_LEN];
 333         struct huff_code *previous = NULL, *current;
 334         struct inflate_huff_code inflate_code_huff;
 335         uint8_t hclen, hdist, hlit;
 336         uint16_t code_count[16], lit_count[16], dist_count[16];
 337         uint16_t *count;
 338         uint16_t symbol;
 339
 340         /* This order is defined in RFC 1951 page 13 */
 341         const uint8_t code_length_code_order[CODE_LEN_CODES] = {
 342                 0x10, 0x11, 0x12, 0x00, 0x08, 0x07, 0x09, 0x06,
 343                 0x0a, 0x05, 0x0b, 0x04, 0x0c, 0x03, 0x0d, 0x02,
 344                 0x0e, 0x01, 0x0f
 345         };
 346
 347         memset(code_count, 0, sizeof(code_count));
 348         memset(lit_count, 0, sizeof(lit_count));
 349         memset(dist_count, 0, sizeof(dist_count));
 350         memset(code_huff, 0, sizeof(code_huff));
 351         memset(lit_and_dist_huff, 0, sizeof(lit_and_dist_huff));
 352
 353         /* These variables are defined in the deflate standard, RFC 1951 */
 354         hlit = inflate_in_read_bits(&state->in_buffer, 5);
 355         hdist = inflate_in_read_bits(&state->in_buffer, 5);
 356         hclen = inflate_in_read_bits(&state->in_buffer, 4);
 357
 358         /* Create the code huffman code for decoding the lit/len and dist huffman codes */
 359         for (i = 0; i < hclen + 4; i++) {
 360                 code_huff[code_length_code_order[i]].length =
 361                     inflate_in_read_bits(&state->in_buffer, 3);
 362
 363                 code_count[code_huff[code_length_code_order[i]].length] += 1;
 364         }
 365
 366         if (state->in_buffer.read_in_length < 0)
 367                 return END_OF_INPUT;
 368
 369         make_inflate_huff_code(&inflate_code_huff, code_huff, CODE_LEN_CODES, code_count);
 370
 371         /* Decode the lit/len and dist huffman codes using the code huffman code */
 372         count = lit_count;
 373         current = lit_and_dist_huff;
 374
 375         while (current < lit_and_dist_huff + LIT_LEN + hdist + 1) {
 376                 /* If finished decoding the lit/len huffman code, start decoding
 377                  * the distance code these decodings are in the same loop
 378                  * because the len/lit and dist huffman codes are run length
 379                  * encoded together. */
 380                 if (current == lit_and_dist_huff + 257 + hlit)
 381                         current = lit_and_dist_huff + LIT_LEN;
 382
 383                 if (current == lit_and_dist_huff + LIT_LEN)
 384                         count = dist_count;
 385
 386                 symbol = decode_next(&state->in_buffer, &inflate_code_huff);
 387
 388                 if (state->in_buffer.read_in_length < 0)
 389                         return END_OF_INPUT;
 390
 391                 if (symbol < 16) {
 392                         /* If a length is found, update the current lit/len/dist
 393                          * to have length symbol */
 394                         count[symbol]++;
 395                         current->length = symbol;
 396                         previous = current;
 397                         current++;
 398
 399                 } else if (symbol == 16) {
 400                         /* If a repeat length is found, update the next repeat
 401                          * length lit/len/dist elements to have the value of the
 402                          * repeated length */
 403                         if (previous == NULL)   /* No elements available to be repeated */
 404                                 return INVALID_BLOCK_HEADER;
 405
 406                         i = 3 + inflate_in_read_bits(&state->in_buffer, 2);
 407                         for (j = 0; j < i; j++) {
 408                                 *current = *previous;
 409                                 count[current->length]++;
 410                                 previous = current;
 411
 412                                 if (current == lit_and_dist_huff + 256 + hlit) {
 413                                         current = lit_and_dist_huff + LIT_LEN;
 414                                         count = dist_count;
 415
 416                                 } else
 417                                         current++;
 418                         }
 419
 420                 } else if (symbol == 17) {
 421                         /* If a repeat zeroes if found, update then next
 422                          * repeated zeroes length lit/len/dist elements to have
 423                          * length 0. */
 424                         i = 3 + inflate_in_read_bits(&state->in_buffer, 3);
 425
 426                         for (j = 0; j < i; j++) {
 427                                 previous = current;
 428
 429                                 if (current == lit_and_dist_huff + 256 + hlit) {
 430                                         current = lit_and_dist_huff + LIT_LEN;
 431                                         count = dist_count;
 432
 433                                 } else
 434                                         current++;
 435                         }
 436
 437                 } else if (symbol == 18) {
 438                         /* If a repeat zeroes if found, update then next
 439                          * repeated zeroes length lit/len/dist elements to have
 440                          * length 0. */
 441                         i = 11 + inflate_in_read_bits(&state->in_buffer, 7);
 442
 443                         for (j = 0; j < i; j++) {
 444                                 previous = current;
 445
 446                                 if (current == lit_and_dist_huff + 256 + hlit) {
 447                                         current = lit_and_dist_huff + LIT_LEN;
 448                                         count = dist_count;
 449
 450                                 } else
 451                                         current++;
 452                         }
 453                 } else
 454                         return INVALID_BLOCK_HEADER;
 455
 456         }
 457
 458         if (state->in_buffer.read_in_length < 0)
 459                 return END_OF_INPUT;
 460
 461         make_inflate_huff_code(&state->lit_huff_code, lit_and_dist_huff, LIT_LEN, lit_count);
 462         make_inflate_huff_code(&state->dist_huff_code, &lit_and_dist_huff[LIT_LEN], DIST_LEN,
 463                                dist_count);
 464
 465         return 0;
 466 }
 467
 468 int read_header(struct inflate_state *state)
 469 {
 470         state->new_block = 0;
 471
 472         /* btype and bfinal are defined in RFC 1951, bfinal represents whether
 473          * the current block is the end of block, and btype represents the
 474          * encoding method on the current block. */
 475         state->bfinal = inflate_in_read_bits(&state->in_buffer, 1);
 476         state->btype = inflate_in_read_bits(&state->in_buffer, 2);
 477
 478         if (state->in_buffer.read_in_length < 0)
 479                 return END_OF_INPUT;
 480
 481         if (state->btype == 0) {
 482                 inflate_in_clear_bits(&state->in_buffer);
 483                 return 0;
 484
 485         } else if (state->btype == 1)
 486                 return setup_static_header(state);
 487
 488         else if (state->btype == 2)
 489                 return setup_dynamic_header(state);
 490
 491         return INVALID_BLOCK_HEADER;
 492 }
 493
 494 void igzip_inflate_init(struct inflate_state *state, uint8_t * in_stream, uint32_t in_size,
 495                         uint8_t * out_stream, uint64_t out_size)
 496 {
 497
 498         init_inflate_in_buffer(&state->in_buffer);
 499
 500         set_inflate_in_buffer(&state->in_buffer, in_stream, in_size);
 501         set_inflate_out_buffer(&state->out_buffer, out_stream, out_size);
 502
 503         state->new_block = 1;
 504         state->bfinal = 0;
 505 }
 506
 507 int igzip_inflate(struct inflate_state *state)
 508 {
 509         /* The following tables are based on the tables in the deflate standard,
 510          * RFC 1951 page 11. */
 511         const uint16_t len_start[29] = {
 512                 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a,
 513                 0x0b, 0x0d, 0x0f, 0x11, 0x13, 0x17, 0x1b, 0x1f,
 514                 0x23, 0x2b, 0x33, 0x3b, 0x43, 0x53, 0x63, 0x73,
 515                 0x83, 0xa3, 0xc3, 0xe3, 0x102
 516         };
 517         const uint8_t len_extra_bit_count[29] = {
 518                 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
 519                 0x1, 0x1, 0x1, 0x1, 0x2, 0x2, 0x2, 0x2,
 520                 0x3, 0x3, 0x3, 0x3, 0x4, 0x4, 0x4, 0x4,
 521                 0x5, 0x5, 0x5, 0x5, 0x0
 522         };
 523         const uint32_t dist_start[30] = {
 524                 0x0001, 0x0002, 0x0003, 0x0004, 0x0005, 0x0007, 0x0009, 0x000d,
 525                 0x0011, 0x0019, 0x0021, 0x0031, 0x0041, 0x0061, 0x0081, 0x00c1,
 526                 0x0101, 0x0181, 0x0201, 0x0301, 0x0401, 0x0601, 0x0801, 0x0c01,
 527                 0x1001, 0x1801, 0x2001, 0x3001, 0x4001, 0x6001
 528         };
 529         const uint8_t dist_extra_bit_count[30] = {
 530                 0x0, 0x0, 0x0, 0x0, 0x1, 0x1, 0x2, 0x2,
 531                 0x3, 0x3, 0x4, 0x4, 0x5, 0x5, 0x6, 0x6,
 532                 0x7, 0x7, 0x8, 0x8, 0x9, 0x9, 0xa, 0xa,
 533                 0xb, 0xb, 0xc, 0xc, 0xd, 0xd
 534         };
 535
 536         uint16_t next_lit, len, nlen;
 537         uint8_t next_dist;
 538         uint32_t repeat_length;
 539         uint32_t look_back_dist;
 540         uint32_t tmp;
 541
 542         while (state->new_block == 0 || state->bfinal == 0) {
 543                 if (state->new_block != 0) {
 544                         tmp = read_header(state);
 545
 546                         if (tmp)
 547                                 return tmp;
 548                 }
 549
 550                 if (state->btype == 0) {
 551                         /* If the block is uncompressed, perform a memcopy while
 552                          * updating state data */
 553                         if (state->in_buffer.avail_in < 4)
 554                                 return END_OF_INPUT;
 555
 556                         len = *(uint16_t *) state->in_buffer.next_in;
 557                         state->in_buffer.next_in += 2;
 558                         nlen = *(uint16_t *) state->in_buffer.next_in;
 559                         state->in_buffer.next_in += 2;
 560
 561                         /* Check if len and nlen match */
 562                         if (len != (~nlen & 0xffff))
 563                                 return INVALID_NON_COMPRESSED_BLOCK_LENGTH;
 564
 565                         if (state->out_buffer.avail_out < len)
 566                                 return OUT_BUFFER_OVERFLOW;
 567
 568                         if (state->in_buffer.avail_in < len)
 569                                 len = state->in_buffer.avail_in;
 570
 571                         else
 572                                 state->new_block = 1;
 573
 574                         memcpy(state->out_buffer.next_out, state->in_buffer.next_in, len);
 575
 576                         state->out_buffer.next_out += len;
 577                         state->out_buffer.avail_out -= len;
 578                         state->out_buffer.total_out += len;
 579                         state->in_buffer.next_in += len;
 580                         state->in_buffer.avail_in -= len + 4;
 581
 582                         if (state->in_buffer.avail_in == 0 && state->new_block == 0)
 583                                 return END_OF_INPUT;
 584
 585                 } else {
 586                         /* Else decode a huffman encoded block */
 587                         while (state->new_block == 0) {
 588                                 /* While not at the end of block, decode the next
 589                                  * symbol */
 590
 591                                 next_lit =
 592                                     decode_next(&state->in_buffer, &state->lit_huff_code);
 593
 594                                 if (state->in_buffer.read_in_length < 0)
 595                                         return END_OF_INPUT;
 596
 597                                 if (next_lit < 256) {
 598                                         /* If the next symbol is a literal,
 599                                          * write out the symbol and update state
 600                                          * data accordingly. */
 601                                         if (state->out_buffer.avail_out < 1)
 602                                                 return OUT_BUFFER_OVERFLOW;
 603
 604                                         *state->out_buffer.next_out = next_lit;
 605                                         state->out_buffer.next_out++;
 606                                         state->out_buffer.avail_out--;
 607                                         state->out_buffer.total_out++;
 608
 609                                 } else if (next_lit == 256) {
 610                                         /* If the next symbol is the end of
 611                                          * block, update the state data
 612                                          * accordingly */
 613                                         state->new_block = 1;
 614
 615                                 } else if (next_lit < 286) {
 616                                         /* Else if the next symbol is a repeat
 617                                          * length, read in the length extra
 618                                          * bits, the distance code, the distance
 619                                          * extra bits. Then write out the
 620                                          * corresponding data and update the
 621                                          * state data accordingly*/
 622                                         repeat_length =
 623                                             len_start[next_lit - 257] +
 624                                             inflate_in_read_bits(&state->in_buffer,
 625                                                                  len_extra_bit_count[next_lit -
 626                                                                                      257]);
 627
 628                                         if (state->out_buffer.avail_out < repeat_length)
 629                                                 return OUT_BUFFER_OVERFLOW;
 630
 631                                         next_dist = decode_next(&state->in_buffer,
 632                                                                 &state->dist_huff_code);
 633
 634                                         look_back_dist = dist_start[next_dist] +
 635                                             inflate_in_read_bits(&state->in_buffer,
 636                                                                  dist_extra_bit_count
 637                                                                  [next_dist]);
 638
 639                                         if (state->in_buffer.read_in_length < 0)
 640                                                 return END_OF_INPUT;
 641
 642                                         if (look_back_dist > state->out_buffer.total_out)
 643                                                 return INVALID_LOOK_BACK_DISTANCE;
 644
 645                                         if (look_back_dist > repeat_length) {
 646                                                 memcpy(state->out_buffer.next_out,
 647                                                        state->out_buffer.next_out -
 648                                                        look_back_dist, repeat_length);
 649                                         } else
 650                                                 byte_copy(state->out_buffer.next_out,
 651                                                           look_back_dist, repeat_length);
 652
 653                                         state->out_buffer.next_out += repeat_length;
 654                                         state->out_buffer.avail_out -= repeat_length;
 655                                         state->out_buffer.total_out += repeat_length;
 656
 657                                 } else
 658                                         /* Else the read in bits do not
 659                                          * correspond to any valid symbol */
 660                                         return INVALID_SYMBOL;
 661                         }
 662                 }
 663         }
 664         state->in_buffer.next_in -= state->in_buffer.read_in_length / 8;
 665         state->in_buffer.avail_in += state->in_buffer.read_in_length / 8;
 666
 667         return DECOMPRESSION_FINISHED;
 668 }