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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

//! 32-bit hashing algorithms
//!
//! # Why?
//!
//! Because 32-bit architectures are a thing (e.g. ARM Cortex-M) and you don't want your hashing
//! function to pull in a bunch of slow 64-bit compiler intrinsics (software implementations of
//! 64-bit operations).
//!
//! # Relationship to `core::hash`
//!
//! This crate extends [`core::hash`] with a 32-bit version of `Hasher`, which extends
//! `core::hash::Hasher`. It requires that the hasher only performs 32-bit operations when computing
//! the hash, and adds [`finish32`] to get the hasher's result as a `u32`. The standard `finish`
//! method should just zero-extend this result.
//!
//! Since it extends `core::hash::Hasher`, `Hasher` can be used with any type which implements the
//! standard `Hash` trait.
//!
//! This crate also adds a version of `BuildHasherDefault` with a const constructor, to work around
//! the `core` version's lack of one.
//!
//! [`core::hash`]: https://doc.rust-lang.org/std/hash/index.html
//! [`finish32`]: crate::Hasher::finish32
//!
//! # Hashers
//!
//! This crate provides implementations of the following 32-bit hashing algorithms:
//!
//! - [Fowler-Noll-Vo](struct.FnvHasher.html)
//! - [MurmurHash3](struct.Murmur3Hasher.html)
//!
//! # Generic code
//!
//! In generic code, the trait bound `H: core::hash::Hasher` accepts *both* 64-bit hashers like
//! `std::collections::hash_map::DefaultHasher`; and 32-bit hashers like the ones defined in this
//! crate (`hash32::FnvHasher` and `hash32::Murmur3Hasher`)
//!
//! The trait bound `H: hash32::Hasher` is *more* restrictive as it only accepts 32-bit hashers.
//!
//! The `BuildHasherDefault<H>` type implements the `core::hash::BuildHasher` trait so it can
//! construct both 32-bit and 64-bit hashers. To constrain the type to only produce 32-bit hasher
//! you can add the trait bound `H::Hasher: hash32::Hasher`
//!
//! # MSRV
//!
//! This crate is guaranteed to compile on latest stable Rust. It *might* compile on older
//! versions but that may change in any new patch release.

#![deny(missing_docs)]
#![deny(warnings)]
#![no_std]

extern crate byteorder;

use core::fmt;
use core::hash::BuildHasher;
use core::marker::PhantomData;

pub use fnv::Hasher as FnvHasher;
pub use murmur3::Hasher as Murmur3Hasher;

mod fnv;
mod murmur3;

/// A copy of [`core::hash::BuildHasherDefault`][0], but with a const constructor.
///
/// This will eventually be deprecated once the version in `core` becomes const-constructible
/// (presumably using `const Default`).
///
/// [0]: https://doc.rust-lang.org/core/hash/struct.BuildHasherDefault.html
pub struct BuildHasherDefault<H> {
    _marker: PhantomData<H>,
}

impl<H> Default for BuildHasherDefault<H> {
    fn default() -> Self {
        BuildHasherDefault {
            _marker: PhantomData,
        }
    }
}

impl<H> Clone for BuildHasherDefault<H> {
    fn clone(&self) -> Self {
        BuildHasherDefault::default()
    }
}

impl<H> PartialEq for BuildHasherDefault<H> {
    fn eq(&self, _other: &BuildHasherDefault<H>) -> bool {
        true
    }
}

impl<H> Eq for BuildHasherDefault<H> {}

impl<H> fmt::Debug for BuildHasherDefault<H> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.pad("BuildHasherDefault")
    }
}

impl<H> BuildHasherDefault<H> {
    /// `const` constructor
    pub const fn new() -> Self {
        BuildHasherDefault {
            _marker: PhantomData,
        }
    }
}

impl<H> BuildHasher for BuildHasherDefault<H>
where
    H: Default + core::hash::Hasher,
{
    type Hasher = H;

    fn build_hasher(&self) -> Self::Hasher {
        H::default()
    }
}

/// An extension of [core::hash::Hasher][0] for hashers which use 32 bits.
///
/// For hashers which implement this trait, the standard `finish` method should just return a
/// zero-extended version of the result of `finish32`.
///
/// [0]: https://doc.rust-lang.org/core/hash/trait.Hasher.html
///
/// # Contract
///
/// Implementers of this trait must *not* perform any 64-bit (or 128-bit) operation while computing
/// the hash.
pub trait Hasher: core::hash::Hasher {
    /// The equivalent of [`core::hash::Hasher.finish`][0] for 32-bit hashers.
    ///
    /// This returns the hash directly; `finish` zero-extends it to 64 bits for compatibility.
    ///
    /// [0]: https://doc.rust-lang.org/std/hash/trait.Hasher.html#tymethod.finish
    fn finish32(&self) -> u32;
}