/*

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

 * All rights reserved.

 *

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

 * LICENSE file in the root directory of this source tree) and the GPLv2 (found

 * in the COPYING file in the root directory of this source tree).

 * You may select, at your option, one of the above-listed licenses.

 */

/*-*************************************

*  Dependencies

***************************************/

#include <limits.h>         /* INT_MAX */

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

#include "cpu.h"

#include "mem.h"

#include "hist.h"           /* HIST_countFast_wksp */

#define FSE_STATIC_LINKING_ONLY   /* FSE_encodeSymbol */

#include "fse.h"

#define HUF_STATIC_LINKING_ONLY

#include "huf.h"

#include "zstd_compress_internal.h"

#include "zstd_compress_sequences.h"

#include "zstd_compress_literals.h"

#include "zstd_fast.h"

#include "zstd_double_fast.h"

#include "zstd_lazy.h"

#include "zstd_opt.h"

#include "zstd_ldm.h"

/*-*************************************

*  Helper functions

***************************************/

size_t ZSTD_compressBound(size_t srcSize) {

    return ZSTD_COMPRESSBOUND(srcSize);

}

/*-*************************************

*  Context memory management

***************************************/

struct ZSTD_CDict_s {

    const void* dictContent;

    size_t dictContentSize;

    U32* entropyWorkspace; /* entropy workspace of HUF_WORKSPACE_SIZE bytes */

    ZSTD_cwksp workspace;

    ZSTD_matchState_t matchState;

    ZSTD_compressedBlockState_t cBlockState;

    ZSTD_customMem customMem;

    U32 dictID;

    int compressionLevel; /* 0 indicates that advanced API was used to select CDict params */

};  /* typedef'd to ZSTD_CDict within "zstd.h" */

ZSTD_CCtx* ZSTD_createCCtx(void)

{

    return ZSTD_createCCtx_advanced(ZSTD_defaultCMem);

}

static void ZSTD_initCCtx(ZSTD_CCtx* cctx, ZSTD_customMem memManager)

{

    assert(cctx != NULL);

    memset(cctx, 0, sizeof(*cctx));

    cctx->customMem = memManager;

    cctx->bmi2 = ZSTD_cpuid_bmi2(ZSTD_cpuid());

    {   size_t const err = ZSTD_CCtx_reset(cctx, ZSTD_reset_parameters);

        assert(!ZSTD_isError(err));

        (void)err;

    }

}

ZSTD_CCtx* ZSTD_createCCtx_advanced(ZSTD_customMem customMem)

{

    ZSTD_STATIC_ASSERT(zcss_init==0);

    ZSTD_STATIC_ASSERT(ZSTD_CONTENTSIZE_UNKNOWN==(0ULL - 1));

    if (!customMem.customAlloc ^ !customMem.customFree) return NULL;

    {   ZSTD_CCtx* const cctx = (ZSTD_CCtx*)ZSTD_malloc(sizeof(ZSTD_CCtx), customMem);

        if (!cctx) return NULL;

        ZSTD_initCCtx(cctx, customMem);

        return cctx;

    }

}

ZSTD_CCtx* ZSTD_initStaticCCtx(void *workspace, size_t workspaceSize)

{

    ZSTD_cwksp ws;

    ZSTD_CCtx* cctx;

    if (workspaceSize <= sizeof(ZSTD_CCtx)) return NULL;  /* minimum size */

    if ((size_t)workspace & 7) return NULL;  /* must be 8-aligned */

    ZSTD_cwksp_init(&ws, workspace, workspaceSize);

    cctx = (ZSTD_CCtx*)ZSTD_cwksp_reserve_object(&ws, sizeof(ZSTD_CCtx));

    if (cctx == NULL) {

        return NULL;

    }

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

    ZSTD_cwksp_move(&cctx->workspace, &ws);

    cctx->staticSize = workspaceSize;

    /* statically sized space. entropyWorkspace never moves (but prev/next block swap places) */

    if (!ZSTD_cwksp_check_available(&cctx->workspace, HUF_WORKSPACE_SIZE + 2 * sizeof(ZSTD_compressedBlockState_t))) return NULL;

    cctx->blockState.prevCBlock = (ZSTD_compressedBlockState_t*)ZSTD_cwksp_reserve_object(&cctx->workspace, sizeof(ZSTD_compressedBlockState_t));

    cctx->blockState.nextCBlock = (ZSTD_compressedBlockState_t*)ZSTD_cwksp_reserve_object(&cctx->workspace, sizeof(ZSTD_compressedBlockState_t));

    cctx->entropyWorkspace = (U32*)ZSTD_cwksp_reserve_object(

        &cctx->workspace, HUF_WORKSPACE_SIZE);

    cctx->bmi2 = ZSTD_cpuid_bmi2(ZSTD_cpuid());

    return cctx;

}

