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