safe_mix/
lib.rs

1// Copyright 2017 Parity Technologies (UK) Ltd.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Means of mixing a series of hashes to create a single secure hash.
16//!
17//! Described in http://www.cs.huji.ac.il/~nati/PAPERS/coll_coin_fl.pdf
18
19#![cfg_attr(not(feature = "std"), no_std)]
20
21#[cfg(feature = "std")]
22use std::ops::{BitAnd, BitOr};
23
24#[cfg(not(feature = "std"))]
25use core::ops::{BitAnd, BitOr};
26
27pub const MAX_DEPTH: usize = 17;
28
29fn sub_mix<T>(seeds: &[T]) -> T where
30	T: BitAnd<Output = T> + BitOr<Output = T> + Copy
31{
32	(seeds[0] & seeds[1]) | (seeds[1] & seeds[2]) | (seeds[0] & seeds[2])
33}
34
35/// Mix a slice.
36pub fn triplet_mix<T>(seeds: &[T]) -> Result<T, ()> where
37	T: BitAnd<Output = T> + BitOr<Output = T>,
38	T: Default + Copy
39{
40	Ok(seeds.iter().cloned().triplet_mix())
41}
42
43/// The mixed trait for mixing a sequence.
44pub trait TripletMix {
45	/// The items in the sequence and simultaneously the return of the mixing.
46	type Item;
47	/// The output of the mixing algorithm on the sequence. Items in the sequence beyond
48	/// the largest power of three that fits within the the sequence up until `3 ** MAX_DEPTH`
49	/// are ignored.
50	fn triplet_mix(self) -> Self::Item;
51}
52
53impl<I, T> TripletMix for I where
54	I: Iterator<Item = T>,
55	T: BitAnd<Output = T> + BitOr<Output = T> + Default + Copy
56{
57	type Item = T;
58	fn triplet_mix(self) -> Self::Item {
59		let mut accum = [[T::default(); 3]; MAX_DEPTH];
60		let mut result = T::default();
61		for (i, seed) in self.enumerate() {
62			accum[0][i % 3] = seed;
63			let mut index_at_depth = i;
64			for depth in 0..MAX_DEPTH {
65				if index_at_depth % 3 != 2 {
66					break;
67				}
68				index_at_depth /= 3;
69				result = sub_mix(&accum[depth]);
70
71				// end of the threesome at depth.
72				if depth == MAX_DEPTH - 1 {
73					// end of our stack - bail with result.
74					break;
75				} else {
76					// save in the stack for parent computation
77					accum[depth + 1][index_at_depth % 3] = result;
78				}
79			}
80		}
81		result
82	}
83}
84
85#[cfg(test)]
86mod tests {
87	use super::*;
88
89	#[test]
90	fn sub_mix_works() {
91		assert_eq!(sub_mix(&[0, 0, 0][..]), 0);
92		assert_eq!(sub_mix(&[0, 0, 1][..]), 0);
93		assert_eq!(sub_mix(&[0, 1, 0][..]), 0);
94		assert_eq!(sub_mix(&[0, 1, 1][..]), 1);
95		assert_eq!(sub_mix(&[1, 0, 0][..]), 0);
96		assert_eq!(sub_mix(&[1, 0, 1][..]), 1);
97		assert_eq!(sub_mix(&[1, 1, 0][..]), 1);
98		assert_eq!(sub_mix(&[1, 1, 1][..]), 1);
99
100		assert_eq!(sub_mix(&[0, 0, 0][..]), 0);
101		assert_eq!(sub_mix(&[0, 0, 2][..]), 0);
102		assert_eq!(sub_mix(&[0, 2, 0][..]), 0);
103		assert_eq!(sub_mix(&[0, 2, 2][..]), 2);
104		assert_eq!(sub_mix(&[2, 0, 0][..]), 0);
105		assert_eq!(sub_mix(&[2, 0, 2][..]), 2);
106		assert_eq!(sub_mix(&[2, 2, 0][..]), 2);
107		assert_eq!(sub_mix(&[2, 2, 2][..]), 2);
108	}
109
110	#[test]
111	fn triplet_mix_works_on_first_level() {
112		assert_eq!(triplet_mix(&[0, 0, 0][..]).unwrap(), 0);
113		assert_eq!(triplet_mix(&[0, 0, 1][..]).unwrap(), 0);
114		assert_eq!(triplet_mix(&[0, 1, 0][..]).unwrap(), 0);
115		assert_eq!(triplet_mix(&[0, 1, 1][..]).unwrap(), 1);
116		assert_eq!(triplet_mix(&[1, 0, 0][..]).unwrap(), 0);
117		assert_eq!(triplet_mix(&[1, 0, 1][..]).unwrap(), 1);
118		assert_eq!(triplet_mix(&[1, 1, 0][..]).unwrap(), 1);
119		assert_eq!(triplet_mix(&[1, 1, 1][..]).unwrap(), 1);
120
121		assert_eq!(triplet_mix(&[0, 0, 0][..]).unwrap(), 0);
122		assert_eq!(triplet_mix(&[0, 0, 2][..]).unwrap(), 0);
123		assert_eq!(triplet_mix(&[0, 2, 0][..]).unwrap(), 0);
124		assert_eq!(triplet_mix(&[0, 2, 2][..]).unwrap(), 2);
125		assert_eq!(triplet_mix(&[2, 0, 0][..]).unwrap(), 0);
126		assert_eq!(triplet_mix(&[2, 0, 2][..]).unwrap(), 2);
127		assert_eq!(triplet_mix(&[2, 2, 0][..]).unwrap(), 2);
128		assert_eq!(triplet_mix(&[2, 2, 2][..]).unwrap(), 2);
129	}
130
131	#[test]
132	fn triplet_mix_works_on_second_level() {
133		assert_eq!(triplet_mix(&[0, 0, 0, 0, 0, 1, 0, 1, 0][..]).unwrap(), 0);
134		assert_eq!(triplet_mix(&[0, 1, 1, 1, 0, 0, 1, 0, 1][..]).unwrap(), 1);
135		assert_eq!(triplet_mix(&[1, 1, 0, 1, 1, 1, 0, 0, 0][..]).unwrap(), 1);
136	}
137
138	#[test]
139	fn triplet_mix_works_on_third_level() {
140		assert_eq!(triplet_mix(&[0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0][..]).unwrap(), 1);
141	}
142}
safe_mix/lib.rs

safe_mix/
lib.rs
