1 #include <sys/types.h> 2 #include <sys/socket.h> 3 4 #include <arpa/inet.h> 5 #include <netinet/in.h> 6 7 #include <stdint.h> 8 #include <stdio.h> 9 #include <stdlib.h> 10 #include <string.h> 11 #include <unistd.h> 12 13 #define HASHMASK 0x7f 14 15 #define KEYLEN 40 16 #define HASHLEN 12 17 18 static uint8_t toeplitz_key[KEYLEN]; 19 static uint32_t hash_table[HASHLEN][256]; 20 21 static void toeplitz_init(uint32_t[][256], int, const uint8_t[], int); 22 static void getaddrport(char *, uint32_t *, uint16_t *); 23 24 static void 25 usage(const char *cmd) 26 { 27 fprintf(stderr, "%s [-s s1_hex [-s s2_hex]] [-p] [-m mask] [-d div] " 28 "addr1.port1 addr2.port2\n", cmd); 29 exit(1); 30 } 31 32 int 33 main(int argc, char *argv[]) 34 { 35 uint32_t saddr, daddr; 36 uint16_t sport, dport; 37 uint32_t res, mask, divisor; 38 39 const char *cmd = argv[0]; 40 uint8_t seeds[2] = { 0x6d, 0x5a }; 41 int i, opt, use_port; 42 43 i = 0; 44 use_port = 0; 45 mask = 0xffffffff; 46 divisor = 0; 47 48 while ((opt = getopt(argc, argv, "d:m:ps:")) != -1) { 49 switch (opt) { 50 case 'd': 51 divisor = strtoul(optarg, NULL, 10); 52 break; 53 54 case 'm': 55 mask = strtoul(optarg, NULL, 16); 56 break; 57 58 case 'p': 59 use_port = 1; 60 break; 61 62 case 's': 63 if (i >= 2) 64 usage(cmd); 65 seeds[i++] = strtoul(optarg, NULL, 16); 66 break; 67 68 default: 69 usage(cmd); 70 } 71 } 72 argc -= optind; 73 argv += optind; 74 75 if (argc != 2) 76 usage(cmd); 77 78 for (i = 0; i < KEYLEN; ++i) { 79 if (i & 1) 80 toeplitz_key[i] = seeds[1]; 81 else 82 toeplitz_key[i] = seeds[0]; 83 } 84 85 getaddrport(argv[0], &saddr, &sport); 86 getaddrport(argv[1], &daddr, &dport); 87 88 toeplitz_init(hash_table, HASHLEN, toeplitz_key, KEYLEN); 89 90 res = hash_table[0][(saddr >> 0) & 0xff]; 91 res ^= hash_table[1][(saddr >> 8) & 0xff]; 92 res ^= hash_table[2][(saddr >> 16) & 0xff]; 93 res ^= hash_table[3][(saddr >> 24) & 0xff]; 94 res ^= hash_table[4][(daddr >> 0) & 0xff]; 95 res ^= hash_table[5][(daddr >> 8) & 0xff]; 96 res ^= hash_table[6][(daddr >> 16) & 0xff]; 97 res ^= hash_table[7][(daddr >> 24) & 0xff]; 98 if (use_port) { 99 res ^= hash_table[8][(sport >> 0) & 0xff]; 100 res ^= hash_table[9][(sport >> 8) & 0xff]; 101 res ^= hash_table[10][(dport >> 0) & 0xff]; 102 res ^= hash_table[11][(dport >> 8) & 0xff]; 103 } 104 105 printf("0x%08x, masked 0x%08x", res, res & mask); 106 if (divisor == 0) 107 printf("\n"); 108 else 109 printf(", modulo %u\n", (res & HASHMASK) % divisor); 110 exit(0); 111 } 112 113 static void 114 toeplitz_init(uint32_t cache[][256], int cache_len, 115 const uint8_t key_str[], int key_strlen) 116 { 117 int i; 118 119 if (key_strlen < cache_len + (int)sizeof(uint32_t)) 120 exit(1); 121 122 for (i = 0; i < cache_len; ++i) { 123 uint32_t key[NBBY]; 124 int j, b, shift, val; 125 126 bzero(key, sizeof(key)); 127 128 /* 129 * Calculate 32bit keys for one byte; one key for each bit. 130 */ 131 for (b = 0; b < NBBY; ++b) { 132 for (j = 0; j < 32; ++j) { 133 uint8_t k; 134 int bit; 135 136 bit = (i * NBBY) + b + j; 137 138 k = key_str[bit / NBBY]; 139 shift = NBBY - (bit % NBBY) - 1; 140 if (k & (1 << shift)) 141 key[b] |= 1 << (31 - j); 142 } 143 } 144 145 /* 146 * Cache the results of all possible bit combination of 147 * one byte. 148 */ 149 for (val = 0; val < 256; ++val) { 150 uint32_t res = 0; 151 152 for (b = 0; b < NBBY; ++b) { 153 shift = NBBY - b - 1; 154 if (val & (1 << shift)) 155 res ^= key[b]; 156 } 157 cache[i][val] = res; 158 } 159 } 160 } 161 162 static void 163 getaddrport(char *ap_str, uint32_t *addr, uint16_t *port0) 164 { 165 uint16_t port; 166 char *p; 167 168 p = strrchr(ap_str, '.'); 169 if (p == NULL) { 170 fprintf(stderr, "invalid addr.port %s\n", ap_str); 171 exit(1); 172 } 173 174 *p = '\0'; 175 ++p; 176 177 port = strtoul(p, NULL, 10); 178 *port0 = htons(port); 179 180 if (inet_pton(AF_INET, ap_str, addr) <= 0) { 181 fprintf(stderr, "invalid addr %s\n", ap_str); 182 exit(1); 183 } 184 } 185