Gitiles
Code Review Sign In
gerrit.opencord.org / voltha-go / 292ab5256baf4b8574a482c5a675300c4a40e8bb / . / vendor / github.com / DataDog / zstd / zstd_decompress_block.c
blob: 24f4859c56c94fd9d42d803bcbe464be18d85b9f [file] [log] [blame]
Scott Baker8461e152019-10-01 14:44:30 -0700[diff] [blame]1/*
2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
3 * All rights reserved.
4 *
5 * This source code is licensed under both the BSD-style license (found in the
6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
7 * in the COPYING file in the root directory of this source tree).
8 * You may select, at your option, one of the above-listed licenses.
9 */
10
11/* 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**********************************************************/
47static 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` */
56size_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 */
74size_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 */
79size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx,
80 const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */
81{
82 RETURN_ERROR_IF(srcSize < MIN_CBLOCK_SIZE, corruption_detected);
83
84 { const BYTE* const istart = (const BYTE*) src;
85 symbolEncodingType_e const litEncType = (symbolEncodingType_e)(istart[0] & 3);
86
87 switch(litEncType)
88 {
89 case set_repeat:
90 RETURN_ERROR_IF(dctx->litEntropy==0, dictionary_corrupted);
91 /* fall-through */
92
93 case set_compressed:
94 RETURN_ERROR_IF(srcSize < 5, corruption_detected, "srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for case 3");
95 { size_t lhSize, litSize, litCSize;
96 U32 singleStream=0;
97 U32 const lhlCode = (istart[0] >> 2) & 3;
98 U32 const lhc = MEM_readLE32(istart);
99 size_t hufSuccess;
100 switch(lhlCode)
101 {
102 case 0: case 1: default: /* note : default is impossible, since lhlCode into [0..3] */
103 /* 2 - 2 - 10 - 10 */
104 singleStream = !lhlCode;
105 lhSize = 3;
106 litSize = (lhc >> 4) & 0x3FF;
107 litCSize = (lhc >> 14) & 0x3FF;
108 break;
109 case 2:
110 /* 2 - 2 - 14 - 14 */
111 lhSize = 4;
112 litSize = (lhc >> 4) & 0x3FFF;
113 litCSize = lhc >> 18;
114 break;
115 case 3:
116 /* 2 - 2 - 18 - 18 */
117 lhSize = 5;
118 litSize = (lhc >> 4) & 0x3FFFF;
119 litCSize = (lhc >> 22) + (istart[4] << 10);
120 break;
121 }
122 RETURN_ERROR_IF(litSize > ZSTD_BLOCKSIZE_MAX, corruption_detected);
123 RETURN_ERROR_IF(litCSize + lhSize > srcSize, corruption_detected);
124
125 /* prefetch huffman table if cold */
126 if (dctx->ddictIsCold && (litSize > 768 /* heuristic */)) {
127 PREFETCH_AREA(dctx->HUFptr, sizeof(dctx->entropy.hufTable));
128 }
129
130 if (litEncType==set_repeat) {
131 if (singleStream) {
132 hufSuccess = HUF_decompress1X_usingDTable_bmi2(
133 dctx->litBuffer, litSize, istart+lhSize, litCSize,
134 dctx->HUFptr, dctx->bmi2);
135 } else {
136 hufSuccess = HUF_decompress4X_usingDTable_bmi2(
137 dctx->litBuffer, litSize, istart+lhSize, litCSize,
138 dctx->HUFptr, dctx->bmi2);
139 }
140 } else {
141 if (singleStream) {
142#if defined(HUF_FORCE_DECOMPRESS_X2)
143 hufSuccess = HUF_decompress1X_DCtx_wksp(
144 dctx->entropy.hufTable, dctx->litBuffer, litSize,
145 istart+lhSize, litCSize, dctx->workspace,
146 sizeof(dctx->workspace));
147#else
148 hufSuccess = HUF_decompress1X1_DCtx_wksp_bmi2(
149 dctx->entropy.hufTable, dctx->litBuffer, litSize,
150 istart+lhSize, litCSize, dctx->workspace,
151 sizeof(dctx->workspace), dctx->bmi2);
152#endif
153 } else {
154 hufSuccess = HUF_decompress4X_hufOnly_wksp_bmi2(
155 dctx->entropy.hufTable, dctx->litBuffer, litSize,
156 istart+lhSize, litCSize, dctx->workspace,
157 sizeof(dctx->workspace), dctx->bmi2);
158 }
159 }
160
161 RETURN_ERROR_IF(HUF_isError(hufSuccess), corruption_detected);
162
163 dctx->litPtr = dctx->litBuffer;
164 dctx->litSize = litSize;
165 dctx->litEntropy = 1;
166 if (litEncType==set_compressed) dctx->HUFptr = dctx->entropy.hufTable;
167 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
168 return litCSize + lhSize;
169 }
170
171 case set_basic:
172 { size_t litSize, lhSize;
173 U32 const lhlCode = ((istart[0]) >> 2) & 3;
174 switch(lhlCode)
175 {
176 case 0: case 2: default: /* note : default is impossible, since lhlCode into [0..3] */
177 lhSize = 1;
178 litSize = istart[0] >> 3;
179 break;
180 case 1:
181 lhSize = 2;
182 litSize = MEM_readLE16(istart) >> 4;
183 break;
184 case 3:
185 lhSize = 3;
186 litSize = MEM_readLE24(istart) >> 4;
187 break;
188 }
189
190 if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */
191 RETURN_ERROR_IF(litSize+lhSize > srcSize, corruption_detected);
192 memcpy(dctx->litBuffer, istart+lhSize, litSize);
193 dctx->litPtr = dctx->litBuffer;
194 dctx->litSize = litSize;
195 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
196 return lhSize+litSize;
197 }
198 /* direct reference into compressed stream */
199 dctx->litPtr = istart+lhSize;
200 dctx->litSize = litSize;
201 return lhSize+litSize;
202 }
203
204 case set_rle:
205 { U32 const lhlCode = ((istart[0]) >> 2) & 3;
206 size_t litSize, lhSize;
207 switch(lhlCode)
208 {
209 case 0: case 2: default: /* note : default is impossible, since lhlCode into [0..3] */
210 lhSize = 1;
211 litSize = istart[0] >> 3;
212 break;
213 case 1:
214 lhSize = 2;
215 litSize = MEM_readLE16(istart) >> 4;
216 break;
217 case 3:
218 lhSize = 3;
219 litSize = MEM_readLE24(istart) >> 4;
220 RETURN_ERROR_IF(srcSize<4, corruption_detected, "srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4");
221 break;
222 }
223 RETURN_ERROR_IF(litSize > ZSTD_BLOCKSIZE_MAX, corruption_detected);
224 memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
225 dctx->litPtr = dctx->litBuffer;
226 dctx->litSize = litSize;
227 return lhSize+1;
228 }
229 default:
230 RETURN_ERROR(corruption_detected, "impossible");
231 }
232 }
233}
234
235/* Default FSE distribution tables.
236 * These are pre-calculated FSE decoding tables using default distributions as defined in specification :
237 * https://github.com/facebook/zstd/blob/master/doc/zstd_compression_format.md#default-distributions
238 * They were generated programmatically with following method :
239 * - start from default distributions, present in /lib/common/zstd_internal.h
240 * - generate tables normally, using ZSTD_buildFSETable()
241 * - printout the content of tables
242 * - pretify output, report below, test with fuzzer to ensure it's correct */
243
244/* Default FSE distribution table for Literal Lengths */
245static const ZSTD_seqSymbol LL_defaultDTable[(1<<LL_DEFAULTNORMLOG)+1] = {
246 { 1, 1, 1, LL_DEFAULTNORMLOG}, /* header : fastMode, tableLog */
247 /* nextState, nbAddBits, nbBits, baseVal */
248 { 0, 0, 4, 0}, { 16, 0, 4, 0},
249 { 32, 0, 5, 1}, { 0, 0, 5, 3},
250 { 0, 0, 5, 4}, { 0, 0, 5, 6},
251 { 0, 0, 5, 7}, { 0, 0, 5, 9},
252 { 0, 0, 5, 10}, { 0, 0, 5, 12},
253 { 0, 0, 6, 14}, { 0, 1, 5, 16},
254 { 0, 1, 5, 20}, { 0, 1, 5, 22},
255 { 0, 2, 5, 28}, { 0, 3, 5, 32},
256 { 0, 4, 5, 48}, { 32, 6, 5, 64},
257 { 0, 7, 5, 128}, { 0, 8, 6, 256},
258 { 0, 10, 6, 1024}, { 0, 12, 6, 4096},
259 { 32, 0, 4, 0}, { 0, 0, 4, 1},
260 { 0, 0, 5, 2}, { 32, 0, 5, 4},
261 { 0, 0, 5, 5}, { 32, 0, 5, 7},
262 { 0, 0, 5, 8}, { 32, 0, 5, 10},
263 { 0, 0, 5, 11}, { 0, 0, 6, 13},
264 { 32, 1, 5, 16}, { 0, 1, 5, 18},
265 { 32, 1, 5, 22}, { 0, 2, 5, 24},
266 { 32, 3, 5, 32}, { 0, 3, 5, 40},
267 { 0, 6, 4, 64}, { 16, 6, 4, 64},
268 { 32, 7, 5, 128}, { 0, 9, 6, 512},
269 { 0, 11, 6, 2048}, { 48, 0, 4, 0},
270 { 16, 0, 4, 1}, { 32, 0, 5, 2},
271 { 32, 0, 5, 3}, { 32, 0, 5, 5},
272 { 32, 0, 5, 6}, { 32, 0, 5, 8},
273 { 32, 0, 5, 9}, { 32, 0, 5, 11},
274 { 32, 0, 5, 12}, { 0, 0, 6, 15},
275 { 32, 1, 5, 18}, { 32, 1, 5, 20},
276 { 32, 2, 5, 24}, { 32, 2, 5, 28},
277 { 32, 3, 5, 40}, { 32, 4, 5, 48},
278 { 0, 16, 6,65536}, { 0, 15, 6,32768},
279 { 0, 14, 6,16384}, { 0, 13, 6, 8192},
280}; /* LL_defaultDTable */
281
282/* Default FSE distribution table for Offset Codes */
283static const ZSTD_seqSymbol OF_defaultDTable[(1<<OF_DEFAULTNORMLOG)+1] = {
284 { 1, 1, 1, OF_DEFAULTNORMLOG}, /* header : fastMode, tableLog */
285 /* nextState, nbAddBits, nbBits, baseVal */
286 { 0, 0, 5, 0}, { 0, 6, 4, 61},
287 { 0, 9, 5, 509}, { 0, 15, 5,32765},
288 { 0, 21, 5,2097149}, { 0, 3, 5, 5},
289 { 0, 7, 4, 125}, { 0, 12, 5, 4093},
290 { 0, 18, 5,262141}, { 0, 23, 5,8388605},
291 { 0, 5, 5, 29}, { 0, 8, 4, 253},
292 { 0, 14, 5,16381}, { 0, 20, 5,1048573},
293 { 0, 2, 5, 1}, { 16, 7, 4, 125},
294 { 0, 11, 5, 2045}, { 0, 17, 5,131069},
295 { 0, 22, 5,4194301}, { 0, 4, 5, 13},
296 { 16, 8, 4, 253}, { 0, 13, 5, 8189},
297 { 0, 19, 5,524285}, { 0, 1, 5, 1},
298 { 16, 6, 4, 61}, { 0, 10, 5, 1021},
299 { 0, 16, 5,65533}, { 0, 28, 5,268435453},
300 { 0, 27, 5,134217725}, { 0, 26, 5,67108861},
301 { 0, 25, 5,33554429}, { 0, 24, 5,16777213},
302}; /* OF_defaultDTable */
303
304
305/* Default FSE distribution table for Match Lengths */
306static const ZSTD_seqSymbol ML_defaultDTable[(1<<ML_DEFAULTNORMLOG)+1] = {
307 { 1, 1, 1, ML_DEFAULTNORMLOG}, /* header : fastMode, tableLog */
308 /* nextState, nbAddBits, nbBits, baseVal */
309 { 0, 0, 6, 3}, { 0, 0, 4, 4},
310 { 32, 0, 5, 5}, { 0, 0, 5, 6},
311 { 0, 0, 5, 8}, { 0, 0, 5, 9},
312 { 0, 0, 5, 11}, { 0, 0, 6, 13},
313 { 0, 0, 6, 16}, { 0, 0, 6, 19},
314 { 0, 0, 6, 22}, { 0, 0, 6, 25},
315 { 0, 0, 6, 28}, { 0, 0, 6, 31},
316 { 0, 0, 6, 34}, { 0, 1, 6, 37},
317 { 0, 1, 6, 41}, { 0, 2, 6, 47},
318 { 0, 3, 6, 59}, { 0, 4, 6, 83},
319 { 0, 7, 6, 131}, { 0, 9, 6, 515},
320 { 16, 0, 4, 4}, { 0, 0, 4, 5},
321 { 32, 0, 5, 6}, { 0, 0, 5, 7},
322 { 32, 0, 5, 9}, { 0, 0, 5, 10},
323 { 0, 0, 6, 12}, { 0, 0, 6, 15},
324 { 0, 0, 6, 18}, { 0, 0, 6, 21},
325 { 0, 0, 6, 24}, { 0, 0, 6, 27},
326 { 0, 0, 6, 30}, { 0, 0, 6, 33},
327 { 0, 1, 6, 35}, { 0, 1, 6, 39},
328 { 0, 2, 6, 43}, { 0, 3, 6, 51},
329 { 0, 4, 6, 67}, { 0, 5, 6, 99},
330 { 0, 8, 6, 259}, { 32, 0, 4, 4},
331 { 48, 0, 4, 4}, { 16, 0, 4, 5},
332 { 32, 0, 5, 7}, { 32, 0, 5, 8},
333 { 32, 0, 5, 10}, { 32, 0, 5, 11},
334 { 0, 0, 6, 14}, { 0, 0, 6, 17},
335 { 0, 0, 6, 20}, { 0, 0, 6, 23},
336 { 0, 0, 6, 26}, { 0, 0, 6, 29},
337 { 0, 0, 6, 32}, { 0, 16, 6,65539},
338 { 0, 15, 6,32771}, { 0, 14, 6,16387},
339 { 0, 13, 6, 8195}, { 0, 12, 6, 4099},
340 { 0, 11, 6, 2051}, { 0, 10, 6, 1027},
341}; /* ML_defaultDTable */
342
343
344static void ZSTD_buildSeqTable_rle(ZSTD_seqSymbol* dt, U32 baseValue, U32 nbAddBits)
345{
346 void* ptr = dt;
347 ZSTD_seqSymbol_header* const DTableH = (ZSTD_seqSymbol_header*)ptr;
348 ZSTD_seqSymbol* const cell = dt + 1;
349
350 DTableH->tableLog = 0;
351 DTableH->fastMode = 0;
352
353 cell->nbBits = 0;
354 cell->nextState = 0;
355 assert(nbAddBits < 255);
356 cell->nbAdditionalBits = (BYTE)nbAddBits;
357 cell->baseValue = baseValue;
358}
359
360
361/* ZSTD_buildFSETable() :
362 * generate FSE decoding table for one symbol (ll, ml or off)
363 * cannot fail if input is valid =>
364 * all inputs are presumed validated at this stage */
365void
366ZSTD_buildFSETable(ZSTD_seqSymbol* dt,
367 const short* normalizedCounter, unsigned maxSymbolValue,
368 const U32* baseValue, const U32* nbAdditionalBits,
369 unsigned tableLog)
370{
371 ZSTD_seqSymbol* const tableDecode = dt+1;
372 U16 symbolNext[MaxSeq+1];
373
374 U32 const maxSV1 = maxSymbolValue + 1;
375 U32 const tableSize = 1 << tableLog;
376 U32 highThreshold = tableSize-1;
377
378 /* Sanity Checks */
379 assert(maxSymbolValue <= MaxSeq);
380 assert(tableLog <= MaxFSELog);
381
382 /* Init, lay down lowprob symbols */
383 { ZSTD_seqSymbol_header DTableH;
384 DTableH.tableLog = tableLog;
385 DTableH.fastMode = 1;
386 { S16 const largeLimit= (S16)(1 << (tableLog-1));
387 U32 s;
388 for (s=0; s<maxSV1; s++) {
389 if (normalizedCounter[s]==-1) {
390 tableDecode[highThreshold--].baseValue = s;
391 symbolNext[s] = 1;
392 } else {
393 if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
394 symbolNext[s] = normalizedCounter[s];
395 } } }
396 memcpy(dt, &DTableH, sizeof(DTableH));
397 }
398
399 /* Spread symbols */
400 { U32 const tableMask = tableSize-1;
401 U32 const step = FSE_TABLESTEP(tableSize);
402 U32 s, position = 0;
403 for (s=0; s<maxSV1; s++) {
404 int i;
405 for (i=0; i<normalizedCounter[s]; i++) {
406 tableDecode[position].baseValue = s;
407 position = (position + step) & tableMask;
408 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
409 } }
410 assert(position == 0); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
411 }
412
413 /* Build Decoding table */
414 { U32 u;
415 for (u=0; u<tableSize; u++) {
416 U32 const symbol = tableDecode[u].baseValue;
417 U32 const nextState = symbolNext[symbol]++;
418 tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32(nextState) );
419 tableDecode[u].nextState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
420 assert(nbAdditionalBits[symbol] < 255);
421 tableDecode[u].nbAdditionalBits = (BYTE)nbAdditionalBits[symbol];
422 tableDecode[u].baseValue = baseValue[symbol];
423 } }
424}
425
426
427/*! ZSTD_buildSeqTable() :
428 * @return : nb bytes read from src,
429 * or an error code if it fails */
430static size_t ZSTD_buildSeqTable(ZSTD_seqSymbol* DTableSpace, const ZSTD_seqSymbol** DTablePtr,
431 symbolEncodingType_e type, unsigned max, U32 maxLog,
432 const void* src, size_t srcSize,
433 const U32* baseValue, const U32* nbAdditionalBits,
434 const ZSTD_seqSymbol* defaultTable, U32 flagRepeatTable,
435 int ddictIsCold, int nbSeq)
436{
437 switch(type)
438 {
439 case set_rle :
440 RETURN_ERROR_IF(!srcSize, srcSize_wrong);
441 RETURN_ERROR_IF((*(const BYTE*)src) > max, corruption_detected);
442 { U32 const symbol = *(const BYTE*)src;
443 U32 const baseline = baseValue[symbol];
444 U32 const nbBits = nbAdditionalBits[symbol];
445 ZSTD_buildSeqTable_rle(DTableSpace, baseline, nbBits);
446 }
447 *DTablePtr = DTableSpace;
448 return 1;
449 case set_basic :
450 *DTablePtr = defaultTable;
451 return 0;
452 case set_repeat:
453 RETURN_ERROR_IF(!flagRepeatTable, corruption_detected);
454 /* prefetch FSE table if used */
455 if (ddictIsCold && (nbSeq > 24 /* heuristic */)) {
456 const void* const pStart = *DTablePtr;
457 size_t const pSize = sizeof(ZSTD_seqSymbol) * (SEQSYMBOL_TABLE_SIZE(maxLog));
458 PREFETCH_AREA(pStart, pSize);
459 }
460 return 0;
461 case set_compressed :
462 { unsigned tableLog;
463 S16 norm[MaxSeq+1];
464 size_t const headerSize = FSE_readNCount(norm, &max, &tableLog, src, srcSize);
465 RETURN_ERROR_IF(FSE_isError(headerSize), corruption_detected);
466 RETURN_ERROR_IF(tableLog > maxLog, corruption_detected);
467 ZSTD_buildFSETable(DTableSpace, norm, max, baseValue, nbAdditionalBits, tableLog);
468 *DTablePtr = DTableSpace;
469 return headerSize;
470 }
471 default :
472 assert(0);
473 RETURN_ERROR(GENERIC, "impossible");
474 }
475}
476
477size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr,
478 const void* src, size_t srcSize)
479{
480 const BYTE* const istart = (const BYTE* const)src;
481 const BYTE* const iend = istart + srcSize;
482 const BYTE* ip = istart;
483 int nbSeq;
484 DEBUGLOG(5, "ZSTD_decodeSeqHeaders");
485
486 /* check */
487 RETURN_ERROR_IF(srcSize < MIN_SEQUENCES_SIZE, srcSize_wrong);
488
489 /* SeqHead */
490 nbSeq = *ip++;
491 if (!nbSeq) {
492 *nbSeqPtr=0;
493 RETURN_ERROR_IF(srcSize != 1, srcSize_wrong);
494 return 1;
495 }
496 if (nbSeq > 0x7F) {
497 if (nbSeq == 0xFF) {
498 RETURN_ERROR_IF(ip+2 > iend, srcSize_wrong);
499 nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2;
500 } else {
501 RETURN_ERROR_IF(ip >= iend, srcSize_wrong);
502 nbSeq = ((nbSeq-0x80)<<8) + *ip++;
503 }
504 }
505 *nbSeqPtr = nbSeq;
506
507 /* FSE table descriptors */
508 RETURN_ERROR_IF(ip+1 > iend, srcSize_wrong); /* minimum possible size: 1 byte for symbol encoding types */
509 { symbolEncodingType_e const LLtype = (symbolEncodingType_e)(*ip >> 6);
510 symbolEncodingType_e const OFtype = (symbolEncodingType_e)((*ip >> 4) & 3);
511 symbolEncodingType_e const MLtype = (symbolEncodingType_e)((*ip >> 2) & 3);
512 ip++;
513
514 /* Build DTables */
515 { size_t const llhSize = ZSTD_buildSeqTable(dctx->entropy.LLTable, &dctx->LLTptr,
516 LLtype, MaxLL, LLFSELog,
517 ip, iend-ip,
518 LL_base, LL_bits,
519 LL_defaultDTable, dctx->fseEntropy,
520 dctx->ddictIsCold, nbSeq);
521 RETURN_ERROR_IF(ZSTD_isError(llhSize), corruption_detected);
522 ip += llhSize;
523 }
524
525 { size_t const ofhSize = ZSTD_buildSeqTable(dctx->entropy.OFTable, &dctx->OFTptr,
526 OFtype, MaxOff, OffFSELog,
527 ip, iend-ip,
528 OF_base, OF_bits,
529 OF_defaultDTable, dctx->fseEntropy,
530 dctx->ddictIsCold, nbSeq);
531 RETURN_ERROR_IF(ZSTD_isError(ofhSize), corruption_detected);
532 ip += ofhSize;
533 }
534
535 { size_t const mlhSize = ZSTD_buildSeqTable(dctx->entropy.MLTable, &dctx->MLTptr,
536 MLtype, MaxML, MLFSELog,
537 ip, iend-ip,
538 ML_base, ML_bits,
539 ML_defaultDTable, dctx->fseEntropy,
540 dctx->ddictIsCold, nbSeq);
541 RETURN_ERROR_IF(ZSTD_isError(mlhSize), corruption_detected);
542 ip += mlhSize;
543 }
544 }
545
546 return ip-istart;
547}
548
549
550typedef struct {
551 size_t litLength;
552 size_t matchLength;
553 size_t offset;
554 const BYTE* match;
555} seq_t;
556
557typedef struct {
558 size_t state;
559 const ZSTD_seqSymbol* table;
560} ZSTD_fseState;
561
562typedef struct {
563 BIT_DStream_t DStream;
564 ZSTD_fseState stateLL;
565 ZSTD_fseState stateOffb;
566 ZSTD_fseState stateML;
567 size_t prevOffset[ZSTD_REP_NUM];
568 const BYTE* prefixStart;
569 const BYTE* dictEnd;
570 size_t pos;
571} seqState_t;
572
573
574/* ZSTD_execSequenceLast7():
575 * exceptional case : decompress a match starting within last 7 bytes of output buffer.
576 * requires more careful checks, to ensure there is no overflow.
577 * performance does not matter though.
578 * note : this case is supposed to be never generated "naturally" by reference encoder,
579 * since in most cases it needs at least 8 bytes to look for a match.
580 * but it's allowed by the specification. */
581FORCE_NOINLINE
582size_t ZSTD_execSequenceLast7(BYTE* op,
583 BYTE* const oend, seq_t sequence,
584 const BYTE** litPtr, const BYTE* const litLimit,
585 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
586{
587 BYTE* const oLitEnd = op + sequence.litLength;
588 size_t const sequenceLength = sequence.litLength + sequence.matchLength;
589 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
590 const BYTE* const iLitEnd = *litPtr + sequence.litLength;
591 const BYTE* match = oLitEnd - sequence.offset;
592
593 /* check */
594 RETURN_ERROR_IF(oMatchEnd>oend, dstSize_tooSmall, "last match must fit within dstBuffer");
595 RETURN_ERROR_IF(iLitEnd > litLimit, corruption_detected, "try to read beyond literal buffer");
596
597 /* copy literals */
598 while (op < oLitEnd) *op++ = *(*litPtr)++;
599
600 /* copy Match */
601 if (sequence.offset > (size_t)(oLitEnd - base)) {
602 /* offset beyond prefix */
603 RETURN_ERROR_IF(sequence.offset > (size_t)(oLitEnd - vBase),corruption_detected);
604 match = dictEnd - (base-match);
605 if (match + sequence.matchLength <= dictEnd) {
606 memmove(oLitEnd, match, sequence.matchLength);
607 return sequenceLength;
608 }
609 /* span extDict & currentPrefixSegment */
610 { size_t const length1 = dictEnd - match;
611 memmove(oLitEnd, match, length1);
612 op = oLitEnd + length1;
613 sequence.matchLength -= length1;
614 match = base;
615 } }
616 while (op < oMatchEnd) *op++ = *match++;
617 return sequenceLength;
618}
619
620
621HINT_INLINE
622size_t ZSTD_execSequence(BYTE* op,
623 BYTE* const oend, seq_t sequence,
624 const BYTE** litPtr, const BYTE* const litLimit,
625 const BYTE* const prefixStart, const BYTE* const virtualStart, const BYTE* const dictEnd)
626{
627 BYTE* const oLitEnd = op + sequence.litLength;
628 size_t const sequenceLength = sequence.litLength + sequence.matchLength;
629 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
630 BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH;
631 const BYTE* const iLitEnd = *litPtr + sequence.litLength;
632 const BYTE* match = oLitEnd - sequence.offset;
633
634 /* check */
635 RETURN_ERROR_IF(oMatchEnd>oend, dstSize_tooSmall, "last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend");
636 RETURN_ERROR_IF(iLitEnd > litLimit, corruption_detected, "over-read beyond lit buffer");
637 if (oLitEnd>oend_w) return ZSTD_execSequenceLast7(op, oend, sequence, litPtr, litLimit, prefixStart, virtualStart, dictEnd);
638
639 /* copy Literals */
640 if (sequence.litLength > 8)
641 ZSTD_wildcopy_16min(op, (*litPtr), sequence.litLength, ZSTD_no_overlap); /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
642 else
643 ZSTD_copy8(op, *litPtr);
644 op = oLitEnd;
645 *litPtr = iLitEnd; /* update for next sequence */
646
647 /* copy Match */
648 if (sequence.offset > (size_t)(oLitEnd - prefixStart)) {
649 /* offset beyond prefix -> go into extDict */
650 RETURN_ERROR_IF(sequence.offset > (size_t)(oLitEnd - virtualStart), corruption_detected);
651 match = dictEnd + (match - prefixStart);
652 if (match + sequence.matchLength <= dictEnd) {
653 memmove(oLitEnd, match, sequence.matchLength);
654 return sequenceLength;
655 }
656 /* span extDict & currentPrefixSegment */
657 { size_t const length1 = dictEnd - match;
658 memmove(oLitEnd, match, length1);
659 op = oLitEnd + length1;
660 sequence.matchLength -= length1;
661 match = prefixStart;
662 if (op > oend_w || sequence.matchLength < MINMATCH) {
663 U32 i;
664 for (i = 0; i < sequence.matchLength; ++i) op[i] = match[i];
665 return sequenceLength;
666 }
667 } }
668 /* Requirement: op <= oend_w && sequence.matchLength >= MINMATCH */
669
670 /* match within prefix */
671 if (sequence.offset < 8) {
672 /* close range match, overlap */
673 static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
674 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* subtracted */
675 int const sub2 = dec64table[sequence.offset];
676 op[0] = match[0];
677 op[1] = match[1];
678 op[2] = match[2];
679 op[3] = match[3];
680 match += dec32table[sequence.offset];
681 ZSTD_copy4(op+4, match);
682 match -= sub2;
683 } else {
684 ZSTD_copy8(op, match);
685 }
686 op += 8; match += 8;
687
688 if (oMatchEnd > oend-(16-MINMATCH)) {
689 if (op < oend_w) {
690 ZSTD_wildcopy(op, match, oend_w - op, ZSTD_overlap_src_before_dst);
691 match += oend_w - op;
692 op = oend_w;
693 }
694 while (op < oMatchEnd) *op++ = *match++;
695 } else {
696 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8, ZSTD_overlap_src_before_dst); /* works even if matchLength < 8 */
697 }
698 return sequenceLength;
699}
700
701
702HINT_INLINE
703size_t ZSTD_execSequenceLong(BYTE* op,
704 BYTE* const oend, seq_t sequence,
705 const BYTE** litPtr, const BYTE* const litLimit,
706 const BYTE* const prefixStart, const BYTE* const dictStart, const BYTE* const dictEnd)
707{
708 BYTE* const oLitEnd = op + sequence.litLength;
709 size_t const sequenceLength = sequence.litLength + sequence.matchLength;
710 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
711 BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH;
712 const BYTE* const iLitEnd = *litPtr + sequence.litLength;
713 const BYTE* match = sequence.match;
714
715 /* check */
716 RETURN_ERROR_IF(oMatchEnd > oend, dstSize_tooSmall, "last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend");
717 RETURN_ERROR_IF(iLitEnd > litLimit, corruption_detected, "over-read beyond lit buffer");
718 if (oLitEnd > oend_w) return ZSTD_execSequenceLast7(op, oend, sequence, litPtr, litLimit, prefixStart, dictStart, dictEnd);
719
720 /* copy Literals */
721 if (sequence.litLength > 8)
722 ZSTD_wildcopy_16min(op, *litPtr, sequence.litLength, ZSTD_no_overlap); /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
723 else
724 ZSTD_copy8(op, *litPtr); /* note : op <= oLitEnd <= oend_w == oend - 8 */
725
726 op = oLitEnd;
727 *litPtr = iLitEnd; /* update for next sequence */
728
729 /* copy Match */
730 if (sequence.offset > (size_t)(oLitEnd - prefixStart)) {
731 /* offset beyond prefix */
732 RETURN_ERROR_IF(sequence.offset > (size_t)(oLitEnd - dictStart), corruption_detected);
733 if (match + sequence.matchLength <= dictEnd) {
734 memmove(oLitEnd, match, sequence.matchLength);
735 return sequenceLength;
736 }
737 /* span extDict & currentPrefixSegment */
738 { size_t const length1 = dictEnd - match;
739 memmove(oLitEnd, match, length1);
740 op = oLitEnd + length1;
741 sequence.matchLength -= length1;
742 match = prefixStart;
743 if (op > oend_w || sequence.matchLength < MINMATCH) {
744 U32 i;
745 for (i = 0; i < sequence.matchLength; ++i) op[i] = match[i];
746 return sequenceLength;
747 }
748 } }
749 assert(op <= oend_w);
750 assert(sequence.matchLength >= MINMATCH);
751
752 /* match within prefix */
753 if (sequence.offset < 8) {
754 /* close range match, overlap */
755 static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
756 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* subtracted */
757 int const sub2 = dec64table[sequence.offset];
758 op[0] = match[0];
759 op[1] = match[1];
760 op[2] = match[2];
761 op[3] = match[3];
762 match += dec32table[sequence.offset];
763 ZSTD_copy4(op+4, match);
764 match -= sub2;
765 } else {
766 ZSTD_copy8(op, match);
767 }
768 op += 8; match += 8;
769
770 if (oMatchEnd > oend-(16-MINMATCH)) {
771 if (op < oend_w) {
772 ZSTD_wildcopy(op, match, oend_w - op, ZSTD_overlap_src_before_dst);
773 match += oend_w - op;
774 op = oend_w;
775 }
776 while (op < oMatchEnd) *op++ = *match++;
777 } else {
778 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8, ZSTD_overlap_src_before_dst); /* works even if matchLength < 8 */
779 }
780 return sequenceLength;
781}
782
783static void
784ZSTD_initFseState(ZSTD_fseState* DStatePtr, BIT_DStream_t* bitD, const ZSTD_seqSymbol* dt)
785{
786 const void* ptr = dt;
787 const ZSTD_seqSymbol_header* const DTableH = (const ZSTD_seqSymbol_header*)ptr;
788 DStatePtr->state = BIT_readBits(bitD, DTableH->tableLog);
789 DEBUGLOG(6, "ZSTD_initFseState : val=%u using %u bits",
790 (U32)DStatePtr->state, DTableH->tableLog);
791 BIT_reloadDStream(bitD);
792 DStatePtr->table = dt + 1;
793}
794
795FORCE_INLINE_TEMPLATE void
796ZSTD_updateFseState(ZSTD_fseState* DStatePtr, BIT_DStream_t* bitD)
797{
798 ZSTD_seqSymbol const DInfo = DStatePtr->table[DStatePtr->state];
799 U32 const nbBits = DInfo.nbBits;
800 size_t const lowBits = BIT_readBits(bitD, nbBits);
801 DStatePtr->state = DInfo.nextState + lowBits;
802}
803
804/* We need to add at most (ZSTD_WINDOWLOG_MAX_32 - 1) bits to read the maximum
805 * offset bits. But we can only read at most (STREAM_ACCUMULATOR_MIN_32 - 1)
806 * bits before reloading. This value is the maximum number of bytes we read
807 * after reloading when we are decoding long offsets.
808 */
809#define LONG_OFFSETS_MAX_EXTRA_BITS_32 \
810 (ZSTD_WINDOWLOG_MAX_32 > STREAM_ACCUMULATOR_MIN_32 \
811 ? ZSTD_WINDOWLOG_MAX_32 - STREAM_ACCUMULATOR_MIN_32 \
812 : 0)
813
814typedef enum { ZSTD_lo_isRegularOffset, ZSTD_lo_isLongOffset=1 } ZSTD_longOffset_e;
815
816#ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
817FORCE_INLINE_TEMPLATE seq_t
818ZSTD_decodeSequence(seqState_t* seqState, const ZSTD_longOffset_e longOffsets)
819{
820 seq_t seq;
821 U32 const llBits = seqState->stateLL.table[seqState->stateLL.state].nbAdditionalBits;
822 U32 const mlBits = seqState->stateML.table[seqState->stateML.state].nbAdditionalBits;
823 U32 const ofBits = seqState->stateOffb.table[seqState->stateOffb.state].nbAdditionalBits;
824 U32 const totalBits = llBits+mlBits+ofBits;
825 U32 const llBase = seqState->stateLL.table[seqState->stateLL.state].baseValue;
826 U32 const mlBase = seqState->stateML.table[seqState->stateML.state].baseValue;
827 U32 const ofBase = seqState->stateOffb.table[seqState->stateOffb.state].baseValue;
828
829 /* sequence */
830 { size_t offset;
831 if (!ofBits)
832 offset = 0;
833 else {
834 ZSTD_STATIC_ASSERT(ZSTD_lo_isLongOffset == 1);
835 ZSTD_STATIC_ASSERT(LONG_OFFSETS_MAX_EXTRA_BITS_32 == 5);
836 assert(ofBits <= MaxOff);
837 if (MEM_32bits() && longOffsets && (ofBits >= STREAM_ACCUMULATOR_MIN_32)) {
838 U32 const extraBits = ofBits - MIN(ofBits, 32 - seqState->DStream.bitsConsumed);
839 offset = ofBase + (BIT_readBitsFast(&seqState->DStream, ofBits - extraBits) << extraBits);
840 BIT_reloadDStream(&seqState->DStream);
841 if (extraBits) offset += BIT_readBitsFast(&seqState->DStream, extraBits);
842 assert(extraBits <= LONG_OFFSETS_MAX_EXTRA_BITS_32); /* to avoid another reload */
843 } else {
844 offset = ofBase + BIT_readBitsFast(&seqState->DStream, ofBits/*>0*/); /* <= (ZSTD_WINDOWLOG_MAX-1) bits */
845 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream);
846 }
847 }
848
849 if (ofBits <= 1) {
850 offset += (llBase==0);
851 if (offset) {
852 size_t temp = (offset==3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
853 temp += !temp; /* 0 is not valid; input is corrupted; force offset to 1 */
854 if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1];
855 seqState->prevOffset[1] = seqState->prevOffset[0];
856 seqState->prevOffset[0] = offset = temp;
857 } else { /* offset == 0 */
858 offset = seqState->prevOffset[0];
859 }
860 } else {
861 seqState->prevOffset[2] = seqState->prevOffset[1];
862 seqState->prevOffset[1] = seqState->prevOffset[0];
863 seqState->prevOffset[0] = offset;
864 }
865 seq.offset = offset;
866 }
867
868 seq.matchLength = mlBase
869 + ((mlBits>0) ? BIT_readBitsFast(&seqState->DStream, mlBits/*>0*/) : 0); /* <= 16 bits */
870 if (MEM_32bits() && (mlBits+llBits >= STREAM_ACCUMULATOR_MIN_32-LONG_OFFSETS_MAX_EXTRA_BITS_32))
871 BIT_reloadDStream(&seqState->DStream);
872 if (MEM_64bits() && (totalBits >= STREAM_ACCUMULATOR_MIN_64-(LLFSELog+MLFSELog+OffFSELog)))
873 BIT_reloadDStream(&seqState->DStream);
874 /* Ensure there are enough bits to read the rest of data in 64-bit mode. */
875 ZSTD_STATIC_ASSERT(16+LLFSELog+MLFSELog+OffFSELog < STREAM_ACCUMULATOR_MIN_64);
876
877 seq.litLength = llBase
878 + ((llBits>0) ? BIT_readBitsFast(&seqState->DStream, llBits/*>0*/) : 0); /* <= 16 bits */
879 if (MEM_32bits())
880 BIT_reloadDStream(&seqState->DStream);
881
882 DEBUGLOG(6, "seq: litL=%u, matchL=%u, offset=%u",
883 (U32)seq.litLength, (U32)seq.matchLength, (U32)seq.offset);
884
885 /* ANS state update */
886 ZSTD_updateFseState(&seqState->stateLL, &seqState->DStream); /* <= 9 bits */
887 ZSTD_updateFseState(&seqState->stateML, &seqState->DStream); /* <= 9 bits */
888 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */
889 ZSTD_updateFseState(&seqState->stateOffb, &seqState->DStream); /* <= 8 bits */
890
891 return seq;
892}
893
894FORCE_INLINE_TEMPLATE size_t
895DONT_VECTORIZE
896ZSTD_decompressSequences_body( ZSTD_DCtx* dctx,
897 void* dst, size_t maxDstSize,
898 const void* seqStart, size_t seqSize, int nbSeq,
899 const ZSTD_longOffset_e isLongOffset)
900{
901 const BYTE* ip = (const BYTE*)seqStart;
902 const BYTE* const iend = ip + seqSize;
903 BYTE* const ostart = (BYTE* const)dst;
904 BYTE* const oend = ostart + maxDstSize;
905 BYTE* op = ostart;
906 const BYTE* litPtr = dctx->litPtr;
907 const BYTE* const litEnd = litPtr + dctx->litSize;
908 const BYTE* const prefixStart = (const BYTE*) (dctx->prefixStart);
909 const BYTE* const vBase = (const BYTE*) (dctx->virtualStart);
910 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
911 DEBUGLOG(5, "ZSTD_decompressSequences_body");
912
913 /* Regen sequences */
914 if (nbSeq) {
915 seqState_t seqState;
916 dctx->fseEntropy = 1;
917 { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->entropy.rep[i]; }
918 RETURN_ERROR_IF(
919 ERR_isError(BIT_initDStream(&seqState.DStream, ip, iend-ip)),
920 corruption_detected);
921 ZSTD_initFseState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
922 ZSTD_initFseState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
923 ZSTD_initFseState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
924
925 ZSTD_STATIC_ASSERT(
926 BIT_DStream_unfinished < BIT_DStream_completed &&
927 BIT_DStream_endOfBuffer < BIT_DStream_completed &&
928 BIT_DStream_completed < BIT_DStream_overflow);
929
930 for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && nbSeq ; ) {
931 nbSeq--;
932 { seq_t const sequence = ZSTD_decodeSequence(&seqState, isLongOffset);
933 size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litEnd, prefixStart, vBase, dictEnd);
934 DEBUGLOG(6, "regenerated sequence size : %u", (U32)oneSeqSize);
935 if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
936 op += oneSeqSize;
937 } }
938
939 /* check if reached exact end */
940 DEBUGLOG(5, "ZSTD_decompressSequences_body: after decode loop, remaining nbSeq : %i", nbSeq);
941 RETURN_ERROR_IF(nbSeq, corruption_detected);
942 RETURN_ERROR_IF(BIT_reloadDStream(&seqState.DStream) < BIT_DStream_completed, corruption_detected);
943 /* save reps for next block */
944 { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]); }
945 }
946
947 /* last literal segment */
948 { size_t const lastLLSize = litEnd - litPtr;
949 RETURN_ERROR_IF(lastLLSize > (size_t)(oend-op), dstSize_tooSmall);
950 memcpy(op, litPtr, lastLLSize);
951 op += lastLLSize;
952 }
953
954 return op-ostart;
955}
956
957static size_t
958ZSTD_decompressSequences_default(ZSTD_DCtx* dctx,
959 void* dst, size_t maxDstSize,
960 const void* seqStart, size_t seqSize, int nbSeq,
961 const ZSTD_longOffset_e isLongOffset)
962{
963 return ZSTD_decompressSequences_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
964}
965#endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */
966
967
968
969#ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
970FORCE_INLINE_TEMPLATE seq_t
971ZSTD_decodeSequenceLong(seqState_t* seqState, ZSTD_longOffset_e const longOffsets)
972{
973 seq_t seq;
974 U32 const llBits = seqState->stateLL.table[seqState->stateLL.state].nbAdditionalBits;
975 U32 const mlBits = seqState->stateML.table[seqState->stateML.state].nbAdditionalBits;
976 U32 const ofBits = seqState->stateOffb.table[seqState->stateOffb.state].nbAdditionalBits;
977 U32 const totalBits = llBits+mlBits+ofBits;
978 U32 const llBase = seqState->stateLL.table[seqState->stateLL.state].baseValue;
979 U32 const mlBase = seqState->stateML.table[seqState->stateML.state].baseValue;
980 U32 const ofBase = seqState->stateOffb.table[seqState->stateOffb.state].baseValue;
981
982 /* sequence */
983 { size_t offset;
984 if (!ofBits)
985 offset = 0;
986 else {
987 ZSTD_STATIC_ASSERT(ZSTD_lo_isLongOffset == 1);
988 ZSTD_STATIC_ASSERT(LONG_OFFSETS_MAX_EXTRA_BITS_32 == 5);
989 assert(ofBits <= MaxOff);
990 if (MEM_32bits() && longOffsets) {
991 U32 const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN_32-1);
992 offset = ofBase + (BIT_readBitsFast(&seqState->DStream, ofBits - extraBits) << extraBits);
993 if (MEM_32bits() || extraBits) BIT_reloadDStream(&seqState->DStream);
994 if (extraBits) offset += BIT_readBitsFast(&seqState->DStream, extraBits);
995 } else {
996 offset = ofBase + BIT_readBitsFast(&seqState->DStream, ofBits); /* <= (ZSTD_WINDOWLOG_MAX-1) bits */
997 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream);
998 }
999 }
1000
1001 if (ofBits <= 1) {
1002 offset += (llBase==0);
1003 if (offset) {
1004 size_t temp = (offset==3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
1005 temp += !temp; /* 0 is not valid; input is corrupted; force offset to 1 */
1006 if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1];
1007 seqState->prevOffset[1] = seqState->prevOffset[0];
1008 seqState->prevOffset[0] = offset = temp;
1009 } else {
1010 offset = seqState->prevOffset[0];
1011 }
1012 } else {
1013 seqState->prevOffset[2] = seqState->prevOffset[1];
1014 seqState->prevOffset[1] = seqState->prevOffset[0];
1015 seqState->prevOffset[0] = offset;
1016 }
1017 seq.offset = offset;
1018 }
1019
1020 seq.matchLength = mlBase + ((mlBits>0) ? BIT_readBitsFast(&seqState->DStream, mlBits) : 0); /* <= 16 bits */
1021 if (MEM_32bits() && (mlBits+llBits >= STREAM_ACCUMULATOR_MIN_32-LONG_OFFSETS_MAX_EXTRA_BITS_32))
1022 BIT_reloadDStream(&seqState->DStream);
1023 if (MEM_64bits() && (totalBits >= STREAM_ACCUMULATOR_MIN_64-(LLFSELog+MLFSELog+OffFSELog)))
1024 BIT_reloadDStream(&seqState->DStream);
1025 /* Verify that there is enough bits to read the rest of the data in 64-bit mode. */
1026 ZSTD_STATIC_ASSERT(16+LLFSELog+MLFSELog+OffFSELog < STREAM_ACCUMULATOR_MIN_64);
1027
1028 seq.litLength = llBase + ((llBits>0) ? BIT_readBitsFast(&seqState->DStream, llBits) : 0); /* <= 16 bits */
1029 if (MEM_32bits())
1030 BIT_reloadDStream(&seqState->DStream);
1031
1032 { size_t const pos = seqState->pos + seq.litLength;
1033 const BYTE* const matchBase = (seq.offset > pos) ? seqState->dictEnd : seqState->prefixStart;
1034 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.
1035 * No consequence though : no memory access will occur, overly large offset will be detected in ZSTD_execSequenceLong() */
1036 seqState->pos = pos + seq.matchLength;
1037 }
1038
1039 /* ANS state update */
1040 ZSTD_updateFseState(&seqState->stateLL, &seqState->DStream); /* <= 9 bits */
1041 ZSTD_updateFseState(&seqState->stateML, &seqState->DStream); /* <= 9 bits */
1042 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */
1043 ZSTD_updateFseState(&seqState->stateOffb, &seqState->DStream); /* <= 8 bits */
1044
1045 return seq;
1046}
1047
1048FORCE_INLINE_TEMPLATE size_t
1049ZSTD_decompressSequencesLong_body(
1050 ZSTD_DCtx* dctx,
1051 void* dst, size_t maxDstSize,
1052 const void* seqStart, size_t seqSize, int nbSeq,
1053 const ZSTD_longOffset_e isLongOffset)
1054{
1055 const BYTE* ip = (const BYTE*)seqStart;
1056 const BYTE* const iend = ip + seqSize;
1057 BYTE* const ostart = (BYTE* const)dst;
1058 BYTE* const oend = ostart + maxDstSize;
1059 BYTE* op = ostart;
1060 const BYTE* litPtr = dctx->litPtr;
1061 const BYTE* const litEnd = litPtr + dctx->litSize;
1062 const BYTE* const prefixStart = (const BYTE*) (dctx->prefixStart);
1063 const BYTE* const dictStart = (const BYTE*) (dctx->virtualStart);
1064 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
1065
1066 /* Regen sequences */
1067 if (nbSeq) {
1068#define STORED_SEQS 4
1069#define STORED_SEQS_MASK (STORED_SEQS-1)
1070#define ADVANCED_SEQS 4
1071 seq_t sequences[STORED_SEQS];
1072 int const seqAdvance = MIN(nbSeq, ADVANCED_SEQS);
1073 seqState_t seqState;
1074 int seqNb;
1075 dctx->fseEntropy = 1;
1076 { int i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->entropy.rep[i]; }
1077 seqState.prefixStart = prefixStart;
1078 seqState.pos = (size_t)(op-prefixStart);
1079 seqState.dictEnd = dictEnd;
1080 assert(iend >= ip);
1081 RETURN_ERROR_IF(
1082 ERR_isError(BIT_initDStream(&seqState.DStream, ip, iend-ip)),
1083 corruption_detected);
1084 ZSTD_initFseState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
1085 ZSTD_initFseState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
1086 ZSTD_initFseState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
1087
1088 /* prepare in advance */
1089 for (seqNb=0; (BIT_reloadDStream(&seqState.DStream) <= BIT_DStream_completed) && (seqNb<seqAdvance); seqNb++) {
1090 sequences[seqNb] = ZSTD_decodeSequenceLong(&seqState, isLongOffset);
1091 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 */
1092 }
1093 RETURN_ERROR_IF(seqNb<seqAdvance, corruption_detected);
1094
1095 /* decode and decompress */
1096 for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (seqNb<nbSeq) ; seqNb++) {
1097 seq_t const sequence = ZSTD_decodeSequenceLong(&seqState, isLongOffset);
1098 size_t const oneSeqSize = ZSTD_execSequenceLong(op, oend, sequences[(seqNb-ADVANCED_SEQS) & STORED_SEQS_MASK], &litPtr, litEnd, prefixStart, dictStart, dictEnd);
1099 if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
1100 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 */
1101 sequences[seqNb & STORED_SEQS_MASK] = sequence;
1102 op += oneSeqSize;
1103 }
1104 RETURN_ERROR_IF(seqNb<nbSeq, corruption_detected);
1105
1106 /* finish queue */
1107 seqNb -= seqAdvance;
1108 for ( ; seqNb<nbSeq ; seqNb++) {
1109 size_t const oneSeqSize = ZSTD_execSequenceLong(op, oend, sequences[seqNb&STORED_SEQS_MASK], &litPtr, litEnd, prefixStart, dictStart, dictEnd);
1110 if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
1111 op += oneSeqSize;
1112 }
1113
1114 /* save reps for next block */
1115 { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]); }
1116 }
1117
1118 /* last literal segment */
1119 { size_t const lastLLSize = litEnd - litPtr;
1120 RETURN_ERROR_IF(lastLLSize > (size_t)(oend-op), dstSize_tooSmall);
1121 memcpy(op, litPtr, lastLLSize);
1122 op += lastLLSize;
1123 }
1124
1125 return op-ostart;
1126}
1127
1128static size_t
1129ZSTD_decompressSequencesLong_default(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{
1134 return ZSTD_decompressSequencesLong_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1135}
1136#endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */
1137
1138
1139
1140#if DYNAMIC_BMI2
1141
1142#ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
1143static TARGET_ATTRIBUTE("bmi2") size_t
1144DONT_VECTORIZE
1145ZSTD_decompressSequences_bmi2(ZSTD_DCtx* dctx,
1146 void* dst, size_t maxDstSize,
1147 const void* seqStart, size_t seqSize, int nbSeq,
1148 const ZSTD_longOffset_e isLongOffset)
1149{
1150 return ZSTD_decompressSequences_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1151}
1152#endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */
1153
1154#ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
1155static TARGET_ATTRIBUTE("bmi2") size_t
1156ZSTD_decompressSequencesLong_bmi2(ZSTD_DCtx* dctx,
1157 void* dst, size_t maxDstSize,
1158 const void* seqStart, size_t seqSize, int nbSeq,
1159 const ZSTD_longOffset_e isLongOffset)
1160{
1161 return ZSTD_decompressSequencesLong_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1162}
1163#endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */
1164
1165#endif /* DYNAMIC_BMI2 */
1166
1167typedef size_t (*ZSTD_decompressSequences_t)(
1168 ZSTD_DCtx* dctx,
1169 void* dst, size_t maxDstSize,
1170 const void* seqStart, size_t seqSize, int nbSeq,
1171 const ZSTD_longOffset_e isLongOffset);
1172
1173#ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
1174static size_t
1175ZSTD_decompressSequences(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize,
1176 const void* seqStart, size_t seqSize, int nbSeq,
1177 const ZSTD_longOffset_e isLongOffset)
1178{
1179 DEBUGLOG(5, "ZSTD_decompressSequences");
1180#if DYNAMIC_BMI2
1181 if (dctx->bmi2) {
1182 return ZSTD_decompressSequences_bmi2(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1183 }
1184#endif
1185 return ZSTD_decompressSequences_default(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1186}
1187#endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */
1188
1189
1190#ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
1191/* ZSTD_decompressSequencesLong() :
1192 * decompression function triggered when a minimum share of offsets is considered "long",
1193 * aka out of cache.
1194 * note : "long" definition seems overloaded here, sometimes meaning "wider than bitstream register", and sometimes meaning "farther than memory cache distance".
1195 * This function will try to mitigate main memory latency through the use of prefetching */
1196static size_t
1197ZSTD_decompressSequencesLong(ZSTD_DCtx* dctx,
1198 void* dst, size_t maxDstSize,
1199 const void* seqStart, size_t seqSize, int nbSeq,
1200 const ZSTD_longOffset_e isLongOffset)
1201{
1202 DEBUGLOG(5, "ZSTD_decompressSequencesLong");
1203#if DYNAMIC_BMI2
1204 if (dctx->bmi2) {
1205 return ZSTD_decompressSequencesLong_bmi2(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1206 }
1207#endif
1208 return ZSTD_decompressSequencesLong_default(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1209}
1210#endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */
1211
1212
1213
1214#if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1215 !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1216/* ZSTD_getLongOffsetsShare() :
1217 * condition : offTable must be valid
1218 * @return : "share" of long offsets (arbitrarily defined as > (1<<23))
1219 * compared to maximum possible of (1<<OffFSELog) */
1220static unsigned
1221ZSTD_getLongOffsetsShare(const ZSTD_seqSymbol* offTable)
1222{
1223 const void* ptr = offTable;
1224 U32 const tableLog = ((const ZSTD_seqSymbol_header*)ptr)[0].tableLog;
1225 const ZSTD_seqSymbol* table = offTable + 1;
1226 U32 const max = 1 << tableLog;
1227 U32 u, total = 0;
1228 DEBUGLOG(5, "ZSTD_getLongOffsetsShare: (tableLog=%u)", tableLog);
1229
1230 assert(max <= (1 << OffFSELog)); /* max not too large */
1231 for (u=0; u<max; u++) {
1232 if (table[u].nbAdditionalBits > 22) total += 1;
1233 }
1234
1235 assert(tableLog <= OffFSELog);
1236 total <<= (OffFSELog - tableLog); /* scale to OffFSELog */
1237
1238 return total;
1239}
1240#endif
1241
1242
1243size_t
1244ZSTD_decompressBlock_internal(ZSTD_DCtx* dctx,
1245 void* dst, size_t dstCapacity,
1246 const void* src, size_t srcSize, const int frame)
1247{ /* blockType == blockCompressed */
1248 const BYTE* ip = (const BYTE*)src;
1249 /* isLongOffset must be true if there are long offsets.
1250 * Offsets are long if they are larger than 2^STREAM_ACCUMULATOR_MIN.
1251 * We don't expect that to be the case in 64-bit mode.
1252 * In block mode, window size is not known, so we have to be conservative.
1253 * (note: but it could be evaluated from current-lowLimit)
1254 */
1255 ZSTD_longOffset_e const isLongOffset = (ZSTD_longOffset_e)(MEM_32bits() && (!frame || (dctx->fParams.windowSize > (1ULL << STREAM_ACCUMULATOR_MIN))));
1256 DEBUGLOG(5, "ZSTD_decompressBlock_internal (size : %u)", (U32)srcSize);
1257
1258 RETURN_ERROR_IF(srcSize >= ZSTD_BLOCKSIZE_MAX, srcSize_wrong);
1259
1260 /* Decode literals section */
1261 { size_t const litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize);
1262 DEBUGLOG(5, "ZSTD_decodeLiteralsBlock : %u", (U32)litCSize);
1263 if (ZSTD_isError(litCSize)) return litCSize;
1264 ip += litCSize;
1265 srcSize -= litCSize;
1266 }
1267
1268 /* Build Decoding Tables */
1269 {
1270 /* These macros control at build-time which decompressor implementation
1271 * we use. If neither is defined, we do some inspection and dispatch at
1272 * runtime.
1273 */
1274#if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1275 !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1276 int usePrefetchDecoder = dctx->ddictIsCold;
1277#endif
1278 int nbSeq;
1279 size_t const seqHSize = ZSTD_decodeSeqHeaders(dctx, &nbSeq, ip, srcSize);
1280 if (ZSTD_isError(seqHSize)) return seqHSize;
1281 ip += seqHSize;
1282 srcSize -= seqHSize;
1283
1284#if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1285 !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1286 if ( !usePrefetchDecoder
1287 && (!frame || (dctx->fParams.windowSize > (1<<24)))
1288 && (nbSeq>ADVANCED_SEQS) ) { /* could probably use a larger nbSeq limit */
1289 U32 const shareLongOffsets = ZSTD_getLongOffsetsShare(dctx->OFTptr);
1290 U32 const minShare = MEM_64bits() ? 7 : 20; /* heuristic values, correspond to 2.73% and 7.81% */
1291 usePrefetchDecoder = (shareLongOffsets >= minShare);
1292 }
1293#endif
1294
1295 dctx->ddictIsCold = 0;
1296
1297#if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1298 !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1299 if (usePrefetchDecoder)
1300#endif
1301#ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
1302 return ZSTD_decompressSequencesLong(dctx, dst, dstCapacity, ip, srcSize, nbSeq, isLongOffset);
1303#endif
1304
1305#ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
1306 /* else */
1307 return ZSTD_decompressSequences(dctx, dst, dstCapacity, ip, srcSize, nbSeq, isLongOffset);
1308#endif
1309 }
1310}
1311
1312
1313size_t ZSTD_decompressBlock(ZSTD_DCtx* dctx,
1314 void* dst, size_t dstCapacity,
1315 const void* src, size_t srcSize)
1316{
1317 size_t dSize;
1318 ZSTD_checkContinuity(dctx, dst);
1319 dSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize, /* frame */ 0);
1320 dctx->previousDstEnd = (char*)dst + dSize;
1321 return dSize;
1322}