deflate.h File Reference

DEFLATE decompression algorithm. More...

#include <stdint.h>
#include <string.h>

Go to the source code of this file.

Data Structures
struct	deflate_huf_symbols
	A Huffman-coded set of symbols of a given length. More...
struct	deflate_alphabet
	A Huffman-coded alphabet. More...
struct	deflate_static_length_pattern
	A static Huffman alphabet length pattern. More...
struct	deflate
	Decompressor. More...
struct	deflate_chunk
	A chunk of data. More...

Macros
#define	DEFLATE_HEADER_BITS   3
	Block header length (in bits)
#define	DEFLATE_HEADER_BFINAL_BIT   0
	Block header final block flags bit.
#define	DEFLATE_HEADER_BTYPE_LSB   1
	Block header type LSB.
#define	DEFLATE_HEADER_BTYPE_MASK   0x03
	Block header type mask.
#define	DEFLATE_HEADER_BTYPE_LITERAL   0
	Block header type: literal data.
#define	DEFLATE_HEADER_BTYPE_STATIC   1
	Block header type: static Huffman alphabet.
#define	DEFLATE_HEADER_BTYPE_DYNAMIC   2
	Block header type: dynamic Huffman alphabet.
#define	DEFLATE_LITERAL_LEN_BITS   16
	Literal header LEN/NLEN field length (in bits)
#define	DEFLATE_DYNAMIC_BITS   14
	Dynamic header length (in bits)
#define	DEFLATE_DYNAMIC_HLIT_LSB   0
	Dynamic header HLIT field LSB.
#define	DEFLATE_DYNAMIC_HLIT_MASK   0x1f
	Dynamic header HLIT field mask.
#define	DEFLATE_DYNAMIC_HDIST_LSB   5
	Dynamic header HDIST field LSB.
#define	DEFLATE_DYNAMIC_HDIST_MASK   0x1f
	Dynamic header HDIST field mask.
#define	DEFLATE_DYNAMIC_HCLEN_LSB   10
	Dynamic header HCLEN field LSB.
#define	DEFLATE_DYNAMIC_HCLEN_MASK   0x0f
	Dynamic header HCLEN field mask.
#define	DEFLATE_CODELEN_BITS   3
	Dynamic header code length length (in bits)
#define	DEFLATE_HUFFMAN_BITS   15
	Maximum length of a Huffman symbol (in bits)
#define	DEFLATE_HUFFMAN_QL_BITS   7
	Quick lookup length for a Huffman symbol (in bits)
#define	DEFLATE_HUFFMAN_QL_SHIFT   ( 16 - DEFLATE_HUFFMAN_QL_BITS )
	Quick lookup shift.
#define	DEFLATE_LITLEN_END   256
	Literal/length end of block code.
#define	DEFLATE_LITLEN_MAX_CODE   287
	Maximum value of a literal/length code.
#define	DEFLATE_DISTANCE_MAX_CODE   31
	Maximum value of a distance code.
#define	DEFLATE_CODELEN_MAX_CODE   18
	Maximum value of a code length code.
#define	ZLIB_HEADER_BITS   16
	ZLIB header length (in bits)
#define	ZLIB_HEADER_CM_LSB   0
	ZLIB header compression method LSB.
#define	ZLIB_HEADER_CM_MASK   0x0f
	ZLIB header compression method mask.
#define	ZLIB_HEADER_CM_DEFLATE   8
	ZLIB header compression method: DEFLATE.
#define	ZLIB_HEADER_FDICT_BIT   13
	ZLIB header preset dictionary flag bit.
#define	ZLIB_ADLER32_BITS   32
	ZLIB ADLER32 length (in bits)

Enumerations
enum	deflate_format { DEFLATE_RAW , DEFLATE_ZLIB }
	Compression formats. More...

Functions
	FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
	FILE_SECBOOT (PERMITTED)
