sbloom/
lib.rs

1//! 
2//! ```rust
3//! extern crate sbloom;
4//! extern crate rustc_hex;
5//! use rustc_hex::FromHex;
6//! use sbloom::{Bloom, Input};
7//!
8//! fn main() {
9//! 	let bloom: Bloom = "00000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002020000000000000000000000000000000000000000000008000000001000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000".into();
10//! 	let address = "ef2d6d194084c2de36e0dabfce45d046b37d1106".from_hex().unwrap();
11//! 	let topic = "02c69be41d0b7e40352fc85be1cd65eb03d40ef8427a0ca4596b1ead9a00e9fc".from_hex().unwrap();
12//! 	
13//! 	let mut my_bloom = Bloom::default();
14//! 	assert!(!my_bloom.contains_input(Input::Raw(&address)));
15//! 	assert!(!my_bloom.contains_input(Input::Raw(&topic)));
16//!
17//! 	my_bloom.accrue(Input::Raw(&address));
18//! 	assert!(my_bloom.contains_input(Input::Raw(&address)));
19//! 	assert!(!my_bloom.contains_input(Input::Raw(&topic)));
20//! 	
21//! 	my_bloom.accrue(Input::Raw(&topic));
22//! 	assert!(my_bloom.contains_input(Input::Raw(&address)));
23//! 	assert!(my_bloom.contains_input(Input::Raw(&topic)));
24//! 	assert_eq!(my_bloom, bloom);
25//! 	}
26//! ```
27//!
28
29#![cfg_attr(not(feature="std"), no_std)]
30
31#[cfg(feature="std")]
32extern crate core;
33
34extern crate tiny_keccak;
35#[macro_use]
36extern crate crunchy;
37
38#[macro_use]
39extern crate fixed_hash;
40
41#[cfg(feature="serialize")]
42extern crate s_types_serialize;
43
44#[cfg(feature="serialize")]
45extern crate serde;
46
47#[cfg(feature="serialize")]
48use serde::{Serialize, Serializer, Deserialize, Deserializer};
49
50use core::{ops, mem};
51use tiny_keccak::keccak256;
52
53#[cfg(feature="std")]
54use core::str;
55
56// 3 according to yellowpaper
57const BLOOM_BITS: u32 = 3;
58const BLOOM_SIZE: usize = 256;
59
60construct_hash!(Bloom, BLOOM_SIZE);
61
62/// Returns log2.
63fn log2(x: usize) -> u32 {
64	if x <= 1 {
65		return 0;
66	}
67
68	let n = x.leading_zeros();
69	mem::size_of::<usize>() as u32 * 8 - n
70}
71
72pub enum Input<'a> {
73	Raw(&'a [u8]),
74	Hash(&'a [u8; 32]),
75}
76
77enum Hash<'a> {
78	Ref(&'a [u8; 32]),
79	Owned([u8; 32]),
80}
81
82impl<'a> From<Input<'a>> for Hash<'a> {
83	fn from(input: Input<'a>) -> Self {
84		match input {
85			Input::Raw(raw) => Hash::Owned(keccak256(raw)),
86			Input::Hash(hash) => Hash::Ref(hash),
87		}
88	}
89}
90
91impl<'a> ops::Index<usize> for Hash<'a> {
92	type Output = u8;
93
94	fn index(&self, index: usize) -> &u8 {
95		match *self {
96			Hash::Ref(r) => &r[index],
97			Hash::Owned(ref hash) => &hash[index],
98		}
99	}
100}
101
102impl<'a> Hash<'a> {
103	fn len(&self) -> usize {
104		match *self {
105			Hash::Ref(r) => r.len(),
106			Hash::Owned(ref hash) => hash.len(),
107		}
108	}
109}
110
111impl<'a> PartialEq<BloomRef<'a>> for Bloom {
112	fn eq(&self, other: &BloomRef<'a>) -> bool {
113		let s_ref: &[u8] = &self.0;
114		let o_ref: &[u8] = other.0;
115		s_ref.eq(o_ref)
116	}
117}
118
119impl<'a> From<Input<'a>> for Bloom {
120	fn from(input: Input<'a>) -> Bloom {
121		let mut bloom = Bloom::default();
122		bloom.accrue(input);
123		bloom
124	}
125}
126
127impl Bloom {
128	pub fn is_empty(&self) -> bool {
129		self.0.iter().all(|x| *x == 0)
130	}
131
132	pub fn contains_input<'a>(&self, input: Input<'a>) -> bool {
133		let bloom: Bloom = input.into();
134		self.contains_bloom(&bloom)
135	}
136
137	pub fn contains_bloom<'a, B>(&self, bloom: B) -> bool where BloomRef<'a>: From<B> {
138		let bloom_ref: BloomRef = bloom.into();
139		// workaround for https://github.com/rust-lang/rust/issues/43644
140		self.contains_bloom_ref(bloom_ref)
141	}
142
143	fn contains_bloom_ref(&self, bloom: BloomRef) -> bool {
144		let self_ref: BloomRef = self.into();
145		self_ref.contains_bloom(bloom)
146	}
147
148	pub fn accrue<'a>(&mut self, input: Input<'a>) {
149		let p = BLOOM_BITS;
150
151		let m = self.0.len();
152		let bloom_bits = m * 8;
153		let mask = bloom_bits - 1;
154		let bloom_bytes = (log2(bloom_bits) + 7) / 8;
155
156		let hash: Hash = input.into();
157
158		// must be a power of 2
159		assert_eq!(m & (m - 1), 0);
160		// out of range
161		assert!(p * bloom_bytes <= hash.len() as u32);
162
163		let mut ptr = 0;
164
165		assert_eq!(BLOOM_BITS, 3);
166		unroll! {
167			for i in 0..3 {
168				let _ = i;
169				let mut index = 0 as usize;
170				for _ in 0..bloom_bytes {
171					index = (index << 8) | hash[ptr] as usize;
172					ptr += 1;
173				}
174				index &= mask;
175				self.0[m - 1 - index / 8] |= 1 << (index % 8);
176			}
177		}
178	}
179
180	pub fn accrue_bloom<'a, B>(&mut self, bloom: B) where BloomRef<'a>: From<B> {
181		let bloom_ref: BloomRef = bloom.into();
182		assert_eq!(self.0.len(), BLOOM_SIZE);
183		assert_eq!(bloom_ref.0.len(), BLOOM_SIZE);
184		for i in 0..BLOOM_SIZE {
185			self.0[i] |= bloom_ref.0[i];
186		}
187	}
188
189	pub fn data(&self) -> &[u8; BLOOM_SIZE] {
190		&self.0
191	}
192}
193
194#[derive(Clone, Copy)]
195pub struct BloomRef<'a>(&'a [u8; BLOOM_SIZE]);
196
197impl<'a> BloomRef<'a> {
198	pub fn is_empty(&self) -> bool {
199		self.0.iter().all(|x| *x == 0)
200	}
201
202	pub fn contains_input<'b>(&self, input: Input<'b>) -> bool {
203		let bloom: Bloom = input.into();
204		self.contains_bloom(&bloom)
205	}
206	
207	pub fn contains_bloom<'b, B>(&self, bloom: B) -> bool where BloomRef<'b>: From<B> {
208		let bloom_ref: BloomRef = bloom.into();
209		assert_eq!(self.0.len(), BLOOM_SIZE);
210		assert_eq!(bloom_ref.0.len(), BLOOM_SIZE);
211		for i in 0..BLOOM_SIZE {
212			let a = self.0[i];
213			let b = bloom_ref.0[i];
214			if (a & b) != b {
215				return false;
216			}
217		}
218		true
219	}
220
221	pub fn data(&self) -> &'a [u8; BLOOM_SIZE] {
222		self.0
223	}
224}
225
226impl<'a> From<&'a [u8; BLOOM_SIZE]> for BloomRef<'a> {
227	fn from(data: &'a [u8; BLOOM_SIZE]) -> Self {
228		BloomRef(data)
229	}
230}
231
232impl<'a> From<&'a Bloom> for BloomRef<'a> {
233	fn from(bloom: &'a Bloom) -> Self {
234		BloomRef(&bloom.0)
235	}
236}
237
238#[cfg(feature="serialize")]
239impl Serialize for Bloom {
240	fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> where S: Serializer {
241		let mut slice = [0u8; 2 + 2 * BLOOM_SIZE];
242		s_types_serialize::serialize(&mut slice, &self.0, serializer)
243	}
244}
245
246#[cfg(feature="serialize")]
247impl<'de> Deserialize<'de> for Bloom {
248	fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> where D: Deserializer<'de> {
249		let mut bytes = [0; BLOOM_SIZE];
250		s_types_serialize::deserialize_check_len(deserializer, s_types_serialize::ExpectedLen::Exact(&mut bytes))?;
251		Ok(Bloom(bytes))
252	}
253}
254
255#[cfg(test)]
256mod tests {
257	extern crate rustc_hex;
258	use self::rustc_hex::FromHex;
259	use {Bloom, Input};
260
261	#[test]
262	fn it_works() {
263		let bloom: Bloom = "00000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002020000000000000000000000000000000000000000000008000000001000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000".into();
264		let address = "ef2d6d194084c2de36e0dabfce45d046b37d1106".from_hex().unwrap();
265		let topic = "02c69be41d0b7e40352fc85be1cd65eb03d40ef8427a0ca4596b1ead9a00e9fc".from_hex().unwrap();
266
267		let mut my_bloom = Bloom::default();
268		assert!(!my_bloom.contains_input(Input::Raw(&address)));
269		assert!(!my_bloom.contains_input(Input::Raw(&topic)));
270
271		my_bloom.accrue(Input::Raw(&address));
272		assert!(my_bloom.contains_input(Input::Raw(&address)));
273		assert!(!my_bloom.contains_input(Input::Raw(&topic)));
274
275		my_bloom.accrue(Input::Raw(&topic));
276		assert!(my_bloom.contains_input(Input::Raw(&address)));
277		assert!(my_bloom.contains_input(Input::Raw(&topic)));
278		assert_eq!(my_bloom, bloom);
279	}
280}
sbloom/lib.rs

sbloom/
lib.rs
