#hash-string #hasher #hash-map #gamedev

no-std slice-by-8

HUD Software's Rust improved implementation of the Intel Slice-By-8 algorithm

4 stable releases

1.0.6 Feb 24, 2023
1.0.5 Feb 23, 2023
1.0.4 Sep 20, 2022
1.0.2 Jun 24, 2022
0.1.0 May 5, 2022

#358 in Algorithms

MIT license

78KB
961 lines

Slice-by-8

Crates.io License

WARNING: This crate is no more maintained, use hud-slice-by-8 instead

--- Rust improved implementation of the [Slice-by-8](http://slicing-by-8.sourceforge.net/) 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 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 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 slice_by_8::slice_by_8;

let my_lookup_table: [[u32; 256]; 8] = slice_by_8::generate_table(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 slice_by_8::generate_table;
use 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 :

No runtime deps

~170KB