| 48 | } |
| 49 | |
| 50 | uint256 ComputeFastMerkleRoot(const std::vector<uint256>& hashes) { |
| 51 | uint256 result_hash = uint256(); |
| 52 | if (hashes.size() == 0) return result_hash; |
| 53 | |
| 54 | // inner is an array of eagerly computed subtree hashes, indexed by tree |
| 55 | // level (0 being the leaves). |
| 56 | // For example, when count is 25 (11001 in binary), inner[4] is the hash of |
| 57 | // the first 16 leaves, inner[3] of the next 8 leaves, and inner[0] equal to |
| 58 | // the last leaf. The other inner entries are undefined. |
| 59 | // |
| 60 | // First process all leaves into 'inner' values. |
| 61 | uint256 inner[32]; |
| 62 | uint32_t count = 0; |
| 63 | while (count < hashes.size()) { |
| 64 | uint256 temp_hash = hashes[count]; |
| 65 | count++; |
| 66 | // For each of the lower bits in count that are 0, do 1 step. Each |
| 67 | // corresponds to an inner value that existed before processing the |
| 68 | // current leaf, and each needs a hash to combine it. |
| 69 | int level; |
| 70 | for (level = 0; !(count & (((uint32_t)1) << level)); level++) { |
| 71 | MerkleHash_Sha256Midstate(temp_hash, inner[level], temp_hash); |
| 72 | } |
| 73 | // Store the resulting hash at inner position level. |
| 74 | inner[level] = temp_hash; |
| 75 | } |
| 76 | |
| 77 | // Do a final 'sweep' over the rightmost branch of the tree to process |
| 78 | // odd levels, and reduce everything to a single top value. |
| 79 | // Level is the level (counted from the bottom) up to which we've sweeped. |
| 80 | // |
| 81 | // As long as bit number level in count is zero, skip it. It means there |
| 82 | // is nothing left at this level. |
| 83 | int level = 0; |
| 84 | while (!(count & (((uint32_t)1) << level))) { |
| 85 | level++; |
| 86 | } |
| 87 | result_hash = inner[level]; |
| 88 | |
| 89 | while (count != (((uint32_t)1) << level)) { |
| 90 | // If we reach this point, hash is an inner value that is not the top. |
| 91 | // We combine it with itself (Bitcoin's special rule for odd levels in |
| 92 | // the tree) to produce a higher level one. |
| 93 | |
| 94 | // Increment count to the value it would have if two entries at this |
| 95 | // level had existed and propagate the result upwards accordingly. |
| 96 | count += (((uint32_t)1) << level); |
| 97 | level++; |
| 98 | while (!(count & (((uint32_t)1) << level))) { |
| 99 | MerkleHash_Sha256Midstate(result_hash, inner[level], result_hash); |
| 100 | level++; |
| 101 | } |
| 102 | } |
| 103 | // Return result. |
| 104 | return result_hash; |
| 105 | } |