crc-fast 1.7.0

World's fastest generic CRC32 and CRC64 calculator using SIMD. Supplies a C-compatible shared library for use in other languages.
Documentation

crc-fast

Test status Latest Version Documentation

World's fastest generic CRC calculator for all known CRC-32 and CRC-64 variants, as well as bring-your-own custom parameters, using SIMD intrinsics, which can exceed 100GiB/s on modern systems.

Supports acceleration on aarch64, x86_64, and x86 architectures, plus has a safe non-accelerated table-based software fallback for others.

The crc crate is ~0.5GiB/s by default, so this is up to >220X faster.

This is unique, not just because of the performance, but also because I couldn't find a single generic SIMD-accelerated implementation (in any language) which worked for all known variants, using the Rocksoft model, especially the "non-reflected" variants.

So I wrote one. :)

Other languages

Supplies a C/C++ compatible library for use with other non-Rust languages.

Implementations

Changes

See CHANGELOG.

Build & Install

cargo build will obviously build the library, including the C-compatible library.

A very basic Makefile is supplied which supports make install to install the shared library and header file to the local system. Specifying the DESTDIR environment variable will allow you to customize the install location.

DESTDIR=/my/custom/path make install

Usage

Add crc-fast = version = "1.5" to your Cargo.toml dependencies, which will enable every available optimization for the stable toolchain.

Digest

Implements the digest::DynDigest trait for easier integration with existing Rust code.

Creates a Digest which can be updated over time, for stream processing, intermittent workloads, etc, enabling finalizing the checksum once processing is complete.

use crc_fast::{Digest, CrcAlgorithm::Crc32IsoHdlc};

let mut digest = Digest::new(Crc32IsoHdlc);
digest.update(b"1234");
digest.update(b"56789");
let checksum = digest.finalize();

assert_eq!(checksum, 0xcbf43926);

Digest Write

Implements the std::io::Write trait for easier integration with existing Rust code.

use std::env;
use std::fs::File;
use crc_fast::{Digest, CrcAlgorithm::Crc32IsoHdlc};

// for example/test purposes only, use your own file path
let binding = env::current_dir().expect("missing working dir").join("crc-check.txt");
let file_on_disk = binding.to_str().unwrap();

// actual usage
let mut digest = Digest::new(Crc32IsoHdlc);
let mut file = File::open(file_on_disk).unwrap();
std::io::copy( & mut file, & mut digest).unwrap();
let checksum = digest.finalize();

assert_eq!(checksum, 0xcbf43926);

checksum

Checksums a string.

 use crc_fast::{checksum, CrcAlgorithm::Crc32IsoHdlc};

let checksum = checksum(Crc32IsoHdlc, b"123456789");

assert_eq!(checksum, 0xcbf43926);

checksum_combine

Combines checksums from two different sources, which can be useful for distributed or multithreaded workloads, etc.

 use crc_fast::{checksum, checksum_combine, CrcAlgorithm::Crc32IsoHdlc};

let checksum_1 = checksum(Crc32IsoHdlc, b"1234");
let checksum_2 = checksum(Crc32IsoHdlc, b"56789");
let checksum = checksum_combine(Crc32IsoHdlc, checksum_1, checksum_2, 5);

assert_eq!(checksum, 0xcbf43926);

checksum_file

Checksums a file, which will chunk through the file optimally, limiting RAM usage and maximizing throughput. Chunk size is optional.

 use crc_fast::{checksum_file, CrcAlgorithm::Crc32IsoHdlc};

// for example/test purposes only, use your own file path
let binding = env::current_dir().expect("missing working dir").join("crc-check.txt");
let file_on_disk = binding.to_str().unwrap();

let checksum = checksum_file(Crc32IsoHdlc, file_on_disk, None);

assert_eq!(checksum.unwrap(), 0xcbf43926);

Custom CRC Parameters

For cases where you need to use CRC variants not included in the predefined algorithms, you can define custom CRC parameters and use the *_with_params functions.

Digest with custom parameters

Creates a Digest with custom CRC parameters for stream processing.

use crc_fast::{Digest, CrcParams};

// Define custom CRC-32 parameters (equivalent to CRC-32/ISO-HDLC)
let custom_params = CrcParams::new(
    "CRC-32/CUSTOM",
    32,
    0x04c11db7,
    0xffffffff,
    true,
    0xffffffff,
    0xcbf43926,
);

let mut digest = Digest::new_with_params(custom_params);
digest.update(b"123456789");
let checksum = digest.finalize();

assert_eq!(checksum, 0xcbf43926);

checksum_with_params

Checksums data using custom CRC parameters.

use crc_fast::{checksum_with_params, CrcParams};

