contrib/zstd/lib/compress/zstd_compress.c

   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 FSE_STATIC_LINKING_ONLY   /* FSE_encodeSymbol */
  17 #include "fse.h"
  18 #define HUF_STATIC_LINKING_ONLY
  19 #include "huf.h"
  20 #include "zstd_internal.h"  /* includes zstd.h */
  21
  22
  23 /*-*************************************
  24 *  Debug
  25 ***************************************/
  26 #if defined(ZSTD_DEBUG) && (ZSTD_DEBUG>=1)
  27 #  include <assert.h>
  28 #else
  29 #  define assert(condition) ((void)0)
  30 #endif
  31
  32 #define ZSTD_STATIC_ASSERT(c) { enum { ZSTD_static_assert = 1/(int)(!!(c)) }; }
  33
  34 #if defined(ZSTD_DEBUG) && (ZSTD_DEBUG>=2)
  35 #  include <stdio.h>
  36    static unsigned g_debugLevel = ZSTD_DEBUG;
  37 #  define DEBUGLOG(l, ...) if (l<=g_debugLevel) { fprintf(stderr, __FILE__ ": "); fprintf(stderr, __VA_ARGS__); fprintf(stderr, " \n"); }
  38 #else
  39 #  define DEBUGLOG(l, ...)      {}    /* disabled */
  40 #endif
  41
  42
  43 /*-*************************************
  44 *  Constants
  45 ***************************************/
  46 static const U32 g_searchStrength = 8;   /* control skip over incompressible data */
  47 #define HASH_READ_SIZE 8
  48 typedef enum { ZSTDcs_created=0, ZSTDcs_init, ZSTDcs_ongoing, ZSTDcs_ending } ZSTD_compressionStage_e;
  49
  50 /* entropy tables always have same size */
  51 static size_t const hufCTable_size = HUF_CTABLE_SIZE(255);
  52 static size_t const litlengthCTable_size = FSE_CTABLE_SIZE(LLFSELog, MaxLL);
  53 static size_t const offcodeCTable_size = FSE_CTABLE_SIZE(OffFSELog, MaxOff);
  54 static size_t const matchlengthCTable_size = FSE_CTABLE_SIZE(MLFSELog, MaxML);
  55 static size_t const entropyScratchSpace_size = HUF_WORKSPACE_SIZE;
  56
  57
  58 /*-*************************************
  59 *  Helper functions
  60 ***************************************/
  61 size_t ZSTD_compressBound(size_t srcSize) {
  62     size_t const lowLimit = 256 KB;
  63     size_t const margin = (srcSize < lowLimit) ? (lowLimit-srcSize) >> 12 : 0;  /* from 64 to 0 */
  64     return srcSize + (srcSize >> 8) + margin;
  65 }
  66
  67
  68 /*-*************************************
  69 *  Sequence storage
  70 ***************************************/
  71 static void ZSTD_resetSeqStore(seqStore_t* ssPtr)
  72 {
  73     ssPtr->lit = ssPtr->litStart;
  74     ssPtr->sequences = ssPtr->sequencesStart;
  75     ssPtr->longLengthID = 0;
  76 }
  77
  78
  79 /*-*************************************
  80 *  Context memory management
  81 ***************************************/
  82 struct ZSTD_CCtx_s {
  83     const BYTE* nextSrc;    /* next block here to continue on current prefix */
  84     const BYTE* base;       /* All regular indexes relative to this position */
  85     const BYTE* dictBase;   /* extDict indexes relative to this position */
  86     U32   dictLimit;        /* below that point, need extDict */
  87     U32   lowLimit;         /* below that point, no more data */
  88     U32   nextToUpdate;     /* index from which to continue dictionary update */
  89     U32   nextToUpdate3;    /* index from which to continue dictionary update */
  90     U32   hashLog3;         /* dispatch table : larger == faster, more memory */
  91     U32   loadedDictEnd;    /* index of end of dictionary */
  92     U32   forceWindow;      /* force back-references to respect limit of 1<<wLog, even for dictionary */
  93     U32   forceRawDict;     /* Force loading dictionary in "content-only" mode (no header analysis) */
  94     ZSTD_compressionStage_e stage;
  95     U32   rep[ZSTD_REP_NUM];
  96     U32   repToConfirm[ZSTD_REP_NUM];
  97     U32   dictID;
  98     ZSTD_parameters params;
  99     void* workSpace;
 100     size_t workSpaceSize;
 101     size_t blockSize;
 102     U64 frameContentSize;
 103     U64 consumedSrcSize;
 104     XXH64_state_t xxhState;
 105     ZSTD_customMem customMem;
 106
 107     seqStore_t seqStore;    /* sequences storage ptrs */
 108     U32* hashTable;
 109     U32* hashTable3;
 110     U32* chainTable;
 111     HUF_repeat hufCTable_repeatMode;
 112     HUF_CElt* hufCTable;
 113     U32 fseCTables_ready;
 114     FSE_CTable* offcodeCTable;
 115     FSE_CTable* matchlengthCTable;
 116     FSE_CTable* litlengthCTable;
 117     unsigned* entropyScratchSpace;
 118 };
 119
 120 ZSTD_CCtx* ZSTD_createCCtx(void)
 121 {
 122     return ZSTD_createCCtx_advanced(defaultCustomMem);
 123 }
 124
 125 ZSTD_CCtx* ZSTD_createCCtx_advanced(ZSTD_customMem customMem)
 126 {
 127     ZSTD_CCtx* cctx;
 128
 129     if (!customMem.customAlloc && !customMem.customFree) customMem = defaultCustomMem;
 130     if (!customMem.customAlloc || !customMem.customFree) return NULL;
 131
 132     cctx = (ZSTD_CCtx*) ZSTD_malloc(sizeof(ZSTD_CCtx), customMem);
 133     if (!cctx) return NULL;
 134     memset(cctx, 0, sizeof(ZSTD_CCtx));
 135     cctx->customMem = customMem;
 136     return cctx;
 137 }
 138
 139 size_t ZSTD_freeCCtx(ZSTD_CCtx* cctx)
 140 {
 141     if (cctx==NULL) return 0;   /* support free on NULL */
 142     ZSTD_free(cctx->workSpace, cctx->customMem);
 143     ZSTD_free(cctx, cctx->customMem);
 144     return 0;   /* reserved as a potential error code in the future */
 145 }
 146
 147 size_t ZSTD_sizeof_CCtx(const ZSTD_CCtx* cctx)
 148 {
 149     if (cctx==NULL) return 0;   /* support sizeof on NULL */
 150     return sizeof(*cctx) + cctx->workSpaceSize;
 151 }
 152
 153 size_t ZSTD_setCCtxParameter(ZSTD_CCtx* cctx, ZSTD_CCtxParameter param, unsigned value)
 154 {
 155     switch(param)
 156     {
 157     case ZSTD_p_forceWindow : cctx->forceWindow = value>0; cctx->loadedDictEnd = 0; return 0;
 158     case ZSTD_p_forceRawDict : cctx->forceRawDict = value>0; return 0;
 159     default: return ERROR(parameter_unknown);
 160     }
 161 }
 162
 163 const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx)   /* hidden interface */
 164 {
 165     return &(ctx->seqStore);
 166 }
 167
 168 static ZSTD_parameters ZSTD_getParamsFromCCtx(const ZSTD_CCtx* cctx)
 169 {
 170     return cctx->params;
 171 }
 172
 173
 174 /** ZSTD_checkParams() :
 175     ensure param values remain within authorized range.
 176     @return : 0, or an error code if one value is beyond authorized range */
 177 size_t ZSTD_checkCParams(ZSTD_compressionParameters cParams)
 178 {
 179 #   define CLAMPCHECK(val,min,max) { if ((val<min) | (val>max)) return ERROR(compressionParameter_unsupported); }
 180     CLAMPCHECK(cParams.windowLog, ZSTD_WINDOWLOG_MIN, ZSTD_WINDOWLOG_MAX);
 181     CLAMPCHECK(cParams.chainLog, ZSTD_CHAINLOG_MIN, ZSTD_CHAINLOG_MAX);
 182     CLAMPCHECK(cParams.hashLog, ZSTD_HASHLOG_MIN, ZSTD_HASHLOG_MAX);
 183     CLAMPCHECK(cParams.searchLog, ZSTD_SEARCHLOG_MIN, ZSTD_SEARCHLOG_MAX);
 184     CLAMPCHECK(cParams.searchLength, ZSTD_SEARCHLENGTH_MIN, ZSTD_SEARCHLENGTH_MAX);
 185     CLAMPCHECK(cParams.targetLength, ZSTD_TARGETLENGTH_MIN, ZSTD_TARGETLENGTH_MAX);
 186     if ((U32)(cParams.strategy) > (U32)ZSTD_btopt2) return ERROR(compressionParameter_unsupported);
 187     return 0;
 188 }
 189
 190
 191 /** ZSTD_cycleLog() :
 192  *  condition for correct operation : hashLog > 1 */
 193 static U32 ZSTD_cycleLog(U32 hashLog, ZSTD_strategy strat)
 194 {
 195     U32 const btScale = ((U32)strat >= (U32)ZSTD_btlazy2);
 196     return hashLog - btScale;
 197 }
 198
 199 /** ZSTD_adjustCParams() :
 200     optimize `cPar` for a given input (`srcSize` and `dictSize`).
 201     mostly downsizing to reduce memory consumption and initialization.
 202     Both `srcSize` and `dictSize` are optional (use 0 if unknown),
 203     but if both are 0, no optimization can be done.
 204     Note : cPar is considered validated at this stage. Use ZSTD_checkParams() to ensure that. */
 205 ZSTD_compressionParameters ZSTD_adjustCParams(ZSTD_compressionParameters cPar, unsigned long long srcSize, size_t dictSize)
 206 {
 207     if (srcSize+dictSize == 0) return cPar;   /* no size information available : no adjustment */
 208
 209     /* resize params, to use less memory when necessary */
 210     {   U32 const minSrcSize = (srcSize==0) ? 500 : 0;
 211         U64 const rSize = srcSize + dictSize + minSrcSize;
 212         if (rSize < ((U64)1<<ZSTD_WINDOWLOG_MAX)) {
 213             U32 const srcLog = MAX(ZSTD_HASHLOG_MIN, ZSTD_highbit32((U32)(rSize)-1) + 1);
 214             if (cPar.windowLog > srcLog) cPar.windowLog = srcLog;
 215     }   }
 216     if (cPar.hashLog > cPar.windowLog) cPar.hashLog = cPar.windowLog;
 217     {   U32 const cycleLog = ZSTD_cycleLog(cPar.chainLog, cPar.strategy);
 218         if (cycleLog > cPar.windowLog) cPar.chainLog -= (cycleLog - cPar.windowLog);
 219     }
 220
 221     if (cPar.windowLog < ZSTD_WINDOWLOG_ABSOLUTEMIN) cPar.windowLog = ZSTD_WINDOWLOG_ABSOLUTEMIN;  /* required for frame header */
 222
 223     return cPar;
 224 }
 225
 226
 227 size_t ZSTD_estimateCCtxSize(ZSTD_compressionParameters cParams)
 228 {
 229     size_t const blockSize = MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, (size_t)1 << cParams.windowLog);
 230     U32    const divider = (cParams.searchLength==3) ? 3 : 4;
 231     size_t const maxNbSeq = blockSize / divider;
 232     size_t const tokenSpace = blockSize + 11*maxNbSeq;
 233
 234     size_t const chainSize = (cParams.strategy == ZSTD_fast) ? 0 : (1 << cParams.chainLog);
 235     size_t const hSize = ((size_t)1) << cParams.hashLog;
 236     U32    const hashLog3 = (cParams.searchLength>3) ? 0 : MIN(ZSTD_HASHLOG3_MAX, cParams.windowLog);
 237     size_t const h3Size = ((size_t)1) << hashLog3;
 238     size_t const entropySpace = hufCTable_size + litlengthCTable_size
 239                               + offcodeCTable_size + matchlengthCTable_size
 240                               + entropyScratchSpace_size;
 241     size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32);
 242
 243     size_t const optSpace = ((MaxML+1) + (MaxLL+1) + (MaxOff+1) + (1<<Litbits))*sizeof(U32)
 244                           + (ZSTD_OPT_NUM+1)*(sizeof(ZSTD_match_t) + sizeof(ZSTD_optimal_t));
 245     size_t const neededSpace = entropySpace + tableSpace + tokenSpace
 246                              + (((cParams.strategy == ZSTD_btopt) || (cParams.strategy == ZSTD_btopt2)) ? optSpace : 0);
 247
 248     return sizeof(ZSTD_CCtx) + neededSpace;
 249 }
 250
 251
 252 static U32 ZSTD_equivalentParams(ZSTD_parameters param1, ZSTD_parameters param2)
 253 {
 254     return (param1.cParams.hashLog  == param2.cParams.hashLog)
 255          & (param1.cParams.chainLog == param2.cParams.chainLog)
 256          & (param1.cParams.strategy == param2.cParams.strategy)
 257          & ((param1.cParams.searchLength==3) == (param2.cParams.searchLength==3));
 258 }
 259
 260 /*! ZSTD_continueCCtx() :
 261     reuse CCtx without reset (note : requires no dictionary) */
 262 static size_t ZSTD_continueCCtx(ZSTD_CCtx* cctx, ZSTD_parameters params, U64 frameContentSize)
 263 {
 264     U32 const end = (U32)(cctx->nextSrc - cctx->base);
 265     cctx->params = params;
 266     cctx->frameContentSize = frameContentSize;
 267     cctx->consumedSrcSize = 0;
 268     cctx->lowLimit = end;
 269     cctx->dictLimit = end;
 270     cctx->nextToUpdate = end+1;
 271     cctx->stage = ZSTDcs_init;
 272     cctx->dictID = 0;
 273     cctx->loadedDictEnd = 0;
 274     { int i; for (i=0; i<ZSTD_REP_NUM; i++) cctx->rep[i] = repStartValue[i]; }
 275     cctx->seqStore.litLengthSum = 0;  /* force reset of btopt stats */
 276     XXH64_reset(&cctx->xxhState, 0);
 277     return 0;
 278 }
 279
 280 typedef enum { ZSTDcrp_continue, ZSTDcrp_noMemset, ZSTDcrp_fullReset } ZSTD_compResetPolicy_e;
 281
 282 /*! ZSTD_resetCCtx_internal() :
 283     note : `params` must be validated */
 284 static size_t ZSTD_resetCCtx_internal (ZSTD_CCtx* zc,
 285                                        ZSTD_parameters params, U64 frameContentSize,
 286                                        ZSTD_compResetPolicy_e const crp)
 287 {
 288     if (crp == ZSTDcrp_continue)
 289         if (ZSTD_equivalentParams(params, zc->params)) {
 290             zc->fseCTables_ready = 0;
 291             zc->hufCTable_repeatMode = HUF_repeat_none;
 292             return ZSTD_continueCCtx(zc, params, frameContentSize);
 293         }
 294
 295     {   size_t const blockSize = MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, (size_t)1 << params.cParams.windowLog);
 296         U32    const divider = (params.cParams.searchLength==3) ? 3 : 4;
 297         size_t const maxNbSeq = blockSize / divider;
 298         size_t const tokenSpace = blockSize + 11*maxNbSeq;
 299         size_t const chainSize = (params.cParams.strategy == ZSTD_fast) ? 0 : (1 << params.cParams.chainLog);
 300         size_t const hSize = ((size_t)1) << params.cParams.hashLog;
 301         U32    const hashLog3 = (params.cParams.searchLength>3) ? 0 : MIN(ZSTD_HASHLOG3_MAX, params.cParams.windowLog);
 302         size_t const h3Size = ((size_t)1) << hashLog3;
 303         size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32);
 304         void* ptr;
 305
 306         /* Check if workSpace is large enough, alloc a new one if needed */
 307         {   size_t const entropySpace = hufCTable_size + litlengthCTable_size
 308                                   + offcodeCTable_size + matchlengthCTable_size
 309                                   + entropyScratchSpace_size;
 310             size_t const optPotentialSpace = ((MaxML+1) + (MaxLL+1) + (MaxOff+1) + (1<<Litbits)) * sizeof(U32)
 311                                   + (ZSTD_OPT_NUM+1) * (sizeof(ZSTD_match_t)+sizeof(ZSTD_optimal_t));
 312             size_t const optSpace = ((params.cParams.strategy == ZSTD_btopt) || (params.cParams.strategy == ZSTD_btopt2)) ? optPotentialSpace : 0;
 313             size_t const neededSpace = entropySpace + optSpace + tableSpace + tokenSpace;
 314             if (zc->workSpaceSize < neededSpace) {
 315                 zc->workSpaceSize = 0;
 316                 ZSTD_free(zc->workSpace, zc->customMem);
 317                 zc->workSpace = ZSTD_malloc(neededSpace, zc->customMem);
 318                 if (zc->workSpace == NULL) return ERROR(memory_allocation);
 319                 zc->workSpaceSize = neededSpace;
 320                 ptr = zc->workSpace;
 321
 322                 /* entropy space */
 323                 zc->hufCTable = (HUF_CElt*)ptr;
 324                 ptr = (char*)zc->hufCTable + hufCTable_size;  /* note : HUF_CElt* is incomplete type, size is estimated via macro */
 325                 zc->offcodeCTable = (FSE_CTable*) ptr;
 326                 ptr = (char*)ptr + offcodeCTable_size;
 327                 zc->matchlengthCTable = (FSE_CTable*) ptr;
 328                 ptr = (char*)ptr + matchlengthCTable_size;
 329                 zc->litlengthCTable = (FSE_CTable*) ptr;
 330                 ptr = (char*)ptr + litlengthCTable_size;
 331                 assert(((size_t)ptr & 3) == 0);   /* ensure correct alignment */
 332                 zc->entropyScratchSpace = (unsigned*) ptr;
 333         }   }
 334
 335         /* init params */
 336         zc->params = params;
 337         zc->blockSize = blockSize;
 338         zc->frameContentSize = frameContentSize;
 339         zc->consumedSrcSize = 0;
 340
 341         XXH64_reset(&zc->xxhState, 0);
 342         zc->stage = ZSTDcs_init;
 343         zc->dictID = 0;
 344         zc->loadedDictEnd = 0;
 345         zc->fseCTables_ready = 0;
 346         zc->hufCTable_repeatMode = HUF_repeat_none;
 347         zc->nextToUpdate = 1;
 348         zc->nextSrc = NULL;
 349         zc->base = NULL;
 350         zc->dictBase = NULL;
 351         zc->dictLimit = 0;
 352         zc->lowLimit = 0;
 353         { int i; for (i=0; i<ZSTD_REP_NUM; i++) zc->rep[i] = repStartValue[i]; }
 354         zc->hashLog3 = hashLog3;
 355         zc->seqStore.litLengthSum = 0;
 356
 357         /* ensure entropy tables are close together at the beginning */
 358         assert((void*)zc->hufCTable == zc->workSpace);
 359         assert((char*)zc->offcodeCTable == (char*)zc->hufCTable + hufCTable_size);
 360         assert((char*)zc->matchlengthCTable == (char*)zc->offcodeCTable + offcodeCTable_size);
 361         assert((char*)zc->litlengthCTable == (char*)zc->matchlengthCTable + matchlengthCTable_size);
 362         assert((char*)zc->entropyScratchSpace == (char*)zc->litlengthCTable + litlengthCTable_size);
 363         ptr = (char*)zc->entropyScratchSpace + entropyScratchSpace_size;
 364
 365         /* opt parser space */
 366         if ((params.cParams.strategy == ZSTD_btopt) || (params.cParams.strategy == ZSTD_btopt2)) {
 367             assert(((size_t)ptr & 3) == 0);  /* ensure ptr is properly aligned */
 368             zc->seqStore.litFreq = (U32*)ptr;
 369             zc->seqStore.litLengthFreq = zc->seqStore.litFreq + (1<<Litbits);
 370             zc->seqStore.matchLengthFreq = zc->seqStore.litLengthFreq + (MaxLL+1);
 371             zc->seqStore.offCodeFreq = zc->seqStore.matchLengthFreq + (MaxML+1);
 372             ptr = zc->seqStore.offCodeFreq + (MaxOff+1);
 373             zc->seqStore.matchTable = (ZSTD_match_t*)ptr;
 374             ptr = zc->seqStore.matchTable + ZSTD_OPT_NUM+1;
 375             zc->seqStore.priceTable = (ZSTD_optimal_t*)ptr;
 376             ptr = zc->seqStore.priceTable + ZSTD_OPT_NUM+1;
 377         }
 378
 379         /* table Space */
 380         if (crp!=ZSTDcrp_noMemset) memset(ptr, 0, tableSpace);   /* reset tables only */
 381         assert(((size_t)ptr & 3) == 0);  /* ensure ptr is properly aligned */
 382         zc->hashTable = (U32*)(ptr);
 383         zc->chainTable = zc->hashTable + hSize;
 384         zc->hashTable3 = zc->chainTable + chainSize;
 385         ptr = zc->hashTable3 + h3Size;
 386
 387         /* sequences storage */
 388         zc->seqStore.sequencesStart = (seqDef*)ptr;
 389         ptr = zc->seqStore.sequencesStart + maxNbSeq;
 390         zc->seqStore.llCode = (BYTE*) ptr;
 391         zc->seqStore.mlCode = zc->seqStore.llCode + maxNbSeq;
 392         zc->seqStore.ofCode = zc->seqStore.mlCode + maxNbSeq;
 393         zc->seqStore.litStart = zc->seqStore.ofCode + maxNbSeq;
 394
 395         return 0;
 396     }
 397 }
 398
 399 /* ZSTD_invalidateRepCodes() :
 400  * ensures next compression will not use repcodes from previous block.
 401  * Note : only works with regular variant;
 402  *        do not use with extDict variant ! */
 403 void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx) {
 404     int i;
 405     for (i=0; i<ZSTD_REP_NUM; i++) cctx->rep[i] = 0;
 406 }
 407
 408
 409 /*! ZSTD_copyCCtx_internal() :
 410  *  Duplicate an existing context `srcCCtx` into another one `dstCCtx`.
 411  *  Only works during stage ZSTDcs_init (i.e. after creation, but before first call to ZSTD_compressContinue()).
 412  *  pledgedSrcSize=0 means "empty" if fParams.contentSizeFlag=1
 413  *  @return : 0, or an error code */
 414 size_t ZSTD_copyCCtx_internal(ZSTD_CCtx* dstCCtx, const ZSTD_CCtx* srcCCtx,
 415                               ZSTD_frameParameters fParams, unsigned long long pledgedSrcSize)
 416 {
 417     if (srcCCtx->stage!=ZSTDcs_init) return ERROR(stage_wrong);
 418
 419     memcpy(&dstCCtx->customMem, &srcCCtx->customMem, sizeof(ZSTD_customMem));
 420     {   ZSTD_parameters params = srcCCtx->params;
 421         params.fParams = fParams;
 422         DEBUGLOG(5, "ZSTD_resetCCtx_internal : dictIDFlag : %u \n", !fParams.noDictIDFlag);
 423         ZSTD_resetCCtx_internal(dstCCtx, params, pledgedSrcSize, ZSTDcrp_noMemset);
 424     }
 425
 426     /* copy tables */
 427     {   size_t const chainSize = (srcCCtx->params.cParams.strategy == ZSTD_fast) ? 0 : (1 << srcCCtx->params.cParams.chainLog);
 428         size_t const hSize =  (size_t)1 << srcCCtx->params.cParams.hashLog;
 429         size_t const h3Size = (size_t)1 << srcCCtx->hashLog3;
 430         size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32);
 431         assert((U32*)dstCCtx->chainTable == (U32*)dstCCtx->hashTable + hSize);  /* chainTable must follow hashTable */
 432         assert((U32*)dstCCtx->hashTable3 == (U32*)dstCCtx->chainTable + chainSize);
 433         memcpy(dstCCtx->hashTable, srcCCtx->hashTable, tableSpace);   /* presumes all tables follow each other */
 434     }
 435
 436     /* copy dictionary offsets */
 437     dstCCtx->nextToUpdate = srcCCtx->nextToUpdate;
 438     dstCCtx->nextToUpdate3= srcCCtx->nextToUpdate3;
 439     dstCCtx->nextSrc      = srcCCtx->nextSrc;
 440     dstCCtx->base         = srcCCtx->base;
 441     dstCCtx->dictBase     = srcCCtx->dictBase;
 442     dstCCtx->dictLimit    = srcCCtx->dictLimit;
 443     dstCCtx->lowLimit     = srcCCtx->lowLimit;
 444     dstCCtx->loadedDictEnd= srcCCtx->loadedDictEnd;
 445     dstCCtx->dictID       = srcCCtx->dictID;
 446
 447     /* copy entropy tables */
 448     dstCCtx->fseCTables_ready = srcCCtx->fseCTables_ready;
 449     if (srcCCtx->fseCTables_ready) {
 450         memcpy(dstCCtx->litlengthCTable, srcCCtx->litlengthCTable, litlengthCTable_size);
 451         memcpy(dstCCtx->matchlengthCTable, srcCCtx->matchlengthCTable, matchlengthCTable_size);
 452         memcpy(dstCCtx->offcodeCTable, srcCCtx->offcodeCTable, offcodeCTable_size);
 453     }
 454     dstCCtx->hufCTable_repeatMode = srcCCtx->hufCTable_repeatMode;
 455     if (srcCCtx->hufCTable_repeatMode) {
 456         memcpy(dstCCtx->hufCTable, srcCCtx->hufCTable, hufCTable_size);
 457     }
 458
 459     return 0;
 460 }
 461
 462 /*! ZSTD_copyCCtx() :
 463  *  Duplicate an existing context `srcCCtx` into another one `dstCCtx`.
 464  *  Only works during stage ZSTDcs_init (i.e. after creation, but before first call to ZSTD_compressContinue()).
 465  *  pledgedSrcSize==0 means "unknown".
 466 *   @return : 0, or an error code */
 467 size_t ZSTD_copyCCtx(ZSTD_CCtx* dstCCtx, const ZSTD_CCtx* srcCCtx, unsigned long long pledgedSrcSize)
 468 {
 469     ZSTD_frameParameters fParams = { 1 /*content*/, 0 /*checksum*/, 0 /*noDictID*/ };
 470     fParams.contentSizeFlag = pledgedSrcSize>0;
 471
 472     return ZSTD_copyCCtx_internal(dstCCtx, srcCCtx, fParams, pledgedSrcSize);
 473 }
 474
 475
 476 /*! ZSTD_reduceTable() :
 477  *  reduce table indexes by `reducerValue` */
 478 static void ZSTD_reduceTable (U32* const table, U32 const size, U32 const reducerValue)
 479 {
 480     U32 u;
 481     for (u=0 ; u < size ; u++) {
 482         if (table[u] < reducerValue) table[u] = 0;
 483         else table[u] -= reducerValue;
 484     }
 485 }
 486
 487 /*! ZSTD_reduceIndex() :
 488 *   rescale all indexes to avoid future overflow (indexes are U32) */
 489 static void ZSTD_reduceIndex (ZSTD_CCtx* zc, const U32 reducerValue)
 490 {
 491     { U32 const hSize = 1 << zc->params.cParams.hashLog;
 492       ZSTD_reduceTable(zc->hashTable, hSize, reducerValue); }
 493
 494     { U32 const chainSize = (zc->params.cParams.strategy == ZSTD_fast) ? 0 : (1 << zc->params.cParams.chainLog);
 495       ZSTD_reduceTable(zc->chainTable, chainSize, reducerValue); }
 496
 497     { U32 const h3Size = (zc->hashLog3) ? 1 << zc->hashLog3 : 0;
 498       ZSTD_reduceTable(zc->hashTable3, h3Size, reducerValue); }
 499 }
 500
 501
 502 /*-*******************************************************
 503 *  Block entropic compression
 504 *********************************************************/
 505
 506 /* See doc/zstd_compression_format.md for detailed format description */
 507
 508 size_t ZSTD_noCompressBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
 509 {
 510     if (srcSize + ZSTD_blockHeaderSize > dstCapacity) return ERROR(dstSize_tooSmall);
 511     memcpy((BYTE*)dst + ZSTD_blockHeaderSize, src, srcSize);
 512     MEM_writeLE24(dst, (U32)(srcSize << 2) + (U32)bt_raw);
 513     return ZSTD_blockHeaderSize+srcSize;
 514 }
 515
 516
 517 static size_t ZSTD_noCompressLiterals (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
 518 {
 519     BYTE* const ostart = (BYTE* const)dst;
 520     U32   const flSize = 1 + (srcSize>31) + (srcSize>4095);
 521
 522     if (srcSize + flSize > dstCapacity) return ERROR(dstSize_tooSmall);
 523
 524     switch(flSize)
 525     {
 526         case 1: /* 2 - 1 - 5 */
 527             ostart[0] = (BYTE)((U32)set_basic + (srcSize<<3));
 528             break;
 529         case 2: /* 2 - 2 - 12 */
 530             MEM_writeLE16(ostart, (U16)((U32)set_basic + (1<<2) + (srcSize<<4)));
 531             break;
 532         default:   /*note : should not be necessary : flSize is within {1,2,3} */
 533         case 3: /* 2 - 2 - 20 */
 534             MEM_writeLE32(ostart, (U32)((U32)set_basic + (3<<2) + (srcSize<<4)));
 535             break;
 536     }
 537
 538     memcpy(ostart + flSize, src, srcSize);
 539     return srcSize + flSize;
 540 }
 541
 542 static size_t ZSTD_compressRleLiteralsBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
 543 {
 544     BYTE* const ostart = (BYTE* const)dst;
 545     U32   const flSize = 1 + (srcSize>31) + (srcSize>4095);
 546
 547     (void)dstCapacity;  /* dstCapacity already guaranteed to be >=4, hence large enough */
 548
 549     switch(flSize)
 550     {
 551         case 1: /* 2 - 1 - 5 */
 552             ostart[0] = (BYTE)((U32)set_rle + (srcSize<<3));
 553             break;
 554         case 2: /* 2 - 2 - 12 */
 555             MEM_writeLE16(ostart, (U16)((U32)set_rle + (1<<2) + (srcSize<<4)));
 556             break;
 557         default:   /*note : should not be necessary : flSize is necessarily within {1,2,3} */
 558         case 3: /* 2 - 2 - 20 */
 559             MEM_writeLE32(ostart, (U32)((U32)set_rle + (3<<2) + (srcSize<<4)));
 560             break;
 561     }
 562
 563     ostart[flSize] = *(const BYTE*)src;
 564     return flSize+1;
 565 }
 566
 567
 568 static size_t ZSTD_minGain(size_t srcSize) { return (srcSize >> 6) + 2; }
 569
 570 static size_t ZSTD_compressLiterals (ZSTD_CCtx* zc,
 571                                      void* dst, size_t dstCapacity,
 572                                const void* src, size_t srcSize)
 573 {
 574     size_t const minGain = ZSTD_minGain(srcSize);
 575     size_t const lhSize = 3 + (srcSize >= 1 KB) + (srcSize >= 16 KB);
 576     BYTE*  const ostart = (BYTE*)dst;
 577     U32 singleStream = srcSize < 256;
 578     symbolEncodingType_e hType = set_compressed;
 579     size_t cLitSize;
 580
 581
 582     /* small ? don't even attempt compression (speed opt) */
 583 #   define LITERAL_NOENTROPY 63
 584     {   size_t const minLitSize = zc->hufCTable_repeatMode == HUF_repeat_valid ? 6 : LITERAL_NOENTROPY;
 585         if (srcSize <= minLitSize) return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
 586     }
 587
 588     if (dstCapacity < lhSize+1) return ERROR(dstSize_tooSmall);   /* not enough space for compression */
 589     {   HUF_repeat repeat = zc->hufCTable_repeatMode;
 590         int const preferRepeat = zc->params.cParams.strategy < ZSTD_lazy ? srcSize <= 1024 : 0;
 591         if (repeat == HUF_repeat_valid && lhSize == 3) singleStream = 1;
 592         cLitSize = singleStream ? HUF_compress1X_repeat(ostart+lhSize, dstCapacity-lhSize, src, srcSize, 255, 11,
 593                                       zc->entropyScratchSpace, entropyScratchSpace_size, zc->hufCTable, &repeat, preferRepeat)
 594                                 : HUF_compress4X_repeat(ostart+lhSize, dstCapacity-lhSize, src, srcSize, 255, 11,
 595                                       zc->entropyScratchSpace, entropyScratchSpace_size, zc->hufCTable, &repeat, preferRepeat);
 596         if (repeat != HUF_repeat_none) { hType = set_repeat; }    /* reused the existing table */
 597         else { zc->hufCTable_repeatMode = HUF_repeat_check; }       /* now have a table to reuse */
 598     }
 599
 600     if ((cLitSize==0) | (cLitSize >= srcSize - minGain)) {
 601         zc->hufCTable_repeatMode = HUF_repeat_none;
 602         return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
 603     }
 604     if (cLitSize==1) {
 605         zc->hufCTable_repeatMode = HUF_repeat_none;
 606         return ZSTD_compressRleLiteralsBlock(dst, dstCapacity, src, srcSize);
 607     }
 608
 609     /* Build header */
 610     switch(lhSize)
 611     {
 612     case 3: /* 2 - 2 - 10 - 10 */
 613         {   U32 const lhc = hType + ((!singleStream) << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<14);
 614             MEM_writeLE24(ostart, lhc);
 615             break;
 616         }
 617     case 4: /* 2 - 2 - 14 - 14 */
 618         {   U32 const lhc = hType + (2 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<18);
 619             MEM_writeLE32(ostart, lhc);
 620             break;
 621         }
 622     default:   /* should not be necessary, lhSize is only {3,4,5} */
 623     case 5: /* 2 - 2 - 18 - 18 */
 624         {   U32 const lhc = hType + (3 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<22);
 625             MEM_writeLE32(ostart, lhc);
 626             ostart[4] = (BYTE)(cLitSize >> 10);
 627             break;
 628         }
 629     }
 630     return lhSize+cLitSize;
 631 }
 632
 633 static const BYTE LL_Code[64] = {  0,  1,  2,  3,  4,  5,  6,  7,
 634                                    8,  9, 10, 11, 12, 13, 14, 15,
 635                                   16, 16, 17, 17, 18, 18, 19, 19,
 636                                   20, 20, 20, 20, 21, 21, 21, 21,
 637                                   22, 22, 22, 22, 22, 22, 22, 22,
 638                                   23, 23, 23, 23, 23, 23, 23, 23,
 639                                   24, 24, 24, 24, 24, 24, 24, 24,
 640                                   24, 24, 24, 24, 24, 24, 24, 24 };
 641
 642 static const BYTE ML_Code[128] = { 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15,
 643                                   16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
 644                                   32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37,
 645                                   38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39,
 646                                   40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
 647                                   41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,
 648                                   42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
 649                                   42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42 };
 650
 651
 652 void ZSTD_seqToCodes(const seqStore_t* seqStorePtr)
 653 {
 654     BYTE const LL_deltaCode = 19;
 655     BYTE const ML_deltaCode = 36;
 656     const seqDef* const sequences = seqStorePtr->sequencesStart;
 657     BYTE* const llCodeTable = seqStorePtr->llCode;
 658     BYTE* const ofCodeTable = seqStorePtr->ofCode;
 659     BYTE* const mlCodeTable = seqStorePtr->mlCode;
 660     U32 const nbSeq = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
 661     U32 u;
 662     for (u=0; u<nbSeq; u++) {
 663         U32 const llv = sequences[u].litLength;
 664         U32 const mlv = sequences[u].matchLength;
 665         llCodeTable[u] = (llv> 63) ? (BYTE)ZSTD_highbit32(llv) + LL_deltaCode : LL_Code[llv];
 666         ofCodeTable[u] = (BYTE)ZSTD_highbit32(sequences[u].offset);
 667         mlCodeTable[u] = (mlv>127) ? (BYTE)ZSTD_highbit32(mlv) + ML_deltaCode : ML_Code[mlv];
 668     }
 669     if (seqStorePtr->longLengthID==1)
 670         llCodeTable[seqStorePtr->longLengthPos] = MaxLL;
 671     if (seqStorePtr->longLengthID==2)
 672         mlCodeTable[seqStorePtr->longLengthPos] = MaxML;
 673 }
 674
 675 MEM_STATIC size_t ZSTD_compressSequences (ZSTD_CCtx* zc,
 676                               void* dst, size_t dstCapacity,
 677                               size_t srcSize)
 678 {
 679     const int longOffsets = zc->params.cParams.windowLog > STREAM_ACCUMULATOR_MIN;
 680     const seqStore_t* seqStorePtr = &(zc->seqStore);
 681     U32 count[MaxSeq+1];
 682     S16 norm[MaxSeq+1];
 683     FSE_CTable* CTable_LitLength = zc->litlengthCTable;
 684     FSE_CTable* CTable_OffsetBits = zc->offcodeCTable;
 685     FSE_CTable* CTable_MatchLength = zc->matchlengthCTable;
 686     U32 LLtype, Offtype, MLtype;   /* compressed, raw or rle */
 687     const seqDef* const sequences = seqStorePtr->sequencesStart;
 688     const BYTE* const ofCodeTable = seqStorePtr->ofCode;
 689     const BYTE* const llCodeTable = seqStorePtr->llCode;
 690     const BYTE* const mlCodeTable = seqStorePtr->mlCode;
 691     BYTE* const ostart = (BYTE*)dst;
 692     BYTE* const oend = ostart + dstCapacity;
 693     BYTE* op = ostart;
 694     size_t const nbSeq = seqStorePtr->sequences - seqStorePtr->sequencesStart;
 695     BYTE* seqHead;
 696     BYTE scratchBuffer[1<<MAX(MLFSELog,LLFSELog)];
 697
 698     /* Compress literals */
 699     {   const BYTE* const literals = seqStorePtr->litStart;
 700         size_t const litSize = seqStorePtr->lit - literals;
 701         size_t const cSize = ZSTD_compressLiterals(zc, op, dstCapacity, literals, litSize);
 702         if (ZSTD_isError(cSize)) return cSize;
 703         op += cSize;
 704     }
 705
 706     /* Sequences Header */
 707     if ((oend-op) < 3 /*max nbSeq Size*/ + 1 /*seqHead */) return ERROR(dstSize_tooSmall);
 708     if (nbSeq < 0x7F) *op++ = (BYTE)nbSeq;
 709     else if (nbSeq < LONGNBSEQ) op[0] = (BYTE)((nbSeq>>8) + 0x80), op[1] = (BYTE)nbSeq, op+=2;
 710     else op[0]=0xFF, MEM_writeLE16(op+1, (U16)(nbSeq - LONGNBSEQ)), op+=3;
 711     if (nbSeq==0) goto _check_compressibility;
 712
 713     /* seqHead : flags for FSE encoding type */
 714     seqHead = op++;
 715
 716 #define MIN_SEQ_FOR_DYNAMIC_FSE   64
 717 #define MAX_SEQ_FOR_STATIC_FSE  1000
 718
 719     /* convert length/distances into codes */
 720     ZSTD_seqToCodes(seqStorePtr);
 721
 722     /* CTable for Literal Lengths */
 723     {   U32 max = MaxLL;
 724         size_t const mostFrequent = FSE_countFast_wksp(count, &max, llCodeTable, nbSeq, zc->entropyScratchSpace);
 725         if ((mostFrequent == nbSeq) && (nbSeq > 2)) {
 726             *op++ = llCodeTable[0];
 727             FSE_buildCTable_rle(CTable_LitLength, (BYTE)max);
 728             LLtype = set_rle;
 729         } else if ((zc->fseCTables_ready) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) {
 730             LLtype = set_repeat;
 731         } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (LL_defaultNormLog-1)))) {
 732             FSE_buildCTable_wksp(CTable_LitLength, LL_defaultNorm, MaxLL, LL_defaultNormLog, scratchBuffer, sizeof(scratchBuffer));
 733             LLtype = set_basic;
 734         } else {
 735             size_t nbSeq_1 = nbSeq;
 736             const U32 tableLog = FSE_optimalTableLog(LLFSELog, nbSeq, max);
 737             if (count[llCodeTable[nbSeq-1]]>1) { count[llCodeTable[nbSeq-1]]--; nbSeq_1--; }
 738             FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max);
 739             { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog);   /* overflow protected */
 740               if (FSE_isError(NCountSize)) return NCountSize;
 741               op += NCountSize; }
 742             FSE_buildCTable_wksp(CTable_LitLength, norm, max, tableLog, scratchBuffer, sizeof(scratchBuffer));
 743             LLtype = set_compressed;
 744     }   }
 745
 746     /* CTable for Offsets */
 747     {   U32 max = MaxOff;
 748         size_t const mostFrequent = FSE_countFast_wksp(count, &max, ofCodeTable, nbSeq, zc->entropyScratchSpace);
 749         if ((mostFrequent == nbSeq) && (nbSeq > 2)) {
 750             *op++ = ofCodeTable[0];
 751             FSE_buildCTable_rle(CTable_OffsetBits, (BYTE)max);
 752             Offtype = set_rle;
 753         } else if ((zc->fseCTables_ready) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) {
 754             Offtype = set_repeat;
 755         } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (OF_defaultNormLog-1)))) {
 756             FSE_buildCTable_wksp(CTable_OffsetBits, OF_defaultNorm, MaxOff, OF_defaultNormLog, scratchBuffer, sizeof(scratchBuffer));
 757             Offtype = set_basic;
 758         } else {
 759             size_t nbSeq_1 = nbSeq;
 760             const U32 tableLog = FSE_optimalTableLog(OffFSELog, nbSeq, max);
 761             if (count[ofCodeTable[nbSeq-1]]>1) { count[ofCodeTable[nbSeq-1]]--; nbSeq_1--; }
 762             FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max);
 763             { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog);   /* overflow protected */
 764               if (FSE_isError(NCountSize)) return NCountSize;
 765               op += NCountSize; }
 766             FSE_buildCTable_wksp(CTable_OffsetBits, norm, max, tableLog, scratchBuffer, sizeof(scratchBuffer));
 767             Offtype = set_compressed;
 768     }   }
 769
 770     /* CTable for MatchLengths */
 771     {   U32 max = MaxML;
 772         size_t const mostFrequent = FSE_countFast_wksp(count, &max, mlCodeTable, nbSeq, zc->entropyScratchSpace);
 773         if ((mostFrequent == nbSeq) && (nbSeq > 2)) {
 774             *op++ = *mlCodeTable;
 775             FSE_buildCTable_rle(CTable_MatchLength, (BYTE)max);
 776             MLtype = set_rle;
 777         } else if ((zc->fseCTables_ready) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) {
 778             MLtype = set_repeat;
 779         } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (ML_defaultNormLog-1)))) {
 780             FSE_buildCTable_wksp(CTable_MatchLength, ML_defaultNorm, MaxML, ML_defaultNormLog, scratchBuffer, sizeof(scratchBuffer));
 781             MLtype = set_basic;
 782         } else {
 783             size_t nbSeq_1 = nbSeq;
 784             const U32 tableLog = FSE_optimalTableLog(MLFSELog, nbSeq, max);
 785             if (count[mlCodeTable[nbSeq-1]]>1) { count[mlCodeTable[nbSeq-1]]--; nbSeq_1--; }
 786             FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max);
 787             { size_t const NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog);   /* overflow protected */
 788               if (FSE_isError(NCountSize)) return NCountSize;
 789               op += NCountSize; }
 790             FSE_buildCTable_wksp(CTable_MatchLength, norm, max, tableLog, scratchBuffer, sizeof(scratchBuffer));
 791             MLtype = set_compressed;
 792     }   }
 793
 794     *seqHead = (BYTE)((LLtype<<6) + (Offtype<<4) + (MLtype<<2));
 795     zc->fseCTables_ready = 0;
 796
 797     /* Encoding Sequences */
 798     {   BIT_CStream_t blockStream;
 799         FSE_CState_t  stateMatchLength;
 800         FSE_CState_t  stateOffsetBits;
 801         FSE_CState_t  stateLitLength;
 802
 803         CHECK_E(BIT_initCStream(&blockStream, op, oend-op), dstSize_tooSmall); /* not enough space remaining */
 804
 805         /* first symbols */
 806         FSE_initCState2(&stateMatchLength, CTable_MatchLength, mlCodeTable[nbSeq-1]);
 807         FSE_initCState2(&stateOffsetBits,  CTable_OffsetBits,  ofCodeTable[nbSeq-1]);
 808         FSE_initCState2(&stateLitLength,   CTable_LitLength,   llCodeTable[nbSeq-1]);
 809         BIT_addBits(&blockStream, sequences[nbSeq-1].litLength, LL_bits[llCodeTable[nbSeq-1]]);
 810         if (MEM_32bits()) BIT_flushBits(&blockStream);
 811         BIT_addBits(&blockStream, sequences[nbSeq-1].matchLength, ML_bits[mlCodeTable[nbSeq-1]]);
 812         if (MEM_32bits()) BIT_flushBits(&blockStream);
 813         if (longOffsets) {
 814             U32 const ofBits = ofCodeTable[nbSeq-1];
 815             int const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);
 816             if (extraBits) {
 817                 BIT_addBits(&blockStream, sequences[nbSeq-1].offset, extraBits);
 818                 BIT_flushBits(&blockStream);
 819             }
 820             BIT_addBits(&blockStream, sequences[nbSeq-1].offset >> extraBits,
 821                         ofBits - extraBits);
 822         } else {
 823             BIT_addBits(&blockStream, sequences[nbSeq-1].offset, ofCodeTable[nbSeq-1]);
 824         }
 825         BIT_flushBits(&blockStream);
 826
 827         {   size_t n;
 828             for (n=nbSeq-2 ; n<nbSeq ; n--) {      /* intentional underflow */
 829                 BYTE const llCode = llCodeTable[n];
 830                 BYTE const ofCode = ofCodeTable[n];
 831                 BYTE const mlCode = mlCodeTable[n];
 832                 U32  const llBits = LL_bits[llCode];
 833                 U32  const ofBits = ofCode;                                     /* 32b*/  /* 64b*/
 834                 U32  const mlBits = ML_bits[mlCode];
 835                                                                                 /* (7)*/  /* (7)*/
 836                 FSE_encodeSymbol(&blockStream, &stateOffsetBits, ofCode);       /* 15 */  /* 15 */
 837                 FSE_encodeSymbol(&blockStream, &stateMatchLength, mlCode);      /* 24 */  /* 24 */
 838                 if (MEM_32bits()) BIT_flushBits(&blockStream);                  /* (7)*/
 839                 FSE_encodeSymbol(&blockStream, &stateLitLength, llCode);        /* 16 */  /* 33 */
 840                 if (MEM_32bits() || (ofBits+mlBits+llBits >= 64-7-(LLFSELog+MLFSELog+OffFSELog)))
 841                     BIT_flushBits(&blockStream);                                /* (7)*/
 842                 BIT_addBits(&blockStream, sequences[n].litLength, llBits);
 843                 if (MEM_32bits() && ((llBits+mlBits)>24)) BIT_flushBits(&blockStream);
 844                 BIT_addBits(&blockStream, sequences[n].matchLength, mlBits);
 845                 if (MEM_32bits()) BIT_flushBits(&blockStream);                  /* (7)*/
 846                 if (longOffsets) {
 847                     int const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);
 848                     if (extraBits) {
 849                         BIT_addBits(&blockStream, sequences[n].offset, extraBits);
 850                         BIT_flushBits(&blockStream);                            /* (7)*/
 851                     }
 852                     BIT_addBits(&blockStream, sequences[n].offset >> extraBits,
 853                                 ofBits - extraBits);                            /* 31 */
 854                 } else {
 855                     BIT_addBits(&blockStream, sequences[n].offset, ofBits);     /* 31 */
 856                 }
 857                 BIT_flushBits(&blockStream);                                    /* (7)*/
 858         }   }
 859
 860         FSE_flushCState(&blockStream, &stateMatchLength);
 861         FSE_flushCState(&blockStream, &stateOffsetBits);
 862         FSE_flushCState(&blockStream, &stateLitLength);
 863
 864         {   size_t const streamSize = BIT_closeCStream(&blockStream);
 865             if (streamSize==0) return ERROR(dstSize_tooSmall);   /* not enough space */
 866             op += streamSize;
 867     }   }
 868
 869     /* check compressibility */
 870 _check_compressibility:
 871     {   size_t const minGain = ZSTD_minGain(srcSize);
 872         size_t const maxCSize = srcSize - minGain;
 873         if ((size_t)(op-ostart) >= maxCSize) {
 874             zc->hufCTable_repeatMode = HUF_repeat_none;
 875             return 0;
 876     }   }
 877
 878     /* confirm repcodes */
 879     { int i; for (i=0; i<ZSTD_REP_NUM; i++) zc->rep[i] = zc->repToConfirm[i]; }
 880
 881     return op - ostart;
 882 }
 883
 884 #if 0 /* for debug */
 885 #  define STORESEQ_DEBUG
 886 #include <stdio.h>   /* fprintf */
 887 U32 g_startDebug = 0;
 888 const BYTE* g_start = NULL;
 889 #endif
 890
 891 /*! ZSTD_storeSeq() :
 892     Store a sequence (literal length, literals, offset code and match length code) into seqStore_t.
 893     `offsetCode` : distance to match, or 0 == repCode.
 894     `matchCode` : matchLength - MINMATCH
 895 */
 896 MEM_STATIC void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const void* literals, U32 offsetCode, size_t matchCode)
 897 {
 898 #ifdef STORESEQ_DEBUG
 899     if (g_startDebug) {
 900         const U32 pos = (U32)((const BYTE*)literals - g_start);
 901         if (g_start==NULL) g_start = (const BYTE*)literals;
 902         if ((pos > 1895000) && (pos < 1895300))
 903             DEBUGLOG(5, "Cpos %6u :%5u literals & match %3u bytes at distance %6u \n",
 904                    pos, (U32)litLength, (U32)matchCode+MINMATCH, (U32)offsetCode);
 905     }
 906 #endif
 907     /* copy Literals */
 908     ZSTD_wildcopy(seqStorePtr->lit, literals, litLength);
 909     seqStorePtr->lit += litLength;
 910
 911     /* literal Length */
 912     if (litLength>0xFFFF) {
 913         seqStorePtr->longLengthID = 1;
 914         seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
 915     }
 916     seqStorePtr->sequences[0].litLength = (U16)litLength;
 917
 918     /* match offset */
 919     seqStorePtr->sequences[0].offset = offsetCode + 1;
 920
 921     /* match Length */
 922     if (matchCode>0xFFFF) {
 923         seqStorePtr->longLengthID = 2;
 924         seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
 925     }
 926     seqStorePtr->sequences[0].matchLength = (U16)matchCode;
 927
 928     seqStorePtr->sequences++;
 929 }
 930
 931
 932 /*-*************************************
 933 *  Match length counter
 934 ***************************************/
 935 static unsigned ZSTD_NbCommonBytes (register size_t val)
 936 {
 937     if (MEM_isLittleEndian()) {
 938         if (MEM_64bits()) {
 939 #       if defined(_MSC_VER) && defined(_WIN64)
 940             unsigned long r = 0;
 941             _BitScanForward64( &r, (U64)val );
 942             return (unsigned)(r>>3);
 943 #       elif defined(__GNUC__) && (__GNUC__ >= 3)
 944             return (__builtin_ctzll((U64)val) >> 3);
 945 #       else
 946             static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2,
 947                                                      0, 3, 1, 3, 1, 4, 2, 7,
 948                                                      0, 2, 3, 6, 1, 5, 3, 5,
 949                                                      1, 3, 4, 4, 2, 5, 6, 7,
 950                                                      7, 0, 1, 2, 3, 3, 4, 6,
 951                                                      2, 6, 5, 5, 3, 4, 5, 6,
 952                                                      7, 1, 2, 4, 6, 4, 4, 5,
 953                                                      7, 2, 6, 5, 7, 6, 7, 7 };
 954             return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
 955 #       endif
 956         } else { /* 32 bits */
 957 #       if defined(_MSC_VER)
 958             unsigned long r=0;
 959             _BitScanForward( &r, (U32)val );
 960             return (unsigned)(r>>3);
 961 #       elif defined(__GNUC__) && (__GNUC__ >= 3)
 962             return (__builtin_ctz((U32)val) >> 3);
 963 #       else
 964             static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0,
 965                                                      3, 2, 2, 1, 3, 2, 0, 1,
 966                                                      3, 3, 1, 2, 2, 2, 2, 0,
 967                                                      3, 1, 2, 0, 1, 0, 1, 1 };
 968             return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
 969 #       endif
 970         }
 971     } else {  /* Big Endian CPU */
 972         if (MEM_64bits()) {
 973 #       if defined(_MSC_VER) && defined(_WIN64)
 974             unsigned long r = 0;
 975             _BitScanReverse64( &r, val );
 976             return (unsigned)(r>>3);
 977 #       elif defined(__GNUC__) && (__GNUC__ >= 3)
 978             return (__builtin_clzll(val) >> 3);
 979 #       else
 980             unsigned r;
 981             const unsigned n32 = sizeof(size_t)*4;   /* calculate this way due to compiler complaining in 32-bits mode */
 982             if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }
 983             if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
 984             r += (!val);
 985             return r;
 986 #       endif
 987         } else { /* 32 bits */
 988 #       if defined(_MSC_VER)
 989             unsigned long r = 0;
 990             _BitScanReverse( &r, (unsigned long)val );
 991             return (unsigned)(r>>3);
 992 #       elif defined(__GNUC__) && (__GNUC__ >= 3)
 993             return (__builtin_clz((U32)val) >> 3);
 994 #       else
 995             unsigned r;
 996             if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
 997             r += (!val);
 998             return r;
 999 #       endif
1000     }   }
1001 }
1002
1003
1004 static size_t ZSTD_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* const pInLimit)
1005 {
1006     const BYTE* const pStart = pIn;
1007     const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1);
1008
1009     while (pIn < pInLoopLimit) {
1010         size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
1011         if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; }
1012         pIn += ZSTD_NbCommonBytes(diff);
1013         return (size_t)(pIn - pStart);
1014     }
1015     if (MEM_64bits()) if ((pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatch+=4; }
1016     if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; }
1017     if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;
1018     return (size_t)(pIn - pStart);
1019 }
1020
1021 /** ZSTD_count_2segments() :
1022 *   can count match length with `ip` & `match` in 2 different segments.
1023 *   convention : on reaching mEnd, match count continue starting from iStart
1024 */
1025 static size_t ZSTD_count_2segments(const BYTE* ip, const BYTE* match, const BYTE* iEnd, const BYTE* mEnd, const BYTE* iStart)
1026 {
1027     const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd);
1028     size_t const matchLength = ZSTD_count(ip, match, vEnd);
1029     if (match + matchLength != mEnd) return matchLength;
1030     return matchLength + ZSTD_count(ip+matchLength, iStart, iEnd);
1031 }
1032
1033
1034 /*-*************************************
1035 *  Hashes
1036 ***************************************/
1037 static const U32 prime3bytes = 506832829U;
1038 static U32    ZSTD_hash3(U32 u, U32 h) { return ((u << (32-24)) * prime3bytes)  >> (32-h) ; }
1039 MEM_STATIC size_t ZSTD_hash3Ptr(const void* ptr, U32 h) { return ZSTD_hash3(MEM_readLE32(ptr), h); } /* only in zstd_opt.h */
1040
1041 static const U32 prime4bytes = 2654435761U;
1042 static U32    ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32-h) ; }
1043 static size_t ZSTD_hash4Ptr(const void* ptr, U32 h) { return ZSTD_hash4(MEM_read32(ptr), h); }
1044
1045 static const U64 prime5bytes = 889523592379ULL;
1046 static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u  << (64-40)) * prime5bytes) >> (64-h)) ; }
1047 static size_t ZSTD_hash5Ptr(const void* p, U32 h) { return ZSTD_hash5(MEM_readLE64(p), h); }
1048
1049 static const U64 prime6bytes = 227718039650203ULL;
1050 static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u  << (64-48)) * prime6bytes) >> (64-h)) ; }
1051 static size_t ZSTD_hash6Ptr(const void* p, U32 h) { return ZSTD_hash6(MEM_readLE64(p), h); }
1052
1053 static const U64 prime7bytes = 58295818150454627ULL;
1054 static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u  << (64-56)) * prime7bytes) >> (64-h)) ; }
1055 static size_t ZSTD_hash7Ptr(const void* p, U32 h) { return ZSTD_hash7(MEM_readLE64(p), h); }
1056
1057 static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL;
1058 static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; }
1059 static size_t ZSTD_hash8Ptr(const void* p, U32 h) { return ZSTD_hash8(MEM_readLE64(p), h); }
1060
1061 static size_t ZSTD_hashPtr(const void* p, U32 hBits, U32 mls)
1062 {
1063     switch(mls)
1064     {
1065     default:
1066     case 4: return ZSTD_hash4Ptr(p, hBits);
1067     case 5: return ZSTD_hash5Ptr(p, hBits);
1068     case 6: return ZSTD_hash6Ptr(p, hBits);
1069     case 7: return ZSTD_hash7Ptr(p, hBits);
1070     case 8: return ZSTD_hash8Ptr(p, hBits);
1071     }
1072 }
1073
1074
1075 /*-*************************************
1076 *  Fast Scan
1077 ***************************************/
1078 static void ZSTD_fillHashTable (ZSTD_CCtx* zc, const void* end, const U32 mls)
1079 {
1080     U32* const hashTable = zc->hashTable;
1081     U32  const hBits = zc->params.cParams.hashLog;
1082     const BYTE* const base = zc->base;
1083     const BYTE* ip = base + zc->nextToUpdate;
1084     const BYTE* const iend = ((const BYTE*)end) - HASH_READ_SIZE;
1085     const size_t fastHashFillStep = 3;
1086
1087     while(ip <= iend) {
1088         hashTable[ZSTD_hashPtr(ip, hBits, mls)] = (U32)(ip - base);
1089         ip += fastHashFillStep;
1090     }
1091 }
1092
1093
1094 FORCE_INLINE
1095 void ZSTD_compressBlock_fast_generic(ZSTD_CCtx* cctx,
1096                                const void* src, size_t srcSize,
1097                                const U32 mls)
1098 {
1099     U32* const hashTable = cctx->hashTable;
1100     U32  const hBits = cctx->params.cParams.hashLog;
1101     seqStore_t* seqStorePtr = &(cctx->seqStore);
1102     const BYTE* const base = cctx->base;
1103     const BYTE* const istart = (const BYTE*)src;
1104     const BYTE* ip = istart;
1105     const BYTE* anchor = istart;
1106     const U32   lowestIndex = cctx->dictLimit;
1107     const BYTE* const lowest = base + lowestIndex;
1108     const BYTE* const iend = istart + srcSize;
1109     const BYTE* const ilimit = iend - HASH_READ_SIZE;
1110     U32 offset_1=cctx->rep[0], offset_2=cctx->rep[1];
1111     U32 offsetSaved = 0;
1112
1113     /* init */
1114     ip += (ip==lowest);
1115     {   U32 const maxRep = (U32)(ip-lowest);
1116         if (offset_2 > maxRep) offsetSaved = offset_2, offset_2 = 0;
1117         if (offset_1 > maxRep) offsetSaved = offset_1, offset_1 = 0;
1118     }
1119
1120     /* Main Search Loop */
1121     while (ip < ilimit) {   /* < instead of <=, because repcode check at (ip+1) */
1122         size_t mLength;
1123         size_t const h = ZSTD_hashPtr(ip, hBits, mls);
1124         U32 const current = (U32)(ip-base);
1125         U32 const matchIndex = hashTable[h];
1126         const BYTE* match = base + matchIndex;
1127         hashTable[h] = current;   /* update hash table */
1128
1129         if ((offset_1 > 0) & (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1))) {
1130             mLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4;
1131             ip++;
1132             ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH);
1133         } else {
1134             U32 offset;
1135             if ( (matchIndex <= lowestIndex) || (MEM_read32(match) != MEM_read32(ip)) ) {
1136                 ip += ((ip-anchor) >> g_searchStrength) + 1;
1137                 continue;
1138             }
1139             mLength = ZSTD_count(ip+4, match+4, iend) + 4;
1140             offset = (U32)(ip-match);
1141             while (((ip>anchor) & (match>lowest)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
1142             offset_2 = offset_1;
1143             offset_1 = offset;
1144
1145             ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
1146         }
1147
1148         /* match found */
1149         ip += mLength;
1150         anchor = ip;
1151
1152         if (ip <= ilimit) {
1153             /* Fill Table */
1154             hashTable[ZSTD_hashPtr(base+current+2, hBits, mls)] = current+2;  /* here because current+2 could be > iend-8 */
1155             hashTable[ZSTD_hashPtr(ip-2, hBits, mls)] = (U32)(ip-2-base);
1156             /* check immediate repcode */
1157             while ( (ip <= ilimit)
1158                  && ( (offset_2>0)
1159                  & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) {
1160                 /* store sequence */
1161                 size_t const rLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4;
1162                 { U32 const tmpOff = offset_2; offset_2 = offset_1; offset_1 = tmpOff; }  /* swap offset_2 <=> offset_1 */
1163                 hashTable[ZSTD_hashPtr(ip, hBits, mls)] = (U32)(ip-base);
1164                 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, rLength-MINMATCH);
1165                 ip += rLength;
1166                 anchor = ip;
1167                 continue;   /* faster when present ... (?) */
1168     }   }   }
1169
1170     /* save reps for next block */
1171     cctx->repToConfirm[0] = offset_1 ? offset_1 : offsetSaved;
1172     cctx->repToConfirm[1] = offset_2 ? offset_2 : offsetSaved;
1173
1174     /* Last Literals */
1175     {   size_t const lastLLSize = iend - anchor;
1176         memcpy(seqStorePtr->lit, anchor, lastLLSize);
1177         seqStorePtr->lit += lastLLSize;
1178     }
1179 }
1180
1181
1182 static void ZSTD_compressBlock_fast(ZSTD_CCtx* ctx,
1183                        const void* src, size_t srcSize)
1184 {
1185     const U32 mls = ctx->params.cParams.searchLength;
1186     switch(mls)
1187     {
1188     default: /* includes case 3 */
1189     case 4 :
1190         ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 4); return;
1191     case 5 :
1192         ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 5); return;
1193     case 6 :
1194         ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 6); return;
1195     case 7 :
1196         ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 7); return;
1197     }
1198 }
1199
1200
1201 static void ZSTD_compressBlock_fast_extDict_generic(ZSTD_CCtx* ctx,
1202                                  const void* src, size_t srcSize,
1203                                  const U32 mls)
1204 {
1205     U32* hashTable = ctx->hashTable;
1206     const U32 hBits = ctx->params.cParams.hashLog;
1207     seqStore_t* seqStorePtr = &(ctx->seqStore);
1208     const BYTE* const base = ctx->base;
1209     const BYTE* const dictBase = ctx->dictBase;
1210     const BYTE* const istart = (const BYTE*)src;
1211     const BYTE* ip = istart;
1212     const BYTE* anchor = istart;
1213     const U32   lowestIndex = ctx->lowLimit;
1214     const BYTE* const dictStart = dictBase + lowestIndex;
1215     const U32   dictLimit = ctx->dictLimit;
1216     const BYTE* const lowPrefixPtr = base + dictLimit;
1217     const BYTE* const dictEnd = dictBase + dictLimit;
1218     const BYTE* const iend = istart + srcSize;
1219     const BYTE* const ilimit = iend - 8;
1220     U32 offset_1=ctx->rep[0], offset_2=ctx->rep[1];
1221
1222     /* Search Loop */
1223     while (ip < ilimit) {  /* < instead of <=, because (ip+1) */
1224         const size_t h = ZSTD_hashPtr(ip, hBits, mls);
1225         const U32 matchIndex = hashTable[h];
1226         const BYTE* matchBase = matchIndex < dictLimit ? dictBase : base;
1227         const BYTE* match = matchBase + matchIndex;
1228         const U32 current = (U32)(ip-base);
1229         const U32 repIndex = current + 1 - offset_1;   /* offset_1 expected <= current +1 */
1230         const BYTE* repBase = repIndex < dictLimit ? dictBase : base;
1231         const BYTE* repMatch = repBase + repIndex;
1232         size_t mLength;
1233         hashTable[h] = current;   /* update hash table */
1234
1235         if ( (((U32)((dictLimit-1) - repIndex) >= 3) /* intentional underflow */ & (repIndex > lowestIndex))
1236            && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {
1237             const BYTE* repMatchEnd = repIndex < dictLimit ? dictEnd : iend;
1238             mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, lowPrefixPtr) + 4;
1239             ip++;
1240             ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH);
1241         } else {
1242             if ( (matchIndex < lowestIndex) ||
1243                  (MEM_read32(match) != MEM_read32(ip)) ) {
1244                 ip += ((ip-anchor) >> g_searchStrength) + 1;
1245                 continue;
1246             }
1247             {   const BYTE* matchEnd = matchIndex < dictLimit ? dictEnd : iend;
1248                 const BYTE* lowMatchPtr = matchIndex < dictLimit ? dictStart : lowPrefixPtr;
1249                 U32 offset;
1250                 mLength = ZSTD_count_2segments(ip+4, match+4, iend, matchEnd, lowPrefixPtr) + 4;
1251                 while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; }   /* catch up */
1252                 offset = current - matchIndex;
1253                 offset_2 = offset_1;
1254                 offset_1 = offset;
1255                 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
1256         }   }
1257
1258         /* found a match : store it */
1259         ip += mLength;
1260         anchor = ip;
1261
1262         if (ip <= ilimit) {
1263             /* Fill Table */
1264             hashTable[ZSTD_hashPtr(base+current+2, hBits, mls)] = current+2;
1265             hashTable[ZSTD_hashPtr(ip-2, hBits, mls)] = (U32)(ip-2-base);
1266             /* check immediate repcode */
1267             while (ip <= ilimit) {
1268                 U32 const current2 = (U32)(ip-base);
1269                 U32 const repIndex2 = current2 - offset_2;
1270                 const BYTE* repMatch2 = repIndex2 < dictLimit ? dictBase + repIndex2 : base + repIndex2;
1271                 if ( (((U32)((dictLimit-1) - repIndex2) >= 3) & (repIndex2 > lowestIndex))  /* intentional overflow */
1272                    && (MEM_read32(repMatch2) == MEM_read32(ip)) ) {
1273                     const BYTE* const repEnd2 = repIndex2 < dictLimit ? dictEnd : iend;
1274                     size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, lowPrefixPtr) + 4;
1275                     U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset;   /* swap offset_2 <=> offset_1 */
1276                     ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, repLength2-MINMATCH);
1277                     hashTable[ZSTD_hashPtr(ip, hBits, mls)] = current2;
1278                     ip += repLength2;
1279                     anchor = ip;
1280                     continue;
1281                 }
1282                 break;
1283     }   }   }
1284
1285     /* save reps for next block */
1286     ctx->repToConfirm[0] = offset_1; ctx->repToConfirm[1] = offset_2;
1287
1288     /* Last Literals */
1289     {   size_t const lastLLSize = iend - anchor;
1290         memcpy(seqStorePtr->lit, anchor, lastLLSize);
1291         seqStorePtr->lit += lastLLSize;
1292     }
1293 }
1294
1295
1296 static void ZSTD_compressBlock_fast_extDict(ZSTD_CCtx* ctx,
1297                          const void* src, size_t srcSize)
1298 {
1299     U32 const mls = ctx->params.cParams.searchLength;
1300     switch(mls)
1301     {
1302     default: /* includes case 3 */
1303     case 4 :
1304         ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 4); return;
1305     case 5 :
1306         ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 5); return;
1307     case 6 :
1308         ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 6); return;
1309     case 7 :
1310         ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 7); return;
1311     }
1312 }
1313
1314
1315 /*-*************************************
1316 *  Double Fast
1317 ***************************************/
1318 static void ZSTD_fillDoubleHashTable (ZSTD_CCtx* cctx, const void* end, const U32 mls)
1319 {
1320     U32* const hashLarge = cctx->hashTable;
1321     U32  const hBitsL = cctx->params.cParams.hashLog;
1322     U32* const hashSmall = cctx->chainTable;
1323     U32  const hBitsS = cctx->params.cParams.chainLog;
1324     const BYTE* const base = cctx->base;
1325     const BYTE* ip = base + cctx->nextToUpdate;
1326     const BYTE* const iend = ((const BYTE*)end) - HASH_READ_SIZE;
1327     const size_t fastHashFillStep = 3;
1328
1329     while(ip <= iend) {
1330         hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = (U32)(ip - base);
1331         hashLarge[ZSTD_hashPtr(ip, hBitsL, 8)] = (U32)(ip - base);
1332         ip += fastHashFillStep;
1333     }
1334 }
1335
1336
1337 FORCE_INLINE
1338 void ZSTD_compressBlock_doubleFast_generic(ZSTD_CCtx* cctx,
1339                                  const void* src, size_t srcSize,
1340                                  const U32 mls)
1341 {
1342     U32* const hashLong = cctx->hashTable;
1343     const U32 hBitsL = cctx->params.cParams.hashLog;
1344     U32* const hashSmall = cctx->chainTable;
1345     const U32 hBitsS = cctx->params.cParams.chainLog;
1346     seqStore_t* seqStorePtr = &(cctx->seqStore);
1347     const BYTE* const base = cctx->base;
1348     const BYTE* const istart = (const BYTE*)src;
1349     const BYTE* ip = istart;
1350     const BYTE* anchor = istart;
1351     const U32 lowestIndex = cctx->dictLimit;
1352     const BYTE* const lowest = base + lowestIndex;
1353     const BYTE* const iend = istart + srcSize;
1354     const BYTE* const ilimit = iend - HASH_READ_SIZE;
1355     U32 offset_1=cctx->rep[0], offset_2=cctx->rep[1];
1356     U32 offsetSaved = 0;
1357
1358     /* init */
1359     ip += (ip==lowest);
1360     {   U32 const maxRep = (U32)(ip-lowest);
1361         if (offset_2 > maxRep) offsetSaved = offset_2, offset_2 = 0;
1362         if (offset_1 > maxRep) offsetSaved = offset_1, offset_1 = 0;
1363     }
1364
1365     /* Main Search Loop */
1366     while (ip < ilimit) {   /* < instead of <=, because repcode check at (ip+1) */
1367         size_t mLength;
1368         size_t const h2 = ZSTD_hashPtr(ip, hBitsL, 8);
1369         size_t const h = ZSTD_hashPtr(ip, hBitsS, mls);
1370         U32 const current = (U32)(ip-base);
1371         U32 const matchIndexL = hashLong[h2];
1372         U32 const matchIndexS = hashSmall[h];
1373         const BYTE* matchLong = base + matchIndexL;
1374         const BYTE* match = base + matchIndexS;
1375         hashLong[h2] = hashSmall[h] = current;   /* update hash tables */
1376
1377         assert(offset_1 <= current);   /* supposed guaranteed by construction */
1378         if ((offset_1 > 0) & (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1))) {
1379             /* favor repcode */
1380             mLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4;
1381             ip++;
1382             ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH);
1383         } else {
1384             U32 offset;
1385             if ( (matchIndexL > lowestIndex) && (MEM_read64(matchLong) == MEM_read64(ip)) ) {
1386                 mLength = ZSTD_count(ip+8, matchLong+8, iend) + 8;
1387                 offset = (U32)(ip-matchLong);
1388                 while (((ip>anchor) & (matchLong>lowest)) && (ip[-1] == matchLong[-1])) { ip--; matchLong--; mLength++; } /* catch up */
1389             } else if ( (matchIndexS > lowestIndex) && (MEM_read32(match) == MEM_read32(ip)) ) {
1390                 size_t const hl3 = ZSTD_hashPtr(ip+1, hBitsL, 8);
1391                 U32 const matchIndexL3 = hashLong[hl3];
1392                 const BYTE* matchL3 = base + matchIndexL3;
1393                 hashLong[hl3] = current + 1;
1394                 if ( (matchIndexL3 > lowestIndex) && (MEM_read64(matchL3) == MEM_read64(ip+1)) ) {
1395                     mLength = ZSTD_count(ip+9, matchL3+8, iend) + 8;
1396                     ip++;
1397                     offset = (U32)(ip-matchL3);
1398                     while (((ip>anchor) & (matchL3>lowest)) && (ip[-1] == matchL3[-1])) { ip--; matchL3--; mLength++; } /* catch up */
1399                 } else {
1400                     mLength = ZSTD_count(ip+4, match+4, iend) + 4;
1401                     offset = (U32)(ip-match);
1402                     while (((ip>anchor) & (match>lowest)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */
1403                 }
1404             } else {
1405                 ip += ((ip-anchor) >> g_searchStrength) + 1;
1406                 continue;
1407             }
1408
1409             offset_2 = offset_1;
1410             offset_1 = offset;
1411
1412             ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
1413         }
1414
1415         /* match found */
1416         ip += mLength;
1417         anchor = ip;
1418
1419         if (ip <= ilimit) {
1420             /* Fill Table */
1421             hashLong[ZSTD_hashPtr(base+current+2, hBitsL, 8)] =
1422                 hashSmall[ZSTD_hashPtr(base+current+2, hBitsS, mls)] = current+2;  /* here because current+2 could be > iend-8 */
1423             hashLong[ZSTD_hashPtr(ip-2, hBitsL, 8)] =
1424                 hashSmall[ZSTD_hashPtr(ip-2, hBitsS, mls)] = (U32)(ip-2-base);
1425
1426             /* check immediate repcode */
1427             while ( (ip <= ilimit)
1428                  && ( (offset_2>0)
1429                  & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) {
1430                 /* store sequence */
1431                 size_t const rLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4;
1432                 { U32 const tmpOff = offset_2; offset_2 = offset_1; offset_1 = tmpOff; } /* swap offset_2 <=> offset_1 */
1433                 hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = (U32)(ip-base);
1434                 hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = (U32)(ip-base);
1435                 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, rLength-MINMATCH);
1436                 ip += rLength;
1437                 anchor = ip;
1438                 continue;   /* faster when present ... (?) */
1439     }   }   }
1440
1441     /* save reps for next block */
1442     cctx->repToConfirm[0] = offset_1 ? offset_1 : offsetSaved;
1443     cctx->repToConfirm[1] = offset_2 ? offset_2 : offsetSaved;
1444
1445     /* Last Literals */
1446     {   size_t const lastLLSize = iend - anchor;
1447         memcpy(seqStorePtr->lit, anchor, lastLLSize);
1448         seqStorePtr->lit += lastLLSize;
1449     }
1450 }
1451
1452
1453 static void ZSTD_compressBlock_doubleFast(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
1454 {
1455     const U32 mls = ctx->params.cParams.searchLength;
1456     switch(mls)
1457     {
1458     default: /* includes case 3 */
1459     case 4 :
1460         ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 4); return;
1461     case 5 :
1462         ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 5); return;
1463     case 6 :
1464         ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 6); return;
1465     case 7 :
1466         ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 7); return;
1467     }
1468 }
1469
1470
1471 static void ZSTD_compressBlock_doubleFast_extDict_generic(ZSTD_CCtx* ctx,
1472                                  const void* src, size_t srcSize,
1473                                  const U32 mls)
1474 {
1475     U32* const hashLong = ctx->hashTable;
1476     U32  const hBitsL = ctx->params.cParams.hashLog;
1477     U32* const hashSmall = ctx->chainTable;
1478     U32  const hBitsS = ctx->params.cParams.chainLog;
1479     seqStore_t* seqStorePtr = &(ctx->seqStore);
1480     const BYTE* const base = ctx->base;
1481     const BYTE* const dictBase = ctx->dictBase;
1482     const BYTE* const istart = (const BYTE*)src;
1483     const BYTE* ip = istart;
1484     const BYTE* anchor = istart;
1485     const U32   lowestIndex = ctx->lowLimit;
1486     const BYTE* const dictStart = dictBase + lowestIndex;
1487     const U32   dictLimit = ctx->dictLimit;
1488     const BYTE* const lowPrefixPtr = base + dictLimit;
1489     const BYTE* const dictEnd = dictBase + dictLimit;
1490     const BYTE* const iend = istart + srcSize;
1491     const BYTE* const ilimit = iend - 8;
1492     U32 offset_1=ctx->rep[0], offset_2=ctx->rep[1];
1493
1494     /* Search Loop */
1495     while (ip < ilimit) {  /* < instead of <=, because (ip+1) */
1496         const size_t hSmall = ZSTD_hashPtr(ip, hBitsS, mls);
1497         const U32 matchIndex = hashSmall[hSmall];
1498         const BYTE* matchBase = matchIndex < dictLimit ? dictBase : base;
1499         const BYTE* match = matchBase + matchIndex;
1500
1501         const size_t hLong = ZSTD_hashPtr(ip, hBitsL, 8);
1502         const U32 matchLongIndex = hashLong[hLong];
1503         const BYTE* matchLongBase = matchLongIndex < dictLimit ? dictBase : base;
1504         const BYTE* matchLong = matchLongBase + matchLongIndex;
1505
1506         const U32 current = (U32)(ip-base);
1507         const U32 repIndex = current + 1 - offset_1;   /* offset_1 expected <= current +1 */
1508         const BYTE* repBase = repIndex < dictLimit ? dictBase : base;
1509         const BYTE* repMatch = repBase + repIndex;
1510         size_t mLength;
1511         hashSmall[hSmall] = hashLong[hLong] = current;   /* update hash table */
1512
1513         if ( (((U32)((dictLimit-1) - repIndex) >= 3) /* intentional underflow */ & (repIndex > lowestIndex))
1514            && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {
1515             const BYTE* repMatchEnd = repIndex < dictLimit ? dictEnd : iend;
1516             mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, lowPrefixPtr) + 4;
1517             ip++;
1518             ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH);
1519         } else {
1520             if ((matchLongIndex > lowestIndex) && (MEM_read64(matchLong) == MEM_read64(ip))) {
1521                 const BYTE* matchEnd = matchLongIndex < dictLimit ? dictEnd : iend;
1522                 const BYTE* lowMatchPtr = matchLongIndex < dictLimit ? dictStart : lowPrefixPtr;
1523                 U32 offset;
1524                 mLength = ZSTD_count_2segments(ip+8, matchLong+8, iend, matchEnd, lowPrefixPtr) + 8;
1525                 offset = current - matchLongIndex;
1526                 while (((ip>anchor) & (matchLong>lowMatchPtr)) && (ip[-1] == matchLong[-1])) { ip--; matchLong--; mLength++; }   /* catch up */
1527                 offset_2 = offset_1;
1528                 offset_1 = offset;
1529                 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
1530
1531             } else if ((matchIndex > lowestIndex) && (MEM_read32(match) == MEM_read32(ip))) {
1532                 size_t const h3 = ZSTD_hashPtr(ip+1, hBitsL, 8);
1533                 U32 const matchIndex3 = hashLong[h3];
1534                 const BYTE* const match3Base = matchIndex3 < dictLimit ? dictBase : base;
1535                 const BYTE* match3 = match3Base + matchIndex3;
1536                 U32 offset;
1537                 hashLong[h3] = current + 1;
1538                 if ( (matchIndex3 > lowestIndex) && (MEM_read64(match3) == MEM_read64(ip+1)) ) {
1539                     const BYTE* matchEnd = matchIndex3 < dictLimit ? dictEnd : iend;
1540                     const BYTE* lowMatchPtr = matchIndex3 < dictLimit ? dictStart : lowPrefixPtr;
1541                     mLength = ZSTD_count_2segments(ip+9, match3+8, iend, matchEnd, lowPrefixPtr) + 8;
1542                     ip++;
1543                     offset = current+1 - matchIndex3;
1544                     while (((ip>anchor) & (match3>lowMatchPtr)) && (ip[-1] == match3[-1])) { ip--; match3--; mLength++; } /* catch up */
1545                 } else {
1546                     const BYTE* matchEnd = matchIndex < dictLimit ? dictEnd : iend;
1547                     const BYTE* lowMatchPtr = matchIndex < dictLimit ? dictStart : lowPrefixPtr;
1548                     mLength = ZSTD_count_2segments(ip+4, match+4, iend, matchEnd, lowPrefixPtr) + 4;
1549                     offset = current - matchIndex;
1550                     while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; }   /* catch up */
1551                 }
1552                 offset_2 = offset_1;
1553                 offset_1 = offset;
1554                 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH);
1555
1556             } else {
1557                 ip += ((ip-anchor) >> g_searchStrength) + 1;
1558                 continue;
1559         }   }
1560
1561         /* found a match : store it */
1562         ip += mLength;
1563         anchor = ip;
1564
1565         if (ip <= ilimit) {
1566             /* Fill Table */
1567             hashSmall[ZSTD_hashPtr(base+current+2, hBitsS, mls)] = current+2;
1568             hashLong[ZSTD_hashPtr(base+current+2, hBitsL, 8)] = current+2;
1569             hashSmall[ZSTD_hashPtr(ip-2, hBitsS, mls)] = (U32)(ip-2-base);
1570             hashLong[ZSTD_hashPtr(ip-2, hBitsL, 8)] = (U32)(ip-2-base);
1571             /* check immediate repcode */
1572             while (ip <= ilimit) {
1573                 U32 const current2 = (U32)(ip-base);
1574                 U32 const repIndex2 = current2 - offset_2;
1575                 const BYTE* repMatch2 = repIndex2 < dictLimit ? dictBase + repIndex2 : base + repIndex2;
1576                 if ( (((U32)((dictLimit-1) - repIndex2) >= 3) & (repIndex2 > lowestIndex))  /* intentional overflow */
1577                    && (MEM_read32(repMatch2) == MEM_read32(ip)) ) {
1578                     const BYTE* const repEnd2 = repIndex2 < dictLimit ? dictEnd : iend;
1579                     size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, lowPrefixPtr) + 4;
1580                     U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset;   /* swap offset_2 <=> offset_1 */
1581                     ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, repLength2-MINMATCH);
1582                     hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = current2;
1583                     hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = current2;
1584                     ip += repLength2;
1585                     anchor = ip;
1586                     continue;
1587                 }
1588                 break;
1589     }   }   }
1590
1591     /* save reps for next block */
1592     ctx->repToConfirm[0] = offset_1; ctx->repToConfirm[1] = offset_2;
1593
1594     /* Last Literals */
1595     {   size_t const lastLLSize = iend - anchor;
1596         memcpy(seqStorePtr->lit, anchor, lastLLSize);
1597         seqStorePtr->lit += lastLLSize;
1598     }
1599 }
1600
1601
1602 static void ZSTD_compressBlock_doubleFast_extDict(ZSTD_CCtx* ctx,
1603                          const void* src, size_t srcSize)
1604 {
1605     U32 const mls = ctx->params.cParams.searchLength;
1606     switch(mls)
1607     {
1608     default: /* includes case 3 */
1609     case 4 :
1610         ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 4); return;
1611     case 5 :
1612         ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 5); return;
1613     case 6 :
1614         ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 6); return;
1615     case 7 :
1616         ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 7); return;
1617     }
1618 }
1619
1620
1621 /*-*************************************
1622 *  Binary Tree search
1623 ***************************************/
1624 /** ZSTD_insertBt1() : add one or multiple positions to tree.
1625 *   ip : assumed <= iend-8 .
1626 *   @return : nb of positions added */
1627 static U32 ZSTD_insertBt1(ZSTD_CCtx* zc, const BYTE* const ip, const U32 mls, const BYTE* const iend, U32 nbCompares,
1628                           U32 extDict)
1629 {
1630     U32*   const hashTable = zc->hashTable;
1631     U32    const hashLog = zc->params.cParams.hashLog;
1632     size_t const h  = ZSTD_hashPtr(ip, hashLog, mls);
1633     U32*   const bt = zc->chainTable;
1634     U32    const btLog  = zc->params.cParams.chainLog - 1;
1635     U32    const btMask = (1 << btLog) - 1;
1636     U32 matchIndex = hashTable[h];
1637     size_t commonLengthSmaller=0, commonLengthLarger=0;
1638     const BYTE* const base = zc->base;
1639     const BYTE* const dictBase = zc->dictBase;
1640     const U32 dictLimit = zc->dictLimit;
1641     const BYTE* const dictEnd = dictBase + dictLimit;
1642     const BYTE* const prefixStart = base + dictLimit;
1643     const BYTE* match;
1644     const U32 current = (U32)(ip-base);
1645     const U32 btLow = btMask >= current ? 0 : current - btMask;
1646     U32* smallerPtr = bt + 2*(current&btMask);
1647     U32* largerPtr  = smallerPtr + 1;
1648     U32 dummy32;   /* to be nullified at the end */
1649     U32 const windowLow = zc->lowLimit;
1650     U32 matchEndIdx = current+8;
1651     size_t bestLength = 8;
1652 #ifdef ZSTD_C_PREDICT
1653     U32 predictedSmall = *(bt + 2*((current-1)&btMask) + 0);
1654     U32 predictedLarge = *(bt + 2*((current-1)&btMask) + 1);
1655     predictedSmall += (predictedSmall>0);
1656     predictedLarge += (predictedLarge>0);
1657 #endif /* ZSTD_C_PREDICT */
1658
1659     hashTable[h] = current;   /* Update Hash Table */
1660
1661     while (nbCompares-- && (matchIndex > windowLow)) {
1662         U32* const nextPtr = bt + 2*(matchIndex & btMask);
1663         size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger);   /* guaranteed minimum nb of common bytes */
1664
1665 #ifdef ZSTD_C_PREDICT   /* note : can create issues when hlog small <= 11 */
1666         const U32* predictPtr = bt + 2*((matchIndex-1) & btMask);   /* written this way, as bt is a roll buffer */
1667         if (matchIndex == predictedSmall) {
1668             /* no need to check length, result known */
1669             *smallerPtr = matchIndex;
1670             if (matchIndex <= btLow) { smallerPtr=&dummy32; break; }   /* beyond tree size, stop the search */
1671             smallerPtr = nextPtr+1;               /* new "smaller" => larger of match */
1672             matchIndex = nextPtr[1];              /* new matchIndex larger than previous (closer to current) */
1673             predictedSmall = predictPtr[1] + (predictPtr[1]>0);
1674             continue;
1675         }
1676         if (matchIndex == predictedLarge) {
1677             *largerPtr = matchIndex;
1678             if (matchIndex <= btLow) { largerPtr=&dummy32; break; }   /* beyond tree size, stop the search */
1679             largerPtr = nextPtr;
1680             matchIndex = nextPtr[0];
1681             predictedLarge = predictPtr[0] + (predictPtr[0]>0);
1682             continue;
1683         }
1684 #endif
1685         if ((!extDict) || (matchIndex+matchLength >= dictLimit)) {
1686             match = base + matchIndex;
1687             if (match[matchLength] == ip[matchLength])
1688                 matchLength += ZSTD_count(ip+matchLength+1, match+matchLength+1, iend) +1;
1689         } else {
1690             match = dictBase + matchIndex;
1691             matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iend, dictEnd, prefixStart);
1692             if (matchIndex+matchLength >= dictLimit)
1693                 match = base + matchIndex;   /* to prepare for next usage of match[matchLength] */
1694         }
1695
1696         if (matchLength > bestLength) {
1697             bestLength = matchLength;
1698             if (matchLength > matchEndIdx - matchIndex)
1699                 matchEndIdx = matchIndex + (U32)matchLength;
1700         }
1701
1702         if (ip+matchLength == iend)   /* equal : no way to know if inf or sup */
1703             break;   /* drop , to guarantee consistency ; miss a bit of compression, but other solutions can corrupt the tree */
1704
1705         if (match[matchLength] < ip[matchLength]) {  /* necessarily within correct buffer */
1706             /* match is smaller than current */
1707             *smallerPtr = matchIndex;             /* update smaller idx */
1708             commonLengthSmaller = matchLength;    /* all smaller will now have at least this guaranteed common length */
1709             if (matchIndex <= btLow) { smallerPtr=&dummy32; break; }   /* beyond tree size, stop the search */
1710             smallerPtr = nextPtr+1;               /* new "smaller" => larger of match */
1711             matchIndex = nextPtr[1];              /* new matchIndex larger than previous (closer to current) */
1712         } else {
1713             /* match is larger than current */
1714             *largerPtr = matchIndex;
1715             commonLengthLarger = matchLength;
1716             if (matchIndex <= btLow) { largerPtr=&dummy32; break; }   /* beyond tree size, stop the search */
1717             largerPtr = nextPtr;
1718             matchIndex = nextPtr[0];
1719     }   }
1720
1721     *smallerPtr = *largerPtr = 0;
1722     if (bestLength > 384) return MIN(192, (U32)(bestLength - 384));   /* speed optimization */
1723     if (matchEndIdx > current + 8) return matchEndIdx - current - 8;
1724     return 1;
1725 }
1726
1727
1728 static size_t ZSTD_insertBtAndFindBestMatch (
1729                         ZSTD_CCtx* zc,
1730                         const BYTE* const ip, const BYTE* const iend,
1731                         size_t* offsetPtr,
1732                         U32 nbCompares, const U32 mls,
1733                         U32 extDict)
1734 {
1735     U32*   const hashTable = zc->hashTable;
1736     U32    const hashLog = zc->params.cParams.hashLog;
1737     size_t const h  = ZSTD_hashPtr(ip, hashLog, mls);
1738     U32*   const bt = zc->chainTable;
1739     U32    const btLog  = zc->params.cParams.chainLog - 1;
1740     U32    const btMask = (1 << btLog) - 1;
1741     U32 matchIndex  = hashTable[h];
1742     size_t commonLengthSmaller=0, commonLengthLarger=0;
1743     const BYTE* const base = zc->base;
1744     const BYTE* const dictBase = zc->dictBase;
1745     const U32 dictLimit = zc->dictLimit;
1746     const BYTE* const dictEnd = dictBase + dictLimit;
1747     const BYTE* const prefixStart = base + dictLimit;
1748     const U32 current = (U32)(ip-base);
1749     const U32 btLow = btMask >= current ? 0 : current - btMask;
1750     const U32 windowLow = zc->lowLimit;
1751     U32* smallerPtr = bt + 2*(current&btMask);
1752     U32* largerPtr  = bt + 2*(current&btMask) + 1;
1753     U32 matchEndIdx = current+8;
1754     U32 dummy32;   /* to be nullified at the end */
1755     size_t bestLength = 0;
1756
1757     hashTable[h] = current;   /* Update Hash Table */
1758
1759     while (nbCompares-- && (matchIndex > windowLow)) {
1760         U32* const nextPtr = bt + 2*(matchIndex & btMask);
1761         size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger);   /* guaranteed minimum nb of common bytes */
1762         const BYTE* match;
1763
1764         if ((!extDict) || (matchIndex+matchLength >= dictLimit)) {
1765             match = base + matchIndex;
1766             if (match[matchLength] == ip[matchLength])
1767                 matchLength += ZSTD_count(ip+matchLength+1, match+matchLength+1, iend) +1;
1768         } else {
1769             match = dictBase + matchIndex;
1770             matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iend, dictEnd, prefixStart);
1771             if (matchIndex+matchLength >= dictLimit)
1772                 match = base + matchIndex;   /* to prepare for next usage of match[matchLength] */
1773         }
1774
1775         if (matchLength > bestLength) {
1776             if (matchLength > matchEndIdx - matchIndex)
1777                 matchEndIdx = matchIndex + (U32)matchLength;
1778             if ( (4*(int)(matchLength-bestLength)) > (int)(ZSTD_highbit32(current-matchIndex+1) - ZSTD_highbit32((U32)offsetPtr[0]+1)) )
1779                 bestLength = matchLength, *offsetPtr = ZSTD_REP_MOVE + current - matchIndex;
1780             if (ip+matchLength == iend)   /* equal : no way to know if inf or sup */
1781                 break;   /* drop, to guarantee consistency (miss a little bit of compression) */
1782         }
1783
1784         if (match[matchLength] < ip[matchLength]) {
1785             /* match is smaller than current */
1786             *smallerPtr = matchIndex;             /* update smaller idx */
1787             commonLengthSmaller = matchLength;    /* all smaller will now have at least this guaranteed common length */
1788             if (matchIndex <= btLow) { smallerPtr=&dummy32; break; }   /* beyond tree size, stop the search */
1789             smallerPtr = nextPtr+1;               /* new "smaller" => larger of match */
1790             matchIndex = nextPtr[1];              /* new matchIndex larger than previous (closer to current) */
1791         } else {
1792             /* match is larger than current */
1793             *largerPtr = matchIndex;
1794             commonLengthLarger = matchLength;
1795             if (matchIndex <= btLow) { largerPtr=&dummy32; break; }   /* beyond tree size, stop the search */
1796             largerPtr = nextPtr;
1797             matchIndex = nextPtr[0];
1798     }   }
1799
1800     *smallerPtr = *largerPtr = 0;
1801
1802     zc->nextToUpdate = (matchEndIdx > current + 8) ? matchEndIdx - 8 : current+1;
1803     return bestLength;
1804 }
1805
1806
1807 static void ZSTD_updateTree(ZSTD_CCtx* zc, const BYTE* const ip, const BYTE* const iend, const U32 nbCompares, const U32 mls)
1808 {
1809     const BYTE* const base = zc->base;
1810     const U32 target = (U32)(ip - base);
1811     U32 idx = zc->nextToUpdate;
1812
1813     while(idx < target)
1814         idx += ZSTD_insertBt1(zc, base+idx, mls, iend, nbCompares, 0);
1815 }
1816
1817 /** ZSTD_BtFindBestMatch() : Tree updater, providing best match */
1818 static size_t ZSTD_BtFindBestMatch (
1819                         ZSTD_CCtx* zc,
1820                         const BYTE* const ip, const BYTE* const iLimit,
1821                         size_t* offsetPtr,
1822                         const U32 maxNbAttempts, const U32 mls)
1823 {
1824     if (ip < zc->base + zc->nextToUpdate) return 0;   /* skipped area */
1825     ZSTD_updateTree(zc, ip, iLimit, maxNbAttempts, mls);
1826     return ZSTD_insertBtAndFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, mls, 0);
1827 }
1828
1829
1830 static size_t ZSTD_BtFindBestMatch_selectMLS (
1831                         ZSTD_CCtx* zc,   /* Index table will be updated */
1832                         const BYTE* ip, const BYTE* const iLimit,
1833                         size_t* offsetPtr,
1834                         const U32 maxNbAttempts, const U32 matchLengthSearch)
1835 {
1836     switch(matchLengthSearch)
1837     {
1838     default : /* includes case 3 */
1839     case 4 : return ZSTD_BtFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4);
1840     case 5 : return ZSTD_BtFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5);
1841     case 7 :
1842     case 6 : return ZSTD_BtFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6);
1843     }
1844 }
1845
1846
1847 static void ZSTD_updateTree_extDict(ZSTD_CCtx* zc, const BYTE* const ip, const BYTE* const iend, const U32 nbCompares, const U32 mls)
1848 {
1849     const BYTE* const base = zc->base;
1850     const U32 target = (U32)(ip - base);
1851     U32 idx = zc->nextToUpdate;
1852
1853     while (idx < target) idx += ZSTD_insertBt1(zc, base+idx, mls, iend, nbCompares, 1);
1854 }
1855
1856
1857 /** Tree updater, providing best match */
1858 static size_t ZSTD_BtFindBestMatch_extDict (
1859                         ZSTD_CCtx* zc,
1860                         const BYTE* const ip, const BYTE* const iLimit,
1861                         size_t* offsetPtr,
1862                         const U32 maxNbAttempts, const U32 mls)
1863 {
1864     if (ip < zc->base + zc->nextToUpdate) return 0;   /* skipped area */
1865     ZSTD_updateTree_extDict(zc, ip, iLimit, maxNbAttempts, mls);
1866     return ZSTD_insertBtAndFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, mls, 1);
1867 }
1868
1869
1870 static size_t ZSTD_BtFindBestMatch_selectMLS_extDict (
1871                         ZSTD_CCtx* zc,   /* Index table will be updated */
1872                         const BYTE* ip, const BYTE* const iLimit,
1873                         size_t* offsetPtr,
1874                         const U32 maxNbAttempts, const U32 matchLengthSearch)
1875 {
1876     switch(matchLengthSearch)
1877     {
1878     default : /* includes case 3 */
1879     case 4 : return ZSTD_BtFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4);
1880     case 5 : return ZSTD_BtFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5);
1881     case 7 :
1882     case 6 : return ZSTD_BtFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6);
1883     }
1884 }
1885
1886
1887
1888 /* *********************************
1889 *  Hash Chain
1890 ***********************************/
1891 #define NEXT_IN_CHAIN(d, mask)   chainTable[(d) & mask]
1892
1893 /* Update chains up to ip (excluded)
1894    Assumption : always within prefix (i.e. not within extDict) */
1895 FORCE_INLINE
1896 U32 ZSTD_insertAndFindFirstIndex (ZSTD_CCtx* zc, const BYTE* ip, U32 mls)
1897 {
1898     U32* const hashTable  = zc->hashTable;
1899     const U32 hashLog = zc->params.cParams.hashLog;
1900     U32* const chainTable = zc->chainTable;
1901     const U32 chainMask = (1 << zc->params.cParams.chainLog) - 1;
1902     const BYTE* const base = zc->base;
1903     const U32 target = (U32)(ip - base);
1904     U32 idx = zc->nextToUpdate;
1905
1906     while(idx < target) { /* catch up */
1907         size_t const h = ZSTD_hashPtr(base+idx, hashLog, mls);
1908         NEXT_IN_CHAIN(idx, chainMask) = hashTable[h];
1909         hashTable[h] = idx;
1910         idx++;
1911     }
1912
1913     zc->nextToUpdate = target;
1914     return hashTable[ZSTD_hashPtr(ip, hashLog, mls)];
1915 }
1916
1917
1918
1919 FORCE_INLINE /* inlining is important to hardwire a hot branch (template emulation) */
1920 size_t ZSTD_HcFindBestMatch_generic (
1921                         ZSTD_CCtx* zc,   /* Index table will be updated */
1922                         const BYTE* const ip, const BYTE* const iLimit,
1923                         size_t* offsetPtr,
1924                         const U32 maxNbAttempts, const U32 mls, const U32 extDict)
1925 {
1926     U32* const chainTable = zc->chainTable;
1927     const U32 chainSize = (1 << zc->params.cParams.chainLog);
1928     const U32 chainMask = chainSize-1;
1929     const BYTE* const base = zc->base;
1930     const BYTE* const dictBase = zc->dictBase;
1931     const U32 dictLimit = zc->dictLimit;
1932     const BYTE* const prefixStart = base + dictLimit;
1933     const BYTE* const dictEnd = dictBase + dictLimit;
1934     const U32 lowLimit = zc->lowLimit;
1935     const U32 current = (U32)(ip-base);
1936     const U32 minChain = current > chainSize ? current - chainSize : 0;
1937     int nbAttempts=maxNbAttempts;
1938     size_t ml=4-1;
1939
1940     /* HC4 match finder */
1941     U32 matchIndex = ZSTD_insertAndFindFirstIndex (zc, ip, mls);
1942
1943     for ( ; (matchIndex>lowLimit) & (nbAttempts>0) ; nbAttempts--) {
1944         const BYTE* match;
1945         size_t currentMl=0;
1946         if ((!extDict) || matchIndex >= dictLimit) {
1947             match = base + matchIndex;
1948             if (match[ml] == ip[ml])   /* potentially better */
1949                 currentMl = ZSTD_count(ip, match, iLimit);
1950         } else {
1951             match = dictBase + matchIndex;
1952             if (MEM_read32(match) == MEM_read32(ip))   /* assumption : matchIndex <= dictLimit-4 (by table construction) */
1953                 currentMl = ZSTD_count_2segments(ip+4, match+4, iLimit, dictEnd, prefixStart) + 4;
1954         }
1955
1956         /* save best solution */
1957         if (currentMl > ml) {
1958             ml = currentMl;
1959             *offsetPtr = current - matchIndex + ZSTD_REP_MOVE;
1960             if (ip+currentMl == iLimit) break; /* best possible, avoids read overflow on next attempt */
1961         }
1962
1963         if (matchIndex <= minChain) break;
1964         matchIndex = NEXT_IN_CHAIN(matchIndex, chainMask);
1965     }
1966
1967     return ml;
1968 }
1969
1970
1971 FORCE_INLINE size_t ZSTD_HcFindBestMatch_selectMLS (
1972                         ZSTD_CCtx* zc,
1973                         const BYTE* ip, const BYTE* const iLimit,
1974                         size_t* offsetPtr,
1975                         const U32 maxNbAttempts, const U32 matchLengthSearch)
1976 {
1977     switch(matchLengthSearch)
1978     {
1979     default : /* includes case 3 */
1980     case 4 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4, 0);
1981     case 5 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5, 0);
1982     case 7 :
1983     case 6 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6, 0);
1984     }
1985 }
1986
1987
1988 FORCE_INLINE size_t ZSTD_HcFindBestMatch_extDict_selectMLS (
1989                         ZSTD_CCtx* zc,
1990                         const BYTE* ip, const BYTE* const iLimit,
1991                         size_t* offsetPtr,
1992                         const U32 maxNbAttempts, const U32 matchLengthSearch)
1993 {
1994     switch(matchLengthSearch)
1995     {
1996     default : /* includes case 3 */
1997     case 4 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4, 1);
1998     case 5 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5, 1);
1999     case 7 :
2000     case 6 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6, 1);
2001     }
2002 }
2003
2004
2005 /* *******************************
2006 *  Common parser - lazy strategy
2007 *********************************/
2008 FORCE_INLINE
2009 void ZSTD_compressBlock_lazy_generic(ZSTD_CCtx* ctx,
2010                                      const void* src, size_t srcSize,
2011                                      const U32 searchMethod, const U32 depth)
2012 {
2013     seqStore_t* seqStorePtr = &(ctx->seqStore);
2014     const BYTE* const istart = (const BYTE*)src;
2015     const BYTE* ip = istart;
2016     const BYTE* anchor = istart;
2017     const BYTE* const iend = istart + srcSize;
2018     const BYTE* const ilimit = iend - 8;
2019     const BYTE* const base = ctx->base + ctx->dictLimit;
2020
2021     U32 const maxSearches = 1 << ctx->params.cParams.searchLog;
2022     U32 const mls = ctx->params.cParams.searchLength;
2023
2024     typedef size_t (*searchMax_f)(ZSTD_CCtx* zc, const BYTE* ip, const BYTE* iLimit,
2025                         size_t* offsetPtr,
2026                         U32 maxNbAttempts, U32 matchLengthSearch);
2027     searchMax_f const searchMax = searchMethod ? ZSTD_BtFindBestMatch_selectMLS : ZSTD_HcFindBestMatch_selectMLS;
2028     U32 offset_1 = ctx->rep[0], offset_2 = ctx->rep[1], savedOffset=0;
2029
2030     /* init */
2031     ip += (ip==base);
2032     ctx->nextToUpdate3 = ctx->nextToUpdate;
2033     {   U32 const maxRep = (U32)(ip-base);
2034         if (offset_2 > maxRep) savedOffset = offset_2, offset_2 = 0;
2035         if (offset_1 > maxRep) savedOffset = offset_1, offset_1 = 0;
2036     }
2037
2038     /* Match Loop */
2039     while (ip < ilimit) {
2040         size_t matchLength=0;
2041         size_t offset=0;
2042         const BYTE* start=ip+1;
2043
2044         /* check repCode */
2045         if ((offset_1>0) & (MEM_read32(ip+1) == MEM_read32(ip+1 - offset_1))) {
2046             /* repcode : we take it */
2047             matchLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4;
2048             if (depth==0) goto _storeSequence;
2049         }
2050
2051         /* first search (depth 0) */
2052         {   size_t offsetFound = 99999999;
2053             size_t const ml2 = searchMax(ctx, ip, iend, &offsetFound, maxSearches, mls);
2054             if (ml2 > matchLength)
2055                 matchLength = ml2, start = ip, offset=offsetFound;
2056         }
2057
2058         if (matchLength < 4) {
2059             ip += ((ip-anchor) >> g_searchStrength) + 1;   /* jump faster over incompressible sections */
2060             continue;
2061         }
2062
2063         /* let's try to find a better solution */
2064         if (depth>=1)
2065         while (ip<ilimit) {
2066             ip ++;
2067             if ((offset) && ((offset_1>0) & (MEM_read32(ip) == MEM_read32(ip - offset_1)))) {
2068                 size_t const mlRep = ZSTD_count(ip+4, ip+4-offset_1, iend) + 4;
2069                 int const gain2 = (int)(mlRep * 3);
2070                 int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)offset+1) + 1);
2071                 if ((mlRep >= 4) && (gain2 > gain1))
2072                     matchLength = mlRep, offset = 0, start = ip;
2073             }
2074             {   size_t offset2=99999999;
2075                 size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls);
2076                 int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1));   /* raw approx */
2077                 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 4);
2078                 if ((ml2 >= 4) && (gain2 > gain1)) {
2079                     matchLength = ml2, offset = offset2, start = ip;
2080                     continue;   /* search a better one */
2081             }   }
2082
2083             /* let's find an even better one */
2084             if ((depth==2) && (ip<ilimit)) {
2085                 ip ++;
2086                 if ((offset) && ((offset_1>0) & (MEM_read32(ip) == MEM_read32(ip - offset_1)))) {
2087                     size_t const ml2 = ZSTD_count(ip+4, ip+4-offset_1, iend) + 4;
2088                     int const gain2 = (int)(ml2 * 4);
2089                     int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 1);
2090                     if ((ml2 >= 4) && (gain2 > gain1))
2091                         matchLength = ml2, offset = 0, start = ip;
2092                 }
2093                 {   size_t offset2=99999999;
2094                     size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls);
2095                     int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1));   /* raw approx */
2096                     int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 7);
2097                     if ((ml2 >= 4) && (gain2 > gain1)) {
2098                         matchLength = ml2, offset = offset2, start = ip;
2099                         continue;
2100             }   }   }
2101             break;  /* nothing found : store previous solution */
2102         }
2103
2104         /* catch up */
2105         if (offset) {
2106             while ( (start > anchor)
2107                  && (start > base+offset-ZSTD_REP_MOVE)
2108                  && (start[-1] == start[-1-offset+ZSTD_REP_MOVE]) )  /* only search for offset within prefix */
2109                 { start--; matchLength++; }
2110             offset_2 = offset_1; offset_1 = (U32)(offset - ZSTD_REP_MOVE);
2111         }
2112
2113         /* store sequence */
2114 _storeSequence:
2115         {   size_t const litLength = start - anchor;
2116             ZSTD_storeSeq(seqStorePtr, litLength, anchor, (U32)offset, matchLength-MINMATCH);
2117             anchor = ip = start + matchLength;
2118         }
2119
2120         /* check immediate repcode */
2121         while ( (ip <= ilimit)
2122              && ((offset_2>0)
2123              & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) {
2124             /* store sequence */
2125             matchLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4;
2126             offset = offset_2; offset_2 = offset_1; offset_1 = (U32)offset; /* swap repcodes */
2127             ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, matchLength-MINMATCH);
2128             ip += matchLength;
2129             anchor = ip;
2130             continue;   /* faster when present ... (?) */
2131     }   }
2132
2133     /* Save reps for next block */
2134     ctx->repToConfirm[0] = offset_1 ? offset_1 : savedOffset;
2135     ctx->repToConfirm[1] = offset_2 ? offset_2 : savedOffset;
2136
2137     /* Last Literals */
2138     {   size_t const lastLLSize = iend - anchor;
2139         memcpy(seqStorePtr->lit, anchor, lastLLSize);
2140         seqStorePtr->lit += lastLLSize;
2141     }
2142 }
2143
2144
2145 static void ZSTD_compressBlock_btlazy2(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2146 {
2147     ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 1, 2);
2148 }
2149
2150 static void ZSTD_compressBlock_lazy2(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2151 {
2152     ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 0, 2);
2153 }
2154
2155 static void ZSTD_compressBlock_lazy(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2156 {
2157     ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 0, 1);
2158 }
2159
2160 static void ZSTD_compressBlock_greedy(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2161 {
2162     ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 0, 0);
2163 }
2164
2165
2166 FORCE_INLINE
2167 void ZSTD_compressBlock_lazy_extDict_generic(ZSTD_CCtx* ctx,
2168                                      const void* src, size_t srcSize,
2169                                      const U32 searchMethod, const U32 depth)
2170 {
2171     seqStore_t* seqStorePtr = &(ctx->seqStore);
2172     const BYTE* const istart = (const BYTE*)src;
2173     const BYTE* ip = istart;
2174     const BYTE* anchor = istart;
2175     const BYTE* const iend = istart + srcSize;
2176     const BYTE* const ilimit = iend - 8;
2177     const BYTE* const base = ctx->base;
2178     const U32 dictLimit = ctx->dictLimit;
2179     const U32 lowestIndex = ctx->lowLimit;
2180     const BYTE* const prefixStart = base + dictLimit;
2181     const BYTE* const dictBase = ctx->dictBase;
2182     const BYTE* const dictEnd  = dictBase + dictLimit;
2183     const BYTE* const dictStart  = dictBase + ctx->lowLimit;
2184
2185     const U32 maxSearches = 1 << ctx->params.cParams.searchLog;
2186     const U32 mls = ctx->params.cParams.searchLength;
2187
2188     typedef size_t (*searchMax_f)(ZSTD_CCtx* zc, const BYTE* ip, const BYTE* iLimit,
2189                         size_t* offsetPtr,
2190                         U32 maxNbAttempts, U32 matchLengthSearch);
2191     searchMax_f searchMax = searchMethod ? ZSTD_BtFindBestMatch_selectMLS_extDict : ZSTD_HcFindBestMatch_extDict_selectMLS;
2192
2193     U32 offset_1 = ctx->rep[0], offset_2 = ctx->rep[1];
2194
2195     /* init */
2196     ctx->nextToUpdate3 = ctx->nextToUpdate;
2197     ip += (ip == prefixStart);
2198
2199     /* Match Loop */
2200     while (ip < ilimit) {
2201         size_t matchLength=0;
2202         size_t offset=0;
2203         const BYTE* start=ip+1;
2204         U32 current = (U32)(ip-base);
2205
2206         /* check repCode */
2207         {   const U32 repIndex = (U32)(current+1 - offset_1);
2208             const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
2209             const BYTE* const repMatch = repBase + repIndex;
2210             if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex))   /* intentional overflow */
2211             if (MEM_read32(ip+1) == MEM_read32(repMatch)) {
2212                 /* repcode detected we should take it */
2213                 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
2214                 matchLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repEnd, prefixStart) + 4;
2215                 if (depth==0) goto _storeSequence;
2216         }   }
2217
2218         /* first search (depth 0) */
2219         {   size_t offsetFound = 99999999;
2220             size_t const ml2 = searchMax(ctx, ip, iend, &offsetFound, maxSearches, mls);
2221             if (ml2 > matchLength)
2222                 matchLength = ml2, start = ip, offset=offsetFound;
2223         }
2224
2225          if (matchLength < 4) {
2226             ip += ((ip-anchor) >> g_searchStrength) + 1;   /* jump faster over incompressible sections */
2227             continue;
2228         }
2229
2230         /* let's try to find a better solution */
2231         if (depth>=1)
2232         while (ip<ilimit) {
2233             ip ++;
2234             current++;
2235             /* check repCode */
2236             if (offset) {
2237                 const U32 repIndex = (U32)(current - offset_1);
2238                 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
2239                 const BYTE* const repMatch = repBase + repIndex;
2240                 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex))  /* intentional overflow */
2241                 if (MEM_read32(ip) == MEM_read32(repMatch)) {
2242                     /* repcode detected */
2243                     const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
2244                     size_t const repLength = ZSTD_count_2segments(ip+4, repMatch+4, iend, repEnd, prefixStart) + 4;
2245                     int const gain2 = (int)(repLength * 3);
2246                     int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)offset+1) + 1);
2247                     if ((repLength >= 4) && (gain2 > gain1))
2248                         matchLength = repLength, offset = 0, start = ip;
2249             }   }
2250
2251             /* search match, depth 1 */
2252             {   size_t offset2=99999999;
2253                 size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls);
2254                 int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1));   /* raw approx */
2255                 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 4);
2256                 if ((ml2 >= 4) && (gain2 > gain1)) {
2257                     matchLength = ml2, offset = offset2, start = ip;
2258                     continue;   /* search a better one */
2259             }   }
2260
2261             /* let's find an even better one */
2262             if ((depth==2) && (ip<ilimit)) {
2263                 ip ++;
2264                 current++;
2265                 /* check repCode */
2266                 if (offset) {
2267                     const U32 repIndex = (U32)(current - offset_1);
2268                     const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
2269                     const BYTE* const repMatch = repBase + repIndex;
2270                     if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex))  /* intentional overflow */
2271                     if (MEM_read32(ip) == MEM_read32(repMatch)) {
2272                         /* repcode detected */
2273                         const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
2274                         size_t const repLength = ZSTD_count_2segments(ip+4, repMatch+4, iend, repEnd, prefixStart) + 4;
2275                         int const gain2 = (int)(repLength * 4);
2276                         int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 1);
2277                         if ((repLength >= 4) && (gain2 > gain1))
2278                             matchLength = repLength, offset = 0, start = ip;
2279                 }   }
2280
2281                 /* search match, depth 2 */
2282                 {   size_t offset2=99999999;
2283                     size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls);
2284                     int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1));   /* raw approx */
2285                     int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 7);
2286                     if ((ml2 >= 4) && (gain2 > gain1)) {
2287                         matchLength = ml2, offset = offset2, start = ip;
2288                         continue;
2289             }   }   }
2290             break;  /* nothing found : store previous solution */
2291         }
2292
2293         /* catch up */
2294         if (offset) {
2295             U32 const matchIndex = (U32)((start-base) - (offset - ZSTD_REP_MOVE));
2296             const BYTE* match = (matchIndex < dictLimit) ? dictBase + matchIndex : base + matchIndex;
2297             const BYTE* const mStart = (matchIndex < dictLimit) ? dictStart : prefixStart;
2298             while ((start>anchor) && (match>mStart) && (start[-1] == match[-1])) { start--; match--; matchLength++; }  /* catch up */
2299             offset_2 = offset_1; offset_1 = (U32)(offset - ZSTD_REP_MOVE);
2300         }
2301
2302         /* store sequence */
2303 _storeSequence:
2304         {   size_t const litLength = start - anchor;
2305             ZSTD_storeSeq(seqStorePtr, litLength, anchor, (U32)offset, matchLength-MINMATCH);
2306             anchor = ip = start + matchLength;
2307         }
2308
2309         /* check immediate repcode */
2310         while (ip <= ilimit) {
2311             const U32 repIndex = (U32)((ip-base) - offset_2);
2312             const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
2313             const BYTE* const repMatch = repBase + repIndex;
2314             if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex))  /* intentional overflow */
2315             if (MEM_read32(ip) == MEM_read32(repMatch)) {
2316                 /* repcode detected we should take it */
2317                 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
2318                 matchLength = ZSTD_count_2segments(ip+4, repMatch+4, iend, repEnd, prefixStart) + 4;
2319                 offset = offset_2; offset_2 = offset_1; offset_1 = (U32)offset;   /* swap offset history */
2320                 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, matchLength-MINMATCH);
2321                 ip += matchLength;
2322                 anchor = ip;
2323                 continue;   /* faster when present ... (?) */
2324             }
2325             break;
2326     }   }
2327
2328     /* Save reps for next block */
2329     ctx->repToConfirm[0] = offset_1; ctx->repToConfirm[1] = offset_2;
2330
2331     /* Last Literals */
2332     {   size_t const lastLLSize = iend - anchor;
2333         memcpy(seqStorePtr->lit, anchor, lastLLSize);
2334         seqStorePtr->lit += lastLLSize;
2335     }
2336 }
2337
2338
2339 void ZSTD_compressBlock_greedy_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2340 {
2341     ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 0, 0);
2342 }
2343
2344 static void ZSTD_compressBlock_lazy_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2345 {
2346     ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 0, 1);
2347 }
2348
2349 static void ZSTD_compressBlock_lazy2_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2350 {
2351     ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 0, 2);
2352 }
2353
2354 static void ZSTD_compressBlock_btlazy2_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2355 {
2356     ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 1, 2);
2357 }
2358
2359
2360 /* The optimal parser */
2361 #include "zstd_opt.h"
2362
2363 static void ZSTD_compressBlock_btopt(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2364 {
2365 #ifdef ZSTD_OPT_H_91842398743
2366     ZSTD_compressBlock_opt_generic(ctx, src, srcSize, 0);
2367 #else
2368     (void)ctx; (void)src; (void)srcSize;
2369     return;
2370 #endif
2371 }
2372
2373 static void ZSTD_compressBlock_btopt2(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2374 {
2375 #ifdef ZSTD_OPT_H_91842398743
2376     ZSTD_compressBlock_opt_generic(ctx, src, srcSize, 1);
2377 #else
2378     (void)ctx; (void)src; (void)srcSize;
2379     return;
2380 #endif
2381 }
2382
2383 static void ZSTD_compressBlock_btopt_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2384 {
2385 #ifdef ZSTD_OPT_H_91842398743
2386     ZSTD_compressBlock_opt_extDict_generic(ctx, src, srcSize, 0);
2387 #else
2388     (void)ctx; (void)src; (void)srcSize;
2389     return;
2390 #endif
2391 }
2392
2393 static void ZSTD_compressBlock_btopt2_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
2394 {
2395 #ifdef ZSTD_OPT_H_91842398743
2396     ZSTD_compressBlock_opt_extDict_generic(ctx, src, srcSize, 1);
2397 #else
2398     (void)ctx; (void)src; (void)srcSize;
2399     return;
2400 #endif
2401 }
2402
2403
2404 typedef void (*ZSTD_blockCompressor) (ZSTD_CCtx* ctx, const void* src, size_t srcSize);
2405
2406 static ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, int extDict)
2407 {
2408     static const ZSTD_blockCompressor blockCompressor[2][8] = {
2409         { ZSTD_compressBlock_fast, ZSTD_compressBlock_doubleFast, ZSTD_compressBlock_greedy,
2410           ZSTD_compressBlock_lazy, ZSTD_compressBlock_lazy2, ZSTD_compressBlock_btlazy2,
2411           ZSTD_compressBlock_btopt, ZSTD_compressBlock_btopt2 },
2412         { ZSTD_compressBlock_fast_extDict, ZSTD_compressBlock_doubleFast_extDict, ZSTD_compressBlock_greedy_extDict,
2413           ZSTD_compressBlock_lazy_extDict,ZSTD_compressBlock_lazy2_extDict, ZSTD_compressBlock_btlazy2_extDict,
2414           ZSTD_compressBlock_btopt_extDict, ZSTD_compressBlock_btopt2_extDict }
2415     };
2416
2417     return blockCompressor[extDict][(U32)strat];
2418 }
2419
2420
2421 static size_t ZSTD_compressBlock_internal(ZSTD_CCtx* zc, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
2422 {
2423     ZSTD_blockCompressor const blockCompressor = ZSTD_selectBlockCompressor(zc->params.cParams.strategy, zc->lowLimit < zc->dictLimit);
2424     const BYTE* const base = zc->base;
2425     const BYTE* const istart = (const BYTE*)src;
2426     const U32 current = (U32)(istart-base);
2427     if (srcSize < MIN_CBLOCK_SIZE+ZSTD_blockHeaderSize+1) return 0;   /* don't even attempt compression below a certain srcSize */
2428     ZSTD_resetSeqStore(&(zc->seqStore));
2429     if (current > zc->nextToUpdate + 384)
2430         zc->nextToUpdate = current - MIN(192, (U32)(current - zc->nextToUpdate - 384));   /* limited update after finding a very long match */
2431     blockCompressor(zc, src, srcSize);
2432     return ZSTD_compressSequences(zc, dst, dstCapacity, srcSize);
2433 }
2434
2435
2436 /*! ZSTD_compress_generic() :
2437 *   Compress a chunk of data into one or multiple blocks.
2438 *   All blocks will be terminated, all input will be consumed.
2439 *   Function will issue an error if there is not enough `dstCapacity` to hold the compressed content.
2440 *   Frame is supposed already started (header already produced)
2441 *   @return : compressed size, or an error code
2442 */
2443 static size_t ZSTD_compress_generic (ZSTD_CCtx* cctx,
2444                                      void* dst, size_t dstCapacity,
2445                                const void* src, size_t srcSize,
2446                                      U32 lastFrameChunk)
2447 {
2448     size_t blockSize = cctx->blockSize;
2449     size_t remaining = srcSize;
2450     const BYTE* ip = (const BYTE*)src;
2451     BYTE* const ostart = (BYTE*)dst;
2452     BYTE* op = ostart;
2453     U32 const maxDist = 1 << cctx->params.cParams.windowLog;
2454
2455     if (cctx->params.fParams.checksumFlag && srcSize)
2456         XXH64_update(&cctx->xxhState, src, srcSize);
2457
2458     while (remaining) {
2459         U32 const lastBlock = lastFrameChunk & (blockSize >= remaining);
2460         size_t cSize;
2461
2462         if (dstCapacity < ZSTD_blockHeaderSize + MIN_CBLOCK_SIZE)
2463             return ERROR(dstSize_tooSmall);   /* not enough space to store compressed block */
2464         if (remaining < blockSize) blockSize = remaining;
2465
2466         /* preemptive overflow correction */
2467         if (cctx->lowLimit > (3U<<29)) {
2468             U32 const cycleMask = (1 << ZSTD_cycleLog(cctx->params.cParams.hashLog, cctx->params.cParams.strategy)) - 1;
2469             U32 const current = (U32)(ip - cctx->base);
2470             U32 const newCurrent = (current & cycleMask) + (1 << cctx->params.cParams.windowLog);
2471             U32 const correction = current - newCurrent;
2472             ZSTD_STATIC_ASSERT(ZSTD_WINDOWLOG_MAX_64 <= 30);
2473             ZSTD_reduceIndex(cctx, correction);
2474             cctx->base += correction;
2475             cctx->dictBase += correction;
2476             cctx->lowLimit -= correction;
2477             cctx->dictLimit -= correction;
2478             if (cctx->nextToUpdate < correction) cctx->nextToUpdate = 0;
2479             else cctx->nextToUpdate -= correction;
2480         }
2481
2482         if ((U32)(ip+blockSize - cctx->base) > cctx->loadedDictEnd + maxDist) {
2483             /* enforce maxDist */
2484             U32 const newLowLimit = (U32)(ip+blockSize - cctx->base) - maxDist;
2485             if (cctx->lowLimit < newLowLimit) cctx->lowLimit = newLowLimit;
2486             if (cctx->dictLimit < cctx->lowLimit) cctx->dictLimit = cctx->lowLimit;
2487         }
2488
2489         cSize = ZSTD_compressBlock_internal(cctx, op+ZSTD_blockHeaderSize, dstCapacity-ZSTD_blockHeaderSize, ip, blockSize);
2490         if (ZSTD_isError(cSize)) return cSize;
2491
2492         if (cSize == 0) {  /* block is not compressible */
2493             U32 const cBlockHeader24 = lastBlock + (((U32)bt_raw)<<1) + (U32)(blockSize << 3);
2494             if (blockSize + ZSTD_blockHeaderSize > dstCapacity) return ERROR(dstSize_tooSmall);
2495             MEM_writeLE32(op, cBlockHeader24);   /* no pb, 4th byte will be overwritten */
2496             memcpy(op + ZSTD_blockHeaderSize, ip, blockSize);
2497             cSize = ZSTD_blockHeaderSize+blockSize;
2498         } else {
2499             U32 const cBlockHeader24 = lastBlock + (((U32)bt_compressed)<<1) + (U32)(cSize << 3);
2500             MEM_writeLE24(op, cBlockHeader24);
2501             cSize += ZSTD_blockHeaderSize;
2502         }
2503
2504         remaining -= blockSize;
2505         dstCapacity -= cSize;
2506         ip += blockSize;
2507         op += cSize;
2508     }
2509
2510     if (lastFrameChunk && (op>ostart)) cctx->stage = ZSTDcs_ending;
2511     return op-ostart;
2512 }
2513
2514
2515 static size_t ZSTD_writeFrameHeader(void* dst, size_t dstCapacity,
2516                                     ZSTD_parameters params, U64 pledgedSrcSize, U32 dictID)
2517 {   BYTE* const op = (BYTE*)dst;
2518     U32   const dictIDSizeCodeLength = (dictID>0) + (dictID>=256) + (dictID>=65536);   /* 0-3 */
2519     U32   const dictIDSizeCode = params.fParams.noDictIDFlag ? 0 : dictIDSizeCodeLength;   /* 0-3 */
2520     U32   const checksumFlag = params.fParams.checksumFlag>0;
2521     U32   const windowSize = 1U << params.cParams.windowLog;
2522     U32   const singleSegment = params.fParams.contentSizeFlag && (windowSize >= pledgedSrcSize);
2523     BYTE  const windowLogByte = (BYTE)((params.cParams.windowLog - ZSTD_WINDOWLOG_ABSOLUTEMIN) << 3);
2524     U32   const fcsCode = params.fParams.contentSizeFlag ?
2525                      (pledgedSrcSize>=256) + (pledgedSrcSize>=65536+256) + (pledgedSrcSize>=0xFFFFFFFFU) :   /* 0-3 */
2526                       0;
2527     BYTE  const frameHeaderDecriptionByte = (BYTE)(dictIDSizeCode + (checksumFlag<<2) + (singleSegment<<5) + (fcsCode<<6) );
2528     size_t pos;
2529
2530     if (dstCapacity < ZSTD_frameHeaderSize_max) return ERROR(dstSize_tooSmall);
2531     DEBUGLOG(5, "ZSTD_writeFrameHeader : dictIDFlag : %u \n", !params.fParams.noDictIDFlag);
2532     DEBUGLOG(5, "ZSTD_writeFrameHeader : dictID : %u \n", dictID);
2533     DEBUGLOG(5, "ZSTD_writeFrameHeader : dictIDSizeCode : %u \n", dictIDSizeCode);
2534
2535     MEM_writeLE32(dst, ZSTD_MAGICNUMBER);
2536     op[4] = frameHeaderDecriptionByte; pos=5;
2537     if (!singleSegment) op[pos++] = windowLogByte;
2538     switch(dictIDSizeCode)
2539     {
2540         default:   /* impossible */
2541         case 0 : break;
2542         case 1 : op[pos] = (BYTE)(dictID); pos++; break;
2543         case 2 : MEM_writeLE16(op+pos, (U16)dictID); pos+=2; break;
2544         case 3 : MEM_writeLE32(op+pos, dictID); pos+=4; break;
2545     }
2546     switch(fcsCode)
2547     {
2548         default:   /* impossible */
2549         case 0 : if (singleSegment) op[pos++] = (BYTE)(pledgedSrcSize); break;
2550         case 1 : MEM_writeLE16(op+pos, (U16)(pledgedSrcSize-256)); pos+=2; break;
2551         case 2 : MEM_writeLE32(op+pos, (U32)(pledgedSrcSize)); pos+=4; break;
2552         case 3 : MEM_writeLE64(op+pos, (U64)(pledgedSrcSize)); pos+=8; break;
2553     }
2554     return pos;
2555 }
2556
2557
2558 static size_t ZSTD_compressContinue_internal (ZSTD_CCtx* cctx,
2559                               void* dst, size_t dstCapacity,
2560                         const void* src, size_t srcSize,
2561                                U32 frame, U32 lastFrameChunk)
2562 {
2563     const BYTE* const ip = (const BYTE*) src;
2564     size_t fhSize = 0;
2565
2566     if (cctx->stage==ZSTDcs_created) return ERROR(stage_wrong);   /* missing init (ZSTD_compressBegin) */
2567
2568     if (frame && (cctx->stage==ZSTDcs_init)) {
2569         fhSize = ZSTD_writeFrameHeader(dst, dstCapacity, cctx->params, cctx->frameContentSize, cctx->dictID);
2570         if (ZSTD_isError(fhSize)) return fhSize;
2571         dstCapacity -= fhSize;
2572         dst = (char*)dst + fhSize;
2573         cctx->stage = ZSTDcs_ongoing;
2574     }
2575
2576     /* Check if blocks follow each other */
2577     if (src != cctx->nextSrc) {
2578         /* not contiguous */
2579         ptrdiff_t const delta = cctx->nextSrc - ip;
2580         cctx->lowLimit = cctx->dictLimit;
2581         cctx->dictLimit = (U32)(cctx->nextSrc - cctx->base);
2582         cctx->dictBase = cctx->base;
2583         cctx->base -= delta;
2584         cctx->nextToUpdate = cctx->dictLimit;
2585         if (cctx->dictLimit - cctx->lowLimit < HASH_READ_SIZE) cctx->lowLimit = cctx->dictLimit;   /* too small extDict */
2586     }
2587
2588     /* if input and dictionary overlap : reduce dictionary (area presumed modified by input) */
2589     if ((ip+srcSize > cctx->dictBase + cctx->lowLimit) & (ip < cctx->dictBase + cctx->dictLimit)) {
2590         ptrdiff_t const highInputIdx = (ip + srcSize) - cctx->dictBase;
2591         U32 const lowLimitMax = (highInputIdx > (ptrdiff_t)cctx->dictLimit) ? cctx->dictLimit : (U32)highInputIdx;
2592         cctx->lowLimit = lowLimitMax;
2593     }
2594
2595     cctx->nextSrc = ip + srcSize;
2596
2597     if (srcSize) {
2598         size_t const cSize = frame ?
2599                              ZSTD_compress_generic (cctx, dst, dstCapacity, src, srcSize, lastFrameChunk) :
2600                              ZSTD_compressBlock_internal (cctx, dst, dstCapacity, src, srcSize);
2601         if (ZSTD_isError(cSize)) return cSize;
2602         cctx->consumedSrcSize += srcSize;
2603         return cSize + fhSize;
2604     } else
2605         return fhSize;
2606 }
2607
2608
2609 size_t ZSTD_compressContinue (ZSTD_CCtx* cctx,
2610                               void* dst, size_t dstCapacity,
2611                         const void* src, size_t srcSize)
2612 {
2613     return ZSTD_compressContinue_internal(cctx, dst, dstCapacity, src, srcSize, 1 /* frame mode */, 0 /* last chunk */);
2614 }
2615
2616
2617 size_t ZSTD_getBlockSizeMax(ZSTD_CCtx* cctx)
2618 {
2619     return MIN (ZSTD_BLOCKSIZE_ABSOLUTEMAX, 1 << cctx->params.cParams.windowLog);
2620 }
2621
2622 size_t ZSTD_compressBlock(ZSTD_CCtx* cctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
2623 {
2624     size_t const blockSizeMax = ZSTD_getBlockSizeMax(cctx);
2625     if (srcSize > blockSizeMax) return ERROR(srcSize_wrong);
2626     return ZSTD_compressContinue_internal(cctx, dst, dstCapacity, src, srcSize, 0 /* frame mode */, 0 /* last chunk */);
2627 }
2628
2629 /*! ZSTD_loadDictionaryContent() :
2630  *  @return : 0, or an error code
2631  */
2632 static size_t ZSTD_loadDictionaryContent(ZSTD_CCtx* zc, const void* src, size_t srcSize)
2633 {
2634     const BYTE* const ip = (const BYTE*) src;
2635     const BYTE* const iend = ip + srcSize;
2636
2637     /* input becomes current prefix */
2638     zc->lowLimit = zc->dictLimit;
2639     zc->dictLimit = (U32)(zc->nextSrc - zc->base);
2640     zc->dictBase = zc->base;
2641     zc->base += ip - zc->nextSrc;
2642     zc->nextToUpdate = zc->dictLimit;
2643     zc->loadedDictEnd = zc->forceWindow ? 0 : (U32)(iend - zc->base);
2644
2645     zc->nextSrc = iend;
2646     if (srcSize <= HASH_READ_SIZE) return 0;
2647
2648     switch(zc->params.cParams.strategy)
2649     {
2650     case ZSTD_fast:
2651         ZSTD_fillHashTable (zc, iend, zc->params.cParams.searchLength);
2652         break;
2653
2654     case ZSTD_dfast:
2655         ZSTD_fillDoubleHashTable (zc, iend, zc->params.cParams.searchLength);
2656         break;
2657
2658     case ZSTD_greedy:
2659     case ZSTD_lazy:
2660     case ZSTD_lazy2:
2661         if (srcSize >= HASH_READ_SIZE)
2662             ZSTD_insertAndFindFirstIndex(zc, iend-HASH_READ_SIZE, zc->params.cParams.searchLength);
2663         break;
2664
2665     case ZSTD_btlazy2:
2666     case ZSTD_btopt:
2667     case ZSTD_btopt2:
2668         if (srcSize >= HASH_READ_SIZE)
2669             ZSTD_updateTree(zc, iend-HASH_READ_SIZE, iend, 1 << zc->params.cParams.searchLog, zc->params.cParams.searchLength);
2670         break;
2671
2672     default:
2673         return ERROR(GENERIC);   /* strategy doesn't exist; impossible */
2674     }
2675
2676     zc->nextToUpdate = (U32)(iend - zc->base);
2677     return 0;
2678 }
2679
2680
2681 /* Dictionaries that assign zero probability to symbols that show up causes problems
2682    when FSE encoding.  Refuse dictionaries that assign zero probability to symbols
2683    that we may encounter during compression.
2684    NOTE: This behavior is not standard and could be improved in the future. */
2685 static size_t ZSTD_checkDictNCount(short* normalizedCounter, unsigned dictMaxSymbolValue, unsigned maxSymbolValue) {
2686     U32 s;
2687     if (dictMaxSymbolValue < maxSymbolValue) return ERROR(dictionary_corrupted);
2688     for (s = 0; s <= maxSymbolValue; ++s) {
2689         if (normalizedCounter[s] == 0) return ERROR(dictionary_corrupted);
2690     }
2691     return 0;
2692 }
2693
2694
2695 /* Dictionary format :
2696  * See :
2697  * https://github.com/facebook/zstd/blob/master/doc/zstd_compression_format.md#dictionary-format
2698  */
2699 /*! ZSTD_loadZstdDictionary() :
2700  * @return : 0, or an error code
2701  *  assumptions : magic number supposed already checked
2702  *                dictSize supposed > 8
2703  */
2704 static size_t ZSTD_loadZstdDictionary(ZSTD_CCtx* cctx, const void* dict, size_t dictSize)
2705 {
2706     const BYTE* dictPtr = (const BYTE*)dict;
2707     const BYTE* const dictEnd = dictPtr + dictSize;
2708     short offcodeNCount[MaxOff+1];
2709     unsigned offcodeMaxValue = MaxOff;
2710     BYTE scratchBuffer[1<<MAX(MLFSELog,LLFSELog)];
2711
2712     dictPtr += 4;   /* skip magic number */
2713     cctx->dictID = cctx->params.fParams.noDictIDFlag ? 0 :  MEM_readLE32(dictPtr);
2714     dictPtr += 4;
2715
2716     {   size_t const hufHeaderSize = HUF_readCTable(cctx->hufCTable, 255, dictPtr, dictEnd-dictPtr);
2717         if (HUF_isError(hufHeaderSize)) return ERROR(dictionary_corrupted);
2718         dictPtr += hufHeaderSize;
2719     }
2720
2721     {   unsigned offcodeLog;
2722         size_t const offcodeHeaderSize = FSE_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dictPtr, dictEnd-dictPtr);
2723         if (FSE_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted);
2724         if (offcodeLog > OffFSELog) return ERROR(dictionary_corrupted);
2725         /* Defer checking offcodeMaxValue because we need to know the size of the dictionary content */
2726         CHECK_E( FSE_buildCTable_wksp(cctx->offcodeCTable, offcodeNCount, offcodeMaxValue, offcodeLog, scratchBuffer, sizeof(scratchBuffer)),
2727                  dictionary_corrupted);
2728         dictPtr += offcodeHeaderSize;
2729     }
2730
2731     {   short matchlengthNCount[MaxML+1];
2732         unsigned matchlengthMaxValue = MaxML, matchlengthLog;
2733         size_t const matchlengthHeaderSize = FSE_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd-dictPtr);
2734         if (FSE_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted);
2735         if (matchlengthLog > MLFSELog) return ERROR(dictionary_corrupted);
2736         /* Every match length code must have non-zero probability */
2737         CHECK_F( ZSTD_checkDictNCount(matchlengthNCount, matchlengthMaxValue, MaxML));
2738         CHECK_E( FSE_buildCTable_wksp(cctx->matchlengthCTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog, scratchBuffer, sizeof(scratchBuffer)),
2739                  dictionary_corrupted);
2740         dictPtr += matchlengthHeaderSize;
2741     }
2742
2743     {   short litlengthNCount[MaxLL+1];
2744         unsigned litlengthMaxValue = MaxLL, litlengthLog;
2745         size_t const litlengthHeaderSize = FSE_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd-dictPtr);
2746         if (FSE_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted);
2747         if (litlengthLog > LLFSELog) return ERROR(dictionary_corrupted);
2748         /* Every literal length code must have non-zero probability */
2749         CHECK_F( ZSTD_checkDictNCount(litlengthNCount, litlengthMaxValue, MaxLL));
2750         CHECK_E( FSE_buildCTable_wksp(cctx->litlengthCTable, litlengthNCount, litlengthMaxValue, litlengthLog, scratchBuffer, sizeof(scratchBuffer)),
2751                  dictionary_corrupted);
2752         dictPtr += litlengthHeaderSize;
2753     }
2754
2755     if (dictPtr+12 > dictEnd) return ERROR(dictionary_corrupted);
2756     cctx->rep[0] = MEM_readLE32(dictPtr+0);
2757     cctx->rep[1] = MEM_readLE32(dictPtr+4);
2758     cctx->rep[2] = MEM_readLE32(dictPtr+8);
2759     dictPtr += 12;
2760
2761     {   size_t const dictContentSize = (size_t)(dictEnd - dictPtr);
2762         U32 offcodeMax = MaxOff;
2763         if (dictContentSize <= ((U32)-1) - 128 KB) {
2764             U32 const maxOffset = (U32)dictContentSize + 128 KB; /* The maximum offset that must be supported */
2765             offcodeMax = ZSTD_highbit32(maxOffset); /* Calculate minimum offset code required to represent maxOffset */
2766         }
2767         /* All offset values <= dictContentSize + 128 KB must be representable */
2768         CHECK_F (ZSTD_checkDictNCount(offcodeNCount, offcodeMaxValue, MIN(offcodeMax, MaxOff)));
2769         /* All repCodes must be <= dictContentSize and != 0*/
2770         {   U32 u;
2771             for (u=0; u<3; u++) {
2772                 if (cctx->rep[u] == 0) return ERROR(dictionary_corrupted);
2773                 if (cctx->rep[u] > dictContentSize) return ERROR(dictionary_corrupted);
2774         }   }
2775
2776         cctx->fseCTables_ready = 1;
2777         cctx->hufCTable_repeatMode = HUF_repeat_valid;
2778         return ZSTD_loadDictionaryContent(cctx, dictPtr, dictContentSize);
2779     }
2780 }
2781
2782 /** ZSTD_compress_insertDictionary() :
2783 *   @return : 0, or an error code */
2784 static size_t ZSTD_compress_insertDictionary(ZSTD_CCtx* cctx, const void* dict, size_t dictSize)
2785 {
2786     if ((dict==NULL) || (dictSize<=8)) return 0;
2787
2788     /* dict as pure content */
2789     if ((MEM_readLE32(dict) != ZSTD_DICT_MAGIC) || (cctx->forceRawDict))
2790         return ZSTD_loadDictionaryContent(cctx, dict, dictSize);
2791
2792     /* dict as zstd dictionary */
2793     return ZSTD_loadZstdDictionary(cctx, dict, dictSize);
2794 }
2795
2796 /*! ZSTD_compressBegin_internal() :
2797 *   @return : 0, or an error code */
2798 static size_t ZSTD_compressBegin_internal(ZSTD_CCtx* cctx,
2799                              const void* dict, size_t dictSize,
2800                                    ZSTD_parameters params, U64 pledgedSrcSize)
2801 {
2802     ZSTD_compResetPolicy_e const crp = dictSize ? ZSTDcrp_fullReset : ZSTDcrp_continue;
2803     assert(!ZSTD_isError(ZSTD_checkCParams(params.cParams)));
2804     CHECK_F(ZSTD_resetCCtx_internal(cctx, params, pledgedSrcSize, crp));
2805     return ZSTD_compress_insertDictionary(cctx, dict, dictSize);
2806 }
2807
2808
2809 /*! ZSTD_compressBegin_advanced() :
2810 *   @return : 0, or an error code */
2811 size_t ZSTD_compressBegin_advanced(ZSTD_CCtx* cctx,
2812                              const void* dict, size_t dictSize,
2813                                    ZSTD_parameters params, unsigned long long pledgedSrcSize)
2814 {
2815     /* compression parameters verification and optimization */
2816     CHECK_F(ZSTD_checkCParams(params.cParams));
2817     return ZSTD_compressBegin_internal(cctx, dict, dictSize, params, pledgedSrcSize);
2818 }
2819
2820
2821 size_t ZSTD_compressBegin_usingDict(ZSTD_CCtx* cctx, const void* dict, size_t dictSize, int compressionLevel)
2822 {
2823     ZSTD_parameters const params = ZSTD_getParams(compressionLevel, 0, dictSize);
2824     return ZSTD_compressBegin_internal(cctx, dict, dictSize, params, 0);
2825 }
2826
2827
2828 size_t ZSTD_compressBegin(ZSTD_CCtx* cctx, int compressionLevel)
2829 {
2830     return ZSTD_compressBegin_usingDict(cctx, NULL, 0, compressionLevel);
2831 }
2832
2833
2834 /*! ZSTD_writeEpilogue() :
2835 *   Ends a frame.
2836 *   @return : nb of bytes written into dst (or an error code) */
2837 static size_t ZSTD_writeEpilogue(ZSTD_CCtx* cctx, void* dst, size_t dstCapacity)
2838 {
2839     BYTE* const ostart = (BYTE*)dst;
2840     BYTE* op = ostart;
2841     size_t fhSize = 0;
2842
2843     if (cctx->stage == ZSTDcs_created) return ERROR(stage_wrong);  /* init missing */
2844
2845     /* special case : empty frame */
2846     if (cctx->stage == ZSTDcs_init) {
2847         fhSize = ZSTD_writeFrameHeader(dst, dstCapacity, cctx->params, 0, 0);
2848         if (ZSTD_isError(fhSize)) return fhSize;
2849         dstCapacity -= fhSize;
2850         op += fhSize;
2851         cctx->stage = ZSTDcs_ongoing;
2852     }
2853
2854     if (cctx->stage != ZSTDcs_ending) {
2855         /* write one last empty block, make it the "last" block */
2856         U32 const cBlockHeader24 = 1 /* last block */ + (((U32)bt_raw)<<1) + 0;
2857         if (dstCapacity<4) return ERROR(dstSize_tooSmall);
2858         MEM_writeLE32(op, cBlockHeader24);
2859         op += ZSTD_blockHeaderSize;
2860         dstCapacity -= ZSTD_blockHeaderSize;
2861     }
2862
2863     if (cctx->params.fParams.checksumFlag) {
2864         U32 const checksum = (U32) XXH64_digest(&cctx->xxhState);
2865         if (dstCapacity<4) return ERROR(dstSize_tooSmall);
2866         MEM_writeLE32(op, checksum);
2867         op += 4;
2868     }
2869
2870     cctx->stage = ZSTDcs_created;  /* return to "created but no init" status */
2871     return op-ostart;
2872 }
2873
2874
2875 size_t ZSTD_compressEnd (ZSTD_CCtx* cctx,
2876                          void* dst, size_t dstCapacity,
2877                    const void* src, size_t srcSize)
2878 {
2879     size_t endResult;
2880     size_t const cSize = ZSTD_compressContinue_internal(cctx, dst, dstCapacity, src, srcSize, 1 /* frame mode */, 1 /* last chunk */);
2881     if (ZSTD_isError(cSize)) return cSize;
2882     endResult = ZSTD_writeEpilogue(cctx, (char*)dst + cSize, dstCapacity-cSize);
2883     if (ZSTD_isError(endResult)) return endResult;
2884     if (cctx->params.fParams.contentSizeFlag) {  /* control src size */
2885         if (cctx->frameContentSize != cctx->consumedSrcSize) return ERROR(srcSize_wrong);
2886     }
2887     return cSize + endResult;
2888 }
2889
2890
2891 static size_t ZSTD_compress_internal (ZSTD_CCtx* cctx,
2892                                void* dst, size_t dstCapacity,
2893                          const void* src, size_t srcSize,
2894                          const void* dict,size_t dictSize,
2895                                ZSTD_parameters params)
2896 {
2897     CHECK_F(ZSTD_compressBegin_internal(cctx, dict, dictSize, params, srcSize));
2898     return ZSTD_compressEnd(cctx, dst,  dstCapacity, src, srcSize);
2899 }
2900
2901 size_t ZSTD_compress_advanced (ZSTD_CCtx* ctx,
2902                                void* dst, size_t dstCapacity,
2903                          const void* src, size_t srcSize,
2904                          const void* dict,size_t dictSize,
2905                                ZSTD_parameters params)
2906 {
2907     CHECK_F(ZSTD_checkCParams(params.cParams));
2908     return ZSTD_compress_internal(ctx, dst, dstCapacity, src, srcSize, dict, dictSize, params);
2909 }
2910
2911 size_t ZSTD_compress_usingDict(ZSTD_CCtx* ctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize,
2912                                const void* dict, size_t dictSize, int compressionLevel)
2913 {
2914     ZSTD_parameters params = ZSTD_getParams(compressionLevel, srcSize, dict ? dictSize : 0);
2915     params.fParams.contentSizeFlag = 1;
2916     return ZSTD_compress_internal(ctx, dst, dstCapacity, src, srcSize, dict, dictSize, params);
2917 }
2918
2919 size_t ZSTD_compressCCtx (ZSTD_CCtx* ctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize, int compressionLevel)
2920 {
2921     return ZSTD_compress_usingDict(ctx, dst, dstCapacity, src, srcSize, NULL, 0, compressionLevel);
2922 }
2923
2924 size_t ZSTD_compress(void* dst, size_t dstCapacity, const void* src, size_t srcSize, int compressionLevel)
2925 {
2926     size_t result;
2927     ZSTD_CCtx ctxBody;
2928     memset(&ctxBody, 0, sizeof(ctxBody));
2929     memcpy(&ctxBody.customMem, &defaultCustomMem, sizeof(ZSTD_customMem));
2930     result = ZSTD_compressCCtx(&ctxBody, dst, dstCapacity, src, srcSize, compressionLevel);
2931     ZSTD_free(ctxBody.workSpace, defaultCustomMem);  /* can't free ctxBody itself, as it's on stack; free only heap content */
2932     return result;
2933 }
2934
2935
2936 /* =====  Dictionary API  ===== */
2937
2938 struct ZSTD_CDict_s {
2939     void* dictBuffer;
2940     const void* dictContent;
2941     size_t dictContentSize;
2942     ZSTD_CCtx* refContext;
2943 };  /* typedef'd tp ZSTD_CDict within "zstd.h" */
2944
2945 size_t ZSTD_sizeof_CDict(const ZSTD_CDict* cdict)
2946 {
2947     if (cdict==NULL) return 0;   /* support sizeof on NULL */
2948     return ZSTD_sizeof_CCtx(cdict->refContext) + (cdict->dictBuffer ? cdict->dictContentSize : 0) + sizeof(*cdict);
2949 }
2950
2951 static ZSTD_parameters ZSTD_makeParams(ZSTD_compressionParameters cParams, ZSTD_frameParameters fParams)
2952 {
2953     ZSTD_parameters params;
2954     params.cParams = cParams;
2955     params.fParams = fParams;
2956     return params;
2957 }
2958
2959 ZSTD_CDict* ZSTD_createCDict_advanced(const void* dictBuffer, size_t dictSize, unsigned byReference,
2960                                       ZSTD_compressionParameters cParams, ZSTD_customMem customMem)
2961 {
2962     if (!customMem.customAlloc && !customMem.customFree) customMem = defaultCustomMem;
2963     if (!customMem.customAlloc || !customMem.customFree) return NULL;
2964
2965     {   ZSTD_CDict* const cdict = (ZSTD_CDict*) ZSTD_malloc(sizeof(ZSTD_CDict), customMem);
2966         ZSTD_CCtx* const cctx = ZSTD_createCCtx_advanced(customMem);
2967
2968         if (!cdict || !cctx) {
2969             ZSTD_free(cdict, customMem);
2970             ZSTD_freeCCtx(cctx);
2971             return NULL;
2972         }
2973
2974         if ((byReference) || (!dictBuffer) || (!dictSize)) {
2975             cdict->dictBuffer = NULL;
2976             cdict->dictContent = dictBuffer;
2977         } else {
2978             void* const internalBuffer = ZSTD_malloc(dictSize, customMem);
2979             if (!internalBuffer) { ZSTD_free(cctx, customMem); ZSTD_free(cdict, customMem); return NULL; }
2980             memcpy(internalBuffer, dictBuffer, dictSize);
2981             cdict->dictBuffer = internalBuffer;
2982             cdict->dictContent = internalBuffer;
2983         }
2984
2985         {   ZSTD_frameParameters const fParams = { 0 /* contentSizeFlag */, 0 /* checksumFlag */, 0 /* noDictIDFlag */ };   /* dummy */
2986             ZSTD_parameters const params = ZSTD_makeParams(cParams, fParams);
2987             size_t const errorCode = ZSTD_compressBegin_advanced(cctx, cdict->dictContent, dictSize, params, 0);
2988             if (ZSTD_isError(errorCode)) {
2989                 ZSTD_free(cdict->dictBuffer, customMem);
2990                 ZSTD_free(cdict, customMem);
2991                 ZSTD_freeCCtx(cctx);
2992                 return NULL;
2993         }   }
2994
2995         cdict->refContext = cctx;
2996         cdict->dictContentSize = dictSize;
2997         return cdict;
2998     }
2999 }
3000
3001 ZSTD_CDict* ZSTD_createCDict(const void* dict, size_t dictSize, int compressionLevel)
3002 {
3003     ZSTD_customMem const allocator = { NULL, NULL, NULL };
3004     ZSTD_compressionParameters cParams = ZSTD_getCParams(compressionLevel, 0, dictSize);
3005     return ZSTD_createCDict_advanced(dict, dictSize, 0, cParams, allocator);
3006 }
3007
3008 ZSTD_CDict* ZSTD_createCDict_byReference(const void* dict, size_t dictSize, int compressionLevel)
3009 {
3010     ZSTD_customMem const allocator = { NULL, NULL, NULL };
3011     ZSTD_compressionParameters cParams = ZSTD_getCParams(compressionLevel, 0, dictSize);
3012     return ZSTD_createCDict_advanced(dict, dictSize, 1, cParams, allocator);
3013 }
3014
3015 size_t ZSTD_freeCDict(ZSTD_CDict* cdict)
3016 {
3017     if (cdict==NULL) return 0;   /* support free on NULL */
3018     {   ZSTD_customMem const cMem = cdict->refContext->customMem;
3019         ZSTD_freeCCtx(cdict->refContext);
3020         ZSTD_free(cdict->dictBuffer, cMem);
3021         ZSTD_free(cdict, cMem);
3022         return 0;
3023     }
3024 }
3025
3026 static ZSTD_parameters ZSTD_getParamsFromCDict(const ZSTD_CDict* cdict) {
3027     return ZSTD_getParamsFromCCtx(cdict->refContext);
3028 }
3029
3030 /* ZSTD_compressBegin_usingCDict_advanced() :
3031  * cdict must be != NULL */
3032 size_t ZSTD_compressBegin_usingCDict_advanced(
3033     ZSTD_CCtx* const cctx, const ZSTD_CDict* const cdict,
3034     ZSTD_frameParameters const fParams, unsigned long long const pledgedSrcSize)
3035 {
3036     if (cdict==NULL) return ERROR(GENERIC);  /* does not support NULL cdict */
3037     DEBUGLOG(5, "ZSTD_compressBegin_usingCDict_advanced : dictIDFlag == %u \n", !fParams.noDictIDFlag);
3038     if (cdict->dictContentSize)
3039         CHECK_F( ZSTD_copyCCtx_internal(cctx, cdict->refContext, fParams, pledgedSrcSize) )
3040     else {
3041         ZSTD_parameters params = cdict->refContext->params;
3042         params.fParams = fParams;
3043         CHECK_F(ZSTD_compressBegin_internal(cctx, NULL, 0, params, pledgedSrcSize));
3044     }
3045     return 0;
3046 }
3047
3048 /* ZSTD_compressBegin_usingCDict() :
3049  * pledgedSrcSize=0 means "unknown"
3050  * if pledgedSrcSize>0, it will enable contentSizeFlag */
3051 size_t ZSTD_compressBegin_usingCDict(ZSTD_CCtx* cctx, const ZSTD_CDict* cdict)
3052 {
3053     ZSTD_frameParameters const fParams = { 0 /*content*/, 0 /*checksum*/, 0 /*noDictID*/ };
3054     DEBUGLOG(5, "ZSTD_compressBegin_usingCDict : dictIDFlag == %u \n", !fParams.noDictIDFlag);
3055     return ZSTD_compressBegin_usingCDict_advanced(cctx, cdict, fParams, 0);
3056 }
3057
3058 size_t ZSTD_compress_usingCDict_advanced(ZSTD_CCtx* cctx,
3059                                 void* dst, size_t dstCapacity,
3060                                 const void* src, size_t srcSize,
3061                                 const ZSTD_CDict* cdict, ZSTD_frameParameters fParams)
3062 {
3063     CHECK_F (ZSTD_compressBegin_usingCDict_advanced(cctx, cdict, fParams, srcSize));   /* will check if cdict != NULL */
3064     return ZSTD_compressEnd(cctx, dst, dstCapacity, src, srcSize);
3065 }
3066
3067 /*! ZSTD_compress_usingCDict() :
3068  *  Compression using a digested Dictionary.
3069  *  Faster startup than ZSTD_compress_usingDict(), recommended when same dictionary is used multiple times.
3070  *  Note that compression parameters are decided at CDict creation time
3071  *  while frame parameters are hardcoded */
3072 size_t ZSTD_compress_usingCDict(ZSTD_CCtx* cctx,
3073                                 void* dst, size_t dstCapacity,
3074                                 const void* src, size_t srcSize,
3075                                 const ZSTD_CDict* cdict)
3076 {
3077     ZSTD_frameParameters const fParams = { 1 /*content*/, 0 /*checksum*/, 0 /*noDictID*/ };
3078     return ZSTD_compress_usingCDict_advanced(cctx, dst, dstCapacity, src, srcSize, cdict, fParams);
3079 }
3080
3081
3082
3083 /* ******************************************************************
3084 *  Streaming
3085 ********************************************************************/
3086
3087 typedef enum { zcss_init, zcss_load, zcss_flush, zcss_final } ZSTD_cStreamStage;
3088
3089 struct ZSTD_CStream_s {
3090     ZSTD_CCtx* cctx;
3091     ZSTD_CDict* cdictLocal;
3092     const ZSTD_CDict* cdict;
3093     char*  inBuff;
3094     size_t inBuffSize;
3095     size_t inToCompress;
3096     size_t inBuffPos;
3097     size_t inBuffTarget;
3098     size_t blockSize;
3099     char*  outBuff;
3100     size_t outBuffSize;
3101     size_t outBuffContentSize;
3102     size_t outBuffFlushedSize;
3103     ZSTD_cStreamStage stage;
3104     U32    checksum;
3105     U32    frameEnded;
3106     U64    pledgedSrcSize;
3107     ZSTD_parameters params;
3108     ZSTD_customMem customMem;
3109 };   /* typedef'd to ZSTD_CStream within "zstd.h" */
3110
3111 ZSTD_CStream* ZSTD_createCStream(void)
3112 {
3113     return ZSTD_createCStream_advanced(defaultCustomMem);
3114 }
3115
3116 ZSTD_CStream* ZSTD_createCStream_advanced(ZSTD_customMem customMem)
3117 {
3118     ZSTD_CStream* zcs;
3119
3120     if (!customMem.customAlloc && !customMem.customFree) customMem = defaultCustomMem;
3121     if (!customMem.customAlloc || !customMem.customFree) return NULL;
3122
3123     zcs = (ZSTD_CStream*)ZSTD_malloc(sizeof(ZSTD_CStream), customMem);
3124     if (zcs==NULL) return NULL;
3125     memset(zcs, 0, sizeof(ZSTD_CStream));
3126     memcpy(&zcs->customMem, &customMem, sizeof(ZSTD_customMem));
3127     zcs->cctx = ZSTD_createCCtx_advanced(customMem);
3128     if (zcs->cctx == NULL) { ZSTD_freeCStream(zcs); return NULL; }
3129     return zcs;
3130 }
3131
3132 size_t ZSTD_freeCStream(ZSTD_CStream* zcs)
3133 {
3134     if (zcs==NULL) return 0;   /* support free on NULL */
3135     {   ZSTD_customMem const cMem = zcs->customMem;
3136         ZSTD_freeCCtx(zcs->cctx);
3137         zcs->cctx = NULL;
3138         ZSTD_freeCDict(zcs->cdictLocal);
3139         zcs->cdictLocal = NULL;
3140         ZSTD_free(zcs->inBuff, cMem);
3141         zcs->inBuff = NULL;
3142         ZSTD_free(zcs->outBuff, cMem);
3143         zcs->outBuff = NULL;
3144         ZSTD_free(zcs, cMem);
3145         return 0;
3146     }
3147 }
3148
3149
3150 /*======   Initialization   ======*/
3151
3152 size_t ZSTD_CStreamInSize(void)  { return ZSTD_BLOCKSIZE_ABSOLUTEMAX; }
3153
3154 size_t ZSTD_CStreamOutSize(void)
3155 {
3156     return ZSTD_compressBound(ZSTD_BLOCKSIZE_ABSOLUTEMAX) + ZSTD_blockHeaderSize + 4 /* 32-bits hash */ ;
3157 }
3158
3159 static size_t ZSTD_resetCStream_internal(ZSTD_CStream* zcs, unsigned long long pledgedSrcSize)
3160 {
3161     if (zcs->inBuffSize==0) return ERROR(stage_wrong);   /* zcs has not been init at least once => can't reset */
3162
3163     DEBUGLOG(5, "ZSTD_resetCStream_internal : dictIDFlag == %u \n", !zcs->params.fParams.noDictIDFlag);
3164
3165     if (zcs->cdict) CHECK_F(ZSTD_compressBegin_usingCDict_advanced(zcs->cctx, zcs->cdict, zcs->params.fParams, pledgedSrcSize))
3166     else CHECK_F(ZSTD_compressBegin_internal(zcs->cctx, NULL, 0, zcs->params, pledgedSrcSize));
3167
3168     zcs->inToCompress = 0;
3169     zcs->inBuffPos = 0;
3170     zcs->inBuffTarget = zcs->blockSize;
3171     zcs->outBuffContentSize = zcs->outBuffFlushedSize = 0;
3172     zcs->stage = zcss_load;
3173     zcs->frameEnded = 0;
3174     zcs->pledgedSrcSize = pledgedSrcSize;
3175     return 0;   /* ready to go */
3176 }
3177
3178 size_t ZSTD_resetCStream(ZSTD_CStream* zcs, unsigned long long pledgedSrcSize)
3179 {
3180
3181     zcs->params.fParams.contentSizeFlag = (pledgedSrcSize > 0);
3182     DEBUGLOG(5, "ZSTD_resetCStream : dictIDFlag == %u \n", !zcs->params.fParams.noDictIDFlag);
3183     return ZSTD_resetCStream_internal(zcs, pledgedSrcSize);
3184 }
3185
3186 /* ZSTD_initCStream_internal() :
3187  * params are supposed validated at this stage
3188  * and zcs->cdict is supposed to be correct */
3189 static size_t ZSTD_initCStream_stage2(ZSTD_CStream* zcs,
3190                                 const ZSTD_parameters params,
3191                                 unsigned long long pledgedSrcSize)
3192 {
3193     assert(!ZSTD_isError(ZSTD_checkCParams(params.cParams)));
3194
3195     /* allocate buffers */
3196     {   size_t const neededInBuffSize = (size_t)1 << params.cParams.windowLog;
3197         if (zcs->inBuffSize < neededInBuffSize) {
3198             zcs->inBuffSize = 0;
3199             ZSTD_free(zcs->inBuff, zcs->customMem);
3200             zcs->inBuff = (char*) ZSTD_malloc(neededInBuffSize, zcs->customMem);
3201             if (zcs->inBuff == NULL) return ERROR(memory_allocation);
3202             zcs->inBuffSize = neededInBuffSize;
3203         }
3204         zcs->blockSize = MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, neededInBuffSize);
3205     }
3206     if (zcs->outBuffSize < ZSTD_compressBound(zcs->blockSize)+1) {
3207         size_t const outBuffSize = ZSTD_compressBound(zcs->blockSize)+1;
3208         zcs->outBuffSize = 0;
3209         ZSTD_free(zcs->outBuff, zcs->customMem);
3210         zcs->outBuff = (char*) ZSTD_malloc(outBuffSize, zcs->customMem);
3211         if (zcs->outBuff == NULL) return ERROR(memory_allocation);
3212         zcs->outBuffSize = outBuffSize;
3213     }
3214
3215     zcs->checksum = params.fParams.checksumFlag > 0;
3216     zcs->params = params;
3217
3218     DEBUGLOG(5, "ZSTD_initCStream_stage2 : dictIDFlag == %u \n", !params.fParams.noDictIDFlag);
3219     return ZSTD_resetCStream_internal(zcs, pledgedSrcSize);
3220 }
3221
3222 /* ZSTD_initCStream_usingCDict_advanced() :
3223  * same as ZSTD_initCStream_usingCDict(), with control over frame parameters */
3224 size_t ZSTD_initCStream_usingCDict_advanced(ZSTD_CStream* zcs, const ZSTD_CDict* cdict, unsigned long long pledgedSrcSize, ZSTD_frameParameters fParams)
3225 {
3226     if (!cdict) return ERROR(GENERIC);   /* cannot handle NULL cdict (does not know what to do) */
3227     {   ZSTD_parameters params = ZSTD_getParamsFromCDict(cdict);
3228         params.fParams = fParams;
3229         zcs->cdict = cdict;
3230         return ZSTD_initCStream_stage2(zcs, params, pledgedSrcSize);
3231     }
3232 }
3233
3234 /* note : cdict must outlive compression session */
3235 size_t ZSTD_initCStream_usingCDict(ZSTD_CStream* zcs, const ZSTD_CDict* cdict)
3236 {
3237     ZSTD_frameParameters const fParams = { 0 /* content */, 0 /* checksum */, 0 /* noDictID */ };
3238     return ZSTD_initCStream_usingCDict_advanced(zcs, cdict, 0, fParams);
3239 }
3240
3241 static size_t ZSTD_initCStream_internal(ZSTD_CStream* zcs,
3242                                 const void* dict, size_t dictSize,
3243                                 ZSTD_parameters params, unsigned long long pledgedSrcSize)
3244 {
3245     assert(!ZSTD_isError(ZSTD_checkCParams(params.cParams)));
3246     zcs->cdict = NULL;
3247
3248     if (dict && dictSize >= 8) {
3249         ZSTD_freeCDict(zcs->cdictLocal);
3250         zcs->cdictLocal = ZSTD_createCDict_advanced(dict, dictSize, 0 /* copy */, params.cParams, zcs->customMem);
3251         if (zcs->cdictLocal == NULL) return ERROR(memory_allocation);
3252         zcs->cdict = zcs->cdictLocal;
3253     }
3254
3255     DEBUGLOG(5, "ZSTD_initCStream_internal : dictIDFlag == %u \n", !params.fParams.noDictIDFlag);
3256     return ZSTD_initCStream_stage2(zcs, params, pledgedSrcSize);
3257 }
3258
3259 size_t ZSTD_initCStream_advanced(ZSTD_CStream* zcs,
3260                                  const void* dict, size_t dictSize,
3261                                  ZSTD_parameters params, unsigned long long pledgedSrcSize)
3262 {
3263     CHECK_F( ZSTD_checkCParams(params.cParams) );
3264     DEBUGLOG(5, "ZSTD_initCStream_advanced : dictIDFlag == %u \n", !params.fParams.noDictIDFlag);
3265     return ZSTD_initCStream_internal(zcs, dict, dictSize, params, pledgedSrcSize);
3266 }
3267
3268 size_t ZSTD_initCStream_usingDict(ZSTD_CStream* zcs, const void* dict, size_t dictSize, int compressionLevel)
3269 {
3270     ZSTD_parameters const params = ZSTD_getParams(compressionLevel, 0, dictSize);
3271     return ZSTD_initCStream_internal(zcs, dict, dictSize, params, 0);
3272 }
3273
3274 size_t ZSTD_initCStream_srcSize(ZSTD_CStream* zcs, int compressionLevel, unsigned long long pledgedSrcSize)
3275 {
3276     ZSTD_parameters params = ZSTD_getParams(compressionLevel, pledgedSrcSize, 0);
3277     params.fParams.contentSizeFlag = (pledgedSrcSize>0);
3278     return ZSTD_initCStream_internal(zcs, NULL, 0, params, pledgedSrcSize);
3279 }
3280
3281 size_t ZSTD_initCStream(ZSTD_CStream* zcs, int compressionLevel)
3282 {
3283     ZSTD_parameters const params = ZSTD_getParams(compressionLevel, 0, 0);
3284     return ZSTD_initCStream_internal(zcs, NULL, 0, params, 0);
3285 }
3286
3287 size_t ZSTD_sizeof_CStream(const ZSTD_CStream* zcs)
3288 {
3289     if (zcs==NULL) return 0;   /* support sizeof on NULL */
3290     return sizeof(*zcs) + ZSTD_sizeof_CCtx(zcs->cctx) + ZSTD_sizeof_CDict(zcs->cdictLocal) + zcs->outBuffSize + zcs->inBuffSize;
3291 }
3292
3293 /*======   Compression   ======*/
3294
3295 typedef enum { zsf_gather, zsf_flush, zsf_end } ZSTD_flush_e;
3296
3297 MEM_STATIC size_t ZSTD_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3298 {
3299     size_t const length = MIN(dstCapacity, srcSize);
3300     memcpy(dst, src, length);
3301     return length;
3302 }
3303
3304 static size_t ZSTD_compressStream_generic(ZSTD_CStream* zcs,
3305                               void* dst, size_t* dstCapacityPtr,
3306                         const void* src, size_t* srcSizePtr,
3307                               ZSTD_flush_e const flush)
3308 {
3309     U32 someMoreWork = 1;
3310     const char* const istart = (const char*)src;
3311     const char* const iend = istart + *srcSizePtr;
3312     const char* ip = istart;
3313     char* const ostart = (char*)dst;
3314     char* const oend = ostart + *dstCapacityPtr;
3315     char* op = ostart;
3316
3317     while (someMoreWork) {
3318         switch(zcs->stage)
3319         {
3320         case zcss_init: return ERROR(init_missing);   /* call ZBUFF_compressInit() first ! */
3321
3322         case zcss_load:
3323             /* complete inBuffer */
3324             {   size_t const toLoad = zcs->inBuffTarget - zcs->inBuffPos;
3325                 size_t const loaded = ZSTD_limitCopy(zcs->inBuff + zcs->inBuffPos, toLoad, ip, iend-ip);
3326                 zcs->inBuffPos += loaded;
3327                 ip += loaded;
3328                 if ( (zcs->inBuffPos==zcs->inToCompress) || (!flush && (toLoad != loaded)) ) {
3329                     someMoreWork = 0; break;  /* not enough input to get a full block : stop there, wait for more */
3330             }   }
3331             /* compress current block (note : this stage cannot be stopped in the middle) */
3332             {   void* cDst;
3333                 size_t cSize;
3334                 size_t const iSize = zcs->inBuffPos - zcs->inToCompress;
3335                 size_t oSize = oend-op;
3336                 if (oSize >= ZSTD_compressBound(iSize))
3337                     cDst = op;   /* compress directly into output buffer (avoid flush stage) */
3338                 else
3339                     cDst = zcs->outBuff, oSize = zcs->outBuffSize;
3340                 cSize = (flush == zsf_end) ?
3341                         ZSTD_compressEnd(zcs->cctx, cDst, oSize, zcs->inBuff + zcs->inToCompress, iSize) :
3342                         ZSTD_compressContinue(zcs->cctx, cDst, oSize, zcs->inBuff + zcs->inToCompress, iSize);
3343                 if (ZSTD_isError(cSize)) return cSize;
3344                 if (flush == zsf_end) zcs->frameEnded = 1;
3345                 /* prepare next block */
3346                 zcs->inBuffTarget = zcs->inBuffPos + zcs->blockSize;
3347                 if (zcs->inBuffTarget > zcs->inBuffSize)
3348                     zcs->inBuffPos = 0, zcs->inBuffTarget = zcs->blockSize;   /* note : inBuffSize >= blockSize */
3349                 zcs->inToCompress = zcs->inBuffPos;
3350                 if (cDst == op) { op += cSize; break; }   /* no need to flush */
3351                 zcs->outBuffContentSize = cSize;
3352                 zcs->outBuffFlushedSize = 0;
3353                 zcs->stage = zcss_flush;   /* pass-through to flush stage */
3354             }
3355
3356         case zcss_flush:
3357             {   size_t const toFlush = zcs->outBuffContentSize - zcs->outBuffFlushedSize;
3358                 size_t const flushed = ZSTD_limitCopy(op, oend-op, zcs->outBuff + zcs->outBuffFlushedSize, toFlush);
3359                 op += flushed;
3360                 zcs->outBuffFlushedSize += flushed;
3361                 if (toFlush!=flushed) { someMoreWork = 0; break; }  /* dst too small to store flushed data : stop there */
3362                 zcs->outBuffContentSize = zcs->outBuffFlushedSize = 0;
3363                 zcs->stage = zcss_load;
3364                 break;
3365             }
3366
3367         case zcss_final:
3368             someMoreWork = 0;   /* do nothing */
3369             break;
3370
3371         default:
3372             return ERROR(GENERIC);   /* impossible */
3373         }
3374     }
3375
3376     *srcSizePtr = ip - istart;
3377     *dstCapacityPtr = op - ostart;
3378     if (zcs->frameEnded) return 0;
3379     {   size_t hintInSize = zcs->inBuffTarget - zcs->inBuffPos;
3380         if (hintInSize==0) hintInSize = zcs->blockSize;
3381         return hintInSize;
3382     }
3383 }
3384
3385 size_t ZSTD_compressStream(ZSTD_CStream* zcs, ZSTD_outBuffer* output, ZSTD_inBuffer* input)
3386 {
3387     size_t sizeRead = input->size - input->pos;
3388     size_t sizeWritten = output->size - output->pos;
3389     size_t const result = ZSTD_compressStream_generic(zcs,
3390                                                       (char*)(output->dst) + output->pos, &sizeWritten,
3391                                                       (const char*)(input->src) + input->pos, &sizeRead, zsf_gather);
3392     input->pos += sizeRead;
3393     output->pos += sizeWritten;
3394     return result;
3395 }
3396
3397
3398 /*======   Finalize   ======*/
3399
3400 /*! ZSTD_flushStream() :
3401 *   @return : amount of data remaining to flush */
3402 size_t ZSTD_flushStream(ZSTD_CStream* zcs, ZSTD_outBuffer* output)
3403 {
3404     size_t srcSize = 0;
3405     size_t sizeWritten = output->size - output->pos;
3406     size_t const result = ZSTD_compressStream_generic(zcs,
3407                                                      (char*)(output->dst) + output->pos, &sizeWritten,
3408                                                      &srcSize, &srcSize, /* use a valid src address instead of NULL */
3409                                                       zsf_flush);
3410     output->pos += sizeWritten;
3411     if (ZSTD_isError(result)) return result;
3412     return zcs->outBuffContentSize - zcs->outBuffFlushedSize;   /* remaining to flush */
3413 }
3414
3415
3416 size_t ZSTD_endStream(ZSTD_CStream* zcs, ZSTD_outBuffer* output)
3417 {
3418     BYTE* const ostart = (BYTE*)(output->dst) + output->pos;
3419     BYTE* const oend = (BYTE*)(output->dst) + output->size;
3420     BYTE* op = ostart;
3421
3422     if (zcs->stage != zcss_final) {
3423         /* flush whatever remains */
3424         size_t srcSize = 0;
3425         size_t sizeWritten = output->size - output->pos;
3426         size_t const notEnded = ZSTD_compressStream_generic(zcs, ostart, &sizeWritten,
3427                                      &srcSize /* use a valid src address instead of NULL */, &srcSize, zsf_end);
3428         size_t const remainingToFlush = zcs->outBuffContentSize - zcs->outBuffFlushedSize;
3429         op += sizeWritten;
3430         if (remainingToFlush) {
3431             output->pos += sizeWritten;
3432             return remainingToFlush + ZSTD_BLOCKHEADERSIZE /* final empty block */ + (zcs->checksum * 4);
3433         }
3434         /* create epilogue */
3435         zcs->stage = zcss_final;
3436         zcs->outBuffContentSize = !notEnded ? 0 :
3437             /* write epilogue, including final empty block, into outBuff */
3438             ZSTD_compressEnd(zcs->cctx, zcs->outBuff, zcs->outBuffSize, NULL, 0);
3439         if (ZSTD_isError(zcs->outBuffContentSize)) return zcs->outBuffContentSize;
3440     }
3441
3442     /* flush epilogue */
3443     {   size_t const toFlush = zcs->outBuffContentSize - zcs->outBuffFlushedSize;
3444         size_t const flushed = ZSTD_limitCopy(op, oend-op, zcs->outBuff + zcs->outBuffFlushedSize, toFlush);
3445         op += flushed;
3446         zcs->outBuffFlushedSize += flushed;
3447         output->pos += op-ostart;
3448         if (toFlush==flushed) zcs->stage = zcss_init;  /* end reached */
3449         return toFlush - flushed;
3450     }
3451 }
3452
3453
3454
3455 /*-=====  Pre-defined compression levels  =====-*/
3456
3457 #define ZSTD_DEFAULT_CLEVEL 1
3458 #define ZSTD_MAX_CLEVEL     22
3459 int ZSTD_maxCLevel(void) { return ZSTD_MAX_CLEVEL; }
3460
3461 static const ZSTD_compressionParameters ZSTD_defaultCParameters[4][ZSTD_MAX_CLEVEL+1] = {
3462 {   /* "default" */
3463     /* W,  C,  H,  S,  L, TL, strat */
3464     { 18, 12, 12,  1,  7, 16, ZSTD_fast    },  /* level  0 - never used */
3465     { 19, 13, 14,  1,  7, 16, ZSTD_fast    },  /* level  1 */
3466     { 19, 15, 16,  1,  6, 16, ZSTD_fast    },  /* level  2 */
3467     { 20, 16, 17,  1,  5, 16, ZSTD_dfast   },  /* level  3.*/
3468     { 20, 18, 18,  1,  5, 16, ZSTD_dfast   },  /* level  4.*/
3469     { 20, 15, 18,  3,  5, 16, ZSTD_greedy  },  /* level  5 */
3470     { 21, 16, 19,  2,  5, 16, ZSTD_lazy    },  /* level  6 */
3471     { 21, 17, 20,  3,  5, 16, ZSTD_lazy    },  /* level  7 */
3472     { 21, 18, 20,  3,  5, 16, ZSTD_lazy2   },  /* level  8 */
3473     { 21, 20, 20,  3,  5, 16, ZSTD_lazy2   },  /* level  9 */
3474     { 21, 19, 21,  4,  5, 16, ZSTD_lazy2   },  /* level 10 */
3475     { 22, 20, 22,  4,  5, 16, ZSTD_lazy2   },  /* level 11 */
3476     { 22, 20, 22,  5,  5, 16, ZSTD_lazy2   },  /* level 12 */
3477     { 22, 21, 22,  5,  5, 16, ZSTD_lazy2   },  /* level 13 */
3478     { 22, 21, 22,  6,  5, 16, ZSTD_lazy2   },  /* level 14 */
3479     { 22, 21, 21,  5,  5, 16, ZSTD_btlazy2 },  /* level 15 */
3480     { 23, 22, 22,  5,  5, 16, ZSTD_btlazy2 },  /* level 16 */
3481     { 23, 21, 22,  4,  5, 24, ZSTD_btopt   },  /* level 17 */
3482     { 23, 22, 22,  5,  4, 32, ZSTD_btopt   },  /* level 18 */
3483     { 23, 23, 22,  6,  3, 48, ZSTD_btopt   },  /* level 19 */
3484     { 25, 25, 23,  7,  3, 64, ZSTD_btopt2  },  /* level 20 */
3485     { 26, 26, 23,  7,  3,256, ZSTD_btopt2  },  /* level 21 */
3486     { 27, 27, 25,  9,  3,512, ZSTD_btopt2  },  /* level 22 */
3487 },
3488 {   /* for srcSize <= 256 KB */
3489     /* W,  C,  H,  S,  L,  T, strat */
3490     {  0,  0,  0,  0,  0,  0, ZSTD_fast    },  /* level  0 - not used */
3491     { 18, 13, 14,  1,  6,  8, ZSTD_fast    },  /* level  1 */
3492     { 18, 14, 13,  1,  5,  8, ZSTD_dfast   },  /* level  2 */
3493     { 18, 16, 15,  1,  5,  8, ZSTD_dfast   },  /* level  3 */
3494     { 18, 15, 17,  1,  5,  8, ZSTD_greedy  },  /* level  4.*/
3495     { 18, 16, 17,  4,  5,  8, ZSTD_greedy  },  /* level  5.*/
3496     { 18, 16, 17,  3,  5,  8, ZSTD_lazy    },  /* level  6.*/
3497     { 18, 17, 17,  4,  4,  8, ZSTD_lazy    },  /* level  7 */
3498     { 18, 17, 17,  4,  4,  8, ZSTD_lazy2   },  /* level  8 */
3499     { 18, 17, 17,  5,  4,  8, ZSTD_lazy2   },  /* level  9 */
3500     { 18, 17, 17,  6,  4,  8, ZSTD_lazy2   },  /* level 10 */
3501     { 18, 18, 17,  6,  4,  8, ZSTD_lazy2   },  /* level 11.*/
3502     { 18, 18, 17,  7,  4,  8, ZSTD_lazy2   },  /* level 12.*/
3503     { 18, 19, 17,  6,  4,  8, ZSTD_btlazy2 },  /* level 13 */
3504     { 18, 18, 18,  4,  4, 16, ZSTD_btopt   },  /* level 14.*/
3505     { 18, 18, 18,  4,  3, 16, ZSTD_btopt   },  /* level 15.*/
3506     { 18, 19, 18,  6,  3, 32, ZSTD_btopt   },  /* level 16.*/
3507     { 18, 19, 18,  8,  3, 64, ZSTD_btopt   },  /* level 17.*/
3508     { 18, 19, 18,  9,  3,128, ZSTD_btopt   },  /* level 18.*/
3509     { 18, 19, 18, 10,  3,256, ZSTD_btopt   },  /* level 19.*/
3510     { 18, 19, 18, 11,  3,512, ZSTD_btopt2  },  /* level 20.*/
3511     { 18, 19, 18, 12,  3,512, ZSTD_btopt2  },  /* level 21.*/
3512     { 18, 19, 18, 13,  3,512, ZSTD_btopt2  },  /* level 22.*/
3513 },
3514 {   /* for srcSize <= 128 KB */
3515     /* W,  C,  H,  S,  L,  T, strat */
3516     { 17, 12, 12,  1,  7,  8, ZSTD_fast    },  /* level  0 - not used */
3517     { 17, 12, 13,  1,  6,  8, ZSTD_fast    },  /* level  1 */
3518     { 17, 13, 16,  1,  5,  8, ZSTD_fast    },  /* level  2 */
3519     { 17, 16, 16,  2,  5,  8, ZSTD_dfast   },  /* level  3 */
3520     { 17, 13, 15,  3,  4,  8, ZSTD_greedy  },  /* level  4 */
3521     { 17, 15, 17,  4,  4,  8, ZSTD_greedy  },  /* level  5 */
3522     { 17, 16, 17,  3,  4,  8, ZSTD_lazy    },  /* level  6 */
3523     { 17, 15, 17,  4,  4,  8, ZSTD_lazy2   },  /* level  7 */
3524     { 17, 17, 17,  4,  4,  8, ZSTD_lazy2   },  /* level  8 */
3525     { 17, 17, 17,  5,  4,  8, ZSTD_lazy2   },  /* level  9 */
3526     { 17, 17, 17,  6,  4,  8, ZSTD_lazy2   },  /* level 10 */
3527     { 17, 17, 17,  7,  4,  8, ZSTD_lazy2   },  /* level 11 */
3528     { 17, 17, 17,  8,  4,  8, ZSTD_lazy2   },  /* level 12 */
3529     { 17, 18, 17,  6,  4,  8, ZSTD_btlazy2 },  /* level 13.*/
3530     { 17, 17, 17,  7,  3,  8, ZSTD_btopt   },  /* level 14.*/
3531     { 17, 17, 17,  7,  3, 16, ZSTD_btopt   },  /* level 15.*/
3532     { 17, 18, 17,  7,  3, 32, ZSTD_btopt   },  /* level 16.*/
3533     { 17, 18, 17,  7,  3, 64, ZSTD_btopt   },  /* level 17.*/
3534     { 17, 18, 17,  7,  3,256, ZSTD_btopt   },  /* level 18.*/
3535     { 17, 18, 17,  8,  3,256, ZSTD_btopt   },  /* level 19.*/
3536     { 17, 18, 17,  9,  3,256, ZSTD_btopt2  },  /* level 20.*/
3537     { 17, 18, 17, 10,  3,256, ZSTD_btopt2  },  /* level 21.*/
3538     { 17, 18, 17, 11,  3,512, ZSTD_btopt2  },  /* level 22.*/
3539 },
3540 {   /* for srcSize <= 16 KB */
3541     /* W,  C,  H,  S,  L,  T, strat */
3542     { 14, 12, 12,  1,  7,  6, ZSTD_fast    },  /* level  0 - not used */
3543     { 14, 14, 14,  1,  6,  6, ZSTD_fast    },  /* level  1 */
3544     { 14, 14, 14,  1,  4,  6, ZSTD_fast    },  /* level  2 */
3545     { 14, 14, 14,  1,  4,  6, ZSTD_dfast   },  /* level  3.*/
3546     { 14, 14, 14,  4,  4,  6, ZSTD_greedy  },  /* level  4.*/
3547     { 14, 14, 14,  3,  4,  6, ZSTD_lazy    },  /* level  5.*/
3548     { 14, 14, 14,  4,  4,  6, ZSTD_lazy2   },  /* level  6 */
3549     { 14, 14, 14,  5,  4,  6, ZSTD_lazy2   },  /* level  7 */
3550     { 14, 14, 14,  6,  4,  6, ZSTD_lazy2   },  /* level  8.*/
3551     { 14, 15, 14,  6,  4,  6, ZSTD_btlazy2 },  /* level  9.*/
3552     { 14, 15, 14,  3,  3,  6, ZSTD_btopt   },  /* level 10.*/
3553     { 14, 15, 14,  6,  3,  8, ZSTD_btopt   },  /* level 11.*/
3554     { 14, 15, 14,  6,  3, 16, ZSTD_btopt   },  /* level 12.*/
3555     { 14, 15, 14,  6,  3, 24, ZSTD_btopt   },  /* level 13.*/
3556     { 14, 15, 15,  6,  3, 48, ZSTD_btopt   },  /* level 14.*/
3557     { 14, 15, 15,  6,  3, 64, ZSTD_btopt   },  /* level 15.*/
3558     { 14, 15, 15,  6,  3, 96, ZSTD_btopt   },  /* level 16.*/
3559     { 14, 15, 15,  6,  3,128, ZSTD_btopt   },  /* level 17.*/
3560     { 14, 15, 15,  6,  3,256, ZSTD_btopt   },  /* level 18.*/
3561     { 14, 15, 15,  7,  3,256, ZSTD_btopt   },  /* level 19.*/
3562     { 14, 15, 15,  8,  3,256, ZSTD_btopt2  },  /* level 20.*/
3563     { 14, 15, 15,  9,  3,256, ZSTD_btopt2  },  /* level 21.*/
3564     { 14, 15, 15, 10,  3,256, ZSTD_btopt2  },  /* level 22.*/
3565 },
3566 };
3567
3568 /*! ZSTD_getCParams() :
3569 *   @return ZSTD_compressionParameters structure for a selected compression level, `srcSize` and `dictSize`.
3570 *   Size values are optional, provide 0 if not known or unused */
3571 ZSTD_compressionParameters ZSTD_getCParams(int compressionLevel, unsigned long long srcSize, size_t dictSize)
3572 {
3573     ZSTD_compressionParameters cp;
3574     size_t const addedSize = srcSize ? 0 : 500;
3575     U64 const rSize = srcSize+dictSize ? srcSize+dictSize+addedSize : (U64)-1;
3576     U32 const tableID = (rSize <= 256 KB) + (rSize <= 128 KB) + (rSize <= 16 KB);   /* intentional underflow for srcSizeHint == 0 */
3577     if (compressionLevel <= 0) compressionLevel = ZSTD_DEFAULT_CLEVEL;   /* 0 == default; no negative compressionLevel yet */
3578     if (compressionLevel > ZSTD_MAX_CLEVEL) compressionLevel = ZSTD_MAX_CLEVEL;
3579     cp = ZSTD_defaultCParameters[tableID][compressionLevel];
3580     if (MEM_32bits()) {   /* auto-correction, for 32-bits mode */
3581         if (cp.windowLog > ZSTD_WINDOWLOG_MAX) cp.windowLog = ZSTD_WINDOWLOG_MAX;
3582         if (cp.chainLog > ZSTD_CHAINLOG_MAX) cp.chainLog = ZSTD_CHAINLOG_MAX;
3583         if (cp.hashLog > ZSTD_HASHLOG_MAX) cp.hashLog = ZSTD_HASHLOG_MAX;
3584     }
3585     cp = ZSTD_adjustCParams(cp, srcSize, dictSize);
3586     return cp;
3587 }
3588
3589 /*! ZSTD_getParams() :
3590 *   same as ZSTD_getCParams(), but @return a `ZSTD_parameters` object (instead of `ZSTD_compressionParameters`).
3591 *   All fields of `ZSTD_frameParameters` are set to default (0) */
3592 ZSTD_parameters ZSTD_getParams(int compressionLevel, unsigned long long srcSize, size_t dictSize) {
3593     ZSTD_parameters params;
3594     ZSTD_compressionParameters const cParams = ZSTD_getCParams(compressionLevel, srcSize, dictSize);
3595     memset(&params, 0, sizeof(params));
3596     params.cParams = cParams;
3597     return params;
3598 }