Skip to main content

crc32fast/
lib.rs

1//! Fast, SIMD-accelerated CRC32 (IEEE) checksum computation.
2//!
3//! ## Usage
4//!
5//! ### Simple usage
6//!
7//! For simple use-cases, you can call the [`hash()`] convenience function to
8//! directly compute the CRC32 checksum for a given byte slice:
9//!
10//! ```rust
11//! let checksum = crc32fast::hash(b"foo bar baz");
12//! ```
13//!
14//! ### Advanced usage
15//!
16//! For use-cases that require more flexibility or performance, for example when
17//! processing large amounts of data, you can create and manipulate a [`Hasher`]:
18//!
19//! ```rust
20//! use crc32fast::Hasher;
21//!
22//! let mut hasher = Hasher::new();
23//! hasher.update(b"foo bar baz");
24//! let checksum = hasher.finalize();
25//! ```
26//!
27//! ## Performance
28//!
29//! This crate contains multiple CRC32 implementations:
30//!
31//! - A fast baseline implementation which processes up to 16 bytes per iteration
32//! - An optimized implementation for modern `x86` using `sse` and `pclmulqdq` instructions
33//! - Wider `x86` implementations using `vpclmulqdq` on 256-bit (`avx2`) and 512-bit (`avx512f`)
34//!   registers (available when built with Rust 1.89 or newer)
35//! - An optimized implementation for `aarch64` using `crc32` instructions
36//!
37//! Calling the [`Hasher::new`] constructor at runtime will perform a feature detection to select the most
38//! optimal implementation for the current CPU feature set.
39
40#![cfg_attr(not(feature = "std"), no_std)]
41#![deny(missing_docs)]
42#![deny(unsafe_code)]
43use core::fmt;
44use core::hash;
45
46mod baseline;
47mod combine;
48mod specialized;
49mod table;
50
51/// Computes the CRC32 hash of a byte slice.
52///
53/// Check out [`Hasher`] for more advanced use-cases.
54#[inline]
55pub fn hash(buf: &[u8]) -> u32 {
56    let mut h = Hasher::new();
57    h.update(buf);
58    h.finalize()
59}
60
61#[derive(Clone)]
62/// Represents an in-progress CRC32 computation.
63pub struct Hasher {
64    amount: u64,
65    state: u32,
66    spec: Option<specialized::State>,
67}
68
69const DEFAULT_INIT_STATE: u32 = 0;
70
71impl Hasher {
72    /// Create a new `Hasher`.
73    ///
74    /// This will perform a CPU feature detection at runtime to select the most
75    /// optimal implementation for the current processor architecture.
76    #[inline]
77    pub fn new() -> Self {
78        Self::new_with_initial(DEFAULT_INIT_STATE)
79    }
80
81    /// Create a new `Hasher` with an initial CRC32 state.
82    ///
83    /// This works just like `Hasher::new`, except that it allows for an initial
84    /// CRC32 state to be passed in.
85    #[inline]
86    pub fn new_with_initial(init: u32) -> Self {
87        Self::new_with_initial_len(init, 0)
88    }
89
90    /// Create a new `Hasher` with an initial CRC32 state.
91    ///
92    /// As `new_with_initial`, but also accepts a length (in bytes). The
93    /// resulting object can then be used with `combine` to compute `crc(a ||
94    /// b)` from `crc(a)`, `crc(b)`, and `len(b)`.
95    #[inline]
96    pub fn new_with_initial_len(init: u32, amount: u64) -> Self {
97        Self::internal_new_specialized(init, amount)
98            .unwrap_or_else(|| Self::internal_new_baseline(init, amount))
99    }
100
101    #[doc(hidden)]
102    // Internal-only API. Don't use.
103    #[inline]
104    pub fn internal_new_baseline(init: u32, amount: u64) -> Self {
105        Hasher {
106            amount,
107            state: init,
108            spec: None,
109        }
110    }
111
112    #[doc(hidden)]
113    // Internal-only API. Don't use.
114    #[inline]
115    pub fn internal_new_specialized(init: u32, amount: u64) -> Option<Self> {
116        Some(Hasher {
117            amount,
118            state: init,
119            spec: Some(specialized::State::new()?),
120        })
121    }
122
123    /// Process the given byte slice and update the hash state.
124    #[inline]
125    pub fn update(&mut self, buf: &[u8]) {
126        self.amount += buf.len() as u64;
127        self.state = match &self.spec {
128            None => baseline::update_fast_16(self.state, buf),
129            Some(spec) => spec.update(self.state, buf),
130        };
131    }
132
133    /// Returns the total number of bytes represented by this hash state.
134    ///
135    /// This includes the length passed to [`Hasher::new_with_initial_len`] and
136    /// the lengths of any hash states added with [`Hasher::combine`].
137    /// [`Hasher::reset`] sets the length back to zero.
138    ///
139    /// A state created with [`Hasher::new_with_initial`] starts with a length
140    /// of zero because the length of the initial state is not known.
141    ///
142    /// ```
143    /// use crc32fast::Hasher;
144    ///
145    /// let mut hasher = Hasher::new();
146    /// hasher.update(b"hello");
147    /// hasher.update(b" world");
148    /// assert_eq!(hasher.total_len(), 11);
149    /// ```
150    #[inline]
151    pub fn total_len(&self) -> u64 {
152        self.amount
153    }
154
155    /// Finalize the hash state and return the computed CRC32 value.
156    #[inline]
157    pub fn finalize(self) -> u32 {
158        self.state
159    }
160
161    /// Reset the hash state.
162    #[inline]
163    pub fn reset(&mut self) {
164        self.state = 0;
165        self.amount = 0;
166    }
167
168    /// Combine the hash state with the hash state for the subsequent block of bytes.
169    pub fn combine(&mut self, other: &Self) {
170        self.amount += other.amount;
171        self.state = combine::combine(self.state, other.state, other.amount);
172    }
173}
174
175impl fmt::Debug for Hasher {
176    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
177        f.debug_struct("crc32fast::Hasher").finish()
178    }
179}
180
181impl Default for Hasher {
182    fn default() -> Self {
183        Self::new()
184    }
185}
186
187impl hash::Hasher for Hasher {
188    fn write(&mut self, bytes: &[u8]) {
189        self.update(bytes)
190    }
191
192    fn finish(&self) -> u64 {
193        u64::from(self.clone().finalize())
194    }
195}
196
197#[cfg(test)]
198mod test {
199    use super::Hasher;
200
201    #[test]
202    fn total_len_tracks_resumed_and_combined_blocks() {
203        let prefix = b"hello";
204        let suffix = b" world";
205        let mut hasher = Hasher::new_with_initial_len(super::hash(prefix), prefix.len() as u64);
206        assert_eq!(hasher.total_len(), 5);
207        hasher.update(b" ");
208        assert_eq!(hasher.total_len(), 6);
209
210        let mut remaining = Hasher::new();
211        remaining.update(&suffix[1..]);
212        hasher.combine(&remaining);
213        assert_eq!(hasher.total_len(), 11);
214        assert_eq!(hasher.clone().finalize(), super::hash(b"hello world"));
215        assert_eq!(remaining.total_len(), 5);
216
217        hasher.reset();
218        assert_eq!(hasher.total_len(), 0);
219        hasher.update(b"again");
220        assert_eq!(hasher.total_len(), 5);
221        assert_eq!(hasher.finalize(), super::hash(b"again"));
222    }
223
224    #[test]
225    fn total_len_for_empty_and_unknown_initial_length() {
226        let mut hasher = Hasher::new();
227        assert_eq!(hasher.total_len(), 0);
228        hasher.update(b"");
229        hasher.combine(&Hasher::new());
230        assert_eq!(hasher.total_len(), 0);
231        assert_eq!(
232            Hasher::new_with_initial(super::hash(b"prefix")).total_len(),
233            0
234        );
235        assert_eq!(
236            Hasher::new_with_initial_len(0, u64::MAX).total_len(),
237            u64::MAX
238        );
239    }
240
241    quickcheck::quickcheck! {
242        fn combine(bytes_1: Vec<u8>, bytes_2: Vec<u8>) -> bool {
243            let mut hash_a = Hasher::new();
244            hash_a.update(&bytes_1);
245            hash_a.update(&bytes_2);
246            let mut hash_b = Hasher::new();
247            hash_b.update(&bytes_2);
248            let mut hash_c = Hasher::new();
249            hash_c.update(&bytes_1);
250            hash_c.combine(&hash_b);
251
252            hash_a.finalize() == hash_c.finalize()
253        }
254
255        fn combine_from_len(bytes_1: Vec<u8>, bytes_2: Vec<u8>) -> bool {
256            let mut hash_a = Hasher::new();
257            hash_a.update(&bytes_1);
258
259            let mut hash_b = Hasher::new();
260            hash_b.update(&bytes_2);
261
262            let mut hash_ab = Hasher::new();
263            hash_ab.update(&bytes_1);
264            hash_ab.update(&bytes_2);
265            let ab = hash_ab.finalize();
266
267            hash_a.combine(&hash_b);
268            hash_a.finalize() == ab
269        }
270    }
271}