txoo 0.10.0

use crate::io;
use alloc::sync::Arc;
use alloc::vec::Vec;
use bitcoin::consensus::Encodable;
use bitcoin::hashes::{Hash, HashEngine};
use bitcoin::bip158::{Error as FilterError, GcsFilterReader, GcsFilterWriter};
use bitcoin::{Block, BlockHash, OutPoint};
use bitcoin::hash_types::{FilterHash, FilterHeader};
use serde_bolt::{NonContiguousOctets, NonContiguousOctetsCursor};

/// Golomb encoding parameter as in BIP-158, see also https://gist.github.com/sipa/576d5f09c3b86c3b1b75598d799fc845
const P: u8 = 19;
const M: u64 = 784931;

/// A byte container made of disparate blocks of memory, each CHUNK_SIZE long,
/// optimized to reduce contiguous memory requirements in embedded devices.
/// See serde_bolt and chunked-buffer for details.
pub type ChunkedOctets = NonContiguousOctets<1024>;

/// A computed or read block filter for spent outpoints in a block
#[derive(Clone)]
pub struct BlockSpendFilter {
    /// Golomb encoded filter
    pub content: Arc<ChunkedOctets>,
}

impl BlockSpendFilter {
    /// Compute this filter's id in a chain of filters
    pub fn filter_header(&self, previous_filter_header: &FilterHeader) -> FilterHeader {
        let filter_hash = self.filter_hash();
        filter_hash.filter_header(previous_filter_header)
    }

    /// Compute the filter hash
    pub fn filter_hash(&self) -> FilterHash {
        let mut engine = FilterHash::engine();
        for slice in self.content.iter_chunks() {
            engine.input(slice);
        }
        FilterHash::from_engine(engine)
    }

    /// create a new filter from pre-computed data
    pub fn new(content: Arc<ChunkedOctets>) -> BlockSpendFilter {
        BlockSpendFilter { content }
    }

    /// Create a new filter from a block
    pub fn from_block(block: &Block) -> BlockSpendFilter {
        let mut out = ChunkedOctets::new();
        {
            let mut writer = BlockFilterWriter::new(&mut out, block);
            writer.add_spent_outpoints();
            writer.finish().expect("writing to a Vec cannot fail");
        }
        BlockSpendFilter {
            content: Arc::new(out),
        }
    }

    /// match any query pattern
    pub fn match_any(
        &self,
        block_hash: &BlockHash,
        query: &mut dyn Iterator<Item = &OutPoint>,
    ) -> bool {
        let encoded: Vec<_> = query.map(|o| encode_point(&o)).collect();
        let filter_reader = BlockFilterReader::new(block_hash);
        filter_reader
            .match_any(
                &mut NonContiguousOctetsCursor::new(&self.content),
                &mut encoded.iter().map(|x| x.as_slice()),
            )
            .expect("reading from a Vec cannot fail")
    }

    /// match all query pattern
    pub fn match_all(
        &self,
        block_hash: &BlockHash,
        query: &mut dyn Iterator<Item = &OutPoint>,
    ) -> bool {
        let encoded: Vec<_> = query.map(|o| encode_point(&o)).collect();
        let filter_reader = BlockFilterReader::new(block_hash);
        filter_reader
            .match_all(
                &mut NonContiguousOctetsCursor::new(&self.content),
                &mut encoded.iter().map(|x| x.as_slice()),
            )
            .expect("reading from a Vec cannot fail")
    }
}

fn hash_to_k0_k1(hash: &[u8; 32]) -> (u64, u64) {
    let mut k0_slice = [0; 8];
    k0_slice.copy_from_slice(&hash[0..8]);
    let mut k1_slice = [0; 8];
    k1_slice.copy_from_slice(&hash[8..16]);
    let k0 = u64::from_le_bytes(k0_slice);
    let k1 = u64::from_le_bytes(k1_slice);
    (k0, k1)
}

/// Compiles and writes a block filter
pub struct BlockFilterWriter<'a, W: io::Write> {
    block: &'a Block,
    writer: GcsFilterWriter<'a, W>,
}

