On Sat, 22 Apr 2006, Geert Bosch wrote: > On Sat, Apr 22, 2006 at 01:36:07PM -0700, Davide Libenzi wrote: >> Geert, I saw you're using a shift of 55 bits, that gives an degree of the >> root polynomial of 63, that is not prime. Where did you get the root >> polynomial, and why you did not chose 61 as degree of the root? >> Just curious ... > > The polynomial was randomly created using code by David Mazieres, that > is part of LBFS. I chose a (irreducible) polynomial of degree 63 as > that was the same as LBFS did. As for my purposes it's best to have > a constant polynomial and I wanted to have all the code for > the computations in the same compilation unit for performance, > I decided to just have a little program print out the tables > and include it directly. The chosen polynomial was 0xb15e234bd3792f63. > > Later on I haven't revisited this decision, although I agree that > it'd probably be a good idea to use a polynomial of prime degree, > even though we're not looking for cryptographically strong hashes here. Right, but you are looking at highest equal-probability distribution over your hash buckets ;) Anyway, thanks for bringing Rabin's polynomial fingerprint up from the forgotten lands. Performance and delta size are quite amazing, and I decided to add Rabin's delta to libxdiff. I hacked some code (attached) to generate T/U tables. Since libxdiff must be portable everywhere, even on system w/out 64 bits support, I use xrabin to create both 64 bits tables (poly degree 61) and 32 bits tables (poly degree 31), and store them in a .c file letting the build environment to pick the correct one for the platform. - Davide - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
This archive was generated by hypermail 2.1.8 : 2006-04-25 05:12:13 EST