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    /// True if the bloom filter contains a log with given address and topics.
206    ///
207    /// Note: This method may return false positives. This is inherent to the
208    /// bloom filter data structure.
209    pub fn contains_raw_log(&self, address: Address, topics: &[B256]) -> bool {
210        let mut bloom = Self::default();
211        bloom.accrue_raw_log(address, topics);
212        self.contains(&bloom)
213    }
214
215    /// True if the bloom filter contains a log with given address and topics.
216    ///
217    /// Note: This method may return false positives. This is inherent to the
218    /// bloom filter data structure.
219    pub fn contains_log(&self, log: &Log) -> bool {
220        self.contains_raw_log(log.address, log.topics())
221    }
222}
223
224#[cfg(test)]
225mod tests {
226    use super::*;
227    use crate::hex;
228
229    #[test]
230    fn works() {
231        let bloom = bloom!(
232            "00000000000000000000000000000000
233             00000000100000000000000000000000
234             00000000000000000000000000000000
235             00000000000000000000000000000000
236             00000000000000000000000000000000
237             00000000000000000000000000000000
238             00000002020000000000000000000000
239             00000000000000000000000800000000
240             10000000000000000000000000000000
241             00000000000000000000001000000000
242             00000000000000000000000000000000
243             00000000000000000000000000000000
244             00000000000000000000000000000000
245             00000000000000000000000000000000
246             00000000000000000000000000000000
247             00000000000000000000000000000000"
248        );
249        let address = hex!("ef2d6d194084c2de36e0dabfce45d046b37d1106");
250        let topic = hex!("02c69be41d0b7e40352fc85be1cd65eb03d40ef8427a0ca4596b1ead9a00e9fc");
251
252        let mut my_bloom = Bloom::default();
253        assert!(!my_bloom.contains_input(BloomInput::Raw(&address)));
254        assert!(!my_bloom.contains_input(BloomInput::Raw(&topic)));
255
256        my_bloom.accrue(BloomInput::Raw(&address));
257        assert!(my_bloom.contains_input(BloomInput::Raw(&address)));
258        assert!(!my_bloom.contains_input(BloomInput::Raw(&topic)));
259
260        my_bloom.accrue(BloomInput::Raw(&topic));
261        assert!(my_bloom.contains_input(BloomInput::Raw(&address)));
262        assert!(my_bloom.contains_input(BloomInput::Raw(&topic)));
263
264        assert_eq!(my_bloom, bloom);
265    }
266}
alloy_primitives/bits/bloom.rs

alloy_primitives/bits/
bloom.rs
