1 /* 2 * LZ4 - Fast LZ compression algorithm 3 * Copyright (C) 2011 - 2016, Yann Collet. 4 * BSD 2 - Clause License (http://www.opensource.org/licenses/bsd - license.php) 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: 8 * * Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * * Redistributions in binary form must reproduce the above 11 * copyright notice, this list of conditions and the following disclaimer 12 * in the documentation and/or other materials provided with the 13 * distribution. 14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 15 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 16 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 17 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 18 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 19 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 20 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25 * You can contact the author at : 26 * - LZ4 homepage : http://www.lz4.org 27 * - LZ4 source repository : https://github.com/lz4/lz4 28 * 29 * Changed for kernel usage by: 30 * Sven Schmidt <4sschmid@informatik.uni-hamburg.de> 31 */ 32 33 /*-************************************ 34 * Dependencies 35 **************************************/ 36 #include <linux/lz4.h> 37 #include "lz4defs.h" 38 #include <linux/init.h> 39 #include <linux/module.h> 40 #include <linux/kernel.h> 41 #include <asm/unaligned.h> 42 43 /*-***************************** 44 * Decompression functions 45 *******************************/ 46 /* LZ4_decompress_generic() : 47 * This generic decompression function cover all use cases. 48 * It shall be instantiated several times, using different sets of directives 49 * Note that it is important this generic function is really inlined, 50 * in order to remove useless branches during compilation optimization. 51 */ 52 static FORCE_INLINE int LZ4_decompress_generic( 53 const char * const source, 54 char * const dest, 55 int inputSize, 56 /* 57 * If endOnInput == endOnInputSize, 58 * this value is the max size of Output Buffer. 59 */ 60 int outputSize, 61 /* endOnOutputSize, endOnInputSize */ 62 int endOnInput, 63 /* full, partial */ 64 int partialDecoding, 65 /* only used if partialDecoding == partial */ 66 int targetOutputSize, 67 /* noDict, withPrefix64k, usingExtDict */ 68 int dict, 69 /* == dest when no prefix */ 70 const BYTE * const lowPrefix, 71 /* only if dict == usingExtDict */ 72 const BYTE * const dictStart, 73 /* note : = 0 if noDict */ 74 const size_t dictSize 75 ) 76 { 77 /* Local Variables */ 78 const BYTE *ip = (const BYTE *) source; 79 const BYTE * const iend = ip + inputSize; 80 81 BYTE *op = (BYTE *) dest; 82 BYTE * const oend = op + outputSize; 83 BYTE *cpy; 84 BYTE *oexit = op + targetOutputSize; 85 const BYTE * const lowLimit = lowPrefix - dictSize; 86 87 const BYTE * const dictEnd = (const BYTE *)dictStart + dictSize; 88 static const unsigned int dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; 89 static const int dec64table[] = { 0, 0, 0, -1, 0, 1, 2, 3 }; 90 91 const int safeDecode = (endOnInput == endOnInputSize); 92 const int checkOffset = ((safeDecode) && (dictSize < (int)(64 * KB))); 93 94 /* Special cases */ 95 /* targetOutputSize too high => decode everything */ 96 if ((partialDecoding) && (oexit > oend - MFLIMIT)) 97 oexit = oend - MFLIMIT; 98 99 /* Empty output buffer */ 100 if ((endOnInput) && (unlikely(outputSize == 0))) 101 return ((inputSize == 1) && (*ip == 0)) ? 0 : -1; 102 103 if ((!endOnInput) && (unlikely(outputSize == 0))) 104 return (*ip == 0 ? 1 : -1); 105 106 /* Main Loop : decode sequences */ 107 while (1) { 108 size_t length; 109 const BYTE *match; 110 size_t offset; 111 112 /* get literal length */ 113 unsigned int const token = *ip++; 114 115 length = token>>ML_BITS; 116 117 if (length == RUN_MASK) { 118 unsigned int s; 119 120 do { 121 s = *ip++; 122 length += s; 123 } while (likely(endOnInput 124 ? ip < iend - RUN_MASK 125 : 1) & (s == 255)); 126 127 if ((safeDecode) 128 && unlikely( 129 (size_t)(op + length) < (size_t)(op))) { 130 /* overflow detection */ 131 goto _output_error; 132 } 133 if ((safeDecode) 134 && unlikely( 135 (size_t)(ip + length) < (size_t)(ip))) { 136 /* overflow detection */ 137 goto _output_error; 138 } 139 } 140 141 /* copy literals */ 142 cpy = op + length; 143 if (((endOnInput) && ((cpy > (partialDecoding ? oexit : oend - MFLIMIT)) 144 || (ip + length > iend - (2 + 1 + LASTLITERALS)))) 145 || ((!endOnInput) && (cpy > oend - WILDCOPYLENGTH))) { 146 if (partialDecoding) { 147 if (cpy > oend) { 148 /* 149 * Error : 150 * write attempt beyond end of output buffer 151 */ 152 goto _output_error; 153 } 154 if ((endOnInput) 155 && (ip + length > iend)) { 156 /* 157 * Error : 158 * read attempt beyond 159 * end of input buffer 160 */ 161 goto _output_error; 162 } 163 } else { 164 if ((!endOnInput) 165 && (cpy != oend)) { 166 /* 167 * Error : 168 * block decoding must 169 * stop exactly there 170 */ 171 goto _output_error; 172 } 173 if ((endOnInput) 174 && ((ip + length != iend) 175 || (cpy > oend))) { 176 /* 177 * Error : 178 * input must be consumed 179 */ 180 goto _output_error; 181 } 182 } 183 184 memcpy(op, ip, length); 185 ip += length; 186 op += length; 187 /* Necessarily EOF, due to parsing restrictions */ 188 break; 189 } 190 191 LZ4_wildCopy(op, ip, cpy); 192 ip += length; 193 op = cpy; 194 195 /* get offset */ 196 offset = LZ4_readLE16(ip); 197 ip += 2; 198 match = op - offset; 199 200 if ((checkOffset) && (unlikely(match < lowLimit))) { 201 /* Error : offset outside buffers */ 202 goto _output_error; 203 } 204 205 /* costs ~1%; silence an msan warning when offset == 0 */ 206 LZ4_write32(op, (U32)offset); 207 208 /* get matchlength */ 209 length = token & ML_MASK; 210 if (length == ML_MASK) { 211 unsigned int s; 212 213 do { 214 s = *ip++; 215 216 if ((endOnInput) && (ip > iend - LASTLITERALS)) 217 goto _output_error; 218 219 length += s; 220 } while (s == 255); 221 222 if ((safeDecode) 223 && unlikely( 224 (size_t)(op + length) < (size_t)op)) { 225 /* overflow detection */ 226 goto _output_error; 227 } 228 } 229 230 length += MINMATCH; 231 232 /* check external dictionary */ 233 if ((dict == usingExtDict) && (match < lowPrefix)) { 234 if (unlikely(op + length > oend - LASTLITERALS)) { 235 /* doesn't respect parsing restriction */ 236 goto _output_error; 237 } 238 239 if (length <= (size_t)(lowPrefix - match)) { 240 /* 241 * match can be copied as a single segment 242 * from external dictionary 243 */ 244 memmove(op, dictEnd - (lowPrefix - match), 245 length); 246 op += length; 247 } else { 248 /* 249 * match encompass external 250 * dictionary and current block 251 */ 252 size_t const copySize = (size_t)(lowPrefix - match); 253 size_t const restSize = length - copySize; 254 255 memcpy(op, dictEnd - copySize, copySize); 256 op += copySize; 257 258 if (restSize > (size_t)(op - lowPrefix)) { 259 /* overlap copy */ 260 BYTE * const endOfMatch = op + restSize; 261 const BYTE *copyFrom = lowPrefix; 262 263 while (op < endOfMatch) 264 *op++ = *copyFrom++; 265 } else { 266 memcpy(op, lowPrefix, restSize); 267 op += restSize; 268 } 269 } 270 271 continue; 272 } 273 274 /* copy match within block */ 275 cpy = op + length; 276 277 if (unlikely(offset < 8)) { 278 const int dec64 = dec64table[offset]; 279 280 op[0] = match[0]; 281 op[1] = match[1]; 282 op[2] = match[2]; 283 op[3] = match[3]; 284 match += dec32table[offset]; 285 memcpy(op + 4, match, 4); 286 match -= dec64; 287 } else { 288 LZ4_copy8(op, match); 289 match += 8; 290 } 291 292 op += 8; 293 294 if (unlikely(cpy > oend - 12)) { 295 BYTE * const oCopyLimit = oend - (WILDCOPYLENGTH - 1); 296 297 if (cpy > oend - LASTLITERALS) { 298 /* 299 * Error : last LASTLITERALS bytes 300 * must be literals (uncompressed) 301 */ 302 goto _output_error; 303 } 304 305 if (op < oCopyLimit) { 306 LZ4_wildCopy(op, match, oCopyLimit); 307 match += oCopyLimit - op; 308 op = oCopyLimit; 309 } 310 311 while (op < cpy) 312 *op++ = *match++; 313 } else { 314 LZ4_copy8(op, match); 315 316 if (length > 16) 317 LZ4_wildCopy(op + 8, match + 8, cpy); 318 } 319 320 op = cpy; /* correction */ 321 } 322 323 /* end of decoding */ 324 if (endOnInput) { 325 /* Nb of output bytes decoded */ 326 return (int) (((char *)op) - dest); 327 } else { 328 /* Nb of input bytes read */ 329 return (int) (((const char *)ip) - source); 330 } 331 332 /* Overflow error detected */ 333 _output_error: 334 return -1; 335 } 336 337 int LZ4_decompress_safe(const char *source, char *dest, 338 int compressedSize, int maxDecompressedSize) 339 { 340 return LZ4_decompress_generic(source, dest, compressedSize, 341 maxDecompressedSize, endOnInputSize, full, 0, 342 noDict, (BYTE *)dest, NULL, 0); 343 } 344 345 int LZ4_decompress_safe_partial(const char *source, char *dest, 346 int compressedSize, int targetOutputSize, int maxDecompressedSize) 347 { 348 return LZ4_decompress_generic(source, dest, compressedSize, 349 maxDecompressedSize, endOnInputSize, partial, 350 targetOutputSize, noDict, (BYTE *)dest, NULL, 0); 351 } 352 353 int LZ4_decompress_fast(const char *source, char *dest, int originalSize) 354 { 355 return LZ4_decompress_generic(source, dest, 0, originalSize, 356 endOnOutputSize, full, 0, withPrefix64k, 357 (BYTE *)(dest - 64 * KB), NULL, 64 * KB); 358 } 359 360 int LZ4_setStreamDecode(LZ4_streamDecode_t *LZ4_streamDecode, 361 const char *dictionary, int dictSize) 362 { 363 LZ4_streamDecode_t_internal *lz4sd = (LZ4_streamDecode_t_internal *) LZ4_streamDecode; 364 365 lz4sd->prefixSize = (size_t) dictSize; 366 lz4sd->prefixEnd = (const BYTE *) dictionary + dictSize; 367 lz4sd->externalDict = NULL; 368 lz4sd->extDictSize = 0; 369 return 1; 370 } 371 372 /* 373 * *_continue() : 374 * These decoding functions allow decompression of multiple blocks 375 * in "streaming" mode. 376 * Previously decoded blocks must still be available at the memory 377 * position where they were decoded. 378 * If it's not possible, save the relevant part of 379 * decoded data into a safe buffer, 380 * and indicate where it stands using LZ4_setStreamDecode() 381 */ 382 int LZ4_decompress_safe_continue(LZ4_streamDecode_t *LZ4_streamDecode, 383 const char *source, char *dest, int compressedSize, int maxOutputSize) 384 { 385 LZ4_streamDecode_t_internal *lz4sd = &LZ4_streamDecode->internal_donotuse; 386 int result; 387 388 if (lz4sd->prefixEnd == (BYTE *)dest) { 389 result = LZ4_decompress_generic(source, dest, 390 compressedSize, 391 maxOutputSize, 392 endOnInputSize, full, 0, 393 usingExtDict, lz4sd->prefixEnd - lz4sd->prefixSize, 394 lz4sd->externalDict, 395 lz4sd->extDictSize); 396 397 if (result <= 0) 398 return result; 399 400 lz4sd->prefixSize += result; 401 lz4sd->prefixEnd += result; 402 } else { 403 lz4sd->extDictSize = lz4sd->prefixSize; 404 lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize; 405 result = LZ4_decompress_generic(source, dest, 406 compressedSize, maxOutputSize, 407 endOnInputSize, full, 0, 408 usingExtDict, (BYTE *)dest, 409 lz4sd->externalDict, lz4sd->extDictSize); 410 if (result <= 0) 411 return result; 412 lz4sd->prefixSize = result; 413 lz4sd->prefixEnd = (BYTE *)dest + result; 414 } 415 416 return result; 417 } 418 419 int LZ4_decompress_fast_continue(LZ4_streamDecode_t *LZ4_streamDecode, 420 const char *source, char *dest, int originalSize) 421 { 422 LZ4_streamDecode_t_internal *lz4sd = &LZ4_streamDecode->internal_donotuse; 423 int result; 424 425 if (lz4sd->prefixEnd == (BYTE *)dest) { 426 result = LZ4_decompress_generic(source, dest, 0, originalSize, 427 endOnOutputSize, full, 0, 428 usingExtDict, 429 lz4sd->prefixEnd - lz4sd->prefixSize, 430 lz4sd->externalDict, lz4sd->extDictSize); 431 432 if (result <= 0) 433 return result; 434 435 lz4sd->prefixSize += originalSize; 436 lz4sd->prefixEnd += originalSize; 437 } else { 438 lz4sd->extDictSize = lz4sd->prefixSize; 439 lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize; 440 result = LZ4_decompress_generic(source, dest, 0, originalSize, 441 endOnOutputSize, full, 0, 442 usingExtDict, (BYTE *)dest, 443 lz4sd->externalDict, lz4sd->extDictSize); 444 if (result <= 0) 445 return result; 446 lz4sd->prefixSize = originalSize; 447 lz4sd->prefixEnd = (BYTE *)dest + originalSize; 448 } 449 450 return result; 451 } 452 453 /* 454 * Advanced decoding functions : 455 * *_usingDict() : 456 * These decoding functions work the same as "_continue" ones, 457 * the dictionary must be explicitly provided within parameters 458 */ 459 static FORCE_INLINE int LZ4_decompress_usingDict_generic(const char *source, 460 char *dest, int compressedSize, int maxOutputSize, int safe, 461 const char *dictStart, int dictSize) 462 { 463 if (dictSize == 0) 464 return LZ4_decompress_generic(source, dest, 465 compressedSize, maxOutputSize, safe, full, 0, 466 noDict, (BYTE *)dest, NULL, 0); 467 if (dictStart + dictSize == dest) { 468 if (dictSize >= (int)(64 * KB - 1)) 469 return LZ4_decompress_generic(source, dest, 470 compressedSize, maxOutputSize, safe, full, 0, 471 withPrefix64k, (BYTE *)dest - 64 * KB, NULL, 0); 472 return LZ4_decompress_generic(source, dest, compressedSize, 473 maxOutputSize, safe, full, 0, noDict, 474 (BYTE *)dest - dictSize, NULL, 0); 475 } 476 return LZ4_decompress_generic(source, dest, compressedSize, 477 maxOutputSize, safe, full, 0, usingExtDict, 478 (BYTE *)dest, (const BYTE *)dictStart, dictSize); 479 } 480 481 int LZ4_decompress_safe_usingDict(const char *source, char *dest, 482 int compressedSize, int maxOutputSize, 483 const char *dictStart, int dictSize) 484 { 485 return LZ4_decompress_usingDict_generic(source, dest, 486 compressedSize, maxOutputSize, 1, dictStart, dictSize); 487 } 488 489 int LZ4_decompress_fast_usingDict(const char *source, char *dest, 490 int originalSize, const char *dictStart, int dictSize) 491 { 492 return LZ4_decompress_usingDict_generic(source, dest, 0, 493 originalSize, 0, dictStart, dictSize); 494 } 495 496 #ifndef STATIC 497 EXPORT_SYMBOL(LZ4_decompress_safe); 498 EXPORT_SYMBOL(LZ4_decompress_safe_partial); 499 EXPORT_SYMBOL(LZ4_decompress_fast); 500 EXPORT_SYMBOL(LZ4_setStreamDecode); 501 EXPORT_SYMBOL(LZ4_decompress_safe_continue); 502 EXPORT_SYMBOL(LZ4_decompress_fast_continue); 503 EXPORT_SYMBOL(LZ4_decompress_safe_usingDict); 504 EXPORT_SYMBOL(LZ4_decompress_fast_usingDict); 505 506 MODULE_LICENSE("Dual BSD/GPL"); 507 MODULE_DESCRIPTION("LZ4 decompressor"); 508 #endif 509