/* * Copyright (C) 2014 Michael Brown . * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License as * published by the Free Software Foundation; either version 2 of the * License, or any later version. * * This program is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA * 02110-1301, USA. * * You can also choose to distribute this program under the terms of * the Unmodified Binary Distribution Licence (as given in the file * COPYING.UBDL), provided that you have satisfied its requirements. */ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); #include #include #include #include #include #include #include /** @file * * DEFLATE decompression algorithm * * This file implements the decompression half of the DEFLATE * algorithm specified in RFC 1951. * * Portions of this code are derived from wimboot's xca.c. * */ /** * Byte reversal table * * For some insane reason, the DEFLATE format stores some values in * bit-reversed order. */ static uint8_t deflate_reverse[256]; /** Literal/length base values * * We include entries only for literal/length codes 257-284. Code 285 * does not fit the pattern (it represents a length of 258; following * the pattern from the earlier codes would give a length of 259), and * has no extra bits. Codes 286-287 are invalid, but can occur. We * treat any code greater than 284 as meaning "length 285, no extra * bits". */ static uint8_t deflate_litlen_base[28]; /** Distance base values * * We include entries for all possible codes 0-31, avoiding the need * to check for undefined codes 30 and 31 before performing the * lookup. Codes 30 and 31 are never initialised, and will therefore * be treated as meaning "14 extra bits, base distance 0". */ static uint16_t deflate_distance_base[32]; /** Code length map */ static uint8_t deflate_codelen_map[19] = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 }; /** Static Huffman alphabet length patterns */ static struct deflate_static_length_pattern deflate_static_length_patterns[] = { /* Literal/length code lengths */ { 0x88, ( ( ( 143 - 0 ) + 1 ) / 2 ) }, { 0x99, ( ( ( 255 - 144 ) + 1 ) / 2 ) }, { 0x77, ( ( ( 279 - 256 ) + 1 ) / 2 ) }, { 0x88, ( ( ( 287 - 280 ) + 1 ) / 2 ) }, /* Distance code lengths */ { 0x55, ( ( ( 31 - 0 ) + 1 ) / 2 ) }, /* End marker */ { 0, 0 } }; /** * Transcribe binary value (for debugging) * * @v value Value * @v bits Length of value (in bits) * @ret string Transcribed value */ static const char * deflate_bin ( unsigned long value, unsigned int bits ) { static char buf[ ( 8 * sizeof ( value ) ) + 1 /* NUL */ ]; char *out = buf; /* Sanity check */ assert ( bits < sizeof ( buf ) ); /* Transcribe value */ while ( bits-- ) *(out++) = ( ( value & ( 1 << bits ) ) ? '1' : '0' ); *out = '\0'; return buf; } /** * Set Huffman symbol length * * @v deflate Decompressor * @v index Index within lengths * @v bits Symbol length (in bits) */ static void deflate_set_length ( struct deflate *deflate, unsigned int index, unsigned int bits ) { deflate->lengths[ index / 2 ] |= ( bits << ( 4 * ( index % 2 ) ) ); } /** * Get Huffman symbol length * * @v deflate Decompressor * @v index Index within lengths * @ret bits Symbol length (in bits) */ static unsigned int deflate_length ( struct deflate *deflate, unsigned int index ) { return ( ( deflate->lengths[ index / 2 ] >> ( 4 * ( index % 2 ) ) ) & 0x0f ); } /** * Determine Huffman alphabet name (for debugging) * * @v deflate Decompressor * @v alphabet Huffman alphabet * @ret name Alphabet name */ static const char * deflate_alphabet_name ( struct deflate *deflate, struct deflate_alphabet *alphabet ){ if ( alphabet == &deflate->litlen ) { return "litlen"; } else if ( alphabet == &deflate->distance_codelen ) { return "distance/codelen"; } else { return ""; } } /** * Dump Huffman alphabet (for debugging) * * @v deflate Decompressor * @v alphabet Huffman alphabet */ static void deflate_dump_alphabet ( struct deflate *deflate, struct deflate_alphabet *alphabet ) { struct deflate_huf_symbols *huf_sym; unsigned int bits; unsigned int huf; unsigned int i; /* Do nothing unless debugging is enabled */ if ( ! DBG_EXTRA ) return; /* Dump symbol table for each utilised length */ for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) / sizeof ( alphabet->huf[0] ) ) ; bits++ ) { huf_sym = &alphabet->huf[ bits - 1 ]; if ( huf_sym->freq == 0 ) continue; huf = ( huf_sym->start >> huf_sym->shift ); DBGC2 ( alphabet, "DEFLATE %p \"%s\" length %d start \"%s\" " "freq %d:", deflate, deflate_alphabet_name ( deflate, alphabet ), bits, deflate_bin ( huf, huf_sym->bits ), huf_sym->freq ); for ( i = 0 ; i < huf_sym->freq ; i++ ) { DBGC2 ( alphabet, " %03x", huf_sym->raw[ huf + i ] ); } DBGC2 ( alphabet, "\n" ); } /* Dump quick lookup table */ DBGC2 ( alphabet, "DEFLATE %p \"%s\" quick lookup:", deflate, deflate_alphabet_name ( deflate, alphabet ) ); for ( i = 0 ; i < ( sizeof ( alphabet->lookup ) / sizeof ( alphabet->lookup[0] ) ) ; i++ ) { DBGC2 ( alphabet, " %d", ( alphabet->lookup[i] + 1 ) ); } DBGC2 ( alphabet, "\n" ); } /** * Construct Huffman alphabet * * @v deflate Decompressor * @v alphabet Huffman alphabet * @v count Number of symbols * @v offset Starting offset within length table * @ret rc Return status code */ static int deflate_alphabet ( struct deflate *deflate, struct deflate_alphabet *alphabet, unsigned int count, unsigned int offset ) { struct deflate_huf_symbols *huf_sym; unsigned int huf; unsigned int cum_freq; unsigned int bits; unsigned int raw; unsigned int adjustment; unsigned int prefix; int complete; /* Clear symbol table */ memset ( alphabet->huf, 0, sizeof ( alphabet->huf ) ); /* Count number of symbols with each Huffman-coded length */ for ( raw = 0 ; raw < count ; raw++ ) { bits = deflate_length ( deflate, ( raw + offset ) ); if ( bits ) alphabet->huf[ bits - 1 ].freq++; } /* Populate Huffman-coded symbol table */ huf = 0; cum_freq = 0; for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) / sizeof ( alphabet->huf[0] ) ) ; bits++ ) { huf_sym = &alphabet->huf[ bits - 1 ]; huf_sym->bits = bits; huf_sym->shift = ( 16 - bits ); huf_sym->start = ( huf << huf_sym->shift ); huf_sym->raw = &alphabet->raw[cum_freq]; huf += huf_sym->freq; if ( huf > ( 1U << bits ) ) { DBGC ( alphabet, "DEFLATE %p \"%s\" has too many " "symbols with lengths <=%d\n", deflate, deflate_alphabet_name ( deflate, alphabet ), bits ); return -EINVAL; } huf <<= 1; cum_freq += huf_sym->freq; } complete = ( huf == ( 1U << bits ) ); /* Populate raw symbol table */ for ( raw = 0 ; raw < count ; raw++ ) { bits = deflate_length ( deflate, ( raw + offset ) ); if ( bits ) { huf_sym = &alphabet->huf[ bits - 1 ]; *(huf_sym->raw++) = raw; } } /* Adjust Huffman-coded symbol table raw pointers and populate * quick lookup table. */ for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) / sizeof ( alphabet->huf[0] ) ) ; bits++ ) { huf_sym = &alphabet->huf[ bits - 1 ]; /* Adjust raw pointer */ huf_sym->raw -= huf_sym->freq; /* Reset to first symbol */ adjustment = ( huf_sym->start >> huf_sym->shift ); huf_sym->raw -= adjustment; /* Adjust for quick indexing */ /* Populate quick lookup table */ for ( prefix = ( huf_sym->start >> DEFLATE_HUFFMAN_QL_SHIFT ) ; prefix < ( 1 << DEFLATE_HUFFMAN_QL_BITS ) ; prefix++ ) { alphabet->lookup[prefix] = ( bits - 1 ); } } /* Dump alphabet (for debugging) */ deflate_dump_alphabet ( deflate, alphabet ); /* Check that there are no invalid codes */ if ( ! complete ) { DBGC ( alphabet, "DEFLATE %p \"%s\" is incomplete\n", deflate, deflate_alphabet_name ( deflate, alphabet ) ); return -EINVAL; } return 0; } /** * Attempt to accumulate bits from input stream * * @v deflate Decompressor * @v in Compressed input data * @v target Number of bits to accumulate * @ret excess Number of excess bits accumulated (may be negative) */ static int deflate_accumulate ( struct deflate *deflate, struct deflate_chunk *in, unsigned int target ) { uint8_t byte; while ( deflate->bits < target ) { /* Check for end of input */ if ( in->offset >= in->len ) break; /* Acquire byte from input */ copy_from_user ( &byte, in->data, in->offset++, sizeof ( byte ) ); deflate->accumulator = ( deflate->accumulator | ( byte << deflate->bits ) ); deflate->rotalumucca = ( deflate->rotalumucca | ( deflate_reverse[byte] << ( 24 - deflate->bits ) ) ); deflate->bits += 8; /* Sanity check */ assert ( deflate->bits <= ( 8 * sizeof ( deflate->accumulator ) ) ); } return ( deflate->bits - target ); } /** * Consume accumulated bits from the input stream * * @v deflate Decompressor * @v count Number of accumulated bits to consume * @ret data Consumed bits */ static int deflate_consume ( struct deflate *deflate, unsigned int count ) { int data; /* Sanity check */ assert ( count <= deflate->bits ); /* Extract data and consume bits */ data = ( deflate->accumulator & ( ( 1 << count ) - 1 ) ); deflate->accumulator >>= count; deflate->rotalumucca <<= count; deflate->bits -= count; return data; } /** * Attempt to extract a fixed number of bits from input stream * * @v deflate Decompressor * @v in Compressed input data * @v target Number of bits to extract * @ret data Extracted bits (or negative if not yet accumulated) */ static int deflate_extract ( struct deflate *deflate, struct deflate_chunk *in, unsigned int target ) { int excess; int data; /* Return immediately if we are attempting to extract zero bits */ if ( target == 0 ) return 0; /* Attempt to accumulate bits */ excess = deflate_accumulate ( deflate, in, target ); if ( excess < 0 ) return excess; /* Extract data and consume bits */ data = deflate_consume ( deflate, target ); DBGCP ( deflate, "DEFLATE %p extracted %s = %#x = %d\n", deflate, deflate_bin ( data, target ), data, data ); return data; } /** * Attempt to decode a Huffman-coded symbol from input stream * * @v deflate Decompressor * @v in Compressed input data * @v alphabet Huffman alphabet * @ret code Raw code (or negative if not yet accumulated) */ static int deflate_decode ( struct deflate *deflate, struct deflate_chunk *in, struct deflate_alphabet *alphabet ) { struct deflate_huf_symbols *huf_sym; uint16_t huf; unsigned int lookup_index; int excess; unsigned int raw; /* Attempt to accumulate maximum required number of bits. * There may be fewer bits than this remaining in the stream, * even if the stream still contains some complete * Huffman-coded symbols. */ deflate_accumulate ( deflate, in, DEFLATE_HUFFMAN_BITS ); /* Normalise the bit-reversed accumulated value to 16 bits */ huf = ( deflate->rotalumucca >> 16 ); /* Find symbol set for this length */ lookup_index = ( huf >> DEFLATE_HUFFMAN_QL_SHIFT ); huf_sym = &alphabet->huf[ alphabet->lookup[ lookup_index ] ]; while ( huf < huf_sym->start ) huf_sym--; /* Calculate number of excess bits, and return if not yet complete */ excess = ( deflate->bits - huf_sym->bits ); if ( excess < 0 ) return excess; /* Consume bits */ deflate_consume ( deflate, huf_sym->bits ); /* Look up raw symbol */ raw = huf_sym->raw[ huf >> huf_sym->shift ]; DBGCP ( deflate, "DEFLATE %p decoded %s = %#x = %d\n", deflate, deflate_bin ( ( huf >> huf_sym->shift ), huf_sym->bits ), raw, raw ); return raw; } /** * Discard bits up to the next byte boundary * * @v deflate Decompressor */ static void deflate_discard_to_byte ( struct deflate *deflate ) { deflate_consume ( deflate, ( deflate->bits & 7 ) ); } /** * Copy data to output buffer (if available) * * @v out Output data buffer * @v start Source data * @v offset Starting offset within source data * @v len Length to copy */ static void deflate_copy ( struct deflate_chunk *out, userptr_t start, size_t offset, size_t len ) { size_t out_offset = out->offset; size_t copy_len; /* Copy data one byte at a time, to allow for overlap */ if ( out_offset < out->len ) { copy_len = ( out->len - out_offset ); if ( copy_len > len ) copy_len = len; while ( copy_len-- ) { memcpy_user ( out->data, out_offset++, start, offset++, 1 ); } } out->offset += len; } /** * Inflate compressed data * * @v deflate Decompressor * @v in Compressed input data * @v out Output data buffer * @ret rc Return status code * * The caller can use deflate_finished() to determine whether a * successful return indicates that the decompressor is merely waiting * for more input. * * Data will not be written beyond the specified end of the output * data buffer, but the offset within the output data buffer will be * updated to reflect the amount that should have been written. The * caller can use this to find the length of the decompressed data * before allocating the output data buffer. */ int deflate_inflate ( struct deflate *deflate, struct deflate_chunk *in, struct deflate_chunk *out ) { /* This could be implemented more neatly if gcc offered a * means for enforcing tail recursion. */ if ( deflate->resume ) { goto *(deflate->resume); } else switch ( deflate->format ) { case DEFLATE_RAW: goto block_header; case DEFLATE_ZLIB: goto zlib_header; default: assert ( 0 ); } zlib_header: { int header; int cm; /* Extract header */ header = deflate_extract ( deflate, in, ZLIB_HEADER_BITS ); if ( header < 0 ) { deflate->resume = &&zlib_header; return 0; } /* Parse header */ cm = ( ( header >> ZLIB_HEADER_CM_LSB ) & ZLIB_HEADER_CM_MASK ); if ( cm != ZLIB_HEADER_CM_DEFLATE ) { DBGC ( deflate, "DEFLATE %p unsupported ZLIB " "compression method %d\n", deflate, cm ); return -ENOTSUP; } if ( header & ( 1 << ZLIB_HEADER_FDICT_BIT ) ) { DBGC ( deflate, "DEFLATE %p unsupported ZLIB preset " "dictionary\n", deflate ); return -ENOTSUP; } /* Process first block header */ goto block_header; } block_header: { int header; int bfinal; int btype; /* Extract block header */ header = deflate_extract ( deflate, in, DEFLATE_HEADER_BITS ); if ( header < 0 ) { deflate->resume = &&block_header; return 0; } /* Parse header */ deflate->header = header; bfinal = ( header & ( 1 << DEFLATE_HEADER_BFINAL_BIT ) ); btype = ( header >> DEFLATE_HEADER_BTYPE_LSB ); DBGC ( deflate, "DEFLATE %p found %sblock type %#x\n", deflate, ( bfinal ? "final " : "" ), btype ); switch ( btype ) { case DEFLATE_HEADER_BTYPE_LITERAL: goto literal_block; case DEFLATE_HEADER_BTYPE_STATIC: goto static_block; case DEFLATE_HEADER_BTYPE_DYNAMIC: goto dynamic_block; default: DBGC ( deflate, "DEFLATE %p unsupported block type " "%#x\n", deflate, btype ); return -ENOTSUP; } } literal_block: { /* Discard any bits up to the next byte boundary */ deflate_discard_to_byte ( deflate ); } literal_len: { int len; /* Extract LEN field */ len = deflate_extract ( deflate, in, DEFLATE_LITERAL_LEN_BITS ); if ( len < 0 ) { deflate->resume = &&literal_len; return 0; } /* Record length of literal data */ deflate->remaining = len; DBGC2 ( deflate, "DEFLATE %p literal block length %#04zx\n", deflate, deflate->remaining ); } literal_nlen: { int nlen; /* Extract NLEN field */ nlen = deflate_extract ( deflate, in, DEFLATE_LITERAL_LEN_BITS); if ( nlen < 0 ) { deflate->resume = &&literal_nlen; return 0; } /* Verify NLEN */ if ( ( ( deflate->remaining ^ ~nlen ) & ( ( 1 << DEFLATE_LITERAL_LEN_BITS ) - 1 ) ) != 0 ) { DBGC ( deflate, "DEFLATE %p invalid len/nlen " "%#04zx/%#04x\n", deflate, deflate->remaining, nlen ); return -EINVAL; } } literal_data: { size_t in_remaining; size_t len; /* Calculate available amount of literal data */ in_remaining = ( in->len - in->offset ); len = deflate->remaining; if ( len > in_remaining ) len = in_remaining; /* Copy data to output buffer */ deflate_copy ( out, in->data, in->offset, len ); /* Consume data from input buffer */ in->offset += len; deflate->remaining -= len; /* Finish processing if we are blocked */ if ( deflate->remaining ) { deflate->resume = &&literal_data; return 0; } /* Otherwise, finish block */ goto block_done; } static_block: { struct deflate_static_length_pattern *pattern; uint8_t *lengths = deflate->lengths; /* Construct static Huffman lengths as per RFC 1950 */ for ( pattern = deflate_static_length_patterns ; pattern->count ; pattern++ ) { memset ( lengths, pattern->fill, pattern->count ); lengths += pattern->count; } deflate->litlen_count = 288; deflate->distance_count = 32; goto construct_alphabets; } dynamic_block: dynamic_header: { int header; unsigned int hlit; unsigned int hdist; unsigned int hclen; /* Extract block header */ header = deflate_extract ( deflate, in, DEFLATE_DYNAMIC_BITS ); if ( header < 0 ) { deflate->resume = &&dynamic_header; return 0; } /* Parse header */ hlit = ( ( header >> DEFLATE_DYNAMIC_HLIT_LSB ) & DEFLATE_DYNAMIC_HLIT_MASK ); hdist = ( ( header >> DEFLATE_DYNAMIC_HDIST_LSB ) & DEFLATE_DYNAMIC_HDIST_MASK ); hclen = ( ( header >> DEFLATE_DYNAMIC_HCLEN_LSB ) & DEFLATE_DYNAMIC_HCLEN_MASK ); deflate->litlen_count = ( hlit + 257 ); deflate->distance_count = ( hdist + 1 ); deflate->length_index = 0; deflate->length_target = ( hclen + 4 ); DBGC2 ( deflate, "DEFLATE %p dynamic block %d codelen, %d " "litlen, %d distance\n", deflate, deflate->length_target, deflate->litlen_count, deflate->distance_count ); /* Prepare for decoding code length code lengths */ memset ( &deflate->lengths, 0, sizeof ( deflate->lengths ) ); } dynamic_codelen: { int len; unsigned int index; int rc; /* Extract all code lengths */ while ( deflate->length_index < deflate->length_target ) { /* Extract code length length */ len = deflate_extract ( deflate, in, DEFLATE_CODELEN_BITS ); if ( len < 0 ) { deflate->resume = &&dynamic_codelen; return 0; } /* Store code length */ index = deflate_codelen_map[deflate->length_index++]; deflate_set_length ( deflate, index, len ); DBGCP ( deflate, "DEFLATE %p codelen for %d is %d\n", deflate, index, len ); } /* Generate code length alphabet */ if ( ( rc = deflate_alphabet ( deflate, &deflate->distance_codelen, ( DEFLATE_CODELEN_MAX_CODE + 1 ), 0 ) ) != 0 ) return rc; /* Prepare for decoding literal/length/distance code lengths */ memset ( &deflate->lengths, 0, sizeof ( deflate->lengths ) ); deflate->length_index = 0; deflate->length_target = ( deflate->litlen_count + deflate->distance_count ); deflate->length = 0; } dynamic_litlen_distance: { int len; int index; /* Decode literal/length/distance code length */ len = deflate_decode ( deflate, in, &deflate->distance_codelen); if ( len < 0 ) { deflate->resume = &&dynamic_litlen_distance; return 0; } /* Prepare for extra bits */ if ( len < 16 ) { deflate->length = len; deflate->extra_bits = 0; deflate->dup_len = 1; } else { static const uint8_t dup_len[3] = { 3, 3, 11 }; static const uint8_t extra_bits[3] = { 2, 3, 7 }; index = ( len - 16 ); deflate->dup_len = dup_len[index]; deflate->extra_bits = extra_bits[index]; if ( index ) deflate->length = 0; } } dynamic_litlen_distance_extra: { int extra; unsigned int dup_len; /* Extract extra bits */ extra = deflate_extract ( deflate, in, deflate->extra_bits ); if ( extra < 0 ) { deflate->resume = &&dynamic_litlen_distance_extra; return 0; } /* Store code lengths */ dup_len = ( deflate->dup_len + extra ); while ( ( deflate->length_index < deflate->length_target ) && dup_len-- ) { deflate_set_length ( deflate, deflate->length_index++, deflate->length ); } /* Process next literal/length or distance code * length, if more are required. */ if ( deflate->length_index < deflate->length_target ) goto dynamic_litlen_distance; /* Construct alphabets */ goto construct_alphabets; } construct_alphabets: { unsigned int distance_offset = deflate->litlen_count; unsigned int distance_count = deflate->distance_count; int rc; /* Generate literal/length alphabet */ if ( ( rc = deflate_alphabet ( deflate, &deflate->litlen, deflate->litlen_count, 0 ) ) !=0) return rc; /* Handle degenerate case of a single distance code * (for which it is impossible to construct a valid, * complete Huffman alphabet). RFC 1951 states: * * If only one distance code is used, it is encoded * using one bit, not zero bits; in this case there * is a single code length of one, with one unused * code. One distance code of zero bits means that * there are no distance codes used at all (the data * is all literals). * * If we have only a single distance code, then we * instead use two distance codes both with length 1. * This results in a valid Huffman alphabet. The code * "0" will mean distance code 0 (which is either * correct or irrelevant), and the code "1" will mean * distance code 1 (which is always irrelevant). */ if ( deflate->distance_count == 1 ) { deflate->lengths[0] = 0x11; distance_offset = 0; distance_count = 2; } /* Generate distance alphabet */ if ( ( rc = deflate_alphabet ( deflate, &deflate->distance_codelen, distance_count, distance_offset ) ) != 0 ) return rc; } lzhuf_litlen: { int code; uint8_t byte; unsigned int extra; unsigned int bits; /* Decode Huffman codes */ while ( 1 ) { /* Decode Huffman code */ code = deflate_decode ( deflate, in, &deflate->litlen ); if ( code < 0 ) { deflate->resume = &&lzhuf_litlen; return 0; } /* Handle according to code type */ if ( code < DEFLATE_LITLEN_END ) { /* Literal value: copy to output buffer */ byte = code; DBGCP ( deflate, "DEFLATE %p literal %#02x " "('%c')\n", deflate, byte, ( isprint ( byte ) ? byte : '.' ) ); deflate_copy ( out, virt_to_user ( &byte ), 0, sizeof ( byte ) ); } else if ( code == DEFLATE_LITLEN_END ) { /* End of block */ goto block_done; } else { /* Length code: process extra bits */ extra = ( code - DEFLATE_LITLEN_END - 1 ); if ( extra < 28 ) { bits = ( extra / 4 ); if ( bits ) bits--; deflate->extra_bits = bits; deflate->dup_len = deflate_litlen_base[extra]; } else { deflate->extra_bits = 0; deflate->dup_len = 258; } goto lzhuf_litlen_extra; } } } lzhuf_litlen_extra: { int extra; /* Extract extra bits */ extra = deflate_extract ( deflate, in, deflate->extra_bits ); if ( extra < 0 ) { deflate->resume = &&lzhuf_litlen_extra; return 0; } /* Update duplicate length */ deflate->dup_len += extra; } lzhuf_distance: { int code; unsigned int extra; unsigned int bits; /* Decode Huffman code */ code = deflate_decode ( deflate, in, &deflate->distance_codelen ); if ( code < 0 ) { deflate->resume = &&lzhuf_distance; return 0; } /* Process extra bits */ extra = code; bits = ( extra / 2 ); if ( bits ) bits--; deflate->extra_bits = bits; deflate->dup_distance = deflate_distance_base[extra]; } lzhuf_distance_extra: { int extra; size_t dup_len; size_t dup_distance; /* Extract extra bits */ extra = deflate_extract ( deflate, in, deflate->extra_bits ); if ( extra < 0 ) { deflate->resume = &&lzhuf_distance_extra; return 0; } /* Update duplicate distance */ dup_distance = ( deflate->dup_distance + extra ); dup_len = deflate->dup_len; DBGCP ( deflate, "DEFLATE %p duplicate length %zd distance " "%zd\n", deflate, dup_len, dup_distance ); /* Sanity check */ if ( dup_distance > out->offset ) { DBGC ( deflate, "DEFLATE %p bad distance %zd (max " "%zd)\n", deflate, dup_distance, out->offset ); return -EINVAL; } /* Copy data, allowing for overlap */ deflate_copy ( out, out->data, ( out->offset - dup_distance ), dup_len ); /* Process next literal/length symbol */ goto lzhuf_litlen; } block_done: { DBGCP ( deflate, "DEFLATE %p end of block\n", deflate ); /* If this was not the final block, process next block header */ if ( ! ( deflate->header & ( 1 << DEFLATE_HEADER_BFINAL_BIT ) )) goto block_header; /* Otherwise, process footer (if any) */ switch ( deflate->format ) { case DEFLATE_RAW: goto finished; case DEFLATE_ZLIB: goto zlib_footer; default: assert ( 0 ); } } zlib_footer: { /* Discard any bits up to the next byte boundary */ deflate_discard_to_byte ( deflate ); } zlib_adler32: { int excess; /* Accumulate the 32 bits of checksum. We don't check * the value, stop processing immediately afterwards, * and so don't have to worry about the nasty corner * cases involved in calling deflate_extract() to * obtain a full 32 bits. */ excess = deflate_accumulate ( deflate, in, ZLIB_ADLER32_BITS ); if ( excess < 0 ) { deflate->resume = &&zlib_adler32; return 0; } /* Finish processing */ goto finished; } finished: { /* Mark as finished and terminate */ DBGCP ( deflate, "DEFLATE %p finished\n", deflate ); deflate->resume = NULL; return 0; } } /** * Initialise decompressor * * @v deflate Decompressor * @v format Compression format code */ void deflate_init ( struct deflate *deflate, enum deflate_format format ) { static int global_init_done; uint8_t i; uint8_t bit; uint8_t byte; unsigned int base; unsigned int bits; /* Perform global initialisation if required */ if ( ! global_init_done ) { /* Initialise byte reversal table */ for ( i = 255 ; i ; i-- ) { for ( bit = 1, byte = 0 ; bit ; bit <<= 1 ) { byte <<= 1; if ( i & bit ) byte |= 1; } deflate_reverse[i] = byte; } /* Initialise literal/length extra bits table */ base = 3; for ( i = 0 ; i < 28 ; i++ ) { bits = ( i / 4 ); if ( bits ) bits--; deflate_litlen_base[i] = base; base += ( 1 << bits ); } assert ( base == 259 ); /* sic */ /* Initialise distance extra bits table */ base = 1; for ( i = 0 ; i < 30 ; i++ ) { bits = ( i / 2 ); if ( bits ) bits--; deflate_distance_base[i] = base; base += ( 1 << bits ); } assert ( base == 32769 ); /* Record global initialisation as complete */ global_init_done = 1; } /* Initialise structure */ memset ( deflate, 0, sizeof ( *deflate ) ); deflate->format = format; }