nihav-core/src/io/intcode.rs

   1 use crate::io::bitreader::{BitReader, BitReaderError, BitReaderResult};
   2
   3 #[derive(Debug)]
   4 pub enum UintCodeType {
   5     UnaryOnes,
   6     UnaryZeroes,
   7     Unary012,
   8     Unary210,
   9     LimitedUnary(u32, u32),
  10     Golomb(u8),
  11     Rice(u8),
  12     Gamma,
  13     GammaP,
  14 }
  15
  16 pub enum IntCodeType {
  17     Golomb(u8),
  18     Rice(u8),
  19     Gamma,
  20     GammaP,
  21 }
  22
  23 pub trait IntCodeReader {
  24     fn read_code(&mut self, t: UintCodeType) -> BitReaderResult<u32>;
  25     fn read_code_signed(&mut self, t: IntCodeType) -> BitReaderResult<i32>;
  26 }
  27
  28 fn read_unary(br: &mut BitReader, terminator: u32) -> BitReaderResult<u32> {
  29     let mut res: u32 = 0;
  30     loop {
  31         if br.read(1)? == terminator { return Ok(res); }
  32         res = res + 1;
  33     }
  34 }
  35
  36 fn read_unary_lim(br: &mut BitReader, len: u32, terminator: u32) -> BitReaderResult<u32> {
  37     let mut res: u32 = 0;
  38     loop {
  39         if br.read(1)? == terminator { return Ok(res); }
  40         res = res + 1;
  41         if res == len { return Ok(res); }
  42     }
  43 }
  44
  45 fn read_unary210(br: &mut BitReader) -> BitReaderResult<u32> {
  46     let val = read_unary_lim(br, 2, 0)?;
  47     Ok(2 - val)
  48 }
  49
  50 fn read_golomb(br: &mut BitReader, m: u8) -> BitReaderResult<u32> {
  51     if m == 0 { return Err(BitReaderError::InvalidValue); }
  52     let nbits = (8 - m.leading_zeros()) as u8;
  53     if (m & (m - 1)) == 0 { return read_rice(br, nbits); }
  54     let cutoff = ((1 << nbits) - m) as u32;
  55     let pfx = read_unary(br, 0)?;
  56     let tail = br.read(nbits - 1)?;
  57     if tail < cutoff {
  58         let res = pfx * (m as u32) + tail;
  59         Ok (res)
  60     } else {
  61         let add = br.read(1)?;
  62         let res = pfx * (m as u32) + (tail - cutoff) * 2 + add + cutoff;
  63         Ok (res)
  64     }
  65 }
  66
  67 fn read_rice(br: &mut BitReader, k: u8) -> BitReaderResult<u32> {
  68     let pfx = read_unary(br, 1)?;
  69     let ret = (pfx << k) + br.read(k)?;
  70     Ok(ret)
  71 }
  72
  73 fn read_gamma(br: &mut BitReader) -> BitReaderResult<u32> {
  74     let mut ret = 1;
  75     while br.read(1)? != 1 {
  76         ret = (ret << 1) | br.read(1)?;
  77     }
  78     Ok(ret - 1)
  79 }
  80
  81 fn read_gammap(br: &mut BitReader) -> BitReaderResult<u32> {
  82     let pfx = read_unary(br, 1)?;
  83     if pfx > 32 { return Err(BitReaderError::InvalidValue); }
  84     let ret = (1 << pfx) + br.read(pfx as u8)?;
  85     Ok(ret)
  86 }
  87
  88 fn uval_to_sval0mp(uval: u32) -> i32 {
  89     if (uval & 1) != 0 { -((uval >> 1) as i32) }
  90     else               { (uval >> 1) as i32 }
  91 }
  92
  93 fn uval_to_sval0pm(uval: u32) -> i32 {
  94     if (uval & 1) != 0 { ((uval + 1) >> 1) as i32 }
  95     else               { -((uval >> 1) as i32) }
  96 }
  97
  98 impl<'a> IntCodeReader for BitReader<'a> {
  99     #[inline(always)]
 100     fn read_code(&mut self, t: UintCodeType) -> BitReaderResult<u32> {
 101         match t {
 102             UintCodeType::UnaryOnes               => read_unary(self, 0),
 103             UintCodeType::UnaryZeroes             => read_unary(self, 1),
 104             UintCodeType::LimitedUnary(len, term) => read_unary_lim(self, len, term),
 105             UintCodeType::Unary012                => read_unary_lim(self, 2, 0),
 106             UintCodeType::Unary210                => read_unary210(self),
 107             UintCodeType::Golomb(m)               => read_golomb(self, m),
 108             UintCodeType::Rice(k)                 => read_rice(self, k),
 109             UintCodeType::Gamma                   => read_gamma(self),
 110             UintCodeType::GammaP                  => read_gammap(self),
 111         }
 112     }
 113     #[allow(unused_variables)]
 114     fn read_code_signed(&mut self, t: IntCodeType) -> BitReaderResult<i32> {
 115         let uval =
 116             match t {
 117                 IntCodeType::Golomb(m)               => read_golomb(self, m)?,
 118                 IntCodeType::Rice(k)                 => read_rice(self, k)?,
 119                 IntCodeType::Gamma                   => read_gamma(self)?,
 120                 IntCodeType::GammaP                  => read_gammap(self)?,
 121             };
 122         match t {
 123             IntCodeType::Golomb(m)               => Ok(uval_to_sval0mp(uval)),
 124             IntCodeType::Rice(k)                 => Ok(uval_to_sval0mp(uval)),
 125             IntCodeType::Gamma                   => Ok(uval_to_sval0pm(uval)),
 126             IntCodeType::GammaP                  => Ok(uval_to_sval0pm(uval)),
 127         }
 128     }
 129 }
 130
 131 #[cfg(test)]
 132 mod test {
 133     use super::*;
 134     use crate::io::bitreader::*;
 135
 136     #[test]
 137     fn int_codes() {
 138         const GDATA: [u8; 6] = [0b000_001_01, 0b0_0110_011, 0b1_1000_100, 0b1_1010_101, 0b10_10111_1, 0b1000_0000];
 139         let src = &GDATA;
 140         let mut br = BitReader::new(src, src.len(), BitReaderMode::BE);
 141         for i in 0..11 {
 142             assert_eq!(br.read_code(UintCodeType::Golomb(5)).unwrap(), i);
 143         }
 144     }
 145 }