iPXE
Functions | Variables
deflate.c File Reference

DEFLATE decompression algorithm. More...

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

Go to the source code of this file.

Functions

 FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
 
static const char * deflate_bin (unsigned long value, unsigned int bits)
 Transcribe binary value (for debugging) 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...
 

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  )

◆ deflate_bin()

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

Transcribe binary value (for debugging)

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

Definition at line 98 of file deflate.c.

98  {
99  static char buf[ ( 8 * sizeof ( value ) ) + 1 /* NUL */ ];
100  char *out = buf;
101 
102  /* Sanity check */
103  assert ( bits < sizeof ( buf ) );
104 
105  /* Transcribe value */
106  while ( bits-- )
107  *(out++) = ( ( value & ( 1 << bits ) ) ? '1' : '0' );
108  *out = '\0';
109 
110  return buf;
111 }
__be32 out[4]
Definition: CIB_PRM.h:36
assert((readw(&hdr->flags) &(GTF_reading|GTF_writing))==0)
pseudo_bit_t value[0x00020]
Definition: arbel.h:13
static volatile void * bits
Definition: bitops.h:27

References assert(), bits, out, and value.

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

◆ deflate_set_length()

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

Set Huffman symbol length.

Parameters
deflateDecompressor
indexIndex within lengths
bitsSymbol length (in bits)

Definition at line 120 of file deflate.c.

121  {
122 
123  deflate->lengths[ index / 2 ] |= ( bits << ( 4 * ( index % 2 ) ) );
124 }
static volatile void * bits
Definition: bitops.h:27
uint8_t lengths[((DEFLATE_LITLEN_MAX_CODE+1)+(DEFLATE_DISTANCE_MAX_CODE+1)+1)/2]
Huffman code lengths.
Definition: deflate.h:237
uint64_t index
Index of the first segment within the content.
Definition: pccrc.h:21
Decompressor.
Definition: deflate.h:156

References bits, index, and deflate::lengths.

Referenced by deflate_inflate().

◆ deflate_length()

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

Get Huffman symbol length.

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

Definition at line 133 of file deflate.c.

134  {
135 
136  return ( ( deflate->lengths[ index / 2 ] >> ( 4 * ( index % 2 ) ) )
137  & 0x0f );
138 }
uint8_t lengths[((DEFLATE_LITLEN_MAX_CODE+1)+(DEFLATE_DISTANCE_MAX_CODE+1)+1)/2]
Huffman code lengths.
Definition: deflate.h:237
uint64_t index
Index of the first segment within the content.
Definition: pccrc.h:21
Decompressor.
Definition: deflate.h:156

References index, and deflate::lengths.

Referenced by deflate_alphabet().

◆ deflate_alphabet_name()

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

Determine Huffman alphabet name (for debugging)

Parameters
deflateDecompressor
alphabetHuffman alphabet
Return values
nameAlphabet name

Definition at line 147 of file deflate.c.

148  {
149 
150  if ( alphabet == &deflate->litlen ) {
151  return "litlen";
152  } else if ( alphabet == &deflate->distance_codelen ) {
153  return "distance/codelen";
154  } else {
155  return "<UNKNOWN>";
156  }
157 }
struct deflate_alphabet distance_codelen
Distance and code length Huffman alphabet.
Definition: deflate.h:212
struct deflate_alphabet litlen
Literal/length Huffman alphabet.
Definition: deflate.h:194
Decompressor.
Definition: deflate.h:156

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

Referenced by deflate_alphabet(), and deflate_dump_alphabet().

◆ deflate_dump_alphabet()

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

Dump Huffman alphabet (for debugging)

Parameters
deflateDecompressor
alphabetHuffman alphabet

Definition at line 165 of file deflate.c.

166  {
167  struct deflate_huf_symbols *huf_sym;
168  unsigned int bits;
169  unsigned int huf;
170  unsigned int i;
171 
172  /* Do nothing unless debugging is enabled */
173  if ( ! DBG_EXTRA )
174  return;
175 
176  /* Dump symbol table for each utilised length */
177  for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
178  sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
179  huf_sym = &alphabet->huf[ bits - 1 ];
180  if ( huf_sym->freq == 0 )
181  continue;
182  huf = ( huf_sym->start >> huf_sym->shift );
183  DBGC2 ( alphabet, "DEFLATE %p \"%s\" length %d start \"%s\" "
184  "freq %d:", deflate,
185  deflate_alphabet_name ( deflate, alphabet ), bits,
186  deflate_bin ( huf, huf_sym->bits ), huf_sym->freq );
187  for ( i = 0 ; i < huf_sym->freq ; i++ ) {
188  DBGC2 ( alphabet, " %03x",
189  huf_sym->raw[ huf + i ] );
190  }
191  DBGC2 ( alphabet, "\n" );
192  }
193 
194  /* Dump quick lookup table */
195  DBGC2 ( alphabet, "DEFLATE %p \"%s\" quick lookup:", deflate,
196  deflate_alphabet_name ( deflate, alphabet ) );
197  for ( i = 0 ; i < ( sizeof ( alphabet->lookup ) /
198  sizeof ( alphabet->lookup[0] ) ) ; i++ ) {
199  DBGC2 ( alphabet, " %d", ( alphabet->lookup[i] + 1 ) );
200  }
201  DBGC2 ( alphabet, "\n" );
202 }
A Huffman-coded set of symbols of a given length.
Definition: deflate.h:115
uint32_t start
First symbol of this length (normalised to 16 bits)
Definition: deflate.h:128
static const char * deflate_bin(unsigned long value, unsigned int bits)
Transcribe binary value (for debugging)
Definition: deflate.c:98
uint8_t lookup[1<< DEFLATE_HUFFMAN_QL_BITS]
Quick lookup table.
Definition: deflate.h:138
struct deflate_huf_symbols huf[DEFLATE_HUFFMAN_BITS]
Huffman-coded symbol set for each length.
Definition: deflate.h:136
uint16_t freq
Number of Huffman-coded symbols having this length.
Definition: deflate.h:121
static const char * deflate_alphabet_name(struct deflate *deflate, struct deflate_alphabet *alphabet)
Determine Huffman alphabet name (for debugging)
Definition: deflate.c:147
uint16_t * raw
Raw symbols having this length.
Definition: deflate.h:130
static volatile void * bits
Definition: bitops.h:27
#define DBGC2(...)
Definition: compiler.h:522
#define DBG_EXTRA
Definition: compiler.h:319
uint8_t shift
Shift to normalise symbols of this length to 16 bits.
Definition: deflate.h:119
uint8_t bits
Length of Huffman-coded symbols.
Definition: deflate.h:117
Decompressor.
Definition: deflate.h:156

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

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

