/** * 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"). */ /* ****************************************************************  Tuning parameters*****************************************************************//*!*  MAXWINDOWSIZE_DEFAULT :*  maximum window size accepted by DStream, by default.*  Frames requiring more memory will be rejected.*/#ifndef ZSTD_MAXWINDOWSIZE_DEFAULT#define ZSTD_MAXWINDOWSIZE_DEFAULT ((1 << ZSTD_WINDOWLOG_MAX) + 1) /* defined within zstd.h */#endif /*-********************************************************  Dependencies*********************************************************/#include "fse.h"#include "huf.h"#include "mem.h" /* low level memory routines */#include "zstd_internal.h"#include <linux/kernel.h>#include <linux/module.h>#include <linux/string.h> /* memcpy, memmove, memset */ #define ZSTD_PREFETCH(ptr) __builtin_prefetch(ptr, 0, 0) /*-**************************************  Macros***************************************/#define ZSTD_isError ERR_isError /* for inlining */#define FSE_isError ERR_isError#define HUF_isError ERR_isError /*_********************************************************  Memory operations**********************************************************/static void ZSTD_copy4(void *dst, const void *src) { memcpy(dst, src, 4); } /*-**************************************************************   Context management***************************************************************/typedef enum {	ZSTDds_getFrameHeaderSize,	ZSTDds_decodeFrameHeader,	ZSTDds_decodeBlockHeader,	ZSTDds_decompressBlock,	ZSTDds_decompressLastBlock,	ZSTDds_checkChecksum,	ZSTDds_decodeSkippableHeader,	ZSTDds_skipFrame} ZSTD_dStage; typedef struct {	FSE_DTable LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];	FSE_DTable OFTable[FSE_DTABLE_SIZE_U32(OffFSELog)];	FSE_DTable MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];	HUF_DTable hufTable[HUF_DTABLE_SIZE(HufLog)]; /* can accommodate HUF_decompress4X */	U64 workspace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32 / 2];	U32 rep[ZSTD_REP_NUM];} ZSTD_entropyTables_t; struct ZSTD_DCtx_s {	const FSE_DTable *LLTptr;	const FSE_DTable *MLTptr;	const FSE_DTable *OFTptr;	const HUF_DTable *HUFptr;	ZSTD_entropyTables_t entropy;	const void *previousDstEnd; /* detect continuity */	const void *base;	   /* start of curr segment */	const void *vBase;	  /* virtual start of previous segment if it was just before curr one */	const void *dictEnd;	/* end of previous segment */	size_t expected;	ZSTD_frameParams fParams;	blockType_e bType; /* used in ZSTD_decompressContinue(), to transfer blockType between header decoding and block decoding stages */	ZSTD_dStage stage;	U32 litEntropy;	U32 fseEntropy;	struct xxh64_state xxhState;	size_t headerSize;	U32 dictID;	const BYTE *litPtr;	ZSTD_customMem customMem;	size_t litSize;	size_t rleSize;	BYTE litBuffer[ZSTD_BLOCKSIZE_ABSOLUTEMAX + WILDCOPY_OVERLENGTH];	BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX];}; /* typedef'd to ZSTD_DCtx within "zstd.h" */ size_t ZSTD_DCtxWorkspaceBound(void) { return ZSTD_ALIGN(sizeof(ZSTD_stack)) + ZSTD_ALIGN(sizeof(ZSTD_DCtx)); } size_t ZSTD_decompressBegin(ZSTD_DCtx *dctx){	dctx->expected = ZSTD_frameHeaderSize_prefix;	dctx->stage = ZSTDds_getFrameHeaderSize;	dctx->previousDstEnd = NULL;	dctx->base = NULL;	dctx->vBase = NULL;	dctx->dictEnd = NULL;	dctx->entropy.hufTable[0] = (HUF_DTable)((HufLog)*0x1000001); /* cover both little and big endian */	dctx->litEntropy = dctx->fseEntropy = 0;	dctx->dictID = 0;	ZSTD_STATIC_ASSERT(sizeof(dctx->entropy.rep) == sizeof(repStartValue));	memcpy(dctx->entropy.rep, repStartValue, sizeof(repStartValue)); /* initial repcodes */	dctx->LLTptr = dctx->entropy.LLTable;	dctx->MLTptr = dctx->entropy.MLTable;	dctx->OFTptr = dctx->entropy.OFTable;	dctx->HUFptr = dctx->entropy.hufTable;	return 0;} ZSTD_DCtx *ZSTD_createDCtx_advanced(ZSTD_customMem customMem){	ZSTD_DCtx *dctx; 	if (!customMem.customAlloc || !customMem.customFree)		return NULL; 	dctx = (ZSTD_DCtx *)ZSTD_malloc(sizeof(ZSTD_DCtx), customMem);	if (!dctx)		return NULL;	memcpy(&dctx->customMem, &customMem, sizeof(customMem));	ZSTD_decompressBegin(dctx);	return dctx;} ZSTD_DCtx *ZSTD_initDCtx(void *workspace, size_t workspaceSize){	ZSTD_customMem const stackMem = ZSTD_initStack(workspace, workspaceSize);	return ZSTD_createDCtx_advanced(stackMem);} size_t ZSTD_freeDCtx(ZSTD_DCtx *dctx){	if (dctx == NULL)		return 0; /* support free on NULL */	ZSTD_free(dctx, dctx->customMem);	return 0; /* reserved as a potential error code in the future */} void ZSTD_copyDCtx(ZSTD_DCtx *dstDCtx, const ZSTD_DCtx *srcDCtx){	size_t const workSpaceSize = (ZSTD_BLOCKSIZE_ABSOLUTEMAX + WILDCOPY_OVERLENGTH) + ZSTD_frameHeaderSize_max;	memcpy(dstDCtx, srcDCtx, sizeof(ZSTD_DCtx) - workSpaceSize); /* no need to copy workspace */} static void ZSTD_refDDict(ZSTD_DCtx *dstDCtx, const ZSTD_DDict *ddict); /*-**************************************************************   Decompression section***************************************************************/ /*! ZSTD_isFrame() : *  Tells if the content of `buffer` starts with a valid Frame Identifier. *  Note : Frame Identifier is 4 bytes. If `size < 4`, @return will always be 0. *  Note 2 : Legacy Frame Identifiers are considered valid only if Legacy Support is enabled. *  Note 3 : Skippable Frame Identifiers are considered valid. */unsigned ZSTD_isFrame(const void *buffer, size_t size){	if (size < 4)		return 0;	{		U32 const magic = ZSTD_readLE32(buffer);		if (magic == ZSTD_MAGICNUMBER)			return 1;		if ((magic & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START)			return 1;	}	return 0;} /** ZSTD_frameHeaderSize() :*   srcSize must be >= ZSTD_frameHeaderSize_prefix.*   @return : size of the Frame Header */static size_t ZSTD_frameHeaderSize(const void *src, size_t srcSize){	if (srcSize < ZSTD_frameHeaderSize_prefix)		return ERROR(srcSize_wrong);	{		BYTE const fhd = ((const BYTE *)src)[4];		U32 const dictID = fhd & 3;		U32 const singleSegment = (fhd >> 5) & 1;		U32 const fcsId = fhd >> 6;		return ZSTD_frameHeaderSize_prefix + !singleSegment + ZSTD_did_fieldSize[dictID] + ZSTD_fcs_fieldSize[fcsId] + (singleSegment && !fcsId);	}} /** ZSTD_getFrameParams() :*   decode Frame Header, or require larger `srcSize`.*   @return : 0, `fparamsPtr` is correctly filled,*            >0, `srcSize` is too small, result is expected `srcSize`,*             or an error code, which can be tested using ZSTD_isError() */size_t ZSTD_getFrameParams(ZSTD_frameParams *fparamsPtr, const void *src, size_t srcSize){	const BYTE *ip = (const BYTE *)src; 	if (srcSize < ZSTD_frameHeaderSize_prefix)		return ZSTD_frameHeaderSize_prefix;	if (ZSTD_readLE32(src) != ZSTD_MAGICNUMBER) {		if ((ZSTD_readLE32(src) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {			if (srcSize < ZSTD_skippableHeaderSize)				return ZSTD_skippableHeaderSize; /* magic number + skippable frame length */			memset(fparamsPtr, 0, sizeof(*fparamsPtr));			fparamsPtr->frameContentSize = ZSTD_readLE32((const char *)src + 4);			fparamsPtr->windowSize = 0; /* windowSize==0 means a frame is skippable */			return 0;		}		return ERROR(prefix_unknown);	} 	/* ensure there is enough `srcSize` to fully read/decode frame header */	{		size_t const fhsize = ZSTD_frameHeaderSize(src, srcSize);		if (srcSize < fhsize)			return fhsize;	} 	{		BYTE const fhdByte = ip[4];		size_t pos = 5;		U32 const dictIDSizeCode = fhdByte & 3;		U32 const checksumFlag = (fhdByte >> 2) & 1;		U32 const singleSegment = (fhdByte >> 5) & 1;		U32 const fcsID = fhdByte >> 6;		U32 const windowSizeMax = 1U << ZSTD_WINDOWLOG_MAX;		U32 windowSize = 0;		U32 dictID = 0;		U64 frameContentSize = 0;		if ((fhdByte & 0x08) != 0)			return ERROR(frameParameter_unsupported); /* reserved bits, which must be zero */		if (!singleSegment) {			BYTE const wlByte = ip[pos++];			U32 const windowLog = (wlByte >> 3) + ZSTD_WINDOWLOG_ABSOLUTEMIN;			if (windowLog > ZSTD_WINDOWLOG_MAX)				return ERROR(frameParameter_windowTooLarge); /* avoids issue with 1 << windowLog */			windowSize = (1U << windowLog);			windowSize += (windowSize >> 3) * (wlByte & 7);		} 		switch (dictIDSizeCode) {		default: /* impossible */		case 0: break;		case 1:			dictID = ip[pos];			pos++;			break;		case 2:			dictID = ZSTD_readLE16(ip + pos);			pos += 2;			break;		case 3:			dictID = ZSTD_readLE32(ip + pos);			pos += 4;			break;		}		switch (fcsID) {		default: /* impossible */		case 0:			if (singleSegment)				frameContentSize = ip[pos];			break;		case 1: frameContentSize = ZSTD_readLE16(ip + pos) + 256; break;		case 2: frameContentSize = ZSTD_readLE32(ip + pos); break;		case 3: frameContentSize = ZSTD_readLE64(ip + pos); break;		}		if (!windowSize)			windowSize = (U32)frameContentSize;		if (windowSize > windowSizeMax)			return ERROR(frameParameter_windowTooLarge);		fparamsPtr->frameContentSize = frameContentSize;		fparamsPtr->windowSize = windowSize;		fparamsPtr->dictID = dictID;		fparamsPtr->checksumFlag = checksumFlag;	}	return 0;} /** ZSTD_getFrameContentSize() :*   compatible with legacy mode*   @return : decompressed size of the single frame pointed to be `src` if known, otherwise*             - ZSTD_CONTENTSIZE_UNKNOWN if the size cannot be determined*             - ZSTD_CONTENTSIZE_ERROR if an error occurred (e.g. invalid magic number, srcSize too small) */unsigned long long ZSTD_getFrameContentSize(const void *src, size_t srcSize){	{		ZSTD_frameParams fParams;		if (ZSTD_getFrameParams(&fParams, src, srcSize) != 0)			return ZSTD_CONTENTSIZE_ERROR;		if (fParams.windowSize == 0) {			/* Either skippable or empty frame, size == 0 either way */			return 0;		} else if (fParams.frameContentSize != 0) {			return fParams.frameContentSize;		} else {			return ZSTD_CONTENTSIZE_UNKNOWN;		}	}} /** ZSTD_findDecompressedSize() : *  compatible with legacy mode *  `srcSize` must be the exact length of some number of ZSTD compressed and/or *      skippable frames *  @return : decompressed size of the frames contained */unsigned long long ZSTD_findDecompressedSize(const void *src, size_t srcSize){	{		unsigned long long totalDstSize = 0;		while (srcSize >= ZSTD_frameHeaderSize_prefix) {			const U32 magicNumber = ZSTD_readLE32(src); 			if ((magicNumber & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {				size_t skippableSize;				if (srcSize < ZSTD_skippableHeaderSize)					return ERROR(srcSize_wrong);				skippableSize = ZSTD_readLE32((const BYTE *)src + 4) + ZSTD_skippableHeaderSize;				if (srcSize < skippableSize) {					return ZSTD_CONTENTSIZE_ERROR;				} 				src = (const BYTE *)src + skippableSize;				srcSize -= skippableSize;				continue;			} 			{				unsigned long long const ret = ZSTD_getFrameContentSize(src, srcSize);				if (ret >= ZSTD_CONTENTSIZE_ERROR)					return ret; 				/* check for overflow */				if (totalDstSize + ret < totalDstSize)					return ZSTD_CONTENTSIZE_ERROR;				totalDstSize += ret;			}			{				size_t const frameSrcSize = ZSTD_findFrameCompressedSize(src, srcSize);				if (ZSTD_isError(frameSrcSize)) {					return ZSTD_CONTENTSIZE_ERROR;				} 				src = (const BYTE *)src + frameSrcSize;				srcSize -= frameSrcSize;			}		} 		if (srcSize) {			return ZSTD_CONTENTSIZE_ERROR;		} 		return totalDstSize;	}} /** ZSTD_decodeFrameHeader() :*   `headerSize` must be the size provided by ZSTD_frameHeaderSize().*   @return : 0 if success, or an error code, which can be tested using ZSTD_isError() */static size_t ZSTD_decodeFrameHeader(ZSTD_DCtx *dctx, const void *src, size_t headerSize){	size_t const result = ZSTD_getFrameParams(&(dctx->fParams), src, headerSize);	if (ZSTD_isError(result))		return result; /* invalid header */	if (result > 0)		return ERROR(srcSize_wrong); /* headerSize too small */	if (dctx->fParams.dictID && (dctx->dictID != dctx->fParams.dictID))		return ERROR(dictionary_wrong);	if (dctx->fParams.checksumFlag)		xxh64_reset(&dctx->xxhState, 0);	return 0;} typedef struct {	blockType_e blockType;	U32 lastBlock;	U32 origSize;} blockProperties_t; /*! ZSTD_getcBlockSize() :*   Provides the size of compressed block from block header `src` */size_t ZSTD_getcBlockSize(const void *src, size_t srcSize, blockProperties_t *bpPtr){	if (srcSize < ZSTD_blockHeaderSize)		return ERROR(srcSize_wrong);	{		U32 const cBlockHeader = ZSTD_readLE24(src);		U32 const cSize = cBlockHeader >> 3;		bpPtr->lastBlock = cBlockHeader & 1;		bpPtr->blockType = (blockType_e)((cBlockHeader >> 1) & 3);		bpPtr->origSize = cSize; /* only useful for RLE */		if (bpPtr->blockType == bt_rle)			return 1;		if (bpPtr->blockType == bt_reserved)			return ERROR(corruption_detected);		return cSize;	}} static size_t ZSTD_copyRawBlock(void *dst, size_t dstCapacity, const void *src, size_t srcSize){	if (srcSize > dstCapacity)		return ERROR(dstSize_tooSmall);	memcpy(dst, src, srcSize);	return srcSize;} static size_t ZSTD_setRleBlock(void *dst, size_t dstCapacity, const void *src, size_t srcSize, size_t regenSize){	if (srcSize != 1)		return ERROR(srcSize_wrong);	if (regenSize > dstCapacity)		return ERROR(dstSize_tooSmall);	memset(dst, *(const BYTE *)src, regenSize);	return regenSize;} /*! ZSTD_decodeLiteralsBlock() :	@return : nb of bytes read from src (< srcSize ) */size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx *dctx, const void *src, size_t srcSize) /* note : srcSize < BLOCKSIZE */{	if (srcSize < MIN_CBLOCK_SIZE)		return ERROR(corruption_detected); 	{		const BYTE *const istart = (const BYTE *)src;		symbolEncodingType_e const litEncType = (symbolEncodingType_e)(istart[0] & 3); 		switch (litEncType) {		case set_repeat:			if (dctx->litEntropy == 0)				return ERROR(dictionary_corrupted);			fallthrough;		case set_compressed:			if (srcSize < 5)				return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for case 3 */			{				size_t lhSize, litSize, litCSize;				U32 singleStream = 0;				U32 const lhlCode = (istart[0] >> 2) & 3;				U32 const lhc = ZSTD_readLE32(istart);				switch (lhlCode) {				case 0:				case 1:				default: /* note : default is impossible, since lhlCode into [0..3] */					/* 2 - 2 - 10 - 10 */					singleStream = !lhlCode;					lhSize = 3;					litSize = (lhc >> 4) & 0x3FF;					litCSize = (lhc >> 14) & 0x3FF;					break;				case 2:					/* 2 - 2 - 14 - 14 */					lhSize = 4;					litSize = (lhc >> 4) & 0x3FFF;					litCSize = lhc >> 18;					break;				case 3:					/* 2 - 2 - 18 - 18 */					lhSize = 5;					litSize = (lhc >> 4) & 0x3FFFF;					litCSize = (lhc >> 22) + (istart[4] << 10);					break;				}				if (litSize > ZSTD_BLOCKSIZE_ABSOLUTEMAX)					return ERROR(corruption_detected);				if (litCSize + lhSize > srcSize)					return ERROR(corruption_detected); 				if (HUF_isError(					(litEncType == set_repeat)					    ? (singleStream ? HUF_decompress1X_usingDTable(dctx->litBuffer, litSize, istart + lhSize, litCSize, dctx->HUFptr)							    : HUF_decompress4X_usingDTable(dctx->litBuffer, litSize, istart + lhSize, litCSize, dctx->HUFptr))					    : (singleStream						   ? HUF_decompress1X2_DCtx_wksp(dctx->entropy.hufTable, dctx->litBuffer, litSize, istart + lhSize, litCSize,										 dctx->entropy.workspace, sizeof(dctx->entropy.workspace))						   : HUF_decompress4X_hufOnly_wksp(dctx->entropy.hufTable, dctx->litBuffer, litSize, istart + lhSize, litCSize,										   dctx->entropy.workspace, sizeof(dctx->entropy.workspace)))))					return ERROR(corruption_detected); 				dctx->litPtr = dctx->litBuffer;				dctx->litSize = litSize;				dctx->litEntropy = 1;				if (litEncType == set_compressed)					dctx->HUFptr = dctx->entropy.hufTable;				memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);				return litCSize + lhSize;			}

Lines 1–500 of 2531. Load more