1 /* $OpenBSD: toeplitz.h,v 1.11 2023/05/17 10:22:17 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 #include <sys/endian.h>
23
24 /*
25 * symmetric toeplitz
26 */
27
28 typedef uint16_t stoeplitz_key;
29
30 struct stoeplitz_cache {
31 uint16_t bytes[256];
32 };
33
34 static __unused inline uint16_t
stoeplitz_cache_entry(const struct stoeplitz_cache * scache,uint8_t byte)35 stoeplitz_cache_entry(const struct stoeplitz_cache *scache, uint8_t byte)
36 {
37 return (scache->bytes[byte]);
38 }
39
40 void stoeplitz_cache_init(struct stoeplitz_cache *, stoeplitz_key);
41
42 uint16_t stoeplitz_hash_ip4(const struct stoeplitz_cache *,
43 uint32_t, uint32_t);
44 uint16_t stoeplitz_hash_ip4port(const struct stoeplitz_cache *,
45 uint32_t, uint32_t, uint16_t, uint16_t);
46
47 #ifdef INET6
48 struct in6_addr;
49 uint16_t stoeplitz_hash_ip6(const struct stoeplitz_cache *,
50 const struct in6_addr *, const struct in6_addr *);
51 uint16_t stoeplitz_hash_ip6port(const struct stoeplitz_cache *,
52 const struct in6_addr *, const struct in6_addr *,
53 uint16_t, uint16_t);
54 #endif
55
56 uint16_t stoeplitz_hash_eaddr(const struct stoeplitz_cache *,
57 const uint8_t *);
58
59 /* hash a uint16_t in network byte order */
60 static __unused inline uint16_t
stoeplitz_hash_n16(const struct stoeplitz_cache * scache,uint16_t n16)61 stoeplitz_hash_n16(const struct stoeplitz_cache *scache, uint16_t n16)
62 {
63 uint16_t hi, lo;
64
65 hi = stoeplitz_cache_entry(scache, n16 >> 8);
66 lo = stoeplitz_cache_entry(scache, n16);
67
68 return (hi ^ swap16(lo));
69 }
70
71 /* hash a uint32_t in network byte order */
72 static __unused inline uint16_t
stoeplitz_hash_n32(const struct stoeplitz_cache * scache,uint32_t n32)73 stoeplitz_hash_n32(const struct stoeplitz_cache *scache, uint32_t n32)
74 {
75 return (stoeplitz_hash_n16(scache, n32 ^ (n32 >> 16)));
76 }
77
78 /* hash a uint16_t in host byte order */
79 static __unused inline uint16_t
stoeplitz_hash_h16(const struct stoeplitz_cache * scache,uint16_t h16)80 stoeplitz_hash_h16(const struct stoeplitz_cache *scache, uint16_t h16)
81 {
82 uint16_t lo, hi;
83
84 lo = stoeplitz_cache_entry(scache, h16);
85 hi = stoeplitz_cache_entry(scache, h16 >> 8);
86
87 #if _BYTE_ORDER == _BIG_ENDIAN
88 return (hi ^ swap16(lo));
89 #else
90 return (swap16(hi) ^ lo);
91 #endif
92 }
93
94 static __unused inline uint16_t
stoeplitz_hash_h32(const struct stoeplitz_cache * scache,uint32_t h32)95 stoeplitz_hash_h32(const struct stoeplitz_cache *scache, uint32_t h32)
96 {
97 return (stoeplitz_hash_h16(scache, h32 ^ (h32 >> 16)));
98 }
99
100 static __unused inline uint16_t
stoeplitz_hash_h64(const struct stoeplitz_cache * scache,uint64_t h64)101 stoeplitz_hash_h64(const struct stoeplitz_cache *scache, uint64_t h64)
102 {
103 return (stoeplitz_hash_h32(scache, h64 ^ (h64 >> 32)));
104 }
105
106 /*
107 * system provided symmetric toeplitz
108 */
109
110 #define STOEPLITZ_KEYSEED 0x6d5a
111
112 void stoeplitz_init(void);
113
114 void stoeplitz_to_key(void *, size_t)
115 __bounded((__buffer__, 1, 2));
116
117 extern const struct stoeplitz_cache *const stoeplitz_cache;
118
119 #define stoeplitz_n16(_n16) \
120 stoeplitz_hash_n16(stoeplitz_cache, (_n16))
121 #define stoeplitz_n32(_n32) \
122 stoeplitz_hash_n32(stoeplitz_cache, (_n32))
123 #define stoeplitz_h16(_h16) \
124 stoeplitz_hash_h16(stoeplitz_cache, (_h16))
125 #define stoeplitz_h32(_h32) \
126 stoeplitz_hash_h32(stoeplitz_cache, (_h32))
127 #define stoeplitz_h64(_h64) \
128 stoeplitz_hash_h64(stoeplitz_cache, (_h64))
129 #define stoeplitz_port(_p) stoeplitz_n16((_p))
130 #define stoeplitz_ip4(_sa4, _da4) \
131 stoeplitz_hash_ip4(stoeplitz_cache, (_sa4), (_da4))
132 #define stoeplitz_ip4port(_sa4, _da4, _sp, _dp) \
133 stoeplitz_hash_ip4port(stoeplitz_cache, (_sa4), (_da4), (_sp), (_dp))
134 #ifdef INET6
135 #define stoeplitz_ip6(_sa6, _da6) \
136 stoeplitz_hash_ip6(stoeplitz_cache, (_sa6), (_da6))
137 #define stoeplitz_ip6port(_sa6, _da6, _sp, _dp) \
138 stoeplitz_hash_ip6port(stoeplitz_cache, (_sa6), (_da6), (_sp), (_dp))
139 #endif
140 #define stoeplitz_eaddr(_ea) \
141 stoeplitz_hash_eaddr(stoeplitz_cache, (_ea))
142
143 #endif /* _SYS_NET_TOEPLITZ_H_ */
144