Commit | Line | Data |
---|---|---|
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 | ***************************************/ | |
31 | static const U32 g_searchStrength = 8; /* control skip over incompressible data */ | |
32 | #define HASH_READ_SIZE 8 | |
33 | typedef enum { ZSTDcs_created = 0, ZSTDcs_init, ZSTDcs_ongoing, ZSTDcs_ending } ZSTD_compressionStage_e; | |
34 | ||
35 | /*-************************************* | |
36 | * Helper functions | |
37 | ***************************************/ | |
38 | size_t ZSTD_compressBound(size_t srcSize) { return FSE_compressBound(srcSize) + 12; } | |
39 | ||
40 | /*-************************************* | |
41 | * Sequence storage | |
42 | ***************************************/ | |
43 | static 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 | ***************************************/ | |
53 | struct 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 | ||
90 | size_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 | ||
109 | static 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 | ||
122 | ZSTD_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 | ||
132 | size_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 | ||
141 | const seqStore_t *ZSTD_getSeqStore(const ZSTD_CCtx *ctx) /* hidden interface */ { return &(ctx->seqStore); } | |
142 | ||
143 | static 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 */ | |
148 | size_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 */ | |
168 | static 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. */ | |
180 | ZSTD_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 | ||
209 | static 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) */ | |
217 | static 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 | ||
238 | typedef enum { ZSTDcrp_continue, ZSTDcrp_noMemset, ZSTDcrp_fullReset } ZSTD_compResetPolicy_e; | |
239 | ||
240 | /*! ZSTD_resetCCtx_advanced() : | |
241 | note : `params` must be validated */ | |
242 | static 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 ! */ | |
337 | void 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 */ | |
348 | size_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` */ | |
397 | static 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) */ | |
410 | static 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 | ||
434 | size_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 | ||
443 | static 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 | ||
462 | static 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 | ||
480 | static size_t ZSTD_minGain(size_t srcSize) { return (srcSize >> 6) + 2; } | |
481 | ||
482 | static 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 | ||
553 | static const BYTE LL_Code[64] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 16, 17, 17, 18, 18, | |
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 | ||
557 | static const BYTE ML_Code[128] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, | |
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 | ||
563 | void 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 | ||
586 | ZSTD_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 | ||
832 | ZSTD_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 | */ | |
861 | ZSTD_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 | ***************************************/ | |
890 | static 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 | ||
907 | static 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 | */ | |
940 | static 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 | ***************************************/ | |
952 | static const U32 prime3bytes = 506832829U; | |
953 | static U32 ZSTD_hash3(U32 u, U32 h) { return ((u << (32 - 24)) * prime3bytes) >> (32 - h); } | |
954 | ZSTD_STATIC size_t ZSTD_hash3Ptr(const void *ptr, U32 h) { return ZSTD_hash3(ZSTD_readLE32(ptr), h); } /* only in zstd_opt.h */ | |
955 | ||
956 | static const U32 prime4bytes = 2654435761U; | |
957 | static U32 ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32 - h); } | |
958 | static size_t ZSTD_hash4Ptr(const void *ptr, U32 h) { return ZSTD_hash4(ZSTD_read32(ptr), h); } | |
959 | ||
960 | static const U64 prime5bytes = 889523592379ULL; | |
961 | static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u << (64 - 40)) * prime5bytes) >> (64 - h)); } | |
962 | static size_t ZSTD_hash5Ptr(const void *p, U32 h) { return ZSTD_hash5(ZSTD_readLE64(p), h); } | |
963 | ||
964 | static const U64 prime6bytes = 227718039650203ULL; | |
965 | static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u << (64 - 48)) * prime6bytes) >> (64 - h)); } | |
966 | static size_t ZSTD_hash6Ptr(const void *p, U32 h) { return ZSTD_hash6(ZSTD_readLE64(p), h); } | |
967 | ||
968 | static const U64 prime7bytes = 58295818150454627ULL; | |
969 | static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u << (64 - 56)) * prime7bytes) >> (64 - h)); } | |
970 | static size_t ZSTD_hash7Ptr(const void *p, U32 h) { return ZSTD_hash7(ZSTD_readLE64(p), h); } | |
971 | ||
972 | static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL; | |
973 | static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u)*prime8bytes) >> (64 - h)); } | |
974 | static size_t ZSTD_hash8Ptr(const void *p, U32 h) { return ZSTD_hash8(ZSTD_readLE64(p), h); } | |
975 | ||
976 | static 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 | ***************************************/ | |
992 | static 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 | ||
1007 | FORCE_INLINE | |
1008 | void 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 | ||
1104 | static 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 | ||
1116 | static 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 | ||
1220 | static 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 | ***************************************/ | |
1235 | static 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 | ||
1253 | FORCE_INLINE | |
1254 | void 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 | ||
1383 | static 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 | ||
1395 | static 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 | ||
1543 | static 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 */ | |
1561 | static 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 | ||
1643 | static 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 | ||
1724 | static 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 */ | |
1735 | static size_t ZSTD_BtFindBestMatch(ZSTD_CCtx *zc, const BYTE *const ip, const BYTE *const iLimit, size_t *offsetPtr, const U32 maxNbAttempts, const U32 mls) | |
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 | ||
1743 | static 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 | ||
1755 | static 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 */ | |
1766 | static 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 | ||
1775 | static 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) */ | |
1795 | FORCE_INLINE | |
1796 | U32 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) */ | |
1818 | FORCE_INLINE | |
1819 | size_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 | ||
1869 | FORCE_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 | ||
1881 | FORCE_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 | *********************************/ | |
1896 | FORCE_INLINE | |
1897 | void 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 | ||
2049 | static void ZSTD_compressBlock_btlazy2(ZSTD_CCtx *ctx, const void *src, size_t srcSize) { ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 1, 2); } | |
2050 | ||
2051 | static void ZSTD_compressBlock_lazy2(ZSTD_CCtx *ctx, const void *src, size_t srcSize) { ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 0, 2); } | |
2052 | ||
2053 | static void ZSTD_compressBlock_lazy(ZSTD_CCtx *ctx, const void *src, size_t srcSize) { ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 0, 1); } | |
2054 | ||
2055 | static void ZSTD_compressBlock_greedy(ZSTD_CCtx *ctx, const void *src, size_t srcSize) { ZSTD_compressBlock_lazy_generic(ctx, src, srcSize, 0, 0); } | |
2056 | ||
2057 | FORCE_INLINE | |
2058 | void 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 | ||
2252 | void ZSTD_compressBlock_greedy_extDict(ZSTD_CCtx *ctx, const void *src, size_t srcSize) { ZSTD_compressBlock_lazy_extDict_generic(ctx, src, srcSize, 0, 0); } | |
2253 | ||
2254 | static 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 | ||
2259 | static 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 | ||
2264 | static 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 | ||
2272 | static 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 | ||
2284 | static 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 | ||
2296 | static 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 | ||
2308 | static 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 | ||
2320 | typedef void (*ZSTD_blockCompressor)(ZSTD_CCtx *ctx, const void *src, size_t srcSize); | |
2321 | ||
2322 | static 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 | ||
2333 | static 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 | */ | |
2355 | static 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 | ||
2431 | static 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 | ||
2490 | static 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 | ||
2539 | size_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 | ||
2544 | size_t ZSTD_getBlockSizeMax(ZSTD_CCtx *cctx) { return MIN(ZSTD_BLOCKSIZE_ABSOLUTEMAX, 1 << cctx->params.cParams.windowLog); } | |
2545 | ||
2546 | size_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 | */ | |
2557 | static 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. */ | |
2605 | static 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 | */ | |
2626 | static 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 */ | |
2723 | static 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 */ | |
2738 | static 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 */ | |
2747 | size_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 | ||
2754 | size_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 | ||
2760 | size_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) */ | |
2765 | static 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 | ||
2806 | size_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 | ||
2818 | static size_t ZSTD_compress_internal(ZSTD_CCtx *cctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const void *dict, size_t dictSize, | |
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 | ||
2825 | size_t ZSTD_compress_usingDict(ZSTD_CCtx *ctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const void *dict, size_t dictSize, | |
2826 | ZSTD_parameters params) | |
2827 | { | |
2828 | return ZSTD_compress_internal(ctx, dst, dstCapacity, src, srcSize, dict, dictSize, params); | |
2829 | } | |
2830 | ||
2831 | size_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 | ||
2838 | struct 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 | ||
2845 | size_t ZSTD_CDictWorkspaceBound(ZSTD_compressionParameters cParams) { return ZSTD_CCtxWorkspaceBound(cParams) + ZSTD_ALIGN(sizeof(ZSTD_CDict)); } | |
2846 | ||
2847 | static 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 | ||
2893 | ZSTD_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 | ||
2899 | size_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 | ||
2912 | static ZSTD_parameters ZSTD_getParamsFromCDict(const ZSTD_CDict *cdict) { return ZSTD_getParamsFromCCtx(cdict->refContext); } | |
2913 | ||
2914 | size_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 */ | |
2930 | size_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 | ||
2948 | typedef enum { zcss_init, zcss_load, zcss_flush, zcss_final } ZSTD_cStreamStage; | |
2949 | ||
2950 | struct 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 | ||
2973 | size_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 | ||
2982 | ZSTD_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 | ||
3002 | size_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 | ||
3023 | size_t ZSTD_CStreamInSize(void) { return ZSTD_BLOCKSIZE_ABSOLUTEMAX; } | |
3024 | size_t ZSTD_CStreamOutSize(void) { return ZSTD_compressBound(ZSTD_BLOCKSIZE_ABSOLUTEMAX) + ZSTD_blockHeaderSize + 4 /* 32-bits hash */; } | |
3025 | ||
3026 | static 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 | ||
3047 | size_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 | ||
3055 | static 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 | ||
3092 | ZSTD_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 | ||
3105 | ZSTD_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 | ||
3120 | typedef enum { zsf_gather, zsf_flush, zsf_end } ZSTD_flush_e; | |
3121 | ||
3122 | ZSTD_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 | ||
3129 | static size_t ZSTD_compressStream_generic(ZSTD_CStream *zcs, void *dst, size_t *dstCapacityPtr, const void *src, size_t *srcSizePtr, ZSTD_flush_e const flush) | |
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 | ||
3222 | size_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 */ | |
3237 | size_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 | ||
3250 | size_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 | |
3294 | int ZSTD_maxCLevel(void) { return ZSTD_MAX_CLEVEL; } | |
3295 | ||
3296 | static 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 */ | |
3410 | ZSTD_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) */ | |
3436 | ZSTD_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(¶ms, 0, sizeof(params)); | |
3441 | params.cParams = cParams; | |
3442 | return params; | |
3443 | } | |
3444 | ||
3445 | EXPORT_SYMBOL(ZSTD_maxCLevel); | |
3446 | EXPORT_SYMBOL(ZSTD_compressBound); | |
3447 | ||
3448 | EXPORT_SYMBOL(ZSTD_CCtxWorkspaceBound); | |
3449 | EXPORT_SYMBOL(ZSTD_initCCtx); | |
3450 | EXPORT_SYMBOL(ZSTD_compressCCtx); | |
3451 | EXPORT_SYMBOL(ZSTD_compress_usingDict); | |
3452 | ||
3453 | EXPORT_SYMBOL(ZSTD_CDictWorkspaceBound); | |
3454 | EXPORT_SYMBOL(ZSTD_initCDict); | |
3455 | EXPORT_SYMBOL(ZSTD_compress_usingCDict); | |
3456 | ||
3457 | EXPORT_SYMBOL(ZSTD_CStreamWorkspaceBound); | |
3458 | EXPORT_SYMBOL(ZSTD_initCStream); | |
3459 | EXPORT_SYMBOL(ZSTD_initCStream_usingCDict); | |
3460 | EXPORT_SYMBOL(ZSTD_resetCStream); | |
3461 | EXPORT_SYMBOL(ZSTD_compressStream); | |
3462 | EXPORT_SYMBOL(ZSTD_flushStream); | |
3463 | EXPORT_SYMBOL(ZSTD_endStream); | |
3464 | EXPORT_SYMBOL(ZSTD_CStreamInSize); | |
3465 | EXPORT_SYMBOL(ZSTD_CStreamOutSize); | |
3466 | ||
3467 | EXPORT_SYMBOL(ZSTD_getCParams); | |
3468 | EXPORT_SYMBOL(ZSTD_getParams); | |
3469 | EXPORT_SYMBOL(ZSTD_checkCParams); | |
3470 | EXPORT_SYMBOL(ZSTD_adjustCParams); | |
3471 | ||
3472 | EXPORT_SYMBOL(ZSTD_compressBegin); | |
3473 | EXPORT_SYMBOL(ZSTD_compressBegin_usingDict); | |
3474 | EXPORT_SYMBOL(ZSTD_compressBegin_advanced); | |
3475 | EXPORT_SYMBOL(ZSTD_copyCCtx); | |
3476 | EXPORT_SYMBOL(ZSTD_compressBegin_usingCDict); | |
3477 | EXPORT_SYMBOL(ZSTD_compressContinue); | |
3478 | EXPORT_SYMBOL(ZSTD_compressEnd); | |
3479 | ||
3480 | EXPORT_SYMBOL(ZSTD_getBlockSizeMax); | |
3481 | EXPORT_SYMBOL(ZSTD_compressBlock); | |
3482 | ||
3483 | MODULE_LICENSE("Dual BSD/GPL"); | |
3484 | MODULE_DESCRIPTION("Zstd Compressor"); |