1 /* $OpenBSD: toeplitz.h,v 1.3 2020/06/19 08:48:15 dlg Exp $ */
2
3 /*
4 * Copyright (c) 2019 David Gwynne <dlg@openbsd.org>
5 *
6 * Permission to use, copy, modify, and distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
9 *
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 */
18
19 #ifndef _SYS_NET_TOEPLITZ_H_
20 #define _SYS_NET_TOEPLITZ_H_
21
22 #ifdef _KERNEL_OPT
23 #include "opt_inet.h"
24 #endif
25
26 #include <sys/endian.h>
27
28 /*
29 * symmetric toeplitz
30 */
31
32 typedef uint16_t stoeplitz_key;
33
34 struct stoeplitz_cache {
35 uint16_t bytes[256];
36 };
37
38 static __unused inline uint16_t
stoeplitz_cache_entry(const struct stoeplitz_cache * scache,uint8_t byte)39 stoeplitz_cache_entry(const struct stoeplitz_cache *scache, uint8_t byte)
40 {
41 return (scache->bytes[byte]);
42 }
43
44 void stoeplitz_cache_init(struct stoeplitz_cache *, stoeplitz_key);
45
46 uint16_t stoeplitz_hash_ip4(const struct stoeplitz_cache *,
47 uint32_t, uint32_t);
48 uint16_t stoeplitz_hash_ip4port(const struct stoeplitz_cache *,
49 uint32_t, uint32_t, uint16_t, uint16_t);
50
51 #ifdef INET6
52 struct in6_addr;
53 uint16_t stoeplitz_hash_ip6(const struct stoeplitz_cache *,
54 const struct in6_addr *, const struct in6_addr *);
55 uint16_t stoeplitz_hash_ip6port(const struct stoeplitz_cache *,
56 const struct in6_addr *, const struct in6_addr *,
57 uint16_t, uint16_t);
58 #endif
59
60 /* hash a uint16_t in network byte order */
61 static __unused inline uint16_t
stoeplitz_hash_n16(const struct stoeplitz_cache * scache,uint16_t n16)62 stoeplitz_hash_n16(const struct stoeplitz_cache *scache, uint16_t n16)
63 {
64 uint16_t hi, lo;
65
66 hi = stoeplitz_cache_entry(scache, n16 >> 8);
67 lo = stoeplitz_cache_entry(scache, n16);
68
69 return (hi ^ bswap16(lo));
70 }
71
72 /* hash a uint32_t in network byte order */
73 static __unused inline uint16_t
stoeplitz_hash_n32(const struct stoeplitz_cache * scache,uint32_t n32)74 stoeplitz_hash_n32(const struct stoeplitz_cache *scache, uint32_t n32)
75 {
76 return (stoeplitz_hash_n16(scache, n32 ^ (n32 >> 16)));
77 }
78
79 /* hash a uint16_t in host byte order */
80 static __unused inline uint16_t
stoeplitz_hash_h16(const struct stoeplitz_cache * scache,uint16_t h16)81 stoeplitz_hash_h16(const struct stoeplitz_cache *scache, uint16_t h16)
82 {
83 uint16_t lo, hi;
84
85 lo = stoeplitz_cache_entry(scache, h16);
86 hi = stoeplitz_cache_entry(scache, h16 >> 8);
87
88 #if _BYTE_ORDER == _BIG_ENDIAN
89 return (hi ^ bswap16(lo));
90 #else
91 return (bswap16(hi) ^ lo);
92 #endif
93 }
94
95 /*
96 * system provided symmetric toeplitz
97 */
98
99 #define STOEPLITZ_KEYSEED 0x6d5a
100
101 void stoeplitz_init(void);
102
103 void stoeplitz_to_key(void *, size_t);
104
105 extern const struct stoeplitz_cache *const stoeplitz_cache;
106
107 #define stoeplitz_n16(_n16) \
108 stoeplitz_cache_n16(stoeplitz_cache, (_n16))
109 #define stoeplitz_h16(_h16) \
110 stoeplitz_cache_h16(stoeplitz_cache, (_h16))
111 #define stoeplitz_port(_p) stoeplitz_n16((_p))
112 #define stoeplitz_ip4(_sa4, _da4) \
113 stoeplitz_hash_ip4(stoeplitz_cache, (_sa4), (_da4))
114 #define stoeplitz_ip4port(_sa4, _da4, _sp, _dp) \
115 stoeplitz_hash_ip4port(stoeplitz_cache, (_sa4), (_da4), (_sp), (_dp))
116 #ifdef INET6
117 #define stoeplitz_ip6(_sa6, _da6) \
118 stoeplitz_hash_ip6(stoeplitz_cache, (_sa6), (_da6))
119 #define stoeplitz_ip6port(_sa6, _da6, _sp, _dp) \
120 stoeplitz_hash_ip6port(stoeplitz_cache, (_sa6), (_da6), (_sp), (_dp))
121 #endif
122
123 /*
124 * system also provided asymmetric toeplitz
125 */
126
127 uint32_t toeplitz_vhash(const uint8_t *, size_t, ...);
128
129 #endif /* _SYS_NET_TOEPLITZ_H_ */
130