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 *  Constants
  32 ***************************************/
  33 static const U32 g_searchStrength = 8;
  34 #define HASH_READ_SIZE 8
  35
  36
  37 /*-*************************************
  38 *  Context memory management
  39 ***************************************/
  40 typedef enum { ZSTDcs_created=0, ZSTDcs_init, ZSTDcs_ongoing, ZSTDcs_ending } ZSTD_compressionStage_e;
  41 typedef enum { zcss_init=0, zcss_load, zcss_flush } ZSTD_cStreamStage;
  42
  43 typedef struct ZSTD_prefixDict_s {
  44     const void* dict;
  45     size_t dictSize;
  46     ZSTD_dictMode_e dictMode;
  47 } ZSTD_prefixDict;
  48
  49 typedef struct {
  50     U32 hufCTable[HUF_CTABLE_SIZE_U32(255)];
  51     FSE_CTable offcodeCTable[FSE_CTABLE_SIZE_U32(OffFSELog, MaxOff)];
  52     FSE_CTable matchlengthCTable[FSE_CTABLE_SIZE_U32(MLFSELog, MaxML)];
  53     FSE_CTable litlengthCTable[FSE_CTABLE_SIZE_U32(LLFSELog, MaxLL)];
  54     U32 workspace[HUF_WORKSPACE_SIZE_U32];
  55     HUF_repeat hufCTable_repeatMode;
  56     FSE_repeat offcode_repeatMode;
  57     FSE_repeat matchlength_repeatMode;
  58     FSE_repeat litlength_repeatMode;
  59 } ZSTD_entropyCTables_t;
  60
  61 typedef struct {
  62     U32 off;
  63     U32 len;
  64 } ZSTD_match_t;
  65
  66 typedef struct {
  67     int price;
  68     U32 off;
  69     U32 mlen;
  70     U32 litlen;
  71     U32 rep[ZSTD_REP_NUM];
  72 } ZSTD_optimal_t;
  73
  74 typedef struct {
  75     /* All tables are allocated inside cctx->workspace by ZSTD_resetCCtx_internal() */
  76     U32* litFreq;               /* table of literals statistics, of size 256 */
  77     U32* litLengthFreq;         /* table of litLength statistics, of size (MaxLL+1) */
  78     U32* matchLengthFreq;       /* table of matchLength statistics, of size (MaxML+1) */
  79     U32* offCodeFreq;           /* table of offCode statistics, of size (MaxOff+1) */
  80     ZSTD_match_t* matchTable;   /* list of found matches, of size ZSTD_OPT_NUM+1 */
  81     ZSTD_optimal_t* priceTable; /* All positions tracked by optimal parser, of size ZSTD_OPT_NUM+1 */
  82
  83     U32  litSum;                 /* nb of literals */
  84     U32  litLengthSum;           /* nb of litLength codes */
  85     U32  matchLengthSum;         /* nb of matchLength codes */
  86     U32  offCodeSum;             /* nb of offset codes */
  87     /* begin updated by ZSTD_setLog2Prices */
  88     U32  log2litSum;             /* pow2 to compare log2(litfreq) to */
  89     U32  log2litLengthSum;       /* pow2 to compare log2(llfreq) to */
  90     U32  log2matchLengthSum;     /* pow2 to compare log2(mlfreq) to */
  91     U32  log2offCodeSum;         /* pow2 to compare log2(offreq) to */
  92     /* end : updated by ZSTD_setLog2Prices */
  93     U32  staticPrices;           /* prices follow a pre-defined cost structure, statistics are irrelevant */
  94 } optState_t;
  95
  96 typedef struct {
  97     U32 offset;
  98     U32 checksum;
  99 } ldmEntry_t;
 100
 101 typedef struct {
 102     ldmEntry_t* hashTable;
 103     BYTE* bucketOffsets;    /* Next position in bucket to insert entry */
 104     U64 hashPower;          /* Used to compute the rolling hash.
 105                              * Depends on ldmParams.minMatchLength */
 106 } ldmState_t;
 107
 108 typedef struct {
 109     U32 enableLdm;          /* 1 if enable long distance matching */
 110     U32 hashLog;            /* Log size of hashTable */
 111     U32 bucketSizeLog;      /* Log bucket size for collision resolution, at most 8 */
 112     U32 minMatchLength;     /* Minimum match length */
 113     U32 hashEveryLog;       /* Log number of entries to skip */
 114 } ldmParams_t;
 115
 116 struct ZSTD_CCtx_params_s {
 117     ZSTD_format_e format;
 118     ZSTD_compressionParameters cParams;
 119     ZSTD_frameParameters fParams;
 120
 121     int compressionLevel;
 122     U32 forceWindow;           /* force back-references to respect limit of
 123                                 * 1<<wLog, even for dictionary */
 124
 125     /* Multithreading: used to pass parameters to mtctx */
 126     U32 nbThreads;
 127     unsigned jobSize;
 128     unsigned overlapSizeLog;
 129
 130     /* Long distance matching parameters */
 131     ldmParams_t ldmParams;
 132
 133     /* For use with createCCtxParams() and freeCCtxParams() only */
 134     ZSTD_customMem customMem;
 135
 136 };  /* typedef'd to ZSTD_CCtx_params within "zstd.h" */
 137
 138 struct ZSTD_CCtx_s {
 139     const BYTE* nextSrc;    /* next block here to continue on current prefix */
 140     const BYTE* base;       /* All regular indexes relative to this position */
 141     const BYTE* dictBase;   /* extDict indexes relative to this position */
 142     U32   dictLimit;        /* below that point, need extDict */
 143     U32   lowLimit;         /* below that point, no more data */
 144     U32   nextToUpdate;     /* index from which to continue dictionary update */
 145     U32   nextToUpdate3;    /* index from which to continue dictionary update */
 146     U32   hashLog3;         /* dispatch table : larger == faster, more memory */
 147     U32   loadedDictEnd;    /* index of end of dictionary */
 148     ZSTD_compressionStage_e stage;
 149     U32   dictID;
 150     ZSTD_CCtx_params requestedParams;
 151     ZSTD_CCtx_params appliedParams;
 152     void* workSpace;
 153     size_t workSpaceSize;
 154     size_t blockSize;
 155     U64 pledgedSrcSizePlusOne;  /* this way, 0 (default) == unknown */
 156     U64 consumedSrcSize;
 157     XXH64_state_t xxhState;
 158     ZSTD_customMem customMem;
 159     size_t staticSize;
 160
 161     seqStore_t seqStore;    /* sequences storage ptrs */
 162     optState_t optState;
 163     ldmState_t ldmState;    /* long distance matching state */
 164     U32* hashTable;
 165     U32* hashTable3;
 166     U32* chainTable;
 167     ZSTD_entropyCTables_t* entropy;
 168
 169     /* streaming */
 170     char*  inBuff;
 171     size_t inBuffSize;
 172     size_t inToCompress;
 173     size_t inBuffPos;
 174     size_t inBuffTarget;
 175     char*  outBuff;
 176     size_t outBuffSize;
 177     size_t outBuffContentSize;
 178     size_t outBuffFlushedSize;
 179     ZSTD_cStreamStage streamStage;
 180     U32    frameEnded;
 181
 182     /* Dictionary */
 183     ZSTD_CDict* cdictLocal;
 184     const ZSTD_CDict* cdict;
 185     ZSTD_prefixDict prefixDict;   /* single-usage dictionary */
 186
 187     /* Multi-threading */
 188 #ifdef ZSTD_MULTITHREAD
 189     ZSTDMT_CCtx* mtctx;
 190 #endif
 191 };
 192
 193
 194 MEM_STATIC U32 ZSTD_LLcode(U32 litLength)
 195 {
 196     static const BYTE LL_Code[64] = {  0,  1,  2,  3,  4,  5,  6,  7,
 197                                        8,  9, 10, 11, 12, 13, 14, 15,
 198                                       16, 16, 17, 17, 18, 18, 19, 19,
 199                                       20, 20, 20, 20, 21, 21, 21, 21,
 200                                       22, 22, 22, 22, 22, 22, 22, 22,
 201                                       23, 23, 23, 23, 23, 23, 23, 23,
 202                                       24, 24, 24, 24, 24, 24, 24, 24,
 203                                       24, 24, 24, 24, 24, 24, 24, 24 };
 204     static const U32 LL_deltaCode = 19;
 205     return (litLength > 63) ? ZSTD_highbit32(litLength) + LL_deltaCode : LL_Code[litLength];
 206 }
 207
 208 /* ZSTD_MLcode() :
 209  * note : mlBase = matchLength - MINMATCH;
 210  *        because it's the format it's stored in seqStore->sequences */
 211 MEM_STATIC U32 ZSTD_MLcode(U32 mlBase)
 212 {
 213     static const BYTE ML_Code[128] = { 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15,
 214                                       16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
 215                                       32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37,
 216                                       38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39,
 217                                       40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
 218                                       41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,
 219                                       42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
 220                                       42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42 };
 221     static const U32 ML_deltaCode = 36;
 222     return (mlBase > 127) ? ZSTD_highbit32(mlBase) + ML_deltaCode : ML_Code[mlBase];
 223 }
 224
 225 /*! ZSTD_storeSeq() :
 226  *  Store a sequence (literal length, literals, offset code and match length code) into seqStore_t.
 227  *  `offsetCode` : distance to match + 3 (values 1-3 are repCodes).
 228  *  `mlBase` : matchLength - MINMATCH
 229 */
 230 MEM_STATIC void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const void* literals, U32 offsetCode, size_t mlBase)
 231 {
 232 #if defined(ZSTD_DEBUG) && (ZSTD_DEBUG >= 6)
 233     static const BYTE* g_start = NULL;
 234     if (g_start==NULL) g_start = (const BYTE*)literals;  /* note : index only works for compression within a single segment */
 235     {   U32 const pos = (U32)((const BYTE*)literals - g_start);
 236         DEBUGLOG(6, "Cpos%7u :%3u literals, match%3u bytes at dist.code%7u",
 237                pos, (U32)litLength, (U32)mlBase+MINMATCH, (U32)offsetCode);
 238     }
 239 #endif
 240     /* copy Literals */
 241     assert(seqStorePtr->lit + litLength <= seqStorePtr->litStart + 128 KB);
 242     ZSTD_wildcopy(seqStorePtr->lit, literals, litLength);
 243     seqStorePtr->lit += litLength;
 244
 245     /* literal Length */
 246     if (litLength>0xFFFF) {
 247         assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
 248         seqStorePtr->longLengthID = 1;
 249         seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
 250     }
 251     seqStorePtr->sequences[0].litLength = (U16)litLength;
 252
 253     /* match offset */
 254     seqStorePtr->sequences[0].offset = offsetCode + 1;
 255
 256     /* match Length */
 257     if (mlBase>0xFFFF) {
 258         assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
 259         seqStorePtr->longLengthID = 2;
 260         seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
 261     }
 262     seqStorePtr->sequences[0].matchLength = (U16)mlBase;
 263
 264     seqStorePtr->sequences++;
 265 }
 266
 267
 268 /*-*************************************
 269 *  Match length counter
 270 ***************************************/
 271 static unsigned ZSTD_NbCommonBytes (size_t val)
 272 {
 273     if (MEM_isLittleEndian()) {
 274         if (MEM_64bits()) {
 275 #       if defined(_MSC_VER) && defined(_WIN64)
 276             unsigned long r = 0;
 277             _BitScanForward64( &r, (U64)val );
 278             return (unsigned)(r>>3);
 279 #       elif defined(__GNUC__) && (__GNUC__ >= 4)
 280             return (__builtin_ctzll((U64)val) >> 3);
 281 #       else
 282             static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2,
 283                                                      0, 3, 1, 3, 1, 4, 2, 7,
 284                                                      0, 2, 3, 6, 1, 5, 3, 5,
 285                                                      1, 3, 4, 4, 2, 5, 6, 7,
 286                                                      7, 0, 1, 2, 3, 3, 4, 6,
 287                                                      2, 6, 5, 5, 3, 4, 5, 6,
 288                                                      7, 1, 2, 4, 6, 4, 4, 5,
 289                                                      7, 2, 6, 5, 7, 6, 7, 7 };
 290             return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
 291 #       endif
 292         } else { /* 32 bits */
 293 #       if defined(_MSC_VER)
 294             unsigned long r=0;
 295             _BitScanForward( &r, (U32)val );
 296             return (unsigned)(r>>3);
 297 #       elif defined(__GNUC__) && (__GNUC__ >= 3)
 298             return (__builtin_ctz((U32)val) >> 3);
 299 #       else
 300             static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0,
 301                                                      3, 2, 2, 1, 3, 2, 0, 1,
 302                                                      3, 3, 1, 2, 2, 2, 2, 0,
 303                                                      3, 1, 2, 0, 1, 0, 1, 1 };
 304             return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
 305 #       endif
 306         }
 307     } else {  /* Big Endian CPU */
 308         if (MEM_64bits()) {
 309 #       if defined(_MSC_VER) && defined(_WIN64)
 310             unsigned long r = 0;
 311             _BitScanReverse64( &r, val );
 312             return (unsigned)(r>>3);
 313 #       elif defined(__GNUC__) && (__GNUC__ >= 4) && __has_builtin(__builtin_clzll)
 314             return (__builtin_clzll(val) >> 3);
 315 #       else
 316             unsigned r;
 317             const unsigned n32 = sizeof(size_t)*4;   /* calculate this way due to compiler complaining in 32-bits mode */
 318             if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }
 319             if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
 320             r += (!val);
 321             return r;
 322 #       endif
 323         } else { /* 32 bits */
 324 #       if defined(_MSC_VER)
 325             unsigned long r = 0;
 326             _BitScanReverse( &r, (unsigned long)val );
 327             return (unsigned)(r>>3);
 328 #       elif defined(__GNUC__) && (__GNUC__ >= 3) && __has_builtin(__builtin_clz)
 329             return (__builtin_clz((U32)val) >> 3);
 330 #       else
 331             unsigned r;
 332             if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
 333             r += (!val);
 334             return r;
 335 #       endif
 336     }   }
 337 }
 338
 339
 340 MEM_STATIC size_t ZSTD_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* const pInLimit)
 341 {
 342     const BYTE* const pStart = pIn;
 343     const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1);
 344
 345     if (pIn < pInLoopLimit) {
 346         { size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
 347           if (diff) return ZSTD_NbCommonBytes(diff); }
 348         pIn+=sizeof(size_t); pMatch+=sizeof(size_t);
 349         while (pIn < pInLoopLimit) {
 350             size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
 351             if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; }
 352             pIn += ZSTD_NbCommonBytes(diff);
 353             return (size_t)(pIn - pStart);
 354     }   }
 355     if (MEM_64bits() && (pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatch+=4; }
 356     if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; }
 357     if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;
 358     return (size_t)(pIn - pStart);
 359 }
 360
 361 /** ZSTD_count_2segments() :
 362 *   can count match length with `ip` & `match` in 2 different segments.
 363 *   convention : on reaching mEnd, match count continue starting from iStart
 364 */
 365 MEM_STATIC size_t ZSTD_count_2segments(const BYTE* ip, const BYTE* match, const BYTE* iEnd, const BYTE* mEnd, const BYTE* iStart)
 366 {
 367     const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd);
 368     size_t const matchLength = ZSTD_count(ip, match, vEnd);
 369     if (match + matchLength != mEnd) return matchLength;
 370     return matchLength + ZSTD_count(ip+matchLength, iStart, iEnd);
 371 }
 372
 373
 374 /*-*************************************
 375 *  Hashes
 376 ***************************************/
 377 static const U32 prime3bytes = 506832829U;
 378 static U32    ZSTD_hash3(U32 u, U32 h) { return ((u << (32-24)) * prime3bytes)  >> (32-h) ; }
 379 MEM_STATIC size_t ZSTD_hash3Ptr(const void* ptr, U32 h) { return ZSTD_hash3(MEM_readLE32(ptr), h); } /* only in zstd_opt.h */
 380
 381 static const U32 prime4bytes = 2654435761U;
 382 static U32    ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32-h) ; }
 383 static size_t ZSTD_hash4Ptr(const void* ptr, U32 h) { return ZSTD_hash4(MEM_read32(ptr), h); }
 384
 385 static const U64 prime5bytes = 889523592379ULL;
 386 static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u  << (64-40)) * prime5bytes) >> (64-h)) ; }
 387 static size_t ZSTD_hash5Ptr(const void* p, U32 h) { return ZSTD_hash5(MEM_readLE64(p), h); }
 388
 389 static const U64 prime6bytes = 227718039650203ULL;
 390 static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u  << (64-48)) * prime6bytes) >> (64-h)) ; }
 391 static size_t ZSTD_hash6Ptr(const void* p, U32 h) { return ZSTD_hash6(MEM_readLE64(p), h); }
 392
 393 static const U64 prime7bytes = 58295818150454627ULL;
 394 static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u  << (64-56)) * prime7bytes) >> (64-h)) ; }
 395 static size_t ZSTD_hash7Ptr(const void* p, U32 h) { return ZSTD_hash7(MEM_readLE64(p), h); }
 396
 397 static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL;
 398 static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; }
 399 static size_t ZSTD_hash8Ptr(const void* p, U32 h) { return ZSTD_hash8(MEM_readLE64(p), h); }
 400
 401 MEM_STATIC size_t ZSTD_hashPtr(const void* p, U32 hBits, U32 mls)
 402 {
 403     switch(mls)
 404     {
 405     default:
 406     case 4: return ZSTD_hash4Ptr(p, hBits);
 407     case 5: return ZSTD_hash5Ptr(p, hBits);
 408     case 6: return ZSTD_hash6Ptr(p, hBits);
 409     case 7: return ZSTD_hash7Ptr(p, hBits);
 410     case 8: return ZSTD_hash8Ptr(p, hBits);
 411     }
 412 }
 413
 414 #if defined (__cplusplus)
 415 }
 416 #endif
 417
 418
 419 /* ==============================================================
 420  * Private declarations
 421  * These prototypes shall only be called from within lib/compress
 422  * ============================================================== */
 423
 424 /*! ZSTD_initCStream_internal() :
 425  *  Private use only. Init streaming operation.
 426  *  expects params to be valid.
 427  *  must receive dict, or cdict, or none, but not both.
 428  *  @return : 0, or an error code */
 429 size_t ZSTD_initCStream_internal(ZSTD_CStream* zcs,
 430                      const void* dict, size_t dictSize,
 431                      const ZSTD_CDict* cdict,
 432                      ZSTD_CCtx_params  params, unsigned long long pledgedSrcSize);
 433
 434 /*! ZSTD_compressStream_generic() :
 435  *  Private use only. To be called from zstdmt_compress.c in single-thread mode. */
 436 size_t ZSTD_compressStream_generic(ZSTD_CStream* zcs,
 437                                    ZSTD_outBuffer* output,
 438                                    ZSTD_inBuffer* input,
 439                                    ZSTD_EndDirective const flushMode);
 440
 441 /*! ZSTD_getCParamsFromCDict() :
 442  *  as the name implies */
 443 ZSTD_compressionParameters ZSTD_getCParamsFromCDict(const ZSTD_CDict* cdict);
 444
 445 /* ZSTD_compressBegin_advanced_internal() :
 446  * Private use only. To be called from zstdmt_compress.c. */
 447 size_t ZSTD_compressBegin_advanced_internal(ZSTD_CCtx* cctx,
 448                                     const void* dict, size_t dictSize,
 449                                     ZSTD_dictMode_e dictMode,
 450                                     const ZSTD_CDict* cdict,
 451                                     ZSTD_CCtx_params params,
 452                                     unsigned long long pledgedSrcSize);
 453
 454 /* ZSTD_compress_advanced_internal() :
 455  * Private use only. To be called from zstdmt_compress.c. */
 456 size_t ZSTD_compress_advanced_internal(ZSTD_CCtx* cctx,
 457                                        void* dst, size_t dstCapacity,
 458                                  const void* src, size_t srcSize,
 459                                  const void* dict,size_t dictSize,
 460                                  ZSTD_CCtx_params params);
 461
 462 #endif /* ZSTD_COMPRESS_H */