diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 19:33:14 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 19:33:14 +0000 |
commit | 36d22d82aa202bb199967e9512281e9a53db42c9 (patch) | |
tree | 105e8c98ddea1c1e4784a60a5a6410fa416be2de /third_party/rust/murmurhash3 | |
parent | Initial commit. (diff) | |
download | firefox-esr-36d22d82aa202bb199967e9512281e9a53db42c9.tar.xz firefox-esr-36d22d82aa202bb199967e9512281e9a53db42c9.zip |
Adding upstream version 115.7.0esr.upstream/115.7.0esr
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'third_party/rust/murmurhash3')
-rw-r--r-- | third_party/rust/murmurhash3/.cargo-checksum.json | 1 | ||||
-rw-r--r-- | third_party/rust/murmurhash3/CHANGELOG.rst | 24 | ||||
-rw-r--r-- | third_party/rust/murmurhash3/Cargo.toml | 19 | ||||
-rw-r--r-- | third_party/rust/murmurhash3/LICENSE | 21 | ||||
-rw-r--r-- | third_party/rust/murmurhash3/README.rst | 50 | ||||
-rw-r--r-- | third_party/rust/murmurhash3/src/hasher.rs | 61 | ||||
-rw-r--r-- | third_party/rust/murmurhash3/src/lib.rs | 15 | ||||
-rw-r--r-- | third_party/rust/murmurhash3/src/mmh3_128.rs | 181 | ||||
-rw-r--r-- | third_party/rust/murmurhash3/src/mmh3_32.rs | 115 |
9 files changed, 487 insertions, 0 deletions
diff --git a/third_party/rust/murmurhash3/.cargo-checksum.json b/third_party/rust/murmurhash3/.cargo-checksum.json new file mode 100644 index 0000000000..ec3dc02821 --- /dev/null +++ b/third_party/rust/murmurhash3/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"CHANGELOG.rst":"11fdd5b156fc2ef5fb7ed980ba91c2a32bdabb79fa386926cbd70673ca6086a5","Cargo.toml":"f61656d89dfd6de3f420e021a55672979d02c4732154b3e91122582af084b8b5","LICENSE":"bb5492d70d4de524e3e29507fb9d87165a49acbc3a5b0e946aaed7e8cfbbd01b","README.rst":"9abdacc75d4886d6201d22b4406353beafb0f3012180109d47fca78e3b8ee5a2","src/hasher.rs":"0022eaa0525dc48b1d8e1dae3fdf5b86b8ae036cb6f87d68f3f5e3b31819f90f","src/lib.rs":"5fc49f47993193b09f170de2747679dc090ff7ec3a62858d62e8cb5213c67392","src/mmh3_128.rs":"0003106e26c34bd9b98155a19953bba946ae4c7899427b160dd74060afa96805","src/mmh3_32.rs":"67fef38bb5f6f4109b401d4b4aaa6bdd3fd4b83f89caeac6666b5f2173a8340e"},"package":"a2983372caf4480544083767bf2d27defafe32af49ab4df3a0b7fc90793a3664"}
\ No newline at end of file diff --git a/third_party/rust/murmurhash3/CHANGELOG.rst b/third_party/rust/murmurhash3/CHANGELOG.rst new file mode 100644 index 0000000000..ba660b5ba5 --- /dev/null +++ b/third_party/rust/murmurhash3/CHANGELOG.rst @@ -0,0 +1,24 @@ +Change Log +========== + +Unreleased_ +---------- + +0.0.4_ — 2014-04-04 +---------- + +* Enable ``HashState`` implementation + + +0.0.3_ — 2014-03-29 +------------------ + +* PR1_: Fixes to keep Rust Nightly compatibility, thanks polyfractal_ + + +.. _Unreleased: https://github.com/mhallin/murmurhash3-rs/compare/v0.0.4...HEAD +.. _0.0.4: https://github.com/mhallin/murmurhash3-rs/compare/v0.0.3...v0.0.4 +.. _0.0.3: https://github.com/mhallin/murmurhash3-rs/compare/v0.0.2...v0.0.3 + +.. _PR1: https://github.com/mhallin/murmurhash3-rs/pull/1 +.. _polyfractal: https://github.com/polyfractal diff --git a/third_party/rust/murmurhash3/Cargo.toml b/third_party/rust/murmurhash3/Cargo.toml new file mode 100644 index 0000000000..654fbbecba --- /dev/null +++ b/third_party/rust/murmurhash3/Cargo.toml @@ -0,0 +1,19 @@ +[package] + +name = "murmurhash3" +version = "0.0.5" +authors = ["mhallin <mhallin@gmail.com>"] +description = "MurmurHash3 implementation" +license = "MIT" +readme = "README.rst" +homepage = "https://github.com/mhallin/murmurhash3-rs" + +[lib] +name = "murmurhash3" +path = "src/lib.rs" + +[dev-dependencies] +rand = "*" + +[features] +nightly = [] diff --git a/third_party/rust/murmurhash3/LICENSE b/third_party/rust/murmurhash3/LICENSE new file mode 100644 index 0000000000..f54e8ea4cf --- /dev/null +++ b/third_party/rust/murmurhash3/LICENSE @@ -0,0 +1,21 @@ +The MIT License (MIT) + +Copyright (c) 2015 Magnus Hallin + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. diff --git a/third_party/rust/murmurhash3/README.rst b/third_party/rust/murmurhash3/README.rst new file mode 100644 index 0000000000..d52ebd26e7 --- /dev/null +++ b/third_party/rust/murmurhash3/README.rst @@ -0,0 +1,50 @@ +************** +MurmurHash3.rs +************** + +.. image:: https://travis-ci.org/mhallin/murmurhash3-rs.svg?branch=master + :target: https://travis-ci.org/mhallin/murmurhash3-rs + +A rust implementation of the MurmurHash3_. Both 32 bit and 128 bit versions are included. The 128 +bit version is implemented with 64 bit datatypes, making it most suitable for x86_64 or other 64 bit +architectures. + +---- + +Usage +===== + +In your ``Cargo.toml``: + +.. code:: toml + + [dependencies] + murmurhash3 = "*" + +Then you can start to use either ``murmurhash3_x86_32`` or ``murmurhash3_x64_128``: + +.. code:: rust + + use murmurhash3::murmurhash3_x64_128; + + fn hash_value() { + let data = "test data"; + let seed = 48221234; + + let hash = murmurhash3_x64_128(data.as_bytes(), seed); + } + +Unfortunately, there is a bug in the ``HashState`` library implementation which prevents +implementation of new ``Hasher`` implementations for use in for example ``HashMap``. Additionally, +only the 32 bit hasher can be used there since ``HashMap`` uses a 64 bit hash internally. + +Tests +===== + +.. code:: + + cargo test + +Runs all tests with optimization level 3 in order to weed out potential problems with the optimizer. + +.. _MurmurHash3: https://code.google.com/p/smhasher/wiki/MurmurHash3 diff --git a/third_party/rust/murmurhash3/src/hasher.rs b/third_party/rust/murmurhash3/src/hasher.rs new file mode 100644 index 0000000000..7b7f6c87ca --- /dev/null +++ b/third_party/rust/murmurhash3/src/hasher.rs @@ -0,0 +1,61 @@ +use std::hash::Hasher; +use std::collections::hash_state::HashState; + +use mmh3_32::murmurhash3_x86_32; + +pub struct Murmur3Hasher { + seed: u32, + bytes: Vec<u8>, +} + +#[derive(Clone, Copy)] +pub struct Murmur3HashState { + seed: u32, +} + +impl Murmur3HashState { + pub fn new() -> Murmur3HashState { + return Murmur3HashState { seed: 0 }; + } + + pub fn with_seed(seed: u32) -> Murmur3HashState { + return Murmur3HashState { seed: seed }; + } +} + + +impl Hasher for Murmur3Hasher { + fn finish(&self) -> u64 { + return murmurhash3_x86_32(&self.bytes, self.seed) as u64; + } + + fn write(&mut self, bytes: &[u8]) { + self.bytes.push_all(bytes); + } +} + +impl HashState for Murmur3HashState { + type Hasher = Murmur3Hasher; + + fn hasher(&self) -> Murmur3Hasher { + return Murmur3Hasher { seed: self.seed, bytes: vec![] }; + } +} + +#[cfg(test)] +mod test { + use super::Murmur3HashState; + use std::collections::hash_map::HashMap; + + #[test] + fn use_in_hashmap() { + let mut hashmap = HashMap::with_hash_state(Murmur3HashState::new()); + hashmap.insert("one", 1); + hashmap.insert("two", 2); + + assert!(hashmap.len() == 2); + + assert!(*hashmap.get("one").unwrap() == 1); + assert!(*hashmap.get("two").unwrap() == 2); + } +} diff --git a/third_party/rust/murmurhash3/src/lib.rs b/third_party/rust/murmurhash3/src/lib.rs new file mode 100644 index 0000000000..6436388699 --- /dev/null +++ b/third_party/rust/murmurhash3/src/lib.rs @@ -0,0 +1,15 @@ +#![cfg_attr(feature = "nightly", feature(hashmap_hasher))] +#![cfg_attr(feature = "nightly", feature(test))] +#![cfg_attr(feature = "nightly", feature(vec_push_all))] + +mod mmh3_128; +mod mmh3_32; + +#[cfg(feature="nightly")] +mod hasher; + +pub use mmh3_128::murmurhash3_x64_128; +pub use mmh3_32::murmurhash3_x86_32; + +#[cfg(feature="nightly")] +pub use hasher::Murmur3HashState; diff --git a/third_party/rust/murmurhash3/src/mmh3_128.rs b/third_party/rust/murmurhash3/src/mmh3_128.rs new file mode 100644 index 0000000000..b748f0fd93 --- /dev/null +++ b/third_party/rust/murmurhash3/src/mmh3_128.rs @@ -0,0 +1,181 @@ +use std::mem; + +fn fmix64(mut k: u64) -> u64 { + k ^= k >> 33; + k = k.wrapping_mul(0xff51afd7ed558ccdu64); + k ^= k >> 33; + k = k.wrapping_mul(0xc4ceb9fe1a85ec53u64); + k ^= k >> 33; + + return k; +} + +fn get_128_block(bytes: &[u8], index: usize) -> (u64, u64) { + let b64: &[u64] = unsafe { mem::transmute(bytes) }; + + return (b64[index], b64[index + 1]); +} + +pub fn murmurhash3_x64_128(bytes: &[u8], seed: u64) -> (u64, u64) { + let c1 = 0x87c37b91114253d5u64; + let c2 = 0x4cf5ad432745937fu64; + let read_size = 16; + let len = bytes.len() as u64; + let block_count = len / read_size; + + let (mut h1, mut h2) = (seed, seed); + + + for i in 0..block_count as usize { + let (mut k1, mut k2) = get_128_block(bytes, i * 2); + + k1 = k1.wrapping_mul(c1); + k1 = k1.rotate_left(31); + k1 = k1.wrapping_mul(c2); + h1 ^= k1; + + h1 = h1.rotate_left(27); + h1 = h1.wrapping_add(h2); + h1 = h1.wrapping_mul(5); + h1 = h1.wrapping_add(0x52dce729); + + k2 = k2.wrapping_mul(c2); + k2 = k2.rotate_left(33); + k2 = k2.wrapping_mul(c1); + h2 ^= k2; + + h2 = h2.rotate_left(31); + h2 = h2.wrapping_add(h1); + h2 = h2.wrapping_mul(5); + h2 = h2.wrapping_add(0x38495ab5); + } + + + let (mut k1, mut k2) = (0u64, 0u64); + + if len & 15 == 15 { k2 ^= (bytes[(block_count * read_size) as usize + 14] as u64) << 48; } + if len & 15 >= 14 { k2 ^= (bytes[(block_count * read_size) as usize + 13] as u64) << 40; } + if len & 15 >= 13 { k2 ^= (bytes[(block_count * read_size) as usize + 12] as u64) << 32; } + if len & 15 >= 12 { k2 ^= (bytes[(block_count * read_size) as usize + 11] as u64) << 24; } + if len & 15 >= 11 { k2 ^= (bytes[(block_count * read_size) as usize + 10] as u64) << 16; } + if len & 15 >= 10 { k2 ^= (bytes[(block_count * read_size) as usize + 9] as u64) << 8; } + if len & 15 >= 9 { k2 ^= bytes[(block_count * read_size) as usize + 8] as u64; + k2 = k2.wrapping_mul(c2); + k2 = k2.rotate_left(33); + k2 = k2.wrapping_mul(c1); + h2 ^= k2; + } + + if len & 15 >= 8 { k1 ^= (bytes[(block_count * read_size) as usize + 7] as u64) << 56; } + if len & 15 >= 7 { k1 ^= (bytes[(block_count * read_size) as usize + 6] as u64) << 48; } + if len & 15 >= 6 { k1 ^= (bytes[(block_count * read_size) as usize + 5] as u64) << 40; } + if len & 15 >= 5 { k1 ^= (bytes[(block_count * read_size) as usize + 4] as u64) << 32; } + if len & 15 >= 4 { k1 ^= (bytes[(block_count * read_size) as usize + 3] as u64) << 24; } + if len & 15 >= 3 { k1 ^= (bytes[(block_count * read_size) as usize + 2] as u64) << 16; } + if len & 15 >= 2 { k1 ^= (bytes[(block_count * read_size) as usize + 1] as u64) << 8; } + if len & 15 >= 1 { k1 ^= bytes[(block_count * read_size) as usize + 0] as u64; + k1 = k1.wrapping_mul(c1); + k1 = k1.rotate_left(31); + k1 = k1.wrapping_mul(c2); + h1 ^= k1; + } + + h1 ^= bytes.len() as u64; + h2 ^= bytes.len() as u64; + + h1 = h1.wrapping_add(h2); + h2 = h2.wrapping_add(h1); + + h1 = fmix64(h1); + h2 = fmix64(h2); + + h1 = h1.wrapping_add(h2); + h2 = h2.wrapping_add(h1); + + return (h1, h2); +} + +#[cfg(test)] +mod test { + use super::murmurhash3_x64_128; + + #[test] + fn test_empty_string() { + assert!(murmurhash3_x64_128("".as_bytes(), 0) == (0, 0)); + } + + #[test] + fn test_tail_lengths() { + assert!(murmurhash3_x64_128("1".as_bytes(), 0) + == (8213365047359667313, 10676604921780958775)); + assert!(murmurhash3_x64_128("12".as_bytes(), 0) + == (5355690773644049813, 9855895140584599837)); + assert!(murmurhash3_x64_128("123".as_bytes(), 0) + == (10978418110857903978, 4791445053355511657)); + assert!(murmurhash3_x64_128("1234".as_bytes(), 0) + == (619023178690193332, 3755592904005385637)); + assert!(murmurhash3_x64_128("12345".as_bytes(), 0) + == (2375712675693977547, 17382870096830835188)); + assert!(murmurhash3_x64_128("123456".as_bytes(), 0) + == (16435832985690558678, 5882968373513761278)); + assert!(murmurhash3_x64_128("1234567".as_bytes(), 0) + == (3232113351312417698, 4025181827808483669)); + assert!(murmurhash3_x64_128("12345678".as_bytes(), 0) + == (4272337174398058908, 10464973996478965079)); + assert!(murmurhash3_x64_128("123456789".as_bytes(), 0) + == (4360720697772133540, 11094893415607738629)); + assert!(murmurhash3_x64_128("123456789a".as_bytes(), 0) + == (12594836289594257748, 2662019112679848245)); + assert!(murmurhash3_x64_128("123456789ab".as_bytes(), 0) + == (6978636991469537545, 12243090730442643750)); + assert!(murmurhash3_x64_128("123456789abc".as_bytes(), 0) + == (211890993682310078, 16480638721813329343)); + assert!(murmurhash3_x64_128("123456789abcd".as_bytes(), 0) + == (12459781455342427559, 3193214493011213179)); + assert!(murmurhash3_x64_128("123456789abcde".as_bytes(), 0) + == (12538342858731408721, 9820739847336455216)); + assert!(murmurhash3_x64_128("123456789abcdef".as_bytes(), 0) + == (9165946068217512774, 2451472574052603025)); + assert!(murmurhash3_x64_128("123456789abcdef1".as_bytes(), 0) + == (9259082041050667785, 12459473952842597282)); + } + + #[test] + fn test_large_data() { + assert!(murmurhash3_x64_128("Lorem ipsum dolor sit amet, consectetur adipiscing elit. Etiam at consequat massa. Cras eleifend pellentesque ex, at dignissim libero maximus ut. Sed eget nulla felis".as_bytes(), 0) + == (9455322759164802692, 17863277201603478371)); + } + + #[cfg(feature="nightly")] + mod bench { + extern crate rand; + extern crate test; + + use std::iter::FromIterator; + use self::rand::Rng; + use self::test::{Bencher, black_box}; + + use super::super::murmurhash3_x64_128; + + fn run_bench(b: &mut Bencher, size: u64) { + let mut data: Vec<u8> = FromIterator::from_iter((0..size).map(|_| 0u8)); + rand::thread_rng().fill_bytes(&mut data); + + b.bytes = size; + b.iter(|| { + black_box(murmurhash3_x64_128(&data, 0)); + }); + } + + #[bench] + fn bench_random_256k(b: &mut Bencher) { + run_bench(b, 256 * 1024); + } + + #[bench] + fn bench_random_16b(b: &mut Bencher) { + run_bench(b, 16); + } + + } +} diff --git a/third_party/rust/murmurhash3/src/mmh3_32.rs b/third_party/rust/murmurhash3/src/mmh3_32.rs new file mode 100644 index 0000000000..49b7a59650 --- /dev/null +++ b/third_party/rust/murmurhash3/src/mmh3_32.rs @@ -0,0 +1,115 @@ +use std::mem; + +fn fmix32(mut h: u32) -> u32 { + h ^= h >> 16; + h = h.wrapping_mul(0x85ebca6b); + h ^= h >> 13; + h = h.wrapping_mul(0xc2b2ae35); + h ^= h >> 16; + + return h; +} + +fn get_32_block(bytes: &[u8], index: usize) -> u32 { + let b32: &[u32] = unsafe { mem::transmute(bytes) }; + + return b32[index]; +} + +pub fn murmurhash3_x86_32(bytes: &[u8], seed: u32) -> u32 { + let c1 = 0xcc9e2d51u32; + let c2 = 0x1b873593u32; + let read_size = 4; + let len = bytes.len() as u32; + let block_count = len / read_size; + + let mut h1 = seed; + + for i in 0..block_count as usize { + let mut k1 = get_32_block(bytes, i); + + k1 = k1.wrapping_mul(c1); + k1 = k1.rotate_left(15); + k1 = k1.wrapping_mul(c2); + + h1 ^= k1; + h1 = h1.rotate_left(13); + h1 = h1.wrapping_mul(5); + h1 = h1.wrapping_add(0xe6546b64) + } + let mut k1 = 0u32; + + if len & 3 == 3 { k1 ^= (bytes[(block_count * read_size) as usize + 2] as u32) << 16; } + if len & 3 >= 2 { k1 ^= (bytes[(block_count * read_size) as usize + 1] as u32) << 8; } + if len & 3 >= 1 { k1 ^= bytes[(block_count * read_size) as usize + 0] as u32; + k1 = k1.wrapping_mul(c1); + k1 = k1.rotate_left(15); + k1 = k1.wrapping_mul(c2); + h1 ^= k1; + } + + h1 ^= bytes.len() as u32; + h1 = fmix32(h1); + + return h1; +} + +#[cfg(test)] +mod test { + use super::murmurhash3_x86_32; + + #[test] + fn test_empty_string() { + assert!(murmurhash3_x86_32("".as_bytes(), 0) == 0); + } + + #[test] + fn test_tail_lengths() { + assert!(murmurhash3_x86_32("1".as_bytes(), 0) + == 2484513939); + assert!(murmurhash3_x86_32("12".as_bytes(), 0) + == 4191350549); + assert!(murmurhash3_x86_32("123".as_bytes(), 0) + == 2662625771); + assert!(murmurhash3_x86_32("1234".as_bytes(), 0) + == 1914461635); + } + + #[test] + fn test_large_data() { + assert!(murmurhash3_x86_32("Lorem ipsum dolor sit amet, consectetur adipiscing elit. Etiam at consequat massa. Cras eleifend pellentesque ex, at dignissim libero maximus ut. Sed eget nulla felis".as_bytes(), 0) + == 1004899618); + } + + #[cfg(feature="nightly")] + mod bench { + extern crate rand; + extern crate test; + + use std::iter::FromIterator; + use self::rand::Rng; + use self::test::{Bencher, black_box}; + + use super::super::murmurhash3_x86_32; + + fn run_bench(b: &mut Bencher, size: u64) { + let mut data: Vec<u8> = FromIterator::from_iter((0..size).map(|_| 0u8)); + rand::thread_rng().fill_bytes(&mut data); + + b.bytes = size; + b.iter(|| { + black_box(murmurhash3_x86_32(&data, 0)); + }); + } + + #[bench] + fn bench_random_256k(b: &mut Bencher) { + run_bench(b, 256 * 1024); + } + + #[bench] + fn bench_random_16b(b: &mut Bencher) { + run_bench(b, 16); + } + } +} |