ReactOS  0.4.15-dev-4614-ga5a6101
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)
28 extern "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() */
44 
45 
46 /*-*************************************
47 * Context memory management
48 ***************************************/
51 
52 typedef struct ZSTD_prefixDict_s {
53  const void* dict;
54  size_t dictSize;
55  ZSTD_dictContentType_e dictContentType;
57 
58 typedef struct {
59  void* dictBuffer;
60  void const* dict;
61  size_t dictSize;
62  ZSTD_dictContentType_e dictContentType;
65 
66 typedef struct {
67  U32 CTable[HUF_CTABLE_SIZE_U32(255)];
68  HUF_repeat repeatMode;
70 
71 typedef 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;
79 
80 typedef struct {
84 
85 typedef struct {
88 } ZSTD_match_t;
89 
90 typedef struct {
91  int price;
97 
99 
100 typedef 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 */
108 
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;
121 
122 typedef struct {
126 
127 typedef 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 */
133 } ZSTD_window_t;
134 
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 */
150  optState_t opt; /* optimal parser state */
152  ZSTD_compressionParameters cParams;
153 };
154 
155 typedef struct {
160 
161 typedef struct {
164 } ldmEntry_t;
165 
166 typedef struct {
167  ZSTD_window_t window; /* State for the window round buffer management */
170  BYTE* bucketOffsets; /* Next position in bucket to insert entry */
171  U64 hashPower; /* Used to compute the rolling hash.
172  * Depends on ldmParams.minMatchLength */
173 } ldmState_t;
174 
175 typedef 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 */
182 } ldmParams_t;
183 
184 typedef struct {
188 } rawSeq;
189 
190 typedef 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 */
195 } rawSeqStore_t;
196 
197 typedef struct {
199  ZSTD_Sequence* seqStart;
200  size_t seqIndex;
201  size_t maxSequences;
202 } SeqCollector;
203 
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 */
218 
219  ZSTD_dictAttachPref_e attachDictPref;
220  ZSTD_literalCompressionMode_e literalCompressionMode;
221 
222  /* Multithreading: used to pass parameters to mtctx */
224  size_t jobSize;
227 
228  /* Long distance matching parameters */
230 
231  /* Internal use, for createCCtxParams() and freeCCtxParams() only */
232  ZSTD_customMem customMem;
233 }; /* typedef'd to ZSTD_CCtx_params within "zstd.h" */
234 
235 struct ZSTD_CCtx_s {
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;
242 
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;
250  size_t staticSize;
254 
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 */
262 
263  /* streaming */
264  char* inBuff;
265  size_t inBuffSize;
266  size_t inToCompress;
267  size_t inBuffPos;
268  size_t inBuffTarget;
269  char* outBuff;
270  size_t outBuffSize;
275 
276  /* Dictionary */
279  ZSTD_prefixDict prefixDict; /* single-usage dictionary */
280 
281  /* Multi-threading */
282 #ifdef ZSTD_MULTITHREAD
283  ZSTDMT_CCtx* mtctx;
284 #endif
285 };
286 
288 
290 
291 
293  ZSTD_matchState_t* bs, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
294  void const* src, size_t srcSize);
296 
297 
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];
327 }
328 
329 typedef struct repcodes_s {
330  U32 rep[3];
331 } repcodes_t;
332 
333 MEM_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 */
369 MEM_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 
379 MEM_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 }
388 
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 */
394 MEM_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 
402 MEM_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 }
416 
422 static 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 
439 void 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++;
490 }
491 
492 
493 /*-*************************************
494 * Match length counter
495 ***************************************/
496 static 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 
561 MEM_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 }
581 
586 MEM_STATIC size_t
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);
599 }
600 
601 
602 /*-*************************************
603  * Hashes
604  ***************************************/
605 static const U32 prime3bytes = 506832829U;
606 static U32 ZSTD_hash3(U32 u, U32 h) { return ((u << (32-24)) * prime3bytes) >> (32-h) ; }
607 MEM_STATIC size_t ZSTD_hash3Ptr(const void* ptr, U32 h) { return ZSTD_hash3(MEM_readLE32(ptr), h); } /* only in zstd_opt.h */
608 
609 static const U32 prime4bytes = 2654435761U;
610 static U32 ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32-h) ; }
611 static size_t ZSTD_hash4Ptr(const void* ptr, U32 h) { return ZSTD_hash4(MEM_read32(ptr), h); }
612 
613 static const U64 prime5bytes = 889523592379ULL;
614 static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u << (64-40)) * prime5bytes) >> (64-h)) ; }
615 static size_t ZSTD_hash5Ptr(const void* p, U32 h) { return ZSTD_hash5(MEM_readLE64(p), h); }
616 
617 static const U64 prime6bytes = 227718039650203ULL;
618 static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u << (64-48)) * prime6bytes) >> (64-h)) ; }
619 static size_t ZSTD_hash6Ptr(const void* p, U32 h) { return ZSTD_hash6(MEM_readLE64(p), h); }
620 
621 static const U64 prime7bytes = 58295818150454627ULL;
622 static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u << (64-56)) * prime7bytes) >> (64-h)) ; }
623 static size_t ZSTD_hash7Ptr(const void* p, U32 h) { return ZSTD_hash7(MEM_readLE64(p), h); }
624 
625 static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL;
626 static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; }
627 static size_t ZSTD_hash8Ptr(const void* p, U32 h) { return ZSTD_hash8(MEM_readLE64(p), h); }
628 
629 MEM_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);
639  }
640 }
641 
645 static 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 }
655 
656 #define ZSTD_ROLL_HASH_CHAR_OFFSET 10
657 
661 static 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;
667  hash += istart[pos] + ZSTD_ROLL_HASH_CHAR_OFFSET;
668  }
669  return hash;
670 }
671 
676 {
677  return ZSTD_rollingHash_append(0, buf, size);
678 }
679 
685 {
686  return ZSTD_ipow(prime8bytes, length - 1);
687 }
688 
692 MEM_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;
696  hash += toAdd + ZSTD_ROLL_HASH_CHAR_OFFSET;
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;
724 }
725 
731 {
732  return window.lowLimit < window.dictLimit;
733 }
734 
741 {
742  return ZSTD_window_hasExtDict(ms->window) ?
743  ZSTD_extDict :
744  ms->dictMatchState != NULL ?
746  ZSTD_noDict;
747 }
748 
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 
847 MEM_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 */
892 MEM_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 
1004 MEM_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 */
1019 MEM_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 */
1047 size_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  */
1063 ZSTD_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 
1076 void ZSTD_resetSeqStore(seqStore_t* ssPtr);
1077 
1080 ZSTD_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  */
1106 size_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  */
1119 size_t ZSTD_referenceExternalSequences(ZSTD_CCtx* cctx, rawSeq* seq, size_t nbSeq);
1120 
1123 U32 ZSTD_cycleLog(U32 hashLog, ZSTD_strategy strat);
1124 
1125 #endif /* ZSTD_COMPRESS_H */
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
#define WILDCOPY_OVERLENGTH
unsigned long long consumedSrcSize
rawSeqStore_t externSeqStore
static size_t ZSTD_hash5Ptr(const void *p, U32 h)
#define max(a, b)
Definition: svc.c:63
Definition: pdh_main.c:93
unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask)
Definition: intrin_arm.h:57
MEM_STATIC size_t MEM_readST(const void *memPtr)
Definition: mem.h:252
ZSTD_dictContentType_e dictContentType
static const U64 prime7bytes
unsigned long long pledgedSrcSizePlusOne
U16 matchLength
MEM_STATIC int ZSTD_cParam_withinBounds(ZSTD_cParameter cParam, int value)
MEM_STATIC unsigned MEM_isLittleEndian(void)
Definition: mem.h:186
ZSTDLIB_API ZSTD_bounds ZSTD_cParam_getBounds(ZSTD_cParameter cParam)
ZSTD_match_t * matchTable
Definition: match.c:28
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
ZSTD_OptPrice_e priceType
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)
MEM_STATIC U32 MEM_readLE32(const void *memPtr)
Definition: mem.h:346
struct XXH64_state_s XXH64_state_t
Definition: xxhash.h:183
HINT_INLINE UNUSED_ATTR void ZSTD_storeSeq(seqStore_t *seqStorePtr, size_t litLength, const BYTE *literals, const BYTE *litLimit, U32 offCode, size_t mlBase)
struct ZSTD_prefixDict_s ZSTD_prefixDict
#define U(x)
Definition: wordpad.c:45
static size_t ZSTD_hash5(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 U32 ZSTD_window_hasExtDict(ZSTD_window_t const window)
MEM_STATIC void ZSTD_window_clear(ZSTD_window_t *window)
MEM_STATIC repcodes_t ZSTD_updateRep(U32 const rep[3], U32 const offset, U32 const ll0)
unsigned * litLengthFreq
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)
MEM_STATIC size_t ZSTD_hash3Ptr(const void *ptr, U32 h)
ZSTD_compressionParameters ZSTD_getCParamsFromCDict(const ZSTD_CDict *cdict)
#define assert(x)
Definition: debug.h:53
ZSTD_compressionStage_e
_In_ UINT iStart
Definition: wingdi.h:3620
size_t ZSTD_writeLastEmptyBlock(void *dst, size_t dstCapacity)
unsigned FSE_CTable
Definition: fse.h:160
seqDef * sequencesStart
ldmEntry_t * hashTable
MEM_STATIC size_t ZSTD_minGain(size_t srcSize, ZSTD_strategy strat)
void ZSTD_resetSeqStore(seqStore_t *ssPtr)
void mls(int argc, const char *argv[])
Definition: cmds.c:1168
MEM_STATIC U64 MEM_readLE64(const void *memPtr)
Definition: mem.h:362
MEM_STATIC unsigned MEM_64bits(void)
Definition: mem.h:184
ZSTD_prefixDict prefixDict
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
MEM_STATIC U64 ZSTD_rollingHash_compute(void const *buf, size_t size)
static size_t ZSTD_hash4Ptr(const void *ptr, U32 h)
T MIN(T a, T b)
Definition: polytest.cpp:79
#define ZSTD_STATIC_ASSERT(c)
Definition: zstd_internal.h:45
#define DEBUGLOG(l,...)
Definition: debug.h:106
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
size_t ZSTD_referenceExternalSequences(ZSTD_CCtx *cctx, rawSeq *seq, size_t nbSeq)
MEM_STATIC U32 ZSTD_getLowestMatchIndex(const ZSTD_matchState_t *ms, U32 current, unsigned windowLog)
#define ZSTD_isError
Definition: zstd_internal.h:46
static unsigned ZSTD_NbCommonBytes(size_t val)
int upperBound
Definition: zstd.h:422
MEM_STATIC void ZSTD_window_init(ZSTD_window_t *window)
ZSTD_localDict localDict
static const size_t ZSTD_blockHeaderSize
seqDef * sequences
static const U64 prime5bytes
GLenum const GLfloat * params
Definition: glext.h:5645
int hash
Definition: main.c:58
MEM_STATIC void ZSTD_window_enforceMaxDist(ZSTD_window_t *window, const void *blockEnd, U32 maxDist, U32 *loadedDictEndPtr, const ZSTD_matchState_t **dictMatchStatePtr)
GLuint base
Definition: 3dtext.c:35
ZSTD_compressionStage_e stage
GLenum GLuint GLenum GLsizei length
Definition: glext.h:5579
static const U64 prime6bytes
size_t error
Definition: zstd.h:420
static PVOID ptr
Definition: dispmode.c:27
int ip[4]
Definition: rtl.c:1176
ZSTD_compressionParameters cParams
static size_t ZSTD_hash8Ptr(const void *p, U32 h)
ZSTD_compressionParameters cParams
static const U32 prime4bytes
ZSTD_CCtx_params appliedParams
ZSTD_blockState_t blockState
MEM_STATIC U32 ZSTD_MLcode(U32 mlBase)
#define MaxML
MEM_STATIC size_t ZSTD_count(const BYTE *pIn, const BYTE *pMatch, const BYTE *const pInLimit)
#define MLFSELog
unsigned * offCodeFreq
static size_t ZSTD_hash8(U64 u, U32 h)
MEM_STATIC size_t ZSTD_count_2segments(const BYTE *ip, const BYTE *match, const BYTE *iEnd, const BYTE *mEnd, const BYTE *iStart)
static int sum(int x_, int y_)
Definition: ptr2_test.cpp:35
#define ULL(a, b)
Definition: format_msg.c:27
GLuint GLfloat * val
Definition: glext.h:7180
signed int S32
Definition: xxhash.c:196
#define ZSTD_REP_MOVE
MEM_STATIC U32 ZSTD_getLowestPrefixIndex(const ZSTD_matchState_t *ms, U32 current, unsigned windowLog)
static void ZSTD_safecopyLiterals(BYTE *op, BYTE const *ip, BYTE const *const iend, BYTE const *ilimit_w)
__kernel_size_t size_t
Definition: linux.h:237
ZSTD_Sequence * seqStart
#define MEM_STATIC
Definition: mem.h:39
GLsizeiptr size
Definition: glext.h:5919
#define RETURN_ERROR_IF(cond, err,...)
Definition: zstd_internal.h:91
Definition: dhcpd.h:61
const ZSTD_matchState_t * dictMatchState
XXH64_state_t xxhState
MEM_STATIC FORCE_INLINE_ATTR void ZSTD_wildcopy(void *dst, const void *src, ptrdiff_t length, ZSTD_overlap_e const ovtype)
static void ZSTD_copy16(void *dst, const void *src)
GLintptr offset
Definition: glext.h:5920
struct repcodes_s repcodes_t
static const U64 prime8bytes
#define OffFSELog
ZSTD_literalCompressionMode_e literalCompressionMode
UINT op
Definition: effect.c:236
ZSTD_frameParameters fParams
unsigned * matchLengthFreq
struct task_struct * current
Definition: linux.c:32
GLuint GLuint end
Definition: gl.h:1545
static const U32 prime3bytes
ZSTD_dictContentType_e dictContentType
static size_t ZSTD_hash6Ptr(const void *p, U32 h)
MEM_STATIC U32 ZSTD_window_needOverflowCorrection(ZSTD_window_t const window, void const *srcEnd)
size_t(* ZSTD_blockCompressor)(ZSTD_matchState_t *bs, seqStore_t *seqStore, U32 rep[ZSTD_REP_NUM], void const *src, size_t srcSize)
MEM_STATIC U32 MEM_read32(const void *memPtr)
Definition: mem.h:242
MEM_STATIC U64 ZSTD_rollingHash_rotate(U64 hash, BYTE toRemove, BYTE toAdd, U64 primePower)
#define HASH_READ_SIZE
size_t maxNbSeq
ZSTD_optimal_t * priceTable
ZSTD_compressedBlockState_t * nextCBlock
const ZSTD_entropyCTables_t * symbolCosts
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
ZSTD_matchState_t matchState
GLenum src
Definition: glext.h:6340
static IHTMLWindow2 * window
Definition: events.c:77
MEM_STATIC void ZSTD_checkDictValidity(const ZSTD_window_t *window, const void *blockEnd, U32 maxDist, U32 *loadedDictEndPtr, const ZSTD_matchState_t **dictMatchStatePtr)
static U64 ZSTD_ipow(U64 base, U64 exponent)
unsigned char BYTE
Definition: xxhash.c:193
MEM_STATIC U32 ZSTD_window_correctOverflow(ZSTD_window_t *window, U32 cycleLog, U32 maxDist, void const *src)
ZSTD_dictTableLoadMethod_e
MEM_STATIC size_t ZSTD_hashPtr(const void *p, U32 hBits, U32 mls)
#define MaxOff
static size_t ZSTD_hash6(U64 u, U32 h)
unsigned short U16
Definition: xxhash.c:194
static U32 ZSTD_hash4(U32 u, U32 h)
static size_t ZSTD_hash7(U64 u, U32 h)
static U32 ZSTD_hash3(U32 u, U32 h)
weight
Definition: sortkey.c:156
ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, ZSTD_dictMode_e dictMode)
float power
Definition: d3drm.c:3372
unsigned long long U64
Definition: xxhash.c:197
MEM_STATIC ZSTD_dictMode_e ZSTD_matchState_dictMode(const ZSTD_matchState_t *ms)
void ZSTD_reset_compressedBlockState(ZSTD_compressedBlockState_t *bs)
static size_t ZSTD_hash7Ptr(const void *p, U32 h)
unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask)
Definition: intrin_arm.h:180
size_t ZSTD_loadCEntropy(ZSTD_compressedBlockState_t *bs, void *workspace, short *offcodeNCount, unsigned *offcodeMaxValue, const void *const dict, size_t dictSize)
MEM_STATIC size_t ZSTD_rleCompressBlock(void *dst, size_t dstCapacity, BYTE src, size_t srcSize, U32 lastBlock)
GLenum GLenum dst
Definition: glext.h:6340
int lowerBound
Definition: zstd.h:421
MEM_STATIC U32 ZSTD_window_update(ZSTD_window_t *window, void const *src, size_t srcSize)
const ZSTD_CDict * cdict
#define NULL
Definition: types.h:112
__kernel_ptrdiff_t ptrdiff_t
Definition: linux.h:247
ZSTD_customMem customMem
MEM_STATIC U32 ZSTD_highbit32(U32 val)
#define MaxLL
ZSTD_cStreamStage streamStage
#define MINMATCH
ZSTD_literalCompressionMode_e literalCompressionMode
ZSTD_CCtx_params requestedParams
ZSTD_cParameter
Definition: zstd.h:265
MEM_STATIC void MEM_writeLE24(void *memPtr, U32 val)
Definition: mem.h:340
unsigned long long producedCSize
ZSTD_window_t window
static U64 ZSTD_rollingHash_append(U64 hash, void const *buf, size_t size)
#define LLFSELog
#define HINT_INLINE
Definition: compiler.h:61
U32 ZSTD_cycleLog(U32 hashLog, ZSTD_strategy strat)
#define ZSTD_CURRENT_MAX
ZSTD_dictAttachPref_e attachDictPref
ZSTD_compressedBlockState_t * prevCBlock
ZSTD_compressionParameters ZSTD_getCParamsFromCCtxParams(const ZSTD_CCtx_params *CCtxParams, U64 srcSizeHint, size_t dictSize)
size_t maxNbLit
GLfloat GLfloat p
Definition: glext.h:8902
MEM_STATIC U64 ZSTD_rollingHash_primePower(U32 length)
#define KB
Definition: setuplib.h:55
MEM_STATIC U16 MEM_read16(const void *memPtr)
Definition: mem.h:237
static struct msdos_boot_sector bs
Definition: mkdosfs.c:539
ZSTD_strategy
Definition: zstd.h:251
MEM_STATIC U32 ZSTD_LLcode(U32 litLength)
Definition: _hash_fun.h:40
#define memset(x, y, z)
Definition: compat.h:39
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)
unsigned int U32
Definition: xxhash.c:195
#define ZSTD_ROLL_HASH_CHAR_OFFSET
SeqCollector seqCollector
#define ZSTD_REP_NUM
static unsigned(__cdecl *hash_bstr)(bstr_t s)
MEM_STATIC int ZSTD_disableLiteralsCompression(const ZSTD_CCtx_params *cctxParams)
#define UNUSED_ATTR
Definition: compiler.h:68