contrib/zstd/lib/compress/zstd_compress.c

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