]>
Commit | Line | Data |
---|---|---|
26c7fdad | 1 | // SPDX-License-Identifier: GPL 2.0+ OR BSD-2-Clause |
027b728d | 2 | /* |
26c7fdad HJ |
3 | * LZ4 - Fast LZ compression algorithm |
4 | * Copyright (C) 2011 - 2016, Yann Collet. | |
5 | * BSD 2 - Clause License (http://www.opensource.org/licenses/bsd - license.php) | |
6 | * Redistribution and use in source and binary forms, with or without | |
7 | * modification, are permitted provided that the following conditions are | |
8 | * met: | |
9 | * * Redistributions of source code must retain the above copyright | |
10 | * notice, this list of conditions and the following disclaimer. | |
11 | * * Redistributions in binary form must reproduce the above | |
12 | * copyright notice, this list of conditions and the following disclaimer | |
13 | * in the documentation and/or other materials provided with the | |
14 | * distribution. | |
15 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
16 | * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
17 | * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
18 | * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
19 | * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
20 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
21 | * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
22 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
23 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
24 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
25 | * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
26 | * You can contact the author at : | |
27 | * - LZ4 homepage : http://www.lz4.org | |
28 | * - LZ4 source repository : https://github.com/lz4/lz4 | |
29 | */ | |
26c7fdad HJ |
30 | #include <compiler.h> |
31 | #include <linux/kernel.h> | |
32 | #include <linux/types.h> | |
33 | #include <linux/bug.h> | |
34 | #include <asm/unaligned.h> | |
35 | #include <u-boot/lz4.h> | |
36 | ||
37 | #define FORCE_INLINE inline __attribute__((always_inline)) | |
38 | ||
39 | static FORCE_INLINE u16 LZ4_readLE16(const void *src) | |
40 | { | |
41 | return get_unaligned_le16(src); | |
42 | } | |
027b728d | 43 | |
26c7fdad HJ |
44 | static FORCE_INLINE void LZ4_copy8(void *dst, const void *src) |
45 | { | |
46 | put_unaligned(get_unaligned((const u64 *)src), (u64 *)dst); | |
47 | } | |
48 | ||
49 | typedef uint8_t BYTE; | |
50 | typedef uint16_t U16; | |
51 | typedef uint32_t U32; | |
52 | typedef int32_t S32; | |
53 | typedef uint64_t U64; | |
54 | typedef uintptr_t uptrval; | |
027b728d | 55 | |
26c7fdad HJ |
56 | static FORCE_INLINE void LZ4_write32(void *memPtr, U32 value) |
57 | { | |
58 | put_unaligned(value, (U32 *)memPtr); | |
59 | } | |
027b728d JW |
60 | |
61 | /************************************** | |
62 | * Reading and writing into memory | |
63 | **************************************/ | |
64 | ||
65 | /* customized version of memcpy, which may overwrite up to 7 bytes beyond dstEnd */ | |
66 | static void LZ4_wildCopy(void* dstPtr, const void* srcPtr, void* dstEnd) | |
67 | { | |
68 | BYTE* d = (BYTE*)dstPtr; | |
69 | const BYTE* s = (const BYTE*)srcPtr; | |
70 | BYTE* e = (BYTE*)dstEnd; | |
71 | do { LZ4_copy8(d,s); d+=8; s+=8; } while (d<e); | |
72 | } | |
73 | ||
74 | ||
75 | /************************************** | |
76 | * Common Constants | |
77 | **************************************/ | |
78 | #define MINMATCH 4 | |
79 | ||
26c7fdad | 80 | #define WILDCOPYLENGTH 8 |
027b728d | 81 | #define LASTLITERALS 5 |
26c7fdad | 82 | #define MFLIMIT (WILDCOPYLENGTH + MINMATCH) |
027b728d | 83 | |
26c7fdad HJ |
84 | /* |
85 | * ensure it's possible to write 2 x wildcopyLength | |
86 | * without overflowing output buffer | |
87 | */ | |
88 | #define MATCH_SAFEGUARD_DISTANCE ((2 * WILDCOPYLENGTH) - MINMATCH) | |
89 | ||
90 | #define KB (1 <<10) | |
027b728d JW |
91 | |
92 | #define MAXD_LOG 16 | |
93 | #define MAX_DISTANCE ((1 << MAXD_LOG) - 1) | |
94 | ||
95 | #define ML_BITS 4 | |
96 | #define ML_MASK ((1U<<ML_BITS)-1) | |
97 | #define RUN_BITS (8-ML_BITS) | |
98 | #define RUN_MASK ((1U<<RUN_BITS)-1) | |
99 | ||
26c7fdad | 100 | #define LZ4_STATIC_ASSERT(c) BUILD_BUG_ON(!(c)) |
027b728d JW |
101 | |
102 | /************************************** | |
103 | * Local Structures and types | |
104 | **************************************/ | |
105 | typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive; | |
106 | typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive; | |
26c7fdad | 107 | typedef enum { decode_full_block = 0, partial_decode = 1 } earlyEnd_directive; |
027b728d | 108 | |
26c7fdad | 109 | #define DEBUGLOG(l, ...) {} /* disabled */ |
027b728d | 110 | |
26c7fdad HJ |
111 | #ifndef assert |
112 | #define assert(condition) ((void)0) | |
113 | #endif | |
027b728d | 114 | |
027b728d | 115 | /* |
26c7fdad HJ |
116 | * LZ4_decompress_generic() : |
117 | * This generic decompression function covers all use cases. | |
118 | * It shall be instantiated several times, using different sets of directives. | |
119 | * Note that it is important for performance that this function really get inlined, | |
027b728d JW |
120 | * in order to remove useless branches during compilation optimization. |
121 | */ | |
26c7fdad HJ |
122 | static FORCE_INLINE int LZ4_decompress_generic( |
123 | const char * const src, | |
124 | char * const dst, | |
125 | int srcSize, | |
126 | /* | |
127 | * If endOnInput == endOnInputSize, | |
128 | * this value is `dstCapacity` | |
129 | */ | |
130 | int outputSize, | |
131 | /* endOnOutputSize, endOnInputSize */ | |
132 | endCondition_directive endOnInput, | |
133 | /* full, partial */ | |
134 | earlyEnd_directive partialDecoding, | |
135 | /* noDict, withPrefix64k, usingExtDict */ | |
136 | dict_directive dict, | |
137 | /* always <= dst, == dst when no prefix */ | |
138 | const BYTE * const lowPrefix, | |
139 | /* only if dict == usingExtDict */ | |
140 | const BYTE * const dictStart, | |
141 | /* note : = 0 if noDict */ | |
142 | const size_t dictSize | |
143 | ) | |
027b728d | 144 | { |
26c7fdad HJ |
145 | const BYTE *ip = (const BYTE *) src; |
146 | const BYTE * const iend = ip + srcSize; | |
147 | ||
148 | BYTE *op = (BYTE *) dst; | |
149 | BYTE * const oend = op + outputSize; | |
150 | BYTE *cpy; | |
151 | ||
152 | const BYTE * const dictEnd = (const BYTE *)dictStart + dictSize; | |
153 | static const unsigned int inc32table[8] = {0, 1, 2, 1, 0, 4, 4, 4}; | |
154 | static const int dec64table[8] = {0, 0, 0, -1, -4, 1, 2, 3}; | |
155 | ||
156 | const int safeDecode = (endOnInput == endOnInputSize); | |
157 | const int checkOffset = ((safeDecode) && (dictSize < (int)(64 * KB))); | |
158 | ||
159 | /* Set up the "end" pointers for the shortcut. */ | |
160 | const BYTE *const shortiend = iend - | |
161 | (endOnInput ? 14 : 8) /*maxLL*/ - 2 /*offset*/; | |
162 | const BYTE *const shortoend = oend - | |
163 | (endOnInput ? 14 : 8) /*maxLL*/ - 18 /*maxML*/; | |
164 | ||
165 | DEBUGLOG(5, "%s (srcSize:%i, dstSize:%i)", __func__, | |
166 | srcSize, outputSize); | |
167 | ||
168 | /* Special cases */ | |
169 | assert(lowPrefix <= op); | |
170 | assert(src != NULL); | |
171 | ||
172 | /* Empty output buffer */ | |
173 | if ((endOnInput) && (unlikely(outputSize == 0))) | |
174 | return ((srcSize == 1) && (*ip == 0)) ? 0 : -1; | |
175 | ||
176 | if ((!endOnInput) && (unlikely(outputSize == 0))) | |
177 | return (*ip == 0 ? 1 : -1); | |
178 | ||
179 | if ((endOnInput) && unlikely(srcSize == 0)) | |
180 | return -1; | |
181 | ||
182 | /* Main Loop : decode sequences */ | |
183 | while (1) { | |
184 | size_t length; | |
185 | const BYTE *match; | |
186 | size_t offset; | |
187 | ||
188 | /* get literal length */ | |
189 | unsigned int const token = *ip++; | |
190 | length = token>>ML_BITS; | |
191 | ||
192 | /* ip < iend before the increment */ | |
193 | assert(!endOnInput || ip <= iend); | |
194 | ||
195 | /* | |
196 | * A two-stage shortcut for the most common case: | |
197 | * 1) If the literal length is 0..14, and there is enough | |
198 | * space, enter the shortcut and copy 16 bytes on behalf | |
199 | * of the literals (in the fast mode, only 8 bytes can be | |
200 | * safely copied this way). | |
201 | * 2) Further if the match length is 4..18, copy 18 bytes | |
202 | * in a similar manner; but we ensure that there's enough | |
203 | * space in the output for those 18 bytes earlier, upon | |
204 | * entering the shortcut (in other words, there is a | |
205 | * combined check for both stages). | |
206 | * | |
207 | * The & in the likely() below is intentionally not && so that | |
208 | * some compilers can produce better parallelized runtime code | |
209 | */ | |
210 | if ((endOnInput ? length != RUN_MASK : length <= 8) | |
211 | /* | |
212 | * strictly "less than" on input, to re-enter | |
213 | * the loop with at least one byte | |
214 | */ | |
215 | && likely((endOnInput ? ip < shortiend : 1) & | |
216 | (op <= shortoend))) { | |
217 | /* Copy the literals */ | |
218 | memcpy(op, ip, endOnInput ? 16 : 8); | |
219 | op += length; ip += length; | |
220 | ||
221 | /* | |
222 | * The second stage: | |
223 | * prepare for match copying, decode full info. | |
224 | * If it doesn't work out, the info won't be wasted. | |
225 | */ | |
226 | length = token & ML_MASK; /* match length */ | |
227 | offset = LZ4_readLE16(ip); | |
228 | ip += 2; | |
229 | match = op - offset; | |
230 | assert(match <= op); /* check overflow */ | |
231 | ||
232 | /* Do not deal with overlapping matches. */ | |
233 | if ((length != ML_MASK) && | |
234 | (offset >= 8) && | |
235 | (dict == withPrefix64k || match >= lowPrefix)) { | |
236 | /* Copy the match. */ | |
237 | memcpy(op + 0, match + 0, 8); | |
238 | memcpy(op + 8, match + 8, 8); | |
239 | memcpy(op + 16, match + 16, 2); | |
240 | op += length + MINMATCH; | |
241 | /* Both stages worked, load the next token. */ | |
242 | continue; | |
243 | } | |
244 | ||
245 | /* | |
246 | * The second stage didn't work out, but the info | |
247 | * is ready. Propel it right to the point of match | |
248 | * copying. | |
249 | */ | |
250 | goto _copy_match; | |
251 | } | |
252 | ||
253 | /* decode literal length */ | |
254 | if (length == RUN_MASK) { | |
255 | unsigned int s; | |
256 | ||
257 | if (unlikely(endOnInput ? ip >= iend - RUN_MASK : 0)) { | |
258 | /* overflow detection */ | |
259 | goto _output_error; | |
260 | } | |
261 | do { | |
262 | s = *ip++; | |
263 | length += s; | |
264 | } while (likely(endOnInput | |
265 | ? ip < iend - RUN_MASK | |
266 | : 1) & (s == 255)); | |
267 | ||
268 | if ((safeDecode) | |
269 | && unlikely((uptrval)(op) + | |
270 | length < (uptrval)(op))) { | |
271 | /* overflow detection */ | |
272 | goto _output_error; | |
273 | } | |
274 | if ((safeDecode) | |
275 | && unlikely((uptrval)(ip) + | |
276 | length < (uptrval)(ip))) { | |
277 | /* overflow detection */ | |
278 | goto _output_error; | |
279 | } | |
280 | } | |
281 | ||
282 | /* copy literals */ | |
283 | cpy = op + length; | |
284 | LZ4_STATIC_ASSERT(MFLIMIT >= WILDCOPYLENGTH); | |
285 | ||
286 | if (((endOnInput) && ((cpy > oend - MFLIMIT) | |
287 | || (ip + length > iend - (2 + 1 + LASTLITERALS)))) | |
288 | || ((!endOnInput) && (cpy > oend - WILDCOPYLENGTH))) { | |
289 | if (partialDecoding) { | |
290 | if (cpy > oend) { | |
291 | /* | |
292 | * Partial decoding : | |
293 | * stop in the middle of literal segment | |
294 | */ | |
295 | cpy = oend; | |
296 | length = oend - op; | |
297 | } | |
298 | if ((endOnInput) | |
299 | && (ip + length > iend)) { | |
300 | /* | |
301 | * Error : | |
302 | * read attempt beyond | |
303 | * end of input buffer | |
304 | */ | |
305 | goto _output_error; | |
306 | } | |
307 | } else { | |
308 | if ((!endOnInput) | |
309 | && (cpy != oend)) { | |
310 | /* | |
311 | * Error : | |
312 | * block decoding must | |
313 | * stop exactly there | |
314 | */ | |
315 | goto _output_error; | |
316 | } | |
317 | if ((endOnInput) | |
318 | && ((ip + length != iend) | |
319 | || (cpy > oend))) { | |
320 | /* | |
321 | * Error : | |
322 | * input must be consumed | |
323 | */ | |
324 | goto _output_error; | |
325 | } | |
326 | } | |
327 | ||
328 | /* | |
329 | * supports overlapping memory regions; only matters | |
330 | * for in-place decompression scenarios | |
331 | */ | |
332 | memmove(op, ip, length); | |
333 | ip += length; | |
334 | op += length; | |
335 | ||
336 | /* Necessarily EOF, due to parsing restrictions */ | |
337 | if (!partialDecoding || (cpy == oend)) | |
338 | break; | |
339 | } else { | |
340 | /* may overwrite up to WILDCOPYLENGTH beyond cpy */ | |
341 | LZ4_wildCopy(op, ip, cpy); | |
342 | ip += length; | |
343 | op = cpy; | |
344 | } | |
345 | ||
346 | /* get offset */ | |
347 | offset = LZ4_readLE16(ip); | |
348 | ip += 2; | |
349 | match = op - offset; | |
350 | ||
351 | /* get matchlength */ | |
352 | length = token & ML_MASK; | |
353 | ||
354 | _copy_match: | |
355 | if ((checkOffset) && (unlikely(match + dictSize < lowPrefix))) { | |
356 | /* Error : offset outside buffers */ | |
357 | goto _output_error; | |
358 | } | |
359 | ||
360 | /* costs ~1%; silence an msan warning when offset == 0 */ | |
361 | /* | |
362 | * note : when partialDecoding, there is no guarantee that | |
363 | * at least 4 bytes remain available in output buffer | |
364 | */ | |
365 | if (!partialDecoding) { | |
366 | assert(oend > op); | |
367 | assert(oend - op >= 4); | |
368 | ||
369 | LZ4_write32(op, (U32)offset); | |
370 | } | |
371 | ||
372 | if (length == ML_MASK) { | |
373 | unsigned int s; | |
374 | ||
375 | do { | |
376 | s = *ip++; | |
377 | ||
378 | if ((endOnInput) && (ip > iend - LASTLITERALS)) | |
379 | goto _output_error; | |
380 | ||
381 | length += s; | |
382 | } while (s == 255); | |
383 | ||
384 | if ((safeDecode) | |
385 | && unlikely( | |
386 | (uptrval)(op) + length < (uptrval)op)) { | |
387 | /* overflow detection */ | |
388 | goto _output_error; | |
389 | } | |
390 | } | |
391 | ||
392 | length += MINMATCH; | |
393 | ||
394 | /* match starting within external dictionary */ | |
395 | if ((dict == usingExtDict) && (match < lowPrefix)) { | |
396 | if (unlikely(op + length > oend - LASTLITERALS)) { | |
397 | /* doesn't respect parsing restriction */ | |
398 | if (!partialDecoding) | |
399 | goto _output_error; | |
400 | length = min(length, (size_t)(oend - op)); | |
401 | } | |
402 | ||
403 | if (length <= (size_t)(lowPrefix - match)) { | |
404 | /* | |
405 | * match fits entirely within external | |
406 | * dictionary : just copy | |
407 | */ | |
408 | memmove(op, dictEnd - (lowPrefix - match), | |
409 | length); | |
410 | op += length; | |
411 | } else { | |
412 | /* | |
413 | * match stretches into both external | |
414 | * dictionary and current block | |
415 | */ | |
416 | size_t const copySize = (size_t)(lowPrefix - match); | |
417 | size_t const restSize = length - copySize; | |
418 | ||
419 | memcpy(op, dictEnd - copySize, copySize); | |
420 | op += copySize; | |
421 | if (restSize > (size_t)(op - lowPrefix)) { | |
422 | /* overlap copy */ | |
423 | BYTE * const endOfMatch = op + restSize; | |
424 | const BYTE *copyFrom = lowPrefix; | |
425 | ||
426 | while (op < endOfMatch) | |
427 | *op++ = *copyFrom++; | |
428 | } else { | |
429 | memcpy(op, lowPrefix, restSize); | |
430 | op += restSize; | |
431 | } | |
432 | } | |
433 | continue; | |
434 | } | |
435 | ||
436 | /* copy match within block */ | |
437 | cpy = op + length; | |
438 | ||
439 | /* | |
440 | * partialDecoding : | |
441 | * may not respect endBlock parsing restrictions | |
442 | */ | |
443 | assert(op <= oend); | |
444 | if (partialDecoding && | |
445 | (cpy > oend - MATCH_SAFEGUARD_DISTANCE)) { | |
446 | size_t const mlen = min(length, (size_t)(oend - op)); | |
447 | const BYTE * const matchEnd = match + mlen; | |
448 | BYTE * const copyEnd = op + mlen; | |
449 | ||
450 | if (matchEnd > op) { | |
451 | /* overlap copy */ | |
452 | while (op < copyEnd) | |
453 | *op++ = *match++; | |
454 | } else { | |
455 | memcpy(op, match, mlen); | |
456 | } | |
457 | op = copyEnd; | |
458 | if (op == oend) | |
459 | break; | |
460 | continue; | |
461 | } | |
462 | ||
463 | if (unlikely(offset < 8)) { | |
464 | op[0] = match[0]; | |
465 | op[1] = match[1]; | |
466 | op[2] = match[2]; | |
467 | op[3] = match[3]; | |
468 | match += inc32table[offset]; | |
469 | memcpy(op + 4, match, 4); | |
470 | match -= dec64table[offset]; | |
471 | } else { | |
472 | LZ4_copy8(op, match); | |
473 | match += 8; | |
474 | } | |
475 | ||
476 | op += 8; | |
477 | ||
478 | if (unlikely(cpy > oend - MATCH_SAFEGUARD_DISTANCE)) { | |
479 | BYTE * const oCopyLimit = oend - (WILDCOPYLENGTH - 1); | |
480 | ||
481 | if (cpy > oend - LASTLITERALS) { | |
482 | /* | |
483 | * Error : last LASTLITERALS bytes | |
484 | * must be literals (uncompressed) | |
485 | */ | |
486 | goto _output_error; | |
487 | } | |
488 | ||
489 | if (op < oCopyLimit) { | |
490 | LZ4_wildCopy(op, match, oCopyLimit); | |
491 | match += oCopyLimit - op; | |
492 | op = oCopyLimit; | |
493 | } | |
494 | while (op < cpy) | |
495 | *op++ = *match++; | |
496 | } else { | |
497 | LZ4_copy8(op, match); | |
498 | if (length > 16) | |
499 | LZ4_wildCopy(op + 8, match + 8, cpy); | |
500 | } | |
501 | op = cpy; /* wildcopy correction */ | |
502 | } | |
503 | ||
504 | /* end of decoding */ | |
505 | if (endOnInput) { | |
506 | /* Nb of output bytes decoded */ | |
507 | return (int) (((char *)op) - dst); | |
508 | } else { | |
509 | /* Nb of input bytes read */ | |
510 | return (int) (((const char *)ip) - src); | |
511 | } | |
512 | ||
513 | /* Overflow error detected */ | |
027b728d | 514 | _output_error: |
26c7fdad HJ |
515 | return (int) (-(((const char *)ip) - src)) - 1; |
516 | } | |
517 | ||
518 | int LZ4_decompress_safe(const char *source, char *dest, | |
519 | int compressedSize, int maxDecompressedSize) | |
520 | { | |
521 | return LZ4_decompress_generic(source, dest, | |
522 | compressedSize, maxDecompressedSize, | |
523 | endOnInputSize, decode_full_block, | |
524 | noDict, (BYTE *)dest, NULL, 0); | |
525 | } | |
526 | ||
527 | int LZ4_decompress_safe_partial(const char *src, char *dst, | |
528 | int compressedSize, int targetOutputSize, int dstCapacity) | |
529 | { | |
530 | dstCapacity = min(targetOutputSize, dstCapacity); | |
531 | return LZ4_decompress_generic(src, dst, compressedSize, dstCapacity, | |
532 | endOnInputSize, partial_decode, | |
533 | noDict, (BYTE *)dst, NULL, 0); | |
027b728d | 534 | } |