1 /**

     1 /*

     5  * This source code is licensed under the BSD-style license found in the

     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. An additional grant

     6  * LICENSE file in the root directory of this source tree) and the GPLv2 (found

     7  * of patent rights can be found in the PATENTS file in the same directory.

     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.

    16  * Select how default decompression function ZSTD_decompress() will allocate memory,

    17  * Select how default decompression function ZSTD_decompress() allocates its context,

    17  * in memory stack (0), or in memory heap (1, requires malloc())

    18  * on stack (0), or into heap (1, default; requires malloc()).

    19  * Note that functions with explicit context such as ZSTD_decompressDCtx() are unaffected.

    25 *  if set to 1, ZSTD_decompress() can decode older formats (v0.1+)

    27 *  if set to 1+, ZSTD_decompress() can decode older formats (v0.1+)

    32 *  MAXWINDOWSIZE_DEFAULT :

    34  *  MAXWINDOWSIZE_DEFAULT :

    33 *  maximum window size accepted by DStream, by default.

    35  *  maximum window size accepted by DStream __by default__.

    34 *  Frames requiring more memory will be rejected.

    36  *  Frames requiring more memory will be rejected.

    35 */

    37  *  It's possible to set a different limit using ZSTD_DCtx_setMaxWindowSize().

    38  */

    37 #  define ZSTD_MAXWINDOWSIZE_DEFAULT ((1 << ZSTD_WINDOWLOG_MAX) + 1)   /* defined within zstd.h */

    40 #  define ZSTD_MAXWINDOWSIZE_DEFAULT (((U32)1 << ZSTD_WINDOWLOG_DEFAULTMAX) + 1)

    69 *  Macros

    62 *  Errors

    92     const FSE_DTable* LLTptr;

   112     const ZSTD_seqSymbol* LLTptr;

    93     const FSE_DTable* MLTptr;

   113     const ZSTD_seqSymbol* MLTptr;

    94     const FSE_DTable* OFTptr;

   114     const ZSTD_seqSymbol* OFTptr;

    96     FSE_DTable LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];

   116     ZSTD_entropyDTables_t entropy;

    97     FSE_DTable OFTable[FSE_DTABLE_SIZE_U32(OffFSELog)];

   117     const void* previousDstEnd;   /* detect continuity */

    98     FSE_DTable MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];

   118     const void* base;             /* start of current segment */

    99     HUF_DTable hufTable[HUF_DTABLE_SIZE(HufLog)];  /* can accommodate HUF_decompress4X */

   119     const void* vBase;            /* virtual start of previous segment if it was just before current one */

   100     const void* previousDstEnd;

   120     const void* dictEnd;          /* end of previous segment */

   101     const void* base;

   102     const void* vBase;

   103     const void* dictEnd;

   105     U32 rep[ZSTD_REP_NUM];

   122     ZSTD_frameHeader fParams;

   106     ZSTD_frameParams fParams;

   123     U64 decodedSize;

   107     blockType_e bType;   /* used in ZSTD_decompressContinue(), to transfer blockType between header decoding and block decoding stages */

   124     blockType_e bType;            /* used in ZSTD_decompressContinue(), store blockType between block header decoding and block decompression stages */

   118     BYTE litBuffer[ZSTD_BLOCKSIZE_ABSOLUTEMAX + WILDCOPY_OVERLENGTH];

   136     size_t staticSize;

   137     int bmi2;                     /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */

   138 

   139     /* streaming */

   140     ZSTD_DDict* ddictLocal;

   141     const ZSTD_DDict* ddict;

   142     ZSTD_dStreamStage streamStage;

   143     char*  inBuff;

   144     size_t inBuffSize;

   145     size_t inPos;

   146     size_t maxWindowSize;

   147     char*  outBuff;

   148     size_t outBuffSize;

   149     size_t outStart;

   150     size_t outEnd;

   151     size_t lhSize;

   152     void* legacyContext;

   153     U32 previousLegacyVersion;

   154     U32 legacyVersion;

   155     U32 hostageByte;

   156 

   157     /* workspace */

   158     BYTE litBuffer[ZSTD_BLOCKSIZE_MAX + WILDCOPY_OVERLENGTH];

   122 size_t ZSTD_sizeof_DCtx (const ZSTD_DCtx* dctx) { return (dctx==NULL) ? 0 : sizeof(ZSTD_DCtx); }

   162 size_t ZSTD_sizeof_DCtx (const ZSTD_DCtx* dctx)

   163 {

   164     if (dctx==NULL) return 0;   /* support sizeof NULL */

   165     return sizeof(*dctx)

   166            + ZSTD_sizeof_DDict(dctx->ddictLocal)

   167            + dctx->inBuffSize + dctx->outBuffSize;

   168 }

   126 size_t ZSTD_decompressBegin(ZSTD_DCtx* dctx)

   172 

   127 {

   173 static size_t ZSTD_startingInputLength(ZSTD_format_e format)

   128     dctx->expected = ZSTD_frameHeaderSize_prefix;

   174 {

   129     dctx->stage = ZSTDds_getFrameHeaderSize;

   175     size_t const startingInputLength = (format==ZSTD_f_zstd1_magicless) ?

   130     dctx->previousDstEnd = NULL;

   176                     ZSTD_frameHeaderSize_prefix - ZSTD_frameIdSize :

   131     dctx->base = NULL;

   177                     ZSTD_frameHeaderSize_prefix;

   132     dctx->vBase = NULL;

   178     ZSTD_STATIC_ASSERT(ZSTD_FRAMEHEADERSIZE_PREFIX >= ZSTD_FRAMEIDSIZE);

   133     dctx->dictEnd = NULL;

   179     /* only supports formats ZSTD_f_zstd1 and ZSTD_f_zstd1_magicless */

   134     dctx->hufTable[0] = (HUF_DTable)((HufLog)*0x1000001);  /* cover both little and big endian */

   180     assert( (format == ZSTD_f_zstd1) || (format == ZSTD_f_zstd1_magicless) );

   135     dctx->litEntropy = dctx->fseEntropy = 0;

   181     return startingInputLength;

   136     dctx->dictID = 0;

   182 }

   137     MEM_STATIC_ASSERT(sizeof(dctx->rep) == sizeof(repStartValue));

   183 

   138     memcpy(dctx->rep, repStartValue, sizeof(repStartValue));  /* initial repcodes */

   184 static void ZSTD_initDCtx_internal(ZSTD_DCtx* dctx)

   139     dctx->LLTptr = dctx->LLTable;

   185 {

   140     dctx->MLTptr = dctx->MLTable;

   186     dctx->format = ZSTD_f_zstd1;  /* ZSTD_decompressBegin() invokes ZSTD_startingInputLength() with argument dctx->format */

   141     dctx->OFTptr = dctx->OFTable;

   187     dctx->staticSize  = 0;

   142     dctx->HUFptr = dctx->hufTable;

   188     dctx->maxWindowSize = ZSTD_MAXWINDOWSIZE_DEFAULT;

   143     return 0;

   189     dctx->ddict       = NULL;

   190     dctx->ddictLocal  = NULL;

   191     dctx->inBuff      = NULL;

   192     dctx->inBuffSize  = 0;

   193     dctx->outBuffSize = 0;

   194     dctx->streamStage = zdss_init;

   195     dctx->bmi2 = ZSTD_cpuid_bmi2(ZSTD_cpuid());

   196 }

   197 

   198 ZSTD_DCtx* ZSTD_initStaticDCtx(void *workspace, size_t workspaceSize)

   199 {

   200     ZSTD_DCtx* const dctx = (ZSTD_DCtx*) workspace;

   201 

   202     if ((size_t)workspace & 7) return NULL;  /* 8-aligned */

   203     if (workspaceSize < sizeof(ZSTD_DCtx)) return NULL;  /* minimum size */

   204 

   205     ZSTD_initDCtx_internal(dctx);

   206     dctx->staticSize = workspaceSize;

   207     dctx->inBuff = (char*)(dctx+1);

   208     return dctx;

   148     ZSTD_DCtx* dctx;

   213     if (!customMem.customAlloc ^ !customMem.customFree) return NULL;

   149 

   214 

   150     if (!customMem.customAlloc && !customMem.customFree) customMem = defaultCustomMem;

   215     {   ZSTD_DCtx* const dctx = (ZSTD_DCtx*)ZSTD_malloc(sizeof(*dctx), customMem);

   151     if (!customMem.customAlloc || !customMem.customFree) return NULL;

   216         if (!dctx) return NULL;

   152 

   217         dctx->customMem = customMem;

   153     dctx = (ZSTD_DCtx*)ZSTD_malloc(sizeof(ZSTD_DCtx), customMem);

   218         dctx->legacyContext = NULL;

   154     if (!dctx) return NULL;

   219         dctx->previousLegacyVersion = 0;

   155     memcpy(&dctx->customMem, &customMem, sizeof(customMem));

   220         ZSTD_initDCtx_internal(dctx);

   156     ZSTD_decompressBegin(dctx);

   221         return dctx;

   157     return dctx;

   222     }

   162     return ZSTD_createDCtx_advanced(defaultCustomMem);

   227     DEBUGLOG(3, "ZSTD_createDCtx");

   228     return ZSTD_createDCtx_advanced(ZSTD_defaultCMem);

   168     ZSTD_free(dctx, dctx->customMem);

   234     if (dctx->staticSize) return ERROR(memory_allocation);   /* not compatible with static DCtx */

   169     return 0;   /* reserved as a potential error code in the future */

   235     {   ZSTD_customMem const cMem = dctx->customMem;

   170 }

   236         ZSTD_freeDDict(dctx->ddictLocal);

   171 

   237         dctx->ddictLocal = NULL;

   238         ZSTD_free(dctx->inBuff, cMem);

   239         dctx->inBuff = NULL;

   240 #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT >= 1)

   241         if (dctx->legacyContext)

   242             ZSTD_freeLegacyStreamContext(dctx->legacyContext, dctx->previousLegacyVersion);

   243 #endif

   244         ZSTD_free(dctx, cMem);

   245         return 0;

   246     }

   247 }

   248 

   249 /* no longer useful */

   174     size_t const workSpaceSize = (ZSTD_BLOCKSIZE_ABSOLUTEMAX+WILDCOPY_OVERLENGTH) + ZSTD_frameHeaderSize_max;

   252     size_t const toCopy = (size_t)((char*)(&dstDCtx->inBuff) - (char*)dstDCtx);

   175     memcpy(dstDCtx, srcDCtx, sizeof(ZSTD_DCtx) - workSpaceSize);  /* no need to copy workspace */

   253     memcpy(dstDCtx, srcDCtx, toCopy);  /* no need to copy workspace */

   176 }

   177 

   178 static void ZSTD_refDCtx(ZSTD_DCtx* dstDCtx, const ZSTD_DCtx* srcDCtx)

   179 {

   180     ZSTD_decompressBegin(dstDCtx);  /* init */

   181     if (srcDCtx) {   /* support refDCtx on NULL */

   182         dstDCtx->dictEnd = srcDCtx->dictEnd;

   183         dstDCtx->vBase = srcDCtx->vBase;

   184         dstDCtx->base = srcDCtx->base;

   185         dstDCtx->previousDstEnd = srcDCtx->previousDstEnd;

   186         dstDCtx->dictID = srcDCtx->dictID;

   187         dstDCtx->litEntropy = srcDCtx->litEntropy;

   188         dstDCtx->fseEntropy = srcDCtx->fseEntropy;

   189         dstDCtx->LLTptr = srcDCtx->LLTable;

   190         dstDCtx->MLTptr = srcDCtx->MLTable;

   191         dstDCtx->OFTptr = srcDCtx->OFTable;

   192         dstDCtx->HUFptr = srcDCtx->hufTable;

   193         dstDCtx->rep[0] = srcDCtx->rep[0];

   194         dstDCtx->rep[1] = srcDCtx->rep[1];

   195         dstDCtx->rep[2] = srcDCtx->rep[2];

   196     }

   201 *   Decompression section

   258  *   Frame header decoding

   202 ***************************************************************/

   259  ***************************************************************/

   211     if (size < 4) return 0;

   268     if (size < ZSTD_frameIdSize) return 0;

   222 

   279 /** ZSTD_frameHeaderSize_internal() :

   223 /** ZSTD_frameHeaderSize() :

   280  *  srcSize must be large enough to reach header size fields.

   224 *   srcSize must be >= ZSTD_frameHeaderSize_prefix.

   281  *  note : only works for formats ZSTD_f_zstd1 and ZSTD_f_zstd1_magicless.

   225 *   @return : size of the Frame Header */

   282  * @return : size of the Frame Header

   226 static size_t ZSTD_frameHeaderSize(const void* src, size_t srcSize)

   283  *           or an error code, which can be tested with ZSTD_isError() */

   227 {

   284 static size_t ZSTD_frameHeaderSize_internal(const void* src, size_t srcSize, ZSTD_format_e format)

   228     if (srcSize < ZSTD_frameHeaderSize_prefix) return ERROR(srcSize_wrong);

   285 {

   229     {   BYTE const fhd = ((const BYTE*)src)[4];

   286     size_t const minInputSize = ZSTD_startingInputLength(format);

   287     if (srcSize < minInputSize) return ERROR(srcSize_wrong);

   288 

   289     {   BYTE const fhd = ((const BYTE*)src)[minInputSize-1];

   233         return ZSTD_frameHeaderSize_prefix + !singleSegment + ZSTD_did_fieldSize[dictID] + ZSTD_fcs_fieldSize[fcsId]

   293         return minInputSize + !singleSegment

   234                 + (singleSegment && !fcsId);

   294              + ZSTD_did_fieldSize[dictID] + ZSTD_fcs_fieldSize[fcsId]

   235     }

   295              + (singleSegment && !fcsId);

   236 }

   296     }

   237 

   297 }

   238 

   298 

   239 /** ZSTD_getFrameParams() :

   299 /** ZSTD_frameHeaderSize() :

   240 *   decode Frame Header, or require larger `srcSize`.

   300  *  srcSize must be >= ZSTD_frameHeaderSize_prefix.

   241 *   @return : 0, `fparamsPtr` is correctly filled,

   301  * @return : size of the Frame Header */

   242 *            >0, `srcSize` is too small, result is expected `srcSize`,

   302 size_t ZSTD_frameHeaderSize(const void* src, size_t srcSize)

   243 *             or an error code, which can be tested using ZSTD_isError() */

   303 {

   244 size_t ZSTD_getFrameParams(ZSTD_frameParams* fparamsPtr, const void* src, size_t srcSize)

   304     return ZSTD_frameHeaderSize_internal(src, srcSize, ZSTD_f_zstd1);

   305 }

   306 

   307 

   308 /** ZSTD_getFrameHeader_internal() :

   309  *  decode Frame Header, or require larger `srcSize`.

   310  *  note : only works for formats ZSTD_f_zstd1 and ZSTD_f_zstd1_magicless

   311  * @return : 0, `zfhPtr` is correctly filled,

   312  *          >0, `srcSize` is too small, value is wanted `srcSize` amount,

   313  *           or an error code, which can be tested using ZSTD_isError() */

   314 static size_t ZSTD_getFrameHeader_internal(ZSTD_frameHeader* zfhPtr, const void* src, size_t srcSize, ZSTD_format_e format)

   247 

   317     size_t const minInputSize = ZSTD_startingInputLength(format);

   248     if (srcSize < ZSTD_frameHeaderSize_prefix) return ZSTD_frameHeaderSize_prefix;

   318 

   249     if (MEM_readLE32(src) != ZSTD_MAGICNUMBER) {

   319     if (srcSize < minInputSize) return minInputSize;

   320 

   321     if ( (format != ZSTD_f_zstd1_magicless)

   322       && (MEM_readLE32(src) != ZSTD_MAGICNUMBER) ) {

   251             if (srcSize < ZSTD_skippableHeaderSize) return ZSTD_skippableHeaderSize; /* magic number + skippable frame length */

   324             /* skippable frame */

   252             memset(fparamsPtr, 0, sizeof(*fparamsPtr));

   325             if (srcSize < ZSTD_skippableHeaderSize)

   253             fparamsPtr->frameContentSize = MEM_readLE32((const char *)src + 4);

   326                 return ZSTD_skippableHeaderSize; /* magic number + frame length */

   254             fparamsPtr->windowSize = 0; /* windowSize==0 means a frame is skippable */

   327             memset(zfhPtr, 0, sizeof(*zfhPtr));

   328             zfhPtr->frameContentSize = MEM_readLE32((const char *)src + ZSTD_frameIdSize);

   329             zfhPtr->frameType = ZSTD_skippableFrame;

   261     { size_t const fhsize = ZSTD_frameHeaderSize(src, srcSize);

   336     {   size_t const fhsize = ZSTD_frameHeaderSize_internal(src, srcSize, format);

   262       if (srcSize < fhsize) return fhsize; }

   337         if (srcSize < fhsize) return fhsize;

   263 

   338         zfhPtr->headerSize = (U32)fhsize;

   264     {   BYTE const fhdByte = ip[4];

   339     }

   265         size_t pos = 5;

   340 

   341     {   BYTE const fhdByte = ip[minInputSize-1];

   342         size_t pos = minInputSize;

   270         U32 const windowSizeMax = 1U << ZSTD_WINDOWLOG_MAX;

   347         U64 windowSize = 0;

   271         U32 windowSize = 0;

   273         U64 frameContentSize = 0;

   349         U64 frameContentSize = ZSTD_CONTENTSIZE_UNKNOWN;

   274         if ((fhdByte & 0x08) != 0) return ERROR(frameParameter_unsupported);   /* reserved bits, which must be zero */

   350         if ((fhdByte & 0x08) != 0)

   351             return ERROR(frameParameter_unsupported); /* reserved bits, must be zero */

   352 

   278             if (windowLog > ZSTD_WINDOWLOG_MAX) return ERROR(frameParameter_windowTooLarge);  /* avoids issue with 1 << windowLog */

   356             if (windowLog > ZSTD_WINDOWLOG_MAX)

   279             windowSize = (1U << windowLog);

   357                 return ERROR(frameParameter_windowTooLarge);

   358             windowSize = (1ULL << windowLog);

   285             default:   /* impossible */

   363             default: assert(0);  /* impossible */

   293             default:   /* impossible */

   371             default: assert(0);  /* impossible */

   299         if (!windowSize) windowSize = (U32)frameContentSize;

   377         if (singleSegment) windowSize = frameContentSize;

   300         if (windowSize > windowSizeMax) return ERROR(frameParameter_windowTooLarge);

   378 

   301         fparamsPtr->frameContentSize = frameContentSize;

   379         zfhPtr->frameType = ZSTD_frame;

   302         fparamsPtr->windowSize = windowSize;

   380         zfhPtr->frameContentSize = frameContentSize;

   303         fparamsPtr->dictID = dictID;

   381         zfhPtr->windowSize = windowSize;

   304         fparamsPtr->checksumFlag = checksumFlag;

   382         zfhPtr->blockSizeMax = (unsigned) MIN(windowSize, ZSTD_BLOCKSIZE_MAX);

   383         zfhPtr->dictID = dictID;

   384         zfhPtr->checksumFlag = checksumFlag;

   314                    - decompressed size is not present within frame header

   477                    - frame content is empty

   478                    - decompressed size field is not present in frame header

   319 #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT==1)

   483     unsigned long long const ret = ZSTD_getFrameContentSize(src, srcSize);

   320     if (ZSTD_isLegacy(src, srcSize)) return ZSTD_getDecompressedSize_legacy(src, srcSize);

   484     ZSTD_STATIC_ASSERT(ZSTD_CONTENTSIZE_ERROR < ZSTD_CONTENTSIZE_UNKNOWN);

   321 #endif

   485     return (ret >= ZSTD_CONTENTSIZE_ERROR) ? 0 : ret;

   322     {   ZSTD_frameParams fparams;

   323         size_t const frResult = ZSTD_getFrameParams(&fparams, src, srcSize);

   324         if (frResult!=0) return 0;

   325         return fparams.frameContentSize;

   326     }

   335     size_t const result = ZSTD_getFrameParams(&(dctx->fParams), src, headerSize);

   494     size_t const result = ZSTD_getFrameHeader_internal(&(dctx->fParams), src, headerSize, dctx->format);

   336     if (ZSTD_isError(result)) return result;  /* invalid header */

   495     if (ZSTD_isError(result)) return result;    /* invalid header */

   337     if (result>0) return ERROR(srcSize_wrong);   /* headerSize too small */

   496     if (result>0) return ERROR(srcSize_wrong);  /* headerSize too small */

   338     if (dctx->fParams.dictID && (dctx->dictID != dctx->fParams.dictID)) return ERROR(dictionary_wrong);

   497     if (dctx->fParams.dictID && (dctx->dictID != dctx->fParams.dictID))

   498         return ERROR(dictionary_wrong);

   344 typedef struct

   504 /*-*************************************************************

   345 {

   505  *   Block decoding

   346     blockType_e blockType;

   506  ***************************************************************/

   347     U32 lastBlock;

   348     U32 origSize;

   349 } blockProperties_t;

   353 size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)

   510 size_t ZSTD_getcBlockSize(const void* src, size_t srcSize,

   511                           blockProperties_t* bpPtr)

   368 static size_t ZSTD_copyRawBlock(void* dst, size_t dstCapacity, const void* src, size_t srcSize)

   526 static size_t ZSTD_copyRawBlock(void* dst, size_t dstCapacity,

   527                           const void* src, size_t srcSize)

   376 static size_t ZSTD_setRleBlock(void* dst, size_t dstCapacity, const void* src, size_t srcSize, size_t regenSize)

   535 static size_t ZSTD_setRleBlock(void* dst, size_t dstCapacity,

   536                          const void* src, size_t srcSize,

   537                                size_t regenSize)

   385     @return : nb of bytes read from src (< srcSize ) */

   546  * @return : nb of bytes read from src (< srcSize )

   547  *  note : symbol not declared but exposed for fullbench */

   427                 if (litSize > ZSTD_BLOCKSIZE_ABSOLUTEMAX) return ERROR(corruption_detected);

   589                 if (litSize > ZSTD_BLOCKSIZE_MAX) return ERROR(corruption_detected);

   432                                         HUF_decompress1X_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->HUFptr) :

   594                                         HUF_decompress1X_usingDTable_bmi2(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->HUFptr, dctx->bmi2) :

   433                                         HUF_decompress4X_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->HUFptr) ) :

   595                                         HUF_decompress4X_usingDTable_bmi2(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->HUFptr, dctx->bmi2) ) :

   435                                         HUF_decompress1X2_DCtx(dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize) :

   597                                         HUF_decompress1X2_DCtx_wksp_bmi2(dctx->entropy.hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize,

   436                                         HUF_decompress4X_hufOnly (dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize)) ))

   598                                                                          dctx->entropy.workspace, sizeof(dctx->entropy.workspace), dctx->bmi2) :

   599                                         HUF_decompress4X_hufOnly_wksp_bmi2(dctx->entropy.hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize,

   600                                                                            dctx->entropy.workspace, sizeof(dctx->entropy.workspace), dctx->bmi2))))

   442                 if (litEncType==set_compressed) dctx->HUFptr = dctx->hufTable;

   606                 if (litEncType==set_compressed) dctx->HUFptr = dctx->entropy.hufTable;

   499                 if (litSize > ZSTD_BLOCKSIZE_ABSOLUTEMAX) return ERROR(corruption_detected);

   663                 if (litSize > ZSTD_BLOCKSIZE_MAX) return ERROR(corruption_detected);

   511 

   675 /* Default FSE distribution tables.

   512 typedef union {

   676  * These are pre-calculated FSE decoding tables using default distributions as defined in specification :

   513     FSE_decode_t realData;

   677  * https://github.com/facebook/zstd/blob/master/doc/zstd_compression_format.md#default-distributions

   514     U32 alignedBy4;

   678  * They were generated programmatically with following method :

   515 } FSE_decode_t4;

   679  * - start from default distributions, present in /lib/common/zstd_internal.h

   516 

   680  * - generate tables normally, using ZSTD_buildFSETable()

   517 static const FSE_decode_t4 LL_defaultDTable[(1<<LL_DEFAULTNORMLOG)+1] = {

   681  * - printout the content of tables

   518     { { LL_DEFAULTNORMLOG, 1, 1 } }, /* header : tableLog, fastMode, fastMode */

   682  * - pretify output, report below, test with fuzzer to ensure it's correct */

   519     { {  0,  0,  4 } },              /* 0 : base, symbol, bits */

   683 

   520     { { 16,  0,  4 } },

   684 /* Default FSE distribution table for Literal Lengths */

   521     { { 32,  1,  5 } },

   685 static const ZSTD_seqSymbol LL_defaultDTable[(1<<LL_DEFAULTNORMLOG)+1] = {

   522     { {  0,  3,  5 } },

   686      {  1,  1,  1, LL_DEFAULTNORMLOG},  /* header : fastMode, tableLog */

   523     { {  0,  4,  5 } },

   687      /* nextState, nbAddBits, nbBits, baseVal */

   524     { {  0,  6,  5 } },

   688      {  0,  0,  4,    0},  { 16,  0,  4,    0},

   525     { {  0,  7,  5 } },

   689      { 32,  0,  5,    1},  {  0,  0,  5,    3},

   526     { {  0,  9,  5 } },

   690      {  0,  0,  5,    4},  {  0,  0,  5,    6},

   527     { {  0, 10,  5 } },

   691      {  0,  0,  5,    7},  {  0,  0,  5,    9},

   528     { {  0, 12,  5 } },

   692      {  0,  0,  5,   10},  {  0,  0,  5,   12},

   529     { {  0, 14,  6 } },

   693      {  0,  0,  6,   14},  {  0,  1,  5,   16},

   530     { {  0, 16,  5 } },

   694      {  0,  1,  5,   20},  {  0,  1,  5,   22},

   531     { {  0, 18,  5 } },

   695      {  0,  2,  5,   28},  {  0,  3,  5,   32},

   532     { {  0, 19,  5 } },

   696      {  0,  4,  5,   48},  { 32,  6,  5,   64},

   533     { {  0, 21,  5 } },

   697      {  0,  7,  5,  128},  {  0,  8,  6,  256},

   534     { {  0, 22,  5 } },

   698      {  0, 10,  6, 1024},  {  0, 12,  6, 4096},

   535     { {  0, 24,  5 } },

   699      { 32,  0,  4,    0},  {  0,  0,  4,    1},

   536     { { 32, 25,  5 } },

   700      {  0,  0,  5,    2},  { 32,  0,  5,    4},

   537     { {  0, 26,  5 } },

   701      {  0,  0,  5,    5},  { 32,  0,  5,    7},

   538     { {  0, 27,  6 } },

   702      {  0,  0,  5,    8},  { 32,  0,  5,   10},

   539     { {  0, 29,  6 } },

   703      {  0,  0,  5,   11},  {  0,  0,  6,   13},

   540     { {  0, 31,  6 } },

   704      { 32,  1,  5,   16},  {  0,  1,  5,   18},

   541     { { 32,  0,  4 } },

   705      { 32,  1,  5,   22},  {  0,  2,  5,   24},

   542     { {  0,  1,  4 } },

   706      { 32,  3,  5,   32},  {  0,  3,  5,   40},

   543     { {  0,  2,  5 } },

   707      {  0,  6,  4,   64},  { 16,  6,  4,   64},

   544     { { 32,  4,  5 } },

   708      { 32,  7,  5,  128},  {  0,  9,  6,  512},

   545     { {  0,  5,  5 } },

   709      {  0, 11,  6, 2048},  { 48,  0,  4,    0},

   546     { { 32,  7,  5 } },

   710      { 16,  0,  4,    1},  { 32,  0,  5,    2},

   547     { {  0,  8,  5 } },

   711      { 32,  0,  5,    3},  { 32,  0,  5,    5},

   548     { { 32, 10,  5 } },

   712      { 32,  0,  5,    6},  { 32,  0,  5,    8},

   549     { {  0, 11,  5 } },

   713      { 32,  0,  5,    9},  { 32,  0,  5,   11},

   550     { {  0, 13,  6 } },

   714      { 32,  0,  5,   12},  {  0,  0,  6,   15},

   551     { { 32, 16,  5 } },

   715      { 32,  1,  5,   18},  { 32,  1,  5,   20},

   552     { {  0, 17,  5 } },

   716      { 32,  2,  5,   24},  { 32,  2,  5,   28},

   553     { { 32, 19,  5 } },

   717      { 32,  3,  5,   40},  { 32,  4,  5,   48},

   554     { {  0, 20,  5 } },

   718      {  0, 16,  6,65536},  {  0, 15,  6,32768},

   555     { { 32, 22,  5 } },

   719      {  0, 14,  6,16384},  {  0, 13,  6, 8192},

   556     { {  0, 23,  5 } },

   557     { {  0, 25,  4 } },

   558     { { 16, 25,  4 } },

   559     { { 32, 26,  5 } },

   560     { {  0, 28,  6 } },

   561     { {  0, 30,  6 } },

   562     { { 48,  0,  4 } },

   563     { { 16,  1,  4 } },

   564     { { 32,  2,  5 } },

   565     { { 32,  3,  5 } },

   566     { { 32,  5,  5 } },

   567     { { 32,  6,  5 } },

   568     { { 32,  8,  5 } },

   569     { { 32,  9,  5 } },

   570     { { 32, 11,  5 } },

   571     { { 32, 12,  5 } },

   572     { {  0, 15,  6 } },

   573     { { 32, 17,  5 } },

   574     { { 32, 18,  5 } },

   575     { { 32, 20,  5 } },

   576     { { 32, 21,  5 } },

   577     { { 32, 23,  5 } },

   578     { { 32, 24,  5 } },

   579     { {  0, 35,  6 } },

   580     { {  0, 34,  6 } },

   581     { {  0, 33,  6 } },

   582     { {  0, 32,  6 } },

   585 static const FSE_decode_t4 ML_defaultDTable[(1<<ML_DEFAULTNORMLOG)+1] = {

   722 /* Default FSE distribution table for Offset Codes */

   586     { { ML_DEFAULTNORMLOG, 1, 1 } }, /* header : tableLog, fastMode, fastMode */

   723 static const ZSTD_seqSymbol OF_defaultDTable[(1<<OF_DEFAULTNORMLOG)+1] = {

   587     { {  0,  0,  6 } },              /* 0 : base, symbol, bits */

   724     {  1,  1,  1, OF_DEFAULTNORMLOG},  /* header : fastMode, tableLog */

   588     { {  0,  1,  4 } },

   725     /* nextState, nbAddBits, nbBits, baseVal */

   589     { { 32,  2,  5 } },

   726     {  0,  0,  5,    0},     {  0,  6,  4,   61},

   590     { {  0,  3,  5 } },

   727     {  0,  9,  5,  509},     {  0, 15,  5,32765},

   591     { {  0,  5,  5 } },

   728     {  0, 21,  5,2097149},   {  0,  3,  5,    5},

   592     { {  0,  6,  5 } },

   729     {  0,  7,  4,  125},     {  0, 12,  5, 4093},

   593     { {  0,  8,  5 } },

   730     {  0, 18,  5,262141},    {  0, 23,  5,8388605},

   594     { {  0, 10,  6 } },

   731     {  0,  5,  5,   29},     {  0,  8,  4,  253},

   595     { {  0, 13,  6 } },

   732     {  0, 14,  5,16381},     {  0, 20,  5,1048573},

   596     { {  0, 16,  6 } },

   733     {  0,  2,  5,    1},     { 16,  7,  4,  125},

   597     { {  0, 19,  6 } },

   734     {  0, 11,  5, 2045},     {  0, 17,  5,131069},

   598     { {  0, 22,  6 } },

   735     {  0, 22,  5,4194301},   {  0,  4,  5,   13},

   599     { {  0, 25,  6 } },

   736     { 16,  8,  4,  253},     {  0, 13,  5, 8189},

   600     { {  0, 28,  6 } },

   737     {  0, 19,  5,524285},    {  0,  1,  5,    1},

   601     { {  0, 31,  6 } },

   738     { 16,  6,  4,   61},     {  0, 10,  5, 1021},

   602     { {  0, 33,  6 } },

   739     {  0, 16,  5,65533},     {  0, 28,  5,268435453},

   603     { {  0, 35,  6 } },

   740     {  0, 27,  5,134217725}, {  0, 26,  5,67108861},

   604     { {  0, 37,  6 } },

   741     {  0, 25,  5,33554429},  {  0, 24,  5,16777213},

   605     { {  0, 39,  6 } },

   742 };   /* OF_defaultDTable */

   606     { {  0, 41,  6 } },

   743 

   607     { {  0, 43,  6 } },

   744 

   608     { {  0, 45,  6 } },

   745 /* Default FSE distribution table for Match Lengths */

   609     { { 16,  1,  4 } },

   746 static const ZSTD_seqSymbol ML_defaultDTable[(1<<ML_DEFAULTNORMLOG)+1] = {

   610     { {  0,  2,  4 } },

   747     {  1,  1,  1, ML_DEFAULTNORMLOG},  /* header : fastMode, tableLog */

   611     { { 32,  3,  5 } },

   748     /* nextState, nbAddBits, nbBits, baseVal */

   612     { {  0,  4,  5 } },

   749     {  0,  0,  6,    3},  {  0,  0,  4,    4},

   613     { { 32,  6,  5 } },

   750     { 32,  0,  5,    5},  {  0,  0,  5,    6},

   614     { {  0,  7,  5 } },

   751     {  0,  0,  5,    8},  {  0,  0,  5,    9},

   615     { {  0,  9,  6 } },

   752     {  0,  0,  5,   11},  {  0,  0,  6,   13},

   616     { {  0, 12,  6 } },

   753     {  0,  0,  6,   16},  {  0,  0,  6,   19},

   617     { {  0, 15,  6 } },

   754     {  0,  0,  6,   22},  {  0,  0,  6,   25},

   618     { {  0, 18,  6 } },

   755     {  0,  0,  6,   28},  {  0,  0,  6,   31},

   619     { {  0, 21,  6 } },

   756     {  0,  0,  6,   34},  {  0,  1,  6,   37},

   620     { {  0, 24,  6 } },

   757     {  0,  1,  6,   41},  {  0,  2,  6,   47},

   621     { {  0, 27,  6 } },

   758     {  0,  3,  6,   59},  {  0,  4,  6,   83},

   622     { {  0, 30,  6 } },

   759     {  0,  7,  6,  131},  {  0,  9,  6,  515},

   623     { {  0, 32,  6 } },

   760     { 16,  0,  4,    4},  {  0,  0,  4,    5},

   624     { {  0, 34,  6 } },

   761     { 32,  0,  5,    6},  {  0,  0,  5,    7},

   625     { {  0, 36,  6 } },

   762     { 32,  0,  5,    9},  {  0,  0,  5,   10},

   626     { {  0, 38,  6 } },

   763     {  0,  0,  6,   12},  {  0,  0,  6,   15},

   627     { {  0, 40,  6 } },

   764     {  0,  0,  6,   18},  {  0,  0,  6,   21},

   628     { {  0, 42,  6 } },

   765     {  0,  0,  6,   24},  {  0,  0,  6,   27},

   629     { {  0, 44,  6 } },

   766     {  0,  0,  6,   30},  {  0,  0,  6,   33},

   630     { { 32,  1,  4 } },

   767     {  0,  1,  6,   35},  {  0,  1,  6,   39},

   631     { { 48,  1,  4 } },

   768     {  0,  2,  6,   43},  {  0,  3,  6,   51},

   632     { { 16,  2,  4 } },

   769     {  0,  4,  6,   67},  {  0,  5,  6,   99},

   633     { { 32,  4,  5 } },

   770     {  0,  8,  6,  259},  { 32,  0,  4,    4},

   634     { { 32,  5,  5 } },

   771     { 48,  0,  4,    4},  { 16,  0,  4,    5},

   635     { { 32,  7,  5 } },

   772     { 32,  0,  5,    7},  { 32,  0,  5,    8},

   636     { { 32,  8,  5 } },

   773     { 32,  0,  5,   10},  { 32,  0,  5,   11},

   637     { {  0, 11,  6 } },

   774     {  0,  0,  6,   14},  {  0,  0,  6,   17},

   638     { {  0, 14,  6 } },

   775     {  0,  0,  6,   20},  {  0,  0,  6,   23},

   639     { {  0, 17,  6 } },

   776     {  0,  0,  6,   26},  {  0,  0,  6,   29},

   640     { {  0, 20,  6 } },

   777     {  0,  0,  6,   32},  {  0, 16,  6,65539},

   641     { {  0, 23,  6 } },

   778     {  0, 15,  6,32771},  {  0, 14,  6,16387},

   642     { {  0, 26,  6 } },

   779     {  0, 13,  6, 8195},  {  0, 12,  6, 4099},

   643     { {  0, 29,  6 } },

   780     {  0, 11,  6, 2051},  {  0, 10,  6, 1027},

   644     { {  0, 52,  6 } },

   645     { {  0, 51,  6 } },

   646     { {  0, 50,  6 } },

   647     { {  0, 49,  6 } },

   648     { {  0, 48,  6 } },

   649     { {  0, 47,  6 } },

   650     { {  0, 46,  6 } },

   653 static const FSE_decode_t4 OF_defaultDTable[(1<<OF_DEFAULTNORMLOG)+1] = {

   783 

   654     { { OF_DEFAULTNORMLOG, 1, 1 } }, /* header : tableLog, fastMode, fastMode */

   784 static void ZSTD_buildSeqTable_rle(ZSTD_seqSymbol* dt, U32 baseValue, U32 nbAddBits)

   655     { {  0,  0,  5 } },              /* 0 : base, symbol, bits */

   785 {

   656     { {  0,  6,  4 } },

   786     void* ptr = dt;

   657     { {  0,  9,  5 } },

   787     ZSTD_seqSymbol_header* const DTableH = (ZSTD_seqSymbol_header*)ptr;

   658     { {  0, 15,  5 } },

   788     ZSTD_seqSymbol* const cell = dt + 1;

   659     { {  0, 21,  5 } },

   789 

   660     { {  0,  3,  5 } },

   790     DTableH->tableLog = 0;

   661     { {  0,  7,  4 } },

   791     DTableH->fastMode = 0;

   662     { {  0, 12,  5 } },

   792 

   663     { {  0, 18,  5 } },

   793     cell->nbBits = 0;

   664     { {  0, 23,  5 } },

   794     cell->nextState = 0;

   665     { {  0,  5,  5 } },

   795     assert(nbAddBits < 255);

   666     { {  0,  8,  4 } },

   796     cell->nbAdditionalBits = (BYTE)nbAddBits;

   667     { {  0, 14,  5 } },

   797     cell->baseValue = baseValue;

   668     { {  0, 20,  5 } },

   798 }

   669     { {  0,  2,  5 } },

   799 

   670     { { 16,  7,  4 } },

   800 

   671     { {  0, 11,  5 } },

   801 /* ZSTD_buildFSETable() :

   672     { {  0, 17,  5 } },

   802  * generate FSE decoding table for one symbol (ll, ml or off) */

   673     { {  0, 22,  5 } },

   803 static void

   674     { {  0,  4,  5 } },

   804 ZSTD_buildFSETable(ZSTD_seqSymbol* dt,

   675     { { 16,  8,  4 } },

   805     const short* normalizedCounter, unsigned maxSymbolValue,

   676     { {  0, 13,  5 } },

   806     const U32* baseValue, const U32* nbAdditionalBits,

   677     { {  0, 19,  5 } },

   807     unsigned tableLog)

   678     { {  0,  1,  5 } },

   808 {

   679     { { 16,  6,  4 } },

   809     ZSTD_seqSymbol* const tableDecode = dt+1;

   680     { {  0, 10,  5 } },

   810     U16 symbolNext[MaxSeq+1];

   681     { {  0, 16,  5 } },

   811 

   682     { {  0, 28,  5 } },

   812     U32 const maxSV1 = maxSymbolValue + 1;

   683     { {  0, 27,  5 } },

   813     U32 const tableSize = 1 << tableLog;

   684     { {  0, 26,  5 } },

   814     U32 highThreshold = tableSize-1;

   685     { {  0, 25,  5 } },

   815 

   686     { {  0, 24,  5 } },

   816     /* Sanity Checks */

   687 };   /* OF_defaultDTable */

   817     assert(maxSymbolValue <= MaxSeq);

   818     assert(tableLog <= MaxFSELog);

   819 

   820     /* Init, lay down lowprob symbols */

   821     {   ZSTD_seqSymbol_header DTableH;

   822         DTableH.tableLog = tableLog;

   823         DTableH.fastMode = 1;

   824         {   S16 const largeLimit= (S16)(1 << (tableLog-1));

   825             U32 s;

   826             for (s=0; s<maxSV1; s++) {

   827                 if (normalizedCounter[s]==-1) {

   828                     tableDecode[highThreshold--].baseValue = s;

   829                     symbolNext[s] = 1;

   830                 } else {

   831                     if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;

   832                     symbolNext[s] = normalizedCounter[s];

   833         }   }   }

   834         memcpy(dt, &DTableH, sizeof(DTableH));

   835     }

   836 

   837     /* Spread symbols */

   838     {   U32 const tableMask = tableSize-1;

   839         U32 const step = FSE_TABLESTEP(tableSize);

   840         U32 s, position = 0;

   841         for (s=0; s<maxSV1; s++) {

   842             int i;

   843             for (i=0; i<normalizedCounter[s]; i++) {

   844                 tableDecode[position].baseValue = s;

   845                 position = (position + step) & tableMask;

   846                 while (position > highThreshold) position = (position + step) & tableMask;   /* lowprob area */

   847         }   }

   848         assert(position == 0); /* position must reach all cells once, otherwise normalizedCounter is incorrect */

   849     }

   850 

   851     /* Build Decoding table */

   852     {   U32 u;

   853         for (u=0; u<tableSize; u++) {

   854             U32 const symbol = tableDecode[u].baseValue;

   855             U32 const nextState = symbolNext[symbol]++;

   856             tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32(nextState) );

   857             tableDecode[u].nextState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);

   858             assert(nbAdditionalBits[symbol] < 255);

   859             tableDecode[u].nbAdditionalBits = (BYTE)nbAdditionalBits[symbol];

   860             tableDecode[u].baseValue = baseValue[symbol];

   861     }   }

   862 }

   863 

   690     @return : nb bytes read from src,

   866  * @return : nb bytes read from src,

   691               or an error code if it fails, testable with ZSTD_isError()

   867  *           or an error code if it fails */

   692 */

   868 static size_t ZSTD_buildSeqTable(ZSTD_seqSymbol* DTableSpace, const ZSTD_seqSymbol** DTablePtr,

   693 static size_t ZSTD_buildSeqTable(FSE_DTable* DTableSpace, const FSE_DTable** DTablePtr,

   696                                  const FSE_decode_t4* defaultTable, U32 flagRepeatTable)

   871                                  const U32* baseValue, const U32* nbAdditionalBits,

   697 {

   872                                  const ZSTD_seqSymbol* defaultTable, U32 flagRepeatTable)

   698     const void* const tmpPtr = defaultTable;   /* bypass strict aliasing */

   873 {

   704         FSE_buildDTable_rle(DTableSpace, *(const BYTE*)src);

   879         {   U32 const symbol = *(const BYTE*)src;

   880             U32 const baseline = baseValue[symbol];

   881             U32 const nbBits = nbAdditionalBits[symbol];

   882             ZSTD_buildSeqTable_rle(DTableSpace, baseline, nbBits);

   883         }

   708         *DTablePtr = (const FSE_DTable*)tmpPtr;

   887         *DTablePtr = defaultTable;

   720             FSE_buildDTable(DTableSpace, norm, max, tableLog);

   898             ZSTD_buildFSETable(DTableSpace, norm, max, baseValue, nbAdditionalBits, tableLog);

   723     }   }

   901         }

   724 }

   902     default :   /* impossible */

   903         assert(0);

   904         return ERROR(GENERIC);

   905     }

   906 }

   907 

   908 static const U32 LL_base[MaxLL+1] = {

   909                  0,    1,    2,     3,     4,     5,     6,      7,

   910                  8,    9,   10,    11,    12,    13,    14,     15,

   911                 16,   18,   20,    22,    24,    28,    32,     40,

   912                 48,   64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,

   913                 0x2000, 0x4000, 0x8000, 0x10000 };

   914 

   915 static const U32 OF_base[MaxOff+1] = {

   916                  0,        1,       1,       5,     0xD,     0x1D,     0x3D,     0x7D,

   917                  0xFD,   0x1FD,   0x3FD,   0x7FD,   0xFFD,   0x1FFD,   0x3FFD,   0x7FFD,

   918                  0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD,

   919                  0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD, 0x1FFFFFFD, 0x3FFFFFFD, 0x7FFFFFFD };

   920 

   921 static const U32 OF_bits[MaxOff+1] = {

   922                      0,  1,  2,  3,  4,  5,  6,  7,

   923                      8,  9, 10, 11, 12, 13, 14, 15,

   924                     16, 17, 18, 19, 20, 21, 22, 23,

   925                     24, 25, 26, 27, 28, 29, 30, 31 };

   926 

   927 static const U32 ML_base[MaxML+1] = {

   928                      3,  4,  5,    6,     7,     8,     9,    10,

   929                     11, 12, 13,   14,    15,    16,    17,    18,

   930                     19, 20, 21,   22,    23,    24,    25,    26,

   931                     27, 28, 29,   30,    31,    32,    33,    34,

   932                     35, 37, 39,   41,    43,    47,    51,    59,

   933                     67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803,

   934                     0x1003, 0x2003, 0x4003, 0x8003, 0x10003 };

   935 

   759         {   size_t const llhSize = ZSTD_buildSeqTable(dctx->LLTable, &dctx->LLTptr,

   971         {   size_t const llhSize = ZSTD_buildSeqTable(dctx->entropy.LLTable, &dctx->LLTptr,

   761                                                       ip, iend-ip, LL_defaultDTable, dctx->fseEntropy);

   973                                                       ip, iend-ip,

   974                                                       LL_base, LL_bits,

   975                                                       LL_defaultDTable, dctx->fseEntropy);

   765         {   size_t const ofhSize = ZSTD_buildSeqTable(dctx->OFTable, &dctx->OFTptr,

   979 

   980         {   size_t const ofhSize = ZSTD_buildSeqTable(dctx->entropy.OFTable, &dctx->OFTptr,

   767                                                       ip, iend-ip, OF_defaultDTable, dctx->fseEntropy);

   982                                                       ip, iend-ip,

   983                                                       OF_base, OF_bits,

   984                                                       OF_defaultDTable, dctx->fseEntropy);

   771         {   size_t const mlhSize = ZSTD_buildSeqTable(dctx->MLTable, &dctx->MLTptr,

   988 

   989         {   size_t const mlhSize = ZSTD_buildSeqTable(dctx->entropy.MLTable, &dctx->MLTptr,

   773                                                       ip, iend-ip, ML_defaultDTable, dctx->fseEntropy);

   991                                                       ip, iend-ip,

   992                                                       ML_base, ML_bits,

   993                                                       ML_defaultDTable, dctx->fseEntropy);

   792     FSE_DState_t stateLL;

  1017     ZSTD_fseState stateLL;

   793     FSE_DState_t stateOffb;

  1018     ZSTD_fseState stateOffb;

   794     FSE_DState_t stateML;

  1019     ZSTD_fseState stateML;

   796     const BYTE* base;

  1021     const BYTE* prefixStart;

  1022     const BYTE* dictEnd;

   849 

  1074 HINT_INLINE

   850 

  1075 size_t ZSTD_execSequence(BYTE* op,

   851 static seq_t ZSTD_decodeSequence(seqState_t* seqState)

  1076                          BYTE* const oend, seq_t sequence,

  1077                          const BYTE** litPtr, const BYTE* const litLimit,

  1078                          const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)

  1079 {

  1080     BYTE* const oLitEnd = op + sequence.litLength;

  1081     size_t const sequenceLength = sequence.litLength + sequence.matchLength;

  1082     BYTE* const oMatchEnd = op + sequenceLength;   /* risk : address space overflow (32-bits) */

  1083     BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH;

  1084     const BYTE* const iLitEnd = *litPtr + sequence.litLength;

  1085     const BYTE* match = oLitEnd - sequence.offset;

  1086 

  1087     /* check */

  1088     if (oMatchEnd>oend) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */

  1089     if (iLitEnd > litLimit) return ERROR(corruption_detected);   /* over-read beyond lit buffer */

  1090     if (oLitEnd>oend_w) return ZSTD_execSequenceLast7(op, oend, sequence, litPtr, litLimit, base, vBase, dictEnd);

  1091 

  1092     /* copy Literals */

  1093     ZSTD_copy8(op, *litPtr);

  1094     if (sequence.litLength > 8)

  1095         ZSTD_wildcopy(op+8, (*litPtr)+8, sequence.litLength - 8);   /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */

  1096     op = oLitEnd;

  1097     *litPtr = iLitEnd;   /* update for next sequence */

  1098 

  1099     /* copy Match */

  1100     if (sequence.offset > (size_t)(oLitEnd - base)) {

  1101         /* offset beyond prefix -> go into extDict */

  1102         if (sequence.offset > (size_t)(oLitEnd - vBase))

  1103             return ERROR(corruption_detected);

  1104         match = dictEnd + (match - base);

  1105         if (match + sequence.matchLength <= dictEnd) {

  1106             memmove(oLitEnd, match, sequence.matchLength);

  1107             return sequenceLength;

  1108         }

  1109         /* span extDict & currentPrefixSegment */

  1110         {   size_t const length1 = dictEnd - match;

  1111             memmove(oLitEnd, match, length1);

  1112             op = oLitEnd + length1;

  1113             sequence.matchLength -= length1;

  1114             match = base;

  1115             if (op > oend_w || sequence.matchLength < MINMATCH) {

  1116               U32 i;

  1117               for (i = 0; i < sequence.matchLength; ++i) op[i] = match[i];

  1118               return sequenceLength;

  1119             }

  1120     }   }

  1121     /* Requirement: op <= oend_w && sequence.matchLength >= MINMATCH */

  1122 

  1123     /* match within prefix */

  1124     if (sequence.offset < 8) {

  1125         /* close range match, overlap */

  1126         static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 };   /* added */

  1127         static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 };   /* subtracted */

  1128         int const sub2 = dec64table[sequence.offset];

  1129         op[0] = match[0];

  1130         op[1] = match[1];

  1131         op[2] = match[2];

  1132         op[3] = match[3];

  1133         match += dec32table[sequence.offset];

  1134         ZSTD_copy4(op+4, match);

  1135         match -= sub2;

  1136     } else {

  1137         ZSTD_copy8(op, match);

  1138     }

  1139     op += 8; match += 8;

  1140 

  1141     if (oMatchEnd > oend-(16-MINMATCH)) {

  1142         if (op < oend_w) {

  1143             ZSTD_wildcopy(op, match, oend_w - op);

  1144             match += oend_w - op;

  1145             op = oend_w;

  1146         }

  1147         while (op < oMatchEnd) *op++ = *match++;

  1148     } else {

  1149         ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8);   /* works even if matchLength < 8 */

  1150     }

  1151     return sequenceLength;

  1152 }

  1153 

  1154 

  1155 HINT_INLINE

  1156 size_t ZSTD_execSequenceLong(BYTE* op,

  1157                              BYTE* const oend, seq_t sequence,

  1158                              const BYTE** litPtr, const BYTE* const litLimit,

  1159                              const BYTE* const prefixStart, const BYTE* const dictStart, const BYTE* const dictEnd)

  1160 {

  1161     BYTE* const oLitEnd = op + sequence.litLength;

  1162     size_t const sequenceLength = sequence.litLength + sequence.matchLength;

  1163     BYTE* const oMatchEnd = op + sequenceLength;   /* risk : address space overflow (32-bits) */

  1164     BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH;

  1165     const BYTE* const iLitEnd = *litPtr + sequence.litLength;

  1166     const BYTE* match = sequence.match;

  1167 

  1168     /* check */

  1169     if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */

  1170     if (iLitEnd > litLimit) return ERROR(corruption_detected);   /* over-read beyond lit buffer */

  1171     if (oLitEnd > oend_w) return ZSTD_execSequenceLast7(op, oend, sequence, litPtr, litLimit, prefixStart, dictStart, dictEnd);

  1172 

  1173     /* copy Literals */

  1174     ZSTD_copy8(op, *litPtr);  /* note : op <= oLitEnd <= oend_w == oend - 8 */

  1175     if (sequence.litLength > 8)

  1176         ZSTD_wildcopy(op+8, (*litPtr)+8, sequence.litLength - 8);   /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */

  1177     op = oLitEnd;

  1178     *litPtr = iLitEnd;   /* update for next sequence */

  1179 

  1180     /* copy Match */

  1181     if (sequence.offset > (size_t)(oLitEnd - prefixStart)) {

  1182         /* offset beyond prefix */

  1183         if (sequence.offset > (size_t)(oLitEnd - dictStart)) return ERROR(corruption_detected);

  1184         if (match + sequence.matchLength <= dictEnd) {

  1185             memmove(oLitEnd, match, sequence.matchLength);

  1186             return sequenceLength;

  1187         }

  1188         /* span extDict & currentPrefixSegment */

  1189         {   size_t const length1 = dictEnd - match;

  1190             memmove(oLitEnd, match, length1);

  1191             op = oLitEnd + length1;

  1192             sequence.matchLength -= length1;

  1193             match = prefixStart;

  1194             if (op > oend_w || sequence.matchLength < MINMATCH) {

  1195               U32 i;

  1196               for (i = 0; i < sequence.matchLength; ++i) op[i] = match[i];

  1197               return sequenceLength;

  1198             }

  1199     }   }

  1200     assert(op <= oend_w);

  1201     assert(sequence.matchLength >= MINMATCH);

  1202 

  1203     /* match within prefix */

  1204     if (sequence.offset < 8) {

  1205         /* close range match, overlap */

  1206         static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 };   /* added */

  1207         static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 };   /* subtracted */

  1208         int const sub2 = dec64table[sequence.offset];