Bitcoin Core 28.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
28Sketch* ConstructGeneric1Byte(int bits, int implementation);
29Sketch* ConstructGeneric2Bytes(int bits, int implementation);
30Sketch* ConstructGeneric3Bytes(int bits, int implementation);
31Sketch* ConstructGeneric4Bytes(int bits, int implementation);
32Sketch* ConstructGeneric5Bytes(int bits, int implementation);
33Sketch* ConstructGeneric6Bytes(int bits, int implementation);
34Sketch* ConstructGeneric7Bytes(int bits, int implementation);
35Sketch* ConstructGeneric8Bytes(int bits, int implementation);
36
37#ifdef HAVE_CLMUL
38Sketch* ConstructClMul1Byte(int bits, int implementation);
39Sketch* ConstructClMul2Bytes(int bits, int implementation);
40Sketch* ConstructClMul3Bytes(int bits, int implementation);
41Sketch* ConstructClMul4Bytes(int bits, int implementation);
42Sketch* ConstructClMul5Bytes(int bits, int implementation);
43Sketch* ConstructClMul6Bytes(int bits, int implementation);
44Sketch* ConstructClMul7Bytes(int bits, int implementation);
45Sketch* ConstructClMul8Bytes(int bits, int implementation);
46Sketch* ConstructClMulTri1Byte(int bits, int implementation);
47Sketch* ConstructClMulTri2Bytes(int bits, int implementation);
48Sketch* ConstructClMulTri3Bytes(int bits, int implementation);
49Sketch* ConstructClMulTri4Bytes(int bits, int implementation);
50Sketch* ConstructClMulTri5Bytes(int bits, int implementation);
51Sketch* ConstructClMulTri6Bytes(int bits, int implementation);
52Sketch* ConstructClMulTri7Bytes(int bits, int implementation);
53Sketch* ConstructClMulTri8Bytes(int bits, int implementation);
54#endif
55
56namespace {
57
58enum class FieldImpl {
59 GENERIC = 0,
60#ifdef HAVE_CLMUL
61 CLMUL,
62 CLMUL_TRI,
63#endif
64};
65
66#ifdef HAVE_CLMUL
67static 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
80Sketch* 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
161extern "C" {
162
163int 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
356uint32_t minisketch_implementation_max() {
357 uint32_t ret = 0;
358#ifdef HAVE_CLMUL
359 ret += 2;
360#endif
361 return ret;
362}
363
364int 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
378minisketch* 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
396uint32_t minisketch_bits(const minisketch* sketch) {
397 const Sketch* s = (const Sketch*)sketch;
398 s->Check();
399 return s->Bits();
400}
401
402size_t minisketch_capacity(const minisketch* sketch) {
403 const Sketch* s = (const Sketch*)sketch;
404 s->Check();
405 return s->Syndromes();
406}
407
408uint32_t minisketch_implementation(const minisketch* sketch) {
409 const Sketch* s = (const Sketch*)sketch;
410 s->Check();
411 return s->Implementation();
412}
413
414minisketch* minisketch_clone(const minisketch* sketch) {
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
424void minisketch_destroy(minisketch* sketch) {
425 if (sketch) {
426 Sketch* s = (Sketch*)sketch;
427 s->UnReady();
428 delete s;
429 }
430}
431
432size_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
440void minisketch_serialize(const minisketch* sketch, unsigned char* output) {
441 const Sketch* s = (const Sketch*)sketch;
442 s->Check();
443 s->Serialize(output);
444}
445
446void minisketch_deserialize(minisketch* sketch, const unsigned char* input) {
447 Sketch* s = (Sketch*)sketch;
448 s->Check();
449 s->Deserialize(input);
450}
451
452void minisketch_add_uint64(minisketch* sketch, uint64_t element) {
453 Sketch* s = (Sketch*)sketch;
454 s->Check();
455 s->Add(element);
456}
457
458size_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
468ssize_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(static_cast<int>(max_elements), output);
472}
473
474void minisketch_set_seed(minisketch* sketch, uint64_t seed) {
475 Sketch* s = (Sketch*)sketch;
476 s->Check();
477 s->SetSeed(seed);
478}
479
480size_t minisketch_compute_capacity(uint32_t bits, size_t max_elements, uint32_t fpbits) {
481 return ComputeCapacity(bits, max_elements, fpbits);
482}
483
484size_t minisketch_compute_max_elements(uint32_t bits, size_t capacity, uint32_t fpbits) {
485 return ComputeMaxElements(bits, capacity, fpbits);
486}
487
488}
ret
int ret
Definition: bitcoin-cli.cpp:1354
Sketch
Abstract class for internal representation of a minisketch object.
Definition: sketch.h:15
Sketch::Implementation
int Implementation() const
Definition: sketch.h:26
Sketch::Bits
int Bits() const
Definition: sketch.h:27
Sketch::Merge
virtual size_t Merge(const Sketch *other_sketch)=0
Sketch::Ready
void Ready()
Definition: sketch.h:23
Sketch::Check
void Check() const
Definition: sketch.h:24
Sketch::Init
virtual void Init(size_t syndromes)=0
ConstructClMul1Byte
Sketch * ConstructClMul1Byte(int bits, int implementation)
Definition: clmul_1byte.cpp:85
ConstructClMulTri1Byte
Sketch * ConstructClMulTri1Byte(int bits, int implementation)
Definition: clmul_1byte.cpp:97
ConstructClMulTri2Bytes
Sketch * ConstructClMulTri2Bytes(int bits, int implementation)
Definition: clmul_2bytes.cpp:132
ConstructClMul2Bytes
Sketch * ConstructClMul2Bytes(int bits, int implementation)
Definition: clmul_2bytes.cpp:108
ConstructClMul3Bytes
Sketch * ConstructClMul3Bytes(int bits, int implementation)
Definition: clmul_3bytes.cpp:117
ConstructClMulTri3Bytes
Sketch * ConstructClMulTri3Bytes(int bits, int implementation)
Definition: clmul_3bytes.cpp:144
ConstructClMul4Bytes
Sketch * ConstructClMul4Bytes(int bits, int implementation)
Definition: clmul_4bytes.cpp:115
ConstructClMulTri4Bytes
Sketch * ConstructClMulTri4Bytes(int bits, int implementation)
Definition: clmul_4bytes.cpp:139
ConstructClMulTri5Bytes
Sketch * ConstructClMulTri5Bytes(int bits, int implementation)
Definition: clmul_5bytes.cpp:155
ConstructClMul5Bytes
Sketch * ConstructClMul5Bytes(int bits, int implementation)
Definition: clmul_5bytes.cpp:125
ConstructClMulTri6Bytes
Sketch * ConstructClMulTri6Bytes(int bits, int implementation)
Definition: clmul_6bytes.cpp:151
ConstructClMul6Bytes
Sketch * ConstructClMul6Bytes(int bits, int implementation)
Definition: clmul_6bytes.cpp:124
ConstructClMul7Bytes
Sketch * ConstructClMul7Bytes(int bits, int implementation)
Definition: clmul_7bytes.cpp:124
ConstructClMulTri7Bytes
Sketch * ConstructClMulTri7Bytes(int bits, int implementation)
Definition: clmul_7bytes.cpp:154
ConstructClMulTri8Bytes
Sketch * ConstructClMulTri8Bytes(int bits, int implementation)
Definition: clmul_8bytes.cpp:156
ConstructClMul8Bytes
Sketch * ConstructClMul8Bytes(int bits, int implementation)
Definition: clmul_8bytes.cpp:132
false_positives.h
ConstructGeneric6Bytes
Sketch * ConstructGeneric6Bytes(int bits, int implementation)
Definition: generic_6bytes.cpp:95
ConstructGeneric7Bytes
Sketch * ConstructGeneric7Bytes(int bits, int implementation)
Definition: generic_7bytes.cpp:95
ConstructGeneric8Bytes
Sketch * ConstructGeneric8Bytes(int bits, int implementation)
Definition: generic_8bytes.cpp:95
ConstructGeneric4Bytes
Sketch * ConstructGeneric4Bytes(int bits, int implementation)
Definition: generic_4bytes.cpp:95
minisketch_add_uint64
void minisketch_add_uint64(minisketch *sketch, uint64_t element)
Add an element to a sketch.
Definition: minisketch.cpp:452
minisketch_decode
ssize_t minisketch_decode(const minisketch *sketch, size_t max_elements, uint64_t *output)
Decode a sketch.
Definition: minisketch.cpp:468
ConstructGeneric3Bytes
Sketch * ConstructGeneric3Bytes(int bits, int implementation)
Definition: generic_3bytes.cpp:95
minisketch_destroy
void minisketch_destroy(minisketch *sketch)
Destroy a sketch.
Definition: minisketch.cpp:424
minisketch_bits
uint32_t minisketch_bits(const minisketch *sketch)
Get the element size of a sketch in bits.
Definition: minisketch.cpp:396
minisketch_implementation_max
uint32_t minisketch_implementation_max()
Determine the maximum number of implementations available.
Definition: minisketch.cpp:356
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:484
minisketch_implementation
uint32_t minisketch_implementation(const minisketch *sketch)
Get the implementation of a sketch.
Definition: minisketch.cpp:408
ConstructGeneric2Bytes
Sketch * ConstructGeneric2Bytes(int bits, int implementation)
Definition: generic_2bytes.cpp:95
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:378
minisketch_deserialize
void minisketch_deserialize(minisketch *sketch, const unsigned char *input)
Deserialize a sketch from bytes.
Definition: minisketch.cpp:446
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:480
minisketch_merge
size_t minisketch_merge(minisketch *sketch, const minisketch *other_sketch)
Merge the elements of another sketch into this sketch.
Definition: minisketch.cpp:458
minisketch_serialize
void minisketch_serialize(const minisketch *sketch, unsigned char *output)
Serialize a sketch to bytes.
Definition: minisketch.cpp:440
minisketch_capacity
size_t minisketch_capacity(const minisketch *sketch)
Get the capacity of a sketch.
Definition: minisketch.cpp:402
minisketch_serialized_size
size_t minisketch_serialized_size(const minisketch *sketch)
Compute the size in bytes for serializing a given sketch.
Definition: minisketch.cpp:432
ConstructGeneric5Bytes
Sketch * ConstructGeneric5Bytes(int bits, int implementation)
Definition: generic_5bytes.cpp:95
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:474
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:364
ConstructGeneric1Byte
Sketch * ConstructGeneric1Byte(int bits, int implementation)
Definition: generic_1byte.cpp:86
minisketch_bits_supported
int minisketch_bits_supported(uint32_t bits)
Determine whether support for elements of bits bits was compiled in.
Definition: minisketch.cpp:163
minisketch_clone
minisketch * minisketch_clone(const minisketch *sketch)
Clone a sketch.
Definition: minisketch.cpp:414
minisketch
struct minisketch minisketch
Opaque type for decoded sketches.
Definition: minisketch.h:41
test_vectors_musig2_generate.s
tuple s
Definition: test_vectors_musig2_generate.py:72
Generated on Wed Dec 18 2024 20:00:13 for Bitcoin Core by doxygen 1.9.4