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 #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 }