Construct Huffman alphabet.

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

Definition at line 213 of file deflate.c.

215  {
216  struct deflate_huf_symbols *huf_sym;
217  unsigned int huf;
218  unsigned int cum_freq;
219  unsigned int bits;
220  unsigned int raw;
221  unsigned int adjustment;
222  unsigned int prefix;
223  int complete;
224 
225  /* Clear symbol table */
226  memset ( alphabet->huf, 0, sizeof ( alphabet->huf ) );
227 
228  /* Count number of symbols with each Huffman-coded length */
229  for ( raw = 0 ; raw < count ; raw++ ) {
230  bits = deflate_length ( deflate, ( raw + offset ) );
231  if ( bits )
232  alphabet->huf[ bits - 1 ].freq++;
233  }
234 
235  /* Populate Huffman-coded symbol table */
236  huf = 0;
237  cum_freq = 0;
238  for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
239  sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
240  huf_sym = &alphabet->huf[ bits - 1 ];
241  huf_sym->bits = bits;
242  huf_sym->shift = ( 16 - bits );
243  huf_sym->start = ( huf << huf_sym->shift );
244  huf_sym->raw = &alphabet->raw[cum_freq];
245  huf += huf_sym->freq;
246  if ( huf > ( 1U << bits ) ) {
247  DBGC ( alphabet, "DEFLATE %p \"%s\" has too many "
248  "symbols with lengths <=%d\n", deflate,
249  deflate_alphabet_name ( deflate, alphabet ),
250  bits );
251  return -EINVAL;
252  }
253  huf <<= 1;
254  cum_freq += huf_sym->freq;
255  }
256  complete = ( huf == ( 1U << bits ) );
257 
258  /* Populate raw symbol table */
259  for ( raw = 0 ; raw < count ; raw++ ) {
260  bits = deflate_length ( deflate, ( raw + offset ) );
261  if ( bits ) {
262  huf_sym = &alphabet->huf[ bits - 1 ];
263  *(huf_sym->raw++) = raw;
264  }
265  }
266 
267  /* Adjust Huffman-coded symbol table raw pointers and populate
268  * quick lookup table.
269  */
270  for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
271  sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
272  huf_sym = &alphabet->huf[ bits - 1 ];
273 
274  /* Adjust raw pointer */
275  huf_sym->raw -= huf_sym->freq; /* Reset to first symbol */
276  adjustment = ( huf_sym->start >> huf_sym->shift );
277  huf_sym->raw -= adjustment; /* Adjust for quick indexing */
278 
279  /* Populate quick lookup table */
280  for ( prefix = ( huf_sym->start >> DEFLATE_HUFFMAN_QL_SHIFT ) ;
281  prefix < ( 1 << DEFLATE_HUFFMAN_QL_BITS ) ; prefix++ ) {
282  alphabet->lookup[prefix] = ( bits - 1 );
283  }
284  }
285 
286  /* Dump alphabet (for debugging) */
287  deflate_dump_alphabet ( deflate, alphabet );
288 
289  /* Check that there are no invalid codes */
290  if ( ! complete ) {
291  DBGC ( alphabet, "DEFLATE %p \"%s\" is incomplete\n", deflate,
292  deflate_alphabet_name ( deflate, alphabet ) );
293  return -EINVAL;
294  }
295 
296  return 0;
297 }
#define EINVAL
Invalid argument.
Definition: errno.h:428
#define DEFLATE_HUFFMAN_QL_SHIFT
Quick lookup shift.
Definition: deflate.h:82
#define DBGC(...)
Definition: compiler.h:505
uint16_t raw[0]
Raw symbols.
Definition: deflate.h:144
A Huffman-coded set of symbols of a given length.
Definition: deflate.h:115
char prefix[4]
Definition: vmconsole.c:53
uint32_t start
First symbol of this length (normalised to 16 bits)
Definition: deflate.h:128
static unsigned int deflate_length(struct deflate *deflate, unsigned int index)
Get Huffman symbol length.
Definition: deflate.c:133
static void deflate_dump_alphabet(struct deflate *deflate, struct deflate_alphabet *alphabet)
Dump Huffman alphabet (for debugging)
Definition: deflate.c:165
#define DEFLATE_HUFFMAN_QL_BITS
Quick lookup length for a Huffman symbol (in bits)
Definition: deflate.h:79
uint8_t lookup[1<< DEFLATE_HUFFMAN_QL_BITS]
Quick lookup table.
Definition: deflate.h:138
static userptr_t size_t offset
Offset of the first segment within the content.
Definition: deflate.h:259
struct deflate_huf_symbols huf[DEFLATE_HUFFMAN_BITS]
Huffman-coded symbol set for each length.
Definition: deflate.h:136
uint16_t freq
Number of Huffman-coded symbols having this length.
Definition: deflate.h:121
static const char * deflate_alphabet_name(struct deflate *deflate, struct deflate_alphabet *alphabet)
Determine Huffman alphabet name (for debugging)
Definition: deflate.c:147
uint16_t * raw
Raw symbols having this length.
Definition: deflate.h:130
static volatile void * bits
Definition: bitops.h:27
uint16_t count
Number of entries.
Definition: ena.h:22
__be32 raw[7]
Definition: CIB_PRM.h:28
uint8_t shift
Shift to normalise symbols of this length to 16 bits.
Definition: deflate.h:119
uint8_t bits
Length of Huffman-coded symbols.
Definition: deflate.h:117
void * memset(void *dest, int character, size_t len) __nonnull
Decompressor.
Definition: deflate.h:156

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.

