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 : 2324 : std::string CBlockFileInfo::ToString() const
11 : : {
12 [ + - + - ]: 4648 : return strprintf("CBlockFileInfo(blocks=%u, size=%u, heights=%u...%u, time=%s...%s)", nBlocks, nSize, nHeightFirst, nHeightLast, FormatISO8601Date(nTimeFirst), FormatISO8601Date(nTimeLast));
13 : : }
14 : :
15 : 219 : std::string CBlockIndex::ToString() const
16 : : {
17 : 219 : return strprintf("CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)",
18 [ + - + - ]: 438 : pprev, nHeight, hashMerkleRoot.ToString(), GetBlockHash().ToString());
19 : : }
20 : :
21 : 832899 : void CChain::SetTip(CBlockIndex& block)
22 : : {
23 : 832899 : CBlockIndex* pindex = █
24 : 832899 : vChain.resize(pindex->nHeight + 1);
25 [ + + + + ]: 46386844 : while (pindex && vChain[pindex->nHeight] != pindex) {
26 : 44721046 : vChain[pindex->nHeight] = pindex;
27 : 44721046 : pindex = pindex->pprev;
28 : : }
29 : 832899 : }
30 : :
31 : 435015 : std::vector<uint256> LocatorEntries(const CBlockIndex* index)
32 : : {
33 : 435015 : int step = 1;
34 : 435015 : std::vector<uint256> have;
35 [ + - ]: 435015 : if (index == nullptr) return have;
36 : :
37 [ + - ]: 435015 : have.reserve(32);
38 [ + - ]: 2447050 : while (index) {
39 [ + - ]: 2447050 : have.emplace_back(index->GetBlockHash());
40 [ + + ]: 2447050 : if (index->nHeight == 0) break;
41 : : // Exponentially larger steps back, plus the genesis block.
42 [ + + ]: 2012035 : int height = std::max(index->nHeight - step, 0);
43 : : // Use skiplist.
44 [ + - ]: 2012035 : index = index->GetAncestor(height);
45 [ - + + + ]: 2012035 : if (have.size() > 10) step *= 2;
46 : : }
47 : : return have;
48 : 0 : }
49 : :
50 : 168997 : CBlockLocator GetLocator(const CBlockIndex* index)
51 : : {
52 : 168997 : return CBlockLocator{LocatorEntries(index)};
53 : : }
54 : :
55 : 307268 : const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const {
56 [ + + ]: 307268 : if (pindex == nullptr) {
57 : : return nullptr;
58 : : }
59 [ - + + + ]: 304944 : if (pindex->nHeight > Height())
60 : 154681 : pindex = pindex->GetAncestor(Height());
61 [ + + - + ]: 304944 : while (pindex && !Contains(pindex))
62 : 0 : pindex = pindex->pprev;
63 : : return pindex;
64 : : }
65 : :
66 : 0 : CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime, int height) const
67 : : {
68 : 0 : std::pair<int64_t, int> blockparams = std::make_pair(nTime, height);
69 : 0 : std::vector<CBlockIndex*>::const_iterator lower = std::lower_bound(vChain.begin(), vChain.end(), blockparams,
70 [ # # # # ]: 0 : [](CBlockIndex* pBlock, const std::pair<int64_t, int>& blockparams) -> bool { return pBlock->GetBlockTimeMax() < blockparams.first || pBlock->nHeight < blockparams.second; });
71 [ # # ]: 0 : return (lower == vChain.end() ? nullptr : *lower);
72 : : }
73 : :
74 : : /** Turn the lowest '1' bit in the binary representation of a number into a '0'. */
75 : 32394823 : int static inline InvertLowestOne(int n) { return n & (n - 1); }
76 : :
77 : : /** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
78 : 32718925 : int static inline GetSkipHeight(int height) {
79 [ + + ]: 32718925 : if (height < 2)
80 : : return 0;
81 : :
82 : : // Determine which height to jump back to. Any number strictly lower than height is acceptable,
83 : : // but the following expression seems to perform well in simulations (max 110 steps to go back
84 : : // up to 2**18 blocks).
85 [ + + ]: 32394823 : return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height);
86 : : }
87 : :
88 : 7126408 : const CBlockIndex* CBlockIndex::GetAncestor(int height) const
89 : : {
90 [ + + + + ]: 7126408 : if (height > nHeight || height < 0) {
91 : : return nullptr;
92 : : }
93 : :
94 : : const CBlockIndex* pindexWalk = this;
95 : : int heightWalk = nHeight;
96 [ + + ]: 20748871 : while (heightWalk > height) {
97 : 16186034 : int heightSkip = GetSkipHeight(heightWalk);
98 : 16186034 : int heightSkipPrev = GetSkipHeight(heightWalk - 1);
99 [ + + + + ]: 16186034 : if (pindexWalk->pskip != nullptr &&
100 [ + + ]: 14176514 : (heightSkip == height ||
101 [ + + + + ]: 6388877 : (heightSkip > height && !(heightSkipPrev < heightSkip - 2 &&
102 : : heightSkipPrev >= height)))) {
103 : : // Only follow pskip if pprev->pskip isn't better than pskip->pprev.
104 : : pindexWalk = pindexWalk->pskip;
105 : : heightWalk = heightSkip;
106 : : } else {
107 [ - + ]: 8651909 : assert(pindexWalk->pprev);
108 : : pindexWalk = pindexWalk->pprev;
109 : : heightWalk--;
110 : : }
111 : : }
112 : : return pindexWalk;
113 : : }
114 : :
115 : 3272899 : CBlockIndex* CBlockIndex::GetAncestor(int height)
116 : : {
117 : 3272899 : return const_cast<CBlockIndex*>(static_cast<const CBlockIndex*>(this)->GetAncestor(height));
118 : : }
119 : :
120 : 347234 : void CBlockIndex::BuildSkip()
121 : : {
122 [ + + ]: 347234 : if (pprev)
123 : 346857 : pskip = pprev->GetAncestor(GetSkipHeight(nHeight));
124 : 347234 : }
125 : :
126 : 1482517 : arith_uint256 GetBlockProof(const CBlockIndex& block)
127 : : {
128 : 1482517 : arith_uint256 bnTarget;
129 : 1482517 : bool fNegative;
130 : 1482517 : bool fOverflow;
131 : 1482517 : bnTarget.SetCompact(block.nBits, &fNegative, &fOverflow);
132 [ + + + + : 2746822 : if (fNegative || fOverflow || bnTarget == 0)
+ + ]
133 : 292608 : return 0;
134 : : // We need to compute 2**256 / (bnTarget+1), but we can't represent 2**256
135 : : // as it's too large for an arith_uint256. However, as 2**256 is at least as large
136 : : // as bnTarget+1, it is equal to ((2**256 - bnTarget - 1) / (bnTarget+1)) + 1,
137 : : // or ~bnTarget / (bnTarget+1) + 1.
138 : 3569727 : return (~bnTarget / (bnTarget + 1)) + 1;
139 : : }
140 : :
141 : 197382 : int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params& params)
142 : : {
143 : 197382 : arith_uint256 r;
144 : 197382 : int sign = 1;
145 [ + + ]: 197382 : if (to.nChainWork > from.nChainWork) {
146 [ + + ]: 571750 : r = to.nChainWork - from.nChainWork;
147 : : } else {
148 [ + + ]: 1402070 : r = from.nChainWork - to.nChainWork;
149 : : sign = -1;
150 : : }
151 [ + + ]: 1181940 : r = r * arith_uint256(params.nPowTargetSpacing) / GetBlockProof(tip);
152 [ + + ]: 87464 : if (r.bits() > 63) {
153 : 35575 : return sign * std::numeric_limits<int64_t>::max();
154 : : }
155 : 51889 : return sign * int64_t(r.GetLow64());
156 : : }
157 : :
158 : : /** Find the last common ancestor two blocks have.
159 : : * Both pa and pb must be non-nullptr. */
160 : 0 : const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb) {
161 [ # # ]: 0 : if (pa->nHeight > pb->nHeight) {
162 : 0 : pa = pa->GetAncestor(pb->nHeight);
163 [ # # ]: 0 : } else if (pb->nHeight > pa->nHeight) {
164 : 0 : pb = pb->GetAncestor(pa->nHeight);
165 : : }
166 : :
167 [ # # # # ]: 0 : while (pa != pb && pa && pb) {
168 : 0 : pa = pa->pprev;
169 : 0 : pb = pb->pprev;
170 : : }
171 : :
172 : : // Eventually all chain branches meet at the genesis block.
173 [ # # ]: 0 : assert(pa == pb);
174 : 0 : return pa;
175 : : }
|
