Crc32C: an assembly library for .NET, on seven platforms
samples/Crc32C computes
CRC-32C, the Castagnoli checksum that iSCSI, ext4, Btrfs, SCTP and gRPC use. It is about 380
lines of NASM for x64 and 300 lines of GNU-syntax assembly for ARM64, half of them comments.
samples/Crc32C.Net
lets C# call it. It is built the way you would ship a hot routine in native code:
- a freestanding shared library for all seven RIDs. It needs nothing to load, so it loads
into any process of its platform:
crc32c.dll, 4.5 KB, with no imports on x64 and one on ARM64 (kernel32'sIsProcessorFeaturePresent);libcrc32c.so, 5.6 KB, with noDT_NEEDED, for glibc and musl alike;libcrc32c.dylib, with no dependent library.
- three code paths and a dispatcher that picks the fastest one the CPU supports, once;
- a kernel that keeps the CRC instruction busy every cycle: 21.8 GB/s on 1 MiB on x64,
3.7 times the C# loop with
BitOperations.Crc32Cand 2.75 times the obvious loop in assembly (measured); - a stable binary interface: five exported names on every OS (versioned on Linux), and nothing else visible.
| File | What it holds |
|---|---|
Crc32C.asmproj |
the project: the seven RIDs, AssemblyName, ExportsFile, a Linux LinkerArg, the package metadata |
crc32c.asm |
the x64 code (NASM, through asmsdk.inc): the dispatcher, the three paths, the table and constants |
crc32c.s |
the ARM64 code (GNU syntax, through asmsdk-gnu.inc): the same exports and the same algorithm |
crc32c.map |
the exports file (a linker version script) |
include/crc32c.inc |
the interface for NASM callers, packed with the library |
../Crc32C.Net/Crc32C.cs |
the C# API: Crc32C.HashToUInt32, Crc32C.Append, Crc32C.Path |
The API
uint32_t crc32c_append(uint32_t crc, const void *data, size_t length);
/* The path crc32c_append runs here: 1 portable, 2 hardware, 3 hardware + 3-way */
int crc32c_implementation(void);
The convention is zlib's (and System.IO.Hashing's): pass 0 to start a checksum, and a previous
result to continue one, so appending b to the checksum of a gives the checksum of a
followed by b. "123456789" gives 0xE3069283, the catalogue check value.
The three paths are exported too, as crc32c_append_portable, crc32c_append_hardware and
crc32c_append_hardware_3way, so that the tests can check each one and the benchmark can time
each one. They check nothing: calling a hardware path on a CPU without the instructions raises
SIGILL (an illegal-instruction exception on Windows).
The project
<Project Sdk="AsmFoundation.Sdk">
<PropertyGroup>
<RuntimeIdentifiers>win-x64;win-arm64;linux-x64;linux-arm64;linux-musl-x64;osx-x64;osx-arm64</RuntimeIdentifiers>
<AssemblyName>crc32c</AssemblyName>
<ExportsFile>crc32c.map</ExportsFile>
<PackageId>Samples.Crc32C</PackageId>
<Version>1.0.0</Version>
</PropertyGroup>
<ItemGroup>
<LinkerArg Include="-z defs" Condition="$(RuntimeIdentifier.StartsWith('linux'))" />
</ItemGroup>
</Project>
- Seven RIDs from two sources.
crc32c.asmhas no qualifier, so it builds every x64 RID.crc32c.sbuilds every ARM64 RID. See Sources per platform. - No
TargetFramework: the default,freestanding. Nothing here calls a C library. -z defsfails a Linux link if any symbol is left undefined, instead of failing when the library is loaded. For a freestanding library that proves it really needs nothing. It is ld.lld's syntax, so the item is conditioned on the Linux RIDs. lld-link and ld64.lld refuse undefined symbols anyway.PackageIdandVersionmakedotnet packproduceSamples.Crc32C.1.0.0.nupkg, with every RID's library in it; see Shipping to .NET through NuGet.
The exports file
CRC32C_1.0 {
global:
crc32c_append;
crc32c_implementation;
crc32c_append_portable;
crc32c_append_hardware;
crc32c_append_hardware_3way;
local:
*;
};
ExportsFile is NativeAOT's name for the linker's version script. On Linux, only the five names
under global stay in the dynamic symbol table, each as name@@CRC32C_1.0; local: * hides
every other label (the dispatcher, the table), so no other library can call or replace them. A
later release would add names under a node CRC32C_1.1 that inherits CRC32C_1.0, and programs
built against 1.0 keep loading. On Windows and macOS, the SDK hands the same five names to
lld-link (-export:) and ld64.lld (-exported_symbol), which have no versions.
One library, two calling conventions
The x64 file serves Windows, whose convention passes the arguments in rcx, rdx, r8, and
Linux and macOS, whose System V convention uses rdi, rsi, rdx. Each exported function is
an asmsdk.inc FUNCTION that moves its OS's ARG1..ARG3 into a private convention every
path shares:
FUNCTION crc32c_append, 3
mov eax, ARG1d ; the crc
mov r10, ARG2 ; the data
mov r11, ARG3 ; the length
jmp [rel dispatch] ; dispatch starts as `resolve`
ENDFUNCTION
eax, r10 and r11 are volatile (caller-saved) in both conventions, as is every other
register the paths touch (rcx, rdx, r8, r9, xmm0-xmm2). So no path saves a register
on any OS, and the kernels keep the shape they had when the library was Linux-only. ARM64 needs
no such step: Windows, Linux and macOS all pass the arguments in w0, x1, x2.
One dispatcher, three paths
resolve:
call select ; picks the path, stores it in dispatch
mov rcx, rax
mov eax, r9d ; select handed the crc back in r9d: rax holds the path
jmp rcx ; and continues as that path
select:
mov r8, rbx ; cpuid destroys rbx, callee-saved on every OS
mov r9d, eax
mov eax, 1
cpuid
mov rbx, r8
lea rax, [rel impl_portable]
bt ecx, CPUID_ECX_SSE42
jnc .store
lea rax, [rel impl_hardware]
bt ecx, CPUID_ECX_PCLMULQDQ
jnc .store
lea rax, [rel impl_hardware_3way]
.store:
mov [rel dispatch], rax
ret
- The choice costs nothing after the first call:
crc32c_appendis a single indirect jump throughdispatch, which then points at the path itself. - No lock is needed. Threads that race through
selectall store the same value, and an aligned 8-byte store is atomic on x86-64 (and single-copy atomic on ARM64), so a reader sees eitherresolveor a whole path. dispatchlives in.data. It holds an address, so the loader fixes it up when the library loads, which needs a writable section. In.rodatathe Linux link would fail, and a macOS build would stop with ASM0081 (see Writing NASM for AsmSdk).- The paths are named by local labels (
impl_hardware), not by their exported names, the habit of ELF shared libraries, where another library could interpose an exported symbol.
On ARM64, the same dispatcher asks each OS in its own way:
| OS | How crc32c.s picks the path |
|---|---|
| Linux | reads the ID_AA64ISAR0_EL1 register (its CRC32 and AES fields). Linux emulates the read for user code (since kernel 4.11) |
| Windows | calls kernel32's IsProcessorFeaturePresent for the CRC32 and the crypto instructions: the library's one import. The SDK links kernel32 into every Windows output |
| macOS | takes the 3-way path: every Apple silicon CPU has both extensions, and macOS does not let user code read the ID registers |
| Path | x64 | ARM64 |
|---|---|---|
| portable | a 256-entry table, one byte per step; any x86-64 | the same table; any ARM64 |
| hardware | SSE4.2's crc32, 8 bytes per step |
the CRC32 extension's crc32cx, 8 bytes per step |
| hardware_3way | three crc32 chains per block, merged with PCLMULQDQ |
three crc32cx chains, merged with PMULL (the AES extension's carry-less multiply) |
Constants computed by the assemblers
The table and the kernel's merge constants are not copied from anywhere: each assembler computes them from the polynomial while it assembles the file. NASM does it with its preprocessor:
crc32c_table:
%assign CRC32C_BYTE 0
%rep 256
%assign CRC32C_REG CRC32C_BYTE
%rep 8
%assign CRC32C_REG (CRC32C_REG >> 1) ^ (CRC32C_POLY & -(CRC32C_REG & 1))
%endrep
dd CRC32C_REG
%assign CRC32C_BYTE CRC32C_BYTE + 1
%endrep
The same reflected "multiply by x" step, repeated n times from x⁰, gives x^n mod P, which is
what the kernel needs (below). A macro, X_POW n, runs it, so changing the kernel's lane size
recomputes its constants with no other edit. crc32c.s does the same with llvm-mc's .rept and
.set, and gets the same numbers: crc32cx is the same function as x64's crc32 r64, and PMULL
the same product as PCLMULQDQ.
The 3-way kernel
crc32 takes 3 cycles to produce a result but can start a new one every cycle. The obvious
loop, 8 bytes per instruction, makes each step wait for the previous one, so the instruction
idles two cycles out of three. The kernel splits each block into three lanes and runs three
independent chains, so a new crc32 starts every cycle:
%%lanes:
crc32 rax, qword [r10] ; lane 0
crc32 r8, qword [r10 + %1] ; lane 1
crc32 r9, qword [r10 + 2 * %1] ; lane 2
add r10, 8
dec ecx
jnz %%lanes
The three partial checksums are then merged. Lane 0's must be moved past the 2 lanes that follow
it, and lane 1's past 1 lane: "moving a CRC past n zero bytes" multiplies it by x^(8n) mod P. One
carry-less multiply (PCLMULQDQ) and one crc32 do that, with the constant x^(8n−33) mod P
(crc32 over 8 bytes multiplies by x³², and the reflected product carries one extra x). Both
products are folded into lane 2's last 8 bytes, so a single crc32 finishes the block:
movq xmm1, rax ; c0
movq xmm2, r8 ; c1
pclmulqdq xmm1, xmm0, 0x00 ; c0 * x^(8 * 2 lane - 33)
pclmulqdq xmm2, xmm0, 0x10 ; c1 * x^(8 * lane - 33)
pxor xmm1, xmm2
movq rdx, xmm1
xor rdx, qword [r10 + 2 * %1] ; lane 2's last 8 bytes
crc32 r9, rdx ; the block's CRC
The ARM64 kernel is the same, instruction for instruction: crc32cx for crc32, pmull for
pclmulqdq. The function runs 1,536-byte blocks (3 × 512), then 192-byte blocks (3 × 64), then
the single chain for the rest. The first lane of each block waits for the previous block's
merge, so small lanes pay that latency more often; two sizes keep both large and medium inputs
fast.
The derivation was checked on a bit-exact model of crc32 for every basis state and 10,000
random ones before the code was written; the tests then compare every path with a C# reference
at every length from 0 to 5,000 bytes, and a build with a wrong exponent fails 6 of them (see
Testing and measuring from C#).
Calling it from C#
Crc32C.Net is a class library with a ProjectReference to the .asmproj. The build carries
each RID's library under runtimes/<rid>/native/, listed in deps.json, and the .NET host
loads the one for the machine it runs on.
[assembly: DisableRuntimeMarshalling]
public static unsafe partial class Crc32C
{
public static uint Append(uint crc, ReadOnlySpan<byte> source)
{
fixed (byte* data = source)
{
return source.Length <= NoTransitionLimit
? AppendShort(crc, data, (nuint)source.Length)
: AppendLong(crc, data, (nuint)source.Length);
}
}
[LibraryImport("crc32c", EntryPoint = "crc32c_append")]
[SuppressGCTransition]
private static partial uint AppendShort(uint crc, byte* data, nuint length);
[LibraryImport("crc32c", EntryPoint = "crc32c_append")]
private static partial uint AppendLong(uint crc, byte* data, nuint length);
}
[LibraryImport]generates the call at compile time, and with onlyuint,byte*andnuintin the signature there is nothing to marshal;DisableRuntimeMarshallingmakes that a compile-time rule."crc32c"findscrc32c.dll,libcrc32c.soorlibcrc32c.dylib.SuppressGCTransitionfor inputs up to 4 KiB. A normal call switches the thread to preemptive mode and back: an empty call measured 9.6 ns with the switch and 3.4 ns without, which matters for a 64-byte record. Without the switch the GC cannot suspend the thread during the call, so it is kept for short inputs only: even the single-chain path finishes 4 KiB in well under a microsecond.Crc32C.Append(crc, data, path)runs one path, for tests and benchmarks, after checking that the CPU has it:Sse42.X64andPclmulqdqon x64,Crc32.Arm64andAeson ARM64. The native path functions check nothing, and an illegal instruction would end the process.- The library loads at the first call. On a platform none of the seven builds serves
(32-bit x86, for one), that call throws
DllNotFoundException.
How it is checked
- Its own tests: 21 xunit tests run every path against a C# reference. CI runs them natively on the five build machines (Windows x64 and Arm, Linux x64 and ARM64, Apple silicon), each with its own platform's build. In Docker they also pass on Alpine (musl), and under ARM64 emulation the library returns the same checksums.
ExampleTests: the exact exported names and their version, noDT_NEEDEDand no text relocation, the constants NASM computed (0x170076FA,0xDD7E3B0C,0x0D3B6092,0x9E4ADDF8and the table's first entries), the packages with their seven RIDs, and the library's tests and benchmark check on the machine running them.