Mercurial > touhou

annotate utils/src/lzss.rs @ 792:11bc22bad1bf default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
python: Replace the image crate with png We weren’t using any of its features anyway, so the png crate is exactly what we need, without the many heavy dependencies of image. https://github.com/image-rs/image-png/pull/670 will eventually make it even faster to build.
author Link Mauve <linkmauve@linkmauve.fr>
date Sat, 17 Jan 2026 22:22:25 +0100
parents daa23a4ff24d
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
637
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
1 //! LZSS implementation.
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
2
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
3 use std::io;
757
21b186be2590 Split the Rust version into multiple crates.
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents: 637
diff changeset
4 use crate::bitstream::BitStream;
637
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
5
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
6 /// Decompresses a LZSS-compressed file.
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
7 pub fn decompress<R: io::Read + io::Seek>(bitstream: &mut BitStream<R>, size: usize, dictionary_size: usize, offset_size: usize, length_size: usize, minimum_match_length: usize) -> io::Result<Vec<u8>> {
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
8 let mut data = vec![0; size];
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
9 let mut dictionary = vec![0; dictionary_size];
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
10 let mut dictionary_head = 1;
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
11 let mut ptr = 0;
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
12
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
13 while ptr < size {
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
14 if bitstream.read_bit()? {
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
15 // The `flag` bit is set, indicating the upcoming chunk of data is a literal.
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
16 // Add it to the uncompressed file, and store it in the dictionary.
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
17 let byte = bitstream.read(8)? as u8;
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
18 dictionary[dictionary_head] = byte;
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
19 dictionary_head = (dictionary_head + 1) % dictionary_size;
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
20 data[ptr] = byte;
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
21 ptr += 1;
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
22 } else {
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
23 // The `flag` bit is not set, the upcoming chunk is a (offset, length) tuple.
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
24 let offset = bitstream.read(offset_size)?;
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
25 let length = bitstream.read(length_size)? + minimum_match_length;
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
26 if ptr + length > size {
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
27 return Err(io::Error::new(io::ErrorKind::Other, "Oh no!"));
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
28 }
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
29 if offset == 0 && length == 0 {
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
30 break;
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
31 }
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
32 for i in offset..offset + length {
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
33 data[ptr] = dictionary[i % dictionary_size];
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
34 dictionary[dictionary_head] = dictionary[i % dictionary_size];
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
35 dictionary_head = (dictionary_head + 1) % dictionary_size;
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
36 ptr += 1;
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
37 }
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
38 }
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
39 }
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
40
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
41 Ok(data)
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
42 }
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
43
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
44 #[cfg(test)]
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
45 mod tests {
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
46 use super::*;
758
daa23a4ff24d utils: Replace custom SeekableSlice struct with std::io::Cursor.
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents: 757
diff changeset
47 use std::io::Cursor;
637
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
48
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
49 #[test]
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
50 #[ignore]
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
51 fn bit_by_bit() {
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
52 // TODO: find actual lzss data.
758
daa23a4ff24d utils: Replace custom SeekableSlice struct with std::io::Cursor.
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents: 757
diff changeset
53 let data = Cursor::new(vec![0, 0, 0]);
637
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
54 let mut bitstream = BitStream::new(data);
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
55 decompress(&mut bitstream, 3, 0x2000, 13, 4, 3).unwrap();
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
56 }
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
57 }