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/deflate.h>

Go to the source code of this file.

Functions
	FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
	FILE_SECBOOT (PERMITTED)
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, 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, unsigned int target)
	Attempt to extract a fixed number of bits from input stream.
static int	deflate_decode (struct deflate *deflate, 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, const void *in, size_t len)
	Copy data to output buffer (if available)
int	deflate_inflate (struct deflate *deflate, const void *data, size_t len, 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()

FILE_LICENCE

(

GPL2_OR_LATER_OR_UBDL

)

FILE_SECBOOT()

FILE_SECBOOT

(

PERMITTED

)

deflate_bin()

const char * deflate_bin ( unsigned long value, unsigned int bits )

static

Transcribe binary value (for debugging)

Parameters

value	Value
bits	Length of value (in bits)

Return values

string

Transcribed value

Definition at line 98 of file deflate.c.

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

References assert, bits, out, and value.

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

deflate_set_length()

void deflate_set_length ( struct deflate * deflate, unsigned int index, unsigned int bits )

static

Set Huffman symbol length.

Parameters

deflate	Decompressor
index	Index within lengths
bits	Symbol length (in bits)

Definition at line 120 of file deflate.c.

                                                     {
 
        deflate->lengths[ index / 2 ] |= ( bits << ( 4 * ( index % 2 ) ) );
}

References bits, index, and deflate::lengths.

Referenced by deflate_inflate().

deflate_length()

unsigned int deflate_length ( struct deflate * deflate, unsigned int index )

static

Get Huffman symbol length.

Parameters

deflate	Decompressor
index	Index within lengths

Return values

bits	Symbol length (in bits)

Definition at line 133 of file deflate.c.

                                                          {
 
        return ( ( deflate->lengths[ index / 2 ] >> ( 4 * ( index % 2 ) ) )
                 & 0x0f );
}

References index, and deflate::lengths.

Referenced by deflate_alphabet().

deflate_alphabet_name()

const char * deflate_alphabet_name ( struct deflate * deflate, struct deflate_alphabet * alphabet )

static

Determine Huffman alphabet name (for debugging)

Parameters

deflate	Decompressor
alphabet	Huffman alphabet

Return values

name	Alphabet name

Definition at line 147 of file deflate.c.

                                                                               {
 
        if ( alphabet == &deflate->litlen ) {
                return "litlen";
        } else if ( alphabet == &deflate->distance_codelen ) {
                return "distance/codelen";
        } else {
                return "<UNKNOWN>";
        }
}

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

Referenced by deflate_alphabet(), and deflate_dump_alphabet().

deflate_dump_alphabet()

void deflate_dump_alphabet ( struct deflate * deflate, struct deflate_alphabet * alphabet )

static

Dump Huffman alphabet (for debugging)

Parameters

deflate	Decompressor
alphabet	Huffman alphabet

Definition at line 165 of file deflate.c.

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

References bits, 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().

deflate_alphabet()

int deflate_alphabet ( struct deflate * deflate, struct deflate_alphabet * alphabet, unsigned int count, unsigned int offset )

static

Construct Huffman alphabet.

Parameters

deflate	Decompressor
alphabet	Huffman alphabet
count	Number of symbols
offset	Starting offset within length table

Return values

rc	Return status code

Definition at line 213 of file deflate.c.

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

References bits, 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(), offset, prefix, deflate_alphabet::raw, deflate_huf_symbols::raw, raw, deflate_huf_symbols::shift, and deflate_huf_symbols::start.

deflate_accumulate()

int deflate_accumulate ( struct deflate * deflate, unsigned int target )

static

Attempt to accumulate bits from input stream.

Parameters

deflate	Decompressor
target	Number of bits to accumulate

Return values

excess

Number of excess bits accumulated (may be negative)

Definition at line 306 of file deflate.c.

                                                      {
        uint8_t byte;
 
        while ( deflate->bits < target ) {
 
                /* Check for end of input */
                if ( deflate->in == deflate->end )
                        break;
 
                /* Acquire byte from input */
                byte = *(deflate->in++);
                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 );
}

References deflate::accumulator, assert, deflate::bits, deflate_reverse, deflate::end, deflate::in, and deflate::rotalumucca.

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

deflate_consume()

int deflate_consume ( struct deflate * deflate, unsigned int count )

static

Consume accumulated bits from the input stream.

Parameters

deflate	Decompressor
count	Number of accumulated bits to consume

Return values

data	Consumed bits

Definition at line 340 of file deflate.c.

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

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

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

deflate_extract()

int deflate_extract ( struct deflate * deflate, unsigned int target )

static

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

Parameters

deflate	Decompressor
target	Number of bits to extract

Return values

data	Extracted bits (or negative if not yet accumulated)

Definition at line 362 of file deflate.c.

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

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

Referenced by deflate_inflate().

deflate_decode()

int deflate_decode ( struct deflate * deflate, struct deflate_alphabet * alphabet )

static

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

Parameters

deflate	Decompressor
alphabet	Huffman alphabet

Return values

code	Raw code (or negative if not yet accumulated)

Definition at line 390 of file deflate.c.

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

References deflate::bits, deflate_huf_symbols::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().

deflate_discard_to_byte()

void deflate_discard_to_byte ( struct deflate * deflate )

static

Discard bits up to the next byte boundary.

Parameters

deflate

Decompressor

Definition at line 436 of file deflate.c.

                                                                {
 
        deflate_consume ( deflate, ( deflate->bits & 7 ) );
}

References deflate::bits, and deflate_consume().

Referenced by deflate_inflate().

deflate_copy()

void deflate_copy ( struct deflate_chunk * out, const void * in, size_t len )

static

Copy data to output buffer (if available)

Parameters

out	Output data buffer
in	Input data
len	Length to copy

Definition at line 448 of file deflate.c.

                                        {
        const uint8_t *in_byte = in;
        uint8_t *out_byte = ( out->data + 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-- )
                        *(out_byte++) = *(in_byte++);
        }
        out->offset += len;
}

