Bitcoin Core  22.99.0
P2P Digital Currency
minisketch.cpp
Go to the documentation of this file.
1 /**********************************************************************
2  * Copyright (c) 2018 Pieter Wuille, Greg Maxwell, Gleb Naumenko *
3  * Distributed under the MIT software license, see the accompanying *
4  * file LICENSE or http://www.opensource.org/licenses/mit-license.php.*
5  **********************************************************************/
6 
7 
8 #include <new>
9 
10 #define MINISKETCH_BUILD
11 #ifdef _MINISKETCH_H_
12 # error "minisketch.h cannot be included before minisketch.cpp"
13 #endif
14 #include "../include/minisketch.h"
15 
16 #include "false_positives.h"
17 #include "fielddefines.h"
18 #include "sketch.h"
19 
20 #ifdef HAVE_CLMUL
21 # ifdef _MSC_VER
22 # include <intrin.h>
23 # else
24 # include <cpuid.h>
25 # endif
26 #endif
27 
28 Sketch* ConstructGeneric1Byte(int bits, int implementation);
29 Sketch* ConstructGeneric2Bytes(int bits, int implementation);
30 Sketch* ConstructGeneric3Bytes(int bits, int implementation);
31 Sketch* ConstructGeneric4Bytes(int bits, int implementation);
32 Sketch* ConstructGeneric5Bytes(int bits, int implementation);
33 Sketch* ConstructGeneric6Bytes(int bits, int implementation);
34 Sketch* ConstructGeneric7Bytes(int bits, int implementation);
35 Sketch* ConstructGeneric8Bytes(int bits, int implementation);
36 
37 #ifdef HAVE_CLMUL
38 Sketch* ConstructClMul1Byte(int bits, int implementation);
39 Sketch* ConstructClMul2Bytes(int bits, int implementation);
40 Sketch* ConstructClMul3Bytes(int bits, int implementation);
41 Sketch* ConstructClMul4Bytes(int bits, int implementation);
42 Sketch* ConstructClMul5Bytes(int bits, int implementation);
43 Sketch* ConstructClMul6Bytes(int bits, int implementation);
44 Sketch* ConstructClMul7Bytes(int bits, int implementation);
45 Sketch* ConstructClMul8Bytes(int bits, int implementation);
46 Sketch* ConstructClMulTri1Byte(int bits, int implementation);
47 Sketch* ConstructClMulTri2Bytes(int bits, int implementation);
48 Sketch* ConstructClMulTri3Bytes(int bits, int implementation);
49 Sketch* ConstructClMulTri4Bytes(int bits, int implementation);
50 Sketch* ConstructClMulTri5Bytes(int bits, int implementation);
51 Sketch* ConstructClMulTri6Bytes(int bits, int implementation);
52 Sketch* ConstructClMulTri7Bytes(int bits, int implementation);
53 Sketch* ConstructClMulTri8Bytes(int bits, int implementation);
54 #endif
55 
56 namespace {
57 
58 enum class FieldImpl {
59  GENERIC = 0,
60 #ifdef HAVE_CLMUL
61  CLMUL,
62  CLMUL_TRI,
63 #endif
64 };
65 
66 static inline bool EnableClmul()
67 {
68 #ifdef HAVE_CLMUL
69 #ifdef _MSC_VER
70  int regs[4];
71  __cpuid(regs, 1);
72  return (regs[2] & 0x2);
73 #else
74  uint32_t eax, ebx, ecx, edx;
75  return (__get_cpuid(1, &eax, &ebx, &ecx, &edx) && (ecx & 0x2));
76 #endif
77 #else
78  return false;
79 #endif
80 }
81 
82 Sketch* Construct(int bits, int impl)
83 {
84  switch (FieldImpl(impl)) {
85  case FieldImpl::GENERIC:
86  switch ((bits + 7) / 8) {
87  case 1:
88  return ConstructGeneric1Byte(bits, impl);
89  case 2:
90  return ConstructGeneric2Bytes(bits, impl);
91  case 3:
92  return ConstructGeneric3Bytes(bits, impl);
93  case 4:
94  return ConstructGeneric4Bytes(bits, impl);
95  case 5:
96  return ConstructGeneric5Bytes(bits, impl);
97  case 6:
98  return ConstructGeneric6Bytes(bits, impl);
99  case 7:
100  return ConstructGeneric7Bytes(bits, impl);
101  case 8:
102  return ConstructGeneric8Bytes(bits, impl);
103  default:
104  return nullptr;
105  }
106  break;
107 #ifdef HAVE_CLMUL
108  case FieldImpl::CLMUL:
109  if (EnableClmul()) {
110  switch ((bits + 7) / 8) {
111  case 1:
112  return ConstructClMul1Byte(bits, impl);
113  case 2:
114  return ConstructClMul2Bytes(bits, impl);
115  case 3:
116  return ConstructClMul3Bytes(bits, impl);
117  case 4:
118  return ConstructClMul4Bytes(bits, impl);
119  case 5:
120  return ConstructClMul5Bytes(bits, impl);
121  case 6:
122  return ConstructClMul6Bytes(bits, impl);
123  case 7:
124  return ConstructClMul7Bytes(bits, impl);
125  case 8:
126  return ConstructClMul8Bytes(bits, impl);
127  default:
128  return nullptr;
129  }
130  }
131  break;
132  case FieldImpl::CLMUL_TRI:
133  if (EnableClmul()) {
134  switch ((bits + 7) / 8) {
135  case 1:
136  return ConstructClMulTri1Byte(bits, impl);
137  case 2:
138  return ConstructClMulTri2Bytes(bits, impl);
139  case 3:
140  return ConstructClMulTri3Bytes(bits, impl);
141  case 4:
142  return ConstructClMulTri4Bytes(bits, impl);
143  case 5:
144  return ConstructClMulTri5Bytes(bits, impl);
145  case 6:
146  return ConstructClMulTri6Bytes(bits, impl);
147  case 7:
148  return ConstructClMulTri7Bytes(bits, impl);
149  case 8:
150  return ConstructClMulTri8Bytes(bits, impl);
151  default:
152  return nullptr;
153  }
154  }
155  break;
156 #endif
157  }
158  return nullptr;
159 }
160 
161 }
162 
163 extern "C" {
164 
165 int minisketch_bits_supported(uint32_t bits) {
166 #ifdef ENABLE_FIELD_INT_2
167  if (bits == 2) return true;
168 #endif
169 #ifdef ENABLE_FIELD_INT_3
170  if (bits == 3) return true;
171 #endif
172 #ifdef ENABLE_FIELD_INT_4
173  if (bits == 4) return true;
174 #endif
175 #ifdef ENABLE_FIELD_INT_5
176  if (bits == 5) return true;
177 #endif
178 #ifdef ENABLE_FIELD_INT_6
179  if (bits == 6) return true;
180 #endif
181 #ifdef ENABLE_FIELD_INT_7
182  if (bits == 7) return true;
183 #endif
184 #ifdef ENABLE_FIELD_INT_8
185  if (bits == 8) return true;
186 #endif
187 #ifdef ENABLE_FIELD_INT_9
188  if (bits == 9) return true;
189 #endif
190 #ifdef ENABLE_FIELD_INT_10
191  if (bits == 10) return true;
192 #endif
193 #ifdef ENABLE_FIELD_INT_11
194  if (bits == 11) return true;
195 #endif
196 #ifdef ENABLE_FIELD_INT_12
197  if (bits == 12) return true;
198 #endif
199 #ifdef ENABLE_FIELD_INT_13
200  if (bits == 13) return true;
201 #endif
202 #ifdef ENABLE_FIELD_INT_14
203  if (bits == 14) return true;
204 #endif
205 #ifdef ENABLE_FIELD_INT_15
206  if (bits == 15) return true;
207 #endif
208 #ifdef ENABLE_FIELD_INT_16
209  if (bits == 16) return true;
210 #endif
211 #ifdef ENABLE_FIELD_INT_17
212  if (bits == 17) return true;
213 #endif
214 #ifdef ENABLE_FIELD_INT_18
215  if (bits == 18) return true;
216 #endif
217 #ifdef ENABLE_FIELD_INT_19
218  if (bits == 19) return true;
219 #endif
220 #ifdef ENABLE_FIELD_INT_20
221  if (bits == 20) return true;
222 #endif
223 #ifdef ENABLE_FIELD_INT_21
224  if (bits == 21) return true;
225 #endif
226 #ifdef ENABLE_FIELD_INT_22
227  if (bits == 22) return true;
228 #endif
229 #ifdef ENABLE_FIELD_INT_23
230  if (bits == 23) return true;
231 #endif
232 #ifdef ENABLE_FIELD_INT_24
233  if (bits == 24) return true;
234 #endif
235 #ifdef ENABLE_FIELD_INT_25
236  if (bits == 25) return true;
237 #endif
238 #ifdef ENABLE_FIELD_INT_26
239  if (bits == 26) return true;
240 #endif
241 #ifdef ENABLE_FIELD_INT_27
242  if (bits == 27) return true;
243 #endif
244 #ifdef ENABLE_FIELD_INT_28
245  if (bits == 28) return true;
246 #endif
247 #ifdef ENABLE_FIELD_INT_29
248  if (bits == 29) return true;
249 #endif
250 #ifdef ENABLE_FIELD_INT_30
251  if (bits == 30) return true;
252 #endif
253 #ifdef ENABLE_FIELD_INT_31
254  if (bits == 31) return true;
255 #endif
256 #ifdef ENABLE_FIELD_INT_32
257  if (bits == 32) return true;
258 #endif
259 #ifdef ENABLE_FIELD_INT_33
260  if (bits == 33) return true;
261 #endif
262 #ifdef ENABLE_FIELD_INT_34
263  if (bits == 34) return true;
264 #endif
265 #ifdef ENABLE_FIELD_INT_35
266  if (bits == 35) return true;
267 #endif
268 #ifdef ENABLE_FIELD_INT_36
269  if (bits == 36) return true;
270 #endif
271 #ifdef ENABLE_FIELD_INT_37
272  if (bits == 37) return true;
273 #endif
274 #ifdef ENABLE_FIELD_INT_38
275  if (bits == 38) return true;
276 #endif
277 #ifdef ENABLE_FIELD_INT_39
278  if (bits == 39) return true;
279 #endif
280 #ifdef ENABLE_FIELD_INT_40
281  if (bits == 40) return true;
282 #endif
283 #ifdef ENABLE_FIELD_INT_41
284  if (bits == 41) return true;
285 #endif
286 #ifdef ENABLE_FIELD_INT_42
287  if (bits == 42) return true;
288 #endif
289 #ifdef ENABLE_FIELD_INT_43
290  if (bits == 43) return true;
291 #endif
292 #ifdef ENABLE_FIELD_INT_44
293  if (bits == 44) return true;
294 #endif
295 #ifdef ENABLE_FIELD_INT_45
296  if (bits == 45) return true;
297 #endif
298 #ifdef ENABLE_FIELD_INT_46
299  if (bits == 46) return true;
300 #endif
301 #ifdef ENABLE_FIELD_INT_47
302  if (bits == 47) return true;
303 #endif
304 #ifdef ENABLE_FIELD_INT_48
305  if (bits == 48) return true;
306 #endif
307 #ifdef ENABLE_FIELD_INT_49
308  if (bits == 49) return true;
309 #endif
310 #ifdef ENABLE_FIELD_INT_50
311  if (bits == 50) return true;
312 #endif
313 #ifdef ENABLE_FIELD_INT_51
314  if (bits == 51) return true;
315 #endif
316 #ifdef ENABLE_FIELD_INT_52
317  if (bits == 52) return true;
318 #endif
319 #ifdef ENABLE_FIELD_INT_53
320  if (bits == 53) return true;
321 #endif
322 #ifdef ENABLE_FIELD_INT_54
323  if (bits == 54) return true;
324 #endif
325 #ifdef ENABLE_FIELD_INT_55
326  if (bits == 55) return true;
327 #endif
328 #ifdef ENABLE_FIELD_INT_56
329  if (bits == 56) return true;
330 #endif
331 #ifdef ENABLE_FIELD_INT_57
332  if (bits == 57) return true;
333 #endif
334 #ifdef ENABLE_FIELD_INT_58
335  if (bits == 58) return true;
336 #endif
337 #ifdef ENABLE_FIELD_INT_59
338  if (bits == 59) return true;
339 #endif
340 #ifdef ENABLE_FIELD_INT_60
341  if (bits == 60) return true;
342 #endif
343 #ifdef ENABLE_FIELD_INT_61
344  if (bits == 61) return true;
345 #endif
346 #ifdef ENABLE_FIELD_INT_62
347  if (bits == 62) return true;
348 #endif
349 #ifdef ENABLE_FIELD_INT_63
350  if (bits == 63) return true;
351 #endif
352 #ifdef ENABLE_FIELD_INT_64
353  if (bits == 64) return true;
354 #endif
355  return false;
356 }
357 
359  uint32_t ret = 0;
360 #ifdef HAVE_CLMUL
361  ret += 2;
362 #endif
363  return ret;
364 }
365 
366 int minisketch_implementation_supported(uint32_t bits, uint32_t implementation) {
367  if (!minisketch_bits_supported(bits) || implementation > minisketch_implementation_max()) {
368  return 0;
369  }
370  try {
371  Sketch* sketch = Construct(bits, implementation);
372  if (sketch) {
373  delete sketch;
374  return 1;
375  }
376  } catch (const std::bad_alloc&) {}
377  return 0;
378 }
379 
380 minisketch* minisketch_create(uint32_t bits, uint32_t implementation, size_t capacity) {
381  try {
382  Sketch* sketch = Construct(bits, implementation);
383  if (sketch) {
384  try {
385  sketch->Init(capacity);
386  } catch (const std::bad_alloc&) {
387  delete sketch;
388  throw;
389  }
390  sketch->Ready();
391  }
392  return (minisketch*)sketch;
393  } catch (const std::bad_alloc&) {
394  return nullptr;
395  }
396 }
397 
398 uint32_t minisketch_bits(const minisketch* sketch) {
399  const Sketch* s = (const Sketch*)sketch;
400  s->Check();
401  return s->Bits();
402 }
403 
404 size_t minisketch_capacity(const minisketch* sketch) {
405  const Sketch* s = (const Sketch*)sketch;
406  s->Check();
407  return s->Syndromes();
408 }
409 
410 uint32_t minisketch_implementation(const minisketch* sketch) {
411  const Sketch* s = (const Sketch*)sketch;
412  s->Check();
413  return s->Implementation();
414 }
415 
417  const Sketch* s = (const Sketch*)sketch;
418  s->Check();
419  Sketch* r = (Sketch*) minisketch_create(s->Bits(), s->Implementation(), s->Syndromes());
420  if (r) {
421  r->Merge(s);
422  }
423  return (minisketch*) r;
424 }
425 
427  if (sketch) {
428  Sketch* s = (Sketch*)sketch;
429  s->UnReady();
430  delete s;
431  }
432 }
433 
434 size_t minisketch_serialized_size(const minisketch* sketch) {
435  const Sketch* s = (const Sketch*)sketch;
436  s->Check();
437  size_t bits = s->Bits();
438  size_t syndromes = s->Syndromes();
439  return (bits * syndromes + 7) / 8;
440 }
441 
442 void minisketch_serialize(const minisketch* sketch, unsigned char* output) {
443  const Sketch* s = (const Sketch*)sketch;
444  s->Check();
445  s->Serialize(output);
446 }
447 
448 void minisketch_deserialize(minisketch* sketch, const unsigned char* input) {
449  Sketch* s = (Sketch*)sketch;
450  s->Check();
451  s->Deserialize(input);
452 }
453 
454 void minisketch_add_uint64(minisketch* sketch, uint64_t element) {
455  Sketch* s = (Sketch*)sketch;
456  s->Check();
457  s->Add(element);
458 }
459 
460 size_t minisketch_merge(minisketch* sketch, const minisketch* other_sketch) {
461  Sketch* s1 = (Sketch*)sketch;
462  const Sketch* s2 = (const Sketch*)other_sketch;
463  s1->Check();
464  s2->Check();
465  if (s1->Bits() != s2->Bits()) return 0;
466  if (s1->Implementation() != s2->Implementation()) return 0;
467  return s1->Merge(s2);
468 }
469 
470 ssize_t minisketch_decode(const minisketch* sketch, size_t max_elements, uint64_t* output) {
471  const Sketch* s = (const Sketch*)sketch;
472  s->Check();
473  return s->Decode(max_elements, output);
474 }
475 
476 void minisketch_set_seed(minisketch* sketch, uint64_t seed) {
477  Sketch* s = (Sketch*)sketch;
478  s->Check();
479  s->SetSeed(seed);
480 }
481 
482 size_t minisketch_compute_capacity(uint32_t bits, size_t max_elements, uint32_t fpbits) {
483  return ComputeCapacity(bits, max_elements, fpbits);
484 }
485 
486 size_t minisketch_compute_max_elements(uint32_t bits, size_t capacity, uint32_t fpbits) {
487  return ComputeMaxElements(bits, capacity, fpbits);
488 }
489 
490 }
minisketch_clone
minisketch * minisketch_clone(const minisketch *sketch)
Clone a sketch.
Definition: minisketch.cpp:416
minisketch_decode
ssize_t minisketch_decode(const minisketch *sketch, size_t max_elements, uint64_t *output)
Decode a sketch.
Definition: minisketch.cpp:470
ConstructClMulTri1Byte
Sketch * ConstructClMulTri1Byte(int bits, int implementation)
Definition: clmul_1byte.cpp:97
minisketch_merge
size_t minisketch_merge(minisketch *sketch, const minisketch *other_sketch)
Merge the elements of another sketch into this sketch.
Definition: minisketch.cpp:460
ConstructClMulTri8Bytes
Sketch * ConstructClMulTri8Bytes(int bits, int implementation)
Definition: clmul_8bytes.cpp:156
Sketch::Decode
virtual int Decode(int max_count, uint64_t *roots) const =0
ConstructClMul6Bytes
Sketch * ConstructClMul6Bytes(int bits, int implementation)
Definition: clmul_6bytes.cpp:124
fielddefines.h
ConstructGeneric3Bytes
Sketch * ConstructGeneric3Bytes(int bits, int implementation)
Definition: generic_3bytes.cpp:95
Sketch::Syndromes
virtual size_t Syndromes() const =0
minisketch_compute_max_elements
size_t minisketch_compute_max_elements(uint32_t bits, size_t capacity, uint32_t fpbits)
Compute what max_elements can be decoded for a certain rate of false positives.
Definition: minisketch.cpp:486
cpuid.h
minisketch_add_uint64
void minisketch_add_uint64(minisketch *sketch, uint64_t element)
Add an element to a sketch.
Definition: minisketch.cpp:454
Sketch::Add
virtual void Add(uint64_t element)=0
minisketch_bits
uint32_t minisketch_bits(const minisketch *sketch)
Get the element size of a sketch in bits.
Definition: minisketch.cpp:398
ConstructGeneric8Bytes
Sketch * ConstructGeneric8Bytes(int bits, int implementation)
Definition: generic_8bytes.cpp:95
Sketch::Implementation
int Implementation() const
Definition: sketch.h:30
minisketch_create
minisketch * minisketch_create(uint32_t bits, uint32_t implementation, size_t capacity)
Construct a sketch for a given element size, implementation and capacity.
Definition: minisketch.cpp:380
minisketch_capacity
size_t minisketch_capacity(const minisketch *sketch)
Get the capacity of a sketch.
Definition: minisketch.cpp:404
minisketch_destroy
void minisketch_destroy(minisketch *sketch)
Destroy a sketch.
Definition: minisketch.cpp:426
Sketch
Abstract class for internal representation of a minisketch object.
Definition: sketch.h:14
ConstructGeneric4Bytes
Sketch * ConstructGeneric4Bytes(int bits, int implementation)
Definition: generic_4bytes.cpp:95
sketch.h
ConstructClMul7Bytes
Sketch * ConstructClMul7Bytes(int bits, int implementation)
Definition: clmul_7bytes.cpp:124
ConstructClMul4Bytes
Sketch * ConstructClMul4Bytes(int bits, int implementation)
Definition: clmul_4bytes.cpp:115
ConstructGeneric5Bytes
Sketch * ConstructGeneric5Bytes(int bits, int implementation)
Definition: generic_5bytes.cpp:95
Sketch::SetSeed
virtual void SetSeed(uint64_t seed)=0
minisketch_compute_capacity
size_t minisketch_compute_capacity(uint32_t bits, size_t max_elements, uint32_t fpbits)
Compute the capacity needed to achieve a certain rate of false positives.
Definition: minisketch.cpp:482
ConstructClMul8Bytes
Sketch * ConstructClMul8Bytes(int bits, int implementation)
Definition: clmul_8bytes.cpp:132
minisketch_deserialize
void minisketch_deserialize(minisketch *sketch, const unsigned char *input)
Deserialize a sketch from bytes.
Definition: minisketch.cpp:448
ConstructClMulTri6Bytes
Sketch * ConstructClMulTri6Bytes(int bits, int implementation)
Definition: clmul_6bytes.cpp:151
ConstructClMul3Bytes
Sketch * ConstructClMul3Bytes(int bits, int implementation)
Definition: clmul_3bytes.cpp:117
minisketch
struct minisketch minisketch
Opaque type for decoded sketches.
Definition: minisketch.h:40
ConstructClMulTri2Bytes
Sketch * ConstructClMulTri2Bytes(int bits, int implementation)
Definition: clmul_2bytes.cpp:132
false_positives.h
minisketch_implementation_max
uint32_t minisketch_implementation_max()
Determine the maximum number of implementations available.
Definition: minisketch.cpp:358
minisketch_implementation_supported
int minisketch_implementation_supported(uint32_t bits, uint32_t implementation)
Determine if the a combination of bits and implementation number is available.
Definition: minisketch.cpp:366
ConstructClMul5Bytes
Sketch * ConstructClMul5Bytes(int bits, int implementation)
Definition: clmul_5bytes.cpp:125
Sketch::Deserialize
virtual void Deserialize(const unsigned char *)=0
ConstructClMulTri7Bytes
Sketch * ConstructClMulTri7Bytes(int bits, int implementation)
Definition: clmul_7bytes.cpp:154
Sketch::Serialize
virtual void Serialize(unsigned char *) const =0
ConstructClMulTri5Bytes
Sketch * ConstructClMulTri5Bytes(int bits, int implementation)
Definition: clmul_5bytes.cpp:155
ConstructGeneric7Bytes
Sketch * ConstructGeneric7Bytes(int bits, int implementation)
Definition: generic_7bytes.cpp:95
ConstructClMulTri4Bytes
Sketch * ConstructClMulTri4Bytes(int bits, int implementation)
Definition: clmul_4bytes.cpp:139
minisketch_serialized_size
size_t minisketch_serialized_size(const minisketch *sketch)
Compute the size in bytes for serializing a given sketch.
Definition: minisketch.cpp:434
minisketch_serialize
void minisketch_serialize(const minisketch *sketch, unsigned char *output)
Serialize a sketch to bytes.
Definition: minisketch.cpp:442
ConstructClMul2Bytes
Sketch * ConstructClMul2Bytes(int bits, int implementation)
Definition: clmul_2bytes.cpp:108
minisketch_bits_supported
int minisketch_bits_supported(uint32_t bits)
Determine whether support for elements of bits bits was compiled in.
Definition: minisketch.cpp:165
ConstructClMul1Byte
Sketch * ConstructClMul1Byte(int bits, int implementation)
Definition: clmul_1byte.cpp:85
ConstructGeneric6Bytes
Sketch * ConstructGeneric6Bytes(int bits, int implementation)
Definition: generic_6bytes.cpp:95
Sketch::Check
void Check() const
Definition: sketch.h:28
Sketch::Ready
void Ready()
Definition: sketch.h:27
ConstructGeneric1Byte
Sketch * ConstructGeneric1Byte(int bits, int implementation)
Definition: generic_1byte.cpp:86
ConstructClMulTri3Bytes
Sketch * ConstructClMulTri3Bytes(int bits, int implementation)
Definition: clmul_3bytes.cpp:144
ConstructGeneric2Bytes
Sketch * ConstructGeneric2Bytes(int bits, int implementation)
Definition: generic_2bytes.cpp:95
Sketch::Init
virtual void Init(int syndromes)=0
minisketch_set_seed
void minisketch_set_seed(minisketch *sketch, uint64_t seed)
Set the seed for randomizing algorithm choices to a fixed value.
Definition: minisketch.cpp:476
minisketch_implementation
uint32_t minisketch_implementation(const minisketch *sketch)
Get the implementation of a sketch.
Definition: minisketch.cpp:410
Sketch::Bits
int Bits() const
Definition: sketch.h:31
Sketch::Merge
virtual size_t Merge(const Sketch *other_sketch)=0
Sketch::UnReady
void UnReady()
Definition: sketch.h:29