hash32/
lib.rs

Help
1//! 32-bit hashing machinery
2//!
3//! # Why?
4//!
5//! Because 32-bit architectures are a thing (e.g. ARM Cortex-M) and you don't want your hashing
6//! function to pull in a bunch of slow 64-bit compiler intrinsics (software implementations of
7//! 64-bit operations).
8//!
9//! # Relationship to `core::hash`
10//!
11//! This crate exposes the same interfaces you'll find in [`core::hash`]: `Hash`, `Hasher`,
12//! `BuildHasher` and `BuildHasherDefault`. The main difference is that `hash32::Hasher::finish`
13//! returns a `u32` instead of `u64`, and the contract of `hash32::Hasher` forbids the implementer
14//! from performing 64-bit (or 128-bit) operations while computing the hash.
15//!
16//! [`core::hash`]: https://doc.rust-lang.org/std/hash/index.html
17//!
18//! # `#[derive(Hash32)]`
19//!
20//! The easiest way to implement `hash32::Hash` for a `struct` is to use the `#[derive(Hash32)]`.
21//!
22//! Note that you need to *explicitly* depend on both `hash32` *and* `hash32_derive`; both crates
23//! must appear in your `Cargo.toml`.
24//!
25//! ``` ignore
26//! use hash32_derive::Hash32;
27//!
28//! #[derive(Hash32)]
29//! struct Ipv4Addr([u8; 4]);
30//!
31//! # fn main() {}
32//!
33//! ```
34//! # Hashers
35//!
36//! This crate provides implementations of the following 32-bit hashing algorithms:
37//!
38//! - [Fowler-Noll-Vo](struct.FnvHasher.html)
39//! - [MurmurHash3](struct.Murmur3Hasher.html)
40//!
41//! # MSRV
42//!
43//! This crate is guaranteed to compile on latest stable Rust. It *might* compile on older
44//! versions but that may change in any new patch release.
45//!
46//! # Future
47//!
48//! In the future we'd like to deprecate this crate in favor of making `core::hash::Hasher` generic
49//! over the size of the computed hash. Below is shown the planned change (but it doesn't work due
50//! to limitations in the `associated_type_defaults` feature):
51//!
52//! ``` ignore
53//! #![feature(associated_type_defaults)]
54//!
55//! trait Hasher {
56//!     type Hash = u64; // default type for backwards compatibility
57//!
58//!     fn finish(&self) -> Self::Hash; // changed
59//!     fn write(&mut self, bytes: &[u8]);
60//! }
61//! ```
62//!
63//! With this change a single `#[derive(Hash)]` would enough to make a type hashable with 32-bit and
64//! 64-bit hashers.
65
66#![deny(missing_docs)]
67#![deny(warnings)]
68#![no_std]
69
70extern crate byteorder;
71
72use core::marker::PhantomData;
73use core::{mem, slice, fmt};
74
75pub use fnv::Hasher as FnvHasher;
76pub use murmur3::Hasher as Murmur3Hasher;
77
78mod fnv;
79mod murmur3;
80
81/// See [`core::hash::BuildHasherDefault`][0] for details
82///
83/// [0]: https://doc.rust-lang.org/core/hash/struct.BuildHasherDefault.html
84pub struct BuildHasherDefault<H>
85{
86    _marker: PhantomData<H>,
87}
88
89impl<H> Default for BuildHasherDefault<H>
90where
91    H: Default + Hasher,
92{
93    fn default() -> Self {
94        BuildHasherDefault {
95            _marker: PhantomData,
96        }
97    }
98}
99
100impl<H> Clone for BuildHasherDefault<H>
101where
102    H: Default + Hasher,
103{
104    fn clone(&self) -> Self {
105        BuildHasherDefault::default()
106    }
107}
108
109impl<H> PartialEq for BuildHasherDefault<H>
110where
111    H: Default + Hasher,
112{
113    fn eq(&self, _other: &BuildHasherDefault<H>) -> bool {
114        true
115    }
116}
117
118impl<H: Default + Hasher> Eq for BuildHasherDefault<H> {}
119
120impl<H: Default + Hasher> fmt::Debug for BuildHasherDefault<H> {
121    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
122        f.pad("BuildHasherDefault")
123    }
124}
125
126impl<H> BuildHasherDefault<H>
127{
128    /// `const` constructor
129    pub const fn new() -> Self {
130        BuildHasherDefault {
131            _marker: PhantomData,
132        }
133    }
134}
135
136impl<H> BuildHasher for BuildHasherDefault<H>
137where
138    H: Default + Hasher,
139{
140    type Hasher = H;
141
142    fn build_hasher(&self) -> Self::Hasher {
143        H::default()
144    }
145}
146
147/// See [`core::hash::BuildHasher`][0] for details
148///
149/// [0]: https://doc.rust-lang.org/core/hash/trait.BuildHasher.html
150pub trait BuildHasher {
151    /// See [`core::hash::BuildHasher::Hasher`][0]
152    ///
153    /// [0]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html#associatedtype.Hasher
154    type Hasher: Hasher;
155
156    /// See [`core::hash::BuildHasher.build_hasher`][0]
157    ///
158    /// [0]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html#tymethod.build_hasher
159    fn build_hasher(&self) -> Self::Hasher;
160}
161
162/// See [`core::hash::Hasher`][0] for details
163///
164/// [0]: https://doc.rust-lang.org/core/hash/trait.Hasher.html
165///
166/// # Contract
167///
168/// Implementers of this trait must *not* perform any 64-bit (or 128-bit) operation while computing
169/// the hash.
170pub trait Hasher {
171    /// See [`core::hash::Hasher.finish`][0]
172    ///
173    /// [0]: https://doc.rust-lang.org/std/hash/trait.Hasher.html#tymethod.finish
174    fn finish(&self) -> u32;
175
176    /// See [`core::hash::Hasher.write`][0]
177    ///
178    /// [0]: https://doc.rust-lang.org/std/hash/trait.Hasher.html#tymethod.write
179    fn write(&mut self, bytes: &[u8]);
180}
181
182/// See [`core::hash::Hash`][0] for details
183///
184/// [0]: https://doc.rust-lang.org/core/hash/trait.Hash.html
185pub trait Hash {
186    /// Feeds this value into the given `Hasher`.
187    fn hash<H>(&self, state: &mut H)
188    where
189        H: Hasher;
190
191    /// Feeds a slice of this type into the given `Hasher`.
192    fn hash_slice<H>(data: &[Self], state: &mut H)
193    where
194        H: Hasher,
195        Self: Sized,
196    {
197        for piece in data {
198            piece.hash(state);
199        }
200    }
201}
202
203macro_rules! int {
204    ($ty:ident) => {
205        impl Hash for $ty {
206            fn hash<H>(&self, state: &mut H)
207            where
208                H: Hasher,
209            {
210                unsafe { state.write(&mem::transmute::<$ty, [u8; mem::size_of::<$ty>()]>(*self)) }
211            }
212
213            fn hash_slice<H>(data: &[Self], state: &mut H)
214            where
215                H: Hasher,
216            {
217                let newlen = data.len() * mem::size_of::<$ty>();
218                let ptr = data.as_ptr() as *const u8;
219                unsafe { state.write(slice::from_raw_parts(ptr, newlen)) }
220            }
221        }
222    };
223}
224
225int!(i16);
226int!(i32);
227int!(i64);
228int!(i8);
229int!(isize);
230int!(u16);
231int!(u32);
232int!(u64);
233int!(u8);
234int!(usize);
235
236impl Hash for bool {
237    fn hash<H>(&self, state: &mut H)
238    where
239        H: Hasher,
240    {
241        (*self as u8).hash(state)
242    }
243}
244
245impl Hash for char {
246    fn hash<H>(&self, state: &mut H)
247    where
248        H: Hasher,
249    {
250        (*self as u32).hash(state)
251    }
252}
253
254impl Hash for str {
255    fn hash<H>(&self, state: &mut H)
256    where
257        H: Hasher,
258    {
259        state.write(self.as_bytes());
260        state.write(&[0xff]);
261    }
262}
263
264impl<T> Hash for [T]
265where
266    T: Hash,
267{
268    fn hash<H>(&self, state: &mut H)
269    where
270        H: Hasher,
271    {
272        self.len().hash(state);
273        T::hash_slice(self, state);
274    }
275}
276
277macro_rules! array {
278    ($($n:expr),+) => {
279        $(
280            impl<T> Hash for [T; $n]
281                where
282                T: Hash,
283            {
284                fn hash<H>(&self, state: &mut H)
285                    where
286                    H: Hasher,
287                {
288                    Hash::hash(&self[..], state)
289                }
290            }
291        )+
292    };
293}
294
295array!(
296    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
297    26, 27, 28, 29, 30, 31, 32
298);
299
300impl<'a, T: ?Sized + Hash> Hash for &'a T {
301    fn hash<H: Hasher>(&self, state: &mut H) {
302        (**self).hash(state);
303    }
304}
305
306impl<'a, T: ?Sized + Hash> Hash for &'a mut T {
307    fn hash<H: Hasher>(&self, state: &mut H) {
308        (**self).hash(state);
309    }
310}
311
312impl Hash for () {
313    fn hash<H: Hasher>(&self, _state: &mut H) {}
314}
315
316macro_rules! tuple {
317    ( $($name:ident)+) => (
318        impl<$($name: Hash),*> Hash for ($($name,)*)
319            where
320            last_type!($($name,)+): ?Sized
321        {
322            #[allow(non_snake_case)]
323            fn hash<S: Hasher>(&self, state: &mut S) {
324                let ($(ref $name,)*) = *self;
325                $($name.hash(state);)*
326            }
327        }
328    );
329}
330
331macro_rules! last_type {
332    ($a:ident,) => { $a };
333    ($a:ident, $($rest_a:ident,)+) => { last_type!($($rest_a,)+) };
334}
335
336tuple! { A }
337tuple! { A B }
338tuple! { A B C }
339tuple! { A B C D }
340tuple! { A B C D E }
341tuple! { A B C D E F }
342tuple! { A B C D E F G }
343tuple! { A B C D E F G H }
344tuple! { A B C D E F G H I }
345tuple! { A B C D E F G H I J }
346tuple! { A B C D E F G H I J K }
347tuple! { A B C D E F G H I J K L }
348
349#[cfg(test)]
350mod test {
351    use super::{FnvHasher, Hash, Hasher};
352    #[test]
353    fn hashes_tuples() {
354        let mut h = FnvHasher::default();
355        ().hash(&mut h);
356        (1_usize,).hash(&mut h);
357        (1_u8, 2_i8).hash(&mut h);
358        (1_u16, 2_i16, 3_u32).hash(&mut h);
359        (1_i32, 2_u64, 3_i64, true).hash(&mut h);
360        (1_isize, 'a', "abc", [1u32, 2, 3, 4], false).hash(&mut h);
361        h.finish();
362    }
363}
hash32/lib.rs

hash32/
lib.rs
