iPXE
Functions | Variables
deflate.c File Reference

DEFLATE decompression algorithm. More...

#include <string.h>
#include <strings.h>
#include <errno.h>
#include <assert.h>
#include <ctype.h>
#include <ipxe/uaccess.h>
#include <ipxe/deflate.h>

Go to the source code of this file.

Functions

 FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
static const char * deflate_bin (unsigned long value, unsigned int bits)
 Transcribe binary value (for debugging)
static void deflate_set_length (struct deflate *deflate, unsigned int index, unsigned int bits)
 Set Huffman symbol length.
static unsigned int deflate_length (struct deflate *deflate, unsigned int index)
 Get Huffman symbol length.
static const char * deflate_alphabet_name (struct deflate *deflate, struct deflate_alphabet *alphabet)
 Determine Huffman alphabet name (for debugging)
static void deflate_dump_alphabet (struct deflate *deflate, struct deflate_alphabet *alphabet)
 Dump Huffman alphabet (for debugging)
static int deflate_alphabet (struct deflate *deflate, struct deflate_alphabet *alphabet, unsigned int count, unsigned int offset)
 Construct Huffman alphabet.
static int deflate_accumulate (struct deflate *deflate, struct deflate_chunk *in, unsigned int target)
 Attempt to accumulate bits from input stream.
static int deflate_consume (struct deflate *deflate, unsigned int count)
 Consume accumulated bits from the input stream.
static int deflate_extract (struct deflate *deflate, struct deflate_chunk *in, unsigned int target)
 Attempt to extract a fixed number of bits from input stream.
static int deflate_decode (struct deflate *deflate, struct deflate_chunk *in, struct deflate_alphabet *alphabet)
 Attempt to decode a Huffman-coded symbol from input stream.
static void deflate_discard_to_byte (struct deflate *deflate)
 Discard bits up to the next byte boundary.
static void deflate_copy (struct deflate_chunk *out, userptr_t start, size_t offset, size_t len)
 Copy data to output buffer (if available)
int deflate_inflate (struct deflate *deflate, struct deflate_chunk *in, struct deflate_chunk *out)
 Inflate compressed data.
void deflate_init (struct deflate *deflate, enum deflate_format format)
 Initialise decompressor.

Variables

static uint8_t deflate_reverse [256]
 Byte reversal table.
static uint8_t deflate_litlen_base [28]
 Literal/length base values.
static uint16_t deflate_distance_base [32]
 Distance base values.
static uint8_t deflate_codelen_map [19]
 Code length map.
static struct
deflate_static_length_pattern 
deflate_static_length_patterns []
 Static Huffman alphabet length patterns.

Detailed Description

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.

Definition in file deflate.c.


Function Documentation

FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL  )
static const char* deflate_bin ( unsigned long  value,
unsigned int  bits 
) [static]

Transcribe binary value (for debugging)

Parameters:
valueValue
bitsLength of value (in bits)
Return values:
stringTranscribed value

Definition at line 98 of file deflate.c.

References assert, out, and value.

Referenced by deflate_decode(), deflate_dump_alphabet(), and deflate_extract().

                                                                           {
        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;
}
static void deflate_set_length ( struct deflate deflate,
unsigned int  index,
unsigned int  bits 
) [static]

Set Huffman symbol length.

Parameters:
deflateDecompressor
indexIndex within lengths
bitsSymbol length (in bits)

Definition at line 120 of file deflate.c.

References deflate::lengths.

Referenced by deflate_inflate().

                                                     {

        deflate->lengths[ index / 2 ] |= ( bits << ( 4 * ( index % 2 ) ) );
}
static unsigned int deflate_length ( struct deflate deflate,
unsigned int  index 
) [static]

Get Huffman symbol length.

Parameters:
deflateDecompressor
indexIndex within lengths
Return values:
bitsSymbol length (in bits)

Definition at line 133 of file deflate.c.

References deflate::lengths.

Referenced by deflate_alphabet().

                                                          {

        return ( ( deflate->lengths[ index / 2 ] >> ( 4 * ( index % 2 ) ) )
                 & 0x0f );
}
static const char* deflate_alphabet_name ( struct deflate deflate,
struct deflate_alphabet alphabet 
) [static]

Determine Huffman alphabet name (for debugging)

Parameters:
deflateDecompressor
alphabetHuffman alphabet
Return values:
nameAlphabet name

Definition at line 147 of file deflate.c.

References deflate::distance_codelen, and deflate::litlen.

