Perl: Multiply-Shift Hash

I've been using the multiply-shift hash lately and have had good results. It's simple, fast, and well tested.

// Multiply-Shift Hash
static uint64_t hash_msh(uint64_t x) {
    uint64_t prime = 0x9e3779b97f4a7c15; // A large prime constant
    x ^= (x >> 30);
    x *= prime;
    x ^= (x >> 27);
    x *= prime;
    x ^= (x >> 31);
    return x;
}

Whenever I find interesting code like this I like to try and implement it in Perl:

sub hash_msh {
    my $x     = $_[0];
    my $prime = 11400714819323198485;

    $x ^= ($x >> 30);
    $x = multiply_uv($x, $prime);
    $x ^= ($x >> 27);
    $x = multiply_uv($x, $prime);
    $x ^= ($x >> 31);

    return $x;
}

# Perl converts numbers larger than 2^64 - 1 to floating point so
# we 'use integer' to force integer math which retains any overflow.
sub multiply_uv {
    my ($one, $two) = @_;

    use integer;
    my $ret = $one * $two;
    no integer;

    # Convert signed IV to unsinged UV
    if ($ret < 0) {
        $ret += 18446744073709551615;
        $ret += 1;
    }

    return $ret;
}
Leave A Reply
All content licensed under the Creative Commons License