From f1543f8b8316f49b318ac6cd8c78a7fd18509311 Mon Sep 17 00:00:00 2001 From: Florian Zumbiehl Date: Tue, 31 Jul 2007 13:47:57 -0700 Subject: [PATCH] [PPPOE]: Improve hashing function in hash_item(). The new code produces the same results as the old version and is ~ 3 to 6 times faster for 4-bit hashes on the CPUs I tested. Signed-off-by: Florian Zumbiehl Signed-off-by: David S. Miller --- drivers/net/pppoe.c | 25 +++++++++++++++---------- 1 file changed, 15 insertions(+), 10 deletions(-) diff --git a/drivers/net/pppoe.c b/drivers/net/pppoe.c index 35a7385ccb2a..68631a5721ac 100644 --- a/drivers/net/pppoe.c +++ b/drivers/net/pppoe.c @@ -108,19 +108,24 @@ static inline int cmp_addr(struct pppoe_addr *a, unsigned long sid, char *addr) (memcmp(a->remote,addr,ETH_ALEN) == 0)); } -static int hash_item(unsigned long sid, unsigned char *addr) +#if 8%PPPOE_HASH_BITS +#error 8 must be a multiple of PPPOE_HASH_BITS +#endif + +static int hash_item(unsigned int sid, unsigned char *addr) { - char hash = 0; - int i, j; + unsigned char hash = 0; + unsigned int i; - for (i = 0; i < ETH_ALEN ; ++i) { - for (j = 0; j < 8/PPPOE_HASH_BITS ; ++j) { - hash ^= addr[i] >> ( j * PPPOE_HASH_BITS ); - } + for (i = 0 ; i < ETH_ALEN ; i++) { + hash ^= addr[i]; + } + for (i = 0 ; i < sizeof(sid_t)*8 ; i += 8 ){ + hash ^= sid>>i; + } + for (i = 8 ; (i>>=1) >= PPPOE_HASH_BITS ; ) { + hash ^= hash>>i; } - - for (i = 0; i < (sizeof(unsigned long)*8) / PPPOE_HASH_BITS ; ++i) - hash ^= sid >> (i*PPPOE_HASH_BITS); return hash & ( PPPOE_HASH_SIZE - 1 ); } -- 2.30.2