• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /**
2  * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
3  * All rights reserved.
4  *
5  * This source code is licensed under the BSD-style license found in the
6  * LICENSE file in the root directory of https://github.com/facebook/zstd.
7  * An additional grant of patent rights can be found in the PATENTS file in the
8  * same directory.
9  *
10  * This program is free software; you can redistribute it and/or modify it under
11  * the terms of the GNU General Public License version 2 as published by the
12  * Free Software Foundation. This program is dual-licensed; you may select
13  * either version 2 of the GNU General Public License ("GPL") or BSD license
14  * ("BSD").
15  */
16 
17 /* ***************************************************************
18 *  Tuning parameters
19 *****************************************************************/
20 /*!
21 *  MAXWINDOWSIZE_DEFAULT :
22 *  maximum window size accepted by DStream, by default.
23 *  Frames requiring more memory will be rejected.
24 */
25 #ifndef ZSTD_MAXWINDOWSIZE_DEFAULT
26 #define ZSTD_MAXWINDOWSIZE_DEFAULT ((1 << ZSTD_WINDOWLOG_MAX) + 1) /* defined within zstd.h */
27 #endif
28 
29 /*-*******************************************************
30 *  Dependencies
31 *********************************************************/
32 #include "fse.h"
33 #include "huf.h"
34 #include "mem.h" /* low level memory routines */
35 #include "zstd_internal.h"
36 #include <linux/kernel.h>
37 #include <linux/module.h>
38 #include <linux/string.h> /* memcpy, memmove, memset */
39 
40 #define ZSTD_PREFETCH(ptr) __builtin_prefetch(ptr, 0, 0)
41 
42 /*-*************************************
43 *  Macros
44 ***************************************/
45 #define ZSTD_isError ERR_isError /* for inlining */
46 #define FSE_isError ERR_isError
47 #define HUF_isError ERR_isError
48 
49 /*_*******************************************************
50 *  Memory operations
51 **********************************************************/
ZSTD_copy4(void * dst,const void * src)52 static void ZSTD_copy4(void *dst, const void *src) { memcpy(dst, src, 4); }
53 
54 /*-*************************************************************
55 *   Context management
56 ***************************************************************/
57 typedef enum {
58 	ZSTDds_getFrameHeaderSize,
59 	ZSTDds_decodeFrameHeader,
60 	ZSTDds_decodeBlockHeader,
61 	ZSTDds_decompressBlock,
62 	ZSTDds_decompressLastBlock,
63 	ZSTDds_checkChecksum,
64 	ZSTDds_decodeSkippableHeader,
65 	ZSTDds_skipFrame
66 } ZSTD_dStage;
67 
68 typedef struct {
69 	FSE_DTable LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
70 	FSE_DTable OFTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
71 	FSE_DTable MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
72 	HUF_DTable hufTable[HUF_DTABLE_SIZE(HufLog)]; /* can accommodate HUF_decompress4X */
73 	U64 workspace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32 / 2];
74 	U32 rep[ZSTD_REP_NUM];
75 } ZSTD_entropyTables_t;
76 
77 struct ZSTD_DCtx_s {
78 	const FSE_DTable *LLTptr;
79 	const FSE_DTable *MLTptr;
80 	const FSE_DTable *OFTptr;
81 	const HUF_DTable *HUFptr;
82 	ZSTD_entropyTables_t entropy;
83 	const void *previousDstEnd; /* detect continuity */
84 	const void *base;	   /* start of curr segment */
85 	const void *vBase;	  /* virtual start of previous segment if it was just before curr one */
86 	const void *dictEnd;	/* end of previous segment */
87 	size_t expected;
88 	ZSTD_frameParams fParams;
89 	blockType_e bType; /* used in ZSTD_decompressContinue(), to transfer blockType between header decoding and block decoding stages */
90 	ZSTD_dStage stage;
91 	U32 litEntropy;
92 	U32 fseEntropy;
93 	struct xxh64_state xxhState;
94 	size_t headerSize;
95 	U32 dictID;
96 	const BYTE *litPtr;
97 	ZSTD_customMem customMem;
98 	size_t litSize;
99 	size_t rleSize;
100 	BYTE litBuffer[ZSTD_BLOCKSIZE_ABSOLUTEMAX + WILDCOPY_OVERLENGTH];
101 	BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX];
102 }; /* typedef'd to ZSTD_DCtx within "zstd.h" */
103 
ZSTD_DCtxWorkspaceBound(void)104 size_t ZSTD_DCtxWorkspaceBound(void) { return ZSTD_ALIGN(sizeof(ZSTD_stack)) + ZSTD_ALIGN(sizeof(ZSTD_DCtx)); }
105 
ZSTD_decompressBegin(ZSTD_DCtx * dctx)106 size_t ZSTD_decompressBegin(ZSTD_DCtx *dctx)
107 {
108 	dctx->expected = ZSTD_frameHeaderSize_prefix;
109 	dctx->stage = ZSTDds_getFrameHeaderSize;
110 	dctx->previousDstEnd = NULL;
111 	dctx->base = NULL;
112 	dctx->vBase = NULL;
113 	dctx->dictEnd = NULL;
114 	dctx->entropy.hufTable[0] = (HUF_DTable)((HufLog)*0x1000001); /* cover both little and big endian */
115 	dctx->litEntropy = dctx->fseEntropy = 0;
116 	dctx->dictID = 0;
117 	ZSTD_STATIC_ASSERT(sizeof(dctx->entropy.rep) == sizeof(repStartValue));
118 	memcpy(dctx->entropy.rep, repStartValue, sizeof(repStartValue)); /* initial repcodes */
119 	dctx->LLTptr = dctx->entropy.LLTable;
120 	dctx->MLTptr = dctx->entropy.MLTable;
121 	dctx->OFTptr = dctx->entropy.OFTable;
122 	dctx->HUFptr = dctx->entropy.hufTable;
123 	return 0;
124 }
125 
ZSTD_createDCtx_advanced(ZSTD_customMem customMem)126 ZSTD_DCtx *ZSTD_createDCtx_advanced(ZSTD_customMem customMem)
127 {
128 	ZSTD_DCtx *dctx;
129 
130 	if (!customMem.customAlloc || !customMem.customFree)
131 		return NULL;
132 
133 	dctx = (ZSTD_DCtx *)ZSTD_malloc(sizeof(ZSTD_DCtx), customMem);
134 	if (!dctx)
135 		return NULL;
136 	memcpy(&dctx->customMem, &customMem, sizeof(customMem));
137 	ZSTD_decompressBegin(dctx);
138 	return dctx;
139 }
140 
ZSTD_initDCtx(void * workspace,size_t workspaceSize)141 ZSTD_DCtx *ZSTD_initDCtx(void *workspace, size_t workspaceSize)
142 {
143 	ZSTD_customMem const stackMem = ZSTD_initStack(workspace, workspaceSize);
144 	return ZSTD_createDCtx_advanced(stackMem);
145 }
146 
ZSTD_freeDCtx(ZSTD_DCtx * dctx)147 size_t ZSTD_freeDCtx(ZSTD_DCtx *dctx)
148 {
149 	if (dctx == NULL)
150 		return 0; /* support free on NULL */
151 	ZSTD_free(dctx, dctx->customMem);
152 	return 0; /* reserved as a potential error code in the future */
153 }
154 
ZSTD_copyDCtx(ZSTD_DCtx * dstDCtx,const ZSTD_DCtx * srcDCtx)155 void ZSTD_copyDCtx(ZSTD_DCtx *dstDCtx, const ZSTD_DCtx *srcDCtx)
156 {
157 	size_t const workSpaceSize = (ZSTD_BLOCKSIZE_ABSOLUTEMAX + WILDCOPY_OVERLENGTH) + ZSTD_frameHeaderSize_max;
158 	memcpy(dstDCtx, srcDCtx, sizeof(ZSTD_DCtx) - workSpaceSize); /* no need to copy workspace */
159 }
160 
161 static void ZSTD_refDDict(ZSTD_DCtx *dstDCtx, const ZSTD_DDict *ddict);
162 
163 /*-*************************************************************
164 *   Decompression section
165 ***************************************************************/
166 
167 /*! ZSTD_isFrame() :
168  *  Tells if the content of `buffer` starts with a valid Frame Identifier.
169  *  Note : Frame Identifier is 4 bytes. If `size < 4`, @return will always be 0.
170  *  Note 2 : Legacy Frame Identifiers are considered valid only if Legacy Support is enabled.
171  *  Note 3 : Skippable Frame Identifiers are considered valid. */
ZSTD_isFrame(const void * buffer,size_t size)172 unsigned ZSTD_isFrame(const void *buffer, size_t size)
173 {
174 	if (size < 4)
175 		return 0;
176 	{
177 		U32 const magic = ZSTD_readLE32(buffer);
178 		if (magic == ZSTD_MAGICNUMBER)
179 			return 1;
180 		if ((magic & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START)
181 			return 1;
182 	}
183 	return 0;
184 }
185 
186 /** ZSTD_frameHeaderSize() :
187 *   srcSize must be >= ZSTD_frameHeaderSize_prefix.
188 *   @return : size of the Frame Header */
ZSTD_frameHeaderSize(const void * src,size_t srcSize)189 static size_t ZSTD_frameHeaderSize(const void *src, size_t srcSize)
190 {
191 	if (srcSize < ZSTD_frameHeaderSize_prefix)
192 		return ERROR(srcSize_wrong);
193 	{
194 		BYTE const fhd = ((const BYTE *)src)[4];
195 		U32 const dictID = fhd & 3;
196 		U32 const singleSegment = (fhd >> 5) & 1;
197 		U32 const fcsId = fhd >> 6;
198 		return ZSTD_frameHeaderSize_prefix + !singleSegment + ZSTD_did_fieldSize[dictID] + ZSTD_fcs_fieldSize[fcsId] + (singleSegment && !fcsId);
199 	}
200 }
201 
202 /** ZSTD_getFrameParams() :
203 *   decode Frame Header, or require larger `srcSize`.
204 *   @return : 0, `fparamsPtr` is correctly filled,
205 *            >0, `srcSize` is too small, result is expected `srcSize`,
206 *             or an error code, which can be tested using ZSTD_isError() */
ZSTD_getFrameParams(ZSTD_frameParams * fparamsPtr,const void * src,size_t srcSize)207 size_t ZSTD_getFrameParams(ZSTD_frameParams *fparamsPtr, const void *src, size_t srcSize)
208 {
209 	const BYTE *ip = (const BYTE *)src;
210 
211 	if (srcSize < ZSTD_frameHeaderSize_prefix)
212 		return ZSTD_frameHeaderSize_prefix;
213 	if (ZSTD_readLE32(src) != ZSTD_MAGICNUMBER) {
214 		if ((ZSTD_readLE32(src) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
215 			if (srcSize < ZSTD_skippableHeaderSize)
216 				return ZSTD_skippableHeaderSize; /* magic number + skippable frame length */
217 			memset(fparamsPtr, 0, sizeof(*fparamsPtr));
218 			fparamsPtr->frameContentSize = ZSTD_readLE32((const char *)src + 4);
219 			fparamsPtr->windowSize = 0; /* windowSize==0 means a frame is skippable */
220 			return 0;
221 		}
222 		return ERROR(prefix_unknown);
223 	}
224 
225 	/* ensure there is enough `srcSize` to fully read/decode frame header */
226 	{
227 		size_t const fhsize = ZSTD_frameHeaderSize(src, srcSize);
228 		if (srcSize < fhsize)
229 			return fhsize;
230 	}
231 
232 	{
233 		BYTE const fhdByte = ip[4];
234 		size_t pos = 5;
235 		U32 const dictIDSizeCode = fhdByte & 3;
236 		U32 const checksumFlag = (fhdByte >> 2) & 1;
237 		U32 const singleSegment = (fhdByte >> 5) & 1;
238 		U32 const fcsID = fhdByte >> 6;
239 		U32 const windowSizeMax = 1U << ZSTD_WINDOWLOG_MAX;
240 		U32 windowSize = 0;
241 		U32 dictID = 0;
242 		U64 frameContentSize = 0;
243 		if ((fhdByte & 0x08) != 0)
244 			return ERROR(frameParameter_unsupported); /* reserved bits, which must be zero */
245 		if (!singleSegment) {
246 			BYTE const wlByte = ip[pos++];
247 			U32 const windowLog = (wlByte >> 3) + ZSTD_WINDOWLOG_ABSOLUTEMIN;
248 			if (windowLog > ZSTD_WINDOWLOG_MAX)
249 				return ERROR(frameParameter_windowTooLarge); /* avoids issue with 1 << windowLog */
250 			windowSize = (1U << windowLog);
251 			windowSize += (windowSize >> 3) * (wlByte & 7);
252 		}
253 
254 		switch (dictIDSizeCode) {
255 		default: /* impossible */
256 		case 0: break;
257 		case 1:
258 			dictID = ip[pos];
259 			pos++;
260 			break;
261 		case 2:
262 			dictID = ZSTD_readLE16(ip + pos);
263 			pos += 2;
264 			break;
265 		case 3:
266 			dictID = ZSTD_readLE32(ip + pos);
267 			pos += 4;
268 			break;
269 		}
270 		switch (fcsID) {
271 		default: /* impossible */
272 		case 0:
273 			if (singleSegment)
274 				frameContentSize = ip[pos];
275 			break;
276 		case 1: frameContentSize = ZSTD_readLE16(ip + pos) + 256; break;
277 		case 2: frameContentSize = ZSTD_readLE32(ip + pos); break;
278 		case 3: frameContentSize = ZSTD_readLE64(ip + pos); break;
279 		}
280 		if (!windowSize)
281 			windowSize = (U32)frameContentSize;
282 		if (windowSize > windowSizeMax)
283 			return ERROR(frameParameter_windowTooLarge);
284 		fparamsPtr->frameContentSize = frameContentSize;
285 		fparamsPtr->windowSize = windowSize;
286 		fparamsPtr->dictID = dictID;
287 		fparamsPtr->checksumFlag = checksumFlag;
288 	}
289 	return 0;
290 }
291 
292 /** ZSTD_getFrameContentSize() :
293 *   compatible with legacy mode
294 *   @return : decompressed size of the single frame pointed to be `src` if known, otherwise
295 *             - ZSTD_CONTENTSIZE_UNKNOWN if the size cannot be determined
296 *             - ZSTD_CONTENTSIZE_ERROR if an error occurred (e.g. invalid magic number, srcSize too small) */
ZSTD_getFrameContentSize(const void * src,size_t srcSize)297 unsigned long long ZSTD_getFrameContentSize(const void *src, size_t srcSize)
298 {
299 	{
300 		ZSTD_frameParams fParams;
301 		if (ZSTD_getFrameParams(&fParams, src, srcSize) != 0)
302 			return ZSTD_CONTENTSIZE_ERROR;
303 		if (fParams.windowSize == 0) {
304 			/* Either skippable or empty frame, size == 0 either way */
305 			return 0;
306 		} else if (fParams.frameContentSize != 0) {
307 			return fParams.frameContentSize;
308 		} else {
309 			return ZSTD_CONTENTSIZE_UNKNOWN;
310 		}
311 	}
312 }
313 
314 /** ZSTD_findDecompressedSize() :
315  *  compatible with legacy mode
316  *  `srcSize` must be the exact length of some number of ZSTD compressed and/or
317  *      skippable frames
318  *  @return : decompressed size of the frames contained */
ZSTD_findDecompressedSize(const void * src,size_t srcSize)319 unsigned long long ZSTD_findDecompressedSize(const void *src, size_t srcSize)
320 {
321 	{
322 		unsigned long long totalDstSize = 0;
323 		while (srcSize >= ZSTD_frameHeaderSize_prefix) {
324 			const U32 magicNumber = ZSTD_readLE32(src);
325 
326 			if ((magicNumber & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
327 				size_t skippableSize;
328 				if (srcSize < ZSTD_skippableHeaderSize)
329 					return ERROR(srcSize_wrong);
330 				skippableSize = ZSTD_readLE32((const BYTE *)src + 4) + ZSTD_skippableHeaderSize;
331 				if (srcSize < skippableSize) {
332 					return ZSTD_CONTENTSIZE_ERROR;
333 				}
334 
335 				src = (const BYTE *)src + skippableSize;
336 				srcSize -= skippableSize;
337 				continue;
338 			}
339 
340 			{
341 				unsigned long long const ret = ZSTD_getFrameContentSize(src, srcSize);
342 				if (ret >= ZSTD_CONTENTSIZE_ERROR)
343 					return ret;
344 
345 				/* check for overflow */
346 				if (totalDstSize + ret < totalDstSize)
347 					return ZSTD_CONTENTSIZE_ERROR;
348 				totalDstSize += ret;
349 			}
350 			{
351 				size_t const frameSrcSize = ZSTD_findFrameCompressedSize(src, srcSize);
352 				if (ZSTD_isError(frameSrcSize)) {
353 					return ZSTD_CONTENTSIZE_ERROR;
354 				}
355 
356 				src = (const BYTE *)src + frameSrcSize;
357 				srcSize -= frameSrcSize;
358 			}
359 		}
360 
361 		if (srcSize) {
362 			return ZSTD_CONTENTSIZE_ERROR;
363 		}
364 
365 		return totalDstSize;
366 	}
367 }
368 
369 /** ZSTD_decodeFrameHeader() :
370 *   `headerSize` must be the size provided by ZSTD_frameHeaderSize().
371 *   @return : 0 if success, or an error code, which can be tested using ZSTD_isError() */
ZSTD_decodeFrameHeader(ZSTD_DCtx * dctx,const void * src,size_t headerSize)372 static size_t ZSTD_decodeFrameHeader(ZSTD_DCtx *dctx, const void *src, size_t headerSize)
373 {
374 	size_t const result = ZSTD_getFrameParams(&(dctx->fParams), src, headerSize);
375 	if (ZSTD_isError(result))
376 		return result; /* invalid header */
377 	if (result > 0)
378 		return ERROR(srcSize_wrong); /* headerSize too small */
379 	if (dctx->fParams.dictID && (dctx->dictID != dctx->fParams.dictID))
380 		return ERROR(dictionary_wrong);
381 	if (dctx->fParams.checksumFlag)
382 		xxh64_reset(&dctx->xxhState, 0);
383 	return 0;
384 }
385 
386 typedef struct {
387 	blockType_e blockType;
388 	U32 lastBlock;
389 	U32 origSize;
390 } blockProperties_t;
391 
392 /*! ZSTD_getcBlockSize() :
393 *   Provides the size of compressed block from block header `src` */
ZSTD_getcBlockSize(const void * src,size_t srcSize,blockProperties_t * bpPtr)394 size_t ZSTD_getcBlockSize(const void *src, size_t srcSize, blockProperties_t *bpPtr)
395 {
396 	if (srcSize < ZSTD_blockHeaderSize)
397 		return ERROR(srcSize_wrong);
398 	{
399 		U32 const cBlockHeader = ZSTD_readLE24(src);
400 		U32 const cSize = cBlockHeader >> 3;
401 		bpPtr->lastBlock = cBlockHeader & 1;
402 		bpPtr->blockType = (blockType_e)((cBlockHeader >> 1) & 3);
403 		bpPtr->origSize = cSize; /* only useful for RLE */
404 		if (bpPtr->blockType == bt_rle)
405 			return 1;
406 		if (bpPtr->blockType == bt_reserved)
407 			return ERROR(corruption_detected);
408 		return cSize;
409 	}
410 }
411 
ZSTD_copyRawBlock(void * dst,size_t dstCapacity,const void * src,size_t srcSize)412 static size_t ZSTD_copyRawBlock(void *dst, size_t dstCapacity, const void *src, size_t srcSize)
413 {
414 	if (srcSize > dstCapacity)
415 		return ERROR(dstSize_tooSmall);
416 	memcpy(dst, src, srcSize);
417 	return srcSize;
418 }
419 
ZSTD_setRleBlock(void * dst,size_t dstCapacity,const void * src,size_t srcSize,size_t regenSize)420 static size_t ZSTD_setRleBlock(void *dst, size_t dstCapacity, const void *src, size_t srcSize, size_t regenSize)
421 {
422 	if (srcSize != 1)
423 		return ERROR(srcSize_wrong);
424 	if (regenSize > dstCapacity)
425 		return ERROR(dstSize_tooSmall);
426 	memset(dst, *(const BYTE *)src, regenSize);
427 	return regenSize;
428 }
429 
430 /*! ZSTD_decodeLiteralsBlock() :
431 	@return : nb of bytes read from src (< srcSize ) */
ZSTD_decodeLiteralsBlock(ZSTD_DCtx * dctx,const void * src,size_t srcSize)432 size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx *dctx, const void *src, size_t srcSize) /* note : srcSize < BLOCKSIZE */
433 {
434 	if (srcSize < MIN_CBLOCK_SIZE)
435 		return ERROR(corruption_detected);
436 
437 	{
438 		const BYTE *const istart = (const BYTE *)src;
439 		symbolEncodingType_e const litEncType = (symbolEncodingType_e)(istart[0] & 3);
440 
441 		switch (litEncType) {
442 		case set_repeat:
443 			if (dctx->litEntropy == 0)
444 				return ERROR(dictionary_corrupted);
445 			fallthrough;
446 		case set_compressed:
447 			if (srcSize < 5)
448 				return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for case 3 */
449 			{
450 				size_t lhSize, litSize, litCSize;
451 				U32 singleStream = 0;
452 				U32 const lhlCode = (istart[0] >> 2) & 3;
453 				U32 const lhc = ZSTD_readLE32(istart);
454 				switch (lhlCode) {
455 				case 0:
456 				case 1:
457 				default: /* note : default is impossible, since lhlCode into [0..3] */
458 					/* 2 - 2 - 10 - 10 */
459 					singleStream = !lhlCode;
460 					lhSize = 3;
461 					litSize = (lhc >> 4) & 0x3FF;
462 					litCSize = (lhc >> 14) & 0x3FF;
463 					break;
464 				case 2:
465 					/* 2 - 2 - 14 - 14 */
466 					lhSize = 4;
467 					litSize = (lhc >> 4) & 0x3FFF;
468 					litCSize = lhc >> 18;
469 					break;
470 				case 3:
471 					/* 2 - 2 - 18 - 18 */
472 					lhSize = 5;
473 					litSize = (lhc >> 4) & 0x3FFFF;
474 					litCSize = (lhc >> 22) + (istart[4] << 10);
475 					break;
476 				}
477 				if (litSize > ZSTD_BLOCKSIZE_ABSOLUTEMAX)
478 					return ERROR(corruption_detected);
479 				if (litCSize + lhSize > srcSize)
480 					return ERROR(corruption_detected);
481 
482 				if (HUF_isError(
483 					(litEncType == set_repeat)
484 					    ? (singleStream ? HUF_decompress1X_usingDTable(dctx->litBuffer, litSize, istart + lhSize, litCSize, dctx->HUFptr)
485 							    : HUF_decompress4X_usingDTable(dctx->litBuffer, litSize, istart + lhSize, litCSize, dctx->HUFptr))
486 					    : (singleStream
487 						   ? HUF_decompress1X2_DCtx_wksp(dctx->entropy.hufTable, dctx->litBuffer, litSize, istart + lhSize, litCSize,
488 										 dctx->entropy.workspace, sizeof(dctx->entropy.workspace))
489 						   : HUF_decompress4X_hufOnly_wksp(dctx->entropy.hufTable, dctx->litBuffer, litSize, istart + lhSize, litCSize,
490 										   dctx->entropy.workspace, sizeof(dctx->entropy.workspace)))))
491 					return ERROR(corruption_detected);
492 
493 				dctx->litPtr = dctx->litBuffer;
494 				dctx->litSize = litSize;
495 				dctx->litEntropy = 1;
496 				if (litEncType == set_compressed)
497 					dctx->HUFptr = dctx->entropy.hufTable;
498 				memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
499 				return litCSize + lhSize;
500 			}
501 
502 		case set_basic: {
503 			size_t litSize, lhSize;
504 			U32 const lhlCode = ((istart[0]) >> 2) & 3;
505 			switch (lhlCode) {
506 			case 0:
507 			case 2:
508 			default: /* note : default is impossible, since lhlCode into [0..3] */
509 				lhSize = 1;
510 				litSize = istart[0] >> 3;
511 				break;
512 			case 1:
513 				lhSize = 2;
514 				litSize = ZSTD_readLE16(istart) >> 4;
515 				break;
516 			case 3:
517 				lhSize = 3;
518 				litSize = ZSTD_readLE24(istart) >> 4;
519 				break;
520 			}
521 
522 			if (lhSize + litSize + WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */
523 				if (litSize + lhSize > srcSize)
524 					return ERROR(corruption_detected);
525 				memcpy(dctx->litBuffer, istart + lhSize, litSize);
526 				dctx->litPtr = dctx->litBuffer;
527 				dctx->litSize = litSize;
528 				memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
529 				return lhSize + litSize;
530 			}
531 			/* direct reference into compressed stream */
532 			dctx->litPtr = istart + lhSize;
533 			dctx->litSize = litSize;
534 			return lhSize + litSize;
535 		}
536 
537 		case set_rle: {
538 			U32 const lhlCode = ((istart[0]) >> 2) & 3;
539 			size_t litSize, lhSize;
540 			switch (lhlCode) {
541 			case 0:
542 			case 2:
543 			default: /* note : default is impossible, since lhlCode into [0..3] */
544 				lhSize = 1;
545 				litSize = istart[0] >> 3;
546 				break;
547 			case 1:
548 				lhSize = 2;
549 				litSize = ZSTD_readLE16(istart) >> 4;
550 				break;
551 			case 3:
552 				lhSize = 3;
553 				litSize = ZSTD_readLE24(istart) >> 4;
554 				if (srcSize < 4)
555 					return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
556 				break;
557 			}
558 			if (litSize > ZSTD_BLOCKSIZE_ABSOLUTEMAX)
559 				return ERROR(corruption_detected);
560 			memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
561 			dctx->litPtr = dctx->litBuffer;
562 			dctx->litSize = litSize;
563 			return lhSize + 1;
564 		}
565 		default:
566 			return ERROR(corruption_detected); /* impossible */
567 		}
568 	}
569 }
570 
571 typedef union {
572 	FSE_decode_t realData;
573 	U32 alignedBy4;
574 } FSE_decode_t4;
575 
576 static const FSE_decode_t4 LL_defaultDTable[(1 << LL_DEFAULTNORMLOG) + 1] = {
577     {{LL_DEFAULTNORMLOG, 1, 1}}, /* header : tableLog, fastMode, fastMode */
578     {{0, 0, 4}},		 /* 0 : base, symbol, bits */
579     {{16, 0, 4}},
580     {{32, 1, 5}},
581     {{0, 3, 5}},
582     {{0, 4, 5}},
583     {{0, 6, 5}},
584     {{0, 7, 5}},
585     {{0, 9, 5}},
586     {{0, 10, 5}},
587     {{0, 12, 5}},
588     {{0, 14, 6}},
589     {{0, 16, 5}},
590     {{0, 18, 5}},
591     {{0, 19, 5}},
592     {{0, 21, 5}},
593     {{0, 22, 5}},
594     {{0, 24, 5}},
595     {{32, 25, 5}},
596     {{0, 26, 5}},
597     {{0, 27, 6}},
598     {{0, 29, 6}},
599     {{0, 31, 6}},
600     {{32, 0, 4}},
601     {{0, 1, 4}},
602     {{0, 2, 5}},
603     {{32, 4, 5}},
604     {{0, 5, 5}},
605     {{32, 7, 5}},
606     {{0, 8, 5}},
607     {{32, 10, 5}},
608     {{0, 11, 5}},
609     {{0, 13, 6}},
610     {{32, 16, 5}},
611     {{0, 17, 5}},
612     {{32, 19, 5}},
613     {{0, 20, 5}},
614     {{32, 22, 5}},
615     {{0, 23, 5}},
616     {{0, 25, 4}},
617     {{16, 25, 4}},
618     {{32, 26, 5}},
619     {{0, 28, 6}},
620     {{0, 30, 6}},
621     {{48, 0, 4}},
622     {{16, 1, 4}},
623     {{32, 2, 5}},
624     {{32, 3, 5}},
625     {{32, 5, 5}},
626     {{32, 6, 5}},
627     {{32, 8, 5}},
628     {{32, 9, 5}},
629     {{32, 11, 5}},
630     {{32, 12, 5}},
631     {{0, 15, 6}},
632     {{32, 17, 5}},
633     {{32, 18, 5}},
634     {{32, 20, 5}},
635     {{32, 21, 5}},
636     {{32, 23, 5}},
637     {{32, 24, 5}},
638     {{0, 35, 6}},
639     {{0, 34, 6}},
640     {{0, 33, 6}},
641     {{0, 32, 6}},
642 }; /* LL_defaultDTable */
643 
644 static const FSE_decode_t4 ML_defaultDTable[(1 << ML_DEFAULTNORMLOG) + 1] = {
645     {{ML_DEFAULTNORMLOG, 1, 1}}, /* header : tableLog, fastMode, fastMode */
646     {{0, 0, 6}},		 /* 0 : base, symbol, bits */
647     {{0, 1, 4}},
648     {{32, 2, 5}},
649     {{0, 3, 5}},
650     {{0, 5, 5}},
651     {{0, 6, 5}},
652     {{0, 8, 5}},
653     {{0, 10, 6}},
654     {{0, 13, 6}},
655     {{0, 16, 6}},
656     {{0, 19, 6}},
657     {{0, 22, 6}},
658     {{0, 25, 6}},
659     {{0, 28, 6}},
660     {{0, 31, 6}},
661     {{0, 33, 6}},
662     {{0, 35, 6}},
663     {{0, 37, 6}},
664     {{0, 39, 6}},
665     {{0, 41, 6}},
666     {{0, 43, 6}},
667     {{0, 45, 6}},
668     {{16, 1, 4}},
669     {{0, 2, 4}},
670     {{32, 3, 5}},
671     {{0, 4, 5}},
672     {{32, 6, 5}},
673     {{0, 7, 5}},
674     {{0, 9, 6}},
675     {{0, 12, 6}},
676     {{0, 15, 6}},
677     {{0, 18, 6}},
678     {{0, 21, 6}},
679     {{0, 24, 6}},
680     {{0, 27, 6}},
681     {{0, 30, 6}},
682     {{0, 32, 6}},
683     {{0, 34, 6}},
684     {{0, 36, 6}},
685     {{0, 38, 6}},
686     {{0, 40, 6}},
687     {{0, 42, 6}},
688     {{0, 44, 6}},
689     {{32, 1, 4}},
690     {{48, 1, 4}},
691     {{16, 2, 4}},
692     {{32, 4, 5}},
693     {{32, 5, 5}},
694     {{32, 7, 5}},
695     {{32, 8, 5}},
696     {{0, 11, 6}},
697     {{0, 14, 6}},
698     {{0, 17, 6}},
699     {{0, 20, 6}},
700     {{0, 23, 6}},
701     {{0, 26, 6}},
702     {{0, 29, 6}},
703     {{0, 52, 6}},
704     {{0, 51, 6}},
705     {{0, 50, 6}},
706     {{0, 49, 6}},
707     {{0, 48, 6}},
708     {{0, 47, 6}},
709     {{0, 46, 6}},
710 }; /* ML_defaultDTable */
711 
712 static const FSE_decode_t4 OF_defaultDTable[(1 << OF_DEFAULTNORMLOG) + 1] = {
713     {{OF_DEFAULTNORMLOG, 1, 1}}, /* header : tableLog, fastMode, fastMode */
714     {{0, 0, 5}},		 /* 0 : base, symbol, bits */
715     {{0, 6, 4}},
716     {{0, 9, 5}},
717     {{0, 15, 5}},
718     {{0, 21, 5}},
719     {{0, 3, 5}},
720     {{0, 7, 4}},
721     {{0, 12, 5}},
722     {{0, 18, 5}},
723     {{0, 23, 5}},
724     {{0, 5, 5}},
725     {{0, 8, 4}},
726     {{0, 14, 5}},
727     {{0, 20, 5}},
728     {{0, 2, 5}},
729     {{16, 7, 4}},
730     {{0, 11, 5}},
731     {{0, 17, 5}},
732     {{0, 22, 5}},
733     {{0, 4, 5}},
734     {{16, 8, 4}},
735     {{0, 13, 5}},
736     {{0, 19, 5}},
737     {{0, 1, 5}},
738     {{16, 6, 4}},
739     {{0, 10, 5}},
740     {{0, 16, 5}},
741     {{0, 28, 5}},
742     {{0, 27, 5}},
743     {{0, 26, 5}},
744     {{0, 25, 5}},
745     {{0, 24, 5}},
746 }; /* OF_defaultDTable */
747 
748 /*! ZSTD_buildSeqTable() :
749 	@return : nb bytes read from src,
750 			  or an error code if it fails, testable with ZSTD_isError()
751 */
ZSTD_buildSeqTable(FSE_DTable * DTableSpace,const FSE_DTable ** DTablePtr,symbolEncodingType_e type,U32 max,U32 maxLog,const void * src,size_t srcSize,const FSE_decode_t4 * defaultTable,U32 flagRepeatTable,void * workspace,size_t workspaceSize)752 static size_t ZSTD_buildSeqTable(FSE_DTable *DTableSpace, const FSE_DTable **DTablePtr, symbolEncodingType_e type, U32 max, U32 maxLog, const void *src,
753 				 size_t srcSize, const FSE_decode_t4 *defaultTable, U32 flagRepeatTable, void *workspace, size_t workspaceSize)
754 {
755 	const void *const tmpPtr = defaultTable; /* bypass strict aliasing */
756 	switch (type) {
757 	case set_rle:
758 		if (!srcSize)
759 			return ERROR(srcSize_wrong);
760 		if ((*(const BYTE *)src) > max)
761 			return ERROR(corruption_detected);
762 		FSE_buildDTable_rle(DTableSpace, *(const BYTE *)src);
763 		*DTablePtr = DTableSpace;
764 		return 1;
765 	case set_basic: *DTablePtr = (const FSE_DTable *)tmpPtr; return 0;
766 	case set_repeat:
767 		if (!flagRepeatTable)
768 			return ERROR(corruption_detected);
769 		return 0;
770 	default: /* impossible */
771 	case set_compressed: {
772 		U32 tableLog;
773 		S16 *norm = (S16 *)workspace;
774 		size_t const spaceUsed32 = ALIGN(sizeof(S16) * (MaxSeq + 1), sizeof(U32)) >> 2;
775 
776 		if ((spaceUsed32 << 2) > workspaceSize)
777 			return ERROR(GENERIC);
778 		workspace = (U32 *)workspace + spaceUsed32;
779 		workspaceSize -= (spaceUsed32 << 2);
780 		{
781 			size_t const headerSize = FSE_readNCount(norm, &max, &tableLog, src, srcSize);
782 			if (FSE_isError(headerSize))
783 				return ERROR(corruption_detected);
784 			if (tableLog > maxLog)
785 				return ERROR(corruption_detected);
786 			FSE_buildDTable_wksp(DTableSpace, norm, max, tableLog, workspace, workspaceSize);
787 			*DTablePtr = DTableSpace;
788 			return headerSize;
789 		}
790 	}
791 	}
792 }
793 
ZSTD_decodeSeqHeaders(ZSTD_DCtx * dctx,int * nbSeqPtr,const void * src,size_t srcSize)794 size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx *dctx, int *nbSeqPtr, const void *src, size_t srcSize)
795 {
796 	const BYTE *const istart = (const BYTE *const)src;
797 	const BYTE *const iend = istart + srcSize;
798 	const BYTE *ip = istart;
799 
800 	/* check */
801 	if (srcSize < MIN_SEQUENCES_SIZE)
802 		return ERROR(srcSize_wrong);
803 
804 	/* SeqHead */
805 	{
806 		int nbSeq = *ip++;
807 		if (!nbSeq) {
808 			*nbSeqPtr = 0;
809 			return 1;
810 		}
811 		if (nbSeq > 0x7F) {
812 			if (nbSeq == 0xFF) {
813 				if (ip + 2 > iend)
814 					return ERROR(srcSize_wrong);
815 				nbSeq = ZSTD_readLE16(ip) + LONGNBSEQ, ip += 2;
816 			} else {
817 				if (ip >= iend)
818 					return ERROR(srcSize_wrong);
819 				nbSeq = ((nbSeq - 0x80) << 8) + *ip++;
820 			}
821 		}
822 		*nbSeqPtr = nbSeq;
823 	}
824 
825 	/* FSE table descriptors */
826 	if (ip + 4 > iend)
827 		return ERROR(srcSize_wrong); /* minimum possible size */
828 	{
829 		symbolEncodingType_e const LLtype = (symbolEncodingType_e)(*ip >> 6);
830 		symbolEncodingType_e const OFtype = (symbolEncodingType_e)((*ip >> 4) & 3);
831 		symbolEncodingType_e const MLtype = (symbolEncodingType_e)((*ip >> 2) & 3);
832 		ip++;
833 
834 		/* Build DTables */
835 		{
836 			size_t const llhSize = ZSTD_buildSeqTable(dctx->entropy.LLTable, &dctx->LLTptr, LLtype, MaxLL, LLFSELog, ip, iend - ip,
837 								  LL_defaultDTable, dctx->fseEntropy, dctx->entropy.workspace, sizeof(dctx->entropy.workspace));
838 			if (ZSTD_isError(llhSize))
839 				return ERROR(corruption_detected);
840 			ip += llhSize;
841 		}
842 		{
843 			size_t const ofhSize = ZSTD_buildSeqTable(dctx->entropy.OFTable, &dctx->OFTptr, OFtype, MaxOff, OffFSELog, ip, iend - ip,
844 								  OF_defaultDTable, dctx->fseEntropy, dctx->entropy.workspace, sizeof(dctx->entropy.workspace));
845 			if (ZSTD_isError(ofhSize))
846 				return ERROR(corruption_detected);
847 			ip += ofhSize;
848 		}
849 		{
850 			size_t const mlhSize = ZSTD_buildSeqTable(dctx->entropy.MLTable, &dctx->MLTptr, MLtype, MaxML, MLFSELog, ip, iend - ip,
851 								  ML_defaultDTable, dctx->fseEntropy, dctx->entropy.workspace, sizeof(dctx->entropy.workspace));
852 			if (ZSTD_isError(mlhSize))
853 				return ERROR(corruption_detected);
854 			ip += mlhSize;
855 		}
856 	}
857 
858 	return ip - istart;
859 }
860 
861 typedef struct {
862 	size_t litLength;
863 	size_t matchLength;
864 	size_t offset;
865 	const BYTE *match;
866 } seq_t;
867 
868 typedef struct {
869 	BIT_DStream_t DStream;
870 	FSE_DState_t stateLL;
871 	FSE_DState_t stateOffb;
872 	FSE_DState_t stateML;
873 	size_t prevOffset[ZSTD_REP_NUM];
874 	const BYTE *base;
875 	size_t pos;
876 	uPtrDiff gotoDict;
877 } seqState_t;
878 
879 FORCE_NOINLINE
ZSTD_execSequenceLast7(BYTE * op,BYTE * const oend,seq_t sequence,const BYTE ** litPtr,const BYTE * const litLimit,const BYTE * const base,const BYTE * const vBase,const BYTE * const dictEnd)880 size_t ZSTD_execSequenceLast7(BYTE *op, BYTE *const oend, seq_t sequence, const BYTE **litPtr, const BYTE *const litLimit, const BYTE *const base,
881 			      const BYTE *const vBase, const BYTE *const dictEnd)
882 {
883 	BYTE *const oLitEnd = op + sequence.litLength;
884 	size_t const sequenceLength = sequence.litLength + sequence.matchLength;
885 	BYTE *const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
886 	BYTE *const oend_w = oend - WILDCOPY_OVERLENGTH;
887 	const BYTE *const iLitEnd = *litPtr + sequence.litLength;
888 	const BYTE *match = oLitEnd - sequence.offset;
889 
890 	/* check */
891 	if (oMatchEnd > oend)
892 		return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
893 	if (iLitEnd > litLimit)
894 		return ERROR(corruption_detected); /* over-read beyond lit buffer */
895 	if (oLitEnd <= oend_w)
896 		return ERROR(GENERIC); /* Precondition */
897 
898 	/* copy literals */
899 	if (op < oend_w) {
900 		ZSTD_wildcopy(op, *litPtr, oend_w - op);
901 		*litPtr += oend_w - op;
902 		op = oend_w;
903 	}
904 	while (op < oLitEnd)
905 		*op++ = *(*litPtr)++;
906 
907 	/* copy Match */
908 	if (sequence.offset > (size_t)(oLitEnd - base)) {
909 		/* offset beyond prefix */
910 		if (sequence.offset > (size_t)(oLitEnd - vBase))
911 			return ERROR(corruption_detected);
912 		match = dictEnd - (base - match);
913 		if (match + sequence.matchLength <= dictEnd) {
914 			memmove(oLitEnd, match, sequence.matchLength);
915 			return sequenceLength;
916 		}
917 		/* span extDict & currPrefixSegment */
918 		{
919 			size_t const length1 = dictEnd - match;
920 			memmove(oLitEnd, match, length1);
921 			op = oLitEnd + length1;
922 			sequence.matchLength -= length1;
923 			match = base;
924 		}
925 	}
926 	while (op < oMatchEnd)
927 		*op++ = *match++;
928 	return sequenceLength;
929 }
930 
ZSTD_decodeSequence(seqState_t * seqState)931 static seq_t ZSTD_decodeSequence(seqState_t *seqState)
932 {
933 	seq_t seq;
934 
935 	U32 const llCode = FSE_peekSymbol(&seqState->stateLL);
936 	U32 const mlCode = FSE_peekSymbol(&seqState->stateML);
937 	U32 const ofCode = FSE_peekSymbol(&seqState->stateOffb); /* <= maxOff, by table construction */
938 
939 	U32 const llBits = LL_bits[llCode];
940 	U32 const mlBits = ML_bits[mlCode];
941 	U32 const ofBits = ofCode;
942 	U32 const totalBits = llBits + mlBits + ofBits;
943 
944 	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,
945 					       20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000};
946 
947 	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,
948 					       21, 22, 23, 24, 25, 26, 27, 28,   29,    30,    31,    32,    33,     34,     35,     37,     39,     41,
949 					       43, 47, 51, 59, 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803, 0x1003, 0x2003, 0x4003, 0x8003, 0x10003};
950 
951 	static const U32 OF_base[MaxOff + 1] = {0,       1,	1,	5,	0xD,      0x1D,      0x3D,      0x7D,      0xFD,     0x1FD,
952 						0x3FD,   0x7FD,    0xFFD,    0x1FFD,   0x3FFD,   0x7FFD,    0xFFFD,    0x1FFFD,   0x3FFFD,  0x7FFFD,
953 						0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD, 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD};
954 
955 	/* sequence */
956 	{
957 		size_t offset;
958 		if (!ofCode)
959 			offset = 0;
960 		else {
961 			offset = OF_base[ofCode] + BIT_readBitsFast(&seqState->DStream, ofBits); /* <=  (ZSTD_WINDOWLOG_MAX-1) bits */
962 			if (ZSTD_32bits())
963 				BIT_reloadDStream(&seqState->DStream);
964 		}
965 
966 		if (ofCode <= 1) {
967 			offset += (llCode == 0);
968 			if (offset) {
969 				size_t temp = (offset == 3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
970 				temp += !temp; /* 0 is not valid; input is corrupted; force offset to 1 */
971 				if (offset != 1)
972 					seqState->prevOffset[2] = seqState->prevOffset[1];
973 				seqState->prevOffset[1] = seqState->prevOffset[0];
974 				seqState->prevOffset[0] = offset = temp;
975 			} else {
976 				offset = seqState->prevOffset[0];
977 			}
978 		} else {
979 			seqState->prevOffset[2] = seqState->prevOffset[1];
980 			seqState->prevOffset[1] = seqState->prevOffset[0];
981 			seqState->prevOffset[0] = offset;
982 		}
983 		seq.offset = offset;
984 	}
985 
986 	seq.matchLength = ML_base[mlCode] + ((mlCode > 31) ? BIT_readBitsFast(&seqState->DStream, mlBits) : 0); /* <=  16 bits */
987 	if (ZSTD_32bits() && (mlBits + llBits > 24))
988 		BIT_reloadDStream(&seqState->DStream);
989 
990 	seq.litLength = LL_base[llCode] + ((llCode > 15) ? BIT_readBitsFast(&seqState->DStream, llBits) : 0); /* <=  16 bits */
991 	if (ZSTD_32bits() || (totalBits > 64 - 7 - (LLFSELog + MLFSELog + OffFSELog)))
992 		BIT_reloadDStream(&seqState->DStream);
993 
994 	/* ANS state update */
995 	FSE_updateState(&seqState->stateLL, &seqState->DStream); /* <=  9 bits */
996 	FSE_updateState(&seqState->stateML, &seqState->DStream); /* <=  9 bits */
997 	if (ZSTD_32bits())
998 		BIT_reloadDStream(&seqState->DStream);		   /* <= 18 bits */
999 	FSE_updateState(&seqState->stateOffb, &seqState->DStream); /* <=  8 bits */
1000 
1001 	seq.match = NULL;
1002 
1003 	return seq;
1004 }
1005 
1006 FORCE_INLINE
ZSTD_execSequence(BYTE * op,BYTE * const oend,seq_t sequence,const BYTE ** litPtr,const BYTE * const litLimit,const BYTE * const base,const BYTE * const vBase,const BYTE * const dictEnd)1007 size_t ZSTD_execSequence(BYTE *op, BYTE *const oend, seq_t sequence, const BYTE **litPtr, const BYTE *const litLimit, const BYTE *const base,
1008 			 const BYTE *const vBase, const BYTE *const dictEnd)
1009 {
1010 	BYTE *const oLitEnd = op + sequence.litLength;
1011 	size_t const sequenceLength = sequence.litLength + sequence.matchLength;
1012 	BYTE *const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
1013 	BYTE *const oend_w = oend - WILDCOPY_OVERLENGTH;
1014 	const BYTE *const iLitEnd = *litPtr + sequence.litLength;
1015 	const BYTE *match = oLitEnd - sequence.offset;
1016 
1017 	/* check */
1018 	if (oMatchEnd > oend)
1019 		return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
1020 	if (iLitEnd > litLimit)
1021 		return ERROR(corruption_detected); /* over-read beyond lit buffer */
1022 	if (oLitEnd > oend_w)
1023 		return ZSTD_execSequenceLast7(op, oend, sequence, litPtr, litLimit, base, vBase, dictEnd);
1024 
1025 	/* copy Literals */
1026 	ZSTD_copy8(op, *litPtr);
1027 	if (sequence.litLength > 8)
1028 		ZSTD_wildcopy(op + 8, (*litPtr) + 8,
1029 			      sequence.litLength - 8); /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
1030 	op = oLitEnd;
1031 	*litPtr = iLitEnd; /* update for next sequence */
1032 
1033 	/* copy Match */
1034 	if (sequence.offset > (size_t)(oLitEnd - base)) {
1035 		/* offset beyond prefix */
1036 		if (sequence.offset > (size_t)(oLitEnd - vBase))
1037 			return ERROR(corruption_detected);
1038 		match = dictEnd + (match - base);
1039 		if (match + sequence.matchLength <= dictEnd) {
1040 			memmove(oLitEnd, match, sequence.matchLength);
1041 			return sequenceLength;
1042 		}
1043 		/* span extDict & currPrefixSegment */
1044 		{
1045 			size_t const length1 = dictEnd - match;
1046 			memmove(oLitEnd, match, length1);
1047 			op = oLitEnd + length1;
1048 			sequence.matchLength -= length1;
1049 			match = base;
1050 			if (op > oend_w || sequence.matchLength < MINMATCH) {
1051 				U32 i;
1052 				for (i = 0; i < sequence.matchLength; ++i)
1053 					op[i] = match[i];
1054 				return sequenceLength;
1055 			}
1056 		}
1057 	}
1058 	/* Requirement: op <= oend_w && sequence.matchLength >= MINMATCH */
1059 
1060 	/* match within prefix */
1061 	if (sequence.offset < 8) {
1062 		/* close range match, overlap */
1063 		static const U32 dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4};   /* added */
1064 		static const int dec64table[] = {8, 8, 8, 7, 8, 9, 10, 11}; /* subtracted */
1065 		int const sub2 = dec64table[sequence.offset];
1066 		op[0] = match[0];
1067 		op[1] = match[1];
1068 		op[2] = match[2];
1069 		op[3] = match[3];
1070 		match += dec32table[sequence.offset];
1071 		ZSTD_copy4(op + 4, match);
1072 		match -= sub2;
1073 	} else {
1074 		ZSTD_copy8(op, match);
1075 	}
1076 	op += 8;
1077 	match += 8;
1078 
1079 	if (oMatchEnd > oend - (16 - MINMATCH)) {
1080 		if (op < oend_w) {
1081 			ZSTD_wildcopy(op, match, oend_w - op);
1082 			match += oend_w - op;
1083 			op = oend_w;
1084 		}
1085 		while (op < oMatchEnd)
1086 			*op++ = *match++;
1087 	} else {
1088 		ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength - 8); /* works even if matchLength < 8 */
1089 	}
1090 	return sequenceLength;
1091 }
1092 
ZSTD_decompressSequences(ZSTD_DCtx * dctx,void * dst,size_t maxDstSize,const void * seqStart,size_t seqSize)1093 static size_t ZSTD_decompressSequences(ZSTD_DCtx *dctx, void *dst, size_t maxDstSize, const void *seqStart, size_t seqSize)
1094 {
1095 	const BYTE *ip = (const BYTE *)seqStart;
1096 	const BYTE *const iend = ip + seqSize;
1097 	BYTE *const ostart = (BYTE * const)dst;
1098 	BYTE *const oend = ostart + maxDstSize;
1099 	BYTE *op = ostart;
1100 	const BYTE *litPtr = dctx->litPtr;
1101 	const BYTE *const litEnd = litPtr + dctx->litSize;
1102 	const BYTE *const base = (const BYTE *)(dctx->base);
1103 	const BYTE *const vBase = (const BYTE *)(dctx->vBase);
1104 	const BYTE *const dictEnd = (const BYTE *)(dctx->dictEnd);
1105 	int nbSeq;
1106 
1107 	/* Build Decoding Tables */
1108 	{
1109 		size_t const seqHSize = ZSTD_decodeSeqHeaders(dctx, &nbSeq, ip, seqSize);
1110 		if (ZSTD_isError(seqHSize))
1111 			return seqHSize;
1112 		ip += seqHSize;
1113 	}
1114 
1115 	/* Regen sequences */
1116 	if (nbSeq) {
1117 		seqState_t seqState;
1118 		dctx->fseEntropy = 1;
1119 		{
1120 			U32 i;
1121 			for (i = 0; i < ZSTD_REP_NUM; i++)
1122 				seqState.prevOffset[i] = dctx->entropy.rep[i];
1123 		}
1124 		CHECK_E(BIT_initDStream(&seqState.DStream, ip, iend - ip), corruption_detected);
1125 		FSE_initDState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
1126 		FSE_initDState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
1127 		FSE_initDState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
1128 
1129 		for (; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && nbSeq;) {
1130 			nbSeq--;
1131 			{
1132 				seq_t const sequence = ZSTD_decodeSequence(&seqState);
1133 				size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd);
1134 				if (ZSTD_isError(oneSeqSize))
1135 					return oneSeqSize;
1136 				op += oneSeqSize;
1137 			}
1138 		}
1139 
1140 		/* check if reached exact end */
1141 		if (nbSeq)
1142 			return ERROR(corruption_detected);
1143 		/* save reps for next block */
1144 		{
1145 			U32 i;
1146 			for (i = 0; i < ZSTD_REP_NUM; i++)
1147 				dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]);
1148 		}
1149 	}
1150 
1151 	/* last literal segment */
1152 	{
1153 		size_t const lastLLSize = litEnd - litPtr;
1154 		if (lastLLSize > (size_t)(oend - op))
1155 			return ERROR(dstSize_tooSmall);
1156 		memcpy(op, litPtr, lastLLSize);
1157 		op += lastLLSize;
1158 	}
1159 
1160 	return op - ostart;
1161 }
1162 
ZSTD_decodeSequenceLong_generic(seqState_t * seqState,int const longOffsets)1163 FORCE_INLINE seq_t ZSTD_decodeSequenceLong_generic(seqState_t *seqState, int const longOffsets)
1164 {
1165 	seq_t seq;
1166 
1167 	U32 const llCode = FSE_peekSymbol(&seqState->stateLL);
1168 	U32 const mlCode = FSE_peekSymbol(&seqState->stateML);
1169 	U32 const ofCode = FSE_peekSymbol(&seqState->stateOffb); /* <= maxOff, by table construction */
1170 
1171 	U32 const llBits = LL_bits[llCode];
1172 	U32 const mlBits = ML_bits[mlCode];
1173 	U32 const ofBits = ofCode;
1174 	U32 const totalBits = llBits + mlBits + ofBits;
1175 
1176 	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,
1177 					       20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000};
1178 
1179 	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,
1180 					       21, 22, 23, 24, 25, 26, 27, 28,   29,    30,    31,    32,    33,     34,     35,     37,     39,     41,
1181 					       43, 47, 51, 59, 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803, 0x1003, 0x2003, 0x4003, 0x8003, 0x10003};
1182 
1183 	static const U32 OF_base[MaxOff + 1] = {0,       1,	1,	5,	0xD,      0x1D,      0x3D,      0x7D,      0xFD,     0x1FD,
1184 						0x3FD,   0x7FD,    0xFFD,    0x1FFD,   0x3FFD,   0x7FFD,    0xFFFD,    0x1FFFD,   0x3FFFD,  0x7FFFD,
1185 						0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD, 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD};
1186 
1187 	/* sequence */
1188 	{
1189 		size_t offset;
1190 		if (!ofCode)
1191 			offset = 0;
1192 		else {
1193 			if (longOffsets) {
1194 				int const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN);
1195 				offset = OF_base[ofCode] + (BIT_readBitsFast(&seqState->DStream, ofBits - extraBits) << extraBits);
1196 				if (ZSTD_32bits() || extraBits)
1197 					BIT_reloadDStream(&seqState->DStream);
1198 				if (extraBits)
1199 					offset += BIT_readBitsFast(&seqState->DStream, extraBits);
1200 			} else {
1201 				offset = OF_base[ofCode] + BIT_readBitsFast(&seqState->DStream, ofBits); /* <=  (ZSTD_WINDOWLOG_MAX-1) bits */
1202 				if (ZSTD_32bits())
1203 					BIT_reloadDStream(&seqState->DStream);
1204 			}
1205 		}
1206 
1207 		if (ofCode <= 1) {
1208 			offset += (llCode == 0);
1209 			if (offset) {
1210 				size_t temp = (offset == 3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
1211 				temp += !temp; /* 0 is not valid; input is corrupted; force offset to 1 */
1212 				if (offset != 1)
1213 					seqState->prevOffset[2] = seqState->prevOffset[1];
1214 				seqState->prevOffset[1] = seqState->prevOffset[0];
1215 				seqState->prevOffset[0] = offset = temp;
1216 			} else {
1217 				offset = seqState->prevOffset[0];
1218 			}
1219 		} else {
1220 			seqState->prevOffset[2] = seqState->prevOffset[1];
1221 			seqState->prevOffset[1] = seqState->prevOffset[0];
1222 			seqState->prevOffset[0] = offset;
1223 		}
1224 		seq.offset = offset;
1225 	}
1226 
1227 	seq.matchLength = ML_base[mlCode] + ((mlCode > 31) ? BIT_readBitsFast(&seqState->DStream, mlBits) : 0); /* <=  16 bits */
1228 	if (ZSTD_32bits() && (mlBits + llBits > 24))
1229 		BIT_reloadDStream(&seqState->DStream);
1230 
1231 	seq.litLength = LL_base[llCode] + ((llCode > 15) ? BIT_readBitsFast(&seqState->DStream, llBits) : 0); /* <=  16 bits */
1232 	if (ZSTD_32bits() || (totalBits > 64 - 7 - (LLFSELog + MLFSELog + OffFSELog)))
1233 		BIT_reloadDStream(&seqState->DStream);
1234 
1235 	{
1236 		size_t const pos = seqState->pos + seq.litLength;
1237 		seq.match = seqState->base + pos - seq.offset; /* single memory segment */
1238 		if (seq.offset > pos)
1239 			seq.match += seqState->gotoDict; /* separate memory segment */
1240 		seqState->pos = pos + seq.matchLength;
1241 	}
1242 
1243 	/* ANS state update */
1244 	FSE_updateState(&seqState->stateLL, &seqState->DStream); /* <=  9 bits */
1245 	FSE_updateState(&seqState->stateML, &seqState->DStream); /* <=  9 bits */
1246 	if (ZSTD_32bits())
1247 		BIT_reloadDStream(&seqState->DStream);		   /* <= 18 bits */
1248 	FSE_updateState(&seqState->stateOffb, &seqState->DStream); /* <=  8 bits */
1249 
1250 	return seq;
1251 }
1252 
ZSTD_decodeSequenceLong(seqState_t * seqState,unsigned const windowSize)1253 static seq_t ZSTD_decodeSequenceLong(seqState_t *seqState, unsigned const windowSize)
1254 {
1255 	if (ZSTD_highbit32(windowSize) > STREAM_ACCUMULATOR_MIN) {
1256 		return ZSTD_decodeSequenceLong_generic(seqState, 1);
1257 	} else {
1258 		return ZSTD_decodeSequenceLong_generic(seqState, 0);
1259 	}
1260 }
1261 
1262 FORCE_INLINE
ZSTD_execSequenceLong(BYTE * op,BYTE * const oend,seq_t sequence,const BYTE ** litPtr,const BYTE * const litLimit,const BYTE * const base,const BYTE * const vBase,const BYTE * const dictEnd)1263 size_t ZSTD_execSequenceLong(BYTE *op, BYTE *const oend, seq_t sequence, const BYTE **litPtr, const BYTE *const litLimit, const BYTE *const base,
1264 			     const BYTE *const vBase, const BYTE *const dictEnd)
1265 {
1266 	BYTE *const oLitEnd = op + sequence.litLength;
1267 	size_t const sequenceLength = sequence.litLength + sequence.matchLength;
1268 	BYTE *const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
1269 	BYTE *const oend_w = oend - WILDCOPY_OVERLENGTH;
1270 	const BYTE *const iLitEnd = *litPtr + sequence.litLength;
1271 	const BYTE *match = sequence.match;
1272 
1273 	/* check */
1274 	if (oMatchEnd > oend)
1275 		return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
1276 	if (iLitEnd > litLimit)
1277 		return ERROR(corruption_detected); /* over-read beyond lit buffer */
1278 	if (oLitEnd > oend_w)
1279 		return ZSTD_execSequenceLast7(op, oend, sequence, litPtr, litLimit, base, vBase, dictEnd);
1280 
1281 	/* copy Literals */
1282 	ZSTD_copy8(op, *litPtr);
1283 	if (sequence.litLength > 8)
1284 		ZSTD_wildcopy(op + 8, (*litPtr) + 8,
1285 			      sequence.litLength - 8); /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
1286 	op = oLitEnd;
1287 	*litPtr = iLitEnd; /* update for next sequence */
1288 
1289 	/* copy Match */
1290 	if (sequence.offset > (size_t)(oLitEnd - base)) {
1291 		/* offset beyond prefix */
1292 		if (sequence.offset > (size_t)(oLitEnd - vBase))
1293 			return ERROR(corruption_detected);
1294 		if (match + sequence.matchLength <= dictEnd) {
1295 			memmove(oLitEnd, match, sequence.matchLength);
1296 			return sequenceLength;
1297 		}
1298 		/* span extDict & currPrefixSegment */
1299 		{
1300 			size_t const length1 = dictEnd - match;
1301 			memmove(oLitEnd, match, length1);
1302 			op = oLitEnd + length1;
1303 			sequence.matchLength -= length1;
1304 			match = base;
1305 			if (op > oend_w || sequence.matchLength < MINMATCH) {
1306 				U32 i;
1307 				for (i = 0; i < sequence.matchLength; ++i)
1308 					op[i] = match[i];
1309 				return sequenceLength;
1310 			}
1311 		}
1312 	}
1313 	/* Requirement: op <= oend_w && sequence.matchLength >= MINMATCH */
1314 
1315 	/* match within prefix */
1316 	if (sequence.offset < 8) {
1317 		/* close range match, overlap */
1318 		static const U32 dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4};   /* added */
1319 		static const int dec64table[] = {8, 8, 8, 7, 8, 9, 10, 11}; /* subtracted */
1320 		int const sub2 = dec64table[sequence.offset];
1321 		op[0] = match[0];
1322 		op[1] = match[1];
1323 		op[2] = match[2];
1324 		op[3] = match[3];
1325 		match += dec32table[sequence.offset];
1326 		ZSTD_copy4(op + 4, match);
1327 		match -= sub2;
1328 	} else {
1329 		ZSTD_copy8(op, match);
1330 	}
1331 	op += 8;
1332 	match += 8;
1333 
1334 	if (oMatchEnd > oend - (16 - MINMATCH)) {
1335 		if (op < oend_w) {
1336 			ZSTD_wildcopy(op, match, oend_w - op);
1337 			match += oend_w - op;
1338 			op = oend_w;
1339 		}
1340 		while (op < oMatchEnd)
1341 			*op++ = *match++;
1342 	} else {
1343 		ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength - 8); /* works even if matchLength < 8 */
1344 	}
1345 	return sequenceLength;
1346 }
1347 
ZSTD_decompressSequencesLong(ZSTD_DCtx * dctx,void * dst,size_t maxDstSize,const void * seqStart,size_t seqSize)1348 static size_t ZSTD_decompressSequencesLong(ZSTD_DCtx *dctx, void *dst, size_t maxDstSize, const void *seqStart, size_t seqSize)
1349 {
1350 	const BYTE *ip = (const BYTE *)seqStart;
1351 	const BYTE *const iend = ip + seqSize;
1352 	BYTE *const ostart = (BYTE * const)dst;
1353 	BYTE *const oend = ostart + maxDstSize;
1354 	BYTE *op = ostart;
1355 	const BYTE *litPtr = dctx->litPtr;
1356 	const BYTE *const litEnd = litPtr + dctx->litSize;
1357 	const BYTE *const base = (const BYTE *)(dctx->base);
1358 	const BYTE *const vBase = (const BYTE *)(dctx->vBase);
1359 	const BYTE *const dictEnd = (const BYTE *)(dctx->dictEnd);
1360 	unsigned const windowSize = dctx->fParams.windowSize;
1361 	int nbSeq;
1362 
1363 	/* Build Decoding Tables */
1364 	{
1365 		size_t const seqHSize = ZSTD_decodeSeqHeaders(dctx, &nbSeq, ip, seqSize);
1366 		if (ZSTD_isError(seqHSize))
1367 			return seqHSize;
1368 		ip += seqHSize;
1369 	}
1370 
1371 	/* Regen sequences */
1372 	if (nbSeq) {
1373 #define STORED_SEQS 4
1374 #define STOSEQ_MASK (STORED_SEQS - 1)
1375 #define ADVANCED_SEQS 4
1376 		seq_t *sequences = (seq_t *)dctx->entropy.workspace;
1377 		int const seqAdvance = MIN(nbSeq, ADVANCED_SEQS);
1378 		seqState_t seqState;
1379 		int seqNb;
1380 		ZSTD_STATIC_ASSERT(sizeof(dctx->entropy.workspace) >= sizeof(seq_t) * STORED_SEQS);
1381 		dctx->fseEntropy = 1;
1382 		{
1383 			U32 i;
1384 			for (i = 0; i < ZSTD_REP_NUM; i++)
1385 				seqState.prevOffset[i] = dctx->entropy.rep[i];
1386 		}
1387 		seqState.base = base;
1388 		seqState.pos = (size_t)(op - base);
1389 		seqState.gotoDict = (uPtrDiff)dictEnd - (uPtrDiff)base; /* cast to avoid undefined behaviour */
1390 		CHECK_E(BIT_initDStream(&seqState.DStream, ip, iend - ip), corruption_detected);
1391 		FSE_initDState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
1392 		FSE_initDState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
1393 		FSE_initDState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
1394 
1395 		/* prepare in advance */
1396 		for (seqNb = 0; (BIT_reloadDStream(&seqState.DStream) <= BIT_DStream_completed) && seqNb < seqAdvance; seqNb++) {
1397 			sequences[seqNb] = ZSTD_decodeSequenceLong(&seqState, windowSize);
1398 		}
1399 		if (seqNb < seqAdvance)
1400 			return ERROR(corruption_detected);
1401 
1402 		/* decode and decompress */
1403 		for (; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && seqNb < nbSeq; seqNb++) {
1404 			seq_t const sequence = ZSTD_decodeSequenceLong(&seqState, windowSize);
1405 			size_t const oneSeqSize =
1406 			    ZSTD_execSequenceLong(op, oend, sequences[(seqNb - ADVANCED_SEQS) & STOSEQ_MASK], &litPtr, litEnd, base, vBase, dictEnd);
1407 			if (ZSTD_isError(oneSeqSize))
1408 				return oneSeqSize;
1409 			ZSTD_PREFETCH(sequence.match);
1410 			sequences[seqNb & STOSEQ_MASK] = sequence;
1411 			op += oneSeqSize;
1412 		}
1413 		if (seqNb < nbSeq)
1414 			return ERROR(corruption_detected);
1415 
1416 		/* finish queue */
1417 		seqNb -= seqAdvance;
1418 		for (; seqNb < nbSeq; seqNb++) {
1419 			size_t const oneSeqSize = ZSTD_execSequenceLong(op, oend, sequences[seqNb & STOSEQ_MASK], &litPtr, litEnd, base, vBase, dictEnd);
1420 			if (ZSTD_isError(oneSeqSize))
1421 				return oneSeqSize;
1422 			op += oneSeqSize;
1423 		}
1424 
1425 		/* save reps for next block */
1426 		{
1427 			U32 i;
1428 			for (i = 0; i < ZSTD_REP_NUM; i++)
1429 				dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]);
1430 		}
1431 	}
1432 
1433 	/* last literal segment */
1434 	{
1435 		size_t const lastLLSize = litEnd - litPtr;
1436 		if (lastLLSize > (size_t)(oend - op))
1437 			return ERROR(dstSize_tooSmall);
1438 		memcpy(op, litPtr, lastLLSize);
1439 		op += lastLLSize;
1440 	}
1441 
1442 	return op - ostart;
1443 }
1444 
ZSTD_decompressBlock_internal(ZSTD_DCtx * dctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize)1445 static size_t ZSTD_decompressBlock_internal(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
1446 { /* blockType == blockCompressed */
1447 	const BYTE *ip = (const BYTE *)src;
1448 
1449 	if (srcSize >= ZSTD_BLOCKSIZE_ABSOLUTEMAX)
1450 		return ERROR(srcSize_wrong);
1451 
1452 	/* Decode literals section */
1453 	{
1454 		size_t const litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize);
1455 		if (ZSTD_isError(litCSize))
1456 			return litCSize;
1457 		ip += litCSize;
1458 		srcSize -= litCSize;
1459 	}
1460 	if (sizeof(size_t) > 4) /* do not enable prefetching on 32-bits x86, as it's performance detrimental */
1461 				/* likely because of register pressure */
1462 				/* if that's the correct cause, then 32-bits ARM should be affected differently */
1463 				/* it would be good to test this on ARM real hardware, to see if prefetch version improves speed */
1464 		if (dctx->fParams.windowSize > (1 << 23))
1465 			return ZSTD_decompressSequencesLong(dctx, dst, dstCapacity, ip, srcSize);
1466 	return ZSTD_decompressSequences(dctx, dst, dstCapacity, ip, srcSize);
1467 }
1468 
ZSTD_checkContinuity(ZSTD_DCtx * dctx,const void * dst)1469 static void ZSTD_checkContinuity(ZSTD_DCtx *dctx, const void *dst)
1470 {
1471 	if (dst != dctx->previousDstEnd) { /* not contiguous */
1472 		dctx->dictEnd = dctx->previousDstEnd;
1473 		dctx->vBase = (const char *)dst - ((const char *)(dctx->previousDstEnd) - (const char *)(dctx->base));
1474 		dctx->base = dst;
1475 		dctx->previousDstEnd = dst;
1476 	}
1477 }
1478 
ZSTD_decompressBlock(ZSTD_DCtx * dctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize)1479 size_t ZSTD_decompressBlock(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
1480 {
1481 	size_t dSize;
1482 	ZSTD_checkContinuity(dctx, dst);
1483 	dSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
1484 	dctx->previousDstEnd = (char *)dst + dSize;
1485 	return dSize;
1486 }
1487 
1488 /** ZSTD_insertBlock() :
1489 	insert `src` block into `dctx` history. Useful to track uncompressed blocks. */
ZSTD_insertBlock(ZSTD_DCtx * dctx,const void * blockStart,size_t blockSize)1490 size_t ZSTD_insertBlock(ZSTD_DCtx *dctx, const void *blockStart, size_t blockSize)
1491 {
1492 	ZSTD_checkContinuity(dctx, blockStart);
1493 	dctx->previousDstEnd = (const char *)blockStart + blockSize;
1494 	return blockSize;
1495 }
1496 
ZSTD_generateNxBytes(void * dst,size_t dstCapacity,BYTE byte,size_t length)1497 size_t ZSTD_generateNxBytes(void *dst, size_t dstCapacity, BYTE byte, size_t length)
1498 {
1499 	if (length > dstCapacity)
1500 		return ERROR(dstSize_tooSmall);
1501 	memset(dst, byte, length);
1502 	return length;
1503 }
1504 
1505 /** ZSTD_findFrameCompressedSize() :
1506  *  compatible with legacy mode
1507  *  `src` must point to the start of a ZSTD frame, ZSTD legacy frame, or skippable frame
1508  *  `srcSize` must be at least as large as the frame contained
1509  *  @return : the compressed size of the frame starting at `src` */
ZSTD_findFrameCompressedSize(const void * src,size_t srcSize)1510 size_t ZSTD_findFrameCompressedSize(const void *src, size_t srcSize)
1511 {
1512 	if (srcSize >= ZSTD_skippableHeaderSize && (ZSTD_readLE32(src) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
1513 		return ZSTD_skippableHeaderSize + ZSTD_readLE32((const BYTE *)src + 4);
1514 	} else {
1515 		const BYTE *ip = (const BYTE *)src;
1516 		const BYTE *const ipstart = ip;
1517 		size_t remainingSize = srcSize;
1518 		ZSTD_frameParams fParams;
1519 
1520 		size_t const headerSize = ZSTD_frameHeaderSize(ip, remainingSize);
1521 		if (ZSTD_isError(headerSize))
1522 			return headerSize;
1523 
1524 		/* Frame Header */
1525 		{
1526 			size_t const ret = ZSTD_getFrameParams(&fParams, ip, remainingSize);
1527 			if (ZSTD_isError(ret))
1528 				return ret;
1529 			if (ret > 0)
1530 				return ERROR(srcSize_wrong);
1531 		}
1532 
1533 		ip += headerSize;
1534 		remainingSize -= headerSize;
1535 
1536 		/* Loop on each block */
1537 		while (1) {
1538 			blockProperties_t blockProperties;
1539 			size_t const cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
1540 			if (ZSTD_isError(cBlockSize))
1541 				return cBlockSize;
1542 
1543 			if (ZSTD_blockHeaderSize + cBlockSize > remainingSize)
1544 				return ERROR(srcSize_wrong);
1545 
1546 			ip += ZSTD_blockHeaderSize + cBlockSize;
1547 			remainingSize -= ZSTD_blockHeaderSize + cBlockSize;
1548 
1549 			if (blockProperties.lastBlock)
1550 				break;
1551 		}
1552 
1553 		if (fParams.checksumFlag) { /* Frame content checksum */
1554 			if (remainingSize < 4)
1555 				return ERROR(srcSize_wrong);
1556 			ip += 4;
1557 			remainingSize -= 4;
1558 		}
1559 
1560 		return ip - ipstart;
1561 	}
1562 }
1563 
1564 /*! ZSTD_decompressFrame() :
1565 *   @dctx must be properly initialized */
ZSTD_decompressFrame(ZSTD_DCtx * dctx,void * dst,size_t dstCapacity,const void ** srcPtr,size_t * srcSizePtr)1566 static size_t ZSTD_decompressFrame(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void **srcPtr, size_t *srcSizePtr)
1567 {
1568 	const BYTE *ip = (const BYTE *)(*srcPtr);
1569 	BYTE *const ostart = (BYTE * const)dst;
1570 	BYTE *const oend = ostart + dstCapacity;
1571 	BYTE *op = ostart;
1572 	size_t remainingSize = *srcSizePtr;
1573 
1574 	/* check */
1575 	if (remainingSize < ZSTD_frameHeaderSize_min + ZSTD_blockHeaderSize)
1576 		return ERROR(srcSize_wrong);
1577 
1578 	/* Frame Header */
1579 	{
1580 		size_t const frameHeaderSize = ZSTD_frameHeaderSize(ip, ZSTD_frameHeaderSize_prefix);
1581 		if (ZSTD_isError(frameHeaderSize))
1582 			return frameHeaderSize;
1583 		if (remainingSize < frameHeaderSize + ZSTD_blockHeaderSize)
1584 			return ERROR(srcSize_wrong);
1585 		CHECK_F(ZSTD_decodeFrameHeader(dctx, ip, frameHeaderSize));
1586 		ip += frameHeaderSize;
1587 		remainingSize -= frameHeaderSize;
1588 	}
1589 
1590 	/* Loop on each block */
1591 	while (1) {
1592 		size_t decodedSize;
1593 		blockProperties_t blockProperties;
1594 		size_t const cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
1595 		if (ZSTD_isError(cBlockSize))
1596 			return cBlockSize;
1597 
1598 		ip += ZSTD_blockHeaderSize;
1599 		remainingSize -= ZSTD_blockHeaderSize;
1600 		if (cBlockSize > remainingSize)
1601 			return ERROR(srcSize_wrong);
1602 
1603 		switch (blockProperties.blockType) {
1604 		case bt_compressed: decodedSize = ZSTD_decompressBlock_internal(dctx, op, oend - op, ip, cBlockSize); break;
1605 		case bt_raw: decodedSize = ZSTD_copyRawBlock(op, oend - op, ip, cBlockSize); break;
1606 		case bt_rle: decodedSize = ZSTD_generateNxBytes(op, oend - op, *ip, blockProperties.origSize); break;
1607 		case bt_reserved:
1608 		default: return ERROR(corruption_detected);
1609 		}
1610 
1611 		if (ZSTD_isError(decodedSize))
1612 			return decodedSize;
1613 		if (dctx->fParams.checksumFlag)
1614 			xxh64_update(&dctx->xxhState, op, decodedSize);
1615 		op += decodedSize;
1616 		ip += cBlockSize;
1617 		remainingSize -= cBlockSize;
1618 		if (blockProperties.lastBlock)
1619 			break;
1620 	}
1621 
1622 	if (dctx->fParams.checksumFlag) { /* Frame content checksum verification */
1623 		U32 const checkCalc = (U32)xxh64_digest(&dctx->xxhState);
1624 		U32 checkRead;
1625 		if (remainingSize < 4)
1626 			return ERROR(checksum_wrong);
1627 		checkRead = ZSTD_readLE32(ip);
1628 		if (checkRead != checkCalc)
1629 			return ERROR(checksum_wrong);
1630 		ip += 4;
1631 		remainingSize -= 4;
1632 	}
1633 
1634 	/* Allow caller to get size read */
1635 	*srcPtr = ip;
1636 	*srcSizePtr = remainingSize;
1637 	return op - ostart;
1638 }
1639 
1640 static const void *ZSTD_DDictDictContent(const ZSTD_DDict *ddict);
1641 static size_t ZSTD_DDictDictSize(const ZSTD_DDict *ddict);
1642 
ZSTD_decompressMultiFrame(ZSTD_DCtx * dctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize,const void * dict,size_t dictSize,const ZSTD_DDict * ddict)1643 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,
1644 					const ZSTD_DDict *ddict)
1645 {
1646 	void *const dststart = dst;
1647 
1648 	if (ddict) {
1649 		if (dict) {
1650 			/* programmer error, these two cases should be mutually exclusive */
1651 			return ERROR(GENERIC);
1652 		}
1653 
1654 		dict = ZSTD_DDictDictContent(ddict);
1655 		dictSize = ZSTD_DDictDictSize(ddict);
1656 	}
1657 
1658 	while (srcSize >= ZSTD_frameHeaderSize_prefix) {
1659 		U32 magicNumber;
1660 
1661 		magicNumber = ZSTD_readLE32(src);
1662 		if (magicNumber != ZSTD_MAGICNUMBER) {
1663 			if ((magicNumber & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
1664 				size_t skippableSize;
1665 				if (srcSize < ZSTD_skippableHeaderSize)
1666 					return ERROR(srcSize_wrong);
1667 				skippableSize = ZSTD_readLE32((const BYTE *)src + 4) + ZSTD_skippableHeaderSize;
1668 				if (srcSize < skippableSize) {
1669 					return ERROR(srcSize_wrong);
1670 				}
1671 
1672 				src = (const BYTE *)src + skippableSize;
1673 				srcSize -= skippableSize;
1674 				continue;
1675 			} else {
1676 				return ERROR(prefix_unknown);
1677 			}
1678 		}
1679 
1680 		if (ddict) {
1681 			/* we were called from ZSTD_decompress_usingDDict */
1682 			ZSTD_refDDict(dctx, ddict);
1683 		} else {
1684 			/* this will initialize correctly with no dict if dict == NULL, so
1685 			 * use this in all cases but ddict */
1686 			CHECK_F(ZSTD_decompressBegin_usingDict(dctx, dict, dictSize));
1687 		}
1688 		ZSTD_checkContinuity(dctx, dst);
1689 
1690 		{
1691 			const size_t res = ZSTD_decompressFrame(dctx, dst, dstCapacity, &src, &srcSize);
1692 			if (ZSTD_isError(res))
1693 				return res;
1694 			/* don't need to bounds check this, ZSTD_decompressFrame will have
1695 			 * already */
1696 			dst = (BYTE *)dst + res;
1697 			dstCapacity -= res;
1698 		}
1699 	}
1700 
1701 	if (srcSize)
1702 		return ERROR(srcSize_wrong); /* input not entirely consumed */
1703 
1704 	return (BYTE *)dst - (BYTE *)dststart;
1705 }
1706 
ZSTD_decompress_usingDict(ZSTD_DCtx * dctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize,const void * dict,size_t dictSize)1707 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)
1708 {
1709 	return ZSTD_decompressMultiFrame(dctx, dst, dstCapacity, src, srcSize, dict, dictSize, NULL);
1710 }
1711 
ZSTD_decompressDCtx(ZSTD_DCtx * dctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize)1712 size_t ZSTD_decompressDCtx(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
1713 {
1714 	return ZSTD_decompress_usingDict(dctx, dst, dstCapacity, src, srcSize, NULL, 0);
1715 }
1716 
1717 /*-**************************************
1718 *   Advanced Streaming Decompression API
1719 *   Bufferless and synchronous
1720 ****************************************/
ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx * dctx)1721 size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx *dctx) { return dctx->expected; }
1722 
ZSTD_nextInputType(ZSTD_DCtx * dctx)1723 ZSTD_nextInputType_e ZSTD_nextInputType(ZSTD_DCtx *dctx)
1724 {
1725 	switch (dctx->stage) {
1726 	default: /* should not happen */
1727 	case ZSTDds_getFrameHeaderSize:
1728 	case ZSTDds_decodeFrameHeader: return ZSTDnit_frameHeader;
1729 	case ZSTDds_decodeBlockHeader: return ZSTDnit_blockHeader;
1730 	case ZSTDds_decompressBlock: return ZSTDnit_block;
1731 	case ZSTDds_decompressLastBlock: return ZSTDnit_lastBlock;
1732 	case ZSTDds_checkChecksum: return ZSTDnit_checksum;
1733 	case ZSTDds_decodeSkippableHeader:
1734 	case ZSTDds_skipFrame: return ZSTDnit_skippableFrame;
1735 	}
1736 }
1737 
ZSTD_isSkipFrame(ZSTD_DCtx * dctx)1738 int ZSTD_isSkipFrame(ZSTD_DCtx *dctx) { return dctx->stage == ZSTDds_skipFrame; } /* for zbuff */
1739 
1740 /** ZSTD_decompressContinue() :
1741 *   @return : nb of bytes generated into `dst` (necessarily <= `dstCapacity)
1742 *             or an error code, which can be tested using ZSTD_isError() */
ZSTD_decompressContinue(ZSTD_DCtx * dctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize)1743 size_t ZSTD_decompressContinue(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
1744 {
1745 	/* Sanity check */
1746 	if (srcSize != dctx->expected)
1747 		return ERROR(srcSize_wrong);
1748 	if (dstCapacity)
1749 		ZSTD_checkContinuity(dctx, dst);
1750 
1751 	switch (dctx->stage) {
1752 	case ZSTDds_getFrameHeaderSize:
1753 		if (srcSize != ZSTD_frameHeaderSize_prefix)
1754 			return ERROR(srcSize_wrong);					/* impossible */
1755 		if ((ZSTD_readLE32(src) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) { /* skippable frame */
1756 			memcpy(dctx->headerBuffer, src, ZSTD_frameHeaderSize_prefix);
1757 			dctx->expected = ZSTD_skippableHeaderSize - ZSTD_frameHeaderSize_prefix; /* magic number + skippable frame length */
1758 			dctx->stage = ZSTDds_decodeSkippableHeader;
1759 			return 0;
1760 		}
1761 		dctx->headerSize = ZSTD_frameHeaderSize(src, ZSTD_frameHeaderSize_prefix);
1762 		if (ZSTD_isError(dctx->headerSize))
1763 			return dctx->headerSize;
1764 		memcpy(dctx->headerBuffer, src, ZSTD_frameHeaderSize_prefix);
1765 		if (dctx->headerSize > ZSTD_frameHeaderSize_prefix) {
1766 			dctx->expected = dctx->headerSize - ZSTD_frameHeaderSize_prefix;
1767 			dctx->stage = ZSTDds_decodeFrameHeader;
1768 			return 0;
1769 		}
1770 		dctx->expected = 0; /* not necessary to copy more */
1771 		fallthrough;
1772 
1773 	case ZSTDds_decodeFrameHeader:
1774 		memcpy(dctx->headerBuffer + ZSTD_frameHeaderSize_prefix, src, dctx->expected);
1775 		CHECK_F(ZSTD_decodeFrameHeader(dctx, dctx->headerBuffer, dctx->headerSize));
1776 		dctx->expected = ZSTD_blockHeaderSize;
1777 		dctx->stage = ZSTDds_decodeBlockHeader;
1778 		return 0;
1779 
1780 	case ZSTDds_decodeBlockHeader: {
1781 		blockProperties_t bp;
1782 		size_t const cBlockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
1783 		if (ZSTD_isError(cBlockSize))
1784 			return cBlockSize;
1785 		dctx->expected = cBlockSize;
1786 		dctx->bType = bp.blockType;
1787 		dctx->rleSize = bp.origSize;
1788 		if (cBlockSize) {
1789 			dctx->stage = bp.lastBlock ? ZSTDds_decompressLastBlock : ZSTDds_decompressBlock;
1790 			return 0;
1791 		}
1792 		/* empty block */
1793 		if (bp.lastBlock) {
1794 			if (dctx->fParams.checksumFlag) {
1795 				dctx->expected = 4;
1796 				dctx->stage = ZSTDds_checkChecksum;
1797 			} else {
1798 				dctx->expected = 0; /* end of frame */
1799 				dctx->stage = ZSTDds_getFrameHeaderSize;
1800 			}
1801 		} else {
1802 			dctx->expected = 3; /* go directly to next header */
1803 			dctx->stage = ZSTDds_decodeBlockHeader;
1804 		}
1805 		return 0;
1806 	}
1807 	case ZSTDds_decompressLastBlock:
1808 	case ZSTDds_decompressBlock: {
1809 		size_t rSize;
1810 		switch (dctx->bType) {
1811 		case bt_compressed: rSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize); break;
1812 		case bt_raw: rSize = ZSTD_copyRawBlock(dst, dstCapacity, src, srcSize); break;
1813 		case bt_rle: rSize = ZSTD_setRleBlock(dst, dstCapacity, src, srcSize, dctx->rleSize); break;
1814 		case bt_reserved: /* should never happen */
1815 		default: return ERROR(corruption_detected);
1816 		}
1817 		if (ZSTD_isError(rSize))
1818 			return rSize;
1819 		if (dctx->fParams.checksumFlag)
1820 			xxh64_update(&dctx->xxhState, dst, rSize);
1821 
1822 		if (dctx->stage == ZSTDds_decompressLastBlock) { /* end of frame */
1823 			if (dctx->fParams.checksumFlag) {	/* another round for frame checksum */
1824 				dctx->expected = 4;
1825 				dctx->stage = ZSTDds_checkChecksum;
1826 			} else {
1827 				dctx->expected = 0; /* ends here */
1828 				dctx->stage = ZSTDds_getFrameHeaderSize;
1829 			}
1830 		} else {
1831 			dctx->stage = ZSTDds_decodeBlockHeader;
1832 			dctx->expected = ZSTD_blockHeaderSize;
1833 			dctx->previousDstEnd = (char *)dst + rSize;
1834 		}
1835 		return rSize;
1836 	}
1837 	case ZSTDds_checkChecksum: {
1838 		U32 const h32 = (U32)xxh64_digest(&dctx->xxhState);
1839 		U32 const check32 = ZSTD_readLE32(src); /* srcSize == 4, guaranteed by dctx->expected */
1840 		if (check32 != h32)
1841 			return ERROR(checksum_wrong);
1842 		dctx->expected = 0;
1843 		dctx->stage = ZSTDds_getFrameHeaderSize;
1844 		return 0;
1845 	}
1846 	case ZSTDds_decodeSkippableHeader: {
1847 		memcpy(dctx->headerBuffer + ZSTD_frameHeaderSize_prefix, src, dctx->expected);
1848 		dctx->expected = ZSTD_readLE32(dctx->headerBuffer + 4);
1849 		dctx->stage = ZSTDds_skipFrame;
1850 		return 0;
1851 	}
1852 	case ZSTDds_skipFrame: {
1853 		dctx->expected = 0;
1854 		dctx->stage = ZSTDds_getFrameHeaderSize;
1855 		return 0;
1856 	}
1857 	default:
1858 		return ERROR(GENERIC); /* impossible */
1859 	}
1860 }
1861 
ZSTD_refDictContent(ZSTD_DCtx * dctx,const void * dict,size_t dictSize)1862 static size_t ZSTD_refDictContent(ZSTD_DCtx *dctx, const void *dict, size_t dictSize)
1863 {
1864 	dctx->dictEnd = dctx->previousDstEnd;
1865 	dctx->vBase = (const char *)dict - ((const char *)(dctx->previousDstEnd) - (const char *)(dctx->base));
1866 	dctx->base = dict;
1867 	dctx->previousDstEnd = (const char *)dict + dictSize;
1868 	return 0;
1869 }
1870 
1871 /* ZSTD_loadEntropy() :
1872  * dict : must point at beginning of a valid zstd dictionary
1873  * @return : size of entropy tables read */
ZSTD_loadEntropy(ZSTD_entropyTables_t * entropy,const void * const dict,size_t const dictSize)1874 static size_t ZSTD_loadEntropy(ZSTD_entropyTables_t *entropy, const void *const dict, size_t const dictSize)
1875 {
1876 	const BYTE *dictPtr = (const BYTE *)dict;
1877 	const BYTE *const dictEnd = dictPtr + dictSize;
1878 
1879 	if (dictSize <= 8)
1880 		return ERROR(dictionary_corrupted);
1881 	dictPtr += 8; /* skip header = magic + dictID */
1882 
1883 	{
1884 		size_t const hSize = HUF_readDTableX4_wksp(entropy->hufTable, dictPtr, dictEnd - dictPtr, entropy->workspace, sizeof(entropy->workspace));
1885 		if (HUF_isError(hSize))
1886 			return ERROR(dictionary_corrupted);
1887 		dictPtr += hSize;
1888 	}
1889 
1890 	{
1891 		short offcodeNCount[MaxOff + 1];
1892 		U32 offcodeMaxValue = MaxOff, offcodeLog;
1893 		size_t const offcodeHeaderSize = FSE_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dictPtr, dictEnd - dictPtr);
1894 		if (FSE_isError(offcodeHeaderSize))
1895 			return ERROR(dictionary_corrupted);
1896 		if (offcodeLog > OffFSELog)
1897 			return ERROR(dictionary_corrupted);
1898 		CHECK_E(FSE_buildDTable_wksp(entropy->OFTable, offcodeNCount, offcodeMaxValue, offcodeLog, entropy->workspace, sizeof(entropy->workspace)), dictionary_corrupted);
1899 		dictPtr += offcodeHeaderSize;
1900 	}
1901 
1902 	{
1903 		short matchlengthNCount[MaxML + 1];
1904 		unsigned matchlengthMaxValue = MaxML, matchlengthLog;
1905 		size_t const matchlengthHeaderSize = FSE_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd - dictPtr);
1906 		if (FSE_isError(matchlengthHeaderSize))
1907 			return ERROR(dictionary_corrupted);
1908 		if (matchlengthLog > MLFSELog)
1909 			return ERROR(dictionary_corrupted);
1910 		CHECK_E(FSE_buildDTable_wksp(entropy->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog, entropy->workspace, sizeof(entropy->workspace)), dictionary_corrupted);
1911 		dictPtr += matchlengthHeaderSize;
1912 	}
1913 
1914 	{
1915 		short litlengthNCount[MaxLL + 1];
1916 		unsigned litlengthMaxValue = MaxLL, litlengthLog;
1917 		size_t const litlengthHeaderSize = FSE_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd - dictPtr);
1918 		if (FSE_isError(litlengthHeaderSize))
1919 			return ERROR(dictionary_corrupted);
1920 		if (litlengthLog > LLFSELog)
1921 			return ERROR(dictionary_corrupted);
1922 		CHECK_E(FSE_buildDTable_wksp(entropy->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog, entropy->workspace, sizeof(entropy->workspace)), dictionary_corrupted);
1923 		dictPtr += litlengthHeaderSize;
1924 	}
1925 
1926 	if (dictPtr + 12 > dictEnd)
1927 		return ERROR(dictionary_corrupted);
1928 	{
1929 		int i;
1930 		size_t const dictContentSize = (size_t)(dictEnd - (dictPtr + 12));
1931 		for (i = 0; i < 3; i++) {
1932 			U32 const rep = ZSTD_readLE32(dictPtr);
1933 			dictPtr += 4;
1934 			if (rep == 0 || rep >= dictContentSize)
1935 				return ERROR(dictionary_corrupted);
1936 			entropy->rep[i] = rep;
1937 		}
1938 	}
1939 
1940 	return dictPtr - (const BYTE *)dict;
1941 }
1942 
ZSTD_decompress_insertDictionary(ZSTD_DCtx * dctx,const void * dict,size_t dictSize)1943 static size_t ZSTD_decompress_insertDictionary(ZSTD_DCtx *dctx, const void *dict, size_t dictSize)
1944 {
1945 	if (dictSize < 8)
1946 		return ZSTD_refDictContent(dctx, dict, dictSize);
1947 	{
1948 		U32 const magic = ZSTD_readLE32(dict);
1949 		if (magic != ZSTD_DICT_MAGIC) {
1950 			return ZSTD_refDictContent(dctx, dict, dictSize); /* pure content mode */
1951 		}
1952 	}
1953 	dctx->dictID = ZSTD_readLE32((const char *)dict + 4);
1954 
1955 	/* load entropy tables */
1956 	{
1957 		size_t const eSize = ZSTD_loadEntropy(&dctx->entropy, dict, dictSize);
1958 		if (ZSTD_isError(eSize))
1959 			return ERROR(dictionary_corrupted);
1960 		dict = (const char *)dict + eSize;
1961 		dictSize -= eSize;
1962 	}
1963 	dctx->litEntropy = dctx->fseEntropy = 1;
1964 
1965 	/* reference dictionary content */
1966 	return ZSTD_refDictContent(dctx, dict, dictSize);
1967 }
1968 
ZSTD_decompressBegin_usingDict(ZSTD_DCtx * dctx,const void * dict,size_t dictSize)1969 size_t ZSTD_decompressBegin_usingDict(ZSTD_DCtx *dctx, const void *dict, size_t dictSize)
1970 {
1971 	CHECK_F(ZSTD_decompressBegin(dctx));
1972 	if (dict && dictSize)
1973 		CHECK_E(ZSTD_decompress_insertDictionary(dctx, dict, dictSize), dictionary_corrupted);
1974 	return 0;
1975 }
1976 
1977 /* ======   ZSTD_DDict   ====== */
1978 
1979 struct ZSTD_DDict_s {
1980 	void *dictBuffer;
1981 	const void *dictContent;
1982 	size_t dictSize;
1983 	ZSTD_entropyTables_t entropy;
1984 	U32 dictID;
1985 	U32 entropyPresent;
1986 	ZSTD_customMem cMem;
1987 }; /* typedef'd to ZSTD_DDict within "zstd.h" */
1988 
ZSTD_DDictWorkspaceBound(void)1989 size_t ZSTD_DDictWorkspaceBound(void) { return ZSTD_ALIGN(sizeof(ZSTD_stack)) + ZSTD_ALIGN(sizeof(ZSTD_DDict)); }
1990 
ZSTD_DDictDictContent(const ZSTD_DDict * ddict)1991 static const void *ZSTD_DDictDictContent(const ZSTD_DDict *ddict) { return ddict->dictContent; }
1992 
ZSTD_DDictDictSize(const ZSTD_DDict * ddict)1993 static size_t ZSTD_DDictDictSize(const ZSTD_DDict *ddict) { return ddict->dictSize; }
1994 
ZSTD_refDDict(ZSTD_DCtx * dstDCtx,const ZSTD_DDict * ddict)1995 static void ZSTD_refDDict(ZSTD_DCtx *dstDCtx, const ZSTD_DDict *ddict)
1996 {
1997 	ZSTD_decompressBegin(dstDCtx); /* init */
1998 	if (ddict) {		       /* support refDDict on NULL */
1999 		dstDCtx->dictID = ddict->dictID;
2000 		dstDCtx->base = ddict->dictContent;
2001 		dstDCtx->vBase = ddict->dictContent;
2002 		dstDCtx->dictEnd = (const BYTE *)ddict->dictContent + ddict->dictSize;
2003 		dstDCtx->previousDstEnd = dstDCtx->dictEnd;
2004 		if (ddict->entropyPresent) {
2005 			dstDCtx->litEntropy = 1;
2006 			dstDCtx->fseEntropy = 1;
2007 			dstDCtx->LLTptr = ddict->entropy.LLTable;
2008 			dstDCtx->MLTptr = ddict->entropy.MLTable;
2009 			dstDCtx->OFTptr = ddict->entropy.OFTable;
2010 			dstDCtx->HUFptr = ddict->entropy.hufTable;
2011 			dstDCtx->entropy.rep[0] = ddict->entropy.rep[0];
2012 			dstDCtx->entropy.rep[1] = ddict->entropy.rep[1];
2013 			dstDCtx->entropy.rep[2] = ddict->entropy.rep[2];
2014 		} else {
2015 			dstDCtx->litEntropy = 0;
2016 			dstDCtx->fseEntropy = 0;
2017 		}
2018 	}
2019 }
2020 
ZSTD_loadEntropy_inDDict(ZSTD_DDict * ddict)2021 static size_t ZSTD_loadEntropy_inDDict(ZSTD_DDict *ddict)
2022 {
2023 	ddict->dictID = 0;
2024 	ddict->entropyPresent = 0;
2025 	if (ddict->dictSize < 8)
2026 		return 0;
2027 	{
2028 		U32 const magic = ZSTD_readLE32(ddict->dictContent);
2029 		if (magic != ZSTD_DICT_MAGIC)
2030 			return 0; /* pure content mode */
2031 	}
2032 	ddict->dictID = ZSTD_readLE32((const char *)ddict->dictContent + 4);
2033 
2034 	/* load entropy tables */
2035 	CHECK_E(ZSTD_loadEntropy(&ddict->entropy, ddict->dictContent, ddict->dictSize), dictionary_corrupted);
2036 	ddict->entropyPresent = 1;
2037 	return 0;
2038 }
2039 
ZSTD_createDDict_advanced(const void * dict,size_t dictSize,unsigned byReference,ZSTD_customMem customMem)2040 static ZSTD_DDict *ZSTD_createDDict_advanced(const void *dict, size_t dictSize, unsigned byReference, ZSTD_customMem customMem)
2041 {
2042 	if (!customMem.customAlloc || !customMem.customFree)
2043 		return NULL;
2044 
2045 	{
2046 		ZSTD_DDict *const ddict = (ZSTD_DDict *)ZSTD_malloc(sizeof(ZSTD_DDict), customMem);
2047 		if (!ddict)
2048 			return NULL;
2049 		ddict->cMem = customMem;
2050 
2051 		if ((byReference) || (!dict) || (!dictSize)) {
2052 			ddict->dictBuffer = NULL;
2053 			ddict->dictContent = dict;
2054 		} else {
2055 			void *const internalBuffer = ZSTD_malloc(dictSize, customMem);
2056 			if (!internalBuffer) {
2057 				ZSTD_freeDDict(ddict);
2058 				return NULL;
2059 			}
2060 			memcpy(internalBuffer, dict, dictSize);
2061 			ddict->dictBuffer = internalBuffer;
2062 			ddict->dictContent = internalBuffer;
2063 		}
2064 		ddict->dictSize = dictSize;
2065 		ddict->entropy.hufTable[0] = (HUF_DTable)((HufLog)*0x1000001); /* cover both little and big endian */
2066 		/* parse dictionary content */
2067 		{
2068 			size_t const errorCode = ZSTD_loadEntropy_inDDict(ddict);
2069 			if (ZSTD_isError(errorCode)) {
2070 				ZSTD_freeDDict(ddict);
2071 				return NULL;
2072 			}
2073 		}
2074 
2075 		return ddict;
2076 	}
2077 }
2078 
2079 /*! ZSTD_initDDict() :
2080 *   Create a digested dictionary, to start decompression without startup delay.
2081 *   `dict` content is copied inside DDict.
2082 *   Consequently, `dict` can be released after `ZSTD_DDict` creation */
ZSTD_initDDict(const void * dict,size_t dictSize,void * workspace,size_t workspaceSize)2083 ZSTD_DDict *ZSTD_initDDict(const void *dict, size_t dictSize, void *workspace, size_t workspaceSize)
2084 {
2085 	ZSTD_customMem const stackMem = ZSTD_initStack(workspace, workspaceSize);
2086 	return ZSTD_createDDict_advanced(dict, dictSize, 1, stackMem);
2087 }
2088 
ZSTD_freeDDict(ZSTD_DDict * ddict)2089 size_t ZSTD_freeDDict(ZSTD_DDict *ddict)
2090 {
2091 	if (ddict == NULL)
2092 		return 0; /* support free on NULL */
2093 	{
2094 		ZSTD_customMem const cMem = ddict->cMem;
2095 		ZSTD_free(ddict->dictBuffer, cMem);
2096 		ZSTD_free(ddict, cMem);
2097 		return 0;
2098 	}
2099 }
2100 
2101 /*! ZSTD_getDictID_fromDict() :
2102  *  Provides the dictID stored within dictionary.
2103  *  if @return == 0, the dictionary is not conformant with Zstandard specification.
2104  *  It can still be loaded, but as a content-only dictionary. */
ZSTD_getDictID_fromDict(const void * dict,size_t dictSize)2105 unsigned ZSTD_getDictID_fromDict(const void *dict, size_t dictSize)
2106 {
2107 	if (dictSize < 8)
2108 		return 0;
2109 	if (ZSTD_readLE32(dict) != ZSTD_DICT_MAGIC)
2110 		return 0;
2111 	return ZSTD_readLE32((const char *)dict + 4);
2112 }
2113 
2114 /*! ZSTD_getDictID_fromDDict() :
2115  *  Provides the dictID of the dictionary loaded into `ddict`.
2116  *  If @return == 0, the dictionary is not conformant to Zstandard specification, or empty.
2117  *  Non-conformant dictionaries can still be loaded, but as content-only dictionaries. */
ZSTD_getDictID_fromDDict(const ZSTD_DDict * ddict)2118 unsigned ZSTD_getDictID_fromDDict(const ZSTD_DDict *ddict)
2119 {
2120 	if (ddict == NULL)
2121 		return 0;
2122 	return ZSTD_getDictID_fromDict(ddict->dictContent, ddict->dictSize);
2123 }
2124 
2125 /*! ZSTD_getDictID_fromFrame() :
2126  *  Provides the dictID required to decompressed the frame stored within `src`.
2127  *  If @return == 0, the dictID could not be decoded.
2128  *  This could for one of the following reasons :
2129  *  - The frame does not require a dictionary to be decoded (most common case).
2130  *  - The frame was built with dictID intentionally removed. Whatever dictionary is necessary is a hidden information.
2131  *    Note : this use case also happens when using a non-conformant dictionary.
2132  *  - `srcSize` is too small, and as a result, the frame header could not be decoded (only possible if `srcSize < ZSTD_FRAMEHEADERSIZE_MAX`).
2133  *  - This is not a Zstandard frame.
2134  *  When identifying the exact failure cause, it's possible to used ZSTD_getFrameParams(), which will provide a more precise error code. */
ZSTD_getDictID_fromFrame(const void * src,size_t srcSize)2135 unsigned ZSTD_getDictID_fromFrame(const void *src, size_t srcSize)
2136 {
2137 	ZSTD_frameParams zfp = {0, 0, 0, 0};
2138 	size_t const hError = ZSTD_getFrameParams(&zfp, src, srcSize);
2139 	if (ZSTD_isError(hError))
2140 		return 0;
2141 	return zfp.dictID;
2142 }
2143 
2144 /*! ZSTD_decompress_usingDDict() :
2145 *   Decompression using a pre-digested Dictionary
2146 *   Use dictionary without significant overhead. */
ZSTD_decompress_usingDDict(ZSTD_DCtx * dctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize,const ZSTD_DDict * ddict)2147 size_t ZSTD_decompress_usingDDict(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const ZSTD_DDict *ddict)
2148 {
2149 	/* pass content and size in case legacy frames are encountered */
2150 	return ZSTD_decompressMultiFrame(dctx, dst, dstCapacity, src, srcSize, NULL, 0, ddict);
2151 }
2152 
2153 /*=====================================
2154 *   Streaming decompression
2155 *====================================*/
2156 
2157 typedef enum { zdss_init, zdss_loadHeader, zdss_read, zdss_load, zdss_flush } ZSTD_dStreamStage;
2158 
2159 /* *** Resource management *** */
2160 struct ZSTD_DStream_s {
2161 	ZSTD_DCtx *dctx;
2162 	ZSTD_DDict *ddictLocal;
2163 	const ZSTD_DDict *ddict;
2164 	ZSTD_frameParams fParams;
2165 	ZSTD_dStreamStage stage;
2166 	char *inBuff;
2167 	size_t inBuffSize;
2168 	size_t inPos;
2169 	size_t maxWindowSize;
2170 	char *outBuff;
2171 	size_t outBuffSize;
2172 	size_t outStart;
2173 	size_t outEnd;
2174 	size_t blockSize;
2175 	BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX]; /* tmp buffer to store frame header */
2176 	size_t lhSize;
2177 	ZSTD_customMem customMem;
2178 	void *legacyContext;
2179 	U32 previousLegacyVersion;
2180 	U32 legacyVersion;
2181 	U32 hostageByte;
2182 }; /* typedef'd to ZSTD_DStream within "zstd.h" */
2183 
ZSTD_DStreamWorkspaceBound(size_t maxWindowSize)2184 size_t ZSTD_DStreamWorkspaceBound(size_t maxWindowSize)
2185 {
2186 	size_t const blockSize = MIN(maxWindowSize, ZSTD_BLOCKSIZE_ABSOLUTEMAX);
2187 	size_t const inBuffSize = blockSize;
2188 	size_t const outBuffSize = maxWindowSize + blockSize + WILDCOPY_OVERLENGTH * 2;
2189 	return ZSTD_DCtxWorkspaceBound() + ZSTD_ALIGN(sizeof(ZSTD_DStream)) + ZSTD_ALIGN(inBuffSize) + ZSTD_ALIGN(outBuffSize);
2190 }
2191 
ZSTD_createDStream_advanced(ZSTD_customMem customMem)2192 static ZSTD_DStream *ZSTD_createDStream_advanced(ZSTD_customMem customMem)
2193 {
2194 	ZSTD_DStream *zds;
2195 
2196 	if (!customMem.customAlloc || !customMem.customFree)
2197 		return NULL;
2198 
2199 	zds = (ZSTD_DStream *)ZSTD_malloc(sizeof(ZSTD_DStream), customMem);
2200 	if (zds == NULL)
2201 		return NULL;
2202 	memset(zds, 0, sizeof(ZSTD_DStream));
2203 	memcpy(&zds->customMem, &customMem, sizeof(ZSTD_customMem));
2204 	zds->dctx = ZSTD_createDCtx_advanced(customMem);
2205 	if (zds->dctx == NULL) {
2206 		ZSTD_freeDStream(zds);
2207 		return NULL;
2208 	}
2209 	zds->stage = zdss_init;
2210 	zds->maxWindowSize = ZSTD_MAXWINDOWSIZE_DEFAULT;
2211 	return zds;
2212 }
2213 
ZSTD_initDStream(size_t maxWindowSize,void * workspace,size_t workspaceSize)2214 ZSTD_DStream *ZSTD_initDStream(size_t maxWindowSize, void *workspace, size_t workspaceSize)
2215 {
2216 	ZSTD_customMem const stackMem = ZSTD_initStack(workspace, workspaceSize);
2217 	ZSTD_DStream *zds = ZSTD_createDStream_advanced(stackMem);
2218 	if (!zds) {
2219 		return NULL;
2220 	}
2221 
2222 	zds->maxWindowSize = maxWindowSize;
2223 	zds->stage = zdss_loadHeader;
2224 	zds->lhSize = zds->inPos = zds->outStart = zds->outEnd = 0;
2225 	ZSTD_freeDDict(zds->ddictLocal);
2226 	zds->ddictLocal = NULL;
2227 	zds->ddict = zds->ddictLocal;
2228 	zds->legacyVersion = 0;
2229 	zds->hostageByte = 0;
2230 
2231 	{
2232 		size_t const blockSize = MIN(zds->maxWindowSize, ZSTD_BLOCKSIZE_ABSOLUTEMAX);
2233 		size_t const neededOutSize = zds->maxWindowSize + blockSize + WILDCOPY_OVERLENGTH * 2;
2234 
2235 		zds->inBuff = (char *)ZSTD_malloc(blockSize, zds->customMem);
2236 		zds->inBuffSize = blockSize;
2237 		zds->outBuff = (char *)ZSTD_malloc(neededOutSize, zds->customMem);
2238 		zds->outBuffSize = neededOutSize;
2239 		if (zds->inBuff == NULL || zds->outBuff == NULL) {
2240 			ZSTD_freeDStream(zds);
2241 			return NULL;
2242 		}
2243 	}
2244 	return zds;
2245 }
2246 
ZSTD_initDStream_usingDDict(size_t maxWindowSize,const ZSTD_DDict * ddict,void * workspace,size_t workspaceSize)2247 ZSTD_DStream *ZSTD_initDStream_usingDDict(size_t maxWindowSize, const ZSTD_DDict *ddict, void *workspace, size_t workspaceSize)
2248 {
2249 	ZSTD_DStream *zds = ZSTD_initDStream(maxWindowSize, workspace, workspaceSize);
2250 	if (zds) {
2251 		zds->ddict = ddict;
2252 	}
2253 	return zds;
2254 }
2255 
ZSTD_freeDStream(ZSTD_DStream * zds)2256 size_t ZSTD_freeDStream(ZSTD_DStream *zds)
2257 {
2258 	if (zds == NULL)
2259 		return 0; /* support free on null */
2260 	{
2261 		ZSTD_customMem const cMem = zds->customMem;
2262 		ZSTD_freeDCtx(zds->dctx);
2263 		zds->dctx = NULL;
2264 		ZSTD_freeDDict(zds->ddictLocal);
2265 		zds->ddictLocal = NULL;
2266 		ZSTD_free(zds->inBuff, cMem);
2267 		zds->inBuff = NULL;
2268 		ZSTD_free(zds->outBuff, cMem);
2269 		zds->outBuff = NULL;
2270 		ZSTD_free(zds, cMem);
2271 		return 0;
2272 	}
2273 }
2274 
2275 /* *** Initialization *** */
2276 
ZSTD_DStreamInSize(void)2277 size_t ZSTD_DStreamInSize(void) { return ZSTD_BLOCKSIZE_ABSOLUTEMAX + ZSTD_blockHeaderSize; }
ZSTD_DStreamOutSize(void)2278 size_t ZSTD_DStreamOutSize(void) { return ZSTD_BLOCKSIZE_ABSOLUTEMAX; }
2279 
ZSTD_resetDStream(ZSTD_DStream * zds)2280 size_t ZSTD_resetDStream(ZSTD_DStream *zds)
2281 {
2282 	zds->stage = zdss_loadHeader;
2283 	zds->lhSize = zds->inPos = zds->outStart = zds->outEnd = 0;
2284 	zds->legacyVersion = 0;
2285 	zds->hostageByte = 0;
2286 	return ZSTD_frameHeaderSize_prefix;
2287 }
2288 
2289 /* *****   Decompression   ***** */
2290 
ZSTD_limitCopy(void * dst,size_t dstCapacity,const void * src,size_t srcSize)2291 ZSTD_STATIC size_t ZSTD_limitCopy(void *dst, size_t dstCapacity, const void *src, size_t srcSize)
2292 {
2293 	size_t const length = MIN(dstCapacity, srcSize);
2294 	memcpy(dst, src, length);
2295 	return length;
2296 }
2297 
ZSTD_decompressStream(ZSTD_DStream * zds,ZSTD_outBuffer * output,ZSTD_inBuffer * input)2298 size_t ZSTD_decompressStream(ZSTD_DStream *zds, ZSTD_outBuffer *output, ZSTD_inBuffer *input)
2299 {
2300 	const char *const istart = (const char *)(input->src) + input->pos;
2301 	const char *const iend = (const char *)(input->src) + input->size;
2302 	const char *ip = istart;
2303 	char *const ostart = (char *)(output->dst) + output->pos;
2304 	char *const oend = (char *)(output->dst) + output->size;
2305 	char *op = ostart;
2306 	U32 someMoreWork = 1;
2307 
2308 	while (someMoreWork) {
2309 		switch (zds->stage) {
2310 		case zdss_init:
2311 			ZSTD_resetDStream(zds); /* transparent reset on starting decoding a new frame */
2312 			fallthrough;
2313 
2314 		case zdss_loadHeader: {
2315 			size_t const hSize = ZSTD_getFrameParams(&zds->fParams, zds->headerBuffer, zds->lhSize);
2316 			if (ZSTD_isError(hSize))
2317 				return hSize;
2318 			if (hSize != 0) {				   /* need more input */
2319 				size_t const toLoad = hSize - zds->lhSize; /* if hSize!=0, hSize > zds->lhSize */
2320 				if (toLoad > (size_t)(iend - ip)) {	/* not enough input to load full header */
2321 					memcpy(zds->headerBuffer + zds->lhSize, ip, iend - ip);
2322 					zds->lhSize += iend - ip;
2323 					input->pos = input->size;
2324 					return (MAX(ZSTD_frameHeaderSize_min, hSize) - zds->lhSize) +
2325 					       ZSTD_blockHeaderSize; /* remaining header bytes + next block header */
2326 				}
2327 				memcpy(zds->headerBuffer + zds->lhSize, ip, toLoad);
2328 				zds->lhSize = hSize;
2329 				ip += toLoad;
2330 				break;
2331 			}
2332 
2333 			/* check for single-pass mode opportunity */
2334 			if (zds->fParams.frameContentSize && zds->fParams.windowSize /* skippable frame if == 0 */
2335 			    && (U64)(size_t)(oend - op) >= zds->fParams.frameContentSize) {
2336 				size_t const cSize = ZSTD_findFrameCompressedSize(istart, iend - istart);
2337 				if (cSize <= (size_t)(iend - istart)) {
2338 					size_t const decompressedSize = ZSTD_decompress_usingDDict(zds->dctx, op, oend - op, istart, cSize, zds->ddict);
2339 					if (ZSTD_isError(decompressedSize))
2340 						return decompressedSize;
2341 					ip = istart + cSize;
2342 					op += decompressedSize;
2343 					zds->dctx->expected = 0;
2344 					zds->stage = zdss_init;
2345 					someMoreWork = 0;
2346 					break;
2347 				}
2348 			}
2349 
2350 			/* Consume header */
2351 			ZSTD_refDDict(zds->dctx, zds->ddict);
2352 			{
2353 				size_t const h1Size = ZSTD_nextSrcSizeToDecompress(zds->dctx); /* == ZSTD_frameHeaderSize_prefix */
2354 				CHECK_F(ZSTD_decompressContinue(zds->dctx, NULL, 0, zds->headerBuffer, h1Size));
2355 				{
2356 					size_t const h2Size = ZSTD_nextSrcSizeToDecompress(zds->dctx);
2357 					CHECK_F(ZSTD_decompressContinue(zds->dctx, NULL, 0, zds->headerBuffer + h1Size, h2Size));
2358 				}
2359 			}
2360 
2361 			zds->fParams.windowSize = MAX(zds->fParams.windowSize, 1U << ZSTD_WINDOWLOG_ABSOLUTEMIN);
2362 			if (zds->fParams.windowSize > zds->maxWindowSize)
2363 				return ERROR(frameParameter_windowTooLarge);
2364 
2365 			/* Buffers are preallocated, but double check */
2366 			{
2367 				size_t const blockSize = MIN(zds->maxWindowSize, ZSTD_BLOCKSIZE_ABSOLUTEMAX);
2368 				size_t const neededOutSize = zds->maxWindowSize + blockSize + WILDCOPY_OVERLENGTH * 2;
2369 				if (zds->inBuffSize < blockSize) {
2370 					return ERROR(GENERIC);
2371 				}
2372 				if (zds->outBuffSize < neededOutSize) {
2373 					return ERROR(GENERIC);
2374 				}
2375 				zds->blockSize = blockSize;
2376 			}
2377 			zds->stage = zdss_read;
2378 		}
2379 			fallthrough;
2380 
2381 		case zdss_read: {
2382 			size_t const neededInSize = ZSTD_nextSrcSizeToDecompress(zds->dctx);
2383 			if (neededInSize == 0) { /* end of frame */
2384 				zds->stage = zdss_init;
2385 				someMoreWork = 0;
2386 				break;
2387 			}
2388 			if ((size_t)(iend - ip) >= neededInSize) { /* decode directly from src */
2389 				const int isSkipFrame = ZSTD_isSkipFrame(zds->dctx);
2390 				size_t const decodedSize = ZSTD_decompressContinue(zds->dctx, zds->outBuff + zds->outStart,
2391 										   (isSkipFrame ? 0 : zds->outBuffSize - zds->outStart), ip, neededInSize);
2392 				if (ZSTD_isError(decodedSize))
2393 					return decodedSize;
2394 				ip += neededInSize;
2395 				if (!decodedSize && !isSkipFrame)
2396 					break; /* this was just a header */
2397 				zds->outEnd = zds->outStart + decodedSize;
2398 				zds->stage = zdss_flush;
2399 				break;
2400 			}
2401 			if (ip == iend) {
2402 				someMoreWork = 0;
2403 				break;
2404 			} /* no more input */
2405 			zds->stage = zdss_load;
2406 			/* pass-through */
2407 		}
2408 			fallthrough;
2409 
2410 		case zdss_load: {
2411 			size_t const neededInSize = ZSTD_nextSrcSizeToDecompress(zds->dctx);
2412 			size_t const toLoad = neededInSize - zds->inPos; /* should always be <= remaining space within inBuff */
2413 			size_t loadedSize;
2414 			if (toLoad > zds->inBuffSize - zds->inPos)
2415 				return ERROR(corruption_detected); /* should never happen */
2416 			loadedSize = ZSTD_limitCopy(zds->inBuff + zds->inPos, toLoad, ip, iend - ip);
2417 			ip += loadedSize;
2418 			zds->inPos += loadedSize;
2419 			if (loadedSize < toLoad) {
2420 				someMoreWork = 0;
2421 				break;
2422 			} /* not enough input, wait for more */
2423 
2424 			/* decode loaded input */
2425 			{
2426 				const int isSkipFrame = ZSTD_isSkipFrame(zds->dctx);
2427 				size_t const decodedSize = ZSTD_decompressContinue(zds->dctx, zds->outBuff + zds->outStart, zds->outBuffSize - zds->outStart,
2428 										   zds->inBuff, neededInSize);
2429 				if (ZSTD_isError(decodedSize))
2430 					return decodedSize;
2431 				zds->inPos = 0; /* input is consumed */
2432 				if (!decodedSize && !isSkipFrame) {
2433 					zds->stage = zdss_read;
2434 					break;
2435 				} /* this was just a header */
2436 				zds->outEnd = zds->outStart + decodedSize;
2437 				zds->stage = zdss_flush;
2438 				/* pass-through */
2439 			}
2440 		}
2441 			fallthrough;
2442 
2443 		case zdss_flush: {
2444 			size_t const toFlushSize = zds->outEnd - zds->outStart;
2445 			size_t const flushedSize = ZSTD_limitCopy(op, oend - op, zds->outBuff + zds->outStart, toFlushSize);
2446 			op += flushedSize;
2447 			zds->outStart += flushedSize;
2448 			if (flushedSize == toFlushSize) { /* flush completed */
2449 				zds->stage = zdss_read;
2450 				if (zds->outStart + zds->blockSize > zds->outBuffSize)
2451 					zds->outStart = zds->outEnd = 0;
2452 				break;
2453 			}
2454 			/* cannot complete flush */
2455 			someMoreWork = 0;
2456 			break;
2457 		}
2458 		default:
2459 			return ERROR(GENERIC); /* impossible */
2460 		}
2461 	}
2462 
2463 	/* result */
2464 	input->pos += (size_t)(ip - istart);
2465 	output->pos += (size_t)(op - ostart);
2466 	{
2467 		size_t nextSrcSizeHint = ZSTD_nextSrcSizeToDecompress(zds->dctx);
2468 		if (!nextSrcSizeHint) {			    /* frame fully decoded */
2469 			if (zds->outEnd == zds->outStart) { /* output fully flushed */
2470 				if (zds->hostageByte) {
2471 					if (input->pos >= input->size) {
2472 						zds->stage = zdss_read;
2473 						return 1;
2474 					}	     /* can't release hostage (not present) */
2475 					input->pos++; /* release hostage */
2476 				}
2477 				return 0;
2478 			}
2479 			if (!zds->hostageByte) { /* output not fully flushed; keep last byte as hostage; will be released when all output is flushed */
2480 				input->pos--;    /* note : pos > 0, otherwise, impossible to finish reading last block */
2481 				zds->hostageByte = 1;
2482 			}
2483 			return 1;
2484 		}
2485 		nextSrcSizeHint += ZSTD_blockHeaderSize * (ZSTD_nextInputType(zds->dctx) == ZSTDnit_block); /* preload header of next block */
2486 		if (zds->inPos > nextSrcSizeHint)
2487 			return ERROR(GENERIC); /* should never happen */
2488 		nextSrcSizeHint -= zds->inPos; /* already loaded*/
2489 		return nextSrcSizeHint;
2490 	}
2491 }
2492 
2493 EXPORT_SYMBOL(ZSTD_DCtxWorkspaceBound);
2494 EXPORT_SYMBOL(ZSTD_initDCtx);
2495 EXPORT_SYMBOL(ZSTD_decompressDCtx);
2496 EXPORT_SYMBOL(ZSTD_decompress_usingDict);
2497 
2498 EXPORT_SYMBOL(ZSTD_DDictWorkspaceBound);
2499 EXPORT_SYMBOL(ZSTD_initDDict);
2500 EXPORT_SYMBOL(ZSTD_decompress_usingDDict);
2501 
2502 EXPORT_SYMBOL(ZSTD_DStreamWorkspaceBound);
2503 EXPORT_SYMBOL(ZSTD_initDStream);
2504 EXPORT_SYMBOL(ZSTD_initDStream_usingDDict);
2505 EXPORT_SYMBOL(ZSTD_resetDStream);
2506 EXPORT_SYMBOL(ZSTD_decompressStream);
2507 EXPORT_SYMBOL(ZSTD_DStreamInSize);
2508 EXPORT_SYMBOL(ZSTD_DStreamOutSize);
2509 
2510 EXPORT_SYMBOL(ZSTD_findFrameCompressedSize);
2511 EXPORT_SYMBOL(ZSTD_getFrameContentSize);
2512 EXPORT_SYMBOL(ZSTD_findDecompressedSize);
2513 
2514 EXPORT_SYMBOL(ZSTD_isFrame);
2515 EXPORT_SYMBOL(ZSTD_getDictID_fromDict);
2516 EXPORT_SYMBOL(ZSTD_getDictID_fromDDict);
2517 EXPORT_SYMBOL(ZSTD_getDictID_fromFrame);
2518 
2519 EXPORT_SYMBOL(ZSTD_getFrameParams);
2520 EXPORT_SYMBOL(ZSTD_decompressBegin);
2521 EXPORT_SYMBOL(ZSTD_decompressBegin_usingDict);
2522 EXPORT_SYMBOL(ZSTD_copyDCtx);
2523 EXPORT_SYMBOL(ZSTD_nextSrcSizeToDecompress);
2524 EXPORT_SYMBOL(ZSTD_decompressContinue);
2525 EXPORT_SYMBOL(ZSTD_nextInputType);
2526 
2527 EXPORT_SYMBOL(ZSTD_decompressBlock);
2528 EXPORT_SYMBOL(ZSTD_insertBlock);
2529 
2530 MODULE_LICENSE("Dual BSD/GPL");
2531 MODULE_DESCRIPTION("Zstd Decompressor");
2532