676 lines · c
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 the6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found7 * 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" /* ZSTD_hashPtr, ZSTD_count, ZSTD_storeSeq */12#include "zstd_fast.h"13 14 15void ZSTD_fillHashTable(ZSTD_matchState_t* ms,16 const void* const end,17 ZSTD_dictTableLoadMethod_e dtlm)18{19 const ZSTD_compressionParameters* const cParams = &ms->cParams;20 U32* const hashTable = ms->hashTable;21 U32 const hBits = cParams->hashLog;22 U32 const mls = cParams->minMatch;23 const BYTE* const base = ms->window.base;24 const BYTE* ip = base + ms->nextToUpdate;25 const BYTE* const iend = ((const BYTE*)end) - HASH_READ_SIZE;26 const U32 fastHashFillStep = 3;27 28 /* Always insert every fastHashFillStep position into the hash table.29 * Insert the other positions if their hash entry is empty.30 */31 for ( ; ip + fastHashFillStep < iend + 2; ip += fastHashFillStep) {32 U32 const curr = (U32)(ip - base);33 size_t const hash0 = ZSTD_hashPtr(ip, hBits, mls);34 hashTable[hash0] = curr;35 if (dtlm == ZSTD_dtlm_fast) continue;36 /* Only load extra positions for ZSTD_dtlm_full */37 { U32 p;38 for (p = 1; p < fastHashFillStep; ++p) {39 size_t const hash = ZSTD_hashPtr(ip + p, hBits, mls);40 if (hashTable[hash] == 0) { /* not yet filled */41 hashTable[hash] = curr + p;42 } } } }43}44 45 46/*47 * If you squint hard enough (and ignore repcodes), the search operation at any48 * given position is broken into 4 stages:49 *50 * 1. Hash (map position to hash value via input read)51 * 2. Lookup (map hash val to index via hashtable read)52 * 3. Load (map index to value at that position via input read)53 * 4. Compare54 *55 * Each of these steps involves a memory read at an address which is computed56 * from the previous step. This means these steps must be sequenced and their57 * latencies are cumulative.58 *59 * Rather than do 1->2->3->4 sequentially for a single position before moving60 * onto the next, this implementation interleaves these operations across the61 * next few positions:62 *63 * R = Repcode Read & Compare64 * H = Hash65 * T = Table Lookup66 * M = Match Read & Compare67 *68 * Pos | Time -->69 * ----+-------------------70 * N | ... M71 * N+1 | ... TM72 * N+2 | R H T M73 * N+3 | H TM74 * N+4 | R H T M75 * N+5 | H ...76 * N+6 | R ...77 *78 * This is very much analogous to the pipelining of execution in a CPU. And just79 * like a CPU, we have to dump the pipeline when we find a match (i.e., take a80 * branch).81 *82 * When this happens, we throw away our current state, and do the following prep83 * to re-enter the loop:84 *85 * Pos | Time -->86 * ----+-------------------87 * N | H T88 * N+1 | H89 *90 * This is also the work we do at the beginning to enter the loop initially.91 */92FORCE_INLINE_TEMPLATE size_t93ZSTD_compressBlock_fast_noDict_generic(94 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],95 void const* src, size_t srcSize,96 U32 const mls, U32 const hasStep)97{98 const ZSTD_compressionParameters* const cParams = &ms->cParams;99 U32* const hashTable = ms->hashTable;100 U32 const hlog = cParams->hashLog;101 /* support stepSize of 0 */102 size_t const stepSize = hasStep ? (cParams->targetLength + !(cParams->targetLength) + 1) : 2;103 const BYTE* const base = ms->window.base;104 const BYTE* const istart = (const BYTE*)src;105 const U32 endIndex = (U32)((size_t)(istart - base) + srcSize);106 const U32 prefixStartIndex = ZSTD_getLowestPrefixIndex(ms, endIndex, cParams->windowLog);107 const BYTE* const prefixStart = base + prefixStartIndex;108 const BYTE* const iend = istart + srcSize;109 const BYTE* const ilimit = iend - HASH_READ_SIZE;110 111 const BYTE* anchor = istart;112 const BYTE* ip0 = istart;113 const BYTE* ip1;114 const BYTE* ip2;115 const BYTE* ip3;116 U32 current0;117 118 U32 rep_offset1 = rep[0];119 U32 rep_offset2 = rep[1];120 U32 offsetSaved = 0;121 122 size_t hash0; /* hash for ip0 */123 size_t hash1; /* hash for ip1 */124 U32 idx; /* match idx for ip0 */125 U32 mval; /* src value at match idx */126 127 U32 offcode;128 const BYTE* match0;129 size_t mLength;130 131 /* ip0 and ip1 are always adjacent. The targetLength skipping and132 * uncompressibility acceleration is applied to every other position,133 * matching the behavior of #1562. step therefore represents the gap134 * between pairs of positions, from ip0 to ip2 or ip1 to ip3. */135 size_t step;136 const BYTE* nextStep;137 const size_t kStepIncr = (1 << (kSearchStrength - 1));138 139 DEBUGLOG(5, "ZSTD_compressBlock_fast_generic");140 ip0 += (ip0 == prefixStart);141 { U32 const curr = (U32)(ip0 - base);142 U32 const windowLow = ZSTD_getLowestPrefixIndex(ms, curr, cParams->windowLog);143 U32 const maxRep = curr - windowLow;144 if (rep_offset2 > maxRep) offsetSaved = rep_offset2, rep_offset2 = 0;145 if (rep_offset1 > maxRep) offsetSaved = rep_offset1, rep_offset1 = 0;146 }147 148 /* start each op */149_start: /* Requires: ip0 */150 151 step = stepSize;152 nextStep = ip0 + kStepIncr;153 154 /* calculate positions, ip0 - anchor == 0, so we skip step calc */155 ip1 = ip0 + 1;156 ip2 = ip0 + step;157 ip3 = ip2 + 1;158 159 if (ip3 >= ilimit) {160 goto _cleanup;161 }162 163 hash0 = ZSTD_hashPtr(ip0, hlog, mls);164 hash1 = ZSTD_hashPtr(ip1, hlog, mls);165 166 idx = hashTable[hash0];167 168 do {169 /* load repcode match for ip[2]*/170 const U32 rval = MEM_read32(ip2 - rep_offset1);171 172 /* write back hash table entry */173 current0 = (U32)(ip0 - base);174 hashTable[hash0] = current0;175 176 /* check repcode at ip[2] */177 if ((MEM_read32(ip2) == rval) & (rep_offset1 > 0)) {178 ip0 = ip2;179 match0 = ip0 - rep_offset1;180 mLength = ip0[-1] == match0[-1];181 ip0 -= mLength;182 match0 -= mLength;183 offcode = STORE_REPCODE_1;184 mLength += 4;185 goto _match;186 }187 188 /* load match for ip[0] */189 if (idx >= prefixStartIndex) {190 mval = MEM_read32(base + idx);191 } else {192 mval = MEM_read32(ip0) ^ 1; /* guaranteed to not match. */193 }194 195 /* check match at ip[0] */196 if (MEM_read32(ip0) == mval) {197 /* found a match! */198 goto _offset;199 }200 201 /* lookup ip[1] */202 idx = hashTable[hash1];203 204 /* hash ip[2] */205 hash0 = hash1;206 hash1 = ZSTD_hashPtr(ip2, hlog, mls);207 208 /* advance to next positions */209 ip0 = ip1;210 ip1 = ip2;211 ip2 = ip3;212 213 /* write back hash table entry */214 current0 = (U32)(ip0 - base);215 hashTable[hash0] = current0;216 217 /* load match for ip[0] */218 if (idx >= prefixStartIndex) {219 mval = MEM_read32(base + idx);220 } else {221 mval = MEM_read32(ip0) ^ 1; /* guaranteed to not match. */222 }223 224 /* check match at ip[0] */225 if (MEM_read32(ip0) == mval) {226 /* found a match! */227 goto _offset;228 }229 230 /* lookup ip[1] */231 idx = hashTable[hash1];232 233 /* hash ip[2] */234 hash0 = hash1;235 hash1 = ZSTD_hashPtr(ip2, hlog, mls);236 237 /* advance to next positions */238 ip0 = ip1;239 ip1 = ip2;240 ip2 = ip0 + step;241 ip3 = ip1 + step;242 243 /* calculate step */244 if (ip2 >= nextStep) {245 step++;246 PREFETCH_L1(ip1 + 64);247 PREFETCH_L1(ip1 + 128);248 nextStep += kStepIncr;249 }250 } while (ip3 < ilimit);251 252_cleanup:253 /* Note that there are probably still a couple positions we could search.254 * However, it seems to be a meaningful performance hit to try to search255 * them. So let's not. */256 257 /* save reps for next block */258 rep[0] = rep_offset1 ? rep_offset1 : offsetSaved;259 rep[1] = rep_offset2 ? rep_offset2 : offsetSaved;260 261 /* Return the last literals size */262 return (size_t)(iend - anchor);263 264_offset: /* Requires: ip0, idx */265 266 /* Compute the offset code. */267 match0 = base + idx;268 rep_offset2 = rep_offset1;269 rep_offset1 = (U32)(ip0-match0);270 offcode = STORE_OFFSET(rep_offset1);271 mLength = 4;272 273 /* Count the backwards match length. */274 while (((ip0>anchor) & (match0>prefixStart)) && (ip0[-1] == match0[-1])) {275 ip0--;276 match0--;277 mLength++;278 }279 280_match: /* Requires: ip0, match0, offcode */281 282 /* Count the forward length. */283 mLength += ZSTD_count(ip0 + mLength, match0 + mLength, iend);284 285 ZSTD_storeSeq(seqStore, (size_t)(ip0 - anchor), anchor, iend, offcode, mLength);286 287 ip0 += mLength;288 anchor = ip0;289 290 /* write next hash table entry */291 if (ip1 < ip0) {292 hashTable[hash1] = (U32)(ip1 - base);293 }294 295 /* Fill table and check for immediate repcode. */296 if (ip0 <= ilimit) {297 /* Fill Table */298 assert(base+current0+2 > istart); /* check base overflow */299 hashTable[ZSTD_hashPtr(base+current0+2, hlog, mls)] = current0+2; /* here because current+2 could be > iend-8 */300 hashTable[ZSTD_hashPtr(ip0-2, hlog, mls)] = (U32)(ip0-2-base);301 302 if (rep_offset2 > 0) { /* rep_offset2==0 means rep_offset2 is invalidated */303 while ( (ip0 <= ilimit) && (MEM_read32(ip0) == MEM_read32(ip0 - rep_offset2)) ) {304 /* store sequence */305 size_t const rLength = ZSTD_count(ip0+4, ip0+4-rep_offset2, iend) + 4;306 { U32 const tmpOff = rep_offset2; rep_offset2 = rep_offset1; rep_offset1 = tmpOff; } /* swap rep_offset2 <=> rep_offset1 */307 hashTable[ZSTD_hashPtr(ip0, hlog, mls)] = (U32)(ip0-base);308 ip0 += rLength;309 ZSTD_storeSeq(seqStore, 0 /*litLen*/, anchor, iend, STORE_REPCODE_1, rLength);310 anchor = ip0;311 continue; /* faster when present (confirmed on gcc-8) ... (?) */312 } } }313 314 goto _start;315}316 317#define ZSTD_GEN_FAST_FN(dictMode, mls, step) \318 static size_t ZSTD_compressBlock_fast_##dictMode##_##mls##_##step( \319 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], \320 void const* src, size_t srcSize) \321 { \322 return ZSTD_compressBlock_fast_##dictMode##_generic(ms, seqStore, rep, src, srcSize, mls, step); \323 }324 325ZSTD_GEN_FAST_FN(noDict, 4, 1)326ZSTD_GEN_FAST_FN(noDict, 5, 1)327ZSTD_GEN_FAST_FN(noDict, 6, 1)328ZSTD_GEN_FAST_FN(noDict, 7, 1)329 330ZSTD_GEN_FAST_FN(noDict, 4, 0)331ZSTD_GEN_FAST_FN(noDict, 5, 0)332ZSTD_GEN_FAST_FN(noDict, 6, 0)333ZSTD_GEN_FAST_FN(noDict, 7, 0)334 335size_t ZSTD_compressBlock_fast(336 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],337 void const* src, size_t srcSize)338{339 U32 const mls = ms->cParams.minMatch;340 assert(ms->dictMatchState == NULL);341 if (ms->cParams.targetLength > 1) {342 switch(mls)343 {344 default: /* includes case 3 */345 case 4 :346 return ZSTD_compressBlock_fast_noDict_4_1(ms, seqStore, rep, src, srcSize);347 case 5 :348 return ZSTD_compressBlock_fast_noDict_5_1(ms, seqStore, rep, src, srcSize);349 case 6 :350 return ZSTD_compressBlock_fast_noDict_6_1(ms, seqStore, rep, src, srcSize);351 case 7 :352 return ZSTD_compressBlock_fast_noDict_7_1(ms, seqStore, rep, src, srcSize);353 }354 } else {355 switch(mls)356 {357 default: /* includes case 3 */358 case 4 :359 return ZSTD_compressBlock_fast_noDict_4_0(ms, seqStore, rep, src, srcSize);360 case 5 :361 return ZSTD_compressBlock_fast_noDict_5_0(ms, seqStore, rep, src, srcSize);362 case 6 :363 return ZSTD_compressBlock_fast_noDict_6_0(ms, seqStore, rep, src, srcSize);364 case 7 :365 return ZSTD_compressBlock_fast_noDict_7_0(ms, seqStore, rep, src, srcSize);366 }367 368 }369}370 371FORCE_INLINE_TEMPLATE372size_t ZSTD_compressBlock_fast_dictMatchState_generic(373 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],374 void const* src, size_t srcSize, U32 const mls, U32 const hasStep)375{376 const ZSTD_compressionParameters* const cParams = &ms->cParams;377 U32* const hashTable = ms->hashTable;378 U32 const hlog = cParams->hashLog;379 /* support stepSize of 0 */380 U32 const stepSize = cParams->targetLength + !(cParams->targetLength);381 const BYTE* const base = ms->window.base;382 const BYTE* const istart = (const BYTE*)src;383 const BYTE* ip = istart;384 const BYTE* anchor = istart;385 const U32 prefixStartIndex = ms->window.dictLimit;386 const BYTE* const prefixStart = base + prefixStartIndex;387 const BYTE* const iend = istart + srcSize;388 const BYTE* const ilimit = iend - HASH_READ_SIZE;389 U32 offset_1=rep[0], offset_2=rep[1];390 U32 offsetSaved = 0;391 392 const ZSTD_matchState_t* const dms = ms->dictMatchState;393 const ZSTD_compressionParameters* const dictCParams = &dms->cParams ;394 const U32* const dictHashTable = dms->hashTable;395 const U32 dictStartIndex = dms->window.dictLimit;396 const BYTE* const dictBase = dms->window.base;397 const BYTE* const dictStart = dictBase + dictStartIndex;398 const BYTE* const dictEnd = dms->window.nextSrc;399 const U32 dictIndexDelta = prefixStartIndex - (U32)(dictEnd - dictBase);400 const U32 dictAndPrefixLength = (U32)(ip - prefixStart + dictEnd - dictStart);401 const U32 dictHLog = dictCParams->hashLog;402 403 /* if a dictionary is still attached, it necessarily means that404 * it is within window size. So we just check it. */405 const U32 maxDistance = 1U << cParams->windowLog;406 const U32 endIndex = (U32)((size_t)(ip - base) + srcSize);407 assert(endIndex - prefixStartIndex <= maxDistance);408 (void)maxDistance; (void)endIndex; /* these variables are not used when assert() is disabled */409 410 (void)hasStep; /* not currently specialized on whether it's accelerated */411 412 /* ensure there will be no underflow413 * when translating a dict index into a local index */414 assert(prefixStartIndex >= (U32)(dictEnd - dictBase));415 416 /* init */417 DEBUGLOG(5, "ZSTD_compressBlock_fast_dictMatchState_generic");418 ip += (dictAndPrefixLength == 0);419 /* dictMatchState repCode checks don't currently handle repCode == 0420 * disabling. */421 assert(offset_1 <= dictAndPrefixLength);422 assert(offset_2 <= dictAndPrefixLength);423 424 /* Main Search Loop */425 while (ip < ilimit) { /* < instead of <=, because repcode check at (ip+1) */426 size_t mLength;427 size_t const h = ZSTD_hashPtr(ip, hlog, mls);428 U32 const curr = (U32)(ip-base);429 U32 const matchIndex = hashTable[h];430 const BYTE* match = base + matchIndex;431 const U32 repIndex = curr + 1 - offset_1;432 const BYTE* repMatch = (repIndex < prefixStartIndex) ?433 dictBase + (repIndex - dictIndexDelta) :434 base + repIndex;435 hashTable[h] = curr; /* update hash table */436 437 if ( ((U32)((prefixStartIndex-1) - repIndex) >= 3) /* intentional underflow : ensure repIndex isn't overlapping dict + prefix */438 && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {439 const BYTE* const repMatchEnd = repIndex < prefixStartIndex ? dictEnd : iend;440 mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, prefixStart) + 4;441 ip++;442 ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, STORE_REPCODE_1, mLength);443 } else if ( (matchIndex <= prefixStartIndex) ) {444 size_t const dictHash = ZSTD_hashPtr(ip, dictHLog, mls);445 U32 const dictMatchIndex = dictHashTable[dictHash];446 const BYTE* dictMatch = dictBase + dictMatchIndex;447 if (dictMatchIndex <= dictStartIndex ||448 MEM_read32(dictMatch) != MEM_read32(ip)) {449 assert(stepSize >= 1);450 ip += ((ip-anchor) >> kSearchStrength) + stepSize;451 continue;452 } else {453 /* found a dict match */454 U32 const offset = (U32)(curr-dictMatchIndex-dictIndexDelta);455 mLength = ZSTD_count_2segments(ip+4, dictMatch+4, iend, dictEnd, prefixStart) + 4;456 while (((ip>anchor) & (dictMatch>dictStart))457 && (ip[-1] == dictMatch[-1])) {458 ip--; dictMatch--; mLength++;459 } /* catch up */460 offset_2 = offset_1;461 offset_1 = offset;462 ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, STORE_OFFSET(offset), mLength);463 }464 } else if (MEM_read32(match) != MEM_read32(ip)) {465 /* it's not a match, and we're not going to check the dictionary */466 assert(stepSize >= 1);467 ip += ((ip-anchor) >> kSearchStrength) + stepSize;468 continue;469 } else {470 /* found a regular match */471 U32 const offset = (U32)(ip-match);472 mLength = ZSTD_count(ip+4, match+4, iend) + 4;473 while (((ip>anchor) & (match>prefixStart))474 && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */475 offset_2 = offset_1;476 offset_1 = offset;477 ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, STORE_OFFSET(offset), mLength);478 }479 480 /* match found */481 ip += mLength;482 anchor = ip;483 484 if (ip <= ilimit) {485 /* Fill Table */486 assert(base+curr+2 > istart); /* check base overflow */487 hashTable[ZSTD_hashPtr(base+curr+2, hlog, mls)] = curr+2; /* here because curr+2 could be > iend-8 */488 hashTable[ZSTD_hashPtr(ip-2, hlog, mls)] = (U32)(ip-2-base);489 490 /* check immediate repcode */491 while (ip <= ilimit) {492 U32 const current2 = (U32)(ip-base);493 U32 const repIndex2 = current2 - offset_2;494 const BYTE* repMatch2 = repIndex2 < prefixStartIndex ?495 dictBase - dictIndexDelta + repIndex2 :496 base + repIndex2;497 if ( ((U32)((prefixStartIndex-1) - (U32)repIndex2) >= 3 /* intentional overflow */)498 && (MEM_read32(repMatch2) == MEM_read32(ip)) ) {499 const BYTE* const repEnd2 = repIndex2 < prefixStartIndex ? dictEnd : iend;500 size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, prefixStart) + 4;501 U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */502 ZSTD_storeSeq(seqStore, 0, anchor, iend, STORE_REPCODE_1, repLength2);503 hashTable[ZSTD_hashPtr(ip, hlog, mls)] = current2;504 ip += repLength2;505 anchor = ip;506 continue;507 }508 break;509 }510 }511 }512 513 /* save reps for next block */514 rep[0] = offset_1 ? offset_1 : offsetSaved;515 rep[1] = offset_2 ? offset_2 : offsetSaved;516 517 /* Return the last literals size */518 return (size_t)(iend - anchor);519}520 521 522ZSTD_GEN_FAST_FN(dictMatchState, 4, 0)523ZSTD_GEN_FAST_FN(dictMatchState, 5, 0)524ZSTD_GEN_FAST_FN(dictMatchState, 6, 0)525ZSTD_GEN_FAST_FN(dictMatchState, 7, 0)526 527size_t ZSTD_compressBlock_fast_dictMatchState(528 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],529 void const* src, size_t srcSize)530{531 U32 const mls = ms->cParams.minMatch;532 assert(ms->dictMatchState != NULL);533 switch(mls)534 {535 default: /* includes case 3 */536 case 4 :537 return ZSTD_compressBlock_fast_dictMatchState_4_0(ms, seqStore, rep, src, srcSize);538 case 5 :539 return ZSTD_compressBlock_fast_dictMatchState_5_0(ms, seqStore, rep, src, srcSize);540 case 6 :541 return ZSTD_compressBlock_fast_dictMatchState_6_0(ms, seqStore, rep, src, srcSize);542 case 7 :543 return ZSTD_compressBlock_fast_dictMatchState_7_0(ms, seqStore, rep, src, srcSize);544 }545}546 547 548static size_t ZSTD_compressBlock_fast_extDict_generic(549 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],550 void const* src, size_t srcSize, U32 const mls, U32 const hasStep)551{552 const ZSTD_compressionParameters* const cParams = &ms->cParams;553 U32* const hashTable = ms->hashTable;554 U32 const hlog = cParams->hashLog;555 /* support stepSize of 0 */556 U32 const stepSize = cParams->targetLength + !(cParams->targetLength);557 const BYTE* const base = ms->window.base;558 const BYTE* const dictBase = ms->window.dictBase;559 const BYTE* const istart = (const BYTE*)src;560 const BYTE* ip = istart;561 const BYTE* anchor = istart;562 const U32 endIndex = (U32)((size_t)(istart - base) + srcSize);563 const U32 lowLimit = ZSTD_getLowestMatchIndex(ms, endIndex, cParams->windowLog);564 const U32 dictStartIndex = lowLimit;565 const BYTE* const dictStart = dictBase + dictStartIndex;566 const U32 dictLimit = ms->window.dictLimit;567 const U32 prefixStartIndex = dictLimit < lowLimit ? lowLimit : dictLimit;568 const BYTE* const prefixStart = base + prefixStartIndex;569 const BYTE* const dictEnd = dictBase + prefixStartIndex;570 const BYTE* const iend = istart + srcSize;571 const BYTE* const ilimit = iend - 8;572 U32 offset_1=rep[0], offset_2=rep[1];573 574 (void)hasStep; /* not currently specialized on whether it's accelerated */575 576 DEBUGLOG(5, "ZSTD_compressBlock_fast_extDict_generic (offset_1=%u)", offset_1);577 578 /* switch to "regular" variant if extDict is invalidated due to maxDistance */579 if (prefixStartIndex == dictStartIndex)580 return ZSTD_compressBlock_fast(ms, seqStore, rep, src, srcSize);581 582 /* Search Loop */583 while (ip < ilimit) { /* < instead of <=, because (ip+1) */584 const size_t h = ZSTD_hashPtr(ip, hlog, mls);585 const U32 matchIndex = hashTable[h];586 const BYTE* const matchBase = matchIndex < prefixStartIndex ? dictBase : base;587 const BYTE* match = matchBase + matchIndex;588 const U32 curr = (U32)(ip-base);589 const U32 repIndex = curr + 1 - offset_1;590 const BYTE* const repBase = repIndex < prefixStartIndex ? dictBase : base;591 const BYTE* const repMatch = repBase + repIndex;592 hashTable[h] = curr; /* update hash table */593 DEBUGLOG(7, "offset_1 = %u , curr = %u", offset_1, curr);594 595 if ( ( ((U32)((prefixStartIndex-1) - repIndex) >= 3) /* intentional underflow */596 & (offset_1 <= curr+1 - dictStartIndex) ) /* note: we are searching at curr+1 */597 && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {598 const BYTE* const repMatchEnd = repIndex < prefixStartIndex ? dictEnd : iend;599 size_t const rLength = ZSTD_count_2segments(ip+1 +4, repMatch +4, iend, repMatchEnd, prefixStart) + 4;600 ip++;601 ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, STORE_REPCODE_1, rLength);602 ip += rLength;603 anchor = ip;604 } else {605 if ( (matchIndex < dictStartIndex) ||606 (MEM_read32(match) != MEM_read32(ip)) ) {607 assert(stepSize >= 1);608 ip += ((ip-anchor) >> kSearchStrength) + stepSize;609 continue;610 }611 { const BYTE* const matchEnd = matchIndex < prefixStartIndex ? dictEnd : iend;612 const BYTE* const lowMatchPtr = matchIndex < prefixStartIndex ? dictStart : prefixStart;613 U32 const offset = curr - matchIndex;614 size_t mLength = ZSTD_count_2segments(ip+4, match+4, iend, matchEnd, prefixStart) + 4;615 while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */616 offset_2 = offset_1; offset_1 = offset; /* update offset history */617 ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, STORE_OFFSET(offset), mLength);618 ip += mLength;619 anchor = ip;620 } }621 622 if (ip <= ilimit) {623 /* Fill Table */624 hashTable[ZSTD_hashPtr(base+curr+2, hlog, mls)] = curr+2;625 hashTable[ZSTD_hashPtr(ip-2, hlog, mls)] = (U32)(ip-2-base);626 /* check immediate repcode */627 while (ip <= ilimit) {628 U32 const current2 = (U32)(ip-base);629 U32 const repIndex2 = current2 - offset_2;630 const BYTE* const repMatch2 = repIndex2 < prefixStartIndex ? dictBase + repIndex2 : base + repIndex2;631 if ( (((U32)((prefixStartIndex-1) - repIndex2) >= 3) & (offset_2 <= curr - dictStartIndex)) /* intentional overflow */632 && (MEM_read32(repMatch2) == MEM_read32(ip)) ) {633 const BYTE* const repEnd2 = repIndex2 < prefixStartIndex ? dictEnd : iend;634 size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, prefixStart) + 4;635 { U32 const tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; } /* swap offset_2 <=> offset_1 */636 ZSTD_storeSeq(seqStore, 0 /*litlen*/, anchor, iend, STORE_REPCODE_1, repLength2);637 hashTable[ZSTD_hashPtr(ip, hlog, mls)] = current2;638 ip += repLength2;639 anchor = ip;640 continue;641 }642 break;643 } } }644 645 /* save reps for next block */646 rep[0] = offset_1;647 rep[1] = offset_2;648 649 /* Return the last literals size */650 return (size_t)(iend - anchor);651}652 653ZSTD_GEN_FAST_FN(extDict, 4, 0)654ZSTD_GEN_FAST_FN(extDict, 5, 0)655ZSTD_GEN_FAST_FN(extDict, 6, 0)656ZSTD_GEN_FAST_FN(extDict, 7, 0)657 658size_t ZSTD_compressBlock_fast_extDict(659 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],660 void const* src, size_t srcSize)661{662 U32 const mls = ms->cParams.minMatch;663 switch(mls)664 {665 default: /* includes case 3 */666 case 4 :667 return ZSTD_compressBlock_fast_extDict_4_0(ms, seqStore, rep, src, srcSize);668 case 5 :669 return ZSTD_compressBlock_fast_extDict_5_0(ms, seqStore, rep, src, srcSize);670 case 6 :671 return ZSTD_compressBlock_fast_extDict_6_0(ms, seqStore, rep, src, srcSize);672 case 7 :673 return ZSTD_compressBlock_fast_extDict_7_0(ms, seqStore, rep, src, srcSize);674 }675}676