Tag: Fast

Fnv1a64Fast.cs

FNV1a 64Bit Hashing Fast

using System.Security.Cryptography;
/// <summary>
///     https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
///     Very fast up to 2GBpS.
/// </summary>
public class Fnv1a64Fast : HashAlgorithm
{
    private const    ulong _prime  = 0x100000001B3;
    private readonly ulong _offset = 0xCBF29CE484222325;
    private          ulong _hash;
    public           ulong Hashf;
    public Fnv1a64Fast()
    {
        _hash = _offset;
    }
    public Fnv1a64Fast(ulong seed)
    {
        _offset = seed;
        _hash   = _offset;
    }
    public override int HashSize => 64;
    public override void Initialize()
    {
        _hash = _offset;
    }
    protected override void HashCore(byte[] bytes, int ibStart, int cbSize)
    {
        Hash64(bytes, ibStart, cbSize);
    }
    private unsafe void Hash64(byte[] bytes, int ibStart, int cbSize)
    {
        if (bytes == null)
            return;
        if (ibStart >= bytes.Length || cbSize > bytes.Length)
            return;
        unchecked
        {
            fixed (byte* pb = bytes)
            {
                var nb = pb + ibStart;
                while (cbSize >= 8)
                {
                    _hash  ^= *(ulong*) nb;
                    _hash  *= _prime;
                    nb     += 8;
                    cbSize -= 8;
                }
                switch (cbSize & 7)
                {
                    case 7:
                        _hash ^= *(ulong*) (nb + 6);
                        _hash *= _prime;
                        goto case 6;
                    case 6:
                        _hash ^= *(ulong*) (nb + 5);
                        _hash *= _prime;
                        goto case 5;
                    case 5:
                        _hash ^= *(ulong*) (nb + 4);
                        _hash *= _prime;
                        goto case 4;
                    case 4:
                        _hash ^= *(ulong*) (nb + 3);
                        _hash *= _prime;
                        goto case 3;
                    case 3:
                        _hash ^= *(ulong*) (nb + 2);
                        _hash *= _prime;
                        goto case 2;
                    case 2:
                        _hash ^= *(ulong*) (nb + 1);
                        _hash *= _prime;
                        goto case 1;
                    case 1:
                        _hash ^= *nb;
                        _hash *= _prime;
                        break;
                }
            }
        }
        _hash = _hash ^ (_hash >> 32);
        Hashf = _hash;
    }
    protected override byte[] HashFinal()
    {
        var ba = new byte[8];
        unsafe
        {
            fixed (byte* ptr = ba)
            {
                *(ulong*) ptr = _hash;
            }
        }
        return ba;
    }
}

FNV1a32Fast.cs

FNV1a 32 Bit Fast Hashing

