vapbloom/
lib.rs

1// Copyright 2020 Parity Technologies
2//
3// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
4// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
5// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
6// option. This file may not be copied, modified, or distributed
7// except according to those terms.
8
9//!
10//! ```
11//! use hex_literal::hex;
12//! use vapbloom::{Bloom, Input};
13//!
14//! use std::str::FromStr;
15//! let bloom = Bloom::from_str(
16//! 	"00000000000000000000000000000000\
17//! 	00000000100000000000000000000000\
18//! 	00000000000000000000000000000000\
19//! 	00000000000000000000000000000000\
20//! 	00000000000000000000000000000000\
21//! 	00000000000000000000000000000000\
22//! 	00000002020000000000000000000000\
23//! 	00000000000000000000000800000000\
24//! 	10000000000000000000000000000000\
25//! 	00000000000000000000001000000000\
26//! 	00000000000000000000000000000000\
27//! 	00000000000000000000000000000000\
28//! 	00000000000000000000000000000000\
29//! 	00000000000000000000000000000000\
30//! 	00000000000000000000000000000000\
31//! 	00000000000000000000000000000000"
32//! ).unwrap();
33//! let address = hex!("ef2d6d194084c2de36e0dabfce45d046b37d1106");
34//! let topic = hex!("02c69be41d0b7e40352fc85be1cd65eb03d40ef8427a0ca4596b1ead9a00e9fc");
35//!
36//! let mut my_bloom = Bloom::default();
37//! assert!(!my_bloom.contains_input(Input::Raw(&address)));
38//! assert!(!my_bloom.contains_input(Input::Raw(&topic)));
39//!
40//! my_bloom.accrue(Input::Raw(&address));
41//! assert!(my_bloom.contains_input(Input::Raw(&address)));
42//! assert!(!my_bloom.contains_input(Input::Raw(&topic)));
43//!
44//! my_bloom.accrue(Input::Raw(&topic));
45//! assert!(my_bloom.contains_input(Input::Raw(&address)));
46//! assert!(my_bloom.contains_input(Input::Raw(&topic)));
47//! assert_eq!(my_bloom, bloom);
48//! ```
49//!
50
51#![cfg_attr(not(feature = "std"), no_std)]
52
53use core::{mem, ops};
54
55use crunchy::unroll;
56use tetsy_fixed_hash::*;
57#[cfg(feature = "codec")]
58use tetsy_impl_codec::impl_fixed_hash_codec;
59#[cfg(feature = "tetsy-rlp")]
60use tetsy_impl_rlp::impl_fixed_hash_rlp;
61#[cfg(feature = "serialize")]
62use tetsy_impl_serde::impl_fixed_hash_serde;
63use tiny_keccak::{Hasher, Keccak};
64
65// 3 according to yellowpaper
66const BLOOM_BITS: u32 = 3;
67const BLOOM_SIZE: usize = 256;
68
69construct_fixed_hash! {
70	/// Bloom hash type with 256 bytes (2048 bits) size.
71	pub struct Bloom(BLOOM_SIZE);
72}
73#[cfg(feature = "tetsy-rlp")]
74impl_fixed_hash_rlp!(Bloom, BLOOM_SIZE);
75#[cfg(feature = "serialize")]
76impl_fixed_hash_serde!(Bloom, BLOOM_SIZE);
77#[cfg(feature = "codec")]
78impl_fixed_hash_codec!(Bloom, BLOOM_SIZE);
79
80/// Returns log2.
81fn log2(x: usize) -> u32 {
82	if x <= 1 {
83		return 0;
84	}
85
86	let n = x.leading_zeros();
87	mem::size_of::<usize>() as u32 * 8 - n
88}
89
90pub enum Input<'a> {
91	Raw(&'a [u8]),
92	Hash(&'a [u8; 32]),
93}
94
95enum Hash<'a> {
96	Ref(&'a [u8; 32]),
97	Owned([u8; 32]),
98}
99
100impl<'a> From<Input<'a>> for Hash<'a> {
101	fn from(input: Input<'a>) -> Self {
102		match input {
103			Input::Raw(raw) => {
104				let mut out = [0u8; 32];
105				let mut keccak256 = Keccak::v256();
106				keccak256.update(raw);
107				keccak256.finalize(&mut out);
108				Hash::Owned(out)
109			}
110			Input::Hash(hash) => Hash::Ref(hash),
111		}
112	}
113}
114
115impl<'a> ops::Index<usize> for Hash<'a> {
116	type Output = u8;
117
118	fn index(&self, index: usize) -> &u8 {
119		match *self {
120			Hash::Ref(r) => &r[index],
121			Hash::Owned(ref hash) => &hash[index],
122		}
123	}
124}
125
126impl<'a> Hash<'a> {
127	fn len(&self) -> usize {
128		match *self {
129			Hash::Ref(r) => r.len(),
130			Hash::Owned(ref hash) => hash.len(),
131		}
132	}
133}
134
135impl<'a> PartialEq<BloomRef<'a>> for Bloom {
136	fn eq(&self, other: &BloomRef<'a>) -> bool {
137		let s_ref: &[u8] = &self.0;
138		let o_ref: &[u8] = other.0;
139		s_ref.eq(o_ref)
140	}
141}
142
143impl<'a> From<Input<'a>> for Bloom {
144	fn from(input: Input<'a>) -> Bloom {
145		let mut bloom = Bloom::default();
146		bloom.accrue(input);
147		bloom
148	}
149}
150
151impl Bloom {
152	pub fn is_empty(&self) -> bool {
153		self.0.iter().all(|x| *x == 0)
154	}
155
156	pub fn contains_input(&self, input: Input<'_>) -> bool {
157		let bloom: Bloom = input.into();
158		self.contains_bloom(&bloom)
159	}
160
161	pub fn contains_bloom<'a, B>(&self, bloom: B) -> bool
162	where
163		BloomRef<'a>: From<B>,
164	{
165		let bloom_ref: BloomRef<'_> = bloom.into();
166		// workaround for https://github.com/rust-lang/rust/issues/43644
167		self.contains_bloom_ref(bloom_ref)
168	}
169
170	fn contains_bloom_ref(&self, bloom: BloomRef<'_>) -> bool {
171		let self_ref: BloomRef<'_> = self.into();
172		self_ref.contains_bloom(bloom)
173	}
174
175	pub fn accrue(&mut self, input: Input<'_>) {
176		let p = BLOOM_BITS;
177
178		let m = self.0.len();
179		let bloom_bits = m * 8;
180		let mask = bloom_bits - 1;
181		let bloom_bytes = (log2(bloom_bits) + 7) / 8;
182
183		let hash: Hash<'_> = input.into();
184
185		// must be a power of 2
186		assert_eq!(m & (m - 1), 0);
187		// out of range
188		assert!(p * bloom_bytes <= hash.len() as u32);
189
190		let mut ptr = 0;
191
192		assert_eq!(BLOOM_BITS, 3);
193		unroll! {
194			for i in 0..3 {
195				let _ = i;
196				let mut index = 0 as usize;
197				for _ in 0..bloom_bytes {
198					index = (index << 8) | hash[ptr] as usize;
199					ptr += 1;
200				}
201				index &= mask;
202				self.0[m - 1 - index / 8] |= 1 << (index % 8);
203			}
204		}
205	}
206
207	pub fn accrue_bloom<'a, B>(&mut self, bloom: B)
208	where
209		BloomRef<'a>: From<B>,
210	{
211		let bloom_ref: BloomRef<'_> = bloom.into();
212		assert_eq!(self.0.len(), BLOOM_SIZE);
213		assert_eq!(bloom_ref.0.len(), BLOOM_SIZE);
214		for i in 0..BLOOM_SIZE {
215			self.0[i] |= bloom_ref.0[i];
216		}
217	}
218
219	pub fn data(&self) -> &[u8; BLOOM_SIZE] {
220		&self.0
221	}
222}
223
224#[derive(Clone, Copy)]
225pub struct BloomRef<'a>(&'a [u8; BLOOM_SIZE]);
226
227impl<'a> BloomRef<'a> {
228	#[allow(clippy::trivially_copy_pass_by_ref)]
229	pub fn is_empty(&self) -> bool {
230		self.0.iter().all(|x| *x == 0)
231	}
232
233	#[allow(clippy::trivially_copy_pass_by_ref)]
234	pub fn contains_input(&self, input: Input<'_>) -> bool {
235		let bloom: Bloom = input.into();
236		self.contains_bloom(&bloom)
237	}
238
239	#[allow(clippy::trivially_copy_pass_by_ref)]
240	pub fn contains_bloom<'b, B>(&self, bloom: B) -> bool
241	where
242		BloomRef<'b>: From<B>,
243	{
244		let bloom_ref: BloomRef<'_> = bloom.into();
245		assert_eq!(self.0.len(), BLOOM_SIZE);
246		assert_eq!(bloom_ref.0.len(), BLOOM_SIZE);
247		for i in 0..BLOOM_SIZE {
248			let a = self.0[i];
249			let b = bloom_ref.0[i];
250			if (a & b) != b {
251				return false;
252			}
253		}
254		true
255	}
256
257	#[allow(clippy::trivially_copy_pass_by_ref)]
258	pub fn data(&self) -> &'a [u8; BLOOM_SIZE] {
259		self.0
260	}
261}
262
263impl<'a> From<&'a [u8; BLOOM_SIZE]> for BloomRef<'a> {
264	fn from(data: &'a [u8; BLOOM_SIZE]) -> Self {
265		BloomRef(data)
266	}
267}
268
269impl<'a> From<&'a Bloom> for BloomRef<'a> {
270	fn from(bloom: &'a Bloom) -> Self {
271		BloomRef(&bloom.0)
272	}
273}
274
275#[cfg(test)]
276mod tests {
277	use super::{Bloom, Input};
278	use core::str::FromStr;
279	use hex_literal::hex;
280
281	#[test]
282	#[rustfmt::skip]
283	fn it_works() {
284		let bloom = Bloom::from_str(
285			"00000000000000000000000000000000\
286			 00000000100000000000000000000000\
287			 00000000000000000000000000000000\
288			 00000000000000000000000000000000\
289			 00000000000000000000000000000000\
290			 00000000000000000000000000000000\
291			 00000002020000000000000000000000\
292			 00000000000000000000000800000000\
293			 10000000000000000000000000000000\
294			 00000000000000000000001000000000\
295			 00000000000000000000000000000000\
296			 00000000000000000000000000000000\
297			 00000000000000000000000000000000\
298			 00000000000000000000000000000000\
299			 00000000000000000000000000000000\
300			 00000000000000000000000000000000",
301		).unwrap();
302		let address = hex!("ef2d6d194084c2de36e0dabfce45d046b37d1106");
303		let topic = hex!("02c69be41d0b7e40352fc85be1cd65eb03d40ef8427a0ca4596b1ead9a00e9fc");
304
305		let mut my_bloom = Bloom::default();
306		assert!(!my_bloom.contains_input(Input::Raw(&address)));
307		assert!(!my_bloom.contains_input(Input::Raw(&topic)));
308
309		my_bloom.accrue(Input::Raw(&address));
310		assert!(my_bloom.contains_input(Input::Raw(&address)));
311		assert!(!my_bloom.contains_input(Input::Raw(&topic)));
312
313		my_bloom.accrue(Input::Raw(&topic));
314		assert!(my_bloom.contains_input(Input::Raw(&address)));
315		assert!(my_bloom.contains_input(Input::Raw(&topic)));
316		assert_eq!(my_bloom, bloom);
317	}
318}
vapbloom/lib.rs

vapbloom/
lib.rs
