threers_codec/vp9/
bool_coder.rs1pub struct BoolEncoder {
20 out: Vec<u8>,
21 range: u32,
23 bottom: u32,
25 bit_count: i32,
27}
28
29impl Default for BoolEncoder {
30 fn default() -> Self {
31 Self::new()
32 }
33}
34
35impl BoolEncoder {
36 pub fn new() -> Self {
40 let mut e = Self {
41 out: Vec::new(),
42 range: 255,
43 bottom: 0,
44 bit_count: 24,
45 };
46 e.put_bit(false); e
48 }
49
50 fn carry(&mut self) {
55 let mut i = self.out.len();
56 while i > 0 {
57 i -= 1;
58 if self.out[i] == 0xff {
59 self.out[i] = 0;
60 } else {
61 self.out[i] += 1;
62 return;
63 }
64 }
65 self.out.insert(0, 1);
66 }
67
68 #[inline]
71 fn shift(&mut self) {
72 if self.bottom & 0x8000_0000 != 0 {
73 self.carry();
74 }
75 self.bottom <<= 1;
76 self.bit_count -= 1;
77 if self.bit_count == 0 {
78 self.out.push((self.bottom >> 24) as u8);
79 self.bottom &= (1 << 24) - 1;
80 self.bit_count = 8;
81 }
82 }
83
84 pub fn put_bool(&mut self, prob: u8, bit: bool) {
87 let split = 1 + (((self.range - 1) * prob as u32) >> 8);
88 if bit {
89 self.bottom += split;
90 self.range -= split;
91 } else {
92 self.range = split;
93 }
94 while self.range < 128 {
95 self.range <<= 1;
96 self.shift();
97 }
98 }
99
100 pub fn put_bit(&mut self, bit: bool) {
102 self.put_bool(128, bit);
103 }
104
105 pub fn put_literal(&mut self, value: u32, n: u32) {
107 for i in (0..n).rev() {
108 self.put_bit((value >> i) & 1 != 0);
109 }
110 }
111
112 pub fn finish(mut self) -> Vec<u8> {
115 for _ in 0..32 {
116 self.put_bit(false);
117 }
118 self.out
119 }
120
121 pub fn len(&self) -> usize {
123 self.out.len()
124 }
125
126 pub fn is_empty(&self) -> bool {
127 self.out.is_empty()
128 }
129}
130
131#[cfg(test)]
132mod tests {
133 use super::*;
134
135 struct BoolDecoder<'a> {
138 input: &'a [u8],
139 pos: usize,
140 range: u32,
141 value: u32,
142 bit_count: i32,
143 }
144 impl<'a> BoolDecoder<'a> {
145 fn new(input: &'a [u8]) -> Self {
146 let b0 = input.first().copied().unwrap_or(0) as u32;
147 let b1 = input.get(1).copied().unwrap_or(0) as u32;
148 let mut d = Self {
149 input,
150 pos: 2,
151 range: 255,
152 value: (b0 << 8) | b1,
153 bit_count: 0,
154 };
155 assert!(!d.get_bool(128), "bool coder marker bit must be 0");
157 d
158 }
159 fn get_bool(&mut self, prob: u8) -> bool {
160 let split = 1 + (((self.range - 1) * prob as u32) >> 8);
161 let big_split = split << 8;
162 let ret = if self.value >= big_split {
163 self.range -= split;
164 self.value -= big_split;
165 true
166 } else {
167 self.range = split;
168 false
169 };
170 while self.range < 128 {
171 self.value <<= 1;
172 self.range <<= 1;
173 self.bit_count += 1;
174 if self.bit_count == 8 {
175 self.bit_count = 0;
176 let byte = self.input.get(self.pos).copied().unwrap_or(0) as u32;
177 self.pos += 1;
178 self.value |= byte;
179 }
180 }
181 ret
182 }
183 fn get_literal(&mut self, n: u32) -> u32 {
184 let mut v = 0;
185 for _ in 0..n {
186 v = (v << 1) | self.get_bool(128) as u32;
187 }
188 v
189 }
190 }
191
192 struct Rng(u32);
194 impl Rng {
195 fn next(&mut self) -> u32 {
196 let mut x = self.0;
197 x ^= x << 13;
198 x ^= x >> 17;
199 x ^= x << 5;
200 self.0 = x;
201 x
202 }
203 }
204
205 #[test]
206 fn roundtrip_simple() {
207 let script: &[(u8, bool)] = &[
208 (128, true),
209 (128, false),
210 (10, true),
211 (250, false),
212 (200, true),
213 (5, false),
214 ];
215 let mut enc = BoolEncoder::new();
216 for &(p, b) in script {
217 enc.put_bool(p, b);
218 }
219 let bytes = enc.finish();
220 let mut dec = BoolDecoder::new(&bytes);
221 for &(p, b) in script {
222 assert_eq!(dec.get_bool(p), b);
223 }
224 }
225
226 #[test]
227 fn roundtrip_randomized() {
228 for trial in 0..300u32 {
231 let mut rng = Rng(0x9E37_79B9 ^ trial.wrapping_mul(2654435761));
232 let len = 20 + (rng.next() % 500) as usize;
233 let ops: Vec<(u8, bool)> = (0..len)
234 .map(|_| {
235 let p = match rng.next() % 4 {
237 0 => 1,
238 1 => 255,
239 _ => (rng.next() % 256) as u8,
240 };
241 (p.max(1), rng.next() & 1 != 0)
242 })
243 .collect();
244
245 let mut enc = BoolEncoder::new();
246 for &(p, b) in &ops {
247 enc.put_bool(p, b);
248 }
249 let bytes = enc.finish();
250
251 let mut dec = BoolDecoder::new(&bytes);
252 for (i, &(p, b)) in ops.iter().enumerate() {
253 assert_eq!(dec.get_bool(p), b, "trial {trial} bin {i} (prob {p})");
254 }
255 }
256 }
257
258 #[test]
259 fn roundtrip_literals() {
260 let mut rng = Rng(0x1234_5678);
261 let vals: Vec<(u32, u32)> = (0..200)
262 .map(|_| {
263 let n = 1 + rng.next() % 16;
264 (rng.next() & ((1 << n) - 1), n)
265 })
266 .collect();
267 let mut enc = BoolEncoder::new();
268 for &(v, n) in &vals {
269 enc.put_literal(v, n);
270 }
271 let bytes = enc.finish();
272 let mut dec = BoolDecoder::new(&bytes);
273 for &(v, n) in &vals {
274 assert_eq!(dec.get_literal(n), v, "literal {v} ({n} bits)");
275 }
276 }
277
278 #[test]
279 fn roundtrip_all_ones_carry_stress() {
280 let mut enc = BoolEncoder::new();
282 let ops: Vec<(u8, bool)> = (0..2000).map(|i| (1u8, i % 7 != 0)).collect();
283 for &(p, b) in &ops {
284 enc.put_bool(p, b);
285 }
286 let bytes = enc.finish();
287 let mut dec = BoolDecoder::new(&bytes);
288 for &(p, b) in &ops {
289 assert_eq!(dec.get_bool(p), b);
290 }
291 }
292}