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