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