Branch data Line data Source code
# 1 : : // Copyright (c) 2009-2010 Satoshi Nakamoto
# 2 : : // Copyright (c) 2009-2019 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 : : std::string CBlockFileInfo::ToString() const
# 11 : 962 : {
# 12 : 962 : return strprintf("CBlockFileInfo(blocks=%u, size=%u, heights=%u...%u, time=%s...%s)", nBlocks, nSize, nHeightFirst, nHeightLast, FormatISO8601Date(nTimeFirst), FormatISO8601Date(nTimeLast));
# 13 : 962 : }
# 14 : :
# 15 : : std::string CBlockIndex::ToString() const
# 16 : 0 : {
# 17 : 0 : return strprintf("CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)",
# 18 : 0 : pprev, nHeight, hashMerkleRoot.ToString(), GetBlockHash().ToString());
# 19 : 0 : }
# 20 : :
# 21 : : void CChain::SetTip(CBlockIndex& block)
# 22 : 931567 : {
# 23 : 931567 : CBlockIndex* pindex = █
# 24 : 931567 : vChain.resize(pindex->nHeight + 1);
# 25 [ + + ][ + + ]: 1906576 : while (pindex && vChain[pindex->nHeight] != pindex) {
# 26 : 975009 : vChain[pindex->nHeight] = pindex;
# 27 : 975009 : pindex = pindex->pprev;
# 28 : 975009 : }
# 29 : 931567 : }
# 30 : :
# 31 : : std::vector<uint256> LocatorEntries(const CBlockIndex* index)
# 32 : 5138 : {
# 33 : 5138 : int step = 1;
# 34 : 5138 : std::vector<uint256> have;
# 35 [ + + ]: 5138 : if (index == nullptr) return have;
# 36 : :
# 37 : 5132 : have.reserve(32);
# 38 [ + - ]: 65662 : while (index) {
# 39 : 65662 : have.emplace_back(index->GetBlockHash());
# 40 [ + + ]: 65662 : if (index->nHeight == 0) break;
# 41 : : // Exponentially larger steps back, plus the genesis block.
# 42 : 60530 : int height = std::max(index->nHeight - step, 0);
# 43 : : // Use skiplist.
# 44 : 60530 : index = index->GetAncestor(height);
# 45 [ + + ]: 60530 : if (have.size() > 10) step *= 2;
# 46 : 60530 : }
# 47 : 5132 : return have;
# 48 : 5138 : }
# 49 : :
# 50 : : CBlockLocator GetLocator(const CBlockIndex* index)
# 51 : 5119 : {
# 52 : 5119 : return CBlockLocator{std::move(LocatorEntries(index))};
# 53 : 5119 : }
# 54 : :
# 55 : : CBlockLocator CChain::GetLocator() const
# 56 : 2626 : {
# 57 : 2626 : return ::GetLocator(Tip());
# 58 : 2626 : }
# 59 : :
# 60 : 151746 : const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const {
# 61 [ + + ]: 151746 : if (pindex == nullptr) {
# 62 : 486 : return nullptr;
# 63 : 486 : }
# 64 [ + + ]: 151260 : if (pindex->nHeight > Height())
# 65 : 75851 : pindex = pindex->GetAncestor(Height());
# 66 [ + + ][ + + ]: 168706 : while (pindex && !Contains(pindex))
# 67 : 17446 : pindex = pindex->pprev;
# 68 : 151260 : return pindex;
# 69 : 151746 : }
# 70 : :
# 71 : : CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime, int height) const
# 72 : 20874 : {
# 73 : 20874 : std::pair<int64_t, int> blockparams = std::make_pair(nTime, height);
# 74 : 20874 : std::vector<CBlockIndex*>::const_iterator lower = std::lower_bound(vChain.begin(), vChain.end(), blockparams,
# 75 [ + + ][ + + ]: 334877 : [](CBlockIndex* pBlock, const std::pair<int64_t, int>& blockparams) -> bool { return pBlock->GetBlockTimeMax() < blockparams.first || pBlock->nHeight < blockparams.second; });
# 76 [ + + ]: 20874 : return (lower == vChain.end() ? nullptr : *lower);
# 77 : 20874 : }
# 78 : :
# 79 : : /** Turn the lowest '1' bit in the binary representation of a number into a '0'. */
# 80 : 141467736 : 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 : 94366509 : int static inline GetSkipHeight(int height) {
# 84 [ + + ]: 94366509 : if (height < 2)
# 85 : 53808 : 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 [ + + ]: 94312701 : return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height);
# 91 : 94366509 : }
# 92 : :
# 93 : : const CBlockIndex* CBlockIndex::GetAncestor(int height) const
# 94 : 11278472 : {
# 95 [ + + ][ + + ]: 11278472 : if (height > nHeight || height < 0) {
# 96 : 896282 : return nullptr;
# 97 : 896282 : }
# 98 : :
# 99 : 10382190 : const CBlockIndex* pindexWalk = this;
# 100 : 10382190 : int heightWalk = nHeight;
# 101 [ + + ]: 53589397 : while (heightWalk > height) {
# 102 : 43207207 : int heightSkip = GetSkipHeight(heightWalk);
# 103 : 43207207 : int heightSkipPrev = GetSkipHeight(heightWalk - 1);
# 104 [ + + ]: 43207207 : if (pindexWalk->pskip != nullptr &&
# 105 [ + + ]: 43207207 : (heightSkip == height ||
# 106 [ + + ][ + + ]: 43206777 : (heightSkip > height && !(heightSkipPrev < heightSkip - 2 &&
# 107 [ + + ]: 21751071 : heightSkipPrev >= height)))) {
# 108 : : // Only follow pskip if pprev->pskip isn't better than pskip->pprev.
# 109 : 21751071 : pindexWalk = pindexWalk->pskip;
# 110 : 21751071 : heightWalk = heightSkip;
# 111 : 21751071 : } else {
# 112 : 21456136 : assert(pindexWalk->pprev);
# 113 : 0 : pindexWalk = pindexWalk->pprev;
# 114 : 21456136 : heightWalk--;
# 115 : 21456136 : }
# 116 : 43207207 : }
# 117 : 10382190 : return pindexWalk;
# 118 : 11278472 : }
# 119 : :
# 120 : : CBlockIndex* CBlockIndex::GetAncestor(int height)
# 121 : 8265944 : {
# 122 : 8265944 : return const_cast<CBlockIndex*>(static_cast<const CBlockIndex*>(this)->GetAncestor(height));
# 123 : 8265944 : }
# 124 : :
# 125 : : void CBlockIndex::BuildSkip()
# 126 : 7952433 : {
# 127 [ + + ]: 7952433 : if (pprev)
# 128 : 7952095 : pskip = pprev->GetAncestor(GetSkipHeight(nHeight));
# 129 : 7952433 : }
# 130 : :
# 131 : : arith_uint256 GetBlockProof(const CBlockIndex& block)
# 132 : 946762 : {
# 133 : 946762 : arith_uint256 bnTarget;
# 134 : 946762 : bool fNegative;
# 135 : 946762 : bool fOverflow;
# 136 : 946762 : bnTarget.SetCompact(block.nBits, &fNegative, &fOverflow);
# 137 [ - + ][ - + ]: 946762 : if (fNegative || fOverflow || bnTarget == 0)
# [ - + ]
# 138 : 0 : 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 : 946762 : return (~bnTarget / (bnTarget + 1)) + 1;
# 144 : 946762 : }
# 145 : :
# 146 : : int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params& params)
# 147 : 2294 : {
# 148 : 2294 : arith_uint256 r;
# 149 : 2294 : int sign = 1;
# 150 [ + + ]: 2294 : if (to.nChainWork > from.nChainWork) {
# 151 : 1258 : r = to.nChainWork - from.nChainWork;
# 152 : 1258 : } else {
# 153 : 1036 : r = from.nChainWork - to.nChainWork;
# 154 : 1036 : sign = -1;
# 155 : 1036 : }
# 156 : 2294 : r = r * arith_uint256(params.nPowTargetSpacing) / GetBlockProof(tip);
# 157 [ - + ]: 2294 : if (r.bits() > 63) {
# 158 : 0 : return sign * std::numeric_limits<int64_t>::max();
# 159 : 0 : }
# 160 : 2294 : return sign * int64_t(r.GetLow64());
# 161 : 2294 : }
# 162 : :
# 163 : : /** Find the last common ancestor two blocks have.
# 164 : : * Both pa and pb must be non-nullptr. */
# 165 : 156418 : const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb) {
# 166 [ - + ]: 156418 : if (pa->nHeight > pb->nHeight) {
# 167 : 0 : pa = pa->GetAncestor(pb->nHeight);
# 168 [ + + ]: 156418 : } else if (pb->nHeight > pa->nHeight) {
# 169 : 53642 : pb = pb->GetAncestor(pa->nHeight);
# 170 : 53642 : }
# 171 : :
# 172 [ + + ][ + - ]: 164785 : while (pa != pb && pa && pb) {
# [ + - ]
# 173 : 8367 : pa = pa->pprev;
# 174 : 8367 : pb = pb->pprev;
# 175 : 8367 : }
# 176 : :
# 177 : : // Eventually all chain branches meet at the genesis block.
# 178 : 156418 : assert(pa == pb);
# 179 : 0 : return pa;
# 180 : 156418 : }
|
