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