Line data Source code
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 this source tree. An additional grant
7 : * of patent rights can be found in the PATENTS file in the same directory.
8 : */
9 :
10 :
11 : /* ***************************************************************
12 : * Tuning parameters
13 : *****************************************************************/
14 : /*!
15 : * HEAPMODE :
16 : * Select how default decompression function ZSTD_decompress() will allocate memory,
17 : * in memory stack (0), or in memory heap (1, requires malloc())
18 : */
19 : #ifndef ZSTD_HEAPMODE
20 : # define ZSTD_HEAPMODE 1
21 : #endif
22 :
23 : /*!
24 : * LEGACY_SUPPORT :
25 : * if set to 1, ZSTD_decompress() can decode older formats (v0.1+)
26 : */
27 : #ifndef ZSTD_LEGACY_SUPPORT
28 : # define ZSTD_LEGACY_SUPPORT 0
29 : #endif
30 :
31 : /*!
32 : * MAXWINDOWSIZE_DEFAULT :
33 : * maximum window size accepted by DStream, by default.
34 : * Frames requiring more memory will be rejected.
35 : */
36 : #ifndef ZSTD_MAXWINDOWSIZE_DEFAULT
37 : # define ZSTD_MAXWINDOWSIZE_DEFAULT (257 << 20) /* 257 MB */
38 : #endif
39 :
40 :
41 : /*-*******************************************************
42 : * Dependencies
43 : *********************************************************/
44 : #include <string.h> /* memcpy, memmove, memset */
45 : #include "mem.h" /* low level memory routines */
46 : #define XXH_STATIC_LINKING_ONLY /* XXH64_state_t */
47 : #include "xxhash.h" /* XXH64_* */
48 : #define FSE_STATIC_LINKING_ONLY
49 : #include "fse.h"
50 : #define HUF_STATIC_LINKING_ONLY
51 : #include "huf.h"
52 : #include "zstd_internal.h"
53 :
54 : #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT>=1)
55 : # include "zstd_legacy.h"
56 : #endif
57 :
58 :
59 : /*-*************************************
60 : * Macros
61 : ***************************************/
62 : #define ZSTD_isError ERR_isError /* for inlining */
63 : #define FSE_isError ERR_isError
64 : #define HUF_isError ERR_isError
65 :
66 :
67 : /*_*******************************************************
68 : * Memory operations
69 : **********************************************************/
70 74516 : static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
71 :
72 :
73 : /*-*************************************************************
74 : * Context management
75 : ***************************************************************/
76 : typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,
77 : ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock,
78 : ZSTDds_decompressLastBlock, ZSTDds_checkChecksum,
79 : ZSTDds_decodeSkippableHeader, ZSTDds_skipFrame } ZSTD_dStage;
80 :
81 : struct ZSTD_DCtx_s
82 : {
83 : const FSE_DTable* LLTptr;
84 : const FSE_DTable* MLTptr;
85 : const FSE_DTable* OFTptr;
86 : const HUF_DTable* HUFptr;
87 : FSE_DTable LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
88 : FSE_DTable OFTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
89 : FSE_DTable MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
90 : HUF_DTable hufTable[HUF_DTABLE_SIZE(HufLog)]; /* can accommodate HUF_decompress4X */
91 : const void* previousDstEnd;
92 : const void* base;
93 : const void* vBase;
94 : const void* dictEnd;
95 : size_t expected;
96 : U32 rep[ZSTD_REP_NUM];
97 : ZSTD_frameParams fParams;
98 : blockType_e bType; /* used in ZSTD_decompressContinue(), to transfer blockType between header decoding and block decoding stages */
99 : ZSTD_dStage stage;
100 : U32 litEntropy;
101 : U32 fseEntropy;
102 : XXH64_state_t xxhState;
103 : size_t headerSize;
104 : U32 dictID;
105 : const BYTE* litPtr;
106 : ZSTD_customMem customMem;
107 : size_t litBufSize;
108 : size_t litSize;
109 : size_t rleSize;
110 : BYTE litBuffer[ZSTD_BLOCKSIZE_ABSOLUTEMAX + WILDCOPY_OVERLENGTH];
111 : BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX];
112 : }; /* typedef'd to ZSTD_DCtx within "zstd.h" */
113 :
114 0 : size_t ZSTD_sizeof_DCtx (const ZSTD_DCtx* dctx) { if (dctx==NULL) return 0; return sizeof(ZSTD_DCtx); } /* support sizeof on NULL */
115 :
116 0 : size_t ZSTD_estimateDCtxSize(void) { return sizeof(ZSTD_DCtx); }
117 :
118 148 : size_t ZSTD_decompressBegin(ZSTD_DCtx* dctx)
119 : {
120 148 : dctx->expected = ZSTD_frameHeaderSize_prefix;
121 148 : dctx->stage = ZSTDds_getFrameHeaderSize;
122 148 : dctx->previousDstEnd = NULL;
123 148 : dctx->base = NULL;
124 148 : dctx->vBase = NULL;
125 148 : dctx->dictEnd = NULL;
126 148 : dctx->hufTable[0] = (HUF_DTable)((HufLog)*0x1000001); /* cover both little and big endian */
127 148 : dctx->litEntropy = dctx->fseEntropy = 0;
128 148 : dctx->dictID = 0;
129 : MEM_STATIC_ASSERT(sizeof(dctx->rep) == sizeof(repStartValue));
130 148 : memcpy(dctx->rep, repStartValue, sizeof(repStartValue)); /* initial repcodes */
131 148 : dctx->LLTptr = dctx->LLTable;
132 148 : dctx->MLTptr = dctx->MLTable;
133 148 : dctx->OFTptr = dctx->OFTable;
134 148 : dctx->HUFptr = dctx->hufTable;
135 148 : return 0;
136 : }
137 :
138 74 : ZSTD_DCtx* ZSTD_createDCtx_advanced(ZSTD_customMem customMem)
139 : {
140 : ZSTD_DCtx* dctx;
141 :
142 74 : if (!customMem.customAlloc && !customMem.customFree) customMem = defaultCustomMem;
143 74 : if (!customMem.customAlloc || !customMem.customFree) return NULL;
144 :
145 74 : dctx = (ZSTD_DCtx*)ZSTD_malloc(sizeof(ZSTD_DCtx), customMem);
146 74 : if (!dctx) return NULL;
147 74 : memcpy(&dctx->customMem, &customMem, sizeof(customMem));
148 74 : ZSTD_decompressBegin(dctx);
149 74 : return dctx;
150 : }
151 :
152 74 : ZSTD_DCtx* ZSTD_createDCtx(void)
153 : {
154 74 : return ZSTD_createDCtx_advanced(defaultCustomMem);
155 : }
156 :
157 74 : size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx)
158 : {
159 74 : if (dctx==NULL) return 0; /* support free on NULL */
160 74 : ZSTD_free(dctx, dctx->customMem);
161 74 : return 0; /* reserved as a potential error code in the future */
162 : }
163 :
164 0 : void ZSTD_copyDCtx(ZSTD_DCtx* dstDCtx, const ZSTD_DCtx* srcDCtx)
165 : {
166 0 : size_t const workSpaceSize = (ZSTD_BLOCKSIZE_ABSOLUTEMAX+WILDCOPY_OVERLENGTH) + ZSTD_frameHeaderSize_max;
167 0 : memcpy(dstDCtx, srcDCtx, sizeof(ZSTD_DCtx) - workSpaceSize); /* no need to copy workspace */
168 0 : }
169 :
170 0 : static void ZSTD_refDCtx(ZSTD_DCtx* dstDCtx, const ZSTD_DCtx* srcDCtx)
171 : {
172 0 : ZSTD_decompressBegin(dstDCtx); /* init */
173 0 : dstDCtx->dictEnd = srcDCtx->dictEnd;
174 0 : dstDCtx->vBase = srcDCtx->vBase;
175 0 : dstDCtx->base = srcDCtx->base;
176 0 : dstDCtx->previousDstEnd = srcDCtx->previousDstEnd;
177 0 : dstDCtx->dictID = srcDCtx->dictID;
178 0 : dstDCtx->litEntropy = srcDCtx->litEntropy;
179 0 : dstDCtx->fseEntropy = srcDCtx->fseEntropy;
180 0 : dstDCtx->LLTptr = srcDCtx->LLTable;
181 0 : dstDCtx->MLTptr = srcDCtx->MLTable;
182 0 : dstDCtx->OFTptr = srcDCtx->OFTable;
183 0 : dstDCtx->HUFptr = srcDCtx->hufTable;
184 0 : dstDCtx->rep[0] = srcDCtx->rep[0];
185 0 : dstDCtx->rep[1] = srcDCtx->rep[1];
186 0 : dstDCtx->rep[2] = srcDCtx->rep[2];
187 0 : }
188 :
189 :
190 : /*-*************************************************************
191 : * Decompression section
192 : ***************************************************************/
193 :
194 : /* See compression format details in : zstd_compression_format.md */
195 :
196 : /** ZSTD_frameHeaderSize() :
197 : * srcSize must be >= ZSTD_frameHeaderSize_prefix.
198 : * @return : size of the Frame Header */
199 148 : static size_t ZSTD_frameHeaderSize(const void* src, size_t srcSize)
200 : {
201 148 : if (srcSize < ZSTD_frameHeaderSize_prefix) return ERROR(srcSize_wrong);
202 148 : { BYTE const fhd = ((const BYTE*)src)[4];
203 148 : U32 const dictID= fhd & 3;
204 148 : U32 const singleSegment = (fhd >> 5) & 1;
205 148 : U32 const fcsId = fhd >> 6;
206 148 : return ZSTD_frameHeaderSize_prefix + !singleSegment + ZSTD_did_fieldSize[dictID] + ZSTD_fcs_fieldSize[fcsId]
207 148 : + (singleSegment && !fcsId);
208 : }
209 : }
210 :
211 :
212 : /** ZSTD_getFrameParams() :
213 : * decode Frame Header, or require larger `srcSize`.
214 : * @return : 0, `fparamsPtr` is correctly filled,
215 : * >0, `srcSize` is too small, result is expected `srcSize`,
216 : * or an error code, which can be tested using ZSTD_isError() */
217 74 : size_t ZSTD_getFrameParams(ZSTD_frameParams* fparamsPtr, const void* src, size_t srcSize)
218 : {
219 74 : const BYTE* ip = (const BYTE*)src;
220 :
221 74 : if (srcSize < ZSTD_frameHeaderSize_prefix) return ZSTD_frameHeaderSize_prefix;
222 74 : if (MEM_readLE32(src) != ZSTD_MAGICNUMBER) {
223 0 : if ((MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
224 0 : if (srcSize < ZSTD_skippableHeaderSize) return ZSTD_skippableHeaderSize; /* magic number + skippable frame length */
225 0 : memset(fparamsPtr, 0, sizeof(*fparamsPtr));
226 0 : fparamsPtr->frameContentSize = MEM_readLE32((const char *)src + 4);
227 0 : fparamsPtr->windowSize = 0; /* windowSize==0 means a frame is skippable */
228 0 : return 0;
229 : }
230 0 : return ERROR(prefix_unknown);
231 : }
232 :
233 : /* ensure there is enough `srcSize` to fully read/decode frame header */
234 74 : { size_t const fhsize = ZSTD_frameHeaderSize(src, srcSize);
235 74 : if (srcSize < fhsize) return fhsize; }
236 :
237 74 : { BYTE const fhdByte = ip[4];
238 74 : size_t pos = 5;
239 74 : U32 const dictIDSizeCode = fhdByte&3;
240 74 : U32 const checksumFlag = (fhdByte>>2)&1;
241 74 : U32 const singleSegment = (fhdByte>>5)&1;
242 74 : U32 const fcsID = fhdByte>>6;
243 74 : U32 const windowSizeMax = 1U << ZSTD_WINDOWLOG_MAX;
244 74 : U32 windowSize = 0;
245 74 : U32 dictID = 0;
246 74 : U64 frameContentSize = 0;
247 74 : if ((fhdByte & 0x08) != 0) return ERROR(frameParameter_unsupported); /* reserved bits, which must be zero */
248 74 : if (!singleSegment) {
249 52 : BYTE const wlByte = ip[pos++];
250 52 : U32 const windowLog = (wlByte >> 3) + ZSTD_WINDOWLOG_ABSOLUTEMIN;
251 52 : if (windowLog > ZSTD_WINDOWLOG_MAX) return ERROR(frameParameter_unsupported);
252 52 : windowSize = (1U << windowLog);
253 52 : windowSize += (windowSize >> 3) * (wlByte&7);
254 : }
255 :
256 74 : switch(dictIDSizeCode)
257 : {
258 : default: /* impossible */
259 74 : case 0 : break;
260 0 : case 1 : dictID = ip[pos]; pos++; break;
261 0 : case 2 : dictID = MEM_readLE16(ip+pos); pos+=2; break;
262 0 : case 3 : dictID = MEM_readLE32(ip+pos); pos+=4; break;
263 : }
264 74 : switch(fcsID)
265 : {
266 : default: /* impossible */
267 0 : case 0 : if (singleSegment) frameContentSize = ip[pos]; break;
268 8 : case 1 : frameContentSize = MEM_readLE16(ip+pos)+256; break;
269 66 : case 2 : frameContentSize = MEM_readLE32(ip+pos); break;
270 0 : case 3 : frameContentSize = MEM_readLE64(ip+pos); break;
271 : }
272 74 : if (!windowSize) windowSize = (U32)frameContentSize;
273 74 : if (windowSize > windowSizeMax) return ERROR(frameParameter_unsupported);
274 74 : fparamsPtr->frameContentSize = frameContentSize;
275 74 : fparamsPtr->windowSize = windowSize;
276 74 : fparamsPtr->dictID = dictID;
277 74 : fparamsPtr->checksumFlag = checksumFlag;
278 : }
279 74 : return 0;
280 : }
281 :
282 :
283 : /** ZSTD_getDecompressedSize() :
284 : * compatible with legacy mode
285 : * @return : decompressed size if known, 0 otherwise
286 : note : 0 can mean any of the following :
287 : - decompressed size is not present within frame header
288 : - frame header unknown / not supported
289 : - frame header not complete (`srcSize` too small) */
290 0 : unsigned long long ZSTD_getDecompressedSize(const void* src, size_t srcSize)
291 : {
292 : #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT==1)
293 : if (ZSTD_isLegacy(src, srcSize)) return ZSTD_getDecompressedSize_legacy(src, srcSize);
294 : #endif
295 : { ZSTD_frameParams fparams;
296 0 : size_t const frResult = ZSTD_getFrameParams(&fparams, src, srcSize);
297 0 : if (frResult!=0) return 0;
298 0 : return fparams.frameContentSize;
299 : }
300 : }
301 :
302 :
303 : /** ZSTD_decodeFrameHeader() :
304 : * `srcSize` must be the size provided by ZSTD_frameHeaderSize().
305 : * @return : 0 if success, or an error code, which can be tested using ZSTD_isError() */
306 74 : static size_t ZSTD_decodeFrameHeader(ZSTD_DCtx* dctx, const void* src, size_t srcSize)
307 : {
308 74 : size_t const result = ZSTD_getFrameParams(&(dctx->fParams), src, srcSize);
309 74 : if (dctx->fParams.dictID && (dctx->dictID != dctx->fParams.dictID)) return ERROR(dictionary_wrong);
310 74 : if (dctx->fParams.checksumFlag) XXH64_reset(&dctx->xxhState, 0);
311 74 : return result;
312 : }
313 :
314 :
315 : typedef struct
316 : {
317 : blockType_e blockType;
318 : U32 lastBlock;
319 : U32 origSize;
320 : } blockProperties_t;
321 :
322 : /*! ZSTD_getcBlockSize() :
323 : * Provides the size of compressed block from block header `src` */
324 3326 : size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
325 : {
326 3326 : if (srcSize < ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
327 3326 : { U32 const cBlockHeader = MEM_readLE24(src);
328 3326 : U32 const cSize = cBlockHeader >> 3;
329 3326 : bpPtr->lastBlock = cBlockHeader & 1;
330 3326 : bpPtr->blockType = (blockType_e)((cBlockHeader >> 1) & 3);
331 3326 : bpPtr->origSize = cSize; /* only useful for RLE */
332 3326 : if (bpPtr->blockType == bt_rle) return 1;
333 3326 : if (bpPtr->blockType == bt_reserved) return ERROR(corruption_detected);
334 3326 : return cSize;
335 : }
336 : }
337 :
338 :
339 1280 : static size_t ZSTD_copyRawBlock(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
340 : {
341 1280 : if (srcSize > dstCapacity) return ERROR(dstSize_tooSmall);
342 1280 : memcpy(dst, src, srcSize);
343 1280 : return srcSize;
344 : }
345 :
346 :
347 0 : static size_t ZSTD_setRleBlock(void* dst, size_t dstCapacity, const void* src, size_t srcSize, size_t regenSize)
348 : {
349 0 : if (srcSize != 1) return ERROR(srcSize_wrong);
350 0 : if (regenSize > dstCapacity) return ERROR(dstSize_tooSmall);
351 0 : memset(dst, *(const BYTE*)src, regenSize);
352 0 : return regenSize;
353 : }
354 :
355 : /*! ZSTD_decodeLiteralsBlock() :
356 : @return : nb of bytes read from src (< srcSize ) */
357 2046 : size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx,
358 : const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */
359 : {
360 2046 : if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
361 :
362 2046 : { const BYTE* const istart = (const BYTE*) src;
363 2046 : symbolEncodingType_e const litEncType = (symbolEncodingType_e)(istart[0] & 3);
364 :
365 2046 : switch(litEncType)
366 : {
367 : case set_repeat:
368 0 : if (dctx->litEntropy==0) return ERROR(dictionary_corrupted);
369 : /* fall-through */
370 : case set_compressed:
371 2004 : if (srcSize < 5) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for case 3 */
372 : { size_t lhSize, litSize, litCSize;
373 2004 : U32 singleStream=0;
374 2004 : U32 const lhlCode = (istart[0] >> 2) & 3;
375 2004 : U32 const lhc = MEM_readLE32(istart);
376 2004 : switch(lhlCode)
377 : {
378 : case 0: case 1: default: /* note : default is impossible, since lhlCode into [0..3] */
379 : /* 2 - 2 - 10 - 10 */
380 18 : singleStream = !lhlCode;
381 18 : lhSize = 3;
382 18 : litSize = (lhc >> 4) & 0x3FF;
383 18 : litCSize = (lhc >> 14) & 0x3FF;
384 18 : break;
385 : case 2:
386 : /* 2 - 2 - 14 - 14 */
387 354 : lhSize = 4;
388 354 : litSize = (lhc >> 4) & 0x3FFF;
389 354 : litCSize = lhc >> 18;
390 354 : break;
391 : case 3:
392 : /* 2 - 2 - 18 - 18 */
393 1632 : lhSize = 5;
394 1632 : litSize = (lhc >> 4) & 0x3FFFF;
395 1632 : litCSize = (lhc >> 22) + (istart[4] << 10);
396 1632 : break;
397 : }
398 2004 : if (litSize > ZSTD_BLOCKSIZE_ABSOLUTEMAX) return ERROR(corruption_detected);
399 2004 : if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
400 :
401 4008 : if (HUF_isError((litEncType==set_repeat) ?
402 : ( singleStream ?
403 0 : HUF_decompress1X_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->HUFptr) :
404 0 : HUF_decompress4X_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->HUFptr) ) :
405 : ( singleStream ?
406 4004 : HUF_decompress1X2_DCtx(dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize) :
407 2000 : HUF_decompress4X_hufOnly (dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize)) ))
408 0 : return ERROR(corruption_detected);
409 :
410 2004 : dctx->litPtr = dctx->litBuffer;
411 2004 : dctx->litBufSize = ZSTD_BLOCKSIZE_ABSOLUTEMAX+WILDCOPY_OVERLENGTH;
412 2004 : dctx->litSize = litSize;
413 2004 : dctx->litEntropy = 1;
414 2004 : if (litEncType==set_compressed) dctx->HUFptr = dctx->hufTable;
415 2004 : return litCSize + lhSize;
416 : }
417 :
418 : case set_basic:
419 : { size_t litSize, lhSize;
420 42 : U32 const lhlCode = ((istart[0]) >> 2) & 3;
421 42 : switch(lhlCode)
422 : {
423 : case 0: case 2: default: /* note : default is impossible, since lhlCode into [0..3] */
424 0 : lhSize = 1;
425 0 : litSize = istart[0] >> 3;
426 0 : break;
427 : case 1:
428 6 : lhSize = 2;
429 6 : litSize = MEM_readLE16(istart) >> 4;
430 6 : break;
431 : case 3:
432 36 : lhSize = 3;
433 36 : litSize = MEM_readLE24(istart) >> 4;
434 36 : break;
435 : }
436 :
437 42 : if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */
438 0 : if (litSize+lhSize > srcSize) return ERROR(corruption_detected);
439 0 : memcpy(dctx->litBuffer, istart+lhSize, litSize);
440 0 : dctx->litPtr = dctx->litBuffer;
441 0 : dctx->litBufSize = ZSTD_BLOCKSIZE_ABSOLUTEMAX+8;
442 0 : dctx->litSize = litSize;
443 0 : return lhSize+litSize;
444 : }
445 : /* direct reference into compressed stream */
446 42 : dctx->litPtr = istart+lhSize;
447 42 : dctx->litBufSize = srcSize-lhSize;
448 42 : dctx->litSize = litSize;
449 42 : return lhSize+litSize;
450 : }
451 :
452 : case set_rle:
453 0 : { U32 const lhlCode = ((istart[0]) >> 2) & 3;
454 : size_t litSize, lhSize;
455 0 : switch(lhlCode)
456 : {
457 : case 0: case 2: default: /* note : default is impossible, since lhlCode into [0..3] */
458 0 : lhSize = 1;
459 0 : litSize = istart[0] >> 3;
460 0 : break;
461 : case 1:
462 0 : lhSize = 2;
463 0 : litSize = MEM_readLE16(istart) >> 4;
464 0 : break;
465 : case 3:
466 0 : lhSize = 3;
467 0 : litSize = MEM_readLE24(istart) >> 4;
468 0 : if (srcSize<4) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
469 0 : break;
470 : }
471 0 : if (litSize > ZSTD_BLOCKSIZE_ABSOLUTEMAX) return ERROR(corruption_detected);
472 0 : memset(dctx->litBuffer, istart[lhSize], litSize);
473 0 : dctx->litPtr = dctx->litBuffer;
474 0 : dctx->litBufSize = ZSTD_BLOCKSIZE_ABSOLUTEMAX+WILDCOPY_OVERLENGTH;
475 0 : dctx->litSize = litSize;
476 0 : return lhSize+1;
477 : }
478 : default:
479 0 : return ERROR(corruption_detected); /* impossible */
480 : }
481 : }
482 : }
483 :
484 :
485 : typedef union {
486 : FSE_decode_t realData;
487 : U32 alignedBy4;
488 : } FSE_decode_t4;
489 :
490 : static const FSE_decode_t4 LL_defaultDTable[(1<<LL_DEFAULTNORMLOG)+1] = {
491 : { { LL_DEFAULTNORMLOG, 1, 1 } }, /* header : tableLog, fastMode, fastMode */
492 : { { 0, 0, 4 } }, /* 0 : base, symbol, bits */
493 : { { 16, 0, 4 } },
494 : { { 32, 1, 5 } },
495 : { { 0, 3, 5 } },
496 : { { 0, 4, 5 } },
497 : { { 0, 6, 5 } },
498 : { { 0, 7, 5 } },
499 : { { 0, 9, 5 } },
500 : { { 0, 10, 5 } },
501 : { { 0, 12, 5 } },
502 : { { 0, 14, 6 } },
503 : { { 0, 16, 5 } },
504 : { { 0, 18, 5 } },
505 : { { 0, 19, 5 } },
506 : { { 0, 21, 5 } },
507 : { { 0, 22, 5 } },
508 : { { 0, 24, 5 } },
509 : { { 32, 25, 5 } },
510 : { { 0, 26, 5 } },
511 : { { 0, 27, 6 } },
512 : { { 0, 29, 6 } },
513 : { { 0, 31, 6 } },
514 : { { 32, 0, 4 } },
515 : { { 0, 1, 4 } },
516 : { { 0, 2, 5 } },
517 : { { 32, 4, 5 } },
518 : { { 0, 5, 5 } },
519 : { { 32, 7, 5 } },
520 : { { 0, 8, 5 } },
521 : { { 32, 10, 5 } },
522 : { { 0, 11, 5 } },
523 : { { 0, 13, 6 } },
524 : { { 32, 16, 5 } },
525 : { { 0, 17, 5 } },
526 : { { 32, 19, 5 } },
527 : { { 0, 20, 5 } },
528 : { { 32, 22, 5 } },
529 : { { 0, 23, 5 } },
530 : { { 0, 25, 4 } },
531 : { { 16, 25, 4 } },
532 : { { 32, 26, 5 } },
533 : { { 0, 28, 6 } },
534 : { { 0, 30, 6 } },
535 : { { 48, 0, 4 } },
536 : { { 16, 1, 4 } },
537 : { { 32, 2, 5 } },
538 : { { 32, 3, 5 } },
539 : { { 32, 5, 5 } },
540 : { { 32, 6, 5 } },
541 : { { 32, 8, 5 } },
542 : { { 32, 9, 5 } },
543 : { { 32, 11, 5 } },
544 : { { 32, 12, 5 } },
545 : { { 0, 15, 6 } },
546 : { { 32, 17, 5 } },
547 : { { 32, 18, 5 } },
548 : { { 32, 20, 5 } },
549 : { { 32, 21, 5 } },
550 : { { 32, 23, 5 } },
551 : { { 32, 24, 5 } },
552 : { { 0, 35, 6 } },
553 : { { 0, 34, 6 } },
554 : { { 0, 33, 6 } },
555 : { { 0, 32, 6 } },
556 : }; /* LL_defaultDTable */
557 :
558 : static const FSE_decode_t4 ML_defaultDTable[(1<<ML_DEFAULTNORMLOG)+1] = {
559 : { { ML_DEFAULTNORMLOG, 1, 1 } }, /* header : tableLog, fastMode, fastMode */
560 : { { 0, 0, 6 } }, /* 0 : base, symbol, bits */
561 : { { 0, 1, 4 } },
562 : { { 32, 2, 5 } },
563 : { { 0, 3, 5 } },
564 : { { 0, 5, 5 } },
565 : { { 0, 6, 5 } },
566 : { { 0, 8, 5 } },
567 : { { 0, 10, 6 } },
568 : { { 0, 13, 6 } },
569 : { { 0, 16, 6 } },
570 : { { 0, 19, 6 } },
571 : { { 0, 22, 6 } },
572 : { { 0, 25, 6 } },
573 : { { 0, 28, 6 } },
574 : { { 0, 31, 6 } },
575 : { { 0, 33, 6 } },
576 : { { 0, 35, 6 } },
577 : { { 0, 37, 6 } },
578 : { { 0, 39, 6 } },
579 : { { 0, 41, 6 } },
580 : { { 0, 43, 6 } },
581 : { { 0, 45, 6 } },
582 : { { 16, 1, 4 } },
583 : { { 0, 2, 4 } },
584 : { { 32, 3, 5 } },
585 : { { 0, 4, 5 } },
586 : { { 32, 6, 5 } },
587 : { { 0, 7, 5 } },
588 : { { 0, 9, 6 } },
589 : { { 0, 12, 6 } },
590 : { { 0, 15, 6 } },
591 : { { 0, 18, 6 } },
592 : { { 0, 21, 6 } },
593 : { { 0, 24, 6 } },
594 : { { 0, 27, 6 } },
595 : { { 0, 30, 6 } },
596 : { { 0, 32, 6 } },
597 : { { 0, 34, 6 } },
598 : { { 0, 36, 6 } },
599 : { { 0, 38, 6 } },
600 : { { 0, 40, 6 } },
601 : { { 0, 42, 6 } },
602 : { { 0, 44, 6 } },
603 : { { 32, 1, 4 } },
604 : { { 48, 1, 4 } },
605 : { { 16, 2, 4 } },
606 : { { 32, 4, 5 } },
607 : { { 32, 5, 5 } },
608 : { { 32, 7, 5 } },
609 : { { 32, 8, 5 } },
610 : { { 0, 11, 6 } },
611 : { { 0, 14, 6 } },
612 : { { 0, 17, 6 } },
613 : { { 0, 20, 6 } },
614 : { { 0, 23, 6 } },
615 : { { 0, 26, 6 } },
616 : { { 0, 29, 6 } },
617 : { { 0, 52, 6 } },
618 : { { 0, 51, 6 } },
619 : { { 0, 50, 6 } },
620 : { { 0, 49, 6 } },
621 : { { 0, 48, 6 } },
622 : { { 0, 47, 6 } },
623 : { { 0, 46, 6 } },
624 : }; /* ML_defaultDTable */
625 :
626 : static const FSE_decode_t4 OF_defaultDTable[(1<<OF_DEFAULTNORMLOG)+1] = {
627 : { { OF_DEFAULTNORMLOG, 1, 1 } }, /* header : tableLog, fastMode, fastMode */
628 : { { 0, 0, 5 } }, /* 0 : base, symbol, bits */
629 : { { 0, 6, 4 } },
630 : { { 0, 9, 5 } },
631 : { { 0, 15, 5 } },
632 : { { 0, 21, 5 } },
633 : { { 0, 3, 5 } },
634 : { { 0, 7, 4 } },
635 : { { 0, 12, 5 } },
636 : { { 0, 18, 5 } },
637 : { { 0, 23, 5 } },
638 : { { 0, 5, 5 } },
639 : { { 0, 8, 4 } },
640 : { { 0, 14, 5 } },
641 : { { 0, 20, 5 } },
642 : { { 0, 2, 5 } },
643 : { { 16, 7, 4 } },
644 : { { 0, 11, 5 } },
645 : { { 0, 17, 5 } },
646 : { { 0, 22, 5 } },
647 : { { 0, 4, 5 } },
648 : { { 16, 8, 4 } },
649 : { { 0, 13, 5 } },
650 : { { 0, 19, 5 } },
651 : { { 0, 1, 5 } },
652 : { { 16, 6, 4 } },
653 : { { 0, 10, 5 } },
654 : { { 0, 16, 5 } },
655 : { { 0, 28, 5 } },
656 : { { 0, 27, 5 } },
657 : { { 0, 26, 5 } },
658 : { { 0, 25, 5 } },
659 : { { 0, 24, 5 } },
660 : }; /* OF_defaultDTable */
661 :
662 : /*! ZSTD_buildSeqTable() :
663 : @return : nb bytes read from src,
664 : or an error code if it fails, testable with ZSTD_isError()
665 : */
666 4224 : static size_t ZSTD_buildSeqTable(FSE_DTable* DTableSpace, const FSE_DTable** DTablePtr,
667 : symbolEncodingType_e type, U32 max, U32 maxLog,
668 : const void* src, size_t srcSize,
669 : const FSE_decode_t4* defaultTable, U32 flagRepeatTable)
670 : {
671 4224 : const void* const tmpPtr = defaultTable; /* bypass strict aliasing */
672 4224 : switch(type)
673 : {
674 : case set_rle :
675 16 : if (!srcSize) return ERROR(srcSize_wrong);
676 16 : if ( (*(const BYTE*)src) > max) return ERROR(corruption_detected);
677 16 : FSE_buildDTable_rle(DTableSpace, *(const BYTE*)src);
678 16 : *DTablePtr = DTableSpace;
679 16 : return 1;
680 : case set_basic :
681 304 : *DTablePtr = (const FSE_DTable*)tmpPtr;
682 304 : return 0;
683 : case set_repeat:
684 0 : if (!flagRepeatTable) return ERROR(corruption_detected);
685 0 : return 0;
686 : default : /* impossible */
687 : case set_compressed :
688 : { U32 tableLog;
689 : S16 norm[MaxSeq+1];
690 3904 : size_t const headerSize = FSE_readNCount(norm, &max, &tableLog, src, srcSize);
691 3904 : if (FSE_isError(headerSize)) return ERROR(corruption_detected);
692 3904 : if (tableLog > maxLog) return ERROR(corruption_detected);
693 3904 : FSE_buildDTable(DTableSpace, norm, max, tableLog);
694 3904 : *DTablePtr = DTableSpace;
695 3904 : return headerSize;
696 : } }
697 : }
698 :
699 2046 : size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr,
700 : const void* src, size_t srcSize)
701 : {
702 2046 : const BYTE* const istart = (const BYTE* const)src;
703 2046 : const BYTE* const iend = istart + srcSize;
704 2046 : const BYTE* ip = istart;
705 :
706 : /* check */
707 2046 : if (srcSize < MIN_SEQUENCES_SIZE) return ERROR(srcSize_wrong);
708 :
709 : /* SeqHead */
710 2046 : { int nbSeq = *ip++;
711 2046 : if (!nbSeq) { *nbSeqPtr=0; return 1; }
712 1408 : if (nbSeq > 0x7F) {
713 1282 : if (nbSeq == 0xFF)
714 0 : nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2;
715 : else
716 1282 : nbSeq = ((nbSeq-0x80)<<8) + *ip++;
717 : }
718 1408 : *nbSeqPtr = nbSeq;
719 : }
720 :
721 : /* FSE table descriptors */
722 1408 : if (ip+4 > iend) return ERROR(srcSize_wrong); /* minimum possible size */
723 1408 : { symbolEncodingType_e const LLtype = (symbolEncodingType_e)(*ip >> 6);
724 1408 : symbolEncodingType_e const OFtype = (symbolEncodingType_e)((*ip >> 4) & 3);
725 1408 : symbolEncodingType_e const MLtype = (symbolEncodingType_e)((*ip >> 2) & 3);
726 1408 : ip++;
727 :
728 : /* Build DTables */
729 2816 : { size_t const llhSize = ZSTD_buildSeqTable(dctx->LLTable, &dctx->LLTptr,
730 : LLtype, MaxLL, LLFSELog,
731 1408 : ip, iend-ip, LL_defaultDTable, dctx->fseEntropy);
732 1408 : if (ZSTD_isError(llhSize)) return ERROR(corruption_detected);
733 1408 : ip += llhSize;
734 : }
735 2816 : { size_t const ofhSize = ZSTD_buildSeqTable(dctx->OFTable, &dctx->OFTptr,
736 : OFtype, MaxOff, OffFSELog,
737 1408 : ip, iend-ip, OF_defaultDTable, dctx->fseEntropy);
738 1408 : if (ZSTD_isError(ofhSize)) return ERROR(corruption_detected);
739 1408 : ip += ofhSize;
740 : }
741 2816 : { size_t const mlhSize = ZSTD_buildSeqTable(dctx->MLTable, &dctx->MLTptr,
742 : MLtype, MaxML, MLFSELog,
743 1408 : ip, iend-ip, ML_defaultDTable, dctx->fseEntropy);
744 1408 : if (ZSTD_isError(mlhSize)) return ERROR(corruption_detected);
745 1408 : ip += mlhSize;
746 : }
747 : }
748 :
749 1408 : return ip-istart;
750 : }
751 :
752 :
753 : typedef struct {
754 : size_t litLength;
755 : size_t matchLength;
756 : size_t offset;
757 : } seq_t;
758 :
759 : typedef struct {
760 : BIT_DStream_t DStream;
761 : FSE_DState_t stateLL;
762 : FSE_DState_t stateOffb;
763 : FSE_DState_t stateML;
764 : size_t prevOffset[ZSTD_REP_NUM];
765 : } seqState_t;
766 :
767 :
768 11115682 : static seq_t ZSTD_decodeSequence(seqState_t* seqState)
769 : {
770 : seq_t seq;
771 :
772 11115682 : U32 const llCode = FSE_peekSymbol(&seqState->stateLL);
773 11115682 : U32 const mlCode = FSE_peekSymbol(&seqState->stateML);
774 11115682 : U32 const ofCode = FSE_peekSymbol(&seqState->stateOffb); /* <= maxOff, by table construction */
775 :
776 11115682 : U32 const llBits = LL_bits[llCode];
777 11115682 : U32 const mlBits = ML_bits[mlCode];
778 11115682 : U32 const ofBits = ofCode;
779 11115682 : U32 const totalBits = llBits+mlBits+ofBits;
780 :
781 : static const U32 LL_base[MaxLL+1] = {
782 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
783 : 16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
784 : 0x2000, 0x4000, 0x8000, 0x10000 };
785 :
786 : static const U32 ML_base[MaxML+1] = {
787 : 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
788 : 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
789 : 35, 37, 39, 41, 43, 47, 51, 59, 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803,
790 : 0x1003, 0x2003, 0x4003, 0x8003, 0x10003 };
791 :
792 : static const U32 OF_base[MaxOff+1] = {
793 : 0, 1, 1, 5, 0xD, 0x1D, 0x3D, 0x7D,
794 : 0xFD, 0x1FD, 0x3FD, 0x7FD, 0xFFD, 0x1FFD, 0x3FFD, 0x7FFD,
795 : 0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD,
796 : 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD };
797 :
798 : /* sequence */
799 : { size_t offset;
800 11115682 : if (!ofCode)
801 4042868 : offset = 0;
802 : else {
803 7072814 : offset = OF_base[ofCode] + BIT_readBits(&seqState->DStream, ofBits); /* <= (ZSTD_WINDOWLOG_MAX-1) bits */
804 7072814 : if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream);
805 : }
806 :
807 11115682 : if (ofCode <= 1) {
808 4042868 : offset += (llCode==0);
809 4042868 : if (offset) {
810 497346 : size_t const temp = (offset==3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
811 497346 : if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1];
812 497346 : seqState->prevOffset[1] = seqState->prevOffset[0];
813 497346 : seqState->prevOffset[0] = offset = temp;
814 : } else {
815 3545522 : offset = seqState->prevOffset[0];
816 : }
817 : } else {
818 7072814 : seqState->prevOffset[2] = seqState->prevOffset[1];
819 7072814 : seqState->prevOffset[1] = seqState->prevOffset[0];
820 7072814 : seqState->prevOffset[0] = offset;
821 : }
822 11115682 : seq.offset = offset;
823 : }
824 :
825 11115682 : seq.matchLength = ML_base[mlCode] + ((mlCode>31) ? BIT_readBits(&seqState->DStream, mlBits) : 0); /* <= 16 bits */
826 11115682 : if (MEM_32bits() && (mlBits+llBits>24)) BIT_reloadDStream(&seqState->DStream);
827 :
828 11115682 : seq.litLength = LL_base[llCode] + ((llCode>15) ? BIT_readBits(&seqState->DStream, llBits) : 0); /* <= 16 bits */
829 11115682 : if (MEM_32bits() ||
830 78 : (totalBits > 64 - 7 - (LLFSELog+MLFSELog+OffFSELog)) ) BIT_reloadDStream(&seqState->DStream);
831 :
832 : /* ANS state update */
833 11115682 : FSE_updateState(&seqState->stateLL, &seqState->DStream); /* <= 9 bits */
834 11115682 : FSE_updateState(&seqState->stateML, &seqState->DStream); /* <= 9 bits */
835 11115682 : if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */
836 11115682 : FSE_updateState(&seqState->stateOffb, &seqState->DStream); /* <= 8 bits */
837 :
838 11115682 : return seq;
839 : }
840 :
841 :
842 : FORCE_INLINE
843 : size_t ZSTD_execSequence(BYTE* op,
844 : BYTE* const oend, seq_t sequence,
845 : const BYTE** litPtr, const BYTE* const litLimit_w,
846 : const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
847 : {
848 11115682 : BYTE* const oLitEnd = op + sequence.litLength;
849 11115682 : size_t const sequenceLength = sequence.litLength + sequence.matchLength;
850 11115682 : BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
851 11115682 : BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH;
852 11115682 : const BYTE* const iLitEnd = *litPtr + sequence.litLength;
853 11115682 : const BYTE* match = oLitEnd - sequence.offset;
854 :
855 : /* check */
856 11115682 : if ((oLitEnd>oend_w) | (oMatchEnd>oend)) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
857 11115682 : if (iLitEnd > litLimit_w) return ERROR(corruption_detected); /* over-read beyond lit buffer */
858 :
859 : /* copy Literals */
860 11115682 : ZSTD_copy8(op, *litPtr);
861 11115682 : if (sequence.litLength > 8)
862 606806 : ZSTD_wildcopy(op+8, (*litPtr)+8, sequence.litLength - 8); /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
863 11115682 : op = oLitEnd;
864 11115682 : *litPtr = iLitEnd; /* update for next sequence */
865 :
866 : /* copy Match */
867 11115682 : if (sequence.offset > (size_t)(oLitEnd - base)) {
868 : /* offset beyond prefix */
869 0 : if (sequence.offset > (size_t)(oLitEnd - vBase)) return ERROR(corruption_detected);
870 0 : match = dictEnd - (base-match);
871 0 : if (match + sequence.matchLength <= dictEnd) {
872 0 : memmove(oLitEnd, match, sequence.matchLength);
873 0 : return sequenceLength;
874 : }
875 : /* span extDict & currentPrefixSegment */
876 0 : { size_t const length1 = dictEnd - match;
877 0 : memmove(oLitEnd, match, length1);
878 0 : op = oLitEnd + length1;
879 0 : sequence.matchLength -= length1;
880 0 : match = base;
881 : } }
882 :
883 : /* match within prefix */
884 11115682 : if (sequence.offset < 8) {
885 : /* close range match, overlap */
886 : static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
887 : static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* substracted */
888 74516 : int const sub2 = dec64table[sequence.offset];
889 74516 : op[0] = match[0];
890 74516 : op[1] = match[1];
891 74516 : op[2] = match[2];
892 74516 : op[3] = match[3];
893 74516 : match += dec32table[sequence.offset];
894 74516 : ZSTD_copy4(op+4, match);
895 74516 : match -= sub2;
896 : } else {
897 11041166 : ZSTD_copy8(op, match);
898 : }
899 11115682 : op += 8; match += 8;
900 :
901 11115682 : if (oMatchEnd > oend-(16-MINMATCH)) {
902 66 : if (op < oend_w) {
903 32 : ZSTD_wildcopy(op, match, oend_w - op);
904 32 : match += oend_w - op;
905 32 : op = oend_w;
906 : }
907 256 : while (op < oMatchEnd) *op++ = *match++;
908 : } else {
909 11115616 : ZSTD_wildcopy(op, match, sequence.matchLength-8); /* works even if matchLength < 8 */
910 : }
911 11115682 : return sequenceLength;
912 : }
913 :
914 :
915 2046 : static size_t ZSTD_decompressSequences(
916 : ZSTD_DCtx* dctx,
917 : void* dst, size_t maxDstSize,
918 : const void* seqStart, size_t seqSize)
919 : {
920 2046 : const BYTE* ip = (const BYTE*)seqStart;
921 2046 : const BYTE* const iend = ip + seqSize;
922 2046 : BYTE* const ostart = (BYTE* const)dst;
923 2046 : BYTE* const oend = ostart + maxDstSize;
924 2046 : BYTE* op = ostart;
925 2046 : const BYTE* litPtr = dctx->litPtr;
926 2046 : const BYTE* const litLimit_w = litPtr + dctx->litBufSize - WILDCOPY_OVERLENGTH;
927 2046 : const BYTE* const litEnd = litPtr + dctx->litSize;
928 2046 : const BYTE* const base = (const BYTE*) (dctx->base);
929 2046 : const BYTE* const vBase = (const BYTE*) (dctx->vBase);
930 2046 : const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
931 : int nbSeq;
932 :
933 : /* Build Decoding Tables */
934 2046 : { size_t const seqHSize = ZSTD_decodeSeqHeaders(dctx, &nbSeq, ip, seqSize);
935 2046 : if (ZSTD_isError(seqHSize)) return seqHSize;
936 2046 : ip += seqHSize;
937 : }
938 :
939 : /* Regen sequences */
940 2046 : if (nbSeq) {
941 : seqState_t seqState;
942 1408 : dctx->fseEntropy = 1;
943 1408 : { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->rep[i]; }
944 1408 : CHECK_E(BIT_initDStream(&seqState.DStream, ip, iend-ip), corruption_detected);
945 1408 : FSE_initDState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
946 1408 : FSE_initDState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
947 1408 : FSE_initDState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
948 :
949 11118498 : for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && nbSeq ; ) {
950 11115682 : nbSeq--;
951 11115682 : { seq_t const sequence = ZSTD_decodeSequence(&seqState);
952 11115682 : size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litLimit_w, base, vBase, dictEnd);
953 11115682 : if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
954 11115682 : op += oneSeqSize;
955 : } }
956 :
957 : /* check if reached exact end */
958 1408 : if (nbSeq) return ERROR(corruption_detected);
959 : /* save reps for next block */
960 1408 : { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->rep[i] = (U32)(seqState.prevOffset[i]); }
961 : }
962 :
963 : /* last literal segment */
964 2046 : { size_t const lastLLSize = litEnd - litPtr;
965 2046 : if (lastLLSize > (size_t)(oend-op)) return ERROR(dstSize_tooSmall);
966 2046 : memcpy(op, litPtr, lastLLSize);
967 2046 : op += lastLLSize;
968 : }
969 :
970 2046 : return op-ostart;
971 : }
972 :
973 :
974 74 : static void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst)
975 : {
976 74 : if (dst != dctx->previousDstEnd) { /* not contiguous */
977 74 : dctx->dictEnd = dctx->previousDstEnd;
978 74 : dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
979 74 : dctx->base = dst;
980 74 : dctx->previousDstEnd = dst;
981 : }
982 74 : }
983 :
984 :
985 2046 : static size_t ZSTD_decompressBlock_internal(ZSTD_DCtx* dctx,
986 : void* dst, size_t dstCapacity,
987 : const void* src, size_t srcSize)
988 : { /* blockType == blockCompressed */
989 2046 : const BYTE* ip = (const BYTE*)src;
990 :
991 2046 : if (srcSize >= ZSTD_BLOCKSIZE_ABSOLUTEMAX) return ERROR(srcSize_wrong);
992 :
993 : /* Decode literals sub-block */
994 2046 : { size_t const litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize);
995 2046 : if (ZSTD_isError(litCSize)) return litCSize;
996 2046 : ip += litCSize;
997 2046 : srcSize -= litCSize;
998 : }
999 2046 : return ZSTD_decompressSequences(dctx, dst, dstCapacity, ip, srcSize);
1000 : }
1001 :
1002 :
1003 0 : size_t ZSTD_decompressBlock(ZSTD_DCtx* dctx,
1004 : void* dst, size_t dstCapacity,
1005 : const void* src, size_t srcSize)
1006 : {
1007 : size_t dSize;
1008 0 : ZSTD_checkContinuity(dctx, dst);
1009 0 : dSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
1010 0 : dctx->previousDstEnd = (char*)dst + dSize;
1011 0 : return dSize;
1012 : }
1013 :
1014 :
1015 : /** ZSTD_insertBlock() :
1016 : insert `src` block into `dctx` history. Useful to track uncompressed blocks. */
1017 0 : ZSTDLIB_API size_t ZSTD_insertBlock(ZSTD_DCtx* dctx, const void* blockStart, size_t blockSize)
1018 : {
1019 0 : ZSTD_checkContinuity(dctx, blockStart);
1020 0 : dctx->previousDstEnd = (const char*)blockStart + blockSize;
1021 0 : return blockSize;
1022 : }
1023 :
1024 :
1025 0 : size_t ZSTD_generateNxBytes(void* dst, size_t dstCapacity, BYTE byte, size_t length)
1026 : {
1027 0 : if (length > dstCapacity) return ERROR(dstSize_tooSmall);
1028 0 : memset(dst, byte, length);
1029 0 : return length;
1030 : }
1031 :
1032 :
1033 : /*! ZSTD_decompressFrame() :
1034 : * `dctx` must be properly initialized */
1035 74 : static size_t ZSTD_decompressFrame(ZSTD_DCtx* dctx,
1036 : void* dst, size_t dstCapacity,
1037 : const void* src, size_t srcSize)
1038 : {
1039 74 : const BYTE* ip = (const BYTE*)src;
1040 74 : BYTE* const ostart = (BYTE* const)dst;
1041 74 : BYTE* const oend = ostart + dstCapacity;
1042 74 : BYTE* op = ostart;
1043 74 : size_t remainingSize = srcSize;
1044 :
1045 : /* check */
1046 74 : if (srcSize < ZSTD_frameHeaderSize_min+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
1047 :
1048 : /* Frame Header */
1049 74 : { size_t const frameHeaderSize = ZSTD_frameHeaderSize(src, ZSTD_frameHeaderSize_prefix);
1050 74 : if (ZSTD_isError(frameHeaderSize)) return frameHeaderSize;
1051 74 : if (srcSize < frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
1052 74 : CHECK_F(ZSTD_decodeFrameHeader(dctx, src, frameHeaderSize));
1053 74 : ip += frameHeaderSize; remainingSize -= frameHeaderSize;
1054 : }
1055 :
1056 : /* Loop on each block */
1057 3252 : while (1) {
1058 : size_t decodedSize;
1059 : blockProperties_t blockProperties;
1060 3326 : size_t const cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
1061 3326 : if (ZSTD_isError(cBlockSize)) return cBlockSize;
1062 :
1063 3326 : ip += ZSTD_blockHeaderSize;
1064 3326 : remainingSize -= ZSTD_blockHeaderSize;
1065 3326 : if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
1066 :
1067 3326 : switch(blockProperties.blockType)
1068 : {
1069 : case bt_compressed:
1070 2046 : decodedSize = ZSTD_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize);
1071 2046 : break;
1072 : case bt_raw :
1073 1280 : decodedSize = ZSTD_copyRawBlock(op, oend-op, ip, cBlockSize);
1074 1280 : break;
1075 : case bt_rle :
1076 0 : decodedSize = ZSTD_generateNxBytes(op, oend-op, *ip, blockProperties.origSize);
1077 0 : break;
1078 : case bt_reserved :
1079 : default:
1080 0 : return ERROR(corruption_detected);
1081 : }
1082 :
1083 3326 : if (ZSTD_isError(decodedSize)) return decodedSize;
1084 3326 : if (dctx->fParams.checksumFlag) XXH64_update(&dctx->xxhState, op, decodedSize);
1085 3326 : op += decodedSize;
1086 3326 : ip += cBlockSize;
1087 3326 : remainingSize -= cBlockSize;
1088 3326 : if (blockProperties.lastBlock) break;
1089 : }
1090 :
1091 74 : if (dctx->fParams.checksumFlag) { /* Frame content checksum verification */
1092 0 : U32 const checkCalc = (U32)XXH64_digest(&dctx->xxhState);
1093 : U32 checkRead;
1094 0 : if (remainingSize<4) return ERROR(checksum_wrong);
1095 0 : checkRead = MEM_readLE32(ip);
1096 0 : if (checkRead != checkCalc) return ERROR(checksum_wrong);
1097 0 : remainingSize -= 4;
1098 : }
1099 :
1100 74 : if (remainingSize) return ERROR(srcSize_wrong);
1101 74 : return op-ostart;
1102 : }
1103 :
1104 :
1105 74 : size_t ZSTD_decompress_usingDict(ZSTD_DCtx* dctx,
1106 : void* dst, size_t dstCapacity,
1107 : const void* src, size_t srcSize,
1108 : const void* dict, size_t dictSize)
1109 : {
1110 : #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT==1)
1111 : if (ZSTD_isLegacy(src, srcSize)) return ZSTD_decompressLegacy(dst, dstCapacity, src, srcSize, dict, dictSize);
1112 : #endif
1113 74 : ZSTD_decompressBegin_usingDict(dctx, dict, dictSize);
1114 74 : ZSTD_checkContinuity(dctx, dst);
1115 74 : return ZSTD_decompressFrame(dctx, dst, dstCapacity, src, srcSize);
1116 : }
1117 :
1118 :
1119 74 : size_t ZSTD_decompressDCtx(ZSTD_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
1120 : {
1121 74 : return ZSTD_decompress_usingDict(dctx, dst, dstCapacity, src, srcSize, NULL, 0);
1122 : }
1123 :
1124 :
1125 74 : size_t ZSTD_decompress(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
1126 : {
1127 : #if defined(ZSTD_HEAPMODE) && (ZSTD_HEAPMODE==1)
1128 : size_t regenSize;
1129 74 : ZSTD_DCtx* const dctx = ZSTD_createDCtx();
1130 74 : if (dctx==NULL) return ERROR(memory_allocation);
1131 74 : regenSize = ZSTD_decompressDCtx(dctx, dst, dstCapacity, src, srcSize);
1132 74 : ZSTD_freeDCtx(dctx);
1133 74 : return regenSize;
1134 : #else /* stack mode */
1135 : ZSTD_DCtx dctx;
1136 : return ZSTD_decompressDCtx(&dctx, dst, dstCapacity, src, srcSize);
1137 : #endif
1138 : }
1139 :
1140 :
1141 : /*-**************************************
1142 : * Advanced Streaming Decompression API
1143 : * Bufferless and synchronous
1144 : ****************************************/
1145 0 : size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx) { return dctx->expected; }
1146 :
1147 0 : ZSTD_nextInputType_e ZSTD_nextInputType(ZSTD_DCtx* dctx) {
1148 0 : switch(dctx->stage)
1149 : {
1150 : default: /* should not happen */
1151 : case ZSTDds_getFrameHeaderSize:
1152 : case ZSTDds_decodeFrameHeader:
1153 0 : return ZSTDnit_frameHeader;
1154 : case ZSTDds_decodeBlockHeader:
1155 0 : return ZSTDnit_blockHeader;
1156 : case ZSTDds_decompressBlock:
1157 0 : return ZSTDnit_block;
1158 : case ZSTDds_decompressLastBlock:
1159 0 : return ZSTDnit_lastBlock;
1160 : case ZSTDds_checkChecksum:
1161 0 : return ZSTDnit_checksum;
1162 : case ZSTDds_decodeSkippableHeader:
1163 : case ZSTDds_skipFrame:
1164 0 : return ZSTDnit_skippableFrame;
1165 : }
1166 : }
1167 :
1168 0 : int ZSTD_isSkipFrame(ZSTD_DCtx* dctx) { return dctx->stage == ZSTDds_skipFrame; } /* for zbuff */
1169 :
1170 : /** ZSTD_decompressContinue() :
1171 : * @return : nb of bytes generated into `dst` (necessarily <= `dstCapacity)
1172 : * or an error code, which can be tested using ZSTD_isError() */
1173 0 : size_t ZSTD_decompressContinue(ZSTD_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
1174 : {
1175 : /* Sanity check */
1176 0 : if (srcSize != dctx->expected) return ERROR(srcSize_wrong);
1177 0 : if (dstCapacity) ZSTD_checkContinuity(dctx, dst);
1178 :
1179 0 : switch (dctx->stage)
1180 : {
1181 : case ZSTDds_getFrameHeaderSize :
1182 0 : if (srcSize != ZSTD_frameHeaderSize_prefix) return ERROR(srcSize_wrong); /* impossible */
1183 0 : if ((MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) { /* skippable frame */
1184 0 : memcpy(dctx->headerBuffer, src, ZSTD_frameHeaderSize_prefix);
1185 0 : dctx->expected = ZSTD_skippableHeaderSize - ZSTD_frameHeaderSize_prefix; /* magic number + skippable frame length */
1186 0 : dctx->stage = ZSTDds_decodeSkippableHeader;
1187 0 : return 0;
1188 : }
1189 0 : dctx->headerSize = ZSTD_frameHeaderSize(src, ZSTD_frameHeaderSize_prefix);
1190 0 : if (ZSTD_isError(dctx->headerSize)) return dctx->headerSize;
1191 0 : memcpy(dctx->headerBuffer, src, ZSTD_frameHeaderSize_prefix);
1192 0 : if (dctx->headerSize > ZSTD_frameHeaderSize_prefix) {
1193 0 : dctx->expected = dctx->headerSize - ZSTD_frameHeaderSize_prefix;
1194 0 : dctx->stage = ZSTDds_decodeFrameHeader;
1195 0 : return 0;
1196 : }
1197 0 : dctx->expected = 0; /* not necessary to copy more */
1198 :
1199 : case ZSTDds_decodeFrameHeader:
1200 0 : memcpy(dctx->headerBuffer + ZSTD_frameHeaderSize_prefix, src, dctx->expected);
1201 0 : CHECK_F(ZSTD_decodeFrameHeader(dctx, dctx->headerBuffer, dctx->headerSize));
1202 0 : dctx->expected = ZSTD_blockHeaderSize;
1203 0 : dctx->stage = ZSTDds_decodeBlockHeader;
1204 0 : return 0;
1205 :
1206 : case ZSTDds_decodeBlockHeader:
1207 : { blockProperties_t bp;
1208 0 : size_t const cBlockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
1209 0 : if (ZSTD_isError(cBlockSize)) return cBlockSize;
1210 0 : dctx->expected = cBlockSize;
1211 0 : dctx->bType = bp.blockType;
1212 0 : dctx->rleSize = bp.origSize;
1213 0 : if (cBlockSize) {
1214 0 : dctx->stage = bp.lastBlock ? ZSTDds_decompressLastBlock : ZSTDds_decompressBlock;
1215 0 : return 0;
1216 : }
1217 : /* empty block */
1218 0 : if (bp.lastBlock) {
1219 0 : if (dctx->fParams.checksumFlag) {
1220 0 : dctx->expected = 4;
1221 0 : dctx->stage = ZSTDds_checkChecksum;
1222 : } else {
1223 0 : dctx->expected = 0; /* end of frame */
1224 0 : dctx->stage = ZSTDds_getFrameHeaderSize;
1225 : }
1226 : } else {
1227 0 : dctx->expected = 3; /* go directly to next header */
1228 0 : dctx->stage = ZSTDds_decodeBlockHeader;
1229 : }
1230 0 : return 0;
1231 : }
1232 : case ZSTDds_decompressLastBlock:
1233 : case ZSTDds_decompressBlock:
1234 : { size_t rSize;
1235 0 : switch(dctx->bType)
1236 : {
1237 : case bt_compressed:
1238 0 : rSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
1239 0 : break;
1240 : case bt_raw :
1241 0 : rSize = ZSTD_copyRawBlock(dst, dstCapacity, src, srcSize);
1242 0 : break;
1243 : case bt_rle :
1244 0 : rSize = ZSTD_setRleBlock(dst, dstCapacity, src, srcSize, dctx->rleSize);
1245 0 : break;
1246 : case bt_reserved : /* should never happen */
1247 : default:
1248 0 : return ERROR(corruption_detected);
1249 : }
1250 0 : if (ZSTD_isError(rSize)) return rSize;
1251 0 : if (dctx->fParams.checksumFlag) XXH64_update(&dctx->xxhState, dst, rSize);
1252 :
1253 0 : if (dctx->stage == ZSTDds_decompressLastBlock) { /* end of frame */
1254 0 : if (dctx->fParams.checksumFlag) { /* another round for frame checksum */
1255 0 : dctx->expected = 4;
1256 0 : dctx->stage = ZSTDds_checkChecksum;
1257 : } else {
1258 0 : dctx->expected = 0; /* ends here */
1259 0 : dctx->stage = ZSTDds_getFrameHeaderSize;
1260 : }
1261 : } else {
1262 0 : dctx->stage = ZSTDds_decodeBlockHeader;
1263 0 : dctx->expected = ZSTD_blockHeaderSize;
1264 0 : dctx->previousDstEnd = (char*)dst + rSize;
1265 : }
1266 0 : return rSize;
1267 : }
1268 : case ZSTDds_checkChecksum:
1269 0 : { U32 const h32 = (U32)XXH64_digest(&dctx->xxhState);
1270 0 : U32 const check32 = MEM_readLE32(src); /* srcSize == 4, guaranteed by dctx->expected */
1271 0 : if (check32 != h32) return ERROR(checksum_wrong);
1272 0 : dctx->expected = 0;
1273 0 : dctx->stage = ZSTDds_getFrameHeaderSize;
1274 0 : return 0;
1275 : }
1276 : case ZSTDds_decodeSkippableHeader:
1277 0 : { memcpy(dctx->headerBuffer + ZSTD_frameHeaderSize_prefix, src, dctx->expected);
1278 0 : dctx->expected = MEM_readLE32(dctx->headerBuffer + 4);
1279 0 : dctx->stage = ZSTDds_skipFrame;
1280 0 : return 0;
1281 : }
1282 : case ZSTDds_skipFrame:
1283 0 : { dctx->expected = 0;
1284 0 : dctx->stage = ZSTDds_getFrameHeaderSize;
1285 0 : return 0;
1286 : }
1287 : default:
1288 0 : return ERROR(GENERIC); /* impossible */
1289 : }
1290 : }
1291 :
1292 :
1293 0 : static size_t ZSTD_refDictContent(ZSTD_DCtx* dctx, const void* dict, size_t dictSize)
1294 : {
1295 0 : dctx->dictEnd = dctx->previousDstEnd;
1296 0 : dctx->vBase = (const char*)dict - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
1297 0 : dctx->base = dict;
1298 0 : dctx->previousDstEnd = (const char*)dict + dictSize;
1299 0 : return 0;
1300 : }
1301 :
1302 0 : static size_t ZSTD_loadEntropy(ZSTD_DCtx* dctx, const void* const dict, size_t const dictSize)
1303 : {
1304 0 : const BYTE* dictPtr = (const BYTE*)dict;
1305 0 : const BYTE* const dictEnd = dictPtr + dictSize;
1306 :
1307 0 : { size_t const hSize = HUF_readDTableX4(dctx->hufTable, dict, dictSize);
1308 0 : if (HUF_isError(hSize)) return ERROR(dictionary_corrupted);
1309 0 : dictPtr += hSize;
1310 : }
1311 :
1312 : { short offcodeNCount[MaxOff+1];
1313 0 : U32 offcodeMaxValue=MaxOff, offcodeLog=OffFSELog;
1314 0 : size_t const offcodeHeaderSize = FSE_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dictPtr, dictEnd-dictPtr);
1315 0 : if (FSE_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted);
1316 0 : CHECK_E(FSE_buildDTable(dctx->OFTable, offcodeNCount, offcodeMaxValue, offcodeLog), dictionary_corrupted);
1317 0 : dictPtr += offcodeHeaderSize;
1318 : }
1319 :
1320 : { short matchlengthNCount[MaxML+1];
1321 0 : unsigned matchlengthMaxValue = MaxML, matchlengthLog = MLFSELog;
1322 0 : size_t const matchlengthHeaderSize = FSE_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd-dictPtr);
1323 0 : if (FSE_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted);
1324 0 : CHECK_E(FSE_buildDTable(dctx->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog), dictionary_corrupted);
1325 0 : dictPtr += matchlengthHeaderSize;
1326 : }
1327 :
1328 : { short litlengthNCount[MaxLL+1];
1329 0 : unsigned litlengthMaxValue = MaxLL, litlengthLog = LLFSELog;
1330 0 : size_t const litlengthHeaderSize = FSE_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd-dictPtr);
1331 0 : if (FSE_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted);
1332 0 : CHECK_E(FSE_buildDTable(dctx->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog), dictionary_corrupted);
1333 0 : dictPtr += litlengthHeaderSize;
1334 : }
1335 :
1336 0 : if (dictPtr+12 > dictEnd) return ERROR(dictionary_corrupted);
1337 0 : dctx->rep[0] = MEM_readLE32(dictPtr+0); if (dctx->rep[0] >= dictSize) return ERROR(dictionary_corrupted);
1338 0 : dctx->rep[1] = MEM_readLE32(dictPtr+4); if (dctx->rep[1] >= dictSize) return ERROR(dictionary_corrupted);
1339 0 : dctx->rep[2] = MEM_readLE32(dictPtr+8); if (dctx->rep[2] >= dictSize) return ERROR(dictionary_corrupted);
1340 0 : dictPtr += 12;
1341 :
1342 0 : dctx->litEntropy = dctx->fseEntropy = 1;
1343 0 : return dictPtr - (const BYTE*)dict;
1344 : }
1345 :
1346 0 : static size_t ZSTD_decompress_insertDictionary(ZSTD_DCtx* dctx, const void* dict, size_t dictSize)
1347 : {
1348 0 : if (dictSize < 8) return ZSTD_refDictContent(dctx, dict, dictSize);
1349 0 : { U32 const magic = MEM_readLE32(dict);
1350 0 : if (magic != ZSTD_DICT_MAGIC) {
1351 0 : return ZSTD_refDictContent(dctx, dict, dictSize); /* pure content mode */
1352 : } }
1353 0 : dctx->dictID = MEM_readLE32((const char*)dict + 4);
1354 :
1355 : /* load entropy tables */
1356 0 : dict = (const char*)dict + 8;
1357 0 : dictSize -= 8;
1358 0 : { size_t const eSize = ZSTD_loadEntropy(dctx, dict, dictSize);
1359 0 : if (ZSTD_isError(eSize)) return ERROR(dictionary_corrupted);
1360 0 : dict = (const char*)dict + eSize;
1361 0 : dictSize -= eSize;
1362 : }
1363 :
1364 : /* reference dictionary content */
1365 0 : return ZSTD_refDictContent(dctx, dict, dictSize);
1366 : }
1367 :
1368 74 : size_t ZSTD_decompressBegin_usingDict(ZSTD_DCtx* dctx, const void* dict, size_t dictSize)
1369 : {
1370 74 : CHECK_F(ZSTD_decompressBegin(dctx));
1371 74 : if (dict && dictSize) CHECK_E(ZSTD_decompress_insertDictionary(dctx, dict, dictSize), dictionary_corrupted);
1372 74 : return 0;
1373 : }
1374 :
1375 :
1376 : /* ====== ZSTD_DDict ====== */
1377 :
1378 : struct ZSTD_DDict_s {
1379 : void* dict;
1380 : size_t dictSize;
1381 : ZSTD_DCtx* refContext;
1382 : }; /* typedef'd to ZSTD_DDict within "zstd.h" */
1383 :
1384 0 : ZSTD_DDict* ZSTD_createDDict_advanced(const void* dict, size_t dictSize, ZSTD_customMem customMem)
1385 : {
1386 0 : if (!customMem.customAlloc && !customMem.customFree) customMem = defaultCustomMem;
1387 0 : if (!customMem.customAlloc || !customMem.customFree) return NULL;
1388 :
1389 0 : { ZSTD_DDict* const ddict = (ZSTD_DDict*) ZSTD_malloc(sizeof(ZSTD_DDict), customMem);
1390 0 : void* const dictContent = ZSTD_malloc(dictSize, customMem);
1391 0 : ZSTD_DCtx* const dctx = ZSTD_createDCtx_advanced(customMem);
1392 :
1393 0 : if (!dictContent || !ddict || !dctx) {
1394 0 : ZSTD_free(dictContent, customMem);
1395 0 : ZSTD_free(ddict, customMem);
1396 0 : ZSTD_free(dctx, customMem);
1397 0 : return NULL;
1398 : }
1399 :
1400 0 : memcpy(dictContent, dict, dictSize);
1401 0 : { size_t const errorCode = ZSTD_decompressBegin_usingDict(dctx, dictContent, dictSize);
1402 0 : if (ZSTD_isError(errorCode)) {
1403 0 : ZSTD_free(dictContent, customMem);
1404 0 : ZSTD_free(ddict, customMem);
1405 0 : ZSTD_free(dctx, customMem);
1406 0 : return NULL;
1407 : } }
1408 :
1409 0 : ddict->dict = dictContent;
1410 0 : ddict->dictSize = dictSize;
1411 0 : ddict->refContext = dctx;
1412 0 : return ddict;
1413 : }
1414 : }
1415 :
1416 : /*! ZSTD_createDDict() :
1417 : * Create a digested dictionary, ready to start decompression without startup delay.
1418 : * `dict` can be released after `ZSTD_DDict` creation */
1419 0 : ZSTD_DDict* ZSTD_createDDict(const void* dict, size_t dictSize)
1420 : {
1421 0 : ZSTD_customMem const allocator = { NULL, NULL, NULL };
1422 0 : return ZSTD_createDDict_advanced(dict, dictSize, allocator);
1423 : }
1424 :
1425 0 : size_t ZSTD_freeDDict(ZSTD_DDict* ddict)
1426 : {
1427 0 : if (ddict==NULL) return 0; /* support free on NULL */
1428 0 : { ZSTD_customMem const cMem = ddict->refContext->customMem;
1429 0 : ZSTD_freeDCtx(ddict->refContext);
1430 0 : ZSTD_free(ddict->dict, cMem);
1431 0 : ZSTD_free(ddict, cMem);
1432 0 : return 0;
1433 : }
1434 : }
1435 :
1436 0 : size_t ZSTD_sizeof_DDict(const ZSTD_DDict* ddict)
1437 : {
1438 0 : if (ddict==NULL) return 0; /* support sizeof on NULL */
1439 0 : return sizeof(*ddict) + sizeof(ddict->refContext) + ddict->dictSize;
1440 : }
1441 :
1442 :
1443 : /*! ZSTD_decompress_usingDDict() :
1444 : * Decompression using a pre-digested Dictionary
1445 : * Use dictionary without significant overhead. */
1446 0 : size_t ZSTD_decompress_usingDDict(ZSTD_DCtx* dctx,
1447 : void* dst, size_t dstCapacity,
1448 : const void* src, size_t srcSize,
1449 : const ZSTD_DDict* ddict)
1450 : {
1451 : #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT==1)
1452 : if (ZSTD_isLegacy(src, srcSize)) return ZSTD_decompressLegacy(dst, dstCapacity, src, srcSize, ddict->dict, ddict->dictSize);
1453 : #endif
1454 0 : ZSTD_refDCtx(dctx, ddict->refContext);
1455 0 : ZSTD_checkContinuity(dctx, dst);
1456 0 : return ZSTD_decompressFrame(dctx, dst, dstCapacity, src, srcSize);
1457 : }
1458 :
1459 :
1460 : /*=====================================
1461 : * Streaming decompression
1462 : *====================================*/
1463 :
1464 : typedef enum { zdss_init, zdss_loadHeader,
1465 : zdss_read, zdss_load, zdss_flush } ZSTD_dStreamStage;
1466 :
1467 : /* *** Resource management *** */
1468 : struct ZSTD_DStream_s {
1469 : ZSTD_DCtx* dctx;
1470 : ZSTD_DDict* ddict;
1471 : ZSTD_frameParams fParams;
1472 : ZSTD_dStreamStage stage;
1473 : char* inBuff;
1474 : size_t inBuffSize;
1475 : size_t inPos;
1476 : size_t maxWindowSize;
1477 : char* outBuff;
1478 : size_t outBuffSize;
1479 : size_t outStart;
1480 : size_t outEnd;
1481 : size_t blockSize;
1482 : BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX]; /* tmp buffer to store frame header */
1483 : size_t lhSize;
1484 : ZSTD_customMem customMem;
1485 : void* legacyContext;
1486 : U32 previousLegacyVersion;
1487 : U32 legacyVersion;
1488 : U32 hostageByte;
1489 : }; /* typedef'd to ZSTD_DStream within "zstd.h" */
1490 :
1491 :
1492 0 : ZSTD_DStream* ZSTD_createDStream(void)
1493 : {
1494 0 : return ZSTD_createDStream_advanced(defaultCustomMem);
1495 : }
1496 :
1497 0 : ZSTD_DStream* ZSTD_createDStream_advanced(ZSTD_customMem customMem)
1498 : {
1499 : ZSTD_DStream* zds;
1500 :
1501 0 : if (!customMem.customAlloc && !customMem.customFree) customMem = defaultCustomMem;
1502 0 : if (!customMem.customAlloc || !customMem.customFree) return NULL;
1503 :
1504 0 : zds = (ZSTD_DStream*) ZSTD_malloc(sizeof(ZSTD_DStream), customMem);
1505 0 : if (zds==NULL) return NULL;
1506 0 : memset(zds, 0, sizeof(ZSTD_DStream));
1507 0 : memcpy(&zds->customMem, &customMem, sizeof(ZSTD_customMem));
1508 0 : zds->dctx = ZSTD_createDCtx_advanced(customMem);
1509 0 : if (zds->dctx == NULL) { ZSTD_freeDStream(zds); return NULL; }
1510 0 : zds->stage = zdss_init;
1511 0 : zds->maxWindowSize = ZSTD_MAXWINDOWSIZE_DEFAULT;
1512 0 : return zds;
1513 : }
1514 :
1515 0 : size_t ZSTD_freeDStream(ZSTD_DStream* zds)
1516 : {
1517 0 : if (zds==NULL) return 0; /* support free on null */
1518 0 : { ZSTD_customMem const cMem = zds->customMem;
1519 0 : ZSTD_freeDCtx(zds->dctx);
1520 0 : ZSTD_freeDDict(zds->ddict);
1521 0 : ZSTD_free(zds->inBuff, cMem);
1522 0 : ZSTD_free(zds->outBuff, cMem);
1523 : #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT >= 1)
1524 : if (zds->legacyContext)
1525 : ZSTD_freeLegacyStreamContext(zds->legacyContext, zds->previousLegacyVersion);
1526 : #endif
1527 0 : ZSTD_free(zds, cMem);
1528 0 : return 0;
1529 : }
1530 : }
1531 :
1532 :
1533 : /* *** Initialization *** */
1534 :
1535 0 : size_t ZSTD_DStreamInSize(void) { return ZSTD_BLOCKSIZE_ABSOLUTEMAX + ZSTD_blockHeaderSize; }
1536 0 : size_t ZSTD_DStreamOutSize(void) { return ZSTD_BLOCKSIZE_ABSOLUTEMAX; }
1537 :
1538 0 : size_t ZSTD_initDStream_usingDict(ZSTD_DStream* zds, const void* dict, size_t dictSize)
1539 : {
1540 0 : zds->stage = zdss_loadHeader;
1541 0 : zds->lhSize = zds->inPos = zds->outStart = zds->outEnd = 0;
1542 0 : ZSTD_freeDDict(zds->ddict);
1543 0 : zds->ddict = ZSTD_createDDict(dict, dictSize);
1544 0 : if (zds->ddict == NULL) return ERROR(memory_allocation);
1545 0 : zds->legacyVersion = 0;
1546 0 : zds->hostageByte = 0;
1547 0 : return ZSTD_frameHeaderSize_prefix;
1548 : }
1549 :
1550 0 : size_t ZSTD_initDStream(ZSTD_DStream* zds)
1551 : {
1552 0 : return ZSTD_initDStream_usingDict(zds, NULL, 0);
1553 : }
1554 :
1555 0 : size_t ZSTD_resetDStream(ZSTD_DStream* zds)
1556 : {
1557 0 : if (zds->ddict == NULL) return ERROR(stage_wrong); /* must be init at least once */
1558 0 : zds->stage = zdss_loadHeader;
1559 0 : zds->lhSize = zds->inPos = zds->outStart = zds->outEnd = 0;
1560 0 : zds->legacyVersion = 0;
1561 0 : zds->hostageByte = 0;
1562 0 : return ZSTD_frameHeaderSize_prefix;
1563 : }
1564 :
1565 0 : size_t ZSTD_setDStreamParameter(ZSTD_DStream* zds,
1566 : ZSTD_DStreamParameter_e paramType, unsigned paramValue)
1567 : {
1568 0 : switch(paramType)
1569 : {
1570 0 : default : return ERROR(parameter_unknown);
1571 0 : case ZSTDdsp_maxWindowSize : zds->maxWindowSize = paramValue; break;
1572 : }
1573 0 : return 0;
1574 : }
1575 :
1576 :
1577 0 : size_t ZSTD_sizeof_DStream(const ZSTD_DStream* zds)
1578 : {
1579 0 : if (zds==NULL) return 0; /* support sizeof on NULL */
1580 0 : return sizeof(*zds) + ZSTD_sizeof_DCtx(zds->dctx) + ZSTD_sizeof_DDict(zds->ddict) + zds->inBuffSize + zds->outBuffSize;
1581 : }
1582 :
1583 :
1584 : /* ***** Decompression ***** */
1585 :
1586 0 : MEM_STATIC size_t ZSTD_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
1587 : {
1588 0 : size_t const length = MIN(dstCapacity, srcSize);
1589 0 : memcpy(dst, src, length);
1590 0 : return length;
1591 : }
1592 :
1593 :
1594 0 : size_t ZSTD_decompressStream(ZSTD_DStream* zds, ZSTD_outBuffer* output, ZSTD_inBuffer* input)
1595 : {
1596 0 : const char* const istart = (const char*)(input->src) + input->pos;
1597 0 : const char* const iend = (const char*)(input->src) + input->size;
1598 0 : const char* ip = istart;
1599 0 : char* const ostart = (char*)(output->dst) + output->pos;
1600 0 : char* const oend = (char*)(output->dst) + output->size;
1601 0 : char* op = ostart;
1602 0 : U32 someMoreWork = 1;
1603 :
1604 : #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT>=1)
1605 : if (zds->legacyVersion)
1606 : return ZSTD_decompressLegacyStream(zds->legacyContext, zds->legacyVersion, output, input);
1607 : #endif
1608 :
1609 0 : while (someMoreWork) {
1610 0 : switch(zds->stage)
1611 : {
1612 : case zdss_init :
1613 0 : return ERROR(init_missing);
1614 :
1615 : case zdss_loadHeader :
1616 0 : { size_t const hSize = ZSTD_getFrameParams(&zds->fParams, zds->headerBuffer, zds->lhSize);
1617 0 : if (ZSTD_isError(hSize))
1618 : #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT>=1)
1619 : { U32 const legacyVersion = ZSTD_isLegacy(istart, iend-istart);
1620 : if (legacyVersion) {
1621 : CHECK_F(ZSTD_initLegacyStream(&zds->legacyContext, zds->previousLegacyVersion, legacyVersion,
1622 : zds->ddict->dict, zds->ddict->dictSize));
1623 : zds->legacyVersion = zds->previousLegacyVersion = legacyVersion;
1624 : return ZSTD_decompressLegacyStream(zds->legacyContext, zds->legacyVersion, output, input);
1625 : } else {
1626 : return hSize; /* error */
1627 : } }
1628 : #else
1629 0 : return hSize;
1630 : #endif
1631 0 : if (hSize != 0) { /* need more input */
1632 0 : size_t const toLoad = hSize - zds->lhSize; /* if hSize!=0, hSize > zds->lhSize */
1633 0 : if (toLoad > (size_t)(iend-ip)) { /* not enough input to load full header */
1634 0 : memcpy(zds->headerBuffer + zds->lhSize, ip, iend-ip);
1635 0 : zds->lhSize += iend-ip;
1636 0 : input->pos = input->size;
1637 0 : return (MAX(ZSTD_frameHeaderSize_min, hSize) - zds->lhSize) + ZSTD_blockHeaderSize; /* remaining header bytes + next block header */
1638 : }
1639 0 : memcpy(zds->headerBuffer + zds->lhSize, ip, toLoad); zds->lhSize = hSize; ip += toLoad;
1640 0 : break;
1641 : } }
1642 :
1643 : /* Consume header */
1644 0 : ZSTD_refDCtx(zds->dctx, zds->ddict->refContext);
1645 0 : { size_t const h1Size = ZSTD_nextSrcSizeToDecompress(zds->dctx); /* == ZSTD_frameHeaderSize_prefix */
1646 0 : CHECK_F(ZSTD_decompressContinue(zds->dctx, NULL, 0, zds->headerBuffer, h1Size));
1647 0 : { size_t const h2Size = ZSTD_nextSrcSizeToDecompress(zds->dctx);
1648 0 : CHECK_F(ZSTD_decompressContinue(zds->dctx, NULL, 0, zds->headerBuffer+h1Size, h2Size));
1649 : } }
1650 :
1651 0 : zds->fParams.windowSize = MAX(zds->fParams.windowSize, 1U << ZSTD_WINDOWLOG_ABSOLUTEMIN);
1652 0 : if (zds->fParams.windowSize > zds->maxWindowSize) return ERROR(frameParameter_unsupported);
1653 :
1654 : /* Adapt buffer sizes to frame header instructions */
1655 0 : { size_t const blockSize = MIN(zds->fParams.windowSize, ZSTD_BLOCKSIZE_ABSOLUTEMAX);
1656 0 : size_t const neededOutSize = zds->fParams.windowSize + blockSize;
1657 0 : zds->blockSize = blockSize;
1658 0 : if (zds->inBuffSize < blockSize) {
1659 0 : ZSTD_free(zds->inBuff, zds->customMem);
1660 0 : zds->inBuffSize = blockSize;
1661 0 : zds->inBuff = (char*)ZSTD_malloc(blockSize, zds->customMem);
1662 0 : if (zds->inBuff == NULL) return ERROR(memory_allocation);
1663 : }
1664 0 : if (zds->outBuffSize < neededOutSize) {
1665 0 : ZSTD_free(zds->outBuff, zds->customMem);
1666 0 : zds->outBuffSize = neededOutSize;
1667 0 : zds->outBuff = (char*)ZSTD_malloc(neededOutSize, zds->customMem);
1668 0 : if (zds->outBuff == NULL) return ERROR(memory_allocation);
1669 : } }
1670 0 : zds->stage = zdss_read;
1671 : /* pass-through */
1672 :
1673 : case zdss_read:
1674 0 : { size_t const neededInSize = ZSTD_nextSrcSizeToDecompress(zds->dctx);
1675 0 : if (neededInSize==0) { /* end of frame */
1676 0 : zds->stage = zdss_init;
1677 0 : someMoreWork = 0;
1678 0 : break;
1679 : }
1680 0 : if ((size_t)(iend-ip) >= neededInSize) { /* decode directly from src */
1681 0 : const int isSkipFrame = ZSTD_isSkipFrame(zds->dctx);
1682 0 : size_t const decodedSize = ZSTD_decompressContinue(zds->dctx,
1683 0 : zds->outBuff + zds->outStart, (isSkipFrame ? 0 : zds->outBuffSize - zds->outStart),
1684 : ip, neededInSize);
1685 0 : if (ZSTD_isError(decodedSize)) return decodedSize;
1686 0 : ip += neededInSize;
1687 0 : if (!decodedSize && !isSkipFrame) break; /* this was just a header */
1688 0 : zds->outEnd = zds->outStart + decodedSize;
1689 0 : zds->stage = zdss_flush;
1690 0 : break;
1691 : }
1692 0 : if (ip==iend) { someMoreWork = 0; break; } /* no more input */
1693 0 : zds->stage = zdss_load;
1694 : /* pass-through */
1695 : }
1696 :
1697 : case zdss_load:
1698 0 : { size_t const neededInSize = ZSTD_nextSrcSizeToDecompress(zds->dctx);
1699 0 : size_t const toLoad = neededInSize - zds->inPos; /* should always be <= remaining space within inBuff */
1700 : size_t loadedSize;
1701 0 : if (toLoad > zds->inBuffSize - zds->inPos) return ERROR(corruption_detected); /* should never happen */
1702 0 : loadedSize = ZSTD_limitCopy(zds->inBuff + zds->inPos, toLoad, ip, iend-ip);
1703 0 : ip += loadedSize;
1704 0 : zds->inPos += loadedSize;
1705 0 : if (loadedSize < toLoad) { someMoreWork = 0; break; } /* not enough input, wait for more */
1706 :
1707 : /* decode loaded input */
1708 0 : { const int isSkipFrame = ZSTD_isSkipFrame(zds->dctx);
1709 0 : size_t const decodedSize = ZSTD_decompressContinue(zds->dctx,
1710 0 : zds->outBuff + zds->outStart, zds->outBuffSize - zds->outStart,
1711 0 : zds->inBuff, neededInSize);
1712 0 : if (ZSTD_isError(decodedSize)) return decodedSize;
1713 0 : zds->inPos = 0; /* input is consumed */
1714 0 : if (!decodedSize && !isSkipFrame) { zds->stage = zdss_read; break; } /* this was just a header */
1715 0 : zds->outEnd = zds->outStart + decodedSize;
1716 0 : zds->stage = zdss_flush;
1717 : /* pass-through */
1718 : } }
1719 :
1720 : case zdss_flush:
1721 0 : { size_t const toFlushSize = zds->outEnd - zds->outStart;
1722 0 : size_t const flushedSize = ZSTD_limitCopy(op, oend-op, zds->outBuff + zds->outStart, toFlushSize);
1723 0 : op += flushedSize;
1724 0 : zds->outStart += flushedSize;
1725 0 : if (flushedSize == toFlushSize) { /* flush completed */
1726 0 : zds->stage = zdss_read;
1727 0 : if (zds->outStart + zds->blockSize > zds->outBuffSize)
1728 0 : zds->outStart = zds->outEnd = 0;
1729 0 : break;
1730 : }
1731 : /* cannot complete flush */
1732 0 : someMoreWork = 0;
1733 0 : break;
1734 : }
1735 0 : default: return ERROR(GENERIC); /* impossible */
1736 : } }
1737 :
1738 : /* result */
1739 0 : input->pos += (size_t)(ip-istart);
1740 0 : output->pos += (size_t)(op-ostart);
1741 0 : { size_t nextSrcSizeHint = ZSTD_nextSrcSizeToDecompress(zds->dctx);
1742 0 : if (!nextSrcSizeHint) { /* frame fully decoded */
1743 0 : if (zds->outEnd == zds->outStart) { /* output fully flushed */
1744 0 : if (zds->hostageByte) {
1745 0 : if (input->pos >= input->size) { zds->stage = zdss_read; return 1; } /* can't release hostage (not present) */
1746 0 : input->pos++; /* release hostage */
1747 : }
1748 0 : return 0;
1749 : }
1750 0 : if (!zds->hostageByte) { /* output not fully flushed; keep last byte as hostage; will be released when all output is flushed */
1751 0 : input->pos--; /* note : pos > 0, otherwise, impossible to finish reading last block */
1752 0 : zds->hostageByte=1;
1753 : }
1754 0 : return 1;
1755 : }
1756 0 : nextSrcSizeHint += ZSTD_blockHeaderSize * (ZSTD_nextInputType(zds->dctx) == ZSTDnit_block); /* preload header of next block */
1757 0 : if (zds->inPos > nextSrcSizeHint) return ERROR(GENERIC); /* should never happen */
1758 0 : nextSrcSizeHint -= zds->inPos; /* already loaded*/
1759 0 : return nextSrcSizeHint;
1760 : }
1761 : }
|