◆ deflate_accumulate()

static int deflate_accumulate ( struct deflate deflate,
struct deflate_chunk in,
unsigned int  target 
)
static

Attempt to accumulate bits from input stream.

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

Definition at line 307 of file deflate.c.

309  {
310  uint8_t byte;
311 
312  while ( deflate->bits < target ) {
313 
314  /* Check for end of input */
315  if ( in->offset >= in->len )
316  break;
317 
318  /* Acquire byte from input */
319  copy_from_user ( &byte, in->data, in->offset++,
320  sizeof ( byte ) );
322  ( byte << deflate->bits ) );
324  ( deflate_reverse[byte] <<
325  ( 24 - deflate->bits ) ) );
326  deflate->bits += 8;
327 
328  /* Sanity check */
329  assert ( deflate->bits <=
330  ( 8 * sizeof ( deflate->accumulator ) ) );
331  }
332 
333  return ( deflate->bits - target );
334 }
__be32 in[4]
Definition: CIB_PRM.h:35
static __always_inline void copy_from_user(void *dest, userptr_t src, off_t src_off, size_t len)
Copy data from user buffer.
Definition: uaccess.h:337
unsigned int bits
Number of bits within the accumulator.
Definition: deflate.h:174
uint32_t accumulator
Accumulator.
Definition: deflate.h:167
assert((readw(&hdr->flags) &(GTF_reading|GTF_writing))==0)
uint32_t rotalumucca
Bit-reversed accumulator.
Definition: deflate.h:172
unsigned char uint8_t
Definition: stdint.h:10
unsigned char byte
Definition: smc9000.h:38
static uint8_t deflate_reverse[256]
Byte reversal table.
Definition: deflate.c:51
Decompressor.
Definition: deflate.h:156

References deflate::accumulator, assert(), deflate::bits, copy_from_user(), deflate_reverse, in, and deflate::rotalumucca.

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

◆ deflate_consume()

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

Consume accumulated bits from the input stream.

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

Definition at line 343 of file deflate.c.

343  {
344  int data;
345 
346  /* Sanity check */
347  assert ( count <= deflate->bits );
348 
349  /* Extract data and consume bits */
350  data = ( deflate->accumulator & ( ( 1 << count ) - 1 ) );
353  deflate->bits -= count;
354 
355  return data;
356 }
unsigned int bits
Number of bits within the accumulator.
Definition: deflate.h:174
uint32_t accumulator
Accumulator.
Definition: deflate.h:167
assert((readw(&hdr->flags) &(GTF_reading|GTF_writing))==0)
uint32_t rotalumucca
Bit-reversed accumulator.
Definition: deflate.h:172
static volatile void * bits
Definition: bitops.h:27
uint16_t count
Number of entries.
Definition: ena.h:22
uint8_t data[48]
Additional event data.
Definition: ena.h:22
Decompressor.
Definition: deflate.h:156

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

static int deflate_extract ( struct deflate deflate,
struct deflate_chunk in,
unsigned int  target 
)
static

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

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

Definition at line 366 of file deflate.c.

367  {
368  int excess;
369  int data;
370 
371  /* Return immediately if we are attempting to extract zero bits */
372  if ( target == 0 )
373  return 0;
374 
375  /* Attempt to accumulate bits */
376  excess = deflate_accumulate ( deflate, in, target );
377  if ( excess < 0 )
378  return excess;
379 
380  /* Extract data and consume bits */
381  data = deflate_consume ( deflate, target );
382  DBGCP ( deflate, "DEFLATE %p extracted %s = %#x = %d\n", deflate,
383  deflate_bin ( data, target ), data, data );
384 
385  return data;
386 }
__be32 in[4]
Definition: CIB_PRM.h:35
static const char * deflate_bin(unsigned long value, unsigned int bits)
Transcribe binary value (for debugging)
Definition: deflate.c:98
static int deflate_consume(struct deflate *deflate, unsigned int count)
Consume accumulated bits from the input stream.
Definition: deflate.c:343
static int deflate_accumulate(struct deflate *deflate, struct deflate_chunk *in, unsigned int target)
Attempt to accumulate bits from input stream.
Definition: deflate.c:307
uint8_t data[48]
Additional event data.
Definition: ena.h:22
#define DBGCP(...)
Definition: compiler.h:539
Decompressor.
Definition: deflate.h:156

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

Referenced by deflate_inflate().

◆ deflate_decode()

static int deflate_decode ( struct deflate deflate,
struct deflate_chunk in,
struct deflate_alphabet alphabet 
)
static

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

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

Definition at line 396 of file deflate.c.