/**

 * Clears and frees all of the dictionaries in the CCtx.

 */

static void ZSTD_clearAllDicts(ZSTD_CCtx* cctx)

{

    ZSTD_free(cctx->localDict.dictBuffer, cctx->customMem);

    ZSTD_freeCDict(cctx->localDict.cdict);

    memset(&cctx->localDict, 0, sizeof(cctx->localDict));

    memset(&cctx->prefixDict, 0, sizeof(cctx->prefixDict));

    cctx->cdict = NULL;

}

static size_t ZSTD_sizeof_localDict(ZSTD_localDict dict)

{

    size_t const bufferSize = dict.dictBuffer != NULL ? dict.dictSize : 0;

    size_t const cdictSize = ZSTD_sizeof_CDict(dict.cdict);

    return bufferSize + cdictSize;

}

static void ZSTD_freeCCtxContent(ZSTD_CCtx* cctx)

{

    assert(cctx != NULL);

    assert(cctx->staticSize == 0);

    ZSTD_clearAllDicts(cctx);

#ifdef ZSTD_MULTITHREAD

    ZSTDMT_freeCCtx(cctx->mtctx); cctx->mtctx = NULL;

#endif

    ZSTD_cwksp_free(&cctx->workspace, cctx->customMem);

}

size_t ZSTD_freeCCtx(ZSTD_CCtx* cctx)

{

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

    RETURN_ERROR_IF(cctx->staticSize, memory_allocation,

                    "not compatible with static CCtx");

    {

        int cctxInWorkspace = ZSTD_cwksp_owns_buffer(&cctx->workspace, cctx);

        ZSTD_freeCCtxContent(cctx);

        if (!cctxInWorkspace) {

            ZSTD_free(cctx, cctx->customMem);

        }

    }

    return 0;

}

static size_t ZSTD_sizeof_mtctx(const ZSTD_CCtx* cctx)

{

#ifdef ZSTD_MULTITHREAD

    return ZSTDMT_sizeof_CCtx(cctx->mtctx);

#else

    (void)cctx;

    return 0;

#endif

}

size_t ZSTD_sizeof_CCtx(const ZSTD_CCtx* cctx)

{

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

    /* cctx may be in the workspace */

    return (cctx->workspace.workspace == cctx ? 0 : sizeof(*cctx))

           + ZSTD_cwksp_sizeof(&cctx->workspace)

           + ZSTD_sizeof_localDict(cctx->localDict)

           + ZSTD_sizeof_mtctx(cctx);

}

size_t ZSTD_sizeof_CStream(const ZSTD_CStream* zcs)

{

    return ZSTD_sizeof_CCtx(zcs);  /* same object */

}

/* private API call, for dictBuilder only */

const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx) { return &(ctx->seqStore); }

static ZSTD_CCtx_params ZSTD_makeCCtxParamsFromCParams(

        ZSTD_compressionParameters cParams)

{

    ZSTD_CCtx_params cctxParams;

    memset(&cctxParams, 0, sizeof(cctxParams));

    cctxParams.cParams = cParams;

    cctxParams.compressionLevel = ZSTD_CLEVEL_DEFAULT;  /* should not matter, as all cParams are presumed properly defined */

    assert(!ZSTD_checkCParams(cParams));

    cctxParams.fParams.contentSizeFlag = 1;

    return cctxParams;

}

