bitcoin/
bip158.rs

1// SPDX-License-Identifier: CC0-1.0
2
3// This module was largely copied from https://github.com/rust-bitcoin/murmel/blob/master/src/blockfilter.rs
4// on 11. June 2019 which is licensed under Apache, that file specifically
5// was written entirely by Tamas Blummer, who is re-licensing its contents here as CC0.
6
7//! BIP 158 Compact Block Filters for Light Clients.
8//!
9//! This module implements a structure for compact filters on block data, for
10//! use in the BIP 157 light client protocol. The filter construction proposed
11//! is an alternative to Bloom filters, as used in BIP 37, that minimizes filter
12//! size by using Golomb-Rice coding for compression.
13//!
14//! ### Relevant BIPS
15//!
16//! * [BIP 157 - Client Side Block Filtering](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki)
17//! * [BIP 158 - Compact Block Filters for Light Clients](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki)
18//!
19//! # Examples
20//!
21//! ```ignore
22//! fn get_script_for_coin(coin: &OutPoint) -> Result<ScriptBuf, BlockFilterError> {
23//!   // get utxo ...
24//! }
25//!
26//! // create a block filter for a block (server side)
27//! let filter = BlockFilter::new_script_filter(&block, get_script_for_coin)?;
28//!
29//! // or create a filter from known raw data
30//! let filter = BlockFilter::new(content);
31//!
32//! // read and evaluate a filter
33//!
34//! let query: Iterator<Item=ScriptBuf> = // .. some scripts you care about
35//! if filter.match_any(&block_hash, &mut query.map(|s| s.as_bytes())) {
36//!   // get this block
37//! }
38//!  ```
39//!
40
41use core::cmp::{self, Ordering};
42use core::fmt::{self, Display, Formatter};
43
44use hashes::{sha256d, siphash24, Hash};
45use internals::write_err;
46use io::{Read, Write};
47
48use crate::blockdata::block::{Block, BlockHash};
49use crate::blockdata::script::Script;
50use crate::blockdata::transaction::OutPoint;
51use crate::consensus::encode::VarInt;
52use crate::consensus::{Decodable, Encodable};
53use crate::internal_macros::impl_hashencode;
54use crate::prelude::*;
55
56/// Golomb encoding parameter as in BIP-158, see also https://gist.github.com/sipa/576d5f09c3b86c3b1b75598d799fc845
57const P: u8 = 19;
58const M: u64 = 784931;
59
60hashes::hash_newtype! {
61    /// Filter hash, as defined in BIP-157
62    pub struct FilterHash(sha256d::Hash);
63    /// Filter header, as defined in BIP-157
64    pub struct FilterHeader(sha256d::Hash);
65}
66
67impl_hashencode!(FilterHash);
68impl_hashencode!(FilterHeader);
69
70/// Errors for blockfilter.
71#[derive(Debug)]
72#[non_exhaustive]
73pub enum Error {
74    /// Missing UTXO, cannot calculate script filter.
75    UtxoMissing(OutPoint),
76    /// IO error reading or writing binary serialization of the filter.
77    Io(io::Error),
78}
79
80internals::impl_from_infallible!(Error);
81
82impl Display for Error {
83    fn fmt(&self, f: &mut Formatter) -> Result<(), fmt::Error> {
84        use Error::*;
85
86        match *self {
87            UtxoMissing(ref coin) => write!(f, "unresolved UTXO {}", coin),
88            Io(ref e) => write_err!(f, "IO error"; e),
89        }
90    }
91}
92
93#[cfg(feature = "std")]
94impl std::error::Error for Error {
95    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
96        use Error::*;
97
98        match *self {
99            UtxoMissing(_) => None,
100            Io(ref e) => Some(e),
101        }
102    }
103}
104
105impl From<io::Error> for Error {
106    fn from(io: io::Error) -> Self { Error::Io(io) }
107}
108
109/// A block filter, as described by BIP 158.
110#[derive(Debug, Clone, PartialEq, Eq)]
111pub struct BlockFilter {
112    /// Golomb encoded filter
113    pub content: Vec<u8>,
114}
115
116impl FilterHash {
117    /// Computes the filter header from a filter hash and previous filter header.
118    pub fn filter_header(&self, previous_filter_header: &FilterHeader) -> FilterHeader {
119        let mut header_data = [0u8; 64];
120        header_data[0..32].copy_from_slice(&self[..]);
121        header_data[32..64].copy_from_slice(&previous_filter_header[..]);
122        FilterHeader::hash(&header_data)
123    }
124}
125
126impl BlockFilter {
127    /// Creates a new filter from pre-computed data.
128    pub fn new(content: &[u8]) -> BlockFilter { BlockFilter { content: content.to_vec() } }
129
130    /// Computes a SCRIPT_FILTER that contains spent and output scripts.
131    pub fn new_script_filter<M, S>(block: &Block, script_for_coin: M) -> Result<BlockFilter, Error>
132    where
133        M: Fn(&OutPoint) -> Result<S, Error>,
134        S: Borrow<Script>,
135    {
136        let mut out = Vec::new();
137        let mut writer = BlockFilterWriter::new(&mut out, block);
138
139        writer.add_output_scripts();
140        writer.add_input_scripts(script_for_coin)?;
141        writer.finish()?;
142
143        Ok(BlockFilter { content: out })
144    }
145
146    /// Computes this filter's ID in a chain of filters (see [BIP 157]).
147    ///
148    /// [BIP 157]: <https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki#Filter_Headers>
149    pub fn filter_header(&self, previous_filter_header: &FilterHeader) -> FilterHeader {
150        let filter_hash = FilterHash::hash(self.content.as_slice());
151        filter_hash.filter_header(previous_filter_header)
152    }
153
154    /// Returns true if any query matches against this [`BlockFilter`].
155    pub fn match_any<I>(&self, block_hash: &BlockHash, query: I) -> Result<bool, Error>
156    where
157        I: Iterator,
158        I::Item: Borrow<[u8]>,
159    {
160        let filter_reader = BlockFilterReader::new(block_hash);
161        filter_reader.match_any(&mut self.content.as_slice(), query)
162    }
163
164    /// Returns true if all queries match against this [`BlockFilter`].
165    pub fn match_all<I>(&self, block_hash: &BlockHash, query: I) -> Result<bool, Error>
166    where
167        I: Iterator,
168        I::Item: Borrow<[u8]>,
169    {
170        let filter_reader = BlockFilterReader::new(block_hash);
171        filter_reader.match_all(&mut self.content.as_slice(), query)
172    }
173}
174
175/// Compiles and writes a block filter.
176pub struct BlockFilterWriter<'a, W> {
177    block: &'a Block,
178    writer: GcsFilterWriter<'a, W>,
179}
180
181impl<'a, W: Write> BlockFilterWriter<'a, W> {
182    /// Creates a new [`BlockFilterWriter`] from `block`.
183    pub fn new(writer: &'a mut W, block: &'a Block) -> BlockFilterWriter<'a, W> {
184        let block_hash_as_int = block.block_hash().to_byte_array();
185        let k0 = u64::from_le_bytes(block_hash_as_int[0..8].try_into().expect("8 byte slice"));
186        let k1 = u64::from_le_bytes(block_hash_as_int[8..16].try_into().expect("8 byte slice"));
187        let writer = GcsFilterWriter::new(writer, k0, k1, M, P);
188        BlockFilterWriter { block, writer }
189    }
190
191    /// Adds output scripts of the block to filter (excluding OP_RETURN scripts).
192    pub fn add_output_scripts(&mut self) {
193        for transaction in &self.block.txdata {
194            for output in &transaction.output {
195                if !output.script_pubkey.is_op_return() {
196                    self.add_element(output.script_pubkey.as_bytes());
197                }
198            }
199        }
200    }
201
202    /// Adds consumed output scripts of a block to filter.
203    pub fn add_input_scripts<M, S>(&mut self, script_for_coin: M) -> Result<(), Error>
204    where
205        M: Fn(&OutPoint) -> Result<S, Error>,
206        S: Borrow<Script>,
207    {
208        for script in self
209            .block
210            .txdata
211            .iter()
212            .skip(1) // skip coinbase
213            .flat_map(|t| t.input.iter().map(|i| &i.previous_output))
214            .map(script_for_coin)
215        {
216            match script {
217                Ok(script) => self.add_element(script.borrow().as_bytes()),
218                Err(e) => return Err(e),
219            }
220        }
221        Ok(())
222    }
223
224    /// Adds an arbitrary element to filter.
225    pub fn add_element(&mut self, data: &[u8]) { self.writer.add_element(data); }
226
227    /// Writes the block filter.
228    pub fn finish(&mut self) -> Result<usize, io::Error> { self.writer.finish() }
229}
230
231/// Reads and interprets a block filter.
232pub struct BlockFilterReader {
233    reader: GcsFilterReader,
234}
235
236impl BlockFilterReader {
237    /// Creates a new [`BlockFilterReader`] from `block_hash`.
238    pub fn new(block_hash: &BlockHash) -> BlockFilterReader {
239        let block_hash_as_int = block_hash.to_byte_array();
240        let k0 = u64::from_le_bytes(block_hash_as_int[0..8].try_into().expect("8 byte slice"));
241        let k1 = u64::from_le_bytes(block_hash_as_int[8..16].try_into().expect("8 byte slice"));
242        BlockFilterReader { reader: GcsFilterReader::new(k0, k1, M, P) }
243    }
244
245    /// Returns true if any query matches against this [`BlockFilterReader`].
246    pub fn match_any<I, R>(&self, reader: &mut R, query: I) -> Result<bool, Error>
247    where
248        I: Iterator,
249        I::Item: Borrow<[u8]>,
250        R: Read + ?Sized,
251    {
252        self.reader.match_any(reader, query)
253    }
254
255    /// Returns true if all queries match against this [`BlockFilterReader`].
256    pub fn match_all<I, R>(&self, reader: &mut R, query: I) -> Result<bool, Error>
257    where
258        I: Iterator,
259        I::Item: Borrow<[u8]>,
260        R: Read + ?Sized,
261    {
262        self.reader.match_all(reader, query)
263    }
264}
265
266/// Golomb-Rice encoded filter reader.
267pub struct GcsFilterReader {
268    filter: GcsFilter,
269    m: u64,
270}
271
272impl GcsFilterReader {
273    /// Creates a new [`GcsFilterReader`] with specific seed to siphash.
274    pub fn new(k0: u64, k1: u64, m: u64, p: u8) -> GcsFilterReader {
275        GcsFilterReader { filter: GcsFilter::new(k0, k1, p), m }
276    }
277
278    /// Returns true if any query matches against this [`GcsFilterReader`].
279    pub fn match_any<I, R>(&self, reader: &mut R, query: I) -> Result<bool, Error>
280    where
281        I: Iterator,
282        I::Item: Borrow<[u8]>,
283        R: Read + ?Sized,
284    {
285        let n_elements: VarInt = Decodable::consensus_decode(reader).unwrap_or(VarInt(0));
286        // map hashes to [0, n_elements << grp]
287        let nm = n_elements.0 * self.m;
288        let mut mapped =
289            query.map(|e| map_to_range(self.filter.hash(e.borrow()), nm)).collect::<Vec<_>>();
290        // sort
291        mapped.sort_unstable();
292        if mapped.is_empty() {
293            return Ok(true);
294        }
295        if n_elements.0 == 0 {
296            return Ok(false);
297        }
298
299        // find first match in two sorted arrays in one read pass
300        let mut reader = BitStreamReader::new(reader);
301        let mut data = self.filter.golomb_rice_decode(&mut reader)?;
302        let mut remaining = n_elements.0 - 1;
303        for p in mapped {
304            loop {
305                match data.cmp(&p) {
306                    Ordering::Equal => return Ok(true),
307                    Ordering::Less =>
308                        if remaining > 0 {
309                            data += self.filter.golomb_rice_decode(&mut reader)?;
310                            remaining -= 1;
311                        } else {
312                            return Ok(false);
313                        },
314                    Ordering::Greater => break,
315                }
316            }
317        }
318        Ok(false)
319    }
320
321    /// Returns true if all queries match against this [`GcsFilterReader`].
322    pub fn match_all<I, R>(&self, reader: &mut R, query: I) -> Result<bool, Error>
323    where
324        I: Iterator,
325        I::Item: Borrow<[u8]>,
326        R: Read + ?Sized,
327    {
328        let n_elements: VarInt = Decodable::consensus_decode(reader).unwrap_or(VarInt(0));
329        // map hashes to [0, n_elements << grp]
330        let nm = n_elements.0 * self.m;
331        let mut mapped =
332            query.map(|e| map_to_range(self.filter.hash(e.borrow()), nm)).collect::<Vec<_>>();
333        // sort
334        mapped.sort_unstable();
335        mapped.dedup();
336        if mapped.is_empty() {
337            return Ok(true);
338        }
339        if n_elements.0 == 0 {
340            return Ok(false);
341        }
342
343        // figure if all mapped are there in one read pass
344        let mut reader = BitStreamReader::new(reader);
345        let mut data = self.filter.golomb_rice_decode(&mut reader)?;
346        let mut remaining = n_elements.0 - 1;
347        for p in mapped {
348            loop {
349                match data.cmp(&p) {
350                    Ordering::Equal => break,
351                    Ordering::Less =>
352                        if remaining > 0 {
353                            data += self.filter.golomb_rice_decode(&mut reader)?;
354                            remaining -= 1;
355                        } else {
356                            return Ok(false);
357                        },
358                    Ordering::Greater => return Ok(false),
359                }
360            }
361        }
362        Ok(true)
363    }
364}
365
366/// Fast reduction of hash to [0, nm) range.
367fn map_to_range(hash: u64, nm: u64) -> u64 { ((hash as u128 * nm as u128) >> 64) as u64 }
368
369/// Golomb-Rice encoded filter writer.
370pub struct GcsFilterWriter<'a, W> {
371    filter: GcsFilter,
372    writer: &'a mut W,
373    elements: BTreeSet<Vec<u8>>,
374    m: u64,
375}
376
377impl<'a, W: Write> GcsFilterWriter<'a, W> {
378    /// Creates a new [`GcsFilterWriter`] wrapping a generic writer, with specific seed to siphash.
379    pub fn new(writer: &'a mut W, k0: u64, k1: u64, m: u64, p: u8) -> GcsFilterWriter<'a, W> {
380        GcsFilterWriter { filter: GcsFilter::new(k0, k1, p), writer, elements: BTreeSet::new(), m }
381    }
382
383    /// Adds data to the filter.
384    pub fn add_element(&mut self, element: &[u8]) {
385        if !element.is_empty() {
386            self.elements.insert(element.to_vec());
387        }
388    }
389
390    /// Writes the filter to the wrapped writer.
391    pub fn finish(&mut self) -> Result<usize, io::Error> {
392        let nm = self.elements.len() as u64 * self.m;
393
394        // map hashes to [0, n_elements * M)
395        let mut mapped: Vec<_> = self
396            .elements
397            .iter()
398            .map(|e| map_to_range(self.filter.hash(e.as_slice()), nm))
399            .collect();
400        mapped.sort_unstable();
401
402        // write number of elements as varint
403        let mut wrote = VarInt::from(mapped.len()).consensus_encode(self.writer)?;
404
405        // write out deltas of sorted values into a Golonb-Rice coded bit stream
406        let mut writer = BitStreamWriter::new(self.writer);
407        let mut last = 0;
408        for data in mapped {
409            wrote += self.filter.golomb_rice_encode(&mut writer, data - last)?;
410            last = data;
411        }
412        wrote += writer.flush()?;
413        Ok(wrote)
414    }
415}
416
417/// Golomb Coded Set Filter.
418struct GcsFilter {
419    k0: u64, // sip hash key
420    k1: u64, // sip hash key
421    p: u8,
422}
423
424impl GcsFilter {
425    /// Creates a new [`GcsFilter`].
426    fn new(k0: u64, k1: u64, p: u8) -> GcsFilter { GcsFilter { k0, k1, p } }
427
428    /// Golomb-Rice encodes a number `n` to a bit stream (parameter 2^k).
429    fn golomb_rice_encode<W>(
430        &self,
431        writer: &mut BitStreamWriter<'_, W>,
432        n: u64,
433    ) -> Result<usize, io::Error>
434    where
435        W: Write,
436    {
437        let mut wrote = 0;
438        let mut q = n >> self.p;
439        while q > 0 {
440            let nbits = cmp::min(q, 64);
441            wrote += writer.write(!0u64, nbits as u8)?;
442            q -= nbits;
443        }
444        wrote += writer.write(0, 1)?;
445        wrote += writer.write(n, self.p)?;
446        Ok(wrote)
447    }
448
449    /// Golomb-Rice decodes a number from a bit stream (parameter 2^k).
450    fn golomb_rice_decode<R>(&self, reader: &mut BitStreamReader<R>) -> Result<u64, io::Error>
451    where
452        R: Read + ?Sized,
453    {
454        let mut q = 0u64;
455        while reader.read(1)? == 1 {
456            q += 1;
457        }
458        let r = reader.read(self.p)?;
459        Ok((q << self.p) + r)
460    }
461
462    /// Hashes an arbitrary slice with siphash using parameters of this filter.
463    fn hash(&self, element: &[u8]) -> u64 {
464        siphash24::Hash::hash_to_u64_with_keys(self.k0, self.k1, element)
465    }
466}
467
468/// Bitwise stream reader.
469pub struct BitStreamReader<'a, R: ?Sized> {
470    buffer: [u8; 1],
471    offset: u8,
472    reader: &'a mut R,
473}
474
475impl<'a, R: Read + ?Sized> BitStreamReader<'a, R> {
476    /// Creates a new [`BitStreamReader`] that reads bitwise from a given `reader`.
477    pub fn new(reader: &'a mut R) -> BitStreamReader<'a, R> {
478        BitStreamReader { buffer: [0u8], reader, offset: 8 }
479    }
480
481    /// Reads nbit bits, returning the bits in a `u64` starting with the rightmost bit.
482    ///
483    /// # Examples
484    /// ```
485    /// # use bitcoin::bip158::BitStreamReader;
486    /// # let data = vec![0xff];
487    /// # let mut input = data.as_slice();
488    /// let mut reader = BitStreamReader::new(&mut input); // input contains all 1's
489    /// let res = reader.read(1).expect("read failed");
490    /// assert_eq!(res, 1_u64);
491    /// ```
492    pub fn read(&mut self, mut nbits: u8) -> Result<u64, io::Error> {
493        if nbits > 64 {
494            return Err(io::Error::new(
495                io::ErrorKind::Other,
496                "can not read more than 64 bits at once",
497            ));
498        }
499        let mut data = 0u64;
500        while nbits > 0 {
501            if self.offset == 8 {
502                self.reader.read_exact(&mut self.buffer)?;
503                self.offset = 0;
504            }
505            let bits = cmp::min(8 - self.offset, nbits);
506            data <<= bits;
507            data |= ((self.buffer[0] << self.offset) >> (8 - bits)) as u64;
508            self.offset += bits;
509            nbits -= bits;
510        }
511        Ok(data)
512    }
513}
514
515/// Bitwise stream writer.
516pub struct BitStreamWriter<'a, W> {
517    buffer: [u8; 1],
518    offset: u8,
519    writer: &'a mut W,
520}
521
522impl<'a, W: Write> BitStreamWriter<'a, W> {
523    /// Creates a new [`BitStreamWriter`] that writes bitwise to a given `writer`.
524    pub fn new(writer: &'a mut W) -> BitStreamWriter<'a, W> {
525        BitStreamWriter { buffer: [0u8], writer, offset: 0 }
526    }
527
528    /// Writes nbits bits from data.
529    pub fn write(&mut self, data: u64, mut nbits: u8) -> Result<usize, io::Error> {
530        if nbits > 64 {
531            return Err(io::Error::new(
532                io::ErrorKind::Other,
533                "can not write more than 64 bits at once",
534            ));
535        }
536        let mut wrote = 0;
537        while nbits > 0 {
538            let bits = cmp::min(8 - self.offset, nbits);
539            self.buffer[0] |= ((data << (64 - nbits)) >> (64 - 8 + self.offset)) as u8;
540            self.offset += bits;
541            nbits -= bits;
542            if self.offset == 8 {
543                wrote += self.flush()?;
544            }
545        }
546        Ok(wrote)
547    }
548
549    /// flush bits not yet written.
550    pub fn flush(&mut self) -> Result<usize, io::Error> {
551        if self.offset > 0 {
552            self.writer.write_all(&self.buffer)?;
553            self.buffer[0] = 0u8;
554            self.offset = 0;
555            Ok(1)
556        } else {
557            Ok(0)
558        }
559    }
560}
561
562#[cfg(test)]
563mod test {
564    use std::collections::HashMap;
565
566    use hex::test_hex_unwrap as hex;
567    use serde_json::Value;
568
569    use super::*;
570    use crate::consensus::encode::deserialize;
571    use crate::ScriptBuf;
572
573    #[test]
574    fn test_blockfilters() {
575        // test vectors from: https://github.com/jimpo/bitcoin/blob/c7efb652f3543b001b4dd22186a354605b14f47e/src/test/data/blockfilters.json
576        let data = include_str!("../tests/data/blockfilters.json");
577
578        let testdata = serde_json::from_str::<Value>(data).unwrap().as_array().unwrap().clone();
579        for t in testdata.iter().skip(1) {
580            let block_hash = t.get(1).unwrap().as_str().unwrap().parse::<BlockHash>().unwrap();
581            let block: Block = deserialize(&hex!(t.get(2).unwrap().as_str().unwrap())).unwrap();
582            assert_eq!(block.block_hash(), block_hash);
583            let scripts = t.get(3).unwrap().as_array().unwrap();
584            let previous_filter_header =
585                t.get(4).unwrap().as_str().unwrap().parse::<FilterHeader>().unwrap();
586            let filter_content = hex!(t.get(5).unwrap().as_str().unwrap());
587            let filter_header =
588                t.get(6).unwrap().as_str().unwrap().parse::<FilterHeader>().unwrap();
589
590            let mut txmap = HashMap::new();
591            let mut si = scripts.iter();
592            for tx in block.txdata.iter().skip(1) {
593                for input in tx.input.iter() {
594                    txmap.insert(
595                        input.previous_output,
596                        ScriptBuf::from(hex!(si.next().unwrap().as_str().unwrap())),
597                    );
598                }
599            }
600
601            let filter = BlockFilter::new_script_filter(&block, |o| {
602                if let Some(s) = txmap.get(o) {
603                    Ok(s.clone())
604                } else {
605                    Err(Error::UtxoMissing(*o))
606                }
607            })
608            .unwrap();
609
610            let test_filter = BlockFilter::new(filter_content.as_slice());
611
612            assert_eq!(test_filter.content, filter.content);
613
614            let block_hash = &block.block_hash();
615            assert!(filter
616                .match_all(
617                    block_hash,
618                    &mut txmap.iter().filter_map(|(_, s)| if !s.is_empty() {
619                        Some(s.as_bytes())
620                    } else {
621                        None
622                    })
623                )
624                .unwrap());
625
626            for script in txmap.values() {
627                let query = [script];
628                if !script.is_empty() {
629                    assert!(filter
630                        .match_any(block_hash, &mut query.iter().map(|s| s.as_bytes()))
631                        .unwrap());
632                }
633            }
634
635            assert_eq!(filter_header, filter.filter_header(&previous_filter_header));
636        }
637    }
638
639    #[test]
640    fn test_filter() {
641        let mut patterns = BTreeSet::new();
642
643        patterns.insert(hex!("000000"));
644        patterns.insert(hex!("111111"));
645        patterns.insert(hex!("222222"));
646        patterns.insert(hex!("333333"));
647        patterns.insert(hex!("444444"));
648        patterns.insert(hex!("555555"));
649        patterns.insert(hex!("666666"));
650        patterns.insert(hex!("777777"));
651        patterns.insert(hex!("888888"));
652        patterns.insert(hex!("999999"));
653        patterns.insert(hex!("aaaaaa"));
654        patterns.insert(hex!("bbbbbb"));
655        patterns.insert(hex!("cccccc"));
656        patterns.insert(hex!("dddddd"));
657        patterns.insert(hex!("eeeeee"));
658        patterns.insert(hex!("ffffff"));
659
660        let mut out = Vec::new();
661        {
662            let mut writer = GcsFilterWriter::new(&mut out, 0, 0, M, P);
663            for p in &patterns {
664                writer.add_element(p.as_slice());
665            }
666            writer.finish().unwrap();
667        }
668
669        let bytes = out;
670
671        {
672            let query = [hex!("abcdef"), hex!("eeeeee")];
673            let reader = GcsFilterReader::new(0, 0, M, P);
674            assert!(reader
675                .match_any(&mut bytes.as_slice(), &mut query.iter().map(|v| v.as_slice()))
676                .unwrap());
677        }
678        {
679            let query = [hex!("abcdef"), hex!("123456")];
680            let reader = GcsFilterReader::new(0, 0, M, P);
681            assert!(!reader
682                .match_any(&mut bytes.as_slice(), &mut query.iter().map(|v| v.as_slice()))
683                .unwrap());
684        }
685        {
686            let reader = GcsFilterReader::new(0, 0, M, P);
687            let mut query = Vec::new();
688            for p in &patterns {
689                query.push(p.clone());
690            }
691            assert!(reader
692                .match_all(&mut bytes.as_slice(), &mut query.iter().map(|v| v.as_slice()))
693                .unwrap());
694        }
695        {
696            let reader = GcsFilterReader::new(0, 0, M, P);
697            let mut query = Vec::new();
698            for p in &patterns {
699                query.push(p.clone());
700            }
701            query.push(hex!("abcdef"));
702            assert!(!reader
703                .match_all(&mut bytes.as_slice(), &mut query.iter().map(|v| v.as_slice()))
704                .unwrap());
705        }
706    }
707
708    #[test]
709    fn test_bit_stream() {
710        let mut out = Vec::new();
711        {
712            let mut writer = BitStreamWriter::new(&mut out);
713            writer.write(0, 1).unwrap(); // 0
714            writer.write(2, 2).unwrap(); // 10
715            writer.write(6, 3).unwrap(); // 110
716            writer.write(11, 4).unwrap(); // 1011
717            writer.write(1, 5).unwrap(); // 00001
718            writer.write(32, 6).unwrap(); // 100000
719            writer.write(7, 7).unwrap(); // 0000111
720            writer.flush().unwrap();
721        }
722        let bytes = out;
723        assert_eq!(
724            "01011010110000110000000001110000",
725            format!("{:08b}{:08b}{:08b}{:08b}", bytes[0], bytes[1], bytes[2], bytes[3])
726        );
727        {
728            let mut input = bytes.as_slice();
729            let mut reader = BitStreamReader::new(&mut input);
730            assert_eq!(reader.read(1).unwrap(), 0);
731            assert_eq!(reader.read(2).unwrap(), 2);
732            assert_eq!(reader.read(3).unwrap(), 6);
733            assert_eq!(reader.read(4).unwrap(), 11);
734            assert_eq!(reader.read(5).unwrap(), 1);
735            assert_eq!(reader.read(6).unwrap(), 32);
736            assert_eq!(reader.read(7).unwrap(), 7);
737            // 4 bits remained
738            assert!(reader.read(5).is_err());
739        }
740    }
741}
bitcoin/bip158.rs

bitcoin/
bip158.rs
