The R Project SVN R

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
49813 ripley 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
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
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
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
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
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
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
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
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
226 
rc_pending(const lzma_range_encoder *rc)
227 
{
228 
	return rc->cache_size + 5 - 1;
229 
}
230 
 
231 
#endif