ReactOS  0.4.14-dev-342-gdc047f9
zstd_compress_internal.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
3  * All rights reserved.
4  *
5  * This source code is licensed under both the BSD-style license (found in the
6  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
7  * in the COPYING file in the root directory of this source tree).
8  * You may select, at your option, one of the above-listed licenses.
9  */
10 
11 /* 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 #ifdef ZSTD_MULTITHREAD
23 # include "zstdmt_compress.h"
24 #endif
25 
26 #if defined (__cplusplus)
27 extern "C" {
28 #endif
29 
30 
31 /*-*************************************
32 * Constants
33 ***************************************/
34 #define kSearchStrength 8
35 #define HASH_READ_SIZE 8
36 #define ZSTD_DUBT_UNSORTED_MARK 1 /* For btlazy2 strategy, index 1 now means "unsorted".
37  It could be confused for a real successor at index "1", if sorted as larger than its predecessor.
38  It's not a big deal though : candidate will just be sorted again.
39  Additionnally, candidate position 1 will be lost.
40  But candidate 1 cannot hide a large tree of candidates, so it's a minimal loss.
41  The benefit is that ZSTD_DUBT_UNSORTED_MARK cannot be misdhandled after table re-use with a different strategy
42  Constant required by ZSTD_compressBlock_btlazy2() and ZSTD_reduceTable_internal() */
43 
44 
45 /*-*************************************
46 * Context memory management
47 ***************************************/
50 
51 typedef enum {
56 
57 typedef struct ZSTD_prefixDict_s {
58  const void* dict;
59  size_t dictSize;
60  ZSTD_dictContentType_e dictContentType;
62 
63 typedef struct {
64  U32 CTable[HUF_CTABLE_SIZE_U32(255)];
65  HUF_repeat repeatMode;
67 
68 typedef struct {
69  FSE_CTable offcodeCTable[FSE_CTABLE_SIZE_U32(OffFSELog, MaxOff)];
70  FSE_CTable matchlengthCTable[FSE_CTABLE_SIZE_U32(MLFSELog, MaxML)];
71  FSE_CTable litlengthCTable[FSE_CTABLE_SIZE_U32(LLFSELog, MaxLL)];
72  FSE_repeat offcode_repeatMode;
76 
77 typedef struct {
81 
82 typedef struct {
85 } ZSTD_match_t;
86 
87 typedef struct {
88  int price;
94 
96 
97 typedef struct {
98  /* All tables are allocated inside cctx->workspace by ZSTD_resetCCtx_internal() */
99  U32* litFreq; /* table of literals statistics, of size 256 */
100  U32* litLengthFreq; /* table of litLength statistics, of size (MaxLL+1) */
101  U32* matchLengthFreq; /* table of matchLength statistics, of size (MaxML+1) */
102  U32* offCodeFreq; /* table of offCode statistics, of size (MaxOff+1) */
103  ZSTD_match_t* matchTable; /* list of found matches, of size ZSTD_OPT_NUM+1 */
104  ZSTD_optimal_t* priceTable; /* All positions tracked by optimal parser, of size ZSTD_OPT_NUM+1 */
105 
106  U32 litSum; /* nb of literals */
107  U32 litLengthSum; /* nb of litLength codes */
108  U32 matchLengthSum; /* nb of matchLength codes */
109  U32 offCodeSum; /* nb of offset codes */
110  U32 litSumBasePrice; /* to compare to log2(litfreq) */
111  U32 litLengthSumBasePrice; /* to compare to log2(llfreq) */
112  U32 matchLengthSumBasePrice;/* to compare to log2(mlfreq) */
113  U32 offCodeSumBasePrice; /* to compare to log2(offreq) */
114  ZSTD_OptPrice_e priceType; /* prices can be determined dynamically, or follow a pre-defined cost structure */
115  const ZSTD_entropyCTables_t* symbolCosts; /* pre-calculated dictionary statistics */
116 } optState_t;
117 
118 typedef struct {
122 
123 typedef struct {
124  BYTE const* nextSrc; /* next block here to continue on current prefix */
125  BYTE const* base; /* All regular indexes relative to this position */
126  BYTE const* dictBase; /* extDict indexes relative to this position */
127  U32 dictLimit; /* below that point, need extDict */
128  U32 lowLimit; /* below that point, no more data */
129 } ZSTD_window_t;
130 
133  ZSTD_window_t window; /* State for window round buffer management */
134  U32 loadedDictEnd; /* index of end of dictionary */
135  U32 nextToUpdate; /* index from which to continue table update */
136  U32 nextToUpdate3; /* index from which to continue table update */
137  U32 hashLog3; /* dispatch table : larger == faster, more memory */
141  optState_t opt; /* optimal parser state */
143  ZSTD_compressionParameters cParams;
144 };
145 
146 typedef struct {
151 
152 typedef struct {
155 } ldmEntry_t;
156 
157 typedef struct {
158  ZSTD_window_t window; /* State for the window round buffer management */
160  BYTE* bucketOffsets; /* Next position in bucket to insert entry */
161  U64 hashPower; /* Used to compute the rolling hash.
162  * Depends on ldmParams.minMatchLength */
163 } ldmState_t;
164 
165 typedef struct {
166  U32 enableLdm; /* 1 if enable long distance matching */
167  U32 hashLog; /* Log size of hashTable */
168  U32 bucketSizeLog; /* Log bucket size for collision resolution, at most 8 */
169  U32 minMatchLength; /* Minimum match length */
170  U32 hashEveryLog; /* Log number of entries to skip */
171  U32 windowLog; /* Window log for the LDM */
172 } ldmParams_t;
173 
174 typedef struct {
178 } rawSeq;
179 
180 typedef struct {
181  rawSeq* seq; /* The start of the sequences */
182  size_t pos; /* The position where reading stopped. <= size. */
183  size_t size; /* The number of sequences. <= capacity. */
184  size_t capacity; /* The capacity starting from `seq` pointer */
185 } rawSeqStore_t;
186 
188  ZSTD_format_e format;
189  ZSTD_compressionParameters cParams;
190  ZSTD_frameParameters fParams;
191 
193  int forceWindow; /* force back-references to respect limit of
194  * 1<<wLog, even for dictionary */
195 
197 
198  /* Multithreading: used to pass parameters to mtctx */
199  unsigned nbWorkers;
200  unsigned jobSize;
201  unsigned overlapSizeLog;
202 
203  /* Long distance matching parameters */
205 
206  /* Internal use, for createCCtxParams() and freeCCtxParams() only */
207  ZSTD_customMem customMem;
208 }; /* typedef'd to ZSTD_CCtx_params within "zstd.h" */
209 
210 struct ZSTD_CCtx_s {
212  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. */
213  int bmi2; /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */
214  ZSTD_CCtx_params requestedParams;
215  ZSTD_CCtx_params appliedParams;
217 
219  void* workSpace;
221  size_t blockSize;
222  unsigned long long pledgedSrcSizePlusOne; /* this way, 0 (default) == unknown */
223  unsigned long long consumedSrcSize;
224  unsigned long long producedCSize;
226  ZSTD_customMem customMem;
227  size_t staticSize;
228 
229  seqStore_t seqStore; /* sequences storage ptrs */
230  ldmState_t ldmState; /* long distance matching state */
231  rawSeq* ldmSequences; /* Storage for the ldm output sequences */
233  rawSeqStore_t externSeqStore; /* Mutable reference to external sequences */
235  U32* entropyWorkspace; /* entropy workspace of HUF_WORKSPACE_SIZE bytes */
236 
237  /* streaming */
238  char* inBuff;
239  size_t inBuffSize;
240  size_t inToCompress;
241  size_t inBuffPos;
242  size_t inBuffTarget;
243  char* outBuff;
244  size_t outBuffSize;
249 
250  /* Dictionary */
253  ZSTD_prefixDict prefixDict; /* single-usage dictionary */
254 
255  /* Multi-threading */
256 #ifdef ZSTD_MULTITHREAD
257  ZSTDMT_CCtx* mtctx;
258 #endif
259 };
260 
262 
264 
265 
267  ZSTD_matchState_t* bs, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
268  void const* src, size_t srcSize);
270 
271 
273 {
274  static const BYTE LL_Code[64] = { 0, 1, 2, 3, 4, 5, 6, 7,
275  8, 9, 10, 11, 12, 13, 14, 15,
276  16, 16, 17, 17, 18, 18, 19, 19,
277  20, 20, 20, 20, 21, 21, 21, 21,
278  22, 22, 22, 22, 22, 22, 22, 22,
279  23, 23, 23, 23, 23, 23, 23, 23,
280  24, 24, 24, 24, 24, 24, 24, 24,
281  24, 24, 24, 24, 24, 24, 24, 24 };
282  static const U32 LL_deltaCode = 19;
283  return (litLength > 63) ? ZSTD_highbit32(litLength) + LL_deltaCode : LL_Code[litLength];
284 }
285 
286 /* ZSTD_MLcode() :
287  * note : mlBase = matchLength - MINMATCH;
288  * because it's the format it's stored in seqStore->sequences */
290 {
291  static const BYTE ML_Code[128] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
292  16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
293  32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37,
294  38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39,
295  40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
296  41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,
297  42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
298  42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42 };
299  static const U32 ML_deltaCode = 36;
300  return (mlBase > 127) ? ZSTD_highbit32(mlBase) + ML_deltaCode : ML_Code[mlBase];
301 }
302 
308 MEM_STATIC void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const void* literals, U32 offsetCode, size_t mlBase)
309 {
310 #if defined(DEBUGLEVEL) && (DEBUGLEVEL >= 6)
311  static const BYTE* g_start = NULL;
312  if (g_start==NULL) g_start = (const BYTE*)literals; /* note : index only works for compression within a single segment */
313  { U32 const pos = (U32)((const BYTE*)literals - g_start);
314  DEBUGLOG(6, "Cpos%7u :%3u literals, match%4u bytes at offCode%7u",
315  pos, (U32)litLength, (U32)mlBase+MINMATCH, (U32)offsetCode);
316  }
317 #endif
318  assert((size_t)(seqStorePtr->sequences - seqStorePtr->sequencesStart) < seqStorePtr->maxNbSeq);
319  /* copy Literals */
320  assert(seqStorePtr->maxNbLit <= 128 KB);
321  assert(seqStorePtr->lit + litLength <= seqStorePtr->litStart + seqStorePtr->maxNbLit);
322  ZSTD_wildcopy(seqStorePtr->lit, literals, litLength);
323  seqStorePtr->lit += litLength;
324 
325  /* literal Length */
326  if (litLength>0xFFFF) {
327  assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
328  seqStorePtr->longLengthID = 1;
329  seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
330  }
331  seqStorePtr->sequences[0].litLength = (U16)litLength;
332 
333  /* match offset */
334  seqStorePtr->sequences[0].offset = offsetCode + 1;
335 
336  /* match Length */
337  if (mlBase>0xFFFF) {
338  assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
339  seqStorePtr->longLengthID = 2;
340  seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
341  }
342  seqStorePtr->sequences[0].matchLength = (U16)mlBase;
343 
344  seqStorePtr->sequences++;
345 }
346 
347 
348 /*-*************************************
349 * Match length counter
350 ***************************************/
351 static unsigned ZSTD_NbCommonBytes (size_t val)
352 {
353  if (MEM_isLittleEndian()) {
354  if (MEM_64bits()) {
355 # if defined(_MSC_VER) && defined(_WIN64)
356  unsigned long r = 0;
357  _BitScanForward64( &r, (U64)val );
358  return (unsigned)(r>>3);
359 # elif defined(__GNUC__) && (__GNUC__ >= 4)
360  return (__builtin_ctzll((U64)val) >> 3);
361 # else
362  static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2,
363  0, 3, 1, 3, 1, 4, 2, 7,
364  0, 2, 3, 6, 1, 5, 3, 5,
365  1, 3, 4, 4, 2, 5, 6, 7,
366  7, 0, 1, 2, 3, 3, 4, 6,
367  2, 6, 5, 5, 3, 4, 5, 6,
368  7, 1, 2, 4, 6, 4, 4, 5,
369  7, 2, 6, 5, 7, 6, 7, 7 };
370  return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
371 # endif
372  } else { /* 32 bits */
373 # if defined(_MSC_VER)
374  unsigned long r=0;
375  _BitScanForward( &r, (U32)val );
376  return (unsigned)(r>>3);
377 # elif defined(__GNUC__) && (__GNUC__ >= 3)
378  return (__builtin_ctz((U32)val) >> 3);
379 # else
380  static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0,
381  3, 2, 2, 1, 3, 2, 0, 1,
382  3, 3, 1, 2, 2, 2, 2, 0,
383  3, 1, 2, 0, 1, 0, 1, 1 };
384  return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
385 # endif
386  }
387  } else { /* Big Endian CPU */
388  if (MEM_64bits()) {
389 # if defined(_MSC_VER) && defined(_WIN64)
390  unsigned long r = 0;
391  _BitScanReverse64( &r, val );
392  return (unsigned)(r>>3);
393 # elif defined(__GNUC__) && (__GNUC__ >= 4)
394  return (__builtin_clzll(val) >> 3);
395 # else
396  unsigned r;
397  const unsigned n32 = sizeof(size_t)*4; /* calculate this way due to compiler complaining in 32-bits mode */
398  if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }
399  if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
400  r += (!val);
401  return r;
402 # endif
403  } else { /* 32 bits */
404 # if defined(_MSC_VER)
405  unsigned long r = 0;
406  _BitScanReverse( &r, (unsigned long)val );
407  return (unsigned)(r>>3);
408 # elif defined(__GNUC__) && (__GNUC__ >= 3)
409  return (__builtin_clz((U32)val) >> 3);
410 # else
411  unsigned r;
412  if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
413  r += (!val);
414  return r;
415 # endif
416  } }
417 }
418 
419 
420 MEM_STATIC size_t ZSTD_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* const pInLimit)
421 {
422  const BYTE* const pStart = pIn;
423  const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1);
424 
425  if (pIn < pInLoopLimit) {
426  { size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
427  if (diff) return ZSTD_NbCommonBytes(diff); }
428  pIn+=sizeof(size_t); pMatch+=sizeof(size_t);
429  while (pIn < pInLoopLimit) {
430  size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
431  if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; }
432  pIn += ZSTD_NbCommonBytes(diff);
433  return (size_t)(pIn - pStart);
434  } }
435  if (MEM_64bits() && (pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatch+=4; }
436  if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; }
437  if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;
438  return (size_t)(pIn - pStart);
439 }
440 
445 MEM_STATIC size_t
447  const BYTE* iEnd, const BYTE* mEnd, const BYTE* iStart)
448 {
449  const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd);
450  size_t const matchLength = ZSTD_count(ip, match, vEnd);
451  if (match + matchLength != mEnd) return matchLength;
452  DEBUGLOG(7, "ZSTD_count_2segments: found a 2-parts match (current length==%zu)", matchLength);
453  DEBUGLOG(7, "distance from match beginning to end dictionary = %zi", mEnd - match);
454  DEBUGLOG(7, "distance from current pos to end buffer = %zi", iEnd - ip);
455  DEBUGLOG(7, "next byte : ip==%02X, istart==%02X", ip[matchLength], *iStart);
456  DEBUGLOG(7, "final match length = %zu", matchLength + ZSTD_count(ip+matchLength, iStart, iEnd));
457  return matchLength + ZSTD_count(ip+matchLength, iStart, iEnd);
458 }
459 
460 
461 /*-*************************************
462  * Hashes
463  ***************************************/
464 static const U32 prime3bytes = 506832829U;
465 static U32 ZSTD_hash3(U32 u, U32 h) { return ((u << (32-24)) * prime3bytes) >> (32-h) ; }
466 MEM_STATIC size_t ZSTD_hash3Ptr(const void* ptr, U32 h) { return ZSTD_hash3(MEM_readLE32(ptr), h); } /* only in zstd_opt.h */
467 
468 static const U32 prime4bytes = 2654435761U;
469 static U32 ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32-h) ; }
470 static size_t ZSTD_hash4Ptr(const void* ptr, U32 h) { return ZSTD_hash4(MEM_read32(ptr), h); }
471 
472 static const U64 prime5bytes = 889523592379ULL;
473 static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u << (64-40)) * prime5bytes) >> (64-h)) ; }
474 static size_t ZSTD_hash5Ptr(const void* p, U32 h) { return ZSTD_hash5(MEM_readLE64(p), h); }
475 
476 static const U64 prime6bytes = 227718039650203ULL;
477 static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u << (64-48)) * prime6bytes) >> (64-h)) ; }
478 static size_t ZSTD_hash6Ptr(const void* p, U32 h) { return ZSTD_hash6(MEM_readLE64(p), h); }
479 
480 static const U64 prime7bytes = 58295818150454627ULL;
481 static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u << (64-56)) * prime7bytes) >> (64-h)) ; }
482 static size_t ZSTD_hash7Ptr(const void* p, U32 h) { return ZSTD_hash7(MEM_readLE64(p), h); }
483 
484 static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL;
485 static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; }
486 static size_t ZSTD_hash8Ptr(const void* p, U32 h) { return ZSTD_hash8(MEM_readLE64(p), h); }
487 
488 MEM_STATIC size_t ZSTD_hashPtr(const void* p, U32 hBits, U32 mls)
489 {
490  switch(mls)
491  {
492  default:
493  case 4: return ZSTD_hash4Ptr(p, hBits);
494  case 5: return ZSTD_hash5Ptr(p, hBits);
495  case 6: return ZSTD_hash6Ptr(p, hBits);
496  case 7: return ZSTD_hash7Ptr(p, hBits);
497  case 8: return ZSTD_hash8Ptr(p, hBits);
498  }
499 }
500 
501 /*-*************************************
502 * Round buffer management
503 ***************************************/
504 /* Max current allowed */
505 #define ZSTD_CURRENT_MAX ((3U << 29) + (1U << ZSTD_WINDOWLOG_MAX))
506 /* Maximum chunk size before overflow correction needs to be called again */
507 #define ZSTD_CHUNKSIZE_MAX \
508  ( ((U32)-1) /* Maximum ending current index */ \
509  - ZSTD_CURRENT_MAX) /* Maximum beginning lowLimit */
510 
516 {
517  size_t const endT = (size_t)(window->nextSrc - window->base);
518  U32 const end = (U32)endT;
519 
520  window->lowLimit = end;
521  window->dictLimit = end;
522 }
523 
529 {
530  return window.lowLimit < window.dictLimit;
531 }
532 
539 {
540  return ZSTD_window_hasExtDict(ms->window) ?
541  ZSTD_extDict :
542  ms->dictMatchState != NULL ?
544  ZSTD_noDict;
545 }
546 
553  void const* srcEnd)
554 {
555  U32 const current = (U32)((BYTE const*)srcEnd - window.base);
556  return current > ZSTD_CURRENT_MAX;
557 }
558 
570  U32 maxDist, void const* src)
571 {
572  /* preemptive overflow correction:
573  * 1. correction is large enough:
574  * lowLimit > (3<<29) ==> current > 3<<29 + 1<<windowLog
575  * 1<<windowLog <= newCurrent < 1<<chainLog + 1<<windowLog
576  *
577  * current - newCurrent
578  * > (3<<29 + 1<<windowLog) - (1<<windowLog + 1<<chainLog)
579  * > (3<<29) - (1<<chainLog)
580  * > (3<<29) - (1<<30) (NOTE: chainLog <= 30)
581  * > 1<<29
582  *
583  * 2. (ip+ZSTD_CHUNKSIZE_MAX - cctx->base) doesn't overflow:
584  * After correction, current is less than (1<<chainLog + 1<<windowLog).
585  * In 64-bit mode we are safe, because we have 64-bit ptrdiff_t.
586  * In 32-bit mode we are safe, because (chainLog <= 29), so
587  * ip+ZSTD_CHUNKSIZE_MAX - cctx->base < 1<<32.
588  * 3. (cctx->lowLimit + 1<<windowLog) < 1<<32:
589  * windowLog <= 31 ==> 3<<29 + 1<<windowLog < 7<<29 < 1<<32.
590  */
591  U32 const cycleMask = (1U << cycleLog) - 1;
592  U32 const current = (U32)((BYTE const*)src - window->base);
593  U32 const newCurrent = (current & cycleMask) + maxDist;
594  U32 const correction = current - newCurrent;
595  assert((maxDist & cycleMask) == 0);
596  assert(current > newCurrent);
597  /* Loose bound, should be around 1<<29 (see above) */
598  assert(correction > 1<<28);
599 
600  window->base += correction;
601  window->dictBase += correction;
602  window->lowLimit -= correction;
603  window->dictLimit -= correction;
604 
605  DEBUGLOG(4, "Correction of 0x%x bytes to lowLimit=0x%x", correction,
606  window->lowLimit);
607  return correction;
608 }
609 
630  void const* srcEnd, U32 maxDist,
631  U32* loadedDictEndPtr,
632  const ZSTD_matchState_t** dictMatchStatePtr)
633 {
634  U32 const current = (U32)((BYTE const*)srcEnd - window->base);
635  U32 loadedDictEnd = loadedDictEndPtr != NULL ? *loadedDictEndPtr : 0;
636  DEBUGLOG(5, "ZSTD_window_enforceMaxDist: current=%u, maxDist=%u", current, maxDist);
637  if (current > maxDist + loadedDictEnd) {
638  U32 const newLowLimit = current - maxDist;
639  if (window->lowLimit < newLowLimit) window->lowLimit = newLowLimit;
640  if (window->dictLimit < window->lowLimit) {
641  DEBUGLOG(5, "Update dictLimit to match lowLimit, from %u to %u",
642  window->dictLimit, window->lowLimit);
643  window->dictLimit = window->lowLimit;
644  }
645  if (loadedDictEndPtr)
646  *loadedDictEndPtr = 0;
647  if (dictMatchStatePtr)
648  *dictMatchStatePtr = NULL;
649  }
650 }
651 
660  void const* src, size_t srcSize)
661 {
662  BYTE const* const ip = (BYTE const*)src;
663  U32 contiguous = 1;
664  DEBUGLOG(5, "ZSTD_window_update");
665  /* Check if blocks follow each other */
666  if (src != window->nextSrc) {
667  /* not contiguous */
668  size_t const distanceFromBase = (size_t)(window->nextSrc - window->base);
669  DEBUGLOG(5, "Non contiguous blocks, new segment starts at %u", window->dictLimit);
670  window->lowLimit = window->dictLimit;
671  assert(distanceFromBase == (size_t)(U32)distanceFromBase); /* should never overflow */
672  window->dictLimit = (U32)distanceFromBase;
673  window->dictBase = window->base;
674  window->base = ip - distanceFromBase;
675  // ms->nextToUpdate = window->dictLimit;
676  if (window->dictLimit - window->lowLimit < HASH_READ_SIZE) window->lowLimit = window->dictLimit; /* too small extDict */
677  contiguous = 0;
678  }
679  window->nextSrc = ip + srcSize;
680  /* if input and dictionary overlap : reduce dictionary (area presumed modified by input) */
681  if ( (ip+srcSize > window->dictBase + window->lowLimit)
682  & (ip < window->dictBase + window->dictLimit)) {
683  ptrdiff_t const highInputIdx = (ip + srcSize) - window->dictBase;
684  U32 const lowLimitMax = (highInputIdx > (ptrdiff_t)window->dictLimit) ? window->dictLimit : (U32)highInputIdx;
685  window->lowLimit = lowLimitMax;
686  DEBUGLOG(5, "Overlapping extDict and input : new lowLimit = %u", window->lowLimit);
687  }
688  return contiguous;
689 }
690 
691 
692 /* debug functions */
693 
694 MEM_STATIC double ZSTD_fWeight(U32 rawStat)
695 {
696  U32 const fp_accuracy = 8;
697  U32 const fp_multiplier = (1 << fp_accuracy);
698  U32 const stat = rawStat + 1;
699  U32 const hb = ZSTD_highbit32(stat);
700  U32 const BWeight = hb * fp_multiplier;
701  U32 const FWeight = (stat << fp_accuracy) >> hb;
702  U32 const weight = BWeight + FWeight;
703  assert(hb + fp_accuracy < 31);
704  return (double)weight / fp_multiplier;
705 }
706 
708 {
709  unsigned u, sum;
710  for (u=0, sum=0; u<=max; u++) sum += table[u];
711  DEBUGLOG(2, "total nb elts: %u", sum);
712  for (u=0; u<=max; u++) {
713  DEBUGLOG(2, "%2u: %5u (%.2f)",
715  }
716 }
717 
718 #if defined (__cplusplus)
719 }
720 #endif
721 
722 
723 /* ==============================================================
724  * Private declarations
725  * These prototypes shall only be called from within lib/compress
726  * ============================================================== */
727 
728 /* ZSTD_getCParamsFromCCtxParams() :
729  * cParams are built depending on compressionLevel, src size hints,
730  * LDM and manually set compression parameters.
731  */
732 ZSTD_compressionParameters ZSTD_getCParamsFromCCtxParams(
733  const ZSTD_CCtx_params* CCtxParams, U64 srcSizeHint, size_t dictSize);
734 
741  const void* dict, size_t dictSize,
742  const ZSTD_CDict* cdict,
743  ZSTD_CCtx_params params, unsigned long long pledgedSrcSize);
744 
745 void ZSTD_resetSeqStore(seqStore_t* ssPtr);
746 
752  ZSTD_EndDirective const flushMode);
753 
756 ZSTD_compressionParameters ZSTD_getCParamsFromCDict(const ZSTD_CDict* cdict);
757 
758 /* ZSTD_compressBegin_advanced_internal() :
759  * Private use only. To be called from zstdmt_compress.c. */
761  const void* dict, size_t dictSize,
762  ZSTD_dictContentType_e dictContentType,
764  const ZSTD_CDict* cdict,
765  ZSTD_CCtx_params params,
766  unsigned long long pledgedSrcSize);
767 
768 /* ZSTD_compress_advanced_internal() :
769  * Private use only. To be called from zstdmt_compress.c. */
771  void* dst, size_t dstCapacity,
772  const void* src, size_t srcSize,
773  const void* dict,size_t dictSize,
774  ZSTD_CCtx_params params);
775 
776 
777 /* ZSTD_writeLastEmptyBlock() :
778  * output an empty Block with end-of-frame mark to complete a frame
779  * @return : size of data written into `dst` (== ZSTD_blockHeaderSize (defined in zstd_internal.h))
780  * or an error code if `dstCapcity` is too small (<ZSTD_blockHeaderSize)
781  */
782 size_t ZSTD_writeLastEmptyBlock(void* dst, size_t dstCapacity);
783 
784 
785 /* ZSTD_referenceExternalSequences() :
786  * Must be called before starting a compression operation.
787  * seqs must parse a prefix of the source.
788  * This cannot be used when long range matching is enabled.
789  * Zstd will use these sequences, and pass the literals to a secondary block
790  * compressor.
791  * @return : An error code on failure.
792  * NOTE: seqs are not verified! Invalid sequences can cause out-of-bounds memory
793  * access and data corruption.
794  */
795 size_t ZSTD_referenceExternalSequences(ZSTD_CCtx* cctx, rawSeq* seq, size_t nbSeq);
796 
797 
798 #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
unsigned short U16
Definition: mem.h:72
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
unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask)
Definition: intrin_arm.h:57
static UCHAR ULONG UCHAR ULONG UCHAR * output
Definition: bcrypt.c:29
MEM_STATIC size_t MEM_readST(const void *memPtr)
Definition: mem.h:179
static const U64 prime7bytes
unsigned long long pledgedSrcSizePlusOne
U16 matchLength
MEM_STATIC unsigned MEM_isLittleEndian(void)
Definition: mem.h:113
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, ZSTD_CCtx_params params)
ZSTD_match_t * matchTable
Definition: match.c:28
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
ZSTD_OptPrice_e priceType
MEM_STATIC U32 MEM_readLE32(const void *memPtr)
Definition: mem.h:273
struct XXH64_state_s XXH64_state_t
Definition: xxhash.h:183
struct ZSTD_prefixDict_s ZSTD_prefixDict
#define U(x)
Definition: wordpad.c:44
static size_t ZSTD_hash5(U64 u, U32 h)
MEM_STATIC U32 ZSTD_window_hasExtDict(ZSTD_window_t const window)
MEM_STATIC void ZSTD_window_clear(ZSTD_window_t *window)
unsigned int U32
Definition: mem.h:77
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:3615
size_t ZSTD_writeLastEmptyBlock(void *dst, size_t dstCapacity)
unsigned FSE_CTable
Definition: fse.h:180
seqDef * sequencesStart
ldmEntry_t * hashTable
GLuint GLuint end
Definition: gl.h:1545
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:289
MEM_STATIC unsigned MEM_64bits(void)
Definition: mem.h:111
ZSTD_prefixDict prefixDict
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
GLuint GLuint GLfloat weight
Definition: glext.h:11719
static size_t ZSTD_hash4Ptr(const void *ptr, U32 h)
T MIN(T a, T b)
Definition: polytest.cpp:79
ZSTD_CDict * cdictLocal
#define DEBUGLOG(l,...)
Definition: debug.h:115
size_t ZSTD_referenceExternalSequences(ZSTD_CCtx *cctx, rawSeq *seq, size_t nbSeq)
static unsigned ZSTD_NbCommonBytes(size_t val)
seqDef * sequences
static const U64 prime5bytes
GLenum const GLfloat * params
Definition: glext.h:5645
ZSTD_compressionStage_e stage
ZSTD_dictAttachPref_e
static const U64 prime6bytes
static PVOID ptr
Definition: dispmode.c:27
ZSTD_compressionParameters cParams
static size_t ZSTD_hash8Ptr(const void *p, U32 h)
ZSTD_compressionParameters cParams
smooth NULL
Definition: ftsmooth.c:416
static const U32 prime4bytes
MEM_STATIC void ZSTD_wildcopy(void *dst, const void *src, ptrdiff_t length)
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)
MEM_STATIC void ZSTD_window_enforceMaxDist(ZSTD_window_t *window, void const *srcEnd, U32 maxDist, U32 *loadedDictEndPtr, const ZSTD_matchState_t **dictMatchStatePtr)
#define MLFSELog
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
__kernel_size_t size_t
Definition: linux.h:237
signed int S32
Definition: mem.h:78
MEM_STATIC void ZSTD_debugTable(const U32 *table, U32 max)
#define MEM_STATIC
Definition: mem.h:39
Definition: dhcpd.h:61
MEM_STATIC void ZSTD_storeSeq(seqStore_t *seqStorePtr, size_t litLength, const void *literals, U32 offsetCode, size_t mlBase)
const ZSTD_matchState_t * dictMatchState
XXH64_state_t xxhState
static const U64 prime8bytes
#define OffFSELog
ZSTD_frameParameters fParams
MEM_STATIC double ZSTD_fWeight(U32 rawStat)
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:169
#define HASH_READ_SIZE
size_t maxNbSeq
ZSTD_optimal_t * priceTable
ZSTD_compressedBlockState_t * nextCBlock
Definition: stat.h:55
const ZSTD_entropyCTables_t * symbolCosts
unsigned char BYTE
Definition: mem.h:68
ZSTD_matchState_t matchState
GLenum src
Definition: glext.h:6340
static IHTMLWindow2 * window
Definition: events.c:77
MEM_STATIC U32 ZSTD_window_correctOverflow(ZSTD_window_t *window, U32 cycleLog, U32 maxDist, void const *src)
ZSTD_dictTableLoadMethod_e
size_t ZSTD_initCStream_internal(ZSTD_CStream *zcs, const void *dict, size_t dictSize, const ZSTD_CDict *cdict, ZSTD_CCtx_params params, unsigned long long pledgedSrcSize)
MEM_STATIC size_t ZSTD_hashPtr(const void *p, U32 hBits, U32 mls)
#define MaxOff
static size_t ZSTD_hash6(U64 u, U32 h)
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)
ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, ZSTD_dictMode_e dictMode)
GLenum GLenum GLenum input
Definition: glext.h:9031
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, ZSTD_CCtx_params params, unsigned long long pledgedSrcSize)
MEM_STATIC ZSTD_dictMode_e ZSTD_matchState_dictMode(const ZSTD_matchState_t *ms)
unsigned long long U64
Definition: mem.h:81
static size_t ZSTD_hash7Ptr(const void *p, U32 h)
unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask)
Definition: intrin_arm.h:180
GLenum GLenum dst
Definition: glext.h:6340
MEM_STATIC U32 ZSTD_window_update(ZSTD_window_t *window, void const *src, size_t srcSize)
const ZSTD_CDict * cdict
__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
Definition: zstd_internal.h:96
ZSTD_CCtx_params requestedParams
unsigned long long producedCSize
ZSTD_window_t window
#define LLFSELog
#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
#define KB
Definition: setuplib.h:52
MEM_STATIC U16 MEM_read16(const void *memPtr)
Definition: mem.h:164
static struct msdos_boot_sector bs
Definition: mkdosfs.c:539
MEM_STATIC U32 ZSTD_LLcode(U32 litLength)
size_t ZSTD_compressStream_generic(ZSTD_CStream *zcs, ZSTD_outBuffer *output, ZSTD_inBuffer *input, ZSTD_EndDirective const flushMode)
#define ZSTD_REP_NUM
Definition: zstd_internal.h:62
struct task_struct * current
Definition: linux.c:32