diff options
Diffstat (limited to 'qemu/roms/ipxe/src/crypto/deflate.c')
| -rw-r--r-- | qemu/roms/ipxe/src/crypto/deflate.c | 1049 |
1 files changed, 0 insertions, 1049 deletions
diff --git a/qemu/roms/ipxe/src/crypto/deflate.c b/qemu/roms/ipxe/src/crypto/deflate.c deleted file mode 100644 index e1c87d5fe..000000000 --- a/qemu/roms/ipxe/src/crypto/deflate.c +++ /dev/null @@ -1,1049 +0,0 @@ -/* - * 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. - * - * 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 <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; -} |