PartialMerkleTree::traverseAndExtract() - Code Metrics - Inspection of "reduce number of coverage runs to 4 (#306)" - Bit-Wasp/bitcoin-php - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( b2abd4...891c12 )

by thomas

created 2016-05-28 14:29 UTC

PartialMerkleTree::traverseAndExtract() D

↳ Parent: PartialMerkleTree

Complexity

Conditions	9
Paths	7

Size

Total Lines	32
Code Lines	22

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	18
CRAP Score	9.8322

Importance

Changes

Metric	Value
cc	9
eloc	22
nc	7
nop	5
dl	0
loc	32
ccs	18
cts	23
cp	0.7826
crap	9.8322
rs	4.909
c	0
b	0
f	0

<?php

namespace BitWasp\Bitcoin\Block;

use BitWasp\Bitcoin\Crypto\Hash;
use BitWasp\Bitcoin\Serializable;
use BitWasp\Bitcoin\Serializer\Block\PartialMerkleTreeSerializer;
use BitWasp\Buffertools\Buffer;
use BitWasp\Buffertools\BufferInterface;
use BitWasp\Buffertools\Buffertools;

class PartialMerkleTree extends Serializable
{
    /**
     * @var int
     */
    private $elementCount;

    /**
     * @var BufferInterface[]
     */
    private $vHashes = [];

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

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

    /**
     * Takes array of hashes and flag array only. Use PartialMerkleTree::create() instead of creating instance directly..
     *
     * @param int $txCount
     * @param array $vHashes
     * @param array $vBits
     */
    public function __construct($txCount = 0, array $vHashes = [], array $vBits = [])
    {
        $this->elementCount = $txCount;
        $this->vHashes = $vHashes;
        $this->vFlagBits = $vBits;
    }

    /**
     * Construct the Merkle tree
     *
     * @param int $txCount
     * @param array $vTxHashes
     * @param array $vMatch
     * @return PartialMerkleTree
     */
    public static function create($txCount, array $vTxHashes, array $vMatch)
    {
        $tree = new self($txCount);
        $tree->traverseAndBuild($tree->calcTreeHeight(), 0, $vTxHashes, $vMatch);
        return $tree;
    }

    /**
     * Calculate tree width for a given height.
     *
     * @param int $height
     * @return int
     */
    public function calcTreeWidth($height)
    {
        return ($this->elementCount + (1 << $height) - 1) >> $height;
    }

    /**
     * Calculate the tree height.
     *
     * @return int
     */
    public function calcTreeHeight()
    {
        $height = 0;
        while ($this->calcTreeWidth($height) > 1) {
            $height++;
        }

        return $height;
    }

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

    /**
     * @return BufferInterface[]
     */
    public function getHashes()
    {
        return $this->vHashes;
    }

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

    /**
     * Calculate the hash for the given $height and $position
     *
     * @param int $height
     * @param int $position
     * @param \BitWasp\Buffertools\BufferInterface[] $vTxid
     * @return \BitWasp\Buffertools\BufferInterface
     */
    public function calculateHash($height, $position, array $vTxid)
    {

        if ($height === 0) {
            return $vTxid[$position];
        } else {
            $left = $this->calculateHash($height - 1, $position * 2, $vTxid);
            if (($position * 2 + 1) < $this->calcTreeWidth($height - 1)) {
                $right = $this->calculateHash($height - 1, ($position * 2 + 1), $vTxid);
            } else {
                $right = $left;
            }

            return Hash::sha256d(Buffertools::concat($left, $right));
        }
    }

    /**
     * Construct the list of Merkle Tree hashes
     *
     * @param int $height
     * @param int $position
     * @param array $vTxid - array of Txid's in the block
     * @param array $vMatch - reference to array to populate
     */
    public function traverseAndBuild($height, $position, array $vTxid, array &$vMatch)
    {
        $parent = false;
        for ($p = $position << $height; $p < ($position + 1) << $height && $p < $this->elementCount; $p++) {
            $parent |= $vMatch[$p];
        }

        $this->vFlagBits[] = $parent;

        if (0 === $height || !$parent) {
            $this->vHashes[] = $this->calculateHash($height, $position, $vTxid);
        } else {
            $this->traverseAndBuild($height - 1, $position * 2, $vTxid, $vMatch);
            if (($position * 2 + 1) < $this->calcTreeWidth($height - 1)) {
                $this->traverseAndBuild($height - 1, $position * 2 + 1, $vTxid, $vMatch);
            }
        }
    }

