| /** |
| * Copyright (c) 2016-present, Yann Collet, Facebook, Inc. |
| * All rights reserved. |
| * |
| * This source code is licensed under the BSD-style license found in the |
| * LICENSE file in the root directory of https://github.com/facebook/zstd. |
| * An additional grant of patent rights can be found in the PATENTS file in the |
| * same directory. |
| * |
| * This program is free software; you can redistribute it and/or modify it under |
| * the terms of the GNU General Public License version 2 as published by the |
| * Free Software Foundation. This program is dual-licensed; you may select |
| * either version 2 of the GNU General Public License ("GPL") or BSD license |
| * ("BSD"). |
| */ |
| |
| /*-************************************* |
| * Dependencies |
| ***************************************/ |
| #include "fse.h" |
| #include "huf.h" |
| #include "mem.h" |
| #include "zstd_internal.h" /* includes zstd.h */ |
| #include <linux/kernel.h> |
| #include <linux/module.h> |
| #include <linux/string.h> /* memset */ |
| |
| /*-************************************* |
| * Constants |
| ***************************************/ |
| static const U32 g_searchStrength = 8; /* control skip over incompressible data */ |
| #define HASH_READ_SIZE 8 |
| typedef enum { ZSTDcs_created = 0, ZSTDcs_init, ZSTDcs_ongoing, ZSTDcs_ending } ZSTD_compressionStage_e; |
| |
| /*-************************************* |
| * Helper functions |
| ***************************************/ |
| size_t ZSTD_compressBound(size_t srcSize) { return FSE_compressBound(srcSize) + 12; } |
| |
| /*-************************************* |
| * Sequence storage |
| ***************************************/ |
| static void ZSTD_resetSeqStore(seqStore_t *ssPtr) |
| { |
| ssPtr->lit = ssPtr->litStart; |
| ssPtr->sequences = ssPtr->sequencesStart; |
| ssPtr->longLengthID = 0; |
| } |
| |
| /*-************************************* |
| * Context memory management |
| ***************************************/ |
| struct ZSTD_CCtx_s { |
| const BYTE *nextSrc; /* next block here to continue on curr prefix */ |
| const BYTE *base; /* All regular indexes relative to this position */ |
| const BYTE *dictBase; /* extDict indexes relative to this position */ |
| U32 dictLimit; /* below that point, need extDict */ |
| U32 lowLimit; /* below that point, no more data */ |
| U32 nextToUpdate; /* index from which to continue dictionary update */ |
| U32 nextToUpdate3; /* index from which to continue dictionary update */ |
| U32 hashLog3; /* dispatch table : larger == faster, more memory */ |
| U32 loadedDictEnd; /* index of end of dictionary */ |
| U32 forceWindow; /* force back-references to respect limit of 1<<wLog, even for dictionary */ |
| U32 forceRawDict; /* Force loading dictionary in "content-only" mode (no header analysis) */ |
| ZSTD_compressionStage_e stage; |
| U32 rep[ZSTD_REP_NUM]; |
| U32 repToConfirm[ZSTD_REP_NUM]; |
| U32 dictID; |
| ZSTD_parameters params; |
| void *workSpace; |
| size_t workSpaceSize; |
| size_t blockSize; |
| U64 frameContentSize; |
| struct xxh64_state xxhState; |
| ZSTD_customMem customMem; |
| |
| seqStore_t seqStore; /* sequences storage ptrs */ |
| U32 *hashTable; |
| U32 *hashTable3; |
| U32 *chainTable; |
| HUF_CElt *hufTable; |
| U32 flagStaticTables; |
| HUF_repeat flagStaticHufTable; |
| FSE_CTable offcodeCTable[FSE_CTABLE_SIZE_U32(OffFSELog, MaxOff)]; |
| FSE_CTable matchlengthCTable[FSE_CTABLE_SIZE_U32(MLFSELog, MaxML)]; |
| FSE_CTable litlengthCTable[FSE_CTABLE_SIZE_U32(LLFSELog, MaxLL)]; |
| unsigned tmpCounters[HUF_COMPRESS_WORKSPACE_SIZE_U32]; |
| }; |
| |
| size_t ZSTD_CCtxWorkspaceBound(ZSTD_compressionParameters cParams) |
| { |
| size_t const blockSize = MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, (size_t)1 << cParams.windowLog); |
| U32 const divider = (cParams.searchLength == 3) ? 3 : 4; |
| size_t const maxNbSeq = blockSize / divider; |
| size_t const tokenSpace = blockSize + 11 * maxNbSeq; |
| size_t const chainSize = (cParams.strategy == ZSTD_fast) ? 0 : (1 << cParams.chainLog); |
| size_t const hSize = ((size_t)1) << cParams.hashLog; |
| U32 const hashLog3 = (cParams.searchLength > 3) ? 0 : MIN(ZSTD_HASHLOG3_MAX, cParams.windowLog); |
| size_t const h3Size = ((size_t)1) << hashLog3; |
| size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32); |
| size_t const optSpace = |
| ((MaxML + 1) + (MaxLL + 1) + (MaxOff + 1) + (1 << Litbits)) * sizeof(U32) + (ZSTD_OPT_NUM + 1) * (sizeof(ZSTD_match_t) + sizeof(ZSTD_optimal_t)); |
| size_t const workspaceSize = tableSpace + (256 * sizeof(U32)) /* huffTable */ + tokenSpace + |
| (((cParams.strategy == ZSTD_btopt) || (cParams.strategy == ZSTD_btopt2)) ? optSpace : 0); |
| |
| return ZSTD_ALIGN(sizeof(ZSTD_stack)) + ZSTD_ALIGN(sizeof(ZSTD_CCtx)) + ZSTD_ALIGN(workspaceSize); |
| } |
| |
| static ZSTD_CCtx *ZSTD_createCCtx_advanced(ZSTD_customMem customMem) |
| { |
| ZSTD_CCtx *cctx; |
| if (!customMem.customAlloc || !customMem.customFree) |
| return NULL; |
| cctx = (ZSTD_CCtx *)ZSTD_malloc(sizeof(ZSTD_CCtx), customMem); |
| if (!cctx) |
| return NULL; |
| memset(cctx, 0, sizeof(ZSTD_CCtx)); |
| cctx->customMem = customMem; |
| return cctx; |
| } |
| |
| ZSTD_CCtx *ZSTD_initCCtx(void *workspace, size_t workspaceSize) |
| { |
| ZSTD_customMem const stackMem = ZSTD_initStack(workspace, workspaceSize); |
| ZSTD_CCtx *cctx = ZSTD_createCCtx_advanced(stackMem); |
| if (cctx) { |
| cctx->workSpace = ZSTD_stackAllocAll(cctx->customMem.opaque, &cctx->workSpaceSize); |
| } |
| return cctx; |
| } |
| |
| size_t ZSTD_freeCCtx(ZSTD_CCtx *cctx) |
| { |
| if (cctx == NULL) |
| return 0; /* support free on NULL */ |
| ZSTD_free(cctx->workSpace, cctx->customMem); |
| ZSTD_free(cctx, cctx->customMem); |
| return 0; /* reserved as a potential error code in the future */ |
| } |
| |
| const seqStore_t *ZSTD_getSeqStore(const ZSTD_CCtx *ctx) /* hidden interface */ { return &(ctx->seqStore); } |
| |
| static ZSTD_parameters ZSTD_getParamsFromCCtx(const ZSTD_CCtx *cctx) { return cctx->params; } |
| |
| /** ZSTD_checkParams() : |
| ensure param values remain within authorized range. |
| @return : 0, or an error code if one value is beyond authorized range */ |
| size_t ZSTD_checkCParams(ZSTD_compressionParameters cParams) |
| { |
| #define CLAMPCHECK(val, min, max) \ |
| { \ |
| if ((val < min) | (val > max)) \ |
| return ERROR(compressionParameter_unsupported); \ |
| } |
| CLAMPCHECK(cParams.windowLog, ZSTD_WINDOWLOG_MIN, ZSTD_WINDOWLOG_MAX); |
| CLAMPCHECK(cParams.chainLog, ZSTD_CHAINLOG_MIN, ZSTD_CHAINLOG_MAX); |
| CLAMPCHECK(cParams.hashLog, ZSTD_HASHLOG_MIN, ZSTD_HASHLOG_MAX); |
| CLAMPCHECK(cParams.searchLog, ZSTD_SEARCHLOG_MIN, ZSTD_SEARCHLOG_MAX); |
| CLAMPCHECK(cParams.searchLength, ZSTD_SEARCHLENGTH_MIN, ZSTD_SEARCHLENGTH_MAX); |
| CLAMPCHECK(cParams.targetLength, ZSTD_TARGETLENGTH_MIN, ZSTD_TARGETLENGTH_MAX); |
| if ((U32)(cParams.strategy) > (U32)ZSTD_btopt2) |
| return ERROR(compressionParameter_unsupported); |
| return 0; |
| } |
| |
| /** ZSTD_cycleLog() : |
| * condition for correct operation : hashLog > 1 */ |
| static U32 ZSTD_cycleLog(U32 hashLog, ZSTD_strategy strat) |
| { |
| U32 const btScale = ((U32)strat >= (U32)ZSTD_btlazy2); |
| return hashLog - btScale; |
| } |
| |
| /** ZSTD_adjustCParams() : |
| optimize `cPar` for a given input (`srcSize` and `dictSize`). |
| mostly downsizing to reduce memory consumption and initialization. |
| Both `srcSize` and `dictSize` are optional (use 0 if unknown), |
| but if both are 0, no optimization can be done. |
| Note : cPar is considered validated at this stage. Use ZSTD_checkParams() to ensure that. */ |
| ZSTD_compressionParameters ZSTD_adjustCParams(ZSTD_compressionParameters cPar, unsigned long long srcSize, size_t dictSize) |
| { |
| if (srcSize + dictSize == 0) |
| return cPar; /* no size information available : no adjustment */ |
| |
| /* resize params, to use less memory when necessary */ |
| { |
| U32 const minSrcSize = (srcSize == 0) ? 500 : 0; |
| U64 const rSize = srcSize + dictSize + minSrcSize; |
| if (rSize < ((U64)1 << ZSTD_WINDOWLOG_MAX)) { |
| U32 const srcLog = MAX(ZSTD_HASHLOG_MIN, ZSTD_highbit32((U32)(rSize)-1) + 1); |
| if (cPar.windowLog > srcLog) |
| cPar.windowLog = srcLog; |
| } |
| } |
| if (cPar.hashLog > cPar.windowLog) |
| cPar.hashLog = cPar.windowLog; |
| { |
| U32 const cycleLog = ZSTD_cycleLog(cPar.chainLog, cPar.strategy); |
| if (cycleLog > cPar.windowLog) |
| cPar.chainLog -= (cycleLog - cPar.windowLog); |
| } |
| |
| if (cPar.windowLog < ZSTD_WINDOWLOG_ABSOLUTEMIN) |
| cPar.windowLog = ZSTD_WINDOWLOG_ABSOLUTEMIN; /* required for frame header */ |
| |
| return cPar; |
| } |
| |
| static U32 ZSTD_equivalentParams(ZSTD_parameters param1, ZSTD_parameters param2) |
| { |
| return (param1.cParams.hashLog == param2.cParams.hashLog) & (param1.cParams.chainLog == param2.cParams.chainLog) & |
| (param1.cParams.strategy == param2.cParams.strategy) & ((param1.cParams.searchLength == 3) == (param2.cParams.searchLength == 3)); |
| } |
| |
| /*! ZSTD_continueCCtx() : |
| reuse CCtx without reset (note : requires no dictionary) */ |
| static size_t ZSTD_continueCCtx(ZSTD_CCtx *cctx, ZSTD_parameters params, U64 frameContentSize) |
| { |
| U32 const end = (U32)(cctx->nextSrc - cctx->base); |
| cctx->params = params; |
| cctx->frameContentSize = frameContentSize; |
| cctx->lowLimit = end; |
| cctx->dictLimit = end; |
| cctx->nextToUpdate = end + 1; |
| cctx->stage = ZSTDcs_init; |
| cctx->dictID = 0; |
| cctx->loadedDictEnd = 0; |
| { |
| int i; |
| for (i = 0; i < ZSTD_REP_NUM; i++) |
| cctx->rep[i] = repStartValue[i]; |
| } |
| cctx->seqStore.litLengthSum = 0; /* force reset of btopt stats */ |
| xxh64_reset(&cctx->xxhState, 0); |
| return 0; |
| } |
| |
| typedef enum { ZSTDcrp_continue, ZSTDcrp_noMemset, ZSTDcrp_fullReset } ZSTD_compResetPolicy_e; |
| |
| /*! ZSTD_resetCCtx_advanced() : |
| note : `params` must be validated */ |
| static size_t ZSTD_resetCCtx_advanced(ZSTD_CCtx *zc, ZSTD_parameters params, U64 frameContentSize, ZSTD_compResetPolicy_e const crp) |
| { |
| if (crp == ZSTDcrp_continue) |
| if (ZSTD_equivalentParams(params, zc->params)) { |
| zc->flagStaticTables = 0; |
| zc->flagStaticHufTable = HUF_repeat_none; |
| return ZSTD_continueCCtx(zc, params, frameContentSize); |
| } |
| |
| { |
| size_t const blockSize = MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, (size_t)1 << params.cParams.windowLog); |
| U32 const divider = (params.cParams.searchLength == 3) ? 3 : 4; |
| size_t const maxNbSeq = blockSize / divider; |
| size_t const tokenSpace = blockSize + 11 * maxNbSeq; |
| size_t const chainSize = (params.cParams.strategy == ZSTD_fast) ? 0 : (1 << params.cParams.chainLog); |
| size_t const hSize = ((size_t)1) << params.cParams.hashLog; |
| U32 const hashLog3 = (params.cParams.searchLength > 3) ? 0 : MIN(ZSTD_HASHLOG3_MAX, params.cParams.windowLog); |
| size_t const h3Size = ((size_t)1) << hashLog3; |
| size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32); |
| void *ptr; |
| |
| /* Check if workSpace is large enough, alloc a new one if needed */ |
| { |
| size_t const optSpace = ((MaxML + 1) + (MaxLL + 1) + (MaxOff + 1) + (1 << Litbits)) * sizeof(U32) + |
| (ZSTD_OPT_NUM + 1) * (sizeof(ZSTD_match_t) + sizeof(ZSTD_optimal_t)); |
| size_t const neededSpace = tableSpace + (256 * sizeof(U32)) /* huffTable */ + tokenSpace + |
| (((params.cParams.strategy == ZSTD_btopt) || (params.cParams.strategy == ZSTD_btopt2)) ? optSpace : 0); |
| if (zc->workSpaceSize < neededSpace) { |
| ZSTD_free(zc->workSpace, zc->customMem); |
| zc->workSpace = ZSTD_malloc(neededSpace, zc->customMem); |
| if (zc->workSpace == NULL) |
| return ERROR(memory_allocation); |
| zc->workSpaceSize = neededSpace; |
| } |
| } |
| |
| if (crp != ZSTDcrp_noMemset) |
| memset(zc->workSpace, 0, tableSpace); /* reset tables only */ |
| xxh64_reset(&zc->xxhState, 0); |
| zc->hashLog3 = hashLog3; |
| zc->hashTable = (U32 *)(zc->workSpace); |
| zc->chainTable = zc->hashTable + hSize; |
| zc->hashTable3 = zc->chainTable + chainSize; |
| ptr = zc->hashTable3 + h3Size; |
| zc->hufTable = (HUF_CElt *)ptr; |
| zc->flagStaticTables = 0; |
| zc->flagStaticHufTable = HUF_repeat_none; |
| ptr = ((U32 *)ptr) + 256; /* note : HUF_CElt* is incomplete type, size is simulated using U32 */ |
| |
| zc->nextToUpdate = 1; |
| zc->nextSrc = NULL; |
| zc->base = NULL; |
| zc->dictBase = NULL; |
| zc->dictLimit = 0; |
| zc->lowLimit = 0; |
| zc->params = params; |
| zc->blockSize = blockSize; |
| zc->frameContentSize = frameContentSize; |
| { |
| int i; |
| for (i = 0; i < ZSTD_REP_NUM; i++) |
| zc->rep[i] = repStartValue[i]; |
| } |
| |
| if ((params.cParams.strategy == ZSTD_btopt) || (params.cParams.strategy == ZSTD_btopt2)) { |
| zc->seqStore.litFreq = (U32 *)ptr; |
| zc->seqStore.litLengthFreq = zc->seqStore.litFreq + (1 << Litbits); |
| zc->seqStore.matchLengthFreq = zc->seqStore.litLengthFreq + (MaxLL + 1); |
| zc->seqStore.offCodeFreq = zc->seqStore.matchLengthFreq + (MaxML + 1); |
| ptr = zc->seqStore.offCodeFreq + (MaxOff + 1); |
| zc->seqStore.matchTable = (ZSTD_match_t *)ptr; |
| ptr = zc->seqStore.matchTable + ZSTD_OPT_NUM + 1; |
| zc->seqStore.priceTable = (ZSTD_optimal_t *)ptr; |
| ptr = zc->seqStore.priceTable + ZSTD_OPT_NUM + 1; |
| zc->seqStore.litLengthSum = 0; |
| } |
| zc->seqStore.sequencesStart = (seqDef *)ptr; |
| ptr = zc->seqStore.sequencesStart + maxNbSeq; |
| zc->seqStore.llCode = (BYTE *)ptr; |
| zc->seqStore.mlCode = zc->seqStore.llCode + maxNbSeq; |
| zc->seqStore.ofCode = zc->seqStore.mlCode + maxNbSeq; |
| zc->seqStore.litStart = zc->seqStore.ofCode + maxNbSeq; |
| |
| zc->stage = ZSTDcs_init; |
| zc->dictID = 0; |
| zc->loadedDictEnd = 0; |
| |
| return 0; |
| } |
| } |
| |
| /* ZSTD_invalidateRepCodes() : |
| * ensures next compression will not use repcodes from previous block. |
| * Note : only works with regular variant; |
| * do not use with extDict variant ! */ |
| void ZSTD_invalidateRepCodes(ZSTD_CCtx *cctx) |
| { |
| int i; |
| for (i = 0; i < ZSTD_REP_NUM; i++) |
| cctx->rep[i] = 0; |
| } |
| |
| /*! ZSTD_copyCCtx() : |
| * Duplicate an existing context `srcCCtx` into another one `dstCCtx`. |
| * Only works during stage ZSTDcs_init (i.e. after creation, but before first call to ZSTD_compressContinue()). |
| * @return : 0, or an error code */ |
| size_t ZSTD_copyCCtx(ZSTD_CCtx *dstCCtx, const ZSTD_CCtx *srcCCtx, unsigned long long pledgedSrcSize) |
| { |
| if (srcCCtx->stage != ZSTDcs_init) |
| return ERROR(stage_wrong); |
| |
| memcpy(&dstCCtx->customMem, &srcCCtx->customMem, sizeof(ZSTD_customMem)); |
| { |
| ZSTD_parameters params = srcCCtx->params; |
| params.fParams.contentSizeFlag = (pledgedSrcSize > 0); |
| ZSTD_resetCCtx_advanced(dstCCtx, params, pledgedSrcSize, ZSTDcrp_noMemset); |
| } |
| |
| /* copy tables */ |
| { |
| size_t const chainSize = (srcCCtx->params.cParams.strategy == ZSTD_fast) ? 0 : (1 << srcCCtx->params.cParams.chainLog); |
| size_t const hSize = ((size_t)1) << srcCCtx->params.cParams.hashLog; |
| size_t const h3Size = (size_t)1 << srcCCtx->hashLog3; |
| size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32); |
| memcpy(dstCCtx->workSpace, srcCCtx->workSpace, tableSpace); |
| } |
| |
| /* copy dictionary offsets */ |
| dstCCtx->nextToUpdate = srcCCtx->nextToUpdate; |
| dstCCtx->nextToUpdate3 = srcCCtx->nextToUpdate3; |
| dstCCtx->nextSrc = srcCCtx->nextSrc; |
| dstCCtx->base = srcCCtx->base; |
| dstCCtx->dictBase = srcCCtx->dictBase; |
| dstCCtx->dictLimit = srcCCtx->dictLimit; |
| dstCCtx->lowLimit = srcCCtx->lowLimit; |
| dstCCtx->loadedDictEnd = srcCCtx->loadedDictEnd; |
| dstCCtx->dictID = srcCCtx->dictID; |
| |
| /* copy entropy tables */ |
| dstCCtx->flagStaticTables = srcCCtx->flagStaticTables; |
| dstCCtx->flagStaticHufTable = srcCCtx->flagStaticHufTable; |
| if (srcCCtx->flagStaticTables) { |
| memcpy(dstCCtx->litlengthCTable, srcCCtx->litlengthCTable, sizeof(dstCCtx->litlengthCTable)); |
| memcpy(dstCCtx->matchlengthCTable, srcCCtx->matchlengthCTable, sizeof(dstCCtx->matchlengthCTable)); |
| memcpy(dstCCtx->offcodeCTable, srcCCtx->offcodeCTable, sizeof(dstCCtx->offcodeCTable)); |
| } |
| if (srcCCtx->flagStaticHufTable) { |
| memcpy(dstCCtx->hufTable, srcCCtx->hufTable, 256 * 4); |
| } |
| |
| return 0; |
| } |
| |
| /*! ZSTD_reduceTable() : |
| * reduce table indexes by `reducerValue` */ |
| static void ZSTD_reduceTable(U32 *const table, U32 const size, U32 const reducerValue) |
| { |
| U32 u; |
| for (u = 0; u < size; u++) { |
| if (table[u] < reducerValue) |
| table[u] = 0; |
| else |
| table[u] -= reducerValue; |
| } |
| } |
| |
| /*! ZSTD_reduceIndex() : |
| * rescale all indexes to avoid future overflow (indexes are U32) */ |
| static void ZSTD_reduceIndex(ZSTD_CCtx *zc, const U32 reducerValue) |
| { |
| { |
| U32 const hSize = 1 << zc->params.cParams.hashLog; |
| ZSTD_reduceTable(zc->hashTable, hSize, reducerValue); |
| } |
| |
| { |
| U32 const chainSize = (zc->params.cParams.strategy == ZSTD_fast) ? 0 : (1 << zc->params.cParams.chainLog); |
| ZSTD_reduceTable(zc->chainTable, chainSize, reducerValue); |
| } |
| |
| { |
| U32 const h3Size = (zc->hashLog3) ? 1 << zc->hashLog3 : 0; |
| ZSTD_reduceTable(zc->hashTable3, h3Size, reducerValue); |
| } |
| } |
| |
| /*-******************************************************* |
| * Block entropic compression |
| *********************************************************/ |
| |
| /* See doc/zstd_compression_format.md for detailed format description */ |
| |
| size_t ZSTD_noCompressBlock(void *dst, size_t dstCapacity, const void *src, size_t srcSize) |
| { |
| if (srcSize + ZSTD_blockHeaderSize > dstCapacity) |
| return ERROR(dstSize_tooSmall); |
| memcpy((BYTE *)dst + ZSTD_blockHeaderSize, src, srcSize); |
| ZSTD_writeLE24(dst, (U32)(srcSize << 2) + (U32)bt_raw); |
| return ZSTD_blockHeaderSize + srcSize; |
| } |
| |
| static size_t ZSTD_noCompressLiterals(void *dst, size_t dstCapacity, const void *src, size_t srcSize) |
| { |
| BYTE *const ostart = (BYTE * const)dst; |
| U32 const flSize = 1 + (srcSize > 31) + (srcSize > 4095); |
| |
| if (srcSize + flSize > dstCapacity) |
| return ERROR(dstSize_tooSmall); |
| |
| switch (flSize) { |
| case 1: /* 2 - 1 - 5 */ ostart[0] = (BYTE)((U32)set_basic + (srcSize << 3)); break; |
| case 2: /* 2 - 2 - 12 */ ZSTD_writeLE16(ostart, (U16)((U32)set_basic + (1 << 2) + (srcSize << 4))); break; |
| default: /*note : should not be necessary : flSize is within {1,2,3} */ |
| case 3: /* 2 - 2 - 20 */ ZSTD_writeLE32(ostart, (U32)((U32)set_basic + (3 << 2) + (srcSize << 4))); break; |
| } |
| |
| memcpy(ostart + flSize, src, srcSize); |
| return srcSize + flSize; |
| } |
| |
| static size_t ZSTD_compressRleLiteralsBlock(void *dst, size_t dstCapacity, const void *src, size_t srcSize) |
| { |
| BYTE *const ostart = (BYTE * const)dst; |
| U32 const flSize = 1 + (srcSize > 31) + (srcSize > 4095); |
| |
| (void)dstCapacity; /* dstCapacity already guaranteed to be >=4, hence large enough */ |
| |
| switch (flSize) { |
| case 1: /* 2 - 1 - 5 */ ostart[0] = (BYTE)((U32)set_rle + (srcSize << 3)); break; |
| case 2: /* 2 - 2 - 12 */ ZSTD_writeLE16(ostart, (U16)((U32)set_rle + (1 << 2) + (srcSize << 4))); break; |
| default: /*note : should not be necessary : flSize is necessarily within {1,2,3} */ |
| case 3: /* 2 - 2 - 20 */ ZSTD_writeLE32(ostart, (U32)((U32)set_rle + (3 << 2) + (srcSize << 4))); break; |
| } |
| |
| ostart[flSize] = *(const BYTE *)src; |
| return flSize + 1; |
| } |
| |
| static size_t ZSTD_minGain(size_t srcSize) { return (srcSize >> 6) + 2; } |
| |
| static size_t ZSTD_compressLiterals(ZSTD_CCtx *zc, void *dst, size_t dstCapacity, const void *src, size_t srcSize) |
| { |
| size_t const minGain = ZSTD_minGain(srcSize); |
| size_t const lhSize = 3 + (srcSize >= 1 KB) + (srcSize >= 16 KB); |
| BYTE *const ostart = (BYTE *)dst; |
| U32 singleStream = srcSize < 256; |
| symbolEncodingType_e hType = set_compressed; |
| size_t cLitSize; |
| |
| /* small ? don't even attempt compression (speed opt) */ |
| #define LITERAL_NOENTROPY 63 |
| { |
| size_t const minLitSize = zc->flagStaticHufTable == HUF_repeat_valid ? 6 : LITERAL_NOENTROPY; |
| if (srcSize <= minLitSize) |
| return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize); |
| } |
| |
| if (dstCapacity < lhSize + 1) |
| return ERROR(dstSize_tooSmall); /* not enough space for compression */ |
| { |
| HUF_repeat repeat = zc->flagStaticHufTable; |
| int const preferRepeat = zc->params.cParams.strategy < ZSTD_lazy ? srcSize <= 1024 : 0; |
| if (repeat == HUF_repeat_valid && lhSize == 3) |
| singleStream = 1; |
| cLitSize = singleStream ? HUF_compress1X_repeat(ostart + lhSize, dstCapacity - lhSize, src, srcSize, 255, 11, zc->tmpCounters, |
| sizeof(zc->tmpCounters), zc->hufTable, &repeat, preferRepeat) |
| : HUF_compress4X_repeat(ostart + lhSize, dstCapacity - lhSize, src, srcSize, 255, 11, zc->tmpCounters, |
| sizeof(zc->tmpCounters), zc->hufTable, &repeat, preferRepeat); |
| if (repeat != HUF_repeat_none) { |
| hType = set_repeat; |
| } /* reused the existing table */ |
| else { |
| zc->flagStaticHufTable = HUF_repeat_check; |
| } /* now have a table to reuse */ |
| } |
| |
| if ((cLitSize == 0) | (cLitSize >= srcSize - minGain)) { |
| zc->flagStaticHufTable = HUF_repeat_none; |
| return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize); |
| } |
| if (cLitSize == 1) { |
| zc->flagStaticHufTable = HUF_repeat_none; |
| return ZSTD_compressRleLiteralsBlock(dst, dstCapacity, src, srcSize); |
| } |
| |
| /* Build header */ |
| switch (lhSize) { |
| case 3: /* 2 - 2 - 10 - 10 */ |
| { |
| U32 const lhc = hType + ((!singleStream) << 2) + ((U32)srcSize << 4) + ((U32)cLitSize << 14); |
| ZSTD_writeLE24(ostart, lhc); |
| break; |
| } |
| case 4: /* 2 - 2 - 14 - 14 */ |
| { |
| U32 const lhc = hType + (2 << 2) + ((U32)srcSize << 4) + ((U32)cLitSize << 18); |
| ZSTD_writeLE32(ostart, lhc); |
| break; |
| } |
| default: /* should not be necessary, lhSize is only {3,4,5} */ |
| case 5: /* 2 - 2 - 18 - 18 */ |
| { |
| U32 const lhc = hType + (3 << 2) + ((U32)srcSize << 4) + ((U32)cLitSize << 22); |
| ZSTD_writeLE32(ostart, lhc); |
| ostart[4] = (BYTE)(cLitSize >> 10); |
| break; |
| } |
| } |
| return lhSize + cLitSize; |
| } |
| |
| static 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, |
| 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, |
| 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24}; |
| |
| static 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, |
| 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, |
| 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, |
| 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, |
| 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42}; |
| |
| void ZSTD_seqToCodes(const seqStore_t *seqStorePtr) |
| { |
| BYTE const LL_deltaCode = 19; |
| BYTE const ML_deltaCode = 36; |
| const seqDef *const sequences = seqStorePtr->sequencesStart; |
| BYTE *const llCodeTable = seqStorePtr->llCode; |
| BYTE *const ofCodeTable = seqStorePtr->ofCode; |
| BYTE *const mlCodeTable = seqStorePtr->mlCode; |
| U32 const nbSeq = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); |
| U32 u; |
| for (u = 0; u < nbSeq; u++) { |
| U32 const llv = sequences[u].litLength; |
| U32 const mlv = sequences[u].matchLength; |
| llCodeTable[u] = (llv > 63) ? (BYTE)ZSTD_highbit32(llv) + LL_deltaCode : LL_Code[llv]; |
| ofCodeTable[u] = (BYTE)ZSTD_highbit32(sequences[u].offset); |
| mlCodeTable[u] = (mlv > 127) ? (BYTE)ZSTD_highbit32(mlv) + ML_deltaCode : ML_Code[mlv]; |
| } |
| if (seqStorePtr->longLengthID == 1) |
| llCodeTable[seqStorePtr->longLengthPos] = MaxLL; |
| if (seqStorePtr->longLengthID == 2) |
| mlCodeTable[seqStorePtr->longLengthPos] = MaxML; |
| } |
| |
| ZSTD_STATIC size_t ZSTD_compressSequences_internal(ZSTD_CCtx *zc, void *dst, size_t dstCapacity) |
| { |
| const int longOffsets = zc->params.cParams.windowLog > STREAM_ACCUMULATOR_MIN; |
| const seqStore_t *seqStorePtr = &(zc->seqStore); |
| FSE_CTable *CTable_LitLength = zc->litlengthCTable; |
| FSE_CTable *CTable_OffsetBits = zc->offcodeCTable; |
| FSE_CTable *CTable_MatchLength = zc->matchlengthCTable; |
| U32 LLtype, Offtype, MLtype; /* compressed, raw or rle */ |
| const seqDef *const sequences = seqStorePtr->sequencesStart; |
| const BYTE *const ofCodeTable = seqStorePtr->ofCode; |
| const BYTE *const llCodeTable = seqStorePtr->llCode; |
| const BYTE *const mlCodeTable = seqStorePtr->mlCode; |
| BYTE *const ostart = (BYTE *)dst; |
| BYTE *const oend = ostart + dstCapacity; |
| BYTE *op = ostart; |
| size_t const nbSeq = seqStorePtr->sequences - seqStorePtr->sequencesStart; |
| BYTE *seqHead; |
| |
| U32 *count; |
| S16 *norm; |
| U32 *workspace; |
| size_t workspaceSize = sizeof(zc->tmpCounters); |
| { |
| size_t spaceUsed32 = 0; |
| count = (U32 *)zc->tmpCounters + spaceUsed32; |
| spaceUsed32 += MaxSeq + 1; |
| norm = (S16 *)((U32 *)zc->tmpCounters + spaceUsed32); |
| spaceUsed32 += ALIGN(sizeof(S16) * (MaxSeq + 1), sizeof(U32)) >> 2; |
| |
| workspace = (U32 *)zc->tmpCounters + spaceUsed32; |
| workspaceSize -= (spaceUsed32 << 2); |
| } |
| |
| /* Compress literals */ |
| { |
| const BYTE *const literals = seqStorePtr->litStart; |
| size_t const litSize = seqStorePtr->lit - literals; |
| size_t const cSize = ZSTD_compressLiterals(zc, op, dstCapacity, literals, litSize); |
| if (ZSTD_isError(cSize)) |
| return cSize; |
| op += cSize; |
| } |
| |
| /* Sequences Header */ |
| if ((oend - op) < 3 /*max nbSeq Size*/ + 1 /*seqHead */) |
| return ERROR(dstSize_tooSmall); |
| if (nbSeq < 0x7F) |
| *op++ = (BYTE)nbSeq; |
| else if (nbSeq < LONGNBSEQ) |
| op[0] = (BYTE)((nbSeq >> 8) + 0x80), op[1] = (BYTE)nbSeq, op += 2; |
| else |
| op[0] = 0xFF, ZSTD_writeLE16(op + 1, (U16)(nbSeq - LONGNBSEQ)), op += 3; |
| if (nbSeq == 0) |
| return op - ostart; |
| |
| /* seqHead : flags for FSE encoding type */ |
| seqHead = op++; |
| |
| #define MIN_SEQ_FOR_DYNAMIC_FSE 64 |
| #define MAX_SEQ_FOR_STATIC_FSE 1000 |
| |
| /* convert length/distances into codes */ |
| ZSTD_seqToCodes(seqStorePtr); |
| |
| /* CTable for Literal Lengths */ |
| { |
| U32 max = MaxLL; |
| size_t const mostFrequent = FSE_countFast_wksp(count, &max, llCodeTable, nbSeq, workspace); |
| if ((mostFrequent == nbSeq) && (nbSeq > 2)) { |
| *op++ = llCodeTable[0]; |
| FSE_buildCTable_rle(CTable_LitLength, (BYTE)max); |
| LLtype = set_rle; |
| } else if ((zc->flagStaticTables) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) { |
| LLtype = set_repeat; |
| } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (LL_defaultNormLog - 1)))) { |
| FSE_buildCTable_wksp(CTable_LitLength, LL_defaultNorm, MaxLL, LL_defaultNormLog, workspace, workspaceSize); |
| LLtype = set_basic; |
| } else { |
| size_t nbSeq_1 = nbSeq; |
| const U32 tableLog = FSE_optimalTableLog(LLFSELog, nbSeq, max); |
| if (count[llCodeTable[nbSeq - 1]] > 1) { |
| count[llCodeTable[nbSeq - 1]]--; |
| nbSeq_1--; |
| } |
| FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max); |
| { |
| size_t const NCountSize = FSE_writeNCount(op, oend - op, norm, max, tableLog); /* overflow protected */ |
| if (FSE_isError(NCountSize)) |
| return NCountSize; |
| op += NCountSize; |
| } |
| FSE_buildCTable_wksp(CTable_LitLength, norm, max, tableLog, workspace, workspaceSize); |
| LLtype = set_compressed; |
| } |
| } |
| |
| /* CTable for Offsets */ |
| { |
| U32 max = MaxOff; |
| size_t const mostFrequent = FSE_countFast_wksp(count, &max, ofCodeTable, nbSeq, workspace); |
| if ((mostFrequent == nbSeq) && (nbSeq > 2)) { |
| *op++ = ofCodeTable[0]; |
| FSE_buildCTable_rle(CTable_OffsetBits, (BYTE)max); |
| Offtype = set_rle; |
| } else if ((zc->flagStaticTables) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) { |
| Offtype = set_repeat; |
| } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (OF_defaultNormLog - 1)))) { |
| FSE_buildCTable_wksp(CTable_OffsetBits, OF_defaultNorm, MaxOff, OF_defaultNormLog, workspace, workspaceSize); |
| Offtype = set_basic; |
| } else { |
| size_t nbSeq_1 = nbSeq; |
| const U32 tableLog = FSE_optimalTableLog(OffFSELog, nbSeq, max); |
| if (count[ofCodeTable[nbSeq - 1]] > 1) { |
| count[ofCodeTable[nbSeq - 1]]--; |
| nbSeq_1--; |
| } |
| FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max); |
| { |
| size_t const NCountSize = FSE_writeNCount(op, oend - op, norm, max, tableLog); /* overflow protected */ |
| if (FSE_isError(NCountSize)) |
| return NCountSize; |
| op += NCountSize; |
| } |
| FSE_buildCTable_wksp(CTable_OffsetBits, norm, max, tableLog, workspace, workspaceSize); |
| Offtype = set_compressed; |
| } |
| } |
| |
| /* CTable for MatchLengths */ |
| { |
| U32 max = MaxML; |
| size_t const mostFrequent = FSE_countFast_wksp(count, &max, mlCodeTable, nbSeq, workspace); |
| if ((mostFrequent == nbSeq) && (nbSeq > 2)) { |
| *op++ = *mlCodeTable; |
| FSE_buildCTable_rle(CTable_MatchLength, (BYTE)max); |
| MLtype = set_rle; |
| } else if ((zc->flagStaticTables) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) { |
| MLtype = set_repeat; |
| } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (ML_defaultNormLog - 1)))) { |
| FSE_buildCTable_wksp(CTable_MatchLength, ML_defaultNorm, MaxML, ML_defaultNormLog, workspace, workspaceSize); |
| MLtype = set_basic; |
| } else { |
| size_t nbSeq_1 = nbSeq; |
| const U32 tableLog = FSE_optimalTableLog(MLFSELog, nbSeq, max); |
| if (count[mlCodeTable[nbSeq - 1]] > 1) { |
| count[mlCodeTable[nbSeq - 1]]--; |
| nbSeq_1--; |
| } |
| FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max); |
| { |
| size_t const NCountSize = FSE_writeNCount(op, oend - op, norm, max, tableLog); /* overflow protected */ |
| if (FSE_isError(NCountSize)) |
| return NCountSize; |
| op += NCountSize; |
| } |
| FSE_buildCTable_wksp(CTable_MatchLength, norm, max, tableLog, workspace, workspaceSize); |
| MLtype = set_compressed; |
| } |
| } |
| |
| *seqHead = (BYTE)((LLtype << 6) + (Offtype << 4) + (MLtype << 2)); |
| zc->flagStaticTables = 0; |
| |
| /* Encoding Sequences */ |
| { |
| BIT_CStream_t blockStream; |
| FSE_CState_t stateMatchLength; |
| FSE_CState_t stateOffsetBits; |
| FSE_CState_t stateLitLength; |
| |
| CHECK_E(BIT_initCStream(&blockStream, op, oend - op), dstSize_tooSmall); /* not enough space remaining */ |
| |
| /* first symbols */ |
| FSE_initCState2(&stateMatchLength, CTable_MatchLength, mlCodeTable[nbSeq - 1]); |
| FSE_initCState2(&stateOffsetBits, CTable_OffsetBits, ofCodeTable[nbSeq - 1]); |
| FSE_initCState2(&stateLitLength, CTable_LitLength, llCodeTable[nbSeq - 1]); |
| BIT_addBits(&blockStream, sequences[nbSeq - 1].litLength, LL_bits[llCodeTable[nbSeq - 1]]); |
| if (ZSTD_32bits()) |
| BIT_flushBits(&blockStream); |
| BIT_addBits(&blockStream, sequences[nbSeq - 1].matchLength, ML_bits[mlCodeTable[nbSeq - 1]]); |
| if (ZSTD_32bits()) |
| BIT_flushBits(&blockStream); |
| if (longOffsets) { |
| U32 const ofBits = ofCodeTable[nbSeq - 1]; |
| int const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN - 1); |
| if (extraBits) { |
| BIT_addBits(&blockStream, sequences[nbSeq - 1].offset, extraBits); |
| BIT_flushBits(&blockStream); |
| } |
| BIT_addBits(&blockStream, sequences[nbSeq - 1].offset >> extraBits, ofBits - extraBits); |
| } else { |
| BIT_addBits(&blockStream, sequences[nbSeq - 1].offset, ofCodeTable[nbSeq - 1]); |
| } |
| BIT_flushBits(&blockStream); |
| |
| { |
| size_t n; |
| for (n = nbSeq - 2; n < nbSeq; n--) { /* intentional underflow */ |
| BYTE const llCode = llCodeTable[n]; |
| BYTE const ofCode = ofCodeTable[n]; |
| BYTE const mlCode = mlCodeTable[n]; |
| U32 const llBits = LL_bits[llCode]; |
| U32 const ofBits = ofCode; /* 32b*/ /* 64b*/ |
| U32 const mlBits = ML_bits[mlCode]; |
| /* (7)*/ /* (7)*/ |
| FSE_encodeSymbol(&blockStream, &stateOffsetBits, ofCode); /* 15 */ /* 15 */ |
| FSE_encodeSymbol(&blockStream, &stateMatchLength, mlCode); /* 24 */ /* 24 */ |
| if (ZSTD_32bits()) |
| BIT_flushBits(&blockStream); /* (7)*/ |
| FSE_encodeSymbol(&blockStream, &stateLitLength, llCode); /* 16 */ /* 33 */ |
| if (ZSTD_32bits() || (ofBits + mlBits + llBits >= 64 - 7 - (LLFSELog + MLFSELog + OffFSELog))) |
| BIT_flushBits(&blockStream); /* (7)*/ |
| BIT_addBits(&blockStream, sequences[n].litLength, llBits); |
| if (ZSTD_32bits() && ((llBits + mlBits) > 24)) |
| BIT_flushBits(&blockStream); |
| BIT_addBits(&blockStream, sequences[n].matchLength, mlBits); |
| if (ZSTD_32bits()) |
| BIT_flushBits(&blockStream); /* (7)*/ |
| if (longOffsets) { |
| int const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN - 1); |
| if (extraBits) { |
| BIT_addBits(&blockStream, sequences[n].offset, extraBits); |
| BIT_flushBits(&blockStream); /* (7)*/ |
| } |
| BIT_addBits(&blockStream, sequences[n].offset >> extraBits, ofBits - extraBits); /* 31 */ |
| } else { |
| BIT_addBits(&blockStream, sequences[n].offset, ofBits); /* 31 */ |
| } |
| BIT_flushBits(&blockStream); /* (7)*/ |
| } |
| } |
| |
| FSE_flushCState(&blockStream, &stateMatchLength); |
| FSE_flushCState(&blockStream, &stateOffsetBits); |
| FSE_flushCState(&blockStream, &stateLitLength); |
| |
| { |
| size_t const streamSize = BIT_closeCStream(&blockStream); |
| if (streamSize == 0) |
| return ERROR(dstSize_tooSmall); /* not enough space */ |
| op += streamSize; |
| } |
| } |
| return op - ostart; |
| } |
| |
| ZSTD_STATIC size_t ZSTD_compressSequences(ZSTD_CCtx *zc, void *dst, size_t dstCapacity, size_t srcSize) |
| { |
| size_t const cSize = ZSTD_compressSequences_internal(zc, dst, dstCapacity); |
| size_t const minGain = ZSTD_minGain(srcSize); |
| size_t const maxCSize = srcSize - minGain; |
| /* If the srcSize <= dstCapacity, then there is enough space to write a |
| * raw uncompressed block. Since we ran out of space, the block must not |
| * be compressible, so fall back to a raw uncompressed block. |
| */ |
| int const uncompressibleError = cSize == ERROR(dstSize_tooSmall) && srcSize <= dstCapacity; |
| int i; |
| |
| if (ZSTD_isError(cSize) && !uncompressibleError) |
| return cSize; |
| if (cSize >= maxCSize || uncompressibleError) { |
| zc->flagStaticHufTable = HUF_repeat_none; |
| return 0; |
| } |
| /* confirm repcodes */ |
| for (i = 0; i < ZSTD_REP_NUM; i++) |
| zc->rep[i] = zc->repToConfirm[i]; |
| return cSize; |
| } |
| |
| /*! ZSTD_storeSeq() : |
| Store a sequence (literal length, literals, offset code and match length code) into seqStore_t. |
| `offsetCode` : distance to match, or 0 == repCode. |
| `matchCode` : matchLength - MINMATCH |
| */ |
| ZSTD_STATIC void ZSTD_storeSeq(seqStore_t *seqStorePtr, size_t litLength, const void *literals, U32 offsetCode, size_t matchCode) |
| { |
| /* copy Literals */ |
| ZSTD_wildcopy(seqStorePtr->lit, literals, litLength); |
| seqStorePtr->lit += litLength; |
| |
| /* literal Length */ |
| if (litLength > 0xFFFF) { |
| seqStorePtr->longLengthID = 1; |
| seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); |
| } |
| seqStorePtr->sequences[0].litLength = (U16)litLength; |
| |
| /* match offset */ |
| seqStorePtr->sequences[0].offset = offsetCode + 1; |
| |
| /* match Length */ |
| if (matchCode > 0xFFFF) { |
| seqStorePtr->longLengthID = 2; |
| seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); |
| } |
| seqStorePtr->sequences[0].matchLength = (U16)matchCode; |
| |
| seqStorePtr->sequences++; |
| } |
| |
| /*-************************************* |
| * Match length counter |
| ***************************************/ |
| static unsigned ZSTD_NbCommonBytes(register size_t val) |
| { |
| if (ZSTD_isLittleEndian()) { |
| if (ZSTD_64bits()) { |
| return (__builtin_ctzll((U64)val) >> 3); |
| } else { /* 32 bits */ |
| return (__builtin_ctz((U32)val) >> 3); |
| } |
| } else { /* Big Endian CPU */ |
| if (ZSTD_64bits()) { |
| return (__builtin_clzll(val) >> 3); |
| } else { /* 32 bits */ |
| return (__builtin_clz((U32)val) >> 3); |
| } |
| } |
| } |
| |
| static size_t ZSTD_count(const BYTE *pIn, const BYTE *pMatch, const BYTE *const pInLimit) |
| { |
| const BYTE *const pStart = pIn; |
| const BYTE *const pInLoopLimit = pInLimit - (sizeof(size_t) - 1); |
| |
| while (pIn < pInLoopLimit) { |
| size_t const diff = ZSTD_readST(pMatch) ^ ZSTD_readST(pIn); |
| if (!diff) { |
| pIn += sizeof(size_t); |
| pMatch += sizeof(size_t); |
| continue; |
| } |
| pIn += ZSTD_NbCommonBytes(diff); |
| return (size_t)(pIn - pStart); |
| } |
| if (ZSTD_64bits()) |
| if ((pIn < (pInLimit - 3)) && (ZSTD_read32(pMatch) == ZSTD_read32(pIn))) { |
| pIn += 4; |
| pMatch += 4; |
| } |
| if ((pIn < (pInLimit - 1)) && (ZSTD_read16(pMatch) == ZSTD_read16(pIn))) { |
| pIn += 2; |
| pMatch += 2; |
| } |
| if ((pIn < pInLimit) && (*pMatch == *pIn)) |
| pIn++; |
| return (size_t)(pIn - pStart); |
| } |
| |
| /** ZSTD_count_2segments() : |
| * can count match length with `ip` & `match` in 2 different segments. |
| * convention : on reaching mEnd, match count continue starting from iStart |
| */ |
| static size_t ZSTD_count_2segments(const BYTE *ip, const BYTE *match, const BYTE *iEnd, const BYTE *mEnd, const BYTE *iStart) |
| { |
| const BYTE *const vEnd = MIN(ip + (mEnd - match), iEnd); |
| size_t const matchLength = ZSTD_count(ip, match, vEnd); |
| if (match + matchLength != mEnd) |
| return matchLength; |
| return matchLength + ZSTD_count(ip + matchLength, iStart, iEnd); |
| } |
| |
| /*-************************************* |
| * Hashes |
| ***************************************/ |
| static const U32 prime3bytes = 506832829U; |
| static U32 ZSTD_hash3(U32 u, U32 h) { return ((u << (32 - 24)) * prime3bytes) >> (32 - h); } |
| ZSTD_STATIC size_t ZSTD_hash3Ptr(const void *ptr, U32 h) { return ZSTD_hash3(ZSTD_readLE32(ptr), h); } /* only in zstd_opt.h */ |
| |
| static const U32 prime4bytes = 2654435761U; |
| static U32 ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32 - h); } |
| static size_t ZSTD_hash4Ptr(const void *ptr, U32 h) { return ZSTD_hash4(ZSTD_read32(ptr), h); } |
| |
| static const U64 prime5bytes = 889523592379ULL; |
| static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u << (64 - 40)) * prime5bytes) >> (64 - h)); } |
| static size_t ZSTD_hash5Ptr(const void *p, U32 h) { return ZSTD_hash5(ZSTD_readLE64(p), h); } |
| |
| static const U64 prime6bytes = 227718039650203ULL; |
| static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u << (64 - 48)) * prime6bytes) >> (64 - h)); } |
| static size_t ZSTD_hash6Ptr(const void *p, U32 h) { return ZSTD_hash6(ZSTD_readLE64(p), h); } |
| |
| static const U64 prime7bytes = 58295818150454627ULL; |
| static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u << (64 - 56)) * prime7bytes) >> (64 - h)); } |
| static size_t ZSTD_hash7Ptr(const void *p, U32 h) { return ZSTD_hash7(ZSTD_readLE64(p), h); } |
| |
| static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL; |
| static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u)*prime8bytes) >> (64 - h)); } |
| static size_t ZSTD_hash8Ptr(const void *p, U32 h) { return ZSTD_hash8(ZSTD_readLE64(p), h); } |
| |
| static size_t ZSTD_hashPtr(const void *p, U32 hBits, U32 mls) |
| { |
| switch (mls) { |
| // case 3: return ZSTD_hash3Ptr(p, hBits); |
| default: |
| case 4: return ZSTD_hash4Ptr(p, hBits); |
| case 5: return ZSTD_hash5Ptr(p, hBits); |
| case 6: return ZSTD_hash6Ptr(p, hBits); |
| case 7: return ZSTD_hash7Ptr(p, hBits); |
| case 8: return ZSTD_hash8Ptr(p, hBits); |
| } |
| } |
| |
| /*-************************************* |
| * Fast Scan |
| ***************************************/ |
| static void ZSTD_fillHashTable(ZSTD_CCtx *zc, const void *end, const U32 mls) |
| { |
| U32 *const hashTable = zc->hashTable; |
| U32 const hBits = zc->params.cParams.hashLog; |
| const BYTE *const base = zc->base; |
| const BYTE *ip = base + zc->nextToUpdate; |
| const BYTE *const iend = ((const BYTE *)end) - HASH_READ_SIZE; |
| const size_t fastHashFillStep = 3; |
| |
| while (ip <= iend) { |
| hashTable[ZSTD_hashPtr(ip, hBits, mls)] = (U32)(ip - base); |
| ip += fastHashFillStep; |
| } |
| } |
| |
| FORCE_INLINE |
| void ZSTD_compressBlock_fast_generic(ZSTD_CCtx *cctx, const void *src, size_t srcSize, const U32 mls) |
| { |
| U32 *const hashTable = cctx->hashTable; |
| U32 const hBits = cctx->params.cParams.hashLog; |
| seqStore_t *seqStorePtr = &(cctx->seqStore); |
| const BYTE *const base = cctx->base; |
| const BYTE *const istart = (const BYTE *)src; |
| const BYTE *ip = istart; |
| const BYTE *anchor = istart; |
| const U32 lowestIndex = cctx->dictLimit; |
| const BYTE *const lowest = base + lowestIndex; |
| const BYTE *const iend = istart + srcSize; |
| const BYTE *const ilimit = iend - HASH_READ_SIZE; |
| U32 offset_1 = cctx->rep[0], offset_2 = cctx->rep[1]; |
| U32 offsetSaved = 0; |
| |
| /* init */ |
| ip += (ip == lowest); |
| { |
| U32 const maxRep = (U32)(ip - lowest); |
| if (offset_2 > maxRep) |
| offsetSaved = offset_2, offset_2 = 0; |
| if (offset_1 > maxRep) |
| offsetSaved = offset_1, offset_1 = 0; |
| } |
| |
| /* Main Search Loop */ |
| while (ip < ilimit) { /* < instead of <=, because repcode check at (ip+1) */ |
| size_t mLength; |
| size_t const h = ZSTD_hashPtr(ip, hBits, mls); |
| U32 const curr = (U32)(ip - base); |
| U32 const matchIndex = hashTable[h]; |
| const BYTE *match = base + matchIndex; |
| hashTable[h] = curr; /* update hash table */ |
| |
| if ((offset_1 > 0) & (ZSTD_read32(ip + 1 - offset_1) == ZSTD_read32(ip + 1))) { |
| mLength = ZSTD_count(ip + 1 + 4, ip + 1 + 4 - offset_1, iend) + 4; |
| ip++; |
| ZSTD_storeSeq(seqStorePtr, ip - anchor, anchor, 0, mLength - MINMATCH); |
| } else { |
| U32 offset; |
| if ((matchIndex <= lowestIndex) || (ZSTD_read32(match) != ZSTD_read32(ip))) { |
| ip += ((ip - anchor) >> g_searchStrength) + 1; |
| continue; |
| } |
| mLength = ZSTD_count(ip + 4, match + 4, iend) + 4; |
| offset = (U32)(ip - match); |
| while (((ip > anchor) & (match > lowest)) && (ip[-1] == match[-1])) { |
| ip--; |
| match--; |
| mLength++; |
| } /* catch up */ |
| offset_2 = offset_1; |
| offset_1 = offset; |
| |
| ZSTD_storeSeq(seqStorePtr, ip - anchor, anchor, offset + ZSTD_REP_MOVE, mLength - MINMATCH); |
| } |
| |
| /* match found */ |
| ip += mLength; |
| anchor = ip; |
| |
| if (ip <= ilimit) { |
| /* Fill Table */ |
| hashTable[ZSTD_hashPtr(base + curr + 2, hBits, mls)] = curr + 2; /* here because curr+2 could be > iend-8 */ |
| hashTable[ZSTD_hashPtr(ip - 2, hBits, mls)] = (U32)(ip - 2 - base); |
| /* check immediate repcode */ |
| while ((ip <= ilimit) && ((offset_2 > 0) & (ZSTD_read32(ip) == ZSTD_read32(ip - offset_2)))) { |
| /* store sequence */ |
| size_t const rLength = ZSTD_count(ip + 4, ip + 4 - offset_2, iend) + 4; |
| { |
| U32 const tmpOff = offset_2; |
| offset_2 = offset_1; |
| offset_1 = tmpOff; |
| } /* swap offset_2 <=> offset_1 */ |
| hashTable[ZSTD_hashPtr(ip, hBits, mls)] = (U32)(ip - base); |
| ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, rLength - MINMATCH); |
| ip += rLength; |
| anchor = ip; |
| continue; /* faster when present ... (?) */ |
| } |
| } |
| } |
| |
| /* save reps for next block */ |
| cctx->repToConfirm[0] = offset_1 ? offset_1 : offsetSaved; |
| cctx->repToConfirm[1] = offset_2 ? offset_2 : offsetSaved; |
| |
| /* Last Literals */ |
| { |
| size_t const lastLLSize = iend - anchor; |
| memcpy(seqStorePtr->lit, anchor, lastLLSize); |
| seqStorePtr->lit += lastLLSize; |
| } |
| } |
| |
| static void ZSTD_compressBlock_fast(ZSTD_CCtx *ctx, const void *src, size_t srcSize) |
| { |
| const U32 mls = ctx->params.cParams.searchLength; |
| switch (mls) { |
| default: /* includes case 3 */ |
| case 4: ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 4); return; |
| case 5: ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 5); return; |
| case 6: ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 6); return; |
| case 7: ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 7); return; |
| } |
| } |
| |
| static void ZSTD_compressBlock_fast_extDict_generic(ZSTD_CCtx *ctx, const void *src, size_t srcSize, const U32 mls) |
| { |
| U32 *hashTable = ctx->hashTable; |
| const U32 hBits = ctx->params.cParams.hashLog; |
| seqStore_t *seqStorePtr = &(ctx->seqStore); |
| const BYTE *const base = ctx->base; |
| const BYTE *const dictBase = ctx->dictBase; |
| const BYTE *const istart = (const BYTE *)src; |
| const BYTE *ip = istart; |
| const BYTE *anchor = istart; |
| const U32 lowestIndex = ctx->lowLimit; |
| const BYTE *const dictStart = dictBase + lowestIndex; |
| const U32 dictLimit = ctx->dictLimit; |
| const BYTE *const lowPrefixPtr = base + dictLimit; |
| const BYTE *const dictEnd = dictBase + dictLimit; |
| const BYTE *const iend = istart + srcSize; |
| const BYTE *const ilimit = iend - 8; |
| U32 offset_1 = ctx->rep[0], offset_2 = ctx->rep[1]; |
| |
| /* Search Loop */ |
| while (ip < ilimit) { /* < instead of <=, because (ip+1) */ |
| const size_t h = ZSTD_hashPtr(ip, hBits, mls); |
| const U32 matchIndex = hashTable[h]; |
| const BYTE *matchBase = matchIndex < dictLimit ? dictBase : base; |
| const BYTE *match = matchBase + matchIndex; |
| const U32 curr = (U32)(ip - base); |
| const U32 repIndex = curr + 1 - offset_1; /* offset_1 expected <= curr +1 */ |
| const BYTE *repBase = repIndex < dictLimit ? dictBase : base; |
| const BYTE *repMatch = repBase + repIndex; |
| size_t mLength; |
| hashTable[h] = curr; /* update hash table */ |
| |
| if ((((U32)((dictLimit - 1) - repIndex) >= 3) /* intentional underflow */ & (repIndex > lowestIndex)) && |
| (ZSTD_read32(repMatch) == ZSTD_read32(ip + 1))) { |
| const BYTE *repMatchEnd = repIndex < dictLimit ? dictEnd : iend; |
| mLength = ZSTD_count_2segments(ip + 1 + EQUAL_READ32, repMatch + EQUAL_READ32, iend, repMatchEnd, lowPrefixPtr) + EQUAL_READ32; |
| ip++; |
| ZSTD_storeSeq(seqStorePtr, ip - anchor, anchor, 0, mLength - MINMATCH); |
| } else { |
| if ((matchIndex < lowestIndex) || (ZSTD_read32(match) != ZSTD_read32(ip))) { |
| ip += ((ip - anchor) >> g_searchStrength) + 1; |
| continue; |
| } |
| { |
| const BYTE *matchEnd = matchIndex < dictLimit ? dictEnd : iend; |
| const BYTE *lowMatchPtr = matchIndex < dictLimit ? dictStart : lowPrefixPtr; |
| U32 offset; |
| mLength = ZSTD_count_2segments(ip + EQUAL_READ32, match + EQUAL_READ32, iend, matchEnd, lowPrefixPtr) + EQUAL_READ32; |
| while (((ip > anchor) & (match > lowMatchPtr)) && (ip[-1] == match[-1])) { |
| ip--; |
| match--; |
| mLength++; |
| } /* catch up */ |
| offset = curr - matchIndex; |
| offset_2 = offset_1; |
| offset_1 = offset; |
| ZSTD_storeSeq(seqStorePtr, ip - anchor, anchor, offset + ZSTD_REP_MOVE, mLength - MINMATCH); |
| } |
| } |
| |
| /* found a match : store it */ |
| ip += mLength; |
| anchor = ip; |
| |
| if (ip <= ilimit) { |
| /* Fill Table */ |
| hashTable[ZSTD_hashPtr(base + curr + 2, hBits, mls)] = curr + 2; |
| hashTable[ZSTD_hashPtr(ip - 2, hBits, mls)] = (U32)(ip - 2 - base); |
| /* check immediate repcode */ |
| while (ip <= ilimit) { |
| U32 const curr2 = (U32)(ip - base); |
| U32 const repIndex2 = curr2 - offset_2; |
| const BYTE *repMatch2 = repIndex2 < dictLimit ? dictBase + repIndex2 : base + repIndex2; |
| if ((((U32)((dictLimit - 1) - repIndex2) >= 3) & (repIndex2 > lowestIndex)) /* intentional overflow */ |
| && (ZSTD_read32(repMatch2) == ZSTD_read32(ip))) { |
| const BYTE *const repEnd2 = repIndex2 < dictLimit ? dictEnd : iend; |
| size_t repLength2 = |
| ZSTD_count_2segments(ip + EQUAL_READ32, repMatch2 + EQUAL_READ32, iend, repEnd2, lowPrefixPtr) + EQUAL_READ32; |
| U32 tmpOffset = offset_2; |
| offset_2 = offset_1; |
| offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */ |
| ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, repLength2 - MINMATCH); |
| hashTable[ZSTD_hashPtr(ip, hBits, mls)] = curr2; |
| ip += repLength2; |
| anchor = ip; |
| continue; |
| } |
| break; |
| } |
| } |
| } |
| |
| /* save reps for next block */ |
| ctx->repToConfirm[0] = offset_1; |
| ctx->repToConfirm[1] = offset_2; |
| |
| /* Last Literals */ |
| { |
| size_t const lastLLSize = iend - anchor; |
| memcpy(seqStorePtr->lit, anchor, lastLLSize); |
| seqStorePtr->lit += lastLLSize; |
| } |
| } |
| |
| static void ZSTD_compressBlock_fast_extDict(ZSTD_CCtx *ctx, const void *src, size_t srcSize) |
| { |
| U32 const mls = ctx->params.cParams.searchLength; |
| switch (mls) { |
| default: /* includes case 3 */ |
| case 4: ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 4); return; |
| case 5: ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 5); return; |
| case 6: ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 6); return; |
| case 7: ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 7); return; |
| } |
| } |
| |
| /*-************************************* |
| * Double Fast |
| ***************************************/ |
| static void ZSTD_fillDoubleHashTable(ZSTD_CCtx *cctx, const void *end, const U32 mls) |
| { |
| U32 *const hashLarge = cctx->hashTable; |
| U32 const hBitsL = cctx->params.cParams.hashLog; |
| U32 *const hashSmall = cctx->chainTable; |
| U32 const hBitsS = cctx->params.cParams.chainLog; |
| const BYTE *const base = cctx->base; |
| const BYTE *ip = base + cctx->nextToUpdate; |
| const BYTE *const iend = ((const BYTE *)end) - HASH_READ_SIZE; |
| const size_t fastHashFillStep = 3; |
| |
| while (ip <= iend) { |
| hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = (U32)(ip - base); |
| hashLarge[ZSTD_hashPtr(ip, hBitsL, 8)] = (U32)(ip - base); |
| ip += fastHashFillStep; |
| } |
| } |
| |
| FORCE_INLINE |
| void ZSTD_compressBlock_doubleFast_generic(ZSTD_CCtx *cctx, const void *src, size_t srcSize, const U32 mls) |
| { |
| U32 *const hashLong = cctx->hashTable; |
| const U32 hBitsL = cctx->params.cParams.hashLog; |
| U32 *const hashSmall = cctx->chainTable; |
| const U32 hBitsS = cctx->params.cParams.chainLog; |
| seqStore_t *seqStorePtr = &(cctx->seqStore); |
| const BYTE *const base = cctx->base; |
| const BYTE *const istart = (const BYTE *)src; |
| const BYTE *ip = istart; |
| const BYTE *anchor = istart; |
| const U32 lowestIndex = cctx->dictLimit; |
| const BYTE *const lowest = base + lowestIndex; |
| const BYTE *const iend = istart + srcSize; |
| const BYTE *const ilimit = iend - HASH_READ_SIZE; |
| U32 offset_1 = cctx->rep[0], offset_2 = cctx->rep[1]; |
| U32 offsetSaved = 0; |
| |
| /* init */ |
| ip += (ip == lowest); |
| { |
| U32 const maxRep = (U32)(ip - lowest); |
| if (offset_2 > maxRep) |
| offsetSaved = offset_2, offset_2 = 0; |
| if (offset_1 > maxRep) |
| offsetSaved = offset_1, offset_1 = 0; |
| } |
| |
| /* Main Search Loop */ |
| while (ip < ilimit) { /* < instead of <=, because repcode check at (ip+1) */ |
| size_t mLength; |
| size_t const h2 = ZSTD_hashPtr(ip, hBitsL, 8); |
| size_t const h = ZSTD_hashPtr(ip, hBitsS, mls); |
| U32 const curr = (U32)(ip - base); |
| U32 const matchIndexL = hashLong[h2]; |
| U32 const matchIndexS = hashSmall[h]; |
| const BYTE *matchLong = base + matchIndexL; |
| const BYTE *match = base + matchIndexS; |
| hashLong[h2] = hashSmall[h] = curr; /* update hash tables */ |
| |
| if ((offset_1 > 0) & (ZSTD_read32(ip + 1 - offset_1) == ZSTD_read32(ip + 1))) { /* note : by construction, offset_1 <= curr */ |
| mLength = ZSTD_count(ip + 1 + 4, ip + 1 + 4 - offset_1, iend) + 4; |
| ip++; |
| ZSTD_storeSeq(seqStorePtr, ip - anchor, anchor, 0, mLength - MINMATCH); |
| } else { |
| U32 offset; |
| if ((matchIndexL > lowestIndex) && (ZSTD_read64(matchLong) == ZSTD_read64(ip))) { |
| mLength = ZSTD_count(ip + 8, matchLong + 8, iend) + 8; |
| offset = (U32)(ip - matchLong); |
| while (((ip > anchor) & (matchLong > lowest)) && (ip[-1] == matchLong[-1])) { |
| ip--; |
| matchLong--; |
| mLength++; |
| } /* catch up */ |
| } else if ((matchIndexS > lowestIndex) && (ZSTD_read32(match) == ZSTD_read32(ip))) { |
| size_t const h3 = ZSTD_hashPtr(ip + 1, hBitsL, 8); |
| U32 const matchIndex3 = hashLong[h3]; |
| const BYTE *match3 = base + matchIndex3; |
| hashLong[h3] = curr + 1; |
| if ((matchIndex3 > lowestIndex) && (ZSTD_read64(match3) == ZSTD_read64(ip + 1))) { |
| mLength = ZSTD_count(ip + 9, match3 + 8, iend) + 8; |
| ip++; |
| offset = (U32)(ip - match3); |
| while (((ip > anchor) & (match3 > lowest)) && (ip[-1] == match3[-1])) { |
| ip--; |
| match3--; |
| mLength++; |
| } /* catch up */ |
| } else { |
| mLength = ZSTD_count(ip + 4, match + 4, iend) + 4; |
| offset = (U32)(ip - match); |
| while (((ip > anchor) & (match > lowest)) && (ip[-1] == match[-1])) { |
| ip--; |
| match--; |
| mLength++; |
| } /* catch up */ |
| } |
| } else { |
| ip += ((ip - anchor) >> g_searchStrength) + 1; |
| continue; |
| } |
| |
| offset_2 = offset_1; |
| offset_1 = offset; |
| |
| ZSTD_storeSeq(seqStorePtr, ip - anchor, anchor, offset + ZSTD_REP_MOVE, mLength - MINMATCH); |
| } |
| |
| /* match found */ |
| ip += mLength; |
| anchor = ip; |
| |
| if (ip <= ilimit) { |
| /* Fill Table */ |
| hashLong[ZSTD_hashPtr(base + curr + 2, hBitsL, 8)] = hashSmall[ZSTD_hashPtr(base + curr + 2, hBitsS, mls)] = |
| curr + 2; /* here because curr+2 could be > iend-8 */ |
| hashLong[ZSTD_hashPtr(ip - 2, hBitsL, 8)] = hashSmall[ZSTD_hashPtr(ip - 2, hBitsS, mls)] = (U32)(ip - 2 - base); |
| |
| /* check immediate repcode */ |
| while ((ip <= ilimit) && ((offset_2 > 0) & (ZSTD_read32(ip) == ZSTD_read32(ip - offset_2)))) { |
| /* store sequence */ |
| size_t const rLength = ZSTD_count(ip + 4, ip + 4 - offset_2, iend) + 4; |
| { |
| U32 const tmpOff = offset_2; |
| offset_2 = offset_1; |
| offset_1 = tmpOff; |
| } /* swap offset_2 <=> offset_1 */ |
| hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = (U32)(ip - base); |
| hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = (U32)(ip - base); |
| ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, rLength - MINMATCH); |
| ip += rLength; |
| anchor = ip; |
| continue; /* faster when present ... (?) */ |
| } |
| } |
| } |
| |
| /* save reps for next block */ |
| cctx->repToConfirm[0] = offset_1 ? offset_1 : offsetSaved; |
| cctx->repToConfirm[1] = offset_2 ? offset_2 : offsetSaved; |
| |
| /* Last Literals */ |
| { |
| size_t const lastLLSize = iend - anchor; |
| memcpy(seqStorePtr->lit, anchor, lastLLSize); |
| seqStorePtr->lit += lastLLSize; |
| } |
| } |
| |
| static void ZSTD_compressBlock_doubleFast(ZSTD_CCtx *ctx, const void *src, size_t srcSize) |
| { |
| const U32 mls = ctx->params.cParams.searchLength; |
| switch (mls) { |
| default: /* includes case 3 */ |
| case 4: ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 4); return; |
| case 5: ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 5); return; |
| case 6: ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 6); return; |
| case 7: ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 7); return; |
| } |
| } |
| |
| static void ZSTD_compressBlock_doubleFast_extDict_generic(ZSTD_CCtx *ctx, const void *src, size_t srcSize, const U32 mls) |
| { |
| U32 *const hashLong = ctx->hashTable; |
| U32 const hBitsL = ctx->params.cParams.hashLog; |
| U32 *const hashSmall = ctx->chainTable; |
| U32 const hBitsS = ctx->params.cParams.chainLog; |
| seqStore_t *seqStorePtr = &(ctx->seqStore); |
| const BYTE *const base = ctx->base; |
| const BYTE *const dictBase = ctx->dictBase; |
| const BYTE *const istart = (const BYTE *)src; |
| const BYTE *ip = istart; |
| const BYTE *anchor = istart; |
| const U32 lowestIndex = ctx->lowLimit; |
| const BYTE *const dictStart = dictBase + lowestIndex; |
| const U32 dictLimit = ctx->dictLimit; |
| const BYTE *const lowPrefixPtr = base + dictLimit; |
| const BYTE *const dictEnd = dictBase + dictLimit; |
| const BYTE *const iend = istart + srcSize; |
| const BYTE *const ilimit = iend - 8; |
| U32 offset_1 = ctx->rep[0], offset_2 = ctx->rep[1]; |
| |
| /* Search Loop */ |
| while (ip < ilimit) { /* < instead of <=, because (ip+1) */ |
| const size_t hSmall = ZSTD_hashPtr(ip, hBitsS, mls); |
| const U32 matchIndex = hashSmall[hSmall]; |
| const BYTE *matchBase = matchIndex < dictLimit ? dictBase : base; |
| const BYTE *match = matchBase + matchIndex; |
| |
| const size_t hLong = ZSTD_hashPtr(ip, hBitsL, 8); |
| const U32 matchLongIndex = hashLong[hLong]; |
| const BYTE *matchLongBase = matchLongIndex < dictLimit ? dictBase : base; |
| const BYTE *matchLong = matchLongBase + matchLongIndex; |
| |
| const U32 curr = (U32)(ip - base); |
| const U32 repIndex = curr + 1 - offset_1; /* offset_1 expected <= curr +1 */ |
| const BYTE *repBase = repIndex < dictLimit ? dictBase : base; |
| const BYTE *repMatch = repBase + repIndex; |
| size_t mLength; |
| hashSmall[hSmall] = hashLong[hLong] = curr; /* update hash table */ |
| |
| if ((((U32)((dictLimit - 1) - repIndex) >= 3) /* intentional underflow */ & (repIndex > lowestIndex)) && |
| (ZSTD_read32(repMatch) == ZSTD_read32(ip + 1))) { |
| const BYTE *repMatchEnd = repIndex < dictLimit ? dictEnd : iend; |
| mLength = ZSTD_count_2segments(ip + 1 + 4, repMatch + 4, iend, repMatchEnd, lowPrefixPtr) + 4; |
| ip++; |
| ZSTD_storeSeq(seqStorePtr, ip - anchor, anchor, 0, mLength - MINMATCH); |
| } else { |
| if ((matchLongIndex > lowestIndex) && (ZSTD_read64(matchLong) == ZSTD_read64(ip))) { |
| const BYTE *matchEnd = matchLongIndex < dictLimit ? dictEnd : iend; |
| const BYTE *lowMatchPtr = matchLongIndex < dictLimit ? dictStart : lowPrefixPtr; |
| U32 offset; |
| mLength = ZSTD_count_2segments(ip + 8, matchLong + 8, iend, matchEnd, lowPrefixPtr) + 8; |
| offset = curr - matchLongIndex; |
| while (((ip > anchor) & (matchLong > lowMatchPtr)) && (ip[-1] == matchLong[-1])) { |
| ip--; |
| matchLong--; |
| mLength++; |
| } /* catch up */ |
| offset_2 = offset_1; |
| offset_1 = offset; |
| ZSTD_storeSeq(seqStorePtr, ip - anchor, anchor, offset + ZSTD_REP_MOVE, mLength - MINMATCH); |
| |
| } else if ((matchIndex > lowestIndex) && (ZSTD_read32(match) == ZSTD_read32(ip))) { |
| size_t const h3 = ZSTD_hashPtr(ip + 1, hBitsL, 8); |
| U32 const matchIndex3 = hashLong[h3]; |
| const BYTE *const match3Base = matchIndex3 < dictLimit ? dictBase : base; |
| const BYTE *match3 = match3Base + matchIndex3; |
| U32 offset; |
| hashLong[h3] = curr + 1; |
| if ((matchIndex3 > lowestIndex) && (ZSTD_read64(match3) == ZSTD_read64(ip + 1))) { |
| const BYTE *matchEnd = matchIndex3 < dictLimit ? dictEnd : iend; |
| const BYTE *lowMatchPtr = matchIndex3 < dictLimit ? dictStart : lowPrefixPtr; |
| mLength = ZSTD_count_2segments(ip + 9, match3 + 8, iend, matchEnd, lowPrefixPtr) + 8; |
| ip++; |
| offset = curr + 1 - matchIndex3; |
| while (((ip > anchor) & (match3 > lowMatchPtr)) && (ip[-1] == match3[-1])) { |
| ip--; |
| match3--; |
| mLength++; |
| } /* catch up */ |
| } else { |
| const BYTE *matchEnd = matchIndex < dictLimit ? dictEnd : iend; |
| const BYTE *lowMatchPtr = matchIndex < dictLimit ? dictStart : lowPrefixPtr; |
| mLength = ZSTD_count_2segments(ip + 4, match + 4, iend, matchEnd, lowPrefixPtr) + 4; |
| offset = curr - matchIndex; |
| while (((ip > anchor) & (match > lowMatchPtr)) && (ip[-1] == match[-1])) { |
| ip--; |
| match--; |
| mLength++; |
| } /* catch up */ |
| } |
| offset_2 = offset_1; |
| offset_1 = offset; |
| ZSTD_storeSeq(seqStorePtr, ip - anchor, anchor, offset + ZSTD_REP_MOVE, mLength - MINMATCH); |
| |
| } else { |
| ip += ((ip - anchor) >> g_searchStrength) + 1; |
| continue; |
| } |
| } |
| |
| /* found a match : store it */ |
| ip += mLength; |
| anchor = ip; |
| |
| if (ip <= ilimit) { |
| /* Fill Table */ |
| hashSmall[ZSTD_hashPtr(base + curr + 2, hBitsS, mls)] = curr + 2; |
| hashLong[ZSTD_hashPtr(base + curr + 2, hBitsL, 8)] = curr + 2; |
| hashSmall[ZSTD_hashPtr(ip - 2, hBitsS, mls)] = (U32)(ip - 2 - base); |
| hashLong[ZSTD_hashPtr(ip - 2, hBitsL, 8)] = (U32)(ip - 2 - base); |
| /* check immediate repcode */ |
| while (ip <= ilimit) { |
| U32 const curr2 = (U32)(ip - base); |
| U32 const repIndex2 = curr2 - offset_2; |
| const BYTE *repMatch2 = repIndex2 < dictLimit ? dictBase + repIndex2 : base + repIndex2; |
| if ((((U32)((dictLimit - 1) - repIndex2) >= 3) & (repIndex2 > lowestIndex)) /* intentional overflow */ |
| && (ZSTD_read32(repMatch2) == ZSTD_read32(ip))) { |
| const BYTE *const repEnd2 = repIndex2 < dictLimit ? dictEnd : iend; |
| size_t const repLength2 = |
| ZSTD_count_2segments(ip + EQUAL_READ32, repMatch2 + EQUAL_READ32, iend, repEnd2, lowPrefixPtr) + EQUAL_READ32; |
| U32 tmpOffset = offset_2; |
| offset_2 = offset_1; |
| offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */ |
| ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, repLength2 - MINMATCH); |
| hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = curr2; |
| hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = curr2; |
| ip += repLength2; |
| anchor = ip; |
| continue; |
| } |
| break; |
| } |
| } |
| } |
| |
| /* save reps for next block */ |
| ctx->repToConfirm[0] = offset_1; |
| ctx->repToConfirm[1] = offset_2; |
| |
| /* Last Literals */ |
| { |
| size_t const lastLLSize = iend - anchor; |
| memcpy(seqStorePtr->lit, anchor, lastLLSize); |
| seqStorePtr->lit += lastLLSize; |
| } |
| } |
| |
| static void ZSTD_compressBlock_doubleFast_extDict(ZSTD_CCtx *ctx, const void *src, size_t srcSize) |
| { |
| U32 const mls = ctx->params.cParams.searchLength; |
| switch (mls) { |
| default: /* includes case 3 */ |
| case 4: ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 4); return; |
| case 5: ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 5); return; |
| case 6: ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 6); return; |
| case 7: ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 7); return; |
| } |
| } |
| |
| /*-************************************* |
| * Binary Tree search |
| ***************************************/ |
| /** ZSTD_insertBt1() : add one or multiple positions to tree. |
| * ip : assumed <= iend-8 . |
| * @return : nb of positions added */ |
| static U32 ZSTD_insertBt1(ZSTD_CCtx *zc, const BYTE *const ip, const U32 mls, const BYTE *const iend, U32 nbCompares, U32 extDict) |
| { |
| U32 *const hashTable = zc->hashTable; |
| U32 const hashLog = zc->params.cParams.hashLog; |
| size_t const h = ZSTD_hashPtr(ip, hashLog, mls); |
| U32 *const bt = zc->chainTable; |
| U32 const btLog = zc->params.cParams.chainLog - 1; |
| U32 const btMask = (1 << btLog) - 1; |
| U32 matchIndex = hashTable[h]; |
| size_t commonLengthSmaller = 0, commonLengthLarger = 0; |
| const BYTE *const base = zc->base; |
| const BYTE *const dictBase = zc->dictBase; |
| const U32 dictLimit = zc->dictLimit; |
| const BYTE *const dictEnd = dictBase + dictLimit; |
| const BYTE *const prefixStart = base + dictLimit; |
| const BYTE *match; |
| const U32 curr = (U32)(ip - base); |
| const U32 btLow = btMask >= curr ? 0 : curr - btMask; |
| U32 *smallerPtr = bt + 2 * (curr & btMask); |
| U32 *largerPtr = smallerPtr + 1; |
| U32 dummy32; /* to be nullified at the end */ |
| U32 const windowLow = zc->lowLimit; |
| U32 matchEndIdx = curr + 8; |
| size_t bestLength = 8; |
| |
| hashTable[h] = curr; /* Update Hash Table */ |
| |
| while (nbCompares-- && (matchIndex > windowLow)) { |
| U32 *const nextPtr = bt + 2 * (matchIndex & btMask); |
| size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */ |
| |
| if ((!extDict) || (matchIndex + matchLength >= dictLimit)) { |
| match = base + matchIndex; |
| if (match[matchLength] == ip[matchLength]) |
| matchLength += ZSTD_count(ip + matchLength + 1, match + matchLength + 1, iend) + 1; |
| } else { |
| match = dictBase + matchIndex; |
| matchLength += ZSTD_count_2segments(ip + matchLength, match + matchLength, iend, dictEnd, prefixStart); |
| if (matchIndex + matchLength >= dictLimit) |
| match = base + matchIndex; /* to prepare for next usage of match[matchLength] */ |
| } |
| |
| if (matchLength > bestLength) { |
| bestLength = matchLength; |
| if (matchLength > matchEndIdx - matchIndex) |
| matchEndIdx = matchIndex + (U32)matchLength; |
| } |
| |
| if (ip + matchLength == iend) /* equal : no way to know if inf or sup */ |
| break; /* drop , to guarantee consistency ; miss a bit of compression, but other solutions can corrupt the tree */ |
| |
| if (match[matchLength] < ip[matchLength]) { /* necessarily within correct buffer */ |
| /* match is smaller than curr */ |
| *smallerPtr = matchIndex; /* update smaller idx */ |
| commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */ |
| if (matchIndex <= btLow) { |
| smallerPtr = &dummy32; |
| break; |
| } /* beyond tree size, stop the search */ |
| smallerPtr = nextPtr + 1; /* new "smaller" => larger of match */ |
| matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to curr) */ |
| } else { |
| /* match is larger than curr */ |
| *largerPtr = matchIndex; |
| commonLengthLarger = matchLength; |
| if (matchIndex <= btLow) { |
| largerPtr = &dummy32; |
| break; |
| } /* beyond tree size, stop the search */ |
| largerPtr = nextPtr; |
| matchIndex = nextPtr[0]; |
| } |
| } |
| |
| *smallerPtr = *largerPtr = 0; |
| if (bestLength > 384) |
| return MIN(192, (U32)(bestLength - 384)); /* speed optimization */ |
| if (matchEndIdx > curr + 8) |
| return matchEndIdx - curr - 8; |
| return 1; |
| } |
| |
| static size_t ZSTD_insertBtAndFindBestMatch(ZSTD_CCtx *zc, const BYTE *const ip, const BYTE *const iend, size_t *offsetPtr, U32 nbCompares, const U32 mls, |
| U32 extDict) |
| { |
| U32 *const hashTable = zc->hashTable; |
| U32 const hashLog = zc->params.cParams.hashLog; |
| size_t const h = ZSTD_hashPtr(ip, hashLog, mls); |
| U32 *const bt = zc->chainTable; |
| U32 const btLog = zc->params.cParams.chainLog - 1; |
| U32 const btMask = (1 << btLog) - 1; |
| U32 matchIndex = hashTable[h]; |
| size_t commonLengthSmaller = 0, commonLengthLarger = 0; |
| const BYTE *const base = zc->base; |
| const BYTE *const dictBase = zc->dictBase; |
| const U32 dictLimit = zc->dictLimit; |
| const BYTE *const dictEnd = dictBase + dictLimit; |
| const BYTE *const prefixStart = base + dictLimit; |
| const U32 curr = (U32)(ip - base); |
| const U32 btLow = btMask >= curr ? 0 : curr - btMask; |
| const U32 windowLow = zc->lowLimit; |
| U32 *smallerPtr = bt + 2 * (curr & btMask); |
| U32 *largerPtr = bt + 2 * (curr & btMask) + 1; |
| U32 matchEndIdx = curr + 8; |
| U32 dummy32; /* to be nullified at the end */ |
| size_t bestLength = 0; |
| |
| hashTable[h] = curr; /* Update Hash Table */ |
| |
| while (nbCompares-- && (matchIndex > windowLow)) { |
| U32 *const nextPtr = bt + 2 * (matchIndex & btMask); |
| size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */ |
| const BYTE *match; |
| |
| if ((!extDict) || (matchIndex + matchLength >= dictLimit)) { |
| match = base + matchIndex; |
| if (match[matchLength] == ip[matchLength]) |
| matchLength += ZSTD_count(ip + matchLength + 1, match + matchLength + 1, iend) + 1; |
| } else { |
| match = dictBase + matchIndex; |
| matchLength += ZSTD_count_2segments(ip + matchLength, match + matchLength, iend, dictEnd, prefixStart); |
| if (matchIndex + matchLength >= dictLimit) |
| match = base + matchIndex; /* to prepare for next usage of match[matchLength] */ |
| } |
| |
| if (matchLength > bestLength) { |
| if (matchLength > matchEndIdx - matchIndex) |
| matchEndIdx = matchIndex + (U32)matchLength; |
| if ((4 * (int)(matchLength - bestLength)) > (int)(ZSTD_highbit32(curr - matchIndex + 1) - ZSTD_highbit32((U32)offsetPtr[0] + 1))) |
| bestLength = matchLength, *offsetPtr = ZSTD_REP_MOVE + curr - matchIndex; |
| if (ip + matchLength == iend) /* equal : no way to know if inf or sup */ |
| break; /* drop, to guarantee consistency (miss a little bit of compression) */ |
| } |
| |
| if (match[matchLength] < ip[matchLength]) { |
| /* match is smaller than curr */ |
| *smallerPtr = matchIndex; /* update smaller idx */ |
| commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */ |
| if (matchIndex <= btLow) { |
| smallerPtr = &dummy32; |
| break; |
| } /* beyond tree size, stop the search */ |
| smallerPtr = nextPtr + 1; /* new "smaller" => larger of match */ |
| matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to curr) */ |
| } else { |
| /* match is larger than curr */ |
| *largerPtr = matchIndex; |
| commonLengthLarger = matchLength; |
| if (matchIndex <= btLow) { |
| largerPtr = &dummy32; |
| break; |
| } /* beyond tree size, stop the search */ |
| largerPtr = nextPtr; |
| matchIndex = nextPtr[0]; |
| } |
| } |
| |
| *smallerPtr = *largerPtr = 0; |
| |
| zc->nextToUpdate = (matchEndIdx > curr + 8) ? matchEndIdx - 8 : curr + 1; |
| return bestLength; |
| } |
| |
| static void ZSTD_updateTree(ZSTD_CCtx *zc, const BYTE *const ip, const BYTE *const iend, const U32 nbCompares, const U32 mls) |
| { |
| const BYTE *const base = zc->base; |
| const U32 target = (U32)(ip - base); |
| U32 idx = zc->nextToUpdate; |
| |
| while (idx < target) |
| idx += ZSTD_insertBt1(zc, base + idx, mls, iend, nbCompares, 0); |
| } |
| |
| /** ZSTD_BtFindBestMatch() : Tree updater, providing best match */ |
| static size_t ZSTD_BtFindBestMatch(ZSTD_CCtx *zc, const BYTE *const ip, const BYTE *const iLimit, size_t *offsetPtr, const U32 maxNbAttempts, const U32 mls) |
| { |
| if (ip < zc->base + zc->nextToUpdate) |
| return 0; /* skipped area */ |
| ZSTD_updateTree(zc, ip, iLimit, maxNbAttempts, mls); |
| return ZSTD_insertBtAndFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, mls, 0); |
| } |
| |
| static size_t ZSTD_BtFindBestMatch_selectMLS(ZSTD_CCtx *zc, /* Index table will be updated */ |
| const BYTE *ip, const BYTE *const iLimit, size_t *offsetPtr, const U32 maxNbAttempts, const U32 matchLengthSearch) |
| { |
| switch (matchLengthSearch) { |
| default: /* includes case 3 */ |
| case 4: return ZSTD_BtFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4); |
| case 5: return ZSTD_BtFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5); |
| case 7: |
| case 6: return ZSTD_BtFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6); |
| } |
| } |
| |
| static void ZSTD_updateTree_extDict(ZSTD_CCtx *zc, const BYTE *const ip, const BYTE *const iend, const U32 nbCompares, const U32 mls) |
| { |
| const BYTE *const base = zc->base; |
| const U32 target = (U32)(ip - base); |
| U32 idx = zc->nextToUpdate; |
| |
| while (idx < target) |
| idx += ZSTD_insertBt1(zc, base + idx, mls, iend, nbCompares, 1); |
| } |
| |
| /** Tree updater, providing best match */ |
| static size_t ZSTD_BtFindBestMatch_extDict(ZSTD_CCtx *zc, const BYTE *const ip, const BYTE *const iLimit, size_t *offsetPtr, const U32 maxNbAttempts, |
| const U32 mls) |
| { |
| if (ip < zc->base + zc->nextToUpdate) |
| return 0; /* skipped area */ |
| ZSTD_updateTree_extDict(zc, ip, iLimit, maxNbAttempts, mls); |
| return ZSTD_insertBtAndFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, mls, 1); |
| } |
| |
| static size_t ZSTD_BtFindBestMatch_selectMLS_extDict(ZSTD_CCtx *zc, /* Index table will be updated */ |
| const BYTE *ip, const BYTE *const iLimit, size_t *offsetPtr, const U32 maxNbAttempts, |
| const U32 matchLengthSearch) |
| { |
| switch (matchLengthSearch) { |
| default: /* includes case 3 */ |
| case 4: return ZSTD_BtFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4); |
| case 5: return ZSTD_BtFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5); |
| case 7: |
| case 6: return ZSTD_BtFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6); |
| } |
| } |
| |
| /* ********************************* |
| * Hash Chain |
| ***********************************/ |
| #define NEXT_IN_CHAIN(d, mask) chainTable[(d)&mask] |
| |
| /* Update chains up to ip (excluded) |
| Assumption : always within prefix (i.e. not within extDict) */ |
| FORCE_INLINE |
| U32 ZSTD_insertAndFindFirstIndex(ZSTD_CCtx *zc, const BYTE *ip, U32 mls) |
| { |
| U32 *const hashTable = zc->hashTable; |
| const U32 hashLog = zc->params.cParams.hashLog; |
| U32 *const chainTable = zc->chainTable; |
| const U32 chainMask = (1 << zc->params.cParams.chainLog) - 1; |
| const BYTE *const base = zc->base; |
| const U32 target = (U32)(ip - base); |
| U32 idx = zc->nextToUpdate; |
| |
| while (idx < target) { /* catch up */ |
| size_t const h = ZSTD_hashPtr(base + idx, hashLog, mls); |
| NEXT_IN_CHAIN(idx, chainMask) = hashTable[h]; |
| hashTable[h] = idx; |
| idx++; |
| } |
| |
| zc->nextToUpdate = target; |
| return hashTable[ZSTD_hashPtr(ip, hashLog, mls)]; |
| } |
| |
| /* inlining is important to hardwire a hot branch (template emulation) */ |
| FORCE_INLINE |
| size_t ZSTD_HcFindBestMatch_generic(ZSTD_CCtx *zc, /* Index table will be updated */ |
| const BYTE *const ip, const BYTE *const iLimit, size_t *offsetPtr, const U32 maxNbAttempts, const U32 mls, |
| const U32 extDict) |
| { |
| U32 *const chainTable = zc->chainTable; |
| const U32 chainSize = (1 << zc->params.cParams.chainLog); |
| const U32 chainMask = chainSize - 1; |
| const BYTE *const base = zc->base; |
| const BYTE *const dictBase = zc->dictBase; |
| const U32 dictLimit = zc->dictLimit; |
| const BYTE *const prefixStart = base + dictLimit; |
| const BYTE *const dictEnd = dictBase + dictLimit; |
| const U32 lowLimit = zc->lowLimit; |
| const U32 curr = (U32)(ip - base); |
| const U32 minChain = curr > chainSize ? curr - chainSize : 0; |
| int nbAttempts = maxNbAttempts; |
| size_t ml = EQUAL_READ32 - 1; |
| |
| /* HC4 match finder */ |
| U32 matchIndex = ZSTD_insertAndFindFirstIndex(zc, ip, mls); |
| |
| for (; (matchIndex > lowLimit) & (nbAttempts > 0); nbAttempts--) { |
| const BYTE *match; |
| size_t currMl = 0; |
| if ((!extDict) || matchIndex >= dictLimit) { |
| match = base + matchIndex; |
| if (match[ml] == ip[ml]) /* potentially better */ |
| currMl = ZSTD_count(ip, match, iLimit); |
| } else { |
| match = dictBase + matchIndex; |
| if (ZSTD_read32(match) == ZSTD_read32(ip)) /* assumption : matchIndex <= dictLimit-4 (by table construction) */ |
| currMl = ZSTD_count_2segments(ip + EQUAL_READ32, match + EQUAL_READ32, iLimit, dictEnd, prefixStart) + EQUAL_READ32; |
| } |
| |
| /* save best solution */ |
| if (currMl > ml) { |
| ml = currMl; |
| *offsetPtr = curr - matchIndex + ZSTD_REP_MOVE; |
| if (ip + currMl == iLimit) |
| break; /* best possible, and avoid read overflow*/ |
| } |
| |
| if (matchIndex <= minChain) |
| break; |
| matchIndex = NEXT_IN_CHAIN(matchIndex, chainMask); |
| } |
| |
| return ml; |
| } |
| |
| FORCE_INLINE size_t ZSTD_HcFindBestMatch_selectMLS(ZSTD_CCtx *zc, const BYTE *ip, const BYTE *const iLimit, size_t *offsetPtr, const U32 maxNbAttempts, |
| const U32 matchLengthSearch) |
| { |
| switch (matchLengthSearch) { |
| default: /* includes case 3 */ |
| case 4: return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4, 0); |
| case 5: return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5, 0); |
| case 7: |
| case 6: return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6, 0); |
| } |
| } |
| |
| FORCE_INLINE size_t ZSTD_HcFindBestMatch_extDict_selectMLS(ZSTD_CCtx *zc, const BYTE *ip, const BYTE *const iLimit, size_t *offsetPtr, const U32 maxNbAttempts, |
| const U32 matchLengthSearch) |
| { |
| switch (matchLengthSearch) { |
| default: /* includes case 3 */ |
| case 4: return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4, 1); |
| case 5: return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5, 1); |
| case 7: |
| case 6: return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6, 1); |
| } |
| } |
| |
| /* ******************************* |
| * Common parser - lazy strategy |
| *********************************/ |
| FORCE_INLINE |
| void ZSTD_compressBlock_lazy_generic(ZSTD_CCtx *ctx, const void *src, size_t srcSize, const U32 searchMethod, const U32 depth) |
| { |
| seqStore_t *seqStorePtr = &(ctx->seqStore); |
| const BYTE *const istart = (const BYTE *)src; |
| const BYTE *ip = istart; |
| const BYTE *anchor = istart; |
| const BYTE *const iend = istart + srcSize; |
| const BYTE *const ilimit = iend - 8; |
| const BYTE *const base = ctx->base + ctx->dictLimit; |
| |
| U32 const maxSearches = 1 << ctx->params.cParams.searchLog; |
| U32 const mls = ctx->params.cParams.searchLength; |
| |
| typedef size_t (*searchMax_f)(ZSTD_CCtx * zc, const BYTE *ip, const BYTE *iLimit, size_t *offsetPtr, U32 maxNbAttempts, U32 matchLengthSearch); |
| searchMax_f const searchMax = searchMethod ? ZSTD_BtFindBestMatch_selectMLS : ZSTD_HcFindBestMatch_selectMLS; |
| U32 offset_1 = ctx->rep[0], offset_2 = ctx->rep[1], savedOffset = 0; |
| |
| /* init */ |
| ip += (ip == base); |
| ctx->nextToUpdate3 = ctx->nextToUpdate; |
| { |
| U32 const maxRep = (U32)(ip - base); |
| if (offset_2 > maxRep) |
| savedOffset = offset_2, offset_2 = 0; |
| if (offset_1 > maxRep) |
| savedOffset = offset_1, offset_1 = 0; |
| } |
| |
| /* Match Loop */ |
| while (ip < ilimit) { |
| size_t matchLength = 0; |
| size_t offset = 0; |
| const BYTE *start = ip + 1; |
| |
| /* check repCode */ |
| if ((offset_1 > 0) & (ZSTD_read32(ip + 1) == ZSTD_read32(ip + 1 - offset_1))) { |
| /* repcode : we take it */ |
| matchLength = ZSTD_count(ip + 1 + EQUAL_READ32, ip + 1 + EQUAL_READ32 - offset_1, iend) + EQUAL_READ32; |
| if (depth == 0) |
| goto _storeSequence; |
| } |
| |
| /* first search (depth 0) */ |
| { |
| size_t offsetFound = 99999999; |
| size_t const ml2 = searchMax(ctx, ip, iend, &offsetFound, maxSearches, mls); |
| if (ml2 > matchLength) |
| matchLength = ml2, start = ip, offset = offsetFound; |
| } |
| |
| if (matchLength < EQUAL_READ32) { |
| ip += ((ip - anchor) >> g_searchStrength) + 1; /* jump faster over incompressible sections */ |
| continue; |
| } |
| |
| /* let's try to find a better solution */ |
| if (depth >= 1) |
| while (ip < ilimit) { |
| ip++; |
| if ((offset) && ((offset_1 > 0) & (ZSTD_read32(ip) == ZSTD_read32(ip - offset_1)))) { |
| size_t const mlRep = ZSTD_count(ip + EQUAL_READ32, ip + EQUAL_READ32 - offset_1, iend) + EQUAL_READ32; |
| int const gain2 = (int)(mlRep * 3); |
| int const gain1 = (int)(matchLength * 3 - ZSTD_highbit32((U32)offset + 1) + 1); |
| if ((mlRep >= EQUAL_READ32) && (gain2 > gain1)) |
| matchLength = mlRep, offset = 0, start = ip; |
| } |
| { |
| size_t offset2 = 99999999; |
| size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls); |
| int const gain2 = (int)(ml2 * 4 - ZSTD_highbit32((U32)offset2 + 1)); /* raw approx */ |
| int const gain1 = (int)(matchLength * 4 - ZSTD_highbit32((U32)offset + 1) + 4); |
| if ((ml2 >= EQUAL_READ32) && (gain2 > gain1)) { |
| matchLength = ml2, offset = offset2, start = ip; |
| continue; /* search a better one */ |
| } |
| } |
| |
| /* let's find an even better one */ |
| if ((depth == 2) && (ip < ilimit)) { |
| ip++; |
| if ((offset) && ((offset_1 > 0) & (ZSTD_read32(ip) == ZSTD_read32(ip - offset_1)))) { |
| size_t const ml2 = ZSTD_count(ip + EQUAL_READ32, ip + EQUAL_READ32 - offset_1, iend) + EQUAL_READ32; |
| int const gain2 = (int)(ml2 * 4); |
| int const gain1 = (int)(matchLength * 4 - ZSTD_highbit32((U32)offset + 1) + 1); |
| if ((ml2 >= EQUAL_READ32) && (gain2 > gain1)) |
| matchLength = ml2, offset = 0, start = ip; |
| } |
| { |
| size_t offset2 = 99999999; |
| size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls); |
| int const gain2 = (int)(ml2 * 4 - ZSTD_highbit32((U32)offset2 + 1)); /* raw approx */ |
| int const gain1 = (int)(matchLength * 4 - ZSTD_highbit32((U32)offset + 1) + 7); |
| if ((ml2 >= EQUAL_READ32) && (gain2 > gain1)) { |
| matchLength = ml2, offset = offset2, start = ip; |
| continue; |
| } |
| } |
| } |
| break; /* nothing found : store previous solution */ |
| } |
| |
| /* NOTE: |
| * start[-offset+ZSTD_REP_MOVE-1] is undefined behavior. |
| * (-offset+ZSTD_REP_MOVE-1) is unsigned, and is added to start, which |
| * overflows the pointer, which is undefined behavior. |
| */ |
| /* catch up */ |
| if (offset) { |
| while ((start > anchor) && (start > base + offset - ZSTD_REP_MOVE) && |
| (start[-1] == (start-offset+ZSTD_REP_MOVE)[-1])) /* only search for offset within prefix */ |
| { |
| start--; |
| matchLength++; |
| } |
| offset_2 = offset_1; |
| offset_1 = (U32)(offset - ZSTD_REP_MOVE); |
| } |
| |
| /* store sequence */ |
| _storeSequence: |
| { |
| size_t const litLength = start - anchor; |
| ZSTD_storeSeq(seqStorePtr, litLength, anchor, (U32)offset, matchLength - MINMATCH); |
| anchor = ip = start + matchLength; |
| } |
| |
| /* check immediate repcode */ |
| while ((ip <= ilimit) && ((offset_2 > 0) & (ZSTD_read32(ip) == ZSTD_read32(ip - offset_2)))) { |
| /* store sequence */ |
| matchLength = ZSTD_count(ip + EQUAL_READ32, ip + EQUAL_READ32 - offset_2, iend) + EQUAL_READ32; |
| offset = offset_2; |
| offset_2 = offset_1; |
| offset_1 = (U32)offset; /* swap repcodes */ |
| ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, matchLength - MINMATCH); |
| ip += matchLength; |
| anchor = ip; |
| continue; /* faster when present ... (?) */ |
| } |
| } |
| |
| /* Save reps for next block */ |
| ctx->repToConfirm[0] = offset_1 ? offset_1 : savedOffset; |
| ctx->repToConfirm[1] = offset_2 ? offset_2 : savedOffset; |
| |
| /* Last Literals */ |
| { |
| size_t const lastLLSize = iend - anchor; |
| memcpy(seqStorePtr->lit, anchor, lastLLSize); |
| seqStorePtr->lit += lastLLSize; |
| } |
| } |
| |
| static void ZSTD_compressBlock_btlazy2(ZSTD_CCtx *ctx, const void *src, size_t srcSize) { ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 1, 2); } |
| |
| static void ZSTD_compressBlock_lazy2(ZSTD_CCtx *ctx, const void *src, size_t srcSize) { ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 0, 2); } |
| |
| static void ZSTD_compressBlock_lazy(ZSTD_CCtx *ctx, const void *src, size_t srcSize) { ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 0, 1); } |
| |
| static void ZSTD_compressBlock_greedy(ZSTD_CCtx *ctx, const void *src, size_t srcSize) { ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 0, 0); } |
| |
| FORCE_INLINE |
| void ZSTD_compressBlock_lazy_extDict_generic(ZSTD_CCtx *ctx, const void *src, size_t srcSize, const U32 searchMethod, const U32 depth) |
| { |
| seqStore_t *seqStorePtr = &(ctx->seqStore); |
| const BYTE *const istart = (const BYTE *)src; |
| const BYTE *ip = istart; |
| const BYTE *anchor = istart; |
| const BYTE *const iend = istart + srcSize; |
| const BYTE *const ilimit = iend - 8; |
| const BYTE *const base = ctx->base; |
| const U32 dictLimit = ctx->dictLimit; |
| const U32 lowestIndex = ctx->lowLimit; |
| const BYTE *const prefixStart = base + dictLimit; |
| const BYTE *const dictBase = ctx->dictBase; |
| const BYTE *const dictEnd = dictBase + dictLimit; |
| const BYTE *const dictStart = dictBase + ctx->lowLimit; |
| |
| const U32 maxSearches = 1 << ctx->params.cParams.searchLog; |
| const U32 mls = ctx->params.cParams.searchLength; |
| |
| typedef size_t (*searchMax_f)(ZSTD_CCtx * zc, const BYTE *ip, const BYTE *iLimit, size_t *offsetPtr, U32 maxNbAttempts, U32 matchLengthSearch); |
| searchMax_f searchMax = searchMethod ? ZSTD_BtFindBestMatch_selectMLS_extDict : ZSTD_HcFindBestMatch_extDict_selectMLS; |
| |
| U32 offset_1 = ctx->rep[0], offset_2 = ctx->rep[1]; |
| |
| /* init */ |
| ctx->nextToUpdate3 = ctx->nextToUpdate; |
| ip += (ip == prefixStart); |
| |
| /* Match Loop */ |
| while (ip < ilimit) { |
| size_t matchLength = 0; |
| size_t offset = 0; |
| const BYTE *start = ip + 1; |
| U32 curr = (U32)(ip - base); |
| |
| /* check repCode */ |
| { |
| const U32 repIndex = (U32)(curr + 1 - offset_1); |
| const BYTE *const repBase = repIndex < dictLimit ? dictBase : base; |
| const BYTE *const repMatch = repBase + repIndex; |
| if (((U32)((dictLimit - 1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */ |
| if (ZSTD_read32(ip + 1) == ZSTD_read32(repMatch)) { |
| /* repcode detected we should take it */ |
| const BYTE *const repEnd = repIndex < dictLimit ? dictEnd : iend; |
| matchLength = |
| ZSTD_count_2segments(ip + 1 + EQUAL_READ32, repMatch + EQUAL_READ32, iend, repEnd, prefixStart) + EQUAL_READ32; |
| if (depth == 0) |
| goto _storeSequence; |
| } |
| } |
| |
| /* first search (depth 0) */ |
| { |
| size_t offsetFound = 99999999; |
| size_t const ml2 = searchMax(ctx, ip, iend, &offsetFound, maxSearches, mls); |
| if (ml2 > matchLength) |
| matchLength = ml2, start = ip, offset = offsetFound; |
| } |
| |
| if (matchLength < EQUAL_READ32) { |
| ip += ((ip - anchor) >> g_searchStrength) + 1; /* jump faster over incompressible sections */ |
| continue; |
| } |
| |
| /* let's try to find a better solution */ |
| if (depth >= 1) |
| while (ip < ilimit) { |
| ip++; |
| curr++; |
| /* check repCode */ |
| if (offset) { |
| const U32 repIndex = (U32)(curr - offset_1); |
| const BYTE *const repBase = repIndex < dictLimit ? dictBase : base; |
| const BYTE *const repMatch = repBase + repIndex; |
| if (((U32)((dictLimit - 1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */ |
| if (ZSTD_read32(ip) == ZSTD_read32(repMatch)) { |
| /* repcode detected */ |
| const BYTE *const repEnd = repIndex < dictLimit ? dictEnd : iend; |
| size_t const repLength = |
| ZSTD_count_2segments(ip + EQUAL_READ32, repMatch + EQUAL_READ32, iend, repEnd, prefixStart) + |
| EQUAL_READ32; |
| int const gain2 = (int)(repLength * 3); |
| int const gain1 = (int)(matchLength * 3 - ZSTD_highbit32((U32)offset + 1) + 1); |
| if ((repLength >= EQUAL_READ32) && (gain2 > gain1)) |
| matchLength = repLength, offset = 0, start = ip; |
| } |
| } |
| |
| /* search match, depth 1 */ |
| { |
| size_t offset2 = 99999999; |
| size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls); |
| int const gain2 = (int)(ml2 * 4 - ZSTD_highbit32((U32)offset2 + 1)); /* raw approx */ |
| int const gain1 = (int)(matchLength * 4 - ZSTD_highbit32((U32)offset + 1) + 4); |
| if ((ml2 >= EQUAL_READ32) && (gain2 > gain1)) { |
| matchLength = ml2, offset = offset2, start = ip; |
| continue; /* search a better one */ |
| } |
| } |
| |
| /* let's find an even better one */ |
| if ((depth == 2) && (ip < ilimit)) { |
| ip++; |
| curr++; |
| /* check repCode */ |
| if (offset) { |
| const U32 repIndex = (U32)(curr - offset_1); |
| const BYTE *const repBase = repIndex < dictLimit ? dictBase : base; |
| const BYTE *const repMatch = repBase + repIndex; |
| if (((U32)((dictLimit - 1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */ |
| if (ZSTD_read32(ip) == ZSTD_read32(repMatch)) { |
| /* repcode detected */ |
| const BYTE *const repEnd = repIndex < dictLimit ? dictEnd : iend; |
| size_t repLength = ZSTD_count_2segments(ip + EQUAL_READ32, repMatch + EQUAL_READ32, iend, |
| repEnd, prefixStart) + |
| EQUAL_READ32; |
| int gain2 = (int)(repLength * 4); |
| int gain1 = (int)(matchLength * 4 - ZSTD_highbit32((U32)offset + 1) + 1); |
| if ((repLength >= EQUAL_READ32) && (gain2 > gain1)) |
| matchLength = repLength, offset = 0, start = ip; |
| } |
| } |
| |
| /* search match, depth 2 */ |
| { |
| size_t offset2 = 99999999; |
| size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls); |
| int const gain2 = (int)(ml2 * 4 - ZSTD_highbit32((U32)offset2 + 1)); /* raw approx */ |
| int const gain1 = (int)(matchLength * 4 - ZSTD_highbit32((U32)offset + 1) + 7); |
| if ((ml2 >= EQUAL_READ32) && (gain2 > gain1)) { |
| matchLength = ml2, offset = offset2, start = ip; |
| continue; |
| } |
| } |
| } |
| break; /* nothing found : store previous solution */ |
| } |
| |
| /* catch up */ |
| if (offset) { |
| U32 const matchIndex = (U32)((start - base) - (offset - ZSTD_REP_MOVE)); |
| const BYTE *match = (matchIndex < dictLimit) ? dictBase + matchIndex : base + matchIndex; |
| const BYTE *const mStart = (matchIndex < dictLimit) ? dictStart : prefixStart; |
| while ((start > anchor) && (match > mStart) && (start[-1] == match[-1])) { |
| start--; |
| match--; |
| matchLength++; |
| } /* catch up */ |
| offset_2 = offset_1; |
| offset_1 = (U32)(offset - ZSTD_REP_MOVE); |
| } |
| |
| /* store sequence */ |
| _storeSequence : { |
| size_t const litLength = start - anchor; |
| ZSTD_storeSeq(seqStorePtr, litLength, anchor, (U32)offset, matchLength - MINMATCH); |
| anchor = ip = start + matchLength; |
| } |
| |
| /* check immediate repcode */ |
| while (ip <= ilimit) { |
| const U32 repIndex = (U32)((ip - base) - offset_2); |
| const BYTE *const repBase = repIndex < dictLimit ? dictBase : base; |
| const BYTE *const repMatch = repBase + repIndex; |
| if (((U32)((dictLimit - 1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */ |
| if (ZSTD_read32(ip) == ZSTD_read32(repMatch)) { |
| /* repcode detected we should take it */ |
| const BYTE *const repEnd = repIndex < dictLimit ? dictEnd : iend; |
| matchLength = |
| ZSTD_count_2segments(ip + EQUAL_READ32, repMatch + EQUAL_READ32, iend, repEnd, prefixStart) + EQUAL_READ32; |
| offset = offset_2; |
| offset_2 = offset_1; |
| offset_1 = (U32)offset; /* swap offset history */ |
| ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, matchLength - MINMATCH); |
| ip += matchLength; |
| anchor = ip; |
| continue; /* faster when present ... (?) */ |
| } |
| break; |
| } |
| } |
| |
| /* Save reps for next block */ |
| ctx->repToConfirm[0] = offset_1; |
| ctx->repToConfirm[1] = offset_2; |
| |
| /* Last Literals */ |
| { |
| size_t const lastLLSize = iend - anchor; |
| memcpy(seqStorePtr->lit, anchor, lastLLSize); |
| seqStorePtr->lit += lastLLSize; |
| } |
| } |
| |
| void ZSTD_compressBlock_greedy_extDict(ZSTD_CCtx *ctx, const void *src, size_t srcSize) { ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 0, 0); } |
| |
| static void ZSTD_compressBlock_lazy_extDict(ZSTD_CCtx *ctx, const void *src, size_t srcSize) |
| { |
| ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 0, 1); |
| } |
| |
| static void ZSTD_compressBlock_lazy2_extDict(ZSTD_CCtx *ctx, const void *src, size_t srcSize) |
| { |
| ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 0, 2); |
| } |
| |
| static void ZSTD_compressBlock_btlazy2_extDict(ZSTD_CCtx *ctx, const void *src, size_t srcSize) |
| { |
| ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 1, 2); |
| } |
| |
| /* The optimal parser */ |
| #include "zstd_opt.h" |
| |
| static void ZSTD_compressBlock_btopt(ZSTD_CCtx *ctx, const void *src, size_t srcSize) |
| { |
| #ifdef ZSTD_OPT_H_91842398743 |
| ZSTD_compressBlock_opt_generic(ctx, src, srcSize, 0); |
| #else |
| (void)ctx; |
| (void)src; |
| (void)srcSize; |
| return; |
| #endif |
| } |
| |
| static void ZSTD_compressBlock_btopt2(ZSTD_CCtx *ctx, const void *src, size_t srcSize) |
| { |
| #ifdef ZSTD_OPT_H_91842398743 |
| ZSTD_compressBlock_opt_generic(ctx, src, srcSize, 1); |
| #else |
| (void)ctx; |
| (void)src; |
| (void)srcSize; |
| return; |
| #endif |
| } |
| |
| static void ZSTD_compressBlock_btopt_extDict(ZSTD_CCtx *ctx, const void *src, size_t srcSize) |
| { |
| #ifdef ZSTD_OPT_H_91842398743 |
| ZSTD_compressBlock_opt_extDict_generic(ctx, src, srcSize, 0); |
| #else |
| (void)ctx; |
| (void)src; |
| (void)srcSize; |
| return; |
| #endif |
| } |
| |
| static void ZSTD_compressBlock_btopt2_extDict(ZSTD_CCtx *ctx, const void *src, size_t srcSize) |
| { |
| #ifdef ZSTD_OPT_H_91842398743 |
| ZSTD_compressBlock_opt_extDict_generic(ctx, src, srcSize, 1); |
| #else |
| (void)ctx; |
| (void)src; |
| (void)srcSize; |
| return; |
| #endif |
| } |
| |
| typedef void (*ZSTD_blockCompressor)(ZSTD_CCtx *ctx, const void *src, size_t srcSize); |
| |
| static ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, int extDict) |
| { |
| static const ZSTD_blockCompressor blockCompressor[2][8] = { |
| {ZSTD_compressBlock_fast, ZSTD_compressBlock_doubleFast, ZSTD_compressBlock_greedy, ZSTD_compressBlock_lazy, ZSTD_compressBlock_lazy2, |
| ZSTD_compressBlock_btlazy2, ZSTD_compressBlock_btopt, ZSTD_compressBlock_btopt2}, |
| {ZSTD_compressBlock_fast_extDict, ZSTD_compressBlock_doubleFast_extDict, ZSTD_compressBlock_greedy_extDict, ZSTD_compressBlock_lazy_extDict, |
| ZSTD_compressBlock_lazy2_extDict, ZSTD_compressBlock_btlazy2_extDict, ZSTD_compressBlock_btopt_extDict, ZSTD_compressBlock_btopt2_extDict}}; |
| |
| return blockCompressor[extDict][(U32)strat]; |
| } |
| |
| static size_t ZSTD_compressBlock_internal(ZSTD_CCtx *zc, void *dst, size_t dstCapacity, const void *src, size_t srcSize) |
| { |
| ZSTD_blockCompressor const blockCompressor = ZSTD_selectBlockCompressor(zc->params.cParams.strategy, zc->lowLimit < zc->dictLimit); |
| const BYTE *const base = zc->base; |
| const BYTE *const istart = (const BYTE *)src; |
| const U32 curr = (U32)(istart - base); |
| if (srcSize < MIN_CBLOCK_SIZE + ZSTD_blockHeaderSize + 1) |
| return 0; /* don't even attempt compression below a certain srcSize */ |
| ZSTD_resetSeqStore(&(zc->seqStore)); |
| if (curr > zc->nextToUpdate + 384) |
| zc->nextToUpdate = curr - MIN(192, (U32)(curr - zc->nextToUpdate - 384)); /* update tree not updated after finding very long rep matches */ |
| blockCompressor(zc, src, srcSize); |
| return ZSTD_compressSequences(zc, dst, dstCapacity, srcSize); |
| } |
| |
| /*! ZSTD_compress_generic() : |
| * Compress a chunk of data into one or multiple blocks. |
| * All blocks will be terminated, all input will be consumed. |
| * Function will issue an error if there is not enough `dstCapacity` to hold the compressed content. |
| * Frame is supposed already started (header already produced) |
| * @return : compressed size, or an error code |
| */ |
| static size_t ZSTD_compress_generic(ZSTD_CCtx * |