1 /**
2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
3 * All rights reserved.
4 *
5 * This source code is licensed under the BSD-style license found in the
6 * LICENSE file in the root directory of https://github.com/facebook/zstd.
7 *
8 * This program is free software; you can redistribute it and/or modify it under
9 * the terms of the GNU General Public License version 2 as published by the
10 * Free Software Foundation. This program is dual-licensed; you may select
11 * either version 2 of the GNU General Public License ("GPL") or BSD license
12 * ("BSD").
13 */
14
15 /*-*************************************
16 * Dependencies
17 ***************************************/
18 #include "fse.h"
19 #include "huf.h"
20 #include "mem.h"
21 #include "zstd_internal.h" /* includes zstd.h */
22 #include <linux/kernel.h>
23 #include <linux/module.h>
24 #include <linux/string.h> /* memset */
25
26 /*-*************************************
27 * Constants
28 ***************************************/
29 static const U32 g_searchStrength = 8; /* control skip over incompressible data */
30 #define HASH_READ_SIZE 8
31 typedef enum { ZSTDcs_created = 0, ZSTDcs_init, ZSTDcs_ongoing, ZSTDcs_ending } ZSTD_compressionStage_e;
32
33 /*-*************************************
34 * Helper functions
35 ***************************************/
ZSTD_compressBound(size_t srcSize)36 size_t ZSTD_compressBound(size_t srcSize) { return FSE_compressBound(srcSize) + 12; }
37
38 /*-*************************************
39 * Sequence storage
40 ***************************************/
ZSTD_resetSeqStore(seqStore_t * ssPtr)41 static void ZSTD_resetSeqStore(seqStore_t *ssPtr)
42 {
43 ssPtr->lit = ssPtr->litStart;
44 ssPtr->sequences = ssPtr->sequencesStart;
45 ssPtr->longLengthID = 0;
46 }
47
48 /*-*************************************
49 * Context memory management
50 ***************************************/
51 struct ZSTD_CCtx_s {
52 const BYTE *nextSrc; /* next block here to continue on curr prefix */
53 const BYTE *base; /* All regular indexes relative to this position */
54 const BYTE *dictBase; /* extDict indexes relative to this position */
55 U32 dictLimit; /* below that point, need extDict */
56 U32 lowLimit; /* below that point, no more data */
57 U32 nextToUpdate; /* index from which to continue dictionary update */
58 U32 nextToUpdate3; /* index from which to continue dictionary update */
59 U32 hashLog3; /* dispatch table : larger == faster, more memory */
60 U32 loadedDictEnd; /* index of end of dictionary */
61 U32 forceWindow; /* force back-references to respect limit of 1<<wLog, even for dictionary */
62 U32 forceRawDict; /* Force loading dictionary in "content-only" mode (no header analysis) */
63 ZSTD_compressionStage_e stage;
64 U32 rep[ZSTD_REP_NUM];
65 U32 repToConfirm[ZSTD_REP_NUM];
66 U32 dictID;
67 ZSTD_parameters params;
68 void *workSpace;
69 size_t workSpaceSize;
70 size_t blockSize;
71 U64 frameContentSize;
72 struct xxh64_state xxhState;
73 ZSTD_customMem customMem;
74
75 seqStore_t seqStore; /* sequences storage ptrs */
76 U32 *hashTable;
77 U32 *hashTable3;
78 U32 *chainTable;
79 HUF_CElt *hufTable;
80 U32 flagStaticTables;
81 HUF_repeat flagStaticHufTable;
82 FSE_CTable offcodeCTable[FSE_CTABLE_SIZE_U32(OffFSELog, MaxOff)];
83 FSE_CTable matchlengthCTable[FSE_CTABLE_SIZE_U32(MLFSELog, MaxML)];
84 FSE_CTable litlengthCTable[FSE_CTABLE_SIZE_U32(LLFSELog, MaxLL)];
85 unsigned tmpCounters[HUF_COMPRESS_WORKSPACE_SIZE_U32];
86 };
87
ZSTD_CCtxWorkspaceBound(ZSTD_compressionParameters cParams)88 size_t ZSTD_CCtxWorkspaceBound(ZSTD_compressionParameters cParams)
89 {
90 size_t const blockSize = MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, (size_t)1 << cParams.windowLog);
91 U32 const divider = (cParams.searchLength == 3) ? 3 : 4;
92 size_t const maxNbSeq = blockSize / divider;
93 size_t const tokenSpace = blockSize + 11 * maxNbSeq;
94 size_t const chainSize = (cParams.strategy == ZSTD_fast) ? 0 : (1 << cParams.chainLog);
95 size_t const hSize = ((size_t)1) << cParams.hashLog;
96 U32 const hashLog3 = (cParams.searchLength > 3) ? 0 : MIN(ZSTD_HASHLOG3_MAX, cParams.windowLog);
97 size_t const h3Size = ((size_t)1) << hashLog3;
98 size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32);
99 size_t const optSpace =
100 ((MaxML + 1) + (MaxLL + 1) + (MaxOff + 1) + (1 << Litbits)) * sizeof(U32) + (ZSTD_OPT_NUM + 1) * (sizeof(ZSTD_match_t) + sizeof(ZSTD_optimal_t));
101 size_t const workspaceSize = tableSpace + (256 * sizeof(U32)) /* huffTable */ + tokenSpace +
102 (((cParams.strategy == ZSTD_btopt) || (cParams.strategy == ZSTD_btopt2)) ? optSpace : 0);
103
104 return ZSTD_ALIGN(sizeof(ZSTD_stack)) + ZSTD_ALIGN(sizeof(ZSTD_CCtx)) + ZSTD_ALIGN(workspaceSize);
105 }
106
ZSTD_createCCtx_advanced(ZSTD_customMem customMem)107 static ZSTD_CCtx *ZSTD_createCCtx_advanced(ZSTD_customMem customMem)
108 {
109 ZSTD_CCtx *cctx;
110 if (!customMem.customAlloc || !customMem.customFree)
111 return NULL;
112 cctx = (ZSTD_CCtx *)ZSTD_malloc(sizeof(ZSTD_CCtx), customMem);
113 if (!cctx)
114 return NULL;
115 memset(cctx, 0, sizeof(ZSTD_CCtx));
116 cctx->customMem = customMem;
117 return cctx;
118 }
119
ZSTD_initCCtx(void * workspace,size_t workspaceSize)120 ZSTD_CCtx *ZSTD_initCCtx(void *workspace, size_t workspaceSize)
121 {
122 ZSTD_customMem const stackMem = ZSTD_initStack(workspace, workspaceSize);
123 ZSTD_CCtx *cctx = ZSTD_createCCtx_advanced(stackMem);
124 if (cctx) {
125 cctx->workSpace = ZSTD_stackAllocAll(cctx->customMem.opaque, &cctx->workSpaceSize);
126 }
127 return cctx;
128 }
129
ZSTD_freeCCtx(ZSTD_CCtx * cctx)130 size_t ZSTD_freeCCtx(ZSTD_CCtx *cctx)
131 {
132 if (cctx == NULL)
133 return 0; /* support free on NULL */
134 ZSTD_free(cctx->workSpace, cctx->customMem);
135 ZSTD_free(cctx, cctx->customMem);
136 return 0; /* reserved as a potential error code in the future */
137 }
138
ZSTD_getSeqStore(const ZSTD_CCtx * ctx)139 const seqStore_t *ZSTD_getSeqStore(const ZSTD_CCtx *ctx) /* hidden interface */ { return &(ctx->seqStore); }
140
ZSTD_getParamsFromCCtx(const ZSTD_CCtx * cctx)141 static ZSTD_parameters ZSTD_getParamsFromCCtx(const ZSTD_CCtx *cctx) { return cctx->params; }
142
143 /** ZSTD_checkParams() :
144 ensure param values remain within authorized range.
145 @return : 0, or an error code if one value is beyond authorized range */
ZSTD_checkCParams(ZSTD_compressionParameters cParams)146 size_t ZSTD_checkCParams(ZSTD_compressionParameters cParams)
147 {
148 #define CLAMPCHECK(val, min, max) \
149 { \
150 if ((val < min) | (val > max)) \
151 return ERROR(compressionParameter_unsupported); \
152 }
153 CLAMPCHECK(cParams.windowLog, ZSTD_WINDOWLOG_MIN, ZSTD_WINDOWLOG_MAX);
154 CLAMPCHECK(cParams.chainLog, ZSTD_CHAINLOG_MIN, ZSTD_CHAINLOG_MAX);
155 CLAMPCHECK(cParams.hashLog, ZSTD_HASHLOG_MIN, ZSTD_HASHLOG_MAX);
156 CLAMPCHECK(cParams.searchLog, ZSTD_SEARCHLOG_MIN, ZSTD_SEARCHLOG_MAX);
157 CLAMPCHECK(cParams.searchLength, ZSTD_SEARCHLENGTH_MIN, ZSTD_SEARCHLENGTH_MAX);
158 CLAMPCHECK(cParams.targetLength, ZSTD_TARGETLENGTH_MIN, ZSTD_TARGETLENGTH_MAX);
159 if ((U32)(cParams.strategy) > (U32)ZSTD_btopt2)
160 return ERROR(compressionParameter_unsupported);
161 return 0;
162 }
163
164 /** ZSTD_cycleLog() :
165 * condition for correct operation : hashLog > 1 */
ZSTD_cycleLog(U32 hashLog,ZSTD_strategy strat)166 static U32 ZSTD_cycleLog(U32 hashLog, ZSTD_strategy strat)
167 {
168 U32 const btScale = ((U32)strat >= (U32)ZSTD_btlazy2);
169 return hashLog - btScale;
170 }
171
172 /** ZSTD_adjustCParams() :
173 optimize `cPar` for a given input (`srcSize` and `dictSize`).
174 mostly downsizing to reduce memory consumption and initialization.
175 Both `srcSize` and `dictSize` are optional (use 0 if unknown),
176 but if both are 0, no optimization can be done.
177 Note : cPar is considered validated at this stage. Use ZSTD_checkParams() to ensure that. */
ZSTD_adjustCParams(ZSTD_compressionParameters cPar,unsigned long long srcSize,size_t dictSize)178 ZSTD_compressionParameters ZSTD_adjustCParams(ZSTD_compressionParameters cPar, unsigned long long srcSize, size_t dictSize)
179 {
180 if (srcSize + dictSize == 0)
181 return cPar; /* no size information available : no adjustment */
182
183 /* resize params, to use less memory when necessary */
184 {
185 U32 const minSrcSize = (srcSize == 0) ? 500 : 0;
186 U64 const rSize = srcSize + dictSize + minSrcSize;
187 if (rSize < ((U64)1 << ZSTD_WINDOWLOG_MAX)) {
188 U32 const srcLog = MAX(ZSTD_HASHLOG_MIN, ZSTD_highbit32((U32)(rSize)-1) + 1);
189 if (cPar.windowLog > srcLog)
190 cPar.windowLog = srcLog;
191 }
192 }
193 if (cPar.hashLog > cPar.windowLog)
194 cPar.hashLog = cPar.windowLog;
195 {
196 U32 const cycleLog = ZSTD_cycleLog(cPar.chainLog, cPar.strategy);
197 if (cycleLog > cPar.windowLog)
198 cPar.chainLog -= (cycleLog - cPar.windowLog);
199 }
200
201 if (cPar.windowLog < ZSTD_WINDOWLOG_ABSOLUTEMIN)
202 cPar.windowLog = ZSTD_WINDOWLOG_ABSOLUTEMIN; /* required for frame header */
203
204 return cPar;
205 }
206
ZSTD_equivalentParams(ZSTD_parameters param1,ZSTD_parameters param2)207 static U32 ZSTD_equivalentParams(ZSTD_parameters param1, ZSTD_parameters param2)
208 {
209 return (param1.cParams.hashLog == param2.cParams.hashLog) & (param1.cParams.chainLog == param2.cParams.chainLog) &
210 (param1.cParams.strategy == param2.cParams.strategy) & ((param1.cParams.searchLength == 3) == (param2.cParams.searchLength == 3));
211 }
212
213 /*! ZSTD_continueCCtx() :
214 reuse CCtx without reset (note : requires no dictionary) */
ZSTD_continueCCtx(ZSTD_CCtx * cctx,ZSTD_parameters params,U64 frameContentSize)215 static size_t ZSTD_continueCCtx(ZSTD_CCtx *cctx, ZSTD_parameters params, U64 frameContentSize)
216 {
217 U32 const end = (U32)(cctx->nextSrc - cctx->base);
218 cctx->params = params;
219 cctx->frameContentSize = frameContentSize;
220 cctx->lowLimit = end;
221 cctx->dictLimit = end;
222 cctx->nextToUpdate = end + 1;
223 cctx->stage = ZSTDcs_init;
224 cctx->dictID = 0;
225 cctx->loadedDictEnd = 0;
226 {
227 int i;
228 for (i = 0; i < ZSTD_REP_NUM; i++)
229 cctx->rep[i] = repStartValue[i];
230 }
231 cctx->seqStore.litLengthSum = 0; /* force reset of btopt stats */
232 xxh64_reset(&cctx->xxhState, 0);
233 return 0;
234 }
235
236 typedef enum { ZSTDcrp_continue, ZSTDcrp_noMemset, ZSTDcrp_fullReset } ZSTD_compResetPolicy_e;
237
238 /*! ZSTD_resetCCtx_advanced() :
239 note : `params` must be validated */
ZSTD_resetCCtx_advanced(ZSTD_CCtx * zc,ZSTD_parameters params,U64 frameContentSize,ZSTD_compResetPolicy_e const crp)240 static size_t ZSTD_resetCCtx_advanced(ZSTD_CCtx *zc, ZSTD_parameters params, U64 frameContentSize, ZSTD_compResetPolicy_e const crp)
241 {
242 if (crp == ZSTDcrp_continue)
243 if (ZSTD_equivalentParams(params, zc->params)) {
244 zc->flagStaticTables = 0;
245 zc->flagStaticHufTable = HUF_repeat_none;
246 return ZSTD_continueCCtx(zc, params, frameContentSize);
247 }
248
249 {
250 size_t const blockSize = MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, (size_t)1 << params.cParams.windowLog);
251 U32 const divider = (params.cParams.searchLength == 3) ? 3 : 4;
252 size_t const maxNbSeq = blockSize / divider;
253 size_t const tokenSpace = blockSize + 11 * maxNbSeq;
254 size_t const chainSize = (params.cParams.strategy == ZSTD_fast) ? 0 : (1 << params.cParams.chainLog);
255 size_t const hSize = ((size_t)1) << params.cParams.hashLog;
256 U32 const hashLog3 = (params.cParams.searchLength > 3) ? 0 : MIN(ZSTD_HASHLOG3_MAX, params.cParams.windowLog);
257 size_t const h3Size = ((size_t)1) << hashLog3;
258 size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32);
259 void *ptr;
260
261 /* Check if workSpace is large enough, alloc a new one if needed */
262 {
263 size_t const optSpace = ((MaxML + 1) + (MaxLL + 1) + (MaxOff + 1) + (1 << Litbits)) * sizeof(U32) +
264 (ZSTD_OPT_NUM + 1) * (sizeof(ZSTD_match_t) + sizeof(ZSTD_optimal_t));
265 size_t const neededSpace = tableSpace + (256 * sizeof(U32)) /* huffTable */ + tokenSpace +
266 (((params.cParams.strategy == ZSTD_btopt) || (params.cParams.strategy == ZSTD_btopt2)) ? optSpace : 0);
267 if (zc->workSpaceSize < neededSpace) {
268 ZSTD_free(zc->workSpace, zc->customMem);
269 zc->workSpace = ZSTD_malloc(neededSpace, zc->customMem);
270 if (zc->workSpace == NULL)
271 return ERROR(memory_allocation);
272 zc->workSpaceSize = neededSpace;
273 }
274 }
275
276 if (crp != ZSTDcrp_noMemset)
277 memset(zc->workSpace, 0, tableSpace); /* reset tables only */
278 xxh64_reset(&zc->xxhState, 0);
279 zc->hashLog3 = hashLog3;
280 zc->hashTable = (U32 *)(zc->workSpace);
281 zc->chainTable = zc->hashTable + hSize;
282 zc->hashTable3 = zc->chainTable + chainSize;
283 ptr = zc->hashTable3 + h3Size;
284 zc->hufTable = (HUF_CElt *)ptr;
285 zc->flagStaticTables = 0;
286 zc->flagStaticHufTable = HUF_repeat_none;
287 ptr = ((U32 *)ptr) + 256; /* note : HUF_CElt* is incomplete type, size is simulated using U32 */
288
289 zc->nextToUpdate = 1;
290 zc->nextSrc = NULL;
291 zc->base = NULL;
292 zc->dictBase = NULL;
293 zc->dictLimit = 0;
294 zc->lowLimit = 0;
295 zc->params = params;
296 zc->blockSize = blockSize;
297 zc->frameContentSize = frameContentSize;
298 {
299 int i;
300 for (i = 0; i < ZSTD_REP_NUM; i++)
301 zc->rep[i] = repStartValue[i];
302 }
303
304 if ((params.cParams.strategy == ZSTD_btopt) || (params.cParams.strategy == ZSTD_btopt2)) {
305 zc->seqStore.litFreq = (U32 *)ptr;
306 zc->seqStore.litLengthFreq = zc->seqStore.litFreq + (1 << Litbits);
307 zc->seqStore.matchLengthFreq = zc->seqStore.litLengthFreq + (MaxLL + 1);
308 zc->seqStore.offCodeFreq = zc->seqStore.matchLengthFreq + (MaxML + 1);
309 ptr = zc->seqStore.offCodeFreq + (MaxOff + 1);
310 zc->seqStore.matchTable = (ZSTD_match_t *)ptr;
311 ptr = zc->seqStore.matchTable + ZSTD_OPT_NUM + 1;
312 zc->seqStore.priceTable = (ZSTD_optimal_t *)ptr;
313 ptr = zc->seqStore.priceTable + ZSTD_OPT_NUM + 1;
314 zc->seqStore.litLengthSum = 0;
315 }
316 zc->seqStore.sequencesStart = (seqDef *)ptr;
317 ptr = zc->seqStore.sequencesStart + maxNbSeq;
318 zc->seqStore.llCode = (BYTE *)ptr;
319 zc->seqStore.mlCode = zc->seqStore.llCode + maxNbSeq;
320 zc->seqStore.ofCode = zc->seqStore.mlCode + maxNbSeq;
321 zc->seqStore.litStart = zc->seqStore.ofCode + maxNbSeq;
322
323 zc->stage = ZSTDcs_init;
324 zc->dictID = 0;
325 zc->loadedDictEnd = 0;
326
327 return 0;
328 }
329 }
330
331 /* ZSTD_invalidateRepCodes() :
332 * ensures next compression will not use repcodes from previous block.
333 * Note : only works with regular variant;
334 * do not use with extDict variant ! */
ZSTD_invalidateRepCodes(ZSTD_CCtx * cctx)335 void ZSTD_invalidateRepCodes(ZSTD_CCtx *cctx)
336 {
337 int i;
338 for (i = 0; i < ZSTD_REP_NUM; i++)
339 cctx->rep[i] = 0;
340 }
341
342 /*! ZSTD_copyCCtx() :
343 * Duplicate an existing context `srcCCtx` into another one `dstCCtx`.
344 * Only works during stage ZSTDcs_init (i.e. after creation, but before first call to ZSTD_compressContinue()).
345 * @return : 0, or an error code */
ZSTD_copyCCtx(ZSTD_CCtx * dstCCtx,const ZSTD_CCtx * srcCCtx,unsigned long long pledgedSrcSize)346 size_t ZSTD_copyCCtx(ZSTD_CCtx *dstCCtx, const ZSTD_CCtx *srcCCtx, unsigned long long pledgedSrcSize)
347 {
348 if (srcCCtx->stage != ZSTDcs_init)
349 return ERROR(stage_wrong);
350
351 memcpy(&dstCCtx->customMem, &srcCCtx->customMem, sizeof(ZSTD_customMem));
352 {
353 ZSTD_parameters params = srcCCtx->params;
354 params.fParams.contentSizeFlag = (pledgedSrcSize > 0);
355 ZSTD_resetCCtx_advanced(dstCCtx, params, pledgedSrcSize, ZSTDcrp_noMemset);
356 }
357
358 /* copy tables */
359 {
360 size_t const chainSize = (srcCCtx->params.cParams.strategy == ZSTD_fast) ? 0 : (1 << srcCCtx->params.cParams.chainLog);
361 size_t const hSize = ((size_t)1) << srcCCtx->params.cParams.hashLog;
362 size_t const h3Size = (size_t)1 << srcCCtx->hashLog3;
363 size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32);
364 memcpy(dstCCtx->workSpace, srcCCtx->workSpace, tableSpace);
365 }
366
367 /* copy dictionary offsets */
368 dstCCtx->nextToUpdate = srcCCtx->nextToUpdate;
369 dstCCtx->nextToUpdate3 = srcCCtx->nextToUpdate3;
370 dstCCtx->nextSrc = srcCCtx->nextSrc;
371 dstCCtx->base = srcCCtx->base;
372 dstCCtx->dictBase = srcCCtx->dictBase;
373 dstCCtx->dictLimit = srcCCtx->dictLimit;
374 dstCCtx->lowLimit = srcCCtx->lowLimit;
375 dstCCtx->loadedDictEnd = srcCCtx->loadedDictEnd;
376 dstCCtx->dictID = srcCCtx->dictID;
377
378 /* copy entropy tables */
379 dstCCtx->flagStaticTables = srcCCtx->flagStaticTables;
380 dstCCtx->flagStaticHufTable = srcCCtx->flagStaticHufTable;
381 if (srcCCtx->flagStaticTables) {
382 memcpy(dstCCtx->litlengthCTable, srcCCtx->litlengthCTable, sizeof(dstCCtx->litlengthCTable));
383 memcpy(dstCCtx->matchlengthCTable, srcCCtx->matchlengthCTable, sizeof(dstCCtx->matchlengthCTable));
384 memcpy(dstCCtx->offcodeCTable, srcCCtx->offcodeCTable, sizeof(dstCCtx->offcodeCTable));
385 }
386 if (srcCCtx->flagStaticHufTable) {
387 memcpy(dstCCtx->hufTable, srcCCtx->hufTable, 256 * 4);
388 }
389
390 return 0;
391 }
392
393 /*! ZSTD_reduceTable() :
394 * reduce table indexes by `reducerValue` */
ZSTD_reduceTable(U32 * const table,U32 const size,U32 const reducerValue)395 static void ZSTD_reduceTable(U32 *const table, U32 const size, U32 const reducerValue)
396 {
397 U32 u;
398 for (u = 0; u < size; u++) {
399 if (table[u] < reducerValue)
400 table[u] = 0;
401 else
402 table[u] -= reducerValue;
403 }
404 }
405
406 /*! ZSTD_reduceIndex() :
407 * rescale all indexes to avoid future overflow (indexes are U32) */
ZSTD_reduceIndex(ZSTD_CCtx * zc,const U32 reducerValue)408 static void ZSTD_reduceIndex(ZSTD_CCtx *zc, const U32 reducerValue)
409 {
410 {
411 U32 const hSize = 1 << zc->params.cParams.hashLog;
412 ZSTD_reduceTable(zc->hashTable, hSize, reducerValue);
413 }
414
415 {
416 U32 const chainSize = (zc->params.cParams.strategy == ZSTD_fast) ? 0 : (1 << zc->params.cParams.chainLog);
417 ZSTD_reduceTable(zc->chainTable, chainSize, reducerValue);
418 }
419
420 {
421 U32 const h3Size = (zc->hashLog3) ? 1 << zc->hashLog3 : 0;
422 ZSTD_reduceTable(zc->hashTable3, h3Size, reducerValue);
423 }
424 }
425
426 /*-*******************************************************
427 * Block entropic compression
428 *********************************************************/
429
430 /* See doc/zstd_compression_format.md for detailed format description */
431
ZSTD_noCompressBlock(void * dst,size_t dstCapacity,const void * src,size_t srcSize)432 size_t ZSTD_noCompressBlock(void *dst, size_t dstCapacity, const void *src, size_t srcSize)
433 {
434 if (srcSize + ZSTD_blockHeaderSize > dstCapacity)
435 return ERROR(dstSize_tooSmall);
436 memcpy((BYTE *)dst + ZSTD_blockHeaderSize, src, srcSize);
437 ZSTD_writeLE24(dst, (U32)(srcSize << 2) + (U32)bt_raw);
438 return ZSTD_blockHeaderSize + srcSize;
439 }
440
ZSTD_noCompressLiterals(void * dst,size_t dstCapacity,const void * src,size_t srcSize)441 static size_t ZSTD_noCompressLiterals(void *dst, size_t dstCapacity, const void *src, size_t srcSize)
442 {
443 BYTE *const ostart = (BYTE * const)dst;
444 U32 const flSize = 1 + (srcSize > 31) + (srcSize > 4095);
445
446 if (srcSize + flSize > dstCapacity)
447 return ERROR(dstSize_tooSmall);
448
449 switch (flSize) {
450 case 1: /* 2 - 1 - 5 */ ostart[0] = (BYTE)((U32)set_basic + (srcSize << 3)); break;
451 case 2: /* 2 - 2 - 12 */ ZSTD_writeLE16(ostart, (U16)((U32)set_basic + (1 << 2) + (srcSize << 4))); break;
452 default: /*note : should not be necessary : flSize is within {1,2,3} */
453 case 3: /* 2 - 2 - 20 */ ZSTD_writeLE32(ostart, (U32)((U32)set_basic + (3 << 2) + (srcSize << 4))); break;
454 }
455
456 memcpy(ostart + flSize, src, srcSize);
457 return srcSize + flSize;
458 }
459
ZSTD_compressRleLiteralsBlock(void * dst,size_t dstCapacity,const void * src,size_t srcSize)460 static size_t ZSTD_compressRleLiteralsBlock(void *dst, size_t dstCapacity, const void *src, size_t srcSize)
461 {
462 BYTE *const ostart = (BYTE * const)dst;
463 U32 const flSize = 1 + (srcSize > 31) + (srcSize > 4095);
464
465 (void)dstCapacity; /* dstCapacity already guaranteed to be >=4, hence large enough */
466
467 switch (flSize) {
468 case 1: /* 2 - 1 - 5 */ ostart[0] = (BYTE)((U32)set_rle + (srcSize << 3)); break;
469 case 2: /* 2 - 2 - 12 */ ZSTD_writeLE16(ostart, (U16)((U32)set_rle + (1 << 2) + (srcSize << 4))); break;
470 default: /*note : should not be necessary : flSize is necessarily within {1,2,3} */
471 case 3: /* 2 - 2 - 20 */ ZSTD_writeLE32(ostart, (U32)((U32)set_rle + (3 << 2) + (srcSize << 4))); break;
472 }
473
474 ostart[flSize] = *(const BYTE *)src;
475 return flSize + 1;
476 }
477
ZSTD_minGain(size_t srcSize)478 static size_t ZSTD_minGain(size_t srcSize) { return (srcSize >> 6) + 2; }
479
ZSTD_compressLiterals(ZSTD_CCtx * zc,void * dst,size_t dstCapacity,const void * src,size_t srcSize)480 static size_t ZSTD_compressLiterals(ZSTD_CCtx *zc, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
481 {
482 size_t const minGain = ZSTD_minGain(srcSize);
483 size_t const lhSize = 3 + (srcSize >= 1 KB) + (srcSize >= 16 KB);
484 BYTE *const ostart = (BYTE *)dst;
485 U32 singleStream = srcSize < 256;
486 symbolEncodingType_e hType = set_compressed;
487 size_t cLitSize;
488
489 /* small ? don't even attempt compression (speed opt) */
490 #define LITERAL_NOENTROPY 63
491 {
492 size_t const minLitSize = zc->flagStaticHufTable == HUF_repeat_valid ? 6 : LITERAL_NOENTROPY;
493 if (srcSize <= minLitSize)
494 return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
495 }
496
497 if (dstCapacity < lhSize + 1)
498 return ERROR(dstSize_tooSmall); /* not enough space for compression */
499 {
500 HUF_repeat repeat = zc->flagStaticHufTable;
501 int const preferRepeat = zc->params.cParams.strategy < ZSTD_lazy ? srcSize <= 1024 : 0;
502 if (repeat == HUF_repeat_valid && lhSize == 3)
503 singleStream = 1;
504 cLitSize = singleStream ? HUF_compress1X_repeat(ostart + lhSize, dstCapacity - lhSize, src, srcSize, 255, 11, zc->tmpCounters,
505 sizeof(zc->tmpCounters), zc->hufTable, &repeat, preferRepeat)
506 : HUF_compress4X_repeat(ostart + lhSize, dstCapacity - lhSize, src, srcSize, 255, 11, zc->tmpCounters,
507 sizeof(zc->tmpCounters), zc->hufTable, &repeat, preferRepeat);
508 if (repeat != HUF_repeat_none) {
509 hType = set_repeat;
510 } /* reused the existing table */
511 else {
512 zc->flagStaticHufTable = HUF_repeat_check;
513 } /* now have a table to reuse */
514 }
515
516 if ((cLitSize == 0) | (cLitSize >= srcSize - minGain)) {
517 zc->flagStaticHufTable = HUF_repeat_none;
518 return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
519 }
520 if (cLitSize == 1) {
521 zc->flagStaticHufTable = HUF_repeat_none;
522 return ZSTD_compressRleLiteralsBlock(dst, dstCapacity, src, srcSize);
523 }
524
525 /* Build header */
526 switch (lhSize) {
527 case 3: /* 2 - 2 - 10 - 10 */
528 {
529 U32 const lhc = hType + ((!singleStream) << 2) + ((U32)srcSize << 4) + ((U32)cLitSize << 14);
530 ZSTD_writeLE24(ostart, lhc);
531 break;
532 }
533 case 4: /* 2 - 2 - 14 - 14 */
534 {
535 U32 const lhc = hType + (2 << 2) + ((U32)srcSize << 4) + ((U32)cLitSize << 18);
536 ZSTD_writeLE32(ostart, lhc);
537 break;
538 }
539 default: /* should not be necessary, lhSize is only {3,4,5} */
540 case 5: /* 2 - 2 - 18 - 18 */
541 {
542 U32 const lhc = hType + (3 << 2) + ((U32)srcSize << 4) + ((U32)cLitSize << 22);
543 ZSTD_writeLE32(ostart, lhc);
544 ostart[4] = (BYTE)(cLitSize >> 10);
545 break;
546 }
547 }
548 return lhSize + cLitSize;
549 }
550
551 static const BYTE LL_Code[64] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 16, 17, 17, 18, 18,
552 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23,
553 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24};
554
555 static const BYTE ML_Code[128] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
556 26, 27, 28, 29, 30, 31, 32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37, 38, 38, 38, 38,
557 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
558 40, 40, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 42, 42, 42, 42, 42, 42, 42, 42,
559 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42};
560
ZSTD_seqToCodes(const seqStore_t * seqStorePtr)561 void ZSTD_seqToCodes(const seqStore_t *seqStorePtr)
562 {
563 BYTE const LL_deltaCode = 19;
564 BYTE const ML_deltaCode = 36;
565 const seqDef *const sequences = seqStorePtr->sequencesStart;
566 BYTE *const llCodeTable = seqStorePtr->llCode;
567 BYTE *const ofCodeTable = seqStorePtr->ofCode;
568 BYTE *const mlCodeTable = seqStorePtr->mlCode;
569 U32 const nbSeq = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
570 U32 u;
571 for (u = 0; u < nbSeq; u++) {
572 U32 const llv = sequences[u].litLength;
573 U32 const mlv = sequences[u].matchLength;
574 llCodeTable[u] = (llv > 63) ? (BYTE)ZSTD_highbit32(llv) + LL_deltaCode : LL_Code[llv];
575 ofCodeTable[u] = (BYTE)ZSTD_highbit32(sequences[u].offset);
576 mlCodeTable[u] = (mlv > 127) ? (BYTE)ZSTD_highbit32(mlv) + ML_deltaCode : ML_Code[mlv];
577 }
578 if (seqStorePtr->longLengthID == 1)
579 llCodeTable[seqStorePtr->longLengthPos] = MaxLL;
580 if (seqStorePtr->longLengthID == 2)
581 mlCodeTable[seqStorePtr->longLengthPos] = MaxML;
582 }
583
ZSTD_compressSequences_internal(ZSTD_CCtx * zc,void * dst,size_t dstCapacity)584 ZSTD_STATIC size_t ZSTD_compressSequences_internal(ZSTD_CCtx *zc, void *dst, size_t dstCapacity)
585 {
586 const int longOffsets = zc->params.cParams.windowLog > STREAM_ACCUMULATOR_MIN;
587 const seqStore_t *seqStorePtr = &(zc->seqStore);
588 FSE_CTable *CTable_LitLength = zc->litlengthCTable;
589 FSE_CTable *CTable_OffsetBits = zc->offcodeCTable;
590 FSE_CTable *CTable_MatchLength = zc->matchlengthCTable;
591 U32 LLtype, Offtype, MLtype; /* compressed, raw or rle */
592 const seqDef *const sequences = seqStorePtr->sequencesStart;
593 const BYTE *const ofCodeTable = seqStorePtr->ofCode;
594 const BYTE *const llCodeTable = seqStorePtr->llCode;
595 const BYTE *const mlCodeTable = seqStorePtr->mlCode;
596 BYTE *const ostart = (BYTE *)dst;
597 BYTE *const oend = ostart + dstCapacity;
598 BYTE *op = ostart;
599 size_t const nbSeq = seqStorePtr->sequences - seqStorePtr->sequencesStart;
600 BYTE *seqHead;
601
602 U32 *count;
603 S16 *norm;
604 U32 *workspace;
605 size_t workspaceSize = sizeof(zc->tmpCounters);
606 {
607 size_t spaceUsed32 = 0;
608 count = (U32 *)zc->tmpCounters + spaceUsed32;
609 spaceUsed32 += MaxSeq + 1;
610 norm = (S16 *)((U32 *)zc->tmpCounters + spaceUsed32);
611 spaceUsed32 += ALIGN(sizeof(S16) * (MaxSeq + 1), sizeof(U32)) >> 2;
612
613 workspace = (U32 *)zc->tmpCounters + spaceUsed32;
614 workspaceSize -= (spaceUsed32 << 2);
615 }
616
617 /* Compress literals */
618 {
619 const BYTE *const literals = seqStorePtr->litStart;
620 size_t const litSize = seqStorePtr->lit - literals;
621 size_t const cSize = ZSTD_compressLiterals(zc, op, dstCapacity, literals, litSize);
622 if (ZSTD_isError(cSize))
623 return cSize;
624 op += cSize;
625 }
626
627 /* Sequences Header */
628 if ((oend - op) < 3 /*max nbSeq Size*/ + 1 /*seqHead */)
629 return ERROR(dstSize_tooSmall);
630 if (nbSeq < 0x7F)
631 *op++ = (BYTE)nbSeq;
632 else if (nbSeq < LONGNBSEQ)
633 op[0] = (BYTE)((nbSeq >> 8) + 0x80), op[1] = (BYTE)nbSeq, op += 2;
634 else
635 op[0] = 0xFF, ZSTD_writeLE16(op + 1, (U16)(nbSeq - LONGNBSEQ)), op += 3;
636 if (nbSeq == 0)
637 return op - ostart;
638
639 /* seqHead : flags for FSE encoding type */
640 seqHead = op++;
641
642 #define MIN_SEQ_FOR_DYNAMIC_FSE 64
643 #define MAX_SEQ_FOR_STATIC_FSE 1000
644
645 /* convert length/distances into codes */
646 ZSTD_seqToCodes(seqStorePtr);
647
648 /* CTable for Literal Lengths */
649 {
650 U32 max = MaxLL;
651 size_t const mostFrequent = FSE_countFast_wksp(count, &max, llCodeTable, nbSeq, workspace);
652 if ((mostFrequent == nbSeq) && (nbSeq > 2)) {
653 *op++ = llCodeTable[0];
654 FSE_buildCTable_rle(CTable_LitLength, (BYTE)max);
655 LLtype = set_rle;
656 } else if ((zc->flagStaticTables) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) {
657 LLtype = set_repeat;
658 } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (LL_defaultNormLog - 1)))) {
659 FSE_buildCTable_wksp(CTable_LitLength, LL_defaultNorm, MaxLL, LL_defaultNormLog, workspace, workspaceSize);
660 LLtype = set_basic;
661 } else {
662 size_t nbSeq_1 = nbSeq;
663 const U32 tableLog = FSE_optimalTableLog(LLFSELog, nbSeq, max);
664 if (count[llCodeTable[nbSeq - 1]] > 1) {
665 count[llCodeTable[nbSeq - 1]]--;
666 nbSeq_1--;
667 }
668 FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max);
669 {
670 size_t const NCountSize = FSE_writeNCount(op, oend - op, norm, max, tableLog); /* overflow protected */
671 if (FSE_isError(NCountSize))
672 return NCountSize;
673 op += NCountSize;
674 }
675 FSE_buildCTable_wksp(CTable_LitLength, norm, max, tableLog, workspace, workspaceSize);
676 LLtype = set_compressed;
677 }
678 }
679
680 /* CTable for Offsets */
681 {
682 U32 max = MaxOff;
683 size_t const mostFrequent = FSE_countFast_wksp(count, &max, ofCodeTable, nbSeq, workspace);
684 if ((mostFrequent == nbSeq) && (nbSeq > 2)) {
685 *op++ = ofCodeTable[0];
686 FSE_buildCTable_rle(CTable_OffsetBits, (BYTE)max);
687 Offtype = set_rle;
688 } else if ((zc->flagStaticTables) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) {
689 Offtype = set_repeat;
690 } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (OF_defaultNormLog - 1)))) {
691 FSE_buildCTable_wksp(CTable_OffsetBits, OF_defaultNorm, MaxOff, OF_defaultNormLog, workspace, workspaceSize);
692 Offtype = set_basic;
693 } else {
694 size_t nbSeq_1 = nbSeq;
695 const U32 tableLog = FSE_optimalTableLog(OffFSELog, nbSeq, max);
696 if (count[ofCodeTable[nbSeq - 1]] > 1) {
697 count[ofCodeTable[nbSeq - 1]]--;
698 nbSeq_1--;
699 }
700 FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max);
701 {
702 size_t const NCountSize = FSE_writeNCount(op, oend - op, norm, max, tableLog); /* overflow protected */
703 if (FSE_isError(NCountSize))
704 return NCountSize;
705 op += NCountSize;
706 }
707 FSE_buildCTable_wksp(CTable_OffsetBits, norm, max, tableLog, workspace, workspaceSize);
708 Offtype = set_compressed;
709 }
710 }
711
712 /* CTable for MatchLengths */
713 {
714 U32 max = MaxML;
715 size_t const mostFrequent = FSE_countFast_wksp(count, &max, mlCodeTable, nbSeq, workspace);
716 if ((mostFrequent == nbSeq) && (nbSeq > 2)) {
717 *op++ = *mlCodeTable;
718 FSE_buildCTable_rle(CTable_MatchLength, (BYTE)max);
719 MLtype = set_rle;
720 } else if ((zc->flagStaticTables) && (nbSeq < MAX_SEQ_FOR_STATIC_FSE)) {
721 MLtype = set_repeat;
722 } else if ((nbSeq < MIN_SEQ_FOR_DYNAMIC_FSE) || (mostFrequent < (nbSeq >> (ML_defaultNormLog - 1)))) {
723 FSE_buildCTable_wksp(CTable_MatchLength, ML_defaultNorm, MaxML, ML_defaultNormLog, workspace, workspaceSize);
724 MLtype = set_basic;
725 } else {
726 size_t nbSeq_1 = nbSeq;
727 const U32 tableLog = FSE_optimalTableLog(MLFSELog, nbSeq, max);
728 if (count[mlCodeTable[nbSeq - 1]] > 1) {
729 count[mlCodeTable[nbSeq - 1]]--;
730 nbSeq_1--;
731 }
732 FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max);
733 {
734 size_t const NCountSize = FSE_writeNCount(op, oend - op, norm, max, tableLog); /* overflow protected */
735 if (FSE_isError(NCountSize))
736 return NCountSize;
737 op += NCountSize;
738 }
739 FSE_buildCTable_wksp(CTable_MatchLength, norm, max, tableLog, workspace, workspaceSize);
740 MLtype = set_compressed;
741 }
742 }
743
744 *seqHead = (BYTE)((LLtype << 6) + (Offtype << 4) + (MLtype << 2));
745 zc->flagStaticTables = 0;
746
747 /* Encoding Sequences */
748 {
749 BIT_CStream_t blockStream;
750 FSE_CState_t stateMatchLength;
751 FSE_CState_t stateOffsetBits;
752 FSE_CState_t stateLitLength;
753
754 CHECK_E(BIT_initCStream(&blockStream, op, oend - op), dstSize_tooSmall); /* not enough space remaining */
755
756 /* first symbols */
757 FSE_initCState2(&stateMatchLength, CTable_MatchLength, mlCodeTable[nbSeq - 1]);
758 FSE_initCState2(&stateOffsetBits, CTable_OffsetBits, ofCodeTable[nbSeq - 1]);
759 FSE_initCState2(&stateLitLength, CTable_LitLength, llCodeTable[nbSeq - 1]);
760 BIT_addBits(&blockStream, sequences[nbSeq - 1].litLength, LL_bits[llCodeTable[nbSeq - 1]]);
761 if (ZSTD_32bits())
762 BIT_flushBits(&blockStream);
763 BIT_addBits(&blockStream, sequences[nbSeq - 1].matchLength, ML_bits[mlCodeTable[nbSeq - 1]]);
764 if (ZSTD_32bits())
765 BIT_flushBits(&blockStream);
766 if (longOffsets) {
767 U32 const ofBits = ofCodeTable[nbSeq - 1];
768 int const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN - 1);
769 if (extraBits) {
770 BIT_addBits(&blockStream, sequences[nbSeq - 1].offset, extraBits);
771 BIT_flushBits(&blockStream);
772 }
773 BIT_addBits(&blockStream, sequences[nbSeq - 1].offset >> extraBits, ofBits - extraBits);
774 } else {
775 BIT_addBits(&blockStream, sequences[nbSeq - 1].offset, ofCodeTable[nbSeq - 1]);
776 }
777 BIT_flushBits(&blockStream);
778
779 {
780 size_t n;
781 for (n = nbSeq - 2; n < nbSeq; n--) { /* intentional underflow */
782 BYTE const llCode = llCodeTable[n];
783 BYTE const ofCode = ofCodeTable[n];
784 BYTE const mlCode = mlCodeTable[n];
785 U32 const llBits = LL_bits[llCode];
786 U32 const ofBits = ofCode; /* 32b*/ /* 64b*/
787 U32 const mlBits = ML_bits[mlCode];
788 /* (7)*/ /* (7)*/
789 FSE_encodeSymbol(&blockStream, &stateOffsetBits, ofCode); /* 15 */ /* 15 */
790 FSE_encodeSymbol(&blockStream, &stateMatchLength, mlCode); /* 24 */ /* 24 */
791 if (ZSTD_32bits())
792 BIT_flushBits(&blockStream); /* (7)*/
793 FSE_encodeSymbol(&blockStream, &stateLitLength, llCode); /* 16 */ /* 33 */
794 if (ZSTD_32bits() || (ofBits + mlBits + llBits >= 64 - 7 - (LLFSELog + MLFSELog + OffFSELog)))
795 BIT_flushBits(&blockStream); /* (7)*/
796 BIT_addBits(&blockStream, sequences[n].litLength, llBits);
797 if (ZSTD_32bits() && ((llBits + mlBits) > 24))
798 BIT_flushBits(&blockStream);
799 BIT_addBits(&blockStream, sequences[n].matchLength, mlBits);
800 if (ZSTD_32bits())
801 BIT_flushBits(&blockStream); /* (7)*/
802 if (longOffsets) {
803 int const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN - 1);
804 if (extraBits) {
805 BIT_addBits(&blockStream, sequences[n].offset, extraBits);
806 BIT_flushBits(&blockStream); /* (7)*/
807 }
808 BIT_addBits(&blockStream, sequences[n].offset >> extraBits, ofBits - extraBits); /* 31 */
809 } else {
810 BIT_addBits(&blockStream, sequences[n].offset, ofBits); /* 31 */
811 }
812 BIT_flushBits(&blockStream); /* (7)*/
813 }
814 }
815
816 FSE_flushCState(&blockStream, &stateMatchLength);
817 FSE_flushCState(&blockStream, &stateOffsetBits);
818 FSE_flushCState(&blockStream, &stateLitLength);
819
820 {
821 size_t const streamSize = BIT_closeCStream(&blockStream);
822 if (streamSize == 0)
823 return ERROR(dstSize_tooSmall); /* not enough space */
824 op += streamSize;
825 }
826 }
827 return op - ostart;
828 }
829
ZSTD_compressSequences(ZSTD_CCtx * zc,void * dst,size_t dstCapacity,size_t srcSize)830 ZSTD_STATIC size_t ZSTD_compressSequences(ZSTD_CCtx *zc, void *dst, size_t dstCapacity, size_t srcSize)
831 {
832 size_t const cSize = ZSTD_compressSequences_internal(zc, dst, dstCapacity);
833 size_t const minGain = ZSTD_minGain(srcSize);
834 size_t const maxCSize = srcSize - minGain;
835 /* If the srcSize <= dstCapacity, then there is enough space to write a
836 * raw uncompressed block. Since we ran out of space, the block must not
837 * be compressible, so fall back to a raw uncompressed block.
838 */
839 int const uncompressibleError = cSize == ERROR(dstSize_tooSmall) && srcSize <= dstCapacity;
840 int i;
841
842 if (ZSTD_isError(cSize) && !uncompressibleError)
843 return cSize;
844 if (cSize >= maxCSize || uncompressibleError) {
845 zc->flagStaticHufTable = HUF_repeat_none;
846 return 0;
847 }
848 /* confirm repcodes */
849 for (i = 0; i < ZSTD_REP_NUM; i++)
850 zc->rep[i] = zc->repToConfirm[i];
851 return cSize;
852 }
853
854 /*! ZSTD_storeSeq() :
855 Store a sequence (literal length, literals, offset code and match length code) into seqStore_t.
856 `offsetCode` : distance to match, or 0 == repCode.
857 `matchCode` : matchLength - MINMATCH
858 */
ZSTD_storeSeq(seqStore_t * seqStorePtr,size_t litLength,const void * literals,U32 offsetCode,size_t matchCode)859 ZSTD_STATIC void ZSTD_storeSeq(seqStore_t *seqStorePtr, size_t litLength, const void *literals, U32 offsetCode, size_t matchCode)
860 {
861 /* copy Literals */
862 ZSTD_wildcopy(seqStorePtr->lit, literals, litLength);
863 seqStorePtr->lit += litLength;
864
865 /* literal Length */
866 if (litLength > 0xFFFF) {
867 seqStorePtr->longLengthID = 1;
868 seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
869 }
870 seqStorePtr->sequences[0].litLength = (U16)litLength;
871
872 /* match offset */
873 seqStorePtr->sequences[0].offset = offsetCode + 1;
874
875 /* match Length */
876 if (matchCode > 0xFFFF) {
877 seqStorePtr->longLengthID = 2;
878 seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
879 }
880 seqStorePtr->sequences[0].matchLength = (U16)matchCode;
881
882 seqStorePtr->sequences++;
883 }
884
885 /*-*************************************
886 * Match length counter
887 ***************************************/
ZSTD_NbCommonBytes(register size_t val)888 static unsigned ZSTD_NbCommonBytes(register size_t val)
889 {
890 if (ZSTD_isLittleEndian()) {
891 if (ZSTD_64bits()) {
892 return (__builtin_ctzll((U64)val) >> 3);
893 } else { /* 32 bits */
894 return (__builtin_ctz((U32)val) >> 3);
895 }
896 } else { /* Big Endian CPU */
897 if (ZSTD_64bits()) {
898 return (__builtin_clzll(val) >> 3);
899 } else { /* 32 bits */
900 return (__builtin_clz((U32)val) >> 3);
901 }
902 }
903 }
904
ZSTD_count(const BYTE * pIn,const BYTE * pMatch,const BYTE * const pInLimit)905 static size_t ZSTD_count(const BYTE *pIn, const BYTE *pMatch, const BYTE *const pInLimit)
906 {
907 const BYTE *const pStart = pIn;
908 const BYTE *const pInLoopLimit = pInLimit - (sizeof(size_t) - 1);
909
910 while (pIn < pInLoopLimit) {
911 size_t const diff = ZSTD_readST(pMatch) ^ ZSTD_readST(pIn);
912 if (!diff) {
913 pIn += sizeof(size_t);
914 pMatch += sizeof(size_t);
915 continue;
916 }
917 pIn += ZSTD_NbCommonBytes(diff);
918 return (size_t)(pIn - pStart);
919 }
920 if (ZSTD_64bits())
921 if ((pIn < (pInLimit - 3)) && (ZSTD_read32(pMatch) == ZSTD_read32(pIn))) {
922 pIn += 4;
923 pMatch += 4;
924 }
925 if ((pIn < (pInLimit - 1)) && (ZSTD_read16(pMatch) == ZSTD_read16(pIn))) {
926 pIn += 2;
927 pMatch += 2;
928 }
929 if ((pIn < pInLimit) && (*pMatch == *pIn))
930 pIn++;
931 return (size_t)(pIn - pStart);
932 }
933
934 /** ZSTD_count_2segments() :
935 * can count match length with `ip` & `match` in 2 different segments.
936 * convention : on reaching mEnd, match count continue starting from iStart
937 */
ZSTD_count_2segments(const BYTE * ip,const BYTE * match,const BYTE * iEnd,const BYTE * mEnd,const BYTE * iStart)938 static size_t ZSTD_count_2segments(const BYTE *ip, const BYTE *match, const BYTE *iEnd, const BYTE *mEnd, const BYTE *iStart)
939 {
940 const BYTE *const vEnd = MIN(ip + (mEnd - match), iEnd);
941 size_t const matchLength = ZSTD_count(ip, match, vEnd);
942 if (match + matchLength != mEnd)
943 return matchLength;
944 return matchLength + ZSTD_count(ip + matchLength, iStart, iEnd);
945 }
946
947 /*-*************************************
948 * Hashes
949 ***************************************/
950 static const U32 prime3bytes = 506832829U;
ZSTD_hash3(U32 u,U32 h)951 static U32 ZSTD_hash3(U32 u, U32 h) { return ((u << (32 - 24)) * prime3bytes) >> (32 - h); }
ZSTD_hash3Ptr(const void * ptr,U32 h)952 ZSTD_STATIC size_t ZSTD_hash3Ptr(const void *ptr, U32 h) { return ZSTD_hash3(ZSTD_readLE32(ptr), h); } /* only in zstd_opt.h */
953
954 static const U32 prime4bytes = 2654435761U;
ZSTD_hash4(U32 u,U32 h)955 static U32 ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32 - h); }
ZSTD_hash4Ptr(const void * ptr,U32 h)956 static size_t ZSTD_hash4Ptr(const void *ptr, U32 h) { return ZSTD_hash4(ZSTD_read32(ptr), h); }
957
958 static const U64 prime5bytes = 889523592379ULL;
ZSTD_hash5(U64 u,U32 h)959 static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u << (64 - 40)) * prime5bytes) >> (64 - h)); }
ZSTD_hash5Ptr(const void * p,U32 h)960 static size_t ZSTD_hash5Ptr(const void *p, U32 h) { return ZSTD_hash5(ZSTD_readLE64(p), h); }
961
962 static const U64 prime6bytes = 227718039650203ULL;
ZSTD_hash6(U64 u,U32 h)963 static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u << (64 - 48)) * prime6bytes) >> (64 - h)); }
ZSTD_hash6Ptr(const void * p,U32 h)964 static size_t ZSTD_hash6Ptr(const void *p, U32 h) { return ZSTD_hash6(ZSTD_readLE64(p), h); }
965
966 static const U64 prime7bytes = 58295818150454627ULL;
ZSTD_hash7(U64 u,U32 h)967 static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u << (64 - 56)) * prime7bytes) >> (64 - h)); }
ZSTD_hash7Ptr(const void * p,U32 h)968 static size_t ZSTD_hash7Ptr(const void *p, U32 h) { return ZSTD_hash7(ZSTD_readLE64(p), h); }
969
970 static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL;
ZSTD_hash8(U64 u,U32 h)971 static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u)*prime8bytes) >> (64 - h)); }
ZSTD_hash8Ptr(const void * p,U32 h)972 static size_t ZSTD_hash8Ptr(const void *p, U32 h) { return ZSTD_hash8(ZSTD_readLE64(p), h); }
973
ZSTD_hashPtr(const void * p,U32 hBits,U32 mls)974 static size_t ZSTD_hashPtr(const void *p, U32 hBits, U32 mls)
975 {
976 switch (mls) {
977 // case 3: return ZSTD_hash3Ptr(p, hBits);
978 default:
979 case 4: return ZSTD_hash4Ptr(p, hBits);
980 case 5: return ZSTD_hash5Ptr(p, hBits);
981 case 6: return ZSTD_hash6Ptr(p, hBits);
982 case 7: return ZSTD_hash7Ptr(p, hBits);
983 case 8: return ZSTD_hash8Ptr(p, hBits);
984 }
985 }
986
987 /*-*************************************
988 * Fast Scan
989 ***************************************/
ZSTD_fillHashTable(ZSTD_CCtx * zc,const void * end,const U32 mls)990 static void ZSTD_fillHashTable(ZSTD_CCtx *zc, const void *end, const U32 mls)
991 {
992 U32 *const hashTable = zc->hashTable;
993 U32 const hBits = zc->params.cParams.hashLog;
994 const BYTE *const base = zc->base;
995 const BYTE *ip = base + zc->nextToUpdate;
996 const BYTE *const iend = ((const BYTE *)end) - HASH_READ_SIZE;
997 const size_t fastHashFillStep = 3;
998
999 while (ip <= iend) {
1000 hashTable[ZSTD_hashPtr(ip, hBits, mls)] = (U32)(ip - base);
1001 ip += fastHashFillStep;
1002 }
1003 }
1004
1005 FORCE_INLINE
ZSTD_compressBlock_fast_generic(ZSTD_CCtx * cctx,const void * src,size_t srcSize,const U32 mls)1006 void ZSTD_compressBlock_fast_generic(ZSTD_CCtx *cctx, const void *src, size_t srcSize, const U32 mls)
1007 {
1008 U32 *const hashTable = cctx->hashTable;
1009 U32 const hBits = cctx->params.cParams.hashLog;
1010 seqStore_t *seqStorePtr = &(cctx->seqStore);
1011 const BYTE *const base = cctx->base;
1012 const BYTE *const istart = (const BYTE *)src;
1013 const BYTE *ip = istart;
1014 const BYTE *anchor = istart;
1015 const U32 lowestIndex = cctx->dictLimit;
1016 const BYTE *const lowest = base + lowestIndex;
1017 const BYTE *const iend = istart + srcSize;
1018 const BYTE *const ilimit = iend - HASH_READ_SIZE;
1019 U32 offset_1 = cctx->rep[0], offset_2 = cctx->rep[1];
1020 U32 offsetSaved = 0;
1021
1022 /* init */
1023 ip += (ip == lowest);
1024 {
1025 U32 const maxRep = (U32)(ip - lowest);
1026 if (offset_2 > maxRep)
1027 offsetSaved = offset_2, offset_2 = 0;
1028 if (offset_1 > maxRep)
1029 offsetSaved = offset_1, offset_1 = 0;
1030 }
1031
1032 /* Main Search Loop */
1033 while (ip < ilimit) { /* < instead of <=, because repcode check at (ip+1) */
1034 size_t mLength;
1035 size_t const h = ZSTD_hashPtr(ip, hBits, mls);
1036 U32 const curr = (U32)(ip - base);
1037 U32 const matchIndex = hashTable[h];
1038 const BYTE *match = base + matchIndex;
1039 hashTable[h] = curr; /* update hash table */
1040
1041 if ((offset_1 > 0) & (ZSTD_read32(ip + 1 - offset_1) == ZSTD_read32(ip + 1))) {
1042 mLength = ZSTD_count(ip + 1 + 4, ip + 1 + 4 - offset_1, iend) + 4;
1043 ip++;
1044 ZSTD_storeSeq(seqStorePtr, ip - anchor, anchor, 0, mLength - MINMATCH);
1045 } else {
1046 U32 offset;
1047 if ((matchIndex <= lowestIndex) || (ZSTD_read32(match) != ZSTD_read32(ip))) {
1048 ip += ((ip - anchor) >> g_searchStrength) + 1;
1049 continue;
1050 }
1051 mLength = ZSTD_count(ip + 4, match + 4, iend) + 4;
1052 offset = (U32)(ip - match);
1053 while (((ip > anchor) & (match > lowest)) && (ip[-1] == match[-1])) {
1054 ip--;
1055 match--;
1056 mLength++;
1057 } /* catch up */
1058 offset_2 = offset_1;
1059 offset_1 = offset;
1060
1061 ZSTD_storeSeq(seqStorePtr, ip - anchor, anchor, offset + ZSTD_REP_MOVE, mLength - MINMATCH);
1062 }
1063
1064 /* match found */
1065 ip += mLength;
1066 anchor = ip;
1067
1068 if (ip <= ilimit) {
1069 /* Fill Table */
1070 hashTable[ZSTD_hashPtr(base + curr + 2, hBits, mls)] = curr + 2; /* here because curr+2 could be > iend-8 */
1071 hashTable[ZSTD_hashPtr(ip - 2, hBits, mls)] = (U32)(ip - 2 - base);
1072 /* check immediate repcode */
1073 while ((ip <= ilimit) && ((offset_2 > 0) & (ZSTD_read32(ip) == ZSTD_read32(ip - offset_2)))) {
1074 /* store sequence */
1075 size_t const rLength = ZSTD_count(ip + 4, ip + 4 - offset_2, iend) + 4;
1076 {
1077 U32 const tmpOff = offset_2;
1078 offset_2 = offset_1;
1079 offset_1 = tmpOff;
1080 } /* swap offset_2 <=> offset_1 */
1081 hashTable[ZSTD_hashPtr(ip, hBits, mls)] = (U32)(ip - base);
1082 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, rLength - MINMATCH);
1083 ip += rLength;
1084 anchor = ip;
1085 continue; /* faster when present ... (?) */
1086 }
1087 }
1088 }
1089
1090 /* save reps for next block */
1091 cctx->repToConfirm[0] = offset_1 ? offset_1 : offsetSaved;
1092 cctx->repToConfirm[1] = offset_2 ? offset_2 : offsetSaved;
1093
1094 /* Last Literals */
1095 {
1096 size_t const lastLLSize = iend - anchor;
1097 memcpy(seqStorePtr->lit, anchor, lastLLSize);
1098 seqStorePtr->lit += lastLLSize;
1099 }
1100 }
1101
ZSTD_compressBlock_fast(ZSTD_CCtx * ctx,const void * src,size_t srcSize)1102 static void ZSTD_compressBlock_fast(ZSTD_CCtx *ctx, const void *src, size_t srcSize)
1103 {
1104 const U32 mls = ctx->params.cParams.searchLength;
1105 switch (mls) {
1106 default: /* includes case 3 */
1107 case 4: ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 4); return;
1108 case 5: ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 5); return;
1109 case 6: ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 6); return;
1110 case 7: ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 7); return;
1111 }
1112 }
1113
ZSTD_compressBlock_fast_extDict_generic(ZSTD_CCtx * ctx,const void * src,size_t srcSize,const U32 mls)1114 static void ZSTD_compressBlock_fast_extDict_generic(ZSTD_CCtx *ctx, const void *src, size_t srcSize, const U32 mls)
1115 {
1116 U32 *hashTable = ctx->hashTable;
1117 const U32 hBits = ctx->params.cParams.hashLog;
1118 seqStore_t *seqStorePtr = &(ctx->seqStore);
1119 const BYTE *const base = ctx->base;
1120 const BYTE *const dictBase = ctx->dictBase;
1121 const BYTE *const istart = (const BYTE *)src;
1122 const BYTE *ip = istart;
1123 const BYTE *anchor = istart;
1124 const U32 lowestIndex = ctx->lowLimit;
1125 const BYTE *const dictStart = dictBase + lowestIndex;
1126 const U32 dictLimit = ctx->dictLimit;
1127 const BYTE *const lowPrefixPtr = base + dictLimit;
1128 const BYTE *const dictEnd = dictBase + dictLimit;
1129 const BYTE *const iend = istart + srcSize;
1130 const BYTE *const ilimit = iend - 8;
1131 U32 offset_1 = ctx->rep[0], offset_2 = ctx->rep[1];
1132
1133 /* Search Loop */
1134 while (ip < ilimit) { /* < instead of <=, because (ip+1) */
1135 const size_t h = ZSTD_hashPtr(ip, hBits, mls);
1136 const U32 matchIndex = hashTable[h];
1137 const BYTE *matchBase = matchIndex < dictLimit ? dictBase : base;
1138 const BYTE *match = matchBase + matchIndex;
1139 const U32 curr = (U32)(ip - base);
1140 const U32 repIndex = curr + 1 - offset_1; /* offset_1 expected <= curr +1 */
1141 const BYTE *repBase = repIndex < dictLimit ? dictBase : base;
1142 const BYTE *repMatch = repBase + repIndex;
1143 size_t mLength;
1144 hashTable[h] = curr; /* update hash table */
1145
1146 if ((((U32)((dictLimit - 1) - repIndex) >= 3) /* intentional underflow */ & (repIndex > lowestIndex)) &&
1147 (ZSTD_read32(repMatch) == ZSTD_read32(ip + 1))) {
1148 const BYTE *repMatchEnd = repIndex < dictLimit ? dictEnd : iend;
1149 mLength = ZSTD_count_2segments(ip + 1 + EQUAL_READ32, repMatch + EQUAL_READ32, iend, repMatchEnd, lowPrefixPtr) + EQUAL_READ32;
1150 ip++;
1151 ZSTD_storeSeq(seqStorePtr, ip - anchor, anchor, 0, mLength - MINMATCH);
1152 } else {
1153 if ((matchIndex < lowestIndex) || (ZSTD_read32(match) != ZSTD_read32(ip))) {
1154 ip += ((ip - anchor) >> g_searchStrength) + 1;
1155 continue;
1156 }
1157 {
1158 const BYTE *matchEnd = matchIndex < dictLimit ? dictEnd : iend;
1159 const BYTE *lowMatchPtr = matchIndex < dictLimit ? dictStart : lowPrefixPtr;
1160 U32 offset;
1161 mLength = ZSTD_count_2segments(ip + EQUAL_READ32, match + EQUAL_READ32, iend, matchEnd, lowPrefixPtr) + EQUAL_READ32;
1162 while (((ip > anchor) & (match > lowMatchPtr)) && (ip[-1] == match[-1])) {
1163 ip--;
1164 match--;
1165 mLength++;
1166 } /* catch up */
1167 offset = curr - matchIndex;
1168 offset_2 = offset_1;
1169 offset_1 = offset;
1170 ZSTD_storeSeq(seqStorePtr, ip - anchor, anchor, offset + ZSTD_REP_MOVE, mLength - MINMATCH);
1171 }
1172 }
1173
1174 /* found a match : store it */
1175 ip += mLength;
1176 anchor = ip;
1177
1178 if (ip <= ilimit) {
1179 /* Fill Table */
1180 hashTable[ZSTD_hashPtr(base + curr + 2, hBits, mls)] = curr + 2;
1181 hashTable[ZSTD_hashPtr(ip - 2, hBits, mls)] = (U32)(ip - 2 - base);
1182 /* check immediate repcode */
1183 while (ip <= ilimit) {
1184 U32 const curr2 = (U32)(ip - base);
1185 U32 const repIndex2 = curr2 - offset_2;
1186 const BYTE *repMatch2 = repIndex2 < dictLimit ? dictBase + repIndex2 : base + repIndex2;
1187 if ((((U32)((dictLimit - 1) - repIndex2) >= 3) & (repIndex2 > lowestIndex)) /* intentional overflow */
1188 && (ZSTD_read32(repMatch2) == ZSTD_read32(ip))) {
1189 const BYTE *const repEnd2 = repIndex2 < dictLimit ? dictEnd : iend;
1190 size_t repLength2 =
1191 ZSTD_count_2segments(ip + EQUAL_READ32, repMatch2 + EQUAL_READ32, iend, repEnd2, lowPrefixPtr) + EQUAL_READ32;
1192 U32 tmpOffset = offset_2;
1193 offset_2 = offset_1;
1194 offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */
1195 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, repLength2 - MINMATCH);
1196 hashTable[ZSTD_hashPtr(ip, hBits, mls)] = curr2;
1197 ip += repLength2;
1198 anchor = ip;
1199 continue;
1200 }
1201 break;
1202 }
1203 }
1204 }
1205
1206 /* save reps for next block */
1207 ctx->repToConfirm[0] = offset_1;
1208 ctx->repToConfirm[1] = offset_2;
1209
1210 /* Last Literals */
1211 {
1212 size_t const lastLLSize = iend - anchor;
1213 memcpy(seqStorePtr->lit, anchor, lastLLSize);
1214 seqStorePtr->lit += lastLLSize;
1215 }
1216 }
1217
ZSTD_compressBlock_fast_extDict(ZSTD_CCtx * ctx,const void * src,size_t srcSize)1218 static void ZSTD_compressBlock_fast_extDict(ZSTD_CCtx *ctx, const void *src, size_t srcSize)
1219 {
1220 U32 const mls = ctx->params.cParams.searchLength;
1221 switch (mls) {
1222 default: /* includes case 3 */
1223 case 4: ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 4); return;
1224 case 5: ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 5); return;
1225 case 6: ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 6); return;
1226 case 7: ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 7); return;
1227 }
1228 }
1229
1230 /*-*************************************
1231 * Double Fast
1232 ***************************************/
ZSTD_fillDoubleHashTable(ZSTD_CCtx * cctx,const void * end,const U32 mls)1233 static void ZSTD_fillDoubleHashTable(ZSTD_CCtx *cctx, const void *end, const U32 mls)
1234 {
1235 U32 *const hashLarge = cctx->hashTable;
1236 U32 const hBitsL = cctx->params.cParams.hashLog;
1237 U32 *const hashSmall = cctx->chainTable;
1238 U32 const hBitsS = cctx->params.cParams.chainLog;
1239 const BYTE *const base = cctx->base;
1240 const BYTE *ip = base + cctx->nextToUpdate;
1241 const BYTE *const iend = ((const BYTE *)end) - HASH_READ_SIZE;
1242 const size_t fastHashFillStep = 3;
1243
1244 while (ip <= iend) {
1245 hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = (U32)(ip - base);
1246 hashLarge[ZSTD_hashPtr(ip, hBitsL, 8)] = (U32)(ip - base);
1247 ip += fastHashFillStep;
1248 }
1249 }
1250
1251 FORCE_INLINE
ZSTD_compressBlock_doubleFast_generic(ZSTD_CCtx * cctx,const void * src,size_t srcSize,const U32 mls)1252 void ZSTD_compressBlock_doubleFast_generic(ZSTD_CCtx *cctx, const void *src, size_t srcSize, const U32 mls)
1253 {
1254 U32 *const hashLong = cctx->hashTable;
1255 const U32 hBitsL = cctx->params.cParams.hashLog;
1256 U32 *const hashSmall = cctx->chainTable;
1257 const U32 hBitsS = cctx->params.cParams.chainLog;
1258 seqStore_t *seqStorePtr = &(cctx->seqStore);
1259 const BYTE *const base = cctx->base;
1260 const BYTE *const istart = (const BYTE *)src;
1261 const BYTE *ip = istart;
1262 const BYTE *anchor = istart;
1263 const U32 lowestIndex = cctx->dictLimit;
1264 const BYTE *const lowest = base + lowestIndex;
1265 const BYTE *const iend = istart + srcSize;
1266 const BYTE *const ilimit = iend - HASH_READ_SIZE;
1267 U32 offset_1 = cctx->rep[0], offset_2 = cctx->rep[1];
1268 U32 offsetSaved = 0;
1269
1270 /* init */
1271 ip += (ip == lowest);
1272 {
1273 U32 const maxRep = (U32)(ip - lowest);
1274 if (offset_2 > maxRep)
1275 offsetSaved = offset_2, offset_2 = 0;
1276 if (offset_1 > maxRep)
1277 offsetSaved = offset_1, offset_1 = 0;
1278 }
1279
1280 /* Main Search Loop */
1281 while (ip < ilimit) { /* < instead of <=, because repcode check at (ip+1) */
1282 size_t mLength;
1283 size_t const h2 = ZSTD_hashPtr(ip, hBitsL, 8);
1284 size_t const h = ZSTD_hashPtr(ip, hBitsS, mls);
1285 U32 const curr = (U32)(ip - base);
1286 U32 const matchIndexL = hashLong[h2];
1287 U32 const matchIndexS = hashSmall[h];
1288 const BYTE *matchLong = base + matchIndexL;
1289 const BYTE *match = base + matchIndexS;
1290 hashLong[h2] = hashSmall[h] = curr; /* update hash tables */
1291
1292 if ((offset_1 > 0) & (ZSTD_read32(ip + 1 - offset_1) == ZSTD_read32(ip + 1))) { /* note : by construction, offset_1 <= curr */
1293 mLength = ZSTD_count(ip + 1 + 4, ip + 1 + 4 - offset_1, iend) + 4;
1294 ip++;
1295 ZSTD_storeSeq(seqStorePtr, ip - anchor, anchor, 0, mLength - MINMATCH);
1296 } else {
1297 U32 offset;
1298 if ((matchIndexL > lowestIndex) && (ZSTD_read64(matchLong) == ZSTD_read64(ip))) {
1299 mLength = ZSTD_count(ip + 8, matchLong + 8, iend) + 8;
1300 offset = (U32)(ip - matchLong);
1301 while (((ip > anchor) & (matchLong > lowest)) && (ip[-1] == matchLong[-1])) {
1302 ip--;
1303 matchLong--;
1304 mLength++;
1305 } /* catch up */
1306 } else if ((matchIndexS > lowestIndex) && (ZSTD_read32(match) == ZSTD_read32(ip))) {
1307 size_t const h3 = ZSTD_hashPtr(ip + 1, hBitsL, 8);
1308 U32 const matchIndex3 = hashLong[h3];
1309 const BYTE *match3 = base + matchIndex3;
1310 hashLong[h3] = curr + 1;
1311 if ((matchIndex3 > lowestIndex) && (ZSTD_read64(match3) == ZSTD_read64(ip + 1))) {
1312 mLength = ZSTD_count(ip + 9, match3 + 8, iend) + 8;
1313 ip++;
1314 offset = (U32)(ip - match3);
1315 while (((ip > anchor) & (match3 > lowest)) && (ip[-1] == match3[-1])) {
1316 ip--;
1317 match3--;
1318 mLength++;
1319 } /* catch up */
1320 } else {
1321 mLength = ZSTD_count(ip + 4, match + 4, iend) + 4;
1322 offset = (U32)(ip - match);
1323 while (((ip > anchor) & (match > lowest)) && (ip[-1] == match[-1])) {
1324 ip--;
1325 match--;
1326 mLength++;
1327 } /* catch up */
1328 }
1329 } else {
1330 ip += ((ip - anchor) >> g_searchStrength) + 1;
1331 continue;
1332 }
1333
1334 offset_2 = offset_1;
1335 offset_1 = offset;
1336
1337 ZSTD_storeSeq(seqStorePtr, ip - anchor, anchor, offset + ZSTD_REP_MOVE, mLength - MINMATCH);
1338 }
1339
1340 /* match found */
1341 ip += mLength;
1342 anchor = ip;
1343
1344 if (ip <= ilimit) {
1345 /* Fill Table */
1346 hashLong[ZSTD_hashPtr(base + curr + 2, hBitsL, 8)] = hashSmall[ZSTD_hashPtr(base + curr + 2, hBitsS, mls)] =
1347 curr + 2; /* here because curr+2 could be > iend-8 */
1348 hashLong[ZSTD_hashPtr(ip - 2, hBitsL, 8)] = hashSmall[ZSTD_hashPtr(ip - 2, hBitsS, mls)] = (U32)(ip - 2 - base);
1349
1350 /* check immediate repcode */
1351 while ((ip <= ilimit) && ((offset_2 > 0) & (ZSTD_read32(ip) == ZSTD_read32(ip - offset_2)))) {
1352 /* store sequence */
1353 size_t const rLength = ZSTD_count(ip + 4, ip + 4 - offset_2, iend) + 4;
1354 {
1355 U32 const tmpOff = offset_2;
1356 offset_2 = offset_1;
1357 offset_1 = tmpOff;
1358 } /* swap offset_2 <=> offset_1 */
1359 hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = (U32)(ip - base);
1360 hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = (U32)(ip - base);
1361 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, rLength - MINMATCH);
1362 ip += rLength;
1363 anchor = ip;
1364 continue; /* faster when present ... (?) */
1365 }
1366 }
1367 }
1368
1369 /* save reps for next block */
1370 cctx->repToConfirm[0] = offset_1 ? offset_1 : offsetSaved;
1371 cctx->repToConfirm[1] = offset_2 ? offset_2 : offsetSaved;
1372
1373 /* Last Literals */
1374 {
1375 size_t const lastLLSize = iend - anchor;
1376 memcpy(seqStorePtr->lit, anchor, lastLLSize);
1377 seqStorePtr->lit += lastLLSize;
1378 }
1379 }
1380
ZSTD_compressBlock_doubleFast(ZSTD_CCtx * ctx,const void * src,size_t srcSize)1381 static void ZSTD_compressBlock_doubleFast(ZSTD_CCtx *ctx, const void *src, size_t srcSize)
1382 {
1383 const U32 mls = ctx->params.cParams.searchLength;
1384 switch (mls) {
1385 default: /* includes case 3 */
1386 case 4: ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 4); return;
1387 case 5: ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 5); return;
1388 case 6: ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 6); return;
1389 case 7: ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 7); return;
1390 }
1391 }
1392
ZSTD_compressBlock_doubleFast_extDict_generic(ZSTD_CCtx * ctx,const void * src,size_t srcSize,const U32 mls)1393 static void ZSTD_compressBlock_doubleFast_extDict_generic(ZSTD_CCtx *ctx, const void *src, size_t srcSize, const U32 mls)
1394 {
1395 U32 *const hashLong = ctx->hashTable;
1396 U32 const hBitsL = ctx->params.cParams.hashLog;
1397 U32 *const hashSmall = ctx->chainTable;
1398 U32 const hBitsS = ctx->params.cParams.chainLog;
1399 seqStore_t *seqStorePtr = &(ctx->seqStore);
1400 const BYTE *const base = ctx->base;
1401 const BYTE *const dictBase = ctx->dictBase;
1402 const BYTE *const istart = (const BYTE *)src;
1403 const BYTE *ip = istart;
1404 const BYTE *anchor = istart;
1405 const U32 lowestIndex = ctx->lowLimit;
1406 const BYTE *const dictStart = dictBase + lowestIndex;
1407 const U32 dictLimit = ctx->dictLimit;
1408 const BYTE *const lowPrefixPtr = base + dictLimit;
1409 const BYTE *const dictEnd = dictBase + dictLimit;
1410 const BYTE *const iend = istart + srcSize;
1411 const BYTE *const ilimit = iend - 8;
1412 U32 offset_1 = ctx->rep[0], offset_2 = ctx->rep[1];
1413
1414 /* Search Loop */
1415 while (ip < ilimit) { /* < instead of <=, because (ip+1) */
1416 const size_t hSmall = ZSTD_hashPtr(ip, hBitsS, mls);
1417 const U32 matchIndex = hashSmall[hSmall];
1418 const BYTE *matchBase = matchIndex < dictLimit ? dictBase : base;
1419 const BYTE *match = matchBase + matchIndex;
1420
1421 const size_t hLong = ZSTD_hashPtr(ip, hBitsL, 8);
1422 const U32 matchLongIndex = hashLong[hLong];
1423 const BYTE *matchLongBase = matchLongIndex < dictLimit ? dictBase : base;
1424 const BYTE *matchLong = matchLongBase + matchLongIndex;
1425
1426 const U32 curr = (U32)(ip - base);
1427 const U32 repIndex = curr + 1 - offset_1; /* offset_1 expected <= curr +1 */
1428 const BYTE *repBase = repIndex < dictLimit ? dictBase : base;
1429 const BYTE *repMatch = repBase + repIndex;
1430 size_t mLength;
1431 hashSmall[hSmall] = hashLong[hLong] = curr; /* update hash table */
1432
1433 if ((((U32)((dictLimit - 1) - repIndex) >= 3) /* intentional underflow */ & (repIndex > lowestIndex)) &&
1434 (ZSTD_read32(repMatch) == ZSTD_read32(ip + 1))) {
1435 const BYTE *repMatchEnd = repIndex < dictLimit ? dictEnd : iend;
1436 mLength = ZSTD_count_2segments(ip + 1 + 4, repMatch + 4, iend, repMatchEnd, lowPrefixPtr) + 4;
1437 ip++;
1438 ZSTD_storeSeq(seqStorePtr, ip - anchor, anchor, 0, mLength - MINMATCH);
1439 } else {
1440 if ((matchLongIndex > lowestIndex) && (ZSTD_read64(matchLong) == ZSTD_read64(ip))) {
1441 const BYTE *matchEnd = matchLongIndex < dictLimit ? dictEnd : iend;
1442 const BYTE *lowMatchPtr = matchLongIndex < dictLimit ? dictStart : lowPrefixPtr;
1443 U32 offset;
1444 mLength = ZSTD_count_2segments(ip + 8, matchLong + 8, iend, matchEnd, lowPrefixPtr) + 8;
1445 offset = curr - matchLongIndex;
1446 while (((ip > anchor) & (matchLong > lowMatchPtr)) && (ip[-1] == matchLong[-1])) {
1447 ip--;
1448 matchLong--;
1449 mLength++;
1450 } /* catch up */
1451 offset_2 = offset_1;
1452 offset_1 = offset;
1453 ZSTD_storeSeq(seqStorePtr, ip - anchor, anchor, offset + ZSTD_REP_MOVE, mLength - MINMATCH);
1454
1455 } else if ((matchIndex > lowestIndex) && (ZSTD_read32(match) == ZSTD_read32(ip))) {
1456 size_t const h3 = ZSTD_hashPtr(ip + 1, hBitsL, 8);
1457 U32 const matchIndex3 = hashLong[h3];
1458 const BYTE *const match3Base = matchIndex3 < dictLimit ? dictBase : base;
1459 const BYTE *match3 = match3Base + matchIndex3;
1460 U32 offset;
1461 hashLong[h3] = curr + 1;
1462 if ((matchIndex3 > lowestIndex) && (ZSTD_read64(match3) == ZSTD_read64(ip + 1))) {
1463 const BYTE *matchEnd = matchIndex3 < dictLimit ? dictEnd : iend;
1464 const BYTE *lowMatchPtr = matchIndex3 < dictLimit ? dictStart : lowPrefixPtr;
1465 mLength = ZSTD_count_2segments(ip + 9, match3 + 8, iend, matchEnd, lowPrefixPtr) + 8;
1466 ip++;
1467 offset = curr + 1 - matchIndex3;
1468 while (((ip > anchor) & (match3 > lowMatchPtr)) && (ip[-1] == match3[-1])) {
1469 ip--;
1470 match3--;
1471 mLength++;
1472 } /* catch up */
1473 } else {
1474 const BYTE *matchEnd = matchIndex < dictLimit ? dictEnd : iend;
1475 const BYTE *lowMatchPtr = matchIndex < dictLimit ? dictStart : lowPrefixPtr;
1476 mLength = ZSTD_count_2segments(ip + 4, match + 4, iend, matchEnd, lowPrefixPtr) + 4;
1477 offset = curr - matchIndex;
1478 while (((ip > anchor) & (match > lowMatchPtr)) && (ip[-1] == match[-1])) {
1479 ip--;
1480 match--;
1481 mLength++;
1482 } /* catch up */
1483 }
1484 offset_2 = offset_1;
1485 offset_1 = offset;
1486 ZSTD_storeSeq(seqStorePtr, ip - anchor, anchor, offset + ZSTD_REP_MOVE, mLength - MINMATCH);
1487
1488 } else {
1489 ip += ((ip - anchor) >> g_searchStrength) + 1;
1490 continue;
1491 }
1492 }
1493
1494 /* found a match : store it */
1495 ip += mLength;
1496 anchor = ip;
1497
1498 if (ip <= ilimit) {
1499 /* Fill Table */
1500 hashSmall[ZSTD_hashPtr(base + curr + 2, hBitsS, mls)] = curr + 2;
1501 hashLong[ZSTD_hashPtr(base + curr + 2, hBitsL, 8)] = curr + 2;
1502 hashSmall[ZSTD_hashPtr(ip - 2, hBitsS, mls)] = (U32)(ip - 2 - base);
1503 hashLong[ZSTD_hashPtr(ip - 2, hBitsL, 8)] = (U32)(ip - 2 - base);
1504 /* check immediate repcode */
1505 while (ip <= ilimit) {
1506 U32 const curr2 = (U32)(ip - base);
1507 U32 const repIndex2 = curr2 - offset_2;
1508 const BYTE *repMatch2 = repIndex2 < dictLimit ? dictBase + repIndex2 : base + repIndex2;
1509 if ((((U32)((dictLimit - 1) - repIndex2) >= 3) & (repIndex2 > lowestIndex)) /* intentional overflow */
1510 && (ZSTD_read32(repMatch2) == ZSTD_read32(ip))) {
1511 const BYTE *const repEnd2 = repIndex2 < dictLimit ? dictEnd : iend;
1512 size_t const repLength2 =
1513 ZSTD_count_2segments(ip + EQUAL_READ32, repMatch2 + EQUAL_READ32, iend, repEnd2, lowPrefixPtr) + EQUAL_READ32;
1514 U32 tmpOffset = offset_2;
1515 offset_2 = offset_1;
1516 offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */
1517 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, repLength2 - MINMATCH);
1518 hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = curr2;
1519 hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = curr2;
1520 ip += repLength2;
1521 anchor = ip;
1522 continue;
1523 }
1524 break;
1525 }
1526 }
1527 }
1528
1529 /* save reps for next block */
1530 ctx->repToConfirm[0] = offset_1;
1531 ctx->repToConfirm[1] = offset_2;
1532
1533 /* Last Literals */
1534 {
1535 size_t const lastLLSize = iend - anchor;
1536 memcpy(seqStorePtr->lit, anchor, lastLLSize);
1537 seqStorePtr->lit += lastLLSize;
1538 }
1539 }
1540
ZSTD_compressBlock_doubleFast_extDict(ZSTD_CCtx * ctx,const void * src,size_t srcSize)1541 static void ZSTD_compressBlock_doubleFast_extDict(ZSTD_CCtx *ctx, const void *src, size_t srcSize)
1542 {
1543 U32 const mls = ctx->params.cParams.searchLength;
1544 switch (mls) {
1545 default: /* includes case 3 */
1546 case 4: ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 4); return;
1547 case 5: ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 5); return;
1548 case 6: ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 6); return;
1549 case 7: ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 7); return;
1550 }
1551 }
1552
1553 /*-*************************************
1554 * Binary Tree search
1555 ***************************************/
1556 /** ZSTD_insertBt1() : add one or multiple positions to tree.
1557 * ip : assumed <= iend-8 .
1558 * @return : nb of positions added */
ZSTD_insertBt1(ZSTD_CCtx * zc,const BYTE * const ip,const U32 mls,const BYTE * const iend,U32 nbCompares,U32 extDict)1559 static U32 ZSTD_insertBt1(ZSTD_CCtx *zc, const BYTE *const ip, const U32 mls, const BYTE *const iend, U32 nbCompares, U32 extDict)
1560 {
1561 U32 *const hashTable = zc->hashTable;
1562 U32 const hashLog = zc->params.cParams.hashLog;
1563 size_t const h = ZSTD_hashPtr(ip, hashLog, mls);
1564 U32 *const bt = zc->chainTable;
1565 U32 const btLog = zc->params.cParams.chainLog - 1;
1566 U32 const btMask = (1 << btLog) - 1;
1567 U32 matchIndex = hashTable[h];
1568 size_t commonLengthSmaller = 0, commonLengthLarger = 0;
1569 const BYTE *const base = zc->base;
1570 const BYTE *const dictBase = zc->dictBase;
1571 const U32 dictLimit = zc->dictLimit;
1572 const BYTE *const dictEnd = dictBase + dictLimit;
1573 const BYTE *const prefixStart = base + dictLimit;
1574 const BYTE *match;
1575 const U32 curr = (U32)(ip - base);
1576 const U32 btLow = btMask >= curr ? 0 : curr - btMask;
1577 U32 *smallerPtr = bt + 2 * (curr & btMask);
1578 U32 *largerPtr = smallerPtr + 1;
1579 U32 dummy32; /* to be nullified at the end */
1580 U32 const windowLow = zc->lowLimit;
1581 U32 matchEndIdx = curr + 8;
1582 size_t bestLength = 8;
1583
1584 hashTable[h] = curr; /* Update Hash Table */
1585
1586 while (nbCompares-- && (matchIndex > windowLow)) {
1587 U32 *const nextPtr = bt + 2 * (matchIndex & btMask);
1588 size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */
1589
1590 if ((!extDict) || (matchIndex + matchLength >= dictLimit)) {
1591 match = base + matchIndex;
1592 if (match[matchLength] == ip[matchLength])
1593 matchLength += ZSTD_count(ip + matchLength + 1, match + matchLength + 1, iend) + 1;
1594 } else {
1595 match = dictBase + matchIndex;
1596 matchLength += ZSTD_count_2segments(ip + matchLength, match + matchLength, iend, dictEnd, prefixStart);
1597 if (matchIndex + matchLength >= dictLimit)
1598 match = base + matchIndex; /* to prepare for next usage of match[matchLength] */
1599 }
1600
1601 if (matchLength > bestLength) {
1602 bestLength = matchLength;
1603 if (matchLength > matchEndIdx - matchIndex)
1604 matchEndIdx = matchIndex + (U32)matchLength;
1605 }
1606
1607 if (ip + matchLength == iend) /* equal : no way to know if inf or sup */
1608 break; /* drop , to guarantee consistency ; miss a bit of compression, but other solutions can corrupt the tree */
1609
1610 if (match[matchLength] < ip[matchLength]) { /* necessarily within correct buffer */
1611 /* match is smaller than curr */
1612 *smallerPtr = matchIndex; /* update smaller idx */
1613 commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */
1614 if (matchIndex <= btLow) {
1615 smallerPtr = &dummy32;
1616 break;
1617 } /* beyond tree size, stop the search */
1618 smallerPtr = nextPtr + 1; /* new "smaller" => larger of match */
1619 matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to curr) */
1620 } else {
1621 /* match is larger than curr */
1622 *largerPtr = matchIndex;
1623 commonLengthLarger = matchLength;
1624 if (matchIndex <= btLow) {
1625 largerPtr = &dummy32;
1626 break;
1627 } /* beyond tree size, stop the search */
1628 largerPtr = nextPtr;
1629 matchIndex = nextPtr[0];
1630 }
1631 }
1632
1633 *smallerPtr = *largerPtr = 0;
1634 if (bestLength > 384)
1635 return MIN(192, (U32)(bestLength - 384)); /* speed optimization */
1636 if (matchEndIdx > curr + 8)
1637 return matchEndIdx - curr - 8;
1638 return 1;
1639 }
1640
ZSTD_insertBtAndFindBestMatch(ZSTD_CCtx * zc,const BYTE * const ip,const BYTE * const iend,size_t * offsetPtr,U32 nbCompares,const U32 mls,U32 extDict)1641 static size_t ZSTD_insertBtAndFindBestMatch(ZSTD_CCtx *zc, const BYTE *const ip, const BYTE *const iend, size_t *offsetPtr, U32 nbCompares, const U32 mls,
1642 U32 extDict)
1643 {
1644 U32 *const hashTable = zc->hashTable;
1645 U32 const hashLog = zc->params.cParams.hashLog;
1646 size_t const h = ZSTD_hashPtr(ip, hashLog, mls);
1647 U32 *const bt = zc->chainTable;
1648 U32 const btLog = zc->params.cParams.chainLog - 1;
1649 U32 const btMask = (1 << btLog) - 1;
1650 U32 matchIndex = hashTable[h];
1651 size_t commonLengthSmaller = 0, commonLengthLarger = 0;
1652 const BYTE *const base = zc->base;
1653 const BYTE *const dictBase = zc->dictBase;
1654 const U32 dictLimit = zc->dictLimit;
1655 const BYTE *const dictEnd = dictBase + dictLimit;
1656 const BYTE *const prefixStart = base + dictLimit;
1657 const U32 curr = (U32)(ip - base);
1658 const U32 btLow = btMask >= curr ? 0 : curr - btMask;
1659 const U32 windowLow = zc->lowLimit;
1660 U32 *smallerPtr = bt + 2 * (curr & btMask);
1661 U32 *largerPtr = bt + 2 * (curr & btMask) + 1;
1662 U32 matchEndIdx = curr + 8;
1663 U32 dummy32; /* to be nullified at the end */
1664 size_t bestLength = 0;
1665
1666 hashTable[h] = curr; /* Update Hash Table */
1667
1668 while (nbCompares-- && (matchIndex > windowLow)) {
1669 U32 *const nextPtr = bt + 2 * (matchIndex & btMask);
1670 size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */
1671 const BYTE *match;
1672
1673 if ((!extDict) || (matchIndex + matchLength >= dictLimit)) {
1674 match = base + matchIndex;
1675 if (match[matchLength] == ip[matchLength])
1676 matchLength += ZSTD_count(ip + matchLength + 1, match + matchLength + 1, iend) + 1;
1677 } else {
1678 match = dictBase + matchIndex;
1679 matchLength += ZSTD_count_2segments(ip + matchLength, match + matchLength, iend, dictEnd, prefixStart);
1680 if (matchIndex + matchLength >= dictLimit)
1681 match = base + matchIndex; /* to prepare for next usage of match[matchLength] */
1682 }
1683
1684 if (matchLength > bestLength) {
1685 if (matchLength > matchEndIdx - matchIndex)
1686 matchEndIdx = matchIndex + (U32)matchLength;
1687 if ((4 * (int)(matchLength - bestLength)) > (int)(ZSTD_highbit32(curr - matchIndex + 1) - ZSTD_highbit32((U32)offsetPtr[0] + 1)))
1688 bestLength = matchLength, *offsetPtr = ZSTD_REP_MOVE + curr - matchIndex;
1689 if (ip + matchLength == iend) /* equal : no way to know if inf or sup */
1690 break; /* drop, to guarantee consistency (miss a little bit of compression) */
1691 }
1692
1693 if (match[matchLength] < ip[matchLength]) {
1694 /* match is smaller than curr */
1695 *smallerPtr = matchIndex; /* update smaller idx */
1696 commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */
1697 if (matchIndex <= btLow) {
1698 smallerPtr = &dummy32;
1699 break;
1700 } /* beyond tree size, stop the search */
1701 smallerPtr = nextPtr + 1; /* new "smaller" => larger of match */
1702 matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to curr) */
1703 } else {
1704 /* match is larger than curr */
1705 *largerPtr = matchIndex;
1706 commonLengthLarger = matchLength;
1707 if (matchIndex <= btLow) {
1708 largerPtr = &dummy32;
1709 break;
1710 } /* beyond tree size, stop the search */
1711 largerPtr = nextPtr;
1712 matchIndex = nextPtr[0];
1713 }
1714 }
1715
1716 *smallerPtr = *largerPtr = 0;
1717
1718 zc->nextToUpdate = (matchEndIdx > curr + 8) ? matchEndIdx - 8 : curr + 1;
1719 return bestLength;
1720 }
1721
ZSTD_updateTree(ZSTD_CCtx * zc,const BYTE * const ip,const BYTE * const iend,const U32 nbCompares,const U32 mls)1722 static void ZSTD_updateTree(ZSTD_CCtx *zc, const BYTE *const ip, const BYTE *const iend, const U32 nbCompares, const U32 mls)
1723 {
1724 const BYTE *const base = zc->base;
1725 const U32 target = (U32)(ip - base);
1726 U32 idx = zc->nextToUpdate;
1727
1728 while (idx < target)
1729 idx += ZSTD_insertBt1(zc, base + idx, mls, iend, nbCompares, 0);
1730 }
1731
1732 /** ZSTD_BtFindBestMatch() : Tree updater, providing best match */
ZSTD_BtFindBestMatch(ZSTD_CCtx * zc,const BYTE * const ip,const BYTE * const iLimit,size_t * offsetPtr,const U32 maxNbAttempts,const U32 mls)1733 static size_t ZSTD_BtFindBestMatch(ZSTD_CCtx *zc, const BYTE *const ip, const BYTE *const iLimit, size_t *offsetPtr, const U32 maxNbAttempts, const U32 mls)
1734 {
1735 if (ip < zc->base + zc->nextToUpdate)
1736 return 0; /* skipped area */
1737 ZSTD_updateTree(zc, ip, iLimit, maxNbAttempts, mls);
1738 return ZSTD_insertBtAndFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, mls, 0);
1739 }
1740
ZSTD_BtFindBestMatch_selectMLS(ZSTD_CCtx * zc,const BYTE * ip,const BYTE * const iLimit,size_t * offsetPtr,const U32 maxNbAttempts,const U32 matchLengthSearch)1741 static size_t ZSTD_BtFindBestMatch_selectMLS(ZSTD_CCtx *zc, /* Index table will be updated */
1742 const BYTE *ip, const BYTE *const iLimit, size_t *offsetPtr, const U32 maxNbAttempts, const U32 matchLengthSearch)
1743 {
1744 switch (matchLengthSearch) {
1745 default: /* includes case 3 */
1746 case 4: return ZSTD_BtFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4);
1747 case 5: return ZSTD_BtFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5);
1748 case 7:
1749 case 6: return ZSTD_BtFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6);
1750 }
1751 }
1752
ZSTD_updateTree_extDict(ZSTD_CCtx * zc,const BYTE * const ip,const BYTE * const iend,const U32 nbCompares,const U32 mls)1753 static void ZSTD_updateTree_extDict(ZSTD_CCtx *zc, const BYTE *const ip, const BYTE *const iend, const U32 nbCompares, const U32 mls)
1754 {
1755 const BYTE *const base = zc->base;
1756 const U32 target = (U32)(ip - base);
1757 U32 idx = zc->nextToUpdate;
1758
1759 while (idx < target)
1760 idx += ZSTD_insertBt1(zc, base + idx, mls, iend, nbCompares, 1);
1761 }
1762
1763 /** Tree updater, providing best match */
ZSTD_BtFindBestMatch_extDict(ZSTD_CCtx * zc,const BYTE * const ip,const BYTE * const iLimit,size_t * offsetPtr,const U32 maxNbAttempts,const U32 mls)1764 static size_t ZSTD_BtFindBestMatch_extDict(ZSTD_CCtx *zc, const BYTE *const ip, const BYTE *const iLimit, size_t *offsetPtr, const U32 maxNbAttempts,
1765 const U32 mls)
1766 {
1767 if (ip < zc->base + zc->nextToUpdate)
1768 return 0; /* skipped area */
1769 ZSTD_updateTree_extDict(zc, ip, iLimit, maxNbAttempts, mls);
1770 return ZSTD_insertBtAndFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, mls, 1);
1771 }
1772
ZSTD_BtFindBestMatch_selectMLS_extDict(ZSTD_CCtx * zc,const BYTE * ip,const BYTE * const iLimit,size_t * offsetPtr,const U32 maxNbAttempts,const U32 matchLengthSearch)1773 static size_t ZSTD_BtFindBestMatch_selectMLS_extDict(ZSTD_CCtx *zc, /* Index table will be updated */
1774 const BYTE *ip, const BYTE *const iLimit, size_t *offsetPtr, const U32 maxNbAttempts,
1775 const U32 matchLengthSearch)
1776 {
1777 switch (matchLengthSearch) {
1778 default: /* includes case 3 */
1779 case 4: return ZSTD_BtFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4);
1780 case 5: return ZSTD_BtFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5);
1781 case 7:
1782 case 6: return ZSTD_BtFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6);
1783 }
1784 }
1785
1786 /* *********************************
1787 * Hash Chain
1788 ***********************************/
1789 #define NEXT_IN_CHAIN(d, mask) chainTable[(d)&mask]
1790
1791 /* Update chains up to ip (excluded)
1792 Assumption : always within prefix (i.e. not within extDict) */
1793 FORCE_INLINE
ZSTD_insertAndFindFirstIndex(ZSTD_CCtx * zc,const BYTE * ip,U32 mls)1794 U32 ZSTD_insertAndFindFirstIndex(ZSTD_CCtx *zc, const BYTE *ip, U32 mls)
1795 {
1796 U32 *const hashTable = zc->hashTable;
1797 const U32 hashLog = zc->params.cParams.hashLog;
1798 U32 *const chainTable = zc->chainTable;
1799 const U32 chainMask = (1 << zc->params.cParams.chainLog) - 1;
1800 const BYTE *const base = zc->base;
1801 const U32 target = (U32)(ip - base);
1802 U32 idx = zc->nextToUpdate;
1803
1804 while (idx < target) { /* catch up */
1805 size_t const h = ZSTD_hashPtr(base + idx, hashLog, mls);
1806 NEXT_IN_CHAIN(idx, chainMask) = hashTable[h];
1807 hashTable[h] = idx;
1808 idx++;
1809 }
1810
1811 zc->nextToUpdate = target;
1812 return hashTable[ZSTD_hashPtr(ip, hashLog, mls)];
1813 }
1814
1815 /* inlining is important to hardwire a hot branch (template emulation) */
1816 FORCE_INLINE
ZSTD_HcFindBestMatch_generic(ZSTD_CCtx * zc,const BYTE * const ip,const BYTE * const iLimit,size_t * offsetPtr,const U32 maxNbAttempts,const U32 mls,const U32 extDict)1817 size_t ZSTD_HcFindBestMatch_generic(ZSTD_CCtx *zc, /* Index table will be updated */
1818 const BYTE *const ip, const BYTE *const iLimit, size_t *offsetPtr, const U32 maxNbAttempts, const U32 mls,
1819 const U32 extDict)
1820 {
1821 U32 *const chainTable = zc->chainTable;
1822 const U32 chainSize = (1 << zc->params.cParams.chainLog);
1823 const U32 chainMask = chainSize - 1;
1824 const BYTE *const base = zc->base;
1825 const BYTE *const dictBase = zc->dictBase;
1826 const U32 dictLimit = zc->dictLimit;
1827 const BYTE *const prefixStart = base + dictLimit;
1828 const BYTE *const dictEnd = dictBase + dictLimit;
1829 const U32 lowLimit = zc->lowLimit;
1830 const U32 curr = (U32)(ip - base);
1831 const U32 minChain = curr > chainSize ? curr - chainSize : 0;
1832 int nbAttempts = maxNbAttempts;
1833 size_t ml = EQUAL_READ32 - 1;
1834
1835 /* HC4 match finder */
1836 U32 matchIndex = ZSTD_insertAndFindFirstIndex(zc, ip, mls);
1837
1838 for (; (matchIndex > lowLimit) & (nbAttempts > 0); nbAttempts--) {
1839 const BYTE *match;
1840 size_t currMl = 0;
1841 if ((!extDict) || matchIndex >= dictLimit) {
1842 match = base + matchIndex;
1843 if (match[ml] == ip[ml]) /* potentially better */
1844 currMl = ZSTD_count(ip, match, iLimit);
1845 } else {
1846 match = dictBase + matchIndex;
1847 if (ZSTD_read32(match) == ZSTD_read32(ip)) /* assumption : matchIndex <= dictLimit-4 (by table construction) */
1848 currMl = ZSTD_count_2segments(ip + EQUAL_READ32, match + EQUAL_READ32, iLimit, dictEnd, prefixStart) + EQUAL_READ32;
1849 }
1850
1851 /* save best solution */
1852 if (currMl > ml) {
1853 ml = currMl;
1854 *offsetPtr = curr - matchIndex + ZSTD_REP_MOVE;
1855 if (ip + currMl == iLimit)
1856 break; /* best possible, and avoid read overflow*/
1857 }
1858
1859 if (matchIndex <= minChain)
1860 break;
1861 matchIndex = NEXT_IN_CHAIN(matchIndex, chainMask);
1862 }
1863
1864 return ml;
1865 }
1866
ZSTD_HcFindBestMatch_selectMLS(ZSTD_CCtx * zc,const BYTE * ip,const BYTE * const iLimit,size_t * offsetPtr,const U32 maxNbAttempts,const U32 matchLengthSearch)1867 FORCE_INLINE size_t ZSTD_HcFindBestMatch_selectMLS(ZSTD_CCtx *zc, const BYTE *ip, const BYTE *const iLimit, size_t *offsetPtr, const U32 maxNbAttempts,
1868 const U32 matchLengthSearch)
1869 {
1870 switch (matchLengthSearch) {
1871 default: /* includes case 3 */
1872 case 4: return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4, 0);
1873 case 5: return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5, 0);
1874 case 7:
1875 case 6: return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6, 0);
1876 }
1877 }
1878
ZSTD_HcFindBestMatch_extDict_selectMLS(ZSTD_CCtx * zc,const BYTE * ip,const BYTE * const iLimit,size_t * offsetPtr,const U32 maxNbAttempts,const U32 matchLengthSearch)1879 FORCE_INLINE size_t ZSTD_HcFindBestMatch_extDict_selectMLS(ZSTD_CCtx *zc, const BYTE *ip, const BYTE *const iLimit, size_t *offsetPtr, const U32 maxNbAttempts,
1880 const U32 matchLengthSearch)
1881 {
1882 switch (matchLengthSearch) {
1883 default: /* includes case 3 */
1884 case 4: return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4, 1);
1885 case 5: return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5, 1);
1886 case 7:
1887 case 6: return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6, 1);
1888 }
1889 }
1890
1891 /* *******************************
1892 * Common parser - lazy strategy
1893 *********************************/
1894 FORCE_INLINE
ZSTD_compressBlock_lazy_generic(ZSTD_CCtx * ctx,const void * src,size_t srcSize,const U32 searchMethod,const U32 depth)1895 void ZSTD_compressBlock_lazy_generic(ZSTD_CCtx *ctx, const void *src, size_t srcSize, const U32 searchMethod, const U32 depth)
1896 {
1897 seqStore_t *seqStorePtr = &(ctx->seqStore);
1898 const BYTE *const istart = (const BYTE *)src;
1899 const BYTE *ip = istart;
1900 const BYTE *anchor = istart;
1901 const BYTE *const iend = istart + srcSize;
1902 const BYTE *const ilimit = iend - 8;
1903 const BYTE *const base = ctx->base + ctx->dictLimit;
1904
1905 U32 const maxSearches = 1 << ctx->params.cParams.searchLog;
1906 U32 const mls = ctx->params.cParams.searchLength;
1907
1908 typedef size_t (*searchMax_f)(ZSTD_CCtx * zc, const BYTE *ip, const BYTE *iLimit, size_t *offsetPtr, U32 maxNbAttempts, U32 matchLengthSearch);
1909 searchMax_f const searchMax = searchMethod ? ZSTD_BtFindBestMatch_selectMLS : ZSTD_HcFindBestMatch_selectMLS;
1910 U32 offset_1 = ctx->rep[0], offset_2 = ctx->rep[1], savedOffset = 0;
1911
1912 /* init */
1913 ip += (ip == base);
1914 ctx->nextToUpdate3 = ctx->nextToUpdate;
1915 {
1916 U32 const maxRep = (U32)(ip - base);
1917 if (offset_2 > maxRep)
1918 savedOffset = offset_2, offset_2 = 0;
1919 if (offset_1 > maxRep)
1920 savedOffset = offset_1, offset_1 = 0;
1921 }
1922
1923 /* Match Loop */
1924 while (ip < ilimit) {
1925 size_t matchLength = 0;
1926 size_t offset = 0;
1927 const BYTE *start = ip + 1;
1928
1929 /* check repCode */
1930 if ((offset_1 > 0) & (ZSTD_read32(ip + 1) == ZSTD_read32(ip + 1 - offset_1))) {
1931 /* repcode : we take it */
1932 matchLength = ZSTD_count(ip + 1 + EQUAL_READ32, ip + 1 + EQUAL_READ32 - offset_1, iend) + EQUAL_READ32;
1933 if (depth == 0)
1934 goto _storeSequence;
1935 }
1936
1937 /* first search (depth 0) */
1938 {
1939 size_t offsetFound = 99999999;
1940 size_t const ml2 = searchMax(ctx, ip, iend, &offsetFound, maxSearches, mls);
1941 if (ml2 > matchLength)
1942 matchLength = ml2, start = ip, offset = offsetFound;
1943 }
1944
1945 if (matchLength < EQUAL_READ32) {
1946 ip += ((ip - anchor) >> g_searchStrength) + 1; /* jump faster over incompressible sections */
1947 continue;
1948 }
1949
1950 /* let's try to find a better solution */
1951 if (depth >= 1)
1952 while (ip < ilimit) {
1953 ip++;
1954 if ((offset) && ((offset_1 > 0) & (ZSTD_read32(ip) == ZSTD_read32(ip - offset_1)))) {
1955 size_t const mlRep = ZSTD_count(ip + EQUAL_READ32, ip + EQUAL_READ32 - offset_1, iend) + EQUAL_READ32;
1956 int const gain2 = (int)(mlRep * 3);
1957 int const gain1 = (int)(matchLength * 3 - ZSTD_highbit32((U32)offset + 1) + 1);
1958 if ((mlRep >= EQUAL_READ32) && (gain2 > gain1))
1959 matchLength = mlRep, offset = 0, start = ip;
1960 }
1961 {
1962 size_t offset2 = 99999999;
1963 size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls);
1964 int const gain2 = (int)(ml2 * 4 - ZSTD_highbit32((U32)offset2 + 1)); /* raw approx */
1965 int const gain1 = (int)(matchLength * 4 - ZSTD_highbit32((U32)offset + 1) + 4);
1966 if ((ml2 >= EQUAL_READ32) && (gain2 > gain1)) {
1967 matchLength = ml2, offset = offset2, start = ip;
1968 continue; /* search a better one */
1969 }
1970 }
1971
1972 /* let's find an even better one */
1973 if ((depth == 2) && (ip < ilimit)) {
1974 ip++;
1975 if ((offset) && ((offset_1 > 0) & (ZSTD_read32(ip) == ZSTD_read32(ip - offset_1)))) {
1976 size_t const ml2 = ZSTD_count(ip + EQUAL_READ32, ip + EQUAL_READ32 - offset_1, iend) + EQUAL_READ32;
1977 int const gain2 = (int)(ml2 * 4);
1978 int const gain1 = (int)(matchLength * 4 - ZSTD_highbit32((U32)offset + 1) + 1);
1979 if ((ml2 >= EQUAL_READ32) && (gain2 > gain1))
1980 matchLength = ml2, offset = 0, start = ip;
1981 }
1982 {
1983 size_t offset2 = 99999999;
1984 size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls);
1985 int const gain2 = (int)(ml2 * 4 - ZSTD_highbit32((U32)offset2 + 1)); /* raw approx */
1986 int const gain1 = (int)(matchLength * 4 - ZSTD_highbit32((U32)offset + 1) + 7);
1987 if ((ml2 >= EQUAL_READ32) && (gain2 > gain1)) {
1988 matchLength = ml2, offset = offset2, start = ip;
1989 continue;
1990 }
1991 }
1992 }
1993 break; /* nothing found : store previous solution */
1994 }
1995
1996 /* NOTE:
1997 * start[-offset+ZSTD_REP_MOVE-1] is undefined behavior.
1998 * (-offset+ZSTD_REP_MOVE-1) is unsigned, and is added to start, which
1999 * overflows the pointer, which is undefined behavior.
2000 */
2001 /* catch up */
2002 if (offset) {
2003 while ((start > anchor) && (start > base + offset - ZSTD_REP_MOVE) &&
2004 (start[-1] == (start-offset+ZSTD_REP_MOVE)[-1])) /* only search for offset within prefix */
2005 {
2006 start--;
2007 matchLength++;
2008 }
2009 offset_2 = offset_1;
2010 offset_1 = (U32)(offset - ZSTD_REP_MOVE);
2011 }
2012
2013 /* store sequence */
2014 _storeSequence:
2015 {
2016 size_t const litLength = start - anchor;
2017 ZSTD_storeSeq(seqStorePtr, litLength, anchor, (U32)offset, matchLength - MINMATCH);
2018 anchor = ip = start + matchLength;
2019 }
2020
2021 /* check immediate repcode */
2022 while ((ip <= ilimit) && ((offset_2 > 0) & (ZSTD_read32(ip) == ZSTD_read32(ip - offset_2)))) {
2023 /* store sequence */
2024 matchLength = ZSTD_count(ip + EQUAL_READ32, ip + EQUAL_READ32 - offset_2, iend) + EQUAL_READ32;
2025 offset = offset_2;
2026 offset_2 = offset_1;
2027 offset_1 = (U32)offset; /* swap repcodes */
2028 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, matchLength - MINMATCH);
2029 ip += matchLength;
2030 anchor = ip;
2031 continue; /* faster when present ... (?) */
2032 }
2033 }
2034
2035 /* Save reps for next block */
2036 ctx->repToConfirm[0] = offset_1 ? offset_1 : savedOffset;
2037 ctx->repToConfirm[1] = offset_2 ? offset_2 : savedOffset;
2038
2039 /* Last Literals */
2040 {
2041 size_t const lastLLSize = iend - anchor;
2042 memcpy(seqStorePtr->lit, anchor, lastLLSize);
2043 seqStorePtr->lit += lastLLSize;
2044 }
2045 }
2046
ZSTD_compressBlock_btlazy2(ZSTD_CCtx * ctx,const void * src,size_t srcSize)2047 static void ZSTD_compressBlock_btlazy2(ZSTD_CCtx *ctx, const void *src, size_t srcSize) { ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 1, 2); }
2048
ZSTD_compressBlock_lazy2(ZSTD_CCtx * ctx,const void * src,size_t srcSize)2049 static void ZSTD_compressBlock_lazy2(ZSTD_CCtx *ctx, const void *src, size_t srcSize) { ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 0, 2); }
2050
ZSTD_compressBlock_lazy(ZSTD_CCtx * ctx,const void * src,size_t srcSize)2051 static void ZSTD_compressBlock_lazy(ZSTD_CCtx *ctx, const void *src, size_t srcSize) { ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 0, 1); }
2052
ZSTD_compressBlock_greedy(ZSTD_CCtx * ctx,const void * src,size_t srcSize)2053 static void ZSTD_compressBlock_greedy(ZSTD_CCtx *ctx, const void *src, size_t srcSize) { ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 0, 0); }
2054
2055 FORCE_INLINE
ZSTD_compressBlock_lazy_extDict_generic(ZSTD_CCtx * ctx,const void * src,size_t srcSize,const U32 searchMethod,const U32 depth)2056 void ZSTD_compressBlock_lazy_extDict_generic(ZSTD_CCtx *ctx, const void *src, size_t srcSize, const U32 searchMethod, const U32 depth)
2057 {
2058 seqStore_t *seqStorePtr = &(ctx->seqStore);
2059 const BYTE *const istart = (const BYTE *)src;
2060 const BYTE *ip = istart;
2061 const BYTE *anchor = istart;
2062 const BYTE *const iend = istart + srcSize;
2063 const BYTE *const ilimit = iend - 8;
2064 const BYTE *const base = ctx->base;
2065 const U32 dictLimit = ctx->dictLimit;
2066 const U32 lowestIndex = ctx->lowLimit;
2067 const BYTE *const prefixStart = base + dictLimit;
2068 const BYTE *const dictBase = ctx->dictBase;
2069 const BYTE *const dictEnd = dictBase + dictLimit;
2070 const BYTE *const dictStart = dictBase + ctx->lowLimit;
2071
2072 const U32 maxSearches = 1 << ctx->params.cParams.searchLog;
2073 const U32 mls = ctx->params.cParams.searchLength;
2074
2075 typedef size_t (*searchMax_f)(ZSTD_CCtx * zc, const BYTE *ip, const BYTE *iLimit, size_t *offsetPtr, U32 maxNbAttempts, U32 matchLengthSearch);
2076 searchMax_f searchMax = searchMethod ? ZSTD_BtFindBestMatch_selectMLS_extDict : ZSTD_HcFindBestMatch_extDict_selectMLS;
2077
2078 U32 offset_1 = ctx->rep[0], offset_2 = ctx->rep[1];
2079
2080 /* init */
2081 ctx->nextToUpdate3 = ctx->nextToUpdate;
2082 ip += (ip == prefixStart);
2083
2084 /* Match Loop */
2085 while (ip < ilimit) {
2086 size_t matchLength = 0;
2087 size_t offset = 0;
2088 const BYTE *start = ip + 1;
2089 U32 curr = (U32)(ip - base);
2090
2091 /* check repCode */
2092 {
2093 const U32 repIndex = (U32)(curr + 1 - offset_1);
2094 const BYTE *const repBase = repIndex < dictLimit ? dictBase : base;
2095 const BYTE *const repMatch = repBase + repIndex;
2096 if (((U32)((dictLimit - 1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
2097 if (ZSTD_read32(ip + 1) == ZSTD_read32(repMatch)) {
2098 /* repcode detected we should take it */
2099 const BYTE *const repEnd = repIndex < dictLimit ? dictEnd : iend;
2100 matchLength =
2101 ZSTD_count_2segments(ip + 1 + EQUAL_READ32, repMatch + EQUAL_READ32, iend, repEnd, prefixStart) + EQUAL_READ32;
2102 if (depth == 0)
2103 goto _storeSequence;
2104 }
2105 }
2106
2107 /* first search (depth 0) */
2108 {
2109 size_t offsetFound = 99999999;
2110 size_t const ml2 = searchMax(ctx, ip, iend, &offsetFound, maxSearches, mls);
2111 if (ml2 > matchLength)
2112 matchLength = ml2, start = ip, offset = offsetFound;
2113 }
2114
2115 if (matchLength < EQUAL_READ32) {
2116 ip += ((ip - anchor) >> g_searchStrength) + 1; /* jump faster over incompressible sections */
2117 continue;
2118 }
2119
2120 /* let's try to find a better solution */
2121 if (depth >= 1)
2122 while (ip < ilimit) {
2123 ip++;
2124 curr++;
2125 /* check repCode */
2126 if (offset) {
2127 const U32 repIndex = (U32)(curr - offset_1);
2128 const BYTE *const repBase = repIndex < dictLimit ? dictBase : base;
2129 const BYTE *const repMatch = repBase + repIndex;
2130 if (((U32)((dictLimit - 1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
2131 if (ZSTD_read32(ip) == ZSTD_read32(repMatch)) {
2132 /* repcode detected */
2133 const BYTE *const repEnd = repIndex < dictLimit ? dictEnd : iend;
2134 size_t const repLength =
2135 ZSTD_count_2segments(ip + EQUAL_READ32, repMatch + EQUAL_READ32, iend, repEnd, prefixStart) +
2136 EQUAL_READ32;
2137 int const gain2 = (int)(repLength * 3);
2138 int const gain1 = (int)(matchLength * 3 - ZSTD_highbit32((U32)offset + 1) + 1);
2139 if ((repLength >= EQUAL_READ32) && (gain2 > gain1))
2140 matchLength = repLength, offset = 0, start = ip;
2141 }
2142 }
2143
2144 /* search match, depth 1 */
2145 {
2146 size_t offset2 = 99999999;
2147 size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls);
2148 int const gain2 = (int)(ml2 * 4 - ZSTD_highbit32((U32)offset2 + 1)); /* raw approx */
2149 int const gain1 = (int)(matchLength * 4 - ZSTD_highbit32((U32)offset + 1) + 4);
2150 if ((ml2 >= EQUAL_READ32) && (gain2 > gain1)) {
2151 matchLength = ml2, offset = offset2, start = ip;
2152 continue; /* search a better one */
2153 }
2154 }
2155
2156 /* let's find an even better one */
2157 if ((depth == 2) && (ip < ilimit)) {
2158 ip++;
2159 curr++;
2160 /* check repCode */
2161 if (offset) {
2162 const U32 repIndex = (U32)(curr - offset_1);
2163 const BYTE *const repBase = repIndex < dictLimit ? dictBase : base;
2164 const BYTE *const repMatch = repBase + repIndex;
2165 if (((U32)((dictLimit - 1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
2166 if (ZSTD_read32(ip) == ZSTD_read32(repMatch)) {
2167 /* repcode detected */
2168 const BYTE *const repEnd = repIndex < dictLimit ? dictEnd : iend;
2169 size_t repLength = ZSTD_count_2segments(ip + EQUAL_READ32, repMatch + EQUAL_READ32, iend,
2170 repEnd, prefixStart) +
2171 EQUAL_READ32;
2172 int gain2 = (int)(repLength * 4);
2173 int gain1 = (int)(matchLength * 4 - ZSTD_highbit32((U32)offset + 1) + 1);
2174 if ((repLength >= EQUAL_READ32) && (gain2 > gain1))
2175 matchLength = repLength, offset = 0, start = ip;
2176 }
2177 }
2178
2179 /* search match, depth 2 */
2180 {
2181 size_t offset2 = 99999999;
2182 size_t const ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls);
2183 int const gain2 = (int)(ml2 * 4 - ZSTD_highbit32((U32)offset2 + 1)); /* raw approx */
2184 int const gain1 = (int)(matchLength * 4 - ZSTD_highbit32((U32)offset + 1) + 7);
2185 if ((ml2 >= EQUAL_READ32) && (gain2 > gain1)) {
2186 matchLength = ml2, offset = offset2, start = ip;
2187 continue;
2188 }
2189 }
2190 }
2191 break; /* nothing found : store previous solution */
2192 }
2193
2194 /* catch up */
2195 if (offset) {
2196 U32 const matchIndex = (U32)((start - base) - (offset - ZSTD_REP_MOVE));
2197 const BYTE *match = (matchIndex < dictLimit) ? dictBase + matchIndex : base + matchIndex;
2198 const BYTE *const mStart = (matchIndex < dictLimit) ? dictStart : prefixStart;
2199 while ((start > anchor) && (match > mStart) && (start[-1] == match[-1])) {
2200 start--;
2201 match--;
2202 matchLength++;
2203 } /* catch up */
2204 offset_2 = offset_1;
2205 offset_1 = (U32)(offset - ZSTD_REP_MOVE);
2206 }
2207
2208 /* store sequence */
2209 _storeSequence : {
2210 size_t const litLength = start - anchor;
2211 ZSTD_storeSeq(seqStorePtr, litLength, anchor, (U32)offset, matchLength - MINMATCH);
2212 anchor = ip = start + matchLength;
2213 }
2214
2215 /* check immediate repcode */
2216 while (ip <= ilimit) {
2217 const U32 repIndex = (U32)((ip - base) - offset_2);
2218 const BYTE *const repBase = repIndex < dictLimit ? dictBase : base;
2219 const BYTE *const repMatch = repBase + repIndex;
2220 if (((U32)((dictLimit - 1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
2221 if (ZSTD_read32(ip) == ZSTD_read32(repMatch)) {
2222 /* repcode detected we should take it */
2223 const BYTE *const repEnd = repIndex < dictLimit ? dictEnd : iend;
2224 matchLength =
2225 ZSTD_count_2segments(ip + EQUAL_READ32, repMatch + EQUAL_READ32, iend, repEnd, prefixStart) + EQUAL_READ32;
2226 offset = offset_2;
2227 offset_2 = offset_1;
2228 offset_1 = (U32)offset; /* swap offset history */
2229 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, matchLength - MINMATCH);
2230 ip += matchLength;
2231 anchor = ip;
2232 continue; /* faster when present ... (?) */
2233 }
2234 break;
2235 }
2236 }
2237
2238 /* Save reps for next block */
2239 ctx->repToConfirm[0] = offset_1;
2240 ctx->repToConfirm[1] = offset_2;
2241
2242 /* Last Literals */
2243 {
2244 size_t const lastLLSize = iend - anchor;
2245 memcpy(seqStorePtr->lit, anchor, lastLLSize);
2246 seqStorePtr->lit += lastLLSize;
2247 }
2248 }
2249
ZSTD_compressBlock_greedy_extDict(ZSTD_CCtx * ctx,const void * src,size_t srcSize)2250 void ZSTD_compressBlock_greedy_extDict(ZSTD_CCtx *ctx, const void *src, size_t srcSize) { ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 0, 0); }
2251
ZSTD_compressBlock_lazy_extDict(ZSTD_CCtx * ctx,const void * src,size_t srcSize)2252 static void ZSTD_compressBlock_lazy_extDict(ZSTD_CCtx *ctx, const void *src, size_t srcSize)
2253 {
2254 ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 0, 1);
2255 }
2256
ZSTD_compressBlock_lazy2_extDict(ZSTD_CCtx * ctx,const void * src,size_t srcSize)2257 static void ZSTD_compressBlock_lazy2_extDict(ZSTD_CCtx *ctx, const void *src, size_t srcSize)
2258 {
2259 ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 0, 2);
2260 }
2261
ZSTD_compressBlock_btlazy2_extDict(ZSTD_CCtx * ctx,const void * src,size_t srcSize)2262 static void ZSTD_compressBlock_btlazy2_extDict(ZSTD_CCtx *ctx, const void *src, size_t srcSize)
2263 {
2264 ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 1, 2);
2265 }
2266
2267 /* The optimal parser */
2268 #include "zstd_opt.h"
2269
ZSTD_compressBlock_btopt(ZSTD_CCtx * ctx,const void * src,size_t srcSize)2270 static void ZSTD_compressBlock_btopt(ZSTD_CCtx *ctx, const void *src, size_t srcSize)
2271 {
2272 #ifdef ZSTD_OPT_H_91842398743
2273 ZSTD_compressBlock_opt_generic(ctx, src, srcSize, 0);
2274 #else
2275 (void)ctx;
2276 (void)src;
2277 (void)srcSize;
2278 return;
2279 #endif
2280 }
2281
ZSTD_compressBlock_btopt2(ZSTD_CCtx * ctx,const void * src,size_t srcSize)2282 static void ZSTD_compressBlock_btopt2(ZSTD_CCtx *ctx, const void *src, size_t srcSize)
2283 {
2284 #ifdef ZSTD_OPT_H_91842398743
2285 ZSTD_compressBlock_opt_generic(ctx, src, srcSize, 1);
2286 #else
2287 (void)ctx;
2288 (void)src;
2289 (void)srcSize;
2290 return;
2291 #endif
2292 }
2293
ZSTD_compressBlock_btopt_extDict(ZSTD_CCtx * ctx,const void * src,size_t srcSize)2294 static void ZSTD_compressBlock_btopt_extDict(ZSTD_CCtx *ctx, const void *src, size_t srcSize)
2295 {
2296 #ifdef ZSTD_OPT_H_91842398743
2297 ZSTD_compressBlock_opt_extDict_generic(ctx, src, srcSize, 0);
2298 #else
2299 (void)ctx;
2300 (void)src;
2301 (void)srcSize;
2302 return;
2303 #endif
2304 }
2305
ZSTD_compressBlock_btopt2_extDict(ZSTD_CCtx * ctx,const void * src,size_t srcSize)2306 static void ZSTD_compressBlock_btopt2_extDict(ZSTD_CCtx *ctx, const void *src, size_t srcSize)
2307 {
2308 #ifdef ZSTD_OPT_H_91842398743
2309 ZSTD_compressBlock_opt_extDict_generic(ctx, src, srcSize, 1);
2310 #else
2311 (void)ctx;
2312 (void)src;
2313 (void)srcSize;
2314 return;
2315 #endif
2316 }
2317
2318 typedef void (*ZSTD_blockCompressor)(ZSTD_CCtx *ctx, const void *src, size_t srcSize);
2319
ZSTD_selectBlockCompressor(ZSTD_strategy strat,int extDict)2320 static ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, int extDict)
2321 {
2322 static const ZSTD_blockCompressor blockCompressor[2][8] = {
2323 {ZSTD_compressBlock_fast, ZSTD_compressBlock_doubleFast, ZSTD_compressBlock_greedy, ZSTD_compressBlock_lazy, ZSTD_compressBlock_lazy2,
2324 ZSTD_compressBlock_btlazy2, ZSTD_compressBlock_btopt, ZSTD_compressBlock_btopt2},
2325 {ZSTD_compressBlock_fast_extDict, ZSTD_compressBlock_doubleFast_extDict, ZSTD_compressBlock_greedy_extDict, ZSTD_compressBlock_lazy_extDict,
2326 ZSTD_compressBlock_lazy2_extDict, ZSTD_compressBlock_btlazy2_extDict, ZSTD_compressBlock_btopt_extDict, ZSTD_compressBlock_btopt2_extDict}};
2327
2328 return blockCompressor[extDict][(U32)strat];
2329 }
2330
ZSTD_compressBlock_internal(ZSTD_CCtx * zc,void * dst,size_t dstCapacity,const void * src,size_t srcSize)2331 static size_t ZSTD_compressBlock_internal(ZSTD_CCtx *zc, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
2332 {
2333 ZSTD_blockCompressor const blockCompressor = ZSTD_selectBlockCompressor(zc->params.cParams.strategy, zc->lowLimit < zc->dictLimit);
2334 const BYTE *const base = zc->base;
2335 const BYTE *const istart = (const BYTE *)src;
2336 const U32 curr = (U32)(istart - base);
2337 if (srcSize < MIN_CBLOCK_SIZE + ZSTD_blockHeaderSize + 1)
2338 return 0; /* don't even attempt compression below a certain srcSize */
2339 ZSTD_resetSeqStore(&(zc->seqStore));
2340 if (curr > zc->nextToUpdate + 384)
2341 zc->nextToUpdate = curr - MIN(192, (U32)(curr - zc->nextToUpdate - 384)); /* update tree not updated after finding very long rep matches */
2342 blockCompressor(zc, src, srcSize);
2343 return ZSTD_compressSequences(zc, dst, dstCapacity, srcSize);
2344 }
2345
2346 /*! ZSTD_compress_generic() :
2347 * Compress a chunk of data into one or multiple blocks.
2348 * All blocks will be terminated, all input will be consumed.
2349 * Function will issue an error if there is not enough `dstCapacity` to hold the compressed content.
2350 * Frame is supposed already started (header already produced)
2351 * @return : compressed size, or an error code
2352 */
ZSTD_compress_generic(ZSTD_CCtx * cctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize,U32 lastFrameChunk)2353 static size_t ZSTD_compress_generic(ZSTD_CCtx *cctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, U32 lastFrameChunk)
2354 {
2355 size_t blockSize = cctx->blockSize;
2356 size_t remaining = srcSize;
2357 const BYTE *ip = (const BYTE *)src;
2358 BYTE *const ostart = (BYTE *)dst;
2359 BYTE *op = ostart;
2360 U32 const maxDist = 1 << cctx->params.cParams.windowLog;
2361
2362 if (cctx->params.fParams.checksumFlag && srcSize)
2363 xxh64_update(&cctx->xxhState, src, srcSize);
2364
2365 while (remaining) {
2366 U32 const lastBlock = lastFrameChunk & (blockSize >= remaining);
2367 size_t cSize;
2368
2369 if (dstCapacity < ZSTD_blockHeaderSize + MIN_CBLOCK_SIZE)
2370 return ERROR(dstSize_tooSmall); /* not enough space to store compressed block */
2371 if (remaining < blockSize)
2372 blockSize = remaining;
2373
2374 /* preemptive overflow correction */
2375 if (cctx->lowLimit > (3U << 29)) {
2376 U32 const cycleMask = (1 << ZSTD_cycleLog(cctx->params.cParams.hashLog, cctx->params.cParams.strategy)) - 1;
2377 U32 const curr = (U32)(ip - cctx->base);
2378 U32 const newCurr = (curr & cycleMask) + (1 << cctx->params.cParams.windowLog);
2379 U32 const correction = curr - newCurr;
2380 ZSTD_STATIC_ASSERT(ZSTD_WINDOWLOG_MAX_64 <= 30);
2381 ZSTD_reduceIndex(cctx, correction);
2382 cctx->base += correction;
2383 cctx->dictBase += correction;
2384 cctx->lowLimit -= correction;
2385 cctx->dictLimit -= correction;
2386 if (cctx->nextToUpdate < correction)
2387 cctx->nextToUpdate = 0;
2388 else
2389 cctx->nextToUpdate -= correction;
2390 }
2391
2392 if ((U32)(ip + blockSize - cctx->base) > cctx->loadedDictEnd + maxDist) {
2393 /* enforce maxDist */
2394 U32 const newLowLimit = (U32)(ip + blockSize - cctx->base) - maxDist;
2395 if (cctx->lowLimit < newLowLimit)
2396 cctx->lowLimit = newLowLimit;
2397 if (cctx->dictLimit < cctx->lowLimit)
2398 cctx->dictLimit = cctx->lowLimit;
2399 }
2400
2401 cSize = ZSTD_compressBlock_internal(cctx, op + ZSTD_blockHeaderSize, dstCapacity - ZSTD_blockHeaderSize, ip, blockSize);
2402 if (ZSTD_isError(cSize))
2403 return cSize;
2404
2405 if (cSize == 0) { /* block is not compressible */
2406 U32 const cBlockHeader24 = lastBlock + (((U32)bt_raw) << 1) + (U32)(blockSize << 3);
2407 if (blockSize + ZSTD_blockHeaderSize > dstCapacity)
2408 return ERROR(dstSize_tooSmall);
2409 ZSTD_writeLE32(op, cBlockHeader24); /* no pb, 4th byte will be overwritten */
2410 memcpy(op + ZSTD_blockHeaderSize, ip, blockSize);
2411 cSize = ZSTD_blockHeaderSize + blockSize;
2412 } else {
2413 U32 const cBlockHeader24 = lastBlock + (((U32)bt_compressed) << 1) + (U32)(cSize << 3);
2414 ZSTD_writeLE24(op, cBlockHeader24);
2415 cSize += ZSTD_blockHeaderSize;
2416 }
2417
2418 remaining -= blockSize;
2419 dstCapacity -= cSize;
2420 ip += blockSize;
2421 op += cSize;
2422 }
2423
2424 if (lastFrameChunk && (op > ostart))
2425 cctx->stage = ZSTDcs_ending;
2426 return op - ostart;
2427 }
2428
ZSTD_writeFrameHeader(void * dst,size_t dstCapacity,ZSTD_parameters params,U64 pledgedSrcSize,U32 dictID)2429 static size_t ZSTD_writeFrameHeader(void *dst, size_t dstCapacity, ZSTD_parameters params, U64 pledgedSrcSize, U32 dictID)
2430 {
2431 BYTE *const op = (BYTE *)dst;
2432 U32 const dictIDSizeCode = (dictID > 0) + (dictID >= 256) + (dictID >= 65536); /* 0-3 */
2433 U32 const checksumFlag = params.fParams.checksumFlag > 0;
2434 U32 const windowSize = 1U << params.cParams.windowLog;
2435 U32 const singleSegment = params.fParams.contentSizeFlag && (windowSize >= pledgedSrcSize);
2436 BYTE const windowLogByte = (BYTE)((params.cParams.windowLog - ZSTD_WINDOWLOG_ABSOLUTEMIN) << 3);
2437 U32 const fcsCode =
2438 params.fParams.contentSizeFlag ? (pledgedSrcSize >= 256) + (pledgedSrcSize >= 65536 + 256) + (pledgedSrcSize >= 0xFFFFFFFFU) : 0; /* 0-3 */
2439 BYTE const frameHeaderDescriptionByte = (BYTE)(dictIDSizeCode + (checksumFlag << 2) + (singleSegment << 5) + (fcsCode << 6));
2440 size_t pos;
2441
2442 if (dstCapacity < ZSTD_frameHeaderSize_max)
2443 return ERROR(dstSize_tooSmall);
2444
2445 ZSTD_writeLE32(dst, ZSTD_MAGICNUMBER);
2446 op[4] = frameHeaderDescriptionByte;
2447 pos = 5;
2448 if (!singleSegment)
2449 op[pos++] = windowLogByte;
2450 switch (dictIDSizeCode) {
2451 default: /* impossible */
2452 case 0: break;
2453 case 1:
2454 op[pos] = (BYTE)(dictID);
2455 pos++;
2456 break;
2457 case 2:
2458 ZSTD_writeLE16(op + pos, (U16)dictID);
2459 pos += 2;
2460 break;
2461 case 3:
2462 ZSTD_writeLE32(op + pos, dictID);
2463 pos += 4;
2464 break;
2465 }
2466 switch (fcsCode) {
2467 default: /* impossible */
2468 case 0:
2469 if (singleSegment)
2470 op[pos++] = (BYTE)(pledgedSrcSize);
2471 break;
2472 case 1:
2473 ZSTD_writeLE16(op + pos, (U16)(pledgedSrcSize - 256));
2474 pos += 2;
2475 break;
2476 case 2:
2477 ZSTD_writeLE32(op + pos, (U32)(pledgedSrcSize));
2478 pos += 4;
2479 break;
2480 case 3:
2481 ZSTD_writeLE64(op + pos, (U64)(pledgedSrcSize));
2482 pos += 8;
2483 break;
2484 }
2485 return pos;
2486 }
2487
ZSTD_compressContinue_internal(ZSTD_CCtx * cctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize,U32 frame,U32 lastFrameChunk)2488 static size_t ZSTD_compressContinue_internal(ZSTD_CCtx *cctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, U32 frame, U32 lastFrameChunk)
2489 {
2490 const BYTE *const ip = (const BYTE *)src;
2491 size_t fhSize = 0;
2492
2493 if (cctx->stage == ZSTDcs_created)
2494 return ERROR(stage_wrong); /* missing init (ZSTD_compressBegin) */
2495
2496 if (frame && (cctx->stage == ZSTDcs_init)) {
2497 fhSize = ZSTD_writeFrameHeader(dst, dstCapacity, cctx->params, cctx->frameContentSize, cctx->dictID);
2498 if (ZSTD_isError(fhSize))
2499 return fhSize;
2500 dstCapacity -= fhSize;
2501 dst = (char *)dst + fhSize;
2502 cctx->stage = ZSTDcs_ongoing;
2503 }
2504
2505 /* Check if blocks follow each other */
2506 if (src != cctx->nextSrc) {
2507 /* not contiguous */
2508 ptrdiff_t const delta = cctx->nextSrc - ip;
2509 cctx->lowLimit = cctx->dictLimit;
2510 cctx->dictLimit = (U32)(cctx->nextSrc - cctx->base);
2511 cctx->dictBase = cctx->base;
2512 cctx->base -= delta;
2513 cctx->nextToUpdate = cctx->dictLimit;
2514 if (cctx->dictLimit - cctx->lowLimit < HASH_READ_SIZE)
2515 cctx->lowLimit = cctx->dictLimit; /* too small extDict */
2516 }
2517
2518 /* if input and dictionary overlap : reduce dictionary (area presumed modified by input) */
2519 if ((ip + srcSize > cctx->dictBase + cctx->lowLimit) & (ip < cctx->dictBase + cctx->dictLimit)) {
2520 ptrdiff_t const highInputIdx = (ip + srcSize) - cctx->dictBase;
2521 U32 const lowLimitMax = (highInputIdx > (ptrdiff_t)cctx->dictLimit) ? cctx->dictLimit : (U32)highInputIdx;
2522 cctx->lowLimit = lowLimitMax;
2523 }
2524
2525 cctx->nextSrc = ip + srcSize;
2526
2527 if (srcSize) {
2528 size_t const cSize = frame ? ZSTD_compress_generic(cctx, dst, dstCapacity, src, srcSize, lastFrameChunk)
2529 : ZSTD_compressBlock_internal(cctx, dst, dstCapacity, src, srcSize);
2530 if (ZSTD_isError(cSize))
2531 return cSize;
2532 return cSize + fhSize;
2533 } else
2534 return fhSize;
2535 }
2536
ZSTD_compressContinue(ZSTD_CCtx * cctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize)2537 size_t ZSTD_compressContinue(ZSTD_CCtx *cctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
2538 {
2539 return ZSTD_compressContinue_internal(cctx, dst, dstCapacity, src, srcSize, 1, 0);
2540 }
2541
ZSTD_getBlockSizeMax(ZSTD_CCtx * cctx)2542 size_t ZSTD_getBlockSizeMax(ZSTD_CCtx *cctx) { return MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, 1 << cctx->params.cParams.windowLog); }
2543
ZSTD_compressBlock(ZSTD_CCtx * cctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize)2544 size_t ZSTD_compressBlock(ZSTD_CCtx *cctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
2545 {
2546 size_t const blockSizeMax = ZSTD_getBlockSizeMax(cctx);
2547 if (srcSize > blockSizeMax)
2548 return ERROR(srcSize_wrong);
2549 return ZSTD_compressContinue_internal(cctx, dst, dstCapacity, src, srcSize, 0, 0);
2550 }
2551
2552 /*! ZSTD_loadDictionaryContent() :
2553 * @return : 0, or an error code
2554 */
ZSTD_loadDictionaryContent(ZSTD_CCtx * zc,const void * src,size_t srcSize)2555 static size_t ZSTD_loadDictionaryContent(ZSTD_CCtx *zc, const void *src, size_t srcSize)
2556 {
2557 const BYTE *const ip = (const BYTE *)src;
2558 const BYTE *const iend = ip + srcSize;
2559
2560 /* input becomes curr prefix */
2561 zc->lowLimit = zc->dictLimit;
2562 zc->dictLimit = (U32)(zc->nextSrc - zc->base);
2563 zc->dictBase = zc->base;
2564 zc->base += ip - zc->nextSrc;
2565 zc->nextToUpdate = zc->dictLimit;
2566 zc->loadedDictEnd = zc->forceWindow ? 0 : (U32)(iend - zc->base);
2567
2568 zc->nextSrc = iend;
2569 if (srcSize <= HASH_READ_SIZE)
2570 return 0;
2571
2572 switch (zc->params.cParams.strategy) {
2573 case ZSTD_fast: ZSTD_fillHashTable(zc, iend, zc->params.cParams.searchLength); break;
2574
2575 case ZSTD_dfast: ZSTD_fillDoubleHashTable(zc, iend, zc->params.cParams.searchLength); break;
2576
2577 case ZSTD_greedy:
2578 case ZSTD_lazy:
2579 case ZSTD_lazy2:
2580 if (srcSize >= HASH_READ_SIZE)
2581 ZSTD_insertAndFindFirstIndex(zc, iend - HASH_READ_SIZE, zc->params.cParams.searchLength);
2582 break;
2583
2584 case ZSTD_btlazy2:
2585 case ZSTD_btopt:
2586 case ZSTD_btopt2:
2587 if (srcSize >= HASH_READ_SIZE)
2588 ZSTD_updateTree(zc, iend - HASH_READ_SIZE, iend, 1 << zc->params.cParams.searchLog, zc->params.cParams.searchLength);
2589 break;
2590
2591 default:
2592 return ERROR(GENERIC); /* strategy doesn't exist; impossible */
2593 }
2594
2595 zc->nextToUpdate = (U32)(iend - zc->base);
2596 return 0;
2597 }
2598
2599 /* Dictionaries that assign zero probability to symbols that show up causes problems
2600 when FSE encoding. Refuse dictionaries that assign zero probability to symbols
2601 that we may encounter during compression.
2602 NOTE: This behavior is not standard and could be improved in the future. */
ZSTD_checkDictNCount(short * normalizedCounter,unsigned dictMaxSymbolValue,unsigned maxSymbolValue)2603 static size_t ZSTD_checkDictNCount(short *normalizedCounter, unsigned dictMaxSymbolValue, unsigned maxSymbolValue)
2604 {
2605 U32 s;
2606 if (dictMaxSymbolValue < maxSymbolValue)
2607 return ERROR(dictionary_corrupted);
2608 for (s = 0; s <= maxSymbolValue; ++s) {
2609 if (normalizedCounter[s] == 0)
2610 return ERROR(dictionary_corrupted);
2611 }
2612 return 0;
2613 }
2614
2615 /* Dictionary format :
2616 * See :
2617 * https://github.com/facebook/zstd/blob/master/doc/zstd_compression_format.md#dictionary-format
2618 */
2619 /*! ZSTD_loadZstdDictionary() :
2620 * @return : 0, or an error code
2621 * assumptions : magic number supposed already checked
2622 * dictSize supposed > 8
2623 */
ZSTD_loadZstdDictionary(ZSTD_CCtx * cctx,const void * dict,size_t dictSize)2624 static size_t ZSTD_loadZstdDictionary(ZSTD_CCtx *cctx, const void *dict, size_t dictSize)
2625 {
2626 const BYTE *dictPtr = (const BYTE *)dict;
2627 const BYTE *const dictEnd = dictPtr + dictSize;
2628 short offcodeNCount[MaxOff + 1];
2629 unsigned offcodeMaxValue = MaxOff;
2630
2631 dictPtr += 4; /* skip magic number */
2632 cctx->dictID = cctx->params.fParams.noDictIDFlag ? 0 : ZSTD_readLE32(dictPtr);
2633 dictPtr += 4;
2634
2635 {
2636 size_t const hufHeaderSize = HUF_readCTable_wksp(cctx->hufTable, 255, dictPtr, dictEnd - dictPtr, cctx->tmpCounters, sizeof(cctx->tmpCounters));
2637 if (HUF_isError(hufHeaderSize))
2638 return ERROR(dictionary_corrupted);
2639 dictPtr += hufHeaderSize;
2640 }
2641
2642 {
2643 unsigned offcodeLog;
2644 size_t const offcodeHeaderSize = FSE_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dictPtr, dictEnd - dictPtr);
2645 if (FSE_isError(offcodeHeaderSize))
2646 return ERROR(dictionary_corrupted);
2647 if (offcodeLog > OffFSELog)
2648 return ERROR(dictionary_corrupted);
2649 /* Defer checking offcodeMaxValue because we need to know the size of the dictionary content */
2650 CHECK_E(FSE_buildCTable_wksp(cctx->offcodeCTable, offcodeNCount, offcodeMaxValue, offcodeLog, cctx->tmpCounters, sizeof(cctx->tmpCounters)),
2651 dictionary_corrupted);
2652 dictPtr += offcodeHeaderSize;
2653 }
2654
2655 {
2656 short matchlengthNCount[MaxML + 1];
2657 unsigned matchlengthMaxValue = MaxML, matchlengthLog;
2658 size_t const matchlengthHeaderSize = FSE_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd - dictPtr);
2659 if (FSE_isError(matchlengthHeaderSize))
2660 return ERROR(dictionary_corrupted);
2661 if (matchlengthLog > MLFSELog)
2662 return ERROR(dictionary_corrupted);
2663 /* Every match length code must have non-zero probability */
2664 CHECK_F(ZSTD_checkDictNCount(matchlengthNCount, matchlengthMaxValue, MaxML));
2665 CHECK_E(
2666 FSE_buildCTable_wksp(cctx->matchlengthCTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog, cctx->tmpCounters, sizeof(cctx->tmpCounters)),
2667 dictionary_corrupted);
2668 dictPtr += matchlengthHeaderSize;
2669 }
2670
2671 {
2672 short litlengthNCount[MaxLL + 1];
2673 unsigned litlengthMaxValue = MaxLL, litlengthLog;
2674 size_t const litlengthHeaderSize = FSE_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd - dictPtr);
2675 if (FSE_isError(litlengthHeaderSize))
2676 return ERROR(dictionary_corrupted);
2677 if (litlengthLog > LLFSELog)
2678 return ERROR(dictionary_corrupted);
2679 /* Every literal length code must have non-zero probability */
2680 CHECK_F(ZSTD_checkDictNCount(litlengthNCount, litlengthMaxValue, MaxLL));
2681 CHECK_E(FSE_buildCTable_wksp(cctx->litlengthCTable, litlengthNCount, litlengthMaxValue, litlengthLog, cctx->tmpCounters, sizeof(cctx->tmpCounters)),
2682 dictionary_corrupted);
2683 dictPtr += litlengthHeaderSize;
2684 }
2685
2686 if (dictPtr + 12 > dictEnd)
2687 return ERROR(dictionary_corrupted);
2688 cctx->rep[0] = ZSTD_readLE32(dictPtr + 0);
2689 cctx->rep[1] = ZSTD_readLE32(dictPtr + 4);
2690 cctx->rep[2] = ZSTD_readLE32(dictPtr + 8);
2691 dictPtr += 12;
2692
2693 {
2694 size_t const dictContentSize = (size_t)(dictEnd - dictPtr);
2695 U32 offcodeMax = MaxOff;
2696 if (dictContentSize <= ((U32)-1) - 128 KB) {
2697 U32 const maxOffset = (U32)dictContentSize + 128 KB; /* The maximum offset that must be supported */
2698 offcodeMax = ZSTD_highbit32(maxOffset); /* Calculate minimum offset code required to represent maxOffset */
2699 }
2700 /* All offset values <= dictContentSize + 128 KB must be representable */
2701 CHECK_F(ZSTD_checkDictNCount(offcodeNCount, offcodeMaxValue, MIN(offcodeMax, MaxOff)));
2702 /* All repCodes must be <= dictContentSize and != 0*/
2703 {
2704 U32 u;
2705 for (u = 0; u < 3; u++) {
2706 if (cctx->rep[u] == 0)
2707 return ERROR(dictionary_corrupted);
2708 if (cctx->rep[u] > dictContentSize)
2709 return ERROR(dictionary_corrupted);
2710 }
2711 }
2712
2713 cctx->flagStaticTables = 1;
2714 cctx->flagStaticHufTable = HUF_repeat_valid;
2715 return ZSTD_loadDictionaryContent(cctx, dictPtr, dictContentSize);
2716 }
2717 }
2718
2719 /** ZSTD_compress_insertDictionary() :
2720 * @return : 0, or an error code */
ZSTD_compress_insertDictionary(ZSTD_CCtx * cctx,const void * dict,size_t dictSize)2721 static size_t ZSTD_compress_insertDictionary(ZSTD_CCtx *cctx, const void *dict, size_t dictSize)
2722 {
2723 if ((dict == NULL) || (dictSize <= 8))
2724 return 0;
2725
2726 /* dict as pure content */
2727 if ((ZSTD_readLE32(dict) != ZSTD_DICT_MAGIC) || (cctx->forceRawDict))
2728 return ZSTD_loadDictionaryContent(cctx, dict, dictSize);
2729
2730 /* dict as zstd dictionary */
2731 return ZSTD_loadZstdDictionary(cctx, dict, dictSize);
2732 }
2733
2734 /*! ZSTD_compressBegin_internal() :
2735 * @return : 0, or an error code */
ZSTD_compressBegin_internal(ZSTD_CCtx * cctx,const void * dict,size_t dictSize,ZSTD_parameters params,U64 pledgedSrcSize)2736 static size_t ZSTD_compressBegin_internal(ZSTD_CCtx *cctx, const void *dict, size_t dictSize, ZSTD_parameters params, U64 pledgedSrcSize)
2737 {
2738 ZSTD_compResetPolicy_e const crp = dictSize ? ZSTDcrp_fullReset : ZSTDcrp_continue;
2739 CHECK_F(ZSTD_resetCCtx_advanced(cctx, params, pledgedSrcSize, crp));
2740 return ZSTD_compress_insertDictionary(cctx, dict, dictSize);
2741 }
2742
2743 /*! ZSTD_compressBegin_advanced() :
2744 * @return : 0, or an error code */
ZSTD_compressBegin_advanced(ZSTD_CCtx * cctx,const void * dict,size_t dictSize,ZSTD_parameters params,unsigned long long pledgedSrcSize)2745 size_t ZSTD_compressBegin_advanced(ZSTD_CCtx *cctx, const void *dict, size_t dictSize, ZSTD_parameters params, unsigned long long pledgedSrcSize)
2746 {
2747 /* compression parameters verification and optimization */
2748 CHECK_F(ZSTD_checkCParams(params.cParams));
2749 return ZSTD_compressBegin_internal(cctx, dict, dictSize, params, pledgedSrcSize);
2750 }
2751
ZSTD_compressBegin_usingDict(ZSTD_CCtx * cctx,const void * dict,size_t dictSize,int compressionLevel)2752 size_t ZSTD_compressBegin_usingDict(ZSTD_CCtx *cctx, const void *dict, size_t dictSize, int compressionLevel)
2753 {
2754 ZSTD_parameters const params = ZSTD_getParams(compressionLevel, 0, dictSize);
2755 return ZSTD_compressBegin_internal(cctx, dict, dictSize, params, 0);
2756 }
2757
ZSTD_compressBegin(ZSTD_CCtx * cctx,int compressionLevel)2758 size_t ZSTD_compressBegin(ZSTD_CCtx *cctx, int compressionLevel) { return ZSTD_compressBegin_usingDict(cctx, NULL, 0, compressionLevel); }
2759
2760 /*! ZSTD_writeEpilogue() :
2761 * Ends a frame.
2762 * @return : nb of bytes written into dst (or an error code) */
ZSTD_writeEpilogue(ZSTD_CCtx * cctx,void * dst,size_t dstCapacity)2763 static size_t ZSTD_writeEpilogue(ZSTD_CCtx *cctx, void *dst, size_t dstCapacity)
2764 {
2765 BYTE *const ostart = (BYTE *)dst;
2766 BYTE *op = ostart;
2767 size_t fhSize = 0;
2768
2769 if (cctx->stage == ZSTDcs_created)
2770 return ERROR(stage_wrong); /* init missing */
2771
2772 /* special case : empty frame */
2773 if (cctx->stage == ZSTDcs_init) {
2774 fhSize = ZSTD_writeFrameHeader(dst, dstCapacity, cctx->params, 0, 0);
2775 if (ZSTD_isError(fhSize))
2776 return fhSize;
2777 dstCapacity -= fhSize;
2778 op += fhSize;
2779 cctx->stage = ZSTDcs_ongoing;
2780 }
2781
2782 if (cctx->stage != ZSTDcs_ending) {
2783 /* write one last empty block, make it the "last" block */
2784 U32 const cBlockHeader24 = 1 /* last block */ + (((U32)bt_raw) << 1) + 0;
2785 if (dstCapacity < 4)
2786 return ERROR(dstSize_tooSmall);
2787 ZSTD_writeLE32(op, cBlockHeader24);
2788 op += ZSTD_blockHeaderSize;
2789 dstCapacity -= ZSTD_blockHeaderSize;
2790 }
2791
2792 if (cctx->params.fParams.checksumFlag) {
2793 U32 const checksum = (U32)xxh64_digest(&cctx->xxhState);
2794 if (dstCapacity < 4)
2795 return ERROR(dstSize_tooSmall);
2796 ZSTD_writeLE32(op, checksum);
2797 op += 4;
2798 }
2799
2800 cctx->stage = ZSTDcs_created; /* return to "created but no init" status */
2801 return op - ostart;
2802 }
2803
ZSTD_compressEnd(ZSTD_CCtx * cctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize)2804 size_t ZSTD_compressEnd(ZSTD_CCtx *cctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
2805 {
2806 size_t endResult;
2807 size_t const cSize = ZSTD_compressContinue_internal(cctx, dst, dstCapacity, src, srcSize, 1, 1);
2808 if (ZSTD_isError(cSize))
2809 return cSize;
2810 endResult = ZSTD_writeEpilogue(cctx, (char *)dst + cSize, dstCapacity - cSize);
2811 if (ZSTD_isError(endResult))
2812 return endResult;
2813 return cSize + endResult;
2814 }
2815
ZSTD_compress_internal(ZSTD_CCtx * cctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize,const void * dict,size_t dictSize,ZSTD_parameters params)2816 static size_t ZSTD_compress_internal(ZSTD_CCtx *cctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const void *dict, size_t dictSize,
2817 ZSTD_parameters params)
2818 {
2819 CHECK_F(ZSTD_compressBegin_internal(cctx, dict, dictSize, params, srcSize));
2820 return ZSTD_compressEnd(cctx, dst, dstCapacity, src, srcSize);
2821 }
2822
ZSTD_compress_usingDict(ZSTD_CCtx * ctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize,const void * dict,size_t dictSize,ZSTD_parameters params)2823 size_t ZSTD_compress_usingDict(ZSTD_CCtx *ctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const void *dict, size_t dictSize,
2824 ZSTD_parameters params)
2825 {
2826 return ZSTD_compress_internal(ctx, dst, dstCapacity, src, srcSize, dict, dictSize, params);
2827 }
2828
ZSTD_compressCCtx(ZSTD_CCtx * ctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize,ZSTD_parameters params)2829 size_t ZSTD_compressCCtx(ZSTD_CCtx *ctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, ZSTD_parameters params)
2830 {
2831 return ZSTD_compress_internal(ctx, dst, dstCapacity, src, srcSize, NULL, 0, params);
2832 }
2833
2834 /* ===== Dictionary API ===== */
2835
2836 struct ZSTD_CDict_s {
2837 void *dictBuffer;
2838 const void *dictContent;
2839 size_t dictContentSize;
2840 ZSTD_CCtx *refContext;
2841 }; /* typedef'd tp ZSTD_CDict within "zstd.h" */
2842
ZSTD_CDictWorkspaceBound(ZSTD_compressionParameters cParams)2843 size_t ZSTD_CDictWorkspaceBound(ZSTD_compressionParameters cParams) { return ZSTD_CCtxWorkspaceBound(cParams) + ZSTD_ALIGN(sizeof(ZSTD_CDict)); }
2844
ZSTD_createCDict_advanced(const void * dictBuffer,size_t dictSize,unsigned byReference,ZSTD_parameters params,ZSTD_customMem customMem)2845 static ZSTD_CDict *ZSTD_createCDict_advanced(const void *dictBuffer, size_t dictSize, unsigned byReference, ZSTD_parameters params, ZSTD_customMem customMem)
2846 {
2847 if (!customMem.customAlloc || !customMem.customFree)
2848 return NULL;
2849
2850 {
2851 ZSTD_CDict *const cdict = (ZSTD_CDict *)ZSTD_malloc(sizeof(ZSTD_CDict), customMem);
2852 ZSTD_CCtx *const cctx = ZSTD_createCCtx_advanced(customMem);
2853
2854 if (!cdict || !cctx) {
2855 ZSTD_free(cdict, customMem);
2856 ZSTD_freeCCtx(cctx);
2857 return NULL;
2858 }
2859
2860 if ((byReference) || (!dictBuffer) || (!dictSize)) {
2861 cdict->dictBuffer = NULL;
2862 cdict->dictContent = dictBuffer;
2863 } else {
2864 void *const internalBuffer = ZSTD_malloc(dictSize, customMem);
2865 if (!internalBuffer) {
2866 ZSTD_free(cctx, customMem);
2867 ZSTD_free(cdict, customMem);
2868 return NULL;
2869 }
2870 memcpy(internalBuffer, dictBuffer, dictSize);
2871 cdict->dictBuffer = internalBuffer;
2872 cdict->dictContent = internalBuffer;
2873 }
2874
2875 {
2876 size_t const errorCode = ZSTD_compressBegin_advanced(cctx, cdict->dictContent, dictSize, params, 0);
2877 if (ZSTD_isError(errorCode)) {
2878 ZSTD_free(cdict->dictBuffer, customMem);
2879 ZSTD_free(cdict, customMem);
2880 ZSTD_freeCCtx(cctx);
2881 return NULL;
2882 }
2883 }
2884
2885 cdict->refContext = cctx;
2886 cdict->dictContentSize = dictSize;
2887 return cdict;
2888 }
2889 }
2890
ZSTD_initCDict(const void * dict,size_t dictSize,ZSTD_parameters params,void * workspace,size_t workspaceSize)2891 ZSTD_CDict *ZSTD_initCDict(const void *dict, size_t dictSize, ZSTD_parameters params, void *workspace, size_t workspaceSize)
2892 {
2893 ZSTD_customMem const stackMem = ZSTD_initStack(workspace, workspaceSize);
2894 return ZSTD_createCDict_advanced(dict, dictSize, 1, params, stackMem);
2895 }
2896
ZSTD_freeCDict(ZSTD_CDict * cdict)2897 size_t ZSTD_freeCDict(ZSTD_CDict *cdict)
2898 {
2899 if (cdict == NULL)
2900 return 0; /* support free on NULL */
2901 {
2902 ZSTD_customMem const cMem = cdict->refContext->customMem;
2903 ZSTD_freeCCtx(cdict->refContext);
2904 ZSTD_free(cdict->dictBuffer, cMem);
2905 ZSTD_free(cdict, cMem);
2906 return 0;
2907 }
2908 }
2909
ZSTD_getParamsFromCDict(const ZSTD_CDict * cdict)2910 static ZSTD_parameters ZSTD_getParamsFromCDict(const ZSTD_CDict *cdict) { return ZSTD_getParamsFromCCtx(cdict->refContext); }
2911
ZSTD_compressBegin_usingCDict(ZSTD_CCtx * cctx,const ZSTD_CDict * cdict,unsigned long long pledgedSrcSize)2912 size_t ZSTD_compressBegin_usingCDict(ZSTD_CCtx *cctx, const ZSTD_CDict *cdict, unsigned long long pledgedSrcSize)
2913 {
2914 if (cdict->dictContentSize)
2915 CHECK_F(ZSTD_copyCCtx(cctx, cdict->refContext, pledgedSrcSize))
2916 else {
2917 ZSTD_parameters params = cdict->refContext->params;
2918 params.fParams.contentSizeFlag = (pledgedSrcSize > 0);
2919 CHECK_F(ZSTD_compressBegin_advanced(cctx, NULL, 0, params, pledgedSrcSize));
2920 }
2921 return 0;
2922 }
2923
2924 /*! ZSTD_compress_usingCDict() :
2925 * Compression using a digested Dictionary.
2926 * Faster startup than ZSTD_compress_usingDict(), recommended when same dictionary is used multiple times.
2927 * Note that compression level is decided during dictionary creation */
ZSTD_compress_usingCDict(ZSTD_CCtx * cctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize,const ZSTD_CDict * cdict)2928 size_t ZSTD_compress_usingCDict(ZSTD_CCtx *cctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const ZSTD_CDict *cdict)
2929 {
2930 CHECK_F(ZSTD_compressBegin_usingCDict(cctx, cdict, srcSize));
2931
2932 if (cdict->refContext->params.fParams.contentSizeFlag == 1) {
2933 cctx->params.fParams.contentSizeFlag = 1;
2934 cctx->frameContentSize = srcSize;
2935 } else {
2936 cctx->params.fParams.contentSizeFlag = 0;
2937 }
2938
2939 return ZSTD_compressEnd(cctx, dst, dstCapacity, src, srcSize);
2940 }
2941
2942 /* ******************************************************************
2943 * Streaming
2944 ********************************************************************/
2945
2946 typedef enum { zcss_init, zcss_load, zcss_flush, zcss_final } ZSTD_cStreamStage;
2947
2948 struct ZSTD_CStream_s {
2949 ZSTD_CCtx *cctx;
2950 ZSTD_CDict *cdictLocal;
2951 const ZSTD_CDict *cdict;
2952 char *inBuff;
2953 size_t inBuffSize;
2954 size_t inToCompress;
2955 size_t inBuffPos;
2956 size_t inBuffTarget;
2957 size_t blockSize;
2958 char *outBuff;
2959 size_t outBuffSize;
2960 size_t outBuffContentSize;
2961 size_t outBuffFlushedSize;
2962 ZSTD_cStreamStage stage;
2963 U32 checksum;
2964 U32 frameEnded;
2965 U64 pledgedSrcSize;
2966 U64 inputProcessed;
2967 ZSTD_parameters params;
2968 ZSTD_customMem customMem;
2969 }; /* typedef'd to ZSTD_CStream within "zstd.h" */
2970
ZSTD_CStreamWorkspaceBound(ZSTD_compressionParameters cParams)2971 size_t ZSTD_CStreamWorkspaceBound(ZSTD_compressionParameters cParams)
2972 {
2973 size_t const inBuffSize = (size_t)1 << cParams.windowLog;
2974 size_t const blockSize = MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, inBuffSize);
2975 size_t const outBuffSize = ZSTD_compressBound(blockSize) + 1;
2976
2977 return ZSTD_CCtxWorkspaceBound(cParams) + ZSTD_ALIGN(sizeof(ZSTD_CStream)) + ZSTD_ALIGN(inBuffSize) + ZSTD_ALIGN(outBuffSize);
2978 }
2979
ZSTD_createCStream_advanced(ZSTD_customMem customMem)2980 ZSTD_CStream *ZSTD_createCStream_advanced(ZSTD_customMem customMem)
2981 {
2982 ZSTD_CStream *zcs;
2983
2984 if (!customMem.customAlloc || !customMem.customFree)
2985 return NULL;
2986
2987 zcs = (ZSTD_CStream *)ZSTD_malloc(sizeof(ZSTD_CStream), customMem);
2988 if (zcs == NULL)
2989 return NULL;
2990 memset(zcs, 0, sizeof(ZSTD_CStream));
2991 memcpy(&zcs->customMem, &customMem, sizeof(ZSTD_customMem));
2992 zcs->cctx = ZSTD_createCCtx_advanced(customMem);
2993 if (zcs->cctx == NULL) {
2994 ZSTD_freeCStream(zcs);
2995 return NULL;
2996 }
2997 return zcs;
2998 }
2999
ZSTD_freeCStream(ZSTD_CStream * zcs)3000 size_t ZSTD_freeCStream(ZSTD_CStream *zcs)
3001 {
3002 if (zcs == NULL)
3003 return 0; /* support free on NULL */
3004 {
3005 ZSTD_customMem const cMem = zcs->customMem;
3006 ZSTD_freeCCtx(zcs->cctx);
3007 zcs->cctx = NULL;
3008 ZSTD_freeCDict(zcs->cdictLocal);
3009 zcs->cdictLocal = NULL;
3010 ZSTD_free(zcs->inBuff, cMem);
3011 zcs->inBuff = NULL;
3012 ZSTD_free(zcs->outBuff, cMem);
3013 zcs->outBuff = NULL;
3014 ZSTD_free(zcs, cMem);
3015 return 0;
3016 }
3017 }
3018
3019 /*====== Initialization ======*/
3020
ZSTD_CStreamInSize(void)3021 size_t ZSTD_CStreamInSize(void) { return ZSTD_BLOCKSIZE_ABSOLUTEMAX; }
ZSTD_CStreamOutSize(void)3022 size_t ZSTD_CStreamOutSize(void) { return ZSTD_compressBound(ZSTD_BLOCKSIZE_ABSOLUTEMAX) + ZSTD_blockHeaderSize + 4 /* 32-bits hash */; }
3023
ZSTD_resetCStream_internal(ZSTD_CStream * zcs,unsigned long long pledgedSrcSize)3024 static size_t ZSTD_resetCStream_internal(ZSTD_CStream *zcs, unsigned long long pledgedSrcSize)
3025 {
3026 if (zcs->inBuffSize == 0)
3027 return ERROR(stage_wrong); /* zcs has not been init at least once => can't reset */
3028
3029 if (zcs->cdict)
3030 CHECK_F(ZSTD_compressBegin_usingCDict(zcs->cctx, zcs->cdict, pledgedSrcSize))
3031 else
3032 CHECK_F(ZSTD_compressBegin_advanced(zcs->cctx, NULL, 0, zcs->params, pledgedSrcSize));
3033
3034 zcs->inToCompress = 0;
3035 zcs->inBuffPos = 0;
3036 zcs->inBuffTarget = zcs->blockSize;
3037 zcs->outBuffContentSize = zcs->outBuffFlushedSize = 0;
3038 zcs->stage = zcss_load;
3039 zcs->frameEnded = 0;
3040 zcs->pledgedSrcSize = pledgedSrcSize;
3041 zcs->inputProcessed = 0;
3042 return 0; /* ready to go */
3043 }
3044
ZSTD_resetCStream(ZSTD_CStream * zcs,unsigned long long pledgedSrcSize)3045 size_t ZSTD_resetCStream(ZSTD_CStream *zcs, unsigned long long pledgedSrcSize)
3046 {
3047
3048 zcs->params.fParams.contentSizeFlag = (pledgedSrcSize > 0);
3049
3050 return ZSTD_resetCStream_internal(zcs, pledgedSrcSize);
3051 }
3052
ZSTD_initCStream_advanced(ZSTD_CStream * zcs,const void * dict,size_t dictSize,ZSTD_parameters params,unsigned long long pledgedSrcSize)3053 static size_t ZSTD_initCStream_advanced(ZSTD_CStream *zcs, const void *dict, size_t dictSize, ZSTD_parameters params, unsigned long long pledgedSrcSize)
3054 {
3055 /* allocate buffers */
3056 {
3057 size_t const neededInBuffSize = (size_t)1 << params.cParams.windowLog;
3058 if (zcs->inBuffSize < neededInBuffSize) {
3059 zcs->inBuffSize = neededInBuffSize;
3060 ZSTD_free(zcs->inBuff, zcs->customMem);
3061 zcs->inBuff = (char *)ZSTD_malloc(neededInBuffSize, zcs->customMem);
3062 if (zcs->inBuff == NULL)
3063 return ERROR(memory_allocation);
3064 }
3065 zcs->blockSize = MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, neededInBuffSize);
3066 }
3067 if (zcs->outBuffSize < ZSTD_compressBound(zcs->blockSize) + 1) {
3068 zcs->outBuffSize = ZSTD_compressBound(zcs->blockSize) + 1;
3069 ZSTD_free(zcs->outBuff, zcs->customMem);
3070 zcs->outBuff = (char *)ZSTD_malloc(zcs->outBuffSize, zcs->customMem);
3071 if (zcs->outBuff == NULL)
3072 return ERROR(memory_allocation);
3073 }
3074
3075 if (dict && dictSize >= 8) {
3076 ZSTD_freeCDict(zcs->cdictLocal);
3077 zcs->cdictLocal = ZSTD_createCDict_advanced(dict, dictSize, 0, params, zcs->customMem);
3078 if (zcs->cdictLocal == NULL)
3079 return ERROR(memory_allocation);
3080 zcs->cdict = zcs->cdictLocal;
3081 } else
3082 zcs->cdict = NULL;
3083
3084 zcs->checksum = params.fParams.checksumFlag > 0;
3085 zcs->params = params;
3086
3087 return ZSTD_resetCStream_internal(zcs, pledgedSrcSize);
3088 }
3089
ZSTD_initCStream(ZSTD_parameters params,unsigned long long pledgedSrcSize,void * workspace,size_t workspaceSize)3090 ZSTD_CStream *ZSTD_initCStream(ZSTD_parameters params, unsigned long long pledgedSrcSize, void *workspace, size_t workspaceSize)
3091 {
3092 ZSTD_customMem const stackMem = ZSTD_initStack(workspace, workspaceSize);
3093 ZSTD_CStream *const zcs = ZSTD_createCStream_advanced(stackMem);
3094 if (zcs) {
3095 size_t const code = ZSTD_initCStream_advanced(zcs, NULL, 0, params, pledgedSrcSize);
3096 if (ZSTD_isError(code)) {
3097 return NULL;
3098 }
3099 }
3100 return zcs;
3101 }
3102
ZSTD_initCStream_usingCDict(const ZSTD_CDict * cdict,unsigned long long pledgedSrcSize,void * workspace,size_t workspaceSize)3103 ZSTD_CStream *ZSTD_initCStream_usingCDict(const ZSTD_CDict *cdict, unsigned long long pledgedSrcSize, void *workspace, size_t workspaceSize)
3104 {
3105 ZSTD_parameters const params = ZSTD_getParamsFromCDict(cdict);
3106 ZSTD_CStream *const zcs = ZSTD_initCStream(params, pledgedSrcSize, workspace, workspaceSize);
3107 if (zcs) {
3108 zcs->cdict = cdict;
3109 if (ZSTD_isError(ZSTD_resetCStream_internal(zcs, pledgedSrcSize))) {
3110 return NULL;
3111 }
3112 }
3113 return zcs;
3114 }
3115
3116 /*====== Compression ======*/
3117
3118 typedef enum { zsf_gather, zsf_flush, zsf_end } ZSTD_flush_e;
3119
ZSTD_limitCopy(void * dst,size_t dstCapacity,const void * src,size_t srcSize)3120 ZSTD_STATIC size_t ZSTD_limitCopy(void *dst, size_t dstCapacity, const void *src, size_t srcSize)
3121 {
3122 size_t const length = MIN(dstCapacity, srcSize);
3123 memcpy(dst, src, length);
3124 return length;
3125 }
3126
ZSTD_compressStream_generic(ZSTD_CStream * zcs,void * dst,size_t * dstCapacityPtr,const void * src,size_t * srcSizePtr,ZSTD_flush_e const flush)3127 static size_t ZSTD_compressStream_generic(ZSTD_CStream *zcs, void *dst, size_t *dstCapacityPtr, const void *src, size_t *srcSizePtr, ZSTD_flush_e const flush)
3128 {
3129 U32 someMoreWork = 1;
3130 const char *const istart = (const char *)src;
3131 const char *const iend = istart + *srcSizePtr;
3132 const char *ip = istart;
3133 char *const ostart = (char *)dst;
3134 char *const oend = ostart + *dstCapacityPtr;
3135 char *op = ostart;
3136
3137 while (someMoreWork) {
3138 switch (zcs->stage) {
3139 case zcss_init:
3140 return ERROR(init_missing); /* call ZBUFF_compressInit() first ! */
3141
3142 case zcss_load:
3143 /* complete inBuffer */
3144 {
3145 size_t const toLoad = zcs->inBuffTarget - zcs->inBuffPos;
3146 size_t const loaded = ZSTD_limitCopy(zcs->inBuff + zcs->inBuffPos, toLoad, ip, iend - ip);
3147 zcs->inBuffPos += loaded;
3148 ip += loaded;
3149 if ((zcs->inBuffPos == zcs->inToCompress) || (!flush && (toLoad != loaded))) {
3150 someMoreWork = 0;
3151 break; /* not enough input to get a full block : stop there, wait for more */
3152 }
3153 }
3154 /* compress curr block (note : this stage cannot be stopped in the middle) */
3155 {
3156 void *cDst;
3157 size_t cSize;
3158 size_t const iSize = zcs->inBuffPos - zcs->inToCompress;
3159 size_t oSize = oend - op;
3160 if (oSize >= ZSTD_compressBound(iSize))
3161 cDst = op; /* compress directly into output buffer (avoid flush stage) */
3162 else
3163 cDst = zcs->outBuff, oSize = zcs->outBuffSize;
3164 cSize = (flush == zsf_end) ? ZSTD_compressEnd(zcs->cctx, cDst, oSize, zcs->inBuff + zcs->inToCompress, iSize)
3165 : ZSTD_compressContinue(zcs->cctx, cDst, oSize, zcs->inBuff + zcs->inToCompress, iSize);
3166 if (ZSTD_isError(cSize))
3167 return cSize;
3168 if (flush == zsf_end)
3169 zcs->frameEnded = 1;
3170 /* prepare next block */
3171 zcs->inBuffTarget = zcs->inBuffPos + zcs->blockSize;
3172 if (zcs->inBuffTarget > zcs->inBuffSize)
3173 zcs->inBuffPos = 0, zcs->inBuffTarget = zcs->blockSize; /* note : inBuffSize >= blockSize */
3174 zcs->inToCompress = zcs->inBuffPos;
3175 if (cDst == op) {
3176 op += cSize;
3177 break;
3178 } /* no need to flush */
3179 zcs->outBuffContentSize = cSize;
3180 zcs->outBuffFlushedSize = 0;
3181 zcs->stage = zcss_flush; /* pass-through to flush stage */
3182 }
3183
3184 case zcss_flush: {
3185 size_t const toFlush = zcs->outBuffContentSize - zcs->outBuffFlushedSize;
3186 size_t const flushed = ZSTD_limitCopy(op, oend - op, zcs->outBuff + zcs->outBuffFlushedSize, toFlush);
3187 op += flushed;
3188 zcs->outBuffFlushedSize += flushed;
3189 if (toFlush != flushed) {
3190 someMoreWork = 0;
3191 break;
3192 } /* dst too small to store flushed data : stop there */
3193 zcs->outBuffContentSize = zcs->outBuffFlushedSize = 0;
3194 zcs->stage = zcss_load;
3195 break;
3196 }
3197
3198 case zcss_final:
3199 someMoreWork = 0; /* do nothing */
3200 break;
3201
3202 default:
3203 return ERROR(GENERIC); /* impossible */
3204 }
3205 }
3206
3207 *srcSizePtr = ip - istart;
3208 *dstCapacityPtr = op - ostart;
3209 zcs->inputProcessed += *srcSizePtr;
3210 if (zcs->frameEnded)
3211 return 0;
3212 {
3213 size_t hintInSize = zcs->inBuffTarget - zcs->inBuffPos;
3214 if (hintInSize == 0)
3215 hintInSize = zcs->blockSize;
3216 return hintInSize;
3217 }
3218 }
3219
ZSTD_compressStream(ZSTD_CStream * zcs,ZSTD_outBuffer * output,ZSTD_inBuffer * input)3220 size_t ZSTD_compressStream(ZSTD_CStream *zcs, ZSTD_outBuffer *output, ZSTD_inBuffer *input)
3221 {
3222 size_t sizeRead = input->size - input->pos;
3223 size_t sizeWritten = output->size - output->pos;
3224 size_t const result =
3225 ZSTD_compressStream_generic(zcs, (char *)(output->dst) + output->pos, &sizeWritten, (const char *)(input->src) + input->pos, &sizeRead, zsf_gather);
3226 input->pos += sizeRead;
3227 output->pos += sizeWritten;
3228 return result;
3229 }
3230
3231 /*====== Finalize ======*/
3232
3233 /*! ZSTD_flushStream() :
3234 * @return : amount of data remaining to flush */
ZSTD_flushStream(ZSTD_CStream * zcs,ZSTD_outBuffer * output)3235 size_t ZSTD_flushStream(ZSTD_CStream *zcs, ZSTD_outBuffer *output)
3236 {
3237 size_t srcSize = 0;
3238 size_t sizeWritten = output->size - output->pos;
3239 size_t const result = ZSTD_compressStream_generic(zcs, (char *)(output->dst) + output->pos, &sizeWritten, &srcSize,
3240 &srcSize, /* use a valid src address instead of NULL */
3241 zsf_flush);
3242 output->pos += sizeWritten;
3243 if (ZSTD_isError(result))
3244 return result;
3245 return zcs->outBuffContentSize - zcs->outBuffFlushedSize; /* remaining to flush */
3246 }
3247
ZSTD_endStream(ZSTD_CStream * zcs,ZSTD_outBuffer * output)3248 size_t ZSTD_endStream(ZSTD_CStream *zcs, ZSTD_outBuffer *output)
3249 {
3250 BYTE *const ostart = (BYTE *)(output->dst) + output->pos;
3251 BYTE *const oend = (BYTE *)(output->dst) + output->size;
3252 BYTE *op = ostart;
3253
3254 if ((zcs->pledgedSrcSize) && (zcs->inputProcessed != zcs->pledgedSrcSize))
3255 return ERROR(srcSize_wrong); /* pledgedSrcSize not respected */
3256
3257 if (zcs->stage != zcss_final) {
3258 /* flush whatever remains */
3259 size_t srcSize = 0;
3260 size_t sizeWritten = output->size - output->pos;
3261 size_t const notEnded =
3262 ZSTD_compressStream_generic(zcs, ostart, &sizeWritten, &srcSize, &srcSize, zsf_end); /* use a valid src address instead of NULL */
3263 size_t const remainingToFlush = zcs->outBuffContentSize - zcs->outBuffFlushedSize;
3264 op += sizeWritten;
3265 if (remainingToFlush) {
3266 output->pos += sizeWritten;
3267 return remainingToFlush + ZSTD_BLOCKHEADERSIZE /* final empty block */ + (zcs->checksum * 4);
3268 }
3269 /* create epilogue */
3270 zcs->stage = zcss_final;
3271 zcs->outBuffContentSize = !notEnded ? 0 : ZSTD_compressEnd(zcs->cctx, zcs->outBuff, zcs->outBuffSize, NULL,
3272 0); /* write epilogue, including final empty block, into outBuff */
3273 }
3274
3275 /* flush epilogue */
3276 {
3277 size_t const toFlush = zcs->outBuffContentSize - zcs->outBuffFlushedSize;
3278 size_t const flushed = ZSTD_limitCopy(op, oend - op, zcs->outBuff + zcs->outBuffFlushedSize, toFlush);
3279 op += flushed;
3280 zcs->outBuffFlushedSize += flushed;
3281 output->pos += op - ostart;
3282 if (toFlush == flushed)
3283 zcs->stage = zcss_init; /* end reached */
3284 return toFlush - flushed;
3285 }
3286 }
3287
3288 /*-===== Pre-defined compression levels =====-*/
3289
3290 #define ZSTD_DEFAULT_CLEVEL 1
3291 #define ZSTD_MAX_CLEVEL 22
ZSTD_maxCLevel(void)3292 int ZSTD_maxCLevel(void) { return ZSTD_MAX_CLEVEL; }
3293
3294 static const ZSTD_compressionParameters ZSTD_defaultCParameters[4][ZSTD_MAX_CLEVEL + 1] = {
3295 {
3296 /* "default" */
3297 /* W, C, H, S, L, TL, strat */
3298 {18, 12, 12, 1, 7, 16, ZSTD_fast}, /* level 0 - never used */
3299 {19, 13, 14, 1, 7, 16, ZSTD_fast}, /* level 1 */
3300 {19, 15, 16, 1, 6, 16, ZSTD_fast}, /* level 2 */
3301 {20, 16, 17, 1, 5, 16, ZSTD_dfast}, /* level 3.*/
3302 {20, 18, 18, 1, 5, 16, ZSTD_dfast}, /* level 4.*/
3303 {20, 15, 18, 3, 5, 16, ZSTD_greedy}, /* level 5 */
3304 {21, 16, 19, 2, 5, 16, ZSTD_lazy}, /* level 6 */
3305 {21, 17, 20, 3, 5, 16, ZSTD_lazy}, /* level 7 */
3306 {21, 18, 20, 3, 5, 16, ZSTD_lazy2}, /* level 8 */
3307 {21, 20, 20, 3, 5, 16, ZSTD_lazy2}, /* level 9 */
3308 {21, 19, 21, 4, 5, 16, ZSTD_lazy2}, /* level 10 */
3309 {22, 20, 22, 4, 5, 16, ZSTD_lazy2}, /* level 11 */
3310 {22, 20, 22, 5, 5, 16, ZSTD_lazy2}, /* level 12 */
3311 {22, 21, 22, 5, 5, 16, ZSTD_lazy2}, /* level 13 */
3312 {22, 21, 22, 6, 5, 16, ZSTD_lazy2}, /* level 14 */
3313 {22, 21, 21, 5, 5, 16, ZSTD_btlazy2}, /* level 15 */
3314 {23, 22, 22, 5, 5, 16, ZSTD_btlazy2}, /* level 16 */
3315 {23, 21, 22, 4, 5, 24, ZSTD_btopt}, /* level 17 */
3316 {23, 23, 22, 6, 5, 32, ZSTD_btopt}, /* level 18 */
3317 {23, 23, 22, 6, 3, 48, ZSTD_btopt}, /* level 19 */
3318 {25, 25, 23, 7, 3, 64, ZSTD_btopt2}, /* level 20 */
3319 {26, 26, 23, 7, 3, 256, ZSTD_btopt2}, /* level 21 */
3320 {27, 27, 25, 9, 3, 512, ZSTD_btopt2}, /* level 22 */
3321 },
3322 {
3323 /* for srcSize <= 256 KB */
3324 /* W, C, H, S, L, T, strat */
3325 {0, 0, 0, 0, 0, 0, ZSTD_fast}, /* level 0 - not used */
3326 {18, 13, 14, 1, 6, 8, ZSTD_fast}, /* level 1 */
3327 {18, 14, 13, 1, 5, 8, ZSTD_dfast}, /* level 2 */
3328 {18, 16, 15, 1, 5, 8, ZSTD_dfast}, /* level 3 */
3329 {18, 15, 17, 1, 5, 8, ZSTD_greedy}, /* level 4.*/
3330 {18, 16, 17, 4, 5, 8, ZSTD_greedy}, /* level 5.*/
3331 {18, 16, 17, 3, 5, 8, ZSTD_lazy}, /* level 6.*/
3332 {18, 17, 17, 4, 4, 8, ZSTD_lazy}, /* level 7 */
3333 {18, 17, 17, 4, 4, 8, ZSTD_lazy2}, /* level 8 */
3334 {18, 17, 17, 5, 4, 8, ZSTD_lazy2}, /* level 9 */
3335 {18, 17, 17, 6, 4, 8, ZSTD_lazy2}, /* level 10 */
3336 {18, 18, 17, 6, 4, 8, ZSTD_lazy2}, /* level 11.*/
3337 {18, 18, 17, 7, 4, 8, ZSTD_lazy2}, /* level 12.*/
3338 {18, 19, 17, 6, 4, 8, ZSTD_btlazy2}, /* level 13 */
3339 {18, 18, 18, 4, 4, 16, ZSTD_btopt}, /* level 14.*/
3340 {18, 18, 18, 4, 3, 16, ZSTD_btopt}, /* level 15.*/
3341 {18, 19, 18, 6, 3, 32, ZSTD_btopt}, /* level 16.*/
3342 {18, 19, 18, 8, 3, 64, ZSTD_btopt}, /* level 17.*/
3343 {18, 19, 18, 9, 3, 128, ZSTD_btopt}, /* level 18.*/
3344 {18, 19, 18, 10, 3, 256, ZSTD_btopt}, /* level 19.*/
3345 {18, 19, 18, 11, 3, 512, ZSTD_btopt2}, /* level 20.*/
3346 {18, 19, 18, 12, 3, 512, ZSTD_btopt2}, /* level 21.*/
3347 {18, 19, 18, 13, 3, 512, ZSTD_btopt2}, /* level 22.*/
3348 },
3349 {
3350 /* for srcSize <= 128 KB */
3351 /* W, C, H, S, L, T, strat */
3352 {17, 12, 12, 1, 7, 8, ZSTD_fast}, /* level 0 - not used */
3353 {17, 12, 13, 1, 6, 8, ZSTD_fast}, /* level 1 */
3354 {17, 13, 16, 1, 5, 8, ZSTD_fast}, /* level 2 */
3355 {17, 16, 16, 2, 5, 8, ZSTD_dfast}, /* level 3 */
3356 {17, 13, 15, 3, 4, 8, ZSTD_greedy}, /* level 4 */
3357 {17, 15, 17, 4, 4, 8, ZSTD_greedy}, /* level 5 */
3358 {17, 16, 17, 3, 4, 8, ZSTD_lazy}, /* level 6 */
3359 {17, 15, 17, 4, 4, 8, ZSTD_lazy2}, /* level 7 */
3360 {17, 17, 17, 4, 4, 8, ZSTD_lazy2}, /* level 8 */
3361 {17, 17, 17, 5, 4, 8, ZSTD_lazy2}, /* level 9 */
3362 {17, 17, 17, 6, 4, 8, ZSTD_lazy2}, /* level 10 */
3363 {17, 17, 17, 7, 4, 8, ZSTD_lazy2}, /* level 11 */
3364 {17, 17, 17, 8, 4, 8, ZSTD_lazy2}, /* level 12 */
3365 {17, 18, 17, 6, 4, 8, ZSTD_btlazy2}, /* level 13.*/
3366 {17, 17, 17, 7, 3, 8, ZSTD_btopt}, /* level 14.*/
3367 {17, 17, 17, 7, 3, 16, ZSTD_btopt}, /* level 15.*/
3368 {17, 18, 17, 7, 3, 32, ZSTD_btopt}, /* level 16.*/
3369 {17, 18, 17, 7, 3, 64, ZSTD_btopt}, /* level 17.*/
3370 {17, 18, 17, 7, 3, 256, ZSTD_btopt}, /* level 18.*/
3371 {17, 18, 17, 8, 3, 256, ZSTD_btopt}, /* level 19.*/
3372 {17, 18, 17, 9, 3, 256, ZSTD_btopt2}, /* level 20.*/
3373 {17, 18, 17, 10, 3, 256, ZSTD_btopt2}, /* level 21.*/
3374 {17, 18, 17, 11, 3, 512, ZSTD_btopt2}, /* level 22.*/
3375 },
3376 {
3377 /* for srcSize <= 16 KB */
3378 /* W, C, H, S, L, T, strat */
3379 {14, 12, 12, 1, 7, 6, ZSTD_fast}, /* level 0 - not used */
3380 {14, 14, 14, 1, 6, 6, ZSTD_fast}, /* level 1 */
3381 {14, 14, 14, 1, 4, 6, ZSTD_fast}, /* level 2 */
3382 {14, 14, 14, 1, 4, 6, ZSTD_dfast}, /* level 3.*/
3383 {14, 14, 14, 4, 4, 6, ZSTD_greedy}, /* level 4.*/
3384 {14, 14, 14, 3, 4, 6, ZSTD_lazy}, /* level 5.*/
3385 {14, 14, 14, 4, 4, 6, ZSTD_lazy2}, /* level 6 */
3386 {14, 14, 14, 5, 4, 6, ZSTD_lazy2}, /* level 7 */
3387 {14, 14, 14, 6, 4, 6, ZSTD_lazy2}, /* level 8.*/
3388 {14, 15, 14, 6, 4, 6, ZSTD_btlazy2}, /* level 9.*/
3389 {14, 15, 14, 3, 3, 6, ZSTD_btopt}, /* level 10.*/
3390 {14, 15, 14, 6, 3, 8, ZSTD_btopt}, /* level 11.*/
3391 {14, 15, 14, 6, 3, 16, ZSTD_btopt}, /* level 12.*/
3392 {14, 15, 14, 6, 3, 24, ZSTD_btopt}, /* level 13.*/
3393 {14, 15, 15, 6, 3, 48, ZSTD_btopt}, /* level 14.*/
3394 {14, 15, 15, 6, 3, 64, ZSTD_btopt}, /* level 15.*/
3395 {14, 15, 15, 6, 3, 96, ZSTD_btopt}, /* level 16.*/
3396 {14, 15, 15, 6, 3, 128, ZSTD_btopt}, /* level 17.*/
3397 {14, 15, 15, 6, 3, 256, ZSTD_btopt}, /* level 18.*/
3398 {14, 15, 15, 7, 3, 256, ZSTD_btopt}, /* level 19.*/
3399 {14, 15, 15, 8, 3, 256, ZSTD_btopt2}, /* level 20.*/
3400 {14, 15, 15, 9, 3, 256, ZSTD_btopt2}, /* level 21.*/
3401 {14, 15, 15, 10, 3, 256, ZSTD_btopt2}, /* level 22.*/
3402 },
3403 };
3404
3405 /*! ZSTD_getCParams() :
3406 * @return ZSTD_compressionParameters structure for a selected compression level, `srcSize` and `dictSize`.
3407 * Size values are optional, provide 0 if not known or unused */
ZSTD_getCParams(int compressionLevel,unsigned long long srcSize,size_t dictSize)3408 ZSTD_compressionParameters ZSTD_getCParams(int compressionLevel, unsigned long long srcSize, size_t dictSize)
3409 {
3410 ZSTD_compressionParameters cp;
3411 size_t const addedSize = srcSize ? 0 : 500;
3412 U64 const rSize = srcSize + dictSize ? srcSize + dictSize + addedSize : (U64)-1;
3413 U32 const tableID = (rSize <= 256 KB) + (rSize <= 128 KB) + (rSize <= 16 KB); /* intentional underflow for srcSizeHint == 0 */
3414 if (compressionLevel <= 0)
3415 compressionLevel = ZSTD_DEFAULT_CLEVEL; /* 0 == default; no negative compressionLevel yet */
3416 if (compressionLevel > ZSTD_MAX_CLEVEL)
3417 compressionLevel = ZSTD_MAX_CLEVEL;
3418 cp = ZSTD_defaultCParameters[tableID][compressionLevel];
3419 if (ZSTD_32bits()) { /* auto-correction, for 32-bits mode */
3420 if (cp.windowLog > ZSTD_WINDOWLOG_MAX)
3421 cp.windowLog = ZSTD_WINDOWLOG_MAX;
3422 if (cp.chainLog > ZSTD_CHAINLOG_MAX)
3423 cp.chainLog = ZSTD_CHAINLOG_MAX;
3424 if (cp.hashLog > ZSTD_HASHLOG_MAX)
3425 cp.hashLog = ZSTD_HASHLOG_MAX;
3426 }
3427 cp = ZSTD_adjustCParams(cp, srcSize, dictSize);
3428 return cp;
3429 }
3430
3431 /*! ZSTD_getParams() :
3432 * same as ZSTD_getCParams(), but @return a `ZSTD_parameters` object (instead of `ZSTD_compressionParameters`).
3433 * All fields of `ZSTD_frameParameters` are set to default (0) */
ZSTD_getParams(int compressionLevel,unsigned long long srcSize,size_t dictSize)3434 ZSTD_parameters ZSTD_getParams(int compressionLevel, unsigned long long srcSize, size_t dictSize)
3435 {
3436 ZSTD_parameters params;
3437 ZSTD_compressionParameters const cParams = ZSTD_getCParams(compressionLevel, srcSize, dictSize);
3438 memset(¶ms, 0, sizeof(params));
3439 params.cParams = cParams;
3440 return params;
3441 }
3442
3443 EXPORT_SYMBOL(ZSTD_maxCLevel);
3444 EXPORT_SYMBOL(ZSTD_compressBound);
3445
3446 EXPORT_SYMBOL(ZSTD_CCtxWorkspaceBound);
3447 EXPORT_SYMBOL(ZSTD_initCCtx);
3448 EXPORT_SYMBOL(ZSTD_compressCCtx);
3449 EXPORT_SYMBOL(ZSTD_compress_usingDict);
3450
3451 EXPORT_SYMBOL(ZSTD_CDictWorkspaceBound);
3452 EXPORT_SYMBOL(ZSTD_initCDict);
3453 EXPORT_SYMBOL(ZSTD_compress_usingCDict);
3454
3455 EXPORT_SYMBOL(ZSTD_CStreamWorkspaceBound);
3456 EXPORT_SYMBOL(ZSTD_initCStream);
3457 EXPORT_SYMBOL(ZSTD_initCStream_usingCDict);
3458 EXPORT_SYMBOL(ZSTD_resetCStream);
3459 EXPORT_SYMBOL(ZSTD_compressStream);
3460 EXPORT_SYMBOL(ZSTD_flushStream);
3461 EXPORT_SYMBOL(ZSTD_endStream);
3462 EXPORT_SYMBOL(ZSTD_CStreamInSize);
3463 EXPORT_SYMBOL(ZSTD_CStreamOutSize);
3464
3465 EXPORT_SYMBOL(ZSTD_getCParams);
3466 EXPORT_SYMBOL(ZSTD_getParams);
3467 EXPORT_SYMBOL(ZSTD_checkCParams);
3468 EXPORT_SYMBOL(ZSTD_adjustCParams);
3469
3470 EXPORT_SYMBOL(ZSTD_compressBegin);
3471 EXPORT_SYMBOL(ZSTD_compressBegin_usingDict);
3472 EXPORT_SYMBOL(ZSTD_compressBegin_advanced);
3473 EXPORT_SYMBOL(ZSTD_copyCCtx);
3474 EXPORT_SYMBOL(ZSTD_compressBegin_usingCDict);
3475 EXPORT_SYMBOL(ZSTD_compressContinue);
3476 EXPORT_SYMBOL(ZSTD_compressEnd);
3477
3478 EXPORT_SYMBOL(ZSTD_getBlockSizeMax);
3479 EXPORT_SYMBOL(ZSTD_compressBlock);
3480
3481 MODULE_LICENSE("Dual BSD/GPL");
3482 MODULE_DESCRIPTION("Zstd Compressor");
3483