]> pd.if.org Git - zpackage/blob - lzma/rangecoder/range_encoder.h
add newline to zpm-stat usage message
[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 <stdlib.h>
18 #include <stdbool.h>
19
20 #include <assert.h>
21
22 #include "range_common.h"
23 #include "price.h"
24
25
26 /// Maximum number of symbols that can be put pending into lzma_range_encoder
27 /// structure between calls to lzma_rc_encode(). For LZMA, 52+5 is enough
28 /// (match with big distance and length followed by range encoder flush).
29 #define RC_SYMBOLS_MAX 58
30
31
32 typedef struct {
33         uint64_t low;
34         uint64_t cache_size;
35         uint32_t range;
36         uint8_t cache;
37
38         /// Number of symbols in the tables
39         size_t count;
40
41         /// rc_encode()'s position in the tables
42         size_t pos;
43
44         /// Symbols to encode
45         enum {
46                 RC_BIT_0,
47                 RC_BIT_1,
48                 RC_DIRECT_0,
49                 RC_DIRECT_1,
50                 RC_FLUSH,
51         } symbols[RC_SYMBOLS_MAX];
52
53         /// Probabilities associated with RC_BIT_0 or RC_BIT_1
54         probability *probs[RC_SYMBOLS_MAX];
55
56 } lzma_range_encoder;
57
58
59 static inline void
60 rc_reset(lzma_range_encoder *rc)
61 {
62         rc->low = 0;
63         rc->cache_size = 1;
64         rc->range = UINT32_MAX;
65         rc->cache = 0;
66         rc->count = 0;
67         rc->pos = 0;
68 }
69
70
71 static inline void
72 rc_bit(lzma_range_encoder *rc, probability *prob, uint32_t bit)
73 {
74         rc->symbols[rc->count] = bit;
75         rc->probs[rc->count] = prob;
76         ++rc->count;
77 }
78
79
80 static inline void
81 rc_bittree(lzma_range_encoder *rc, probability *probs,
82                 uint32_t bit_count, uint32_t symbol)
83 {
84         uint32_t model_index = 1;
85
86         do {
87                 const uint32_t bit = (symbol >> --bit_count) & 1;
88                 rc_bit(rc, &probs[model_index], bit);
89                 model_index = (model_index << 1) + bit;
90         } while (bit_count != 0);
91 }
92
93
94 static inline void
95 rc_bittree_reverse(lzma_range_encoder *rc, probability *probs,
96                 uint32_t bit_count, uint32_t symbol)
97 {
98         uint32_t model_index = 1;
99
100         do {
101                 const uint32_t bit = symbol & 1;
102                 symbol >>= 1;
103                 rc_bit(rc, &probs[model_index], bit);
104                 model_index = (model_index << 1) + bit;
105         } while (--bit_count != 0);
106 }
107
108
109 static inline void
110 rc_direct(lzma_range_encoder *rc,
111                 uint32_t value, uint32_t bit_count)
112 {
113         do {
114                 rc->symbols[rc->count++]
115                                 = RC_DIRECT_0 + ((value >> --bit_count) & 1);
116         } while (bit_count != 0);
117 }
118
119
120 static inline void
121 rc_flush(lzma_range_encoder *rc)
122 {
123         for (size_t i = 0; i < 5; ++i)
124                 rc->symbols[rc->count++] = RC_FLUSH;
125 }
126
127
128 static inline bool
129 rc_shift_low(lzma_range_encoder *rc,
130                 uint8_t *out, size_t *out_pos, size_t out_size)
131 {
132         if ((uint32_t)(rc->low) < (uint32_t)(0xFF000000)
133                         || (uint32_t)(rc->low >> 32) != 0) {
134                 do {
135                         if (*out_pos == out_size)
136                                 return true;
137
138                         out[*out_pos] = rc->cache + (uint8_t)(rc->low >> 32);
139                         ++*out_pos;
140                         rc->cache = 0xFF;
141
142                 } while (--rc->cache_size != 0);
143
144                 rc->cache = (rc->low >> 24) & 0xFF;
145         }
146
147         ++rc->cache_size;
148         rc->low = (rc->low & 0x00FFFFFF) << RC_SHIFT_BITS;
149
150         return false;
151 }
152
153
154 static inline bool
155 rc_encode(lzma_range_encoder *rc,
156                 uint8_t *out, size_t *out_pos, size_t out_size)
157 {
158         assert(rc->count <= RC_SYMBOLS_MAX);
159
160         while (rc->pos < rc->count) {
161                 // Normalize
162                 if (rc->range < RC_TOP_VALUE) {
163                         if (rc_shift_low(rc, out, out_pos, out_size))
164                                 return true;
165
166                         rc->range <<= RC_SHIFT_BITS;
167                 }
168
169                 // Encode a bit
170                 switch (rc->symbols[rc->pos]) {
171                 case RC_BIT_0: {
172                         probability prob = *rc->probs[rc->pos];
173                         rc->range = (rc->range >> RC_BIT_MODEL_TOTAL_BITS)
174                                         * prob;
175                         prob += (RC_BIT_MODEL_TOTAL - prob) >> RC_MOVE_BITS;
176                         *rc->probs[rc->pos] = prob;
177                         break;
178                 }
179
180                 case RC_BIT_1: {
181                         probability prob = *rc->probs[rc->pos];
182                         const uint32_t bound = prob * (rc->range
183                                         >> RC_BIT_MODEL_TOTAL_BITS);
184                         rc->low += bound;
185                         rc->range -= bound;
186                         prob -= prob >> RC_MOVE_BITS;
187                         *rc->probs[rc->pos] = prob;
188                         break;
189                 }
190
191                 case RC_DIRECT_0:
192                         rc->range >>= 1;
193                         break;
194
195                 case RC_DIRECT_1:
196                         rc->range >>= 1;
197                         rc->low += rc->range;
198                         break;
199
200                 case RC_FLUSH:
201                         // Prevent further normalizations.
202                         rc->range = UINT32_MAX;
203
204                         // Flush the last five bytes (see rc_flush()).
205                         do {
206                                 if (rc_shift_low(rc, out, out_pos, out_size))
207                                         return true;
208                         } while (++rc->pos < rc->count);
209
210                         // Reset the range encoder so we are ready to continue
211                         // encoding if we weren't finishing the stream.
212                         rc_reset(rc);
213                         return false;
214
215                 default:
216                         assert(0);
217                         break;
218                 }
219
220                 ++rc->pos;
221         }
222
223         rc->count = 0;
224         rc->pos = 0;
225
226         return false;
227 }
228
229
230 static inline uint64_t
231 rc_pending(const lzma_range_encoder *rc)
232 {
233         return rc->cache_size + 5 - 1;
234 }
235
236 #endif