1 /**

     2  * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.

     3  * All rights reserved.

     4  *

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

     6  * LICENSE file in the root directory of this source tree. An additional grant

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

     8  */

     9 

    10 

    11 /*-*************************************

    12 *  Dependencies

    13 ***************************************/

    14 #include <string.h>         /* memset */

    15 #include "mem.h"

    16 #define XXH_STATIC_LINKING_ONLY   /* XXH64_state_t */

    17 #include "xxhash.h"               /* XXH_reset, update, digest */

    18 #define FSE_STATIC_LINKING_ONLY   /* FSE_encodeSymbol */

    19 #include "fse.h"

    20 #define HUF_STATIC_LINKING_ONLY

    21 #include "huf.h"

    22 #include "zstd_internal.h"  /* includes zstd.h */

    23 

    24 

    25 /*-*************************************

    26 *  Constants

    27 ***************************************/

    28 static const U32 g_searchStrength = 8;   /* control skip over incompressible data */

    29 #define HASH_READ_SIZE 8

    30 typedef enum { ZSTDcs_created=0, ZSTDcs_init, ZSTDcs_ongoing, ZSTDcs_ending } ZSTD_compressionStage_e;

    31 

    32 

    33 /*-*************************************

    34 *  Helper functions

    35 ***************************************/

    36 size_t ZSTD_compressBound(size_t srcSize) { return FSE_compressBound(srcSize) + 12; }

    37 

    38 

    39 /*-*************************************

    40 *  Sequence storage

    41 ***************************************/

    42 static void ZSTD_resetSeqStore(seqStore_t* ssPtr)

    43 {

    44     ssPtr->lit = ssPtr->litStart;

    45     ssPtr->sequences = ssPtr->sequencesStart;

    46     ssPtr->longLengthID = 0;

    47 }

    48 

    49 

    50 /*-*************************************

    51 *  Context memory management

    52 ***************************************/

    53 struct ZSTD_CCtx_s

    54 {

    55     const BYTE* nextSrc;    /* next block here to continue on current prefix */

    56     const BYTE* base;       /* All regular indexes relative to this position */

    57     const BYTE* dictBase;   /* extDict indexes relative to this position */

    58     U32   dictLimit;        /* below that point, need extDict */

    59     U32   lowLimit;         /* below that point, no more data */

    60     U32   nextToUpdate;     /* index from which to continue dictionary update */

    61     U32   nextToUpdate3;    /* index from which to continue dictionary update */

    62     U32   hashLog3;         /* dispatch table : larger == faster, more memory */

    63     U32   loadedDictEnd;

    64     ZSTD_compressionStage_e stage;

    65     U32   rep[ZSTD_REP_NUM];

    66     U32   savedRep[ZSTD_REP_NUM];

    67     U32   dictID;

    68     ZSTD_parameters params;

    69     void* workSpace;

    70     size_t workSpaceSize;

    71     size_t blockSize;

    72     U64 frameContentSize;

    73     XXH64_state_t xxhState;

    74     ZSTD_customMem customMem;

    75 

    76     seqStore_t seqStore;    /* sequences storage ptrs */

    77     U32* hashTable;

    78     U32* hashTable3;

    79     U32* chainTable;

    80     HUF_CElt* hufTable;

    81     U32 flagStaticTables;

    82     FSE_CTable offcodeCTable  [FSE_CTABLE_SIZE_U32(OffFSELog, MaxOff)];

    83     FSE_CTable matchlengthCTable[FSE_CTABLE_SIZE_U32(MLFSELog, MaxML)];

    84     FSE_CTable litlengthCTable  [FSE_CTABLE_SIZE_U32(LLFSELog, MaxLL)];

    85 };

    86 

    87 ZSTD_CCtx* ZSTD_createCCtx(void)

    88 {

    89     return ZSTD_createCCtx_advanced(defaultCustomMem);

    90 }

    91 

    92 ZSTD_CCtx* ZSTD_createCCtx_advanced(ZSTD_customMem customMem)

    93 {

    94     ZSTD_CCtx* cctx;

    95 

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

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

    98 

    99     cctx = (ZSTD_CCtx*) ZSTD_malloc(sizeof(ZSTD_CCtx), customMem);

   100     if (!cctx) return NULL;

   101     memset(cctx, 0, sizeof(ZSTD_CCtx));

   102     memcpy(&(cctx->customMem), &customMem, sizeof(customMem));

   103     return cctx;

   104 }

   105 

   106 size_t ZSTD_freeCCtx(ZSTD_CCtx* cctx)

   107 {

   108     if (cctx==NULL) return 0;   /* support free on NULL */

   109     ZSTD_free(cctx->workSpace, cctx->customMem);

   110     ZSTD_free(cctx, cctx->customMem);

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

   112 }

   113 

   114 size_t ZSTD_sizeof_CCtx(const ZSTD_CCtx* cctx)

   115 {

   116     if (cctx==NULL) return 0;   /* support sizeof on NULL */

   117     return sizeof(*cctx) + cctx->workSpaceSize;

   118 }

   119 

   120 const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx)   /* hidden interface */

   121 {

   122     return &(ctx->seqStore);

   123 }

   124 

   125 static ZSTD_parameters ZSTD_getParamsFromCCtx(const ZSTD_CCtx* cctx)

   126 {

   127     return cctx->params;

   128 }

   129 

   130 

   131 /** ZSTD_checkParams() :

   132     ensure param values remain within authorized range.

   133     @return : 0, or an error code if one value is beyond authorized range */

   134 size_t ZSTD_checkCParams(ZSTD_compressionParameters cParams)

   135 {

   136 #   define CLAMPCHECK(val,min,max) { if ((val<min) | (val>max)) return ERROR(compressionParameter_unsupported); }

   137     CLAMPCHECK(cParams.windowLog, ZSTD_WINDOWLOG_MIN, ZSTD_WINDOWLOG_MAX);

   138     CLAMPCHECK(cParams.chainLog, ZSTD_CHAINLOG_MIN, ZSTD_CHAINLOG_MAX);

   139     CLAMPCHECK(cParams.hashLog, ZSTD_HASHLOG_MIN, ZSTD_HASHLOG_MAX);

   140     CLAMPCHECK(cParams.searchLog, ZSTD_SEARCHLOG_MIN, ZSTD_SEARCHLOG_MAX);

   141     { U32 const searchLengthMin = ((cParams.strategy == ZSTD_fast) | (cParams.strategy == ZSTD_greedy)) ? ZSTD_SEARCHLENGTH_MIN+1 : ZSTD_SEARCHLENGTH_MIN;

   142       U32 const searchLengthMax = (cParams.strategy == ZSTD_fast) ? ZSTD_SEARCHLENGTH_MAX : ZSTD_SEARCHLENGTH_MAX-1;

   143       CLAMPCHECK(cParams.searchLength, searchLengthMin, searchLengthMax); }

   144     CLAMPCHECK(cParams.targetLength, ZSTD_TARGETLENGTH_MIN, ZSTD_TARGETLENGTH_MAX);

   145     if ((U32)(cParams.strategy) > (U32)ZSTD_btopt2) return ERROR(compressionParameter_unsupported);

   146     return 0;

   147 }

   148 

   149 

   150 /** ZSTD_adjustCParams() :

   151     optimize `cPar` for a given input (`srcSize` and `dictSize`).

   152     mostly downsizing to reduce memory consumption and initialization.

   153     Both `srcSize` and `dictSize` are optional (use 0 if unknown),

   154     but if both are 0, no optimization can be done.

   155     Note : cPar is considered validated at this stage. Use ZSTD_checkParams() to ensure that. */

   156 ZSTD_compressionParameters ZSTD_adjustCParams(ZSTD_compressionParameters cPar, unsigned long long srcSize, size_t dictSize)

   157 {

   158     if (srcSize+dictSize == 0) return cPar;   /* no size information available : no adjustment */

   159 

   160     /* resize params, to use less memory when necessary */

   161     {   U32 const minSrcSize = (srcSize==0) ? 500 : 0;

   162         U64 const rSize = srcSize + dictSize + minSrcSize;

   163         if (rSize < ((U64)1<<ZSTD_WINDOWLOG_MAX)) {

   164             U32 const srcLog = MAX(ZSTD_HASHLOG_MIN, ZSTD_highbit32((U32)(rSize)-1) + 1);

   165             if (cPar.windowLog > srcLog) cPar.windowLog = srcLog;

   166     }   }

   167     if (cPar.hashLog > cPar.windowLog) cPar.hashLog = cPar.windowLog;

   168     {   U32 const btPlus = (cPar.strategy == ZSTD_btlazy2) | (cPar.strategy == ZSTD_btopt) | (cPar.strategy == ZSTD_btopt2);

   169         U32 const maxChainLog = cPar.windowLog+btPlus;

   170         if (cPar.chainLog > maxChainLog) cPar.chainLog = maxChainLog; }   /* <= ZSTD_CHAINLOG_MAX */

   171 

   172     if (cPar.windowLog < ZSTD_WINDOWLOG_ABSOLUTEMIN) cPar.windowLog = ZSTD_WINDOWLOG_ABSOLUTEMIN;  /* required for frame header */

   173 

   174     return cPar;

   175 }

   176 

   177 

   178 size_t ZSTD_estimateCCtxSize(ZSTD_compressionParameters cParams)

   179 {

   180     size_t const blockSize = MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, (size_t)1 << cParams.windowLog);

   181     U32    const divider = (cParams.searchLength==3) ? 3 : 4;

   182     size_t const maxNbSeq = blockSize / divider;

   183     size_t const tokenSpace = blockSize + 11*maxNbSeq;

   184 

   185     size_t const chainSize = (cParams.strategy == ZSTD_fast) ? 0 : (1 << cParams.chainLog);

   186     size_t const hSize = ((size_t)1) << cParams.hashLog;

   187     U32    const hashLog3 = (cParams.searchLength>3) ? 0 : MIN(ZSTD_HASHLOG3_MAX, cParams.windowLog);

   188     size_t const h3Size = ((size_t)1) << hashLog3;

   189     size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32);

   190 

   191     size_t const optSpace = ((MaxML+1) + (MaxLL+1) + (MaxOff+1) + (1<<Litbits))*sizeof(U32)

   192                           + (ZSTD_OPT_NUM+1)*(sizeof(ZSTD_match_t) + sizeof(ZSTD_optimal_t));

   193     size_t const neededSpace = tableSpace + (256*sizeof(U32)) /* huffTable */ + tokenSpace

   194                              + (((cParams.strategy == ZSTD_btopt) || (cParams.strategy == ZSTD_btopt2)) ? optSpace : 0);

   195 

   196     return sizeof(ZSTD_CCtx) + neededSpace;

   197 }

   198 

   199 

   200 static U32 ZSTD_equivalentParams(ZSTD_parameters param1, ZSTD_parameters param2)

   201 {

   202     return (param1.cParams.hashLog  == param2.cParams.hashLog)

   203          & (param1.cParams.chainLog == param2.cParams.chainLog)

   204          & (param1.cParams.strategy == param2.cParams.strategy)

   205          & ((param1.cParams.searchLength==3) == (param2.cParams.searchLength==3));

   206 }

   207 

   208 /*! ZSTD_continueCCtx() :

   209     reuse CCtx without reset (note : requires no dictionary) */

   210 static size_t ZSTD_continueCCtx(ZSTD_CCtx* cctx, ZSTD_parameters params, U64 frameContentSize)

   211 {

   212     U32 const end = (U32)(cctx->nextSrc - cctx->base);

   213     cctx->params = params;

   214     cctx->frameContentSize = frameContentSize;

   215     cctx->lowLimit = end;

   216     cctx->dictLimit = end;

   217     cctx->nextToUpdate = end+1;

   218     cctx->stage = ZSTDcs_init;

   219     cctx->dictID = 0;

   220     cctx->loadedDictEnd = 0;

   221     { int i; for (i=0; i<ZSTD_REP_NUM; i++) cctx->rep[i] = repStartValue[i]; }

   222     cctx->seqStore.litLengthSum = 0;  /* force reset of btopt stats */

   223     XXH64_reset(&cctx->xxhState, 0);

   224     return 0;

   225 }

   226 

   227 typedef enum { ZSTDcrp_continue, ZSTDcrp_noMemset, ZSTDcrp_fullReset } ZSTD_compResetPolicy_e;

   228 

   229 /*! ZSTD_resetCCtx_advanced() :

   230     note : 'params' must be validated */

   231 static size_t ZSTD_resetCCtx_advanced (ZSTD_CCtx* zc,

   232                                        ZSTD_parameters params, U64 frameContentSize,

   233                                        ZSTD_compResetPolicy_e const crp)

   234 {

   235     if (crp == ZSTDcrp_continue)

   236         if (ZSTD_equivalentParams(params, zc->params))

   237             return ZSTD_continueCCtx(zc, params, frameContentSize);

   238 

   239     {   size_t const blockSize = MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, (size_t)1 << params.cParams.windowLog);

   240         U32    const divider = (params.cParams.searchLength==3) ? 3 : 4;

   241         size_t const maxNbSeq = blockSize / divider;

   242         size_t const tokenSpace = blockSize + 11*maxNbSeq;

   243         size_t const chainSize = (params.cParams.strategy == ZSTD_fast) ? 0 : (1 << params.cParams.chainLog);

   244         size_t const hSize = ((size_t)1) << params.cParams.hashLog;

   245         U32    const hashLog3 = (params.cParams.searchLength>3) ? 0 : MIN(ZSTD_HASHLOG3_MAX, params.cParams.windowLog);

   246         size_t const h3Size = ((size_t)1) << hashLog3;

   247         size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32);

   248         void* ptr;

   249 

   250         /* Check if workSpace is large enough, alloc a new one if needed */

   251         {   size_t const optSpace = ((MaxML+1) + (MaxLL+1) + (MaxOff+1) + (1<<Litbits))*sizeof(U32)

   252                                   + (ZSTD_OPT_NUM+1)*(sizeof(ZSTD_match_t) + sizeof(ZSTD_optimal_t));

   253             size_t const neededSpace = tableSpace + (256*sizeof(U32)) /* huffTable */ + tokenSpace

   254                                   + (((params.cParams.strategy == ZSTD_btopt) || (params.cParams.strategy == ZSTD_btopt2)) ? optSpace : 0);

   255             if (zc->workSpaceSize < neededSpace) {

   256                 ZSTD_free(zc->workSpace, zc->customMem);

   257                 zc->workSpace = ZSTD_malloc(neededSpace, zc->customMem);

   258                 if (zc->workSpace == NULL) return ERROR(memory_allocation);

   259                 zc->workSpaceSize = neededSpace;

   260         }   }

   261 

   262         if (crp!=ZSTDcrp_noMemset) memset(zc->workSpace, 0, tableSpace);   /* reset tables only */

   263         XXH64_reset(&zc->xxhState, 0);

   264         zc->hashLog3 = hashLog3;

   265         zc->hashTable = (U32*)(zc->workSpace);

   266         zc->chainTable = zc->hashTable + hSize;

   267         zc->hashTable3 = zc->chainTable + chainSize;

   268         ptr = zc->hashTable3 + h3Size;

   269         zc->hufTable = (HUF_CElt*)ptr;

   270         zc->flagStaticTables = 0;

   271         ptr = ((U32*)ptr) + 256;  /* note : HUF_CElt* is incomplete type, size is simulated using U32 */

   272 

   273         zc->nextToUpdate = 1;

   274         zc->nextSrc = NULL;

   275         zc->base = NULL;

   276         zc->dictBase = NULL;

   277         zc->dictLimit = 0;

   278         zc->lowLimit = 0;

   279         zc->params = params;

   280         zc->blockSize = blockSize;

   281         zc->frameContentSize = frameContentSize;

   282         { int i; for (i=0; i<ZSTD_REP_NUM; i++) zc->rep[i] = repStartValue[i]; }

   283 

   284         if ((params.cParams.strategy == ZSTD_btopt) || (params.cParams.strategy == ZSTD_btopt2)) {

   285             zc->seqStore.litFreq = (U32*)ptr;

   286             zc->seqStore.litLengthFreq = zc->seqStore.litFreq + (1<<Litbits);

   287             zc->seqStore.matchLengthFreq = zc->seqStore.litLengthFreq + (MaxLL+1);

   288             zc->seqStore.offCodeFreq = zc->seqStore.matchLengthFreq + (MaxML+1);

   289             ptr = zc->seqStore.offCodeFreq + (MaxOff+1);

   290             zc->seqStore.matchTable = (ZSTD_match_t*)ptr;

   291             ptr = zc->seqStore.matchTable + ZSTD_OPT_NUM+1;

   292             zc->seqStore.priceTable = (ZSTD_optimal_t*)ptr;

   293             ptr = zc->seqStore.priceTable + ZSTD_OPT_NUM+1;

   294             zc->seqStore.litLengthSum = 0;

   295         }

   296         zc->seqStore.sequencesStart = (seqDef*)ptr;

   297         ptr = zc->seqStore.sequencesStart + maxNbSeq;

   298         zc->seqStore.llCode = (BYTE*) ptr;

   299         zc->seqStore.mlCode = zc->seqStore.llCode + maxNbSeq;

   300         zc->seqStore.ofCode = zc->seqStore.mlCode + maxNbSeq;

   301         zc->seqStore.litStart = zc->seqStore.ofCode + maxNbSeq;

   302 

   303         zc->stage = ZSTDcs_init;

   304         zc->dictID = 0;

   305         zc->loadedDictEnd = 0;

   306 

   307         return 0;

   308     }

   309 }

   310 

   311 

   312 /*! ZSTD_copyCCtx() :

   313 *   Duplicate an existing context `srcCCtx` into another one `dstCCtx`.

   314 *   Only works during stage ZSTDcs_init (i.e. after creation, but before first call to ZSTD_compressContinue()).

   315 *   @return : 0, or an error code */

   316 size_t ZSTD_copyCCtx(ZSTD_CCtx* dstCCtx, const ZSTD_CCtx* srcCCtx, unsigned long long pledgedSrcSize)

   317 {

   318     if (srcCCtx->stage!=ZSTDcs_init) return ERROR(stage_wrong);

   319 

   320     memcpy(&dstCCtx->customMem, &srcCCtx->customMem, sizeof(ZSTD_customMem));

   321     ZSTD_resetCCtx_advanced(dstCCtx, srcCCtx->params, pledgedSrcSize, ZSTDcrp_noMemset);

   322 

   323     /* copy tables */

   324     {   size_t const chainSize = (srcCCtx->params.cParams.strategy == ZSTD_fast) ? 0 : (1 << srcCCtx->params.cParams.chainLog);

   325         size_t const hSize = ((size_t)1) << srcCCtx->params.cParams.hashLog;

   326         size_t const h3Size = (size_t)1 << srcCCtx->hashLog3;

   327         size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32);

   328         memcpy(dstCCtx->workSpace, srcCCtx->workSpace, tableSpace);

   329     }

   330 

   331     /* copy dictionary offsets */

   332     dstCCtx->nextToUpdate = srcCCtx->nextToUpdate;

   333     dstCCtx->nextToUpdate3= srcCCtx->nextToUpdate3;

   334     dstCCtx->nextSrc      = srcCCtx->nextSrc;

   335     dstCCtx->base         = srcCCtx->base;

   336     dstCCtx->dictBase     = srcCCtx->dictBase;

   337     dstCCtx->dictLimit    = srcCCtx->dictLimit;

   338     dstCCtx->lowLimit     = srcCCtx->lowLimit;

   339     dstCCtx->loadedDictEnd= srcCCtx->loadedDictEnd;

   340     dstCCtx->dictID       = srcCCtx->dictID;

   341 

   342     /* copy entropy tables */

   343     dstCCtx->flagStaticTables = srcCCtx->flagStaticTables;

   344     if (srcCCtx->flagStaticTables) {

   345         memcpy(dstCCtx->hufTable, srcCCtx->hufTable, 256*4);

   346         memcpy(dstCCtx->litlengthCTable, srcCCtx->litlengthCTable, sizeof(dstCCtx->litlengthCTable));

   347         memcpy(dstCCtx->matchlengthCTable, srcCCtx->matchlengthCTable, sizeof(dstCCtx->matchlengthCTable));

   348         memcpy(dstCCtx->offcodeCTable, srcCCtx->offcodeCTable, sizeof(dstCCtx->offcodeCTable));

   349     }

   350 

   351     return 0;

   352 }

   353 

   354 

   355 /*! ZSTD_reduceTable() :

   356 *   reduce table indexes by `reducerValue` */

   357 static void ZSTD_reduceTable (U32* const table, U32 const size, U32 const reducerValue)

   358 {

   359     U32 u;

   360     for (u=0 ; u < size ; u++) {

   361         if (table[u] < reducerValue) table[u] = 0;

   362         else table[u] -= reducerValue;

   363     }

   364 }

   365 

   366 /*! ZSTD_reduceIndex() :

   367 *   rescale all indexes to avoid future overflow (indexes are U32) */

   368 static void ZSTD_reduceIndex (ZSTD_CCtx* zc, const U32 reducerValue)

   369 {

   370     { U32 const hSize = 1 << zc->params.cParams.hashLog;

   371       ZSTD_reduceTable(zc->hashTable, hSize, reducerValue); }

   372 

   373     { U32 const chainSize = (zc->params.cParams.strategy == ZSTD_fast) ? 0 : (1 << zc->params.cParams.chainLog);

   374       ZSTD_reduceTable(zc->chainTable, chainSize, reducerValue); }

   375 

   376     { U32 const h3Size = (zc->hashLog3) ? 1 << zc->hashLog3 : 0;

   377       ZSTD_reduceTable(zc->hashTable3, h3Size, reducerValue); }

   378 }

   379 

   380 

   381 /*-*******************************************************

   382 *  Block entropic compression

   383 *********************************************************/

   384 

   385 /* See doc/zstd_compression_format.md for detailed format description */

   386 

   387 size_t ZSTD_noCompressBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize)

   388 {

   389     if (srcSize + ZSTD_blockHeaderSize > dstCapacity) return ERROR(dstSize_tooSmall);

   390     memcpy((BYTE*)dst + ZSTD_blockHeaderSize, src, srcSize);

   391     MEM_writeLE24(dst, (U32)(srcSize << 2) + (U32)bt_raw);

   392     return ZSTD_blockHeaderSize+srcSize;

   393 }

   394 

   395 

   396 static size_t ZSTD_noCompressLiterals (void* dst, size_t dstCapacity, const void* src, size_t srcSize)

   397 {

   398     BYTE* const ostart = (BYTE* const)dst;

   399     U32   const flSize = 1 + (srcSize>31) + (srcSize>4095);

   400 

   401     if (srcSize + flSize > dstCapacity) return ERROR(dstSize_tooSmall);

   402 

   403     switch(flSize)

   404     {

   405         case 1: /* 2 - 1 - 5 */

   406             ostart[0] = (BYTE)((U32)set_basic + (srcSize<<3));

   407             break;

   408         case 2: /* 2 - 2 - 12 */

   409             MEM_writeLE16(ostart, (U16)((U32)set_basic + (1<<2) + (srcSize<<4)));

   410             break;

   411         default:   /*note : should not be necessary : flSize is within {1,2,3} */

   412         case 3: /* 2 - 2 - 20 */

   413             MEM_writeLE32(ostart, (U32)((U32)set_basic + (3<<2) + (srcSize<<4)));

   414             break;

   415     }

   416 

   417     memcpy(ostart + flSize, src, srcSize);

   418     return srcSize + flSize;

   419 }

   420 

   421 static size_t ZSTD_compressRleLiteralsBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize)

   422 {

   423     BYTE* const ostart = (BYTE* const)dst;

   424     U32   const flSize = 1 + (srcSize>31) + (srcSize>4095);

   425 

   426     (void)dstCapacity;  /* dstCapacity already guaranteed to be >=4, hence large enough */

   427 

   428     switch(flSize)

   429     {

   430         case 1: /* 2 - 1 - 5 */

   431             ostart[0] = (BYTE)((U32)set_rle + (srcSize<<3));

   432             break;

   433         case 2: /* 2 - 2 - 12 */

   434             MEM_writeLE16(ostart, (U16)((U32)set_rle + (1<<2) + (srcSize<<4)));

   435             break;

   436         default:   /*note : should not be necessary : flSize is necessarily within {1,2,3} */

   437         case 3: /* 2 - 2 - 20 */

   438             MEM_writeLE32(ostart, (U32)((U32)set_rle + (3<<2) + (srcSize<<4)));

   439             break;

   440     }

   441 

   442     ostart[flSize] = *(const BYTE*)src;

   443     return flSize+1;

   444 }

   445 

   446 

   447 static size_t ZSTD_minGain(size_t srcSize) { return (srcSize >> 6) + 2; }

   448 

   449 static size_t ZSTD_compressLiterals (ZSTD_CCtx* zc,

   450                                      void* dst, size_t dstCapacity,

   451                                const void* src, size_t srcSize)

   452 {

   453     size_t const minGain = ZSTD_minGain(srcSize);

   454     size_t const lhSize = 3 + (srcSize >= 1 KB) + (srcSize >= 16 KB);

   455     BYTE*  const ostart = (BYTE*)dst;

   456     U32 singleStream = srcSize < 256;

   457     symbolEncodingType_e hType = set_compressed;

   458     size_t cLitSize;

   459 

   460 

   461     /* small ? don't even attempt compression (speed opt) */

   462 #   define LITERAL_NOENTROPY 63

   463     {   size_t const minLitSize = zc->flagStaticTables ? 6 : LITERAL_NOENTROPY;

   464         if (srcSize <= minLitSize) return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);

   465     }

   466 

   467     if (dstCapacity < lhSize+1) return ERROR(dstSize_tooSmall);   /* not enough space for compression */

   468     if (zc->flagStaticTables && (lhSize==3)) {

   469         hType = set_repeat;

   470         singleStream = 1;

   471         cLitSize = HUF_compress1X_usingCTable(ostart+lhSize, dstCapacity-lhSize, src, srcSize, zc->hufTable);

   472     } else {

   473         cLitSize = singleStream ? HUF_compress1X(ostart+lhSize, dstCapacity-lhSize, src, srcSize, 255, 11)

   474                                 : HUF_compress2 (ostart+lhSize, dstCapacity-lhSize, src, srcSize, 255, 11);

   475     }

   476 

   477     if ((cLitSize==0) | (cLitSize >= srcSize - minGain))

   478         return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);

   479     if (cLitSize==1)

   480         return ZSTD_compressRleLiteralsBlock(dst, dstCapacity, src, srcSize);

   481 

   482     /* Build header */

   483     switch(lhSize)

   484     {

   485     case 3: /* 2 - 2 - 10 - 10 */

   486         {   U32 const lhc = hType + ((!singleStream) << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<14);

   487             MEM_writeLE24(ostart, lhc);

   488             break;

   489         }

   490     case 4: /* 2 - 2 - 14 - 14 */

   491         {   U32 const lhc = hType + (2 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<18);

   492             MEM_writeLE32(ostart, lhc);

   493             break;

   494         }

   495     default:   /* should not be necessary, lhSize is only {3,4,5} */

   496     case 5: /* 2 - 2 - 18 - 18 */

   497         {   U32 const lhc = hType + (3 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<22);

   498             MEM_writeLE32(ostart, lhc);

   499             ostart[4] = (BYTE)(cLitSize >> 10);

   500             break;

   501         }

   502     }

   503     return lhSize+cLitSize;

   504 }

   505 

   506 static const BYTE LL_Code[64] = {  0,  1,  2,  3,  4,  5,  6,  7,

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

   508                                   16, 16, 17, 17, 18, 18, 19, 19,

   509                                   20, 20, 20, 20, 21, 21, 21, 21,

   510                                   22, 22, 22, 22, 22, 22, 22, 22,

   511                                   23, 23, 23, 23, 23, 23, 23, 23,

   512                                   24, 24, 24, 24, 24, 24, 24, 24,

   513                                   24, 24, 24, 24, 24, 24, 24, 24 };

   514 

   515 static const BYTE ML_Code[128] = { 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15,

   516                                   16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,

   517                                   32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37,

   518                                   38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39,

   519                                   40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,

   520                                   41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,

   521                                   42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,

   522                                   42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42 };

   523 

   524 

   525 void ZSTD_seqToCodes(const seqStore_t* seqStorePtr)

   526 {

   527     BYTE const LL_deltaCode = 19;

   528     BYTE const ML_deltaCode = 36;

   529     const seqDef* const sequences = seqStorePtr->sequencesStart;

   530     BYTE* const llCodeTable = seqStorePtr->llCode;

   531     BYTE* const ofCodeTable = seqStorePtr->ofCode;

   532     BYTE* const mlCodeTable = seqStorePtr->mlCode;

   533     U32 const nbSeq = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);

   534     U32 u;

   535     for (u=0; u<nbSeq; u++) {

   536         U32 const llv = sequences[u].litLength;

   537         U32 const mlv = sequences[u].matchLength;

   538         llCodeTable[u] = (llv> 63) ? (BYTE)ZSTD_highbit32(llv) + LL_deltaCode : LL_Code[llv];

   539         ofCodeTable[u] = (BYTE)ZSTD_highbit32(sequences[u].offset);

   540         mlCodeTable[u] = (mlv>127) ? (BYTE)ZSTD_highbit32(mlv) + ML_deltaCode : ML_Code[mlv];

   541     }

   542     if (seqStorePtr->longLengthID==1)

   543         llCodeTable[seqStorePtr->longLengthPos] = MaxLL;

   544     if (seqStorePtr->longLengthID==2)

   545         mlCodeTable[seqStorePtr->longLengthPos] = MaxML;

   546 }

   547 

   548 

   549 size_t ZSTD_compressSequences(ZSTD_CCtx* zc,

   550                               void* dst, size_t dstCapacity,

   551                               size_t srcSize)

   552 {

   553     const seqStore_t* seqStorePtr = &(zc->seqStore);

   554     U32 count[MaxSeq+1];

   555     S16 norm[MaxSeq+1];

   556     FSE_CTable* CTable_LitLength = zc->litlengthCTable;

   557     FSE_CTable* CTable_OffsetBits = zc->offcodeCTable;

   558     FSE_CTable* CTable_MatchLength = zc->matchlengthCTable;

   559     U32 LLtype, Offtype, MLtype;   /* compressed, raw or rle */

   560     const seqDef* const sequences = seqStorePtr->sequencesStart;

   561     const BYTE* const ofCodeTable = seqStorePtr->ofCode;

   562     const BYTE* const llCodeTable = seqStorePtr->llCode;

   563     const BYTE* const mlCodeTable = seqStorePtr->mlCode;

   564     BYTE* const ostart = (BYTE*)dst;

   565     BYTE* const oend = ostart + dstCapacity;

   566     BYTE* op = ostart;

   567     size_t const nbSeq = seqStorePtr->sequences - seqStorePtr->sequencesStart;

   568     BYTE* seqHead;

   569 

   570     /* Compress literals */

   571     {   const BYTE* const literals = seqStorePtr->litStart;

   572         size_t const litSize = seqStorePtr->lit - literals;

   573         size_t const cSize = ZSTD_compressLiterals(zc, op, dstCapacity, literals, litSize);

   574         if (ZSTD_isError(cSize)) return cSize;

   575         op += cSize;

   576     }

   577 

   578     /* Sequences Header */

   579     if ((oend-op) < 3 /*max nbSeq Size*/ + 1 /*seqHead */) return ERROR(dstSize_tooSmall);

   580     if (nbSeq < 0x7F) *op++ = (BYTE)nbSeq;

   581     else if (nbSeq < LONGNBSEQ) op[0] = (BYTE)((nbSeq>>8) + 0x80), op[1] = (BYTE)nbSeq, op+=2;

   582     else op[0]=0xFF, MEM_writeLE16(op+1, (U16)(nbSeq - LONGNBSEQ)), op+=3;

   583     if (nbSeq==0) goto _check_compressibility;

   584 

   585     /* seqHead : flags for FSE encoding type */

   586     seqHead = op++;

   587 

   588 #define MIN_SEQ_FOR_DYNAMIC_FSE   64

   589 #define MAX_SEQ_FOR_STATIC_FSE  1000

   590 

   591     /* convert length/distances into codes */

   592     ZSTD_seqToCodes(seqStorePtr);

   593 

   594     /* CTable for Literal Lengths */

   595     {   U32 max = MaxLL;

   596         size_t const mostFrequent = FSE_countFast(count, &max, llCodeTable, nbSeq);

   597         if ((mostFrequent == nbSeq) && (nbSeq > 2)) {

   598             *op++ = llCodeTable[0];

   599             FSE_buildCTable_rle(CTable_LitLength, (BYTE)max);

   600             LLtype = set_rle;

   601         } else if ((zc->flagStaticTables) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) {

   602             LLtype = set_repeat;

   603         } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (LL_defaultNormLog-1)))) {

   604             FSE_buildCTable(CTable_LitLength, LL_defaultNorm, MaxLL, LL_defaultNormLog);

   605             LLtype = set_basic;

   606         } else {

   607             size_t nbSeq_1 = nbSeq;

   608             const U32 tableLog = FSE_optimalTableLog(LLFSELog, nbSeq, max);

   609             if (count[llCodeTable[nbSeq-1]]>1) { count[llCodeTable[nbSeq-1]]--; nbSeq_1--; }

   610             FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max);

   611             { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog);   /* overflow protected */

   612               if (FSE_isError(NCountSize)) return ERROR(GENERIC);

   613               op += NCountSize; }

   614             FSE_buildCTable(CTable_LitLength, norm, max, tableLog);

   615             LLtype = set_compressed;

   616     }   }

   617 

   618     /* CTable for Offsets */

   619     {   U32 max = MaxOff;

   620         size_t const mostFrequent = FSE_countFast(count, &max, ofCodeTable, nbSeq);

   621         if ((mostFrequent == nbSeq) && (nbSeq > 2)) {

   622             *op++ = ofCodeTable[0];

   623             FSE_buildCTable_rle(CTable_OffsetBits, (BYTE)max);

   624             Offtype = set_rle;

   625         } else if ((zc->flagStaticTables) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) {

   626             Offtype = set_repeat;

   627         } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (OF_defaultNormLog-1)))) {

   628             FSE_buildCTable(CTable_OffsetBits, OF_defaultNorm, MaxOff, OF_defaultNormLog);

   629             Offtype = set_basic;

   630         } else {

   631             size_t nbSeq_1 = nbSeq;

   632             const U32 tableLog = FSE_optimalTableLog(OffFSELog, nbSeq, max);

   633             if (count[ofCodeTable[nbSeq-1]]>1) { count[ofCodeTable[nbSeq-1]]--; nbSeq_1--; }

   634             FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max);

   635             { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog);   /* overflow protected */

   636               if (FSE_isError(NCountSize)) return ERROR(GENERIC);

   637               op += NCountSize; }

   638             FSE_buildCTable(CTable_OffsetBits, norm, max, tableLog);

   639             Offtype = set_compressed;

   640     }   }

   641 

   642     /* CTable for MatchLengths */

   643     {   U32 max = MaxML;

   644         size_t const mostFrequent = FSE_countFast(count, &max, mlCodeTable, nbSeq);

   645         if ((mostFrequent == nbSeq) && (nbSeq > 2)) {

   646             *op++ = *mlCodeTable;

   647             FSE_buildCTable_rle(CTable_MatchLength, (BYTE)max);

   648             MLtype = set_rle;

   649         } else if ((zc->flagStaticTables) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) {

   650             MLtype = set_repeat;

   651         } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (ML_defaultNormLog-1)))) {

   652             FSE_buildCTable(CTable_MatchLength, ML_defaultNorm, MaxML, ML_defaultNormLog);

   653             MLtype = set_basic;

   654         } else {

   655             size_t nbSeq_1 = nbSeq;

   656             const U32 tableLog = FSE_optimalTableLog(MLFSELog, nbSeq, max);

   657             if (count[mlCodeTable[nbSeq-1]]>1) { count[mlCodeTable[nbSeq-1]]--; nbSeq_1--; }

   658             FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max);

   659             { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog);   /* overflow protected */

   660               if (FSE_isError(NCountSize)) return ERROR(GENERIC);

   661               op += NCountSize; }

   662             FSE_buildCTable(CTable_MatchLength, norm, max, tableLog);

   663             MLtype = set_compressed;

   664     }   }

   665 

   666     *seqHead = (BYTE)((LLtype<<6) + (Offtype<<4) + (MLtype<<2));

   667     zc->flagStaticTables = 0;

   668 

   669     /* Encoding Sequences */

   670     {   BIT_CStream_t blockStream;

   671         FSE_CState_t  stateMatchLength;

   672         FSE_CState_t  stateOffsetBits;

   673         FSE_CState_t  stateLitLength;

   674 

   675         CHECK_E(BIT_initCStream(&blockStream, op, oend-op), dstSize_tooSmall); /* not enough space remaining */

   676 

   677         /* first symbols */

   678         FSE_initCState2(&stateMatchLength, CTable_MatchLength, mlCodeTable[nbSeq-1]);

   679         FSE_initCState2(&stateOffsetBits,  CTable_OffsetBits,  ofCodeTable[nbSeq-1]);

   680         FSE_initCState2(&stateLitLength,   CTable_LitLength,   llCodeTable[nbSeq-1]);

   681         BIT_addBits(&blockStream, sequences[nbSeq-1].litLength, LL_bits[llCodeTable[nbSeq-1]]);

   682         if (MEM_32bits()) BIT_flushBits(&blockStream);

   683         BIT_addBits(&blockStream, sequences[nbSeq-1].matchLength, ML_bits[mlCodeTable[nbSeq-1]]);

   684         if (MEM_32bits()) BIT_flushBits(&blockStream);

   685         BIT_addBits(&blockStream, sequences[nbSeq-1].offset, ofCodeTable[nbSeq-1]);

   686         BIT_flushBits(&blockStream);

   687 

   688         {   size_t n;

   689             for (n=nbSeq-2 ; n<nbSeq ; n--) {      /* intentional underflow */

   690                 BYTE const llCode = llCodeTable[n];

   691                 BYTE const ofCode = ofCodeTable[n];

   692                 BYTE const mlCode = mlCodeTable[n];

   693                 U32  const llBits = LL_bits[llCode];

   694                 U32  const ofBits = ofCode;                                     /* 32b*/  /* 64b*/

   695                 U32  const mlBits = ML_bits[mlCode];

   696                                                                                 /* (7)*/  /* (7)*/

   697                 FSE_encodeSymbol(&blockStream, &stateOffsetBits, ofCode);       /* 15 */  /* 15 */

   698                 FSE_encodeSymbol(&blockStream, &stateMatchLength, mlCode);      /* 24 */  /* 24 */

   699                 if (MEM_32bits()) BIT_flushBits(&blockStream);                  /* (7)*/

   700                 FSE_encodeSymbol(&blockStream, &stateLitLength, llCode);        /* 16 */  /* 33 */

   701                 if (MEM_32bits() || (ofBits+mlBits+llBits >= 64-7-(LLFSELog+MLFSELog+OffFSELog)))

   702                     BIT_flushBits(&blockStream);                                /* (7)*/

   703                 BIT_addBits(&blockStream, sequences[n].litLength, llBits);

   704                 if (MEM_32bits() && ((llBits+mlBits)>24)) BIT_flushBits(&blockStream);

   705                 BIT_addBits(&blockStream, sequences[n].matchLength, mlBits);

   706                 if (MEM_32bits()) BIT_flushBits(&blockStream);                  /* (7)*/

   707                 BIT_addBits(&blockStream, sequences[n].offset, ofBits);         /* 31 */

   708                 BIT_flushBits(&blockStream);                                    /* (7)*/

   709         }   }

   710 

   711         FSE_flushCState(&blockStream, &stateMatchLength);

   712         FSE_flushCState(&blockStream, &stateOffsetBits);

   713         FSE_flushCState(&blockStream, &stateLitLength);

   714 

   715         {   size_t const streamSize = BIT_closeCStream(&blockStream);

   716             if (streamSize==0) return ERROR(dstSize_tooSmall);   /* not enough space */

   717             op += streamSize;

   718     }   }

   719 

   720     /* check compressibility */

   721 _check_compressibility:

   722     { size_t const minGain = ZSTD_minGain(srcSize);

   723       size_t const maxCSize = srcSize - minGain;

   724       if ((size_t)(op-ostart) >= maxCSize) return 0; }

   725 

   726     /* confirm repcodes */

   727     { int i; for (i=0; i<ZSTD_REP_NUM; i++) zc->rep[i] = zc->savedRep[i]; }

   728 

   729     return op - ostart;

   730 }

   731 

   732 

   733 /*! ZSTD_storeSeq() :

   734     Store a sequence (literal length, literals, offset code and match length code) into seqStore_t.

   735     `offsetCode` : distance to match, or 0 == repCode.

   736     `matchCode` : matchLength - MINMATCH

   737 */

   738 MEM_STATIC void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const void* literals, U32 offsetCode, size_t matchCode)

   739 {

   740 #if 0  /* for debug */

   741     static const BYTE* g_start = NULL;

   742     const U32 pos = (U32)(literals - g_start);

   743     if (g_start==NULL) g_start = literals;

   744     //if ((pos > 1) && (pos < 50000))

   745         printf("Cpos %6u :%5u literals & match %3u bytes at distance %6u \n",

   746                pos, (U32)litLength, (U32)matchCode+MINMATCH, (U32)offsetCode);

   747 #endif

   748     /* copy Literals */

   749     ZSTD_wildcopy(seqStorePtr->lit, literals, litLength);

   750     seqStorePtr->lit += litLength;

   751 

   752     /* literal Length */

   753     if (litLength>0xFFFF) { seqStorePtr->longLengthID = 1; seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); }

   754     seqStorePtr->sequences[0].litLength = (U16)litLength;

   755 

   756     /* match offset */

   757     seqStorePtr->sequences[0].offset = offsetCode + 1;

   758 

   759     /* match Length */

   760     if (matchCode>0xFFFF) { seqStorePtr->longLengthID = 2; seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); }

   761     seqStorePtr->sequences[0].matchLength = (U16)matchCode;

   762 

   763     seqStorePtr->sequences++;

   764 }

   765 

   766 

   767 /*-*************************************

   768 *  Match length counter

   769 ***************************************/

   770 static unsigned ZSTD_NbCommonBytes (register size_t val)

   771 {

   772     if (MEM_isLittleEndian()) {

   773         if (MEM_64bits()) {

   774 #       if defined(_MSC_VER) && defined(_WIN64)

   775             unsigned long r = 0;

   776             _BitScanForward64( &r, (U64)val );

   777             return (unsigned)(r>>3);

   778 #       elif defined(__GNUC__) && (__GNUC__ >= 3)

   779             return (__builtin_ctzll((U64)val) >> 3);

   780 #       else

   781             static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5, 3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5, 5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4, 4, 5, 7, 2, 6, 5, 7, 6, 7, 7 };

   782             return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];

   783 #       endif

   784         } else { /* 32 bits */

   785 #       if defined(_MSC_VER)

   786             unsigned long r=0;

   787             _BitScanForward( &r, (U32)val );

   788             return (unsigned)(r>>3);

   789 #       elif defined(__GNUC__) && (__GNUC__ >= 3)

   790             return (__builtin_ctz((U32)val) >> 3);

   791 #       else

   792             static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, 3, 2, 2, 1, 3, 2, 0, 1, 3, 3, 1, 2, 2, 2, 2, 0, 3, 1, 2, 0, 1, 0, 1, 1 };

   793             return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];

   794 #       endif

   795         }

   796     } else {  /* Big Endian CPU */

   797         if (MEM_64bits()) {

   798 #       if defined(_MSC_VER) && defined(_WIN64)

   799             unsigned long r = 0;

   800             _BitScanReverse64( &r, val );

   801             return (unsigned)(r>>3);

   802 #       elif defined(__GNUC__) && (__GNUC__ >= 3)

   803             return (__builtin_clzll(val) >> 3);

   804 #       else

   805             unsigned r;

   806             const unsigned n32 = sizeof(size_t)*4;   /* calculate this way due to compiler complaining in 32-bits mode */

   807             if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }

   808             if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }

   809             r += (!val);

   810             return r;

   811 #       endif

   812         } else { /* 32 bits */

   813 #       if defined(_MSC_VER)

   814             unsigned long r = 0;

   815             _BitScanReverse( &r, (unsigned long)val );

   816             return (unsigned)(r>>3);

   817 #       elif defined(__GNUC__) && (__GNUC__ >= 3)

   818             return (__builtin_clz((U32)val) >> 3);

   819 #       else

   820             unsigned r;

   821             if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }

   822             r += (!val);

   823             return r;

   824 #       endif

   825     }   }

   826 }

   827 

   828 

   829 static size_t ZSTD_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* const pInLimit)

   830 {

   831     const BYTE* const pStart = pIn;

   832     const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1);

   833 

   834     while (pIn < pInLoopLimit) {

   835         size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);

   836         if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; }

   837         pIn += ZSTD_NbCommonBytes(diff);

   838         return (size_t)(pIn - pStart);

   839     }

   840     if (MEM_64bits()) if ((pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatch+=4; }

   841     if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; }

   842     if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;

   843     return (size_t)(pIn - pStart);

   844 }

   845 

   846 /** ZSTD_count_2segments() :

   847 *   can count match length with `ip` & `match` in 2 different segments.

   848 *   convention : on reaching mEnd, match count continue starting from iStart

   849 */

   850 static size_t ZSTD_count_2segments(const BYTE* ip, const BYTE* match, const BYTE* iEnd, const BYTE* mEnd, const BYTE* iStart)

   851 {

   852     const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd);

   853     size_t const matchLength = ZSTD_count(ip, match, vEnd);

   854     if (match + matchLength != mEnd) return matchLength;

   855     return matchLength + ZSTD_count(ip+matchLength, iStart, iEnd);

   856 }

   857 

   858 

   859 /*-*************************************

   860 *  Hashes

   861 ***************************************/

   862 static const U32 prime3bytes = 506832829U;

   863 static U32    ZSTD_hash3(U32 u, U32 h) { return ((u << (32-24)) * prime3bytes)  >> (32-h) ; }

   864 MEM_STATIC size_t ZSTD_hash3Ptr(const void* ptr, U32 h) { return ZSTD_hash3(MEM_readLE32(ptr), h); }   /* only in zstd_opt.h */

   865 

   866 static const U32 prime4bytes = 2654435761U;

   867 static U32    ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32-h) ; }

   868 static size_t ZSTD_hash4Ptr(const void* ptr, U32 h) { return ZSTD_hash4(MEM_read32(ptr), h); }

   869 

   870 static const U64 prime5bytes = 889523592379ULL;

   871 static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u  << (64-40)) * prime5bytes) >> (64-h)) ; }

   872 static size_t ZSTD_hash5Ptr(const void* p, U32 h) { return ZSTD_hash5(MEM_readLE64(p), h); }

   873 

   874 static const U64 prime6bytes = 227718039650203ULL;

   875 static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u  << (64-48)) * prime6bytes) >> (64-h)) ; }

   876 static size_t ZSTD_hash6Ptr(const void* p, U32 h) { return ZSTD_hash6(MEM_readLE64(p), h); }

   877 

   878 static const U64 prime7bytes = 58295818150454627ULL;

   879 static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u  << (64-56)) * prime7bytes) >> (64-h)) ; }

   880 static size_t ZSTD_hash7Ptr(const void* p, U32 h) { return ZSTD_hash7(MEM_readLE64(p), h); }

   881 

   882 static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL;

   883 static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; }

   884 static size_t ZSTD_hash8Ptr(const void* p, U32 h) { return ZSTD_hash8(MEM_readLE64(p), h); }

   885 

   886 static size_t ZSTD_hashPtr(const void* p, U32 hBits, U32 mls)

   887 {

   888     switch(mls)

   889     {

   890     default:

   891     case 4: return ZSTD_hash4Ptr(p, hBits);

   892     case 5: return ZSTD_hash5Ptr(p, hBits);

   893     case 6: return ZSTD_hash6Ptr(p, hBits);

   894     case 7: return ZSTD_hash7Ptr(p, hBits);

   895     case 8: return ZSTD_hash8Ptr(p, hBits);

   896     }

   897 }

   898 

   899 

   900 /*-*************************************

   901 *  Fast Scan

   902 ***************************************/

   903 static void ZSTD_fillHashTable (ZSTD_CCtx* zc, const void* end, const U32 mls)

   904 {

   905     U32* const hashTable = zc->hashTable;

   906     U32  const hBits = zc->params.cParams.hashLog;

   907     const BYTE* const base = zc->base;

   908     const BYTE* ip = base + zc->nextToUpdate;

   909     const BYTE* const iend = ((const BYTE*)end) - HASH_READ_SIZE;

   910     const size_t fastHashFillStep = 3;

   911 

   912     while(ip <= iend) {

   913         hashTable[ZSTD_hashPtr(ip, hBits, mls)] = (U32)(ip - base);

   914         ip += fastHashFillStep;

   915     }

   916 }

   917 

   918 

   919 FORCE_INLINE

   920 void ZSTD_compressBlock_fast_generic(ZSTD_CCtx* cctx,

   921                                const void* src, size_t srcSize,

   922                                const U32 mls)

   923 {

   924     U32* const hashTable = cctx->hashTable;

   925     U32  const hBits = cctx->params.cParams.hashLog;

   926     seqStore_t* seqStorePtr = &(cctx->seqStore);

   927     const BYTE* const base = cctx->base;

   928     const BYTE* const istart = (const BYTE*)src;

   929     const BYTE* ip = istart;

   930     const BYTE* anchor = istart;

   931     const U32   lowestIndex = cctx->dictLimit;

   932     const BYTE* const lowest = base + lowestIndex;

   933     const BYTE* const iend = istart + srcSize;

   934     const BYTE* const ilimit = iend - HASH_READ_SIZE;

   935     U32 offset_1=cctx->rep[0], offset_2=cctx->rep[1];

   936     U32 offsetSaved = 0;

   937 

   938     /* init */

   939     ip += (ip==lowest);

   940     {   U32 const maxRep = (U32)(ip-lowest);

   941         if (offset_2 > maxRep) offsetSaved = offset_2, offset_2 = 0;

   942         if (offset_1 > maxRep) offsetSaved = offset_1, offset_1 = 0;

   943     }

   944 

   945     /* Main Search Loop */

   946     while (ip < ilimit) {   /* < instead of <=, because repcode check at (ip+1) */

   947         size_t mLength;

   948         size_t const h = ZSTD_hashPtr(ip, hBits, mls);

   949         U32 const current = (U32)(ip-base);

   950         U32 const matchIndex = hashTable[h];

   951         const BYTE* match = base + matchIndex;

   952         hashTable[h] = current;   /* update hash table */

   953 

   954         if ((offset_1 > 0) & (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1))) {

   955             mLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4;

   956             ip++;

   957             ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH);

   958         } else {

   959             U32 offset;

   960             if ( (matchIndex <= lowestIndex) || (MEM_read32(match) != MEM_read32(ip)) ) {

   961                 ip += ((ip-anchor) >> g_searchStrength) + 1;

   962                 continue;

   963             }

   964             mLength = ZSTD_count(ip+4, match+4, iend) + 4;

   965             offset = (U32)(ip-match);

   966             while (((ip>anchor) & (match>lowest)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */

   967             offset_2 = offset_1;

   968             offset_1 = offset;

   969 

   970             ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);

   971         }

   972 

   973         /* match found */

   974         ip += mLength;

   975         anchor = ip;

   976 

   977         if (ip <= ilimit) {

   978             /* Fill Table */

   979             hashTable[ZSTD_hashPtr(base+current+2, hBits, mls)] = current+2;  /* here because current+2 could be > iend-8 */

   980             hashTable[ZSTD_hashPtr(ip-2, hBits, mls)] = (U32)(ip-2-base);

   981             /* check immediate repcode */

   982             while ( (ip <= ilimit)

   983                  && ( (offset_2>0)

   984                  & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) {

   985                 /* store sequence */

   986                 size_t const rLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4;

   987                 { U32 const tmpOff = offset_2; offset_2 = offset_1; offset_1 = tmpOff; }  /* swap offset_2 <=> offset_1 */

   988                 hashTable[ZSTD_hashPtr(ip, hBits, mls)] = (U32)(ip-base);

   989                 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, rLength-MINMATCH);

   990                 ip += rLength;

   991                 anchor = ip;

   992                 continue;   /* faster when present ... (?) */

   993     }   }   }

   994 

   995     /* save reps for next block */

   996     cctx->savedRep[0] = offset_1 ? offset_1 : offsetSaved;

   997     cctx->savedRep[1] = offset_2 ? offset_2 : offsetSaved;

   998 

   999     /* Last Literals */

  1000     {   size_t const lastLLSize = iend - anchor;

  1001         memcpy(seqStorePtr->lit, anchor, lastLLSize);

  1002         seqStorePtr->lit += lastLLSize;

  1003     }

  1004 }

  1005 

  1006 

  1007 static void ZSTD_compressBlock_fast(ZSTD_CCtx* ctx,

  1008                        const void* src, size_t srcSize)

  1009 {

  1010     const U32 mls = ctx->params.cParams.searchLength;

  1011     switch(mls)

  1012     {

  1013     default:

  1014     case 4 :

  1015         ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 4); return;

  1016     case 5 :

  1017         ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 5); return;

  1018     case 6 :

  1019         ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 6); return;

  1020     case 7 :

  1021         ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 7); return;

  1022     }

  1023 }

  1024 

  1025 

  1026 static void ZSTD_compressBlock_fast_extDict_generic(ZSTD_CCtx* ctx,

  1027                                  const void* src, size_t srcSize,

  1028                                  const U32 mls)

  1029 {

  1030     U32* hashTable = ctx->hashTable;

  1031     const U32 hBits = ctx->params.cParams.hashLog;

  1032     seqStore_t* seqStorePtr = &(ctx->seqStore);

  1033     const BYTE* const base = ctx->base;

  1034     const BYTE* const dictBase = ctx->dictBase;

  1035     const BYTE* const istart = (const BYTE*)src;

  1036     const BYTE* ip = istart;

  1037     const BYTE* anchor = istart;

  1038     const U32   lowestIndex = ctx->lowLimit;

  1039     const BYTE* const dictStart = dictBase + lowestIndex;

  1040     const U32   dictLimit = ctx->dictLimit;

  1041     const BYTE* const lowPrefixPtr = base + dictLimit;

  1042     const BYTE* const dictEnd = dictBase + dictLimit;

  1043     const BYTE* const iend = istart + srcSize;

  1044     const BYTE* const ilimit = iend - 8;

  1045     U32 offset_1=ctx->rep[0], offset_2=ctx->rep[1];

  1046 

  1047     /* Search Loop */

  1048     while (ip < ilimit) {  /* < instead of <=, because (ip+1) */

  1049         const size_t h = ZSTD_hashPtr(ip, hBits, mls);

  1050         const U32 matchIndex = hashTable[h];

  1051         const BYTE* matchBase = matchIndex < dictLimit ? dictBase : base;

  1052         const BYTE* match = matchBase + matchIndex;

  1053         const U32 current = (U32)(ip-base);

  1054         const U32 repIndex = current + 1 - offset_1;   /* offset_1 expected <= current +1 */

  1055         const BYTE* repBase = repIndex < dictLimit ? dictBase : base;

  1056         const BYTE* repMatch = repBase + repIndex;

  1057         size_t mLength;

  1058         hashTable[h] = current;   /* update hash table */

  1059 

  1060         if ( (((U32)((dictLimit-1) - repIndex) >= 3) /* intentional underflow */ & (repIndex > lowestIndex))

  1061            && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {

  1062             const BYTE* repMatchEnd = repIndex < dictLimit ? dictEnd : iend;

  1063             mLength = ZSTD_count_2segments(ip+1+EQUAL_READ32, repMatch+EQUAL_READ32, iend, repMatchEnd, lowPrefixPtr) + EQUAL_READ32;

  1064             ip++;

  1065             ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH);

  1066         } else {

  1067             if ( (matchIndex < lowestIndex) ||

  1068                  (MEM_read32(match) != MEM_read32(ip)) ) {

  1069                 ip += ((ip-anchor) >> g_searchStrength) + 1;

  1070                 continue;

  1071             }

  1072             {   const BYTE* matchEnd = matchIndex < dictLimit ? dictEnd : iend;

  1073                 const BYTE* lowMatchPtr = matchIndex < dictLimit ? dictStart : lowPrefixPtr;

  1074                 U32 offset;

  1075                 mLength = ZSTD_count_2segments(ip+EQUAL_READ32, match+EQUAL_READ32, iend, matchEnd, lowPrefixPtr) + EQUAL_READ32;

  1076                 while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; }   /* catch up */

  1077                 offset = current - matchIndex;

  1078                 offset_2 = offset_1;

  1079                 offset_1 = offset;

  1080                 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);

  1081         }   }

  1082 

  1083         /* found a match : store it */

  1084         ip += mLength;

  1085         anchor = ip;

  1086 

  1087         if (ip <= ilimit) {

  1088             /* Fill Table */

  1089             hashTable[ZSTD_hashPtr(base+current+2, hBits, mls)] = current+2;

  1090             hashTable[ZSTD_hashPtr(ip-2, hBits, mls)] = (U32)(ip-2-base);

  1091             /* check immediate repcode */

  1092             while (ip <= ilimit) {

  1093                 U32 const current2 = (U32)(ip-base);

  1094                 U32 const repIndex2 = current2 - offset_2;

  1095                 const BYTE* repMatch2 = repIndex2 < dictLimit ? dictBase + repIndex2 : base + repIndex2;

  1096                 if ( (((U32)((dictLimit-1) - repIndex2) >= 3) & (repIndex2 > lowestIndex))  /* intentional overflow */

  1097                    && (MEM_read32(repMatch2) == MEM_read32(ip)) ) {

  1098                     const BYTE* const repEnd2 = repIndex2 < dictLimit ? dictEnd : iend;

  1099                     size_t repLength2 = ZSTD_count_2segments(ip+EQUAL_READ32, repMatch2+EQUAL_READ32, iend, repEnd2, lowPrefixPtr) + EQUAL_READ32;

  1100                     U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset;   /* swap offset_2 <=> offset_1 */

  1101                     ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, repLength2-MINMATCH);

  1102                     hashTable[ZSTD_hashPtr(ip, hBits, mls)] = current2;

  1103                     ip += repLength2;

  1104                     anchor = ip;

  1105                     continue;

  1106                 }

  1107                 break;

  1108     }   }   }

  1109 

  1110     /* save reps for next block */

  1111     ctx->savedRep[0] = offset_1; ctx->savedRep[1] = offset_2;

  1112 

  1113     /* Last Literals */

  1114     {   size_t const lastLLSize = iend - anchor;

  1115         memcpy(seqStorePtr->lit, anchor, lastLLSize);

  1116         seqStorePtr->lit += lastLLSize;

  1117     }

  1118 }

  1119 

  1120 

  1121 static void ZSTD_compressBlock_fast_extDict(ZSTD_CCtx* ctx,

  1122                          const void* src, size_t srcSize)

  1123 {

  1124     U32 const mls = ctx->params.cParams.searchLength;

  1125     switch(mls)

  1126     {

  1127     default:

  1128     case 4 :

  1129         ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 4); return;

  1130     case 5 :

  1131         ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 5); return;

  1132     case 6 :

  1133         ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 6); return;

  1134     case 7 :

  1135         ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 7); return;