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

   1 /*
   2  * lzms.h
   3  *
   4  * Declarations shared between LZMS compression and decompression.
   5  */
   6
   7 #ifndef _WIMLIB_LZMS_H
   8 #define _WIMLIB_LZMS_H
   9
  10 #include "wimlib/lzms_constants.h"
  11 #include "wimlib/util.h"
  12
  13 //#define ENABLE_LZMS_DEBUG
  14 #ifdef ENABLE_LZMS_DEBUG
  15 #       define LZMS_DEBUG DEBUG
  16 #       define LZMS_ASSERT wimlib_assert
  17 #       include "wimlib/assert.h"
  18 #       include "wimlib/error.h"
  19 #else
  20 #       define LZMS_DEBUG(format, ...)
  21 #       define LZMS_ASSERT(...)
  22 #endif
  23
  24 extern void
  25 lzms_x86_filter(u8 data[], s32 size, s32 last_target_usages[], bool undo);
  26
  27 /* Probability entry for use by the range coder when in a specific state.  */
  28 struct lzms_probability_entry {
  29
  30         /* Number of zeroes in the most recent LZMS_PROBABILITY_MAX bits that
  31          * have been coded using this probability entry.  This is a cached value
  32          * because it can be computed as LZMS_PROBABILITY_MAX minus the number
  33          * of bits set in the low-order LZMS_PROBABILITY_MAX bits of
  34          * @recent_bits.  */
  35         u32 num_recent_zero_bits;
  36
  37         /* The most recent LZMS_PROBABILITY_MAX bits that have been coded using
  38          * this probability entry.  The size of this variable, in bits, must be
  39          * at least LZMS_PROBABILITY_MAX.  */
  40         u64 recent_bits;
  41 };
  42
  43 /* LRU queues for LZ matches.  */
  44 struct lzms_lz_lru_queues {
  45
  46         /* Recent LZ match offsets  */
  47         u32 recent_offsets[LZMS_NUM_RECENT_OFFSETS + 1];
  48
  49         /* These variables are used to delay updates to the LRU queues by one
  50          * decoded item.  */
  51         u32 prev_offset;
  52         u32 upcoming_offset;
  53 };
  54
  55 /* LRU queues for delta matches.  */
  56 struct lzms_delta_lru_queues {
  57
  58         /* Recent delta match powers and offsets  */
  59         u32 recent_powers[LZMS_NUM_RECENT_OFFSETS + 1];
  60         u32 recent_offsets[LZMS_NUM_RECENT_OFFSETS + 1];
  61
  62         /* These variables are used to delay updates to the LRU queues by one
  63          * decoded item.  */
  64         u32 prev_power;
  65         u32 prev_offset;
  66         u32 upcoming_power;
  67         u32 upcoming_offset;
  68 };
  69
  70 /* LRU (least-recently-used) queues for match information.  */
  71 struct lzms_lru_queues {
  72         struct lzms_lz_lru_queues lz;
  73         struct lzms_delta_lru_queues delta;
  74 };
  75
  76 /* Offset slot tables  */
  77 extern u32 lzms_offset_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1];
  78 extern u8 lzms_extra_offset_bits[LZMS_MAX_NUM_OFFSET_SYMS];
  79
  80 /* Length slot tables  */
  81 extern u32 lzms_length_slot_base[LZMS_NUM_LEN_SYMS + 1];
  82 extern u8 lzms_extra_length_bits[LZMS_NUM_LEN_SYMS];
  83
  84 extern void
  85 lzms_init_slots(void);
  86
  87 extern unsigned
  88 lzms_get_slot(u32 value, const u32 slot_base_tab[], unsigned num_slots);
  89
  90 /* Return the offset slot for the specified offset  */
  91 static inline unsigned
  92 lzms_get_offset_slot(u32 offset)
  93 {
  94         return lzms_get_slot(offset, lzms_offset_slot_base, LZMS_MAX_NUM_OFFSET_SYMS);
  95 }
  96
  97 /* Return the length slot for the specified length  */
  98 static inline unsigned
  99 lzms_get_length_slot(u32 length)
 100 {
 101         return lzms_get_slot(length, lzms_length_slot_base, LZMS_NUM_LEN_SYMS);
 102 }
 103
 104 extern void
 105 lzms_init_lz_lru_queues(struct lzms_lz_lru_queues *lz);
 106
 107 extern void
 108 lzms_init_delta_lru_queues(struct lzms_delta_lru_queues *delta);
 109
 110 extern void
 111 lzms_init_lru_queues(struct lzms_lru_queues *lru);
 112
 113 extern void
 114 lzms_update_lz_lru_queue(struct lzms_lz_lru_queues *lz);
 115
 116 extern void
 117 lzms_update_delta_lru_queues(struct lzms_delta_lru_queues *delta);
 118
 119 extern void
 120 lzms_update_lru_queues(struct lzms_lru_queues *lru);
 121
 122 /* Given a decoded bit, update the probability entry.  */
 123 static inline void
 124 lzms_update_probability_entry(struct lzms_probability_entry *prob_entry, int bit)
 125 {
 126         s32 delta_zero_bits;
 127
 128         BUILD_BUG_ON(LZMS_PROBABILITY_MAX != sizeof(prob_entry->recent_bits) * 8);
 129
 130         delta_zero_bits = (s32)(prob_entry->recent_bits >> (LZMS_PROBABILITY_MAX - 1)) - bit;
 131
 132         prob_entry->num_recent_zero_bits += delta_zero_bits;
 133         prob_entry->recent_bits <<= 1;
 134         prob_entry->recent_bits |= bit;
 135 }
 136
 137 /* Given a probability entry, return the chance out of LZMS_PROBABILITY_MAX that
 138  * the next decoded bit will be a 0.  */
 139 static inline u32
 140 lzms_get_probability(const struct lzms_probability_entry *prob_entry)
 141 {
 142         u32 prob;
 143
 144         prob = prob_entry->num_recent_zero_bits;
 145
 146         /* 0% and 100% probabilities aren't allowed.  */
 147         if (prob == 0)
 148                 prob++;
 149         if (prob == LZMS_PROBABILITY_MAX)
 150                 prob--;
 151         return prob;
 152 }
 153
 154 #endif /* _WIMLIB_LZMS_H  */