sys/contrib/zstd/lib/decompress/zstd_decompress_block.c

   1 /*
   2  * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
   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 /* zstd_decompress_block :
  12  * this module takes care of decompressing _compressed_ block */
  13
  14 /*-*******************************************************
  15 *  Dependencies
  16 *********************************************************/
  17 #include <string.h>      /* memcpy, memmove, memset */
  18 #include "compiler.h"    /* prefetch */
  19 #include "cpu.h"         /* bmi2 */
  20 #include "mem.h"         /* low level memory routines */
  21 #define FSE_STATIC_LINKING_ONLY
  22 #include "fse.h"
  23 #define HUF_STATIC_LINKING_ONLY
  24 #include "huf.h"
  25 #include "zstd_internal.h"
  26 #include "zstd_decompress_internal.h"   /* ZSTD_DCtx */
  27 #include "zstd_ddict.h"  /* ZSTD_DDictDictContent */
  28 #include "zstd_decompress_block.h"
  29
  30 /*_*******************************************************
  31 *  Macros
  32 **********************************************************/
  33
  34 /* These two optional macros force the use one way or another of the two
  35  * ZSTD_decompressSequences implementations. You can't force in both directions
  36  * at the same time.
  37  */
  38 #if defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
  39     defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
  40 #error "Cannot force the use of the short and the long ZSTD_decompressSequences variants!"
  41 #endif
  42
  43
  44 /*_*******************************************************
  45 *  Memory operations
  46 **********************************************************/
  47 static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
  48
  49
  50 /*-*************************************************************
  51  *   Block decoding
  52  ***************************************************************/
  53
  54 /*! ZSTD_getcBlockSize() :
  55  *  Provides the size of compressed block from block header `src` */
  56 size_t ZSTD_getcBlockSize(const void* src, size_t srcSize,
  57                           blockProperties_t* bpPtr)
  58 {
  59     RETURN_ERROR_IF(srcSize < ZSTD_blockHeaderSize, srcSize_wrong);
  60
  61     {   U32 const cBlockHeader = MEM_readLE24(src);
  62         U32 const cSize = cBlockHeader >> 3;
  63         bpPtr->lastBlock = cBlockHeader & 1;
  64         bpPtr->blockType = (blockType_e)((cBlockHeader >> 1) & 3);
  65         bpPtr->origSize = cSize;   /* only useful for RLE */
  66         if (bpPtr->blockType == bt_rle) return 1;
  67         RETURN_ERROR_IF(bpPtr->blockType == bt_reserved, corruption_detected);
  68         return cSize;
  69     }
  70 }
  71
  72
  73 /* Hidden declaration for fullbench */
  74 size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx,
  75                           const void* src, size_t srcSize);
  76 /*! ZSTD_decodeLiteralsBlock() :
  77  * @return : nb of bytes read from src (< srcSize )
  78  *  note : symbol not declared but exposed for fullbench */
  79 size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx,
  80                           const void* src, size_t srcSize)   /* note : srcSize < BLOCKSIZE */
  81 {
  82     RETURN_ERROR_IF(srcSize < MIN_CBLOCK_SIZE, corruption_detected);
  83
  84     {   const BYTE* const istart = (const BYTE*) src;
  85         symbolEncodingType_e const litEncType = (symbolEncodingType_e)(istart[0] & 3);
  86
  87         switch(litEncType)
  88         {
  89         case set_repeat:
  90             RETURN_ERROR_IF(dctx->litEntropy==0, dictionary_corrupted);
  91             /* fall-through */
  92
  93         case set_compressed:
  94             RETURN_ERROR_IF(srcSize < 5, corruption_detected, "srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for case 3");
  95             {   size_t lhSize, litSize, litCSize;
  96                 U32 singleStream=0;
  97                 U32 const lhlCode = (istart[0] >> 2) & 3;
  98                 U32 const lhc = MEM_readLE32(istart);
  99                 size_t hufSuccess;
 100                 switch(lhlCode)
 101                 {
 102                 case 0: case 1: default:   /* note : default is impossible, since lhlCode into [0..3] */
 103                     /* 2 - 2 - 10 - 10 */
 104                     singleStream = !lhlCode;
 105                     lhSize = 3;
 106                     litSize  = (lhc >> 4) & 0x3FF;
 107                     litCSize = (lhc >> 14) & 0x3FF;
 108                     break;
 109                 case 2:
 110                     /* 2 - 2 - 14 - 14 */
 111                     lhSize = 4;
 112                     litSize  = (lhc >> 4) & 0x3FFF;
 113                     litCSize = lhc >> 18;
 114                     break;
 115                 case 3:
 116                     /* 2 - 2 - 18 - 18 */
 117                     lhSize = 5;
 118                     litSize  = (lhc >> 4) & 0x3FFFF;
 119                     litCSize = (lhc >> 22) + (istart[4] << 10);
 120                     break;
 121                 }
 122                 RETURN_ERROR_IF(litSize > ZSTD_BLOCKSIZE_MAX, corruption_detected);
 123                 RETURN_ERROR_IF(litCSize + lhSize > srcSize, corruption_detected);
 124
 125                 /* prefetch huffman table if cold */
 126                 if (dctx->ddictIsCold && (litSize > 768 /* heuristic */)) {
 127                     PREFETCH_AREA(dctx->HUFptr, sizeof(dctx->entropy.hufTable));
 128                 }
 129
 130                 if (litEncType==set_repeat) {
 131                     if (singleStream) {
 132                         hufSuccess = HUF_decompress1X_usingDTable_bmi2(
 133                             dctx->litBuffer, litSize, istart+lhSize, litCSize,
 134                             dctx->HUFptr, dctx->bmi2);
 135                     } else {
 136                         hufSuccess = HUF_decompress4X_usingDTable_bmi2(
 137                             dctx->litBuffer, litSize, istart+lhSize, litCSize,
 138                             dctx->HUFptr, dctx->bmi2);
 139                     }
 140                 } else {
 141                     if (singleStream) {
 142 #if defined(HUF_FORCE_DECOMPRESS_X2)
 143                         hufSuccess = HUF_decompress1X_DCtx_wksp(
 144                             dctx->entropy.hufTable, dctx->litBuffer, litSize,
 145                             istart+lhSize, litCSize, dctx->workspace,
 146                             sizeof(dctx->workspace));
 147 #else
 148                         hufSuccess = HUF_decompress1X1_DCtx_wksp_bmi2(
 149                             dctx->entropy.hufTable, dctx->litBuffer, litSize,
 150                             istart+lhSize, litCSize, dctx->workspace,
 151                             sizeof(dctx->workspace), dctx->bmi2);
 152 #endif
 153                     } else {
 154                         hufSuccess = HUF_decompress4X_hufOnly_wksp_bmi2(
 155                             dctx->entropy.hufTable, dctx->litBuffer, litSize,
 156                             istart+lhSize, litCSize, dctx->workspace,
 157                             sizeof(dctx->workspace), dctx->bmi2);
 158                     }
 159                 }
 160
 161                 RETURN_ERROR_IF(HUF_isError(hufSuccess), corruption_detected);
 162
 163                 dctx->litPtr = dctx->litBuffer;
 164                 dctx->litSize = litSize;
 165                 dctx->litEntropy = 1;
 166                 if (litEncType==set_compressed) dctx->HUFptr = dctx->entropy.hufTable;
 167                 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
 168                 return litCSize + lhSize;
 169             }
 170
 171         case set_basic:
 172             {   size_t litSize, lhSize;
 173                 U32 const lhlCode = ((istart[0]) >> 2) & 3;
 174                 switch(lhlCode)
 175                 {
 176                 case 0: case 2: default:   /* note : default is impossible, since lhlCode into [0..3] */
 177                     lhSize = 1;
 178                     litSize = istart[0] >> 3;
 179                     break;
 180                 case 1:
 181                     lhSize = 2;
 182                     litSize = MEM_readLE16(istart) >> 4;
 183                     break;
 184                 case 3:
 185                     lhSize = 3;
 186                     litSize = MEM_readLE24(istart) >> 4;
 187                     break;
 188                 }
 189
 190                 if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) {  /* risk reading beyond src buffer with wildcopy */
 191                     RETURN_ERROR_IF(litSize+lhSize > srcSize, corruption_detected);
 192                     memcpy(dctx->litBuffer, istart+lhSize, litSize);
 193                     dctx->litPtr = dctx->litBuffer;
 194                     dctx->litSize = litSize;
 195                     memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
 196                     return lhSize+litSize;
 197                 }
 198                 /* direct reference into compressed stream */
 199                 dctx->litPtr = istart+lhSize;
 200                 dctx->litSize = litSize;
 201                 return lhSize+litSize;
 202             }
 203
 204         case set_rle:
 205             {   U32 const lhlCode = ((istart[0]) >> 2) & 3;
 206                 size_t litSize, lhSize;
 207                 switch(lhlCode)
 208                 {
 209                 case 0: case 2: default:   /* note : default is impossible, since lhlCode into [0..3] */
 210                     lhSize = 1;
 211                     litSize = istart[0] >> 3;
 212                     break;
 213                 case 1:
 214                     lhSize = 2;
 215                     litSize = MEM_readLE16(istart) >> 4;
 216                     break;
 217                 case 3:
 218                     lhSize = 3;
 219                     litSize = MEM_readLE24(istart) >> 4;
 220                     RETURN_ERROR_IF(srcSize<4, corruption_detected, "srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4");
 221                     break;
 222                 }
 223                 RETURN_ERROR_IF(litSize > ZSTD_BLOCKSIZE_MAX, corruption_detected);
 224                 memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
 225                 dctx->litPtr = dctx->litBuffer;
 226                 dctx->litSize = litSize;
 227                 return lhSize+1;
 228             }
 229         default:
 230             RETURN_ERROR(corruption_detected, "impossible");
 231         }
 232     }
 233 }
 234
 235 /* Default FSE distribution tables.
 236  * These are pre-calculated FSE decoding tables using default distributions as defined in specification :
 237  * https://github.com/facebook/zstd/blob/master/doc/zstd_compression_format.md#default-distributions
 238  * They were generated programmatically with following method :
 239  * - start from default distributions, present in /lib/common/zstd_internal.h
 240  * - generate tables normally, using ZSTD_buildFSETable()
 241  * - printout the content of tables
 242  * - pretify output, report below, test with fuzzer to ensure it's correct */
 243
 244 /* Default FSE distribution table for Literal Lengths */
 245 static const ZSTD_seqSymbol LL_defaultDTable[(1<<LL_DEFAULTNORMLOG)+1] = {
 246      {  1,  1,  1, LL_DEFAULTNORMLOG},  /* header : fastMode, tableLog */
 247      /* nextState, nbAddBits, nbBits, baseVal */
 248      {  0,  0,  4,    0},  { 16,  0,  4,    0},
 249      { 32,  0,  5,    1},  {  0,  0,  5,    3},
 250      {  0,  0,  5,    4},  {  0,  0,  5,    6},
 251      {  0,  0,  5,    7},  {  0,  0,  5,    9},
 252      {  0,  0,  5,   10},  {  0,  0,  5,   12},
 253      {  0,  0,  6,   14},  {  0,  1,  5,   16},
 254      {  0,  1,  5,   20},  {  0,  1,  5,   22},
 255      {  0,  2,  5,   28},  {  0,  3,  5,   32},
 256      {  0,  4,  5,   48},  { 32,  6,  5,   64},
 257      {  0,  7,  5,  128},  {  0,  8,  6,  256},
 258      {  0, 10,  6, 1024},  {  0, 12,  6, 4096},
 259      { 32,  0,  4,    0},  {  0,  0,  4,    1},
 260      {  0,  0,  5,    2},  { 32,  0,  5,    4},
 261      {  0,  0,  5,    5},  { 32,  0,  5,    7},
 262      {  0,  0,  5,    8},  { 32,  0,  5,   10},
 263      {  0,  0,  5,   11},  {  0,  0,  6,   13},
 264      { 32,  1,  5,   16},  {  0,  1,  5,   18},
 265      { 32,  1,  5,   22},  {  0,  2,  5,   24},
 266      { 32,  3,  5,   32},  {  0,  3,  5,   40},
 267      {  0,  6,  4,   64},  { 16,  6,  4,   64},
 268      { 32,  7,  5,  128},  {  0,  9,  6,  512},
 269      {  0, 11,  6, 2048},  { 48,  0,  4,    0},
 270      { 16,  0,  4,    1},  { 32,  0,  5,    2},
 271      { 32,  0,  5,    3},  { 32,  0,  5,    5},
 272      { 32,  0,  5,    6},  { 32,  0,  5,    8},
 273      { 32,  0,  5,    9},  { 32,  0,  5,   11},
 274      { 32,  0,  5,   12},  {  0,  0,  6,   15},
 275      { 32,  1,  5,   18},  { 32,  1,  5,   20},
 276      { 32,  2,  5,   24},  { 32,  2,  5,   28},
 277      { 32,  3,  5,   40},  { 32,  4,  5,   48},
 278      {  0, 16,  6,65536},  {  0, 15,  6,32768},
 279      {  0, 14,  6,16384},  {  0, 13,  6, 8192},
 280 };   /* LL_defaultDTable */
 281
 282 /* Default FSE distribution table for Offset Codes */
 283 static const ZSTD_seqSymbol OF_defaultDTable[(1<<OF_DEFAULTNORMLOG)+1] = {
 284     {  1,  1,  1, OF_DEFAULTNORMLOG},  /* header : fastMode, tableLog */
 285     /* nextState, nbAddBits, nbBits, baseVal */
 286     {  0,  0,  5,    0},     {  0,  6,  4,   61},
 287     {  0,  9,  5,  509},     {  0, 15,  5,32765},
 288     {  0, 21,  5,2097149},   {  0,  3,  5,    5},
 289     {  0,  7,  4,  125},     {  0, 12,  5, 4093},
 290     {  0, 18,  5,262141},    {  0, 23,  5,8388605},
 291     {  0,  5,  5,   29},     {  0,  8,  4,  253},
 292     {  0, 14,  5,16381},     {  0, 20,  5,1048573},
 293     {  0,  2,  5,    1},     { 16,  7,  4,  125},
 294     {  0, 11,  5, 2045},     {  0, 17,  5,131069},
 295     {  0, 22,  5,4194301},   {  0,  4,  5,   13},
 296     { 16,  8,  4,  253},     {  0, 13,  5, 8189},
 297     {  0, 19,  5,524285},    {  0,  1,  5,    1},
 298     { 16,  6,  4,   61},     {  0, 10,  5, 1021},
 299     {  0, 16,  5,65533},     {  0, 28,  5,268435453},
 300     {  0, 27,  5,134217725}, {  0, 26,  5,67108861},
 301     {  0, 25,  5,33554429},  {  0, 24,  5,16777213},
 302 };   /* OF_defaultDTable */
 303
 304
 305 /* Default FSE distribution table for Match Lengths */
 306 static const ZSTD_seqSymbol ML_defaultDTable[(1<<ML_DEFAULTNORMLOG)+1] = {
 307     {  1,  1,  1, ML_DEFAULTNORMLOG},  /* header : fastMode, tableLog */
 308     /* nextState, nbAddBits, nbBits, baseVal */
 309     {  0,  0,  6,    3},  {  0,  0,  4,    4},
 310     { 32,  0,  5,    5},  {  0,  0,  5,    6},
 311     {  0,  0,  5,    8},  {  0,  0,  5,    9},
 312     {  0,  0,  5,   11},  {  0,  0,  6,   13},
 313     {  0,  0,  6,   16},  {  0,  0,  6,   19},
 314     {  0,  0,  6,   22},  {  0,  0,  6,   25},
 315     {  0,  0,  6,   28},  {  0,  0,  6,   31},
 316     {  0,  0,  6,   34},  {  0,  1,  6,   37},
 317     {  0,  1,  6,   41},  {  0,  2,  6,   47},
 318     {  0,  3,  6,   59},  {  0,  4,  6,   83},
 319     {  0,  7,  6,  131},  {  0,  9,  6,  515},
 320     { 16,  0,  4,    4},  {  0,  0,  4,    5},
 321     { 32,  0,  5,    6},  {  0,  0,  5,    7},
 322     { 32,  0,  5,    9},  {  0,  0,  5,   10},
 323     {  0,  0,  6,   12},  {  0,  0,  6,   15},
 324     {  0,  0,  6,   18},  {  0,  0,  6,   21},
 325     {  0,  0,  6,   24},  {  0,  0,  6,   27},
 326     {  0,  0,  6,   30},  {  0,  0,  6,   33},
 327     {  0,  1,  6,   35},  {  0,  1,  6,   39},
 328     {  0,  2,  6,   43},  {  0,  3,  6,   51},
 329     {  0,  4,  6,   67},  {  0,  5,  6,   99},
 330     {  0,  8,  6,  259},  { 32,  0,  4,    4},
 331     { 48,  0,  4,    4},  { 16,  0,  4,    5},
 332     { 32,  0,  5,    7},  { 32,  0,  5,    8},
 333     { 32,  0,  5,   10},  { 32,  0,  5,   11},
 334     {  0,  0,  6,   14},  {  0,  0,  6,   17},
 335     {  0,  0,  6,   20},  {  0,  0,  6,   23},
 336     {  0,  0,  6,   26},  {  0,  0,  6,   29},
 337     {  0,  0,  6,   32},  {  0, 16,  6,65539},
 338     {  0, 15,  6,32771},  {  0, 14,  6,16387},
 339     {  0, 13,  6, 8195},  {  0, 12,  6, 4099},
 340     {  0, 11,  6, 2051},  {  0, 10,  6, 1027},
 341 };   /* ML_defaultDTable */
 342
 343
 344 static void ZSTD_buildSeqTable_rle(ZSTD_seqSymbol* dt, U32 baseValue, U32 nbAddBits)
 345 {
 346     void* ptr = dt;
 347     ZSTD_seqSymbol_header* const DTableH = (ZSTD_seqSymbol_header*)ptr;
 348     ZSTD_seqSymbol* const cell = dt + 1;
 349
 350     DTableH->tableLog = 0;
 351     DTableH->fastMode = 0;
 352
 353     cell->nbBits = 0;
 354     cell->nextState = 0;
 355     assert(nbAddBits < 255);
 356     cell->nbAdditionalBits = (BYTE)nbAddBits;
 357     cell->baseValue = baseValue;
 358 }
 359
 360
 361 /* ZSTD_buildFSETable() :
 362  * generate FSE decoding table for one symbol (ll, ml or off)
 363  * cannot fail if input is valid =>
 364  * all inputs are presumed validated at this stage */
 365 void
 366 ZSTD_buildFSETable(ZSTD_seqSymbol* dt,
 367             const short* normalizedCounter, unsigned maxSymbolValue,
 368             const U32* baseValue, const U32* nbAdditionalBits,
 369             unsigned tableLog)
 370 {
 371     ZSTD_seqSymbol* const tableDecode = dt+1;
 372     U16 symbolNext[MaxSeq+1];
 373
 374     U32 const maxSV1 = maxSymbolValue + 1;
 375     U32 const tableSize = 1 << tableLog;
 376     U32 highThreshold = tableSize-1;
 377
 378     /* Sanity Checks */
 379     assert(maxSymbolValue <= MaxSeq);
 380     assert(tableLog <= MaxFSELog);
 381
 382     /* Init, lay down lowprob symbols */
 383     {   ZSTD_seqSymbol_header DTableH;
 384         DTableH.tableLog = tableLog;
 385         DTableH.fastMode = 1;
 386         {   S16 const largeLimit= (S16)(1 << (tableLog-1));
 387             U32 s;
 388             for (s=0; s<maxSV1; s++) {
 389                 if (normalizedCounter[s]==-1) {
 390                     tableDecode[highThreshold--].baseValue = s;
 391                     symbolNext[s] = 1;
 392                 } else {
 393                     if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
 394                     symbolNext[s] = normalizedCounter[s];
 395         }   }   }
 396         memcpy(dt, &DTableH, sizeof(DTableH));
 397     }
 398
 399     /* Spread symbols */
 400     {   U32 const tableMask = tableSize-1;
 401         U32 const step = FSE_TABLESTEP(tableSize);
 402         U32 s, position = 0;
 403         for (s=0; s<maxSV1; s++) {
 404             int i;
 405             for (i=0; i<normalizedCounter[s]; i++) {
 406                 tableDecode[position].baseValue = s;
 407                 position = (position + step) & tableMask;
 408                 while (position > highThreshold) position = (position + step) & tableMask;   /* lowprob area */
 409         }   }
 410         assert(position == 0); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
 411     }
 412
 413     /* Build Decoding table */
 414     {   U32 u;
 415         for (u=0; u<tableSize; u++) {
 416             U32 const symbol = tableDecode[u].baseValue;
 417             U32 const nextState = symbolNext[symbol]++;
 418             tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32(nextState) );
 419             tableDecode[u].nextState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
 420             assert(nbAdditionalBits[symbol] < 255);
 421             tableDecode[u].nbAdditionalBits = (BYTE)nbAdditionalBits[symbol];
 422             tableDecode[u].baseValue = baseValue[symbol];
 423     }   }
 424 }
 425
 426
 427 /*! ZSTD_buildSeqTable() :
 428  * @return : nb bytes read from src,
 429  *           or an error code if it fails */
 430 static size_t ZSTD_buildSeqTable(ZSTD_seqSymbol* DTableSpace, const ZSTD_seqSymbol** DTablePtr,
 431                                  symbolEncodingType_e type, unsigned max, U32 maxLog,
 432                                  const void* src, size_t srcSize,
 433                                  const U32* baseValue, const U32* nbAdditionalBits,
 434                                  const ZSTD_seqSymbol* defaultTable, U32 flagRepeatTable,
 435                                  int ddictIsCold, int nbSeq)
 436 {
 437     switch(type)
 438     {
 439     case set_rle :
 440         RETURN_ERROR_IF(!srcSize, srcSize_wrong);
 441         RETURN_ERROR_IF((*(const BYTE*)src) > max, corruption_detected);
 442         {   U32 const symbol = *(const BYTE*)src;
 443             U32 const baseline = baseValue[symbol];
 444             U32 const nbBits = nbAdditionalBits[symbol];
 445             ZSTD_buildSeqTable_rle(DTableSpace, baseline, nbBits);
 446         }
 447         *DTablePtr = DTableSpace;
 448         return 1;
 449     case set_basic :
 450         *DTablePtr = defaultTable;
 451         return 0;
 452     case set_repeat:
 453         RETURN_ERROR_IF(!flagRepeatTable, corruption_detected);
 454         /* prefetch FSE table if used */
 455         if (ddictIsCold && (nbSeq > 24 /* heuristic */)) {
 456             const void* const pStart = *DTablePtr;
 457             size_t const pSize = sizeof(ZSTD_seqSymbol) * (SEQSYMBOL_TABLE_SIZE(maxLog));
 458             PREFETCH_AREA(pStart, pSize);
 459         }
 460         return 0;
 461     case set_compressed :
 462         {   unsigned tableLog;
 463             S16 norm[MaxSeq+1];
 464             size_t const headerSize = FSE_readNCount(norm, &max, &tableLog, src, srcSize);
 465             RETURN_ERROR_IF(FSE_isError(headerSize), corruption_detected);
 466             RETURN_ERROR_IF(tableLog > maxLog, corruption_detected);
 467             ZSTD_buildFSETable(DTableSpace, norm, max, baseValue, nbAdditionalBits, tableLog);
 468             *DTablePtr = DTableSpace;
 469             return headerSize;
 470         }
 471     default :
 472         assert(0);
 473         RETURN_ERROR(GENERIC, "impossible");
 474     }
 475 }
 476
 477 size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr,
 478                              const void* src, size_t srcSize)
 479 {
 480     const BYTE* const istart = (const BYTE* const)src;
 481     const BYTE* const iend = istart + srcSize;
 482     const BYTE* ip = istart;
 483     int nbSeq;
 484     DEBUGLOG(5, "ZSTD_decodeSeqHeaders");
 485
 486     /* check */
 487     RETURN_ERROR_IF(srcSize < MIN_SEQUENCES_SIZE, srcSize_wrong);
 488
 489     /* SeqHead */
 490     nbSeq = *ip++;
 491     if (!nbSeq) {
 492         *nbSeqPtr=0;
 493         RETURN_ERROR_IF(srcSize != 1, srcSize_wrong);
 494         return 1;
 495     }
 496     if (nbSeq > 0x7F) {
 497         if (nbSeq == 0xFF) {
 498             RETURN_ERROR_IF(ip+2 > iend, srcSize_wrong);
 499             nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2;
 500         } else {
 501             RETURN_ERROR_IF(ip >= iend, srcSize_wrong);
 502             nbSeq = ((nbSeq-0x80)<<8) + *ip++;
 503         }
 504     }
 505     *nbSeqPtr = nbSeq;
 506
 507     /* FSE table descriptors */
 508     RETURN_ERROR_IF(ip+1 > iend, srcSize_wrong); /* minimum possible size: 1 byte for symbol encoding types */
 509     {   symbolEncodingType_e const LLtype = (symbolEncodingType_e)(*ip >> 6);
 510         symbolEncodingType_e const OFtype = (symbolEncodingType_e)((*ip >> 4) & 3);
 511         symbolEncodingType_e const MLtype = (symbolEncodingType_e)((*ip >> 2) & 3);
 512         ip++;
 513
 514         /* Build DTables */
 515         {   size_t const llhSize = ZSTD_buildSeqTable(dctx->entropy.LLTable, &dctx->LLTptr,
 516                                                       LLtype, MaxLL, LLFSELog,
 517                                                       ip, iend-ip,
 518                                                       LL_base, LL_bits,
 519                                                       LL_defaultDTable, dctx->fseEntropy,
 520                                                       dctx->ddictIsCold, nbSeq);
 521             RETURN_ERROR_IF(ZSTD_isError(llhSize), corruption_detected);
 522             ip += llhSize;
 523         }
 524
 525         {   size_t const ofhSize = ZSTD_buildSeqTable(dctx->entropy.OFTable, &dctx->OFTptr,
 526                                                       OFtype, MaxOff, OffFSELog,
 527                                                       ip, iend-ip,
 528                                                       OF_base, OF_bits,
 529                                                       OF_defaultDTable, dctx->fseEntropy,
 530                                                       dctx->ddictIsCold, nbSeq);
 531             RETURN_ERROR_IF(ZSTD_isError(ofhSize), corruption_detected);
 532             ip += ofhSize;
 533         }
 534
 535         {   size_t const mlhSize = ZSTD_buildSeqTable(dctx->entropy.MLTable, &dctx->MLTptr,
 536                                                       MLtype, MaxML, MLFSELog,
 537                                                       ip, iend-ip,
 538                                                       ML_base, ML_bits,
 539                                                       ML_defaultDTable, dctx->fseEntropy,
 540                                                       dctx->ddictIsCold, nbSeq);
 541             RETURN_ERROR_IF(ZSTD_isError(mlhSize), corruption_detected);
 542             ip += mlhSize;
 543         }
 544     }
 545
 546     return ip-istart;
 547 }
 548
 549
 550 typedef struct {
 551     size_t litLength;
 552     size_t matchLength;
 553     size_t offset;
 554     const BYTE* match;
 555 } seq_t;
 556
 557 typedef struct {
 558     size_t state;
 559     const ZSTD_seqSymbol* table;
 560 } ZSTD_fseState;
 561
 562 typedef struct {
 563     BIT_DStream_t DStream;
 564     ZSTD_fseState stateLL;
 565     ZSTD_fseState stateOffb;
 566     ZSTD_fseState stateML;
 567     size_t prevOffset[ZSTD_REP_NUM];
 568     const BYTE* prefixStart;
 569     const BYTE* dictEnd;
 570     size_t pos;
 571 } seqState_t;
 572
 573
 574 /* ZSTD_execSequenceLast7():
 575  * exceptional case : decompress a match starting within last 7 bytes of output buffer.
 576  * requires more careful checks, to ensure there is no overflow.
 577  * performance does not matter though.
 578  * note : this case is supposed to be never generated "naturally" by reference encoder,
 579  *        since in most cases it needs at least 8 bytes to look for a match.
 580  *        but it's allowed by the specification. */
 581 FORCE_NOINLINE
 582 size_t ZSTD_execSequenceLast7(BYTE* op,
 583                               BYTE* const oend, seq_t sequence,
 584                               const BYTE** litPtr, const BYTE* const litLimit,
 585                               const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
 586 {
 587     BYTE* const oLitEnd = op + sequence.litLength;
 588     size_t const sequenceLength = sequence.litLength + sequence.matchLength;
 589     BYTE* const oMatchEnd = op + sequenceLength;   /* risk : address space overflow (32-bits) */
 590     const BYTE* const iLitEnd = *litPtr + sequence.litLength;
 591     const BYTE* match = oLitEnd - sequence.offset;
 592
 593     /* check */
 594     RETURN_ERROR_IF(oMatchEnd>oend, dstSize_tooSmall, "last match must fit within dstBuffer");
 595     RETURN_ERROR_IF(iLitEnd > litLimit, corruption_detected, "try to read beyond literal buffer");
 596
 597     /* copy literals */
 598     while (op < oLitEnd) *op++ = *(*litPtr)++;
 599
 600     /* copy Match */
 601     if (sequence.offset > (size_t)(oLitEnd - base)) {
 602         /* offset beyond prefix */
 603         RETURN_ERROR_IF(sequence.offset > (size_t)(oLitEnd - vBase),corruption_detected);
 604         match = dictEnd - (base-match);
 605         if (match + sequence.matchLength <= dictEnd) {
 606             memmove(oLitEnd, match, sequence.matchLength);
 607             return sequenceLength;
 608         }
 609         /* span extDict & currentPrefixSegment */
 610         {   size_t const length1 = dictEnd - match;
 611             memmove(oLitEnd, match, length1);
 612             op = oLitEnd + length1;
 613             sequence.matchLength -= length1;
 614             match = base;
 615     }   }
 616     while (op < oMatchEnd) *op++ = *match++;
 617     return sequenceLength;
 618 }
 619
 620
 621 HINT_INLINE
 622 size_t ZSTD_execSequence(BYTE* op,
 623                          BYTE* const oend, seq_t sequence,
 624                          const BYTE** litPtr, const BYTE* const litLimit,
 625                          const BYTE* const prefixStart, const BYTE* const virtualStart, const BYTE* const dictEnd)
 626 {
 627     BYTE* const oLitEnd = op + sequence.litLength;
 628     size_t const sequenceLength = sequence.litLength + sequence.matchLength;
 629     BYTE* const oMatchEnd = op + sequenceLength;   /* risk : address space overflow (32-bits) */
 630     BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH;
 631     const BYTE* const iLitEnd = *litPtr + sequence.litLength;
 632     const BYTE* match = oLitEnd - sequence.offset;
 633
 634     /* check */
 635     RETURN_ERROR_IF(oMatchEnd>oend, dstSize_tooSmall, "last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend");
 636     RETURN_ERROR_IF(iLitEnd > litLimit, corruption_detected, "over-read beyond lit buffer");
 637     if (oLitEnd>oend_w) return ZSTD_execSequenceLast7(op, oend, sequence, litPtr, litLimit, prefixStart, virtualStart, dictEnd);
 638
 639     /* copy Literals */
 640     if (sequence.litLength > 8)
 641         ZSTD_wildcopy_16min(op, (*litPtr), sequence.litLength, ZSTD_no_overlap);   /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
 642     else
 643         ZSTD_copy8(op, *litPtr);
 644     op = oLitEnd;
 645     *litPtr = iLitEnd;   /* update for next sequence */
 646
 647     /* copy Match */
 648     if (sequence.offset > (size_t)(oLitEnd - prefixStart)) {
 649         /* offset beyond prefix -> go into extDict */
 650         RETURN_ERROR_IF(sequence.offset > (size_t)(oLitEnd - virtualStart), corruption_detected);
 651         match = dictEnd + (match - prefixStart);
 652         if (match + sequence.matchLength <= dictEnd) {
 653             memmove(oLitEnd, match, sequence.matchLength);
 654             return sequenceLength;
 655         }
 656         /* span extDict & currentPrefixSegment */
 657         {   size_t const length1 = dictEnd - match;
 658             memmove(oLitEnd, match, length1);
 659             op = oLitEnd + length1;
 660             sequence.matchLength -= length1;
 661             match = prefixStart;
 662             if (op > oend_w || sequence.matchLength < MINMATCH) {
 663               U32 i;
 664               for (i = 0; i < sequence.matchLength; ++i) op[i] = match[i];
 665               return sequenceLength;
 666             }
 667     }   }
 668     /* Requirement: op <= oend_w && sequence.matchLength >= MINMATCH */
 669
 670     /* match within prefix */
 671     if (sequence.offset < 8) {
 672         /* close range match, overlap */
 673         static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 };   /* added */
 674         static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 };   /* subtracted */
 675         int const sub2 = dec64table[sequence.offset];
 676         op[0] = match[0];
 677         op[1] = match[1];
 678         op[2] = match[2];
 679         op[3] = match[3];
 680         match += dec32table[sequence.offset];
 681         ZSTD_copy4(op+4, match);
 682         match -= sub2;
 683     } else {
 684         ZSTD_copy8(op, match);
 685     }
 686     op += 8; match += 8;
 687
 688     if (oMatchEnd > oend-(16-MINMATCH)) {
 689         if (op < oend_w) {
 690             ZSTD_wildcopy(op, match, oend_w - op, ZSTD_overlap_src_before_dst);
 691             match += oend_w - op;
 692             op = oend_w;
 693         }
 694         while (op < oMatchEnd) *op++ = *match++;
 695     } else {
 696         ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8, ZSTD_overlap_src_before_dst);   /* works even if matchLength < 8 */
 697     }
 698     return sequenceLength;
 699 }
 700
 701
 702 HINT_INLINE
 703 size_t ZSTD_execSequenceLong(BYTE* op,
 704                              BYTE* const oend, seq_t sequence,
 705                              const BYTE** litPtr, const BYTE* const litLimit,
 706                              const BYTE* const prefixStart, const BYTE* const dictStart, const BYTE* const dictEnd)
 707 {
 708     BYTE* const oLitEnd = op + sequence.litLength;
 709     size_t const sequenceLength = sequence.litLength + sequence.matchLength;
 710     BYTE* const oMatchEnd = op + sequenceLength;   /* risk : address space overflow (32-bits) */
 711     BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH;
 712     const BYTE* const iLitEnd = *litPtr + sequence.litLength;
 713     const BYTE* match = sequence.match;
 714
 715     /* check */
 716     RETURN_ERROR_IF(oMatchEnd > oend, dstSize_tooSmall, "last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend");
 717     RETURN_ERROR_IF(iLitEnd > litLimit, corruption_detected, "over-read beyond lit buffer");
 718     if (oLitEnd > oend_w) return ZSTD_execSequenceLast7(op, oend, sequence, litPtr, litLimit, prefixStart, dictStart, dictEnd);
 719
 720     /* copy Literals */
 721     if (sequence.litLength > 8)
 722         ZSTD_wildcopy_16min(op, *litPtr, sequence.litLength, ZSTD_no_overlap);   /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
 723     else
 724         ZSTD_copy8(op, *litPtr);  /* note : op <= oLitEnd <= oend_w == oend - 8 */
 725
 726     op = oLitEnd;
 727     *litPtr = iLitEnd;   /* update for next sequence */
 728
 729     /* copy Match */
 730     if (sequence.offset > (size_t)(oLitEnd - prefixStart)) {
 731         /* offset beyond prefix */
 732         RETURN_ERROR_IF(sequence.offset > (size_t)(oLitEnd - dictStart), corruption_detected);
 733         if (match + sequence.matchLength <= dictEnd) {
 734             memmove(oLitEnd, match, sequence.matchLength);
 735             return sequenceLength;
 736         }
 737         /* span extDict & currentPrefixSegment */
 738         {   size_t const length1 = dictEnd - match;
 739             memmove(oLitEnd, match, length1);
 740             op = oLitEnd + length1;
 741             sequence.matchLength -= length1;
 742             match = prefixStart;
 743             if (op > oend_w || sequence.matchLength < MINMATCH) {
 744               U32 i;
 745               for (i = 0; i < sequence.matchLength; ++i) op[i] = match[i];
 746               return sequenceLength;
 747             }
 748     }   }
 749     assert(op <= oend_w);
 750     assert(sequence.matchLength >= MINMATCH);
 751
 752     /* match within prefix */
 753     if (sequence.offset < 8) {
 754         /* close range match, overlap */
 755         static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 };   /* added */
 756         static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 };   /* subtracted */
 757         int const sub2 = dec64table[sequence.offset];
 758         op[0] = match[0];
 759         op[1] = match[1];
 760         op[2] = match[2];
 761         op[3] = match[3];
 762         match += dec32table[sequence.offset];
 763         ZSTD_copy4(op+4, match);
 764         match -= sub2;
 765     } else {
 766         ZSTD_copy8(op, match);
 767     }
 768     op += 8; match += 8;
 769
 770     if (oMatchEnd > oend-(16-MINMATCH)) {
 771         if (op < oend_w) {
 772             ZSTD_wildcopy(op, match, oend_w - op, ZSTD_overlap_src_before_dst);
 773             match += oend_w - op;
 774             op = oend_w;
 775         }
 776         while (op < oMatchEnd) *op++ = *match++;
 777     } else {
 778         ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8, ZSTD_overlap_src_before_dst);   /* works even if matchLength < 8 */
 779     }
 780     return sequenceLength;
 781 }
 782
 783 static void
 784 ZSTD_initFseState(ZSTD_fseState* DStatePtr, BIT_DStream_t* bitD, const ZSTD_seqSymbol* dt)
 785 {
 786     const void* ptr = dt;
 787     const ZSTD_seqSymbol_header* const DTableH = (const ZSTD_seqSymbol_header*)ptr;
 788     DStatePtr->state = BIT_readBits(bitD, DTableH->tableLog);
 789     DEBUGLOG(6, "ZSTD_initFseState : val=%u using %u bits",
 790                 (U32)DStatePtr->state, DTableH->tableLog);
 791     BIT_reloadDStream(bitD);
 792     DStatePtr->table = dt + 1;
 793 }
 794
 795 FORCE_INLINE_TEMPLATE void
 796 ZSTD_updateFseState(ZSTD_fseState* DStatePtr, BIT_DStream_t* bitD)
 797 {
 798     ZSTD_seqSymbol const DInfo = DStatePtr->table[DStatePtr->state];
 799     U32 const nbBits = DInfo.nbBits;
 800     size_t const lowBits = BIT_readBits(bitD, nbBits);
 801     DStatePtr->state = DInfo.nextState + lowBits;
 802 }
 803
 804 /* We need to add at most (ZSTD_WINDOWLOG_MAX_32 - 1) bits to read the maximum
 805  * offset bits. But we can only read at most (STREAM_ACCUMULATOR_MIN_32 - 1)
 806  * bits before reloading. This value is the maximum number of bytes we read
 807  * after reloading when we are decoding long offsets.
 808  */
 809 #define LONG_OFFSETS_MAX_EXTRA_BITS_32                       \
 810     (ZSTD_WINDOWLOG_MAX_32 > STREAM_ACCUMULATOR_MIN_32       \
 811         ? ZSTD_WINDOWLOG_MAX_32 - STREAM_ACCUMULATOR_MIN_32  \
 812         : 0)
 813
 814 typedef enum { ZSTD_lo_isRegularOffset, ZSTD_lo_isLongOffset=1 } ZSTD_longOffset_e;
 815
 816 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
 817 FORCE_INLINE_TEMPLATE seq_t
 818 ZSTD_decodeSequence(seqState_t* seqState, const ZSTD_longOffset_e longOffsets)
 819 {
 820     seq_t seq;
 821     U32 const llBits = seqState->stateLL.table[seqState->stateLL.state].nbAdditionalBits;
 822     U32 const mlBits = seqState->stateML.table[seqState->stateML.state].nbAdditionalBits;
 823     U32 const ofBits = seqState->stateOffb.table[seqState->stateOffb.state].nbAdditionalBits;
 824     U32 const totalBits = llBits+mlBits+ofBits;
 825     U32 const llBase = seqState->stateLL.table[seqState->stateLL.state].baseValue;
 826     U32 const mlBase = seqState->stateML.table[seqState->stateML.state].baseValue;
 827     U32 const ofBase = seqState->stateOffb.table[seqState->stateOffb.state].baseValue;
 828
 829     /* sequence */
 830     {   size_t offset;
 831         if (!ofBits)
 832             offset = 0;
 833         else {
 834             ZSTD_STATIC_ASSERT(ZSTD_lo_isLongOffset == 1);
 835             ZSTD_STATIC_ASSERT(LONG_OFFSETS_MAX_EXTRA_BITS_32 == 5);
 836             assert(ofBits <= MaxOff);
 837             if (MEM_32bits() && longOffsets && (ofBits >= STREAM_ACCUMULATOR_MIN_32)) {
 838                 U32 const extraBits = ofBits - MIN(ofBits, 32 - seqState->DStream.bitsConsumed);
 839                 offset = ofBase + (BIT_readBitsFast(&seqState->DStream, ofBits - extraBits) << extraBits);
 840                 BIT_reloadDStream(&seqState->DStream);
 841                 if (extraBits) offset += BIT_readBitsFast(&seqState->DStream, extraBits);
 842                 assert(extraBits <= LONG_OFFSETS_MAX_EXTRA_BITS_32);   /* to avoid another reload */
 843             } else {
 844                 offset = ofBase + BIT_readBitsFast(&seqState->DStream, ofBits/*>0*/);   /* <=  (ZSTD_WINDOWLOG_MAX-1) bits */
 845                 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream);
 846             }
 847         }
 848
 849         if (ofBits <= 1) {
 850             offset += (llBase==0);
 851             if (offset) {
 852                 size_t temp = (offset==3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
 853                 temp += !temp;   /* 0 is not valid; input is corrupted; force offset to 1 */
 854                 if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1];
 855                 seqState->prevOffset[1] = seqState->prevOffset[0];
 856                 seqState->prevOffset[0] = offset = temp;
 857             } else {  /* offset == 0 */
 858                 offset = seqState->prevOffset[0];
 859             }
 860         } else {
 861             seqState->prevOffset[2] = seqState->prevOffset[1];
 862             seqState->prevOffset[1] = seqState->prevOffset[0];
 863             seqState->prevOffset[0] = offset;
 864         }
 865         seq.offset = offset;
 866     }
 867
 868     seq.matchLength = mlBase
 869                     + ((mlBits>0) ? BIT_readBitsFast(&seqState->DStream, mlBits/*>0*/) : 0);  /* <=  16 bits */
 870     if (MEM_32bits() && (mlBits+llBits >= STREAM_ACCUMULATOR_MIN_32-LONG_OFFSETS_MAX_EXTRA_BITS_32))
 871         BIT_reloadDStream(&seqState->DStream);
 872     if (MEM_64bits() && (totalBits >= STREAM_ACCUMULATOR_MIN_64-(LLFSELog+MLFSELog+OffFSELog)))
 873         BIT_reloadDStream(&seqState->DStream);
 874     /* Ensure there are enough bits to read the rest of data in 64-bit mode. */
 875     ZSTD_STATIC_ASSERT(16+LLFSELog+MLFSELog+OffFSELog < STREAM_ACCUMULATOR_MIN_64);
 876
 877     seq.litLength = llBase
 878                   + ((llBits>0) ? BIT_readBitsFast(&seqState->DStream, llBits/*>0*/) : 0);    /* <=  16 bits */
 879     if (MEM_32bits())
 880         BIT_reloadDStream(&seqState->DStream);
 881
 882     DEBUGLOG(6, "seq: litL=%u, matchL=%u, offset=%u",
 883                 (U32)seq.litLength, (U32)seq.matchLength, (U32)seq.offset);
 884
 885     /* ANS state update */
 886     ZSTD_updateFseState(&seqState->stateLL, &seqState->DStream);    /* <=  9 bits */
 887     ZSTD_updateFseState(&seqState->stateML, &seqState->DStream);    /* <=  9 bits */
 888     if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream);    /* <= 18 bits */
 889     ZSTD_updateFseState(&seqState->stateOffb, &seqState->DStream);  /* <=  8 bits */
 890
 891     return seq;
 892 }
 893
 894 FORCE_INLINE_TEMPLATE size_t
 895 DONT_VECTORIZE
 896 ZSTD_decompressSequences_body( ZSTD_DCtx* dctx,
 897                                void* dst, size_t maxDstSize,
 898                          const void* seqStart, size_t seqSize, int nbSeq,
 899                          const ZSTD_longOffset_e isLongOffset)
 900 {
 901     const BYTE* ip = (const BYTE*)seqStart;
 902     const BYTE* const iend = ip + seqSize;
 903     BYTE* const ostart = (BYTE* const)dst;
 904     BYTE* const oend = ostart + maxDstSize;
 905     BYTE* op = ostart;
 906     const BYTE* litPtr = dctx->litPtr;
 907     const BYTE* const litEnd = litPtr + dctx->litSize;
 908     const BYTE* const prefixStart = (const BYTE*) (dctx->prefixStart);
 909     const BYTE* const vBase = (const BYTE*) (dctx->virtualStart);
 910     const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
 911     DEBUGLOG(5, "ZSTD_decompressSequences_body");
 912
 913     /* Regen sequences */
 914     if (nbSeq) {
 915         seqState_t seqState;
 916         dctx->fseEntropy = 1;
 917         { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->entropy.rep[i]; }
 918         RETURN_ERROR_IF(
 919             ERR_isError(BIT_initDStream(&seqState.DStream, ip, iend-ip)),
 920             corruption_detected);
 921         ZSTD_initFseState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
 922         ZSTD_initFseState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
 923         ZSTD_initFseState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
 924
 925         ZSTD_STATIC_ASSERT(
 926                 BIT_DStream_unfinished < BIT_DStream_completed &&
 927                 BIT_DStream_endOfBuffer < BIT_DStream_completed &&
 928                 BIT_DStream_completed < BIT_DStream_overflow);
 929
 930         for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && nbSeq ; ) {
 931             nbSeq--;
 932             {   seq_t const sequence = ZSTD_decodeSequence(&seqState, isLongOffset);
 933                 size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litEnd, prefixStart, vBase, dictEnd);
 934                 DEBUGLOG(6, "regenerated sequence size : %u", (U32)oneSeqSize);
 935                 if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
 936                 op += oneSeqSize;
 937         }   }
 938
 939         /* check if reached exact end */
 940         DEBUGLOG(5, "ZSTD_decompressSequences_body: after decode loop, remaining nbSeq : %i", nbSeq);
 941         RETURN_ERROR_IF(nbSeq, corruption_detected);
 942         RETURN_ERROR_IF(BIT_reloadDStream(&seqState.DStream) < BIT_DStream_completed, corruption_detected);
 943         /* save reps for next block */
 944         { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]); }
 945     }
 946
 947     /* last literal segment */
 948     {   size_t const lastLLSize = litEnd - litPtr;
 949         RETURN_ERROR_IF(lastLLSize > (size_t)(oend-op), dstSize_tooSmall);
 950         memcpy(op, litPtr, lastLLSize);
 951         op += lastLLSize;
 952     }
 953
 954     return op-ostart;
 955 }
 956
 957 static size_t
 958 ZSTD_decompressSequences_default(ZSTD_DCtx* dctx,
 959                                  void* dst, size_t maxDstSize,
 960                            const void* seqStart, size_t seqSize, int nbSeq,
 961                            const ZSTD_longOffset_e isLongOffset)
 962 {
 963     return ZSTD_decompressSequences_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
 964 }
 965 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */
 966
 967
 968
 969 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
 970 FORCE_INLINE_TEMPLATE seq_t
 971 ZSTD_decodeSequenceLong(seqState_t* seqState, ZSTD_longOffset_e const longOffsets)
 972 {
 973     seq_t seq;
 974     U32 const llBits = seqState->stateLL.table[seqState->stateLL.state].nbAdditionalBits;
 975     U32 const mlBits = seqState->stateML.table[seqState->stateML.state].nbAdditionalBits;
 976     U32 const ofBits = seqState->stateOffb.table[seqState->stateOffb.state].nbAdditionalBits;
 977     U32 const totalBits = llBits+mlBits+ofBits;
 978     U32 const llBase = seqState->stateLL.table[seqState->stateLL.state].baseValue;
 979     U32 const mlBase = seqState->stateML.table[seqState->stateML.state].baseValue;
 980     U32 const ofBase = seqState->stateOffb.table[seqState->stateOffb.state].baseValue;
 981
 982     /* sequence */
 983     {   size_t offset;
 984         if (!ofBits)
 985             offset = 0;
 986         else {
 987             ZSTD_STATIC_ASSERT(ZSTD_lo_isLongOffset == 1);
 988             ZSTD_STATIC_ASSERT(LONG_OFFSETS_MAX_EXTRA_BITS_32 == 5);
 989             assert(ofBits <= MaxOff);
 990             if (MEM_32bits() && longOffsets) {
 991                 U32 const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN_32-1);
 992                 offset = ofBase + (BIT_readBitsFast(&seqState->DStream, ofBits - extraBits) << extraBits);
 993                 if (MEM_32bits() || extraBits) BIT_reloadDStream(&seqState->DStream);
 994                 if (extraBits) offset += BIT_readBitsFast(&seqState->DStream, extraBits);
 995             } else {
 996                 offset = ofBase + BIT_readBitsFast(&seqState->DStream, ofBits);   /* <=  (ZSTD_WINDOWLOG_MAX-1) bits */
 997                 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream);
 998             }
 999         }
