nihav-core/src/io/intcode.rs

   1 //! Some universal integer codes support for bitstream reader.
   2 use crate::io::bitreader::{BitReader, BitReaderError, BitReaderResult};
   3
   4 /// Unsigned integer code types.
   5 #[derive(Debug)]
   6 pub enum UintCodeType {
   7     /// Code where number is represented as run of ones with terminating zero.
   8     UnaryOnes,
   9     /// Code where number is represented as run of zeroes with terminating one.
  10     UnaryZeroes,
  11     /// Code for 0, 1 and 2 coded as `0`, `10` and `11`
  12     Unary012,
  13     /// Code for 0, 1 and 2 coded as `11`, `10` and `0`
  14     Unary210,
  15     /// General limited unary code with defined run and terminating bit.
  16     LimitedUnary(u32, u32),
  17     /// Limited run of zeroes with terminating one (unless the code has maximum length).
  18     ///
  19     /// [`Unary012`] is essentially an alias for `LimitedZeroes(2)`.
  20     ///
  21     /// [`Unary012`]: #variant.Unary012
  22     LimitedZeroes(u32),
  23     /// Limited run of one with terminating zero (unless the code has maximum length).
  24     LimitedOnes(u32),
  25     /// Golomb code.
  26     Golomb(u8),
  27     /// Rice code.
  28     Rice(u8),
  29     /// Elias Gamma code (interleaved).
  30     Gamma,
  31     /// Elias Gamma' code (sometimes incorrectly called exp-Golomb).
  32     GammaP,
  33 }
  34
  35 /// Signed integer code types.
  36 pub enum IntCodeType {
  37     /// Golomb code. Last bit represents the sign.
  38     Golomb(u8),
  39     /// Golomb code. Last bit represents the sign.
  40     Rice(u8),
  41     /// Elias Gamma code. Unsigned values are remapped as 0, 1, -1, 2, -2, ...
  42     Gamma,
  43     /// Elias Gamma' code. Unsigned values are remapped as 0, 1, -1, 2, -2, ...
  44     GammaP,
  45 }
  46
  47 /// Universal integer code reader trait for bitstream reader.
  48 ///
  49 /// # Examples
  50 ///
  51 /// Read an unsigned Golomb code:
  52 /// ````
  53 /// use nihav_core::io::bitreader::*;
  54 /// use nihav_core::io::intcode::{IntCodeReader,UintCodeType};
  55 ///
  56 /// # fn foo() -> BitReaderResult<()> {
  57 /// let mem: [u8; 4] = [ 0, 1, 2, 3];
  58 /// let mut br = BitReader::new(&mem, BitReaderMode::BE);
  59 /// let val = br.read_code(UintCodeType::Golomb(3))?;
  60 /// # Ok(())
  61 /// # }
  62 /// ````
  63 ///
  64 /// Read signed Elias code:
  65 /// ````
  66 /// use nihav_core::io::bitreader::*;
  67 /// use nihav_core::io::intcode::{IntCodeReader,IntCodeType};
  68 ///
  69 /// # fn foo() -> BitReaderResult<()> {
  70 /// let mem: [u8; 4] = [ 0, 1, 2, 3];
  71 /// let mut br = BitReader::new(&mem, BitReaderMode::BE);
  72 /// let val = br.read_code_signed(IntCodeType::Gamma)?;
  73 /// # Ok(())
  74 /// # }
  75 /// ````
  76 pub trait IntCodeReader {
  77     /// Reads an unsigned integer code of requested type.
  78     fn read_code(&mut self, t: UintCodeType) -> BitReaderResult<u32>;
  79     /// Reads signed integer code of requested type.
  80     fn read_code_signed(&mut self, t: IntCodeType) -> BitReaderResult<i32>;
  81 }
  82
  83 fn read_unary(br: &mut BitReader, terminator: u32) -> BitReaderResult<u32> {
  84     let mut res: u32 = 0;
  85     loop {
  86         if br.read(1)? == terminator { return Ok(res); }
  87         res += 1;
  88     }
  89 }
  90
  91 fn read_unary_lim(br: &mut BitReader, len: u32, terminator: u32) -> BitReaderResult<u32> {
  92     let mut res: u32 = 0;
  93     loop {
  94         if br.read(1)? == terminator { return Ok(res); }
  95         res += 1;
  96         if res == len { return Ok(res); }
  97     }
  98 }
  99
 100 fn read_unary210(br: &mut BitReader) -> BitReaderResult<u32> {
 101     let val = read_unary_lim(br, 2, 0)?;
 102     Ok(2 - val)
 103 }
 104
 105 fn read_golomb(br: &mut BitReader, m: u8) -> BitReaderResult<u32> {
 106     if m == 0 { return Err(BitReaderError::InvalidValue); }
 107     let nbits = (8 - m.leading_zeros()) as u8;
 108     if (m & (m - 1)) == 0 { return read_rice(br, nbits); }
 109     let cutoff = u32::from((1 << nbits) - m);
 110     let pfx = read_unary(br, 0)?;
 111     let tail = br.read(nbits - 1)?;
 112     if tail < cutoff {
 113         let res = pfx * u32::from(m) + tail;
 114         Ok (res)
 115     } else {
 116         let add = br.read(1)?;
 117         let res = pfx * u32::from(m) + (tail - cutoff) * 2 + add + cutoff;
 118         Ok (res)
 119     }
 120 }
 121
 122 fn read_rice(br: &mut BitReader, k: u8) -> BitReaderResult<u32> {
 123     let pfx = read_unary(br, 1)?;
 124     let ret = (pfx << k) + br.read(k)?;
 125     Ok(ret)
 126 }
 127
 128 fn read_gamma(br: &mut BitReader) -> BitReaderResult<u32> {
 129     let mut ret = 1;
 130     while br.read(1)? != 1 {
 131         ret = (ret << 1) | br.read(1)?;
 132     }
 133     Ok(ret - 1)
 134 }
 135
 136 fn read_gammap(br: &mut BitReader) -> BitReaderResult<u32> {
 137     let pfx = read_unary(br, 1)?;
 138     if pfx > 32 { return Err(BitReaderError::InvalidValue); }
 139     let ret = (1 << pfx) + br.read(pfx as u8)?;
 140     Ok(ret)
 141 }
 142
 143 fn uval_to_sval0mp(uval: u32) -> i32 {
 144     if (uval & 1) != 0 { -((uval >> 1) as i32) }
 145     else               { (uval >> 1) as i32 }
 146 }
 147
 148 fn uval_to_sval0pm(uval: u32) -> i32 {
 149     if (uval & 1) != 0 { ((uval + 1) >> 1) as i32 }
 150     else               { -((uval >> 1) as i32) }
 151 }
 152
 153 impl<'a> IntCodeReader for BitReader<'a> {
 154     #[inline(always)]
 155     fn read_code(&mut self, t: UintCodeType) -> BitReaderResult<u32> {
 156         match t {
 157             UintCodeType::UnaryOnes               => read_unary(self, 0),
 158             UintCodeType::UnaryZeroes             => read_unary(self, 1),
 159             UintCodeType::LimitedZeroes(len)      => read_unary_lim(self, len, 1),
 160             UintCodeType::LimitedOnes(len)        => read_unary_lim(self, len, 0),
 161             UintCodeType::LimitedUnary(len, term) => read_unary_lim(self, len, term),
 162             UintCodeType::Unary012                => read_unary_lim(self, 2, 0),
 163             UintCodeType::Unary210                => read_unary210(self),
 164             UintCodeType::Golomb(m)               => read_golomb(self, m),
 165             UintCodeType::Rice(k)                 => read_rice(self, k),
 166             UintCodeType::Gamma                   => read_gamma(self),
 167             UintCodeType::GammaP                  => read_gammap(self),
 168         }
 169     }
 170     #[allow(unused_variables)]
 171     fn read_code_signed(&mut self, t: IntCodeType) -> BitReaderResult<i32> {
 172         let uval =
 173             match t {
 174                 IntCodeType::Golomb(m)               => read_golomb(self, m)?,
 175                 IntCodeType::Rice(k)                 => read_rice(self, k)?,
 176                 IntCodeType::Gamma                   => read_gamma(self)?,
 177                 IntCodeType::GammaP                  => read_gammap(self)?,
 178             };
 179         match t {
 180             IntCodeType::Golomb(m)               => Ok(uval_to_sval0mp(uval)),
 181             IntCodeType::Rice(k)                 => Ok(uval_to_sval0mp(uval)),
 182             IntCodeType::Gamma                   => Ok(uval_to_sval0pm(uval)),
 183             IntCodeType::GammaP                  => Ok(uval_to_sval0pm(uval)),
 184         }
 185     }
 186 }
 187
 188 #[cfg(test)]
 189 mod test {
 190     use super::*;
 191     use crate::io::bitreader::*;
 192
 193     #[test]
 194     fn int_codes() {
 195         const GDATA: [u8; 6] = [0b000_001_01, 0b0_0110_011, 0b1_1000_100, 0b1_1010_101, 0b10_10111_1, 0b1000_0000];
 196         let src = &GDATA;
 197         let mut br = BitReader::new(src, BitReaderMode::BE);
 198         for i in 0..11 {
 199             assert_eq!(br.read_code(UintCodeType::Golomb(5)).unwrap(), i);
 200         }
 201     }
 202 }