bl_generator.h - odin-blend2d - Odin bindings to Blend2D

bl_generator.h (22415B)
      1 #include <stdio.h>
      2 #include <stdint.h>
      3 #include <string.h>
      4 
      5 #include <atomic>
      6 #include <algorithm>
      7 #include <cmath>
      8 #include <map>
      9 #include <mutex>
     10 #include <random>
     11 #include <string>
     12 #include <thread>
     13 #include <utility>
     14 #include <vector>
     15 
     16 // This is a stupid hash function finder that maps uint32_t inputs into a set of predefined consecutive IDs.
     17 //
     18 // Why stupid? Because it's a brute force approach and totally anti computer science - there is no theory behind
     19 // this except for trying to find a constant that when multiplied with input generates the least number of
     20 // collisions.
     21 namespace StupidHash {
     22 
     23 // Utility Functions
     24 // =================
     25 
     26 static uint32_t alignUpToPowerOf2(uint32_t n) {
     27   n -= 1;
     28 
     29   n |= n >> 1;
     30   n |= n >> 2;
     31   n |= n >> 4;
     32   n |= n >> 8;
     33   n |= n >> 16;
     34 
     35   return n + 1;
     36 }
     37 
     38 static uint32_t count_trailing_bits(uint32_t n) {
     39   for (uint32_t i = 0; i < 32; i++)
     40     if (n & (1u << i))
     41       return i;
     42   return 32;
     43 }
     44 
     45 static size_t replace_in_string(std::string& str, const std::string& pattern, const std::string& replacement) {
     46   size_t pos = 0;
     47   size_t count = 0;
     48 
     49   for (;;) {
     50     pos = str.find(pattern, pos);
     51     if (pos == std::string::npos)
     52       return count;
     53     str.replace(pos, pattern.length(), replacement);
     54     pos += replacement.length();
     55     count++;
     56   }
     57 }
     58 
     59 static inline uint32_t mul64Op1(uint32_t value, uint32_t adder, uint64_t multiplier, uint32_t shift) noexcept {
     60   return uint32_t(((value + adder) * multiplier) >> shift);
     61 }
     62 
     63 static inline uint32_t mulOp1(uint32_t value, uint32_t multiplier, uint32_t shift) noexcept {
     64   return (value * multiplier) >> shift;
     65 }
     66 
     67 static inline uint32_t mulOp2(uint32_t value, uint32_t multiplier, uint32_t shift) noexcept {
     68   return ((value * multiplier + (13u << shift)) >> shift);
     69 }
     70 
     71 // [Pseudo] Random Number Generator
     72 // ================================
     73 
     74 // A pseudo random number generator based on a paper by Sebastiano Vigna:
     75 //   http://vigna.di.unimi.it/ftp/papers/xorshiftplus.pdf
     76 class Random {
     77 public:
     78   // Constants suggested as `23/18/5`.
     79   enum Steps : uint32_t {
     80     kStep1_SHL = 23,
     81     kStep2_SHR = 18,
     82     kStep3_SHR = 5
     83   };
     84 
     85   inline explicit Random(uint64_t seed = 0) noexcept { reset(seed); }
     86   inline Random(const Random& other) noexcept = default;
     87 
     88   inline void reset(uint64_t seed = 0) noexcept {
     89     // The number is arbitrary, it means nothing.
     90     constexpr uint64_t kZeroSeed = 0x1F0A2BE71D163FA0u;
     91 
     92     // Generate the state data by using splitmix64.
     93     for (uint32_t i = 0; i < 2; i++) {
     94       seed += 0x9E3779B97F4A7C15u;
     95       uint64_t x = seed;
     96       x = (x ^ (x >> 30)) * 0xBF58476D1CE4E5B9u;
     97       x = (x ^ (x >> 27)) * 0x94D049BB133111EBu;
     98       x = (x ^ (x >> 31));
     99       _state[i] = x != 0 ? x : kZeroSeed;
    100     }
    101   }
    102 
    103   inline uint32_t next_uint32() noexcept {
    104     return uint32_t(next_uint64() >> 32);
    105   }
    106 
    107   inline uint64_t next_uint64() noexcept {
    108     uint64_t x = _state[0];
    109     uint64_t y = _state[1];
    110 
    111     x ^= x << kStep1_SHL;
    112     y ^= y >> kStep3_SHR;
    113     x ^= x >> kStep2_SHR;
    114     x ^= y;
    115 
    116     _state[0] = y;
    117     _state[1] = x;
    118     return x + y;
    119   }
    120 
    121   uint64_t _state[2];
    122 };
    123 
    124 // Bit Array
    125 // =========
    126 
    127 class BitArray {
    128   std::vector<size_t> _bits;
    129   enum : size_t { kBitWordSize = sizeof(size_t) * 8u };
    130 
    131 public:
    132   inline void resize(size_t size) {
    133     size_t size_in_words = (size + kBitWordSize - 1) / kBitWordSize;
    134     _bits.resize(size_in_words);
    135     clear();
    136   }
    137 
    138   inline void clear() {
    139     std::fill(_bits.begin(), _bits.end(), size_t(0));
    140   }
    141 
    142   inline bool has_bit(size_t bit_index) const {
    143     size_t word_index = bit_index / kBitWordSize;
    144     size_t mask = size_t(1) << (bit_index % kBitWordSize);
    145     return (_bits[word_index] & mask) != 0;
    146   }
    147 
    148   inline void set_bit(size_t bit_index) {
    149     size_t word_index = bit_index / kBitWordSize;
    150     size_t mask = size_t(1) << (bit_index % kBitWordSize);
    151     _bits[word_index] |= mask;
    152   }
    153 };
    154 
    155 // Hash Function
    156 // =============
    157 
    158 class HashFunction {
    159 public:
    160   struct Param {
    161     bool used;
    162     uint32_t multiplier;
    163     uint32_t shift;
    164     std::vector<uint32_t> table;
    165   };
    166 
    167   Param params[2];
    168   std::vector<std::pair<uint32_t, uint32_t>> remaining;
    169 
    170   std::string body(const std::string& prototype, const std::string& input_value, const std::string& check_id_before, const std::string& check_id_after) const {
    171     // Single hash table.
    172     const char function_template_1[] =
    173       "{\n"
    174       "  static const $TABLE_TYPE_A$ hash_table[$TABLE_SIZE_A$] = {\n"
    175       "$TABLE_VALUES_A$\n"
    176       "  };\n"
    177       "\n"
    178       "  uint32_t h1 = ($INPUT_VALUE$ * $HASH_MULTIPLIER_A$u) >> $HASH_SHIFT_A$u;\n"
    179       "  uint32_t i1 = hash_table[h1];\n"
    180       "  uint32_t index = 0xFFFFFFFFu;\n"
    181       "\n"
    182       "  if ($CHECK_ID_BEFORE$i1$CHECK_ID_AFTER$ == $INPUT_VALUE$)\n"
    183       "    index = i1;\n"
    184       "$REMAINING_CHECKS$"
    185       "\n"
    186       "  return index;\n"
    187       "}\n";
    188 
    189     // Single hash table, two hash functions.
    190     const char function_template_2[] =
    191       "{\n"
    192       "  static const $TABLE_TYPE_A$ hash_table[$TABLE_SIZE_A$] = {\n"
    193       "$TABLE_VALUES_A$\n"
    194       "  };\n"
    195       "\n"
    196       "  uint32_t h1 = ($INPUT_VALUE$ * $HASH_MULTIPLIER_A$u) >> $HASH_SHIFT_A$u;\n"
    197       "  uint32_t h2 = ($INPUT_VALUE$ * $HASH_MULTIPLIER_B$u) >> $HASH_SHIFT_B$u;\n"
    198       "\n"
    199       "  uint32_t i1 = hash_table[h1];\n"
    200       "  uint32_t i2 = hash_table[h2];\n"
    201       "\n"
    202       "  uint32_t index = 0xFFFFFFFFu;\n"
    203       "\n"
    204       "  if ($CHECK_ID_BEFORE$i1$CHECK_ID_AFTER$ == $INPUT_VALUE$)\n"
    205       "    index = i1;\n"
    206       "\n"
    207       "  if ($CHECK_ID_BEFORE$i2$CHECK_ID_AFTER$ == $INPUT_VALUE$)\n"
    208       "    index = i2;\n"
    209       "$REMAINING_CHECKS$"
    210       "\n"
    211       "  return index;\n"
    212       "}\n";
    213 
    214     // Two hash tables, two hash functions.
    215     const char function_template_3[] =
    216       "{\n"
    217       "  static const $TABLE_TYPE_A$ hashTable1[$TABLE_SIZE_A$] = {\n"
    218       "$TABLE_VALUES_A$\n"
    219       "  };\n"
    220       "\n"
    221       "  static const $TABLE_TYPE_B$ hashTable2[$TABLE_SIZE_B$] = {\n"
    222       "$TABLE_VALUES_B$\n"
    223       "  };\n"
    224       "\n"
    225       "  uint32_t h1 = ($INPUT_VALUE$ * $HASH_MULTIPLIER_A$u) >> $HASH_SHIFT_A$u;\n"
    226       "  uint32_t h2 = ($INPUT_VALUE$ * $HASH_MULTIPLIER_B$u) >> $HASH_SHIFT_B$u;\n"
    227       "\n"
    228       "  uint32_t i1 = hashTable1[h1];\n"
    229       "  uint32_t i2 = hashTable2[h2];\n"
    230       "\n"
    231       "  uint32_t index = 0xFFFFFFFFu;\n"
    232       "\n"
    233       "  if ($CHECK_ID_BEFORE$i1$CHECK_ID_AFTER$ == $INPUT_VALUE$)\n"
    234       "    index = i1;\n"
    235       "\n"
    236       "  if ($CHECK_ID_BEFORE$i2$CHECK_ID_AFTER$ == $INPUT_VALUE$)\n"
    237       "    index = i2;\n"
    238       "$REMAINING_CHECKS$"
    239       "\n"
    240       "  return index;\n"
    241       "}\n";
    242 
    243     std::string body;
    244 
    245     auto format_table = [](const std::vector<uint32_t>& t) {
    246       std::string s("    ");
    247       for (size_t i = 0; i < t.size(); i++) {
    248         if (i != 0) {
    249           if ((i % 24) == 0)
    250             s.append(",\n    ");
    251           else
    252             s.append(", ");
    253         }
    254         s.append(std::to_string(t[i] != 0xFFFFFFFFu ? t[i] : uint32_t(0u)));
    255       }
    256       return s;
    257     };
    258 
    259     auto value_type_of_table = [](const std::vector<uint32_t>& t) {
    260       uint32_t greatest = 0;
    261       for (size_t i = 0; i < t.size(); i++) {
    262         if (t[i] == 0xFFFFFFFFu)
    263           continue;
    264         greatest = std::max(greatest, t[i]);
    265       }
    266 
    267       if (greatest > 65535u)
    268         return "uint32_t";
    269       else if (greatest > 255u)
    270         return "uint16_t";
    271       else
    272         return "uint8_t";
    273     };
    274 
    275     uint32_t bitMask0 = (1u << (32u - params[0].shift)) - 1u;
    276     uint32_t bitMask1 = (1u << (32u - params[1].shift)) - 1u;
    277 
    278     if (params[1].used)
    279       body = params[1].table.size() == 0 ? function_template_2 : function_template_3;
    280     else
    281       body = function_template_1;
    282 
    283     std::string remaining_checks;
    284     if (!remaining.empty()) {
    285       for (auto p : remaining) {
    286         std::string condition("\n"
    287                               "  if ($INPUT_VALUE$ == $KEY$)\n"
    288                               "    index = $KEY_VALUE$;\n");
    289         replace_in_string(condition, std::string("$INPUT_VALUE$"), input_value);
    290         replace_in_string(condition, std::string("$KEY$"), std::to_string(p.first));
    291         replace_in_string(condition, std::string("$KEY_VALUE$"), std::to_string(p.second));
    292         remaining_checks += condition;
    293       }
    294     }
    295 
    296     replace_in_string(body, std::string("$INPUT_VALUE$"), input_value);
    297     replace_in_string(body, std::string("$CHECK_ID_BEFORE$"), check_id_before);
    298     replace_in_string(body, std::string("$CHECK_ID_AFTER$"), check_id_after);
    299 
    300     replace_in_string(body, std::string("$HASH_MULTIPLIER_A$"), std::to_string(params[0].multiplier));
    301     replace_in_string(body, std::string("$HASH_MULTIPLIER_B$"), std::to_string(params[1].multiplier));
    302     replace_in_string(body, std::string("$HASH_SHIFT_A$"), std::to_string(params[0].shift));
    303     replace_in_string(body, std::string("$HASH_SHIFT_B$"), std::to_string(params[1].shift));
    304     replace_in_string(body, std::string("$HASH_MASK_A$"), std::to_string(bitMask0));
    305     replace_in_string(body, std::string("$HASH_MASK_B$"), std::to_string(bitMask1));
    306     replace_in_string(body, std::string("$TABLE_TYPE_A$"), value_type_of_table(params[0].table));
    307     replace_in_string(body, std::string("$TABLE_TYPE_B$"), value_type_of_table(params[1].table));
    308     replace_in_string(body, std::string("$TABLE_SIZE_A$"), std::to_string(params[0].table.size()));
    309     replace_in_string(body, std::string("$TABLE_SIZE_B$"), std::to_string(params[1].table.size()));
    310     replace_in_string(body, std::string("$TABLE_VALUES_A$"), format_table(params[0].table));
    311     replace_in_string(body, std::string("$TABLE_VALUES_B$"), format_table(params[1].table));
    312     replace_in_string(body, std::string("$REMAINING_CHECKS$"), remaining_checks);
    313     body = std::string(prototype) + " " + body;
    314 
    315     return body;
    316   }
    317 };
    318 
    319 template<typename Lambda>
    320 static void run_async(Lambda&& fn, size_t thread_count) {
    321   std::vector<std::thread> threads;
    322 
    323   for (size_t thread_id = 0; thread_id < thread_count; thread_id++)
    324     threads.push_back(std::thread(fn));
    325 
    326   for (std::thread& thread : threads)
    327     thread.join();
    328 }
    329 
    330 // Hash Function Finder
    331 // --------------------
    332 
    333 class Finder {
    334 public:
    335   const uint32_t* _values {};
    336   uint32_t _size {};
    337   HashFunction _hf {};
    338 
    339   Finder(const uint32_t* values, uint32_t size) {
    340     _values = values;
    341     _size = size;
    342   }
    343 /*
    344   void try_another(uint32_t bucketCount1) {
    345     BitArray occupied1;
    346     BitArray occupied2;
    347 
    348     std::vector<uint32_t> hits;
    349 
    350     occupied1.resize(bucketCount1);
    351     occupied2.resize(bucketCount1);
    352     hits.resize(bucketCount1);
    353 
    354     const uint32_t* values = _values;
    355     uint32_t size = _size;
    356     uint32_t localBestCollisions1 = 0xFFFFFFFFu;
    357     uint32_t localBestCollisions2 = 0xFFFFFFFFu;
    358     uint32_t best_score = 0xFFFFFFFFu;
    359 
    360     uint32_t shift1 = 64 - count_trailing_bits(bucketCount1);
    361     Random r;
    362 
    363     uint64_t m1_base = r.next_uint64();
    364     uint32_t attempt = 0;
    365 
    366     for (;;) {
    367       uint64_t bestM1 = m1_base;
    368 
    369       uint64_t pattern1;
    370       uint64_t pattern2;
    371 
    372       if (attempt == 0) {
    373         pattern1 = 0x1;
    374         pattern2 = 0x1;
    375       }
    376       else if (attempt % 16 == 0) {
    377         pattern1 = r.next_uint64() & 0x00FF00FF00FF00FF;
    378         pattern2 = r.next_uint64() & 0xFF00FF00FF00FF00;
    379       }
    380       else {
    381         pattern1 = r.next_uint64() & 0xF;
    382         pattern2 = r.next_uint64() & 0xF000000000000000;
    383       }
    384 
    385       for (uint32_t a = 0; a < 100; a++) {
    386         for (uint32_t bit1 = 0; bit1 < 64; bit1++) {
    387           for (uint32_t bit2 = 0; bit2 < 64; bit2++) {
    388             uint64_t m1 = m1_base ^ (uint64_t(pattern1) << bit1)
    389                                  ^ (uint64_t(pattern2) >> bit2);
    390             uint32_t collisions = 0;
    391             uint32_t moreThan2Collisions = 0;
    392 
    393             occupied1.clear();
    394             occupied2.clear();
    395             uint32_t score = uint32_t(_size);
    396 
    397             for (size_t i = 0; i < size; i++) {
    398               uint32_t index = mul64Op1(values[i], 0, m1, shift1);
    399               if (occupied1.has_bit(index)) {
    400                 collisions++;
    401                 moreThan2Collisions += occupied2.has_bit(index);
    402                 occupied2.set_bit(index);
    403                 if (hits[index] > 1)
    404                   score += 1000;
    405                 else
    406                   score += 1;
    407                 hits[index]++;
    408               }
    409               else {
    410                 occupied1.set_bit(index);
    411                 hits[index] = 1;
    412                 score--;
    413               }
    414             }
    415 
    416             if (score < best_score) {
    417               localBestCollisions1 = collisions;
    418 
    419               if (score < best_score)
    420                 best_score = score;
    421 
    422               bestM1 = m1;
    423               attempt = 0;
    424 
    425               _hf.params[0].used = true;
    426               _hf.params[0].multiplier = m1;
    427               _hf.params[0].shift = shift1;
    428 
    429               // best_collisions = collisions;
    430               printf("  Found (mul=0x%08llX) (collisions=%u) %s\n", (unsigned long long)bestM1, collisions, moreThan2Collisions ? "" : "(max 2 collisions per bucket)");
    431 
    432               if (collisions == 0) {
    433                 return;
    434               }
    435             }
    436           }
    437         }
    438       }
    439 
    440       if (m1_base == bestM1) {
    441         // m1_base += r.next_uint64();
    442         if (++attempt > 10000000) {
    443           printf("Maximum attempts reached\n");
    444           return;
    445         }
    446       }
    447       else {
    448         m1_base = bestM1;
    449       }
    450     }
    451   }
    452 */
    453   bool find_hash_function(uint32_t bucketCount1) {
    454     constexpr uint32_t thread_count = 30;
    455     constexpr uint32_t mStep = 0x00100000u;
    456 
    457     uint32_t mGlobal = 0;
    458     uint32_t mMaxGlobal = 0x7FFFFFFFu;
    459 
    460     uint32_t best_collisions = 0xFFFFFFFFu;
    461     uint32_t bucketCount2 = 0;
    462     std::mutex mutex;
    463 
    464     auto stop_workers = [&]() { mGlobal = 0xFFFFFFFFu; };
    465 
    466     auto next_multiplier_base = [&]() -> uint32_t {
    467       std::lock_guard<std::mutex> guard(mutex);
    468       if (mGlobal == 0xFFFFFFFFu)
    469         return 0xFFFFFFFFu;
    470 
    471       uint32_t m1_base = mGlobal;
    472       mGlobal += mStep;
    473       if (mGlobal >= mMaxGlobal)
    474         mGlobal = 0xFFFFFFFFu;
    475 
    476       return m1_base;
    477     };
    478 
    479     auto reset_multiplier = [&](uint32_t bucket_count, bool guess_max_global = false) {
    480       mGlobal = 0;
    481       uint32_t t = count_trailing_bits(bucket_count);
    482       if (t <= 5 || !guess_max_global)
    483         mMaxGlobal = 0x7FFFFFFFu;
    484       else
    485         mMaxGlobal = 0xFFFFFFFFu >> (t - 5);
    486     };
    487 
    488     printf("Finder::find_hash_function() - Trying to find a first hash function for %u values [%u buckets]\n", _size, bucketCount1);
    489     best_collisions = 0xFFFFFFFFu;
    490     reset_multiplier(bucketCount1, true);
    491 
    492     uint32_t shift1 = 32 - count_trailing_bits(bucketCount1);
    493 
    494     run_async([&]() {
    495       BitArray occupied1;
    496       BitArray occupied2;
    497 
    498       occupied1.resize(bucketCount1);
    499       occupied2.resize(bucketCount1);
    500 
    501       const uint32_t* values = _values;
    502       uint32_t size = _size;
    503       uint32_t localBestCollisions1 = 0xFFFFFFFFu;
    504       uint32_t localBestCollisions2 = 0xFFFFFFFFu;
    505 
    506       for (;;) {
    507         uint32_t m1_base = next_multiplier_base();
    508         if (m1_base == 0xFFFFFFFFu)
    509           return;
    510 
    511         for (uint32_t m1_index = 0; m1_index < mStep; m1_index++) {
    512           uint32_t m1 = m1_base + m1_index;
    513           uint32_t collisions = 0;
    514           uint32_t moreThan2Collisions = 0;
    515 
    516           occupied1.clear();
    517           occupied2.clear();
    518 
    519           for (size_t i = 0; i < size; i++) {
    520             uint32_t index = mulOp1(values[i], m1, shift1);
    521             if (occupied1.has_bit(index)) {
    522               collisions++;
    523               moreThan2Collisions += occupied2.has_bit(index);
    524               occupied2.set_bit(index);
    525             }
    526             occupied1.set_bit(index);
    527           }
    528 
    529           if (collisions < localBestCollisions2 && moreThan2Collisions == 0) {
    530             std::lock_guard<std::mutex> guard(mutex);
    531             localBestCollisions2 = collisions;
    532             printf("  Found 0x%08X (collisions=%u) - no third collision\n", m1, collisions);
    533           }
    534 
    535           if (collisions < localBestCollisions1) {
    536             std::lock_guard<std::mutex> guard(mutex);
    537             localBestCollisions1 = best_collisions;
    538 
    539             if (collisions < best_collisions) {
    540               _hf.params[0].used = true;
    541               _hf.params[0].multiplier = m1;
    542               _hf.params[0].shift = shift1;
    543 
    544               best_collisions = collisions;
    545               printf("  Found 0x%08X (collisions=%u)\n", m1, collisions);
    546 
    547               if (collisions == 0)
    548                 stop_workers();
    549             }
    550           }
    551         }
    552       }
    553     }, thread_count);
    554 
    555     printf("Finder::find_hash_function() - Found a hash function with %u collision(s)\n", best_collisions);
    556     std::vector<std::pair<uint32_t, uint32_t>> remaining_pairs;
    557     std::vector<uint32_t> remaining_values;
    558 
    559     BitArray occupied1;
    560     occupied1.resize(bucketCount1);
    561 
    562     {
    563       for (uint32_t i = 0; i < _size; i++) {
    564         uint32_t index = (_values[i] * _hf.params[0].multiplier) >> _hf.params[0].shift;
    565         if (occupied1.has_bit(index)) {
    566           remaining_pairs.push_back(std::pair<uint32_t, uint32_t>(_values[i], i));
    567           remaining_values.push_back(_values[i]);
    568         }
    569         else {
    570           occupied1.set_bit(index);
    571         }
    572       }
    573     }
    574 
    575     // Try to find another hash function that would use the same table.
    576     bool m2_found = false;
    577     bool m2_same_bucket_table = false;
    578 
    579     // Don't create a secondary hash table for 1 value.
    580     if (remaining_values.size() == 1) {
    581       _hf.remaining = std::move(remaining_pairs);
    582       m2_found = true;
    583     }
    584 
    585     if (!m2_found && best_collisions > 0) {
    586       printf("Finder::find_hash_function() - Trying to find a second hash function using the same bucket list [%u buckets]\n", bucketCount1);
    587 
    588       reset_multiplier(bucketCount1);
    589       run_async([&]() {
    590         const uint32_t* values_data = remaining_values.data();
    591         size_t values_count = remaining_values.size();
    592 
    593         BitArray occupied;
    594         occupied.resize(bucketCount1);
    595 
    596         for (;;) {
    597           uint32_t m2_base = next_multiplier_base();
    598           if (m2_base == 0xFFFFFFFFu)
    599             return;
    600 
    601           for (uint32_t m2_index = 0; m2_index < mStep; m2_index++) {
    602             bool found = true;
    603             uint32_t m2 = m2_base + m2_index;
    604             occupied.clear();
    605 
    606             for (size_t i = 0; i < values_count; i++) {
    607               uint32_t index = mulOp2(values_data[i], m2, shift1);
    608               if (occupied1.has_bit(index) || occupied.has_bit(index)) {
    609                 found = false;
    610                 break;
    611               }
    612               occupied.set_bit(index);
    613             }
    614 
    615             if (found) {
    616               std::lock_guard<std::mutex> guard(mutex);
    617               if (!m2_found) {
    618                 printf("FOUND\n");
    619                 m2_found = true;
    620                 m2_same_bucket_table = true;
    621                 stop_workers();
    622 
    623                 _hf.params[1].used = true;
    624                 _hf.params[1].multiplier = m2;
    625                 _hf.params[1].shift = shift1;
    626                 break;
    627               }
    628             }
    629           }
    630         }
    631       }, thread_count);
    632     }
    633 
    634     // Reset the global multiplier - we want to start from zero again, to find the second hash function M.
    635     if (!m2_found && best_collisions > 0) {
    636       bucketCount2 = alignUpToPowerOf2(best_collisions);
    637       for (;;) {
    638         printf("Finder::find_hash_function() - Trying to find a second hash function [%u buckets]\n", bucketCount2);
    639 
    640         reset_multiplier(bucketCount2);
    641         uint32_t shift2 = 32 - count_trailing_bits(bucketCount2);
    642 
    643         run_async([&]() {
    644           const uint32_t* values_data = remaining_values.data();
    645           size_t values_count = remaining_values.size();
    646 
    647           BitArray occupied;
    648           occupied.resize(bucketCount2);
    649 
    650           for (;;) {
    651             uint32_t m2_base = next_multiplier_base();
    652             if (m2_base == 0xFFFFFFFFu)
    653               return;
    654 
    655             for (uint32_t m2_index = 0; m2_index < mStep; m2_index++) {
    656               bool found = true;
    657               uint32_t m2 = m2_base + m2_index;
    658               occupied.clear();
    659 
    660               for (size_t i = 0; i < values_count; i++) {
    661                 uint32_t index = mulOp2(values_data[i], m2, shift2);
    662                 if (occupied.has_bit(index)) {
    663                   found = false;
    664                   break;
    665                 }
    666                 occupied.set_bit(index);
    667               }
    668 
    669               if (found) {
    670                 std::lock_guard<std::mutex> guard(mutex);
    671                 if (!m2_found) {
    672                   m2_found = true;
    673                   stop_workers();
    674 
    675                   _hf.params[1].used = true;
    676                   _hf.params[1].multiplier = m2;
    677                   _hf.params[1].shift = shift2;
    678                   break;
    679                 }
    680               }
    681             }
    682           }
    683         }, thread_count);
    684 
    685         if (m2_found)
    686           break;
    687         bucketCount2 *= 2u;
    688       }
    689     }
    690 
    691     // Build tables.
    692     {
    693       BitArray occupied;
    694       std::vector<uint32_t> remaining_indexes;
    695 
    696       occupied.resize(bucketCount1);
    697       _hf.params[0].table.resize(bucketCount1, uint32_t(0xFFFFFFFFu));
    698       _hf.params[1].table.resize(bucketCount2, uint32_t(0xFFFFFFFFu));
    699 
    700       {
    701         std::vector<uint32_t>& table = _hf.params[0].table;
    702         for (uint32_t i = 0; i < _size; i++) {
    703           uint32_t index1 = (_values[i] * _hf.params[0].multiplier) >> _hf.params[0].shift;
    704           if (!occupied.has_bit(index1)) {
    705             table[index1] = i;
    706             occupied.set_bit(index1);
    707           }
    708           else {
    709             remaining_indexes.push_back(i);
    710           }
    711         }
    712       }
    713 
    714       if (m2_same_bucket_table || bucketCount2) {
    715         std::vector<uint32_t>& table = m2_same_bucket_table ? _hf.params[0].table : _hf.params[1].table;
    716         for (uint32_t i : remaining_indexes) {
    717           uint32_t index2 = (_values[i] * _hf.params[1].multiplier) >> _hf.params[1].shift;
    718           if (table[index2] == 0xFFFFFFFFu)
    719             table[index2] = i;
    720         }
    721       }
    722     }
    723 
    724     return best_collisions != 0xFFFFFFFFu;
    725   }
    726 
    727   bool find_solution() {
    728     uint32_t bucket_count = alignUpToPowerOf2(_size);
    729     for (;;) {
    730       if (find_hash_function(bucket_count))
    731         return true;
    732 
    733       bucket_count <<= 1;
    734       if (bucket_count > _size * 8)
    735         return false;
    736     }
    737   }
    738 };
    739 
    740 } // {StupidHash}
	odin-blend2d Odin bindings to Blend2D
	Log \| Files \| Refs \| README \| LICENSE