| 38 | // D (1, 1) 00 C |
| 39 | template <int N = 32, typename T = std::uint32_t, typename R = std::uint64_t> |
| 40 | inline R HilbertToLinear(T x, T y) |
| 41 | { |
| 42 | static_assert(N <= sizeof(T) * CHAR_BIT, "input type is smaller than N"); |
| 43 | static_assert(2 * N <= sizeof(R) * CHAR_BIT, "output type is smaller than 2N"); |
| 44 | |
| 45 | R result = 0; |
| 46 | unsigned state = 0; |
| 47 | for (int i = 0; i < N; ++i) |
| 48 | { |
| 49 | const unsigned xi = (x >> (sizeof(T) * CHAR_BIT - 1)) & 1; |
| 50 | const unsigned yi = (y >> (sizeof(T) * CHAR_BIT - 1)) & 1; |
| 51 | x <<= 1; |
| 52 | y <<= 1; |
| 53 | |
| 54 | const unsigned row = 4 * state | 2 * xi | yi; |
| 55 | result = (result << 2) | ((0x361E9CB4 >> 2 * row) & 3); |
| 56 | state = (0x8FE65831 >> 2 * row) & 3; |
| 57 | } |
| 58 | return result; |
| 59 | } |
| 60 | |
| 61 | // Computes a 64 bit value that corresponds to the hilbert space filling curve |
| 62 | inline std::uint64_t GetHilbertCode(const Coordinate &coordinate) |