    /**
     * Traverse the Merkle Tree hashes and extract those which have a matching bit.
     *
     * @param int $height
     * @param int $position
     * @param int $nBitsUsed
     * @param int $nHashUsed
     * @param BufferInterface[] $vMatch
     * @return BufferInterface
     */
    public function traverseAndExtract($height, $position, &$nBitsUsed, &$nHashUsed, &$vMatch)
    {
        if ($nBitsUsed >= count($this->vFlagBits)) {
            $this->fBad = true;
            return new Buffer();
        }

        $parent = $this->vFlagBits[$nBitsUsed++];
        if (0 === $height || !$parent) {
            if ($nHashUsed >= count($this->vHashes)) {
                $this->fBad = true;
                return new Buffer();
            }
            $hash = $this->vHashes[$nHashUsed++];
            if ($height === 0 && $parent) {
                $vMatch[] = $hash->flip();
            }
            return $hash;
        } else {
            $left = $this->traverseAndExtract($height - 1, $position * 2, $nBitsUsed, $nHashUsed, $vMatch);
            if (($position * 2 + 1) < $this->calcTreeWidth($height - 1)) {
                $right = $this->traverseAndExtract($height - 1, ($position * 2 + 1), $nBitsUsed, $nHashUsed, $vMatch);
                if ($right === $left) {
                    $this->fBad = true;
                }
            } else {
                $right = $left;
            }

            return Hash::sha256d(Buffertools::concat($left, $right));
        }
    }

