bitcoin/util/
bip158.rs

1// Rust Bitcoin Library
2// Written in 2019 by
3//   The rust-bitcoin developers
4//
5// To the extent possible under law, the author(s) have dedicated all
6// copyright and related and neighboring rights to this software to
7// the public domain worldwide. This software is distributed without
8// any warranty.
9//
10// You should have received a copy of the CC0 Public Domain Dedication
11// along with this software.
12// If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
13//
14
15// This module was largely copied from https://github.com/rust-bitcoin/murmel/blob/master/src/blockfilter.rs
16// on 11. June 2019 which is licensed under Apache, that file specifically
17// was written entirely by Tamas Blummer, who is re-licensing its contents here as CC0.
18
19//!
20//! # BIP158 Compact Block Filters for Light Clients
21//!
22//! Implements a structure for compact filters on block data, for use in the BIP 157 light client protocol.
23//! The filter construction proposed is an alternative to Bloom filters, as used in BIP 37,
24//! that minimizes filter size by using Golomb-Rice coding for compression.
25//!
26//!  USE :
27//!   // create a block filter for a block (server side)
28//!
29//!   fn get_script_for_coin (coin: &OutPoint) -> Result<Script, BlockFilterError> {
30//!     // get utxo ...
31//!   }
32//!
33//!   let filter = BlockFilter::new_script_filter (&block, get_script_for_coin)?;
34//!
35//!   // or create a filter from known raw data
36//!   let filter = BlockFilter::new(content);
37//!
38//!   // read and evaluate a filter
39//!
40//!   let query: Iterator<Item=Script> = // .. some scripts you care about
41//!   if filter.match_any (&block_hash, &mut query.map(|s| s.as_bytes())) {
42//!     // get this block
43//!   }
44//!
45//!
46
47use std::{cmp, fmt, io};
48use std::collections::HashSet;
49use std::error;
50use std::fmt::{Display, Formatter};
51use std::io::Cursor;
52use std::cmp::Ordering;
53
54
55use hashes::{Hash, siphash24};
56use hash_types::{BlockHash, FilterHash, FilterHeader};
57
58use blockdata::block::Block;
59use blockdata::script::Script;
60use blockdata::transaction::OutPoint;
61use consensus::{Decodable, Encodable};
62use consensus::encode::VarInt;
63use util::endian;
64
65/// Golomb encoding parameter as in BIP-158, see also https://gist.github.com/sipa/576d5f09c3b86c3b1b75598d799fc845
66const P: u8 = 19;
67const M: u64 = 784931;
68
69/// Errors for blockfilter
70#[derive(Debug)]
71pub enum Error {
72    /// missing UTXO, can not calculate script filter
73    UtxoMissing(OutPoint),
74    /// some IO error reading or writing binary serialization of the filter
75    Io(io::Error),
76}
77
78impl error::Error for Error {}
79
80impl Display for Error {
81    fn fmt(&self, f: &mut Formatter) -> Result<(), fmt::Error> {
82        match *self {
83            Error::UtxoMissing(ref coin) => write!(f, "unresolved UTXO {}", coin),
84            Error::Io(ref io) => write!(f, "{}", io)
85        }
86    }
87}
88
89impl From<io::Error> for Error {
90    fn from(io: io::Error) -> Self {
91        Error::Io(io)
92    }
93}
94
95
96/// a computed or read block filter
97#[derive(Debug, Clone, PartialEq, Eq)]
98pub struct BlockFilter {
99    /// Golomb encoded filter
100    pub content: Vec<u8>
101}
102
103impl FilterHash {
104    /// compute the filter header from a filter hash and previous filter header
105    pub fn filter_header(&self, previous_filter_header: &FilterHeader) -> FilterHeader {
106        let mut header_data = [0u8; 64];
107        header_data[0..32].copy_from_slice(&self[..]);
108        header_data[32..64].copy_from_slice(&previous_filter_header[..]);
109        FilterHeader::hash(&header_data)
110    }
111}
112
113impl BlockFilter {
114    /// compute this filter's id in a chain of filters
115    pub fn filter_header(&self, previous_filter_header: &FilterHeader) -> FilterHeader {
116        let filter_hash = FilterHash::hash(self.content.as_slice());
117        filter_hash.filter_header(previous_filter_header)
118    }
119
120    /// create a new filter from pre-computed data
121    pub fn new (content: &[u8]) -> BlockFilter {
122        BlockFilter { content: content.to_vec() }
123    }
124
125    /// Compute a SCRIPT_FILTER that contains spent and output scripts
126    pub fn new_script_filter<M>(block: &Block, script_for_coin: M) -> Result<BlockFilter, Error>
127        where M: Fn(&OutPoint) -> Result<Script, Error> {
128        let mut out = Cursor::new(Vec::new());
129        {
130            let mut writer = BlockFilterWriter::new(&mut out, block);
131            writer.add_output_scripts();
132            writer.add_input_scripts(script_for_coin)?;
133            writer.finish()?;
134        }
135        Ok(BlockFilter { content: out.into_inner() })
136    }
137
138    /// match any query pattern
139    pub fn match_any(&self, block_hash: &BlockHash, query: &mut dyn Iterator<Item=&[u8]>) -> Result<bool, Error> {
140        let filter_reader = BlockFilterReader::new(block_hash);
141        filter_reader.match_any(&mut Cursor::new(self.content.as_slice()), query)
142    }
143
144    /// match all query pattern
145    pub fn match_all(&self, block_hash: &BlockHash, query: &mut dyn Iterator<Item=&[u8]>) -> Result<bool, Error> {
146        let filter_reader = BlockFilterReader::new(block_hash);
147        filter_reader.match_all(&mut Cursor::new(self.content.as_slice()), query)
148    }
149}
150
151/// Compiles and writes a block filter
152pub struct BlockFilterWriter<'a> {
153    block: &'a Block,
154    writer: GCSFilterWriter<'a>,
155}
156
157impl<'a> BlockFilterWriter<'a> {
158    /// Create a block filter writer
159    pub fn new(writer: &'a mut dyn io::Write, block: &'a Block) -> BlockFilterWriter<'a> {
160        let block_hash_as_int = block.block_hash().into_inner();
161        let k0 = endian::slice_to_u64_le(&block_hash_as_int[0..8]);
162        let k1 = endian::slice_to_u64_le(&block_hash_as_int[8..16]);
163        let writer = GCSFilterWriter::new(writer, k0, k1, M, P);
164        BlockFilterWriter { block, writer }
165    }
166
167    /// Add output scripts of the block - excluding OP_RETURN scripts
168    pub fn add_output_scripts(&mut self) {
169        for transaction in &self.block.txdata {
170            for output in &transaction.output {
171                if !output.script_pubkey.is_op_return() {
172                    self.add_element(output.script_pubkey.as_bytes());
173                }
174            }
175        }
176    }
177
178    /// Add consumed output scripts of a block to filter
179    pub fn add_input_scripts<M>(&mut self, script_for_coin: M) -> Result<(), Error>
180        where M: Fn(&OutPoint) -> Result<Script, Error> {
181        for script in self.block.txdata.iter()
182            .skip(1) // skip coinbase
183            .flat_map(|t| t.input.iter().map(|i| &i.previous_output))
184            .map(script_for_coin) {
185            match script {
186                Ok(script) => self.add_element(script.as_bytes()),
187                Err(e) => return Err(e)
188            }
189        }
190        Ok(())
191    }
192
193    /// Add arbitrary element to a filter
194    pub fn add_element(&mut self, data: &[u8]) {
195        self.writer.add_element(data);
196    }
197
198    /// Write block filter
199    pub fn finish(&mut self) -> Result<usize, io::Error> {
200        self.writer.finish()
201    }
202}
203
204
205/// Reads and interpret a block filter
206pub struct BlockFilterReader {
207    reader: GCSFilterReader
208}
209
210impl BlockFilterReader {
211    /// Create a block filter reader
212    pub fn new(block_hash: &BlockHash) -> BlockFilterReader {
213        let block_hash_as_int = block_hash.into_inner();
214        let k0 = endian::slice_to_u64_le(&block_hash_as_int[0..8]);
215        let k1 = endian::slice_to_u64_le(&block_hash_as_int[8..16]);
216        BlockFilterReader { reader: GCSFilterReader::new(k0, k1, M, P) }
217    }
218
219    /// match any query pattern
220    pub fn match_any(&self, reader: &mut dyn io::Read, query: &mut dyn Iterator<Item=&[u8]>) -> Result<bool, Error> {
221        self.reader.match_any(reader, query)
222    }
223
224    /// match all query pattern
225    pub fn match_all(&self, reader: &mut dyn io::Read, query: &mut dyn Iterator<Item=&[u8]>) -> Result<bool, Error> {
226        self.reader.match_all(reader, query)
227    }
228}
229
230
231/// Golomb-Rice encoded filter reader
232pub struct GCSFilterReader {
233    filter: GCSFilter,
234    m: u64
235}
236
237impl GCSFilterReader {
238    /// Create a new filter reader with specific seed to siphash
239    pub fn new(k0: u64, k1: u64, m: u64, p: u8) -> GCSFilterReader {
240        GCSFilterReader { filter: GCSFilter::new(k0, k1, p), m }
241    }
242
243    /// match any query pattern
244    pub fn match_any(&self, reader: &mut dyn io::Read, query: &mut dyn Iterator<Item=&[u8]>) -> Result<bool, Error> {
245        let mut decoder = reader;
246        let n_elements: VarInt = Decodable::consensus_decode(&mut decoder).unwrap_or(VarInt(0));
247        let reader = &mut decoder;
248        // map hashes to [0, n_elements << grp]
249        let nm = n_elements.0 * self.m;
250        let mut mapped = query.map(|e| map_to_range(self.filter.hash(e), nm)).collect::<Vec<_>>();
251        // sort
252        mapped.sort();
253        if mapped.is_empty() {
254            return Ok(true);
255        }
256        if n_elements.0 == 0 {
257            return Ok(false);
258        }
259
260        // find first match in two sorted arrays in one read pass
261        let mut reader = BitStreamReader::new(reader);
262        let mut data = self.filter.golomb_rice_decode(&mut reader)?;
263        let mut remaining = n_elements.0 - 1;
264        for p in mapped {
265            loop {
266                match data.cmp(&p) {
267                    Ordering::Equal => return Ok(true),
268                    Ordering::Less => {
269                        if remaining > 0 {
270                            data += self.filter.golomb_rice_decode(&mut reader)?;
271                            remaining -= 1;
272                        } else {
273                            return Ok(false);
274                        }
275                    }
276                    Ordering::Greater => break,
277                }
278            }
279        }
280        Ok(false)
281    }
282
283    /// match all query pattern
284    pub fn match_all(&self, reader: &mut dyn io::Read, query: &mut dyn Iterator<Item=&[u8]>) -> Result<bool, Error> {
285        let mut decoder = reader;
286        let n_elements: VarInt = Decodable::consensus_decode(&mut decoder).unwrap_or(VarInt(0));
287        let reader = &mut decoder;
288        // map hashes to [0, n_elements << grp]
289        let nm = n_elements.0 * self.m;
290        let mut mapped = query.map(|e| map_to_range(self.filter.hash(e), nm)).collect::<Vec<_>>();
291        // sort
292        mapped.sort();
293        mapped.dedup();
294        if mapped.is_empty() {
295            return Ok(true);
296        }
297        if n_elements.0 == 0 {
298            return Ok(false);
299        }
300
301        // figure if all mapped are there in one read pass
302        let mut reader = BitStreamReader::new(reader);
303        let mut data = self.filter.golomb_rice_decode(&mut reader)?;
304        let mut remaining = n_elements.0 - 1;
305        for p in mapped {
306            loop {
307                match data.cmp(&p) {
308                    Ordering::Equal => break,
309                    Ordering::Less => {
310                        if remaining > 0 {
311                            data += self.filter.golomb_rice_decode(&mut reader)?;
312                            remaining -= 1;
313                        } else {
314                            return Ok(false);
315                        }
316                    },
317                    Ordering::Greater => return Ok(false),
318                }
319            }
320        }
321        Ok(true)
322    }
323}
324
325// fast reduction of hash to [0, nm) range
326fn map_to_range(hash: u64, nm: u64) -> u64 {
327    ((hash as u128 * nm as u128) >> 64) as u64
328}
329
330/// Colomb-Rice encoded filter writer
331pub struct GCSFilterWriter<'a> {
332    filter: GCSFilter,
333    writer: &'a mut dyn io::Write,
334    elements: HashSet<Vec<u8>>,
335    m: u64
336}
337
338impl<'a> GCSFilterWriter<'a> {
339    /// Create a new GCS writer wrapping a generic writer, with specific seed to siphash
340    pub fn new(writer: &'a mut dyn io::Write, k0: u64, k1: u64, m: u64, p: u8) -> GCSFilterWriter<'a> {
341        GCSFilterWriter {
342            filter: GCSFilter::new(k0, k1, p),
343            writer,
344            elements: HashSet::new(),
345            m
346        }
347    }
348
349    /// Add some data to the filter
350    pub fn add_element(&mut self, element: &[u8]) {
351        if !element.is_empty() {
352            self.elements.insert(element.to_vec());
353        }
354    }
355
356    /// write the filter to the wrapped writer
357    pub fn finish(&mut self) -> Result<usize, io::Error> {
358        let nm = self.elements.len() as u64 * self.m;
359
360        // map hashes to [0, n_elements * M)
361        let mut mapped: Vec<_> = self.elements.iter()
362            .map(|e| map_to_range(self.filter.hash(e.as_slice()), nm)).collect();
363        mapped.sort();
364
365        // write number of elements as varint
366        let mut encoder = io::Cursor::new(Vec::new());
367        VarInt(mapped.len() as u64).consensus_encode(&mut encoder).unwrap();
368        let mut wrote = self.writer.write(encoder.into_inner().as_slice())?;
369
370        // write out deltas of sorted values into a Golonb-Rice coded bit stream
371        let mut writer = BitStreamWriter::new(self.writer);
372        let mut last = 0;
373        for data in mapped {
374            wrote += self.filter.golomb_rice_encode(&mut writer, data - last)?;
375            last = data;
376        }
377        wrote += writer.flush()?;
378        Ok(wrote)
379    }
380}
381
382/// Golomb Coded Set Filter
383struct GCSFilter {
384    k0: u64, // sip hash key
385    k1: u64, // sip hash key
386    p: u8
387}
388
389impl GCSFilter {
390    /// Create a new filter
391    fn new(k0: u64, k1: u64, p: u8) -> GCSFilter {
392        GCSFilter { k0, k1, p }
393    }
394
395    /// Golomb-Rice encode a number n to a bit stream (Parameter 2^k)
396    fn golomb_rice_encode(&self, writer: &mut BitStreamWriter, n: u64) -> Result<usize, io::Error> {
397        let mut wrote = 0;
398        let mut q = n >> self.p;
399        while q > 0 {
400            let nbits = cmp::min(q, 64);
401            wrote += writer.write(!0u64, nbits as u8)?;
402            q -= nbits;
403        }
404        wrote += writer.write(0, 1)?;
405        wrote += writer.write(n, self.p)?;
406        Ok(wrote)
407    }
408
409    /// Golomb-Rice decode a number from a bit stream (Parameter 2^k)
410    fn golomb_rice_decode(&self, reader: &mut BitStreamReader) -> Result<u64, io::Error> {
411        let mut q = 0u64;
412        while reader.read(1)? == 1 {
413            q += 1;
414        }
415        let r = reader.read(self.p)?;
416        Ok((q << self.p) + r)
417    }
418
419    /// Hash an arbitrary slice with siphash using parameters of this filter
420    fn hash(&self, element: &[u8]) -> u64 {
421        siphash24::Hash::hash_to_u64_with_keys(self.k0, self.k1, element)
422    }
423}
424
425/// Bitwise stream reader
426pub struct BitStreamReader<'a> {
427    buffer: [u8; 1],
428    offset: u8,
429    reader: &'a mut dyn io::Read,
430}
431
432impl<'a> BitStreamReader<'a> {
433    /// Create a new BitStreamReader that reads bitwise from a given reader
434    pub fn new(reader: &'a mut dyn io::Read) -> BitStreamReader {
435        BitStreamReader {
436            buffer: [0u8],
437            reader: reader,
438            offset: 8,
439        }
440    }
441
442    /// Read nbit bits
443    pub fn read(&mut self, mut nbits: u8) -> Result<u64, io::Error> {
444        if nbits > 64 {
445            return Err(io::Error::new(io::ErrorKind::Other, "can not read more than 64 bits at once"));
446        }
447        let mut data = 0u64;
448        while nbits > 0 {
449            if self.offset == 8 {
450                self.reader.read_exact(&mut self.buffer)?;
451                self.offset = 0;
452            }
453            let bits = cmp::min(8 - self.offset, nbits);
454            data <<= bits;
455            data |= ((self.buffer[0] << self.offset) >> (8 - bits)) as u64;
456            self.offset += bits;
457            nbits -= bits;
458        }
459        Ok(data)
460    }
461}
462
463/// Bitwise stream writer
464pub struct BitStreamWriter<'a> {
465    buffer: [u8; 1],
466    offset: u8,
467    writer: &'a mut dyn io::Write,
468}
469
470impl<'a> BitStreamWriter<'a> {
471    /// Create a new BitStreamWriter that writes bitwise to a given writer
472    pub fn new(writer: &'a mut dyn io::Write) -> BitStreamWriter {
473        BitStreamWriter {
474            buffer: [0u8],
475            writer: writer,
476            offset: 0,
477        }
478    }
479
480    /// Write nbits bits from data
481    pub fn write(&mut self, data: u64, mut nbits: u8) -> Result<usize, io::Error> {
482        if nbits > 64 {
483            return Err(io::Error::new(io::ErrorKind::Other, "can not write more than 64 bits at once"));
484        }
485        let mut wrote = 0;
486        while nbits > 0 {
487            let bits = cmp::min(8 - self.offset, nbits);
488            self.buffer[0] |= ((data << (64 - nbits)) >> (64 - 8 + self.offset)) as u8;
489            self.offset += bits;
490            nbits -= bits;
491            if self.offset == 8 {
492                wrote += self.flush()?;
493            }
494        }
495        Ok(wrote)
496    }
497
498    /// flush bits not yet written
499    pub fn flush(&mut self) -> Result<usize, io::Error> {
500        if self.offset > 0 {
501            self.writer.write_all(&self.buffer)?;
502            self.buffer[0] = 0u8;
503            self.offset = 0;
504            Ok(1)
505        } else {
506            Ok(0)
507        }
508    }
509}
510
511#[cfg(test)]
512mod test {
513    use std::collections::{HashSet, HashMap};
514    use std::io::Cursor;
515
516    use hash_types::BlockHash;
517    use hashes::hex::FromHex;
518
519    use super::*;
520
521    extern crate serde_json;
522    use self::serde_json::{Value};
523
524    use consensus::encode::deserialize;
525
526    #[test]
527    fn test_blockfilters() {
528
529        // test vectors from: https://github.com/jimpo/bitcoin/blob/c7efb652f3543b001b4dd22186a354605b14f47e/src/test/data/blockfilters.json
530        let data = r#"
531        [
532            ["Block Height,Block Hash,Block,[Prev Output Scripts for Block],Previous Basic Header,Basic Filter,Basic Header,Notes"],
533            [0,"000000000933ea01ad0ee984209779baaec3ced90fa3f408719526f8d77f4943","0100000000000000000000000000000000000000000000000000000000000000000000003ba3edfd7a7b12b27ac72c3e67768f617fc81bc3888a51323a9fb8aa4b1e5e4adae5494dffff001d1aa4ae180101000000010000000000000000000000000000000000000000000000000000000000000000ffffffff4d04ffff001d0104455468652054696d65732030332f4a616e2f32303039204368616e63656c6c6f72206f6e206272696e6b206f66207365636f6e64206261696c6f757420666f722062616e6b73ffffffff0100f2052a01000000434104678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5fac00000000",[],"0000000000000000000000000000000000000000000000000000000000000000","019dfca8","21584579b7eb08997773e5aeff3a7f932700042d0ed2a6129012b7d7ae81b750","Genesis block"],
534            [2,"000000006c02c8ea6e4ff69651f7fcde348fb9d557a06e6957b65552002a7820","0100000006128e87be8b1b4dea47a7247d5528d2702c96826c7a648497e773b800000000e241352e3bec0a95a6217e10c3abb54adfa05abb12c126695595580fb92e222032e7494dffff001d00d235340101000000010000000000000000000000000000000000000000000000000000000000000000ffffffff0e0432e7494d010e062f503253482fffffffff0100f2052a010000002321038a7f6ef1c8ca0c588aa53fa860128077c9e6c11e6830f4d7ee4e763a56b7718fac00000000",[],"d7bdac13a59d745b1add0d2ce852f1a0442e8945fc1bf3848d3cbffd88c24fe1","0174a170","186afd11ef2b5e7e3504f2e8cbf8df28a1fd251fe53d60dff8b1467d1b386cf0",""],
535            [3,"000000008b896e272758da5297bcd98fdc6d97c9b765ecec401e286dc1fdbe10","0100000020782a005255b657696ea057d5b98f34defcf75196f64f6eeac8026c0000000041ba5afc532aae03151b8aa87b65e1594f97504a768e010c98c0add79216247186e7494dffff001d058dc2b60101000000010000000000000000000000000000000000000000000000000000000000000000ffffffff0e0486e7494d0151062f503253482fffffffff0100f2052a01000000232103f6d9ff4c12959445ca5549c811683bf9c88e637b222dd2e0311154c4c85cf423ac00000000",[],"186afd11ef2b5e7e3504f2e8cbf8df28a1fd251fe53d60dff8b1467d1b386cf0","016cf7a0","8d63aadf5ab7257cb6d2316a57b16f517bff1c6388f124ec4c04af1212729d2a",""],
536            [15007,"0000000038c44c703bae0f98cdd6bf30922326340a5996cc692aaae8bacf47ad","0100000002394092aa378fe35d7e9ac79c869b975c4de4374cd75eb5484b0e1e00000000eb9b8670abd44ad6c55cee18e3020fb0c6519e7004b01a16e9164867531b67afc33bc94fffff001d123f10050101000000010000000000000000000000000000000000000000000000000000000000000000ffffffff0e04c33bc94f0115062f503253482fffffffff0100f2052a01000000232103f268e9ae07e0f8cb2f6e901d87c510d650b97230c0365b021df8f467363cafb1ac00000000",[],"18b5c2b0146d2d09d24fb00ff5b52bd0742f36c9e65527abdb9de30c027a4748","013c3710","07384b01311867949e0c046607c66b7a766d338474bb67f66c8ae9dbd454b20e","Tx has non-standard OP_RETURN output followed by opcodes"],
537            [49291,"0000000018b07dca1b28b4b5a119f6d6e71698ce1ed96f143f54179ce177a19c","02000000abfaf47274223ca2fea22797e44498240e482cb4c2f2baea088962f800000000604b5b52c32305b15d7542071d8b04e750a547500005d4010727694b6e72a776e55d0d51ffff001d211806480201000000010000000000000000000000000000000000000000000000000000000000000000ffffffff0d038bc0000102062f503253482fffffffff01a078072a01000000232102971dd6034ed0cf52450b608d196c07d6345184fcb14deb277a6b82d526a6163dac0000000001000000081cefd96060ecb1c4fbe675ad8a4f8bdc61d634c52b3a1c4116dee23749fe80ff000000009300493046022100866859c21f306538152e83f115bcfbf59ab4bb34887a88c03483a5dff9895f96022100a6dfd83caa609bf0516debc2bf65c3df91813a4842650a1858b3f61cfa8af249014730440220296d4b818bb037d0f83f9f7111665f49532dfdcbec1e6b784526e9ac4046eaa602204acf3a5cb2695e8404d80bf49ab04828bcbe6fc31d25a2844ced7a8d24afbdff01ffffffff1cefd96060ecb1c4fbe675ad8a4f8bdc61d634c52b3a1c4116dee23749fe80ff020000009400483045022100e87899175991aa008176cb553c6f2badbb5b741f328c9845fcab89f8b18cae2302200acce689896dc82933015e7230e5230d5cff8a1ffe82d334d60162ac2c5b0c9601493046022100994ad29d1e7b03e41731a4316e5f4992f0d9b6e2efc40a1ccd2c949b461175c502210099b69fdc2db00fbba214f16e286f6a49e2d8a0d5ffc6409d87796add475478d601ffffffff1e4a6d2d280ea06680d6cf8788ac90344a9c67cca9b06005bbd6d3f6945c8272010000009500493046022100a27400ba52fd842ce07398a1de102f710a10c5599545e6c95798934352c2e4df022100f6383b0b14c9f64b6718139f55b6b9494374755b86bae7d63f5d3e583b57255a01493046022100fdf543292f34e1eeb1703b264965339ec4a450ec47585009c606b3edbc5b617b022100a5fbb1c8de8aaaa582988cdb23622838e38de90bebcaab3928d949aa502a65d401ffffffff1e4a6d2d280ea06680d6cf8788ac90344a9c67cca9b06005bbd6d3f6945c8272020000009400493046022100ac626ac3051f875145b4fe4cfe089ea895aac73f65ab837b1ac30f5d875874fa022100bc03e79fa4b7eb707fb735b95ff6613ca33adeaf3a0607cdcead4cfd3b51729801483045022100b720b04a5c5e2f61b7df0fcf334ab6fea167b7aaede5695d3f7c6973496adbf1022043328c4cc1cdc3e5db7bb895ccc37133e960b2fd3ece98350f774596badb387201ffffffff23a8733e349c97d6cd90f520fdd084ba15ce0a395aad03cd51370602bb9e5db3010000004a00483045022100e8556b72c5e9c0da7371913a45861a61c5df434dfd962de7b23848e1a28c86ca02205d41ceda00136267281be0974be132ac4cda1459fe2090ce455619d8b91045e901ffffffff6856d609b881e875a5ee141c235e2a82f6b039f2b9babe82333677a5570285a6000000006a473044022040a1c631554b8b210fbdf2a73f191b2851afb51d5171fb53502a3a040a38d2c0022040d11cf6e7b41fe1b66c3d08f6ada1aee07a047cb77f242b8ecc63812c832c9a012102bcfad931b502761e452962a5976c79158a0f6d307ad31b739611dac6a297c256ffffffff6856d609b881e875a5ee141c235e2a82f6b039f2b9babe82333677a5570285a601000000930048304502205b109df098f7e932fbf71a45869c3f80323974a826ee2770789eae178a21bfc8022100c0e75615e53ee4b6e32b9bb5faa36ac539e9c05fa2ae6b6de5d09c08455c8b9601483045022009fb7d27375c47bea23b24818634df6a54ecf72d52e0c1268fb2a2c84f1885de022100e0ed4f15d62e7f537da0d0f1863498f9c7c0c0a4e00e4679588c8d1a9eb20bb801ffffffffa563c3722b7b39481836d5edfc1461f97335d5d1e9a23ade13680d0e2c1c371f030000006c493046022100ecc38ae2b1565643dc3c0dad5e961a5f0ea09cab28d024f92fa05c922924157e022100ebc166edf6fbe4004c72bfe8cf40130263f98ddff728c8e67b113dbd621906a601210211a4ed241174708c07206601b44a4c1c29e5ad8b1f731c50ca7e1d4b2a06dc1fffffffff02d0223a00000000001976a91445db0b779c0b9fa207f12a8218c94fc77aff504588ac80f0fa02000000000000000000",["5221033423007d8f263819a2e42becaaf5b06f34cb09919e06304349d950668209eaed21021d69e2b68c3960903b702af7829fadcd80bd89b158150c85c4a75b2c8cb9c39452ae","52210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f8179821021d69e2b68c3960903b702af7829fadcd80bd89b158150c85c4a75b2c8cb9c39452ae","522102a7ae1e0971fc1689bd66d2a7296da3a1662fd21a53c9e38979e0f090a375c12d21022adb62335f41eb4e27056ac37d462cda5ad783fa8e0e526ed79c752475db285d52ae","52210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f8179821022adb62335f41eb4e27056ac37d462cda5ad783fa8e0e526ed79c752475db285d52ae","512103b9d1d0e2b4355ec3cdef7c11a5c0beff9e8b8d8372ab4b4e0aaf30e80173001951ae","76a9149144761ebaccd5b4bbdc2a35453585b5637b2f8588ac","522103f1848b40621c5d48471d9784c8174ca060555891ace6d2b03c58eece946b1a9121020ee5d32b54d429c152fdc7b1db84f2074b0564d35400d89d11870f9273ec140c52ae","76a914f4fa1cc7de742d135ea82c17adf0bb9cf5f4fb8388ac"],"ed47705334f4643892ca46396eb3f4196a5e30880589e4009ef38eae895d4a13","0afbc2920af1b027f31f87b592276eb4c32094bb4d3697021b4c6380","b6d98692cec5145f67585f3434ec3c2b3030182e1cb3ec58b855c5c164dfaaa3","Tx pays to empty output script"],
538            [180480,"00000000fd3ceb2404ff07a785c7fdcc76619edc8ed61bd25134eaa22084366a","020000006058aa080a655aa991a444bd7d1f2defd9a3bbe68aabb69030cf3b4e00000000d2e826bfd7ef0beaa891a7eedbc92cd6a544a6cb61c7bdaa436762eb2123ef9790f5f552ffff001d0002c90f0501000000010000000000000000000000000000000000000000000000000000000000000000ffffffff0e0300c102024608062f503253482fffffffff01c0c6072a01000000232102e769e60137a4df6b0df8ebd387cca44c4c57ae74cc0114a8e8317c8f3bfd85e9ac00000000010000000381a0802911a01ffb025c4dea0bc77963e8c1bb46313b71164c53f72f37fe5248010000000151ffffffffc904b267833d215e2128bd9575242232ac2bc311550c7fc1f0ef6f264b40d14c010000000151ffffffffdf0915666649dba81886519c531649b7b02180b4af67d6885e871299e9d5f775000000000151ffffffff0180817dcb00000000232103bb52138972c48a132fc1f637858c5189607dd0f7fe40c4f20f6ad65f2d389ba4ac0000000001000000018da38b434fba82d66052af74fc5e4e94301b114d9bc03f819dc876398404c8b4010000006c493046022100fe738b7580dc5fb5168e51fc61b5aed211125eb71068031009a22d9bbad752c5022100be5086baa384d40bcab0fa586e4f728397388d86e18b66cc417dc4f7fa4f9878012103f233299455134caa2687bdf15cb0becdfb03bd0ff2ff38e65ec6b7834295c34fffffffff022ebc1400000000001976a9147779b7fba1c1e06b717069b80ca170e8b04458a488ac9879c40f000000001976a9142a0307cd925dbb66b534c4db33003dd18c57015788ac0000000001000000026139a62e3422a602de36c873a225c1d3ca5aeee598539ceecb9f0dc8d1ad0f83010000006b483045022100ad9f32b4a0a2ddc19b5a74eba78123e57616f1b3cfd72ce68c03ea35a3dda1f002200dbd22aa6da17213df5e70dfc3b2611d40f70c98ed9626aa5e2cde9d97461f0a012103ddb295d2f1e8319187738fb4b230fdd9aa29d0e01647f69f6d770b9ab24eea90ffffffff983c82c87cf020040d671956525014d5c2b28c6d948c85e1a522362c0059eeae010000006b4830450221009ca544274c786d30a5d5d25e17759201ea16d3aedddf0b9e9721246f7ef6b32e02202cfa5564b6e87dfd9fd98957820e4d4e6238baeb0f65fe305d91506bb13f5f4f012103c99113deac0d5d044e3ac0346abc02501542af8c8d3759f1382c72ff84e704f7ffffffff02c0c62d00000000001976a914ae19d27efe12f5a886dc79af37ad6805db6f922d88ac70ce2000000000001976a9143b8d051d37a07ea1042067e93efe63dbf73920b988ac000000000100000002be566e8cd9933f0c75c4a82c027f7d0c544d5c101d0607ef6ae5d07b98e7f1dc000000006b483045022036a8cdfd5ea7ebc06c2bfb6e4f942bbf9a1caeded41680d11a3a9f5d8284abad022100cacb92a5be3f39e8bc14db1710910ef7b395fa1e18f45d41c28d914fcdde33be012102bf59abf110b5131fae0a3ce1ec379329b4c896a6ae5d443edb68529cc2bc7816ffffffff96cf67645b76ceb23fe922874847456a15feee1655082ff32d25a6bf2c0dfc90000000006a47304402203471ca2001784a5ac0abab583581f2613523da47ec5f53df833c117b5abd81500220618a2847723d57324f2984678db556dbca1a72230fc7e39df04c2239942ba942012102925c9794fd7bb9f8b29e207d5fc491b1150135a21f505041858889fa4edf436fffffffff026c840f00000000001976a914797fb8777d7991d8284d88bfd421ce520f0f843188ac00ca9a3b000000001976a9146d10f3f592699265d10b106eda37c3ce793f7a8588ac00000000",["","","","76a9142903b138c24be9e070b3e73ec495d77a204615e788ac","76a91433a1941fd9a37b9821d376f5a51bd4b52fa50e2888ac","76a914e4374e8155d0865742ca12b8d4d14d41b57d682f88ac","76a914001fa7459a6cfc64bdc178ba7e7a21603bb2568f88ac","76a914f6039952bc2b307aeec5371bfb96b66078ec17f688ac"],"d34ef98386f413769502808d4bac5f20f8dfd5bffc9eedafaa71de0eb1f01489","0db414c859a07e8205876354a210a75042d0463404913d61a8e068e58a3ae2aa080026","c582d51c0ca365e3fcf36c51cb646d7f83a67e867cb4743fd2128e3e022b700c","Tx spends from empty output script"],
539            [926485,"000000000000015d6077a411a8f5cc95caf775ccf11c54e27df75ce58d187313","0000002060bbab0edbf3ef8a49608ee326f8fd75c473b7e3982095e2d100000000000000c30134f8c9b6d2470488d7a67a888f6fa12f8692e0c3411fbfb92f0f68f67eedae03ca57ef13021acc22dc4105010000000001010000000000000000000000000000000000000000000000000000000000000000ffffffff2f0315230e0004ae03ca57043e3d1e1d0c8796bf579aef0c0000000000122f4e696e6a61506f6f6c2f5345475749542fffffffff038427a112000000001976a914876fbb82ec05caa6af7a3b5e5a983aae6c6cc6d688ac0000000000000000266a24aa21a9ed5c748e121c0fe146d973a4ac26fa4a68b0549d46ee22d25f50a5e46fe1b377ee00000000000000002952534b424c4f434b3acd16772ad61a3c5f00287480b720f6035d5e54c9efc71be94bb5e3727f10909001200000000000000000000000000000000000000000000000000000000000000000000000000100000000010145310e878941a1b2bc2d33797ee4d89d95eaaf2e13488063a2aa9a74490f510a0100000023220020b6744de4f6ec63cc92f7c220cdefeeb1b1bed2b66c8e5706d80ec247d37e65a1ffffffff01002d3101000000001976a9143ebc40e411ed3c76f86711507ab952300890397288ac0400473044022001dd489a5d4e2fbd8a3ade27177f6b49296ba7695c40dbbe650ea83f106415fd02200b23a0602d8ff1bdf79dee118205fc7e9b40672bf31563e5741feb53fb86388501483045022100f88f040e90cc5dc6c6189d04718376ac19ed996bf9e4a3c29c3718d90ffd27180220761711f16c9e3a44f71aab55cbc0634907a1fa8bb635d971a9a01d368727bea10169522103b3623117e988b76aaabe3d63f56a4fc88b228a71e64c4cc551d1204822fe85cb2103dd823066e096f72ed617a41d3ca56717db335b1ea47a1b4c5c9dbdd0963acba621033d7c89bd9da29fa8d44db7906a9778b53121f72191184a9fee785c39180e4be153ae00000000010000000120925534261de4dcebb1ed5ab1b62bfe7a3ef968fb111dc2c910adfebc6e3bdf010000006b483045022100f50198f5ae66211a4f485190abe4dc7accdabe3bc214ebc9ea7069b97097d46e0220316a70a03014887086e335fc1b48358d46cd6bdc9af3b57c109c94af76fc915101210316cff587a01a2736d5e12e53551b18d73780b83c3bfb4fcf209c869b11b6415effffffff0220a10700000000001976a91450333046115eaa0ac9e0216565f945070e44573988ac2e7cd01a000000001976a914c01a7ca16b47be50cbdbc60724f701d52d75156688ac00000000010000000203a25f58630d7a1ea52550365fd2156683f56daf6ca73a4b4bbd097e66516322010000006a47304402204efc3d70e4ca3049c2a425025edf22d5ca355f9ec899dbfbbeeb2268533a0f2b02204780d3739653035af4814ea52e1396d021953f948c29754edd0ee537364603dc012103f7a897e4dbecab2264b21917f90664ea8256189ea725d28740cf7ba5d85b5763ffffffff03a25f58630d7a1ea52550365fd2156683f56daf6ca73a4b4bbd097e66516322000000006a47304402202d96defdc5b4af71d6ba28c9a6042c2d5ee7bc6de565d4db84ef517445626e03022022da80320e9e489c8f41b74833dfb6a54a4eb5087cdb46eb663eef0b25caa526012103f7a897e4dbecab2264b21917f90664ea8256189ea725d28740cf7ba5d85b5763ffffffff0200e1f5050000000017a914b7e6f7ff8658b2d1fb107e3d7be7af4742e6b1b3876f88fc00000000001976a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88ac0000000001000000043ffd60d3818431c495b89be84afac205d5d1ed663009291c560758bbd0a66df5010000006b483045022100f344607de9df42049688dcae8ff1db34c0c7cd25ec05516e30d2bc8f12ac9b2f022060b648f6a21745ea6d9782e17bcc4277b5808326488a1f40d41e125879723d3a012103f7a897e4dbecab2264b21917f90664ea8256189ea725d28740cf7ba5d85b5763ffffffffa5379401cce30f84731ef1ba65ce27edf2cc7ce57704507ebe8714aa16a96b92010000006a473044022020c37a63bf4d7f564c2192528709b6a38ab8271bd96898c6c2e335e5208661580220435c6f1ad4d9305d2c0a818b2feb5e45d443f2f162c0f61953a14d097fd07064012103f7a897e4dbecab2264b21917f90664ea8256189ea725d28740cf7ba5d85b5763ffffffff70e731e193235ff12c3184510895731a099112ffca4b00246c60003c40f843ce000000006a473044022053760f74c29a879e30a17b5f03a5bb057a5751a39f86fa6ecdedc36a1b7db04c022041d41c9b95f00d2d10a0373322a9025dba66c942196bc9d8adeb0e12d3024728012103f7a897e4dbecab2264b21917f90664ea8256189ea725d28740cf7ba5d85b5763ffffffff66b7a71b3e50379c8e85fc18fe3f1a408fc985f257036c34702ba205cef09f6f000000006a4730440220499bf9e2db3db6e930228d0661395f65431acae466634d098612fd80b08459ee022040e069fc9e3c60009f521cef54c38aadbd1251aee37940e6018aadb10f194d6a012103f7a897e4dbecab2264b21917f90664ea8256189ea725d28740cf7ba5d85b5763ffffffff0200e1f5050000000017a9148fc37ad460fdfbd2b44fe446f6e3071a4f64faa6878f447f0b000000001976a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88ac00000000",["a914feb8a29635c56d9cd913122f90678756bf23887687","76a914c01a7ca16b47be50cbdbc60724f701d52d75156688ac","76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88ac","76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88ac","76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88ac","76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88ac","76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88ac","76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88ac"],"8f13b9a9c85611635b47906c3053ac53cfcec7211455d4cb0d63dc9acc13d472","09027acea61b6cc3fb33f5d52f7d088a6b2f75d234e89ca800","546c574a0472144bcaf9b6aeabf26372ad87c7af7d1ee0dbfae5e099abeae49c","Duplicate pushdata 913bcc2be49cb534c20474c4dee1e9c4c317e7eb"],
540            [987876,"0000000000000c00901f2049055e2a437c819d79a3d54fd63e6af796cd7b8a79","000000202694f74969fdb542090e95a56bc8aa2d646e27033850e32f1c5f000000000000f7e53676b3f12d5beb524ed617f2d25f5a93b5f4f52c1ba2678260d72712f8dd0a6dfe5740257e1a4b1768960101000000010000000000000000000000000000000000000000000000000000000000000000ffffffff1603e4120ff9c30a1c216900002f424d4920546573742fffffff0001205fa012000000001e76a914c486de584a735ec2f22da7cd9681614681f92173d83d0aa68688ac00000000",[],"fe4d230dbb0f4fec9bed23a5283e08baf996e3f32b93f52c7de1f641ddfd04ad","010c0b40","0965a544743bbfa36f254446e75630c09404b3d164a261892372977538928ed5","Coinbase tx has unparseable output script"],
541            [1263442,"000000006f27ddfe1dd680044a34548f41bed47eba9e6f0b310da21423bc5f33","000000201c8d1a529c39a396db2db234d5ec152fa651a2872966daccbde028b400000000083f14492679151dbfaa1a825ef4c18518e780c1f91044180280a7d33f4a98ff5f45765aaddc001d38333b9a02010000000001010000000000000000000000000000000000000000000000000000000000000000ffffffff230352471300fe5f45765afe94690a000963676d696e6572343208000000000000000000ffffffff024423a804000000001976a914f2c25ac3d59f3d674b1d1d0a25c27339aaac0ba688ac0000000000000000266a24aa21a9edcb26cb3052426b9ebb4d19c819ef87c19677bbf3a7c46ef0855bd1b2abe83491012000000000000000000000000000000000000000000000000000000000000000000000000002000000000101d20978463906ba4ff5e7192494b88dd5eb0de85d900ab253af909106faa22cc5010000000004000000014777ff000000000016001446c29eabe8208a33aa1023c741fa79aa92e881ff0347304402207d7ca96134f2bcfdd6b536536fdd39ad17793632016936f777ebb32c22943fda02206014d2fb8a6aa58279797f861042ba604ebd2f8f61e5bddbd9d3be5a245047b201004b632103eeaeba7ce5dc2470221e9517fb498e8d6bd4e73b85b8be655196972eb9ccd5566754b2752103a40b74d43df244799d041f32ce1ad515a6cd99501701540e38750d883ae21d3a68ac00000000",["002027a5000c7917f785d8fc6e5a55adfca8717ecb973ebb7743849ff956d896a7ed"],"31d66d516a9eda7de865df29f6ef6cb8e4bf9309e5dac899968a9a62a5df61e3","0385acb4f0fe889ef0","4e6d564c2a2452065c205dd7eb2791124e0c4e0dbb064c410c24968572589dec","Includes witness data"],
542            [1414221,"0000000000000027b2b3b3381f114f674f481544ff2be37ae3788d7e078383b1","000000204ea88307a7959d8207968f152bedca5a93aefab253f1fb2cfb032a400000000070cebb14ec6dbc27a9dfd066d9849a4d3bac5f674665f73a5fe1de01a022a0c851fda85bf05f4c19a779d1450102000000010000000000000000000000000000000000000000000000000000000000000000ffffffff18034d94154d696e6572476174653030310d000000f238f401ffffffff01c817a804000000000000000000",[],"5e5e12d90693c8e936f01847859404c67482439681928353ca1296982042864e","00","021e8882ef5a0ed932edeebbecfeda1d7ce528ec7b3daa27641acf1189d7b5dc","Empty data"]
543        ]
544        "#;
545
546        let testdata = serde_json::from_str::<Value>(data).unwrap().as_array().unwrap().clone();
547        for t in testdata.iter().skip(1) {
548            let block_hash = BlockHash::from_hex(&t.get(1).unwrap().as_str().unwrap()).unwrap();
549            let block: Block = deserialize(&Vec::from_hex(&t.get(2).unwrap().as_str().unwrap()).unwrap()).unwrap();
550            assert_eq!(block.block_hash(), block_hash);
551            let scripts = t.get(3).unwrap().as_array().unwrap();
552            let previous_filter_header = FilterHeader::from_hex(&t.get(4).unwrap().as_str().unwrap()).unwrap();
553            let filter_content = Vec::from_hex(&t.get(5).unwrap().as_str().unwrap()).unwrap();
554            let filter_header = FilterHeader::from_hex(&t.get(6).unwrap().as_str().unwrap()).unwrap();
555
556            let mut txmap = HashMap::new();
557            let mut si = scripts.iter();
558            for tx in block.txdata.iter().skip(1) {
559                for input in tx.input.iter() {
560                    txmap.insert(input.previous_output.clone(), Script::from(Vec::from_hex(si.next().unwrap().as_str().unwrap()).unwrap()));
561                }
562            }
563
564            let filter = BlockFilter::new_script_filter(&block,
565                                        |o| if let Some(s) = txmap.get(o) {
566                                            Ok(s.clone())
567                                        } else {
568                                            Err(Error::UtxoMissing(o.clone()))
569                                        }).unwrap();
570
571            let test_filter = BlockFilter::new(filter_content.as_slice());
572
573            assert_eq!(test_filter.content, filter.content);
574
575            let block_hash = &block.block_hash();
576            assert!(filter.match_all(block_hash, &mut txmap.iter()
577                .filter_map(|(_, s)| if !s.is_empty() { Some(s.as_bytes()) } else { None })).unwrap());
578
579            for (_, script) in &txmap {
580                let query = vec![script];
581                if !script.is_empty () {
582                    assert!(filter.match_any(&block_hash, &mut query.iter()
583                        .map(|s| s.as_bytes())).unwrap());
584                }
585            }
586
587            assert_eq!(filter_header, filter.filter_header(&previous_filter_header));
588        }
589    }
590
591    #[test]
592    fn test_filter () {
593        let mut patterns = HashSet::new();
594
595        patterns.insert(Vec::from_hex("000000").unwrap());
596        patterns.insert(Vec::from_hex("111111").unwrap());
597        patterns.insert(Vec::from_hex("222222").unwrap());
598        patterns.insert(Vec::from_hex("333333").unwrap());
599        patterns.insert(Vec::from_hex("444444").unwrap());
600        patterns.insert(Vec::from_hex("555555").unwrap());
601        patterns.insert(Vec::from_hex("666666").unwrap());
602        patterns.insert(Vec::from_hex("777777").unwrap());
603        patterns.insert(Vec::from_hex("888888").unwrap());
604        patterns.insert(Vec::from_hex("999999").unwrap());
605        patterns.insert(Vec::from_hex("aaaaaa").unwrap());
606        patterns.insert(Vec::from_hex("bbbbbb").unwrap());
607        patterns.insert(Vec::from_hex("cccccc").unwrap());
608        patterns.insert(Vec::from_hex("dddddd").unwrap());
609        patterns.insert(Vec::from_hex("eeeeee").unwrap());
610        patterns.insert(Vec::from_hex("ffffff").unwrap());
611
612        let mut out = Cursor::new(Vec::new());
613        {
614            let mut writer = GCSFilterWriter::new(&mut out, 0, 0, M, P);
615            for p in &patterns {
616                writer.add_element(p.as_slice());
617            }
618            writer.finish().unwrap();
619        }
620
621        let bytes = out.into_inner();
622
623        {
624            let mut query = Vec::new();
625            query.push(Vec::from_hex("abcdef").unwrap());
626            query.push(Vec::from_hex("eeeeee").unwrap());
627
628            let reader = GCSFilterReader::new(0, 0, M, P);
629            let mut input = Cursor::new(bytes.clone());
630            assert!(reader.match_any(&mut input, &mut query.iter().map(|v| v.as_slice())).unwrap());
631        }
632        {
633            let mut query = Vec::new();
634            query.push(Vec::from_hex("abcdef").unwrap());
635            query.push(Vec::from_hex("123456").unwrap());
636
637            let reader = GCSFilterReader::new(0, 0, M, P);
638            let mut input = Cursor::new(bytes.clone());
639            assert!(!reader.match_any(&mut input, &mut query.iter().map(|v| v.as_slice())).unwrap());
640        }
641        {
642            let reader = GCSFilterReader::new(0, 0, M, P);
643            let mut query = Vec::new();
644            for p in &patterns {
645                query.push(p.clone());
646            }
647            let mut input = Cursor::new(bytes.clone());
648            assert!(reader.match_all(&mut input, &mut query.iter().map(|v| v.as_slice())).unwrap());
649        }
650        {
651            let reader = GCSFilterReader::new(0, 0, M, P);
652            let mut query = Vec::new();
653            for p in &patterns {
654                query.push(p.clone());
655            }
656            query.push(Vec::from_hex("abcdef").unwrap());
657            let mut input = Cursor::new(bytes.clone());
658            assert!(!reader.match_all(&mut input, &mut query.iter().map(|v| v.as_slice())).unwrap());
659        }
660    }
661
662    #[test]
663    fn test_bit_stream() {
664        let mut out = Cursor::new(Vec::new());
665        {
666            let mut writer = BitStreamWriter::new(&mut out);
667            writer.write(0, 1).unwrap(); // 0
668            writer.write(2, 2).unwrap(); // 10
669            writer.write(6, 3).unwrap(); // 110
670            writer.write(11, 4).unwrap(); // 1011
671            writer.write(1, 5).unwrap(); // 00001
672            writer.write(32, 6).unwrap(); // 100000
673            writer.write(7, 7).unwrap(); // 0000111
674            writer.flush().unwrap();
675        }
676        let bytes = out.into_inner();
677        assert_eq!("01011010110000110000000001110000", format!("{:08b}{:08b}{:08b}{:08b}", bytes[0], bytes[1], bytes[2], bytes[3]));
678        {
679            let mut input = Cursor::new(bytes);
680            let mut reader = BitStreamReader::new(&mut input);
681            assert_eq!(reader.read(1).unwrap(), 0);
682            assert_eq!(reader.read(2).unwrap(), 2);
683            assert_eq!(reader.read(3).unwrap(), 6);
684            assert_eq!(reader.read(4).unwrap(), 11);
685            assert_eq!(reader.read(5).unwrap(), 1);
686            assert_eq!(reader.read(6).unwrap(), 32);
687            assert_eq!(reader.read(7).unwrap(), 7);
688            // 4 bits remained
689            assert!(reader.read(5).is_err());
690        }
691    }
692}
bitcoin/util/bip158.rs

bitcoin/util/
bip158.rs
