iPXE
|
DEFLATE decompression algorithm. More...
#include <string.h>
#include <strings.h>
#include <errno.h>
#include <assert.h>
#include <ctype.h>
#include <ipxe/uaccess.h>
#include <ipxe/deflate.h>
Go to the source code of this file.
Functions | |
FILE_LICENCE (GPL2_OR_LATER_OR_UBDL) | |
static const char * | deflate_bin (unsigned long value, unsigned int bits) |
Transcribe binary value (for debugging) More... | |
static void | deflate_set_length (struct deflate *deflate, unsigned int index, unsigned int bits) |
Set Huffman symbol length. More... | |
static unsigned int | deflate_length (struct deflate *deflate, unsigned int index) |
Get Huffman symbol length. More... | |
static const char * | deflate_alphabet_name (struct deflate *deflate, struct deflate_alphabet *alphabet) |
Determine Huffman alphabet name (for debugging) More... | |
static void | deflate_dump_alphabet (struct deflate *deflate, struct deflate_alphabet *alphabet) |
Dump Huffman alphabet (for debugging) More... | |
static int | deflate_alphabet (struct deflate *deflate, struct deflate_alphabet *alphabet, unsigned int count, unsigned int offset) |
Construct Huffman alphabet. More... | |
static int | deflate_accumulate (struct deflate *deflate, struct deflate_chunk *in, unsigned int target) |
Attempt to accumulate bits from input stream. More... | |
static int | deflate_consume (struct deflate *deflate, unsigned int count) |
Consume accumulated bits from the input stream. More... | |
static int | deflate_extract (struct deflate *deflate, struct deflate_chunk *in, unsigned int target) |
Attempt to extract a fixed number of bits from input stream. More... | |
static int | deflate_decode (struct deflate *deflate, struct deflate_chunk *in, struct deflate_alphabet *alphabet) |
Attempt to decode a Huffman-coded symbol from input stream. More... | |
static void | deflate_discard_to_byte (struct deflate *deflate) |
Discard bits up to the next byte boundary. More... | |
static void | deflate_copy (struct deflate_chunk *out, userptr_t start, size_t offset, size_t len) |
Copy data to output buffer (if available) More... | |
int | deflate_inflate (struct deflate *deflate, struct deflate_chunk *in, struct deflate_chunk *out) |
Inflate compressed data. More... | |
void | deflate_init (struct deflate *deflate, enum deflate_format format) |
Initialise decompressor. More... | |
Variables | |
static uint8_t | deflate_reverse [256] |
Byte reversal table. More... | |
static uint8_t | deflate_litlen_base [28] |
Literal/length base values. More... | |
static uint16_t | deflate_distance_base [32] |
Distance base values. More... | |
static uint8_t | deflate_codelen_map [19] |
Code length map. More... | |
static struct deflate_static_length_pattern | deflate_static_length_patterns [] |
Static Huffman alphabet length patterns. More... | |
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.
FILE_LICENCE | ( | GPL2_OR_LATER_OR_UBDL | ) |
|
static |
Transcribe binary value (for debugging)
value | Value |
bits | Length of value (in bits) |
string | Transcribed value |
Definition at line 98 of file deflate.c.
References assert(), bits, out, and value.
Referenced by deflate_decode(), deflate_dump_alphabet(), and deflate_extract().
|
static |
Set Huffman symbol length.
deflate | Decompressor |
index | Index within lengths |
bits | Symbol length (in bits) |
Definition at line 120 of file deflate.c.
References bits, index, and deflate::lengths.
Referenced by deflate_inflate().
|
static |
Get Huffman symbol length.
deflate | Decompressor |
index | Index within lengths |
bits | Symbol length (in bits) |
Definition at line 133 of file deflate.c.
References index, and deflate::lengths.
Referenced by deflate_alphabet().
|
static |
Determine Huffman alphabet name (for debugging)
deflate | Decompressor |
alphabet | Huffman alphabet |
name | Alphabet name |
Definition at line 147 of file deflate.c.
References deflate::distance_codelen, and deflate::litlen.
Referenced by deflate_alphabet(), and deflate_dump_alphabet().
|
static |
Dump Huffman alphabet (for debugging)
deflate | Decompressor |
alphabet | Huffman alphabet |
Definition at line 165 of file deflate.c.
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().
|
static |
Construct Huffman alphabet.
deflate | Decompressor |
alphabet | Huffman alphabet |
count | Number of symbols |
offset | Starting offset within length table |
rc | Return status code |
Definition at line 213 of file deflate.c.
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, raw, deflate_huf_symbols::raw, deflate_alphabet::raw, deflate_huf_symbols::shift, and deflate_huf_symbols::start.
|
static |
Attempt to accumulate bits from input stream.
deflate | Decompressor |
in | Compressed input data |
target | Number of bits to accumulate |
excess | Number of excess bits accumulated (may be negative) |
Definition at line 307 of file deflate.c.
References deflate::accumulator, assert(), deflate::bits, copy_from_user(), deflate_reverse, in, and deflate::rotalumucca.
Referenced by deflate_decode(), deflate_extract(), and deflate_inflate().
|
static |
Consume accumulated bits from the input stream.
deflate | Decompressor |
count | Number of accumulated bits to consume |
data | Consumed bits |
Definition at line 343 of file deflate.c.
References deflate::accumulator, assert(), bits, deflate::bits, count, data, and deflate::rotalumucca.
Referenced by deflate_decode(), deflate_discard_to_byte(), and deflate_extract().
|
static |
Attempt to extract a fixed number of bits from input stream.
deflate | Decompressor |
in | Compressed input data |
target | Number of bits to extract |
data | Extracted bits (or negative if not yet accumulated) |
Definition at line 366 of file deflate.c.
References data, DBGCP, deflate_accumulate(), deflate_bin(), deflate_consume(), and in.
Referenced by deflate_inflate().
|
static |
Attempt to decode a Huffman-coded symbol from input stream.
deflate | Decompressor |
in | Compressed input data |
alphabet | Huffman alphabet |
code | Raw code (or negative if not yet accumulated) |
Definition at line 396 of file deflate.c.
References deflate_huf_symbols::bits, deflate::bits, DBGCP, deflate_accumulate(), deflate_bin(), deflate_consume(), DEFLATE_HUFFMAN_BITS, DEFLATE_HUFFMAN_QL_SHIFT, deflate_alphabet::huf, in, deflate_alphabet::lookup, raw, deflate_huf_symbols::raw, deflate::rotalumucca, deflate_huf_symbols::shift, and start.
Referenced by deflate_inflate().
|
static |
Discard bits up to the next byte boundary.
deflate | Decompressor |
Definition at line 443 of file deflate.c.
References deflate::bits, and deflate_consume().
Referenced by deflate_inflate().
|
static |
Copy data to output buffer (if available)
out | Output data buffer |
start | Source data |
offset | Starting offset within source data |
len | Length to copy |
Definition at line 456 of file deflate.c.
References len, memcpy_user(), offset, out, and start.
Referenced by deflate_inflate().
int deflate_inflate | ( | struct deflate * | deflate, |
struct deflate_chunk * | in, | ||
struct deflate_chunk * | out | ||
) |
Inflate compressed data.
deflate | Decompressor |
in | Compressed input data |
out | Output data buffer |
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 492 of file deflate.c.
References assert(), bits, cm, code, deflate_static_length_pattern::count, 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, ENOTSUP, extra, deflate::extra_bits, deflate_static_length_pattern::fill, deflate::format, deflate::header, header, 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, 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(), png_image_data(), and zlib_deflate().
void deflate_init | ( | struct deflate * | deflate, |
enum deflate_format | format | ||
) |
Initialise decompressor.
deflate | Decompressor |
format | Compression format code |
Definition at line 999 of file deflate.c.
References assert(), base, bit, bits, deflate_distance_base, deflate_litlen_base, deflate_reverse, format, deflate::format, and memset().
Referenced by deflate_okx(), png_pixbuf(), and zlib_deflate().
|
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().
|
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().
|
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().
|
static |
Code length map.
Definition at line 74 of file deflate.c.
Referenced by deflate_inflate().
|
static |
Static Huffman alphabet length patterns.
Definition at line 79 of file deflate.c.
Referenced by deflate_inflate().