iPXE
Data Structures | Macros | 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...
 

Macros

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

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. More...
 
static int deflate_finished (struct deflate *deflate)
 Check if decompression has finished. More...
 
void deflate_init (struct deflate *deflate, enum deflate_format format)
 Initialise decompressor. More...
 
int deflate_inflate (struct deflate *deflate, struct deflate_chunk *in, struct deflate_chunk *out)
 Inflate compressed data. More...
 

Variables

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

Detailed Description

DEFLATE decompression algorithm.

Definition in file deflate.h.

Macro Definition Documentation

◆ DEFLATE_HEADER_BITS

#define DEFLATE_HEADER_BITS   3

Block header length (in bits)

Definition at line 25 of file deflate.h.

◆ DEFLATE_HEADER_BFINAL_BIT

#define DEFLATE_HEADER_BFINAL_BIT   0

Block header final block flags bit.

Definition at line 28 of file deflate.h.

◆ DEFLATE_HEADER_BTYPE_LSB

#define DEFLATE_HEADER_BTYPE_LSB   1

Block header type LSB.

Definition at line 31 of file deflate.h.

◆ DEFLATE_HEADER_BTYPE_MASK

#define DEFLATE_HEADER_BTYPE_MASK   0x03

Block header type mask.

Definition at line 34 of file deflate.h.

◆ DEFLATE_HEADER_BTYPE_LITERAL

#define DEFLATE_HEADER_BTYPE_LITERAL   0

Block header type: literal data.

Definition at line 37 of file deflate.h.

◆ DEFLATE_HEADER_BTYPE_STATIC

#define DEFLATE_HEADER_BTYPE_STATIC   1

Block header type: static Huffman alphabet.

Definition at line 40 of file deflate.h.

◆ DEFLATE_HEADER_BTYPE_DYNAMIC

#define DEFLATE_HEADER_BTYPE_DYNAMIC   2

Block header type: dynamic Huffman alphabet.

Definition at line 43 of file deflate.h.

◆ DEFLATE_LITERAL_LEN_BITS

#define DEFLATE_LITERAL_LEN_BITS   16

Literal header LEN/NLEN field length (in bits)

Definition at line 46 of file deflate.h.

◆ DEFLATE_DYNAMIC_BITS

#define DEFLATE_DYNAMIC_BITS   14

Dynamic header length (in bits)

Definition at line 49 of file deflate.h.

◆ DEFLATE_DYNAMIC_HLIT_LSB

#define DEFLATE_DYNAMIC_HLIT_LSB   0

Dynamic header HLIT field LSB.

Definition at line 52 of file deflate.h.

◆ DEFLATE_DYNAMIC_HLIT_MASK

#define DEFLATE_DYNAMIC_HLIT_MASK   0x1f

Dynamic header HLIT field mask.

Definition at line 55 of file deflate.h.

◆ DEFLATE_DYNAMIC_HDIST_LSB

#define DEFLATE_DYNAMIC_HDIST_LSB   5

Dynamic header HDIST field LSB.

Definition at line 58 of file deflate.h.

◆ DEFLATE_DYNAMIC_HDIST_MASK

#define DEFLATE_DYNAMIC_HDIST_MASK   0x1f

Dynamic header HDIST field mask.

Definition at line 61 of file deflate.h.

◆ DEFLATE_DYNAMIC_HCLEN_LSB

#define DEFLATE_DYNAMIC_HCLEN_LSB   10

Dynamic header HCLEN field LSB.

Definition at line 64 of file deflate.h.

◆ DEFLATE_DYNAMIC_HCLEN_MASK

#define DEFLATE_DYNAMIC_HCLEN_MASK   0x0f

Dynamic header HCLEN field mask.

Definition at line 67 of file deflate.h.

◆ DEFLATE_CODELEN_BITS

#define DEFLATE_CODELEN_BITS   3

Dynamic header code length length (in bits)

Definition at line 70 of file deflate.h.

◆ DEFLATE_HUFFMAN_BITS

