sys/contrib/zstd/lib/compress/zstd_compress_internal.h

   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 ***************************************/
  48 typedef enum { ZSTDcs_created=0, ZSTDcs_init, ZSTDcs_ongoing, ZSTDcs_ending } ZSTD_compressionStage_e;
  49 typedef enum { zcss_init=0, zcss_load, zcss_flush } ZSTD_cStreamStage;
  50
  51 typedef enum {
  52     ZSTD_dictDefaultAttach = 0,
  53     ZSTD_dictForceAttach = 1,
  54     ZSTD_dictForceCopy = -1,
  55 } ZSTD_dictAttachPref_e;
  56
  57 typedef struct ZSTD_prefixDict_s {
  58     const void* dict;
  59     size_t dictSize;
  60     ZSTD_dictContentType_e dictContentType;
  61 } ZSTD_prefixDict;
  62
  63 typedef struct {
  64     U32 CTable[HUF_CTABLE_SIZE_U32(255)];
  65     HUF_repeat repeatMode;
  66 } ZSTD_hufCTables_t;
  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;
  73     FSE_repeat matchlength_repeatMode;
  74     FSE_repeat litlength_repeatMode;
  75 } ZSTD_fseCTables_t;
  76
  77 typedef struct {
  78     ZSTD_hufCTables_t huf;
  79     ZSTD_fseCTables_t fse;
  80 } ZSTD_entropyCTables_t;
  81
  82 typedef struct {
  83     U32 off;
  84     U32 len;
  85 } ZSTD_match_t;
  86
  87 typedef struct {
  88     int price;
  89     U32 off;
  90     U32 mlen;
  91     U32 litlen;
  92     U32 rep[ZSTD_REP_NUM];
  93 } ZSTD_optimal_t;
  94
  95 typedef enum { zop_dynamic=0, zop_predef } ZSTD_OptPrice_e;
  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 {
 119   ZSTD_entropyCTables_t entropy;
 120   U32 rep[ZSTD_REP_NUM];
 121 } ZSTD_compressedBlockState_t;
 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
 131 typedef struct ZSTD_matchState_t ZSTD_matchState_t;
 132 struct ZSTD_matchState_t {
 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 */
 138     U32* hashTable;
 139     U32* hashTable3;
 140     U32* chainTable;
 141     optState_t opt;         /* optimal parser state */
 142     const ZSTD_matchState_t *dictMatchState;
 143     ZSTD_compressionParameters cParams;
 144 };
 145
 146 typedef struct {
 147     ZSTD_compressedBlockState_t* prevCBlock;
 148     ZSTD_compressedBlockState_t* nextCBlock;
 149     ZSTD_matchState_t matchState;
 150 } ZSTD_blockState_t;
 151
 152 typedef struct {
 153     U32 offset;
 154     U32 checksum;
 155 } ldmEntry_t;
 156
 157 typedef struct {
 158     ZSTD_window_t window;   /* State for the window round buffer management */
 159     ldmEntry_t* hashTable;
 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 {
 175     U32 offset;
 176     U32 litLength;
 177     U32 matchLength;
 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
 187 struct ZSTD_CCtx_params_s {
 188     ZSTD_format_e format;
 189     ZSTD_compressionParameters cParams;
 190     ZSTD_frameParameters fParams;
 191
 192     int compressionLevel;
 193     int forceWindow;           /* force back-references to respect limit of
 194                                 * 1<<wLog, even for dictionary */
 195
 196     ZSTD_dictAttachPref_e attachDictPref;
 197
 198     /* Multithreading: used to pass parameters to mtctx */
 199     unsigned nbWorkers;
 200     unsigned jobSize;
 201     unsigned overlapSizeLog;
 202
 203     /* Long distance matching parameters */
 204     ldmParams_t ldmParams;
 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 {
 211     ZSTD_compressionStage_e stage;
 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;
 216     U32   dictID;
 217
 218     int workSpaceOversizedDuration;
 219     void* workSpace;
 220     size_t workSpaceSize;
 221     size_t blockSize;
 222     unsigned long long pledgedSrcSizePlusOne;  /* this way, 0 (default) == unknown */
 223     unsigned long long consumedSrcSize;
 224     unsigned long long producedCSize;
 225     XXH64_state_t xxhState;
 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 */
 232     size_t maxNbLdmSequences;
 233     rawSeqStore_t externSeqStore; /* Mutable reference to external sequences */
 234     ZSTD_blockState_t blockState;
 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;
 245     size_t outBuffContentSize;
 246     size_t outBuffFlushedSize;
 247     ZSTD_cStreamStage streamStage;
 248     U32    frameEnded;
 249
 250     /* Dictionary */
 251     ZSTD_CDict* cdictLocal;
 252     const ZSTD_CDict* cdict;
 253     ZSTD_prefixDict prefixDict;   /* single-usage dictionary */
 254
 255     /* Multi-threading */
 256 #ifdef ZSTD_MULTITHREAD
 257     ZSTDMT_CCtx* mtctx;
 258 #endif
 259 };
 260
 261 typedef enum { ZSTD_dtlm_fast, ZSTD_dtlm_full } ZSTD_dictTableLoadMethod_e;
 262
 263 typedef enum { ZSTD_noDict = 0, ZSTD_extDict = 1, ZSTD_dictMatchState = 2 } ZSTD_dictMode_e;
 264
 265
 266 typedef size_t (*ZSTD_blockCompressor) (
 267         ZSTD_matchState_t* bs, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
 268         void const* src, size_t srcSize);
 269 ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, ZSTD_dictMode_e dictMode);
 270
 271
 272 MEM_STATIC U32 ZSTD_LLcode(U32 litLength)
 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 */
 289 MEM_STATIC U32 ZSTD_MLcode(U32 mlBase)
 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
 303 /*! ZSTD_storeSeq() :
 304  *  Store a sequence (literal length, literals, offset code and match length code) into seqStore_t.
 305  *  `offsetCode` : distance to match + 3 (values 1-3 are repCodes).
 306  *  `mlBase` : matchLength - MINMATCH
 307 */
 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
 441 /** ZSTD_count_2segments() :
 442  *  can count match length with `ip` & `match` in 2 different segments.
 443  *  convention : on reaching mEnd, match count continue starting from iStart
 444  */
 445 MEM_STATIC size_t
 446 ZSTD_count_2segments(const BYTE* ip, const BYTE* match,
 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
 511 /**
 512  * ZSTD_window_clear():
 513  * Clears the window containing the history by simply setting it to empty.
 514  */
 515 MEM_STATIC void ZSTD_window_clear(ZSTD_window_t* window)
 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
 524 /**
 525  * ZSTD_window_hasExtDict():
 526  * Returns non-zero if the window has a non-empty extDict.
 527  */
 528 MEM_STATIC U32 ZSTD_window_hasExtDict(ZSTD_window_t const window)
 529 {
 530     return window.lowLimit < window.dictLimit;
 531 }
 532
 533 /**
 534  * ZSTD_matchState_dictMode():
 535  * Inspects the provided matchState and figures out what dictMode should be
 536  * passed to the compressor.
 537  */
 538 MEM_STATIC ZSTD_dictMode_e ZSTD_matchState_dictMode(const ZSTD_matchState_t *ms)
 539 {
 540     return ZSTD_window_hasExtDict(ms->window) ?
 541         ZSTD_extDict :
 542         ms->dictMatchState != NULL ?
 543             ZSTD_dictMatchState :
 544             ZSTD_noDict;
 545 }
 546
 547 /**
 548  * ZSTD_window_needOverflowCorrection():
 549  * Returns non-zero if the indices are getting too large and need overflow
 550  * protection.
 551  */
 552 MEM_STATIC U32 ZSTD_window_needOverflowCorrection(ZSTD_window_t const window,
 553                                                   void const* srcEnd)
 554 {
 555     U32 const current = (U32)((BYTE const*)srcEnd - window.base);
 556     return current > ZSTD_CURRENT_MAX;
 557 }
 558
 559 /**
 560  * ZSTD_window_correctOverflow():
 561  * Reduces the indices to protect from index overflow.
 562  * Returns the correction made to the indices, which must be applied to every
 563  * stored index.
 564  *
 565  * The least significant cycleLog bits of the indices must remain the same,
 566  * which may be 0. Every index up to maxDist in the past must be valid.
 567  * NOTE: (maxDist & cycleMask) must be zero.
 568  */
 569 MEM_STATIC U32 ZSTD_window_correctOverflow(ZSTD_window_t* window, U32 cycleLog,
 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
 610 /**
 611  * ZSTD_window_enforceMaxDist():
 612  * Updates lowLimit so that:
 613  *    (srcEnd - base) - lowLimit == maxDist + loadedDictEnd
 614  *
 615  * This allows a simple check that index >= lowLimit to see if index is valid.
 616  * This must be called before a block compression call, with srcEnd as the block
 617  * source end.
 618  *
 619  * If loadedDictEndPtr is not NULL, we set it to zero once we update lowLimit.
 620  * This is because dictionaries are allowed to be referenced as long as the last
 621  * byte of the dictionary is in the window, but once they are out of range,
 622  * they cannot be referenced. If loadedDictEndPtr is NULL, we use
 623  * loadedDictEnd == 0.
 624  *
 625  * In normal dict mode, the dict is between lowLimit and dictLimit. In
 626  * dictMatchState mode, lowLimit and dictLimit are the same, and the dictionary
 627  * is below them. forceWindow and dictMatchState are therefore incompatible.
 628  */
 629 MEM_STATIC void ZSTD_window_enforceMaxDist(ZSTD_window_t* window,
 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
 652 /**
 653  * ZSTD_window_update():
 654  * Updates the window by appending [src, src + srcSize) to the window.
 655  * If it is not contiguous, the current prefix becomes the extDict, and we
 656  * forget about the extDict. Handles overlap of the prefix and extDict.
 657  * Returns non-zero if the segment is contiguous.
 658  */
 659 MEM_STATIC U32 ZSTD_window_update(ZSTD_window_t* window,
 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
 707 MEM_STATIC void ZSTD_debugTable(const U32* table, U32 max)
 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)",
 714                 u, table[u], ZSTD_fWeight(sum) - ZSTD_fWeight(table[u]) );
 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
 735 /*! ZSTD_initCStream_internal() :
 736  *  Private use only. Init streaming operation.
 737  *  expects params to be valid.
 738  *  must receive dict, or cdict, or none, but not both.
 739  *  @return : 0, or an error code */
 740 size_t ZSTD_initCStream_internal(ZSTD_CStream* zcs,
 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
 747 /*! ZSTD_compressStream_generic() :
 748  *  Private use only. To be called from zstdmt_compress.c in single-thread mode. */
 749 size_t ZSTD_compressStream_generic(ZSTD_CStream* zcs,
 750                                    ZSTD_outBuffer* output,
 751                                    ZSTD_inBuffer* input,
 752                                    ZSTD_EndDirective const flushMode);
 753
 754 /*! ZSTD_getCParamsFromCDict() :
 755  *  as the name implies */
 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. */
 760 size_t ZSTD_compressBegin_advanced_internal(ZSTD_CCtx* cctx,
 761                                     const void* dict, size_t dictSize,
 762                                     ZSTD_dictContentType_e dictContentType,
 763                                     ZSTD_dictTableLoadMethod_e dtlm,
 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. */
 770 size_t ZSTD_compress_advanced_internal(ZSTD_CCtx* cctx,
 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 */