Back to home page

OSCL-LXR
 
 

     

0001 /*
0002  * Copyright (c) Yann Collet, Facebook, Inc.
0003  * All rights reserved.
0004  *
0005  * This source code is licensed under both the BSD-style license (found in the
0006  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
0007  * in the COPYING file in the root directory of this source tree).
0008  * You may select, at your option, one of the above-listed licenses.
0009  */
0010 
0011 /* zstd_decompress_block :
0012  * this module takes care of decompressing _compressed_ block */
0013 
0014 /*-*******************************************************
0015 *  Dependencies
0016 *********************************************************/
0017 #include "../common/zstd_deps.h"   /* ZSTD_memcpy, ZSTD_memmove, ZSTD_memset */
0018 #include "../common/compiler.h"    /* prefetch */
0019 #include "../common/cpu.h"         /* bmi2 */
0020 #include "../common/mem.h"         /* low level memory routines */
0021 #define FSE_STATIC_LINKING_ONLY
0022 #include "../common/fse.h"
0023 #define HUF_STATIC_LINKING_ONLY
0024 #include "../common/huf.h"
0025 #include "../common/zstd_internal.h"
0026 #include "zstd_decompress_internal.h"   /* ZSTD_DCtx */
0027 #include "zstd_ddict.h"  /* ZSTD_DDictDictContent */
0028 #include "zstd_decompress_block.h"
0029 
0030 /*_*******************************************************
0031 *  Macros
0032 **********************************************************/
0033 
0034 /* These two optional macros force the use one way or another of the two
0035  * ZSTD_decompressSequences implementations. You can't force in both directions
0036  * at the same time.
0037  */
0038 #if defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
0039     defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
0040 #error "Cannot force the use of the short and the long ZSTD_decompressSequences variants!"
0041 #endif
0042 
0043 
0044 /*_*******************************************************
0045 *  Memory operations
0046 **********************************************************/
0047 static void ZSTD_copy4(void* dst, const void* src) { ZSTD_memcpy(dst, src, 4); }
0048 
0049 
0050 /*-*************************************************************
0051  *   Block decoding
0052  ***************************************************************/
0053 
0054 /*! ZSTD_getcBlockSize() :
0055  *  Provides the size of compressed block from block header `src` */
0056 size_t ZSTD_getcBlockSize(const void* src, size_t srcSize,
0057                           blockProperties_t* bpPtr)
0058 {
0059     RETURN_ERROR_IF(srcSize < ZSTD_blockHeaderSize, srcSize_wrong, "");
0060 
0061     {   U32 const cBlockHeader = MEM_readLE24(src);
0062         U32 const cSize = cBlockHeader >> 3;
0063         bpPtr->lastBlock = cBlockHeader & 1;
0064         bpPtr->blockType = (blockType_e)((cBlockHeader >> 1) & 3);
0065         bpPtr->origSize = cSize;   /* only useful for RLE */
0066         if (bpPtr->blockType == bt_rle) return 1;
0067         RETURN_ERROR_IF(bpPtr->blockType == bt_reserved, corruption_detected, "");
0068         return cSize;
0069     }
0070 }
0071 
0072 
0073 /* Hidden declaration for fullbench */
0074 size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx,
0075                           const void* src, size_t srcSize);
0076 /*! ZSTD_decodeLiteralsBlock() :
0077  * @return : nb of bytes read from src (< srcSize )
0078  *  note : symbol not declared but exposed for fullbench */
0079 size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx,
0080                           const void* src, size_t srcSize)   /* note : srcSize < BLOCKSIZE */
0081 {
0082     DEBUGLOG(5, "ZSTD_decodeLiteralsBlock");
0083     RETURN_ERROR_IF(srcSize < MIN_CBLOCK_SIZE, corruption_detected, "");
0084 
0085     {   const BYTE* const istart = (const BYTE*) src;
0086         symbolEncodingType_e const litEncType = (symbolEncodingType_e)(istart[0] & 3);
0087 
0088         switch(litEncType)
0089         {
0090         case set_repeat:
0091             DEBUGLOG(5, "set_repeat flag : re-using stats from previous compressed literals block");
0092             RETURN_ERROR_IF(dctx->litEntropy==0, dictionary_corrupted, "");
0093             ZSTD_FALLTHROUGH;
0094 
0095         case set_compressed:
0096             RETURN_ERROR_IF(srcSize < 5, corruption_detected, "srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for case 3");
0097             {   size_t lhSize, litSize, litCSize;
0098                 U32 singleStream=0;
0099                 U32 const lhlCode = (istart[0] >> 2) & 3;
0100                 U32 const lhc = MEM_readLE32(istart);
0101                 size_t hufSuccess;
0102                 switch(lhlCode)
0103                 {
0104                 case 0: case 1: default:   /* note : default is impossible, since lhlCode into [0..3] */
0105                     /* 2 - 2 - 10 - 10 */
0106                     singleStream = !lhlCode;
0107                     lhSize = 3;
0108                     litSize  = (lhc >> 4) & 0x3FF;
0109                     litCSize = (lhc >> 14) & 0x3FF;
0110                     break;
0111                 case 2:
0112                     /* 2 - 2 - 14 - 14 */
0113                     lhSize = 4;
0114                     litSize  = (lhc >> 4) & 0x3FFF;
0115                     litCSize = lhc >> 18;
0116                     break;
0117                 case 3:
0118                     /* 2 - 2 - 18 - 18 */
0119                     lhSize = 5;
0120                     litSize  = (lhc >> 4) & 0x3FFFF;
0121                     litCSize = (lhc >> 22) + ((size_t)istart[4] << 10);
0122                     break;
0123                 }
0124                 RETURN_ERROR_IF(litSize > ZSTD_BLOCKSIZE_MAX, corruption_detected, "");
0125                 RETURN_ERROR_IF(litCSize + lhSize > srcSize, corruption_detected, "");
0126 
0127                 /* prefetch huffman table if cold */
0128                 if (dctx->ddictIsCold && (litSize > 768 /* heuristic */)) {
0129                     PREFETCH_AREA(dctx->HUFptr, sizeof(dctx->entropy.hufTable));
0130                 }
0131 
0132                 if (litEncType==set_repeat) {
0133                     if (singleStream) {
0134                         hufSuccess = HUF_decompress1X_usingDTable_bmi2(
0135                             dctx->litBuffer, litSize, istart+lhSize, litCSize,
0136                             dctx->HUFptr, dctx->bmi2);
0137                     } else {
0138                         hufSuccess = HUF_decompress4X_usingDTable_bmi2(
0139                             dctx->litBuffer, litSize, istart+lhSize, litCSize,
0140                             dctx->HUFptr, dctx->bmi2);
0141                     }
0142                 } else {
0143                     if (singleStream) {
0144 #if defined(HUF_FORCE_DECOMPRESS_X2)
0145                         hufSuccess = HUF_decompress1X_DCtx_wksp(
0146                             dctx->entropy.hufTable, dctx->litBuffer, litSize,
0147                             istart+lhSize, litCSize, dctx->workspace,
0148                             sizeof(dctx->workspace));
0149 #else
0150                         hufSuccess = HUF_decompress1X1_DCtx_wksp_bmi2(
0151                             dctx->entropy.hufTable, dctx->litBuffer, litSize,
0152                             istart+lhSize, litCSize, dctx->workspace,
0153                             sizeof(dctx->workspace), dctx->bmi2);
0154 #endif
0155                     } else {
0156                         hufSuccess = HUF_decompress4X_hufOnly_wksp_bmi2(
0157                             dctx->entropy.hufTable, dctx->litBuffer, litSize,
0158                             istart+lhSize, litCSize, dctx->workspace,
0159                             sizeof(dctx->workspace), dctx->bmi2);
0160                     }
0161                 }
0162 
0163                 RETURN_ERROR_IF(HUF_isError(hufSuccess), corruption_detected, "");
0164 
0165                 dctx->litPtr = dctx->litBuffer;
0166                 dctx->litSize = litSize;
0167                 dctx->litEntropy = 1;
0168                 if (litEncType==set_compressed) dctx->HUFptr = dctx->entropy.hufTable;
0169                 ZSTD_memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
0170                 return litCSize + lhSize;
0171             }
0172 
0173         case set_basic:
0174             {   size_t litSize, lhSize;
0175                 U32 const lhlCode = ((istart[0]) >> 2) & 3;
0176                 switch(lhlCode)
0177                 {
0178                 case 0: case 2: default:   /* note : default is impossible, since lhlCode into [0..3] */
0179                     lhSize = 1;
0180                     litSize = istart[0] >> 3;
0181                     break;
0182                 case 1:
0183                     lhSize = 2;
0184                     litSize = MEM_readLE16(istart) >> 4;
0185                     break;
0186                 case 3:
0187                     lhSize = 3;
0188                     litSize = MEM_readLE24(istart) >> 4;
0189                     break;
0190                 }
0191 
0192                 if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) {  /* risk reading beyond src buffer with wildcopy */
0193                     RETURN_ERROR_IF(litSize+lhSize > srcSize, corruption_detected, "");
0194                     ZSTD_memcpy(dctx->litBuffer, istart+lhSize, litSize);
0195                     dctx->litPtr = dctx->litBuffer;
0196                     dctx->litSize = litSize;
0197                     ZSTD_memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
0198                     return lhSize+litSize;
0199                 }
0200                 /* direct reference into compressed stream */
0201                 dctx->litPtr = istart+lhSize;
0202                 dctx->litSize = litSize;
0203                 return lhSize+litSize;
0204             }
0205 
0206         case set_rle:
0207             {   U32 const lhlCode = ((istart[0]) >> 2) & 3;
0208                 size_t litSize, lhSize;
0209                 switch(lhlCode)
0210                 {
0211                 case 0: case 2: default:   /* note : default is impossible, since lhlCode into [0..3] */
0212                     lhSize = 1;
0213                     litSize = istart[0] >> 3;
0214                     break;
0215                 case 1:
0216                     lhSize = 2;
0217                     litSize = MEM_readLE16(istart) >> 4;
0218                     break;
0219                 case 3:
0220                     lhSize = 3;
0221                     litSize = MEM_readLE24(istart) >> 4;
0222                     RETURN_ERROR_IF(srcSize<4, corruption_detected, "srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4");
0223                     break;
0224                 }
0225                 RETURN_ERROR_IF(litSize > ZSTD_BLOCKSIZE_MAX, corruption_detected, "");
0226                 ZSTD_memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
0227                 dctx->litPtr = dctx->litBuffer;
0228                 dctx->litSize = litSize;
0229                 return lhSize+1;
0230             }
0231         default:
0232             RETURN_ERROR(corruption_detected, "impossible");
0233         }
0234     }
0235 }
0236 
0237 /* Default FSE distribution tables.
0238  * These are pre-calculated FSE decoding tables using default distributions as defined in specification :
0239  * https://github.com/facebook/zstd/blob/release/doc/zstd_compression_format.md#default-distributions
0240  * They were generated programmatically with following method :
0241  * - start from default distributions, present in /lib/common/zstd_internal.h
0242  * - generate tables normally, using ZSTD_buildFSETable()
0243  * - printout the content of tables
0244  * - pretify output, report below, test with fuzzer to ensure it's correct */
0245 
0246 /* Default FSE distribution table for Literal Lengths */
0247 static const ZSTD_seqSymbol LL_defaultDTable[(1<<LL_DEFAULTNORMLOG)+1] = {
0248      {  1,  1,  1, LL_DEFAULTNORMLOG},  /* header : fastMode, tableLog */
0249      /* nextState, nbAddBits, nbBits, baseVal */
0250      {  0,  0,  4,    0},  { 16,  0,  4,    0},
0251      { 32,  0,  5,    1},  {  0,  0,  5,    3},
0252      {  0,  0,  5,    4},  {  0,  0,  5,    6},
0253      {  0,  0,  5,    7},  {  0,  0,  5,    9},
0254      {  0,  0,  5,   10},  {  0,  0,  5,   12},
0255      {  0,  0,  6,   14},  {  0,  1,  5,   16},
0256      {  0,  1,  5,   20},  {  0,  1,  5,   22},
0257      {  0,  2,  5,   28},  {  0,  3,  5,   32},
0258      {  0,  4,  5,   48},  { 32,  6,  5,   64},
0259      {  0,  7,  5,  128},  {  0,  8,  6,  256},
0260      {  0, 10,  6, 1024},  {  0, 12,  6, 4096},
0261      { 32,  0,  4,    0},  {  0,  0,  4,    1},
0262      {  0,  0,  5,    2},  { 32,  0,  5,    4},
0263      {  0,  0,  5,    5},  { 32,  0,  5,    7},
0264      {  0,  0,  5,    8},  { 32,  0,  5,   10},
0265      {  0,  0,  5,   11},  {  0,  0,  6,   13},
0266      { 32,  1,  5,   16},  {  0,  1,  5,   18},
0267      { 32,  1,  5,   22},  {  0,  2,  5,   24},
0268      { 32,  3,  5,   32},  {  0,  3,  5,   40},
0269      {  0,  6,  4,   64},  { 16,  6,  4,   64},
0270      { 32,  7,  5,  128},  {  0,  9,  6,  512},
0271      {  0, 11,  6, 2048},  { 48,  0,  4,    0},
0272      { 16,  0,  4,    1},  { 32,  0,  5,    2},
0273      { 32,  0,  5,    3},  { 32,  0,  5,    5},
0274      { 32,  0,  5,    6},  { 32,  0,  5,    8},
0275      { 32,  0,  5,    9},  { 32,  0,  5,   11},
0276      { 32,  0,  5,   12},  {  0,  0,  6,   15},
0277      { 32,  1,  5,   18},  { 32,  1,  5,   20},
0278      { 32,  2,  5,   24},  { 32,  2,  5,   28},
0279      { 32,  3,  5,   40},  { 32,  4,  5,   48},
0280      {  0, 16,  6,65536},  {  0, 15,  6,32768},
0281      {  0, 14,  6,16384},  {  0, 13,  6, 8192},
0282 };   /* LL_defaultDTable */
0283 
0284 /* Default FSE distribution table for Offset Codes */
0285 static const ZSTD_seqSymbol OF_defaultDTable[(1<<OF_DEFAULTNORMLOG)+1] = {
0286     {  1,  1,  1, OF_DEFAULTNORMLOG},  /* header : fastMode, tableLog */
0287     /* nextState, nbAddBits, nbBits, baseVal */
0288     {  0,  0,  5,    0},     {  0,  6,  4,   61},
0289     {  0,  9,  5,  509},     {  0, 15,  5,32765},
0290     {  0, 21,  5,2097149},   {  0,  3,  5,    5},
0291     {  0,  7,  4,  125},     {  0, 12,  5, 4093},
0292     {  0, 18,  5,262141},    {  0, 23,  5,8388605},
0293     {  0,  5,  5,   29},     {  0,  8,  4,  253},
0294     {  0, 14,  5,16381},     {  0, 20,  5,1048573},
0295     {  0,  2,  5,    1},     { 16,  7,  4,  125},
0296     {  0, 11,  5, 2045},     {  0, 17,  5,131069},
0297     {  0, 22,  5,4194301},   {  0,  4,  5,   13},
0298     { 16,  8,  4,  253},     {  0, 13,  5, 8189},
0299     {  0, 19,  5,524285},    {  0,  1,  5,    1},
0300     { 16,  6,  4,   61},     {  0, 10,  5, 1021},
0301     {  0, 16,  5,65533},     {  0, 28,  5,268435453},
0302     {  0, 27,  5,134217725}, {  0, 26,  5,67108861},
0303     {  0, 25,  5,33554429},  {  0, 24,  5,16777213},
0304 };   /* OF_defaultDTable */
0305 
0306 
0307 /* Default FSE distribution table for Match Lengths */
0308 static const ZSTD_seqSymbol ML_defaultDTable[(1<<ML_DEFAULTNORMLOG)+1] = {
0309     {  1,  1,  1, ML_DEFAULTNORMLOG},  /* header : fastMode, tableLog */
0310     /* nextState, nbAddBits, nbBits, baseVal */
0311     {  0,  0,  6,    3},  {  0,  0,  4,    4},
0312     { 32,  0,  5,    5},  {  0,  0,  5,    6},
0313     {  0,  0,  5,    8},  {  0,  0,  5,    9},
0314     {  0,  0,  5,   11},  {  0,  0,  6,   13},
0315     {  0,  0,  6,   16},  {  0,  0,  6,   19},
0316     {  0,  0,  6,   22},  {  0,  0,  6,   25},
0317     {  0,  0,  6,   28},  {  0,  0,  6,   31},
0318     {  0,  0,  6,   34},  {  0,  1,  6,   37},
0319     {  0,  1,  6,   41},  {  0,  2,  6,   47},
0320     {  0,  3,  6,   59},  {  0,  4,  6,   83},
0321     {  0,  7,  6,  131},  {  0,  9,  6,  515},
0322     { 16,  0,  4,    4},  {  0,  0,  4,    5},
0323     { 32,  0,  5,    6},  {  0,  0,  5,    7},
0324     { 32,  0,  5,    9},  {  0,  0,  5,   10},
0325     {  0,  0,  6,   12},  {  0,  0,  6,   15},
0326     {  0,  0,  6,   18},  {  0,  0,  6,   21},
0327     {  0,  0,  6,   24},  {  0,  0,  6,   27},
0328     {  0,  0,  6,   30},  {  0,  0,  6,   33},
0329     {  0,  1,  6,   35},  {  0,  1,  6,   39},
0330     {  0,  2,  6,   43},  {  0,  3,  6,   51},
0331     {  0,  4,  6,   67},  {  0,  5,  6,   99},
0332     {  0,  8,  6,  259},  { 32,  0,  4,    4},
0333     { 48,  0,  4,    4},  { 16,  0,  4,    5},
0334     { 32,  0,  5,    7},  { 32,  0,  5,    8},
0335     { 32,  0,  5,   10},  { 32,  0,  5,   11},
0336     {  0,  0,  6,   14},  {  0,  0,  6,   17},
0337     {  0,  0,  6,   20},  {  0,  0,  6,   23},
0338     {  0,  0,  6,   26},  {  0,  0,  6,   29},
0339     {  0,  0,  6,   32},  {  0, 16,  6,65539},
0340     {  0, 15,  6,32771},  {  0, 14,  6,16387},
0341     {  0, 13,  6, 8195},  {  0, 12,  6, 4099},
0342     {  0, 11,  6, 2051},  {  0, 10,  6, 1027},
0343 };   /* ML_defaultDTable */
0344 
0345 
0346 static void ZSTD_buildSeqTable_rle(ZSTD_seqSymbol* dt, U32 baseValue, U32 nbAddBits)
0347 {
0348     void* ptr = dt;
0349     ZSTD_seqSymbol_header* const DTableH = (ZSTD_seqSymbol_header*)ptr;
0350     ZSTD_seqSymbol* const cell = dt + 1;
0351 
0352     DTableH->tableLog = 0;
0353     DTableH->fastMode = 0;
0354 
0355     cell->nbBits = 0;
0356     cell->nextState = 0;
0357     assert(nbAddBits < 255);
0358     cell->nbAdditionalBits = (BYTE)nbAddBits;
0359     cell->baseValue = baseValue;
0360 }
0361 
0362 
0363 /* ZSTD_buildFSETable() :
0364  * generate FSE decoding table for one symbol (ll, ml or off)
0365  * cannot fail if input is valid =>
0366  * all inputs are presumed validated at this stage */
0367 FORCE_INLINE_TEMPLATE
0368 void ZSTD_buildFSETable_body(ZSTD_seqSymbol* dt,
0369             const short* normalizedCounter, unsigned maxSymbolValue,
0370             const U32* baseValue, const U32* nbAdditionalBits,
0371             unsigned tableLog, void* wksp, size_t wkspSize)
0372 {
0373     ZSTD_seqSymbol* const tableDecode = dt+1;
0374     U32 const maxSV1 = maxSymbolValue + 1;
0375     U32 const tableSize = 1 << tableLog;
0376 
0377     U16* symbolNext = (U16*)wksp;
0378     BYTE* spread = (BYTE*)(symbolNext + MaxSeq + 1);
0379     U32 highThreshold = tableSize - 1;
0380 
0381 
0382     /* Sanity Checks */
0383     assert(maxSymbolValue <= MaxSeq);
0384     assert(tableLog <= MaxFSELog);
0385     assert(wkspSize >= ZSTD_BUILD_FSE_TABLE_WKSP_SIZE);
0386     (void)wkspSize;
0387     /* Init, lay down lowprob symbols */
0388     {   ZSTD_seqSymbol_header DTableH;
0389         DTableH.tableLog = tableLog;
0390         DTableH.fastMode = 1;
0391         {   S16 const largeLimit= (S16)(1 << (tableLog-1));
0392             U32 s;
0393             for (s=0; s<maxSV1; s++) {
0394                 if (normalizedCounter[s]==-1) {
0395                     tableDecode[highThreshold--].baseValue = s;
0396                     symbolNext[s] = 1;
0397                 } else {
0398                     if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
0399                     assert(normalizedCounter[s]>=0);
0400                     symbolNext[s] = (U16)normalizedCounter[s];
0401         }   }   }
0402         ZSTD_memcpy(dt, &DTableH, sizeof(DTableH));
0403     }
0404 
0405     /* Spread symbols */
0406     assert(tableSize <= 512);
0407     /* Specialized symbol spreading for the case when there are
0408      * no low probability (-1 count) symbols. When compressing
0409      * small blocks we avoid low probability symbols to hit this
0410      * case, since header decoding speed matters more.
0411      */
0412     if (highThreshold == tableSize - 1) {
0413         size_t const tableMask = tableSize-1;
0414         size_t const step = FSE_TABLESTEP(tableSize);
0415         /* First lay down the symbols in order.
0416          * We use a uint64_t to lay down 8 bytes at a time. This reduces branch
0417          * misses since small blocks generally have small table logs, so nearly
0418          * all symbols have counts <= 8. We ensure we have 8 bytes at the end of
0419          * our buffer to handle the over-write.
0420          */
0421         {
0422             U64 const add = 0x0101010101010101ull;
0423             size_t pos = 0;
0424             U64 sv = 0;
0425             U32 s;
0426             for (s=0; s<maxSV1; ++s, sv += add) {
0427                 int i;
0428                 int const n = normalizedCounter[s];
0429                 MEM_write64(spread + pos, sv);
0430                 for (i = 8; i < n; i += 8) {
0431                     MEM_write64(spread + pos + i, sv);
0432                 }
0433                 pos += n;
0434             }
0435         }
0436         /* Now we spread those positions across the table.
0437          * The benefit of doing it in two stages is that we avoid the the
0438          * variable size inner loop, which caused lots of branch misses.
0439          * Now we can run through all the positions without any branch misses.
0440          * We unroll the loop twice, since that is what emperically worked best.
0441          */
0442         {
0443             size_t position = 0;
0444             size_t s;
0445             size_t const unroll = 2;
0446             assert(tableSize % unroll == 0); /* FSE_MIN_TABLELOG is 5 */
0447             for (s = 0; s < (size_t)tableSize; s += unroll) {
0448                 size_t u;
0449                 for (u = 0; u < unroll; ++u) {
0450                     size_t const uPosition = (position + (u * step)) & tableMask;
0451                     tableDecode[uPosition].baseValue = spread[s + u];
0452                 }
0453                 position = (position + (unroll * step)) & tableMask;
0454             }
0455             assert(position == 0);
0456         }
0457     } else {
0458         U32 const tableMask = tableSize-1;
0459         U32 const step = FSE_TABLESTEP(tableSize);
0460         U32 s, position = 0;
0461         for (s=0; s<maxSV1; s++) {
0462             int i;
0463             int const n = normalizedCounter[s];
0464             for (i=0; i<n; i++) {
0465                 tableDecode[position].baseValue = s;
0466                 position = (position + step) & tableMask;
0467                 while (position > highThreshold) position = (position + step) & tableMask;   /* lowprob area */
0468         }   }
0469         assert(position == 0); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
0470     }
0471 
0472     /* Build Decoding table */
0473     {
0474         U32 u;
0475         for (u=0; u<tableSize; u++) {
0476             U32 const symbol = tableDecode[u].baseValue;
0477             U32 const nextState = symbolNext[symbol]++;
0478             tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32(nextState) );
0479             tableDecode[u].nextState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
0480             assert(nbAdditionalBits[symbol] < 255);
0481             tableDecode[u].nbAdditionalBits = (BYTE)nbAdditionalBits[symbol];
0482             tableDecode[u].baseValue = baseValue[symbol];
0483         }
0484     }
0485 }
0486 
0487 /* Avoids the FORCE_INLINE of the _body() function. */
0488 static void ZSTD_buildFSETable_body_default(ZSTD_seqSymbol* dt,
0489             const short* normalizedCounter, unsigned maxSymbolValue,
0490             const U32* baseValue, const U32* nbAdditionalBits,
0491             unsigned tableLog, void* wksp, size_t wkspSize)
0492 {
0493     ZSTD_buildFSETable_body(dt, normalizedCounter, maxSymbolValue,
0494             baseValue, nbAdditionalBits, tableLog, wksp, wkspSize);
0495 }
0496 
0497 #if DYNAMIC_BMI2
0498 TARGET_ATTRIBUTE("bmi2") static void ZSTD_buildFSETable_body_bmi2(ZSTD_seqSymbol* dt,
0499             const short* normalizedCounter, unsigned maxSymbolValue,
0500             const U32* baseValue, const U32* nbAdditionalBits,
0501             unsigned tableLog, void* wksp, size_t wkspSize)
0502 {
0503     ZSTD_buildFSETable_body(dt, normalizedCounter, maxSymbolValue,
0504             baseValue, nbAdditionalBits, tableLog, wksp, wkspSize);
0505 }
0506 #endif
0507 
0508 void ZSTD_buildFSETable(ZSTD_seqSymbol* dt,
0509             const short* normalizedCounter, unsigned maxSymbolValue,
0510             const U32* baseValue, const U32* nbAdditionalBits,
0511             unsigned tableLog, void* wksp, size_t wkspSize, int bmi2)
0512 {
0513 #if DYNAMIC_BMI2
0514     if (bmi2) {
0515         ZSTD_buildFSETable_body_bmi2(dt, normalizedCounter, maxSymbolValue,
0516                 baseValue, nbAdditionalBits, tableLog, wksp, wkspSize);
0517         return;
0518     }
0519 #endif
0520     (void)bmi2;
0521     ZSTD_buildFSETable_body_default(dt, normalizedCounter, maxSymbolValue,
0522             baseValue, nbAdditionalBits, tableLog, wksp, wkspSize);
0523 }
0524 
0525 
0526 /*! ZSTD_buildSeqTable() :
0527  * @return : nb bytes read from src,
0528  *           or an error code if it fails */
0529 static size_t ZSTD_buildSeqTable(ZSTD_seqSymbol* DTableSpace, const ZSTD_seqSymbol** DTablePtr,
0530                                  symbolEncodingType_e type, unsigned max, U32 maxLog,
0531                                  const void* src, size_t srcSize,
0532                                  const U32* baseValue, const U32* nbAdditionalBits,
0533                                  const ZSTD_seqSymbol* defaultTable, U32 flagRepeatTable,
0534                                  int ddictIsCold, int nbSeq, U32* wksp, size_t wkspSize,
0535                                  int bmi2)
0536 {
0537     switch(type)
0538     {
0539     case set_rle :
0540         RETURN_ERROR_IF(!srcSize, srcSize_wrong, "");
0541         RETURN_ERROR_IF((*(const BYTE*)src) > max, corruption_detected, "");
0542         {   U32 const symbol = *(const BYTE*)src;
0543             U32 const baseline = baseValue[symbol];
0544             U32 const nbBits = nbAdditionalBits[symbol];
0545             ZSTD_buildSeqTable_rle(DTableSpace, baseline, nbBits);
0546         }
0547         *DTablePtr = DTableSpace;
0548         return 1;
0549     case set_basic :
0550         *DTablePtr = defaultTable;
0551         return 0;
0552     case set_repeat:
0553         RETURN_ERROR_IF(!flagRepeatTable, corruption_detected, "");
0554         /* prefetch FSE table if used */
0555         if (ddictIsCold && (nbSeq > 24 /* heuristic */)) {
0556             const void* const pStart = *DTablePtr;
0557             size_t const pSize = sizeof(ZSTD_seqSymbol) * (SEQSYMBOL_TABLE_SIZE(maxLog));
0558             PREFETCH_AREA(pStart, pSize);
0559         }
0560         return 0;
0561     case set_compressed :
0562         {   unsigned tableLog;
0563             S16 norm[MaxSeq+1];
0564             size_t const headerSize = FSE_readNCount(norm, &max, &tableLog, src, srcSize);
0565             RETURN_ERROR_IF(FSE_isError(headerSize), corruption_detected, "");
0566             RETURN_ERROR_IF(tableLog > maxLog, corruption_detected, "");
0567             ZSTD_buildFSETable(DTableSpace, norm, max, baseValue, nbAdditionalBits, tableLog, wksp, wkspSize, bmi2);
0568             *DTablePtr = DTableSpace;
0569             return headerSize;
0570         }
0571     default :
0572         assert(0);
0573         RETURN_ERROR(GENERIC, "impossible");
0574     }
0575 }
0576 
0577 size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr,
0578                              const void* src, size_t srcSize)
0579 {
0580     const BYTE* const istart = (const BYTE*)src;
0581     const BYTE* const iend = istart + srcSize;
0582     const BYTE* ip = istart;
0583     int nbSeq;
0584     DEBUGLOG(5, "ZSTD_decodeSeqHeaders");
0585 
0586     /* check */
0587     RETURN_ERROR_IF(srcSize < MIN_SEQUENCES_SIZE, srcSize_wrong, "");
0588 
0589     /* SeqHead */
0590     nbSeq = *ip++;
0591     if (!nbSeq) {
0592         *nbSeqPtr=0;
0593         RETURN_ERROR_IF(srcSize != 1, srcSize_wrong, "");
0594         return 1;
0595     }
0596     if (nbSeq > 0x7F) {
0597         if (nbSeq == 0xFF) {
0598             RETURN_ERROR_IF(ip+2 > iend, srcSize_wrong, "");
0599             nbSeq = MEM_readLE16(ip) + LONGNBSEQ;
0600             ip+=2;
0601         } else {
0602             RETURN_ERROR_IF(ip >= iend, srcSize_wrong, "");
0603             nbSeq = ((nbSeq-0x80)<<8) + *ip++;
0604         }
0605     }
0606     *nbSeqPtr = nbSeq;
0607 
0608     /* FSE table descriptors */
0609     RETURN_ERROR_IF(ip+1 > iend, srcSize_wrong, ""); /* minimum possible size: 1 byte for symbol encoding types */
0610     {   symbolEncodingType_e const LLtype = (symbolEncodingType_e)(*ip >> 6);
0611         symbolEncodingType_e const OFtype = (symbolEncodingType_e)((*ip >> 4) & 3);
0612         symbolEncodingType_e const MLtype = (symbolEncodingType_e)((*ip >> 2) & 3);
0613         ip++;
0614 
0615         /* Build DTables */
0616         {   size_t const llhSize = ZSTD_buildSeqTable(dctx->entropy.LLTable, &dctx->LLTptr,
0617                                                       LLtype, MaxLL, LLFSELog,
0618                                                       ip, iend-ip,
0619                                                       LL_base, LL_bits,
0620                                                       LL_defaultDTable, dctx->fseEntropy,
0621                                                       dctx->ddictIsCold, nbSeq,
0622                                                       dctx->workspace, sizeof(dctx->workspace),
0623                                                       dctx->bmi2);
0624             RETURN_ERROR_IF(ZSTD_isError(llhSize), corruption_detected, "ZSTD_buildSeqTable failed");
0625             ip += llhSize;
0626         }
0627 
0628         {   size_t const ofhSize = ZSTD_buildSeqTable(dctx->entropy.OFTable, &dctx->OFTptr,
0629                                                       OFtype, MaxOff, OffFSELog,
0630                                                       ip, iend-ip,
0631                                                       OF_base, OF_bits,
0632                                                       OF_defaultDTable, dctx->fseEntropy,
0633                                                       dctx->ddictIsCold, nbSeq,
0634                                                       dctx->workspace, sizeof(dctx->workspace),
0635                                                       dctx->bmi2);
0636             RETURN_ERROR_IF(ZSTD_isError(ofhSize), corruption_detected, "ZSTD_buildSeqTable failed");
0637             ip += ofhSize;
0638         }
0639 
0640         {   size_t const mlhSize = ZSTD_buildSeqTable(dctx->entropy.MLTable, &dctx->MLTptr,
0641                                                       MLtype, MaxML, MLFSELog,
0642                                                       ip, iend-ip,
0643                                                       ML_base, ML_bits,
0644                                                       ML_defaultDTable, dctx->fseEntropy,
0645                                                       dctx->ddictIsCold, nbSeq,
0646                                                       dctx->workspace, sizeof(dctx->workspace),
0647                                                       dctx->bmi2);
0648             RETURN_ERROR_IF(ZSTD_isError(mlhSize), corruption_detected, "ZSTD_buildSeqTable failed");
0649             ip += mlhSize;
0650         }
0651     }
0652 
0653     return ip-istart;
0654 }
0655 
0656 
0657 typedef struct {
0658     size_t litLength;
0659     size_t matchLength;
0660     size_t offset;
0661     const BYTE* match;
0662 } seq_t;
0663 
0664 typedef struct {
0665     size_t state;
0666     const ZSTD_seqSymbol* table;
0667 } ZSTD_fseState;
0668 
0669 typedef struct {
0670     BIT_DStream_t DStream;
0671     ZSTD_fseState stateLL;
0672     ZSTD_fseState stateOffb;
0673     ZSTD_fseState stateML;
0674     size_t prevOffset[ZSTD_REP_NUM];
0675     const BYTE* prefixStart;
0676     const BYTE* dictEnd;
0677     size_t pos;
0678 } seqState_t;
0679 
0680 /*! ZSTD_overlapCopy8() :
0681  *  Copies 8 bytes from ip to op and updates op and ip where ip <= op.
0682  *  If the offset is < 8 then the offset is spread to at least 8 bytes.
0683  *
0684  *  Precondition: *ip <= *op
0685  *  Postcondition: *op - *op >= 8
0686  */
0687 HINT_INLINE void ZSTD_overlapCopy8(BYTE** op, BYTE const** ip, size_t offset) {
0688     assert(*ip <= *op);
0689     if (offset < 8) {
0690         /* close range match, overlap */
0691         static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 };   /* added */
0692         static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 };   /* subtracted */
0693         int const sub2 = dec64table[offset];
0694         (*op)[0] = (*ip)[0];
0695         (*op)[1] = (*ip)[1];
0696         (*op)[2] = (*ip)[2];
0697         (*op)[3] = (*ip)[3];
0698         *ip += dec32table[offset];
0699         ZSTD_copy4(*op+4, *ip);
0700         *ip -= sub2;
0701     } else {
0702         ZSTD_copy8(*op, *ip);
0703     }
0704     *ip += 8;
0705     *op += 8;
0706     assert(*op - *ip >= 8);
0707 }
0708 
0709 /*! ZSTD_safecopy() :
0710  *  Specialized version of memcpy() that is allowed to READ up to WILDCOPY_OVERLENGTH past the input buffer
0711  *  and write up to 16 bytes past oend_w (op >= oend_w is allowed).
0712  *  This function is only called in the uncommon case where the sequence is near the end of the block. It
0713  *  should be fast for a single long sequence, but can be slow for several short sequences.
0714  *
0715  *  @param ovtype controls the overlap detection
0716  *         - ZSTD_no_overlap: The source and destination are guaranteed to be at least WILDCOPY_VECLEN bytes apart.
0717  *         - ZSTD_overlap_src_before_dst: The src and dst may overlap and may be any distance apart.
0718  *           The src buffer must be before the dst buffer.
0719  */
0720 static void ZSTD_safecopy(BYTE* op, BYTE* const oend_w, BYTE const* ip, ptrdiff_t length, ZSTD_overlap_e ovtype) {
0721     ptrdiff_t const diff = op - ip;
0722     BYTE* const oend = op + length;
0723 
0724     assert((ovtype == ZSTD_no_overlap && (diff <= -8 || diff >= 8 || op >= oend_w)) ||
0725            (ovtype == ZSTD_overlap_src_before_dst && diff >= 0));
0726 
0727     if (length < 8) {
0728         /* Handle short lengths. */
0729         while (op < oend) *op++ = *ip++;
0730         return;
0731     }
0732     if (ovtype == ZSTD_overlap_src_before_dst) {
0733         /* Copy 8 bytes and ensure the offset >= 8 when there can be overlap. */
0734         assert(length >= 8);
0735         ZSTD_overlapCopy8(&op, &ip, diff);
0736         assert(op - ip >= 8);
0737         assert(op <= oend);
0738     }
0739 
0740     if (oend <= oend_w) {
0741         /* No risk of overwrite. */
0742         ZSTD_wildcopy(op, ip, length, ovtype);
0743         return;
0744     }
0745     if (op <= oend_w) {
0746         /* Wildcopy until we get close to the end. */
0747         assert(oend > oend_w);
0748         ZSTD_wildcopy(op, ip, oend_w - op, ovtype);
0749         ip += oend_w - op;
0750         op = oend_w;
0751     }
0752     /* Handle the leftovers. */
0753     while (op < oend) *op++ = *ip++;
0754 }
0755 
0756 /* ZSTD_execSequenceEnd():
0757  * This version handles cases that are near the end of the output buffer. It requires
0758  * more careful checks to make sure there is no overflow. By separating out these hard
0759  * and unlikely cases, we can speed up the common cases.
0760  *
0761  * NOTE: This function needs to be fast for a single long sequence, but doesn't need
0762  * to be optimized for many small sequences, since those fall into ZSTD_execSequence().
0763  */
0764 FORCE_NOINLINE
0765 size_t ZSTD_execSequenceEnd(BYTE* op,
0766                             BYTE* const oend, seq_t sequence,
0767                             const BYTE** litPtr, const BYTE* const litLimit,
0768                             const BYTE* const prefixStart, const BYTE* const virtualStart, const BYTE* const dictEnd)
0769 {
0770     BYTE* const oLitEnd = op + sequence.litLength;
0771     size_t const sequenceLength = sequence.litLength + sequence.matchLength;
0772     const BYTE* const iLitEnd = *litPtr + sequence.litLength;
0773     const BYTE* match = oLitEnd - sequence.offset;
0774     BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH;
0775 
0776     /* bounds checks : careful of address space overflow in 32-bit mode */
0777     RETURN_ERROR_IF(sequenceLength > (size_t)(oend - op), dstSize_tooSmall, "last match must fit within dstBuffer");
0778     RETURN_ERROR_IF(sequence.litLength > (size_t)(litLimit - *litPtr), corruption_detected, "try to read beyond literal buffer");
0779     assert(op < op + sequenceLength);
0780     assert(oLitEnd < op + sequenceLength);
0781 
0782     /* copy literals */
0783     ZSTD_safecopy(op, oend_w, *litPtr, sequence.litLength, ZSTD_no_overlap);
0784     op = oLitEnd;
0785     *litPtr = iLitEnd;
0786 
0787     /* copy Match */
0788     if (sequence.offset > (size_t)(oLitEnd - prefixStart)) {
0789         /* offset beyond prefix */
0790         RETURN_ERROR_IF(sequence.offset > (size_t)(oLitEnd - virtualStart), corruption_detected, "");
0791         match = dictEnd - (prefixStart-match);
0792         if (match + sequence.matchLength <= dictEnd) {
0793             ZSTD_memmove(oLitEnd, match, sequence.matchLength);
0794             return sequenceLength;
0795         }
0796         /* span extDict & currentPrefixSegment */
0797         {   size_t const length1 = dictEnd - match;
0798             ZSTD_memmove(oLitEnd, match, length1);
0799             op = oLitEnd + length1;
0800             sequence.matchLength -= length1;
0801             match = prefixStart;
0802     }   }
0803     ZSTD_safecopy(op, oend_w, match, sequence.matchLength, ZSTD_overlap_src_before_dst);
0804     return sequenceLength;
0805 }
0806 
0807 HINT_INLINE
0808 size_t ZSTD_execSequence(BYTE* op,
0809                          BYTE* const oend, seq_t sequence,
0810                          const BYTE** litPtr, const BYTE* const litLimit,
0811                          const BYTE* const prefixStart, const BYTE* const virtualStart, const BYTE* const dictEnd)
0812 {
0813     BYTE* const oLitEnd = op + sequence.litLength;
0814     size_t const sequenceLength = sequence.litLength + sequence.matchLength;
0815     BYTE* const oMatchEnd = op + sequenceLength;   /* risk : address space overflow (32-bits) */
0816     BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH;   /* risk : address space underflow on oend=NULL */
0817     const BYTE* const iLitEnd = *litPtr + sequence.litLength;
0818     const BYTE* match = oLitEnd - sequence.offset;
0819 
0820     assert(op != NULL /* Precondition */);
0821     assert(oend_w < oend /* No underflow */);
0822     /* Handle edge cases in a slow path:
0823      *   - Read beyond end of literals
0824      *   - Match end is within WILDCOPY_OVERLIMIT of oend
0825      *   - 32-bit mode and the match length overflows
0826      */
0827     if (UNLIKELY(
0828             iLitEnd > litLimit ||
0829             oMatchEnd > oend_w ||
0830             (MEM_32bits() && (size_t)(oend - op) < sequenceLength + WILDCOPY_OVERLENGTH)))
0831         return ZSTD_execSequenceEnd(op, oend, sequence, litPtr, litLimit, prefixStart, virtualStart, dictEnd);
0832 
0833     /* Assumptions (everything else goes into ZSTD_execSequenceEnd()) */
0834     assert(op <= oLitEnd /* No overflow */);
0835     assert(oLitEnd < oMatchEnd /* Non-zero match & no overflow */);
0836     assert(oMatchEnd <= oend /* No underflow */);
0837     assert(iLitEnd <= litLimit /* Literal length is in bounds */);
0838     assert(oLitEnd <= oend_w /* Can wildcopy literals */);
0839     assert(oMatchEnd <= oend_w /* Can wildcopy matches */);
0840 
0841     /* Copy Literals:
0842      * Split out litLength <= 16 since it is nearly always true. +1.6% on gcc-9.
0843      * We likely don't need the full 32-byte wildcopy.
0844      */
0845     assert(WILDCOPY_OVERLENGTH >= 16);
0846     ZSTD_copy16(op, (*litPtr));
0847     if (UNLIKELY(sequence.litLength > 16)) {
0848         ZSTD_wildcopy(op+16, (*litPtr)+16, sequence.litLength-16, ZSTD_no_overlap);
0849     }
0850     op = oLitEnd;
0851     *litPtr = iLitEnd;   /* update for next sequence */
0852 
0853     /* Copy Match */
0854     if (sequence.offset > (size_t)(oLitEnd - prefixStart)) {
0855         /* offset beyond prefix -> go into extDict */
0856         RETURN_ERROR_IF(UNLIKELY(sequence.offset > (size_t)(oLitEnd - virtualStart)), corruption_detected, "");
0857         match = dictEnd + (match - prefixStart);
0858         if (match + sequence.matchLength <= dictEnd) {
0859             ZSTD_memmove(oLitEnd, match, sequence.matchLength);
0860             return sequenceLength;
0861         }
0862         /* span extDict & currentPrefixSegment */
0863         {   size_t const length1 = dictEnd - match;
0864             ZSTD_memmove(oLitEnd, match, length1);
0865             op = oLitEnd + length1;
0866             sequence.matchLength -= length1;
0867             match = prefixStart;
0868     }   }
0869     /* Match within prefix of 1 or more bytes */
0870     assert(op <= oMatchEnd);
0871     assert(oMatchEnd <= oend_w);
0872     assert(match >= prefixStart);
0873     assert(sequence.matchLength >= 1);
0874 
0875     /* Nearly all offsets are >= WILDCOPY_VECLEN bytes, which means we can use wildcopy
0876      * without overlap checking.
0877      */
0878     if (LIKELY(sequence.offset >= WILDCOPY_VECLEN)) {
0879         /* We bet on a full wildcopy for matches, since we expect matches to be
0880          * longer than literals (in general). In silesia, ~10% of matches are longer
0881          * than 16 bytes.
0882          */
0883         ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength, ZSTD_no_overlap);
0884         return sequenceLength;
0885     }
0886     assert(sequence.offset < WILDCOPY_VECLEN);
0887 
0888     /* Copy 8 bytes and spread the offset to be >= 8. */
0889     ZSTD_overlapCopy8(&op, &match, sequence.offset);
0890 
0891     /* If the match length is > 8 bytes, then continue with the wildcopy. */
0892     if (sequence.matchLength > 8) {
0893         assert(op < oMatchEnd);
0894         ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8, ZSTD_overlap_src_before_dst);
0895     }
0896     return sequenceLength;
0897 }
0898 
0899 static void
0900 ZSTD_initFseState(ZSTD_fseState* DStatePtr, BIT_DStream_t* bitD, const ZSTD_seqSymbol* dt)
0901 {
0902     const void* ptr = dt;
0903     const ZSTD_seqSymbol_header* const DTableH = (const ZSTD_seqSymbol_header*)ptr;
0904     DStatePtr->state = BIT_readBits(bitD, DTableH->tableLog);
0905     DEBUGLOG(6, "ZSTD_initFseState : val=%u using %u bits",
0906                 (U32)DStatePtr->state, DTableH->tableLog);
0907     BIT_reloadDStream(bitD);
0908     DStatePtr->table = dt + 1;
0909 }
0910 
0911 FORCE_INLINE_TEMPLATE void
0912 ZSTD_updateFseState(ZSTD_fseState* DStatePtr, BIT_DStream_t* bitD)
0913 {
0914     ZSTD_seqSymbol const DInfo = DStatePtr->table[DStatePtr->state];
0915     U32 const nbBits = DInfo.nbBits;
0916     size_t const lowBits = BIT_readBits(bitD, nbBits);
0917     DStatePtr->state = DInfo.nextState + lowBits;
0918 }
0919 
0920 FORCE_INLINE_TEMPLATE void
0921 ZSTD_updateFseStateWithDInfo(ZSTD_fseState* DStatePtr, BIT_DStream_t* bitD, ZSTD_seqSymbol const DInfo)
0922 {
0923     U32 const nbBits = DInfo.nbBits;
0924     size_t const lowBits = BIT_readBits(bitD, nbBits);
0925     DStatePtr->state = DInfo.nextState + lowBits;
0926 }
0927 
0928 /* We need to add at most (ZSTD_WINDOWLOG_MAX_32 - 1) bits to read the maximum
0929  * offset bits. But we can only read at most (STREAM_ACCUMULATOR_MIN_32 - 1)
0930  * bits before reloading. This value is the maximum number of bytes we read
0931  * after reloading when we are decoding long offsets.
0932  */
0933 #define LONG_OFFSETS_MAX_EXTRA_BITS_32                       \
0934     (ZSTD_WINDOWLOG_MAX_32 > STREAM_ACCUMULATOR_MIN_32       \
0935         ? ZSTD_WINDOWLOG_MAX_32 - STREAM_ACCUMULATOR_MIN_32  \
0936         : 0)
0937 
0938 typedef enum { ZSTD_lo_isRegularOffset, ZSTD_lo_isLongOffset=1 } ZSTD_longOffset_e;
0939 typedef enum { ZSTD_p_noPrefetch=0, ZSTD_p_prefetch=1 } ZSTD_prefetch_e;
0940 
0941 FORCE_INLINE_TEMPLATE seq_t
0942 ZSTD_decodeSequence(seqState_t* seqState, const ZSTD_longOffset_e longOffsets, const ZSTD_prefetch_e prefetch)
0943 {
0944     seq_t seq;
0945     ZSTD_seqSymbol const llDInfo = seqState->stateLL.table[seqState->stateLL.state];
0946     ZSTD_seqSymbol const mlDInfo = seqState->stateML.table[seqState->stateML.state];
0947     ZSTD_seqSymbol const ofDInfo = seqState->stateOffb.table[seqState->stateOffb.state];
0948     U32 const llBase = llDInfo.baseValue;
0949     U32 const mlBase = mlDInfo.baseValue;
0950     U32 const ofBase = ofDInfo.baseValue;
0951     BYTE const llBits = llDInfo.nbAdditionalBits;
0952     BYTE const mlBits = mlDInfo.nbAdditionalBits;
0953     BYTE const ofBits = ofDInfo.nbAdditionalBits;
0954     BYTE const totalBits = llBits+mlBits+ofBits;
0955 
0956     /* sequence */
0957     {   size_t offset;
0958         if (ofBits > 1) {
0959             ZSTD_STATIC_ASSERT(ZSTD_lo_isLongOffset == 1);
0960             ZSTD_STATIC_ASSERT(LONG_OFFSETS_MAX_EXTRA_BITS_32 == 5);
0961             assert(ofBits <= MaxOff);
0962             if (MEM_32bits() && longOffsets && (ofBits >= STREAM_ACCUMULATOR_MIN_32)) {
0963                 U32 const extraBits = ofBits - MIN(ofBits, 32 - seqState->DStream.bitsConsumed);
0964                 offset = ofBase + (BIT_readBitsFast(&seqState->DStream, ofBits - extraBits) << extraBits);
0965                 BIT_reloadDStream(&seqState->DStream);
0966                 if (extraBits) offset += BIT_readBitsFast(&seqState->DStream, extraBits);
0967                 assert(extraBits <= LONG_OFFSETS_MAX_EXTRA_BITS_32);   /* to avoid another reload */
0968             } else {
0969                 offset = ofBase + BIT_readBitsFast(&seqState->DStream, ofBits/*>0*/);   /* <=  (ZSTD_WINDOWLOG_MAX-1) bits */
0970                 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream);
0971             }
0972             seqState->prevOffset[2] = seqState->prevOffset[1];
0973             seqState->prevOffset[1] = seqState->prevOffset[0];
0974             seqState->prevOffset[0] = offset;
0975         } else {
0976             U32 const ll0 = (llBase == 0);
0977             if (LIKELY((ofBits == 0))) {
0978                 if (LIKELY(!ll0))
0979                     offset = seqState->prevOffset[0];
0980                 else {
0981                     offset = seqState->prevOffset[1];
0982                     seqState->prevOffset[1] = seqState->prevOffset[0];
0983                     seqState->prevOffset[0] = offset;
0984                 }
0985             } else {
0986                 offset = ofBase + ll0 + BIT_readBitsFast(&seqState->DStream, 1);
0987                 {   size_t temp = (offset==3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
0988                     temp += !temp;   /* 0 is not valid; input is corrupted; force offset to 1 */
0989                     if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1];
0990                     seqState->prevOffset[1] = seqState->prevOffset[0];
0991                     seqState->prevOffset[0] = offset = temp;
0992         }   }   }
0993         seq.offset = offset;
0994     }
0995 
0996     seq.matchLength = mlBase;
0997     if (mlBits > 0)
0998         seq.matchLength += BIT_readBitsFast(&seqState->DStream, mlBits/*>0*/);
0999 
1000     if (MEM_32bits() && (mlBits+llBits >= STREAM_ACCUMULATOR_MIN_32-LONG_OFFSETS_MAX_EXTRA_BITS_32))
1001         BIT_reloadDStream(&seqState->DStream);
1002     if (MEM_64bits() && UNLIKELY(totalBits >= STREAM_ACCUMULATOR_MIN_64-(LLFSELog+MLFSELog+OffFSELog)))
1003         BIT_reloadDStream(&seqState->DStream);
1004     /* Ensure there are enough bits to read the rest of data in 64-bit mode. */
1005     ZSTD_STATIC_ASSERT(16+LLFSELog+MLFSELog+OffFSELog < STREAM_ACCUMULATOR_MIN_64);
1006 
1007     seq.litLength = llBase;
1008     if (llBits > 0)
1009         seq.litLength += BIT_readBitsFast(&seqState->DStream, llBits/*>0*/);
1010 
1011     if (MEM_32bits())
1012         BIT_reloadDStream(&seqState->DStream);
1013 
1014     DEBUGLOG(6, "seq: litL=%u, matchL=%u, offset=%u",
1015                 (U32)seq.litLength, (U32)seq.matchLength, (U32)seq.offset);
1016 
1017     if (prefetch == ZSTD_p_prefetch) {
1018         size_t const pos = seqState->pos + seq.litLength;
1019         const BYTE* const matchBase = (seq.offset > pos) ? seqState->dictEnd : seqState->prefixStart;
1020         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.
1021                                                     * No consequence though : no memory access will occur, offset is only used for prefetching */
1022         seqState->pos = pos + seq.matchLength;
1023     }
1024 
1025     /* ANS state update
1026      * gcc-9.0.0 does 2.5% worse with ZSTD_updateFseStateWithDInfo().
1027      * clang-9.2.0 does 7% worse with ZSTD_updateFseState().
1028      * Naturally it seems like ZSTD_updateFseStateWithDInfo() should be the
1029      * better option, so it is the default for other compilers. But, if you
1030      * measure that it is worse, please put up a pull request.
1031      */
1032     {
1033 #if !defined(__clang__)
1034         const int kUseUpdateFseState = 1;
1035 #else
1036         const int kUseUpdateFseState = 0;
1037 #endif
1038         if (kUseUpdateFseState) {
1039             ZSTD_updateFseState(&seqState->stateLL, &seqState->DStream);    /* <=  9 bits */
1040             ZSTD_updateFseState(&seqState->stateML, &seqState->DStream);    /* <=  9 bits */
1041             if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream);    /* <= 18 bits */
1042             ZSTD_updateFseState(&seqState->stateOffb, &seqState->DStream);  /* <=  8 bits */
1043         } else {
1044             ZSTD_updateFseStateWithDInfo(&seqState->stateLL, &seqState->DStream, llDInfo);    /* <=  9 bits */
1045             ZSTD_updateFseStateWithDInfo(&seqState->stateML, &seqState->DStream, mlDInfo);    /* <=  9 bits */
1046             if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream);    /* <= 18 bits */
1047             ZSTD_updateFseStateWithDInfo(&seqState->stateOffb, &seqState->DStream, ofDInfo);  /* <=  8 bits */
1048         }
1049     }
1050 
1051     return seq;
1052 }
1053 
1054 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
1055 MEM_STATIC int ZSTD_dictionaryIsActive(ZSTD_DCtx const* dctx, BYTE const* prefixStart, BYTE const* oLitEnd)
1056 {
1057     size_t const windowSize = dctx->fParams.windowSize;
1058     /* No dictionary used. */
1059     if (dctx->dictContentEndForFuzzing == NULL) return 0;
1060     /* Dictionary is our prefix. */
1061     if (prefixStart == dctx->dictContentBeginForFuzzing) return 1;
1062     /* Dictionary is not our ext-dict. */
1063     if (dctx->dictEnd != dctx->dictContentEndForFuzzing) return 0;
1064     /* Dictionary is not within our window size. */
1065     if ((size_t)(oLitEnd - prefixStart) >= windowSize) return 0;
1066     /* Dictionary is active. */
1067     return 1;
1068 }
1069 
1070 MEM_STATIC void ZSTD_assertValidSequence(
1071         ZSTD_DCtx const* dctx,
1072         BYTE const* op, BYTE const* oend,
1073         seq_t const seq,
1074         BYTE const* prefixStart, BYTE const* virtualStart)
1075 {
1076 #if DEBUGLEVEL >= 1
1077     size_t const windowSize = dctx->fParams.windowSize;
1078     size_t const sequenceSize = seq.litLength + seq.matchLength;
1079     BYTE const* const oLitEnd = op + seq.litLength;
1080     DEBUGLOG(6, "Checking sequence: litL=%u matchL=%u offset=%u",
1081             (U32)seq.litLength, (U32)seq.matchLength, (U32)seq.offset);
1082     assert(op <= oend);
1083     assert((size_t)(oend - op) >= sequenceSize);
1084     assert(sequenceSize <= ZSTD_BLOCKSIZE_MAX);
1085     if (ZSTD_dictionaryIsActive(dctx, prefixStart, oLitEnd)) {
1086         size_t const dictSize = (size_t)((char const*)dctx->dictContentEndForFuzzing - (char const*)dctx->dictContentBeginForFuzzing);
1087         /* Offset must be within the dictionary. */
1088         assert(seq.offset <= (size_t)(oLitEnd - virtualStart));
1089         assert(seq.offset <= windowSize + dictSize);
1090     } else {
1091         /* Offset must be within our window. */
1092         assert(seq.offset <= windowSize);
1093     }
1094 #else
1095     (void)dctx, (void)op, (void)oend, (void)seq, (void)prefixStart, (void)virtualStart;
1096 #endif
1097 }
1098 #endif
1099 
1100 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
1101 FORCE_INLINE_TEMPLATE size_t
1102 DONT_VECTORIZE
1103 ZSTD_decompressSequences_body( ZSTD_DCtx* dctx,
1104                                void* dst, size_t maxDstSize,
1105                          const void* seqStart, size_t seqSize, int nbSeq,
1106                          const ZSTD_longOffset_e isLongOffset,
1107                          const int frame)
1108 {
1109     const BYTE* ip = (const BYTE*)seqStart;
1110     const BYTE* const iend = ip + seqSize;
1111     BYTE* const ostart = (BYTE*)dst;
1112     BYTE* const oend = ostart + maxDstSize;
1113     BYTE* op = ostart;
1114     const BYTE* litPtr = dctx->litPtr;
1115     const BYTE* const litEnd = litPtr + dctx->litSize;
1116     const BYTE* const prefixStart = (const BYTE*) (dctx->prefixStart);
1117     const BYTE* const vBase = (const BYTE*) (dctx->virtualStart);
1118     const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
1119     DEBUGLOG(5, "ZSTD_decompressSequences_body");
1120     (void)frame;
1121 
1122     /* Regen sequences */
1123     if (nbSeq) {
1124         seqState_t seqState;
1125         size_t error = 0;
1126         dctx->fseEntropy = 1;
1127         { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->entropy.rep[i]; }
1128         RETURN_ERROR_IF(
1129             ERR_isError(BIT_initDStream(&seqState.DStream, ip, iend-ip)),
1130             corruption_detected, "");
1131         ZSTD_initFseState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
1132         ZSTD_initFseState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
1133         ZSTD_initFseState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
1134         assert(dst != NULL);
1135 
1136         ZSTD_STATIC_ASSERT(
1137                 BIT_DStream_unfinished < BIT_DStream_completed &&
1138                 BIT_DStream_endOfBuffer < BIT_DStream_completed &&
1139                 BIT_DStream_completed < BIT_DStream_overflow);
1140 
1141 #if defined(__x86_64__)
1142         /* Align the decompression loop to 32 + 16 bytes.
1143          *
1144          * zstd compiled with gcc-9 on an Intel i9-9900k shows 10% decompression
1145          * speed swings based on the alignment of the decompression loop. This
1146          * performance swing is caused by parts of the decompression loop falling
1147          * out of the DSB. The entire decompression loop should fit in the DSB,
1148          * when it can't we get much worse performance. You can measure if you've
1149          * hit the good case or the bad case with this perf command for some
1150          * compressed file test.zst:
1151          *
1152          *   perf stat -e cycles -e instructions -e idq.all_dsb_cycles_any_uops \
1153          *             -e idq.all_mite_cycles_any_uops -- ./zstd -tq test.zst
1154          *
1155          * If you see most cycles served out of the MITE you've hit the bad case.
1156          * If you see most cycles served out of the DSB you've hit the good case.
1157          * If it is pretty even then you may be in an okay case.
1158          *
1159          * I've been able to reproduce this issue on the following CPUs:
1160          *   - Kabylake: Macbook Pro (15-inch, 2019) 2.4 GHz Intel Core i9
1161          *               Use Instruments->Counters to get DSB/MITE cycles.
1162          *               I never got performance swings, but I was able to
1163          *               go from the good case of mostly DSB to half of the
1164          *               cycles served from MITE.
1165          *   - Coffeelake: Intel i9-9900k
1166          *
1167          * I haven't been able to reproduce the instability or DSB misses on any
1168          * of the following CPUS:
1169          *   - Haswell
1170          *   - Broadwell: Intel(R) Xeon(R) CPU E5-2680 v4 @ 2.40GH
1171          *   - Skylake
1172          *
1173          * If you are seeing performance stability this script can help test.
1174          * It tests on 4 commits in zstd where I saw performance change.
1175          *
1176          *   https://gist.github.com/terrelln/9889fc06a423fd5ca6e99351564473f4
1177          */
1178         __asm__(".p2align 5");
1179         __asm__("nop");
1180         __asm__(".p2align 4");
1181 #endif
1182         for ( ; ; ) {
1183             seq_t const sequence = ZSTD_decodeSequence(&seqState, isLongOffset, ZSTD_p_noPrefetch);
1184             size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litEnd, prefixStart, vBase, dictEnd);
1185 #if defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION) && defined(FUZZING_ASSERT_VALID_SEQUENCE)
1186             assert(!ZSTD_isError(oneSeqSize));
1187             if (frame) ZSTD_assertValidSequence(dctx, op, oend, sequence, prefixStart, vBase);
1188 #endif
1189             DEBUGLOG(6, "regenerated sequence size : %u", (U32)oneSeqSize);
1190             BIT_reloadDStream(&(seqState.DStream));
1191             op += oneSeqSize;
1192             /* gcc and clang both don't like early returns in this loop.
1193              * Instead break and check for an error at the end of the loop.
1194              */
1195             if (UNLIKELY(ZSTD_isError(oneSeqSize))) {
1196                 error = oneSeqSize;
1197                 break;
1198             }
1199             if (UNLIKELY(!--nbSeq)) break;
1200         }
1201 
1202         /* check if reached exact end */
1203         DEBUGLOG(5, "ZSTD_decompressSequences_body: after decode loop, remaining nbSeq : %i", nbSeq);
1204         if (ZSTD_isError(error)) return error;
1205         RETURN_ERROR_IF(nbSeq, corruption_detected, "");
1206         RETURN_ERROR_IF(BIT_reloadDStream(&seqState.DStream) < BIT_DStream_completed, corruption_detected, "");
1207         /* save reps for next block */
1208         { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]); }
1209     }
1210 
1211     /* last literal segment */
1212     {   size_t const lastLLSize = litEnd - litPtr;
1213         RETURN_ERROR_IF(lastLLSize > (size_t)(oend-op), dstSize_tooSmall, "");
1214         if (op != NULL) {
1215             ZSTD_memcpy(op, litPtr, lastLLSize);
1216             op += lastLLSize;
1217         }
1218     }
1219 
1220     return op-ostart;
1221 }
1222 
1223 static size_t
1224 ZSTD_decompressSequences_default(ZSTD_DCtx* dctx,
1225                                  void* dst, size_t maxDstSize,
1226                            const void* seqStart, size_t seqSize, int nbSeq,
1227                            const ZSTD_longOffset_e isLongOffset,
1228                            const int frame)
1229 {
1230     return ZSTD_decompressSequences_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1231 }
1232 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */
1233 
1234 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
1235 FORCE_INLINE_TEMPLATE size_t
1236 ZSTD_decompressSequencesLong_body(
1237                                ZSTD_DCtx* dctx,
1238                                void* dst, size_t maxDstSize,
1239                          const void* seqStart, size_t seqSize, int nbSeq,
1240                          const ZSTD_longOffset_e isLongOffset,
1241                          const int frame)
1242 {
1243     const BYTE* ip = (const BYTE*)seqStart;
1244     const BYTE* const iend = ip + seqSize;
1245     BYTE* const ostart = (BYTE*)dst;
1246     BYTE* const oend = ostart + maxDstSize;
1247     BYTE* op = ostart;
1248     const BYTE* litPtr = dctx->litPtr;
1249     const BYTE* const litEnd = litPtr + dctx->litSize;
1250     const BYTE* const prefixStart = (const BYTE*) (dctx->prefixStart);
1251     const BYTE* const dictStart = (const BYTE*) (dctx->virtualStart);
1252     const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
1253     (void)frame;
1254 
1255     /* Regen sequences */
1256     if (nbSeq) {
1257 #define STORED_SEQS 4
1258 #define STORED_SEQS_MASK (STORED_SEQS-1)
1259 #define ADVANCED_SEQS 4
1260         seq_t sequences[STORED_SEQS];
1261         int const seqAdvance = MIN(nbSeq, ADVANCED_SEQS);
1262         seqState_t seqState;
1263         int seqNb;
1264         dctx->fseEntropy = 1;
1265         { int i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->entropy.rep[i]; }
1266         seqState.prefixStart = prefixStart;
1267         seqState.pos = (size_t)(op-prefixStart);
1268         seqState.dictEnd = dictEnd;
1269         assert(dst != NULL);
1270         assert(iend >= ip);
1271         RETURN_ERROR_IF(
1272             ERR_isError(BIT_initDStream(&seqState.DStream, ip, iend-ip)),
1273             corruption_detected, "");
1274         ZSTD_initFseState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
1275         ZSTD_initFseState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
1276         ZSTD_initFseState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
1277 
1278         /* prepare in advance */
1279         for (seqNb=0; (BIT_reloadDStream(&seqState.DStream) <= BIT_DStream_completed) && (seqNb<seqAdvance); seqNb++) {
1280             sequences[seqNb] = ZSTD_decodeSequence(&seqState, isLongOffset, ZSTD_p_prefetch);
1281             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 */
1282         }
1283         RETURN_ERROR_IF(seqNb<seqAdvance, corruption_detected, "");
1284 
1285         /* decode and decompress */
1286         for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (seqNb<nbSeq) ; seqNb++) {
1287             seq_t const sequence = ZSTD_decodeSequence(&seqState, isLongOffset, ZSTD_p_prefetch);
1288             size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequences[(seqNb-ADVANCED_SEQS) & STORED_SEQS_MASK], &litPtr, litEnd, prefixStart, dictStart, dictEnd);
1289 #if defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION) && defined(FUZZING_ASSERT_VALID_SEQUENCE)
1290             assert(!ZSTD_isError(oneSeqSize));
1291             if (frame) ZSTD_assertValidSequence(dctx, op, oend, sequences[(seqNb-ADVANCED_SEQS) & STORED_SEQS_MASK], prefixStart, dictStart);
1292 #endif
1293             if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
1294             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 */
1295             sequences[seqNb & STORED_SEQS_MASK] = sequence;
1296             op += oneSeqSize;
1297         }
1298         RETURN_ERROR_IF(seqNb<nbSeq, corruption_detected, "");
1299 
1300         /* finish queue */
1301         seqNb -= seqAdvance;
1302         for ( ; seqNb<nbSeq ; seqNb++) {
1303             size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequences[seqNb&STORED_SEQS_MASK], &litPtr, litEnd, prefixStart, dictStart, dictEnd);
1304 #if defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION) && defined(FUZZING_ASSERT_VALID_SEQUENCE)
1305             assert(!ZSTD_isError(oneSeqSize));
1306             if (frame) ZSTD_assertValidSequence(dctx, op, oend, sequences[seqNb&STORED_SEQS_MASK], prefixStart, dictStart);
1307 #endif
1308             if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
1309             op += oneSeqSize;
1310         }
1311 
1312         /* save reps for next block */
1313         { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]); }
1314     }
1315 
1316     /* last literal segment */
1317     {   size_t const lastLLSize = litEnd - litPtr;
1318         RETURN_ERROR_IF(lastLLSize > (size_t)(oend-op), dstSize_tooSmall, "");
1319         if (op != NULL) {
1320             ZSTD_memcpy(op, litPtr, lastLLSize);
1321             op += lastLLSize;
1322         }
1323     }
1324 
1325     return op-ostart;
1326 }
1327 
1328 static size_t
1329 ZSTD_decompressSequencesLong_default(ZSTD_DCtx* dctx,
1330                                  void* dst, size_t maxDstSize,
1331                            const void* seqStart, size_t seqSize, int nbSeq,
1332                            const ZSTD_longOffset_e isLongOffset,
1333                            const int frame)
1334 {
1335     return ZSTD_decompressSequencesLong_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1336 }
1337 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */
1338 
1339 
1340 
1341 #if DYNAMIC_BMI2
1342 
1343 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
1344 static TARGET_ATTRIBUTE("bmi2") size_t
1345 DONT_VECTORIZE
1346 ZSTD_decompressSequences_bmi2(ZSTD_DCtx* dctx,
1347                                  void* dst, size_t maxDstSize,
1348                            const void* seqStart, size_t seqSize, int nbSeq,
1349                            const ZSTD_longOffset_e isLongOffset,
1350                            const int frame)
1351 {
1352     return ZSTD_decompressSequences_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1353 }
1354 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */
1355 
1356 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
1357 static TARGET_ATTRIBUTE("bmi2") size_t
1358 ZSTD_decompressSequencesLong_bmi2(ZSTD_DCtx* dctx,
1359                                  void* dst, size_t maxDstSize,
1360                            const void* seqStart, size_t seqSize, int nbSeq,
1361                            const ZSTD_longOffset_e isLongOffset,
1362                            const int frame)
1363 {
1364     return ZSTD_decompressSequencesLong_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1365 }
1366 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */
1367 
1368 #endif /* DYNAMIC_BMI2 */
1369 
1370 typedef size_t (*ZSTD_decompressSequences_t)(
1371                             ZSTD_DCtx* dctx,
1372                             void* dst, size_t maxDstSize,
1373                             const void* seqStart, size_t seqSize, int nbSeq,
1374                             const ZSTD_longOffset_e isLongOffset,
1375                             const int frame);
1376 
1377 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
1378 static size_t
1379 ZSTD_decompressSequences(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize,
1380                    const void* seqStart, size_t seqSize, int nbSeq,
1381                    const ZSTD_longOffset_e isLongOffset,
1382                    const int frame)
1383 {
1384     DEBUGLOG(5, "ZSTD_decompressSequences");
1385 #if DYNAMIC_BMI2
1386     if (dctx->bmi2) {
1387         return ZSTD_decompressSequences_bmi2(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1388     }
1389 #endif
1390   return ZSTD_decompressSequences_default(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1391 }
1392 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */
1393 
1394 
1395 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
1396 /* ZSTD_decompressSequencesLong() :
1397  * decompression function triggered when a minimum share of offsets is considered "long",
1398  * aka out of cache.
1399  * note : "long" definition seems overloaded here, sometimes meaning "wider than bitstream register", and sometimes meaning "farther than memory cache distance".
1400  * This function will try to mitigate main memory latency through the use of prefetching */
1401 static size_t
1402 ZSTD_decompressSequencesLong(ZSTD_DCtx* dctx,
1403                              void* dst, size_t maxDstSize,
1404                              const void* seqStart, size_t seqSize, int nbSeq,
1405                              const ZSTD_longOffset_e isLongOffset,
1406                              const int frame)
1407 {
1408     DEBUGLOG(5, "ZSTD_decompressSequencesLong");
1409 #if DYNAMIC_BMI2
1410     if (dctx->bmi2) {
1411         return ZSTD_decompressSequencesLong_bmi2(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1412     }
1413 #endif
1414   return ZSTD_decompressSequencesLong_default(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1415 }
1416 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */
1417 
1418 
1419 
1420 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1421     !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1422 /* ZSTD_getLongOffsetsShare() :
1423  * condition : offTable must be valid
1424  * @return : "share" of long offsets (arbitrarily defined as > (1<<23))
1425  *           compared to maximum possible of (1<<OffFSELog) */
1426 static unsigned
1427 ZSTD_getLongOffsetsShare(const ZSTD_seqSymbol* offTable)
1428 {
1429     const void* ptr = offTable;
1430     U32 const tableLog = ((const ZSTD_seqSymbol_header*)ptr)[0].tableLog;
1431     const ZSTD_seqSymbol* table = offTable + 1;
1432     U32 const max = 1 << tableLog;
1433     U32 u, total = 0;
1434     DEBUGLOG(5, "ZSTD_getLongOffsetsShare: (tableLog=%u)", tableLog);
1435 
1436     assert(max <= (1 << OffFSELog));  /* max not too large */
1437     for (u=0; u<max; u++) {
1438         if (table[u].nbAdditionalBits > 22) total += 1;
1439     }
1440 
1441     assert(tableLog <= OffFSELog);
1442     total <<= (OffFSELog - tableLog);  /* scale to OffFSELog */
1443 
1444     return total;
1445 }
1446 #endif
1447 
1448 size_t
1449 ZSTD_decompressBlock_internal(ZSTD_DCtx* dctx,
1450                               void* dst, size_t dstCapacity,
1451                         const void* src, size_t srcSize, const int frame)
1452 {   /* blockType == blockCompressed */
1453     const BYTE* ip = (const BYTE*)src;
1454     /* isLongOffset must be true if there are long offsets.
1455      * Offsets are long if they are larger than 2^STREAM_ACCUMULATOR_MIN.
1456      * We don't expect that to be the case in 64-bit mode.
1457      * In block mode, window size is not known, so we have to be conservative.
1458      * (note: but it could be evaluated from current-lowLimit)
1459      */
1460     ZSTD_longOffset_e const isLongOffset = (ZSTD_longOffset_e)(MEM_32bits() && (!frame || (dctx->fParams.windowSize > (1ULL << STREAM_ACCUMULATOR_MIN))));
1461     DEBUGLOG(5, "ZSTD_decompressBlock_internal (size : %u)", (U32)srcSize);
1462 
1463     RETURN_ERROR_IF(srcSize >= ZSTD_BLOCKSIZE_MAX, srcSize_wrong, "");
1464 
1465     /* Decode literals section */
1466     {   size_t const litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize);
1467         DEBUGLOG(5, "ZSTD_decodeLiteralsBlock : %u", (U32)litCSize);
1468         if (ZSTD_isError(litCSize)) return litCSize;
1469         ip += litCSize;
1470         srcSize -= litCSize;
1471     }
1472 
1473     /* Build Decoding Tables */
1474     {
1475         /* These macros control at build-time which decompressor implementation
1476          * we use. If neither is defined, we do some inspection and dispatch at
1477          * runtime.
1478          */
1479 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1480     !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1481         int usePrefetchDecoder = dctx->ddictIsCold;
1482 #endif
1483         int nbSeq;
1484         size_t const seqHSize = ZSTD_decodeSeqHeaders(dctx, &nbSeq, ip, srcSize);
1485         if (ZSTD_isError(seqHSize)) return seqHSize;
1486         ip += seqHSize;
1487         srcSize -= seqHSize;
1488 
1489         RETURN_ERROR_IF(dst == NULL && nbSeq > 0, dstSize_tooSmall, "NULL not handled");
1490 
1491 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1492     !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1493         if ( !usePrefetchDecoder
1494           && (!frame || (dctx->fParams.windowSize > (1<<24)))
1495           && (nbSeq>ADVANCED_SEQS) ) {  /* could probably use a larger nbSeq limit */
1496             U32 const shareLongOffsets = ZSTD_getLongOffsetsShare(dctx->OFTptr);
1497             U32 const minShare = MEM_64bits() ? 7 : 20; /* heuristic values, correspond to 2.73% and 7.81% */
1498             usePrefetchDecoder = (shareLongOffsets >= minShare);
1499         }
1500 #endif
1501 
1502         dctx->ddictIsCold = 0;
1503 
1504 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1505     !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1506         if (usePrefetchDecoder)
1507 #endif
1508 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
1509             return ZSTD_decompressSequencesLong(dctx, dst, dstCapacity, ip, srcSize, nbSeq, isLongOffset, frame);
1510 #endif
1511 
1512 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
1513         /* else */
1514         return ZSTD_decompressSequences(dctx, dst, dstCapacity, ip, srcSize, nbSeq, isLongOffset, frame);
1515 #endif
1516     }
1517 }
1518 
1519 
1520 void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst, size_t dstSize)
1521 {
1522     if (dst != dctx->previousDstEnd && dstSize > 0) {   /* not contiguous */
1523         dctx->dictEnd = dctx->previousDstEnd;
1524         dctx->virtualStart = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->prefixStart));
1525         dctx->prefixStart = dst;
1526         dctx->previousDstEnd = dst;
1527     }
1528 }
1529 
1530 
1531 size_t ZSTD_decompressBlock(ZSTD_DCtx* dctx,
1532                             void* dst, size_t dstCapacity,
1533                       const void* src, size_t srcSize)
1534 {
1535     size_t dSize;
1536     ZSTD_checkContinuity(dctx, dst, dstCapacity);
1537     dSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize, /* frame */ 0);
1538     dctx->previousDstEnd = (char*)dst + dSize;
1539     return dSize;
1540 }
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!