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::{Address, B256, Log, LogData, keccak256};
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    #[cfg_attr(feature = "rkyv", derive(rkyv::Archive, rkyv::Serialize, rkyv::Deserialize))]
55    #[cfg_attr(feature = "rkyv", rkyv(derive(Copy, Clone, Hash, PartialEq, Eq)))]
56    pub struct Bloom<256>;
57);
58
59impl<'a> FromIterator<&'a (Address, LogData)> for Bloom {
60    fn from_iter<T: IntoIterator<Item = &'a (Address, LogData)>>(iter: T) -> Self {
61        let mut bloom = Self::ZERO;
62        bloom.extend(iter);
63        bloom
64    }
65}
66
67impl<'a> Extend<&'a (Address, LogData)> for Bloom {
68    fn extend<T: IntoIterator<Item = &'a (Address, LogData)>>(&mut self, iter: T) {
69        for (address, log_data) in iter {
70            self.accrue_raw_log(*address, log_data.topics())
71        }
72    }
73}
74
75impl<'a> FromIterator<&'a Log> for Bloom {
76    #[inline]
77    fn from_iter<T: IntoIterator<Item = &'a Log>>(logs: T) -> Self {
78        let mut bloom = Self::ZERO;
79        bloom.extend(logs);
80        bloom
81    }
82}
83
84impl<'a> Extend<&'a Log> for Bloom {
85    #[inline]
86    fn extend<T: IntoIterator<Item = &'a Log>>(&mut self, logs: T) {
87        for log in logs {
88            self.accrue_log(log)
89        }
90    }
91}
92
93impl<'a, 'b> FromIterator<&'a BloomInput<'b>> for Bloom {
94    #[inline]
95    fn from_iter<T: IntoIterator<Item = &'a BloomInput<'b>>>(inputs: T) -> Self {
96        let mut bloom = Self::ZERO;
97        bloom.extend(inputs);
98        bloom
99    }
100}
101
102impl<'a, 'b> Extend<&'a BloomInput<'b>> for Bloom {
103    #[inline]
104    fn extend<T: IntoIterator<Item = &'a BloomInput<'b>>>(&mut self, inputs: T) {
105        for input in inputs {
106            self.accrue(*input);
107        }
108    }
109}
110
111impl Bloom {
112    /// Returns a reference to the underlying data.
113    #[inline]
114    pub const fn data(&self) -> &[u8; BLOOM_SIZE_BYTES] {
115        &self.0.0
116    }
117
118    /// Returns a mutable reference to the underlying data.
119    #[inline]
120    pub const fn data_mut(&mut self) -> &mut [u8; BLOOM_SIZE_BYTES] {
121        &mut self.0.0
122    }
123
124    /// Returns true if this bloom filter is a possible superset of the other
125    /// bloom filter, admitting false positives.
126    ///
127    /// Note: This method may return false positives. This is inherent to the
128    /// bloom filter data structure.
129    #[inline]
130    pub fn contains_input(&self, input: BloomInput<'_>) -> bool {
131        self.contains(&input.into())
132    }
133
134    /// Compile-time version of [`contains`](Self::contains).
135    ///
136    /// Note: This method may return false positives. This is inherent to the
137    /// bloom filter data structure.
138    pub const fn const_contains(self, other: Self) -> bool {
139        self.0.const_covers(other.0)
140    }
141
142    /// Returns true if this bloom filter is a possible superset of the other
143    /// bloom filter, admitting false positives.
144    ///
145    /// Note: This method may return false positives. This is inherent to the
146    /// bloom filter data structure.
147    pub fn contains(&self, other: &Self) -> bool {
148        self.0.covers(&other.0)
149    }
150
151    /// Accrues the input into the bloom filter.
152    pub fn accrue(&mut self, input: BloomInput<'_>) {
153        let hash = input.into_hash();
154
155        let mut ptr = 0;
156
157        for _ in 0..3 {
158            let mut index = 0_usize;
159            for _ in 0..ITEM_BYTES {
160                index = (index << 8) | hash[ptr] as usize;
161                ptr += 1;
162            }
163            index &= MASK;
164            self.0[BLOOM_SIZE_BYTES - 1 - index / 8] |= 1 << (index % 8);
165        }
166    }
167
168    /// Accrues the input into the bloom filter.
169    pub fn accrue_bloom(&mut self, bloom: &Self) {
170        *self |= *bloom;
171    }
172
173    /// Specialised Bloom filter that sets three bits out of 2048, given an
174    /// arbitrary byte sequence.
175    ///
176    /// See Section 4.3.1 "Transaction Receipt" of the
177    /// [Ethereum Yellow Paper][ref] (page 6).
178    ///
179    /// [ref]: https://ethereum.github.io/yellowpaper/paper.pdf
180    pub fn m3_2048(&mut self, bytes: &[u8]) {
181        self.m3_2048_hashed(&keccak256(bytes));
182    }
183
184    /// [`m3_2048`](Self::m3_2048) but with a pre-hashed input.
185    pub fn m3_2048_hashed(&mut self, hash: &B256) {
186        for i in [0, 2, 4] {
187            let bit = (hash[i + 1] as usize + ((hash[i] as usize) << 8)) & 0x7FF;
188            self[BLOOM_SIZE_BYTES - 1 - bit / 8] |= 1 << (bit % 8);
189        }
190    }
191
192    /// Ingests a raw log into the bloom filter.
193    pub fn accrue_raw_log(&mut self, address: Address, topics: &[B256]) {
194        self.m3_2048(address.as_slice());
195        for topic in topics.iter() {
196            self.m3_2048(topic.as_slice());
197        }
198    }
199
200    /// Ingests a log into the bloom filter.
201    pub fn accrue_log(&mut self, log: &Log) {
202        self.accrue_raw_log(log.address, log.topics())
203    }
204
205    /// Ingests multiple logs into the bloom filter.
206    pub fn accrue_logs(&mut self, logs: &[Log]) {
207        for log in logs {
208            self.accrue_log(log)
209        }
210    }
211
212    /// True if the bloom filter contains a log with given address and topics.
213    ///
214    /// Note: This method may return false positives. This is inherent to the
215    /// bloom filter data structure.
216    pub fn contains_raw_log(&self, address: Address, topics: &[B256]) -> bool {
217        let mut bloom = Self::default();
218        bloom.accrue_raw_log(address, topics);
219        self.contains(&bloom)
220    }
221
222    /// True if the bloom filter contains a log with given address and topics.
223    ///
224    /// Note: This method may return false positives. This is inherent to the
225    /// bloom filter data structure.
226    pub fn contains_log(&self, log: &Log) -> bool {
227        self.contains_raw_log(log.address, log.topics())
228    }
229}
230
231#[cfg(test)]
232mod tests {
233    use super::*;
234    use crate::hex;
235
236    #[test]
237    fn works() {
238        let bloom = bloom!(
239            "00000000000000000000000000000000
240             00000000100000000000000000000000
241             00000000000000000000000000000000
242             00000000000000000000000000000000
243             00000000000000000000000000000000
244             00000000000000000000000000000000
245             00000002020000000000000000000000
246             00000000000000000000000800000000
247             10000000000000000000000000000000
248             00000000000000000000001000000000
249             00000000000000000000000000000000
250             00000000000000000000000000000000
251             00000000000000000000000000000000
252             00000000000000000000000000000000
253             00000000000000000000000000000000
254             00000000000000000000000000000000"
255        );
256        let address = hex!("ef2d6d194084c2de36e0dabfce45d046b37d1106");
257        let topic = hex!("02c69be41d0b7e40352fc85be1cd65eb03d40ef8427a0ca4596b1ead9a00e9fc");
258
259        let mut my_bloom = Bloom::default();
260        assert!(!my_bloom.contains_input(BloomInput::Raw(&address)));
261        assert!(!my_bloom.contains_input(BloomInput::Raw(&topic)));
262
263        my_bloom.accrue(BloomInput::Raw(&address));
264        assert!(my_bloom.contains_input(BloomInput::Raw(&address)));
265        assert!(!my_bloom.contains_input(BloomInput::Raw(&topic)));
266
267        my_bloom.accrue(BloomInput::Raw(&topic));
268        assert!(my_bloom.contains_input(BloomInput::Raw(&address)));
269        assert!(my_bloom.contains_input(BloomInput::Raw(&topic)));
270
271        assert_eq!(my_bloom, bloom);
272    }
273}
alloy_primitives/bits/bloom.rs

alloy_primitives/bits/
bloom.rs
