Runtime: Expose general purpose Crc32 APIs

[tannergooding]

Rationale

Computing a Cyclic Redundancy Check (CRC) is a common algorithm used for error detection in things like networks or storage. Additionally, modern hardware provides instruction level support for computing these values. It would be beneficial if we exposed a set of general-purpose methods which allow iterative CRC32 computation.

Proposed API

namespace System.Numerics
{
    public static class BitOperations
    {
        public static uint Crc32(uint crc, byte data);
        public static uint Crc32(uint crc, ushort data);
        public static uint Crc32(uint crc, uint data);
        public static uint Crc32(uint crc, ulong data);
    }
}

Open Questions

The output is generally treated as unsigned, however .NET considers unsigned integers (other than byte) as non-CLS compliant. It would be possible to expose both versions (those that take/return int and those that take/return uint). It would likewise be good on the input data to determine if they should be signed, unsigned, or both.

[Wraith2]

Is this using a specific polynomial? and if so which one? and can there be a way for the user to choose?

[tannergooding]

can there be a way for the user to choose?

Not if we want these accelerated by the underlying hardware.

• X86 uses: 0x1EDC6F41
• ARM uses: 0x04C11DB7 or 0x1EDC6F41 (depending on the instruction)

[Wraith2]

So if someone is dealing with zip or something using the old polynomial they'll still need to make their own. That's a bit of a shame.

Given that at least half of the time you want to calculate a crc you will be validating incoming data it might make sense to have a ReadOnlySpan<byte> overload (that works on a fixed length, leave looping to users).

[GrabYourPitchforks]

If we were to expose a CRC32 API over a buffer rather than an integral type I'd probably push for it not to be on the BitOperations class.

[Wraith2]

If BitOperations and these methods only exist to provide access to the hardware intrinsics I agree.
It would be useful to have a CRC32HashAlgorithm available which uses these operations if they are available.

[tannergooding]

If BitOperations and these methods only exist to provide access to the hardware intrinsics I agree

Right, this is namely meant to be a "cross-platform" version of the hardware intrinsics (much like the other functions on System.Numerics.BitOperations) and should allow users to easily get:

if (X86.Sse42.IsSupported) { }
else if (Arm.Crc32.IsSupported) { }
else { /* software fallback */ }

I agree that having a more general purpose class that allows polynomial customization and trivial operation over spans of data would be useful, but that isn't the immediate goal of this API.

[danmosemsft]

If I understand right, given the caller can't choose the polynomial, and we will use the fixed CPU specific algorithm if available, this API would only be useful for callers that are (a) not interoperating with some other format that has a chosen polynomial (such as zlib), and (b) do not need to exchange the value across architectures. Is that right?

[tannergooding]

We likely could provide both and we might even be able to expose the API in such a way that the JIT specially handles the method if the polynomial given is constant.

But as proposed, it would be limited to the given polynomials.

[danmosemsft]

I guess I'm wondering whether there's examples when this API with the "undefined" polynomial would be useful. But maybe that's not that different to asking when the intrinsics we already have would be useful. It would have to be when you're producing/consuming on the same machine. (Unless I misunderstand)

[terrajobst]

Video

• Looks good as proposed
• We can add overloads with custom polynomials later, but we should document the ones that we're using here.

C# namespace System.Numerics { public static class BitOperations { public static uint Crc32(uint crc, byte data); public static uint Crc32(uint crc, ushort data); public static uint Crc32(uint crc, uint data); public static uint Crc32(uint crc, ulong data); } }

[danmosemsft]

I watched the video and I still need clarification on my questions I think 😄

1. How will we choose the polynomial?
2. Whatever we pick, it it will only be hardware accelerated on x64/x86 OR ARMxx, or neither, but not both, right? But it will give the same results on all CPU/platforms?
3. Are we targeting a specific standard (eg., zlib, or some other RFC or file format) or is this primarily for when I don't care about the polynomial because I'm both calculating the CRC and verifying the CRC in my own app?

Also, it would be good to have an example of usage, especially since this API is expected to be used to checksum an array or stream. How does that look?

[tannergooding]

The polynomial is 0x1EDC6F41, it is accelerated on both x86/x64 and ARM64 (I'm not sure about ARM32). ARM64 has an additional polynomial that it can also accelerate, 0x04C11DB7, which would require something like Crc32(uint crc, byte data, uint polynomial) to support. The JIT could then optimize it when polynomial is a constant of that value.

The polynomial being used is for CRC32-Castagnoli, which is fairly popular/prevalent and adopted in several standards; but which is not universaly used.

[tannergooding]

In particular, wikipedia lists Castagnoli as used by iSCSI, SCTP, G.hn payload, SSE4.2, Btrfs, ext4, Ceph. Arm64's other polynomial is used by ISO 3309 (HDLC), ANSI X3.66 (ADCCP), FIPS PUB 71, FED-STD-1003, ITU-T V.42, ISO/IEC/IEEE 802-3 (Ethernet), SATA, MPEG-2, PKZIP, Gzip, Bzip2, POSIX cksum,[52] PNG,[53] ZMODEM, many others, but has no built-in acceleration for x86/x64.

[danmosemsft]

I see. That also seems to be the one used by the most popular package (CRC32C.NET)

[shaggygi]

Any plans to add Crc8 and Crc16 support, as well?

Used in protocol messages (https://sourceforge.net/p/bacnet/mailman/message/1259086/).

[Wraith2]

Not as part of this work because I don't believe there is hardware intrinsic that provides either of those.
There does seem to be some interest in having CRC algorithms in general but I think that would need a separate api proposal and it's too late in the release cycle to get them into 5 even if approved.

[Gnbrkm41]

Could I give this a try?

[tannergooding]

Sure thing, thanks @Gnbrkm41!