References in, len, and out.

Referenced by deflate_inflate().

deflate_inflate()

int deflate_inflate	(	struct deflate *	deflate,
		const void *	data,
		size_t	len,
		struct deflate_chunk *	out )

Inflate compressed data.

Parameters

deflate	Decompressor
data	Compressed input data
len	Length of compressed input data
out	Output data buffer

Return values

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.

Definition at line 484 of file deflate.c.

                                                  {
 
        /* Store input data pointers */
        deflate->in = data;
        deflate->end = ( data + len );
 
        /* 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, 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, 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 llen;
 
                /* Extract LEN field */
                llen = deflate_extract ( deflate, DEFLATE_LITERAL_LEN_BITS );
                if ( llen < 0 ) {
                        deflate->resume = &&literal_len;
                        return 0;
                }
 
                /* Record length of literal data */
                deflate->remaining = llen;
                DBGC2 ( deflate, "DEFLATE %p literal block length %#04zx\n",
                        deflate, deflate->remaining );
        }
 
 literal_nlen: {
                int nlen;
 
                /* Extract NLEN field */
                nlen = deflate_extract ( deflate, 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 dlen;
 
                /* Calculate available amount of literal data */
                in_remaining = ( deflate->end - deflate->in );
                dlen = deflate->remaining;
                if ( dlen > in_remaining )
                        dlen = in_remaining;
 
                /* Copy data to output buffer */
                deflate_copy ( out, deflate->in, dlen );
 
                /* Consume data from input buffer */
                deflate->in += dlen;
                deflate->remaining -= dlen;
 
                /* 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, 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 clen;
                unsigned int index;
                int rc;
 
                /* Extract all code lengths */
                while ( deflate->length_index < deflate->length_target ) {
 
                        /* Extract code length length */
                        clen = deflate_extract ( deflate,
                                                 DEFLATE_CODELEN_BITS );
                        if ( clen < 0 ) {
                                deflate->resume = &&dynamic_codelen;
                                return 0;
                        }
 
                        /* Store code length */
                        index = deflate_codelen_map[deflate->length_index++];
                        deflate_set_length ( deflate, index, clen );
                        DBGCP ( deflate, "DEFLATE %p codelen for %d is %d\n",
                                deflate, index, clen );
                }
 
                /* 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 clen;
                int index;
 
                /* Decode literal/length/distance code length */
                clen = deflate_decode ( deflate, &deflate->distance_codelen );
                if ( clen < 0 ) {
                        deflate->resume = &&dynamic_litlen_distance;
                        return 0;
                }
 
                /* Prepare for extra bits */
                if ( clen < 16 ) {
                        deflate->length = clen;
                        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 = ( clen - 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, 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, &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, &byte, 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, 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, &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, 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, 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;
        }
}

References assert, bits, cm, code, deflate_static_length_pattern::count, 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_static_length_patterns, DEFLATE_ZLIB, deflate::distance_codelen, deflate::distance_count, deflate::dup_distance, deflate::dup_len, EINVAL, deflate::end, ENOTSUP, extra, deflate::extra_bits, deflate_static_length_pattern::fill, deflate::format, deflate::header, header, deflate::in, index, isprint(), len, deflate::length, deflate::length_index, deflate::length_target, deflate::lengths, deflate::litlen, deflate::litlen_count, memset(), NULL, out, rc, deflate::remaining, deflate::resume, 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(), png_image_data(), and zlib_deflate().

deflate_init()

void deflate_init	(	struct deflate *	deflate,
		enum deflate_format	format )

Initialise decompressor.

Parameters

deflate	Decompressor
format	Compression format code

Definition at line 992 of file deflate.c.

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

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

Referenced by deflate_okx(), png_pixbuf(), and zlib_deflate().

Variable Documentation

deflate_reverse

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().

deflate_litlen_base

uint8_t deflate_litlen_base[28]

static

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

Definition at line 62 of file deflate.c.

Referenced by deflate_inflate(), and deflate_init().

deflate_distance_base

uint16_t deflate_distance_base[32]

static

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().

deflate_codelen_map

uint8_t deflate_codelen_map[19]

static

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.

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

Referenced by deflate_inflate().

deflate_static_length_patterns

struct deflate_static_length_pattern deflate_static_length_patterns[]

static

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.

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

Referenced by deflate_inflate().