using BenchmarkDotNet.Attributes;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading.Tasks;
using BenchmarkDotNet.Configs;
using BenchmarkDotNet.Jobs;
using BenchmarkDotNet.Running;
using Xunit;

namespace DeBruijnBenchmark
{
    public class Program
    {
        public static void Main()
        {
            Console.WriteLine(Vector.IsHardwareAccelerated);
            if (!Vector.IsHardwareAccelerated) throw new ArgumentException();
            Console.WriteLine(FirstByteBenchmark._vectors[0]);
            BenchmarkRunner.Run<FirstByteBenchmark>();
        }
    }
    public class Config : ManualConfig
    {
        public Config()
        {
            // gets too slow otherwise
            Add(Job.Default
                    .WithLaunchCount(1) // benchmark process will be launched only once
                    .WithIterationTime(200) // 200ms per iteration
                    .WithWarmupCount(10) // 10 warmup iteration
                    .WithTargetCount(10) // 10 target iteration
            );
        }
    }

    [Config(typeof(Config))]
    public class FirstByteBenchmark
    {
        private static readonly byte[] Debruijn64Xor =
        {
            0, 5, 0, 7, 6, 3, 0, 7,
            7, 6, 5, 4, 3, 2, 0, 7,
            6, 7, 4, 6, 6, 5, 2, 5,
            4, 4, 3, 2, 2, 1, 0, 7,
            5, 6, 3, 7, 5, 4, 1, 6,
            4, 6, 2, 5, 3, 2, 1, 5,
            3, 4, 1, 4, 2, 3, 1, 3,
            1, 2, 1, 1, 0, 0, 0, 7,
        };

        static readonly byte[] Debruijn64Long =
{
            0, 0, 0, 7, 0, 4, 7, 5, 3, 0, 2, 4, 0, 7, 1, 5,
            7, 3, 2, 0, 2, 2, 4, 2, 6, 1, 7, 4, 3, 1, 6, 4,
            7, 6, 3, 5, 3, 2, 0, 1, 7, 2, 1, 2, 6, 4, 3, 4,
            6, 5, 3, 1, 7, 1, 6, 4, 5, 3, 1, 6, 5, 6, 5, 5,
        };

