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