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/compiler.h"
  10 #include "wimlib/util.h"
  11 #include "wimlib/types.h"
  12
  13 //#define ENABLE_LZX_DEBUG
  14 #ifdef ENABLE_LZX_DEBUG
  15 #       define LZX_DEBUG DEBUG
  16 #       define LZX_ASSERT wimlib_assert
  17 #else
  18 #       define LZX_DEBUG(format, ...)
  19 #       define LZX_ASSERT(...)
  20 #endif
  21
  22 /* Constants, most of which are defined by the LZX specification: */
  23
  24 /* The smallest and largest allowed match lengths. */
  25 #define LZX_MIN_MATCH_LEN            2
  26 #define LZX_MAX_MATCH_LEN            257
  27
  28 /* Number of values an uncompressed literal byte can represent. */
  29 #define LZX_NUM_CHARS                256
  30
  31 /* Each LZX block begins with 3 bits that determines the block type.  Below are
  32  * the valid block types.  Values 0, and 4 through 7, are invalid. */
  33 #define LZX_BLOCKTYPE_VERBATIM       1
  34 #define LZX_BLOCKTYPE_ALIGNED        2
  35 #define LZX_BLOCKTYPE_UNCOMPRESSED   3
  36
  37 #define LZX_NUM_PRIMARY_LENS         7
  38
  39 /* The number of position slots varies from 30 to 51 depending on the window
  40  * size (see comment in lzx-decompress.c).  */
  41 #define LZX_MAX_POSITION_SLOTS          51
  42
  43 #define LZX_MIN_WINDOW_ORDER    15
  44 #define LZX_MAX_WINDOW_ORDER    21
  45 #define LZX_MIN_WINDOW_SIZE     (1U << LZX_MIN_WINDOW_ORDER)  /* 32768   */
  46 #define LZX_MAX_WINDOW_SIZE     (1U << LZX_MAX_WINDOW_ORDER)  /* 2097152 */
  47
  48 /* Read the LZX specification for information about the Huffman trees used in
  49  * the LZX compression format.  Basically there are 4 of them: The main tree,
  50  * the length tree, the pre tree, and the aligned tree.  The main tree and
  51  * length tree are given at the beginning of VERBATIM and ALIGNED blocks as a
  52  * list of *_NUM_SYMBOLS code length values.  They are read using the
  53  * read_code_lens() function and built using the make_decode_table() function.
  54  * The decode table is not a real tree but rather a table that we can index by
  55  * some number of bits (*_TABLEBITS) of the input to quickly look up the symbol
  56  * corresponding to a Huffman code.
  57  *
  58  * The ALIGNED tree is only present on ALIGNED blocks.
  59  *
  60  * A PRECODE is used to encode the code lengths for the main tree and the length
  61  * tree.  There is a separate pretree for each half of the main tree.  */
  62
  63 #define LZX_MAINCODE_MAX_NUM_SYMBOLS    (LZX_NUM_CHARS + (LZX_MAX_POSITION_SLOTS << 3))
  64 #define LZX_MAINCODE_TABLEBITS          11
  65
  66 #define LZX_LENCODE_NUM_SYMBOLS         249
  67 #define LZX_LENCODE_TABLEBITS           10
  68
  69 #define LZX_PRECODE_NUM_SYMBOLS         20
  70 #define LZX_PRECODE_TABLEBITS           6
  71 #define LZX_PRECODE_ELEMENT_SIZE        4
  72
  73 #define LZX_ALIGNEDCODE_NUM_SYMBOLS     8
  74 #define LZX_ALIGNEDCODE_TABLEBITS       7
  75 #define LZX_ALIGNEDCODE_ELEMENT_SIZE    3
  76
  77 /* Maximum allowed length of Huffman codewords.  */
  78 #define LZX_MAX_MAIN_CODEWORD_LEN       16
  79 #define LZX_MAX_LEN_CODEWORD_LEN        16
  80 #define LZX_MAX_PRE_CODEWORD_LEN        16
  81 #define LZX_MAX_ALIGNED_CODEWORD_LEN    8
  82
  83 /* For the LZX-compressed blocks in WIM files, this value is always used as the
  84  * filesize parameter for the call instruction (0xe8 byte) preprocessing, even
  85  * though the blocks themselves are not this size, and the size of the actual
  86  * file resource in the WIM file is very likely to be something entirely
  87  * different as well.  */
  88 #define LZX_WIM_MAGIC_FILESIZE          12000000
  89
  90 /* Assumed LZX block size when the encoded block size begins with a 0 bit.  */
  91 #define LZX_DEFAULT_BLOCK_SIZE          32768
  92
  93 #define USE_LZX_EXTRA_BITS_ARRAY
  94
  95 #ifdef USE_LZX_EXTRA_BITS_ARRAY
  96 extern const u8 lzx_extra_bits[LZX_MAX_POSITION_SLOTS];
  97 #endif
  98
  99 /* Given the number of an LZX position slot, return the number of extra bits that
 100  * are needed to encode the match offset. */
 101 static inline unsigned
 102 lzx_get_num_extra_bits(unsigned position_slot)
 103 {
 104 #ifdef USE_LZX_EXTRA_BITS_ARRAY
 105         /* Use a table */
 106         return lzx_extra_bits[position_slot];
 107 #else
 108         /* Calculate directly using a shift and subtraction. */
 109         LZX_ASSERT(position_slot >= 2 && position_slot <= 37);
 110         return (position_slot >> 1) - 1;
 111 #endif
 112 }
 113
 114 extern const u32 lzx_position_base[LZX_MAX_POSITION_SLOTS];
 115
 116 /* Returns the LZX position slot that corresponds to a given formatted offset.
 117  *
 118  * Logically, this returns the smallest i such that
 119  * formatted_offset >= lzx_position_base[i].
 120  *
 121  * The actual implementation below takes advantage of the regularity of the
 122  * numbers in the lzx_position_base array to calculate the slot directly from
 123  * the formatted offset without actually looking at the array.
 124  */
 125 static inline unsigned
 126 lzx_get_position_slot_raw(u32 formatted_offset)
 127 {
 128         if (formatted_offset >= 196608) {
 129                 return (formatted_offset >> 17) + 34;
 130         } else {
 131                 LZX_ASSERT(2 <= formatted_offset && formatted_offset < 655360);
 132                 unsigned mssb_idx = bsr32(formatted_offset);
 133                 return (mssb_idx << 1) |
 134                         ((formatted_offset >> (mssb_idx - 1)) & 1);
 135         }
 136 }
 137
 138 extern bool lzx_window_size_valid(size_t window_size);
 139 extern unsigned lzx_get_num_main_syms(u32 window_size);
 140
 141 #define LZX_NUM_RECENT_OFFSETS  3
 142
 143 /* Least-recently used queue for match offsets.  */
 144 struct lzx_lru_queue {
 145         u32 R[LZX_NUM_RECENT_OFFSETS];
 146 }
 147 #ifdef __x86_64__
 148 _aligned_attribute(8)  /* Improves performance of LZX compression by 1% - 2%;
 149                           specifically, this speeds up
 150                           lzx_get_near_optimal_match().  */
 151 #endif
 152 ;
 153
 154 /* In the LZX format, an offset of n bytes is actually encoded
 155  * as (n + LZX_OFFSET_OFFSET).  */
 156 #define LZX_OFFSET_OFFSET       (LZX_NUM_RECENT_OFFSETS - 1)
 157
 158 /* Initialize the LZX least-recently-used match offset queue at the beginning of
 159  * a new window for either decompression or compression.  */
 160 static inline void
 161 lzx_lru_queue_init(struct lzx_lru_queue *queue)
 162 {
 163         for (unsigned i = 0; i < LZX_NUM_RECENT_OFFSETS; i++)
 164                 queue->R[i] = 1;
 165 }
 166
 167 extern void
 168 lzx_do_e8_preprocessing(u8 *data, s32 size);
 169
 170 extern void
 171 lzx_undo_e8_preprocessing(u8 *data, s32 size);
 172
 173 #endif /* _WIMLIB_LZX_H */