Branch data Line data Source code
1 : : // Copyright (c) 2009-2010 Satoshi Nakamoto 2 : : // Copyright (c) 2009-2022 The Bitcoin Core developers 3 : : // Distributed under the MIT software license, see the accompanying 4 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php. 5 : : 6 : : #include <chain.h> 7 : : #include <tinyformat.h> 8 : : #include <util/time.h> 9 : : 10 : 2055 : std::string CBlockFileInfo::ToString() const 11 : : { 12 [ + - - + ]: 2055 : return strprintf("CBlockFileInfo(blocks=%u, size=%u, heights=%u...%u, time=%s...%s)", nBlocks, nSize, nHeightFirst, nHeightLast, FormatISO8601Date(nTimeFirst), FormatISO8601Date(nTimeLast)); 13 : 0 : } 14 : : 15 : 83 : std::string CBlockIndex::ToString() const 16 : : { 17 [ - + ]: 83 : return strprintf("CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)", 18 [ + - + - ]: 83 : pprev, nHeight, hashMerkleRoot.ToString(), GetBlockHash().ToString()); 19 : 0 : } 20 : : 21 : 85235 : void CChain::SetTip(CBlockIndex& block) 22 : : { 23 : 85235 : CBlockIndex* pindex = █ 24 : 85235 : vChain.resize(pindex->nHeight + 1); 25 [ + + + + ]: 170470 : while (pindex && vChain[pindex->nHeight] != pindex) { 26 : 85235 : vChain[pindex->nHeight] = pindex; 27 : 85235 : pindex = pindex->pprev; 28 : : } 29 : 85235 : } 30 : : 31 : 342536 : std::vector<uint256> LocatorEntries(const CBlockIndex* index) 32 : : { 33 : 342536 : int step = 1; 34 : 342536 : std::vector<uint256> have; 35 [ + - ]: 342536 : if (index == nullptr) return have; 36 : : 37 [ + - ]: 342536 : have.reserve(32); 38 [ - + ]: 2016258 : while (index) { 39 [ + - + - ]: 2016258 : have.emplace_back(index->GetBlockHash()); 40 [ + + ]: 2016258 : if (index->nHeight == 0) break; 41 : : // Exponentially larger steps back, plus the genesis block. 42 [ + - ]: 1673722 : int height = std::max(index->nHeight - step, 0); 43 : : // Use skiplist. 44 [ + - ]: 1673722 : index = index->GetAncestor(height); 45 [ + + ]: 1673722 : if (have.size() > 10) step *= 2; 46 : 1673722 : } 47 : 342536 : return have; 48 [ + - ]: 342536 : } 49 : : 50 : 122629 : CBlockLocator GetLocator(const CBlockIndex* index) 51 : : { 52 [ + - ]: 122629 : return CBlockLocator{LocatorEntries(index)}; 53 : 0 : } 54 : : 55 : 114473 : CBlockLocator CChain::GetLocator() const 56 : : { 57 : 114473 : return ::GetLocator(Tip()); 58 : : } 59 : : 60 : 185677 : const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const { 61 [ + + ]: 185677 : if (pindex == nullptr) { 62 : 2055 : return nullptr; 63 : : } 64 [ + + ]: 183622 : if (pindex->nHeight > Height()) 65 : 92838 : pindex = pindex->GetAncestor(Height()); 66 [ + + - + ]: 183622 : while (pindex && !Contains(pindex)) 67 : 0 : pindex = pindex->pprev; 68 : 183622 : return pindex; 69 : 185677 : } 70 : : 71 : 0 : CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime, int height) const 72 : : { 73 : 0 : std::pair<int64_t, int> blockparams = std::make_pair(nTime, height); 74 : 1 : std::vector<CBlockIndex*>::const_iterator lower = std::lower_bound(vChain.begin(), vChain.end(), blockparams, 75 [ # # ]: 0 : [](CBlockIndex* pBlock, const std::pair<int64_t, int>& blockparams) -> bool { return pBlock->GetBlockTimeMax() < blockparams.first || pBlock->nHeight < blockparams.second; }); 76 [ # # ]: 0 : return (lower == vChain.end() ? nullptr : *lower); 77 : 0 : } 78 : : 79 : : /** Turn the lowest '1' bit in the binary representation of a number into a '0'. */ 80 : 27657433 : int static inline InvertLowestOne(int n) { return n & (n - 1); } 81 : : 82 : : /** Compute what height to jump back to with the CBlockIndex::pskip pointer. */ 83 : 18693973 : int static inline GetSkipHeight(int height) { 84 [ + + ]: 18693973 : if (height < 2) 85 : 245468 : return 0; 86 : : 87 : : // Determine which height to jump back to. Any number strictly lower than height is acceptable, 88 : : // but the following expression seems to perform well in simulations (max 110 steps to go back 89 : : // up to 2**18 blocks). 90 [ + + ]: 18448505 : return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height); 91 : 18693973 : } 92 : : 93 : 3050151 : const CBlockIndex* CBlockIndex::GetAncestor(int height) const 94 : : { 95 [ + + + + ]: 3050151 : if (height > nHeight || height < 0) { 96 : 128774 : return nullptr; 97 : : } 98 : : 99 : 2921377 : const CBlockIndex* pindexWalk = this; 100 : 2921377 : int heightWalk = nHeight; 101 [ + + ]: 12098606 : while (heightWalk > height) { 102 : 9177229 : int heightSkip = GetSkipHeight(heightWalk); 103 : 9177229 : int heightSkipPrev = GetSkipHeight(heightWalk - 1); 104 [ + + + + ]: 9819033 : if (pindexWalk->pskip != nullptr && 105 [ + + ]: 8673391 : (heightSkip == height || 106 [ + + + + ]: 7997363 : (heightSkip > height && !(heightSkipPrev < heightSkip - 2 && 107 : 641804 : heightSkipPrev >= height)))) { 108 : : // Only follow pskip if pprev->pskip isn't better than pskip->pprev. 109 : 3590174 : pindexWalk = pindexWalk->pskip; 110 : 3590174 : heightWalk = heightSkip; 111 : 3590174 : } else { 112 [ + - ]: 5587055 : assert(pindexWalk->pprev); 113 : 5587055 : pindexWalk = pindexWalk->pprev; 114 : 5587055 : heightWalk--; 115 : : } 116 : 9177229 : } 117 : 2921377 : return pindexWalk; 118 : 3050151 : } 119 : : 120 : 894218 : CBlockIndex* CBlockIndex::GetAncestor(int height) 121 : : { 122 : 894218 : return const_cast<CBlockIndex*>(static_cast<const CBlockIndex*>(this)->GetAncestor(height)); 123 : : } 124 : : 125 : 339822 : void CBlockIndex::BuildSkip() 126 : : { 127 [ + + ]: 339822 : if (pprev) 128 : 339515 : pskip = pprev->GetAncestor(GetSkipHeight(nHeight)); 129 : 339822 : } 130 : : 131 : 853549 : arith_uint256 GetBlockProof(const CBlockIndex& block) 132 : : { 133 : 853549 : arith_uint256 bnTarget; 134 : 853549 : bool fNegative; 135 : 853549 : bool fOverflow; 136 : 853549 : bnTarget.SetCompact(block.nBits, &fNegative, &fOverflow); 137 [ + + + + : 853549 : if (fNegative || fOverflow || bnTarget == 0) + + ] 138 : 211821 : return 0; 139 : : // We need to compute 2**256 / (bnTarget+1), but we can't represent 2**256 140 : : // as it's too large for an arith_uint256. However, as 2**256 is at least as large 141 : : // as bnTarget+1, it is equal to ((2**256 - bnTarget - 1) / (bnTarget+1)) + 1, 142 : : // or ~bnTarget / (bnTarget+1) + 1. 143 : 641728 : return (~bnTarget / (bnTarget + 1)) + 1; 144 : 853549 : } 145 : : 146 : 144524 : int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params& params) 147 : : { 148 : 144524 : arith_uint256 r; 149 : 144524 : int sign = 1; 150 [ + + ]: 144524 : if (to.nChainWork > from.nChainWork) { 151 : 40029 : r = to.nChainWork - from.nChainWork; 152 : 40029 : } else { 153 : 104495 : r = from.nChainWork - to.nChainWork; 154 : 104495 : sign = -1; 155 : : } 156 : 144524 : r = r * arith_uint256(params.nPowTargetSpacing) / GetBlockProof(tip); 157 [ + + ]: 144524 : if (r.bits() > 63) { 158 : 24082 : return sign * std::numeric_limits<int64_t>::max(); 159 : : } 160 : 40384 : return sign * int64_t(r.GetLow64()); 161 : 64466 : } 162 : : 163 : : /** Find the last common ancestor two blocks have. 164 : : * Both pa and pb must be non-nullptr. */ 165 : 12118 : const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb) { 166 [ - + ]: 12118 : if (pa->nHeight > pb->nHeight) { 167 : 0 : pa = pa->GetAncestor(pb->nHeight); 168 [ + + ]: 12118 : } else if (pb->nHeight > pa->nHeight) { 169 : 11071 : pb = pb->GetAncestor(pa->nHeight); 170 : 11071 : } 171 : : 172 [ + + - + : 12119 : while (pa != pb && pa && pb) { + + ] 173 : 1 : pa = pa->pprev; 174 : 1 : pb = pb->pprev; 175 : : } 176 : : 177 : : // Eventually all chain branches meet at the genesis block. 178 [ + - ]: 12118 : assert(pa == pb); 179 : 12118 : return pa; 180 : : }