Referenced by deflate_alphabet(), and deflate_dump_alphabet().

                                                                               {

        if ( alphabet == &deflate->litlen ) {
                return "litlen";
        } else if ( alphabet == &deflate->distance_codelen ) {
                return "distance/codelen";
        } else {
                return "<UNKNOWN>";
        }
}
static void deflate_dump_alphabet ( struct deflate deflate,
struct deflate_alphabet alphabet 
) [static]

Dump Huffman alphabet (for debugging)

Parameters:
deflateDecompressor
alphabetHuffman alphabet

Definition at line 165 of file deflate.c.

References deflate_huf_symbols::bits, DBG_EXTRA, DBGC2, deflate_alphabet_name(), deflate_bin(), deflate_huf_symbols::freq, deflate_alphabet::huf, deflate_alphabet::lookup, deflate_huf_symbols::raw, deflate_huf_symbols::shift, and deflate_huf_symbols::start.

Referenced by deflate_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" );
}
static int deflate_alphabet ( struct deflate deflate,
struct deflate_alphabet alphabet,
unsigned int  count,
unsigned int  offset 
) [static]

Construct Huffman alphabet.

Parameters:
deflateDecompressor
alphabetHuffman alphabet
countNumber of symbols
offsetStarting offset within length table
Return values:
rcReturn status code

Definition at line 213 of file deflate.c.

References deflate_huf_symbols::bits, count, DBGC, deflate_alphabet_name(), deflate_dump_alphabet(), DEFLATE_HUFFMAN_QL_BITS, DEFLATE_HUFFMAN_QL_SHIFT, deflate_length(), EINVAL, deflate_huf_symbols::freq, deflate_alphabet::huf, deflate_alphabet::lookup, memset(), prefix, deflate_huf_symbols::raw, deflate_alphabet::raw, raw, deflate_huf_symbols::shift, and deflate_huf_symbols::start.

                                                                        {
        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;
}
static int deflate_accumulate ( struct deflate deflate,
struct deflate_chunk in,
unsigned int  target 
) [static]

Attempt to accumulate bits from input stream.

Parameters:
deflateDecompressor
inCompressed input data
targetNumber of bits to accumulate
Return values:
excessNumber of excess bits accumulated (may be negative)

Definition at line 307 of file deflate.c.

References deflate::accumulator, assert, deflate::bits, byte, copy_from_user(), deflate_chunk::data, deflate_reverse, deflate_chunk::len, deflate_chunk::offset, and deflate::rotalumucca.

Referenced by deflate_decode(), deflate_extract(), and deflate_inflate().

                                                      {
        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 );
}
static int deflate_consume ( struct deflate deflate,
unsigned int  count 
) [static]

Consume accumulated bits from the input stream.

Parameters:
deflateDecompressor
countNumber of accumulated bits to consume
Return values:
dataConsumed bits

Definition at line 343 of file deflate.c.

References deflate::accumulator, assert, deflate_huf_symbols::bits, deflate::bits, count, data, and deflate::rotalumucca.

Referenced by deflate_decode(), deflate_discard_to_byte(), and deflate_extract().

                                                                           {
        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;
}
static int deflate_extract ( struct deflate deflate,
struct deflate_chunk in,
unsigned int  target 
) [static]

Attempt to extract a fixed number of bits from input stream.

Parameters:
deflateDecompressor
inCompressed input data
targetNumber of bits to extract
Return values:
dataExtracted bits (or negative if not yet accumulated)

Definition at line 366 of file deflate.c.

References data, DBGCP, deflate_accumulate(), deflate_bin(), and deflate_consume().

Referenced by deflate_inflate().

                                                   {
        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;
}
static int deflate_decode ( struct deflate deflate,
struct deflate_chunk in,
struct deflate_alphabet alphabet 
) [static]

Attempt to decode a Huffman-coded symbol from input stream.

Parameters:
deflateDecompressor
inCompressed input data
alphabetHuffman alphabet
Return values:
codeRaw code (or negative if not yet accumulated)

Definition at line 396 of file deflate.c.

References deflate_huf_symbols::bits, deflate::bits, DBGCP, deflate_accumulate(), deflate_bin(), deflate_consume(), DEFLATE_HUFFMAN_BITS, DEFLATE_HUFFMAN_QL_SHIFT, deflate_alphabet::huf, deflate_alphabet::lookup, deflate_huf_symbols::raw, raw, deflate::rotalumucca, deflate_huf_symbols::shift, and start.

Referenced by deflate_inflate().

                                                                {
        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;
}
static void deflate_discard_to_byte ( struct deflate deflate) [static]

Discard bits up to the next byte boundary.

Parameters:
deflateDecompressor

Definition at line 443 of file deflate.c.

References deflate::bits, and deflate_consume().

