Vectorize custom polynomial CRC-32/-64

[bartonjs]

Extracting #124117 (comment) to a new issue:

For poly64: 0x104C11DB7 I match Intel's answers for forward constants with

private static ulong ComputeFoldingConstant(ulong poly, int power)
{
    UInt640 value = new(1);
    value.ShiftLeftEquals(power);
    int polyDeg = 32;

    while (value.Degree >= polyDeg)
    {
        int shift = value.Degree - polyDeg;
        UInt640 polyShifted = new(poly);
        polyShifted.ShiftLeftEquals(shift);
        value.XorEquals(ref polyShifted);
    }

    return value.ToUInt64();
}

Along with private struct UInt640, powered by private InlineArray10<ulong> _data;

But I guess I'm not mathy enough to figure it out for reflected polynomials (I can't come up with the k1Prime value)

My thoughts were to base-class ForwardTable and ReflectedTable with Forward and Reverse, capture the Update call there, do vector-if-appropriate-and-able, then call virtual UpdateScalar (just taking over from the current Update) for the fallback/remainder.

At least, my understanding of the paper is that the forward code and reflected/reverse code are different... so that was my plan. I'm not married to it, though.

// Crc32ParameterSet.cs
    public partial class Crc32ParameterSet
    {
        private abstract partial class ForwardCrc32
        {
            private readonly bool _canVectorize;

            partial void ComputeConstants(ref bool canVectorize);
            partial void UpdateVectorized(ref uint crc, ReadOnlySpan<byte> source, ref int bytesConsumed);
            
            internal ForwardCrc32(...) : base(...)
            {
                ComputeConstants(ref _canVectorize);
            }

            internal abstract uint UpdateScalar(uint crc, ReadOnlySpan<byte> source);

            internal sealed override uint Update(uint crc, ReadOnlySpan<byte> source)
            {
                if (_canVectorize)
                {
                    int consumed = 0;
                    UpdateVectorized(ref crc, source, ref consumed);

                    if (consumed == source.Length)
                    {
                        return crc;
                    }

                    source = source.Slice(consumed);
                }
                
                return UpdateScalar(source);
            }
        }
    }

// Crc32ParameterSet.Vectorized.cs
#if NET
namespace System.IO.Hashing
{
    public partial class Crc32ParameterSet
    {
        private abstract partial class ForwardCrc32
        {
            private uint _k1; // etc

            partial void ComputeConstants(ref bool canVectorize)
            {
                if (...)
                {
                    canVectorize = true;
                    _k1 = ComputeFoldingConstant(Polynomial, 4 * 128 + 64);
                    // ...
                }
            }

            partial void UpdateVectorized(uint crc, ReadOnlySpan<byte> source, ref int bytesConsumed)
            {
                if (source.IsLongEnoughToBeWorthwhile)
                {
                    // Code goes here?
                }
            }
        }
    }
}
#endif

[dotnet-policy-service]

Tagging subscribers to this area: @dotnet/area-system-io-hashing, @bartonjs, @vcsjones
See info in area-owners.md if you want to be subscribed.