Debian Codegraph @

.cargo/vendor/bzip2-rs/src/block/mod.rs

raw
1 //! bzip2 low-level block APIs
2
3 use std::mem;
4
5 use tinyvec::ArrayVec;
6
7 pub use self::error::BlockError;
8 use crate::bitreader::BitReader;
9 #[cfg(target_pointer_width = "64")]
10 use crate::bitreader::CachedBitReader;
11 use crate::crc::Hasher;
12 use crate::header::Header;
13 use crate::huffman::HuffmanTree;
14 use crate::move_to_front::MoveToFrontDecoder;
15
16 mod bwt;
17 mod error;
18
19 const BLOCK_MAGIC: u64 = 0x314159265359;
20 const FINAL_MAGIC: u64 = 0x177245385090;
21
22 pub(crate) struct Block {
23 header: Header,
24
25 tt: Vec<u32>,
26 pre_rle_used: u32,
27 t_pos: u32,
28 last_byte: i16,
29 byte_repeats: u8,
30 repeats: u8,
31
32 hasher: Hasher,
33 expected_crc: u32,
34
35 state: State,
36 }
37
38 enum State {
39 ReadyForRead,
40 Reading,
41 NotReady,
42 }
43
44 impl Block {
45 pub fn new(header: Header) -> Self {
46 let max_blocksize = header.max_blocksize();
47
48 Self {
49 header,
50
51 tt: Vec::with_capacity(max_blocksize as usize),
52 pre_rle_used: 0,
53 t_pos: 0,
54 last_byte: -1,
55 byte_repeats: 0,
56 repeats: 0,
57
58 hasher: Hasher::new(),
59 expected_crc: 0,
60
61 state: State::NotReady,
62 }
63 }
64
65 pub fn is_ready_for_read(&self) -> bool {
66 match self.state {
67 State::ReadyForRead => true,
68 State::Reading | State::NotReady => false,
69 }
70 }
71
72 pub fn is_reading(&self) -> bool {
73 match self.state {
74 State::Reading => true,
75 State::ReadyForRead | State::NotReady => false,
76 }
77 }
78
79 pub fn is_not_ready(&self) -> bool {
80 match self.state {
81 State::NotReady => true,
82 State::ReadyForRead | State::Reading => false,
83 }
84 }
85
86 pub fn set_ready_for_read(&mut self) {
87 self.state = State::ReadyForRead;
88 }
89
90 pub fn read(
91 &mut self,
92 reader: &mut BitReader<'_>,
93 out: &mut [u8],
94 ) -> Result<usize, BlockError> {
95 match &self.state {
96 State::ReadyForRead => {
97 let magic = reader
98 .read_u64(48)
99 .ok_or_else(|| BlockError::new("next magic truncated"))?;
100 match magic {
101 BLOCK_MAGIC => {
102 self.read_block(reader)?;
103 self.state = State::Reading;
104
105 self.read(reader, out)
106 }
107 FINAL_MAGIC => {
108 let _crc = reader
109 .read_u32(32)
110 .ok_or_else(|| BlockError::new("whole stream crc truncated"))?;
111
112 // TODO: check whole stream crc
113
114 self.state = State::NotReady;
115 Ok(0)
116 }
117 _ => {
118 self.state = State::NotReady;
119 Err(BlockError::new("bad magic value found"))
120 }
121 }
122 }
123 State::Reading => {
124 let n = self.read_from_block(out)?;
125 if n == 0 && !out.is_empty() {
126 self.state = State::NotReady;
127 }
128
129 Ok(n)
130 }
131 State::NotReady => Err(BlockError::new("not ready")),
132 }
133 }
134
135 pub fn read_from_block(&mut self, out: &mut [u8]) -> Result<usize, BlockError> {
136 let mut read = 0;
137
138 while (self.repeats > 0 || self.pre_rle_used < (self.tt.len() as u32)) && read < out.len() {
139 if self.repeats > 0 {
140 out[read] = self.last_byte as u8;
141 read += 1;
142
143 self.repeats -= 1;
144 if self.repeats == 0 {
145 self.last_byte = -1;
146 }
147 continue;
148 }
149
150 self.t_pos = self.tt[self.t_pos as usize];
151 let b = self.t_pos as u8;
152 self.t_pos >>= 8;
153 self.pre_rle_used += 1;
154
155 if self.byte_repeats == 3 {
156 self.repeats = b;
157 self.byte_repeats = 0;
158 continue;
159 }
160
161 if self.last_byte == i16::from(b) {
162 self.byte_repeats += 1;
163 } else {
164 self.byte_repeats = 0;
165 }
166 self.last_byte = i16::from(b);
167
168 out[read] = b;
169 read += 1;
170 }
171
172 if read == 0 && !out.is_empty() {
173 self.state = State::NotReady;
174
175 let crc = self.hasher.finalyze();
176 return if self.expected_crc == crc {
177 Ok(0)
178 } else {
179 Err(BlockError::new("bad crc"))
180 };
181 }
182
183 self.hasher.update(&out[..read]);
184 Ok(read)
185 }
186
187 pub fn read_block(&mut self, reader: &mut BitReader<'_>) -> Result<(), BlockError> {
188 self.hasher = Hasher::new();
189 self.tt.clear();
190
191 self.expected_crc = reader
192 .read_u32(32)
193 .ok_or_else(|| BlockError::new("crc truncated"))?;
194
195 let randomised = reader
196 .read_bool()
197 .ok_or_else(|| BlockError::new("randomised truncated"))?;
198 if randomised {
199 return Err(BlockError::new("randomised expected to be 'normal'"));
200 }
201
202 let orig_ptr = reader
203 .read_u32(24)
204 .ok_or_else(|| BlockError::new("orig ptr truncated"))?;
205
206 let mut huffman_used_symbols = ArrayVec::<[u8; 16]>::new();
207 let mut huffman_used_bitmaps = ArrayVec::<[u8; 256]>::new();
208
209 for i in 0..16 {
210 if reader
211 .read_bool()
212 .ok_or_else(|| BlockError::new("symbol range truncated"))?
213 {
214 huffman_used_symbols.push(i);
215 }
216 }
217
218 for symbol_range in huffman_used_symbols {
219 for symbol in 0..16 {
220 if reader
221 .read_bool()
222 .ok_or_else(|| BlockError::new("symbol range truncated"))?
223 {
224 huffman_used_bitmaps.push(symbol_range * 16 + symbol);
225 }
226 }
227 }
228
229 if huffman_used_bitmaps.is_empty() {
230 return Err(BlockError::new("huffman no symbols in input"));
231 }
232
233 let huffman_groups = reader
234 .read_u8(3)
235 .ok_or_else(|| BlockError::new("huffmann groups truncated"))?;
236 if huffman_groups < 2 || huffman_groups > 6 {
237 return Err(BlockError::new("invalid number of huffman trees"));
238 }
239
240 let selectors_used = reader
241 .read_u16(15)
242 .ok_or_else(|| BlockError::new("selectors used truncated"))?;
243
244 #[cfg(feature = "nightly")]
245 let mut selectors_list = ArrayVec::<[u8; 18001]>::new();
246 #[cfg(feature = "nightly")]
247 selectors_list.set_len(usize::from(selectors_used));
248 #[cfg(not(feature = "nightly"))]
249 let mut selectors_list = vec![0u8; usize::from(selectors_used)];
250
251 let mut move_to_front_decoder = MoveToFrontDecoder::new();
252 for selector_item in selectors_list.iter_mut().rev() {
253 let mut trees = 0;
254
255 while reader
256 .read_bool()
257 .ok_or_else(|| BlockError::new("selector truncated"))?
258 {
259 trees += 1;
260
261 if trees >= huffman_groups {
262 return Err(BlockError::new("tree index too large"));
263 }
264 }
265
266 *selector_item = move_to_front_decoder.decode(trees);
267 }
268
269 // limited in lenght of huffman_used_symbols
270 let mut symbols = [0u8; 256];
271 symbols[..huffman_used_bitmaps.len()].copy_from_slice(&huffman_used_bitmaps);
272 let mut move_to_front_decoder_2 = MoveToFrontDecoder::new_from_symbols(symbols);
273
274 let mut huffman_trees = ArrayVec::<[HuffmanTree; 6]>::new();
275
276 let mut lengths = ArrayVec::<[u8; crate::LEN_258]>::new();
277 lengths.set_len(huffman_used_bitmaps.len() + 2);
278
279 for _ in 0..huffman_groups {
280 let mut length = reader
281 .read_u8(5)
282 .ok_or_else(|| BlockError::new("huffman group length truncated"))?;
283
284 for length_item in &mut *lengths {
285 loop {
286 if length < 1 || length > 20 {
287 return Err(BlockError::new("huffman length out of range"));
288 }
289
290 if !reader
291 .read_bool()
292 .ok_or_else(|| BlockError::new("length bit1 truncated"))?
293 {
294 break;
295 }
296
297 if reader
298 .read_bool()
299 .ok_or_else(|| BlockError::new("length bit2 truncated"))?
300 {
301 length -= 1;
302 } else {
303 length += 1;
304 }
305 }
306
307 *length_item = length;
308 }
309
310 let tree = HuffmanTree::new(&lengths).map_err(BlockError::new)?;
311 huffman_trees.push(tree);
312 }
313
314 let selector = selectors_list
315 .pop()
316 .ok_or_else(|| BlockError::new("no tree selectors given"))?;
317 let mut current_huffman_tree = huffman_trees
318 .get(usize::from(selector))
319 .ok_or_else(|| BlockError::new("tree selector out of range"))?;
320
321 let mut repeat = 0u32;
322 let mut repeat_power = 0u32;
323 let mut c = [0u32; 256];
324
325 let mut decoded = 0;
326 #[cfg(target_pointer_width = "64")]
327 let mut r = CachedBitReader::new(reader)
328 .ok_or_else(|| BlockError::new("huffman bitstream truncated"))?;
329 loop {
330 if decoded == 50 {
331 let selector = selectors_list.pop().ok_or_else(|| {
332 BlockError::new("insufficient selector indices for number of symbols")
333 })?;
334
335 current_huffman_tree = huffman_trees
336 .get(usize::from(selector))
337 .ok_or_else(|| BlockError::new("tree selector out of range"))?;
338 decoded = 0;
339 }
340
341 #[cfg(target_pointer_width = "64")]
342 let v = {
343 let read = r.read();
344 let v = current_huffman_tree.decode(&mut r);
345
346 if r.overflowed() {
347 r.restore(reader, read);
348 r.refresh(reader)
349 .ok_or_else(|| BlockError::new("huffman bitstream truncated"))?;
350
351 current_huffman_tree.decode(&mut r)
352 } else {
353 v
354 }
355 };
356 #[cfg(not(target_pointer_width = "64"))]
357 let v = current_huffman_tree.decode(reader);
358
359 let v = v.ok_or_else(|| BlockError::new("huffman bitstream truncated"))?;
360 decoded += 1;
361
362 if v < 2 {
363 if repeat == 0 {
364 repeat_power = 1;
365 }
366 repeat += repeat_power << v;
367 repeat_power <<= 1;
368
369 if repeat > 2 * 1024 * 1024 {
370 return Err(BlockError::new("repeat count too large"));
371 }
372 continue;
373 }
374
375 let old_repeat = mem::replace(&mut repeat, 0);
376 if old_repeat > 0 {
377 if old_repeat > self.header.max_blocksize() - (self.tt.len() as u32) {
378 return Err(BlockError::new("repeats past end of block"));
379 }
380
381 let b = move_to_front_decoder_2.first();
382 // extend self.tt with `b` repeated `old_repeat` times
383 let new_len = self.tt.len() + old_repeat as usize;
384 self.tt.resize(new_len, u32::from(b));
385 c[usize::from(b)] += old_repeat;
386 }
387
388 if usize::from(v) == (huffman_used_bitmaps.len() + 2) - 1 {
389 break;
390 }
391
392 let b = move_to_front_decoder_2.decode((v - 1) as u8);
393 if self.tt.len() >= self.header.max_blocksize() as usize {
394 return Err(BlockError::new("data exceeds block size"));
395 }
396
397 self.tt.push(u32::from(b));
398 c[usize::from(b)] += 1;
399 }
400 #[cfg(target_pointer_width = "64")]
401 r.restore(reader, r.read());
402
403 if (orig_ptr as usize) >= self.tt.len() {
404 return Err(BlockError::new("orig_ptr out of bounds"));
405 }
406
407 self.pre_rle_used = 0;
408 self.t_pos = bwt::inverse_bwt(&mut self.tt, orig_ptr as usize, c);
409 self.last_byte = -1;
410 self.byte_repeats = 0;
411 self.repeats = 0;
412
413 Ok(())
414 }
415 }
416
417 #[cfg(test)]
418 mod tests {
419 use std::convert::TryInto;
420
421 use super::*;
422
423 #[test]
424 fn decode1() {
425 let compressed = include_bytes!("../../tests/samplefiles/sample1.bz2");
426 let decompressed = include_bytes!("../../tests/samplefiles/sample1.ref");
427
428 let header = Header::parse(compressed[..4].try_into().unwrap()).unwrap();
429 println!("block_size: {}", header.raw_blocksize());
430
431 let compressed = &compressed[4..];
432
433 let mut bits = BitReader::new(&compressed);
434 let mut reader = Block::new(header);
435
436 let mut out = vec![0u8; decompressed.len()];
437
438 reader.set_ready_for_read();
439 let read = reader.read(&mut bits, &mut out).unwrap();
440 assert_eq!(&out[..read], decompressed.as_ref());
441 }
442
443 #[test]
444 fn decode2() {
445 let compressed = include_bytes!("../../tests/samplefiles/sample2.bz2");
446 let decompressed = include_bytes!("../../tests/samplefiles/sample2.ref");
447
448 let header = Header::parse(compressed[..4].try_into().unwrap()).unwrap();
449 println!("block_size: {}", header.raw_blocksize());
450
451 let compressed = &compressed[4..];
452
453 let mut bits = BitReader::new(&compressed);
454 let mut reader = Block::new(header);
455
456 let mut out = vec![0u8; decompressed.len()];
457
458 reader.set_ready_for_read();
459 let read1 = reader.read(&mut bits, &mut out).unwrap();
460 reader.set_ready_for_read();
461 let read2 = reader.read(&mut bits, &mut out[read1..]).unwrap();
462 assert_eq!(&out[..read1 + read2], decompressed.as_ref());
463 }
464
465 #[test]
466 fn decode3() {
467 let compressed = include_bytes!("../../tests/samplefiles/sample3.bz2");
468 let decompressed = include_bytes!("../../tests/samplefiles/sample3.ref");
469
470 let header = Header::parse(compressed[..4].try_into().unwrap()).unwrap();
471 println!("block_size: {}", header.raw_blocksize());
472
473 let compressed = &compressed[4..];
474
475 let mut bits = BitReader::new(&compressed);
476 let mut reader = Block::new(header);
477
478 let mut out = vec![0u8; decompressed.len()];
479
480 reader.set_ready_for_read();
481 let read = reader.read(&mut bits, &mut out).unwrap();
482 assert_eq!(&out[..read], decompressed.as_ref());
483 }
484 }