static ZSTD_CCtx_params* ZSTD_createCCtxParams_advanced(

        ZSTD_customMem customMem)

{

    ZSTD_CCtx_params* params;

    if (!customMem.customAlloc ^ !customMem.customFree) return NULL;

    params = (ZSTD_CCtx_params*)ZSTD_calloc(

            sizeof(ZSTD_CCtx_params), customMem);

    if (!params) { return NULL; }

    params->customMem = customMem;

    params->compressionLevel = ZSTD_CLEVEL_DEFAULT;

    params->fParams.contentSizeFlag = 1;

    return params;

}

ZSTD_CCtx_params* ZSTD_createCCtxParams(void)

{

    return ZSTD_createCCtxParams_advanced(ZSTD_defaultCMem);

}

size_t ZSTD_freeCCtxParams(ZSTD_CCtx_params* params)

{

    if (params == NULL) { return 0; }

    ZSTD_free(params, params->customMem);

    return 0;

}

size_t ZSTD_CCtxParams_reset(ZSTD_CCtx_params* params)

{

    return ZSTD_CCtxParams_init(params, ZSTD_CLEVEL_DEFAULT);

}

size_t ZSTD_CCtxParams_init(ZSTD_CCtx_params* cctxParams, int compressionLevel) {

    RETURN_ERROR_IF(!cctxParams, GENERIC);

    memset(cctxParams, 0, sizeof(*cctxParams));

    cctxParams->compressionLevel = compressionLevel;

    cctxParams->fParams.contentSizeFlag = 1;

    return 0;

}

size_t ZSTD_CCtxParams_init_advanced(ZSTD_CCtx_params* cctxParams, ZSTD_parameters params)

{

    RETURN_ERROR_IF(!cctxParams, GENERIC);

    FORWARD_IF_ERROR( ZSTD_checkCParams(params.cParams) );

    memset(cctxParams, 0, sizeof(*cctxParams));

    assert(!ZSTD_checkCParams(params.cParams));

    cctxParams->cParams = params.cParams;

    cctxParams->fParams = params.fParams;

    cctxParams->compressionLevel = ZSTD_CLEVEL_DEFAULT;   /* should not matter, as all cParams are presumed properly defined */

    return 0;

}

/* ZSTD_assignParamsToCCtxParams() :

 * params is presumed valid at this stage */

static ZSTD_CCtx_params ZSTD_assignParamsToCCtxParams(

        const ZSTD_CCtx_params* cctxParams, ZSTD_parameters params)

{

    ZSTD_CCtx_params ret = *cctxParams;

    assert(!ZSTD_checkCParams(params.cParams));

    ret.cParams = params.cParams;

    ret.fParams = params.fParams;

    ret.compressionLevel = ZSTD_CLEVEL_DEFAULT;   /* should not matter, as all cParams are presumed properly defined */

    return ret;

}

ZSTD_bounds ZSTD_cParam_getBounds(ZSTD_cParameter param)

