[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: reversible fingerprint comment in membuffer code

From: Philip Martin <philip.martin_at_wandisco.com>
Date: Tue, 19 May 2015 19:25:50 +0100

Philip Martin <philip.martin_at_wandisco.com> writes:

> Is this comment in cache-membuffer.c:combine_key correct?
>
> /* scramble key DATA. All of this must be reversible to prevent key
> * collisions. So, we limit ourselves to xor and permutations. */
> data[1] = (data[1] << 27) | (data[1] >> 37);
> data[1] ^= data[0] & 0xffff;
> data[0] ^= data[1] & APR_UINT64_C(0xffffffffffff0000);
>
> I don't see why this needs to be reversible, and it's not clear it is
> reversible.

I talked to Stefan and I believe I can explain. Reversibility is not a
hard requirement on trunk or 1.9 at present, since we store the full
key, but may be a requirement in future. This code is for keys that fit
in the fingerprint and when generating the fingerprint from such keys we
want to avoid introducing collisions, i.e. distinct keys should generate
distinct fingerprints. The cache would cope with collisions but is
better without. A reversible scramble is one way to ensure no
collisions are introduced.

The other reason for the scramble is that it spreads the variation for
small keys across more bytes of the fingerprint and thus across the
cache.

-- 
Philip Martin | Subversion Committer
WANdisco // *Non-Stop Data*
Received on 2015-05-19 20:26:48 CEST

This is an archived mail posted to the Subversion Dev mailing list.