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 */ 861