Messages in this thread | | | Date | Thu, 15 Apr 1999 16:51:58 +0200 | From | Peter Steiner <> | Subject | Re: more on hash functions |
| |
>You really have to make every bit of the result depend on >every bit in the key.
What about:
unsigned int rand1[256]; #define HASH1(x) ( ((x)<<8)^rand1[(x)>>24] ) #define hashfn(key) ( { int hashx=HASH1((key)<<8);\ hashx=HASH1(hashx);\ HASH1(hashx);\ } )
And to initialize the table: >---------------------------------------------- void genrand(void) { unsigned int i,j,k; for(i=0;i<256;i++){ k=i<<16; for(j=0;j<8;j++) { if (k<0x00800000) k<<=1; else k=((k<<1)&0xFFFFFF)^0x14A445; } k+=i<<24; rand1[i]=k; } } >----------------------------------------------
The key may be up to 24 bits. The result looks like this:
movl %edx,%eax sall $8,%eax sall $16,%edx sarl $24,%eax xorl rand1(,%eax,4),%edx movl %edx,%eax sall $8,%edx sarl $24,%eax xorl rand1(,%eax,4),%edx movl %edx,%eax sall $8,%edx sarl $24,%eax xorl rand1(,%eax,4),%edx movl %edx,%eax
Is that still fast enough?
Peter
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
| |