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

   1 /*
   2  * lzms_common.h
   3  *
   4  * Declarations shared between LZMS compression and decompression.
   5  */
   6
   7 #ifndef _LZMS_COMMON_H
   8 #define _LZMS_COMMON_H
   9
  10 #include "wimlib/compiler.h"
  11 #include "wimlib/lzms_constants.h"
  12 #include "wimlib/types.h"
  13
  14 /* Offset slot tables  */
  15 extern const u32 lzms_offset_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1];
  16 extern const u8 lzms_extra_offset_bits[LZMS_MAX_NUM_OFFSET_SYMS];
  17
  18 /* Length slot tables  */
  19 extern const u32 lzms_length_slot_base[LZMS_NUM_LENGTH_SYMS + 1];
  20 extern const u8 lzms_extra_length_bits[LZMS_NUM_LENGTH_SYMS];
  21
  22 extern unsigned
  23 lzms_get_slot(u32 value, const u32 slot_base_tab[], unsigned num_slots);
  24
  25 /* Return the offset slot for the specified offset  */
  26 static inline unsigned
  27 lzms_get_offset_slot(u32 offset)
  28 {
  29         return lzms_get_slot(offset, lzms_offset_slot_base, LZMS_MAX_NUM_OFFSET_SYMS);
  30 }
  31
  32 /* Return the length slot for the specified length  */
  33 static inline unsigned
  34 lzms_get_length_slot(u32 length)
  35 {
  36         return lzms_get_slot(length, lzms_length_slot_base, LZMS_NUM_LENGTH_SYMS);
  37 }
  38
  39 extern unsigned
  40 lzms_get_num_offset_slots(size_t uncompressed_size);
  41
  42
  43 /* Probability entry for use by the range coder when in a specific state  */
  44 struct lzms_probability_entry {
  45
  46         /* The number of zeroes in the most recent LZMS_PROBABILITY_DENOMINATOR
  47          * bits that have been decoded or encoded using this probability entry.
  48          * The probability of the next bit being 0 is this value over
  49          * LZMS_PROBABILITY_DENOMINATOR, except for the cases where this would
  50          * imply 0% or 100% probability.  */
  51         u32 num_recent_zero_bits;
  52
  53         /* The most recent LZMS_PROBABILITY_DENOMINATOR bits that have been
  54          * coded using this probability entry.  The bits are ordered such that
  55          * low order is newest and high order is oldest.  */
  56         u64 recent_bits;
  57 };
  58
  59 struct lzms_probabilites {
  60         struct lzms_probability_entry main[LZMS_NUM_MAIN_PROBS];
  61         struct lzms_probability_entry match[LZMS_NUM_MATCH_PROBS];
  62         struct lzms_probability_entry lz[LZMS_NUM_LZ_PROBS];
  63         struct lzms_probability_entry delta[LZMS_NUM_DELTA_PROBS];
  64         struct lzms_probability_entry lz_rep[LZMS_NUM_LZ_REP_DECISIONS]
  65                                             [LZMS_NUM_LZ_REP_PROBS];
  66         struct lzms_probability_entry delta_rep[LZMS_NUM_DELTA_REP_DECISIONS]
  67                                                [LZMS_NUM_DELTA_REP_PROBS];
  68 };
  69
  70 extern void
  71 lzms_init_probabilities(struct lzms_probabilites *probs);
  72
  73 /* Given a decoded or encoded bit, update the probability entry.  */
  74 static inline void
  75 lzms_update_probability_entry(struct lzms_probability_entry *entry, int bit)
  76 {
  77         BUILD_BUG_ON(LZMS_PROBABILITY_DENOMINATOR != sizeof(entry->recent_bits) * 8);
  78
  79         s32 delta_zero_bits = (s32)(entry->recent_bits >>
  80                                     (LZMS_PROBABILITY_DENOMINATOR - 1)) - bit;
  81
  82         entry->num_recent_zero_bits += delta_zero_bits;
  83         entry->recent_bits = (entry->recent_bits << 1) | bit;
  84 }
  85
  86 /* Given a probability entry, return the chance out of
  87  * LZMS_PROBABILITY_DENOMINATOR that the next decoded bit will be a 0.  */
  88 static inline u32
  89 lzms_get_probability(const struct lzms_probability_entry *prob_entry)
  90 {
  91         u32 prob = prob_entry->num_recent_zero_bits;
  92
  93         /* 0% and 100% probabilities aren't allowed.  */
  94         if (prob == 0)
  95                 prob++;
  96         else if (prob == LZMS_PROBABILITY_DENOMINATOR)
  97                 prob--;
  98         return prob;
  99 }
 100
 101 extern void
 102 lzms_init_symbol_frequencies(u32 freqs[], unsigned num_syms);
 103
 104 extern void
 105 lzms_dilute_symbol_frequencies(u32 freqs[], unsigned num_syms);
 106
 107 /* Pre/post-processing  */
 108 extern void
 109 lzms_x86_filter(u8 data[], s32 size, s32 last_target_usages[], bool undo);
 110
 111 #endif /* _LZMS_COMMON_H */