#define DEFLATE_HUFFMAN_BITS   15

Maximum length of a Huffman symbol (in bits)

Definition at line 73 of file deflate.h.

◆ DEFLATE_HUFFMAN_QL_BITS

#define DEFLATE_HUFFMAN_QL_BITS   7

Quick lookup length for a Huffman symbol (in bits)

This is a policy decision.

Definition at line 79 of file deflate.h.

◆ DEFLATE_HUFFMAN_QL_SHIFT

#define DEFLATE_HUFFMAN_QL_SHIFT   ( 16 - DEFLATE_HUFFMAN_QL_BITS )

Quick lookup shift.

Definition at line 82 of file deflate.h.

◆ DEFLATE_LITLEN_END

#define DEFLATE_LITLEN_END   256

Literal/length end of block code.

Definition at line 85 of file deflate.h.

◆ DEFLATE_LITLEN_MAX_CODE

#define DEFLATE_LITLEN_MAX_CODE   287

Maximum value of a literal/length code.

Definition at line 88 of file deflate.h.

◆ DEFLATE_DISTANCE_MAX_CODE

#define DEFLATE_DISTANCE_MAX_CODE   31

Maximum value of a distance code.

Definition at line 91 of file deflate.h.

◆ DEFLATE_CODELEN_MAX_CODE

#define DEFLATE_CODELEN_MAX_CODE   18

Maximum value of a code length code.

Definition at line 94 of file deflate.h.

◆ ZLIB_HEADER_BITS

#define ZLIB_HEADER_BITS   16

ZLIB header length (in bits)

Definition at line 97 of file deflate.h.

◆ ZLIB_HEADER_CM_LSB

#define ZLIB_HEADER_CM_LSB   0

ZLIB header compression method LSB.

Definition at line 100 of file deflate.h.

◆ ZLIB_HEADER_CM_MASK

#define ZLIB_HEADER_CM_MASK   0x0f

ZLIB header compression method mask.

Definition at line 103 of file deflate.h.

◆ ZLIB_HEADER_CM_DEFLATE

#define ZLIB_HEADER_CM_DEFLATE   8

ZLIB header compression method: DEFLATE.

Definition at line 106 of file deflate.h.

◆ ZLIB_HEADER_FDICT_BIT

#define ZLIB_HEADER_FDICT_BIT   13

ZLIB header preset dictionary flag bit.

Definition at line 109 of file deflate.h.

◆ ZLIB_ADLER32_BITS

#define ZLIB_ADLER32_BITS   32

ZLIB ADLER32 length (in bits)

Definition at line 112 of file deflate.h.

Enumeration Type Documentation

◆ deflate_format

Compression formats.

Enumerator
DEFLATE_RAW 

Raw DEFLATE data (no header or footer)

DEFLATE_ZLIB 

ZLIB header and footer.

Definition at line 17 of file deflate.h.

17  {
18  /** Raw DEFLATE data (no header or footer) */
20  /** ZLIB header and footer */
22 };
ZLIB header and footer.
Definition: deflate.h:21
Raw DEFLATE data (no header or footer)
Definition: deflate.h:19

Function Documentation

◆ FILE_LICENCE()

FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL  )

◆ __attribute__() [1/2]

◆ __attribute__() [2/2]

static __attribute__ ( (always_inline)  )
inlinestatic

Initialise chunk of data.

Parameters
chunkChunk of data to initialise
dataData
offsetStarting offset
lenLength

◆ deflate_finished()

static int deflate_finished ( struct deflate deflate)
inlinestatic

Check if decompression has finished.

Parameters
deflateDecompressor
Return values
finishedDecompression has finished

Definition at line 273 of file deflate.h.

273  {
274  return ( deflate->resume == NULL );
275 }
void * resume
Resume point.
Definition: deflate.h:162
#define NULL
NULL pointer (VOID *)
Definition: Base.h:362
Decompressor.
Definition: deflate.h:156

References NULL, and deflate::resume.

Referenced by deflate_okx(), and png_image_end().

