Debian Codegraph @

.cargo/vendor/delharc/src/decode/lhv2.rs

raw
1 use core::num::NonZeroU32;
2 #[cfg(not(feature = "std"))]
3 use alloc::boxed::Box;
4 use crate::error::{LhaResult, LhaError};
5 use crate::stub_io::Read;
6 use crate::bitstream::*;
7 use crate::statictree::*;
8 use crate::ringbuf::*;
9
10 use super::Decoder;
11
12 const NUM_COMMANDS: usize = 510;
13 const NUM_TEMP_CODELEN: usize = 20;
14
15 pub trait LhaDecoderConfig {
16 type RingBuffer: RingBuffer;
17 const HISTORY_BITS: u32;
18 const OFFSET_BITS: u32;
19 }
20
21 /// A generic decoder for LHArc version 2 compression methods.
22 #[derive(Debug)]
23 pub struct LhaV2Decoder<C: LhaDecoderConfig, R> {
24 bit_reader: BitStream<R>,
25 command_tree: HuffTree,
26 offset_tree: HuffTree,
27 remaining_commands: u16,
28 copy_progress: Option<(u32, NonZeroU32)>,
29 ringbuf: Box<C::RingBuffer>,
30 }
31
32 macro_rules! impl_lhav2_decoder {
33 ($cfg_name:ident, HISTORY_BITS=$history_bits:literal, OFFSET_BITS=$offset_bits:literal) => {
34 #[derive(Debug)]
35 pub struct $cfg_name;
36
37 impl LhaDecoderConfig for $cfg_name {
38 type RingBuffer = RingArrayBuf<{1 << $history_bits - 1}>;
39 const HISTORY_BITS: u32 = $history_bits;
40 const OFFSET_BITS: u32 = $offset_bits;
41 }
42 };
43 }
44
45 impl_lhav2_decoder!(Lh5DecoderCfg, HISTORY_BITS=14, OFFSET_BITS=4);
46 impl_lhav2_decoder!(Lh7DecoderCfg, HISTORY_BITS=17, OFFSET_BITS=5);
47 #[cfg(feature = "lhx")]
48 impl_lhav2_decoder!(LhxDecoderCfg, HISTORY_BITS=20, OFFSET_BITS=5);
49
50 /// A decoder for `-lh4-` and `-lh5-` compression methods.
51 pub type Lh5Decoder<R> = LhaV2Decoder<Lh5DecoderCfg, R>;
52 /// A decoder for `-lh6-` and `-lh7-` compression methods.
53 pub type Lh7Decoder<R> = LhaV2Decoder<Lh7DecoderCfg, R>;
54 /// A decoder for `-lhx-` compression methods.
55 #[cfg(feature = "lhx")]
56 pub type LhxDecoder<R> = LhaV2Decoder<LhxDecoderCfg, R>;
57
58
59 impl<C: LhaDecoderConfig, R: Read> LhaV2Decoder<C, R> {
60 pub fn new(rd: R) -> LhaV2Decoder<C, R> {
61 let bit_reader = BitStream::new(rd);
62 let ringbuf = Default::default();
63 let command_tree = HuffTree::with_capacity(NUM_COMMANDS * 2);
64 let offset_tree = HuffTree::with_capacity(NUM_TEMP_CODELEN * 2);
65 LhaV2Decoder {
66 bit_reader,
67 ringbuf,
68 command_tree,
69 offset_tree,
70 remaining_commands: 0,
71 copy_progress: None
72 }
73 }
74
75 // reads code length value, usually 0..=7 but might be higher
76 fn read_code_length(&mut self) -> LhaResult<u8, R> {
77 let mut len: u8 = self.bit_reader.read_bits(3)?;
78 if len == 7 {
79 while self.bit_reader.read_bit()? {
80 len = len.checked_add(1).ok_or_else(||
81 LhaError::Decompress("code length overflow"))?;
82 }
83 }
84 Ok(len)
85 }
86
87 // skip_range: 0, 1 or 2
88 fn read_code_skip(&mut self, skip_range: u16) -> LhaResult<usize, R> {
89 let (bits, increment) = match skip_range {
90 0 => return Ok(1),
91 1 => (4, 3), // 3..=18
92 _ => (9, 20), // 20..=531
93 };
94 self.bit_reader.read_bits(bits).map(|skip: usize| skip + increment)
95 }
96
97 fn read_temp_tree(&mut self) -> LhaResult<(), R> {
98 let mut code_lengths = [0u8; NUM_TEMP_CODELEN];
99
100 // number of codes to read
101 let num_codes: usize = self.bit_reader.read_bits(5)?;
102 // println!("num codes: {:?}", num_codes);
103
104 // single code only
105 if num_codes == 0 {
106 let code = self.bit_reader.read_bits(5)?;
107 self.offset_tree.set_single(code);
108 return Ok(());
109 }
110
111 if num_codes > NUM_TEMP_CODELEN {
112 return Err(LhaError::Decompress("temporary codelen table has invalid size"))
113 }
114
115 // read actual lengths
116 for p in code_lengths[0..num_codes.min(3)].iter_mut() {
117 *p = self.read_code_length()?;
118 // println!("length: {:?}", *p);
119 }
120 // 2-bit skip value follows
121 let skip: usize = self.bit_reader.read_bits(2)?;
122 // println!("skip: {:?}", skip);
123
124 if 3 + skip > num_codes {
125 return Err(LhaError::Decompress("temporary codelen table has invalid size"))}
126
127 for p in code_lengths[3 + skip..num_codes].iter_mut() {
128 *p = self.read_code_length()?;
129 // println!("length: {:?}", *p);
130 }
131
132 self.offset_tree.build_tree(&code_lengths[0..num_codes])
133 .map_err(LhaError::Decompress)?;
134 Ok(())
135 }
136
137 fn read_command_tree(&mut self) -> LhaResult<(), R> {
138 let mut code_lengths = [0u8; NUM_COMMANDS];
139
140 // number of codes to read
141 let num_codes: usize = self.bit_reader.read_bits(9)?;
142 // println!("num codes: {:?}", num_codes);
143
144 // single code only
145 if num_codes == 0 {
146 let code = self.bit_reader.read_bits(9)?;
147 self.command_tree.set_single(code);
148 return Ok(());
149 }
150
151 if num_codes > NUM_COMMANDS {
152 return Err(LhaError::Decompress("commands codelen table has invalid size"))
153 }
154
155 let mut index = 0;
156 'outer: while index < num_codes {
157 for (n, p) in code_lengths[index..num_codes].iter_mut().enumerate() {
158 match self.offset_tree.read_entry(&mut self.bit_reader)? {
159 skip_range @ 0..=2 => {
160 let skip_count = self.read_code_skip(skip_range)?;
161 // println!("n: {} skip: {}", n + index, skip_count);
162 index += n + skip_count;
163 continue 'outer;
164 }
165 code => {
166 *p = (code - 2) as u8;
167 // println!("n: {} value: {}", index + n, *p);
168 }
169 }
170 }
171 break;
172 }
173
174 self.command_tree.build_tree(&code_lengths[0..num_codes])
175 .map_err(LhaError::Decompress)?;
176 Ok(())
177 }
178
179 fn read_offset_tree(&mut self) -> LhaResult<(), R> {
180 debug_assert!(NUM_TEMP_CODELEN >= C::HISTORY_BITS as usize);
181 let mut code_lengths = [0u8; NUM_TEMP_CODELEN];
182
183 // number of codes to read
184 let num_codes: usize = self.bit_reader.read_bits(C::OFFSET_BITS)?;
185 // println!("num codes: {} bits: {}", num_codes, C::OFFSET_BITS);
186
187 // single code only
188 if num_codes == 0 {
189 let code = self.bit_reader.read_bits(C::OFFSET_BITS)?;
190 self.offset_tree.set_single(code);
191 return Ok(());
192 }
193
194 if num_codes > C::HISTORY_BITS as usize {
195 return Err(LhaError::Decompress("offset codelen table has invalid size"))
196 }
197
198 // read actual lengths
199 for p in code_lengths[0..num_codes].iter_mut() {
200 *p = self.read_code_length()?;
201 // println!("length: {}", *p);
202 }
203
204 self.offset_tree.build_tree(&code_lengths[0..num_codes])
205 .map_err(LhaError::Decompress)?;
206 Ok(())
207 }
208
209 fn begin_new_block(&mut self) -> LhaResult<(), R> {
210 self.remaining_commands = self.bit_reader.read_bits(16)?;
211 self.read_temp_tree()?;
212 self.read_command_tree()?;
213 self.read_offset_tree()
214 }
215
216 #[inline]
217 fn read_command(&mut self) -> LhaResult<u16, R> {
218 self.command_tree.read_entry(&mut self.bit_reader)
219 }
220
221 #[inline]
222 fn read_offset(&mut self) -> LhaResult<u32, R> {
223 match self.offset_tree.read_entry(&mut self.bit_reader)?.into() {
224 // bits => 0 -> 0
225 // bits => 1 -> 1
226 res @ 0..=1 => Ok(res),
227 // bits => 2 -> 1x
228 // bits => 3 -> 1xx
229 // bits => 4 -> 1xxx
230 bits => {
231 let res: u32 = self.bit_reader.read_bits(bits - 1)?;
232 Ok(res | (1 << (bits - 1)))
233 }
234 }
235 }
236
237 fn copy_from_history<'a, I: Iterator<Item=&'a mut u8> + ExactSizeIterator>(
238 &mut self,
239 target: I,
240 offset: usize,
241 count: usize
242 ) -> LhaResult<(), R>
243 {
244 let history_iter = self.ringbuf.iter_from_offset(offset);
245 let count_after = count - target.len().min(count);
246 for (t, s) in target.zip(history_iter).take(count) {
247 *t = s;
248 }
249 self.copy_progress = NonZeroU32::new(count_after as u32)
250 .map(|count| (offset as u32, count));
251 Ok(())
252 }
253
254 }
255
256 impl<C: LhaDecoderConfig, R: Read> Decoder<R> for LhaV2Decoder<C, R>
257 where R::Error: core::fmt::Debug
258 {
259 type Error = R::Error;
260
261 fn into_inner(self) -> R {
262 self.bit_reader.into_inner()
263 }
264
265 fn fill_buffer(&mut self, buf: &mut[u8]) -> LhaResult<(), R> {
266 let buflen = buf.len();
267 let mut target = buf.iter_mut();
268 if let Some((offset, count)) = self.copy_progress {
269 self.copy_from_history(&mut target,
270 offset as usize,
271 count.get() as usize)?;
272 }
273
274 while let Some(dst) = target.next() {
275 while self.remaining_commands == 0 {
276 self.begin_new_block()?;
277 }
278
279 self.remaining_commands -= 1;
280
281 match self.read_command()? {
282 code @ 0..=0xff => {
283 let value = code as u8;
284 *dst = value;
285 self.ringbuf.push(value);
286 }
287 count => {
288 let offset = self.read_offset()?;
289 let index = buflen - target.len() - 1;
290 target = buf[index..].iter_mut();
291 self.copy_from_history(&mut target,
292 offset as usize,
293 (count - 0x100 + 3).into())?;
294 }
295 }
296 }
297 Ok(())
298 }
299 }
300
301 #[cfg(feature = "std")]
302 #[cfg(test)]
303 mod tests {
304 use super::*;
305 use super::super::DecoderAny;
306 use std::fs;
307 use std::io;
308
309 #[test]
310 fn lhav2_works() {
311 println!("DecoderAny<Empty> {}", core::mem::size_of::<DecoderAny<io::Empty>>());
312 println!("DecoderAny<fs::File> {}", core::mem::size_of::<DecoderAny<fs::File>>());
313 println!("Lh7Decoder<Empty> {}", core::mem::size_of::<Lh7Decoder<io::Empty>>());
314 println!("Lh7Decoder<File> {}", core::mem::size_of::<Lh7Decoder<fs::File>>());
315 println!("BitStream<File> {}", core::mem::size_of::<BitStream<fs::File>>());
316 println!("HuffTree {}", core::mem::size_of::<HuffTree>());
317 println!("Option<(u32, NonZeroU32)> {}", core::mem::size_of::<Option<(u32, NonZeroU32)>>());
318 println!("Box<C::RingBuffer> {}", core::mem::size_of::<Box<<Lh7DecoderCfg as LhaDecoderConfig>::RingBuffer>>());
319 }
320 }