Parameterized CRC computations

[bartonjs]

Background and motivation

Since the addition of CRC-32 (also known as CRC-32/ADCCP, CRC-32/IEEE-802.3, CRC-32/ISO-HLDP, CRC-32/PKZIP, CRC-32/V-42, CRC-32/XZ) and CRC-64 (also known as CRC-64/ECMA-182) there have been various requests for other polynomial-basis variants (#78063, #85222) and sizes (#117078).

This proposal generalizes the requests into support for bringing any 8, 16, 32, or 64-bit polynomial, but also allows us to predefine and/or optimize common ones.

API Proposal

All API here is for the System.IO.Hashing nuget package, netstandard2.0+

namespace System.IO.Hashing;

[System.CLSCompliantAttribute(false)]
public abstract partial class Crc32ParameterSet
{
    internal Crc32ParameterSet();

    public uint Polynomial { get; }
    public uint InitialValue { get; }
    public uint FinalXorValue { get; }
    public bool ReflectInput { get; }
    public bool ReflectOutput { get; }

    // Optional.
    // The easy value for people to use is `CRC(data || CRC(data)))`, but most things talking about "residue" use
    // `CRC(data || CRC(data)) ^ FinalXorValue` (because it's from before the XOR), as a "faster" way to validate.
    public uint Residue { get; }

    // Optional, currently omitted.  Would have to capture in Create.
    // public string Name { get; }

    // Writes the CRC into a byte array using the ordering that guarantees the residue relationship.
    // ReflectedOutput == LittleEndian
    public void ComputeBytes(System.ReadOnlySpan<byte> source, System.Span<byte> destination);

    // abstract to distinguish between table-based (via Create) and optimized.
    // could change to template method pattern to keep virtual out of the public API,
    // but the methods have no validation, so it's lower value.
    public abstract uint Update(uint value, System.ReadOnlySpan<byte> source);
    public virtual uint Compute(System.ReadOnlySpan<byte> source);
    public virtual uint Finalize(uint value);

    // reflectInput almost always == reflectOutput, but CRC-12/UMTS aka CRC-12/3GPP is "crossed-endian", so being flexible.
    public static Crc32ParameterSet Create(uint polynomial, uint initialValue, uint finalXorValue, bool reflectInput, bool reflectOutput);
}

public abstract partial class Crc32ParameterSet
{
    // Option 1: All 32-bit values from https://reveng.sourceforge.io/crc-catalogue/all.htm using that site's names, prefix-trimmed.
    // Pro: We don't miss anything.
    // Con: Name them.
    public static Crc32ParameterSet Aixm { get; }
    public static Crc32ParameterSet Autosar { get; }
    public static Crc32ParameterSet Base91D { get; }
    public static Crc32ParameterSet Bzip2 { get; }
    public static Crc32ParameterSet CdRomEdc { get; }
    public static Crc32ParameterSet Cksum { get; }
    public static Crc32ParameterSet IscsiCrc { get; }
    public static Crc32ParameterSet IsoHdlc { get; }
    public static Crc32ParameterSet Jamcrc { get; }
    public static Crc32ParameterSet Mef { get; }
    public static Crc32ParameterSet Mpeg2 { get; }
    public static Crc32ParameterSet Xfer { get; }

    // Option 2: Just ones we can optimize and/or have been requested
    public static Crc32ParameterSet Crc32 { get; } // ISO-HDLC above, ARM Crc32 intrinsics
    public static Crc32ParameterSet Crc32C { get; } // BASE91-D above, x86 SSE 4.2 intrinsics, ARM Crc32 intrinsics
    // ILC uses JAMCRC, but they could just call Create.
}

[System.CLSCompliantAttribute(false)]
public abstract partial class Crc64ParameterSet
{
    internal Crc64ParameterSet();

    public ulong Polynomial { get; }
    public ulong InitialValue { get; }
    public ulong FinalXorValue { get; }
    public bool ReflectInput { get; }
    public bool ReflectOutput { get; }

    public ulong Residue { get; }

    public void ComputeBytes(System.ReadOnlySpan<byte> source, System.Span<byte> destination);

    public abstract ulong Update(ulong value, System.ReadOnlySpan<byte> source);
    public virtual ulong Compute(System.ReadOnlySpan<byte> source);
    public virtual ulong Finalize(ulong value);

    public static Crc64ParameterSet Create(ulong polynomial, ulong initialValue, ulong finalXorValue, bool reflectInput, bool reflectOutput);
}

public abstract partial class Crc64ParameterSet
{
    // ECMA-182 is Crc64, and optimized.
    // NVME has been specifically requested.

    public static System.IO.Hashing.Crc64ParameterSet Ecma182 { get { throw null; } }
    public static System.IO.Hashing.Crc64ParameterSet GoIso { get { throw null; } }
    public static System.IO.Hashing.Crc64ParameterSet Ms { get { throw null; } }
    public static System.IO.Hashing.Crc64ParameterSet Nvme { get { throw null; } }
    public static System.IO.Hashing.Crc64ParameterSet Redis { get { throw null; } }
    public static System.IO.Hashing.Crc64ParameterSet We { get { throw null; } }
    public static System.IO.Hashing.Crc64ParameterSet Xz { get { throw null; } }
}

[System.CLSCompliantAttribute(false)]
public abstract partial class Crc16ParameterSet
{
    internal Crc16ParameterSet();

    public ushort Polynomial { get; }
    public ushort InitialValue { get; }
    public ushort FinalXorValue { get; }
    public bool ReflectInput { get; }
    public bool ReflectOutput { get; }

    public ushort Residue { get; }

    public void ComputeBytes(System.ReadOnlySpan<byte> source, System.Span<byte> destination);

    public abstract ushort Update(ushort value, System.ReadOnlySpan<byte> source);
    public virtual ushort Compute(System.ReadOnlySpan<byte> source);
    public virtual ushort Finalize(ushort value);

    public static Crc16ParameterSet Create(ushort polynomial, ushort initialValue, ushort finalXorValue, bool reflectInput, bool reflectOutput);
}

// Future: Specific CRC-16 parameter sets, or all named ones from
// https://reveng.sourceforge.io/crc-catalogue/all.htm or
// https://www.crccalc.com/?crc=123456789&method=&datatype=ascii&outtype=hex

public abstract partial class Crc8ParameterSet
{
    internal Crc8ParameterSet();

    public byte Polynomial { get; }
    public byte InitialValue { get; }
    public byte FinalXorValue { get; }
    public bool ReflectInput { get; }
    public bool ReflectOutput { get; }

    public byte Residue { get; }

    public void ComputeBytes(System.ReadOnlySpan<byte> source, System.Span<byte> destination);

    public abstract byte Update(byte value, System.ReadOnlySpan<byte> source);
    public virtual byte Compute(System.ReadOnlySpan<byte> source);
    public virtual byte Finalize(byte value);

    public static Crc8ParameterSet Create(byte polynomial, byte initialValue, byte finalXorValue, bool reflectInput, bool reflectOutput);
}

// Future: Specific CRC-8 parameter sets, or all named ones from
// https://reveng.sourceforge.io/crc-catalogue/all.htm or
// https://www.crccalc.com/?crc=123456789&method=&datatype=ascii&outtype=hex

API Usage

uint crc32 = Crc32ParameterSet.IsoHdlp.Compute(data);
uint crc32c = Crc32ParameterSet.Base91D.Compute(data);
ulong crc64 = Crc64ParameterSet.Ecma182.Compute(data);
ulong crc64nvme = Crc64ParameterSet.Nvme.Compute(data);

Crc8ParameterSet bluetooth = Crc8ParameterSet.Create(0xA7, 0x00, 0x00, true, true);
byte crc8BT = bluetooth.Compute(data);

Alternative Designs

The parameter sets can be merged in with the Crc32 and Crc64 classes, either as just one type, or adding state into them:

public partial class Crc32
{
    public Crc32(uint polynomial, uint init, ...);
}

public partial class Crc32
{
    public Crc32(Crc32ParameterSet parameterSet);
    public Crc32ParameterSet ParameterSet { get; }
}
...

We can also try to support non-byte-aligned CRCs with a defaulted parameter of the CRC size:

public partial class Crc32ParameterSet
{
   public static Crc32ParameterSet Create(uint polynomial, uint init, ..., int outputSize=32);
}

But that has as a downside that Update gains error states (bits set on value that are impossible), and that it's no longer a CRC-32.

Risks

No response

[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.

[bartonjs]

A working version of Crc32ParameterSet and Crc64ParameterSet are available at https://github.com/bartonjs/runtime/tree/parameterized_crc_work

[bartonjs]

Video

• Let's leave the Residue property out.
• Move computation into the existing Crc32/Crc64 classes, taking a parameter set as a constructor/static-method parameter.
• Drop CRC-16 and CRC-8 for now.

namespace System.IO.Hashing;

public partial class Crc32
{
    public Crc32ParameterSet ParameterSet { get; }

    public Crc32(Crc32ParameterSet parameterSet);

    public static byte[] Hash(Crc32ParameterSet parameterSet, byte[] source);
    public static byte[] Hash(Crc32ParameterSet parameterSet, ReadOnlySpan<byte> source);
    public static int Hash(Crc32ParameterSet parameterSet, ReadOnlySpan<byte> source, Span<byte> destination);
    public static uint HashToUInt32(Crc32ParameterSet parameterSet, ReadOnlySpan<byte> source);
    public static bool TryHash(Crc32ParameterSet parameterSet, ReadOnlySpan<byte> source, Span<byte> destination, out int bytesWritten);
}

[System.CLSCompliantAttribute(false)]
public partial class Crc32ParameterSet
{
    internal Crc32ParameterSet();

    public uint Polynomial { get; }
    public uint InitialValue { get; }
    public uint FinalXorValue { get; }
    public bool ReflectInput { get; }
    public bool ReflectOutput { get; }

    public static Crc32ParameterSet Create(uint polynomial, uint initialValue, uint finalXorValue, bool reflectInput, bool reflectOutput);
}

public partial class Crc32ParameterSet
{
    public static Crc32ParameterSet Crc32 { get; }
    public static Crc32ParameterSet Crc32C { get; }
}

public partial class Crc64
{
    public Crc64ParameterSet ParameterSet { get; }

    public Crc64(Crc64ParameterSet parameterSet);

    public static byte[] Hash(Crc64ParameterSet parameterSet, byte[] source);
    public static byte[] Hash(Crc64ParameterSet parameterSet, ReadOnlySpan<byte> source);
    public static int Hash(Crc64ParameterSet parameterSet, ReadOnlySpan<byte> source, Span<byte> destination);
    public static ulong HashToUInt64(Crc64ParameterSet parameterSet, ReadOnlySpan<byte> source);
    public static bool TryHash(Crc64ParameterSet parameterSet, ReadOnlySpan<byte> source, Span<byte> destination, out int bytesWritten);
}

[System.CLSCompliantAttribute(false)]
public partial class Crc64ParameterSet
{
    internal Crc64ParameterSet();

    public ulong Polynomial { get; }
    public ulong InitialValue { get; }
    public ulong FinalXorValue { get; }
    public bool ReflectInput { get; }
    public bool ReflectOutput { get; }

    public static Crc64ParameterSet Create(ulong polynomial, ulong initialValue, ulong finalXorValue, bool reflectInput, bool reflectOutput);
}

public partial class Crc64ParameterSet
{
    public static Crc64ParameterSet Crc64 { get; }
    public static Crc64ParameterSet Nvme { get; }
}

[rmja]

Please include crc-16 as well. It is really useful for various iot network protocols.