iPXE
Data Structures | Defines | Enumerations | Functions | Variables
deflate.h File Reference

DEFLATE decompression algorithm. More...

#include <stdint.h>
#include <string.h>
#include <ipxe/uaccess.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...

Defines

#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)
struct
deflate_static_length_pattern 
__attribute__ ((packed))
static __attribute__ ((always_inline)) void deflate_chunk_init(struct deflate_chunk *chunk
 Initialise chunk of data.
int deflate_inflate (struct deflate *deflate, struct deflate_chunk *in, struct deflate_chunk *out)
 Inflate compressed data.

Variables

uint8_t fill
 Length pair.
uint8_t count
 Repetition count.
struct deflate __attribute__
static userptr_t data
static userptr_t size_t offset
 Offset of the first segment within the content.

Detailed Description

DEFLATE decompression algorithm.

Definition in file deflate.h.


Define Documentation

#define DEFLATE_HEADER_BITS   3

Block header length (in bits)

Definition at line 25 of file deflate.h.

Referenced by deflate_inflate().

#define DEFLATE_HEADER_BFINAL_BIT   0

Block header final block flags bit.

Definition at line 28 of file deflate.h.

Referenced by deflate_inflate().

#define DEFLATE_HEADER_BTYPE_LSB   1

Block header type LSB.

Definition at line 31 of file deflate.h.

Referenced by deflate_inflate().

#define DEFLATE_HEADER_BTYPE_MASK   0x03

Block header type mask.

Definition at line 34 of file deflate.h.

Block header type: literal data.

Definition at line 37 of file deflate.h.

Referenced by deflate_inflate().

Block header type: static Huffman alphabet.

Definition at line 40 of file deflate.h.

Referenced by deflate_inflate().

Block header type: dynamic Huffman alphabet.

Definition at line 43 of file deflate.h.

Referenced by deflate_inflate().

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

#define DEFLATE_DYNAMIC_BITS   14

Dynamic header length (in bits)

Definition at line 49 of file deflate.h.

Referenced by deflate_inflate().

#define DEFLATE_DYNAMIC_HLIT_LSB   0

Dynamic header HLIT field LSB.

Definition at line 52 of file deflate.h.

Referenced by deflate_inflate().

#define DEFLATE_DYNAMIC_HLIT_MASK   0x1f

Dynamic header HLIT field mask.

Definition at line 55 of file deflate.h.

Referenced by deflate_inflate().

#define DEFLATE_DYNAMIC_HDIST_LSB   5

Dynamic header HDIST field LSB.

Definition at line 58 of file deflate.h.

Referenced by deflate_inflate().

#define DEFLATE_DYNAMIC_HDIST_MASK   0x1f

Dynamic header HDIST field mask.

Definition at line 61 of file deflate.h.

Referenced by deflate_inflate().

#define DEFLATE_DYNAMIC_HCLEN_LSB   10

Dynamic header HCLEN field LSB.

Definition at line 64 of file deflate.h.

Referenced by deflate_inflate().

#define DEFLATE_DYNAMIC_HCLEN_MASK   0x0f

Dynamic header HCLEN field mask.

Definition at line 67 of file deflate.h.

Referenced by deflate_inflate().

#define DEFLATE_CODELEN_BITS   3

Dynamic header code length length (in bits)

Definition at line 70 of file deflate.h.

Referenced by deflate_inflate().

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

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

Quick lookup shift.

Definition at line 82 of file deflate.h.

Referenced by deflate_alphabet(), and deflate_decode().

#define DEFLATE_LITLEN_END   256

Literal/length end of block code.

Definition at line 85 of file deflate.h.

Referenced by deflate_inflate().

#define DEFLATE_LITLEN_MAX_CODE   287

Maximum value of a literal/length code.

Definition at line 88 of file deflate.h.

#define DEFLATE_DISTANCE_MAX_CODE   31

Maximum value of a distance code.

Definition at line 91 of file deflate.h.

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

#define ZLIB_HEADER_BITS   16

ZLIB header length (in bits)

Definition at line 97 of file deflate.h.

Referenced by deflate_inflate().

#define ZLIB_HEADER_CM_LSB   0

ZLIB header compression method LSB.

Definition at line 100 of file deflate.h.

Referenced by deflate_inflate().

#define ZLIB_HEADER_CM_MASK   0x0f

ZLIB header compression method mask.

Definition at line 103 of file deflate.h.

Referenced by deflate_inflate().

#define ZLIB_HEADER_CM_DEFLATE   8

ZLIB header compression method: DEFLATE.

Definition at line 106 of file deflate.h.

Referenced by deflate_inflate().

#define ZLIB_HEADER_FDICT_BIT   13

ZLIB header preset dictionary flag bit.

Definition at line 109 of file deflate.h.

Referenced by deflate_inflate().

#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

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 ( GPL2_OR_LATER_OR_UBDL  )
static __attribute__ ( (always_inline)  ) [inline, static]

Initialise chunk of data.

Parameters:
chunkChunk of data to initialise
dataData
offsetStarting offset
lenLength
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;
        }
}

