Re: SipHash for Lua 5.4.0 patch

[Sam Trenholme <lua@...>]

> > > No difference in speed [Using 64-bit SipHash 2-4 with x86_64]
> >
> > Note that there is about a 20% slowdown when we run the same benchmark
> > as an i386 binary compiled with GCC 3.2.3 from 2002.
>
> On i386-type processors less than 20 years old you could use SSE2
> instructions
>
> Public domain code can be found here: 
> https://github.com/floodyberry/siphash

That’s one way to speed things up if using x86 code.  Another would be 
to use HalfSipHash 1-3 instead of the SipHash 2-4 I use in the current 
code.

Neither SipHash 1-3 nor HalfSipHash are readily documented at 
https://131002.net/siphash/ so I will explain them.  HalfSipHash is a 
variant of SipHash that uses 32-bit words instead of 64-bit words.  It’s 
described, along with reference test vectors, over at: 
https://github.com/veorq/SipHash

SipHash 1-3 is a simple variant which does one round of the SipHash 
“compression” function while hashing the input (instead of two rounds), 
and three rounds of the SipHash “compression” function after the input 
ends.  In the patch I provided, there’s a line which looks like this:

    for(round = 0; round < 2; round++) {

Replace the line to look like this:

    for(round = 0; round < 1; round++) {

Or, better yet, just get rid of that particular for loop in SipHash 1-3.

There’s a another line in my patch which looks like this:

    for(round = 0; round < 4; round++) {

In SipHash 1-3, make it:

    for(round = 0; round < 3; round++) {

Some more discussion of SipHash 1-3:

https://bugs.ruby-lang.org/issues/13017
https://github.com/rust-lang/rust/issues/29754#issue-116174313
https://github.com/rust-lang/rust/issues/29754#issuecomment-156073946

Personally, I think i386-based systems are rare enough here in 2020 that 
we do not need to worry about the 20% overall performance impact of 
using SipHash instead of Lua’s default hasher, so that’s the approach I 
take.  SipHash 2-4 is fast enough on x86_64 that I can’t see any 
real-world performance hit by using it.

The biggest issue with adding SipHash to strictly ANSI C compliant code 
is that it needs 128 bits of randomness to make good keys which are 
strong against hash collision attacks.  The code I have to gather 
entropy is OS-specific and not ANSI C, looking like this:

-----------------------------------------------------------------------------
        char noise[17];
#ifndef MINGW
        FILE *rfile = NULL;
        rfile = fopen("/dev/urandom","rb");
        for(a=0;a<16;a++) { noise[a] = getc(rfile); }
#else // Windows API
        HCRYPTPROV CryptContext;
        CryptAcquireContext(&CryptContext, NULL, NULL, PROV_RSA_FULL,
                CRYPT_VERIFYCONTEXT);
        CryptGenRandom(CryptContext, 16, noise);
-----------------------------------------------------------------------------

— Sam