398  {
399  struct deflate_huf_symbols *huf_sym;
400  uint16_t huf;
401  unsigned int lookup_index;
402  int excess;
403  unsigned int raw;
404 
405  /* Attempt to accumulate maximum required number of bits.
406  * There may be fewer bits than this remaining in the stream,
407  * even if the stream still contains some complete
408  * Huffman-coded symbols.
409  */
411 
412  /* Normalise the bit-reversed accumulated value to 16 bits */
413  huf = ( deflate->rotalumucca >> 16 );
414 
415  /* Find symbol set for this length */
416  lookup_index = ( huf >> DEFLATE_HUFFMAN_QL_SHIFT );
417  huf_sym = &alphabet->huf[ alphabet->lookup[ lookup_index ] ];
418  while ( huf < huf_sym->start )
419  huf_sym--;
420 
421  /* Calculate number of excess bits, and return if not yet complete */
422  excess = ( deflate->bits - huf_sym->bits );
423  if ( excess < 0 )
424  return excess;
425 
426  /* Consume bits */
427  deflate_consume ( deflate, huf_sym->bits );
428 
429  /* Look up raw symbol */
430  raw = huf_sym->raw[ huf >> huf_sym->shift ];
431  DBGCP ( deflate, "DEFLATE %p decoded %s = %#x = %d\n", deflate,
432  deflate_bin ( ( huf >> huf_sym->shift ), huf_sym->bits ),
433  raw, raw );
434 
435  return raw;
436 }
unsigned short uint16_t
Definition: stdint.h:11
__be32 in[4]
Definition: CIB_PRM.h:35
#define DEFLATE_HUFFMAN_QL_SHIFT
Quick lookup shift.
Definition: deflate.h:82
#define DEFLATE_HUFFMAN_BITS
Maximum length of a Huffman symbol (in bits)
Definition: deflate.h:73
A Huffman-coded set of symbols of a given length.
Definition: deflate.h:115
unsigned int bits
Number of bits within the accumulator.
Definition: deflate.h:174
static const char * deflate_bin(unsigned long value, unsigned int bits)
Transcribe binary value (for debugging)
Definition: deflate.c:98
uint32_t start
Starting offset.
Definition: netvsc.h:12
uint8_t lookup[1<< DEFLATE_HUFFMAN_QL_BITS]
Quick lookup table.
Definition: deflate.h:138
struct deflate_huf_symbols huf[DEFLATE_HUFFMAN_BITS]
Huffman-coded symbol set for each length.
Definition: deflate.h:136
uint32_t rotalumucca
Bit-reversed accumulator.
Definition: deflate.h:172
static int deflate_consume(struct deflate *deflate, unsigned int count)
Consume accumulated bits from the input stream.
Definition: deflate.c:343
uint16_t * raw
Raw symbols having this length.
Definition: deflate.h:130
static int deflate_accumulate(struct deflate *deflate, struct deflate_chunk *in, unsigned int target)
Attempt to accumulate bits from input stream.
Definition: deflate.c:307
#define DBGCP(...)
Definition: compiler.h:539
__be32 raw[7]
Definition: CIB_PRM.h:28
uint8_t shift
Shift to normalise symbols of this length to 16 bits.
Definition: deflate.h:119
uint8_t bits
Length of Huffman-coded symbols.
Definition: deflate.h:117
Decompressor.
Definition: deflate.h:156

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

◆ deflate_discard_to_byte()

static void deflate_discard_to_byte ( struct deflate deflate)
static

Discard bits up to the next byte boundary.

Parameters
deflateDecompressor

Definition at line 443 of file deflate.c.

443  {
444 
445  deflate_consume ( deflate, ( deflate->bits & 7 ) );
446 }
unsigned int bits
Number of bits within the accumulator.
Definition: deflate.h:174
static int deflate_consume(struct deflate *deflate, unsigned int count)
Consume accumulated bits from the input stream.
Definition: deflate.c:343
Decompressor.
Definition: deflate.h:156

References deflate::bits, and deflate_consume().

Referenced by deflate_inflate().

◆ deflate_copy()

static void deflate_copy ( struct deflate_chunk out,
userptr_t  start,
size_t  offset,
size_t  len 
)
static

Copy data to output buffer (if available)

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

Definition at line 456 of file deflate.c.

457  {
458  size_t out_offset = out->offset;
459  size_t copy_len;
460 
461  /* Copy data one byte at a time, to allow for overlap */
462  if ( out_offset < out->len ) {
463  copy_len = ( out->len - out_offset );
464  if ( copy_len > len )
465  copy_len = len;
466  while ( copy_len-- ) {
467  memcpy_user ( out->data, out_offset++,
468  start, offset++, 1 );
469  }
470  }
471  out->offset += len;
472 }
__be32 out[4]
Definition: CIB_PRM.h:36
uint32_t start
Starting offset.
Definition: netvsc.h:12
static userptr_t size_t offset
Offset of the first segment within the content.
Definition: deflate.h:259
uint32_t len
Length.
Definition: ena.h:14
void memcpy_user(userptr_t dest, off_t dest_off, userptr_t src, off_t src_off, size_t len)
Copy data between user buffers.

References len, memcpy_user(), offset, out, and start.

Referenced by deflate_inflate().

◆ deflate_inflate()

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.

