ReactOS  0.4.14-dev-49-gfb4591c
zstd_decompress.c
Go to the documentation of this file.
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 *****************************************************************/
21 #ifndef ZSTD_HEAPMODE
22 # define ZSTD_HEAPMODE 1
23 #endif
24 
29 #ifndef ZSTD_LEGACY_SUPPORT
30 # define ZSTD_LEGACY_SUPPORT 0
31 #endif
32 
39 #ifndef ZSTD_MAXWINDOWSIZE_DEFAULT
40 # define ZSTD_MAXWINDOWSIZE_DEFAULT (((U32)1 << ZSTD_WINDOWLOG_DEFAULTMAX) + 1)
41 #endif
42 
50 #ifndef ZSTD_NO_FORWARD_PROGRESS_MAX
51 # define ZSTD_NO_FORWARD_PROGRESS_MAX 16
52 #endif
53 
54 
55 /*-*******************************************************
56 * Dependencies
57 *********************************************************/
58 #include <string.h> /* memcpy, memmove, memset */
59 #include "compiler.h" /* prefetch */
60 #include "cpu.h" /* bmi2 */
61 #include "mem.h" /* low level memory routines */
62 #define FSE_STATIC_LINKING_ONLY
63 #include "fse.h"
64 #define HUF_STATIC_LINKING_ONLY
65 #include "huf.h"
66 #include "zstd_internal.h"
67 
68 #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT>=1)
69 # include "zstd_legacy.h"
70 #endif
71 
72 static const void* ZSTD_DDictDictContent(const ZSTD_DDict* ddict);
73 static size_t ZSTD_DDictDictSize(const ZSTD_DDict* ddict);
74 
75 
76 /*-*************************************
77 * Errors
78 ***************************************/
79 #define ZSTD_isError ERR_isError /* for inlining */
80 #define FSE_isError ERR_isError
81 #define HUF_isError ERR_isError
82 
83 
84 /*_*******************************************************
85 * Memory operations
86 **********************************************************/
87 static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
88 
89 
90 /*-*************************************************************
91 * Context management
92 ***************************************************************/
97 
98 typedef enum { zdss_init=0, zdss_loadHeader,
100 
101 
102 typedef struct {
106 
107 typedef struct {
113 
114 #define SEQSYMBOL_TABLE_SIZE(log) (1 + (1 << (log)))
115 
116 typedef struct {
117  ZSTD_seqSymbol LLTable[SEQSYMBOL_TABLE_SIZE(LLFSELog)]; /* Note : Space reserved for FSE Tables */
118  ZSTD_seqSymbol OFTable[SEQSYMBOL_TABLE_SIZE(OffFSELog)]; /* is also used as temporary workspace while building hufTable during DDict creation */
119  ZSTD_seqSymbol MLTable[SEQSYMBOL_TABLE_SIZE(MLFSELog)]; /* and therefore must be at least HUF_DECOMPRESS_WORKSPACE_SIZE large */
120  HUF_DTable hufTable[HUF_DTABLE_SIZE(HufLog)]; /* can accommodate HUF_decompress4X */
123 
125 {
129  const HUF_DTable* HUFptr;
131  U32 workspace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32]; /* space needed when building huffman tables */
132  const void* previousDstEnd; /* detect continuity */
133  const void* prefixStart; /* start of current segment */
134  const void* virtualStart; /* virtual start of previous segment if it was just before current one */
135  const void* dictEnd; /* end of previous segment */
136  size_t expected;
137  ZSTD_frameHeader fParams;
139  blockType_e bType; /* used in ZSTD_decompressContinue(), store blockType between block header decoding and block decompression stages */
144  size_t headerSize;
145  ZSTD_format_e format;
146  const BYTE* litPtr;
147  ZSTD_customMem customMem;
148  size_t litSize;
149  size_t rleSize;
150  size_t staticSize;
151  int bmi2; /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */
152 
153  /* dictionary */
155  const ZSTD_DDict* ddict; /* set by ZSTD_initDStream_usingDDict(), or ZSTD_DCtx_refDDict() */
157  int ddictIsCold; /* if == 1 : dictionary is "new" for working context, and presumed "cold" (not in cpu cache) */
158 
159  /* streaming */
161  char* inBuff;
162  size_t inBuffSize;
163  size_t inPos;
165  char* outBuff;
166  size_t outBuffSize;
167  size_t outStart;
168  size_t outEnd;
169  size_t lhSize;
175 
176  /* workspace */
177  BYTE litBuffer[ZSTD_BLOCKSIZE_MAX + WILDCOPY_OVERLENGTH];
178  BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX];
179 }; /* typedef'd to ZSTD_DCtx within "zstd.h" */
180 
181 size_t ZSTD_sizeof_DCtx (const ZSTD_DCtx* dctx)
182 {
183  if (dctx==NULL) return 0; /* support sizeof NULL */
184  return sizeof(*dctx)
186  + dctx->inBuffSize + dctx->outBuffSize;
187 }
188 
189 size_t ZSTD_estimateDCtxSize(void) { return sizeof(ZSTD_DCtx); }
190 
191 
192 static size_t ZSTD_startingInputLength(ZSTD_format_e format)
193 {
194  size_t const startingInputLength = (format==ZSTD_f_zstd1_magicless) ?
195  ZSTD_frameHeaderSize_prefix - ZSTD_FRAMEIDSIZE :
196  ZSTD_frameHeaderSize_prefix;
197  ZSTD_STATIC_ASSERT(ZSTD_FRAMEHEADERSIZE_PREFIX >= ZSTD_FRAMEIDSIZE);
198  /* only supports formats ZSTD_f_zstd1 and ZSTD_f_zstd1_magicless */
199  assert( (format == ZSTD_f_zstd1) || (format == ZSTD_f_zstd1_magicless) );
200  return startingInputLength;
201 }
202 
204 {
205  dctx->format = ZSTD_f_zstd1; /* ZSTD_decompressBegin() invokes ZSTD_startingInputLength() with argument dctx->format */
206  dctx->staticSize = 0;
208  dctx->ddict = NULL;
209  dctx->ddictLocal = NULL;
210  dctx->dictEnd = NULL;
211  dctx->ddictIsCold = 0;
212  dctx->inBuff = NULL;
213  dctx->inBuffSize = 0;
214  dctx->outBuffSize = 0;
215  dctx->streamStage = zdss_init;
216  dctx->legacyContext = NULL;
217  dctx->previousLegacyVersion = 0;
218  dctx->noForwardProgress = 0;
219  dctx->bmi2 = ZSTD_cpuid_bmi2(ZSTD_cpuid());
220 }
221 
222 ZSTD_DCtx* ZSTD_initStaticDCtx(void *workspace, size_t workspaceSize)
223 {
224  ZSTD_DCtx* const dctx = (ZSTD_DCtx*) workspace;
225 
226  if ((size_t)workspace & 7) return NULL; /* 8-aligned */
227  if (workspaceSize < sizeof(ZSTD_DCtx)) return NULL; /* minimum size */
228 
230  dctx->staticSize = workspaceSize;
231  dctx->inBuff = (char*)(dctx+1);
232  return dctx;
233 }
234 
235 ZSTD_DCtx* ZSTD_createDCtx_advanced(ZSTD_customMem customMem)
236 {
237  if (!customMem.customAlloc ^ !customMem.customFree) return NULL;
238 
239  { ZSTD_DCtx* const dctx = (ZSTD_DCtx*)ZSTD_malloc(sizeof(*dctx), customMem);
240  if (!dctx) return NULL;
241  dctx->customMem = customMem;
243  return dctx;
244  }
245 }
246 
248 {
249  DEBUGLOG(3, "ZSTD_createDCtx");
250  return ZSTD_createDCtx_advanced(ZSTD_defaultCMem);
251 }
252 
254 {
255  if (dctx==NULL) return 0; /* support free on NULL */
256  if (dctx->staticSize) return ERROR(memory_allocation); /* not compatible with static DCtx */
257  { ZSTD_customMem const cMem = dctx->customMem;
258  ZSTD_freeDDict(dctx->ddictLocal);
259  dctx->ddictLocal = NULL;
260  ZSTD_free(dctx->inBuff, cMem);
261  dctx->inBuff = NULL;
262 #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT >= 1)
263  if (dctx->legacyContext)
264  ZSTD_freeLegacyStreamContext(dctx->legacyContext, dctx->previousLegacyVersion);
265 #endif
266  ZSTD_free(dctx, cMem);
267  return 0;
268  }
269 }
270 
271 /* no longer useful */
272 void ZSTD_copyDCtx(ZSTD_DCtx* dstDCtx, const ZSTD_DCtx* srcDCtx)
273 {
274  size_t const toCopy = (size_t)((char*)(&dstDCtx->inBuff) - (char*)dstDCtx);
275  memcpy(dstDCtx, srcDCtx, toCopy); /* no need to copy workspace */
276 }
277 
278 
279 /*-*************************************************************
280  * Frame header decoding
281  ***************************************************************/
282 
288 unsigned ZSTD_isFrame(const void* buffer, size_t size)
289 {
290  if (size < ZSTD_FRAMEIDSIZE) return 0;
291  { U32 const magic = MEM_readLE32(buffer);
292  if (magic == ZSTD_MAGICNUMBER) return 1;
293  if ((magic & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) return 1;
294  }
295 #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT >= 1)
296  if (ZSTD_isLegacy(buffer, size)) return 1;
297 #endif
298  return 0;
299 }
300 
306 static size_t ZSTD_frameHeaderSize_internal(const void* src, size_t srcSize, ZSTD_format_e format)
307 {
308  size_t const minInputSize = ZSTD_startingInputLength(format);
309  if (srcSize < minInputSize) return ERROR(srcSize_wrong);
310 
311  { BYTE const fhd = ((const BYTE*)src)[minInputSize-1];
312  U32 const dictID= fhd & 3;
313  U32 const singleSegment = (fhd >> 5) & 1;
314  U32 const fcsId = fhd >> 6;
315  return minInputSize + !singleSegment
316  + ZSTD_did_fieldSize[dictID] + ZSTD_fcs_fieldSize[fcsId]
317  + (singleSegment && !fcsId);
318  }
319 }
320 
325 size_t ZSTD_frameHeaderSize(const void* src, size_t srcSize)
326 {
327  return ZSTD_frameHeaderSize_internal(src, srcSize, ZSTD_f_zstd1);
328 }
329 
330 
337 size_t ZSTD_getFrameHeader_advanced(ZSTD_frameHeader* zfhPtr, const void* src, size_t srcSize, ZSTD_format_e format)
338 {
339  const BYTE* ip = (const BYTE*)src;
340  size_t const minInputSize = ZSTD_startingInputLength(format);
341 
342  memset(zfhPtr, 0, sizeof(*zfhPtr)); /* not strictly necessary, but static analyzer do not understand that zfhPtr is only going to be read only if return value is zero, since they are 2 different signals */
343  if (srcSize < minInputSize) return minInputSize;
344  if (src==NULL) return ERROR(GENERIC); /* invalid parameter */
345 
346  if ( (format != ZSTD_f_zstd1_magicless)
347  && (MEM_readLE32(src) != ZSTD_MAGICNUMBER) ) {
348  if ((MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
349  /* skippable frame */
350  if (srcSize < ZSTD_skippableHeaderSize)
351  return ZSTD_skippableHeaderSize; /* magic number + frame length */
352  memset(zfhPtr, 0, sizeof(*zfhPtr));
353  zfhPtr->frameContentSize = MEM_readLE32((const char *)src + ZSTD_FRAMEIDSIZE);
354  zfhPtr->frameType = ZSTD_skippableFrame;
355  return 0;
356  }
357  return ERROR(prefix_unknown);
358  }
359 
360  /* ensure there is enough `srcSize` to fully read/decode frame header */
361  { size_t const fhsize = ZSTD_frameHeaderSize_internal(src, srcSize, format);
362  if (srcSize < fhsize) return fhsize;
363  zfhPtr->headerSize = (U32)fhsize;
364  }
365 
366  { BYTE const fhdByte = ip[minInputSize-1];
367  size_t pos = minInputSize;
368  U32 const dictIDSizeCode = fhdByte&3;
369  U32 const checksumFlag = (fhdByte>>2)&1;
370  U32 const singleSegment = (fhdByte>>5)&1;
371  U32 const fcsID = fhdByte>>6;
372  U64 windowSize = 0;
373  U32 dictID = 0;
374  U64 frameContentSize = ZSTD_CONTENTSIZE_UNKNOWN;
375  if ((fhdByte & 0x08) != 0)
376  return ERROR(frameParameter_unsupported); /* reserved bits, must be zero */
377 
378  if (!singleSegment) {
379  BYTE const wlByte = ip[pos++];
380  U32 const windowLog = (wlByte >> 3) + ZSTD_WINDOWLOG_ABSOLUTEMIN;
381  if (windowLog > ZSTD_WINDOWLOG_MAX)
382  return ERROR(frameParameter_windowTooLarge);
383  windowSize = (1ULL << windowLog);
384  windowSize += (windowSize >> 3) * (wlByte&7);
385  }
386  switch(dictIDSizeCode)
387  {
388  default: assert(0); /* impossible */
389  case 0 : break;
390  case 1 : dictID = ip[pos]; pos++; break;
391  case 2 : dictID = MEM_readLE16(ip+pos); pos+=2; break;
392  case 3 : dictID = MEM_readLE32(ip+pos); pos+=4; break;
393  }
394  switch(fcsID)
395  {
396  default: assert(0); /* impossible */
397  case 0 : if (singleSegment) frameContentSize = ip[pos]; break;
398  case 1 : frameContentSize = MEM_readLE16(ip+pos)+256; break;
399  case 2 : frameContentSize = MEM_readLE32(ip+pos); break;
400  case 3 : frameContentSize = MEM_readLE64(ip+pos); break;
401  }
402  if (singleSegment) windowSize = frameContentSize;
403 
404  zfhPtr->frameType = ZSTD_frame;
405  zfhPtr->frameContentSize = frameContentSize;
406  zfhPtr->windowSize = windowSize;
407  zfhPtr->blockSizeMax = (unsigned) MIN(windowSize, ZSTD_BLOCKSIZE_MAX);
408  zfhPtr->dictID = dictID;
409  zfhPtr->checksumFlag = checksumFlag;
410  }
411  return 0;
412 }
413 
420 size_t ZSTD_getFrameHeader(ZSTD_frameHeader* zfhPtr, const void* src, size_t srcSize)
421 {
422  return ZSTD_getFrameHeader_advanced(zfhPtr, src, srcSize, ZSTD_f_zstd1);
423 }
424 
425 
431 unsigned long long ZSTD_getFrameContentSize(const void *src, size_t srcSize)
432 {
433 #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT >= 1)
434  if (ZSTD_isLegacy(src, srcSize)) {
435  unsigned long long const ret = ZSTD_getDecompressedSize_legacy(src, srcSize);
436  return ret == 0 ? ZSTD_CONTENTSIZE_UNKNOWN : ret;
437  }
438 #endif
439  { ZSTD_frameHeader zfh;
440  if (ZSTD_getFrameHeader(&zfh, src, srcSize) != 0)
441  return ZSTD_CONTENTSIZE_ERROR;
442  if (zfh.frameType == ZSTD_skippableFrame) {
443  return 0;
444  } else {
445  return zfh.frameContentSize;
446  } }
447 }
448 
454 unsigned long long ZSTD_findDecompressedSize(const void* src, size_t srcSize)
455 {
456  unsigned long long totalDstSize = 0;
457 
458  while (srcSize >= ZSTD_frameHeaderSize_prefix) {
459  U32 const magicNumber = MEM_readLE32(src);
460 
461  if ((magicNumber & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
462  size_t skippableSize;
463  if (srcSize < ZSTD_skippableHeaderSize)
464  return ERROR(srcSize_wrong);
465  skippableSize = MEM_readLE32((const BYTE *)src + ZSTD_FRAMEIDSIZE)
466  + ZSTD_skippableHeaderSize;
467  if (srcSize < skippableSize) {
468  return ZSTD_CONTENTSIZE_ERROR;
469  }
470 
471  src = (const BYTE *)src + skippableSize;
472  srcSize -= skippableSize;
473  continue;
474  }
475 
476  { unsigned long long const ret = ZSTD_getFrameContentSize(src, srcSize);
477  if (ret >= ZSTD_CONTENTSIZE_ERROR) return ret;
478 
479  /* check for overflow */
480  if (totalDstSize + ret < totalDstSize) return ZSTD_CONTENTSIZE_ERROR;
481  totalDstSize += ret;
482  }
483  { size_t const frameSrcSize = ZSTD_findFrameCompressedSize(src, srcSize);
484  if (ZSTD_isError(frameSrcSize)) {
485  return ZSTD_CONTENTSIZE_ERROR;
486  }
487 
488  src = (const BYTE *)src + frameSrcSize;
489  srcSize -= frameSrcSize;
490  }
491  } /* while (srcSize >= ZSTD_frameHeaderSize_prefix) */
492 
493  if (srcSize) return ZSTD_CONTENTSIZE_ERROR;
494 
495  return totalDstSize;
496 }
497 
506 unsigned long long ZSTD_getDecompressedSize(const void* src, size_t srcSize)
507 {
508  unsigned long long const ret = ZSTD_getFrameContentSize(src, srcSize);
510  return (ret >= ZSTD_CONTENTSIZE_ERROR) ? 0 : ret;
511 }
512 
513 
517 static size_t ZSTD_decodeFrameHeader(ZSTD_DCtx* dctx, const void* src, size_t headerSize)
518 {
519  size_t const result = ZSTD_getFrameHeader_advanced(&(dctx->fParams), src, headerSize, dctx->format);
520  if (ZSTD_isError(result)) return result; /* invalid header */
521  if (result>0) return ERROR(srcSize_wrong); /* headerSize too small */
522  if (dctx->fParams.dictID && (dctx->dictID != dctx->fParams.dictID))
523  return ERROR(dictionary_wrong);
524  if (dctx->fParams.checksumFlag) XXH64_reset(&dctx->xxhState, 0);
525  return 0;
526 }
527 
528 
529 /*-*************************************************************
530  * Block decoding
531  ***************************************************************/
532 
535 size_t ZSTD_getcBlockSize(const void* src, size_t srcSize,
536  blockProperties_t* bpPtr)
537 {
538  if (srcSize < ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
539  { U32 const cBlockHeader = MEM_readLE24(src);
540  U32 const cSize = cBlockHeader >> 3;
541  bpPtr->lastBlock = cBlockHeader & 1;
542  bpPtr->blockType = (blockType_e)((cBlockHeader >> 1) & 3);
543  bpPtr->origSize = cSize; /* only useful for RLE */
544  if (bpPtr->blockType == bt_rle) return 1;
545  if (bpPtr->blockType == bt_reserved) return ERROR(corruption_detected);
546  return cSize;
547  }
548 }
549 
550 
551 static size_t ZSTD_copyRawBlock(void* dst, size_t dstCapacity,
552  const void* src, size_t srcSize)
553 {
554  if (dst==NULL) return ERROR(dstSize_tooSmall);
555  if (srcSize > dstCapacity) return ERROR(dstSize_tooSmall);
556  memcpy(dst, src, srcSize);
557  return srcSize;
558 }
559 
560 
561 static size_t ZSTD_setRleBlock(void* dst, size_t dstCapacity,
562  const void* src, size_t srcSize,
563  size_t regenSize)
564 {
565  if (srcSize != 1) return ERROR(srcSize_wrong);
566  if (regenSize > dstCapacity) return ERROR(dstSize_tooSmall);
567  memset(dst, *(const BYTE*)src, regenSize);
568  return regenSize;
569 }
570 
571 /* Hidden declaration for fullbench */
573  const void* src, size_t srcSize);
578  const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */
579 {
580  if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
581 
582  { const BYTE* const istart = (const BYTE*) src;
583  symbolEncodingType_e const litEncType = (symbolEncodingType_e)(istart[0] & 3);
584 
585  switch(litEncType)
586  {
587  case set_repeat:
588  if (dctx->litEntropy==0) return ERROR(dictionary_corrupted);
589  /* fall-through */
590 
591  case set_compressed:
592  if (srcSize < 5) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for case 3 */
593  { size_t lhSize, litSize, litCSize;
594  U32 singleStream=0;
595  U32 const lhlCode = (istart[0] >> 2) & 3;
596  U32 const lhc = MEM_readLE32(istart);
597  switch(lhlCode)
598  {
599  case 0: case 1: default: /* note : default is impossible, since lhlCode into [0..3] */
600  /* 2 - 2 - 10 - 10 */
601  singleStream = !lhlCode;
602  lhSize = 3;
603  litSize = (lhc >> 4) & 0x3FF;
604  litCSize = (lhc >> 14) & 0x3FF;
605  break;
606  case 2:
607  /* 2 - 2 - 14 - 14 */
608  lhSize = 4;
609  litSize = (lhc >> 4) & 0x3FFF;
610  litCSize = lhc >> 18;
611  break;
612  case 3:
613  /* 2 - 2 - 18 - 18 */
614  lhSize = 5;
615  litSize = (lhc >> 4) & 0x3FFFF;
616  litCSize = (lhc >> 22) + (istart[4] << 10);
617  break;
618  }
619  if (litSize > ZSTD_BLOCKSIZE_MAX) return ERROR(corruption_detected);
620  if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
621 
622  /* prefetch huffman table if cold */
623  if (dctx->ddictIsCold && (litSize > 768 /* heuristic */)) {
624  PREFETCH_AREA(dctx->HUFptr, sizeof(dctx->entropy.hufTable));
625  }
626 
627  if (HUF_isError((litEncType==set_repeat) ?
628  ( singleStream ?
629  HUF_decompress1X_usingDTable_bmi2(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->HUFptr, dctx->bmi2) :
630  HUF_decompress4X_usingDTable_bmi2(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->HUFptr, dctx->bmi2) ) :
631  ( singleStream ?
632  HUF_decompress1X1_DCtx_wksp_bmi2(dctx->entropy.hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize,
633  dctx->workspace, sizeof(dctx->workspace), dctx->bmi2) :
634  HUF_decompress4X_hufOnly_wksp_bmi2(dctx->entropy.hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize,
635  dctx->workspace, sizeof(dctx->workspace), dctx->bmi2))))
636  return ERROR(corruption_detected);
637 
638  dctx->litPtr = dctx->litBuffer;
639  dctx->litSize = litSize;
640  dctx->litEntropy = 1;
641  if (litEncType==set_compressed) dctx->HUFptr = dctx->entropy.hufTable;
642  memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
643  return litCSize + lhSize;
644  }
645 
646  case set_basic:
647  { size_t litSize, lhSize;
648  U32 const lhlCode = ((istart[0]) >> 2) & 3;
649  switch(lhlCode)
650  {
651  case 0: case 2: default: /* note : default is impossible, since lhlCode into [0..3] */
652  lhSize = 1;
653  litSize = istart[0] >> 3;
654  break;
655  case 1:
656  lhSize = 2;
657  litSize = MEM_readLE16(istart) >> 4;
658  break;
659  case 3:
660  lhSize = 3;
661  litSize = MEM_readLE24(istart) >> 4;
662  break;
663  }
664 
665  if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */
666  if (litSize+lhSize > srcSize) return ERROR(corruption_detected);
667  memcpy(dctx->litBuffer, istart+lhSize, litSize);
668  dctx->litPtr = dctx->litBuffer;
669  dctx->litSize = litSize;
670  memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
671  return lhSize+litSize;
672  }
673  /* direct reference into compressed stream */
674  dctx->litPtr = istart+lhSize;
675  dctx->litSize = litSize;
676  return lhSize+litSize;
677  }
678 
679  case set_rle:
680  { U32 const lhlCode = ((istart[0]) >> 2) & 3;
681  size_t litSize, lhSize;
682  switch(lhlCode)
683  {
684  case 0: case 2: default: /* note : default is impossible, since lhlCode into [0..3] */
685  lhSize = 1;
686  litSize = istart[0] >> 3;
687  break;
688  case 1:
689  lhSize = 2;
690  litSize = MEM_readLE16(istart) >> 4;
691  break;
692  case 3:
693  lhSize = 3;
694  litSize = MEM_readLE24(istart) >> 4;
695  if (srcSize<4) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
696  break;
697  }
698  if (litSize > ZSTD_BLOCKSIZE_MAX) return ERROR(corruption_detected);
699  memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
700  dctx->litPtr = dctx->litBuffer;
701  dctx->litSize = litSize;
702  return lhSize+1;
703  }
704  default:
705  return ERROR(corruption_detected); /* impossible */
706  }
707  }
708 }
709 
710 /* Default FSE distribution tables.
711  * These are pre-calculated FSE decoding tables using default distributions as defined in specification :
712  * https://github.com/facebook/zstd/blob/master/doc/zstd_compression_format.md#default-distributions
713  * They were generated programmatically with following method :
714  * - start from default distributions, present in /lib/common/zstd_internal.h
715  * - generate tables normally, using ZSTD_buildFSETable()
716  * - printout the content of tables
717  * - pretify output, report below, test with fuzzer to ensure it's correct */
718 
719 /* Default FSE distribution table for Literal Lengths */
721  { 1, 1, 1, LL_DEFAULTNORMLOG}, /* header : fastMode, tableLog */
722  /* nextState, nbAddBits, nbBits, baseVal */
723  { 0, 0, 4, 0}, { 16, 0, 4, 0},
724  { 32, 0, 5, 1}, { 0, 0, 5, 3},
725  { 0, 0, 5, 4}, { 0, 0, 5, 6},
726  { 0, 0, 5, 7}, { 0, 0, 5, 9},
727  { 0, 0, 5, 10}, { 0, 0, 5, 12},
728  { 0, 0, 6, 14}, { 0, 1, 5, 16},
729  { 0, 1, 5, 20}, { 0, 1, 5, 22},
730  { 0, 2, 5, 28}, { 0, 3, 5, 32},
731  { 0, 4, 5, 48}, { 32, 6, 5, 64},
732  { 0, 7, 5, 128}, { 0, 8, 6, 256},
733  { 0, 10, 6, 1024}, { 0, 12, 6, 4096},
734  { 32, 0, 4, 0}, { 0, 0, 4, 1},
735  { 0, 0, 5, 2}, { 32, 0, 5, 4},
736  { 0, 0, 5, 5}, { 32, 0, 5, 7},
737  { 0, 0, 5, 8}, { 32, 0, 5, 10},
738  { 0, 0, 5, 11}, { 0, 0, 6, 13},
739  { 32, 1, 5, 16}, { 0, 1, 5, 18},
740  { 32, 1, 5, 22}, { 0, 2, 5, 24},
741  { 32, 3, 5, 32}, { 0, 3, 5, 40},
742  { 0, 6, 4, 64}, { 16, 6, 4, 64},
743  { 32, 7, 5, 128}, { 0, 9, 6, 512},
744  { 0, 11, 6, 2048}, { 48, 0, 4, 0},
745  { 16, 0, 4, 1}, { 32, 0, 5, 2},
746  { 32, 0, 5, 3}, { 32, 0, 5, 5},
747  { 32, 0, 5, 6}, { 32, 0, 5, 8},
748  { 32, 0, 5, 9}, { 32, 0, 5, 11},
749  { 32, 0, 5, 12}, { 0, 0, 6, 15},
750  { 32, 1, 5, 18}, { 32, 1, 5, 20},
751  { 32, 2, 5, 24}, { 32, 2, 5, 28},
752  { 32, 3, 5, 40}, { 32, 4, 5, 48},
753  { 0, 16, 6,65536}, { 0, 15, 6,32768},
754  { 0, 14, 6,16384}, { 0, 13, 6, 8192},
755 }; /* LL_defaultDTable */
756 
757 /* Default FSE distribution table for Offset Codes */
759  { 1, 1, 1, OF_DEFAULTNORMLOG}, /* header : fastMode, tableLog */
760  /* nextState, nbAddBits, nbBits, baseVal */
761  { 0, 0, 5, 0}, { 0, 6, 4, 61},
762  { 0, 9, 5, 509}, { 0, 15, 5,32765},
763  { 0, 21, 5,2097149}, { 0, 3, 5, 5},
764  { 0, 7, 4, 125}, { 0, 12, 5, 4093},
765  { 0, 18, 5,262141}, { 0, 23, 5,8388605},
766  { 0, 5, 5, 29}, { 0, 8, 4, 253},
767  { 0, 14, 5,16381}, { 0, 20, 5,1048573},
768  { 0, 2, 5, 1}, { 16, 7, 4, 125},
769  { 0, 11, 5, 2045}, { 0, 17, 5,131069},
770  { 0, 22, 5,4194301}, { 0, 4, 5, 13},
771  { 16, 8, 4, 253}, { 0, 13, 5, 8189},
772  { 0, 19, 5,524285}, { 0, 1, 5, 1},
773  { 16, 6, 4, 61}, { 0, 10, 5, 1021},
774  { 0, 16, 5,65533}, { 0, 28, 5,268435453},
775  { 0, 27, 5,134217725}, { 0, 26, 5,67108861},
776  { 0, 25, 5,33554429}, { 0, 24, 5,16777213},
777 }; /* OF_defaultDTable */
778 
779 
780 /* Default FSE distribution table for Match Lengths */
782  { 1, 1, 1, ML_DEFAULTNORMLOG}, /* header : fastMode, tableLog */
783  /* nextState, nbAddBits, nbBits, baseVal */
784  { 0, 0, 6, 3}, { 0, 0, 4, 4},
785  { 32, 0, 5, 5}, { 0, 0, 5, 6},
786  { 0, 0, 5, 8}, { 0, 0, 5, 9},
787  { 0, 0, 5, 11}, { 0, 0, 6, 13},
788  { 0, 0, 6, 16}, { 0, 0, 6, 19},
789  { 0, 0, 6, 22}, { 0, 0, 6, 25},
790  { 0, 0, 6, 28}, { 0, 0, 6, 31},
791  { 0, 0, 6, 34}, { 0, 1, 6, 37},
792  { 0, 1, 6, 41}, { 0, 2, 6, 47},
793  { 0, 3, 6, 59}, { 0, 4, 6, 83},
794  { 0, 7, 6, 131}, { 0, 9, 6, 515},
795  { 16, 0, 4, 4}, { 0, 0, 4, 5},
796  { 32, 0, 5, 6}, { 0, 0, 5, 7},
797  { 32, 0, 5, 9}, { 0, 0, 5, 10},
798  { 0, 0, 6, 12}, { 0, 0, 6, 15},
799  { 0, 0, 6, 18}, { 0, 0, 6, 21},
800  { 0, 0, 6, 24}, { 0, 0, 6, 27},
801  { 0, 0, 6, 30}, { 0, 0, 6, 33},
802  { 0, 1, 6, 35}, { 0, 1, 6, 39},
803  { 0, 2, 6, 43}, { 0, 3, 6, 51},
804  { 0, 4, 6, 67}, { 0, 5, 6, 99},
805  { 0, 8, 6, 259}, { 32, 0, 4, 4},
806  { 48, 0, 4, 4}, { 16, 0, 4, 5},
807  { 32, 0, 5, 7}, { 32, 0, 5, 8},
808  { 32, 0, 5, 10}, { 32, 0, 5, 11},
809  { 0, 0, 6, 14}, { 0, 0, 6, 17},
810  { 0, 0, 6, 20}, { 0, 0, 6, 23},
811  { 0, 0, 6, 26}, { 0, 0, 6, 29},
812  { 0, 0, 6, 32}, { 0, 16, 6,65539},
813  { 0, 15, 6,32771}, { 0, 14, 6,16387},
814  { 0, 13, 6, 8195}, { 0, 12, 6, 4099},
815  { 0, 11, 6, 2051}, { 0, 10, 6, 1027},
816 }; /* ML_defaultDTable */
817 
818 
819 static void ZSTD_buildSeqTable_rle(ZSTD_seqSymbol* dt, U32 baseValue, U32 nbAddBits)
820 {
821  void* ptr = dt;
823  ZSTD_seqSymbol* const cell = dt + 1;
824 
825  DTableH->tableLog = 0;
826  DTableH->fastMode = 0;
827 
828  cell->nbBits = 0;
829  cell->nextState = 0;
830  assert(nbAddBits < 255);
831  cell->nbAdditionalBits = (BYTE)nbAddBits;
832  cell->baseValue = baseValue;
833 }
834 
835 
836 /* ZSTD_buildFSETable() :
837  * generate FSE decoding table for one symbol (ll, ml or off) */
838 static void
840  const short* normalizedCounter, unsigned maxSymbolValue,
841  const U32* baseValue, const U32* nbAdditionalBits,
842  unsigned tableLog)
843 {
844  ZSTD_seqSymbol* const tableDecode = dt+1;
845  U16 symbolNext[MaxSeq+1];
846 
847  U32 const maxSV1 = maxSymbolValue + 1;
848  U32 const tableSize = 1 << tableLog;
849  U32 highThreshold = tableSize-1;
850 
851  /* Sanity Checks */
852  assert(maxSymbolValue <= MaxSeq);
853  assert(tableLog <= MaxFSELog);
854 
855  /* Init, lay down lowprob symbols */
856  { ZSTD_seqSymbol_header DTableH;
857  DTableH.tableLog = tableLog;
858  DTableH.fastMode = 1;
859  { S16 const largeLimit= (S16)(1 << (tableLog-1));
860  U32 s;
861  for (s=0; s<maxSV1; s++) {
862  if (normalizedCounter[s]==-1) {
863  tableDecode[highThreshold--].baseValue = s;
864  symbolNext[s] = 1;
865  } else {
866  if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
867  symbolNext[s] = normalizedCounter[s];
868  } } }
869  memcpy(dt, &DTableH, sizeof(DTableH));
870  }
871 
872  /* Spread symbols */
873  { U32 const tableMask = tableSize-1;
874  U32 const step = FSE_TABLESTEP(tableSize);
875  U32 s, position = 0;
876  for (s=0; s<maxSV1; s++) {
877  int i;
878  for (i=0; i<normalizedCounter[s]; i++) {
879  tableDecode[position].baseValue = s;
880  position = (position + step) & tableMask;
881  while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
882  } }
883  assert(position == 0); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
884  }
885 
886  /* Build Decoding table */
887  { U32 u;
888  for (u=0; u<tableSize; u++) {
889  U32 const symbol = tableDecode[u].baseValue;
890  U32 const nextState = symbolNext[symbol]++;
891  tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32(nextState) );
892  tableDecode[u].nextState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
893  assert(nbAdditionalBits[symbol] < 255);
894  tableDecode[u].nbAdditionalBits = (BYTE)nbAdditionalBits[symbol];
895  tableDecode[u].baseValue = baseValue[symbol];
896  } }
897 }
898 
899 
903 static size_t ZSTD_buildSeqTable(ZSTD_seqSymbol* DTableSpace, const ZSTD_seqSymbol** DTablePtr,
905  const void* src, size_t srcSize,
906  const U32* baseValue, const U32* nbAdditionalBits,
907  const ZSTD_seqSymbol* defaultTable, U32 flagRepeatTable,
908  int ddictIsCold, int nbSeq)
909 {
910  switch(type)
911  {
912  case set_rle :
913  if (!srcSize) return ERROR(srcSize_wrong);
914  if ( (*(const BYTE*)src) > max) return ERROR(corruption_detected);
915  { U32 const symbol = *(const BYTE*)src;
916  U32 const baseline = baseValue[symbol];
917  U32 const nbBits = nbAdditionalBits[symbol];
918  ZSTD_buildSeqTable_rle(DTableSpace, baseline, nbBits);
919  }
920  *DTablePtr = DTableSpace;
921  return 1;
922  case set_basic :
923  *DTablePtr = defaultTable;
924  return 0;
925  case set_repeat:
926  if (!flagRepeatTable) return ERROR(corruption_detected);
927  /* prefetch FSE table if used */
928  if (ddictIsCold && (nbSeq > 24 /* heuristic */)) {
929  const void* const pStart = *DTablePtr;
930  size_t const pSize = sizeof(ZSTD_seqSymbol) * (SEQSYMBOL_TABLE_SIZE(maxLog));
931  PREFETCH_AREA(pStart, pSize);
932  }
933  return 0;
934  case set_compressed :
935  { U32 tableLog;
936  S16 norm[MaxSeq+1];
937  size_t const headerSize = FSE_readNCount(norm, &max, &tableLog, src, srcSize);
938  if (FSE_isError(headerSize)) return ERROR(corruption_detected);
939  if (tableLog > maxLog) return ERROR(corruption_detected);
940  ZSTD_buildFSETable(DTableSpace, norm, max, baseValue, nbAdditionalBits, tableLog);
941  *DTablePtr = DTableSpace;
942  return headerSize;
943  }
944  default : /* impossible */
945  assert(0);
946  return ERROR(GENERIC);
947  }
948 }
949 
950 static const U32 LL_base[MaxLL+1] = {
951  0, 1, 2, 3, 4, 5, 6, 7,
952  8, 9, 10, 11, 12, 13, 14, 15,
953  16, 18, 20, 22, 24, 28, 32, 40,
954  48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
955  0x2000, 0x4000, 0x8000, 0x10000 };
956 
957 static const U32 OF_base[MaxOff+1] = {
958  0, 1, 1, 5, 0xD, 0x1D, 0x3D, 0x7D,
959  0xFD, 0x1FD, 0x3FD, 0x7FD, 0xFFD, 0x1FFD, 0x3FFD, 0x7FFD,
960  0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD,
961  0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD, 0x1FFFFFFD, 0x3FFFFFFD, 0x7FFFFFFD };
962 
963 static const U32 OF_bits[MaxOff+1] = {
964  0, 1, 2, 3, 4, 5, 6, 7,
965  8, 9, 10, 11, 12, 13, 14, 15,
966  16, 17, 18, 19, 20, 21, 22, 23,
967  24, 25, 26, 27, 28, 29, 30, 31 };
968 
969 static const U32 ML_base[MaxML+1] = {
970  3, 4, 5, 6, 7, 8, 9, 10,
971  11, 12, 13, 14, 15, 16, 17, 18,
972  19, 20, 21, 22, 23, 24, 25, 26,
973  27, 28, 29, 30, 31, 32, 33, 34,
974  35, 37, 39, 41, 43, 47, 51, 59,
975  67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803,
976  0x1003, 0x2003, 0x4003, 0x8003, 0x10003 };
977 
978 /* Hidden delcaration for fullbench */
979 size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr,
980  const void* src, size_t srcSize);
981 
982 size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr,
983  const void* src, size_t srcSize)
984 {
985  const BYTE* const istart = (const BYTE* const)src;
986  const BYTE* const iend = istart + srcSize;
987  const BYTE* ip = istart;
988  int nbSeq;
989  DEBUGLOG(5, "ZSTD_decodeSeqHeaders");
990 
991  /* check */
992  if (srcSize < MIN_SEQUENCES_SIZE) return ERROR(srcSize_wrong);
993 
994  /* SeqHead */
995  nbSeq = *ip++;
996  if (!nbSeq) { *nbSeqPtr=0; return 1; }
997  if (nbSeq > 0x7F) {
998  if (nbSeq == 0xFF) {
999  if (ip+2 > iend) return ERROR(srcSize_wrong);
1000  nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2;
1001  } else {
1002  if (ip >= iend) return ERROR(srcSize_wrong);
1003  nbSeq = ((nbSeq-0x80)<<8) + *ip++;
1004  }
1005  }
1006  *nbSeqPtr = nbSeq;
1007 
1008  /* FSE table descriptors */
1009  if (ip+4 > iend) return ERROR(srcSize_wrong); /* minimum possible size */
1010  { symbolEncodingType_e const LLtype = (symbolEncodingType_e)(*ip >> 6);
1011  symbolEncodingType_e const OFtype = (symbolEncodingType_e)((*ip >> 4) & 3);
1012  symbolEncodingType_e const MLtype = (symbolEncodingType_e)((*ip >> 2) & 3);
1013  ip++;
1014 
1015  /* Build DTables */
1016  { size_t const llhSize = ZSTD_buildSeqTable(dctx->entropy.LLTable, &dctx->LLTptr,
1017  LLtype, MaxLL, LLFSELog,
1018  ip, iend-ip,
1019  LL_base, LL_bits,
1021  dctx->ddictIsCold, nbSeq);
1022  if (ZSTD_isError(llhSize)) return ERROR(corruption_detected);
1023  ip += llhSize;
1024  }
1025 
1026  { size_t const ofhSize = ZSTD_buildSeqTable(dctx->entropy.OFTable, &dctx->OFTptr,
1027  OFtype, MaxOff, OffFSELog,
1028  ip, iend-ip,
1029  OF_base, OF_bits,
1031  dctx->ddictIsCold, nbSeq);
1032  if (ZSTD_isError(ofhSize)) return ERROR(corruption_detected);
1033  ip += ofhSize;
1034  }
1035 
1036  { size_t const mlhSize = ZSTD_buildSeqTable(dctx->entropy.MLTable, &dctx->MLTptr,
1037  MLtype, MaxML, MLFSELog,
1038  ip, iend-ip,
1039  ML_base, ML_bits,
1041  dctx->ddictIsCold, nbSeq);
1042  if (ZSTD_isError(mlhSize)) return ERROR(corruption_detected);
1043  ip += mlhSize;
1044  }
1045  }
1046 
1047  /* prefetch dictionary content */
1048  if (dctx->ddictIsCold) {
1049  size_t const dictSize = (const char*)dctx->prefixStart - (const char*)dctx->virtualStart;
1050  size_t const psmin = MIN(dictSize, (size_t)(64*nbSeq) /* heuristic */ );
1051  size_t const pSize = MIN(psmin, 128 KB /* protection */ );
1052  const void* const pStart = (const char*)dctx->dictEnd - pSize;
1053  PREFETCH_AREA(pStart, pSize);
1054  dctx->ddictIsCold = 0;
1055  }
1056 
1057  return ip-istart;
1058 }
1059 
1060 
1061 typedef struct {
1062  size_t litLength;
1063  size_t matchLength;
1064  size_t offset;
1065  const BYTE* match;
1066 } seq_t;
1067 
1068 typedef struct {
1069  size_t state;
1071 } ZSTD_fseState;
1072 
1073 typedef struct {
1078  size_t prevOffset[ZSTD_REP_NUM];
1080  const BYTE* dictEnd;
1081  size_t pos;
1082 } seqState_t;
1083 
1084 
1087  BYTE* const oend, seq_t sequence,
1088  const BYTE** litPtr, const BYTE* const litLimit,
1089  const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
1090 {
1091  BYTE* const oLitEnd = op + sequence.litLength;
1092  size_t const sequenceLength = sequence.litLength + sequence.matchLength;
1093  BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
1094  BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH;
1095  const BYTE* const iLitEnd = *litPtr + sequence.litLength;
1096  const BYTE* match = oLitEnd - sequence.offset;
1097 
1098  /* check */
1099  if (oMatchEnd>oend) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
1100  if (iLitEnd > litLimit) return ERROR(corruption_detected); /* over-read beyond lit buffer */
1101  if (oLitEnd <= oend_w) return ERROR(GENERIC); /* Precondition */
1102 
1103  /* copy literals */
1104  if (op < oend_w) {
1105  ZSTD_wildcopy(op, *litPtr, oend_w - op);
1106  *litPtr += oend_w - op;
1107  op = oend_w;
1108  }
1109  while (op < oLitEnd) *op++ = *(*litPtr)++;
1110 
1111  /* copy Match */
1112  if (sequence.offset > (size_t)(oLitEnd - base)) {
1113  /* offset beyond prefix */
1114  if (sequence.offset > (size_t)(oLitEnd - vBase)) return ERROR(corruption_detected);
1115  match = dictEnd - (base-match);
1116  if (match + sequence.matchLength <= dictEnd) {
1117  memmove(oLitEnd, match, sequence.matchLength);
1118  return sequenceLength;
1119  }
1120  /* span extDict & currentPrefixSegment */
1121  { size_t const length1 = dictEnd - match;
1122  memmove(oLitEnd, match, length1);
1123  op = oLitEnd + length1;
1124  sequence.matchLength -= length1;
1125  match = base;
1126  } }
1127  while (op < oMatchEnd) *op++ = *match++;
1128  return sequenceLength;
1129 }
1130 
1131 
1134  BYTE* const oend, seq_t sequence,
1135  const BYTE** litPtr, const BYTE* const litLimit,
1136  const BYTE* const prefixStart, const BYTE* const virtualStart, const BYTE* const dictEnd)
1137 {
1138  BYTE* const oLitEnd = op + sequence.litLength;
1139  size_t const sequenceLength = sequence.litLength + sequence.matchLength;
1140  BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
1141  BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH;
1142  const BYTE* const iLitEnd = *litPtr + sequence.litLength;
1143  const BYTE* match = oLitEnd - sequence.offset;
1144 
1145  /* check */
1146  if (oMatchEnd>oend) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
1147  if (iLitEnd > litLimit) return ERROR(corruption_detected); /* over-read beyond lit buffer */
1148  if (oLitEnd>oend_w) return ZSTD_execSequenceLast7(op, oend, sequence, litPtr, litLimit, prefixStart, virtualStart, dictEnd);
1149 
1150  /* copy Literals */
1151  ZSTD_copy8(op, *litPtr);
1152  if (sequence.litLength > 8)
1153  ZSTD_wildcopy(op+8, (*litPtr)+8, sequence.litLength - 8); /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
1154  op = oLitEnd;
1155  *litPtr = iLitEnd; /* update for next sequence */
1156 
1157  /* copy Match */
1158  if (sequence.offset > (size_t)(oLitEnd - prefixStart)) {
1159  /* offset beyond prefix -> go into extDict */
1160  if (sequence.offset > (size_t)(oLitEnd - virtualStart))
1161  return ERROR(corruption_detected);
1162  match = dictEnd + (match - prefixStart);
1163  if (match + sequence.matchLength <= dictEnd) {
1164  memmove(oLitEnd, match, sequence.matchLength);
1165  return sequenceLength;
1166  }
1167  /* span extDict & currentPrefixSegment */
1168  { size_t const length1 = dictEnd - match;
1169  memmove(oLitEnd, match, length1);
1170  op = oLitEnd + length1;
1171  sequence.matchLength -= length1;
1172  match = prefixStart;
1173  if (op > oend_w || sequence.matchLength < MINMATCH) {
1174  U32 i;
1175  for (i = 0; i < sequence.matchLength; ++i) op[i] = match[i];
1176  return sequenceLength;
1177  }
1178  } }
1179  /* Requirement: op <= oend_w && sequence.matchLength >= MINMATCH */
1180 
1181  /* match within prefix */
1182  if (sequence.offset < 8) {
1183  /* close range match, overlap */
1184  static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
1185  static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* subtracted */
1186  int const sub2 = dec64table[sequence.offset];
1187  op[0] = match[0];
1188  op[1] = match[1];
1189  op[2] = match[2];
1190  op[3] = match[3];
1191  match += dec32table[sequence.offset];
1192  ZSTD_copy4(op+4, match);
1193  match -= sub2;
1194  } else {
1195  ZSTD_copy8(op, match);
1196  }
1197  op += 8; match += 8;
1198 
1199  if (oMatchEnd > oend-(16-MINMATCH)) {
1200  if (op < oend_w) {
1201  ZSTD_wildcopy(op, match, oend_w - op);
1202  match += oend_w - op;
1203  op = oend_w;
1204  }
1205  while (op < oMatchEnd) *op++ = *match++;
1206  } else {
1207  ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
1208  }
1209  return sequenceLength;
1210 }
1211 
1212 
1215  BYTE* const oend, seq_t sequence,
1216  const BYTE** litPtr, const BYTE* const litLimit,
1217  const BYTE* const prefixStart, const BYTE* const dictStart, const BYTE* const dictEnd)
1218 {
1219  BYTE* const oLitEnd = op + sequence.litLength;
1220  size_t const sequenceLength = sequence.litLength + sequence.matchLength;
1221  BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
1222  BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH;
1223  const BYTE* const iLitEnd = *litPtr + sequence.litLength;
1224  const BYTE* match = sequence.match;
1225 
1226  /* check */
1227  if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
1228  if (iLitEnd > litLimit) return ERROR(corruption_detected); /* over-read beyond lit buffer */
1229  if (oLitEnd > oend_w) return ZSTD_execSequenceLast7(op, oend, sequence, litPtr, litLimit, prefixStart, dictStart, dictEnd);
1230 
1231  /* copy Literals */
1232  ZSTD_copy8(op, *litPtr); /* note : op <= oLitEnd <= oend_w == oend - 8 */
1233  if (sequence.litLength > 8)
1234  ZSTD_wildcopy(op+8, (*litPtr)+8, sequence.litLength - 8); /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
1235  op = oLitEnd;
1236  *litPtr = iLitEnd; /* update for next sequence */
1237 
1238  /* copy Match */
1239  if (sequence.offset > (size_t)(oLitEnd - prefixStart)) {
1240  /* offset beyond prefix */
1241  if (sequence.offset > (size_t)(oLitEnd - dictStart)) return ERROR(corruption_detected);
1242  if (match + sequence.matchLength <= dictEnd) {
1243  memmove(oLitEnd, match, sequence.matchLength);
1244  return sequenceLength;
1245  }
1246  /* span extDict & currentPrefixSegment */
1247  { size_t const length1 = dictEnd - match;
1248  memmove(oLitEnd, match, length1);
1249  op = oLitEnd + length1;
1250  sequence.matchLength -= length1;
1251  match = prefixStart;
1252  if (op > oend_w || sequence.matchLength < MINMATCH) {
1253  U32 i;
1254  for (i = 0; i < sequence.matchLength; ++i) op[i] = match[i];
1255  return sequenceLength;
1256  }
1257  } }
1258  assert(op <= oend_w);
1259  assert(sequence.matchLength >= MINMATCH);
1260 
1261  /* match within prefix */
1262  if (sequence.offset < 8) {
1263  /* close range match, overlap */
1264  static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
1265  static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* subtracted */
1266  int const sub2 = dec64table[sequence.offset];
1267  op[0] = match[0];
1268  op[1] = match[1];
1269  op[2] = match[2];
1270  op[3] = match[3];
1271  match += dec32table[sequence.offset];
1272  ZSTD_copy4(op+4, match);
1273  match -= sub2;
1274  } else {
1275  ZSTD_copy8(op, match);
1276  }
1277  op += 8; match += 8;
1278 
1279  if (oMatchEnd > oend-(16-MINMATCH)) {
1280  if (op < oend_w) {
1281  ZSTD_wildcopy(op, match, oend_w - op);
1282  match += oend_w - op;
1283  op = oend_w;
1284  }
1285  while (op < oMatchEnd) *op++ = *match++;
1286  } else {
1287  ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
1288  }
1289  return sequenceLength;
1290 }
1291 
1292 static void
1294 {
1295  const void* ptr = dt;
1296  const ZSTD_seqSymbol_header* const DTableH = (const ZSTD_seqSymbol_header*)ptr;
1297  DStatePtr->state = BIT_readBits(bitD, DTableH->tableLog);
1298  DEBUGLOG(6, "ZSTD_initFseState : val=%u using %u bits",
1299  (U32)DStatePtr->state, DTableH->tableLog);
1300  BIT_reloadDStream(bitD);
1301  DStatePtr->table = dt + 1;
1302 }
1303 
1306 {
1307  ZSTD_seqSymbol const DInfo = DStatePtr->table[DStatePtr->state];
1308  U32 const nbBits = DInfo.nbBits;
1309  size_t const lowBits = BIT_readBits(bitD, nbBits);
1310  DStatePtr->state = DInfo.nextState + lowBits;
1311 }
1312 
1313 /* We need to add at most (ZSTD_WINDOWLOG_MAX_32 - 1) bits to read the maximum
1314  * offset bits. But we can only read at most (STREAM_ACCUMULATOR_MIN_32 - 1)
1315  * bits before reloading. This value is the maximum number of bytes we read
1316  * after reloading when we are decoding long offets.
1317  */
1318 #define LONG_OFFSETS_MAX_EXTRA_BITS_32 \
1319  (ZSTD_WINDOWLOG_MAX_32 > STREAM_ACCUMULATOR_MIN_32 \
1320  ? ZSTD_WINDOWLOG_MAX_32 - STREAM_ACCUMULATOR_MIN_32 \
1321  : 0)
1322 
1324 
1326 ZSTD_decodeSequence(seqState_t* seqState, const ZSTD_longOffset_e longOffsets)
1327 {
1328  seq_t seq;
1329  U32 const llBits = seqState->stateLL.table[seqState->stateLL.state].nbAdditionalBits;
1330  U32 const mlBits = seqState->stateML.table[seqState->stateML.state].nbAdditionalBits;
1331  U32 const ofBits = seqState->stateOffb.table[seqState->stateOffb.state].nbAdditionalBits;
1332  U32 const totalBits = llBits+mlBits+ofBits;
1333  U32 const llBase = seqState->stateLL.table[seqState->stateLL.state].baseValue;
1334  U32 const mlBase = seqState->stateML.table[seqState->stateML.state].baseValue;
1335  U32 const ofBase = seqState->stateOffb.table[seqState->stateOffb.state].baseValue;
1336 
1337  /* sequence */
1338  { size_t offset;
1339  if (!ofBits)
1340  offset = 0;
1341  else {
1344  assert(ofBits <= MaxOff);
1345  if (MEM_32bits() && longOffsets && (ofBits >= STREAM_ACCUMULATOR_MIN_32)) {
1346  U32 const extraBits = ofBits - MIN(ofBits, 32 - seqState->DStream.bitsConsumed);
1347  offset = ofBase + (BIT_readBitsFast(&seqState->DStream, ofBits - extraBits) << extraBits);
1348  BIT_reloadDStream(&seqState->DStream);
1349  if (extraBits) offset += BIT_readBitsFast(&seqState->DStream, extraBits);
1350  assert(extraBits <= LONG_OFFSETS_MAX_EXTRA_BITS_32); /* to avoid another reload */
1351  } else {
1352  offset = ofBase + BIT_readBitsFast(&seqState->DStream, ofBits/*>0*/); /* <= (ZSTD_WINDOWLOG_MAX-1) bits */
1353  if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream);
1354  }
1355  }
1356 
1357  if (ofBits <= 1) {
1358  offset += (llBase==0);
1359  if (offset) {
1360  size_t temp = (offset==3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
1361  temp += !temp; /* 0 is not valid; input is corrupted; force offset to 1 */
1362  if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1];
1363  seqState->prevOffset[1] = seqState->prevOffset[0];
1364  seqState->prevOffset[0] = offset = temp;
1365  } else { /* offset == 0 */
1366  offset = seqState->prevOffset[0];
1367  }
1368  } else {
1369  seqState->prevOffset[2] = seqState->prevOffset[1];
1370  seqState->prevOffset[1] = seqState->prevOffset[0];
1371  seqState->prevOffset[0] = offset;
1372  }
1373  seq.offset = offset;
1374  }
1375 
1376  seq.matchLength = mlBase
1377  + ((mlBits>0) ? BIT_readBitsFast(&seqState->DStream, mlBits/*>0*/) : 0); /* <= 16 bits */
1379  BIT_reloadDStream(&seqState->DStream);
1381  BIT_reloadDStream(&seqState->DStream);
1382  /* Ensure there are enough bits to read the rest of data in 64-bit mode. */
1384 
1385  seq.litLength = llBase
1386  + ((llBits>0) ? BIT_readBitsFast(&seqState->DStream, llBits/*>0*/) : 0); /* <= 16 bits */
1387  if (MEM_32bits())
1388  BIT_reloadDStream(&seqState->DStream);
1389 
1390  DEBUGLOG(6, "seq: litL=%u, matchL=%u, offset=%u",
1391  (U32)seq.litLength, (U32)seq.matchLength, (U32)seq.offset);
1392 
1393  /* ANS state update */
1394  ZSTD_updateFseState(&seqState->stateLL, &seqState->DStream); /* <= 9 bits */
1395  ZSTD_updateFseState(&seqState->stateML, &seqState->DStream); /* <= 9 bits */
1396  if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */
1397  ZSTD_updateFseState(&seqState->stateOffb, &seqState->DStream); /* <= 8 bits */
1398 
1399  return seq;
1400 }
1401 
1402 FORCE_INLINE_TEMPLATE size_t
1404  void* dst, size_t maxDstSize,
1405  const void* seqStart, size_t seqSize, int nbSeq,
1406  const ZSTD_longOffset_e isLongOffset)
1407 {
1408  const BYTE* ip = (const BYTE*)seqStart;
1409  const BYTE* const iend = ip + seqSize;
1410  BYTE* const ostart = (BYTE* const)dst;
1411  BYTE* const oend = ostart + maxDstSize;
1412  BYTE* op = ostart;
1413  const BYTE* litPtr = dctx->litPtr;
1414  const BYTE* const litEnd = litPtr + dctx->litSize;
1415  const BYTE* const prefixStart = (const BYTE*) (dctx->prefixStart);
1416  const BYTE* const vBase = (const BYTE*) (dctx->virtualStart);
1417  const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
1418  DEBUGLOG(5, "ZSTD_decompressSequences_body");
1419 
1420  /* Regen sequences */
1421  if (nbSeq) {
1422  seqState_t seqState;
1423  dctx->fseEntropy = 1;
1424  { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->entropy.rep[i]; }
1425  CHECK_E(BIT_initDStream(&seqState.DStream, ip, iend-ip), corruption_detected);
1426  ZSTD_initFseState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
1427  ZSTD_initFseState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
1428  ZSTD_initFseState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
1429 
1430  for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && nbSeq ; ) {
1431  nbSeq--;
1432  { seq_t const sequence = ZSTD_decodeSequence(&seqState, isLongOffset);
1433  size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litEnd, prefixStart, vBase, dictEnd);
1434  DEBUGLOG(6, "regenerated sequence size : %u", (U32)oneSeqSize);
1435  if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
1436  op += oneSeqSize;
1437  } }
1438 
1439  /* check if reached exact end */
1440  DEBUGLOG(5, "ZSTD_decompressSequences_body: after decode loop, remaining nbSeq : %i", nbSeq);
1441  if (nbSeq) return ERROR(corruption_detected);
1442  /* save reps for next block */
1443  { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]); }
1444  }
1445 
1446  /* last literal segment */
1447  { size_t const lastLLSize = litEnd - litPtr;
1448  if (lastLLSize > (size_t)(oend-op)) return ERROR(dstSize_tooSmall);
1449  memcpy(op, litPtr, lastLLSize);
1450  op += lastLLSize;
1451  }
1452 
1453  return op-ostart;
1454 }
1455 
1456 static size_t
1458  void* dst, size_t maxDstSize,
1459  const void* seqStart, size_t seqSize, int nbSeq,
1460  const ZSTD_longOffset_e isLongOffset)
1461 {
1462  return ZSTD_decompressSequences_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1463 }
1464 
1465 
1466 
1469 {
1470  seq_t seq;
1471  U32 const llBits = seqState->stateLL.table[seqState->stateLL.state].nbAdditionalBits;
1472  U32 const mlBits = seqState->stateML.table[seqState->stateML.state].nbAdditionalBits;
1473  U32 const ofBits = seqState->stateOffb.table[seqState->stateOffb.state].nbAdditionalBits;
1474  U32 const totalBits = llBits+mlBits+ofBits;
1475  U32 const llBase = seqState->stateLL.table[seqState->stateLL.state].baseValue;
1476  U32 const mlBase = seqState->stateML.table[seqState->stateML.state].baseValue;
1477  U32 const ofBase = seqState->stateOffb.table[seqState->stateOffb.state].baseValue;
1478 
1479  /* sequence */
1480  { size_t offset;
1481  if (!ofBits)
1482  offset = 0;
1483  else {
1486  assert(ofBits <= MaxOff);
1487  if (MEM_32bits() && longOffsets) {
1488  U32 const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN_32-1);
1489  offset = ofBase + (BIT_readBitsFast(&seqState->DStream, ofBits - extraBits) << extraBits);
1490  if (MEM_32bits() || extraBits) BIT_reloadDStream(&seqState->DStream);
1491  if (extraBits) offset += BIT_readBitsFast(&seqState->DStream, extraBits);
1492  } else {
1493  offset = ofBase + BIT_readBitsFast(&seqState->DStream, ofBits); /* <= (ZSTD_WINDOWLOG_MAX-1) bits */
1494  if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream);
1495  }
1496  }
1497 
1498  if (ofBits <= 1) {
1499  offset += (llBase==0);
1500  if (offset) {
1501  size_t temp = (offset==3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
1502  temp += !temp; /* 0 is not valid; input is corrupted; force offset to 1 */
1503  if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1];
1504  seqState->prevOffset[1] = seqState->prevOffset[0];
1505  seqState->prevOffset[0] = offset = temp;
1506  } else {
1507  offset = seqState->prevOffset[0];
1508  }
1509  } else {
1510  seqState->prevOffset[2] = seqState->prevOffset[1];
1511  seqState->prevOffset[1] = seqState->prevOffset[0];
1512  seqState->prevOffset[0] = offset;
1513  }
1514  seq.offset = offset;
1515  }
1516 
1517  seq.matchLength = mlBase + ((mlBits>0) ? BIT_readBitsFast(&seqState->DStream, mlBits) : 0); /* <= 16 bits */
1519  BIT_reloadDStream(&seqState->DStream);
1521  BIT_reloadDStream(&seqState->DStream);
1522  /* Verify that there is enough bits to read the rest of the data in 64-bit mode. */
1524 
1525  seq.litLength = llBase + ((llBits>0) ? BIT_readBitsFast(&seqState->DStream, llBits) : 0); /* <= 16 bits */
1526  if (MEM_32bits())
1527  BIT_reloadDStream(&seqState->DStream);
1528 
1529  { size_t const pos = seqState->pos + seq.litLength;
1530  const BYTE* const matchBase = (seq.offset > pos) ? seqState->dictEnd : seqState->prefixStart;
1531  seq.match = matchBase + pos - seq.offset; /* note : this operation can overflow when seq.offset is really too large, which can only happen when input is corrupted.
1532  * No consequence though : no memory access will occur, overly large offset will be detected in ZSTD_execSequenceLong() */
1533  seqState->pos = pos + seq.matchLength;
1534  }
1535 
1536  /* ANS state update */
1537  ZSTD_updateFseState(&seqState->stateLL, &seqState->DStream); /* <= 9 bits */
1538  ZSTD_updateFseState(&seqState->stateML, &seqState->DStream); /* <= 9 bits */
1539  if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */
1540  ZSTD_updateFseState(&seqState->stateOffb, &seqState->DStream); /* <= 8 bits */
1541 
1542  return seq;
1543 }
1544 
1545 FORCE_INLINE_TEMPLATE size_t
1547  ZSTD_DCtx* dctx,
1548  void* dst, size_t maxDstSize,
1549  const void* seqStart, size_t seqSize, int nbSeq,
1550  const ZSTD_longOffset_e isLongOffset)
1551 {
1552  const BYTE* ip = (const BYTE*)seqStart;
1553  const BYTE* const iend = ip + seqSize;
1554  BYTE* const ostart = (BYTE* const)dst;
1555  BYTE* const oend = ostart + maxDstSize;
1556  BYTE* op = ostart;
1557  const BYTE* litPtr = dctx->litPtr;
1558  const BYTE* const litEnd = litPtr + dctx->litSize;
1559  const BYTE* const prefixStart = (const BYTE*) (dctx->prefixStart);
1560  const BYTE* const dictStart = (const BYTE*) (dctx->virtualStart);
1561  const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
1562 
1563  /* Regen sequences */
1564  if (nbSeq) {
1565 #define STORED_SEQS 4
1566 #define STOSEQ_MASK (STORED_SEQS-1)
1567 #define ADVANCED_SEQS 4
1569  int const seqAdvance = MIN(nbSeq, ADVANCED_SEQS);
1570  seqState_t seqState;
1571  int seqNb;
1572  dctx->fseEntropy = 1;
1573  { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->entropy.rep[i]; }
1574  seqState.prefixStart = prefixStart;
1575  seqState.pos = (size_t)(op-prefixStart);
1576  seqState.dictEnd = dictEnd;
1577  CHECK_E(BIT_initDStream(&seqState.DStream, ip, iend-ip), corruption_detected);
1578  ZSTD_initFseState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
1579  ZSTD_initFseState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
1580  ZSTD_initFseState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
1581 
1582  /* prepare in advance */
1583  for (seqNb=0; (BIT_reloadDStream(&seqState.DStream) <= BIT_DStream_completed) && (seqNb<seqAdvance); seqNb++) {
1584  sequences[seqNb] = ZSTD_decodeSequenceLong(&seqState, isLongOffset);
1585  }
1586  if (seqNb<seqAdvance) return ERROR(corruption_detected);
1587 
1588  /* decode and decompress */
1589  for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (seqNb<nbSeq) ; seqNb++) {
1590  seq_t const sequence = ZSTD_decodeSequenceLong(&seqState, isLongOffset);
1591  size_t const oneSeqSize = ZSTD_execSequenceLong(op, oend, sequences[(seqNb-ADVANCED_SEQS) & STOSEQ_MASK], &litPtr, litEnd, prefixStart, dictStart, dictEnd);
1592  if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
1593  PREFETCH(sequence.match); /* note : it's safe to invoke PREFETCH() on any memory address, including invalid ones */
1594  sequences[seqNb&STOSEQ_MASK] = sequence;
1595  op += oneSeqSize;
1596  }
1597  if (seqNb<nbSeq) return ERROR(corruption_detected);
1598 
1599  /* finish queue */
1600  seqNb -= seqAdvance;
1601  for ( ; seqNb<nbSeq ; seqNb++) {
1602  size_t const oneSeqSize = ZSTD_execSequenceLong(op, oend, sequences[seqNb&STOSEQ_MASK], &litPtr, litEnd, prefixStart, dictStart, dictEnd);
1603  if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
1604  op += oneSeqSize;
1605  }
1606 
1607  /* save reps for next block */
1608  { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]); }
1609 #undef STORED_SEQS
1610 #undef STOSEQ_MASK
1611 #undef ADVANCED_SEQS
1612  }
1613 
1614  /* last literal segment */
1615  { size_t const lastLLSize = litEnd - litPtr;
1616  if (lastLLSize > (size_t)(oend-op)) return ERROR(dstSize_tooSmall);
1617  memcpy(op, litPtr, lastLLSize);
1618  op += lastLLSize;
1619  }
1620 
1621  return op-ostart;
1622 }
1623 
1624 static size_t
1626  void* dst, size_t maxDstSize,
1627  const void* seqStart, size_t seqSize, int nbSeq,
1628  const ZSTD_longOffset_e isLongOffset)
1629 {
1630  return ZSTD_decompressSequencesLong_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1631 }
1632 
1633 
1634 
1635 #if DYNAMIC_BMI2
1636 
1637 static TARGET_ATTRIBUTE("bmi2") size_t
1638 ZSTD_decompressSequences_bmi2(ZSTD_DCtx* dctx,
1639  void* dst, size_t maxDstSize,
1640  const void* seqStart, size_t seqSize, int nbSeq,
1641  const ZSTD_longOffset_e isLongOffset)
1642 {
1643  return ZSTD_decompressSequences_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1644 }
1645 
1646 static TARGET_ATTRIBUTE("bmi2") size_t
1647 ZSTD_decompressSequencesLong_bmi2(ZSTD_DCtx* dctx,
1648  void* dst, size_t maxDstSize,
1649  const void* seqStart, size_t seqSize, int nbSeq,
1650  const ZSTD_longOffset_e isLongOffset)
1651 {
1652  return ZSTD_decompressSequencesLong_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1653 }
1654 
1655 #endif
1656 
1658  ZSTD_DCtx *dctx, void *dst, size_t maxDstSize,
1659  const void *seqStart, size_t seqSize, int nbSeq,
1660  const ZSTD_longOffset_e isLongOffset);
1661 
1662 static size_t ZSTD_decompressSequences(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize,
1663  const void* seqStart, size_t seqSize, int nbSeq,
1664  const ZSTD_longOffset_e isLongOffset)
1665 {
1666  DEBUGLOG(5, "ZSTD_decompressSequences");
1667 #if DYNAMIC_BMI2
1668  if (dctx->bmi2) {
1669  return ZSTD_decompressSequences_bmi2(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1670  }
1671 #endif
1672  return ZSTD_decompressSequences_default(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1673 }
1674 
1676  void* dst, size_t maxDstSize,
1677  const void* seqStart, size_t seqSize, int nbSeq,
1678  const ZSTD_longOffset_e isLongOffset)
1679 {
1680  DEBUGLOG(5, "ZSTD_decompressSequencesLong");
1681 #if DYNAMIC_BMI2
1682  if (dctx->bmi2) {
1683  return ZSTD_decompressSequencesLong_bmi2(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1684  }
1685 #endif
1686  return ZSTD_decompressSequencesLong_default(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1687 }
1688 
1689 /* ZSTD_getLongOffsetsShare() :
1690  * condition : offTable must be valid
1691  * @return : "share" of long offsets (arbitrarily defined as > (1<<23))
1692  * compared to maximum possible of (1<<OffFSELog) */
1693 static unsigned
1695 {
1696  const void* ptr = offTable;
1697  U32 const tableLog = ((const ZSTD_seqSymbol_header*)ptr)[0].tableLog;
1698  const ZSTD_seqSymbol* table = offTable + 1;
1699  U32 const max = 1 << tableLog;
1700  U32 u, total = 0;
1701  DEBUGLOG(5, "ZSTD_getLongOffsetsShare: (tableLog=%u)", tableLog);
1702 
1703  assert(max <= (1 << OffFSELog)); /* max not too large */
1704  for (u=0; u<max; u++) {
1705  if (table[u].nbAdditionalBits > 22) total += 1;
1706  }
1707 
1708  assert(tableLog <= OffFSELog);
1709  total <<= (OffFSELog - tableLog); /* scale to OffFSELog */
1710 
1711  return total;
1712 }
1713 
1714 
1716  void* dst, size_t dstCapacity,
1717  const void* src, size_t srcSize, const int frame)
1718 { /* blockType == blockCompressed */
1719  const BYTE* ip = (const BYTE*)src;
1720  /* isLongOffset must be true if there are long offsets.
1721  * Offsets are long if they are larger than 2^STREAM_ACCUMULATOR_MIN.
1722  * We don't expect that to be the case in 64-bit mode.
1723  * In block mode, window size is not known, so we have to be conservative.
1724  * (note: but it could be evaluated from current-lowLimit)
1725  */
1726  ZSTD_longOffset_e const isLongOffset = (ZSTD_longOffset_e)(MEM_32bits() && (!frame || dctx->fParams.windowSize > (1ULL << STREAM_ACCUMULATOR_MIN)));
1727  DEBUGLOG(5, "ZSTD_decompressBlock_internal (size : %u)", (U32)srcSize);
1728 
1729  if (srcSize >= ZSTD_BLOCKSIZE_MAX) return ERROR(srcSize_wrong);
1730 
1731  /* Decode literals section */
1732  { size_t const litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize);
1733  DEBUGLOG(5, "ZSTD_decodeLiteralsBlock : %u", (U32)litCSize);
1734  if (ZSTD_isError(litCSize)) return litCSize;
1735  ip += litCSize;
1736  srcSize -= litCSize;
1737  }
1738 
1739  /* Build Decoding Tables */
1740  { int nbSeq;
1741  size_t const seqHSize = ZSTD_decodeSeqHeaders(dctx, &nbSeq, ip, srcSize);
1742  if (ZSTD_isError(seqHSize)) return seqHSize;
1743  ip += seqHSize;
1744  srcSize -= seqHSize;
1745 
1746  if ( (!frame || dctx->fParams.windowSize > (1<<24))
1747  && (nbSeq>0) ) { /* could probably use a larger nbSeq limit */
1748  U32 const shareLongOffsets = ZSTD_getLongOffsetsShare(dctx->OFTptr);
1749  U32 const minShare = MEM_64bits() ? 7 : 20; /* heuristic values, correspond to 2.73% and 7.81% */
1750  if (shareLongOffsets >= minShare)
1751  return ZSTD_decompressSequencesLong(dctx, dst, dstCapacity, ip, srcSize, nbSeq, isLongOffset);
1752  }
1753 
1754  return ZSTD_decompressSequences(dctx, dst, dstCapacity, ip, srcSize, nbSeq, isLongOffset);
1755  }
1756 }
1757 
1758 
1759 static void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst)
1760 {
1761  if (dst != dctx->previousDstEnd) { /* not contiguous */
1762  dctx->dictEnd = dctx->previousDstEnd;
1763  dctx->virtualStart = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->prefixStart));
1764  dctx->prefixStart = dst;
1765  dctx->previousDstEnd = dst;
1766  }
1767 }
1768 
1770  void* dst, size_t dstCapacity,
1771  const void* src, size_t srcSize)
1772 {
1773  size_t dSize;
1774  ZSTD_checkContinuity(dctx, dst);
1775  dSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize, /* frame */ 0);
1776  dctx->previousDstEnd = (char*)dst + dSize;
1777  return dSize;
1778 }
1779 
1780 
1783 ZSTDLIB_API size_t ZSTD_insertBlock(ZSTD_DCtx* dctx, const void* blockStart, size_t blockSize)
1784 {
1785  ZSTD_checkContinuity(dctx, blockStart);
1786  dctx->previousDstEnd = (const char*)blockStart + blockSize;
1787  return blockSize;
1788 }
1789 
1790 
1791 static size_t ZSTD_generateNxBytes(void* dst, size_t dstCapacity, BYTE value, size_t length)
1792 {
1793  if (length > dstCapacity) return ERROR(dstSize_tooSmall);
1794  memset(dst, value, length);
1795  return length;
1796 }
1797 
1803 size_t ZSTD_findFrameCompressedSize(const void *src, size_t srcSize)
1804 {
1805 #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT >= 1)
1806  if (ZSTD_isLegacy(src, srcSize))
1807  return ZSTD_findFrameCompressedSizeLegacy(src, srcSize);
1808 #endif
1809  if ( (srcSize >= ZSTD_skippableHeaderSize)
1810  && (MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START ) {
1811  return ZSTD_skippableHeaderSize + MEM_readLE32((const BYTE*)src + ZSTD_FRAMEIDSIZE);
1812  } else {
1813  const BYTE* ip = (const BYTE*)src;
1814  const BYTE* const ipstart = ip;
1815  size_t remainingSize = srcSize;
1816  ZSTD_frameHeader zfh;
1817 
1818  /* Extract Frame Header */
1819  { size_t const ret = ZSTD_getFrameHeader(&zfh, src, srcSize);
1820  if (ZSTD_isError(ret)) return ret;
1821  if (ret > 0) return ERROR(srcSize_wrong);
1822  }
1823 
1824  ip += zfh.headerSize;
1825  remainingSize -= zfh.headerSize;
1826 
1827  /* Loop on each block */
1828  while (1) {
1829  blockProperties_t blockProperties;
1830  size_t const cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
1831  if (ZSTD_isError(cBlockSize)) return cBlockSize;
1832 
1833  if (ZSTD_blockHeaderSize + cBlockSize > remainingSize)
1834  return ERROR(srcSize_wrong);
1835 
1836  ip += ZSTD_blockHeaderSize + cBlockSize;
1837  remainingSize -= ZSTD_blockHeaderSize + cBlockSize;
1838 
1839  if (blockProperties.lastBlock) break;
1840  }
1841 
1842  if (zfh.checksumFlag) { /* Final frame content checksum */
1843  if (remainingSize < 4) return ERROR(srcSize_wrong);
1844  ip += 4;
1845  }
1846 
1847  return ip - ipstart;
1848  }
1849 }
1850 
1853 static size_t ZSTD_decompressFrame(ZSTD_DCtx* dctx,
1854  void* dst, size_t dstCapacity,
1855  const void** srcPtr, size_t *srcSizePtr)
1856 {
1857  const BYTE* ip = (const BYTE*)(*srcPtr);
1858  BYTE* const ostart = (BYTE* const)dst;
1859  BYTE* const oend = ostart + dstCapacity;
1860  BYTE* op = ostart;
1861  size_t remainingSize = *srcSizePtr;
1862 
1863  /* check */
1864  if (remainingSize < ZSTD_frameHeaderSize_min+ZSTD_blockHeaderSize)
1865  return ERROR(srcSize_wrong);
1866 
1867  /* Frame Header */
1868  { size_t const frameHeaderSize = ZSTD_frameHeaderSize(ip, ZSTD_frameHeaderSize_prefix);
1869  if (ZSTD_isError(frameHeaderSize)) return frameHeaderSize;
1870  if (remainingSize < frameHeaderSize+ZSTD_blockHeaderSize)
1871  return ERROR(srcSize_wrong);
1872  CHECK_F( ZSTD_decodeFrameHeader(dctx, ip, frameHeaderSize) );
1873  ip += frameHeaderSize; remainingSize -= frameHeaderSize;
1874  }
1875 
1876  /* Loop on each block */
1877  while (1) {
1878  size_t decodedSize;
1879  blockProperties_t blockProperties;
1880  size_t const cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
1881  if (ZSTD_isError(cBlockSize)) return cBlockSize;
1882 
1884  remainingSize -= ZSTD_blockHeaderSize;
1885  if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
1886 
1887  switch(blockProperties.blockType)
1888  {
1889  case bt_compressed:
1890  decodedSize = ZSTD_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize, /* frame */ 1);
1891  break;
1892  case bt_raw :
1893  decodedSize = ZSTD_copyRawBlock(op, oend-op, ip, cBlockSize);
1894  break;
1895  case bt_rle :
1896  decodedSize = ZSTD_generateNxBytes(op, oend-op, *ip, blockProperties.origSize);
1897  break;
1898  case bt_reserved :
1899  default:
1900  return ERROR(corruption_detected);
1901  }
1902 
1903  if (ZSTD_isError(decodedSize)) return decodedSize;
1904  if (dctx->fParams.checksumFlag)
1905  XXH64_update(&dctx->xxhState, op, decodedSize);
1906  op += decodedSize;
1907  ip += cBlockSize;
1908  remainingSize -= cBlockSize;
1909  if (blockProperties.lastBlock) break;
1910  }
1911 
1912  if (dctx->fParams.frameContentSize != ZSTD_CONTENTSIZE_UNKNOWN) {
1913  if ((U64)(op-ostart) != dctx->fParams.frameContentSize) {
1914  return ERROR(corruption_detected);
1915  } }
1916  if (dctx->fParams.checksumFlag) { /* Frame content checksum verification */
1917  U32 const checkCalc = (U32)XXH64_digest(&dctx->xxhState);
1918  U32 checkRead;
1919  if (remainingSize<4) return ERROR(checksum_wrong);
1920  checkRead = MEM_readLE32(ip);
1921  if (checkRead != checkCalc) return ERROR(checksum_wrong);
1922  ip += 4;
1923  remainingSize -= 4;
1924  }
1925 
1926  /* Allow caller to get size read */
1927  *srcPtr = ip;
1928  *srcSizePtr = remainingSize;
1929  return op-ostart;
1930 }
1931 
1933  void* dst, size_t dstCapacity,
1934  const void* src, size_t srcSize,
1935  const void* dict, size_t dictSize,
1936  const ZSTD_DDict* ddict)
1937 {
1938  void* const dststart = dst;
1939  int moreThan1Frame = 0;
1940 
1941  DEBUGLOG(5, "ZSTD_decompressMultiFrame");
1942  assert(dict==NULL || ddict==NULL); /* either dict or ddict set, not both */
1943 
1944  if (ddict) {
1945  dict = ZSTD_DDictDictContent(ddict);
1946  dictSize = ZSTD_DDictDictSize(ddict);
1947  }
1948 
1949  while (srcSize >= ZSTD_frameHeaderSize_prefix) {
1950 
1951 #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT >= 1)
1952  if (ZSTD_isLegacy(src, srcSize)) {
1953  size_t decodedSize;
1954  size_t const frameSize = ZSTD_findFrameCompressedSizeLegacy(src, srcSize);
1955  if (ZSTD_isError(frameSize)) return frameSize;
1956  /* legacy support is not compatible with static dctx */
1957  if (dctx->staticSize) return ERROR(memory_allocation);
1958 
1959  decodedSize = ZSTD_decompressLegacy(dst, dstCapacity, src, frameSize, dict, dictSize);
1960 
1961  dst = (BYTE*)dst + decodedSize;
1962  dstCapacity -= decodedSize;
1963 
1964  src = (const BYTE*)src + frameSize;
1965  srcSize -= frameSize;
1966 
1967  continue;
1968  }
1969 #endif
1970 
1971  { U32 const magicNumber = MEM_readLE32(src);
1972  DEBUGLOG(4, "reading magic number %08X (expecting %08X)",
1973  (U32)magicNumber, (U32)ZSTD_MAGICNUMBER);
1974  if ((magicNumber & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
1975  size_t skippableSize;
1976  if (srcSize < ZSTD_skippableHeaderSize)
1977  return ERROR(srcSize_wrong);
1978  skippableSize = MEM_readLE32((const BYTE*)src + ZSTD_FRAMEIDSIZE)
1979  + ZSTD_skippableHeaderSize;
1980  if (srcSize < skippableSize) return ERROR(srcSize_wrong);
1981 
1982  src = (const BYTE *)src + skippableSize;
1983  srcSize -= skippableSize;
1984  continue;
1985  } }
1986 
1987  if (ddict) {
1988  /* we were called from ZSTD_decompress_usingDDict */
1990  } else {
1991  /* this will initialize correctly with no dict if dict == NULL, so
1992  * use this in all cases but ddict */
1993  CHECK_F(ZSTD_decompressBegin_usingDict(dctx, dict, dictSize));
1994  }
1995  ZSTD_checkContinuity(dctx, dst);
1996 
1997  { const size_t res = ZSTD_decompressFrame(dctx, dst, dstCapacity,
1998  &src, &srcSize);
2000  && (moreThan1Frame==1) ) {
2001  /* at least one frame successfully completed,
2002  * but following bytes are garbage :
2003  * it's more likely to be a srcSize error,
2004  * specifying more bytes than compressed size of frame(s).
2005  * This error message replaces ERROR(prefix_unknown),
2006  * which would be confusing, as the first header is actually correct.
2007  * Note that one could be unlucky, it might be a corruption error instead,
2008  * happening right at the place where we expect zstd magic bytes.
2009  * But this is _much_ less likely than a srcSize field error. */
2010  return ERROR(srcSize_wrong);
2011  }
2012  if (ZSTD_isError(res)) return res;
2013  /* no need to bound check, ZSTD_decompressFrame already has */
2014  dst = (BYTE*)dst + res;
2015  dstCapacity -= res;
2016  }
2017  moreThan1Frame = 1;
2018  } /* while (srcSize >= ZSTD_frameHeaderSize_prefix) */
2019 
2020  if (srcSize) return ERROR(srcSize_wrong); /* input not entirely consumed */
2021 
2022  return (BYTE*)dst - (BYTE*)dststart;
2023 }
2024 
2026  void* dst, size_t dstCapacity,
2027  const void* src, size_t srcSize,
2028  const void* dict, size_t dictSize)
2029 {
2030  return ZSTD_decompressMultiFrame(dctx, dst, dstCapacity, src, srcSize, dict, dictSize, NULL);
2031 }
2032 
2033 
2034 size_t ZSTD_decompressDCtx(ZSTD_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
2035 {
2036  return ZSTD_decompress_usingDict(dctx, dst, dstCapacity, src, srcSize, NULL, 0);
2037 }
2038 
2039 
2040 size_t ZSTD_decompress(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
2041 {
2042 #if defined(ZSTD_HEAPMODE) && (ZSTD_HEAPMODE>=1)
2043  size_t regenSize;
2044  ZSTD_DCtx* const dctx = ZSTD_createDCtx();
2045  if (dctx==NULL) return ERROR(memory_allocation);
2046  regenSize = ZSTD_decompressDCtx(dctx, dst, dstCapacity, src, srcSize);
2047  ZSTD_freeDCtx(dctx);
2048  return regenSize;
2049 #else /* stack mode */
2050  ZSTD_DCtx dctx;
2051  ZSTD_initDCtx_internal(&dctx);
2052  return ZSTD_decompressDCtx(&dctx, dst, dstCapacity, src, srcSize);
2053 #endif
2054 }
2055 
2056 
2057 /*-**************************************
2058 * Advanced Streaming Decompression API
2059 * Bufferless and synchronous
2060 ****************************************/
2061 size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx) { return dctx->expected; }
2062 
2063 ZSTD_nextInputType_e ZSTD_nextInputType(ZSTD_DCtx* dctx) {
2064  switch(dctx->stage)
2065  {
2066  default: /* should not happen */
2067  assert(0);
2070  return ZSTDnit_frameHeader;
2072  return ZSTDnit_blockHeader;
2074  return ZSTDnit_block;
2076  return ZSTDnit_lastBlock;
2077  case ZSTDds_checkChecksum:
2078  return ZSTDnit_checksum;
2080  case ZSTDds_skipFrame:
2081  return ZSTDnit_skippableFrame;
2082  }
2083 }
2084 
2085 static int ZSTD_isSkipFrame(ZSTD_DCtx* dctx) { return dctx->stage == ZSTDds_skipFrame; }
2086 
2091 size_t ZSTD_decompressContinue(ZSTD_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
2092 {
2093  DEBUGLOG(5, "ZSTD_decompressContinue (srcSize:%u)", (U32)srcSize);
2094  /* Sanity check */
2095  if (srcSize != dctx->expected) return ERROR(srcSize_wrong); /* not allowed */
2096  if (dstCapacity) ZSTD_checkContinuity(dctx, dst);
2097 
2098  switch (dctx->stage)
2099  {
2101  assert(src != NULL);
2102  if (dctx->format == ZSTD_f_zstd1) { /* allows header */
2103  assert(srcSize >= ZSTD_FRAMEIDSIZE); /* to read skippable magic number */
2104  if ((MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) { /* skippable frame */
2105  memcpy(dctx->headerBuffer, src, srcSize);
2106  dctx->expected = ZSTD_skippableHeaderSize - srcSize; /* remaining to load to get full skippable frame header */
2108  return 0;
2109  } }
2110  dctx->headerSize = ZSTD_frameHeaderSize_internal(src, srcSize, dctx->format);
2111  if (ZSTD_isError(dctx->headerSize)) return dctx->headerSize;
2112  memcpy(dctx->headerBuffer, src, srcSize);
2113  dctx->expected = dctx->headerSize - srcSize;
2115  return 0;
2116 
2118  assert(src != NULL);
2119  memcpy(dctx->headerBuffer + (dctx->headerSize - srcSize), src, srcSize);
2123  return 0;
2124 
2126  { blockProperties_t bp;
2127  size_t const cBlockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
2128  if (ZSTD_isError(cBlockSize)) return cBlockSize;
2129  dctx->expected = cBlockSize;
2130  dctx->bType = bp.blockType;
2131  dctx->rleSize = bp.origSize;
2132  if (cBlockSize) {
2134  return 0;
2135  }
2136  /* empty block */
2137  if (bp.lastBlock) {
2138  if (dctx->fParams.checksumFlag) {
2139  dctx->expected = 4;
2140  dctx->stage = ZSTDds_checkChecksum;
2141  } else {
2142  dctx->expected = 0; /* end of frame */
2144  }
2145  } else {
2146  dctx->expected = ZSTD_blockHeaderSize; /* jump to next header */
2148  }
2149  return 0;
2150  }
2151 
2154  DEBUGLOG(5, "ZSTD_decompressContinue: case ZSTDds_decompressBlock");
2155  { size_t rSize;
2156  switch(dctx->bType)
2157  {
2158  case bt_compressed:
2159  DEBUGLOG(5, "ZSTD_decompressContinue: case bt_compressed");
2160  rSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize, /* frame */ 1);
2161  break;
2162  case bt_raw :
2163  rSize = ZSTD_copyRawBlock(dst, dstCapacity, src, srcSize);
2164  break;
2165  case bt_rle :
2166  rSize = ZSTD_setRleBlock(dst, dstCapacity, src, srcSize, dctx->rleSize);
2167  break;
2168  case bt_reserved : /* should never happen */
2169  default:
2170  return ERROR(corruption_detected);
2171  }
2172  if (ZSTD_isError(rSize)) return rSize;
2173  DEBUGLOG(5, "ZSTD_decompressContinue: decoded size from block : %u", (U32)rSize);
2174  dctx->decodedSize += rSize;
2175  if (dctx->fParams.checksumFlag) XXH64_update(&dctx->xxhState, dst, rSize);
2176 
2177  if (dctx->stage == ZSTDds_decompressLastBlock) { /* end of frame */
2178  DEBUGLOG(4, "ZSTD_decompressContinue: decoded size from frame : %u", (U32)dctx->decodedSize);
2179  if (dctx->fParams.frameContentSize != ZSTD_CONTENTSIZE_UNKNOWN) {
2180  if (dctx->decodedSize != dctx->fParams.frameContentSize) {
2181  return ERROR(corruption_detected);
2182  } }
2183  if (dctx->fParams.checksumFlag) { /* another round for frame checksum */
2184  dctx->expected = 4;
2185  dctx->stage = ZSTDds_checkChecksum;
2186  } else {
2187  dctx->expected = 0; /* ends here */
2189  }
2190  } else {
2193  dctx->previousDstEnd = (char*)dst + rSize;
2194  }
2195  return rSize;
2196  }
2197 
2198  case ZSTDds_checkChecksum:
2199  assert(srcSize == 4); /* guaranteed by dctx->expected */
2200  { U32 const h32 = (U32)XXH64_digest(&dctx->xxhState);
2201  U32 const check32 = MEM_readLE32(src);
2202  DEBUGLOG(4, "ZSTD_decompressContinue: checksum : calculated %08X :: %08X read", h32, check32);
2203  if (check32 != h32) return ERROR(checksum_wrong);
2204  dctx->expected = 0;
2206  return 0;
2207  }
2208 
2210  assert(src != NULL);
2211  assert(srcSize <= ZSTD_skippableHeaderSize);
2212  memcpy(dctx->headerBuffer + (ZSTD_skippableHeaderSize - srcSize), src, srcSize); /* complete skippable header */
2213  dctx->expected = MEM_readLE32(dctx->headerBuffer + ZSTD_FRAMEIDSIZE); /* note : dctx->expected can grow seriously large, beyond local buffer size */
2214  dctx->stage = ZSTDds_skipFrame;
2215  return 0;
2216 
2217  case ZSTDds_skipFrame:
2218  dctx->expected = 0;
2220  return 0;
2221 
2222  default:
2223  return ERROR(GENERIC); /* impossible */
2224  }
2225 }
2226 
2227 
2228 static size_t ZSTD_refDictContent(ZSTD_DCtx* dctx, const void* dict, size_t dictSize)
2229 {
2230  dctx->dictEnd = dctx->previousDstEnd;
2231  dctx->virtualStart = (const char*)dict - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->prefixStart));
2232  dctx->prefixStart = dict;
2233  dctx->previousDstEnd = (const char*)dict + dictSize;
2234  return 0;
2235 }
2236 
2241  const void* const dict, size_t const dictSize)
2242 {
2243  const BYTE* dictPtr = (const BYTE*)dict;
2244  const BYTE* const dictEnd = dictPtr + dictSize;
2245 
2246  if (dictSize <= 8) return ERROR(dictionary_corrupted);
2247  assert(MEM_readLE32(dict) == ZSTD_MAGIC_DICTIONARY); /* dict must be valid */
2248  dictPtr += 8; /* skip header = magic + dictID */
2249 
2250  ZSTD_STATIC_ASSERT(offsetof(ZSTD_entropyDTables_t, OFTable) == offsetof(ZSTD_entropyDTables_t, LLTable) + sizeof(entropy->LLTable));
2251  ZSTD_STATIC_ASSERT(offsetof(ZSTD_entropyDTables_t, MLTable) == offsetof(ZSTD_entropyDTables_t, OFTable) + sizeof(entropy->OFTable));
2252  ZSTD_STATIC_ASSERT(sizeof(entropy->LLTable) + sizeof(entropy->OFTable) + sizeof(entropy->MLTable) >= HUF_DECOMPRESS_WORKSPACE_SIZE);
2253  { void* const workspace = &entropy->LLTable; /* use fse tables as temporary workspace; implies fse tables are grouped together */
2254  size_t const workspaceSize = sizeof(entropy->LLTable) + sizeof(entropy->OFTable) + sizeof(entropy->MLTable);
2255  size_t const hSize = HUF_readDTableX2_wksp(entropy->hufTable,
2256  dictPtr, dictEnd - dictPtr,
2257  workspace, workspaceSize);
2258  if (HUF_isError(hSize)) return ERROR(dictionary_corrupted);
2259  dictPtr += hSize;
2260  }
2261 
2262  { short offcodeNCount[MaxOff+1];
2263  U32 offcodeMaxValue = MaxOff, offcodeLog;
2264  size_t const offcodeHeaderSize = FSE_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dictPtr, dictEnd-dictPtr);
2265  if (FSE_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted);
2266  if (offcodeMaxValue > MaxOff) return ERROR(dictionary_corrupted);
2267  if (offcodeLog > OffFSELog) return ERROR(dictionary_corrupted);
2268  ZSTD_buildFSETable( entropy->OFTable,
2269  offcodeNCount, offcodeMaxValue,
2270  OF_base, OF_bits,
2271  offcodeLog);
2272  dictPtr += offcodeHeaderSize;
2273  }
2274 
2275  { short matchlengthNCount[MaxML+1];
2276  unsigned matchlengthMaxValue = MaxML, matchlengthLog;
2277  size_t const matchlengthHeaderSize = FSE_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd-dictPtr);
2278  if (FSE_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted);
2279  if (matchlengthMaxValue > MaxML) return ERROR(dictionary_corrupted);
2280  if (matchlengthLog > MLFSELog) return ERROR(dictionary_corrupted);
2281  ZSTD_buildFSETable( entropy->MLTable,
2282  matchlengthNCount, matchlengthMaxValue,
2283  ML_base, ML_bits,
2284  matchlengthLog);
2285  dictPtr += matchlengthHeaderSize;
2286  }
2287 
2288  { short litlengthNCount[MaxLL+1];
2289  unsigned litlengthMaxValue = MaxLL, litlengthLog;
2290  size_t const litlengthHeaderSize = FSE_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd-dictPtr);
2291  if (FSE_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted);
2292  if (litlengthMaxValue > MaxLL) return ERROR(dictionary_corrupted);
2293  if (litlengthLog > LLFSELog) return ERROR(dictionary_corrupted);
2294  ZSTD_buildFSETable( entropy->LLTable,
2295  litlengthNCount, litlengthMaxValue,
2296  LL_base, LL_bits,
2297  litlengthLog);
2298  dictPtr += litlengthHeaderSize;
2299  }
2300 
2301  if (dictPtr+12 > dictEnd) return ERROR(dictionary_corrupted);
2302  { int i;
2303  size_t const dictContentSize = (size_t)(dictEnd - (dictPtr+12));
2304  for (i=0; i<3; i++) {
2305  U32 const rep = MEM_readLE32(dictPtr); dictPtr += 4;
2306  if (rep==0 || rep >= dictContentSize) return ERROR(dictionary_corrupted);
2307  entropy->rep[i] = rep;
2308  } }
2309 
2310  return dictPtr - (const BYTE*)dict;
2311 }
2312 
2313 static size_t ZSTD_decompress_insertDictionary(ZSTD_DCtx* dctx, const void* dict, size_t dictSize)
2314 {
2315  if (dictSize < 8) return ZSTD_refDictContent(dctx, dict, dictSize);
2316  { U32 const magic = MEM_readLE32(dict);
2317  if (magic != ZSTD_MAGIC_DICTIONARY) {
2318  return ZSTD_refDictContent(dctx, dict, dictSize); /* pure content mode */
2319  } }
2320  dctx->dictID = MEM_readLE32((const char*)dict + ZSTD_FRAMEIDSIZE);
2321 
2322  /* load entropy tables */
2323  { size_t const eSize = ZSTD_loadEntropy(&dctx->entropy, dict, dictSize);
2324  if (ZSTD_isError(eSize)) return ERROR(dictionary_corrupted);
2325  dict = (const char*)dict + eSize;
2326  dictSize -= eSize;
2327  }
2328  dctx->litEntropy = dctx->fseEntropy = 1;
2329 
2330  /* reference dictionary content */
2331  return ZSTD_refDictContent(dctx, dict, dictSize);
2332 }
2333 
2335 {
2336  assert(dctx != NULL);
2337  dctx->expected = ZSTD_startingInputLength(dctx->format); /* dctx->format must be properly set */
2339  dctx->decodedSize = 0;
2340  dctx->previousDstEnd = NULL;
2341  dctx->prefixStart = NULL;
2342  dctx->virtualStart = NULL;
2343  dctx->dictEnd = NULL;
2344  dctx->entropy.hufTable[0] = (HUF_DTable)((HufLog)*0x1000001); /* cover both little and big endian */
2345  dctx->litEntropy = dctx->fseEntropy = 0;
2346  dctx->dictID = 0;
2347  ZSTD_STATIC_ASSERT(sizeof(dctx->entropy.rep) == sizeof(repStartValue));
2348  memcpy(dctx->entropy.rep, repStartValue, sizeof(repStartValue)); /* initial repcodes */
2349  dctx->LLTptr = dctx->entropy.LLTable;
2350  dctx->MLTptr = dctx->entropy.MLTable;
2351  dctx->OFTptr = dctx->entropy.OFTable;
2352  dctx->HUFptr = dctx->entropy.hufTable;
2353  return 0;
2354 }
2355 
2356 size_t ZSTD_decompressBegin_usingDict(ZSTD_DCtx* dctx, const void* dict, size_t dictSize)
2357 {
2358  CHECK_F( ZSTD_decompressBegin(dctx) );
2359  if (dict && dictSize)
2360  CHECK_E(ZSTD_decompress_insertDictionary(dctx, dict, dictSize), dictionary_corrupted);
2361  return 0;
2362 }
2363 
2364 
2365 /* ====== ZSTD_DDict ====== */
2366 
2368  void* dictBuffer;
2369  const void* dictContent;
2370  size_t dictSize;
2374  ZSTD_customMem cMem;
2375 }; /* typedef'd to ZSTD_DDict within "zstd.h" */
2376 
2377 static const void* ZSTD_DDictDictContent(const ZSTD_DDict* ddict)
2378 {
2379  assert(ddict != NULL);
2380  return ddict->dictContent;
2381 }
2382 
2383 static size_t ZSTD_DDictDictSize(const ZSTD_DDict* ddict)
2384 {
2385  assert(ddict != NULL);
2386  return ddict->dictSize;
2387 }
2388 
2390 {
2391  DEBUGLOG(4, "ZSTD_decompressBegin_usingDDict");
2392  assert(dctx != NULL);
2393  if (ddict) {
2394  dctx->ddictIsCold = (dctx->dictEnd != (const char*)ddict->dictContent + ddict->dictSize);
2395  DEBUGLOG(4, "DDict is %s",
2396  dctx->ddictIsCold ? "~cold~" : "hot!");
2397  }
2398  CHECK_F( ZSTD_decompressBegin(dctx) );
2399  if (ddict) { /* NULL ddict is equivalent to no dictionary */
2400  dctx->dictID = ddict->dictID;
2401  dctx->prefixStart = ddict->dictContent;
2402  dctx->virtualStart = ddict->dictContent;
2403  dctx->dictEnd = (const BYTE*)ddict->dictContent + ddict->dictSize;
2404  dctx->previousDstEnd = dctx->dictEnd;
2405  if (ddict->entropyPresent) {
2406  dctx->litEntropy = 1;
2407  dctx->fseEntropy = 1;
2408  dctx->LLTptr = ddict->entropy.LLTable;
2409  dctx->MLTptr = ddict->entropy.MLTable;
2410  dctx->OFTptr = ddict->entropy.OFTable;
2411  dctx->HUFptr = ddict->entropy.hufTable;
2412  dctx->entropy.rep[0] = ddict->entropy.rep[0];
2413  dctx->entropy.rep[1] = ddict->entropy.rep[1];
2414  dctx->entropy.rep[2] = ddict->entropy.rep[2];
2415  } else {
2416  dctx->litEntropy = 0;
2417  dctx->fseEntropy = 0;
2418  }
2419  }
2420  return 0;
2421 }
2422 
2423 static size_t
2425  ZSTD_dictContentType_e dictContentType)
2426 {
2427  ddict->dictID = 0;
2428  ddict->entropyPresent = 0;
2429  if (dictContentType == ZSTD_dct_rawContent) return 0;
2430 
2431  if (ddict->dictSize < 8) {
2432  if (dictContentType == ZSTD_dct_fullDict)
2433  return ERROR(dictionary_corrupted); /* only accept specified dictionaries */
2434  return 0; /* pure content mode */
2435  }
2436  { U32 const magic = MEM_readLE32(ddict->dictContent);
2437  if (magic != ZSTD_MAGIC_DICTIONARY) {
2438  if (dictContentType == ZSTD_dct_fullDict)
2439  return ERROR(dictionary_corrupted); /* only accept specified dictionaries */
2440  return 0; /* pure content mode */
2441  }
2442  }
2443  ddict->dictID = MEM_readLE32((const char*)ddict->dictContent + ZSTD_FRAMEIDSIZE);
2444 
2445  /* load entropy tables */
2446  CHECK_E( ZSTD_loadEntropy(&ddict->entropy,
2447  ddict->dictContent, ddict->dictSize),
2448  dictionary_corrupted );
2449  ddict->entropyPresent = 1;
2450  return 0;
2451 }
2452 
2453 
2455  const void* dict, size_t dictSize,
2456  ZSTD_dictLoadMethod_e dictLoadMethod,
2457  ZSTD_dictContentType_e dictContentType)
2458 {
2459  if ((dictLoadMethod == ZSTD_dlm_byRef) || (!dict) || (!dictSize)) {
2460  ddict->dictBuffer = NULL;
2461  ddict->dictContent = dict;
2462  if (!dict) dictSize = 0;
2463  } else {
2464  void* const internalBuffer = ZSTD_malloc(dictSize, ddict->cMem);
2465  ddict->dictBuffer = internalBuffer;
2466  ddict->dictContent = internalBuffer;
2467  if (!internalBuffer) return ERROR(memory_allocation);
2468  memcpy(internalBuffer, dict, dictSize);
2469  }
2470  ddict->dictSize = dictSize;
2471  ddict->entropy.hufTable[0] = (HUF_DTable)((HufLog)*0x1000001); /* cover both little and big endian */
2472 
2473  /* parse dictionary content */
2474  CHECK_F( ZSTD_loadEntropy_inDDict(ddict, dictContentType) );
2475 
2476  return 0;
2477 }
2478 
2479 ZSTD_DDict* ZSTD_createDDict_advanced(const void* dict, size_t dictSize,
2480  ZSTD_dictLoadMethod_e dictLoadMethod,
2481  ZSTD_dictContentType_e dictContentType,
2482  ZSTD_customMem customMem)
2483 {
2484  if (!customMem.customAlloc ^ !customMem.customFree) return NULL;
2485 
2486  { ZSTD_DDict* const ddict = (ZSTD_DDict*) ZSTD_malloc(sizeof(ZSTD_DDict), customMem);
2487  if (ddict == NULL) return NULL;
2488  ddict->cMem = customMem;
2489  { size_t const initResult = ZSTD_initDDict_internal(ddict,
2490  dict, dictSize,
2491  dictLoadMethod, dictContentType);
2492  if (ZSTD_isError(initResult)) {
2493  ZSTD_freeDDict(ddict);
2494  return NULL;
2495  } }
2496  return ddict;
2497  }
2498 }
2499 
2504 ZSTD_DDict* ZSTD_createDDict(const void* dict, size_t dictSize)
2505 {
2506  ZSTD_customMem const allocator = { NULL, NULL, NULL };
2507  return ZSTD_createDDict_advanced(dict, dictSize, ZSTD_dlm_byCopy, ZSTD_dct_auto, allocator);
2508 }
2509 
2514 ZSTD_DDict* ZSTD_createDDict_byReference(const void* dictBuffer, size_t dictSize)
2515 {
2516  ZSTD_customMem const allocator = { NULL, NULL, NULL };
2517  return ZSTD_createDDict_advanced(dictBuffer, dictSize, ZSTD_dlm_byRef, ZSTD_dct_auto, allocator);
2518 }
2519 
2520 
2522  void* sBuffer, size_t sBufferSize,
2523  const void* dict, size_t dictSize,
2524  ZSTD_dictLoadMethod_e dictLoadMethod,
2525  ZSTD_dictContentType_e dictContentType)
2526 {
2527  size_t const neededSpace = sizeof(ZSTD_DDict)
2528  + (dictLoadMethod == ZSTD_dlm_byRef ? 0 : dictSize);
2529  ZSTD_DDict* const ddict = (ZSTD_DDict*)sBuffer;
2530  assert(sBuffer != NULL);
2531  assert(dict != NULL);
2532  if ((size_t)sBuffer & 7) return NULL; /* 8-aligned */
2533  if (sBufferSize < neededSpace) return NULL;
2534  if (dictLoadMethod == ZSTD_dlm_byCopy) {
2535  memcpy(ddict+1, dict, dictSize); /* local copy */
2536  dict = ddict+1;
2537  }
2539  dict, dictSize,
2540  ZSTD_dlm_byRef, dictContentType) ))
2541  return NULL;
2542  return ddict;
2543 }
2544 
2545 
2547 {
2548  if (ddict==NULL) return 0; /* support free on NULL */
2549  { ZSTD_customMem const cMem = ddict->cMem;
2550  ZSTD_free(ddict->dictBuffer, cMem);
2551  ZSTD_free(ddict, cMem);
2552  return 0;
2553  }
2554 }
2555 
2559 size_t ZSTD_estimateDDictSize(size_t dictSize, ZSTD_dictLoadMethod_e dictLoadMethod)
2560 {
2561  return sizeof(ZSTD_DDict) + (dictLoadMethod == ZSTD_dlm_byRef ? 0 : dictSize);
2562 }
2563 
2564 size_t ZSTD_sizeof_DDict(const ZSTD_DDict* ddict)
2565 {
2566  if (ddict==NULL) return 0; /* support sizeof on NULL */
2567  return sizeof(*ddict) + (ddict->dictBuffer ? ddict->dictSize : 0) ;
2568 }
2569 
2574 unsigned ZSTD_getDictID_fromDict(const void* dict, size_t dictSize)
2575 {
2576  if (dictSize < 8) return 0;
2577  if (MEM_readLE32(dict) != ZSTD_MAGIC_DICTIONARY) return 0;
2578  return MEM_readLE32((const char*)dict + ZSTD_FRAMEIDSIZE);
2579 }
2580 
2585 unsigned ZSTD_getDictID_fromDDict(const ZSTD_DDict* ddict)
2586 {
2587  if (ddict==NULL) return 0;
2588  return ZSTD_getDictID_fromDict(ddict->dictContent, ddict->dictSize);
2589 }
2590 
2604 unsigned ZSTD_getDictID_fromFrame(const void* src, size_t srcSize)
2605 {
2606  ZSTD_frameHeader zfp = { 0, 0, 0, ZSTD_frame, 0, 0, 0 };
2607  size_t const hError = ZSTD_getFrameHeader(&zfp, src, srcSize);
2608  if (ZSTD_isError(hError)) return 0;
2609  return zfp.dictID;
2610 }
2611 
2612 
2617  void* dst, size_t dstCapacity,
2618  const void* src, size_t srcSize,
2619  const ZSTD_DDict* ddict)
2620 {
2621  /* pass content and size in case legacy frames are encountered */
2622  return ZSTD_decompressMultiFrame(dctx, dst, dstCapacity, src, srcSize,
2623  NULL, 0,
2624  ddict);
2625 }
2626 
2627 
2628 /*=====================================
2629 * Streaming decompression
2630 *====================================*/
2631 
2633 {
2634  DEBUGLOG(3, "ZSTD_createDStream");
2635  return ZSTD_createDStream_advanced(ZSTD_defaultCMem);
2636 }
2637 
2638 ZSTD_DStream* ZSTD_initStaticDStream(void *workspace, size_t workspaceSize)
2639 {
2640  return ZSTD_initStaticDCtx(workspace, workspaceSize);
2641 }
2642 
2643 ZSTD_DStream* ZSTD_createDStream_advanced(ZSTD_customMem customMem)
2644 {
2645  return ZSTD_createDCtx_advanced(customMem);
2646 }
2647 
2649 {
2650  return ZSTD_freeDCtx(zds);
2651 }
2652 
2653 
2654 /* *** Initialization *** */
2655 
2656 size_t ZSTD_DStreamInSize(void) { return ZSTD_BLOCKSIZE_MAX + ZSTD_blockHeaderSize; }
2657 size_t ZSTD_DStreamOutSize(void) { return ZSTD_BLOCKSIZE_MAX; }
2658 
2660  const void* dict, size_t dictSize,
2661  ZSTD_dictLoadMethod_e dictLoadMethod,
2662  ZSTD_dictContentType_e dictContentType)
2663 {
2664  if (dctx->streamStage != zdss_init) return ERROR(stage_wrong);
2665  ZSTD_freeDDict(dctx->ddictLocal);
2666  if (dict && dictSize >= 8) {
2667  dctx->ddictLocal = ZSTD_createDDict_advanced(dict, dictSize, dictLoadMethod, dictContentType, dctx->customMem);
2668  if (dctx->ddictLocal == NULL) return ERROR(memory_allocation);
2669  } else {
2670  dctx->ddictLocal = NULL;
2671  }
2672  dctx->ddict = dctx->ddictLocal;
2673  return 0;
2674 }
2675 
2676 size_t ZSTD_DCtx_loadDictionary_byReference(ZSTD_DCtx* dctx, const void* dict, size_t dictSize)
2677 {
2678  return ZSTD_DCtx_loadDictionary_advanced(dctx, dict, dictSize, ZSTD_dlm_byRef, ZSTD_dct_auto);
2679 }
2680 
2681 size_t ZSTD_DCtx_loadDictionary(ZSTD_DCtx* dctx, const void* dict, size_t dictSize)
2682 {
2683  return ZSTD_DCtx_loadDictionary_advanced(dctx, dict, dictSize, ZSTD_dlm_byCopy, ZSTD_dct_auto);
2684 }
2685 
2686 size_t ZSTD_DCtx_refPrefix_advanced(ZSTD_DCtx* dctx, const void* prefix, size_t prefixSize, ZSTD_dictContentType_e dictContentType)
2687 {
2688  return ZSTD_DCtx_loadDictionary_advanced(dctx, prefix, prefixSize, ZSTD_dlm_byRef, dictContentType);
2689 }
2690 
2691 size_t ZSTD_DCtx_refPrefix(ZSTD_DCtx* dctx, const void* prefix, size_t prefixSize)
2692 {
2693  return ZSTD_DCtx_refPrefix_advanced(dctx, prefix, prefixSize, ZSTD_dct_rawContent);
2694 }
2695 
2696 
2697 /* ZSTD_initDStream_usingDict() :
2698  * return : expected size, aka ZSTD_frameHeaderSize_prefix.
2699  * this function cannot fail */
2700 size_t ZSTD_initDStream_usingDict(ZSTD_DStream* zds, const void* dict, size_t dictSize)
2701 {
2702  DEBUGLOG(4, "ZSTD_initDStream_usingDict");
2703  zds->streamStage = zdss_init;
2704  zds->noForwardProgress = 0;
2705  CHECK_F( ZSTD_DCtx_loadDictionary(zds, dict, dictSize) );
2706  return ZSTD_frameHeaderSize_prefix;
2707 }
2708 
2709 /* note : this variant can't fail */
2711 {
2712  DEBUGLOG(4, "ZSTD_initDStream");
2713  return ZSTD_initDStream_usingDict(zds, NULL, 0);
2714 }
2715 
2716 /* ZSTD_initDStream_usingDDict() :
2717  * ddict will just be referenced, and must outlive decompression session
2718  * this function cannot fail */
2720 {
2721  size_t const initResult = ZSTD_initDStream(dctx);
2722  dctx->ddict = ddict;
2723  return initResult;
2724 }
2725 
2726 /* ZSTD_resetDStream() :
2727  * return : expected size, aka ZSTD_frameHeaderSize_prefix.
2728  * this function cannot fail */
2730 {
2731  DEBUGLOG(4, "ZSTD_resetDStream");
2732  dctx->streamStage = zdss_loadHeader;
2733  dctx->lhSize = dctx->inPos = dctx->outStart = dctx->outEnd = 0;
2734  dctx->legacyVersion = 0;
2735  dctx->hostageByte = 0;
2736  return ZSTD_frameHeaderSize_prefix;
2737 }
2738 
2740  ZSTD_DStreamParameter_e paramType, unsigned paramValue)
2741 {
2742  if (dctx->streamStage != zdss_init) return ERROR(stage_wrong);
2743  switch(paramType)
2744  {
2745  default : return ERROR(parameter_unsupported);
2746  case DStream_p_maxWindowSize :
2747  DEBUGLOG(4, "setting maxWindowSize = %u KB", paramValue >> 10);
2748  dctx->maxWindowSize = paramValue ? paramValue : (U32)(-1);
2749  break;
2750  }
2751  return 0;
2752 }
2753 
2754 size_t ZSTD_DCtx_refDDict(ZSTD_DCtx* dctx, const ZSTD_DDict* ddict)
2755 {
2756  if (dctx->streamStage != zdss_init) return ERROR(stage_wrong);
2757  dctx->ddict = ddict;
2758  return 0;
2759 }
2760 
2761 size_t ZSTD_DCtx_setMaxWindowSize(ZSTD_DCtx* dctx, size_t maxWindowSize)
2762 {
2763  if (dctx->streamStage != zdss_init) return ERROR(stage_wrong);
2764  dctx->maxWindowSize = maxWindowSize;
2765  return 0;
2766 }
2767 
2768 size_t ZSTD_DCtx_setFormat(ZSTD_DCtx* dctx, ZSTD_format_e format)
2769 {
2770  DEBUGLOG(4, "ZSTD_DCtx_setFormat : %u", (unsigned)format);
2771  if (dctx->streamStage != zdss_init) return ERROR(stage_wrong);
2772  dctx->format = format;
2773  return 0;
2774 }
2775 
2776 
2778 {
2779  return ZSTD_sizeof_DCtx(dctx);
2780 }
2781 
2782 size_t ZSTD_decodingBufferSize_min(unsigned long long windowSize, unsigned long long frameContentSize)
2783 {
2784  size_t const blockSize = (size_t) MIN(windowSize, ZSTD_BLOCKSIZE_MAX);
2785  unsigned long long const neededRBSize = windowSize + blockSize + (WILDCOPY_OVERLENGTH * 2);
2786  unsigned long long const neededSize = MIN(frameContentSize, neededRBSize);
2787  size_t const minRBSize = (size_t) neededSize;
2788  if ((unsigned long long)minRBSize != neededSize) return ERROR(frameParameter_windowTooLarge);
2789  return minRBSize;
2790 }
2791 
2792 size_t ZSTD_estimateDStreamSize(size_t windowSize)
2793 {
2794  size_t const blockSize = MIN(windowSize, ZSTD_BLOCKSIZE_MAX);
2795  size_t const inBuffSize = blockSize; /* no block can be larger */
2796  size_t const outBuffSize = ZSTD_decodingBufferSize_min(windowSize, ZSTD_CONTENTSIZE_UNKNOWN);
2797  return ZSTD_estimateDCtxSize() + inBuffSize + outBuffSize;
2798 }
2799 
2800 size_t ZSTD_estimateDStreamSize_fromFrame(const void* src, size_t srcSize)
2801 {
2802  U32 const windowSizeMax = 1U << ZSTD_WINDOWLOG_MAX; /* note : should be user-selectable */
2803  ZSTD_frameHeader zfh;
2804  size_t const err = ZSTD_getFrameHeader(&zfh, src, srcSize);
2805  if (ZSTD_isError(err)) return err;
2806  if (err>0) return ERROR(srcSize_wrong);
2807  if (zfh.windowSize > windowSizeMax)
2808  return ERROR(frameParameter_windowTooLarge);
2809  return ZSTD_estimateDStreamSize((size_t)zfh.windowSize);
2810 }
2811 
2812 
2813 /* ***** Decompression ***** */
2814 
2815 MEM_STATIC size_t ZSTD_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
2816 {
2817  size_t const length = MIN(dstCapacity, srcSize);
2818  memcpy(dst, src, length);
2819  return length;
2820 }
2821 
2822 
2824 {
2825  const char* const istart = (const char*)(input->src) + input->pos;
2826  const char* const iend = (const char*)(input->src) + input->size;
2827  const char* ip = istart;
2828  char* const ostart = (char*)(output->dst) + output->pos;
2829  char* const oend = (char*)(output->dst) + output->size;
2830  char* op = ostart;
2831  U32 someMoreWork = 1;
2832 
2833  DEBUGLOG(5, "ZSTD_decompressStream");
2834  if (input->pos > input->size) { /* forbidden */
2835  DEBUGLOG(5, "in: pos: %u vs size: %u",
2836  (U32)input->pos, (U32)input->size);
2837  return ERROR(srcSize_wrong);
2838  }
2839  if (output->pos > output->size) { /* forbidden */
2840  DEBUGLOG(5, "out: pos: %u vs size: %u",
2841  (U32)output->pos, (U32)output->size);
2842  return ERROR(dstSize_tooSmall);
2843  }
2844  DEBUGLOG(5, "input size : %u", (U32)(input->size - input->pos));
2845 
2846  while (someMoreWork) {
2847  switch(zds->streamStage)
2848  {
2849  case zdss_init :
2850  DEBUGLOG(5, "stage zdss_init => transparent reset ");
2851  ZSTD_resetDStream(zds); /* transparent reset on starting decoding a new frame */
2852  /* fall-through */
2853 
2854  case zdss_loadHeader :
2855  DEBUGLOG(5, "stage zdss_loadHeader (srcSize : %u)", (U32)(iend - ip));
2856 #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT>=1)
2857  if (zds->legacyVersion) {
2858  /* legacy support is incompatible with static dctx */
2859  if (zds->staticSize) return ERROR(memory_allocation);
2860  { size_t const hint = ZSTD_decompressLegacyStream(zds->legacyContext, zds->legacyVersion, output, input);
2861  if (hint==0) zds->streamStage = zdss_init;
2862  return hint;
2863  } }
2864 #endif
2865  { size_t const hSize = ZSTD_getFrameHeader_advanced(&zds->fParams, zds->headerBuffer, zds->lhSize, zds->format);
2866  DEBUGLOG(5, "header size : %u", (U32)hSize);
2867  if (ZSTD_isError(hSize)) {
2868 #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT>=1)
2869  U32 const legacyVersion = ZSTD_isLegacy(istart, iend-istart);
2870  if (legacyVersion) {
2871  const void* const dict = zds->ddict ? zds->ddict->dictContent : NULL;
2872  size_t const dictSize = zds->ddict ? zds->ddict->dictSize : 0;
2873  DEBUGLOG(5, "ZSTD_decompressStream: detected legacy version v0.%u", legacyVersion);
2874  /* legacy support is incompatible with static dctx */
2875  if (zds->staticSize) return ERROR(memory_allocation);
2876  CHECK_F(ZSTD_initLegacyStream(&zds->legacyContext,
2877  zds->previousLegacyVersion, legacyVersion,
2878  dict, dictSize));
2879  zds->legacyVersion = zds->previousLegacyVersion = legacyVersion;
2880  { size_t const hint = ZSTD_decompressLegacyStream(zds->legacyContext, legacyVersion, output, input);
2881  if (hint==0) zds->streamStage = zdss_init; /* or stay in stage zdss_loadHeader */
2882  return hint;
2883  } }
2884 #endif
2885  return hSize; /* error */
2886  }
2887  if (hSize != 0) { /* need more input */
2888  size_t const toLoad = hSize - zds->lhSize; /* if hSize!=0, hSize > zds->lhSize */
2889  size_t const remainingInput = (size_t)(iend-ip);
2890  assert(iend >= ip);
2891  if (toLoad > remainingInput) { /* not enough input to load full header */
2892  if (remainingInput > 0) {
2893  memcpy(zds->headerBuffer + zds->lhSize, ip, remainingInput);
2894  zds->lhSize += remainingInput;
2895  }
2896  input->pos = input->size;
2897  return (MAX(ZSTD_frameHeaderSize_min, hSize) - zds->lhSize) + ZSTD_blockHeaderSize; /* remaining header bytes + next block header */
2898  }
2899  assert(ip != NULL);
2900  memcpy(zds->headerBuffer + zds->lhSize, ip, toLoad); zds->lhSize = hSize; ip += toLoad;
2901  break;
2902  } }
2903 
2904  /* check for single-pass mode opportunity */
2905  if (zds->fParams.frameContentSize && zds->fParams.windowSize /* skippable frame if == 0 */
2906  && (U64)(size_t)(oend-op) >= zds->fParams.frameContentSize) {
2907  size_t const cSize = ZSTD_findFrameCompressedSize(istart, iend-istart);
2908  if (cSize <= (size_t)(iend-istart)) {
2909  /* shortcut : using single-pass mode */
2910  size_t const decompressedSize = ZSTD_decompress_usingDDict(zds, op, oend-op, istart, cSize, zds->ddict);
2911  if (ZSTD_isError(decompressedSize)) return decompressedSize;
2912  DEBUGLOG(4, "shortcut to single-pass ZSTD_decompress_usingDDict()")
2913  ip = istart + cSize;
2914  op += decompressedSize;
2915  zds->expected = 0;
2916  zds->streamStage = zdss_init;
2917  someMoreWork = 0;
2918  break;
2919  } }
2920 
2921  /* Consume header (see ZSTDds_decodeFrameHeader) */
2922  DEBUGLOG(4, "Consume header");
2924 
2925  if ((MEM_readLE32(zds->headerBuffer) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) { /* skippable frame */
2927  zds->stage = ZSTDds_skipFrame;
2928  } else {
2932  }
2933 
2934  /* control buffer memory usage */
2935  DEBUGLOG(4, "Control max memory usage (%u KB <= max %u KB)",
2936  (U32)(zds->fParams.windowSize >>10),
2937  (U32)(zds->maxWindowSize >> 10) );
2938  zds->fParams.windowSize = MAX(zds->fParams.windowSize, 1U << ZSTD_WINDOWLOG_ABSOLUTEMIN);
2939  if (zds->fParams.windowSize > zds->maxWindowSize) return ERROR(frameParameter_windowTooLarge);
2940 
2941  /* Adapt buffer sizes to frame header instructions */
2942  { size_t const neededInBuffSize = MAX(zds->fParams.blockSizeMax, 4 /* frame checksum */);
2943  size_t const neededOutBuffSize = ZSTD_decodingBufferSize_min(zds->fParams.windowSize, zds->fParams.frameContentSize);
2944  if ((zds->inBuffSize < neededInBuffSize) || (zds->outBuffSize < neededOutBuffSize)) {
2945  size_t const bufferSize = neededInBuffSize + neededOutBuffSize;
2946  DEBUGLOG(4, "inBuff : from %u to %u",
2947  (U32)zds->inBuffSize, (U32)neededInBuffSize);
2948  DEBUGLOG(4, "outBuff : from %u to %u",
2949  (U32)zds->outBuffSize, (U32)neededOutBuffSize);
2950  if (zds->staticSize) { /* static DCtx */
2951  DEBUGLOG(4, "staticSize : %u", (U32)zds->staticSize);
2952  assert(zds->staticSize >= sizeof(ZSTD_DCtx)); /* controlled at init */
2953  if (bufferSize > zds->staticSize - sizeof(ZSTD_DCtx))
2954  return ERROR(memory_allocation);
2955  } else {
2956  ZSTD_free(zds->inBuff, zds->customMem);
2957  zds->inBuffSize = 0;
2958  zds->outBuffSize = 0;
2959  zds->inBuff = (char*)ZSTD_malloc(bufferSize, zds->customMem);
2960  if (zds->inBuff == NULL) return ERROR(memory_allocation);
2961  }
2962  zds->inBuffSize = neededInBuffSize;
2963  zds->outBuff = zds->inBuff + zds->inBuffSize;
2964  zds->outBuffSize = neededOutBuffSize;
2965  } }
2966  zds->streamStage = zdss_read;
2967  /* fall-through */
2968 
2969  case zdss_read:
2970  DEBUGLOG(5, "stage zdss_read");
2971  { size_t const neededInSize = ZSTD_nextSrcSizeToDecompress(zds);
2972  DEBUGLOG(5, "neededInSize = %u", (U32)neededInSize);
2973  if (neededInSize==0) { /* end of frame */
2974  zds->streamStage = zdss_init;
2975  someMoreWork = 0;
2976  break;
2977  }
2978  if ((size_t)(iend-ip) >= neededInSize) { /* decode directly from src */
2979  int const isSkipFrame = ZSTD_isSkipFrame(zds);
2980  size_t const decodedSize = ZSTD_decompressContinue(zds,
2981  zds->outBuff + zds->outStart, (isSkipFrame ? 0 : zds->outBuffSize - zds->outStart),
2982  ip, neededInSize);
2983  if (ZSTD_isError(decodedSize)) return decodedSize;
2984  ip += neededInSize;
2985  if (!decodedSize && !isSkipFrame) break; /* this was just a header */
2986  zds->outEnd = zds->outStart + decodedSize;
2987  zds->streamStage = zdss_flush;
2988  break;
2989  } }
2990  if (ip==iend) { someMoreWork = 0; break; } /* no more input */
2991  zds->streamStage = zdss_load;
2992  /* fall-through */
2993 
2994  case zdss_load:
2995  { size_t const neededInSize = ZSTD_nextSrcSizeToDecompress(zds);
2996  size_t const toLoad = neededInSize - zds->inPos;
2997  int const isSkipFrame = ZSTD_isSkipFrame(zds);
2998  size_t loadedSize;
2999  if (isSkipFrame) {
3000  loadedSize = MIN(toLoad, (size_t)(iend-ip));
3001  } else {
3002  if (toLoad > zds->inBuffSize - zds->inPos) return ERROR(corruption_detected); /* should never happen */
3003  loadedSize = ZSTD_limitCopy(zds->inBuff + zds->inPos, toLoad, ip, iend-ip);
3004  }
3005  ip += loadedSize;
3006  zds->inPos += loadedSize;
3007  if (loadedSize < toLoad) { someMoreWork = 0; break; } /* not enough input, wait for more */
3008 
3009  /* decode loaded input */
3010  { size_t const decodedSize = ZSTD_decompressContinue(zds,
3011  zds->outBuff + zds->outStart, zds->outBuffSize - zds->outStart,
3012  zds->inBuff, neededInSize);
3013  if (ZSTD_isError(decodedSize)) return decodedSize;
3014  zds->inPos = 0; /* input is consumed */
3015  if (!decodedSize && !isSkipFrame) { zds->streamStage = zdss_read; break; } /* this was just a header */
3016  zds->outEnd = zds->outStart + decodedSize;
3017  } }
3018  zds->streamStage = zdss_flush;
3019  /* fall-through */
3020 
3021  case zdss_flush:
3022  { size_t const toFlushSize = zds->outEnd - zds->outStart;
3023  size_t const flushedSize = ZSTD_limitCopy(op, oend-op, zds->outBuff + zds->outStart, toFlushSize);
3024  op += flushedSize;
3025  zds->outStart += flushedSize;
3026  if (flushedSize == toFlushSize) { /* flush completed */
3027  zds->streamStage = zdss_read;
3028  if ( (zds->outBuffSize < zds->fParams.frameContentSize)
3029  && (zds->outStart + zds->fParams.blockSizeMax > zds->outBuffSize) ) {
3030  DEBUGLOG(5, "restart filling outBuff from beginning (left:%i, needed:%u)",
3031  (int)(zds->outBuffSize - zds->outStart),
3032  (U32)zds->fParams.blockSizeMax);
3033  zds->outStart = zds->outEnd = 0;
3034  }
3035  break;
3036  } }
3037  /* cannot complete flush */
3038  someMoreWork = 0;
3039  break;
3040 
3041  default: return ERROR(GENERIC); /* impossible */
3042  } }
3043 
3044  /* result */
3045  input->pos = (size_t)(ip - (const char*)(input->src));
3046  output->pos = (size_t)(op - (char*)(output->dst));
3047  if ((ip==istart) && (op==ostart)) { /* no forward progress */
3048  zds->noForwardProgress ++;
3050  if (op==oend) return ERROR(dstSize_tooSmall);
3051  if (ip==iend) return ERROR(srcSize_wrong);
3052  assert(0);
3053  }
3054  } else {
3055  zds->noForwardProgress = 0;
3056  }
3057  { size_t nextSrcSizeHint = ZSTD_nextSrcSizeToDecompress(zds);
3058  if (!nextSrcSizeHint) { /* frame fully decoded */
3059  if (zds->outEnd == zds->outStart) { /* output fully flushed */
3060  if (zds->hostageByte) {
3061  if (input->pos >= input->size) {
3062  /* can't release hostage (not present) */
3063  zds->streamStage = zdss_read;
3064  return 1;
3065  }
3066  input->pos++; /* release hostage */
3067  } /* zds->hostageByte */
3068  return 0;
3069  } /* zds->outEnd == zds->outStart */
3070  if (!zds->hostageByte) { /* output not fully flushed; keep last byte as hostage; will be released when all output is flushed */
3071  input->pos--; /* note : pos > 0, otherwise, impossible to finish reading last block */
3072  zds->hostageByte=1;
3073  }
3074  return 1;
3075  } /* nextSrcSizeHint==0 */
3076  nextSrcSizeHint += ZSTD_blockHeaderSize * (ZSTD_nextInputType(zds) == ZSTDnit_block); /* preload header of next block */
3077  assert(zds->inPos <= nextSrcSizeHint);
3078  nextSrcSizeHint -= zds->inPos; /* part already loaded*/
3079  return nextSrcSizeHint;
3080  }
3081 }
3082 
3083 
3085 {
3086  return ZSTD_decompressStream(dctx, output, input);
3087 }
3088 
3090  ZSTD_DCtx* dctx,
3091  void* dst, size_t dstCapacity, size_t* dstPos,
3092  const void* src, size_t srcSize, size_t* srcPos)
3093 {
3094  ZSTD_outBuffer output = { dst, dstCapacity, *dstPos };
3095  ZSTD_inBuffer input = { src, srcSize, *srcPos };
3096  /* ZSTD_compress_generic() will check validity of dstPos and srcPos */
3097  size_t const cErr = ZSTD_decompress_generic(dctx, &output, &input);
3098  *dstPos = output.pos;
3099  *srcPos = input.pos;
3100  return cErr;
3101 }
3102 
3104 {
3105  (void)ZSTD_initDStream(dctx);
3106  dctx->format = ZSTD_f_zstd1;
3108 }
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble * u
Definition: glfuncs.h:240
const void * previousDstEnd
#define WILDCOPY_OVERLENGTH
unsigned short U16
Definition: mem.h:72
const BYTE * dictEnd
#define ZSTD_NO_FORWARD_PROGRESS_MAX
symbolEncodingType_e
Definition: zstd_internal.h:92
ZSTD_dStreamStage
static const U32 OF_base[MaxOff+1]
#define memmove(s1, s2, n)
Definition: mkisofs.h:881
#define max(a, b)
Definition: svc.c:63
size_t(* ZSTD_decompressSequences_t)(ZSTD_DCtx *dctx, void *dst, size_t maxDstSize, const void *seqStart, size_t seqSize, int nbSeq, const ZSTD_longOffset_e isLongOffset)
#define SEQSYMBOL_TABLE_SIZE(log)
size_t ZSTD_DCtx_refPrefix_advanced(ZSTD_DCtx *dctx, const void *prefix, size_t prefixSize, ZSTD_dictContentType_e dictContentType)
blockType_e bType
BIT_DStream_t DStream
size_t ZSTD_sizeof_DCtx(const ZSTD_DCtx *dctx)
static UCHAR ULONG UCHAR ULONG UCHAR * output
Definition: bcrypt.c:29
static const U32 OF_bits[MaxOff+1]
ZSTD_DCtx * ZSTD_createDCtx(void)
const ZSTD_DDict * ZSTD_initStaticDDict(void *sBuffer, size_t sBufferSize, const void *dict, size_t dictSize, ZSTD_dictLoadMethod_e dictLoadMethod, ZSTD_dictContentType_e dictContentType)
unsigned ZSTD_getDictID_fromDDict(const ZSTD_DDict *ddict)
struct png_info_def **typedef void(__cdecl typeof(png_destroy_read_struct))(struct png_struct_def **
Definition: typeof.h:49
#define MaxSeq
struct ZSTD_DDict_s ZSTD_DDict
Definition: zstd.h:248
static void ZSTD_copy8(void *dst, const void *src)
#define ZSTD_CONTENTSIZE_UNKNOWN
Definition: zstd.h:136
ZSTD_ErrorCode ZSTD_getErrorCode(size_t code)
Definition: zstd_common.c:43
#define ADVANCED_SEQS
_Tp _STLP_CALL norm(const complex< _Tp > &__z)
Definition: _complex.h:741
#define LL_DEFAULTNORMLOG
const void * dictContent
size_t ZSTD_initDStream_usingDict(ZSTD_DStream *zds, const void *dict, size_t dictSize)
static size_t ZSTD_startingInputLength(ZSTD_format_e format)
size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx *dctx, const void *src, size_t srcSize)
ZSTD_nextInputType_e ZSTD_nextInputType(ZSTD_DCtx *dctx)
size_t ZSTD_DCtx_setFormat(ZSTD_DCtx *dctx, ZSTD_format_e format)
U32 rep[ZSTD_REP_NUM]
ZSTD_DStream * ZSTD_initStaticDStream(void *workspace, size_t workspaceSize)
blockType_e blockType
#define TARGET_ATTRIBUTE(target)
Definition: compiler.h:73
ZSTD_frameHeader fParams
Definition: match.c:28
size_t HUF_readDTableX2_wksp(HUF_DTable *DTable, const void *src, size_t srcSize, void *workSpace, size_t wkspSize)
size_t ZSTD_frameHeaderSize(const void *src, size_t srcSize)
#define ERROR(name)
Definition: error_private.h:53
ZSTD_dStreamStage streamStage
size_t FSE_readNCount(short *normalizedCounter, unsigned *maxSVPtr, unsigned *tableLogPtr, const void *headerBuffer, size_t hbSize)
size_t ZSTD_DCtx_refPrefix(ZSTD_DCtx *dctx, const void *prefix, size_t prefixSize)
void ZSTD_free(void *ptr, ZSTD_customMem customMem)
Definition: zstd_common.c:68
static int ZSTD_isSkipFrame(ZSTD_DCtx *dctx)
static const U32 LL_bits[MaxLL+1]
#define MaxFSELog
FORCE_INLINE_TEMPLATE size_t ZSTD_decompressSequences_body(ZSTD_DCtx *dctx, void *dst, size_t maxDstSize, const void *seqStart, size_t seqSize, int nbSeq, const ZSTD_longOffset_e isLongOffset)
MEM_STATIC U32 MEM_readLE32(const void *memPtr)
Definition: mem.h:273
blockType_e
Definition: zstd_internal.h:86
ZSTD_entropyDTables_t entropy
struct XXH64_state_s XXH64_state_t
Definition: xxhash.h:183
#define U(x)
Definition: wordpad.c:44
GLintptr offset
Definition: glext.h:5920
const ZSTD_seqSymbol * OFTptr
BYTE litBuffer[ZSTD_BLOCKSIZE_MAX+WILDCOPY_OVERLENGTH]
const BYTE * prefixStart
#define ZSTD_WINDOWLOG_ABSOLUTEMIN
Definition: zstd_internal.h:77
#define OF_DEFAULTNORMLOG
unsigned int U32
Definition: mem.h:77
size_t ZSTD_decompressBegin(ZSTD_DCtx *dctx)
#define ZSTD_MAXWINDOWSIZE_DEFAULT
XXH64_state_t xxhState
MEM_STATIC size_t BIT_initDStream(BIT_DStream_t *bitD, const void *srcBuffer, size_t srcSize)
Definition: bitstream.h:287
u32_t magic(void)
GLuint GLuint GLsizei GLenum type
Definition: gl.h:1545
#define assert(x)
Definition: debug.h:53
MEM_STATIC unsigned MEM_32bits(void)
Definition: mem.h:110
#define LONG_OFFSETS_MAX_EXTRA_BITS_32
GLuint buffer
Definition: glext.h:5915
static const ZSTD_seqSymbol OF_defaultDTable[(1<< OF_DEFAULTNORMLOG)+1]
static size_t ZSTD_buildSeqTable(ZSTD_seqSymbol *DTableSpace, const ZSTD_seqSymbol **DTablePtr, symbolEncodingType_e type, U32 max, U32 maxLog, const void *src, size_t srcSize, const U32 *baseValue, const U32 *nbAdditionalBits, const ZSTD_seqSymbol *defaultTable, U32 flagRepeatTable, int ddictIsCold, int nbSeq)
#define PREFETCH(ptr)
Definition: compiler.h:108
size_t ZSTD_setDStreamParameter(ZSTD_DStream *dctx, ZSTD_DStreamParameter_e paramType, unsigned paramValue)
ZSTD_seqSymbol OFTable[SEQSYMBOL_TABLE_SIZE(OffFSELog)]
size_t ZSTD_sizeof_DStream(const ZSTD_DStream *dctx)
static size_t ZSTD_refDictContent(ZSTD_DCtx *dctx, const void *dict, size_t dictSize)
static size_t ZSTD_decompressMultiFrame(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const void *dict, size_t dictSize, const ZSTD_DDict *ddict)
MEM_STATIC ZSTD_cpuid_t ZSTD_cpuid(void)
Definition: cpu.h:34
ZSTD_DStream * ZSTD_createDStream(void)
ZSTD_DCtx * ZSTD_initStaticDCtx(void *workspace, size_t workspaceSize)
unsigned ZSTD_getDictID_fromFrame(const void *src, size_t srcSize)
static const U32 ML_base[MaxML+1]
static void ZSTD_checkContinuity(ZSTD_DCtx *dctx, const void *dst)
const void * dictEnd
MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t *bitD)
Definition: bitstream.h:414
ZSTD_format_e format
ZSTD_fseState stateOffb
MEM_STATIC U64 MEM_readLE64(const void *memPtr)
Definition: mem.h:289
MEM_STATIC unsigned MEM_64bits(void)
Definition: mem.h:111
GLint GLint GLsizei GLsizei GLsizei GLint GLenum format
Definition: gl.h:1546
static unsigned ZSTD_getLongOffsetsShare(const ZSTD_seqSymbol *offTable)
ZSTD_fseState stateML
MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t *bitD, unsigned nbBits)
XXH_PUBLIC_API unsigned long long XXH64_digest(const XXH64_state_t *state_in)
Definition: xxhash.c:844
T MIN(T a, T b)
Definition: polytest.cpp:79
size_t ZSTD_decompressBegin_usingDict(ZSTD_DCtx *dctx, const void *dict, size_t dictSize)
#define ZSTD_STATIC_ASSERT(c)
Definition: zstd_internal.h:43
size_t litLength
#define CHECK_E(f, e)
Definition: zstd_internal.h:54
#define DEBUGLOG(l,...)
Definition: debug.h:115
static const size_t ZSTD_fcs_fieldSize[4]
Definition: zstd_internal.h:79
const void * virtualStart
MEM_STATIC unsigned BIT_highbit32(U32 val)
Definition: bitstream.h:156
static size_t ZSTD_decompressBlock_internal(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const int frame)
ZSTD_longOffset_e
static size_t ZSTD_DDictDictSize(const ZSTD_DDict *ddict)
const ZSTD_seqSymbol * table
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx *dctx)
size_t HUF_decompress4X_usingDTable_bmi2(void *dst, size_t maxDstSize, const void *cSrc, size_t cSrcSize, const HUF_DTable *DTable, int bmi2)
static const size_t ZSTD_blockHeaderSize
Definition: zstd_internal.h:85
const void * prefixStart
GLuint base
Definition: 3dtext.c:35
void * legacyContext
size_t ZSTD_estimateDDictSize(size_t dictSize, ZSTD_dictLoadMethod_e dictLoadMethod)
FORCE_NOINLINE size_t ZSTD_execSequenceLast7(BYTE *op, BYTE *const oend, seq_t sequence, const BYTE **litPtr, const BYTE *const litLimit, const BYTE *const base, const BYTE *const vBase, const BYTE *const dictEnd)
U32 workspace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32]
size_t ZSTD_decompressDCtx(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
size_t ZSTD_getFrameHeader_advanced(ZSTD_frameHeader *zfhPtr, const void *src, size_t srcSize, ZSTD_format_e format)
size_t ZSTD_estimateDCtxSize(void)
int ip[4]
Definition: rtl.c:1176
static PVOID ptr
Definition: dispmode.c:27
static const void * ZSTD_DDictDictContent(const ZSTD_DDict *ddict)
static void ZSTD_copy4(void *dst, const void *src)
size_t ZSTD_freeDStream(ZSTD_DStream *zds)
size_t ZSTD_DCtx_loadDictionary_advanced(ZSTD_DCtx *dctx, const void *dict, size_t dictSize, ZSTD_dictLoadMethod_e dictLoadMethod, ZSTD_dictContentType_e dictContentType)
#define HufLog
Definition: zstd_internal.h:91
size_t ZSTD_sizeof_DDict(const ZSTD_DDict *ddict)
ZSTD_DStream * ZSTD_createDStream_advanced(ZSTD_customMem customMem)
size_t ZSTD_decompressBegin_usingDDict(ZSTD_DCtx *dctx, const ZSTD_DDict *ddict)
smooth NULL
Definition: ftsmooth.c:416
size_t ZSTD_resetDStream(ZSTD_DStream *dctx)
#define offsetof(TYPE, MEMBER)
ZSTD_customMem customMem
MEM_STATIC void ZSTD_wildcopy(void *dst, const void *src, ptrdiff_t length)
static const U32 repStartValue[ZSTD_REP_NUM]
Definition: zstd_internal.h:64
static size_t ZSTD_decompress_insertDictionary(ZSTD_DCtx *dctx, const void *dict, size_t dictSize)
ZSTDLIB_API size_t ZSTD_insertBlock(ZSTD_DCtx *dctx, const void *blockStart, size_t blockSize)
#define MIN_SEQUENCES_SIZE
Definition: zstd_internal.h:88
size_t ZSTD_initDStream(ZSTD_DStream *zds)
FORCE_INLINE_TEMPLATE seq_t ZSTD_decodeSequence(seqState_t *seqState, const ZSTD_longOffset_e longOffsets)
#define CHECK_F(f)
Definition: fse_compress.c:661
#define MaxML
ZSTD_customMem cMem
struct match match
Definition: match.c:33
#define MLFSELog
#define PREFETCH_AREA(p, s)
Definition: compiler.h:114
size_t ZSTD_estimateDStreamSize(size_t windowSize)
BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX]
size_t ZSTD_decompress(void *dst, size_t dstCapacity, const void *src, size_t srcSize)
const ZSTD_seqSymbol * LLTptr
#define ULL(a, b)
Definition: format_msg.c:27
MEM_STATIC size_t ZSTD_limitCopy(void *dst, size_t dstCapacity, const void *src, size_t srcSize)
FORCE_INLINE_TEMPLATE size_t ZSTD_decompressSequencesLong_body(ZSTD_DCtx *dctx, void *dst, size_t maxDstSize, const void *seqStart, size_t seqSize, int nbSeq, const ZSTD_longOffset_e isLongOffset)
#define ML_DEFAULTNORMLOG
static void ZSTD_initFseState(ZSTD_fseState *DStatePtr, BIT_DStream_t *bitD, const ZSTD_seqSymbol *dt)
const ZSTD_DDict * ddict
FORCE_INLINE_TEMPLATE void ZSTD_updateFseState(ZSTD_fseState *DStatePtr, BIT_DStream_t *bitD)
static size_t ZSTD_decodeFrameHeader(ZSTD_DCtx *dctx, const void *src, size_t headerSize)
const ZSTD_seqSymbol * MLTptr
#define STOSEQ_MASK
MEM_STATIC U16 MEM_readLE16(const void *memPtr)
Definition: mem.h:241
__kernel_size_t size_t
Definition: linux.h:237
#define HUF_isError
size_t HUF_decompress4X_hufOnly_wksp_bmi2(HUF_DTable *dctx, void *dst, size_t dstSize, const void *cSrc, size_t cSrcSize, void *workSpace, size_t wkspSize, int bmi2)
static void ZSTD_buildFSETable(ZSTD_seqSymbol *dt, const short *normalizedCounter, unsigned maxSymbolValue, const U32 *baseValue, const U32 *nbAdditionalBits, unsigned tableLog)
size_t ZSTD_decompressStream(ZSTD_DStream *zds, ZSTD_outBuffer *output, ZSTD_inBuffer *input)
#define MEM_STATIC
Definition: mem.h:39
GLsizeiptr size
Definition: glext.h:5919
size_t ZSTD_decompress_generic(ZSTD_DCtx *dctx, ZSTD_outBuffer *output, ZSTD_inBuffer *input)
size_t HUF_decompress1X1_DCtx_wksp_bmi2(HUF_DTable *dctx, void *dst, size_t dstSize, const void *cSrc, size_t cSrcSize, void *workSpace, size_t wkspSize, int bmi2)
Definition: dhcpd.h:61
static void ZSTD_buildSeqTable_rle(ZSTD_seqSymbol *dt, U32 baseValue, U32 nbAddBits)
if(!(yy_init))
Definition: macro.lex.yy.c:714
ZSTD_entropyDTables_t entropy
ZSTD_seqSymbol MLTable[SEQSYMBOL_TABLE_SIZE(MLFSELog)]
XXH_PUBLIC_API XXH_errorcode XXH64_update(XXH64_state_t *state_in, const void *input, size_t len)
Definition: xxhash.c:780
size_t ZSTD_decompress_usingDDict(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const ZSTD_DDict *ddict)
GLenum GLuint GLenum GLsizei length
Definition: glext.h:5579
static size_t ZSTD_generateNxBytes(void *dst, size_t dstCapacity, BYTE value, size_t length)
ZSTD_dStage stage
#define OffFSELog
static size_t ZSTD_decompressFrame(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void **srcPtr, size_t *srcSizePtr)
HUF_DTable hufTable[HUF_DTABLE_SIZE(HufLog)]
size_t ZSTD_findFrameCompressedSize(const void *src, size_t srcSize)
size_t ZSTD_decompress_generic_simpleArgs(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, size_t *dstPos, const void *src, size_t srcSize, size_t *srcPos)
static const size_t ZSTD_did_fieldSize[4]
Definition: zstd_internal.h:80
#define FSE_isError
const BYTE * match
unsigned long long ZSTD_findDecompressedSize(const void *src, size_t srcSize)
#define STREAM_ACCUMULATOR_MIN_32
Definition: bitstream.h:62
static size_t ZSTD_decompressSequences_default(ZSTD_DCtx *dctx, void *dst, size_t maxDstSize, const void *seqStart, size_t seqSize, int nbSeq, const ZSTD_longOffset_e isLongOffset)
#define STREAM_ACCUMULATOR_MIN_64
Definition: bitstream.h:63
ZSTD_DDict * ddictLocal
int ret
unsigned bitsConsumed
Definition: bitstream.h:110
static struct message * sequence
Definition: subclass.c:48
size_t ZSTD_getFrameHeader(ZSTD_frameHeader *zfhPtr, const void *src, size_t srcSize)
ZSTD_fseState stateLL
ZSTD_DDict * ZSTD_createDDict_advanced(const void *dict, size_t dictSize, ZSTD_dictLoadMethod_e dictLoadMethod, ZSTD_dictContentType_e dictContentType, ZSTD_customMem customMem)
size_t matchLength
#define MIN_CBLOCK_SIZE
Definition: zstd_internal.h:89
#define FORCE_INLINE_TEMPLATE
Definition: compiler.h:37
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
unsigned char BYTE
Definition: mem.h:68
GLdouble s
Definition: gl.h:2039
size_t ZSTD_freeDCtx(ZSTD_DCtx *dctx)
#define LONGNBSEQ
Definition: zstd_internal.h:94
GLenum src
Definition: glext.h:6340
#define err(...)
void * ZSTD_malloc(size_t size, ZSTD_customMem customMem)
Definition: zstd_common.c:54
static size_t ZSTD_setRleBlock(void *dst, size_t dstCapacity, const void *src, size_t srcSize, size_t regenSize)
static struct msg_sequence * sequences[NUM_MSG_SEQUENCES]
Definition: button.c:53
static void ZSTD_initDCtx_internal(ZSTD_DCtx *dctx)
unsigned ZSTD_isFrame(const void *buffer, size_t size)
T MAX(T a, T b)
Definition: polytest.cpp:85
#define STREAM_ACCUMULATOR_MIN
Definition: bitstream.h:64
size_t ZSTD_initDStream_usingDDict(ZSTD_DStream *dctx, const ZSTD_DDict *ddict)
size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx *dctx, int *nbSeqPtr, const void *src, size_t srcSize)
#define MaxOff
U32 previousLegacyVersion
static size_t ZSTD_decompressSequencesLong(ZSTD_DCtx *dctx, void *dst, size_t maxDstSize, const void *seqStart, size_t seqSize, int nbSeq, const ZSTD_longOffset_e isLongOffset)
#define ZSTD_isError
size_t ZSTD_DStreamOutSize(void)
static size_t ZSTD_initDDict_internal(ZSTD_DDict *ddict, const void *dict, size_t dictSize, ZSTD_dictLoadMethod_e dictLoadMethod, ZSTD_dictContentType_e dictContentType)
ZSTD_DCtx * ZSTD_createDCtx_advanced(ZSTD_customMem customMem)
size_t ZSTD_decompressContinue(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
DWORD hint
Definition: vfdcmd.c:88
GLenum GLenum GLenum input
Definition: glext.h:9031
MEM_STATIC size_t BIT_readBits(BIT_DStream_t *bitD, unsigned nbBits)
void ZSTD_DCtx_reset(ZSTD_DCtx *dctx)
static const ZSTD_seqSymbol LL_defaultDTable[(1<< LL_DEFAULTNORMLOG)+1]
static calc_node_t temp
Definition: rpn_ieee.c:38
unsigned long long U64
Definition: mem.h:81
size_t outBuffSize
ZSTD_DDict * ZSTD_createDDict(const void *dict, size_t dictSize)
#define STORED_SEQS
#define ZSTD_FRAMEIDSIZE
Definition: zstd_internal.h:82
size_t ZSTD_DStreamInSize(void)
HINT_INLINE size_t ZSTD_execSequence(BYTE *op, BYTE *const oend, seq_t sequence, const BYTE **litPtr, const BYTE *const litLimit, const BYTE *const prefixStart, const BYTE *const virtualStart, const BYTE *const dictEnd)
size_t ZSTD_estimateDStreamSize_fromFrame(const void *src, size_t srcSize)
ZSTD_seqSymbol LLTable[SEQSYMBOL_TABLE_SIZE(LLFSELog)]
size_t ZSTD_DCtx_refDDict(ZSTD_DCtx *dctx, const ZSTD_DDict *ddict)
GLenum GLenum dst
Definition: glext.h:6340
static size_t ZSTD_loadEntropy_inDDict(ZSTD_DDict *ddict, ZSTD_dictContentType_e dictContentType)
static const U32 ML_bits[MaxML+1]
struct ZSTD_DCtx_s ZSTD_DCtx
Definition: zstd.h:182
size_t prevOffset[ZSTD_REP_NUM]
const BYTE * litPtr
__kernel_ptrdiff_t ptrdiff_t
Definition: linux.h:247
unsigned long long ZSTD_getDecompressedSize(const void *src, size_t srcSize)
ZSTD_DDict * ZSTD_createDDict_byReference(const void *dictBuffer, size_t dictSize)
#define MaxLL
unsigned long long ZSTD_getFrameContentSize(const void *src, size_t srcSize)
static size_t ZSTD_decompressSequences(ZSTD_DCtx *dctx, void *dst, size_t maxDstSize, const void *seqStart, size_t seqSize, int nbSeq, const ZSTD_longOffset_e isLongOffset)
size_t ZSTD_DCtx_loadDictionary(ZSTD_DCtx *dctx, const void *dict, size_t dictSize)
static size_t ZSTD_copyRawBlock(void *dst, size_t dstCapacity, const void *src, size_t srcSize)
#define MINMATCH
Definition: zstd_internal.h:96
size_t HUF_decompress1X_usingDTable_bmi2(void *dst, size_t maxDstSize, const void *cSrc, size_t cSrcSize, const HUF_DTable *DTable, int bmi2)
size_t ZSTD_DCtx_loadDictionary_byReference(ZSTD_DCtx *dctx, const void *dict, size_t dictSize)
GLuint res
Definition: glext.h:9613
signed short S16
Definition: mem.h:73
size_t ZSTD_decodingBufferSize_min(unsigned long long windowSize, unsigned long long frameContentSize)
size_t ZSTD_DCtx_setMaxWindowSize(ZSTD_DCtx *dctx, size_t maxWindowSize)
size_t ZSTD_freeDDict(ZSTD_DDict *ddict)
#define const
Definition: zconf.h:230
#define LLFSELog
const HUF_DTable * HUFptr
size_t ZSTD_getcBlockSize(const void *src, size_t srcSize, blockProperties_t *bpPtr)
ZSTD_dStage
UINT op
Definition: effect.c:223
static size_t ZSTD_decompressSequencesLong_default(ZSTD_DCtx *dctx, void *dst, size_t maxDstSize, const void *seqStart, size_t seqSize, int nbSeq, const ZSTD_longOffset_e isLongOffset)
XXH_PUBLIC_API XXH_errorcode XXH64_reset(XXH64_state_t *statePtr, unsigned long long seed)
Definition: xxhash.c:592
#define HINT_INLINE
Definition: compiler.h:52
void ZSTD_copyDCtx(ZSTD_DCtx *dstDCtx, const ZSTD_DCtx *srcDCtx)
#define ZSTD_CONTENTSIZE_ERROR
Definition: zstd.h:137
#define KB
Definition: setuplib.h:52
static const U32 LL_base[MaxLL+1]
size_t offset
GLuint64EXT * result
Definition: glext.h:11304
#define memset(x, y, z)
Definition: compat.h:39
HINT_INLINE size_t ZSTD_execSequenceLong(BYTE *op, BYTE *const oend, seq_t sequence, const BYTE **litPtr, const BYTE *const litLimit, const BYTE *const prefixStart, const BYTE *const dictStart, const BYTE *const dictEnd)
size_t maxWindowSize
size_t ZSTD_decompress_usingDict(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const void *dict, size_t dictSize)
#define ZSTD_REP_NUM
Definition: zstd_internal.h:62
static size_t ZSTD_loadEntropy(ZSTD_entropyDTables_t *entropy, const void *const dict, size_t const dictSize)
#define FORCE_NOINLINE
Definition: compiler.h:62
static size_t ZSTD_frameHeaderSize_internal(const void *src, size_t srcSize, ZSTD_format_e format)
unsigned ZSTD_getDictID_fromDict(const void *dict, size_t dictSize)
MEM_STATIC U32 MEM_readLE24(const void *memPtr)
Definition: mem.h:262
#define ZSTDLIB_API
Definition: zstd.h:34
FORCE_INLINE_TEMPLATE seq_t ZSTD_decodeSequenceLong(seqState_t *seqState, ZSTD_longOffset_e const longOffsets)
size_t ZSTD_decompressBlock(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
static const ZSTD_seqSymbol ML_defaultDTable[(1<< ML_DEFAULTNORMLOG)+1]