--- /dev/null
+/*
+ * 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;
+}
Code Review / kvmfornfv.git / blobdiff