| 1 | //! Some universal integer codes support for bitstream reader. |
| 2 | use crate::io::bitreader::{BitReader, BitReaderError, BitReaderResult}; |
| 3 | use crate::io::bitwriter::BitWriter; |
| 4 | |
| 5 | /// Unsigned integer code types. |
| 6 | #[derive(Debug)] |
| 7 | pub enum UintCodeType { |
| 8 | /// Code where number is represented as run of ones with terminating zero. |
| 9 | UnaryOnes, |
| 10 | /// Code where number is represented as run of zeroes with terminating one. |
| 11 | UnaryZeroes, |
| 12 | /// Code for 0, 1 and 2 coded as `0`, `10` and `11` |
| 13 | Unary012, |
| 14 | /// Code for 0, 1 and 2 coded as `11`, `10` and `0` |
| 15 | Unary210, |
| 16 | /// General limited unary code with defined run and terminating bit. |
| 17 | LimitedUnary(u32, u32), |
| 18 | /// Limited run of zeroes with terminating one (unless the code has maximum length). |
| 19 | /// |
| 20 | /// [`Unary012`] is essentially an alias for `LimitedZeroes(2)`. |
| 21 | /// |
| 22 | /// [`Unary012`]: #variant.Unary012 |
| 23 | LimitedZeroes(u32), |
| 24 | /// Limited run of one with terminating zero (unless the code has maximum length). |
| 25 | LimitedOnes(u32), |
| 26 | /// Golomb code. |
| 27 | Golomb(u8), |
| 28 | /// Rice code. |
| 29 | Rice(u8), |
| 30 | /// Elias Gamma code (interleaved). |
| 31 | Gamma, |
| 32 | /// Elias Gamma' code (sometimes incorrectly called exp-Golomb). |
| 33 | GammaP, |
| 34 | } |
| 35 | |
| 36 | /// Signed integer code types. |
| 37 | pub enum IntCodeType { |
| 38 | /// Golomb code. Last bit represents the sign. |
| 39 | Golomb(u8), |
| 40 | /// Golomb code. Last bit represents the sign. |
| 41 | Rice(u8), |
| 42 | /// Elias Gamma code. Unsigned values are remapped as 0, 1, -1, 2, -2, ... |
| 43 | Gamma, |
| 44 | /// Elias Gamma' code. Unsigned values are remapped as 0, 1, -1, 2, -2, ... |
| 45 | GammaP, |
| 46 | } |
| 47 | |
| 48 | /// Universal integer code reader trait for bitstream reader. |
| 49 | /// |
| 50 | /// # Examples |
| 51 | /// |
| 52 | /// Read an unsigned Golomb code: |
| 53 | /// ```` |
| 54 | /// use nihav_core::io::bitreader::*; |
| 55 | /// use nihav_core::io::intcode::{IntCodeReader,UintCodeType}; |
| 56 | /// |
| 57 | /// # fn foo() -> BitReaderResult<()> { |
| 58 | /// let mem: [u8; 4] = [ 0, 1, 2, 3]; |
| 59 | /// let mut br = BitReader::new(&mem, BitReaderMode::BE); |
| 60 | /// let val = br.read_code(UintCodeType::Golomb(3))?; |
| 61 | /// # Ok(()) |
| 62 | /// # } |
| 63 | /// ```` |
| 64 | /// |
| 65 | /// Read signed Elias code: |
| 66 | /// ```` |
| 67 | /// use nihav_core::io::bitreader::*; |
| 68 | /// use nihav_core::io::intcode::{IntCodeReader,IntCodeType}; |
| 69 | /// |
| 70 | /// # fn foo() -> BitReaderResult<()> { |
| 71 | /// let mem: [u8; 4] = [ 0, 1, 2, 3]; |
| 72 | /// let mut br = BitReader::new(&mem, BitReaderMode::BE); |
| 73 | /// let val = br.read_code_signed(IntCodeType::Gamma)?; |
| 74 | /// # Ok(()) |
| 75 | /// # } |
| 76 | /// ```` |
| 77 | pub trait IntCodeReader { |
| 78 | /// Reads an unsigned integer code of requested type. |
| 79 | fn read_code(&mut self, t: UintCodeType) -> BitReaderResult<u32>; |
| 80 | /// Reads signed integer code of requested type. |
| 81 | fn read_code_signed(&mut self, t: IntCodeType) -> BitReaderResult<i32>; |
| 82 | } |
| 83 | |
| 84 | fn read_unary(br: &mut BitReader, terminator: u32) -> BitReaderResult<u32> { |
| 85 | let mut res: u32 = 0; |
| 86 | loop { |
| 87 | if br.read(1)? == terminator { return Ok(res); } |
| 88 | res += 1; |
| 89 | } |
| 90 | } |
| 91 | |
| 92 | fn read_unary_lim(br: &mut BitReader, len: u32, terminator: u32) -> BitReaderResult<u32> { |
| 93 | let mut res: u32 = 0; |
| 94 | loop { |
| 95 | if br.read(1)? == terminator { return Ok(res); } |
| 96 | res += 1; |
| 97 | if res == len { return Ok(res); } |
| 98 | } |
| 99 | } |
| 100 | |
| 101 | fn read_unary210(br: &mut BitReader) -> BitReaderResult<u32> { |
| 102 | let val = read_unary_lim(br, 2, 0)?; |
| 103 | Ok(2 - val) |
| 104 | } |
| 105 | |
| 106 | fn read_golomb(br: &mut BitReader, m: u8) -> BitReaderResult<u32> { |
| 107 | if m == 0 { return Err(BitReaderError::InvalidValue); } |
| 108 | let nbits = (8 - m.leading_zeros()) as u8; |
| 109 | if (m & (m - 1)) == 0 { return read_rice(br, nbits); } |
| 110 | let cutoff = u32::from((1 << nbits) - m); |
| 111 | let pfx = read_unary(br, 0)?; |
| 112 | let tail = br.read(nbits - 1)?; |
| 113 | if tail < cutoff { |
| 114 | let res = pfx * u32::from(m) + tail; |
| 115 | Ok (res) |
| 116 | } else { |
| 117 | let add = br.read(1)?; |
| 118 | let res = pfx * u32::from(m) + (tail - cutoff) * 2 + add + cutoff; |
| 119 | Ok (res) |
| 120 | } |
| 121 | } |
| 122 | |
| 123 | fn read_rice(br: &mut BitReader, k: u8) -> BitReaderResult<u32> { |
| 124 | let pfx = read_unary(br, 1)?; |
| 125 | let ret = (pfx << k) + br.read(k)?; |
| 126 | Ok(ret) |
| 127 | } |
| 128 | |
| 129 | fn read_gamma(br: &mut BitReader) -> BitReaderResult<u32> { |
| 130 | let mut ret = 1; |
| 131 | while br.read(1)? != 1 { |
| 132 | ret = (ret << 1) | br.read(1)?; |
| 133 | } |
| 134 | Ok(ret - 1) |
| 135 | } |
| 136 | |
| 137 | fn read_gammap(br: &mut BitReader) -> BitReaderResult<u32> { |
| 138 | let pfx = read_unary(br, 1)?; |
| 139 | if pfx > 32 { return Err(BitReaderError::InvalidValue); } |
| 140 | let ret = (1 << pfx) + br.read(pfx as u8)?; |
| 141 | Ok(ret) |
| 142 | } |
| 143 | |
| 144 | fn uval_to_sval0mp(uval: u32) -> i32 { |
| 145 | if (uval & 1) != 0 { -(((uval + 1) >> 1) as i32) } |
| 146 | else { (uval >> 1) as i32 } |
| 147 | } |
| 148 | |
| 149 | fn uval_to_sval0pm(uval: u32) -> i32 { |
| 150 | if (uval & 1) != 0 { ((uval + 1) >> 1) as i32 } |
| 151 | else { -((uval >> 1) as i32) } |
| 152 | } |
| 153 | |
| 154 | impl<'a> IntCodeReader for BitReader<'a> { |
| 155 | #[inline(always)] |
| 156 | fn read_code(&mut self, t: UintCodeType) -> BitReaderResult<u32> { |
| 157 | match t { |
| 158 | UintCodeType::UnaryOnes => read_unary(self, 0), |
| 159 | UintCodeType::UnaryZeroes => read_unary(self, 1), |
| 160 | UintCodeType::LimitedZeroes(len) => read_unary_lim(self, len, 1), |
| 161 | UintCodeType::LimitedOnes(len) => read_unary_lim(self, len, 0), |
| 162 | UintCodeType::LimitedUnary(len, term) => read_unary_lim(self, len, term), |
| 163 | UintCodeType::Unary012 => read_unary_lim(self, 2, 0), |
| 164 | UintCodeType::Unary210 => read_unary210(self), |
| 165 | UintCodeType::Golomb(m) => read_golomb(self, m), |
| 166 | UintCodeType::Rice(k) => read_rice(self, k), |
| 167 | UintCodeType::Gamma => read_gamma(self), |
| 168 | UintCodeType::GammaP => read_gammap(self), |
| 169 | } |
| 170 | } |
| 171 | #[allow(unused_variables)] |
| 172 | fn read_code_signed(&mut self, t: IntCodeType) -> BitReaderResult<i32> { |
| 173 | let uval = |
| 174 | match t { |
| 175 | IntCodeType::Golomb(m) => read_golomb(self, m)?, |
| 176 | IntCodeType::Rice(k) => read_rice(self, k)?, |
| 177 | IntCodeType::Gamma => read_gamma(self)?, |
| 178 | IntCodeType::GammaP => read_gammap(self)?, |
| 179 | }; |
| 180 | match t { |
| 181 | IntCodeType::Golomb(m) => Ok(uval_to_sval0mp(uval)), |
| 182 | IntCodeType::Rice(k) => Ok(uval_to_sval0mp(uval)), |
| 183 | IntCodeType::Gamma => Ok(uval_to_sval0pm(uval)), |
| 184 | IntCodeType::GammaP => Ok(uval_to_sval0pm(uval)), |
| 185 | } |
| 186 | } |
| 187 | } |
| 188 | |
| 189 | /// Universal integer code writer trait for bitstream writer. |
| 190 | /// |
| 191 | /// # Examples |
| 192 | /// |
| 193 | /// Write an unsigned Golomb code: |
| 194 | /// ```` |
| 195 | /// use nihav_core::io::bitwriter::*; |
| 196 | /// use nihav_core::io::intcode::{IntCodeWriter,UintCodeType}; |
| 197 | /// |
| 198 | /// let mut bw = BitWriter::new(Vec::new(), BitWriterMode::BE); |
| 199 | /// bw.write_code(UintCodeType::Golomb(3), 42); |
| 200 | /// ```` |
| 201 | /// |
| 202 | /// Write signed Elias code: |
| 203 | /// ```` |
| 204 | /// use nihav_core::io::bitwriter::*; |
| 205 | /// use nihav_core::io::intcode::{IntCodeWriter,IntCodeType}; |
| 206 | /// |
| 207 | /// let mut bw = BitWriter::new(Vec::new(), BitWriterMode::BE); |
| 208 | /// bw.write_code_signed(IntCodeType::Gamma, 42); |
| 209 | /// ```` |
| 210 | pub trait IntCodeWriter { |
| 211 | /// Writes an unsigned integer code of requested type. |
| 212 | fn write_code(&mut self, t: UintCodeType, val: u32); |
| 213 | /// Writes signed integer code of requested type. |
| 214 | fn write_code_signed(&mut self, t: IntCodeType, val: i32); |
| 215 | } |
| 216 | |
| 217 | impl IntCodeWriter for BitWriter { |
| 218 | #[inline(always)] |
| 219 | fn write_code(&mut self, t: UintCodeType, val: u32) { |
| 220 | match t { |
| 221 | UintCodeType::UnaryOnes => write_unary(self, val, 0), |
| 222 | UintCodeType::UnaryZeroes => write_unary(self, val, 1), |
| 223 | UintCodeType::LimitedZeroes(len) => write_unary_lim(self, val, len, 1), |
| 224 | UintCodeType::LimitedOnes(len) => write_unary_lim(self, val, len, 0), |
| 225 | UintCodeType::LimitedUnary(len, term) => write_unary_lim(self, val, len, term), |
| 226 | UintCodeType::Unary012 => write_unary_lim(self, val, 2, 0), |
| 227 | UintCodeType::Unary210 => write_unary210(self, val), |
| 228 | UintCodeType::Golomb(m) => write_golomb(self, val, m), |
| 229 | UintCodeType::Rice(k) => write_rice(self, val, k), |
| 230 | UintCodeType::Gamma => write_gamma(self, val), |
| 231 | UintCodeType::GammaP => write_gammap(self, val), |
| 232 | }; |
| 233 | } |
| 234 | fn write_code_signed(&mut self, t: IntCodeType, val: i32) { |
| 235 | match t { |
| 236 | IntCodeType::Golomb(m) => write_golomb(self, sval0mp_to_uval(val), m), |
| 237 | IntCodeType::Rice(k) => write_rice(self, sval0mp_to_uval(val), k), |
| 238 | IntCodeType::Gamma => write_gamma(self, sval0pm_to_uval(val)), |
| 239 | IntCodeType::GammaP => write_gammap(self, sval0pm_to_uval(val)), |
| 240 | }; |
| 241 | } |
| 242 | } |
| 243 | |
| 244 | fn sval0mp_to_uval(val: i32) -> u32 { |
| 245 | if val < 0 { (-val as u32) * 2 - 1 } |
| 246 | else { (val as u32) * 2 } |
| 247 | } |
| 248 | |
| 249 | fn sval0pm_to_uval(val: i32) -> u32 { |
| 250 | if val >= 0 { (val as u32) * 2 + 1 } |
| 251 | else { (-val as u32) * 2 } |
| 252 | } |
| 253 | |
| 254 | fn write_unary210(bw: &mut BitWriter, val: u32) { |
| 255 | bw.write_bit(val == 0); |
| 256 | if val != 0 { |
| 257 | bw.write_bit(val == 1); |
| 258 | } |
| 259 | } |
| 260 | |
| 261 | fn write_unary(bw: &mut BitWriter, val: u32, term: u32) { |
| 262 | let term = term != 0; |
| 263 | for _ in 0..val { |
| 264 | bw.write_bit(!term); |
| 265 | } |
| 266 | bw.write_bit(term); |
| 267 | } |
| 268 | |
| 269 | fn write_unary_lim(bw: &mut BitWriter, val: u32, maxval: u32, term: u32) { |
| 270 | let term = term != 0; |
| 271 | for _ in 0..val { |
| 272 | bw.write_bit(!term); |
| 273 | } |
| 274 | if val < maxval { |
| 275 | bw.write_bit(term); |
| 276 | } |
| 277 | } |
| 278 | |
| 279 | fn write_rice(bw: &mut BitWriter, val: u32, k: u8) { |
| 280 | let mut exp = val >> k; |
| 281 | while exp >= 16 { |
| 282 | bw.write(0, 16); |
| 283 | exp -= 16 |
| 284 | } |
| 285 | if exp > 0 { |
| 286 | bw.write(0, exp as u8); |
| 287 | } |
| 288 | bw.write1(); |
| 289 | if k > 0 { |
| 290 | let mant = val & ((1 << k) - 1); |
| 291 | bw.write(mant, k); |
| 292 | } |
| 293 | } |
| 294 | |
| 295 | fn write_golomb(bw: &mut BitWriter, val: u32, m: u8) { |
| 296 | if m == 0 { return; } |
| 297 | let nbits = (8 - m.leading_zeros()) as u8; |
| 298 | if (m & (m - 1)) == 0 { return write_rice(bw, val, nbits); } |
| 299 | let q = val / u32::from(m); |
| 300 | let r = val % u32::from(m); |
| 301 | let cutoff = u32::from((1 << nbits) - m); |
| 302 | |
| 303 | write_unary(bw, q, 0); |
| 304 | if r < cutoff { |
| 305 | bw.write(r, nbits - 1); |
| 306 | } else { |
| 307 | bw.write(r + cutoff, nbits); |
| 308 | } |
| 309 | } |
| 310 | |
| 311 | fn write_gamma(bw: &mut BitWriter, val: u32) { |
| 312 | let val = val + 1; |
| 313 | let bits = (32 - val.leading_zeros()) as u8; |
| 314 | let mut mask = 1 << bits >> 2; |
| 315 | while mask != 0 { |
| 316 | bw.write0(); |
| 317 | bw.write_bit((val & mask) != 0); |
| 318 | mask >>= 1; |
| 319 | } |
| 320 | bw.write1(); |
| 321 | } |
| 322 | |
| 323 | fn write_gammap(bw: &mut BitWriter, val: u32) { |
| 324 | let bits = 31 - val.leading_zeros(); |
| 325 | write_unary(bw, bits, 1); |
| 326 | bw.write(val - (1 << bits), bits as u8); |
| 327 | } |
| 328 | |
| 329 | #[cfg(test)] |
| 330 | mod test { |
| 331 | use super::*; |
| 332 | use crate::io::bitreader::*; |
| 333 | use crate::io::bitwriter::*; |
| 334 | |
| 335 | #[test] |
| 336 | fn int_codes() { |
| 337 | const GDATA: [u8; 6] = [0b000_001_01, 0b0_0110_011, 0b1_1000_100, 0b1_1010_101, 0b10_10111_1, 0b1000_0000]; |
| 338 | let src = &GDATA; |
| 339 | let mut br = BitReader::new(src, BitReaderMode::BE); |
| 340 | for i in 0..11 { |
| 341 | assert_eq!(br.read_code(UintCodeType::Golomb(5)).unwrap(), i); |
| 342 | } |
| 343 | } |
| 344 | #[test] |
| 345 | fn rw_codes() { |
| 346 | let mut bw = BitWriter::new(Vec::new(), BitWriterMode::BE); |
| 347 | bw.write_code(UintCodeType::Golomb(5), 42); |
| 348 | bw.write_code(UintCodeType::Gamma, 42); |
| 349 | bw.write_code(UintCodeType::GammaP, 42); |
| 350 | let data = bw.end(); |
| 351 | |
| 352 | let mut br = BitReader::new(&data, BitReaderMode::BE); |
| 353 | assert_eq!(br.read_code(UintCodeType::Golomb(5)).unwrap(), 42); |
| 354 | assert_eq!(br.read_code(UintCodeType::Gamma).unwrap(), 42); |
| 355 | assert_eq!(br.read_code(UintCodeType::GammaP).unwrap(), 42); |
| 356 | } |
| 357 | } |