diff options
author | Martin Geisler <mgeisler@google.com> | 2024-04-09 20:04:48 +0200 |
---|---|---|
committer | Martin Geisler <mgeisler@google.com> | 2024-04-25 13:51:57 +0000 |
commit | 23ed1286d3d3dc52ef2284d30b0d6e5b0da44302 (patch) | |
tree | 41c6d7470f7af84f697ec28ca9e01c37a3bd1287 | |
parent | 685c480890ae92acc7d7253a1581325b59e815b0 (diff) | |
download | siphasher-upstream.tar.gz |
Import 'siphasher' crateupstream
Request Document: go/android-rust-importing-crates
For CL Reviewers: go/android3p#cl-review
For Build Team: go/ab-third-party-imports
Bug: http://b/330683646
Test: m libsiphasher
Change-Id: I5776c5876da2d07b4a218e541182ff60307c2414
-rw-r--r-- | .cargo_vcs_info.json | 6 | ||||
-rw-r--r-- | .github/dependabot.yml | 8 | ||||
-rw-r--r-- | .gitignore | 4 | ||||
-rw-r--r-- | Android.bp | 42 | ||||
-rw-r--r-- | COPYING | 7 | ||||
-rw-r--r-- | Cargo.toml | 54 | ||||
-rw-r--r-- | LICENSE | 201 | ||||
-rw-r--r-- | METADATA | 20 | ||||
-rw-r--r-- | MODULE_LICENSE_APACHE2 | 0 | ||||
-rw-r--r-- | OWNERS | 2 | ||||
-rw-r--r-- | README.md | 93 | ||||
-rw-r--r-- | cargo_embargo.json | 4 | ||||
-rw-r--r-- | src/lib.rs | 30 | ||||
-rw-r--r-- | src/sip.rs | 594 | ||||
-rw-r--r-- | src/sip128.rs | 696 | ||||
-rw-r--r-- | src/tests.rs | 332 | ||||
-rw-r--r-- | src/tests128.rs | 134 |
17 files changed, 2227 insertions, 0 deletions
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json new file mode 100644 index 0000000..4da2d70 --- /dev/null +++ b/.cargo_vcs_info.json @@ -0,0 +1,6 @@ +{ + "git": { + "sha1": "f57236be563e74ed9d4a3df93b6d2da15660bd18" + }, + "path_in_vcs": "" +}
\ No newline at end of file diff --git a/.github/dependabot.yml b/.github/dependabot.yml new file mode 100644 index 0000000..c11601f --- /dev/null +++ b/.github/dependabot.yml @@ -0,0 +1,8 @@ +version: 2 +updates: +- package-ecosystem: cargo + directory: "/" + schedule: + interval: daily + time: "04:00" + open-pull-requests-limit: 10 diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..6f973fb --- /dev/null +++ b/.gitignore @@ -0,0 +1,4 @@ +/target/ +Cargo.lock +.vscode +*~ diff --git a/Android.bp b/Android.bp new file mode 100644 index 0000000..76c2d1b --- /dev/null +++ b/Android.bp @@ -0,0 +1,42 @@ +// This file is generated by cargo_embargo. +// Do not modify this file as changes will be overridden on upgrade. + +// TODO: Add license. +rust_library { + name: "libsiphasher", + host_supported: true, + crate_name: "siphasher", + cargo_env_compat: true, + cargo_pkg_version: "1.0.1", + srcs: ["src/lib.rs"], + edition: "2018", + features: [ + "default", + "std", + ], + apex_available: [ + "//apex_available:platform", + "//apex_available:anyapex", + ], + product_available: true, + vendor_available: true, +} + +rust_test { + name: "siphasher_test_src_lib", + host_supported: true, + crate_name: "siphasher", + cargo_env_compat: true, + cargo_pkg_version: "1.0.1", + srcs: ["src/lib.rs"], + test_suites: ["general-tests"], + auto_gen_config: true, + test_options: { + unit_test: true, + }, + edition: "2018", + features: [ + "default", + "std", + ], +} @@ -0,0 +1,7 @@ +Copyright 2012-2016 The Rust Project Developers. +Copyright 2016-2024 Frank Denis. + +Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +<LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +option. diff --git a/Cargo.toml b/Cargo.toml new file mode 100644 index 0000000..336ee1e --- /dev/null +++ b/Cargo.toml @@ -0,0 +1,54 @@ +# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO +# +# When uploading crates to the registry Cargo will automatically +# "normalize" Cargo.toml files for maximal compatibility +# with all versions of Cargo and also rewrite `path` dependencies +# to registry (e.g., crates.io) dependencies. +# +# If you are reading this file be aware that the original Cargo.toml +# will likely look very different (and much more reasonable). +# See Cargo.toml.orig for the original contents. + +[package] +edition = "2018" +name = "siphasher" +version = "1.0.1" +authors = ["Frank Denis <github@pureftpd.org>"] +description = "SipHash-2-4, SipHash-1-3 and 128-bit variants in pure Rust" +homepage = "https://docs.rs/siphasher" +documentation = "https://docs.rs/siphasher" +readme = "README.md" +keywords = [ + "crypto", + "hash", + "siphash", +] +categories = [ + "algorithms", + "cryptography", +] +license = "MIT/Apache-2.0" +repository = "https://github.com/jedisct1/rust-siphash" + +[profile.release] +opt-level = 3 +lto = true +panic = "abort" + +[dependencies.serde] +version = "1.0" +features = ["derive"] +optional = true + +[dependencies.serde_json] +version = "1.0" +optional = true + +[features] +default = ["std"] +serde_no_std = ["serde/alloc"] +serde_std = [ + "std", + "serde/std", +] +std = [] @@ -0,0 +1,201 @@ + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + +TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + +1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + +2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + +3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + +4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + +5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + +6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + +7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + +8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + +9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + +END OF TERMS AND CONDITIONS + +APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + +Copyright [yyyy] [name of copyright owner] + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. diff --git a/METADATA b/METADATA new file mode 100644 index 0000000..c379548 --- /dev/null +++ b/METADATA @@ -0,0 +1,20 @@ +name: "siphasher" +description: "SipHash-2-4, SipHash-1-3 and 128-bit variants in pure Rust" +third_party { + identifier { + type: "crates.io" + value: "siphasher" + } + identifier { + type: "Archive" + value: "https://static.crates.io/crates/siphasher/siphasher-1.0.1.crate" + primary_source: true + } + version: "1.0.1" + license_type: NOTICE + last_upgrade_date { + year: 2024 + month: 3 + day: 21 + } +} diff --git a/MODULE_LICENSE_APACHE2 b/MODULE_LICENSE_APACHE2 new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/MODULE_LICENSE_APACHE2 @@ -0,0 +1,2 @@ +# Bug component: 688011 +include platform/prebuilts/rust:main:/OWNERS diff --git a/README.md b/README.md new file mode 100644 index 0000000..e485ab4 --- /dev/null +++ b/README.md @@ -0,0 +1,93 @@ +SipHash implementation for Rust +=============================== + +This crates implements SipHash-2-4 and SipHash-1-3 in Rust. + +It is based on the original implementation from rust-core and exposes the +same API. + +It also implements SipHash variants returning 128-bit tags. + +The `sip` module implements the standard 64-bit mode, whereas the `sip128` +module implements the 128-bit mode. + +Usage +----- + +In `Cargo.toml`: + +```toml +[dependencies] +siphasher = "1" +``` + +If you want [serde](https://github.com/serde-rs/serde) support, include the feature like this: + +```toml +[dependencies] +siphasher = { version = "1", features = ["serde"] } +``` + +64-bit mode: + +```rust +use siphasher::sip::{SipHasher, SipHasher13, SipHasher24}; + +// one-shot: + +let array: &[u8] = &[1, 2, 3]; +let key: &[u8; 16] = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]; +let hasher = SipHasher13::new_with_key(key); +let h = hasher.hash(array); + +// incremental: + +use core::hash::Hasher; + +let array1: &[u8] = &[1, 2, 3]; +let array2: &[u8] = &[4, 5, 6]; +let key: &[u8; 16] = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]; +let mut hasher = SipHasher13::new_with_key(key); +hasher.write(array1); +hasher.write(array2); +let h = hasher.finish(); +``` + +128-bit mode: + +```rust +use siphasher::sip128::{Hasher128, SipHasher, SipHasher13, SipHasher24}; + +// one-shot: + +let array: &[u8] = &[1, 2, 3]; +let key: &[u8; 16] = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]; +let hasher = SipHasher13::new_with_key(key); +let h = hasher.hash(array).as_bytes(); + +// incremental: + +use core::hash::Hasher; + +let array1: &[u8] = &[1, 2, 3]; +let array2: &[u8] = &[4, 5, 6]; +let key: &[u8; 16] = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]; +let mut hasher = SipHasher13::new_with_key(key); +hasher.write(array1); +hasher.write(array2); +let h = hasher.finish128().as_bytes(); +``` + +[API documentation](https://docs.rs/siphasher/) +----------------------------------------------- + +Note +---- + +Due to a confusing and not well documented API, methods from the `Hasher` trait of the standard library (`std::hash::Hasher`, `core::hash::Hasher`) produce non-portable results. + +This is not specific to SipHash, and affects all hash functions. + +The only safe methods in that trait are `write()` and `finish()`. + +It is thus recommended to use SipHash (and all other hash functions, actually) as documented above. diff --git a/cargo_embargo.json b/cargo_embargo.json new file mode 100644 index 0000000..c8842d1 --- /dev/null +++ b/cargo_embargo.json @@ -0,0 +1,4 @@ +{ + "run_cargo": false, + "tests": true +} diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..2a89800 --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,30 @@ +#![doc = include_str!("../README.md")] + +#![cfg_attr(not(test), no_std)] +#![allow(clippy::unreadable_literal)] +#![allow(clippy::cast_lossless)] +#![allow(clippy::many_single_char_names)] + +pub mod sip; +pub mod sip128; + +#[cfg(test)] +mod tests; + +#[cfg(test)] +mod tests128; + +#[cfg(any(feature = "serde", feature = "serde_std", feature = "serde_no_std"))] +pub mod reexports { + pub use serde; + #[cfg(feature = "serde_json")] + pub use serde_json; +} + +pub mod prelude { + pub use core::hash::Hasher as _; + + pub use sip128::Hasher128 as _; + + pub use crate::{sip, sip128}; +} diff --git a/src/sip.rs b/src/sip.rs new file mode 100644 index 0000000..4ed90ed --- /dev/null +++ b/src/sip.rs @@ -0,0 +1,594 @@ +// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! An implementation of SipHash. + +use core::cmp; +use core::hash; +use core::hash::Hasher as _; +use core::marker::PhantomData; +use core::mem; +use core::ptr; +use core::u64; + +/// An implementation of SipHash 1-3. +/// +/// See: <https://www.aumasson.jp/siphash/siphash.pdf> +#[derive(Debug, Clone, Copy, Default)] +#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))] +pub struct SipHasher13 { + hasher: Hasher<Sip13Rounds>, +} + +/// An implementation of SipHash 2-4. +/// +/// See: <https://www.aumasson.jp/siphash/siphash.pdf> +#[derive(Debug, Clone, Copy, Default)] +#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))] +pub struct SipHasher24 { + hasher: Hasher<Sip24Rounds>, +} + +/// An implementation of SipHash 2-4. +/// +/// See: <https://www.aumasson.jp/siphash/siphash.pdf> +/// +/// SipHash is a general-purpose hashing function: it runs at a good +/// speed (competitive with Spooky and City) and permits strong _keyed_ +/// hashing. This lets you key your hashtables from a strong RNG, such as +/// [`rand::os::OsRng`](https://doc.rust-lang.org/rand/rand/os/struct.OsRng.html). +/// +/// Although the SipHash algorithm is considered to be generally strong, +/// it is not intended for cryptographic purposes. As such, all +/// cryptographic uses of this implementation are _strongly discouraged_. +#[derive(Debug, Clone, Copy, Default)] +#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))] +pub struct SipHasher(SipHasher24); + +#[derive(Debug, Clone, Copy)] +#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))] +struct Hasher<S: Sip> { + k0: u64, + k1: u64, + length: usize, // how many bytes we've processed + state: State, // hash State + tail: u64, // unprocessed bytes le + ntail: usize, // how many bytes in tail are valid + _marker: PhantomData<S>, +} + +#[derive(Debug, Clone, Copy)] +#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))] +struct State { + // v0, v2 and v1, v3 show up in pairs in the algorithm, + // and simd implementations of SipHash will use vectors + // of v02 and v13. By placing them in this order in the struct, + // the compiler can pick up on just a few simd optimizations by itself. + v0: u64, + v2: u64, + v1: u64, + v3: u64, +} + +macro_rules! compress { + ($state:expr) => {{ + compress!($state.v0, $state.v1, $state.v2, $state.v3) + }}; + ($v0:expr, $v1:expr, $v2:expr, $v3:expr) => {{ + $v0 = $v0.wrapping_add($v1); + $v1 = $v1.rotate_left(13); + $v1 ^= $v0; + $v0 = $v0.rotate_left(32); + $v2 = $v2.wrapping_add($v3); + $v3 = $v3.rotate_left(16); + $v3 ^= $v2; + $v0 = $v0.wrapping_add($v3); + $v3 = $v3.rotate_left(21); + $v3 ^= $v0; + $v2 = $v2.wrapping_add($v1); + $v1 = $v1.rotate_left(17); + $v1 ^= $v2; + $v2 = $v2.rotate_left(32); + }}; +} + +/// Loads an integer of the desired type from a byte stream, in LE order. Uses +/// `copy_nonoverlapping` to let the compiler generate the most efficient way +/// to load it from a possibly unaligned address. +/// +/// Unsafe because: unchecked indexing at `i..i+size_of(int_ty)` +macro_rules! load_int_le { + ($buf:expr, $i:expr, $int_ty:ident) => {{ + debug_assert!($i + mem::size_of::<$int_ty>() <= $buf.len()); + let mut data = 0 as $int_ty; + ptr::copy_nonoverlapping( + $buf.as_ptr().add($i), + &mut data as *mut _ as *mut u8, + mem::size_of::<$int_ty>(), + ); + data.to_le() + }}; +} + +/// Loads a u64 using up to 7 bytes of a byte slice. It looks clumsy but the +/// `copy_nonoverlapping` calls that occur (via `load_int_le!`) all have fixed +/// sizes and avoid calling `memcpy`, which is good for speed. +/// +/// Unsafe because: unchecked indexing at start..start+len +#[inline] +unsafe fn u8to64_le(buf: &[u8], start: usize, len: usize) -> u64 { + debug_assert!(len < 8); + let mut i = 0; // current byte index (from LSB) in the output u64 + let mut out = 0; + if i + 3 < len { + out = load_int_le!(buf, start + i, u32) as u64; + i += 4; + } + if i + 1 < len { + out |= (load_int_le!(buf, start + i, u16) as u64) << (i * 8); + i += 2 + } + if i < len { + out |= (*buf.get_unchecked(start + i) as u64) << (i * 8); + i += 1; + } + debug_assert_eq!(i, len); + out +} + +impl SipHasher { + /// Creates a new `SipHasher` with the two initial keys set to 0. + #[inline] + pub fn new() -> SipHasher { + SipHasher::new_with_keys(0, 0) + } + + /// Creates a `SipHasher` that is keyed off the provided keys. + #[inline] + pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher { + SipHasher(SipHasher24::new_with_keys(key0, key1)) + } + + /// Creates a `SipHasher` from a 16 byte key. + pub fn new_with_key(key: &[u8; 16]) -> SipHasher { + let mut b0 = [0u8; 8]; + let mut b1 = [0u8; 8]; + b0.copy_from_slice(&key[0..8]); + b1.copy_from_slice(&key[8..16]); + let key0 = u64::from_le_bytes(b0); + let key1 = u64::from_le_bytes(b1); + Self::new_with_keys(key0, key1) + } + + /// Get the keys used by this hasher + pub fn keys(&self) -> (u64, u64) { + (self.0.hasher.k0, self.0.hasher.k1) + } + + /// Get the key used by this hasher as a 16 byte vector + pub fn key(&self) -> [u8; 16] { + let mut bytes = [0u8; 16]; + bytes[0..8].copy_from_slice(&self.0.hasher.k0.to_le_bytes()); + bytes[8..16].copy_from_slice(&self.0.hasher.k1.to_le_bytes()); + bytes + } + + /// Hash a byte array - This is the easiest and safest way to use SipHash. + #[inline] + pub fn hash(&self, bytes: &[u8]) -> u64 { + let mut hasher = self.0.hasher; + hasher.write(bytes); + hasher.finish() + } +} + +impl SipHasher13 { + /// Creates a new `SipHasher13` with the two initial keys set to 0. + #[inline] + pub fn new() -> SipHasher13 { + SipHasher13::new_with_keys(0, 0) + } + + /// Creates a `SipHasher13` that is keyed off the provided keys. + #[inline] + pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher13 { + SipHasher13 { + hasher: Hasher::new_with_keys(key0, key1), + } + } + + /// Creates a `SipHasher13` from a 16 byte key. + pub fn new_with_key(key: &[u8; 16]) -> SipHasher13 { + let mut b0 = [0u8; 8]; + let mut b1 = [0u8; 8]; + b0.copy_from_slice(&key[0..8]); + b1.copy_from_slice(&key[8..16]); + let key0 = u64::from_le_bytes(b0); + let key1 = u64::from_le_bytes(b1); + Self::new_with_keys(key0, key1) + } + + /// Get the keys used by this hasher + pub fn keys(&self) -> (u64, u64) { + (self.hasher.k0, self.hasher.k1) + } + + /// Get the key used by this hasher as a 16 byte vector + pub fn key(&self) -> [u8; 16] { + let mut bytes = [0u8; 16]; + bytes[0..8].copy_from_slice(&self.hasher.k0.to_le_bytes()); + bytes[8..16].copy_from_slice(&self.hasher.k1.to_le_bytes()); + bytes + } + + /// Hash a byte array - This is the easiest and safest way to use SipHash. + #[inline] + pub fn hash(&self, bytes: &[u8]) -> u64 { + let mut hasher = self.hasher; + hasher.write(bytes); + hasher.finish() + } +} + +impl SipHasher24 { + /// Creates a new `SipHasher24` with the two initial keys set to 0. + #[inline] + pub fn new() -> SipHasher24 { + SipHasher24::new_with_keys(0, 0) + } + + /// Creates a `SipHasher24` that is keyed off the provided keys. + #[inline] + pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher24 { + SipHasher24 { + hasher: Hasher::new_with_keys(key0, key1), + } + } + + /// Creates a `SipHasher24` from a 16 byte key. + pub fn new_with_key(key: &[u8; 16]) -> SipHasher24 { + let mut b0 = [0u8; 8]; + let mut b1 = [0u8; 8]; + b0.copy_from_slice(&key[0..8]); + b1.copy_from_slice(&key[8..16]); + let key0 = u64::from_le_bytes(b0); + let key1 = u64::from_le_bytes(b1); + Self::new_with_keys(key0, key1) + } + + /// Get the keys used by this hasher + pub fn keys(&self) -> (u64, u64) { + (self.hasher.k0, self.hasher.k1) + } + + /// Get the key used by this hasher as a 16 byte vector + pub fn key(&self) -> [u8; 16] { + let mut bytes = [0u8; 16]; + bytes[0..8].copy_from_slice(&self.hasher.k0.to_le_bytes()); + bytes[8..16].copy_from_slice(&self.hasher.k1.to_le_bytes()); + bytes + } + + /// Hash a byte array - This is the easiest and safest way to use SipHash. + #[inline] + pub fn hash(&self, bytes: &[u8]) -> u64 { + let mut hasher = self.hasher; + hasher.write(bytes); + hasher.finish() + } +} + +impl<S: Sip> Hasher<S> { + #[inline] + fn new_with_keys(key0: u64, key1: u64) -> Hasher<S> { + let mut state = Hasher { + k0: key0, + k1: key1, + length: 0, + state: State { + v0: 0, + v1: 0, + v2: 0, + v3: 0, + }, + tail: 0, + ntail: 0, + _marker: PhantomData, + }; + state.reset(); + state + } + + #[inline] + fn reset(&mut self) { + self.length = 0; + self.state.v0 = self.k0 ^ 0x736f6d6570736575; + self.state.v1 = self.k1 ^ 0x646f72616e646f6d; + self.state.v2 = self.k0 ^ 0x6c7967656e657261; + self.state.v3 = self.k1 ^ 0x7465646279746573; + self.ntail = 0; + } + + // A specialized write function for values with size <= 8. + // + // The hashing of multi-byte integers depends on endianness. E.g.: + // - little-endian: `write_u32(0xDDCCBBAA)` == `write([0xAA, 0xBB, 0xCC, 0xDD])` + // - big-endian: `write_u32(0xDDCCBBAA)` == `write([0xDD, 0xCC, 0xBB, 0xAA])` + // + // This function does the right thing for little-endian hardware. On + // big-endian hardware `x` must be byte-swapped first to give the right + // behaviour. After any byte-swapping, the input must be zero-extended to + // 64-bits. The caller is responsible for the byte-swapping and + // zero-extension. + #[inline] + fn short_write<T>(&mut self, _x: T, x: u64) { + let size = mem::size_of::<T>(); + self.length += size; + + // The original number must be zero-extended, not sign-extended. + debug_assert!(if size < 8 { x >> (8 * size) == 0 } else { true }); + + // The number of bytes needed to fill `self.tail`. + let needed = 8 - self.ntail; + + self.tail |= x << (8 * self.ntail); + if size < needed { + self.ntail += size; + return; + } + + // `self.tail` is full, process it. + self.state.v3 ^= self.tail; + S::c_rounds(&mut self.state); + self.state.v0 ^= self.tail; + + self.ntail = size - needed; + self.tail = if needed < 8 { x >> (8 * needed) } else { 0 }; + } +} + +impl hash::Hasher for SipHasher { + #[inline] + fn write(&mut self, msg: &[u8]) { + self.0.write(msg) + } + + #[inline] + fn finish(&self) -> u64 { + self.0.finish() + } + + #[inline] + fn write_usize(&mut self, i: usize) { + self.0.write_usize(i); + } + + #[inline] + fn write_u8(&mut self, i: u8) { + self.0.write_u8(i); + } + + #[inline] + fn write_u16(&mut self, i: u16) { + self.0.write_u16(i); + } + + #[inline] + fn write_u32(&mut self, i: u32) { + self.0.write_u32(i); + } + + #[inline] + fn write_u64(&mut self, i: u64) { + self.0.write_u64(i); + } +} + +impl hash::Hasher for SipHasher13 { + #[inline] + fn write(&mut self, msg: &[u8]) { + self.hasher.write(msg) + } + + #[inline] + fn finish(&self) -> u64 { + self.hasher.finish() + } + + #[inline] + fn write_usize(&mut self, i: usize) { + self.hasher.write_usize(i); + } + + #[inline] + fn write_u8(&mut self, i: u8) { + self.hasher.write_u8(i); + } + + #[inline] + fn write_u16(&mut self, i: u16) { + self.hasher.write_u16(i); + } + + #[inline] + fn write_u32(&mut self, i: u32) { + self.hasher.write_u32(i); + } + + #[inline] + fn write_u64(&mut self, i: u64) { + self.hasher.write_u64(i); + } +} + +impl hash::Hasher for SipHasher24 { + #[inline] + fn write(&mut self, msg: &[u8]) { + self.hasher.write(msg) + } + + #[inline] + fn finish(&self) -> u64 { + self.hasher.finish() + } + + #[inline] + fn write_usize(&mut self, i: usize) { + self.hasher.write_usize(i); + } + + #[inline] + fn write_u8(&mut self, i: u8) { + self.hasher.write_u8(i); + } + + #[inline] + fn write_u16(&mut self, i: u16) { + self.hasher.write_u16(i); + } + + #[inline] + fn write_u32(&mut self, i: u32) { + self.hasher.write_u32(i); + } + + #[inline] + fn write_u64(&mut self, i: u64) { + self.hasher.write_u64(i); + } +} + +impl<S: Sip> hash::Hasher for Hasher<S> { + #[inline] + fn write_usize(&mut self, i: usize) { + self.short_write(i, i.to_le() as u64); + } + + #[inline] + fn write_u8(&mut self, i: u8) { + self.short_write(i, i as u64); + } + + #[inline] + fn write_u32(&mut self, i: u32) { + self.short_write(i, i.to_le() as u64); + } + + #[inline] + fn write_u64(&mut self, i: u64) { + self.short_write(i, i.to_le()); + } + + #[inline] + fn write(&mut self, msg: &[u8]) { + let length = msg.len(); + self.length += length; + + let mut needed = 0; + + if self.ntail != 0 { + needed = 8 - self.ntail; + self.tail |= unsafe { u8to64_le(msg, 0, cmp::min(length, needed)) } << (8 * self.ntail); + if length < needed { + self.ntail += length; + return; + } else { + self.state.v3 ^= self.tail; + S::c_rounds(&mut self.state); + self.state.v0 ^= self.tail; + self.ntail = 0; + } + } + + // Buffered tail is now flushed, process new input. + let len = length - needed; + let left = len & 0x7; + + let mut i = needed; + while i < len - left { + let mi = unsafe { load_int_le!(msg, i, u64) }; + + self.state.v3 ^= mi; + S::c_rounds(&mut self.state); + self.state.v0 ^= mi; + + i += 8; + } + + self.tail = unsafe { u8to64_le(msg, i, left) }; + self.ntail = left; + } + + #[inline] + fn finish(&self) -> u64 { + let mut state = self.state; + + let b: u64 = ((self.length as u64 & 0xff) << 56) | self.tail; + + state.v3 ^= b; + S::c_rounds(&mut state); + state.v0 ^= b; + + state.v2 ^= 0xff; + S::d_rounds(&mut state); + + state.v0 ^ state.v1 ^ state.v2 ^ state.v3 + } +} + +impl<S: Sip> Default for Hasher<S> { + /// Creates a `Hasher<S>` with the two initial keys set to 0. + #[inline] + fn default() -> Hasher<S> { + Hasher::new_with_keys(0, 0) + } +} + +#[doc(hidden)] +trait Sip { + fn c_rounds(_: &mut State); + fn d_rounds(_: &mut State); +} + +#[derive(Debug, Clone, Copy, Default)] +struct Sip13Rounds; + +impl Sip for Sip13Rounds { + #[inline] + fn c_rounds(state: &mut State) { + compress!(state); + } + + #[inline] + fn d_rounds(state: &mut State) { + compress!(state); + compress!(state); + compress!(state); + } +} + +#[derive(Debug, Clone, Copy, Default)] +struct Sip24Rounds; + +impl Sip for Sip24Rounds { + #[inline] + fn c_rounds(state: &mut State) { + compress!(state); + compress!(state); + } + + #[inline] + fn d_rounds(state: &mut State) { + compress!(state); + compress!(state); + compress!(state); + compress!(state); + } +} diff --git a/src/sip128.rs b/src/sip128.rs new file mode 100644 index 0000000..5299ed0 --- /dev/null +++ b/src/sip128.rs @@ -0,0 +1,696 @@ +// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! An implementation of SipHash with a 128-bit output. + +use core::cmp; +use core::hash; +use core::hash::Hasher as _; +use core::marker::PhantomData; +use core::mem; +use core::ptr; +use core::u64; + +/// A 128-bit (2x64) hash output +#[derive(Debug, Clone, Copy, Default)] +#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))] +pub struct Hash128 { + pub h1: u64, + pub h2: u64, +} + +impl From<u128> for Hash128 { + fn from(v: u128) -> Self { + Hash128 { + h1: v as u64, + h2: (v >> 64) as u64, + } + } +} + +impl From<Hash128> for u128 { + fn from(h: Hash128) -> u128 { + (h.h1 as u128) | ((h.h2 as u128) << 64) + } +} + +/// An implementation of SipHash128 1-3. +#[derive(Debug, Clone, Copy, Default)] +#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))] +pub struct SipHasher13 { + hasher: Hasher<Sip13Rounds>, +} + +/// An implementation of SipHash128 2-4. +#[derive(Debug, Clone, Copy, Default)] +#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))] +pub struct SipHasher24 { + hasher: Hasher<Sip24Rounds>, +} + +/// An implementation of SipHash128 2-4. +/// +/// SipHash is a general-purpose hashing function: it runs at a good +/// speed (competitive with Spooky and City) and permits strong _keyed_ +/// hashing. This lets you key your hashtables from a strong RNG, such as +/// [`rand::os::OsRng`](https://doc.rust-lang.org/rand/rand/os/struct.OsRng.html). +/// +/// Although the SipHash algorithm is considered to be generally strong, +/// it is not intended for cryptographic purposes. As such, all +/// cryptographic uses of this implementation are _strongly discouraged_. +#[derive(Debug, Clone, Copy, Default)] +pub struct SipHasher(SipHasher24); + +#[derive(Debug, Copy)] +#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))] +struct Hasher<S: Sip> { + k0: u64, + k1: u64, + length: usize, // how many bytes we've processed + state: State, // hash State + tail: u64, // unprocessed bytes le + ntail: usize, // how many bytes in tail are valid + _marker: PhantomData<S>, +} + +#[derive(Debug, Clone, Copy)] +#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))] +struct State { + // v0, v2 and v1, v3 show up in pairs in the algorithm, + // and simd implementations of SipHash will use vectors + // of v02 and v13. By placing them in this order in the struct, + // the compiler can pick up on just a few simd optimizations by itself. + v0: u64, + v2: u64, + v1: u64, + v3: u64, +} + +macro_rules! compress { + ($state:expr) => {{ + compress!($state.v0, $state.v1, $state.v2, $state.v3) + }}; + ($v0:expr, $v1:expr, $v2:expr, $v3:expr) => {{ + $v0 = $v0.wrapping_add($v1); + $v1 = $v1.rotate_left(13); + $v1 ^= $v0; + $v0 = $v0.rotate_left(32); + $v2 = $v2.wrapping_add($v3); + $v3 = $v3.rotate_left(16); + $v3 ^= $v2; + $v0 = $v0.wrapping_add($v3); + $v3 = $v3.rotate_left(21); + $v3 ^= $v0; + $v2 = $v2.wrapping_add($v1); + $v1 = $v1.rotate_left(17); + $v1 ^= $v2; + $v2 = $v2.rotate_left(32); + }}; +} + +/// Loads an integer of the desired type from a byte stream, in LE order. Uses +/// `copy_nonoverlapping` to let the compiler generate the most efficient way +/// to load it from a possibly unaligned address. +/// +/// Unsafe because: unchecked indexing at `i..i+size_of(int_ty)` +macro_rules! load_int_le { + ($buf:expr, $i:expr, $int_ty:ident) => {{ + debug_assert!($i + mem::size_of::<$int_ty>() <= $buf.len()); + let mut data = 0 as $int_ty; + ptr::copy_nonoverlapping( + $buf.as_ptr().add($i), + &mut data as *mut _ as *mut u8, + mem::size_of::<$int_ty>(), + ); + data.to_le() + }}; +} + +/// Loads a u64 using up to 7 bytes of a byte slice. It looks clumsy but the +/// `copy_nonoverlapping` calls that occur (via `load_int_le!`) all have fixed +/// sizes and avoid calling `memcpy`, which is good for speed. +/// +/// Unsafe because: unchecked indexing at start..start+len +#[inline] +unsafe fn u8to64_le(buf: &[u8], start: usize, len: usize) -> u64 { + debug_assert!(len < 8); + let mut i = 0; // current byte index (from LSB) in the output u64 + let mut out = 0; + if i + 3 < len { + out = load_int_le!(buf, start + i, u32) as u64; + i += 4; + } + if i + 1 < len { + out |= (load_int_le!(buf, start + i, u16) as u64) << (i * 8); + i += 2 + } + if i < len { + out |= (*buf.get_unchecked(start + i) as u64) << (i * 8); + i += 1; + } + debug_assert_eq!(i, len); + out +} + +pub trait Hasher128 { + /// Return a 128-bit hash + fn finish128(&self) -> Hash128; +} + +impl SipHasher { + /// Creates a new `SipHasher` with the two initial keys set to 0. + #[inline] + pub fn new() -> SipHasher { + SipHasher::new_with_keys(0, 0) + } + + /// Creates a `SipHasher` that is keyed off the provided keys. + #[inline] + pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher { + SipHasher(SipHasher24::new_with_keys(key0, key1)) + } + + /// Creates a `SipHasher` from a 16 byte key. + pub fn new_with_key(key: &[u8; 16]) -> SipHasher { + let mut b0 = [0u8; 8]; + let mut b1 = [0u8; 8]; + b0.copy_from_slice(&key[0..8]); + b1.copy_from_slice(&key[8..16]); + let key0 = u64::from_le_bytes(b0); + let key1 = u64::from_le_bytes(b1); + Self::new_with_keys(key0, key1) + } + + /// Get the keys used by this hasher + pub fn keys(&self) -> (u64, u64) { + (self.0.hasher.k0, self.0.hasher.k1) + } + + /// Get the key used by this hasher as a 16 byte vector + pub fn key(&self) -> [u8; 16] { + let mut bytes = [0u8; 16]; + bytes[0..8].copy_from_slice(&self.0.hasher.k0.to_le_bytes()); + bytes[8..16].copy_from_slice(&self.0.hasher.k1.to_le_bytes()); + bytes + } + + /// Hash a byte array - This is the easiest and safest way to use SipHash. + #[inline] + pub fn hash(&self, bytes: &[u8]) -> Hash128 { + let mut hasher = self.0.hasher; + hasher.write(bytes); + hasher.finish128() + } +} + +impl Hasher128 for SipHasher { + /// Return a 128-bit hash + #[inline] + fn finish128(&self) -> Hash128 { + self.0.finish128() + } +} + +impl SipHasher13 { + /// Creates a new `SipHasher13` with the two initial keys set to 0. + #[inline] + pub fn new() -> SipHasher13 { + SipHasher13::new_with_keys(0, 0) + } + + /// Creates a `SipHasher13` that is keyed off the provided keys. + #[inline] + pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher13 { + SipHasher13 { + hasher: Hasher::new_with_keys(key0, key1), + } + } + + /// Creates a `SipHasher13` from a 16 byte key. + pub fn new_with_key(key: &[u8; 16]) -> SipHasher13 { + let mut b0 = [0u8; 8]; + let mut b1 = [0u8; 8]; + b0.copy_from_slice(&key[0..8]); + b1.copy_from_slice(&key[8..16]); + let key0 = u64::from_le_bytes(b0); + let key1 = u64::from_le_bytes(b1); + Self::new_with_keys(key0, key1) + } + + /// Get the keys used by this hasher + pub fn keys(&self) -> (u64, u64) { + (self.hasher.k0, self.hasher.k1) + } + + /// Get the key used by this hasher as a 16 byte vector + pub fn key(&self) -> [u8; 16] { + let mut bytes = [0u8; 16]; + bytes[0..8].copy_from_slice(&self.hasher.k0.to_le_bytes()); + bytes[8..16].copy_from_slice(&self.hasher.k1.to_le_bytes()); + bytes + } + + /// Hash a byte array - This is the easiest and safest way to use SipHash. + #[inline] + pub fn hash(&self, bytes: &[u8]) -> Hash128 { + let mut hasher = self.hasher; + hasher.write(bytes); + hasher.finish128() + } +} + +impl Hasher128 for SipHasher13 { + /// Return a 128-bit hash + #[inline] + fn finish128(&self) -> Hash128 { + self.hasher.finish128() + } +} + +impl SipHasher24 { + /// Creates a new `SipHasher24` with the two initial keys set to 0. + #[inline] + pub fn new() -> SipHasher24 { + SipHasher24::new_with_keys(0, 0) + } + + /// Creates a `SipHasher24` that is keyed off the provided keys. + #[inline] + pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher24 { + SipHasher24 { + hasher: Hasher::new_with_keys(key0, key1), + } + } + + /// Creates a `SipHasher24` from a 16 byte key. + pub fn new_with_key(key: &[u8; 16]) -> SipHasher24 { + let mut b0 = [0u8; 8]; + let mut b1 = [0u8; 8]; + b0.copy_from_slice(&key[0..8]); + b1.copy_from_slice(&key[8..16]); + let key0 = u64::from_le_bytes(b0); + let key1 = u64::from_le_bytes(b1); + Self::new_with_keys(key0, key1) + } + + /// Get the keys used by this hasher + pub fn keys(&self) -> (u64, u64) { + (self.hasher.k0, self.hasher.k1) + } + + /// Get the key used by this hasher as a 16 byte vector + pub fn key(&self) -> [u8; 16] { + let mut bytes = [0u8; 16]; + bytes[0..8].copy_from_slice(&self.hasher.k0.to_le_bytes()); + bytes[8..16].copy_from_slice(&self.hasher.k1.to_le_bytes()); + bytes + } + + /// Hash a byte array - This is the easiest and safest way to use SipHash. + #[inline] + pub fn hash(&self, bytes: &[u8]) -> Hash128 { + let mut hasher = self.hasher; + hasher.write(bytes); + hasher.finish128() + } +} + +impl Hasher128 for SipHasher24 { + /// Return a 128-bit hash + #[inline] + fn finish128(&self) -> Hash128 { + self.hasher.finish128() + } +} + +impl<S: Sip> Hasher<S> { + #[inline] + fn new_with_keys(key0: u64, key1: u64) -> Hasher<S> { + let mut state = Hasher { + k0: key0, + k1: key1, + length: 0, + state: State { + v0: 0, + v1: 0xee, + v2: 0, + v3: 0, + }, + tail: 0, + ntail: 0, + _marker: PhantomData, + }; + state.reset(); + state + } + + #[inline] + fn reset(&mut self) { + self.length = 0; + self.state.v0 = self.k0 ^ 0x736f6d6570736575; + self.state.v1 = self.k1 ^ 0x646f72616e646f83; + self.state.v2 = self.k0 ^ 0x6c7967656e657261; + self.state.v3 = self.k1 ^ 0x7465646279746573; + self.ntail = 0; + } + + // A specialized write function for values with size <= 8. + // + // The hashing of multi-byte integers depends on endianness. E.g.: + // - little-endian: `write_u32(0xDDCCBBAA)` == `write([0xAA, 0xBB, 0xCC, 0xDD])` + // - big-endian: `write_u32(0xDDCCBBAA)` == `write([0xDD, 0xCC, 0xBB, 0xAA])` + // + // This function does the right thing for little-endian hardware. On + // big-endian hardware `x` must be byte-swapped first to give the right + // behaviour. After any byte-swapping, the input must be zero-extended to + // 64-bits. The caller is responsible for the byte-swapping and + // zero-extension. + #[inline] + fn short_write<T>(&mut self, _x: T, x: u64) { + let size = mem::size_of::<T>(); + self.length += size; + + // The original number must be zero-extended, not sign-extended. + debug_assert!(if size < 8 { x >> (8 * size) == 0 } else { true }); + + // The number of bytes needed to fill `self.tail`. + let needed = 8 - self.ntail; + + self.tail |= x << (8 * self.ntail); + if size < needed { + self.ntail += size; + return; + } + + // `self.tail` is full, process it. + self.state.v3 ^= self.tail; + S::c_rounds(&mut self.state); + self.state.v0 ^= self.tail; + + self.ntail = size - needed; + self.tail = if needed < 8 { x >> (8 * needed) } else { 0 }; + } +} + +impl<S: Sip> Hasher<S> { + #[inline] + pub fn finish128(&self) -> Hash128 { + let mut state = self.state; + + let b: u64 = ((self.length as u64 & 0xff) << 56) | self.tail; + + state.v3 ^= b; + S::c_rounds(&mut state); + state.v0 ^= b; + + state.v2 ^= 0xee; + S::d_rounds(&mut state); + let h1 = state.v0 ^ state.v1 ^ state.v2 ^ state.v3; + + state.v1 ^= 0xdd; + S::d_rounds(&mut state); + let h2 = state.v0 ^ state.v1 ^ state.v2 ^ state.v3; + + Hash128 { h1, h2 } + } +} + +impl hash::Hasher for SipHasher { + #[inline] + fn write(&mut self, msg: &[u8]) { + self.0.write(msg) + } + + #[inline] + fn finish(&self) -> u64 { + self.0.finish() + } + + #[inline] + fn write_usize(&mut self, i: usize) { + self.0.write_usize(i); + } + + #[inline] + fn write_u8(&mut self, i: u8) { + self.0.write_u8(i); + } + + #[inline] + fn write_u16(&mut self, i: u16) { + self.0.write_u16(i); + } + + #[inline] + fn write_u32(&mut self, i: u32) { + self.0.write_u32(i); + } + + #[inline] + fn write_u64(&mut self, i: u64) { + self.0.write_u64(i); + } +} + +impl hash::Hasher for SipHasher13 { + #[inline] + fn write(&mut self, msg: &[u8]) { + self.hasher.write(msg) + } + + #[inline] + fn finish(&self) -> u64 { + self.hasher.finish() + } + + #[inline] + fn write_usize(&mut self, i: usize) { + self.hasher.write_usize(i); + } + + #[inline] + fn write_u8(&mut self, i: u8) { + self.hasher.write_u8(i); + } + + #[inline] + fn write_u16(&mut self, i: u16) { + self.hasher.write_u16(i); + } + + #[inline] + fn write_u32(&mut self, i: u32) { + self.hasher.write_u32(i); + } + + #[inline] + fn write_u64(&mut self, i: u64) { + self.hasher.write_u64(i); + } +} + +impl hash::Hasher for SipHasher24 { + #[inline] + fn write(&mut self, msg: &[u8]) { + self.hasher.write(msg) + } + + #[inline] + fn finish(&self) -> u64 { + self.hasher.finish() + } + + #[inline] + fn write_usize(&mut self, i: usize) { + self.hasher.write_usize(i); + } + + #[inline] + fn write_u8(&mut self, i: u8) { + self.hasher.write_u8(i); + } + + #[inline] + fn write_u16(&mut self, i: u16) { + self.hasher.write_u16(i); + } + + #[inline] + fn write_u32(&mut self, i: u32) { + self.hasher.write_u32(i); + } + + #[inline] + fn write_u64(&mut self, i: u64) { + self.hasher.write_u64(i); + } +} + +impl<S: Sip> hash::Hasher for Hasher<S> { + #[inline] + fn write_usize(&mut self, i: usize) { + self.short_write(i, i.to_le() as u64); + } + + #[inline] + fn write_u8(&mut self, i: u8) { + self.short_write(i, i as u64); + } + + #[inline] + fn write_u32(&mut self, i: u32) { + self.short_write(i, i.to_le() as u64); + } + + #[inline] + fn write_u64(&mut self, i: u64) { + self.short_write(i, i.to_le()); + } + + #[inline] + fn write(&mut self, msg: &[u8]) { + let length = msg.len(); + self.length += length; + + let mut needed = 0; + + if self.ntail != 0 { + needed = 8 - self.ntail; + self.tail |= unsafe { u8to64_le(msg, 0, cmp::min(length, needed)) } << (8 * self.ntail); + if length < needed { + self.ntail += length; + return; + } else { + self.state.v3 ^= self.tail; + S::c_rounds(&mut self.state); + self.state.v0 ^= self.tail; + self.ntail = 0; + } + } + + // Buffered tail is now flushed, process new input. + let len = length - needed; + let left = len & 0x7; + + let mut i = needed; + while i < len - left { + let mi = unsafe { load_int_le!(msg, i, u64) }; + + self.state.v3 ^= mi; + S::c_rounds(&mut self.state); + self.state.v0 ^= mi; + + i += 8; + } + + self.tail = unsafe { u8to64_le(msg, i, left) }; + self.ntail = left; + } + + #[inline] + fn finish(&self) -> u64 { + self.finish128().h2 + } +} + +impl<S: Sip> Clone for Hasher<S> { + #[inline] + fn clone(&self) -> Hasher<S> { + Hasher { + k0: self.k0, + k1: self.k1, + length: self.length, + state: self.state, + tail: self.tail, + ntail: self.ntail, + _marker: self._marker, + } + } +} + +impl<S: Sip> Default for Hasher<S> { + /// Creates a `Hasher<S>` with the two initial keys set to 0. + #[inline] + fn default() -> Hasher<S> { + Hasher::new_with_keys(0, 0) + } +} + +#[doc(hidden)] +trait Sip { + fn c_rounds(_: &mut State); + fn d_rounds(_: &mut State); +} + +#[derive(Debug, Clone, Copy, Default)] +struct Sip13Rounds; + +impl Sip for Sip13Rounds { + #[inline] + fn c_rounds(state: &mut State) { + compress!(state); + } + + #[inline] + fn d_rounds(state: &mut State) { + compress!(state); + compress!(state); + compress!(state); + } +} + +#[derive(Debug, Clone, Copy, Default)] +struct Sip24Rounds; + +impl Sip for Sip24Rounds { + #[inline] + fn c_rounds(state: &mut State) { + compress!(state); + compress!(state); + } + + #[inline] + fn d_rounds(state: &mut State) { + compress!(state); + compress!(state); + compress!(state); + compress!(state); + } +} + +impl Hash128 { + /// Convert into a 16-bytes vector + pub fn as_bytes(&self) -> [u8; 16] { + let mut bytes = [0u8; 16]; + let h1 = self.h1.to_le(); + let h2 = self.h2.to_le(); + unsafe { + ptr::copy_nonoverlapping(&h1 as *const _ as *const u8, bytes.as_mut_ptr(), 8); + ptr::copy_nonoverlapping(&h2 as *const _ as *const u8, bytes.as_mut_ptr().add(8), 8); + } + bytes + } + + /// Convert into a `u128` + #[inline] + pub fn as_u128(&self) -> u128 { + let h1 = self.h1.to_le(); + let h2 = self.h2.to_le(); + h1 as u128 | ((h2 as u128) << 64) + } + + /// Convert into `(u64, u64)` + #[inline] + pub fn as_u64(&self) -> (u64, u64) { + let h1 = self.h1.to_le(); + let h2 = self.h2.to_le(); + (h1, h2) + } +} diff --git a/src/tests.rs b/src/tests.rs new file mode 100644 index 0000000..48dd48c --- /dev/null +++ b/src/tests.rs @@ -0,0 +1,332 @@ +// Copyright 2014 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use std::hash::{Hash, Hasher}; + +use super::sip::{SipHasher, SipHasher13, SipHasher24}; + +// Hash just the bytes of the slice, without length prefix +struct Bytes<'a>(&'a [u8]); + +impl<'a> Hash for Bytes<'a> { + #[allow(unused_must_use)] + fn hash<H: Hasher>(&self, state: &mut H) { + let Bytes(v) = *self; + state.write(v); + } +} + +macro_rules! u8to64_le { + ($buf:expr, $i:expr) => { + $buf[0 + $i] as u64 + | ($buf[1 + $i] as u64) << 8 + | ($buf[2 + $i] as u64) << 16 + | ($buf[3 + $i] as u64) << 24 + | ($buf[4 + $i] as u64) << 32 + | ($buf[5 + $i] as u64) << 40 + | ($buf[6 + $i] as u64) << 48 + | ($buf[7 + $i] as u64) << 56 + }; + ($buf:expr, $i:expr, $len:expr) => {{ + let mut t = 0; + let mut out = 0; + while t < $len { + out |= ($buf[t + $i] as u64) << t * 8; + t += 1; + } + out + }}; +} + +fn hash_with<H: Hasher, T: Hash>(mut st: H, x: &T) -> u64 { + x.hash(&mut st); + st.finish() +} + +fn hash<T: Hash>(x: &T) -> u64 { + hash_with(SipHasher::new(), x) +} + +#[test] +#[allow(unused_must_use)] +fn test_siphash_1_3() { + let vecs: [[u8; 8]; 64] = [ + [0xdc, 0xc4, 0x0f, 0x05, 0x58, 0x01, 0xac, 0xab], + [0x93, 0xca, 0x57, 0x7d, 0xf3, 0x9b, 0xf4, 0xc9], + [0x4d, 0xd4, 0xc7, 0x4d, 0x02, 0x9b, 0xcb, 0x82], + [0xfb, 0xf7, 0xdd, 0xe7, 0xb8, 0x0a, 0xf8, 0x8b], + [0x28, 0x83, 0xd3, 0x88, 0x60, 0x57, 0x75, 0xcf], + [0x67, 0x3b, 0x53, 0x49, 0x2f, 0xd5, 0xf9, 0xde], + [0xa7, 0x22, 0x9f, 0xc5, 0x50, 0x2b, 0x0d, 0xc5], + [0x40, 0x11, 0xb1, 0x9b, 0x98, 0x7d, 0x92, 0xd3], + [0x8e, 0x9a, 0x29, 0x8d, 0x11, 0x95, 0x90, 0x36], + [0xe4, 0x3d, 0x06, 0x6c, 0xb3, 0x8e, 0xa4, 0x25], + [0x7f, 0x09, 0xff, 0x92, 0xee, 0x85, 0xde, 0x79], + [0x52, 0xc3, 0x4d, 0xf9, 0xc1, 0x18, 0xc1, 0x70], + [0xa2, 0xd9, 0xb4, 0x57, 0xb1, 0x84, 0xa3, 0x78], + [0xa7, 0xff, 0x29, 0x12, 0x0c, 0x76, 0x6f, 0x30], + [0x34, 0x5d, 0xf9, 0xc0, 0x11, 0xa1, 0x5a, 0x60], + [0x56, 0x99, 0x51, 0x2a, 0x6d, 0xd8, 0x20, 0xd3], + [0x66, 0x8b, 0x90, 0x7d, 0x1a, 0xdd, 0x4f, 0xcc], + [0x0c, 0xd8, 0xdb, 0x63, 0x90, 0x68, 0xf2, 0x9c], + [0x3e, 0xe6, 0x73, 0xb4, 0x9c, 0x38, 0xfc, 0x8f], + [0x1c, 0x7d, 0x29, 0x8d, 0xe5, 0x9d, 0x1f, 0xf2], + [0x40, 0xe0, 0xcc, 0xa6, 0x46, 0x2f, 0xdc, 0xc0], + [0x44, 0xf8, 0x45, 0x2b, 0xfe, 0xab, 0x92, 0xb9], + [0x2e, 0x87, 0x20, 0xa3, 0x9b, 0x7b, 0xfe, 0x7f], + [0x23, 0xc1, 0xe6, 0xda, 0x7f, 0x0e, 0x5a, 0x52], + [0x8c, 0x9c, 0x34, 0x67, 0xb2, 0xae, 0x64, 0xf4], + [0x79, 0x09, 0x5b, 0x70, 0x28, 0x59, 0xcd, 0x45], + [0xa5, 0x13, 0x99, 0xca, 0xe3, 0x35, 0x3e, 0x3a], + [0x35, 0x3b, 0xde, 0x4a, 0x4e, 0xc7, 0x1d, 0xa9], + [0x0d, 0xd0, 0x6c, 0xef, 0x02, 0xed, 0x0b, 0xfb], + [0xf4, 0xe1, 0xb1, 0x4a, 0xb4, 0x3c, 0xd9, 0x88], + [0x63, 0xe6, 0xc5, 0x43, 0xd6, 0x11, 0x0f, 0x54], + [0xbc, 0xd1, 0x21, 0x8c, 0x1f, 0xdd, 0x70, 0x23], + [0x0d, 0xb6, 0xa7, 0x16, 0x6c, 0x7b, 0x15, 0x81], + [0xbf, 0xf9, 0x8f, 0x7a, 0xe5, 0xb9, 0x54, 0x4d], + [0x3e, 0x75, 0x2a, 0x1f, 0x78, 0x12, 0x9f, 0x75], + [0x91, 0x6b, 0x18, 0xbf, 0xbe, 0xa3, 0xa1, 0xce], + [0x06, 0x62, 0xa2, 0xad, 0xd3, 0x08, 0xf5, 0x2c], + [0x57, 0x30, 0xc3, 0xa3, 0x2d, 0x1c, 0x10, 0xb6], + [0xa1, 0x36, 0x3a, 0xae, 0x96, 0x74, 0xf4, 0xb3], + [0x92, 0x83, 0x10, 0x7b, 0x54, 0x57, 0x6b, 0x62], + [0x31, 0x15, 0xe4, 0x99, 0x32, 0x36, 0xd2, 0xc1], + [0x44, 0xd9, 0x1a, 0x3f, 0x92, 0xc1, 0x7c, 0x66], + [0x25, 0x88, 0x13, 0xc8, 0xfe, 0x4f, 0x70, 0x65], + [0xa6, 0x49, 0x89, 0xc2, 0xd1, 0x80, 0xf2, 0x24], + [0x6b, 0x87, 0xf8, 0xfa, 0xed, 0x1c, 0xca, 0xc2], + [0x96, 0x21, 0x04, 0x9f, 0xfc, 0x4b, 0x16, 0xc2], + [0x23, 0xd6, 0xb1, 0x68, 0x93, 0x9c, 0x6e, 0xa1], + [0xfd, 0x14, 0x51, 0x8b, 0x9c, 0x16, 0xfb, 0x49], + [0x46, 0x4c, 0x07, 0xdf, 0xf8, 0x43, 0x31, 0x9f], + [0xb3, 0x86, 0xcc, 0x12, 0x24, 0xaf, 0xfd, 0xc6], + [0x8f, 0x09, 0x52, 0x0a, 0xd1, 0x49, 0xaf, 0x7e], + [0x9a, 0x2f, 0x29, 0x9d, 0x55, 0x13, 0xf3, 0x1c], + [0x12, 0x1f, 0xf4, 0xa2, 0xdd, 0x30, 0x4a, 0xc4], + [0xd0, 0x1e, 0xa7, 0x43, 0x89, 0xe9, 0xfa, 0x36], + [0xe6, 0xbc, 0xf0, 0x73, 0x4c, 0xb3, 0x8f, 0x31], + [0x80, 0xe9, 0xa7, 0x70, 0x36, 0xbf, 0x7a, 0xa2], + [0x75, 0x6d, 0x3c, 0x24, 0xdb, 0xc0, 0xbc, 0xb4], + [0x13, 0x15, 0xb7, 0xfd, 0x52, 0xd8, 0xf8, 0x23], + [0x08, 0x8a, 0x7d, 0xa6, 0x4d, 0x5f, 0x03, 0x8f], + [0x48, 0xf1, 0xe8, 0xb7, 0xe5, 0xd0, 0x9c, 0xd8], + [0xee, 0x44, 0xa6, 0xf7, 0xbc, 0xe6, 0xf4, 0xf6], + [0xf2, 0x37, 0x18, 0x0f, 0xd8, 0x9a, 0xc5, 0xae], + [0xe0, 0x94, 0x66, 0x4b, 0x15, 0xf6, 0xb2, 0xc3], + [0xa8, 0xb3, 0xbb, 0xb7, 0x62, 0x90, 0x19, 0x9d], + ]; + + let k0 = 0x_07_06_05_04_03_02_01_00; + let k1 = 0x_0f_0e_0d_0c_0b_0a_09_08; + let mut buf = Vec::new(); + let mut t = 0; + let mut state_inc = SipHasher13::new_with_keys(k0, k1); + + while t < 64 { + let vec = u8to64_le!(vecs[t], 0); + let out = hash_with(SipHasher13::new_with_keys(k0, k1), &Bytes(&buf)); + assert_eq!(vec, out); + + let full = hash_with(SipHasher13::new_with_keys(k0, k1), &Bytes(&buf)); + let i = state_inc.finish(); + + assert_eq!(full, i); + assert_eq!(full, vec); + + buf.push(t as u8); + Hasher::write(&mut state_inc, &[t as u8]); + + t += 1; + } +} + +#[test] +#[allow(unused_must_use)] +fn test_siphash_2_4() { + let vecs: [[u8; 8]; 64] = [ + [0x31, 0x0e, 0x0e, 0xdd, 0x47, 0xdb, 0x6f, 0x72], + [0xfd, 0x67, 0xdc, 0x93, 0xc5, 0x39, 0xf8, 0x74], + [0x5a, 0x4f, 0xa9, 0xd9, 0x09, 0x80, 0x6c, 0x0d], + [0x2d, 0x7e, 0xfb, 0xd7, 0x96, 0x66, 0x67, 0x85], + [0xb7, 0x87, 0x71, 0x27, 0xe0, 0x94, 0x27, 0xcf], + [0x8d, 0xa6, 0x99, 0xcd, 0x64, 0x55, 0x76, 0x18], + [0xce, 0xe3, 0xfe, 0x58, 0x6e, 0x46, 0xc9, 0xcb], + [0x37, 0xd1, 0x01, 0x8b, 0xf5, 0x00, 0x02, 0xab], + [0x62, 0x24, 0x93, 0x9a, 0x79, 0xf5, 0xf5, 0x93], + [0xb0, 0xe4, 0xa9, 0x0b, 0xdf, 0x82, 0x00, 0x9e], + [0xf3, 0xb9, 0xdd, 0x94, 0xc5, 0xbb, 0x5d, 0x7a], + [0xa7, 0xad, 0x6b, 0x22, 0x46, 0x2f, 0xb3, 0xf4], + [0xfb, 0xe5, 0x0e, 0x86, 0xbc, 0x8f, 0x1e, 0x75], + [0x90, 0x3d, 0x84, 0xc0, 0x27, 0x56, 0xea, 0x14], + [0xee, 0xf2, 0x7a, 0x8e, 0x90, 0xca, 0x23, 0xf7], + [0xe5, 0x45, 0xbe, 0x49, 0x61, 0xca, 0x29, 0xa1], + [0xdb, 0x9b, 0xc2, 0x57, 0x7f, 0xcc, 0x2a, 0x3f], + [0x94, 0x47, 0xbe, 0x2c, 0xf5, 0xe9, 0x9a, 0x69], + [0x9c, 0xd3, 0x8d, 0x96, 0xf0, 0xb3, 0xc1, 0x4b], + [0xbd, 0x61, 0x79, 0xa7, 0x1d, 0xc9, 0x6d, 0xbb], + [0x98, 0xee, 0xa2, 0x1a, 0xf2, 0x5c, 0xd6, 0xbe], + [0xc7, 0x67, 0x3b, 0x2e, 0xb0, 0xcb, 0xf2, 0xd0], + [0x88, 0x3e, 0xa3, 0xe3, 0x95, 0x67, 0x53, 0x93], + [0xc8, 0xce, 0x5c, 0xcd, 0x8c, 0x03, 0x0c, 0xa8], + [0x94, 0xaf, 0x49, 0xf6, 0xc6, 0x50, 0xad, 0xb8], + [0xea, 0xb8, 0x85, 0x8a, 0xde, 0x92, 0xe1, 0xbc], + [0xf3, 0x15, 0xbb, 0x5b, 0xb8, 0x35, 0xd8, 0x17], + [0xad, 0xcf, 0x6b, 0x07, 0x63, 0x61, 0x2e, 0x2f], + [0xa5, 0xc9, 0x1d, 0xa7, 0xac, 0xaa, 0x4d, 0xde], + [0x71, 0x65, 0x95, 0x87, 0x66, 0x50, 0xa2, 0xa6], + [0x28, 0xef, 0x49, 0x5c, 0x53, 0xa3, 0x87, 0xad], + [0x42, 0xc3, 0x41, 0xd8, 0xfa, 0x92, 0xd8, 0x32], + [0xce, 0x7c, 0xf2, 0x72, 0x2f, 0x51, 0x27, 0x71], + [0xe3, 0x78, 0x59, 0xf9, 0x46, 0x23, 0xf3, 0xa7], + [0x38, 0x12, 0x05, 0xbb, 0x1a, 0xb0, 0xe0, 0x12], + [0xae, 0x97, 0xa1, 0x0f, 0xd4, 0x34, 0xe0, 0x15], + [0xb4, 0xa3, 0x15, 0x08, 0xbe, 0xff, 0x4d, 0x31], + [0x81, 0x39, 0x62, 0x29, 0xf0, 0x90, 0x79, 0x02], + [0x4d, 0x0c, 0xf4, 0x9e, 0xe5, 0xd4, 0xdc, 0xca], + [0x5c, 0x73, 0x33, 0x6a, 0x76, 0xd8, 0xbf, 0x9a], + [0xd0, 0xa7, 0x04, 0x53, 0x6b, 0xa9, 0x3e, 0x0e], + [0x92, 0x59, 0x58, 0xfc, 0xd6, 0x42, 0x0c, 0xad], + [0xa9, 0x15, 0xc2, 0x9b, 0xc8, 0x06, 0x73, 0x18], + [0x95, 0x2b, 0x79, 0xf3, 0xbc, 0x0a, 0xa6, 0xd4], + [0xf2, 0x1d, 0xf2, 0xe4, 0x1d, 0x45, 0x35, 0xf9], + [0x87, 0x57, 0x75, 0x19, 0x04, 0x8f, 0x53, 0xa9], + [0x10, 0xa5, 0x6c, 0xf5, 0xdf, 0xcd, 0x9a, 0xdb], + [0xeb, 0x75, 0x09, 0x5c, 0xcd, 0x98, 0x6c, 0xd0], + [0x51, 0xa9, 0xcb, 0x9e, 0xcb, 0xa3, 0x12, 0xe6], + [0x96, 0xaf, 0xad, 0xfc, 0x2c, 0xe6, 0x66, 0xc7], + [0x72, 0xfe, 0x52, 0x97, 0x5a, 0x43, 0x64, 0xee], + [0x5a, 0x16, 0x45, 0xb2, 0x76, 0xd5, 0x92, 0xa1], + [0xb2, 0x74, 0xcb, 0x8e, 0xbf, 0x87, 0x87, 0x0a], + [0x6f, 0x9b, 0xb4, 0x20, 0x3d, 0xe7, 0xb3, 0x81], + [0xea, 0xec, 0xb2, 0xa3, 0x0b, 0x22, 0xa8, 0x7f], + [0x99, 0x24, 0xa4, 0x3c, 0xc1, 0x31, 0x57, 0x24], + [0xbd, 0x83, 0x8d, 0x3a, 0xaf, 0xbf, 0x8d, 0xb7], + [0x0b, 0x1a, 0x2a, 0x32, 0x65, 0xd5, 0x1a, 0xea], + [0x13, 0x50, 0x79, 0xa3, 0x23, 0x1c, 0xe6, 0x60], + [0x93, 0x2b, 0x28, 0x46, 0xe4, 0xd7, 0x06, 0x66], + [0xe1, 0x91, 0x5f, 0x5c, 0xb1, 0xec, 0xa4, 0x6c], + [0xf3, 0x25, 0x96, 0x5c, 0xa1, 0x6d, 0x62, 0x9f], + [0x57, 0x5f, 0xf2, 0x8e, 0x60, 0x38, 0x1b, 0xe5], + [0x72, 0x45, 0x06, 0xeb, 0x4c, 0x32, 0x8a, 0x95], + ]; + + let k0 = 0x_07_06_05_04_03_02_01_00; + let k1 = 0x_0f_0e_0d_0c_0b_0a_09_08; + let mut buf = Vec::new(); + let mut t = 0; + let mut state_inc = SipHasher24::new_with_keys(k0, k1); + + while t < 64 { + let vec = u8to64_le!(vecs[t], 0); + let out = hash_with(SipHasher24::new_with_keys(k0, k1), &Bytes(&buf)); + assert_eq!(vec, out); + + let full = hash_with(SipHasher24::new_with_keys(k0, k1), &Bytes(&buf)); + let i = state_inc.finish(); + + assert_eq!(full, i); + assert_eq!(full, vec); + + buf.push(t as u8); + Hasher::write(&mut state_inc, &[t as u8]); + + t += 1; + } +} +#[test] +fn test_hash_idempotent() { + let val64 = 0xdead_beef_dead_beef_u64; + assert_eq!(hash(&val64), hash(&val64)); + let val32 = 0xdeadbeef_u32; + assert_eq!(hash(&val32), hash(&val32)); +} + +#[test] +fn test_hash_no_bytes_dropped_64() { + let val = 0xdead_beef_dead_beef_u64; + + assert_ne!(hash(&val), hash(&zero_byte(val, 0))); + assert_ne!(hash(&val), hash(&zero_byte(val, 1))); + assert_ne!(hash(&val), hash(&zero_byte(val, 2))); + assert_ne!(hash(&val), hash(&zero_byte(val, 3))); + assert_ne!(hash(&val), hash(&zero_byte(val, 4))); + assert_ne!(hash(&val), hash(&zero_byte(val, 5))); + assert_ne!(hash(&val), hash(&zero_byte(val, 6))); + assert_ne!(hash(&val), hash(&zero_byte(val, 7))); + + fn zero_byte(val: u64, byte: usize) -> u64 { + assert!(byte < 8); + val & !(0xff << (byte * 8)) + } +} + +#[test] +fn test_hash_no_bytes_dropped_32() { + let val = 0xdeadbeef_u32; + + assert_ne!(hash(&val), hash(&zero_byte(val, 0))); + assert_ne!(hash(&val), hash(&zero_byte(val, 1))); + assert_ne!(hash(&val), hash(&zero_byte(val, 2))); + assert_ne!(hash(&val), hash(&zero_byte(val, 3))); + + fn zero_byte(val: u32, byte: usize) -> u32 { + assert!(byte < 4); + val & !(0xff << (byte * 8)) + } +} + +#[test] +fn test_hash_no_concat_alias() { + let s = ("aa", "bb"); + let t = ("aabb", ""); + let u = ("a", "abb"); + + assert!(s != t && t != u); + assert!(hash(&s) != hash(&t) && hash(&s) != hash(&u)); + + let u = [1, 0, 0, 0]; + let v = (&u[..1], &u[1..3], &u[3..]); + let w = (&u[..], &u[4..4], &u[4..4]); + + assert_ne!(v, w); + assert_ne!(hash(&v), hash(&w)); +} + +#[test] +fn test_hash_simple() { + let array: &[u8] = &[1, 2, 3]; + let key: &[u8; 16] = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]; + let hasher = SipHasher13::new_with_key(key); + let h = hasher.hash(array); + _ = h; +} + +#[test] +fn test_hash_incremental() { + let array1: &[u8] = &[1, 2, 3]; + let array2: &[u8] = &[4, 5, 6]; + let key: &[u8; 16] = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]; + let mut hasher = SipHasher13::new_with_key(key); + hasher.write(array1); + hasher.write(array2); + let h = hasher.finish(); + _ = h; +} + +#[test] +#[cfg(all(feature = "serde", feature = "serde_json"))] +fn test_hash_serde() { + let val64 = 0xdead_beef_dead_beef_u64; + let hash = hash(&val64); + let serialized = serde_json::to_string(&hash).unwrap(); + let deserialized: u64 = serde_json::from_str(&serialized).unwrap(); + assert_eq!(hash, deserialized); +} diff --git a/src/tests128.rs b/src/tests128.rs new file mode 100644 index 0000000..c1711b7 --- /dev/null +++ b/src/tests128.rs @@ -0,0 +1,134 @@ +// Copyright 2014 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use std::hash::{Hash, Hasher}; + +use super::sip128::{Hasher128, SipHasher, SipHasher13, SipHasher24}; + +// Hash just the bytes of the slice, without length prefix +struct Bytes<'a>(&'a [u8]); + +impl<'a> Hash for Bytes<'a> { + #[allow(unused_must_use)] + fn hash<H: Hasher>(&self, state: &mut H) { + let Bytes(v) = *self; + state.write(v); + } +} + +fn hash_with<H: Hasher + Hasher128, T: Hash>(mut st: H, x: &T) -> [u8; 16] { + x.hash(&mut st); + st.finish128().as_bytes() +} + +fn hash<T: Hash>(x: &T) -> [u8; 16] { + hash_with(SipHasher::new(), x) +} + +#[test] +fn test_siphash128_idempotent() { + let val64 = 0xdead_beef_dead_beef_u64; + assert_eq!(hash(&val64), hash(&val64)); + let val32 = 0xdeadbeef_u32; + assert_eq!(hash(&val32), hash(&val32)); +} + +#[test] +#[allow(unused_must_use)] +fn test_siphash128_1_3() { + let vecs: [[u8; 16]; 1] = [[ + 231, 126, 188, 178, 39, 136, 165, 190, 253, 98, 219, 106, 221, 48, 48, 1, + ]]; + + let k0 = 0x_07_06_05_04_03_02_01_00; + let k1 = 0x_0f_0e_0d_0c_0b_0a_09_08; + let mut buf = Vec::new(); + let mut t = 0; + let mut state_inc = SipHasher13::new_with_keys(k0, k1); + + while t < 1 { + let vec = vecs[t]; + let out = hash_with(SipHasher13::new_with_keys(k0, k1), &Bytes(&buf)); + assert_eq!(vec, out[..]); + + let full = hash_with(SipHasher13::new_with_keys(k0, k1), &Bytes(&buf)); + let i = state_inc.finish128().as_bytes(); + + assert_eq!(full, i); + assert_eq!(full, vec); + + buf.push(t as u8); + Hasher::write(&mut state_inc, &[t as u8]); + + t += 1; + } +} + +#[test] +#[allow(unused_must_use)] +fn test_siphash128_2_4() { + let vecs: [[u8; 16]; 1] = [[ + 163, 129, 127, 4, 186, 37, 168, 230, 109, 246, 114, 20, 199, 85, 2, 147, + ]]; + + let k0 = 0x_07_06_05_04_03_02_01_00; + let k1 = 0x_0f_0e_0d_0c_0b_0a_09_08; + let mut buf = Vec::new(); + let mut t = 0; + let mut state_inc = SipHasher24::new_with_keys(k0, k1); + + while t < 1 { + let vec = vecs[t]; + let out = hash_with(SipHasher24::new_with_keys(k0, k1), &Bytes(&buf)); + assert_eq!(vec, out[..]); + + let full = hash_with(SipHasher24::new_with_keys(k0, k1), &Bytes(&buf)); + let i = state_inc.finish128().as_bytes(); + + assert_eq!(full, i); + assert_eq!(full, vec); + + buf.push(t as u8); + Hasher::write(&mut state_inc, &[t as u8]); + + t += 1; + } +} + +#[test] +fn test_siphash128_simple() { + let array: &[u8] = &[1, 2, 3]; + let key: &[u8; 16] = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]; + let hasher = SipHasher13::new_with_key(key); + let h = hasher.hash(array).as_bytes(); + _ = h; +} + +#[test] +fn test_siphash128_incremental() { + let array1: &[u8] = &[1, 2, 3]; + let array2: &[u8] = &[4, 5, 6]; + let key: &[u8; 16] = &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]; + let mut hasher = SipHasher13::new_with_key(key); + hasher.write(array1); + hasher.write(array2); + let h = hasher.finish128().as_bytes(); + _ = h; +} + +#[test] +#[cfg(all(feature = "serde", feature = "serde_json"))] +fn test_siphash128_serde() { + let val64 = 0xdead_beef_dead_beef_u64; + let hash = hash(&val64); + let serialized = serde_json::to_string(&hash).unwrap(); + let deserialized: [u8; 16] = serde_json::from_str(&serialized).unwrap(); + assert_eq!(hash, deserialized); +} |