1000
1001         if (ofBits <= 1) {
1002             offset += (llBase==0);
1003             if (offset) {
1004                 size_t temp = (offset==3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
1005                 temp += !temp;   /* 0 is not valid; input is corrupted; force offset to 1 */
1006                 if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1];
1007                 seqState->prevOffset[1] = seqState->prevOffset[0];
1008                 seqState->prevOffset[0] = offset = temp;
1009             } else {
1010                 offset = seqState->prevOffset[0];
1011             }
1012         } else {
1013             seqState->prevOffset[2] = seqState->prevOffset[1];
1014             seqState->prevOffset[1] = seqState->prevOffset[0];
1015             seqState->prevOffset[0] = offset;
1016         }
1017         seq.offset = offset;
1018     }
1019
1020     seq.matchLength = mlBase + ((mlBits>0) ? BIT_readBitsFast(&seqState->DStream, mlBits) : 0);  /* <=  16 bits */
1021     if (MEM_32bits() && (mlBits+llBits >= STREAM_ACCUMULATOR_MIN_32-LONG_OFFSETS_MAX_EXTRA_BITS_32))
1022         BIT_reloadDStream(&seqState->DStream);
1023     if (MEM_64bits() && (totalBits >= STREAM_ACCUMULATOR_MIN_64-(LLFSELog+MLFSELog+OffFSELog)))
1024         BIT_reloadDStream(&seqState->DStream);
1025     /* Verify that there is enough bits to read the rest of the data in 64-bit mode. */
1026     ZSTD_STATIC_ASSERT(16+LLFSELog+MLFSELog+OffFSELog < STREAM_ACCUMULATOR_MIN_64);
1027
1028     seq.litLength = llBase + ((llBits>0) ? BIT_readBitsFast(&seqState->DStream, llBits) : 0);    /* <=  16 bits */
1029     if (MEM_32bits())
1030         BIT_reloadDStream(&seqState->DStream);
1031
1032     {   size_t const pos = seqState->pos + seq.litLength;
1033         const BYTE* const matchBase = (seq.offset > pos) ? seqState->dictEnd : seqState->prefixStart;
1034         seq.match = matchBase + pos - seq.offset;  /* note : this operation can overflow when seq.offset is really too large, which can only happen when input is corrupted.
1035                                                     * No consequence though : no memory access will occur, overly large offset will be detected in ZSTD_execSequenceLong() */
1036         seqState->pos = pos + seq.matchLength;
1037     }
1038
1039     /* ANS state update */
1040     ZSTD_updateFseState(&seqState->stateLL, &seqState->DStream);    /* <=  9 bits */
1041     ZSTD_updateFseState(&seqState->stateML, &seqState->DStream);    /* <=  9 bits */
1042     if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream);    /* <= 18 bits */
1043     ZSTD_updateFseState(&seqState->stateOffb, &seqState->DStream);  /* <=  8 bits */
1044
1045     return seq;
1046 }
1047
1048 FORCE_INLINE_TEMPLATE size_t
1049 ZSTD_decompressSequencesLong_body(
1050                                ZSTD_DCtx* dctx,
1051                                void* dst, size_t maxDstSize,
1052                          const void* seqStart, size_t seqSize, int nbSeq,
1053                          const ZSTD_longOffset_e isLongOffset)
1054 {
1055     const BYTE* ip = (const BYTE*)seqStart;
1056     const BYTE* const iend = ip + seqSize;
1057     BYTE* const ostart = (BYTE* const)dst;
1058     BYTE* const oend = ostart + maxDstSize;
1059     BYTE* op = ostart;
1060     const BYTE* litPtr = dctx->litPtr;
1061     const BYTE* const litEnd = litPtr + dctx->litSize;
1062     const BYTE* const prefixStart = (const BYTE*) (dctx->prefixStart);
1063     const BYTE* const dictStart = (const BYTE*) (dctx->virtualStart);
1064     const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
1065
1066     /* Regen sequences */
1067     if (nbSeq) {
1068 #define STORED_SEQS 4
1069 #define STORED_SEQS_MASK (STORED_SEQS-1)
1070 #define ADVANCED_SEQS 4
1071         seq_t sequences[STORED_SEQS];
1072         int const seqAdvance = MIN(nbSeq, ADVANCED_SEQS);
1073         seqState_t seqState;
1074         int seqNb;
1075         dctx->fseEntropy = 1;
1076         { int i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->entropy.rep[i]; }
1077         seqState.prefixStart = prefixStart;
1078         seqState.pos = (size_t)(op-prefixStart);
1079         seqState.dictEnd = dictEnd;
1080         assert(iend >= ip);
1081         RETURN_ERROR_IF(
1082             ERR_isError(BIT_initDStream(&seqState.DStream, ip, iend-ip)),
1083             corruption_detected);
1084         ZSTD_initFseState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
1085         ZSTD_initFseState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
1086         ZSTD_initFseState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
1087
1088         /* prepare in advance */
1089         for (seqNb=0; (BIT_reloadDStream(&seqState.DStream) <= BIT_DStream_completed) && (seqNb<seqAdvance); seqNb++) {
1090             sequences[seqNb] = ZSTD_decodeSequenceLong(&seqState, isLongOffset);
1091             PREFETCH_L1(sequences[seqNb].match); PREFETCH_L1(sequences[seqNb].match + sequences[seqNb].matchLength - 1); /* note : it's safe to invoke PREFETCH() on any memory address, including invalid ones */
1092         }
1093         RETURN_ERROR_IF(seqNb<seqAdvance, corruption_detected);
1094
1095         /* decode and decompress */
1096         for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (seqNb<nbSeq) ; seqNb++) {
1097             seq_t const sequence = ZSTD_decodeSequenceLong(&seqState, isLongOffset);
1098             size_t const oneSeqSize = ZSTD_execSequenceLong(op, oend, sequences[(seqNb-ADVANCED_SEQS) & STORED_SEQS_MASK], &litPtr, litEnd, prefixStart, dictStart, dictEnd);
1099             if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
1100             PREFETCH_L1(sequence.match); PREFETCH_L1(sequence.match + sequence.matchLength - 1); /* note : it's safe to invoke PREFETCH() on any memory address, including invalid ones */
1101             sequences[seqNb & STORED_SEQS_MASK] = sequence;
1102             op += oneSeqSize;
1103         }
1104         RETURN_ERROR_IF(seqNb<nbSeq, corruption_detected);
1105
1106         /* finish queue */
1107         seqNb -= seqAdvance;
1108         for ( ; seqNb<nbSeq ; seqNb++) {
1109             size_t const oneSeqSize = ZSTD_execSequenceLong(op, oend, sequences[seqNb&STORED_SEQS_MASK], &litPtr, litEnd, prefixStart, dictStart, dictEnd);
1110             if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
1111             op += oneSeqSize;
1112         }
1113
1114         /* save reps for next block */
1115         { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]); }
1116     }
1117
1118     /* last literal segment */
1119     {   size_t const lastLLSize = litEnd - litPtr;
1120         RETURN_ERROR_IF(lastLLSize > (size_t)(oend-op), dstSize_tooSmall);
1121         memcpy(op, litPtr, lastLLSize);
1122         op += lastLLSize;
1123     }
1124
1125     return op-ostart;
1126 }
1127
1128 static size_t
1129 ZSTD_decompressSequencesLong_default(ZSTD_DCtx* dctx,
1130                                  void* dst, size_t maxDstSize,
1131                            const void* seqStart, size_t seqSize, int nbSeq,
1132                            const ZSTD_longOffset_e isLongOffset)
1133 {
1134     return ZSTD_decompressSequencesLong_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1135 }
1136 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */
1137
1138
1139
1140 #if DYNAMIC_BMI2
1141
1142 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
1143 static TARGET_ATTRIBUTE("bmi2") size_t
1144 DONT_VECTORIZE
1145 ZSTD_decompressSequences_bmi2(ZSTD_DCtx* dctx,
1146                                  void* dst, size_t maxDstSize,
1147                            const void* seqStart, size_t seqSize, int nbSeq,
1148                            const ZSTD_longOffset_e isLongOffset)
1149 {
1150     return ZSTD_decompressSequences_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1151 }
1152 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */
1153
1154 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
1155 static TARGET_ATTRIBUTE("bmi2") size_t
1156 ZSTD_decompressSequencesLong_bmi2(ZSTD_DCtx* dctx,
1157                                  void* dst, size_t maxDstSize,
1158                            const void* seqStart, size_t seqSize, int nbSeq,
1159                            const ZSTD_longOffset_e isLongOffset)
1160 {
1161     return ZSTD_decompressSequencesLong_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1162 }
1163 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */
1164
1165 #endif /* DYNAMIC_BMI2 */
1166
1167 typedef size_t (*ZSTD_decompressSequences_t)(
1168                             ZSTD_DCtx* dctx,
1169                             void* dst, size_t maxDstSize,
1170                             const void* seqStart, size_t seqSize, int nbSeq,
1171                             const ZSTD_longOffset_e isLongOffset);
1172
1173 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
1174 static size_t
1175 ZSTD_decompressSequences(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize,
1176                    const void* seqStart, size_t seqSize, int nbSeq,
1177                    const ZSTD_longOffset_e isLongOffset)
1178 {
1179     DEBUGLOG(5, "ZSTD_decompressSequences");
1180 #if DYNAMIC_BMI2
1181     if (dctx->bmi2) {
1182         return ZSTD_decompressSequences_bmi2(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1183     }
1184 #endif
1185   return ZSTD_decompressSequences_default(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1186 }
1187 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */
1188
1189
1190 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
1191 /* ZSTD_decompressSequencesLong() :
1192  * decompression function triggered when a minimum share of offsets is considered "long",
1193  * aka out of cache.
1194  * note : "long" definition seems overloaded here, sometimes meaning "wider than bitstream register", and sometimes meaning "farther than memory cache distance".
1195  * This function will try to mitigate main memory latency through the use of prefetching */
1196 static size_t
1197 ZSTD_decompressSequencesLong(ZSTD_DCtx* dctx,
1198                              void* dst, size_t maxDstSize,
1199                              const void* seqStart, size_t seqSize, int nbSeq,
1200                              const ZSTD_longOffset_e isLongOffset)
1201 {
1202     DEBUGLOG(5, "ZSTD_decompressSequencesLong");
1203 #if DYNAMIC_BMI2
1204     if (dctx->bmi2) {
1205         return ZSTD_decompressSequencesLong_bmi2(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1206     }
1207 #endif
1208   return ZSTD_decompressSequencesLong_default(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1209 }
1210 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */
1211
1212
1213
1214 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1215     !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1216 /* ZSTD_getLongOffsetsShare() :
1217  * condition : offTable must be valid
1218  * @return : "share" of long offsets (arbitrarily defined as > (1<<23))
1219  *           compared to maximum possible of (1<<OffFSELog) */
1220 static unsigned
1221 ZSTD_getLongOffsetsShare(const ZSTD_seqSymbol* offTable)
1222 {
1223     const void* ptr = offTable;
1224     U32 const tableLog = ((const ZSTD_seqSymbol_header*)ptr)[0].tableLog;
1225     const ZSTD_seqSymbol* table = offTable + 1;
1226     U32 const max = 1 << tableLog;
1227     U32 u, total = 0;
1228     DEBUGLOG(5, "ZSTD_getLongOffsetsShare: (tableLog=%u)", tableLog);
1229
1230     assert(max <= (1 << OffFSELog));  /* max not too large */
1231     for (u=0; u<max; u++) {
1232         if (table[u].nbAdditionalBits > 22) total += 1;
1233     }
1234
1235     assert(tableLog <= OffFSELog);
1236     total <<= (OffFSELog - tableLog);  /* scale to OffFSELog */
1237
1238     return total;
1239 }
1240 #endif
1241
1242
1243 size_t
1244 ZSTD_decompressBlock_internal(ZSTD_DCtx* dctx,
1245                               void* dst, size_t dstCapacity,
1246                         const void* src, size_t srcSize, const int frame)
1247 {   /* blockType == blockCompressed */
1248     const BYTE* ip = (const BYTE*)src;
1249     /* isLongOffset must be true if there are long offsets.
1250      * Offsets are long if they are larger than 2^STREAM_ACCUMULATOR_MIN.
1251      * We don't expect that to be the case in 64-bit mode.
1252      * In block mode, window size is not known, so we have to be conservative.
1253      * (note: but it could be evaluated from current-lowLimit)
1254      */
1255     ZSTD_longOffset_e const isLongOffset = (ZSTD_longOffset_e)(MEM_32bits() && (!frame || (dctx->fParams.windowSize > (1ULL << STREAM_ACCUMULATOR_MIN))));
1256     DEBUGLOG(5, "ZSTD_decompressBlock_internal (size : %u)", (U32)srcSize);
1257
1258     RETURN_ERROR_IF(srcSize >= ZSTD_BLOCKSIZE_MAX, srcSize_wrong);
1259
1260     /* Decode literals section */
1261     {   size_t const litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize);
1262         DEBUGLOG(5, "ZSTD_decodeLiteralsBlock : %u", (U32)litCSize);
1263         if (ZSTD_isError(litCSize)) return litCSize;
1264         ip += litCSize;
1265         srcSize -= litCSize;
1266     }
1267
1268     /* Build Decoding Tables */
1269     {
1270         /* These macros control at build-time which decompressor implementation
1271          * we use. If neither is defined, we do some inspection and dispatch at
1272          * runtime.
1273          */
1274 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1275     !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1276         int usePrefetchDecoder = dctx->ddictIsCold;
1277 #endif
1278         int nbSeq;
1279         size_t const seqHSize = ZSTD_decodeSeqHeaders(dctx, &nbSeq, ip, srcSize);
1280         if (ZSTD_isError(seqHSize)) return seqHSize;
1281         ip += seqHSize;
1282         srcSize -= seqHSize;
1283
1284 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1285     !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1286         if ( !usePrefetchDecoder
1287           && (!frame || (dctx->fParams.windowSize > (1<<24)))
1288           && (nbSeq>ADVANCED_SEQS) ) {  /* could probably use a larger nbSeq limit */
1289             U32 const shareLongOffsets = ZSTD_getLongOffsetsShare(dctx->OFTptr);
1290             U32 const minShare = MEM_64bits() ? 7 : 20; /* heuristic values, correspond to 2.73% and 7.81% */
1291             usePrefetchDecoder = (shareLongOffsets >= minShare);
1292         }
1293 #endif
1294
1295         dctx->ddictIsCold = 0;
1296
1297 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1298     !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1299         if (usePrefetchDecoder)
1300 #endif
1301 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
1302             return ZSTD_decompressSequencesLong(dctx, dst, dstCapacity, ip, srcSize, nbSeq, isLongOffset);
1303 #endif
1304
1305 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
1306         /* else */
1307         return ZSTD_decompressSequences(dctx, dst, dstCapacity, ip, srcSize, nbSeq, isLongOffset);
1308 #endif
1309     }
1310 }
1311
1312
1313 size_t ZSTD_decompressBlock(ZSTD_DCtx* dctx,
1314                             void* dst, size_t dstCapacity,
1315                       const void* src, size_t srcSize)
1316 {
1317     size_t dSize;
1318     ZSTD_checkContinuity(dctx, dst);
1319     dSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize, /* frame */ 0);
1320     dctx->previousDstEnd = (char*)dst + dSize;
1321     return dSize;
1322 }