ReactOS  0.4.15-dev-5455-g015cd25
zstd_decompress_block.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2016-2020, 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 /* zstd_decompress_block :
12  * this module takes care of decompressing _compressed_ block */
13 
14 /*-*******************************************************
15 * Dependencies
16 *********************************************************/
17 #include <string.h> /* memcpy, memmove, memset */
18 #include "compiler.h" /* prefetch */
19 #include "cpu.h" /* bmi2 */
20 #include "mem.h" /* low level memory routines */
21 #define FSE_STATIC_LINKING_ONLY
22 #include "fse.h"
23 #define HUF_STATIC_LINKING_ONLY
24 #include "huf.h"
25 #include "zstd_internal.h"
26 #include "zstd_decompress_internal.h" /* ZSTD_DCtx */
27 #include "zstd_ddict.h" /* ZSTD_DDictDictContent */
28 #include "zstd_decompress_block.h"
29 
30 /*_*******************************************************
31 * Macros
32 **********************************************************/
33 
34 /* These two optional macros force the use one way or another of the two
35  * ZSTD_decompressSequences implementations. You can't force in both directions
36  * at the same time.
37  */
38 #if defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
39  defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
40 #error "Cannot force the use of the short and the long ZSTD_decompressSequences variants!"
41 #endif
42 
43 
44 /*_*******************************************************
45 * Memory operations
46 **********************************************************/
47 static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
48 
49 
50 /*-*************************************************************
51  * Block decoding
52  ***************************************************************/
53 
56 size_t ZSTD_getcBlockSize(const void* src, size_t srcSize,
57  blockProperties_t* bpPtr)
58 {
59  RETURN_ERROR_IF(srcSize < ZSTD_blockHeaderSize, srcSize_wrong, "");
60 
61  { U32 const cBlockHeader = MEM_readLE24(src);
62  U32 const cSize = cBlockHeader >> 3;
63  bpPtr->lastBlock = cBlockHeader & 1;
64  bpPtr->blockType = (blockType_e)((cBlockHeader >> 1) & 3);
65  bpPtr->origSize = cSize; /* only useful for RLE */
66  if (bpPtr->blockType == bt_rle) return 1;
67  RETURN_ERROR_IF(bpPtr->blockType == bt_reserved, corruption_detected, "");
68  return cSize;
69  }
70 }
71 
72 
73 /* Hidden declaration for fullbench */
75  const void* src, size_t srcSize);
80  const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */
81 {
82  DEBUGLOG(5, "ZSTD_decodeLiteralsBlock");
83  RETURN_ERROR_IF(srcSize < MIN_CBLOCK_SIZE, corruption_detected, "");
84 
85  { const BYTE* const istart = (const BYTE*) src;
86  symbolEncodingType_e const litEncType = (symbolEncodingType_e)(istart[0] & 3);
87 
88  switch(litEncType)
89  {
90  case set_repeat:
91  DEBUGLOG(5, "set_repeat flag : re-using stats from previous compressed literals block");
92  RETURN_ERROR_IF(dctx->litEntropy==0, dictionary_corrupted, "");
93  /* fall-through */
94 
95  case set_compressed:
96  RETURN_ERROR_IF(srcSize < 5, corruption_detected, "srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for case 3");
97  { size_t lhSize, litSize, litCSize;
98  U32 singleStream=0;
99  U32 const lhlCode = (istart[0] >> 2) & 3;
100  U32 const lhc = MEM_readLE32(istart);
101  size_t hufSuccess;
102  switch(lhlCode)
103  {
104  case 0: case 1: default: /* note : default is impossible, since lhlCode into [0..3] */
105  /* 2 - 2 - 10 - 10 */
106  singleStream = !lhlCode;
107  lhSize = 3;
108  litSize = (lhc >> 4) & 0x3FF;
109  litCSize = (lhc >> 14) & 0x3FF;
110  break;
111  case 2:
112  /* 2 - 2 - 14 - 14 */
113  lhSize = 4;
114  litSize = (lhc >> 4) & 0x3FFF;
115  litCSize = lhc >> 18;
116  break;
117  case 3:
118  /* 2 - 2 - 18 - 18 */
119  lhSize = 5;
120  litSize = (lhc >> 4) & 0x3FFFF;
121  litCSize = (lhc >> 22) + ((size_t)istart[4] << 10);
122  break;
123  }
124  RETURN_ERROR_IF(litSize > ZSTD_BLOCKSIZE_MAX, corruption_detected, "");
125  RETURN_ERROR_IF(litCSize + lhSize > srcSize, corruption_detected, "");
126 
127  /* prefetch huffman table if cold */
128  if (dctx->ddictIsCold && (litSize > 768 /* heuristic */)) {
129  PREFETCH_AREA(dctx->HUFptr, sizeof(dctx->entropy.hufTable));
130  }
131 
132  if (litEncType==set_repeat) {
133  if (singleStream) {
134  hufSuccess = HUF_decompress1X_usingDTable_bmi2(
135  dctx->litBuffer, litSize, istart+lhSize, litCSize,
136  dctx->HUFptr, dctx->bmi2);
137  } else {
138  hufSuccess = HUF_decompress4X_usingDTable_bmi2(
139  dctx->litBuffer, litSize, istart+lhSize, litCSize,
140  dctx->HUFptr, dctx->bmi2);
141  }
142  } else {
143  if (singleStream) {
144 #if defined(HUF_FORCE_DECOMPRESS_X2)
145  hufSuccess = HUF_decompress1X_DCtx_wksp(
146  dctx->entropy.hufTable, dctx->litBuffer, litSize,
147  istart+lhSize, litCSize, dctx->workspace,
148  sizeof(dctx->workspace));
149 #else
150  hufSuccess = HUF_decompress1X1_DCtx_wksp_bmi2(
151  dctx->entropy.hufTable, dctx->litBuffer, litSize,
152  istart+lhSize, litCSize, dctx->workspace,
153  sizeof(dctx->workspace), dctx->bmi2);
154 #endif
155  } else {
156  hufSuccess = HUF_decompress4X_hufOnly_wksp_bmi2(
157  dctx->entropy.hufTable, dctx->litBuffer, litSize,
158  istart+lhSize, litCSize, dctx->workspace,
159  sizeof(dctx->workspace), dctx->bmi2);
160  }
161  }
162 
163  RETURN_ERROR_IF(HUF_isError(hufSuccess), corruption_detected, "");
164 
165  dctx->litPtr = dctx->litBuffer;
166  dctx->litSize = litSize;
167  dctx->litEntropy = 1;
168  if (litEncType==set_compressed) dctx->HUFptr = dctx->entropy.hufTable;
169  memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
170  return litCSize + lhSize;
171  }
172 
173  case set_basic:
174  { size_t litSize, lhSize;
175  U32 const lhlCode = ((istart[0]) >> 2) & 3;
176  switch(lhlCode)
177  {
178  case 0: case 2: default: /* note : default is impossible, since lhlCode into [0..3] */
179  lhSize = 1;
180  litSize = istart[0] >> 3;
181  break;
182  case 1:
183  lhSize = 2;
184  litSize = MEM_readLE16(istart) >> 4;
185  break;
186  case 3:
187  lhSize = 3;
188  litSize = MEM_readLE24(istart) >> 4;
189  break;
190  }
191 
192  if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */
193  RETURN_ERROR_IF(litSize+lhSize > srcSize, corruption_detected, "");
194  memcpy(dctx->litBuffer, istart+lhSize, litSize);
195  dctx->litPtr = dctx->litBuffer;
196  dctx->litSize = litSize;
197  memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
198  return lhSize+litSize;
199  }
200  /* direct reference into compressed stream */
201  dctx->litPtr = istart+lhSize;
202  dctx->litSize = litSize;
203  return lhSize+litSize;
204  }
205 
206  case set_rle:
207  { U32 const lhlCode = ((istart[0]) >> 2) & 3;
208  size_t litSize, lhSize;
209  switch(lhlCode)
210  {
211  case 0: case 2: default: /* note : default is impossible, since lhlCode into [0..3] */
212  lhSize = 1;
213  litSize = istart[0] >> 3;
214  break;
215  case 1:
216  lhSize = 2;
217  litSize = MEM_readLE16(istart) >> 4;
218  break;
219  case 3:
220  lhSize = 3;
221  litSize = MEM_readLE24(istart) >> 4;
222  RETURN_ERROR_IF(srcSize<4, corruption_detected, "srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4");
223  break;
224  }
225  RETURN_ERROR_IF(litSize > ZSTD_BLOCKSIZE_MAX, corruption_detected, "");
226  memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
227  dctx->litPtr = dctx->litBuffer;
228  dctx->litSize = litSize;
229  return lhSize+1;
230  }
231  default:
232  RETURN_ERROR(corruption_detected, "impossible");
233  }
234  }
235 }
236 
237 /* Default FSE distribution tables.
238  * These are pre-calculated FSE decoding tables using default distributions as defined in specification :
239  * https://github.com/facebook/zstd/blob/master/doc/zstd_compression_format.md#default-distributions
240  * They were generated programmatically with following method :
241  * - start from default distributions, present in /lib/common/zstd_internal.h
242  * - generate tables normally, using ZSTD_buildFSETable()
243  * - printout the content of tables
244  * - pretify output, report below, test with fuzzer to ensure it's correct */
245 
246 /* Default FSE distribution table for Literal Lengths */
247 static const ZSTD_seqSymbol LL_defaultDTable[(1<<LL_DEFAULTNORMLOG)+1] = {
248  { 1, 1, 1, LL_DEFAULTNORMLOG}, /* header : fastMode, tableLog */
249  /* nextState, nbAddBits, nbBits, baseVal */
250  { 0, 0, 4, 0}, { 16, 0, 4, 0},
251  { 32, 0, 5, 1}, { 0, 0, 5, 3},
252  { 0, 0, 5, 4}, { 0, 0, 5, 6},
253  { 0, 0, 5, 7}, { 0, 0, 5, 9},
254  { 0, 0, 5, 10}, { 0, 0, 5, 12},
255  { 0, 0, 6, 14}, { 0, 1, 5, 16},
256  { 0, 1, 5, 20}, { 0, 1, 5, 22},
257  { 0, 2, 5, 28}, { 0, 3, 5, 32},
258  { 0, 4, 5, 48}, { 32, 6, 5, 64},
259  { 0, 7, 5, 128}, { 0, 8, 6, 256},
260  { 0, 10, 6, 1024}, { 0, 12, 6, 4096},
261  { 32, 0, 4, 0}, { 0, 0, 4, 1},
262  { 0, 0, 5, 2}, { 32, 0, 5, 4},
263  { 0, 0, 5, 5}, { 32, 0, 5, 7},
264  { 0, 0, 5, 8}, { 32, 0, 5, 10},
265  { 0, 0, 5, 11}, { 0, 0, 6, 13},
266  { 32, 1, 5, 16}, { 0, 1, 5, 18},
267  { 32, 1, 5, 22}, { 0, 2, 5, 24},
268  { 32, 3, 5, 32}, { 0, 3, 5, 40},
269  { 0, 6, 4, 64}, { 16, 6, 4, 64},
270  { 32, 7, 5, 128}, { 0, 9, 6, 512},
271  { 0, 11, 6, 2048}, { 48, 0, 4, 0},
272  { 16, 0, 4, 1}, { 32, 0, 5, 2},
273  { 32, 0, 5, 3}, { 32, 0, 5, 5},
274  { 32, 0, 5, 6}, { 32, 0, 5, 8},
275  { 32, 0, 5, 9}, { 32, 0, 5, 11},
276  { 32, 0, 5, 12}, { 0, 0, 6, 15},
277  { 32, 1, 5, 18}, { 32, 1, 5, 20},
278  { 32, 2, 5, 24}, { 32, 2, 5, 28},
279  { 32, 3, 5, 40}, { 32, 4, 5, 48},
280  { 0, 16, 6,65536}, { 0, 15, 6,32768},
281  { 0, 14, 6,16384}, { 0, 13, 6, 8192},
282 }; /* LL_defaultDTable */
283 
284 /* Default FSE distribution table for Offset Codes */
285 static const ZSTD_seqSymbol OF_defaultDTable[(1<<OF_DEFAULTNORMLOG)+1] = {
286  { 1, 1, 1, OF_DEFAULTNORMLOG}, /* header : fastMode, tableLog */
287  /* nextState, nbAddBits, nbBits, baseVal */
288  { 0, 0, 5, 0}, { 0, 6, 4, 61},
289  { 0, 9, 5, 509}, { 0, 15, 5,32765},
290  { 0, 21, 5,2097149}, { 0, 3, 5, 5},
291  { 0, 7, 4, 125}, { 0, 12, 5, 4093},
292  { 0, 18, 5,262141}, { 0, 23, 5,8388605},
293  { 0, 5, 5, 29}, { 0, 8, 4, 253},
294  { 0, 14, 5,16381}, { 0, 20, 5,1048573},
295  { 0, 2, 5, 1}, { 16, 7, 4, 125},
296  { 0, 11, 5, 2045}, { 0, 17, 5,131069},
297  { 0, 22, 5,4194301}, { 0, 4, 5, 13},
298  { 16, 8, 4, 253}, { 0, 13, 5, 8189},
299  { 0, 19, 5,524285}, { 0, 1, 5, 1},
300  { 16, 6, 4, 61}, { 0, 10, 5, 1021},
301  { 0, 16, 5,65533}, { 0, 28, 5,268435453},
302  { 0, 27, 5,134217725}, { 0, 26, 5,67108861},
303  { 0, 25, 5,33554429}, { 0, 24, 5,16777213},
304 }; /* OF_defaultDTable */
305 
306 
307 /* Default FSE distribution table for Match Lengths */
308 static const ZSTD_seqSymbol ML_defaultDTable[(1<<ML_DEFAULTNORMLOG)+1] = {
309  { 1, 1, 1, ML_DEFAULTNORMLOG}, /* header : fastMode, tableLog */
310  /* nextState, nbAddBits, nbBits, baseVal */
311  { 0, 0, 6, 3}, { 0, 0, 4, 4},
312  { 32, 0, 5, 5}, { 0, 0, 5, 6},
313  { 0, 0, 5, 8}, { 0, 0, 5, 9},
314  { 0, 0, 5, 11}, { 0, 0, 6, 13},
315  { 0, 0, 6, 16}, { 0, 0, 6, 19},
316  { 0, 0, 6, 22}, { 0, 0, 6, 25},
317  { 0, 0, 6, 28}, { 0, 0, 6, 31},
318  { 0, 0, 6, 34}, { 0, 1, 6, 37},
319  { 0, 1, 6, 41}, { 0, 2, 6, 47},
320  { 0, 3, 6, 59}, { 0, 4, 6, 83},
321  { 0, 7, 6, 131}, { 0, 9, 6, 515},
322  { 16, 0, 4, 4}, { 0, 0, 4, 5},
323  { 32, 0, 5, 6}, { 0, 0, 5, 7},
324  { 32, 0, 5, 9}, { 0, 0, 5, 10},
325  { 0, 0, 6, 12}, { 0, 0, 6, 15},
326  { 0, 0, 6, 18}, { 0, 0, 6, 21},
327  { 0, 0, 6, 24}, { 0, 0, 6, 27},
328  { 0, 0, 6, 30}, { 0, 0, 6, 33},
329  { 0, 1, 6, 35}, { 0, 1, 6, 39},
330  { 0, 2, 6, 43}, { 0, 3, 6, 51},
331  { 0, 4, 6, 67}, { 0, 5, 6, 99},
332  { 0, 8, 6, 259}, { 32, 0, 4, 4},
333  { 48, 0, 4, 4}, { 16, 0, 4, 5},
334  { 32, 0, 5, 7}, { 32, 0, 5, 8},
335  { 32, 0, 5, 10}, { 32, 0, 5, 11},
336  { 0, 0, 6, 14}, { 0, 0, 6, 17},
337  { 0, 0, 6, 20}, { 0, 0, 6, 23},
338  { 0, 0, 6, 26}, { 0, 0, 6, 29},
339  { 0, 0, 6, 32}, { 0, 16, 6,65539},
340  { 0, 15, 6,32771}, { 0, 14, 6,16387},
341  { 0, 13, 6, 8195}, { 0, 12, 6, 4099},
342  { 0, 11, 6, 2051}, { 0, 10, 6, 1027},
343 }; /* ML_defaultDTable */
344 
345 
346 static void ZSTD_buildSeqTable_rle(ZSTD_seqSymbol* dt, U32 baseValue, U32 nbAddBits)
347 {
348  void* ptr = dt;
349  ZSTD_seqSymbol_header* const DTableH = (ZSTD_seqSymbol_header*)ptr;
350  ZSTD_seqSymbol* const cell = dt + 1;
351 
352  DTableH->tableLog = 0;
353  DTableH->fastMode = 0;
354 
355  cell->nbBits = 0;
356  cell->nextState = 0;
357  assert(nbAddBits < 255);
358  cell->nbAdditionalBits = (BYTE)nbAddBits;
359  cell->baseValue = baseValue;
360 }
361 
362 
363 /* ZSTD_buildFSETable() :
364  * generate FSE decoding table for one symbol (ll, ml or off)
365  * cannot fail if input is valid =>
366  * all inputs are presumed validated at this stage */
367 void
368 ZSTD_buildFSETable(ZSTD_seqSymbol* dt,
369  const short* normalizedCounter, unsigned maxSymbolValue,
370  const U32* baseValue, const U32* nbAdditionalBits,
371  unsigned tableLog)
372 {
373  ZSTD_seqSymbol* const tableDecode = dt+1;
374  U16 symbolNext[MaxSeq+1];
375 
376  U32 const maxSV1 = maxSymbolValue + 1;
377  U32 const tableSize = 1 << tableLog;
378  U32 highThreshold = tableSize-1;
379 
380  /* Sanity Checks */
381  assert(maxSymbolValue <= MaxSeq);
382  assert(tableLog <= MaxFSELog);
383 
384  /* Init, lay down lowprob symbols */
385  { ZSTD_seqSymbol_header DTableH;
386  DTableH.tableLog = tableLog;
387  DTableH.fastMode = 1;
388  { S16 const largeLimit= (S16)(1 << (tableLog-1));
389  U32 s;
390  for (s=0; s<maxSV1; s++) {
391  if (normalizedCounter[s]==-1) {
392  tableDecode[highThreshold--].baseValue = s;
393  symbolNext[s] = 1;
394  } else {
395  if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
396  assert(normalizedCounter[s]>=0);
397  symbolNext[s] = (U16)normalizedCounter[s];
398  } } }
399  memcpy(dt, &DTableH, sizeof(DTableH));
400  }
401 
402  /* Spread symbols */
403  { U32 const tableMask = tableSize-1;
404  U32 const step = FSE_TABLESTEP(tableSize);
405  U32 s, position = 0;
406  for (s=0; s<maxSV1; s++) {
407  int i;
408  for (i=0; i<normalizedCounter[s]; i++) {
409  tableDecode[position].baseValue = s;
410  position = (position + step) & tableMask;
411  while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
412  } }
413  assert(position == 0); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
414  }
415 
416  /* Build Decoding table */
417  { U32 u;
418  for (u=0; u<tableSize; u++) {
419  U32 const symbol = tableDecode[u].baseValue;
420  U32 const nextState = symbolNext[symbol]++;
421  tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32(nextState) );
422  tableDecode[u].nextState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
423  assert(nbAdditionalBits[symbol] < 255);
424  tableDecode[u].nbAdditionalBits = (BYTE)nbAdditionalBits[symbol];
425  tableDecode[u].baseValue = baseValue[symbol];
426  } }
427 }
428 
429 
433 static size_t ZSTD_buildSeqTable(ZSTD_seqSymbol* DTableSpace, const ZSTD_seqSymbol** DTablePtr,
434  symbolEncodingType_e type, unsigned max, U32 maxLog,
435  const void* src, size_t srcSize,
436  const U32* baseValue, const U32* nbAdditionalBits,
437  const ZSTD_seqSymbol* defaultTable, U32 flagRepeatTable,
438  int ddictIsCold, int nbSeq)
439 {
440  switch(type)
441  {
442  case set_rle :
443  RETURN_ERROR_IF(!srcSize, srcSize_wrong, "");
444  RETURN_ERROR_IF((*(const BYTE*)src) > max, corruption_detected, "");
445  { U32 const symbol = *(const BYTE*)src;
446  U32 const baseline = baseValue[symbol];
447  U32 const nbBits = nbAdditionalBits[symbol];
448  ZSTD_buildSeqTable_rle(DTableSpace, baseline, nbBits);
449  }
450  *DTablePtr = DTableSpace;
451  return 1;
452  case set_basic :
453  *DTablePtr = defaultTable;
454  return 0;
455  case set_repeat:
456  RETURN_ERROR_IF(!flagRepeatTable, corruption_detected, "");
457  /* prefetch FSE table if used */
458  if (ddictIsCold && (nbSeq > 24 /* heuristic */)) {
459  const void* const pStart = *DTablePtr;
460  size_t const pSize = sizeof(ZSTD_seqSymbol) * (SEQSYMBOL_TABLE_SIZE(maxLog));
461  PREFETCH_AREA(pStart, pSize);
462  }
463  return 0;
464  case set_compressed :
465  { unsigned tableLog;
466  S16 norm[MaxSeq+1];
467  size_t const headerSize = FSE_readNCount(norm, &max, &tableLog, src, srcSize);
468  RETURN_ERROR_IF(FSE_isError(headerSize), corruption_detected, "");
469  RETURN_ERROR_IF(tableLog > maxLog, corruption_detected, "");
470  ZSTD_buildFSETable(DTableSpace, norm, max, baseValue, nbAdditionalBits, tableLog);
471  *DTablePtr = DTableSpace;
472  return headerSize;
473  }
474  default :
475  assert(0);
476  RETURN_ERROR(GENERIC, "impossible");
477  }
478 }
479 
480 size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr,
481  const void* src, size_t srcSize)
482 {
483  const BYTE* const istart = (const BYTE* const)src;
484  const BYTE* const iend = istart + srcSize;
485  const BYTE* ip = istart;
486  int nbSeq;
487  DEBUGLOG(5, "ZSTD_decodeSeqHeaders");
488 
489  /* check */
490  RETURN_ERROR_IF(srcSize < MIN_SEQUENCES_SIZE, srcSize_wrong, "");
491 
492  /* SeqHead */
493  nbSeq = *ip++;
494  if (!nbSeq) {
495  *nbSeqPtr=0;
496  RETURN_ERROR_IF(srcSize != 1, srcSize_wrong, "");
497  return 1;
498  }
499  if (nbSeq > 0x7F) {
500  if (nbSeq == 0xFF) {
501  RETURN_ERROR_IF(ip+2 > iend, srcSize_wrong, "");
502  nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2;
503  } else {
504  RETURN_ERROR_IF(ip >= iend, srcSize_wrong, "");
505  nbSeq = ((nbSeq-0x80)<<8) + *ip++;
506  }
507  }
508  *nbSeqPtr = nbSeq;
509 
510  /* FSE table descriptors */
511  RETURN_ERROR_IF(ip+1 > iend, srcSize_wrong, ""); /* minimum possible size: 1 byte for symbol encoding types */
512  { symbolEncodingType_e const LLtype = (symbolEncodingType_e)(*ip >> 6);
513  symbolEncodingType_e const OFtype = (symbolEncodingType_e)((*ip >> 4) & 3);
514  symbolEncodingType_e const MLtype = (symbolEncodingType_e)((*ip >> 2) & 3);
515  ip++;
516 
517  /* Build DTables */
518  { size_t const llhSize = ZSTD_buildSeqTable(dctx->entropy.LLTable, &dctx->LLTptr,
519  LLtype, MaxLL, LLFSELog,
520  ip, iend-ip,
521  LL_base, LL_bits,
522  LL_defaultDTable, dctx->fseEntropy,
523  dctx->ddictIsCold, nbSeq);
524  RETURN_ERROR_IF(ZSTD_isError(llhSize), corruption_detected, "ZSTD_buildSeqTable failed");
525  ip += llhSize;
526  }
527 
528  { size_t const ofhSize = ZSTD_buildSeqTable(dctx->entropy.OFTable, &dctx->OFTptr,
529  OFtype, MaxOff, OffFSELog,
530  ip, iend-ip,
531  OF_base, OF_bits,
532  OF_defaultDTable, dctx->fseEntropy,
533  dctx->ddictIsCold, nbSeq);
534  RETURN_ERROR_IF(ZSTD_isError(ofhSize), corruption_detected, "ZSTD_buildSeqTable failed");
535  ip += ofhSize;
536  }
537 
538  { size_t const mlhSize = ZSTD_buildSeqTable(dctx->entropy.MLTable, &dctx->MLTptr,
539  MLtype, MaxML, MLFSELog,
540  ip, iend-ip,
541  ML_base, ML_bits,
542  ML_defaultDTable, dctx->fseEntropy,
543  dctx->ddictIsCold, nbSeq);
544  RETURN_ERROR_IF(ZSTD_isError(mlhSize), corruption_detected, "ZSTD_buildSeqTable failed");
545  ip += mlhSize;
546  }
547  }
548 
549  return ip-istart;
550 }
551 
552 
553 typedef struct {
554  size_t litLength;
555  size_t matchLength;
556  size_t offset;
557  const BYTE* match;
558 } seq_t;
559 
560 typedef struct {
561  size_t state;
562  const ZSTD_seqSymbol* table;
563 } ZSTD_fseState;
564 
565 typedef struct {
566  BIT_DStream_t DStream;
567  ZSTD_fseState stateLL;
568  ZSTD_fseState stateOffb;
569  ZSTD_fseState stateML;
570  size_t prevOffset[ZSTD_REP_NUM];
571  const BYTE* prefixStart;
572  const BYTE* dictEnd;
573  size_t pos;
574 } seqState_t;
575 
583 HINT_INLINE void ZSTD_overlapCopy8(BYTE** op, BYTE const** ip, size_t offset) {
584  assert(*ip <= *op);
585  if (offset < 8) {
586  /* close range match, overlap */
587  static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
588  static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* subtracted */
589  int const sub2 = dec64table[offset];
590  (*op)[0] = (*ip)[0];
591  (*op)[1] = (*ip)[1];
592  (*op)[2] = (*ip)[2];
593  (*op)[3] = (*ip)[3];
594  *ip += dec32table[offset];
595  ZSTD_copy4(*op+4, *ip);
596  *ip -= sub2;
597  } else {
598  ZSTD_copy8(*op, *ip);
599  }
600  *ip += 8;
601  *op += 8;
602  assert(*op - *ip >= 8);
603 }
604 
616 static void ZSTD_safecopy(BYTE* op, BYTE* const oend_w, BYTE const* ip, ptrdiff_t length, ZSTD_overlap_e ovtype) {
617  ptrdiff_t const diff = op - ip;
618  BYTE* const oend = op + length;
619 
620  assert((ovtype == ZSTD_no_overlap && (diff <= -8 || diff >= 8 || op >= oend_w)) ||
621  (ovtype == ZSTD_overlap_src_before_dst && diff >= 0));
622 
623  if (length < 8) {
624  /* Handle short lengths. */
625  while (op < oend) *op++ = *ip++;
626  return;
627  }
628  if (ovtype == ZSTD_overlap_src_before_dst) {
629  /* Copy 8 bytes and ensure the offset >= 8 when there can be overlap. */
630  assert(length >= 8);
631  ZSTD_overlapCopy8(&op, &ip, diff);
632  assert(op - ip >= 8);
633  assert(op <= oend);
634  }
635 
636  if (oend <= oend_w) {
637  /* No risk of overwrite. */
638  ZSTD_wildcopy(op, ip, length, ovtype);
639  return;
640  }
641  if (op <= oend_w) {
642  /* Wildcopy until we get close to the end. */
643  assert(oend > oend_w);
644  ZSTD_wildcopy(op, ip, oend_w - op, ovtype);
645  ip += oend_w - op;
646  op = oend_w;
647  }
648  /* Handle the leftovers. */
649  while (op < oend) *op++ = *ip++;
650 }
651 
652 /* ZSTD_execSequenceEnd():
653  * This version handles cases that are near the end of the output buffer. It requires
654  * more careful checks to make sure there is no overflow. By separating out these hard
655  * and unlikely cases, we can speed up the common cases.
656  *
657  * NOTE: This function needs to be fast for a single long sequence, but doesn't need
658  * to be optimized for many small sequences, since those fall into ZSTD_execSequence().
659  */
660 FORCE_NOINLINE
661 size_t ZSTD_execSequenceEnd(BYTE* op,
662  BYTE* const oend, seq_t sequence,
663  const BYTE** litPtr, const BYTE* const litLimit,
664  const BYTE* const prefixStart, const BYTE* const virtualStart, const BYTE* const dictEnd)
665 {
666  BYTE* const oLitEnd = op + sequence.litLength;
667  size_t const sequenceLength = sequence.litLength + sequence.matchLength;
668  const BYTE* const iLitEnd = *litPtr + sequence.litLength;
669  const BYTE* match = oLitEnd - sequence.offset;
670  BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH;
671 
672  /* bounds checks : careful of address space overflow in 32-bit mode */
673  RETURN_ERROR_IF(sequenceLength > (size_t)(oend - op), dstSize_tooSmall, "last match must fit within dstBuffer");
674  RETURN_ERROR_IF(sequence.litLength > (size_t)(litLimit - *litPtr), corruption_detected, "try to read beyond literal buffer");
675  assert(op < op + sequenceLength);
676  assert(oLitEnd < op + sequenceLength);
677 
678  /* copy literals */
679  ZSTD_safecopy(op, oend_w, *litPtr, sequence.litLength, ZSTD_no_overlap);
680  op = oLitEnd;
681  *litPtr = iLitEnd;
682 
683  /* copy Match */
684  if (sequence.offset > (size_t)(oLitEnd - prefixStart)) {
685  /* offset beyond prefix */
686  RETURN_ERROR_IF(sequence.offset > (size_t)(oLitEnd - virtualStart), corruption_detected, "");
687  match = dictEnd - (prefixStart-match);
688  if (match + sequence.matchLength <= dictEnd) {
689  memmove(oLitEnd, match, sequence.matchLength);
690  return sequenceLength;
691  }
692  /* span extDict & currentPrefixSegment */
693  { size_t const length1 = dictEnd - match;
694  memmove(oLitEnd, match, length1);
695  op = oLitEnd + length1;
696  sequence.matchLength -= length1;
697  match = prefixStart;
698  } }
699  ZSTD_safecopy(op, oend_w, match, sequence.matchLength, ZSTD_overlap_src_before_dst);
700  return sequenceLength;
701 }
702 
703 HINT_INLINE
704 size_t ZSTD_execSequence(BYTE* op,
705  BYTE* const oend, seq_t sequence,
706  const BYTE** litPtr, const BYTE* const litLimit,
707  const BYTE* const prefixStart, const BYTE* const virtualStart, const BYTE* const dictEnd)
708 {
709  BYTE* const oLitEnd = op + sequence.litLength;
710  size_t const sequenceLength = sequence.litLength + sequence.matchLength;
711  BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
712  BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH; /* risk : address space underflow on oend=NULL */
713  const BYTE* const iLitEnd = *litPtr + sequence.litLength;
714  const BYTE* match = oLitEnd - sequence.offset;
715 
716  assert(op != NULL /* Precondition */);
717  assert(oend_w < oend /* No underflow */);
718  /* Handle edge cases in a slow path:
719  * - Read beyond end of literals
720  * - Match end is within WILDCOPY_OVERLIMIT of oend
721  * - 32-bit mode and the match length overflows
722  */
723  if (UNLIKELY(
724  iLitEnd > litLimit ||
725  oMatchEnd > oend_w ||
726  (MEM_32bits() && (size_t)(oend - op) < sequenceLength + WILDCOPY_OVERLENGTH)))
727  return ZSTD_execSequenceEnd(op, oend, sequence, litPtr, litLimit, prefixStart, virtualStart, dictEnd);
728 
729  /* Assumptions (everything else goes into ZSTD_execSequenceEnd()) */
730  assert(op <= oLitEnd /* No overflow */);
731  assert(oLitEnd < oMatchEnd /* Non-zero match & no overflow */);
732  assert(oMatchEnd <= oend /* No underflow */);
733  assert(iLitEnd <= litLimit /* Literal length is in bounds */);
734  assert(oLitEnd <= oend_w /* Can wildcopy literals */);
735  assert(oMatchEnd <= oend_w /* Can wildcopy matches */);
736 
737  /* Copy Literals:
738  * Split out litLength <= 16 since it is nearly always true. +1.6% on gcc-9.
739  * We likely don't need the full 32-byte wildcopy.
740  */
741  assert(WILDCOPY_OVERLENGTH >= 16);
742  ZSTD_copy16(op, (*litPtr));
743  if (UNLIKELY(sequence.litLength > 16)) {
744  ZSTD_wildcopy(op+16, (*litPtr)+16, sequence.litLength-16, ZSTD_no_overlap);
745  }
746  op = oLitEnd;
747  *litPtr = iLitEnd; /* update for next sequence */
748 
749  /* Copy Match */
750  if (sequence.offset > (size_t)(oLitEnd - prefixStart)) {
751  /* offset beyond prefix -> go into extDict */
752  RETURN_ERROR_IF(UNLIKELY(sequence.offset > (size_t)(oLitEnd - virtualStart)), corruption_detected, "");
753  match = dictEnd + (match - prefixStart);
754  if (match + sequence.matchLength <= dictEnd) {
755  memmove(oLitEnd, match, sequence.matchLength);
756  return sequenceLength;
757  }
758  /* span extDict & currentPrefixSegment */
759  { size_t const length1 = dictEnd - match;
760  memmove(oLitEnd, match, length1);
761  op = oLitEnd + length1;
762  sequence.matchLength -= length1;
763  match = prefixStart;
764  } }
765  /* Match within prefix of 1 or more bytes */
766  assert(op <= oMatchEnd);
767  assert(oMatchEnd <= oend_w);
768  assert(match >= prefixStart);
769  assert(sequence.matchLength >= 1);
770 
771  /* Nearly all offsets are >= WILDCOPY_VECLEN bytes, which means we can use wildcopy
772  * without overlap checking.
773  */
774  if (LIKELY(sequence.offset >= WILDCOPY_VECLEN)) {
775  /* We bet on a full wildcopy for matches, since we expect matches to be
776  * longer than literals (in general). In silesia, ~10% of matches are longer
777  * than 16 bytes.
778  */
779  ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength, ZSTD_no_overlap);
780  return sequenceLength;
781  }
782  assert(sequence.offset < WILDCOPY_VECLEN);
783 
784  /* Copy 8 bytes and spread the offset to be >= 8. */
785  ZSTD_overlapCopy8(&op, &match, sequence.offset);
786 
787  /* If the match length is > 8 bytes, then continue with the wildcopy. */
788  if (sequence.matchLength > 8) {
789  assert(op < oMatchEnd);
790  ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8, ZSTD_overlap_src_before_dst);
791  }
792  return sequenceLength;
793 }
794 
795 static void
796 ZSTD_initFseState(ZSTD_fseState* DStatePtr, BIT_DStream_t* bitD, const ZSTD_seqSymbol* dt)
797 {
798  const void* ptr = dt;
799  const ZSTD_seqSymbol_header* const DTableH = (const ZSTD_seqSymbol_header*)ptr;
800  DStatePtr->state = BIT_readBits(bitD, DTableH->tableLog);
801  DEBUGLOG(6, "ZSTD_initFseState : val=%u using %u bits",
802  (U32)DStatePtr->state, DTableH->tableLog);
803  BIT_reloadDStream(bitD);
804  DStatePtr->table = dt + 1;
805 }
806 
807 FORCE_INLINE_TEMPLATE void
808 ZSTD_updateFseState(ZSTD_fseState* DStatePtr, BIT_DStream_t* bitD)
809 {
810  ZSTD_seqSymbol const DInfo = DStatePtr->table[DStatePtr->state];
811  U32 const nbBits = DInfo.nbBits;
812  size_t const lowBits = BIT_readBits(bitD, nbBits);
813  DStatePtr->state = DInfo.nextState + lowBits;
814 }
815 
816 FORCE_INLINE_TEMPLATE void
817 ZSTD_updateFseStateWithDInfo(ZSTD_fseState* DStatePtr, BIT_DStream_t* bitD, ZSTD_seqSymbol const DInfo)
818 {
819  U32 const nbBits = DInfo.nbBits;
820  size_t const lowBits = BIT_readBits(bitD, nbBits);
821  DStatePtr->state = DInfo.nextState + lowBits;
822 }
823 
824 /* We need to add at most (ZSTD_WINDOWLOG_MAX_32 - 1) bits to read the maximum
825  * offset bits. But we can only read at most (STREAM_ACCUMULATOR_MIN_32 - 1)
826  * bits before reloading. This value is the maximum number of bytes we read
827  * after reloading when we are decoding long offsets.
828  */
829 #define LONG_OFFSETS_MAX_EXTRA_BITS_32 \
830  (ZSTD_WINDOWLOG_MAX_32 > STREAM_ACCUMULATOR_MIN_32 \
831  ? ZSTD_WINDOWLOG_MAX_32 - STREAM_ACCUMULATOR_MIN_32 \
832  : 0)
833 
834 typedef enum { ZSTD_lo_isRegularOffset, ZSTD_lo_isLongOffset=1 } ZSTD_longOffset_e;
835 typedef enum { ZSTD_p_noPrefetch=0, ZSTD_p_prefetch=1 } ZSTD_prefetch_e;
836 
837 FORCE_INLINE_TEMPLATE seq_t
838 ZSTD_decodeSequence(seqState_t* seqState, const ZSTD_longOffset_e longOffsets, const ZSTD_prefetch_e prefetch)
839 {
840  seq_t seq;
841  ZSTD_seqSymbol const llDInfo = seqState->stateLL.table[seqState->stateLL.state];
842  ZSTD_seqSymbol const mlDInfo = seqState->stateML.table[seqState->stateML.state];
843  ZSTD_seqSymbol const ofDInfo = seqState->stateOffb.table[seqState->stateOffb.state];
844  U32 const llBase = llDInfo.baseValue;
845  U32 const mlBase = mlDInfo.baseValue;
846  U32 const ofBase = ofDInfo.baseValue;
847  BYTE const llBits = llDInfo.nbAdditionalBits;
848  BYTE const mlBits = mlDInfo.nbAdditionalBits;
849  BYTE const ofBits = ofDInfo.nbAdditionalBits;
850  BYTE const totalBits = llBits+mlBits+ofBits;
851 
852  /* sequence */
853  { size_t offset;
854  if (ofBits > 1) {
855  ZSTD_STATIC_ASSERT(ZSTD_lo_isLongOffset == 1);
856  ZSTD_STATIC_ASSERT(LONG_OFFSETS_MAX_EXTRA_BITS_32 == 5);
857  assert(ofBits <= MaxOff);
858  if (MEM_32bits() && longOffsets && (ofBits >= STREAM_ACCUMULATOR_MIN_32)) {
859  U32 const extraBits = ofBits - MIN(ofBits, 32 - seqState->DStream.bitsConsumed);
860  offset = ofBase + (BIT_readBitsFast(&seqState->DStream, ofBits - extraBits) << extraBits);
861  BIT_reloadDStream(&seqState->DStream);
862  if (extraBits) offset += BIT_readBitsFast(&seqState->DStream, extraBits);
863  assert(extraBits <= LONG_OFFSETS_MAX_EXTRA_BITS_32); /* to avoid another reload */
864  } else {
865  offset = ofBase + BIT_readBitsFast(&seqState->DStream, ofBits/*>0*/); /* <= (ZSTD_WINDOWLOG_MAX-1) bits */
866  if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream);
867  }
868  seqState->prevOffset[2] = seqState->prevOffset[1];
869  seqState->prevOffset[1] = seqState->prevOffset[0];
870  seqState->prevOffset[0] = offset;
871  } else {
872  U32 const ll0 = (llBase == 0);
873  if (LIKELY((ofBits == 0))) {
874  if (LIKELY(!ll0))
875  offset = seqState->prevOffset[0];
876  else {
877  offset = seqState->prevOffset[1];
878  seqState->prevOffset[1] = seqState->prevOffset[0];
879  seqState->prevOffset[0] = offset;
880  }
881  } else {
882  offset = ofBase + ll0 + BIT_readBitsFast(&seqState->DStream, 1);
883  { size_t temp = (offset==3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
884  temp += !temp; /* 0 is not valid; input is corrupted; force offset to 1 */
885  if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1];
886  seqState->prevOffset[1] = seqState->prevOffset[0];
887  seqState->prevOffset[0] = offset = temp;
888  } } }
889  seq.offset = offset;
890  }
891 
892  seq.matchLength = mlBase;
893  if (mlBits > 0)
894  seq.matchLength += BIT_readBitsFast(&seqState->DStream, mlBits/*>0*/);
895 
896  if (MEM_32bits() && (mlBits+llBits >= STREAM_ACCUMULATOR_MIN_32-LONG_OFFSETS_MAX_EXTRA_BITS_32))
897  BIT_reloadDStream(&seqState->DStream);
898  if (MEM_64bits() && UNLIKELY(totalBits >= STREAM_ACCUMULATOR_MIN_64-(LLFSELog+MLFSELog+OffFSELog)))
899  BIT_reloadDStream(&seqState->DStream);
900  /* Ensure there are enough bits to read the rest of data in 64-bit mode. */
901  ZSTD_STATIC_ASSERT(16+LLFSELog+MLFSELog+OffFSELog < STREAM_ACCUMULATOR_MIN_64);
902 
903  seq.litLength = llBase;
904  if (llBits > 0)
905  seq.litLength += BIT_readBitsFast(&seqState->DStream, llBits/*>0*/);
906 
907  if (MEM_32bits())
908  BIT_reloadDStream(&seqState->DStream);
909 
910  DEBUGLOG(6, "seq: litL=%u, matchL=%u, offset=%u",
911  (U32)seq.litLength, (U32)seq.matchLength, (U32)seq.offset);
912 
913  if (prefetch == ZSTD_p_prefetch) {
914  size_t const pos = seqState->pos + seq.litLength;
915  const BYTE* const matchBase = (seq.offset > pos) ? seqState->dictEnd : seqState->prefixStart;
916  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.
917  * No consequence though : no memory access will occur, offset is only used for prefetching */
918  seqState->pos = pos + seq.matchLength;
919  }
920 
921  /* ANS state update
922  * gcc-9.0.0 does 2.5% worse with ZSTD_updateFseStateWithDInfo().
923  * clang-9.2.0 does 7% worse with ZSTD_updateFseState().
924  * Naturally it seems like ZSTD_updateFseStateWithDInfo() should be the
925  * better option, so it is the default for other compilers. But, if you
926  * measure that it is worse, please put up a pull request.
927  */
928  {
929 #if defined(__GNUC__) && !defined(__clang__)
930  const int kUseUpdateFseState = 1;
931 #else
932  const int kUseUpdateFseState = 0;
933 #endif
934  if (kUseUpdateFseState) {
935  ZSTD_updateFseState(&seqState->stateLL, &seqState->DStream); /* <= 9 bits */
936  ZSTD_updateFseState(&seqState->stateML, &seqState->DStream); /* <= 9 bits */
937  if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */
938  ZSTD_updateFseState(&seqState->stateOffb, &seqState->DStream); /* <= 8 bits */
939  } else {
940  ZSTD_updateFseStateWithDInfo(&seqState->stateLL, &seqState->DStream, llDInfo); /* <= 9 bits */
941  ZSTD_updateFseStateWithDInfo(&seqState->stateML, &seqState->DStream, mlDInfo); /* <= 9 bits */
942  if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */
943  ZSTD_updateFseStateWithDInfo(&seqState->stateOffb, &seqState->DStream, ofDInfo); /* <= 8 bits */
944  }
945  }
946 
947  return seq;
948 }
949 
950 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
951 static int ZSTD_dictionaryIsActive(ZSTD_DCtx const* dctx, BYTE const* prefixStart, BYTE const* oLitEnd)
952 {
953  size_t const windowSize = dctx->fParams.windowSize;
954  /* No dictionary used. */
955  if (dctx->dictContentEndForFuzzing == NULL) return 0;
956  /* Dictionary is our prefix. */
957  if (prefixStart == dctx->dictContentBeginForFuzzing) return 1;
958  /* Dictionary is not our ext-dict. */
959  if (dctx->dictEnd != dctx->dictContentEndForFuzzing) return 0;
960  /* Dictionary is not within our window size. */
961  if ((size_t)(oLitEnd - prefixStart) >= windowSize) return 0;
962  /* Dictionary is active. */
963  return 1;
964 }
965 
966 MEM_STATIC void ZSTD_assertValidSequence(
967  ZSTD_DCtx const* dctx,
968  BYTE const* op, BYTE const* oend,
969  seq_t const seq,
970  BYTE const* prefixStart, BYTE const* virtualStart)
971 {
972  size_t const windowSize = dctx->fParams.windowSize;
973  size_t const sequenceSize = seq.litLength + seq.matchLength;
974  BYTE const* const oLitEnd = op + seq.litLength;
975  DEBUGLOG(6, "Checking sequence: litL=%u matchL=%u offset=%u",
976  (U32)seq.litLength, (U32)seq.matchLength, (U32)seq.offset);
977  assert(op <= oend);
978  assert((size_t)(oend - op) >= sequenceSize);
979  assert(sequenceSize <= ZSTD_BLOCKSIZE_MAX);
980  if (ZSTD_dictionaryIsActive(dctx, prefixStart, oLitEnd)) {
981  size_t const dictSize = (size_t)((char const*)dctx->dictContentEndForFuzzing - (char const*)dctx->dictContentBeginForFuzzing);
982  /* Offset must be within the dictionary. */
983  assert(seq.offset <= (size_t)(oLitEnd - virtualStart));
984  assert(seq.offset <= windowSize + dictSize);
985  } else {
986  /* Offset must be within our window. */
987  assert(seq.offset <= windowSize);
988  }
989 }
990 #endif
991 
992 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
993 FORCE_INLINE_TEMPLATE size_t
994 DONT_VECTORIZE
995 ZSTD_decompressSequences_body( ZSTD_DCtx* dctx,
996  void* dst, size_t maxDstSize,
997  const void* seqStart, size_t seqSize, int nbSeq,
998  const ZSTD_longOffset_e isLongOffset,
999  const int frame)
1000 {
1001  const BYTE* ip = (const BYTE*)seqStart;
1002  const BYTE* const iend = ip + seqSize;
1003  BYTE* const ostart = (BYTE* const)dst;
1004  BYTE* const oend = ostart + maxDstSize;
1005  BYTE* op = ostart;
1006  const BYTE* litPtr = dctx->litPtr;
1007  const BYTE* const litEnd = litPtr + dctx->litSize;
1008  const BYTE* const prefixStart = (const BYTE*) (dctx->prefixStart);
1009  const BYTE* const vBase = (const BYTE*) (dctx->virtualStart);
1010  const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
1011  DEBUGLOG(5, "ZSTD_decompressSequences_body");
1012  (void)frame;
1013 
1014  /* Regen sequences */
1015  if (nbSeq) {
1016  seqState_t seqState;
1017  size_t error = 0;
1018  dctx->fseEntropy = 1;
1019  { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->entropy.rep[i]; }
1020  RETURN_ERROR_IF(
1021  ERR_isError(BIT_initDStream(&seqState.DStream, ip, iend-ip)),
1022  corruption_detected, "");
1023  ZSTD_initFseState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
1024  ZSTD_initFseState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
1025  ZSTD_initFseState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
1026  assert(dst != NULL);
1027 
1028  ZSTD_STATIC_ASSERT(
1029  BIT_DStream_unfinished < BIT_DStream_completed &&
1030  BIT_DStream_endOfBuffer < BIT_DStream_completed &&
1031  BIT_DStream_completed < BIT_DStream_overflow);
1032 
1033 #if defined(__GNUC__) && defined(__x86_64__)
1034  /* Align the decompression loop to 32 + 16 bytes.
1035  *
1036  * zstd compiled with gcc-9 on an Intel i9-9900k shows 10% decompression
1037  * speed swings based on the alignment of the decompression loop. This
1038  * performance swing is caused by parts of the decompression loop falling
1039  * out of the DSB. The entire decompression loop should fit in the DSB,
1040  * when it can't we get much worse performance. You can measure if you've
1041  * hit the good case or the bad case with this perf command for some
1042  * compressed file test.zst:
1043  *
1044  * perf stat -e cycles -e instructions -e idq.all_dsb_cycles_any_uops \
1045  * -e idq.all_mite_cycles_any_uops -- ./zstd -tq test.zst
1046  *
1047  * If you see most cycles served out of the MITE you've hit the bad case.
1048  * If you see most cycles served out of the DSB you've hit the good case.
1049  * If it is pretty even then you may be in an okay case.
1050  *
1051  * I've been able to reproduce this issue on the following CPUs:
1052  * - Kabylake: Macbook Pro (15-inch, 2019) 2.4 GHz Intel Core i9
1053  * Use Instruments->Counters to get DSB/MITE cycles.
1054  * I never got performance swings, but I was able to
1055  * go from the good case of mostly DSB to half of the
1056  * cycles served from MITE.
1057  * - Coffeelake: Intel i9-9900k
1058  *
1059  * I haven't been able to reproduce the instability or DSB misses on any
1060  * of the following CPUS:
1061  * - Haswell
1062  * - Broadwell: Intel(R) Xeon(R) CPU E5-2680 v4 @ 2.40GH
1063  * - Skylake
1064  *
1065  * If you are seeing performance stability this script can help test.
1066  * It tests on 4 commits in zstd where I saw performance change.
1067  *
1068  * https://gist.github.com/terrelln/9889fc06a423fd5ca6e99351564473f4
1069  */
1070  __asm__(".p2align 5");
1071  __asm__("nop");
1072  __asm__(".p2align 4");
1073 #endif
1074  for ( ; ; ) {
1075  seq_t const sequence = ZSTD_decodeSequence(&seqState, isLongOffset, ZSTD_p_noPrefetch);
1076  size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litEnd, prefixStart, vBase, dictEnd);
1077 #if defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION) && defined(FUZZING_ASSERT_VALID_SEQUENCE)
1078  assert(!ZSTD_isError(oneSeqSize));
1079  if (frame) ZSTD_assertValidSequence(dctx, op, oend, sequence, prefixStart, vBase);
1080 #endif
1081  DEBUGLOG(6, "regenerated sequence size : %u", (U32)oneSeqSize);
1082  BIT_reloadDStream(&(seqState.DStream));
1083  /* gcc and clang both don't like early returns in this loop.
1084  * gcc doesn't like early breaks either.
1085  * Instead save an error and report it at the end.
1086  * When there is an error, don't increment op, so we don't
1087  * overwrite.
1088  */
1089  if (UNLIKELY(ZSTD_isError(oneSeqSize))) error = oneSeqSize;
1090  else op += oneSeqSize;
1091  if (UNLIKELY(!--nbSeq)) break;
1092  }
1093 
1094  /* check if reached exact end */
1095  DEBUGLOG(5, "ZSTD_decompressSequences_body: after decode loop, remaining nbSeq : %i", nbSeq);
1096  if (ZSTD_isError(error)) return error;
1097  RETURN_ERROR_IF(nbSeq, corruption_detected, "");
1098  RETURN_ERROR_IF(BIT_reloadDStream(&seqState.DStream) < BIT_DStream_completed, corruption_detected, "");
1099  /* save reps for next block */
1100  { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]); }
1101  }
1102 
1103  /* last literal segment */
1104  { size_t const lastLLSize = litEnd - litPtr;
1105  RETURN_ERROR_IF(lastLLSize > (size_t)(oend-op), dstSize_tooSmall, "");
1106  if (op != NULL) {
1107  memcpy(op, litPtr, lastLLSize);
1108  op += lastLLSize;
1109  }
1110  }
1111 
1112  return op-ostart;
1113 }
1114 
1115 static size_t
1116 ZSTD_decompressSequences_default(ZSTD_DCtx* dctx,
1117  void* dst, size_t maxDstSize,
1118  const void* seqStart, size_t seqSize, int nbSeq,
1119  const ZSTD_longOffset_e isLongOffset,
1120  const int frame)
1121 {
1122  return ZSTD_decompressSequences_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1123 }
1124 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */
1125 
1126 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
1127 FORCE_INLINE_TEMPLATE size_t
1128 ZSTD_decompressSequencesLong_body(
1129  ZSTD_DCtx* dctx,
1130  void* dst, size_t maxDstSize,
1131  const void* seqStart, size_t seqSize, int nbSeq,
1132  const ZSTD_longOffset_e isLongOffset,
1133  const int frame)
1134 {
1135  const BYTE* ip = (const BYTE*)seqStart;
1136  const BYTE* const iend = ip + seqSize;
1137  BYTE* const ostart = (BYTE* const)dst;
1138  BYTE* const oend = ostart + maxDstSize;
1139  BYTE* op = ostart;
1140  const BYTE* litPtr = dctx->litPtr;
1141  const BYTE* const litEnd = litPtr + dctx->litSize;
1142  const BYTE* const prefixStart = (const BYTE*) (dctx->prefixStart);
1143  const BYTE* const dictStart = (const BYTE*) (dctx->virtualStart);
1144  const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
1145  (void)frame;
1146 
1147  /* Regen sequences */
1148  if (nbSeq) {
1149 #define STORED_SEQS 4
1150 #define STORED_SEQS_MASK (STORED_SEQS-1)
1151 #define ADVANCED_SEQS 4
1152  seq_t sequences[STORED_SEQS];
1153  int const seqAdvance = MIN(nbSeq, ADVANCED_SEQS);
1154  seqState_t seqState;
1155  int seqNb;
1156  dctx->fseEntropy = 1;
1157  { int i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->entropy.rep[i]; }
1158  seqState.prefixStart = prefixStart;
1159  seqState.pos = (size_t)(op-prefixStart);
1160  seqState.dictEnd = dictEnd;
1161  assert(dst != NULL);
1162  assert(iend >= ip);
1163  RETURN_ERROR_IF(
1164  ERR_isError(BIT_initDStream(&seqState.DStream, ip, iend-ip)),
1165  corruption_detected, "");
1166  ZSTD_initFseState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
1167  ZSTD_initFseState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
1168  ZSTD_initFseState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
1169 
1170  /* prepare in advance */
1171  for (seqNb=0; (BIT_reloadDStream(&seqState.DStream) <= BIT_DStream_completed) && (seqNb<seqAdvance); seqNb++) {
1172  sequences[seqNb] = ZSTD_decodeSequence(&seqState, isLongOffset, ZSTD_p_prefetch);
1173  PREFETCH_L1(sequences[seqNb].match); PREFETCH_L1(sequences[seqNb].match + sequences[seqNb].matchLength - 1); /* note : it's safe to invoke PREFETCH() on any memory address, including invalid ones */
1174  }
1175  RETURN_ERROR_IF(seqNb<seqAdvance, corruption_detected, "");
1176 
1177  /* decode and decompress */
1178  for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (seqNb<nbSeq) ; seqNb++) {
1179  seq_t const sequence = ZSTD_decodeSequence(&seqState, isLongOffset, ZSTD_p_prefetch);
1180  size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequences[(seqNb-ADVANCED_SEQS) & STORED_SEQS_MASK], &litPtr, litEnd, prefixStart, dictStart, dictEnd);
1181 #if defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION) && defined(FUZZING_ASSERT_VALID_SEQUENCE)
1182  assert(!ZSTD_isError(oneSeqSize));
1183  if (frame) ZSTD_assertValidSequence(dctx, op, oend, sequences[(seqNb-ADVANCED_SEQS) & STORED_SEQS_MASK], prefixStart, dictStart);
1184 #endif
1185  if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
1186  PREFETCH_L1(sequence.match); PREFETCH_L1(sequence.match + sequence.matchLength - 1); /* note : it's safe to invoke PREFETCH() on any memory address, including invalid ones */
1187  sequences[seqNb & STORED_SEQS_MASK] = sequence;
1188  op += oneSeqSize;
1189  }
1190  RETURN_ERROR_IF(seqNb<nbSeq, corruption_detected, "");
1191 
1192  /* finish queue */
1193  seqNb -= seqAdvance;
1194  for ( ; seqNb<nbSeq ; seqNb++) {
1195  size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequences[seqNb&STORED_SEQS_MASK], &litPtr, litEnd, prefixStart, dictStart, dictEnd);
1196 #if defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION) && defined(FUZZING_ASSERT_VALID_SEQUENCE)
1197  assert(!ZSTD_isError(oneSeqSize));
1198  if (frame) ZSTD_assertValidSequence(dctx, op, oend, sequences[seqNb&STORED_SEQS_MASK], prefixStart, dictStart);
1199 #endif
1200  if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
1201  op += oneSeqSize;
1202  }
1203 
1204  /* save reps for next block */
1205  { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]); }
1206  }
1207 
1208  /* last literal segment */
1209  { size_t const lastLLSize = litEnd - litPtr;
1210  RETURN_ERROR_IF(lastLLSize > (size_t)(oend-op), dstSize_tooSmall, "");
1211  if (op != NULL) {
1212  memcpy(op, litPtr, lastLLSize);
1213  op += lastLLSize;
1214  }
1215  }
1216 
1217  return op-ostart;
1218 }
1219 
1220 static size_t
1221 ZSTD_decompressSequencesLong_default(ZSTD_DCtx* dctx,
1222  void* dst, size_t maxDstSize,
1223  const void* seqStart, size_t seqSize, int nbSeq,
1224  const ZSTD_longOffset_e isLongOffset,
1225  const int frame)
1226 {
1227  return ZSTD_decompressSequencesLong_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1228 }
1229 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */
1230 
1231 
1232 
1233 #if DYNAMIC_BMI2
1234 
1235 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
1236 static TARGET_ATTRIBUTE("bmi2") size_t
1237 DONT_VECTORIZE
1238 ZSTD_decompressSequences_bmi2(ZSTD_DCtx* dctx,
1239  void* dst, size_t maxDstSize,
1240  const void* seqStart, size_t seqSize, int nbSeq,
1241  const ZSTD_longOffset_e isLongOffset,
1242  const int frame)
1243 {
1244  return ZSTD_decompressSequences_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1245 }
1246 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */
1247 
1248 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
1249 static TARGET_ATTRIBUTE("bmi2") size_t
1250 ZSTD_decompressSequencesLong_bmi2(ZSTD_DCtx* dctx,
1251  void* dst, size_t maxDstSize,
1252  const void* seqStart, size_t seqSize, int nbSeq,
1253  const ZSTD_longOffset_e isLongOffset,
1254  const int frame)
1255 {
1256  return ZSTD_decompressSequencesLong_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1257 }
1258 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */
1259 
1260 #endif /* DYNAMIC_BMI2 */
1261 
1262 typedef size_t (*ZSTD_decompressSequences_t)(
1263  ZSTD_DCtx* dctx,
1264  void* dst, size_t maxDstSize,
1265  const void* seqStart, size_t seqSize, int nbSeq,
1266  const ZSTD_longOffset_e isLongOffset,
1267  const int frame);
1268 
1269 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
1270 static size_t
1271 ZSTD_decompressSequences(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize,
1272  const void* seqStart, size_t seqSize, int nbSeq,
1273  const ZSTD_longOffset_e isLongOffset,
1274  const int frame)
1275 {
1276  DEBUGLOG(5, "ZSTD_decompressSequences");
1277 #if DYNAMIC_BMI2
1278  if (dctx->bmi2) {
1279  return ZSTD_decompressSequences_bmi2(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1280  }
1281 #endif
1282  return ZSTD_decompressSequences_default(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1283 }
1284 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */
1285 
1286 
1287 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
1288 /* ZSTD_decompressSequencesLong() :
1289  * decompression function triggered when a minimum share of offsets is considered "long",
1290  * aka out of cache.
1291  * note : "long" definition seems overloaded here, sometimes meaning "wider than bitstream register", and sometimes meaning "farther than memory cache distance".
1292  * This function will try to mitigate main memory latency through the use of prefetching */
1293 static size_t
1294 ZSTD_decompressSequencesLong(ZSTD_DCtx* dctx,
1295  void* dst, size_t maxDstSize,
1296  const void* seqStart, size_t seqSize, int nbSeq,
1297  const ZSTD_longOffset_e isLongOffset,
1298  const int frame)
1299 {
1300  DEBUGLOG(5, "ZSTD_decompressSequencesLong");
1301 #if DYNAMIC_BMI2
1302  if (dctx->bmi2) {
1303  return ZSTD_decompressSequencesLong_bmi2(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1304  }
1305 #endif
1306  return ZSTD_decompressSequencesLong_default(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1307 }
1308 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */
1309 
1310 
1311 
1312 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1313  !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1314 /* ZSTD_getLongOffsetsShare() :
1315  * condition : offTable must be valid
1316  * @return : "share" of long offsets (arbitrarily defined as > (1<<23))
1317  * compared to maximum possible of (1<<OffFSELog) */
1318 static unsigned
1319 ZSTD_getLongOffsetsShare(const ZSTD_seqSymbol* offTable)
1320 {
1321  const void* ptr = offTable;
1322  U32 const tableLog = ((const ZSTD_seqSymbol_header*)ptr)[0].tableLog;
1323  const ZSTD_seqSymbol* table = offTable + 1;
1324  U32 const max = 1 << tableLog;
1325  U32 u, total = 0;
1326  DEBUGLOG(5, "ZSTD_getLongOffsetsShare: (tableLog=%u)", tableLog);
1327 
1328  assert(max <= (1 << OffFSELog)); /* max not too large */
1329  for (u=0; u<max; u++) {
1330  if (table[u].nbAdditionalBits > 22) total += 1;
1331  }
1332 
1333  assert(tableLog <= OffFSELog);
1334  total <<= (OffFSELog - tableLog); /* scale to OffFSELog */
1335 
1336  return total;
1337 }
1338 #endif
1339 
1340 size_t
1341 ZSTD_decompressBlock_internal(ZSTD_DCtx* dctx,
1342  void* dst, size_t dstCapacity,
1343  const void* src, size_t srcSize, const int frame)
1344 { /* blockType == blockCompressed */
1345  const BYTE* ip = (const BYTE*)src;
1346  /* isLongOffset must be true if there are long offsets.
1347  * Offsets are long if they are larger than 2^STREAM_ACCUMULATOR_MIN.
1348  * We don't expect that to be the case in 64-bit mode.
1349  * In block mode, window size is not known, so we have to be conservative.
1350  * (note: but it could be evaluated from current-lowLimit)
1351  */
1352  ZSTD_longOffset_e const isLongOffset = (ZSTD_longOffset_e)(MEM_32bits() && (!frame || (dctx->fParams.windowSize > (1ULL << STREAM_ACCUMULATOR_MIN))));
1353  DEBUGLOG(5, "ZSTD_decompressBlock_internal (size : %u)", (U32)srcSize);
1354 
1355  RETURN_ERROR_IF(srcSize >= ZSTD_BLOCKSIZE_MAX, srcSize_wrong, "");
1356 
1357  /* Decode literals section */
1358  { size_t const litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize);
1359  DEBUGLOG(5, "ZSTD_decodeLiteralsBlock : %u", (U32)litCSize);
1360  if (ZSTD_isError(litCSize)) return litCSize;
1361  ip += litCSize;
1362  srcSize -= litCSize;
1363  }
1364 
1365  /* Build Decoding Tables */
1366  {
1367  /* These macros control at build-time which decompressor implementation
1368  * we use. If neither is defined, we do some inspection and dispatch at
1369  * runtime.
1370  */
1371 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1372  !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1373  int usePrefetchDecoder = dctx->ddictIsCold;
1374 #endif
1375  int nbSeq;
1376  size_t const seqHSize = ZSTD_decodeSeqHeaders(dctx, &nbSeq, ip, srcSize);
1377  if (ZSTD_isError(seqHSize)) return seqHSize;
1378  ip += seqHSize;
1379  srcSize -= seqHSize;
1380 
1381  RETURN_ERROR_IF(dst == NULL && nbSeq > 0, dstSize_tooSmall, "NULL not handled");
1382 
1383 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1384  !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1385  if ( !usePrefetchDecoder
1386  && (!frame || (dctx->fParams.windowSize > (1<<24)))
1387  && (nbSeq>ADVANCED_SEQS) ) { /* could probably use a larger nbSeq limit */
1388  U32 const shareLongOffsets = ZSTD_getLongOffsetsShare(dctx->OFTptr);
1389  U32 const minShare = MEM_64bits() ? 7 : 20; /* heuristic values, correspond to 2.73% and 7.81% */
1390  usePrefetchDecoder = (shareLongOffsets >= minShare);
1391  }
1392 #endif
1393 
1394  dctx->ddictIsCold = 0;
1395 
1396 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1397  !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1398  if (usePrefetchDecoder)
1399 #endif
1400 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
1401  return ZSTD_decompressSequencesLong(dctx, dst, dstCapacity, ip, srcSize, nbSeq, isLongOffset, frame);
1402 #endif
1403 
1404 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
1405  /* else */
1406  return ZSTD_decompressSequences(dctx, dst, dstCapacity, ip, srcSize, nbSeq, isLongOffset, frame);
1407 #endif
1408  }
1409 }
1410 
1411 
1412 void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst)
1413 {
1414  if (dst != dctx->previousDstEnd) { /* not contiguous */
1415  dctx->dictEnd = dctx->previousDstEnd;
1416  dctx->virtualStart = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->prefixStart));
1417  dctx->prefixStart = dst;
1418  dctx->previousDstEnd = dst;
1419  }
1420 }
1421 
1422 
1423 size_t ZSTD_decompressBlock(ZSTD_DCtx* dctx,
1424  void* dst, size_t dstCapacity,
1425  const void* src, size_t srcSize)
1426 {
1427  size_t dSize;
1428  ZSTD_checkContinuity(dctx, dst);
1429  dSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize, /* frame */ 0);
1430  dctx->previousDstEnd = (char*)dst + dSize;
1431  return dSize;
1432 }
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
Definition: cache.c:48
symbolEncodingType_e
size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx *dctx, int *nbSeqPtr, const void *src, size_t srcSize)
blockType_e blockType
POINT last
Definition: font.c:46
Definition: match.c:28
blockType_e
GLuint buffer
Definition: glext.h:5915
static void ZSTD_copy4(void *dst, const void *src)
static char memory[1024 *256]
Definition: process.c:116
GLenum GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * bits
Definition: glext.h:10929
size_t ZSTD_getcBlockSize(const void *src, size_t srcSize, blockProperties_t *bpPtr)
GLsizei GLsizei GLfloat distance
Definition: glext.h:11755
#define DEBUGLOG(l,...)
Definition: debug.h:106
static size_t ZSTD_buildSeqTable(ZSTD_seqSymbol *DTableSpace, const ZSTD_seqSymbol **DTablePtr, symbolEncodingType_e type, unsigned 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 up(mutex)
Definition: glue.h:30
static const size_t ZSTD_blockHeaderSize
size_t ZSTD_decompressBlock_internal(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const int frame)
GLuint GLfloat * val
Definition: glext.h:7180
GLsizeiptr size
Definition: glext.h:5919
#define RETURN_ERROR_IF(cond, err,...)
Definition: zstd_internal.h:91
GLintptr offset
Definition: glext.h:5920
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, const int frame)
static unsigned ZSTD_getLongOffsetsShare(const ZSTD_seqSymbol *offTable)
size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx *dctx, const void *src, size_t srcSize)
static struct message * sequence
Definition: subclass.c:46
#define MIN_CBLOCK_SIZE
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
__inline int after(__u32 seq1, __u32 seq2)
Definition: tcpcore.h:2419
GLenum src
Definition: glext.h:6340
unsigned char BYTE
Definition: xxhash.c:193
static BYTE decode(char c)
Definition: base64_codec.c:97
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
FORCE_INLINE_TEMPLATE size_t DONT_VECTORIZE ZSTD_decompressSequences_body(ZSTD_DCtx *dctx, void *dst, size_t maxDstSize, const void *seqStart, size_t seqSize, int nbSeq, const ZSTD_longOffset_e isLongOffset, const int frame)
GLenum GLenum dst
Definition: glext.h:6340
#define NULL
Definition: types.h:112
static void ZSTD_initFseState(ZSTD_fseState *DStatePtr, BIT_DStream_t *bitD, const ZSTD_seqSymbol *dt)
unsigned int U32
Definition: xxhash.c:195
static UINT PSTR DWORD UINT * need
Definition: parser.c:36
_CRTIMP int __cdecl read(_In_ int _FileHandle, _Out_writes_bytes_(_MaxCharCount) void *_DstBuf, _In_ unsigned int _MaxCharCount)
MEM_STATIC U32 MEM_readLE24(const void *memPtr)
Definition: mem.h:335
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, const int frame)