alloy_primitives/bits/
bloom.rs

1//! Bloom type.
2//!
3//! Adapted from <https://github.com/paritytech/parity-common/blob/2fb72eea96b6de4a085144ce239feb49da0cd39e/ethbloom/src/lib.rs>
4
5use crate::{keccak256, Address, Log, LogData, B256};
6
7/// Number of bits to set per input in Ethereum bloom filter.
8pub const BLOOM_BITS_PER_ITEM: usize = 3;
9/// Size of the bloom filter in bytes.
10pub const BLOOM_SIZE_BYTES: usize = 256;
11/// Size of the bloom filter in bits
12pub const BLOOM_SIZE_BITS: usize = BLOOM_SIZE_BYTES * 8;
13
14/// Mask, used in accrue
15const MASK: usize = BLOOM_SIZE_BITS - 1;
16/// Number of bytes per item, used in accrue
17const ITEM_BYTES: usize = BLOOM_SIZE_BITS.ilog2().div_ceil(8) as usize;
18
19// BLOOM_SIZE_BYTES must be a power of 2
20#[allow(clippy::assertions_on_constants)]
21const _: () = assert!(BLOOM_SIZE_BYTES.is_power_of_two());
22
23/// Input to the [`Bloom::accrue`] method.
24#[derive(Clone, Copy, Debug)]
25pub enum BloomInput<'a> {
26    /// Raw input to be hashed.
27    Raw(&'a [u8]),
28    /// Already hashed input.
29    Hash(B256),
30}
31
32impl BloomInput<'_> {
33    /// Consume the input, converting it to the hash.
34    #[inline]
35    pub fn into_hash(self) -> B256 {
36        match self {
37            BloomInput::Raw(raw) => keccak256(raw),
38            BloomInput::Hash(hash) => hash,
39        }
40    }
41}
42
43impl From<BloomInput<'_>> for Bloom {
44    #[inline]
45    fn from(input: BloomInput<'_>) -> Self {
46        let mut bloom = Self::ZERO;
47        bloom.accrue(input);
48        bloom
49    }
50}
51
52wrap_fixed_bytes!(
53    /// Ethereum 256 byte bloom filter.
54    pub struct Bloom<256>;
55);
56
57impl<'a> FromIterator<&'a (Address, LogData)> for Bloom {
58    fn from_iter<T: IntoIterator<Item = &'a (Address, LogData)>>(iter: T) -> Self {
59        let mut bloom = Self::ZERO;
60        bloom.extend(iter);
61        bloom
62    }
63}
64
65impl<'a> Extend<&'a (Address, LogData)> for Bloom {
66    fn extend<T: IntoIterator<Item = &'a (Address, LogData)>>(&mut self, iter: T) {
67        for (address, log_data) in iter {
68            self.accrue_raw_log(*address, log_data.topics())
69        }
70    }
71}
72
73impl<'a> FromIterator<&'a Log> for Bloom {
74    #[inline]
75    fn from_iter<T: IntoIterator<Item = &'a Log>>(logs: T) -> Self {
76        let mut bloom = Self::ZERO;
77        bloom.extend(logs);
78        bloom
79    }
80}
81
82impl<'a> Extend<&'a Log> for Bloom {
83    #[inline]
84    fn extend<T: IntoIterator<Item = &'a Log>>(&mut self, logs: T) {
85        for log in logs {
86            self.accrue_log(log)
87        }
88    }
89}
90
91impl<'a, 'b> FromIterator<&'a BloomInput<'b>> for Bloom {
92    #[inline]
93    fn from_iter<T: IntoIterator<Item = &'a BloomInput<'b>>>(inputs: T) -> Self {
94        let mut bloom = Self::ZERO;
95        bloom.extend(inputs);
96        bloom
97    }
98}
99
100impl<'a, 'b> Extend<&'a BloomInput<'b>> for Bloom {
101    #[inline]
102    fn extend<T: IntoIterator<Item = &'a BloomInput<'b>>>(&mut self, inputs: T) {
103        for input in inputs {
104            self.accrue(*input);
105        }
106    }
107}
108
109impl Bloom {
110    /// Returns a reference to the underlying data.
111    #[inline]
112    pub const fn data(&self) -> &[u8; BLOOM_SIZE_BYTES] {
113        &self.0 .0
114    }
115
116    /// Returns a mutable reference to the underlying data.
117    #[inline]
118    pub fn data_mut(&mut self) -> &mut [u8; BLOOM_SIZE_BYTES] {
119        &mut self.0 .0
120    }
121
122    /// Returns true if this bloom filter is a possible superset of the other
123    /// bloom filter, admitting false positives.
124    ///
125    /// Note: This method may return false positives. This is inherent to the
126    /// bloom filter data structure.
127    #[inline]
128    pub fn contains_input(&self, input: BloomInput<'_>) -> bool {
129        self.contains(&input.into())
130    }
131
132    /// Compile-time version of [`contains`](Self::contains).
133    ///
134    /// Note: This method may return false positives. This is inherent to the
135    /// bloom filter data structure.
136    pub const fn const_contains(self, other: Self) -> bool {
137        self.0.const_covers(other.0)
138    }
139
140    /// Returns true if this bloom filter is a possible superset of the other
141    /// bloom filter, admitting false positives.
142    ///
143    /// Note: This method may return false positives. This is inherent to the
144    /// bloom filter data structure.
145    pub fn contains(&self, other: &Self) -> bool {
146        self.0.covers(&other.0)
147    }
148
149    /// Accrues the input into the bloom filter.
150    pub fn accrue(&mut self, input: BloomInput<'_>) {
151        let hash = input.into_hash();
152
153        let mut ptr = 0;
154
155        for _ in 0..3 {
156            let mut index = 0_usize;
157            for _ in 0..ITEM_BYTES {
158                index = (index << 8) | hash[ptr] as usize;
159                ptr += 1;
160            }
161            index &= MASK;
162            self.0[BLOOM_SIZE_BYTES - 1 - index / 8] |= 1 << (index % 8);
163        }
164    }
165
166    /// Accrues the input into the bloom filter.
167    pub fn accrue_bloom(&mut self, bloom: &Self) {
168        *self |= *bloom;
169    }
170
171    /// Specialised Bloom filter that sets three bits out of 2048, given an
172    /// arbitrary byte sequence.
173    ///
174    /// See Section 4.3.1 "Transaction Receipt" of the
175    /// [Ethereum Yellow Paper][ref] (page 6).
176    ///
177    /// [ref]: https://ethereum.github.io/yellowpaper/paper.pdf
178    pub fn m3_2048(&mut self, bytes: &[u8]) {
179        self.m3_2048_hashed(&keccak256(bytes));
180    }
181
182    /// [`m3_2048`](Self::m3_2048) but with a pre-hashed input.
183    pub fn m3_2048_hashed(&mut self, hash: &B256) {
184        for i in [0, 2, 4] {
185            let bit = (hash[i + 1] as usize + ((hash[i] as usize) << 8)) & 0x7FF;
186            self[BLOOM_SIZE_BYTES - 1 - bit / 8] |= 1 << (bit % 8);
187        }
188    }
189
190    /// Ingests a raw log into the bloom filter.
191    pub fn accrue_raw_log(&mut self, address: Address, topics: &[B256]) {
192        self.m3_2048(address.as_slice());
193        for topic in topics.iter() {
194            self.m3_2048(topic.as_slice());
195        }
196    }
197
198    /// Ingests a log into the bloom filter.
199    pub fn accrue_log(&mut self, log: &Log) {
200        self.accrue_raw_log(log.address, log.topics())
201    }
202
203    /// True if the bloom filter contains a log with given address and topics.
204    ///
205    /// Note: This method may return false positives. This is inherent to the
206    /// bloom filter data structure.
207    pub fn contains_raw_log(&self, address: Address, topics: &[B256]) -> bool {
208        let mut bloom = Self::default();
209        bloom.accrue_raw_log(address, topics);
210        self.contains(&bloom)
211    }
212
213    /// True if the bloom filter contains a log with given address and topics.
214    ///
215    /// Note: This method may return false positives. This is inherent to the
216    /// bloom filter data structure.
217    pub fn contains_log(&self, log: &Log) -> bool {
218        self.contains_raw_log(log.address, log.topics())
219    }
220}
221
222#[cfg(test)]
223mod tests {
224    use super::*;
225    use crate::hex;
226
227    #[test]
228    fn works() {
229        let bloom = bloom!(
230            "00000000000000000000000000000000
231             00000000100000000000000000000000
232             00000000000000000000000000000000
233             00000000000000000000000000000000
234             00000000000000000000000000000000
235             00000000000000000000000000000000
236             00000002020000000000000000000000
237             00000000000000000000000800000000
238             10000000000000000000000000000000
239             00000000000000000000001000000000
240             00000000000000000000000000000000
241             00000000000000000000000000000000
242             00000000000000000000000000000000
243             00000000000000000000000000000000
244             00000000000000000000000000000000
245             00000000000000000000000000000000"
246        );
247        let address = hex!("ef2d6d194084c2de36e0dabfce45d046b37d1106");
248        let topic = hex!("02c69be41d0b7e40352fc85be1cd65eb03d40ef8427a0ca4596b1ead9a00e9fc");
249
250        let mut my_bloom = Bloom::default();
251        assert!(!my_bloom.contains_input(BloomInput::Raw(&address)));
252        assert!(!my_bloom.contains_input(BloomInput::Raw(&topic)));
253
254        my_bloom.accrue(BloomInput::Raw(&address));
255        assert!(my_bloom.contains_input(BloomInput::Raw(&address)));
256        assert!(!my_bloom.contains_input(BloomInput::Raw(&topic)));
257
258        my_bloom.accrue(BloomInput::Raw(&topic));
259        assert!(my_bloom.contains_input(BloomInput::Raw(&address)));
260        assert!(my_bloom.contains_input(BloomInput::Raw(&topic)));
261
262        assert_eq!(my_bloom, bloom);
263    }
264}
alloy_primitives/bits/bloom.rs

alloy_primitives/bits/
bloom.rs
