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::fmt; 9 10 use crate::bitstream_utils::BitReader; 11 12 const LOTS_OF_BITS: u32 = 0x40000000; 13 const U8_BITS: usize = u8::BITS as usize; 14 const BD_VALUE_SIZE: usize = std::mem::size_of::<usize>() * U8_BITS; 15 16 const NORM: [u8; 256] = [ 17 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, 18 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, 19 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, 20 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, 21 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, 22 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, 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 ]; 26 27 /// Some bits are "encoded" with a 50/50 probability. 28 const DEFAULT_PROBABILITY: u8 = 128; 29 30 /// A capture of the state of the boolean decoder. 31 /// 32 /// A `BoolDecoder` can be consumed and turned into this structure, which captures its state. This 33 /// is useful to pass that state to the next decoding step, typically a hardware accelerator. 34 pub struct BoolDecoderState { 35 pub range: usize, 36 pub value: usize, 37 pub count: isize, 38 } 39 40 #[derive(Debug, PartialEq, Eq)] 41 pub enum BoolDecoderError { 42 EndOfInput, 43 CannotConvert, 44 } 45 46 impl fmt::Display for BoolDecoderError { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result47 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 48 match self { 49 BoolDecoderError::EndOfInput => write!(f, "end of input reached"), 50 BoolDecoderError::CannotConvert => { 51 write!(f, "could not convert number of read bits to target type") 52 } 53 } 54 } 55 } 56 57 pub type BoolDecoderResult<T> = std::result::Result<T, BoolDecoderError>; 58 59 /// The decoder state. 60 pub struct BoolDecoder<'a> { 61 data: BitReader<'a>, 62 range: usize, 63 value: usize, 64 count: isize, 65 } 66 67 impl<'a> BoolDecoder<'a> { 68 /// Creates a new instance. new(data: &'a [u8]) -> Self69 pub fn new(data: &'a [u8]) -> Self { 70 Self { 71 data: BitReader::new(data, false), 72 range: 255usize, 73 value: 0usize, 74 count: -(U8_BITS as isize), 75 } 76 } 77 78 /// Fills more bits from `data` to `value`. We shall keep at least 8 bits of the current `data` 79 /// in `value`. 80 /// 81 /// Returns `Some(())` if there was input data to fill from, `None` if we reached the end of 82 /// the input. fill(&mut self) -> Option<()>83 fn fill(&mut self) -> Option<()> { 84 let mut shift = 85 (BD_VALUE_SIZE as isize - U8_BITS as isize - (self.count + U8_BITS as isize)) as i32; 86 let bits_left = self.data.num_bits_left() as i32; 87 let x = shift + U8_BITS as i32 - bits_left; 88 let mut loop_end = 0; 89 90 if x >= 0 { 91 self.count += LOTS_OF_BITS as isize; 92 loop_end = x; 93 } 94 95 if x < 0 || bits_left != 0 { 96 while shift >= loop_end { 97 self.count += U8_BITS as isize; 98 self.value |= self.data.read_bits::<usize>(8).ok()? << shift; 99 shift -= U8_BITS as i32; 100 } 101 Some(()) 102 } else { 103 None 104 } 105 } 106 107 /// Reads the next bit from the coded stream. The probability of the bit to 108 /// be one is probability / 256. read_bit(&mut self, probability: u8) -> BoolDecoderResult<bool>109 fn read_bit(&mut self, probability: u8) -> BoolDecoderResult<bool> { 110 let split = 1 + (((self.range - 1) * probability as usize) >> 8); 111 112 if self.count < 0 { 113 self.fill().ok_or(BoolDecoderError::EndOfInput)?; 114 } 115 116 let bigsplit = split << (BD_VALUE_SIZE - U8_BITS); 117 118 let bit = if self.value >= bigsplit { 119 self.range -= split; 120 self.value -= bigsplit; 121 true 122 } else { 123 self.range = split; 124 false 125 }; 126 127 let shift = NORM[self.range]; 128 self.range <<= shift; 129 self.value <<= shift; 130 self.count -= isize::from(shift); 131 132 Ok(bit) 133 } 134 135 /// Reads a "literal", that is, a "num_bits"-wide unsigned value whose bits 136 /// come high- to low-order, with each bit encoded at probability 1/2. 137 /// 138 /// # Panics 139 /// 140 /// Will panic if `nbits > 31`. read_literal(&mut self, nbits: usize) -> BoolDecoderResult<i32>141 fn read_literal(&mut self, nbits: usize) -> BoolDecoderResult<i32> { 142 // This won't perform well if we read more than 31 bits. 143 assert!(nbits <= 31); 144 145 let mut ret = 0; 146 147 for _ in 0..nbits { 148 ret = (ret << 1) | self.read_bit(DEFAULT_PROBABILITY)? as i32; 149 } 150 151 Ok(ret) 152 } 153 154 /// Reads a boolean from the coded stream. Returns false if it has reached the 155 /// end of data and failed to read the boolean. The probability of out to 156 /// be true is probability / 256, e.g., when probability is 0x80, the 157 /// chance is 1/2 (i.e., 0x80 / 256). read_bool(&mut self) -> BoolDecoderResult<bool>158 pub fn read_bool(&mut self) -> BoolDecoderResult<bool> { 159 self.read_literal(1).map(|bit| bit != 0) 160 } 161 162 /// Reads a boolean from the coded stream. Returns false if it has reached the 163 /// end of data and failed to read the boolean. The probability of out to 164 /// be true is probability / 256, e.g., when probability is 0x80, the 165 /// chance is 1/2 (i.e., 0x80 / 256). read_bool_with_prob(&mut self, probability: u8) -> BoolDecoderResult<bool>166 pub fn read_bool_with_prob(&mut self, probability: u8) -> BoolDecoderResult<bool> { 167 self.read_bit(probability) 168 } 169 170 /// Reads an unsigned literal from the coded stream. 171 /// 172 /// # Panics 173 /// 174 /// Will panic if `nbits > 31`. read_uint<U: TryFrom<i32>>(&mut self, nbits: usize) -> BoolDecoderResult<U>175 pub fn read_uint<U: TryFrom<i32>>(&mut self, nbits: usize) -> BoolDecoderResult<U> { 176 let value = self.read_literal(nbits)?; 177 U::try_from(value).map_err(|_| BoolDecoderError::CannotConvert) 178 } 179 180 /// Reads a literal with sign from the coded stream. This is similar to the 181 /// read_literal(), it first read a "num_bits"-wide unsigned value, and then 182 /// read an extra bit as the sign of the literal. 183 /// 184 /// # Panics 185 /// 186 /// Will panic if `nbits > 31`. read_sint<U: TryFrom<i32>>(&mut self, nbits: usize) -> BoolDecoderResult<U>187 pub fn read_sint<U: TryFrom<i32>>(&mut self, nbits: usize) -> BoolDecoderResult<U> { 188 let mut value = self.read_literal(nbits)?; 189 let sign = self.read_bool()?; 190 191 if sign { 192 value = -value; 193 } 194 195 U::try_from(value).map_err(|_| BoolDecoderError::CannotConvert) 196 } 197 198 /// Returns the current bit position. pos(&self) -> usize199 pub fn pos(&self) -> usize { 200 let mut bit_count = (self.count + 8) as usize; 201 202 if bit_count > BD_VALUE_SIZE { 203 bit_count = bit_count.saturating_sub(LOTS_OF_BITS as usize) 204 } 205 206 let pos = self.data.position() as usize; 207 pos - bit_count 208 } 209 } 210 211 impl From<BoolDecoder<'_>> for BoolDecoderState { from(mut bd: BoolDecoder) -> Self212 fn from(mut bd: BoolDecoder) -> Self { 213 if bd.count < 0 { 214 let _ = bd.fill(); 215 } 216 217 Self { 218 value: bd.value >> (BD_VALUE_SIZE - U8_BITS), 219 count: (U8_BITS as isize + bd.count) % U8_BITS as isize, 220 range: bd.range, 221 } 222 } 223 } 224 225 #[cfg(test)] 226 mod tests { 227 use super::*; 228 229 const NUM_BITS_TO_TEST: usize = 100; 230 231 /// 100 zeros with probability of 0x80. 232 const DATA_ZEROS_AND_EVEN_PROBABILITIES: [u8; 14] = 233 [0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00]; 234 235 /// 100 ones with probability of 0x80. 236 const DATA_ONES_AND_EVEN_PROBABILITIES: [u8; 14] = 237 [0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf0, 0x20]; 238 239 /// [0, 1, 0, 1, ..., 1] with probability [0, 1, 2, 3, ..., 99]. 240 const DATA_PARITIES_AND_INCREASING_PROBABILITIES: [u8; 21] = [ 241 0x00, 0x02, 0x08, 0x31, 0x8e, 0xca, 0xab, 0xe2, 0xc8, 0x31, 0x12, 0xb3, 0x2c, 0x19, 0x90, 242 0xc6, 0x6a, 0xeb, 0x17, 0x52, 0x30, 243 ]; 244 245 // All tests adapted from: 246 // https://chromium.googlesource.com/chromium/src/+/refs/heads/main/media/parsers/vp8_bool_decoder_unittest.cc 247 248 #[test] decode_bools_with_zeros_and_even_probabilities()249 fn decode_bools_with_zeros_and_even_probabilities() { 250 let mut bd = BoolDecoder::new(&DATA_ZEROS_AND_EVEN_PROBABILITIES[..]); 251 assert!(bd.pos() == 0); 252 253 for i in 0..NUM_BITS_TO_TEST { 254 assert_eq!(bd.read_bool_with_prob(0x80), Ok(false)); 255 assert_eq!(i, bd.pos()); 256 } 257 } 258 259 #[test] decode_literals_with_zeros_and_even_probabilities()260 fn decode_literals_with_zeros_and_even_probabilities() { 261 // Adapted from: 262 // https://chromium.googlesource.com/chromium/src/+/refs/heads/main/media/parsers/vp8_bool_decoder_unittest.cc 263 let mut bd = BoolDecoder::new(&DATA_ZEROS_AND_EVEN_PROBABILITIES[..]); 264 assert_eq!(bd.pos(), 0); 265 266 assert_eq!(bd.read_literal(1), Ok(0)); 267 assert_eq!(bd.read_literal(31), Ok(0)); 268 assert_eq!(bd.read_sint::<i32>(1), Ok(0)); 269 assert_eq!(bd.read_sint::<i32>(31), Ok(0)); 270 } 271 272 #[test] decode_bools_with_ones_and_even_probabilities()273 fn decode_bools_with_ones_and_even_probabilities() { 274 let mut bd = BoolDecoder::new(&DATA_ONES_AND_EVEN_PROBABILITIES[..]); 275 assert!(bd.pos() == 0); 276 277 for i in 0..NUM_BITS_TO_TEST { 278 assert_eq!(bd.read_bool_with_prob(0x80), Ok(true)); 279 assert_eq!(i + 1, bd.pos()); 280 } 281 } 282 283 #[test] decode_literals_with_ones_and_even_probabilities()284 fn decode_literals_with_ones_and_even_probabilities() { 285 let mut bd = BoolDecoder::new(&DATA_ONES_AND_EVEN_PROBABILITIES[..]); 286 assert_eq!(bd.pos(), 0); 287 288 assert_eq!(bd.read_literal(1), Ok(1)); 289 assert_eq!(bd.read_literal(31), Ok(0x7fffffff)); 290 assert_eq!(bd.read_sint::<i32>(1), Ok(-1)); 291 assert_eq!(bd.read_sint::<i32>(31), Ok(-0x7fffffff)); 292 } 293 294 #[test] decode_bools_with_parities_and_increasing_probabilities()295 fn decode_bools_with_parities_and_increasing_probabilities() { 296 let mut bd = BoolDecoder::new(&DATA_PARITIES_AND_INCREASING_PROBABILITIES[..]); 297 assert!(bd.pos() == 0); 298 299 for i in 0..NUM_BITS_TO_TEST { 300 let bit = bd.read_bool_with_prob(i as u8).unwrap(); 301 302 if i % 2 == 0 { 303 assert!(!bit); 304 } else { 305 assert!(bit); 306 } 307 } 308 } 309 } 310