/** Various hash functions, including integer ones.
 *
 * Test: dmd -mcpu=native -checkaction=context -debug -g -unittest -main -I.. -i -run hash_functions.d
 */
module nxt.hash_functions;

@safe nothrow:

/** See_Also: http://forum.dlang.org/post/o1igoc$21ma$1@digitalmars.com
 *
 * Doesn't work: integers are returned as is.
 */
pragma(inline, true)
size_t typeidHashOf(T)(in T x) @trusted => typeid(T).getHash(&x);

///
@safe nothrow unittest
{
    scope x = typeidHashOf(cast(int)17);
}

pure @nogc:

pragma(inline, true)
hash_t hashOfTypeInfoPtr(TypeInfo_Class typeinfo) @trusted pure nothrow @nogc
in(typeof(typeinfo).alignof == 8)
	=> (cast(hash_t)(cast(void*)typeinfo) >> 3);

/** Hash that incorporates the hash of `typeid` bit-xored with `hashOf(a)`.
 *
 * See_Also: https://forum.dlang.org/post/lxqoknwuujbymolnlyfw@forum.dlang.org
 */
pragma(inline, true)
hash_t hashOfPolymorphic(Class)(Class a) @trusted pure nothrow @nogc
if (is(Class == class))
{
    static assert(typeid(Class).alignof == 8);
    // const class_typeid_hash = (cast(hash_t)(cast(void*)typeid(Class)) >> 3)
    return fibonacciHash(.hashOf(cast(void*)typeid(a))) ^ .hashOf(a);
}

pragma(inline, true)
size_t fibonacciHash(in hash_t hash) @safe pure nothrow @nogc
	=> (hash * 11400714819323198485LU);

version(unittest)
{
    private static:

    class Thing
    {
    }

    class Expr : Thing
    {
        @safe pure nothrow @nogc:
        alias Data = string;
        this(Data data)
        {
            this.data = data;
        }
        @property override hash_t toHash() const @safe pure nothrow @nogc => .hashOf(data);
        Data data;
    }

    class NounExpr : Expr
    {
        @safe pure nothrow @nogc:
        this(Data data)
        {
            super(data);
        }
        @property override hash_t toHash() const @safe pure nothrow @nogc => .hashOf(data);
    }
}

///
@safe pure nothrow @nogc unittest
{
    scope car1 = new Expr("car");
    scope car2 = new Expr("car");
    scope bar1 = new Expr("bar");
    scope ncar = new NounExpr("car");

    void testEqual() @safe pure nothrow @nogc
    {
        assert(hashOf(car1) == hashOf(car2));
        assert(hashOfPolymorphic(car1) == hashOfPolymorphic(car2));
    }

    void testDifferent1() @safe pure nothrow @nogc
    {
        assert(hashOf(car1) != hashOf(bar1));
        assert(hashOfPolymorphic(car1) != hashOfPolymorphic(bar1));
    }

    void testDifferent2() @safe pure nothrow @nogc
    {
        assert(hashOf(car1) == hashOf(ncar));
        assert(hashOfPolymorphic(car1) != hashOfPolymorphic(ncar));
    }

    testEqual();
    testDifferent1();
    testDifferent2();
}

@nogc:

/** Dummy-hash for benchmarking performance of HashSet. */
pragma(inline, true)
hash_t identityHash64(in ulong x) @safe pure nothrow @nogc => x; // maps -1 to ulong.max

///
@safe pure nothrow @nogc unittest
{
    assert(identityHash64(-1) == ulong.max);
    assert(identityHash64(int.max) == int.max);
    assert(identityHash64(ulong.max) == ulong.max);
}

/** Mueller integer hash function (bit mixer) A (32-bit).
 *
 * See_Also: https://stackoverflow.com/a/12996028/683710
 * See_Also: http://zimbry.blogspot.se/2011/09/better-bit-mixing-improving-on.html
 */
uint muellerHash32(uint x) @safe pure nothrow @nogc
{
    version(D_Coverage) {} else pragma(inline, true);
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    return x;
}

