iPXE
deflate.h
Go to the documentation of this file.
1 #ifndef _IPXE_DEFLATE_H
2 #define _IPXE_DEFLATE_H
3 
4 /** @file
5  *
6  * DEFLATE decompression algorithm
7  *
8  */
9 
10 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
11 
12 #include <stdint.h>
13 #include <string.h>
14 #include <ipxe/uaccess.h>
15 
16 /** Compression formats */
18  /** Raw DEFLATE data (no header or footer) */
20  /** ZLIB header and footer */
22 };
23 
24 /** Block header length (in bits) */
25 #define DEFLATE_HEADER_BITS 3
26 
27 /** Block header final block flags bit */
28 #define DEFLATE_HEADER_BFINAL_BIT 0
29 
30 /** Block header type LSB */
31 #define DEFLATE_HEADER_BTYPE_LSB 1
32 
33 /** Block header type mask */
34 #define DEFLATE_HEADER_BTYPE_MASK 0x03
35 
36 /** Block header type: literal data */
37 #define DEFLATE_HEADER_BTYPE_LITERAL 0
38 
39 /** Block header type: static Huffman alphabet */
40 #define DEFLATE_HEADER_BTYPE_STATIC 1
41 
42 /** Block header type: dynamic Huffman alphabet */
43 #define DEFLATE_HEADER_BTYPE_DYNAMIC 2
44 
45 /** Literal header LEN/NLEN field length (in bits) */
46 #define DEFLATE_LITERAL_LEN_BITS 16
47 
48 /** Dynamic header length (in bits) */
49 #define DEFLATE_DYNAMIC_BITS 14
50 
51 /** Dynamic header HLIT field LSB */
52 #define DEFLATE_DYNAMIC_HLIT_LSB 0
53 
54 /** Dynamic header HLIT field mask */
55 #define DEFLATE_DYNAMIC_HLIT_MASK 0x1f
56 
57 /** Dynamic header HDIST field LSB */
58 #define DEFLATE_DYNAMIC_HDIST_LSB 5
59 
60 /** Dynamic header HDIST field mask */
61 #define DEFLATE_DYNAMIC_HDIST_MASK 0x1f
62 
63 /** Dynamic header HCLEN field LSB */
64 #define DEFLATE_DYNAMIC_HCLEN_LSB 10
65 
66 /** Dynamic header HCLEN field mask */
67 #define DEFLATE_DYNAMIC_HCLEN_MASK 0x0f
68 
69 /** Dynamic header code length length (in bits) */
70 #define DEFLATE_CODELEN_BITS 3
71 
72 /** Maximum length of a Huffman symbol (in bits) */
73 #define DEFLATE_HUFFMAN_BITS 15
74 
75 /** Quick lookup length for a Huffman symbol (in bits)
76  *
77  * This is a policy decision.
78  */
79 #define DEFLATE_HUFFMAN_QL_BITS 7
80 
81 /** Quick lookup shift */
82 #define DEFLATE_HUFFMAN_QL_SHIFT ( 16 - DEFLATE_HUFFMAN_QL_BITS )
83 
84 /** Literal/length end of block code */
85 #define DEFLATE_LITLEN_END 256
86 
87 /** Maximum value of a literal/length code */
88 #define DEFLATE_LITLEN_MAX_CODE 287
89 
90 /** Maximum value of a distance code */
91 #define DEFLATE_DISTANCE_MAX_CODE 31
92 
93 /** Maximum value of a code length code */
94 #define DEFLATE_CODELEN_MAX_CODE 18
95 
96 /** ZLIB header length (in bits) */
97 #define ZLIB_HEADER_BITS 16
98 
99 /** ZLIB header compression method LSB */
100 #define ZLIB_HEADER_CM_LSB 0
101 
102 /** ZLIB header compression method mask */
103 #define ZLIB_HEADER_CM_MASK 0x0f
104 
105 /** ZLIB header compression method: DEFLATE */
106 #define ZLIB_HEADER_CM_DEFLATE 8
107 
108 /** ZLIB header preset dictionary flag bit */
109 #define ZLIB_HEADER_FDICT_BIT 13
110 
111 /** ZLIB ADLER32 length (in bits) */
112 #define ZLIB_ADLER32_BITS 32
113 
114 /** A Huffman-coded set of symbols of a given length */
116  /** Length of Huffman-coded symbols */
118  /** Shift to normalise symbols of this length to 16 bits */
120  /** Number of Huffman-coded symbols having this length */
122  /** First symbol of this length (normalised to 16 bits)
123  *
124  * Stored as a 32-bit value to allow the value 0x10000 to be
125  * used for empty sets of symbols longer than the maximum
126  * utilised length.
127  */
129  /** Raw symbols having this length */
131 };
132 
133 /** A Huffman-coded alphabet */
135  /** Huffman-coded symbol set for each length */
137  /** Quick lookup table */
139  /** Raw symbols
140  *
141  * Ordered by Huffman-coded symbol length, then by symbol
142  * value. This field has a variable length.
143  */
145 };
146 
147 /** A static Huffman alphabet length pattern */
149  /** Length pair */
151  /** Repetition count */
153 } __attribute__ (( packed ));
154 
155 /** Decompressor */
156 struct deflate {
157  /** Resume point
158  *
159  * Used as the target of a computed goto to jump to the
160  * appropriate point within the state machine.
161  */
162  void *resume;
163  /** Format */
165 
166  /** Accumulator */
168  /** Bit-reversed accumulator
169  *
170  * Don't ask.
171  */
173  /** Number of bits within the accumulator */
174  unsigned int bits;
175 
176  /** Current block header */
177  unsigned int header;
178  /** Remaining length of data (e.g. within a literal block) */
179  size_t remaining;
180  /** Current length index within a set of code lengths */
181  unsigned int length_index;
182  /** Target length index within a set of code lengths */
183  unsigned int length_target;
184  /** Current length within a set of code lengths */
185  unsigned int length;
186  /** Number of extra bits required */
187  unsigned int extra_bits;
188  /** Length of a duplicated string */
189  size_t dup_len;
190  /** Distance of a duplicated string */
191  size_t dup_distance;
192 
193  /** Literal/length Huffman alphabet */
195  /** Literal/length raw symbols
196  *
197  * Must immediately follow the literal/length Huffman alphabet.
198  */
200  /** Number of symbols in the literal/length Huffman alphabet */
201  unsigned int litlen_count;
202 
203  /** Distance and code length Huffman alphabet
204  *
205  * The code length Huffman alphabet has a maximum Huffman
206  * symbol length of 7 and a maximum code value of 18, and is
207  * thus strictly smaller than the distance Huffman alphabet.
208  * Since we never need both alphabets simultaneously, we can
209  * reuse the storage space for the distance alphabet to
210  * temporarily hold the code length alphabet.
211  */
213  /** Distance and code length raw symbols
214  *
215  * Must immediately follow the distance and code length
216  * Huffman alphabet.
217  */
219  /** Number of symbols in the distance Huffman alphabet */
220  unsigned int distance_count;
221 
222  /** Huffman code lengths
223  *
224  * The literal/length and distance code lengths are
225  * constructed as a single set of lengths.
226  *
227  * The code length Huffman alphabet has a maximum code value
228  * of 18 and the set of lengths is thus strictly smaller than
229  * the combined literal/length and distance set of lengths.
230  * Since we never need both alphabets simultaneously, we can
231  * reuse the storage space for the literal/length and distance
232  * code lengths to temporarily hold the code length code
233  * lengths.
234  */
236  ( DEFLATE_DISTANCE_MAX_CODE + 1 ) +
237  1 /* round up */ ) / 2 ];
238 };
239 
240 /** A chunk of data */
242  /** Data */
244  /** Current offset */
245  size_t offset;
246  /** Length of data */
247  size_t len;
248 };
249 
250 /**
251  * Initialise chunk of data
252  *
253  * @v chunk Chunk of data to initialise
254  * @v data Data
255  * @v offset Starting offset
256  * @v len Length
257  */
258 static inline __attribute__ (( always_inline )) void
259 deflate_chunk_init ( struct deflate_chunk *chunk, userptr_t data,
260  size_t offset, size_t len ) {
261 
262  chunk->data = data;
263  chunk->offset = offset;
264  chunk->len = len;
265 }
266 
267 /**
268  * Check if decompression has finished
269  *
270  * @v deflate Decompressor
271  * @ret finished Decompression has finished
272  */
273 static inline int deflate_finished ( struct deflate *deflate ) {
274  return ( deflate->resume == NULL );
275 }
276 
277 extern void deflate_init ( struct deflate *deflate,
278  enum deflate_format format );
279 extern int deflate_inflate ( struct deflate *deflate,
280  struct deflate_chunk *in,
281  struct deflate_chunk *out );
282 
283 #endif /* _IPXE_DEFLATE_H */
unsigned short uint16_t
Definition: stdint.h:11
unsigned int length_index
Current length index within a set of code lengths.
Definition: deflate.h:181
__be32 in[4]
Definition: CIB_PRM.h:35
struct deflate_alphabet distance_codelen
Distance and code length Huffman alphabet.
Definition: deflate.h:212
#define DEFLATE_LITLEN_MAX_CODE
Maximum value of a literal/length code.
Definition: deflate.h:88
unsigned int length_target
Target length index within a set of code lengths.
Definition: deflate.h:183
unsigned int extra_bits
Number of extra bits required.
Definition: deflate.h:187
#define DEFLATE_HUFFMAN_BITS
Maximum length of a Huffman symbol (in bits)
Definition: deflate.h:73
size_t dup_distance
Distance of a duplicated string.
Definition: deflate.h:191
unsigned int header
Current block header.
Definition: deflate.h:177
uint16_t raw[0]
Raw symbols.
Definition: deflate.h:144
enum deflate_format format
Format.
Definition: deflate.h:164
unsigned int length
Current length within a set of code lengths.
Definition: deflate.h:185
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
A Huffman-coded alphabet.
Definition: deflate.h:134
static userptr_t size_t size_t len
Definition: deflate.h:260
uint8_t count
Repetition count.
Definition: deflate.h:152
Access to external ("user") memory.
unsigned int bits
Number of bits within the accumulator.
Definition: deflate.h:174
__be32 out[4]
Definition: CIB_PRM.h:36
uint16_t distance_codelen_raw[DEFLATE_DISTANCE_MAX_CODE+1]
Distance and code length raw symbols.
Definition: deflate.h:218
A chunk of data.
Definition: deflate.h:241
uint32_t accumulator
Accumulator.
Definition: deflate.h:167
size_t dup_len
Length of a duplicated string.
Definition: deflate.h:189
void * resume
Resume point.
Definition: deflate.h:162
static int deflate_finished(struct deflate *deflate)
Check if decompression has finished.
Definition: deflate.h:273
#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
static userptr_t data
Definition: deflate.h:259
uint16_t freq
Number of Huffman-coded symbols having this length.
Definition: deflate.h:121
ZLIB header and footer.
Definition: deflate.h:21
uint8_t fill
Length pair.
Definition: deflate.h:150
deflate_format
Compression formats.
Definition: deflate.h:17
struct deflate __attribute__
uint32_t rotalumucca
Bit-reversed accumulator.
Definition: deflate.h:172
unsigned char uint8_t
Definition: stdint.h:10
unsigned int distance_count
Number of symbols in the distance Huffman alphabet.
Definition: deflate.h:220
size_t offset
Current offset.
Definition: deflate.h:245
FILE_LICENCE(GPL2_OR_LATER_OR_UBDL)
unsigned int uint32_t
Definition: stdint.h:12
struct deflate_alphabet litlen
Literal/length Huffman alphabet.
Definition: deflate.h:194
uint16_t * raw
Raw symbols having this length.
Definition: deflate.h:130
#define DEFLATE_DISTANCE_MAX_CODE
Maximum value of a distance code.
Definition: deflate.h:91
Raw DEFLATE data (no header or footer)
Definition: deflate.h:19
A static Huffman alphabet length pattern.
Definition: deflate.h:148
unsigned int litlen_count
Number of symbols in the literal/length Huffman alphabet.
Definition: deflate.h:201
int deflate_inflate(struct deflate *deflate, struct deflate_chunk *in, struct deflate_chunk *out)
Inflate compressed data.
Definition: deflate.c:492
userptr_t data
Data.
Definition: deflate.h:243
uint8_t lengths[((DEFLATE_LITLEN_MAX_CODE+1)+(DEFLATE_DISTANCE_MAX_CODE+1)+1)/2]
Huffman code lengths.
Definition: deflate.h:237
uint8_t shift
Shift to normalise symbols of this length to 16 bits.
Definition: deflate.h:119
uint16_t litlen_raw[DEFLATE_LITLEN_MAX_CODE+1]
Literal/length raw symbols.
Definition: deflate.h:199
int const char * format
Definition: xfer.h:104
#define NULL
NULL pointer (VOID *)
Definition: Base.h:321
size_t len
Length of data.
Definition: deflate.h:247
uint8_t bits
Length of Huffman-coded symbols.
Definition: deflate.h:117
String functions.
size_t remaining
Remaining length of data (e.g.
Definition: deflate.h:179
unsigned long userptr_t
A pointer to a user buffer.
Definition: uaccess.h:33
void deflate_init(struct deflate *deflate, enum deflate_format format)
Initialise decompressor.
Definition: deflate.c:999
Decompressor.
Definition: deflate.h:156