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 #else
  12 #       define LZMS_DEBUG(format, ...)
  13 #       define LZMS_ASSERT(...)
  14 #endif
  15
  16 #define LZMS_NUM_RECENT_OFFSETS                 3
  17
  18 #define LZMS_PROBABILITY_BITS                   6
  19 #define LZMS_PROBABILITY_MAX                    (1U << LZMS_PROBABILITY_BITS)
  20 #define LZMS_INITIAL_PROBABILITY                48
  21 #define LZMS_INITIAL_RECENT_BITS                0x0000000055555555ULL
  22
  23 #define LZMS_NUM_MAIN_STATES                    16
  24 #define LZMS_NUM_MATCH_STATES                   32
  25 #define LZMS_NUM_LZ_MATCH_STATES                64
  26 #define LZMS_NUM_LZ_REPEAT_MATCH_STATES         64
  27 #define LZMS_NUM_DELTA_MATCH_STATES             64
  28 #define LZMS_NUM_DELTA_REPEAT_MATCH_STATES      64
  29 #define LZMS_MAX_NUM_STATES                     64
  30
  31 #define LZMS_NUM_LITERAL_SYMS                   256
  32 #define LZMS_NUM_LEN_SYMS                       54
  33 #define LZMS_NUM_DELTA_POWER_SYMS               8
  34 #define LZMS_MAX_NUM_OFFSET_SYMS                799
  35 #define LZMS_MAX_NUM_SYMS                       799
  36
  37 #define LZMS_MAX_CODEWORD_LEN                   15
  38
  39 #define LZMS_LITERAL_CODE_REBUILD_FREQ          1024
  40 #define LZMS_LZ_OFFSET_CODE_REBUILD_FREQ        1024
  41 #define LZMS_LENGTH_CODE_REBUILD_FREQ           512
  42 #define LZMS_DELTA_OFFSET_CODE_REBUILD_FREQ     1024
  43 #define LZMS_DELTA_POWER_CODE_REBUILD_FREQ      512
  44
  45 #define LZMS_X86_MAX_GOOD_TARGET_OFFSET         65535
  46 #define LZMS_X86_MAX_TRANSLATION_OFFSET         1023
  47
  48 /* Code shared between the LZMS decompressor and compressor.  */
  49
  50 #include <wimlib/types.h>
  51
  52 extern void
  53 lzms_x86_filter(u8 data[], s32 size, s32 last_target_usages[], bool undo);
  54
  55 /* Probability entry for use by the range coder when in a specific state.  */
  56 struct lzms_probability_entry {
  57
  58         /* Number of zeroes in the most recent LZMS_PROBABILITY_MAX bits that
  59          * have been coded using this probability entry.  This is a cached value
  60          * because it can be computed as LZMS_PROBABILITY_MAX minus the Hamming
  61          * weight of the low-order LZMS_PROBABILITY_MAX bits of @recent_bits.
  62          * */
  63         u32 num_recent_zero_bits;
  64
  65         /* The most recent LZMS_PROBABILITY_MAX bits that have been coded using
  66          * this probability entry.  The size of this variable, in bits, must be
  67          * at least LZMS_PROBABILITY_MAX.  */
  68         u64 recent_bits;
  69 };
  70
  71 /* LRU queues for LZ matches.  */
  72 struct lzms_lz_lru_queues {
  73
  74         /* Recent LZ match offsets  */
  75         u32 recent_offsets[LZMS_NUM_RECENT_OFFSETS + 1];
  76
  77         /* These variables are used to delay updates to the LRU queues by one
  78          * decoded item.  */
  79         u32 prev_offset;
  80         u32 upcoming_offset;
  81 };
  82
  83 /* LRU queues for delta matches.  */
  84 struct lzms_delta_lru_queues {
  85
  86         /* Recent delta match powers and offsets  */
  87         u32 recent_powers[LZMS_NUM_RECENT_OFFSETS + 1];
  88         u32 recent_offsets[LZMS_NUM_RECENT_OFFSETS + 1];
  89
  90         /* These variables are used to delay updates to the LRU queues by one
  91          * decoded item.  */
  92         u32 prev_power;
  93         u32 prev_offset;
  94         u32 upcoming_power;
  95         u32 upcoming_offset;
  96 };
  97
  98 /* LRU (least-recently-used) queues for match information.  */
  99 struct lzms_lru_queues {
 100         struct lzms_lz_lru_queues lz;
 101         struct lzms_delta_lru_queues delta;
 102 };
 103
 104 extern u32 lzms_position_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1];
 105
 106 extern u32 lzms_length_slot_base[LZMS_NUM_LEN_SYMS + 1];
 107
 108 extern void
 109 lzms_init_slot_bases(void);
 110
 111 extern u32
 112 lzms_get_slot(u32 value, const u32 slot_base_tab[], unsigned num_slots);
 113
 114 static inline u32
 115 lzms_get_position_slot(u32 value)
 116 {
 117         return lzms_get_slot(value, lzms_position_slot_base,
 118                              LZMS_MAX_NUM_OFFSET_SYMS);
 119 }
 120
 121 static inline u32
 122 lzms_get_length_slot(u32 value)
 123 {
 124         return lzms_get_slot(value, lzms_length_slot_base,
 125                              LZMS_NUM_LEN_SYMS);
 126 }
 127
 128 extern void
 129 lzms_init_lru_queues(struct lzms_lru_queues *lru);
 130
 131 extern void
 132 lzms_update_lru_queues(struct lzms_lru_queues *lru);
 133
 134 #endif /* _WIMLIB_LZMS_H  */