#include <stdio.h> #define U64 unsigned long long #define C64(x) x##ULL U64 flipDiagA1H8(U64 x) { U64 t; const U64 k1 = C64(0x5500550055005500); const U64 k2 = C64(0x3333000033330000); const U64 k4 = C64(0x0f0f0f0f00000000); t = k4 & (x ^ (x << 28)); x ^= t ^ (t >> 28) ; t = k2 & (x ^ (x << 14)); x ^= t ^ (t >> 14) ; t = k1 & (x ^ (x << 7)); x ^= t ^ (t >> 7) ; return x; } U64 flipVertical(U64 x) { return ( (x << 56) ) | ( (x << 40) & C64(0x00ff000000000000) ) | ( (x << 24) & C64(0x0000ff0000000000) ) | ( (x << 8) & C64(0x000000ff00000000) ) | ( (x >> 8) & C64(0x00000000ff000000) ) | ( (x >> 24) & C64(0x0000000000ff0000) ) | ( (x >> 40) & C64(0x000000000000ff00) ) | ( (x >> 56) ); } U64 hashword(U64 x) { // Made up of four parts // Flip along antidiagonal U64 x1 = flipDiagA1H8(x); // Flip vertically x1 = flipVertical(x1); // XOR x1 = x ^ x1; // Add one x1++; return x1; } int main() { U64 input = 0; U64 output = 0; int collisions = 0; printf("Small values:\n"); for (input = 0; input < 16; input++) { printf("Input: %016llx\n", input); output = hashword(input); printf("Output: %016llx\n\n", output); } printf("Large values:\n"); for (input = 0xFFFFFFFFFF; input < 0xFFFFFFFFFF + 16; input++) { printf("Input: %016llx\n", input); output = hashword(input); printf("Output: %016llx\n\n", output); } return 0; }
Standard input is empty
Small values: Input: 0000000000000000 Output: 0000000000000001 Input: 0000000000000001 Output: 0100000000000002 Input: 0000000000000002 Output: 0001000000000003 Input: 0000000000000003 Output: 0101000000000004 Input: 0000000000000004 Output: 0000010000000005 Input: 0000000000000005 Output: 0100010000000006 Input: 0000000000000006 Output: 0001010000000007 Input: 0000000000000007 Output: 0101010000000008 Input: 0000000000000008 Output: 0000000100000009 Input: 0000000000000009 Output: 010000010000000a Input: 000000000000000a Output: 000100010000000b Input: 000000000000000b Output: 010100010000000c Input: 000000000000000c Output: 000001010000000d Input: 000000000000000d Output: 010001010000000e Input: 000000000000000e Output: 000101010000000f Input: 000000000000000f Output: 0101010100000010 Large values: Input: 000000ffffffffff Output: 1f1f1fe0e0e0e0e1 Input: 0000010000000000 Output: 2000010000000001 Input: 0000010000000001 Output: 2100010000000002 Input: 0000010000000002 Output: 2001010000000003 Input: 0000010000000003 Output: 2101010000000004 Input: 0000010000000004 Output: 2000000000000005 Input: 0000010000000005 Output: 2100000000000006 Input: 0000010000000006 Output: 2001000000000007 Input: 0000010000000007 Output: 2101000000000008 Input: 0000010000000008 Output: 2000010100000009 Input: 0000010000000009 Output: 210001010000000a Input: 000001000000000a Output: 200101010000000b Input: 000001000000000b Output: 210101010000000c Input: 000001000000000c Output: 200000010000000d Input: 000001000000000d Output: 210000010000000e Input: 000001000000000e Output: 200100010000000f