/** Mueller integer hash function (bit mixer) A (64-bit).
 *
 * Based on splitmix64, which seems to be based on the blog article "Better Bit
 * Mixing" (mix 13).
 *
 * See_Also: https://stackoverflow.com/a/12996028/683710
 * See_Also: http://zimbry.blogspot.se/2011/09/better-bit-mixing-improving-on.html
 * See_Also: http://xorshift.di.unimi.it/splitmix64.c
 */
hash_t muellerHash64(ulong x) @safe pure nothrow @nogc
{
    version(D_Coverage) {} else pragma(inline, true);
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9UL;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebUL;
    x = x ^ (x >> 31);
    return x;
}

/** Thomas Wang 64-bit mix integer hash function.
 *
 * See_Also: https://gist.github.com/badboy/6267743#64-bit-mix-functions
 */
hash_t wangMixHash64(ulong x) @safe pure nothrow @nogc
{
    version(D_Coverage) {} else pragma(inline, true);
    x = (~x) + (x << 21); // x = (x << 21) - x - 1;
    x = x ^ (x >>> 24);
    x = (x + (x << 3)) + (x << 8); // x * 265
    x = x ^ (x >>> 14);
    x = (x + (x << 2)) + (x << 4); // x * 21
    x = x ^ (x >>> 28);
    x = x + (x << 31);
    return x;
}

///
@safe pure nothrow @nogc unittest
{
    assert(wangMixHash64(0) == 8633297058295171728UL);
    assert(wangMixHash64(1) == 6614235796240398542UL);
}

/** Inspired by Lemire's strongly universal hashing.
 *
 * See_Also: https://lemire.me/blog/2018/08/15/fast-strongly-universal-64-bit-hashing-everywhere/
 *
 * Instead of shifts, we use rotations so we don't lose any bits.
 *
 * Added a final multiplcation with a constant for more mixing. It is most important that the
 * lower bits are well mixed.
 */
hash_t lemireHash64(in ulong x) @safe pure nothrow @nogc
{
	import core.bitop : ror;
    version(D_Coverage) {} else pragma(inline, true);
	enum shift = 8*x.sizeof / 2;
    const ulong h1 = x * 0x_A24B_AED4_963E_E407UL;
    const ulong h2 = ror(x, shift) * 0x_9FB2_1C65_1E98_DF25UL;
    const ulong h = ror(h1 + h2, shift);
    return h;
}
/// ditto
hash_t lemireHash64(in double x) @trusted pure nothrow @nogc
{
	return lemireHash64(*(cast(ulong*)&x));
}

///
@safe pure nothrow @nogc unittest
{
    assert(lemireHash64(0) == 0UL);
    assert(lemireHash64(1) == 10826341276197359097UL);
    assert(lemireHash64(2) == 3205938474390199283UL);
    assert(lemireHash64(0f) == 0UL);
    assert(lemireHash64(1f) == 5597974336836488763);
    assert(lemireHash64(2f) == 4611686018555721673UL);
}

uint lemireHash32(in uint x) @safe pure nothrow @nogc
{
	import core.bitop : ror;
    version(D_Coverage) {} else pragma(inline, true);
	enum shift = 8*x.sizeof / 2;
    const uint h1 = x * 0x_963E_E407U;
    const uint h2 = ror(x, shift) * 0x_1E98_DF25U;
    const uint h = ror(h1 + h2, shift);
    return h;
}
/// ditto
uint lemireHash32(in float x) @trusted pure nothrow @nogc
{
	return lemireHash32(*(cast(uint*)&x));
}

///
@safe pure nothrow @nogc unittest
{
    assert(lemireHash32(0) == 0UL);
    assert(lemireHash32(1) == 3825694051);
    assert(lemireHash32(2) == 3356420807);
    assert(lemireHash32(0f) == 0UL);
    assert(lemireHash32(1f) == 2910889945);
    assert(lemireHash32(2f) == 1073805257);
}