sit_algos/
adcr_v1.rs

1use binrw::BinReaderExt;
2use std::io;
3
4#[derive(Debug, thiserror::Error)]
5pub enum Error {
6    #[error(transparent)]
7    Io(#[from] io::Error),
8
9    #[error(transparent)]
10    BinRw(#[from] binrw::Error),
11
12    #[error("Input data did not produce enough data and is likely cut-off or incomplete")]
13    NotEnoughInstructions,
14
15    #[error("Input would have produced more data than expected and was aborted")]
16    TooMuchOutput,
17
18    #[error("Invalid reference")]
19    BookmarkHasNotBeenSet,
20
21    #[error("Referenced dictionary entry does not exist")]
22    DictionaryOutOfBounds,
23
24    #[error("Unknown tree encoding")]
25    TreeEncodingUnknown,
26
27    #[error("Embedded tree is not properly encoded")]
28    InvalidTree,
29}
30
31struct CheckpointMap {
32    storage: [Option<usize>; 0x1000],
33    next: u8,
34}
35
36impl CheckpointMap {
37    fn new() -> CheckpointMap {
38        Self {
39            storage: [None; 0x1000],
40            next: 0,
41        }
42    }
43
44    fn add(&mut self, key: u16, value: usize) {
45        let index = self.next as usize + key as usize;
46        self.next = self.next.wrapping_add(1);
47        self.storage[index] = Some(value);
48    }
49
50    fn get(&mut self, key: u16) -> Option<usize> {
51        self.storage[key as usize]
52    }
53}
54
55enum Command {
56    Literal,
57    Reference,
58}
59
60struct CommandBuffer {
61    value: u16,
62    bits: u8,
63}
64
65impl CommandBuffer {
66    #[inline]
67    pub fn new() -> Self {
68        Self { value: 0, bits: 0 }
69    }
70
71    #[inline]
72    pub fn next(&mut self, mut reader: impl io::Read + io::Seek) -> Result<Command, Error> {
73        if self.is_empty() {
74            match reader.read_le() {
75                Ok(value) => {
76                    self.value = value;
77                    self.bits = 16
78                }
79                Err(e) if e.is_eof() => return Err(Error::NotEnoughInstructions),
80                Err(e) => return Err(Error::BinRw(e)),
81            }
82        }
83
84        let bitset = (self.value & 1) != 0;
85        self.bits -= 1;
86        self.value >>= 1;
87        Ok(if bitset {
88            Command::Reference
89        } else {
90            Command::Literal
91        })
92    }
93
94    #[inline]
95    fn is_empty(&self) -> bool {
96        self.bits == 0
97    }
98}
99
100pub fn decompress(
101    uncompressed_len: usize,
102    mut input: impl io::Read + io::Seek,
103) -> Result<Vec<u8>, Error> {
104    let mut output = vec![0u8; uncompressed_len];
105    let mut output_ptr: usize = 0;
106    let mut bookmark = CheckpointMap::new();
107    let mut cmd = CommandBuffer::new();
108
109    let mut streak = 0;
110
111    fn hash(output: &[u8], i: usize) -> u16 {
112        (output[i]
113            .wrapping_add(output[i - 1])
114            .wrapping_add(output[i - 2])
115            & 0x1e)
116            .cast_signed() as u16
117            * 0x80
118    }
119
120    loop {
121        if output_ptr == output.len() {
122            return Ok(output);
123        }
124
125        match cmd.next(&mut input)? {
126            Command::Literal => {
127                output[output_ptr] = input.read_be()?;
128                output_ptr += 1;
129                streak += 1;
130
131                if streak == 3 {
132                    let key = hash(&output, output_ptr - 1);
133                    bookmark.add(key, output_ptr - 3);
134                    streak = 2;
135                }
136            }
137            Command::Reference => {
138                let [b1, b2]: [u8; 2] = input.read_le()?;
139                let [b1, b2] = [b1 as u16, b2 as u16];
140                let count = (b1 & 0x0F) as usize + 3;
141                if output_ptr + count >= output.len() {
142                    return Err(Error::TooMuchOutput);
143                }
144
145                let key = ((b1 & 0xF0) << 4) | b2;
146                if let Some(offset) = bookmark.get(key) {
147                    for i in 0..(count) {
148                        output[output_ptr + i] = output[offset + i];
149                    }
150                } else {
151                    output[output_ptr..(output_ptr + count)].fill(0x20);
152                }
153
154                if streak > 0 {
155                    let key = hash(&output, output_ptr - streak + 2);
156                    bookmark.add(key, output_ptr - streak);
157                }
158
159                if streak == 2 {
160                    let key = hash(&output, output_ptr + 1);
161                    bookmark.add(key, output_ptr - 1);
162                }
163
164                bookmark.add((b1 & 0xF0) << 4, output_ptr);
165                output_ptr += count;
166                streak = 0;
167            }
168        }
169    }
170}
sit_algos/adcr_v1.rs

sit_algos/
adcr_v1.rs
