Interleave lower bits of x and y, so the bits of x * are in the even positions and bits from y in the odd; * x and y must initially be less than 2**32 (65536). * From: https://graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN */
| 50 | * From: https://graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN |
| 51 | */ |
| 52 | static inline uint64_t interleave64(uint32_t xlo, uint32_t ylo) { |
| 53 | static const uint64_t B[] = {0x5555555555555555ULL, 0x3333333333333333ULL, |
| 54 | 0x0F0F0F0F0F0F0F0FULL, 0x00FF00FF00FF00FFULL, |
| 55 | 0x0000FFFF0000FFFFULL}; |
| 56 | static const unsigned int S[] = {1, 2, 4, 8, 16}; |
| 57 | |
| 58 | uint64_t x = xlo; |
| 59 | uint64_t y = ylo; |
| 60 | |
| 61 | x = (x | (x << S[4])) & B[4]; |
| 62 | y = (y | (y << S[4])) & B[4]; |
| 63 | |
| 64 | x = (x | (x << S[3])) & B[3]; |
| 65 | y = (y | (y << S[3])) & B[3]; |
| 66 | |
| 67 | x = (x | (x << S[2])) & B[2]; |
| 68 | y = (y | (y << S[2])) & B[2]; |
| 69 | |
| 70 | x = (x | (x << S[1])) & B[1]; |
| 71 | y = (y | (y << S[1])) & B[1]; |
| 72 | |
| 73 | x = (x | (x << S[0])) & B[0]; |
| 74 | y = (y | (y << S[0])) & B[0]; |
| 75 | |
| 76 | return x | (y << 1); |
| 77 | } |
| 78 | |
| 79 | /* reverse the interleave process |
| 80 | * derived from http://stackoverflow.com/questions/4909263 |