{

    ZSTD_bounds bounds = { 0, 0, 0 };

    switch(param)

    {

    case ZSTD_c_compressionLevel:

        bounds.lowerBound = ZSTD_minCLevel();

        bounds.upperBound = ZSTD_maxCLevel();

        return bounds;

    case ZSTD_c_windowLog:

        bounds.lowerBound = ZSTD_WINDOWLOG_MIN;

        bounds.upperBound = ZSTD_WINDOWLOG_MAX;

        return bounds;

    case ZSTD_c_hashLog:

        bounds.lowerBound = ZSTD_HASHLOG_MIN;

        bounds.upperBound = ZSTD_HASHLOG_MAX;

        return bounds;

    case ZSTD_c_chainLog:

        bounds.lowerBound = ZSTD_CHAINLOG_MIN;

        bounds.upperBound = ZSTD_CHAINLOG_MAX;

        return bounds;

    case ZSTD_c_searchLog:

        bounds.lowerBound = ZSTD_SEARCHLOG_MIN;

        bounds.upperBound = ZSTD_SEARCHLOG_MAX;

        return bounds;

    case ZSTD_c_minMatch:

        bounds.lowerBound = ZSTD_MINMATCH_MIN;

        bounds.upperBound = ZSTD_MINMATCH_MAX;

        return bounds;

    case ZSTD_c_targetLength:

        bounds.lowerBound = ZSTD_TARGETLENGTH_MIN;

        bounds.upperBound = ZSTD_TARGETLENGTH_MAX;

        return bounds;

    case ZSTD_c_strategy:

        bounds.lowerBound = ZSTD_STRATEGY_MIN;

        bounds.upperBound = ZSTD_STRATEGY_MAX;

        return bounds;

    case ZSTD_c_contentSizeFlag:

        bounds.lowerBound = 0;

        bounds.upperBound = 1;

        return bounds;

    case ZSTD_c_checksumFlag:

        bounds.lowerBound = 0;

        bounds.upperBound = 1;

        return bounds;

    case ZSTD_c_dictIDFlag:

        bounds.lowerBound = 0;

        bounds.upperBound = 1;

        return bounds;

    case ZSTD_c_nbWorkers:

        bounds.lowerBound = 0;

#ifdef ZSTD_MULTITHREAD

        bounds.upperBound = ZSTDMT_NBWORKERS_MAX;

#else

        bounds.upperBound = 0;

#endif

        return bounds;

    case ZSTD_c_jobSize:

        bounds.lowerBound = 0;

#ifdef ZSTD_MULTITHREAD

        bounds.upperBound = ZSTDMT_JOBSIZE_MAX;

#else

        bounds.upperBound = 0;

#endif

        return bounds;

    case ZSTD_c_overlapLog:

        bounds.lowerBound = ZSTD_OVERLAPLOG_MIN;

        bounds.upperBound = ZSTD_OVERLAPLOG_MAX;

        return bounds;

    case ZSTD_c_enableLongDistanceMatching:

        bounds.lowerBound = 0;

        bounds.upperBound = 1;

        return bounds;

    case ZSTD_c_ldmHashLog:

        bounds.lowerBound = ZSTD_LDM_HASHLOG_MIN;

        bounds.upperBound = ZSTD_LDM_HASHLOG_MAX;

        return bounds;

    case ZSTD_c_ldmMinMatch:

        bounds.lowerBound = ZSTD_LDM_MINMATCH_MIN;

        bounds.upperBound = ZSTD_LDM_MINMATCH_MAX;

        return bounds;

    case ZSTD_c_ldmBucketSizeLog:

        bounds.lowerBound = ZSTD_LDM_BUCKETSIZELOG_MIN;

        bounds.upperBound = ZSTD_LDM_BUCKETSIZELOG_MAX;

        return bounds;

    case ZSTD_c_ldmHashRateLog:

        bounds.lowerBound = ZSTD_LDM_HASHRATELOG_MIN;

        bounds.upperBound = ZSTD_LDM_HASHRATELOG_MAX;

        return bounds;

    /* experimental parameters */

    case ZSTD_c_rsyncable:

        bounds.lowerBound = 0;

        bounds.upperBound = 1;

        return bounds;

    case ZSTD_c_forceMaxWindow :

        bounds.lowerBound = 0;

        bounds.upperBound = 1;

        return bounds;

    case ZSTD_c_format:

        ZSTD_STATIC_ASSERT(ZSTD_f_zstd1 < ZSTD_f_zstd1_magicless);

        bounds.lowerBound = ZSTD_f_zstd1;

        bounds.upperBound = ZSTD_f_zstd1_magicless;   /* note : how to ensure at compile time that this is the highest value enum ? */

        return bounds;

    case ZSTD_c_forceAttachDict:

        ZSTD_STATIC_ASSERT(ZSTD_dictDefaultAttach < ZSTD_dictForceCopy);

        bounds.lowerBound = ZSTD_dictDefaultAttach;

        bounds.upperBound = ZSTD_dictForceLoad;       /* note : how to ensure at compile time that this is the highest value enum ? */

        return bounds;

    case ZSTD_c_literalCompressionMode:

        ZSTD_STATIC_ASSERT(ZSTD_lcm_auto < ZSTD_lcm_huffman && ZSTD_lcm_huffman < ZSTD_lcm_uncompressed);

        bounds.lowerBound = ZSTD_lcm_auto;

        bounds.upperBound = ZSTD_lcm_uncompressed;

        return bounds;

    case ZSTD_c_targetCBlockSize:

        bounds.lowerBound = ZSTD_TARGETCBLOCKSIZE_MIN;

        bounds.upperBound = ZSTD_TARGETCBLOCKSIZE_MAX;

        return bounds;

    case ZSTD_c_srcSizeHint:

        bounds.lowerBound = ZSTD_SRCSIZEHINT_MIN;

        bounds.upperBound = ZSTD_SRCSIZEHINT_MAX;

        return bounds;

    default:

        {   ZSTD_bounds const boundError = { ERROR(parameter_unsupported), 0, 0 };

            return boundError;

        }

    }

}

