wimlib.net Git - wimlib/blob - include/wimlib/lzx.h

   1 #ifndef _WIMLIB_LZX_H
   2 #define _WIMLIB_LZX_H
   3
   4 /* Constants for the LZX data compression format.  See the comments in
   5  * lzx-compress.c and lzx-decompress.c for more information about this format.
   6  * */
   7
   8 #include "wimlib/assert.h"
   9 #include "wimlib/types.h"
  10
  11 //#define ENABLE_LZX_DEBUG
  12 #ifdef ENABLE_LZX_DEBUG
  13 #       define LZX_DEBUG DEBUG
  14 #       define LZX_ASSERT wimlib_assert
  15 #else
  16 #       define LZX_DEBUG(format, ...)
  17 #       define LZX_ASSERT(...)
  18 #endif
  19
  20 /* Constants, most of which are defined by the LZX specification: */
  21
  22 /* The smallest and largest allowed match lengths. */
  23 #define LZX_MIN_MATCH_LEN            2
  24 #define LZX_MAX_MATCH_LEN            257
  25
  26 /* Number of values an uncompressed literal byte can represent. */
  27 #define LZX_NUM_CHARS                256
  28
  29 /* Each LZX block begins with 3 bits that determines the block type.  Below are
  30  * the valid block types.  Values 0, and 4 through 7, are invalid. */
  31 #define LZX_BLOCKTYPE_VERBATIM       1
  32 #define LZX_BLOCKTYPE_ALIGNED        2
  33 #define LZX_BLOCKTYPE_UNCOMPRESSED   3
  34
  35 #define LZX_NUM_PRIMARY_LENS         7  /* this one missing from spec! */
  36
  37 /* NOTE: There are really 51 position slots in the LZX format as a whole, but
  38  * only 30 are needed to allow for the window to be up to 32768 bytes long,
  39  * which is the maximum in the WIM format. */
  40 #define LZX_NUM_POSITION_SLOTS       30
  41
  42 /* Read the LZX specification for information about the Huffman trees used in
  43  * the LZX compression format.  Basically there are 4 of them: The main tree,
  44  * the length tree, the pre tree, and the aligned tree.  The main tree and
  45  * length tree are given at the beginning of VERBATIM and ALIGNED blocks as a
  46  * list of *_NUM_SYMBOLS code length values.  They are read using the
  47  * read_code_lens() function and built using the make_decode_table() function.
  48  * The decode table is not a real tree but rather a table that we can index by
  49  * some number of bits (*_TABLEBITS) of the input to quickly look up the symbol
  50  * corresponding to a Huffman code.
  51  *
  52  * The ALIGNED tree is only present on ALIGNED blocks.
  53  *
  54  * A PRECODE is used to encode the code lengths for the main tree and the length
  55  * tree.  There is a separate pretree for each half of the main tree.  */
  56
  57 #define LZX_MAINCODE_NUM_SYMBOLS         (LZX_NUM_CHARS + \
  58                                         (LZX_NUM_POSITION_SLOTS << 3))
  59 #define LZX_MAINCODE_TABLEBITS          11
  60
  61 #define LZX_LENCODE_NUM_SYMBOLS         249
  62 #define LZX_LENCODE_TABLEBITS           10
  63
  64 #define LZX_PRECODE_NUM_SYMBOLS         20
  65 #define LZX_PRECODE_TABLEBITS           6
  66 #define LZX_PRECODE_ELEMENT_SIZE        4
  67
  68 #define LZX_ALIGNEDCODE_NUM_SYMBOLS     8
  69 #define LZX_ALIGNEDCODE_TABLEBITS       7
  70 #define LZX_ALIGNEDCODE_ELEMENT_SIZE    3
  71
  72 /* Maximum allowed length of Huffman codewords.  */
  73 #define LZX_MAX_MAIN_CODEWORD_LEN       16
  74 #define LZX_MAX_LEN_CODEWORD_LEN        16
  75 #define LZX_MAX_PRE_CODEWORD_LEN        16
  76 #define LZX_MAX_ALIGNED_CODEWORD_LEN    8
  77
  78 /* For the LZX-compressed blocks in WIM files, this value is always used as the
  79  * filesize parameter for the call instruction (0xe8 byte) preprocessing, even
  80  * though the blocks themselves are not this size, and the size of the actual
  81  * file resource in the WIM file is very likely to be something entirely
  82  * different as well.  */
  83 #define LZX_WIM_MAGIC_FILESIZE          12000000
  84
  85 #define LZX_BLOCKTYPE_NBITS     3
  86 #define LZX_BLOCKSIZE_NBITS     16
  87
  88 #define USE_LZX_EXTRA_BITS_ARRAY
  89
  90 #ifdef USE_LZX_EXTRA_BITS_ARRAY
  91 extern const u8 lzx_extra_bits[];
  92 #endif
  93
  94 /* Given the number of a LZX position slot, return the number of extra bits that
  95  * are needed to encode the match offset. */
  96 static inline unsigned
  97 lzx_get_num_extra_bits(unsigned position_slot)
  98 {
  99 #ifdef USE_LZX_EXTRA_BITS_ARRAY
 100         /* Use a table */
 101         return lzx_extra_bits[position_slot];
 102 #else
 103         /* Calculate directly using a shift and subtraction. */
 104         LZX_ASSERT(position_slot >= 2 && position_slot <= 37);
 105         return (position_slot >> 1) - 1;
 106 #endif
 107 }
 108
 109 extern const u32 lzx_position_base[];
 110
 111 #define LZX_NUM_RECENT_OFFSETS  3
 112
 113 /* Least-recently used queue for match offsets.  */
 114 struct lzx_lru_queue {
 115         u32 R[LZX_NUM_RECENT_OFFSETS];
 116 };
 117
 118 /* In the LZX format, an offset of n bytes is actually encoded
 119  * as (n + LZX_OFFSET_OFFSET).  */
 120 #define LZX_OFFSET_OFFSET       (LZX_NUM_RECENT_OFFSETS - 1)
 121
 122 static inline void
 123 lzx_lru_queue_init(struct lzx_lru_queue *queue)
 124 {
 125         for (unsigned i = 0; i < LZX_NUM_RECENT_OFFSETS; i++)
 126                 queue->R[i] = 1;
 127 }
 128
 129 #endif /* _WIMLIB_LZX_H */