1 /* $OpenBSD: toeplitz.c,v 1.9 2020/09/01 19:18:26 tb Exp $ */ 2 3 /* 4 * Copyright (c) 2009 The DragonFly Project. All rights reserved. 5 * 6 * This code is derived from software contributed to The DragonFly Project 7 * by Sepherosa Ziehau <sepherosa (at) gmail.com> 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in 17 * the documentation and/or other materials provided with the 18 * distribution. 19 * 3. Neither the name of The DragonFly Project nor the names of its 20 * contributors may be used to endorse or promote products derived 21 * from this software without specific, prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 26 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 27 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 28 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 29 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 30 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 31 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 32 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 33 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 */ 36 37 /* 38 * Copyright (c) 2019 David Gwynne <dlg (at) openbsd.org> 39 * Copyright (c) 2020 Theo Buehler <tb (at) openbsd.org> 40 * 41 * Permission to use, copy, modify, and distribute this software for any 42 * purpose with or without fee is hereby granted, provided that the above 43 * copyright notice and this permission notice appear in all copies. 44 * 45 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 46 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 47 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 48 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 49 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 50 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 51 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 52 */ 53 54 /*- 55 * Copyright (c) 2019 Ryo Shimizu 56 * All rights reserved. 57 * 58 * Redistribution and use in source and binary forms, with or without 59 * modification, are permitted provided that the following conditions 60 * are met: 61 * 1. Redistributions of source code must retain the above copyright 62 * notice, this list of conditions and the following disclaimer. 63 * 2. Redistributions in binary form must reproduce the above copyright 64 * notice, this list of conditions and the following disclaimer in the 65 * documentation and/or other materials provided with the distribution. 66 * 67 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS 68 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 69 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 70 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, 71 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 72 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 73 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 74 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 75 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 76 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 77 * POSSIBILITY OF SUCH DAMAGE. 78 */ 79 80 #include <sys/param.h> 81 #include <sys/systm.h> 82 #include <sys/kernel.h> 83 #include <sys/sysctl.h> 84 #include <sys/cprng.h> 85 86 #include <netinet/in.h> 87 88 #include <net/toeplitz.h> 89 90 /* 91 * symmetric toeplitz 92 */ 93 94 static stoeplitz_key stoeplitz_keyseed = STOEPLITZ_KEYSEED; 95 static struct stoeplitz_cache stoeplitz_syskey_cache; 96 const struct stoeplitz_cache *const 97 stoeplitz_cache = &stoeplitz_syskey_cache; 98 99 /* parity of n16: count (mod 2) of ones in the binary representation. */ 100 static int 101 parity(uint16_t n16) 102 { 103 n16 = ((n16 & 0xaaaa) >> 1) ^ (n16 & 0x5555); 104 n16 = ((n16 & 0xcccc) >> 2) ^ (n16 & 0x3333); 105 n16 = ((n16 & 0xf0f0) >> 4) ^ (n16 & 0x0f0f); 106 n16 = ((n16 & 0xff00) >> 8) ^ (n16 & 0x00ff); 107 108 return (n16); 109 } 110 111 /* 112 * The Toeplitz matrix obtained from a seed is invertible if and only if the 113 * parity of the seed is 1. Generate such a seed uniformly at random. 114 */ 115 static stoeplitz_key 116 stoeplitz_random_seed(void) 117 { 118 stoeplitz_key seed; 119 120 seed = cprng_strong32() & UINT16_MAX; 121 if (parity(seed) == 0) 122 seed ^= 1; 123 124 return (seed); 125 } 126 127 void 128 stoeplitz_init(void) 129 { 130 stoeplitz_keyseed = stoeplitz_random_seed(); 131 stoeplitz_cache_init(&stoeplitz_syskey_cache, stoeplitz_keyseed); 132 } 133 134 #define NBSK (NBBY * sizeof(stoeplitz_key)) 135 136 /* 137 * The Toeplitz hash of a 16-bit number considered as a column vector over 138 * the field with two elements is calculated as a matrix multiplication with 139 * a 16x16 circulant Toeplitz matrix T generated by skey. 140 * 141 * The first eight columns H of T generate the remaining eight columns using 142 * the byteswap operation J = swap16: T = [H JH]. Thus, the Toeplitz hash of 143 * n = [hi lo] is computed via the formula T * n = (H * hi) ^ swap16(H * lo). 144 * 145 * Therefore the results H * val for all values of a byte are cached in scache. 146 */ 147 void 148 stoeplitz_cache_init(struct stoeplitz_cache *scache, stoeplitz_key skey) 149 { 150 uint16_t column[NBBY]; 151 unsigned int b, shift, val; 152 153 bzero(column, sizeof(column)); 154 155 /* Calculate the first eight columns H of the Toeplitz matrix T. */ 156 for (b = 0; b < NBBY; ++b) 157 column[b] = skey << b | skey >> (NBSK - b); 158 159 /* Cache the results of H * val for all possible values of a byte. */ 160 for (val = 0; val < 256; ++val) { 161 uint16_t res = 0; 162 163 for (b = 0; b < NBBY; ++b) { 164 shift = NBBY - b - 1; 165 if (val & (1 << shift)) 166 res ^= column[b]; 167 } 168 scache->bytes[val] = res; 169 } 170 } 171 172 uint16_t 173 stoeplitz_hash_ip4(const struct stoeplitz_cache *scache, 174 in_addr_t faddr, in_addr_t laddr) 175 { 176 return (stoeplitz_hash_n32(scache, faddr ^ laddr)); 177 } 178 179 uint16_t 180 stoeplitz_hash_ip4port(const struct stoeplitz_cache *scache, 181 in_addr_t faddr, in_addr_t laddr, in_port_t fport, in_port_t lport) 182 { 183 return (stoeplitz_hash_n32(scache, faddr ^ laddr ^ fport ^ lport)); 184 } 185 186 #ifdef INET6 187 uint16_t 188 stoeplitz_hash_ip6(const struct stoeplitz_cache *scache, 189 const struct in6_addr *faddr6, const struct in6_addr *laddr6) 190 { 191 uint32_t n32 = 0; 192 size_t i; 193 194 for (i = 0; i < __arraycount(faddr6->s6_addr32); i++) 195 n32 ^= faddr6->s6_addr32[i] ^ laddr6->s6_addr32[i]; 196 197 return (stoeplitz_hash_n32(scache, n32)); 198 } 199 200 uint16_t 201 stoeplitz_hash_ip6port(const struct stoeplitz_cache *scache, 202 const struct in6_addr *faddr6, const struct in6_addr *laddr6, 203 in_port_t fport, in_port_t lport) 204 { 205 uint32_t n32 = 0; 206 size_t i; 207 208 for (i = 0; i < __arraycount(faddr6->s6_addr32); i++) 209 n32 ^= faddr6->s6_addr32[i] ^ laddr6->s6_addr32[i]; 210 211 n32 ^= fport ^ lport; 212 213 return (stoeplitz_hash_n32(scache, n32)); 214 } 215 #endif /* INET6 */ 216 217 void 218 stoeplitz_to_key(void *key, size_t klen) 219 { 220 uint8_t *k = key; 221 uint16_t skey = htons(stoeplitz_keyseed); 222 size_t i; 223 224 KASSERT((klen % 2) == 0); 225 226 for (i = 0; i < klen; i += sizeof(skey)) { 227 k[i + 0] = skey >> 8; 228 k[i + 1] = skey; 229 } 230 } 231 232 /* 233 * e.g.) 234 * 235 * struct in_addr src, dst; 236 * uint16_t srcport, dstport; 237 * toeplitz_vhash(rsskey[], sizeof(rsskey), 238 * &src, sizeof(src), 239 * &dst, sizeof(dst), 240 * &srcport, sizeof(srcport), 241 * &dstport, sizeof(dstport), 242 * NULL); 243 * 244 * struct in6_addr src6, dst6; 245 * toeplitz_vhash(rsskey[], sizeof(rsskey), 246 * &src6, sizeof(src6), 247 * &dst6, sizeof(dst6), 248 * NULL); 249 * 250 * struct ip *ip; 251 * struct tcphdr *tcp; 252 * toeplitz_vhash(rsskey[], sizeof(rsskey), 253 * &ip->ip_src, sizeof(ip->ip_src), 254 * &ip->ip_dst, sizeof(ip->ip_dst), 255 * &tcp->th_sport, sizeof(tcp->th_sport), 256 * &tcp->th_dport, sizeof(tcp->th_dport), 257 * NULL); 258 * 259 */ 260 uint32_t 261 toeplitz_vhash(const uint8_t *keyp, size_t keylen, ...) 262 { 263 va_list ap; 264 uint32_t hash, v; 265 size_t datalen; 266 uint8_t *datap, key, data; 267 const uint8_t *keyend; 268 269 keyend = keyp + keylen; 270 271 /* first 32bit is initial vector */ 272 v = *keyp++; 273 v <<= 8; 274 v |= *keyp++; 275 v <<= 8; 276 v |= *keyp++; 277 v <<= 8; 278 v |= *keyp++; 279 280 hash = 0; 281 va_start(ap, keylen); 282 283 while ((datap = va_arg(ap, uint8_t *)) != NULL) { 284 for (datalen = va_arg(ap, size_t); datalen > 0; datalen--) { 285 /* fetch key and input data by 8bit */ 286 if (keyp < keyend) 287 key = *keyp++; 288 else 289 key = 0; 290 data = *datap++; 291 292 #define XOR_AND_FETCH_BIT(x) \ 293 if (data & __BIT(x)) \ 294 hash ^= v; \ 295 v <<= 1; \ 296 if (key & __BIT(x)) \ 297 v |= 1; 298 299 XOR_AND_FETCH_BIT(7); 300 XOR_AND_FETCH_BIT(6); 301 XOR_AND_FETCH_BIT(5); 302 XOR_AND_FETCH_BIT(4); 303 XOR_AND_FETCH_BIT(3); 304 XOR_AND_FETCH_BIT(2); 305 XOR_AND_FETCH_BIT(1); 306 XOR_AND_FETCH_BIT(0); 307 308 #undef XOR_AND_FETCH_BIT 309 } 310 } 311 va_end(ap); 312 313 return hash; 314 } 315
Indexes created Sun Sep 21 20:09:37 GMT 2025