Variable Documentation

Repetition count.

Definition at line 157 of file deflate.h.

Definition at line 259 of file deflate.h.

Offset of the first segment within the content.

Definition at line 259 of file deflate.h.

Referenced by acpi_currticks(), acpi_settings_fetch(), acpi_sx_zsdt(), alloc_iob_raw(), ar9003_hw_tx_iq_cal_post_proc(), ar9285_hw_pa_cal(), ar9300_read_otp(), ar9300_uncompress_block(), asn1_okx(), ath5k_cal_data_offset_2413(), ath5k_eeprom_init_modes(), ath5k_eeprom_read_ants(), ath5k_eeprom_read_ctl_info(), ath5k_eeprom_read_freq_list(), ath5k_eeprom_read_mac(), ath5k_eeprom_read_modes(), ath5k_eeprom_read_pcal_info_2413(), ath5k_eeprom_read_pcal_info_5111(), ath5k_eeprom_read_pcal_info_5112(), ath5k_eeprom_read_target_rate_pwr_info(), ath5k_eeprom_read_turbo_modes(), ath5k_hw_rfb_op(), ath9k_olc_get_pdadcs(), atl1e_setup_ring_resources(), axge_in_complete(), base64_decode(), bios_currticks(), bnx2_init_context(), bofm_locate_section(), bzimage_load_initrd(), bzimage_load_initrds(), cert_exec(), check_bios_interrupts(), clear_b0_fpga_memories(), cms_digest(), day_of_week(), dbg_hex_dump_da(), deflate_okx(), dhcpopt_fetch(), dhcpopt_store(), dhcpopt_update_used_len(), digest_exec(), dns_decode(), dns_label(), dns_list_okx(), dns_skip(), dns_skip_search(), efifb_glyph(), efifb_glyphs(), ehci_enqueue(), ehci_extended_capability(), exanic_poll_rx(), exanic_transmit(), fbcon_clear(), fbcon_draw(), fbcon_draw_cursor(), fbcon_picture_init(), fbcon_redraw(), fbcon_store(), fcpcmd_recv_rddata(), find_dhcp_option_with_encap(), find_smbios_entry(), find_smbios_structure(), fragment_reassemble(), goto_find_label(), history_entry(), history_move(), hunt_mcdi_copyout(), ibft_install(), ibft_string(), inject_corruption_nonzero(), ioremap_pages(), iscsi_rx_data_in(), iscsi_start_data_out(), iscsi_tx_data_out(), linda_post_send(), linda_verify_uc_ram(), load_cpu_fw(), md4_update(), md5_update(), mlx_pci_gw_check_capability_id(), multiboot_find_header(), multiboot_load_raw(), natsemi_create_ring(), natsemi_hwaddr_insane(), ndp_fetch(), ndp_register_settings(), ndp_rx_options(), nodnic_port_thin_init(), ntlm_challenge(), ntlm_data_okx(), pci_backup(), pci_restore(), pciea_bar_value(), pciea_offset(), peerdist_info_v1_block_offset(), pem_asn1(), pem_image_probe(), pem_marker(), phantom_clp_cmd(), phantom_clp_fetch(), phantom_clp_store(), phantom_crb_access_128m(), phantom_crb_access_2m(), phantom_crb_access_32m(), phantom_dmesg(), phantom_get_macaddr(), phantom_read_test_mem(), phantom_readl(), phantom_writel(), png_palette(), png_unfilter_pass(), pnm_data(), pxenv_file_api_check(), qib7322_post_send(), read_smbios_string(), rsdp_find_rsdt_range(), set_dhcp_option(), sha1_update(), sha256_update(), sha512_update(), tcpip_bind(), tftp_rx_data(), txnic_poll_cq(), txnic_refill_rq(), txnic_send(), vesafb_glyph(), virtio_pci_map_capability(), vmbus_xfer_page_iobufs(), vxge_hw_ring_replenish(), xenstore_recv(), xenstore_send(), xfer_seek(), xhci_extended_capability(), and xhci_supported_protocol().