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                                        Additionally, 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 mishandled 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 struct ZSTD_prefixDict_s {
  52     const void* dict;
  53     size_t dictSize;
  54     ZSTD_dictContentType_e dictContentType;
  55 } ZSTD_prefixDict;
  56
  57 typedef struct {
  58     void* dictBuffer;
  59     void const* dict;
  60     size_t dictSize;
  61     ZSTD_dictContentType_e dictContentType;
  62     ZSTD_CDict* cdict;
  63 } ZSTD_localDict;
  64
  65 typedef struct {
  66     U32 CTable[HUF_CTABLE_SIZE_U32(255)];
  67     HUF_repeat repeatMode;
  68 } ZSTD_hufCTables_t;
  69
  70 typedef struct {
  71     FSE_CTable offcodeCTable[FSE_CTABLE_SIZE_U32(OffFSELog, MaxOff)];
  72     FSE_CTable matchlengthCTable[FSE_CTABLE_SIZE_U32(MLFSELog, MaxML)];
  73     FSE_CTable litlengthCTable[FSE_CTABLE_SIZE_U32(LLFSELog, MaxLL)];
  74     FSE_repeat offcode_repeatMode;
  75     FSE_repeat matchlength_repeatMode;
  76     FSE_repeat litlength_repeatMode;
  77 } ZSTD_fseCTables_t;
  78
  79 typedef struct {
  80     ZSTD_hufCTables_t huf;
  81     ZSTD_fseCTables_t fse;
  82 } ZSTD_entropyCTables_t;
  83
  84 typedef struct {
  85     U32 off;
  86     U32 len;
  87 } ZSTD_match_t;
  88
  89 typedef struct {
  90     int price;
  91     U32 off;
  92     U32 mlen;
  93     U32 litlen;
  94     U32 rep[ZSTD_REP_NUM];
  95 } ZSTD_optimal_t;
  96
  97 typedef enum { zop_dynamic=0, zop_predef } ZSTD_OptPrice_e;
  98
  99 typedef struct {
 100     /* All tables are allocated inside cctx->workspace by ZSTD_resetCCtx_internal() */
 101     unsigned* litFreq;           /* table of literals statistics, of size 256 */
 102     unsigned* litLengthFreq;     /* table of litLength statistics, of size (MaxLL+1) */
 103     unsigned* matchLengthFreq;   /* table of matchLength statistics, of size (MaxML+1) */
 104     unsigned* offCodeFreq;       /* table of offCode statistics, of size (MaxOff+1) */
 105     ZSTD_match_t* matchTable;    /* list of found matches, of size ZSTD_OPT_NUM+1 */
 106     ZSTD_optimal_t* priceTable;  /* All positions tracked by optimal parser, of size ZSTD_OPT_NUM+1 */
 107
 108     U32  litSum;                 /* nb of literals */
 109     U32  litLengthSum;           /* nb of litLength codes */
 110     U32  matchLengthSum;         /* nb of matchLength codes */
 111     U32  offCodeSum;             /* nb of offset codes */
 112     U32  litSumBasePrice;        /* to compare to log2(litfreq) */
 113     U32  litLengthSumBasePrice;  /* to compare to log2(llfreq)  */
 114     U32  matchLengthSumBasePrice;/* to compare to log2(mlfreq)  */
 115     U32  offCodeSumBasePrice;    /* to compare to log2(offreq)  */
 116     ZSTD_OptPrice_e priceType;   /* prices can be determined dynamically, or follow a pre-defined cost structure */
 117     const ZSTD_entropyCTables_t* symbolCosts;  /* pre-calculated dictionary statistics */
 118     ZSTD_literalCompressionMode_e literalCompressionMode;
 119 } optState_t;
 120
 121 typedef struct {
 122   ZSTD_entropyCTables_t entropy;
 123   U32 rep[ZSTD_REP_NUM];
 124 } ZSTD_compressedBlockState_t;
 125
 126 typedef struct {
 127     BYTE const* nextSrc;    /* next block here to continue on current prefix */
 128     BYTE const* base;       /* All regular indexes relative to this position */
 129     BYTE const* dictBase;   /* extDict indexes relative to this position */
 130     U32 dictLimit;          /* below that point, need extDict */
 131     U32 lowLimit;           /* below that point, no more data */
 132 } ZSTD_window_t;
 133
 134 typedef struct ZSTD_matchState_t ZSTD_matchState_t;
 135 struct ZSTD_matchState_t {
 136     ZSTD_window_t window;   /* State for window round buffer management */
 137     U32 loadedDictEnd;      /* index of end of dictionary */
 138     U32 nextToUpdate;       /* index from which to continue table update */
 139     U32 nextToUpdate3;      /* index from which to continue table update */
 140     U32 hashLog3;           /* dispatch table : larger == faster, more memory */
 141     U32* hashTable;
 142     U32* hashTable3;
 143     U32* chainTable;
 144     optState_t opt;         /* optimal parser state */
 145     const ZSTD_matchState_t * dictMatchState;
 146     ZSTD_compressionParameters cParams;
 147 };
 148
 149 typedef struct {
 150     ZSTD_compressedBlockState_t* prevCBlock;
 151     ZSTD_compressedBlockState_t* nextCBlock;
 152     ZSTD_matchState_t matchState;
 153 } ZSTD_blockState_t;
 154
 155 typedef struct {
 156     U32 offset;
 157     U32 checksum;
 158 } ldmEntry_t;
 159
 160 typedef struct {
 161     ZSTD_window_t window;   /* State for the window round buffer management */
 162     ldmEntry_t* hashTable;
 163     BYTE* bucketOffsets;    /* Next position in bucket to insert entry */
 164     U64 hashPower;          /* Used to compute the rolling hash.
 165                              * Depends on ldmParams.minMatchLength */
 166 } ldmState_t;
 167
 168 typedef struct {
 169     U32 enableLdm;          /* 1 if enable long distance matching */
 170     U32 hashLog;            /* Log size of hashTable */
 171     U32 bucketSizeLog;      /* Log bucket size for collision resolution, at most 8 */
 172     U32 minMatchLength;     /* Minimum match length */
 173     U32 hashRateLog;       /* Log number of entries to skip */
 174     U32 windowLog;          /* Window log for the LDM */
 175 } ldmParams_t;
 176
 177 typedef struct {
 178     U32 offset;
 179     U32 litLength;
 180     U32 matchLength;
 181 } rawSeq;
 182
 183 typedef struct {
 184   rawSeq* seq;     /* The start of the sequences */
 185   size_t pos;      /* The position where reading stopped. <= size. */
 186   size_t size;     /* The number of sequences. <= capacity. */
 187   size_t capacity; /* The capacity starting from `seq` pointer */
 188 } rawSeqStore_t;
 189
 190 struct ZSTD_CCtx_params_s {
 191     ZSTD_format_e format;
 192     ZSTD_compressionParameters cParams;
 193     ZSTD_frameParameters fParams;
 194
 195     int compressionLevel;
 196     int forceWindow;           /* force back-references to respect limit of
 197                                 * 1<<wLog, even for dictionary */
 198
 199     ZSTD_dictAttachPref_e attachDictPref;
 200     ZSTD_literalCompressionMode_e literalCompressionMode;
 201
 202     /* Multithreading: used to pass parameters to mtctx */
 203     int nbWorkers;
 204     size_t jobSize;
 205     int overlapLog;
 206     int rsyncable;
 207
 208     /* Long distance matching parameters */
 209     ldmParams_t ldmParams;
 210
 211     /* Internal use, for createCCtxParams() and freeCCtxParams() only */
 212     ZSTD_customMem customMem;
 213 };  /* typedef'd to ZSTD_CCtx_params within "zstd.h" */
 214
 215 struct ZSTD_CCtx_s {
 216     ZSTD_compressionStage_e stage;
 217     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. */
 218     int bmi2;                            /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */
 219     ZSTD_CCtx_params requestedParams;
 220     ZSTD_CCtx_params appliedParams;
 221     U32   dictID;
 222
 223     int workSpaceOversizedDuration;
 224     void* workSpace;
 225     size_t workSpaceSize;
 226     size_t blockSize;
 227     unsigned long long pledgedSrcSizePlusOne;  /* this way, 0 (default) == unknown */
 228     unsigned long long consumedSrcSize;
 229     unsigned long long producedCSize;
 230     XXH64_state_t xxhState;
 231     ZSTD_customMem customMem;
 232     size_t staticSize;
 233
 234     seqStore_t seqStore;      /* sequences storage ptrs */
 235     ldmState_t ldmState;      /* long distance matching state */
 236     rawSeq* ldmSequences;     /* Storage for the ldm output sequences */
 237     size_t maxNbLdmSequences;
 238     rawSeqStore_t externSeqStore; /* Mutable reference to external sequences */
 239     ZSTD_blockState_t blockState;
 240     U32* entropyWorkspace;  /* entropy workspace of HUF_WORKSPACE_SIZE bytes */
 241
 242     /* streaming */
 243     char*  inBuff;
 244     size_t inBuffSize;
 245     size_t inToCompress;
 246     size_t inBuffPos;
 247     size_t inBuffTarget;
 248     char*  outBuff;
 249     size_t outBuffSize;
 250     size_t outBuffContentSize;
 251     size_t outBuffFlushedSize;
 252     ZSTD_cStreamStage streamStage;
 253     U32    frameEnded;
 254
 255     /* Dictionary */
 256     ZSTD_localDict localDict;
 257     const ZSTD_CDict* cdict;
 258     ZSTD_prefixDict prefixDict;   /* single-usage dictionary */
 259
 260     /* Multi-threading */
 261 #ifdef ZSTD_MULTITHREAD
 262     ZSTDMT_CCtx* mtctx;
 263 #endif
 264 };
 265
 266 typedef enum { ZSTD_dtlm_fast, ZSTD_dtlm_full } ZSTD_dictTableLoadMethod_e;
 267
 268 typedef enum { ZSTD_noDict = 0, ZSTD_extDict = 1, ZSTD_dictMatchState = 2 } ZSTD_dictMode_e;
 269
 270
 271 typedef size_t (*ZSTD_blockCompressor) (
 272         ZSTD_matchState_t* bs, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
 273         void const* src, size_t srcSize);
 274 ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, ZSTD_dictMode_e dictMode);
 275
 276
 277 MEM_STATIC U32 ZSTD_LLcode(U32 litLength)
 278 {
 279     static const BYTE LL_Code[64] = {  0,  1,  2,  3,  4,  5,  6,  7,
 280                                        8,  9, 10, 11, 12, 13, 14, 15,
 281                                       16, 16, 17, 17, 18, 18, 19, 19,
 282                                       20, 20, 20, 20, 21, 21, 21, 21,
 283                                       22, 22, 22, 22, 22, 22, 22, 22,
 284                                       23, 23, 23, 23, 23, 23, 23, 23,
 285                                       24, 24, 24, 24, 24, 24, 24, 24,
 286                                       24, 24, 24, 24, 24, 24, 24, 24 };
 287     static const U32 LL_deltaCode = 19;
 288     return (litLength > 63) ? ZSTD_highbit32(litLength) + LL_deltaCode : LL_Code[litLength];
 289 }
 290
 291 /* ZSTD_MLcode() :
 292  * note : mlBase = matchLength - MINMATCH;
 293  *        because it's the format it's stored in seqStore->sequences */
 294 MEM_STATIC U32 ZSTD_MLcode(U32 mlBase)
 295 {
 296     static const BYTE ML_Code[128] = { 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15,
 297                                       16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
 298                                       32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37,
 299                                       38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39,
 300                                       40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
 301                                       41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,
 302                                       42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
 303                                       42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42 };
 304     static const U32 ML_deltaCode = 36;
 305     return (mlBase > 127) ? ZSTD_highbit32(mlBase) + ML_deltaCode : ML_Code[mlBase];
 306 }
 307
 308 /*! ZSTD_storeSeq() :
 309  *  Store a sequence (literal length, literals, offset code and match length code) into seqStore_t.
 310  *  `offsetCode` : distance to match + 3 (values 1-3 are repCodes).
 311  *  `mlBase` : matchLength - MINMATCH
 312 */
 313 MEM_STATIC void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const void* literals, U32 offsetCode, size_t mlBase)
 314 {
 315 #if defined(DEBUGLEVEL) && (DEBUGLEVEL >= 6)
 316     static const BYTE* g_start = NULL;
 317     if (g_start==NULL) g_start = (const BYTE*)literals;  /* note : index only works for compression within a single segment */
 318     {   U32 const pos = (U32)((const BYTE*)literals - g_start);
 319         DEBUGLOG(6, "Cpos%7u :%3u literals, match%4u bytes at offCode%7u",
 320                pos, (U32)litLength, (U32)mlBase+MINMATCH, (U32)offsetCode);
 321     }
 322 #endif
 323     assert((size_t)(seqStorePtr->sequences - seqStorePtr->sequencesStart) < seqStorePtr->maxNbSeq);
 324     /* copy Literals */
 325     assert(seqStorePtr->maxNbLit <= 128 KB);
 326     assert(seqStorePtr->lit + litLength <= seqStorePtr->litStart + seqStorePtr->maxNbLit);
 327     ZSTD_wildcopy(seqStorePtr->lit, literals, litLength);
 328     seqStorePtr->lit += litLength;
 329
 330     /* literal Length */
 331     if (litLength>0xFFFF) {
 332         assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
 333         seqStorePtr->longLengthID = 1;
 334         seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
 335     }
 336     seqStorePtr->sequences[0].litLength = (U16)litLength;
 337
 338     /* match offset */
 339     seqStorePtr->sequences[0].offset = offsetCode + 1;
 340
 341     /* match Length */
 342     if (mlBase>0xFFFF) {
 343         assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
 344         seqStorePtr->longLengthID = 2;
 345         seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
 346     }
 347     seqStorePtr->sequences[0].matchLength = (U16)mlBase;
 348
 349     seqStorePtr->sequences++;
 350 }
 351
 352
 353 /*-*************************************
 354 *  Match length counter
 355 ***************************************/
 356 static unsigned ZSTD_NbCommonBytes (size_t val)
 357 {
 358     if (MEM_isLittleEndian()) {
 359         if (MEM_64bits()) {
 360 #       if defined(_MSC_VER) && defined(_WIN64)
 361             unsigned long r = 0;
 362             _BitScanForward64( &r, (U64)val );
 363             return (unsigned)(r>>3);
 364 #       elif defined(__GNUC__) && (__GNUC__ >= 4)
 365             return (__builtin_ctzll((U64)val) >> 3);
 366 #       else
 367             static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2,
 368                                                      0, 3, 1, 3, 1, 4, 2, 7,
 369                                                      0, 2, 3, 6, 1, 5, 3, 5,
 370                                                      1, 3, 4, 4, 2, 5, 6, 7,
 371                                                      7, 0, 1, 2, 3, 3, 4, 6,
 372                                                      2, 6, 5, 5, 3, 4, 5, 6,
 373                                                      7, 1, 2, 4, 6, 4, 4, 5,
 374                                                      7, 2, 6, 5, 7, 6, 7, 7 };
 375             return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
 376 #       endif
 377         } else { /* 32 bits */
 378 #       if defined(_MSC_VER)
 379             unsigned long r=0;
 380             _BitScanForward( &r, (U32)val );
 381             return (unsigned)(r>>3);
 382 #       elif defined(__GNUC__) && (__GNUC__ >= 3)
 383             return (__builtin_ctz((U32)val) >> 3);
 384 #       else
 385             static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0,
 386                                                      3, 2, 2, 1, 3, 2, 0, 1,
 387                                                      3, 3, 1, 2, 2, 2, 2, 0,
 388                                                      3, 1, 2, 0, 1, 0, 1, 1 };
 389             return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
 390 #       endif
 391         }
 392     } else {  /* Big Endian CPU */
 393         if (MEM_64bits()) {
 394 #       if defined(_MSC_VER) && defined(_WIN64)
 395             unsigned long r = 0;
 396             _BitScanReverse64( &r, val );
 397             return (unsigned)(r>>3);
 398 #       elif defined(__GNUC__) && (__GNUC__ >= 4)
 399             return (__builtin_clzll(val) >> 3);
 400 #       else
 401             unsigned r;
 402             const unsigned n32 = sizeof(size_t)*4;   /* calculate this way due to compiler complaining in 32-bits mode */
 403             if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }
 404             if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
 405             r += (!val);
 406             return r;
 407 #       endif
 408         } else { /* 32 bits */
 409 #       if defined(_MSC_VER)
 410             unsigned long r = 0;
 411             _BitScanReverse( &r, (unsigned long)val );
 412             return (unsigned)(r>>3);
 413 #       elif defined(__GNUC__) && (__GNUC__ >= 3)
 414             return (__builtin_clz((U32)val) >> 3);
 415 #       else
 416             unsigned r;
 417             if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
 418             r += (!val);
 419             return r;
 420 #       endif
 421     }   }
 422 }
 423
 424
 425 MEM_STATIC size_t ZSTD_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* const pInLimit)
 426 {
 427     const BYTE* const pStart = pIn;
 428     const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1);
 429
 430     if (pIn < pInLoopLimit) {
 431         { size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
 432           if (diff) return ZSTD_NbCommonBytes(diff); }
 433         pIn+=sizeof(size_t); pMatch+=sizeof(size_t);
 434         while (pIn < pInLoopLimit) {
 435             size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
 436             if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; }
 437             pIn += ZSTD_NbCommonBytes(diff);
 438             return (size_t)(pIn - pStart);
 439     }   }
 440     if (MEM_64bits() && (pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatch+=4; }
 441     if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; }
 442     if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;
 443     return (size_t)(pIn - pStart);
 444 }
 445
 446 /** ZSTD_count_2segments() :
 447  *  can count match length with `ip` & `match` in 2 different segments.
 448  *  convention : on reaching mEnd, match count continue starting from iStart
 449  */
 450 MEM_STATIC size_t
 451 ZSTD_count_2segments(const BYTE* ip, const BYTE* match,
 452                      const BYTE* iEnd, const BYTE* mEnd, const BYTE* iStart)
 453 {
 454     const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd);
 455     size_t const matchLength = ZSTD_count(ip, match, vEnd);
 456     if (match + matchLength != mEnd) return matchLength;
 457     DEBUGLOG(7, "ZSTD_count_2segments: found a 2-parts match (current length==%zu)", matchLength);
 458     DEBUGLOG(7, "distance from match beginning to end dictionary = %zi", mEnd - match);
 459     DEBUGLOG(7, "distance from current pos to end buffer = %zi", iEnd - ip);
 460     DEBUGLOG(7, "next byte : ip==%02X, istart==%02X", ip[matchLength], *iStart);
 461     DEBUGLOG(7, "final match length = %zu", matchLength + ZSTD_count(ip+matchLength, iStart, iEnd));
 462     return matchLength + ZSTD_count(ip+matchLength, iStart, iEnd);
 463 }
 464
 465
 466 /*-*************************************
 467  *  Hashes
 468  ***************************************/
 469 static const U32 prime3bytes = 506832829U;
 470 static U32    ZSTD_hash3(U32 u, U32 h) { return ((u << (32-24)) * prime3bytes)  >> (32-h) ; }
 471 MEM_STATIC size_t ZSTD_hash3Ptr(const void* ptr, U32 h) { return ZSTD_hash3(MEM_readLE32(ptr), h); } /* only in zstd_opt.h */
 472
 473 static const U32 prime4bytes = 2654435761U;
 474 static U32    ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32-h) ; }
 475 static size_t ZSTD_hash4Ptr(const void* ptr, U32 h) { return ZSTD_hash4(MEM_read32(ptr), h); }
 476
 477 static const U64 prime5bytes = 889523592379ULL;
 478 static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u  << (64-40)) * prime5bytes) >> (64-h)) ; }
 479 static size_t ZSTD_hash5Ptr(const void* p, U32 h) { return ZSTD_hash5(MEM_readLE64(p), h); }
 480
 481 static const U64 prime6bytes = 227718039650203ULL;
 482 static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u  << (64-48)) * prime6bytes) >> (64-h)) ; }
 483 static size_t ZSTD_hash6Ptr(const void* p, U32 h) { return ZSTD_hash6(MEM_readLE64(p), h); }
 484
 485 static const U64 prime7bytes = 58295818150454627ULL;
 486 static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u  << (64-56)) * prime7bytes) >> (64-h)) ; }
 487 static size_t ZSTD_hash7Ptr(const void* p, U32 h) { return ZSTD_hash7(MEM_readLE64(p), h); }
 488
 489 static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL;
 490 static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; }
 491 static size_t ZSTD_hash8Ptr(const void* p, U32 h) { return ZSTD_hash8(MEM_readLE64(p), h); }
 492
 493 MEM_STATIC size_t ZSTD_hashPtr(const void* p, U32 hBits, U32 mls)
 494 {
 495     switch(mls)
 496     {
 497     default:
 498     case 4: return ZSTD_hash4Ptr(p, hBits);
 499     case 5: return ZSTD_hash5Ptr(p, hBits);
 500     case 6: return ZSTD_hash6Ptr(p, hBits);
 501     case 7: return ZSTD_hash7Ptr(p, hBits);
 502     case 8: return ZSTD_hash8Ptr(p, hBits);
 503     }
 504 }
 505
 506 /** ZSTD_ipow() :
 507  * Return base^exponent.
 508  */
 509 static U64 ZSTD_ipow(U64 base, U64 exponent)
 510 {
 511     U64 power = 1;
 512     while (exponent) {
 513       if (exponent & 1) power *= base;
 514       exponent >>= 1;
 515       base *= base;
 516     }
 517     return power;
 518 }
 519
 520 #define ZSTD_ROLL_HASH_CHAR_OFFSET 10
 521
 522 /** ZSTD_rollingHash_append() :
 523  * Add the buffer to the hash value.
 524  */
 525 static U64 ZSTD_rollingHash_append(U64 hash, void const* buf, size_t size)
 526 {
 527     BYTE const* istart = (BYTE const*)buf;
 528     size_t pos;
 529     for (pos = 0; pos < size; ++pos) {
 530         hash *= prime8bytes;
 531         hash += istart[pos] + ZSTD_ROLL_HASH_CHAR_OFFSET;
 532     }
 533     return hash;
 534 }
 535
 536 /** ZSTD_rollingHash_compute() :
 537  * Compute the rolling hash value of the buffer.
 538  */
 539 MEM_STATIC U64 ZSTD_rollingHash_compute(void const* buf, size_t size)
 540 {
 541     return ZSTD_rollingHash_append(0, buf, size);
 542 }
 543
 544 /** ZSTD_rollingHash_primePower() :
 545  * Compute the primePower to be passed to ZSTD_rollingHash_rotate() for a hash
 546  * over a window of length bytes.
 547  */
 548 MEM_STATIC U64 ZSTD_rollingHash_primePower(U32 length)
 549 {
 550     return ZSTD_ipow(prime8bytes, length - 1);
 551 }
 552
 553 /** ZSTD_rollingHash_rotate() :
 554  * Rotate the rolling hash by one byte.
 555  */
 556 MEM_STATIC U64 ZSTD_rollingHash_rotate(U64 hash, BYTE toRemove, BYTE toAdd, U64 primePower)
 557 {
 558     hash -= (toRemove + ZSTD_ROLL_HASH_CHAR_OFFSET) * primePower;
 559     hash *= prime8bytes;
 560     hash += toAdd + ZSTD_ROLL_HASH_CHAR_OFFSET;
 561     return hash;
 562 }
 563
 564 /*-*************************************
 565 *  Round buffer management
 566 ***************************************/
 567 /* Max current allowed */
 568 #define ZSTD_CURRENT_MAX ((3U << 29) + (1U << ZSTD_WINDOWLOG_MAX))
 569 /* Maximum chunk size before overflow correction needs to be called again */
 570 #define ZSTD_CHUNKSIZE_MAX                                                     \
 571     ( ((U32)-1)                  /* Maximum ending current index */            \
 572     - ZSTD_CURRENT_MAX)          /* Maximum beginning lowLimit */
 573
 574 /**
 575  * ZSTD_window_clear():
 576  * Clears the window containing the history by simply setting it to empty.
 577  */
 578 MEM_STATIC void ZSTD_window_clear(ZSTD_window_t* window)
 579 {
 580     size_t const endT = (size_t)(window->nextSrc - window->base);
 581     U32 const end = (U32)endT;
 582
 583     window->lowLimit = end;
 584     window->dictLimit = end;
 585 }
 586
 587 /**
 588  * ZSTD_window_hasExtDict():
 589  * Returns non-zero if the window has a non-empty extDict.
 590  */
 591 MEM_STATIC U32 ZSTD_window_hasExtDict(ZSTD_window_t const window)
 592 {
 593     return window.lowLimit < window.dictLimit;
 594 }
 595
 596 /**
 597  * ZSTD_matchState_dictMode():
 598  * Inspects the provided matchState and figures out what dictMode should be
 599  * passed to the compressor.
 600  */
 601 MEM_STATIC ZSTD_dictMode_e ZSTD_matchState_dictMode(const ZSTD_matchState_t *ms)
 602 {
 603     return ZSTD_window_hasExtDict(ms->window) ?
 604         ZSTD_extDict :
 605         ms->dictMatchState != NULL ?
 606             ZSTD_dictMatchState :
 607             ZSTD_noDict;
 608 }
 609
 610 /**
 611  * ZSTD_window_needOverflowCorrection():
 612  * Returns non-zero if the indices are getting too large and need overflow
 613  * protection.
 614  */
 615 MEM_STATIC U32 ZSTD_window_needOverflowCorrection(ZSTD_window_t const window,
 616                                                   void const* srcEnd)
 617 {
 618     U32 const current = (U32)((BYTE const*)srcEnd - window.base);
 619     return current > ZSTD_CURRENT_MAX;
 620 }
 621
 622 /**
 623  * ZSTD_window_correctOverflow():
 624  * Reduces the indices to protect from index overflow.
 625  * Returns the correction made to the indices, which must be applied to every
 626  * stored index.
 627  *
 628  * The least significant cycleLog bits of the indices must remain the same,
 629  * which may be 0. Every index up to maxDist in the past must be valid.
 630  * NOTE: (maxDist & cycleMask) must be zero.
 631  */
 632 MEM_STATIC U32 ZSTD_window_correctOverflow(ZSTD_window_t* window, U32 cycleLog,
 633                                            U32 maxDist, void const* src)
 634 {
 635     /* preemptive overflow correction:
 636      * 1. correction is large enough:
 637      *    lowLimit > (3<<29) ==> current > 3<<29 + 1<<windowLog
 638      *    1<<windowLog <= newCurrent < 1<<chainLog + 1<<windowLog
 639      *
 640      *    current - newCurrent
 641      *    > (3<<29 + 1<<windowLog) - (1<<windowLog + 1<<chainLog)
 642      *    > (3<<29) - (1<<chainLog)
 643      *    > (3<<29) - (1<<30)             (NOTE: chainLog <= 30)
 644      *    > 1<<29
 645      *
 646      * 2. (ip+ZSTD_CHUNKSIZE_MAX - cctx->base) doesn't overflow:
 647      *    After correction, current is less than (1<<chainLog + 1<<windowLog).
 648      *    In 64-bit mode we are safe, because we have 64-bit ptrdiff_t.
 649      *    In 32-bit mode we are safe, because (chainLog <= 29), so
 650      *    ip+ZSTD_CHUNKSIZE_MAX - cctx->base < 1<<32.
 651      * 3. (cctx->lowLimit + 1<<windowLog) < 1<<32:
 652      *    windowLog <= 31 ==> 3<<29 + 1<<windowLog < 7<<29 < 1<<32.
 653      */
 654     U32 const cycleMask = (1U << cycleLog) - 1;
 655     U32 const current = (U32)((BYTE const*)src - window->base);
 656     U32 const newCurrent = (current & cycleMask) + maxDist;
 657     U32 const correction = current - newCurrent;
 658     assert((maxDist & cycleMask) == 0);
 659     assert(current > newCurrent);
 660     /* Loose bound, should be around 1<<29 (see above) */
 661     assert(correction > 1<<28);
 662
 663     window->base += correction;
 664     window->dictBase += correction;
 665     window->lowLimit -= correction;
 666     window->dictLimit -= correction;
 667
 668     DEBUGLOG(4, "Correction of 0x%x bytes to lowLimit=0x%x", correction,
 669              window->lowLimit);
 670     return correction;
 671 }
 672
 673 /**
 674  * ZSTD_window_enforceMaxDist():
 675  * Updates lowLimit so that:
 676  *    (srcEnd - base) - lowLimit == maxDist + loadedDictEnd
 677  *
 678  * This allows a simple check that index >= lowLimit to see if index is valid.
 679  * This must be called before a block compression call, with srcEnd as the block
 680  * source end.
 681  *
 682  * If loadedDictEndPtr is not NULL, we set it to zero once we update lowLimit.
 683  * This is because dictionaries are allowed to be referenced as long as the last
 684  * byte of the dictionary is in the window, but once they are out of range,
 685  * they cannot be referenced. If loadedDictEndPtr is NULL, we use
 686  * loadedDictEnd == 0.
 687  *
 688  * In normal dict mode, the dict is between lowLimit and dictLimit. In
 689  * dictMatchState mode, lowLimit and dictLimit are the same, and the dictionary
 690  * is below them. forceWindow and dictMatchState are therefore incompatible.
 691  */
 692 MEM_STATIC void
 693 ZSTD_window_enforceMaxDist(ZSTD_window_t* window,
 694                            void const* srcEnd,
 695                            U32 maxDist,
 696                            U32* loadedDictEndPtr,
 697                      const ZSTD_matchState_t** dictMatchStatePtr)
 698 {
 699     U32 const blockEndIdx = (U32)((BYTE const*)srcEnd - window->base);
 700     U32 loadedDictEnd = (loadedDictEndPtr != NULL) ? *loadedDictEndPtr : 0;
 701     DEBUGLOG(5, "ZSTD_window_enforceMaxDist: blockEndIdx=%u, maxDist=%u",
 702                 (unsigned)blockEndIdx, (unsigned)maxDist);
 703     if (blockEndIdx > maxDist + loadedDictEnd) {
 704         U32 const newLowLimit = blockEndIdx - maxDist;
 705         if (window->lowLimit < newLowLimit) window->lowLimit = newLowLimit;
 706         if (window->dictLimit < window->lowLimit) {
 707             DEBUGLOG(5, "Update dictLimit to match lowLimit, from %u to %u",
 708                         (unsigned)window->dictLimit, (unsigned)window->lowLimit);
 709             window->dictLimit = window->lowLimit;
 710         }
 711         if (loadedDictEndPtr)
 712             *loadedDictEndPtr = 0;
 713         if (dictMatchStatePtr)
 714             *dictMatchStatePtr = NULL;
 715     }
 716 }
 717
 718 /**
 719  * ZSTD_window_update():
 720  * Updates the window by appending [src, src + srcSize) to the window.
 721  * If it is not contiguous, the current prefix becomes the extDict, and we
 722  * forget about the extDict. Handles overlap of the prefix and extDict.
 723  * Returns non-zero if the segment is contiguous.
 724  */
 725 MEM_STATIC U32 ZSTD_window_update(ZSTD_window_t* window,
 726                                   void const* src, size_t srcSize)
 727 {
 728     BYTE const* const ip = (BYTE const*)src;
 729     U32 contiguous = 1;
 730     DEBUGLOG(5, "ZSTD_window_update");
 731     /* Check if blocks follow each other */
 732     if (src != window->nextSrc) {
 733         /* not contiguous */
 734         size_t const distanceFromBase = (size_t)(window->nextSrc - window->base);
 735         DEBUGLOG(5, "Non contiguous blocks, new segment starts at %u", window->dictLimit);
 736         window->lowLimit = window->dictLimit;
 737         assert(distanceFromBase == (size_t)(U32)distanceFromBase);  /* should never overflow */
 738         window->dictLimit = (U32)distanceFromBase;
 739         window->dictBase = window->base;
 740         window->base = ip - distanceFromBase;
 741         // ms->nextToUpdate = window->dictLimit;
 742         if (window->dictLimit - window->lowLimit < HASH_READ_SIZE) window->lowLimit = window->dictLimit;   /* too small extDict */
 743         contiguous = 0;
 744     }
 745     window->nextSrc = ip + srcSize;
 746     /* if input and dictionary overlap : reduce dictionary (area presumed modified by input) */
 747     if ( (ip+srcSize > window->dictBase + window->lowLimit)
 748        & (ip < window->dictBase + window->dictLimit)) {
 749         ptrdiff_t const highInputIdx = (ip + srcSize) - window->dictBase;
 750         U32 const lowLimitMax = (highInputIdx > (ptrdiff_t)window->dictLimit) ? window->dictLimit : (U32)highInputIdx;
 751         window->lowLimit = lowLimitMax;
 752         DEBUGLOG(5, "Overlapping extDict and input : new lowLimit = %u", window->lowLimit);
 753     }
 754     return contiguous;
 755 }
 756
 757
 758 /* debug functions */
 759 #if (DEBUGLEVEL>=2)
 760
 761 MEM_STATIC double ZSTD_fWeight(U32 rawStat)
 762 {
 763     U32 const fp_accuracy = 8;
 764     U32 const fp_multiplier = (1 << fp_accuracy);
 765     U32 const newStat = rawStat + 1;
 766     U32 const hb = ZSTD_highbit32(newStat);
 767     U32 const BWeight = hb * fp_multiplier;
 768     U32 const FWeight = (newStat << fp_accuracy) >> hb;
 769     U32 const weight = BWeight + FWeight;
 770     assert(hb + fp_accuracy < 31);
 771     return (double)weight / fp_multiplier;
 772 }
 773
 774 /* display a table content,
 775  * listing each element, its frequency, and its predicted bit cost */
 776 MEM_STATIC void ZSTD_debugTable(const U32* table, U32 max)
 777 {
 778     unsigned u, sum;
 779     for (u=0, sum=0; u<=max; u++) sum += table[u];
 780     DEBUGLOG(2, "total nb elts: %u", sum);
 781     for (u=0; u<=max; u++) {
 782         DEBUGLOG(2, "%2u: %5u  (%.2f)",
 783                 u, table[u], ZSTD_fWeight(sum) - ZSTD_fWeight(table[u]) );
 784     }
 785 }
 786
 787 #endif
 788
 789
 790 #if defined (__cplusplus)
 791 }
 792 #endif
 793
 794
 795 /* ==============================================================
 796  * Private declarations
 797  * These prototypes shall only be called from within lib/compress
 798  * ============================================================== */
 799
 800 /* ZSTD_getCParamsFromCCtxParams() :
 801  * cParams are built depending on compressionLevel, src size hints,
 802  * LDM and manually set compression parameters.
 803  */
 804 ZSTD_compressionParameters ZSTD_getCParamsFromCCtxParams(
 805         const ZSTD_CCtx_params* CCtxParams, U64 srcSizeHint, size_t dictSize);
 806
 807 /*! ZSTD_initCStream_internal() :
 808  *  Private use only. Init streaming operation.
 809  *  expects params to be valid.
 810  *  must receive dict, or cdict, or none, but not both.
 811  *  @return : 0, or an error code */
 812 size_t ZSTD_initCStream_internal(ZSTD_CStream* zcs,
 813                      const void* dict, size_t dictSize,
 814                      const ZSTD_CDict* cdict,
 815                      ZSTD_CCtx_params  params, unsigned long long pledgedSrcSize);
 816
 817 void ZSTD_resetSeqStore(seqStore_t* ssPtr);
 818
 819 /*! ZSTD_getCParamsFromCDict() :
 820  *  as the name implies */
 821 ZSTD_compressionParameters ZSTD_getCParamsFromCDict(const ZSTD_CDict* cdict);
 822
 823 /* ZSTD_compressBegin_advanced_internal() :
 824  * Private use only. To be called from zstdmt_compress.c. */
 825 size_t ZSTD_compressBegin_advanced_internal(ZSTD_CCtx* cctx,
 826                                     const void* dict, size_t dictSize,
 827                                     ZSTD_dictContentType_e dictContentType,
 828                                     ZSTD_dictTableLoadMethod_e dtlm,
 829                                     const ZSTD_CDict* cdict,
 830                                     ZSTD_CCtx_params params,
 831                                     unsigned long long pledgedSrcSize);
 832
 833 /* ZSTD_compress_advanced_internal() :
 834  * Private use only. To be called from zstdmt_compress.c. */
 835 size_t ZSTD_compress_advanced_internal(ZSTD_CCtx* cctx,
 836                                        void* dst, size_t dstCapacity,
 837                                  const void* src, size_t srcSize,
 838                                  const void* dict,size_t dictSize,
 839                                  ZSTD_CCtx_params params);
 840
 841
 842 /* ZSTD_writeLastEmptyBlock() :
 843  * output an empty Block with end-of-frame mark to complete a frame
 844  * @return : size of data written into `dst` (== ZSTD_blockHeaderSize (defined in zstd_internal.h))
 845  *           or an error code if `dstCapacity` is too small (<ZSTD_blockHeaderSize)
 846  */
 847 size_t ZSTD_writeLastEmptyBlock(void* dst, size_t dstCapacity);
 848
 849
 850 /* ZSTD_referenceExternalSequences() :
 851  * Must be called before starting a compression operation.
 852  * seqs must parse a prefix of the source.
 853  * This cannot be used when long range matching is enabled.
 854  * Zstd will use these sequences, and pass the literals to a secondary block
 855  * compressor.
 856  * @return : An error code on failure.
 857  * NOTE: seqs are not verified! Invalid sequences can cause out-of-bounds memory
 858  * access and data corruption.
 859  */
 860 size_t ZSTD_referenceExternalSequences(ZSTD_CCtx* cctx, rawSeq* seq, size_t nbSeq);
 861
 862
 863 #endif /* ZSTD_COMPRESS_H */