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