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_fast.h" 12 13 14 void ZSTD_fillHashTable (ZSTD_CCtx* zc, const void* end, const U32 mls) 15 { 16 U32* const hashTable = zc->hashTable; 17 U32 const hBits = zc->appliedParams.cParams.hashLog; 18 const BYTE* const base = zc->base; 19 const BYTE* ip = base + zc->nextToUpdate; 20 const BYTE* const iend = ((const BYTE*)end) - HASH_READ_SIZE; 21 const size_t fastHashFillStep = 3; 22 23 while(ip <= iend) { 24 hashTable[ZSTD_hashPtr(ip, hBits, mls)] = (U32)(ip - base); 25 ip += fastHashFillStep; 26 } 27 } 28 29 30 FORCE_INLINE_TEMPLATE 31 size_t ZSTD_compressBlock_fast_generic(ZSTD_CCtx* cctx, 32 const void* src, size_t srcSize, 33 const U32 mls) 34 { 35 U32* const hashTable = cctx->hashTable; 36 U32 const hBits = cctx->appliedParams.cParams.hashLog; 37 seqStore_t* seqStorePtr = &(cctx->seqStore); 38 const BYTE* const base = cctx->base; 39 const BYTE* const istart = (const BYTE*)src; 40 const BYTE* ip = istart; 41 const BYTE* anchor = istart; 42 const U32 lowestIndex = cctx->dictLimit; 43 const BYTE* const lowest = base + lowestIndex; 44 const BYTE* const iend = istart + srcSize; 45 const BYTE* const ilimit = iend - HASH_READ_SIZE; 46 U32 offset_1=seqStorePtr->rep[0], offset_2=seqStorePtr->rep[1]; 47 U32 offsetSaved = 0; 48 49 /* init */ 50 ip += (ip==lowest); 51 { U32 const maxRep = (U32)(ip-lowest); 52 if (offset_2 > maxRep) offsetSaved = offset_2, offset_2 = 0; 53 if (offset_1 > maxRep) offsetSaved = offset_1, offset_1 = 0; 54 } 55 56 /* Main Search Loop */ 57 while (ip < ilimit) { /* < instead of <=, because repcode check at (ip+1) */ 58 size_t mLength; 59 size_t const h = ZSTD_hashPtr(ip, hBits, mls); 60 U32 const current = (U32)(ip-base); 61 U32 const matchIndex = hashTable[h]; 62 const BYTE* match = base + matchIndex; 63 hashTable[h] = current; /* update hash table */ 64 65 if ((offset_1 > 0) & (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1))) { 66 mLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4; 67 ip++; 68 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH); 69 } else { 70 U32 offset; 71 if ( (matchIndex <= lowestIndex) || (MEM_read32(match) != MEM_read32(ip)) ) { 72 ip += ((ip-anchor) >> g_searchStrength) + 1; 73 continue; 74 } 75 mLength = ZSTD_count(ip+4, match+4, iend) + 4; 76 offset = (U32)(ip-match); 77 while (((ip>anchor) & (match>lowest)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */ 78 offset_2 = offset_1; 79 offset_1 = offset; 80 81 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH); 82 } 83 84 /* match found */ 85 ip += mLength; 86 anchor = ip; 87 88 if (ip <= ilimit) { 89 /* Fill Table */ 90 hashTable[ZSTD_hashPtr(base+current+2, hBits, mls)] = current+2; /* here because current+2 could be > iend-8 */ 91 hashTable[ZSTD_hashPtr(ip-2, hBits, mls)] = (U32)(ip-2-base); 92 /* check immediate repcode */ 93 while ( (ip <= ilimit) 94 && ( (offset_2>0) 95 & (MEM_read32(ip) == MEM_read32(ip - offset_2)) )) { 96 /* store sequence */ 97 size_t const rLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4; 98 { U32 const tmpOff = offset_2; offset_2 = offset_1; offset_1 = tmpOff; } /* swap offset_2 <=> offset_1 */ 99 hashTable[ZSTD_hashPtr(ip, hBits, mls)] = (U32)(ip-base); 100 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, rLength-MINMATCH); 101 ip += rLength; 102 anchor = ip; 103 continue; /* faster when present ... (?) */ 104 } } } 105 106 /* save reps for next block */ 107 seqStorePtr->repToConfirm[0] = offset_1 ? offset_1 : offsetSaved; 108 seqStorePtr->repToConfirm[1] = offset_2 ? offset_2 : offsetSaved; 109 110 /* Return the last literals size */ 111 return iend - anchor; 112 } 113 114 115 size_t ZSTD_compressBlock_fast(ZSTD_CCtx* ctx, 116 const void* src, size_t srcSize) 117 { 118 const U32 mls = ctx->appliedParams.cParams.searchLength; 119 switch(mls) 120 { 121 default: /* includes case 3 */ 122 case 4 : 123 return ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 4); 124 case 5 : 125 return ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 5); 126 case 6 : 127 return ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 6); 128 case 7 : 129 return ZSTD_compressBlock_fast_generic(ctx, src, srcSize, 7); 130 } 131 } 132 133 134 static size_t ZSTD_compressBlock_fast_extDict_generic(ZSTD_CCtx* ctx, 135 const void* src, size_t srcSize, 136 const U32 mls) 137 { 138 U32* hashTable = ctx->hashTable; 139 const U32 hBits = ctx->appliedParams.cParams.hashLog; 140 seqStore_t* seqStorePtr = &(ctx->seqStore); 141 const BYTE* const base = ctx->base; 142 const BYTE* const dictBase = ctx->dictBase; 143 const BYTE* const istart = (const BYTE*)src; 144 const BYTE* ip = istart; 145 const BYTE* anchor = istart; 146 const U32 lowestIndex = ctx->lowLimit; 147 const BYTE* const dictStart = dictBase + lowestIndex; 148 const U32 dictLimit = ctx->dictLimit; 149 const BYTE* const lowPrefixPtr = base + dictLimit; 150 const BYTE* const dictEnd = dictBase + dictLimit; 151 const BYTE* const iend = istart + srcSize; 152 const BYTE* const ilimit = iend - 8; 153 U32 offset_1=seqStorePtr->rep[0], offset_2=seqStorePtr->rep[1]; 154 155 /* Search Loop */ 156 while (ip < ilimit) { /* < instead of <=, because (ip+1) */ 157 const size_t h = ZSTD_hashPtr(ip, hBits, mls); 158 const U32 matchIndex = hashTable[h]; 159 const BYTE* matchBase = matchIndex < dictLimit ? dictBase : base; 160 const BYTE* match = matchBase + matchIndex; 161 const U32 current = (U32)(ip-base); 162 const U32 repIndex = current + 1 - offset_1; /* offset_1 expected <= current +1 */ 163 const BYTE* repBase = repIndex < dictLimit ? dictBase : base; 164 const BYTE* repMatch = repBase + repIndex; 165 size_t mLength; 166 hashTable[h] = current; /* update hash table */ 167 168 if ( (((U32)((dictLimit-1) - repIndex) >= 3) /* intentional underflow */ & (repIndex > lowestIndex)) 169 && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) { 170 const BYTE* repMatchEnd = repIndex < dictLimit ? dictEnd : iend; 171 mLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, lowPrefixPtr) + 4; 172 ip++; 173 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, 0, mLength-MINMATCH); 174 } else { 175 if ( (matchIndex < lowestIndex) || 176 (MEM_read32(match) != MEM_read32(ip)) ) { 177 ip += ((ip-anchor) >> g_searchStrength) + 1; 178 continue; 179 } 180 { const BYTE* matchEnd = matchIndex < dictLimit ? dictEnd : iend; 181 const BYTE* lowMatchPtr = matchIndex < dictLimit ? dictStart : lowPrefixPtr; 182 U32 offset; 183 mLength = ZSTD_count_2segments(ip+4, match+4, iend, matchEnd, lowPrefixPtr) + 4; 184 while (((ip>anchor) & (match>lowMatchPtr)) && (ip[-1] == match[-1])) { ip--; match--; mLength++; } /* catch up */ 185 offset = current - matchIndex; 186 offset_2 = offset_1; 187 offset_1 = offset; 188 ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset + ZSTD_REP_MOVE, mLength-MINMATCH); 189 } } 190 191 /* found a match : store it */ 192 ip += mLength; 193 anchor = ip; 194 195 if (ip <= ilimit) { 196 /* Fill Table */ 197 hashTable[ZSTD_hashPtr(base+current+2, hBits, mls)] = current+2; 198 hashTable[ZSTD_hashPtr(ip-2, hBits, mls)] = (U32)(ip-2-base); 199 /* check immediate repcode */ 200 while (ip <= ilimit) { 201 U32 const current2 = (U32)(ip-base); 202 U32 const repIndex2 = current2 - offset_2; 203 const BYTE* repMatch2 = repIndex2 < dictLimit ? dictBase + repIndex2 : base + repIndex2; 204 if ( (((U32)((dictLimit-1) - repIndex2) >= 3) & (repIndex2 > lowestIndex)) /* intentional overflow */ 205 && (MEM_read32(repMatch2) == MEM_read32(ip)) ) { 206 const BYTE* const repEnd2 = repIndex2 < dictLimit ? dictEnd : iend; 207 size_t const repLength2 = ZSTD_count_2segments(ip+4, repMatch2+4, iend, repEnd2, lowPrefixPtr) + 4; 208 U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */ 209 ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, repLength2-MINMATCH); 210 hashTable[ZSTD_hashPtr(ip, hBits, mls)] = current2; 211 ip += repLength2; 212 anchor = ip; 213 continue; 214 } 215 break; 216 } } } 217 218 /* save reps for next block */ 219 seqStorePtr->repToConfirm[0] = offset_1; seqStorePtr->repToConfirm[1] = offset_2; 220 221 /* Return the last literals size */ 222 return iend - anchor; 223 } 224 225 226 size_t ZSTD_compressBlock_fast_extDict(ZSTD_CCtx* ctx, 227 const void* src, size_t srcSize) 228 { 229 U32 const mls = ctx->appliedParams.cParams.searchLength; 230 switch(mls) 231 { 232 default: /* includes case 3 */ 233 case 4 : 234 return ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 4); 235 case 5 : 236 return ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 5); 237 case 6 : 238 return ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 6); 239 case 7 : 240 return ZSTD_compressBlock_fast_extDict_generic(ctx, src, srcSize, 7); 241 } 242 } 243