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 32typedef uint16_t stoeplitz_key; 33 34struct stoeplitz_cache { 35 uint16_t bytes[256]; 36}; 37 38static __unused inline uint16_t 39stoeplitz_cache_entry(const struct stoeplitz_cache *scache, uint8_t byte) 40{ 41 return (scache->bytes[byte]); 42} 43 44void stoeplitz_cache_init(struct stoeplitz_cache *, stoeplitz_key); 45 46uint16_t stoeplitz_hash_ip4(const struct stoeplitz_cache *, 47 uint32_t, uint32_t); 48uint16_t stoeplitz_hash_ip4port(const struct stoeplitz_cache *, 49 uint32_t, uint32_t, uint16_t, uint16_t); 50 51#ifdef INET6 52struct in6_addr; 53uint16_t stoeplitz_hash_ip6(const struct stoeplitz_cache *, 54 const struct in6_addr *, const struct in6_addr *); 55uint16_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 */ 61static __unused inline uint16_t 62stoeplitz_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 */ 73static __unused inline uint16_t 74stoeplitz_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 */ 80static __unused inline uint16_t 81stoeplitz_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 101void stoeplitz_init(void); 102 103void stoeplitz_to_key(void *, size_t); 104 105extern 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 127uint32_t toeplitz_vhash(const uint8_t *, size_t, ...); 128 129#endif /* _SYS_NET_TOEPLITZ_H_ */ 130