Tag: Zobrist

Example Zobrist Hashing 64-Bit

using System;
using System.Runtime.InteropServices;
using System.Security.Cryptography;
/// <summary>
///     
///     https://en.wikipedia.org/wiki/Zobrist_hashing
///    
/// </summary>
public class ZOB64 : HashAlgorithm
{
    private readonly ulong      starthash = 0x391615744853B307;
    private          ulong[]    _table;
    private          ulong      hash;
    private          uint       hash32;
    private          ZOB32State zhs;
    public ZOB64()
    {
        hash = starthash;
        BuildTable(0x7965CBDDD4A9E7AF);
    }
    public override int HashSize => 64;
    public override void Initialize()
    {
        hash = starthash;
    }
    protected override void HashCore(byte[] bytes, int ibStart, int cbSize)
    {
        Hash64(bytes, ibStart, cbSize);
    }
    private static ulong RotateLeft(ulong value, int count)
    {
        return(value << count) | (value >> (64 - count % 64));
    }
    private unsafe void Hash64(byte[] bytes, int ibStart, int cbSize)
    {
        if(bytes == null)
            return;
        if(ibStart >= bytes.Length || cbSize > bytes.Length)
            return;
        var i = 1;
        fixed(byte* pb = bytes)
        {
            var nb = pb + ibStart;
            while(cbSize >= 1)
            {
                hash   ^= RotateLeft(_table[*nb], i++);
                nb     += 1;
                cbSize -= 1;
            }
        }
    }
    protected override byte[] HashFinal()
    {
        zhs.hash64 = hash;
        hash32     = zhs.hi ^ zhs.lo;
        return hash.GetBytes();
    }
    public void BuildTable(ulong seed)
    {
        var s1   = (int) seed;
        var s2   = (int) (seed >> 32);
        var rnd  = new Random(s1);
        var rnd1 = new Random(s2);
        var tt   = new DynHashSet32<ulong>();
        _table = new ulong[256];
        var u = new ZOB32State();
        for(var i = 0; i < 256; i++)
        {
            ulong v;
            do
            {
                u.hi = (uint) rnd.Next();
                u.lo = (uint) rnd1.Next();
                v    = u.hash64;
            } while(tt.Contains(v));
            tt.Add(v);
            _table[i] = v;
        }
    }
    [StructLayout(LayoutKind.Explicit)]
    public struct ZOB32State
    {
        [FieldOffset(0)] public ulong hash64;
        [FieldOffset(0)] public uint  lo;
        [FieldOffset(4)] public uint  hi;
    }
}