libflate/non_blocking/deflate/
decode.rs

1use crate::deflate::symbol::{self, HuffmanCodec};
2use crate::lz77;
3use crate::non_blocking::transaction::TransactionalBitReader;
4use core::cmp;
5use no_std_io2::io::{self, Read};
6/// DEFLATE decoder which supports non-blocking I/O.
7#[derive(Debug)]
8pub struct Decoder<R> {
9    state: DecoderState,
10    eos: bool,
11    bit_reader: TransactionalBitReader<R>,
12    block_decoder: BlockDecoder,
13}
14impl<R: Read> Decoder<R> {
15    /// Makes a new decoder instance.
16    ///
17    /// `inner` is to be decoded DEFLATE stream.
18    ///
19    /// # Examples
20    /// ```
21    /// use no_std_io2::io::{Cursor, Read};
22    /// use libflate::non_blocking::deflate::Decoder;
23    ///
24    /// let encoded_data = [243, 72, 205, 201, 201, 87, 8, 207, 47, 202, 73, 81, 4, 0];
25    /// let mut decoder = Decoder::new(&encoded_data[..]);
26    /// let mut buf = Vec::new();
27    /// decoder.read_to_end(&mut buf).unwrap();
28    ///
29    /// assert_eq!(buf, b"Hello World!");
30    /// ```
31    pub fn new(inner: R) -> Self {
32        Decoder {
33            state: DecoderState::ReadBlockHeader,
34            eos: false,
35            bit_reader: TransactionalBitReader::new(inner),
36            block_decoder: BlockDecoder::new(),
37        }
38    }
39
40    /// Returns the immutable reference to the inner stream.
41    pub fn as_inner_ref(&self) -> &R {
42        self.bit_reader.as_inner_ref()
43    }
44
45    /// Returns the mutable reference to the inner stream.
46    pub fn as_inner_mut(&mut self) -> &mut R {
47        self.bit_reader.as_inner_mut()
48    }
49
50    /// Unwraps this `Decoder`, returning the underlying reader.
51    ///
52    /// # Examples
53    /// ```
54    /// use no_std_io2::io::Cursor;
55    /// use libflate::non_blocking::deflate::Decoder;
56    ///
57    /// let encoded_data = [243, 72, 205, 201, 201, 87, 8, 207, 47, 202, 73, 81, 4, 0];
58    /// let decoder = Decoder::new(Cursor::new(&encoded_data));
59    /// assert_eq!(decoder.into_inner().into_inner(), &encoded_data);
60    /// ```
61    pub fn into_inner(self) -> R {
62        self.bit_reader.into_inner()
63    }
64
65    pub(crate) fn bit_reader_mut(&mut self) -> &mut TransactionalBitReader<R> {
66        &mut self.bit_reader
67    }
68}
69impl<R: Read> Read for Decoder<R> {
70    fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
71        let mut read_size;
72        loop {
73            let next = match self.state {
74                DecoderState::ReadBlockHeader => {
75                    let (bfinal, btype) = self.bit_reader.transaction(|r| {
76                        let bfinal = r.read_bit()?;
77                        let btype = r.read_bits(2)?;
78                        Ok((bfinal, btype))
79                    })?;
80                    self.eos = bfinal;
81                    self.block_decoder.enter_new_block();
82                    match btype {
83                        0b00 => DecoderState::ReadNonCompressedBlockLen,
84                        0b01 => DecoderState::LoadFixedHuffmanCode,
85                        0b10 => DecoderState::LoadDynamicHuffmanCode,
86                        0b11 => {
87                            return Err(invalid_data_error!(
88                                "btype 0x11 of DEFLATE is reserved(error) value"
89                            ));
90                        }
91                        _ => unreachable!(),
92                    }
93                }
94                DecoderState::ReadNonCompressedBlockLen => {
95                    let len = self.bit_reader.transaction(|r| {
96                        r.reset();
97                        let mut buf = [0; 2];
98                        r.as_inner_mut().read_exact(&mut buf)?;
99                        let len = u16::from_le_bytes(buf);
100                        r.as_inner_mut().read_exact(&mut buf)?;
101                        let nlen = u16::from_le_bytes(buf);
102                        if !len != nlen {
103                            Err(invalid_data_error!(
104                                "LEN={} is not the one's complement of NLEN={}",
105                                len,
106                                nlen
107                            ))
108                        } else {
109                            Ok(len)
110                        }
111                    })?;
112                    DecoderState::ReadNonCompressedBlock { len }
113                }
114                DecoderState::ReadNonCompressedBlock { len: 0 } => {
115                    if self.eos {
116                        read_size = 0;
117                        break;
118                    } else {
119                        DecoderState::ReadBlockHeader
120                    }
121                }
122                DecoderState::ReadNonCompressedBlock { ref mut len } => {
123                    let buf_len = buf.len();
124                    let buf = &mut buf[..cmp::min(buf_len, *len as usize)];
125                    read_size = self.bit_reader.as_inner_mut().read(buf)?;
126
127                    self.block_decoder.extend(&buf[..read_size]);
128                    *len -= read_size as u16;
129                    break;
130                }
131                DecoderState::LoadFixedHuffmanCode => {
132                    let symbol_decoder = self
133                        .bit_reader
134                        .transaction(|r| symbol::FixedHuffmanCodec.load(r))?;
135                    DecoderState::DecodeBlock(symbol_decoder)
136                }
137                DecoderState::LoadDynamicHuffmanCode => {
138                    let symbol_decoder = self
139                        .bit_reader
140                        .transaction(|r| symbol::DynamicHuffmanCodec.load(r))?;
141                    DecoderState::DecodeBlock(symbol_decoder)
142                }
143                DecoderState::DecodeBlock(ref mut symbol_decoder) => {
144                    self.block_decoder
145                        .decode(&mut self.bit_reader, symbol_decoder)?;
146                    read_size = self.block_decoder.read(buf)?;
147                    if read_size == 0 && !buf.is_empty() && !self.eos {
148                        DecoderState::ReadBlockHeader
149                    } else {
150                        break;
151                    }
152                }
153            };
154            self.state = next;
155        }
156        Ok(read_size)
157    }
158}
159
160#[derive(Debug)]
161enum DecoderState {
162    ReadBlockHeader,
163    ReadNonCompressedBlockLen,
164    ReadNonCompressedBlock { len: u16 },
165    LoadFixedHuffmanCode,
166    LoadDynamicHuffmanCode,
167    DecodeBlock(symbol::Decoder),
168}
169
170#[derive(Debug)]
171struct BlockDecoder {
172    lz77_decoder: lz77::Lz77Decoder,
173    eob: bool,
174}
175impl BlockDecoder {
176    pub fn new() -> Self {
177        BlockDecoder {
178            lz77_decoder: lz77::Lz77Decoder::new(),
179            eob: false,
180        }
181    }
182    pub fn enter_new_block(&mut self) {
183        self.eob = false;
184    }
185    pub fn decode<R: Read>(
186        &mut self,
187        bit_reader: &mut TransactionalBitReader<R>,
188        symbol_decoder: &mut symbol::Decoder,
189    ) -> io::Result<()> {
190        if self.eob {
191            return Ok(());
192        }
193        while let Some(s) = self.decode_symbol(bit_reader, symbol_decoder)? {
194            match s {
195                symbol::Symbol::Code(code) => {
196                    self.lz77_decoder.decode(code)?;
197                }
198                symbol::Symbol::EndOfBlock => {
199                    self.eob = true;
200                    break;
201                }
202            }
203        }
204        Ok(())
205    }
206
207    fn extend(&mut self, buf: &[u8]) {
208        self.lz77_decoder.extend_from_slice(buf);
209    }
210
211    fn decode_symbol<R: Read>(
212        &mut self,
213        bit_reader: &mut TransactionalBitReader<R>,
214        symbol_decoder: &mut symbol::Decoder,
215    ) -> io::Result<Option<symbol::Symbol>> {
216        let result = bit_reader.transaction(|bit_reader| {
217            let s = symbol_decoder.decode_unchecked(bit_reader);
218            bit_reader.check_last_error().map(|()| s)
219        });
220        match result {
221            Err(ref e) if e.kind() == io::ErrorKind::WouldBlock => Ok(None),
222            Err(e) => Err(e),
223            Ok(s) => Ok(Some(s)),
224        }
225    }
226}
227impl Read for BlockDecoder {
228    fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
229        if !self.lz77_decoder.buffer().is_empty() {
230            self.lz77_decoder.read(buf)
231        } else if self.eob {
232            Ok(0)
233        } else {
234            Err(io::Error::new(io::ErrorKind::WouldBlock, "Would block"))
235        }
236    }
237}
238
239#[cfg(test)]
240mod tests {
241    use super::*;
242    use crate::deflate::{EncodeOptions, Encoder};
243    use crate::util::{WouldBlockReader, nb_read_to_end};
244    use alloc::{format, string::String, vec::Vec};
245    use no_std_io2::io::{Read, Write};
246
247    #[test]
248    fn it_works() {
249        let mut encoder = Encoder::new(Vec::new());
250        encoder.write_all(b"Hello World!".as_ref()).unwrap();
251        let encoded_data = encoder.finish().into_result().unwrap();
252
253        let mut decoder = Decoder::new(&encoded_data[..]);
254        let mut decoded_data = Vec::new();
255        decoder.read_to_end(&mut decoded_data).unwrap();
256
257        assert_eq!(decoded_data, b"Hello World!");
258    }
259
260    #[test]
261    fn non_blocking_io_works() {
262        let mut encoder = Encoder::new(Vec::new());
263        encoder.write_all(b"Hello World!".as_ref()).unwrap();
264        let encoded_data = encoder.finish().into_result().unwrap();
265
266        let decoder = Decoder::new(WouldBlockReader::new(&encoded_data[..]));
267        let decoded_data = nb_read_to_end(decoder).unwrap();
268
269        assert_eq!(decoded_data, b"Hello World!");
270    }
271
272    #[test]
273    fn non_blocking_io_for_large_text_works() {
274        let text: String = (0..10000)
275            .into_iter()
276            .map(|i| format!("test {}", i))
277            .collect();
278
279        let mut encoder = crate::deflate::Encoder::new(Vec::new());
280        encoder.write_all(text.as_bytes()).unwrap();
281        let encoded_data = encoder.finish().into_result().unwrap();
282
283        let decoder = Decoder::new(WouldBlockReader::new(&encoded_data[..]));
284        let decoded_data = nb_read_to_end(decoder).unwrap();
285        assert_eq!(decoded_data, text.as_bytes());
286    }
287
288    #[test]
289    fn non_compressed_non_blocking_io_works() {
290        let mut encoder = Encoder::with_options(Vec::new(), EncodeOptions::new().no_compression());
291        encoder.write_all(b"Hello World!".as_ref()).unwrap();
292        let encoded_data = encoder.finish().into_result().unwrap();
293
294        let decoder = Decoder::new(WouldBlockReader::new(&encoded_data[..]));
295        let decoded_data = nb_read_to_end(decoder).unwrap();
296
297        assert_eq!(decoded_data, b"Hello World!");
298    }
299}
libflate/non_blocking/deflate/decode.rs

libflate/non_blocking/deflate/
decode.rs