494  {
495 
496  /* This could be implemented more neatly if gcc offered a
497  * means for enforcing tail recursion.
498  */
499  if ( deflate->resume ) {
500  goto *(deflate->resume);
501  } else switch ( deflate->format ) {
502  case DEFLATE_RAW: goto block_header;
503  case DEFLATE_ZLIB: goto zlib_header;
504  default: assert ( 0 );
505  }
506 
507  zlib_header: {
508  int header;
509  int cm;
510 
511  /* Extract header */
513  if ( header < 0 ) {
514  deflate->resume = &&zlib_header;
515  return 0;
516  }
517 
518  /* Parse header */
520  if ( cm != ZLIB_HEADER_CM_DEFLATE ) {
521  DBGC ( deflate, "DEFLATE %p unsupported ZLIB "
522  "compression method %d\n", deflate, cm );
523  return -ENOTSUP;
524  }
525  if ( header & ( 1 << ZLIB_HEADER_FDICT_BIT ) ) {
526  DBGC ( deflate, "DEFLATE %p unsupported ZLIB preset "
527  "dictionary\n", deflate );
528  return -ENOTSUP;
529  }
530 
531  /* Process first block header */
532  goto block_header;
533  }
534 
535  block_header: {
536  int header;
537  int bfinal;
538  int btype;
539 
540  /* Extract block header */
542  if ( header < 0 ) {
543  deflate->resume = &&block_header;
544  return 0;
545  }
546 
547  /* Parse header */
548  deflate->header = header;
549  bfinal = ( header & ( 1 << DEFLATE_HEADER_BFINAL_BIT ) );
550  btype = ( header >> DEFLATE_HEADER_BTYPE_LSB );
551  DBGC ( deflate, "DEFLATE %p found %sblock type %#x\n",
552  deflate, ( bfinal ? "final " : "" ), btype );
553  switch ( btype ) {
555  goto literal_block;
557  goto static_block;
559  goto dynamic_block;
560  default:
561  DBGC ( deflate, "DEFLATE %p unsupported block type "
562  "%#x\n", deflate, btype );
563  return -ENOTSUP;
564  }
565  }
566 
567  literal_block: {
568 
569  /* Discard any bits up to the next byte boundary */
571  }
572 
573  literal_len: {
574  int len;
575 
576  /* Extract LEN field */
578  if ( len < 0 ) {
579  deflate->resume = &&literal_len;
580  return 0;
581  }
582 
583  /* Record length of literal data */
584  deflate->remaining = len;
585  DBGC2 ( deflate, "DEFLATE %p literal block length %#04zx\n",
587  }
588 
589  literal_nlen: {
590  int nlen;
591 
592  /* Extract NLEN field */
594  if ( nlen < 0 ) {
595  deflate->resume = &&literal_nlen;
596  return 0;
597  }
598 
599  /* Verify NLEN */
600  if ( ( ( deflate->remaining ^ ~nlen ) &
601  ( ( 1 << DEFLATE_LITERAL_LEN_BITS ) - 1 ) ) != 0 ) {
602  DBGC ( deflate, "DEFLATE %p invalid len/nlen "
603  "%#04zx/%#04x\n", deflate,
604  deflate->remaining, nlen );
605  return -EINVAL;
606  }
607  }
608 
609  literal_data: {
610  size_t in_remaining;
611  size_t len;
612 
613  /* Calculate available amount of literal data */
614  in_remaining = ( in->len - in->offset );
615  len = deflate->remaining;
616  if ( len > in_remaining )
617  len = in_remaining;
618 
619  /* Copy data to output buffer */
620  deflate_copy ( out, in->data, in->offset, len );
621 
622  /* Consume data from input buffer */
623  in->offset += len;
624  deflate->remaining -= len;
625 
626  /* Finish processing if we are blocked */
627  if ( deflate->remaining ) {
628  deflate->resume = &&literal_data;
629  return 0;
630  }
631 
632  /* Otherwise, finish block */
633  goto block_done;
634  }
635 
636  static_block: {
637  struct deflate_static_length_pattern *pattern;
638  uint8_t *lengths = deflate->lengths;
639 
640  /* Construct static Huffman lengths as per RFC 1950 */
641  for ( pattern = deflate_static_length_patterns ;
642  pattern->count ; pattern++ ) {
643  memset ( lengths, pattern->fill, pattern->count );
644  lengths += pattern->count;
645  }
646  deflate->litlen_count = 288;
647  deflate->distance_count = 32;
648  goto construct_alphabets;
649  }
650 
651  dynamic_block:
652 
653  dynamic_header: {
654  int header;
655  unsigned int hlit;
656  unsigned int hdist;
657  unsigned int hclen;
658 
659  /* Extract block header */
661  if ( header < 0 ) {
662  deflate->resume = &&dynamic_header;
663  return 0;
664  }
665 
666  /* Parse header */
667  hlit = ( ( header >> DEFLATE_DYNAMIC_HLIT_LSB ) &
669  hdist = ( ( header >> DEFLATE_DYNAMIC_HDIST_LSB ) &
671  hclen = ( ( header >> DEFLATE_DYNAMIC_HCLEN_LSB ) &
673  deflate->litlen_count = ( hlit + 257 );
674  deflate->distance_count = ( hdist + 1 );
675  deflate->length_index = 0;
676  deflate->length_target = ( hclen + 4 );
677  DBGC2 ( deflate, "DEFLATE %p dynamic block %d codelen, %d "
678  "litlen, %d distance\n", deflate,
681 
682  /* Prepare for decoding code length code lengths */
683  memset ( &deflate->lengths, 0, sizeof ( deflate->lengths ) );
684  }
685 
686  dynamic_codelen: {
687  int len;
688  unsigned int index;
689  int rc;
690 
691  /* Extract all code lengths */
692  while ( deflate->length_index < deflate->length_target ) {
693 
694  /* Extract code length length */
697  if ( len < 0 ) {
698  deflate->resume = &&dynamic_codelen;
699  return 0;
700  }
701 
702  /* Store code length */
705  DBGCP ( deflate, "DEFLATE %p codelen for %d is %d\n",
706  deflate, index, len );
707  }
708 
709  /* Generate code length alphabet */
710  if ( ( rc = deflate_alphabet ( deflate,
712  ( DEFLATE_CODELEN_MAX_CODE + 1 ),
713  0 ) ) != 0 )
714  return rc;
715 
716  /* Prepare for decoding literal/length/distance code lengths */
717  memset ( &deflate->lengths, 0, sizeof ( deflate->lengths ) );
718  deflate->length_index = 0;
721  deflate->length = 0;
722  }
723 
724  dynamic_litlen_distance: {
725  int len;
726  int index;
727 
728  /* Decode literal/length/distance code length */
730  if ( len < 0 ) {
731  deflate->resume = &&dynamic_litlen_distance;
732  return 0;
733  }
734 
735  /* Prepare for extra bits */
736  if ( len < 16 ) {
737  deflate->length = len;
738  deflate->extra_bits = 0;
739  deflate->dup_len = 1;
740  } else {
741  static const uint8_t dup_len[3] = { 3, 3, 11 };
742  static const uint8_t extra_bits[3] = { 2, 3, 7 };
743  index = ( len - 16 );
744  deflate->dup_len = dup_len[index];
745  deflate->extra_bits = extra_bits[index];
746  if ( index )
747  deflate->length = 0;
748  }
749  }
750 
751  dynamic_litlen_distance_extra: {
752  int extra;
753  unsigned int dup_len;
754 
755  /* Extract extra bits */
757  if ( extra < 0 ) {
758  deflate->resume = &&dynamic_litlen_distance_extra;
759  return 0;
760  }
761 
762  /* Store code lengths */
763  dup_len = ( deflate->dup_len + extra );
764  while ( ( deflate->length_index < deflate->length_target ) &&
765  dup_len-- ) {
767  deflate->length );
768  }
769 
770  /* Process next literal/length or distance code
771  * length, if more are required.
772  */
774  goto dynamic_litlen_distance;
775 
776  /* Construct alphabets */
777  goto construct_alphabets;
778  }
779 
780  construct_alphabets: {
781  unsigned int distance_offset = deflate->litlen_count;
782  unsigned int distance_count = deflate->distance_count;
783  int rc;
784 
785  /* Generate literal/length alphabet */
786  if ( ( rc = deflate_alphabet ( deflate, &deflate->litlen,
787  deflate->litlen_count, 0 ) ) !=0)
788  return rc;
789 
790  /* Handle degenerate case of a single distance code
791  * (for which it is impossible to construct a valid,
792  * complete Huffman alphabet). RFC 1951 states:
793  *
794  * If only one distance code is used, it is encoded
795  * using one bit, not zero bits; in this case there
796  * is a single code length of one, with one unused
797  * code. One distance code of zero bits means that
798  * there are no distance codes used at all (the data
799  * is all literals).
800  *
801  * If we have only a single distance code, then we
802  * instead use two distance codes both with length 1.
803  * This results in a valid Huffman alphabet. The code
804  * "0" will mean distance code 0 (which is either
805  * correct or irrelevant), and the code "1" will mean
806  * distance code 1 (which is always irrelevant).
807  */
808  if ( deflate->distance_count == 1 ) {
809 
810  deflate->lengths[0] = 0x11;
811  distance_offset = 0;
812  distance_count = 2;
813  }
814 
815  /* Generate distance alphabet */
816  if ( ( rc = deflate_alphabet ( deflate,
818  distance_count,
819  distance_offset ) ) != 0 )
820  return rc;
821  }
822 
823  lzhuf_litlen: {
824  int code;
825  uint8_t byte;
826  unsigned int extra;
827  unsigned int bits;
828 
829  /* Decode Huffman codes */
830  while ( 1 ) {
831 
832  /* Decode Huffman code */
834  if ( code < 0 ) {
835  deflate->resume = &&lzhuf_litlen;
836  return 0;
837  }
838 
839  /* Handle according to code type */
840  if ( code < DEFLATE_LITLEN_END ) {
841 
842  /* Literal value: copy to output buffer */
843  byte = code;
844  DBGCP ( deflate, "DEFLATE %p literal %#02x "
845  "('%c')\n", deflate, byte,
846  ( isprint ( byte ) ? byte : '.' ) );
847  deflate_copy ( out, virt_to_user ( &byte ), 0,
848  sizeof ( byte ) );
849 
850  } else if ( code == DEFLATE_LITLEN_END ) {
851 
852  /* End of block */
853  goto block_done;
854 
855  } else {
856 
857  /* Length code: process extra bits */
858  extra = ( code - DEFLATE_LITLEN_END - 1 );
859  if ( extra < 28 ) {
860  bits = ( extra / 4 );
861  if ( bits )
862  bits--;
864  deflate->dup_len =
866  } else {
867  deflate->extra_bits = 0;
868  deflate->dup_len = 258;
869  }
870  goto lzhuf_litlen_extra;
871  }
872  }
873  }
874 
875  lzhuf_litlen_extra: {
876  int extra;
877 
878  /* Extract extra bits */
880  if ( extra < 0 ) {
881  deflate->resume = &&lzhuf_litlen_extra;
882  return 0;
883  }
884 
885  /* Update duplicate length */
886  deflate->dup_len += extra;
887  }
888 
889  lzhuf_distance: {
890  int code;
891  unsigned int extra;
892  unsigned int bits;
893 
894  /* Decode Huffman code */
897  if ( code < 0 ) {
898  deflate->resume = &&lzhuf_distance;
899  return 0;
900  }
901 
902  /* Process extra bits */
903  extra = code;
904  bits = ( extra / 2 );
905  if ( bits )
906  bits--;
909  }
910 
911  lzhuf_distance_extra: {
912  int extra;
913  size_t dup_len;
914  size_t dup_distance;
915 
916  /* Extract extra bits */
918  if ( extra < 0 ) {
919  deflate->resume = &&lzhuf_distance_extra;
920  return 0;
921  }
922 
923  /* Update duplicate distance */
924  dup_distance = ( deflate->dup_distance + extra );
925  dup_len = deflate->dup_len;
926  DBGCP ( deflate, "DEFLATE %p duplicate length %zd distance "
927  "%zd\n", deflate, dup_len, dup_distance );
928 
929  /* Sanity check */
930  if ( dup_distance > out->offset ) {
931  DBGC ( deflate, "DEFLATE %p bad distance %zd (max "
932  "%zd)\n", deflate, dup_distance, out->offset );
933  return -EINVAL;
934  }
935 
936  /* Copy data, allowing for overlap */
937  deflate_copy ( out, out->data, ( out->offset - dup_distance ),
938  dup_len );
939 
940  /* Process next literal/length symbol */
941  goto lzhuf_litlen;
942  }
943 
944  block_done: {
945 
946  DBGCP ( deflate, "DEFLATE %p end of block\n", deflate );
947 
948  /* If this was not the final block, process next block header */
949  if ( ! ( deflate->header & ( 1 << DEFLATE_HEADER_BFINAL_BIT ) ))
950  goto block_header;
951 
952  /* Otherwise, process footer (if any) */
953  switch ( deflate->format ) {
954  case DEFLATE_RAW: goto finished;
955  case DEFLATE_ZLIB: goto zlib_footer;
956  default: assert ( 0 );
957  }
958  }
959 
960  zlib_footer: {
961 
962  /* Discard any bits up to the next byte boundary */
964  }
965 
966  zlib_adler32: {
967  int excess;
968 
969  /* Accumulate the 32 bits of checksum. We don't check
970  * the value, stop processing immediately afterwards,
971  * and so don't have to worry about the nasty corner
972  * cases involved in calling deflate_extract() to
973  * obtain a full 32 bits.
974  */
976  if ( excess < 0 ) {
977  deflate->resume = &&zlib_adler32;
978  return 0;
979  }
980 
981  /* Finish processing */
982  goto finished;
983  }
984 
985  finished: {
986  /* Mark as finished and terminate */
987  DBGCP ( deflate, "DEFLATE %p finished\n", deflate );
988  deflate->resume = NULL;
989  return 0;
990  }
991 }
#define EINVAL
Invalid argument.
Definition: errno.h:428
static void deflate_set_length(struct deflate *deflate, unsigned int index, unsigned int bits)
Set Huffman symbol length.
Definition: deflate.c:120
struct arbelprm_rc_send_wqe rc
Definition: arbel.h:14
unsigned int length_index
Current length index within a set of code lengths.
Definition: deflate.h:181
#define DEFLATE_DYNAMIC_HLIT_LSB
Dynamic header HLIT field LSB.
Definition: deflate.h:52
static uint16_t deflate_distance_base[32]
Distance base values.
Definition: deflate.c:71
__be32 in[4]
Definition: CIB_PRM.h:35
static void deflate_copy(struct deflate_chunk *out, userptr_t start, size_t offset, size_t len)
Copy data to output buffer (if available)
Definition: deflate.c:456
#define DEFLATE_CODELEN_BITS
Dynamic header code length length (in bits)
Definition: deflate.h:70
struct deflate_alphabet distance_codelen
Distance and code length Huffman alphabet.
Definition: deflate.h:212
unsigned int length_target
Target length index within a set of code lengths.
Definition: deflate.h:183
uint8_t extra
Signature extra byte.
Definition: smbios.h:17
#define DEFLATE_DYNAMIC_HCLEN_MASK
Dynamic header HCLEN field mask.
Definition: deflate.h:67
unsigned int extra_bits
Number of extra bits required.
Definition: deflate.h:187
size_t dup_distance
Distance of a duplicated string.
Definition: deflate.h:191
#define DEFLATE_HEADER_BTYPE_STATIC
Block header type: static Huffman alphabet.
Definition: deflate.h:40
unsigned int header
Current block header.
Definition: deflate.h:177
#define DBGC(...)
Definition: compiler.h:505
enum deflate_format format
Format.
Definition: deflate.h:164
unsigned int length
Current length within a set of code lengths.
Definition: deflate.h:185
#define ZLIB_ADLER32_BITS
ZLIB ADLER32 length (in bits)
Definition: deflate.h:112
A Huffman-coded alphabet.
Definition: deflate.h:134
#define DEFLATE_LITLEN_END
Literal/length end of block code.
Definition: deflate.h:85
#define DEFLATE_DYNAMIC_HDIST_MASK
Dynamic header HDIST field mask.
Definition: deflate.h:61
uint8_t count
Repetition count.
Definition: deflate.h:152
struct ib_mad_cm cm
Definition: ib_mad.h:14
__be32 out[4]
Definition: CIB_PRM.h:36
#define ENOTSUP
Operation not supported.
Definition: errno.h:589
static int isprint(int character)
Check if character is printable.
Definition: ctype.h:97
#define DEFLATE_DYNAMIC_HCLEN_LSB
Dynamic header HCLEN field LSB.
Definition: deflate.h:64
#define DEFLATE_HEADER_BTYPE_LSB
Block header type LSB.
Definition: deflate.h:31
#define ZLIB_HEADER_BITS
ZLIB header length (in bits)
Definition: deflate.h:97
#define DEFLATE_LITERAL_LEN_BITS
Literal header LEN/NLEN field length (in bits)
Definition: deflate.h:46
size_t dup_len
Length of a duplicated string.
Definition: deflate.h:189
#define ZLIB_HEADER_CM_DEFLATE
ZLIB header compression method: DEFLATE.
Definition: deflate.h:106
assert((readw(&hdr->flags) &(GTF_reading|GTF_writing))==0)
void * resume
Resume point.
Definition: deflate.h:162
ZLIB header and footer.
Definition: deflate.h:21
#define DEFLATE_DYNAMIC_HLIT_MASK
Dynamic header HLIT field mask.
Definition: deflate.h:55
uint8_t fill
Length pair.
Definition: deflate.h:150
#define DEFLATE_CODELEN_MAX_CODE
Maximum value of a code length code.
Definition: deflate.h:94
unsigned char uint8_t
Definition: stdint.h:10
unsigned int distance_count
Number of symbols in the distance Huffman alphabet.
Definition: deflate.h:220
static uint8_t deflate_litlen_base[28]
Literal/length base values.
Definition: deflate.c:62
unsigned char byte
Definition: smc9000.h:38
struct deflate_alphabet litlen
Literal/length Huffman alphabet.
Definition: deflate.h:194
static int deflate_accumulate(struct deflate *deflate, struct deflate_chunk *in, unsigned int target)
Attempt to accumulate bits from input stream.
Definition: deflate.c:307
static uint8_t deflate_codelen_map[19]
Code length map.
Definition: deflate.c:74
#define DEFLATE_DYNAMIC_BITS
Dynamic header length (in bits)
Definition: deflate.h:49
Raw DEFLATE data (no header or footer)
Definition: deflate.h:19
uint8_t code
Response code.
Definition: scsi.h:16
static volatile void * bits
Definition: bitops.h:27
uint32_t len
Length.
Definition: ena.h:14
#define DBGC2(...)
Definition: compiler.h:522
A static Huffman alphabet length pattern.
Definition: deflate.h:148
#define DEFLATE_HEADER_BTYPE_LITERAL
Block header type: literal data.
Definition: deflate.h:37
struct ena_aq_header header
Header.
Definition: ena.h:12
userptr_t virt_to_user(volatile const void *addr)
Convert virtual address to user pointer.
#define DEFLATE_HEADER_BITS
Block header length (in bits)
Definition: deflate.h:25
#define ZLIB_HEADER_CM_MASK
ZLIB header compression method mask.
Definition: deflate.h:103
static struct deflate_static_length_pattern deflate_static_length_patterns[]
Static Huffman alphabet length patterns.
Definition: deflate.c:79
#define DBGCP(...)
Definition: compiler.h:539
unsigned int litlen_count
Number of symbols in the literal/length Huffman alphabet.
Definition: deflate.h:201
#define ZLIB_HEADER_CM_LSB
ZLIB header compression method LSB.
Definition: deflate.h:100
#define DEFLATE_HEADER_BFINAL_BIT
Block header final block flags bit.
Definition: deflate.h:28
uint8_t lengths[((DEFLATE_LITLEN_MAX_CODE+1)+(DEFLATE_DISTANCE_MAX_CODE+1)+1)/2]
Huffman code lengths.
Definition: deflate.h:237
static void deflate_discard_to_byte(struct deflate *deflate)
Discard bits up to the next byte boundary.
Definition: deflate.c:443
uint64_t index
Index of the first segment within the content.
Definition: pccrc.h:21
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.
Definition: deflate.c:366
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.
Definition: deflate.c:396
#define ZLIB_HEADER_FDICT_BIT
ZLIB header preset dictionary flag bit.
Definition: deflate.h:109
#define NULL
NULL pointer (VOID *)
Definition: Base.h:321
#define DEFLATE_DYNAMIC_HDIST_LSB
Dynamic header HDIST field LSB.
Definition: deflate.h:58
size_t remaining
Remaining length of data (e.g.
Definition: deflate.h:179
void * memset(void *dest, int character, size_t len) __nonnull
#define DEFLATE_HEADER_BTYPE_DYNAMIC
Block header type: dynamic Huffman alphabet.
Definition: deflate.h:43
Decompressor.
Definition: deflate.h:156

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

◆ deflate_init()

void deflate_init ( struct deflate deflate,
enum deflate_format  format 
)

Initialise decompressor.

Parameters
deflateDecompressor
formatCompression format code

Definition at line 999 of file deflate.c.

999  {
1000  static int global_init_done;
1001  uint8_t i;
1002  uint8_t bit;
1003  uint8_t byte;
1004  unsigned int base;
1005  unsigned int bits;
1006 
1007  /* Perform global initialisation if required */
1008  if ( ! global_init_done ) {
1009 
1010  /* Initialise byte reversal table */
1011  for ( i = 255 ; i ; i-- ) {
1012  for ( bit = 1, byte = 0 ; bit ; bit <<= 1 ) {
1013  byte <<= 1;
1014  if ( i & bit )
1015  byte |= 1;
1016  }
1017  deflate_reverse[i] = byte;
1018  }
1019 
1020  /* Initialise literal/length extra bits table */
1021  base = 3;
1022  for ( i = 0 ; i < 28 ; i++ ) {
1023  bits = ( i / 4 );
1024  if ( bits )
1025  bits--;
1027  base += ( 1 << bits );
1028  }
1029  assert ( base == 259 ); /* sic */
1030 
1031  /* Initialise distance extra bits table */
1032  base = 1;
1033  for ( i = 0 ; i < 30 ; i++ ) {
1034  bits = ( i / 2 );
1035  if ( bits )
1036  bits--;
1038  base += ( 1 << bits );
1039  }
1040  assert ( base == 32769 );
1041 
1042  /* Record global initialisation as complete */
1043  global_init_done = 1;
1044  }
1045 
1046  /* Initialise structure */
1047  memset ( deflate, 0, sizeof ( *deflate ) );
1048  deflate->format = format;
1049 }
static uint16_t deflate_distance_base[32]
Distance base values.
Definition: deflate.c:71
static unsigned int unsigned int bit
Definition: bigint.h:208
enum deflate_format format
Format.
Definition: deflate.h:164
static const void * base
Base address.
Definition: crypto.h:335
assert((readw(&hdr->flags) &(GTF_reading|GTF_writing))==0)
unsigned char uint8_t
Definition: stdint.h:10
static uint8_t deflate_litlen_base[28]
Literal/length base values.
Definition: deflate.c:62
unsigned char byte
Definition: smc9000.h:38
static volatile void * bits
Definition: bitops.h:27
int const char * format
Definition: xfer.h:104
static uint8_t deflate_reverse[256]
Byte reversal table.
Definition: deflate.c:51
void * memset(void *dest, int character, size_t len) __nonnull
Decompressor.
Definition: deflate.h:156

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

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.

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.

Referenced by deflate_inflate().