struct deflate_static_length_pattern	__attribute__ ((packed))
static	__attribute__ ((always_inline)) void deflate_chunk_init(struct deflate_chunk *chunk
	Initialise chunk of data.
static int	deflate_finished (struct deflate *deflate)
	Check if decompression has finished.
void	deflate_init (struct deflate *deflate, enum deflate_format format)
	Initialise decompressor.
int	deflate_inflate (struct deflate *deflate, const void *data, size_t len, struct deflate_chunk *out)
	Inflate compressed data.

Variables
uint8_t	fill
	Length pair.
uint8_t	count
	Repetition count.
struct deflate	__attribute__
static void *	data
static void size_t	offset = offset
static void size_t size_t	len

Detailed Description

DEFLATE decompression algorithm.

Definition in file deflate.h.

Macro Definition Documentation

DEFLATE_HEADER_BITS

#define DEFLATE_HEADER_BITS   3

Block header length (in bits)

Definition at line 25 of file deflate.h.

Referenced by deflate_inflate().

DEFLATE_HEADER_BFINAL_BIT

#define DEFLATE_HEADER_BFINAL_BIT   0

Block header final block flags bit.

Definition at line 28 of file deflate.h.

Referenced by deflate_inflate().

DEFLATE_HEADER_BTYPE_LSB

#define DEFLATE_HEADER_BTYPE_LSB   1

Block header type LSB.

Definition at line 31 of file deflate.h.

Referenced by deflate_inflate().

DEFLATE_HEADER_BTYPE_MASK

#define DEFLATE_HEADER_BTYPE_MASK   0x03

Block header type mask.

Definition at line 34 of file deflate.h.

DEFLATE_HEADER_BTYPE_LITERAL

#define DEFLATE_HEADER_BTYPE_LITERAL   0

Block header type: literal data.

Definition at line 37 of file deflate.h.

Referenced by deflate_inflate().

DEFLATE_HEADER_BTYPE_STATIC

#define DEFLATE_HEADER_BTYPE_STATIC   1

Block header type: static Huffman alphabet.

Definition at line 40 of file deflate.h.

Referenced by deflate_inflate().

DEFLATE_HEADER_BTYPE_DYNAMIC

#define DEFLATE_HEADER_BTYPE_DYNAMIC   2

Block header type: dynamic Huffman alphabet.

Definition at line 43 of file deflate.h.

Referenced by deflate_inflate().

DEFLATE_LITERAL_LEN_BITS

#define DEFLATE_LITERAL_LEN_BITS   16

Literal header LEN/NLEN field length (in bits)

Definition at line 46 of file deflate.h.

Referenced by deflate_inflate().

DEFLATE_DYNAMIC_BITS

#define DEFLATE_DYNAMIC_BITS   14

Dynamic header length (in bits)

Definition at line 49 of file deflate.h.

Referenced by deflate_inflate().

DEFLATE_DYNAMIC_HLIT_LSB

#define DEFLATE_DYNAMIC_HLIT_LSB   0

Dynamic header HLIT field LSB.

Definition at line 52 of file deflate.h.

Referenced by deflate_inflate().

DEFLATE_DYNAMIC_HLIT_MASK

#define DEFLATE_DYNAMIC_HLIT_MASK   0x1f

Dynamic header HLIT field mask.

Definition at line 55 of file deflate.h.

Referenced by deflate_inflate().

DEFLATE_DYNAMIC_HDIST_LSB

#define DEFLATE_DYNAMIC_HDIST_LSB   5

Dynamic header HDIST field LSB.

Definition at line 58 of file deflate.h.

Referenced by deflate_inflate().

DEFLATE_DYNAMIC_HDIST_MASK

#define DEFLATE_DYNAMIC_HDIST_MASK   0x1f

Dynamic header HDIST field mask.

Definition at line 61 of file deflate.h.

Referenced by deflate_inflate().

DEFLATE_DYNAMIC_HCLEN_LSB

#define DEFLATE_DYNAMIC_HCLEN_LSB   10

Dynamic header HCLEN field LSB.

Definition at line 64 of file deflate.h.

Referenced by deflate_inflate().

DEFLATE_DYNAMIC_HCLEN_MASK

#define DEFLATE_DYNAMIC_HCLEN_MASK   0x0f

Dynamic header HCLEN field mask.

Definition at line 67 of file deflate.h.

Referenced by deflate_inflate().

DEFLATE_CODELEN_BITS

#define DEFLATE_CODELEN_BITS   3

Dynamic header code length length (in bits)

Definition at line 70 of file deflate.h.

Referenced by deflate_inflate().

DEFLATE_HUFFMAN_BITS

#define DEFLATE_HUFFMAN_BITS   15

Maximum length of a Huffman symbol (in bits)

Definition at line 73 of file deflate.h.

Referenced by deflate_decode().

DEFLATE_HUFFMAN_QL_BITS

#define DEFLATE_HUFFMAN_QL_BITS   7

Quick lookup length for a Huffman symbol (in bits)

This is a policy decision.

Definition at line 79 of file deflate.h.

Referenced by deflate_alphabet().

DEFLATE_HUFFMAN_QL_SHIFT

#define DEFLATE_HUFFMAN_QL_SHIFT   ( 16 - DEFLATE_HUFFMAN_QL_BITS )

Quick lookup shift.

Definition at line 82 of file deflate.h.

Referenced by deflate_alphabet(), and deflate_decode().

DEFLATE_LITLEN_END

#define DEFLATE_LITLEN_END   256

Literal/length end of block code.

Definition at line 85 of file deflate.h.

Referenced by deflate_inflate().

DEFLATE_LITLEN_MAX_CODE

#define DEFLATE_LITLEN_MAX_CODE   287

Maximum value of a literal/length code.

Definition at line 88 of file deflate.h.

DEFLATE_DISTANCE_MAX_CODE

#define DEFLATE_DISTANCE_MAX_CODE   31

Maximum value of a distance code.

Definition at line 91 of file deflate.h.

DEFLATE_CODELEN_MAX_CODE

#define DEFLATE_CODELEN_MAX_CODE   18

Maximum value of a code length code.

Definition at line 94 of file deflate.h.

Referenced by deflate_inflate().

ZLIB_HEADER_BITS

#define ZLIB_HEADER_BITS   16

ZLIB header length (in bits)

Definition at line 97 of file deflate.h.

Referenced by deflate_inflate().

ZLIB_HEADER_CM_LSB

#define ZLIB_HEADER_CM_LSB   0

ZLIB header compression method LSB.

Definition at line 100 of file deflate.h.

Referenced by deflate_inflate().

ZLIB_HEADER_CM_MASK

#define ZLIB_HEADER_CM_MASK   0x0f

ZLIB header compression method mask.

Definition at line 103 of file deflate.h.

Referenced by deflate_inflate().

ZLIB_HEADER_CM_DEFLATE

#define ZLIB_HEADER_CM_DEFLATE   8

ZLIB header compression method: DEFLATE.

Definition at line 106 of file deflate.h.

Referenced by deflate_inflate().

ZLIB_HEADER_FDICT_BIT

#define ZLIB_HEADER_FDICT_BIT   13

ZLIB header preset dictionary flag bit.

Definition at line 109 of file deflate.h.

Referenced by deflate_inflate().

ZLIB_ADLER32_BITS

#define ZLIB_ADLER32_BITS   32

ZLIB ADLER32 length (in bits)

Definition at line 112 of file deflate.h.

Referenced by deflate_inflate().

Enumeration Type Documentation

deflate_format

enum deflate_format

Compression formats.

Enumerator
DEFLATE_RAW	Raw DEFLATE data (no header or footer)
DEFLATE_ZLIB	ZLIB header and footer.

Definition at line 17 of file deflate.h.

                    {
        /** Raw DEFLATE data (no header or footer) */
        DEFLATE_RAW,
        /** ZLIB header and footer */
        DEFLATE_ZLIB,
};

Function Documentation

FILE_LICENCE()

FILE_LICENCE

(

GPL2_OR_LATER_OR_UBDL

)

FILE_SECBOOT()

FILE_SECBOOT

(

PERMITTED

)

__attribute__() [1/2]

struct deflate_static_length_pattern __attribute__

(

(packed)

)

__attribute__() [2/2]

__attribute__ ( (always_inline) )

inlinestatic

Initialise chunk of data.

Parameters

chunk	Chunk of data to initialise
data	Data
offset	Starting offset
len	Length

deflate_finished()

int deflate_finished ( struct deflate * deflate )

inlinestatic

Check if decompression has finished.

Parameters

deflate

Decompressor

Return values

finished

Decompression has finished

Definition at line 278 of file deflate.h.

                                                               {
        return ( deflate->resume == NULL );
}

References NULL, and deflate::resume.

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

deflate_init()

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

extern

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

deflate_inflate()

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

extern

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

Variable Documentation

fill

uint8_t fill

Length pair.

Definition at line 1 of file deflate.h.

count

uint8_t count

Repetition count.

Definition at line 3 of file deflate.h.

data

void* data

Definition at line 264 of file deflate.h.

offset

chunk offset = offset

Definition at line 265 of file deflate.h.

len

chunk len

Initial value:

{
 
        chunk->data = data

Definition at line 265 of file deflate.h.