summaryrefslogtreecommitdiffstats
path: root/qemu/roms/ipxe/src/crypto/deflate.c
diff options
context:
space:
mode:
authorRajithaY <rajithax.yerrumsetty@intel.com>2017-04-25 03:31:15 -0700
committerRajitha Yerrumchetty <rajithax.yerrumsetty@intel.com>2017-05-22 06:48:08 +0000
commitbb756eebdac6fd24e8919e2c43f7d2c8c4091f59 (patch)
treeca11e03542edf2d8f631efeca5e1626d211107e3 /qemu/roms/ipxe/src/crypto/deflate.c
parenta14b48d18a9ed03ec191cf16b162206998a895ce (diff)
Adding qemu as a submodule of KVMFORNFV
This Patch includes the changes to add qemu as a submodule to kvmfornfv repo and make use of the updated latest qemu for the execution of all testcase Change-Id: I1280af507a857675c7f81d30c95255635667bdd7 Signed-off-by:RajithaY<rajithax.yerrumsetty@intel.com>
Diffstat (limited to 'qemu/roms/ipxe/src/crypto/deflate.c')
-rw-r--r--qemu/roms/ipxe/src/crypto/deflate.c1049
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;
-}