On Fri, Apr 29, 2016 at 5:32 PM, George Spelvin <li...@horizon.com> wrote:
>
> Odd is important. If the multiplier is even, the msbit of the input
> doesn't affect the hash result at all.
Fair enough. My test-set was incomplete.
>> Yeah. gcc will actually do the clever stuff for the 32-bit case, afaik.
>
> It's not as clever as it could be; it just does the same Booth
> recoding thing, a simple series of shifts with add/subtract.
Ahh. I thought gcc did the Bernstein's algorithm thing, which is
exponential in the bit size. That would have explained why it only
does it for 32-bit constants.
Not doing it for 64-bit constants makes no sense if it just uses the
trivial Booth's algorithm version.
So the odd "we don't do it for 64-bit" is apparently just an
oversight, not because gcc does something clever.
Oh well.
Linus