        const ulong DEBRUIJN_SEQ64 = 0x03f79d71b4cb0a89;
        const long DEBRUIJN_SEQ64L = 0x26752B916FC7B0D;

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static int DebruijnFindByteXor(ulong v)
        {
            return Debruijn64Xor[((v ^ (v - 1)) * DEBRUIJN_SEQ64) >> 58];
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static int DebruijnFindByte(long v)
        {
            return Debruijn64Long[(ulong)((v & -v) * DEBRUIJN_SEQ64L) >> 58];
        }

        /// <summary>
        /// Find first byte
        /// </summary>
        /// <param  name="byteEquals"></param >
        /// <returns>The first index of the result vector</returns>
        /// <exception cref="InvalidOperationException">byteEquals = 0</exception>
        private static int FindFirstEqualByteOld(ref Vector<byte> byteEquals)
        {
            // Quasi-tree search

            var vector64 = Vector.AsVectorInt64(byteEquals);
            for (var i = 0; i < Vector<long>.Count; i++)
            {
                var longValue = vector64[i];
                if (longValue == 0) continue;

                return (i << 3) +
                       ((longValue & 0x00000000ffffffff) > 0
                           ? (longValue & 0x000000000000ffff) > 0
                               ? (longValue & 0x00000000000000ff) > 0 ? 0 : 1
                               : (longValue & 0x0000000000ff0000) > 0 ? 2 : 3
                           : (longValue & 0x0000ffff00000000) > 0
                               ? (longValue & 0x000000ff00000000) > 0 ? 4 : 5
                               : (longValue & 0x00ff000000000000) > 0 ? 6 : 7);
            }
            throw new InvalidOperationException();
        }

        /// <summary>
        /// Find first byte
        /// </summary>
        /// <param  name="byteEquals"></param >
        /// <returns>The first index of the result vector</returns>
        /// <exception cref="InvalidOperationException">byteEquals = 0</exception>

        internal static int FindFirstEqualByteDeBrujinXor(ref Vector<byte> byteEquals)
        {
            var vector64 = Vector.AsVectorUInt64(byteEquals);
            for (var i = 0; i < Vector<ulong>.Count; i++)
            {
                var longValue = vector64[i];
                if (longValue == 0) continue;

                return (i << 3) + DebruijnFindByteXor(longValue);
            }
            throw new InvalidOperationException();
        }

        /// <summary>
        /// Find first byte
        /// </summary>
        /// <param  name="byteEquals"></param >
        /// <returns>The first index of the result vector</returns>
        /// <exception cref="InvalidOperationException">byteEquals = 0</exception>

        internal static int FindFirstEqualByteDeBrujin(ref Vector<byte> byteEquals)
        {
            var vector64 = Vector.AsVectorInt64(byteEquals);
            for (var i = 0; i < Vector<long>.Count; i++)
            {
                var longValue = vector64[i];
                if (longValue == 0) continue;

                return (i << 3) + DebruijnFindByte(longValue);
            }
            throw new InvalidOperationException();
        }

        internal static int FindFirstByteNaive(byte[] bytes)
        {
            for (int i = 0; i < bytes.Length; i++)
            {
                if (bytes[i] != 0) return i;
            }
            throw new InvalidOperationException();
        }



        public static readonly byte[][] _vectors = InitVectors();

        static byte[][] InitVectors()
        {
            int vbCount = Vector<byte>.Count;
            var vectors = new byte[vbCount][];
            for (int i = 0; i < vectors.Length; i++)
            {
                byte[] vectorData = new byte[vbCount];
                vectorData[i] = 1;
                vectors[i] = vectorData;
            }
            return vectors;
        }


        //static Vector<byte>[] InitVectors()
        //{
        //    int vbCount = Vector<byte>.Count;
        //    var vectors = new Vector<byte>[vbCount];
        //    for (int i = 0; i < vectors.Length; i++)
        //    {
        //        byte[] vectorData = new byte[vbCount];
        //        vectorData[i] = 1;
        //        vectors[i] = new Vector<byte>(vectorData);
        //    }
        //    return vectors;
        //}




        [Params(31, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)]
        public int ByteSet { get; set; }


        [Benchmark]
        public int FirstByteVector()
        {
            var bytes = _vectors[ByteSet];
            var vector = new Vector<byte>(bytes);
            return FindFirstEqualByteOld(ref vector);
        }

        [Benchmark]
        public int FirstByteDeBruijnXor()
        {
            var bytes = _vectors[ByteSet];
            var vector = new Vector<byte>(bytes);
            return FindFirstEqualByteDeBrujinXor(ref vector);
        }

        [Benchmark]
        public int FirstByteDeBruijnClassic()
        {
            var bytes = _vectors[ByteSet];
            var vector = new Vector<byte>(bytes);
            return FindFirstEqualByteDeBrujin(ref vector);
        }

        [Benchmark]
        public int FindFirstByteNaive()
        {
            var bytes = _vectors[ByteSet];
            return FindFirstByteNaive(bytes);

        }

        [Theory]
        [InlineData(0)]
        [InlineData(1)]
        [InlineData(2)]
        [InlineData(3)]
        [InlineData(4)]
        [InlineData(5)]
        [InlineData(6)]
        [InlineData(7)]
        [InlineData(8)]
        [InlineData(9)]
        [InlineData(10)]
        [InlineData(11)]
        [InlineData(12)]
        [InlineData(13)]
        [InlineData(14)]
        [InlineData(15)]
        public void AssertFirstByte(int b)
        {
            var bytes = _vectors[b];
            var vvalue = new Vector<byte>(bytes);
            int dbPos = FindFirstEqualByteDeBrujin(ref vvalue);
            int vPos = FindFirstEqualByteOld(ref vvalue);
            int dbxPos = FindFirstEqualByteDeBrujinXor(ref vvalue);
            int pos = FindFirstByteNaive(bytes);
            Assert.Equal(b, dbPos);
            Assert.Equal(b, vPos);
            Assert.Equal(b, dbxPos);
            Assert.Equal(b, pos);
        }
    }
}