Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1 | /* |
| 2 | zstd - standard compression library |
| 3 | Copyright (C) 2014-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 | * Redistributions of source code must retain the above copyright |
| 11 | notice, this list of conditions and the following disclaimer. |
| 12 | * Redistributions in binary form must reproduce the above |
| 13 | copyright notice, this list of conditions and the following disclaimer |
| 14 | in the documentation and/or other materials provided with the |
| 15 | distribution. |
| 16 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 17 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 18 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 19 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 20 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 21 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| 22 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| 23 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 24 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 25 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| 26 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 27 | |
| 28 | You can contact the author at : |
| 29 | - zstd source repository : https://github.com/Cyan4973/zstd |
| 30 | - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c |
| 31 | */ |
| 32 | |
| 33 | /* *************************************************************** |
| 34 | * Tuning parameters |
| 35 | *****************************************************************/ |
| 36 | /*! |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 37 | * HEAPMODE : |
Yann Collet | dcac00e | 2015-11-19 11:23:44 +0100 | [diff] [blame^] | 38 | * Select how default functions will allocate memory for their context, |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 39 | * in memory stack (0, fastest), or in memory heap (1, requires malloc()) |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 40 | */ |
| 41 | #ifndef ZSTD_HEAPMODE |
| 42 | # define ZSTD_HEAPMODE 1 |
| 43 | #endif /* ZSTD_HEAPMODE */ |
| 44 | |
| 45 | /*! |
| 46 | * LEGACY_SUPPORT : |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 47 | * ZSTD_decompress() can decode older formats (starting from zstd 0.1+) |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 48 | */ |
| 49 | #ifndef ZSTD_LEGACY_SUPPORT |
| 50 | # define ZSTD_LEGACY_SUPPORT 1 |
| 51 | #endif |
| 52 | |
| 53 | |
| 54 | /* ******************************************************* |
| 55 | * Includes |
| 56 | *********************************************************/ |
| 57 | #include <stdlib.h> /* calloc */ |
| 58 | #include <string.h> /* memcpy, memmove */ |
| 59 | #include <stdio.h> /* debug : printf */ |
| 60 | #include "mem.h" /* low level memory routines */ |
| 61 | #include "zstd_static.h" |
| 62 | #include "zstd_internal.h" |
| 63 | #include "fse_static.h" |
| 64 | #include "huff0.h" |
| 65 | |
| 66 | #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT==1) |
| 67 | # include "zstd_legacy.h" |
| 68 | #endif |
| 69 | |
| 70 | |
| 71 | /* ******************************************************* |
| 72 | * Compiler specifics |
| 73 | *********************************************************/ |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 74 | #ifdef _MSC_VER /* Visual Studio */ |
| 75 | # define FORCE_INLINE static __forceinline |
| 76 | # include <intrin.h> /* For Visual 2005 */ |
| 77 | # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ |
| 78 | # pragma warning(disable : 4324) /* disable: C4324: padded structure */ |
| 79 | #else |
| 80 | # define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__) |
| 81 | # ifdef __GNUC__ |
| 82 | # define FORCE_INLINE static inline __attribute__((always_inline)) |
| 83 | # else |
| 84 | # define FORCE_INLINE static inline |
| 85 | # endif |
| 86 | #endif |
| 87 | |
| 88 | |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 89 | /* ************************************* |
| 90 | * Local types |
| 91 | ***************************************/ |
| 92 | typedef struct |
| 93 | { |
| 94 | blockType_t blockType; |
| 95 | U32 origSize; |
| 96 | } blockProperties_t; |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 97 | |
| 98 | |
| 99 | /* ******************************************************* |
| 100 | * Memory operations |
| 101 | **********************************************************/ |
| 102 | static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); } |
| 103 | |
| 104 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 105 | /* ************************************* |
| 106 | * Error Management |
| 107 | ***************************************/ |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 108 | unsigned ZSTD_versionNumber (void) { return ZSTD_VERSION_NUMBER; } |
| 109 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 110 | /*! ZSTD_isError |
| 111 | * tells if a return value is an error code */ |
| 112 | unsigned ZSTD_isError(size_t code) { return ERR_isError(code); } |
| 113 | |
| 114 | /*! ZSTD_getErrorName |
| 115 | * provides error code string (useful for debugging) */ |
| 116 | const char* ZSTD_getErrorName(size_t code) { return ERR_getErrorName(code); } |
| 117 | |
| 118 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 119 | /* ************************************************************* |
Yann Collet | 5b78d2f | 2015-11-12 15:36:05 +0100 | [diff] [blame] | 120 | * Context management |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 121 | ***************************************************************/ |
| 122 | struct ZSTD_DCtx_s |
| 123 | { |
| 124 | U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)]; |
| 125 | U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)]; |
| 126 | U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)]; |
| 127 | void* previousDstEnd; |
| 128 | void* base; |
Yann Collet | 5b78d2f | 2015-11-12 15:36:05 +0100 | [diff] [blame] | 129 | void* vBase; |
| 130 | void* dictEnd; |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 131 | size_t expected; |
| 132 | blockType_t bType; |
| 133 | U32 phase; |
| 134 | const BYTE* litPtr; |
| 135 | size_t litBufSize; |
| 136 | size_t litSize; |
| 137 | BYTE litBuffer[BLOCKSIZE + 8 /* margin for wildcopy */]; |
| 138 | }; /* typedef'd to ZSTD_Dctx within "zstd_static.h" */ |
| 139 | |
Yann Collet | 5b78d2f | 2015-11-12 15:36:05 +0100 | [diff] [blame] | 140 | size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx) |
| 141 | { |
| 142 | dctx->expected = ZSTD_frameHeaderSize; |
| 143 | dctx->phase = 0; |
| 144 | dctx->previousDstEnd = NULL; |
| 145 | dctx->base = NULL; |
| 146 | dctx->vBase = NULL; |
| 147 | dctx->dictEnd = NULL; |
| 148 | return 0; |
| 149 | } |
| 150 | |
| 151 | ZSTD_DCtx* ZSTD_createDCtx(void) |
| 152 | { |
| 153 | ZSTD_DCtx* dctx = (ZSTD_DCtx*)malloc(sizeof(ZSTD_DCtx)); |
| 154 | if (dctx==NULL) return NULL; |
| 155 | ZSTD_resetDCtx(dctx); |
| 156 | return dctx; |
| 157 | } |
| 158 | |
| 159 | size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx) |
| 160 | { |
| 161 | free(dctx); |
| 162 | return 0; |
| 163 | } |
| 164 | |
| 165 | |
| 166 | /* ************************************************************* |
| 167 | * Decompression section |
| 168 | ***************************************************************/ |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 169 | |
| 170 | size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr) |
| 171 | { |
| 172 | const BYTE* const in = (const BYTE* const)src; |
| 173 | BYTE headerFlags; |
| 174 | U32 cSize; |
| 175 | |
| 176 | if (srcSize < 3) return ERROR(srcSize_wrong); |
| 177 | |
| 178 | headerFlags = *in; |
| 179 | cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16); |
| 180 | |
| 181 | bpPtr->blockType = (blockType_t)(headerFlags >> 6); |
| 182 | bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0; |
| 183 | |
| 184 | if (bpPtr->blockType == bt_end) return 0; |
| 185 | if (bpPtr->blockType == bt_rle) return 1; |
| 186 | return cSize; |
| 187 | } |
| 188 | |
Yann Collet | 0f366c6 | 2015-11-12 16:19:30 +0100 | [diff] [blame] | 189 | static size_t ZSTD_copyRawBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize) |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 190 | { |
| 191 | if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall); |
| 192 | memcpy(dst, src, srcSize); |
| 193 | return srcSize; |
| 194 | } |
| 195 | |
| 196 | |
| 197 | /** ZSTD_decompressLiterals |
| 198 | @return : nb of bytes read from src, or an error code*/ |
| 199 | static size_t ZSTD_decompressLiterals(void* dst, size_t* maxDstSizePtr, |
| 200 | const void* src, size_t srcSize) |
| 201 | { |
| 202 | const BYTE* ip = (const BYTE*)src; |
| 203 | |
| 204 | const size_t litSize = (MEM_readLE32(src) & 0x1FFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ |
| 205 | const size_t litCSize = (MEM_readLE32(ip+2) & 0xFFFFFF) >> 5; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ |
| 206 | |
| 207 | if (litSize > *maxDstSizePtr) return ERROR(corruption_detected); |
| 208 | if (litCSize + 5 > srcSize) return ERROR(corruption_detected); |
| 209 | |
| 210 | if (HUF_isError(HUF_decompress(dst, litSize, ip+5, litCSize))) return ERROR(corruption_detected); |
| 211 | |
| 212 | *maxDstSizePtr = litSize; |
| 213 | return litCSize + 5; |
| 214 | } |
| 215 | |
| 216 | |
| 217 | /** ZSTD_decodeLiteralsBlock |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 218 | @return : nb of bytes read from src (< srcSize ) */ |
Yann Collet | 5b78d2f | 2015-11-12 15:36:05 +0100 | [diff] [blame] | 219 | size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx, |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 220 | const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */ |
| 221 | { |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 222 | const BYTE* const istart = (const BYTE*) src; |
| 223 | |
| 224 | /* any compressed block with literals segment must be at least this size */ |
| 225 | if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected); |
| 226 | |
| 227 | switch(*istart & 3) |
| 228 | { |
| 229 | /* compressed */ |
| 230 | case 0: |
| 231 | { |
| 232 | size_t litSize = BLOCKSIZE; |
| 233 | const size_t readSize = ZSTD_decompressLiterals(dctx->litBuffer, &litSize, src, srcSize); |
| 234 | dctx->litPtr = dctx->litBuffer; |
| 235 | dctx->litBufSize = BLOCKSIZE+8; |
| 236 | dctx->litSize = litSize; |
| 237 | return readSize; /* works if it's an error too */ |
| 238 | } |
| 239 | case IS_RAW: |
| 240 | { |
| 241 | const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ |
| 242 | if (litSize > srcSize-11) /* risk of reading too far with wildcopy */ |
| 243 | { |
| 244 | if (litSize > srcSize-3) return ERROR(corruption_detected); |
| 245 | memcpy(dctx->litBuffer, istart, litSize); |
| 246 | dctx->litPtr = dctx->litBuffer; |
| 247 | dctx->litBufSize = BLOCKSIZE+8; |
| 248 | dctx->litSize = litSize; |
| 249 | return litSize+3; |
| 250 | } |
| 251 | /* direct reference into compressed stream */ |
| 252 | dctx->litPtr = istart+3; |
| 253 | dctx->litBufSize = srcSize-3; |
| 254 | dctx->litSize = litSize; |
| 255 | return litSize+3; } |
| 256 | case IS_RLE: |
| 257 | { |
| 258 | const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */ |
| 259 | if (litSize > BLOCKSIZE) return ERROR(corruption_detected); |
| 260 | memset(dctx->litBuffer, istart[3], litSize); |
| 261 | dctx->litPtr = dctx->litBuffer; |
| 262 | dctx->litBufSize = BLOCKSIZE+8; |
| 263 | dctx->litSize = litSize; |
| 264 | return 4; |
| 265 | } |
| 266 | default: |
| 267 | return ERROR(corruption_detected); /* forbidden nominal case */ |
| 268 | } |
| 269 | } |
| 270 | |
| 271 | |
| 272 | size_t ZSTD_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr, |
| 273 | FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb, |
| 274 | const void* src, size_t srcSize) |
| 275 | { |
| 276 | const BYTE* const istart = (const BYTE* const)src; |
| 277 | const BYTE* ip = istart; |
| 278 | const BYTE* const iend = istart + srcSize; |
| 279 | U32 LLtype, Offtype, MLtype; |
| 280 | U32 LLlog, Offlog, MLlog; |
| 281 | size_t dumpsLength; |
| 282 | |
| 283 | /* check */ |
| 284 | if (srcSize < 5) return ERROR(srcSize_wrong); |
| 285 | |
| 286 | /* SeqHead */ |
| 287 | *nbSeq = MEM_readLE16(ip); ip+=2; |
| 288 | LLtype = *ip >> 6; |
| 289 | Offtype = (*ip >> 4) & 3; |
| 290 | MLtype = (*ip >> 2) & 3; |
| 291 | if (*ip & 2) |
| 292 | { |
| 293 | dumpsLength = ip[2]; |
| 294 | dumpsLength += ip[1] << 8; |
| 295 | ip += 3; |
| 296 | } |
| 297 | else |
| 298 | { |
| 299 | dumpsLength = ip[1]; |
| 300 | dumpsLength += (ip[0] & 1) << 8; |
| 301 | ip += 2; |
| 302 | } |
| 303 | *dumpsPtr = ip; |
| 304 | ip += dumpsLength; |
| 305 | *dumpsLengthPtr = dumpsLength; |
| 306 | |
| 307 | /* check */ |
| 308 | if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */ |
| 309 | |
| 310 | /* sequences */ |
| 311 | { |
Yann Collet | 82368cf | 2015-11-16 19:10:56 +0100 | [diff] [blame] | 312 | S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL >= MaxOff */ |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 313 | size_t headerSize; |
| 314 | |
| 315 | /* Build DTables */ |
| 316 | switch(LLtype) |
| 317 | { |
| 318 | U32 max; |
| 319 | case bt_rle : |
| 320 | LLlog = 0; |
| 321 | FSE_buildDTable_rle(DTableLL, *ip++); break; |
| 322 | case bt_raw : |
| 323 | LLlog = LLbits; |
| 324 | FSE_buildDTable_raw(DTableLL, LLbits); break; |
| 325 | default : |
| 326 | max = MaxLL; |
| 327 | headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip); |
| 328 | if (FSE_isError(headerSize)) return ERROR(GENERIC); |
| 329 | if (LLlog > LLFSELog) return ERROR(corruption_detected); |
| 330 | ip += headerSize; |
| 331 | FSE_buildDTable(DTableLL, norm, max, LLlog); |
| 332 | } |
| 333 | |
| 334 | switch(Offtype) |
| 335 | { |
| 336 | U32 max; |
| 337 | case bt_rle : |
| 338 | Offlog = 0; |
| 339 | if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */ |
| 340 | FSE_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */ |
| 341 | break; |
| 342 | case bt_raw : |
| 343 | Offlog = Offbits; |
| 344 | FSE_buildDTable_raw(DTableOffb, Offbits); break; |
| 345 | default : |
| 346 | max = MaxOff; |
| 347 | headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip); |
| 348 | if (FSE_isError(headerSize)) return ERROR(GENERIC); |
| 349 | if (Offlog > OffFSELog) return ERROR(corruption_detected); |
| 350 | ip += headerSize; |
| 351 | FSE_buildDTable(DTableOffb, norm, max, Offlog); |
| 352 | } |
| 353 | |
| 354 | switch(MLtype) |
| 355 | { |
| 356 | U32 max; |
| 357 | case bt_rle : |
| 358 | MLlog = 0; |
| 359 | if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */ |
| 360 | FSE_buildDTable_rle(DTableML, *ip++); break; |
| 361 | case bt_raw : |
| 362 | MLlog = MLbits; |
| 363 | FSE_buildDTable_raw(DTableML, MLbits); break; |
| 364 | default : |
| 365 | max = MaxML; |
| 366 | headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip); |
| 367 | if (FSE_isError(headerSize)) return ERROR(GENERIC); |
| 368 | if (MLlog > MLFSELog) return ERROR(corruption_detected); |
| 369 | ip += headerSize; |
| 370 | FSE_buildDTable(DTableML, norm, max, MLlog); |
| 371 | } |
| 372 | } |
| 373 | |
| 374 | return ip-istart; |
| 375 | } |
| 376 | |
| 377 | |
| 378 | typedef struct { |
| 379 | size_t litLength; |
| 380 | size_t offset; |
| 381 | size_t matchLength; |
| 382 | } seq_t; |
| 383 | |
| 384 | typedef struct { |
| 385 | BIT_DStream_t DStream; |
| 386 | FSE_DState_t stateLL; |
| 387 | FSE_DState_t stateOffb; |
| 388 | FSE_DState_t stateML; |
| 389 | size_t prevOffset; |
| 390 | const BYTE* dumps; |
| 391 | const BYTE* dumpsEnd; |
| 392 | } seqState_t; |
| 393 | |
| 394 | |
Yann Collet | dcac00e | 2015-11-19 11:23:44 +0100 | [diff] [blame^] | 395 | /** ZSTD_decodeSequence |
| 396 | * Decode the next sequence, defined as nbLiterals, PtrToLiterals, nbMatches, Offset |
| 397 | * @seq : store sequence into this seq_t |
| 398 | */ |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 399 | static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState) |
| 400 | { |
| 401 | size_t litLength; |
| 402 | size_t prevOffset; |
| 403 | size_t offset; |
| 404 | size_t matchLength; |
| 405 | const BYTE* dumps = seqState->dumps; |
| 406 | const BYTE* const de = seqState->dumpsEnd; |
| 407 | |
| 408 | /* Literal length */ |
| 409 | litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream)); |
| 410 | prevOffset = litLength ? seq->offset : seqState->prevOffset; |
| 411 | seqState->prevOffset = seq->offset; |
| 412 | if (litLength == MaxLL) |
| 413 | { |
| 414 | U32 add = *dumps++; |
| 415 | if (add < 255) litLength += add; |
| 416 | else |
| 417 | { |
| 418 | litLength = MEM_readLE32(dumps) & 0xFFFFFF; /* no pb : dumps is always followed by seq tables > 1 byte */ |
| 419 | dumps += 3; |
| 420 | } |
| 421 | if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */ |
| 422 | } |
| 423 | |
| 424 | /* Offset */ |
| 425 | { |
| 426 | static const U32 offsetPrefix[MaxOff+1] = { |
| 427 | 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256, |
| 428 | 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, |
| 429 | 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 }; |
| 430 | U32 offsetCode, nbBits; |
| 431 | offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); /* <= maxOff, by table construction */ |
| 432 | if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream)); |
| 433 | nbBits = offsetCode - 1; |
| 434 | if (offsetCode==0) nbBits = 0; /* cmove */ |
| 435 | offset = offsetPrefix[offsetCode] + BIT_readBits(&(seqState->DStream), nbBits); |
| 436 | if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream)); |
| 437 | if (offsetCode==0) offset = prevOffset; /* cmove */ |
| 438 | } |
| 439 | |
| 440 | /* MatchLength */ |
| 441 | matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream)); |
| 442 | if (matchLength == MaxML) |
| 443 | { |
| 444 | U32 add = *dumps++; |
| 445 | if (add < 255) matchLength += add; |
| 446 | else |
| 447 | { |
| 448 | matchLength = MEM_readLE32(dumps) & 0xFFFFFF; /* no pb : dumps is always followed by seq tables > 1 byte */ |
| 449 | dumps += 3; |
| 450 | } |
| 451 | if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */ |
| 452 | } |
| 453 | matchLength += MINMATCH; |
| 454 | |
| 455 | /* save result */ |
| 456 | seq->litLength = litLength; |
| 457 | seq->offset = offset; |
| 458 | seq->matchLength = matchLength; |
| 459 | seqState->dumps = dumps; |
| 460 | } |
| 461 | |
| 462 | |
Yann Collet | 5b78d2f | 2015-11-12 15:36:05 +0100 | [diff] [blame] | 463 | FORCE_INLINE size_t ZSTD_execSequence(BYTE* op, |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 464 | seq_t sequence, |
| 465 | const BYTE** litPtr, const BYTE* const litLimit_8, |
Yann Collet | 5b78d2f | 2015-11-12 15:36:05 +0100 | [diff] [blame] | 466 | BYTE* const base, BYTE* const vBase, BYTE* const dictEnd, |
| 467 | BYTE* const oend) |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 468 | { |
| 469 | static const int dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4}; /* added */ |
| 470 | static const int dec64table[] = {8, 8, 8, 7, 8, 9,10,11}; /* substracted */ |
| 471 | const BYTE* const ostart = op; |
| 472 | BYTE* const oLitEnd = op + sequence.litLength; |
| 473 | BYTE* const oMatchEnd = op + sequence.litLength + sequence.matchLength; /* risk : address space overflow (32-bits) */ |
| 474 | BYTE* const oend_8 = oend-8; |
| 475 | const BYTE* const litEnd = *litPtr + sequence.litLength; |
| 476 | |
| 477 | /* check */ |
| 478 | if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of 8 from oend */ |
| 479 | if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */ |
| 480 | if (litEnd > litLimit_8) return ERROR(corruption_detected); /* risk read beyond lit buffer */ |
| 481 | |
| 482 | /* copy Literals */ |
| 483 | ZSTD_wildcopy(op, *litPtr, sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */ |
| 484 | op = oLitEnd; |
| 485 | *litPtr = litEnd; /* update for next sequence */ |
| 486 | |
| 487 | /* copy Match */ |
| 488 | { |
| 489 | const BYTE* match = op - sequence.offset; |
| 490 | |
| 491 | /* check */ |
Yann Collet | 0f366c6 | 2015-11-12 16:19:30 +0100 | [diff] [blame] | 492 | //if (match > op) return ERROR(corruption_detected); /* address space overflow test (is clang optimizer wrongly removing this test ?) */ |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 493 | if (sequence.offset > (size_t)op) return ERROR(corruption_detected); /* address space overflow test (this test seems kept by clang optimizer) */ |
Yann Collet | 0f366c6 | 2015-11-12 16:19:30 +0100 | [diff] [blame] | 494 | |
Yann Collet | b254984 | 2015-11-18 11:29:32 +0100 | [diff] [blame] | 495 | if (match < base) |
Yann Collet | 93a823c | 2015-11-13 15:08:43 +0100 | [diff] [blame] | 496 | { |
Yann Collet | b254984 | 2015-11-18 11:29:32 +0100 | [diff] [blame] | 497 | /* offset beyond prefix */ |
| 498 | if (match < vBase) return ERROR(corruption_detected); |
| 499 | match = dictEnd - (base-match); |
| 500 | if (match + sequence.matchLength <= dictEnd) |
| 501 | { |
| 502 | memcpy(op, match, sequence.matchLength); |
| 503 | return oMatchEnd - ostart; |
| 504 | } |
| 505 | /* span extDict & currentPrefixSegment */ |
| 506 | { |
| 507 | size_t length1 = dictEnd - match; |
| 508 | memcpy(op, match, length1); |
| 509 | op += length1; |
| 510 | sequence.matchLength -= length1; |
| 511 | match = base; |
| 512 | } |
| 513 | } |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 514 | |
Yann Collet | b254984 | 2015-11-18 11:29:32 +0100 | [diff] [blame] | 515 | { |
| 516 | /* match within prefix */ |
| 517 | if (sequence.offset < 8) |
| 518 | { |
| 519 | /* close range match, overlap */ |
| 520 | const int dec64 = dec64table[sequence.offset]; |
| 521 | op[0] = match[0]; |
| 522 | op[1] = match[1]; |
| 523 | op[2] = match[2]; |
| 524 | op[3] = match[3]; |
| 525 | match += dec32table[sequence.offset]; |
| 526 | ZSTD_copy4(op+4, match); |
| 527 | match -= dec64; |
| 528 | } |
| 529 | else |
| 530 | { |
| 531 | ZSTD_copy8(op, match); |
| 532 | } |
| 533 | op += 8; match += 8; |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 534 | |
Yann Collet | b254984 | 2015-11-18 11:29:32 +0100 | [diff] [blame] | 535 | if (oMatchEnd > oend-12) |
| 536 | { |
| 537 | if (op < oend_8) |
| 538 | { |
| 539 | ZSTD_wildcopy(op, match, oend_8 - op); |
| 540 | match += oend_8 - op; |
| 541 | op = oend_8; |
| 542 | } |
| 543 | while (op < oMatchEnd) *op++ = *match++; |
| 544 | } |
| 545 | else |
| 546 | { |
| 547 | ZSTD_wildcopy(op, match, sequence.matchLength-8); /* works even if matchLength < 8 */ |
| 548 | } |
| 549 | return oMatchEnd - ostart; |
| 550 | } |
Yann Collet | 93a823c | 2015-11-13 15:08:43 +0100 | [diff] [blame] | 551 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 552 | } |
| 553 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 554 | } |
| 555 | |
| 556 | static size_t ZSTD_decompressSequences( |
Yann Collet | 5b78d2f | 2015-11-12 15:36:05 +0100 | [diff] [blame] | 557 | ZSTD_DCtx* dctx, |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 558 | void* dst, size_t maxDstSize, |
| 559 | const void* seqStart, size_t seqSize) |
| 560 | { |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 561 | const BYTE* ip = (const BYTE*)seqStart; |
| 562 | const BYTE* const iend = ip + seqSize; |
| 563 | BYTE* const ostart = (BYTE* const)dst; |
| 564 | BYTE* op = ostart; |
| 565 | BYTE* const oend = ostart + maxDstSize; |
| 566 | size_t errorCode, dumpsLength; |
| 567 | const BYTE* litPtr = dctx->litPtr; |
| 568 | const BYTE* const litLimit_8 = litPtr + dctx->litBufSize - 8; |
| 569 | const BYTE* const litEnd = litPtr + dctx->litSize; |
| 570 | int nbSeq; |
| 571 | const BYTE* dumps; |
| 572 | U32* DTableLL = dctx->LLTable; |
| 573 | U32* DTableML = dctx->MLTable; |
| 574 | U32* DTableOffb = dctx->OffTable; |
| 575 | BYTE* const base = (BYTE*) (dctx->base); |
Yann Collet | 5b78d2f | 2015-11-12 15:36:05 +0100 | [diff] [blame] | 576 | BYTE* const vBase = (BYTE*) (dctx->vBase); |
| 577 | BYTE* const dictEnd = (BYTE*) (dctx->dictEnd); |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 578 | |
| 579 | /* Build Decoding Tables */ |
| 580 | errorCode = ZSTD_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength, |
| 581 | DTableLL, DTableML, DTableOffb, |
| 582 | ip, iend-ip); |
| 583 | if (ZSTD_isError(errorCode)) return errorCode; |
| 584 | ip += errorCode; |
| 585 | |
| 586 | /* Regen sequences */ |
| 587 | { |
| 588 | seq_t sequence; |
| 589 | seqState_t seqState; |
| 590 | |
| 591 | memset(&sequence, 0, sizeof(sequence)); |
| 592 | sequence.offset = 4; |
| 593 | seqState.dumps = dumps; |
| 594 | seqState.dumpsEnd = dumps + dumpsLength; |
| 595 | seqState.prevOffset = 4; |
| 596 | errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip); |
| 597 | if (ERR_isError(errorCode)) return ERROR(corruption_detected); |
| 598 | FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL); |
| 599 | FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb); |
| 600 | FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML); |
| 601 | |
| 602 | for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (nbSeq>0) ; ) |
| 603 | { |
| 604 | size_t oneSeqSize; |
| 605 | nbSeq--; |
| 606 | ZSTD_decodeSequence(&sequence, &seqState); |
Yann Collet | 5b78d2f | 2015-11-12 15:36:05 +0100 | [diff] [blame] | 607 | oneSeqSize = ZSTD_execSequence(op, sequence, &litPtr, litLimit_8, base, vBase, dictEnd, oend); |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 608 | if (ZSTD_isError(oneSeqSize)) return oneSeqSize; |
| 609 | op += oneSeqSize; |
| 610 | } |
| 611 | |
| 612 | /* check if reached exact end */ |
| 613 | if ( !BIT_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected); /* requested too much : data is corrupted */ |
| 614 | if (nbSeq<0) return ERROR(corruption_detected); /* requested too many sequences : data is corrupted */ |
| 615 | |
| 616 | /* last literal segment */ |
| 617 | { |
| 618 | size_t lastLLSize = litEnd - litPtr; |
| 619 | if (litPtr > litEnd) return ERROR(corruption_detected); |
| 620 | if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall); |
| 621 | if (op != litPtr) memcpy(op, litPtr, lastLLSize); |
| 622 | op += lastLLSize; |
| 623 | } |
| 624 | } |
| 625 | |
| 626 | return op-ostart; |
| 627 | } |
| 628 | |
| 629 | |
| 630 | static size_t ZSTD_decompressBlock( |
Yann Collet | 5b78d2f | 2015-11-12 15:36:05 +0100 | [diff] [blame] | 631 | ZSTD_DCtx* dctx, |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 632 | void* dst, size_t maxDstSize, |
| 633 | const void* src, size_t srcSize) |
| 634 | { |
| 635 | /* blockType == blockCompressed */ |
| 636 | const BYTE* ip = (const BYTE*)src; |
| 637 | |
| 638 | /* Decode literals sub-block */ |
Yann Collet | 5b78d2f | 2015-11-12 15:36:05 +0100 | [diff] [blame] | 639 | size_t litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize); |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 640 | if (ZSTD_isError(litCSize)) return litCSize; |
| 641 | ip += litCSize; |
| 642 | srcSize -= litCSize; |
| 643 | |
Yann Collet | 5b78d2f | 2015-11-12 15:36:05 +0100 | [diff] [blame] | 644 | return ZSTD_decompressSequences(dctx, dst, maxDstSize, ip, srcSize); |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 645 | } |
| 646 | |
| 647 | |
Yann Collet | 5b78d2f | 2015-11-12 15:36:05 +0100 | [diff] [blame] | 648 | size_t ZSTD_decompressDCtx(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 649 | { |
| 650 | const BYTE* ip = (const BYTE*)src; |
| 651 | const BYTE* iend = ip + srcSize; |
| 652 | BYTE* const ostart = (BYTE* const)dst; |
| 653 | BYTE* op = ostart; |
| 654 | BYTE* const oend = ostart + maxDstSize; |
| 655 | size_t remainingSize = srcSize; |
| 656 | U32 magicNumber; |
| 657 | blockProperties_t blockProperties; |
| 658 | |
Yann Collet | 5b78d2f | 2015-11-12 15:36:05 +0100 | [diff] [blame] | 659 | |
Yann Collet | b254984 | 2015-11-18 11:29:32 +0100 | [diff] [blame] | 660 | /* init */ |
| 661 | ctx->base = ctx->vBase = ctx->dictEnd = dst; |
Yann Collet | 5b78d2f | 2015-11-12 15:36:05 +0100 | [diff] [blame] | 662 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 663 | /* Frame Header */ |
| 664 | if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong); |
| 665 | magicNumber = MEM_readLE32(src); |
| 666 | #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT==1) |
| 667 | if (ZSTD_isLegacy(magicNumber)) |
| 668 | return ZSTD_decompressLegacy(dst, maxDstSize, src, srcSize, magicNumber); |
| 669 | #endif |
| 670 | if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown); |
| 671 | ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize; |
| 672 | |
| 673 | /* Loop on each block */ |
| 674 | while (1) |
| 675 | { |
| 676 | size_t decodedSize=0; |
| 677 | size_t cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties); |
| 678 | if (ZSTD_isError(cBlockSize)) return cBlockSize; |
| 679 | |
| 680 | ip += ZSTD_blockHeaderSize; |
| 681 | remainingSize -= ZSTD_blockHeaderSize; |
| 682 | if (cBlockSize > remainingSize) return ERROR(srcSize_wrong); |
| 683 | |
| 684 | switch(blockProperties.blockType) |
| 685 | { |
| 686 | case bt_compressed: |
| 687 | decodedSize = ZSTD_decompressBlock(ctx, op, oend-op, ip, cBlockSize); |
| 688 | break; |
| 689 | case bt_raw : |
Yann Collet | 0f366c6 | 2015-11-12 16:19:30 +0100 | [diff] [blame] | 690 | decodedSize = ZSTD_copyRawBlock(op, oend-op, ip, cBlockSize); |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 691 | break; |
| 692 | case bt_rle : |
| 693 | return ERROR(GENERIC); /* not yet supported */ |
| 694 | break; |
| 695 | case bt_end : |
| 696 | /* end of frame */ |
| 697 | if (remainingSize) return ERROR(srcSize_wrong); |
| 698 | break; |
| 699 | default: |
| 700 | return ERROR(GENERIC); /* impossible */ |
| 701 | } |
| 702 | if (cBlockSize == 0) break; /* bt_end */ |
| 703 | |
| 704 | if (ZSTD_isError(decodedSize)) return decodedSize; |
| 705 | op += decodedSize; |
| 706 | ip += cBlockSize; |
| 707 | remainingSize -= cBlockSize; |
| 708 | } |
| 709 | |
| 710 | return op-ostart; |
| 711 | } |
| 712 | |
| 713 | size_t ZSTD_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize) |
| 714 | { |
| 715 | ZSTD_DCtx ctx; |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 716 | return ZSTD_decompressDCtx(&ctx, dst, maxDstSize, src, srcSize); |
| 717 | } |
| 718 | |
| 719 | |
| 720 | /* ****************************** |
| 721 | * Streaming Decompression API |
| 722 | ********************************/ |
| 723 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 724 | size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx) |
| 725 | { |
| 726 | return dctx->expected; |
| 727 | } |
| 728 | |
| 729 | size_t ZSTD_decompressContinue(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) |
| 730 | { |
| 731 | /* Sanity check */ |
| 732 | if (srcSize != ctx->expected) return ERROR(srcSize_wrong); |
| 733 | if (dst != ctx->previousDstEnd) /* not contiguous */ |
Yann Collet | 5b78d2f | 2015-11-12 15:36:05 +0100 | [diff] [blame] | 734 | { |
Yann Collet | b254984 | 2015-11-18 11:29:32 +0100 | [diff] [blame] | 735 | ctx->dictEnd = ctx->previousDstEnd; |
| 736 | if ((dst > ctx->base) && (dst < ctx->previousDstEnd)) /* rolling buffer : new segment right into tracked memory */ |
| 737 | ctx->base = (char*)dst + maxDstSize; /* temporary affectation, for vBase calculation */ |
| 738 | ctx->vBase = (char*)dst - ((char*)(ctx->dictEnd) - (char*)(ctx->base)); |
| 739 | ctx->base = dst; |
| 740 | } |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 741 | |
| 742 | /* Decompress : frame header */ |
| 743 | if (ctx->phase == 0) |
| 744 | { |
| 745 | /* Check frame magic header */ |
| 746 | U32 magicNumber = MEM_readLE32(src); |
| 747 | if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown); |
| 748 | ctx->phase = 1; |
| 749 | ctx->expected = ZSTD_blockHeaderSize; |
| 750 | return 0; |
| 751 | } |
| 752 | |
| 753 | /* Decompress : block header */ |
| 754 | if (ctx->phase == 1) |
| 755 | { |
| 756 | blockProperties_t bp; |
| 757 | size_t blockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp); |
| 758 | if (ZSTD_isError(blockSize)) return blockSize; |
| 759 | if (bp.blockType == bt_end) |
| 760 | { |
| 761 | ctx->expected = 0; |
| 762 | ctx->phase = 0; |
| 763 | } |
| 764 | else |
| 765 | { |
| 766 | ctx->expected = blockSize; |
| 767 | ctx->bType = bp.blockType; |
| 768 | ctx->phase = 2; |
| 769 | } |
| 770 | |
Yann Collet | 0f366c6 | 2015-11-12 16:19:30 +0100 | [diff] [blame] | 771 | ctx->previousDstEnd = dst; |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 772 | return 0; |
| 773 | } |
| 774 | |
| 775 | /* Decompress : block content */ |
| 776 | { |
| 777 | size_t rSize; |
| 778 | switch(ctx->bType) |
| 779 | { |
| 780 | case bt_compressed: |
| 781 | rSize = ZSTD_decompressBlock(ctx, dst, maxDstSize, src, srcSize); |
| 782 | break; |
| 783 | case bt_raw : |
Yann Collet | 0f366c6 | 2015-11-12 16:19:30 +0100 | [diff] [blame] | 784 | rSize = ZSTD_copyRawBlock(dst, maxDstSize, src, srcSize); |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 785 | break; |
| 786 | case bt_rle : |
| 787 | return ERROR(GENERIC); /* not yet handled */ |
| 788 | break; |
| 789 | case bt_end : /* should never happen (filtered at phase 1) */ |
| 790 | rSize = 0; |
| 791 | break; |
| 792 | default: |
| 793 | return ERROR(GENERIC); |
| 794 | } |
| 795 | ctx->phase = 1; |
| 796 | ctx->expected = ZSTD_blockHeaderSize; |
Yann Collet | 5b78d2f | 2015-11-12 15:36:05 +0100 | [diff] [blame] | 797 | ctx->previousDstEnd = (char*)dst + rSize; |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 798 | return rSize; |
| 799 | } |
| 800 | |
| 801 | } |
| 802 | |
| 803 | |