// <!--
// The MIT License (MIT)
//
// Copyright (c) 2024 Kris Jusiak <kris@jusiak.net>
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.
//
#if 0
// -->
[Overview](#Overview) / [Examples](#Examples) / [API](#API) / [FAQ](#FAQ) / [Resources](#Resources)

## `mph`: [Minimal] Static perfect hash library

[![MIT Licence](http://img.shields.io/badge/license-MIT-blue.svg)](https://opensource.org/license/mit)
[![Version](https://img.shields.io/github/v/release/qlibs/mph)](https://github.com/qlibs/mph/releases)
[![Build](https://img.shields.io/badge/build-green.svg)](https://godbolt.org/z/MsE4nnhvc)
[![Try it online](https://img.shields.io/badge/try%20it-online-blue.svg)](https://godbolt.org/z/jcPPsbEvK)

> https://en.wikipedia.org/wiki/Perfect_hash_function

### Use cases

> A static perfect hash function maps a set of keys known in advance to a set of values with no collisions

### Features

- Single header (https://raw.githubusercontent.com/qlibs/mph/main/mph) / C++20 module (https://raw.githubusercontent.com/qlibs/mph/main/mph.cppm)
- Self verification upon include (can be disabled by `-DNTEST` - see [FAQ](#faq))
- Compiles cleanly with ([`-Wall -Wextra -Werror -pedantic -pedantic-errors -fno-exceptions -fno-rtti`](https://godbolt.org/z/WraE4q1dE))
- Minimal [API](#api)
- Optimized run-time execution (see [performance](#performance) / [benchmarks](#benchmarks))
- Fast compilation times (see [compilation](#compilation))
- Trade-offs (see [FAQ](#faq))

### Requirements

- C++20 ([gcc-12+, clang-15+](https://godbolt.org/z/WraE4q1dE)) / [optional] ([bmi2](https://en.wikipedia.org/wiki/X86_Bit_manipulation_instruction_set)), [optional] ([simd](https://en.wikipedia.org/wiki/Single_instruction,_multiple_data)),

### Overview

> Hello world (https://godbolt.org/z/dzd6o3Pxo)

```cpp
enum class color { red, green, blue };

constexpr auto colors = std::array{
  std::pair{"red"sv, color::red},
  std::pair{"green"sv, color::green},
  std::pair{"blue"sv, color::blue},
};

static_assert(color::green == mph::lookup<colors>("green"));
static_assert(color::red   == mph::lookup<colors>("red"));
static_assert(color::blue  == mph::lookup<colors>("blue"));

std::print("{}", mph::lookup<colors>("green"sv)); // prints 1
```

> [!NOTE]
> `mph::lookup` assumes only valid input and returns mapped value direclty.

```cpp
static_assert(not mph::find<colors>("unknown"));
static_assert(mph::find<colors>("green"));
static_assert(mph::find<colors>("red"));
static_assert(mph::find<colors>("blue"));

std::print("{}", *mph::find<colors>("green"sv)); // prints 1
```

> [!NOTE]
> `mph::find` doesnt assume valid input and returns optional of mapped value.

<a name="performance"></a>
> [Minimal] Lookup (https://godbolt.org/z/rqYj9a1cr)

```cpp
int lookup(int id) {
  static constexpr std::array ids{
    std::pair{54u, 91u},
    std::pair{64u, 324u},
    std::pair{91u, 234u},
  };
  return mph::lookup<ids>(id);
}
```

```cpp
lookup: // g++ -DNDEBUG -std=c++20 -O3
  imull   $1275516394, %edi, %eax
  shrl    $23, %eax
  movl    $24029728, %ecx
  shrxl   %eax, %ecx, %eax
  andl    $511, %eax
  retq
```

> Lookup (https://godbolt.org/z/vv6W4nGfb)

```cpp
int lookup(int id) {
  static constexpr std::array ids{
    std::pair{54u, 91u},
    std::pair{324u, 54u},
    std::pair{64u, 324u},
    std::pair{234u, 64u},
    std::pair{91u, 234u},
  };
  return mph::lookup<ids>(id);
}
```

```cpp
lookup: // g++ -DNDEBUG -std=c++20 -O3
  andl    $7, %edi
  leaq    lookup(%rip), %rax
  movl    (%rax,%rdi,4), %eax
  retq

lookup:
 .long   324
 .long   0
 .long   64
 .long   234
 .long   54
 .long   0
 .long   91
```

> Find (https://godbolt.org/z/qMzxKK4sd)

```cpp
int find(int id) {
  static constexpr std::array ids{
    std::pair{27629, 1},
    std::pair{6280, 2},
    // 1..128 pairs...
    std::pair{33691, 128},
  };
  return *mph::find<ids>(id);
}
```

```cpp
find: // g++ -DNDEBUG -std=c++20 -O3 -mbmi2 -mavx512f
  vpbroadcastd    %edi, %zmm0
  shll            $4, %edi
  movzbl          %dil, %ecx
  leaq            find
  vpcmpeqd        (%rdx,%rcx,4), %zmm0, %k0
  kmovw           %k0, %esi
  kortestw        %k0, %k0
  rep             bsfq %rax, %rax
  movl            $64, %eax
  addl            %eax, %ecx
  xorl            %eax, %eax
  testw           %si, %si
  cmovnel         1024(%rdx,%rcx,4), %eax
  vzeroupper
  retq

find:
  ... // see godbolt
```

> Find Strings (https://godbolt.org/z/KaKzf7Pax)

```cpp
int find(std::span<const char, 8> str) {
  static constexpr auto symbols = std::array{
    std::pair{"AMZN    "sv, 1},
    std::pair{"AAPL    "sv, 2},
    std::pair{"GOOGL   "sv, 3},
    std::pair{"META    "sv, 4},
    std::pair{"MSFT    "sv, 5},
    std::pair{"NVDA    "sv, 6},
    std::pair{"TSLA    "sv, 7},
  };
  return *mph::find<symbols>(str);
}
```

```cpp
find: // g++ -DNDEBUG -std=c++20 -O3 -mbmi2
  movq    8(%rsi), %rax
  movl    $1031, %ecx
  leaq    find(%rip), %rdx
  xorl    %esi, %esi
  movq    (%rax), %rax
  pextq   %rcx, %rax, %rcx
  shll    $4, %ecx
  cmpq    (%rcx,%rdx), %rax
  movzbl  8(%rcx,%rdx), %eax
  cmovnel %esi, %eax
  retq

find:
  ... // see godbolt
```

> Find Strings (https://godbolt.org/z/fdMPsYWjE)

```cpp
int find(std::string_view str) {
  using std::literals::operator""sv;
  // values assigned from 0..N-1
  static constexpr std::array symbols{
    "BTC "sv, "ETH "sv, "BNB "sv,
    "SOL "sv, "XRP "sv, "DOGE"sv,
    "TON "sv, "ADA "sv, "SHIB"sv,
    "AVAX"sv, "LINK"sv, "BCH "sv,
  };
  return *mph::find<symbols>(str);
}
```

```cpp
find: // g++ -DNDEBUG -std=c++20 -O3 -mbmi2
  shll    $3, %edi
  bzhil   %edi, (%rsi), %eax
  movl    $789, %ecx
  pextl   %ecx, %eax, %ecx
  leaq    find(%rip), %rdx
  xorl    %esi, %esi
  cmpl    (%rdx,%rcx,8), %eax
  movzbl  4(%rdx,%rcx,8), %eax
  cmovnel %esi, %eax
  retq

find:
  ... // see godbolt
```

### Examples

- [feature] `lookup/find` customization point - https://godbolt.org/z/enqeGxKK9
- [feature] `to` customization point - https://godbolt.org/z/jTMx4n6j3
- [example] `branchless dispatcher` - https://godbolt.org/z/5PTE3ercE
- [performance - https://wg21.link/P2996] `enum_to_string` - https://godbolt.org/z/ojohP6j7f
- [performance - https://wg21.link/P2996] `string_to_enum` - https://godbolt.org/z/83vGhY7M8

<a name="benchmarks"></a>
### Benchmarks (run-time)

> https://github.com/qlibs/mph/tree/benchmark

  `clang++ -std=c++20 -O3 -DNDEBUG -mbmi2 benchmark.cpp`

  ```
  | ns/op |           op/s | err% |total | benchmark
  |------:|---------------:|-----:|-----:|:----------
  | 12.25 |  81,602,449.70 | 0.3% | 0.15 | `random_strings_5_len_4.std.map`
  |  5.56 | 179,750,906.50 | 0.2% | 0.07 | `random_strings_5_len_4.std.unordered_map`
  |  9.17 | 109,096,850.98 | 0.2% | 0.11 | `random_strings_5_len_4.boost.unordered_map`
  | 13.48 |  74,210,250.54 | 0.3% | 0.16 | `random_strings_5_len_4.boost.flat_map`
  |  7.70 | 129,942,965.18 | 0.3% | 0.09 | `random_strings_5_len_4.gperf`
  |  1.61 | 621,532,188.81 | 0.1% | 0.02 | `random_strings_5_len_4.mph`
  | 14.66 |  68,218,086.71 | 0.8% | 0.18 | `random_strings_5_len_8.std.map`
  | 13.45 |  74,365,239.56 | 0.2% | 0.16 | `random_strings_5_len_8.std.unordered_map`
  |  9.68 | 103,355,605.09 | 0.2% | 0.12 | `random_strings_5_len_8.boost.unordered_map`
  | 16.00 |  62,517,180.19 | 0.4% | 0.19 | `random_strings_5_len_8.boost.flat_map`
  |  7.70 | 129,809,356.36 | 0.3% | 0.09 | `random_strings_5_len_8.gperf`
  |  1.58 | 633,084,194.24 | 0.1% | 0.02 | `random_strings_5_len_8.mph`
  | 17.21 |  58,109,576.87 | 0.3% | 0.21 | `random_strings_6_len_2_5.std.map`
  | 15.28 |  65,461,167.99 | 0.2% | 0.18 | `random_strings_6_len_2_5.std.unordered_map`
  | 12.21 |  81,931,391.20 | 0.4% | 0.15 | `random_strings_6_len_2_5.boost.unordered_map`
  | 17.15 |  58,323,741.08 | 0.5% | 0.21 | `random_strings_6_len_2_5.boost.flat_map`
  |  7.94 | 125,883,197.55 | 0.5% | 0.09 | `random_strings_6_len_2_5.gperf`
  |  6.05 | 165,239,616.00 | 0.5% | 0.07 | `random_strings_6_len_2_5.mph`
  | 31.61 |  31,631,402.94 | 0.2% | 0.38 | `random_strings_100_len_8.std.map`
  | 15.32 |  65,280,594.09 | 0.2% | 0.18 | `random_strings_100_len_8.std.unordered_map`
  | 17.13 |  58,383,850.20 | 0.3% | 0.20 | `random_strings_100_len_8.boost.unordered_map`
  | 31.42 |  31,822,519.67 | 0.2% | 0.38 | `random_strings_100_len_8.boost.flat_map`
  |  8.04 | 124,397,773.85 | 0.2% | 0.10 | `random_strings_100_len_8.gperf`
  |  1.58 | 632,813,481.73 | 0.1% | 0.02 | `random_strings_100_len_8.mph`
  | 32.62 |  30,656,015.03 | 0.3% | 0.39 | `random_strings_100_len_1_8.std.map`
  | 19.34 |  51,697,107.73 | 0.5% | 0.23 | `random_strings_100_len_1_8.std.unordered_map`
  | 19.51 |  51,254,525.17 | 0.3% | 0.23 | `random_strings_100_len_1_8.boost.unordered_map`
  | 33.58 |  29,780,574.17 | 0.6% | 0.40 | `random_strings_100_len_1_8.boost.flat_map`
  | 13.06 |  76,577,037.07 | 0.7% | 0.16 | `random_strings_100_len_1_8.gperf`
  |  6.02 | 166,100,665.07 | 0.2% | 0.07 | `random_strings_100_len_1_8.mph`
  |  1.28 | 778,723,795.75 | 0.1% | 0.02 | `random_uints_5.mph`
  ```

  `g++ -std=c++20 -O3 -DNDEBUG -mbmi2 benchmark.cpp`

  ```
  | ns/op |           op/s | err% |total | benchmark
  |------:|---------------:|-----:|-----:|:----------
  | 12.28 |  81,460,330.38 | 0.9% | 0.15 | `random_strings_5_len_4.std.map`
  |  5.29 | 188,967,241.90 | 0.3% | 0.06 | `random_strings_5_len_4.std.unordered_map`
  |  9.69 | 103,163,192.67 | 0.2% | 0.12 | `random_strings_5_len_4.boost.unordered_map`
  | 13.56 |  73,756,333.08 | 0.4% | 0.16 | `random_strings_5_len_4.boost.flat_map`
  |  7.69 | 130,055,662.66 | 0.6% | 0.09 | `random_strings_5_len_4.gperf`
  |  1.39 | 718,910,252.82 | 0.1% | 0.02 | `random_strings_5_len_4.mph`
  | 14.26 |  70,103,007.82 | 2.4% | 0.17 | `random_strings_5_len_8.std.map`
  | 13.36 |  74,871,047.51 | 0.4% | 0.16 | `random_strings_5_len_8.std.unordered_map`
  |  9.82 | 101,802,074.00 | 0.3% | 0.12 | `random_strings_5_len_8.boost.unordered_map`
  | 15.97 |  62,621,571.95 | 0.3% | 0.19 | `random_strings_5_len_8.boost.flat_map`
  |  7.92 | 126,265,206.30 | 0.3% | 0.09 | `random_strings_5_len_8.gperf`
  |  1.40 | 713,596,376.62 | 0.4% | 0.02 | `random_strings_5_len_8.mph`
  | 15.98 |  62,576,142.34 | 0.5% | 0.19 | `random_strings_6_len_2_5.std.map`
  | 17.56 |  56,957,868.12 | 0.5% | 0.21 | `random_strings_6_len_2_5.std.unordered_map`
  | 11.68 |  85,637,378.45 | 0.3% | 0.14 | `random_strings_6_len_2_5.boost.unordered_map`
  | 17.25 |  57,965,732.68 | 0.6% | 0.21 | `random_strings_6_len_2_5.boost.flat_map`
  |  9.13 | 109,580,632.48 | 0.7% | 0.11 | `random_strings_6_len_2_5.gperf`
  |  7.17 | 139,563,745.72 | 0.4% | 0.09 | `random_strings_6_len_2_5.mph`
  | 30.20 |  33,117,522.76 | 0.7% | 0.36 | `random_strings_100_len_8.std.map`
  | 15.01 |  66,627,962.89 | 0.4% | 0.18 | `random_strings_100_len_8.std.unordered_map`
  | 16.79 |  59,559,414.60 | 0.6% | 0.20 | `random_strings_100_len_8.boost.unordered_map`
  | 31.36 |  31,884,629.57 | 0.8% | 0.38 | `random_strings_100_len_8.boost.flat_map`
  |  7.75 | 128,973,947.61 | 0.7% | 0.09 | `random_strings_100_len_8.gperf`
  |  1.50 | 667,041,673.54 | 0.1% | 0.02 | `random_strings_100_len_8.mph`
  | 30.92 |  32,340,612.08 | 0.4% | 0.37 | `random_strings_100_len_1_8.std.map`
  | 25.35 |  39,450,222.09 | 0.4% | 0.30 | `random_strings_100_len_1_8.std.unordered_map`
  | 19.76 |  50,609,820.90 | 0.2% | 0.24 | `random_strings_100_len_1_8.boost.unordered_map`
  | 32.39 |  30,878,018.77 | 0.6% | 0.39 | `random_strings_100_len_1_8.boost.flat_map`
  | 11.20 |  89,270,687.92 | 0.2% | 0.13 | `random_strings_100_len_1_8.gperf`
  |  7.17 | 139,471,159.67 | 0.5% | 0.09 | `random_strings_100_len_1_8.mph`
  |  1.93 | 519,047,110.39 | 0.3% | 0.02 | `random_uints_5.mph`
  ```

<a name="compilation"></a>
### Benchmarks (compilation-time)

> https://qlibs.github.io/mph/perfect_hashing

[![Benchmark](https://raw.githubusercontent.com/qlibs/mph/benchmark/perfect_hashing/benchmark_int_to_int.png)](https://qlibs.github.io/mph/perfect_hashing)
[![Benchmark](https://raw.githubusercontent.com/qlibs/mph/benchmark/perfect_hashing/benchmark_str_to_int.png)](https://qlibs.github.io/mph/perfect_hashing)

### API

```cpp
namespace mph::inline v5_0_5 {
  /**
   * Static [minimal] perfect hash lookup function
   * @tparam entries constexpr array of keys or key/value pairs
   */
  template<const auto& entries>
  inline constexpr auto lookup = [](const auto& key) {
    if constexpr(constexpr lookup$magic_lut<entries> lookup{}; lookup) {
      return lookup(key);
    } else {
      return lookup$pext<entries>(key);
    }
  };

  /**
   * Static perfect hash find function
   * @tparam entries constexpr array of keys or key/value pairs
   */
  template<const auto& entries>
  inline constexpr auto find =
    []<u8 probability = 50u>(const auto& key, const auto& unknown = {}) -> optional {
      if constexpr (entries.size() == 0u) {
        return unknown;
      } else if constexpr (entries.size() <= 64u) {
        return find$pext<entries>.operator()<probability>(key, unknown);
      } else {
        constexpr auto bucket_size = simd_size_v<key_type, simd_abi::native<key_type>>;
        return find$simd<entries, bucket_size>.operator()<probability>(key, unknown);
      }
    };
} // namespace mph
```

### FAQ

> - Trade-offs?
>
>     > `mph` supports different types of key/value pairs and thousands of key/value pairs, but not millions - (see [benchmarks](#benchmarks)).
>
>   - All keys have to fit into `uint128_t`, that includes strings.
>   - If the above criteria are not satisfied `mph` will [SFINAE](https://en.wikipedia.org/wiki/Substitution_failure_is_not_an_error) away `lookup` function.
>   - In such case different backup policy should be used instead (which can be also used as customization point for user-defined `lookup` implementation), for example:
>
>     ```cpp
>     template<const auto& entries> requires (entries.size() > 1'000'000)
>     inline constexpr auto mph::find =
>         [](const auto& key, const auto& unknown = {}) -> optional { ... }
>     ```
>
> - How `mph` is working under the hood?
>
>     > `mph` takes advantage of knowing the key/value pairs at compile-time as well as the specific hardware instructions.
>       The following is a pseudo code of the `lookup` algorithm for minimal perfect hash table.
>
>     ```python
>     def lookup$magic_lut[entries: array](key : any, max_attempts = 100'000):
>       # 0. magic and lut for entries [compile-time]
>       nbits = sizeof(u32) * CHAR_BIT - countl_zero(max(entries.second))
>       mask = (1u << nbits) - 1u;
>       shift = sizeof(u32) * CHAR_BIT - nbits;
>       lut = {};
>       while max_attempts--:
>         magic = rand()
>         for k, v in entries:
>           lut |= v << (k * magic >> shift);
>
>         for k, v in entries:
>           if (lut >> (k * magic >> shift) & mask) != v:
>             lut = {}
>             break
>
>       assert magic != 0 and lut != 0 and shift != 0 and mask != 0
>
>       # 1. lookup [run-time]
>       return (lut >> ((key * magic) >> shift)) & mask;
>     ```
>
>     > The following is a pseudo code of the `find` algorithm for perfect hash table.
>
>     ```python
>     # word: 00101011
>     # mask: 11100001
>     #    &: 000____1
>     # pext: ____0001 # intel/intrinsics-guide/index.html#text=pext
>     def pext(a : uN, mask : uN):
>       dst, m, k = ([], 0, 0)
>
>       while m < nbits(a):
>         if mask[m] == 1:
>           dst.append(a[m])
>           k += 1
>         m += 1
>
>       return uN(dst)
>     ```
>
>     ```python
>     def find$pext[entries: array](key : any, unknown: any):
>       # 0. find mask which uniquely identifies all keys [compile-time]
>       mask = 0b111111...
>
>       for i in range(nbits(mask)):
>         masked = []
>         mask.unset(i)
>
>         for k, v in entries:
>           masked.append(k & mask)
>
>         if not unique(masked):
>           mask.set(i)
>
>       assert unique(masked)
>       assert mask != ~mask{}
>
>       # 1. create lookup table [compile-time]
>       lookup = array(typeof(entries[0]), 2**popcount(mask))
>       for k, v in entries:
>         lookup[pext(k, mask)] = (k, v)
>
>       # 2. lookup [run-time] # if key is a string convert to integral first (memcpy)
>       k, v = lookup[pext(key, mask)]
>
>       if k == key: # cmove
>         return v
>       else:
>         return unknown
>     ```
>
>     ```python
>     def find$simd[entries: array](key : any, unknown: any):
>       # 0. find mask which uniquely identifies all keys [compile-time]
>       mask = 0b111111...
>       bucket_size = simd_size_v<entries[0].first, native>
>
>       for i in range(nbits(mask)):
>         masked = []
>         mask.unset(i)
>
>         for k, v in entries:
>           masked.append(k & mask)
>
>         if not unique(masked, bucket_size):
>           mask.set(i)
>
>       assert unique(masked, bucket_size)
>       assert mask != ~mask{}
>
>       # 1. create lookup table [compile-time]
>       keys   = array(typeof(entries[0].first), bucket_size * 2**popcount(mask))
>       values = array(typeof(entries[0].second), bucket_size * 2**popcount(mask))
>       for k, v in entries:
>         slot = pext(k, mask)
>         while (keys[slot]) slot++;
>         keys[slot] = k
>         values[slot] = v
>
>       # 2. lookup [run-time] # if key is a string convert to integral first (memcpy)
>       index = bucket_size * pext(key, mask)
>       match = k == keys[&index] # simd element-wise comparison
>
>       if any_of(match):
>         return values[index + find_first_set(match)]
>       else:
>         return unknown
>     ```
>
>     > [More information](https://www.youtube.com/watch?v=kCATOctR0BA)
>
> - How to tweak `lookup/find` performance for my data/use case?
>
>     > Always measure!
>
>   - [[bmi2](https://en.wikipedia.org/wiki/X86_Bit_manipulation_instruction_set) ([Intel Haswell](Intel)+, [AMD Zen3](https://en.wikipedia.org/wiki/Zen_3)+)] hardware instruction acceleration is faster than software emulation. (AMD Zen2 pext takes 18 cycles, is worth disabling hardware accelerated version)
>   - For integral keys, use u32 or u64.
>   - For strings, consider aligning the input data and passing it with compile-time size via `span`, `array`.
>   - If all strings length is less than 4 that will be more optimized than if all string length will be less than 8 and 16. That will make the lookup table smaller and getting the value will have one instruction less.
>   - Experiment with different `probability` values to optimize lookups. Especially benefitial if its known that input keys are always coming from predefined `entries` (probability = 100) as it will avoid the comparison.
>   - Consider passing cache size alignment (`hardware_destructive_interference_size` - usually `64u`) to the `lookup/find`. That will align the underlying lookup table.
>
> - How to fix compilation error `constexpr evaluation hit maximum step limit`?
>
>     > The following options can be used to increase the limits, however, compilation-times should be monitored.
>
>     ```
>     gcc:   -fconstexpr-ops-limit=N
>     clang: -fconstexpr-steps=N
>     ```
>
> - Is support for [bmi2](https://en.wikipedia.org/wiki/X86_Bit_manipulation_instruction_set) instructions required?
>
>     > `mph` works on platforms without `bmi2` instructions which can be emulated with some limitations (*).
>
>     ```cpp
>     // bmi2
>     mov     ecx, 789
>     pext    ecx, eax, ecx
>     ```
>
>     > [intel.com/pext](https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#text=pext) / [uops.info/pext](https://uops.info/table.html?search=PEXT%20(R64%2C%20R64%2C%20R64)&cb_lat=on&cb_HSW=on&cb_BDW=on&cb_SKL=on&cb_CFL=on&cb_CLX=on&cb_ICL=on&cb_TGL=on&cb_RKL=on&cb_ZEN2=on&cb_ZEN3=on&cb_ZEN4=on&cb_measurements=on&cb_bmi=on)
>
>     ```cpp
>     // no bmi2
>     mov     ecx, eax
>     and     ecx, 789
>     imul    ecx, ecx, 57
>     shr     ecx, 2
>     and     ecx, 248
>     ```
>
>     > https://stackoverflow.com/questions/14547087/extracting-bits-with-a-single-multiplication (*)
>
> - How to disable `cmov` generation?
>
>     > Set `probability` value to something else than `50u` (default) - it means that the input data is predictable in some way and `jmp` will be generated instead. Additionaly the following compiler options can be used.
>
>     ```
>     clang: -mllvm -x86-cmov-converter=false
>     ```
>
> - How to disable running tests at compile-time?
>
>     > When `-DNTEST` is defined static_asserts tests wont be executed upon inclusion.
>       Note: Use with caution as disabling tests means that there are no gurantees upon inclusion that given compiler/env combination works as expected.
>
> - Similar projects?
>
>     > [gperf](https://www.gnu.org/software/gperf), [frozen](https://github.com/serge-sans-paille/frozen), [nbperf](https://github.com/rurban/nbperf), [cmph](https://cmph.sourceforge.net), [perfecthash](https://github.com/tpn/perfecthash), [lemonhash](https://github.com/ByteHamster/LeMonHash), [pthash](https://github.com/jermp/pthash), [shockhash](https://github.com/ByteHamster/ShockHash), [burr](https://github.com/lorenzhs/BuRR), [hash-prospector](https://github.com/skeeto/hash-prospector)

### Resources

> - Minimal Perfect Hashing - http://stevehanov.ca/blog/index.php?id=119
> - Pefect Hashing - https://github.com/tpn/pdfs/tree/master/Perfect%20Hashing
> - Hash Functions - https://nullprogram.com/blog/2018/07/31
> - `gperf` - https://www.dre.vanderbilt.edu/~schmidt/PDF/C++-USENIX-90.pdf
> - `cmph` - https://cmph.sourceforge.net/papers
> - `pthash` - https://arxiv.org/pdf/2104.10402
> - `smasher` - https://github.com/rurban/smhasher

### License

> - [MIT](LICENSE)

<!--
#endif

#pragma once
#pragma GCC system_header

#if __has_include(<experimental/simd>)
#include <experimental/simd>
#endif

namespace mph::inline v5_0_5 {
using i8   = __INT8_TYPE__;
using u8   = __UINT8_TYPE__;
using i16  = __INT16_TYPE__;
using u16  = __UINT16_TYPE__;
using i32  = __INT32_TYPE__;
using u32  = __UINT32_TYPE__;
using i64  = __INT64_TYPE__;
using u64  = __UINT64_TYPE__;
#if defined(__SIZEOF_INT128__)
using i128 = __int128;
using u128 = unsigned __int128;
#endif

namespace utility {
template<class T1, class T2>
struct compressed_pair {
  using first_type = T1;
  using second_type = T2;
  [[no_unique_address]] T1 first;
  [[no_unique_address]] T2 second;
};
template<class... Ts> compressed_pair(Ts...) -> compressed_pair<Ts...>;

template<class T, u32 Size>
struct array {
  using value_type = T;
  [[nodiscard]] constexpr const T* data() const noexcept { return data_; }
  [[nodiscard]] constexpr T* data() noexcept { return data_; }
  [[nodiscard]] constexpr auto begin() const noexcept { return &data_[0]; }
  [[nodiscard]] constexpr auto begin() noexcept { return &data_[0]; }
  [[nodiscard]] constexpr auto end() const noexcept { return &data_[0] + Size; }
  [[nodiscard]] constexpr auto end() noexcept { return &data_[0] + Size; }
  [[nodiscard]] constexpr auto size() const noexcept { return Size; }
  [[nodiscard]] constexpr const auto& operator[](u32 i) const noexcept { return data_[i]; }
  [[nodiscard]] constexpr auto& operator[](u32 i) noexcept { return data_[i]; }
  constexpr void fill(const T& value) noexcept { for (auto i = 0u; i < Size; ++i) { data_[i] = value; } }
  T data_[Size];
};
template<class T, class... Ts> array(T, Ts...) -> array<T, 1u + sizeof...(Ts)>;
} // namespace utility

namespace type_traits {
namespace detail {
template<bool> struct conditional;
template<> struct conditional<false> { template <class, class T> using fn = T; };
template<> struct conditional<true>  { template <class T, class> using fn = T; };
template<class T> auto value_type(const T&) -> typename T::value_type;
} // namespace detail

template<bool B, class T, class F>
using conditional_t = typename detail::conditional<B>::template fn<T, F>;

template<const auto& v>
using value_type_t = decltype(detail::value_type(v));

template<auto v> struct constant {
  static constexpr auto value = v;
  constexpr operator auto() const noexcept { return value; }
};
template<auto v> inline constexpr constant<v> constant_v{};
template<class T> struct constant_t { static constexpr T value{}; };
} // namespace type_traits

namespace random {
// https://www.pcg-random.org
struct pcg {
  [[nodiscard]] constexpr auto operator()() noexcept -> u32 {
    u64 old_state = state;
    state = old_state * 6364136223846793005u + increment;
    u32 xor_shifted = ((old_state >> 18u) ^ old_state) >> 27u;
    u32 rot = u32(old_state >> 59u);
    return (xor_shifted >> rot) | (xor_shifted << ((-rot) & 31u));
  }
  u64 increment{1442695040888963407u};
  u64 state{5573589319906701683u + increment};
};
} // namespace random

template<u8 probability> requires (probability >= 0u and probability <= 100u)
inline constexpr auto conditional =
  []<class T>([[maybe_unused]] const bool cond, [[maybe_unused]] const T lhs, [[maybe_unused]] const T rhs) {
    if constexpr (probability == 0u) {
      return rhs;
    } else if constexpr (probability == 100u) {
      return lhs;
    } else if constexpr (probability == 50u) {
        #if __has_builtin(__builtin_unpredictable)
        if (__builtin_is_constant_evaluated()) {
          return cond ? lhs : rhs;
        } else if (__builtin_unpredictable(cond)) {
          return lhs;
        } else {
          return rhs;
        }
        #else
        constexpr auto underlying = [](const auto value) {
          if constexpr (__is_enum(decltype(value))) {
            return static_cast<__underlying_type(decltype(value))>(value);
          } else {
            return value;
          }
        };
        if constexpr (requires { T(cond * underlying(lhs.value), cond); }) {
          return T(cond * underlying(lhs.value), cond);
        } else if constexpr (requires { T(cond * underlying(lhs)); }) {
          return T(cond * underlying(lhs));
        } else {
          return __builtin_expect_with_probability(cond, 1, .5f) ? lhs : rhs;
        }
        #endif
    } else {
      return __builtin_expect_with_probability(cond, 1,
        [] { return float(probability) / float(100u); }()) ? lhs : rhs;
    }
  };

template<class T>
[[nodiscard]] [[gnu::always_inline]] constexpr auto to(const auto& data) noexcept -> T {
  if (__builtin_is_constant_evaluated()) {
    if constexpr (requires { data.data(); data.size(); }) {
      T t{};
      for (auto i = 0u; i < data.size(); ++i) {
        t = (t << __CHAR_BIT__) | data.data()[data.size() - i - 1u];
      }
      return t;
    } else if constexpr (requires(u32 n) { data[n]; }) {
      u32 size{};
      auto ptr = data;
      while (*ptr++) size++;
      T t{};
      for (auto i = 0u; i < size; ++i) {
        t = (t << __CHAR_BIT__) | data[size - i - 1u];
      }
      return t;
    } else {
      return static_cast<T>(data);
    }
  } else if constexpr (requires { static_cast<T>(data); } ) {
    return static_cast<T>(data);
  } else if constexpr (requires { data.data(); data.size(); }) {
    if constexpr (requires { []<template<class, auto> class T_, class _, auto size>(T_<_, size>){}(data); }) {
      return [&]<template<class, auto> class T_, class _, auto size>(T_<_, size>) {
        if constexpr (not size) {
          return T{};
        } else if constexpr (size == sizeof(T)) {
          return *__builtin_bit_cast(const T*, data.data());
        } else if constexpr (size <= sizeof(T)) {
          T t{};
          __builtin_memcpy(&t, data.data(), size);
          return t;
        }
      }(data);
    } else {
      #if defined (MPH_PAGE_SIZE)
      // https://github.com/bminor/glibc/blob/master/sysdeps/generic/memcopy.h#L162
      if ((u64(data.data()) & (MPH_PAGE_SIZE - 1ul)) > (MPH_PAGE_SIZE - sizeof(T))) [[unlikely]] {
        return [&data] [[gnu::cold]] {
          T t{};
          __builtin_memcpy(&t, data.data(), data.size());
          return t;
        }();
      }
      #endif
      T t{};
      __builtin_memcpy(&t, data.data(), data.size() < sizeof(t) ? data.size() : sizeof(t));
      const auto index = T(data.size() * __CHAR_BIT__);
      #ifdef __BMI2__
      if constexpr (sizeof(t) <= sizeof(u32)) {
        return __builtin_ia32_bzhi_si(t, index);
      } else if constexpr (sizeof(t) <= sizeof(u64)) {
        return __builtin_ia32_bzhi_di(t, index);
      } else {
      #endif
        constexpr T size = sizeof(T) * __CHAR_BIT__;
        return index >= size ? t : t & ((T(1) << index) - T(1));
      #ifdef __BMI2__
      }
      #endif
    }
  } else { // unsafe
    #pragma GCC diagnostic push
    #pragma GCC diagnostic ignored "-Warray-bounds"
    return *reinterpret_cast<const T*>(data);
    #pragma GCC diagnostic pop
  }
  __builtin_unreachable();
}

namespace detail {
template<class T, T size = sizeof(T) * __CHAR_BIT__>
[[nodiscard]] [[gnu::always_inline]] constexpr auto pext(const T a, const auto mask) noexcept -> T {
  #ifdef __BMI2__
  // https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#text=pext
  if (__builtin_is_constant_evaluated()) {
    T result{};
    T m = mask;
    auto k = 0u;
    for (T i{}; i < size; ++i) {
      if (m & 1) result |= ((a >> i) & 1) << k++;
      m >>= 1;
    }
    return result;
  }
  else if constexpr (requires { u32{mask}; }) { return __builtin_ia32_pext_si(a, mask); }
  else if constexpr (requires { u64{mask}; }) { return __builtin_ia32_pext_di(a, mask); }
  else
  #endif
  if constexpr (requires { mask.value; }) {
    // https://stackoverflow.com/questions/14547087/extracting-bits-with-a-single-multiplication
    // https://github.com/intel/compile-time-init-build/blob/main/include/lookup/pseudo_pext_lookup.hpp
    constexpr auto clz = [](auto x) {
      decltype(x) n{sizeof(x) * __CHAR_BIT__ - 1};
      if (not x) return decltype(x)(sizeof(x) * __CHAR_BIT__);
      while (x >>= 1u) n--;
      return n;
    };
    constexpr auto mbits = __builtin_popcountl(mask);
    constexpr auto nbits = size - mbits - clz(mask.value);
    constexpr auto coefficient = [&] {
      auto set = false;
      auto dst = nbits;
      T result{};
      for (auto i = 0u; i < size; ++i) {
        const auto curr = ((T(1) << i) & mask) != T();
        if (curr and not set) result = result | (T(1) << (dst - i));
        dst += curr;
        set = curr;
      }
      return result;
    }();
    if constexpr(constexpr auto final_mask = ((T(1) << mbits) - T(1));
      ((((mask) * coefficient) >> nbits) & final_mask) == final_mask) {
      return (((a & mask) * coefficient) >> nbits) & final_mask;
    }
  }
  T result{};
  T m = mask;
  auto k = 0u;
  for (T i{}; i < size; ++i) {
    if (m & 1) result |= ((a >> i) & 1) << k++;
    m >>= 1;
  }
  return result;
}

template<class T, u32 N = 1u>
[[nodiscard]] constexpr auto mask(const auto& entries) noexcept -> T {
  utility::array<T, decltype(entries){}.size()> vs;
  T max{};
  for (auto i = 0u; i < vs.size(); ++i) {
    if (vs[i] = entries[i].first; vs[i] > max) max = vs[i];
  }
  constexpr auto H = (N * vs.size()) << 1u;
  constexpr auto N_ = N - 1u;
  const auto lz = sizeof(max) <= sizeof(u32) ? __builtin_clz(max) : __builtin_clzl(max);
  const auto nbits = sizeof(T) * __CHAR_BIT__ - lz - 1u;
  utility::array<T, H> hashed;
  T mask = ((T(1) << nbits) - 1u);
  for (int i = nbits; i >= 0; --i) {
    mask &= ~(T(1) << i);
    hashed = {};
    for (auto j = 0u; j < vs.size(); ++j) {
      const T masked = (vs[j] & mask) + 1u;
      auto slot = masked % H;
      auto n = N_;
      auto found = false;
      while (hashed[slot]) {
        if (hashed[slot] == masked and not n--) {
          found = true;
          break;
        }
        slot = (slot + 1u) % H;
      }
      if (found) {
        mask |= (T(1) << i);
        break;
      }
      hashed[slot] = masked;
    }
  }
  return mask;
}

template<auto entries>
[[nodiscard]] constexpr auto narrow_mask() noexcept {
    static constexpr auto wide_mask = mask<u64>(entries);
    if constexpr (wide_mask <= UINT32_MAX) {
        return static_cast<u32>(wide_mask);
    } else {
        return wide_mask;
    }
}

template<const auto& entries>
struct traits {
  static constexpr auto mappings = [] {
    if constexpr (requires { entries[0].size(); }) { // array{"a"sv, "b"sv, ...}
      constexpr auto max_len = [] {
        u32 len{};
        for (const auto& entry : entries) { if (entry.size() > len) { len = entry.size(); } }
        return len;
      }();

      using key_type = decltype([] {
            if constexpr (max_len <= sizeof(u8)) { return u8{}; }
        else if constexpr (max_len <= sizeof(u16)) { return u16{}; }
        else if constexpr (max_len <= sizeof(u32)) { return u32{}; }
        else if constexpr (max_len <= sizeof(u64)) { return u64{}; }
        #if defined(__SIZEOF_INT128__)
        else if constexpr (max_len <= sizeof(u128)) { return u128{}; }
        #endif
      }());

      using mapped_type = decltype([] {
             if constexpr (entries.size() < u8(u8{}-1u)) { return u8{}; }
        else if constexpr (entries.size() < u16(u16{}-1u)) { return u16{}; }
        else if constexpr (entries.size() < u32(u32{}-1u)) { return u32{}; }
        else if constexpr (entries.size() < u64(u64{}-1u)) { return u64{}; }
        #if defined(__SIZEOF_INT128__)
        else if constexpr (entries.size() < u128(u128{}-1u)) { return u128{}; }
        #endif
      }());

      utility::array<utility::compressed_pair<key_type, mapped_type>, entries.size()> entries_;
      for (mapped_type i{}; i < entries.size(); ++i) {
        entries_[i] = {to<key_type>(entries[i]), mapped_type(i)};
      }
      return entries_;
    } else if constexpr (requires (u32 n) { entries[n].first.size(); entries[n].second; }) { // array{pair{"a"sv, 1}, ...}
      constexpr auto max_len = [] {
        u32 len{};
        for (const auto& entry : entries) { if (entry.first.size() > len) { len = entry.first.size(); } }
        return len;
      }();

      using key_type = decltype([] {
            if constexpr (max_len <= sizeof(u8)) { return u8{}; }
        else if constexpr (max_len <= sizeof(u16)) { return u16{}; }
        else if constexpr (max_len <= sizeof(u32)) { return u32{}; }
        else if constexpr (max_len <= sizeof(u64)) { return u64{}; }
        #if defined(__SIZEOF_INT128__)
        else if constexpr (max_len <= sizeof(u128)) { return u128{}; }
        #endif
      }());
      using mapped_type = typename type_traits::value_type_t<entries>::second_type;

      utility::array<utility::compressed_pair<key_type, mapped_type>, entries.size()> entries_;
      for (auto i = 0u; i < entries.size(); ++i) {
        entries_[i] = {to<key_type>(entries[i].first), entries[i].second};
      }
      return entries_;
    } else if constexpr (not requires (u32 n) { entries[n].first; entries[n].second; }) { // array{1, 2, 3, ...}
      using key_type = type_traits::value_type_t<entries>;
      using mapped_type = decltype([] {
             if constexpr (entries.size() < u8(u8{}-1u)) { return u8{}; }
        else if constexpr (entries.size() < u16(u16{}-1u)) { return u16{}; }
        else if constexpr (entries.size() < u32(u32{}-1u)) { return u32{}; }
        else if constexpr (entries.size() < u64(u64{}-1u)) { return u64{}; }
        #if defined(__SIZEOF_INT128__)
        else if constexpr (entries.size() < u128(u128{}-1u)) { return u128{}; }
        #endif
      }());

      utility::array<utility::compressed_pair<key_type, mapped_type>, entries.size()> entries_;
      for (auto i = 0u; i < entries.size(); ++i) {
        entries_[i] = {entries[i], mapped_type(i)};
      }
      return entries_;
    } else if constexpr (__is_enum(typename type_traits::value_type_t<entries>::first_type)) {
      using key_type = __underlying_type(typename type_traits::value_type_t<entries>::first_type);
      using mapped_type = typename type_traits::value_type_t<entries>::second_type;

      utility::array<utility::compressed_pair<key_type, mapped_type>, entries.size()> entries_;
      for (auto i = 0u; i < entries.size(); ++i) {
        entries_[i] = {static_cast<key_type>(entries[i].first), entries[i].second};
      }
      return entries_;
    } else { // array{pair{1, 2}, ...}
      return entries;
    }
  }();
  using key_type = typename type_traits::value_type_t<mappings>::first_type;
  using mapped_type = typename type_traits::value_type_t<mappings>::second_type;
  using key_mapped_type = utility::compressed_pair<key_type, mapped_type>;
};
} // namespace detail

template<class T>
struct optional {
  using value_type = T;
  constexpr optional() noexcept = default;
  constexpr optional(const value_type value, const bool flag = true) noexcept
    : value(value), flag(flag)
  { }
  [[nodiscard]] constexpr operator bool() const noexcept { return flag; }
  [[nodiscard]] constexpr auto operator*() const noexcept { return value; }
  T value{};
  bool flag{};
};

template<const auto& entries>
struct lookup$magic_lut {
  using key_type = typename detail::traits<entries>::key_type;
  using mapped_type = typename detail::traits<entries>::mapped_type;
  using value_type = type_traits::conditional_t<sizeof(key_type) <= sizeof(u32), u32, u64>;
  using result_type = mapped_type;

  constexpr explicit lookup$magic_lut(u32 max_attempts = 100'000) noexcept {
    const auto nbits = [] {
      value_type max{};
      for (const auto& [_, v]: detail::traits<entries>::mappings) {
        if (value_type(v) > max) max = value_type(v);
      }
      return max ? (sizeof(value_type) * __CHAR_BIT__ - __builtin_clz(max)) : value_type{};
    }();

    if (nbits * entries.size() > sizeof(value_type) * __CHAR_BIT__) {
      return;
    }

    mask = (1u << nbits) - 1u;
    shift = sizeof(value_type) * __CHAR_BIT__ - nbits;

    random::pcg random{};
    while (not lut and max_attempts--) {
      [&] {
        magic = random();
        for (const auto& [k, v] : detail::traits<entries>::mappings) {
          const auto shl = value_type(k * magic) >> shift;
          if (shl >= sizeof(value_type) * __CHAR_BIT__) {
            lut = {};
            return;
          }
          lut |= value_type(v) << shl;
        }
        for (const auto& [k, v] : detail::traits<entries>::mappings) {
          if (((lut >> (value_type(k * magic) >> shift)) & mask) != value_type(v)) {
            lut = {};
            return;
          }
        }
      }();
    }
  }

  [[nodiscard]] constexpr auto operator()(const auto& key) const noexcept -> result_type {
    return (lut >> ((to<key_type>(key) * magic) >> shift)) & mask;
  }

  [[nodiscard]] constexpr explicit operator bool() const noexcept {
    return mask and shift and magic and lut;
  }

  value_type mask{};
  value_type shift{};
  value_type magic{};
  value_type lut{};
};

template<const auto& entries>
struct lookup$pext {
  using key_type = typename detail::traits<entries>::key_type;
  using mapped_type = typename detail::traits<entries>::mapped_type;
  static constexpr auto mask = type_traits::constant_v<detail::narrow_mask<detail::traits<entries>::mappings>()>;
  using mask_type = type_traits::conditional_t<sizeof(mask.value) <= sizeof(u32), u32, u64>;
  using result_type = mapped_type;

  constexpr lookup$pext() noexcept {
    for (const auto& [k, v] : detail::traits<entries>::mappings) {
      lut[detail::pext(k, mask)] = v;
    }
  }

  [[nodiscard]] constexpr auto operator()(const auto& key) const noexcept -> result_type {
    return lut[detail::pext(to<mask_type>(key), mask)];
  }

  static constexpr auto size = [] {
    key_type max{};
    for (const auto& [k, _] : detail::traits<entries>::mappings) {
      if (const auto p = detail::pext(k, mask); p > max) {
        max = p;
      }
    }
    return max + 1u;
  }();
  utility::array<mapped_type, size> lut{};
};

template<const auto& entries>
struct find$pext {
  using key_type = typename detail::traits<entries>::key_type;
  using mapped_type = typename detail::traits<entries>::mapped_type;
  using key_mapped_type = utility::compressed_pair<key_type, mapped_type>;
  static constexpr auto mask = type_traits::constant_v<detail::narrow_mask<detail::traits<entries>::mappings>()>;
  using mask_type = type_traits::conditional_t<sizeof(mask.value) <= sizeof(u32), u32, u64>;
  using result_type = optional<mapped_type>;

  constexpr find$pext() noexcept {
    for (const auto& [key, value] : detail::traits<entries>::mappings) {
      lut[detail::pext(key, mask)] = {key, value};
    }
  }

  template<u8 probability = 50u> requires (probability >= 0u and probability <= 100u)
  [[nodiscard]] constexpr auto operator()(const auto& key, const auto&... ts) const noexcept -> result_type {
    auto&& lhs = to<mask_type>(key);
    auto&& [rhs, value] = lut[detail::pext(lhs, mask)];
    return conditional<probability>(lhs == rhs, result_type(value), result_type(ts...));
  }

  utility::array<key_mapped_type, mask_type(1) << __builtin_popcountl(mask)> lut{};
};

#if __has_include(<experimental/simd>)
template<const auto& entries, u32 BucketSize>
struct find$simd {
  using key_type = typename detail::traits<entries>::key_type;
  using mapped_type = typename detail::traits<entries>::mapped_type;
  using key_mapped_type = utility::compressed_pair<key_type, mapped_type>;
  static constexpr auto mask = type_traits::constant_v<detail::narrow_mask<detail::traits<entries>::mappings>()>;
  using mask_type = type_traits::conditional_t<sizeof(mask.value) <= sizeof(u32), u32, u64>;
  using result_type = optional<mapped_type>;

  constexpr find$simd() noexcept {
    for (const auto& [key, value] : detail::traits<entries>::mappings) {
      auto slot = BucketSize * detail::pext(key, mask);
      while (keys[slot]) slot++;
      keys[slot] = key;
      values[slot] = value;
    }
  }

  template<u8 probability = 50u> requires (probability >= 0u and probability <= 100u)
  [[nodiscard]] constexpr auto operator()(const auto& key, const auto&... ts) const noexcept -> result_type {
    auto&& value = to<mask_type>(key);
    auto&& index = BucketSize * detail::pext(value, mask);
    const std::experimental::fixed_size_simd<key_type, BucketSize> lhs{value};
    const std::experimental::fixed_size_simd<key_type, BucketSize> rhs{&keys[index], std::experimental::element_aligned};
    const auto match = lhs == rhs;
    return conditional<probability>(
      std::experimental::any_of(match),
      result_type(values[index + std::experimental::find_first_set(match)]),
      result_type(ts...)
    );
  }

  static constexpr auto size = BucketSize * (mask_type(1) << __builtin_popcountl(mask));
  utility::array<key_type, size> keys{};
  utility::array<mapped_type, size> values{};
};
#endif

/**
 * Static [minimal] perfect hash lookup function
 * @tparam entries constexpr array of keys or key/value pairs
 */
template<const auto& entries> inline constexpr auto lookup =
  []([[maybe_unused]] const auto& key) {
    using key_type = typename detail::traits<entries>::key_type;
    using mapped_type = typename detail::traits<entries>::mapped_type;
    using result_type = mapped_type;
    if constexpr (entries.size() == 0u) {
      return result_type{};
    } else if constexpr (entries.size() == 1u) {
      return result_type(detail::traits<entries>::mappings[0].second);
    } else if constexpr (constexpr lookup$magic_lut<entries> lookup{}; lookup) {
      return lookup(key);
    } else {
      return type_traits::constant_t<lookup$pext<entries>>::value(key);
    }
  };

/**
 * Static perfect hash find function
 * @tparam entries constexpr array of keys or key/value pairs
 */
template<const auto& entries> inline constexpr auto find =
  []<u8 probability = 50u>
    requires (probability >= 0u and probability <= 100u)
    #if not __has_include(<experimental/simd>)
    and (entries.size() <= 64u)
    #endif
    ([[maybe_unused]] const auto& key, [[maybe_unused]] const auto&... ts) {
    using key_type = typename detail::traits<entries>::key_type;
    using mapped_type = typename detail::traits<entries>::mapped_type;
    using result_type = optional<mapped_type>;
    if constexpr (entries.size() == 0u) {
      return result_type(ts...);
    } else if constexpr (entries.size() == 1u) {
      auto&& lhs = to<key_type>(key);
      auto&& [rhs, value] = detail::traits<entries>::mappings[0];
      return conditional<probability>(lhs == rhs, result_type(value), result_type(ts...));
    } else if constexpr (entries.size() <= 64u) {
      return type_traits::constant_t<find$pext<entries>>::value.template
        operator()<probability>(key, ts...);
    }
    #if __has_include(<experimental/simd>)
    else {
      constexpr auto bucket_size = std::experimental::simd_size_v<key_type, std::experimental::simd_abi::native<key_type>>;
      return type_traits::constant_t<find$simd<entries, bucket_size>>::value.template
        operator()<probability>(key, ts...);
    }
    #endif
  };
} // namespace mph

#ifndef NTEST
static_assert(([] {
  constexpr auto expect = [](bool cond) { if (not cond) { void failed(); failed(); } };

  // mph::utility::compressed_pair
  {
    static_assert(1 == mph::utility::compressed_pair{1, 2}.first);
    static_assert(2 == mph::utility::compressed_pair{1, 2}.second);
    static_assert(sizeof(int) + sizeof(int) == sizeof(mph::utility::compressed_pair{int{}, int{}}));
    struct empty { };
    static_assert(sizeof(int) == sizeof(mph::utility::compressed_pair{empty{}, 42}));
    static_assert(sizeof(int) == sizeof(mph::utility::compressed_pair{42, empty{}}));
    static_assert(sizeof(empty) + sizeof(empty) == sizeof(mph::utility::compressed_pair{empty{}, empty{}}));
  }

  // mph::utility::array
  {
    {
      mph::utility::array<mph::u32, 1> a{};
      expect(1 == a.size());
    }

    {
      mph::utility::array a{1, 2};
      expect(2u == a.size());
      expect(1 == a[0]);
      expect(2 == a[1]);
    }

    {
      mph::utility::array a{1};
      a[0] = 2;
      expect(2 == a[0]);
    }

    {
      mph::utility::array a{1, 2, 3};
      expect(3u == a.size());
      expect(a.begin() != a.end());
      expect(a.size() == mph::u32(a.end() - a.begin()));
      expect(a.end() == a.begin() + a.size());
    }
  }

  // mph::utility::constant{_v}
  {
    static_assert(0 == mph::type_traits::constant<0>::value);
    static_assert(0 == mph::type_traits::constant_v<0>);
    static_assert(42 == mph::type_traits::constant<42>{});
    static_assert(42 == mph::type_traits::constant_v<42>);
    static_assert(42u == mph::type_traits::constant<42u>::value);
    static_assert('X' == mph::type_traits::constant<'X'>::value);
    static_assert('X' == mph::type_traits::constant_v<'X'>);
  }

  // mph::type_traits::conditional_t
  {
    using mph::u32;
    using mph::u64;

    static_assert(sizeof(u32) == sizeof(mph::type_traits::conditional_t<true, u32, u64>));
    static_assert(sizeof(u64) == sizeof(mph::type_traits::conditional_t<false, u32, u64>));
  }

  // mph::random
  {
    mph::random::pcg random{};
    expect(random() != random());
  }

  // mph::detail::pext
  {
    using mph::u32;

    static_assert(0    == mph::detail::pext(0b00, 0b00));
    static_assert(0    == mph::detail::pext(0b01, 0b00));
    static_assert(0b1  == mph::detail::pext(0b01, 0b01));
    static_assert(0b01 == mph::detail::pext(0b01, 0b11));
    static_assert(0b0  == mph::detail::pext(0b01, 0b10));
    static_assert(0b1  == mph::detail::pext(0b11, 0b10));
    static_assert(0b1  == mph::detail::pext(0b11, 0b01));
    static_assert(0b11 == mph::detail::pext(0b11, 0b11));
  }

  // mph::detail::mask
  {
    using mph::u32;
    using mph::utility::array;
    using mph::utility::compressed_pair;

    static_assert(0b01 == mph::detail::mask<u32, 1u>(array{compressed_pair{0b10, 0}, compressed_pair{0b11, 0}}));
    static_assert(0b10 == mph::detail::mask<u32, 1u>(array{compressed_pair{0b01, 0}, compressed_pair{0b11, 0}}));
    static_assert(0b10 == mph::detail::mask<u32, 1u>(array{compressed_pair{0b11, 0}, compressed_pair{0b01, 0}}));
    static_assert(0b01 == mph::detail::mask<u32, 1u>(array{compressed_pair{0b11, 0}, compressed_pair{0b10, 0}}));
    static_assert(0b01 == mph::detail::mask<u32, 1u>(array{compressed_pair{0b01, 0}, compressed_pair{0b10, 0}}));
    static_assert(0b01 == mph::detail::mask<u32, 1u>(array{compressed_pair{0b10, 0}, compressed_pair{0b01, 0}}));
    static_assert(0b11 == mph::detail::mask<u32, 1u>(array{compressed_pair{0b11, 0}, compressed_pair{0b11, 0}}));
  }

  // mph::detail::narrow_mask
  {
    using mph::u32;
    using mph::u64;
    using mph::utility::array;
    using mph::utility::compressed_pair;

    static_assert(sizeof(mph::detail::narrow_mask<array{compressed_pair{u32{1}, 0}, compressed_pair{u32{1}<<1, 0}}>())==sizeof(u32));
    static_assert(sizeof(mph::detail::narrow_mask<array{compressed_pair{u64{1}, 0}, compressed_pair{u64{1}<<32, 0}}>())==sizeof(u32));
    static_assert(sizeof(mph::detail::narrow_mask<array{compressed_pair{u64{1}<<32, 0}, compressed_pair{u64{1}<<33, 0}}>())==sizeof(u64));
  }

  // mph::datail::traits
  {
    using mph::u8;
    using mph::u32;
    using mph::utility::compressed_pair;
    using mph::utility::array;
    using mph::type_traits::constant;

    {
      constexpr const auto& entries = constant<array{u32(4)}>::value;
      constexpr const auto v = mph::detail::traits<entries>::mappings;
      static_assert(1u == v.size());
      static_assert(u32(4) == v[0].first);
      static_assert(u8(0) == v[0].second);
    }

    {
      constexpr const auto& entries = constant<array{u32(4), u32(2)}>::value;
      constexpr const auto v = mph::detail::traits<entries>::mappings;
      static_assert(2u == v.size());
      static_assert(u32(4) == v[0].first);
      static_assert(u32(2) == v[1].first);
      static_assert(u8(0) == v[0].second);
      static_assert(u8(1) == v[1].second);
    }
  }

  // mph::conditional
  {
    static_assert(0 == mph::conditional<0u>(true, 1, 0));
    static_assert(0 == mph::conditional<0u>(false, 1, 0));
    static_assert(1 == mph::conditional<50u>(true, 1, 0));
    static_assert(0 == mph::conditional<50u>(false, 1, 0));
    static_assert(1 == mph::conditional<100u>(true, 1, 0));
    static_assert(1 == mph::conditional<100u>(false, 1, 0));
  }

  // mph::optional
  {
    using mph::u32;

    static_assert(not [](auto value) { return requires { mph::optional<u32>(value); }; }(""));
    static_assert([](auto value) { return requires { mph::optional<u32>(value); }; }(u32{}));

    static_assert(not mph::optional<u32>{});
    static_assert(not mph::optional<u32>{u32{}, false});
    static_assert(mph::optional<u32>{42});
    static_assert(42 == *mph::optional<u32>{42});
    static_assert(mph::optional<bool>{true});
    static_assert(*mph::optional<bool>{true});
    static_assert(mph::optional<bool>{false});
    static_assert(not *mph::optional<bool>{false});
  }

  // mph::to
  {
    using mph::u32;
    using mph::utility::array;

    static_assert(0 == mph::to<u32>(0));
    static_assert(42 == mph::to<u32>(42));
    static_assert(42u == mph::to<u32>(42u));
    static_assert(0 == mph::to<u32>(""));
    static_assert((u32('A') << 0) + (u32('B') << __CHAR_BIT__) == mph::to<u32>("AB"));
    static_assert((u32('A') << 0) + (u32('B') << __CHAR_BIT__) + (u32('C') << __CHAR_BIT__*2) == mph::to<u32>("ABC"));
    static_assert((u32('A') << 0) + (u32('B') << __CHAR_BIT__) == mph::to<u32>(array{'A','B'}));
    static_assert((u32('A') << 0) + (u32('B') << __CHAR_BIT__) + (u32('C') << __CHAR_BIT__*2) == mph::to<u32>(array{'A','B','C'}));
  }

  // mph::lookup
  {
    using mph::u16;
    using mph::u32;
    using mph::u64;
    using mph::utility::compressed_pair;
    using mph::utility::array;
    using mph::type_traits::constant;

    // integral
    {
      {
        constexpr const auto& entries = constant<array{
          compressed_pair{u32(4), u32(2)}
        }>::value;

        auto lookup = mph::lookup<entries>;

        static_assert(2 == lookup(u32(4)));
      }

      {
        constexpr const auto& entries = constant<[] {
          std::array<int, 512> a{};
          auto count = 0;
          for (auto &v : a) v = count++;
          return a;
        }()>::value;

        static_assert(0 == mph::lookup<entries>(u16(0)));
        static_assert(1 == mph::lookup<entries>(u16(1)));
        static_assert(128 == mph::lookup<entries>(u16(128)));
        static_assert(255 == mph::lookup<entries>(u16(255)));
        static_assert(256 == mph::lookup<entries>(u16(256)));
        static_assert(entries.size()-1 == mph::lookup<entries>(u16(entries.size()-1)));
      }

      {
        constexpr const auto& entries = constant<array{
          compressed_pair{u32(4), u32(2)},
          compressed_pair{u32(42), u32(87)},
          compressed_pair{u32(100), u32(100)},
        }>::value;

        static_assert(2 == mph::lookup<entries>(u32(4)));
        static_assert(87 == mph::lookup<entries>(u32(42)));
        static_assert(100 == mph::lookup<entries>(u32(100)));
      }

      {
        constexpr const auto& entries = constant<array{
          compressed_pair{u64{4}<<32, u32(2)},
          compressed_pair{u64{42}<<32, u32(87)},
          compressed_pair{u64{100}<<32, u32(100)},
        }>::value;

        static_assert(2 == mph::lookup$pext<entries>{}(u64{4}<<32));
        static_assert(87 == mph::lookup<entries>(u64{42}<<32));
        static_assert(100 == mph::lookup<entries>(u64{100}<<32));
      }

      {
        enum class color { red, green, blue };

        constexpr const auto& entries = constant<array{
          compressed_pair{color::red, 0},
          compressed_pair{color::green, 1},
          compressed_pair{color::blue, 2},
        }>::value;

        static_assert(0 == mph::lookup<entries>(color::red));
        static_assert(1 == mph::lookup<entries>(color::green));
        static_assert(2 == mph::lookup<entries>(color::blue));
      }
    }

    // string-like
    {
      using mph::to;

      {
        constexpr const auto& entries = constant<array{
          compressed_pair{to<u32>("BTC"), 1},
          compressed_pair{to<u32>("ETH"), 2},
          compressed_pair{to<u32>("XRP"), 3},
        }>::value;

        static_assert(1 == mph::lookup<entries>("BTC"));
        static_assert(2 == mph::lookup<entries>("ETH"));
        static_assert(3 == mph::lookup<entries>("XRP"));
      }
    }
  }

  // mph::find
  {
    using mph::u32;
    using mph::u64;
    using mph::utility::compressed_pair;
    using mph::utility::array;
    using mph::type_traits::constant;

    // integral
    {
      {
        constexpr const auto& entries = constant<array{
          compressed_pair{u32(4), u32(2)}
        }>::value;

        auto find = mph::find<entries>;

        static_assert(not find(u32(0)));
        static_assert(not find(u32(1)));
        static_assert(find(u32(4)));

        static_assert(0 == *find(u32(0)));
        static_assert(0 == *find(u32(1)));
        static_assert(2 == *find(u32(4)));
      }

      {
        constexpr const auto& entries = constant<array{
          compressed_pair{u32(4), u32(2)},
          compressed_pair{u32(42), u32(87)},
          compressed_pair{u32(100), u32(100)},
        }>::value;

        static_assert(not mph::find<entries>(u32(0)));
        static_assert(mph::find<entries>(u32(4)));
        static_assert(mph::find<entries>(u32(42)));
        static_assert(mph::find<entries>(u32(100)));

        static_assert(0 == *mph::find<entries>(u32(0)));
        static_assert(2 == *mph::find<entries>(u32(4)));
        static_assert(87 == *mph::find<entries>(u32(42)));
        static_assert(100 == *mph::find<entries>(u32(100)));
      }

      {
        constexpr const auto& entries = constant<array{
          compressed_pair{u64(4)<<32, u32(2)},
          compressed_pair{u64(42)<<32, u32(87)},
          compressed_pair{u64(100)<<32, u32(100)},
        }>::value;

        static_assert(not mph::find<entries>(u64(0)));
        static_assert(mph::find<entries>(u64(4)<<32));
        static_assert(mph::find<entries>(u64(42)<<32));
        static_assert(mph::find<entries>(u64(100)<<32));

        static_assert(0 == *mph::find<entries>(u64(0)));
        static_assert(2 == *mph::find<entries>(u64(4)<<32));
        static_assert(87 == *mph::find<entries>(u64(42)<<32));
        static_assert(100 == *mph::find<entries>(u64(100)<<32));
      }

      {
        constexpr const auto& entries = constant<array{
          compressed_pair{u32(9), u32(0)},
          compressed_pair{u32(6), u32(1)},
          compressed_pair{u32(14), u32(2)},
          compressed_pair{u32(11), u32(3)},
        }>::value;

        static_assert(not mph::find<entries>(u32(42)));

        static_assert(0 == *mph::find<entries>(u32(9)));
        static_assert(1 == *mph::find<entries>(u32(6)));
        static_assert(2 == *mph::find<entries>(u32(14)));
        static_assert(3 == *mph::find<entries>(u32(11)));
      }

      {
        enum class color { red, green, blue };

        constexpr const auto& entries = constant<array{
          compressed_pair{color::red, 0},
          compressed_pair{color::green, 1},
          compressed_pair{color::blue, 2},
        }>::value;

        static_assert(mph::find<entries>(color::red));
        static_assert(mph::find<entries>(color::green));
        static_assert(mph::find<entries>(color::blue));

        static_assert(0 == *mph::find<entries>(color::red));
        static_assert(1 == *mph::find<entries>(color::green));
        static_assert(2 == *mph::find<entries>(color::blue));
      }
    }

    // string-like
    {
      using mph::to;

      {
        constexpr const auto& entries = constant<array{
          compressed_pair{to<u32>("BTC"), 1},
          compressed_pair{to<u32>("ETH"), 2},
          compressed_pair{to<u32>("XRP"), 3},
        }>::value;

        static_assert(not mph::find<entries>(""));
        static_assert(mph::find<entries>("BTC"));
        static_assert(mph::find<entries>("ETH"));
        static_assert(mph::find<entries>("XRP"));

        static_assert(0 == *mph::find<entries>(""));
        static_assert(1 == *mph::find<entries>("BTC"));
        static_assert(2 == *mph::find<entries>("ETH"));
        static_assert(3 == *mph::find<entries>("XRP"));
      }
    }
  }
}(), true));
#endif // NTEST