    /**
     * Extract matches from the tree into provided $vMatch reference.
     *
     * @param BufferInterface[] $vMatch - reference to array of extracted 'matching' hashes
     * @return BufferInterface - this will be the merkle root
     * @throws \Exception
     */
    public function extractMatches(array &$vMatch)
    {
        $nTx = $this->getTxCount();
        if (0 === $nTx) {
            throw new \Exception('ntx = 0');
        }

        if ($nTx > BlockInterface::MAX_BLOCK_SIZE / 60) {
            throw new \Exception('ntx > bound size');
        }

        if (count($this->vHashes) > $nTx) {
            throw new \Exception('nHashes > nTx');
        }

        if (count($this->vFlagBits) < count($this->vHashes)) {
            throw new \Exception('nBits < nHashes');
        }

        $height = $this->calcTreeHeight();
        $nBitsUsed = 0;
        $nHashesUsed = 0;
        $merkleRoot = $this->traverseAndExtract($height, 0, $nBitsUsed, $nHashesUsed, $vMatch);
        $merkleRoot = $merkleRoot->flip();
        if ($this->fBad) {
            throw new \Exception('bad data');
        }

        if (ceil(($nBitsUsed + 7) / 8) !== ceil((count($this->vFlagBits)+7)/8)) {
            throw new \Exception('Not all bits consumed');
        }

        if ($nHashesUsed !== count($this->vHashes)) {
            throw new \Exception('Not all hashes consumed');
        }

        return $merkleRoot;
    }

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


1		<?php
2
3		namespace BitWasp\Bitcoin\Block;
4
5		use BitWasp\Bitcoin\Crypto\Hash;
6		use BitWasp\Bitcoin\Serializable;
7		use BitWasp\Bitcoin\Serializer\Block\PartialMerkleTreeSerializer;
8		use BitWasp\Buffertools\Buffer;
9		use BitWasp\Buffertools\BufferInterface;
10		use BitWasp\Buffertools\Buffertools;
11
12		class PartialMerkleTree extends Serializable
13		{
14		/**
15		* @var int
16		*/
17		private $elementCount;
18
19		/**
20		* @var BufferInterface[]
21		*/
22		private $vHashes = [];
23
24		/**
25		* @var array
26		*/
27		private $vFlagBits = [];
28
29		/**
30		* @var bool
31		*/
32		private $fBad = false;
33
34		/**
35		* Takes array of hashes and flag array only. Use PartialMerkleTree::create() instead of creating instance directly..
36		*
37		* @param int $txCount
38		* @param array $vHashes
39		* @param array $vBits
40		*/
41	24	public function __construct($txCount = 0, array $vHashes = [], array $vBits = [])
42		{
43	24	$this->elementCount = $txCount;
44	24	$this->vHashes = $vHashes;
45	24	$this->vFlagBits = $vBits;
46	24	}
47
48		/**
49		* Construct the Merkle tree
50		*
51		* @param int $txCount
52		* @param array $vTxHashes
53		* @param array $vMatch
54		* @return PartialMerkleTree
55		*/
56	24	public static function create($txCount, array $vTxHashes, array $vMatch)
57		{
58	24	$tree = new self($txCount);
59	24	$tree->traverseAndBuild($tree->calcTreeHeight(), 0, $vTxHashes, $vMatch);
60	24	return $tree;
61		}
62
63		/**
64		* Calculate tree width for a given height.
65		*
66		* @param int $height
67		* @return int
68		*/
69	24	public function calcTreeWidth($height)
70		{
71	24	return ($this->elementCount + (1 << $height) - 1) >> $height;
72		}
73
74		/**
75		* Calculate the tree height.
76		*
77		* @return int
78		*/
79	24	public function calcTreeHeight()
80		{
81	24	$height = 0;
82	24	while ($this->calcTreeWidth($height) > 1) {
83	16	$height++;
84	12	}
85
86	24	return $height;
87		}
88
89		/**
90		* @return int
91		*/
92	24	public function getTxCount()
93		{
94	24	return $this->elementCount;
95		}
96
97		/**
98		* @return BufferInterface[]
99		*/
100	16	public function getHashes()
101		{
102	16	return $this->vHashes;
103		}
104
105		/**
106		* @return array
107		*/
108	16	public function getFlagBits()
109		{
110	16	return $this->vFlagBits;
111		}
112
113		/**
114		* Calculate the hash for the given $height and $position
115		*
116		* @param int $height
117		* @param int $position
118		* @param \BitWasp\Buffertools\BufferInterface[] $vTxid
119		* @return \BitWasp\Buffertools\BufferInterface
120		*/
121	24	public function calculateHash($height, $position, array $vTxid)
122		{
123
124	24	if ($height === 0) {
125	24	return $vTxid[$position];
126		} else {
127	16	$left = $this->calculateHash($height - 1, $position * 2, $vTxid);
128	16	if (($position * 2 + 1) < $this->calcTreeWidth($height - 1)) {
129	16	$right = $this->calculateHash($height - 1, ($position * 2 + 1), $vTxid);
130	12	} else {
131		$right = $left;
132		}
133
134	16	return Hash::sha256d(Buffertools::concat($left, $right));
135		}
136		}
137
138		/**
139		* Construct the list of Merkle Tree hashes
140		*
141		* @param int $height
142		* @param int $position
143		* @param array $vTxid - array of Txid's in the block
144		* @param array $vMatch - reference to array to populate
145		*/
146	24	public function traverseAndBuild($height, $position, array $vTxid, array &$vMatch)
147		{
148	24	$parent = false;
149	24	for ($p = $position << $height; $p < ($position + 1) << $height && $p < $this->elementCount; $p++) {
150	24	$parent \|= $vMatch[$p];
151	18	}
152
153	24	$this->vFlagBits[] = $parent;
154
155	24	if (0 === $height \|\| !$parent) {
156	24	$this->vHashes[] = $this->calculateHash($height, $position, $vTxid);
157	18	} else {
158	16	$this->traverseAndBuild($height - 1, $position * 2, $vTxid, $vMatch);
159	16	if (($position * 2 + 1) < $this->calcTreeWidth($height - 1)) {
160	16	$this->traverseAndBuild($height - 1, $position * 2 + 1, $vTxid, $vMatch);
161	12	}
162		}
163	24	}
164
165		/**
166		* Traverse the Merkle Tree hashes and extract those which have a matching bit.
167		*
168		* @param int $height
169		* @param int $position
170		* @param int $nBitsUsed
171		* @param int $nHashUsed
172		* @param BufferInterface[] $vMatch
173		* @return BufferInterface
174		*/
175	24	public function traverseAndExtract($height, $position, &$nBitsUsed, &$nHashUsed, &$vMatch)
176		{
177	24	if ($nBitsUsed >= count($this->vFlagBits)) {
178		$this->fBad = true;
179		return new Buffer();
180		}
181
182	24	$parent = $this->vFlagBits[$nBitsUsed++];
183	24	if (0 === $height \|\| !$parent) {
184	24	if ($nHashUsed >= count($this->vHashes)) {
185		$this->fBad = true;
186		return new Buffer();
187		}
188	24	$hash = $this->vHashes[$nHashUsed++];
189	24	if ($height === 0 && $parent) {
190	24	$vMatch[] = $hash->flip();
191	18	}
192	24	return $hash;
193		} else {
194	16	$left = $this->traverseAndExtract($height - 1, $position * 2, $nBitsUsed, $nHashUsed, $vMatch);
195	16	if (($position * 2 + 1) < $this->calcTreeWidth($height - 1)) {
196	16	$right = $this->traverseAndExtract($height - 1, ($position * 2 + 1), $nBitsUsed, $nHashUsed, $vMatch);
197	16	if ($right === $left) {
198	4	$this->fBad = true;
199		}
200	12	} else {
201	8	$right = $left;
202		}
203
204	16	return Hash::sha256d(Buffertools::concat($left, $right));
205		}
206		}
207
208		/**
209		* Extract matches from the tree into provided $vMatch reference.
210		*
211		* @param BufferInterface[] $vMatch - reference to array of extracted 'matching' hashes
212		* @return BufferInterface - this will be the merkle root
213		* @throws \Exception
214		*/
215	24	public function extractMatches(array &$vMatch)
216		{
217	24	$nTx = $this->getTxCount();
218	24	if (0 === $nTx) {
219		throw new \Exception('ntx = 0');
220		}
221
222	24	if ($nTx > BlockInterface::MAX_BLOCK_SIZE / 60) {
223		throw new \Exception('ntx > bound size');
224		}
225
226	24	if (count($this->vHashes) > $nTx) {
227		throw new \Exception('nHashes > nTx');
228		}
229
230	24	if (count($this->vFlagBits) < count($this->vHashes)) {
231		throw new \Exception('nBits < nHashes');
232		}
233
234	24	$height = $this->calcTreeHeight();
235	24	$nBitsUsed = 0;
236	24	$nHashesUsed = 0;
237	24	$merkleRoot = $this->traverseAndExtract($height, 0, $nBitsUsed, $nHashesUsed, $vMatch);
238	24	$merkleRoot = $merkleRoot->flip();
239	24	if ($this->fBad) {
240		throw new \Exception('bad data');
241		}
242
243	24	if (ceil(($nBitsUsed + 7) / 8) !== ceil((count($this->vFlagBits)+7)/8)) {
244		throw new \Exception('Not all bits consumed');
245		}
246
247	24	if ($nHashesUsed !== count($this->vHashes)) {
248		throw new \Exception('Not all hashes consumed');
249		}
250
251	24	return $merkleRoot;
252		}
253
254		/**
255		* @return BufferInterface
256		*/
257	4	public function getBuffer()
258		{
259	4	return (new PartialMerkleTreeSerializer())->serialize($this);
260		}
261		}
262

Bit-Wasp / bitcoin-php

Push — master ( b2abd4...891c12 )

PartialMerkleTree::traverseAndExtract() D

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like