Stop force-inlining everything marked 'inline'
[wimlib] / 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 forceinline 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 forceinline 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 forceinline void
75 lzms_update_probability_entry(struct lzms_probability_entry *entry, int bit)
76 {
77         STATIC_ASSERT(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 forceinline 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 += (u32)(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 */