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