// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.

#if NET

using System.Diagnostics;
using System.Runtime.CompilerServices;

namespace System.IO.Hashing
{
    internal static class CrcPolynomialHelper
    {
        internal static ulong ComputeFoldingConstantCrc32(ulong fullPoly, int power)
        {
            UInt640 poly = new(fullPoly);
            return ComputeFoldingConstant(poly, power);
        }

        internal static ulong ComputeFoldingConstantCrc64(ulong reducedPolynomial, int power)
        {
            UInt640 poly = new(1UL, reducedPolynomial);
            return ComputeFoldingConstant(poly, power);
        }

        private static ulong ComputeFoldingConstant(UInt640 poly, int power)
        {
            int polyDeg = poly.Degree;

            UInt640 value = new(1);
            value <<= power;

            while (value.Degree >= polyDeg)
            {
                int shift = value.Degree - polyDeg;
                UInt640 polyShifted = poly;
                polyShifted <<= shift;
                value ^= polyShifted;
            }

            return value.ToUInt64();
        }

        internal static ulong ComputeBarrettConstantCrc32(ulong fullPoly)
        {
            UInt640 poly = new(fullPoly);
            return ComputeBarrettConstant(poly, 64);
        }

        internal static ulong ComputeBarrettConstantCrc64(ulong reducedPolynomial)
        {
            UInt640 poly = new(1UL, reducedPolynomial);
            return ComputeBarrettConstant(poly, 128);
        }

        private static ulong ComputeBarrettConstant(UInt640 poly, int power)
        {
            int polyDeg = poly.Degree;

            UInt640 value = new(1);
            value <<= power;

            UInt640 quotient = default;

            while (value.Degree >= polyDeg)
            {
                int shift = value.Degree - polyDeg;
                UInt640 polyShifted = poly;
                polyShifted <<= shift;
                value ^= polyShifted;

                UInt640 bit = new(1);
                bit <<= shift;
                quotient ^= bit;
            }

            return quotient.ToUInt64();
        }

        [InlineArray(Length)]
        private struct UInt640
        {
            private const int Length = 10;
            private ulong _element;

            internal UInt640(ulong value)
            {
                this = default;
                this[0] = value;
            }

            internal UInt640(ulong high, ulong low)
            {
                this = default;
                this[0] = low;
                this[1] = high;
            }

            internal readonly int Degree
            {
                get
                {
                    for (int i = Length - 1; i >= 0; i--)
                    {
                        if (this[i] != 0)
                        {
                            return (i * 64) + (63 - (int)ulong.LeadingZeroCount(this[i]));
                        }
                    }

                    return -1;
                }
            }

            public void operator <<=(int count)
            {
                Debug.Assert(count >= 0);

                int wordShift = count >> 6; // count / 64
                int bitShift = count & 63;  // count % 64

                if (wordShift > 0)
                {
                    for (int i = Length - 1; i >= wordShift; i--)
                    {
                        this[i] = this[i - wordShift];
                    }

                    for (int i = wordShift - 1; i >= 0; i--)
                    {
                        this[i] = 0;
                    }
                }

                if (bitShift > 0)
                {
                    for (int i = Length - 1; i > 0; i--)
                    {
                        this[i] = (this[i] << bitShift) | (this[i - 1] >> (64 - bitShift));
                    }

                    this[0] <<= bitShift;
                }
            }

            public void operator ^=(in UInt640 other)
            {
                for (int i = 0; i < Length; i++)
                {
                    this[i] ^= other[i];
                }
            }

            internal readonly ulong ToUInt64()
            {
                return this[0];
            }
        }
    }
}

#endif