BloomFilter::containsOutPoint() - Code Metrics - Inspection of "Merge pull request #220 from afk11/type-fields-as-..." - Bit-Wasp/bitcoin-php - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 410ea8...0c9ae2 )

by thomas

created 2015-12-16 03:15 UTC

BloomFilter::containsOutPoint() A

↳ Parent: BloomFilter

Complexity

Conditions	1
Paths	1

Size

Total Lines	4
Code Lines	2

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	2
CRAP Score	1

Importance

Changes	1
Bugs	0	Features	1

Metric	Value
c	1
b	0
f	1
dl	0
loc	4
ccs	2
cts	2
cp	1
rs	10
cc	1
eloc	2
nc	1
nop	1
crap	1

<?php

namespace BitWasp\Bitcoin\Bloom;

use BitWasp\Bitcoin\Crypto\Hash;
use BitWasp\Bitcoin\Flags;
use BitWasp\Bitcoin\Math\Math;
use BitWasp\Bitcoin\Serializer\Bloom\BloomFilterSerializer;
use BitWasp\Bitcoin\Script\ScriptFactory;
use BitWasp\Bitcoin\Serializable;
use BitWasp\Bitcoin\Transaction\OutPointInterface;
use BitWasp\Bitcoin\Transaction\TransactionInterface;
use BitWasp\Buffertools\Buffer;

class BloomFilter extends Serializable
{
    const LN2SQUARED = '0.4804530139182014246671025263266649717305529515945455';
    const LN2 = '0.6931471805599453094172321214581765680755001343602552';
    const MAX_HASH_FUNCS = '50';
    const MAX_FILTER_SIZE = 36000; // bytes
    const TWEAK_START = '4221880213'; // 0xFBA4C795

    const UPDATE_NONE = 0;
    const UPDATE_ALL = 1;
    const UPDATE_P2PUBKEY_ONLY = 2;
    const UPDATE_MASK = 3;

    /**
     * @var Math
     */
    private $math;

    /**
     * @var bool
     */
    private $empty = true;

    /**
     * @var bool
     */
    private $full = false;

    /**
     * @var int
     */
    private $numHashFuncs;

    /**
     * @var array
     */
    private $vFilter = [];

    /**
     * @var int|string
     */
    private $nTweak;

    /**
     * @var Flags
     */
    private $flags;

    /**
     * @param Math $math
     * @param array $vFilter
     * @param int $numHashFuncs
     * @param int|string $nTweak
     * @param Flags $flags
     */
    public function __construct(Math $math, array $vFilter, $numHashFuncs, $nTweak, Flags $flags)
    {
        $this->math = $math;
        $this->vFilter = $vFilter;
        $this->numHashFuncs = $numHashFuncs;
        $this->nTweak = $nTweak;
        $this->flags = $flags;
        $this->updateEmptyFull();
    }

    /**
     * @param int $size
     * @return array
     */
    public static function emptyFilter($size)
    {
        return str_split(str_pad('', $size, '0'), 1);
    }

    /**
     * Create the Bloom Filter given the number of elements, a false positive rate,
     * and the flags governing how the filter should be updated.
     *
     * @param Math $math
     * @param int $nElements
     * @param float $nFpRate
     * @param int $nTweak
     * @param Flags $flags
     * @return BloomFilter
     */
    public static function create(Math $math, $nElements, $nFpRate, $nTweak, Flags $flags)
    {
        $size = self::idealSize($nElements, $nFpRate);

        return new self(
            $math,
            self::emptyFilter($size),
            self::idealNumHashFuncs($size, $nElements),
            $nTweak,
            $flags
        );
    }

    /**
     * @param int $flag
     * @return bool
     */
    public function checkFlag($flag)
    {
        return $this->math->cmp($this->math->bitwiseAnd($this->flags->getFlags(), self::UPDATE_MASK), $flag) === 0;
    }

    /**
     * @return bool
     */
    public function isUpdateNone()
    {
        return $this->checkFlag(self::UPDATE_NONE);
    }

    /**
     * @return bool
     */
    public function isUpdateAll()
    {
        return $this->checkFlag(self::UPDATE_ALL);
    }

    /**
     * @return bool
     */
    public function isUpdatePubKeyOnly()
    {
        return $this->checkFlag(self::UPDATE_P2PUBKEY_ONLY);
    }

