qemu/roms/ipxe/src/crypto/deflate.c

   1 /*
   2  * Copyright (C) 2014 Michael Brown <mbrown@fensystems.co.uk>.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License as
   6  * published by the Free Software Foundation; either version 2 of the
   7  * License, or any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  17  * 02110-1301, USA.
  18  */
  19
  20 FILE_LICENCE ( GPL2_OR_LATER );
  21
  22 #include <string.h>
  23 #include <strings.h>
  24 #include <errno.h>
  25 #include <assert.h>
  26 #include <ctype.h>
  27 #include <ipxe/uaccess.h>
  28 #include <ipxe/deflate.h>
  29
  30 /** @file
  31  *
  32  * DEFLATE decompression algorithm
  33  *
  34  * This file implements the decompression half of the DEFLATE
  35  * algorithm specified in RFC 1951.
  36  *
  37  * Portions of this code are derived from wimboot's xca.c.
  38  *
  39  */
  40
  41 /**
  42  * Byte reversal table
  43  *
  44  * For some insane reason, the DEFLATE format stores some values in
  45  * bit-reversed order.
  46  */
  47 static uint8_t deflate_reverse[256];
  48
  49 /** Literal/length base values
  50  *
  51  * We include entries only for literal/length codes 257-284.  Code 285
  52  * does not fit the pattern (it represents a length of 258; following
  53  * the pattern from the earlier codes would give a length of 259), and
  54  * has no extra bits.  Codes 286-287 are invalid, but can occur.  We
  55  * treat any code greater than 284 as meaning "length 285, no extra
  56  * bits".
  57  */
  58 static uint8_t deflate_litlen_base[28];
  59
  60 /** Distance base values
  61  *
  62  * We include entries for all possible codes 0-31, avoiding the need
  63  * to check for undefined codes 30 and 31 before performing the
  64  * lookup.  Codes 30 and 31 are never initialised, and will therefore
  65  * be treated as meaning "14 extra bits, base distance 0".
  66  */
  67 static uint16_t deflate_distance_base[32];
  68
  69 /** Code length map */
  70 static uint8_t deflate_codelen_map[19] = {
  71         16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
  72 };
  73
  74 /** Static Huffman alphabet length patterns */
  75 static struct deflate_static_length_pattern deflate_static_length_patterns[] = {
  76         /* Literal/length code lengths */
  77         { 0x88, ( ( ( 143 -   0 ) + 1 ) / 2 ) },
  78         { 0x99, ( ( ( 255 - 144 ) + 1 ) / 2 ) },
  79         { 0x77, ( ( ( 279 - 256 ) + 1 ) / 2 ) },
  80         { 0x88, ( ( ( 287 - 280 ) + 1 ) / 2 ) },
  81         /* Distance code lengths */
  82         { 0x55, ( ( (  31 -   0 ) + 1 ) / 2 ) },
  83         /* End marker */
  84         { 0, 0 }
  85 };
  86
  87 /**
  88  * Transcribe binary value (for debugging)
  89  *
  90  * @v value             Value
  91  * @v bits              Length of value (in bits)
  92  * @ret string          Transcribed value
  93  */
  94 static const char * deflate_bin ( unsigned long value, unsigned int bits ) {
  95         static char buf[ ( 8 * sizeof ( value ) ) + 1 /* NUL */ ];
  96         char *out = buf;
  97
  98         /* Sanity check */
  99         assert ( bits < sizeof ( buf ) );
 100
 101         /* Transcribe value */
 102         while ( bits-- )
 103                 *(out++) = ( ( value & ( 1 << bits ) ) ? '1' : '0' );
 104         *out = '\0';
 105
 106         return buf;
 107 }
 108
 109 /**
 110  * Set Huffman symbol length
 111  *
 112  * @v deflate           Decompressor
 113  * @v index             Index within lengths
 114  * @v bits              Symbol length (in bits)
 115  */
 116 static void deflate_set_length ( struct deflate *deflate, unsigned int index,
 117                                  unsigned int bits ) {
 118
 119         deflate->lengths[ index / 2 ] |= ( bits << ( 4 * ( index % 2 ) ) );
 120 }
 121
 122 /**
 123  * Get Huffman symbol length
 124  *
 125  * @v deflate           Decompressor
 126  * @v index             Index within lengths
 127  * @ret bits            Symbol length (in bits)
 128  */
 129 static unsigned int deflate_length ( struct deflate *deflate,
 130                                      unsigned int index ) {
 131
 132         return ( ( deflate->lengths[ index / 2 ] >> ( 4 * ( index % 2 ) ) )
 133                  & 0x0f );
 134 }
 135
 136 /**
 137  * Determine Huffman alphabet name (for debugging)
 138  *
 139  * @v deflate           Decompressor
 140  * @v alphabet          Huffman alphabet
 141  * @ret name            Alphabet name
 142  */
 143 static const char * deflate_alphabet_name ( struct deflate *deflate,
 144                                             struct deflate_alphabet *alphabet ){
 145
 146         if ( alphabet == &deflate->litlen ) {
 147                 return "litlen";
 148         } else if ( alphabet == &deflate->distance_codelen ) {
 149                 return "distance/codelen";
 150         } else {
 151                 return "<UNKNOWN>";
 152         }
 153 }
 154
 155 /**
 156  * Dump Huffman alphabet (for debugging)
 157  *
 158  * @v deflate           Decompressor
 159  * @v alphabet          Huffman alphabet
 160  */
 161 static void deflate_dump_alphabet ( struct deflate *deflate,
 162                                     struct deflate_alphabet *alphabet ) {
 163         struct deflate_huf_symbols *huf_sym;
 164         unsigned int bits;
 165         unsigned int huf;
 166         unsigned int i;
 167
 168         /* Do nothing unless debugging is enabled */
 169         if ( ! DBG_EXTRA )
 170                 return;
 171
 172         /* Dump symbol table for each utilised length */
 173         for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
 174                                    sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
 175                 huf_sym = &alphabet->huf[ bits - 1 ];
 176                 if ( huf_sym->freq == 0 )
 177                         continue;
 178                 huf = ( huf_sym->start >> huf_sym->shift );
 179                 DBGC2 ( alphabet, "DEFLATE %p \"%s\" length %d start \"%s\" "
 180                         "freq %d:", deflate,
 181                         deflate_alphabet_name ( deflate, alphabet ), bits,
 182                         deflate_bin ( huf, huf_sym->bits ), huf_sym->freq );
 183                 for ( i = 0 ; i < huf_sym->freq ; i++ ) {
 184                         DBGC2 ( alphabet, " %03x",
 185                                 huf_sym->raw[ huf + i ] );
 186                 }
 187                 DBGC2 ( alphabet, "\n" );
 188         }
 189
 190         /* Dump quick lookup table */
 191         DBGC2 ( alphabet, "DEFLATE %p \"%s\" quick lookup:", deflate,
 192                 deflate_alphabet_name ( deflate, alphabet ) );
 193         for ( i = 0 ; i < ( sizeof ( alphabet->lookup ) /
 194                             sizeof ( alphabet->lookup[0] ) ) ; i++ ) {
 195                 DBGC2 ( alphabet, " %d", ( alphabet->lookup[i] + 1 ) );
 196         }
 197         DBGC2 ( alphabet, "\n" );
 198 }
 199
 200 /**
 201  * Construct Huffman alphabet
 202  *
 203  * @v deflate           Decompressor
 204  * @v alphabet          Huffman alphabet
 205  * @v count             Number of symbols
 206  * @v offset            Starting offset within length table
 207  * @ret rc              Return status code
 208  */
 209 static int deflate_alphabet ( struct deflate *deflate,
 210                               struct deflate_alphabet *alphabet,
 211                               unsigned int count, unsigned int offset ) {
 212         struct deflate_huf_symbols *huf_sym;
 213         unsigned int huf;
 214         unsigned int cum_freq;
 215         unsigned int bits;
 216         unsigned int raw;
 217         unsigned int adjustment;
 218         unsigned int prefix;
 219         int complete;
 220
 221         /* Clear symbol table */
 222         memset ( alphabet->huf, 0, sizeof ( alphabet->huf ) );
 223
 224         /* Count number of symbols with each Huffman-coded length */
 225         for ( raw = 0 ; raw < count ; raw++ ) {
 226                 bits = deflate_length ( deflate, ( raw + offset ) );
 227                 if ( bits )
 228                         alphabet->huf[ bits - 1 ].freq++;
 229         }
 230
 231         /* Populate Huffman-coded symbol table */
 232         huf = 0;
 233         cum_freq = 0;
 234         for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
 235                                    sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
 236                 huf_sym = &alphabet->huf[ bits - 1 ];
 237                 huf_sym->bits = bits;
 238                 huf_sym->shift = ( 16 - bits );
 239                 huf_sym->start = ( huf << huf_sym->shift );
 240                 huf_sym->raw = &alphabet->raw[cum_freq];
 241                 huf += huf_sym->freq;
 242                 if ( huf > ( 1U << bits ) ) {
 243                         DBGC ( alphabet, "DEFLATE %p \"%s\" has too many "
 244                                "symbols with lengths <=%d\n", deflate,
 245                                deflate_alphabet_name ( deflate, alphabet ),
 246                                bits );
 247                         return -EINVAL;
 248                 }
 249                 huf <<= 1;
 250                 cum_freq += huf_sym->freq;
 251         }
 252         complete = ( huf == ( 1U << bits ) );
 253
 254         /* Populate raw symbol table */
 255         for ( raw = 0 ; raw < count ; raw++ ) {
 256                 bits = deflate_length ( deflate, ( raw + offset ) );
 257                 if ( bits ) {
 258                         huf_sym = &alphabet->huf[ bits - 1 ];
 259                         *(huf_sym->raw++) = raw;
 260                 }
 261         }
 262
 263         /* Adjust Huffman-coded symbol table raw pointers and populate
 264          * quick lookup table.
 265          */
 266         for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
 267                                    sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
 268                 huf_sym = &alphabet->huf[ bits - 1 ];
 269
 270                 /* Adjust raw pointer */
 271                 huf_sym->raw -= huf_sym->freq; /* Reset to first symbol */
 272                 adjustment = ( huf_sym->start >> huf_sym->shift );
 273                 huf_sym->raw -= adjustment; /* Adjust for quick indexing */
 274
 275                 /* Populate quick lookup table */
 276                 for ( prefix = ( huf_sym->start >> DEFLATE_HUFFMAN_QL_SHIFT ) ;
 277                       prefix < ( 1 << DEFLATE_HUFFMAN_QL_BITS ) ; prefix++ ) {
 278                         alphabet->lookup[prefix] = ( bits - 1 );
 279                 }
 280         }
 281
 282         /* Dump alphabet (for debugging) */
 283         deflate_dump_alphabet ( deflate, alphabet );
 284
 285         /* Check that there are no invalid codes */
 286         if ( ! complete ) {
 287                 DBGC ( alphabet, "DEFLATE %p \"%s\" is incomplete\n", deflate,
 288                        deflate_alphabet_name ( deflate, alphabet ) );
 289                 return -EINVAL;
 290         }
 291
 292         return 0;
 293 }
 294
 295 /**
 296  * Attempt to accumulate bits from input stream
 297  *
 298  * @v deflate           Decompressor
 299  * @v in                Compressed input data
 300  * @v target            Number of bits to accumulate
 301  * @ret excess          Number of excess bits accumulated (may be negative)
 302  */
 303 static int deflate_accumulate ( struct deflate *deflate,
 304                                 struct deflate_chunk *in,
 305                                 unsigned int target ) {
 306         uint8_t byte;
 307
 308         while ( deflate->bits < target ) {
 309
 310                 /* Check for end of input */
 311                 if ( in->offset >= in->len )
 312                         break;
 313
 314                 /* Acquire byte from input */
 315                 copy_from_user ( &byte, in->data, in->offset++,
 316                                  sizeof ( byte ) );
 317                 deflate->accumulator = ( deflate->accumulator |
 318                                          ( byte << deflate->bits ) );
 319                 deflate->rotalumucca = ( deflate->rotalumucca |
 320                                          ( deflate_reverse[byte] <<
 321                                            ( 24 - deflate->bits ) ) );
 322                 deflate->bits += 8;
 323
 324                 /* Sanity check */
 325                 assert ( deflate->bits <=
 326                          ( 8 * sizeof ( deflate->accumulator ) ) );
 327         }
 328
 329         return ( deflate->bits - target );
 330 }
 331
 332 /**
 333  * Consume accumulated bits from the input stream
 334  *
 335  * @v deflate           Decompressor
 336  * @v count             Number of accumulated bits to consume
 337  * @ret data            Consumed bits
 338  */
 339 static int deflate_consume ( struct deflate *deflate, unsigned int count ) {
 340         int data;
 341
 342         /* Sanity check */
 343         assert ( count <= deflate->bits );
 344
 345         /* Extract data and consume bits */
 346         data = ( deflate->accumulator & ( ( 1 << count ) - 1 ) );
 347         deflate->accumulator >>= count;
 348         deflate->rotalumucca <<= count;
 349         deflate->bits -= count;
 350
 351         return data;
 352 }
 353
 354 /**
 355  * Attempt to extract a fixed number of bits from input stream
 356  *
 357  * @v deflate           Decompressor
 358  * @v in                Compressed input data
 359  * @v target            Number of bits to extract
 360  * @ret data            Extracted bits (or negative if not yet accumulated)
 361  */
 362 static int deflate_extract ( struct deflate *deflate, struct deflate_chunk *in,
 363                              unsigned int target ) {
 364         int excess;
 365         int data;
 366
 367         /* Return immediately if we are attempting to extract zero bits */
 368         if ( target == 0 )
 369                 return 0;
 370
 371         /* Attempt to accumulate bits */
 372         excess = deflate_accumulate ( deflate, in, target );
 373         if ( excess < 0 )
 374                 return excess;
 375
 376         /* Extract data and consume bits */
 377         data = deflate_consume ( deflate, target );
 378         DBGCP ( deflate, "DEFLATE %p extracted %s = %#x = %d\n", deflate,
 379                 deflate_bin ( data, target ), data, data );
 380
 381         return data;
 382 }
 383
 384 /**
 385  * Attempt to decode a Huffman-coded symbol from input stream
 386  *
 387  * @v deflate           Decompressor
 388  * @v in                Compressed input data
 389  * @v alphabet          Huffman alphabet
 390  * @ret code            Raw code (or negative if not yet accumulated)
 391  */
 392 static int deflate_decode ( struct deflate *deflate,
 393                             struct deflate_chunk *in,
 394                             struct deflate_alphabet *alphabet ) {
 395         struct deflate_huf_symbols *huf_sym;
 396         uint16_t huf;
 397         unsigned int lookup_index;
 398         int excess;
 399         unsigned int raw;
 400
 401         /* Attempt to accumulate maximum required number of bits.
 402          * There may be fewer bits than this remaining in the stream,
 403          * even if the stream still contains some complete
 404          * Huffman-coded symbols.
 405          */
 406         deflate_accumulate ( deflate, in, DEFLATE_HUFFMAN_BITS );
 407
 408         /* Normalise the bit-reversed accumulated value to 16 bits */
 409         huf = ( deflate->rotalumucca >> 16 );
 410
 411         /* Find symbol set for this length */
 412         lookup_index = ( huf >> DEFLATE_HUFFMAN_QL_SHIFT );
 413         huf_sym = &alphabet->huf[ alphabet->lookup[ lookup_index ] ];
 414         while ( huf < huf_sym->start )
 415                 huf_sym--;
 416
 417         /* Calculate number of excess bits, and return if not yet complete */
 418         excess = ( deflate->bits - huf_sym->bits );
 419         if ( excess < 0 )
 420                 return excess;
 421
 422         /* Consume bits */
 423         deflate_consume ( deflate, huf_sym->bits );
 424
 425         /* Look up raw symbol */
 426         raw = huf_sym->raw[ huf >> huf_sym->shift ];
 427         DBGCP ( deflate, "DEFLATE %p decoded %s = %#x = %d\n", deflate,
 428                 deflate_bin ( ( huf >> huf_sym->shift ), huf_sym->bits ),
 429                 raw, raw );
 430
 431         return raw;
 432 }
 433
 434 /**
 435  * Discard bits up to the next byte boundary
 436  *
 437  * @v deflate           Decompressor
 438  */
 439 static void deflate_discard_to_byte ( struct deflate *deflate ) {
 440
 441         deflate_consume ( deflate, ( deflate->bits & 7 ) );
 442 }
 443
 444 /**
 445  * Copy data to output buffer (if available)
 446  *
 447  * @v out               Output data buffer
 448  * @v start             Source data
 449  * @v offset            Starting offset within source data
 450  * @v len               Length to copy
 451  */
 452 static void deflate_copy ( struct deflate_chunk *out,
 453                            userptr_t start, size_t offset, size_t len ) {
 454         size_t out_offset = out->offset;
 455         size_t copy_len;
 456
 457         /* Copy data one byte at a time, to allow for overlap */
 458         if ( out_offset < out->len ) {
 459                 copy_len = ( out->len - out_offset );
 460                 if ( copy_len > len )
 461                         copy_len = len;
 462                 while ( copy_len-- ) {
 463                         memcpy_user ( out->data, out_offset++,
 464                                       start, offset++, 1 );
 465                 }
 466         }
 467         out->offset += len;
 468 }
 469
 470 /**
 471  * Inflate compressed data
 472  *
 473  * @v deflate           Decompressor
 474  * @v in                Compressed input data
 475  * @v out               Output data buffer
 476  * @ret rc              Return status code
 477  *
 478  * The caller can use deflate_finished() to determine whether a
 479  * successful return indicates that the decompressor is merely waiting
 480  * for more input.
 481  *
 482  * Data will not be written beyond the specified end of the output
 483  * data buffer, but the offset within the output data buffer will be
 484  * updated to reflect the amount that should have been written.  The
 485  * caller can use this to find the length of the decompressed data
 486  * before allocating the output data buffer.
 487  */
 488 int deflate_inflate ( struct deflate *deflate,
 489                       struct deflate_chunk *in,
 490                       struct deflate_chunk *out ) {
 491
 492         /* This could be implemented more neatly if gcc offered a
 493          * means for enforcing tail recursion.
 494          */
 495         if ( deflate->resume ) {
 496                 goto *(deflate->resume);
 497         } else switch ( deflate->format ) {
 498                 case DEFLATE_RAW:       goto block_header;
 499                 case DEFLATE_ZLIB:      goto zlib_header;
 500                 default:                assert ( 0 );
 501         }
 502
 503  zlib_header: {
 504                 int header;
 505                 int cm;
 506
 507                 /* Extract header */
 508                 header = deflate_extract ( deflate, in, ZLIB_HEADER_BITS );
 509                 if ( header < 0 ) {
 510                         deflate->resume = &&zlib_header;
 511                         return 0;
 512                 }
 513
 514                 /* Parse header */
 515                 cm = ( ( header >> ZLIB_HEADER_CM_LSB ) & ZLIB_HEADER_CM_MASK );
 516                 if ( cm != ZLIB_HEADER_CM_DEFLATE ) {
 517                         DBGC ( deflate, "DEFLATE %p unsupported ZLIB "
 518                                "compression method %d\n", deflate, cm );
 519                         return -ENOTSUP;
 520                 }
 521                 if ( header & ( 1 << ZLIB_HEADER_FDICT_BIT ) ) {
 522                         DBGC ( deflate, "DEFLATE %p unsupported ZLIB preset "
 523                                "dictionary\n", deflate );
 524                         return -ENOTSUP;
 525                 }
 526
 527                 /* Process first block header */
 528                 goto block_header;
 529         }
 530
 531  block_header: {
 532                 int header;
 533                 int bfinal;
 534                 int btype;
 535
 536                 /* Extract block header */
 537                 header = deflate_extract ( deflate, in, DEFLATE_HEADER_BITS );
 538                 if ( header < 0 ) {
 539                         deflate->resume = &&block_header;
 540                         return 0;
 541                 }
 542
 543                 /* Parse header */
 544                 deflate->header = header;
 545                 bfinal = ( header & ( 1 << DEFLATE_HEADER_BFINAL_BIT ) );
 546                 btype = ( header >> DEFLATE_HEADER_BTYPE_LSB );
 547                 DBGC ( deflate, "DEFLATE %p found %sblock type %#x\n",
 548                        deflate, ( bfinal ? "final " : "" ), btype );
 549                 switch ( btype ) {
 550                 case DEFLATE_HEADER_BTYPE_LITERAL:
 551                         goto literal_block;
 552                 case DEFLATE_HEADER_BTYPE_STATIC:
 553                         goto static_block;
 554                 case DEFLATE_HEADER_BTYPE_DYNAMIC:
 555                         goto dynamic_block;
 556                 default:
 557                         DBGC ( deflate, "DEFLATE %p unsupported block type "
 558                                "%#x\n", deflate, btype );
 559                         return -ENOTSUP;
 560                 }
 561         }
 562
 563  literal_block: {
 564
 565                 /* Discard any bits up to the next byte boundary */
 566                 deflate_discard_to_byte ( deflate );
 567         }
 568
 569  literal_len: {
 570                 int len;
 571
 572                 /* Extract LEN field */
 573                 len = deflate_extract ( deflate, in, DEFLATE_LITERAL_LEN_BITS );
 574                 if ( len < 0 ) {
 575                         deflate->resume = &&literal_len;
 576                         return 0;
 577                 }
 578
 579                 /* Record length of literal data */
 580                 deflate->remaining = len;
 581                 DBGC2 ( deflate, "DEFLATE %p literal block length %#04zx\n",
 582                         deflate, deflate->remaining );
 583         }
 584
 585  literal_nlen: {
 586                 int nlen;
 587
 588                 /* Extract NLEN field */
 589                 nlen = deflate_extract ( deflate, in, DEFLATE_LITERAL_LEN_BITS);
 590                 if ( nlen < 0 ) {
 591                         deflate->resume = &&literal_nlen;
 592                         return 0;
 593                 }
 594
 595                 /* Verify NLEN */
 596                 if ( ( ( deflate->remaining ^ ~nlen ) &
 597                        ( ( 1 << DEFLATE_LITERAL_LEN_BITS ) - 1 ) ) != 0 ) {
 598                         DBGC ( deflate, "DEFLATE %p invalid len/nlen "
 599                                "%#04zx/%#04x\n", deflate,
 600                                deflate->remaining, nlen );
 601                         return -EINVAL;
 602                 }
 603         }
 604
 605  literal_data: {
 606                 size_t in_remaining;
 607                 size_t len;
 608
 609                 /* Calculate available amount of literal data */
 610                 in_remaining = ( in->len - in->offset );
 611                 len = deflate->remaining;
 612                 if ( len > in_remaining )
 613                         len = in_remaining;
 614
 615                 /* Copy data to output buffer */
 616                 deflate_copy ( out, in->data, in->offset, len );
 617
 618                 /* Consume data from input buffer */
 619                 in->offset += len;
 620                 deflate->remaining -= len;
 621
 622                 /* Finish processing if we are blocked */
 623                 if ( deflate->remaining ) {
 624                         deflate->resume = &&literal_data;
 625                         return 0;
 626                 }
 627
 628                 /* Otherwise, finish block */
 629                 goto block_done;
 630         }
 631
 632  static_block: {
 633                 struct deflate_static_length_pattern *pattern;
 634                 uint8_t *lengths = deflate->lengths;
 635
 636                 /* Construct static Huffman lengths as per RFC 1950 */
 637                 for ( pattern = deflate_static_length_patterns ;
 638                       pattern->count ; pattern++ ) {
 639                         memset ( lengths, pattern->fill, pattern->count );
 640                         lengths += pattern->count;
 641                 }
 642                 deflate->litlen_count = 288;
 643                 deflate->distance_count = 32;
 644                 goto construct_alphabets;
 645         }
 646
 647  dynamic_block:
 648
 649  dynamic_header: {
 650                 int header;
 651                 unsigned int hlit;
 652                 unsigned int hdist;
 653                 unsigned int hclen;
 654
 655                 /* Extract block header */
 656                 header = deflate_extract ( deflate, in, DEFLATE_DYNAMIC_BITS );
 657                 if ( header < 0 ) {
 658                         deflate->resume = &&dynamic_header;
 659                         return 0;
 660                 }
 661
 662                 /* Parse header */
 663                 hlit = ( ( header >> DEFLATE_DYNAMIC_HLIT_LSB ) &
 664                          DEFLATE_DYNAMIC_HLIT_MASK );
 665                 hdist = ( ( header >> DEFLATE_DYNAMIC_HDIST_LSB ) &
 666                           DEFLATE_DYNAMIC_HDIST_MASK );
 667                 hclen = ( ( header >> DEFLATE_DYNAMIC_HCLEN_LSB ) &
 668                           DEFLATE_DYNAMIC_HCLEN_MASK );
 669                 deflate->litlen_count = ( hlit + 257 );
 670                 deflate->distance_count = ( hdist + 1 );
 671                 deflate->length_index = 0;
 672                 deflate->length_target = ( hclen + 4 );
 673                 DBGC2 ( deflate, "DEFLATE %p dynamic block %d codelen, %d "
 674                         "litlen, %d distance\n", deflate,
 675                         deflate->length_target, deflate->litlen_count,
 676                         deflate->distance_count );
 677
 678                 /* Prepare for decoding code length code lengths */
 679                 memset ( &deflate->lengths, 0, sizeof ( deflate->lengths ) );
 680         }
 681
 682  dynamic_codelen: {
 683                 int len;
 684                 unsigned int index;
 685                 int rc;
 686
 687                 /* Extract all code lengths */
 688                 while ( deflate->length_index < deflate->length_target ) {
 689
 690                         /* Extract code length length */
 691                         len = deflate_extract ( deflate, in,
 692                                                 DEFLATE_CODELEN_BITS );
 693                         if ( len < 0 ) {
 694                                 deflate->resume = &&dynamic_codelen;
 695                                 return 0;
 696                         }
 697
 698                         /* Store code length */
 699                         index = deflate_codelen_map[deflate->length_index++];
 700                         deflate_set_length ( deflate, index, len );
 701                         DBGCP ( deflate, "DEFLATE %p codelen for %d is %d\n",
 702                                 deflate, index, len );
 703                 }
 704
 705                 /* Generate code length alphabet */
 706                 if ( ( rc = deflate_alphabet ( deflate,
 707                                                &deflate->distance_codelen,
 708                                                ( DEFLATE_CODELEN_MAX_CODE + 1 ),
 709                                                0 ) ) != 0 )
 710                         return rc;
 711
 712                 /* Prepare for decoding literal/length/distance code lengths */
 713                 memset ( &deflate->lengths, 0, sizeof ( deflate->lengths ) );
 714                 deflate->length_index = 0;
 715                 deflate->length_target = ( deflate->litlen_count +
 716                                            deflate->distance_count );
 717                 deflate->length = 0;
 718         }
 719
 720  dynamic_litlen_distance: {
 721                 int len;
 722                 int index;
 723
 724                 /* Decode literal/length/distance code length */
 725                 len = deflate_decode ( deflate, in, &deflate->distance_codelen);
 726                 if ( len < 0 ) {
 727                         deflate->resume = &&dynamic_litlen_distance;
 728                         return 0;
 729                 }
 730
 731                 /* Prepare for extra bits */
 732                 if ( len < 16 ) {
 733                         deflate->length = len;
 734                         deflate->extra_bits = 0;
 735                         deflate->dup_len = 1;
 736                 } else {
 737                         static const uint8_t dup_len[3] = { 3, 3, 11 };
 738                         static const uint8_t extra_bits[3] = { 2, 3, 7 };
 739                         index = ( len - 16 );
 740                         deflate->dup_len = dup_len[index];
 741                         deflate->extra_bits = extra_bits[index];
 742                         if ( index )
 743                                 deflate->length = 0;
 744                 }
 745         }
 746
 747  dynamic_litlen_distance_extra: {
 748                 int extra;
 749                 unsigned int dup_len;
 750
 751                 /* Extract extra bits */
 752                 extra = deflate_extract ( deflate, in, deflate->extra_bits );
 753                 if ( extra < 0 ) {
 754                         deflate->resume = &&dynamic_litlen_distance_extra;
 755                         return 0;
 756                 }
 757
 758                 /* Store code lengths */
 759                 dup_len = ( deflate->dup_len + extra );
 760                 while ( ( deflate->length_index < deflate->length_target ) &&
 761                         dup_len-- ) {
 762                         deflate_set_length ( deflate, deflate->length_index++,
 763                                              deflate->length );
 764                 }
 765
 766                 /* Process next literal/length or distance code
 767                  * length, if more are required.
 768                  */
 769                 if ( deflate->length_index < deflate->length_target )
 770                         goto dynamic_litlen_distance;
 771
 772                 /* Construct alphabets */
 773                 goto construct_alphabets;
 774         }
 775
 776  construct_alphabets: {
 777                 unsigned int distance_offset = deflate->litlen_count;
 778                 unsigned int distance_count = deflate->distance_count;
 779                 int rc;
 780
 781                 /* Generate literal/length alphabet */
 782                 if ( ( rc = deflate_alphabet ( deflate, &deflate->litlen,
 783                                                deflate->litlen_count, 0 ) ) !=0)
 784                         return rc;
 785
 786                 /* Handle degenerate case of a single distance code
 787                  * (for which it is impossible to construct a valid,
 788                  * complete Huffman alphabet).  RFC 1951 states:
 789                  *
 790                  *   If only one distance code is used, it is encoded
 791                  *   using one bit, not zero bits; in this case there
 792                  *   is a single code length of one, with one unused
 793                  *   code.  One distance code of zero bits means that
 794                  *   there are no distance codes used at all (the data
 795                  *   is all literals).
 796                  *
 797                  * If we have only a single distance code, then we
 798                  * instead use two distance codes both with length 1.
 799                  * This results in a valid Huffman alphabet.  The code
 800                  * "0" will mean distance code 0 (which is either
 801                  * correct or irrelevant), and the code "1" will mean
 802                  * distance code 1 (which is always irrelevant).
 803                  */
 804                 if ( deflate->distance_count == 1 ) {
 805
 806                         deflate->lengths[0] = 0x11;
 807                         distance_offset = 0;
 808                         distance_count = 2;
 809                 }
 810
 811                 /* Generate distance alphabet */
 812                 if ( ( rc = deflate_alphabet ( deflate,
 813                                                &deflate->distance_codelen,
 814                                                distance_count,
 815                                                distance_offset ) ) != 0 )
 816                         return rc;
 817         }
 818
 819  lzhuf_litlen: {
 820                 int code;
 821                 uint8_t byte;
 822                 unsigned int extra;
 823                 unsigned int bits;
 824
 825                 /* Decode Huffman codes */
 826                 while ( 1 ) {
 827
 828                         /* Decode Huffman code */
 829                         code = deflate_decode ( deflate, in, &deflate->litlen );
 830                         if ( code < 0 ) {
 831                                 deflate->resume = &&lzhuf_litlen;
 832                                 return 0;
 833                         }
 834
 835                         /* Handle according to code type */
 836                         if ( code < DEFLATE_LITLEN_END ) {
 837
 838                                 /* Literal value: copy to output buffer */
 839                                 byte = code;
 840                                 DBGCP ( deflate, "DEFLATE %p literal %#02x "
 841                                         "('%c')\n", deflate, byte,
 842                                         ( isprint ( byte ) ? byte : '.' ) );
 843                                 deflate_copy ( out, virt_to_user ( &byte ), 0,
 844                                                sizeof ( byte ) );
 845
 846                         } else if ( code == DEFLATE_LITLEN_END ) {
 847
 848                                 /* End of block */
 849                                 goto block_done;
 850
 851                         } else {
 852
 853                                 /* Length code: process extra bits */
 854                                 extra = ( code - DEFLATE_LITLEN_END - 1 );
 855                                 if ( extra < 28 ) {
 856                                         bits = ( extra / 4 );
 857                                         if ( bits )
 858                                                 bits--;
 859                                         deflate->extra_bits = bits;
 860                                         deflate->dup_len =
 861                                                 deflate_litlen_base[extra];
 862                                 } else {
 863                                         deflate->extra_bits = 0;
 864                                         deflate->dup_len = 258;
 865                                 }
 866                                 goto lzhuf_litlen_extra;
 867                         }
 868                 }
 869         }
 870
 871  lzhuf_litlen_extra: {
 872                 int extra;
 873
 874                 /* Extract extra bits */
 875                 extra = deflate_extract ( deflate, in, deflate->extra_bits );
 876                 if ( extra < 0 ) {
 877                         deflate->resume = &&lzhuf_litlen_extra;
 878                         return 0;
 879                 }
 880
 881                 /* Update duplicate length */
 882                 deflate->dup_len += extra;
 883         }
 884
 885  lzhuf_distance: {
 886                 int code;
 887                 unsigned int extra;
 888                 unsigned int bits;
 889
 890                 /* Decode Huffman code */
 891                 code = deflate_decode ( deflate, in,
 892                                         &deflate->distance_codelen );
 893                 if ( code < 0 ) {
 894                         deflate->resume = &&lzhuf_distance;
 895                         return 0;
 896                 }
 897
 898                 /* Process extra bits */
 899                 extra = code;
 900                 bits = ( extra / 2 );
 901                 if ( bits )
 902                         bits--;
 903                 deflate->extra_bits = bits;
 904                 deflate->dup_distance = deflate_distance_base[extra];
 905         }
 906
 907  lzhuf_distance_extra: {
 908                 int extra;
 909                 size_t dup_len;
 910                 size_t dup_distance;
 911
 912                 /* Extract extra bits */
 913                 extra = deflate_extract ( deflate, in, deflate->extra_bits );
 914                 if ( extra < 0 ) {
 915                         deflate->resume = &&lzhuf_distance_extra;
 916                         return 0;
 917                 }
 918
 919                 /* Update duplicate distance */
 920                 dup_distance = ( deflate->dup_distance + extra );
 921                 dup_len = deflate->dup_len;
 922                 DBGCP ( deflate, "DEFLATE %p duplicate length %zd distance "
 923                         "%zd\n", deflate, dup_len, dup_distance );
 924
 925                 /* Sanity check */
 926                 if ( dup_distance > out->offset ) {
 927                         DBGC ( deflate, "DEFLATE %p bad distance %zd (max "
 928                                "%zd)\n", deflate, dup_distance, out->offset );
 929                         return -EINVAL;
 930                 }
 931
 932                 /* Copy data, allowing for overlap */
 933                 deflate_copy ( out, out->data, ( out->offset - dup_distance ),
 934                                dup_len );
 935
 936                 /* Process next literal/length symbol */
 937                 goto lzhuf_litlen;
 938         }
 939
 940  block_done: {
 941
 942                 DBGCP ( deflate, "DEFLATE %p end of block\n", deflate );
 943
 944                 /* If this was not the final block, process next block header */
 945                 if ( ! ( deflate->header & ( 1 << DEFLATE_HEADER_BFINAL_BIT ) ))
 946                         goto block_header;
 947
 948                 /* Otherwise, process footer (if any) */
 949                 switch ( deflate->format ) {
 950                 case DEFLATE_RAW:       goto finished;
 951                 case DEFLATE_ZLIB:      goto zlib_footer;
 952                 default:                assert ( 0 );
 953                 }
 954         }
 955
 956  zlib_footer: {
 957
 958                 /* Discard any bits up to the next byte boundary */
 959                 deflate_discard_to_byte ( deflate );
 960         }
 961
 962  zlib_adler32: {
 963                 int excess;
 964
 965                 /* Accumulate the 32 bits of checksum.  We don't check
 966                  * the value, stop processing immediately afterwards,
 967                  * and so don't have to worry about the nasty corner
 968                  * cases involved in calling deflate_extract() to
 969                  * obtain a full 32 bits.
 970                  */
 971                 excess = deflate_accumulate ( deflate, in, ZLIB_ADLER32_BITS );
 972                 if ( excess < 0 ) {
 973                         deflate->resume = &&zlib_adler32;
 974                         return 0;
 975                 }
 976
 977                 /* Finish processing */
 978                 goto finished;
 979         }
 980
 981  finished: {
 982                 /* Mark as finished and terminate */
 983                 DBGCP ( deflate, "DEFLATE %p finished\n", deflate );
 984                 deflate->resume = NULL;
 985                 return 0;
 986         }
 987 }
 988
 989 /**
 990  * Initialise decompressor
 991  *
 992  * @v deflate           Decompressor
 993  * @v format            Compression format code
 994  */
 995 void deflate_init ( struct deflate *deflate, enum deflate_format format ) {
 996         static int global_init_done;
 997         uint8_t i;
 998         uint8_t bit;
 999         uint8_t byte;
1000         unsigned int base;
1001         unsigned int bits;
1002
1003         /* Perform global initialisation if required */
1004         if ( ! global_init_done ) {
1005
1006                 /* Initialise byte reversal table */
1007                 for ( i = 255 ; i ; i-- ) {
1008                         for ( bit = 1, byte = 0 ; bit ; bit <<= 1 ) {
1009                                 byte <<= 1;
1010                                 if ( i & bit )
1011                                         byte |= 1;
1012                         }
1013                         deflate_reverse[i] = byte;
1014                 }
1015
1016                 /* Initialise literal/length extra bits table */
1017                 base = 3;
1018                 for ( i = 0 ; i < 28 ; i++ ) {
1019                         bits = ( i / 4 );
1020                         if ( bits )
1021                                 bits--;
1022                         deflate_litlen_base[i] = base;
1023                         base += ( 1 << bits );
1024                 }
1025                 assert ( base == 259 ); /* sic */
1026
1027                 /* Initialise distance extra bits table */
1028                 base = 1;
1029                 for ( i = 0 ; i < 30 ; i++ ) {
1030                         bits = ( i / 2 );
1031                         if ( bits )
1032                                 bits--;
1033                         deflate_distance_base[i] = base;
1034                         base += ( 1 << bits );
1035                 }
1036                 assert ( base == 32769 );
1037
1038                 /* Record global initialisation as complete */
1039                 global_init_done = 1;
1040         }
1041
1042         /* Initialise structure */
1043         memset ( deflate, 0, sizeof ( *deflate ) );
1044         deflate->format = format;
1045 }