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 **********************************************************/
ZSTD_copy4(void * dst,const void * src)47 static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
48 
49 
50 /*-*************************************************************
51  *   Block decoding
52  ***************************************************************/
53 
54 /*! ZSTD_getcBlockSize() :
55  *  Provides the size of compressed block from block header `src` */
ZSTD_getcBlockSize(const void * src,size_t srcSize,blockProperties_t * bpPtr)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 */
74 size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx,
75                           const void* src, size_t srcSize);
76 /*! ZSTD_decodeLiteralsBlock() :
77  * @return : nb of bytes read from src (< srcSize )
78  *  note : symbol not declared but exposed for fullbench */
ZSTD_decodeLiteralsBlock(ZSTD_DCtx * dctx,const void * src,size_t srcSize)79 size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx,
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 
ZSTD_buildSeqTable_rle(ZSTD_seqSymbol * dt,U32 baseValue,U32 nbAddBits)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
ZSTD_buildFSETable(ZSTD_seqSymbol * dt,const short * normalizedCounter,unsigned maxSymbolValue,const U32 * baseValue,const U32 * nbAdditionalBits,unsigned tableLog)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 
430 /*! ZSTD_buildSeqTable() :
431  * @return : nb bytes read from src,
432  *           or an error code if it fails */
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)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 
ZSTD_decodeSeqHeaders(ZSTD_DCtx * dctx,int * nbSeqPtr,const void * src,size_t srcSize)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 
576 /*! ZSTD_overlapCopy8() :
577  *  Copies 8 bytes from ip to op and updates op and ip where ip <= op.
578  *  If the offset is < 8 then the offset is spread to at least 8 bytes.
579  *
580  *  Precondition: *ip <= *op
581  *  Postcondition: *op - *op >= 8
582  */
ZSTD_overlapCopy8(BYTE ** op,BYTE const ** ip,size_t offset)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 
605 /*! ZSTD_safecopy() :
606  *  Specialized version of memcpy() that is allowed to READ up to WILDCOPY_OVERLENGTH past the input buffer
607  *  and write up to 16 bytes past oend_w (op >= oend_w is allowed).
608  *  This function is only called in the uncommon case where the sequence is near the end of the block. It
609  *  should be fast for a single long sequence, but can be slow for several short sequences.
610  *
611  *  @param ovtype controls the overlap detection
612  *         - ZSTD_no_overlap: The source and destination are guaranteed to be at least WILDCOPY_VECLEN bytes apart.
613  *         - ZSTD_overlap_src_before_dst: The src and dst may overlap and may be any distance apart.
614  *           The src buffer must be before the dst buffer.
615  */
ZSTD_safecopy(BYTE * op,BYTE * const oend_w,BYTE const * ip,ptrdiff_t length,ZSTD_overlap_e ovtype)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
ZSTD_execSequenceEnd(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)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
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)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
ZSTD_initFseState(ZSTD_fseState * DStatePtr,BIT_DStream_t * bitD,const ZSTD_seqSymbol * dt)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
ZSTD_updateFseState(ZSTD_fseState * DStatePtr,BIT_DStream_t * bitD)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
ZSTD_updateFseStateWithDInfo(ZSTD_fseState * DStatePtr,BIT_DStream_t * bitD,ZSTD_seqSymbol const DInfo)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
ZSTD_decodeSequence(seqState_t * seqState,const ZSTD_longOffset_e longOffsets,const ZSTD_prefetch_e prefetch)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
ZSTD_dictionaryIsActive(ZSTD_DCtx const * dctx,BYTE const * prefixStart,BYTE const * oLitEnd)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 
ZSTD_assertValidSequence(ZSTD_DCtx const * dctx,BYTE const * op,BYTE const * oend,seq_t const seq,BYTE const * prefixStart,BYTE const * virtualStart)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
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)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
ZSTD_decompressSequences_default(ZSTD_DCtx * dctx,void * dst,size_t maxDstSize,const void * seqStart,size_t seqSize,int nbSeq,const ZSTD_longOffset_e isLongOffset,const int frame)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
ZSTD_decompressSequencesLong_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)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
ZSTD_decompressSequencesLong_default(ZSTD_DCtx * dctx,void * dst,size_t maxDstSize,const void * seqStart,size_t seqSize,int nbSeq,const ZSTD_longOffset_e isLongOffset,const int frame)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
ZSTD_decompressSequences_bmi2(ZSTD_DCtx * dctx,void * dst,size_t maxDstSize,const void * seqStart,size_t seqSize,int nbSeq,const ZSTD_longOffset_e isLongOffset,const int frame)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
ZSTD_decompressSequencesLong_bmi2(ZSTD_DCtx * dctx,void * dst,size_t maxDstSize,const void * seqStart,size_t seqSize,int nbSeq,const ZSTD_longOffset_e isLongOffset,const int frame)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
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)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
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)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
ZSTD_getLongOffsetsShare(const ZSTD_seqSymbol * offTable)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
ZSTD_decompressBlock_internal(ZSTD_DCtx * dctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize,const int frame)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 
ZSTD_checkContinuity(ZSTD_DCtx * dctx,const void * dst)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 
ZSTD_decompressBlock(ZSTD_DCtx * dctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize)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 }
1433