    /**
     * @return bool
     */
    public function isEmpty()
    {
        return $this->empty;
    }

    /**
     * @return bool
     */
    public function isFull()
    {
        return $this->full;
    }

    /**
     * @return array
     */
    public function getData()
    {
        return $this->vFilter;
    }

    /**
     * @return int
     */
    public function getNumHashFuncs()
    {
        return $this->numHashFuncs;
    }

    /**
     * @return int|string
     */
    public function getTweak()
    {
        return $this->nTweak;
    }

    /**
     * @return Flags
     */
    public function getFlags()
    {
        return $this->flags;
    }

    /**
     * @param int $nElements
     * @param float $fpRate
     * @return int
     */
    public static function idealSize($nElements, $fpRate)
    {
        return (int) floor(
            bcdiv(
                min(
                    bcmul(
                        bcmul(
                            bcdiv(
                                -1,
                                self::LN2SQUARED
                            ),
                            $nElements
                        ),
                        log($fpRate)
                    ),
                    bcmul(
                        self::MAX_FILTER_SIZE,
                        8
                    )
                ),
                8
            )
        );
    }

    /**
     * @param int $filterSize
     * @param int $nElements
     * @return int
     */
    public static function idealNumHashFuncs($filterSize, $nElements)
    {
        return (int) floor(
            min(
                bcmul(
                    bcdiv(
                        bcmul(
                            $filterSize,
                            8
                        ),
                        $nElements
                    ),
                    self::LN2
                ),
                bcmul(
                    self::MAX_FILTER_SIZE,
                    8
                )
            )
        );
    }

    /**
     * @param int $nHashNum
     * @param Buffer $data
     * @return string
     */
    public function hash($nHashNum, Buffer $data)
    {
        return $this->math->mod(
            Hash::murmur3($data, ($nHashNum * self::TWEAK_START + $this->nTweak) & 0xffffffff)->getInt(),
            count($this->vFilter) * 8
        );
    }

    /**
     * @param Buffer $data
     * @return $this
     */
    public function insertData(Buffer $data)
    {
        if ($this->isFull()) {
            return $this;
        }

        for ($i = 0; $i < $this->numHashFuncs; $i++) {
            $index = $this->hash($i, $data);
            $this->vFilter[$index >> 3] |= (1 << (7 & $index));
        }

        $this->updateEmptyFull();
        return $this;
    }

    /**
     * @param OutPointInterface $outPoint
     * @return BloomFilter
     */
    public function insertOutPoint(OutPointInterface $outPoint)
    {
        return $this->insertData($outPoint->getBuffer());
    }

    /**
     * @param Buffer $data
     * @return bool
     */
    public function containsData(Buffer $data)
    {
        if ($this->isFull()) {
            return true;
        }

        if ($this->isEmpty()) {
            return false;
        }

        for ($i = 0; $i < $this->numHashFuncs; $i++) {
            $index = $this->hash($i, $data);

            if (!($this->vFilter[($index >> 3)] & (1 << (7 & $index)))) {
                return false;
            }
        }

        return true;
    }

    /**
     * @param OutPointInterface $outPoint
     * @return bool
     */
    public function containsOutPoint(OutPointInterface $outPoint)
    {
        return $this->containsData($outPoint->getBuffer());
    }

    /**
     * @return bool
     */
    public function hasAcceptableSize()
    {
        return count($this->vFilter) <= self::MAX_FILTER_SIZE && $this->numHashFuncs <= self::MAX_HASH_FUNCS;
    }

