/slice-by-8-rs

Rust implementation of Intel Slice-By-8 hash algorithm

Primary LanguageRustMIT LicenseMIT

Slice-by-8

Crates.io License

Rust improved implementation of the Slice-by-8 intel algorithm from the paper "A Systematic Approach to building High Performance, Software-based, CRC Generators By Intel Researche and Development"

Slice-by-8 do not load the standard library (a.k.a #![no_std])

Status

Build Clippy docs.rs Test codecov

Table of contents

  1. Introduction
  2. Usage
    1. Using Hasher
    2. Using slice-by-8 functions
    3. Using your own lookup table
  3. Generate Lookup table
  4. Performance

Introduction

Slice-by-8 crate provides function that performs CRC hashing using improved variant of intel's Slice-by-8 algorithm. The crate provides the slice-by-8 algorithm that take the loopup table to use as parameter if you want to use your own. The crate also provides the CRC32 (Polynomial 0x04c11db7 ) available in slice_by_8::crc32 and the CRC32c (Polynomial 0x1EDC6F41 ) in slice_by_8::crc32c. CRC32c hash can use CRC32c intrinsics if enabled. You can enable intrinsic version on x86_64 target_arch by enabling sse4.2 target_feature or on aarch64 target_arch by enabling crc target_feature.

Usage

Using Hasher

use hud_slice_by_8::crc32::CRC32BuildHasher;
use std::collections::HashMap;
const KEY: &str = "hash";
const VALUE: &str = "me!";

// Create a HashMap that use CRC32Hasher to hash keys
let mut map = HashMap::with_hasher(CRC32BuildHasher::default());
map.insert(KEY, VALUE);

assert_eq!(map.get(&KEY), Some(&VALUE));

Using slice-by-8 functions

Slice-by-8 provides functions to hash slice of bytes.

use hud_slice_by_8::crc32c;

const HASH_ME: &[u8] = b"abcdefghijklmnopqrstuvwxyz";
assert_eq!(crc32c::slice_by_8(HASH_ME), 0x9EE6EF25);

Note: slice_by_8 is a similar to slice_by_8_with_seed with seed equals 0.

Using your own lookup table

You own lookup table must be [[u32; 256]; 8].

use hud_slice_by_8::slice_by_8;

let my_lookup_table: [[u32; 256]; 8] = hud_slice_by_8::generate_table(hud_slice_by_8::crc32::POLYNOMIAL);
const HASH_ME: &[u8] = b"abcdefghijklmnopqrstuvwxyz";

assert_eq!(slice_by_8(HASH_ME, &my_lookup_table), 0x4C2750BD);

Generate Lookup table

The crate provide generate_table function to generate a lookup table from a polynomial.

use hud_slice_by_8::generate_table;
use hud_slice_by_8::{crc32, crc32c};

assert_eq!(generate_table(crc32::POLYNOMIAL), crc32::LOOKUP_TABLE);
assert_eq!(generate_table(crc32c::POLYNOMIAL), crc32c::LOOKUP_TABLE);

Performance

Improvement are based on :