compression/lzhuf/
decoder.rs

1//! rust-compression
2//!
3//! # Licensing
4//! This Source Code is subject to the terms of the Mozilla Public License
5//! version 2.0 (the "License"). You can obtain a copy of the License at
6//! <http://mozilla.org/MPL/2.0/>.
7
8use crate::bitio::direction::left::Left;
9use crate::bitio::reader::{BitRead, BitReader};
10use crate::error::CompressionError;
11use crate::huffman::decoder::HuffmanDecoder;
12use crate::lzhuf::{LzhufMethod, LZSS_MIN_MATCH};
13use crate::lzss::decoder::LzssDecoder;
14use crate::lzss::LzssCode;
15use crate::traits::decoder::{
16    BitDecodeService, BitDecoder, BitDecoderImpl, DecodeIterator, Decoder,
17};
18#[cfg(not(feature = "std"))]
19#[allow(unused_imports)]
20use alloc::vec;
21#[cfg(not(feature = "std"))]
22use alloc::vec::Vec;
23
24#[derive(Debug)]
25enum LzhufHuffmanDecoder {
26    HuffmanDecoder(HuffmanDecoder<Left>),
27    Default(u16),
28}
29
30impl LzhufHuffmanDecoder {
31    pub(crate) fn dec<R: BitRead, I: Iterator<Item = u8>>(
32        &mut self,
33        reader: &mut R,
34        iter: &mut I,
35    ) -> Result<Option<u16>, CompressionError> {
36        match *self {
37            LzhufHuffmanDecoder::HuffmanDecoder(ref mut hd) => hd
38                .dec(reader, iter)
39                .map_err(|_| CompressionError::DataError),
40            LzhufHuffmanDecoder::Default(s) => Ok(Some(s)),
41        }
42    }
43}
44
45#[derive(Debug)]
46pub(crate) struct LzhufDecoderInner {
47    offset_len: usize,
48    min_match: usize,
49    block_len: usize,
50    symbol_decoder: Option<LzhufHuffmanDecoder>,
51    offset_decoder: Option<LzhufHuffmanDecoder>,
52}
53
54impl LzhufDecoderInner {
55    const SEARCH_TAB_LEN: usize = 12;
56
57    pub(crate) fn new(method: LzhufMethod) -> Self {
58        Self {
59            offset_len: method.offset_bits(),
60            min_match: LZSS_MIN_MATCH,
61            block_len: 0,
62
63            symbol_decoder: None,
64            offset_decoder: None,
65        }
66    }
67
68    fn dec_len<R: BitRead, I: Iterator<Item = u8>>(
69        &mut self,
70        reader: &mut R,
71        iter: &mut I,
72    ) -> Result<u8, CompressionError> {
73        let mut c = reader
74            .read_bits::<u8, _>(3, iter)
75            .map_err(|_| CompressionError::UnexpectedEof)?
76            .data();
77        if c == 7 {
78            while reader
79                .read_bits::<u8, _>(1, iter)
80                .map_err(|_| CompressionError::UnexpectedEof)?
81                .data()
82                == 1
83            {
84                c += 1;
85            }
86        }
87        Ok(c)
88    }
89
90    fn dec_len_tree<R: BitRead, I: Iterator<Item = u8>>(
91        &mut self,
92        tbit_len: usize,
93        reader: &mut R,
94        iter: &mut I,
95    ) -> Result<LzhufHuffmanDecoder, CompressionError> {
96        let len = reader
97            .read_bits::<u16, _>(tbit_len, iter)
98            .map_err(|_| CompressionError::UnexpectedEof)?
99            .data() as usize;
100        if len == 0 {
101            Ok(LzhufHuffmanDecoder::Default(
102                reader
103                    .read_bits::<u16, _>(tbit_len, iter)
104                    .map_err(|_| CompressionError::UnexpectedEof)?
105                    .data(),
106            ))
107        } else {
108            let mut ll = Vec::new();
109            while ll.len() < len {
110                if ll.len() == 3 {
111                    for _ in 0..reader
112                        .read_bits::<u8, _>(2, iter)
113                        .map_err(|_| CompressionError::UnexpectedEof)?
114                        .data()
115                    {
116                        ll.push(0);
117                    }
118                    if ll.len() > len {
119                        return Err(CompressionError::DataError);
120                    }
121                    if ll.len() == len {
122                        break;
123                    }
124                }
125                ll.push(self.dec_len(reader, iter)?);
126            }
127            Ok(LzhufHuffmanDecoder::HuffmanDecoder(
128                HuffmanDecoder::new(&ll, 5)
129                    .map_err(|_| CompressionError::DataError)?,
130            ))
131        }
132    }
133
134    fn dec_symb_tree<R: BitRead, I: Iterator<Item = u8>>(
135        &mut self,
136        len_decoder: &mut LzhufHuffmanDecoder,
137        reader: &mut R,
138        iter: &mut I,
139    ) -> Result<LzhufHuffmanDecoder, CompressionError> {
140        let len = reader
141            .read_bits::<u16, _>(9, iter)
142            .map_err(|_| CompressionError::UnexpectedEof)?
143            .data() as usize;
144        if len == 0 {
145            Ok(LzhufHuffmanDecoder::Default(
146                reader
147                    .read_bits::<u16, _>(9, iter)
148                    .map_err(|_| CompressionError::UnexpectedEof)?
149                    .data(),
150            ))
151        } else {
152            let mut ll = Vec::new();
153            while ll.len() < len {
154                match len_decoder.dec(reader, iter)? {
155                    None => return Err(CompressionError::UnexpectedEof),
156                    Some(0) => ll.push(0),
157                    Some(1) => {
158                        for _ in 0..(3 + reader
159                            .read_bits::<u8, _>(4, iter)
160                            .map_err(|_| CompressionError::UnexpectedEof)?
161                            .data())
162                        {
163                            ll.push(0);
164                        }
165                    }
166                    Some(2) => {
167                        for _ in 0..(20
168                            + reader
169                                .read_bits::<u16, _>(9, iter)
170                                .map_err(|_| CompressionError::UnexpectedEof)?
171                                .data())
172                        {
173                            ll.push(0);
174                        }
175                    }
176                    Some(n) => ll.push((n - 2) as u8),
177                }
178            }
179            Ok(LzhufHuffmanDecoder::HuffmanDecoder(
180                HuffmanDecoder::new(&ll, Self::SEARCH_TAB_LEN)
181                    .map_err(|_| CompressionError::DataError)?,
182            ))
183        }
184    }
185
186    fn dec_offs_tree<R: BitRead, I: Iterator<Item = u8>>(
187        &mut self,
188        pbit_len: usize,
189        reader: &mut R,
190        iter: &mut I,
191    ) -> Result<LzhufHuffmanDecoder, CompressionError> {
192        let len = reader
193            .read_bits::<u16, _>(pbit_len, iter)
194            .map_err(|_| CompressionError::UnexpectedEof)?
195            .data() as usize;
196        if len == 0 {
197            Ok(LzhufHuffmanDecoder::Default(
198                reader
199                    .read_bits::<u16, _>(pbit_len, iter)
200                    .map_err(|_| CompressionError::UnexpectedEof)?
201                    .data(),
202            ))
203        } else {
204            Ok(LzhufHuffmanDecoder::HuffmanDecoder(
205                HuffmanDecoder::new(
206                    &(0..len)
207                        .map(|_| self.dec_len(reader, iter))
208                        .collect::<Result<Vec<u8>, CompressionError>>()?,
209                    Self::SEARCH_TAB_LEN,
210                )
211                .map_err(|_| CompressionError::DataError)?,
212            ))
213        }
214    }
215
216    fn init_block<R: BitRead, I: Iterator<Item = u8>>(
217        &mut self,
218        reader: &mut R,
219        iter: &mut I,
220    ) -> Result<bool, CompressionError> {
221        match reader
222            .read_bits::<u16, _>(16, iter)
223            .map(|x| (x.data(), x.len()))
224            .map_err(|_| CompressionError::UnexpectedEof)?
225        {
226            (s, 16) if s != 0 => {
227                self.block_len = s as usize;
228                let mut lt = self.dec_len_tree(5, reader, iter)?;
229                self.symbol_decoder =
230                    Some(self.dec_symb_tree(&mut lt, reader, iter)?);
231                let offlen = self.offset_len;
232                self.offset_decoder =
233                    Some(self.dec_offs_tree(offlen, reader, iter)?);
234                Ok(true)
235            }
236            _ => Ok(false),
237        }
238    }
239}
240
241impl BitDecodeService for LzhufDecoderInner {
242    type Direction = Left;
243    type Error = CompressionError;
244    type Output = LzssCode;
245
246    fn next<I: Iterator<Item = u8>>(
247        &mut self,
248        reader: &mut BitReader<Self::Direction>,
249        iter: &mut I,
250    ) -> Result<Option<LzssCode>, CompressionError> {
251        if self.block_len == 0 && !self.init_block(reader, iter)? {
252            return Ok(None);
253        }
254        self.block_len -= 1;
255        let sym = self
256            .symbol_decoder
257            .as_mut()
258            .unwrap()
259            .dec(reader, iter)?
260            .ok_or_else(|| CompressionError::UnexpectedEof)?
261            as usize;
262        if sym <= 255 {
263            Ok(Some(LzssCode::Symbol(sym as u8)))
264        } else {
265            let len = sym - 256 + self.min_match;
266            let mut pos = self
267                .offset_decoder
268                .as_mut()
269                .unwrap()
270                .dec(reader, iter)?
271                .ok_or_else(|| CompressionError::UnexpectedEof)?
272                as usize;
273            if pos > 1 {
274                pos = (1 << (pos - 1))
275                    | reader
276                        .read_bits::<u16, _>(pos - 1, iter)
277                        .map_err(|_| CompressionError::UnexpectedEof)?
278                        .data() as usize;
279            }
280            Ok(Some(LzssCode::Reference { len, pos }))
281        }
282    }
283}
284
285#[derive(Debug)]
286pub(crate) struct LzhufDecoderBase {
287    lzss_decoder: LzssDecoder,
288    inner: LzhufDecoderInner,
289}
290
291impl LzhufDecoderBase {
292    const MAX_BLOCK_SIZE: usize = 0x1_0000;
293
294    pub(crate) fn new(method: LzhufMethod) -> Self {
295        Self {
296            lzss_decoder: LzssDecoder::new(Self::MAX_BLOCK_SIZE),
297            inner: LzhufDecoderInner::new(method),
298        }
299    }
300}
301
302impl BitDecodeService for LzhufDecoderBase {
303    type Direction = Left;
304    type Error = CompressionError;
305    type Output = u8;
306
307    fn next<I: Iterator<Item = u8>>(
308        &mut self,
309        reader: &mut BitReader<Self::Direction>,
310        iter: &mut I,
311    ) -> Result<Option<u8>, Self::Error> {
312        let mut bd = BitDecoder::<LzhufDecoderInner, _, _>::with_service(
313            &mut self.inner,
314            reader,
315        );
316        self.lzss_decoder
317            .next(&mut DecodeIterator::<I, _, _>::new(iter, &mut bd).flatten())
318            .transpose()
319    }
320}
321
322#[derive(Debug)]
323pub struct LzhufDecoder {
324    inner: BitDecoderImpl<LzhufDecoderBase>,
325}
326
327impl LzhufDecoder {
328    pub fn new(method: &LzhufMethod) -> Self {
329        Self {
330            inner: BitDecoderImpl::<LzhufDecoderBase>::with_service(
331                LzhufDecoderBase::new(*method),
332                BitReader::new(),
333            ),
334        }
335    }
336}
337
338impl Decoder for LzhufDecoder {
339    type Input = u8;
340    type Output = u8;
341    type Error = CompressionError;
342
343    fn next<I: Iterator<Item = Self::Input>>(
344        &mut self,
345        iter: &mut I,
346    ) -> Option<Result<Self::Output, Self::Error>> {
347        self.inner.next(iter)
348    }
349}
compression/lzhuf/decoder.rs

compression/lzhuf/
decoder.rs
