iPXE
deflate.h
Go to the documentation of this file.
00001 #ifndef _IPXE_DEFLATE_H
00002 #define _IPXE_DEFLATE_H
00003 
00004 /** @file
00005  *
00006  * DEFLATE decompression algorithm
00007  *
00008  */
00009 
00010 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
00011 
00012 #include <stdint.h>
00013 #include <string.h>
00014 #include <ipxe/uaccess.h>
00015 
00016 /** Compression formats */
00017 enum deflate_format {
00018         /** Raw DEFLATE data (no header or footer) */
00019         DEFLATE_RAW,
00020         /** ZLIB header and footer */
00021         DEFLATE_ZLIB,
00022 };
00023 
00024 /** Block header length (in bits) */
00025 #define DEFLATE_HEADER_BITS 3
00026 
00027 /** Block header final block flags bit */
00028 #define DEFLATE_HEADER_BFINAL_BIT 0
00029 
00030 /** Block header type LSB */
00031 #define DEFLATE_HEADER_BTYPE_LSB 1
00032 
00033 /** Block header type mask */
00034 #define DEFLATE_HEADER_BTYPE_MASK 0x03
00035 
00036 /** Block header type: literal data */
00037 #define DEFLATE_HEADER_BTYPE_LITERAL 0
00038 
00039 /** Block header type: static Huffman alphabet */
00040 #define DEFLATE_HEADER_BTYPE_STATIC 1
00041 
00042 /** Block header type: dynamic Huffman alphabet */
00043 #define DEFLATE_HEADER_BTYPE_DYNAMIC 2
00044 
00045 /** Literal header LEN/NLEN field length (in bits) */
00046 #define DEFLATE_LITERAL_LEN_BITS 16
00047 
00048 /** Dynamic header length (in bits) */
00049 #define DEFLATE_DYNAMIC_BITS 14
00050 
00051 /** Dynamic header HLIT field LSB */
00052 #define DEFLATE_DYNAMIC_HLIT_LSB 0
00053 
00054 /** Dynamic header HLIT field mask */
00055 #define DEFLATE_DYNAMIC_HLIT_MASK 0x1f
00056 
00057 /** Dynamic header HDIST field LSB */
00058 #define DEFLATE_DYNAMIC_HDIST_LSB 5
00059 
00060 /** Dynamic header HDIST field mask */
00061 #define DEFLATE_DYNAMIC_HDIST_MASK 0x1f
00062 
00063 /** Dynamic header HCLEN field LSB */
00064 #define DEFLATE_DYNAMIC_HCLEN_LSB 10
00065 
00066 /** Dynamic header HCLEN field mask */
00067 #define DEFLATE_DYNAMIC_HCLEN_MASK 0x0f
00068 
00069 /** Dynamic header code length length (in bits) */
00070 #define DEFLATE_CODELEN_BITS 3
00071 
00072 /** Maximum length of a Huffman symbol (in bits) */
00073 #define DEFLATE_HUFFMAN_BITS 15
00074 
00075 /** Quick lookup length for a Huffman symbol (in bits)
00076  *
00077  * This is a policy decision.
00078  */
00079 #define DEFLATE_HUFFMAN_QL_BITS 7
00080 
00081 /** Quick lookup shift */
00082 #define DEFLATE_HUFFMAN_QL_SHIFT ( 16 - DEFLATE_HUFFMAN_QL_BITS )
00083 
00084 /** Literal/length end of block code */
00085 #define DEFLATE_LITLEN_END 256
00086 
00087 /** Maximum value of a literal/length code */
00088 #define DEFLATE_LITLEN_MAX_CODE 287
00089 
00090 /** Maximum value of a distance code */
00091 #define DEFLATE_DISTANCE_MAX_CODE 31
00092 
00093 /** Maximum value of a code length code */
00094 #define DEFLATE_CODELEN_MAX_CODE 18
00095 
00096 /** ZLIB header length (in bits) */
00097 #define ZLIB_HEADER_BITS 16
00098 
00099 /** ZLIB header compression method LSB */
00100 #define ZLIB_HEADER_CM_LSB 0
00101 
00102 /** ZLIB header compression method mask */
00103 #define ZLIB_HEADER_CM_MASK 0x0f
00104 
00105 /** ZLIB header compression method: DEFLATE */
00106 #define ZLIB_HEADER_CM_DEFLATE 8
00107 
00108 /** ZLIB header preset dictionary flag bit */
00109 #define ZLIB_HEADER_FDICT_BIT 13
00110 
00111 /** ZLIB ADLER32 length (in bits) */
00112 #define ZLIB_ADLER32_BITS 32
00113 
00114 /** A Huffman-coded set of symbols of a given length */
00115 struct deflate_huf_symbols {
00116         /** Length of Huffman-coded symbols */
00117         uint8_t bits;
00118         /** Shift to normalise symbols of this length to 16 bits */
00119         uint8_t shift;
00120         /** Number of Huffman-coded symbols having this length */
00121         uint16_t freq;
00122         /** First symbol of this length (normalised to 16 bits)
00123          *
00124          * Stored as a 32-bit value to allow the value 0x10000 to be
00125          * used for empty sets of symbols longer than the maximum
00126          * utilised length.
00127          */
00128         uint32_t start;
00129         /** Raw symbols having this length */
00130         uint16_t *raw;
00131 };
00132 
00133 /** A Huffman-coded alphabet */
00134 struct deflate_alphabet {
00135         /** Huffman-coded symbol set for each length */
00136         struct deflate_huf_symbols huf[DEFLATE_HUFFMAN_BITS];
00137         /** Quick lookup table */
00138         uint8_t lookup[ 1 << DEFLATE_HUFFMAN_QL_BITS ];
00139         /** Raw symbols
00140          *
00141          * Ordered by Huffman-coded symbol length, then by symbol
00142          * value.  This field has a variable length.
00143          */
00144         uint16_t raw[0];
00145 };
00146 
00147 /** A static Huffman alphabet length pattern */
00148 struct deflate_static_length_pattern {
00149         /** Length pair */
00150         uint8_t fill;
00151         /** Repetition count */
00152         uint8_t count;
00153 } __attribute__ (( packed ));
00154 
00155 /** Decompressor */
00156 struct deflate {
00157         /** Resume point
00158          *
00159          * Used as the target of a computed goto to jump to the
00160          * appropriate point within the state machine.
00161          */
00162         void *resume;
00163         /** Format */
00164         enum deflate_format format;
00165 
00166         /** Accumulator */
00167         uint32_t accumulator;
00168         /** Bit-reversed accumulator
00169          *
00170          * Don't ask.
00171          */
00172         uint32_t rotalumucca;
00173         /** Number of bits within the accumulator */
00174         unsigned int bits;
00175 
00176         /** Current block header */
00177         unsigned int header;
00178         /** Remaining length of data (e.g. within a literal block) */
00179         size_t remaining;
00180         /** Current length index within a set of code lengths */
00181         unsigned int length_index;
00182         /** Target length index within a set of code lengths */
00183         unsigned int length_target;
00184         /** Current length within a set of code lengths */
00185         unsigned int length;
00186         /** Number of extra bits required */
00187         unsigned int extra_bits;
00188         /** Length of a duplicated string */
00189         size_t dup_len;
00190         /** Distance of a duplicated string */
00191         size_t dup_distance;
00192 
00193         /** Literal/length Huffman alphabet */
00194         struct deflate_alphabet litlen;
00195         /** Literal/length raw symbols
00196          *
00197          * Must immediately follow the literal/length Huffman alphabet.
00198          */
00199         uint16_t litlen_raw[ DEFLATE_LITLEN_MAX_CODE + 1 ];
00200         /** Number of symbols in the literal/length Huffman alphabet */
00201         unsigned int litlen_count;
00202 
00203         /** Distance and code length Huffman alphabet
00204          *
00205          * The code length Huffman alphabet has a maximum Huffman
00206          * symbol length of 7 and a maximum code value of 18, and is
00207          * thus strictly smaller than the distance Huffman alphabet.
00208          * Since we never need both alphabets simultaneously, we can
00209          * reuse the storage space for the distance alphabet to
00210          * temporarily hold the code length alphabet.
00211          */
00212         struct deflate_alphabet distance_codelen;
00213         /** Distance and code length raw symbols
00214          *
00215          * Must immediately follow the distance and code length
00216          * Huffman alphabet.
00217          */
00218         uint16_t distance_codelen_raw[ DEFLATE_DISTANCE_MAX_CODE + 1 ];
00219         /** Number of symbols in the distance Huffman alphabet */
00220         unsigned int distance_count;
00221 
00222         /** Huffman code lengths
00223          *
00224          * The literal/length and distance code lengths are
00225          * constructed as a single set of lengths.
00226          *
00227          * The code length Huffman alphabet has a maximum code value
00228          * of 18 and the set of lengths is thus strictly smaller than
00229          * the combined literal/length and distance set of lengths.
00230          * Since we never need both alphabets simultaneously, we can
00231          * reuse the storage space for the literal/length and distance
00232          * code lengths to temporarily hold the code length code
00233          * lengths.
00234          */
00235         uint8_t lengths[ ( ( DEFLATE_LITLEN_MAX_CODE + 1 ) +
00236                            ( DEFLATE_DISTANCE_MAX_CODE + 1 ) +
00237                            1 /* round up */ ) / 2 ];
00238 };
00239 
00240 /** A chunk of data */
00241 struct deflate_chunk {
00242         /** Data */
00243         userptr_t data;
00244         /** Current offset */
00245         size_t offset;
00246         /** Length of data */
00247         size_t len;
00248 };
00249 
00250 /**
00251  * Initialise chunk of data
00252  *
00253  * @v chunk             Chunk of data to initialise
00254  * @v data              Data
00255  * @v offset            Starting offset
00256  * @v len               Length
00257  */
00258 static inline __attribute__ (( always_inline )) void
00259 deflate_chunk_init ( struct deflate_chunk *chunk, userptr_t data,
00260                      size_t offset, size_t len ) {
00261 
00262         chunk->data = data;
00263         chunk->offset = offset;
00264         chunk->len = len;
00265 }
00266 
00267 /**
00268  * Check if decompression has finished
00269  *
00270  * @v deflate           Decompressor
00271  * @ret finished        Decompression has finished
00272  */
00273 static inline int deflate_finished ( struct deflate *deflate ) {
00274         return ( deflate->resume == NULL );
00275 }
00276 
00277 extern void deflate_init ( struct deflate *deflate,
00278                            enum deflate_format format );
00279 extern int deflate_inflate ( struct deflate *deflate,
00280                              struct deflate_chunk *in,
00281                              struct deflate_chunk *out );
00282 
00283 #endif /* _IPXE_DEFLATE_H */