1 ///////////////////////////////////////////////////////////////////////////////
3 /// \file range_encoder.h
4 /// \brief Range Encoder
6 // Copyright (C) 1999-2006 Igor Pavlov
7 // Copyright (C) 2007-2008 Lasse Collin
9 // This library is free software; you can redistribute it and/or
10 // modify it under the terms of the GNU Lesser General Public
11 // License as published by the Free Software Foundation; either
12 // version 2.1 of the License, or (at your option) any later version.
14 // This library is distributed in the hope that it will be useful,
15 // but WITHOUT ANY WARRANTY; without even the implied warranty of
16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 // Lesser General Public License for more details.
19 ///////////////////////////////////////////////////////////////////////////////
21 #ifndef LZMA_RANGE_ENCODER_H
22 #define LZMA_RANGE_ENCODER_H
24 #include "range_common.h"
28 /// Maximum number of symbols that can be put pending into lzma_range_encoder
29 /// structure between calls to lzma_rc_encode(). For LZMA, 52+5 is enough
30 /// (match with big distance and length followed by range encoder flush).
31 #define RC_SYMBOLS_MAX 58
40 /// Number of symbols in the tables
43 /// rc_encode()'s position in the tables
53 } symbols[RC_SYMBOLS_MAX];
55 /// Probabilities associated with RC_BIT_0 or RC_BIT_1
56 probability *probs[RC_SYMBOLS_MAX];
62 rc_reset(lzma_range_encoder *rc)
66 rc->range = UINT32_MAX;
74 rc_bit(lzma_range_encoder *rc, probability *prob, uint32_t bit)
76 rc->symbols[rc->count] = bit;
77 rc->probs[rc->count] = prob;
83 rc_bittree(lzma_range_encoder *rc, probability *probs,
84 uint32_t bit_count, uint32_t symbol)
86 uint32_t model_index = 1;
89 const uint32_t bit = (symbol >> --bit_count) & 1;
90 rc_bit(rc, &probs[model_index], bit);
91 model_index = (model_index << 1) + bit;
92 } while (bit_count != 0);
97 rc_bittree_reverse(lzma_range_encoder *rc, probability *probs,
98 uint32_t bit_count, uint32_t symbol)
100 uint32_t model_index = 1;
103 const uint32_t bit = symbol & 1;
105 rc_bit(rc, &probs[model_index], bit);
106 model_index = (model_index << 1) + bit;
107 } while (--bit_count != 0);
112 rc_direct(lzma_range_encoder *rc,
113 uint32_t value, uint32_t bit_count)
116 rc->symbols[rc->count++]
117 = RC_DIRECT_0 + ((value >> --bit_count) & 1);
118 } while (bit_count != 0);
123 rc_flush(lzma_range_encoder *rc)
125 for (size_t i = 0; i < 5; ++i)
126 rc->symbols[rc->count++] = RC_FLUSH;
131 rc_shift_low(lzma_range_encoder *rc,
132 uint8_t *out, size_t *out_pos, size_t out_size)
134 if ((uint32_t)(rc->low) < (uint32_t)(0xFF000000)
135 || (uint32_t)(rc->low >> 32) != 0) {
137 if (*out_pos == out_size)
140 out[*out_pos] = rc->cache + (uint8_t)(rc->low >> 32);
144 } while (--rc->cache_size != 0);
146 rc->cache = (rc->low >> 24) & 0xFF;
150 rc->low = (rc->low & 0x00FFFFFF) << RC_SHIFT_BITS;
157 rc_encode(lzma_range_encoder *rc,
158 uint8_t *out, size_t *out_pos, size_t out_size)
160 assert(rc->count <= RC_SYMBOLS_MAX);
162 while (rc->pos < rc->count) {
164 if (rc->range < RC_TOP_VALUE) {
165 if (rc_shift_low(rc, out, out_pos, out_size))
168 rc->range <<= RC_SHIFT_BITS;
172 switch (rc->symbols[rc->pos]) {
174 probability prob = *rc->probs[rc->pos];
175 rc->range = (rc->range >> RC_BIT_MODEL_TOTAL_BITS)
177 prob += (RC_BIT_MODEL_TOTAL - prob) >> RC_MOVE_BITS;
178 *rc->probs[rc->pos] = prob;
183 probability prob = *rc->probs[rc->pos];
184 const uint32_t bound = prob * (rc->range
185 >> RC_BIT_MODEL_TOTAL_BITS);
188 prob -= prob >> RC_MOVE_BITS;
189 *rc->probs[rc->pos] = prob;
199 rc->low += rc->range;
203 // Prevent further normalizations.
204 rc->range = UINT32_MAX;
206 // Flush the last five bytes (see rc_flush()).
208 if (rc_shift_low(rc, out, out_pos, out_size))
210 } while (++rc->pos < rc->count);
212 // Reset the range encoder so we are ready to continue
213 // encoding if we weren't finishing the stream.
232 static inline uint64_t
233 rc_pending(const lzma_range_encoder *rc)
235 return rc->cache_size + 5 - 1;