1 /*
2 * Copyright (c) Meta Platforms, Inc. and affiliates.
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 "../common/compiler.h" /* ZSTD_ALIGNOF */
12 #include "../common/mem.h" /* S64 */
13 #include "../common/zstd_deps.h" /* ZSTD_memset */
14 #include "../common/zstd_internal.h" /* ZSTD_STATIC_ASSERT */
15 #include "hist.h" /* HIST_add */
16 #include "zstd_preSplit.h"
17
18
19 #define BLOCKSIZE_MIN 3500
20 #define THRESHOLD_PENALTY_RATE 16
21 #define THRESHOLD_BASE (THRESHOLD_PENALTY_RATE - 2)
22 #define THRESHOLD_PENALTY 3
23
24 #define HASHLENGTH 2
25 #define HASHLOG_MAX 10
26 #define HASHTABLESIZE (1 << HASHLOG_MAX)
27 #define HASHMASK (HASHTABLESIZE - 1)
28 #define KNUTH 0x9e3779b9
29
30 /* for hashLog > 8, hash 2 bytes.
31 * for hashLog == 8, just take the byte, no hashing.
32 * The speed of this method relies on compile-time constant propagation */
hash2(const void * p,unsigned hashLog)33 FORCE_INLINE_TEMPLATE unsigned hash2(const void *p, unsigned hashLog)
34 {
35 assert(hashLog >= 8);
36 if (hashLog == 8) return (U32)((const BYTE*)p)[0];
37 assert(hashLog <= HASHLOG_MAX);
38 return (U32)(MEM_read16(p)) * KNUTH >> (32 - hashLog);
39 }
40
41
42 typedef struct {
43 unsigned events[HASHTABLESIZE];
44 size_t nbEvents;
45 } Fingerprint;
46 typedef struct {
47 Fingerprint pastEvents;
48 Fingerprint newEvents;
49 } FPStats;
50
initStats(FPStats * fpstats)51 static void initStats(FPStats* fpstats)
52 {
53 ZSTD_memset(fpstats, 0, sizeof(FPStats));
54 }
55
56 FORCE_INLINE_TEMPLATE void
addEvents_generic(Fingerprint * fp,const void * src,size_t srcSize,size_t samplingRate,unsigned hashLog)57 addEvents_generic(Fingerprint* fp, const void* src, size_t srcSize, size_t samplingRate, unsigned hashLog)
58 {
59 const char* p = (const char*)src;
60 size_t limit = srcSize - HASHLENGTH + 1;
61 size_t n;
62 assert(srcSize >= HASHLENGTH);
63 for (n = 0; n < limit; n+=samplingRate) {
64 fp->events[hash2(p+n, hashLog)]++;
65 }
66 fp->nbEvents += limit/samplingRate;
67 }
68
69 FORCE_INLINE_TEMPLATE void
recordFingerprint_generic(Fingerprint * fp,const void * src,size_t srcSize,size_t samplingRate,unsigned hashLog)70 recordFingerprint_generic(Fingerprint* fp, const void* src, size_t srcSize, size_t samplingRate, unsigned hashLog)
71 {
72 ZSTD_memset(fp, 0, sizeof(unsigned) * ((size_t)1 << hashLog));
73 fp->nbEvents = 0;
74 addEvents_generic(fp, src, srcSize, samplingRate, hashLog);
75 }
76
77 typedef void (*RecordEvents_f)(Fingerprint* fp, const void* src, size_t srcSize);
78
79 #define FP_RECORD(_rate) ZSTD_recordFingerprint_##_rate
80
81 #define ZSTD_GEN_RECORD_FINGERPRINT(_rate, _hSize) \
82 static void FP_RECORD(_rate)(Fingerprint* fp, const void* src, size_t srcSize) \
83 { \
84 recordFingerprint_generic(fp, src, srcSize, _rate, _hSize); \
85 }
86
87 ZSTD_GEN_RECORD_FINGERPRINT(1, 10)
88 ZSTD_GEN_RECORD_FINGERPRINT(5, 10)
89 ZSTD_GEN_RECORD_FINGERPRINT(11, 9)
90 ZSTD_GEN_RECORD_FINGERPRINT(43, 8)
91
92
abs64(S64 s64)93 static U64 abs64(S64 s64) { return (U64)((s64 < 0) ? -s64 : s64); }
94
fpDistance(const Fingerprint * fp1,const Fingerprint * fp2,unsigned hashLog)95 static U64 fpDistance(const Fingerprint* fp1, const Fingerprint* fp2, unsigned hashLog)
96 {
97 U64 distance = 0;
98 size_t n;
99 assert(hashLog <= HASHLOG_MAX);
100 for (n = 0; n < ((size_t)1 << hashLog); n++) {
101 distance +=
102 abs64((S64)fp1->events[n] * (S64)fp2->nbEvents - (S64)fp2->events[n] * (S64)fp1->nbEvents);
103 }
104 return distance;
105 }
106
107 /* Compare newEvents with pastEvents
108 * return 1 when considered "too different"
109 */
compareFingerprints(const Fingerprint * ref,const Fingerprint * newfp,int penalty,unsigned hashLog)110 static int compareFingerprints(const Fingerprint* ref,
111 const Fingerprint* newfp,
112 int penalty,
113 unsigned hashLog)
114 {
115 assert(ref->nbEvents > 0);
116 assert(newfp->nbEvents > 0);
117 { U64 p50 = (U64)ref->nbEvents * (U64)newfp->nbEvents;
118 U64 deviation = fpDistance(ref, newfp, hashLog);
119 U64 threshold = p50 * (U64)(THRESHOLD_BASE + penalty) / THRESHOLD_PENALTY_RATE;
120 return deviation >= threshold;
121 }
122 }
123
mergeEvents(Fingerprint * acc,const Fingerprint * newfp)124 static void mergeEvents(Fingerprint* acc, const Fingerprint* newfp)
125 {
126 size_t n;
127 for (n = 0; n < HASHTABLESIZE; n++) {
128 acc->events[n] += newfp->events[n];
129 }
130 acc->nbEvents += newfp->nbEvents;
131 }
132
flushEvents(FPStats * fpstats)133 static void flushEvents(FPStats* fpstats)
134 {
135 size_t n;
136 for (n = 0; n < HASHTABLESIZE; n++) {
137 fpstats->pastEvents.events[n] = fpstats->newEvents.events[n];
138 }
139 fpstats->pastEvents.nbEvents = fpstats->newEvents.nbEvents;
140 ZSTD_memset(&fpstats->newEvents, 0, sizeof(fpstats->newEvents));
141 }
142
removeEvents(Fingerprint * acc,const Fingerprint * slice)143 static void removeEvents(Fingerprint* acc, const Fingerprint* slice)
144 {
145 size_t n;
146 for (n = 0; n < HASHTABLESIZE; n++) {
147 assert(acc->events[n] >= slice->events[n]);
148 acc->events[n] -= slice->events[n];
149 }
150 acc->nbEvents -= slice->nbEvents;
151 }
152
153 #define CHUNKSIZE (8 << 10)
ZSTD_splitBlock_byChunks(const void * blockStart,size_t blockSize,int level,void * workspace,size_t wkspSize)154 static size_t ZSTD_splitBlock_byChunks(const void* blockStart, size_t blockSize,
155 int level,
156 void* workspace, size_t wkspSize)
157 {
158 static const RecordEvents_f records_fs[] = {
159 FP_RECORD(43), FP_RECORD(11), FP_RECORD(5), FP_RECORD(1)
160 };
161 static const unsigned hashParams[] = { 8, 9, 10, 10 };
162 const RecordEvents_f record_f = (assert(0<=level && level<=3), records_fs[level]);
163 FPStats* const fpstats = (FPStats*)workspace;
164 const char* p = (const char*)blockStart;
165 int penalty = THRESHOLD_PENALTY;
166 size_t pos = 0;
167 assert(blockSize == (128 << 10));
168 assert(workspace != NULL);
169 assert((size_t)workspace % ZSTD_ALIGNOF(FPStats) == 0);
170 ZSTD_STATIC_ASSERT(ZSTD_SLIPBLOCK_WORKSPACESIZE >= sizeof(FPStats));
171 assert(wkspSize >= sizeof(FPStats)); (void)wkspSize;
172
173 initStats(fpstats);
174 record_f(&fpstats->pastEvents, p, CHUNKSIZE);
175 for (pos = CHUNKSIZE; pos <= blockSize - CHUNKSIZE; pos += CHUNKSIZE) {
176 record_f(&fpstats->newEvents, p + pos, CHUNKSIZE);
177 if (compareFingerprints(&fpstats->pastEvents, &fpstats->newEvents, penalty, hashParams[level])) {
178 return pos;
179 } else {
180 mergeEvents(&fpstats->pastEvents, &fpstats->newEvents);
181 if (penalty > 0) penalty--;
182 }
183 }
184 assert(pos == blockSize);
185 return blockSize;
186 (void)flushEvents; (void)removeEvents;
187 }
188
189 /* ZSTD_splitBlock_fromBorders(): very fast strategy :
190 * compare fingerprint from beginning and end of the block,
191 * derive from their difference if it's preferable to split in the middle,
192 * repeat the process a second time, for finer grained decision.
193 * 3 times did not brought improvements, so I stopped at 2.
194 * Benefits are good enough for a cheap heuristic.
195 * More accurate splitting saves more, but speed impact is also more perceptible.
196 * For better accuracy, use more elaborate variant *_byChunks.
197 */
ZSTD_splitBlock_fromBorders(const void * blockStart,size_t blockSize,void * workspace,size_t wkspSize)198 static size_t ZSTD_splitBlock_fromBorders(const void* blockStart, size_t blockSize,
199 void* workspace, size_t wkspSize)
200 {
201 #define SEGMENT_SIZE 512
202 FPStats* const fpstats = (FPStats*)workspace;
203 Fingerprint* middleEvents = (Fingerprint*)(void*)((char*)workspace + 512 * sizeof(unsigned));
204 assert(blockSize == (128 << 10));
205 assert(workspace != NULL);
206 assert((size_t)workspace % ZSTD_ALIGNOF(FPStats) == 0);
207 ZSTD_STATIC_ASSERT(ZSTD_SLIPBLOCK_WORKSPACESIZE >= sizeof(FPStats));
208 assert(wkspSize >= sizeof(FPStats)); (void)wkspSize;
209
210 initStats(fpstats);
211 HIST_add(fpstats->pastEvents.events, blockStart, SEGMENT_SIZE);
212 HIST_add(fpstats->newEvents.events, (const char*)blockStart + blockSize - SEGMENT_SIZE, SEGMENT_SIZE);
213 fpstats->pastEvents.nbEvents = fpstats->newEvents.nbEvents = SEGMENT_SIZE;
214 if (!compareFingerprints(&fpstats->pastEvents, &fpstats->newEvents, 0, 8))
215 return blockSize;
216
217 HIST_add(middleEvents->events, (const char*)blockStart + blockSize/2 - SEGMENT_SIZE/2, SEGMENT_SIZE);
218 middleEvents->nbEvents = SEGMENT_SIZE;
219 { U64 const distFromBegin = fpDistance(&fpstats->pastEvents, middleEvents, 8);
220 U64 const distFromEnd = fpDistance(&fpstats->newEvents, middleEvents, 8);
221 U64 const minDistance = SEGMENT_SIZE * SEGMENT_SIZE / 3;
222 if (abs64((S64)distFromBegin - (S64)distFromEnd) < minDistance)
223 return 64 KB;
224 return (distFromBegin > distFromEnd) ? 32 KB : 96 KB;
225 }
226 }
227
ZSTD_splitBlock(const void * blockStart,size_t blockSize,int level,void * workspace,size_t wkspSize)228 size_t ZSTD_splitBlock(const void* blockStart, size_t blockSize,
229 int level,
230 void* workspace, size_t wkspSize)
231 {
232 DEBUGLOG(6, "ZSTD_splitBlock (level=%i)", level);
233 assert(0<=level && level<=4);
234 if (level == 0)
235 return ZSTD_splitBlock_fromBorders(blockStart, blockSize, workspace, wkspSize);
236 /* level >= 1*/
237 return ZSTD_splitBlock_byChunks(blockStart, blockSize, level-1, workspace, wkspSize);
238 }
239