1 ///////////////////////////////////////////////////////////////////////////////
2 //
3 /// \file range_encoder.h
4 /// \brief Range Encoder
5 ///
6 // Authors: Igor Pavlov
7 // Lasse Collin
8 //
9 // This file has been put into the public domain.
10 // You can do whatever you want with this file.
11 //
12 ///////////////////////////////////////////////////////////////////////////////
13
14 #ifndef LZMA_RANGE_ENCODER_H
15 #define LZMA_RANGE_ENCODER_H
16
17 #include "range_common.h"
18 #include "price.h"
19
20
21 /// Maximum number of symbols that can be put pending into lzma_range_encoder
22 /// structure between calls to lzma_rc_encode(). For LZMA, 52+5 is enough
23 /// (match with big distance and length followed by range encoder flush).
24 #define RC_SYMBOLS_MAX 58
25
26
27 typedef struct {
28 uint64_t low;
29 uint64_t cache_size;
30 uint32_t range;
31 uint8_t cache;
32
33 /// Number of symbols in the tables
34 size_t count;
35
36 /// rc_encode()'s position in the tables
37 size_t pos;
38
39 /// Symbols to encode
40 enum {
41 RC_BIT_0,
42 RC_BIT_1,
43 RC_DIRECT_0,
44 RC_DIRECT_1,
45 RC_FLUSH,
46 } symbols[RC_SYMBOLS_MAX];
47
48 /// Probabilities associated with RC_BIT_0 or RC_BIT_1
49 probability *probs[RC_SYMBOLS_MAX];
50
51 } lzma_range_encoder;
52
53
54 static inline void
rc_reset(lzma_range_encoder * rc)55 rc_reset(lzma_range_encoder *rc)
56 {
57 rc->low = 0;
58 rc->cache_size = 1;
59 rc->range = UINT32_MAX;
60 rc->cache = 0;
61 rc->count = 0;
62 rc->pos = 0;
63 }
64
65
66 static inline void
rc_bit(lzma_range_encoder * rc,probability * prob,uint32_t bit)67 rc_bit(lzma_range_encoder *rc, probability *prob, uint32_t bit)
68 {
69 rc->symbols[rc->count] = bit;
70 rc->probs[rc->count] = prob;
71 ++rc->count;
72 }
73
74
75 static inline void
rc_bittree(lzma_range_encoder * rc,probability * probs,uint32_t bit_count,uint32_t symbol)76 rc_bittree(lzma_range_encoder *rc, probability *probs,
77 uint32_t bit_count, uint32_t symbol)
78 {
79 uint32_t model_index = 1;
80
81 do {
82 const uint32_t bit = (symbol >> --bit_count) & 1;
83 rc_bit(rc, &probs[model_index], bit);
84 model_index = (model_index << 1) + bit;
85 } while (bit_count != 0);
86 }
87
88
89 static inline void
rc_bittree_reverse(lzma_range_encoder * rc,probability * probs,uint32_t bit_count,uint32_t symbol)90 rc_bittree_reverse(lzma_range_encoder *rc, probability *probs,
91 uint32_t bit_count, uint32_t symbol)
92 {
93 uint32_t model_index = 1;
94
95 do {
96 const uint32_t bit = symbol & 1;
97 symbol >>= 1;
98 rc_bit(rc, &probs[model_index], bit);
99 model_index = (model_index << 1) + bit;
100 } while (--bit_count != 0);
101 }
102
103
104 static inline void
rc_direct(lzma_range_encoder * rc,uint32_t value,uint32_t bit_count)105 rc_direct(lzma_range_encoder *rc,
106 uint32_t value, uint32_t bit_count)
107 {
108 do {
109 rc->symbols[rc->count++]
110 = RC_DIRECT_0 + ((value >> --bit_count) & 1);
111 } while (bit_count != 0);
112 }
113
114
115 static inline void
rc_flush(lzma_range_encoder * rc)116 rc_flush(lzma_range_encoder *rc)
117 {
118 for (size_t i = 0; i < 5; ++i)
119 rc->symbols[rc->count++] = RC_FLUSH;
120 }
121
122
123 static inline bool
rc_shift_low(lzma_range_encoder * rc,uint8_t * out,size_t * out_pos,size_t out_size)124 rc_shift_low(lzma_range_encoder *rc,
125 uint8_t *out, size_t *out_pos, size_t out_size)
126 {
127 if ((uint32_t)(rc->low) < (uint32_t)(0xFF000000)
128 || (uint32_t)(rc->low >> 32) != 0) {
129 do {
130 if (*out_pos == out_size)
131 return true;
132
133 out[*out_pos] = rc->cache + (uint8_t)(rc->low >> 32);
134 ++*out_pos;
135 rc->cache = 0xFF;
136
137 } while (--rc->cache_size != 0);
138
139 rc->cache = (rc->low >> 24) & 0xFF;
140 }
141
142 ++rc->cache_size;
143 rc->low = (rc->low & 0x00FFFFFF) << RC_SHIFT_BITS;
144
145 return false;
146 }
147
148
149 static inline bool
rc_encode(lzma_range_encoder * rc,uint8_t * out,size_t * out_pos,size_t out_size)150 rc_encode(lzma_range_encoder *rc,
151 uint8_t *out, size_t *out_pos, size_t out_size)
152 {
153 assert(rc->count <= RC_SYMBOLS_MAX);
154
155 while (rc->pos < rc->count) {
156 // Normalize
157 if (rc->range < RC_TOP_VALUE) {
158 if (rc_shift_low(rc, out, out_pos, out_size))
159 return true;
160
161 rc->range <<= RC_SHIFT_BITS;
162 }
163
164 // Encode a bit
165 switch (rc->symbols[rc->pos]) {
166 case RC_BIT_0: {
167 probability prob = *rc->probs[rc->pos];
168 rc->range = (rc->range >> RC_BIT_MODEL_TOTAL_BITS)
169 * prob;
170 prob += (RC_BIT_MODEL_TOTAL - prob) >> RC_MOVE_BITS;
171 *rc->probs[rc->pos] = prob;
172 break;
173 }
174
175 case RC_BIT_1: {
176 probability prob = *rc->probs[rc->pos];
177 const uint32_t bound = prob * (rc->range
178 >> RC_BIT_MODEL_TOTAL_BITS);
179 rc->low += bound;
180 rc->range -= bound;
181 prob -= prob >> RC_MOVE_BITS;
182 *rc->probs[rc->pos] = prob;
183 break;
184 }
185
186 case RC_DIRECT_0:
187 rc->range >>= 1;
188 break;
189
190 case RC_DIRECT_1:
191 rc->range >>= 1;
192 rc->low += rc->range;
193 break;
194
195 case RC_FLUSH:
196 // Prevent further normalizations.
197 rc->range = UINT32_MAX;
198
199 // Flush the last five bytes (see rc_flush()).
200 do {
201 if (rc_shift_low(rc, out, out_pos, out_size))
202 return true;
203 } while (++rc->pos < rc->count);
204
205 // Reset the range encoder so we are ready to continue
206 // encoding if we weren't finishing the stream.
207 rc_reset(rc);
208 return false;
209
210 default:
211 assert(0);
212 break;
213 }
214
215 ++rc->pos;
216 }
217
218 rc->count = 0;
219 rc->pos = 0;
220
221 return false;
222 }
223
224
225 static inline uint64_t
rc_pending(const lzma_range_encoder * rc)226 rc_pending(const lzma_range_encoder *rc)
227 {
228 return rc->cache_size + 5 - 1;
229 }
230
231 #endif
232