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 #ifdef __x86_64__
  80         if (__builtin_constant_p(bit)) {
  81                 /* Optimized implementation for x86_64 using carry flag  */
  82                 if (bit) {
  83                        __asm__("shlq %[recent_bits]                          \n"
  84                                "adcl $0xffffffff, %[num_recent_zero_bits]    \n"
  85                                "orq $0x1, %[recent_bits]                     \n"
  86                                : [recent_bits] "+r" (entry->recent_bits),
  87                                  [num_recent_zero_bits] "+mr" (entry->num_recent_zero_bits)
  88                                :
  89                                : "cc");
  90                 } else {
  91                        __asm__("shlq %[recent_bits]                          \n"
  92                                "adcl $0x0, %[num_recent_zero_bits]           \n"
  93                                : [recent_bits] "+m" (entry->recent_bits),
  94                                  [num_recent_zero_bits] "+mr" (entry->num_recent_zero_bits)
  95                                :
  96                                : "cc");
  97                 }
  98         } else
  99 #endif
 100         {
 101                 s32 delta_zero_bits = (s32)(entry->recent_bits >>
 102                                             (LZMS_PROBABILITY_DENOMINATOR - 1)) - bit;
 103
 104                 entry->num_recent_zero_bits += delta_zero_bits;
 105                 entry->recent_bits = (entry->recent_bits << 1) | bit;
 106         }
 107 }
 108
 109 /* Given a probability entry, return the chance out of
 110  * LZMS_PROBABILITY_DENOMINATOR that the next decoded bit will be a 0.  */
 111 static inline u32
 112 lzms_get_probability(const struct lzms_probability_entry *prob_entry)
 113 {
 114         u32 prob = prob_entry->num_recent_zero_bits;
 115
 116         /* 0% and 100% probabilities aren't allowed.  */
 117
 118         /*
 119          *      if (prob == 0)
 120          *              prob++;
 121          */
 122         prob += (prob - 1) >> 31;
 123
 124         /*
 125          *      if (prob == LZMS_PROBABILITY_DENOMINATOR)
 126          *              prob--;
 127          */
 128         prob -= (prob >> LZMS_PROBABILITY_BITS);
 129
 130         return prob;
 131 }
 132
 133 extern void
 134 lzms_init_symbol_frequencies(u32 freqs[], unsigned num_syms);
 135
 136 extern void
 137 lzms_dilute_symbol_frequencies(u32 freqs[], unsigned num_syms);
 138
 139 /* Pre/post-processing  */
 140 extern void
 141 lzms_x86_filter(u8 data[], s32 size, s32 last_target_usages[], bool undo);
 142
 143 #endif /* _LZMS_COMMON_H */