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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
extern crate alloc;
#[cfg(any(feature = "enc", feature = "dec"))]
use alloc::vec::Vec;
#[cfg(feature = "dec")]
use embark_format::Error;
// --- shared varint (Snappy uses little-endian base-128 for the preamble) ---
#[cfg(feature = "enc")]
fn put_uvarint(out: &mut Vec<u8>, mut v: u32) {
while v >= 0x80 {
out.push((v as u8) | 0x80);
v >>= 7;
}
out.push(v as u8);
}
#[cfg(feature = "dec")]
fn read_uvarint(input: &[u8]) -> Result<(u32, usize), Error> {
let mut value: u32 = 0;
for (i, &b) in input.iter().enumerate() {
// Four bytes carry 28 bits and the fifth has room for four more;
// anything above that would be shifted off the end of the `u32`.
if i == 5 || (i == 4 && b & 0x70 != 0) {
return Err(Error::Corrupt);
}
value |= u32::from(b & 0x7f) << (7 * i);
if b & 0x80 == 0 {
return Ok((value, i + 1));
}
}
Err(Error::Truncated)
}
// --- encoder: hash-based greedy match finder over the Snappy block format ---
#[cfg(feature = "enc")]
const MAX_OFFSET: usize = 1 << 16; // we emit 2-byte-offset copies only (simplest valid subset)
#[cfg(feature = "enc")]
pub(crate) fn compress(input: &[u8]) -> Vec<u8> {
let mut out = Vec::with_capacity(input.len() / 2 + 8);
put_uvarint(&mut out, input.len() as u32);
let n = input.len();
if n == 0 {
return out;
}
// Hash table of 4-byte sequences -> position.
let table_bits = 14;
let table_size = 1usize << table_bits;
let mut table = alloc::vec![usize::MAX; table_size];
let hash = |bytes: &[u8]| -> usize {
let x = u32::from_le_bytes([bytes[0], bytes[1], bytes[2], bytes[3]]);
(x.wrapping_mul(0x1e35a7bd) >> (32 - table_bits)) as usize
};
let mut lit_start = 0usize;
let mut i = 0usize;
while i + 4 <= n {
let h = hash(&input[i..]);
let cand = table[h];
table[h] = i;
let in_range = cand != usize::MAX && i - cand < MAX_OFFSET;
if in_range && input[cand..cand + 4] == input[i..i + 4] {
emit_literals(&mut out, &input[lit_start..i]);
let offset = i - cand;
// Extend the match.
let mut len = 4;
while i + len < n && input[cand + len] == input[i + len] {
len += 1;
}
emit_copy(&mut out, offset, len);
i += len;
lit_start = i;
} else {
i += 1;
}
}
emit_literals(&mut out, &input[lit_start..]);
out
}
#[cfg(feature = "enc")]
fn emit_literals(out: &mut Vec<u8>, lit: &[u8]) {
if lit.is_empty() {
return;
}
let n = lit.len() - 1;
if n < 60 {
out.push((n as u8) << 2); // tag 00, length-1 in upper 6 bits
} else {
// length-1 stored in following bytes; count how many bytes needed.
let mut bytes = [0u8; 4];
let mut count = 0;
let mut v = n as u32;
while v > 0 {
bytes[count] = v as u8;
v >>= 8;
count += 1;
}
out.push((59 + count as u8) << 2); // tag 00, 60..=63 => 1..=4 extra bytes
out.extend_from_slice(&bytes[..count]);
}
out.extend_from_slice(lit);
}
#[cfg(feature = "enc")]
fn emit_copy(out: &mut Vec<u8>, offset: usize, mut len: usize) {
// Emit as repeated 2-byte-offset copies (tag 10), max length 64 each.
while len > 0 {
let chunk = len.min(64);
out.push((0b10) | (((chunk - 1) as u8) << 2)); // tag 10, len-1 in bits 2..8
out.push((offset & 0xff) as u8);
out.push(((offset >> 8) & 0xff) as u8);
len -= chunk;
}
}
// --- decoder: full Snappy block format (handles all copy tag widths) ---
#[cfg(feature = "dec")]
pub(crate) fn decompress(input: &[u8], orig_len: usize) -> Result<Vec<u8>, Error> {
let (declared, mut pos) = read_uvarint(input)?;
if declared as usize != orig_len {
return Err(Error::Corrupt);
}
// `orig_len` is bounded to `u32::MAX` (~4 GiB) by the preamble varint
// above, but that is still an allocation an attacker can demand from a
// 5-byte input, and it is far more than the `no_std` targets this crate
// supports can ever satisfy.
// Reserve for what is plausible rather than for what is claimed. The
// claim is the attacker's; the buffer grows as real output arrives, and a
// claim the payload cannot honour ends as a decode failure below.
const EAGER: usize = 64 * 1024;
let mut out: Vec<u8> = Vec::new();
out.try_reserve(orig_len.min(EAGER))
.map_err(|_| Error::Corrupt)?;
while pos < input.len() {
let tag = input[pos];
pos += 1;
match tag & 0b11 {
0 => {
// literal
let mut len = (tag >> 2) as usize;
if len >= 60 {
let extra = len - 59;
if pos + extra > input.len() {
return Err(Error::Truncated);
}
let mut v = 0usize;
for k in 0..extra {
v |= (input[pos + k] as usize) << (8 * k);
}
pos += extra;
len = v;
}
// A four-byte stored length of `FF FF FF FF` is `usize::MAX`
// on a 32-bit target, where `+ 1` would wrap to zero and turn
// a truncated literal into a silently accepted empty one.
let len = len.checked_add(1).ok_or(Error::Corrupt)?;
if len > input.len() - pos {
return Err(Error::Truncated);
}
out.extend_from_slice(&input[pos..pos + len]);
pos += len;
}
1 => {
// copy, 1-byte offset (len 4..=11, 3-bit len, 11-bit offset)
let len = 4 + ((tag >> 2) & 0x7) as usize;
if pos >= input.len() {
return Err(Error::Truncated);
}
let offset = (((tag >> 5) as usize) << 8) | input[pos] as usize;
pos += 1;
copy_match(&mut out, offset, len)?;
}
2 => {
// copy, 2-byte offset
let len = 1 + (tag >> 2) as usize;
if pos + 2 > input.len() {
return Err(Error::Truncated);
}
let offset = input[pos] as usize | ((input[pos + 1] as usize) << 8);
pos += 2;
copy_match(&mut out, offset, len)?;
}
_ => {
// copy, 4-byte offset
let len = 1 + (tag >> 2) as usize;
if pos + 4 > input.len() {
return Err(Error::Truncated);
}
let offset = input[pos] as usize
| ((input[pos + 1] as usize) << 8)
| ((input[pos + 2] as usize) << 16)
| ((input[pos + 3] as usize) << 24);
pos += 4;
copy_match(&mut out, offset, len)?;
}
}
if out.len() > orig_len {
return Err(Error::Corrupt);
}
}
if out.len() != orig_len {
return Err(Error::Corrupt);
}
Ok(out)
}
#[cfg(feature = "dec")]
fn copy_match(out: &mut Vec<u8>, offset: usize, len: usize) -> Result<(), Error> {
if offset == 0 || offset > out.len() {
return Err(Error::Corrupt);
}
let start = out.len() - offset;
for k in 0..len {
let byte = out[start + k];
out.push(byte);
}
Ok(())
}
#[cfg(all(test, feature = "enc", feature = "dec"))]
mod tests {
use super::*;
fn rt(data: &[u8]) {
let c = compress(data);
assert_eq!(
decompress(&c, data.len()).unwrap(),
data,
"roundtrip mismatch"
);
}
#[test]
fn roundtrip_cases() {
rt(b"");
rt(b"a");
rt(b"hello hello hello hello world world world");
rt(&b"The quick brown fox jumps over the lazy dog. ".repeat(30));
rt(&(0u8..=255).collect::<alloc::vec::Vec<u8>>());
}
#[test]
fn preamble_encodes_length() {
// 300 bytes -> varint preamble 0xAC 0x02 at the front.
let c = compress(&[7u8; 300]);
assert_eq!(&c[..2], &[0xAC, 0x02]);
}
#[test]
fn truncated_is_error() {
assert!(decompress(&[0x04, 0xff], 4).is_err());
}
// A preamble that sets bits above the 32nd is not a length at all, so
// it is refused rather than read with those bits dropped.
#[test]
fn preamble_bits_past_the_thirty_second_are_corrupt() {
assert_eq!(
read_uvarint(&[0xff, 0xff, 0xff, 0xff, 0x0f]),
Ok((u32::MAX, 5))
);
assert_eq!(
read_uvarint(&[0xff, 0xff, 0xff, 0xff, 0x1f]),
Err(Error::Corrupt)
);
assert_eq!(
read_uvarint(&[0xff, 0xff, 0xff, 0xff, 0xff, 0x00]),
Err(Error::Corrupt)
);
}
#[test]
fn hostile_orig_len_does_not_over_allocate() {
// The preamble varint must equal `orig_len` exactly, which caps a
// claim at `u32::MAX` (~4 GiB) from a 5-byte input -- on a desktop
// with ample virtual memory, `Vec::with_capacity(u32::MAX)` tends to
// succeed and this already returned `Err` from the trailing
// length check, so this assertion alone does not distinguish the
// fix from the old code on every platform. It still guards the
// `no_std` targets this crate supports (this crate is verified
// against thumbv7em-none-eabihf, which cannot satisfy a 4 GiB
// request), where the old unconditional `with_capacity` aborts.
let hostile_orig_len = u32::MAX as usize;
let mut input = Vec::new();
put_uvarint(&mut input, hostile_orig_len as u32);
assert!(decompress(&input, hostile_orig_len).is_err());
}
#[test]
fn literal_length_at_usize_max_does_not_wrap() {
// A four-byte literal length of `FF FF FF FF` is `usize::MAX` on a
// 32-bit target once the format's stored `length - 1` is undone, so
// the `+ 1` must be checked. On a 64-bit target the same input is
// simply a truncated literal. Either way it must be an error, never
// an accepted zero-length literal.
// Tag 0xFC: literal, length field 63 -> four following length bytes.
let body: &[u8] = &[0x04, 0xFC, 0xFF, 0xFF, 0xFF, 0xFF];
assert!(decompress(body, 4).is_err());
}
#[test]
fn overgrowth_is_rejected() {
// Preamble declares orig_len = 4, then a 4-byte literal ("AAAA") fills
// it exactly, followed by a 2-byte-offset copy tag that would append
// 64 more bytes (offset 1, len 64) -- output would balloon to 68
// bytes despite the declared length of 4. Must be rejected before
// that growth completes, not just via the final length check.
let body: &[u8] = &[
0x04, // preamble: orig_len = 4
0x0C, // literal tag: len - 1 = 3 -> 4 literal bytes
b'A', b'A', b'A', b'A', // the literal
0xFE, // copy tag: 2-byte offset, len - 1 = 63 -> len = 64
0x01, 0x00, // offset = 1
];
assert!(decompress(body, 4).is_err());
}
}