Julius Werner | bf27391 | 2015-06-30 10:30:30 -0700 | [diff] [blame] | 1 | /* |
| 2 | LZ4 - Fast LZ compression algorithm |
| 3 | Copyright (C) 2011-2015, Yann Collet. |
| 4 | |
| 5 | BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) |
| 6 | |
| 7 | Redistribution and use in source and binary forms, with or without |
| 8 | modification, are permitted provided that the following conditions are |
| 9 | met: |
| 10 | |
| 11 | * Redistributions of source code must retain the above copyright |
| 12 | notice, this list of conditions and the following disclaimer. |
| 13 | * Redistributions in binary form must reproduce the above |
| 14 | copyright notice, this list of conditions and the following disclaimer |
| 15 | in the documentation and/or other materials provided with the |
| 16 | distribution. |
| 17 | |
| 18 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 19 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 20 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 21 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 22 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 23 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| 24 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| 25 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 26 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 27 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| 28 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 29 | |
| 30 | You can contact the author at : |
| 31 | - LZ4 source repository : https://github.com/Cyan4973/lz4 |
| 32 | - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c |
| 33 | */ |
| 34 | |
| 35 | |
| 36 | /************************************** |
| 37 | * Reading and writing into memory |
| 38 | **************************************/ |
| 39 | |
Julius Werner | 09f2921 | 2015-09-29 13:51:35 -0700 | [diff] [blame] | 40 | /* customized variant of memcpy, which can overwrite up to 7 bytes beyond dstEnd */ |
Julius Werner | bf27391 | 2015-06-30 10:30:30 -0700 | [diff] [blame] | 41 | static void LZ4_wildCopy(void* dstPtr, const void* srcPtr, void* dstEnd) |
| 42 | { |
| 43 | BYTE* d = (BYTE*)dstPtr; |
| 44 | const BYTE* s = (const BYTE*)srcPtr; |
Julius Werner | 09f2921 | 2015-09-29 13:51:35 -0700 | [diff] [blame] | 45 | BYTE* const e = (BYTE*)dstEnd; |
| 46 | |
| 47 | #if 0 |
| 48 | const size_t l2 = 8 - (((size_t)d) & (sizeof(void*)-1)); |
| 49 | LZ4_copy8(d,s); if (d>e-9) return; |
| 50 | d+=l2; s+=l2; |
| 51 | #endif /* join to align */ |
| 52 | |
Julius Werner | bf27391 | 2015-06-30 10:30:30 -0700 | [diff] [blame] | 53 | do { LZ4_copy8(d,s); d+=8; s+=8; } while (d<e); |
| 54 | } |
| 55 | |
| 56 | |
| 57 | /************************************** |
| 58 | * Common Constants |
| 59 | **************************************/ |
| 60 | #define MINMATCH 4 |
| 61 | |
Julius Werner | 09f2921 | 2015-09-29 13:51:35 -0700 | [diff] [blame] | 62 | #define WILDCOPYLENGTH 8 |
Julius Werner | bf27391 | 2015-06-30 10:30:30 -0700 | [diff] [blame] | 63 | #define LASTLITERALS 5 |
Julius Werner | 09f2921 | 2015-09-29 13:51:35 -0700 | [diff] [blame] | 64 | #define MFLIMIT (WILDCOPYLENGTH+MINMATCH) |
Julius Werner | bf27391 | 2015-06-30 10:30:30 -0700 | [diff] [blame] | 65 | static const int LZ4_minLength = (MFLIMIT+1); |
| 66 | |
| 67 | #define KB *(1 <<10) |
| 68 | #define MB *(1 <<20) |
| 69 | #define GB *(1U<<30) |
| 70 | |
| 71 | #define MAXD_LOG 16 |
| 72 | #define MAX_DISTANCE ((1 << MAXD_LOG) - 1) |
| 73 | |
| 74 | #define ML_BITS 4 |
| 75 | #define ML_MASK ((1U<<ML_BITS)-1) |
| 76 | #define RUN_BITS (8-ML_BITS) |
| 77 | #define RUN_MASK ((1U<<RUN_BITS)-1) |
| 78 | |
| 79 | |
| 80 | /************************************** |
| 81 | * Local Structures and types |
| 82 | **************************************/ |
| 83 | typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive; |
| 84 | typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive; |
| 85 | typedef enum { full = 0, partial = 1 } earlyEnd_directive; |
| 86 | |
| 87 | |
| 88 | |
| 89 | /******************************* |
| 90 | * Decompression functions |
| 91 | *******************************/ |
| 92 | /* |
| 93 | * This generic decompression function cover all use cases. |
| 94 | * It shall be instantiated several times, using different sets of directives |
| 95 | * Note that it is essential this generic function is really inlined, |
| 96 | * in order to remove useless branches during compilation optimization. |
| 97 | */ |
| 98 | FORCE_INLINE int LZ4_decompress_generic( |
| 99 | const char* const source, |
| 100 | char* const dest, |
| 101 | int inputSize, |
| 102 | int outputSize, /* If endOnInput==endOnInputSize, this value is the max size of Output Buffer. */ |
| 103 | |
| 104 | int endOnInput, /* endOnOutputSize, endOnInputSize */ |
| 105 | int partialDecoding, /* full, partial */ |
| 106 | int targetOutputSize, /* only used if partialDecoding==partial */ |
| 107 | int dict, /* noDict, withPrefix64k, usingExtDict */ |
| 108 | const BYTE* const lowPrefix, /* == dest if dict == noDict */ |
| 109 | const BYTE* const dictStart, /* only if dict==usingExtDict */ |
| 110 | const size_t dictSize /* note : = 0 if noDict */ |
| 111 | ) |
| 112 | { |
| 113 | /* Local Variables */ |
| 114 | const BYTE* ip = (const BYTE*) source; |
| 115 | const BYTE* const iend = ip + inputSize; |
| 116 | |
| 117 | BYTE* op = (BYTE*) dest; |
| 118 | BYTE* const oend = op + outputSize; |
| 119 | BYTE* cpy; |
| 120 | BYTE* oexit = op + targetOutputSize; |
| 121 | const BYTE* const lowLimit = lowPrefix - dictSize; |
| 122 | |
| 123 | const BYTE* const dictEnd = (const BYTE*)dictStart + dictSize; |
Julius Werner | 09f2921 | 2015-09-29 13:51:35 -0700 | [diff] [blame] | 124 | const unsigned dec32table[] = {4, 1, 2, 1, 4, 4, 4, 4}; |
| 125 | const int dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3}; |
Julius Werner | bf27391 | 2015-06-30 10:30:30 -0700 | [diff] [blame] | 126 | |
| 127 | const int safeDecode = (endOnInput==endOnInputSize); |
| 128 | const int checkOffset = ((safeDecode) && (dictSize < (int)(64 KB))); |
Julius Werner | 09f2921 | 2015-09-29 13:51:35 -0700 | [diff] [blame] | 129 | const int inPlaceDecode = ((ip >= op) && (ip < oend)); |
Julius Werner | bf27391 | 2015-06-30 10:30:30 -0700 | [diff] [blame] | 130 | |
| 131 | |
| 132 | /* Special cases */ |
| 133 | if ((partialDecoding) && (oexit> oend-MFLIMIT)) oexit = oend-MFLIMIT; /* targetOutputSize too high => decode everything */ |
| 134 | if ((endOnInput) && (unlikely(outputSize==0))) return ((inputSize==1) && (*ip==0)) ? 0 : -1; /* Empty output buffer */ |
| 135 | if ((!endOnInput) && (unlikely(outputSize==0))) return (*ip==0?1:-1); |
| 136 | |
| 137 | |
| 138 | /* Main Loop */ |
| 139 | while (1) |
| 140 | { |
| 141 | unsigned token; |
| 142 | size_t length; |
| 143 | const BYTE* match; |
Julius Werner | 09f2921 | 2015-09-29 13:51:35 -0700 | [diff] [blame] | 144 | size_t offset; |
| 145 | |
| 146 | if (unlikely((inPlaceDecode) && (op + WILDCOPYLENGTH > ip))) goto _output_error; /* output stream ran over input stream */ |
Julius Werner | bf27391 | 2015-06-30 10:30:30 -0700 | [diff] [blame] | 147 | |
| 148 | /* get literal length */ |
| 149 | token = *ip++; |
| 150 | if ((length=(token>>ML_BITS)) == RUN_MASK) |
| 151 | { |
| 152 | unsigned s; |
Alex Rebert | 70282ae | 2020-02-29 17:36:08 -0500 | [diff] [blame] | 153 | if ((endOnInput) && unlikely(ip>=iend-RUN_MASK)) goto _output_error; /* overflow detection */ |
Julius Werner | bf27391 | 2015-06-30 10:30:30 -0700 | [diff] [blame] | 154 | do |
| 155 | { |
| 156 | s = *ip++; |
| 157 | length += s; |
| 158 | } |
Julius Werner | 09f2921 | 2015-09-29 13:51:35 -0700 | [diff] [blame] | 159 | while ( likely(endOnInput ? ip<iend-RUN_MASK : 1) && (s==255) ); |
Julius Werner | bf27391 | 2015-06-30 10:30:30 -0700 | [diff] [blame] | 160 | if ((safeDecode) && unlikely((size_t)(op+length)<(size_t)(op))) goto _output_error; /* overflow detection */ |
| 161 | if ((safeDecode) && unlikely((size_t)(ip+length)<(size_t)(ip))) goto _output_error; /* overflow detection */ |
| 162 | } |
| 163 | |
| 164 | /* copy literals */ |
| 165 | cpy = op+length; |
| 166 | if (((endOnInput) && ((cpy>(partialDecoding?oexit:oend-MFLIMIT)) || (ip+length>iend-(2+1+LASTLITERALS))) ) |
Julius Werner | 09f2921 | 2015-09-29 13:51:35 -0700 | [diff] [blame] | 167 | || ((!endOnInput) && (cpy>oend-WILDCOPYLENGTH))) |
Julius Werner | bf27391 | 2015-06-30 10:30:30 -0700 | [diff] [blame] | 168 | { |
| 169 | if (partialDecoding) |
| 170 | { |
| 171 | if (cpy > oend) goto _output_error; /* Error : write attempt beyond end of output buffer */ |
| 172 | if ((endOnInput) && (ip+length > iend)) goto _output_error; /* Error : read attempt beyond end of input buffer */ |
| 173 | } |
| 174 | else |
| 175 | { |
| 176 | if ((!endOnInput) && (cpy != oend)) goto _output_error; /* Error : block decoding must stop exactly there */ |
| 177 | if ((endOnInput) && ((ip+length != iend) || (cpy > oend))) goto _output_error; /* Error : input must be consumed */ |
| 178 | } |
Julius Werner | 09f2921 | 2015-09-29 13:51:35 -0700 | [diff] [blame] | 179 | memmove(op, ip, length); |
Julius Werner | bf27391 | 2015-06-30 10:30:30 -0700 | [diff] [blame] | 180 | ip += length; |
| 181 | op += length; |
| 182 | break; /* Necessarily EOF, due to parsing restrictions */ |
| 183 | } |
| 184 | LZ4_wildCopy(op, ip, cpy); |
| 185 | ip += length; op = cpy; |
| 186 | |
| 187 | /* get offset */ |
Julius Werner | 09f2921 | 2015-09-29 13:51:35 -0700 | [diff] [blame] | 188 | offset = LZ4_readLE16(ip); ip+=2; |
| 189 | match = op - offset; |
| 190 | if ((checkOffset) && (unlikely(match < lowLimit))) goto _output_error; /* Error : offset outside buffers */ |
Julius Werner | bf27391 | 2015-06-30 10:30:30 -0700 | [diff] [blame] | 191 | |
| 192 | /* get matchlength */ |
| 193 | length = token & ML_MASK; |
| 194 | if (length == ML_MASK) |
| 195 | { |
| 196 | unsigned s; |
| 197 | do |
| 198 | { |
| 199 | if ((endOnInput) && (ip > iend-LASTLITERALS)) goto _output_error; |
| 200 | s = *ip++; |
| 201 | length += s; |
| 202 | } while (s==255); |
| 203 | if ((safeDecode) && unlikely((size_t)(op+length)<(size_t)op)) goto _output_error; /* overflow detection */ |
| 204 | } |
| 205 | length += MINMATCH; |
| 206 | |
| 207 | /* check external dictionary */ |
| 208 | if ((dict==usingExtDict) && (match < lowPrefix)) |
| 209 | { |
| 210 | if (unlikely(op+length > oend-LASTLITERALS)) goto _output_error; /* doesn't respect parsing restriction */ |
| 211 | |
| 212 | if (length <= (size_t)(lowPrefix-match)) |
| 213 | { |
| 214 | /* match can be copied as a single segment from external dictionary */ |
| 215 | match = dictEnd - (lowPrefix-match); |
| 216 | memmove(op, match, length); op += length; |
| 217 | } |
| 218 | else |
| 219 | { |
Julius Werner | 09f2921 | 2015-09-29 13:51:35 -0700 | [diff] [blame] | 220 | /* match encompass external dictionary and current block */ |
Julius Werner | bf27391 | 2015-06-30 10:30:30 -0700 | [diff] [blame] | 221 | size_t copySize = (size_t)(lowPrefix-match); |
| 222 | memcpy(op, dictEnd - copySize, copySize); |
| 223 | op += copySize; |
| 224 | copySize = length - copySize; |
Julius Werner | 09f2921 | 2015-09-29 13:51:35 -0700 | [diff] [blame] | 225 | if (copySize > (size_t)(op-lowPrefix)) /* overlap copy */ |
Julius Werner | bf27391 | 2015-06-30 10:30:30 -0700 | [diff] [blame] | 226 | { |
| 227 | BYTE* const endOfMatch = op + copySize; |
| 228 | const BYTE* copyFrom = lowPrefix; |
| 229 | while (op < endOfMatch) *op++ = *copyFrom++; |
| 230 | } |
| 231 | else |
| 232 | { |
| 233 | memcpy(op, lowPrefix, copySize); |
| 234 | op += copySize; |
| 235 | } |
| 236 | } |
| 237 | continue; |
| 238 | } |
| 239 | |
Julius Werner | 09f2921 | 2015-09-29 13:51:35 -0700 | [diff] [blame] | 240 | /* copy match within block */ |
Julius Werner | bf27391 | 2015-06-30 10:30:30 -0700 | [diff] [blame] | 241 | cpy = op + length; |
Julius Werner | 09f2921 | 2015-09-29 13:51:35 -0700 | [diff] [blame] | 242 | if (unlikely(offset<8)) |
Julius Werner | bf27391 | 2015-06-30 10:30:30 -0700 | [diff] [blame] | 243 | { |
Julius Werner | 09f2921 | 2015-09-29 13:51:35 -0700 | [diff] [blame] | 244 | const int dec64 = dec64table[offset]; |
Julius Werner | bf27391 | 2015-06-30 10:30:30 -0700 | [diff] [blame] | 245 | op[0] = match[0]; |
| 246 | op[1] = match[1]; |
| 247 | op[2] = match[2]; |
| 248 | op[3] = match[3]; |
Julius Werner | 09f2921 | 2015-09-29 13:51:35 -0700 | [diff] [blame] | 249 | match += dec32table[offset]; |
| 250 | memcpy(op+4, match, 4); |
| 251 | match -= dec64; |
| 252 | } else { LZ4_copy8(op, match); match+=8; } |
| 253 | op += 8; |
Julius Werner | bf27391 | 2015-06-30 10:30:30 -0700 | [diff] [blame] | 254 | |
| 255 | if (unlikely(cpy>oend-12)) |
| 256 | { |
Julius Werner | 09f2921 | 2015-09-29 13:51:35 -0700 | [diff] [blame] | 257 | BYTE* const oCopyLimit = oend-(WILDCOPYLENGTH-1); |
| 258 | if (cpy > oend-LASTLITERALS) goto _output_error; /* Error : last LASTLITERALS bytes must be literals (uncompressed) */ |
| 259 | if (op < oCopyLimit) |
Julius Werner | bf27391 | 2015-06-30 10:30:30 -0700 | [diff] [blame] | 260 | { |
Julius Werner | 09f2921 | 2015-09-29 13:51:35 -0700 | [diff] [blame] | 261 | LZ4_wildCopy(op, match, oCopyLimit); |
| 262 | match += oCopyLimit - op; |
| 263 | op = oCopyLimit; |
Julius Werner | bf27391 | 2015-06-30 10:30:30 -0700 | [diff] [blame] | 264 | } |
| 265 | while (op<cpy) *op++ = *match++; |
| 266 | } |
| 267 | else |
| 268 | LZ4_wildCopy(op, match, cpy); |
| 269 | op=cpy; /* correction */ |
| 270 | } |
| 271 | |
| 272 | /* end of decoding */ |
| 273 | if (endOnInput) |
| 274 | return (int) (((char*)op)-dest); /* Nb of output bytes decoded */ |
| 275 | else |
| 276 | return (int) (((const char*)ip)-source); /* Nb of input bytes read */ |
| 277 | |
| 278 | /* Overflow error detected */ |
| 279 | _output_error: |
| 280 | return (int) (-(((const char*)ip)-source))-1; |
| 281 | } |