deflate.c

Go to the documentation of this file.

/*
 * 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 258, 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;
}