xref: /freebsd/contrib/xz/src/liblzma/rangecoder/range_encoder.h (revision f126890ac5386406dadf7c4cfa9566cbb56537c5)
1 // SPDX-License-Identifier: 0BSD
2 
3 ///////////////////////////////////////////////////////////////////////////////
4 //
5 /// \file       range_encoder.h
6 /// \brief      Range Encoder
7 ///
8 //  Authors:    Igor Pavlov
9 //              Lasse Collin
10 //
11 ///////////////////////////////////////////////////////////////////////////////
12 
13 #ifndef LZMA_RANGE_ENCODER_H
14 #define LZMA_RANGE_ENCODER_H
15 
16 #include "range_common.h"
17 #include "price.h"
18 
19 
20 /// Maximum number of symbols that can be put pending into lzma_range_encoder
21 /// structure between calls to lzma_rc_encode(). For LZMA, 48+5 is enough
22 /// (match with big distance and length followed by range encoder flush).
23 #define RC_SYMBOLS_MAX 53
24 
25 
26 typedef struct {
27 	uint64_t low;
28 	uint64_t cache_size;
29 	uint32_t range;
30 	uint8_t cache;
31 
32 	/// Number of bytes written out by rc_encode() -> rc_shift_low()
33 	uint64_t out_total;
34 
35 	/// Number of symbols in the tables
36 	size_t count;
37 
38 	/// rc_encode()'s position in the tables
39 	size_t pos;
40 
41 	/// Symbols to encode
42 	enum {
43 		RC_BIT_0,
44 		RC_BIT_1,
45 		RC_DIRECT_0,
46 		RC_DIRECT_1,
47 		RC_FLUSH,
48 	} symbols[RC_SYMBOLS_MAX];
49 
50 	/// Probabilities associated with RC_BIT_0 or RC_BIT_1
51 	probability *probs[RC_SYMBOLS_MAX];
52 
53 } lzma_range_encoder;
54 
55 
56 static inline void
57 rc_reset(lzma_range_encoder *rc)
58 {
59 	rc->low = 0;
60 	rc->cache_size = 1;
61 	rc->range = UINT32_MAX;
62 	rc->cache = 0;
63 	rc->out_total = 0;
64 	rc->count = 0;
65 	rc->pos = 0;
66 }
67 
68 
69 static inline void
70 rc_forget(lzma_range_encoder *rc)
71 {
72 	// This must not be called when rc_encode() is partially done.
73 	assert(rc->pos == 0);
74 	rc->count = 0;
75 }
76 
77 
78 static inline void
79 rc_bit(lzma_range_encoder *rc, probability *prob, uint32_t bit)
80 {
81 	rc->symbols[rc->count] = bit;
82 	rc->probs[rc->count] = prob;
83 	++rc->count;
84 }
85 
86 
87 static inline void
88 rc_bittree(lzma_range_encoder *rc, probability *probs,
89 		uint32_t bit_count, uint32_t symbol)
90 {
91 	uint32_t model_index = 1;
92 
93 	do {
94 		const uint32_t bit = (symbol >> --bit_count) & 1;
95 		rc_bit(rc, &probs[model_index], bit);
96 		model_index = (model_index << 1) + bit;
97 	} while (bit_count != 0);
98 }
99 
100 
101 static inline void
102 rc_bittree_reverse(lzma_range_encoder *rc, probability *probs,
103 		uint32_t bit_count, uint32_t symbol)
104 {
105 	uint32_t model_index = 1;
106 
107 	do {
108 		const uint32_t bit = symbol & 1;
109 		symbol >>= 1;
110 		rc_bit(rc, &probs[model_index], bit);
111 		model_index = (model_index << 1) + bit;
112 	} while (--bit_count != 0);
113 }
114 
115 
116 static inline void
117 rc_direct(lzma_range_encoder *rc,
118 		uint32_t value, uint32_t bit_count)
119 {
120 	do {
121 		rc->symbols[rc->count++]
122 				= RC_DIRECT_0 + ((value >> --bit_count) & 1);
123 	} while (bit_count != 0);
124 }
125 
126 
127 static inline void
128 rc_flush(lzma_range_encoder *rc)
129 {
130 	for (size_t i = 0; i < 5; ++i)
131 		rc->symbols[rc->count++] = RC_FLUSH;
132 }
133 
134 
135 static inline bool
136 rc_shift_low(lzma_range_encoder *rc,
137 		uint8_t *out, size_t *out_pos, size_t out_size)
138 {
139 	if ((uint32_t)(rc->low) < (uint32_t)(0xFF000000)
140 			|| (uint32_t)(rc->low >> 32) != 0) {
141 		do {
142 			if (*out_pos == out_size)
143 				return true;
144 
145 			out[*out_pos] = rc->cache + (uint8_t)(rc->low >> 32);
146 			++*out_pos;
147 			++rc->out_total;
148 			rc->cache = 0xFF;
149 
150 		} while (--rc->cache_size != 0);
151 
152 		rc->cache = (rc->low >> 24) & 0xFF;
153 	}
154 
155 	++rc->cache_size;
156 	rc->low = (rc->low & 0x00FFFFFF) << RC_SHIFT_BITS;
157 
158 	return false;
159 }
160 
161 
162 // NOTE: The last two arguments are uint64_t instead of size_t because in
163 // the dummy version these refer to the size of the whole range-encoded
164 // output stream, not just to the currently available output buffer space.
165 static inline bool
166 rc_shift_low_dummy(uint64_t *low, uint64_t *cache_size, uint8_t *cache,
167 		uint64_t *out_pos, uint64_t out_size)
168 {
169 	if ((uint32_t)(*low) < (uint32_t)(0xFF000000)
170 			|| (uint32_t)(*low >> 32) != 0) {
171 		do {
172 			if (*out_pos == out_size)
173 				return true;
174 
175 			++*out_pos;
176 			*cache = 0xFF;
177 
178 		} while (--*cache_size != 0);
179 
180 		*cache = (*low >> 24) & 0xFF;
181 	}
182 
183 	++*cache_size;
184 	*low = (*low & 0x00FFFFFF) << RC_SHIFT_BITS;
185 
186 	return false;
187 }
188 
189 
190 static inline bool
191 rc_encode(lzma_range_encoder *rc,
192 		uint8_t *out, size_t *out_pos, size_t out_size)
193 {
194 	assert(rc->count <= RC_SYMBOLS_MAX);
195 
196 	while (rc->pos < rc->count) {
197 		// Normalize
198 		if (rc->range < RC_TOP_VALUE) {
199 			if (rc_shift_low(rc, out, out_pos, out_size))
200 				return true;
201 
202 			rc->range <<= RC_SHIFT_BITS;
203 		}
204 
205 		// Encode a bit
206 		switch (rc->symbols[rc->pos]) {
207 		case RC_BIT_0: {
208 			probability prob = *rc->probs[rc->pos];
209 			rc->range = (rc->range >> RC_BIT_MODEL_TOTAL_BITS)
210 					* prob;
211 			prob += (RC_BIT_MODEL_TOTAL - prob) >> RC_MOVE_BITS;
212 			*rc->probs[rc->pos] = prob;
213 			break;
214 		}
215 
216 		case RC_BIT_1: {
217 			probability prob = *rc->probs[rc->pos];
218 			const uint32_t bound = prob * (rc->range
219 					>> RC_BIT_MODEL_TOTAL_BITS);
220 			rc->low += bound;
221 			rc->range -= bound;
222 			prob -= prob >> RC_MOVE_BITS;
223 			*rc->probs[rc->pos] = prob;
224 			break;
225 		}
226 
227 		case RC_DIRECT_0:
228 			rc->range >>= 1;
229 			break;
230 
231 		case RC_DIRECT_1:
232 			rc->range >>= 1;
233 			rc->low += rc->range;
234 			break;
235 
236 		case RC_FLUSH:
237 			// Prevent further normalizations.
238 			rc->range = UINT32_MAX;
239 
240 			// Flush the last five bytes (see rc_flush()).
241 			do {
242 				if (rc_shift_low(rc, out, out_pos, out_size))
243 					return true;
244 			} while (++rc->pos < rc->count);
245 
246 			// Reset the range encoder so we are ready to continue
247 			// encoding if we weren't finishing the stream.
248 			rc_reset(rc);
249 			return false;
250 
251 		default:
252 			assert(0);
253 			break;
254 		}
255 
256 		++rc->pos;
257 	}
258 
259 	rc->count = 0;
260 	rc->pos = 0;
261 
262 	return false;
263 }
264 
265 
266 static inline bool
267 rc_encode_dummy(const lzma_range_encoder *rc, uint64_t out_limit)
268 {
269 	assert(rc->count <= RC_SYMBOLS_MAX);
270 
271 	uint64_t low = rc->low;
272 	uint64_t cache_size = rc->cache_size;
273 	uint32_t range = rc->range;
274 	uint8_t cache = rc->cache;
275 	uint64_t out_pos = rc->out_total;
276 
277 	size_t pos = rc->pos;
278 
279 	while (true) {
280 		// Normalize
281 		if (range < RC_TOP_VALUE) {
282 			if (rc_shift_low_dummy(&low, &cache_size, &cache,
283 					&out_pos, out_limit))
284 				return true;
285 
286 			range <<= RC_SHIFT_BITS;
287 		}
288 
289 		// This check is here because the normalization above must
290 		// be done before flushing the last bytes.
291 		if (pos == rc->count)
292 			break;
293 
294 		// Encode a bit
295 		switch (rc->symbols[pos]) {
296 		case RC_BIT_0: {
297 			probability prob = *rc->probs[pos];
298 			range = (range >> RC_BIT_MODEL_TOTAL_BITS)
299 					* prob;
300 			break;
301 		}
302 
303 		case RC_BIT_1: {
304 			probability prob = *rc->probs[pos];
305 			const uint32_t bound = prob * (range
306 					>> RC_BIT_MODEL_TOTAL_BITS);
307 			low += bound;
308 			range -= bound;
309 			break;
310 		}
311 
312 		case RC_DIRECT_0:
313 			range >>= 1;
314 			break;
315 
316 		case RC_DIRECT_1:
317 			range >>= 1;
318 			low += range;
319 			break;
320 
321 		case RC_FLUSH:
322 		default:
323 			assert(0);
324 			break;
325 		}
326 
327 		++pos;
328 	}
329 
330 	// Flush the last bytes. This isn't in rc->symbols[] so we do
331 	// it after the above loop to take into account the size of
332 	// the flushing that will be done at the end of the stream.
333 	for (pos = 0; pos < 5; ++pos) {
334 		if (rc_shift_low_dummy(&low, &cache_size,
335 				&cache, &out_pos, out_limit))
336 			return true;
337 	}
338 
339 	return false;
340 }
341 
342 
343 static inline uint64_t
344 rc_pending(const lzma_range_encoder *rc)
345 {
346 	return rc->cache_size + 5 - 1;
347 }
348 
349 #endif
350