client/deps/hardnested/hardnested_bitarray_core.c

   1 //-----------------------------------------------------------------------------
   2 // Copyright (C) 2016, 2017 by piwi
   3 //
   4 // This code is licensed to you under the terms of the GNU GPL, version 2 or,
   5 // at your option, any later version. See the LICENSE.txt file for the text of
   6 // the license.ch b
   7 //-----------------------------------------------------------------------------
   8 // Implements a card only attack based on crypto text (encrypted nonces
   9 // received during a nested authentication) only. Unlike other card only
  10 // attacks this doesn't rely on implementation errors but only on the
  11 // inherent weaknesses of the crypto1 cypher. Described in
  12 //   Carlo Meijer, Roel Verdult, "Ciphertext-only Cryptanalysis on Hardened
  13 //   Mifare Classic Cards" in Proceedings of the 22nd ACM SIGSAC Conference on
  14 //   Computer and Communications Security, 2015
  15 //-----------------------------------------------------------------------------
  16 // some helper functions which can benefit from SIMD instructions or other special instructions
  17 //
  18
  19 #include "hardnested_bitarray_core.h"
  20 #include "hardnested_bf_core.h"
  21
  22 #include <stdint.h>
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #ifndef __APPLE__
  26 #include <malloc.h>
  27 #endif
  28
  29 // this needs to be compiled several times for each instruction set.
  30 // For each instruction set, define a dedicated function name:
  31 #if defined (__AVX512F__)
  32 #define MALLOC_BITARRAY malloc_bitarray_AVX512
  33 #define FREE_BITARRAY free_bitarray_AVX512
  34 #define BITCOUNT bitcount_AVX512
  35 #define COUNT_STATES count_states_AVX512
  36 #define BITARRAY_AND bitarray_AND_AVX512
  37 #define BITARRAY_LOW20_AND bitarray_low20_AND_AVX512
  38 #define COUNT_BITARRAY_AND count_bitarray_AND_AVX512
  39 #define COUNT_BITARRAY_LOW20_AND count_bitarray_low20_AND_AVX512
  40 #define BITARRAY_AND4 bitarray_AND4_AVX512
  41 #define BITARRAY_OR bitarray_OR_AVX512
  42 #define COUNT_BITARRAY_AND2 count_bitarray_AND2_AVX512
  43 #define COUNT_BITARRAY_AND3 count_bitarray_AND3_AVX512
  44 #define COUNT_BITARRAY_AND4 count_bitarray_AND4_AVX512
  45 #elif defined (__AVX2__)
  46 #define MALLOC_BITARRAY malloc_bitarray_AVX2
  47 #define FREE_BITARRAY free_bitarray_AVX2
  48 #define BITCOUNT bitcount_AVX2
  49 #define COUNT_STATES count_states_AVX2
  50 #define BITARRAY_AND bitarray_AND_AVX2
  51 #define BITARRAY_LOW20_AND bitarray_low20_AND_AVX2
  52 #define COUNT_BITARRAY_AND count_bitarray_AND_AVX2
  53 #define COUNT_BITARRAY_LOW20_AND count_bitarray_low20_AND_AVX2
  54 #define BITARRAY_AND4 bitarray_AND4_AVX2
  55 #define BITARRAY_OR bitarray_OR_AVX2
  56 #define COUNT_BITARRAY_AND2 count_bitarray_AND2_AVX2
  57 #define COUNT_BITARRAY_AND3 count_bitarray_AND3_AVX2
  58 #define COUNT_BITARRAY_AND4 count_bitarray_AND4_AVX2
  59 #elif defined (__AVX__)
  60 #define MALLOC_BITARRAY malloc_bitarray_AVX
  61 #define FREE_BITARRAY free_bitarray_AVX
  62 #define BITCOUNT bitcount_AVX
  63 #define COUNT_STATES count_states_AVX
  64 #define BITARRAY_AND bitarray_AND_AVX
  65 #define BITARRAY_LOW20_AND bitarray_low20_AND_AVX
  66 #define COUNT_BITARRAY_AND count_bitarray_AND_AVX
  67 #define COUNT_BITARRAY_LOW20_AND count_bitarray_low20_AND_AVX
  68 #define BITARRAY_AND4 bitarray_AND4_AVX
  69 #define BITARRAY_OR bitarray_OR_AVX
  70 #define COUNT_BITARRAY_AND2 count_bitarray_AND2_AVX
  71 #define COUNT_BITARRAY_AND3 count_bitarray_AND3_AVX
  72 #define COUNT_BITARRAY_AND4 count_bitarray_AND4_AVX
  73 #elif defined (__SSE2__)
  74 #define MALLOC_BITARRAY malloc_bitarray_SSE2
  75 #define FREE_BITARRAY free_bitarray_SSE2
  76 #define BITCOUNT bitcount_SSE2
  77 #define COUNT_STATES count_states_SSE2
  78 #define BITARRAY_AND bitarray_AND_SSE2
  79 #define BITARRAY_LOW20_AND bitarray_low20_AND_SSE2
  80 #define COUNT_BITARRAY_AND count_bitarray_AND_SSE2
  81 #define COUNT_BITARRAY_LOW20_AND count_bitarray_low20_AND_SSE2
  82 #define BITARRAY_AND4 bitarray_AND4_SSE2
  83 #define BITARRAY_OR bitarray_OR_SSE2
  84 #define COUNT_BITARRAY_AND2 count_bitarray_AND2_SSE2
  85 #define COUNT_BITARRAY_AND3 count_bitarray_AND3_SSE2
  86 #define COUNT_BITARRAY_AND4 count_bitarray_AND4_SSE2
  87 #elif defined (__MMX__)
  88 #define MALLOC_BITARRAY malloc_bitarray_MMX
  89 #define FREE_BITARRAY free_bitarray_MMX
  90 #define BITCOUNT bitcount_MMX
  91 #define COUNT_STATES count_states_MMX
  92 #define BITARRAY_AND bitarray_AND_MMX
  93 #define BITARRAY_LOW20_AND bitarray_low20_AND_MMX
  94 #define COUNT_BITARRAY_AND count_bitarray_AND_MMX
  95 #define COUNT_BITARRAY_LOW20_AND count_bitarray_low20_AND_MMX
  96 #define BITARRAY_AND4 bitarray_AND4_MMX
  97 #define BITARRAY_OR bitarray_OR_MMX
  98 #define COUNT_BITARRAY_AND2 count_bitarray_AND2_MMX
  99 #define COUNT_BITARRAY_AND3 count_bitarray_AND3_MMX
 100 #define COUNT_BITARRAY_AND4 count_bitarray_AND4_MMX
 101 #else
 102 #define MALLOC_BITARRAY malloc_bitarray_NOSIMD
 103 #define FREE_BITARRAY free_bitarray_NOSIMD
 104 #define BITCOUNT bitcount_NOSIMD
 105 #define COUNT_STATES count_states_NOSIMD
 106 #define BITARRAY_AND bitarray_AND_NOSIMD
 107 #define BITARRAY_LOW20_AND bitarray_low20_AND_NOSIMD
 108 #define COUNT_BITARRAY_AND count_bitarray_AND_NOSIMD
 109 #define COUNT_BITARRAY_LOW20_AND count_bitarray_low20_AND_NOSIMD
 110 #define BITARRAY_AND4 bitarray_AND4_NOSIMD
 111 #define BITARRAY_OR bitarray_OR_NOSIMD
 112 #define COUNT_BITARRAY_AND2 count_bitarray_AND2_NOSIMD
 113 #define COUNT_BITARRAY_AND3 count_bitarray_AND3_NOSIMD
 114 #define COUNT_BITARRAY_AND4 count_bitarray_AND4_NOSIMD
 115 #endif
 116
 117
 118 // typedefs and declaration of functions:
 119 typedef uint32_t *malloc_bitarray_t(uint32_t);
 120 malloc_bitarray_t malloc_bitarray_AVX512, malloc_bitarray_AVX2, malloc_bitarray_AVX, malloc_bitarray_SSE2, malloc_bitarray_MMX, malloc_bitarray_NOSIMD, malloc_bitarray_dispatch;
 121 typedef void free_bitarray_t(uint32_t *);
 122 free_bitarray_t free_bitarray_AVX512, free_bitarray_AVX2, free_bitarray_AVX, free_bitarray_SSE2, free_bitarray_MMX, free_bitarray_NOSIMD, free_bitarray_dispatch;
 123 typedef uint32_t bitcount_t(uint32_t);
 124 bitcount_t bitcount_AVX512, bitcount_AVX2, bitcount_AVX, bitcount_SSE2, bitcount_MMX, bitcount_NOSIMD, bitcount_dispatch;
 125 typedef uint32_t count_states_t(uint32_t *);
 126 count_states_t count_states_AVX512, count_states_AVX2, count_states_AVX, count_states_SSE2, count_states_MMX, count_states_NOSIMD, count_states_dispatch;
 127 typedef void bitarray_AND_t(uint32_t[], uint32_t[]);
 128 bitarray_AND_t bitarray_AND_AVX512, bitarray_AND_AVX2, bitarray_AND_AVX, bitarray_AND_SSE2, bitarray_AND_MMX, bitarray_AND_NOSIMD, bitarray_AND_dispatch;
 129 typedef void bitarray_low20_AND_t(uint32_t *, uint32_t *);
 130 bitarray_low20_AND_t bitarray_low20_AND_AVX512, bitarray_low20_AND_AVX2, bitarray_low20_AND_AVX, bitarray_low20_AND_SSE2, bitarray_low20_AND_MMX, bitarray_low20_AND_NOSIMD, bitarray_low20_AND_dispatch;
 131 typedef uint32_t count_bitarray_AND_t(uint32_t *, uint32_t *);
 132 count_bitarray_AND_t count_bitarray_AND_AVX512, count_bitarray_AND_AVX2, count_bitarray_AND_AVX, count_bitarray_AND_SSE2, count_bitarray_AND_MMX, count_bitarray_AND_NOSIMD, count_bitarray_AND_dispatch;
 133 typedef uint32_t count_bitarray_low20_AND_t(uint32_t *, uint32_t *);
 134 count_bitarray_low20_AND_t count_bitarray_low20_AND_AVX512, count_bitarray_low20_AND_AVX2, count_bitarray_low20_AND_AVX, count_bitarray_low20_AND_SSE2, count_bitarray_low20_AND_MMX, count_bitarray_low20_AND_NOSIMD, count_bitarray_low20_AND_dispatch;
 135 typedef void bitarray_AND4_t(uint32_t *, uint32_t *, uint32_t *, uint32_t *);
 136 bitarray_AND4_t bitarray_AND4_AVX512, bitarray_AND4_AVX2, bitarray_AND4_AVX, bitarray_AND4_SSE2, bitarray_AND4_MMX, bitarray_AND4_NOSIMD, bitarray_AND4_dispatch;
 137 typedef void bitarray_OR_t(uint32_t[], uint32_t[]);
 138 bitarray_OR_t bitarray_OR_AVX512, bitarray_OR_AVX2, bitarray_OR_AVX, bitarray_OR_SSE2, bitarray_OR_MMX, bitarray_OR_NOSIMD, bitarray_OR_dispatch;
 139 typedef uint32_t count_bitarray_AND2_t(uint32_t *, uint32_t *);
 140 count_bitarray_AND2_t count_bitarray_AND2_AVX512, count_bitarray_AND2_AVX2, count_bitarray_AND2_AVX, count_bitarray_AND2_SSE2, count_bitarray_AND2_MMX, count_bitarray_AND2_NOSIMD, count_bitarray_AND2_dispatch;
 141 typedef uint32_t count_bitarray_AND3_t(uint32_t *, uint32_t *, uint32_t *);
 142 count_bitarray_AND3_t count_bitarray_AND3_AVX512, count_bitarray_AND3_AVX2, count_bitarray_AND3_AVX, count_bitarray_AND3_SSE2, count_bitarray_AND3_MMX, count_bitarray_AND3_NOSIMD, count_bitarray_AND3_dispatch;
 143 typedef uint32_t count_bitarray_AND4_t(uint32_t *, uint32_t *, uint32_t *, uint32_t *);
 144 count_bitarray_AND4_t count_bitarray_AND4_AVX512, count_bitarray_AND4_AVX2, count_bitarray_AND4_AVX, count_bitarray_AND4_SSE2, count_bitarray_AND4_MMX, count_bitarray_AND4_NOSIMD, count_bitarray_AND4_dispatch;
 145
 146
 147 inline uint32_t *MALLOC_BITARRAY(uint32_t x) {
 148 #if defined (_WIN32)
 149     return __builtin_assume_aligned(_aligned_malloc((x), __BIGGEST_ALIGNMENT__), __BIGGEST_ALIGNMENT__);
 150 #elif defined (__APPLE__)
 151     uint32_t *allocated_memory;
 152     if (posix_memalign((void **)&allocated_memory, __BIGGEST_ALIGNMENT__, x)) {
 153         return NULL;
 154     } else {
 155         return __builtin_assume_aligned(allocated_memory, __BIGGEST_ALIGNMENT__);
 156     }
 157 #else
 158     return __builtin_assume_aligned(memalign(__BIGGEST_ALIGNMENT__, (x)), __BIGGEST_ALIGNMENT__);
 159 #endif
 160 }
 161
 162
 163 inline void FREE_BITARRAY(uint32_t *x) {
 164 #ifdef _WIN32
 165     _aligned_free(x);
 166 #else
 167     free(x);
 168 #endif
 169 }
 170
 171
 172 inline uint32_t BITCOUNT(uint32_t a) {
 173     return __builtin_popcountl(a);
 174 }
 175
 176
 177 inline uint32_t COUNT_STATES(uint32_t *A) {
 178     uint32_t count = 0;
 179     for (uint32_t i = 0; i < (1 << 19); i++) {
 180         count += BITCOUNT(A[i]);
 181     }
 182     return count;
 183 }
 184
 185
 186 inline void BITARRAY_AND(uint32_t *restrict A, uint32_t *restrict B) {
 187     A = __builtin_assume_aligned(A, __BIGGEST_ALIGNMENT__);
 188     B = __builtin_assume_aligned(B, __BIGGEST_ALIGNMENT__);
 189     for (uint32_t i = 0; i < (1 << 19); i++) {
 190         A[i] &= B[i];
 191     }
 192 }
 193
 194
 195 inline void BITARRAY_LOW20_AND(uint32_t *restrict A, uint32_t *restrict B) {
 196     uint16_t *a = (uint16_t *)__builtin_assume_aligned(A, __BIGGEST_ALIGNMENT__);
 197     uint16_t *b = (uint16_t *)__builtin_assume_aligned(B, __BIGGEST_ALIGNMENT__);
 198
 199     for (uint32_t i = 0; i < (1 << 20); i++) {
 200         if (!b[i]) {
 201             a[i] = 0;
 202         }
 203     }
 204 }
 205
 206
 207 inline uint32_t COUNT_BITARRAY_AND(uint32_t *restrict A, uint32_t *restrict B) {
 208     A = __builtin_assume_aligned(A, __BIGGEST_ALIGNMENT__);
 209     B = __builtin_assume_aligned(B, __BIGGEST_ALIGNMENT__);
 210     uint32_t count = 0;
 211     for (uint32_t i = 0; i < (1 << 19); i++) {
 212         A[i] &= B[i];
 213         count += BITCOUNT(A[i]);
 214     }
 215     return count;
 216 }
 217
 218
 219 inline uint32_t COUNT_BITARRAY_LOW20_AND(uint32_t *restrict A, uint32_t *restrict B) {
 220     uint16_t *a = (uint16_t *)__builtin_assume_aligned(A, __BIGGEST_ALIGNMENT__);
 221     uint16_t *b = (uint16_t *)__builtin_assume_aligned(B, __BIGGEST_ALIGNMENT__);
 222     uint32_t count = 0;
 223
 224     for (uint32_t i = 0; i < (1 << 20); i++) {
 225         if (!b[i]) {
 226             a[i] = 0;
 227         }
 228         count += BITCOUNT(a[i]);
 229     }
 230     return count;
 231 }
 232
 233
 234 inline void BITARRAY_AND4(uint32_t *restrict A, uint32_t *restrict B, uint32_t *restrict C, uint32_t *restrict D) {
 235     A = __builtin_assume_aligned(A, __BIGGEST_ALIGNMENT__);
 236     B = __builtin_assume_aligned(B, __BIGGEST_ALIGNMENT__);
 237     C = __builtin_assume_aligned(C, __BIGGEST_ALIGNMENT__);
 238     D = __builtin_assume_aligned(D, __BIGGEST_ALIGNMENT__);
 239     for (uint32_t i = 0; i < (1 << 19); i++) {
 240         A[i] = B[i] & C[i] & D[i];
 241     }
 242 }
 243
 244
 245 inline void BITARRAY_OR(uint32_t *restrict A, uint32_t *restrict B) {
 246     A = __builtin_assume_aligned(A, __BIGGEST_ALIGNMENT__);
 247     B = __builtin_assume_aligned(B, __BIGGEST_ALIGNMENT__);
 248     for (uint32_t i = 0; i < (1 << 19); i++) {
 249         A[i] |= B[i];
 250     }
 251 }
 252
 253
 254 inline uint32_t COUNT_BITARRAY_AND2(uint32_t *restrict A, uint32_t *restrict B) {
 255     A = __builtin_assume_aligned(A, __BIGGEST_ALIGNMENT__);
 256     B = __builtin_assume_aligned(B, __BIGGEST_ALIGNMENT__);
 257     uint32_t count = 0;
 258     for (uint32_t i = 0; i < (1 << 19); i++) {
 259         count += BITCOUNT(A[i] & B[i]);
 260     }
 261     return count;
 262 }
 263
 264
 265 inline uint32_t COUNT_BITARRAY_AND3(uint32_t *restrict A, uint32_t *restrict B, uint32_t *restrict C) {
 266     A = __builtin_assume_aligned(A, __BIGGEST_ALIGNMENT__);
 267     B = __builtin_assume_aligned(B, __BIGGEST_ALIGNMENT__);
 268     C = __builtin_assume_aligned(C, __BIGGEST_ALIGNMENT__);
 269     uint32_t count = 0;
 270     for (uint32_t i = 0; i < (1 << 19); i++) {
 271         count += BITCOUNT(A[i] & B[i] & C[i]);
 272     }
 273     return count;
 274 }
 275
 276
 277 inline uint32_t COUNT_BITARRAY_AND4(uint32_t *restrict A, uint32_t *restrict B, uint32_t *restrict C, uint32_t *restrict D) {
 278     A = __builtin_assume_aligned(A, __BIGGEST_ALIGNMENT__);
 279     B = __builtin_assume_aligned(B, __BIGGEST_ALIGNMENT__);
 280     C = __builtin_assume_aligned(C, __BIGGEST_ALIGNMENT__);
 281     D = __builtin_assume_aligned(D, __BIGGEST_ALIGNMENT__);
 282     uint32_t count = 0;
 283     for (uint32_t i = 0; i < (1 << 19); i++) {
 284         count += BITCOUNT(A[i] & B[i] & C[i] & D[i]);
 285     }
 286     return count;
 287 }
 288
 289
 290 #ifndef __MMX__
 291
 292 // pointers to functions:
 293 malloc_bitarray_t *malloc_bitarray_function_p = &malloc_bitarray_dispatch;
 294 free_bitarray_t *free_bitarray_function_p = &free_bitarray_dispatch;
 295 bitcount_t *bitcount_function_p = &bitcount_dispatch;
 296 count_states_t *count_states_function_p = &count_states_dispatch;
 297 bitarray_AND_t *bitarray_AND_function_p = &bitarray_AND_dispatch;
 298 bitarray_low20_AND_t *bitarray_low20_AND_function_p = &bitarray_low20_AND_dispatch;
 299 count_bitarray_AND_t *count_bitarray_AND_function_p = &count_bitarray_AND_dispatch;
 300 count_bitarray_low20_AND_t *count_bitarray_low20_AND_function_p = &count_bitarray_low20_AND_dispatch;
 301 bitarray_AND4_t *bitarray_AND4_function_p = &bitarray_AND4_dispatch;
 302 bitarray_OR_t *bitarray_OR_function_p = &bitarray_OR_dispatch;
 303 count_bitarray_AND2_t *count_bitarray_AND2_function_p = &count_bitarray_AND2_dispatch;
 304 count_bitarray_AND3_t *count_bitarray_AND3_function_p = &count_bitarray_AND3_dispatch;
 305 count_bitarray_AND4_t *count_bitarray_AND4_function_p = &count_bitarray_AND4_dispatch;
 306
 307 // determine the available instruction set at runtime and call the correct function
 308 uint32_t *malloc_bitarray_dispatch(uint32_t x) {
 309 #if defined(COMPILER_HAS_SIMD_AVX512)
 310     if (__builtin_cpu_supports("avx512f")) malloc_bitarray_function_p = &malloc_bitarray_AVX512;
 311     else
 312 #endif
 313 #if defined(COMPILER_HAS_SIMD)
 314         if (__builtin_cpu_supports("avx2")) malloc_bitarray_function_p = &malloc_bitarray_AVX2;
 315         else if (__builtin_cpu_supports("avx")) malloc_bitarray_function_p = &malloc_bitarray_AVX;
 316         else if (__builtin_cpu_supports("sse2")) malloc_bitarray_function_p = &malloc_bitarray_SSE2;
 317         else if (__builtin_cpu_supports("mmx")) malloc_bitarray_function_p = &malloc_bitarray_MMX;
 318         else
 319 #endif
 320             malloc_bitarray_function_p = &malloc_bitarray_NOSIMD;
 321
 322     // call the most optimized function for this CPU
 323     return (*malloc_bitarray_function_p)(x);
 324 }
 325
 326 void free_bitarray_dispatch(uint32_t *x) {
 327 #if defined(COMPILER_HAS_SIMD_AVX512)
 328     if (__builtin_cpu_supports("avx512f")) free_bitarray_function_p = &free_bitarray_AVX512;
 329     else
 330 #endif
 331 #if defined(COMPILER_HAS_SIMD)
 332         if (__builtin_cpu_supports("avx2")) free_bitarray_function_p = &free_bitarray_AVX2;
 333         else if (__builtin_cpu_supports("avx")) free_bitarray_function_p = &free_bitarray_AVX;
 334         else if (__builtin_cpu_supports("sse2")) free_bitarray_function_p = &free_bitarray_SSE2;
 335         else if (__builtin_cpu_supports("mmx")) free_bitarray_function_p = &free_bitarray_MMX;
 336         else
 337 #endif
 338             free_bitarray_function_p = &free_bitarray_NOSIMD;
 339
 340     // call the most optimized function for this CPU
 341     (*free_bitarray_function_p)(x);
 342 }
 343
 344 uint32_t bitcount_dispatch(uint32_t a) {
 345 #if defined(COMPILER_HAS_SIMD_AVX512)
 346     if (__builtin_cpu_supports("avx512f")) bitcount_function_p = &bitcount_AVX512;
 347     else
 348 #endif
 349 #if defined(COMPILER_HAS_SIMD)
 350         if (__builtin_cpu_supports("avx2")) bitcount_function_p = &bitcount_AVX2;
 351         else if (__builtin_cpu_supports("avx")) bitcount_function_p = &bitcount_AVX;
 352         else if (__builtin_cpu_supports("sse2")) bitcount_function_p = &bitcount_SSE2;
 353         else if (__builtin_cpu_supports("mmx")) bitcount_function_p = &bitcount_MMX;
 354         else
 355 #endif
 356             bitcount_function_p = &bitcount_NOSIMD;
 357
 358     // call the most optimized function for this CPU
 359     return (*bitcount_function_p)(a);
 360 }
 361
 362 uint32_t count_states_dispatch(uint32_t *bitarray) {
 363 #if defined(COMPILER_HAS_SIMD_AVX512)
 364     if (__builtin_cpu_supports("avx512f")) count_states_function_p = &count_states_AVX512;
 365     else
 366 #endif
 367 #if defined(COMPILER_HAS_SIMD)
 368         if (__builtin_cpu_supports("avx2")) count_states_function_p = &count_states_AVX2;
 369         else if (__builtin_cpu_supports("avx")) count_states_function_p = &count_states_AVX;
 370         else if (__builtin_cpu_supports("sse2")) count_states_function_p = &count_states_SSE2;
 371         else if (__builtin_cpu_supports("mmx")) count_states_function_p = &count_states_MMX;
 372         else
 373 #endif
 374             count_states_function_p = &count_states_NOSIMD;
 375
 376     // call the most optimized function for this CPU
 377     return (*count_states_function_p)(bitarray);
 378 }
 379
 380 void bitarray_AND_dispatch(uint32_t *A, uint32_t *B) {
 381 #if defined(COMPILER_HAS_SIMD_AVX512)
 382     if (__builtin_cpu_supports("avx512f")) bitarray_AND_function_p = &bitarray_AND_AVX512;
 383     else
 384 #endif
 385 #if defined(COMPILER_HAS_SIMD)
 386         if (__builtin_cpu_supports("avx2")) bitarray_AND_function_p = &bitarray_AND_AVX2;
 387         else if (__builtin_cpu_supports("avx")) bitarray_AND_function_p = &bitarray_AND_AVX;
 388         else if (__builtin_cpu_supports("sse2")) bitarray_AND_function_p = &bitarray_AND_SSE2;
 389         else if (__builtin_cpu_supports("mmx")) bitarray_AND_function_p = &bitarray_AND_MMX;
 390         else
 391 #endif
 392             bitarray_AND_function_p = &bitarray_AND_NOSIMD;
 393
 394     // call the most optimized function for this CPU
 395     (*bitarray_AND_function_p)(A, B);
 396 }
 397
 398 void bitarray_low20_AND_dispatch(uint32_t *A, uint32_t *B) {
 399 #if defined(COMPILER_HAS_SIMD_AVX512)
 400     if (__builtin_cpu_supports("avx512f")) bitarray_low20_AND_function_p = &bitarray_low20_AND_AVX512;
 401     else
 402 #endif
 403 #if defined(COMPILER_HAS_SIMD)
 404         if (__builtin_cpu_supports("avx2")) bitarray_low20_AND_function_p = &bitarray_low20_AND_AVX2;
 405         else if (__builtin_cpu_supports("avx")) bitarray_low20_AND_function_p = &bitarray_low20_AND_AVX;
 406         else if (__builtin_cpu_supports("sse2")) bitarray_low20_AND_function_p = &bitarray_low20_AND_SSE2;
 407         else if (__builtin_cpu_supports("mmx")) bitarray_low20_AND_function_p = &bitarray_low20_AND_MMX;
 408         else
 409 #endif
 410             bitarray_low20_AND_function_p = &bitarray_low20_AND_NOSIMD;
 411
 412     // call the most optimized function for this CPU
 413     (*bitarray_low20_AND_function_p)(A, B);
 414 }
 415
 416 uint32_t count_bitarray_AND_dispatch(uint32_t *A, uint32_t *B) {
 417 #if defined(COMPILER_HAS_SIMD_AVX512)
 418     if (__builtin_cpu_supports("avx512f")) count_bitarray_AND_function_p = &count_bitarray_AND_AVX512;
 419     else
 420 #endif
 421 #if defined(COMPILER_HAS_SIMD)
 422         if (__builtin_cpu_supports("avx2")) count_bitarray_AND_function_p = &count_bitarray_AND_AVX2;
 423         else if (__builtin_cpu_supports("avx")) count_bitarray_AND_function_p = &count_bitarray_AND_AVX;
 424         else if (__builtin_cpu_supports("sse2")) count_bitarray_AND_function_p = &count_bitarray_AND_SSE2;
 425         else if (__builtin_cpu_supports("mmx")) count_bitarray_AND_function_p = &count_bitarray_AND_MMX;
 426         else
 427 #endif
 428             count_bitarray_AND_function_p = &count_bitarray_AND_NOSIMD;
 429
 430     // call the most optimized function for this CPU
 431     return (*count_bitarray_AND_function_p)(A, B);
 432 }
 433
 434 uint32_t count_bitarray_low20_AND_dispatch(uint32_t *A, uint32_t *B) {
 435 #if defined(COMPILER_HAS_SIMD_AVX512)
 436     if (__builtin_cpu_supports("avx512f")) count_bitarray_low20_AND_function_p = &count_bitarray_low20_AND_AVX512;
 437     else
 438 #endif
 439 #if defined(COMPILER_HAS_SIMD)
 440         if (__builtin_cpu_supports("avx2")) count_bitarray_low20_AND_function_p = &count_bitarray_low20_AND_AVX2;
 441         else if (__builtin_cpu_supports("avx")) count_bitarray_low20_AND_function_p = &count_bitarray_low20_AND_AVX;
 442         else if (__builtin_cpu_supports("sse2")) count_bitarray_low20_AND_function_p = &count_bitarray_low20_AND_SSE2;
 443         else if (__builtin_cpu_supports("mmx")) count_bitarray_low20_AND_function_p = &count_bitarray_low20_AND_MMX;
 444         else
 445 #endif
 446             count_bitarray_low20_AND_function_p = &count_bitarray_low20_AND_NOSIMD;
 447
 448     // call the most optimized function for this CPU
 449     return (*count_bitarray_low20_AND_function_p)(A, B);
 450 }
 451
 452 void bitarray_AND4_dispatch(uint32_t *A, uint32_t *B, uint32_t *C, uint32_t *D) {
 453 #if defined(COMPILER_HAS_SIMD_AVX512)
 454     if (__builtin_cpu_supports("avx512f")) bitarray_AND4_function_p = &bitarray_AND4_AVX512;
 455     else
 456 #endif
 457 #if defined(COMPILER_HAS_SIMD)
 458         if (__builtin_cpu_supports("avx2")) bitarray_AND4_function_p = &bitarray_AND4_AVX2;
 459         else if (__builtin_cpu_supports("avx")) bitarray_AND4_function_p = &bitarray_AND4_AVX;
 460         else if (__builtin_cpu_supports("sse2")) bitarray_AND4_function_p = &bitarray_AND4_SSE2;
 461         else if (__builtin_cpu_supports("mmx")) bitarray_AND4_function_p = &bitarray_AND4_MMX;
 462         else
 463 #endif
 464             bitarray_AND4_function_p = &bitarray_AND4_NOSIMD;
 465
 466     // call the most optimized function for this CPU
 467     (*bitarray_AND4_function_p)(A, B, C, D);
 468 }
 469
 470 void bitarray_OR_dispatch(uint32_t *A, uint32_t *B) {
 471 #if defined(COMPILER_HAS_SIMD_AVX512)
 472     if (__builtin_cpu_supports("avx512f")) bitarray_OR_function_p = &bitarray_OR_AVX512;
 473     else
 474 #endif
 475 #if defined(COMPILER_HAS_SIMD)
 476         if (__builtin_cpu_supports("avx2")) bitarray_OR_function_p = &bitarray_OR_AVX2;
 477         else if (__builtin_cpu_supports("avx")) bitarray_OR_function_p = &bitarray_OR_AVX;
 478         else if (__builtin_cpu_supports("sse2")) bitarray_OR_function_p = &bitarray_OR_SSE2;
 479         else if (__builtin_cpu_supports("mmx")) bitarray_OR_function_p = &bitarray_OR_MMX;
 480         else
 481 #endif
 482             bitarray_OR_function_p = &bitarray_OR_NOSIMD;
 483
 484     // call the most optimized function for this CPU
 485     (*bitarray_OR_function_p)(A, B);
 486 }
 487
 488 uint32_t count_bitarray_AND2_dispatch(uint32_t *A, uint32_t *B) {
 489 #if defined(COMPILER_HAS_SIMD_AVX512)
 490     if (__builtin_cpu_supports("avx512f")) count_bitarray_AND2_function_p = &count_bitarray_AND2_AVX512;
 491     else
 492 #endif
 493 #if defined(COMPILER_HAS_SIMD)
 494         if (__builtin_cpu_supports("avx2")) count_bitarray_AND2_function_p = &count_bitarray_AND2_AVX2;
 495         else if (__builtin_cpu_supports("avx")) count_bitarray_AND2_function_p = &count_bitarray_AND2_AVX;
 496         else if (__builtin_cpu_supports("sse2")) count_bitarray_AND2_function_p = &count_bitarray_AND2_SSE2;
 497         else if (__builtin_cpu_supports("mmx")) count_bitarray_AND2_function_p = &count_bitarray_AND2_MMX;
 498         else
 499 #endif
 500             count_bitarray_AND2_function_p = &count_bitarray_AND2_NOSIMD;
 501
 502     // call the most optimized function for this CPU
 503     return (*count_bitarray_AND2_function_p)(A, B);
 504 }
 505
 506 uint32_t count_bitarray_AND3_dispatch(uint32_t *A, uint32_t *B, uint32_t *C) {
 507 #if defined(COMPILER_HAS_SIMD_AVX512)
 508     if (__builtin_cpu_supports("avx512f")) count_bitarray_AND3_function_p = &count_bitarray_AND3_AVX512;
 509     else
 510 #endif
 511 #if defined(COMPILER_HAS_SIMD)
 512         if (__builtin_cpu_supports("avx2")) count_bitarray_AND3_function_p = &count_bitarray_AND3_AVX2;
 513         else if (__builtin_cpu_supports("avx")) count_bitarray_AND3_function_p = &count_bitarray_AND3_AVX;
 514         else if (__builtin_cpu_supports("sse2")) count_bitarray_AND3_function_p = &count_bitarray_AND3_SSE2;
 515         else if (__builtin_cpu_supports("mmx")) count_bitarray_AND3_function_p = &count_bitarray_AND3_MMX;
 516         else
 517 #endif
 518             count_bitarray_AND3_function_p = &count_bitarray_AND3_NOSIMD;
 519
 520     // call the most optimized function for this CPU
 521     return (*count_bitarray_AND3_function_p)(A, B, C);
 522 }
 523
 524 uint32_t count_bitarray_AND4_dispatch(uint32_t *A, uint32_t *B, uint32_t *C, uint32_t *D) {
 525 #if defined(COMPILER_HAS_SIMD_AVX512)
 526     if (__builtin_cpu_supports("avx512f")) count_bitarray_AND4_function_p = &count_bitarray_AND4_AVX512;
 527     else
 528 #endif
 529 #if defined(COMPILER_HAS_SIMD)
 530         if (__builtin_cpu_supports("avx2")) count_bitarray_AND4_function_p = &count_bitarray_AND4_AVX2;
 531         else if (__builtin_cpu_supports("avx")) count_bitarray_AND4_function_p = &count_bitarray_AND4_AVX;
 532         else if (__builtin_cpu_supports("sse2")) count_bitarray_AND4_function_p = &count_bitarray_AND4_SSE2;
 533         else if (__builtin_cpu_supports("mmx")) count_bitarray_AND4_function_p = &count_bitarray_AND4_MMX;
 534         else
 535 #endif
 536             count_bitarray_AND4_function_p = &count_bitarray_AND4_NOSIMD;
 537
 538     // call the most optimized function for this CPU
 539     return (*count_bitarray_AND4_function_p)(A, B, C, D);
 540 }
 541
 542
 543 ///////////////////////////////////////////////77
 544 // Entries to dispatched function calls
 545
 546 uint32_t *malloc_bitarray(uint32_t x) {
 547     return (*malloc_bitarray_function_p)(x);
 548 }
 549
 550 void free_bitarray(uint32_t *x) {
 551     (*free_bitarray_function_p)(x);
 552 }
 553
 554 uint32_t bitcount(uint32_t a) {
 555     return (*bitcount_function_p)(a);
 556 }
 557
 558 uint32_t count_states(uint32_t *A) {
 559     return (*count_states_function_p)(A);
 560 }
 561
 562 void bitarray_AND(uint32_t *A, uint32_t *B) {
 563     (*bitarray_AND_function_p)(A, B);
 564 }
 565
 566 void bitarray_low20_AND(uint32_t *A, uint32_t *B) {
 567     (*bitarray_low20_AND_function_p)(A, B);
 568 }
 569
 570 uint32_t count_bitarray_AND(uint32_t *A, uint32_t *B) {
 571     return (*count_bitarray_AND_function_p)(A, B);
 572 }
 573
 574 uint32_t count_bitarray_low20_AND(uint32_t *A, uint32_t *B) {
 575     return (*count_bitarray_low20_AND_function_p)(A, B);
 576 }
 577
 578 void bitarray_AND4(uint32_t *A, uint32_t *B, uint32_t *C, uint32_t *D) {
 579     (*bitarray_AND4_function_p)(A, B, C, D);
 580 }
 581
 582 void bitarray_OR(uint32_t *A, uint32_t *B) {
 583     (*bitarray_OR_function_p)(A, B);
 584 }
 585
 586 uint32_t count_bitarray_AND2(uint32_t *A, uint32_t *B) {
 587     return (*count_bitarray_AND2_function_p)(A, B);
 588 }
 589
 590 uint32_t count_bitarray_AND3(uint32_t *A, uint32_t *B, uint32_t *C) {
 591     return (*count_bitarray_AND3_function_p)(A, B, C);
 592 }
 593
 594 uint32_t count_bitarray_AND4(uint32_t *A, uint32_t *B, uint32_t *C, uint32_t *D) {
 595     return (*count_bitarray_AND4_function_p)(A, B, C, D);
 596 }
 597
 598 #endif
 599