1 /*
2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
3 * All rights reserved.
4 *
5 * This source code is licensed under both the BSD-style license (found in the
6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
7 * in the COPYING file in the root directory of this source tree).
8 * You may select, at your option, one of the above-listed licenses.
9 */
10
11 /*-*************************************
12 * Dependencies
13 ***************************************/
14 #include <string.h> /* memset */
15 #include "cpu.h"
16 #include "mem.h"
17 #include "hist.h" /* HIST_countFast_wksp */
18 #define FSE_STATIC_LINKING_ONLY /* FSE_encodeSymbol */
19 #include "fse.h"
20 #define HUF_STATIC_LINKING_ONLY
21 #include "huf.h"
22 #include "zstd_compress_internal.h"
23 #include "zstd_fast.h"
24 #include "zstd_double_fast.h"
25 #include "zstd_lazy.h"
26 #include "zstd_opt.h"
27 #include "zstd_ldm.h"
28
29
30 /*-*************************************
31 * Helper functions
32 ***************************************/
ZSTD_compressBound(size_t srcSize)33 size_t ZSTD_compressBound(size_t srcSize) {
34 return ZSTD_COMPRESSBOUND(srcSize);
35 }
36
37
38 /*-*************************************
39 * Context memory management
40 ***************************************/
41 struct ZSTD_CDict_s {
42 void* dictBuffer;
43 const void* dictContent;
44 size_t dictContentSize;
45 void* workspace;
46 size_t workspaceSize;
47 ZSTD_matchState_t matchState;
48 ZSTD_compressedBlockState_t cBlockState;
49 ZSTD_customMem customMem;
50 U32 dictID;
51 }; /* typedef'd to ZSTD_CDict within "zstd.h" */
52
ZSTD_createCCtx(void)53 ZSTD_CCtx* ZSTD_createCCtx(void)
54 {
55 return ZSTD_createCCtx_advanced(ZSTD_defaultCMem);
56 }
57
ZSTD_initCCtx(ZSTD_CCtx * cctx,ZSTD_customMem memManager)58 static void ZSTD_initCCtx(ZSTD_CCtx* cctx, ZSTD_customMem memManager)
59 {
60 assert(cctx != NULL);
61 memset(cctx, 0, sizeof(*cctx));
62 cctx->customMem = memManager;
63 cctx->bmi2 = ZSTD_cpuid_bmi2(ZSTD_cpuid());
64 { size_t const err = ZSTD_CCtx_resetParameters(cctx);
65 assert(!ZSTD_isError(err));
66 (void)err;
67 }
68 }
69
ZSTD_createCCtx_advanced(ZSTD_customMem customMem)70 ZSTD_CCtx* ZSTD_createCCtx_advanced(ZSTD_customMem customMem)
71 {
72 ZSTD_STATIC_ASSERT(zcss_init==0);
73 ZSTD_STATIC_ASSERT(ZSTD_CONTENTSIZE_UNKNOWN==(0ULL - 1));
74 if (!customMem.customAlloc ^ !customMem.customFree) return NULL;
75 { ZSTD_CCtx* const cctx = (ZSTD_CCtx*)ZSTD_malloc(sizeof(ZSTD_CCtx), customMem);
76 if (!cctx) return NULL;
77 ZSTD_initCCtx(cctx, customMem);
78 return cctx;
79 }
80 }
81
ZSTD_initStaticCCtx(void * workspace,size_t workspaceSize)82 ZSTD_CCtx* ZSTD_initStaticCCtx(void *workspace, size_t workspaceSize)
83 {
84 ZSTD_CCtx* const cctx = (ZSTD_CCtx*) workspace;
85 if (workspaceSize <= sizeof(ZSTD_CCtx)) return NULL; /* minimum size */
86 if ((size_t)workspace & 7) return NULL; /* must be 8-aligned */
87 memset(workspace, 0, workspaceSize); /* may be a bit generous, could memset be smaller ? */
88 cctx->staticSize = workspaceSize;
89 cctx->workSpace = (void*)(cctx+1);
90 cctx->workSpaceSize = workspaceSize - sizeof(ZSTD_CCtx);
91
92 /* statically sized space. entropyWorkspace never moves (but prev/next block swap places) */
93 if (cctx->workSpaceSize < HUF_WORKSPACE_SIZE + 2 * sizeof(ZSTD_compressedBlockState_t)) return NULL;
94 assert(((size_t)cctx->workSpace & (sizeof(void*)-1)) == 0); /* ensure correct alignment */
95 cctx->blockState.prevCBlock = (ZSTD_compressedBlockState_t*)cctx->workSpace;
96 cctx->blockState.nextCBlock = cctx->blockState.prevCBlock + 1;
97 {
98 void* const ptr = cctx->blockState.nextCBlock + 1;
99 cctx->entropyWorkspace = (U32*)ptr;
100 }
101 cctx->bmi2 = ZSTD_cpuid_bmi2(ZSTD_cpuid());
102 return cctx;
103 }
104
ZSTD_freeCCtxContent(ZSTD_CCtx * cctx)105 static void ZSTD_freeCCtxContent(ZSTD_CCtx* cctx)
106 {
107 assert(cctx != NULL);
108 assert(cctx->staticSize == 0);
109 ZSTD_free(cctx->workSpace, cctx->customMem); cctx->workSpace = NULL;
110 ZSTD_freeCDict(cctx->cdictLocal); cctx->cdictLocal = NULL;
111 #ifdef ZSTD_MULTITHREAD
112 ZSTDMT_freeCCtx(cctx->mtctx); cctx->mtctx = NULL;
113 #endif
114 }
115
ZSTD_freeCCtx(ZSTD_CCtx * cctx)116 size_t ZSTD_freeCCtx(ZSTD_CCtx* cctx)
117 {
118 if (cctx==NULL) return 0; /* support free on NULL */
119 if (cctx->staticSize) return ERROR(memory_allocation); /* not compatible with static CCtx */
120 ZSTD_freeCCtxContent(cctx);
121 ZSTD_free(cctx, cctx->customMem);
122 return 0;
123 }
124
125
ZSTD_sizeof_mtctx(const ZSTD_CCtx * cctx)126 static size_t ZSTD_sizeof_mtctx(const ZSTD_CCtx* cctx)
127 {
128 #ifdef ZSTD_MULTITHREAD
129 return ZSTDMT_sizeof_CCtx(cctx->mtctx);
130 #else
131 (void) cctx;
132 return 0;
133 #endif
134 }
135
136
ZSTD_sizeof_CCtx(const ZSTD_CCtx * cctx)137 size_t ZSTD_sizeof_CCtx(const ZSTD_CCtx* cctx)
138 {
139 if (cctx==NULL) return 0; /* support sizeof on NULL */
140 return sizeof(*cctx) + cctx->workSpaceSize
141 + ZSTD_sizeof_CDict(cctx->cdictLocal)
142 + ZSTD_sizeof_mtctx(cctx);
143 }
144
ZSTD_sizeof_CStream(const ZSTD_CStream * zcs)145 size_t ZSTD_sizeof_CStream(const ZSTD_CStream* zcs)
146 {
147 return ZSTD_sizeof_CCtx(zcs); /* same object */
148 }
149
150 /* private API call, for dictBuilder only */
ZSTD_getSeqStore(const ZSTD_CCtx * ctx)151 const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx) { return &(ctx->seqStore); }
152
ZSTD_makeCCtxParamsFromCParams(ZSTD_compressionParameters cParams)153 static ZSTD_CCtx_params ZSTD_makeCCtxParamsFromCParams(
154 ZSTD_compressionParameters cParams)
155 {
156 ZSTD_CCtx_params cctxParams;
157 memset(&cctxParams, 0, sizeof(cctxParams));
158 cctxParams.cParams = cParams;
159 cctxParams.compressionLevel = ZSTD_CLEVEL_DEFAULT; /* should not matter, as all cParams are presumed properly defined */
160 assert(!ZSTD_checkCParams(cParams));
161 cctxParams.fParams.contentSizeFlag = 1;
162 return cctxParams;
163 }
164
ZSTD_createCCtxParams_advanced(ZSTD_customMem customMem)165 static ZSTD_CCtx_params* ZSTD_createCCtxParams_advanced(
166 ZSTD_customMem customMem)
167 {
168 ZSTD_CCtx_params* params;
169 if (!customMem.customAlloc ^ !customMem.customFree) return NULL;
170 params = (ZSTD_CCtx_params*)ZSTD_calloc(
171 sizeof(ZSTD_CCtx_params), customMem);
172 if (!params) { return NULL; }
173 params->customMem = customMem;
174 params->compressionLevel = ZSTD_CLEVEL_DEFAULT;
175 params->fParams.contentSizeFlag = 1;
176 return params;
177 }
178
ZSTD_createCCtxParams(void)179 ZSTD_CCtx_params* ZSTD_createCCtxParams(void)
180 {
181 return ZSTD_createCCtxParams_advanced(ZSTD_defaultCMem);
182 }
183
ZSTD_freeCCtxParams(ZSTD_CCtx_params * params)184 size_t ZSTD_freeCCtxParams(ZSTD_CCtx_params* params)
185 {
186 if (params == NULL) { return 0; }
187 ZSTD_free(params, params->customMem);
188 return 0;
189 }
190
ZSTD_CCtxParams_reset(ZSTD_CCtx_params * params)191 size_t ZSTD_CCtxParams_reset(ZSTD_CCtx_params* params)
192 {
193 return ZSTD_CCtxParams_init(params, ZSTD_CLEVEL_DEFAULT);
194 }
195
ZSTD_CCtxParams_init(ZSTD_CCtx_params * cctxParams,int compressionLevel)196 size_t ZSTD_CCtxParams_init(ZSTD_CCtx_params* cctxParams, int compressionLevel) {
197 if (!cctxParams) { return ERROR(GENERIC); }
198 memset(cctxParams, 0, sizeof(*cctxParams));
199 cctxParams->compressionLevel = compressionLevel;
200 cctxParams->fParams.contentSizeFlag = 1;
201 return 0;
202 }
203
ZSTD_CCtxParams_init_advanced(ZSTD_CCtx_params * cctxParams,ZSTD_parameters params)204 size_t ZSTD_CCtxParams_init_advanced(ZSTD_CCtx_params* cctxParams, ZSTD_parameters params)
205 {
206 if (!cctxParams) { return ERROR(GENERIC); }
207 CHECK_F( ZSTD_checkCParams(params.cParams) );
208 memset(cctxParams, 0, sizeof(*cctxParams));
209 cctxParams->cParams = params.cParams;
210 cctxParams->fParams = params.fParams;
211 cctxParams->compressionLevel = ZSTD_CLEVEL_DEFAULT; /* should not matter, as all cParams are presumed properly defined */
212 assert(!ZSTD_checkCParams(params.cParams));
213 return 0;
214 }
215
216 /* ZSTD_assignParamsToCCtxParams() :
217 * params is presumed valid at this stage */
ZSTD_assignParamsToCCtxParams(ZSTD_CCtx_params cctxParams,ZSTD_parameters params)218 static ZSTD_CCtx_params ZSTD_assignParamsToCCtxParams(
219 ZSTD_CCtx_params cctxParams, ZSTD_parameters params)
220 {
221 ZSTD_CCtx_params ret = cctxParams;
222 ret.cParams = params.cParams;
223 ret.fParams = params.fParams;
224 ret.compressionLevel = ZSTD_CLEVEL_DEFAULT; /* should not matter, as all cParams are presumed properly defined */
225 assert(!ZSTD_checkCParams(params.cParams));
226 return ret;
227 }
228
229 #define CLAMPCHECK(val,min,max) { \
230 if (((val)<(min)) | ((val)>(max))) { \
231 return ERROR(parameter_outOfBound); \
232 } }
233
234
ZSTD_isUpdateAuthorized(ZSTD_cParameter param)235 static int ZSTD_isUpdateAuthorized(ZSTD_cParameter param)
236 {
237 switch(param)
238 {
239 case ZSTD_p_compressionLevel:
240 case ZSTD_p_hashLog:
241 case ZSTD_p_chainLog:
242 case ZSTD_p_searchLog:
243 case ZSTD_p_minMatch:
244 case ZSTD_p_targetLength:
245 case ZSTD_p_compressionStrategy:
246 return 1;
247
248 case ZSTD_p_format:
249 case ZSTD_p_windowLog:
250 case ZSTD_p_contentSizeFlag:
251 case ZSTD_p_checksumFlag:
252 case ZSTD_p_dictIDFlag:
253 case ZSTD_p_forceMaxWindow :
254 case ZSTD_p_nbWorkers:
255 case ZSTD_p_jobSize:
256 case ZSTD_p_overlapSizeLog:
257 case ZSTD_p_rsyncable:
258 case ZSTD_p_enableLongDistanceMatching:
259 case ZSTD_p_ldmHashLog:
260 case ZSTD_p_ldmMinMatch:
261 case ZSTD_p_ldmBucketSizeLog:
262 case ZSTD_p_ldmHashEveryLog:
263 case ZSTD_p_forceAttachDict:
264 default:
265 return 0;
266 }
267 }
268
ZSTD_CCtx_setParameter(ZSTD_CCtx * cctx,ZSTD_cParameter param,unsigned value)269 size_t ZSTD_CCtx_setParameter(ZSTD_CCtx* cctx, ZSTD_cParameter param, unsigned value)
270 {
271 DEBUGLOG(4, "ZSTD_CCtx_setParameter (%u, %u)", (U32)param, value);
272 if (cctx->streamStage != zcss_init) {
273 if (ZSTD_isUpdateAuthorized(param)) {
274 cctx->cParamsChanged = 1;
275 } else {
276 return ERROR(stage_wrong);
277 } }
278
279 switch(param)
280 {
281 case ZSTD_p_format :
282 return ZSTD_CCtxParam_setParameter(&cctx->requestedParams, param, value);
283
284 case ZSTD_p_compressionLevel:
285 if (cctx->cdict) return ERROR(stage_wrong);
286 return ZSTD_CCtxParam_setParameter(&cctx->requestedParams, param, value);
287
288 case ZSTD_p_windowLog:
289 case ZSTD_p_hashLog:
290 case ZSTD_p_chainLog:
291 case ZSTD_p_searchLog:
292 case ZSTD_p_minMatch:
293 case ZSTD_p_targetLength:
294 case ZSTD_p_compressionStrategy:
295 if (cctx->cdict) return ERROR(stage_wrong);
296 return ZSTD_CCtxParam_setParameter(&cctx->requestedParams, param, value);
297
298 case ZSTD_p_contentSizeFlag:
299 case ZSTD_p_checksumFlag:
300 case ZSTD_p_dictIDFlag:
301 return ZSTD_CCtxParam_setParameter(&cctx->requestedParams, param, value);
302
303 case ZSTD_p_forceMaxWindow : /* Force back-references to remain < windowSize,
304 * even when referencing into Dictionary content.
305 * default : 0 when using a CDict, 1 when using a Prefix */
306 return ZSTD_CCtxParam_setParameter(&cctx->requestedParams, param, value);
307
308 case ZSTD_p_forceAttachDict:
309 return ZSTD_CCtxParam_setParameter(&cctx->requestedParams, param, value);
310
311 case ZSTD_p_nbWorkers:
312 if ((value>0) && cctx->staticSize) {
313 return ERROR(parameter_unsupported); /* MT not compatible with static alloc */
314 }
315 return ZSTD_CCtxParam_setParameter(&cctx->requestedParams, param, value);
316
317 case ZSTD_p_jobSize:
318 case ZSTD_p_overlapSizeLog:
319 case ZSTD_p_rsyncable:
320 return ZSTD_CCtxParam_setParameter(&cctx->requestedParams, param, value);
321
322 case ZSTD_p_enableLongDistanceMatching:
323 case ZSTD_p_ldmHashLog:
324 case ZSTD_p_ldmMinMatch:
325 case ZSTD_p_ldmBucketSizeLog:
326 case ZSTD_p_ldmHashEveryLog:
327 if (cctx->cdict) return ERROR(stage_wrong);
328 return ZSTD_CCtxParam_setParameter(&cctx->requestedParams, param, value);
329
330 default: return ERROR(parameter_unsupported);
331 }
332 }
333
ZSTD_CCtxParam_setParameter(ZSTD_CCtx_params * CCtxParams,ZSTD_cParameter param,unsigned value)334 size_t ZSTD_CCtxParam_setParameter(
335 ZSTD_CCtx_params* CCtxParams, ZSTD_cParameter param, unsigned value)
336 {
337 DEBUGLOG(4, "ZSTD_CCtxParam_setParameter (%u, %u)", (U32)param, value);
338 switch(param)
339 {
340 case ZSTD_p_format :
341 if (value > (unsigned)ZSTD_f_zstd1_magicless)
342 return ERROR(parameter_unsupported);
343 CCtxParams->format = (ZSTD_format_e)value;
344 return (size_t)CCtxParams->format;
345
346 case ZSTD_p_compressionLevel : {
347 int cLevel = (int)value; /* cast expected to restore negative sign */
348 if (cLevel > ZSTD_maxCLevel()) cLevel = ZSTD_maxCLevel();
349 if (cLevel) { /* 0 : does not change current level */
350 CCtxParams->compressionLevel = cLevel;
351 }
352 if (CCtxParams->compressionLevel >= 0) return CCtxParams->compressionLevel;
353 return 0; /* return type (size_t) cannot represent negative values */
354 }
355
356 case ZSTD_p_windowLog :
357 if (value>0) /* 0 => use default */
358 CLAMPCHECK(value, ZSTD_WINDOWLOG_MIN, ZSTD_WINDOWLOG_MAX);
359 CCtxParams->cParams.windowLog = value;
360 return CCtxParams->cParams.windowLog;
361
362 case ZSTD_p_hashLog :
363 if (value>0) /* 0 => use default */
364 CLAMPCHECK(value, ZSTD_HASHLOG_MIN, ZSTD_HASHLOG_MAX);
365 CCtxParams->cParams.hashLog = value;
366 return CCtxParams->cParams.hashLog;
367
368 case ZSTD_p_chainLog :
369 if (value>0) /* 0 => use default */
370 CLAMPCHECK(value, ZSTD_CHAINLOG_MIN, ZSTD_CHAINLOG_MAX);
371 CCtxParams->cParams.chainLog = value;
372 return CCtxParams->cParams.chainLog;
373
374 case ZSTD_p_searchLog :
375 if (value>0) /* 0 => use default */
376 CLAMPCHECK(value, ZSTD_SEARCHLOG_MIN, ZSTD_SEARCHLOG_MAX);
377 CCtxParams->cParams.searchLog = value;
378 return value;
379
380 case ZSTD_p_minMatch :
381 if (value>0) /* 0 => use default */
382 CLAMPCHECK(value, ZSTD_SEARCHLENGTH_MIN, ZSTD_SEARCHLENGTH_MAX);
383 CCtxParams->cParams.searchLength = value;
384 return CCtxParams->cParams.searchLength;
385
386 case ZSTD_p_targetLength :
387 /* all values are valid. 0 => use default */
388 CCtxParams->cParams.targetLength = value;
389 return CCtxParams->cParams.targetLength;
390
391 case ZSTD_p_compressionStrategy :
392 if (value>0) /* 0 => use default */
393 CLAMPCHECK(value, (unsigned)ZSTD_fast, (unsigned)ZSTD_btultra);
394 CCtxParams->cParams.strategy = (ZSTD_strategy)value;
395 return (size_t)CCtxParams->cParams.strategy;
396
397 case ZSTD_p_contentSizeFlag :
398 /* Content size written in frame header _when known_ (default:1) */
399 DEBUGLOG(4, "set content size flag = %u", (value>0));
400 CCtxParams->fParams.contentSizeFlag = value > 0;
401 return CCtxParams->fParams.contentSizeFlag;
402
403 case ZSTD_p_checksumFlag :
404 /* A 32-bits content checksum will be calculated and written at end of frame (default:0) */
405 CCtxParams->fParams.checksumFlag = value > 0;
406 return CCtxParams->fParams.checksumFlag;
407
408 case ZSTD_p_dictIDFlag : /* When applicable, dictionary's dictID is provided in frame header (default:1) */
409 DEBUGLOG(4, "set dictIDFlag = %u", (value>0));
410 CCtxParams->fParams.noDictIDFlag = !value;
411 return !CCtxParams->fParams.noDictIDFlag;
412
413 case ZSTD_p_forceMaxWindow :
414 CCtxParams->forceWindow = (value > 0);
415 return CCtxParams->forceWindow;
416
417 case ZSTD_p_forceAttachDict : {
418 const ZSTD_dictAttachPref_e pref = (ZSTD_dictAttachPref_e)value;
419 CLAMPCHECK(pref, ZSTD_dictDefaultAttach, ZSTD_dictForceCopy);
420 CCtxParams->attachDictPref = pref;
421 return CCtxParams->attachDictPref;
422 }
423
424 case ZSTD_p_nbWorkers :
425 #ifndef ZSTD_MULTITHREAD
426 if (value>0) return ERROR(parameter_unsupported);
427 return 0;
428 #else
429 return ZSTDMT_CCtxParam_setNbWorkers(CCtxParams, value);
430 #endif
431
432 case ZSTD_p_jobSize :
433 #ifndef ZSTD_MULTITHREAD
434 return ERROR(parameter_unsupported);
435 #else
436 return ZSTDMT_CCtxParam_setMTCtxParameter(CCtxParams, ZSTDMT_p_jobSize, value);
437 #endif
438
439 case ZSTD_p_overlapSizeLog :
440 #ifndef ZSTD_MULTITHREAD
441 return ERROR(parameter_unsupported);
442 #else
443 return ZSTDMT_CCtxParam_setMTCtxParameter(CCtxParams, ZSTDMT_p_overlapSectionLog, value);
444 #endif
445
446 case ZSTD_p_rsyncable :
447 #ifndef ZSTD_MULTITHREAD
448 return ERROR(parameter_unsupported);
449 #else
450 return ZSTDMT_CCtxParam_setMTCtxParameter(CCtxParams, ZSTDMT_p_rsyncable, value);
451 #endif
452
453 case ZSTD_p_enableLongDistanceMatching :
454 CCtxParams->ldmParams.enableLdm = (value>0);
455 return CCtxParams->ldmParams.enableLdm;
456
457 case ZSTD_p_ldmHashLog :
458 if (value>0) /* 0 ==> auto */
459 CLAMPCHECK(value, ZSTD_HASHLOG_MIN, ZSTD_HASHLOG_MAX);
460 CCtxParams->ldmParams.hashLog = value;
461 return CCtxParams->ldmParams.hashLog;
462
463 case ZSTD_p_ldmMinMatch :
464 if (value>0) /* 0 ==> default */
465 CLAMPCHECK(value, ZSTD_LDM_MINMATCH_MIN, ZSTD_LDM_MINMATCH_MAX);
466 CCtxParams->ldmParams.minMatchLength = value;
467 return CCtxParams->ldmParams.minMatchLength;
468
469 case ZSTD_p_ldmBucketSizeLog :
470 if (value > ZSTD_LDM_BUCKETSIZELOG_MAX)
471 return ERROR(parameter_outOfBound);
472 CCtxParams->ldmParams.bucketSizeLog = value;
473 return CCtxParams->ldmParams.bucketSizeLog;
474
475 case ZSTD_p_ldmHashEveryLog :
476 if (value > ZSTD_WINDOWLOG_MAX - ZSTD_HASHLOG_MIN)
477 return ERROR(parameter_outOfBound);
478 CCtxParams->ldmParams.hashEveryLog = value;
479 return CCtxParams->ldmParams.hashEveryLog;
480
481 default: return ERROR(parameter_unsupported);
482 }
483 }
484
ZSTD_CCtx_getParameter(ZSTD_CCtx * cctx,ZSTD_cParameter param,unsigned * value)485 size_t ZSTD_CCtx_getParameter(ZSTD_CCtx* cctx, ZSTD_cParameter param, unsigned* value)
486 {
487 return ZSTD_CCtxParam_getParameter(&cctx->requestedParams, param, value);
488 }
489
ZSTD_CCtxParam_getParameter(ZSTD_CCtx_params * CCtxParams,ZSTD_cParameter param,unsigned * value)490 size_t ZSTD_CCtxParam_getParameter(
491 ZSTD_CCtx_params* CCtxParams, ZSTD_cParameter param, unsigned* value)
492 {
493 switch(param)
494 {
495 case ZSTD_p_format :
496 *value = CCtxParams->format;
497 break;
498 case ZSTD_p_compressionLevel :
499 *value = CCtxParams->compressionLevel;
500 break;
501 case ZSTD_p_windowLog :
502 *value = CCtxParams->cParams.windowLog;
503 break;
504 case ZSTD_p_hashLog :
505 *value = CCtxParams->cParams.hashLog;
506 break;
507 case ZSTD_p_chainLog :
508 *value = CCtxParams->cParams.chainLog;
509 break;
510 case ZSTD_p_searchLog :
511 *value = CCtxParams->cParams.searchLog;
512 break;
513 case ZSTD_p_minMatch :
514 *value = CCtxParams->cParams.searchLength;
515 break;
516 case ZSTD_p_targetLength :
517 *value = CCtxParams->cParams.targetLength;
518 break;
519 case ZSTD_p_compressionStrategy :
520 *value = (unsigned)CCtxParams->cParams.strategy;
521 break;
522 case ZSTD_p_contentSizeFlag :
523 *value = CCtxParams->fParams.contentSizeFlag;
524 break;
525 case ZSTD_p_checksumFlag :
526 *value = CCtxParams->fParams.checksumFlag;
527 break;
528 case ZSTD_p_dictIDFlag :
529 *value = !CCtxParams->fParams.noDictIDFlag;
530 break;
531 case ZSTD_p_forceMaxWindow :
532 *value = CCtxParams->forceWindow;
533 break;
534 case ZSTD_p_forceAttachDict :
535 *value = CCtxParams->attachDictPref;
536 break;
537 case ZSTD_p_nbWorkers :
538 #ifndef ZSTD_MULTITHREAD
539 assert(CCtxParams->nbWorkers == 0);
540 #endif
541 *value = CCtxParams->nbWorkers;
542 break;
543 case ZSTD_p_jobSize :
544 #ifndef ZSTD_MULTITHREAD
545 return ERROR(parameter_unsupported);
546 #else
547 *value = CCtxParams->jobSize;
548 break;
549 #endif
550 case ZSTD_p_overlapSizeLog :
551 #ifndef ZSTD_MULTITHREAD
552 return ERROR(parameter_unsupported);
553 #else
554 *value = CCtxParams->overlapSizeLog;
555 break;
556 #endif
557 case ZSTD_p_rsyncable :
558 #ifndef ZSTD_MULTITHREAD
559 return ERROR(parameter_unsupported);
560 #else
561 *value = CCtxParams->rsyncable;
562 break;
563 #endif
564 case ZSTD_p_enableLongDistanceMatching :
565 *value = CCtxParams->ldmParams.enableLdm;
566 break;
567 case ZSTD_p_ldmHashLog :
568 *value = CCtxParams->ldmParams.hashLog;
569 break;
570 case ZSTD_p_ldmMinMatch :
571 *value = CCtxParams->ldmParams.minMatchLength;
572 break;
573 case ZSTD_p_ldmBucketSizeLog :
574 *value = CCtxParams->ldmParams.bucketSizeLog;
575 break;
576 case ZSTD_p_ldmHashEveryLog :
577 *value = CCtxParams->ldmParams.hashEveryLog;
578 break;
579 default: return ERROR(parameter_unsupported);
580 }
581 return 0;
582 }
583
584 /** ZSTD_CCtx_setParametersUsingCCtxParams() :
585 * just applies `params` into `cctx`
586 * no action is performed, parameters are merely stored.
587 * If ZSTDMT is enabled, parameters are pushed to cctx->mtctx.
588 * This is possible even if a compression is ongoing.
589 * In which case, new parameters will be applied on the fly, starting with next compression job.
590 */
ZSTD_CCtx_setParametersUsingCCtxParams(ZSTD_CCtx * cctx,const ZSTD_CCtx_params * params)591 size_t ZSTD_CCtx_setParametersUsingCCtxParams(
592 ZSTD_CCtx* cctx, const ZSTD_CCtx_params* params)
593 {
594 DEBUGLOG(4, "ZSTD_CCtx_setParametersUsingCCtxParams");
595 if (cctx->streamStage != zcss_init) return ERROR(stage_wrong);
596 if (cctx->cdict) return ERROR(stage_wrong);
597
598 cctx->requestedParams = *params;
599 return 0;
600 }
601
ZSTD_CCtx_setPledgedSrcSize(ZSTD_CCtx * cctx,unsigned long long pledgedSrcSize)602 ZSTDLIB_API size_t ZSTD_CCtx_setPledgedSrcSize(ZSTD_CCtx* cctx, unsigned long long pledgedSrcSize)
603 {
604 DEBUGLOG(4, "ZSTD_CCtx_setPledgedSrcSize to %u bytes", (U32)pledgedSrcSize);
605 if (cctx->streamStage != zcss_init) return ERROR(stage_wrong);
606 cctx->pledgedSrcSizePlusOne = pledgedSrcSize+1;
607 return 0;
608 }
609
ZSTD_CCtx_loadDictionary_advanced(ZSTD_CCtx * cctx,const void * dict,size_t dictSize,ZSTD_dictLoadMethod_e dictLoadMethod,ZSTD_dictContentType_e dictContentType)610 size_t ZSTD_CCtx_loadDictionary_advanced(
611 ZSTD_CCtx* cctx, const void* dict, size_t dictSize,
612 ZSTD_dictLoadMethod_e dictLoadMethod, ZSTD_dictContentType_e dictContentType)
613 {
614 if (cctx->streamStage != zcss_init) return ERROR(stage_wrong);
615 if (cctx->staticSize) return ERROR(memory_allocation); /* no malloc for static CCtx */
616 DEBUGLOG(4, "ZSTD_CCtx_loadDictionary_advanced (size: %u)", (U32)dictSize);
617 ZSTD_freeCDict(cctx->cdictLocal); /* in case one already exists */
618 if (dict==NULL || dictSize==0) { /* no dictionary mode */
619 cctx->cdictLocal = NULL;
620 cctx->cdict = NULL;
621 } else {
622 ZSTD_compressionParameters const cParams =
623 ZSTD_getCParamsFromCCtxParams(&cctx->requestedParams, cctx->pledgedSrcSizePlusOne-1, dictSize);
624 cctx->cdictLocal = ZSTD_createCDict_advanced(
625 dict, dictSize,
626 dictLoadMethod, dictContentType,
627 cParams, cctx->customMem);
628 cctx->cdict = cctx->cdictLocal;
629 if (cctx->cdictLocal == NULL)
630 return ERROR(memory_allocation);
631 }
632 return 0;
633 }
634
ZSTD_CCtx_loadDictionary_byReference(ZSTD_CCtx * cctx,const void * dict,size_t dictSize)635 ZSTDLIB_API size_t ZSTD_CCtx_loadDictionary_byReference(
636 ZSTD_CCtx* cctx, const void* dict, size_t dictSize)
637 {
638 return ZSTD_CCtx_loadDictionary_advanced(
639 cctx, dict, dictSize, ZSTD_dlm_byRef, ZSTD_dct_auto);
640 }
641
ZSTD_CCtx_loadDictionary(ZSTD_CCtx * cctx,const void * dict,size_t dictSize)642 ZSTDLIB_API size_t ZSTD_CCtx_loadDictionary(ZSTD_CCtx* cctx, const void* dict, size_t dictSize)
643 {
644 return ZSTD_CCtx_loadDictionary_advanced(
645 cctx, dict, dictSize, ZSTD_dlm_byCopy, ZSTD_dct_auto);
646 }
647
648
ZSTD_CCtx_refCDict(ZSTD_CCtx * cctx,const ZSTD_CDict * cdict)649 size_t ZSTD_CCtx_refCDict(ZSTD_CCtx* cctx, const ZSTD_CDict* cdict)
650 {
651 if (cctx->streamStage != zcss_init) return ERROR(stage_wrong);
652 cctx->cdict = cdict;
653 memset(&cctx->prefixDict, 0, sizeof(cctx->prefixDict)); /* exclusive */
654 return 0;
655 }
656
ZSTD_CCtx_refPrefix(ZSTD_CCtx * cctx,const void * prefix,size_t prefixSize)657 size_t ZSTD_CCtx_refPrefix(ZSTD_CCtx* cctx, const void* prefix, size_t prefixSize)
658 {
659 return ZSTD_CCtx_refPrefix_advanced(cctx, prefix, prefixSize, ZSTD_dct_rawContent);
660 }
661
ZSTD_CCtx_refPrefix_advanced(ZSTD_CCtx * cctx,const void * prefix,size_t prefixSize,ZSTD_dictContentType_e dictContentType)662 size_t ZSTD_CCtx_refPrefix_advanced(
663 ZSTD_CCtx* cctx, const void* prefix, size_t prefixSize, ZSTD_dictContentType_e dictContentType)
664 {
665 if (cctx->streamStage != zcss_init) return ERROR(stage_wrong);
666 cctx->cdict = NULL; /* prefix discards any prior cdict */
667 cctx->prefixDict.dict = prefix;
668 cctx->prefixDict.dictSize = prefixSize;
669 cctx->prefixDict.dictContentType = dictContentType;
670 return 0;
671 }
672
673 /*! ZSTD_CCtx_reset() :
674 * Also dumps dictionary */
ZSTD_CCtx_reset(ZSTD_CCtx * cctx)675 void ZSTD_CCtx_reset(ZSTD_CCtx* cctx)
676 {
677 cctx->streamStage = zcss_init;
678 cctx->pledgedSrcSizePlusOne = 0;
679 }
680
ZSTD_CCtx_resetParameters(ZSTD_CCtx * cctx)681 size_t ZSTD_CCtx_resetParameters(ZSTD_CCtx* cctx)
682 {
683 if (cctx->streamStage != zcss_init) return ERROR(stage_wrong);
684 cctx->cdict = NULL;
685 return ZSTD_CCtxParams_reset(&cctx->requestedParams);
686 }
687
688 /** ZSTD_checkCParams() :
689 control CParam values remain within authorized range.
690 @return : 0, or an error code if one value is beyond authorized range */
ZSTD_checkCParams(ZSTD_compressionParameters cParams)691 size_t ZSTD_checkCParams(ZSTD_compressionParameters cParams)
692 {
693 CLAMPCHECK(cParams.windowLog, ZSTD_WINDOWLOG_MIN, ZSTD_WINDOWLOG_MAX);
694 CLAMPCHECK(cParams.chainLog, ZSTD_CHAINLOG_MIN, ZSTD_CHAINLOG_MAX);
695 CLAMPCHECK(cParams.hashLog, ZSTD_HASHLOG_MIN, ZSTD_HASHLOG_MAX);
696 CLAMPCHECK(cParams.searchLog, ZSTD_SEARCHLOG_MIN, ZSTD_SEARCHLOG_MAX);
697 CLAMPCHECK(cParams.searchLength, ZSTD_SEARCHLENGTH_MIN, ZSTD_SEARCHLENGTH_MAX);
698 ZSTD_STATIC_ASSERT(ZSTD_TARGETLENGTH_MIN == 0);
699 if (cParams.targetLength > ZSTD_TARGETLENGTH_MAX)
700 return ERROR(parameter_outOfBound);
701 if ((U32)(cParams.strategy) > (U32)ZSTD_btultra)
702 return ERROR(parameter_unsupported);
703 return 0;
704 }
705
706 /** ZSTD_clampCParams() :
707 * make CParam values within valid range.
708 * @return : valid CParams */
709 static ZSTD_compressionParameters
ZSTD_clampCParams(ZSTD_compressionParameters cParams)710 ZSTD_clampCParams(ZSTD_compressionParameters cParams)
711 {
712 # define CLAMP(val,min,max) { \
713 if (val<min) val=min; \
714 else if (val>max) val=max; \
715 }
716 CLAMP(cParams.windowLog, ZSTD_WINDOWLOG_MIN, ZSTD_WINDOWLOG_MAX);
717 CLAMP(cParams.chainLog, ZSTD_CHAINLOG_MIN, ZSTD_CHAINLOG_MAX);
718 CLAMP(cParams.hashLog, ZSTD_HASHLOG_MIN, ZSTD_HASHLOG_MAX);
719 CLAMP(cParams.searchLog, ZSTD_SEARCHLOG_MIN, ZSTD_SEARCHLOG_MAX);
720 CLAMP(cParams.searchLength, ZSTD_SEARCHLENGTH_MIN, ZSTD_SEARCHLENGTH_MAX);
721 ZSTD_STATIC_ASSERT(ZSTD_TARGETLENGTH_MIN == 0);
722 if (cParams.targetLength > ZSTD_TARGETLENGTH_MAX)
723 cParams.targetLength = ZSTD_TARGETLENGTH_MAX;
724 CLAMP(cParams.strategy, ZSTD_fast, ZSTD_btultra);
725 return cParams;
726 }
727
728 /** ZSTD_cycleLog() :
729 * condition for correct operation : hashLog > 1 */
ZSTD_cycleLog(U32 hashLog,ZSTD_strategy strat)730 static U32 ZSTD_cycleLog(U32 hashLog, ZSTD_strategy strat)
731 {
732 U32 const btScale = ((U32)strat >= (U32)ZSTD_btlazy2);
733 return hashLog - btScale;
734 }
735
736 /** ZSTD_adjustCParams_internal() :
737 optimize `cPar` for a given input (`srcSize` and `dictSize`).
738 mostly downsizing to reduce memory consumption and initialization latency.
739 Both `srcSize` and `dictSize` are optional (use 0 if unknown).
740 Note : cPar is assumed validated. Use ZSTD_checkCParams() to ensure this condition. */
741 static ZSTD_compressionParameters
ZSTD_adjustCParams_internal(ZSTD_compressionParameters cPar,unsigned long long srcSize,size_t dictSize)742 ZSTD_adjustCParams_internal(ZSTD_compressionParameters cPar,
743 unsigned long long srcSize,
744 size_t dictSize)
745 {
746 static const U64 minSrcSize = 513; /* (1<<9) + 1 */
747 static const U64 maxWindowResize = 1ULL << (ZSTD_WINDOWLOG_MAX-1);
748 assert(ZSTD_checkCParams(cPar)==0);
749
750 if (dictSize && (srcSize+1<2) /* srcSize unknown */ )
751 srcSize = minSrcSize; /* presumed small when there is a dictionary */
752 else if (srcSize == 0)
753 srcSize = ZSTD_CONTENTSIZE_UNKNOWN; /* 0 == unknown : presumed large */
754
755 /* resize windowLog if input is small enough, to use less memory */
756 if ( (srcSize < maxWindowResize)
757 && (dictSize < maxWindowResize) ) {
758 U32 const tSize = (U32)(srcSize + dictSize);
759 static U32 const hashSizeMin = 1 << ZSTD_HASHLOG_MIN;
760 U32 const srcLog = (tSize < hashSizeMin) ? ZSTD_HASHLOG_MIN :
761 ZSTD_highbit32(tSize-1) + 1;
762 if (cPar.windowLog > srcLog) cPar.windowLog = srcLog;
763 }
764 if (cPar.hashLog > cPar.windowLog+1) cPar.hashLog = cPar.windowLog+1;
765 { U32 const cycleLog = ZSTD_cycleLog(cPar.chainLog, cPar.strategy);
766 if (cycleLog > cPar.windowLog)
767 cPar.chainLog -= (cycleLog - cPar.windowLog);
768 }
769
770 if (cPar.windowLog < ZSTD_WINDOWLOG_ABSOLUTEMIN)
771 cPar.windowLog = ZSTD_WINDOWLOG_ABSOLUTEMIN; /* required for frame header */
772
773 return cPar;
774 }
775
776 ZSTD_compressionParameters
ZSTD_adjustCParams(ZSTD_compressionParameters cPar,unsigned long long srcSize,size_t dictSize)777 ZSTD_adjustCParams(ZSTD_compressionParameters cPar,
778 unsigned long long srcSize,
779 size_t dictSize)
780 {
781 cPar = ZSTD_clampCParams(cPar);
782 return ZSTD_adjustCParams_internal(cPar, srcSize, dictSize);
783 }
784
ZSTD_getCParamsFromCCtxParams(const ZSTD_CCtx_params * CCtxParams,U64 srcSizeHint,size_t dictSize)785 ZSTD_compressionParameters ZSTD_getCParamsFromCCtxParams(
786 const ZSTD_CCtx_params* CCtxParams, U64 srcSizeHint, size_t dictSize)
787 {
788 ZSTD_compressionParameters cParams = ZSTD_getCParams(CCtxParams->compressionLevel, srcSizeHint, dictSize);
789 if (CCtxParams->ldmParams.enableLdm) cParams.windowLog = ZSTD_LDM_DEFAULT_WINDOW_LOG;
790 if (CCtxParams->cParams.windowLog) cParams.windowLog = CCtxParams->cParams.windowLog;
791 if (CCtxParams->cParams.hashLog) cParams.hashLog = CCtxParams->cParams.hashLog;
792 if (CCtxParams->cParams.chainLog) cParams.chainLog = CCtxParams->cParams.chainLog;
793 if (CCtxParams->cParams.searchLog) cParams.searchLog = CCtxParams->cParams.searchLog;
794 if (CCtxParams->cParams.searchLength) cParams.searchLength = CCtxParams->cParams.searchLength;
795 if (CCtxParams->cParams.targetLength) cParams.targetLength = CCtxParams->cParams.targetLength;
796 if (CCtxParams->cParams.strategy) cParams.strategy = CCtxParams->cParams.strategy;
797 assert(!ZSTD_checkCParams(cParams));
798 return ZSTD_adjustCParams_internal(cParams, srcSizeHint, dictSize);
799 }
800
801 static size_t
ZSTD_sizeof_matchState(const ZSTD_compressionParameters * const cParams,const U32 forCCtx)802 ZSTD_sizeof_matchState(const ZSTD_compressionParameters* const cParams,
803 const U32 forCCtx)
804 {
805 size_t const chainSize = (cParams->strategy == ZSTD_fast) ? 0 : ((size_t)1 << cParams->chainLog);
806 size_t const hSize = ((size_t)1) << cParams->hashLog;
807 U32 const hashLog3 = (forCCtx && cParams->searchLength==3) ? MIN(ZSTD_HASHLOG3_MAX, cParams->windowLog) : 0;
808 size_t const h3Size = ((size_t)1) << hashLog3;
809 size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32);
810 size_t const optPotentialSpace = ((MaxML+1) + (MaxLL+1) + (MaxOff+1) + (1<<Litbits)) * sizeof(U32)
811 + (ZSTD_OPT_NUM+1) * (sizeof(ZSTD_match_t)+sizeof(ZSTD_optimal_t));
812 size_t const optSpace = (forCCtx && ((cParams->strategy == ZSTD_btopt) ||
813 (cParams->strategy == ZSTD_btultra)))
814 ? optPotentialSpace
815 : 0;
816 DEBUGLOG(4, "chainSize: %u - hSize: %u - h3Size: %u",
817 (U32)chainSize, (U32)hSize, (U32)h3Size);
818 return tableSpace + optSpace;
819 }
820
ZSTD_estimateCCtxSize_usingCCtxParams(const ZSTD_CCtx_params * params)821 size_t ZSTD_estimateCCtxSize_usingCCtxParams(const ZSTD_CCtx_params* params)
822 {
823 /* Estimate CCtx size is supported for single-threaded compression only. */
824 if (params->nbWorkers > 0) { return ERROR(GENERIC); }
825 { ZSTD_compressionParameters const cParams =
826 ZSTD_getCParamsFromCCtxParams(params, 0, 0);
827 size_t const blockSize = MIN(ZSTD_BLOCKSIZE_MAX, (size_t)1 << cParams.windowLog);
828 U32 const divider = (cParams.searchLength==3) ? 3 : 4;
829 size_t const maxNbSeq = blockSize / divider;
830 size_t const tokenSpace = WILDCOPY_OVERLENGTH + blockSize + 11*maxNbSeq;
831 size_t const entropySpace = HUF_WORKSPACE_SIZE;
832 size_t const blockStateSpace = 2 * sizeof(ZSTD_compressedBlockState_t);
833 size_t const matchStateSize = ZSTD_sizeof_matchState(&cParams, /* forCCtx */ 1);
834
835 size_t const ldmSpace = ZSTD_ldm_getTableSize(params->ldmParams);
836 size_t const ldmSeqSpace = ZSTD_ldm_getMaxNbSeq(params->ldmParams, blockSize) * sizeof(rawSeq);
837
838 size_t const neededSpace = entropySpace + blockStateSpace + tokenSpace +
839 matchStateSize + ldmSpace + ldmSeqSpace;
840
841 DEBUGLOG(5, "sizeof(ZSTD_CCtx) : %u", (U32)sizeof(ZSTD_CCtx));
842 DEBUGLOG(5, "estimate workSpace : %u", (U32)neededSpace);
843 return sizeof(ZSTD_CCtx) + neededSpace;
844 }
845 }
846
ZSTD_estimateCCtxSize_usingCParams(ZSTD_compressionParameters cParams)847 size_t ZSTD_estimateCCtxSize_usingCParams(ZSTD_compressionParameters cParams)
848 {
849 ZSTD_CCtx_params const params = ZSTD_makeCCtxParamsFromCParams(cParams);
850 return ZSTD_estimateCCtxSize_usingCCtxParams(¶ms);
851 }
852
ZSTD_estimateCCtxSize_internal(int compressionLevel)853 static size_t ZSTD_estimateCCtxSize_internal(int compressionLevel)
854 {
855 ZSTD_compressionParameters const cParams = ZSTD_getCParams(compressionLevel, 0, 0);
856 return ZSTD_estimateCCtxSize_usingCParams(cParams);
857 }
858
ZSTD_estimateCCtxSize(int compressionLevel)859 size_t ZSTD_estimateCCtxSize(int compressionLevel)
860 {
861 int level;
862 size_t memBudget = 0;
863 for (level=1; level<=compressionLevel; level++) {
864 size_t const newMB = ZSTD_estimateCCtxSize_internal(level);
865 if (newMB > memBudget) memBudget = newMB;
866 }
867 return memBudget;
868 }
869
ZSTD_estimateCStreamSize_usingCCtxParams(const ZSTD_CCtx_params * params)870 size_t ZSTD_estimateCStreamSize_usingCCtxParams(const ZSTD_CCtx_params* params)
871 {
872 if (params->nbWorkers > 0) { return ERROR(GENERIC); }
873 { size_t const CCtxSize = ZSTD_estimateCCtxSize_usingCCtxParams(params);
874 size_t const blockSize = MIN(ZSTD_BLOCKSIZE_MAX, (size_t)1 << params->cParams.windowLog);
875 size_t const inBuffSize = ((size_t)1 << params->cParams.windowLog) + blockSize;
876 size_t const outBuffSize = ZSTD_compressBound(blockSize) + 1;
877 size_t const streamingSize = inBuffSize + outBuffSize;
878
879 return CCtxSize + streamingSize;
880 }
881 }
882
ZSTD_estimateCStreamSize_usingCParams(ZSTD_compressionParameters cParams)883 size_t ZSTD_estimateCStreamSize_usingCParams(ZSTD_compressionParameters cParams)
884 {
885 ZSTD_CCtx_params const params = ZSTD_makeCCtxParamsFromCParams(cParams);
886 return ZSTD_estimateCStreamSize_usingCCtxParams(¶ms);
887 }
888
ZSTD_estimateCStreamSize_internal(int compressionLevel)889 static size_t ZSTD_estimateCStreamSize_internal(int compressionLevel)
890 {
891 ZSTD_compressionParameters const cParams = ZSTD_getCParams(compressionLevel, 0, 0);
892 return ZSTD_estimateCStreamSize_usingCParams(cParams);
893 }
894
ZSTD_estimateCStreamSize(int compressionLevel)895 size_t ZSTD_estimateCStreamSize(int compressionLevel)
896 {
897 int level;
898 size_t memBudget = 0;
899 for (level=1; level<=compressionLevel; level++) {
900 size_t const newMB = ZSTD_estimateCStreamSize_internal(level);
901 if (newMB > memBudget) memBudget = newMB;
902 }
903 return memBudget;
904 }
905
906 /* ZSTD_getFrameProgression():
907 * tells how much data has been consumed (input) and produced (output) for current frame.
908 * able to count progression inside worker threads (non-blocking mode).
909 */
ZSTD_getFrameProgression(const ZSTD_CCtx * cctx)910 ZSTD_frameProgression ZSTD_getFrameProgression(const ZSTD_CCtx* cctx)
911 {
912 #ifdef ZSTD_MULTITHREAD
913 if (cctx->appliedParams.nbWorkers > 0) {
914 return ZSTDMT_getFrameProgression(cctx->mtctx);
915 }
916 #endif
917 { ZSTD_frameProgression fp;
918 size_t const buffered = (cctx->inBuff == NULL) ? 0 :
919 cctx->inBuffPos - cctx->inToCompress;
920 if (buffered) assert(cctx->inBuffPos >= cctx->inToCompress);
921 assert(buffered <= ZSTD_BLOCKSIZE_MAX);
922 fp.ingested = cctx->consumedSrcSize + buffered;
923 fp.consumed = cctx->consumedSrcSize;
924 fp.produced = cctx->producedCSize;
925 fp.flushed = cctx->producedCSize; /* simplified; some data might still be left within streaming output buffer */
926 fp.currentJobID = 0;
927 fp.nbActiveWorkers = 0;
928 return fp;
929 } }
930
931 /*! ZSTD_toFlushNow()
932 * Only useful for multithreading scenarios currently (nbWorkers >= 1).
933 */
ZSTD_toFlushNow(ZSTD_CCtx * cctx)934 size_t ZSTD_toFlushNow(ZSTD_CCtx* cctx)
935 {
936 #ifdef ZSTD_MULTITHREAD
937 if (cctx->appliedParams.nbWorkers > 0) {
938 return ZSTDMT_toFlushNow(cctx->mtctx);
939 }
940 #endif
941 (void)cctx;
942 return 0; /* over-simplification; could also check if context is currently running in streaming mode, and in which case, report how many bytes are left to be flushed within output buffer */
943 }
944
945
946
ZSTD_equivalentCParams(ZSTD_compressionParameters cParams1,ZSTD_compressionParameters cParams2)947 static U32 ZSTD_equivalentCParams(ZSTD_compressionParameters cParams1,
948 ZSTD_compressionParameters cParams2)
949 {
950 return (cParams1.hashLog == cParams2.hashLog)
951 & (cParams1.chainLog == cParams2.chainLog)
952 & (cParams1.strategy == cParams2.strategy) /* opt parser space */
953 & ((cParams1.searchLength==3) == (cParams2.searchLength==3)); /* hashlog3 space */
954 }
955
ZSTD_assertEqualCParams(ZSTD_compressionParameters cParams1,ZSTD_compressionParameters cParams2)956 static void ZSTD_assertEqualCParams(ZSTD_compressionParameters cParams1,
957 ZSTD_compressionParameters cParams2)
958 {
959 (void)cParams1;
960 (void)cParams2;
961 assert(cParams1.windowLog == cParams2.windowLog);
962 assert(cParams1.chainLog == cParams2.chainLog);
963 assert(cParams1.hashLog == cParams2.hashLog);
964 assert(cParams1.searchLog == cParams2.searchLog);
965 assert(cParams1.searchLength == cParams2.searchLength);
966 assert(cParams1.targetLength == cParams2.targetLength);
967 assert(cParams1.strategy == cParams2.strategy);
968 }
969
970 /** The parameters are equivalent if ldm is not enabled in both sets or
971 * all the parameters are equivalent. */
ZSTD_equivalentLdmParams(ldmParams_t ldmParams1,ldmParams_t ldmParams2)972 static U32 ZSTD_equivalentLdmParams(ldmParams_t ldmParams1,
973 ldmParams_t ldmParams2)
974 {
975 return (!ldmParams1.enableLdm && !ldmParams2.enableLdm) ||
976 (ldmParams1.enableLdm == ldmParams2.enableLdm &&
977 ldmParams1.hashLog == ldmParams2.hashLog &&
978 ldmParams1.bucketSizeLog == ldmParams2.bucketSizeLog &&
979 ldmParams1.minMatchLength == ldmParams2.minMatchLength &&
980 ldmParams1.hashEveryLog == ldmParams2.hashEveryLog);
981 }
982
983 typedef enum { ZSTDb_not_buffered, ZSTDb_buffered } ZSTD_buffered_policy_e;
984
985 /* ZSTD_sufficientBuff() :
986 * check internal buffers exist for streaming if buffPol == ZSTDb_buffered .
987 * Note : they are assumed to be correctly sized if ZSTD_equivalentCParams()==1 */
ZSTD_sufficientBuff(size_t bufferSize1,size_t maxNbSeq1,size_t maxNbLit1,ZSTD_buffered_policy_e buffPol2,ZSTD_compressionParameters cParams2,U64 pledgedSrcSize)988 static U32 ZSTD_sufficientBuff(size_t bufferSize1, size_t maxNbSeq1,
989 size_t maxNbLit1,
990 ZSTD_buffered_policy_e buffPol2,
991 ZSTD_compressionParameters cParams2,
992 U64 pledgedSrcSize)
993 {
994 size_t const windowSize2 = MAX(1, (size_t)MIN(((U64)1 << cParams2.windowLog), pledgedSrcSize));
995 size_t const blockSize2 = MIN(ZSTD_BLOCKSIZE_MAX, windowSize2);
996 size_t const maxNbSeq2 = blockSize2 / ((cParams2.searchLength == 3) ? 3 : 4);
997 size_t const maxNbLit2 = blockSize2;
998 size_t const neededBufferSize2 = (buffPol2==ZSTDb_buffered) ? windowSize2 + blockSize2 : 0;
999 DEBUGLOG(4, "ZSTD_sufficientBuff: is neededBufferSize2=%u <= bufferSize1=%u",
1000 (U32)neededBufferSize2, (U32)bufferSize1);
1001 DEBUGLOG(4, "ZSTD_sufficientBuff: is maxNbSeq2=%u <= maxNbSeq1=%u",
1002 (U32)maxNbSeq2, (U32)maxNbSeq1);
1003 DEBUGLOG(4, "ZSTD_sufficientBuff: is maxNbLit2=%u <= maxNbLit1=%u",
1004 (U32)maxNbLit2, (U32)maxNbLit1);
1005 return (maxNbLit2 <= maxNbLit1)
1006 & (maxNbSeq2 <= maxNbSeq1)
1007 & (neededBufferSize2 <= bufferSize1);
1008 }
1009
1010 /** Equivalence for resetCCtx purposes */
ZSTD_equivalentParams(ZSTD_CCtx_params params1,ZSTD_CCtx_params params2,size_t buffSize1,size_t maxNbSeq1,size_t maxNbLit1,ZSTD_buffered_policy_e buffPol2,U64 pledgedSrcSize)1011 static U32 ZSTD_equivalentParams(ZSTD_CCtx_params params1,
1012 ZSTD_CCtx_params params2,
1013 size_t buffSize1,
1014 size_t maxNbSeq1, size_t maxNbLit1,
1015 ZSTD_buffered_policy_e buffPol2,
1016 U64 pledgedSrcSize)
1017 {
1018 DEBUGLOG(4, "ZSTD_equivalentParams: pledgedSrcSize=%u", (U32)pledgedSrcSize);
1019 if (!ZSTD_equivalentCParams(params1.cParams, params2.cParams)) {
1020 DEBUGLOG(4, "ZSTD_equivalentCParams() == 0");
1021 return 0;
1022 }
1023 if (!ZSTD_equivalentLdmParams(params1.ldmParams, params2.ldmParams)) {
1024 DEBUGLOG(4, "ZSTD_equivalentLdmParams() == 0");
1025 return 0;
1026 }
1027 if (!ZSTD_sufficientBuff(buffSize1, maxNbSeq1, maxNbLit1, buffPol2,
1028 params2.cParams, pledgedSrcSize)) {
1029 DEBUGLOG(4, "ZSTD_sufficientBuff() == 0");
1030 return 0;
1031 }
1032 return 1;
1033 }
1034
ZSTD_reset_compressedBlockState(ZSTD_compressedBlockState_t * bs)1035 static void ZSTD_reset_compressedBlockState(ZSTD_compressedBlockState_t* bs)
1036 {
1037 int i;
1038 for (i = 0; i < ZSTD_REP_NUM; ++i)
1039 bs->rep[i] = repStartValue[i];
1040 bs->entropy.huf.repeatMode = HUF_repeat_none;
1041 bs->entropy.fse.offcode_repeatMode = FSE_repeat_none;
1042 bs->entropy.fse.matchlength_repeatMode = FSE_repeat_none;
1043 bs->entropy.fse.litlength_repeatMode = FSE_repeat_none;
1044 }
1045
1046 /*! ZSTD_invalidateMatchState()
1047 * Invalidate all the matches in the match finder tables.
1048 * Requires nextSrc and base to be set (can be NULL).
1049 */
ZSTD_invalidateMatchState(ZSTD_matchState_t * ms)1050 static void ZSTD_invalidateMatchState(ZSTD_matchState_t* ms)
1051 {
1052 ZSTD_window_clear(&ms->window);
1053
1054 ms->nextToUpdate = ms->window.dictLimit + 1;
1055 ms->nextToUpdate3 = ms->window.dictLimit + 1;
1056 ms->loadedDictEnd = 0;
1057 ms->opt.litLengthSum = 0; /* force reset of btopt stats */
1058 ms->dictMatchState = NULL;
1059 }
1060
1061 /*! ZSTD_continueCCtx() :
1062 * reuse CCtx without reset (note : requires no dictionary) */
ZSTD_continueCCtx(ZSTD_CCtx * cctx,ZSTD_CCtx_params params,U64 pledgedSrcSize)1063 static size_t ZSTD_continueCCtx(ZSTD_CCtx* cctx, ZSTD_CCtx_params params, U64 pledgedSrcSize)
1064 {
1065 size_t const windowSize = MAX(1, (size_t)MIN(((U64)1 << params.cParams.windowLog), pledgedSrcSize));
1066 size_t const blockSize = MIN(ZSTD_BLOCKSIZE_MAX, windowSize);
1067 DEBUGLOG(4, "ZSTD_continueCCtx: re-use context in place");
1068
1069 cctx->blockSize = blockSize; /* previous block size could be different even for same windowLog, due to pledgedSrcSize */
1070 cctx->appliedParams = params;
1071 cctx->blockState.matchState.cParams = params.cParams;
1072 cctx->pledgedSrcSizePlusOne = pledgedSrcSize+1;
1073 cctx->consumedSrcSize = 0;
1074 cctx->producedCSize = 0;
1075 if (pledgedSrcSize == ZSTD_CONTENTSIZE_UNKNOWN)
1076 cctx->appliedParams.fParams.contentSizeFlag = 0;
1077 DEBUGLOG(4, "pledged content size : %u ; flag : %u",
1078 (U32)pledgedSrcSize, cctx->appliedParams.fParams.contentSizeFlag);
1079 cctx->stage = ZSTDcs_init;
1080 cctx->dictID = 0;
1081 if (params.ldmParams.enableLdm)
1082 ZSTD_window_clear(&cctx->ldmState.window);
1083 ZSTD_referenceExternalSequences(cctx, NULL, 0);
1084 ZSTD_invalidateMatchState(&cctx->blockState.matchState);
1085 ZSTD_reset_compressedBlockState(cctx->blockState.prevCBlock);
1086 XXH64_reset(&cctx->xxhState, 0);
1087 return 0;
1088 }
1089
1090 typedef enum { ZSTDcrp_continue, ZSTDcrp_noMemset } ZSTD_compResetPolicy_e;
1091
1092 static void*
ZSTD_reset_matchState(ZSTD_matchState_t * ms,void * ptr,const ZSTD_compressionParameters * cParams,ZSTD_compResetPolicy_e const crp,U32 const forCCtx)1093 ZSTD_reset_matchState(ZSTD_matchState_t* ms,
1094 void* ptr,
1095 const ZSTD_compressionParameters* cParams,
1096 ZSTD_compResetPolicy_e const crp, U32 const forCCtx)
1097 {
1098 size_t const chainSize = (cParams->strategy == ZSTD_fast) ? 0 : ((size_t)1 << cParams->chainLog);
1099 size_t const hSize = ((size_t)1) << cParams->hashLog;
1100 U32 const hashLog3 = (forCCtx && cParams->searchLength==3) ? MIN(ZSTD_HASHLOG3_MAX, cParams->windowLog) : 0;
1101 size_t const h3Size = ((size_t)1) << hashLog3;
1102 size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32);
1103
1104 assert(((size_t)ptr & 3) == 0);
1105
1106 ms->hashLog3 = hashLog3;
1107 memset(&ms->window, 0, sizeof(ms->window));
1108 ms->window.dictLimit = 1; /* start from 1, so that 1st position is valid */
1109 ms->window.lowLimit = 1; /* it ensures first and later CCtx usages compress the same */
1110 ms->window.nextSrc = ms->window.base + 1; /* see issue #1241 */
1111 ZSTD_invalidateMatchState(ms);
1112
1113 /* opt parser space */
1114 if (forCCtx && ((cParams->strategy == ZSTD_btopt) | (cParams->strategy == ZSTD_btultra))) {
1115 DEBUGLOG(4, "reserving optimal parser space");
1116 ms->opt.litFreq = (U32*)ptr;
1117 ms->opt.litLengthFreq = ms->opt.litFreq + (1<<Litbits);
1118 ms->opt.matchLengthFreq = ms->opt.litLengthFreq + (MaxLL+1);
1119 ms->opt.offCodeFreq = ms->opt.matchLengthFreq + (MaxML+1);
1120 ptr = ms->opt.offCodeFreq + (MaxOff+1);
1121 ms->opt.matchTable = (ZSTD_match_t*)ptr;
1122 ptr = ms->opt.matchTable + ZSTD_OPT_NUM+1;
1123 ms->opt.priceTable = (ZSTD_optimal_t*)ptr;
1124 ptr = ms->opt.priceTable + ZSTD_OPT_NUM+1;
1125 }
1126
1127 /* table Space */
1128 DEBUGLOG(4, "reset table : %u", crp!=ZSTDcrp_noMemset);
1129 assert(((size_t)ptr & 3) == 0); /* ensure ptr is properly aligned */
1130 if (crp!=ZSTDcrp_noMemset) memset(ptr, 0, tableSpace); /* reset tables only */
1131 ms->hashTable = (U32*)(ptr);
1132 ms->chainTable = ms->hashTable + hSize;
1133 ms->hashTable3 = ms->chainTable + chainSize;
1134 ptr = ms->hashTable3 + h3Size;
1135
1136 ms->cParams = *cParams;
1137
1138 assert(((size_t)ptr & 3) == 0);
1139 return ptr;
1140 }
1141
1142 #define ZSTD_WORKSPACETOOLARGE_FACTOR 3 /* define "workspace is too large" as this number of times larger than needed */
1143 #define ZSTD_WORKSPACETOOLARGE_MAXDURATION 128 /* when workspace is continuously too large
1144 * during at least this number of times,
1145 * context's memory usage is considered wasteful,
1146 * because it's sized to handle a worst case scenario which rarely happens.
1147 * In which case, resize it down to free some memory */
1148
1149 /*! ZSTD_resetCCtx_internal() :
1150 note : `params` are assumed fully validated at this stage */
ZSTD_resetCCtx_internal(ZSTD_CCtx * zc,ZSTD_CCtx_params params,U64 pledgedSrcSize,ZSTD_compResetPolicy_e const crp,ZSTD_buffered_policy_e const zbuff)1151 static size_t ZSTD_resetCCtx_internal(ZSTD_CCtx* zc,
1152 ZSTD_CCtx_params params,
1153 U64 pledgedSrcSize,
1154 ZSTD_compResetPolicy_e const crp,
1155 ZSTD_buffered_policy_e const zbuff)
1156 {
1157 DEBUGLOG(4, "ZSTD_resetCCtx_internal: pledgedSrcSize=%u, wlog=%u",
1158 (U32)pledgedSrcSize, params.cParams.windowLog);
1159 assert(!ZSTD_isError(ZSTD_checkCParams(params.cParams)));
1160
1161 if (crp == ZSTDcrp_continue) {
1162 if (ZSTD_equivalentParams(zc->appliedParams, params,
1163 zc->inBuffSize,
1164 zc->seqStore.maxNbSeq, zc->seqStore.maxNbLit,
1165 zbuff, pledgedSrcSize)) {
1166 DEBUGLOG(4, "ZSTD_equivalentParams()==1 -> continue mode (wLog1=%u, blockSize1=%zu)",
1167 zc->appliedParams.cParams.windowLog, zc->blockSize);
1168 zc->workSpaceOversizedDuration += (zc->workSpaceOversizedDuration > 0); /* if it was too large, it still is */
1169 if (zc->workSpaceOversizedDuration <= ZSTD_WORKSPACETOOLARGE_MAXDURATION)
1170 return ZSTD_continueCCtx(zc, params, pledgedSrcSize);
1171 } }
1172 DEBUGLOG(4, "ZSTD_equivalentParams()==0 -> reset CCtx");
1173
1174 if (params.ldmParams.enableLdm) {
1175 /* Adjust long distance matching parameters */
1176 ZSTD_ldm_adjustParameters(¶ms.ldmParams, ¶ms.cParams);
1177 assert(params.ldmParams.hashLog >= params.ldmParams.bucketSizeLog);
1178 assert(params.ldmParams.hashEveryLog < 32);
1179 zc->ldmState.hashPower = ZSTD_rollingHash_primePower(params.ldmParams.minMatchLength);
1180 }
1181
1182 { size_t const windowSize = MAX(1, (size_t)MIN(((U64)1 << params.cParams.windowLog), pledgedSrcSize));
1183 size_t const blockSize = MIN(ZSTD_BLOCKSIZE_MAX, windowSize);
1184 U32 const divider = (params.cParams.searchLength==3) ? 3 : 4;
1185 size_t const maxNbSeq = blockSize / divider;
1186 size_t const tokenSpace = WILDCOPY_OVERLENGTH + blockSize + 11*maxNbSeq;
1187 size_t const buffOutSize = (zbuff==ZSTDb_buffered) ? ZSTD_compressBound(blockSize)+1 : 0;
1188 size_t const buffInSize = (zbuff==ZSTDb_buffered) ? windowSize + blockSize : 0;
1189 size_t const matchStateSize = ZSTD_sizeof_matchState(¶ms.cParams, /* forCCtx */ 1);
1190 size_t const maxNbLdmSeq = ZSTD_ldm_getMaxNbSeq(params.ldmParams, blockSize);
1191 void* ptr; /* used to partition workSpace */
1192
1193 /* Check if workSpace is large enough, alloc a new one if needed */
1194 { size_t const entropySpace = HUF_WORKSPACE_SIZE;
1195 size_t const blockStateSpace = 2 * sizeof(ZSTD_compressedBlockState_t);
1196 size_t const bufferSpace = buffInSize + buffOutSize;
1197 size_t const ldmSpace = ZSTD_ldm_getTableSize(params.ldmParams);
1198 size_t const ldmSeqSpace = maxNbLdmSeq * sizeof(rawSeq);
1199
1200 size_t const neededSpace = entropySpace + blockStateSpace + ldmSpace +
1201 ldmSeqSpace + matchStateSize + tokenSpace +
1202 bufferSpace;
1203
1204 int const workSpaceTooSmall = zc->workSpaceSize < neededSpace;
1205 int const workSpaceTooLarge = zc->workSpaceSize > ZSTD_WORKSPACETOOLARGE_FACTOR * neededSpace;
1206 int const workSpaceWasteful = workSpaceTooLarge && (zc->workSpaceOversizedDuration > ZSTD_WORKSPACETOOLARGE_MAXDURATION);
1207 zc->workSpaceOversizedDuration = workSpaceTooLarge ? zc->workSpaceOversizedDuration+1 : 0;
1208
1209 DEBUGLOG(4, "Need %zuKB workspace, including %zuKB for match state, and %zuKB for buffers",
1210 neededSpace>>10, matchStateSize>>10, bufferSpace>>10);
1211 DEBUGLOG(4, "windowSize: %zu - blockSize: %zu", windowSize, blockSize);
1212
1213 if (workSpaceTooSmall || workSpaceWasteful) {
1214 DEBUGLOG(4, "Need to resize workSpaceSize from %zuKB to %zuKB",
1215 zc->workSpaceSize >> 10,
1216 neededSpace >> 10);
1217 /* static cctx : no resize, error out */
1218 if (zc->staticSize) return ERROR(memory_allocation);
1219
1220 zc->workSpaceSize = 0;
1221 ZSTD_free(zc->workSpace, zc->customMem);
1222 zc->workSpace = ZSTD_malloc(neededSpace, zc->customMem);
1223 if (zc->workSpace == NULL) return ERROR(memory_allocation);
1224 zc->workSpaceSize = neededSpace;
1225 zc->workSpaceOversizedDuration = 0;
1226
1227 /* Statically sized space.
1228 * entropyWorkspace never moves,
1229 * though prev/next block swap places */
1230 assert(((size_t)zc->workSpace & 3) == 0); /* ensure correct alignment */
1231 assert(zc->workSpaceSize >= 2 * sizeof(ZSTD_compressedBlockState_t));
1232 zc->blockState.prevCBlock = (ZSTD_compressedBlockState_t*)zc->workSpace;
1233 zc->blockState.nextCBlock = zc->blockState.prevCBlock + 1;
1234 ptr = zc->blockState.nextCBlock + 1;
1235 zc->entropyWorkspace = (U32*)ptr;
1236 } }
1237
1238 /* init params */
1239 zc->appliedParams = params;
1240 zc->blockState.matchState.cParams = params.cParams;
1241 zc->pledgedSrcSizePlusOne = pledgedSrcSize+1;
1242 zc->consumedSrcSize = 0;
1243 zc->producedCSize = 0;
1244 if (pledgedSrcSize == ZSTD_CONTENTSIZE_UNKNOWN)
1245 zc->appliedParams.fParams.contentSizeFlag = 0;
1246 DEBUGLOG(4, "pledged content size : %u ; flag : %u",
1247 (U32)pledgedSrcSize, zc->appliedParams.fParams.contentSizeFlag);
1248 zc->blockSize = blockSize;
1249
1250 XXH64_reset(&zc->xxhState, 0);
1251 zc->stage = ZSTDcs_init;
1252 zc->dictID = 0;
1253
1254 ZSTD_reset_compressedBlockState(zc->blockState.prevCBlock);
1255
1256 ptr = zc->entropyWorkspace + HUF_WORKSPACE_SIZE_U32;
1257
1258 /* ldm hash table */
1259 /* initialize bucketOffsets table later for pointer alignment */
1260 if (params.ldmParams.enableLdm) {
1261 size_t const ldmHSize = ((size_t)1) << params.ldmParams.hashLog;
1262 memset(ptr, 0, ldmHSize * sizeof(ldmEntry_t));
1263 assert(((size_t)ptr & 3) == 0); /* ensure ptr is properly aligned */
1264 zc->ldmState.hashTable = (ldmEntry_t*)ptr;
1265 ptr = zc->ldmState.hashTable + ldmHSize;
1266 zc->ldmSequences = (rawSeq*)ptr;
1267 ptr = zc->ldmSequences + maxNbLdmSeq;
1268 zc->maxNbLdmSequences = maxNbLdmSeq;
1269
1270 memset(&zc->ldmState.window, 0, sizeof(zc->ldmState.window));
1271 }
1272 assert(((size_t)ptr & 3) == 0); /* ensure ptr is properly aligned */
1273
1274 ptr = ZSTD_reset_matchState(&zc->blockState.matchState, ptr, ¶ms.cParams, crp, /* forCCtx */ 1);
1275
1276 /* sequences storage */
1277 zc->seqStore.maxNbSeq = maxNbSeq;
1278 zc->seqStore.sequencesStart = (seqDef*)ptr;
1279 ptr = zc->seqStore.sequencesStart + maxNbSeq;
1280 zc->seqStore.llCode = (BYTE*) ptr;
1281 zc->seqStore.mlCode = zc->seqStore.llCode + maxNbSeq;
1282 zc->seqStore.ofCode = zc->seqStore.mlCode + maxNbSeq;
1283 zc->seqStore.litStart = zc->seqStore.ofCode + maxNbSeq;
1284 /* ZSTD_wildcopy() is used to copy into the literals buffer,
1285 * so we have to oversize the buffer by WILDCOPY_OVERLENGTH bytes.
1286 */
1287 zc->seqStore.maxNbLit = blockSize;
1288 ptr = zc->seqStore.litStart + blockSize + WILDCOPY_OVERLENGTH;
1289
1290 /* ldm bucketOffsets table */
1291 if (params.ldmParams.enableLdm) {
1292 size_t const ldmBucketSize =
1293 ((size_t)1) << (params.ldmParams.hashLog -
1294 params.ldmParams.bucketSizeLog);
1295 memset(ptr, 0, ldmBucketSize);
1296 zc->ldmState.bucketOffsets = (BYTE*)ptr;
1297 ptr = zc->ldmState.bucketOffsets + ldmBucketSize;
1298 ZSTD_window_clear(&zc->ldmState.window);
1299 }
1300 ZSTD_referenceExternalSequences(zc, NULL, 0);
1301
1302 /* buffers */
1303 zc->inBuffSize = buffInSize;
1304 zc->inBuff = (char*)ptr;
1305 zc->outBuffSize = buffOutSize;
1306 zc->outBuff = zc->inBuff + buffInSize;
1307
1308 return 0;
1309 }
1310 }
1311
1312 /* ZSTD_invalidateRepCodes() :
1313 * ensures next compression will not use repcodes from previous block.
1314 * Note : only works with regular variant;
1315 * do not use with extDict variant ! */
ZSTD_invalidateRepCodes(ZSTD_CCtx * cctx)1316 void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx) {
1317 int i;
1318 for (i=0; i<ZSTD_REP_NUM; i++) cctx->blockState.prevCBlock->rep[i] = 0;
1319 assert(!ZSTD_window_hasExtDict(cctx->blockState.matchState.window));
1320 }
1321
1322 /* These are the approximate sizes for each strategy past which copying the
1323 * dictionary tables into the working context is faster than using them
1324 * in-place.
1325 */
1326 static const size_t attachDictSizeCutoffs[(unsigned)ZSTD_btultra+1] = {
1327 8 KB, /* unused */
1328 8 KB, /* ZSTD_fast */
1329 16 KB, /* ZSTD_dfast */
1330 32 KB, /* ZSTD_greedy */
1331 32 KB, /* ZSTD_lazy */
1332 32 KB, /* ZSTD_lazy2 */
1333 32 KB, /* ZSTD_btlazy2 */
1334 32 KB, /* ZSTD_btopt */
1335 8 KB /* ZSTD_btultra */
1336 };
1337
ZSTD_shouldAttachDict(const ZSTD_CDict * cdict,ZSTD_CCtx_params params,U64 pledgedSrcSize)1338 static int ZSTD_shouldAttachDict(const ZSTD_CDict* cdict,
1339 ZSTD_CCtx_params params,
1340 U64 pledgedSrcSize)
1341 {
1342 size_t cutoff = attachDictSizeCutoffs[cdict->matchState.cParams.strategy];
1343 return ( pledgedSrcSize <= cutoff
1344 || pledgedSrcSize == ZSTD_CONTENTSIZE_UNKNOWN
1345 || params.attachDictPref == ZSTD_dictForceAttach )
1346 && params.attachDictPref != ZSTD_dictForceCopy
1347 && !params.forceWindow; /* dictMatchState isn't correctly
1348 * handled in _enforceMaxDist */
1349 }
1350
ZSTD_resetCCtx_byAttachingCDict(ZSTD_CCtx * cctx,const ZSTD_CDict * cdict,ZSTD_CCtx_params params,U64 pledgedSrcSize,ZSTD_buffered_policy_e zbuff)1351 static size_t ZSTD_resetCCtx_byAttachingCDict(
1352 ZSTD_CCtx* cctx,
1353 const ZSTD_CDict* cdict,
1354 ZSTD_CCtx_params params,
1355 U64 pledgedSrcSize,
1356 ZSTD_buffered_policy_e zbuff)
1357 {
1358 {
1359 const ZSTD_compressionParameters *cdict_cParams = &cdict->matchState.cParams;
1360 unsigned const windowLog = params.cParams.windowLog;
1361 assert(windowLog != 0);
1362 /* Resize working context table params for input only, since the dict
1363 * has its own tables. */
1364 params.cParams = ZSTD_adjustCParams_internal(*cdict_cParams, pledgedSrcSize, 0);
1365 params.cParams.windowLog = windowLog;
1366 ZSTD_resetCCtx_internal(cctx, params, pledgedSrcSize,
1367 ZSTDcrp_continue, zbuff);
1368 assert(cctx->appliedParams.cParams.strategy == cdict_cParams->strategy);
1369 }
1370
1371 {
1372 const U32 cdictEnd = (U32)( cdict->matchState.window.nextSrc
1373 - cdict->matchState.window.base);
1374 const U32 cdictLen = cdictEnd - cdict->matchState.window.dictLimit;
1375 if (cdictLen == 0) {
1376 /* don't even attach dictionaries with no contents */
1377 DEBUGLOG(4, "skipping attaching empty dictionary");
1378 } else {
1379 DEBUGLOG(4, "attaching dictionary into context");
1380 cctx->blockState.matchState.dictMatchState = &cdict->matchState;
1381
1382 /* prep working match state so dict matches never have negative indices
1383 * when they are translated to the working context's index space. */
1384 if (cctx->blockState.matchState.window.dictLimit < cdictEnd) {
1385 cctx->blockState.matchState.window.nextSrc =
1386 cctx->blockState.matchState.window.base + cdictEnd;
1387 ZSTD_window_clear(&cctx->blockState.matchState.window);
1388 }
1389 cctx->blockState.matchState.loadedDictEnd = cctx->blockState.matchState.window.dictLimit;
1390 }
1391 }
1392
1393 cctx->dictID = cdict->dictID;
1394
1395 /* copy block state */
1396 memcpy(cctx->blockState.prevCBlock, &cdict->cBlockState, sizeof(cdict->cBlockState));
1397
1398 return 0;
1399 }
1400
ZSTD_resetCCtx_byCopyingCDict(ZSTD_CCtx * cctx,const ZSTD_CDict * cdict,ZSTD_CCtx_params params,U64 pledgedSrcSize,ZSTD_buffered_policy_e zbuff)1401 static size_t ZSTD_resetCCtx_byCopyingCDict(ZSTD_CCtx* cctx,
1402 const ZSTD_CDict* cdict,
1403 ZSTD_CCtx_params params,
1404 U64 pledgedSrcSize,
1405 ZSTD_buffered_policy_e zbuff)
1406 {
1407 const ZSTD_compressionParameters *cdict_cParams = &cdict->matchState.cParams;
1408
1409 DEBUGLOG(4, "copying dictionary into context");
1410
1411 { unsigned const windowLog = params.cParams.windowLog;
1412 assert(windowLog != 0);
1413 /* Copy only compression parameters related to tables. */
1414 params.cParams = *cdict_cParams;
1415 params.cParams.windowLog = windowLog;
1416 ZSTD_resetCCtx_internal(cctx, params, pledgedSrcSize,
1417 ZSTDcrp_noMemset, zbuff);
1418 assert(cctx->appliedParams.cParams.strategy == cdict_cParams->strategy);
1419 assert(cctx->appliedParams.cParams.hashLog == cdict_cParams->hashLog);
1420 assert(cctx->appliedParams.cParams.chainLog == cdict_cParams->chainLog);
1421 }
1422
1423 /* copy tables */
1424 { size_t const chainSize = (cdict_cParams->strategy == ZSTD_fast) ? 0 : ((size_t)1 << cdict_cParams->chainLog);
1425 size_t const hSize = (size_t)1 << cdict_cParams->hashLog;
1426 size_t const tableSpace = (chainSize + hSize) * sizeof(U32);
1427 assert((U32*)cctx->blockState.matchState.chainTable == (U32*)cctx->blockState.matchState.hashTable + hSize); /* chainTable must follow hashTable */
1428 assert((U32*)cctx->blockState.matchState.hashTable3 == (U32*)cctx->blockState.matchState.chainTable + chainSize);
1429 assert((U32*)cdict->matchState.chainTable == (U32*)cdict->matchState.hashTable + hSize); /* chainTable must follow hashTable */
1430 assert((U32*)cdict->matchState.hashTable3 == (U32*)cdict->matchState.chainTable + chainSize);
1431 memcpy(cctx->blockState.matchState.hashTable, cdict->matchState.hashTable, tableSpace); /* presumes all tables follow each other */
1432 }
1433
1434 /* Zero the hashTable3, since the cdict never fills it */
1435 { size_t const h3Size = (size_t)1 << cctx->blockState.matchState.hashLog3;
1436 assert(cdict->matchState.hashLog3 == 0);
1437 memset(cctx->blockState.matchState.hashTable3, 0, h3Size * sizeof(U32));
1438 }
1439
1440 /* copy dictionary offsets */
1441 { ZSTD_matchState_t const* srcMatchState = &cdict->matchState;
1442 ZSTD_matchState_t* dstMatchState = &cctx->blockState.matchState;
1443 dstMatchState->window = srcMatchState->window;
1444 dstMatchState->nextToUpdate = srcMatchState->nextToUpdate;
1445 dstMatchState->nextToUpdate3= srcMatchState->nextToUpdate3;
1446 dstMatchState->loadedDictEnd= srcMatchState->loadedDictEnd;
1447 }
1448
1449 cctx->dictID = cdict->dictID;
1450
1451 /* copy block state */
1452 memcpy(cctx->blockState.prevCBlock, &cdict->cBlockState, sizeof(cdict->cBlockState));
1453
1454 return 0;
1455 }
1456
1457 /* We have a choice between copying the dictionary context into the working
1458 * context, or referencing the dictionary context from the working context
1459 * in-place. We decide here which strategy to use. */
ZSTD_resetCCtx_usingCDict(ZSTD_CCtx * cctx,const ZSTD_CDict * cdict,ZSTD_CCtx_params params,U64 pledgedSrcSize,ZSTD_buffered_policy_e zbuff)1460 static size_t ZSTD_resetCCtx_usingCDict(ZSTD_CCtx* cctx,
1461 const ZSTD_CDict* cdict,
1462 ZSTD_CCtx_params params,
1463 U64 pledgedSrcSize,
1464 ZSTD_buffered_policy_e zbuff)
1465 {
1466
1467 DEBUGLOG(4, "ZSTD_resetCCtx_usingCDict (pledgedSrcSize=%u)", (U32)pledgedSrcSize);
1468
1469 if (ZSTD_shouldAttachDict(cdict, params, pledgedSrcSize)) {
1470 return ZSTD_resetCCtx_byAttachingCDict(
1471 cctx, cdict, params, pledgedSrcSize, zbuff);
1472 } else {
1473 return ZSTD_resetCCtx_byCopyingCDict(
1474 cctx, cdict, params, pledgedSrcSize, zbuff);
1475 }
1476 }
1477
1478 /*! ZSTD_copyCCtx_internal() :
1479 * Duplicate an existing context `srcCCtx` into another one `dstCCtx`.
1480 * Only works during stage ZSTDcs_init (i.e. after creation, but before first call to ZSTD_compressContinue()).
1481 * The "context", in this case, refers to the hash and chain tables,
1482 * entropy tables, and dictionary references.
1483 * `windowLog` value is enforced if != 0, otherwise value is copied from srcCCtx.
1484 * @return : 0, or an error code */
ZSTD_copyCCtx_internal(ZSTD_CCtx * dstCCtx,const ZSTD_CCtx * srcCCtx,ZSTD_frameParameters fParams,U64 pledgedSrcSize,ZSTD_buffered_policy_e zbuff)1485 static size_t ZSTD_copyCCtx_internal(ZSTD_CCtx* dstCCtx,
1486 const ZSTD_CCtx* srcCCtx,
1487 ZSTD_frameParameters fParams,
1488 U64 pledgedSrcSize,
1489 ZSTD_buffered_policy_e zbuff)
1490 {
1491 DEBUGLOG(5, "ZSTD_copyCCtx_internal");
1492 if (srcCCtx->stage!=ZSTDcs_init) return ERROR(stage_wrong);
1493
1494 memcpy(&dstCCtx->customMem, &srcCCtx->customMem, sizeof(ZSTD_customMem));
1495 { ZSTD_CCtx_params params = dstCCtx->requestedParams;
1496 /* Copy only compression parameters related to tables. */
1497 params.cParams = srcCCtx->appliedParams.cParams;
1498 params.fParams = fParams;
1499 ZSTD_resetCCtx_internal(dstCCtx, params, pledgedSrcSize,
1500 ZSTDcrp_noMemset, zbuff);
1501 assert(dstCCtx->appliedParams.cParams.windowLog == srcCCtx->appliedParams.cParams.windowLog);
1502 assert(dstCCtx->appliedParams.cParams.strategy == srcCCtx->appliedParams.cParams.strategy);
1503 assert(dstCCtx->appliedParams.cParams.hashLog == srcCCtx->appliedParams.cParams.hashLog);
1504 assert(dstCCtx->appliedParams.cParams.chainLog == srcCCtx->appliedParams.cParams.chainLog);
1505 assert(dstCCtx->blockState.matchState.hashLog3 == srcCCtx->blockState.matchState.hashLog3);
1506 }
1507
1508 /* copy tables */
1509 { size_t const chainSize = (srcCCtx->appliedParams.cParams.strategy == ZSTD_fast) ? 0 : ((size_t)1 << srcCCtx->appliedParams.cParams.chainLog);
1510 size_t const hSize = (size_t)1 << srcCCtx->appliedParams.cParams.hashLog;
1511 size_t const h3Size = (size_t)1 << srcCCtx->blockState.matchState.hashLog3;
1512 size_t const tableSpace = (chainSize + hSize + h3Size) * sizeof(U32);
1513 assert((U32*)dstCCtx->blockState.matchState.chainTable == (U32*)dstCCtx->blockState.matchState.hashTable + hSize); /* chainTable must follow hashTable */
1514 assert((U32*)dstCCtx->blockState.matchState.hashTable3 == (U32*)dstCCtx->blockState.matchState.chainTable + chainSize);
1515 memcpy(dstCCtx->blockState.matchState.hashTable, srcCCtx->blockState.matchState.hashTable, tableSpace); /* presumes all tables follow each other */
1516 }
1517
1518 /* copy dictionary offsets */
1519 {
1520 const ZSTD_matchState_t* srcMatchState = &srcCCtx->blockState.matchState;
1521 ZSTD_matchState_t* dstMatchState = &dstCCtx->blockState.matchState;
1522 dstMatchState->window = srcMatchState->window;
1523 dstMatchState->nextToUpdate = srcMatchState->nextToUpdate;
1524 dstMatchState->nextToUpdate3= srcMatchState->nextToUpdate3;
1525 dstMatchState->loadedDictEnd= srcMatchState->loadedDictEnd;
1526 }
1527 dstCCtx->dictID = srcCCtx->dictID;
1528
1529 /* copy block state */
1530 memcpy(dstCCtx->blockState.prevCBlock, srcCCtx->blockState.prevCBlock, sizeof(*srcCCtx->blockState.prevCBlock));
1531
1532 return 0;
1533 }
1534
1535 /*! ZSTD_copyCCtx() :
1536 * Duplicate an existing context `srcCCtx` into another one `dstCCtx`.
1537 * Only works during stage ZSTDcs_init (i.e. after creation, but before first call to ZSTD_compressContinue()).
1538 * pledgedSrcSize==0 means "unknown".
1539 * @return : 0, or an error code */
ZSTD_copyCCtx(ZSTD_CCtx * dstCCtx,const ZSTD_CCtx * srcCCtx,unsigned long long pledgedSrcSize)1540 size_t ZSTD_copyCCtx(ZSTD_CCtx* dstCCtx, const ZSTD_CCtx* srcCCtx, unsigned long long pledgedSrcSize)
1541 {
1542 ZSTD_frameParameters fParams = { 1 /*content*/, 0 /*checksum*/, 0 /*noDictID*/ };
1543 ZSTD_buffered_policy_e const zbuff = (ZSTD_buffered_policy_e)(srcCCtx->inBuffSize>0);
1544 ZSTD_STATIC_ASSERT((U32)ZSTDb_buffered==1);
1545 if (pledgedSrcSize==0) pledgedSrcSize = ZSTD_CONTENTSIZE_UNKNOWN;
1546 fParams.contentSizeFlag = (pledgedSrcSize != ZSTD_CONTENTSIZE_UNKNOWN);
1547
1548 return ZSTD_copyCCtx_internal(dstCCtx, srcCCtx,
1549 fParams, pledgedSrcSize,
1550 zbuff);
1551 }
1552
1553
1554 #define ZSTD_ROWSIZE 16
1555 /*! ZSTD_reduceTable() :
1556 * reduce table indexes by `reducerValue`, or squash to zero.
1557 * PreserveMark preserves "unsorted mark" for btlazy2 strategy.
1558 * It must be set to a clear 0/1 value, to remove branch during inlining.
1559 * Presume table size is a multiple of ZSTD_ROWSIZE
1560 * to help auto-vectorization */
1561 FORCE_INLINE_TEMPLATE void
ZSTD_reduceTable_internal(U32 * const table,U32 const size,U32 const reducerValue,int const preserveMark)1562 ZSTD_reduceTable_internal (U32* const table, U32 const size, U32 const reducerValue, int const preserveMark)
1563 {
1564 int const nbRows = (int)size / ZSTD_ROWSIZE;
1565 int cellNb = 0;
1566 int rowNb;
1567 assert((size & (ZSTD_ROWSIZE-1)) == 0); /* multiple of ZSTD_ROWSIZE */
1568 assert(size < (1U<<31)); /* can be casted to int */
1569 for (rowNb=0 ; rowNb < nbRows ; rowNb++) {
1570 int column;
1571 for (column=0; column<ZSTD_ROWSIZE; column++) {
1572 if (preserveMark) {
1573 U32 const adder = (table[cellNb] == ZSTD_DUBT_UNSORTED_MARK) ? reducerValue : 0;
1574 table[cellNb] += adder;
1575 }
1576 if (table[cellNb] < reducerValue) table[cellNb] = 0;
1577 else table[cellNb] -= reducerValue;
1578 cellNb++;
1579 } }
1580 }
1581
ZSTD_reduceTable(U32 * const table,U32 const size,U32 const reducerValue)1582 static void ZSTD_reduceTable(U32* const table, U32 const size, U32 const reducerValue)
1583 {
1584 ZSTD_reduceTable_internal(table, size, reducerValue, 0);
1585 }
1586
ZSTD_reduceTable_btlazy2(U32 * const table,U32 const size,U32 const reducerValue)1587 static void ZSTD_reduceTable_btlazy2(U32* const table, U32 const size, U32 const reducerValue)
1588 {
1589 ZSTD_reduceTable_internal(table, size, reducerValue, 1);
1590 }
1591
1592 /*! ZSTD_reduceIndex() :
1593 * rescale all indexes to avoid future overflow (indexes are U32) */
ZSTD_reduceIndex(ZSTD_CCtx * zc,const U32 reducerValue)1594 static void ZSTD_reduceIndex (ZSTD_CCtx* zc, const U32 reducerValue)
1595 {
1596 ZSTD_matchState_t* const ms = &zc->blockState.matchState;
1597 { U32 const hSize = (U32)1 << zc->appliedParams.cParams.hashLog;
1598 ZSTD_reduceTable(ms->hashTable, hSize, reducerValue);
1599 }
1600
1601 if (zc->appliedParams.cParams.strategy != ZSTD_fast) {
1602 U32 const chainSize = (U32)1 << zc->appliedParams.cParams.chainLog;
1603 if (zc->appliedParams.cParams.strategy == ZSTD_btlazy2)
1604 ZSTD_reduceTable_btlazy2(ms->chainTable, chainSize, reducerValue);
1605 else
1606 ZSTD_reduceTable(ms->chainTable, chainSize, reducerValue);
1607 }
1608
1609 if (ms->hashLog3) {
1610 U32 const h3Size = (U32)1 << ms->hashLog3;
1611 ZSTD_reduceTable(ms->hashTable3, h3Size, reducerValue);
1612 }
1613 }
1614
1615
1616 /*-*******************************************************
1617 * Block entropic compression
1618 *********************************************************/
1619
1620 /* See doc/zstd_compression_format.md for detailed format description */
1621
ZSTD_noCompressBlock(void * dst,size_t dstCapacity,const void * src,size_t srcSize,U32 lastBlock)1622 static size_t ZSTD_noCompressBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize, U32 lastBlock)
1623 {
1624 U32 const cBlockHeader24 = lastBlock + (((U32)bt_raw)<<1) + (U32)(srcSize << 3);
1625 if (srcSize + ZSTD_blockHeaderSize > dstCapacity) return ERROR(dstSize_tooSmall);
1626 MEM_writeLE24(dst, cBlockHeader24);
1627 memcpy((BYTE*)dst + ZSTD_blockHeaderSize, src, srcSize);
1628 return ZSTD_blockHeaderSize + srcSize;
1629 }
1630
ZSTD_noCompressLiterals(void * dst,size_t dstCapacity,const void * src,size_t srcSize)1631 static size_t ZSTD_noCompressLiterals (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
1632 {
1633 BYTE* const ostart = (BYTE* const)dst;
1634 U32 const flSize = 1 + (srcSize>31) + (srcSize>4095);
1635
1636 if (srcSize + flSize > dstCapacity) return ERROR(dstSize_tooSmall);
1637
1638 switch(flSize)
1639 {
1640 case 1: /* 2 - 1 - 5 */
1641 ostart[0] = (BYTE)((U32)set_basic + (srcSize<<3));
1642 break;
1643 case 2: /* 2 - 2 - 12 */
1644 MEM_writeLE16(ostart, (U16)((U32)set_basic + (1<<2) + (srcSize<<4)));
1645 break;
1646 case 3: /* 2 - 2 - 20 */
1647 MEM_writeLE32(ostart, (U32)((U32)set_basic + (3<<2) + (srcSize<<4)));
1648 break;
1649 default: /* not necessary : flSize is {1,2,3} */
1650 assert(0);
1651 }
1652
1653 memcpy(ostart + flSize, src, srcSize);
1654 return srcSize + flSize;
1655 }
1656
ZSTD_compressRleLiteralsBlock(void * dst,size_t dstCapacity,const void * src,size_t srcSize)1657 static size_t ZSTD_compressRleLiteralsBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
1658 {
1659 BYTE* const ostart = (BYTE* const)dst;
1660 U32 const flSize = 1 + (srcSize>31) + (srcSize>4095);
1661
1662 (void)dstCapacity; /* dstCapacity already guaranteed to be >=4, hence large enough */
1663
1664 switch(flSize)
1665 {
1666 case 1: /* 2 - 1 - 5 */
1667 ostart[0] = (BYTE)((U32)set_rle + (srcSize<<3));
1668 break;
1669 case 2: /* 2 - 2 - 12 */
1670 MEM_writeLE16(ostart, (U16)((U32)set_rle + (1<<2) + (srcSize<<4)));
1671 break;
1672 case 3: /* 2 - 2 - 20 */
1673 MEM_writeLE32(ostart, (U32)((U32)set_rle + (3<<2) + (srcSize<<4)));
1674 break;
1675 default: /* not necessary : flSize is {1,2,3} */
1676 assert(0);
1677 }
1678
1679 ostart[flSize] = *(const BYTE*)src;
1680 return flSize+1;
1681 }
1682
1683
1684 /* ZSTD_minGain() :
1685 * minimum compression required
1686 * to generate a compress block or a compressed literals section.
1687 * note : use same formula for both situations */
ZSTD_minGain(size_t srcSize,ZSTD_strategy strat)1688 static size_t ZSTD_minGain(size_t srcSize, ZSTD_strategy strat)
1689 {
1690 U32 const minlog = (strat==ZSTD_btultra) ? 7 : 6;
1691 return (srcSize >> minlog) + 2;
1692 }
1693
ZSTD_compressLiterals(ZSTD_hufCTables_t const * prevHuf,ZSTD_hufCTables_t * nextHuf,ZSTD_strategy strategy,int disableLiteralCompression,void * dst,size_t dstCapacity,const void * src,size_t srcSize,void * workspace,size_t wkspSize,const int bmi2)1694 static size_t ZSTD_compressLiterals (ZSTD_hufCTables_t const* prevHuf,
1695 ZSTD_hufCTables_t* nextHuf,
1696 ZSTD_strategy strategy, int disableLiteralCompression,
1697 void* dst, size_t dstCapacity,
1698 const void* src, size_t srcSize,
1699 void* workspace, size_t wkspSize,
1700 const int bmi2)
1701 {
1702 size_t const minGain = ZSTD_minGain(srcSize, strategy);
1703 size_t const lhSize = 3 + (srcSize >= 1 KB) + (srcSize >= 16 KB);
1704 BYTE* const ostart = (BYTE*)dst;
1705 U32 singleStream = srcSize < 256;
1706 symbolEncodingType_e hType = set_compressed;
1707 size_t cLitSize;
1708
1709 DEBUGLOG(5,"ZSTD_compressLiterals (disableLiteralCompression=%i)",
1710 disableLiteralCompression);
1711
1712 /* Prepare nextEntropy assuming reusing the existing table */
1713 memcpy(nextHuf, prevHuf, sizeof(*prevHuf));
1714
1715 if (disableLiteralCompression)
1716 return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
1717
1718 /* small ? don't even attempt compression (speed opt) */
1719 # define COMPRESS_LITERALS_SIZE_MIN 63
1720 { size_t const minLitSize = (prevHuf->repeatMode == HUF_repeat_valid) ? 6 : COMPRESS_LITERALS_SIZE_MIN;
1721 if (srcSize <= minLitSize) return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
1722 }
1723
1724 if (dstCapacity < lhSize+1) return ERROR(dstSize_tooSmall); /* not enough space for compression */
1725 { HUF_repeat repeat = prevHuf->repeatMode;
1726 int const preferRepeat = strategy < ZSTD_lazy ? srcSize <= 1024 : 0;
1727 if (repeat == HUF_repeat_valid && lhSize == 3) singleStream = 1;
1728 cLitSize = singleStream ? HUF_compress1X_repeat(ostart+lhSize, dstCapacity-lhSize, src, srcSize, 255, 11,
1729 workspace, wkspSize, (HUF_CElt*)nextHuf->CTable, &repeat, preferRepeat, bmi2)
1730 : HUF_compress4X_repeat(ostart+lhSize, dstCapacity-lhSize, src, srcSize, 255, 11,
1731 workspace, wkspSize, (HUF_CElt*)nextHuf->CTable, &repeat, preferRepeat, bmi2);
1732 if (repeat != HUF_repeat_none) {
1733 /* reused the existing table */
1734 hType = set_repeat;
1735 }
1736 }
1737
1738 if ((cLitSize==0) | (cLitSize >= srcSize - minGain) | ERR_isError(cLitSize)) {
1739 memcpy(nextHuf, prevHuf, sizeof(*prevHuf));
1740 return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
1741 }
1742 if (cLitSize==1) {
1743 memcpy(nextHuf, prevHuf, sizeof(*prevHuf));
1744 return ZSTD_compressRleLiteralsBlock(dst, dstCapacity, src, srcSize);
1745 }
1746
1747 if (hType == set_compressed) {
1748 /* using a newly constructed table */
1749 nextHuf->repeatMode = HUF_repeat_check;
1750 }
1751
1752 /* Build header */
1753 switch(lhSize)
1754 {
1755 case 3: /* 2 - 2 - 10 - 10 */
1756 { U32 const lhc = hType + ((!singleStream) << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<14);
1757 MEM_writeLE24(ostart, lhc);
1758 break;
1759 }
1760 case 4: /* 2 - 2 - 14 - 14 */
1761 { U32 const lhc = hType + (2 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<18);
1762 MEM_writeLE32(ostart, lhc);
1763 break;
1764 }
1765 case 5: /* 2 - 2 - 18 - 18 */
1766 { U32 const lhc = hType + (3 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<22);
1767 MEM_writeLE32(ostart, lhc);
1768 ostart[4] = (BYTE)(cLitSize >> 10);
1769 break;
1770 }
1771 default: /* not possible : lhSize is {3,4,5} */
1772 assert(0);
1773 }
1774 return lhSize+cLitSize;
1775 }
1776
1777
ZSTD_seqToCodes(const seqStore_t * seqStorePtr)1778 void ZSTD_seqToCodes(const seqStore_t* seqStorePtr)
1779 {
1780 const seqDef* const sequences = seqStorePtr->sequencesStart;
1781 BYTE* const llCodeTable = seqStorePtr->llCode;
1782 BYTE* const ofCodeTable = seqStorePtr->ofCode;
1783 BYTE* const mlCodeTable = seqStorePtr->mlCode;
1784 U32 const nbSeq = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
1785 U32 u;
1786 assert(nbSeq <= seqStorePtr->maxNbSeq);
1787 for (u=0; u<nbSeq; u++) {
1788 U32 const llv = sequences[u].litLength;
1789 U32 const mlv = sequences[u].matchLength;
1790 llCodeTable[u] = (BYTE)ZSTD_LLcode(llv);
1791 ofCodeTable[u] = (BYTE)ZSTD_highbit32(sequences[u].offset);
1792 mlCodeTable[u] = (BYTE)ZSTD_MLcode(mlv);
1793 }
1794 if (seqStorePtr->longLengthID==1)
1795 llCodeTable[seqStorePtr->longLengthPos] = MaxLL;
1796 if (seqStorePtr->longLengthID==2)
1797 mlCodeTable[seqStorePtr->longLengthPos] = MaxML;
1798 }
1799
1800
1801 /**
1802 * -log2(x / 256) lookup table for x in [0, 256).
1803 * If x == 0: Return 0
1804 * Else: Return floor(-log2(x / 256) * 256)
1805 */
1806 static unsigned const kInverseProbabiltyLog256[256] = {
1807 0, 2048, 1792, 1642, 1536, 1453, 1386, 1329, 1280, 1236, 1197, 1162,
1808 1130, 1100, 1073, 1047, 1024, 1001, 980, 960, 941, 923, 906, 889,
1809 874, 859, 844, 830, 817, 804, 791, 779, 768, 756, 745, 734,
1810 724, 714, 704, 694, 685, 676, 667, 658, 650, 642, 633, 626,
1811 618, 610, 603, 595, 588, 581, 574, 567, 561, 554, 548, 542,
1812 535, 529, 523, 517, 512, 506, 500, 495, 489, 484, 478, 473,
1813 468, 463, 458, 453, 448, 443, 438, 434, 429, 424, 420, 415,
1814 411, 407, 402, 398, 394, 390, 386, 382, 377, 373, 370, 366,
1815 362, 358, 354, 350, 347, 343, 339, 336, 332, 329, 325, 322,
1816 318, 315, 311, 308, 305, 302, 298, 295, 292, 289, 286, 282,
1817 279, 276, 273, 270, 267, 264, 261, 258, 256, 253, 250, 247,
1818 244, 241, 239, 236, 233, 230, 228, 225, 222, 220, 217, 215,
1819 212, 209, 207, 204, 202, 199, 197, 194, 192, 190, 187, 185,
1820 182, 180, 178, 175, 173, 171, 168, 166, 164, 162, 159, 157,
1821 155, 153, 151, 149, 146, 144, 142, 140, 138, 136, 134, 132,
1822 130, 128, 126, 123, 121, 119, 117, 115, 114, 112, 110, 108,
1823 106, 104, 102, 100, 98, 96, 94, 93, 91, 89, 87, 85,
1824 83, 82, 80, 78, 76, 74, 73, 71, 69, 67, 66, 64,
1825 62, 61, 59, 57, 55, 54, 52, 50, 49, 47, 46, 44,
1826 42, 41, 39, 37, 36, 34, 33, 31, 30, 28, 26, 25,
1827 23, 22, 20, 19, 17, 16, 14, 13, 11, 10, 8, 7,
1828 5, 4, 2, 1,
1829 };
1830
1831
1832 /**
1833 * Returns the cost in bits of encoding the distribution described by count
1834 * using the entropy bound.
1835 */
ZSTD_entropyCost(unsigned const * count,unsigned const max,size_t const total)1836 static size_t ZSTD_entropyCost(unsigned const* count, unsigned const max, size_t const total)
1837 {
1838 unsigned cost = 0;
1839 unsigned s;
1840 for (s = 0; s <= max; ++s) {
1841 unsigned norm = (unsigned)((256 * count[s]) / total);
1842 if (count[s] != 0 && norm == 0)
1843 norm = 1;
1844 assert(count[s] < total);
1845 cost += count[s] * kInverseProbabiltyLog256[norm];
1846 }
1847 return cost >> 8;
1848 }
1849
1850
1851 /**
1852 * Returns the cost in bits of encoding the distribution in count using the
1853 * table described by norm. The max symbol support by norm is assumed >= max.
1854 * norm must be valid for every symbol with non-zero probability in count.
1855 */
ZSTD_crossEntropyCost(short const * norm,unsigned accuracyLog,unsigned const * count,unsigned const max)1856 static size_t ZSTD_crossEntropyCost(short const* norm, unsigned accuracyLog,
1857 unsigned const* count, unsigned const max)
1858 {
1859 unsigned const shift = 8 - accuracyLog;
1860 size_t cost = 0;
1861 unsigned s;
1862 assert(accuracyLog <= 8);
1863 for (s = 0; s <= max; ++s) {
1864 unsigned const normAcc = norm[s] != -1 ? norm[s] : 1;
1865 unsigned const norm256 = normAcc << shift;
1866 assert(norm256 > 0);
1867 assert(norm256 < 256);
1868 cost += count[s] * kInverseProbabiltyLog256[norm256];
1869 }
1870 return cost >> 8;
1871 }
1872
1873
ZSTD_getFSEMaxSymbolValue(FSE_CTable const * ctable)1874 static unsigned ZSTD_getFSEMaxSymbolValue(FSE_CTable const* ctable) {
1875 void const* ptr = ctable;
1876 U16 const* u16ptr = (U16 const*)ptr;
1877 U32 const maxSymbolValue = MEM_read16(u16ptr + 1);
1878 return maxSymbolValue;
1879 }
1880
1881
1882 /**
1883 * Returns the cost in bits of encoding the distribution in count using ctable.
1884 * Returns an error if ctable cannot represent all the symbols in count.
1885 */
ZSTD_fseBitCost(FSE_CTable const * ctable,unsigned const * count,unsigned const max)1886 static size_t ZSTD_fseBitCost(
1887 FSE_CTable const* ctable,
1888 unsigned const* count,
1889 unsigned const max)
1890 {
1891 unsigned const kAccuracyLog = 8;
1892 size_t cost = 0;
1893 unsigned s;
1894 FSE_CState_t cstate;
1895 FSE_initCState(&cstate, ctable);
1896 if (ZSTD_getFSEMaxSymbolValue(ctable) < max) {
1897 DEBUGLOG(5, "Repeat FSE_CTable has maxSymbolValue %u < %u",
1898 ZSTD_getFSEMaxSymbolValue(ctable), max);
1899 return ERROR(GENERIC);
1900 }
1901 for (s = 0; s <= max; ++s) {
1902 unsigned const tableLog = cstate.stateLog;
1903 unsigned const badCost = (tableLog + 1) << kAccuracyLog;
1904 unsigned const bitCost = FSE_bitCost(cstate.symbolTT, tableLog, s, kAccuracyLog);
1905 if (count[s] == 0)
1906 continue;
1907 if (bitCost >= badCost) {
1908 DEBUGLOG(5, "Repeat FSE_CTable has Prob[%u] == 0", s);
1909 return ERROR(GENERIC);
1910 }
1911 cost += count[s] * bitCost;
1912 }
1913 return cost >> kAccuracyLog;
1914 }
1915
1916 /**
1917 * Returns the cost in bytes of encoding the normalized count header.
1918 * Returns an error if any of the helper functions return an error.
1919 */
ZSTD_NCountCost(unsigned const * count,unsigned const max,size_t const nbSeq,unsigned const FSELog)1920 static size_t ZSTD_NCountCost(unsigned const* count, unsigned const max,
1921 size_t const nbSeq, unsigned const FSELog)
1922 {
1923 BYTE wksp[FSE_NCOUNTBOUND];
1924 S16 norm[MaxSeq + 1];
1925 const U32 tableLog = FSE_optimalTableLog(FSELog, nbSeq, max);
1926 CHECK_F(FSE_normalizeCount(norm, tableLog, count, nbSeq, max));
1927 return FSE_writeNCount(wksp, sizeof(wksp), norm, max, tableLog);
1928 }
1929
1930
1931 typedef enum {
1932 ZSTD_defaultDisallowed = 0,
1933 ZSTD_defaultAllowed = 1
1934 } ZSTD_defaultPolicy_e;
1935
1936 MEM_STATIC symbolEncodingType_e
ZSTD_selectEncodingType(FSE_repeat * repeatMode,unsigned const * count,unsigned const max,size_t const mostFrequent,size_t nbSeq,unsigned const FSELog,FSE_CTable const * prevCTable,short const * defaultNorm,U32 defaultNormLog,ZSTD_defaultPolicy_e const isDefaultAllowed,ZSTD_strategy const strategy)1937 ZSTD_selectEncodingType(
1938 FSE_repeat* repeatMode, unsigned const* count, unsigned const max,
1939 size_t const mostFrequent, size_t nbSeq, unsigned const FSELog,
1940 FSE_CTable const* prevCTable,
1941 short const* defaultNorm, U32 defaultNormLog,
1942 ZSTD_defaultPolicy_e const isDefaultAllowed,
1943 ZSTD_strategy const strategy)
1944 {
1945 ZSTD_STATIC_ASSERT(ZSTD_defaultDisallowed == 0 && ZSTD_defaultAllowed != 0);
1946 if (mostFrequent == nbSeq) {
1947 *repeatMode = FSE_repeat_none;
1948 if (isDefaultAllowed && nbSeq <= 2) {
1949 /* Prefer set_basic over set_rle when there are 2 or less symbols,
1950 * since RLE uses 1 byte, but set_basic uses 5-6 bits per symbol.
1951 * If basic encoding isn't possible, always choose RLE.
1952 */
1953 DEBUGLOG(5, "Selected set_basic");
1954 return set_basic;
1955 }
1956 DEBUGLOG(5, "Selected set_rle");
1957 return set_rle;
1958 }
1959 if (strategy < ZSTD_lazy) {
1960 if (isDefaultAllowed) {
1961 size_t const staticFse_nbSeq_max = 1000;
1962 size_t const mult = 10 - strategy;
1963 size_t const baseLog = 3;
1964 size_t const dynamicFse_nbSeq_min = (((size_t)1 << defaultNormLog) * mult) >> baseLog; /* 28-36 for offset, 56-72 for lengths */
1965 assert(defaultNormLog >= 5 && defaultNormLog <= 6); /* xx_DEFAULTNORMLOG */
1966 assert(mult <= 9 && mult >= 7);
1967 if ( (*repeatMode == FSE_repeat_valid)
1968 && (nbSeq < staticFse_nbSeq_max) ) {
1969 DEBUGLOG(5, "Selected set_repeat");
1970 return set_repeat;
1971 }
1972 if ( (nbSeq < dynamicFse_nbSeq_min)
1973 || (mostFrequent < (nbSeq >> (defaultNormLog-1))) ) {
1974 DEBUGLOG(5, "Selected set_basic");
1975 /* The format allows default tables to be repeated, but it isn't useful.
1976 * When using simple heuristics to select encoding type, we don't want
1977 * to confuse these tables with dictionaries. When running more careful
1978 * analysis, we don't need to waste time checking both repeating tables
1979 * and default tables.
1980 */
1981 *repeatMode = FSE_repeat_none;
1982 return set_basic;
1983 }
1984 }
1985 } else {
1986 size_t const basicCost = isDefaultAllowed ? ZSTD_crossEntropyCost(defaultNorm, defaultNormLog, count, max) : ERROR(GENERIC);
1987 size_t const repeatCost = *repeatMode != FSE_repeat_none ? ZSTD_fseBitCost(prevCTable, count, max) : ERROR(GENERIC);
1988 size_t const NCountCost = ZSTD_NCountCost(count, max, nbSeq, FSELog);
1989 size_t const compressedCost = (NCountCost << 3) + ZSTD_entropyCost(count, max, nbSeq);
1990
1991 if (isDefaultAllowed) {
1992 assert(!ZSTD_isError(basicCost));
1993 assert(!(*repeatMode == FSE_repeat_valid && ZSTD_isError(repeatCost)));
1994 }
1995 assert(!ZSTD_isError(NCountCost));
1996 assert(compressedCost < ERROR(maxCode));
1997 DEBUGLOG(5, "Estimated bit costs: basic=%u\trepeat=%u\tcompressed=%u",
1998 (U32)basicCost, (U32)repeatCost, (U32)compressedCost);
1999 if (basicCost <= repeatCost && basicCost <= compressedCost) {
2000 DEBUGLOG(5, "Selected set_basic");
2001 assert(isDefaultAllowed);
2002 *repeatMode = FSE_repeat_none;
2003 return set_basic;
2004 }
2005 if (repeatCost <= compressedCost) {
2006 DEBUGLOG(5, "Selected set_repeat");
2007 assert(!ZSTD_isError(repeatCost));
2008 return set_repeat;
2009 }
2010 assert(compressedCost < basicCost && compressedCost < repeatCost);
2011 }
2012 DEBUGLOG(5, "Selected set_compressed");
2013 *repeatMode = FSE_repeat_check;
2014 return set_compressed;
2015 }
2016
2017 MEM_STATIC size_t
ZSTD_buildCTable(void * dst,size_t dstCapacity,FSE_CTable * nextCTable,U32 FSELog,symbolEncodingType_e type,U32 * count,U32 max,const BYTE * codeTable,size_t nbSeq,const S16 * defaultNorm,U32 defaultNormLog,U32 defaultMax,const FSE_CTable * prevCTable,size_t prevCTableSize,void * workspace,size_t workspaceSize)2018 ZSTD_buildCTable(void* dst, size_t dstCapacity,
2019 FSE_CTable* nextCTable, U32 FSELog, symbolEncodingType_e type,
2020 U32* count, U32 max,
2021 const BYTE* codeTable, size_t nbSeq,
2022 const S16* defaultNorm, U32 defaultNormLog, U32 defaultMax,
2023 const FSE_CTable* prevCTable, size_t prevCTableSize,
2024 void* workspace, size_t workspaceSize)
2025 {
2026 BYTE* op = (BYTE*)dst;
2027 const BYTE* const oend = op + dstCapacity;
2028 DEBUGLOG(6, "ZSTD_buildCTable (dstCapacity=%u)", (unsigned)dstCapacity);
2029
2030 switch (type) {
2031 case set_rle:
2032 CHECK_F(FSE_buildCTable_rle(nextCTable, (BYTE)max));
2033 if (dstCapacity==0) return ERROR(dstSize_tooSmall);
2034 *op = codeTable[0];
2035 return 1;
2036 case set_repeat:
2037 memcpy(nextCTable, prevCTable, prevCTableSize);
2038 return 0;
2039 case set_basic:
2040 CHECK_F(FSE_buildCTable_wksp(nextCTable, defaultNorm, defaultMax, defaultNormLog, workspace, workspaceSize)); /* note : could be pre-calculated */
2041 return 0;
2042 case set_compressed: {
2043 S16 norm[MaxSeq + 1];
2044 size_t nbSeq_1 = nbSeq;
2045 const U32 tableLog = FSE_optimalTableLog(FSELog, nbSeq, max);
2046 if (count[codeTable[nbSeq-1]] > 1) {
2047 count[codeTable[nbSeq-1]]--;
2048 nbSeq_1--;
2049 }
2050 assert(nbSeq_1 > 1);
2051 CHECK_F(FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max));
2052 { size_t const NCountSize = FSE_writeNCount(op, oend - op, norm, max, tableLog); /* overflow protected */
2053 if (FSE_isError(NCountSize)) return NCountSize;
2054 CHECK_F(FSE_buildCTable_wksp(nextCTable, norm, max, tableLog, workspace, workspaceSize));
2055 return NCountSize;
2056 }
2057 }
2058 default: return assert(0), ERROR(GENERIC);
2059 }
2060 }
2061
2062 FORCE_INLINE_TEMPLATE size_t
ZSTD_encodeSequences_body(void * dst,size_t dstCapacity,FSE_CTable const * CTable_MatchLength,BYTE const * mlCodeTable,FSE_CTable const * CTable_OffsetBits,BYTE const * ofCodeTable,FSE_CTable const * CTable_LitLength,BYTE const * llCodeTable,seqDef const * sequences,size_t nbSeq,int longOffsets)2063 ZSTD_encodeSequences_body(
2064 void* dst, size_t dstCapacity,
2065 FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,
2066 FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,
2067 FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,
2068 seqDef const* sequences, size_t nbSeq, int longOffsets)
2069 {
2070 BIT_CStream_t blockStream;
2071 FSE_CState_t stateMatchLength;
2072 FSE_CState_t stateOffsetBits;
2073 FSE_CState_t stateLitLength;
2074
2075 CHECK_E(BIT_initCStream(&blockStream, dst, dstCapacity), dstSize_tooSmall); /* not enough space remaining */
2076 DEBUGLOG(6, "available space for bitstream : %i (dstCapacity=%u)",
2077 (int)(blockStream.endPtr - blockStream.startPtr),
2078 (unsigned)dstCapacity);
2079
2080 /* first symbols */
2081 FSE_initCState2(&stateMatchLength, CTable_MatchLength, mlCodeTable[nbSeq-1]);
2082 FSE_initCState2(&stateOffsetBits, CTable_OffsetBits, ofCodeTable[nbSeq-1]);
2083 FSE_initCState2(&stateLitLength, CTable_LitLength, llCodeTable[nbSeq-1]);
2084 BIT_addBits(&blockStream, sequences[nbSeq-1].litLength, LL_bits[llCodeTable[nbSeq-1]]);
2085 if (MEM_32bits()) BIT_flushBits(&blockStream);
2086 BIT_addBits(&blockStream, sequences[nbSeq-1].matchLength, ML_bits[mlCodeTable[nbSeq-1]]);
2087 if (MEM_32bits()) BIT_flushBits(&blockStream);
2088 if (longOffsets) {
2089 U32 const ofBits = ofCodeTable[nbSeq-1];
2090 int const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);
2091 if (extraBits) {
2092 BIT_addBits(&blockStream, sequences[nbSeq-1].offset, extraBits);
2093 BIT_flushBits(&blockStream);
2094 }
2095 BIT_addBits(&blockStream, sequences[nbSeq-1].offset >> extraBits,
2096 ofBits - extraBits);
2097 } else {
2098 BIT_addBits(&blockStream, sequences[nbSeq-1].offset, ofCodeTable[nbSeq-1]);
2099 }
2100 BIT_flushBits(&blockStream);
2101
2102 { size_t n;
2103 for (n=nbSeq-2 ; n<nbSeq ; n--) { /* intentional underflow */
2104 BYTE const llCode = llCodeTable[n];
2105 BYTE const ofCode = ofCodeTable[n];
2106 BYTE const mlCode = mlCodeTable[n];
2107 U32 const llBits = LL_bits[llCode];
2108 U32 const ofBits = ofCode;
2109 U32 const mlBits = ML_bits[mlCode];
2110 DEBUGLOG(6, "encoding: litlen:%2u - matchlen:%2u - offCode:%7u",
2111 sequences[n].litLength,
2112 sequences[n].matchLength + MINMATCH,
2113 sequences[n].offset);
2114 /* 32b*/ /* 64b*/
2115 /* (7)*/ /* (7)*/
2116 FSE_encodeSymbol(&blockStream, &stateOffsetBits, ofCode); /* 15 */ /* 15 */
2117 FSE_encodeSymbol(&blockStream, &stateMatchLength, mlCode); /* 24 */ /* 24 */
2118 if (MEM_32bits()) BIT_flushBits(&blockStream); /* (7)*/
2119 FSE_encodeSymbol(&blockStream, &stateLitLength, llCode); /* 16 */ /* 33 */
2120 if (MEM_32bits() || (ofBits+mlBits+llBits >= 64-7-(LLFSELog+MLFSELog+OffFSELog)))
2121 BIT_flushBits(&blockStream); /* (7)*/
2122 BIT_addBits(&blockStream, sequences[n].litLength, llBits);
2123 if (MEM_32bits() && ((llBits+mlBits)>24)) BIT_flushBits(&blockStream);
2124 BIT_addBits(&blockStream, sequences[n].matchLength, mlBits);
2125 if (MEM_32bits() || (ofBits+mlBits+llBits > 56)) BIT_flushBits(&blockStream);
2126 if (longOffsets) {
2127 int const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);
2128 if (extraBits) {
2129 BIT_addBits(&blockStream, sequences[n].offset, extraBits);
2130 BIT_flushBits(&blockStream); /* (7)*/
2131 }
2132 BIT_addBits(&blockStream, sequences[n].offset >> extraBits,
2133 ofBits - extraBits); /* 31 */
2134 } else {
2135 BIT_addBits(&blockStream, sequences[n].offset, ofBits); /* 31 */
2136 }
2137 BIT_flushBits(&blockStream); /* (7)*/
2138 DEBUGLOG(7, "remaining space : %i", (int)(blockStream.endPtr - blockStream.ptr));
2139 } }
2140
2141 DEBUGLOG(6, "ZSTD_encodeSequences: flushing ML state with %u bits", stateMatchLength.stateLog);
2142 FSE_flushCState(&blockStream, &stateMatchLength);
2143 DEBUGLOG(6, "ZSTD_encodeSequences: flushing Off state with %u bits", stateOffsetBits.stateLog);
2144 FSE_flushCState(&blockStream, &stateOffsetBits);
2145 DEBUGLOG(6, "ZSTD_encodeSequences: flushing LL state with %u bits", stateLitLength.stateLog);
2146 FSE_flushCState(&blockStream, &stateLitLength);
2147
2148 { size_t const streamSize = BIT_closeCStream(&blockStream);
2149 if (streamSize==0) return ERROR(dstSize_tooSmall); /* not enough space */
2150 return streamSize;
2151 }
2152 }
2153
2154 static size_t
ZSTD_encodeSequences_default(void * dst,size_t dstCapacity,FSE_CTable const * CTable_MatchLength,BYTE const * mlCodeTable,FSE_CTable const * CTable_OffsetBits,BYTE const * ofCodeTable,FSE_CTable const * CTable_LitLength,BYTE const * llCodeTable,seqDef const * sequences,size_t nbSeq,int longOffsets)2155 ZSTD_encodeSequences_default(
2156 void* dst, size_t dstCapacity,
2157 FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,
2158 FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,
2159 FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,
2160 seqDef const* sequences, size_t nbSeq, int longOffsets)
2161 {
2162 return ZSTD_encodeSequences_body(dst, dstCapacity,
2163 CTable_MatchLength, mlCodeTable,
2164 CTable_OffsetBits, ofCodeTable,
2165 CTable_LitLength, llCodeTable,
2166 sequences, nbSeq, longOffsets);
2167 }
2168
2169
2170 #if DYNAMIC_BMI2
2171
2172 static TARGET_ATTRIBUTE("bmi2") size_t
ZSTD_encodeSequences_bmi2(void * dst,size_t dstCapacity,FSE_CTable const * CTable_MatchLength,BYTE const * mlCodeTable,FSE_CTable const * CTable_OffsetBits,BYTE const * ofCodeTable,FSE_CTable const * CTable_LitLength,BYTE const * llCodeTable,seqDef const * sequences,size_t nbSeq,int longOffsets)2173 ZSTD_encodeSequences_bmi2(
2174 void* dst, size_t dstCapacity,
2175 FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,
2176 FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,
2177 FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,
2178 seqDef const* sequences, size_t nbSeq, int longOffsets)
2179 {
2180 return ZSTD_encodeSequences_body(dst, dstCapacity,
2181 CTable_MatchLength, mlCodeTable,
2182 CTable_OffsetBits, ofCodeTable,
2183 CTable_LitLength, llCodeTable,
2184 sequences, nbSeq, longOffsets);
2185 }
2186
2187 #endif
2188
ZSTD_encodeSequences(void * dst,size_t dstCapacity,FSE_CTable const * CTable_MatchLength,BYTE const * mlCodeTable,FSE_CTable const * CTable_OffsetBits,BYTE const * ofCodeTable,FSE_CTable const * CTable_LitLength,BYTE const * llCodeTable,seqDef const * sequences,size_t nbSeq,int longOffsets,int bmi2)2189 static size_t ZSTD_encodeSequences(
2190 void* dst, size_t dstCapacity,
2191 FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,
2192 FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,
2193 FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,
2194 seqDef const* sequences, size_t nbSeq, int longOffsets, int bmi2)
2195 {
2196 DEBUGLOG(5, "ZSTD_encodeSequences: dstCapacity = %u", (unsigned)dstCapacity);
2197 #if DYNAMIC_BMI2
2198 if (bmi2) {
2199 return ZSTD_encodeSequences_bmi2(dst, dstCapacity,
2200 CTable_MatchLength, mlCodeTable,
2201 CTable_OffsetBits, ofCodeTable,
2202 CTable_LitLength, llCodeTable,
2203 sequences, nbSeq, longOffsets);
2204 }
2205 #endif
2206 (void)bmi2;
2207 return ZSTD_encodeSequences_default(dst, dstCapacity,
2208 CTable_MatchLength, mlCodeTable,
2209 CTable_OffsetBits, ofCodeTable,
2210 CTable_LitLength, llCodeTable,
2211 sequences, nbSeq, longOffsets);
2212 }
2213
2214 MEM_STATIC size_t
ZSTD_compressSequences_internal(seqStore_t * seqStorePtr,ZSTD_entropyCTables_t const * prevEntropy,ZSTD_entropyCTables_t * nextEntropy,ZSTD_CCtx_params const * cctxParams,void * dst,size_t dstCapacity,void * workspace,size_t wkspSize,const int bmi2)2215 ZSTD_compressSequences_internal(seqStore_t* seqStorePtr,
2216 ZSTD_entropyCTables_t const* prevEntropy,
2217 ZSTD_entropyCTables_t* nextEntropy,
2218 ZSTD_CCtx_params const* cctxParams,
2219 void* dst, size_t dstCapacity,
2220 void* workspace, size_t wkspSize,
2221 const int bmi2)
2222 {
2223 const int longOffsets = cctxParams->cParams.windowLog > STREAM_ACCUMULATOR_MIN;
2224 ZSTD_strategy const strategy = cctxParams->cParams.strategy;
2225 U32 count[MaxSeq+1];
2226 FSE_CTable* CTable_LitLength = nextEntropy->fse.litlengthCTable;
2227 FSE_CTable* CTable_OffsetBits = nextEntropy->fse.offcodeCTable;
2228 FSE_CTable* CTable_MatchLength = nextEntropy->fse.matchlengthCTable;
2229 U32 LLtype, Offtype, MLtype; /* compressed, raw or rle */
2230 const seqDef* const sequences = seqStorePtr->sequencesStart;
2231 const BYTE* const ofCodeTable = seqStorePtr->ofCode;
2232 const BYTE* const llCodeTable = seqStorePtr->llCode;
2233 const BYTE* const mlCodeTable = seqStorePtr->mlCode;
2234 BYTE* const ostart = (BYTE*)dst;
2235 BYTE* const oend = ostart + dstCapacity;
2236 BYTE* op = ostart;
2237 size_t const nbSeq = seqStorePtr->sequences - seqStorePtr->sequencesStart;
2238 BYTE* seqHead;
2239 BYTE* lastNCount = NULL;
2240
2241 ZSTD_STATIC_ASSERT(HUF_WORKSPACE_SIZE >= (1<<MAX(MLFSELog,LLFSELog)));
2242
2243 /* Compress literals */
2244 { const BYTE* const literals = seqStorePtr->litStart;
2245 size_t const litSize = seqStorePtr->lit - literals;
2246 int const disableLiteralCompression = (cctxParams->cParams.strategy == ZSTD_fast) && (cctxParams->cParams.targetLength > 0);
2247 size_t const cSize = ZSTD_compressLiterals(
2248 &prevEntropy->huf, &nextEntropy->huf,
2249 cctxParams->cParams.strategy, disableLiteralCompression,
2250 op, dstCapacity,
2251 literals, litSize,
2252 workspace, wkspSize,
2253 bmi2);
2254 if (ZSTD_isError(cSize))
2255 return cSize;
2256 assert(cSize <= dstCapacity);
2257 op += cSize;
2258 }
2259
2260 /* Sequences Header */
2261 if ((oend-op) < 3 /*max nbSeq Size*/ + 1 /*seqHead*/) return ERROR(dstSize_tooSmall);
2262 if (nbSeq < 0x7F)
2263 *op++ = (BYTE)nbSeq;
2264 else if (nbSeq < LONGNBSEQ)
2265 op[0] = (BYTE)((nbSeq>>8) + 0x80), op[1] = (BYTE)nbSeq, op+=2;
2266 else
2267 op[0]=0xFF, MEM_writeLE16(op+1, (U16)(nbSeq - LONGNBSEQ)), op+=3;
2268 if (nbSeq==0) {
2269 /* Copy the old tables over as if we repeated them */
2270 memcpy(&nextEntropy->fse, &prevEntropy->fse, sizeof(prevEntropy->fse));
2271 return op - ostart;
2272 }
2273
2274 /* seqHead : flags for FSE encoding type */
2275 seqHead = op++;
2276
2277 /* convert length/distances into codes */
2278 ZSTD_seqToCodes(seqStorePtr);
2279 /* build CTable for Literal Lengths */
2280 { U32 max = MaxLL;
2281 size_t const mostFrequent = HIST_countFast_wksp(count, &max, llCodeTable, nbSeq, workspace, wkspSize); /* can't fail */
2282 DEBUGLOG(5, "Building LL table");
2283 nextEntropy->fse.litlength_repeatMode = prevEntropy->fse.litlength_repeatMode;
2284 LLtype = ZSTD_selectEncodingType(&nextEntropy->fse.litlength_repeatMode, count, max, mostFrequent, nbSeq, LLFSELog, prevEntropy->fse.litlengthCTable, LL_defaultNorm, LL_defaultNormLog, ZSTD_defaultAllowed, strategy);
2285 assert(set_basic < set_compressed && set_rle < set_compressed);
2286 assert(!(LLtype < set_compressed && nextEntropy->fse.litlength_repeatMode != FSE_repeat_none)); /* We don't copy tables */
2287 { size_t const countSize = ZSTD_buildCTable(op, oend - op, CTable_LitLength, LLFSELog, (symbolEncodingType_e)LLtype,
2288 count, max, llCodeTable, nbSeq, LL_defaultNorm, LL_defaultNormLog, MaxLL,
2289 prevEntropy->fse.litlengthCTable, sizeof(prevEntropy->fse.litlengthCTable),
2290 workspace, wkspSize);
2291 if (ZSTD_isError(countSize)) return countSize;
2292 if (LLtype == set_compressed)
2293 lastNCount = op;
2294 op += countSize;
2295 } }
2296 /* build CTable for Offsets */
2297 { U32 max = MaxOff;
2298 size_t const mostFrequent = HIST_countFast_wksp(count, &max, ofCodeTable, nbSeq, workspace, wkspSize); /* can't fail */
2299 /* We can only use the basic table if max <= DefaultMaxOff, otherwise the offsets are too large */
2300 ZSTD_defaultPolicy_e const defaultPolicy = (max <= DefaultMaxOff) ? ZSTD_defaultAllowed : ZSTD_defaultDisallowed;
2301 DEBUGLOG(5, "Building OF table");
2302 nextEntropy->fse.offcode_repeatMode = prevEntropy->fse.offcode_repeatMode;
2303 Offtype = ZSTD_selectEncodingType(&nextEntropy->fse.offcode_repeatMode, count, max, mostFrequent, nbSeq, OffFSELog, prevEntropy->fse.offcodeCTable, OF_defaultNorm, OF_defaultNormLog, defaultPolicy, strategy);
2304 assert(!(Offtype < set_compressed && nextEntropy->fse.offcode_repeatMode != FSE_repeat_none)); /* We don't copy tables */
2305 { size_t const countSize = ZSTD_buildCTable(op, oend - op, CTable_OffsetBits, OffFSELog, (symbolEncodingType_e)Offtype,
2306 count, max, ofCodeTable, nbSeq, OF_defaultNorm, OF_defaultNormLog, DefaultMaxOff,
2307 prevEntropy->fse.offcodeCTable, sizeof(prevEntropy->fse.offcodeCTable),
2308 workspace, wkspSize);
2309 if (ZSTD_isError(countSize)) return countSize;
2310 if (Offtype == set_compressed)
2311 lastNCount = op;
2312 op += countSize;
2313 } }
2314 /* build CTable for MatchLengths */
2315 { U32 max = MaxML;
2316 size_t const mostFrequent = HIST_countFast_wksp(count, &max, mlCodeTable, nbSeq, workspace, wkspSize); /* can't fail */
2317 DEBUGLOG(5, "Building ML table (remaining space : %i)", (int)(oend-op));
2318 nextEntropy->fse.matchlength_repeatMode = prevEntropy->fse.matchlength_repeatMode;
2319 MLtype = ZSTD_selectEncodingType(&nextEntropy->fse.matchlength_repeatMode, count, max, mostFrequent, nbSeq, MLFSELog, prevEntropy->fse.matchlengthCTable, ML_defaultNorm, ML_defaultNormLog, ZSTD_defaultAllowed, strategy);
2320 assert(!(MLtype < set_compressed && nextEntropy->fse.matchlength_repeatMode != FSE_repeat_none)); /* We don't copy tables */
2321 { size_t const countSize = ZSTD_buildCTable(op, oend - op, CTable_MatchLength, MLFSELog, (symbolEncodingType_e)MLtype,
2322 count, max, mlCodeTable, nbSeq, ML_defaultNorm, ML_defaultNormLog, MaxML,
2323 prevEntropy->fse.matchlengthCTable, sizeof(prevEntropy->fse.matchlengthCTable),
2324 workspace, wkspSize);
2325 if (ZSTD_isError(countSize)) return countSize;
2326 if (MLtype == set_compressed)
2327 lastNCount = op;
2328 op += countSize;
2329 } }
2330
2331 *seqHead = (BYTE)((LLtype<<6) + (Offtype<<4) + (MLtype<<2));
2332
2333 { size_t const bitstreamSize = ZSTD_encodeSequences(
2334 op, oend - op,
2335 CTable_MatchLength, mlCodeTable,
2336 CTable_OffsetBits, ofCodeTable,
2337 CTable_LitLength, llCodeTable,
2338 sequences, nbSeq,
2339 longOffsets, bmi2);
2340 if (ZSTD_isError(bitstreamSize)) return bitstreamSize;
2341 op += bitstreamSize;
2342 /* zstd versions <= 1.3.4 mistakenly report corruption when
2343 * FSE_readNCount() recieves a buffer < 4 bytes.
2344 * Fixed by https://github.com/facebook/zstd/pull/1146.
2345 * This can happen when the last set_compressed table present is 2
2346 * bytes and the bitstream is only one byte.
2347 * In this exceedingly rare case, we will simply emit an uncompressed
2348 * block, since it isn't worth optimizing.
2349 */
2350 if (lastNCount && (op - lastNCount) < 4) {
2351 /* NCountSize >= 2 && bitstreamSize > 0 ==> lastCountSize == 3 */
2352 assert(op - lastNCount == 3);
2353 DEBUGLOG(5, "Avoiding bug in zstd decoder in versions <= 1.3.4 by "
2354 "emitting an uncompressed block.");
2355 return 0;
2356 }
2357 }
2358
2359 return op - ostart;
2360 }
2361
2362 MEM_STATIC size_t
ZSTD_compressSequences(seqStore_t * seqStorePtr,const ZSTD_entropyCTables_t * prevEntropy,ZSTD_entropyCTables_t * nextEntropy,const ZSTD_CCtx_params * cctxParams,void * dst,size_t dstCapacity,size_t srcSize,void * workspace,size_t wkspSize,int bmi2)2363 ZSTD_compressSequences(seqStore_t* seqStorePtr,
2364 const ZSTD_entropyCTables_t* prevEntropy,
2365 ZSTD_entropyCTables_t* nextEntropy,
2366 const ZSTD_CCtx_params* cctxParams,
2367 void* dst, size_t dstCapacity,
2368 size_t srcSize,
2369 void* workspace, size_t wkspSize,
2370 int bmi2)
2371 {
2372 size_t const cSize = ZSTD_compressSequences_internal(
2373 seqStorePtr, prevEntropy, nextEntropy, cctxParams,
2374 dst, dstCapacity,
2375 workspace, wkspSize, bmi2);
2376 if (cSize == 0) return 0;
2377 /* When srcSize <= dstCapacity, there is enough space to write a raw uncompressed block.
2378 * Since we ran out of space, block must be not compressible, so fall back to raw uncompressed block.
2379 */
2380 if ((cSize == ERROR(dstSize_tooSmall)) & (srcSize <= dstCapacity))
2381 return 0; /* block not compressed */
2382 if (ZSTD_isError(cSize)) return cSize;
2383
2384 /* Check compressibility */
2385 { size_t const maxCSize = srcSize - ZSTD_minGain(srcSize, cctxParams->cParams.strategy);
2386 if (cSize >= maxCSize) return 0; /* block not compressed */
2387 }
2388
2389 return cSize;
2390 }
2391
2392 /* ZSTD_selectBlockCompressor() :
2393 * Not static, but internal use only (used by long distance matcher)
2394 * assumption : strat is a valid strategy */
ZSTD_selectBlockCompressor(ZSTD_strategy strat,ZSTD_dictMode_e dictMode)2395 ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, ZSTD_dictMode_e dictMode)
2396 {
2397 static const ZSTD_blockCompressor blockCompressor[3][(unsigned)ZSTD_btultra+1] = {
2398 { ZSTD_compressBlock_fast /* default for 0 */,
2399 ZSTD_compressBlock_fast,
2400 ZSTD_compressBlock_doubleFast,
2401 ZSTD_compressBlock_greedy,
2402 ZSTD_compressBlock_lazy,
2403 ZSTD_compressBlock_lazy2,
2404 ZSTD_compressBlock_btlazy2,
2405 ZSTD_compressBlock_btopt,
2406 ZSTD_compressBlock_btultra },
2407 { ZSTD_compressBlock_fast_extDict /* default for 0 */,
2408 ZSTD_compressBlock_fast_extDict,
2409 ZSTD_compressBlock_doubleFast_extDict,
2410 ZSTD_compressBlock_greedy_extDict,
2411 ZSTD_compressBlock_lazy_extDict,
2412 ZSTD_compressBlock_lazy2_extDict,
2413 ZSTD_compressBlock_btlazy2_extDict,
2414 ZSTD_compressBlock_btopt_extDict,
2415 ZSTD_compressBlock_btultra_extDict },
2416 { ZSTD_compressBlock_fast_dictMatchState /* default for 0 */,
2417 ZSTD_compressBlock_fast_dictMatchState,
2418 ZSTD_compressBlock_doubleFast_dictMatchState,
2419 ZSTD_compressBlock_greedy_dictMatchState,
2420 ZSTD_compressBlock_lazy_dictMatchState,
2421 ZSTD_compressBlock_lazy2_dictMatchState,
2422 ZSTD_compressBlock_btlazy2_dictMatchState,
2423 ZSTD_compressBlock_btopt_dictMatchState,
2424 ZSTD_compressBlock_btultra_dictMatchState }
2425 };
2426 ZSTD_blockCompressor selectedCompressor;
2427 ZSTD_STATIC_ASSERT((unsigned)ZSTD_fast == 1);
2428
2429 assert((U32)strat >= (U32)ZSTD_fast);
2430 assert((U32)strat <= (U32)ZSTD_btultra);
2431 selectedCompressor = blockCompressor[(int)dictMode][(U32)strat];
2432 assert(selectedCompressor != NULL);
2433 return selectedCompressor;
2434 }
2435
ZSTD_storeLastLiterals(seqStore_t * seqStorePtr,const BYTE * anchor,size_t lastLLSize)2436 static void ZSTD_storeLastLiterals(seqStore_t* seqStorePtr,
2437 const BYTE* anchor, size_t lastLLSize)
2438 {
2439 memcpy(seqStorePtr->lit, anchor, lastLLSize);
2440 seqStorePtr->lit += lastLLSize;
2441 }
2442
ZSTD_resetSeqStore(seqStore_t * ssPtr)2443 void ZSTD_resetSeqStore(seqStore_t* ssPtr)
2444 {
2445 ssPtr->lit = ssPtr->litStart;
2446 ssPtr->sequences = ssPtr->sequencesStart;
2447 ssPtr->longLengthID = 0;
2448 }
2449
ZSTD_compressBlock_internal(ZSTD_CCtx * zc,void * dst,size_t dstCapacity,const void * src,size_t srcSize)2450 static size_t ZSTD_compressBlock_internal(ZSTD_CCtx* zc,
2451 void* dst, size_t dstCapacity,
2452 const void* src, size_t srcSize)
2453 {
2454 ZSTD_matchState_t* const ms = &zc->blockState.matchState;
2455 size_t cSize;
2456 DEBUGLOG(5, "ZSTD_compressBlock_internal (dstCapacity=%zu, dictLimit=%u, nextToUpdate=%u)",
2457 dstCapacity, ms->window.dictLimit, ms->nextToUpdate);
2458 assert(srcSize <= ZSTD_BLOCKSIZE_MAX);
2459
2460 /* Assert that we have correctly flushed the ctx params into the ms's copy */
2461 ZSTD_assertEqualCParams(zc->appliedParams.cParams, ms->cParams);
2462
2463 if (srcSize < MIN_CBLOCK_SIZE+ZSTD_blockHeaderSize+1) {
2464 ZSTD_ldm_skipSequences(&zc->externSeqStore, srcSize, zc->appliedParams.cParams.searchLength);
2465 cSize = 0;
2466 goto out; /* don't even attempt compression below a certain srcSize */
2467 }
2468 ZSTD_resetSeqStore(&(zc->seqStore));
2469 ms->opt.symbolCosts = &zc->blockState.prevCBlock->entropy; /* required for optimal parser to read stats from dictionary */
2470
2471 /* a gap between an attached dict and the current window is not safe,
2472 * they must remain adjacent, and when that stops being the case, the dict
2473 * must be unset */
2474 assert(ms->dictMatchState == NULL || ms->loadedDictEnd == ms->window.dictLimit);
2475
2476 /* limited update after a very long match */
2477 { const BYTE* const base = ms->window.base;
2478 const BYTE* const istart = (const BYTE*)src;
2479 const U32 current = (U32)(istart-base);
2480 if (sizeof(ptrdiff_t)==8) assert(istart - base < (ptrdiff_t)(U32)(-1)); /* ensure no overflow */
2481 if (current > ms->nextToUpdate + 384)
2482 ms->nextToUpdate = current - MIN(192, (U32)(current - ms->nextToUpdate - 384));
2483 }
2484
2485 /* select and store sequences */
2486 { ZSTD_dictMode_e const dictMode = ZSTD_matchState_dictMode(ms);
2487 size_t lastLLSize;
2488 { int i;
2489 for (i = 0; i < ZSTD_REP_NUM; ++i)
2490 zc->blockState.nextCBlock->rep[i] = zc->blockState.prevCBlock->rep[i];
2491 }
2492 if (zc->externSeqStore.pos < zc->externSeqStore.size) {
2493 assert(!zc->appliedParams.ldmParams.enableLdm);
2494 /* Updates ldmSeqStore.pos */
2495 lastLLSize =
2496 ZSTD_ldm_blockCompress(&zc->externSeqStore,
2497 ms, &zc->seqStore,
2498 zc->blockState.nextCBlock->rep,
2499 src, srcSize);
2500 assert(zc->externSeqStore.pos <= zc->externSeqStore.size);
2501 } else if (zc->appliedParams.ldmParams.enableLdm) {
2502 rawSeqStore_t ldmSeqStore = {NULL, 0, 0, 0};
2503
2504 ldmSeqStore.seq = zc->ldmSequences;
2505 ldmSeqStore.capacity = zc->maxNbLdmSequences;
2506 /* Updates ldmSeqStore.size */
2507 CHECK_F(ZSTD_ldm_generateSequences(&zc->ldmState, &ldmSeqStore,
2508 &zc->appliedParams.ldmParams,
2509 src, srcSize));
2510 /* Updates ldmSeqStore.pos */
2511 lastLLSize =
2512 ZSTD_ldm_blockCompress(&ldmSeqStore,
2513 ms, &zc->seqStore,
2514 zc->blockState.nextCBlock->rep,
2515 src, srcSize);
2516 assert(ldmSeqStore.pos == ldmSeqStore.size);
2517 } else { /* not long range mode */
2518 ZSTD_blockCompressor const blockCompressor = ZSTD_selectBlockCompressor(zc->appliedParams.cParams.strategy, dictMode);
2519 lastLLSize = blockCompressor(ms, &zc->seqStore, zc->blockState.nextCBlock->rep, src, srcSize);
2520 }
2521 { const BYTE* const lastLiterals = (const BYTE*)src + srcSize - lastLLSize;
2522 ZSTD_storeLastLiterals(&zc->seqStore, lastLiterals, lastLLSize);
2523 } }
2524
2525 /* encode sequences and literals */
2526 cSize = ZSTD_compressSequences(&zc->seqStore,
2527 &zc->blockState.prevCBlock->entropy, &zc->blockState.nextCBlock->entropy,
2528 &zc->appliedParams,
2529 dst, dstCapacity,
2530 srcSize,
2531 zc->entropyWorkspace, HUF_WORKSPACE_SIZE /* statically allocated in resetCCtx */,
2532 zc->bmi2);
2533
2534 out:
2535 if (!ZSTD_isError(cSize) && cSize != 0) {
2536 /* confirm repcodes and entropy tables when emitting a compressed block */
2537 ZSTD_compressedBlockState_t* const tmp = zc->blockState.prevCBlock;
2538 zc->blockState.prevCBlock = zc->blockState.nextCBlock;
2539 zc->blockState.nextCBlock = tmp;
2540 }
2541 /* We check that dictionaries have offset codes available for the first
2542 * block. After the first block, the offcode table might not have large
2543 * enough codes to represent the offsets in the data.
2544 */
2545 if (zc->blockState.prevCBlock->entropy.fse.offcode_repeatMode == FSE_repeat_valid)
2546 zc->blockState.prevCBlock->entropy.fse.offcode_repeatMode = FSE_repeat_check;
2547
2548 return cSize;
2549 }
2550
2551
2552 /*! ZSTD_compress_frameChunk() :
2553 * Compress a chunk of data into one or multiple blocks.
2554 * All blocks will be terminated, all input will be consumed.
2555 * Function will issue an error if there is not enough `dstCapacity` to hold the compressed content.
2556 * Frame is supposed already started (header already produced)
2557 * @return : compressed size, or an error code
2558 */
ZSTD_compress_frameChunk(ZSTD_CCtx * cctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize,U32 lastFrameChunk)2559 static size_t ZSTD_compress_frameChunk (ZSTD_CCtx* cctx,
2560 void* dst, size_t dstCapacity,
2561 const void* src, size_t srcSize,
2562 U32 lastFrameChunk)
2563 {
2564 size_t blockSize = cctx->blockSize;
2565 size_t remaining = srcSize;
2566 const BYTE* ip = (const BYTE*)src;
2567 BYTE* const ostart = (BYTE*)dst;
2568 BYTE* op = ostart;
2569 U32 const maxDist = (U32)1 << cctx->appliedParams.cParams.windowLog;
2570 assert(cctx->appliedParams.cParams.windowLog <= 31);
2571
2572 DEBUGLOG(5, "ZSTD_compress_frameChunk (blockSize=%u)", (U32)blockSize);
2573 if (cctx->appliedParams.fParams.checksumFlag && srcSize)
2574 XXH64_update(&cctx->xxhState, src, srcSize);
2575
2576 while (remaining) {
2577 ZSTD_matchState_t* const ms = &cctx->blockState.matchState;
2578 U32 const lastBlock = lastFrameChunk & (blockSize >= remaining);
2579
2580 if (dstCapacity < ZSTD_blockHeaderSize + MIN_CBLOCK_SIZE)
2581 return ERROR(dstSize_tooSmall); /* not enough space to store compressed block */
2582 if (remaining < blockSize) blockSize = remaining;
2583
2584 if (ZSTD_window_needOverflowCorrection(ms->window, ip + blockSize)) {
2585 U32 const cycleLog = ZSTD_cycleLog(cctx->appliedParams.cParams.chainLog, cctx->appliedParams.cParams.strategy);
2586 U32 const correction = ZSTD_window_correctOverflow(&ms->window, cycleLog, maxDist, ip);
2587 ZSTD_STATIC_ASSERT(ZSTD_CHAINLOG_MAX <= 30);
2588 ZSTD_STATIC_ASSERT(ZSTD_WINDOWLOG_MAX_32 <= 30);
2589 ZSTD_STATIC_ASSERT(ZSTD_WINDOWLOG_MAX <= 31);
2590 ZSTD_reduceIndex(cctx, correction);
2591 if (ms->nextToUpdate < correction) ms->nextToUpdate = 0;
2592 else ms->nextToUpdate -= correction;
2593 ms->loadedDictEnd = 0;
2594 ms->dictMatchState = NULL;
2595 }
2596 ZSTD_window_enforceMaxDist(&ms->window, ip + blockSize, maxDist, &ms->loadedDictEnd, &ms->dictMatchState);
2597 if (ms->nextToUpdate < ms->window.lowLimit) ms->nextToUpdate = ms->window.lowLimit;
2598
2599 { size_t cSize = ZSTD_compressBlock_internal(cctx,
2600 op+ZSTD_blockHeaderSize, dstCapacity-ZSTD_blockHeaderSize,
2601 ip, blockSize);
2602 if (ZSTD_isError(cSize)) return cSize;
2603
2604 if (cSize == 0) { /* block is not compressible */
2605 cSize = ZSTD_noCompressBlock(op, dstCapacity, ip, blockSize, lastBlock);
2606 if (ZSTD_isError(cSize)) return cSize;
2607 } else {
2608 U32 const cBlockHeader24 = lastBlock + (((U32)bt_compressed)<<1) + (U32)(cSize << 3);
2609 MEM_writeLE24(op, cBlockHeader24);
2610 cSize += ZSTD_blockHeaderSize;
2611 }
2612
2613 ip += blockSize;
2614 assert(remaining >= blockSize);
2615 remaining -= blockSize;
2616 op += cSize;
2617 assert(dstCapacity >= cSize);
2618 dstCapacity -= cSize;
2619 DEBUGLOG(5, "ZSTD_compress_frameChunk: adding a block of size %u",
2620 (U32)cSize);
2621 } }
2622
2623 if (lastFrameChunk && (op>ostart)) cctx->stage = ZSTDcs_ending;
2624 return op-ostart;
2625 }
2626
2627
ZSTD_writeFrameHeader(void * dst,size_t dstCapacity,ZSTD_CCtx_params params,U64 pledgedSrcSize,U32 dictID)2628 static size_t ZSTD_writeFrameHeader(void* dst, size_t dstCapacity,
2629 ZSTD_CCtx_params params, U64 pledgedSrcSize, U32 dictID)
2630 { BYTE* const op = (BYTE*)dst;
2631 U32 const dictIDSizeCodeLength = (dictID>0) + (dictID>=256) + (dictID>=65536); /* 0-3 */
2632 U32 const dictIDSizeCode = params.fParams.noDictIDFlag ? 0 : dictIDSizeCodeLength; /* 0-3 */
2633 U32 const checksumFlag = params.fParams.checksumFlag>0;
2634 U32 const windowSize = (U32)1 << params.cParams.windowLog;
2635 U32 const singleSegment = params.fParams.contentSizeFlag && (windowSize >= pledgedSrcSize);
2636 BYTE const windowLogByte = (BYTE)((params.cParams.windowLog - ZSTD_WINDOWLOG_ABSOLUTEMIN) << 3);
2637 U32 const fcsCode = params.fParams.contentSizeFlag ?
2638 (pledgedSrcSize>=256) + (pledgedSrcSize>=65536+256) + (pledgedSrcSize>=0xFFFFFFFFU) : 0; /* 0-3 */
2639 BYTE const frameHeaderDecriptionByte = (BYTE)(dictIDSizeCode + (checksumFlag<<2) + (singleSegment<<5) + (fcsCode<<6) );
2640 size_t pos=0;
2641
2642 assert(!(params.fParams.contentSizeFlag && pledgedSrcSize == ZSTD_CONTENTSIZE_UNKNOWN));
2643 if (dstCapacity < ZSTD_frameHeaderSize_max) return ERROR(dstSize_tooSmall);
2644 DEBUGLOG(4, "ZSTD_writeFrameHeader : dictIDFlag : %u ; dictID : %u ; dictIDSizeCode : %u",
2645 !params.fParams.noDictIDFlag, dictID, dictIDSizeCode);
2646
2647 if (params.format == ZSTD_f_zstd1) {
2648 MEM_writeLE32(dst, ZSTD_MAGICNUMBER);
2649 pos = 4;
2650 }
2651 op[pos++] = frameHeaderDecriptionByte;
2652 if (!singleSegment) op[pos++] = windowLogByte;
2653 switch(dictIDSizeCode)
2654 {
2655 default: assert(0); /* impossible */
2656 case 0 : break;
2657 case 1 : op[pos] = (BYTE)(dictID); pos++; break;
2658 case 2 : MEM_writeLE16(op+pos, (U16)dictID); pos+=2; break;
2659 case 3 : MEM_writeLE32(op+pos, dictID); pos+=4; break;
2660 }
2661 switch(fcsCode)
2662 {
2663 default: assert(0); /* impossible */
2664 case 0 : if (singleSegment) op[pos++] = (BYTE)(pledgedSrcSize); break;
2665 case 1 : MEM_writeLE16(op+pos, (U16)(pledgedSrcSize-256)); pos+=2; break;
2666 case 2 : MEM_writeLE32(op+pos, (U32)(pledgedSrcSize)); pos+=4; break;
2667 case 3 : MEM_writeLE64(op+pos, (U64)(pledgedSrcSize)); pos+=8; break;
2668 }
2669 return pos;
2670 }
2671
2672 /* ZSTD_writeLastEmptyBlock() :
2673 * output an empty Block with end-of-frame mark to complete a frame
2674 * @return : size of data written into `dst` (== ZSTD_blockHeaderSize (defined in zstd_internal.h))
2675 * or an error code if `dstCapcity` is too small (<ZSTD_blockHeaderSize)
2676 */
ZSTD_writeLastEmptyBlock(void * dst,size_t dstCapacity)2677 size_t ZSTD_writeLastEmptyBlock(void* dst, size_t dstCapacity)
2678 {
2679 if (dstCapacity < ZSTD_blockHeaderSize) return ERROR(dstSize_tooSmall);
2680 { U32 const cBlockHeader24 = 1 /*lastBlock*/ + (((U32)bt_raw)<<1); /* 0 size */
2681 MEM_writeLE24(dst, cBlockHeader24);
2682 return ZSTD_blockHeaderSize;
2683 }
2684 }
2685
ZSTD_referenceExternalSequences(ZSTD_CCtx * cctx,rawSeq * seq,size_t nbSeq)2686 size_t ZSTD_referenceExternalSequences(ZSTD_CCtx* cctx, rawSeq* seq, size_t nbSeq)
2687 {
2688 if (cctx->stage != ZSTDcs_init)
2689 return ERROR(stage_wrong);
2690 if (cctx->appliedParams.ldmParams.enableLdm)
2691 return ERROR(parameter_unsupported);
2692 cctx->externSeqStore.seq = seq;
2693 cctx->externSeqStore.size = nbSeq;
2694 cctx->externSeqStore.capacity = nbSeq;
2695 cctx->externSeqStore.pos = 0;
2696 return 0;
2697 }
2698
2699
ZSTD_compressContinue_internal(ZSTD_CCtx * cctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize,U32 frame,U32 lastFrameChunk)2700 static size_t ZSTD_compressContinue_internal (ZSTD_CCtx* cctx,
2701 void* dst, size_t dstCapacity,
2702 const void* src, size_t srcSize,
2703 U32 frame, U32 lastFrameChunk)
2704 {
2705 ZSTD_matchState_t* const ms = &cctx->blockState.matchState;
2706 size_t fhSize = 0;
2707
2708 DEBUGLOG(5, "ZSTD_compressContinue_internal, stage: %u, srcSize: %u",
2709 cctx->stage, (U32)srcSize);
2710 if (cctx->stage==ZSTDcs_created) return ERROR(stage_wrong); /* missing init (ZSTD_compressBegin) */
2711
2712 if (frame && (cctx->stage==ZSTDcs_init)) {
2713 fhSize = ZSTD_writeFrameHeader(dst, dstCapacity, cctx->appliedParams,
2714 cctx->pledgedSrcSizePlusOne-1, cctx->dictID);
2715 if (ZSTD_isError(fhSize)) return fhSize;
2716 dstCapacity -= fhSize;
2717 dst = (char*)dst + fhSize;
2718 cctx->stage = ZSTDcs_ongoing;
2719 }
2720
2721 if (!srcSize) return fhSize; /* do not generate an empty block if no input */
2722
2723 if (!ZSTD_window_update(&ms->window, src, srcSize)) {
2724 ms->nextToUpdate = ms->window.dictLimit;
2725 }
2726 if (cctx->appliedParams.ldmParams.enableLdm) {
2727 ZSTD_window_update(&cctx->ldmState.window, src, srcSize);
2728 }
2729
2730 if (!frame) {
2731 /* overflow check and correction for block mode */
2732 if (ZSTD_window_needOverflowCorrection(ms->window, (const char*)src + srcSize)) {
2733 U32 const cycleLog = ZSTD_cycleLog(cctx->appliedParams.cParams.chainLog, cctx->appliedParams.cParams.strategy);
2734 U32 const correction = ZSTD_window_correctOverflow(&ms->window, cycleLog, 1 << cctx->appliedParams.cParams.windowLog, src);
2735 ZSTD_STATIC_ASSERT(ZSTD_CHAINLOG_MAX <= 30);
2736 ZSTD_STATIC_ASSERT(ZSTD_WINDOWLOG_MAX_32 <= 30);
2737 ZSTD_STATIC_ASSERT(ZSTD_WINDOWLOG_MAX <= 31);
2738 ZSTD_reduceIndex(cctx, correction);
2739 if (ms->nextToUpdate < correction) ms->nextToUpdate = 0;
2740 else ms->nextToUpdate -= correction;
2741 ms->loadedDictEnd = 0;
2742 ms->dictMatchState = NULL;
2743 }
2744 }
2745
2746 DEBUGLOG(5, "ZSTD_compressContinue_internal (blockSize=%u)", (U32)cctx->blockSize);
2747 { size_t const cSize = frame ?
2748 ZSTD_compress_frameChunk (cctx, dst, dstCapacity, src, srcSize, lastFrameChunk) :
2749 ZSTD_compressBlock_internal (cctx, dst, dstCapacity, src, srcSize);
2750 if (ZSTD_isError(cSize)) return cSize;
2751 cctx->consumedSrcSize += srcSize;
2752 cctx->producedCSize += (cSize + fhSize);
2753 assert(!(cctx->appliedParams.fParams.contentSizeFlag && cctx->pledgedSrcSizePlusOne == 0));
2754 if (cctx->pledgedSrcSizePlusOne != 0) { /* control src size */
2755 ZSTD_STATIC_ASSERT(ZSTD_CONTENTSIZE_UNKNOWN == (unsigned long long)-1);
2756 if (cctx->consumedSrcSize+1 > cctx->pledgedSrcSizePlusOne) {
2757 DEBUGLOG(4, "error : pledgedSrcSize = %u, while realSrcSize >= %u",
2758 (U32)cctx->pledgedSrcSizePlusOne-1, (U32)cctx->consumedSrcSize);
2759 return ERROR(srcSize_wrong);
2760 }
2761 }
2762 return cSize + fhSize;
2763 }
2764 }
2765
ZSTD_compressContinue(ZSTD_CCtx * cctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize)2766 size_t ZSTD_compressContinue (ZSTD_CCtx* cctx,
2767 void* dst, size_t dstCapacity,
2768 const void* src, size_t srcSize)
2769 {
2770 DEBUGLOG(5, "ZSTD_compressContinue (srcSize=%u)", (U32)srcSize);
2771 return ZSTD_compressContinue_internal(cctx, dst, dstCapacity, src, srcSize, 1 /* frame mode */, 0 /* last chunk */);
2772 }
2773
2774
ZSTD_getBlockSize(const ZSTD_CCtx * cctx)2775 size_t ZSTD_getBlockSize(const ZSTD_CCtx* cctx)
2776 {
2777 ZSTD_compressionParameters const cParams = cctx->appliedParams.cParams;
2778 assert(!ZSTD_checkCParams(cParams));
2779 return MIN (ZSTD_BLOCKSIZE_MAX, (U32)1 << cParams.windowLog);
2780 }
2781
ZSTD_compressBlock(ZSTD_CCtx * cctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize)2782 size_t ZSTD_compressBlock(ZSTD_CCtx* cctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
2783 {
2784 size_t const blockSizeMax = ZSTD_getBlockSize(cctx);
2785 if (srcSize > blockSizeMax) return ERROR(srcSize_wrong);
2786
2787 return ZSTD_compressContinue_internal(cctx, dst, dstCapacity, src, srcSize, 0 /* frame mode */, 0 /* last chunk */);
2788 }
2789
2790 /*! ZSTD_loadDictionaryContent() :
2791 * @return : 0, or an error code
2792 */
ZSTD_loadDictionaryContent(ZSTD_matchState_t * ms,ZSTD_CCtx_params const * params,const void * src,size_t srcSize,ZSTD_dictTableLoadMethod_e dtlm)2793 static size_t ZSTD_loadDictionaryContent(ZSTD_matchState_t* ms,
2794 ZSTD_CCtx_params const* params,
2795 const void* src, size_t srcSize,
2796 ZSTD_dictTableLoadMethod_e dtlm)
2797 {
2798 const BYTE* const ip = (const BYTE*) src;
2799 const BYTE* const iend = ip + srcSize;
2800
2801 ZSTD_window_update(&ms->window, src, srcSize);
2802 ms->loadedDictEnd = params->forceWindow ? 0 : (U32)(iend - ms->window.base);
2803
2804 /* Assert that we the ms params match the params we're being given */
2805 ZSTD_assertEqualCParams(params->cParams, ms->cParams);
2806
2807 if (srcSize <= HASH_READ_SIZE) return 0;
2808
2809 switch(params->cParams.strategy)
2810 {
2811 case ZSTD_fast:
2812 ZSTD_fillHashTable(ms, iend, dtlm);
2813 break;
2814 case ZSTD_dfast:
2815 ZSTD_fillDoubleHashTable(ms, iend, dtlm);
2816 break;
2817
2818 case ZSTD_greedy:
2819 case ZSTD_lazy:
2820 case ZSTD_lazy2:
2821 if (srcSize >= HASH_READ_SIZE)
2822 ZSTD_insertAndFindFirstIndex(ms, iend-HASH_READ_SIZE);
2823 break;
2824
2825 case ZSTD_btlazy2: /* we want the dictionary table fully sorted */
2826 case ZSTD_btopt:
2827 case ZSTD_btultra:
2828 if (srcSize >= HASH_READ_SIZE)
2829 ZSTD_updateTree(ms, iend-HASH_READ_SIZE, iend);
2830 break;
2831
2832 default:
2833 assert(0); /* not possible : not a valid strategy id */
2834 }
2835
2836 ms->nextToUpdate = (U32)(iend - ms->window.base);
2837 return 0;
2838 }
2839
2840
2841 /* Dictionaries that assign zero probability to symbols that show up causes problems
2842 when FSE encoding. Refuse dictionaries that assign zero probability to symbols
2843 that we may encounter during compression.
2844 NOTE: This behavior is not standard and could be improved in the future. */
ZSTD_checkDictNCount(short * normalizedCounter,unsigned dictMaxSymbolValue,unsigned maxSymbolValue)2845 static size_t ZSTD_checkDictNCount(short* normalizedCounter, unsigned dictMaxSymbolValue, unsigned maxSymbolValue) {
2846 U32 s;
2847 if (dictMaxSymbolValue < maxSymbolValue) return ERROR(dictionary_corrupted);
2848 for (s = 0; s <= maxSymbolValue; ++s) {
2849 if (normalizedCounter[s] == 0) return ERROR(dictionary_corrupted);
2850 }
2851 return 0;
2852 }
2853
2854
2855 /* Dictionary format :
2856 * See :
2857 * https://github.com/facebook/zstd/blob/master/doc/zstd_compression_format.md#dictionary-format
2858 */
2859 /*! ZSTD_loadZstdDictionary() :
2860 * @return : dictID, or an error code
2861 * assumptions : magic number supposed already checked
2862 * dictSize supposed > 8
2863 */
ZSTD_loadZstdDictionary(ZSTD_compressedBlockState_t * bs,ZSTD_matchState_t * ms,ZSTD_CCtx_params const * params,const void * dict,size_t dictSize,ZSTD_dictTableLoadMethod_e dtlm,void * workspace)2864 static size_t ZSTD_loadZstdDictionary(ZSTD_compressedBlockState_t* bs,
2865 ZSTD_matchState_t* ms,
2866 ZSTD_CCtx_params const* params,
2867 const void* dict, size_t dictSize,
2868 ZSTD_dictTableLoadMethod_e dtlm,
2869 void* workspace)
2870 {
2871 const BYTE* dictPtr = (const BYTE*)dict;
2872 const BYTE* const dictEnd = dictPtr + dictSize;
2873 short offcodeNCount[MaxOff+1];
2874 unsigned offcodeMaxValue = MaxOff;
2875 size_t dictID;
2876
2877 ZSTD_STATIC_ASSERT(HUF_WORKSPACE_SIZE >= (1<<MAX(MLFSELog,LLFSELog)));
2878 assert(dictSize > 8);
2879 assert(MEM_readLE32(dictPtr) == ZSTD_MAGIC_DICTIONARY);
2880
2881 dictPtr += 4; /* skip magic number */
2882 dictID = params->fParams.noDictIDFlag ? 0 : MEM_readLE32(dictPtr);
2883 dictPtr += 4;
2884
2885 { unsigned maxSymbolValue = 255;
2886 size_t const hufHeaderSize = HUF_readCTable((HUF_CElt*)bs->entropy.huf.CTable, &maxSymbolValue, dictPtr, dictEnd-dictPtr);
2887 if (HUF_isError(hufHeaderSize)) return ERROR(dictionary_corrupted);
2888 if (maxSymbolValue < 255) return ERROR(dictionary_corrupted);
2889 dictPtr += hufHeaderSize;
2890 }
2891
2892 { unsigned offcodeLog;
2893 size_t const offcodeHeaderSize = FSE_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dictPtr, dictEnd-dictPtr);
2894 if (FSE_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted);
2895 if (offcodeLog > OffFSELog) return ERROR(dictionary_corrupted);
2896 /* Defer checking offcodeMaxValue because we need to know the size of the dictionary content */
2897 /* fill all offset symbols to avoid garbage at end of table */
2898 CHECK_E( FSE_buildCTable_wksp(bs->entropy.fse.offcodeCTable, offcodeNCount, MaxOff, offcodeLog, workspace, HUF_WORKSPACE_SIZE),
2899 dictionary_corrupted);
2900 dictPtr += offcodeHeaderSize;
2901 }
2902
2903 { short matchlengthNCount[MaxML+1];
2904 unsigned matchlengthMaxValue = MaxML, matchlengthLog;
2905 size_t const matchlengthHeaderSize = FSE_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd-dictPtr);
2906 if (FSE_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted);
2907 if (matchlengthLog > MLFSELog) return ERROR(dictionary_corrupted);
2908 /* Every match length code must have non-zero probability */
2909 CHECK_F( ZSTD_checkDictNCount(matchlengthNCount, matchlengthMaxValue, MaxML));
2910 CHECK_E( FSE_buildCTable_wksp(bs->entropy.fse.matchlengthCTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog, workspace, HUF_WORKSPACE_SIZE),
2911 dictionary_corrupted);
2912 dictPtr += matchlengthHeaderSize;
2913 }
2914
2915 { short litlengthNCount[MaxLL+1];
2916 unsigned litlengthMaxValue = MaxLL, litlengthLog;
2917 size_t const litlengthHeaderSize = FSE_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd-dictPtr);
2918 if (FSE_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted);
2919 if (litlengthLog > LLFSELog) return ERROR(dictionary_corrupted);
2920 /* Every literal length code must have non-zero probability */
2921 CHECK_F( ZSTD_checkDictNCount(litlengthNCount, litlengthMaxValue, MaxLL));
2922 CHECK_E( FSE_buildCTable_wksp(bs->entropy.fse.litlengthCTable, litlengthNCount, litlengthMaxValue, litlengthLog, workspace, HUF_WORKSPACE_SIZE),
2923 dictionary_corrupted);
2924 dictPtr += litlengthHeaderSize;
2925 }
2926
2927 if (dictPtr+12 > dictEnd) return ERROR(dictionary_corrupted);
2928 bs->rep[0] = MEM_readLE32(dictPtr+0);
2929 bs->rep[1] = MEM_readLE32(dictPtr+4);
2930 bs->rep[2] = MEM_readLE32(dictPtr+8);
2931 dictPtr += 12;
2932
2933 { size_t const dictContentSize = (size_t)(dictEnd - dictPtr);
2934 U32 offcodeMax = MaxOff;
2935 if (dictContentSize <= ((U32)-1) - 128 KB) {
2936 U32 const maxOffset = (U32)dictContentSize + 128 KB; /* The maximum offset that must be supported */
2937 offcodeMax = ZSTD_highbit32(maxOffset); /* Calculate minimum offset code required to represent maxOffset */
2938 }
2939 /* All offset values <= dictContentSize + 128 KB must be representable */
2940 CHECK_F (ZSTD_checkDictNCount(offcodeNCount, offcodeMaxValue, MIN(offcodeMax, MaxOff)));
2941 /* All repCodes must be <= dictContentSize and != 0*/
2942 { U32 u;
2943 for (u=0; u<3; u++) {
2944 if (bs->rep[u] == 0) return ERROR(dictionary_corrupted);
2945 if (bs->rep[u] > dictContentSize) return ERROR(dictionary_corrupted);
2946 } }
2947
2948 bs->entropy.huf.repeatMode = HUF_repeat_valid;
2949 bs->entropy.fse.offcode_repeatMode = FSE_repeat_valid;
2950 bs->entropy.fse.matchlength_repeatMode = FSE_repeat_valid;
2951 bs->entropy.fse.litlength_repeatMode = FSE_repeat_valid;
2952 CHECK_F(ZSTD_loadDictionaryContent(ms, params, dictPtr, dictContentSize, dtlm));
2953 return dictID;
2954 }
2955 }
2956
2957 /** ZSTD_compress_insertDictionary() :
2958 * @return : dictID, or an error code */
2959 static size_t
ZSTD_compress_insertDictionary(ZSTD_compressedBlockState_t * bs,ZSTD_matchState_t * ms,const ZSTD_CCtx_params * params,const void * dict,size_t dictSize,ZSTD_dictContentType_e dictContentType,ZSTD_dictTableLoadMethod_e dtlm,void * workspace)2960 ZSTD_compress_insertDictionary(ZSTD_compressedBlockState_t* bs,
2961 ZSTD_matchState_t* ms,
2962 const ZSTD_CCtx_params* params,
2963 const void* dict, size_t dictSize,
2964 ZSTD_dictContentType_e dictContentType,
2965 ZSTD_dictTableLoadMethod_e dtlm,
2966 void* workspace)
2967 {
2968 DEBUGLOG(4, "ZSTD_compress_insertDictionary (dictSize=%u)", (U32)dictSize);
2969 if ((dict==NULL) || (dictSize<=8)) return 0;
2970
2971 ZSTD_reset_compressedBlockState(bs);
2972
2973 /* dict restricted modes */
2974 if (dictContentType == ZSTD_dct_rawContent)
2975 return ZSTD_loadDictionaryContent(ms, params, dict, dictSize, dtlm);
2976
2977 if (MEM_readLE32(dict) != ZSTD_MAGIC_DICTIONARY) {
2978 if (dictContentType == ZSTD_dct_auto) {
2979 DEBUGLOG(4, "raw content dictionary detected");
2980 return ZSTD_loadDictionaryContent(ms, params, dict, dictSize, dtlm);
2981 }
2982 if (dictContentType == ZSTD_dct_fullDict)
2983 return ERROR(dictionary_wrong);
2984 assert(0); /* impossible */
2985 }
2986
2987 /* dict as full zstd dictionary */
2988 return ZSTD_loadZstdDictionary(bs, ms, params, dict, dictSize, dtlm, workspace);
2989 }
2990
2991 /*! ZSTD_compressBegin_internal() :
2992 * @return : 0, or an error code */
ZSTD_compressBegin_internal(ZSTD_CCtx * cctx,const void * dict,size_t dictSize,ZSTD_dictContentType_e dictContentType,ZSTD_dictTableLoadMethod_e dtlm,const ZSTD_CDict * cdict,ZSTD_CCtx_params params,U64 pledgedSrcSize,ZSTD_buffered_policy_e zbuff)2993 static size_t ZSTD_compressBegin_internal(ZSTD_CCtx* cctx,
2994 const void* dict, size_t dictSize,
2995 ZSTD_dictContentType_e dictContentType,
2996 ZSTD_dictTableLoadMethod_e dtlm,
2997 const ZSTD_CDict* cdict,
2998 ZSTD_CCtx_params params, U64 pledgedSrcSize,
2999 ZSTD_buffered_policy_e zbuff)
3000 {
3001 DEBUGLOG(4, "ZSTD_compressBegin_internal: wlog=%u", params.cParams.windowLog);
3002 /* params are supposed to be fully validated at this point */
3003 assert(!ZSTD_isError(ZSTD_checkCParams(params.cParams)));
3004 assert(!((dict) && (cdict))); /* either dict or cdict, not both */
3005
3006 if (cdict && cdict->dictContentSize>0) {
3007 return ZSTD_resetCCtx_usingCDict(cctx, cdict, params, pledgedSrcSize, zbuff);
3008 }
3009
3010 CHECK_F( ZSTD_resetCCtx_internal(cctx, params, pledgedSrcSize,
3011 ZSTDcrp_continue, zbuff) );
3012 {
3013 size_t const dictID = ZSTD_compress_insertDictionary(
3014 cctx->blockState.prevCBlock, &cctx->blockState.matchState,
3015 ¶ms, dict, dictSize, dictContentType, dtlm, cctx->entropyWorkspace);
3016 if (ZSTD_isError(dictID)) return dictID;
3017 assert(dictID <= (size_t)(U32)-1);
3018 cctx->dictID = (U32)dictID;
3019 }
3020 return 0;
3021 }
3022
ZSTD_compressBegin_advanced_internal(ZSTD_CCtx * cctx,const void * dict,size_t dictSize,ZSTD_dictContentType_e dictContentType,ZSTD_dictTableLoadMethod_e dtlm,const ZSTD_CDict * cdict,ZSTD_CCtx_params params,unsigned long long pledgedSrcSize)3023 size_t ZSTD_compressBegin_advanced_internal(ZSTD_CCtx* cctx,
3024 const void* dict, size_t dictSize,
3025 ZSTD_dictContentType_e dictContentType,
3026 ZSTD_dictTableLoadMethod_e dtlm,
3027 const ZSTD_CDict* cdict,
3028 ZSTD_CCtx_params params,
3029 unsigned long long pledgedSrcSize)
3030 {
3031 DEBUGLOG(4, "ZSTD_compressBegin_advanced_internal: wlog=%u", params.cParams.windowLog);
3032 /* compression parameters verification and optimization */
3033 CHECK_F( ZSTD_checkCParams(params.cParams) );
3034 return ZSTD_compressBegin_internal(cctx,
3035 dict, dictSize, dictContentType, dtlm,
3036 cdict,
3037 params, pledgedSrcSize,
3038 ZSTDb_not_buffered);
3039 }
3040
3041 /*! ZSTD_compressBegin_advanced() :
3042 * @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)3043 size_t ZSTD_compressBegin_advanced(ZSTD_CCtx* cctx,
3044 const void* dict, size_t dictSize,
3045 ZSTD_parameters params, unsigned long long pledgedSrcSize)
3046 {
3047 ZSTD_CCtx_params const cctxParams =
3048 ZSTD_assignParamsToCCtxParams(cctx->requestedParams, params);
3049 return ZSTD_compressBegin_advanced_internal(cctx,
3050 dict, dictSize, ZSTD_dct_auto, ZSTD_dtlm_fast,
3051 NULL /*cdict*/,
3052 cctxParams, pledgedSrcSize);
3053 }
3054
ZSTD_compressBegin_usingDict(ZSTD_CCtx * cctx,const void * dict,size_t dictSize,int compressionLevel)3055 size_t ZSTD_compressBegin_usingDict(ZSTD_CCtx* cctx, const void* dict, size_t dictSize, int compressionLevel)
3056 {
3057 ZSTD_parameters const params = ZSTD_getParams(compressionLevel, ZSTD_CONTENTSIZE_UNKNOWN, dictSize);
3058 ZSTD_CCtx_params const cctxParams =
3059 ZSTD_assignParamsToCCtxParams(cctx->requestedParams, params);
3060 DEBUGLOG(4, "ZSTD_compressBegin_usingDict (dictSize=%u)", (U32)dictSize);
3061 return ZSTD_compressBegin_internal(cctx, dict, dictSize, ZSTD_dct_auto, ZSTD_dtlm_fast, NULL,
3062 cctxParams, ZSTD_CONTENTSIZE_UNKNOWN, ZSTDb_not_buffered);
3063 }
3064
ZSTD_compressBegin(ZSTD_CCtx * cctx,int compressionLevel)3065 size_t ZSTD_compressBegin(ZSTD_CCtx* cctx, int compressionLevel)
3066 {
3067 return ZSTD_compressBegin_usingDict(cctx, NULL, 0, compressionLevel);
3068 }
3069
3070
3071 /*! ZSTD_writeEpilogue() :
3072 * Ends a frame.
3073 * @return : nb of bytes written into dst (or an error code) */
ZSTD_writeEpilogue(ZSTD_CCtx * cctx,void * dst,size_t dstCapacity)3074 static size_t ZSTD_writeEpilogue(ZSTD_CCtx* cctx, void* dst, size_t dstCapacity)
3075 {
3076 BYTE* const ostart = (BYTE*)dst;
3077 BYTE* op = ostart;
3078 size_t fhSize = 0;
3079
3080 DEBUGLOG(4, "ZSTD_writeEpilogue");
3081 if (cctx->stage == ZSTDcs_created) return ERROR(stage_wrong); /* init missing */
3082
3083 /* special case : empty frame */
3084 if (cctx->stage == ZSTDcs_init) {
3085 fhSize = ZSTD_writeFrameHeader(dst, dstCapacity, cctx->appliedParams, 0, 0);
3086 if (ZSTD_isError(fhSize)) return fhSize;
3087 dstCapacity -= fhSize;
3088 op += fhSize;
3089 cctx->stage = ZSTDcs_ongoing;
3090 }
3091
3092 if (cctx->stage != ZSTDcs_ending) {
3093 /* write one last empty block, make it the "last" block */
3094 U32 const cBlockHeader24 = 1 /* last block */ + (((U32)bt_raw)<<1) + 0;
3095 if (dstCapacity<4) return ERROR(dstSize_tooSmall);
3096 MEM_writeLE32(op, cBlockHeader24);
3097 op += ZSTD_blockHeaderSize;
3098 dstCapacity -= ZSTD_blockHeaderSize;
3099 }
3100
3101 if (cctx->appliedParams.fParams.checksumFlag) {
3102 U32 const checksum = (U32) XXH64_digest(&cctx->xxhState);
3103 if (dstCapacity<4) return ERROR(dstSize_tooSmall);
3104 DEBUGLOG(4, "ZSTD_writeEpilogue: write checksum : %08X", checksum);
3105 MEM_writeLE32(op, checksum);
3106 op += 4;
3107 }
3108
3109 cctx->stage = ZSTDcs_created; /* return to "created but no init" status */
3110 return op-ostart;
3111 }
3112
ZSTD_compressEnd(ZSTD_CCtx * cctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize)3113 size_t ZSTD_compressEnd (ZSTD_CCtx* cctx,
3114 void* dst, size_t dstCapacity,
3115 const void* src, size_t srcSize)
3116 {
3117 size_t endResult;
3118 size_t const cSize = ZSTD_compressContinue_internal(cctx,
3119 dst, dstCapacity, src, srcSize,
3120 1 /* frame mode */, 1 /* last chunk */);
3121 if (ZSTD_isError(cSize)) return cSize;
3122 endResult = ZSTD_writeEpilogue(cctx, (char*)dst + cSize, dstCapacity-cSize);
3123 if (ZSTD_isError(endResult)) return endResult;
3124 assert(!(cctx->appliedParams.fParams.contentSizeFlag && cctx->pledgedSrcSizePlusOne == 0));
3125 if (cctx->pledgedSrcSizePlusOne != 0) { /* control src size */
3126 ZSTD_STATIC_ASSERT(ZSTD_CONTENTSIZE_UNKNOWN == (unsigned long long)-1);
3127 DEBUGLOG(4, "end of frame : controlling src size");
3128 if (cctx->pledgedSrcSizePlusOne != cctx->consumedSrcSize+1) {
3129 DEBUGLOG(4, "error : pledgedSrcSize = %u, while realSrcSize = %u",
3130 (U32)cctx->pledgedSrcSizePlusOne-1, (U32)cctx->consumedSrcSize);
3131 return ERROR(srcSize_wrong);
3132 } }
3133 return cSize + endResult;
3134 }
3135
3136
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)3137 static size_t ZSTD_compress_internal (ZSTD_CCtx* cctx,
3138 void* dst, size_t dstCapacity,
3139 const void* src, size_t srcSize,
3140 const void* dict,size_t dictSize,
3141 ZSTD_parameters params)
3142 {
3143 ZSTD_CCtx_params const cctxParams =
3144 ZSTD_assignParamsToCCtxParams(cctx->requestedParams, params);
3145 DEBUGLOG(4, "ZSTD_compress_internal");
3146 return ZSTD_compress_advanced_internal(cctx,
3147 dst, dstCapacity,
3148 src, srcSize,
3149 dict, dictSize,
3150 cctxParams);
3151 }
3152
ZSTD_compress_advanced(ZSTD_CCtx * cctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize,const void * dict,size_t dictSize,ZSTD_parameters params)3153 size_t ZSTD_compress_advanced (ZSTD_CCtx* cctx,
3154 void* dst, size_t dstCapacity,
3155 const void* src, size_t srcSize,
3156 const void* dict,size_t dictSize,
3157 ZSTD_parameters params)
3158 {
3159 DEBUGLOG(4, "ZSTD_compress_advanced");
3160 CHECK_F(ZSTD_checkCParams(params.cParams));
3161 return ZSTD_compress_internal(cctx,
3162 dst, dstCapacity,
3163 src, srcSize,
3164 dict, dictSize,
3165 params);
3166 }
3167
3168 /* Internal */
ZSTD_compress_advanced_internal(ZSTD_CCtx * cctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize,const void * dict,size_t dictSize,ZSTD_CCtx_params params)3169 size_t ZSTD_compress_advanced_internal(
3170 ZSTD_CCtx* cctx,
3171 void* dst, size_t dstCapacity,
3172 const void* src, size_t srcSize,
3173 const void* dict,size_t dictSize,
3174 ZSTD_CCtx_params params)
3175 {
3176 DEBUGLOG(4, "ZSTD_compress_advanced_internal (srcSize:%u)", (U32)srcSize);
3177 CHECK_F( ZSTD_compressBegin_internal(cctx,
3178 dict, dictSize, ZSTD_dct_auto, ZSTD_dtlm_fast, NULL,
3179 params, srcSize, ZSTDb_not_buffered) );
3180 return ZSTD_compressEnd(cctx, dst, dstCapacity, src, srcSize);
3181 }
3182
ZSTD_compress_usingDict(ZSTD_CCtx * cctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize,const void * dict,size_t dictSize,int compressionLevel)3183 size_t ZSTD_compress_usingDict(ZSTD_CCtx* cctx,
3184 void* dst, size_t dstCapacity,
3185 const void* src, size_t srcSize,
3186 const void* dict, size_t dictSize,
3187 int compressionLevel)
3188 {
3189 ZSTD_parameters const params = ZSTD_getParams(compressionLevel, srcSize + (!srcSize), dict ? dictSize : 0);
3190 ZSTD_CCtx_params cctxParams = ZSTD_assignParamsToCCtxParams(cctx->requestedParams, params);
3191 assert(params.fParams.contentSizeFlag == 1);
3192 return ZSTD_compress_advanced_internal(cctx, dst, dstCapacity, src, srcSize, dict, dictSize, cctxParams);
3193 }
3194
ZSTD_compressCCtx(ZSTD_CCtx * cctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize,int compressionLevel)3195 size_t ZSTD_compressCCtx(ZSTD_CCtx* cctx,
3196 void* dst, size_t dstCapacity,
3197 const void* src, size_t srcSize,
3198 int compressionLevel)
3199 {
3200 DEBUGLOG(4, "ZSTD_compressCCtx (srcSize=%u)", (U32)srcSize);
3201 assert(cctx != NULL);
3202 return ZSTD_compress_usingDict(cctx, dst, dstCapacity, src, srcSize, NULL, 0, compressionLevel);
3203 }
3204
ZSTD_compress(void * dst,size_t dstCapacity,const void * src,size_t srcSize,int compressionLevel)3205 size_t ZSTD_compress(void* dst, size_t dstCapacity,
3206 const void* src, size_t srcSize,
3207 int compressionLevel)
3208 {
3209 size_t result;
3210 ZSTD_CCtx ctxBody;
3211 ZSTD_initCCtx(&ctxBody, ZSTD_defaultCMem);
3212 result = ZSTD_compressCCtx(&ctxBody, dst, dstCapacity, src, srcSize, compressionLevel);
3213 ZSTD_freeCCtxContent(&ctxBody); /* can't free ctxBody itself, as it's on stack; free only heap content */
3214 return result;
3215 }
3216
3217
3218 /* ===== Dictionary API ===== */
3219
3220 /*! ZSTD_estimateCDictSize_advanced() :
3221 * Estimate amount of memory that will be needed to create a dictionary with following arguments */
ZSTD_estimateCDictSize_advanced(size_t dictSize,ZSTD_compressionParameters cParams,ZSTD_dictLoadMethod_e dictLoadMethod)3222 size_t ZSTD_estimateCDictSize_advanced(
3223 size_t dictSize, ZSTD_compressionParameters cParams,
3224 ZSTD_dictLoadMethod_e dictLoadMethod)
3225 {
3226 DEBUGLOG(5, "sizeof(ZSTD_CDict) : %u", (U32)sizeof(ZSTD_CDict));
3227 return sizeof(ZSTD_CDict) + HUF_WORKSPACE_SIZE + ZSTD_sizeof_matchState(&cParams, /* forCCtx */ 0)
3228 + (dictLoadMethod == ZSTD_dlm_byRef ? 0 : dictSize);
3229 }
3230
ZSTD_estimateCDictSize(size_t dictSize,int compressionLevel)3231 size_t ZSTD_estimateCDictSize(size_t dictSize, int compressionLevel)
3232 {
3233 ZSTD_compressionParameters const cParams = ZSTD_getCParams(compressionLevel, 0, dictSize);
3234 return ZSTD_estimateCDictSize_advanced(dictSize, cParams, ZSTD_dlm_byCopy);
3235 }
3236
ZSTD_sizeof_CDict(const ZSTD_CDict * cdict)3237 size_t ZSTD_sizeof_CDict(const ZSTD_CDict* cdict)
3238 {
3239 if (cdict==NULL) return 0; /* support sizeof on NULL */
3240 DEBUGLOG(5, "sizeof(*cdict) : %u", (U32)sizeof(*cdict));
3241 return cdict->workspaceSize + (cdict->dictBuffer ? cdict->dictContentSize : 0) + sizeof(*cdict);
3242 }
3243
ZSTD_initCDict_internal(ZSTD_CDict * cdict,const void * dictBuffer,size_t dictSize,ZSTD_dictLoadMethod_e dictLoadMethod,ZSTD_dictContentType_e dictContentType,ZSTD_compressionParameters cParams)3244 static size_t ZSTD_initCDict_internal(
3245 ZSTD_CDict* cdict,
3246 const void* dictBuffer, size_t dictSize,
3247 ZSTD_dictLoadMethod_e dictLoadMethod,
3248 ZSTD_dictContentType_e dictContentType,
3249 ZSTD_compressionParameters cParams)
3250 {
3251 DEBUGLOG(3, "ZSTD_initCDict_internal (dictContentType:%u)", (U32)dictContentType);
3252 assert(!ZSTD_checkCParams(cParams));
3253 cdict->matchState.cParams = cParams;
3254 if ((dictLoadMethod == ZSTD_dlm_byRef) || (!dictBuffer) || (!dictSize)) {
3255 cdict->dictBuffer = NULL;
3256 cdict->dictContent = dictBuffer;
3257 } else {
3258 void* const internalBuffer = ZSTD_malloc(dictSize, cdict->customMem);
3259 cdict->dictBuffer = internalBuffer;
3260 cdict->dictContent = internalBuffer;
3261 if (!internalBuffer) return ERROR(memory_allocation);
3262 memcpy(internalBuffer, dictBuffer, dictSize);
3263 }
3264 cdict->dictContentSize = dictSize;
3265
3266 /* Reset the state to no dictionary */
3267 ZSTD_reset_compressedBlockState(&cdict->cBlockState);
3268 { void* const end = ZSTD_reset_matchState(
3269 &cdict->matchState,
3270 (U32*)cdict->workspace + HUF_WORKSPACE_SIZE_U32,
3271 &cParams, ZSTDcrp_continue, /* forCCtx */ 0);
3272 assert(end == (char*)cdict->workspace + cdict->workspaceSize);
3273 (void)end;
3274 }
3275 /* (Maybe) load the dictionary
3276 * Skips loading the dictionary if it is <= 8 bytes.
3277 */
3278 { ZSTD_CCtx_params params;
3279 memset(¶ms, 0, sizeof(params));
3280 params.compressionLevel = ZSTD_CLEVEL_DEFAULT;
3281 params.fParams.contentSizeFlag = 1;
3282 params.cParams = cParams;
3283 { size_t const dictID = ZSTD_compress_insertDictionary(
3284 &cdict->cBlockState, &cdict->matchState, ¶ms,
3285 cdict->dictContent, cdict->dictContentSize,
3286 dictContentType, ZSTD_dtlm_full, cdict->workspace);
3287 if (ZSTD_isError(dictID)) return dictID;
3288 assert(dictID <= (size_t)(U32)-1);
3289 cdict->dictID = (U32)dictID;
3290 }
3291 }
3292
3293 return 0;
3294 }
3295
ZSTD_createCDict_advanced(const void * dictBuffer,size_t dictSize,ZSTD_dictLoadMethod_e dictLoadMethod,ZSTD_dictContentType_e dictContentType,ZSTD_compressionParameters cParams,ZSTD_customMem customMem)3296 ZSTD_CDict* ZSTD_createCDict_advanced(const void* dictBuffer, size_t dictSize,
3297 ZSTD_dictLoadMethod_e dictLoadMethod,
3298 ZSTD_dictContentType_e dictContentType,
3299 ZSTD_compressionParameters cParams, ZSTD_customMem customMem)
3300 {
3301 DEBUGLOG(3, "ZSTD_createCDict_advanced, mode %u", (U32)dictContentType);
3302 if (!customMem.customAlloc ^ !customMem.customFree) return NULL;
3303
3304 { ZSTD_CDict* const cdict = (ZSTD_CDict*)ZSTD_malloc(sizeof(ZSTD_CDict), customMem);
3305 size_t const workspaceSize = HUF_WORKSPACE_SIZE + ZSTD_sizeof_matchState(&cParams, /* forCCtx */ 0);
3306 void* const workspace = ZSTD_malloc(workspaceSize, customMem);
3307
3308 if (!cdict || !workspace) {
3309 ZSTD_free(cdict, customMem);
3310 ZSTD_free(workspace, customMem);
3311 return NULL;
3312 }
3313 cdict->customMem = customMem;
3314 cdict->workspace = workspace;
3315 cdict->workspaceSize = workspaceSize;
3316 if (ZSTD_isError( ZSTD_initCDict_internal(cdict,
3317 dictBuffer, dictSize,
3318 dictLoadMethod, dictContentType,
3319 cParams) )) {
3320 ZSTD_freeCDict(cdict);
3321 return NULL;
3322 }
3323
3324 return cdict;
3325 }
3326 }
3327
ZSTD_createCDict(const void * dict,size_t dictSize,int compressionLevel)3328 ZSTD_CDict* ZSTD_createCDict(const void* dict, size_t dictSize, int compressionLevel)
3329 {
3330 ZSTD_compressionParameters cParams = ZSTD_getCParams(compressionLevel, 0, dictSize);
3331 return ZSTD_createCDict_advanced(dict, dictSize,
3332 ZSTD_dlm_byCopy, ZSTD_dct_auto,
3333 cParams, ZSTD_defaultCMem);
3334 }
3335
ZSTD_createCDict_byReference(const void * dict,size_t dictSize,int compressionLevel)3336 ZSTD_CDict* ZSTD_createCDict_byReference(const void* dict, size_t dictSize, int compressionLevel)
3337 {
3338 ZSTD_compressionParameters cParams = ZSTD_getCParams(compressionLevel, 0, dictSize);
3339 return ZSTD_createCDict_advanced(dict, dictSize,
3340 ZSTD_dlm_byRef, ZSTD_dct_auto,
3341 cParams, ZSTD_defaultCMem);
3342 }
3343
ZSTD_freeCDict(ZSTD_CDict * cdict)3344 size_t ZSTD_freeCDict(ZSTD_CDict* cdict)
3345 {
3346 if (cdict==NULL) return 0; /* support free on NULL */
3347 { ZSTD_customMem const cMem = cdict->customMem;
3348 ZSTD_free(cdict->workspace, cMem);
3349 ZSTD_free(cdict->dictBuffer, cMem);
3350 ZSTD_free(cdict, cMem);
3351 return 0;
3352 }
3353 }
3354
3355 /*! ZSTD_initStaticCDict_advanced() :
3356 * Generate a digested dictionary in provided memory area.
3357 * workspace: The memory area to emplace the dictionary into.
3358 * Provided pointer must 8-bytes aligned.
3359 * It must outlive dictionary usage.
3360 * workspaceSize: Use ZSTD_estimateCDictSize()
3361 * to determine how large workspace must be.
3362 * cParams : use ZSTD_getCParams() to transform a compression level
3363 * into its relevants cParams.
3364 * @return : pointer to ZSTD_CDict*, or NULL if error (size too small)
3365 * Note : there is no corresponding "free" function.
3366 * Since workspace was allocated externally, it must be freed externally.
3367 */
ZSTD_initStaticCDict(void * workspace,size_t workspaceSize,const void * dict,size_t dictSize,ZSTD_dictLoadMethod_e dictLoadMethod,ZSTD_dictContentType_e dictContentType,ZSTD_compressionParameters cParams)3368 const ZSTD_CDict* ZSTD_initStaticCDict(
3369 void* workspace, size_t workspaceSize,
3370 const void* dict, size_t dictSize,
3371 ZSTD_dictLoadMethod_e dictLoadMethod,
3372 ZSTD_dictContentType_e dictContentType,
3373 ZSTD_compressionParameters cParams)
3374 {
3375 size_t const matchStateSize = ZSTD_sizeof_matchState(&cParams, /* forCCtx */ 0);
3376 size_t const neededSize = sizeof(ZSTD_CDict) + (dictLoadMethod == ZSTD_dlm_byRef ? 0 : dictSize)
3377 + HUF_WORKSPACE_SIZE + matchStateSize;
3378 ZSTD_CDict* const cdict = (ZSTD_CDict*) workspace;
3379 void* ptr;
3380 if ((size_t)workspace & 7) return NULL; /* 8-aligned */
3381 DEBUGLOG(4, "(workspaceSize < neededSize) : (%u < %u) => %u",
3382 (U32)workspaceSize, (U32)neededSize, (U32)(workspaceSize < neededSize));
3383 if (workspaceSize < neededSize) return NULL;
3384
3385 if (dictLoadMethod == ZSTD_dlm_byCopy) {
3386 memcpy(cdict+1, dict, dictSize);
3387 dict = cdict+1;
3388 ptr = (char*)workspace + sizeof(ZSTD_CDict) + dictSize;
3389 } else {
3390 ptr = cdict+1;
3391 }
3392 cdict->workspace = ptr;
3393 cdict->workspaceSize = HUF_WORKSPACE_SIZE + matchStateSize;
3394
3395 if (ZSTD_isError( ZSTD_initCDict_internal(cdict,
3396 dict, dictSize,
3397 ZSTD_dlm_byRef, dictContentType,
3398 cParams) ))
3399 return NULL;
3400
3401 return cdict;
3402 }
3403
ZSTD_getCParamsFromCDict(const ZSTD_CDict * cdict)3404 ZSTD_compressionParameters ZSTD_getCParamsFromCDict(const ZSTD_CDict* cdict)
3405 {
3406 assert(cdict != NULL);
3407 return cdict->matchState.cParams;
3408 }
3409
3410 /* ZSTD_compressBegin_usingCDict_advanced() :
3411 * cdict must be != NULL */
ZSTD_compressBegin_usingCDict_advanced(ZSTD_CCtx * const cctx,const ZSTD_CDict * const cdict,ZSTD_frameParameters const fParams,unsigned long long const pledgedSrcSize)3412 size_t ZSTD_compressBegin_usingCDict_advanced(
3413 ZSTD_CCtx* const cctx, const ZSTD_CDict* const cdict,
3414 ZSTD_frameParameters const fParams, unsigned long long const pledgedSrcSize)
3415 {
3416 DEBUGLOG(4, "ZSTD_compressBegin_usingCDict_advanced");
3417 if (cdict==NULL) return ERROR(dictionary_wrong);
3418 { ZSTD_CCtx_params params = cctx->requestedParams;
3419 params.cParams = ZSTD_getCParamsFromCDict(cdict);
3420 /* Increase window log to fit the entire dictionary and source if the
3421 * source size is known. Limit the increase to 19, which is the
3422 * window log for compression level 1 with the largest source size.
3423 */
3424 if (pledgedSrcSize != ZSTD_CONTENTSIZE_UNKNOWN) {
3425 U32 const limitedSrcSize = (U32)MIN(pledgedSrcSize, 1U << 19);
3426 U32 const limitedSrcLog = limitedSrcSize > 1 ? ZSTD_highbit32(limitedSrcSize - 1) + 1 : 1;
3427 params.cParams.windowLog = MAX(params.cParams.windowLog, limitedSrcLog);
3428 }
3429 params.fParams = fParams;
3430 return ZSTD_compressBegin_internal(cctx,
3431 NULL, 0, ZSTD_dct_auto, ZSTD_dtlm_fast,
3432 cdict,
3433 params, pledgedSrcSize,
3434 ZSTDb_not_buffered);
3435 }
3436 }
3437
3438 /* ZSTD_compressBegin_usingCDict() :
3439 * pledgedSrcSize=0 means "unknown"
3440 * if pledgedSrcSize>0, it will enable contentSizeFlag */
ZSTD_compressBegin_usingCDict(ZSTD_CCtx * cctx,const ZSTD_CDict * cdict)3441 size_t ZSTD_compressBegin_usingCDict(ZSTD_CCtx* cctx, const ZSTD_CDict* cdict)
3442 {
3443 ZSTD_frameParameters const fParams = { 0 /*content*/, 0 /*checksum*/, 0 /*noDictID*/ };
3444 DEBUGLOG(4, "ZSTD_compressBegin_usingCDict : dictIDFlag == %u", !fParams.noDictIDFlag);
3445 return ZSTD_compressBegin_usingCDict_advanced(cctx, cdict, fParams, ZSTD_CONTENTSIZE_UNKNOWN);
3446 }
3447
ZSTD_compress_usingCDict_advanced(ZSTD_CCtx * cctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize,const ZSTD_CDict * cdict,ZSTD_frameParameters fParams)3448 size_t ZSTD_compress_usingCDict_advanced(ZSTD_CCtx* cctx,
3449 void* dst, size_t dstCapacity,
3450 const void* src, size_t srcSize,
3451 const ZSTD_CDict* cdict, ZSTD_frameParameters fParams)
3452 {
3453 CHECK_F (ZSTD_compressBegin_usingCDict_advanced(cctx, cdict, fParams, srcSize)); /* will check if cdict != NULL */
3454 return ZSTD_compressEnd(cctx, dst, dstCapacity, src, srcSize);
3455 }
3456
3457 /*! ZSTD_compress_usingCDict() :
3458 * Compression using a digested Dictionary.
3459 * Faster startup than ZSTD_compress_usingDict(), recommended when same dictionary is used multiple times.
3460 * Note that compression parameters are decided at CDict creation time
3461 * while frame parameters are hardcoded */
ZSTD_compress_usingCDict(ZSTD_CCtx * cctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize,const ZSTD_CDict * cdict)3462 size_t ZSTD_compress_usingCDict(ZSTD_CCtx* cctx,
3463 void* dst, size_t dstCapacity,
3464 const void* src, size_t srcSize,
3465 const ZSTD_CDict* cdict)
3466 {
3467 ZSTD_frameParameters const fParams = { 1 /*content*/, 0 /*checksum*/, 0 /*noDictID*/ };
3468 return ZSTD_compress_usingCDict_advanced(cctx, dst, dstCapacity, src, srcSize, cdict, fParams);
3469 }
3470
3471
3472
3473 /* ******************************************************************
3474 * Streaming
3475 ********************************************************************/
3476
ZSTD_createCStream(void)3477 ZSTD_CStream* ZSTD_createCStream(void)
3478 {
3479 DEBUGLOG(3, "ZSTD_createCStream");
3480 return ZSTD_createCStream_advanced(ZSTD_defaultCMem);
3481 }
3482
ZSTD_initStaticCStream(void * workspace,size_t workspaceSize)3483 ZSTD_CStream* ZSTD_initStaticCStream(void *workspace, size_t workspaceSize)
3484 {
3485 return ZSTD_initStaticCCtx(workspace, workspaceSize);
3486 }
3487
ZSTD_createCStream_advanced(ZSTD_customMem customMem)3488 ZSTD_CStream* ZSTD_createCStream_advanced(ZSTD_customMem customMem)
3489 { /* CStream and CCtx are now same object */
3490 return ZSTD_createCCtx_advanced(customMem);
3491 }
3492
ZSTD_freeCStream(ZSTD_CStream * zcs)3493 size_t ZSTD_freeCStream(ZSTD_CStream* zcs)
3494 {
3495 return ZSTD_freeCCtx(zcs); /* same object */
3496 }
3497
3498
3499
3500 /*====== Initialization ======*/
3501
ZSTD_CStreamInSize(void)3502 size_t ZSTD_CStreamInSize(void) { return ZSTD_BLOCKSIZE_MAX; }
3503
ZSTD_CStreamOutSize(void)3504 size_t ZSTD_CStreamOutSize(void)
3505 {
3506 return ZSTD_compressBound(ZSTD_BLOCKSIZE_MAX) + ZSTD_blockHeaderSize + 4 /* 32-bits hash */ ;
3507 }
3508
ZSTD_resetCStream_internal(ZSTD_CStream * cctx,const void * const dict,size_t const dictSize,ZSTD_dictContentType_e const dictContentType,const ZSTD_CDict * const cdict,ZSTD_CCtx_params params,unsigned long long const pledgedSrcSize)3509 static size_t ZSTD_resetCStream_internal(ZSTD_CStream* cctx,
3510 const void* const dict, size_t const dictSize, ZSTD_dictContentType_e const dictContentType,
3511 const ZSTD_CDict* const cdict,
3512 ZSTD_CCtx_params params, unsigned long long const pledgedSrcSize)
3513 {
3514 DEBUGLOG(4, "ZSTD_resetCStream_internal");
3515 /* Finalize the compression parameters */
3516 params.cParams = ZSTD_getCParamsFromCCtxParams(¶ms, pledgedSrcSize, dictSize);
3517 /* params are supposed to be fully validated at this point */
3518 assert(!ZSTD_isError(ZSTD_checkCParams(params.cParams)));
3519 assert(!((dict) && (cdict))); /* either dict or cdict, not both */
3520
3521 CHECK_F( ZSTD_compressBegin_internal(cctx,
3522 dict, dictSize, dictContentType, ZSTD_dtlm_fast,
3523 cdict,
3524 params, pledgedSrcSize,
3525 ZSTDb_buffered) );
3526
3527 cctx->inToCompress = 0;
3528 cctx->inBuffPos = 0;
3529 cctx->inBuffTarget = cctx->blockSize
3530 + (cctx->blockSize == pledgedSrcSize); /* for small input: avoid automatic flush on reaching end of block, since it would require to add a 3-bytes null block to end frame */
3531 cctx->outBuffContentSize = cctx->outBuffFlushedSize = 0;
3532 cctx->streamStage = zcss_load;
3533 cctx->frameEnded = 0;
3534 return 0; /* ready to go */
3535 }
3536
3537 /* ZSTD_resetCStream():
3538 * pledgedSrcSize == 0 means "unknown" */
ZSTD_resetCStream(ZSTD_CStream * zcs,unsigned long long pledgedSrcSize)3539 size_t ZSTD_resetCStream(ZSTD_CStream* zcs, unsigned long long pledgedSrcSize)
3540 {
3541 ZSTD_CCtx_params params = zcs->requestedParams;
3542 DEBUGLOG(4, "ZSTD_resetCStream: pledgedSrcSize = %u", (U32)pledgedSrcSize);
3543 if (pledgedSrcSize==0) pledgedSrcSize = ZSTD_CONTENTSIZE_UNKNOWN;
3544 params.fParams.contentSizeFlag = 1;
3545 return ZSTD_resetCStream_internal(zcs, NULL, 0, ZSTD_dct_auto, zcs->cdict, params, pledgedSrcSize);
3546 }
3547
3548 /*! ZSTD_initCStream_internal() :
3549 * Note : for lib/compress only. Used by zstdmt_compress.c.
3550 * Assumption 1 : params are valid
3551 * Assumption 2 : either dict, or cdict, is defined, not both */
ZSTD_initCStream_internal(ZSTD_CStream * zcs,const void * dict,size_t dictSize,const ZSTD_CDict * cdict,ZSTD_CCtx_params params,unsigned long long pledgedSrcSize)3552 size_t ZSTD_initCStream_internal(ZSTD_CStream* zcs,
3553 const void* dict, size_t dictSize, const ZSTD_CDict* cdict,
3554 ZSTD_CCtx_params params, unsigned long long pledgedSrcSize)
3555 {
3556 DEBUGLOG(4, "ZSTD_initCStream_internal");
3557 params.cParams = ZSTD_getCParamsFromCCtxParams(¶ms, pledgedSrcSize, dictSize);
3558 assert(!ZSTD_isError(ZSTD_checkCParams(params.cParams)));
3559 assert(!((dict) && (cdict))); /* either dict or cdict, not both */
3560
3561 if (dict && dictSize >= 8) {
3562 DEBUGLOG(4, "loading dictionary of size %u", (U32)dictSize);
3563 if (zcs->staticSize) { /* static CCtx : never uses malloc */
3564 /* incompatible with internal cdict creation */
3565 return ERROR(memory_allocation);
3566 }
3567 ZSTD_freeCDict(zcs->cdictLocal);
3568 zcs->cdictLocal = ZSTD_createCDict_advanced(dict, dictSize,
3569 ZSTD_dlm_byCopy, ZSTD_dct_auto,
3570 params.cParams, zcs->customMem);
3571 zcs->cdict = zcs->cdictLocal;
3572 if (zcs->cdictLocal == NULL) return ERROR(memory_allocation);
3573 } else {
3574 if (cdict) {
3575 params.cParams = ZSTD_getCParamsFromCDict(cdict); /* cParams are enforced from cdict; it includes windowLog */
3576 }
3577 ZSTD_freeCDict(zcs->cdictLocal);
3578 zcs->cdictLocal = NULL;
3579 zcs->cdict = cdict;
3580 }
3581
3582 return ZSTD_resetCStream_internal(zcs, NULL, 0, ZSTD_dct_auto, zcs->cdict, params, pledgedSrcSize);
3583 }
3584
3585 /* ZSTD_initCStream_usingCDict_advanced() :
3586 * same as ZSTD_initCStream_usingCDict(), with control over frame parameters */
ZSTD_initCStream_usingCDict_advanced(ZSTD_CStream * zcs,const ZSTD_CDict * cdict,ZSTD_frameParameters fParams,unsigned long long pledgedSrcSize)3587 size_t ZSTD_initCStream_usingCDict_advanced(ZSTD_CStream* zcs,
3588 const ZSTD_CDict* cdict,
3589 ZSTD_frameParameters fParams,
3590 unsigned long long pledgedSrcSize)
3591 {
3592 DEBUGLOG(4, "ZSTD_initCStream_usingCDict_advanced");
3593 if (!cdict) return ERROR(dictionary_wrong); /* cannot handle NULL cdict (does not know what to do) */
3594 { ZSTD_CCtx_params params = zcs->requestedParams;
3595 params.cParams = ZSTD_getCParamsFromCDict(cdict);
3596 params.fParams = fParams;
3597 return ZSTD_initCStream_internal(zcs,
3598 NULL, 0, cdict,
3599 params, pledgedSrcSize);
3600 }
3601 }
3602
3603 /* note : cdict must outlive compression session */
ZSTD_initCStream_usingCDict(ZSTD_CStream * zcs,const ZSTD_CDict * cdict)3604 size_t ZSTD_initCStream_usingCDict(ZSTD_CStream* zcs, const ZSTD_CDict* cdict)
3605 {
3606 ZSTD_frameParameters const fParams = { 0 /* contentSizeFlag */, 0 /* checksum */, 0 /* hideDictID */ };
3607 DEBUGLOG(4, "ZSTD_initCStream_usingCDict");
3608 return ZSTD_initCStream_usingCDict_advanced(zcs, cdict, fParams, ZSTD_CONTENTSIZE_UNKNOWN); /* note : will check that cdict != NULL */
3609 }
3610
3611
3612 /* ZSTD_initCStream_advanced() :
3613 * pledgedSrcSize must be exact.
3614 * if srcSize is not known at init time, use value ZSTD_CONTENTSIZE_UNKNOWN.
3615 * dict is loaded with default parameters ZSTD_dm_auto and ZSTD_dlm_byCopy. */
ZSTD_initCStream_advanced(ZSTD_CStream * zcs,const void * dict,size_t dictSize,ZSTD_parameters params,unsigned long long pledgedSrcSize)3616 size_t ZSTD_initCStream_advanced(ZSTD_CStream* zcs,
3617 const void* dict, size_t dictSize,
3618 ZSTD_parameters params, unsigned long long pledgedSrcSize)
3619 {
3620 DEBUGLOG(4, "ZSTD_initCStream_advanced: pledgedSrcSize=%u, flag=%u",
3621 (U32)pledgedSrcSize, params.fParams.contentSizeFlag);
3622 CHECK_F( ZSTD_checkCParams(params.cParams) );
3623 if ((pledgedSrcSize==0) && (params.fParams.contentSizeFlag==0)) pledgedSrcSize = ZSTD_CONTENTSIZE_UNKNOWN; /* for compatibility with older programs relying on this behavior. Users should now specify ZSTD_CONTENTSIZE_UNKNOWN. This line will be removed in the future. */
3624 zcs->requestedParams = ZSTD_assignParamsToCCtxParams(zcs->requestedParams, params);
3625 return ZSTD_initCStream_internal(zcs, dict, dictSize, NULL /*cdict*/, zcs->requestedParams, pledgedSrcSize);
3626 }
3627
ZSTD_initCStream_usingDict(ZSTD_CStream * zcs,const void * dict,size_t dictSize,int compressionLevel)3628 size_t ZSTD_initCStream_usingDict(ZSTD_CStream* zcs, const void* dict, size_t dictSize, int compressionLevel)
3629 {
3630 ZSTD_CCtxParams_init(&zcs->requestedParams, compressionLevel);
3631 return ZSTD_initCStream_internal(zcs, dict, dictSize, NULL, zcs->requestedParams, ZSTD_CONTENTSIZE_UNKNOWN);
3632 }
3633
ZSTD_initCStream_srcSize(ZSTD_CStream * zcs,int compressionLevel,unsigned long long pss)3634 size_t ZSTD_initCStream_srcSize(ZSTD_CStream* zcs, int compressionLevel, unsigned long long pss)
3635 {
3636 U64 const pledgedSrcSize = (pss==0) ? ZSTD_CONTENTSIZE_UNKNOWN : pss; /* temporary : 0 interpreted as "unknown" during transition period. Users willing to specify "unknown" **must** use ZSTD_CONTENTSIZE_UNKNOWN. `0` will be interpreted as "empty" in the future */
3637 ZSTD_CCtxParams_init(&zcs->requestedParams, compressionLevel);
3638 return ZSTD_initCStream_internal(zcs, NULL, 0, NULL, zcs->requestedParams, pledgedSrcSize);
3639 }
3640
ZSTD_initCStream(ZSTD_CStream * zcs,int compressionLevel)3641 size_t ZSTD_initCStream(ZSTD_CStream* zcs, int compressionLevel)
3642 {
3643 DEBUGLOG(4, "ZSTD_initCStream");
3644 return ZSTD_initCStream_srcSize(zcs, compressionLevel, ZSTD_CONTENTSIZE_UNKNOWN);
3645 }
3646
3647 /*====== Compression ======*/
3648
ZSTD_limitCopy(void * dst,size_t dstCapacity,const void * src,size_t srcSize)3649 MEM_STATIC size_t ZSTD_limitCopy(void* dst, size_t dstCapacity,
3650 const void* src, size_t srcSize)
3651 {
3652 size_t const length = MIN(dstCapacity, srcSize);
3653 if (length) memcpy(dst, src, length);
3654 return length;
3655 }
3656
3657 /** ZSTD_compressStream_generic():
3658 * internal function for all *compressStream*() variants and *compress_generic()
3659 * non-static, because can be called from zstdmt_compress.c
3660 * @return : hint size for next input */
ZSTD_compressStream_generic(ZSTD_CStream * zcs,ZSTD_outBuffer * output,ZSTD_inBuffer * input,ZSTD_EndDirective const flushMode)3661 size_t ZSTD_compressStream_generic(ZSTD_CStream* zcs,
3662 ZSTD_outBuffer* output,
3663 ZSTD_inBuffer* input,
3664 ZSTD_EndDirective const flushMode)
3665 {
3666 const char* const istart = (const char*)input->src;
3667 const char* const iend = istart + input->size;
3668 const char* ip = istart + input->pos;
3669 char* const ostart = (char*)output->dst;
3670 char* const oend = ostart + output->size;
3671 char* op = ostart + output->pos;
3672 U32 someMoreWork = 1;
3673
3674 /* check expectations */
3675 DEBUGLOG(5, "ZSTD_compressStream_generic, flush=%u", (U32)flushMode);
3676 assert(zcs->inBuff != NULL);
3677 assert(zcs->inBuffSize > 0);
3678 assert(zcs->outBuff != NULL);
3679 assert(zcs->outBuffSize > 0);
3680 assert(output->pos <= output->size);
3681 assert(input->pos <= input->size);
3682
3683 while (someMoreWork) {
3684 switch(zcs->streamStage)
3685 {
3686 case zcss_init:
3687 /* call ZSTD_initCStream() first ! */
3688 return ERROR(init_missing);
3689
3690 case zcss_load:
3691 if ( (flushMode == ZSTD_e_end)
3692 && ((size_t)(oend-op) >= ZSTD_compressBound(iend-ip)) /* enough dstCapacity */
3693 && (zcs->inBuffPos == 0) ) {
3694 /* shortcut to compression pass directly into output buffer */
3695 size_t const cSize = ZSTD_compressEnd(zcs,
3696 op, oend-op, ip, iend-ip);
3697 DEBUGLOG(4, "ZSTD_compressEnd : %u", (U32)cSize);
3698 if (ZSTD_isError(cSize)) return cSize;
3699 ip = iend;
3700 op += cSize;
3701 zcs->frameEnded = 1;
3702 ZSTD_CCtx_reset(zcs);
3703 someMoreWork = 0; break;
3704 }
3705 /* complete loading into inBuffer */
3706 { size_t const toLoad = zcs->inBuffTarget - zcs->inBuffPos;
3707 size_t const loaded = ZSTD_limitCopy(
3708 zcs->inBuff + zcs->inBuffPos, toLoad,
3709 ip, iend-ip);
3710 zcs->inBuffPos += loaded;
3711 ip += loaded;
3712 if ( (flushMode == ZSTD_e_continue)
3713 && (zcs->inBuffPos < zcs->inBuffTarget) ) {
3714 /* not enough input to fill full block : stop here */
3715 someMoreWork = 0; break;
3716 }
3717 if ( (flushMode == ZSTD_e_flush)
3718 && (zcs->inBuffPos == zcs->inToCompress) ) {
3719 /* empty */
3720 someMoreWork = 0; break;
3721 }
3722 }
3723 /* compress current block (note : this stage cannot be stopped in the middle) */
3724 DEBUGLOG(5, "stream compression stage (flushMode==%u)", flushMode);
3725 { void* cDst;
3726 size_t cSize;
3727 size_t const iSize = zcs->inBuffPos - zcs->inToCompress;
3728 size_t oSize = oend-op;
3729 unsigned const lastBlock = (flushMode == ZSTD_e_end) && (ip==iend);
3730 if (oSize >= ZSTD_compressBound(iSize))
3731 cDst = op; /* compress into output buffer, to skip flush stage */
3732 else
3733 cDst = zcs->outBuff, oSize = zcs->outBuffSize;
3734 cSize = lastBlock ?
3735 ZSTD_compressEnd(zcs, cDst, oSize,
3736 zcs->inBuff + zcs->inToCompress, iSize) :
3737 ZSTD_compressContinue(zcs, cDst, oSize,
3738 zcs->inBuff + zcs->inToCompress, iSize);
3739 if (ZSTD_isError(cSize)) return cSize;
3740 zcs->frameEnded = lastBlock;
3741 /* prepare next block */
3742 zcs->inBuffTarget = zcs->inBuffPos + zcs->blockSize;
3743 if (zcs->inBuffTarget > zcs->inBuffSize)
3744 zcs->inBuffPos = 0, zcs->inBuffTarget = zcs->blockSize;
3745 DEBUGLOG(5, "inBuffTarget:%u / inBuffSize:%u",
3746 (U32)zcs->inBuffTarget, (U32)zcs->inBuffSize);
3747 if (!lastBlock)
3748 assert(zcs->inBuffTarget <= zcs->inBuffSize);
3749 zcs->inToCompress = zcs->inBuffPos;
3750 if (cDst == op) { /* no need to flush */
3751 op += cSize;
3752 if (zcs->frameEnded) {
3753 DEBUGLOG(5, "Frame completed directly in outBuffer");
3754 someMoreWork = 0;
3755 ZSTD_CCtx_reset(zcs);
3756 }
3757 break;
3758 }
3759 zcs->outBuffContentSize = cSize;
3760 zcs->outBuffFlushedSize = 0;
3761 zcs->streamStage = zcss_flush; /* pass-through to flush stage */
3762 }
3763 /* fall-through */
3764 case zcss_flush:
3765 DEBUGLOG(5, "flush stage");
3766 { size_t const toFlush = zcs->outBuffContentSize - zcs->outBuffFlushedSize;
3767 size_t const flushed = ZSTD_limitCopy(op, oend-op,
3768 zcs->outBuff + zcs->outBuffFlushedSize, toFlush);
3769 DEBUGLOG(5, "toFlush: %u into %u ==> flushed: %u",
3770 (U32)toFlush, (U32)(oend-op), (U32)flushed);
3771 op += flushed;
3772 zcs->outBuffFlushedSize += flushed;
3773 if (toFlush!=flushed) {
3774 /* flush not fully completed, presumably because dst is too small */
3775 assert(op==oend);
3776 someMoreWork = 0;
3777 break;
3778 }
3779 zcs->outBuffContentSize = zcs->outBuffFlushedSize = 0;
3780 if (zcs->frameEnded) {
3781 DEBUGLOG(5, "Frame completed on flush");
3782 someMoreWork = 0;
3783 ZSTD_CCtx_reset(zcs);
3784 break;
3785 }
3786 zcs->streamStage = zcss_load;
3787 break;
3788 }
3789
3790 default: /* impossible */
3791 assert(0);
3792 }
3793 }
3794
3795 input->pos = ip - istart;
3796 output->pos = op - ostart;
3797 if (zcs->frameEnded) return 0;
3798 { size_t hintInSize = zcs->inBuffTarget - zcs->inBuffPos;
3799 if (hintInSize==0) hintInSize = zcs->blockSize;
3800 return hintInSize;
3801 }
3802 }
3803
ZSTD_compressStream(ZSTD_CStream * zcs,ZSTD_outBuffer * output,ZSTD_inBuffer * input)3804 size_t ZSTD_compressStream(ZSTD_CStream* zcs, ZSTD_outBuffer* output, ZSTD_inBuffer* input)
3805 {
3806 /* check conditions */
3807 if (output->pos > output->size) return ERROR(GENERIC);
3808 if (input->pos > input->size) return ERROR(GENERIC);
3809
3810 return ZSTD_compressStream_generic(zcs, output, input, ZSTD_e_continue);
3811 }
3812
3813
ZSTD_compress_generic(ZSTD_CCtx * cctx,ZSTD_outBuffer * output,ZSTD_inBuffer * input,ZSTD_EndDirective endOp)3814 size_t ZSTD_compress_generic (ZSTD_CCtx* cctx,
3815 ZSTD_outBuffer* output,
3816 ZSTD_inBuffer* input,
3817 ZSTD_EndDirective endOp)
3818 {
3819 DEBUGLOG(5, "ZSTD_compress_generic, endOp=%u ", (U32)endOp);
3820 /* check conditions */
3821 if (output->pos > output->size) return ERROR(GENERIC);
3822 if (input->pos > input->size) return ERROR(GENERIC);
3823 assert(cctx!=NULL);
3824
3825 /* transparent initialization stage */
3826 if (cctx->streamStage == zcss_init) {
3827 ZSTD_CCtx_params params = cctx->requestedParams;
3828 ZSTD_prefixDict const prefixDict = cctx->prefixDict;
3829 memset(&cctx->prefixDict, 0, sizeof(cctx->prefixDict)); /* single usage */
3830 assert(prefixDict.dict==NULL || cctx->cdict==NULL); /* only one can be set */
3831 DEBUGLOG(4, "ZSTD_compress_generic : transparent init stage");
3832 if (endOp == ZSTD_e_end) cctx->pledgedSrcSizePlusOne = input->size + 1; /* auto-fix pledgedSrcSize */
3833 params.cParams = ZSTD_getCParamsFromCCtxParams(
3834 &cctx->requestedParams, cctx->pledgedSrcSizePlusOne-1, 0 /*dictSize*/);
3835
3836
3837 #ifdef ZSTD_MULTITHREAD
3838 if ((cctx->pledgedSrcSizePlusOne-1) <= ZSTDMT_JOBSIZE_MIN) {
3839 params.nbWorkers = 0; /* do not invoke multi-threading when src size is too small */
3840 }
3841 if (params.nbWorkers > 0) {
3842 /* mt context creation */
3843 if (cctx->mtctx == NULL) {
3844 DEBUGLOG(4, "ZSTD_compress_generic: creating new mtctx for nbWorkers=%u",
3845 params.nbWorkers);
3846 cctx->mtctx = ZSTDMT_createCCtx_advanced(params.nbWorkers, cctx->customMem);
3847 if (cctx->mtctx == NULL) return ERROR(memory_allocation);
3848 }
3849 /* mt compression */
3850 DEBUGLOG(4, "call ZSTDMT_initCStream_internal as nbWorkers=%u", params.nbWorkers);
3851 CHECK_F( ZSTDMT_initCStream_internal(
3852 cctx->mtctx,
3853 prefixDict.dict, prefixDict.dictSize, ZSTD_dct_rawContent,
3854 cctx->cdict, params, cctx->pledgedSrcSizePlusOne-1) );
3855 cctx->streamStage = zcss_load;
3856 cctx->appliedParams.nbWorkers = params.nbWorkers;
3857 } else
3858 #endif
3859 { CHECK_F( ZSTD_resetCStream_internal(cctx,
3860 prefixDict.dict, prefixDict.dictSize, prefixDict.dictContentType,
3861 cctx->cdict,
3862 params, cctx->pledgedSrcSizePlusOne-1) );
3863 assert(cctx->streamStage == zcss_load);
3864 assert(cctx->appliedParams.nbWorkers == 0);
3865 } }
3866
3867 /* compression stage */
3868 #ifdef ZSTD_MULTITHREAD
3869 if (cctx->appliedParams.nbWorkers > 0) {
3870 if (cctx->cParamsChanged) {
3871 ZSTDMT_updateCParams_whileCompressing(cctx->mtctx, &cctx->requestedParams);
3872 cctx->cParamsChanged = 0;
3873 }
3874 { size_t const flushMin = ZSTDMT_compressStream_generic(cctx->mtctx, output, input, endOp);
3875 if ( ZSTD_isError(flushMin)
3876 || (endOp == ZSTD_e_end && flushMin == 0) ) { /* compression completed */
3877 ZSTD_CCtx_reset(cctx);
3878 }
3879 DEBUGLOG(5, "completed ZSTD_compress_generic delegating to ZSTDMT_compressStream_generic");
3880 return flushMin;
3881 } }
3882 #endif
3883 CHECK_F( ZSTD_compressStream_generic(cctx, output, input, endOp) );
3884 DEBUGLOG(5, "completed ZSTD_compress_generic");
3885 return cctx->outBuffContentSize - cctx->outBuffFlushedSize; /* remaining to flush */
3886 }
3887
ZSTD_compress_generic_simpleArgs(ZSTD_CCtx * cctx,void * dst,size_t dstCapacity,size_t * dstPos,const void * src,size_t srcSize,size_t * srcPos,ZSTD_EndDirective endOp)3888 size_t ZSTD_compress_generic_simpleArgs (
3889 ZSTD_CCtx* cctx,
3890 void* dst, size_t dstCapacity, size_t* dstPos,
3891 const void* src, size_t srcSize, size_t* srcPos,
3892 ZSTD_EndDirective endOp)
3893 {
3894 ZSTD_outBuffer output = { dst, dstCapacity, *dstPos };
3895 ZSTD_inBuffer input = { src, srcSize, *srcPos };
3896 /* ZSTD_compress_generic() will check validity of dstPos and srcPos */
3897 size_t const cErr = ZSTD_compress_generic(cctx, &output, &input, endOp);
3898 *dstPos = output.pos;
3899 *srcPos = input.pos;
3900 return cErr;
3901 }
3902
3903
3904 /*====== Finalize ======*/
3905
3906 /*! ZSTD_flushStream() :
3907 * @return : amount of data remaining to flush */
ZSTD_flushStream(ZSTD_CStream * zcs,ZSTD_outBuffer * output)3908 size_t ZSTD_flushStream(ZSTD_CStream* zcs, ZSTD_outBuffer* output)
3909 {
3910 ZSTD_inBuffer input = { NULL, 0, 0 };
3911 if (output->pos > output->size) return ERROR(GENERIC);
3912 CHECK_F( ZSTD_compressStream_generic(zcs, output, &input, ZSTD_e_flush) );
3913 return zcs->outBuffContentSize - zcs->outBuffFlushedSize; /* remaining to flush */
3914 }
3915
3916
ZSTD_endStream(ZSTD_CStream * zcs,ZSTD_outBuffer * output)3917 size_t ZSTD_endStream(ZSTD_CStream* zcs, ZSTD_outBuffer* output)
3918 {
3919 ZSTD_inBuffer input = { NULL, 0, 0 };
3920 if (output->pos > output->size) return ERROR(GENERIC);
3921 CHECK_F( ZSTD_compressStream_generic(zcs, output, &input, ZSTD_e_end) );
3922 { size_t const lastBlockSize = zcs->frameEnded ? 0 : ZSTD_BLOCKHEADERSIZE;
3923 size_t const checksumSize = zcs->frameEnded ? 0 : zcs->appliedParams.fParams.checksumFlag * 4;
3924 size_t const toFlush = zcs->outBuffContentSize - zcs->outBuffFlushedSize + lastBlockSize + checksumSize;
3925 DEBUGLOG(4, "ZSTD_endStream : remaining to flush : %u", (U32)toFlush);
3926 return toFlush;
3927 }
3928 }
3929
3930
3931 /*-===== Pre-defined compression levels =====-*/
3932
3933 #define ZSTD_MAX_CLEVEL 22
ZSTD_maxCLevel(void)3934 int ZSTD_maxCLevel(void) { return ZSTD_MAX_CLEVEL; }
ZSTD_minCLevel(void)3935 int ZSTD_minCLevel(void) { return (int)-ZSTD_TARGETLENGTH_MAX; }
3936
3937 static const ZSTD_compressionParameters ZSTD_defaultCParameters[4][ZSTD_MAX_CLEVEL+1] = {
3938 { /* "default" - guarantees a monotonically increasing memory budget */
3939 /* W, C, H, S, L, TL, strat */
3940 { 19, 12, 13, 1, 6, 1, ZSTD_fast }, /* base for negative levels */
3941 { 19, 13, 14, 1, 7, 0, ZSTD_fast }, /* level 1 */
3942 { 19, 15, 16, 1, 6, 0, ZSTD_fast }, /* level 2 */
3943 { 20, 16, 17, 1, 5, 1, ZSTD_dfast }, /* level 3 */
3944 { 20, 18, 18, 1, 5, 1, ZSTD_dfast }, /* level 4 */
3945 { 20, 18, 18, 2, 5, 2, ZSTD_greedy }, /* level 5 */
3946 { 21, 18, 19, 2, 5, 4, ZSTD_lazy }, /* level 6 */
3947 { 21, 18, 19, 3, 5, 8, ZSTD_lazy2 }, /* level 7 */
3948 { 21, 19, 19, 3, 5, 16, ZSTD_lazy2 }, /* level 8 */
3949 { 21, 19, 20, 4, 5, 16, ZSTD_lazy2 }, /* level 9 */
3950 { 21, 20, 21, 4, 5, 16, ZSTD_lazy2 }, /* level 10 */
3951 { 21, 21, 22, 4, 5, 16, ZSTD_lazy2 }, /* level 11 */
3952 { 22, 20, 22, 5, 5, 16, ZSTD_lazy2 }, /* level 12 */
3953 { 22, 21, 22, 4, 5, 32, ZSTD_btlazy2 }, /* level 13 */
3954 { 22, 21, 22, 5, 5, 32, ZSTD_btlazy2 }, /* level 14 */
3955 { 22, 22, 22, 6, 5, 32, ZSTD_btlazy2 }, /* level 15 */
3956 { 22, 21, 22, 4, 5, 48, ZSTD_btopt }, /* level 16 */
3957 { 23, 22, 22, 4, 4, 64, ZSTD_btopt }, /* level 17 */
3958 { 23, 23, 22, 6, 3,256, ZSTD_btopt }, /* level 18 */
3959 { 23, 24, 22, 7, 3,256, ZSTD_btultra }, /* level 19 */
3960 { 25, 25, 23, 7, 3,256, ZSTD_btultra }, /* level 20 */
3961 { 26, 26, 24, 7, 3,512, ZSTD_btultra }, /* level 21 */
3962 { 27, 27, 25, 9, 3,999, ZSTD_btultra }, /* level 22 */
3963 },
3964 { /* for srcSize <= 256 KB */
3965 /* W, C, H, S, L, T, strat */
3966 { 18, 12, 13, 1, 5, 1, ZSTD_fast }, /* base for negative levels */
3967 { 18, 13, 14, 1, 6, 0, ZSTD_fast }, /* level 1 */
3968 { 18, 14, 14, 1, 5, 1, ZSTD_dfast }, /* level 2 */
3969 { 18, 16, 16, 1, 4, 1, ZSTD_dfast }, /* level 3 */
3970 { 18, 16, 17, 2, 5, 2, ZSTD_greedy }, /* level 4.*/
3971 { 18, 18, 18, 3, 5, 2, ZSTD_greedy }, /* level 5.*/
3972 { 18, 18, 19, 3, 5, 4, ZSTD_lazy }, /* level 6.*/
3973 { 18, 18, 19, 4, 4, 4, ZSTD_lazy }, /* level 7 */
3974 { 18, 18, 19, 4, 4, 8, ZSTD_lazy2 }, /* level 8 */
3975 { 18, 18, 19, 5, 4, 8, ZSTD_lazy2 }, /* level 9 */
3976 { 18, 18, 19, 6, 4, 8, ZSTD_lazy2 }, /* level 10 */
3977 { 18, 18, 19, 5, 4, 16, ZSTD_btlazy2 }, /* level 11.*/
3978 { 18, 19, 19, 6, 4, 16, ZSTD_btlazy2 }, /* level 12.*/
3979 { 18, 19, 19, 8, 4, 16, ZSTD_btlazy2 }, /* level 13 */
3980 { 18, 18, 19, 4, 4, 24, ZSTD_btopt }, /* level 14.*/
3981 { 18, 18, 19, 4, 3, 24, ZSTD_btopt }, /* level 15.*/
3982 { 18, 19, 19, 6, 3, 64, ZSTD_btopt }, /* level 16.*/
3983 { 18, 19, 19, 8, 3,128, ZSTD_btopt }, /* level 17.*/
3984 { 18, 19, 19, 10, 3,256, ZSTD_btopt }, /* level 18.*/
3985 { 18, 19, 19, 10, 3,256, ZSTD_btultra }, /* level 19.*/
3986 { 18, 19, 19, 11, 3,512, ZSTD_btultra }, /* level 20.*/
3987 { 18, 19, 19, 12, 3,512, ZSTD_btultra }, /* level 21.*/
3988 { 18, 19, 19, 13, 3,999, ZSTD_btultra }, /* level 22.*/
3989 },
3990 { /* for srcSize <= 128 KB */
3991 /* W, C, H, S, L, T, strat */
3992 { 17, 12, 12, 1, 5, 1, ZSTD_fast }, /* base for negative levels */
3993 { 17, 12, 13, 1, 6, 0, ZSTD_fast }, /* level 1 */
3994 { 17, 13, 15, 1, 5, 0, ZSTD_fast }, /* level 2 */
3995 { 17, 15, 16, 2, 5, 1, ZSTD_dfast }, /* level 3 */
3996 { 17, 17, 17, 2, 4, 1, ZSTD_dfast }, /* level 4 */
3997 { 17, 16, 17, 3, 4, 2, ZSTD_greedy }, /* level 5 */
3998 { 17, 17, 17, 3, 4, 4, ZSTD_lazy }, /* level 6 */
3999 { 17, 17, 17, 3, 4, 8, ZSTD_lazy2 }, /* level 7 */
4000 { 17, 17, 17, 4, 4, 8, ZSTD_lazy2 }, /* level 8 */
4001 { 17, 17, 17, 5, 4, 8, ZSTD_lazy2 }, /* level 9 */
4002 { 17, 17, 17, 6, 4, 8, ZSTD_lazy2 }, /* level 10 */
4003 { 17, 17, 17, 7, 4, 8, ZSTD_lazy2 }, /* level 11 */
4004 { 17, 18, 17, 6, 4, 16, ZSTD_btlazy2 }, /* level 12 */
4005 { 17, 18, 17, 8, 4, 16, ZSTD_btlazy2 }, /* level 13.*/
4006 { 17, 18, 17, 4, 4, 32, ZSTD_btopt }, /* level 14.*/
4007 { 17, 18, 17, 6, 3, 64, ZSTD_btopt }, /* level 15.*/
4008 { 17, 18, 17, 7, 3,128, ZSTD_btopt }, /* level 16.*/
4009 { 17, 18, 17, 7, 3,256, ZSTD_btopt }, /* level 17.*/
4010 { 17, 18, 17, 8, 3,256, ZSTD_btopt }, /* level 18.*/
4011 { 17, 18, 17, 8, 3,256, ZSTD_btultra }, /* level 19.*/
4012 { 17, 18, 17, 9, 3,256, ZSTD_btultra }, /* level 20.*/
4013 { 17, 18, 17, 10, 3,256, ZSTD_btultra }, /* level 21.*/
4014 { 17, 18, 17, 11, 3,512, ZSTD_btultra }, /* level 22.*/
4015 },
4016 { /* for srcSize <= 16 KB */
4017 /* W, C, H, S, L, T, strat */
4018 { 14, 12, 13, 1, 5, 1, ZSTD_fast }, /* base for negative levels */
4019 { 14, 14, 15, 1, 5, 0, ZSTD_fast }, /* level 1 */
4020 { 14, 14, 15, 1, 4, 0, ZSTD_fast }, /* level 2 */
4021 { 14, 14, 14, 2, 4, 1, ZSTD_dfast }, /* level 3.*/
4022 { 14, 14, 14, 4, 4, 2, ZSTD_greedy }, /* level 4.*/
4023 { 14, 14, 14, 3, 4, 4, ZSTD_lazy }, /* level 5.*/
4024 { 14, 14, 14, 4, 4, 8, ZSTD_lazy2 }, /* level 6 */
4025 { 14, 14, 14, 6, 4, 8, ZSTD_lazy2 }, /* level 7 */
4026 { 14, 14, 14, 8, 4, 8, ZSTD_lazy2 }, /* level 8.*/
4027 { 14, 15, 14, 5, 4, 8, ZSTD_btlazy2 }, /* level 9.*/
4028 { 14, 15, 14, 9, 4, 8, ZSTD_btlazy2 }, /* level 10.*/
4029 { 14, 15, 14, 3, 4, 12, ZSTD_btopt }, /* level 11.*/
4030 { 14, 15, 14, 6, 3, 16, ZSTD_btopt }, /* level 12.*/
4031 { 14, 15, 14, 6, 3, 24, ZSTD_btopt }, /* level 13.*/
4032 { 14, 15, 15, 6, 3, 48, ZSTD_btopt }, /* level 14.*/
4033 { 14, 15, 15, 6, 3, 64, ZSTD_btopt }, /* level 15.*/
4034 { 14, 15, 15, 6, 3, 96, ZSTD_btopt }, /* level 16.*/
4035 { 14, 15, 15, 6, 3,128, ZSTD_btopt }, /* level 17.*/
4036 { 14, 15, 15, 8, 3,256, ZSTD_btopt }, /* level 18.*/
4037 { 14, 15, 15, 6, 3,256, ZSTD_btultra }, /* level 19.*/
4038 { 14, 15, 15, 8, 3,256, ZSTD_btultra }, /* level 20.*/
4039 { 14, 15, 15, 9, 3,256, ZSTD_btultra }, /* level 21.*/
4040 { 14, 15, 15, 10, 3,512, ZSTD_btultra }, /* level 22.*/
4041 },
4042 };
4043
4044 /*! ZSTD_getCParams() :
4045 * @return ZSTD_compressionParameters structure for a selected compression level, srcSize and dictSize.
4046 * Size values are optional, provide 0 if not known or unused */
ZSTD_getCParams(int compressionLevel,unsigned long long srcSizeHint,size_t dictSize)4047 ZSTD_compressionParameters ZSTD_getCParams(int compressionLevel, unsigned long long srcSizeHint, size_t dictSize)
4048 {
4049 size_t const addedSize = srcSizeHint ? 0 : 500;
4050 U64 const rSize = srcSizeHint+dictSize ? srcSizeHint+dictSize+addedSize : (U64)-1;
4051 U32 const tableID = (rSize <= 256 KB) + (rSize <= 128 KB) + (rSize <= 16 KB); /* intentional underflow for srcSizeHint == 0 */
4052 int row = compressionLevel;
4053 DEBUGLOG(5, "ZSTD_getCParams (cLevel=%i)", compressionLevel);
4054 if (compressionLevel == 0) row = ZSTD_CLEVEL_DEFAULT; /* 0 == default */
4055 if (compressionLevel < 0) row = 0; /* entry 0 is baseline for fast mode */
4056 if (compressionLevel > ZSTD_MAX_CLEVEL) row = ZSTD_MAX_CLEVEL;
4057 { ZSTD_compressionParameters cp = ZSTD_defaultCParameters[tableID][row];
4058 if (compressionLevel < 0) cp.targetLength = (unsigned)(-compressionLevel); /* acceleration factor */
4059 return ZSTD_adjustCParams_internal(cp, srcSizeHint, dictSize); }
4060
4061 }
4062
4063 /*! ZSTD_getParams() :
4064 * same as ZSTD_getCParams(), but @return a `ZSTD_parameters` object (instead of `ZSTD_compressionParameters`).
4065 * All fields of `ZSTD_frameParameters` are set to default (0) */
ZSTD_getParams(int compressionLevel,unsigned long long srcSizeHint,size_t dictSize)4066 ZSTD_parameters ZSTD_getParams(int compressionLevel, unsigned long long srcSizeHint, size_t dictSize) {
4067 ZSTD_parameters params;
4068 ZSTD_compressionParameters const cParams = ZSTD_getCParams(compressionLevel, srcSizeHint, dictSize);
4069 DEBUGLOG(5, "ZSTD_getParams (cLevel=%i)", compressionLevel);
4070 memset(¶ms, 0, sizeof(params));
4071 params.cParams = cParams;
4072 params.fParams.contentSizeFlag = 1;
4073 return params;
4074 }
4075