]> git.proxmox.com Git - ceph.git/blob - ceph/src/zstd/lib/decompress/zstd_decompress.c
projects / ceph.git / blob
? search:


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