deflate/
input_buffer.rs

Help
1use std::cmp;
2
3use chained_hash_table::WINDOW_SIZE;
4use huffman_table;
5
6const MAX_MATCH: usize = huffman_table::MAX_MATCH as usize;
7
8/// The maximum size of the buffer.
9pub const BUFFER_SIZE: usize = (WINDOW_SIZE * 2) + MAX_MATCH;
10
11pub struct InputBuffer {
12    buffer: Vec<u8>,
13}
14
15impl InputBuffer {
16    #[cfg(test)]
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
23    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).
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.
50    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.
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.
95    pub fn get_buffer(&mut self) -> &mut [u8] {
96        &mut self.buffer
97    }
98}
99
100#[cfg(test)]
101mod test {
102    use super::MAX_MATCH;
103    use chained_hash_table::WINDOW_SIZE;
104    use super::*;
105    #[test]
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]
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]
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}
deflate/input_buffer.rs

deflate/
input_buffer.rs
