-************************************* * Binary Tree search ***************************************/ ZSTD_insertBt1() : add one or multiple positions to tree. * ip : assumed <= iend-8 . * @return : nb of positions added */
| 367 | * ip : assumed <= iend-8 . |
| 368 | * @return : nb of positions added */ |
| 369 | static U32 ZSTD_insertBt1( |
| 370 | ZSTD_matchState_t* ms, |
| 371 | const BYTE* const ip, const BYTE* const iend, |
| 372 | U32 const mls, const int extDict) |
| 373 | { |
| 374 | const ZSTD_compressionParameters* const cParams = &ms->cParams; |
| 375 | U32* const hashTable = ms->hashTable; |
| 376 | U32 const hashLog = cParams->hashLog; |
| 377 | size_t const h = ZSTD_hashPtr(ip, hashLog, mls); |
| 378 | U32* const bt = ms->chainTable; |
| 379 | U32 const btLog = cParams->chainLog - 1; |
| 380 | U32 const btMask = (1 << btLog) - 1; |
| 381 | U32 matchIndex = hashTable[h]; |
| 382 | size_t commonLengthSmaller=0, commonLengthLarger=0; |
| 383 | const BYTE* const base = ms->window.base; |
| 384 | const BYTE* const dictBase = ms->window.dictBase; |
| 385 | const U32 dictLimit = ms->window.dictLimit; |
| 386 | const BYTE* const dictEnd = dictBase + dictLimit; |
| 387 | const BYTE* const prefixStart = base + dictLimit; |
| 388 | const BYTE* match; |
| 389 | const U32 curr = (U32)(ip-base); |
| 390 | const U32 btLow = btMask >= curr ? 0 : curr - btMask; |
| 391 | U32* smallerPtr = bt + 2*(curr&btMask); |
| 392 | U32* largerPtr = smallerPtr + 1; |
| 393 | U32 dummy32; /* to be nullified at the end */ |
| 394 | U32 const windowLow = ms->window.lowLimit; |
| 395 | U32 matchEndIdx = curr+8+1; |
| 396 | size_t bestLength = 8; |
| 397 | U32 nbCompares = 1U << cParams->searchLog; |
| 398 | #ifdef ZSTD_C_PREDICT |
| 399 | U32 predictedSmall = *(bt + 2*((curr-1)&btMask) + 0); |
| 400 | U32 predictedLarge = *(bt + 2*((curr-1)&btMask) + 1); |
| 401 | predictedSmall += (predictedSmall>0); |
| 402 | predictedLarge += (predictedLarge>0); |
| 403 | #endif /* ZSTD_C_PREDICT */ |
| 404 | |
| 405 | DEBUGLOG(8, "ZSTD_insertBt1 (%u)", curr); |
| 406 | |
| 407 | assert(ip <= iend-8); /* required for h calculation */ |
| 408 | hashTable[h] = curr; /* Update Hash Table */ |
| 409 | |
| 410 | assert(windowLow > 0); |
| 411 | while (nbCompares-- && (matchIndex >= windowLow)) { |
| 412 | U32* const nextPtr = bt + 2*(matchIndex & btMask); |
| 413 | size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */ |
| 414 | assert(matchIndex < curr); |
| 415 | |
| 416 | #ifdef ZSTD_C_PREDICT /* note : can create issues when hlog small <= 11 */ |
| 417 | const U32* predictPtr = bt + 2*((matchIndex-1) & btMask); /* written this way, as bt is a roll buffer */ |
| 418 | if (matchIndex == predictedSmall) { |
| 419 | /* no need to check length, result known */ |
| 420 | *smallerPtr = matchIndex; |
| 421 | if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */ |
| 422 | smallerPtr = nextPtr+1; /* new "smaller" => larger of match */ |
| 423 | matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */ |
| 424 | predictedSmall = predictPtr[1] + (predictPtr[1]>0); |
| 425 | continue; |
| 426 | } |
no test coverage detected