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

   1 #ifndef _WIMLIB_LZMS_H
   2 #define _WIMLIB_LZMS_H
   3
   4 /* Constants for the LZMS data compression format.  See the comments in
   5  * lzms-decompress.c for more information about this format.  */
   6
   7 //#define ENABLE_LZMS_DEBUG
   8 #ifdef ENABLE_LZMS_DEBUG
   9 #       define LZMS_DEBUG DEBUG
  10 #       define LZMS_ASSERT wimlib_assert
  11 #       include "wimlib/assert.h"
  12 #       include "wimlib/error.h"
  13 #else
  14 #       define LZMS_DEBUG(format, ...)
  15 #       define LZMS_ASSERT(...)
  16 #endif
  17
  18 #define LZMS_NUM_RECENT_OFFSETS                 3
  19 #define LZMS_MAX_INIT_RECENT_OFFSET             (LZMS_NUM_RECENT_OFFSETS + 1)
  20
  21 #define LZMS_PROBABILITY_BITS                   6
  22 #define LZMS_PROBABILITY_MAX                    (1U << LZMS_PROBABILITY_BITS)
  23 #define LZMS_INITIAL_PROBABILITY                48
  24 #define LZMS_INITIAL_RECENT_BITS                0x0000000055555555ULL
  25
  26 #define LZMS_NUM_MAIN_STATES                    16
  27 #define LZMS_NUM_MATCH_STATES                   32
  28 #define LZMS_NUM_LZ_MATCH_STATES                64
  29 #define LZMS_NUM_LZ_REPEAT_MATCH_STATES         64
  30 #define LZMS_NUM_DELTA_MATCH_STATES             64
  31 #define LZMS_NUM_DELTA_REPEAT_MATCH_STATES      64
  32 #define LZMS_MAX_NUM_STATES                     64
  33
  34 #define LZMS_NUM_LITERAL_SYMS                   256
  35 #define LZMS_NUM_LEN_SYMS                       54
  36 #define LZMS_NUM_DELTA_POWER_SYMS               8
  37 #define LZMS_MAX_NUM_OFFSET_SYMS                799
  38 #define LZMS_MAX_NUM_SYMS                       799
  39
  40 #define LZMS_MAX_CODEWORD_LEN                   15
  41
  42 #define LZMS_LITERAL_CODE_REBUILD_FREQ          1024
  43 #define LZMS_LZ_OFFSET_CODE_REBUILD_FREQ        1024
  44 #define LZMS_LENGTH_CODE_REBUILD_FREQ           512
  45 #define LZMS_DELTA_OFFSET_CODE_REBUILD_FREQ     1024
  46 #define LZMS_DELTA_POWER_CODE_REBUILD_FREQ      512
  47
  48 #define LZMS_X86_MAX_GOOD_TARGET_OFFSET         65535
  49 #define LZMS_X86_MAX_TRANSLATION_OFFSET         1023
  50
  51 /* Code shared between the LZMS decompressor and compressor.  */
  52
  53 #include <wimlib/util.h>
  54
  55 extern void
  56 lzms_x86_filter(u8 data[], s32 size, s32 last_target_usages[], bool undo);
  57
  58 /* Probability entry for use by the range coder when in a specific state.  */
  59 struct lzms_probability_entry {
  60
  61         /* Number of zeroes in the most recent LZMS_PROBABILITY_MAX bits that
  62          * have been coded using this probability entry.  This is a cached value
  63          * because it can be computed as LZMS_PROBABILITY_MAX minus the Hamming
  64          * weight of the low-order LZMS_PROBABILITY_MAX bits of @recent_bits.
  65          * */
  66         u32 num_recent_zero_bits;
  67
  68         /* The most recent LZMS_PROBABILITY_MAX bits that have been coded using
  69          * this probability entry.  The size of this variable, in bits, must be
  70          * at least LZMS_PROBABILITY_MAX.  */
  71         u64 recent_bits;
  72 };
  73
  74 /* LRU queues for LZ matches.  */
  75 struct lzms_lz_lru_queues {
  76
  77         /* Recent LZ match offsets  */
  78         u32 recent_offsets[LZMS_NUM_RECENT_OFFSETS + 1];
  79
  80         /* These variables are used to delay updates to the LRU queues by one
  81          * decoded item.  */
  82         u32 prev_offset;
  83         u32 upcoming_offset;
  84 };
  85
  86 /* LRU queues for delta matches.  */
  87 struct lzms_delta_lru_queues {
  88
  89         /* Recent delta match powers and offsets  */
  90         u32 recent_powers[LZMS_NUM_RECENT_OFFSETS + 1];
  91         u32 recent_offsets[LZMS_NUM_RECENT_OFFSETS + 1];
  92
  93         /* These variables are used to delay updates to the LRU queues by one
  94          * decoded item.  */
  95         u32 prev_power;
  96         u32 prev_offset;
  97         u32 upcoming_power;
  98         u32 upcoming_offset;
  99 };
 100
 101 /* LRU (least-recently-used) queues for match information.  */
 102 struct lzms_lru_queues {
 103         struct lzms_lz_lru_queues lz;
 104         struct lzms_delta_lru_queues delta;
 105 };
 106
 107 extern u32 lzms_position_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1];
 108
 109 extern u8 lzms_extra_position_bits[LZMS_MAX_NUM_OFFSET_SYMS];
 110
 111 extern u16 lzms_order_to_position_slot_bounds[30][2];
 112
 113 extern u32 lzms_length_slot_base[LZMS_NUM_LEN_SYMS + 1];
 114
 115 #define LZMS_NUM_FAST_LENGTHS 1024
 116 extern u8 lzms_length_slot_fast[LZMS_NUM_FAST_LENGTHS];
 117
 118 extern u8 lzms_extra_length_bits[LZMS_NUM_LEN_SYMS];
 119
 120 extern void
 121 lzms_init_slots(void);
 122
 123 /* Return the slot for the specified value.  */
 124 extern u32
 125 lzms_get_slot(u32 value, const u32 slot_base_tab[], u32 num_slots);
 126
 127 static inline u32
 128 lzms_get_position_slot(u32 position)
 129 {
 130         u32 order = bsr32(position);
 131         u32 l = lzms_order_to_position_slot_bounds[order][0];
 132         u32 r = lzms_order_to_position_slot_bounds[order][1];
 133
 134         for (;;) {
 135                 u32 slot = (l + r) / 2;
 136                 if (position >= lzms_position_slot_base[slot]) {
 137                         if (position < lzms_position_slot_base[slot + 1])
 138                                 return slot;
 139                         else
 140                                 l = slot + 1;
 141                 } else {
 142                         r = slot - 1;
 143                 }
 144         }
 145 }
 146
 147 static inline u32
 148 lzms_get_length_slot(u32 length)
 149 {
 150         if (likely(length < LZMS_NUM_FAST_LENGTHS))
 151                 return lzms_length_slot_fast[length];
 152         else
 153                 return lzms_get_slot(length, lzms_length_slot_base,
 154                                      LZMS_NUM_LEN_SYMS);
 155 }
 156
 157 extern void
 158 lzms_init_lru_queues(struct lzms_lru_queues *lru);
 159
 160 extern void
 161 lzms_update_lz_lru_queues(struct lzms_lz_lru_queues *lz);
 162
 163 extern void
 164 lzms_update_delta_lru_queues(struct lzms_delta_lru_queues *delta);
 165
 166 extern void
 167 lzms_update_lru_queues(struct lzms_lru_queues *lru);
 168
 169 #endif /* _WIMLIB_LZMS_H  */