projects / linux-2.6-block.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Merge tag 'imx-fixes-5.2-2' of git://git.kernel.org/pub/scm/linux/kernel/git/shawnguo...
[linux-2.6-block.git] / lib / zstd / decompress.c
CommitLineData
73f3d1b4
NT		 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**********************************************************/
52static void ZSTD_copy4(void *dst, const void *src) { memcpy(dst, src, 4); }
53
54/*-*************************************************************
55* Context management
56***************************************************************/
57typedef 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
68typedef 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
77struct 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
104size_t ZSTD_DCtxWorkspaceBound(void) { return ZSTD_ALIGN(sizeof(ZSTD_stack)) + ZSTD_ALIGN(sizeof(ZSTD_DCtx)); }
105
106size_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
126ZSTD_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
141ZSTD_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
147size_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
155void 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
161static 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. */
172unsigned 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 */
189static 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() */
207size_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) */
297unsigned 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 */
319unsigned 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() */
372static 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
386typedef 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` */
394size_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
412static 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
420static 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 ) */
432size_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 /* fall-through */
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
571typedef union {
572 FSE_decode_t realData;
573 U32 alignedBy4;
574} FSE_decode_t4;
575
576static 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
644static 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
712static 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*/
752static 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
794size_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
861typedef struct {
862 size_t litLength;
863 size_t matchLength;
864 size_t offset;
865 const BYTE *match;
866} seq_t;
867
868typedef 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
879FORCE_NOINLINE
880size_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
931static 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
1006FORCE_INLINE
1007size_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
1093static 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
1163FORCE_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
1253static 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
1262FORCE_INLINE
1263size_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
1348static 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
1445static 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
1469static 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
1479size_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. */
1490size_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
1497size_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` */
1510size_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 */
1566static 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
1640static const void *ZSTD_DDictDictContent(const ZSTD_DDict *ddict);
1641static size_t ZSTD_DDictDictSize(const ZSTD_DDict *ddict);
1642
1643static 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
1707size_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
1712size_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****************************************/
1721size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx *dctx) { return dctx->expected; }
1722
1723ZSTD_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
1738int 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() */
1743size_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 */
224b44d4 1771 /* fall through */
73f3d1b4
NT		 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
1862static 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 */
1874static 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
1943static 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
1969size_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
1979struct 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
1989size_t ZSTD_DDictWorkspaceBound(void) { return ZSTD_ALIGN(sizeof(ZSTD_stack)) + ZSTD_ALIGN(sizeof(ZSTD_DDict)); }
1990
1991static const void *ZSTD_DDictDictContent(const ZSTD_DDict *ddict) { return ddict->dictContent; }
1992
1993static size_t ZSTD_DDictDictSize(const ZSTD_DDict *ddict) { return ddict->dictSize; }
1994
1995static 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
2021static 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
2040static 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 */
2083ZSTD_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
2089size_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. */
2105unsigned 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. */
2118unsigned 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. */
2135unsigned 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. */
2147size_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
2157typedef enum { zdss_init, zdss_loadHeader, zdss_read, zdss_load, zdss_flush } ZSTD_dStreamStage;
2158
2159/* *** Resource management *** */
2160struct 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
2184size_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
2192static 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
2214ZSTD_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
2247ZSTD_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
2256size_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
2277size_t ZSTD_DStreamInSize(void) { return ZSTD_BLOCKSIZE_ABSOLUTEMAX + ZSTD_blockHeaderSize; }
2278size_t ZSTD_DStreamOutSize(void) { return ZSTD_BLOCKSIZE_ABSOLUTEMAX; }
2279
2280size_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
2291ZSTD_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
2298size_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 /* fall-through */
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 }
224b44d4 2379 /* fall through */
73f3d1b4
NT		 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 }
224b44d4 2408 /* fall through */
73f3d1b4
NT		 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 }
224b44d4 2441 /* fall through */
73f3d1b4
NT		 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
2493EXPORT_SYMBOL(ZSTD_DCtxWorkspaceBound);
2494EXPORT_SYMBOL(ZSTD_initDCtx);
2495EXPORT_SYMBOL(ZSTD_decompressDCtx);
2496EXPORT_SYMBOL(ZSTD_decompress_usingDict);
2497
2498EXPORT_SYMBOL(ZSTD_DDictWorkspaceBound);
2499EXPORT_SYMBOL(ZSTD_initDDict);
2500EXPORT_SYMBOL(ZSTD_decompress_usingDDict);
2501
2502EXPORT_SYMBOL(ZSTD_DStreamWorkspaceBound);
2503EXPORT_SYMBOL(ZSTD_initDStream);
2504EXPORT_SYMBOL(ZSTD_initDStream_usingDDict);
2505EXPORT_SYMBOL(ZSTD_resetDStream);
2506EXPORT_SYMBOL(ZSTD_decompressStream);
2507EXPORT_SYMBOL(ZSTD_DStreamInSize);
2508EXPORT_SYMBOL(ZSTD_DStreamOutSize);
2509
2510EXPORT_SYMBOL(ZSTD_findFrameCompressedSize);
2511EXPORT_SYMBOL(ZSTD_getFrameContentSize);
2512EXPORT_SYMBOL(ZSTD_findDecompressedSize);
2513
2514EXPORT_SYMBOL(ZSTD_isFrame);
2515EXPORT_SYMBOL(ZSTD_getDictID_fromDict);
2516EXPORT_SYMBOL(ZSTD_getDictID_fromDDict);
2517EXPORT_SYMBOL(ZSTD_getDictID_fromFrame);
2518
2519EXPORT_SYMBOL(ZSTD_getFrameParams);
2520EXPORT_SYMBOL(ZSTD_decompressBegin);
2521EXPORT_SYMBOL(ZSTD_decompressBegin_usingDict);
2522EXPORT_SYMBOL(ZSTD_copyDCtx);
2523EXPORT_SYMBOL(ZSTD_nextSrcSizeToDecompress);
2524EXPORT_SYMBOL(ZSTD_decompressContinue);
2525EXPORT_SYMBOL(ZSTD_nextInputType);
2526
2527EXPORT_SYMBOL(ZSTD_decompressBlock);
2528EXPORT_SYMBOL(ZSTD_insertBlock);
2529
2530MODULE_LICENSE("Dual BSD/GPL");
2531MODULE_DESCRIPTION("Zstd Decompressor");
Linux 6.x block layer and io_uring tree(s)