1 /* 2 * Copyright (c) Yann Collet, Meta Platforms, Inc. and affiliates. 3 * All rights reserved. 4 * 5 * This source code is licensed under both the BSD-style license (found in the 6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found 7 * in the COPYING file in the root directory of this source tree). 8 * You may select, at your option, one of the above-listed licenses. 9 */ 10 11 12 /****************************************** 13 * Includes 14 ******************************************/ 15 #include <stddef.h> /* size_t, ptrdiff_t */ 16 #include "zstd_v01.h" 17 #include "../common/compiler.h" 18 #include "../common/error_private.h" 19 20 21 /****************************************** 22 * Static allocation 23 ******************************************/ 24 /* You can statically allocate FSE CTable/DTable as a table of unsigned using below macro */ 25 #define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog)) 26 27 /* You can statically allocate Huff0 DTable as a table of unsigned short using below macro */ 28 #define HUF_DTABLE_SIZE_U16(maxTableLog) (1 + (1<<maxTableLog)) 29 #define HUF_CREATE_STATIC_DTABLE(DTable, maxTableLog) \ 30 unsigned short DTable[HUF_DTABLE_SIZE_U16(maxTableLog)] = { maxTableLog } 31 32 33 /****************************************** 34 * Error Management 35 ******************************************/ 36 #define FSE_LIST_ERRORS(ITEM) \ 37 ITEM(FSE_OK_NoError) ITEM(FSE_ERROR_GENERIC) \ 38 ITEM(FSE_ERROR_tableLog_tooLarge) ITEM(FSE_ERROR_maxSymbolValue_tooLarge) ITEM(FSE_ERROR_maxSymbolValue_tooSmall) \ 39 ITEM(FSE_ERROR_dstSize_tooSmall) ITEM(FSE_ERROR_srcSize_wrong)\ 40 ITEM(FSE_ERROR_corruptionDetected) \ 41 ITEM(FSE_ERROR_maxCode) 42 43 #define FSE_GENERATE_ENUM(ENUM) ENUM, 44 typedef enum { FSE_LIST_ERRORS(FSE_GENERATE_ENUM) } FSE_errorCodes; /* enum is exposed, to detect & handle specific errors; compare function result to -enum value */ 45 46 47 /****************************************** 48 * FSE symbol compression API 49 ******************************************/ 50 /* 51 This API consists of small unitary functions, which highly benefit from being inlined. 52 You will want to enable link-time-optimization to ensure these functions are properly inlined in your binary. 53 Visual seems to do it automatically. 54 For gcc or clang, you'll need to add -flto flag at compilation and linking stages. 55 If none of these solutions is applicable, include "fse.c" directly. 56 */ 57 58 typedef unsigned FSE_CTable; /* don't allocate that. It's just a way to be more restrictive than void* */ 59 typedef unsigned FSE_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */ 60 61 typedef struct 62 { 63 size_t bitContainer; 64 int bitPos; 65 char* startPtr; 66 char* ptr; 67 char* endPtr; 68 } FSE_CStream_t; 69 70 typedef struct 71 { 72 ptrdiff_t value; 73 const void* stateTable; 74 const void* symbolTT; 75 unsigned stateLog; 76 } FSE_CState_t; 77 78 typedef struct 79 { 80 size_t bitContainer; 81 unsigned bitsConsumed; 82 const char* ptr; 83 const char* start; 84 } FSE_DStream_t; 85 86 typedef struct 87 { 88 size_t state; 89 const void* table; /* precise table may vary, depending on U16 */ 90 } FSE_DState_t; 91 92 typedef enum { FSE_DStream_unfinished = 0, 93 FSE_DStream_endOfBuffer = 1, 94 FSE_DStream_completed = 2, 95 FSE_DStream_tooFar = 3 } FSE_DStream_status; /* result of FSE_reloadDStream() */ 96 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... ?! */ 97 98 99 /**************************************************************** 100 * Tuning parameters 101 ****************************************************************/ 102 /* MEMORY_USAGE : 103 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.) 104 * Increasing memory usage improves compression ratio 105 * Reduced memory usage can improve speed, due to cache effect 106 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */ 107 #define FSE_MAX_MEMORY_USAGE 14 108 #define FSE_DEFAULT_MEMORY_USAGE 13 109 110 /* FSE_MAX_SYMBOL_VALUE : 111 * Maximum symbol value authorized. 112 * Required for proper stack allocation */ 113 #define FSE_MAX_SYMBOL_VALUE 255 114 115 116 /**************************************************************** 117 * template functions type & suffix 118 ****************************************************************/ 119 #define FSE_FUNCTION_TYPE BYTE 120 #define FSE_FUNCTION_EXTENSION 121 122 123 /**************************************************************** 124 * Byte symbol type 125 ****************************************************************/ 126 typedef struct 127 { 128 unsigned short newState; 129 unsigned char symbol; 130 unsigned char nbBits; 131 } FSE_decode_t; /* size == U32 */ 132 133 134 135 /**************************************************************** 136 * Compiler specifics 137 ****************************************************************/ 138 #ifdef _MSC_VER /* Visual Studio */ 139 # define FORCE_INLINE static __forceinline 140 # include <intrin.h> /* For Visual 2005 */ 141 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 142 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */ 143 #else 144 # define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__) 145 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */ 146 # ifdef __GNUC__ 147 # define FORCE_INLINE static inline __attribute__((always_inline)) 148 # else 149 # define FORCE_INLINE static inline 150 # endif 151 # else 152 # define FORCE_INLINE static 153 # endif /* __STDC_VERSION__ */ 154 #endif 155 156 157 /**************************************************************** 158 * Includes 159 ****************************************************************/ 160 #include <stdlib.h> /* malloc, free, qsort */ 161 #include <string.h> /* memcpy, memset */ 162 #include <stdio.h> /* printf (debug) */ 163 164 165 #ifndef MEM_ACCESS_MODULE 166 #define MEM_ACCESS_MODULE 167 /**************************************************************** 168 * Basic Types 169 *****************************************************************/ 170 #if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */ 171 # include <stdint.h> 172 typedef uint8_t BYTE; 173 typedef uint16_t U16; 174 typedef int16_t S16; 175 typedef uint32_t U32; 176 typedef int32_t S32; 177 typedef uint64_t U64; 178 typedef int64_t S64; 179 #else 180 typedef unsigned char BYTE; 181 typedef unsigned short U16; 182 typedef signed short S16; 183 typedef unsigned int U32; 184 typedef signed int S32; 185 typedef unsigned long long U64; 186 typedef signed long long S64; 187 #endif 188 189 #endif /* MEM_ACCESS_MODULE */ 190 191 /**************************************************************** 192 * Memory I/O 193 *****************************************************************/ 194 195 static unsigned FSE_32bits(void) 196 { 197 return sizeof(void*)==4; 198 } 199 200 static unsigned FSE_isLittleEndian(void) 201 { 202 const union { U32 i; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */ 203 return one.c[0]; 204 } 205 206 static U16 FSE_read16(const void* memPtr) 207 { 208 U16 val; memcpy(&val, memPtr, sizeof(val)); return val; 209 } 210 211 static U32 FSE_read32(const void* memPtr) 212 { 213 U32 val; memcpy(&val, memPtr, sizeof(val)); return val; 214 } 215 216 static U64 FSE_read64(const void* memPtr) 217 { 218 U64 val; memcpy(&val, memPtr, sizeof(val)); return val; 219 } 220 221 static U16 FSE_readLE16(const void* memPtr) 222 { 223 if (FSE_isLittleEndian()) 224 return FSE_read16(memPtr); 225 else 226 { 227 const BYTE* p = (const BYTE*)memPtr; 228 return (U16)(p[0] + (p[1]<<8)); 229 } 230 } 231 232 static U32 FSE_readLE32(const void* memPtr) 233 { 234 if (FSE_isLittleEndian()) 235 return FSE_read32(memPtr); 236 else 237 { 238 const BYTE* p = (const BYTE*)memPtr; 239 return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24)); 240 } 241 } 242 243 244 static U64 FSE_readLE64(const void* memPtr) 245 { 246 if (FSE_isLittleEndian()) 247 return FSE_read64(memPtr); 248 else 249 { 250 const BYTE* p = (const BYTE*)memPtr; 251 return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24) 252 + ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56)); 253 } 254 } 255 256 static size_t FSE_readLEST(const void* memPtr) 257 { 258 if (FSE_32bits()) 259 return (size_t)FSE_readLE32(memPtr); 260 else 261 return (size_t)FSE_readLE64(memPtr); 262 } 263 264 265 266 /**************************************************************** 267 * Constants 268 *****************************************************************/ 269 #define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2) 270 #define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG) 271 #define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1) 272 #define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2) 273 #define FSE_MIN_TABLELOG 5 274 275 #define FSE_TABLELOG_ABSOLUTE_MAX 15 276 #if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX 277 #error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported" 278 #endif 279 280 281 /**************************************************************** 282 * Error Management 283 ****************************************************************/ 284 #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ 285 286 287 /**************************************************************** 288 * Complex types 289 ****************************************************************/ 290 typedef struct 291 { 292 int deltaFindState; 293 U32 deltaNbBits; 294 } FSE_symbolCompressionTransform; /* total 8 bytes */ 295 296 typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)]; 297 298 /**************************************************************** 299 * Internal functions 300 ****************************************************************/ 301 FORCE_INLINE unsigned FSE_highbit32 (U32 val) 302 { 303 # if defined(_MSC_VER) /* Visual */ 304 unsigned long r; 305 return _BitScanReverse(&r, val) ? (unsigned)r : 0; 306 # elif defined(__GNUC__) && (GCC_VERSION >= 304) /* GCC Intrinsic */ 307 return __builtin_clz (val) ^ 31; 308 # else /* Software version */ 309 static const unsigned DeBruijnClz[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 }; 310 U32 v = val; 311 unsigned r; 312 v |= v >> 1; 313 v |= v >> 2; 314 v |= v >> 4; 315 v |= v >> 8; 316 v |= v >> 16; 317 r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27]; 318 return r; 319 # endif 320 } 321 322 323 /**************************************************************** 324 * Templates 325 ****************************************************************/ 326 /* 327 designed to be included 328 for type-specific functions (template emulation in C) 329 Objective is to write these functions only once, for improved maintenance 330 */ 331 332 /* safety checks */ 333 #ifndef FSE_FUNCTION_EXTENSION 334 # error "FSE_FUNCTION_EXTENSION must be defined" 335 #endif 336 #ifndef FSE_FUNCTION_TYPE 337 # error "FSE_FUNCTION_TYPE must be defined" 338 #endif 339 340 /* Function names */ 341 #define FSE_CAT(X,Y) X##Y 342 #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y) 343 #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y) 344 345 346 347 static U32 FSE_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; } 348 349 #define FSE_DECODE_TYPE FSE_decode_t 350 351 352 typedef struct { 353 U16 tableLog; 354 U16 fastMode; 355 } FSE_DTableHeader; /* sizeof U32 */ 356 357 static size_t FSE_buildDTable 358 (FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog) 359 { 360 void* ptr = dt; 361 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr; 362 FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*)(ptr) + 1; /* because dt is unsigned, 32-bits aligned on 32-bits */ 363 const U32 tableSize = 1 << tableLog; 364 const U32 tableMask = tableSize-1; 365 const U32 step = FSE_tableStep(tableSize); 366 U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1]; 367 U32 position = 0; 368 U32 highThreshold = tableSize-1; 369 const S16 largeLimit= (S16)(1 << (tableLog-1)); 370 U32 noLarge = 1; 371 U32 s; 372 373 /* Sanity Checks */ 374 if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return (size_t)-FSE_ERROR_maxSymbolValue_tooLarge; 375 if (tableLog > FSE_MAX_TABLELOG) return (size_t)-FSE_ERROR_tableLog_tooLarge; 376 377 /* Init, lay down lowprob symbols */ 378 DTableH[0].tableLog = (U16)tableLog; 379 for (s=0; s<=maxSymbolValue; s++) 380 { 381 if (normalizedCounter[s]==-1) 382 { 383 tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s; 384 symbolNext[s] = 1; 385 } 386 else 387 { 388 if (normalizedCounter[s] >= largeLimit) noLarge=0; 389 symbolNext[s] = normalizedCounter[s]; 390 } 391 } 392 393 /* Spread symbols */ 394 for (s=0; s<=maxSymbolValue; s++) 395 { 396 int i; 397 for (i=0; i<normalizedCounter[s]; i++) 398 { 399 tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s; 400 position = (position + step) & tableMask; 401 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */ 402 } 403 } 404 405 if (position!=0) return (size_t)-FSE_ERROR_GENERIC; /* position must reach all cells once, otherwise normalizedCounter is incorrect */ 406 407 /* Build Decoding table */ 408 { 409 U32 i; 410 for (i=0; i<tableSize; i++) 411 { 412 FSE_FUNCTION_TYPE symbol = (FSE_FUNCTION_TYPE)(tableDecode[i].symbol); 413 U16 nextState = symbolNext[symbol]++; 414 tableDecode[i].nbBits = (BYTE) (tableLog - FSE_highbit32 ((U32)nextState) ); 415 tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize); 416 } 417 } 418 419 DTableH->fastMode = (U16)noLarge; 420 return 0; 421 } 422 423 424 /****************************************** 425 * FSE byte symbol 426 ******************************************/ 427 #ifndef FSE_COMMONDEFS_ONLY 428 429 static unsigned FSE_isError(size_t code) { return (code > (size_t)(-FSE_ERROR_maxCode)); } 430 431 static short FSE_abs(short a) 432 { 433 return a<0? -a : a; 434 } 435 436 437 /**************************************************************** 438 * Header bitstream management 439 ****************************************************************/ 440 static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr, 441 const void* headerBuffer, size_t hbSize) 442 { 443 const BYTE* const istart = (const BYTE*) headerBuffer; 444 const BYTE* const iend = istart + hbSize; 445 const BYTE* ip = istart; 446 int nbBits; 447 int remaining; 448 int threshold; 449 U32 bitStream; 450 int bitCount; 451 unsigned charnum = 0; 452 int previous0 = 0; 453 454 if (hbSize < 4) return (size_t)-FSE_ERROR_srcSize_wrong; 455 bitStream = FSE_readLE32(ip); 456 nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */ 457 if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return (size_t)-FSE_ERROR_tableLog_tooLarge; 458 bitStream >>= 4; 459 bitCount = 4; 460 *tableLogPtr = nbBits; 461 remaining = (1<<nbBits)+1; 462 threshold = 1<<nbBits; 463 nbBits++; 464 465 while ((remaining>1) && (charnum<=*maxSVPtr)) 466 { 467 if (previous0) 468 { 469 unsigned n0 = charnum; 470 while ((bitStream & 0xFFFF) == 0xFFFF) 471 { 472 n0+=24; 473 if (ip < iend-5) 474 { 475 ip+=2; 476 bitStream = FSE_readLE32(ip) >> bitCount; 477 } 478 else 479 { 480 bitStream >>= 16; 481 bitCount+=16; 482 } 483 } 484 while ((bitStream & 3) == 3) 485 { 486 n0+=3; 487 bitStream>>=2; 488 bitCount+=2; 489 } 490 n0 += bitStream & 3; 491 bitCount += 2; 492 if (n0 > *maxSVPtr) return (size_t)-FSE_ERROR_maxSymbolValue_tooSmall; 493 while (charnum < n0) normalizedCounter[charnum++] = 0; 494 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) 495 { 496 ip += bitCount>>3; 497 bitCount &= 7; 498 bitStream = FSE_readLE32(ip) >> bitCount; 499 } 500 else 501 bitStream >>= 2; 502 } 503 { 504 const short max = (short)((2*threshold-1)-remaining); 505 short count; 506 507 if ((bitStream & (threshold-1)) < (U32)max) 508 { 509 count = (short)(bitStream & (threshold-1)); 510 bitCount += nbBits-1; 511 } 512 else 513 { 514 count = (short)(bitStream & (2*threshold-1)); 515 if (count >= threshold) count -= max; 516 bitCount += nbBits; 517 } 518 519 count--; /* extra accuracy */ 520 remaining -= FSE_abs(count); 521 normalizedCounter[charnum++] = count; 522 previous0 = !count; 523 while (remaining < threshold) 524 { 525 nbBits--; 526 threshold >>= 1; 527 } 528 529 { 530 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) 531 { 532 ip += bitCount>>3; 533 bitCount &= 7; 534 } 535 else 536 { 537 bitCount -= (int)(8 * (iend - 4 - ip)); 538 ip = iend - 4; 539 } 540 bitStream = FSE_readLE32(ip) >> (bitCount & 31); 541 } 542 } 543 } 544 if (remaining != 1) return (size_t)-FSE_ERROR_GENERIC; 545 *maxSVPtr = charnum-1; 546 547 ip += (bitCount+7)>>3; 548 if ((size_t)(ip-istart) > hbSize) return (size_t)-FSE_ERROR_srcSize_wrong; 549 return ip-istart; 550 } 551 552 553 /********************************************************* 554 * Decompression (Byte symbols) 555 *********************************************************/ 556 static size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue) 557 { 558 void* ptr = dt; 559 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr; 560 FSE_decode_t* const cell = (FSE_decode_t*)(ptr) + 1; /* because dt is unsigned */ 561 562 DTableH->tableLog = 0; 563 DTableH->fastMode = 0; 564 565 cell->newState = 0; 566 cell->symbol = symbolValue; 567 cell->nbBits = 0; 568 569 return 0; 570 } 571 572 573 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits) 574 { 575 void* ptr = dt; 576 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr; 577 FSE_decode_t* const dinfo = (FSE_decode_t*)(ptr) + 1; /* because dt is unsigned */ 578 const unsigned tableSize = 1 << nbBits; 579 const unsigned tableMask = tableSize - 1; 580 const unsigned maxSymbolValue = tableMask; 581 unsigned s; 582 583 /* Sanity checks */ 584 if (nbBits < 1) return (size_t)-FSE_ERROR_GENERIC; /* min size */ 585 586 /* Build Decoding Table */ 587 DTableH->tableLog = (U16)nbBits; 588 DTableH->fastMode = 1; 589 for (s=0; s<=maxSymbolValue; s++) 590 { 591 dinfo[s].newState = 0; 592 dinfo[s].symbol = (BYTE)s; 593 dinfo[s].nbBits = (BYTE)nbBits; 594 } 595 596 return 0; 597 } 598 599 600 /* FSE_initDStream 601 * Initialize a FSE_DStream_t. 602 * srcBuffer must point at the beginning of an FSE block. 603 * The function result is the size of the FSE_block (== srcSize). 604 * If srcSize is too small, the function will return an errorCode; 605 */ 606 static size_t FSE_initDStream(FSE_DStream_t* bitD, const void* srcBuffer, size_t srcSize) 607 { 608 if (srcSize < 1) return (size_t)-FSE_ERROR_srcSize_wrong; 609 610 if (srcSize >= sizeof(size_t)) 611 { 612 U32 contain32; 613 bitD->start = (const char*)srcBuffer; 614 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t); 615 bitD->bitContainer = FSE_readLEST(bitD->ptr); 616 contain32 = ((const BYTE*)srcBuffer)[srcSize-1]; 617 if (contain32 == 0) return (size_t)-FSE_ERROR_GENERIC; /* stop bit not present */ 618 bitD->bitsConsumed = 8 - FSE_highbit32(contain32); 619 } 620 else 621 { 622 U32 contain32; 623 bitD->start = (const char*)srcBuffer; 624 bitD->ptr = bitD->start; 625 bitD->bitContainer = *(const BYTE*)(bitD->start); 626 switch(srcSize) 627 { 628 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16); 629 /* fallthrough */ 630 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24); 631 /* fallthrough */ 632 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32); 633 /* fallthrough */ 634 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24; 635 /* fallthrough */ 636 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16; 637 /* fallthrough */ 638 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8; 639 /* fallthrough */ 640 default:; 641 } 642 contain32 = ((const BYTE*)srcBuffer)[srcSize-1]; 643 if (contain32 == 0) return (size_t)-FSE_ERROR_GENERIC; /* stop bit not present */ 644 bitD->bitsConsumed = 8 - FSE_highbit32(contain32); 645 bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8; 646 } 647 648 return srcSize; 649 } 650 651 652 /*!FSE_lookBits 653 * Provides next n bits from the bitContainer. 654 * bitContainer is not modified (bits are still present for next read/look) 655 * On 32-bits, maxNbBits==25 656 * On 64-bits, maxNbBits==57 657 * return : value extracted. 658 */ 659 static size_t FSE_lookBits(FSE_DStream_t* bitD, U32 nbBits) 660 { 661 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1; 662 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask); 663 } 664 665 static size_t FSE_lookBitsFast(FSE_DStream_t* bitD, U32 nbBits) /* only if nbBits >= 1 !! */ 666 { 667 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1; 668 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask); 669 } 670 671 static void FSE_skipBits(FSE_DStream_t* bitD, U32 nbBits) 672 { 673 bitD->bitsConsumed += nbBits; 674 } 675 676 677 /*!FSE_readBits 678 * Read next n bits from the bitContainer. 679 * On 32-bits, don't read more than maxNbBits==25 680 * On 64-bits, don't read more than maxNbBits==57 681 * Use the fast variant *only* if n >= 1. 682 * return : value extracted. 683 */ 684 static size_t FSE_readBits(FSE_DStream_t* bitD, U32 nbBits) 685 { 686 size_t value = FSE_lookBits(bitD, nbBits); 687 FSE_skipBits(bitD, nbBits); 688 return value; 689 } 690 691 static size_t FSE_readBitsFast(FSE_DStream_t* bitD, U32 nbBits) /* only if nbBits >= 1 !! */ 692 { 693 size_t value = FSE_lookBitsFast(bitD, nbBits); 694 FSE_skipBits(bitD, nbBits); 695 return value; 696 } 697 698 static unsigned FSE_reloadDStream(FSE_DStream_t* bitD) 699 { 700 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */ 701 return FSE_DStream_tooFar; 702 703 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) 704 { 705 bitD->ptr -= bitD->bitsConsumed >> 3; 706 bitD->bitsConsumed &= 7; 707 bitD->bitContainer = FSE_readLEST(bitD->ptr); 708 return FSE_DStream_unfinished; 709 } 710 if (bitD->ptr == bitD->start) 711 { 712 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return FSE_DStream_endOfBuffer; 713 return FSE_DStream_completed; 714 } 715 { 716 U32 nbBytes = bitD->bitsConsumed >> 3; 717 U32 result = FSE_DStream_unfinished; 718 if (bitD->ptr - nbBytes < bitD->start) 719 { 720 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */ 721 result = FSE_DStream_endOfBuffer; 722 } 723 bitD->ptr -= nbBytes; 724 bitD->bitsConsumed -= nbBytes*8; 725 bitD->bitContainer = FSE_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */ 726 return result; 727 } 728 } 729 730 731 static void FSE_initDState(FSE_DState_t* DStatePtr, FSE_DStream_t* bitD, const FSE_DTable* dt) 732 { 733 const void* ptr = dt; 734 const FSE_DTableHeader* const DTableH = (const FSE_DTableHeader*)ptr; 735 DStatePtr->state = FSE_readBits(bitD, DTableH->tableLog); 736 FSE_reloadDStream(bitD); 737 DStatePtr->table = dt + 1; 738 } 739 740 static BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, FSE_DStream_t* bitD) 741 { 742 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state]; 743 const U32 nbBits = DInfo.nbBits; 744 BYTE symbol = DInfo.symbol; 745 size_t lowBits = FSE_readBits(bitD, nbBits); 746 747 DStatePtr->state = DInfo.newState + lowBits; 748 return symbol; 749 } 750 751 static BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, FSE_DStream_t* bitD) 752 { 753 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state]; 754 const U32 nbBits = DInfo.nbBits; 755 BYTE symbol = DInfo.symbol; 756 size_t lowBits = FSE_readBitsFast(bitD, nbBits); 757 758 DStatePtr->state = DInfo.newState + lowBits; 759 return symbol; 760 } 761 762 /* FSE_endOfDStream 763 Tells if bitD has reached end of bitStream or not */ 764 765 static unsigned FSE_endOfDStream(const FSE_DStream_t* bitD) 766 { 767 return ((bitD->ptr == bitD->start) && (bitD->bitsConsumed == sizeof(bitD->bitContainer)*8)); 768 } 769 770 static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr) 771 { 772 return DStatePtr->state == 0; 773 } 774 775 776 FORCE_INLINE size_t FSE_decompress_usingDTable_generic( 777 void* dst, size_t maxDstSize, 778 const void* cSrc, size_t cSrcSize, 779 const FSE_DTable* dt, const unsigned fast) 780 { 781 BYTE* const ostart = (BYTE*) dst; 782 BYTE* op = ostart; 783 BYTE* const omax = op + maxDstSize; 784 BYTE* const olimit = omax-3; 785 786 FSE_DStream_t bitD; 787 FSE_DState_t state1; 788 FSE_DState_t state2; 789 size_t errorCode; 790 791 /* Init */ 792 errorCode = FSE_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */ 793 if (FSE_isError(errorCode)) return errorCode; 794 795 FSE_initDState(&state1, &bitD, dt); 796 FSE_initDState(&state2, &bitD, dt); 797 798 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD) 799 800 /* 4 symbols per loop */ 801 for ( ; (FSE_reloadDStream(&bitD)==FSE_DStream_unfinished) && (op<olimit) ; op+=4) 802 { 803 op[0] = FSE_GETSYMBOL(&state1); 804 805 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 806 FSE_reloadDStream(&bitD); 807 808 op[1] = FSE_GETSYMBOL(&state2); 809 810 if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 811 { if (FSE_reloadDStream(&bitD) > FSE_DStream_unfinished) { op+=2; break; } } 812 813 op[2] = FSE_GETSYMBOL(&state1); 814 815 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ 816 FSE_reloadDStream(&bitD); 817 818 op[3] = FSE_GETSYMBOL(&state2); 819 } 820 821 /* tail */ 822 /* note : FSE_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly FSE_DStream_completed */ 823 while (1) 824 { 825 if ( (FSE_reloadDStream(&bitD)>FSE_DStream_completed) || (op==omax) || (FSE_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state1))) ) 826 break; 827 828 *op++ = FSE_GETSYMBOL(&state1); 829 830 if ( (FSE_reloadDStream(&bitD)>FSE_DStream_completed) || (op==omax) || (FSE_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state2))) ) 831 break; 832 833 *op++ = FSE_GETSYMBOL(&state2); 834 } 835 836 /* end ? */ 837 if (FSE_endOfDStream(&bitD) && FSE_endOfDState(&state1) && FSE_endOfDState(&state2)) 838 return op-ostart; 839 840 if (op==omax) return (size_t)-FSE_ERROR_dstSize_tooSmall; /* dst buffer is full, but cSrc unfinished */ 841 842 return (size_t)-FSE_ERROR_corruptionDetected; 843 } 844 845 846 static size_t FSE_decompress_usingDTable(void* dst, size_t originalSize, 847 const void* cSrc, size_t cSrcSize, 848 const FSE_DTable* dt) 849 { 850 FSE_DTableHeader DTableH; 851 memcpy(&DTableH, dt, sizeof(DTableH)); /* memcpy() into local variable, to avoid strict aliasing warning */ 852 853 /* select fast mode (static) */ 854 if (DTableH.fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1); 855 return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0); 856 } 857 858 859 static size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize) 860 { 861 const BYTE* const istart = (const BYTE*)cSrc; 862 const BYTE* ip = istart; 863 short counting[FSE_MAX_SYMBOL_VALUE+1]; 864 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */ 865 unsigned tableLog; 866 unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE; 867 size_t errorCode; 868 869 if (cSrcSize<2) return (size_t)-FSE_ERROR_srcSize_wrong; /* too small input size */ 870 871 /* normal FSE decoding mode */ 872 errorCode = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize); 873 if (FSE_isError(errorCode)) return errorCode; 874 if (errorCode >= cSrcSize) return (size_t)-FSE_ERROR_srcSize_wrong; /* too small input size */ 875 ip += errorCode; 876 cSrcSize -= errorCode; 877 878 errorCode = FSE_buildDTable (dt, counting, maxSymbolValue, tableLog); 879 if (FSE_isError(errorCode)) return errorCode; 880 881 /* always return, even if it is an error code */ 882 return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt); 883 } 884 885 886 887 /* ******************************************************* 888 * Huff0 : Huffman block compression 889 *********************************************************/ 890 #define HUF_MAX_SYMBOL_VALUE 255 891 #define HUF_DEFAULT_TABLELOG 12 /* used by default, when not specified */ 892 #define HUF_MAX_TABLELOG 12 /* max possible tableLog; for allocation purpose; can be modified */ 893 #define HUF_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */ 894 #if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG) 895 # error "HUF_MAX_TABLELOG is too large !" 896 #endif 897 898 typedef struct HUF_CElt_s { 899 U16 val; 900 BYTE nbBits; 901 } HUF_CElt ; 902 903 typedef struct nodeElt_s { 904 U32 count; 905 U16 parent; 906 BYTE byte; 907 BYTE nbBits; 908 } nodeElt; 909 910 911 /* ******************************************************* 912 * Huff0 : Huffman block decompression 913 *********************************************************/ 914 typedef struct { 915 BYTE byte; 916 BYTE nbBits; 917 } HUF_DElt; 918 919 static size_t HUF_readDTable (U16* DTable, const void* src, size_t srcSize) 920 { 921 BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1]; 922 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */ 923 U32 weightTotal; 924 U32 maxBits; 925 const BYTE* ip = (const BYTE*) src; 926 size_t iSize; 927 size_t oSize; 928 U32 n; 929 U32 nextRankStart; 930 void* ptr = DTable+1; 931 HUF_DElt* const dt = (HUF_DElt*)ptr; 932 933 if (!srcSize) return (size_t)-FSE_ERROR_srcSize_wrong; 934 iSize = ip[0]; 935 936 FSE_STATIC_ASSERT(sizeof(HUF_DElt) == sizeof(U16)); /* if compilation fails here, assertion is false */ 937 //memset(huffWeight, 0, sizeof(huffWeight)); /* should not be necessary, but some analyzer complain ... */ 938 if (iSize >= 128) /* special header */ 939 { 940 if (iSize >= (242)) /* RLE */ 941 { 942 static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 }; 943 oSize = l[iSize-242]; 944 memset(huffWeight, 1, sizeof(huffWeight)); 945 iSize = 0; 946 } 947 else /* Incompressible */ 948 { 949 oSize = iSize - 127; 950 iSize = ((oSize+1)/2); 951 if (iSize+1 > srcSize) return (size_t)-FSE_ERROR_srcSize_wrong; 952 ip += 1; 953 for (n=0; n<oSize; n+=2) 954 { 955 huffWeight[n] = ip[n/2] >> 4; 956 huffWeight[n+1] = ip[n/2] & 15; 957 } 958 } 959 } 960 else /* header compressed with FSE (normal case) */ 961 { 962 if (iSize+1 > srcSize) return (size_t)-FSE_ERROR_srcSize_wrong; 963 oSize = FSE_decompress(huffWeight, HUF_MAX_SYMBOL_VALUE, ip+1, iSize); /* max 255 values decoded, last one is implied */ 964 if (FSE_isError(oSize)) return oSize; 965 } 966 967 /* collect weight stats */ 968 memset(rankVal, 0, sizeof(rankVal)); 969 weightTotal = 0; 970 for (n=0; n<oSize; n++) 971 { 972 if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return (size_t)-FSE_ERROR_corruptionDetected; 973 rankVal[huffWeight[n]]++; 974 weightTotal += (1 << huffWeight[n]) >> 1; 975 } 976 if (weightTotal == 0) return (size_t)-FSE_ERROR_corruptionDetected; 977 978 /* get last non-null symbol weight (implied, total must be 2^n) */ 979 maxBits = FSE_highbit32(weightTotal) + 1; 980 if (maxBits > DTable[0]) return (size_t)-FSE_ERROR_tableLog_tooLarge; /* DTable is too small */ 981 DTable[0] = (U16)maxBits; 982 { 983 U32 total = 1 << maxBits; 984 U32 rest = total - weightTotal; 985 U32 verif = 1 << FSE_highbit32(rest); 986 U32 lastWeight = FSE_highbit32(rest) + 1; 987 if (verif != rest) return (size_t)-FSE_ERROR_corruptionDetected; /* last value must be a clean power of 2 */ 988 huffWeight[oSize] = (BYTE)lastWeight; 989 rankVal[lastWeight]++; 990 } 991 992 /* check tree construction validity */ 993 if ((rankVal[1] < 2) || (rankVal[1] & 1)) return (size_t)-FSE_ERROR_corruptionDetected; /* by construction : at least 2 elts of rank 1, must be even */ 994 995 /* Prepare ranks */ 996 nextRankStart = 0; 997 for (n=1; n<=maxBits; n++) 998 { 999 U32 current = nextRankStart; 1000 nextRankStart += (rankVal[n] << (n-1)); 1001 rankVal[n] = current; 1002 } 1003 1004 /* fill DTable */ 1005 for (n=0; n<=oSize; n++) 1006 { 1007 const U32 w = huffWeight[n]; 1008 const U32 length = (1 << w) >> 1; 1009 U32 i; 1010 HUF_DElt D; 1011 D.byte = (BYTE)n; D.nbBits = (BYTE)(maxBits + 1 - w); 1012 for (i = rankVal[w]; i < rankVal[w] + length; i++) 1013 dt[i] = D; 1014 rankVal[w] += length; 1015 } 1016 1017 return iSize+1; 1018 } 1019 1020 1021 static BYTE HUF_decodeSymbol(FSE_DStream_t* Dstream, const HUF_DElt* dt, const U32 dtLog) 1022 { 1023 const size_t val = FSE_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */ 1024 const BYTE c = dt[val].byte; 1025 FSE_skipBits(Dstream, dt[val].nbBits); 1026 return c; 1027 } 1028 1029 static size_t HUF_decompress_usingDTable( /* -3% slower when non static */ 1030 void* dst, size_t maxDstSize, 1031 const void* cSrc, size_t cSrcSize, 1032 const U16* DTable) 1033 { 1034 if (cSrcSize < 6) return (size_t)-FSE_ERROR_srcSize_wrong; 1035 { 1036 BYTE* const ostart = (BYTE*) dst; 1037 BYTE* op = ostart; 1038 BYTE* const omax = op + maxDstSize; 1039 BYTE* const olimit = maxDstSize < 15 ? op : omax-15; 1040 1041 const void* ptr = DTable; 1042 const HUF_DElt* const dt = (const HUF_DElt*)(ptr)+1; 1043 const U32 dtLog = DTable[0]; 1044 size_t errorCode; 1045 U32 reloadStatus; 1046 1047 /* Init */ 1048 1049 const U16* jumpTable = (const U16*)cSrc; 1050 const size_t length1 = FSE_readLE16(jumpTable); 1051 const size_t length2 = FSE_readLE16(jumpTable+1); 1052 const size_t length3 = FSE_readLE16(jumpTable+2); 1053 const size_t length4 = cSrcSize - 6 - length1 - length2 - length3; /* check coherency !! */ 1054 const char* const start1 = (const char*)(cSrc) + 6; 1055 const char* const start2 = start1 + length1; 1056 const char* const start3 = start2 + length2; 1057 const char* const start4 = start3 + length3; 1058 FSE_DStream_t bitD1, bitD2, bitD3, bitD4; 1059 1060 if (length1+length2+length3+6 >= cSrcSize) return (size_t)-FSE_ERROR_srcSize_wrong; 1061 1062 errorCode = FSE_initDStream(&bitD1, start1, length1); 1063 if (FSE_isError(errorCode)) return errorCode; 1064 errorCode = FSE_initDStream(&bitD2, start2, length2); 1065 if (FSE_isError(errorCode)) return errorCode; 1066 errorCode = FSE_initDStream(&bitD3, start3, length3); 1067 if (FSE_isError(errorCode)) return errorCode; 1068 errorCode = FSE_initDStream(&bitD4, start4, length4); 1069 if (FSE_isError(errorCode)) return errorCode; 1070 1071 reloadStatus=FSE_reloadDStream(&bitD2); 1072 1073 /* 16 symbols per loop */ 1074 for ( ; (reloadStatus<FSE_DStream_completed) && (op<olimit); /* D2-3-4 are supposed to be synchronized and finish together */ 1075 op+=16, reloadStatus = FSE_reloadDStream(&bitD2) | FSE_reloadDStream(&bitD3) | FSE_reloadDStream(&bitD4), FSE_reloadDStream(&bitD1)) 1076 { 1077 #define HUF_DECODE_SYMBOL_0(n, Dstream) \ 1078 op[n] = HUF_decodeSymbol(&Dstream, dt, dtLog); 1079 1080 #define HUF_DECODE_SYMBOL_1(n, Dstream) \ 1081 op[n] = HUF_decodeSymbol(&Dstream, dt, dtLog); \ 1082 if (FSE_32bits() && (HUF_MAX_TABLELOG>12)) FSE_reloadDStream(&Dstream) 1083 1084 #define HUF_DECODE_SYMBOL_2(n, Dstream) \ 1085 op[n] = HUF_decodeSymbol(&Dstream, dt, dtLog); \ 1086 if (FSE_32bits()) FSE_reloadDStream(&Dstream) 1087 1088 HUF_DECODE_SYMBOL_1( 0, bitD1); 1089 HUF_DECODE_SYMBOL_1( 1, bitD2); 1090 HUF_DECODE_SYMBOL_1( 2, bitD3); 1091 HUF_DECODE_SYMBOL_1( 3, bitD4); 1092 HUF_DECODE_SYMBOL_2( 4, bitD1); 1093 HUF_DECODE_SYMBOL_2( 5, bitD2); 1094 HUF_DECODE_SYMBOL_2( 6, bitD3); 1095 HUF_DECODE_SYMBOL_2( 7, bitD4); 1096 HUF_DECODE_SYMBOL_1( 8, bitD1); 1097 HUF_DECODE_SYMBOL_1( 9, bitD2); 1098 HUF_DECODE_SYMBOL_1(10, bitD3); 1099 HUF_DECODE_SYMBOL_1(11, bitD4); 1100 HUF_DECODE_SYMBOL_0(12, bitD1); 1101 HUF_DECODE_SYMBOL_0(13, bitD2); 1102 HUF_DECODE_SYMBOL_0(14, bitD3); 1103 HUF_DECODE_SYMBOL_0(15, bitD4); 1104 } 1105 1106 if (reloadStatus!=FSE_DStream_completed) /* not complete : some bitStream might be FSE_DStream_unfinished */ 1107 return (size_t)-FSE_ERROR_corruptionDetected; 1108 1109 /* tail */ 1110 { 1111 /* bitTail = bitD1; */ /* *much* slower : -20% !??! */ 1112 FSE_DStream_t bitTail; 1113 bitTail.ptr = bitD1.ptr; 1114 bitTail.bitsConsumed = bitD1.bitsConsumed; 1115 bitTail.bitContainer = bitD1.bitContainer; /* required in case of FSE_DStream_endOfBuffer */ 1116 bitTail.start = start1; 1117 for ( ; (FSE_reloadDStream(&bitTail) < FSE_DStream_completed) && (op<omax) ; op++) 1118 { 1119 HUF_DECODE_SYMBOL_0(0, bitTail); 1120 } 1121 1122 if (FSE_endOfDStream(&bitTail)) 1123 return op-ostart; 1124 } 1125 1126 if (op==omax) return (size_t)-FSE_ERROR_dstSize_tooSmall; /* dst buffer is full, but cSrc unfinished */ 1127 1128 return (size_t)-FSE_ERROR_corruptionDetected; 1129 } 1130 } 1131 1132 1133 static size_t HUF_decompress (void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize) 1134 { 1135 HUF_CREATE_STATIC_DTABLE(DTable, HUF_MAX_TABLELOG); 1136 const BYTE* ip = (const BYTE*) cSrc; 1137 size_t errorCode; 1138 1139 errorCode = HUF_readDTable (DTable, cSrc, cSrcSize); 1140 if (FSE_isError(errorCode)) return errorCode; 1141 if (errorCode >= cSrcSize) return (size_t)-FSE_ERROR_srcSize_wrong; 1142 ip += errorCode; 1143 cSrcSize -= errorCode; 1144 1145 return HUF_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, DTable); 1146 } 1147 1148 1149 #endif /* FSE_COMMONDEFS_ONLY */ 1150 1151 /* 1152 zstd - standard compression library 1153 Copyright (C) 2014-2015, Yann Collet. 1154 1155 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php) 1156 1157 Redistribution and use in source and binary forms, with or without 1158 modification, are permitted provided that the following conditions are 1159 met: 1160 * Redistributions of source code must retain the above copyright 1161 notice, this list of conditions and the following disclaimer. 1162 * Redistributions in binary form must reproduce the above 1163 copyright notice, this list of conditions and the following disclaimer 1164 in the documentation and/or other materials provided with the 1165 distribution. 1166 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1167 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1168 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1169 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1170 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 1171 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 1172 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1173 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1174 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 1175 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 1176 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 1177 1178 You can contact the author at : 1179 - zstd source repository : https://github.com/Cyan4973/zstd 1180 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c 1181 */ 1182 1183 /**************************************************************** 1184 * Tuning parameters 1185 *****************************************************************/ 1186 /* MEMORY_USAGE : 1187 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.) 1188 * Increasing memory usage improves compression ratio 1189 * Reduced memory usage can improve speed, due to cache effect */ 1190 #define ZSTD_MEMORY_USAGE 17 1191 1192 1193 /************************************** 1194 CPU Feature Detection 1195 **************************************/ 1196 /* 1197 * Automated efficient unaligned memory access detection 1198 * Based on known hardware architectures 1199 * This list will be updated thanks to feedbacks 1200 */ 1201 #if defined(CPU_HAS_EFFICIENT_UNALIGNED_MEMORY_ACCESS) \ 1202 || defined(__ARM_FEATURE_UNALIGNED) \ 1203 || defined(__i386__) || defined(__x86_64__) \ 1204 || defined(_M_IX86) || defined(_M_X64) \ 1205 || defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_8__) \ 1206 || (defined(_M_ARM) && (_M_ARM >= 7)) 1207 # define ZSTD_UNALIGNED_ACCESS 1 1208 #else 1209 # define ZSTD_UNALIGNED_ACCESS 0 1210 #endif 1211 1212 1213 /******************************************************** 1214 * Includes 1215 *********************************************************/ 1216 #include <stdlib.h> /* calloc */ 1217 #include <string.h> /* memcpy, memmove */ 1218 #include <stdio.h> /* debug : printf */ 1219 1220 1221 /******************************************************** 1222 * Compiler specifics 1223 *********************************************************/ 1224 #ifdef __AVX2__ 1225 # include <immintrin.h> /* AVX2 intrinsics */ 1226 #endif 1227 1228 #ifdef _MSC_VER /* Visual Studio */ 1229 # include <intrin.h> /* For Visual 2005 */ 1230 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 1231 # pragma warning(disable : 4324) /* disable: C4324: padded structure */ 1232 #endif 1233 1234 1235 #ifndef MEM_ACCESS_MODULE 1236 #define MEM_ACCESS_MODULE 1237 /******************************************************** 1238 * Basic Types 1239 *********************************************************/ 1240 #if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */ 1241 # if defined(_AIX) 1242 # include <inttypes.h> 1243 # else 1244 # include <stdint.h> /* intptr_t */ 1245 # endif 1246 typedef uint8_t BYTE; 1247 typedef uint16_t U16; 1248 typedef int16_t S16; 1249 typedef uint32_t U32; 1250 typedef int32_t S32; 1251 typedef uint64_t U64; 1252 #else 1253 typedef unsigned char BYTE; 1254 typedef unsigned short U16; 1255 typedef signed short S16; 1256 typedef unsigned int U32; 1257 typedef signed int S32; 1258 typedef unsigned long long U64; 1259 #endif 1260 1261 #endif /* MEM_ACCESS_MODULE */ 1262 1263 1264 /******************************************************** 1265 * Constants 1266 *********************************************************/ 1267 static const U32 ZSTD_magicNumber = 0xFD2FB51E; /* 3rd version : seqNb header */ 1268 1269 #define HASH_LOG (ZSTD_MEMORY_USAGE - 2) 1270 #define HASH_TABLESIZE (1 << HASH_LOG) 1271 #define HASH_MASK (HASH_TABLESIZE - 1) 1272 1273 #define KNUTH 2654435761 1274 1275 #define BIT7 128 1276 #define BIT6 64 1277 #define BIT5 32 1278 #define BIT4 16 1279 1280 #define KB *(1 <<10) 1281 #define MB *(1 <<20) 1282 #define GB *(1U<<30) 1283 1284 #define BLOCKSIZE (128 KB) /* define, for static allocation */ 1285 1286 #define WORKPLACESIZE (BLOCKSIZE*3) 1287 #define MINMATCH 4 1288 #define MLbits 7 1289 #define LLbits 6 1290 #define Offbits 5 1291 #define MaxML ((1<<MLbits )-1) 1292 #define MaxLL ((1<<LLbits )-1) 1293 #define MaxOff ((1<<Offbits)-1) 1294 #define LitFSELog 11 1295 #define MLFSELog 10 1296 #define LLFSELog 10 1297 #define OffFSELog 9 1298 #define MAX(a,b) ((a)<(b)?(b):(a)) 1299 #define MaxSeq MAX(MaxLL, MaxML) 1300 1301 #define LITERAL_NOENTROPY 63 1302 #define COMMAND_NOENTROPY 7 /* to remove */ 1303 1304 #define ZSTD_CONTENTSIZE_ERROR (0ULL - 2) 1305 1306 static const size_t ZSTD_blockHeaderSize = 3; 1307 static const size_t ZSTD_frameHeaderSize = 4; 1308 1309 1310 /******************************************************** 1311 * Memory operations 1312 *********************************************************/ 1313 static unsigned ZSTD_32bits(void) { return sizeof(void*)==4; } 1314 1315 static unsigned ZSTD_isLittleEndian(void) 1316 { 1317 const union { U32 i; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */ 1318 return one.c[0]; 1319 } 1320 1321 static U16 ZSTD_read16(const void* p) { U16 r; memcpy(&r, p, sizeof(r)); return r; } 1322 1323 static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); } 1324 1325 static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); } 1326 1327 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; } 1328 1329 static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length) 1330 { 1331 const BYTE* ip = (const BYTE*)src; 1332 BYTE* op = (BYTE*)dst; 1333 BYTE* const oend = op + length; 1334 while (op < oend) COPY8(op, ip); 1335 } 1336 1337 static U16 ZSTD_readLE16(const void* memPtr) 1338 { 1339 if (ZSTD_isLittleEndian()) return ZSTD_read16(memPtr); 1340 else 1341 { 1342 const BYTE* p = (const BYTE*)memPtr; 1343 return (U16)((U16)p[0] + ((U16)p[1]<<8)); 1344 } 1345 } 1346 1347 static U32 ZSTD_readLE24(const void* memPtr) 1348 { 1349 return ZSTD_readLE16(memPtr) + (((const BYTE*)memPtr)[2] << 16); 1350 } 1351 1352 static U32 ZSTD_readBE32(const void* memPtr) 1353 { 1354 const BYTE* p = (const BYTE*)memPtr; 1355 return (U32)(((U32)p[0]<<24) + ((U32)p[1]<<16) + ((U32)p[2]<<8) + ((U32)p[3]<<0)); 1356 } 1357 1358 1359 /************************************** 1360 * Local structures 1361 ***************************************/ 1362 typedef struct ZSTD_Cctx_s ZSTD_Cctx; 1363 1364 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t; 1365 1366 typedef struct 1367 { 1368 blockType_t blockType; 1369 U32 origSize; 1370 } blockProperties_t; 1371 1372 typedef struct { 1373 void* buffer; 1374 U32* offsetStart; 1375 U32* offset; 1376 BYTE* offCodeStart; 1377 BYTE* offCode; 1378 BYTE* litStart; 1379 BYTE* lit; 1380 BYTE* litLengthStart; 1381 BYTE* litLength; 1382 BYTE* matchLengthStart; 1383 BYTE* matchLength; 1384 BYTE* dumpsStart; 1385 BYTE* dumps; 1386 } seqStore_t; 1387 1388 1389 typedef struct ZSTD_Cctx_s 1390 { 1391 const BYTE* base; 1392 U32 current; 1393 U32 nextUpdate; 1394 seqStore_t seqStore; 1395 #ifdef __AVX2__ 1396 __m256i hashTable[HASH_TABLESIZE>>3]; 1397 #else 1398 U32 hashTable[HASH_TABLESIZE]; 1399 #endif 1400 BYTE buffer[WORKPLACESIZE]; 1401 } cctxi_t; 1402 1403 1404 1405 1406 /************************************** 1407 * Error Management 1408 **************************************/ 1409 /* published entry point */ 1410 unsigned ZSTDv01_isError(size_t code) { return ERR_isError(code); } 1411 1412 1413 /************************************** 1414 * Tool functions 1415 **************************************/ 1416 #define ZSTD_VERSION_MAJOR 0 /* for breaking interface changes */ 1417 #define ZSTD_VERSION_MINOR 1 /* for new (non-breaking) interface capabilities */ 1418 #define ZSTD_VERSION_RELEASE 3 /* for tweaks, bug-fixes, or development */ 1419 #define ZSTD_VERSION_NUMBER (ZSTD_VERSION_MAJOR *100*100 + ZSTD_VERSION_MINOR *100 + ZSTD_VERSION_RELEASE) 1420 1421 /************************************************************** 1422 * Decompression code 1423 **************************************************************/ 1424 1425 static size_t ZSTDv01_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr) 1426 { 1427 const BYTE* const in = (const BYTE* const)src; 1428 BYTE headerFlags; 1429 U32 cSize; 1430 1431 if (srcSize < 3) return ERROR(srcSize_wrong); 1432 1433 headerFlags = *in; 1434 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16); 1435 1436 bpPtr->blockType = (blockType_t)(headerFlags >> 6); 1437 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0; 1438 1439 if (bpPtr->blockType == bt_end) return 0; 1440 if (bpPtr->blockType == bt_rle) return 1; 1441 return cSize; 1442 } 1443 1444 1445 static size_t ZSTD_copyUncompressedBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize) 1446 { 1447 if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall); 1448 if (srcSize > 0) { 1449 memcpy(dst, src, srcSize); 1450 } 1451 return srcSize; 1452 } 1453 1454 1455 static size_t ZSTD_decompressLiterals(void* ctx, 1456 void* dst, size_t maxDstSize, 1457 const void* src, size_t srcSize) 1458 { 1459 BYTE* op = (BYTE*)dst; 1460 BYTE* const oend = op + maxDstSize; 1461 const BYTE* ip = (const BYTE*)src; 1462 size_t errorCode; 1463 size_t litSize; 1464 1465 /* check : minimum 2, for litSize, +1, for content */ 1466 if (srcSize <= 3) return ERROR(corruption_detected); 1467 1468 litSize = ip[1] + (ip[0]<<8); 1469 litSize += ((ip[-3] >> 3) & 7) << 16; /* mmmmh.... */ 1470 op = oend - litSize; 1471 1472 (void)ctx; 1473 if (litSize > maxDstSize) return ERROR(dstSize_tooSmall); 1474 errorCode = HUF_decompress(op, litSize, ip+2, srcSize-2); 1475 if (FSE_isError(errorCode)) return ERROR(GENERIC); 1476 return litSize; 1477 } 1478 1479 1480 static size_t ZSTDv01_decodeLiteralsBlock(void* ctx, 1481 void* dst, size_t maxDstSize, 1482 const BYTE** litStart, size_t* litSize, 1483 const void* src, size_t srcSize) 1484 { 1485 const BYTE* const istart = (const BYTE* const)src; 1486 const BYTE* ip = istart; 1487 BYTE* const ostart = (BYTE* const)dst; 1488 BYTE* const oend = ostart + maxDstSize; 1489 blockProperties_t litbp; 1490 1491 size_t litcSize = ZSTDv01_getcBlockSize(src, srcSize, &litbp); 1492 if (ZSTDv01_isError(litcSize)) return litcSize; 1493 if (litcSize > srcSize - ZSTD_blockHeaderSize) return ERROR(srcSize_wrong); 1494 ip += ZSTD_blockHeaderSize; 1495 1496 switch(litbp.blockType) 1497 { 1498 case bt_raw: 1499 *litStart = ip; 1500 ip += litcSize; 1501 *litSize = litcSize; 1502 break; 1503 case bt_rle: 1504 { 1505 size_t rleSize = litbp.origSize; 1506 if (rleSize>maxDstSize) return ERROR(dstSize_tooSmall); 1507 if (!srcSize) return ERROR(srcSize_wrong); 1508 if (rleSize > 0) { 1509 memset(oend - rleSize, *ip, rleSize); 1510 } 1511 *litStart = oend - rleSize; 1512 *litSize = rleSize; 1513 ip++; 1514 break; 1515 } 1516 case bt_compressed: 1517 { 1518 size_t decodedLitSize = ZSTD_decompressLiterals(ctx, dst, maxDstSize, ip, litcSize); 1519 if (ZSTDv01_isError(decodedLitSize)) return decodedLitSize; 1520 *litStart = oend - decodedLitSize; 1521 *litSize = decodedLitSize; 1522 ip += litcSize; 1523 break; 1524 } 1525 case bt_end: 1526 default: 1527 return ERROR(GENERIC); 1528 } 1529 1530 return ip-istart; 1531 } 1532 1533 1534 static size_t ZSTDv01_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr, 1535 FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb, 1536 const void* src, size_t srcSize) 1537 { 1538 const BYTE* const istart = (const BYTE* const)src; 1539 const BYTE* ip = istart; 1540 const BYTE* const iend = istart + srcSize; 1541 U32 LLtype, Offtype, MLtype; 1542 U32 LLlog, Offlog, MLlog; 1543 size_t dumpsLength; 1544 1545 /* check */ 1546 if (srcSize < 5) return ERROR(srcSize_wrong); 1547 1548 /* SeqHead */ 1549 *nbSeq = ZSTD_readLE16(ip); ip+=2; 1550 LLtype = *ip >> 6; 1551 Offtype = (*ip >> 4) & 3; 1552 MLtype = (*ip >> 2) & 3; 1553 if (*ip & 2) 1554 { 1555 dumpsLength = ip[2]; 1556 dumpsLength += ip[1] << 8; 1557 ip += 3; 1558 } 1559 else 1560 { 1561 dumpsLength = ip[1]; 1562 dumpsLength += (ip[0] & 1) << 8; 1563 ip += 2; 1564 } 1565 *dumpsPtr = ip; 1566 ip += dumpsLength; 1567 *dumpsLengthPtr = dumpsLength; 1568 1569 /* check */ 1570 if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */ 1571 1572 /* sequences */ 1573 { 1574 S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL and MaxOff */ 1575 size_t headerSize; 1576 1577 /* Build DTables */ 1578 switch(LLtype) 1579 { 1580 case bt_rle : 1581 LLlog = 0; 1582 FSE_buildDTable_rle(DTableLL, *ip++); break; 1583 case bt_raw : 1584 LLlog = LLbits; 1585 FSE_buildDTable_raw(DTableLL, LLbits); break; 1586 default : 1587 { U32 max = MaxLL; 1588 headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip); 1589 if (FSE_isError(headerSize)) return ERROR(GENERIC); 1590 if (LLlog > LLFSELog) return ERROR(corruption_detected); 1591 ip += headerSize; 1592 FSE_buildDTable(DTableLL, norm, max, LLlog); 1593 } } 1594 1595 switch(Offtype) 1596 { 1597 case bt_rle : 1598 Offlog = 0; 1599 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */ 1600 FSE_buildDTable_rle(DTableOffb, *ip++); break; 1601 case bt_raw : 1602 Offlog = Offbits; 1603 FSE_buildDTable_raw(DTableOffb, Offbits); break; 1604 default : 1605 { U32 max = MaxOff; 1606 headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip); 1607 if (FSE_isError(headerSize)) return ERROR(GENERIC); 1608 if (Offlog > OffFSELog) return ERROR(corruption_detected); 1609 ip += headerSize; 1610 FSE_buildDTable(DTableOffb, norm, max, Offlog); 1611 } } 1612 1613 switch(MLtype) 1614 { 1615 case bt_rle : 1616 MLlog = 0; 1617 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */ 1618 FSE_buildDTable_rle(DTableML, *ip++); break; 1619 case bt_raw : 1620 MLlog = MLbits; 1621 FSE_buildDTable_raw(DTableML, MLbits); break; 1622 default : 1623 { U32 max = MaxML; 1624 headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip); 1625 if (FSE_isError(headerSize)) return ERROR(GENERIC); 1626 if (MLlog > MLFSELog) return ERROR(corruption_detected); 1627 ip += headerSize; 1628 FSE_buildDTable(DTableML, norm, max, MLlog); 1629 } } } 1630 1631 return ip-istart; 1632 } 1633 1634 1635 typedef struct { 1636 size_t litLength; 1637 size_t offset; 1638 size_t matchLength; 1639 } seq_t; 1640 1641 typedef struct { 1642 FSE_DStream_t DStream; 1643 FSE_DState_t stateLL; 1644 FSE_DState_t stateOffb; 1645 FSE_DState_t stateML; 1646 size_t prevOffset; 1647 const BYTE* dumps; 1648 const BYTE* dumpsEnd; 1649 } seqState_t; 1650 1651 1652 static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState) 1653 { 1654 size_t litLength; 1655 size_t prevOffset; 1656 size_t offset; 1657 size_t matchLength; 1658 const BYTE* dumps = seqState->dumps; 1659 const BYTE* const de = seqState->dumpsEnd; 1660 1661 /* Literal length */ 1662 litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream)); 1663 prevOffset = litLength ? seq->offset : seqState->prevOffset; 1664 seqState->prevOffset = seq->offset; 1665 if (litLength == MaxLL) 1666 { 1667 const U32 add = dumps<de ? *dumps++ : 0; 1668 if (add < 255) litLength += add; 1669 else 1670 { 1671 if (dumps<=(de-3)) 1672 { 1673 litLength = ZSTD_readLE24(dumps); 1674 dumps += 3; 1675 } 1676 } 1677 } 1678 1679 /* Offset */ 1680 { 1681 U32 offsetCode, nbBits; 1682 offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); 1683 if (ZSTD_32bits()) FSE_reloadDStream(&(seqState->DStream)); 1684 nbBits = offsetCode - 1; 1685 if (offsetCode==0) nbBits = 0; /* cmove */ 1686 offset = ((size_t)1 << (nbBits & ((sizeof(offset)*8)-1))) + FSE_readBits(&(seqState->DStream), nbBits); 1687 if (ZSTD_32bits()) FSE_reloadDStream(&(seqState->DStream)); 1688 if (offsetCode==0) offset = prevOffset; 1689 } 1690 1691 /* MatchLength */ 1692 matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream)); 1693 if (matchLength == MaxML) 1694 { 1695 const U32 add = dumps<de ? *dumps++ : 0; 1696 if (add < 255) matchLength += add; 1697 else 1698 { 1699 if (dumps<=(de-3)) 1700 { 1701 matchLength = ZSTD_readLE24(dumps); 1702 dumps += 3; 1703 } 1704 } 1705 } 1706 matchLength += MINMATCH; 1707 1708 /* save result */ 1709 seq->litLength = litLength; 1710 seq->offset = offset; 1711 seq->matchLength = matchLength; 1712 seqState->dumps = dumps; 1713 } 1714 1715 1716 static size_t ZSTD_execSequence(BYTE* op, 1717 seq_t sequence, 1718 const BYTE** litPtr, const BYTE* const litLimit, 1719 BYTE* const base, BYTE* const oend) 1720 { 1721 static const int dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4}; /* added */ 1722 static const int dec64table[] = {8, 8, 8, 7, 8, 9,10,11}; /* subtracted */ 1723 const BYTE* const ostart = op; 1724 BYTE* const oLitEnd = op + sequence.litLength; 1725 const size_t litLength = sequence.litLength; 1726 BYTE* const endMatch = op + litLength + sequence.matchLength; /* risk : address space overflow (32-bits) */ 1727 const BYTE* const litEnd = *litPtr + litLength; 1728 1729 /* checks */ 1730 size_t const seqLength = sequence.litLength + sequence.matchLength; 1731 1732 if (seqLength > (size_t)(oend - op)) return ERROR(dstSize_tooSmall); 1733 if (sequence.litLength > (size_t)(litLimit - *litPtr)) return ERROR(corruption_detected); 1734 /* Now we know there are no overflow in literal nor match lengths, can use pointer checks */ 1735 if (sequence.offset > (U32)(oLitEnd - base)) return ERROR(corruption_detected); 1736 1737 if (endMatch > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */ 1738 if (litEnd > litLimit) return ERROR(corruption_detected); /* overRead beyond lit buffer */ 1739 if (sequence.matchLength > (size_t)(*litPtr-op)) return ERROR(dstSize_tooSmall); /* overwrite literal segment */ 1740 1741 /* copy Literals */ 1742 ZSTD_memmove(op, *litPtr, sequence.litLength); /* note : v0.1 seems to allow scenarios where output or input are close to end of buffer */ 1743 1744 op += litLength; 1745 *litPtr = litEnd; /* update for next sequence */ 1746 1747 /* check : last match must be at a minimum distance of 8 from end of dest buffer */ 1748 if (oend-op < 8) return ERROR(dstSize_tooSmall); 1749 1750 /* copy Match */ 1751 { 1752 const U32 overlapRisk = (((size_t)(litEnd - endMatch)) < 12); 1753 const BYTE* match = op - sequence.offset; /* possible underflow at op - offset ? */ 1754 size_t qutt = 12; 1755 U64 saved[2]; 1756 1757 /* check */ 1758 if (match < base) return ERROR(corruption_detected); 1759 if (sequence.offset > (size_t)base) return ERROR(corruption_detected); 1760 1761 /* save beginning of literal sequence, in case of write overlap */ 1762 if (overlapRisk) 1763 { 1764 if ((endMatch + qutt) > oend) qutt = oend-endMatch; 1765 memcpy(saved, endMatch, qutt); 1766 } 1767 1768 if (sequence.offset < 8) 1769 { 1770 const int dec64 = dec64table[sequence.offset]; 1771 op[0] = match[0]; 1772 op[1] = match[1]; 1773 op[2] = match[2]; 1774 op[3] = match[3]; 1775 match += dec32table[sequence.offset]; 1776 ZSTD_copy4(op+4, match); 1777 match -= dec64; 1778 } else { ZSTD_copy8(op, match); } 1779 op += 8; match += 8; 1780 1781 if (endMatch > oend-(16-MINMATCH)) 1782 { 1783 if (op < oend-8) 1784 { 1785 ZSTD_wildcopy(op, match, (oend-8) - op); 1786 match += (oend-8) - op; 1787 op = oend-8; 1788 } 1789 while (op<endMatch) *op++ = *match++; 1790 } 1791 else 1792 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */ 1793 1794 /* restore, in case of overlap */ 1795 if (overlapRisk) memcpy(endMatch, saved, qutt); 1796 } 1797 1798 return endMatch-ostart; 1799 } 1800 1801 typedef struct ZSTDv01_Dctx_s 1802 { 1803 U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)]; 1804 U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)]; 1805 U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)]; 1806 void* previousDstEnd; 1807 void* base; 1808 size_t expected; 1809 blockType_t bType; 1810 U32 phase; 1811 } dctx_t; 1812 1813 1814 static size_t ZSTD_decompressSequences( 1815 void* ctx, 1816 void* dst, size_t maxDstSize, 1817 const void* seqStart, size_t seqSize, 1818 const BYTE* litStart, size_t litSize) 1819 { 1820 dctx_t* dctx = (dctx_t*)ctx; 1821 const BYTE* ip = (const BYTE*)seqStart; 1822 const BYTE* const iend = ip + seqSize; 1823 BYTE* const ostart = (BYTE* const)dst; 1824 BYTE* op = ostart; 1825 BYTE* const oend = ostart + maxDstSize; 1826 size_t errorCode, dumpsLength; 1827 const BYTE* litPtr = litStart; 1828 const BYTE* const litEnd = litStart + litSize; 1829 int nbSeq; 1830 const BYTE* dumps; 1831 U32* DTableLL = dctx->LLTable; 1832 U32* DTableML = dctx->MLTable; 1833 U32* DTableOffb = dctx->OffTable; 1834 BYTE* const base = (BYTE*) (dctx->base); 1835 1836 /* Build Decoding Tables */ 1837 errorCode = ZSTDv01_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength, 1838 DTableLL, DTableML, DTableOffb, 1839 ip, iend-ip); 1840 if (ZSTDv01_isError(errorCode)) return errorCode; 1841 ip += errorCode; 1842 1843 /* Regen sequences */ 1844 { 1845 seq_t sequence; 1846 seqState_t seqState; 1847 1848 memset(&sequence, 0, sizeof(sequence)); 1849 seqState.dumps = dumps; 1850 seqState.dumpsEnd = dumps + dumpsLength; 1851 seqState.prevOffset = 1; 1852 errorCode = FSE_initDStream(&(seqState.DStream), ip, iend-ip); 1853 if (FSE_isError(errorCode)) return ERROR(corruption_detected); 1854 FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL); 1855 FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb); 1856 FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML); 1857 1858 for ( ; (FSE_reloadDStream(&(seqState.DStream)) <= FSE_DStream_completed) && (nbSeq>0) ; ) 1859 { 1860 size_t oneSeqSize; 1861 nbSeq--; 1862 ZSTD_decodeSequence(&sequence, &seqState); 1863 oneSeqSize = ZSTD_execSequence(op, sequence, &litPtr, litEnd, base, oend); 1864 if (ZSTDv01_isError(oneSeqSize)) return oneSeqSize; 1865 op += oneSeqSize; 1866 } 1867 1868 /* check if reached exact end */ 1869 if ( !FSE_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected); /* requested too much : data is corrupted */ 1870 if (nbSeq<0) return ERROR(corruption_detected); /* requested too many sequences : data is corrupted */ 1871 1872 /* last literal segment */ 1873 { 1874 size_t lastLLSize = litEnd - litPtr; 1875 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall); 1876 if (lastLLSize > 0) { 1877 if (op != litPtr) memmove(op, litPtr, lastLLSize); 1878 op += lastLLSize; 1879 } 1880 } 1881 } 1882 1883 return op-ostart; 1884 } 1885 1886 1887 static size_t ZSTD_decompressBlock( 1888 void* ctx, 1889 void* dst, size_t maxDstSize, 1890 const void* src, size_t srcSize) 1891 { 1892 /* blockType == blockCompressed, srcSize is trusted */ 1893 const BYTE* ip = (const BYTE*)src; 1894 const BYTE* litPtr = NULL; 1895 size_t litSize = 0; 1896 size_t errorCode; 1897 1898 /* Decode literals sub-block */ 1899 errorCode = ZSTDv01_decodeLiteralsBlock(ctx, dst, maxDstSize, &litPtr, &litSize, src, srcSize); 1900 if (ZSTDv01_isError(errorCode)) return errorCode; 1901 ip += errorCode; 1902 srcSize -= errorCode; 1903 1904 return ZSTD_decompressSequences(ctx, dst, maxDstSize, ip, srcSize, litPtr, litSize); 1905 } 1906 1907 1908 size_t ZSTDv01_decompressDCtx(void* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) 1909 { 1910 const BYTE* ip = (const BYTE*)src; 1911 const BYTE* iend = ip + srcSize; 1912 BYTE* const ostart = (BYTE* const)dst; 1913 BYTE* op = ostart; 1914 BYTE* const oend = ostart + maxDstSize; 1915 size_t remainingSize = srcSize; 1916 U32 magicNumber; 1917 size_t errorCode=0; 1918 blockProperties_t blockProperties; 1919 1920 /* Frame Header */ 1921 if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong); 1922 magicNumber = ZSTD_readBE32(src); 1923 if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown); 1924 ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize; 1925 1926 /* Loop on each block */ 1927 while (1) 1928 { 1929 size_t blockSize = ZSTDv01_getcBlockSize(ip, iend-ip, &blockProperties); 1930 if (ZSTDv01_isError(blockSize)) return blockSize; 1931 1932 ip += ZSTD_blockHeaderSize; 1933 remainingSize -= ZSTD_blockHeaderSize; 1934 if (blockSize > remainingSize) return ERROR(srcSize_wrong); 1935 1936 switch(blockProperties.blockType) 1937 { 1938 case bt_compressed: 1939 errorCode = ZSTD_decompressBlock(ctx, op, oend-op, ip, blockSize); 1940 break; 1941 case bt_raw : 1942 errorCode = ZSTD_copyUncompressedBlock(op, oend-op, ip, blockSize); 1943 break; 1944 case bt_rle : 1945 return ERROR(GENERIC); /* not yet supported */ 1946 break; 1947 case bt_end : 1948 /* end of frame */ 1949 if (remainingSize) return ERROR(srcSize_wrong); 1950 break; 1951 default: 1952 return ERROR(GENERIC); 1953 } 1954 if (blockSize == 0) break; /* bt_end */ 1955 1956 if (ZSTDv01_isError(errorCode)) return errorCode; 1957 op += errorCode; 1958 ip += blockSize; 1959 remainingSize -= blockSize; 1960 } 1961 1962 return op-ostart; 1963 } 1964 1965 size_t ZSTDv01_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize) 1966 { 1967 dctx_t ctx; 1968 ctx.base = dst; 1969 return ZSTDv01_decompressDCtx(&ctx, dst, maxDstSize, src, srcSize); 1970 } 1971 1972 /* ZSTD_errorFrameSizeInfoLegacy() : 1973 assumes `cSize` and `dBound` are _not_ NULL */ 1974 static void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret) 1975 { 1976 *cSize = ret; 1977 *dBound = ZSTD_CONTENTSIZE_ERROR; 1978 } 1979 1980 void ZSTDv01_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound) 1981 { 1982 const BYTE* ip = (const BYTE*)src; 1983 size_t remainingSize = srcSize; 1984 size_t nbBlocks = 0; 1985 U32 magicNumber; 1986 blockProperties_t blockProperties; 1987 1988 /* Frame Header */ 1989 if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) { 1990 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong)); 1991 return; 1992 } 1993 magicNumber = ZSTD_readBE32(src); 1994 if (magicNumber != ZSTD_magicNumber) { 1995 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown)); 1996 return; 1997 } 1998 ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize; 1999 2000 /* Loop on each block */ 2001 while (1) 2002 { 2003 size_t blockSize = ZSTDv01_getcBlockSize(ip, remainingSize, &blockProperties); 2004 if (ZSTDv01_isError(blockSize)) { 2005 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, blockSize); 2006 return; 2007 } 2008 2009 ip += ZSTD_blockHeaderSize; 2010 remainingSize -= ZSTD_blockHeaderSize; 2011 if (blockSize > remainingSize) { 2012 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong)); 2013 return; 2014 } 2015 2016 if (blockSize == 0) break; /* bt_end */ 2017 2018 ip += blockSize; 2019 remainingSize -= blockSize; 2020 nbBlocks++; 2021 } 2022 2023 *cSize = ip - (const BYTE*)src; 2024 *dBound = nbBlocks * BLOCKSIZE; 2025 } 2026 2027 /******************************* 2028 * Streaming Decompression API 2029 *******************************/ 2030 2031 size_t ZSTDv01_resetDCtx(ZSTDv01_Dctx* dctx) 2032 { 2033 dctx->expected = ZSTD_frameHeaderSize; 2034 dctx->phase = 0; 2035 dctx->previousDstEnd = NULL; 2036 dctx->base = NULL; 2037 return 0; 2038 } 2039 2040 ZSTDv01_Dctx* ZSTDv01_createDCtx(void) 2041 { 2042 ZSTDv01_Dctx* dctx = (ZSTDv01_Dctx*)malloc(sizeof(ZSTDv01_Dctx)); 2043 if (dctx==NULL) return NULL; 2044 ZSTDv01_resetDCtx(dctx); 2045 return dctx; 2046 } 2047 2048 size_t ZSTDv01_freeDCtx(ZSTDv01_Dctx* dctx) 2049 { 2050 free(dctx); 2051 return 0; 2052 } 2053 2054 size_t ZSTDv01_nextSrcSizeToDecompress(ZSTDv01_Dctx* dctx) 2055 { 2056 return ((dctx_t*)dctx)->expected; 2057 } 2058 2059 size_t ZSTDv01_decompressContinue(ZSTDv01_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) 2060 { 2061 dctx_t* ctx = (dctx_t*)dctx; 2062 2063 /* Sanity check */ 2064 if (srcSize != ctx->expected) return ERROR(srcSize_wrong); 2065 if (dst != ctx->previousDstEnd) /* not contiguous */ 2066 ctx->base = dst; 2067 2068 /* Decompress : frame header */ 2069 if (ctx->phase == 0) 2070 { 2071 /* Check frame magic header */ 2072 U32 magicNumber = ZSTD_readBE32(src); 2073 if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown); 2074 ctx->phase = 1; 2075 ctx->expected = ZSTD_blockHeaderSize; 2076 return 0; 2077 } 2078 2079 /* Decompress : block header */ 2080 if (ctx->phase == 1) 2081 { 2082 blockProperties_t bp; 2083 size_t blockSize = ZSTDv01_getcBlockSize(src, ZSTD_blockHeaderSize, &bp); 2084 if (ZSTDv01_isError(blockSize)) return blockSize; 2085 if (bp.blockType == bt_end) 2086 { 2087 ctx->expected = 0; 2088 ctx->phase = 0; 2089 } 2090 else 2091 { 2092 ctx->expected = blockSize; 2093 ctx->bType = bp.blockType; 2094 ctx->phase = 2; 2095 } 2096 2097 return 0; 2098 } 2099 2100 /* Decompress : block content */ 2101 { 2102 size_t rSize; 2103 switch(ctx->bType) 2104 { 2105 case bt_compressed: 2106 rSize = ZSTD_decompressBlock(ctx, dst, maxDstSize, src, srcSize); 2107 break; 2108 case bt_raw : 2109 rSize = ZSTD_copyUncompressedBlock(dst, maxDstSize, src, srcSize); 2110 break; 2111 case bt_rle : 2112 return ERROR(GENERIC); /* not yet handled */ 2113 break; 2114 case bt_end : /* should never happen (filtered at phase 1) */ 2115 rSize = 0; 2116 break; 2117 default: 2118 return ERROR(GENERIC); 2119 } 2120 ctx->phase = 1; 2121 ctx->expected = ZSTD_blockHeaderSize; 2122 if (ZSTDv01_isError(rSize)) return rSize; 2123 ctx->previousDstEnd = (void*)( ((char*)dst) + rSize); 2124 return rSize; 2125 } 2126 2127 } 2128