| 1 |
//! # Bit-stream tools. |
| 2 |
use core::mem; |
| 3 |
use crate::error::{LhaResult, LhaError}; |
| 4 |
use crate::stub_io::Read; |
| 5 |
|
| 6 |
type BitBuf = usize; |
| 7 |
const BITBUF_BYTESIZE: usize = mem::size_of::<BitBuf>(); |
| 8 |
const BITBUF_BITSIZE: u32 = (BITBUF_BYTESIZE * 8) as u32; |
| 9 |
|
| 10 |
/// The trait is implemented for all the types that can receive bits using [BitRead::read_bits]. |
| 11 |
pub trait UBits: Copy { |
| 12 |
fn from_bits(bitbuf: BitBuf) -> Self; |
| 13 |
} |
| 14 |
|
| 15 |
/// This trait is being used to read single bits from data source. |
| 16 |
pub trait BitRead { |
| 17 |
type Error; |
| 18 |
/// Reads the next single bit from the stream. `true` represents `1` and `false` represents `0`. |
| 19 |
fn read_bit(&mut self) -> Result<bool, LhaError<Self::Error>>; |
| 20 |
/// Reads the next `n` bits from the stream. |
| 21 |
/// |
| 22 |
/// For example reading 4 bits into the `u8` type will result in: `0b0000abcd` where |
| 23 |
/// `a`, `b`, `c`, `d` are consecutive bits that were read from source. |
| 24 |
/// |
| 25 |
/// Returns `0` if `n` is `0`. |
| 26 |
/// |
| 27 |
/// # Panics |
| 28 |
/// Panics if `n` exceed the bit capacity of `T`. |
| 29 |
fn read_bits<T: UBits>(&mut self, n: u32) -> Result<T, LhaError<Self::Error>>; |
| 30 |
// /// Creates a "by reference" adaptor for this instance of `BitRead`. |
| 31 |
// /// The returned adaptor also implements `BitRead` and will simply borrow this current reader. |
| 32 |
// fn by_ref(&mut self) -> &mut Self { |
| 33 |
// self |
| 34 |
// } |
| 35 |
} |
| 36 |
|
| 37 |
/// A simple bit-stream reader, wrapped over a readable stream. |
| 38 |
/// |
| 39 |
/// Bits are being read from an each consecutive byte, starting from its highest bit. |
| 40 |
#[derive(Debug)] |
| 41 |
pub struct BitStream<R> { |
| 42 |
inner: R, |
| 43 |
// x..x10..0 |
| 44 |
bits_buf: BitBuf, |
| 45 |
} |
| 46 |
|
| 47 |
macro_rules! impl_ubits { |
| 48 |
($ty:ty) => { |
| 49 |
impl UBits for $ty { |
| 50 |
#[inline(always)] |
| 51 |
fn from_bits(bitbuf: BitBuf) -> Self { |
| 52 |
bitbuf as $ty |
| 53 |
} |
| 54 |
} |
| 55 |
}; |
| 56 |
} |
| 57 |
|
| 58 |
impl_ubits!(u8); |
| 59 |
impl_ubits!(u16); |
| 60 |
impl_ubits!(u32); |
| 61 |
impl_ubits!(usize); |
| 62 |
|
| 63 |
impl<R: Read> BitStream<R> { |
| 64 |
/// Creates a new `BitStream<R>`. |
| 65 |
pub fn new(inner: R) -> BitStream<R> { |
| 66 |
BitStream { inner, bits_buf: 1 << (BITBUF_BITSIZE - 1) } |
| 67 |
} |
| 68 |
/// Unwraps this `BitStream<R>`, returning the underlying reader. |
| 69 |
/// |
| 70 |
/// Note that any leftover data in the internal bit buffer is lost. Therefore, a following read from |
| 71 |
/// the underlying reader may lead to data loss. |
| 72 |
pub fn into_inner(self) -> R { |
| 73 |
self.inner |
| 74 |
} |
| 75 |
|
| 76 |
#[inline] |
| 77 |
fn next_bits(&mut self, n: u32) -> LhaResult<BitBuf, R> { |
| 78 |
debug_assert!(n != 0 && n <= BITBUF_BITSIZE); |
| 79 |
let have_bits = BITBUF_BITSIZE - self.bits_buf.trailing_zeros() - 1; |
| 80 |
let res = self.bits_buf >> (BITBUF_BITSIZE - n); |
| 81 |
|
| 82 |
if n <= have_bits { |
| 83 |
self.bits_buf <<= n; |
| 84 |
return Ok(res) |
| 85 |
} |
| 86 |
|
| 87 |
let missing_bits = n - have_bits; |
| 88 |
let mut buf = [0u8;BITBUF_BYTESIZE]; |
| 89 |
let bits_read = 8u32 * self.inner.read_all(&mut buf) |
| 90 |
.map_err(LhaError::Io)? as u32; |
| 91 |
if bits_read < missing_bits { |
| 92 |
return Err(LhaError::Io(R::unexpected_eof())) |
| 93 |
} |
| 94 |
let new_bits: BitBuf = BitBuf::from_be_bytes(buf); |
| 95 |
// clear trailing bits and merge |
| 96 |
let res = res & (res - 1) |
| 97 |
| new_bits >> (BITBUF_BITSIZE - missing_bits); |
| 98 |
self.bits_buf = if missing_bits == BITBUF_BITSIZE { |
| 99 |
0 |
| 100 |
} |
| 101 |
else { |
| 102 |
new_bits << missing_bits |
| 103 |
} | 1 << (BITBUF_BITSIZE - 1 - (bits_read - missing_bits)); |
| 104 |
Ok(res) |
| 105 |
} |
| 106 |
|
| 107 |
// #[inline] |
| 108 |
// fn read_exact_or_to_end(&mut self, mut buf: &mut[u8]) -> io::Result<usize> { |
| 109 |
// let orig_len = buf.len(); |
| 110 |
// while !buf.is_empty() { |
| 111 |
// match self.inner.read(buf) { |
| 112 |
// Ok(0) => break, |
| 113 |
// Ok(n) => buf = &mut buf[n..], |
| 114 |
// Err(ref e) if e.kind() == io::ErrorKind::Interrupted => {} |
| 115 |
// Err(e) => return Err(e), |
| 116 |
// } |
| 117 |
// } |
| 118 |
// Ok(orig_len - buf.len()) |
| 119 |
// } |
| 120 |
} |
| 121 |
|
| 122 |
impl<R: BitRead> BitRead for &mut R { |
| 123 |
type Error = R::Error; |
| 124 |
|
| 125 |
#[inline] |
| 126 |
fn read_bit(&mut self) -> Result<bool, LhaError<Self::Error>> { |
| 127 |
(*self).read_bit() |
| 128 |
} |
| 129 |
|
| 130 |
#[inline] |
| 131 |
fn read_bits<T: UBits>(&mut self, n: u32) -> Result<T, LhaError<Self::Error>> { |
| 132 |
(*self).read_bits(n) |
| 133 |
} |
| 134 |
} |
| 135 |
|
| 136 |
impl<R: Read> BitRead for BitStream<R> { |
| 137 |
type Error = R::Error; |
| 138 |
|
| 139 |
#[inline] |
| 140 |
fn read_bit(&mut self) -> Result<bool, LhaError<Self::Error>> { |
| 141 |
self.next_bits(1).map(|bits| bits != 0) |
| 142 |
} |
| 143 |
|
| 144 |
fn read_bits<T: UBits>(&mut self, n: u32) -> Result<T, LhaError<Self::Error>> { |
| 145 |
match n { |
| 146 |
0 => Ok(0), |
| 147 |
n if n <= bitsize::<T>() => self.next_bits(n), |
| 148 |
_ => Err(LhaError::Decompress("too many bits requested")) |
| 149 |
}.map(T::from_bits) |
| 150 |
} |
| 151 |
} |
| 152 |
|
| 153 |
#[inline(always)] |
| 154 |
const fn bitsize<T>() -> u32 { |
| 155 |
mem::size_of::<T>() as u32 * 8 |
| 156 |
} |
| 157 |
|
| 158 |
#[cfg(feature = "std")] |
| 159 |
#[cfg(test)] |
| 160 |
mod tests { |
| 161 |
use std::io; |
| 162 |
use super::*; |
| 163 |
#[test] |
| 164 |
fn bit_stream_works() { |
| 165 |
assert_eq!(BITBUF_BYTESIZE, mem::size_of::<usize>()); |
| 166 |
assert!(BITBUF_BITSIZE >= 32); |
| 167 |
assert_eq!(BITBUF_BITSIZE, BITBUF_BYTESIZE as u32 * 8); |
| 168 |
let mut somebits: &[u8] = &[]; |
| 169 |
let mut brdr = BitStream::new(&mut somebits); |
| 170 |
let err: io::Error = brdr.read_bit().unwrap_err().into(); |
| 171 |
assert_eq!(err.kind(), io::ErrorKind::UnexpectedEof); |
| 172 |
let err: io::Error = brdr.read_bits::<usize>(BITBUF_BITSIZE).unwrap_err().into(); |
| 173 |
assert_eq!(err.kind(), io::ErrorKind::UnexpectedEof); |
| 174 |
let mut somebits: &[u8] = &[0]; |
| 175 |
let mut brdr = BitStream::new(&mut somebits); |
| 176 |
for _ in 0..8 { |
| 177 |
assert_eq!(brdr.read_bit().unwrap(), false); |
| 178 |
} |
| 179 |
let mut somebits: &[u8] = &[!0]; |
| 180 |
let mut brdr = BitStream::new(&mut somebits); |
| 181 |
for _ in 0..8 { |
| 182 |
assert_eq!(brdr.read_bit().unwrap(), true); |
| 183 |
} |
| 184 |
let mut somebits: &[u8] = &[0b01001100, 0b01110000, 0b11110000, 0b01111100, 0b00001111, 0b11000000, 0b01111111, |
| 185 |
0b00000000, 0b11111111, 0b00000000, 0b01111111, 0b11000000, 0b00001111, 0b11111100, |
| 186 |
0b00000000, 0b01111111, 0b11110000, 0b00000000, 0b11111111, 0b11110000, 0b00000000, |
| 187 |
0b01111111, 0b11111100, 0b00000000, 0b00001111, 0b11111111, 0b11000000, 0b00000000, |
| 188 |
0b01111111, 0b11111111]; |
| 189 |
assert_eq!(brdr.read_bits::<usize>(0).unwrap(), 0); |
| 190 |
let mut brdr = BitStream::new(&mut somebits); |
| 191 |
for n in 1..16 { |
| 192 |
assert_eq!(brdr.read_bits::<u16>(n).unwrap(), 0); |
| 193 |
assert_eq!(brdr.read_bits::<u16>(n).unwrap(), (1 << n) - 1); |
| 194 |
} |
| 195 |
assert_eq!(brdr.read_bits::<usize>(0).unwrap(), 0); |
| 196 |
let err: io::Error = brdr.read_bit().unwrap_err().into(); |
| 197 |
assert_eq!(err.kind(), io::ErrorKind::UnexpectedEof); |
| 198 |
|
| 199 |
let mut somebits: &[u8] = &[1,2,3,4,5,6,7,8]; |
| 200 |
let mut brdr = BitStream::new(&mut somebits); |
| 201 |
match BITBUF_BITSIZE { |
| 202 |
#[cfg(target_pointer_width = "64")] |
| 203 |
64 => { |
| 204 |
assert_eq!(brdr.read_bits::<usize>(BITBUF_BITSIZE).unwrap(), 0x0102030405060708); |
| 205 |
} |
| 206 |
#[cfg(target_pointer_width = "32")] |
| 207 |
32 => { |
| 208 |
assert_eq!(brdr.read_bits::<usize>(BITBUF_BITSIZE).unwrap(), 0x01020304); |
| 209 |
} |
| 210 |
_ => unimplemented!() |
| 211 |
} |
| 212 |
} |
| 213 |
} |