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
27typedef 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
54static inline void
55rc_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
66static inline void
67rc_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
75static inline void
76rc_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
89static inline void
90rc_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
104static inline void
105rc_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
115static inline void
116rc_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
123static inline bool
124rc_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
149static inline bool
150rc_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
225static inline uint64_t
226rc_pending(const lzma_range_encoder *rc)
227{
228	return rc->cache_size + 5 - 1;
229}
230
231#endif
232