This implements a constant-space merkle root/path calculator, limited to 2^32 leaves. */
| 24 | |
| 25 | /* This implements a constant-space merkle root/path calculator, limited to 2^32 leaves. */ |
| 26 | static void MerkleComputation(const std::vector<uint256>& leaves, uint256* proot, bool* pmutated, uint32_t branchpos, std::vector<uint256>* pbranch) { |
| 27 | if (pbranch) pbranch->clear(); |
| 28 | if (leaves.size() == 0) { |
| 29 | if (pmutated) *pmutated = false; |
| 30 | if (proot) *proot = uint256(); |
| 31 | return; |
| 32 | } |
| 33 | bool mutated = false; |
| 34 | // count is the number of leaves processed so far. |
| 35 | uint32_t count = 0; |
| 36 | // inner is an array of eagerly computed subtree hashes, indexed by tree |
| 37 | // level (0 being the leaves). |
| 38 | // For example, when count is 25 (11001 in binary), inner[4] is the hash of |
| 39 | // the first 16 leaves, inner[3] of the next 8 leaves, and inner[0] equal to |
| 40 | // the last leaf. The other inner entries are undefined. |
| 41 | uint256 inner[32]; |
| 42 | // Which position in inner is a hash that depends on the matching leaf. |
| 43 | int matchlevel = -1; |
| 44 | // First process all leaves into 'inner' values. |
| 45 | while (count < leaves.size()) { |
| 46 | uint256 h = leaves[count]; |
| 47 | bool matchh = count == branchpos; |
| 48 | count++; |
| 49 | int level; |
| 50 | // For each of the lower bits in count that are 0, do 1 step. Each |
| 51 | // corresponds to an inner value that existed before processing the |
| 52 | // current leaf, and each needs a hash to combine it. |
| 53 | for (level = 0; !(count & (((uint32_t)1) << level)); level++) { |
| 54 | if (pbranch) { |
| 55 | if (matchh) { |
| 56 | pbranch->push_back(inner[level]); |
| 57 | } else if (matchlevel == level) { |
| 58 | pbranch->push_back(h); |
| 59 | matchh = true; |
| 60 | } |
| 61 | } |
| 62 | mutated |= (inner[level] == h); |
| 63 | CHash256().Write(inner[level]).Write(h).Finalize(h); |
| 64 | } |
| 65 | // Store the resulting hash at inner position level. |
| 66 | inner[level] = h; |
| 67 | if (matchh) { |
| 68 | matchlevel = level; |
| 69 | } |
| 70 | } |
| 71 | // Do a final 'sweep' over the rightmost branch of the tree to process |
| 72 | // odd levels, and reduce everything to a single top value. |
| 73 | // Level is the level (counted from the bottom) up to which we've sweeped. |
| 74 | int level = 0; |
| 75 | // As long as bit number level in count is zero, skip it. It means there |
| 76 | // is nothing left at this level. |
| 77 | while (!(count & (((uint32_t)1) << level))) { |
| 78 | level++; |
| 79 | } |
| 80 | uint256 h = inner[level]; |
| 81 | bool matchh = matchlevel == level; |
| 82 | while (count != (((uint32_t)1) << level)) { |
| 83 | // If we reach this point, h is an inner value that is not the top. |