using System.Security.Cryptography;
/// <summary>
///     https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
///     Very fast 2GBpS.
/// </summary>
public class FNV1a32Fast : HashAlgorithm
{
    private const    ulong _prime = 0x100000001B3;
    private          ulong _hash;
    private readonly ulong _offset = 0xCBF29CE484222325;
    public           uint  Hashf;
    public FNV1a32Fast()
    {
        _hash = _offset;
    }
    public FNV1a32Fast(ulong seed)
    {
        _offset = seed;
        _hash   = _offset;
    }
    public override int HashSize => 32;
    public override void Initialize()
    {
        _hash = _offset;
    }
    protected override void HashCore(byte[] bytes, int ibStart, int cbSize)
    {
        Hash64(bytes, ibStart, cbSize);
    }
    private unsafe void Hash64(byte[] bytes, int ibStart, int cbSize)
    {
        if (bytes == null)
            return;
        if (ibStart >= bytes.Length || cbSize > bytes.Length)
            return;
        unchecked
        {
            fixed (byte* pb = bytes)
            {
                var nb = pb + ibStart;
                while (cbSize >= 8)
                {
                    _hash  ^= *(ulong*) nb;
                    _hash  *= _prime;
                    nb     += 8;
                    cbSize -= 8;
                }
                switch (cbSize & 7)
                {
                    case 7:
                        _hash ^= *(ulong*) (nb + 6);
                        _hash *= _prime;
                        goto case 6;
                    case 6:
                        _hash ^= *(ulong*) (nb + 5);
                        _hash *= _prime;
                        goto case 5;
                    case 5:
                        _hash ^= *(ulong*) (nb + 4);
                        _hash *= _prime;
                        goto case 4;
                    case 4:
                        _hash ^= *(ulong*) (nb + 3);
                        _hash *= _prime;
                        goto case 3;
                    case 3:
                        _hash ^= *(ulong*) (nb + 2);
                        _hash *= _prime;
                        goto case 2;
                    case 2:
                        _hash ^= *(ulong*) (nb + 1);
                        _hash *= _prime;
                        goto case 1;
                    case 1:
                        _hash ^= *nb;
                        _hash *= _prime;
                        break;
                }
            }
        }
        var usb = (uint) (_hash >> 32);
        var lsb = (uint) _hash;
        Hashf = usb ^ lsb;
    }
    protected override byte[] HashFinal()
    {
        var ba = new byte[4];
        unsafe
        {
            fixed (byte* ptr = ba)
            {
                *(uint*) ptr = Hashf;
            }
        }
        return ba;
    }
}

ObjectAssociativeArray.cs

Key based, Fast Searchable Values, Multiple Value Arrays.

Key, Values, Values,… All Comparisons are done at the byte level, no need for custom comparator. Keys and all values are searchable, using (Indexed) variable bit width map hashing (Default is 64 Bits, can go up to 512 bits). 

using System;
using System.Diagnostics;
[DebuggerDisplay("Count = {" + nameof(Count) + "}")]
[Serializable]
public class ObjectAssociativeArray : MonitorActionFuncWrapper
{
    private ObjectBase   _keys;
    private ObjectBase[] _values;
    public ObjectAssociativeArray() : this(1024)
    {
    }
    public ObjectAssociativeArray(int size, int order = 1)
    {
        _keys   = new ObjectBase(size);
        _values = new ObjectBase[order];
        for (var i = 0; i < order; ++i)
            _values[i] = new ObjectBase(size);
    }
    public int Count => _keys.Count;
    public bool Add(object key, params object[] value)
    {
        if (key == null)
            throw new ArgumentException("Key cannot be null.");
        if (value == null)
            throw new ArgumentException("There must be a least one value.");
        return Lock(this, () =>
        {
            for (var p = 0; p < value.Length; ++p)
                if (_keys.Contains(key) || _values[p].Contains(value[p]))
                    return false;
            var ka = _keys.Add(key);
            var va = false;
            for (var p = 0; p < value.Length; ++p)
            {
                va = _values[p].Add(value[p]);
                if (!va)
                    throw new Exception($"the nth parameter {p} could not be added.");
            }
            return ka && va;
        });
    }
    public (object[] key, object value) GetKeysAndValues(int index)
    {
        return (_keys.ToArray(), _values[index].ToArray());
    }
    #region Generic
    public bool Contains(object key)
    {
        return _keys.Contains(key);
    }
    public bool ContainsValue(object value, int index = 0)
    {
        return _values[index].Contains(value);
    }
    #endregion
}

RandomX.cs

A Fast Random Number Generator Based on BigInteger