Referenced by deflate_inflate().

                                                                {

        deflate_consume ( deflate, ( deflate->bits & 7 ) );
}
static void deflate_copy ( struct deflate_chunk out,
userptr_t  start,
size_t  offset,
size_t  len 
) [static]

Copy data to output buffer (if available)

Parameters:
outOutput data buffer
startSource data
offsetStarting offset within source data
lenLength to copy

Definition at line 456 of file deflate.c.

References deflate_chunk::data, deflate_chunk::len, len, memcpy_user(), and deflate_chunk::offset.

Referenced by deflate_inflate().

                                                                        {
        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;
}
int deflate_inflate ( struct deflate deflate,
struct deflate_chunk in,
struct deflate_chunk out 
)

Inflate compressed data.

Parameters:
deflateDecompressor
inCompressed input data
outOutput data buffer
Return values:
rcReturn 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.

Definition at line 492 of file deflate.c.

References assert, byte, cm, code, deflate_static_length_pattern::count, deflate_chunk::data, DBGC, DBGC2, DBGCP, deflate_accumulate(), DEFLATE_CODELEN_BITS, deflate_codelen_map, DEFLATE_CODELEN_MAX_CODE, deflate_copy(), deflate_decode(), deflate_discard_to_byte(), deflate_distance_base, DEFLATE_DYNAMIC_BITS, DEFLATE_DYNAMIC_HCLEN_LSB, DEFLATE_DYNAMIC_HCLEN_MASK, DEFLATE_DYNAMIC_HDIST_LSB, DEFLATE_DYNAMIC_HDIST_MASK, DEFLATE_DYNAMIC_HLIT_LSB, DEFLATE_DYNAMIC_HLIT_MASK, deflate_extract(), DEFLATE_HEADER_BFINAL_BIT, DEFLATE_HEADER_BITS, DEFLATE_HEADER_BTYPE_DYNAMIC, DEFLATE_HEADER_BTYPE_LITERAL, DEFLATE_HEADER_BTYPE_LSB, DEFLATE_HEADER_BTYPE_STATIC, DEFLATE_LITERAL_LEN_BITS, deflate_litlen_base, DEFLATE_LITLEN_END, DEFLATE_RAW, deflate_set_length(), DEFLATE_ZLIB, deflate::distance_codelen, deflate::distance_count, deflate::dup_distance, deflate::dup_len, EINVAL, ENOTSUP, deflate::extra_bits, deflate_static_length_pattern::fill, deflate::format, header, deflate::header, index, isprint(), deflate_chunk::len, len, deflate::length, deflate::length_index, deflate::length_target, deflate::lengths, deflate::litlen, deflate::litlen_count, memset(), NULL, deflate_chunk::offset, rc, deflate::remaining, deflate::resume, virt_to_user(), ZLIB_ADLER32_BITS, ZLIB_HEADER_BITS, ZLIB_HEADER_CM_DEFLATE, ZLIB_HEADER_CM_LSB, ZLIB_HEADER_CM_MASK, and ZLIB_HEADER_FDICT_BIT.

Referenced by deflate_okx(), and png_image_data().

                                                  {

        /* 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;
        }
}
void deflate_init ( struct deflate deflate,
enum deflate_format  format 
)

Initialise decompressor.

Parameters:
deflateDecompressor
formatCompression format code

Definition at line 999 of file deflate.c.

References assert, base, byte, deflate_distance_base, deflate_litlen_base, deflate_reverse, format, deflate::format, and memset().

Referenced by deflate_okx(), and png_pixbuf().

                                                                          {
        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;
}

Variable Documentation

uint8_t deflate_reverse[256] [static]

Byte reversal table.

For some insane reason, the DEFLATE format stores some values in bit-reversed order.

Definition at line 51 of file deflate.c.

Referenced by deflate_accumulate(), and deflate_init().

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".

Definition at line 62 of file deflate.c.

Referenced by deflate_inflate(), and deflate_init().

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".

Definition at line 71 of file deflate.c.

Referenced by deflate_inflate(), and deflate_init().

Initial value:
 {
        16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
}

Code length map.

Definition at line 74 of file deflate.c.

Referenced by deflate_inflate().

Initial value:
 {
        
        { 0x88, ( ( ( 143 -   0 ) + 1 ) / 2 ) },
        { 0x99, ( ( ( 255 - 144 ) + 1 ) / 2 ) },
        { 0x77, ( ( ( 279 - 256 ) + 1 ) / 2 ) },
        { 0x88, ( ( ( 287 - 280 ) + 1 ) / 2 ) },
        
        { 0x55, ( ( (  31 -   0 ) + 1 ) / 2 ) },
        
        { 0, 0 }
}

Static Huffman alphabet length patterns.

Definition at line 79 of file deflate.c.