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/check.h>
9 : :
10 : 0 : std::string CBlockIndex::ToString() const
11 : : {
12 : 0 : return strprintf("CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)",
13 [ # # # # ]: 0 : pprev, nHeight, hashMerkleRoot.ToString(), GetBlockHash().ToString());
14 : : }
15 : :
16 : 930495 : void CChain::SetTip(CBlockIndex& block)
17 : : {
18 : 930495 : CBlockIndex* pindex = █
19 : 930495 : vChain.resize(pindex->nHeight + 1);
20 [ + + + + ]: 240850755 : while (pindex && vChain[pindex->nHeight] != pindex) {
21 : 238989765 : vChain[pindex->nHeight] = pindex;
22 : 238989765 : pindex = pindex->pprev;
23 : : }
24 : 930495 : }
25 : :
26 : 24416 : std::vector<uint256> LocatorEntries(const CBlockIndex* index)
27 : : {
28 : 24416 : int step = 1;
29 : 24416 : std::vector<uint256> have;
30 [ + + ]: 24416 : if (index == nullptr) return have;
31 : :
32 [ + - ]: 24412 : have.reserve(32);
33 [ + - ]: 434268 : while (index) {
34 [ + - ]: 434268 : have.emplace_back(index->GetBlockHash());
35 [ + + ]: 434268 : if (index->nHeight == 0) break;
36 : : // Exponentially larger steps back, plus the genesis block.
37 [ + + ]: 409856 : int height = std::max(index->nHeight - step, 0);
38 : : // Use skiplist.
39 [ + - ]: 409856 : index = index->GetAncestor(height);
40 [ - + + + ]: 409856 : if (have.size() > 10) step *= 2;
41 : : }
42 : : return have;
43 : 0 : }
44 : :
45 : 24390 : CBlockLocator GetLocator(const CBlockIndex* index)
46 : : {
47 : 24390 : return CBlockLocator{LocatorEntries(index)};
48 : : }
49 : :
50 : 242132 : const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const {
51 [ + + ]: 242132 : if (pindex == nullptr) {
52 : : return nullptr;
53 : : }
54 [ - + + + ]: 241648 : if (pindex->nHeight > Height())
55 : 120985 : pindex = pindex->GetAncestor(Height());
56 [ + + + + ]: 262307 : while (pindex && !Contains(pindex))
57 : 20659 : pindex = pindex->pprev;
58 : : return pindex;
59 : : }
60 : :
61 : 10676 : CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime, int height) const
62 : : {
63 : 10676 : std::pair<int64_t, int> blockparams = std::make_pair(nTime, height);
64 : 10676 : std::vector<CBlockIndex*>::const_iterator lower = std::lower_bound(vChain.begin(), vChain.end(), blockparams,
65 [ + + + + ]: 167389 : [](CBlockIndex* pBlock, const std::pair<int64_t, int>& blockparams) -> bool { return pBlock->GetBlockTimeMax() < blockparams.first || pBlock->nHeight < blockparams.second; });
66 [ + + ]: 10676 : return (lower == vChain.end() ? nullptr : *lower);
67 : : }
68 : :
69 : : /** Turn the lowest '1' bit in the binary representation of a number into a '0'. */
70 : 162397723 : int static inline InvertLowestOne(int n) { return n & (n - 1); }
71 : :
72 : : /** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
73 : 162504612 : int static inline GetSkipHeight(int height) {
74 [ + + ]: 162504612 : if (height < 2)
75 : : return 0;
76 : :
77 : : // Determine which height to jump back to. Any number strictly lower than height is acceptable,
78 : : // but the following expression seems to perform well in simulations (max 110 steps to go back
79 : : // up to 2**18 blocks).
80 [ + + ]: 162397723 : return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height);
81 : : }
82 : :
83 : 25776239 : const CBlockIndex* CBlockIndex::GetAncestor(int height) const
84 : : {
85 [ + + + + ]: 25776239 : if (height > nHeight || height < 0) {
86 : : return nullptr;
87 : : }
88 : :
89 : : const CBlockIndex* pindexWalk = this;
90 : : int heightWalk = nHeight;
91 [ + + ]: 91217470 : while (heightWalk > height) {
92 : 77537583 : int heightSkip = GetSkipHeight(heightWalk);
93 : 77537583 : int heightSkipPrev = GetSkipHeight(heightWalk - 1);
94 [ + + + + ]: 77537583 : if (pindexWalk->pskip != nullptr &&
95 [ + + ]: 72646417 : (heightSkip == height ||
96 [ + + + + ]: 35152668 : (heightSkip > height && !(heightSkipPrev < heightSkip - 2 &&
97 : : heightSkipPrev >= height)))) {
98 : : // Only follow pskip if pprev->pskip isn't better than pskip->pprev.
99 : : pindexWalk = pindexWalk->pskip;
100 : : heightWalk = heightSkip;
101 : : } else {
102 [ - + ]: 39542641 : assert(pindexWalk->pprev);
103 : : pindexWalk = pindexWalk->pprev;
104 : : heightWalk--;
105 : : }
106 : : }
107 : : return pindexWalk;
108 : : }
109 : :
110 : 18153721 : CBlockIndex* CBlockIndex::GetAncestor(int height)
111 : : {
112 : 18153721 : return const_cast<CBlockIndex*>(static_cast<const CBlockIndex*>(this)->GetAncestor(height));
113 : : }
114 : :
115 : 7429780 : void CBlockIndex::BuildSkip()
116 : : {
117 [ + + ]: 7429780 : if (pprev)
118 : 7429446 : pskip = pprev->GetAncestor(GetSkipHeight(nHeight));
119 : 7429780 : }
120 : :
121 : 910168 : arith_uint256 GetBlockProof(const CBlockIndex& block)
122 : : {
123 : 910168 : arith_uint256 bnTarget;
124 : 910168 : bool fNegative;
125 : 910168 : bool fOverflow;
126 : 910168 : bnTarget.SetCompact(block.nBits, &fNegative, &fOverflow);
127 [ + - + - : 1820336 : if (fNegative || fOverflow || bnTarget == 0)
+ + ]
128 : 23 : return 0;
129 : : // We need to compute 2**256 / (bnTarget+1), but we can't represent 2**256
130 : : // as it's too large for an arith_uint256. However, as 2**256 is at least as large
131 : : // as bnTarget+1, it is equal to ((2**256 - bnTarget - 1) / (bnTarget+1)) + 1,
132 : : // or ~bnTarget / (bnTarget+1) + 1.
133 : 1820290 : return (~bnTarget / (bnTarget + 1)) + 1;
134 : : }
135 : :
136 : 1374 : int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params& params)
137 : : {
138 : 1374 : arith_uint256 r;
139 : 1374 : int sign = 1;
140 [ + + ]: 1374 : if (to.nChainWork > from.nChainWork) {
141 : 874 : r = to.nChainWork - from.nChainWork;
142 : : } else {
143 : 500 : r = from.nChainWork - to.nChainWork;
144 : 500 : sign = -1;
145 : : }
146 : 2748 : r = r * arith_uint256(params.nPowTargetSpacing) / GetBlockProof(tip);
147 [ - + ]: 1374 : if (r.bits() > 63) {
148 : 0 : return sign * std::numeric_limits<int64_t>::max();
149 : : }
150 : 1374 : return sign * int64_t(r.GetLow64());
151 : : }
152 : :
153 : : /** Find the last common ancestor two blocks have.
154 : : * Both pa and pb must be non-nullptr. */
155 : 252109 : const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb) {
156 : : // First rewind to the last common height (the forking point cannot be past one of the two).
157 [ + + ]: 252109 : if (pa->nHeight > pb->nHeight) {
158 : 92392 : pa = pa->GetAncestor(pb->nHeight);
159 [ + + ]: 159717 : } else if (pb->nHeight > pa->nHeight) {
160 : 51054 : pb = pb->GetAncestor(pa->nHeight);
161 : : }
162 [ + + ]: 966690 : while (pa != pb) {
163 : : // Jump back until pa and pb have a common "skip" ancestor.
164 [ + + ]: 1273107 : while (pa->pskip != pb->pskip) {
165 : : // This logic relies on the property that equal-height blocks have equal-height skip
166 : : // pointers.
167 : 558526 : Assume(pa->nHeight == pb->nHeight);
168 : 558526 : Assume(pa->pskip->nHeight == pb->pskip->nHeight);
169 : 558526 : pa = pa->pskip;
170 : 558526 : pb = pb->pskip;
171 : : }
172 : : // At this point, pa and pb are different, but have equal pskip. The forking point lies in
173 : : // between pa/pb on the one end, and pa->pskip/pb->pskip on the other end.
174 : 714581 : pa = pa->pprev;
175 : 714581 : pb = pb->pprev;
176 : : }
177 : 252109 : return pa;
178 : : }
|