◆ 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:205
enum deflate_format format
Format.
Definition: deflate.h:164
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
uint16_t base
Base address.
Definition: edd.h:14
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(), and png_pixbuf().

◆ 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 =
865  deflate_litlen_base[extra];
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
#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
#define ENOTSUP
Operation not supported.
Definition: errno.h:589
static int isprint(int character)
Check if character is printable.
Definition: ctype.h:86
#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
__be32 out[4]
Definition: CIB_PRM.h:36
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
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
uint64_t index
Index of the first segment within the content.
Definition: pccrc.h:21
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:362
#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, deflate::extra_bits, deflate_static_length_pattern::fill, deflate::format, header, deflate::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(), and png_image_data().

Variable Documentation

◆ fill

static int fill

◆ count

uint8_t count

Repetition count.

Definition at line 14 of file deflate.h.

◆ __attribute__

◆ data

userptr_t data

Definition at line 259 of file deflate.h.

◆ offset

uint32_t offset = offset

Offset of the first segment within the content.

Interrupt wrapper address offset.

Definition at line 259 of file deflate.h.

Referenced by __vxge_hw_desc_offset_up(), __vxge_hw_vpath_pci_read(), acpi_currticks(), acpi_settings_fetch(), acpi_sx_zsdt(), aes_setkey(), alloc_iob_fail_okx(), alloc_iob_okx(), alloc_iob_raw(), alloc_memblock(), apply_dns_settings(), ar9003_hw_tx_iq_cal_post_proc(), ar9285_hw_pa_cal(), ar9300_read_otp(), ar9300_uncompress_block(), arbel_cmd_unmap_icm(), arbel_ring_doorbell(), asn1_okx(), ath5k_cal_data_offset_2413(), ath5k_eeprom_init_11a_pcal_freq(), ath5k_eeprom_init_11bg_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_eeprom_read(), ath5k_hw_rfb_op(), ath9k_olc_get_pdadcs(), atl1e_setup_ring_resources(), axge_in_complete(), axge_read_byte(), axge_read_dword(), axge_read_register(), axge_read_word(), axge_write_byte(), axge_write_dword(), axge_write_register(), axge_write_word(), base64_decode(), bios_currticks(), blktrans_xferbuf_read(), blktrans_xferbuf_write(), bnx2_ctx_wr(), bnx2_init_context(), bnx2_reg_rd_ind(), bnx2_reg_wr_ind(), bofm_locate_section(), bzimage_load_initrd(), bzimage_load_initrds(), call_bootsector(), cert_exec(), check_bios_interrupts(), clear_b0_fpga_memories(), cms_digest(), day_of_week(), dbg_hex_dump_da(), dbg_hex_dump_da_row(), deflate_alphabet(), deflate_copy(), deflate_okx(), dhcp_option(), dhcpopt_fetch(), dhcpopt_store(), dhcpopt_update_used_len(), digest_exec(), dm96xx_read_register(), dm96xx_read_registers(), dm96xx_write_register(), dm96xx_write_registers(), dns_decode(), dns_label(), dns_list_okx(), dns_question(), dns_skip(), dns_skip_search(), dns_xfer_deliver(), efi_disk_io_read_disk(), efi_disk_io_write_disk(), efi_pxe_buf_write(), efi_snp_nvdata(), efifb_glyph(), efifb_glyphs(), ehci_enqueue(), ehci_extended_capability(), ena_clear_caps(), ena_set_base(), ena_set_caps(), exanic_poll_rx(), exanic_transmit(), fbcon_clear(), fbcon_draw(), fbcon_draw_cursor(), fbcon_picture_init(), fbcon_redraw(), fbcon_store(), fcpcmd_recv_rddata(), fdt_alias(), fdt_child(), fdt_mac(), fdt_path(), fdt_property(), fdt_string(), find_dhcp_option_with_encap(), find_smbios_entry(), find_smbios_structure(), find_strings_terminator(), fragment_reassemble(), get_e(), goto_find_label(), hermon_cmd_unmap_icm(), hermon_mod_stat_cfg(), hfa384x_copy_from_bap(), hfa384x_copy_to_bap(), hfa384x_prepare_bap(), history_entry(), history_move(), hunt_mcdi_copyout(), i2c_bit_read(), i2c_bit_write(), i2c_select(), ibft_install(), ibft_string(), icplus_set_base(), if(), image_asn1(), image_x509(), inject_corruption_nonzero(), ioremap_pages(), is_pnp_bios(), iscsi_rx_data_in(), iscsi_start_data_out(), iscsi_tx_data_out(), linda_post_send(), linda_readq(), linda_verify_uc_ram(), linda_writel(), linda_writeq(), linux_lseek(), linux_mmap(), load_cpu_fw(), malloc_dma_offset(), md4_update(), md5_update(), mlx_pci_config(), mlx_pci_config_byte(), mlx_pci_config_dword(), mlx_pci_config_word(), mlx_pci_gw_check_capability_id(), mlx_pci_mem_read(), mlx_pci_mem_read_priv(), mlx_pci_mem_write(), mlx_pci_mem_write_priv(), mlx_pci_read(), mlx_pci_read_priv(), mlx_pci_write(), mlx_pci_write_priv(), multiboot_find_header(), multiboot_load_raw(), natsemi_create_ring(), natsemi_hwaddr_insane(), nbi_load_segment(), nbi_process_segments(), ndp_fetch(), ndp_register_settings(), ndp_rx_options(), netvsc_buffer_copy(), nfs_read(), nodnic_port_thin_init(), ntlm_challenge(), ntlm_data_okx(), pci_backup(), pci_backup_excluded(), pci_msix_ioremap(), pci_restore(), pciea_bar_value(), pciea_offset(), peerdist_info_get(), peerdist_info_v1_block_offset(), peerdist_info_v1_blocks(), pem_asn1(), pem_image_asn1(), pem_image_probe(), pem_marker(), pem_next(), 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_read_test_mem_block(), phantom_readl(), phantom_writel(), phy_read(), phy_write(), png_palette(), png_unfilter_pass(), pnm_data(), prep_pci_cfg_cap(), print_user_string(), pxenv_file_api_check(), qib7322_post_send(), qib7322_readq(), qib7322_writel(), qib7322_writeq(), read_smbios_string(), read_srom_word(), read_user(), real_to_user(), reg_delay(), resize_dhcp_option(), rsdp_find_rsdt_range(), script_exec_line(), set_dhcp_option(), sha1_update(), sha256_update(), sha512_update(), smscusb_fdt_fetch_mac(), t509_id_read_eeprom(), t509_load_eeprom_word(), tcpip_bind(), tftp_rx_data(), tg3_nvram_read(), tg3_nvram_read_be32(), tg3_nvram_read_using_eeprom(), trivial_memchr_user(), trivial_memset_user(), trivial_strlen_user(), trivial_user_to_virt(), trivial_userptr_add(), txnic_poll_cq(), txnic_refill_rq(), txnic_send(), vesafb_glyph(), virtio_pci_map_capability(), vmbus_xfer_page_iobufs(), vp_get(), vpm_get(), vpm_ioread16(), vpm_ioread32(), vpm_ioread8(), vpm_iowrite16(), vpm_iowrite32(), vpm_iowrite8(), vxge_hw_fifo_txd_offset_up(), vxge_hw_ring_replenish(), vxge_hw_ring_rxd_offset_up(), vxge_hw_set_fw_api(), xenstore_recv(), xenstore_send(), xfer_seek(), xferbuf_malloc_read(), xferbuf_malloc_write(), xferbuf_read(), xferbuf_umalloc_read(), xferbuf_umalloc_write(), xferbuf_write(), xhci_extended_capability(), and xhci_supported_protocol().

◆ len

chunk len
Initial value:
{
chunk->data = data
static userptr_t data
Definition: deflate.h:259

Definition at line 260 of file deflate.h.