Home | History | Annotate | Line # | Download | only in net 
      1 /*	$OpenBSD: toeplitz.h,v 1.3 2020/06/19 08:48:15 dlg Exp $ */
      2 
      3 /*
      4  * Copyright (c) 2019 David Gwynne <dlg (at) 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
     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
     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
     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
     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