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 #include "zstd_compress_internal.h" 12 #include "zstd_lazy.h" 13 14 15 /*-************************************* 16 * Binary Tree search 17 ***************************************/ 18 19 static void 20 ZSTD_updateDUBT(ZSTD_matchState_t* ms, 21 const BYTE* ip, const BYTE* iend, 22 U32 mls) 23 { 24 const ZSTD_compressionParameters* const cParams = &ms->cParams; 25 U32* const hashTable = ms->hashTable; 26 U32 const hashLog = cParams->hashLog; 27 28 U32* const bt = ms->chainTable; 29 U32 const btLog = cParams->chainLog - 1; 30 U32 const btMask = (1 << btLog) - 1; 31 32 const BYTE* const base = ms->window.base; 33 U32 const target = (U32)(ip - base); 34 U32 idx = ms->nextToUpdate; 35 36 if (idx != target) 37 DEBUGLOG(7, "ZSTD_updateDUBT, from %u to %u (dictLimit:%u)", 38 idx, target, ms->window.dictLimit); 39 assert(ip + 8 <= iend); /* condition for ZSTD_hashPtr */ 40 (void)iend; 41 42 assert(idx >= ms->window.dictLimit); /* condition for valid base+idx */ 43 for ( ; idx < target ; idx++) { 44 size_t const h = ZSTD_hashPtr(base + idx, hashLog, mls); /* assumption : ip + 8 <= iend */ 45 U32 const matchIndex = hashTable[h]; 46 47 U32* const nextCandidatePtr = bt + 2*(idx&btMask); 48 U32* const sortMarkPtr = nextCandidatePtr + 1; 49 50 DEBUGLOG(8, "ZSTD_updateDUBT: insert %u", idx); 51 hashTable[h] = idx; /* Update Hash Table */ 52 *nextCandidatePtr = matchIndex; /* update BT like a chain */ 53 *sortMarkPtr = ZSTD_DUBT_UNSORTED_MARK; 54 } 55 ms->nextToUpdate = target; 56 } 57 58 59 /** ZSTD_insertDUBT1() : 60 * sort one already inserted but unsorted position 61 * assumption : current >= btlow == (current - btmask) 62 * doesn't fail */ 63 static void 64 ZSTD_insertDUBT1(ZSTD_matchState_t* ms, 65 U32 current, const BYTE* inputEnd, 66 U32 nbCompares, U32 btLow, 67 const ZSTD_dictMode_e dictMode) 68 { 69 const ZSTD_compressionParameters* const cParams = &ms->cParams; 70 U32* const bt = ms->chainTable; 71 U32 const btLog = cParams->chainLog - 1; 72 U32 const btMask = (1 << btLog) - 1; 73 size_t commonLengthSmaller=0, commonLengthLarger=0; 74 const BYTE* const base = ms->window.base; 75 const BYTE* const dictBase = ms->window.dictBase; 76 const U32 dictLimit = ms->window.dictLimit; 77 const BYTE* const ip = (current>=dictLimit) ? base + current : dictBase + current; 78 const BYTE* const iend = (current>=dictLimit) ? inputEnd : dictBase + dictLimit; 79 const BYTE* const dictEnd = dictBase + dictLimit; 80 const BYTE* const prefixStart = base + dictLimit; 81 const BYTE* match; 82 U32* smallerPtr = bt + 2*(current&btMask); 83 U32* largerPtr = smallerPtr + 1; 84 U32 matchIndex = *smallerPtr; /* this candidate is unsorted : next sorted candidate is reached through *smallerPtr, while *largerPtr contains previous unsorted candidate (which is already saved and can be overwritten) */ 85 U32 dummy32; /* to be nullified at the end */ 86 U32 const windowValid = ms->window.lowLimit; 87 U32 const maxDistance = 1U << cParams->windowLog; 88 U32 const windowLow = (current - windowValid > maxDistance) ? current - maxDistance : windowValid; 89 90 91 DEBUGLOG(8, "ZSTD_insertDUBT1(%u) (dictLimit=%u, lowLimit=%u)", 92 current, dictLimit, windowLow); 93 assert(current >= btLow); 94 assert(ip < iend); /* condition for ZSTD_count */ 95 96 while (nbCompares-- && (matchIndex > windowLow)) { 97 U32* const nextPtr = bt + 2*(matchIndex & btMask); 98 size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */ 99 assert(matchIndex < current); 100 /* note : all candidates are now supposed sorted, 101 * but it's still possible to have nextPtr[1] == ZSTD_DUBT_UNSORTED_MARK 102 * when a real index has the same value as ZSTD_DUBT_UNSORTED_MARK */ 103 104 if ( (dictMode != ZSTD_extDict) 105 || (matchIndex+matchLength >= dictLimit) /* both in current segment*/ 106 || (current < dictLimit) /* both in extDict */) { 107 const BYTE* const mBase = ( (dictMode != ZSTD_extDict) 108 || (matchIndex+matchLength >= dictLimit)) ? 109 base : dictBase; 110 assert( (matchIndex+matchLength >= dictLimit) /* might be wrong if extDict is incorrectly set to 0 */ 111 || (current < dictLimit) ); 112 match = mBase + matchIndex; 113 matchLength += ZSTD_count(ip+matchLength, match+matchLength, iend); 114 } else { 115 match = dictBase + matchIndex; 116 matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iend, dictEnd, prefixStart); 117 if (matchIndex+matchLength >= dictLimit) 118 match = base + matchIndex; /* preparation for next read of match[matchLength] */ 119 } 120 121 DEBUGLOG(8, "ZSTD_insertDUBT1: comparing %u with %u : found %u common bytes ", 122 current, matchIndex, (U32)matchLength); 123 124 if (ip+matchLength == iend) { /* equal : no way to know if inf or sup */ 125 break; /* drop , to guarantee consistency ; miss a bit of compression, but other solutions can corrupt tree */ 126 } 127 128 if (match[matchLength] < ip[matchLength]) { /* necessarily within buffer */ 129 /* match is smaller than current */ 130 *smallerPtr = matchIndex; /* update smaller idx */ 131 commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */ 132 if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop searching */ 133 DEBUGLOG(8, "ZSTD_insertDUBT1: %u (>btLow=%u) is smaller : next => %u", 134 matchIndex, btLow, nextPtr[1]); 135 smallerPtr = nextPtr+1; /* new "candidate" => larger than match, which was smaller than target */ 136 matchIndex = nextPtr[1]; /* new matchIndex, larger than previous and closer to current */ 137 } else { 138 /* match is larger than current */ 139 *largerPtr = matchIndex; 140 commonLengthLarger = matchLength; 141 if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop searching */ 142 DEBUGLOG(8, "ZSTD_insertDUBT1: %u (>btLow=%u) is larger => %u", 143 matchIndex, btLow, nextPtr[0]); 144 largerPtr = nextPtr; 145 matchIndex = nextPtr[0]; 146 } } 147 148 *smallerPtr = *largerPtr = 0; 149 } 150 151 152 static size_t 153 ZSTD_DUBT_findBetterDictMatch ( 154 ZSTD_matchState_t* ms, 155 const BYTE* const ip, const BYTE* const iend, 156 size_t* offsetPtr, 157 size_t bestLength, 158 U32 nbCompares, 159 U32 const mls, 160 const ZSTD_dictMode_e dictMode) 161 { 162 const ZSTD_matchState_t * const dms = ms->dictMatchState; 163 const ZSTD_compressionParameters* const dmsCParams = &dms->cParams; 164 const U32 * const dictHashTable = dms->hashTable; 165 U32 const hashLog = dmsCParams->hashLog; 166 size_t const h = ZSTD_hashPtr(ip, hashLog, mls); 167 U32 dictMatchIndex = dictHashTable[h]; 168 169 const BYTE* const base = ms->window.base; 170 const BYTE* const prefixStart = base + ms->window.dictLimit; 171 U32 const current = (U32)(ip-base); 172 const BYTE* const dictBase = dms->window.base; 173 const BYTE* const dictEnd = dms->window.nextSrc; 174 U32 const dictHighLimit = (U32)(dms->window.nextSrc - dms->window.base); 175 U32 const dictLowLimit = dms->window.lowLimit; 176 U32 const dictIndexDelta = ms->window.lowLimit - dictHighLimit; 177 178 U32* const dictBt = dms->chainTable; 179 U32 const btLog = dmsCParams->chainLog - 1; 180 U32 const btMask = (1 << btLog) - 1; 181 U32 const btLow = (btMask >= dictHighLimit - dictLowLimit) ? dictLowLimit : dictHighLimit - btMask; 182 183 size_t commonLengthSmaller=0, commonLengthLarger=0; 184 185 (void)dictMode; 186 assert(dictMode == ZSTD_dictMatchState); 187 188 while (nbCompares-- && (dictMatchIndex > dictLowLimit)) { 189 U32* const nextPtr = dictBt + 2*(dictMatchIndex & btMask); 190 size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */ 191 const BYTE* match = dictBase + dictMatchIndex; 192 matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iend, dictEnd, prefixStart); 193 if (dictMatchIndex+matchLength >= dictHighLimit) 194 match = base + dictMatchIndex + dictIndexDelta; /* to prepare for next usage of match[matchLength] */ 195 196 if (matchLength > bestLength) { 197 U32 matchIndex = dictMatchIndex + dictIndexDelta; 198 if ( (4*(int)(matchLength-bestLength)) > (int)(ZSTD_highbit32(current-matchIndex+1) - ZSTD_highbit32((U32)offsetPtr[0]+1)) ) { 199 DEBUGLOG(9, "ZSTD_DUBT_findBetterDictMatch(%u) : found better match length %u -> %u and offsetCode %u -> %u (dictMatchIndex %u, matchIndex %u)", 200 current, (U32)bestLength, (U32)matchLength, (U32)*offsetPtr, ZSTD_REP_MOVE + current - matchIndex, dictMatchIndex, matchIndex); 201 bestLength = matchLength, *offsetPtr = ZSTD_REP_MOVE + current - matchIndex; 202 } 203 if (ip+matchLength == iend) { /* reached end of input : ip[matchLength] is not valid, no way to know if it's larger or smaller than match */ 204 break; /* drop, to guarantee consistency (miss a little bit of compression) */ 205 } 206 } 207 208 if (match[matchLength] < ip[matchLength]) { 209 if (dictMatchIndex <= btLow) { break; } /* beyond tree size, stop the search */ 210 commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */ 211 dictMatchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */ 212 } else { 213 /* match is larger than current */ 214 if (dictMatchIndex <= btLow) { break; } /* beyond tree size, stop the search */ 215 commonLengthLarger = matchLength; 216 dictMatchIndex = nextPtr[0]; 217 } 218 } 219 220 if (bestLength >= MINMATCH) { 221 U32 const mIndex = current - ((U32)*offsetPtr - ZSTD_REP_MOVE); (void)mIndex; 222 DEBUGLOG(8, "ZSTD_DUBT_findBetterDictMatch(%u) : found match of length %u and offsetCode %u (pos %u)", 223 current, (U32)bestLength, (U32)*offsetPtr, mIndex); 224 } 225 return bestLength; 226 227 } 228 229 230 static size_t 231 ZSTD_DUBT_findBestMatch(ZSTD_matchState_t* ms, 232 const BYTE* const ip, const BYTE* const iend, 233 size_t* offsetPtr, 234 U32 const mls, 235 const ZSTD_dictMode_e dictMode) 236 { 237 const ZSTD_compressionParameters* const cParams = &ms->cParams; 238 U32* const hashTable = ms->hashTable; 239 U32 const hashLog = cParams->hashLog; 240 size_t const h = ZSTD_hashPtr(ip, hashLog, mls); 241 U32 matchIndex = hashTable[h]; 242 243 const BYTE* const base = ms->window.base; 244 U32 const current = (U32)(ip-base); 245 U32 const maxDistance = 1U << cParams->windowLog; 246 U32 const windowValid = ms->window.lowLimit; 247 U32 const windowLow = (current - windowValid > maxDistance) ? current - maxDistance : windowValid; 248 249 U32* const bt = ms->chainTable; 250 U32 const btLog = cParams->chainLog - 1; 251 U32 const btMask = (1 << btLog) - 1; 252 U32 const btLow = (btMask >= current) ? 0 : current - btMask; 253 U32 const unsortLimit = MAX(btLow, windowLow); 254 255 U32* nextCandidate = bt + 2*(matchIndex&btMask); 256 U32* unsortedMark = bt + 2*(matchIndex&btMask) + 1; 257 U32 nbCompares = 1U << cParams->searchLog; 258 U32 nbCandidates = nbCompares; 259 U32 previousCandidate = 0; 260 261 DEBUGLOG(7, "ZSTD_DUBT_findBestMatch (%u) ", current); 262 assert(ip <= iend-8); /* required for h calculation */ 263 264 /* reach end of unsorted candidates list */ 265 while ( (matchIndex > unsortLimit) 266 && (*unsortedMark == ZSTD_DUBT_UNSORTED_MARK) 267 && (nbCandidates > 1) ) { 268 DEBUGLOG(8, "ZSTD_DUBT_findBestMatch: candidate %u is unsorted", 269 matchIndex); 270 *unsortedMark = previousCandidate; /* the unsortedMark becomes a reversed chain, to move up back to original position */ 271 previousCandidate = matchIndex; 272 matchIndex = *nextCandidate; 273 nextCandidate = bt + 2*(matchIndex&btMask); 274 unsortedMark = bt + 2*(matchIndex&btMask) + 1; 275 nbCandidates --; 276 } 277 278 /* nullify last candidate if it's still unsorted 279 * simplification, detrimental to compression ratio, beneficial for speed */ 280 if ( (matchIndex > unsortLimit) 281 && (*unsortedMark==ZSTD_DUBT_UNSORTED_MARK) ) { 282 DEBUGLOG(7, "ZSTD_DUBT_findBestMatch: nullify last unsorted candidate %u", 283 matchIndex); 284 *nextCandidate = *unsortedMark = 0; 285 } 286 287 /* batch sort stacked candidates */ 288 matchIndex = previousCandidate; 289 while (matchIndex) { /* will end on matchIndex == 0 */ 290 U32* const nextCandidateIdxPtr = bt + 2*(matchIndex&btMask) + 1; 291 U32 const nextCandidateIdx = *nextCandidateIdxPtr; 292 ZSTD_insertDUBT1(ms, matchIndex, iend, 293 nbCandidates, unsortLimit, dictMode); 294 matchIndex = nextCandidateIdx; 295 nbCandidates++; 296 } 297 298 /* find longest match */ 299 { size_t commonLengthSmaller = 0, commonLengthLarger = 0; 300 const BYTE* const dictBase = ms->window.dictBase; 301 const U32 dictLimit = ms->window.dictLimit; 302 const BYTE* const dictEnd = dictBase + dictLimit; 303 const BYTE* const prefixStart = base + dictLimit; 304 U32* smallerPtr = bt + 2*(current&btMask); 305 U32* largerPtr = bt + 2*(current&btMask) + 1; 306 U32 matchEndIdx = current + 8 + 1; 307 U32 dummy32; /* to be nullified at the end */ 308 size_t bestLength = 0; 309 310 matchIndex = hashTable[h]; 311 hashTable[h] = current; /* Update Hash Table */ 312 313 while (nbCompares-- && (matchIndex > windowLow)) { 314 U32* const nextPtr = bt + 2*(matchIndex & btMask); 315 size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */ 316 const BYTE* match; 317 318 if ((dictMode != ZSTD_extDict) || (matchIndex+matchLength >= dictLimit)) { 319 match = base + matchIndex; 320 matchLength += ZSTD_count(ip+matchLength, match+matchLength, iend); 321 } else { 322 match = dictBase + matchIndex; 323 matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iend, dictEnd, prefixStart); 324 if (matchIndex+matchLength >= dictLimit) 325 match = base + matchIndex; /* to prepare for next usage of match[matchLength] */ 326 } 327 328 if (matchLength > bestLength) { 329 if (matchLength > matchEndIdx - matchIndex) 330 matchEndIdx = matchIndex + (U32)matchLength; 331 if ( (4*(int)(matchLength-bestLength)) > (int)(ZSTD_highbit32(current-matchIndex+1) - ZSTD_highbit32((U32)offsetPtr[0]+1)) ) 332 bestLength = matchLength, *offsetPtr = ZSTD_REP_MOVE + current - matchIndex; 333 if (ip+matchLength == iend) { /* equal : no way to know if inf or sup */ 334 if (dictMode == ZSTD_dictMatchState) { 335 nbCompares = 0; /* in addition to avoiding checking any 336 * further in this loop, make sure we 337 * skip checking in the dictionary. */ 338 } 339 break; /* drop, to guarantee consistency (miss a little bit of compression) */ 340 } 341 } 342 343 if (match[matchLength] < ip[matchLength]) { 344 /* match is smaller than current */ 345 *smallerPtr = matchIndex; /* update smaller idx */ 346 commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */ 347 if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */ 348 smallerPtr = nextPtr+1; /* new "smaller" => larger of match */ 349 matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */ 350 } else { 351 /* match is larger than current */ 352 *largerPtr = matchIndex; 353 commonLengthLarger = matchLength; 354 if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop the search */ 355 largerPtr = nextPtr; 356 matchIndex = nextPtr[0]; 357 } } 358 359 *smallerPtr = *largerPtr = 0; 360 361 if (dictMode == ZSTD_dictMatchState && nbCompares) { 362 bestLength = ZSTD_DUBT_findBetterDictMatch( 363 ms, ip, iend, 364 offsetPtr, bestLength, nbCompares, 365 mls, dictMode); 366 } 367 368 assert(matchEndIdx > current+8); /* ensure nextToUpdate is increased */ 369 ms->nextToUpdate = matchEndIdx - 8; /* skip repetitive patterns */ 370 if (bestLength >= MINMATCH) { 371 U32 const mIndex = current - ((U32)*offsetPtr - ZSTD_REP_MOVE); (void)mIndex; 372 DEBUGLOG(8, "ZSTD_DUBT_findBestMatch(%u) : found match of length %u and offsetCode %u (pos %u)", 373 current, (U32)bestLength, (U32)*offsetPtr, mIndex); 374 } 375 return bestLength; 376 } 377 } 378 379 380 /** ZSTD_BtFindBestMatch() : Tree updater, providing best match */ 381 FORCE_INLINE_TEMPLATE size_t 382 ZSTD_BtFindBestMatch( ZSTD_matchState_t* ms, 383 const BYTE* const ip, const BYTE* const iLimit, 384 size_t* offsetPtr, 385 const U32 mls /* template */, 386 const ZSTD_dictMode_e dictMode) 387 { 388 DEBUGLOG(7, "ZSTD_BtFindBestMatch"); 389 if (ip < ms->window.base + ms->nextToUpdate) return 0; /* skipped area */ 390 ZSTD_updateDUBT(ms, ip, iLimit, mls); 391 return ZSTD_DUBT_findBestMatch(ms, ip, iLimit, offsetPtr, mls, dictMode); 392 } 393 394 395 static size_t 396 ZSTD_BtFindBestMatch_selectMLS ( ZSTD_matchState_t* ms, 397 const BYTE* ip, const BYTE* const iLimit, 398 size_t* offsetPtr) 399 { 400 switch(ms->cParams.minMatch) 401 { 402 default : /* includes case 3 */ 403 case 4 : return ZSTD_BtFindBestMatch(ms, ip, iLimit, offsetPtr, 4, ZSTD_noDict); 404 case 5 : return ZSTD_BtFindBestMatch(ms, ip, iLimit, offsetPtr, 5, ZSTD_noDict); 405 case 7 : 406 case 6 : return ZSTD_BtFindBestMatch(ms, ip, iLimit, offsetPtr, 6, ZSTD_noDict); 407 } 408 } 409 410 411 static size_t ZSTD_BtFindBestMatch_dictMatchState_selectMLS ( 412 ZSTD_matchState_t* ms, 413 const BYTE* ip, const BYTE* const iLimit, 414 size_t* offsetPtr) 415 { 416 switch(ms->cParams.minMatch) 417 { 418 default : /* includes case 3 */ 419 case 4 : return ZSTD_BtFindBestMatch(ms, ip, iLimit, offsetPtr, 4, ZSTD_dictMatchState); 420 case 5 : return ZSTD_BtFindBestMatch(ms, ip, iLimit, offsetPtr, 5, ZSTD_dictMatchState); 421 case 7 : 422 case 6 : return ZSTD_BtFindBestMatch(ms, ip, iLimit, offsetPtr, 6, ZSTD_dictMatchState); 423 } 424 } 425 426 427 static size_t ZSTD_BtFindBestMatch_extDict_selectMLS ( 428 ZSTD_matchState_t* ms, 429 const BYTE* ip, const BYTE* const iLimit, 430 size_t* offsetPtr) 431 { 432 switch(ms->cParams.minMatch) 433 { 434 default : /* includes case 3 */ 435 case 4 : return ZSTD_BtFindBestMatch(ms, ip, iLimit, offsetPtr, 4, ZSTD_extDict); 436 case 5 : return ZSTD_BtFindBestMatch(ms, ip, iLimit, offsetPtr, 5, ZSTD_extDict); 437 case 7 : 438 case 6 : return ZSTD_BtFindBestMatch(ms, ip, iLimit, offsetPtr, 6, ZSTD_extDict); 439 } 440 } 441 442 443 444 /* ********************************* 445 * Hash Chain 446 ***********************************/ 447 #define NEXT_IN_CHAIN(d, mask) chainTable[(d) & (mask)] 448 449 /* Update chains up to ip (excluded) 450 Assumption : always within prefix (i.e. not within extDict) */ 451 static U32 ZSTD_insertAndFindFirstIndex_internal( 452 ZSTD_matchState_t* ms, 453 const ZSTD_compressionParameters* const cParams, 454 const BYTE* ip, U32 const mls) 455 { 456 U32* const hashTable = ms->hashTable; 457 const U32 hashLog = cParams->hashLog; 458 U32* const chainTable = ms->chainTable; 459 const U32 chainMask = (1 << cParams->chainLog) - 1; 460 const BYTE* const base = ms->window.base; 461 const U32 target = (U32)(ip - base); 462 U32 idx = ms->nextToUpdate; 463 464 while(idx < target) { /* catch up */ 465 size_t const h = ZSTD_hashPtr(base+idx, hashLog, mls); 466 NEXT_IN_CHAIN(idx, chainMask) = hashTable[h]; 467 hashTable[h] = idx; 468 idx++; 469 } 470 471 ms->nextToUpdate = target; 472 return hashTable[ZSTD_hashPtr(ip, hashLog, mls)]; 473 } 474 475 U32 ZSTD_insertAndFindFirstIndex(ZSTD_matchState_t* ms, const BYTE* ip) { 476 const ZSTD_compressionParameters* const cParams = &ms->cParams; 477 return ZSTD_insertAndFindFirstIndex_internal(ms, cParams, ip, ms->cParams.minMatch); 478 } 479 480 481 /* inlining is important to hardwire a hot branch (template emulation) */ 482 FORCE_INLINE_TEMPLATE 483 size_t ZSTD_HcFindBestMatch_generic ( 484 ZSTD_matchState_t* ms, 485 const BYTE* const ip, const BYTE* const iLimit, 486 size_t* offsetPtr, 487 const U32 mls, const ZSTD_dictMode_e dictMode) 488 { 489 const ZSTD_compressionParameters* const cParams = &ms->cParams; 490 U32* const chainTable = ms->chainTable; 491 const U32 chainSize = (1 << cParams->chainLog); 492 const U32 chainMask = chainSize-1; 493 const BYTE* const base = ms->window.base; 494 const BYTE* const dictBase = ms->window.dictBase; 495 const U32 dictLimit = ms->window.dictLimit; 496 const BYTE* const prefixStart = base + dictLimit; 497 const BYTE* const dictEnd = dictBase + dictLimit; 498 const U32 current = (U32)(ip-base); 499 const U32 maxDistance = 1U << cParams->windowLog; 500 const U32 lowValid = ms->window.lowLimit; 501 const U32 lowLimit = (current - lowValid > maxDistance) ? current - maxDistance : lowValid; 502 const U32 minChain = current > chainSize ? current - chainSize : 0; 503 U32 nbAttempts = 1U << cParams->searchLog; 504 size_t ml=4-1; 505 506 /* HC4 match finder */ 507 U32 matchIndex = ZSTD_insertAndFindFirstIndex_internal(ms, cParams, ip, mls); 508 509 for ( ; (matchIndex>lowLimit) & (nbAttempts>0) ; nbAttempts--) { 510 size_t currentMl=0; 511 if ((dictMode != ZSTD_extDict) || matchIndex >= dictLimit) { 512 const BYTE* const match = base + matchIndex; 513 assert(matchIndex >= dictLimit); /* ensures this is true if dictMode != ZSTD_extDict */ 514 if (match[ml] == ip[ml]) /* potentially better */ 515 currentMl = ZSTD_count(ip, match, iLimit); 516 } else { 517 const BYTE* const match = dictBase + matchIndex; 518 assert(match+4 <= dictEnd); 519 if (MEM_read32(match) == MEM_read32(ip)) /* assumption : matchIndex <= dictLimit-4 (by table construction) */ 520 currentMl = ZSTD_count_2segments(ip+4, match+4, iLimit, dictEnd, prefixStart) + 4; 521 } 522 523 /* save best solution */ 524 if (currentMl > ml) { 525 ml = currentMl; 526 *offsetPtr = current - matchIndex + ZSTD_REP_MOVE; 527 if (ip+currentMl == iLimit) break; /* best possible, avoids read overflow on next attempt */ 528 } 529 530 if (matchIndex <= minChain) break; 531 matchIndex = NEXT_IN_CHAIN(matchIndex, chainMask); 532 } 533 534 if (dictMode == ZSTD_dictMatchState) { 535 const ZSTD_matchState_t* const dms = ms->dictMatchState; 536 const U32* const dmsChainTable = dms->chainTable; 537 const U32 dmsChainSize = (1 << dms->cParams.chainLog); 538 const U32 dmsChainMask = dmsChainSize - 1; 539 const U32 dmsLowestIndex = dms->window.dictLimit; 540 const BYTE* const dmsBase = dms->window.base; 541 const BYTE* const dmsEnd = dms->window.nextSrc; 542 const U32 dmsSize = (U32)(dmsEnd - dmsBase); 543 const U32 dmsIndexDelta = dictLimit - dmsSize; 544 const U32 dmsMinChain = dmsSize > dmsChainSize ? dmsSize - dmsChainSize : 0; 545 546 matchIndex = dms->hashTable[ZSTD_hashPtr(ip, dms->cParams.hashLog, mls)]; 547 548 for ( ; (matchIndex>dmsLowestIndex) & (nbAttempts>0) ; nbAttempts--) { 549 size_t currentMl=0; 550 const BYTE* const match = dmsBase + matchIndex; 551 assert(match+4 <= dmsEnd); 552 if (MEM_read32(match) == MEM_read32(ip)) /* assumption : matchIndex <= dictLimit-4 (by table construction) */ 553 currentMl = ZSTD_count_2segments(ip+4, match+4, iLimit, dmsEnd, prefixStart) + 4; 554 555 /* save best solution */ 556 if (currentMl > ml) { 557 ml = currentMl; 558 *offsetPtr = current - (matchIndex + dmsIndexDelta) + ZSTD_REP_MOVE; 559 if (ip+currentMl == iLimit) break; /* best possible, avoids read overflow on next attempt */ 560 } 561 562 if (matchIndex <= dmsMinChain) break; 563 matchIndex = dmsChainTable[matchIndex & dmsChainMask]; 564 } 565 } 566 567 return ml; 568 } 569 570 571 FORCE_INLINE_TEMPLATE size_t ZSTD_HcFindBestMatch_selectMLS ( 572 ZSTD_matchState_t* ms, 573 const BYTE* ip, const BYTE* const iLimit, 574 size_t* offsetPtr) 575 { 576 switch(ms->cParams.minMatch) 577 { 578 default : /* includes case 3 */ 579 case 4 : return ZSTD_HcFindBestMatch_generic(ms, ip, iLimit, offsetPtr, 4, ZSTD_noDict); 580 case 5 : return ZSTD_HcFindBestMatch_generic(ms, ip, iLimit, offsetPtr, 5, ZSTD_noDict); 581 case 7 : 582 case 6 : return ZSTD_HcFindBestMatch_generic(ms, ip, iLimit, offsetPtr, 6, ZSTD_noDict); 583 } 584 } 585 586 587 static size_t ZSTD_HcFindBestMatch_dictMatchState_selectMLS ( 588 ZSTD_matchState_t* ms, 589 const BYTE* ip, const BYTE* const iLimit, 590 size_t* offsetPtr) 591 { 592 switch(ms->cParams.minMatch) 593 { 594 default : /* includes case 3 */ 595 case 4 : return ZSTD_HcFindBestMatch_generic(ms, ip, iLimit, offsetPtr, 4, ZSTD_dictMatchState); 596 case 5 : return ZSTD_HcFindBestMatch_generic(ms, ip, iLimit, offsetPtr, 5, ZSTD_dictMatchState); 597 case 7 : 598 case 6 : return ZSTD_HcFindBestMatch_generic(ms, ip, iLimit, offsetPtr, 6, ZSTD_dictMatchState); 599 } 600 } 601 602 603 FORCE_INLINE_TEMPLATE size_t ZSTD_HcFindBestMatch_extDict_selectMLS ( 604 ZSTD_matchState_t* ms, 605 const BYTE* ip, const BYTE* const iLimit, 606 size_t* offsetPtr) 607 { 608 switch(ms->cParams.minMatch) 609 { 610 default : /* includes case 3 */ 611 case 4 : return ZSTD_HcFindBestMatch_generic(ms, ip, iLimit, offsetPtr, 4, ZSTD_extDict); 612 case 5 : return ZSTD_HcFindBestMatch_generic(ms, ip, iLimit, offsetPtr, 5, ZSTD_extDict); 613 case 7 : 614 case 6 : return ZSTD_HcFindBestMatch_generic(ms, ip, iLimit, offsetPtr, 6, ZSTD_extDict); 615 } 616 } 617 618 619 /* ******************************* 620 * Common parser - lazy strategy 621 *********************************/ 622 FORCE_INLINE_TEMPLATE 623 size_t ZSTD_compressBlock_lazy_generic( 624 ZSTD_matchState_t* ms, seqStore_t* seqStore, 625 U32 rep[ZSTD_REP_NUM], 626 const void* src, size_t srcSize, 627 const U32 searchMethod, const U32 depth, 628 ZSTD_dictMode_e const dictMode) 629 { 630 const BYTE* const istart = (const BYTE*)src; 631 const BYTE* ip = istart; 632 const BYTE* anchor = istart; 633 const BYTE* const iend = istart + srcSize; 634 const BYTE* const ilimit = iend - 8; 635 const BYTE* const base = ms->window.base; 636 const U32 prefixLowestIndex = ms->window.dictLimit; 637 const BYTE* const prefixLowest = base + prefixLowestIndex; 638 639 typedef size_t (*searchMax_f)( 640 ZSTD_matchState_t* ms, 641 const BYTE* ip, const BYTE* iLimit, size_t* offsetPtr); 642 searchMax_f const searchMax = dictMode == ZSTD_dictMatchState ? 643 (searchMethod ? ZSTD_BtFindBestMatch_dictMatchState_selectMLS : ZSTD_HcFindBestMatch_dictMatchState_selectMLS) : 644 (searchMethod ? ZSTD_BtFindBestMatch_selectMLS : ZSTD_HcFindBestMatch_selectMLS); 645 U32 offset_1 = rep[0], offset_2 = rep[1], savedOffset=0; 646 647 const ZSTD_matchState_t* const dms = ms->dictMatchState; 648 const U32 dictLowestIndex = dictMode == ZSTD_dictMatchState ? 649 dms->window.dictLimit : 0; 650 const BYTE* const dictBase = dictMode == ZSTD_dictMatchState ? 651 dms->window.base : NULL; 652 const BYTE* const dictLowest = dictMode == ZSTD_dictMatchState ? 653 dictBase + dictLowestIndex : NULL; 654 const BYTE* const dictEnd = dictMode == ZSTD_dictMatchState ? 655 dms->window.nextSrc : NULL; 656 const U32 dictIndexDelta = dictMode == ZSTD_dictMatchState ? 657 prefixLowestIndex - (U32)(dictEnd - dictBase) : 658 0; 659 const U32 dictAndPrefixLength = (U32)(ip - prefixLowest + dictEnd - dictLowest); 660 661 /* init */ 662 ip += (dictAndPrefixLength == 0); 663 if (dictMode == ZSTD_noDict) { 664 U32 const maxRep = (U32)(ip - prefixLowest); 665 if (offset_2 > maxRep) savedOffset = offset_2, offset_2 = 0; 666 if (offset_1 > maxRep) savedOffset = offset_1, offset_1 = 0; 667 } 668 if (dictMode == ZSTD_dictMatchState) { 669 /* dictMatchState repCode checks don't currently handle repCode == 0 670 * disabling. */ 671 assert(offset_1 <= dictAndPrefixLength); 672 assert(offset_2 <= dictAndPrefixLength); 673 } 674 675 /* Match Loop */ 676 while (ip < ilimit) { 677 size_t matchLength=0; 678 size_t offset=0; 679 const BYTE* start=ip+1; 680 681 /* check repCode */ 682 if (dictMode == ZSTD_dictMatchState) { 683 const U32 repIndex = (U32)(ip - base) + 1 - offset_1; 684 const BYTE* repMatch = (dictMode == ZSTD_dictMatchState 685 && repIndex < prefixLowestIndex) ? 686 dictBase + (repIndex - dictIndexDelta) : 687 base + repIndex; 688 if (((U32)((prefixLowestIndex-1) - repIndex) >= 3 /* intentional underflow */) 689 && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) { 690 const BYTE* repMatchEnd = repIndex < prefixLowestIndex ? dictEnd : iend; 691 matchLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, prefixLowest) + 4; 692 if (depth==0) goto _storeSequence; 693 } 694 } 695 if ( dictMode == ZSTD_noDict 696 && ((offset_1 > 0) & (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1)))) { 697 matchLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4; 698 if (depth==0) goto _storeSequence; 699 } 700 701 /* first search (depth 0) */ 702 { size_t offsetFound = 999999999; 703 size_t const ml2 = searchMax(ms, ip, iend, &offsetFound); 704 if (ml2 > matchLength) 705 matchLength = ml2, start = ip, offset=offsetFound; 706 } 707 708 if (matchLength < 4) { 709 ip += ((ip-anchor) >> kSearchStrength) + 1; /* jump faster over incompressible sections */ 710 continue; 711 } 712 713 /* let's try to find a better solution */ 714 if (depth>=1) 715 while (ip<ilimit) { 716 ip ++; 717 if ( (dictMode == ZSTD_noDict) 718 && (offset) && ((offset_1>0) & (MEM_read32(ip) == MEM_read32(ip - offset_1)))) { 719 size_t const mlRep = ZSTD_count(ip+4, ip+4-offset_1, iend) + 4; 720 int const gain2 = (int)(mlRep * 3); 721 int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)offset+1) + 1); 722 if ((mlRep >= 4) && (gain2 > gain1)) 723 matchLength = mlRep, offset = 0, start = ip; 724 } 725 if (dictMode == ZSTD_dictMatchState) { 726 const U32 repIndex = (U32)(ip - base) - offset_1; 727 const BYTE* repMatch = repIndex < prefixLowestIndex ? 728 dictBase + (repIndex - dictIndexDelta) : 729 base + repIndex; 730 if (((U32)((prefixLowestIndex-1) - repIndex) >= 3 /* intentional underflow */) 731 && (MEM_read32(repMatch) == MEM_read32(ip)) ) { 732 const BYTE* repMatchEnd = repIndex < prefixLowestIndex ? dictEnd : iend; 733 size_t const mlRep = ZSTD_count_2segments(ip+4, repMatch+4, iend, repMatchEnd, prefixLowest) + 4; 734 int const gain2 = (int)(mlRep * 3); 735 int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)offset+1) + 1); 736 if ((mlRep >= 4) && (gain2 > gain1)) 737 matchLength = mlRep, offset = 0, start = ip; 738 } 739 } 740 { size_t offset2=999999999; 741 size_t const ml2 = searchMax(ms, ip, iend, &offset2); 742 int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1)); /* raw approx */ 743 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 4); 744 if ((ml2 >= 4) && (gain2 > gain1)) { 745 matchLength = ml2, offset = offset2, start = ip; 746 continue; /* search a better one */ 747 } } 748 749 /* let's find an even better one */ 750 if ((depth==2) && (ip<ilimit)) { 751 ip ++; 752 if ( (dictMode == ZSTD_noDict) 753 && (offset) && ((offset_1>0) & (MEM_read32(ip) == MEM_read32(ip - offset_1)))) { 754 size_t const mlRep = ZSTD_count(ip+4, ip+4-offset_1, iend) + 4; 755 int const gain2 = (int)(mlRep * 4); 756 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 1); 757 if ((mlRep >= 4) && (gain2 > gain1)) 758 matchLength = mlRep, offset = 0, start = ip; 759 } 760 if (dictMode == ZSTD_dictMatchState) { 761 const U32 repIndex = (U32)(ip - base) - offset_1; 762 const BYTE* repMatch = repIndex < prefixLowestIndex ? 763 dictBase + (repIndex - dictIndexDelta) : 764 base + repIndex; 765 if (((U32)((prefixLowestIndex-1) - repIndex) >= 3 /* intentional underflow */) 766 && (MEM_read32(repMatch) == MEM_read32(ip)) ) { 767 const BYTE* repMatchEnd = repIndex < prefixLowestIndex ? dictEnd : iend; 768 size_t const mlRep = ZSTD_count_2segments(ip+4, repMatch+4, iend, repMatchEnd, prefixLowest) + 4; 769 int const gain2 = (int)(mlRep * 4); 770 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 1); 771 if ((mlRep >= 4) && (gain2 > gain1)) 772 matchLength = mlRep, offset = 0, start = ip; 773 } 774 } 775 { size_t offset2=999999999; 776 size_t const ml2 = searchMax(ms, ip, iend, &offset2); 777 int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1)); /* raw approx */ 778 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 7); 779 if ((ml2 >= 4) && (gain2 > gain1)) { 780 matchLength = ml2, offset = offset2, start = ip; 781 continue; 782 } } } 783 break; /* nothing found : store previous solution */ 784 } 785 786 /* NOTE: 787 * start[-offset+ZSTD_REP_MOVE-1] is undefined behavior. 788 * (-offset+ZSTD_REP_MOVE-1) is unsigned, and is added to start, which 789 * overflows the pointer, which is undefined behavior. 790 */ 791 /* catch up */ 792 if (offset) { 793 if (dictMode == ZSTD_noDict) { 794 while ( ((start > anchor) & (start - (offset-ZSTD_REP_MOVE) > prefixLowest)) 795 && (start[-1] == (start-(offset-ZSTD_REP_MOVE))[-1]) ) /* only search for offset within prefix */ 796 { start--; matchLength++; } 797 } 798 if (dictMode == ZSTD_dictMatchState) { 799 U32 const matchIndex = (U32)((start-base) - (offset - ZSTD_REP_MOVE)); 800 const BYTE* match = (matchIndex < prefixLowestIndex) ? dictBase + matchIndex - dictIndexDelta : base + matchIndex; 801 const BYTE* const mStart = (matchIndex < prefixLowestIndex) ? dictLowest : prefixLowest; 802 while ((start>anchor) && (match>mStart) && (start[-1] == match[-1])) { start--; match--; matchLength++; } /* catch up */ 803 } 804 offset_2 = offset_1; offset_1 = (U32)(offset - ZSTD_REP_MOVE); 805 } 806 /* store sequence */ 807 _storeSequence: 808 { size_t const litLength = start - anchor; 809 ZSTD_storeSeq(seqStore, litLength, anchor, (U32)offset, matchLength-MINMATCH); 810 anchor = ip = start + matchLength; 811 } 812 813 /* check immediate repcode */ 814 if (dictMode == ZSTD_dictMatchState) { 815 while (ip <= ilimit) { 816 U32 const current2 = (U32)(ip-base); 817 U32 const repIndex = current2 - offset_2; 818 const BYTE* repMatch = dictMode == ZSTD_dictMatchState 819 && repIndex < prefixLowestIndex ? 820 dictBase - dictIndexDelta + repIndex : 821 base + repIndex; 822 if ( ((U32)((prefixLowestIndex-1) - (U32)repIndex) >= 3 /* intentional overflow */) 823 && (MEM_read32(repMatch) == MEM_read32(ip)) ) { 824 const BYTE* const repEnd2 = repIndex < prefixLowestIndex ? dictEnd : iend; 825 matchLength = ZSTD_count_2segments(ip+4, repMatch+4, iend, repEnd2, prefixLowest) + 4; 826 offset = offset_2; offset_2 = offset_1; offset_1 = (U32)offset; /* swap offset_2 <=> offset_1 */ 827 ZSTD_storeSeq(seqStore, 0, anchor, 0, matchLength-MINMATCH); 828 ip += matchLength; 829 anchor = ip; 830 continue; 831 } 832 break; 833 } 834 } 835 836 if (dictMode == ZSTD_noDict) { 837 while ( ((ip <= ilimit) & (offset_2>0)) 838 && (MEM_read32(ip) == MEM_read32(ip - offset_2)) ) { 839 /* store sequence */ 840 matchLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4; 841 offset = offset_2; offset_2 = offset_1; offset_1 = (U32)offset; /* swap repcodes */ 842 ZSTD_storeSeq(seqStore, 0, anchor, 0, matchLength-MINMATCH); 843 ip += matchLength; 844 anchor = ip; 845 continue; /* faster when present ... (?) */ 846 } } } 847 848 /* Save reps for next block */ 849 rep[0] = offset_1 ? offset_1 : savedOffset; 850 rep[1] = offset_2 ? offset_2 : savedOffset; 851 852 /* Return the last literals size */ 853 return iend - anchor; 854 } 855 856 857 size_t ZSTD_compressBlock_btlazy2( 858 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 859 void const* src, size_t srcSize) 860 { 861 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 1, 2, ZSTD_noDict); 862 } 863 864 size_t ZSTD_compressBlock_lazy2( 865 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 866 void const* src, size_t srcSize) 867 { 868 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 0, 2, ZSTD_noDict); 869 } 870 871 size_t ZSTD_compressBlock_lazy( 872 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 873 void const* src, size_t srcSize) 874 { 875 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 0, 1, ZSTD_noDict); 876 } 877 878 size_t ZSTD_compressBlock_greedy( 879 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 880 void const* src, size_t srcSize) 881 { 882 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 0, 0, ZSTD_noDict); 883 } 884 885 size_t ZSTD_compressBlock_btlazy2_dictMatchState( 886 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 887 void const* src, size_t srcSize) 888 { 889 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 1, 2, ZSTD_dictMatchState); 890 } 891 892 size_t ZSTD_compressBlock_lazy2_dictMatchState( 893 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 894 void const* src, size_t srcSize) 895 { 896 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 0, 2, ZSTD_dictMatchState); 897 } 898 899 size_t ZSTD_compressBlock_lazy_dictMatchState( 900 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 901 void const* src, size_t srcSize) 902 { 903 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 0, 1, ZSTD_dictMatchState); 904 } 905 906 size_t ZSTD_compressBlock_greedy_dictMatchState( 907 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 908 void const* src, size_t srcSize) 909 { 910 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 0, 0, ZSTD_dictMatchState); 911 } 912 913 914 FORCE_INLINE_TEMPLATE 915 size_t ZSTD_compressBlock_lazy_extDict_generic( 916 ZSTD_matchState_t* ms, seqStore_t* seqStore, 917 U32 rep[ZSTD_REP_NUM], 918 const void* src, size_t srcSize, 919 const U32 searchMethod, const U32 depth) 920 { 921 const BYTE* const istart = (const BYTE*)src; 922 const BYTE* ip = istart; 923 const BYTE* anchor = istart; 924 const BYTE* const iend = istart + srcSize; 925 const BYTE* const ilimit = iend - 8; 926 const BYTE* const base = ms->window.base; 927 const U32 dictLimit = ms->window.dictLimit; 928 const U32 lowestIndex = ms->window.lowLimit; 929 const BYTE* const prefixStart = base + dictLimit; 930 const BYTE* const dictBase = ms->window.dictBase; 931 const BYTE* const dictEnd = dictBase + dictLimit; 932 const BYTE* const dictStart = dictBase + lowestIndex; 933 934 typedef size_t (*searchMax_f)( 935 ZSTD_matchState_t* ms, 936 const BYTE* ip, const BYTE* iLimit, size_t* offsetPtr); 937 searchMax_f searchMax = searchMethod ? ZSTD_BtFindBestMatch_extDict_selectMLS : ZSTD_HcFindBestMatch_extDict_selectMLS; 938 939 U32 offset_1 = rep[0], offset_2 = rep[1]; 940 941 /* init */ 942 ip += (ip == prefixStart); 943 944 /* Match Loop */ 945 while (ip < ilimit) { 946 size_t matchLength=0; 947 size_t offset=0; 948 const BYTE* start=ip+1; 949 U32 current = (U32)(ip-base); 950 951 /* check repCode */ 952 { const U32 repIndex = (U32)(current+1 - offset_1); 953 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base; 954 const BYTE* const repMatch = repBase + repIndex; 955 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */ 956 if (MEM_read32(ip+1) == MEM_read32(repMatch)) { 957 /* repcode detected we should take it */ 958 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend; 959 matchLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repEnd, prefixStart) + 4; 960 if (depth==0) goto _storeSequence; 961 } } 962 963 /* first search (depth 0) */ 964 { size_t offsetFound = 999999999; 965 size_t const ml2 = searchMax(ms, ip, iend, &offsetFound); 966 if (ml2 > matchLength) 967 matchLength = ml2, start = ip, offset=offsetFound; 968 } 969 970 if (matchLength < 4) { 971 ip += ((ip-anchor) >> kSearchStrength) + 1; /* jump faster over incompressible sections */ 972 continue; 973 } 974 975 /* let's try to find a better solution */ 976 if (depth>=1) 977 while (ip<ilimit) { 978 ip ++; 979 current++; 980 /* check repCode */ 981 if (offset) { 982 const U32 repIndex = (U32)(current - offset_1); 983 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base; 984 const BYTE* const repMatch = repBase + repIndex; 985 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */ 986 if (MEM_read32(ip) == MEM_read32(repMatch)) { 987 /* repcode detected */ 988 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend; 989 size_t const repLength = ZSTD_count_2segments(ip+4, repMatch+4, iend, repEnd, prefixStart) + 4; 990 int const gain2 = (int)(repLength * 3); 991 int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)offset+1) + 1); 992 if ((repLength >= 4) && (gain2 > gain1)) 993 matchLength = repLength, offset = 0, start = ip; 994 } } 995 996 /* search match, depth 1 */ 997 { size_t offset2=999999999; 998 size_t const ml2 = searchMax(ms, ip, iend, &offset2); 999 int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1)); /* raw approx */ 1000 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 4); 1001 if ((ml2 >= 4) && (gain2 > gain1)) { 1002 matchLength = ml2, offset = offset2, start = ip; 1003 continue; /* search a better one */ 1004 } } 1005 1006 /* let's find an even better one */ 1007 if ((depth==2) && (ip<ilimit)) { 1008 ip ++; 1009 current++; 1010 /* check repCode */ 1011 if (offset) { 1012 const U32 repIndex = (U32)(current - offset_1); 1013 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base; 1014 const BYTE* const repMatch = repBase + repIndex; 1015 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */ 1016 if (MEM_read32(ip) == MEM_read32(repMatch)) { 1017 /* repcode detected */ 1018 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend; 1019 size_t const repLength = ZSTD_count_2segments(ip+4, repMatch+4, iend, repEnd, prefixStart) + 4; 1020 int const gain2 = (int)(repLength * 4); 1021 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 1); 1022 if ((repLength >= 4) && (gain2 > gain1)) 1023 matchLength = repLength, offset = 0, start = ip; 1024 } } 1025 1026 /* search match, depth 2 */ 1027 { size_t offset2=999999999; 1028 size_t const ml2 = searchMax(ms, ip, iend, &offset2); 1029 int const gain2 = (int)(ml2*4 - ZSTD_highbit32((U32)offset2+1)); /* raw approx */ 1030 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 7); 1031 if ((ml2 >= 4) && (gain2 > gain1)) { 1032 matchLength = ml2, offset = offset2, start = ip; 1033 continue; 1034 } } } 1035 break; /* nothing found : store previous solution */ 1036 } 1037 1038 /* catch up */ 1039 if (offset) { 1040 U32 const matchIndex = (U32)((start-base) - (offset - ZSTD_REP_MOVE)); 1041 const BYTE* match = (matchIndex < dictLimit) ? dictBase + matchIndex : base + matchIndex; 1042 const BYTE* const mStart = (matchIndex < dictLimit) ? dictStart : prefixStart; 1043 while ((start>anchor) && (match>mStart) && (start[-1] == match[-1])) { start--; match--; matchLength++; } /* catch up */ 1044 offset_2 = offset_1; offset_1 = (U32)(offset - ZSTD_REP_MOVE); 1045 } 1046 1047 /* store sequence */ 1048 _storeSequence: 1049 { size_t const litLength = start - anchor; 1050 ZSTD_storeSeq(seqStore, litLength, anchor, (U32)offset, matchLength-MINMATCH); 1051 anchor = ip = start + matchLength; 1052 } 1053 1054 /* check immediate repcode */ 1055 while (ip <= ilimit) { 1056 const U32 repIndex = (U32)((ip-base) - offset_2); 1057 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base; 1058 const BYTE* const repMatch = repBase + repIndex; 1059 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */ 1060 if (MEM_read32(ip) == MEM_read32(repMatch)) { 1061 /* repcode detected we should take it */ 1062 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend; 1063 matchLength = ZSTD_count_2segments(ip+4, repMatch+4, iend, repEnd, prefixStart) + 4; 1064 offset = offset_2; offset_2 = offset_1; offset_1 = (U32)offset; /* swap offset history */ 1065 ZSTD_storeSeq(seqStore, 0, anchor, 0, matchLength-MINMATCH); 1066 ip += matchLength; 1067 anchor = ip; 1068 continue; /* faster when present ... (?) */ 1069 } 1070 break; 1071 } } 1072 1073 /* Save reps for next block */ 1074 rep[0] = offset_1; 1075 rep[1] = offset_2; 1076 1077 /* Return the last literals size */ 1078 return iend - anchor; 1079 } 1080 1081 1082 size_t ZSTD_compressBlock_greedy_extDict( 1083 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 1084 void const* src, size_t srcSize) 1085 { 1086 return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, 0, 0); 1087 } 1088 1089 size_t ZSTD_compressBlock_lazy_extDict( 1090 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 1091 void const* src, size_t srcSize) 1092 1093 { 1094 return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, 0, 1); 1095 } 1096 1097 size_t ZSTD_compressBlock_lazy2_extDict( 1098 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 1099 void const* src, size_t srcSize) 1100 1101 { 1102 return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, 0, 2); 1103 } 1104 1105 size_t ZSTD_compressBlock_btlazy2_extDict( 1106 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 1107 void const* src, size_t srcSize) 1108 1109 { 1110 return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, 1, 2); 1111 } 1112