Mercurial > touhou

annotate src/util/lzss.rs @ 664:f08e8e3c6196

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Use bitflags for the rank, instead of an u16.
author Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
date Sun, 11 Aug 2019 19:55:45 +0200
parents afa012bb8021
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;
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
4 use crate::util::bitstream::BitStream;
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::*;
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
47 use crate::util::SeekableSlice;
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.
afa012bb8021 Hello Rust!
Emmanuel Gil Peyrot <linkmauve@linkmauve.fr>
parents:
diff changeset
53 let data = SeekableSlice::new(&[0, 0, 0]);
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 }