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