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