10 #define MINISKETCH_BUILD
12 # error "minisketch.h cannot be included before minisketch.cpp"
14 #include "../include/minisketch.h"
58 enum class FieldImpl {
67 static inline bool EnableClmul()
72 return (regs[2] & 0x2);
74 uint32_t eax, ebx, ecx, edx;
75 return (__get_cpuid(1, &eax, &ebx, &ecx, &edx) && (ecx & 0x2));
80 Sketch* Construct(
int bits,
int impl)
82 switch (FieldImpl(impl)) {
83 case FieldImpl::GENERIC:
84 switch ((bits + 7) / 8) {
106 case FieldImpl::CLMUL:
108 switch ((bits + 7) / 8) {
130 case FieldImpl::CLMUL_TRI:
132 switch ((bits + 7) / 8) {
164 #ifdef ENABLE_FIELD_INT_2
165 if (bits == 2)
return true;
167 #ifdef ENABLE_FIELD_INT_3
168 if (bits == 3)
return true;
170 #ifdef ENABLE_FIELD_INT_4
171 if (bits == 4)
return true;
173 #ifdef ENABLE_FIELD_INT_5
174 if (bits == 5)
return true;
176 #ifdef ENABLE_FIELD_INT_6
177 if (bits == 6)
return true;
179 #ifdef ENABLE_FIELD_INT_7
180 if (bits == 7)
return true;
182 #ifdef ENABLE_FIELD_INT_8
183 if (bits == 8)
return true;
185 #ifdef ENABLE_FIELD_INT_9
186 if (bits == 9)
return true;
188 #ifdef ENABLE_FIELD_INT_10
189 if (bits == 10)
return true;
191 #ifdef ENABLE_FIELD_INT_11
192 if (bits == 11)
return true;
194 #ifdef ENABLE_FIELD_INT_12
195 if (bits == 12)
return true;
197 #ifdef ENABLE_FIELD_INT_13
198 if (bits == 13)
return true;
200 #ifdef ENABLE_FIELD_INT_14
201 if (bits == 14)
return true;
203 #ifdef ENABLE_FIELD_INT_15
204 if (bits == 15)
return true;
206 #ifdef ENABLE_FIELD_INT_16
207 if (bits == 16)
return true;
209 #ifdef ENABLE_FIELD_INT_17
210 if (bits == 17)
return true;
212 #ifdef ENABLE_FIELD_INT_18
213 if (bits == 18)
return true;
215 #ifdef ENABLE_FIELD_INT_19
216 if (bits == 19)
return true;
218 #ifdef ENABLE_FIELD_INT_20
219 if (bits == 20)
return true;
221 #ifdef ENABLE_FIELD_INT_21
222 if (bits == 21)
return true;
224 #ifdef ENABLE_FIELD_INT_22
225 if (bits == 22)
return true;
227 #ifdef ENABLE_FIELD_INT_23
228 if (bits == 23)
return true;
230 #ifdef ENABLE_FIELD_INT_24
231 if (bits == 24)
return true;
233 #ifdef ENABLE_FIELD_INT_25
234 if (bits == 25)
return true;
236 #ifdef ENABLE_FIELD_INT_26
237 if (bits == 26)
return true;
239 #ifdef ENABLE_FIELD_INT_27
240 if (bits == 27)
return true;
242 #ifdef ENABLE_FIELD_INT_28
243 if (bits == 28)
return true;
245 #ifdef ENABLE_FIELD_INT_29
246 if (bits == 29)
return true;
248 #ifdef ENABLE_FIELD_INT_30
249 if (bits == 30)
return true;
251 #ifdef ENABLE_FIELD_INT_31
252 if (bits == 31)
return true;
254 #ifdef ENABLE_FIELD_INT_32
255 if (bits == 32)
return true;
257 #ifdef ENABLE_FIELD_INT_33
258 if (bits == 33)
return true;
260 #ifdef ENABLE_FIELD_INT_34
261 if (bits == 34)
return true;
263 #ifdef ENABLE_FIELD_INT_35
264 if (bits == 35)
return true;
266 #ifdef ENABLE_FIELD_INT_36
267 if (bits == 36)
return true;
269 #ifdef ENABLE_FIELD_INT_37
270 if (bits == 37)
return true;
272 #ifdef ENABLE_FIELD_INT_38
273 if (bits == 38)
return true;
275 #ifdef ENABLE_FIELD_INT_39
276 if (bits == 39)
return true;
278 #ifdef ENABLE_FIELD_INT_40
279 if (bits == 40)
return true;
281 #ifdef ENABLE_FIELD_INT_41
282 if (bits == 41)
return true;
284 #ifdef ENABLE_FIELD_INT_42
285 if (bits == 42)
return true;
287 #ifdef ENABLE_FIELD_INT_43
288 if (bits == 43)
return true;
290 #ifdef ENABLE_FIELD_INT_44
291 if (bits == 44)
return true;
293 #ifdef ENABLE_FIELD_INT_45
294 if (bits == 45)
return true;
296 #ifdef ENABLE_FIELD_INT_46
297 if (bits == 46)
return true;
299 #ifdef ENABLE_FIELD_INT_47
300 if (bits == 47)
return true;
302 #ifdef ENABLE_FIELD_INT_48
303 if (bits == 48)
return true;
305 #ifdef ENABLE_FIELD_INT_49
306 if (bits == 49)
return true;
308 #ifdef ENABLE_FIELD_INT_50
309 if (bits == 50)
return true;
311 #ifdef ENABLE_FIELD_INT_51
312 if (bits == 51)
return true;
314 #ifdef ENABLE_FIELD_INT_52
315 if (bits == 52)
return true;
317 #ifdef ENABLE_FIELD_INT_53
318 if (bits == 53)
return true;
320 #ifdef ENABLE_FIELD_INT_54
321 if (bits == 54)
return true;
323 #ifdef ENABLE_FIELD_INT_55
324 if (bits == 55)
return true;
326 #ifdef ENABLE_FIELD_INT_56
327 if (bits == 56)
return true;
329 #ifdef ENABLE_FIELD_INT_57
330 if (bits == 57)
return true;
332 #ifdef ENABLE_FIELD_INT_58
333 if (bits == 58)
return true;
335 #ifdef ENABLE_FIELD_INT_59
336 if (bits == 59)
return true;
338 #ifdef ENABLE_FIELD_INT_60
339 if (bits == 60)
return true;
341 #ifdef ENABLE_FIELD_INT_61
342 if (bits == 61)
return true;
344 #ifdef ENABLE_FIELD_INT_62
345 if (bits == 62)
return true;
347 #ifdef ENABLE_FIELD_INT_63
348 if (bits == 63)
return true;
350 #ifdef ENABLE_FIELD_INT_64
351 if (bits == 64)
return true;
369 Sketch* sketch = Construct(bits, implementation);
374 }
catch (
const std::bad_alloc&) {}
380 Sketch* sketch = Construct(bits, implementation);
383 sketch->
Init(capacity);
384 }
catch (
const std::bad_alloc&) {
391 }
catch (
const std::bad_alloc&) {
435 size_t bits = s->
Bits();
437 return (bits * syndromes + 7) / 8;
463 if (s1->
Bits() != s2->
Bits())
return 0;
465 return s1->
Merge(s2);
471 return s->
Decode(max_elements, output);
481 return ComputeCapacity(bits, max_elements, fpbits);
485 return ComputeMaxElements(bits, capacity, fpbits);
Abstract class for internal representation of a minisketch object.
virtual void Serialize(unsigned char *) const =0
int Implementation() const
virtual size_t Merge(const Sketch *other_sketch)=0
virtual void Init(int syndromes)=0
virtual void SetSeed(uint64_t seed)=0
virtual size_t Syndromes() const =0
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)
Sketch * ConstructClMulTri1Byte(int bits, int implementation)
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.
ssize_t minisketch_decode(const minisketch *sketch, size_t max_elements, uint64_t *output)
Decode a sketch.
void minisketch_destroy(minisketch *sketch)
Destroy a sketch.
uint32_t minisketch_bits(const minisketch *sketch)
Get the element size of a sketch in bits.
uint32_t minisketch_implementation_max()
Determine the maximum number of implementations available.
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.
minisketch * minisketch_clone(const minisketch *sketch)
Clone a sketch.
uint32_t minisketch_implementation(const minisketch *sketch)
Get the implementation of a sketch.
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.
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.
size_t minisketch_merge(minisketch *sketch, const minisketch *other_sketch)
Merge the elements of another sketch into this sketch.
void minisketch_serialize(const minisketch *sketch, unsigned char *output)
Serialize a sketch to bytes.
size_t minisketch_capacity(const minisketch *sketch)
Get the capacity of a sketch.
Sketch * ConstructGeneric2Bytes(int bits, int implementation)
size_t minisketch_serialized_size(const minisketch *sketch)
Compute the size in bytes for serializing a given sketch.
void minisketch_set_seed(minisketch *sketch, uint64_t seed)
Set the seed for randomizing algorithm choices to a fixed value.
minisketch * minisketch_create(uint32_t bits, uint32_t implementation, size_t capacity)
Construct a sketch for a given element size, implementation and capacity.
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.
Sketch * ConstructGeneric6Bytes(int bits, int implementation)
int minisketch_bits_supported(uint32_t bits)
Determine whether support for elements of bits bits was compiled in.
struct minisketch minisketch
Opaque type for decoded sketches.