ReactOS 0.4.15-dev-8241-g63935f8
zstd_compress_internal.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2016-2020, Yann Collet, Facebook, Inc.
3 * All rights reserved.
4 *
5 * This source code is licensed under both the BSD-style license (found in the
6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
7 * in the COPYING file in the root directory of this source tree).
8 * You may select, at your option, one of the above-listed licenses.
9 */
10
11/* This header contains definitions
12 * that shall **only** be used by modules within lib/compress.
13 */
14
15#ifndef ZSTD_COMPRESS_H
16#define ZSTD_COMPRESS_H
17
18/*-*************************************
19* Dependencies
20***************************************/
21#include "zstd_internal.h"
22#include "zstd_cwksp.h"
23#ifdef ZSTD_MULTITHREAD
24# include "zstdmt_compress.h"
25#endif
26
27#if defined (__cplusplus)
28extern "C" {
29#endif
30
31
32/*-*************************************
33* Constants
34***************************************/
35#define kSearchStrength 8
36#define HASH_READ_SIZE 8
37#define ZSTD_DUBT_UNSORTED_MARK 1 /* For btlazy2 strategy, index ZSTD_DUBT_UNSORTED_MARK==1 means "unsorted".
38 It could be confused for a real successor at index "1", if sorted as larger than its predecessor.
39 It's not a big deal though : candidate will just be sorted again.
40 Additionally, candidate position 1 will be lost.
41 But candidate 1 cannot hide a large tree of candidates, so it's a minimal loss.
42 The benefit is that ZSTD_DUBT_UNSORTED_MARK cannot be mishandled after table re-use with a different strategy.
43 This constant is required by ZSTD_compressBlock_btlazy2() and ZSTD_reduceTable_internal() */
45
46/*-*************************************
47* Context memory management
48***************************************/
51
52typedef struct ZSTD_prefixDict_s {
53 const void* dict;
54 size_t dictSize;
55 ZSTD_dictContentType_e dictContentType;
58typedef struct {
59 void* dictBuffer;
60 void const* dict;
61 size_t dictSize;
62 ZSTD_dictContentType_e dictContentType;
63 ZSTD_CDict* cdict;
66typedef struct {
67 U32 CTable[HUF_CTABLE_SIZE_U32(255)];
68 HUF_repeat repeatMode;
71typedef struct {
72 FSE_CTable offcodeCTable[FSE_CTABLE_SIZE_U32(OffFSELog, MaxOff)];
73 FSE_CTable matchlengthCTable[FSE_CTABLE_SIZE_U32(MLFSELog, MaxML)];
74 FSE_CTable litlengthCTable[FSE_CTABLE_SIZE_U32(LLFSELog, MaxLL)];
75 FSE_repeat offcode_repeatMode;
76 FSE_repeat matchlength_repeatMode;
77 FSE_repeat litlength_repeatMode;
80typedef struct {
85typedef struct {
90typedef struct {
91 int price;
92 U32 off;
93 U32 mlen;
94 U32 litlen;
95 U32 rep[ZSTD_REP_NUM];
100typedef struct {
101 /* All tables are allocated inside cctx->workspace by ZSTD_resetCCtx_internal() */
102 unsigned* litFreq; /* table of literals statistics, of size 256 */
103 unsigned* litLengthFreq; /* table of litLength statistics, of size (MaxLL+1) */
104 unsigned* matchLengthFreq; /* table of matchLength statistics, of size (MaxML+1) */
105 unsigned* offCodeFreq; /* table of offCode statistics, of size (MaxOff+1) */
106 ZSTD_match_t* matchTable; /* list of found matches, of size ZSTD_OPT_NUM+1 */
107 ZSTD_optimal_t* priceTable; /* All positions tracked by optimal parser, of size ZSTD_OPT_NUM+1 */
109 U32 litSum; /* nb of literals */
110 U32 litLengthSum; /* nb of litLength codes */
111 U32 matchLengthSum; /* nb of matchLength codes */
112 U32 offCodeSum; /* nb of offset codes */
113 U32 litSumBasePrice; /* to compare to log2(litfreq) */
114 U32 litLengthSumBasePrice; /* to compare to log2(llfreq) */
115 U32 matchLengthSumBasePrice;/* to compare to log2(mlfreq) */
116 U32 offCodeSumBasePrice; /* to compare to log2(offreq) */
117 ZSTD_OptPrice_e priceType; /* prices can be determined dynamically, or follow a pre-defined cost structure */
118 const ZSTD_entropyCTables_t* symbolCosts; /* pre-calculated dictionary statistics */
119 ZSTD_literalCompressionMode_e literalCompressionMode;
120} optState_t;
122typedef struct {
127typedef struct {
128 BYTE const* nextSrc; /* next block here to continue on current prefix */
129 BYTE const* base; /* All regular indexes relative to this position */
130 BYTE const* dictBase; /* extDict indexes relative to this position */
131 U32 dictLimit; /* below that point, need extDict */
132 U32 lowLimit; /* below that point, no more valid data */
134
136struct ZSTD_matchState_t {
137 ZSTD_window_t window; /* State for window round buffer management */
138 U32 loadedDictEnd; /* index of end of dictionary, within context's referential.
139 * When loadedDictEnd != 0, a dictionary is in use, and still valid.
140 * This relies on a mechanism to set loadedDictEnd=0 when dictionary is no longer within distance.
141 * Such mechanism is provided within ZSTD_window_enforceMaxDist() and ZSTD_checkDictValidity().
142 * When dict referential is copied into active context (i.e. not attached),
143 * loadedDictEnd == dictSize, since referential starts from zero.
144 */
145 U32 nextToUpdate; /* index from which to continue table update */
146 U32 hashLog3; /* dispatch table for matches of len==3 : larger == faster, more memory */
147 U32* hashTable;
150 optState_t opt; /* optimal parser state */
152 ZSTD_compressionParameters cParams;
153};
154
155typedef struct {
158 ZSTD_matchState_t matchState;
161typedef struct {
166typedef struct {
167 ZSTD_window_t window; /* State for the window round buffer management */
168 ldmEntry_t* hashTable;
169 U32 loadedDictEnd;
170 BYTE* bucketOffsets; /* Next position in bucket to insert entry */
171 U64 hashPower; /* Used to compute the rolling hash.
172 * Depends on ldmParams.minMatchLength */
175typedef struct {
176 U32 enableLdm; /* 1 if enable long distance matching */
177 U32 hashLog; /* Log size of hashTable */
178 U32 bucketSizeLog; /* Log bucket size for collision resolution, at most 8 */
179 U32 minMatchLength; /* Minimum match length */
180 U32 hashRateLog; /* Log number of entries to skip */
181 U32 windowLog; /* Window log for the LDM */
183
184typedef struct {
186 U32 litLength;
187 U32 matchLength;
189
190typedef struct {
191 rawSeq* seq; /* The start of the sequences */
192 size_t pos; /* The position where reading stopped. <= size. */
193 size_t size; /* The number of sequences. <= capacity. */
194 size_t capacity; /* The capacity starting from `seq` pointer */
196
197typedef struct {
198 int collectSequences;
199 ZSTD_Sequence* seqStart;
200 size_t seqIndex;
201 size_t maxSequences;
205 ZSTD_format_e format;
206 ZSTD_compressionParameters cParams;
207 ZSTD_frameParameters fParams;
208
210 int forceWindow; /* force back-references to respect limit of
211 * 1<<wLog, even for dictionary */
212 size_t targetCBlockSize; /* Tries to fit compressed block size to be around targetCBlockSize.
213 * No target when targetCBlockSize == 0.
214 * There is no guarantee on compressed block size */
215 int srcSizeHint; /* User's best guess of source size.
216 * Hint is not valid when srcSizeHint == 0.
217 * There is no guarantee that hint is close to actual source size */
219 ZSTD_dictAttachPref_e attachDictPref;
220 ZSTD_literalCompressionMode_e literalCompressionMode;
221
222 /* Multithreading: used to pass parameters to mtctx */
224 size_t jobSize;
225 int overlapLog;
227
228 /* Long distance matching parameters */
231 /* Internal use, for createCCtxParams() and freeCCtxParams() only */
232 ZSTD_customMem customMem;
233}; /* typedef'd to ZSTD_CCtx_params within "zstd.h" */
237 int cParamsChanged; /* == 1 if cParams(except wlog) or compression level are changed in requestedParams. Triggers transmission of new params to ZSTDMT (if available) then reset to 0. */
238 int bmi2; /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */
239 ZSTD_CCtx_params requestedParams;
240 ZSTD_CCtx_params appliedParams;
243 ZSTD_cwksp workspace; /* manages buffer for dynamic allocations */
244 size_t blockSize;
245 unsigned long long pledgedSrcSizePlusOne; /* this way, 0 (default) == unknown */
246 unsigned long long consumedSrcSize;
247 unsigned long long producedCSize;
249 ZSTD_customMem customMem;
255 seqStore_t seqStore; /* sequences storage ptrs */
256 ldmState_t ldmState; /* long distance matching state */
257 rawSeq* ldmSequences; /* Storage for the ldm output sequences */
259 rawSeqStore_t externSeqStore; /* Mutable reference to external sequences */
261 U32* entropyWorkspace; /* entropy workspace of HUF_WORKSPACE_SIZE bytes */
263 /* streaming */
264 char* inBuff;
267 size_t inBuffPos;
269 char* outBuff;
270 size_t outBuffSize;
275
276 /* Dictionary */
278 const ZSTD_CDict* cdict;
279 ZSTD_prefixDict prefixDict; /* single-usage dictionary */
280
281 /* Multi-threading */
282#ifdef ZSTD_MULTITHREAD
283 ZSTDMT_CCtx* mtctx;
284#endif
285};
288
289typedef enum { ZSTD_noDict = 0, ZSTD_extDict = 1, ZSTD_dictMatchState = 2 } ZSTD_dictMode_e;
290
291
294 void const* src, size_t srcSize);
296
297
298MEM_STATIC U32 ZSTD_LLcode(U32 litLength)
299{
300 static const BYTE LL_Code[64] = { 0, 1, 2, 3, 4, 5, 6, 7,
301 8, 9, 10, 11, 12, 13, 14, 15,
302 16, 16, 17, 17, 18, 18, 19, 19,
303 20, 20, 20, 20, 21, 21, 21, 21,
304 22, 22, 22, 22, 22, 22, 22, 22,
305 23, 23, 23, 23, 23, 23, 23, 23,
306 24, 24, 24, 24, 24, 24, 24, 24,
307 24, 24, 24, 24, 24, 24, 24, 24 };
308 static const U32 LL_deltaCode = 19;
309 return (litLength > 63) ? ZSTD_highbit32(litLength) + LL_deltaCode : LL_Code[litLength];
310}
311
312/* ZSTD_MLcode() :
313 * note : mlBase = matchLength - MINMATCH;
314 * because it's the format it's stored in seqStore->sequences */
316{
317 static const BYTE ML_Code[128] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
318 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
319 32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37,
320 38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39,
321 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
322 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,
323 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
324 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42 };
325 static const U32 ML_deltaCode = 36;
326 return (mlBase > 127) ? ZSTD_highbit32(mlBase) + ML_deltaCode : ML_Code[mlBase];
328
329typedef struct repcodes_s {
330 U32 rep[3];
331} repcodes_t;
332
333MEM_STATIC repcodes_t ZSTD_updateRep(U32 const rep[3], U32 const offset, U32 const ll0)
334{
335 repcodes_t newReps;
336 if (offset >= ZSTD_REP_NUM) { /* full offset */
337 newReps.rep[2] = rep[1];
338 newReps.rep[1] = rep[0];
339 newReps.rep[0] = offset - ZSTD_REP_MOVE;
340 } else { /* repcode */
341 U32 const repCode = offset + ll0;
342 if (repCode > 0) { /* note : if repCode==0, no change */
343 U32 const currentOffset = (repCode==ZSTD_REP_NUM) ? (rep[0] - 1) : rep[repCode];
344 newReps.rep[2] = (repCode >= 2) ? rep[1] : rep[2];
345 newReps.rep[1] = rep[0];
346 newReps.rep[0] = currentOffset;
347 } else { /* repCode == 0 */
348 memcpy(&newReps, rep, sizeof(newReps));
349 }
350 }
351 return newReps;
352}
353
354/* ZSTD_cParam_withinBounds:
355 * @return 1 if value is within cParam bounds,
356 * 0 otherwise */
358{
359 ZSTD_bounds const bounds = ZSTD_cParam_getBounds(cParam);
360 if (ZSTD_isError(bounds.error)) return 0;
361 if (value < bounds.lowerBound) return 0;
362 if (value > bounds.upperBound) return 0;
363 return 1;
364}
365
366/* ZSTD_noCompressBlock() :
367 * Writes uncompressed block to dst buffer from given src.
368 * Returns the size of the block */
369MEM_STATIC size_t ZSTD_noCompressBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize, U32 lastBlock)
370{
371 U32 const cBlockHeader24 = lastBlock + (((U32)bt_raw)<<1) + (U32)(srcSize << 3);
372 RETURN_ERROR_IF(srcSize + ZSTD_blockHeaderSize > dstCapacity,
373 dstSize_tooSmall, "dst buf too small for uncompressed block");
374 MEM_writeLE24(dst, cBlockHeader24);
375 memcpy((BYTE*)dst + ZSTD_blockHeaderSize, src, srcSize);
376 return ZSTD_blockHeaderSize + srcSize;
377}
378
379MEM_STATIC size_t ZSTD_rleCompressBlock (void* dst, size_t dstCapacity, BYTE src, size_t srcSize, U32 lastBlock)
380{
381 BYTE* const op = (BYTE*)dst;
382 U32 const cBlockHeader = lastBlock + (((U32)bt_rle)<<1) + (U32)(srcSize << 3);
383 RETURN_ERROR_IF(dstCapacity < 4, dstSize_tooSmall, "");
384 MEM_writeLE24(op, cBlockHeader);
385 op[3] = src;
386 return 4;
387}
389
390/* ZSTD_minGain() :
391 * minimum compression required
392 * to generate a compress block or a compressed literals section.
393 * note : use same formula for both situations */
394MEM_STATIC size_t ZSTD_minGain(size_t srcSize, ZSTD_strategy strat)
395{
396 U32 const minlog = (strat>=ZSTD_btultra) ? (U32)(strat) - 1 : 6;
399 return (srcSize >> minlog) + 2;
400}
401
402MEM_STATIC int ZSTD_disableLiteralsCompression(const ZSTD_CCtx_params* cctxParams)
403{
404 switch (cctxParams->literalCompressionMode) {
405 case ZSTD_lcm_huffman:
406 return 0;
407 case ZSTD_lcm_uncompressed:
408 return 1;
409 default:
410 assert(0 /* impossible: pre-validated */);
411 /* fall-through */
412 case ZSTD_lcm_auto:
413 return (cctxParams->cParams.strategy == ZSTD_fast) && (cctxParams->cParams.targetLength > 0);
414 }
415}
422static void ZSTD_safecopyLiterals(BYTE* op, BYTE const* ip, BYTE const* const iend, BYTE const* ilimit_w) {
423 assert(iend > ilimit_w);
424 if (ip <= ilimit_w) {
425 ZSTD_wildcopy(op, ip, ilimit_w - ip, ZSTD_no_overlap);
426 op += ilimit_w - ip;
427 ip = ilimit_w;
428 }
429 while (ip < iend) *op++ = *ip++;
430}
431
439void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const BYTE* literals, const BYTE* litLimit, U32 offCode, size_t mlBase)
440{
441 BYTE const* const litLimit_w = litLimit - WILDCOPY_OVERLENGTH;
442 BYTE const* const litEnd = literals + litLength;
443#if defined(DEBUGLEVEL) && (DEBUGLEVEL >= 6)
444 static const BYTE* g_start = NULL;
445 if (g_start==NULL) g_start = (const BYTE*)literals; /* note : index only works for compression within a single segment */
446 { U32 const pos = (U32)((const BYTE*)literals - g_start);
447 DEBUGLOG(6, "Cpos%7u :%3u literals, match%4u bytes at offCode%7u",
448 pos, (U32)litLength, (U32)mlBase+MINMATCH, (U32)offCode);
449 }
450#endif
451 assert((size_t)(seqStorePtr->sequences - seqStorePtr->sequencesStart) < seqStorePtr->maxNbSeq);
452 /* copy Literals */
453 assert(seqStorePtr->maxNbLit <= 128 KB);
454 assert(seqStorePtr->lit + litLength <= seqStorePtr->litStart + seqStorePtr->maxNbLit);
455 assert(literals + litLength <= litLimit);
456 if (litEnd <= litLimit_w) {
457 /* Common case we can use wildcopy.
458 * First copy 16 bytes, because literals are likely short.
459 */
461 ZSTD_copy16(seqStorePtr->lit, literals);
462 if (litLength > 16) {
463 ZSTD_wildcopy(seqStorePtr->lit+16, literals+16, (ptrdiff_t)litLength-16, ZSTD_no_overlap);
464 }
465 } else {
466 ZSTD_safecopyLiterals(seqStorePtr->lit, literals, litEnd, litLimit_w);
467 }
468 seqStorePtr->lit += litLength;
469
470 /* literal Length */
471 if (litLength>0xFFFF) {
472 assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
473 seqStorePtr->longLengthID = 1;
474 seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
475 }
476 seqStorePtr->sequences[0].litLength = (U16)litLength;
477
478 /* match offset */
479 seqStorePtr->sequences[0].offset = offCode + 1;
480
481 /* match Length */
482 if (mlBase>0xFFFF) {
483 assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
484 seqStorePtr->longLengthID = 2;
485 seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
486 }
487 seqStorePtr->sequences[0].matchLength = (U16)mlBase;
488
489 seqStorePtr->sequences++;
491
492
493/*-*************************************
494* Match length counter
495***************************************/
496static unsigned ZSTD_NbCommonBytes (size_t val)
497{
498 if (MEM_isLittleEndian()) {
499 if (MEM_64bits()) {
500# if defined(_MSC_VER) && defined(_WIN64)
501 unsigned long r = 0;
502 return _BitScanForward64( &r, (U64)val ) ? (unsigned)(r >> 3) : 0;
503# elif defined(__GNUC__) && (__GNUC__ >= 4)
504 return (__builtin_ctzll((U64)val) >> 3);
505# else
506 static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2,
507 0, 3, 1, 3, 1, 4, 2, 7,
508 0, 2, 3, 6, 1, 5, 3, 5,
509 1, 3, 4, 4, 2, 5, 6, 7,
510 7, 0, 1, 2, 3, 3, 4, 6,
511 2, 6, 5, 5, 3, 4, 5, 6,
512 7, 1, 2, 4, 6, 4, 4, 5,
513 7, 2, 6, 5, 7, 6, 7, 7 };
514 return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
515# endif
516 } else { /* 32 bits */
517# if defined(_MSC_VER)
518 unsigned long r=0;
519 return _BitScanForward( &r, (U32)val ) ? (unsigned)(r >> 3) : 0;
520# elif defined(__GNUC__) && (__GNUC__ >= 3)
521 return (__builtin_ctz((U32)val) >> 3);
522# else
523 static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0,
524 3, 2, 2, 1, 3, 2, 0, 1,
525 3, 3, 1, 2, 2, 2, 2, 0,
526 3, 1, 2, 0, 1, 0, 1, 1 };
527 return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
528# endif
529 }
530 } else { /* Big Endian CPU */
531 if (MEM_64bits()) {
532# if defined(_MSC_VER) && defined(_WIN64)
533 unsigned long r = 0;
534 return _BitScanReverse64( &r, val ) ? (unsigned)(r >> 3) : 0;
535# elif defined(__GNUC__) && (__GNUC__ >= 4)
536 return (__builtin_clzll(val) >> 3);
537# else
538 unsigned r;
539 const unsigned n32 = sizeof(size_t)*4; /* calculate this way due to compiler complaining in 32-bits mode */
540 if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }
541 if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
542 r += (!val);
543 return r;
544# endif
545 } else { /* 32 bits */
546# if defined(_MSC_VER)
547 unsigned long r = 0;
548 return _BitScanReverse( &r, (unsigned long)val ) ? (unsigned)(r >> 3) : 0;
549# elif defined(__GNUC__) && (__GNUC__ >= 3)
550 return (__builtin_clz((U32)val) >> 3);
551# else
552 unsigned r;
553 if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
554 r += (!val);
555 return r;
556# endif
557 } }
558}
559
560
561MEM_STATIC size_t ZSTD_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* const pInLimit)
562{
563 const BYTE* const pStart = pIn;
564 const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1);
565
566 if (pIn < pInLoopLimit) {
567 { size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
568 if (diff) return ZSTD_NbCommonBytes(diff); }
569 pIn+=sizeof(size_t); pMatch+=sizeof(size_t);
570 while (pIn < pInLoopLimit) {
571 size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
572 if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; }
573 pIn += ZSTD_NbCommonBytes(diff);
574 return (size_t)(pIn - pStart);
575 } }
576 if (MEM_64bits() && (pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatch+=4; }
577 if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; }
578 if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;
579 return (size_t)(pIn - pStart);
580}
586MEM_STATIC size_t
587ZSTD_count_2segments(const BYTE* ip, const BYTE* match,
588 const BYTE* iEnd, const BYTE* mEnd, const BYTE* iStart)
589{
590 const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd);
591 size_t const matchLength = ZSTD_count(ip, match, vEnd);
592 if (match + matchLength != mEnd) return matchLength;
593 DEBUGLOG(7, "ZSTD_count_2segments: found a 2-parts match (current length==%zu)", matchLength);
594 DEBUGLOG(7, "distance from match beginning to end dictionary = %zi", mEnd - match);
595 DEBUGLOG(7, "distance from current pos to end buffer = %zi", iEnd - ip);
596 DEBUGLOG(7, "next byte : ip==%02X, istart==%02X", ip[matchLength], *iStart);
597 DEBUGLOG(7, "final match length = %zu", matchLength + ZSTD_count(ip+matchLength, iStart, iEnd));
598 return matchLength + ZSTD_count(ip+matchLength, iStart, iEnd);
602/*-*************************************
603 * Hashes
604 ***************************************/
605static const U32 prime3bytes = 506832829U;
606static U32 ZSTD_hash3(U32 u, U32 h) { return ((u << (32-24)) * prime3bytes) >> (32-h) ; }
607MEM_STATIC size_t ZSTD_hash3Ptr(const void* ptr, U32 h) { return ZSTD_hash3(MEM_readLE32(ptr), h); } /* only in zstd_opt.h */
609static const U32 prime4bytes = 2654435761U;
610static U32 ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32-h) ; }
611static size_t ZSTD_hash4Ptr(const void* ptr, U32 h) { return ZSTD_hash4(MEM_read32(ptr), h); }
613static const U64 prime5bytes = 889523592379ULL;
614static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u << (64-40)) * prime5bytes) >> (64-h)) ; }
615static size_t ZSTD_hash5Ptr(const void* p, U32 h) { return ZSTD_hash5(MEM_readLE64(p), h); }
617static const U64 prime6bytes = 227718039650203ULL;
618static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u << (64-48)) * prime6bytes) >> (64-h)) ; }
619static size_t ZSTD_hash6Ptr(const void* p, U32 h) { return ZSTD_hash6(MEM_readLE64(p), h); }
621static const U64 prime7bytes = 58295818150454627ULL;
622static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u << (64-56)) * prime7bytes) >> (64-h)) ; }
623static size_t ZSTD_hash7Ptr(const void* p, U32 h) { return ZSTD_hash7(MEM_readLE64(p), h); }
624
625static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL;
626static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; }
627static size_t ZSTD_hash8Ptr(const void* p, U32 h) { return ZSTD_hash8(MEM_readLE64(p), h); }
628
629MEM_STATIC size_t ZSTD_hashPtr(const void* p, U32 hBits, U32 mls)
630{
631 switch(mls)
632 {
633 default:
634 case 4: return ZSTD_hash4Ptr(p, hBits);
635 case 5: return ZSTD_hash5Ptr(p, hBits);
636 case 6: return ZSTD_hash6Ptr(p, hBits);
637 case 7: return ZSTD_hash7Ptr(p, hBits);
638 case 8: return ZSTD_hash8Ptr(p, hBits);
640}
641
645static U64 ZSTD_ipow(U64 base, U64 exponent)
646{
647 U64 power = 1;
648 while (exponent) {
649 if (exponent & 1) power *= base;
650 exponent >>= 1;
651 base *= base;
652 }
653 return power;
654}
656#define ZSTD_ROLL_HASH_CHAR_OFFSET 10
657
661static U64 ZSTD_rollingHash_append(U64 hash, void const* buf, size_t size)
662{
663 BYTE const* istart = (BYTE const*)buf;
664 size_t pos;
665 for (pos = 0; pos < size; ++pos) {
666 hash *= prime8bytes;
668 }
669 return hash;
670}
671
676{
677 return ZSTD_rollingHash_append(0, buf, size);
679
685{
687}
688
692MEM_STATIC U64 ZSTD_rollingHash_rotate(U64 hash, BYTE toRemove, BYTE toAdd, U64 primePower)
693{
694 hash -= (toRemove + ZSTD_ROLL_HASH_CHAR_OFFSET) * primePower;
695 hash *= prime8bytes;
697 return hash;
698}
699
700/*-*************************************
701* Round buffer management
702***************************************/
703#if (ZSTD_WINDOWLOG_MAX_64 > 31)
704# error "ZSTD_WINDOWLOG_MAX is too large : would overflow ZSTD_CURRENT_MAX"
705#endif
706/* Max current allowed */
707#define ZSTD_CURRENT_MAX ((3U << 29) + (1U << ZSTD_WINDOWLOG_MAX))
708/* Maximum chunk size before overflow correction needs to be called again */
709#define ZSTD_CHUNKSIZE_MAX \
710 ( ((U32)-1) /* Maximum ending current index */ \
711 - ZSTD_CURRENT_MAX) /* Maximum beginning lowLimit */
712
718{
719 size_t const endT = (size_t)(window->nextSrc - window->base);
720 U32 const end = (U32)endT;
721
722 window->lowLimit = end;
723 window->dictLimit = end;
725
731{
732 return window.lowLimit < window.dictLimit;
733}
741{
742 return ZSTD_window_hasExtDict(ms->window) ?
744 ms->dictMatchState != NULL ?
747}
755 void const* srcEnd)
756{
757 U32 const current = (U32)((BYTE const*)srcEnd - window.base);
758 return current > ZSTD_CURRENT_MAX;
759}
760
772 U32 maxDist, void const* src)
773{
774 /* preemptive overflow correction:
775 * 1. correction is large enough:
776 * lowLimit > (3<<29) ==> current > 3<<29 + 1<<windowLog
777 * 1<<windowLog <= newCurrent < 1<<chainLog + 1<<windowLog
778 *
779 * current - newCurrent
780 * > (3<<29 + 1<<windowLog) - (1<<windowLog + 1<<chainLog)
781 * > (3<<29) - (1<<chainLog)
782 * > (3<<29) - (1<<30) (NOTE: chainLog <= 30)
783 * > 1<<29
784 *
785 * 2. (ip+ZSTD_CHUNKSIZE_MAX - cctx->base) doesn't overflow:
786 * After correction, current is less than (1<<chainLog + 1<<windowLog).
787 * In 64-bit mode we are safe, because we have 64-bit ptrdiff_t.
788 * In 32-bit mode we are safe, because (chainLog <= 29), so
789 * ip+ZSTD_CHUNKSIZE_MAX - cctx->base < 1<<32.
790 * 3. (cctx->lowLimit + 1<<windowLog) < 1<<32:
791 * windowLog <= 31 ==> 3<<29 + 1<<windowLog < 7<<29 < 1<<32.
792 */
793 U32 const cycleMask = (1U << cycleLog) - 1;
794 U32 const current = (U32)((BYTE const*)src - window->base);
795 U32 const currentCycle0 = current & cycleMask;
796 /* Exclude zero so that newCurrent - maxDist >= 1. */
797 U32 const currentCycle1 = currentCycle0 == 0 ? (1U << cycleLog) : currentCycle0;
798 U32 const newCurrent = currentCycle1 + maxDist;
799 U32 const correction = current - newCurrent;
800 assert((maxDist & cycleMask) == 0);
801 assert(current > newCurrent);
802 /* Loose bound, should be around 1<<29 (see above) */
803 assert(correction > 1<<28);
804
805 window->base += correction;
806 window->dictBase += correction;
807 if (window->lowLimit <= correction) window->lowLimit = 1;
808 else window->lowLimit -= correction;
809 if (window->dictLimit <= correction) window->dictLimit = 1;
810 else window->dictLimit -= correction;
811
812 /* Ensure we can still reference the full window. */
813 assert(newCurrent >= maxDist);
814 assert(newCurrent - maxDist >= 1);
815 /* Ensure that lowLimit and dictLimit didn't underflow. */
816 assert(window->lowLimit <= newCurrent);
817 assert(window->dictLimit <= newCurrent);
818
819 DEBUGLOG(4, "Correction of 0x%x bytes to lowLimit=0x%x", correction,
820 window->lowLimit);
821 return correction;
822}
823
847MEM_STATIC void
849 const void* blockEnd,
850 U32 maxDist,
851 U32* loadedDictEndPtr,
852 const ZSTD_matchState_t** dictMatchStatePtr)
853{
854 U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base);
855 U32 const loadedDictEnd = (loadedDictEndPtr != NULL) ? *loadedDictEndPtr : 0;
856 DEBUGLOG(5, "ZSTD_window_enforceMaxDist: blockEndIdx=%u, maxDist=%u, loadedDictEnd=%u",
857 (unsigned)blockEndIdx, (unsigned)maxDist, (unsigned)loadedDictEnd);
858
859 /* - When there is no dictionary : loadedDictEnd == 0.
860 In which case, the test (blockEndIdx > maxDist) is merely to avoid
861 overflowing next operation `newLowLimit = blockEndIdx - maxDist`.
862 - When there is a standard dictionary :
863 Index referential is copied from the dictionary,
864 which means it starts from 0.
865 In which case, loadedDictEnd == dictSize,
866 and it makes sense to compare `blockEndIdx > maxDist + dictSize`
867 since `blockEndIdx` also starts from zero.
868 - When there is an attached dictionary :
869 loadedDictEnd is expressed within the referential of the context,
870 so it can be directly compared against blockEndIdx.
871 */
872 if (blockEndIdx > maxDist + loadedDictEnd) {
873 U32 const newLowLimit = blockEndIdx - maxDist;
874 if (window->lowLimit < newLowLimit) window->lowLimit = newLowLimit;
875 if (window->dictLimit < window->lowLimit) {
876 DEBUGLOG(5, "Update dictLimit to match lowLimit, from %u to %u",
877 (unsigned)window->dictLimit, (unsigned)window->lowLimit);
878 window->dictLimit = window->lowLimit;
879 }
880 /* On reaching window size, dictionaries are invalidated */
881 if (loadedDictEndPtr) *loadedDictEndPtr = 0;
882 if (dictMatchStatePtr) *dictMatchStatePtr = NULL;
883 }
884}
885
886/* Similar to ZSTD_window_enforceMaxDist(),
887 * but only invalidates dictionary
888 * when input progresses beyond window size.
889 * assumption : loadedDictEndPtr and dictMatchStatePtr are valid (non NULL)
890 * loadedDictEnd uses same referential as window->base
891 * maxDist is the window size */
892MEM_STATIC void
894 const void* blockEnd,
895 U32 maxDist,
896 U32* loadedDictEndPtr,
897 const ZSTD_matchState_t** dictMatchStatePtr)
898{
899 assert(loadedDictEndPtr != NULL);
900 assert(dictMatchStatePtr != NULL);
901 { U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base);
902 U32 const loadedDictEnd = *loadedDictEndPtr;
903 DEBUGLOG(5, "ZSTD_checkDictValidity: blockEndIdx=%u, maxDist=%u, loadedDictEnd=%u",
904 (unsigned)blockEndIdx, (unsigned)maxDist, (unsigned)loadedDictEnd);
905 assert(blockEndIdx >= loadedDictEnd);
906
907 if (blockEndIdx > loadedDictEnd + maxDist) {
908 /* On reaching window size, dictionaries are invalidated.
909 * For simplification, if window size is reached anywhere within next block,
910 * the dictionary is invalidated for the full block.
911 */
912 DEBUGLOG(6, "invalidating dictionary for current block (distance > windowSize)");
913 *loadedDictEndPtr = 0;
914 *dictMatchStatePtr = NULL;
915 } else {
916 if (*loadedDictEndPtr != 0) {
917 DEBUGLOG(6, "dictionary considered valid for current block");
918 } } }
919}
920
922 memset(window, 0, sizeof(*window));
923 window->base = (BYTE const*)"";
924 window->dictBase = (BYTE const*)"";
925 window->dictLimit = 1; /* start from 1, so that 1st position is valid */
926 window->lowLimit = 1; /* it ensures first and later CCtx usages compress the same */
927 window->nextSrc = window->base + 1; /* see issue #1241 */
928}
929
938 void const* src, size_t srcSize)
939{
940 BYTE const* const ip = (BYTE const*)src;
941 U32 contiguous = 1;
942 DEBUGLOG(5, "ZSTD_window_update");
943 if (srcSize == 0)
944 return contiguous;
945 assert(window->base != NULL);
946 assert(window->dictBase != NULL);
947 /* Check if blocks follow each other */
948 if (src != window->nextSrc) {
949 /* not contiguous */
950 size_t const distanceFromBase = (size_t)(window->nextSrc - window->base);
951 DEBUGLOG(5, "Non contiguous blocks, new segment starts at %u", window->dictLimit);
952 window->lowLimit = window->dictLimit;
953 assert(distanceFromBase == (size_t)(U32)distanceFromBase); /* should never overflow */
954 window->dictLimit = (U32)distanceFromBase;
955 window->dictBase = window->base;
956 window->base = ip - distanceFromBase;
957 /* ms->nextToUpdate = window->dictLimit; */
958 if (window->dictLimit - window->lowLimit < HASH_READ_SIZE) window->lowLimit = window->dictLimit; /* too small extDict */
959 contiguous = 0;
960 }
961 window->nextSrc = ip + srcSize;
962 /* if input and dictionary overlap : reduce dictionary (area presumed modified by input) */
963 if ( (ip+srcSize > window->dictBase + window->lowLimit)
964 & (ip < window->dictBase + window->dictLimit)) {
965 ptrdiff_t const highInputIdx = (ip + srcSize) - window->dictBase;
966 U32 const lowLimitMax = (highInputIdx > (ptrdiff_t)window->dictLimit) ? window->dictLimit : (U32)highInputIdx;
967 window->lowLimit = lowLimitMax;
968 DEBUGLOG(5, "Overlapping extDict and input : new lowLimit = %u", window->lowLimit);
969 }
970 return contiguous;
971}
972
977{
978 U32 const maxDistance = 1U << windowLog;
979 U32 const lowestValid = ms->window.lowLimit;
980 U32 const withinWindow = (current - lowestValid > maxDistance) ? current - maxDistance : lowestValid;
981 U32 const isDictionary = (ms->loadedDictEnd != 0);
982 U32 const matchLowest = isDictionary ? lowestValid : withinWindow;
983 return matchLowest;
984}
985
990{
991 U32 const maxDistance = 1U << windowLog;
992 U32 const lowestValid = ms->window.dictLimit;
993 U32 const withinWindow = (current - lowestValid > maxDistance) ? current - maxDistance : lowestValid;
994 U32 const isDictionary = (ms->loadedDictEnd != 0);
995 U32 const matchLowest = isDictionary ? lowestValid : withinWindow;
996 return matchLowest;
997}
998
999
1000
1001/* debug functions */
1002#if (DEBUGLEVEL>=2)
1003
1004MEM_STATIC double ZSTD_fWeight(U32 rawStat)
1005{
1006 U32 const fp_accuracy = 8;
1007 U32 const fp_multiplier = (1 << fp_accuracy);
1008 U32 const newStat = rawStat + 1;
1009 U32 const hb = ZSTD_highbit32(newStat);
1010 U32 const BWeight = hb * fp_multiplier;
1011 U32 const FWeight = (newStat << fp_accuracy) >> hb;
1012 U32 const weight = BWeight + FWeight;
1013 assert(hb + fp_accuracy < 31);
1014 return (double)weight / fp_multiplier;
1015}
1016
1017/* display a table content,
1018 * listing each element, its frequency, and its predicted bit cost */
1019MEM_STATIC void ZSTD_debugTable(const U32* table, U32 max)
1020{
1021 unsigned u, sum;
1022 for (u=0, sum=0; u<=max; u++) sum += table[u];
1023 DEBUGLOG(2, "total nb elts: %u", sum);
1024 for (u=0; u<=max; u++) {
1025 DEBUGLOG(2, "%2u: %5u (%.2f)",
1026 u, table[u], ZSTD_fWeight(sum) - ZSTD_fWeight(table[u]) );
1027 }
1028}
1029
1030#endif
1031
1032
1033#if defined (__cplusplus)
1034}
1035#endif
1036
1037/* ===============================================================
1038 * Shared internal declarations
1039 * These prototypes may be called from sources not in lib/compress
1040 * =============================================================== */
1041
1042/* ZSTD_loadCEntropy() :
1043 * dict : must point at beginning of a valid zstd dictionary.
1044 * return : size of dictionary header (size of magic number + dict ID + entropy tables)
1045 * assumptions : magic number supposed already checked
1046 * and dictSize >= 8 */
1047size_t ZSTD_loadCEntropy(ZSTD_compressedBlockState_t* bs, void* workspace,
1048 short* offcodeNCount, unsigned* offcodeMaxValue,
1049 const void* const dict, size_t dictSize);
1050
1052
1053/* ==============================================================
1054 * Private declarations
1055 * These prototypes shall only be called from within lib/compress
1056 * ============================================================== */
1057
1058/* ZSTD_getCParamsFromCCtxParams() :
1059 * cParams are built depending on compressionLevel, src size hints,
1060 * LDM and manually set compression parameters.
1061 * Note: srcSizeHint == 0 means 0!
1062 */
1063ZSTD_compressionParameters ZSTD_getCParamsFromCCtxParams(
1064 const ZSTD_CCtx_params* CCtxParams, U64 srcSizeHint, size_t dictSize);
1065
1072 const void* dict, size_t dictSize,
1073 const ZSTD_CDict* cdict,
1074 const ZSTD_CCtx_params* params, unsigned long long pledgedSrcSize);
1075
1076void ZSTD_resetSeqStore(seqStore_t* ssPtr);
1077
1080ZSTD_compressionParameters ZSTD_getCParamsFromCDict(const ZSTD_CDict* cdict);
1081
1082/* ZSTD_compressBegin_advanced_internal() :
1083 * Private use only. To be called from zstdmt_compress.c. */
1085 const void* dict, size_t dictSize,
1086 ZSTD_dictContentType_e dictContentType,
1088 const ZSTD_CDict* cdict,
1089 const ZSTD_CCtx_params* params,
1090 unsigned long long pledgedSrcSize);
1091
1092/* ZSTD_compress_advanced_internal() :
1093 * Private use only. To be called from zstdmt_compress.c. */
1095 void* dst, size_t dstCapacity,
1096 const void* src, size_t srcSize,
1097 const void* dict,size_t dictSize,
1098 const ZSTD_CCtx_params* params);
1099
1100
1101/* ZSTD_writeLastEmptyBlock() :
1102 * output an empty Block with end-of-frame mark to complete a frame
1103 * @return : size of data written into `dst` (== ZSTD_blockHeaderSize (defined in zstd_internal.h))
1104 * or an error code if `dstCapacity` is too small (<ZSTD_blockHeaderSize)
1105 */
1106size_t ZSTD_writeLastEmptyBlock(void* dst, size_t dstCapacity);
1107
1108
1109/* ZSTD_referenceExternalSequences() :
1110 * Must be called before starting a compression operation.
1111 * seqs must parse a prefix of the source.
1112 * This cannot be used when long range matching is enabled.
1113 * Zstd will use these sequences, and pass the literals to a secondary block
1114 * compressor.
1115 * @return : An error code on failure.
1116 * NOTE: seqs are not verified! Invalid sequences can cause out-of-bounds memory
1117 * access and data corruption.
1118 */
1119size_t ZSTD_referenceExternalSequences(ZSTD_CCtx* cctx, rawSeq* seq, size_t nbSeq);
1120
1123U32 ZSTD_cycleLog(U32 hashLog, ZSTD_strategy strat);
1124
1125#endif /* ZSTD_COMPRESS_H */
#define MIN(x, y)
Definition: rdesktop.h:171
void mls(int argc, const char *argv[])
Definition: cmds.c:1168
#define NULL
Definition: types.h:112
UINT op
Definition: effect.c:236
static cab_ULONG checksum(const cab_UBYTE *data, cab_UWORD bytes, cab_ULONG csum)
Definition: fdi.c:353
#define assert(x)
Definition: debug.h:53
#define HINT_INLINE
Definition: compiler.h:61
#define UNUSED_ATTR
Definition: compiler.h:68
#define DEBUGLOG(l,...)
Definition: debug.h:106
MEM_STATIC U32 MEM_read32(const void *memPtr)
Definition: mem.h:242
MEM_STATIC U16 MEM_read16(const void *memPtr)
Definition: mem.h:237
MEM_STATIC size_t MEM_readST(const void *memPtr)
Definition: mem.h:252
MEM_STATIC unsigned MEM_isLittleEndian(void)
Definition: mem.h:186
MEM_STATIC unsigned MEM_64bits(void)
Definition: mem.h:184
MEM_STATIC U64 MEM_readLE64(const void *memPtr)
Definition: mem.h:362
#define MEM_STATIC
Definition: mem.h:39
MEM_STATIC void MEM_writeLE24(void *memPtr, U32 val)
Definition: mem.h:340
MEM_STATIC U32 MEM_readLE32(const void *memPtr)
Definition: mem.h:346
__kernel_size_t size_t
Definition: linux.h:237
__kernel_ptrdiff_t ptrdiff_t
Definition: linux.h:247
unsigned FSE_CTable
Definition: fse.h:160
GLuint GLuint end
Definition: gl.h:1545
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
GLsizeiptr size
Definition: glext.h:5919
GLenum src
Definition: glext.h:6340
GLenum const GLfloat * params
Definition: glext.h:5645
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
GLenum GLenum dst
Definition: glext.h:6340
GLuint GLsizei GLsizei * length
Definition: glext.h:6040
GLuint GLfloat * val
Definition: glext.h:7180
GLfloat GLfloat p
Definition: glext.h:8902
GLenum GLsizei len
Definition: glext.h:6722
GLintptr offset
Definition: glext.h:5920
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble * u
Definition: glfuncs.h:240
unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask)
Definition: intrin_arm.h:180
unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask)
Definition: intrin_arm.h:57
static struct msdos_boot_sector bs
Definition: mkdosfs.c:539
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
struct task_struct * current
Definition: linux.c:32
static PVOID ptr
Definition: dispmode.c:27
float power
Definition: d3drm.c:3372
static IHTMLWindow2 * window
Definition: events.c:77
static unsigned(__cdecl *hash_bstr)(bstr_t s)
static int sum(int x_, int y_)
Definition: ptr2_test.cpp:35
#define memset(x, y, z)
Definition: compat.h:39
weight
Definition: sortkey.c:157
#define KB
Definition: setuplib.h:55
ZSTD_frameParameters fParams
ZSTD_compressionParameters cParams
ZSTD_literalCompressionMode_e literalCompressionMode
ZSTD_dictAttachPref_e attachDictPref
ZSTD_CCtx_params appliedParams
ZSTD_customMem customMem
ZSTD_prefixDict prefixDict
SeqCollector seqCollector
ZSTD_compressionStage_e stage
ZSTD_CCtx_params requestedParams
rawSeqStore_t externSeqStore
unsigned long long pledgedSrcSizePlusOne
ZSTD_blockState_t blockState
ZSTD_cStreamStage streamStage
const ZSTD_CDict * cdict
XXH64_state_t xxhState
unsigned long long consumedSrcSize
unsigned long long producedCSize
ZSTD_localDict localDict
int upperBound
Definition: zstd.h:422
size_t error
Definition: zstd.h:420
int lowerBound
Definition: zstd.h:421
ZSTD_compressionParameters cParams
const ZSTD_matchState_t * dictMatchState
ZSTD_dictContentType_e dictContentType
Definition: _hash_fun.h:40
Definition: dhcpd.h:62
Definition: match.c:28
U16 matchLength
size_t maxNbSeq
size_t maxNbLit
seqDef * sequencesStart
seqDef * sequences
#define max(a, b)
Definition: svc.c:63
Definition: pdh_main.c:94
_In_ UINT iStart
Definition: wingdi.h:3620
unsigned long long U64
Definition: xxhash.c:197
signed int S32
Definition: xxhash.c:196
unsigned char BYTE
Definition: xxhash.c:193
unsigned int U32
Definition: xxhash.c:195
unsigned short U16
Definition: xxhash.c:194
struct XXH64_state_s XXH64_state_t
Definition: xxhash.h:183
ZSTD_cParameter
Definition: zstd.h:265
@ ZSTD_c_strategy
Definition: zstd.h:326
ZSTD_strategy
Definition: zstd.h:251
@ ZSTD_btultra
Definition: zstd.h:258
@ ZSTD_fast
Definition: zstd.h:251
ZSTDLIB_API ZSTD_bounds ZSTD_cParam_getBounds(ZSTD_cParameter cParam)
ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, ZSTD_dictMode_e dictMode)
size_t ZSTD_compress_advanced_internal(ZSTD_CCtx *cctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const void *dict, size_t dictSize, const ZSTD_CCtx_params *params)
MEM_STATIC size_t ZSTD_minGain(size_t srcSize, ZSTD_strategy strat)
MEM_STATIC U32 ZSTD_MLcode(U32 mlBase)
#define ZSTD_CURRENT_MAX
static size_t ZSTD_hash6Ptr(const void *p, U32 h)
MEM_STATIC ZSTD_dictMode_e ZSTD_matchState_dictMode(const ZSTD_matchState_t *ms)
static const U64 prime7bytes
static size_t ZSTD_hash6(U64 u, U32 h)
static const U32 prime4bytes
MEM_STATIC void ZSTD_window_clear(ZSTD_window_t *window)
static size_t ZSTD_hash5(U64 u, U32 h)
static const U64 prime6bytes
MEM_STATIC U64 ZSTD_rollingHash_compute(void const *buf, size_t size)
MEM_STATIC U64 ZSTD_rollingHash_rotate(U64 hash, BYTE toRemove, BYTE toAdd, U64 primePower)
size_t ZSTD_referenceExternalSequences(ZSTD_CCtx *cctx, rawSeq *seq, size_t nbSeq)
MEM_STATIC U32 ZSTD_window_needOverflowCorrection(ZSTD_window_t const window, void const *srcEnd)
static U32 ZSTD_hash4(U32 u, U32 h)
static size_t ZSTD_hash8(U64 u, U32 h)
MEM_STATIC size_t ZSTD_noCompressBlock(void *dst, size_t dstCapacity, const void *src, size_t srcSize, U32 lastBlock)
MEM_STATIC size_t ZSTD_count_2segments(const BYTE *ip, const BYTE *match, const BYTE *iEnd, const BYTE *mEnd, const BYTE *iStart)
static size_t ZSTD_hash8Ptr(const void *p, U32 h)
MEM_STATIC U64 ZSTD_rollingHash_primePower(U32 length)
MEM_STATIC repcodes_t ZSTD_updateRep(U32 const rep[3], U32 const offset, U32 const ll0)
static U64 ZSTD_ipow(U64 base, U64 exponent)
MEM_STATIC size_t ZSTD_hashPtr(const void *p, U32 hBits, U32 mls)
size_t ZSTD_loadCEntropy(ZSTD_compressedBlockState_t *bs, void *workspace, short *offcodeNCount, unsigned *offcodeMaxValue, const void *const dict, size_t dictSize)
static unsigned ZSTD_NbCommonBytes(size_t val)
MEM_STATIC U32 ZSTD_getLowestPrefixIndex(const ZSTD_matchState_t *ms, U32 current, unsigned windowLog)
MEM_STATIC U32 ZSTD_window_hasExtDict(ZSTD_window_t const window)
struct repcodes_s repcodes_t
MEM_STATIC U32 ZSTD_LLcode(U32 litLength)
static U64 ZSTD_rollingHash_append(U64 hash, void const *buf, size_t size)
MEM_STATIC U32 ZSTD_getLowestMatchIndex(const ZSTD_matchState_t *ms, U32 current, unsigned windowLog)
void ZSTD_resetSeqStore(seqStore_t *ssPtr)
MEM_STATIC void ZSTD_window_init(ZSTD_window_t *window)
MEM_STATIC size_t ZSTD_count(const BYTE *pIn, const BYTE *pMatch, const BYTE *const pInLimit)
size_t ZSTD_compressBegin_advanced_internal(ZSTD_CCtx *cctx, const void *dict, size_t dictSize, ZSTD_dictContentType_e dictContentType, ZSTD_dictTableLoadMethod_e dtlm, const ZSTD_CDict *cdict, const ZSTD_CCtx_params *params, unsigned long long pledgedSrcSize)
struct ZSTD_prefixDict_s ZSTD_prefixDict
size_t ZSTD_initCStream_internal(ZSTD_CStream *zcs, const void *dict, size_t dictSize, const ZSTD_CDict *cdict, const ZSTD_CCtx_params *params, unsigned long long pledgedSrcSize)
size_t(* ZSTD_blockCompressor)(ZSTD_matchState_t *bs, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
static size_t ZSTD_hash5Ptr(const void *p, U32 h)
MEM_STATIC int ZSTD_disableLiteralsCompression(const ZSTD_CCtx_params *cctxParams)
MEM_STATIC size_t ZSTD_rleCompressBlock(void *dst, size_t dstCapacity, BYTE src, size_t srcSize, U32 lastBlock)
MEM_STATIC int ZSTD_cParam_withinBounds(ZSTD_cParameter cParam, int value)
MEM_STATIC U32 ZSTD_window_update(ZSTD_window_t *window, void const *src, size_t srcSize)
static const U32 prime3bytes
MEM_STATIC void ZSTD_checkDictValidity(const ZSTD_window_t *window, const void *blockEnd, U32 maxDist, U32 *loadedDictEndPtr, const ZSTD_matchState_t **dictMatchStatePtr)
ZSTD_compressionStage_e
@ ZSTDcs_ongoing
@ ZSTDcs_created
@ ZSTDcs_ending
static void ZSTD_safecopyLiterals(BYTE *op, BYTE const *ip, BYTE const *const iend, BYTE const *ilimit_w)
MEM_STATIC size_t ZSTD_hash3Ptr(const void *ptr, U32 h)
MEM_STATIC void ZSTD_window_enforceMaxDist(ZSTD_window_t *window, const void *blockEnd, U32 maxDist, U32 *loadedDictEndPtr, const ZSTD_matchState_t **dictMatchStatePtr)
U32 ZSTD_cycleLog(U32 hashLog, ZSTD_strategy strat)
HINT_INLINE UNUSED_ATTR void ZSTD_storeSeq(seqStore_t *seqStorePtr, size_t litLength, const BYTE *literals, const BYTE *litLimit, U32 offCode, size_t mlBase)
ZSTD_dictTableLoadMethod_e
@ ZSTD_dtlm_full
@ ZSTD_dtlm_fast
static const U64 prime8bytes
size_t ZSTD_writeLastEmptyBlock(void *dst, size_t dstCapacity)
static U32 ZSTD_hash3(U32 u, U32 h)
static size_t ZSTD_hash7Ptr(const void *p, U32 h)
void ZSTD_reset_compressedBlockState(ZSTD_compressedBlockState_t *bs)
MEM_STATIC U32 ZSTD_window_correctOverflow(ZSTD_window_t *window, U32 cycleLog, U32 maxDist, void const *src)
#define HASH_READ_SIZE
static size_t ZSTD_hash4Ptr(const void *ptr, U32 h)
#define ZSTD_ROLL_HASH_CHAR_OFFSET
static const U64 prime5bytes
ZSTD_compressionParameters ZSTD_getCParamsFromCCtxParams(const ZSTD_CCtx_params *CCtxParams, U64 srcSizeHint, size_t dictSize)
ZSTD_compressionParameters ZSTD_getCParamsFromCDict(const ZSTD_CDict *cdict)
@ ZSTD_dictMatchState
static size_t ZSTD_hash7(U64 u, U32 h)
#define MINMATCH
#define MaxLL
static const size_t ZSTD_blockHeaderSize
#define WILDCOPY_OVERLENGTH
#define MaxML
MEM_STATIC U32 ZSTD_highbit32(U32 val)
#define RETURN_ERROR_IF(cond, err,...)
Definition: zstd_internal.h:91
#define ZSTD_REP_MOVE
#define ZSTD_isError
Definition: zstd_internal.h:46
#define MLFSELog
@ bt_rle
@ bt_raw
static void ZSTD_copy16(void *dst, const void *src)
#define MaxOff
MEM_STATIC FORCE_INLINE_ATTR void ZSTD_wildcopy(void *dst, const void *src, ptrdiff_t length, ZSTD_overlap_e const ovtype)
#define LLFSELog
#define ZSTD_STATIC_ASSERT(c)
Definition: zstd_internal.h:45
#define ZSTD_REP_NUM
@ ZSTD_no_overlap
#define OffFSELog