deflate/
input_buffer.rs

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

deflate/
input_buffer.rs
