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

pexacoin/util/
bip158.rs
