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     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(_)               => Ok(uval_to_sval0mp(uval)),
 181             IntCodeType::Rice(_)                 => 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 /// Universal integer code writer trait for bitstream writer.
 189 ///
 190 /// # Examples
 191 ///
 192 /// Write an unsigned Golomb code:
 193 /// ````
 194 /// use nihav_core::io::bitwriter::*;
 195 /// use nihav_core::io::intcode::{IntCodeWriter,UintCodeType};
 196 ///
 197 /// let mut bw = BitWriter::new(Vec::new(), BitWriterMode::BE);
 198 /// bw.write_code(UintCodeType::Golomb(3), 42);
 199 /// ````
 200 ///
 201 /// Write signed Elias code:
 202 /// ````
 203 /// use nihav_core::io::bitwriter::*;
 204 /// use nihav_core::io::intcode::{IntCodeWriter,IntCodeType};
 205 ///
 206 /// let mut bw = BitWriter::new(Vec::new(), BitWriterMode::BE);
 207 /// bw.write_code_signed(IntCodeType::Gamma, 42);
 208 /// ````
 209 pub trait IntCodeWriter {
 210     /// Writes an unsigned integer code of requested type.
 211     fn write_code(&mut self, t: UintCodeType, val: u32);
 212     /// Writes signed integer code of requested type.
 213     fn write_code_signed(&mut self, t: IntCodeType, val: i32);
 214 }
 215
 216 impl IntCodeWriter for BitWriter {
 217     #[inline(always)]
 218     fn write_code(&mut self, t: UintCodeType, val: u32) {
 219         match t {
 220             UintCodeType::UnaryOnes               => write_unary(self, val, 0),
 221             UintCodeType::UnaryZeroes             => write_unary(self, val, 1),
 222             UintCodeType::LimitedZeroes(len)      => write_unary_lim(self, val, len, 1),
 223             UintCodeType::LimitedOnes(len)        => write_unary_lim(self, val, len, 0),
 224             UintCodeType::LimitedUnary(len, term) => write_unary_lim(self, val, len, term),
 225             UintCodeType::Unary012                => write_unary_lim(self, val, 2, 0),
 226             UintCodeType::Unary210                => write_unary210(self, val),
 227             UintCodeType::Golomb(m)               => write_golomb(self, val, m),
 228             UintCodeType::Rice(k)                 => write_rice(self, val, k),
 229             UintCodeType::Gamma                   => write_gamma(self, val),
 230             UintCodeType::GammaP                  => write_gammap(self, val),
 231         };
 232     }
 233     fn write_code_signed(&mut self, t: IntCodeType, val: i32) {
 234         match t {
 235             IntCodeType::Golomb(m)  => write_golomb(self, sval0mp_to_uval(val), m),
 236             IntCodeType::Rice(k)    => write_rice(self, sval0mp_to_uval(val), k),
 237             IntCodeType::Gamma      => write_gamma(self, sval0pm_to_uval(val)),
 238             IntCodeType::GammaP     => write_gammap(self, sval0pm_to_uval(val)),
 239         };
 240     }
 241 }
 242
 243 fn sval0mp_to_uval(val: i32) -> u32 {
 244     if val < 0  { (-val as u32) * 2 - 1 }
 245     else        { (val as u32) * 2 }
 246 }
 247
 248 fn sval0pm_to_uval(val: i32) -> u32 {
 249     if val >= 0 { (val as u32) * 2 + 1 }
 250     else        { (-val as u32) * 2 }
 251 }
 252
 253 fn write_unary210(bw: &mut BitWriter, val: u32) {
 254     bw.write_bit(val == 0);
 255     if val != 0 {
 256         bw.write_bit(val == 1);
 257     }
 258 }
 259
 260 fn write_unary(bw: &mut BitWriter, val: u32, term: u32) {
 261     let term = term != 0;
 262     for _ in 0..val {
 263         bw.write_bit(!term);
 264     }
 265     bw.write_bit(term);
 266 }
 267
 268 fn write_unary_lim(bw: &mut BitWriter, val: u32, maxval: u32, term: u32) {
 269     let term = term != 0;
 270     for _ in 0..val {
 271         bw.write_bit(!term);
 272     }
 273     if val < maxval {
 274         bw.write_bit(term);
 275     }
 276 }
 277
 278 fn write_rice(bw: &mut BitWriter, val: u32, k: u8) {
 279     let mut exp = val >> k;
 280     while exp >= 16 {
 281         bw.write(0, 16);
 282         exp -= 16
 283     }
 284     if exp > 0 {
 285         bw.write(0, exp as u8);
 286     }
 287     bw.write1();
 288     if k > 0 {
 289         let mant = val & ((1 << k) - 1);
 290         bw.write(mant, k);
 291     }
 292 }
 293
 294 fn write_golomb(bw: &mut BitWriter, val: u32, m: u8) {
 295     if m == 0 { return; }
 296     let nbits = (8 - m.leading_zeros()) as u8;
 297     if (m & (m - 1)) == 0 { return write_rice(bw, val, nbits); }
 298     let q = val / u32::from(m);
 299     let r = val % u32::from(m);
 300     let cutoff = u32::from((1 << nbits) - m);
 301
 302     write_unary(bw, q, 0);
 303     if r < cutoff {
 304         bw.write(r, nbits - 1);
 305     } else {
 306         bw.write(r + cutoff, nbits);
 307     }
 308 }
 309
 310 fn write_gamma(bw: &mut BitWriter, val: u32) {
 311     let val = val + 1;
 312     let bits = (32 - val.leading_zeros()) as u8;
 313     let mut mask = 1 << bits >> 2;
 314     while mask != 0 {
 315         bw.write0();
 316         bw.write_bit((val & mask) != 0);
 317         mask >>= 1;
 318     }
 319     bw.write1();
 320 }
 321
 322 fn write_gammap(bw: &mut BitWriter, val: u32) {
 323     let bits = 31 - val.leading_zeros();
 324     write_unary(bw, bits, 1);
 325     bw.write(val - (1 << bits), bits as u8);
 326 }
 327
 328 #[cfg(test)]
 329 mod test {
 330     use super::*;
 331     use crate::io::bitreader::*;
 332     use crate::io::bitwriter::*;
 333
 334     #[test]
 335     fn int_codes() {
 336         const GDATA: [u8; 6] = [0b000_001_01, 0b0_0110_011, 0b1_1000_100, 0b1_1010_101, 0b10_10111_1, 0b1000_0000];
 337         let src = &GDATA;
 338         let mut br = BitReader::new(src, BitReaderMode::BE);
 339         for i in 0..11 {
 340             assert_eq!(br.read_code(UintCodeType::Golomb(5)).unwrap(), i);
 341         }
 342     }
 343     #[test]
 344     fn rw_codes() {
 345         let mut bw = BitWriter::new(Vec::new(), BitWriterMode::BE);
 346         bw.write_code(UintCodeType::Golomb(5), 42);
 347         bw.write_code(UintCodeType::Gamma, 42);
 348         bw.write_code(UintCodeType::GammaP, 42);
 349         let data = bw.end();
 350
 351         let mut br = BitReader::new(&data, BitReaderMode::BE);
 352         assert_eq!(br.read_code(UintCodeType::Golomb(5)).unwrap(), 42);
 353         assert_eq!(br.read_code(UintCodeType::Gamma).unwrap(), 42);
 354         assert_eq!(br.read_code(UintCodeType::GammaP).unwrap(), 42);
 355     }
 356 }