1use bytes::Bytes;
37
38use super::{BlockCodec, Codec, Decoded};
39use crate::budget::DecodeBuf;
40use crate::error::Error;
41
42#[derive(Clone, Copy, Debug, Default)]
44pub struct Lz4;
45
46const _: () = crate::send_sync::<Lz4>();
47
48impl BlockCodec for Lz4 {
49 fn decode(
62 &self,
63 input: &Bytes,
64 uncompressed: u32,
65 out: &mut DecodeBuf,
66 ) -> Result<Decoded, Error> {
67 let fail = |detail: String| Error::Decompress {
68 codec: Codec::Lz4,
69 detail: detail.into(),
70 };
71 let Ok(capacity) = i32::try_from(uncompressed) else {
72 return Err(fail(
73 "OverflowError: signed integer is greater than maximum".to_owned(),
74 ));
75 };
76 if i32::try_from(input.len()).is_err() {
77 return Err(fail(
78 "OverflowError: Input too large for LZ4 API".to_owned(),
79 ));
80 }
81 let capacity = usize::try_from(capacity).unwrap_or(0);
82 let lz4_error = |at: usize| {
83 fail(format!(
84 "LZ4BlockError: Decompression failed: corrupt input or insufficient space in \
85 destination buffer. Error code: {}",
86 at.saturating_add(1)
87 ))
88 };
89 let n = lz4_run(input, capacity, None).map_err(lz4_error)?;
90 let dst = out.grow_zeroed(n)?;
91 lz4_run(input, capacity, Some(dst)).map_err(lz4_error)?;
92 Ok(Decoded::Written)
93 }
94}
95
96const MINMATCH: usize = 4;
98const LASTLITERALS: usize = 5;
99const MFLIMIT: usize = 12;
100const FASTLOOP_SAFE_DISTANCE: usize = 64;
101const ML_MASK: usize = 15;
102const RUN_MASK: usize = 15;
103
104fn read_variable_length(
109 src: &[u8],
110 ip: &mut usize,
111 limit: isize,
112 initial_check: bool,
113) -> Option<usize> {
114 let past = |ip: usize| isize::try_from(ip).map_or(true, |i| i > limit);
115 if initial_check && isize::try_from(*ip).map_or(true, |i| i >= limit) {
116 return None;
117 }
118 let mut length = 0usize;
119 loop {
120 let s = *src.get(*ip)?;
121 *ip += 1;
122 length = length.saturating_add(usize::from(s));
123 if past(*ip) {
124 return None;
125 }
126 if s != 255 {
127 return Some(length);
128 }
129 }
130}
131
132fn copy_match(dst: &mut [u8], op: usize, offset: usize, length: usize) {
136 let end = op.saturating_add(length).min(dst.len());
137 if offset == 0 {
138 if let Some(d) = dst.get_mut(op..end) {
139 d.fill(0);
140 }
141 return;
142 }
143 let Some(src) = op.checked_sub(offset) else {
144 return;
145 };
146 let mut at = op;
147 while at < end {
148 let step = (at - src).min(end - at);
151 dst.copy_within(src..src + step, at);
152 at += step;
153 }
154}
155
156struct Lz4State<'a, 'o> {
159 src: &'a [u8],
160 dst: Option<&'o mut [u8]>,
161 ip: usize,
162 op: usize,
163 iend: isize,
165 oend: isize,
166}
167
168enum Lz4Entry {
170 Top,
172 Literals(usize, usize),
174 Match(usize, usize),
176}
177
178fn signed(n: usize) -> isize {
179 isize::try_from(n).unwrap_or(isize::MAX)
180}
181
182impl Lz4State<'_, '_> {
183 fn token(&mut self) -> Result<usize, usize> {
184 let t = self.src.get(self.ip).copied().ok_or(self.ip)?;
185 self.ip += 1;
186 Ok(usize::from(t))
187 }
188
189 fn le16(&mut self) -> Result<usize, usize> {
190 let b = self
191 .src
192 .get(self.ip..self.ip.saturating_add(2))
193 .and_then(|b| <[u8; 2]>::try_from(b).ok())
194 .ok_or(self.ip)?;
195 self.ip += 2;
196 Ok(usize::from(u16::from_le_bytes(b)))
197 }
198
199 fn varlen(&mut self, limit: isize, initial_check: bool) -> Result<usize, usize> {
200 read_variable_length(self.src, &mut self.ip, limit, initial_check).ok_or(self.ip)
201 }
202
203 fn literals(&mut self, n: usize) {
205 if let (Some(d), Some(from)) = (
206 self.dst.as_deref_mut(),
207 self.src.get(self.ip..self.ip.saturating_add(n)),
208 ) && let Some(to) = d.get_mut(self.op..self.op.saturating_add(n))
209 {
210 to.copy_from_slice(from);
211 }
212 self.ip = self.ip.saturating_add(n);
213 self.op = self.op.saturating_add(n);
214 }
215
216 fn copy(&mut self, offset: usize, n: usize) {
218 if let Some(d) = self.dst.as_deref_mut() {
219 copy_match(d, self.op, offset, n);
220 }
221 self.op = self.op.saturating_add(n);
222 }
223
224 fn match_length(&mut self, mlen: usize) -> Result<usize, usize> {
227 let mut length = mlen;
228 if length == ML_MASK {
229 length += self.varlen(self.iend - signed(LASTLITERALS) + 1, false)?;
230 }
231 Ok(length + MINMATCH)
232 }
233
234 fn safe_literals(
238 &mut self,
239 token: usize,
240 length: usize,
241 ) -> Result<Option<(usize, usize)>, usize> {
242 let cpy = signed(self.op).saturating_add(signed(length));
243 let lit_end = signed(self.ip).saturating_add(signed(length));
244 if cpy > self.oend - signed(MFLIMIT) || lit_end > self.iend - signed(2 + 1 + LASTLITERALS) {
245 if lit_end != self.iend || cpy > self.oend {
247 return Err(self.ip);
248 }
249 self.literals(length);
250 return Ok(None);
251 }
252 self.literals(length);
253 let offset = self.le16()?;
254 let length = self.match_length(token & ML_MASK)?;
255 Ok(Some((offset, length)))
256 }
257
258 fn fast_loop(&mut self) -> Result<Lz4Entry, usize> {
261 loop {
262 let token = self.token()?;
263 let mut length = token >> 4;
264 if length == RUN_MASK {
265 length += self.varlen(self.iend - signed(RUN_MASK), true)?;
266 if signed(self.op).saturating_add(signed(length)) > self.oend - 32
267 || signed(self.ip).saturating_add(signed(length)) > self.iend - 32
268 {
269 return Ok(Lz4Entry::Literals(token, length));
270 }
271 } else if signed(self.ip) > self.iend - (16 + 1) {
272 return Ok(Lz4Entry::Literals(token, length));
273 }
274 self.literals(length);
275 let offset = self.le16()?;
276 let mut length = token & ML_MASK;
277 if length == ML_MASK {
278 length += self.varlen(self.iend - signed(LASTLITERALS) + 1, false)? + MINMATCH;
279 if offset > self.op {
280 return Err(self.ip);
281 }
282 } else {
283 length += MINMATCH;
284 }
285 if signed(self.op).saturating_add(signed(length))
286 >= self.oend - signed(FASTLOOP_SAFE_DISTANCE)
287 {
288 return Ok(Lz4Entry::Match(offset, length));
289 }
290 if offset > self.op {
291 return Err(self.ip);
292 }
293 self.copy(offset, length);
294 }
295 }
296
297 fn safe_loop(&mut self, mut entry: Lz4Entry) -> Result<usize, usize> {
300 let short_in = self.iend - 14 - 2;
302 let short_out = self.oend - 14 - 18;
303 loop {
304 let (offset, length) = match std::mem::replace(&mut entry, Lz4Entry::Top) {
305 Lz4Entry::Match(offset, length) => (offset, length),
306 Lz4Entry::Literals(token, length) => match self.safe_literals(token, length)? {
307 Some(m) => m,
308 None => return Ok(self.op),
309 },
310 Lz4Entry::Top => {
311 let token = self.token()?;
312 let mut length = token >> 4;
313 if length != RUN_MASK
314 && signed(self.ip) < short_in
315 && signed(self.op) <= short_out
316 {
317 self.literals(length);
318 let mlen = token & ML_MASK;
319 let offset = self.le16()?;
320 if mlen != ML_MASK && offset >= 8 && offset <= self.op {
321 self.copy(offset, mlen + MINMATCH);
322 continue;
323 }
324 (offset, self.match_length(mlen)?)
325 } else {
326 if length == RUN_MASK {
327 length += self.varlen(self.iend - signed(RUN_MASK), true)?;
328 }
329 match self.safe_literals(token, length)? {
330 Some(m) => m,
331 None => return Ok(self.op),
332 }
333 }
334 }
335 };
336 if offset > self.op {
339 return Err(self.ip);
340 }
341 if signed(self.op).saturating_add(signed(length)) > self.oend - signed(LASTLITERALS) {
342 return Err(self.ip);
343 }
344 self.copy(offset, length);
345 }
346 }
347}
348
349fn lz4_run(src: &[u8], output_size: usize, dst: Option<&mut [u8]>) -> Result<usize, usize> {
361 if output_size == 0 {
362 return if src == [0] { Ok(0) } else { Err(0) };
363 }
364 if src.is_empty() {
365 return Err(0);
366 }
367 let mut st = Lz4State {
368 src,
369 dst,
370 ip: 0,
371 op: 0,
372 iend: signed(src.len()),
373 oend: signed(output_size),
374 };
375 let entry = if st.oend >= signed(FASTLOOP_SAFE_DISTANCE) {
376 st.fast_loop()?
377 } else {
378 Lz4Entry::Top
379 };
380 st.safe_loop(entry)
381}