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 */
17 enum deflate_format {
18 /** Raw DEFLATE data (no header or footer) */
19 DEFLATE_RAW,
20 /** ZLIB header and footer */
21 DEFLATE_ZLIB,
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 */
115 struct deflate_huf_symbols {
116 /** Length of Huffman-coded symbols */
117 uint8_t bits;
118 /** Shift to normalise symbols of this length to 16 bits */
119 uint8_t shift;
120 /** Number of Huffman-coded symbols having this length */
121 uint16_t freq;
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 */
128 uint32_t start;
129 /** Raw symbols having this length */
130 uint16_t *raw;
131 };
132
133 /** A Huffman-coded alphabet */
134 struct deflate_alphabet {
135 /** Huffman-coded symbol set for each length */
136 struct deflate_huf_symbols huf[DEFLATE_HUFFMAN_BITS];
137 /** Quick lookup table */
138 uint8_t lookup[ 1 << DEFLATE_HUFFMAN_QL_BITS ];
139 /** Raw symbols
140 *
141 * Ordered by Huffman-coded symbol length, then by symbol
142 * value. This field has a variable length.
143 */
144 uint16_t raw[0];
145 };
146
147 /** A static Huffman alphabet length pattern */
148 struct deflate_static_length_pattern {
149 /** Length pair */
150 uint8_t fill;
151 /** Repetition count */
152 uint8_t 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 */
164 enum deflate_format format;
165
166 /** Accumulator */
167 uint32_t accumulator;
168 /** Bit-reversed accumulator
169 *
170 * Don't ask.
171 */
172 uint32_t rotalumucca;
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 */
194 struct deflate_alphabet litlen;
195 /** Literal/length raw symbols
196 *
197 * Must immediately follow the literal/length Huffman alphabet.
198 */
199 uint16_t litlen_raw[ DEFLATE_LITLEN_MAX_CODE + 1 ];
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 */
212 struct deflate_alphabet distance_codelen;
213 /** Distance and code length raw symbols
214 *
215 * Must immediately follow the distance and code length
216 * Huffman alphabet.
217 */
218 uint16_t distance_codelen_raw[ DEFLATE_DISTANCE_MAX_CODE + 1 ];
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 */
235 uint8_t lengths[ ( ( DEFLATE_LITLEN_MAX_CODE + 1 ) +
236 ( DEFLATE_DISTANCE_MAX_CODE + 1 ) +
237 1 /* round up */ ) / 2 ];
238 };
239
240 /** A chunk of data */
241 struct deflate_chunk {
242 /** Data */
243 userptr_t 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
deflate_chunk_init(struct deflate_chunk * chunk,userptr_t data,size_t offset,size_t len)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 */
deflate_finished(struct deflate * deflate)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 */
284