10c16b537SWarner Losh /* 237f1f268SConrad Meyer * Copyright (c) 2016-2020, Yann Collet, Facebook, Inc. 30c16b537SWarner Losh * All rights reserved. 40c16b537SWarner Losh * 50c16b537SWarner Losh * This source code is licensed under both the BSD-style license (found in the 60c16b537SWarner Losh * LICENSE file in the root directory of this source tree) and the GPLv2 (found 70c16b537SWarner Losh * in the COPYING file in the root directory of this source tree). 80c16b537SWarner Losh * You may select, at your option, one of the above-listed licenses. 90c16b537SWarner Losh */ 100c16b537SWarner Losh 11052d3c12SConrad Meyer #include "zstd_compress_internal.h" 120c16b537SWarner Losh #include "zstd_double_fast.h" 130c16b537SWarner Losh 140c16b537SWarner Losh 1519fcbaf1SConrad Meyer void ZSTD_fillDoubleHashTable(ZSTD_matchState_t* ms, 160f743729SConrad Meyer void const* end, ZSTD_dictTableLoadMethod_e dtlm) 170c16b537SWarner Losh { 180f743729SConrad Meyer const ZSTD_compressionParameters* const cParams = &ms->cParams; 1919fcbaf1SConrad Meyer U32* const hashLarge = ms->hashTable; 2019fcbaf1SConrad Meyer U32 const hBitsL = cParams->hashLog; 21a0483764SConrad Meyer U32 const mls = cParams->minMatch; 2219fcbaf1SConrad Meyer U32* const hashSmall = ms->chainTable; 2319fcbaf1SConrad Meyer U32 const hBitsS = cParams->chainLog; 2419fcbaf1SConrad Meyer const BYTE* const base = ms->window.base; 2519fcbaf1SConrad Meyer const BYTE* ip = base + ms->nextToUpdate; 260c16b537SWarner Losh const BYTE* const iend = ((const BYTE*)end) - HASH_READ_SIZE; 2719fcbaf1SConrad Meyer const U32 fastHashFillStep = 3; 280c16b537SWarner Losh 2919fcbaf1SConrad Meyer /* Always insert every fastHashFillStep position into the hash tables. 3019fcbaf1SConrad Meyer * Insert the other positions into the large hash table if their entry 3119fcbaf1SConrad Meyer * is empty. 3219fcbaf1SConrad Meyer */ 3319fcbaf1SConrad Meyer for (; ip + fastHashFillStep - 1 <= iend; ip += fastHashFillStep) { 34f7cd7fe5SConrad Meyer U32 const curr = (U32)(ip - base); 3519fcbaf1SConrad Meyer U32 i; 3619fcbaf1SConrad Meyer for (i = 0; i < fastHashFillStep; ++i) { 3719fcbaf1SConrad Meyer size_t const smHash = ZSTD_hashPtr(ip + i, hBitsS, mls); 3819fcbaf1SConrad Meyer size_t const lgHash = ZSTD_hashPtr(ip + i, hBitsL, 8); 3919fcbaf1SConrad Meyer if (i == 0) 40f7cd7fe5SConrad Meyer hashSmall[smHash] = curr + i; 4119fcbaf1SConrad Meyer if (i == 0 || hashLarge[lgHash] == 0) 42f7cd7fe5SConrad Meyer hashLarge[lgHash] = curr + i; 430f743729SConrad Meyer /* Only load extra positions for ZSTD_dtlm_full */ 440f743729SConrad Meyer if (dtlm == ZSTD_dtlm_fast) 450f743729SConrad Meyer break; 464d3f1eafSConrad Meyer } } 470c16b537SWarner Losh } 480c16b537SWarner Losh 490c16b537SWarner Losh 500c16b537SWarner Losh FORCE_INLINE_TEMPLATE 5119fcbaf1SConrad Meyer size_t ZSTD_compressBlock_doubleFast_generic( 5219fcbaf1SConrad Meyer ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 530f743729SConrad Meyer void const* src, size_t srcSize, 540f743729SConrad Meyer U32 const mls /* template */, ZSTD_dictMode_e const dictMode) 550c16b537SWarner Losh { 560f743729SConrad Meyer ZSTD_compressionParameters const* cParams = &ms->cParams; 5719fcbaf1SConrad Meyer U32* const hashLong = ms->hashTable; 5819fcbaf1SConrad Meyer const U32 hBitsL = cParams->hashLog; 5919fcbaf1SConrad Meyer U32* const hashSmall = ms->chainTable; 6019fcbaf1SConrad Meyer const U32 hBitsS = cParams->chainLog; 6119fcbaf1SConrad Meyer const BYTE* const base = ms->window.base; 620c16b537SWarner Losh const BYTE* const istart = (const BYTE*)src; 630c16b537SWarner Losh const BYTE* ip = istart; 640c16b537SWarner Losh const BYTE* anchor = istart; 654d3f1eafSConrad Meyer const U32 endIndex = (U32)((size_t)(istart - base) + srcSize); 669cbefe25SConrad Meyer /* presumes that, if there is a dictionary, it must be using Attach mode */ 6737f1f268SConrad Meyer const U32 prefixLowestIndex = ZSTD_getLowestPrefixIndex(ms, endIndex, cParams->windowLog); 680f743729SConrad Meyer const BYTE* const prefixLowest = base + prefixLowestIndex; 690c16b537SWarner Losh const BYTE* const iend = istart + srcSize; 700c16b537SWarner Losh const BYTE* const ilimit = iend - HASH_READ_SIZE; 7119fcbaf1SConrad Meyer U32 offset_1=rep[0], offset_2=rep[1]; 720c16b537SWarner Losh U32 offsetSaved = 0; 730c16b537SWarner Losh 740f743729SConrad Meyer const ZSTD_matchState_t* const dms = ms->dictMatchState; 750f743729SConrad Meyer const ZSTD_compressionParameters* const dictCParams = 760f743729SConrad Meyer dictMode == ZSTD_dictMatchState ? 770f743729SConrad Meyer &dms->cParams : NULL; 780f743729SConrad Meyer const U32* const dictHashLong = dictMode == ZSTD_dictMatchState ? 790f743729SConrad Meyer dms->hashTable : NULL; 800f743729SConrad Meyer const U32* const dictHashSmall = dictMode == ZSTD_dictMatchState ? 810f743729SConrad Meyer dms->chainTable : NULL; 820f743729SConrad Meyer const U32 dictStartIndex = dictMode == ZSTD_dictMatchState ? 830f743729SConrad Meyer dms->window.dictLimit : 0; 840f743729SConrad Meyer const BYTE* const dictBase = dictMode == ZSTD_dictMatchState ? 850f743729SConrad Meyer dms->window.base : NULL; 860f743729SConrad Meyer const BYTE* const dictStart = dictMode == ZSTD_dictMatchState ? 870f743729SConrad Meyer dictBase + dictStartIndex : NULL; 880f743729SConrad Meyer const BYTE* const dictEnd = dictMode == ZSTD_dictMatchState ? 890f743729SConrad Meyer dms->window.nextSrc : NULL; 900f743729SConrad Meyer const U32 dictIndexDelta = dictMode == ZSTD_dictMatchState ? 910f743729SConrad Meyer prefixLowestIndex - (U32)(dictEnd - dictBase) : 920f743729SConrad Meyer 0; 930f743729SConrad Meyer const U32 dictHBitsL = dictMode == ZSTD_dictMatchState ? 940f743729SConrad Meyer dictCParams->hashLog : hBitsL; 950f743729SConrad Meyer const U32 dictHBitsS = dictMode == ZSTD_dictMatchState ? 960f743729SConrad Meyer dictCParams->chainLog : hBitsS; 9737f1f268SConrad Meyer const U32 dictAndPrefixLength = (U32)((ip - prefixLowest) + (dictEnd - dictStart)); 980f743729SConrad Meyer 994d3f1eafSConrad Meyer DEBUGLOG(5, "ZSTD_compressBlock_doubleFast_generic"); 1004d3f1eafSConrad Meyer 1010f743729SConrad Meyer assert(dictMode == ZSTD_noDict || dictMode == ZSTD_dictMatchState); 1020f743729SConrad Meyer 1034d3f1eafSConrad Meyer /* if a dictionary is attached, it must be within window range */ 1044d3f1eafSConrad Meyer if (dictMode == ZSTD_dictMatchState) { 10537f1f268SConrad Meyer assert(ms->window.dictLimit + (1U << cParams->windowLog) >= endIndex); 1064d3f1eafSConrad Meyer } 1074d3f1eafSConrad Meyer 1080c16b537SWarner Losh /* init */ 1090f743729SConrad Meyer ip += (dictAndPrefixLength == 0); 1100f743729SConrad Meyer if (dictMode == ZSTD_noDict) { 111f7cd7fe5SConrad Meyer U32 const curr = (U32)(ip - base); 112f7cd7fe5SConrad Meyer U32 const windowLow = ZSTD_getLowestPrefixIndex(ms, curr, cParams->windowLog); 113f7cd7fe5SConrad Meyer U32 const maxRep = curr - windowLow; 1140c16b537SWarner Losh if (offset_2 > maxRep) offsetSaved = offset_2, offset_2 = 0; 1150c16b537SWarner Losh if (offset_1 > maxRep) offsetSaved = offset_1, offset_1 = 0; 1160c16b537SWarner Losh } 1170f743729SConrad Meyer if (dictMode == ZSTD_dictMatchState) { 1180f743729SConrad Meyer /* dictMatchState repCode checks don't currently handle repCode == 0 1190f743729SConrad Meyer * disabling. */ 1200f743729SConrad Meyer assert(offset_1 <= dictAndPrefixLength); 1210f743729SConrad Meyer assert(offset_2 <= dictAndPrefixLength); 1220f743729SConrad Meyer } 1230c16b537SWarner Losh 1240c16b537SWarner Losh /* Main Search Loop */ 1250c16b537SWarner Losh while (ip < ilimit) { /* < instead of <=, because repcode check at (ip+1) */ 1260c16b537SWarner Losh size_t mLength; 1270f743729SConrad Meyer U32 offset; 1280c16b537SWarner Losh size_t const h2 = ZSTD_hashPtr(ip, hBitsL, 8); 1290c16b537SWarner Losh size_t const h = ZSTD_hashPtr(ip, hBitsS, mls); 1300f743729SConrad Meyer size_t const dictHL = ZSTD_hashPtr(ip, dictHBitsL, 8); 1310f743729SConrad Meyer size_t const dictHS = ZSTD_hashPtr(ip, dictHBitsS, mls); 132f7cd7fe5SConrad Meyer U32 const curr = (U32)(ip-base); 1330c16b537SWarner Losh U32 const matchIndexL = hashLong[h2]; 1340f743729SConrad Meyer U32 matchIndexS = hashSmall[h]; 1350c16b537SWarner Losh const BYTE* matchLong = base + matchIndexL; 1360c16b537SWarner Losh const BYTE* match = base + matchIndexS; 137f7cd7fe5SConrad Meyer const U32 repIndex = curr + 1 - offset_1; 1380f743729SConrad Meyer const BYTE* repMatch = (dictMode == ZSTD_dictMatchState 1390f743729SConrad Meyer && repIndex < prefixLowestIndex) ? 1400f743729SConrad Meyer dictBase + (repIndex - dictIndexDelta) : 1410f743729SConrad Meyer base + repIndex; 142f7cd7fe5SConrad Meyer hashLong[h2] = hashSmall[h] = curr; /* update hash tables */ 1430c16b537SWarner Losh 1440f743729SConrad Meyer /* check dictMatchState repcode */ 1450f743729SConrad Meyer if (dictMode == ZSTD_dictMatchState 1460f743729SConrad Meyer && ((U32)((prefixLowestIndex-1) - repIndex) >= 3 /* intentional underflow */) 1470f743729SConrad Meyer && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) { 1480f743729SConrad Meyer const BYTE* repMatchEnd = repIndex < prefixLowestIndex ? dictEnd : iend; 1490f743729SConrad Meyer mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, prefixLowest) + 4; 1500f743729SConrad Meyer ip++; 1519cbefe25SConrad Meyer ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, 0, mLength-MINMATCH); 1520f743729SConrad Meyer goto _match_stored; 1530f743729SConrad Meyer } 1540f743729SConrad Meyer 1550f743729SConrad Meyer /* check noDict repcode */ 1560f743729SConrad Meyer if ( dictMode == ZSTD_noDict 1570f743729SConrad Meyer && ((offset_1 > 0) & (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1)))) { 1580c16b537SWarner Losh mLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4; 1590c16b537SWarner Losh ip++; 1609cbefe25SConrad Meyer ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, 0, mLength-MINMATCH); 1610f743729SConrad Meyer goto _match_stored; 1620f743729SConrad Meyer } 1630f743729SConrad Meyer 1640f743729SConrad Meyer if (matchIndexL > prefixLowestIndex) { 1650f743729SConrad Meyer /* check prefix long match */ 1660f743729SConrad Meyer if (MEM_read64(matchLong) == MEM_read64(ip)) { 1670c16b537SWarner Losh mLength = ZSTD_count(ip+8, matchLong+8, iend) + 8; 1680c16b537SWarner Losh offset = (U32)(ip-matchLong); 1690f743729SConrad Meyer while (((ip>anchor) & (matchLong>prefixLowest)) && (ip[-1] == matchLong[-1])) { ip--; matchLong--; mLength++; } /* catch up */ 1700f743729SConrad Meyer goto _match_found; 1710f743729SConrad Meyer } 1720f743729SConrad Meyer } else if (dictMode == ZSTD_dictMatchState) { 1730f743729SConrad Meyer /* check dictMatchState long match */ 1740f743729SConrad Meyer U32 const dictMatchIndexL = dictHashLong[dictHL]; 1750f743729SConrad Meyer const BYTE* dictMatchL = dictBase + dictMatchIndexL; 1760f743729SConrad Meyer assert(dictMatchL < dictEnd); 1770f743729SConrad Meyer 1780f743729SConrad Meyer if (dictMatchL > dictStart && MEM_read64(dictMatchL) == MEM_read64(ip)) { 1790f743729SConrad Meyer mLength = ZSTD_count_2segments(ip+8, dictMatchL+8, iend, dictEnd, prefixLowest) + 8; 180f7cd7fe5SConrad Meyer offset = (U32)(curr - dictMatchIndexL - dictIndexDelta); 1810f743729SConrad Meyer while (((ip>anchor) & (dictMatchL>dictStart)) && (ip[-1] == dictMatchL[-1])) { ip--; dictMatchL--; mLength++; } /* catch up */ 1820f743729SConrad Meyer goto _match_found; 1834d3f1eafSConrad Meyer } } 1840f743729SConrad Meyer 1850f743729SConrad Meyer if (matchIndexS > prefixLowestIndex) { 1860f743729SConrad Meyer /* check prefix short match */ 1870f743729SConrad Meyer if (MEM_read32(match) == MEM_read32(ip)) { 1880f743729SConrad Meyer goto _search_next_long; 1890f743729SConrad Meyer } 1900f743729SConrad Meyer } else if (dictMode == ZSTD_dictMatchState) { 1910f743729SConrad Meyer /* check dictMatchState short match */ 1920f743729SConrad Meyer U32 const dictMatchIndexS = dictHashSmall[dictHS]; 1930f743729SConrad Meyer match = dictBase + dictMatchIndexS; 1940f743729SConrad Meyer matchIndexS = dictMatchIndexS + dictIndexDelta; 1950f743729SConrad Meyer 1960f743729SConrad Meyer if (match > dictStart && MEM_read32(match) == MEM_read32(ip)) { 1970f743729SConrad Meyer goto _search_next_long; 1984d3f1eafSConrad Meyer } } 1990f743729SConrad Meyer 2000f743729SConrad Meyer ip += ((ip-anchor) >> kSearchStrength) + 1; 20137f1f268SConrad Meyer #if defined(__aarch64__) 20237f1f268SConrad Meyer PREFETCH_L1(ip+256); 20337f1f268SConrad Meyer #endif 2040f743729SConrad Meyer continue; 2050f743729SConrad Meyer 2060f743729SConrad Meyer _search_next_long: 2070f743729SConrad Meyer 2084d3f1eafSConrad Meyer { size_t const hl3 = ZSTD_hashPtr(ip+1, hBitsL, 8); 2090f743729SConrad Meyer size_t const dictHLNext = ZSTD_hashPtr(ip+1, dictHBitsL, 8); 2100c16b537SWarner Losh U32 const matchIndexL3 = hashLong[hl3]; 2110c16b537SWarner Losh const BYTE* matchL3 = base + matchIndexL3; 212f7cd7fe5SConrad Meyer hashLong[hl3] = curr + 1; 2130f743729SConrad Meyer 2140f743729SConrad Meyer /* check prefix long +1 match */ 2150f743729SConrad Meyer if (matchIndexL3 > prefixLowestIndex) { 2160f743729SConrad Meyer if (MEM_read64(matchL3) == MEM_read64(ip+1)) { 2170c16b537SWarner Losh mLength = ZSTD_count(ip+9, matchL3+8, iend) + 8; 2180c16b537SWarner Losh ip++; 2190c16b537SWarner Losh offset = (U32)(ip-matchL3); 2200f743729SConrad Meyer while (((ip>anchor) & (matchL3>prefixLowest)) && (ip[-1] == matchL3[-1])) { ip--; matchL3--; mLength++; } /* catch up */ 2210f743729SConrad Meyer goto _match_found; 2220f743729SConrad Meyer } 2230f743729SConrad Meyer } else if (dictMode == ZSTD_dictMatchState) { 2240f743729SConrad Meyer /* check dict long +1 match */ 2250f743729SConrad Meyer U32 const dictMatchIndexL3 = dictHashLong[dictHLNext]; 2260f743729SConrad Meyer const BYTE* dictMatchL3 = dictBase + dictMatchIndexL3; 2270f743729SConrad Meyer assert(dictMatchL3 < dictEnd); 2280f743729SConrad Meyer if (dictMatchL3 > dictStart && MEM_read64(dictMatchL3) == MEM_read64(ip+1)) { 2290f743729SConrad Meyer mLength = ZSTD_count_2segments(ip+1+8, dictMatchL3+8, iend, dictEnd, prefixLowest) + 8; 2300f743729SConrad Meyer ip++; 231f7cd7fe5SConrad Meyer offset = (U32)(curr + 1 - dictMatchIndexL3 - dictIndexDelta); 2320f743729SConrad Meyer while (((ip>anchor) & (dictMatchL3>dictStart)) && (ip[-1] == dictMatchL3[-1])) { ip--; dictMatchL3--; mLength++; } /* catch up */ 2330f743729SConrad Meyer goto _match_found; 2344d3f1eafSConrad Meyer } } } 2350f743729SConrad Meyer 2360f743729SConrad Meyer /* if no long +1 match, explore the short match we found */ 2370f743729SConrad Meyer if (dictMode == ZSTD_dictMatchState && matchIndexS < prefixLowestIndex) { 2380f743729SConrad Meyer mLength = ZSTD_count_2segments(ip+4, match+4, iend, dictEnd, prefixLowest) + 4; 239f7cd7fe5SConrad Meyer offset = (U32)(curr - matchIndexS); 2400f743729SConrad Meyer while (((ip>anchor) & (match>dictStart)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */ 2410c16b537SWarner Losh } else { 2420c16b537SWarner Losh mLength = ZSTD_count(ip+4, match+4, iend) + 4; 2430c16b537SWarner Losh offset = (U32)(ip - match); 2440f743729SConrad Meyer while (((ip>anchor) & (match>prefixLowest)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */ 2450c16b537SWarner Losh } 2460c16b537SWarner Losh 2470f743729SConrad Meyer /* fall-through */ 2480f743729SConrad Meyer 2490f743729SConrad Meyer _match_found: 2500c16b537SWarner Losh offset_2 = offset_1; 2510c16b537SWarner Losh offset_1 = offset; 2520c16b537SWarner Losh 2539cbefe25SConrad Meyer ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, offset + ZSTD_REP_MOVE, mLength-MINMATCH); 2540c16b537SWarner Losh 2550f743729SConrad Meyer _match_stored: 2560c16b537SWarner Losh /* match found */ 2570c16b537SWarner Losh ip += mLength; 2580c16b537SWarner Losh anchor = ip; 2590c16b537SWarner Losh 2600c16b537SWarner Losh if (ip <= ilimit) { 2614d3f1eafSConrad Meyer /* Complementary insertion */ 2624d3f1eafSConrad Meyer /* done after iLimit test, as candidates could be > iend-8 */ 263f7cd7fe5SConrad Meyer { U32 const indexToInsert = curr+2; 2644d3f1eafSConrad Meyer hashLong[ZSTD_hashPtr(base+indexToInsert, hBitsL, 8)] = indexToInsert; 2654d3f1eafSConrad Meyer hashLong[ZSTD_hashPtr(ip-2, hBitsL, 8)] = (U32)(ip-2-base); 2664d3f1eafSConrad Meyer hashSmall[ZSTD_hashPtr(base+indexToInsert, hBitsS, mls)] = indexToInsert; 2674d3f1eafSConrad Meyer hashSmall[ZSTD_hashPtr(ip-1, hBitsS, mls)] = (U32)(ip-1-base); 2684d3f1eafSConrad Meyer } 2690c16b537SWarner Losh 2700c16b537SWarner Losh /* check immediate repcode */ 2710f743729SConrad Meyer if (dictMode == ZSTD_dictMatchState) { 2720f743729SConrad Meyer while (ip <= ilimit) { 2730f743729SConrad Meyer U32 const current2 = (U32)(ip-base); 2740f743729SConrad Meyer U32 const repIndex2 = current2 - offset_2; 2750f743729SConrad Meyer const BYTE* repMatch2 = dictMode == ZSTD_dictMatchState 2760f743729SConrad Meyer && repIndex2 < prefixLowestIndex ? 27737f1f268SConrad Meyer dictBase + repIndex2 - dictIndexDelta : 2780f743729SConrad Meyer base + repIndex2; 2790f743729SConrad Meyer if ( ((U32)((prefixLowestIndex-1) - (U32)repIndex2) >= 3 /* intentional overflow */) 2800f743729SConrad Meyer && (MEM_read32(repMatch2) == MEM_read32(ip)) ) { 2810f743729SConrad Meyer const BYTE* const repEnd2 = repIndex2 < prefixLowestIndex ? dictEnd : iend; 2820f743729SConrad Meyer size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, prefixLowest) + 4; 2830f743729SConrad Meyer U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */ 2849cbefe25SConrad Meyer ZSTD_storeSeq(seqStore, 0, anchor, iend, 0, repLength2-MINMATCH); 2850f743729SConrad Meyer hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = current2; 2860f743729SConrad Meyer hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = current2; 2870f743729SConrad Meyer ip += repLength2; 2880f743729SConrad Meyer anchor = ip; 2890f743729SConrad Meyer continue; 2900f743729SConrad Meyer } 2910f743729SConrad Meyer break; 2924d3f1eafSConrad Meyer } } 2930f743729SConrad Meyer 2940f743729SConrad Meyer if (dictMode == ZSTD_noDict) { 2950c16b537SWarner Losh while ( (ip <= ilimit) 2960c16b537SWarner Losh && ( (offset_2>0) 2970c16b537SWarner Losh & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) { 2980c16b537SWarner Losh /* store sequence */ 2990c16b537SWarner Losh size_t const rLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4; 3000f743729SConrad Meyer U32 const tmpOff = offset_2; offset_2 = offset_1; offset_1 = tmpOff; /* swap offset_2 <=> offset_1 */ 3010c16b537SWarner Losh hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = (U32)(ip-base); 3020c16b537SWarner Losh hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = (U32)(ip-base); 3039cbefe25SConrad Meyer ZSTD_storeSeq(seqStore, 0, anchor, iend, 0, rLength-MINMATCH); 3040c16b537SWarner Losh ip += rLength; 3050c16b537SWarner Losh anchor = ip; 3060c16b537SWarner Losh continue; /* faster when present ... (?) */ 3074d3f1eafSConrad Meyer } } } 3084d3f1eafSConrad Meyer } /* while (ip < ilimit) */ 3090c16b537SWarner Losh 3100c16b537SWarner Losh /* save reps for next block */ 31119fcbaf1SConrad Meyer rep[0] = offset_1 ? offset_1 : offsetSaved; 31219fcbaf1SConrad Meyer rep[1] = offset_2 ? offset_2 : offsetSaved; 3130c16b537SWarner Losh 3140c16b537SWarner Losh /* Return the last literals size */ 3154d3f1eafSConrad Meyer return (size_t)(iend - anchor); 3160c16b537SWarner Losh } 3170c16b537SWarner Losh 3180c16b537SWarner Losh 31919fcbaf1SConrad Meyer size_t ZSTD_compressBlock_doubleFast( 32019fcbaf1SConrad Meyer ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 3210f743729SConrad Meyer void const* src, size_t srcSize) 3220c16b537SWarner Losh { 323a0483764SConrad Meyer const U32 mls = ms->cParams.minMatch; 3240c16b537SWarner Losh switch(mls) 3250c16b537SWarner Losh { 3260c16b537SWarner Losh default: /* includes case 3 */ 3270c16b537SWarner Losh case 4 : 3280f743729SConrad Meyer return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 4, ZSTD_noDict); 3290c16b537SWarner Losh case 5 : 3300f743729SConrad Meyer return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 5, ZSTD_noDict); 3310c16b537SWarner Losh case 6 : 3320f743729SConrad Meyer return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 6, ZSTD_noDict); 3330c16b537SWarner Losh case 7 : 3340f743729SConrad Meyer return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 7, ZSTD_noDict); 3350f743729SConrad Meyer } 3360f743729SConrad Meyer } 3370f743729SConrad Meyer 3380f743729SConrad Meyer 3390f743729SConrad Meyer size_t ZSTD_compressBlock_doubleFast_dictMatchState( 3400f743729SConrad Meyer ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 3410f743729SConrad Meyer void const* src, size_t srcSize) 3420f743729SConrad Meyer { 343a0483764SConrad Meyer const U32 mls = ms->cParams.minMatch; 3440f743729SConrad Meyer switch(mls) 3450f743729SConrad Meyer { 3460f743729SConrad Meyer default: /* includes case 3 */ 3470f743729SConrad Meyer case 4 : 3480f743729SConrad Meyer return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 4, ZSTD_dictMatchState); 3490f743729SConrad Meyer case 5 : 3500f743729SConrad Meyer return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 5, ZSTD_dictMatchState); 3510f743729SConrad Meyer case 6 : 3520f743729SConrad Meyer return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 6, ZSTD_dictMatchState); 3530f743729SConrad Meyer case 7 : 3540f743729SConrad Meyer return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, 7, ZSTD_dictMatchState); 3550c16b537SWarner Losh } 3560c16b537SWarner Losh } 3570c16b537SWarner Losh 3580c16b537SWarner Losh 35919fcbaf1SConrad Meyer static size_t ZSTD_compressBlock_doubleFast_extDict_generic( 36019fcbaf1SConrad Meyer ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 3610f743729SConrad Meyer void const* src, size_t srcSize, 36219fcbaf1SConrad Meyer U32 const mls /* template */) 3630c16b537SWarner Losh { 3640f743729SConrad Meyer ZSTD_compressionParameters const* cParams = &ms->cParams; 36519fcbaf1SConrad Meyer U32* const hashLong = ms->hashTable; 36619fcbaf1SConrad Meyer U32 const hBitsL = cParams->hashLog; 36719fcbaf1SConrad Meyer U32* const hashSmall = ms->chainTable; 36819fcbaf1SConrad Meyer U32 const hBitsS = cParams->chainLog; 3690c16b537SWarner Losh const BYTE* const istart = (const BYTE*)src; 3700c16b537SWarner Losh const BYTE* ip = istart; 3710c16b537SWarner Losh const BYTE* anchor = istart; 3720c16b537SWarner Losh const BYTE* const iend = istart + srcSize; 3730c16b537SWarner Losh const BYTE* const ilimit = iend - 8; 3740f743729SConrad Meyer const BYTE* const base = ms->window.base; 3754d3f1eafSConrad Meyer const U32 endIndex = (U32)((size_t)(istart - base) + srcSize); 3769cbefe25SConrad Meyer const U32 lowLimit = ZSTD_getLowestMatchIndex(ms, endIndex, cParams->windowLog); 3774d3f1eafSConrad Meyer const U32 dictStartIndex = lowLimit; 3784d3f1eafSConrad Meyer const U32 dictLimit = ms->window.dictLimit; 3794d3f1eafSConrad Meyer const U32 prefixStartIndex = (dictLimit > lowLimit) ? dictLimit : lowLimit; 3800f743729SConrad Meyer const BYTE* const prefixStart = base + prefixStartIndex; 3810f743729SConrad Meyer const BYTE* const dictBase = ms->window.dictBase; 3820f743729SConrad Meyer const BYTE* const dictStart = dictBase + dictStartIndex; 3830f743729SConrad Meyer const BYTE* const dictEnd = dictBase + prefixStartIndex; 38419fcbaf1SConrad Meyer U32 offset_1=rep[0], offset_2=rep[1]; 3850c16b537SWarner Losh 3860f743729SConrad Meyer DEBUGLOG(5, "ZSTD_compressBlock_doubleFast_extDict_generic (srcSize=%zu)", srcSize); 3870f743729SConrad Meyer 3884d3f1eafSConrad Meyer /* if extDict is invalidated due to maxDistance, switch to "regular" variant */ 3894d3f1eafSConrad Meyer if (prefixStartIndex == dictStartIndex) 3904d3f1eafSConrad Meyer return ZSTD_compressBlock_doubleFast_generic(ms, seqStore, rep, src, srcSize, mls, ZSTD_noDict); 3914d3f1eafSConrad Meyer 3920c16b537SWarner Losh /* Search Loop */ 3930c16b537SWarner Losh while (ip < ilimit) { /* < instead of <=, because (ip+1) */ 3940c16b537SWarner Losh const size_t hSmall = ZSTD_hashPtr(ip, hBitsS, mls); 3950c16b537SWarner Losh const U32 matchIndex = hashSmall[hSmall]; 3960f743729SConrad Meyer const BYTE* const matchBase = matchIndex < prefixStartIndex ? dictBase : base; 3970c16b537SWarner Losh const BYTE* match = matchBase + matchIndex; 3980c16b537SWarner Losh 3990c16b537SWarner Losh const size_t hLong = ZSTD_hashPtr(ip, hBitsL, 8); 4000c16b537SWarner Losh const U32 matchLongIndex = hashLong[hLong]; 4010f743729SConrad Meyer const BYTE* const matchLongBase = matchLongIndex < prefixStartIndex ? dictBase : base; 4020c16b537SWarner Losh const BYTE* matchLong = matchLongBase + matchLongIndex; 4030c16b537SWarner Losh 404f7cd7fe5SConrad Meyer const U32 curr = (U32)(ip-base); 405f7cd7fe5SConrad Meyer const U32 repIndex = curr + 1 - offset_1; /* offset_1 expected <= curr +1 */ 4060f743729SConrad Meyer const BYTE* const repBase = repIndex < prefixStartIndex ? dictBase : base; 4070f743729SConrad Meyer const BYTE* const repMatch = repBase + repIndex; 4080c16b537SWarner Losh size_t mLength; 409f7cd7fe5SConrad Meyer hashSmall[hSmall] = hashLong[hLong] = curr; /* update hash table */ 4100c16b537SWarner Losh 4110f743729SConrad Meyer if ((((U32)((prefixStartIndex-1) - repIndex) >= 3) /* intentional underflow : ensure repIndex doesn't overlap dict + prefix */ 4120f743729SConrad Meyer & (repIndex > dictStartIndex)) 4130c16b537SWarner Losh && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) { 4140f743729SConrad Meyer const BYTE* repMatchEnd = repIndex < prefixStartIndex ? dictEnd : iend; 4150f743729SConrad Meyer mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, prefixStart) + 4; 4160c16b537SWarner Losh ip++; 4179cbefe25SConrad Meyer ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, 0, mLength-MINMATCH); 4180c16b537SWarner Losh } else { 4190f743729SConrad Meyer if ((matchLongIndex > dictStartIndex) && (MEM_read64(matchLong) == MEM_read64(ip))) { 4200f743729SConrad Meyer const BYTE* const matchEnd = matchLongIndex < prefixStartIndex ? dictEnd : iend; 4210f743729SConrad Meyer const BYTE* const lowMatchPtr = matchLongIndex < prefixStartIndex ? dictStart : prefixStart; 4220c16b537SWarner Losh U32 offset; 4230f743729SConrad Meyer mLength = ZSTD_count_2segments(ip+8, matchLong+8, iend, matchEnd, prefixStart) + 8; 424f7cd7fe5SConrad Meyer offset = curr - matchLongIndex; 4250c16b537SWarner Losh while (((ip>anchor) & (matchLong>lowMatchPtr)) && (ip[-1] == matchLong[-1])) { ip--; matchLong--; mLength++; } /* catch up */ 4260c16b537SWarner Losh offset_2 = offset_1; 4270c16b537SWarner Losh offset_1 = offset; 4289cbefe25SConrad Meyer ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, offset + ZSTD_REP_MOVE, mLength-MINMATCH); 4290c16b537SWarner Losh 4300f743729SConrad Meyer } else if ((matchIndex > dictStartIndex) && (MEM_read32(match) == MEM_read32(ip))) { 4310c16b537SWarner Losh size_t const h3 = ZSTD_hashPtr(ip+1, hBitsL, 8); 4320c16b537SWarner Losh U32 const matchIndex3 = hashLong[h3]; 4330f743729SConrad Meyer const BYTE* const match3Base = matchIndex3 < prefixStartIndex ? dictBase : base; 4340c16b537SWarner Losh const BYTE* match3 = match3Base + matchIndex3; 4350c16b537SWarner Losh U32 offset; 436f7cd7fe5SConrad Meyer hashLong[h3] = curr + 1; 4370f743729SConrad Meyer if ( (matchIndex3 > dictStartIndex) && (MEM_read64(match3) == MEM_read64(ip+1)) ) { 4380f743729SConrad Meyer const BYTE* const matchEnd = matchIndex3 < prefixStartIndex ? dictEnd : iend; 4390f743729SConrad Meyer const BYTE* const lowMatchPtr = matchIndex3 < prefixStartIndex ? dictStart : prefixStart; 4400f743729SConrad Meyer mLength = ZSTD_count_2segments(ip+9, match3+8, iend, matchEnd, prefixStart) + 8; 4410c16b537SWarner Losh ip++; 442f7cd7fe5SConrad Meyer offset = curr+1 - matchIndex3; 4430c16b537SWarner Losh while (((ip>anchor) & (match3>lowMatchPtr)) && (ip[-1] == match3[-1])) { ip--; match3--; mLength++; } /* catch up */ 4440c16b537SWarner Losh } else { 4450f743729SConrad Meyer const BYTE* const matchEnd = matchIndex < prefixStartIndex ? dictEnd : iend; 4460f743729SConrad Meyer const BYTE* const lowMatchPtr = matchIndex < prefixStartIndex ? dictStart : prefixStart; 4470f743729SConrad Meyer mLength = ZSTD_count_2segments(ip+4, match+4, iend, matchEnd, prefixStart) + 4; 448f7cd7fe5SConrad Meyer offset = curr - matchIndex; 4490c16b537SWarner Losh while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */ 4500c16b537SWarner Losh } 4510c16b537SWarner Losh offset_2 = offset_1; 4520c16b537SWarner Losh offset_1 = offset; 4539cbefe25SConrad Meyer ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, offset + ZSTD_REP_MOVE, mLength-MINMATCH); 4540c16b537SWarner Losh 4550c16b537SWarner Losh } else { 45619fcbaf1SConrad Meyer ip += ((ip-anchor) >> kSearchStrength) + 1; 4570c16b537SWarner Losh continue; 4580c16b537SWarner Losh } } 4590c16b537SWarner Losh 4604d3f1eafSConrad Meyer /* move to next sequence start */ 4610c16b537SWarner Losh ip += mLength; 4620c16b537SWarner Losh anchor = ip; 4630c16b537SWarner Losh 4640c16b537SWarner Losh if (ip <= ilimit) { 4654d3f1eafSConrad Meyer /* Complementary insertion */ 4664d3f1eafSConrad Meyer /* done after iLimit test, as candidates could be > iend-8 */ 467f7cd7fe5SConrad Meyer { U32 const indexToInsert = curr+2; 4684d3f1eafSConrad Meyer hashLong[ZSTD_hashPtr(base+indexToInsert, hBitsL, 8)] = indexToInsert; 4690c16b537SWarner Losh hashLong[ZSTD_hashPtr(ip-2, hBitsL, 8)] = (U32)(ip-2-base); 4704d3f1eafSConrad Meyer hashSmall[ZSTD_hashPtr(base+indexToInsert, hBitsS, mls)] = indexToInsert; 4714d3f1eafSConrad Meyer hashSmall[ZSTD_hashPtr(ip-1, hBitsS, mls)] = (U32)(ip-1-base); 4724d3f1eafSConrad Meyer } 4734d3f1eafSConrad Meyer 4740c16b537SWarner Losh /* check immediate repcode */ 4750c16b537SWarner Losh while (ip <= ilimit) { 4760c16b537SWarner Losh U32 const current2 = (U32)(ip-base); 4770c16b537SWarner Losh U32 const repIndex2 = current2 - offset_2; 4780f743729SConrad Meyer const BYTE* repMatch2 = repIndex2 < prefixStartIndex ? dictBase + repIndex2 : base + repIndex2; 4790f743729SConrad Meyer if ( (((U32)((prefixStartIndex-1) - repIndex2) >= 3) /* intentional overflow : ensure repIndex2 doesn't overlap dict + prefix */ 4800f743729SConrad Meyer & (repIndex2 > dictStartIndex)) 4810c16b537SWarner Losh && (MEM_read32(repMatch2) == MEM_read32(ip)) ) { 4820f743729SConrad Meyer const BYTE* const repEnd2 = repIndex2 < prefixStartIndex ? dictEnd : iend; 4830f743729SConrad Meyer size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, prefixStart) + 4; 4840f743729SConrad Meyer U32 const tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */ 4859cbefe25SConrad Meyer ZSTD_storeSeq(seqStore, 0, anchor, iend, 0, repLength2-MINMATCH); 4860c16b537SWarner Losh hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = current2; 4870c16b537SWarner Losh hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = current2; 4880c16b537SWarner Losh ip += repLength2; 4890c16b537SWarner Losh anchor = ip; 4900c16b537SWarner Losh continue; 4910c16b537SWarner Losh } 4920c16b537SWarner Losh break; 4930c16b537SWarner Losh } } } 4940c16b537SWarner Losh 4950c16b537SWarner Losh /* save reps for next block */ 49619fcbaf1SConrad Meyer rep[0] = offset_1; 49719fcbaf1SConrad Meyer rep[1] = offset_2; 4980c16b537SWarner Losh 4990c16b537SWarner Losh /* Return the last literals size */ 5004d3f1eafSConrad Meyer return (size_t)(iend - anchor); 5010c16b537SWarner Losh } 5020c16b537SWarner Losh 5030c16b537SWarner Losh 50419fcbaf1SConrad Meyer size_t ZSTD_compressBlock_doubleFast_extDict( 50519fcbaf1SConrad Meyer ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM], 5060f743729SConrad Meyer void const* src, size_t srcSize) 5070c16b537SWarner Losh { 508a0483764SConrad Meyer U32 const mls = ms->cParams.minMatch; 5090c16b537SWarner Losh switch(mls) 5100c16b537SWarner Losh { 5110c16b537SWarner Losh default: /* includes case 3 */ 5120c16b537SWarner Losh case 4 : 5130f743729SConrad Meyer return ZSTD_compressBlock_doubleFast_extDict_generic(ms, seqStore, rep, src, srcSize, 4); 5140c16b537SWarner Losh case 5 : 5150f743729SConrad Meyer return ZSTD_compressBlock_doubleFast_extDict_generic(ms, seqStore, rep, src, srcSize, 5); 5160c16b537SWarner Losh case 6 : 5170f743729SConrad Meyer return ZSTD_compressBlock_doubleFast_extDict_generic(ms, seqStore, rep, src, srcSize, 6); 5180c16b537SWarner Losh case 7 : 5190f743729SConrad Meyer return ZSTD_compressBlock_doubleFast_extDict_generic(ms, seqStore, rep, src, srcSize, 7); 5200c16b537SWarner Losh } 5210c16b537SWarner Losh } 522