1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
//! Pure-Rust PalmDOC compression/decompression.
//!
//! PalmDOC uses a simple LZ77-style compression scheme with a sliding window.
use std::io;
/// Decompress PalmDOC data.
pub fn decompress(input: &[u8]) -> io::Result<Vec<u8>> {
let mut output = Vec::with_capacity(input.len() * 2);
let mut i = 0;
while i < input.len() {
let byte = input[i];
i += 1;
match byte {
// Literal byte
0x00 | 0x09..=0x7F => {
output.push(byte);
}
// Copy next 1-8 bytes literally
0x01..=0x08 => {
let count = byte as usize;
if i + count > input.len() {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
"PalmDoc: unexpected end of input",
));
}
output.extend_from_slice(&input[i..i + count]);
i += count;
}
// Back-reference: copy from sliding window
0x80..=0xBF => {
if i >= input.len() {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
"PalmDoc: unexpected end of input",
));
}
let next = input[i] as usize;
i += 1;
// Distance and length encoded in two bytes
let distance = (((byte as usize) & 0x3F) << 5) | (next >> 3);
let length = (next & 0x07) + 3;
if distance > output.len() || distance == 0 {
return Err(io::Error::new(
io::ErrorKind::InvalidData,
format!("PalmDoc: invalid back-reference distance {distance}"),
));
}
let start = output.len() - distance;
for j in 0..length {
output.push(output[start + (j % distance)]);
}
}
// Space + character
0xC0..=0xFF => {
output.push(b' ');
output.push(byte ^ 0x80);
}
}
}
Ok(output)
}
/// Hash function for 3-byte sequences
#[inline]
fn hash3(data: &[u8]) -> usize {
((data[0] as usize) << 16 | (data[1] as usize) << 8 | (data[2] as usize)) % HASH_SIZE
}
const HASH_SIZE: usize = 4096;
const MAX_DISTANCE: usize = 2047;
/// Compress data using PalmDOC compression with hash-based match finding.
pub fn compress(input: &[u8]) -> Vec<u8> {
let mut output = Vec::with_capacity(input.len());
let mut i = 0;
// Hash table: maps hash -> most recent position with that hash
let mut hash_table = [0usize; HASH_SIZE];
// Chain: for each position, points to previous position with same hash
let mut chain = vec![0usize; input.len()];
while i < input.len() {
let mut best_match_len = 0;
let mut best_match_dist = 0;
// Look for matches using hash table
if i + 3 <= input.len() {
let h = hash3(&input[i..]);
let mut pos = hash_table[h];
// Follow the hash chain to find matches
let min_pos = i.saturating_sub(MAX_DISTANCE);
let mut chain_len = 0;
while pos >= min_pos && pos < i && chain_len < 16 {
let dist = i - pos;
if dist <= MAX_DISTANCE {
// Check match length
let mut len = 0;
let max_len = (input.len() - i).min(10);
while len < max_len && input[pos + len] == input[i + len] {
len += 1;
}
if len >= 3 && len > best_match_len {
best_match_len = len;
best_match_dist = dist;
if len == 10 {
break; // Max match length reached
}
}
}
if pos == 0 {
break;
}
pos = chain[pos];
chain_len += 1;
}
// Update hash table and chain
chain[i] = hash_table[h];
hash_table[h] = i;
}
if best_match_len >= 3 {
// Encode back-reference
let len_code = (best_match_len - 3).min(7);
let dist_hi = (best_match_dist >> 5) & 0x3F;
let dist_lo = best_match_dist & 0x1F;
output.push(0x80 | dist_hi as u8);
output.push(((dist_lo << 3) | len_code) as u8);
// Update hash table for skipped positions
for j in 1..best_match_len {
if i + j + 3 <= input.len() {
let h = hash3(&input[i + j..]);
chain[i + j] = hash_table[h];
hash_table[h] = i + j;
}
}
i += best_match_len;
} else if input[i] == b' '
&& i + 1 < input.len()
&& input[i + 1] >= 0x40
&& input[i + 1] < 0x80
{
// Space + printable ASCII -> single byte encoding
output.push(input[i + 1] ^ 0x80);
i += 2;
} else if input[i] == 0 || (input[i] >= 0x09 && input[i] <= 0x7F) {
// Literal byte
output.push(input[i]);
i += 1;
} else {
// Byte needs literal escape (0x01-0x08 prefix)
let mut literal_run = Vec::new();
while i < input.len()
&& literal_run.len() < 8
&& !(input[i] == 0 || (input[i] >= 0x09 && input[i] <= 0x7F))
{
literal_run.push(input[i]);
i += 1;
}
if !literal_run.is_empty() {
output.push(literal_run.len() as u8);
output.extend_from_slice(&literal_run);
}
}
}
output
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_roundtrip() {
let original = b"Hello, this is a test of PalmDOC compression. This text has some repetition. This text has some repetition.";
let compressed = compress(original);
let decompressed = decompress(&compressed).unwrap();
assert_eq!(decompressed, original);
}
#[test]
fn test_space_encoding() {
let original = b"Hello World";
let compressed = compress(original);
let decompressed = decompress(&compressed).unwrap();
assert_eq!(decompressed, original);
}
}