    /**
     * @param TransactionInterface $tx
     * @return bool
     */
    public function isRelevantAndUpdate(TransactionInterface $tx)
    {
        $this->updateEmptyFull();
        $found = false;
        if ($this->isFull()) {
            return true;
        }

        if ($this->isEmpty()) {
            return false;
        }

        // Check if the txid hash is in the filter
        $txHash = $tx->getTxId();
        if ($this->containsData($txHash)) {
            $found = true;
        }

        // Check for relevant output scripts. We add the outpoint to the filter if found.
        foreach ($tx->getOutputs() as $vout => $output) {
            $script = $output->getScript();
            $parser = $script->getScriptParser();
            foreach ($parser as $exec) {
                if ($exec->isPush() && $this->containsData($exec->getData())) {
                    $found = true;
                    if ($this->isUpdateAll()) {
                        $this->insertOutPoint($tx->makeOutPoint($vout));
                    } else if ($this->isUpdatePubKeyOnly()) {
                        $type = ScriptFactory::scriptPubKey()->classify($script);
                        if ($type->isMultisig() || $type->isPayToPublicKey()) {
                            $this->insertOutPoint($tx->makeOutPoint($vout));
                        }
                    }
                }
            }
        }

        if ($found) {
            return true;
        }

        foreach ($tx->getInputs() as $txIn) {
            if ($this->containsOutPoint($txIn->getOutPoint())) {
                return true;
            }

            $parser = $txIn->getScript()->getScriptParser();
            foreach ($parser as $exec) {
                if ($exec->isPush() > 0 && $this->containsData($exec->getData())) {
                    return true;
                }
            }
        }

        return false;
    }

    /**
     *
     */
    public function updateEmptyFull()
    {
        $full = true;
        $empty = true;
        for ($i = 0, $size = count($this->vFilter); $i < $size; $i++) {
            $byte = (int) $this->vFilter[$i];
            $full &= ($byte === 0xff);
            $empty &= ($byte === 0x0);
        }

        $this->full = (bool)$full;
        $this->empty = (bool)$empty;
    }

    /**
     * @return Buffer
     */
    public function getBuffer()
    {
        return (new BloomFilterSerializer())->serialize($this);
    }
}