/* ZSTD_cParam_clampBounds:

 * Clamps the value into the bounded range.

 */

static size_t ZSTD_cParam_clampBounds(ZSTD_cParameter cParam, int* value)

{

    ZSTD_bounds const bounds = ZSTD_cParam_getBounds(cParam);

    if (ZSTD_isError(bounds.error)) return bounds.error;

    if (*value < bounds.lowerBound) *value = bounds.lowerBound;

    if (*value > bounds.upperBound) *value = bounds.upperBound;

    return 0;

}

#define BOUNDCHECK(cParam, val) { \

    RETURN_ERROR_IF(!ZSTD_cParam_withinBounds(cParam,val), \

                    parameter_outOfBound); \

}

static int ZSTD_isUpdateAuthorized(ZSTD_cParameter param)

{

    switch(param)

    {

    case ZSTD_c_compressionLevel:

    case ZSTD_c_hashLog:

    case ZSTD_c_chainLog:

    case ZSTD_c_searchLog:

    case ZSTD_c_minMatch:

    case ZSTD_c_targetLength:

    case ZSTD_c_strategy:

        return 1;

    case ZSTD_c_format:

    case ZSTD_c_windowLog:

    case ZSTD_c_contentSizeFlag:

    case ZSTD_c_checksumFlag:

    case ZSTD_c_dictIDFlag:

    case ZSTD_c_forceMaxWindow :

    case ZSTD_c_nbWorkers:

    case ZSTD_c_jobSize:

    case ZSTD_c_overlapLog:

    case ZSTD_c_rsyncable:

    case ZSTD_c_enableLongDistanceMatching:

    case ZSTD_c_ldmHashLog:

    case ZSTD_c_ldmMinMatch:

    case ZSTD_c_ldmBucketSizeLog:

    case ZSTD_c_ldmHashRateLog:

    case ZSTD_c_forceAttachDict:

    case ZSTD_c_literalCompressionMode:

    case ZSTD_c_targetCBlockSize:

    case ZSTD_c_srcSizeHint:

    default:

        return 0;

    }

}

size_t ZSTD_CCtx_setParameter(ZSTD_CCtx* cctx, ZSTD_cParameter param, int value)

{

    DEBUGLOG(4, "ZSTD_CCtx_setParameter (%i, %i)", (int)param, value);

    if (cctx->streamStage != zcss_init) {

        if (ZSTD_isUpdateAuthorized(param)) {

            cctx->cParamsChanged = 1;

        } else {

            RETURN_ERROR(stage_wrong);

    }   }

    switch(param)

    {

    case ZSTD_c_nbWorkers:

        RETURN_ERROR_IF((value!=0) && cctx->staticSize, parameter_unsupported,

                        "MT not compatible with static alloc");

        break;

    case ZSTD_c_compressionLevel:

    case ZSTD_c_windowLog:

    case ZSTD_c_hashLog:

    case ZSTD_c_chainLog: