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