1		<?php
2
3		namespace BitWasp\Bitcoin\Bloom;
4
5		use BitWasp\Bitcoin\Crypto\Hash;
6		use BitWasp\Bitcoin\Flags;
7		use BitWasp\Bitcoin\Math\Math;
8		use BitWasp\Bitcoin\Serializer\Bloom\BloomFilterSerializer;
9		use BitWasp\Bitcoin\Script\ScriptFactory;
10		use BitWasp\Bitcoin\Serializable;
11		use BitWasp\Bitcoin\Transaction\OutPointInterface;
12		use BitWasp\Bitcoin\Transaction\TransactionInterface;
13		use BitWasp\Buffertools\Buffer;
14
15		class BloomFilter extends Serializable
16		{
17		const LN2SQUARED = '0.4804530139182014246671025263266649717305529515945455';
18		const LN2 = '0.6931471805599453094172321214581765680755001343602552';
19		const MAX_HASH_FUNCS = '50';
20		const MAX_FILTER_SIZE = 36000; // bytes
21		const TWEAK_START = '4221880213'; // 0xFBA4C795
22
23		const UPDATE_NONE = 0;
24		const UPDATE_ALL = 1;
25		const UPDATE_P2PUBKEY_ONLY = 2;
26		const UPDATE_MASK = 3;
27
28		/**
29		* @var Math
30		*/
31		private $math;
32
33		/**
34		* @var bool
35		*/
36		private $empty = true;
37
38		/**
39		* @var bool
40		*/
41		private $full = false;
42
43		/**
44		* @var int
45		*/
46		private $numHashFuncs;
47
48		/**
49		* @var array
50		*/
51		private $vFilter = [];
52
53		/**
54		* @var int\|string
55		*/
56		private $nTweak;
57
58		/**
59		* @var Flags
60		*/
61		private $flags;
62
63		/**
64		* @param Math $math
65		* @param array $vFilter
66		* @param int $numHashFuncs
67		* @param int\|string $nTweak
68		* @param Flags $flags
69	132	*/
70		public function __construct(Math $math, array $vFilter, $numHashFuncs, $nTweak, Flags $flags)
71	132	{
72	132	$this->math = $math;
73	132	$this->vFilter = $vFilter;
74	132	$this->numHashFuncs = $numHashFuncs;
75	132	$this->nTweak = $nTweak;
76	132	$this->flags = $flags;
77	132	$this->updateEmptyFull();
78		}
79
80		/**
81		* @param int $size
82		* @return array
83	102	*/
84		public static function emptyFilter($size)
85	102	{
86		return str_split(str_pad('', $size, '0'), 1);
87		}
88
89		/**
90		* Create the Bloom Filter given the number of elements, a false positive rate,
91		* and the flags governing how the filter should be updated.
92		*
93		* @param Math $math
94		* @param int $nElements
95		* @param float $nFpRate
96		* @param int $nTweak
97		* @param Flags $flags
98		* @return BloomFilter
99	102	*/
100		public static function create(Math $math, $nElements, $nFpRate, $nTweak, Flags $flags)
101	102	{
102		$size = self::idealSize($nElements, $nFpRate);
103	102
104	102	return new self(
105	102	$math,
106	102	self::emptyFilter($size),
107	102	self::idealNumHashFuncs($size, $nElements),
108		$nTweak,
109	102	$flags
110		);
111		}
112
113		/**
114		* @param int $flag
115		* @return bool
116	36	*/
117	4	public function checkFlag($flag)
118	36	{
119		return $this->math->cmp($this->math->bitwiseAnd($this->flags->getFlags(), self::UPDATE_MASK), $flag) === 0;
120		}
121
122		/**
123		* @return bool
124	6	*/
125		public function isUpdateNone()
126	6	{
127		return $this->checkFlag(self::UPDATE_NONE);
128		}
129
130		/**
131		* @return bool
132	36	*/
133		public function isUpdateAll()
134	36	{
135		return $this->checkFlag(self::UPDATE_ALL);
136		}
137
138		/**
139		* @return bool
140	24	*/
141		public function isUpdatePubKeyOnly()
142	24	{
143		return $this->checkFlag(self::UPDATE_P2PUBKEY_ONLY);
144		}
145
146		/**
147		* @return bool
148	96	*/
149		public function isEmpty()
150	96	{
151		return $this->empty;
152		}
153
154		/**
155		* @return bool
156	120	*/
157		public function isFull()
158	120	{
159		return $this->full;
160		}
161
162		/**
163		* @return array
164	24	*/
165		public function getData()
166	24	{
167		return $this->vFilter;
168		}
169
170		/**
171		* @return int
172	24	*/
173		public function getNumHashFuncs()
174	24	{
175		return $this->numHashFuncs;
176		}
177
178		/**
179		* @return int\|string
180	24	*/
181		public function getTweak()
182	24	{
183		return $this->nTweak;
184		}
185
186		/**
187		* @return Flags
188	24	*/
189		public function getFlags()
190	24	{
191		return $this->flags;
192		}
193
194		/**
195		* @param int $nElements
196		* @param float $fpRate
197		* @return int
198	102	*/
199		public static function idealSize($nElements, $fpRate)
200	102	{
201	102	return (int) floor(
202	102	bcdiv(
203	102	min(
204	102	bcmul(
205	102	bcmul(
206	102	bcdiv(
207		-1,
208	102	self::LN2SQUARED
209		),
210	102	$nElements
211	102	),
212	102	log($fpRate)
213	102	),
214	102	bcmul(
215		self::MAX_FILTER_SIZE,
216	102	8
217	102	)
218		),
219	102	8
220	102	)
221		);
222		}
223
224		/**
225		* @param int $filterSize
226		* @param int $nElements
227		* @return int
228	102	*/
229		public static function idealNumHashFuncs($filterSize, $nElements)
230	102	{
231	102	return (int) floor(
232	102	min(
233	102	bcmul(
234	102	bcdiv(
235	102	bcmul(
236		$filterSize,
237	102	8
238		),
239	102	$nElements
240		),
241	102	self::LN2
242	102	),
243	102	bcmul(
244		self::MAX_FILTER_SIZE,
245	102	8
246	102	)
247	102	)
248		);
249		}
250
251		/**
252		* @param int $nHashNum
253		* @param Buffer $data
254		* @return string
255	78	*/
256		public function hash($nHashNum, Buffer $data)
257	78	{
258	78	return $this->math->mod(
259	78	Hash::murmur3($data, ($nHashNum * self::TWEAK_START + $this->nTweak) & 0xffffffff)->getInt(),
260	78	count($this->vFilter) * 8
261		);
262		}
263
264		/**
265		* @param Buffer $data
266		* @return $this
267	84	*/
268		public function insertData(Buffer $data)
269	84	{
270	6	if ($this->isFull()) {
271		return $this;
272		}
273	78
274	78	for ($i = 0; $i < $this->numHashFuncs; $i++) {
275	78	$index = $this->hash($i, $data);
276	78	$this->vFilter[$index >> 3] \|= (1 << (7 & $index));
277		}
278	78
279	78	$this->updateEmptyFull();
280		return $this;
281		}
282
283		/**
284		* @param OutPointInterface $outPoint
285		* @return BloomFilter
286		*/
287	24	public function insertOutPoint(OutPointInterface $outPoint)
288		{
289	24	return $this->insertData($outPoint->getBuffer());
290		}
291
292		/**
293		* @param Buffer $data
294		* @return bool
295		*/
296	42	public function containsData(Buffer $data)
297		{
298	42	if ($this->isFull()) {
299		return true;
300		}
301
302		if ($this->isEmpty()) {
303		return false;
304		}
305	84
306		for ($i = 0; $i < $this->numHashFuncs; $i++) {
307	84	$index = $this->hash($i, $data);
308	6
309		if (!($this->vFilter[($index >> 3)] & (1 << (7 & $index)))) {
310		return false;
311	78	}
312	6	}
313
314		return true;
315	72	}
316	72
317		/**
318	72	* @param OutPointInterface $outPoint
319	72	* @return bool
320		*/
321	72	public function containsOutPoint(OutPointInterface $outPoint)
322		{
323	72	return $this->containsData($outPoint->getBuffer());
324		}
325
326		/**
327		* @return bool
328		*/
329		public function hasAcceptableSize()
330		{
331	30	return count($this->vFilter) <= self::MAX_FILTER_SIZE && $this->numHashFuncs <= self::MAX_HASH_FUNCS;
332		}
333	30
334		/**
335		* @param TransactionInterface $tx
336		* @return bool
337		*/
338		public function isRelevantAndUpdate(TransactionInterface $tx)
339	6	{
340		$this->updateEmptyFull();
341	6	$found = false;
342		if ($this->isFull()) {
343		return true;
344		}
345
346		if ($this->isEmpty()) {
347		return false;
348	72	}
349
350	72	// Check if the txid hash is in the filter
351	72	$txHash = $tx->getTxId();
352	72	if ($this->containsData($txHash)) {
353	6	$found = true;
354		}
355
356	66	// Check for relevant output scripts. We add the outpoint to the filter if found.
357	12	foreach ($tx->getOutputs() as $vout => $output) {
358		$script = $output->getScript();
359		$parser = $script->getScriptParser();
360		foreach ($parser as $exec) {
361	54	if ($exec->isPush() && $this->containsData($exec->getData())) {
362	54	$found = true;
363	42	if ($this->isUpdateAll()) {
364	42	$this->insertOutPoint($tx->makeOutPoint($vout));
365		} else if ($this->isUpdatePubKeyOnly()) {
366		$type = ScriptFactory::scriptPubKey()->classify($script);
367	54	if ($type->isMultisig() \|\| $type->isPayToPublicKey()) {
368	54	$this->insertOutPoint($tx->makeOutPoint($vout));
369	54	}
370	54	}
371	54	}
372	30	}
373	30	}
374	12
375	30	if ($found) {
376	12	return true;
377	12	}
378	12
379	12	foreach ($tx->getInputs() as $txIn) {
380	12	if ($this->containsOutPoint($txIn->getOutPoint())) {
381	30	return true;
382	54	}
383	54
384		$parser = $txIn->getScript()->getScriptParser();
385	54	foreach ($parser as $exec) {
386	54	if ($exec->isPush() > 0 && $this->containsData($exec->getData())) {
387		return true;
388		}
389	30	}
390	30	}
391	12
392		return false;
393		}
394	30
395	30	/**
396	30	*
397	6	*/
398		public function updateEmptyFull()
399	30	{
400	30	$full = true;
401		$empty = true;
402	30	for ($i = 0, $size = count($this->vFilter); $i < $size; $i++) {
403		$byte = (int) $this->vFilter[$i];
404		$full &= ($byte === 0xff);
405		$empty &= ($byte === 0x0);
406		}
407
408	132	$this->full = (bool)$full;
409		$this->empty = (bool)$empty;
410	132	}
411	132
412	132	/**
413	132	* @return Buffer
414	132	*/
415	132	public function getBuffer()
416	132	{
417		return (new BloomFilterSerializer())->serialize($this);
418	132	}
419		}
420

Bit-Wasp / bitcoin-php

Push — master ( 410ea8...0c9ae2 )

BloomFilter::containsOutPoint() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like