diff options
Diffstat (limited to 'third_party/rust/deflate/src/bitstream.rs')
| -rw-r--r-- | third_party/rust/deflate/src/bitstream.rs | 265 |
1 files changed, 265 insertions, 0 deletions
diff --git a/third_party/rust/deflate/src/bitstream.rs b/third_party/rust/deflate/src/bitstream.rs new file mode 100644 index 0000000000..6aba35d4c1 --- /dev/null +++ b/third_party/rust/deflate/src/bitstream.rs @@ -0,0 +1,265 @@ +// This was originally based on code from: https://github.com/nwin/lzw +// Copyright (c) 2015 nwin +// which is under both Apache 2.0 and MIT + +//! This module provides a bit writer +use std::io::{self, Write}; + +#[cfg(target_pointer_width = "64")] +#[macro_use] +mod arch_dep { + /// The data type of the accumulator. + /// a 64-bit value allows us to store more before + /// each push to the vector, but is sub-optimal + /// on 32-bit platforms. + pub type AccType = u64; + pub const FLUSH_AT: u8 = 48; + /// Push pending bits to vector. + /// Using a macro here since an inline function. + /// didn't optimise properly. + macro_rules! push{ + ($s:ident) => { + let len = $s.w.len(); + $s.w.reserve(6); + // Optimization: + // + // This is basically what `Vec::extend_from_slice` does, but it didn't inline + // properly, so we do it manually for now. + // + // # Unsafe + // We reserve enough space right before this, so setting the len manually and doing + // unchecked indexing is safe here since we only, and always write to all of the the + // uninitialized bytes of the vector. + unsafe { + $s.w.set_len(len + 6); + $s.w.get_unchecked_mut(len..).copy_from_slice(&[$s.acc as u8, + ($s.acc >> 8) as u8, + ($s.acc >> 16) as u8, + ($s.acc >> 24) as u8, + ($s.acc >> 32) as u8, + ($s.acc >> 40) as u8 + ][..]); + } + + }; + } +} +#[cfg(not(target_pointer_width = "64"))] +#[macro_use] +mod arch_dep { + pub type AccType = u32; + pub const FLUSH_AT: u8 = 16; + macro_rules! push{ + ($s:ident) => { + // Unlike the 64-bit case, using copy_from_slice seemed to worsen performance here. + // TODO: Needs benching on a 32-bit system to see what works best. + $s.w.push($s.acc as u8); + $s.w.push(($s.acc >> 8) as u8); + }; + } +} + +use self::arch_dep::*; + +/// Writes bits to a byte stream, LSB first. +pub struct LsbWriter { + // Public for now so it can be replaced after initialization. + pub w: Vec<u8>, + bits: u8, + acc: AccType, +} + +impl LsbWriter { + /// Creates a new bit reader + pub fn new(writer: Vec<u8>) -> LsbWriter { + LsbWriter { + w: writer, + bits: 0, + acc: 0, + } + } + + pub fn pending_bits(&self) -> u8 { + self.bits + } + + /// Buffer n number of bits, and write them to the vec if there are enough pending bits. + pub fn write_bits(&mut self, v: u16, n: u8) { + // NOTE: This outputs garbage data if n is 0, but v is not 0 + self.acc |= (v as AccType) << self.bits; + self.bits += n; + // Waiting until we have FLUSH_AT bits and pushing them all in one batch. + while self.bits >= FLUSH_AT { + push!(self); + self.acc >>= FLUSH_AT; + self.bits -= FLUSH_AT; + } + } + + fn write_bits_finish(&mut self, v: u16, n: u8) { + // NOTE: This outputs garbage data if n is 0, but v is not 0 + self.acc |= (v as AccType) << self.bits; + self.bits += n % 8; + while self.bits >= 8 { + self.w.push(self.acc as u8); + self.acc >>= 8; + self.bits -= 8; + } + } + + pub fn flush_raw(&mut self) { + let missing = FLUSH_AT - self.bits; + // Have to test for self.bits > 0 here, + // otherwise flush would output an extra byte when flush was called at a byte boundary + if missing > 0 && self.bits > 0 { + self.write_bits_finish(0, missing); + } + } +} + +impl Write for LsbWriter { + fn write(&mut self, buf: &[u8]) -> io::Result<usize> { + if self.acc == 0 { + self.w.extend_from_slice(buf) + } else { + for &byte in buf.iter() { + self.write_bits(byte as u16, 8) + } + } + Ok(buf.len()) + } + + fn flush(&mut self) -> io::Result<()> { + self.flush_raw(); + Ok(()) + } +} + +#[cfg(test)] +mod test { + use super::LsbWriter; + + #[test] + fn write_bits() { + let input = [ + (3, 3), + (10, 8), + (88, 7), + (0, 2), + (0, 5), + (0, 0), + (238, 8), + (126, 8), + (161, 8), + (10, 8), + (238, 8), + (174, 8), + (126, 8), + (174, 8), + (65, 8), + (142, 8), + (62, 8), + (10, 8), + (1, 8), + (161, 8), + (78, 8), + (62, 8), + (158, 8), + (206, 8), + (10, 8), + (64, 7), + (0, 0), + (24, 5), + (0, 0), + (174, 8), + (126, 8), + (193, 8), + (174, 8), + ]; + let expected = [ + 83, + 192, + 2, + 220, + 253, + 66, + 21, + 220, + 93, + 253, + 92, + 131, + 28, + 125, + 20, + 2, + 66, + 157, + 124, + 60, + 157, + 21, + 128, + 216, + 213, + 47, + 216, + 21, + ]; + let mut writer = LsbWriter::new(Vec::new()); + for v in input.iter() { + writer.write_bits(v.0, v.1); + } + writer.flush_raw(); + assert_eq!(writer.w, expected); + } +} + + +#[cfg(all(test, feature = "benchmarks"))] +mod bench { + use test_std::Bencher; + use super::LsbWriter; + #[bench] + fn bit_writer(b: &mut Bencher) { + let input = [ + (3, 3), + (10, 8), + (88, 7), + (0, 2), + (0, 5), + (0, 0), + (238, 8), + (126, 8), + (161, 8), + (10, 8), + (238, 8), + (174, 8), + (126, 8), + (174, 8), + (65, 8), + (142, 8), + (62, 8), + (10, 8), + (1, 8), + (161, 8), + (78, 8), + (62, 8), + (158, 8), + (206, 8), + (10, 8), + (64, 7), + (0, 0), + (24, 5), + (0, 0), + (174, 8), + (126, 8), + (193, 8), + (174, 8), + ]; + let mut writer = LsbWriter::new(Vec::with_capacity(100)); + b.iter(|| for v in input.iter() { + let _ = writer.write_bits(v.0, v.1); + }); + } +} |