1 // This was originally based on code from: https://github.com/nwin/lzw 2 // Copyright (c) 2015 nwin 3 // which is under both Apache 2.0 and MIT 4 5 //! This module provides a bit writer 6 use std::io::{self, Write}; 7 8 #[cfg(target_pointer_width = "64")] 9 #[macro_use] 10 mod arch_dep { 11 /// The data type of the accumulator. 12 /// a 64-bit value allows us to store more before 13 /// each push to the vector, but is sub-optimal 14 /// on 32-bit platforms. 15 pub type AccType = u64; 16 pub const FLUSH_AT: u8 = 48; 17 /// Push pending bits to vector. 18 /// Using a macro here since an inline function. 19 /// didn't optimise properly. 20 /// TODO June 2019: See if it's still needed. 21 macro_rules! push { 22 ($s:ident) => { 23 $s.w.extend_from_slice( 24 &[ 25 $s.acc as u8, 26 ($s.acc >> 8) as u8, 27 ($s.acc >> 16) as u8, 28 ($s.acc >> 24) as u8, 29 ($s.acc >> 32) as u8, 30 ($s.acc >> 40) as u8, 31 ][..], 32 ) 33 }; 34 } 35 } 36 #[cfg(not(target_pointer_width = "64"))] 37 #[macro_use] 38 mod arch_dep { 39 pub type AccType = u32; 40 pub const FLUSH_AT: u8 = 16; 41 macro_rules! push { 42 ($s:ident) => { 43 // Unlike the 64-bit case, using copy_from_slice seemed to worsen performance here. 44 // TODO: Needs benching on a 32-bit system to see what works best. 45 $s.w.push($s.acc as u8); 46 $s.w.push(($s.acc >> 8) as u8); 47 }; 48 } 49 } 50 51 use self::arch_dep::*; 52 53 /// Writes bits to a byte stream, LSB first. 54 pub struct LsbWriter { 55 // Public for now so it can be replaced after initialization. 56 pub w: Vec<u8>, 57 bits: u8, 58 acc: AccType, 59 } 60 61 impl LsbWriter { 62 /// Creates a new bit reader new(writer: Vec<u8>) -> LsbWriter63 pub fn new(writer: Vec<u8>) -> LsbWriter { 64 LsbWriter { 65 w: writer, 66 bits: 0, 67 acc: 0, 68 } 69 } 70 pending_bits(&self) -> u871 pub fn pending_bits(&self) -> u8 { 72 self.bits 73 } 74 75 /// Buffer n number of bits, and write them to the vec if there are enough pending bits. write_bits(&mut self, v: u16, n: u8)76 pub fn write_bits(&mut self, v: u16, n: u8) { 77 // NOTE: This outputs garbage data if n is 0, but v is not 0 78 self.acc |= (AccType::from(v)) << self.bits; 79 self.bits += n; 80 // Waiting until we have FLUSH_AT bits and pushing them all in one batch. 81 while self.bits >= FLUSH_AT { 82 push!(self); 83 self.acc >>= FLUSH_AT; 84 self.bits -= FLUSH_AT; 85 } 86 } 87 write_bits_finish(&mut self, v: u16, n: u8)88 fn write_bits_finish(&mut self, v: u16, n: u8) { 89 // NOTE: This outputs garbage data if n is 0, but v is not 0 90 self.acc |= (AccType::from(v)) << self.bits; 91 self.bits += n % 8; 92 while self.bits >= 8 { 93 self.w.push(self.acc as u8); 94 self.acc >>= 8; 95 self.bits -= 8; 96 } 97 } 98 flush_raw(&mut self)99 pub fn flush_raw(&mut self) { 100 let missing = FLUSH_AT - self.bits; 101 // Have to test for self.bits > 0 here, 102 // otherwise flush would output an extra byte when flush was called at a byte boundary 103 if missing > 0 && self.bits > 0 { 104 self.write_bits_finish(0, missing); 105 } 106 } 107 } 108 109 impl Write for LsbWriter { write(&mut self, buf: &[u8]) -> io::Result<usize>110 fn write(&mut self, buf: &[u8]) -> io::Result<usize> { 111 if self.acc == 0 { 112 self.w.extend_from_slice(buf) 113 } else { 114 for &byte in buf.iter() { 115 self.write_bits(u16::from(byte), 8) 116 } 117 } 118 Ok(buf.len()) 119 } 120 flush(&mut self) -> io::Result<()>121 fn flush(&mut self) -> io::Result<()> { 122 self.flush_raw(); 123 Ok(()) 124 } 125 } 126 127 #[cfg(test)] 128 mod test { 129 use super::LsbWriter; 130 131 #[test] write_bits()132 fn write_bits() { 133 let input = [ 134 (3, 3), 135 (10, 8), 136 (88, 7), 137 (0, 2), 138 (0, 5), 139 (0, 0), 140 (238, 8), 141 (126, 8), 142 (161, 8), 143 (10, 8), 144 (238, 8), 145 (174, 8), 146 (126, 8), 147 (174, 8), 148 (65, 8), 149 (142, 8), 150 (62, 8), 151 (10, 8), 152 (1, 8), 153 (161, 8), 154 (78, 8), 155 (62, 8), 156 (158, 8), 157 (206, 8), 158 (10, 8), 159 (64, 7), 160 (0, 0), 161 (24, 5), 162 (0, 0), 163 (174, 8), 164 (126, 8), 165 (193, 8), 166 (174, 8), 167 ]; 168 let expected = [ 169 83, 192, 2, 220, 253, 66, 21, 220, 93, 253, 92, 131, 28, 125, 20, 2, 66, 157, 124, 60, 170 157, 21, 128, 216, 213, 47, 216, 21, 171 ]; 172 let mut writer = LsbWriter::new(Vec::new()); 173 for v in input.iter() { 174 writer.write_bits(v.0, v.1); 175 } 176 writer.flush_raw(); 177 assert_eq!(writer.w, expected); 178 } 179 } 180 181 #[cfg(all(test, feature = "benchmarks"))] 182 mod bench { 183 use super::LsbWriter; 184 use test_std::Bencher; 185 #[bench] bit_writer(b: &mut Bencher)186 fn bit_writer(b: &mut Bencher) { 187 let input = [ 188 (3, 3), 189 (10, 8), 190 (88, 7), 191 (0, 2), 192 (0, 5), 193 (0, 0), 194 (238, 8), 195 (126, 8), 196 (161, 8), 197 (10, 8), 198 (238, 8), 199 (174, 8), 200 (126, 8), 201 (174, 8), 202 (65, 8), 203 (142, 8), 204 (62, 8), 205 (10, 8), 206 (1, 8), 207 (161, 8), 208 (78, 8), 209 (62, 8), 210 (158, 8), 211 (206, 8), 212 (10, 8), 213 (64, 7), 214 (0, 0), 215 (24, 5), 216 (0, 0), 217 (174, 8), 218 (126, 8), 219 (193, 8), 220 (174, 8), 221 ]; 222 let mut writer = LsbWriter::new(Vec::with_capacity(100)); 223 b.iter(|| { 224 for v in input.iter() { 225 let _ = writer.write_bits(v.0, v.1); 226 } 227 }); 228 } 229 } 230