zstd_compress_internal.h (48984B)
1/* 2 * Copyright (c) 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 "../common/zstd_internal.h" 22#include "zstd_cwksp.h" 23 24 25/*-************************************* 26* Constants 27***************************************/ 28#define kSearchStrength 8 29#define HASH_READ_SIZE 8 30#define ZSTD_DUBT_UNSORTED_MARK 1 /* For btlazy2 strategy, index ZSTD_DUBT_UNSORTED_MARK==1 means "unsorted". 31 It could be confused for a real successor at index "1", if sorted as larger than its predecessor. 32 It's not a big deal though : candidate will just be sorted again. 33 Additionally, candidate position 1 will be lost. 34 But candidate 1 cannot hide a large tree of candidates, so it's a minimal loss. 35 The benefit is that ZSTD_DUBT_UNSORTED_MARK cannot be mishandled after table re-use with a different strategy. 36 This constant is required by ZSTD_compressBlock_btlazy2() and ZSTD_reduceTable_internal() */ 37 38 39/*-************************************* 40* Context memory management 41***************************************/ 42typedef enum { ZSTDcs_created=0, ZSTDcs_init, ZSTDcs_ongoing, ZSTDcs_ending } ZSTD_compressionStage_e; 43typedef enum { zcss_init=0, zcss_load, zcss_flush } ZSTD_cStreamStage; 44 45typedef struct ZSTD_prefixDict_s { 46 const void* dict; 47 size_t dictSize; 48 ZSTD_dictContentType_e dictContentType; 49} ZSTD_prefixDict; 50 51typedef struct { 52 void* dictBuffer; 53 void const* dict; 54 size_t dictSize; 55 ZSTD_dictContentType_e dictContentType; 56 ZSTD_CDict* cdict; 57} ZSTD_localDict; 58 59typedef struct { 60 HUF_CElt CTable[HUF_CTABLE_SIZE_U32(255)]; 61 HUF_repeat repeatMode; 62} ZSTD_hufCTables_t; 63 64typedef struct { 65 FSE_CTable offcodeCTable[FSE_CTABLE_SIZE_U32(OffFSELog, MaxOff)]; 66 FSE_CTable matchlengthCTable[FSE_CTABLE_SIZE_U32(MLFSELog, MaxML)]; 67 FSE_CTable litlengthCTable[FSE_CTABLE_SIZE_U32(LLFSELog, MaxLL)]; 68 FSE_repeat offcode_repeatMode; 69 FSE_repeat matchlength_repeatMode; 70 FSE_repeat litlength_repeatMode; 71} ZSTD_fseCTables_t; 72 73typedef struct { 74 ZSTD_hufCTables_t huf; 75 ZSTD_fseCTables_t fse; 76} ZSTD_entropyCTables_t; 77 78typedef struct { 79 U32 off; /* Offset code (offset + ZSTD_REP_MOVE) for the match */ 80 U32 len; /* Raw length of match */ 81} ZSTD_match_t; 82 83typedef struct { 84 U32 offset; /* Offset of sequence */ 85 U32 litLength; /* Length of literals prior to match */ 86 U32 matchLength; /* Raw length of match */ 87} rawSeq; 88 89typedef struct { 90 rawSeq* seq; /* The start of the sequences */ 91 size_t pos; /* The index in seq where reading stopped. pos <= size. */ 92 size_t posInSequence; /* The position within the sequence at seq[pos] where reading 93 stopped. posInSequence <= seq[pos].litLength + seq[pos].matchLength */ 94 size_t size; /* The number of sequences. <= capacity. */ 95 size_t capacity; /* The capacity starting from `seq` pointer */ 96} rawSeqStore_t; 97 98UNUSED_ATTR static const rawSeqStore_t kNullRawSeqStore = {NULL, 0, 0, 0, 0}; 99 100typedef struct { 101 int price; 102 U32 off; 103 U32 mlen; 104 U32 litlen; 105 U32 rep[ZSTD_REP_NUM]; 106} ZSTD_optimal_t; 107 108typedef enum { zop_dynamic=0, zop_predef } ZSTD_OptPrice_e; 109 110typedef struct { 111 /* All tables are allocated inside cctx->workspace by ZSTD_resetCCtx_internal() */ 112 unsigned* litFreq; /* table of literals statistics, of size 256 */ 113 unsigned* litLengthFreq; /* table of litLength statistics, of size (MaxLL+1) */ 114 unsigned* matchLengthFreq; /* table of matchLength statistics, of size (MaxML+1) */ 115 unsigned* offCodeFreq; /* table of offCode statistics, of size (MaxOff+1) */ 116 ZSTD_match_t* matchTable; /* list of found matches, of size ZSTD_OPT_NUM+1 */ 117 ZSTD_optimal_t* priceTable; /* All positions tracked by optimal parser, of size ZSTD_OPT_NUM+1 */ 118 119 U32 litSum; /* nb of literals */ 120 U32 litLengthSum; /* nb of litLength codes */ 121 U32 matchLengthSum; /* nb of matchLength codes */ 122 U32 offCodeSum; /* nb of offset codes */ 123 U32 litSumBasePrice; /* to compare to log2(litfreq) */ 124 U32 litLengthSumBasePrice; /* to compare to log2(llfreq) */ 125 U32 matchLengthSumBasePrice;/* to compare to log2(mlfreq) */ 126 U32 offCodeSumBasePrice; /* to compare to log2(offreq) */ 127 ZSTD_OptPrice_e priceType; /* prices can be determined dynamically, or follow a pre-defined cost structure */ 128 const ZSTD_entropyCTables_t* symbolCosts; /* pre-calculated dictionary statistics */ 129 ZSTD_literalCompressionMode_e literalCompressionMode; 130} optState_t; 131 132typedef struct { 133 ZSTD_entropyCTables_t entropy; 134 U32 rep[ZSTD_REP_NUM]; 135} ZSTD_compressedBlockState_t; 136 137typedef struct { 138 BYTE const* nextSrc; /* next block here to continue on current prefix */ 139 BYTE const* base; /* All regular indexes relative to this position */ 140 BYTE const* dictBase; /* extDict indexes relative to this position */ 141 U32 dictLimit; /* below that point, need extDict */ 142 U32 lowLimit; /* below that point, no more valid data */ 143} ZSTD_window_t; 144 145typedef struct ZSTD_matchState_t ZSTD_matchState_t; 146struct ZSTD_matchState_t { 147 ZSTD_window_t window; /* State for window round buffer management */ 148 U32 loadedDictEnd; /* index of end of dictionary, within context's referential. 149 * When loadedDictEnd != 0, a dictionary is in use, and still valid. 150 * This relies on a mechanism to set loadedDictEnd=0 when dictionary is no longer within distance. 151 * Such mechanism is provided within ZSTD_window_enforceMaxDist() and ZSTD_checkDictValidity(). 152 * When dict referential is copied into active context (i.e. not attached), 153 * loadedDictEnd == dictSize, since referential starts from zero. 154 */ 155 U32 nextToUpdate; /* index from which to continue table update */ 156 U32 hashLog3; /* dispatch table for matches of len==3 : larger == faster, more memory */ 157 U32* hashTable; 158 U32* hashTable3; 159 U32* chainTable; 160 int dedicatedDictSearch; /* Indicates whether this matchState is using the 161 * dedicated dictionary search structure. 162 */ 163 optState_t opt; /* optimal parser state */ 164 const ZSTD_matchState_t* dictMatchState; 165 ZSTD_compressionParameters cParams; 166 const rawSeqStore_t* ldmSeqStore; 167}; 168 169typedef struct { 170 ZSTD_compressedBlockState_t* prevCBlock; 171 ZSTD_compressedBlockState_t* nextCBlock; 172 ZSTD_matchState_t matchState; 173} ZSTD_blockState_t; 174 175typedef struct { 176 U32 offset; 177 U32 checksum; 178} ldmEntry_t; 179 180typedef struct { 181 BYTE const* split; 182 U32 hash; 183 U32 checksum; 184 ldmEntry_t* bucket; 185} ldmMatchCandidate_t; 186 187#define LDM_BATCH_SIZE 64 188 189typedef struct { 190 ZSTD_window_t window; /* State for the window round buffer management */ 191 ldmEntry_t* hashTable; 192 U32 loadedDictEnd; 193 BYTE* bucketOffsets; /* Next position in bucket to insert entry */ 194 size_t splitIndices[LDM_BATCH_SIZE]; 195 ldmMatchCandidate_t matchCandidates[LDM_BATCH_SIZE]; 196} ldmState_t; 197 198typedef struct { 199 U32 enableLdm; /* 1 if enable long distance matching */ 200 U32 hashLog; /* Log size of hashTable */ 201 U32 bucketSizeLog; /* Log bucket size for collision resolution, at most 8 */ 202 U32 minMatchLength; /* Minimum match length */ 203 U32 hashRateLog; /* Log number of entries to skip */ 204 U32 windowLog; /* Window log for the LDM */ 205} ldmParams_t; 206 207typedef struct { 208 int collectSequences; 209 ZSTD_Sequence* seqStart; 210 size_t seqIndex; 211 size_t maxSequences; 212} SeqCollector; 213 214struct ZSTD_CCtx_params_s { 215 ZSTD_format_e format; 216 ZSTD_compressionParameters cParams; 217 ZSTD_frameParameters fParams; 218 219 int compressionLevel; 220 int forceWindow; /* force back-references to respect limit of 221 * 1<<wLog, even for dictionary */ 222 size_t targetCBlockSize; /* Tries to fit compressed block size to be around targetCBlockSize. 223 * No target when targetCBlockSize == 0. 224 * There is no guarantee on compressed block size */ 225 int srcSizeHint; /* User's best guess of source size. 226 * Hint is not valid when srcSizeHint == 0. 227 * There is no guarantee that hint is close to actual source size */ 228 229 ZSTD_dictAttachPref_e attachDictPref; 230 ZSTD_literalCompressionMode_e literalCompressionMode; 231 232 /* Multithreading: used to pass parameters to mtctx */ 233 int nbWorkers; 234 size_t jobSize; 235 int overlapLog; 236 int rsyncable; 237 238 /* Long distance matching parameters */ 239 ldmParams_t ldmParams; 240 241 /* Dedicated dict search algorithm trigger */ 242 int enableDedicatedDictSearch; 243 244 /* Input/output buffer modes */ 245 ZSTD_bufferMode_e inBufferMode; 246 ZSTD_bufferMode_e outBufferMode; 247 248 /* Sequence compression API */ 249 ZSTD_sequenceFormat_e blockDelimiters; 250 int validateSequences; 251 252 /* Internal use, for createCCtxParams() and freeCCtxParams() only */ 253 ZSTD_customMem customMem; 254}; /* typedef'd to ZSTD_CCtx_params within "zstd.h" */ 255 256#define COMPRESS_SEQUENCES_WORKSPACE_SIZE (sizeof(unsigned) * (MaxSeq + 2)) 257#define ENTROPY_WORKSPACE_SIZE (HUF_WORKSPACE_SIZE + COMPRESS_SEQUENCES_WORKSPACE_SIZE) 258 259/* 260 * Indicates whether this compression proceeds directly from user-provided 261 * source buffer to user-provided destination buffer (ZSTDb_not_buffered), or 262 * whether the context needs to buffer the input/output (ZSTDb_buffered). 263 */ 264typedef enum { 265 ZSTDb_not_buffered, 266 ZSTDb_buffered 267} ZSTD_buffered_policy_e; 268 269struct ZSTD_CCtx_s { 270 ZSTD_compressionStage_e stage; 271 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. */ 272 int bmi2; /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */ 273 ZSTD_CCtx_params requestedParams; 274 ZSTD_CCtx_params appliedParams; 275 U32 dictID; 276 size_t dictContentSize; 277 278 ZSTD_cwksp workspace; /* manages buffer for dynamic allocations */ 279 size_t blockSize; 280 unsigned long long pledgedSrcSizePlusOne; /* this way, 0 (default) == unknown */ 281 unsigned long long consumedSrcSize; 282 unsigned long long producedCSize; 283 struct xxh64_state xxhState; 284 ZSTD_customMem customMem; 285 ZSTD_threadPool* pool; 286 size_t staticSize; 287 SeqCollector seqCollector; 288 int isFirstBlock; 289 int initialized; 290 291 seqStore_t seqStore; /* sequences storage ptrs */ 292 ldmState_t ldmState; /* long distance matching state */ 293 rawSeq* ldmSequences; /* Storage for the ldm output sequences */ 294 size_t maxNbLdmSequences; 295 rawSeqStore_t externSeqStore; /* Mutable reference to external sequences */ 296 ZSTD_blockState_t blockState; 297 U32* entropyWorkspace; /* entropy workspace of ENTROPY_WORKSPACE_SIZE bytes */ 298 299 /* Wether we are streaming or not */ 300 ZSTD_buffered_policy_e bufferedPolicy; 301 302 /* streaming */ 303 char* inBuff; 304 size_t inBuffSize; 305 size_t inToCompress; 306 size_t inBuffPos; 307 size_t inBuffTarget; 308 char* outBuff; 309 size_t outBuffSize; 310 size_t outBuffContentSize; 311 size_t outBuffFlushedSize; 312 ZSTD_cStreamStage streamStage; 313 U32 frameEnded; 314 315 /* Stable in/out buffer verification */ 316 ZSTD_inBuffer expectedInBuffer; 317 size_t expectedOutBufferSize; 318 319 /* Dictionary */ 320 ZSTD_localDict localDict; 321 const ZSTD_CDict* cdict; 322 ZSTD_prefixDict prefixDict; /* single-usage dictionary */ 323 324 /* Multi-threading */ 325 326 /* Tracing */ 327}; 328 329typedef enum { ZSTD_dtlm_fast, ZSTD_dtlm_full } ZSTD_dictTableLoadMethod_e; 330 331typedef enum { 332 ZSTD_noDict = 0, 333 ZSTD_extDict = 1, 334 ZSTD_dictMatchState = 2, 335 ZSTD_dedicatedDictSearch = 3 336} ZSTD_dictMode_e; 337 338typedef enum { 339 ZSTD_cpm_noAttachDict = 0, /* Compression with ZSTD_noDict or ZSTD_extDict. 340 * In this mode we use both the srcSize and the dictSize 341 * when selecting and adjusting parameters. 342 */ 343 ZSTD_cpm_attachDict = 1, /* Compression with ZSTD_dictMatchState or ZSTD_dedicatedDictSearch. 344 * In this mode we only take the srcSize into account when selecting 345 * and adjusting parameters. 346 */ 347 ZSTD_cpm_createCDict = 2, /* Creating a CDict. 348 * In this mode we take both the source size and the dictionary size 349 * into account when selecting and adjusting the parameters. 350 */ 351 ZSTD_cpm_unknown = 3, /* ZSTD_getCParams, ZSTD_getParams, ZSTD_adjustParams. 352 * We don't know what these parameters are for. We default to the legacy 353 * behavior of taking both the source size and the dict size into account 354 * when selecting and adjusting parameters. 355 */ 356} ZSTD_cParamMode_e; 357 358typedef size_t (*ZSTD_blockCompressor) ( 359 ZSTD_matchState_t* bs, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 360 void const* src, size_t srcSize); 361ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, ZSTD_dictMode_e dictMode); 362 363 364MEM_STATIC U32 ZSTD_LLcode(U32 litLength) 365{ 366 static const BYTE LL_Code[64] = { 0, 1, 2, 3, 4, 5, 6, 7, 367 8, 9, 10, 11, 12, 13, 14, 15, 368 16, 16, 17, 17, 18, 18, 19, 19, 369 20, 20, 20, 20, 21, 21, 21, 21, 370 22, 22, 22, 22, 22, 22, 22, 22, 371 23, 23, 23, 23, 23, 23, 23, 23, 372 24, 24, 24, 24, 24, 24, 24, 24, 373 24, 24, 24, 24, 24, 24, 24, 24 }; 374 static const U32 LL_deltaCode = 19; 375 return (litLength > 63) ? ZSTD_highbit32(litLength) + LL_deltaCode : LL_Code[litLength]; 376} 377 378/* ZSTD_MLcode() : 379 * note : mlBase = matchLength - MINMATCH; 380 * because it's the format it's stored in seqStore->sequences */ 381MEM_STATIC U32 ZSTD_MLcode(U32 mlBase) 382{ 383 static const BYTE ML_Code[128] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 384 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 385 32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37, 386 38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39, 387 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 388 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 389 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 390 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42 }; 391 static const U32 ML_deltaCode = 36; 392 return (mlBase > 127) ? ZSTD_highbit32(mlBase) + ML_deltaCode : ML_Code[mlBase]; 393} 394 395typedef struct repcodes_s { 396 U32 rep[3]; 397} repcodes_t; 398 399MEM_STATIC repcodes_t ZSTD_updateRep(U32 const rep[3], U32 const offset, U32 const ll0) 400{ 401 repcodes_t newReps; 402 if (offset >= ZSTD_REP_NUM) { /* full offset */ 403 newReps.rep[2] = rep[1]; 404 newReps.rep[1] = rep[0]; 405 newReps.rep[0] = offset - ZSTD_REP_MOVE; 406 } else { /* repcode */ 407 U32 const repCode = offset + ll0; 408 if (repCode > 0) { /* note : if repCode==0, no change */ 409 U32 const currentOffset = (repCode==ZSTD_REP_NUM) ? (rep[0] - 1) : rep[repCode]; 410 newReps.rep[2] = (repCode >= 2) ? rep[1] : rep[2]; 411 newReps.rep[1] = rep[0]; 412 newReps.rep[0] = currentOffset; 413 } else { /* repCode == 0 */ 414 ZSTD_memcpy(&newReps, rep, sizeof(newReps)); 415 } 416 } 417 return newReps; 418} 419 420/* ZSTD_cParam_withinBounds: 421 * @return 1 if value is within cParam bounds, 422 * 0 otherwise */ 423MEM_STATIC int ZSTD_cParam_withinBounds(ZSTD_cParameter cParam, int value) 424{ 425 ZSTD_bounds const bounds = ZSTD_cParam_getBounds(cParam); 426 if (ZSTD_isError(bounds.error)) return 0; 427 if (value < bounds.lowerBound) return 0; 428 if (value > bounds.upperBound) return 0; 429 return 1; 430} 431 432/* ZSTD_noCompressBlock() : 433 * Writes uncompressed block to dst buffer from given src. 434 * Returns the size of the block */ 435MEM_STATIC size_t ZSTD_noCompressBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize, U32 lastBlock) 436{ 437 U32 const cBlockHeader24 = lastBlock + (((U32)bt_raw)<<1) + (U32)(srcSize << 3); 438 RETURN_ERROR_IF(srcSize + ZSTD_blockHeaderSize > dstCapacity, 439 dstSize_tooSmall, "dst buf too small for uncompressed block"); 440 MEM_writeLE24(dst, cBlockHeader24); 441 ZSTD_memcpy((BYTE*)dst + ZSTD_blockHeaderSize, src, srcSize); 442 return ZSTD_blockHeaderSize + srcSize; 443} 444 445MEM_STATIC size_t ZSTD_rleCompressBlock (void* dst, size_t dstCapacity, BYTE src, size_t srcSize, U32 lastBlock) 446{ 447 BYTE* const op = (BYTE*)dst; 448 U32 const cBlockHeader = lastBlock + (((U32)bt_rle)<<1) + (U32)(srcSize << 3); 449 RETURN_ERROR_IF(dstCapacity < 4, dstSize_tooSmall, ""); 450 MEM_writeLE24(op, cBlockHeader); 451 op[3] = src; 452 return 4; 453} 454 455 456/* ZSTD_minGain() : 457 * minimum compression required 458 * to generate a compress block or a compressed literals section. 459 * note : use same formula for both situations */ 460MEM_STATIC size_t ZSTD_minGain(size_t srcSize, ZSTD_strategy strat) 461{ 462 U32 const minlog = (strat>=ZSTD_btultra) ? (U32)(strat) - 1 : 6; 463 ZSTD_STATIC_ASSERT(ZSTD_btultra == 8); 464 assert(ZSTD_cParam_withinBounds(ZSTD_c_strategy, strat)); 465 return (srcSize >> minlog) + 2; 466} 467 468MEM_STATIC int ZSTD_disableLiteralsCompression(const ZSTD_CCtx_params* cctxParams) 469{ 470 switch (cctxParams->literalCompressionMode) { 471 case ZSTD_lcm_huffman: 472 return 0; 473 case ZSTD_lcm_uncompressed: 474 return 1; 475 default: 476 assert(0 /* impossible: pre-validated */); 477 ZSTD_FALLTHROUGH; 478 case ZSTD_lcm_auto: 479 return (cctxParams->cParams.strategy == ZSTD_fast) && (cctxParams->cParams.targetLength > 0); 480 } 481} 482 483/*! ZSTD_safecopyLiterals() : 484 * memcpy() function that won't read beyond more than WILDCOPY_OVERLENGTH bytes past ilimit_w. 485 * Only called when the sequence ends past ilimit_w, so it only needs to be optimized for single 486 * large copies. 487 */ 488static void ZSTD_safecopyLiterals(BYTE* op, BYTE const* ip, BYTE const* const iend, BYTE const* ilimit_w) { 489 assert(iend > ilimit_w); 490 if (ip <= ilimit_w) { 491 ZSTD_wildcopy(op, ip, ilimit_w - ip, ZSTD_no_overlap); 492 op += ilimit_w - ip; 493 ip = ilimit_w; 494 } 495 while (ip < iend) *op++ = *ip++; 496} 497 498/*! ZSTD_storeSeq() : 499 * Store a sequence (litlen, litPtr, offCode and mlBase) into seqStore_t. 500 * `offCode` : distance to match + ZSTD_REP_MOVE (values <= ZSTD_REP_MOVE are repCodes). 501 * `mlBase` : matchLength - MINMATCH 502 * Allowed to overread literals up to litLimit. 503*/ 504HINT_INLINE UNUSED_ATTR 505void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const BYTE* literals, const BYTE* litLimit, U32 offCode, size_t mlBase) 506{ 507 BYTE const* const litLimit_w = litLimit - WILDCOPY_OVERLENGTH; 508 BYTE const* const litEnd = literals + litLength; 509#if defined(DEBUGLEVEL) && (DEBUGLEVEL >= 6) 510 static const BYTE* g_start = NULL; 511 if (g_start==NULL) g_start = (const BYTE*)literals; /* note : index only works for compression within a single segment */ 512 { U32 const pos = (U32)((const BYTE*)literals - g_start); 513 DEBUGLOG(6, "Cpos%7u :%3u literals, match%4u bytes at offCode%7u", 514 pos, (U32)litLength, (U32)mlBase+MINMATCH, (U32)offCode); 515 } 516#endif 517 assert((size_t)(seqStorePtr->sequences - seqStorePtr->sequencesStart) < seqStorePtr->maxNbSeq); 518 /* copy Literals */ 519 assert(seqStorePtr->maxNbLit <= 128 KB); 520 assert(seqStorePtr->lit + litLength <= seqStorePtr->litStart + seqStorePtr->maxNbLit); 521 assert(literals + litLength <= litLimit); 522 if (litEnd <= litLimit_w) { 523 /* Common case we can use wildcopy. 524 * First copy 16 bytes, because literals are likely short. 525 */ 526 assert(WILDCOPY_OVERLENGTH >= 16); 527 ZSTD_copy16(seqStorePtr->lit, literals); 528 if (litLength > 16) { 529 ZSTD_wildcopy(seqStorePtr->lit+16, literals+16, (ptrdiff_t)litLength-16, ZSTD_no_overlap); 530 } 531 } else { 532 ZSTD_safecopyLiterals(seqStorePtr->lit, literals, litEnd, litLimit_w); 533 } 534 seqStorePtr->lit += litLength; 535 536 /* literal Length */ 537 if (litLength>0xFFFF) { 538 assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */ 539 seqStorePtr->longLengthID = 1; 540 seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); 541 } 542 seqStorePtr->sequences[0].litLength = (U16)litLength; 543 544 /* match offset */ 545 seqStorePtr->sequences[0].offset = offCode + 1; 546 547 /* match Length */ 548 if (mlBase>0xFFFF) { 549 assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */ 550 seqStorePtr->longLengthID = 2; 551 seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart); 552 } 553 seqStorePtr->sequences[0].matchLength = (U16)mlBase; 554 555 seqStorePtr->sequences++; 556} 557 558 559/*-************************************* 560* Match length counter 561***************************************/ 562static unsigned ZSTD_NbCommonBytes (size_t val) 563{ 564 if (MEM_isLittleEndian()) { 565 if (MEM_64bits()) { 566# if (__GNUC__ >= 4) 567 return (__builtin_ctzll((U64)val) >> 3); 568# else 569 static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2, 570 0, 3, 1, 3, 1, 4, 2, 7, 571 0, 2, 3, 6, 1, 5, 3, 5, 572 1, 3, 4, 4, 2, 5, 6, 7, 573 7, 0, 1, 2, 3, 3, 4, 6, 574 2, 6, 5, 5, 3, 4, 5, 6, 575 7, 1, 2, 4, 6, 4, 4, 5, 576 7, 2, 6, 5, 7, 6, 7, 7 }; 577 return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58]; 578# endif 579 } else { /* 32 bits */ 580# if (__GNUC__ >= 3) 581 return (__builtin_ctz((U32)val) >> 3); 582# else 583 static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, 584 3, 2, 2, 1, 3, 2, 0, 1, 585 3, 3, 1, 2, 2, 2, 2, 0, 586 3, 1, 2, 0, 1, 0, 1, 1 }; 587 return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27]; 588# endif 589 } 590 } else { /* Big Endian CPU */ 591 if (MEM_64bits()) { 592# if (__GNUC__ >= 4) 593 return (__builtin_clzll(val) >> 3); 594# else 595 unsigned r; 596 const unsigned n32 = sizeof(size_t)*4; /* calculate this way due to compiler complaining in 32-bits mode */ 597 if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; } 598 if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; } 599 r += (!val); 600 return r; 601# endif 602 } else { /* 32 bits */ 603# if (__GNUC__ >= 3) 604 return (__builtin_clz((U32)val) >> 3); 605# else 606 unsigned r; 607 if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; } 608 r += (!val); 609 return r; 610# endif 611 } } 612} 613 614 615MEM_STATIC size_t ZSTD_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* const pInLimit) 616{ 617 const BYTE* const pStart = pIn; 618 const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1); 619 620 if (pIn < pInLoopLimit) { 621 { size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn); 622 if (diff) return ZSTD_NbCommonBytes(diff); } 623 pIn+=sizeof(size_t); pMatch+=sizeof(size_t); 624 while (pIn < pInLoopLimit) { 625 size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn); 626 if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; } 627 pIn += ZSTD_NbCommonBytes(diff); 628 return (size_t)(pIn - pStart); 629 } } 630 if (MEM_64bits() && (pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatch+=4; } 631 if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; } 632 if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++; 633 return (size_t)(pIn - pStart); 634} 635 636/* ZSTD_count_2segments() : 637 * can count match length with `ip` & `match` in 2 different segments. 638 * convention : on reaching mEnd, match count continue starting from iStart 639 */ 640MEM_STATIC size_t 641ZSTD_count_2segments(const BYTE* ip, const BYTE* match, 642 const BYTE* iEnd, const BYTE* mEnd, const BYTE* iStart) 643{ 644 const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd); 645 size_t const matchLength = ZSTD_count(ip, match, vEnd); 646 if (match + matchLength != mEnd) return matchLength; 647 DEBUGLOG(7, "ZSTD_count_2segments: found a 2-parts match (current length==%zu)", matchLength); 648 DEBUGLOG(7, "distance from match beginning to end dictionary = %zi", mEnd - match); 649 DEBUGLOG(7, "distance from current pos to end buffer = %zi", iEnd - ip); 650 DEBUGLOG(7, "next byte : ip==%02X, istart==%02X", ip[matchLength], *iStart); 651 DEBUGLOG(7, "final match length = %zu", matchLength + ZSTD_count(ip+matchLength, iStart, iEnd)); 652 return matchLength + ZSTD_count(ip+matchLength, iStart, iEnd); 653} 654 655 656/*-************************************* 657 * Hashes 658 ***************************************/ 659static const U32 prime3bytes = 506832829U; 660static U32 ZSTD_hash3(U32 u, U32 h) { return ((u << (32-24)) * prime3bytes) >> (32-h) ; } 661MEM_STATIC size_t ZSTD_hash3Ptr(const void* ptr, U32 h) { return ZSTD_hash3(MEM_readLE32(ptr), h); } /* only in zstd_opt.h */ 662 663static const U32 prime4bytes = 2654435761U; 664static U32 ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32-h) ; } 665static size_t ZSTD_hash4Ptr(const void* ptr, U32 h) { return ZSTD_hash4(MEM_read32(ptr), h); } 666 667static const U64 prime5bytes = 889523592379ULL; 668static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u << (64-40)) * prime5bytes) >> (64-h)) ; } 669static size_t ZSTD_hash5Ptr(const void* p, U32 h) { return ZSTD_hash5(MEM_readLE64(p), h); } 670 671static const U64 prime6bytes = 227718039650203ULL; 672static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u << (64-48)) * prime6bytes) >> (64-h)) ; } 673static size_t ZSTD_hash6Ptr(const void* p, U32 h) { return ZSTD_hash6(MEM_readLE64(p), h); } 674 675static const U64 prime7bytes = 58295818150454627ULL; 676static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u << (64-56)) * prime7bytes) >> (64-h)) ; } 677static size_t ZSTD_hash7Ptr(const void* p, U32 h) { return ZSTD_hash7(MEM_readLE64(p), h); } 678 679static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL; 680static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; } 681static size_t ZSTD_hash8Ptr(const void* p, U32 h) { return ZSTD_hash8(MEM_readLE64(p), h); } 682 683MEM_STATIC FORCE_INLINE_ATTR 684size_t ZSTD_hashPtr(const void* p, U32 hBits, U32 mls) 685{ 686 switch(mls) 687 { 688 default: 689 case 4: return ZSTD_hash4Ptr(p, hBits); 690 case 5: return ZSTD_hash5Ptr(p, hBits); 691 case 6: return ZSTD_hash6Ptr(p, hBits); 692 case 7: return ZSTD_hash7Ptr(p, hBits); 693 case 8: return ZSTD_hash8Ptr(p, hBits); 694 } 695} 696 697/* ZSTD_ipow() : 698 * Return base^exponent. 699 */ 700static U64 ZSTD_ipow(U64 base, U64 exponent) 701{ 702 U64 power = 1; 703 while (exponent) { 704 if (exponent & 1) power *= base; 705 exponent >>= 1; 706 base *= base; 707 } 708 return power; 709} 710 711#define ZSTD_ROLL_HASH_CHAR_OFFSET 10 712 713/* ZSTD_rollingHash_append() : 714 * Add the buffer to the hash value. 715 */ 716static U64 ZSTD_rollingHash_append(U64 hash, void const* buf, size_t size) 717{ 718 BYTE const* istart = (BYTE const*)buf; 719 size_t pos; 720 for (pos = 0; pos < size; ++pos) { 721 hash *= prime8bytes; 722 hash += istart[pos] + ZSTD_ROLL_HASH_CHAR_OFFSET; 723 } 724 return hash; 725} 726 727/* ZSTD_rollingHash_compute() : 728 * Compute the rolling hash value of the buffer. 729 */ 730MEM_STATIC U64 ZSTD_rollingHash_compute(void const* buf, size_t size) 731{ 732 return ZSTD_rollingHash_append(0, buf, size); 733} 734 735/* ZSTD_rollingHash_primePower() : 736 * Compute the primePower to be passed to ZSTD_rollingHash_rotate() for a hash 737 * over a window of length bytes. 738 */ 739MEM_STATIC U64 ZSTD_rollingHash_primePower(U32 length) 740{ 741 return ZSTD_ipow(prime8bytes, length - 1); 742} 743 744/* ZSTD_rollingHash_rotate() : 745 * Rotate the rolling hash by one byte. 746 */ 747MEM_STATIC U64 ZSTD_rollingHash_rotate(U64 hash, BYTE toRemove, BYTE toAdd, U64 primePower) 748{ 749 hash -= (toRemove + ZSTD_ROLL_HASH_CHAR_OFFSET) * primePower; 750 hash *= prime8bytes; 751 hash += toAdd + ZSTD_ROLL_HASH_CHAR_OFFSET; 752 return hash; 753} 754 755/*-************************************* 756* Round buffer management 757***************************************/ 758#if (ZSTD_WINDOWLOG_MAX_64 > 31) 759# error "ZSTD_WINDOWLOG_MAX is too large : would overflow ZSTD_CURRENT_MAX" 760#endif 761/* Max current allowed */ 762#define ZSTD_CURRENT_MAX ((3U << 29) + (1U << ZSTD_WINDOWLOG_MAX)) 763/* Maximum chunk size before overflow correction needs to be called again */ 764#define ZSTD_CHUNKSIZE_MAX \ 765 ( ((U32)-1) /* Maximum ending current index */ \ 766 - ZSTD_CURRENT_MAX) /* Maximum beginning lowLimit */ 767 768/* 769 * ZSTD_window_clear(): 770 * Clears the window containing the history by simply setting it to empty. 771 */ 772MEM_STATIC void ZSTD_window_clear(ZSTD_window_t* window) 773{ 774 size_t const endT = (size_t)(window->nextSrc - window->base); 775 U32 const end = (U32)endT; 776 777 window->lowLimit = end; 778 window->dictLimit = end; 779} 780 781/* 782 * ZSTD_window_hasExtDict(): 783 * Returns non-zero if the window has a non-empty extDict. 784 */ 785MEM_STATIC U32 ZSTD_window_hasExtDict(ZSTD_window_t const window) 786{ 787 return window.lowLimit < window.dictLimit; 788} 789 790/* 791 * ZSTD_matchState_dictMode(): 792 * Inspects the provided matchState and figures out what dictMode should be 793 * passed to the compressor. 794 */ 795MEM_STATIC ZSTD_dictMode_e ZSTD_matchState_dictMode(const ZSTD_matchState_t *ms) 796{ 797 return ZSTD_window_hasExtDict(ms->window) ? 798 ZSTD_extDict : 799 ms->dictMatchState != NULL ? 800 (ms->dictMatchState->dedicatedDictSearch ? ZSTD_dedicatedDictSearch : ZSTD_dictMatchState) : 801 ZSTD_noDict; 802} 803 804/* 805 * ZSTD_window_needOverflowCorrection(): 806 * Returns non-zero if the indices are getting too large and need overflow 807 * protection. 808 */ 809MEM_STATIC U32 ZSTD_window_needOverflowCorrection(ZSTD_window_t const window, 810 void const* srcEnd) 811{ 812 U32 const curr = (U32)((BYTE const*)srcEnd - window.base); 813 return curr > ZSTD_CURRENT_MAX; 814} 815 816/* 817 * ZSTD_window_correctOverflow(): 818 * Reduces the indices to protect from index overflow. 819 * Returns the correction made to the indices, which must be applied to every 820 * stored index. 821 * 822 * The least significant cycleLog bits of the indices must remain the same, 823 * which may be 0. Every index up to maxDist in the past must be valid. 824 * NOTE: (maxDist & cycleMask) must be zero. 825 */ 826MEM_STATIC U32 ZSTD_window_correctOverflow(ZSTD_window_t* window, U32 cycleLog, 827 U32 maxDist, void const* src) 828{ 829 /* preemptive overflow correction: 830 * 1. correction is large enough: 831 * lowLimit > (3<<29) ==> current > 3<<29 + 1<<windowLog 832 * 1<<windowLog <= newCurrent < 1<<chainLog + 1<<windowLog 833 * 834 * current - newCurrent 835 * > (3<<29 + 1<<windowLog) - (1<<windowLog + 1<<chainLog) 836 * > (3<<29) - (1<<chainLog) 837 * > (3<<29) - (1<<30) (NOTE: chainLog <= 30) 838 * > 1<<29 839 * 840 * 2. (ip+ZSTD_CHUNKSIZE_MAX - cctx->base) doesn't overflow: 841 * After correction, current is less than (1<<chainLog + 1<<windowLog). 842 * In 64-bit mode we are safe, because we have 64-bit ptrdiff_t. 843 * In 32-bit mode we are safe, because (chainLog <= 29), so 844 * ip+ZSTD_CHUNKSIZE_MAX - cctx->base < 1<<32. 845 * 3. (cctx->lowLimit + 1<<windowLog) < 1<<32: 846 * windowLog <= 31 ==> 3<<29 + 1<<windowLog < 7<<29 < 1<<32. 847 */ 848 U32 const cycleMask = (1U << cycleLog) - 1; 849 U32 const curr = (U32)((BYTE const*)src - window->base); 850 U32 const currentCycle0 = curr & cycleMask; 851 /* Exclude zero so that newCurrent - maxDist >= 1. */ 852 U32 const currentCycle1 = currentCycle0 == 0 ? (1U << cycleLog) : currentCycle0; 853 U32 const newCurrent = currentCycle1 + maxDist; 854 U32 const correction = curr - newCurrent; 855 assert((maxDist & cycleMask) == 0); 856 assert(curr > newCurrent); 857 /* Loose bound, should be around 1<<29 (see above) */ 858 assert(correction > 1<<28); 859 860 window->base += correction; 861 window->dictBase += correction; 862 if (window->lowLimit <= correction) window->lowLimit = 1; 863 else window->lowLimit -= correction; 864 if (window->dictLimit <= correction) window->dictLimit = 1; 865 else window->dictLimit -= correction; 866 867 /* Ensure we can still reference the full window. */ 868 assert(newCurrent >= maxDist); 869 assert(newCurrent - maxDist >= 1); 870 /* Ensure that lowLimit and dictLimit didn't underflow. */ 871 assert(window->lowLimit <= newCurrent); 872 assert(window->dictLimit <= newCurrent); 873 874 DEBUGLOG(4, "Correction of 0x%x bytes to lowLimit=0x%x", correction, 875 window->lowLimit); 876 return correction; 877} 878 879/* 880 * ZSTD_window_enforceMaxDist(): 881 * Updates lowLimit so that: 882 * (srcEnd - base) - lowLimit == maxDist + loadedDictEnd 883 * 884 * It ensures index is valid as long as index >= lowLimit. 885 * This must be called before a block compression call. 886 * 887 * loadedDictEnd is only defined if a dictionary is in use for current compression. 888 * As the name implies, loadedDictEnd represents the index at end of dictionary. 889 * The value lies within context's referential, it can be directly compared to blockEndIdx. 890 * 891 * If loadedDictEndPtr is NULL, no dictionary is in use, and we use loadedDictEnd == 0. 892 * If loadedDictEndPtr is not NULL, we set it to zero after updating lowLimit. 893 * This is because dictionaries are allowed to be referenced fully 894 * as long as the last byte of the dictionary is in the window. 895 * Once input has progressed beyond window size, dictionary cannot be referenced anymore. 896 * 897 * In normal dict mode, the dictionary lies between lowLimit and dictLimit. 898 * In dictMatchState mode, lowLimit and dictLimit are the same, 899 * and the dictionary is below them. 900 * forceWindow and dictMatchState are therefore incompatible. 901 */ 902MEM_STATIC void 903ZSTD_window_enforceMaxDist(ZSTD_window_t* window, 904 const void* blockEnd, 905 U32 maxDist, 906 U32* loadedDictEndPtr, 907 const ZSTD_matchState_t** dictMatchStatePtr) 908{ 909 U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base); 910 U32 const loadedDictEnd = (loadedDictEndPtr != NULL) ? *loadedDictEndPtr : 0; 911 DEBUGLOG(5, "ZSTD_window_enforceMaxDist: blockEndIdx=%u, maxDist=%u, loadedDictEnd=%u", 912 (unsigned)blockEndIdx, (unsigned)maxDist, (unsigned)loadedDictEnd); 913 914 /* - When there is no dictionary : loadedDictEnd == 0. 915 In which case, the test (blockEndIdx > maxDist) is merely to avoid 916 overflowing next operation `newLowLimit = blockEndIdx - maxDist`. 917 - When there is a standard dictionary : 918 Index referential is copied from the dictionary, 919 which means it starts from 0. 920 In which case, loadedDictEnd == dictSize, 921 and it makes sense to compare `blockEndIdx > maxDist + dictSize` 922 since `blockEndIdx` also starts from zero. 923 - When there is an attached dictionary : 924 loadedDictEnd is expressed within the referential of the context, 925 so it can be directly compared against blockEndIdx. 926 */ 927 if (blockEndIdx > maxDist + loadedDictEnd) { 928 U32 const newLowLimit = blockEndIdx - maxDist; 929 if (window->lowLimit < newLowLimit) window->lowLimit = newLowLimit; 930 if (window->dictLimit < window->lowLimit) { 931 DEBUGLOG(5, "Update dictLimit to match lowLimit, from %u to %u", 932 (unsigned)window->dictLimit, (unsigned)window->lowLimit); 933 window->dictLimit = window->lowLimit; 934 } 935 /* On reaching window size, dictionaries are invalidated */ 936 if (loadedDictEndPtr) *loadedDictEndPtr = 0; 937 if (dictMatchStatePtr) *dictMatchStatePtr = NULL; 938 } 939} 940 941/* Similar to ZSTD_window_enforceMaxDist(), 942 * but only invalidates dictionary 943 * when input progresses beyond window size. 944 * assumption : loadedDictEndPtr and dictMatchStatePtr are valid (non NULL) 945 * loadedDictEnd uses same referential as window->base 946 * maxDist is the window size */ 947MEM_STATIC void 948ZSTD_checkDictValidity(const ZSTD_window_t* window, 949 const void* blockEnd, 950 U32 maxDist, 951 U32* loadedDictEndPtr, 952 const ZSTD_matchState_t** dictMatchStatePtr) 953{ 954 assert(loadedDictEndPtr != NULL); 955 assert(dictMatchStatePtr != NULL); 956 { U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base); 957 U32 const loadedDictEnd = *loadedDictEndPtr; 958 DEBUGLOG(5, "ZSTD_checkDictValidity: blockEndIdx=%u, maxDist=%u, loadedDictEnd=%u", 959 (unsigned)blockEndIdx, (unsigned)maxDist, (unsigned)loadedDictEnd); 960 assert(blockEndIdx >= loadedDictEnd); 961 962 if (blockEndIdx > loadedDictEnd + maxDist) { 963 /* On reaching window size, dictionaries are invalidated. 964 * For simplification, if window size is reached anywhere within next block, 965 * the dictionary is invalidated for the full block. 966 */ 967 DEBUGLOG(6, "invalidating dictionary for current block (distance > windowSize)"); 968 *loadedDictEndPtr = 0; 969 *dictMatchStatePtr = NULL; 970 } else { 971 if (*loadedDictEndPtr != 0) { 972 DEBUGLOG(6, "dictionary considered valid for current block"); 973 } } } 974} 975 976MEM_STATIC void ZSTD_window_init(ZSTD_window_t* window) { 977 ZSTD_memset(window, 0, sizeof(*window)); 978 window->base = (BYTE const*)""; 979 window->dictBase = (BYTE const*)""; 980 window->dictLimit = 1; /* start from 1, so that 1st position is valid */ 981 window->lowLimit = 1; /* it ensures first and later CCtx usages compress the same */ 982 window->nextSrc = window->base + 1; /* see issue #1241 */ 983} 984 985/* 986 * ZSTD_window_update(): 987 * Updates the window by appending [src, src + srcSize) to the window. 988 * If it is not contiguous, the current prefix becomes the extDict, and we 989 * forget about the extDict. Handles overlap of the prefix and extDict. 990 * Returns non-zero if the segment is contiguous. 991 */ 992MEM_STATIC U32 ZSTD_window_update(ZSTD_window_t* window, 993 void const* src, size_t srcSize) 994{ 995 BYTE const* const ip = (BYTE const*)src; 996 U32 contiguous = 1; 997 DEBUGLOG(5, "ZSTD_window_update"); 998 if (srcSize == 0) 999 return contiguous; 1000 assert(window->base != NULL); 1001 assert(window->dictBase != NULL); 1002 /* Check if blocks follow each other */ 1003 if (src != window->nextSrc) { 1004 /* not contiguous */ 1005 size_t const distanceFromBase = (size_t)(window->nextSrc - window->base); 1006 DEBUGLOG(5, "Non contiguous blocks, new segment starts at %u", window->dictLimit); 1007 window->lowLimit = window->dictLimit; 1008 assert(distanceFromBase == (size_t)(U32)distanceFromBase); /* should never overflow */ 1009 window->dictLimit = (U32)distanceFromBase; 1010 window->dictBase = window->base; 1011 window->base = ip - distanceFromBase; 1012 /* ms->nextToUpdate = window->dictLimit; */ 1013 if (window->dictLimit - window->lowLimit < HASH_READ_SIZE) window->lowLimit = window->dictLimit; /* too small extDict */ 1014 contiguous = 0; 1015 } 1016 window->nextSrc = ip + srcSize; 1017 /* if input and dictionary overlap : reduce dictionary (area presumed modified by input) */ 1018 if ( (ip+srcSize > window->dictBase + window->lowLimit) 1019 & (ip < window->dictBase + window->dictLimit)) { 1020 ptrdiff_t const highInputIdx = (ip + srcSize) - window->dictBase; 1021 U32 const lowLimitMax = (highInputIdx > (ptrdiff_t)window->dictLimit) ? window->dictLimit : (U32)highInputIdx; 1022 window->lowLimit = lowLimitMax; 1023 DEBUGLOG(5, "Overlapping extDict and input : new lowLimit = %u", window->lowLimit); 1024 } 1025 return contiguous; 1026} 1027 1028/* 1029 * Returns the lowest allowed match index. It may either be in the ext-dict or the prefix. 1030 */ 1031MEM_STATIC U32 ZSTD_getLowestMatchIndex(const ZSTD_matchState_t* ms, U32 curr, unsigned windowLog) 1032{ 1033 U32 const maxDistance = 1U << windowLog; 1034 U32 const lowestValid = ms->window.lowLimit; 1035 U32 const withinWindow = (curr - lowestValid > maxDistance) ? curr - maxDistance : lowestValid; 1036 U32 const isDictionary = (ms->loadedDictEnd != 0); 1037 /* When using a dictionary the entire dictionary is valid if a single byte of the dictionary 1038 * is within the window. We invalidate the dictionary (and set loadedDictEnd to 0) when it isn't 1039 * valid for the entire block. So this check is sufficient to find the lowest valid match index. 1040 */ 1041 U32 const matchLowest = isDictionary ? lowestValid : withinWindow; 1042 return matchLowest; 1043} 1044 1045/* 1046 * Returns the lowest allowed match index in the prefix. 1047 */ 1048MEM_STATIC U32 ZSTD_getLowestPrefixIndex(const ZSTD_matchState_t* ms, U32 curr, unsigned windowLog) 1049{ 1050 U32 const maxDistance = 1U << windowLog; 1051 U32 const lowestValid = ms->window.dictLimit; 1052 U32 const withinWindow = (curr - lowestValid > maxDistance) ? curr - maxDistance : lowestValid; 1053 U32 const isDictionary = (ms->loadedDictEnd != 0); 1054 /* When computing the lowest prefix index we need to take the dictionary into account to handle 1055 * the edge case where the dictionary and the source are contiguous in memory. 1056 */ 1057 U32 const matchLowest = isDictionary ? lowestValid : withinWindow; 1058 return matchLowest; 1059} 1060 1061 1062 1063/* debug functions */ 1064#if (DEBUGLEVEL>=2) 1065 1066MEM_STATIC double ZSTD_fWeight(U32 rawStat) 1067{ 1068 U32 const fp_accuracy = 8; 1069 U32 const fp_multiplier = (1 << fp_accuracy); 1070 U32 const newStat = rawStat + 1; 1071 U32 const hb = ZSTD_highbit32(newStat); 1072 U32 const BWeight = hb * fp_multiplier; 1073 U32 const FWeight = (newStat << fp_accuracy) >> hb; 1074 U32 const weight = BWeight + FWeight; 1075 assert(hb + fp_accuracy < 31); 1076 return (double)weight / fp_multiplier; 1077} 1078 1079/* display a table content, 1080 * listing each element, its frequency, and its predicted bit cost */ 1081MEM_STATIC void ZSTD_debugTable(const U32* table, U32 max) 1082{ 1083 unsigned u, sum; 1084 for (u=0, sum=0; u<=max; u++) sum += table[u]; 1085 DEBUGLOG(2, "total nb elts: %u", sum); 1086 for (u=0; u<=max; u++) { 1087 DEBUGLOG(2, "%2u: %5u (%.2f)", 1088 u, table[u], ZSTD_fWeight(sum) - ZSTD_fWeight(table[u]) ); 1089 } 1090} 1091 1092#endif 1093 1094 1095 1096/* =============================================================== 1097 * Shared internal declarations 1098 * These prototypes may be called from sources not in lib/compress 1099 * =============================================================== */ 1100 1101/* ZSTD_loadCEntropy() : 1102 * dict : must point at beginning of a valid zstd dictionary. 1103 * return : size of dictionary header (size of magic number + dict ID + entropy tables) 1104 * assumptions : magic number supposed already checked 1105 * and dictSize >= 8 */ 1106size_t ZSTD_loadCEntropy(ZSTD_compressedBlockState_t* bs, void* workspace, 1107 const void* const dict, size_t dictSize); 1108 1109void ZSTD_reset_compressedBlockState(ZSTD_compressedBlockState_t* bs); 1110 1111/* ============================================================== 1112 * Private declarations 1113 * These prototypes shall only be called from within lib/compress 1114 * ============================================================== */ 1115 1116/* ZSTD_getCParamsFromCCtxParams() : 1117 * cParams are built depending on compressionLevel, src size hints, 1118 * LDM and manually set compression parameters. 1119 * Note: srcSizeHint == 0 means 0! 1120 */ 1121ZSTD_compressionParameters ZSTD_getCParamsFromCCtxParams( 1122 const ZSTD_CCtx_params* CCtxParams, U64 srcSizeHint, size_t dictSize, ZSTD_cParamMode_e mode); 1123 1124/*! ZSTD_initCStream_internal() : 1125 * Private use only. Init streaming operation. 1126 * expects params to be valid. 1127 * must receive dict, or cdict, or none, but not both. 1128 * @return : 0, or an error code */ 1129size_t ZSTD_initCStream_internal(ZSTD_CStream* zcs, 1130 const void* dict, size_t dictSize, 1131 const ZSTD_CDict* cdict, 1132 const ZSTD_CCtx_params* params, unsigned long long pledgedSrcSize); 1133 1134void ZSTD_resetSeqStore(seqStore_t* ssPtr); 1135 1136/*! ZSTD_getCParamsFromCDict() : 1137 * as the name implies */ 1138ZSTD_compressionParameters ZSTD_getCParamsFromCDict(const ZSTD_CDict* cdict); 1139 1140/* ZSTD_compressBegin_advanced_internal() : 1141 * Private use only. To be called from zstdmt_compress.c. */ 1142size_t ZSTD_compressBegin_advanced_internal(ZSTD_CCtx* cctx, 1143 const void* dict, size_t dictSize, 1144 ZSTD_dictContentType_e dictContentType, 1145 ZSTD_dictTableLoadMethod_e dtlm, 1146 const ZSTD_CDict* cdict, 1147 const ZSTD_CCtx_params* params, 1148 unsigned long long pledgedSrcSize); 1149 1150/* ZSTD_compress_advanced_internal() : 1151 * Private use only. To be called from zstdmt_compress.c. */ 1152size_t ZSTD_compress_advanced_internal(ZSTD_CCtx* cctx, 1153 void* dst, size_t dstCapacity, 1154 const void* src, size_t srcSize, 1155 const void* dict,size_t dictSize, 1156 const ZSTD_CCtx_params* params); 1157 1158 1159/* ZSTD_writeLastEmptyBlock() : 1160 * output an empty Block with end-of-frame mark to complete a frame 1161 * @return : size of data written into `dst` (== ZSTD_blockHeaderSize (defined in zstd_internal.h)) 1162 * or an error code if `dstCapacity` is too small (<ZSTD_blockHeaderSize) 1163 */ 1164size_t ZSTD_writeLastEmptyBlock(void* dst, size_t dstCapacity); 1165 1166 1167/* ZSTD_referenceExternalSequences() : 1168 * Must be called before starting a compression operation. 1169 * seqs must parse a prefix of the source. 1170 * This cannot be used when long range matching is enabled. 1171 * Zstd will use these sequences, and pass the literals to a secondary block 1172 * compressor. 1173 * @return : An error code on failure. 1174 * NOTE: seqs are not verified! Invalid sequences can cause out-of-bounds memory 1175 * access and data corruption. 1176 */ 1177size_t ZSTD_referenceExternalSequences(ZSTD_CCtx* cctx, rawSeq* seq, size_t nbSeq); 1178 1179/* ZSTD_cycleLog() : 1180 * condition for correct operation : hashLog > 1 */ 1181U32 ZSTD_cycleLog(U32 hashLog, ZSTD_strategy strat); 1182 1183/* ZSTD_CCtx_trace() : 1184 * Trace the end of a compression call. 1185 */ 1186void ZSTD_CCtx_trace(ZSTD_CCtx* cctx, size_t extraCSize); 1187 1188#endif /* ZSTD_COMPRESS_H */