1 use std::cmp; 2 3 use chained_hash_table::WINDOW_SIZE; 4 use huffman_table; 5 6 const MAX_MATCH: usize = huffman_table::MAX_MATCH as usize; 7 8 /// The maximum size of the buffer. 9 pub const BUFFER_SIZE: usize = (WINDOW_SIZE * 2) + MAX_MATCH; 10 11 pub struct InputBuffer { 12 buffer: Vec<u8>, 13 } 14 15 impl InputBuffer { 16 #[cfg(test)] new<'a>(data: &'a [u8]) -> (InputBuffer, Option<&[u8]>)17 pub fn new<'a>(data: &'a [u8]) -> (InputBuffer, Option<&[u8]>) { 18 let mut b = InputBuffer::empty(); 19 let rem = b.add_data(data); 20 (b, rem) 21 } 22 empty() -> InputBuffer23 pub fn empty() -> InputBuffer { 24 InputBuffer { 25 buffer: Vec::with_capacity(BUFFER_SIZE), 26 } 27 } 28 29 /// Add data to the buffer. 30 /// 31 /// Returns a slice of the data that was not added (including the lookahead if any). add_data<'a>(&mut self, data: &'a [u8]) -> Option<&'a [u8]>32 pub fn add_data<'a>(&mut self, data: &'a [u8]) -> Option<&'a [u8]> { 33 debug_assert!(self.current_end() <= BUFFER_SIZE); 34 if self.current_end() + data.len() > BUFFER_SIZE { 35 // Add data and return how much was left. 36 let consumed = { 37 let space_left = BUFFER_SIZE - self.buffer.len(); 38 self.buffer.extend_from_slice(&data[..space_left]); 39 space_left 40 }; 41 Some(&data[consumed..]) 42 } else { 43 // There's space for all of the data. 44 self.buffer.extend_from_slice(data); 45 None 46 } 47 } 48 49 /// Get the current amount of data in the buffer. current_end(&self) -> usize50 pub fn current_end(&self) -> usize { 51 self.buffer.len() 52 } 53 54 /// Slide the input window and add new data. 55 /// 56 /// Returns a slice containing the data that did not fit, or None if all data was consumed. slide<'a>(&mut self, data: &'a [u8]) -> Option<&'a [u8]>57 pub fn slide<'a>(&mut self, data: &'a [u8]) -> Option<&'a [u8]> { 58 // This should only be used when the buffer is full 59 assert!(self.buffer.len() > WINDOW_SIZE * 2); 60 61 // Do this in a closure to to end the borrow of buffer. 62 let (final_len, upper_len, end) = { 63 // Split into lower window and upper window + lookahead 64 let (lower, upper) = self.buffer.split_at_mut(WINDOW_SIZE); 65 // Copy the upper window to the lower window 66 lower.copy_from_slice(&upper[..WINDOW_SIZE]); 67 let lookahead_len = { 68 // Copy the lookahead to the start of the upper window 69 let (upper_2, lookahead) = upper.split_at_mut(WINDOW_SIZE); 70 let lookahead_len = lookahead.len(); 71 debug_assert!(lookahead_len <= MAX_MATCH); 72 upper_2[..lookahead_len].copy_from_slice(lookahead); 73 lookahead_len 74 }; 75 76 // Length of the upper window minus the lookahead bytes 77 let upper_len = upper.len() - lookahead_len; 78 let end = cmp::min(data.len(), upper_len); 79 upper[lookahead_len..lookahead_len + end].copy_from_slice(&data[..end]); 80 // Remove unused data if any. 81 (lower.len() + lookahead_len + end, upper_len, end) 82 }; 83 // Remove unused space. 84 self.buffer.truncate(final_len); 85 86 if data.len() > upper_len { 87 // Return a slice of the data that was not added 88 Some(&data[end..]) 89 } else { 90 None 91 } 92 } 93 94 /// Get a mutable slice of the used part of the buffer. get_buffer(&mut self) -> &mut [u8]95 pub fn get_buffer(&mut self) -> &mut [u8] { 96 &mut self.buffer 97 } 98 } 99 100 #[cfg(test)] 101 mod test { 102 use super::MAX_MATCH; 103 use chained_hash_table::WINDOW_SIZE; 104 use super::*; 105 #[test] buffer_add_full()106 pub fn buffer_add_full() { 107 let data = [10u8; BUFFER_SIZE + 10]; 108 let (mut buf, extra) = InputBuffer::new(&data[..]); 109 assert!(extra.unwrap() == &[10; 10]); 110 let to_add = [2, 5, 3]; 111 let not_added = buf.add_data(&to_add); 112 assert_eq!(not_added.unwrap(), to_add); 113 } 114 115 #[test] buffer_add_not_full()116 pub fn buffer_add_not_full() { 117 let data = [10u8; BUFFER_SIZE - 5]; 118 let (mut buf, extra) = InputBuffer::new(&data[..]); 119 assert_eq!(buf.current_end(), data.len()); 120 assert_eq!(extra, None); 121 let to_add = [2, 5, 3]; 122 { 123 let not_added = buf.add_data(&to_add); 124 assert!(not_added.is_none()); 125 } 126 let not_added = buf.add_data(&to_add); 127 assert_eq!(not_added.unwrap()[0], 3); 128 } 129 130 #[test] slide()131 fn slide() { 132 let data = [10u8; BUFFER_SIZE]; 133 let (mut buf, extra) = InputBuffer::new(&data[..]); 134 assert_eq!(extra, None); 135 let to_add = [5; 5]; 136 let rem = buf.slide(&to_add); 137 assert!(rem.is_none()); 138 { 139 let slice = buf.get_buffer(); 140 assert!(slice[..WINDOW_SIZE + MAX_MATCH] == data[WINDOW_SIZE..]); 141 assert_eq!( 142 slice[WINDOW_SIZE + MAX_MATCH..WINDOW_SIZE + MAX_MATCH + 5], 143 to_add 144 ); 145 } 146 assert_eq!(buf.current_end(), WINDOW_SIZE + MAX_MATCH + to_add.len()); 147 } 148 } 149