1#[derive(Clone)]
10pub struct Rc<'a> {
11 buf: &'a [u8],
13 limit: usize,
15 index: usize,
16 rb_pos: usize,
18 rb_bytes: u32,
19 rb_cachelen: u32,
20 rb_cacheval: u32,
21 pub range: u32,
22 pub value: u32,
23 pub total_bits: u32,
24}
25
26const SYM: u32 = 8;
27const CEIL: u32 = (1 << SYM) - 1;
28const TOP: u32 = 1 << 31;
29const BOT: u32 = TOP >> SYM;
30
31#[inline]
32pub fn ilog(i: u32) -> u32 {
33 if i == 0 {
34 0
35 } else {
36 32 - i.leading_zeros()
37 }
38}
39
40#[inline]
41fn log2(v: u32) -> u32 {
42 31 - (v | 1).leading_zeros()
43}
44
45impl<'a> Rc<'a> {
46 pub fn new(buf: &'a [u8], size: usize) -> Self {
48 let mut rc = Rc {
49 buf,
50 limit: size * 8 + 8,
51 index: 0,
52 rb_pos: 0,
53 rb_bytes: 0,
54 rb_cachelen: 0,
55 rb_cacheval: 0,
56 range: 128,
57 value: 0,
58 total_bits: 9,
59 };
60 rc.value = 127 - rc.get_bits(7);
61 rc.normalize();
62 rc
63 }
64
65 #[inline]
66 fn byte(&self, i: usize) -> u32 {
67 self.buf.get(i).copied().unwrap_or(0) as u32
68 }
69
70 #[inline]
71 fn get_bits(&mut self, n: u32) -> u32 {
72 let i = self.index;
73 let b = i >> 3;
74 let w = (self.byte(b) << 24)
75 | (self.byte(b + 1) << 16)
76 | (self.byte(b + 2) << 8)
77 | self.byte(b + 3);
78 let v = (w << (i & 7)) >> (32 - n);
79 self.index = (i + n as usize).min(self.limit);
80 v
81 }
82
83 pub fn raw_init(&mut self, end: usize, bytes: u32) {
85 self.rb_pos = end;
86 self.rb_bytes = bytes;
87 self.rb_cachelen = 0;
88 self.rb_cacheval = 0;
89 }
90
91 pub fn rb_bytes(&self) -> u32 {
92 self.rb_bytes
93 }
94
95 #[inline]
96 fn normalize(&mut self) {
97 while self.range <= BOT {
98 self.value = ((self.value << SYM) | (self.get_bits(SYM) ^ CEIL)) & (TOP - 1);
99 self.range <<= SYM;
100 self.total_bits += SYM;
101 }
102 }
103
104 #[inline]
105 fn update(&mut self, scale: u32, low: u32, high: u32, total: u32) {
106 self.value = self.value.wrapping_sub(scale.wrapping_mul(total - high));
107 self.range = if low != 0 {
108 scale * (high - low)
109 } else {
110 self.range - scale * (total - high)
111 };
112 self.normalize();
113 }
114
115 #[inline]
116 pub fn tell(&self) -> u32 {
117 self.total_bits
118 .wrapping_sub(log2(self.range))
119 .wrapping_sub(1)
120 }
121
122 pub fn tell_frac(&self) -> u32 {
123 let total_bits = self.total_bits << 3;
124 let mut rcbuffer = log2(self.range) + 1;
125 let mut range = self.range >> (rcbuffer - 16);
126 for _ in 0..3 {
127 range = (range * range) >> 15;
128 let bit = range >> 16;
129 rcbuffer = rcbuffer << 1 | bit;
130 range >>= bit;
131 }
132 total_bits.wrapping_sub(rcbuffer)
133 }
134
135 pub fn dec_cdf(&mut self, cdf: &[u16]) -> u32 {
137 let total = cdf[0] as u32;
138 let cdf = &cdf[1..];
139 let scale = self.range / total;
140 let symbol = self.value / scale + 1;
141 let symbol = total - symbol.min(total);
142 let mut k = 0;
143 while cdf[k] as u32 <= symbol {
144 k += 1;
145 }
146 let high = cdf[k] as u32;
147 let low = if k > 0 { cdf[k - 1] as u32 } else { 0 };
148 self.update(scale, low, high, total);
149 k as u32
150 }
151
152 pub fn dec_log(&mut self, bits: u32) -> u32 {
153 let scale = self.range >> bits;
154 let k = if self.value >= scale {
155 self.value -= scale;
156 self.range -= scale;
157 0
158 } else {
159 self.range = scale;
160 1
161 };
162 self.normalize();
163 k
164 }
165
166 pub fn get_raw(&mut self, count: u32) -> u32 {
167 while self.rb_bytes > 0 && self.rb_cachelen < count {
168 self.rb_pos -= 1;
169 self.rb_cacheval |= (self.buf[self.rb_pos] as u32) << self.rb_cachelen;
170 self.rb_cachelen += 8;
171 self.rb_bytes -= 1;
172 }
173 let value = if count >= 32 {
174 self.rb_cacheval
175 } else {
176 self.rb_cacheval & ((1u32 << count) - 1)
177 };
178 self.rb_cacheval = if count >= 32 {
179 0
180 } else {
181 self.rb_cacheval >> count
182 };
183 self.rb_cachelen = self.rb_cachelen.wrapping_sub(count);
184 self.total_bits += count;
185 value
186 }
187
188 pub fn dec_uint(&mut self, size: u32) -> u32 {
189 let bits = ilog(size - 1);
190 let total = if bits > 8 {
191 ((size - 1) >> (bits - 8)) + 1
192 } else {
193 size
194 };
195 let scale = self.range / total;
196 let k = self.value / scale + 1;
197 let k = total - k.min(total);
198 self.update(scale, k, k + 1, total);
199 if bits > 8 {
200 let k = k << (bits - 8) | self.get_raw(bits - 8);
201 k.min(size - 1)
202 } else {
203 k
204 }
205 }
206
207 pub fn dec_uint_step(&mut self, k0: u32) -> u32 {
208 let total = (k0 + 1) * 3 + k0;
209 let scale = self.range / total;
210 let symbol = self.value / scale + 1;
211 let symbol = total - symbol.min(total);
212 let k = if symbol < (k0 + 1) * 3 {
213 symbol / 3
214 } else {
215 symbol - (k0 + 1) * 2
216 };
217 let (lo, hi) = if k <= k0 {
218 (3 * k, 3 * (k + 1))
219 } else {
220 ((k - 1 - k0) + 3 * (k0 + 1), (k - k0) + 3 * (k0 + 1))
221 };
222 self.update(scale, lo, hi, total);
223 k
224 }
225
226 pub fn dec_uint_tri(&mut self, qn: u32) -> u32 {
227 let total = ((qn >> 1) + 1) * ((qn >> 1) + 1);
228 let scale = self.range / total;
229 let center = self.value / scale + 1;
230 let center = total - center.min(total);
231 let (k, low, symbol);
232 if center < total >> 1 {
233 k = (ff_sqrt(8 * center + 1) - 1) >> 1;
234 low = (k * (k + 1)) >> 1;
235 symbol = k + 1;
236 } else {
237 k = (2 * (qn + 1) - ff_sqrt(8 * (total - center - 1) + 1)) >> 1;
238 low = total - (((qn + 1 - k) * (qn + 2 - k)) >> 1);
239 symbol = qn + 1 - k;
240 }
241 self.update(scale, low, low + symbol, total);
242 k
243 }
244
245 pub fn dec_laplace(&mut self, symbol: u32, decay: i32) -> i32 {
246 let mut symbol = symbol;
247 let mut value: i32 = 0;
248 let mut low = 0u32;
249 let scale = self.range >> 15;
250 let center = self.value / scale + 1;
251 let center = (1u32 << 15) - center.min(1 << 15);
252 if center >= symbol {
253 value += 1;
254 low = symbol;
255 symbol = 1 + (((32768 - 32 - symbol) as i32 * (16384 - decay)) >> 15) as u32;
256 while symbol > 1 && center >= low + 2 * symbol {
257 value += 1;
258 symbol *= 2;
259 low += symbol;
260 symbol = ((((symbol - 2) as i32) * decay) >> 15) as u32 + 1;
261 }
262 if symbol <= 1 {
263 let distance = (center - low) >> 1;
264 value += distance as i32;
265 low += 2 * distance;
266 }
267 if center < low + symbol {
268 value = -value;
269 } else {
270 low += symbol;
271 }
272 }
273 self.update(scale, low, (low + symbol).min(32768), 32768);
274 value
275 }
276}
277
278pub fn ff_sqrt(a: u32) -> u32 {
280 let mut r = (a as f64).sqrt() as u32;
281 while r * r > a {
282 r -= 1;
283 }
284 while (r + 1) * (r + 1) <= a {
285 r += 1;
286 }
287 r
288}