1 // SPDX-License-Identifier: (GPL-2.0 or BSD-3-Clause-Clear)
3 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
7 /* ***************************************************************
9 *****************************************************************/
11 * MAXWINDOWSIZE_DEFAULT :
12 * maximum window size accepted by DStream, by default.
13 * Frames requiring more memory will be rejected.
15 #ifndef ZSTD_MAXWINDOWSIZE_DEFAULT
16 #define ZSTD_MAXWINDOWSIZE_DEFAULT ((1 << ZSTD_WINDOWLOG_MAX) + 1) /* defined within zstd.h */
19 /*-*******************************************************
21 *********************************************************/
24 #include "mem.h" /* low level memory routines */
25 #include "zstd_internal.h"
26 #include <linux/kernel.h>
27 #include <linux/compat.h>
28 #include <linux/string.h> /* memcpy, memmove, memset */
30 #define ZSTD_PREFETCH(ptr) __builtin_prefetch(ptr, 0, 0)
32 /*-*************************************
34 ***************************************/
35 #define ZSTD_isError ERR_isError /* for inlining */
36 #define FSE_isError ERR_isError
37 #define HUF_isError ERR_isError
39 /*_*******************************************************
41 **********************************************************/
42 static void ZSTD_copy4(void *dst, const void *src) { memcpy(dst, src, 4); }
44 /*-*************************************************************
46 ***************************************************************/
48 ZSTDds_getFrameHeaderSize,
49 ZSTDds_decodeFrameHeader,
50 ZSTDds_decodeBlockHeader,
51 ZSTDds_decompressBlock,
52 ZSTDds_decompressLastBlock,
54 ZSTDds_decodeSkippableHeader,
59 FSE_DTable LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
60 FSE_DTable OFTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
61 FSE_DTable MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
62 HUF_DTable hufTable[HUF_DTABLE_SIZE(HufLog)]; /* can accommodate HUF_decompress4X */
63 U64 workspace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32 / 2];
64 U32 rep[ZSTD_REP_NUM];
65 } ZSTD_entropyTables_t;
68 const FSE_DTable *LLTptr;
69 const FSE_DTable *MLTptr;
70 const FSE_DTable *OFTptr;
71 const HUF_DTable *HUFptr;
72 ZSTD_entropyTables_t entropy;
73 const void *previousDstEnd; /* detect continuity */
74 const void *base; /* start of curr segment */
75 const void *vBase; /* virtual start of previous segment if it was just before curr one */
76 const void *dictEnd; /* end of previous segment */
78 ZSTD_frameParams fParams;
79 blockType_e bType; /* used in ZSTD_decompressContinue(), to transfer blockType between header decoding and block decoding stages */
83 struct xxh64_state xxhState;
87 ZSTD_customMem customMem;
90 BYTE litBuffer[ZSTD_BLOCKSIZE_ABSOLUTEMAX + WILDCOPY_OVERLENGTH];
91 BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX];
92 }; /* typedef'd to ZSTD_DCtx within "zstd.h" */
94 size_t ZSTD_DCtxWorkspaceBound(void) { return ZSTD_ALIGN(sizeof(ZSTD_stack)) + ZSTD_ALIGN(sizeof(ZSTD_DCtx)); }
96 size_t ZSTD_decompressBegin(ZSTD_DCtx *dctx)
98 dctx->expected = ZSTD_frameHeaderSize_prefix;
99 dctx->stage = ZSTDds_getFrameHeaderSize;
100 dctx->previousDstEnd = NULL;
103 dctx->dictEnd = NULL;
104 dctx->entropy.hufTable[0] = (HUF_DTable)((HufLog)*0x1000001); /* cover both little and big endian */
105 dctx->litEntropy = dctx->fseEntropy = 0;
107 ZSTD_STATIC_ASSERT(sizeof(dctx->entropy.rep) == sizeof(repStartValue));
108 memcpy(dctx->entropy.rep, repStartValue, sizeof(repStartValue)); /* initial repcodes */
109 dctx->LLTptr = dctx->entropy.LLTable;
110 dctx->MLTptr = dctx->entropy.MLTable;
111 dctx->OFTptr = dctx->entropy.OFTable;
112 dctx->HUFptr = dctx->entropy.hufTable;
116 ZSTD_DCtx *ZSTD_createDCtx_advanced(ZSTD_customMem customMem)
120 if (!customMem.customAlloc || !customMem.customFree)
123 dctx = (ZSTD_DCtx *)ZSTD_malloc(sizeof(ZSTD_DCtx), customMem);
126 memcpy(&dctx->customMem, &customMem, sizeof(customMem));
127 ZSTD_decompressBegin(dctx);
131 ZSTD_DCtx *ZSTD_initDCtx(void *workspace, size_t workspaceSize)
133 ZSTD_customMem const stackMem = ZSTD_initStack(workspace, workspaceSize);
134 return ZSTD_createDCtx_advanced(stackMem);
137 size_t ZSTD_freeDCtx(ZSTD_DCtx *dctx)
140 return 0; /* support free on NULL */
141 ZSTD_free(dctx, dctx->customMem);
142 return 0; /* reserved as a potential error code in the future */
145 void ZSTD_copyDCtx(ZSTD_DCtx *dstDCtx, const ZSTD_DCtx *srcDCtx)
147 size_t const workSpaceSize = (ZSTD_BLOCKSIZE_ABSOLUTEMAX + WILDCOPY_OVERLENGTH) + ZSTD_frameHeaderSize_max;
148 memcpy(dstDCtx, srcDCtx, sizeof(ZSTD_DCtx) - workSpaceSize); /* no need to copy workspace */
151 static void ZSTD_refDDict(ZSTD_DCtx *dstDCtx, const ZSTD_DDict *ddict);
153 /*-*************************************************************
154 * Decompression section
155 ***************************************************************/
158 * Tells if the content of `buffer` starts with a valid Frame Identifier.
159 * Note : Frame Identifier is 4 bytes. If `size < 4`, @return will always be 0.
160 * Note 2 : Legacy Frame Identifiers are considered valid only if Legacy Support is enabled.
161 * Note 3 : Skippable Frame Identifiers are considered valid. */
162 unsigned ZSTD_isFrame(const void *buffer, size_t size)
167 U32 const magic = ZSTD_readLE32(buffer);
168 if (magic == ZSTD_MAGICNUMBER)
170 if ((magic & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START)
176 /** ZSTD_frameHeaderSize() :
177 * srcSize must be >= ZSTD_frameHeaderSize_prefix.
178 * @return : size of the Frame Header */
179 static size_t ZSTD_frameHeaderSize(const void *src, size_t srcSize)
181 if (srcSize < ZSTD_frameHeaderSize_prefix)
182 return ERROR(srcSize_wrong);
184 BYTE const fhd = ((const BYTE *)src)[4];
185 U32 const dictID = fhd & 3;
186 U32 const singleSegment = (fhd >> 5) & 1;
187 U32 const fcsId = fhd >> 6;
188 return ZSTD_frameHeaderSize_prefix + !singleSegment + ZSTD_did_fieldSize[dictID] + ZSTD_fcs_fieldSize[fcsId] + (singleSegment && !fcsId);
192 /** ZSTD_getFrameParams() :
193 * decode Frame Header, or require larger `srcSize`.
194 * @return : 0, `fparamsPtr` is correctly filled,
195 * >0, `srcSize` is too small, result is expected `srcSize`,
196 * or an error code, which can be tested using ZSTD_isError() */
197 size_t ZSTD_getFrameParams(ZSTD_frameParams *fparamsPtr, const void *src, size_t srcSize)
199 const BYTE *ip = (const BYTE *)src;
201 if (srcSize < ZSTD_frameHeaderSize_prefix)
202 return ZSTD_frameHeaderSize_prefix;
203 if (ZSTD_readLE32(src) != ZSTD_MAGICNUMBER) {
204 if ((ZSTD_readLE32(src) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
205 if (srcSize < ZSTD_skippableHeaderSize)
206 return ZSTD_skippableHeaderSize; /* magic number + skippable frame length */
207 memset(fparamsPtr, 0, sizeof(*fparamsPtr));
208 fparamsPtr->frameContentSize = ZSTD_readLE32((const char *)src + 4);
209 fparamsPtr->windowSize = 0; /* windowSize==0 means a frame is skippable */
212 return ERROR(prefix_unknown);
215 /* ensure there is enough `srcSize` to fully read/decode frame header */
217 size_t const fhsize = ZSTD_frameHeaderSize(src, srcSize);
218 if (srcSize < fhsize)
223 BYTE const fhdByte = ip[4];
225 U32 const dictIDSizeCode = fhdByte & 3;
226 U32 const checksumFlag = (fhdByte >> 2) & 1;
227 U32 const singleSegment = (fhdByte >> 5) & 1;
228 U32 const fcsID = fhdByte >> 6;
229 U32 const windowSizeMax = 1U << ZSTD_WINDOWLOG_MAX;
232 U64 frameContentSize = 0;
233 if ((fhdByte & 0x08) != 0)
234 return ERROR(frameParameter_unsupported); /* reserved bits, which must be zero */
235 if (!singleSegment) {
236 BYTE const wlByte = ip[pos++];
237 U32 const windowLog = (wlByte >> 3) + ZSTD_WINDOWLOG_ABSOLUTEMIN;
238 if (windowLog > ZSTD_WINDOWLOG_MAX)
239 return ERROR(frameParameter_windowTooLarge); /* avoids issue with 1 << windowLog */
240 windowSize = (1U << windowLog);
241 windowSize += (windowSize >> 3) * (wlByte & 7);
244 switch (dictIDSizeCode) {
245 default: /* impossible */
252 dictID = ZSTD_readLE16(ip + pos);
256 dictID = ZSTD_readLE32(ip + pos);
261 default: /* impossible */
264 frameContentSize = ip[pos];
266 case 1: frameContentSize = ZSTD_readLE16(ip + pos) + 256; break;
267 case 2: frameContentSize = ZSTD_readLE32(ip + pos); break;
268 case 3: frameContentSize = ZSTD_readLE64(ip + pos); break;
271 windowSize = (U32)frameContentSize;
272 if (windowSize > windowSizeMax)
273 return ERROR(frameParameter_windowTooLarge);
274 fparamsPtr->frameContentSize = frameContentSize;
275 fparamsPtr->windowSize = windowSize;
276 fparamsPtr->dictID = dictID;
277 fparamsPtr->checksumFlag = checksumFlag;
282 /** ZSTD_getFrameContentSize() :
283 * compatible with legacy mode
284 * @return : decompressed size of the single frame pointed to be `src` if known, otherwise
285 * - ZSTD_CONTENTSIZE_UNKNOWN if the size cannot be determined
286 * - ZSTD_CONTENTSIZE_ERROR if an error occurred (e.g. invalid magic number, srcSize too small) */
287 unsigned long long ZSTD_getFrameContentSize(const void *src, size_t srcSize)
290 ZSTD_frameParams fParams;
291 if (ZSTD_getFrameParams(&fParams, src, srcSize) != 0)
292 return ZSTD_CONTENTSIZE_ERROR;
293 if (fParams.windowSize == 0) {
294 /* Either skippable or empty frame, size == 0 either way */
296 } else if (fParams.frameContentSize != 0) {
297 return fParams.frameContentSize;
299 return ZSTD_CONTENTSIZE_UNKNOWN;
304 /** ZSTD_findDecompressedSize() :
305 * compatible with legacy mode
306 * `srcSize` must be the exact length of some number of ZSTD compressed and/or
308 * @return : decompressed size of the frames contained */
309 unsigned long long ZSTD_findDecompressedSize(const void *src, size_t srcSize)
312 unsigned long long totalDstSize = 0;
313 while (srcSize >= ZSTD_frameHeaderSize_prefix) {
314 const U32 magicNumber = ZSTD_readLE32(src);
316 if ((magicNumber & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
317 size_t skippableSize;
318 if (srcSize < ZSTD_skippableHeaderSize)
319 return ERROR(srcSize_wrong);
320 skippableSize = ZSTD_readLE32((const BYTE *)src + 4) + ZSTD_skippableHeaderSize;
321 if (srcSize < skippableSize) {
322 return ZSTD_CONTENTSIZE_ERROR;
325 src = (const BYTE *)src + skippableSize;
326 srcSize -= skippableSize;
331 unsigned long long const ret = ZSTD_getFrameContentSize(src, srcSize);
332 if (ret >= ZSTD_CONTENTSIZE_ERROR)
335 /* check for overflow */
336 if (totalDstSize + ret < totalDstSize)
337 return ZSTD_CONTENTSIZE_ERROR;
341 size_t const frameSrcSize = ZSTD_findFrameCompressedSize(src, srcSize);
342 if (ZSTD_isError(frameSrcSize)) {
343 return ZSTD_CONTENTSIZE_ERROR;
346 src = (const BYTE *)src + frameSrcSize;
347 srcSize -= frameSrcSize;
352 return ZSTD_CONTENTSIZE_ERROR;
359 /** ZSTD_decodeFrameHeader() :
360 * `headerSize` must be the size provided by ZSTD_frameHeaderSize().
361 * @return : 0 if success, or an error code, which can be tested using ZSTD_isError() */
362 static size_t ZSTD_decodeFrameHeader(ZSTD_DCtx *dctx, const void *src, size_t headerSize)
364 size_t const result = ZSTD_getFrameParams(&(dctx->fParams), src, headerSize);
365 if (ZSTD_isError(result))
366 return result; /* invalid header */
368 return ERROR(srcSize_wrong); /* headerSize too small */
369 if (dctx->fParams.dictID && (dctx->dictID != dctx->fParams.dictID))
370 return ERROR(dictionary_wrong);
371 if (dctx->fParams.checksumFlag)
372 xxh64_reset(&dctx->xxhState, 0);
377 blockType_e blockType;
382 /*! ZSTD_getcBlockSize() :
383 * Provides the size of compressed block from block header `src` */
384 size_t ZSTD_getcBlockSize(const void *src, size_t srcSize, blockProperties_t *bpPtr)
386 if (srcSize < ZSTD_blockHeaderSize)
387 return ERROR(srcSize_wrong);
389 U32 const cBlockHeader = ZSTD_readLE24(src);
390 U32 const cSize = cBlockHeader >> 3;
391 bpPtr->lastBlock = cBlockHeader & 1;
392 bpPtr->blockType = (blockType_e)((cBlockHeader >> 1) & 3);
393 bpPtr->origSize = cSize; /* only useful for RLE */
394 if (bpPtr->blockType == bt_rle)
396 if (bpPtr->blockType == bt_reserved)
397 return ERROR(corruption_detected);
402 static size_t ZSTD_copyRawBlock(void *dst, size_t dstCapacity, const void *src, size_t srcSize)
404 if (srcSize > dstCapacity)
405 return ERROR(dstSize_tooSmall);
406 memcpy(dst, src, srcSize);
410 static size_t ZSTD_setRleBlock(void *dst, size_t dstCapacity, const void *src, size_t srcSize, size_t regenSize)
413 return ERROR(srcSize_wrong);
414 if (regenSize > dstCapacity)
415 return ERROR(dstSize_tooSmall);
416 memset(dst, *(const BYTE *)src, regenSize);
420 /*! ZSTD_decodeLiteralsBlock() :
421 @return : nb of bytes read from src (< srcSize ) */
422 size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx *dctx, const void *src, size_t srcSize) /* note : srcSize < BLOCKSIZE */
424 if (srcSize < MIN_CBLOCK_SIZE)
425 return ERROR(corruption_detected);
428 const BYTE *const istart = (const BYTE *)src;
429 symbolEncodingType_e const litEncType = (symbolEncodingType_e)(istart[0] & 3);
431 switch (litEncType) {
433 if (dctx->litEntropy == 0)
434 return ERROR(dictionary_corrupted);
438 return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for case 3 */
440 size_t lhSize, litSize, litCSize;
441 U32 singleStream = 0;
442 U32 const lhlCode = (istart[0] >> 2) & 3;
443 U32 const lhc = ZSTD_readLE32(istart);
447 default: /* note : default is impossible, since lhlCode into [0..3] */
448 /* 2 - 2 - 10 - 10 */
449 singleStream = !lhlCode;
451 litSize = (lhc >> 4) & 0x3FF;
452 litCSize = (lhc >> 14) & 0x3FF;
455 /* 2 - 2 - 14 - 14 */
457 litSize = (lhc >> 4) & 0x3FFF;
458 litCSize = lhc >> 18;
461 /* 2 - 2 - 18 - 18 */
463 litSize = (lhc >> 4) & 0x3FFFF;
464 litCSize = (lhc >> 22) + (istart[4] << 10);
467 if (litSize > ZSTD_BLOCKSIZE_ABSOLUTEMAX)
468 return ERROR(corruption_detected);
469 if (litCSize + lhSize > srcSize)
470 return ERROR(corruption_detected);
473 (litEncType == set_repeat)
474 ? (singleStream ? HUF_decompress1X_usingDTable(dctx->litBuffer, litSize, istart + lhSize, litCSize, dctx->HUFptr)
475 : HUF_decompress4X_usingDTable(dctx->litBuffer, litSize, istart + lhSize, litCSize, dctx->HUFptr))
477 ? HUF_decompress1X2_DCtx_wksp(dctx->entropy.hufTable, dctx->litBuffer, litSize, istart + lhSize, litCSize,
478 dctx->entropy.workspace, sizeof(dctx->entropy.workspace))
479 : HUF_decompress4X_hufOnly_wksp(dctx->entropy.hufTable, dctx->litBuffer, litSize, istart + lhSize, litCSize,
480 dctx->entropy.workspace, sizeof(dctx->entropy.workspace)))))
481 return ERROR(corruption_detected);
483 dctx->litPtr = dctx->litBuffer;
484 dctx->litSize = litSize;
485 dctx->litEntropy = 1;
486 if (litEncType == set_compressed)
487 dctx->HUFptr = dctx->entropy.hufTable;
488 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
489 return litCSize + lhSize;
493 size_t litSize, lhSize;
494 U32 const lhlCode = ((istart[0]) >> 2) & 3;
498 default: /* note : default is impossible, since lhlCode into [0..3] */
500 litSize = istart[0] >> 3;
504 litSize = ZSTD_readLE16(istart) >> 4;
508 litSize = ZSTD_readLE24(istart) >> 4;
512 if (lhSize + litSize + WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */
513 if (litSize + lhSize > srcSize)
514 return ERROR(corruption_detected);
515 memcpy(dctx->litBuffer, istart + lhSize, litSize);
516 dctx->litPtr = dctx->litBuffer;
517 dctx->litSize = litSize;
518 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
519 return lhSize + litSize;
521 /* direct reference into compressed stream */
522 dctx->litPtr = istart + lhSize;
523 dctx->litSize = litSize;
524 return lhSize + litSize;
528 U32 const lhlCode = ((istart[0]) >> 2) & 3;
529 size_t litSize, lhSize;
533 default: /* note : default is impossible, since lhlCode into [0..3] */
535 litSize = istart[0] >> 3;
539 litSize = ZSTD_readLE16(istart) >> 4;
543 litSize = ZSTD_readLE24(istart) >> 4;
545 return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
548 if (litSize > ZSTD_BLOCKSIZE_ABSOLUTEMAX)
549 return ERROR(corruption_detected);
550 memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
551 dctx->litPtr = dctx->litBuffer;
552 dctx->litSize = litSize;
556 return ERROR(corruption_detected); /* impossible */
562 FSE_decode_t realData;
566 static const FSE_decode_t4 LL_defaultDTable[(1 << LL_DEFAULTNORMLOG) + 1] = {
567 {{LL_DEFAULTNORMLOG, 1, 1}}, /* header : tableLog, fastMode, fastMode */
568 {{0, 0, 4}}, /* 0 : base, symbol, bits */
632 }; /* LL_defaultDTable */
634 static const FSE_decode_t4 ML_defaultDTable[(1 << ML_DEFAULTNORMLOG) + 1] = {
635 {{ML_DEFAULTNORMLOG, 1, 1}}, /* header : tableLog, fastMode, fastMode */
636 {{0, 0, 6}}, /* 0 : base, symbol, bits */
700 }; /* ML_defaultDTable */
702 static const FSE_decode_t4 OF_defaultDTable[(1 << OF_DEFAULTNORMLOG) + 1] = {
703 {{OF_DEFAULTNORMLOG, 1, 1}}, /* header : tableLog, fastMode, fastMode */
704 {{0, 0, 5}}, /* 0 : base, symbol, bits */
736 }; /* OF_defaultDTable */
738 /*! ZSTD_buildSeqTable() :
739 @return : nb bytes read from src,
740 or an error code if it fails, testable with ZSTD_isError()
742 static size_t ZSTD_buildSeqTable(FSE_DTable *DTableSpace, const FSE_DTable **DTablePtr, symbolEncodingType_e type, U32 max, U32 maxLog, const void *src,
743 size_t srcSize, const FSE_decode_t4 *defaultTable, U32 flagRepeatTable, void *workspace, size_t workspaceSize)
745 const void *const tmpPtr = defaultTable; /* bypass strict aliasing */
749 return ERROR(srcSize_wrong);
750 if ((*(const BYTE *)src) > max)
751 return ERROR(corruption_detected);
752 FSE_buildDTable_rle(DTableSpace, *(const BYTE *)src);
753 *DTablePtr = DTableSpace;
755 case set_basic: *DTablePtr = (const FSE_DTable *)tmpPtr; return 0;
757 if (!flagRepeatTable)
758 return ERROR(corruption_detected);
760 default: /* impossible */
761 case set_compressed: {
763 S16 *norm = (S16 *)workspace;
764 size_t const spaceUsed32 = ALIGN(sizeof(S16) * (MaxSeq + 1), sizeof(U32)) >> 2;
766 if ((spaceUsed32 << 2) > workspaceSize)
767 return ERROR(GENERIC);
768 workspace = (U32 *)workspace + spaceUsed32;
769 workspaceSize -= (spaceUsed32 << 2);
771 size_t const headerSize = FSE_readNCount(norm, &max, &tableLog, src, srcSize);
772 if (FSE_isError(headerSize))
773 return ERROR(corruption_detected);
774 if (tableLog > maxLog)
775 return ERROR(corruption_detected);
776 FSE_buildDTable_wksp(DTableSpace, norm, max, tableLog, workspace, workspaceSize);
777 *DTablePtr = DTableSpace;
784 size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx *dctx, int *nbSeqPtr, const void *src, size_t srcSize)
786 const BYTE *const istart = (const BYTE *const)src;
787 const BYTE *const iend = istart + srcSize;
788 const BYTE *ip = istart;
791 if (srcSize < MIN_SEQUENCES_SIZE)
792 return ERROR(srcSize_wrong);
804 return ERROR(srcSize_wrong);
805 nbSeq = ZSTD_readLE16(ip) + LONGNBSEQ, ip += 2;
808 return ERROR(srcSize_wrong);
809 nbSeq = ((nbSeq - 0x80) << 8) + *ip++;
815 /* FSE table descriptors */
817 return ERROR(srcSize_wrong); /* minimum possible size */
819 symbolEncodingType_e const LLtype = (symbolEncodingType_e)(*ip >> 6);
820 symbolEncodingType_e const OFtype = (symbolEncodingType_e)((*ip >> 4) & 3);
821 symbolEncodingType_e const MLtype = (symbolEncodingType_e)((*ip >> 2) & 3);
826 size_t const llhSize = ZSTD_buildSeqTable(dctx->entropy.LLTable, &dctx->LLTptr, LLtype, MaxLL, LLFSELog, ip, iend - ip,
827 LL_defaultDTable, dctx->fseEntropy, dctx->entropy.workspace, sizeof(dctx->entropy.workspace));
828 if (ZSTD_isError(llhSize))
829 return ERROR(corruption_detected);
833 size_t const ofhSize = ZSTD_buildSeqTable(dctx->entropy.OFTable, &dctx->OFTptr, OFtype, MaxOff, OffFSELog, ip, iend - ip,
834 OF_defaultDTable, dctx->fseEntropy, dctx->entropy.workspace, sizeof(dctx->entropy.workspace));
835 if (ZSTD_isError(ofhSize))
836 return ERROR(corruption_detected);
840 size_t const mlhSize = ZSTD_buildSeqTable(dctx->entropy.MLTable, &dctx->MLTptr, MLtype, MaxML, MLFSELog, ip, iend - ip,
841 ML_defaultDTable, dctx->fseEntropy, dctx->entropy.workspace, sizeof(dctx->entropy.workspace));
842 if (ZSTD_isError(mlhSize))
843 return ERROR(corruption_detected);
859 BIT_DStream_t DStream;
860 FSE_DState_t stateLL;
861 FSE_DState_t stateOffb;
862 FSE_DState_t stateML;
863 size_t prevOffset[ZSTD_REP_NUM];
870 size_t ZSTD_execSequenceLast7(BYTE *op, BYTE *const oend, seq_t sequence, const BYTE **litPtr, const BYTE *const litLimit, const BYTE *const base,
871 const BYTE *const vBase, const BYTE *const dictEnd)
873 BYTE *const oLitEnd = op + sequence.litLength;
874 size_t const sequenceLength = sequence.litLength + sequence.matchLength;
875 BYTE *const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
876 BYTE *const oend_w = oend - WILDCOPY_OVERLENGTH;
877 const BYTE *const iLitEnd = *litPtr + sequence.litLength;
878 const BYTE *match = oLitEnd - sequence.offset;
881 if (oMatchEnd > oend)
882 return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
883 if (iLitEnd > litLimit)
884 return ERROR(corruption_detected); /* over-read beyond lit buffer */
885 if (oLitEnd <= oend_w)
886 return ERROR(GENERIC); /* Precondition */
890 ZSTD_wildcopy(op, *litPtr, oend_w - op);
891 *litPtr += oend_w - op;
895 *op++ = *(*litPtr)++;
898 if (sequence.offset > (size_t)(oLitEnd - base)) {
899 /* offset beyond prefix */
900 if (sequence.offset > (size_t)(oLitEnd - vBase))
901 return ERROR(corruption_detected);
902 match = dictEnd - (base - match);
903 if (match + sequence.matchLength <= dictEnd) {
904 memmove(oLitEnd, match, sequence.matchLength);
905 return sequenceLength;
907 /* span extDict & currPrefixSegment */
909 size_t const length1 = dictEnd - match;
910 memmove(oLitEnd, match, length1);
911 op = oLitEnd + length1;
912 sequence.matchLength -= length1;
916 while (op < oMatchEnd)
918 return sequenceLength;
921 static seq_t ZSTD_decodeSequence(seqState_t *seqState)
925 U32 const llCode = FSE_peekSymbol(&seqState->stateLL);
926 U32 const mlCode = FSE_peekSymbol(&seqState->stateML);
927 U32 const ofCode = FSE_peekSymbol(&seqState->stateOffb); /* <= maxOff, by table construction */
929 U32 const llBits = LL_bits[llCode];
930 U32 const mlBits = ML_bits[mlCode];
931 U32 const ofBits = ofCode;
932 U32 const totalBits = llBits + mlBits + ofBits;
934 static const U32 LL_base[MaxLL + 1] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18,
935 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000};
937 static const U32 ML_base[MaxML + 1] = {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
938 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 39, 41,
939 43, 47, 51, 59, 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803, 0x1003, 0x2003, 0x4003, 0x8003, 0x10003};
941 static const U32 OF_base[MaxOff + 1] = {0, 1, 1, 5, 0xD, 0x1D, 0x3D, 0x7D, 0xFD, 0x1FD,
942 0x3FD, 0x7FD, 0xFFD, 0x1FFD, 0x3FFD, 0x7FFD, 0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD,
943 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD, 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD};
951 offset = OF_base[ofCode] + BIT_readBitsFast(&seqState->DStream, ofBits); /* <= (ZSTD_WINDOWLOG_MAX-1) bits */
953 BIT_reloadDStream(&seqState->DStream);
957 offset += (llCode == 0);
959 size_t temp = (offset == 3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
960 temp += !temp; /* 0 is not valid; input is corrupted; force offset to 1 */
962 seqState->prevOffset[2] = seqState->prevOffset[1];
963 seqState->prevOffset[1] = seqState->prevOffset[0];
964 seqState->prevOffset[0] = offset = temp;
966 offset = seqState->prevOffset[0];
969 seqState->prevOffset[2] = seqState->prevOffset[1];
970 seqState->prevOffset[1] = seqState->prevOffset[0];
971 seqState->prevOffset[0] = offset;
976 seq.matchLength = ML_base[mlCode] + ((mlCode > 31) ? BIT_readBitsFast(&seqState->DStream, mlBits) : 0); /* <= 16 bits */
977 if (ZSTD_32bits() && (mlBits + llBits > 24))
978 BIT_reloadDStream(&seqState->DStream);
980 seq.litLength = LL_base[llCode] + ((llCode > 15) ? BIT_readBitsFast(&seqState->DStream, llBits) : 0); /* <= 16 bits */
981 if (ZSTD_32bits() || (totalBits > 64 - 7 - (LLFSELog + MLFSELog + OffFSELog)))
982 BIT_reloadDStream(&seqState->DStream);
984 /* ANS state update */
985 FSE_updateState(&seqState->stateLL, &seqState->DStream); /* <= 9 bits */
986 FSE_updateState(&seqState->stateML, &seqState->DStream); /* <= 9 bits */
988 BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */
989 FSE_updateState(&seqState->stateOffb, &seqState->DStream); /* <= 8 bits */
997 size_t ZSTD_execSequence(BYTE *op, BYTE *const oend, seq_t sequence, const BYTE **litPtr, const BYTE *const litLimit, const BYTE *const base,
998 const BYTE *const vBase, const BYTE *const dictEnd)
1000 BYTE *const oLitEnd = op + sequence.litLength;
1001 size_t const sequenceLength = sequence.litLength + sequence.matchLength;
1002 BYTE *const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
1003 BYTE *const oend_w = oend - WILDCOPY_OVERLENGTH;
1004 const BYTE *const iLitEnd = *litPtr + sequence.litLength;
1005 const BYTE *match = oLitEnd - sequence.offset;
1008 if (oMatchEnd > oend)
1009 return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
1010 if (iLitEnd > litLimit)
1011 return ERROR(corruption_detected); /* over-read beyond lit buffer */
1012 if (oLitEnd > oend_w)
1013 return ZSTD_execSequenceLast7(op, oend, sequence, litPtr, litLimit, base, vBase, dictEnd);
1016 ZSTD_copy8(op, *litPtr);
1017 if (sequence.litLength > 8)
1018 ZSTD_wildcopy(op + 8, (*litPtr) + 8,
1019 sequence.litLength - 8); /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
1021 *litPtr = iLitEnd; /* update for next sequence */
1024 if (sequence.offset > (size_t)(oLitEnd - base)) {
1025 /* offset beyond prefix */
1026 if (sequence.offset > (size_t)(oLitEnd - vBase))
1027 return ERROR(corruption_detected);
1028 match = dictEnd + (match - base);
1029 if (match + sequence.matchLength <= dictEnd) {
1030 memmove(oLitEnd, match, sequence.matchLength);
1031 return sequenceLength;
1033 /* span extDict & currPrefixSegment */
1035 size_t const length1 = dictEnd - match;
1036 memmove(oLitEnd, match, length1);
1037 op = oLitEnd + length1;
1038 sequence.matchLength -= length1;
1040 if (op > oend_w || sequence.matchLength < MINMATCH) {
1042 for (i = 0; i < sequence.matchLength; ++i)
1044 return sequenceLength;
1048 /* Requirement: op <= oend_w && sequence.matchLength >= MINMATCH */
1050 /* match within prefix */
1051 if (sequence.offset < 8) {
1052 /* close range match, overlap */
1053 static const U32 dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4}; /* added */
1054 static const int dec64table[] = {8, 8, 8, 7, 8, 9, 10, 11}; /* subtracted */
1055 int const sub2 = dec64table[sequence.offset];
1060 match += dec32table[sequence.offset];
1061 ZSTD_copy4(op + 4, match);
1064 ZSTD_copy8(op, match);
1069 if (oMatchEnd > oend - (16 - MINMATCH)) {
1071 ZSTD_wildcopy(op, match, oend_w - op);
1072 match += oend_w - op;
1075 while (op < oMatchEnd)
1078 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength - 8); /* works even if matchLength < 8 */
1080 return sequenceLength;
1083 static size_t ZSTD_decompressSequences(ZSTD_DCtx *dctx, void *dst, size_t maxDstSize, const void *seqStart, size_t seqSize)
1085 const BYTE *ip = (const BYTE *)seqStart;
1086 const BYTE *const iend = ip + seqSize;
1087 BYTE *const ostart = (BYTE * const)dst;
1088 BYTE *const oend = ostart + maxDstSize;
1090 const BYTE *litPtr = dctx->litPtr;
1091 const BYTE *const litEnd = litPtr + dctx->litSize;
1092 const BYTE *const base = (const BYTE *)(dctx->base);
1093 const BYTE *const vBase = (const BYTE *)(dctx->vBase);
1094 const BYTE *const dictEnd = (const BYTE *)(dctx->dictEnd);
1097 /* Build Decoding Tables */
1099 size_t const seqHSize = ZSTD_decodeSeqHeaders(dctx, &nbSeq, ip, seqSize);
1100 if (ZSTD_isError(seqHSize))
1105 /* Regen sequences */
1107 seqState_t seqState;
1108 dctx->fseEntropy = 1;
1111 for (i = 0; i < ZSTD_REP_NUM; i++)
1112 seqState.prevOffset[i] = dctx->entropy.rep[i];
1114 CHECK_E(BIT_initDStream(&seqState.DStream, ip, iend - ip), corruption_detected);
1115 FSE_initDState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
1116 FSE_initDState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
1117 FSE_initDState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
1119 for (; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && nbSeq;) {
1122 seq_t const sequence = ZSTD_decodeSequence(&seqState);
1123 size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd);
1124 if (ZSTD_isError(oneSeqSize))
1130 /* check if reached exact end */
1132 return ERROR(corruption_detected);
1133 /* save reps for next block */
1136 for (i = 0; i < ZSTD_REP_NUM; i++)
1137 dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]);
1141 /* last literal segment */
1143 size_t const lastLLSize = litEnd - litPtr;
1144 if (lastLLSize > (size_t)(oend - op))
1145 return ERROR(dstSize_tooSmall);
1146 memcpy(op, litPtr, lastLLSize);
1153 FORCE_INLINE seq_t ZSTD_decodeSequenceLong_generic(seqState_t *seqState, int const longOffsets)
1157 U32 const llCode = FSE_peekSymbol(&seqState->stateLL);
1158 U32 const mlCode = FSE_peekSymbol(&seqState->stateML);
1159 U32 const ofCode = FSE_peekSymbol(&seqState->stateOffb); /* <= maxOff, by table construction */
1161 U32 const llBits = LL_bits[llCode];
1162 U32 const mlBits = ML_bits[mlCode];
1163 U32 const ofBits = ofCode;
1164 U32 const totalBits = llBits + mlBits + ofBits;
1166 static const U32 LL_base[MaxLL + 1] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18,
1167 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000};
1169 static const U32 ML_base[MaxML + 1] = {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
1170 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 39, 41,
1171 43, 47, 51, 59, 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803, 0x1003, 0x2003, 0x4003, 0x8003, 0x10003};
1173 static const U32 OF_base[MaxOff + 1] = {0, 1, 1, 5, 0xD, 0x1D, 0x3D, 0x7D, 0xFD, 0x1FD,
1174 0x3FD, 0x7FD, 0xFFD, 0x1FFD, 0x3FFD, 0x7FFD, 0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD,
1175 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD, 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD};
1184 int const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN);
1185 offset = OF_base[ofCode] + (BIT_readBitsFast(&seqState->DStream, ofBits - extraBits) << extraBits);
1186 if (ZSTD_32bits() || extraBits)
1187 BIT_reloadDStream(&seqState->DStream);
1189 offset += BIT_readBitsFast(&seqState->DStream, extraBits);
1191 offset = OF_base[ofCode] + BIT_readBitsFast(&seqState->DStream, ofBits); /* <= (ZSTD_WINDOWLOG_MAX-1) bits */
1193 BIT_reloadDStream(&seqState->DStream);
1198 offset += (llCode == 0);
1200 size_t temp = (offset == 3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
1201 temp += !temp; /* 0 is not valid; input is corrupted; force offset to 1 */
1203 seqState->prevOffset[2] = seqState->prevOffset[1];
1204 seqState->prevOffset[1] = seqState->prevOffset[0];
1205 seqState->prevOffset[0] = offset = temp;
1207 offset = seqState->prevOffset[0];
1210 seqState->prevOffset[2] = seqState->prevOffset[1];
1211 seqState->prevOffset[1] = seqState->prevOffset[0];
1212 seqState->prevOffset[0] = offset;
1214 seq.offset = offset;
1217 seq.matchLength = ML_base[mlCode] + ((mlCode > 31) ? BIT_readBitsFast(&seqState->DStream, mlBits) : 0); /* <= 16 bits */
1218 if (ZSTD_32bits() && (mlBits + llBits > 24))
1219 BIT_reloadDStream(&seqState->DStream);
1221 seq.litLength = LL_base[llCode] + ((llCode > 15) ? BIT_readBitsFast(&seqState->DStream, llBits) : 0); /* <= 16 bits */
1222 if (ZSTD_32bits() || (totalBits > 64 - 7 - (LLFSELog + MLFSELog + OffFSELog)))
1223 BIT_reloadDStream(&seqState->DStream);
1226 size_t const pos = seqState->pos + seq.litLength;
1227 seq.match = seqState->base + pos - seq.offset; /* single memory segment */
1228 if (seq.offset > pos)
1229 seq.match += seqState->gotoDict; /* separate memory segment */
1230 seqState->pos = pos + seq.matchLength;
1233 /* ANS state update */
1234 FSE_updateState(&seqState->stateLL, &seqState->DStream); /* <= 9 bits */
1235 FSE_updateState(&seqState->stateML, &seqState->DStream); /* <= 9 bits */
1237 BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */
1238 FSE_updateState(&seqState->stateOffb, &seqState->DStream); /* <= 8 bits */
1243 static seq_t ZSTD_decodeSequenceLong(seqState_t *seqState, unsigned const windowSize)
1245 if (ZSTD_highbit32(windowSize) > STREAM_ACCUMULATOR_MIN) {
1246 return ZSTD_decodeSequenceLong_generic(seqState, 1);
1248 return ZSTD_decodeSequenceLong_generic(seqState, 0);
1253 size_t ZSTD_execSequenceLong(BYTE *op, BYTE *const oend, seq_t sequence, const BYTE **litPtr, const BYTE *const litLimit, const BYTE *const base,
1254 const BYTE *const vBase, const BYTE *const dictEnd)
1256 BYTE *const oLitEnd = op + sequence.litLength;
1257 size_t const sequenceLength = sequence.litLength + sequence.matchLength;
1258 BYTE *const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
1259 BYTE *const oend_w = oend - WILDCOPY_OVERLENGTH;
1260 const BYTE *const iLitEnd = *litPtr + sequence.litLength;
1261 const BYTE *match = sequence.match;
1264 if (oMatchEnd > oend)
1265 return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
1266 if (iLitEnd > litLimit)
1267 return ERROR(corruption_detected); /* over-read beyond lit buffer */
1268 if (oLitEnd > oend_w)
1269 return ZSTD_execSequenceLast7(op, oend, sequence, litPtr, litLimit, base, vBase, dictEnd);
1272 ZSTD_copy8(op, *litPtr);
1273 if (sequence.litLength > 8)
1274 ZSTD_wildcopy(op + 8, (*litPtr) + 8,
1275 sequence.litLength - 8); /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
1277 *litPtr = iLitEnd; /* update for next sequence */
1280 if (sequence.offset > (size_t)(oLitEnd - base)) {
1281 /* offset beyond prefix */
1282 if (sequence.offset > (size_t)(oLitEnd - vBase))
1283 return ERROR(corruption_detected);
1284 if (match + sequence.matchLength <= dictEnd) {
1285 memmove(oLitEnd, match, sequence.matchLength);
1286 return sequenceLength;
1288 /* span extDict & currPrefixSegment */
1290 size_t const length1 = dictEnd - match;
1291 memmove(oLitEnd, match, length1);
1292 op = oLitEnd + length1;
1293 sequence.matchLength -= length1;
1295 if (op > oend_w || sequence.matchLength < MINMATCH) {
1297 for (i = 0; i < sequence.matchLength; ++i)
1299 return sequenceLength;
1303 /* Requirement: op <= oend_w && sequence.matchLength >= MINMATCH */
1305 /* match within prefix */
1306 if (sequence.offset < 8) {
1307 /* close range match, overlap */
1308 static const U32 dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4}; /* added */
1309 static const int dec64table[] = {8, 8, 8, 7, 8, 9, 10, 11}; /* subtracted */
1310 int const sub2 = dec64table[sequence.offset];
1315 match += dec32table[sequence.offset];
1316 ZSTD_copy4(op + 4, match);
1319 ZSTD_copy8(op, match);
1324 if (oMatchEnd > oend - (16 - MINMATCH)) {
1326 ZSTD_wildcopy(op, match, oend_w - op);
1327 match += oend_w - op;
1330 while (op < oMatchEnd)
1333 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength - 8); /* works even if matchLength < 8 */
1335 return sequenceLength;
1338 static size_t ZSTD_decompressSequencesLong(ZSTD_DCtx *dctx, void *dst, size_t maxDstSize, const void *seqStart, size_t seqSize)
1340 const BYTE *ip = (const BYTE *)seqStart;
1341 const BYTE *const iend = ip + seqSize;
1342 BYTE *const ostart = (BYTE * const)dst;
1343 BYTE *const oend = ostart + maxDstSize;
1345 const BYTE *litPtr = dctx->litPtr;
1346 const BYTE *const litEnd = litPtr + dctx->litSize;
1347 const BYTE *const base = (const BYTE *)(dctx->base);
1348 const BYTE *const vBase = (const BYTE *)(dctx->vBase);
1349 const BYTE *const dictEnd = (const BYTE *)(dctx->dictEnd);
1350 unsigned const windowSize = dctx->fParams.windowSize;
1353 /* Build Decoding Tables */
1355 size_t const seqHSize = ZSTD_decodeSeqHeaders(dctx, &nbSeq, ip, seqSize);
1356 if (ZSTD_isError(seqHSize))
1361 /* Regen sequences */
1363 #define STORED_SEQS 4
1364 #define STOSEQ_MASK (STORED_SEQS - 1)
1365 #define ADVANCED_SEQS 4
1366 seq_t *sequences = (seq_t *)dctx->entropy.workspace;
1367 int const seqAdvance = MIN(nbSeq, ADVANCED_SEQS);
1368 seqState_t seqState;
1370 ZSTD_STATIC_ASSERT(sizeof(dctx->entropy.workspace) >= sizeof(seq_t) * STORED_SEQS);
1371 dctx->fseEntropy = 1;
1374 for (i = 0; i < ZSTD_REP_NUM; i++)
1375 seqState.prevOffset[i] = dctx->entropy.rep[i];
1377 seqState.base = base;
1378 seqState.pos = (size_t)(op - base);
1379 seqState.gotoDict = (uPtrDiff)dictEnd - (uPtrDiff)base; /* cast to avoid undefined behaviour */
1380 CHECK_E(BIT_initDStream(&seqState.DStream, ip, iend - ip), corruption_detected);
1381 FSE_initDState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
1382 FSE_initDState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
1383 FSE_initDState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
1385 /* prepare in advance */
1386 for (seqNb = 0; (BIT_reloadDStream(&seqState.DStream) <= BIT_DStream_completed) && seqNb < seqAdvance; seqNb++) {
1387 sequences[seqNb] = ZSTD_decodeSequenceLong(&seqState, windowSize);
1389 if (seqNb < seqAdvance)
1390 return ERROR(corruption_detected);
1392 /* decode and decompress */
1393 for (; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && seqNb < nbSeq; seqNb++) {
1394 seq_t const sequence = ZSTD_decodeSequenceLong(&seqState, windowSize);
1395 size_t const oneSeqSize =
1396 ZSTD_execSequenceLong(op, oend, sequences[(seqNb - ADVANCED_SEQS) & STOSEQ_MASK], &litPtr, litEnd, base, vBase, dictEnd);
1397 if (ZSTD_isError(oneSeqSize))
1399 ZSTD_PREFETCH(sequence.match);
1400 sequences[seqNb & STOSEQ_MASK] = sequence;
1404 return ERROR(corruption_detected);
1407 seqNb -= seqAdvance;
1408 for (; seqNb < nbSeq; seqNb++) {
1409 size_t const oneSeqSize = ZSTD_execSequenceLong(op, oend, sequences[seqNb & STOSEQ_MASK], &litPtr, litEnd, base, vBase, dictEnd);
1410 if (ZSTD_isError(oneSeqSize))
1415 /* save reps for next block */
1418 for (i = 0; i < ZSTD_REP_NUM; i++)
1419 dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]);
1423 /* last literal segment */
1425 size_t const lastLLSize = litEnd - litPtr;
1426 if (lastLLSize > (size_t)(oend - op))
1427 return ERROR(dstSize_tooSmall);
1428 memcpy(op, litPtr, lastLLSize);
1435 static size_t ZSTD_decompressBlock_internal(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
1436 { /* blockType == blockCompressed */
1437 const BYTE *ip = (const BYTE *)src;
1439 if (srcSize >= ZSTD_BLOCKSIZE_ABSOLUTEMAX)
1440 return ERROR(srcSize_wrong);
1442 /* Decode literals section */
1444 size_t const litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize);
1445 if (ZSTD_isError(litCSize))
1448 srcSize -= litCSize;
1450 if (sizeof(size_t) > 4) /* do not enable prefetching on 32-bits x86, as it's performance detrimental */
1451 /* likely because of register pressure */
1452 /* if that's the correct cause, then 32-bits ARM should be affected differently */
1453 /* it would be good to test this on ARM real hardware, to see if prefetch version improves speed */
1454 if (dctx->fParams.windowSize > (1 << 23))
1455 return ZSTD_decompressSequencesLong(dctx, dst, dstCapacity, ip, srcSize);
1456 return ZSTD_decompressSequences(dctx, dst, dstCapacity, ip, srcSize);
1459 static void ZSTD_checkContinuity(ZSTD_DCtx *dctx, const void *dst)
1461 if (dst != dctx->previousDstEnd) { /* not contiguous */
1462 dctx->dictEnd = dctx->previousDstEnd;
1463 dctx->vBase = (const char *)dst - ((const char *)(dctx->previousDstEnd) - (const char *)(dctx->base));
1465 dctx->previousDstEnd = dst;
1469 size_t ZSTD_decompressBlock(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
1472 ZSTD_checkContinuity(dctx, dst);
1473 dSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
1474 dctx->previousDstEnd = (char *)dst + dSize;
1478 /** ZSTD_insertBlock() :
1479 insert `src` block into `dctx` history. Useful to track uncompressed blocks. */
1480 size_t ZSTD_insertBlock(ZSTD_DCtx *dctx, const void *blockStart, size_t blockSize)
1482 ZSTD_checkContinuity(dctx, blockStart);
1483 dctx->previousDstEnd = (const char *)blockStart + blockSize;
1487 size_t ZSTD_generateNxBytes(void *dst, size_t dstCapacity, BYTE byte, size_t length)
1489 if (length > dstCapacity)
1490 return ERROR(dstSize_tooSmall);
1491 memset(dst, byte, length);
1495 /** ZSTD_findFrameCompressedSize() :
1496 * compatible with legacy mode
1497 * `src` must point to the start of a ZSTD frame, ZSTD legacy frame, or skippable frame
1498 * `srcSize` must be at least as large as the frame contained
1499 * @return : the compressed size of the frame starting at `src` */
1500 size_t ZSTD_findFrameCompressedSize(const void *src, size_t srcSize)
1502 if (srcSize >= ZSTD_skippableHeaderSize && (ZSTD_readLE32(src) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
1503 return ZSTD_skippableHeaderSize + ZSTD_readLE32((const BYTE *)src + 4);
1505 const BYTE *ip = (const BYTE *)src;
1506 const BYTE *const ipstart = ip;
1507 size_t remainingSize = srcSize;
1508 ZSTD_frameParams fParams;
1510 size_t const headerSize = ZSTD_frameHeaderSize(ip, remainingSize);
1511 if (ZSTD_isError(headerSize))
1516 size_t const ret = ZSTD_getFrameParams(&fParams, ip, remainingSize);
1517 if (ZSTD_isError(ret))
1520 return ERROR(srcSize_wrong);
1524 remainingSize -= headerSize;
1526 /* Loop on each block */
1528 blockProperties_t blockProperties;
1529 size_t const cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
1530 if (ZSTD_isError(cBlockSize))
1533 if (ZSTD_blockHeaderSize + cBlockSize > remainingSize)
1534 return ERROR(srcSize_wrong);
1536 ip += ZSTD_blockHeaderSize + cBlockSize;
1537 remainingSize -= ZSTD_blockHeaderSize + cBlockSize;
1539 if (blockProperties.lastBlock)
1543 if (fParams.checksumFlag) { /* Frame content checksum */
1544 if (remainingSize < 4)
1545 return ERROR(srcSize_wrong);
1550 return ip - ipstart;
1554 /*! ZSTD_decompressFrame() :
1555 * @dctx must be properly initialized */
1556 static size_t ZSTD_decompressFrame(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void **srcPtr, size_t *srcSizePtr)
1558 const BYTE *ip = (const BYTE *)(*srcPtr);
1559 BYTE *const ostart = (BYTE * const)dst;
1560 BYTE *const oend = ostart + dstCapacity;
1562 size_t remainingSize = *srcSizePtr;
1565 if (remainingSize < ZSTD_frameHeaderSize_min + ZSTD_blockHeaderSize)
1566 return ERROR(srcSize_wrong);
1570 size_t const frameHeaderSize = ZSTD_frameHeaderSize(ip, ZSTD_frameHeaderSize_prefix);
1571 if (ZSTD_isError(frameHeaderSize))
1572 return frameHeaderSize;
1573 if (remainingSize < frameHeaderSize + ZSTD_blockHeaderSize)
1574 return ERROR(srcSize_wrong);
1575 CHECK_F(ZSTD_decodeFrameHeader(dctx, ip, frameHeaderSize));
1576 ip += frameHeaderSize;
1577 remainingSize -= frameHeaderSize;
1580 /* Loop on each block */
1583 blockProperties_t blockProperties;
1584 size_t const cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
1585 if (ZSTD_isError(cBlockSize))
1588 ip += ZSTD_blockHeaderSize;
1589 remainingSize -= ZSTD_blockHeaderSize;
1590 if (cBlockSize > remainingSize)
1591 return ERROR(srcSize_wrong);
1593 switch (blockProperties.blockType) {
1594 case bt_compressed: decodedSize = ZSTD_decompressBlock_internal(dctx, op, oend - op, ip, cBlockSize); break;
1595 case bt_raw: decodedSize = ZSTD_copyRawBlock(op, oend - op, ip, cBlockSize); break;
1596 case bt_rle: decodedSize = ZSTD_generateNxBytes(op, oend - op, *ip, blockProperties.origSize); break;
1598 default: return ERROR(corruption_detected);
1601 if (ZSTD_isError(decodedSize))
1603 if (dctx->fParams.checksumFlag)
1604 xxh64_update(&dctx->xxhState, op, decodedSize);
1607 remainingSize -= cBlockSize;
1608 if (blockProperties.lastBlock)
1612 if (dctx->fParams.checksumFlag) { /* Frame content checksum verification */
1613 U32 const checkCalc = (U32)xxh64_digest(&dctx->xxhState);
1615 if (remainingSize < 4)
1616 return ERROR(checksum_wrong);
1617 checkRead = ZSTD_readLE32(ip);
1618 if (checkRead != checkCalc)
1619 return ERROR(checksum_wrong);
1624 /* Allow caller to get size read */
1626 *srcSizePtr = remainingSize;
1630 static const void *ZSTD_DDictDictContent(const ZSTD_DDict *ddict);
1631 static size_t ZSTD_DDictDictSize(const ZSTD_DDict *ddict);
1633 static size_t ZSTD_decompressMultiFrame(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const void *dict, size_t dictSize,
1634 const ZSTD_DDict *ddict)
1636 void *const dststart = dst;
1640 /* programmer error, these two cases should be mutually exclusive */
1641 return ERROR(GENERIC);
1644 dict = ZSTD_DDictDictContent(ddict);
1645 dictSize = ZSTD_DDictDictSize(ddict);
1648 while (srcSize >= ZSTD_frameHeaderSize_prefix) {
1651 magicNumber = ZSTD_readLE32(src);
1652 if (magicNumber != ZSTD_MAGICNUMBER) {
1653 if ((magicNumber & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
1654 size_t skippableSize;
1655 if (srcSize < ZSTD_skippableHeaderSize)
1656 return ERROR(srcSize_wrong);
1657 skippableSize = ZSTD_readLE32((const BYTE *)src + 4) + ZSTD_skippableHeaderSize;
1658 if (srcSize < skippableSize) {
1659 return ERROR(srcSize_wrong);
1662 src = (const BYTE *)src + skippableSize;
1663 srcSize -= skippableSize;
1666 return ERROR(prefix_unknown);
1671 /* we were called from ZSTD_decompress_usingDDict */
1672 ZSTD_refDDict(dctx, ddict);
1674 /* this will initialize correctly with no dict if dict == NULL, so
1675 * use this in all cases but ddict */
1676 CHECK_F(ZSTD_decompressBegin_usingDict(dctx, dict, dictSize));
1678 ZSTD_checkContinuity(dctx, dst);
1681 const size_t res = ZSTD_decompressFrame(dctx, dst, dstCapacity, &src, &srcSize);
1682 if (ZSTD_isError(res))
1684 /* don't need to bounds check this, ZSTD_decompressFrame will have
1686 dst = (BYTE *)dst + res;
1692 return ERROR(srcSize_wrong); /* input not entirely consumed */
1694 return (BYTE *)dst - (BYTE *)dststart;
1697 size_t ZSTD_decompress_usingDict(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const void *dict, size_t dictSize)
1699 return ZSTD_decompressMultiFrame(dctx, dst, dstCapacity, src, srcSize, dict, dictSize, NULL);
1702 size_t ZSTD_decompressDCtx(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
1704 return ZSTD_decompress_usingDict(dctx, dst, dstCapacity, src, srcSize, NULL, 0);
1707 /*-**************************************
1708 * Advanced Streaming Decompression API
1709 * Bufferless and synchronous
1710 ****************************************/
1711 size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx *dctx) { return dctx->expected; }
1713 ZSTD_nextInputType_e ZSTD_nextInputType(ZSTD_DCtx *dctx)
1715 switch (dctx->stage) {
1716 default: /* should not happen */
1717 case ZSTDds_getFrameHeaderSize:
1718 case ZSTDds_decodeFrameHeader: return ZSTDnit_frameHeader;
1719 case ZSTDds_decodeBlockHeader: return ZSTDnit_blockHeader;
1720 case ZSTDds_decompressBlock: return ZSTDnit_block;
1721 case ZSTDds_decompressLastBlock: return ZSTDnit_lastBlock;
1722 case ZSTDds_checkChecksum: return ZSTDnit_checksum;
1723 case ZSTDds_decodeSkippableHeader:
1724 case ZSTDds_skipFrame: return ZSTDnit_skippableFrame;
1728 int ZSTD_isSkipFrame(ZSTD_DCtx *dctx) { return dctx->stage == ZSTDds_skipFrame; } /* for zbuff */
1730 /** ZSTD_decompressContinue() :
1731 * @return : nb of bytes generated into `dst` (necessarily <= `dstCapacity)
1732 * or an error code, which can be tested using ZSTD_isError() */
1733 size_t ZSTD_decompressContinue(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
1736 if (srcSize != dctx->expected)
1737 return ERROR(srcSize_wrong);
1739 ZSTD_checkContinuity(dctx, dst);
1741 switch (dctx->stage) {
1742 case ZSTDds_getFrameHeaderSize:
1743 if (srcSize != ZSTD_frameHeaderSize_prefix)
1744 return ERROR(srcSize_wrong); /* impossible */
1745 if ((ZSTD_readLE32(src) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) { /* skippable frame */
1746 memcpy(dctx->headerBuffer, src, ZSTD_frameHeaderSize_prefix);
1747 dctx->expected = ZSTD_skippableHeaderSize - ZSTD_frameHeaderSize_prefix; /* magic number + skippable frame length */
1748 dctx->stage = ZSTDds_decodeSkippableHeader;
1751 dctx->headerSize = ZSTD_frameHeaderSize(src, ZSTD_frameHeaderSize_prefix);
1752 if (ZSTD_isError(dctx->headerSize))
1753 return dctx->headerSize;
1754 memcpy(dctx->headerBuffer, src, ZSTD_frameHeaderSize_prefix);
1755 if (dctx->headerSize > ZSTD_frameHeaderSize_prefix) {
1756 dctx->expected = dctx->headerSize - ZSTD_frameHeaderSize_prefix;
1757 dctx->stage = ZSTDds_decodeFrameHeader;
1760 dctx->expected = 0; /* not necessary to copy more */
1762 case ZSTDds_decodeFrameHeader:
1763 memcpy(dctx->headerBuffer + ZSTD_frameHeaderSize_prefix, src, dctx->expected);
1764 CHECK_F(ZSTD_decodeFrameHeader(dctx, dctx->headerBuffer, dctx->headerSize));
1765 dctx->expected = ZSTD_blockHeaderSize;
1766 dctx->stage = ZSTDds_decodeBlockHeader;
1769 case ZSTDds_decodeBlockHeader: {
1770 blockProperties_t bp;
1771 size_t const cBlockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
1772 if (ZSTD_isError(cBlockSize))
1774 dctx->expected = cBlockSize;
1775 dctx->bType = bp.blockType;
1776 dctx->rleSize = bp.origSize;
1778 dctx->stage = bp.lastBlock ? ZSTDds_decompressLastBlock : ZSTDds_decompressBlock;
1783 if (dctx->fParams.checksumFlag) {
1785 dctx->stage = ZSTDds_checkChecksum;
1787 dctx->expected = 0; /* end of frame */
1788 dctx->stage = ZSTDds_getFrameHeaderSize;
1791 dctx->expected = 3; /* go directly to next header */
1792 dctx->stage = ZSTDds_decodeBlockHeader;
1796 case ZSTDds_decompressLastBlock:
1797 case ZSTDds_decompressBlock: {
1799 switch (dctx->bType) {
1800 case bt_compressed: rSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize); break;
1801 case bt_raw: rSize = ZSTD_copyRawBlock(dst, dstCapacity, src, srcSize); break;
1802 case bt_rle: rSize = ZSTD_setRleBlock(dst, dstCapacity, src, srcSize, dctx->rleSize); break;
1803 case bt_reserved: /* should never happen */
1804 default: return ERROR(corruption_detected);
1806 if (ZSTD_isError(rSize))
1808 if (dctx->fParams.checksumFlag)
1809 xxh64_update(&dctx->xxhState, dst, rSize);
1811 if (dctx->stage == ZSTDds_decompressLastBlock) { /* end of frame */
1812 if (dctx->fParams.checksumFlag) { /* another round for frame checksum */
1814 dctx->stage = ZSTDds_checkChecksum;
1816 dctx->expected = 0; /* ends here */
1817 dctx->stage = ZSTDds_getFrameHeaderSize;
1820 dctx->stage = ZSTDds_decodeBlockHeader;
1821 dctx->expected = ZSTD_blockHeaderSize;
1822 dctx->previousDstEnd = (char *)dst + rSize;
1826 case ZSTDds_checkChecksum: {
1827 U32 const h32 = (U32)xxh64_digest(&dctx->xxhState);
1828 U32 const check32 = ZSTD_readLE32(src); /* srcSize == 4, guaranteed by dctx->expected */
1830 return ERROR(checksum_wrong);
1832 dctx->stage = ZSTDds_getFrameHeaderSize;
1835 case ZSTDds_decodeSkippableHeader: {
1836 memcpy(dctx->headerBuffer + ZSTD_frameHeaderSize_prefix, src, dctx->expected);
1837 dctx->expected = ZSTD_readLE32(dctx->headerBuffer + 4);
1838 dctx->stage = ZSTDds_skipFrame;
1841 case ZSTDds_skipFrame: {
1843 dctx->stage = ZSTDds_getFrameHeaderSize;
1847 return ERROR(GENERIC); /* impossible */
1851 static size_t ZSTD_refDictContent(ZSTD_DCtx *dctx, const void *dict, size_t dictSize)
1853 dctx->dictEnd = dctx->previousDstEnd;
1854 dctx->vBase = (const char *)dict - ((const char *)(dctx->previousDstEnd) - (const char *)(dctx->base));
1856 dctx->previousDstEnd = (const char *)dict + dictSize;
1860 /* ZSTD_loadEntropy() :
1861 * dict : must point at beginning of a valid zstd dictionary
1862 * @return : size of entropy tables read */
1863 static size_t ZSTD_loadEntropy(ZSTD_entropyTables_t *entropy, const void *const dict, size_t const dictSize)
1865 const BYTE *dictPtr = (const BYTE *)dict;
1866 const BYTE *const dictEnd = dictPtr + dictSize;
1869 return ERROR(dictionary_corrupted);
1870 dictPtr += 8; /* skip header = magic + dictID */
1873 size_t const hSize = HUF_readDTableX4_wksp(entropy->hufTable, dictPtr, dictEnd - dictPtr, entropy->workspace, sizeof(entropy->workspace));
1874 if (HUF_isError(hSize))
1875 return ERROR(dictionary_corrupted);
1880 short offcodeNCount[MaxOff + 1];
1881 U32 offcodeMaxValue = MaxOff, offcodeLog;
1882 size_t const offcodeHeaderSize = FSE_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dictPtr, dictEnd - dictPtr);
1883 if (FSE_isError(offcodeHeaderSize))
1884 return ERROR(dictionary_corrupted);
1885 if (offcodeLog > OffFSELog)
1886 return ERROR(dictionary_corrupted);
1887 CHECK_E(FSE_buildDTable_wksp(entropy->OFTable, offcodeNCount, offcodeMaxValue, offcodeLog, entropy->workspace, sizeof(entropy->workspace)), dictionary_corrupted);
1888 dictPtr += offcodeHeaderSize;
1892 short matchlengthNCount[MaxML + 1];
1893 unsigned matchlengthMaxValue = MaxML, matchlengthLog;
1894 size_t const matchlengthHeaderSize = FSE_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd - dictPtr);
1895 if (FSE_isError(matchlengthHeaderSize))
1896 return ERROR(dictionary_corrupted);
1897 if (matchlengthLog > MLFSELog)
1898 return ERROR(dictionary_corrupted);
1899 CHECK_E(FSE_buildDTable_wksp(entropy->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog, entropy->workspace, sizeof(entropy->workspace)), dictionary_corrupted);
1900 dictPtr += matchlengthHeaderSize;
1904 short litlengthNCount[MaxLL + 1];
1905 unsigned litlengthMaxValue = MaxLL, litlengthLog;
1906 size_t const litlengthHeaderSize = FSE_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd - dictPtr);
1907 if (FSE_isError(litlengthHeaderSize))
1908 return ERROR(dictionary_corrupted);
1909 if (litlengthLog > LLFSELog)
1910 return ERROR(dictionary_corrupted);
1911 CHECK_E(FSE_buildDTable_wksp(entropy->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog, entropy->workspace, sizeof(entropy->workspace)), dictionary_corrupted);
1912 dictPtr += litlengthHeaderSize;
1915 if (dictPtr + 12 > dictEnd)
1916 return ERROR(dictionary_corrupted);
1919 size_t const dictContentSize = (size_t)(dictEnd - (dictPtr + 12));
1920 for (i = 0; i < 3; i++) {
1921 U32 const rep = ZSTD_readLE32(dictPtr);
1923 if (rep == 0 || rep >= dictContentSize)
1924 return ERROR(dictionary_corrupted);
1925 entropy->rep[i] = rep;
1929 return dictPtr - (const BYTE *)dict;
1932 static size_t ZSTD_decompress_insertDictionary(ZSTD_DCtx *dctx, const void *dict, size_t dictSize)
1935 return ZSTD_refDictContent(dctx, dict, dictSize);
1937 U32 const magic = ZSTD_readLE32(dict);
1938 if (magic != ZSTD_DICT_MAGIC) {
1939 return ZSTD_refDictContent(dctx, dict, dictSize); /* pure content mode */
1942 dctx->dictID = ZSTD_readLE32((const char *)dict + 4);
1944 /* load entropy tables */
1946 size_t const eSize = ZSTD_loadEntropy(&dctx->entropy, dict, dictSize);
1947 if (ZSTD_isError(eSize))
1948 return ERROR(dictionary_corrupted);
1949 dict = (const char *)dict + eSize;
1952 dctx->litEntropy = dctx->fseEntropy = 1;
1954 /* reference dictionary content */
1955 return ZSTD_refDictContent(dctx, dict, dictSize);
1958 size_t ZSTD_decompressBegin_usingDict(ZSTD_DCtx *dctx, const void *dict, size_t dictSize)
1960 CHECK_F(ZSTD_decompressBegin(dctx));
1961 if (dict && dictSize)
1962 CHECK_E(ZSTD_decompress_insertDictionary(dctx, dict, dictSize), dictionary_corrupted);
1966 /* ====== ZSTD_DDict ====== */
1968 struct ZSTD_DDict_s {
1970 const void *dictContent;
1972 ZSTD_entropyTables_t entropy;
1975 ZSTD_customMem cMem;
1976 }; /* typedef'd to ZSTD_DDict within "zstd.h" */
1978 size_t ZSTD_DDictWorkspaceBound(void) { return ZSTD_ALIGN(sizeof(ZSTD_stack)) + ZSTD_ALIGN(sizeof(ZSTD_DDict)); }
1980 static const void *ZSTD_DDictDictContent(const ZSTD_DDict *ddict) { return ddict->dictContent; }
1982 static size_t ZSTD_DDictDictSize(const ZSTD_DDict *ddict) { return ddict->dictSize; }
1984 static void ZSTD_refDDict(ZSTD_DCtx *dstDCtx, const ZSTD_DDict *ddict)
1986 ZSTD_decompressBegin(dstDCtx); /* init */
1987 if (ddict) { /* support refDDict on NULL */
1988 dstDCtx->dictID = ddict->dictID;
1989 dstDCtx->base = ddict->dictContent;
1990 dstDCtx->vBase = ddict->dictContent;
1991 dstDCtx->dictEnd = (const BYTE *)ddict->dictContent + ddict->dictSize;
1992 dstDCtx->previousDstEnd = dstDCtx->dictEnd;
1993 if (ddict->entropyPresent) {
1994 dstDCtx->litEntropy = 1;
1995 dstDCtx->fseEntropy = 1;
1996 dstDCtx->LLTptr = ddict->entropy.LLTable;
1997 dstDCtx->MLTptr = ddict->entropy.MLTable;
1998 dstDCtx->OFTptr = ddict->entropy.OFTable;
1999 dstDCtx->HUFptr = ddict->entropy.hufTable;
2000 dstDCtx->entropy.rep[0] = ddict->entropy.rep[0];
2001 dstDCtx->entropy.rep[1] = ddict->entropy.rep[1];
2002 dstDCtx->entropy.rep[2] = ddict->entropy.rep[2];
2004 dstDCtx->litEntropy = 0;
2005 dstDCtx->fseEntropy = 0;
2010 static size_t ZSTD_loadEntropy_inDDict(ZSTD_DDict *ddict)
2013 ddict->entropyPresent = 0;
2014 if (ddict->dictSize < 8)
2017 U32 const magic = ZSTD_readLE32(ddict->dictContent);
2018 if (magic != ZSTD_DICT_MAGIC)
2019 return 0; /* pure content mode */
2021 ddict->dictID = ZSTD_readLE32((const char *)ddict->dictContent + 4);
2023 /* load entropy tables */
2024 CHECK_E(ZSTD_loadEntropy(&ddict->entropy, ddict->dictContent, ddict->dictSize), dictionary_corrupted);
2025 ddict->entropyPresent = 1;
2029 static ZSTD_DDict *ZSTD_createDDict_advanced(const void *dict, size_t dictSize, unsigned byReference, ZSTD_customMem customMem)
2031 if (!customMem.customAlloc || !customMem.customFree)
2035 ZSTD_DDict *const ddict = (ZSTD_DDict *)ZSTD_malloc(sizeof(ZSTD_DDict), customMem);
2038 ddict->cMem = customMem;
2040 if ((byReference) || (!dict) || (!dictSize)) {
2041 ddict->dictBuffer = NULL;
2042 ddict->dictContent = dict;
2044 void *const internalBuffer = ZSTD_malloc(dictSize, customMem);
2045 if (!internalBuffer) {
2046 ZSTD_freeDDict(ddict);
2049 memcpy(internalBuffer, dict, dictSize);
2050 ddict->dictBuffer = internalBuffer;
2051 ddict->dictContent = internalBuffer;
2053 ddict->dictSize = dictSize;
2054 ddict->entropy.hufTable[0] = (HUF_DTable)((HufLog)*0x1000001); /* cover both little and big endian */
2055 /* parse dictionary content */
2057 size_t const errorCode = ZSTD_loadEntropy_inDDict(ddict);
2058 if (ZSTD_isError(errorCode)) {
2059 ZSTD_freeDDict(ddict);
2068 /*! ZSTD_initDDict() :
2069 * Create a digested dictionary, to start decompression without startup delay.
2070 * `dict` content is copied inside DDict.
2071 * Consequently, `dict` can be released after `ZSTD_DDict` creation */
2072 ZSTD_DDict *ZSTD_initDDict(const void *dict, size_t dictSize, void *workspace, size_t workspaceSize)
2074 ZSTD_customMem const stackMem = ZSTD_initStack(workspace, workspaceSize);
2075 return ZSTD_createDDict_advanced(dict, dictSize, 1, stackMem);
2078 size_t ZSTD_freeDDict(ZSTD_DDict *ddict)
2081 return 0; /* support free on NULL */
2083 ZSTD_customMem const cMem = ddict->cMem;
2084 ZSTD_free(ddict->dictBuffer, cMem);
2085 ZSTD_free(ddict, cMem);
2090 /*! ZSTD_getDictID_fromDict() :
2091 * Provides the dictID stored within dictionary.
2092 * if @return == 0, the dictionary is not conformant with Zstandard specification.
2093 * It can still be loaded, but as a content-only dictionary. */
2094 unsigned ZSTD_getDictID_fromDict(const void *dict, size_t dictSize)
2098 if (ZSTD_readLE32(dict) != ZSTD_DICT_MAGIC)
2100 return ZSTD_readLE32((const char *)dict + 4);
2103 /*! ZSTD_getDictID_fromDDict() :
2104 * Provides the dictID of the dictionary loaded into `ddict`.
2105 * If @return == 0, the dictionary is not conformant to Zstandard specification, or empty.
2106 * Non-conformant dictionaries can still be loaded, but as content-only dictionaries. */
2107 unsigned ZSTD_getDictID_fromDDict(const ZSTD_DDict *ddict)
2111 return ZSTD_getDictID_fromDict(ddict->dictContent, ddict->dictSize);
2114 /*! ZSTD_getDictID_fromFrame() :
2115 * Provides the dictID required to decompressed the frame stored within `src`.
2116 * If @return == 0, the dictID could not be decoded.
2117 * This could for one of the following reasons :
2118 * - The frame does not require a dictionary to be decoded (most common case).
2119 * - The frame was built with dictID intentionally removed. Whatever dictionary is necessary is a hidden information.
2120 * Note : this use case also happens when using a non-conformant dictionary.
2121 * - `srcSize` is too small, and as a result, the frame header could not be decoded (only possible if `srcSize < ZSTD_FRAMEHEADERSIZE_MAX`).
2122 * - This is not a Zstandard frame.
2123 * When identifying the exact failure cause, it's possible to used ZSTD_getFrameParams(), which will provide a more precise error code. */
2124 unsigned ZSTD_getDictID_fromFrame(const void *src, size_t srcSize)
2126 ZSTD_frameParams zfp = {0, 0, 0, 0};
2127 size_t const hError = ZSTD_getFrameParams(&zfp, src, srcSize);
2128 if (ZSTD_isError(hError))
2133 /*! ZSTD_decompress_usingDDict() :
2134 * Decompression using a pre-digested Dictionary
2135 * Use dictionary without significant overhead. */
2136 size_t ZSTD_decompress_usingDDict(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const ZSTD_DDict *ddict)
2138 /* pass content and size in case legacy frames are encountered */
2139 return ZSTD_decompressMultiFrame(dctx, dst, dstCapacity, src, srcSize, NULL, 0, ddict);
2142 /*=====================================
2143 * Streaming decompression
2144 *====================================*/
2146 typedef enum { zdss_init, zdss_loadHeader, zdss_read, zdss_load, zdss_flush } ZSTD_dStreamStage;
2148 /* *** Resource management *** */
2149 struct ZSTD_DStream_s {
2151 ZSTD_DDict *ddictLocal;
2152 const ZSTD_DDict *ddict;
2153 ZSTD_frameParams fParams;
2154 ZSTD_dStreamStage stage;
2158 size_t maxWindowSize;
2164 BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX]; /* tmp buffer to store frame header */
2166 ZSTD_customMem customMem;
2167 void *legacyContext;
2168 U32 previousLegacyVersion;
2171 }; /* typedef'd to ZSTD_DStream within "zstd.h" */
2173 size_t ZSTD_DStreamWorkspaceBound(size_t maxWindowSize)
2175 size_t const blockSize = MIN(maxWindowSize, ZSTD_BLOCKSIZE_ABSOLUTEMAX);
2176 size_t const inBuffSize = blockSize;
2177 size_t const outBuffSize = maxWindowSize + blockSize + WILDCOPY_OVERLENGTH * 2;
2178 return ZSTD_DCtxWorkspaceBound() + ZSTD_ALIGN(sizeof(ZSTD_DStream)) + ZSTD_ALIGN(inBuffSize) + ZSTD_ALIGN(outBuffSize);
2181 static ZSTD_DStream *ZSTD_createDStream_advanced(ZSTD_customMem customMem)
2185 if (!customMem.customAlloc || !customMem.customFree)
2188 zds = (ZSTD_DStream *)ZSTD_malloc(sizeof(ZSTD_DStream), customMem);
2191 memset(zds, 0, sizeof(ZSTD_DStream));
2192 memcpy(&zds->customMem, &customMem, sizeof(ZSTD_customMem));
2193 zds->dctx = ZSTD_createDCtx_advanced(customMem);
2194 if (zds->dctx == NULL) {
2195 ZSTD_freeDStream(zds);
2198 zds->stage = zdss_init;
2199 zds->maxWindowSize = ZSTD_MAXWINDOWSIZE_DEFAULT;
2203 ZSTD_DStream *ZSTD_initDStream(size_t maxWindowSize, void *workspace, size_t workspaceSize)
2205 ZSTD_customMem const stackMem = ZSTD_initStack(workspace, workspaceSize);
2206 ZSTD_DStream *zds = ZSTD_createDStream_advanced(stackMem);
2211 zds->maxWindowSize = maxWindowSize;
2212 zds->stage = zdss_loadHeader;
2213 zds->lhSize = zds->inPos = zds->outStart = zds->outEnd = 0;
2214 ZSTD_freeDDict(zds->ddictLocal);
2215 zds->ddictLocal = NULL;
2216 zds->ddict = zds->ddictLocal;
2217 zds->legacyVersion = 0;
2218 zds->hostageByte = 0;
2221 size_t const blockSize = MIN(zds->maxWindowSize, ZSTD_BLOCKSIZE_ABSOLUTEMAX);
2222 size_t const neededOutSize = zds->maxWindowSize + blockSize + WILDCOPY_OVERLENGTH * 2;
2224 zds->inBuff = (char *)ZSTD_malloc(blockSize, zds->customMem);
2225 zds->inBuffSize = blockSize;
2226 zds->outBuff = (char *)ZSTD_malloc(neededOutSize, zds->customMem);
2227 zds->outBuffSize = neededOutSize;
2228 if (zds->inBuff == NULL || zds->outBuff == NULL) {
2229 ZSTD_freeDStream(zds);
2236 ZSTD_DStream *ZSTD_initDStream_usingDDict(size_t maxWindowSize, const ZSTD_DDict *ddict, void *workspace, size_t workspaceSize)
2238 ZSTD_DStream *zds = ZSTD_initDStream(maxWindowSize, workspace, workspaceSize);
2245 size_t ZSTD_freeDStream(ZSTD_DStream *zds)
2248 return 0; /* support free on null */
2250 ZSTD_customMem const cMem = zds->customMem;
2251 ZSTD_freeDCtx(zds->dctx);
2253 ZSTD_freeDDict(zds->ddictLocal);
2254 zds->ddictLocal = NULL;
2255 ZSTD_free(zds->inBuff, cMem);
2257 ZSTD_free(zds->outBuff, cMem);
2258 zds->outBuff = NULL;
2259 ZSTD_free(zds, cMem);
2264 /* *** Initialization *** */
2266 size_t ZSTD_DStreamInSize(void) { return ZSTD_BLOCKSIZE_ABSOLUTEMAX + ZSTD_blockHeaderSize; }
2267 size_t ZSTD_DStreamOutSize(void) { return ZSTD_BLOCKSIZE_ABSOLUTEMAX; }
2269 size_t ZSTD_resetDStream(ZSTD_DStream *zds)
2271 zds->stage = zdss_loadHeader;
2272 zds->lhSize = zds->inPos = zds->outStart = zds->outEnd = 0;
2273 zds->legacyVersion = 0;
2274 zds->hostageByte = 0;
2275 return ZSTD_frameHeaderSize_prefix;
2278 /* ***** Decompression ***** */
2280 ZSTD_STATIC size_t ZSTD_limitCopy(void *dst, size_t dstCapacity, const void *src, size_t srcSize)
2282 size_t const length = MIN(dstCapacity, srcSize);
2283 memcpy(dst, src, length);
2287 size_t ZSTD_decompressStream(ZSTD_DStream *zds, ZSTD_outBuffer *output, ZSTD_inBuffer *input)
2289 const char *const istart = (const char *)(input->src) + input->pos;
2290 const char *const iend = (const char *)(input->src) + input->size;
2291 const char *ip = istart;
2292 char *const ostart = (char *)(output->dst) + output->pos;
2293 char *const oend = (char *)(output->dst) + output->size;
2295 U32 someMoreWork = 1;
2297 while (someMoreWork) {
2298 switch (zds->stage) {
2300 ZSTD_resetDStream(zds); /* transparent reset on starting decoding a new frame */
2303 case zdss_loadHeader: {
2304 size_t const hSize = ZSTD_getFrameParams(&zds->fParams, zds->headerBuffer, zds->lhSize);
2305 if (ZSTD_isError(hSize))
2307 if (hSize != 0) { /* need more input */
2308 size_t const toLoad = hSize - zds->lhSize; /* if hSize!=0, hSize > zds->lhSize */
2309 if (toLoad > (size_t)(iend - ip)) { /* not enough input to load full header */
2310 memcpy(zds->headerBuffer + zds->lhSize, ip, iend - ip);
2311 zds->lhSize += iend - ip;
2312 input->pos = input->size;
2313 return (MAX(ZSTD_frameHeaderSize_min, hSize) - zds->lhSize) +
2314 ZSTD_blockHeaderSize; /* remaining header bytes + next block header */
2316 memcpy(zds->headerBuffer + zds->lhSize, ip, toLoad);
2317 zds->lhSize = hSize;
2322 /* check for single-pass mode opportunity */
2323 if (zds->fParams.frameContentSize && zds->fParams.windowSize /* skippable frame if == 0 */
2324 && (U64)(size_t)(oend - op) >= zds->fParams.frameContentSize) {
2325 size_t const cSize = ZSTD_findFrameCompressedSize(istart, iend - istart);
2326 if (cSize <= (size_t)(iend - istart)) {
2327 size_t const decompressedSize = ZSTD_decompress_usingDDict(zds->dctx, op, oend - op, istart, cSize, zds->ddict);
2328 if (ZSTD_isError(decompressedSize))
2329 return decompressedSize;
2330 ip = istart + cSize;
2331 op += decompressedSize;
2332 zds->dctx->expected = 0;
2333 zds->stage = zdss_init;
2339 /* Consume header */
2340 ZSTD_refDDict(zds->dctx, zds->ddict);
2342 size_t const h1Size = ZSTD_nextSrcSizeToDecompress(zds->dctx); /* == ZSTD_frameHeaderSize_prefix */
2343 CHECK_F(ZSTD_decompressContinue(zds->dctx, NULL, 0, zds->headerBuffer, h1Size));
2345 size_t const h2Size = ZSTD_nextSrcSizeToDecompress(zds->dctx);
2346 CHECK_F(ZSTD_decompressContinue(zds->dctx, NULL, 0, zds->headerBuffer + h1Size, h2Size));
2350 zds->fParams.windowSize = MAX(zds->fParams.windowSize, 1U << ZSTD_WINDOWLOG_ABSOLUTEMIN);
2351 if (zds->fParams.windowSize > zds->maxWindowSize)
2352 return ERROR(frameParameter_windowTooLarge);
2354 /* Buffers are preallocated, but double check */
2356 size_t const blockSize = MIN(zds->maxWindowSize, ZSTD_BLOCKSIZE_ABSOLUTEMAX);
2357 size_t const neededOutSize = zds->maxWindowSize + blockSize + WILDCOPY_OVERLENGTH * 2;
2358 if (zds->inBuffSize < blockSize) {
2359 return ERROR(GENERIC);
2361 if (zds->outBuffSize < neededOutSize) {
2362 return ERROR(GENERIC);
2364 zds->blockSize = blockSize;
2366 zds->stage = zdss_read;
2371 size_t const neededInSize = ZSTD_nextSrcSizeToDecompress(zds->dctx);
2372 if (neededInSize == 0) { /* end of frame */
2373 zds->stage = zdss_init;
2377 if ((size_t)(iend - ip) >= neededInSize) { /* decode directly from src */
2378 const int isSkipFrame = ZSTD_isSkipFrame(zds->dctx);
2379 size_t const decodedSize = ZSTD_decompressContinue(zds->dctx, zds->outBuff + zds->outStart,
2380 (isSkipFrame ? 0 : zds->outBuffSize - zds->outStart), ip, neededInSize);
2381 if (ZSTD_isError(decodedSize))
2384 if (!decodedSize && !isSkipFrame)
2385 break; /* this was just a header */
2386 zds->outEnd = zds->outStart + decodedSize;
2387 zds->stage = zdss_flush;
2393 } /* no more input */
2394 zds->stage = zdss_load;
2399 size_t const neededInSize = ZSTD_nextSrcSizeToDecompress(zds->dctx);
2400 size_t const toLoad = neededInSize - zds->inPos; /* should always be <= remaining space within inBuff */
2402 if (toLoad > zds->inBuffSize - zds->inPos)
2403 return ERROR(corruption_detected); /* should never happen */
2404 loadedSize = ZSTD_limitCopy(zds->inBuff + zds->inPos, toLoad, ip, iend - ip);
2406 zds->inPos += loadedSize;
2407 if (loadedSize < toLoad) {
2410 } /* not enough input, wait for more */
2412 /* decode loaded input */
2414 const int isSkipFrame = ZSTD_isSkipFrame(zds->dctx);
2415 size_t const decodedSize = ZSTD_decompressContinue(zds->dctx, zds->outBuff + zds->outStart, zds->outBuffSize - zds->outStart,
2416 zds->inBuff, neededInSize);
2417 if (ZSTD_isError(decodedSize))
2419 zds->inPos = 0; /* input is consumed */
2420 if (!decodedSize && !isSkipFrame) {
2421 zds->stage = zdss_read;
2423 } /* this was just a header */
2424 zds->outEnd = zds->outStart + decodedSize;
2425 zds->stage = zdss_flush;
2431 size_t const toFlushSize = zds->outEnd - zds->outStart;
2432 size_t const flushedSize = ZSTD_limitCopy(op, oend - op, zds->outBuff + zds->outStart, toFlushSize);
2434 zds->outStart += flushedSize;
2435 if (flushedSize == toFlushSize) { /* flush completed */
2436 zds->stage = zdss_read;
2437 if (zds->outStart + zds->blockSize > zds->outBuffSize)
2438 zds->outStart = zds->outEnd = 0;
2441 /* cannot complete flush */
2446 return ERROR(GENERIC); /* impossible */
2451 input->pos += (size_t)(ip - istart);
2452 output->pos += (size_t)(op - ostart);
2454 size_t nextSrcSizeHint = ZSTD_nextSrcSizeToDecompress(zds->dctx);
2455 if (!nextSrcSizeHint) { /* frame fully decoded */
2456 if (zds->outEnd == zds->outStart) { /* output fully flushed */
2457 if (zds->hostageByte) {
2458 if (input->pos >= input->size) {
2459 zds->stage = zdss_read;
2461 } /* can't release hostage (not present) */
2462 input->pos++; /* release hostage */
2466 if (!zds->hostageByte) { /* output not fully flushed; keep last byte as hostage; will be released when all output is flushed */
2467 input->pos--; /* note : pos > 0, otherwise, impossible to finish reading last block */
2468 zds->hostageByte = 1;
2472 nextSrcSizeHint += ZSTD_blockHeaderSize * (ZSTD_nextInputType(zds->dctx) == ZSTDnit_block); /* preload header of next block */
2473 if (zds->inPos > nextSrcSizeHint)
2474 return ERROR(GENERIC); /* should never happen */
2475 nextSrcSizeHint -= zds->inPos; /* already loaded*/
2476 return nextSrcSizeHint;
2480 EXPORT_SYMBOL(ZSTD_DCtxWorkspaceBound);
2481 EXPORT_SYMBOL(ZSTD_initDCtx);
2482 EXPORT_SYMBOL(ZSTD_decompressDCtx);
2483 EXPORT_SYMBOL(ZSTD_decompress_usingDict);
2485 EXPORT_SYMBOL(ZSTD_DDictWorkspaceBound);
2486 EXPORT_SYMBOL(ZSTD_initDDict);
2487 EXPORT_SYMBOL(ZSTD_decompress_usingDDict);
2489 EXPORT_SYMBOL(ZSTD_DStreamWorkspaceBound);
2490 EXPORT_SYMBOL(ZSTD_initDStream);
2491 EXPORT_SYMBOL(ZSTD_initDStream_usingDDict);
2492 EXPORT_SYMBOL(ZSTD_resetDStream);
2493 EXPORT_SYMBOL(ZSTD_decompressStream);
2494 EXPORT_SYMBOL(ZSTD_DStreamInSize);
2495 EXPORT_SYMBOL(ZSTD_DStreamOutSize);
2497 EXPORT_SYMBOL(ZSTD_findFrameCompressedSize);
2498 EXPORT_SYMBOL(ZSTD_getFrameContentSize);
2499 EXPORT_SYMBOL(ZSTD_findDecompressedSize);
2501 EXPORT_SYMBOL(ZSTD_isFrame);
2502 EXPORT_SYMBOL(ZSTD_getDictID_fromDict);
2503 EXPORT_SYMBOL(ZSTD_getDictID_fromDDict);
2504 EXPORT_SYMBOL(ZSTD_getDictID_fromFrame);
2506 EXPORT_SYMBOL(ZSTD_getFrameParams);
2507 EXPORT_SYMBOL(ZSTD_decompressBegin);
2508 EXPORT_SYMBOL(ZSTD_decompressBegin_usingDict);
2509 EXPORT_SYMBOL(ZSTD_copyDCtx);
2510 EXPORT_SYMBOL(ZSTD_nextSrcSizeToDecompress);
2511 EXPORT_SYMBOL(ZSTD_decompressContinue);
2512 EXPORT_SYMBOL(ZSTD_nextInputType);
2514 EXPORT_SYMBOL(ZSTD_decompressBlock);
2515 EXPORT_SYMBOL(ZSTD_insertBlock);