The next step is to use that we have cached the result of the matrix
multiplication H * val in stoeplitz_cache_entry(scache, val), so the
identity (H * x) ^ (H * y) == H * (x ^ y) allows us to push the calls to
the cache function down to the end of stoeplitz_hash_ip{4,6}{,port}().
The result is the mechanical diff below. I have at least one follow-up,
so it's intentionally minimalistic.
The identity in question was again confirmed by brute force on amd64,
sparc64 and powerpc for all possible values of skey, x and y.
Index: toeplitz.c
===================================================================
RCS file: /cvs/src/sys/net/toeplitz.c,v
retrieving revision 1.2
diff -u -p -r1.2 toeplitz.c
--- toeplitz.c 17 Jun 2020 06:36:56 -0000 1.2
+++ toeplitz.c 17 Jun 2020 06:56:11 -0000
@@ -118,17 +118,18 @@ stoeplitz_hash_ip4(const struct stoeplit
{
uint16_t lo, hi;
- lo = stoeplitz_cache_entry(scache, faddr >> 0);
- lo ^= stoeplitz_cache_entry(scache, faddr >> 16);
- lo ^= stoeplitz_cache_entry(scache, laddr >> 0);
- lo ^= stoeplitz_cache_entry(scache, laddr >> 16);
-
- hi = stoeplitz_cache_entry(scache, faddr >> 8);
- hi ^= stoeplitz_cache_entry(scache, faddr >> 24);
- hi ^= stoeplitz_cache_entry(scache, laddr >> 8);
- hi ^= stoeplitz_cache_entry(scache, laddr >> 24);
+ lo = faddr >> 0;
+ lo ^= faddr >> 16;
+ lo ^= laddr >> 0;
+ lo ^= laddr >> 16;
+
+ hi = faddr >> 8;
+ hi ^= faddr >> 24;
+ hi ^= laddr >> 8;
+ hi ^= laddr >> 24;
- return (swap16(lo) ^ hi);
+ return (swap16(stoeplitz_cache_entry(scache, lo))
+ ^ stoeplitz_cache_entry(scache, hi));
}
uint16_t
@@ -137,21 +138,22 @@ stoeplitz_hash_ip4port(const struct stoe
{
uint16_t hi, lo;
- lo = stoeplitz_cache_entry(scache, faddr >> 0);
- lo ^= stoeplitz_cache_entry(scache, faddr >> 16);
- lo ^= stoeplitz_cache_entry(scache, laddr >> 0);
- lo ^= stoeplitz_cache_entry(scache, laddr >> 16);
- lo ^= stoeplitz_cache_entry(scache, fport >> 0);
- lo ^= stoeplitz_cache_entry(scache, lport >> 0);
-
- hi = stoeplitz_cache_entry(scache, faddr >> 8);
- hi ^= stoeplitz_cache_entry(scache, faddr >> 24);
- hi ^= stoeplitz_cache_entry(scache, laddr >> 8);
- hi ^= stoeplitz_cache_entry(scache, laddr >> 24);
- hi ^= stoeplitz_cache_entry(scache, fport >> 8);
- hi ^= stoeplitz_cache_entry(scache, lport >> 8);
+ lo = faddr >> 0;
+ lo ^= faddr >> 16;
+ lo ^= laddr >> 0;
+ lo ^= laddr >> 16;
+ lo ^= fport >> 0;
+ lo ^= lport >> 0;
+
+ hi = faddr >> 8;
+ hi ^= faddr >> 24;
+ hi ^= laddr >> 8;
+ hi ^= laddr >> 24;
+ hi ^= fport >> 8;
+ hi ^= lport >> 8;
- return (swap16(lo) ^ hi);
+ return (swap16(stoeplitz_cache_entry(scache, lo))
+ ^ stoeplitz_cache_entry(scache, hi));
}
#ifdef INET6
@@ -166,18 +168,19 @@ stoeplitz_hash_ip6(const struct stoeplit
uint32_t faddr = faddr6->s6_addr32[i];
uint32_t laddr = laddr6->s6_addr32[i];
- lo ^= stoeplitz_cache_entry(scache, faddr >> 0);
- lo ^= stoeplitz_cache_entry(scache, faddr >> 16);
- lo ^= stoeplitz_cache_entry(scache, laddr >> 0);
- lo ^= stoeplitz_cache_entry(scache, laddr >> 16);
-
- hi ^= stoeplitz_cache_entry(scache, faddr >> 8);
- hi ^= stoeplitz_cache_entry(scache, faddr >> 24);
- hi ^= stoeplitz_cache_entry(scache, laddr >> 8);
- hi ^= stoeplitz_cache_entry(scache, laddr >> 24);
+ lo ^= faddr >> 0;
+ lo ^= faddr >> 16;
+ lo ^= laddr >> 0;
+ lo ^= laddr >> 16;
+
+ hi ^= faddr >> 8;
+ hi ^= faddr >> 24;
+ hi ^= laddr >> 8;
+ hi ^= laddr >> 24;
}
- return (swap16(lo) ^ hi);
+ return (swap16(stoeplitz_cache_entry(scache, lo))
+ ^ stoeplitz_cache_entry(scache, hi));
}
uint16_t
@@ -192,24 +195,25 @@ stoeplitz_hash_ip6port(const struct stoe
uint32_t faddr = faddr6->s6_addr32[i];
uint32_t laddr = laddr6->s6_addr32[i];
- lo ^= stoeplitz_cache_entry(scache, faddr >> 0);
- lo ^= stoeplitz_cache_entry(scache, faddr >> 16);
- lo ^= stoeplitz_cache_entry(scache, laddr >> 0);
- lo ^= stoeplitz_cache_entry(scache, laddr >> 16);
-
- hi ^= stoeplitz_cache_entry(scache, faddr >> 8);
- hi ^= stoeplitz_cache_entry(scache, faddr >> 24);
- hi ^= stoeplitz_cache_entry(scache, laddr >> 8);
- hi ^= stoeplitz_cache_entry(scache, laddr >> 24);
+ lo ^= faddr >> 0;
+ lo ^= faddr >> 16;
+ lo ^= laddr >> 0;
+ lo ^= laddr >> 16;
+
+ hi ^= faddr >> 8;
+ hi ^= faddr >> 24;
+ hi ^= laddr >> 8;
+ hi ^= laddr >> 24;
}
- lo ^= stoeplitz_cache_entry(scache, fport >> 0);
- lo ^= stoeplitz_cache_entry(scache, lport >> 0);
+ lo ^= fport >> 0;
+ lo ^= lport >> 0;
- hi ^= stoeplitz_cache_entry(scache, fport >> 8);
- hi ^= stoeplitz_cache_entry(scache, lport >> 8);
+ hi ^= fport >> 8;
+ hi ^= lport >> 8;
- return (swap16(lo) ^ hi);
+ return (swap16(stoeplitz_cache_entry(scache, lo))
+ ^ stoeplitz_cache_entry(scache, hi));
}
#endif /* INET6 */
