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  
356  uint32_t minisketch_implementation_max() {
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  
414  minisketch* 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  
424  void minisketch_destroy(minisketch* sketch) {
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(static_cast<int>(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  }