impl<'a, W: io::Write> BlockFilterWriter<'a, W> {
    /// Create a block filter writer
    pub fn new(writer: &'a mut W, block: &'a Block) -> BlockFilterWriter<'a, W> {
        let hash = block.block_hash().to_byte_array();
        let (k0, k1) = hash_to_k0_k1(&hash);
        let writer = GcsFilterWriter::new(writer, k0, k1, M, P);
        BlockFilterWriter { block, writer }
    }

    /// Add spend outpoints to the filter
    pub fn add_spent_outpoints(&mut self) {
        for transaction in &self.block.txdata {
            for txin in &transaction.input {
                let buf = encode_point(&txin.previous_output);
                self.add_element(&buf);
            }
        }
    }

    /// Add arbitrary element to a filter
    pub fn add_element(&mut self, data: &[u8]) {
        self.writer.add_element(data);
    }

    /// Write block filter
    pub fn finish(&mut self) -> Result<usize, io::Error> {
        self.writer.finish()
    }
}

/// Reads and interpret a block filter
pub struct BlockFilterReader {
    reader: GcsFilterReader,
}

impl BlockFilterReader {
    /// Create a block filter reader
    pub fn new(block_hash: &BlockHash) -> BlockFilterReader {
        let hash = block_hash.to_byte_array();
        let (k0, k1) = hash_to_k0_k1(&hash);
        BlockFilterReader {
            reader: GcsFilterReader::new(k0, k1, M, P),
        }
    }

    /// match any query pattern
    pub fn match_any<R: io::Read>(
        &self,
        reader: &mut R,
        query: &mut dyn Iterator<Item = &[u8]>,
    ) -> Result<bool, FilterError> {
        self.reader.match_any(reader, query)
    }

    /// match all query pattern
    pub fn match_all<R: io::Read>(
        &self,
        reader: &mut R,
        query: &mut dyn Iterator<Item = &[u8]>,
    ) -> Result<bool, FilterError> {
        self.reader.match_all(reader, query)
    }
}

fn encode_point(point: &OutPoint) -> Vec<u8> {
    let mut buf = Vec::new();
    point.consensus_encode(&mut buf).unwrap();
    buf
}

#[cfg(test)]
mod tests {
    use crate::filter::BlockSpendFilter;
    use bitcoin::absolute::LockTime;
    use bitcoin::transaction::Version;
    use bitcoin::hash_types::TxMerkleNode;
    use bitcoin::hashes::Hash;
    use bitcoin::{Amount, Block, BlockHash, CompactTarget, OutPoint, Transaction, TxIn, TxOut, Txid};
    use bitcoin::blockdata::block::Header as BlockHeader;

    #[test]
    fn filter_test() {
        let mut txs = Vec::new();
        for i in 0..16665 {
            let tx = Transaction {
                version: Version::non_standard(0),
                lock_time: LockTime::ZERO,
                input: vec![TxIn {
                    previous_output: OutPoint {
                        txid: Txid::all_zeros(),
                        vout: i,
                    },
                    script_sig: Default::default(),
                    sequence: Default::default(),
                    witness: Default::default(),
                }],
                output: vec![TxOut {
                    value: Amount::ZERO,
                    script_pubkey: Default::default(),
                }],
            };
            txs.push(tx);
        }
        let block = Block {
            header: BlockHeader {
                version: bitcoin::block::Version::from_consensus(0),
                prev_blockhash: BlockHash::all_zeros(),
                merkle_root: TxMerkleNode::all_zeros(),
                time: 0,
                bits: CompactTarget::from_consensus(0),
                nonce: 0,
            },
            txdata: txs,
        };
        let block_hash = block.block_hash();
        let filter = BlockSpendFilter::from_block(&block);
        assert_eq!(block.total_size(), 999983);
        assert_eq!(filter.content.len(), 43862);
        assert!(filter.match_any(
            &block_hash,
            &mut vec![
                OutPoint {
                    txid: Txid::all_zeros(),
                    vout: 1234,
                },
                OutPoint {
                    txid: Txid::all_zeros(),
                    vout: 5555,
                }
            ]
            .iter()
        ));

        assert!(!filter.match_all(
            &block_hash,
            &mut vec![
                OutPoint {
                    txid: Txid::all_zeros(),
                    vout: 1234,
                },
                OutPoint {
                    txid: Txid::all_zeros(),
                    vout: 20000,
                }
            ]
            .iter()
        ));

        assert_eq!(filter.content.len(), 43862);

        let txid = Txid::hash(&[1]);

        // the first false positive is at 1212
        for i in 0..100 {
            let points = (0..1000)
                .map(|j| OutPoint {
                    txid,
                    vout: i * 1000 + j,
                })
                .collect::<Vec<_>>();

            if filter.match_any(&block_hash, &mut points.iter()) {
                panic!("false positive at {}", i);
            }
        }
    }
}