← Back to branch summary

~pmdj/ubuntu/trusty/qemu/2.9+applesmc+fadtv3

« back to all changes in this revision

Viewing changes to roms/ipxe/src/include/ipxe/deflate.h

  • Committer: Phil Dennis-Jordan
  • Date: 2017-07-21 08:03:43 UTC
  • mfrom: (1.1.1)
  • Revision ID: phil@philjordan.eu-20170721080343-2yr2vdj7713czahv
New upstream release 2.9.0.

Show diffs side-by-side

added added

removed removed

Lines of Context:
roms/ipxe/src/include/ipxe/deflate.h
 
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
 
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 */