// Define custom CRC-32 parameters (equivalent to CRC-32/ISO-HDLC)
let custom_params = CrcParams::new(
    "CRC-32/CUSTOM",
    32,
    0x04c11db7,
    0xffffffff,
    true,
    0xffffffff,
    0xcbf43926,
);

let checksum = checksum_with_params(custom_params, b"123456789");

assert_eq!(checksum, 0xcbf43926);

checksum_combine_with_params

Combines checksums from two different sources using custom CRC parameters.

use crc_fast::{checksum_with_params, checksum_combine_with_params, CrcParams};

// Define custom CRC-32 parameters (equivalent to CRC-32/ISO-HDLC)
let custom_params = CrcParams::new(
    "CRC-32/CUSTOM",
    32,
    0x04c11db7,
    0xffffffff,
    true,
    0xffffffff,
    0xcbf43926,
);

let checksum_1 = checksum_with_params(custom_params, b"1234");
let checksum_2 = checksum_with_params(custom_params, b"56789");
let checksum = checksum_combine_with_params(custom_params, checksum_1, checksum_2, 5);

assert_eq!(checksum, 0xcbf43926);

checksum_file_with_params

Checksums a file using custom CRC parameters, chunking through the file optimally.

use std::env;
use crc_fast::{checksum_file_with_params, CrcParams};

// for example/test purposes only, use your own file path
let binding = env::current_dir().expect("missing working dir").join("crc-check.txt");
let file_on_disk = binding.to_str().unwrap();

// Define custom CRC-32 parameters (equivalent to CRC-32/ISO-HDLC)
let custom_params = CrcParams::new(
    "CRC-32/CUSTOM",
    32,
    0x04c11db7,
    0xffffffff,
    true,
    0xffffffff,
    0xcbf43926,
);

let checksum = checksum_file_with_params(custom_params, file_on_disk, None);

assert_eq!(checksum.unwrap(), 0xcbf43926);

C/C++ compatible library

cargo build will produce a shared library target (.so on Linux, .dll on Windows, .dylib on macOS, etc) and an auto-generated libcrc_fast.h header file for use in non-Rust projects, such as through FFI. It will also produce a static library target (.a on Linux and macOS, .lib on Windows, etc) for projects which prefer statically linking.

There is a crc-fast PHP extension using it, for example.

Background

This implementation is based on Intel's Fast CRC Computation for Generic Polynomials Using PCLMULQDQ Instruction white paper, though it folds 8-at-a-time, like other modern implementations, rather than the 4-at-a-time as in Intel's paper.

This library works on aarch64, x86_64, and x86 architectures, and is hardware-accelerated and optimized for each architecture.

Inspired by crc32fast, crc64fast, and crc64fast-nvme, each of which only accelerates a single, different CRC variant, and all of them were "reflected" variants.

In contrast, this library accelerates every known variant (and should accelerate any future variants without changes), including all the "non-reflected" variants.

Important CRC variants

While there are many variants, three stand out as being the most important and widely used (all of which are "reflected"):

CRC-32/ISCSI

Many, but not all, implementations simply call this crc32c and it's probably the 2nd most popular and widely used, after CRC-32/ISO-HDLC. It's used in iSCSI, ext4, btrfs, etc.

Both x86_64 and aarch64 have native hardware support for this CRC variant, so we can use fusion in many cases to accelerate it further by fusing SIMD CLMUL instructions with the native CRC instructions.

CRC-32/ISO-HDLC

Many, but not all, implementations simply call this crc32 and it may be the most popular and widely used. It's used in Ethernet, PKZIP, xz, etc.

Only aarch64 has native hardware support for this CRC variant, so we can use fusion on that platform, but not x86_64.

CRC-64/NVME

CRC-64/NVME comes from the NVM Express® NVM Command Set Specification (Revision 1.0d, December 2023), is AWS S3's recommended checksum option (as CRC64-NVME), and has also been implemented in the Linux kernel (where it's been called CRC-64/Rocksoft in the past).

Note that the Check value in the NVMe spec uses incorrect endianness (see Section 5.2.1.3.4, Figure 120, page 83) but all known public & private implementations agree on the correct value, which this library produces.

Acceleration targets

This library has baseline support for accelerating all known CRC-32 and CRC-64 variants on aarch64, x86_64, and x86 internally in pure Rust.

Checking your platform capabilities

There's an arch-check binary which will explain the selected target architecture.

// test it works on your system (patches welcome!)
cargo test

// examine the chosen acceleration targets
cargo run arch-check

// build for release
cargo build --release

Performance

Modern systems can exceed 100 GiB/s for calculating CRC-32/ISCSI, CRC-32/ISO-HDLC, CRC-64/NVME, and all other reflected variants. (Forward variants are slower, due to the extra shuffle-masking, but are still extremely fast in this library).

This is a summary of the performance for the most important and popular CRC checksums.

CRC-32/ISCSI (reflected)

