On Wed, Oct 20, 2010 at 05:03:02PM +0200, Michael Niedermayer wrote: [...] > yet another way to get a fast 128bit hash function is to use a LFG > heres an example: > > tmp[i] = input[i] + tmp[i-7] + tmp[i-10] > with input and tmp being uint64_t > this can be implemented extreemly efficient by putting all 10 tmp values in > registers requireing only 1 64bit read and 2 64bit additions for each 8 bytes > of input if the loop is unrolled > the output of that hash function would be 10*64bit and could either be used > directly or passed through a second hash to get 128bit out of it > other values instead of 7 and 10 can be used to improve the strength of this > but then they wont fit in the 16 available registers on x86_64 anymore
Replying to my own mail ... one way to make above stronger without completely loosing the register optimization is to use tmp[i] = input[i] + tmp[i-6] + tmp[i-31] that way the tmp[i-6] case can still be read from register while tmp[i-31] would need actual memory so this would need 1 write and 1 read more than the case above without the register optimization something like tmp[i] = input[i] + tmp[i-24] + tmp[i-55] can be used One weakness of these hash functions is that theres a periodicy of 2^n in the highest bit, that is moving the MSB of a 64bit input by 1024 64bit words shouldnt change the hash of the 7,10 function. with the others this problem is moved up to 2^31 and 2^55 which should be a non issue. How much this is of relevance to ccache i dont know ... [...] -- Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB The bravest are surely those who have the clearest vision of what is before them, glory and danger alike, and yet notwithstanding go out to meet it. -- Thucydides
signature.asc
Description: Digital signature
_______________________________________________ ccache mailing list ccache@lists.samba.org https://lists.samba.org/mailman/listinfo/ccache