using System;
using System.Numerics;
using System.Security.Cryptography;
public struct RandomX
{
    private readonly RNGCryptoServiceProvider _crng;
    private          int                      _maxByteWidth;
    private          int                      _bitWidth;
    public RandomX(int bitWidth)
    {
        MaxValue      = BigIntegerHelper.GetMaxValueBitWidth(bitWidth);
        _maxByteWidth = bitWidth >> 3;
        OddsOnly      = false;
        Unsigned      = false;
        _crng         = new RNGCryptoServiceProvider();
        _bitWidth     = bitWidth;
    }
    public bool OddsOnly;
    public bool Unsigned;
    public int BitWidth
    {
        get => _bitWidth;
        set
        {
            _bitWidth     = value;
            MaxValue      = BigIntegerHelper.GetMaxValueBitWidth(_bitWidth);
            _maxByteWidth = _bitWidth >> 3;
        }
    }
    public BigInteger MaxValue;
    public bool NextBool()
    {
        return Sample() < .5;
    }
    public char NextChar(char maxValue)
    {
        if (maxValue < 0)
            throw new ArgumentException("maxValue must be greater than zero.");
        if (!Unsigned)
            Unsigned = true;
        if (_bitWidth < 16)
            BitWidth = 16;
        return (char) (Sample() * maxValue);
    }
    public char NextChar(char minValue, char maxValue)
    {
        if (!Unsigned)
            Unsigned = true;
        if (_bitWidth < 16)
            BitWidth = 16;
        return (char) Next(minValue, maxValue);
    }
    public sbyte NextInt8()
    {
        if (Unsigned)
            Unsigned = false;
        if (_bitWidth < 8)
            BitWidth = 8;
        return (sbyte) Internal();
    }
    public sbyte NextInt8(sbyte maxValue)
    {
        if (maxValue < 0)
            throw new ArgumentException("maxValue must be greater than zero.");
        if (Unsigned)
            Unsigned = false;
        if (_bitWidth < 8)
            BitWidth = 8;
        return (sbyte) (Sample() * maxValue);
    }
    public sbyte NextInt8(sbyte minValue, sbyte maxValue)
    {
        if (minValue > maxValue)
            throw new ArgumentException("maxValue must be greater than or equal to minValue");
        if (Unsigned)
            Unsigned = false;
        if (_bitWidth < 8)
            BitWidth = 8;
        return (sbyte) Next(minValue, maxValue);
    }
    public byte NextUInt8()
    {
        if (!Unsigned)
            Unsigned = true;
        if (_bitWidth < 8)
            BitWidth = 8;
        var n = Internal();
        return (byte) n;
    }
    public byte NextUInt8(byte maxValue)
    {
        if (!Unsigned)
            Unsigned = true;
        if (_bitWidth < 8)
            BitWidth = 8;
        return (byte) (Sample() * maxValue);
    }
    public byte NextUInt8(byte minValue, byte maxValue)
    {
        if (minValue > maxValue)
            throw new ArgumentException("maxValue must be greater than or equal to minValue");
        if (!Unsigned)
            Unsigned = true;
        if (_bitWidth < 8)
            BitWidth = 8;
        return (byte) Next(minValue, maxValue);
    }
    public short NextInt16()
    {
        if (_bitWidth < 16)
            BitWidth = 16;
        if (Unsigned)
            Unsigned = false;
        return (short) Internal();
    }
    public short NextInt16(short maxValue)
    {
        if (maxValue < 0)
            throw new ArgumentException("maxValue must be greater than zero.");
        if (Unsigned)
            Unsigned = false;
        if (_bitWidth < 16)
            BitWidth = 16;
        return (short) (Sample() * maxValue);
    }
    public short NextInt16(short minValue, short maxValue)
    {
        if (minValue > maxValue)
            throw new ArgumentException("maxValue must be greater than or equal to minValue");
        if (Unsigned)
            Unsigned = false;
        if (_bitWidth < 16)
            BitWidth = 16;
        return (short) Next(minValue, maxValue);
    }
    public ushort NextUInt16()
    {
        if (!Unsigned)
            Unsigned = true;
        if (_bitWidth < 16)
            BitWidth = 16;
        return (ushort) Internal();
    }
    public ushort NextUInt16(ushort maxValue)
    {
        if (!Unsigned)
            Unsigned = true;
        if (_bitWidth < 16)
            BitWidth = 16;
        return (ushort) (Sample() * maxValue);
    }
    public ushort NextUInt16(ushort minValue, ushort maxValue)
    {
        if (minValue > maxValue)
            throw new ArgumentException("maxValue must be greater than or equal to minValue");
        if (!Unsigned)
            Unsigned = true;
        if (_bitWidth < 16)
            BitWidth = 16;
        return (ushort) Next(minValue, maxValue);
    }
    public int NextInt24()
    {
        BitWidth = 24;
        if (Unsigned)
            Unsigned = false;
        return (int) Internal();
    }
    public int NextInt24(int maxValue)
    {
        if (maxValue < 0)
            throw new ArgumentException("maxValue must be greater than zero.");
        if (Unsigned)
            Unsigned = false;
        BitWidth = 24;
        return (int) (Sample() * maxValue);
    }
    public int NextInt24(int minValue, int maxValue)
    {
        if (minValue > maxValue)
            throw new ArgumentException("maxValue must be greater than or equal to minValue");
        if (Unsigned)
            Unsigned = false;
        BitWidth = 24;
        return (int) Next(minValue, maxValue);
    }
    public uint NextUInt24()
    {
        if (!Unsigned)
            Unsigned = true;
        BitWidth = 24;
        return (uint) Internal();
    }
    public uint NextUInt24(uint maxValue)
    {
        if (!Unsigned)
            Unsigned = true;
        BitWidth = 24;
        return (uint) (Sample() * maxValue);
    }
    public uint NextUInt24(uint minValue, uint maxValue)
    {
        if (minValue > maxValue)
            throw new ArgumentException("maxValue must be greater than or equal to minValue");
        if (!Unsigned)
            Unsigned = true;
        BitWidth = 24;
        return (uint) Next(minValue, maxValue);
    }
    public uint NextUInt32()
    {
        if (!Unsigned)
            Unsigned = true;
        if (_bitWidth < 32)
            BitWidth = 32;
        return (uint) Internal();
    }
    public uint NextUInt32(uint maxValue)
    {
        if (!Unsigned)
            Unsigned = true;
        if (_bitWidth < 32)
            BitWidth = 32;
        return (uint) (Sample() * maxValue);
    }
    public uint NextUInt32(uint minValue, uint maxValue)
    {
        if (minValue > maxValue)
            throw new ArgumentException("maxValue must be greater than or equal to minValue");
        if (!Unsigned)
            Unsigned = true;
        if (_bitWidth < 32)
            BitWidth = 32;
        return (uint) Next(minValue, maxValue);
    }
    public int NextInt32()
    {
        if (Unsigned)
            Unsigned = false;
        if (_bitWidth < 32)
            BitWidth = 32;
        return (int) Internal();
    }
    public int NextInt32(int maxValue)
    {
        if (maxValue < 0)
            throw new ArgumentException("maxValue must be greater than zero.");
        if (Unsigned)
            Unsigned = false;
        if (_bitWidth < 32)
            BitWidth = 32;
        return (int) (Sample() * maxValue);
    }
    public int NextInt32(int minValue, int maxValue)
    {
        if (minValue > maxValue)
            throw new ArgumentException("maxValue must be greater than or equal to minValue");
        if (Unsigned)
            Unsigned = false;
        if (_bitWidth < 32)
            BitWidth = 32;
        return (int) Next(minValue, maxValue);
    }
    public long NextUInt40()
    {
        if (!Unsigned)
            Unsigned = true;
        BitWidth = 40;
        return (long) Internal();
    }
    public long NextUInt40(long maxValue)
    {
        if (!Unsigned)
            Unsigned = true;
        BitWidth = 40;
        return (long) (Sample() * maxValue);
    }
    public long NextUInt40(long minValue, long maxValue)
    {
        if (minValue > maxValue)
            throw new ArgumentException("maxValue must be greater than or equal to minValue");
        if (!Unsigned)
            Unsigned = true;
        BitWidth = 40;
        return (long) Next(minValue, maxValue);
    }
    public long NextInt40()
    {
        if (Unsigned)
            Unsigned = false;
        BitWidth = 40;
        return (long) Internal();
    }
    public long NextInt40(long maxValue)
    {
        if (maxValue < 0)
            throw new ArgumentException("maxValue must be greater than zero.");
        if (Unsigned)
            Unsigned = false;
        BitWidth = 40;
        return (long) (Sample() * maxValue);
    }
    public long NextInt40(long minValue, long maxValue)
    {
        if (minValue > maxValue)
            throw new ArgumentException("maxValue must be greater than or equal to minValue");
        if (Unsigned)
            Unsigned = false;
        BitWidth = 40;
        return (long) Next(minValue, maxValue);
    }
    public ulong NextUInt48()
    {
        if (!Unsigned)
            Unsigned = true;
        BitWidth = 48;
        return (ulong) Internal();
    }
    public ulong NextUInt48(ulong maxValue)
    {
        if (!Unsigned)
            Unsigned = true;
        BitWidth = 48;
        return (ulong) (Sample() * maxValue);
    }
    public ulong NextUInt48(ulong minValue, ulong maxValue)
    {
        if (minValue > maxValue)
            throw new ArgumentException("maxValue must be greater than or equal to minValue");
        if (!Unsigned)
            Unsigned = true;
        BitWidth = 48;
        return (ulong) Next(minValue, maxValue);
    }
    public long NextInt48()
    {
        if (Unsigned)
            Unsigned = false;
        BitWidth = 48;
        return (long) Internal();
    }
    public long NextInt48(long maxValue)
    {
        if (maxValue < 0)
            throw new ArgumentException("maxValue must be greater than zero.");
        if (Unsigned)
            Unsigned = false;
        BitWidth = 48;
        return (long) (Sample() * maxValue);
    }
    public ulong NextUInt56()
    {
        if (!Unsigned)
            Unsigned = true;
        BitWidth = 56;
        return (ulong) Internal();
    }
    public ulong NextUInt56(ulong maxValue)
    {
        if (!Unsigned)
            Unsigned = true;
        BitWidth = 56;
        return (ulong) (Sample() * maxValue);
    }
    public ulong NextUInt56(ulong minValue, ulong maxValue)
    {
        if (minValue > maxValue)
            throw new ArgumentException("maxValue must be greater than or equal to minValue");
        if (!Unsigned)
            Unsigned = true;
        BitWidth = 56;
        return (uint) Next(minValue, maxValue);
    }
    public long NextInt56()
    {
        if (Unsigned)
            Unsigned = false;
        BitWidth = 56;
        return (long) Internal();
    }
    public long NextInt56(long maxValue)
    {
        if (maxValue < 0)
            throw new ArgumentException("maxValue must be greater than zero.");
        if (Unsigned)
            Unsigned = false;
        BitWidth = 56;
        return (long) (Sample() * maxValue);
    }
    public long NextInt56(long minValue, long maxValue)
    {
        if (minValue > maxValue)
            throw new ArgumentException("maxValue must be greater than or equal to minValue");
        if (Unsigned)
            Unsigned = false;
        BitWidth = 48;
        return (long) Next(minValue, maxValue);
    }
    public long NextInt64()
    {
        if (Unsigned)
            Unsigned = false;
        if (_bitWidth < 64)
            BitWidth = 64;
        return (long) Internal();
    }
    public long NextInt64(long maxValue)
    {
        if (maxValue < 0)
            throw new ArgumentException("maxValue must be greater than zero.");
        if (Unsigned)
            Unsigned = false;
        if (_bitWidth < 64)
            BitWidth = 64;
        return (long) (Sample() * maxValue);
    }
    public long NextInt64(long minValue, long maxValue)
    {
        if (minValue > maxValue)
            throw new ArgumentException("maxValue must be greater than or equal to minValue");
        if (Unsigned)
            Unsigned = false;
        if (_bitWidth < 64)
            BitWidth = 64;
        return (long) Next(minValue, maxValue);
    }
    public ulong NextUInt64()
    {
        if (!Unsigned)
            Unsigned = true;
        if (_bitWidth < 64)
            BitWidth = 64;
        return (ulong) Internal();
    }
    public ulong NextUInt64(ulong maxValue)
    {
        if (!Unsigned)
            Unsigned = true;
        if (_bitWidth < 64)
            BitWidth = 64;
        return (ulong) (Sample() * maxValue);
    }
    public ulong NextUInt64(ulong minValue, ulong maxValue)
    {
        if (minValue > maxValue)
            throw new ArgumentException("maxValue must be greater than or equal to minValue");
        if (!Unsigned)
            Unsigned = true;
        if (_bitWidth < 64)
            BitWidth = 64;
        return (ulong) Next(minValue, maxValue);
    }
    public BigInteger Next()
    {
        return Internal();
    }
    public BigInteger Next(BigInteger minValue, BigInteger maxValue)
    {
        if (minValue > maxValue)
            throw new ArgumentException("maxValue must be greater than or equal to minValue");
        return (BigInteger) (Sample() * (maxValue - minValue)) + minValue;
    }
    public UInt512 Next(UInt512 minValue, UInt512 maxValue)
    {
        if (minValue > maxValue)
            throw new ArgumentException("maxValue must be greater than or equal to minValue");
        var s = Sample();
        var f = (BigDecimal) ((BigInteger) maxValue - (BigInteger) minValue);
        return (BigInteger) (s * f);
    }
    public BigInteger Next(BigInteger maxValue)
    {
        if (maxValue < 0)
            throw new ArgumentException("maxValue must be greater than zero.");
        return (BigInteger) (Sample() * maxValue);
    }
    public unsafe double NextDouble()
    {
        var buf = new byte[8];
        GetBytes(buf);
        fixed (byte* ptr = buf)
        {
            return *(ulong*) ptr * (1.0 / ulong.MaxValue) * ulong.MaxValue;
        }
    }
    public BigRational NextBigRational()
    {
        return new BigRational(Internal(), Internal());
    }
    public decimal NextDecimal()
    {
        return new decimal(NextInt32(), NextInt32(), NextInt32(), NextBool(), NextUInt8(255));
    }
    public BigDecimal NextBigDecimal()
    {
        return Sample();
    }
    public byte[] GetNextByteArray(int size)
    {
        var ba = new byte[size];
        _crng.GetBytes(ba);
        return ba;
    }
    public char[] GetNextCharArray(int size)
    {
        var xbc = new byte[1];
        var ca  = new char[size];
        var ptr = 0;
        do
        {
            _crng.GetBytes(xbc);
            var c = xbc[0];
            if (c >= 0x20 && c <= 0x7F)
                ca[ptr++] = (char) c;
        } while (ptr < size);
        return ca;
    }
    public char NextChar()
    {
        var xbc = new byte[1];
        while (true)
        {
            _crng.GetBytes(xbc);
            var c = xbc[0];
            if (c >= 0x20 && c <= 0x7F)
                return (char) c;
        }
    }
    public string GetRandomString(int minLen, int maxLen)
    {
        return minLen == maxLen ? new string(GetNextCharArray(minLen)) : new string(GetNextCharArray((int) NextUInt32((uint) minLen, (uint) maxLen)));
    }
    private BigDecimal Sample()
    {
        var i = Internal();
        var s = i * (BigDecimal.One / MaxValue);
        if (s.Sign == -1)
            s = s * -1;
        if (s.IsZero)
            throw new Exception("Sample is zero.");
        return s;
    }
    public void GetBytes(byte[] data)
    {
        if (data == null)
            throw new ArgumentException("The buffer cannot be null.");
        _crng.GetBytes(data);
    }
    private BigInteger Internal()
    {
        if (Unsigned)
        {
            var buffer = new byte[_maxByteWidth + 1];
            _crng.GetBytes(buffer);
            buffer[_maxByteWidth] = 0;
            var n = new BigInteger(buffer);
            return !OddsOnly ? n : n | 1;
        }
        else
        {
            var buffer = new byte[_maxByteWidth];
            _crng.GetBytes(buffer);
            var n = new BigInteger(buffer);
            return !OddsOnly ? n : n | 1;
        }
    }
}