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