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_double_fast.h" 13 14 15 void ZSTD_fillDoubleHashTable(ZSTD_CCtx* cctx, const void* end, const U32 mls) 16 { 17 U32* const hashLarge = cctx->hashTable; 18 U32 const hBitsL = cctx->appliedParams.cParams.hashLog; 19 U32* const hashSmall = cctx->chainTable; 20 U32 const hBitsS = cctx->appliedParams.cParams.chainLog; 21 const BYTE* const base = cctx->base; 22 const BYTE* ip = base + cctx->nextToUpdate; 23 const BYTE* const iend = ((const BYTE*)end) - HASH_READ_SIZE; 24 const size_t fastHashFillStep = 3; 25 26 while(ip <= iend) { 27 hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = (U32)(ip - base); 28 hashLarge[ZSTD_hashPtr(ip, hBitsL, 8)] = (U32)(ip - base); 29 ip += fastHashFillStep; 30 } 31 } 32 33 34 FORCE_INLINE_TEMPLATE 35 size_t ZSTD_compressBlock_doubleFast_generic(ZSTD_CCtx* cctx, 36 const void* src, size_t srcSize, 37 const U32 mls) 38 { 39 U32* const hashLong = cctx->hashTable; 40 const U32 hBitsL = cctx->appliedParams.cParams.hashLog; 41 U32* const hashSmall = cctx->chainTable; 42 const U32 hBitsS = cctx->appliedParams.cParams.chainLog; 43 seqStore_t* seqStorePtr = &(cctx->seqStore); 44 const BYTE* const base = cctx->base; 45 const BYTE* const istart = (const BYTE*)src; 46 const BYTE* ip = istart; 47 const BYTE* anchor = istart; 48 const U32 lowestIndex = cctx->dictLimit; 49 const BYTE* const lowest = base + lowestIndex; 50 const BYTE* const iend = istart + srcSize; 51 const BYTE* const ilimit = iend - HASH_READ_SIZE; 52 U32 offset_1=seqStorePtr->rep[0], offset_2=seqStorePtr->rep[1]; 53 U32 offsetSaved = 0; 54 55 /* init */ 56 ip += (ip==lowest); 57 { U32 const maxRep = (U32)(ip-lowest); 58 if (offset_2 > maxRep) offsetSaved = offset_2, offset_2 = 0; 59 if (offset_1 > maxRep) offsetSaved = offset_1, offset_1 = 0; 60 } 61 62 /* Main Search Loop */ 63 while (ip < ilimit) { /* < instead of <=, because repcode check at (ip+1) */ 64 size_t mLength; 65 size_t const h2 = ZSTD_hashPtr(ip, hBitsL, 8); 66 size_t const h = ZSTD_hashPtr(ip, hBitsS, mls); 67 U32 const current = (U32)(ip-base); 68 U32 const matchIndexL = hashLong[h2]; 69 U32 const matchIndexS = hashSmall[h]; 70 const BYTE* matchLong = base + matchIndexL; 71 const BYTE* match = base + matchIndexS; 72 hashLong[h2] = hashSmall[h] = current; /* update hash tables */ 73 74 assert(offset_1 <= current); /* supposed guaranteed by construction */ 75 if ((offset_1 > 0) & (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1))) { 76 /* favor repcode */ 77 mLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4; 78 ip++; 79 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH); 80 } else { 81 U32 offset; 82 if ( (matchIndexL > lowestIndex) && (MEM_read64(matchLong) == MEM_read64(ip)) ) { 83 mLength = ZSTD_count(ip+8, matchLong+8, iend) + 8; 84 offset = (U32)(ip-matchLong); 85 while (((ip>anchor) & (matchLong>lowest)) && (ip[-1] == matchLong[-1])) { ip--; matchLong--; mLength++; } /* catch up */ 86 } else if ( (matchIndexS > lowestIndex) && (MEM_read32(match) == MEM_read32(ip)) ) { 87 size_t const hl3 = ZSTD_hashPtr(ip+1, hBitsL, 8); 88 U32 const matchIndexL3 = hashLong[hl3]; 89 const BYTE* matchL3 = base + matchIndexL3; 90 hashLong[hl3] = current + 1; 91 if ( (matchIndexL3 > lowestIndex) && (MEM_read64(matchL3) == MEM_read64(ip+1)) ) { 92 mLength = ZSTD_count(ip+9, matchL3+8, iend) + 8; 93 ip++; 94 offset = (U32)(ip-matchL3); 95 while (((ip>anchor) & (matchL3>lowest)) && (ip[-1] == matchL3[-1])) { ip--; matchL3--; mLength++; } /* catch up */ 96 } else { 97 mLength = ZSTD_count(ip+4, match+4, iend) + 4; 98 offset = (U32)(ip-match); 99 while (((ip>anchor) & (match>lowest)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */ 100 } 101 } else { 102 ip += ((ip-anchor) >> g_searchStrength) + 1; 103 continue; 104 } 105 106 offset_2 = offset_1; 107 offset_1 = offset; 108 109 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH); 110 } 111 112 /* match found */ 113 ip += mLength; 114 anchor = ip; 115 116 if (ip <= ilimit) { 117 /* Fill Table */ 118 hashLong[ZSTD_hashPtr(base+current+2, hBitsL, 8)] = 119 hashSmall[ZSTD_hashPtr(base+current+2, hBitsS, mls)] = current+2; /* here because current+2 could be > iend-8 */ 120 hashLong[ZSTD_hashPtr(ip-2, hBitsL, 8)] = 121 hashSmall[ZSTD_hashPtr(ip-2, hBitsS, mls)] = (U32)(ip-2-base); 122 123 /* check immediate repcode */ 124 while ( (ip <= ilimit) 125 && ( (offset_2>0) 126 & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) { 127 /* store sequence */ 128 size_t const rLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4; 129 { U32 const tmpOff = offset_2; offset_2 = offset_1; offset_1 = tmpOff; } /* swap offset_2 <=> offset_1 */ 130 hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = (U32)(ip-base); 131 hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = (U32)(ip-base); 132 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, rLength-MINMATCH); 133 ip += rLength; 134 anchor = ip; 135 continue; /* faster when present ... (?) */ 136 } } } 137 138 /* save reps for next block */ 139 seqStorePtr->repToConfirm[0] = offset_1 ? offset_1 : offsetSaved; 140 seqStorePtr->repToConfirm[1] = offset_2 ? offset_2 : offsetSaved; 141 142 /* Return the last literals size */ 143 return iend - anchor; 144 } 145 146 147 size_t ZSTD_compressBlock_doubleFast(ZSTD_CCtx* ctx, const void* src, size_t srcSize) 148 { 149 const U32 mls = ctx->appliedParams.cParams.searchLength; 150 switch(mls) 151 { 152 default: /* includes case 3 */ 153 case 4 : 154 return ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 4); 155 case 5 : 156 return ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 5); 157 case 6 : 158 return ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 6); 159 case 7 : 160 return ZSTD_compressBlock_doubleFast_generic(ctx, src, srcSize, 7); 161 } 162 } 163 164 165 static size_t ZSTD_compressBlock_doubleFast_extDict_generic(ZSTD_CCtx* ctx, 166 const void* src, size_t srcSize, 167 const U32 mls) 168 { 169 U32* const hashLong = ctx->hashTable; 170 U32 const hBitsL = ctx->appliedParams.cParams.hashLog; 171 U32* const hashSmall = ctx->chainTable; 172 U32 const hBitsS = ctx->appliedParams.cParams.chainLog; 173 seqStore_t* seqStorePtr = &(ctx->seqStore); 174 const BYTE* const base = ctx->base; 175 const BYTE* const dictBase = ctx->dictBase; 176 const BYTE* const istart = (const BYTE*)src; 177 const BYTE* ip = istart; 178 const BYTE* anchor = istart; 179 const U32 lowestIndex = ctx->lowLimit; 180 const BYTE* const dictStart = dictBase + lowestIndex; 181 const U32 dictLimit = ctx->dictLimit; 182 const BYTE* const lowPrefixPtr = base + dictLimit; 183 const BYTE* const dictEnd = dictBase + dictLimit; 184 const BYTE* const iend = istart + srcSize; 185 const BYTE* const ilimit = iend - 8; 186 U32 offset_1=seqStorePtr->rep[0], offset_2=seqStorePtr->rep[1]; 187 188 /* Search Loop */ 189 while (ip < ilimit) { /* < instead of <=, because (ip+1) */ 190 const size_t hSmall = ZSTD_hashPtr(ip, hBitsS, mls); 191 const U32 matchIndex = hashSmall[hSmall]; 192 const BYTE* matchBase = matchIndex < dictLimit ? dictBase : base; 193 const BYTE* match = matchBase + matchIndex; 194 195 const size_t hLong = ZSTD_hashPtr(ip, hBitsL, 8); 196 const U32 matchLongIndex = hashLong[hLong]; 197 const BYTE* matchLongBase = matchLongIndex < dictLimit ? dictBase : base; 198 const BYTE* matchLong = matchLongBase + matchLongIndex; 199 200 const U32 current = (U32)(ip-base); 201 const U32 repIndex = current + 1 - offset_1; /* offset_1 expected <= current +1 */ 202 const BYTE* repBase = repIndex < dictLimit ? dictBase : base; 203 const BYTE* repMatch = repBase + repIndex; 204 size_t mLength; 205 hashSmall[hSmall] = hashLong[hLong] = current; /* update hash table */ 206 207 if ( (((U32)((dictLimit-1) - repIndex) >= 3) /* intentional underflow */ & (repIndex > lowestIndex)) 208 && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) { 209 const BYTE* repMatchEnd = repIndex < dictLimit ? dictEnd : iend; 210 mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, lowPrefixPtr) + 4; 211 ip++; 212 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH); 213 } else { 214 if ((matchLongIndex > lowestIndex) && (MEM_read64(matchLong) == MEM_read64(ip))) { 215 const BYTE* matchEnd = matchLongIndex < dictLimit ? dictEnd : iend; 216 const BYTE* lowMatchPtr = matchLongIndex < dictLimit ? dictStart : lowPrefixPtr; 217 U32 offset; 218 mLength = ZSTD_count_2segments(ip+8, matchLong+8, iend, matchEnd, lowPrefixPtr) + 8; 219 offset = current - matchLongIndex; 220 while (((ip>anchor) & (matchLong>lowMatchPtr)) && (ip[-1] == matchLong[-1])) { ip--; matchLong--; mLength++; } /* catch up */ 221 offset_2 = offset_1; 222 offset_1 = offset; 223 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH); 224 225 } else if ((matchIndex > lowestIndex) && (MEM_read32(match) == MEM_read32(ip))) { 226 size_t const h3 = ZSTD_hashPtr(ip+1, hBitsL, 8); 227 U32 const matchIndex3 = hashLong[h3]; 228 const BYTE* const match3Base = matchIndex3 < dictLimit ? dictBase : base; 229 const BYTE* match3 = match3Base + matchIndex3; 230 U32 offset; 231 hashLong[h3] = current + 1; 232 if ( (matchIndex3 > lowestIndex) && (MEM_read64(match3) == MEM_read64(ip+1)) ) { 233 const BYTE* matchEnd = matchIndex3 < dictLimit ? dictEnd : iend; 234 const BYTE* lowMatchPtr = matchIndex3 < dictLimit ? dictStart : lowPrefixPtr; 235 mLength = ZSTD_count_2segments(ip+9, match3+8, iend, matchEnd, lowPrefixPtr) + 8; 236 ip++; 237 offset = current+1 - matchIndex3; 238 while (((ip>anchor) & (match3>lowMatchPtr)) && (ip[-1] == match3[-1])) { ip--; match3--; mLength++; } /* catch up */ 239 } else { 240 const BYTE* matchEnd = matchIndex < dictLimit ? dictEnd : iend; 241 const BYTE* lowMatchPtr = matchIndex < dictLimit ? dictStart : lowPrefixPtr; 242 mLength = ZSTD_count_2segments(ip+4, match+4, iend, matchEnd, lowPrefixPtr) + 4; 243 offset = current - matchIndex; 244 while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */ 245 } 246 offset_2 = offset_1; 247 offset_1 = offset; 248 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH); 249 250 } else { 251 ip += ((ip-anchor) >> g_searchStrength) + 1; 252 continue; 253 } } 254 255 /* found a match : store it */ 256 ip += mLength; 257 anchor = ip; 258 259 if (ip <= ilimit) { 260 /* Fill Table */ 261 hashSmall[ZSTD_hashPtr(base+current+2, hBitsS, mls)] = current+2; 262 hashLong[ZSTD_hashPtr(base+current+2, hBitsL, 8)] = current+2; 263 hashSmall[ZSTD_hashPtr(ip-2, hBitsS, mls)] = (U32)(ip-2-base); 264 hashLong[ZSTD_hashPtr(ip-2, hBitsL, 8)] = (U32)(ip-2-base); 265 /* check immediate repcode */ 266 while (ip <= ilimit) { 267 U32 const current2 = (U32)(ip-base); 268 U32 const repIndex2 = current2 - offset_2; 269 const BYTE* repMatch2 = repIndex2 < dictLimit ? dictBase + repIndex2 : base + repIndex2; 270 if ( (((U32)((dictLimit-1) - repIndex2) >= 3) & (repIndex2 > lowestIndex)) /* intentional overflow */ 271 && (MEM_read32(repMatch2) == MEM_read32(ip)) ) { 272 const BYTE* const repEnd2 = repIndex2 < dictLimit ? dictEnd : iend; 273 size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, lowPrefixPtr) + 4; 274 U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */ 275 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, repLength2-MINMATCH); 276 hashSmall[ZSTD_hashPtr(ip, hBitsS, mls)] = current2; 277 hashLong[ZSTD_hashPtr(ip, hBitsL, 8)] = current2; 278 ip += repLength2; 279 anchor = ip; 280 continue; 281 } 282 break; 283 } } } 284 285 /* save reps for next block */ 286 seqStorePtr->repToConfirm[0] = offset_1; seqStorePtr->repToConfirm[1] = offset_2; 287 288 /* Return the last literals size */ 289 return iend - anchor; 290 } 291 292 293 size_t ZSTD_compressBlock_doubleFast_extDict(ZSTD_CCtx* ctx, 294 const void* src, size_t srcSize) 295 { 296 U32 const mls = ctx->appliedParams.cParams.searchLength; 297 switch(mls) 298 { 299 default: /* includes case 3 */ 300 case 4 : 301 return ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 4); 302 case 5 : 303 return ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 5); 304 case 6 : 305 return ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 6); 306 case 7 : 307 return ZSTD_compressBlock_doubleFast_extDict_generic(ctx, src, srcSize, 7); 308 } 309 } 310