/** * 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 8typedef 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 */

Lines 1–500 of 3485. Load more