diff options
Diffstat (limited to 'lib/lz4/lz4_decompress.c')
| -rw-r--r-- | lib/lz4/lz4_decompress.c | 705 |
1 files changed, 456 insertions, 249 deletions
diff --git a/lib/lz4/lz4_decompress.c b/lib/lz4/lz4_decompress.c index 6d940c72b5fc..b5e00a19a7b4 100644 --- a/lib/lz4/lz4_decompress.c +++ b/lib/lz4/lz4_decompress.c @@ -1,25 +1,16 @@ /* - * LZ4 Decompressor for Linux kernel - * - * Copyright (C) 2013, LG Electronics, Kyungsik Lee <kyungsik.lee@lge.com> - * - * Based on LZ4 implementation by Yann Collet. - * * LZ4 - Fast LZ compression algorithm - * Copyright (C) 2011-2012, Yann Collet. - * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) - * + * Copyright (C) 2011 - 2016, Yann Collet. + * BSD 2 - Clause License (http://www.opensource.org/licenses/bsd - license.php) * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are * met: - * - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * * Redistributions in binary form must reproduce the above + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above * copyright notice, this list of conditions and the following disclaimer * in the documentation and/or other materials provided with the * distribution. - * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR @@ -31,313 +22,529 @@ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * You can contact the author at : + * - LZ4 homepage : http://www.lz4.org + * - LZ4 source repository : https://github.com/lz4/lz4 * - * You can contact the author at : - * - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html - * - LZ4 source repository : http://code.google.com/p/lz4/ + * Changed for kernel usage by: + * Sven Schmidt <4sschmid@informatik.uni-hamburg.de> */ -#ifndef STATIC +/*-************************************ + * Dependencies + **************************************/ +#include <linux/lz4.h> +#include "lz4defs.h" +#include <linux/init.h> #include <linux/module.h> #include <linux/kernel.h> -#endif -#include <linux/lz4.h> - #include <asm/unaligned.h> -#include "lz4defs.h" - -static const int dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0}; -#if LZ4_ARCH64 -static const int dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3}; -#endif - -static int lz4_uncompress(const char *source, char *dest, int osize) +/*-***************************** + * Decompression functions + *******************************/ +/* LZ4_decompress_generic() : + * This generic decompression function cover all use cases. + * It shall be instantiated several times, using different sets of directives + * Note that it is important this generic function is really inlined, + * in order to remove useless branches during compilation optimization. + */ +static FORCE_INLINE int LZ4_decompress_generic( + const char * const source, + char * const dest, + int inputSize, + /* + * If endOnInput == endOnInputSize, + * this value is the max size of Output Buffer. + */ + int outputSize, + /* endOnOutputSize, endOnInputSize */ + int endOnInput, + /* full, partial */ + int partialDecoding, + /* only used if partialDecoding == partial */ + int targetOutputSize, + /* noDict, withPrefix64k, usingExtDict */ + int dict, + /* == dest when no prefix */ + const BYTE * const lowPrefix, + /* only if dict == usingExtDict */ + const BYTE * const dictStart, + /* note : = 0 if noDict */ + const size_t dictSize + ) { + /* Local Variables */ const BYTE *ip = (const BYTE *) source; - const BYTE *ref; + const BYTE * const iend = ip + inputSize; + BYTE *op = (BYTE *) dest; - BYTE * const oend = op + osize; + BYTE * const oend = op + outputSize; BYTE *cpy; - unsigned token; - size_t length; + BYTE *oexit = op + targetOutputSize; + const BYTE * const lowLimit = lowPrefix - dictSize; + + const BYTE * const dictEnd = (const BYTE *)dictStart + dictSize; + const unsigned int dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; + const int dec64table[] = { 0, 0, 0, -1, 0, 1, 2, 3 }; + const int safeDecode = (endOnInput == endOnInputSize); + const int checkOffset = ((safeDecode) && (dictSize < (int)(64 * KB))); + + /* Special cases */ + /* targetOutputSize too high => decode everything */ + if ((partialDecoding) && (oexit > oend - MFLIMIT)) + oexit = oend - MFLIMIT; + + /* Empty output buffer */ + if ((endOnInput) && (unlikely(outputSize == 0))) + return ((inputSize == 1) && (*ip == 0)) ? 0 : -1; + + if ((!endOnInput) && (unlikely(outputSize == 0))) + return (*ip == 0 ? 1 : -1); + + /* Main Loop : decode sequences */ while (1) { + size_t length; + const BYTE *match; + size_t offset; + + /* get literal length */ + unsigned int const token = *ip++; + + length = token>>ML_BITS; - /* get runlength */ - token = *ip++; - length = (token >> ML_BITS); if (length == RUN_MASK) { - size_t len; + unsigned int s; - len = *ip++; - for (; len == 255; length += 255) - len = *ip++; - if (unlikely(length > (size_t)(length + len))) + do { + s = *ip++; + length += s; + } while (likely(endOnInput + ? ip < iend - RUN_MASK + : 1) & (s == 255)); + + if ((safeDecode) + && unlikely( + (size_t)(op + length) < (size_t)(op))) { + /* overflow detection */ goto _output_error; - length += len; + } + if ((safeDecode) + && unlikely( + (size_t)(ip + length) < (size_t)(ip))) { + /* overflow detection */ + goto _output_error; + } } /* copy literals */ cpy = op + length; - if (unlikely(cpy > oend - COPYLENGTH)) { - /* - * Error: not enough place for another match - * (min 4) + 5 literals - */ - if (cpy != oend) - goto _output_error; + if (((endOnInput) && ((cpy > (partialDecoding ? oexit : oend - MFLIMIT)) + || (ip + length > iend - (2 + 1 + LASTLITERALS)))) + || ((!endOnInput) && (cpy > oend - WILDCOPYLENGTH))) { + if (partialDecoding) { + if (cpy > oend) { + /* + * Error : + * write attempt beyond end of output buffer + */ + goto _output_error; + } + if ((endOnInput) + && (ip + length > iend)) { + /* + * Error : + * read attempt beyond + * end of input buffer + */ + goto _output_error; + } + } else { + if ((!endOnInput) + && (cpy != oend)) { + /* + * Error : + * block decoding must + * stop exactly there + */ + goto _output_error; + } + if ((endOnInput) + && ((ip + length != iend) + || (cpy > oend))) { + /* + * Error : + * input must be consumed + */ + goto _output_error; + } + } memcpy(op, ip, length); ip += length; - break; /* EOF */ + op += length; + /* Necessarily EOF, due to parsing restrictions */ + break; } - LZ4_WILDCOPY(ip, op, cpy); - ip -= (op - cpy); + + LZ4_wildCopy(op, ip, cpy); + ip += length; op = cpy; /* get offset */ - LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip); + offset = LZ4_readLE16(ip); ip += 2; + match = op - offset; - /* Error: offset create reference outside destination buffer */ - if (unlikely(ref < (BYTE *const) dest)) + if ((checkOffset) && (unlikely(match < lowLimit))) { + /* Error : offset outside buffers */ goto _output_error; + } + + /* costs ~1%; silence an msan warning when offset == 0 */ + LZ4_write32(op, (U32)offset); /* get matchlength */ length = token & ML_MASK; if (length == ML_MASK) { - for (; *ip == 255; length += 255) - ip++; - if (unlikely(length > (size_t)(length + *ip))) + unsigned int s; + + do { + s = *ip++; + + if ((endOnInput) && (ip > iend - LASTLITERALS)) + goto _output_error; + + length += s; + } while (s == 255); + + if ((safeDecode) + && unlikely( + (size_t)(op + length) < (size_t)op)) { + /* overflow detection */ goto _output_error; - length += *ip++; + } } - /* copy repeated sequence */ - if (unlikely((op - ref) < STEPSIZE)) { -#if LZ4_ARCH64 - int dec64 = dec64table[op - ref]; -#else - const int dec64 = 0; -#endif - op[0] = ref[0]; - op[1] = ref[1]; - op[2] = ref[2]; - op[3] = ref[3]; - op += 4; - ref += 4; - ref -= dec32table[op-ref]; - PUT4(ref, op); - op += STEPSIZE - 4; - ref -= dec64; + length += MINMATCH; + + /* check external dictionary */ + if ((dict == usingExtDict) && (match < lowPrefix)) { + if (unlikely(op + length > oend - LASTLITERALS)) { + /* doesn't respect parsing restriction */ + goto _output_error; + } + + if (length <= (size_t)(lowPrefix - match)) { + /* + * match can be copied as a single segment + * from external dictionary + */ + memmove(op, dictEnd - (lowPrefix - match), + length); + op += length; + } else { + /* + * match encompass external + * dictionary and current block + */ + size_t const copySize = (size_t)(lowPrefix - match); + size_t const restSize = length - copySize; + + memcpy(op, dictEnd - copySize, copySize); + op += copySize; + + if (restSize > (size_t)(op - lowPrefix)) { + /* overlap copy */ + BYTE * const endOfMatch = op + restSize; + const BYTE *copyFrom = lowPrefix; + + while (op < endOfMatch) + *op++ = *copyFrom++; + } else { + memcpy(op, lowPrefix, restSize); + op += restSize; + } + } + + continue; + } + + /* copy match within block */ + cpy = op + length; + + if (unlikely(offset < 8)) { + const int dec64 = dec64table[offset]; + + op[0] = match[0]; + op[1] = match[1]; + op[2] = match[2]; + op[3] = match[3]; + match += dec32table[offset]; + memcpy(op + 4, match, 4); + match -= dec64; } else { - LZ4_COPYSTEP(ref, op); + LZ4_copy8(op, match); + match += 8; } - cpy = op + length - (STEPSIZE - 4); - if (cpy > (oend - COPYLENGTH)) { - /* Error: request to write beyond destination buffer */ - if (cpy > oend) - goto _output_error; -#if LZ4_ARCH64 - if ((ref + COPYLENGTH) > oend) -#else - if ((ref + COPYLENGTH) > oend || - (op + COPYLENGTH) > oend) -#endif + op += 8; + + if (unlikely(cpy > oend - 12)) { + BYTE * const oCopyLimit = oend - (WILDCOPYLENGTH - 1); + + if (cpy > oend - LASTLITERALS) { + /* + * Error : last LASTLITERALS bytes + * must be literals (uncompressed) + */ goto _output_error; - LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH)); + } + + if (op < oCopyLimit) { + LZ4_wildCopy(op, match, oCopyLimit); + match += oCopyLimit - op; + op = oCopyLimit; + } + while (op < cpy) - *op++ = *ref++; - op = cpy; - /* - * Check EOF (should never happen, since last 5 bytes - * are supposed to be literals) - */ - if (op == oend) - goto _output_error; - continue; + *op++ = *match++; + } else { + LZ4_copy8(op, match); + + if (length > 16) + LZ4_wildCopy(op + 8, match + 8, cpy); } - LZ4_SECURECOPY(ref, op, cpy); + op = cpy; /* correction */ } + /* end of decoding */ - return (int) (((char *)ip) - source); + if (endOnInput) { + /* Nb of output bytes decoded */ + return (int) (((char *)op) - dest); + } else { + /* Nb of input bytes read */ + return (int) (((const char *)ip) - source); + } - /* write overflow error detected */ + /* Overflow error detected */ _output_error: return -1; } -static int lz4_uncompress_unknownoutputsize(const char *source, char *dest, - int isize, size_t maxoutputsize) +int LZ4_decompress_safe(const char *source, char *dest, + int compressedSize, int maxDecompressedSize) { - const BYTE *ip = (const BYTE *) source; - const BYTE *const iend = ip + isize; - const BYTE *ref; - + return LZ4_decompress_generic(source, dest, compressedSize, + maxDecompressedSize, endOnInputSize, full, 0, + noDict, (BYTE *)dest, NULL, 0); +} - BYTE *op = (BYTE *) dest; - BYTE * const oend = op + maxoutputsize; - BYTE *cpy; +int LZ4_decompress_safe_partial(const char *source, char *dest, + int compressedSize, int targetOutputSize, int maxDecompressedSize) +{ + return LZ4_decompress_generic(source, dest, compressedSize, + maxDecompressedSize, endOnInputSize, partial, + targetOutputSize, noDict, (BYTE *)dest, NULL, 0); +} - /* Main Loop */ - while (ip < iend) { +int LZ4_decompress_fast(const char *source, char *dest, int originalSize) +{ + return LZ4_decompress_generic(source, dest, 0, originalSize, + endOnOutputSize, full, 0, withPrefix64k, + (BYTE *)(dest - 64 * KB), NULL, 64 * KB); +} - unsigned token; - size_t length; +int LZ4_setStreamDecode(LZ4_streamDecode_t *LZ4_streamDecode, + const char *dictionary, int dictSize) +{ + LZ4_streamDecode_t_internal *lz4sd = (LZ4_streamDecode_t_internal *) LZ4_streamDecode; - /* get runlength */ - token = *ip++; - length = (token >> ML_BITS); - if (length == RUN_MASK) { - int s = 255; - while ((ip < iend) && (s == 255)) { - s = *ip++; - if (unlikely(length > (size_t)(length + s))) - goto _output_error; - length += s; - } - } - /* copy literals */ - cpy = op + length; - if ((cpy > oend - COPYLENGTH) || - (ip + length > iend - COPYLENGTH)) { - - if (cpy > oend) - goto _output_error;/* writes beyond buffer */ - - if (ip + length != iend) - goto _output_error;/* - * Error: LZ4 format requires - * to consume all input - * at this stage - */ - memcpy(op, ip, length); - op += length; - break;/* Necessarily EOF, due to parsing restrictions */ - } - LZ4_WILDCOPY(ip, op, cpy); - ip -= (op - cpy); - op = cpy; + lz4sd->prefixSize = (size_t) dictSize; + lz4sd->prefixEnd = (const BYTE *) dictionary + dictSize; + lz4sd->externalDict = NULL; + lz4sd->extDictSize = 0; + return 1; +} - /* get offset */ - LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip); - ip += 2; - if (ref < (BYTE * const) dest) - goto _output_error; - /* - * Error : offset creates reference - * outside of destination buffer - */ +/* + * *_continue() : + * These decoding functions allow decompression of multiple blocks + * in "streaming" mode. + * Previously decoded blocks must still be available at the memory + * position where they were decoded. + * If it's not possible, save the relevant part of + * decoded data into a safe buffer, + * and indicate where it stands using LZ4_setStreamDecode() + */ +int LZ4_decompress_safe_continue(LZ4_streamDecode_t *LZ4_streamDecode, + const char *source, char *dest, int compressedSize, int maxOutputSize) +{ + LZ4_streamDecode_t_internal *lz4sd = &LZ4_streamDecode->internal_donotuse; + int result; + + if (lz4sd->prefixEnd == (BYTE *)dest) { + result = LZ4_decompress_generic(source, dest, + compressedSize, + maxOutputSize, + endOnInputSize, full, 0, + usingExtDict, lz4sd->prefixEnd - lz4sd->prefixSize, + lz4sd->externalDict, + lz4sd->extDictSize); + + if (result <= 0) + return result; + + lz4sd->prefixSize += result; + lz4sd->prefixEnd += result; + } else { + lz4sd->extDictSize = lz4sd->prefixSize; + lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize; + result = LZ4_decompress_generic(source, dest, + compressedSize, maxOutputSize, + endOnInputSize, full, 0, + usingExtDict, (BYTE *)dest, + lz4sd->externalDict, lz4sd->extDictSize); + if (result <= 0) + return result; + lz4sd->prefixSize = result; + lz4sd->prefixEnd = (BYTE *)dest + result; + } - /* get matchlength */ - length = (token & ML_MASK); - if (length == ML_MASK) { - while (ip < iend) { - int s = *ip++; - if (unlikely(length > (size_t)(length + s))) - goto _output_error; - length += s; - if (s == 255) - continue; - break; - } - } + return result; +} - /* copy repeated sequence */ - if (unlikely((op - ref) < STEPSIZE)) { -#if LZ4_ARCH64 - int dec64 = dec64table[op - ref]; -#else - const int dec64 = 0; -#endif - op[0] = ref[0]; - op[1] = ref[1]; - op[2] = ref[2]; - op[3] = ref[3]; - op += 4; - ref += 4; - ref -= dec32table[op - ref]; - PUT4(ref, op); - op += STEPSIZE - 4; - ref -= dec64; - } else { - LZ4_COPYSTEP(ref, op); - } - cpy = op + length - (STEPSIZE-4); - if (cpy > oend - COPYLENGTH) { - if (cpy > oend) - goto _output_error; /* write outside of buf */ -#if LZ4_ARCH64 - if ((ref + COPYLENGTH) > oend) -#else - if ((ref + COPYLENGTH) > oend || - (op + COPYLENGTH) > oend) -#endif - goto _output_error; - LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH)); - while (op < cpy) - *op++ = *ref++; - op = cpy; - /* - * Check EOF (should never happen, since last 5 bytes - * are supposed to be literals) - */ - if (op == oend) - goto _output_error; - continue; - } - LZ4_SECURECOPY(ref, op, cpy); - op = cpy; /* correction */ +int LZ4_decompress_fast_continue(LZ4_streamDecode_t *LZ4_streamDecode, + const char *source, char *dest, int originalSize) +{ + LZ4_streamDecode_t_internal *lz4sd = &LZ4_streamDecode->internal_donotuse; + int result; + + if (lz4sd->prefixEnd == (BYTE *)dest) { + result = LZ4_decompress_generic(source, dest, 0, originalSize, + endOnOutputSize, full, 0, + usingExtDict, + lz4sd->prefixEnd - lz4sd->prefixSize, + lz4sd->externalDict, lz4sd->extDictSize); + + if (result <= 0) + return result; + + lz4sd->prefixSize += originalSize; + lz4sd->prefixEnd += originalSize; + } else { + lz4sd->extDictSize = lz4sd->prefixSize; + lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize; + result = LZ4_decompress_generic(source, dest, 0, originalSize, + endOnOutputSize, full, 0, + usingExtDict, (BYTE *)dest, + lz4sd->externalDict, lz4sd->extDictSize); + if (result <= 0) + return result; + lz4sd->prefixSize = originalSize; + lz4sd->prefixEnd = (BYTE *)dest + originalSize; } - /* end of decoding */ - return (int) (((char *) op) - dest); - /* write overflow error detected */ -_output_error: - return -1; + return result; } -int lz4_decompress(const unsigned char *src, size_t *src_len, - unsigned char *dest, size_t actual_dest_len) +/* + * Advanced decoding functions : + * *_usingDict() : + * These decoding functions work the same as "_continue" ones, + * the dictionary must be explicitly provided within parameters + */ +static FORCE_INLINE int LZ4_decompress_usingDict_generic(const char *source, + char *dest, int compressedSize, int maxOutputSize, int safe, + const char *dictStart, int dictSize) { - int ret = -1; - int input_len = 0; - - input_len = lz4_uncompress(src, dest, actual_dest_len); - if (input_len < 0) - goto exit_0; - *src_len = input_len; + if (dictSize == 0) + return LZ4_decompress_generic(source, dest, + compressedSize, maxOutputSize, safe, full, 0, + noDict, (BYTE *)dest, NULL, 0); + if (dictStart + dictSize == dest) { + if (dictSize >= (int)(64 * KB - 1)) + return LZ4_decompress_generic(source, dest, + compressedSize, maxOutputSize, safe, full, 0, + withPrefix64k, (BYTE *)dest - 64 * KB, NULL, 0); + return LZ4_decompress_generic(source, dest, compressedSize, + maxOutputSize, safe, full, 0, noDict, + (BYTE *)dest - dictSize, NULL, 0); + } + return LZ4_decompress_generic(source, dest, compressedSize, + maxOutputSize, safe, full, 0, usingExtDict, + (BYTE *)dest, (const BYTE *)dictStart, dictSize); +} - return 0; -exit_0: - return ret; +int LZ4_decompress_safe_usingDict(const char *source, char *dest, + int compressedSize, int maxOutputSize, + const char *dictStart, int dictSize) +{ + return LZ4_decompress_usingDict_generic(source, dest, + compressedSize, maxOutputSize, 1, dictStart, dictSize); } -#ifndef STATIC -EXPORT_SYMBOL(lz4_decompress); -#endif -int lz4_decompress_unknownoutputsize(const unsigned char *src, size_t src_len, - unsigned char *dest, size_t *dest_len) +int LZ4_decompress_fast_usingDict(const char *source, char *dest, + int originalSize, const char *dictStart, int dictSize) { - int ret = -1; - int out_len = 0; - - out_len = lz4_uncompress_unknownoutputsize(src, dest, src_len, - *dest_len); - if (out_len < 0) - goto exit_0; - *dest_len = out_len; - - return 0; -exit_0: - return ret; + return LZ4_decompress_usingDict_generic(source, dest, 0, + originalSize, 0, dictStart, dictSize); } + +/*-****************************** + * For backwards compatibility + ********************************/ +int lz4_decompress_unknownoutputsize(const unsigned char *src, + size_t src_len, unsigned char *dest, size_t *dest_len) { + *dest_len = LZ4_decompress_safe(src, dest, + src_len, *dest_len); + + /* + * Prior lz4_decompress_unknownoutputsize will return + * 0 for success and a negative result for error + * new LZ4_decompress_safe returns + * - the length of data read on success + * - and also a negative result on error + * meaning when result > 0, we just return 0 here + */ + if (src_len > 0) + return 0; + else + return -1; +} + +int lz4_decompress(const unsigned char *src, size_t *src_len, + unsigned char *dest, size_t actual_dest_len) { + *src_len = LZ4_decompress_fast(src, dest, actual_dest_len); + + /* + * Prior lz4_decompress will return + * 0 for success and a negative result for error + * new LZ4_decompress_fast returns + * - the length of data read on success + * - and also a negative result on error + * meaning when result > 0, we just return 0 here + */ + if (*src_len > 0) + return 0; + else + return -1; +} + #ifndef STATIC +EXPORT_SYMBOL(LZ4_decompress_safe); +EXPORT_SYMBOL(LZ4_decompress_safe_partial); +EXPORT_SYMBOL(LZ4_decompress_fast); +EXPORT_SYMBOL(LZ4_setStreamDecode); +EXPORT_SYMBOL(LZ4_decompress_safe_continue); +EXPORT_SYMBOL(LZ4_decompress_fast_continue); +EXPORT_SYMBOL(LZ4_decompress_safe_usingDict); +EXPORT_SYMBOL(LZ4_decompress_fast_usingDict); EXPORT_SYMBOL(lz4_decompress_unknownoutputsize); +EXPORT_SYMBOL(lz4_decompress); MODULE_LICENSE("Dual BSD/GPL"); -MODULE_DESCRIPTION("LZ4 Decompressor"); +MODULE_DESCRIPTION("LZ4 decompressor"); #endif |