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