1 // Copyright 2022 The ChromiumOS Authors 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 //! A VP8 boolean decoder based on the implementation in Chromium and GStreamer. 6 7 use std::convert::TryFrom; 8 use std::io::Cursor; 9 10 use anyhow::anyhow; 11 use anyhow::Result; 12 use bytes::Buf; 13 14 const LOTS_OF_BITS: u32 = 0x40000000; 15 const U8_BITS: usize = u8::BITS as usize; 16 const BD_VALUE_SIZE: usize = std::mem::size_of::<usize>() * U8_BITS; 17 18 const NORM: [u8; 256] = [ 19 0, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 20 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 21 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 22 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 24 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 25 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 26 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 27 ]; 28 29 /// Some bits are "encoded" with a 50/50 probability. 30 const DEFAULT_PROBABILITY: u8 = 128; 31 32 /// The decoder state. 33 #[derive(Default)] 34 pub struct BoolDecoder<T> { 35 data: Cursor<T>, 36 range: usize, 37 value: usize, 38 count: isize, 39 } 40 41 impl<T: AsRef<[u8]>> BoolDecoder<T> { 42 /// Creates a new instance. new(data: T) -> Self43 pub fn new(data: T) -> Self { 44 Self { 45 data: Cursor::new(data), 46 range: 255usize, 47 value: 0usize, 48 count: -8, 49 } 50 } 51 52 /// Fills more bits from `data` to `value`. We shall keep at least 8 bits of 53 /// the current `data` in `value`. fill(&mut self) -> Result<()>54 fn fill(&mut self) -> Result<()> { 55 let mut shift = 56 (BD_VALUE_SIZE as isize - U8_BITS as isize - (self.count + U8_BITS as isize)) as i32; 57 let bits_left = (self.data.remaining() * U8_BITS) as i32; 58 let x = shift + U8_BITS as i32 - bits_left; 59 let mut loop_end = 0; 60 61 if x >= 0 { 62 self.count += LOTS_OF_BITS as isize; 63 loop_end = x; 64 } 65 66 if x < 0 || bits_left != 0 { 67 while shift >= loop_end { 68 self.count += U8_BITS as isize; 69 self.value |= (self.data.get_u8() as usize) << shift; 70 shift -= U8_BITS as i32; 71 } 72 Ok(()) 73 } else { 74 Err(anyhow!("Out of bits")) 75 } 76 } 77 78 /// Reads the next bit from the coded stream. The probability of the bit to 79 /// be one is probability / 256. read_bit(&mut self, probability: u8) -> Result<bool>80 fn read_bit(&mut self, probability: u8) -> Result<bool> { 81 let split = 1 + (((self.range - 1) * probability as usize) >> 8); 82 83 if self.count < 0 { 84 self.fill()?; 85 } 86 87 let bigsplit = split << (BD_VALUE_SIZE - U8_BITS); 88 89 let bit = if self.value >= bigsplit { 90 self.range -= split; 91 self.value -= bigsplit; 92 true 93 } else { 94 self.range = split; 95 false 96 }; 97 98 let shift = NORM[self.range]; 99 self.range <<= shift; 100 self.value <<= shift; 101 self.count -= isize::from(shift); 102 103 Ok(bit) 104 } 105 106 /// Reads a "literal", that is, a "num_bits"-wide unsigned value whose bits 107 /// come high- to low-order, with each bit encoded at probability 1/2. read_literal(&mut self, mut nbits: usize) -> Result<i32>108 fn read_literal(&mut self, mut nbits: usize) -> Result<i32> { 109 let mut ret = 0; 110 111 while nbits > 0 { 112 let bit = self.read_bit(DEFAULT_PROBABILITY)?; 113 ret = (ret << 1) | bit as i32; 114 nbits -= 1; 115 } 116 117 Ok(ret) 118 } 119 120 /// Reads a boolean from the coded stream. Returns false if it has reached the 121 /// end of data and failed to read the boolean. The probability of out to 122 /// be true is probability / 256, e.g., when probability is 0x80, the 123 /// chance is 1/2 (i.e., 0x80 / 256). read_bool(&mut self) -> Result<bool>124 pub fn read_bool(&mut self) -> Result<bool> { 125 self.read_literal(1).map(|bit| bit != 0) 126 } 127 128 /// Reads a boolean from the coded stream. Returns false if it has reached the 129 /// end of data and failed to read the boolean. The probability of out to 130 /// be true is probability / 256, e.g., when probability is 0x80, the 131 /// chance is 1/2 (i.e., 0x80 / 256). read_bool_with_prob(&mut self, probability: u8) -> Result<bool>132 pub fn read_bool_with_prob(&mut self, probability: u8) -> Result<bool> { 133 self.read_bit(probability) 134 } 135 136 /// Reads an unsigned literal from the coded stream. read_uint<U: TryFrom<i32>>(&mut self, nbits: usize) -> Result<U>137 pub fn read_uint<U: TryFrom<i32>>(&mut self, nbits: usize) -> Result<U> { 138 let value = self.read_literal(nbits)?; 139 U::try_from(value).map_err(|_| anyhow!("Conversion failed")) 140 } 141 142 /// Reads a literal with sign from the coded stream. This is similar to the 143 /// read_literal(), it first read a "num_bits"-wide unsigned value, and then 144 /// read an extra bit as the sign of the literal. read_sint<U: TryFrom<i32>>(&mut self, nbits: usize) -> Result<U>145 pub fn read_sint<U: TryFrom<i32>>(&mut self, nbits: usize) -> Result<U> { 146 let mut value = self.read_literal(nbits)?; 147 let sign = self.read_bool()?; 148 149 if sign { 150 value = -value; 151 } 152 153 U::try_from(value).map_err(|_| anyhow!("Conversion failed")) 154 } 155 156 /// Returns the current coded value. value(&self) -> usize157 pub fn value(&self) -> usize { 158 self.value >> (BD_VALUE_SIZE - U8_BITS) 159 } 160 161 /// Returns the number of bytes in the `value` buffer. count(&self) -> isize162 pub fn count(&self) -> isize { 163 (U8_BITS as isize + self.count) % U8_BITS as isize 164 } 165 166 /// Returns the range of the current coded value. range(&self) -> usize167 pub fn range(&self) -> usize { 168 self.range 169 } 170 171 /// Returns the current bit position. pos(&self) -> usize172 pub fn pos(&self) -> usize { 173 let mut bit_count = (self.count + 8) as usize; 174 175 if bit_count > BD_VALUE_SIZE { 176 bit_count = std::cmp::max(0, bit_count - LOTS_OF_BITS as usize); 177 } 178 179 let pos = self.data.position() as usize; 180 pos * U8_BITS - bit_count 181 } 182 } 183 184 #[cfg(test)] 185 mod tests { 186 use super::*; 187 188 const NUM_BITS_TO_TEST: usize = 100; 189 190 /// 100 zeros with probability of 0x80. 191 const DATA_ZEROS_AND_EVEN_PROBABILITIES: [u8; 14] = [ 192 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 193 ]; 194 195 /// 100 ones with probability of 0x80. 196 const DATA_ONES_AND_EVEN_PROBABILITIES: [u8; 14] = [ 197 0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf0, 0x20, 198 ]; 199 200 /// [0, 1, 0, 1, ..., 1] with probability [0, 1, 2, 3, ..., 99]. 201 const DATA_PARITIES_AND_INCREASING_PROBABILITIES: [u8; 21] = [ 202 0x00, 0x02, 0x08, 0x31, 0x8e, 0xca, 0xab, 0xe2, 0xc8, 0x31, 0x12, 0xb3, 0x2c, 0x19, 0x90, 203 0xc6, 0x6a, 0xeb, 0x17, 0x52, 0x30, 204 ]; 205 206 // All tests adapted from: 207 // https://chromium.googlesource.com/chromium/src/+/refs/heads/main/media/parsers/vp8_bool_decoder_unittest.cc 208 209 #[test] decode_bools_with_zeros_and_even_probabilities()210 fn decode_bools_with_zeros_and_even_probabilities() { 211 let mut bd = BoolDecoder::new(&DATA_ZEROS_AND_EVEN_PROBABILITIES[..]); 212 assert!(bd.pos() == 0); 213 214 for i in 0..NUM_BITS_TO_TEST { 215 assert!(!bd.read_bool_with_prob(0x80).unwrap()); 216 assert_eq!(i, bd.pos()); 217 } 218 } 219 220 #[test] decode_literals_with_zeros_and_even_probabilities()221 fn decode_literals_with_zeros_and_even_probabilities() { 222 // Adapted from: 223 // https://chromium.googlesource.com/chromium/src/+/refs/heads/main/media/parsers/vp8_bool_decoder_unittest.cc 224 let mut bd = BoolDecoder::new(&DATA_ZEROS_AND_EVEN_PROBABILITIES[..]); 225 assert!(bd.pos() == 0); 226 227 assert!(bd.read_literal(1).unwrap() == 0); 228 assert!(bd.read_literal(32).unwrap() == 0); 229 assert!(bd.read_sint::<i32>(1).unwrap() == 0); 230 assert!(bd.read_sint::<i32>(31).unwrap() == 0); 231 } 232 233 #[test] decode_bools_with_ones_and_even_probabilities()234 fn decode_bools_with_ones_and_even_probabilities() { 235 let mut bd = BoolDecoder::new(&DATA_ONES_AND_EVEN_PROBABILITIES[..]); 236 assert!(bd.pos() == 0); 237 238 for i in 0..NUM_BITS_TO_TEST { 239 assert!(bd.read_bool_with_prob(0x80).unwrap()); 240 assert_eq!(i + 1, bd.pos()); 241 } 242 } 243 244 #[test] decode_literals_with_ones_and_even_probabilities()245 fn decode_literals_with_ones_and_even_probabilities() { 246 let mut bd = BoolDecoder::new(&DATA_ONES_AND_EVEN_PROBABILITIES[..]); 247 assert!(bd.pos() == 0); 248 249 assert!(bd.read_literal(1).unwrap() == 1); 250 assert!(bd.read_literal(31).unwrap() == 0x7fffffff); 251 assert!(bd.read_sint::<i32>(1).unwrap() == -1); 252 assert!(bd.read_sint::<i32>(31).unwrap() == -0x7fffffff); 253 } 254 255 #[test] decode_bools_with_parities_and_increasing_probabilities()256 fn decode_bools_with_parities_and_increasing_probabilities() { 257 let mut bd = BoolDecoder::new(&DATA_PARITIES_AND_INCREASING_PROBABILITIES[..]); 258 assert!(bd.pos() == 0); 259 260 for i in 0..NUM_BITS_TO_TEST { 261 let bit = bd.read_bool_with_prob(i as u8).unwrap(); 262 263 if i % 2 == 0 { 264 assert!(!bit); 265 } else { 266 assert!(bit); 267 } 268 } 269 } 270 } 271