1 // SPDX-License-Identifier: GPL-2.0+ OR BSD-3-Clause
6  * This source code is licensed under both the BSD-style license (found in the
9  * You may select, at your option, one of the above-listed licenses.
22 #define THRESHOLD_BASE (THRESHOLD_PENALTY_RATE - 2)
28 #define HASHMASK (HASHTABLESIZE - 1)
31 /* for hashLog > 8, hash 2 bytes.
32  * for hashLog == 8, just take the byte, no hashing.
33  * The speed of this method relies on compile-time constant propagation */
36     assert(hashLog >= 8);  in hash2()
37     if (hashLog == 8) return (U32)((const BYTE*)p)[0];  in hash2()
39     return (U32)(MEM_read16(p)) * KNUTH >> (32 - hashLog);  in hash2()
61     size_t limit = srcSize - HASHLENGTH + 1;  in addEvents_generic()
65         fp->events[hash2(p+n, hashLog)]++;  in addEvents_generic()
67     fp->nbEvents += limit/samplingRate;  in addEvents_generic()
74     fp->nbEvents = 0;  in recordFingerprint_generic()
91 ZSTD_GEN_RECORD_FINGERPRINT(43, 8)
94 static U64 abs64(S64 s64) { return (U64)((s64 < 0) ? -s64 : s64); }  in abs64()
103 …        abs64((S64)fp1->events[n] * (S64)fp2->nbEvents - (S64)fp2->events[n] * (S64)fp1->nbEvents);  in fpDistance()
116     assert(ref->nbEvents > 0);  in compareFingerprints()
117     assert(newfp->nbEvents > 0);  in compareFingerprints()
118     {   U64 p50 = (U64)ref->nbEvents * (U64)newfp->nbEvents;  in compareFingerprints()
129         acc->events[n] += newfp->events[n];  in mergeEvents()
131     acc->nbEvents += newfp->nbEvents;  in mergeEvents()
138         fpstats->pastEvents.events[n] = fpstats->newEvents.events[n];  in flushEvents()
140     fpstats->pastEvents.nbEvents = fpstats->newEvents.nbEvents;  in flushEvents()
141     ZSTD_memset(&fpstats->newEvents, 0, sizeof(fpstats->newEvents));  in flushEvents()
148         assert(acc->events[n] >= slice->events[n]);  in removeEvents()
149         acc->events[n] -= slice->events[n];  in removeEvents()
151     acc->nbEvents -= slice->nbEvents;  in removeEvents()
154 #define CHUNKSIZE (8 << 10)
156                         int level,  in ZSTD_splitBlock_byChunks()  argument
162     static const unsigned hashParams[] = { 8, 9, 10, 10 };  in ZSTD_splitBlock_byChunks()
163     const RecordEvents_f record_f = (assert(0<=level && level<=3), records_fs[level]);  in ZSTD_splitBlock_byChunks()
175     record_f(&fpstats->pastEvents, p, CHUNKSIZE);  in ZSTD_splitBlock_byChunks()
176     for (pos = CHUNKSIZE; pos <= blockSize - CHUNKSIZE; pos += CHUNKSIZE) {  in ZSTD_splitBlock_byChunks()
177         record_f(&fpstats->newEvents, p + pos, CHUNKSIZE);  in ZSTD_splitBlock_byChunks()
178 …  if (compareFingerprints(&fpstats->pastEvents, &fpstats->newEvents, penalty, hashParams[level])) {  in ZSTD_splitBlock_byChunks()
181             mergeEvents(&fpstats->pastEvents, &fpstats->newEvents);  in ZSTD_splitBlock_byChunks()
182             if (penalty > 0) penalty--;  in ZSTD_splitBlock_byChunks()
212     HIST_add(fpstats->pastEvents.events, blockStart, SEGMENT_SIZE);  in ZSTD_splitBlock_fromBorders()
213 …HIST_add(fpstats->newEvents.events, (const char*)blockStart + blockSize - SEGMENT_SIZE, SEGMENT_SI…  in ZSTD_splitBlock_fromBorders()
214     fpstats->pastEvents.nbEvents = fpstats->newEvents.nbEvents = SEGMENT_SIZE;  in ZSTD_splitBlock_fromBorders()
215     if (!compareFingerprints(&fpstats->pastEvents, &fpstats->newEvents, 0, 8))  in ZSTD_splitBlock_fromBorders()
218 …HIST_add(middleEvents->events, (const char*)blockStart + blockSize/2 - SEGMENT_SIZE/2, SEGMENT_SIZ…  in ZSTD_splitBlock_fromBorders()
219     middleEvents->nbEvents = SEGMENT_SIZE;  in ZSTD_splitBlock_fromBorders()
220     {   U64 const distFromBegin = fpDistance(&fpstats->pastEvents, middleEvents, 8);  in ZSTD_splitBlock_fromBorders()
221         U64 const distFromEnd = fpDistance(&fpstats->newEvents, middleEvents, 8);  in ZSTD_splitBlock_fromBorders()
223         if (abs64((S64)distFromBegin - (S64)distFromEnd) < minDistance)  in ZSTD_splitBlock_fromBorders()
230                     int level,  in ZSTD_splitBlock()  argument
233     DEBUGLOG(6, "ZSTD_splitBlock (level=%i)", level);  in ZSTD_splitBlock()
234     assert(0<=level && level<=4);  in ZSTD_splitBlock()
235     if (level == 0)  in ZSTD_splitBlock()
237     /* level >= 1*/  in ZSTD_splitBlock()
238     return ZSTD_splitBlock_byChunks(blockStart, blockSize, level-1, workspace, wkspSize);  in ZSTD_splitBlock()