]> pd.if.org Git - zpackage/blob - lzma/rangecoder/range_encoder.h
update to sqlite 3.27.2
[zpackage] / lzma / rangecoder / range_encoder.h
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