qemu/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 );
  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 */