]> Git Repo - linux.git/blame - lib/zstd/decompress.c
projects / linux.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Merge tag 'for-linus-4.17-rc5-tag' of git://git.kernel.org/pub/scm/linux/kernel/git...
[linux.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 */
1771
1772 case ZSTDds_decodeFrameHeader:
1773 memcpy(dctx->headerBuffer + ZSTD_frameHeaderSize_prefix, src, dctx->expected);
1774 CHECK_F(ZSTD_decodeFrameHeader(dctx, dctx->headerBuffer, dctx->headerSize));
1775 dctx->expected = ZSTD_blockHeaderSize;
1776 dctx->stage = ZSTDds_decodeBlockHeader;
1777 return 0;
1778
1779 case ZSTDds_decodeBlockHeader: {
1780 blockProperties_t bp;
1781 size_t const cBlockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
1782 if (ZSTD_isError(cBlockSize))
1783 return cBlockSize;
1784 dctx->expected = cBlockSize;
1785 dctx->bType = bp.blockType;
1786 dctx->rleSize = bp.origSize;
1787 if (cBlockSize) {
1788 dctx->stage = bp.lastBlock ? ZSTDds_decompressLastBlock : ZSTDds_decompressBlock;
1789 return 0;
1790 }
1791 /* empty block */
1792 if (bp.lastBlock) {
1793 if (dctx->fParams.checksumFlag) {
1794 dctx->expected = 4;
1795 dctx->stage = ZSTDds_checkChecksum;
1796 } else {
1797 dctx->expected = 0; /* end of frame */
1798 dctx->stage = ZSTDds_getFrameHeaderSize;
1799 }
1800 } else {
1801 dctx->expected = 3; /* go directly to next header */
1802 dctx->stage = ZSTDds_decodeBlockHeader;
1803 }
1804 return 0;
1805 }
1806 case ZSTDds_decompressLastBlock:
1807 case ZSTDds_decompressBlock: {
1808 size_t rSize;
1809 switch (dctx->bType) {
1810 case bt_compressed: rSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize); break;
1811 case bt_raw: rSize = ZSTD_copyRawBlock(dst, dstCapacity, src, srcSize); break;
1812 case bt_rle: rSize = ZSTD_setRleBlock(dst, dstCapacity, src, srcSize, dctx->rleSize); break;
1813 case bt_reserved: /* should never happen */
1814 default: return ERROR(corruption_detected);
1815 }
1816 if (ZSTD_isError(rSize))
1817 return rSize;
1818 if (dctx->fParams.checksumFlag)
1819 xxh64_update(&dctx->xxhState, dst, rSize);
1820
1821 if (dctx->stage == ZSTDds_decompressLastBlock) { /* end of frame */
1822 if (dctx->fParams.checksumFlag) { /* another round for frame checksum */
1823 dctx->expected = 4;
1824 dctx->stage = ZSTDds_checkChecksum;
1825 } else {
1826 dctx->expected = 0; /* ends here */
1827 dctx->stage = ZSTDds_getFrameHeaderSize;
1828 }
1829 } else {
1830 dctx->stage = ZSTDds_decodeBlockHeader;
1831 dctx->expected = ZSTD_blockHeaderSize;
1832 dctx->previousDstEnd = (char *)dst + rSize;
1833 }
1834 return rSize;
1835 }
1836 case ZSTDds_checkChecksum: {
1837 U32 const h32 = (U32)xxh64_digest(&dctx->xxhState);
1838 U32 const check32 = ZSTD_readLE32(src); /* srcSize == 4, guaranteed by dctx->expected */
1839 if (check32 != h32)
1840 return ERROR(checksum_wrong);
1841 dctx->expected = 0;
1842 dctx->stage = ZSTDds_getFrameHeaderSize;
1843 return 0;
1844 }
1845 case ZSTDds_decodeSkippableHeader: {
1846 memcpy(dctx->headerBuffer + ZSTD_frameHeaderSize_prefix, src, dctx->expected);
1847 dctx->expected = ZSTD_readLE32(dctx->headerBuffer + 4);
1848 dctx->stage = ZSTDds_skipFrame;
1849 return 0;
1850 }
1851 case ZSTDds_skipFrame: {
1852 dctx->expected = 0;
1853 dctx->stage = ZSTDds_getFrameHeaderSize;
1854 return 0;
1855 }
1856 default:
1857 return ERROR(GENERIC); /* impossible */
1858 }
1859}
1860
1861static size_t ZSTD_refDictContent(ZSTD_DCtx *dctx, const void *dict, size_t dictSize)
1862{
1863 dctx->dictEnd = dctx->previousDstEnd;
1864 dctx->vBase = (const char *)dict - ((const char *)(dctx->previousDstEnd) - (const char *)(dctx->base));
1865 dctx->base = dict;
1866 dctx->previousDstEnd = (const char *)dict + dictSize;
1867 return 0;
1868}
1869
1870/* ZSTD_loadEntropy() :
1871 * dict : must point at beginning of a valid zstd dictionary
1872 * @return : size of entropy tables read */
1873static size_t ZSTD_loadEntropy(ZSTD_entropyTables_t *entropy, const void *const dict, size_t const dictSize)
1874{
1875 const BYTE *dictPtr = (const BYTE *)dict;
1876 const BYTE *const dictEnd = dictPtr + dictSize;
1877
1878 if (dictSize <= 8)
1879 return ERROR(dictionary_corrupted);
1880 dictPtr += 8; /* skip header = magic + dictID */
1881
1882 {
1883 size_t const hSize = HUF_readDTableX4_wksp(entropy->hufTable, dictPtr, dictEnd - dictPtr, entropy->workspace, sizeof(entropy->workspace));
1884 if (HUF_isError(hSize))
1885 return ERROR(dictionary_corrupted);
1886 dictPtr += hSize;
1887 }
1888
1889 {
1890 short offcodeNCount[MaxOff + 1];
1891 U32 offcodeMaxValue = MaxOff, offcodeLog;
1892 size_t const offcodeHeaderSize = FSE_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dictPtr, dictEnd - dictPtr);
1893 if (FSE_isError(offcodeHeaderSize))
1894 return ERROR(dictionary_corrupted);
1895 if (offcodeLog > OffFSELog)
1896 return ERROR(dictionary_corrupted);
1897 CHECK_E(FSE_buildDTable_wksp(entropy->OFTable, offcodeNCount, offcodeMaxValue, offcodeLog, entropy->workspace, sizeof(entropy->workspace)), dictionary_corrupted);
1898 dictPtr += offcodeHeaderSize;
1899 }
1900
1901 {
1902 short matchlengthNCount[MaxML + 1];
1903 unsigned matchlengthMaxValue = MaxML, matchlengthLog;
1904 size_t const matchlengthHeaderSize = FSE_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd - dictPtr);
1905 if (FSE_isError(matchlengthHeaderSize))
1906 return ERROR(dictionary_corrupted);
1907 if (matchlengthLog > MLFSELog)
1908 return ERROR(dictionary_corrupted);
1909 CHECK_E(FSE_buildDTable_wksp(entropy->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog, entropy->workspace, sizeof(entropy->workspace)), dictionary_corrupted);
1910 dictPtr += matchlengthHeaderSize;
1911 }
1912
1913 {
1914 short litlengthNCount[MaxLL + 1];
1915 unsigned litlengthMaxValue = MaxLL, litlengthLog;
1916 size_t const litlengthHeaderSize = FSE_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd - dictPtr);
1917 if (FSE_isError(litlengthHeaderSize))
1918 return ERROR(dictionary_corrupted);
1919 if (litlengthLog > LLFSELog)
1920 return ERROR(dictionary_corrupted);
1921 CHECK_E(FSE_buildDTable_wksp(entropy->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog, entropy->workspace, sizeof(entropy->workspace)), dictionary_corrupted);
1922 dictPtr += litlengthHeaderSize;
1923 }
1924
1925 if (dictPtr + 12 > dictEnd)
1926 return ERROR(dictionary_corrupted);
1927 {
1928 int i;
1929 size_t const dictContentSize = (size_t)(dictEnd - (dictPtr + 12));
1930 for (i = 0; i < 3; i++) {
1931 U32 const rep = ZSTD_readLE32(dictPtr);
1932 dictPtr += 4;
1933 if (rep == 0 || rep >= dictContentSize)
1934 return ERROR(dictionary_corrupted);
1935 entropy->rep[i] = rep;
1936 }
1937 }
1938
1939 return dictPtr - (const BYTE *)dict;
1940}
1941
1942static size_t ZSTD_decompress_insertDictionary(ZSTD_DCtx *dctx, const void *dict, size_t dictSize)
1943{
1944 if (dictSize < 8)
1945 return ZSTD_refDictContent(dctx, dict, dictSize);
1946 {
1947 U32 const magic = ZSTD_readLE32(dict);
1948 if (magic != ZSTD_DICT_MAGIC) {
1949 return ZSTD_refDictContent(dctx, dict, dictSize); /* pure content mode */
1950 }
1951 }
1952 dctx->dictID = ZSTD_readLE32((const char *)dict + 4);
1953
1954 /* load entropy tables */
1955 {
1956 size_t const eSize = ZSTD_loadEntropy(&dctx->entropy, dict, dictSize);
1957 if (ZSTD_isError(eSize))
1958 return ERROR(dictionary_corrupted);
1959 dict = (const char *)dict + eSize;
1960 dictSize -= eSize;
1961 }
1962 dctx->litEntropy = dctx->fseEntropy = 1;
1963
1964 /* reference dictionary content */
1965 return ZSTD_refDictContent(dctx, dict, dictSize);
1966}
1967
1968size_t ZSTD_decompressBegin_usingDict(ZSTD_DCtx *dctx, const void *dict, size_t dictSize)
1969{
1970 CHECK_F(ZSTD_decompressBegin(dctx));
1971 if (dict && dictSize)
1972 CHECK_E(ZSTD_decompress_insertDictionary(dctx, dict, dictSize), dictionary_corrupted);
1973 return 0;
1974}
1975
1976/* ====== ZSTD_DDict ====== */
1977
1978struct ZSTD_DDict_s {
1979 void *dictBuffer;
1980 const void *dictContent;
1981 size_t dictSize;
1982 ZSTD_entropyTables_t entropy;
1983 U32 dictID;
1984 U32 entropyPresent;
1985 ZSTD_customMem cMem;
1986}; /* typedef'd to ZSTD_DDict within "zstd.h" */
1987
1988size_t ZSTD_DDictWorkspaceBound(void) { return ZSTD_ALIGN(sizeof(ZSTD_stack)) + ZSTD_ALIGN(sizeof(ZSTD_DDict)); }
1989
1990static const void *ZSTD_DDictDictContent(const ZSTD_DDict *ddict) { return ddict->dictContent; }
1991
1992static size_t ZSTD_DDictDictSize(const ZSTD_DDict *ddict) { return ddict->dictSize; }
1993
1994static void ZSTD_refDDict(ZSTD_DCtx *dstDCtx, const ZSTD_DDict *ddict)
1995{
1996 ZSTD_decompressBegin(dstDCtx); /* init */
1997 if (ddict) { /* support refDDict on NULL */
1998 dstDCtx->dictID = ddict->dictID;
1999 dstDCtx->base = ddict->dictContent;
2000 dstDCtx->vBase = ddict->dictContent;
2001 dstDCtx->dictEnd = (const BYTE *)ddict->dictContent + ddict->dictSize;
2002 dstDCtx->previousDstEnd = dstDCtx->dictEnd;
2003 if (ddict->entropyPresent) {
2004 dstDCtx->litEntropy = 1;
2005 dstDCtx->fseEntropy = 1;
2006 dstDCtx->LLTptr = ddict->entropy.LLTable;
2007 dstDCtx->MLTptr = ddict->entropy.MLTable;
2008 dstDCtx->OFTptr = ddict->entropy.OFTable;
2009 dstDCtx->HUFptr = ddict->entropy.hufTable;
2010 dstDCtx->entropy.rep[0] = ddict->entropy.rep[0];
2011 dstDCtx->entropy.rep[1] = ddict->entropy.rep[1];
2012 dstDCtx->entropy.rep[2] = ddict->entropy.rep[2];
2013 } else {
2014 dstDCtx->litEntropy = 0;
2015 dstDCtx->fseEntropy = 0;
2016 }
2017 }
2018}
2019
2020static size_t ZSTD_loadEntropy_inDDict(ZSTD_DDict *ddict)
2021{
2022 ddict->dictID = 0;
2023 ddict->entropyPresent = 0;
2024 if (ddict->dictSize < 8)
2025 return 0;
2026 {
2027 U32 const magic = ZSTD_readLE32(ddict->dictContent);
2028 if (magic != ZSTD_DICT_MAGIC)
2029 return 0; /* pure content mode */
2030 }
2031 ddict->dictID = ZSTD_readLE32((const char *)ddict->dictContent + 4);
2032
2033 /* load entropy tables */
2034 CHECK_E(ZSTD_loadEntropy(&ddict->entropy, ddict->dictContent, ddict->dictSize), dictionary_corrupted);
2035 ddict->entropyPresent = 1;
2036 return 0;
2037}
2038
2039static ZSTD_DDict *ZSTD_createDDict_advanced(const void *dict, size_t dictSize, unsigned byReference, ZSTD_customMem customMem)
2040{
2041 if (!customMem.customAlloc || !customMem.customFree)
2042 return NULL;
2043
2044 {
2045 ZSTD_DDict *const ddict = (ZSTD_DDict *)ZSTD_malloc(sizeof(ZSTD_DDict), customMem);
2046 if (!ddict)
2047 return NULL;
2048 ddict->cMem = customMem;
2049
2050 if ((byReference) || (!dict) || (!dictSize)) {
2051 ddict->dictBuffer = NULL;
2052 ddict->dictContent = dict;
2053 } else {
2054 void *const internalBuffer = ZSTD_malloc(dictSize, customMem);
2055 if (!internalBuffer) {
2056 ZSTD_freeDDict(ddict);
2057 return NULL;
2058 }
2059 memcpy(internalBuffer, dict, dictSize);
2060 ddict->dictBuffer = internalBuffer;
2061 ddict->dictContent = internalBuffer;
2062 }
2063 ddict->dictSize = dictSize;
2064 ddict->entropy.hufTable[0] = (HUF_DTable)((HufLog)*0x1000001); /* cover both little and big endian */
2065 /* parse dictionary content */
2066 {
2067 size_t const errorCode = ZSTD_loadEntropy_inDDict(ddict);
2068 if (ZSTD_isError(errorCode)) {
2069 ZSTD_freeDDict(ddict);
2070 return NULL;
2071 }
2072 }
2073
2074 return ddict;
2075 }
2076}
2077
2078/*! ZSTD_initDDict() :
2079* Create a digested dictionary, to start decompression without startup delay.
2080* `dict` content is copied inside DDict.
2081* Consequently, `dict` can be released after `ZSTD_DDict` creation */
2082ZSTD_DDict *ZSTD_initDDict(const void *dict, size_t dictSize, void *workspace, size_t workspaceSize)
2083{
2084 ZSTD_customMem const stackMem = ZSTD_initStack(workspace, workspaceSize);
2085 return ZSTD_createDDict_advanced(dict, dictSize, 1, stackMem);
2086}
2087
2088size_t ZSTD_freeDDict(ZSTD_DDict *ddict)
2089{
2090 if (ddict == NULL)
2091 return 0; /* support free on NULL */
2092 {
2093 ZSTD_customMem const cMem = ddict->cMem;
2094 ZSTD_free(ddict->dictBuffer, cMem);
2095 ZSTD_free(ddict, cMem);
2096 return 0;
2097 }
2098}
2099
2100/*! ZSTD_getDictID_fromDict() :
2101 * Provides the dictID stored within dictionary.
2102 * if @return == 0, the dictionary is not conformant with Zstandard specification.
2103 * It can still be loaded, but as a content-only dictionary. */
2104unsigned ZSTD_getDictID_fromDict(const void *dict, size_t dictSize)
2105{
2106 if (dictSize < 8)
2107 return 0;
2108 if (ZSTD_readLE32(dict) != ZSTD_DICT_MAGIC)
2109 return 0;
2110 return ZSTD_readLE32((const char *)dict + 4);
2111}
2112
2113/*! ZSTD_getDictID_fromDDict() :
2114 * Provides the dictID of the dictionary loaded into `ddict`.
2115 * If @return == 0, the dictionary is not conformant to Zstandard specification, or empty.
2116 * Non-conformant dictionaries can still be loaded, but as content-only dictionaries. */
2117unsigned ZSTD_getDictID_fromDDict(const ZSTD_DDict *ddict)
2118{
2119 if (ddict == NULL)
2120 return 0;
2121 return ZSTD_getDictID_fromDict(ddict->dictContent, ddict->dictSize);
2122}
2123
2124/*! ZSTD_getDictID_fromFrame() :
2125 * Provides the dictID required to decompressed the frame stored within `src`.
2126 * If @return == 0, the dictID could not be decoded.
2127 * This could for one of the following reasons :
2128 * - The frame does not require a dictionary to be decoded (most common case).
2129 * - The frame was built with dictID intentionally removed. Whatever dictionary is necessary is a hidden information.
2130 * Note : this use case also happens when using a non-conformant dictionary.
2131 * - `srcSize` is too small, and as a result, the frame header could not be decoded (only possible if `srcSize < ZSTD_FRAMEHEADERSIZE_MAX`).
2132 * - This is not a Zstandard frame.
2133 * When identifying the exact failure cause, it's possible to used ZSTD_getFrameParams(), which will provide a more precise error code. */
2134unsigned ZSTD_getDictID_fromFrame(const void *src, size_t srcSize)
2135{
2136 ZSTD_frameParams zfp = {0, 0, 0, 0};
2137 size_t const hError = ZSTD_getFrameParams(&zfp, src, srcSize);
2138 if (ZSTD_isError(hError))
2139 return 0;
2140 return zfp.dictID;
2141}
2142
2143/*! ZSTD_decompress_usingDDict() :
2144* Decompression using a pre-digested Dictionary
2145* Use dictionary without significant overhead. */
2146size_t ZSTD_decompress_usingDDict(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const ZSTD_DDict *ddict)
2147{
2148 /* pass content and size in case legacy frames are encountered */
2149 return ZSTD_decompressMultiFrame(dctx, dst, dstCapacity, src, srcSize, NULL, 0, ddict);
2150}
2151
2152/*=====================================
2153* Streaming decompression
2154*====================================*/
2155
2156typedef enum { zdss_init, zdss_loadHeader, zdss_read, zdss_load, zdss_flush } ZSTD_dStreamStage;
2157
2158/* *** Resource management *** */
2159struct ZSTD_DStream_s {
2160 ZSTD_DCtx *dctx;
2161 ZSTD_DDict *ddictLocal;
2162 const ZSTD_DDict *ddict;
2163 ZSTD_frameParams fParams;
2164 ZSTD_dStreamStage stage;
2165 char *inBuff;
2166 size_t inBuffSize;
2167 size_t inPos;
2168 size_t maxWindowSize;
2169 char *outBuff;
2170 size_t outBuffSize;
2171 size_t outStart;
2172 size_t outEnd;
2173 size_t blockSize;
2174 BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX]; /* tmp buffer to store frame header */
2175 size_t lhSize;
2176 ZSTD_customMem customMem;
2177 void *legacyContext;
2178 U32 previousLegacyVersion;
2179 U32 legacyVersion;
2180 U32 hostageByte;
2181}; /* typedef'd to ZSTD_DStream within "zstd.h" */
2182
2183size_t ZSTD_DStreamWorkspaceBound(size_t maxWindowSize)
2184{
2185 size_t const blockSize = MIN(maxWindowSize, ZSTD_BLOCKSIZE_ABSOLUTEMAX);
2186 size_t const inBuffSize = blockSize;
2187 size_t const outBuffSize = maxWindowSize + blockSize + WILDCOPY_OVERLENGTH * 2;
2188 return ZSTD_DCtxWorkspaceBound() + ZSTD_ALIGN(sizeof(ZSTD_DStream)) + ZSTD_ALIGN(inBuffSize) + ZSTD_ALIGN(outBuffSize);
2189}
2190
2191static ZSTD_DStream *ZSTD_createDStream_advanced(ZSTD_customMem customMem)
2192{
2193 ZSTD_DStream *zds;
2194
2195 if (!customMem.customAlloc || !customMem.customFree)
2196 return NULL;
2197
2198 zds = (ZSTD_DStream *)ZSTD_malloc(sizeof(ZSTD_DStream), customMem);
2199 if (zds == NULL)
2200 return NULL;
2201 memset(zds, 0, sizeof(ZSTD_DStream));
2202 memcpy(&zds->customMem, &customMem, sizeof(ZSTD_customMem));
2203 zds->dctx = ZSTD_createDCtx_advanced(customMem);
2204 if (zds->dctx == NULL) {
2205 ZSTD_freeDStream(zds);
2206 return NULL;
2207 }
2208 zds->stage = zdss_init;
2209 zds->maxWindowSize = ZSTD_MAXWINDOWSIZE_DEFAULT;
2210 return zds;
2211}
2212
2213ZSTD_DStream *ZSTD_initDStream(size_t maxWindowSize, void *workspace, size_t workspaceSize)
2214{
2215 ZSTD_customMem const stackMem = ZSTD_initStack(workspace, workspaceSize);
2216 ZSTD_DStream *zds = ZSTD_createDStream_advanced(stackMem);
2217 if (!zds) {
2218 return NULL;
2219 }
2220
2221 zds->maxWindowSize = maxWindowSize;
2222 zds->stage = zdss_loadHeader;
2223 zds->lhSize = zds->inPos = zds->outStart = zds->outEnd = 0;
2224 ZSTD_freeDDict(zds->ddictLocal);
2225 zds->ddictLocal = NULL;
2226 zds->ddict = zds->ddictLocal;
2227 zds->legacyVersion = 0;
2228 zds->hostageByte = 0;
2229
2230 {
2231 size_t const blockSize = MIN(zds->maxWindowSize, ZSTD_BLOCKSIZE_ABSOLUTEMAX);
2232 size_t const neededOutSize = zds->maxWindowSize + blockSize + WILDCOPY_OVERLENGTH * 2;
2233
2234 zds->inBuff = (char *)ZSTD_malloc(blockSize, zds->customMem);
2235 zds->inBuffSize = blockSize;
2236 zds->outBuff = (char *)ZSTD_malloc(neededOutSize, zds->customMem);
2237 zds->outBuffSize = neededOutSize;
2238 if (zds->inBuff == NULL || zds->outBuff == NULL) {
2239 ZSTD_freeDStream(zds);
2240 return NULL;
2241 }
2242 }
2243 return zds;
2244}
2245
2246ZSTD_DStream *ZSTD_initDStream_usingDDict(size_t maxWindowSize, const ZSTD_DDict *ddict, void *workspace, size_t workspaceSize)
2247{
2248 ZSTD_DStream *zds = ZSTD_initDStream(maxWindowSize, workspace, workspaceSize);
2249 if (zds) {
2250 zds->ddict = ddict;
2251 }
2252 return zds;
2253}
2254
2255size_t ZSTD_freeDStream(ZSTD_DStream *zds)
2256{
2257 if (zds == NULL)
2258 return 0; /* support free on null */
2259 {
2260 ZSTD_customMem const cMem = zds->customMem;
2261 ZSTD_freeDCtx(zds->dctx);
2262 zds->dctx = NULL;
2263 ZSTD_freeDDict(zds->ddictLocal);
2264 zds->ddictLocal = NULL;
2265 ZSTD_free(zds->inBuff, cMem);
2266 zds->inBuff = NULL;
2267 ZSTD_free(zds->outBuff, cMem);
2268 zds->outBuff = NULL;
2269 ZSTD_free(zds, cMem);
2270 return 0;
2271 }
2272}
2273
2274/* *** Initialization *** */
2275
2276size_t ZSTD_DStreamInSize(void) { return ZSTD_BLOCKSIZE_ABSOLUTEMAX + ZSTD_blockHeaderSize; }
2277size_t ZSTD_DStreamOutSize(void) { return ZSTD_BLOCKSIZE_ABSOLUTEMAX; }
2278
2279size_t ZSTD_resetDStream(ZSTD_DStream *zds)
2280{
2281 zds->stage = zdss_loadHeader;
2282 zds->lhSize = zds->inPos = zds->outStart = zds->outEnd = 0;
2283 zds->legacyVersion = 0;
2284 zds->hostageByte = 0;
2285 return ZSTD_frameHeaderSize_prefix;
2286}
2287
2288/* ***** Decompression ***** */
2289
2290ZSTD_STATIC size_t ZSTD_limitCopy(void *dst, size_t dstCapacity, const void *src, size_t srcSize)
2291{
2292 size_t const length = MIN(dstCapacity, srcSize);
2293 memcpy(dst, src, length);
2294 return length;
2295}
2296
2297size_t ZSTD_decompressStream(ZSTD_DStream *zds, ZSTD_outBuffer *output, ZSTD_inBuffer *input)
2298{
2299 const char *const istart = (const char *)(input->src) + input->pos;
2300 const char *const iend = (const char *)(input->src) + input->size;
2301 const char *ip = istart;
2302 char *const ostart = (char *)(output->dst) + output->pos;
2303 char *const oend = (char *)(output->dst) + output->size;
2304 char *op = ostart;
2305 U32 someMoreWork = 1;
2306
2307 while (someMoreWork) {
2308 switch (zds->stage) {
2309 case zdss_init:
2310 ZSTD_resetDStream(zds); /* transparent reset on starting decoding a new frame */
2311 /* fall-through */
2312
2313 case zdss_loadHeader: {
2314 size_t const hSize = ZSTD_getFrameParams(&zds->fParams, zds->headerBuffer, zds->lhSize);
2315 if (ZSTD_isError(hSize))
2316 return hSize;
2317 if (hSize != 0) { /* need more input */
2318 size_t const toLoad = hSize - zds->lhSize; /* if hSize!=0, hSize > zds->lhSize */
2319 if (toLoad > (size_t)(iend - ip)) { /* not enough input to load full header */
2320 memcpy(zds->headerBuffer + zds->lhSize, ip, iend - ip);
2321 zds->lhSize += iend - ip;
2322 input->pos = input->size;
2323 return (MAX(ZSTD_frameHeaderSize_min, hSize) - zds->lhSize) +
2324 ZSTD_blockHeaderSize; /* remaining header bytes + next block header */
2325 }
2326 memcpy(zds->headerBuffer + zds->lhSize, ip, toLoad);
2327 zds->lhSize = hSize;
2328 ip += toLoad;
2329 break;
2330 }
2331
2332 /* check for single-pass mode opportunity */
2333 if (zds->fParams.frameContentSize && zds->fParams.windowSize /* skippable frame if == 0 */
2334 && (U64)(size_t)(oend - op) >= zds->fParams.frameContentSize) {
2335 size_t const cSize = ZSTD_findFrameCompressedSize(istart, iend - istart);
2336 if (cSize <= (size_t)(iend - istart)) {
2337 size_t const decompressedSize = ZSTD_decompress_usingDDict(zds->dctx, op, oend - op, istart, cSize, zds->ddict);
2338 if (ZSTD_isError(decompressedSize))
2339 return decompressedSize;
2340 ip = istart + cSize;
2341 op += decompressedSize;
2342 zds->dctx->expected = 0;
2343 zds->stage = zdss_init;
2344 someMoreWork = 0;
2345 break;
2346 }
2347 }
2348
2349 /* Consume header */
2350 ZSTD_refDDict(zds->dctx, zds->ddict);
2351 {
2352 size_t const h1Size = ZSTD_nextSrcSizeToDecompress(zds->dctx); /* == ZSTD_frameHeaderSize_prefix */
2353 CHECK_F(ZSTD_decompressContinue(zds->dctx, NULL, 0, zds->headerBuffer, h1Size));
2354 {
2355 size_t const h2Size = ZSTD_nextSrcSizeToDecompress(zds->dctx);
2356 CHECK_F(ZSTD_decompressContinue(zds->dctx, NULL, 0, zds->headerBuffer + h1Size, h2Size));
2357 }
2358 }
2359
2360 zds->fParams.windowSize = MAX(zds->fParams.windowSize, 1U << ZSTD_WINDOWLOG_ABSOLUTEMIN);
2361 if (zds->fParams.windowSize > zds->maxWindowSize)
2362 return ERROR(frameParameter_windowTooLarge);
2363
2364 /* Buffers are preallocated, but double check */
2365 {
2366 size_t const blockSize = MIN(zds->maxWindowSize, ZSTD_BLOCKSIZE_ABSOLUTEMAX);
2367 size_t const neededOutSize = zds->maxWindowSize + blockSize + WILDCOPY_OVERLENGTH * 2;
2368 if (zds->inBuffSize < blockSize) {
2369 return ERROR(GENERIC);
2370 }
2371 if (zds->outBuffSize < neededOutSize) {
2372 return ERROR(GENERIC);
2373 }
2374 zds->blockSize = blockSize;
2375 }
2376 zds->stage = zdss_read;
2377 }
2378 /* pass-through */
2379
2380 case zdss_read: {
2381 size_t const neededInSize = ZSTD_nextSrcSizeToDecompress(zds->dctx);
2382 if (neededInSize == 0) { /* end of frame */
2383 zds->stage = zdss_init;
2384 someMoreWork = 0;
2385 break;
2386 }
2387 if ((size_t)(iend - ip) >= neededInSize) { /* decode directly from src */
2388 const int isSkipFrame = ZSTD_isSkipFrame(zds->dctx);
2389 size_t const decodedSize = ZSTD_decompressContinue(zds->dctx, zds->outBuff + zds->outStart,
2390 (isSkipFrame ? 0 : zds->outBuffSize - zds->outStart), ip, neededInSize);
2391 if (ZSTD_isError(decodedSize))
2392 return decodedSize;
2393 ip += neededInSize;
2394 if (!decodedSize && !isSkipFrame)
2395 break; /* this was just a header */
2396 zds->outEnd = zds->outStart + decodedSize;
2397 zds->stage = zdss_flush;
2398 break;
2399 }
2400 if (ip == iend) {
2401 someMoreWork = 0;
2402 break;
2403 } /* no more input */
2404 zds->stage = zdss_load;
2405 /* pass-through */
2406 }
2407
2408 case zdss_load: {
2409 size_t const neededInSize = ZSTD_nextSrcSizeToDecompress(zds->dctx);
2410 size_t const toLoad = neededInSize - zds->inPos; /* should always be <= remaining space within inBuff */
2411 size_t loadedSize;
2412 if (toLoad > zds->inBuffSize - zds->inPos)
2413 return ERROR(corruption_detected); /* should never happen */
2414 loadedSize = ZSTD_limitCopy(zds->inBuff + zds->inPos, toLoad, ip, iend - ip);
2415 ip += loadedSize;
2416 zds->inPos += loadedSize;
2417 if (loadedSize < toLoad) {
2418 someMoreWork = 0;
2419 break;
2420 } /* not enough input, wait for more */
2421
2422 /* decode loaded input */
2423 {
2424 const int isSkipFrame = ZSTD_isSkipFrame(zds->dctx);
2425 size_t const decodedSize = ZSTD_decompressContinue(zds->dctx, zds->outBuff + zds->outStart, zds->outBuffSize - zds->outStart,
2426 zds->inBuff, neededInSize);
2427 if (ZSTD_isError(decodedSize))
2428 return decodedSize;
2429 zds->inPos = 0; /* input is consumed */
2430 if (!decodedSize && !isSkipFrame) {
2431 zds->stage = zdss_read;
2432 break;
2433 } /* this was just a header */
2434 zds->outEnd = zds->outStart + decodedSize;
2435 zds->stage = zdss_flush;
2436 /* pass-through */
2437 }
2438 }
2439
2440 case zdss_flush: {
2441 size_t const toFlushSize = zds->outEnd - zds->outStart;
2442 size_t const flushedSize = ZSTD_limitCopy(op, oend - op, zds->outBuff + zds->outStart, toFlushSize);
2443 op += flushedSize;
2444 zds->outStart += flushedSize;
2445 if (flushedSize == toFlushSize) { /* flush completed */
2446 zds->stage = zdss_read;
2447 if (zds->outStart + zds->blockSize > zds->outBuffSize)
2448 zds->outStart = zds->outEnd = 0;
2449 break;
2450 }
2451 /* cannot complete flush */
2452 someMoreWork = 0;
2453 break;
2454 }
2455 default:
2456 return ERROR(GENERIC); /* impossible */
2457 }
2458 }
2459
2460 /* result */
2461 input->pos += (size_t)(ip - istart);
2462 output->pos += (size_t)(op - ostart);
2463 {
2464 size_t nextSrcSizeHint = ZSTD_nextSrcSizeToDecompress(zds->dctx);
2465 if (!nextSrcSizeHint) { /* frame fully decoded */
2466 if (zds->outEnd == zds->outStart) { /* output fully flushed */
2467 if (zds->hostageByte) {
2468 if (input->pos >= input->size) {
2469 zds->stage = zdss_read;
2470 return 1;
2471 } /* can't release hostage (not present) */
2472 input->pos++; /* release hostage */
2473 }
2474 return 0;
2475 }
2476 if (!zds->hostageByte) { /* output not fully flushed; keep last byte as hostage; will be released when all output is flushed */
2477 input->pos--; /* note : pos > 0, otherwise, impossible to finish reading last block */
2478 zds->hostageByte = 1;
2479 }
2480 return 1;
2481 }
2482 nextSrcSizeHint += ZSTD_blockHeaderSize * (ZSTD_nextInputType(zds->dctx) == ZSTDnit_block); /* preload header of next block */
2483 if (zds->inPos > nextSrcSizeHint)
2484 return ERROR(GENERIC); /* should never happen */
2485 nextSrcSizeHint -= zds->inPos; /* already loaded*/
2486 return nextSrcSizeHint;
2487 }
2488}
2489
2490EXPORT_SYMBOL(ZSTD_DCtxWorkspaceBound);
2491EXPORT_SYMBOL(ZSTD_initDCtx);
2492EXPORT_SYMBOL(ZSTD_decompressDCtx);
2493EXPORT_SYMBOL(ZSTD_decompress_usingDict);
2494
2495EXPORT_SYMBOL(ZSTD_DDictWorkspaceBound);
2496EXPORT_SYMBOL(ZSTD_initDDict);
2497EXPORT_SYMBOL(ZSTD_decompress_usingDDict);
2498
2499EXPORT_SYMBOL(ZSTD_DStreamWorkspaceBound);
2500EXPORT_SYMBOL(ZSTD_initDStream);
2501EXPORT_SYMBOL(ZSTD_initDStream_usingDDict);
2502EXPORT_SYMBOL(ZSTD_resetDStream);
2503EXPORT_SYMBOL(ZSTD_decompressStream);
2504EXPORT_SYMBOL(ZSTD_DStreamInSize);
2505EXPORT_SYMBOL(ZSTD_DStreamOutSize);
2506
2507EXPORT_SYMBOL(ZSTD_findFrameCompressedSize);
2508EXPORT_SYMBOL(ZSTD_getFrameContentSize);
2509EXPORT_SYMBOL(ZSTD_findDecompressedSize);
2510
2511EXPORT_SYMBOL(ZSTD_isFrame);
2512EXPORT_SYMBOL(ZSTD_getDictID_fromDict);
2513EXPORT_SYMBOL(ZSTD_getDictID_fromDDict);
2514EXPORT_SYMBOL(ZSTD_getDictID_fromFrame);
2515
2516EXPORT_SYMBOL(ZSTD_getFrameParams);
2517EXPORT_SYMBOL(ZSTD_decompressBegin);
2518EXPORT_SYMBOL(ZSTD_decompressBegin_usingDict);
2519EXPORT_SYMBOL(ZSTD_copyDCtx);
2520EXPORT_SYMBOL(ZSTD_nextSrcSizeToDecompress);
2521EXPORT_SYMBOL(ZSTD_decompressContinue);
2522EXPORT_SYMBOL(ZSTD_nextInputType);
2523
2524EXPORT_SYMBOL(ZSTD_decompressBlock);
2525EXPORT_SYMBOL(ZSTD_insertBlock);
2526
2527MODULE_LICENSE("Dual BSD/GPL");
2528MODULE_DESCRIPTION("Zstd Decompressor");
Empty description
This page took 0.34192 seconds and 4 git commands to generate.