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