Author tim.peters
Recipients eric.smith, jdemeyer, mark.dickinson, rhettinger, sir-sigurd, tim.peters
Date 2018-10-03.01:15:04
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1538529305.32.0.545547206417.issue34751@psf.upfronthosting.co.za>
In-reply-to
Content
> SeaHash seems to be designed for 64 bits.

Absolutely.

> I'm guessing that replacing the shifts by
>
> x ^= ((x >> 16) >> (x >> 29))
>
> would be what you'd do for a 32-bit hash.

My guess too.  But "the prime" is a puzzle.  As noted before, the 64-bit prime is specially constructed to satisfy specific dispersion properties.  While I haven't triple-checked this, I believe it fails at two specific bit positions:

- Bit 2**16 doesn't propagate into the leading 4 bits at all.

- Bit 2**17 does propagate into bit 2**60, but _only_ into that bit among the highest 4 bits.  One of the criteria is that the prime shouldn't propagate a lower-order bit into _only_ the least-significant of the 4 leading bits.

Repairing that would probably require adding a bit or two.  But the prime already has 35 bits set.  The greater the imbalance between 0 and 1 bits, the more multiply acts like a simpler sequence of shift-and-adds or shift-and-subtracts (for example, at an extreme, consider the multiplier (1 << 63) - 1).

Anyway, it seems the density of 1 bits would have to be even higher for a 32-bit multiplier to ensure all low-order bits directly propagated to at least one of the topmost 3 bits, but not to the third-most significant alone.

Or I could search for a 31-bit prime - or just an odd integer - that got as close as possible with 16 or 17 bits set.  Or ...

> Alternatively, we could always compute the hash with
> 64 bits (using uint64_t) and then truncate at the end
> if needed.

Provided we continue to like it at all ;-)  In which case I'd probably end it with

    32_bit_result = (32_bit_result_type)(x ^ (x >> 32));

instead.
History
Date User Action Args
2018-10-03 01:15:06tim.peterssetrecipients: + tim.peters, rhettinger, mark.dickinson, eric.smith, jdemeyer, sir-sigurd
2018-10-03 01:15:05tim.peterssetmessageid: <1538529305.32.0.545547206417.issue34751@psf.upfronthosting.co.za>
2018-10-03 01:15:05tim.peterslinkissue34751 messages
2018-10-03 01:15:04tim.peterscreate