nihav-core/src/io/intcode.rs

   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 }