diff options
Diffstat (limited to 'roms/ipxe/src/crypto/deflate.c')
| -rw-r--r-- | roms/ipxe/src/crypto/deflate.c | 1045 |
1 files changed, 1045 insertions, 0 deletions
diff --git a/roms/ipxe/src/crypto/deflate.c b/roms/ipxe/src/crypto/deflate.c new file mode 100644 index 00000000..91a48996 --- /dev/null +++ b/roms/ipxe/src/crypto/deflate.c @@ -0,0 +1,1045 @@ +/* + * Copyright (C) 2014 Michael Brown <mbrown@fensystems.co.uk>. + * + * 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. + */ + +FILE_LICENCE ( GPL2_OR_LATER ); + +#include <string.h> +#include <strings.h> +#include <errno.h> +#include <assert.h> +#include <ctype.h> +#include <ipxe/uaccess.h> +#include <ipxe/deflate.h> + +/** @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 "<UNKNOWN>"; + } +} + +/** + * 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; +} |