AKA crc32c in many, but not all, implementations.

Arch Brand CPU System Target 1KiB (GiB/s) 1MiB (GiB/s)
x86_64 Intel Sapphire Rapids EC2 c7i.metal-24xl avx512-vpclmulqdq ~52 ~111
x86_64 AMD Genoa EC2 c7a.metal-48xl avx512-vpclmulqdq ~24 ~54
aarch64 AWS Graviton4 EC2 c8g.metal-48xl neon-pmull-eor3 ~21 ~53
aarch64 AWS Graviton2 EC2 c6g.metal neon-pmull ~11 ~17
aarch64 Apple M3 Ultra Mac Studio (32 core) neon-pmull-eor3 ~49 ~99
aarch64 Apple M4 Max MacBook Pro 16" (16 core) neon-pmull-eor3 ~56 ~94

CRC-32/ISO-HDLC (reflected)

AKA crc32 in many, but not all, implementations.

Arch Brand CPU System Target 1KiB (GiB/s) 1MiB (GiB/s)
x86_64 Intel Sapphire Rapids EC2 c7i.metal-248xl avx512-vpclmulqdq ~20 ~88
x86_64 AMD Genoa EC2 c7a.metal-48xl avx512-vpclmulqdq ~15 ~55
aarch64 AWS Graviton4 EC2 c8g.metal-48xl neon-pmull-eor3 ~21 ~53
aarch64 AWS Graviton2 EC2 c6g.metal neon-pmull ~11 ~17
aarch64 Apple M3 Ultra Mac Studio (32 core) neon-pmull-eor3 ~48 ~98
aarch64 Apple M4 Max MacBook Pro 16" (16 core) neon-pmull-eor3 ~56 ~94

CRC-64/NVME (reflected)

AWS S3's recommended checksum option

Arch Brand CPU System Target 1KiB (GiB/s) 1MiB (GiB/s)
x86_64 Intel Sapphire Rapids EC2 c7i.metal-24xl avx512-vpclmulqdq ~21 ~110
x86_64 AMD Genoa EC2 c7a.metal-48xl avx512-vpclmulqdq ~16 ~55
aarch64 AWS Graviton4 EC2 c8g.metal-48xl neon-pmull-eor3 ~21 ~41
aarch64 AWS Graviton2 EC2 c6g.metal neon-pmull ~11 ~16
aarch64 Apple M3 Ultra Mac Studio (32 core) neon-pmull-eor3 ~50 ~72
aarch64 Apple M4 Max MacBook Pro 16" (16 core) neon-pmull-eor3 ~52 ~72

CRC-32/BZIP2 (forward)

Arch Brand CPU System Target 1KiB (GiB/s) 1MiB (GiB/s)
x86_64 Intel Sapphire Rapids EC2 c7i.metal-24xl avx512-vpclmulqdq ~20 ~56
x86_64 AMD Genoa EC2 c7a.metal-48xl avx512-vpclmulqdq ~14 ~43
aarch64 AWS Graviton4 EC2 c8g.metal-48xl neon-pmull-eor3 ~18 ~40
aarch64 AWS Graviton2 EC2 c6g.metal neon-pmull ~9 ~14
aarch64 Apple M3 Ultra Mac Studio (32 core) neon-pmull-eor3 ~41 ~59
aarch64 Apple M4 Max MacBook Pro 16" (16 core) neon-pmull-eor3 ~47 ~64

CRC-64/ECMA-182 (forward)

Arch Brand CPU System Target 1KiB (GiB/s) 1MiB (GiB/s)
x86_64 Intel Sapphire Rapids EC2 c7i.metal-24xl avx512-vpclmulqdq ~21 ~56
x86_64 AMD Genoa EC2 c7a.metal-48xl avx512-vpclmulqdq ~14 ~43
aarch64 AWS Graviton4 EC2 c8g.metal-48xl neon-pmull-eor3 ~19 ~40
aarch64 AWS Graviton2 EC2 c6g.metal neon-pmull ~9 ~14
aarch64 Apple M3 Ultra Mac Studio (32 core) neon-pmull-eor3 ~40 ~59
aarch64 Apple M4 Max MacBook Pro 16" (16 core) neon-pmull-eor3 ~46 ~61

Other CRC widths

There are a lot of other known CRC widths and variants, ranging from CRC-3/GSM to CRC-82/DARC, and everything in between.

Since Awesome doesn't use any that aren't CRC-32 or CRC-64 in length, this library doesn't currently support them, either. (It should support any newly created or discovered CRC-32 and CRC-64 variants, though, with zero changes other than defining the Rocksoft parameters).

In theory, much of the "heavy lifting" has been done, so it should be possible to add other widths with minimal effort.

PRs welcome!

References

License

cfc-fast is dual-licensed under