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 : 1379 : std::string CBlockFileInfo::ToString() const
11 : : {
12 [ + - + - ]: 2758 : return strprintf("CBlockFileInfo(blocks=%u, size=%u, heights=%u...%u, time=%s...%s)", nBlocks, nSize, nHeightFirst, nHeightLast, FormatISO8601Date(nTimeFirst), FormatISO8601Date(nTimeLast));
13 : : }
14 : :
15 : 1 : std::string CBlockIndex::ToString() const
16 : : {
17 : 1 : return strprintf("CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)",
18 [ + - + - ]: 2 : pprev, nHeight, hashMerkleRoot.ToString(), GetBlockHash().ToString());
19 : : }
20 : :
21 : 990220 : void CChain::SetTip(CBlockIndex& block)
22 : : {
23 : 990220 : CBlockIndex* pindex = █
24 : 990220 : vChain.resize(pindex->nHeight + 1);
25 [ + + + + ]: 280757502 : while (pindex && vChain[pindex->nHeight] != pindex) {
26 : 278777062 : vChain[pindex->nHeight] = pindex;
27 : 278777062 : pindex = pindex->pprev;
28 : : }
29 : 990220 : }
30 : :
31 : 7079 : std::vector<uint256> LocatorEntries(const CBlockIndex* index)
32 : : {
33 : 7079 : int step = 1;
34 : 7079 : std::vector<uint256> have;
35 [ + + ]: 7079 : if (index == nullptr) return have;
36 : :
37 [ + - ]: 7077 : have.reserve(32);
38 [ + - ]: 107865 : while (index) {
39 [ + - ]: 107865 : have.emplace_back(index->GetBlockHash());
40 [ + + ]: 107865 : if (index->nHeight == 0) break;
41 : : // Exponentially larger steps back, plus the genesis block.
42 [ + + ]: 100788 : int height = std::max(index->nHeight - step, 0);
43 : : // Use skiplist.
44 : 100788 : index = index->GetAncestor(height);
45 [ + + ]: 100788 : if (have.size() > 10) step *= 2;
46 : : }
47 : : return have;
48 : 0 : }
49 : :
50 : 7065 : CBlockLocator GetLocator(const CBlockIndex* index)
51 : : {
52 : 7065 : return CBlockLocator{LocatorEntries(index)};
53 : : }
54 : :
55 : 4253 : CBlockLocator CChain::GetLocator() const
56 : : {
57 [ + + ]: 8505 : return ::GetLocator(Tip());
58 : : }
59 : :
60 : 263887 : const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const {
61 [ + + ]: 263887 : if (pindex == nullptr) {
62 : : return nullptr;
63 : : }
64 [ + + ]: 263357 : if (pindex->nHeight > Height())
65 : 131887 : pindex = pindex->GetAncestor(Height());
66 [ + + + + ]: 283001 : while (pindex && !Contains(pindex))
67 : 19644 : pindex = pindex->pprev;
68 : : return pindex;
69 : : }
70 : :
71 : 11082 : CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime, int height) const
72 : : {
73 : 11082 : std::pair<int64_t, int> blockparams = std::make_pair(nTime, height);
74 : 11082 : std::vector<CBlockIndex*>::const_iterator lower = std::lower_bound(vChain.begin(), vChain.end(), blockparams,
75 [ + + + + ]: 172164 : [](CBlockIndex* pBlock, const std::pair<int64_t, int>& blockparams) -> bool { return pBlock->GetBlockTimeMax() < blockparams.first || pBlock->nHeight < blockparams.second; });
76 [ + + ]: 11082 : return (lower == vChain.end() ? nullptr : *lower);
77 : : }
78 : :
79 : : /** Turn the lowest '1' bit in the binary representation of a number into a '0'. */
80 : 142983812 : 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 : 143059734 : int static inline GetSkipHeight(int height) {
84 [ + + ]: 143059734 : if (height < 2)
85 : : 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 [ + + ]: 142983812 : return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height);
91 : : }
92 : :
93 : 14326491 : const CBlockIndex* CBlockIndex::GetAncestor(int height) const
94 : : {
95 [ + + + + ]: 14326491 : if (height > nHeight || height < 0) {
96 : : return nullptr;
97 : : }
98 : :
99 : : const CBlockIndex* pindexWalk = this;
100 : : int heightWalk = nHeight;
101 [ + + ]: 80505000 : while (heightWalk > height) {
102 : 67864471 : int heightSkip = GetSkipHeight(heightWalk);
103 : 67864471 : int heightSkipPrev = GetSkipHeight(heightWalk - 1);
104 [ + + + + ]: 67864471 : if (pindexWalk->pskip != nullptr &&
105 [ + + ]: 63270004 : (heightSkip == height ||
106 [ + + + + ]: 30930975 : (heightSkip > height && !(heightSkipPrev < heightSkip - 2 &&
107 : : heightSkipPrev >= height)))) {
108 : : // Only follow pskip if pprev->pskip isn't better than pskip->pprev.
109 : : pindexWalk = pindexWalk->pskip;
110 : : heightWalk = heightSkip;
111 : : } else {
112 [ - + ]: 34356060 : assert(pindexWalk->pprev);
113 : : pindexWalk = pindexWalk->pprev;
114 : : heightWalk--;
115 : : }
116 : : }
117 : : return pindexWalk;
118 : : }
119 : :
120 : 7773335 : CBlockIndex* CBlockIndex::GetAncestor(int height)
121 : : {
122 : 7773335 : return const_cast<CBlockIndex*>(static_cast<const CBlockIndex*>(this)->GetAncestor(height));
123 : : }
124 : :
125 : 7331126 : void CBlockIndex::BuildSkip()
126 : : {
127 [ + + ]: 7331126 : if (pprev)
128 : 7330792 : pskip = pprev->GetAncestor(GetSkipHeight(nHeight));
129 : 7331126 : }
130 : :
131 : 700957 : arith_uint256 GetBlockProof(const CBlockIndex& block)
132 : : {
133 : 700957 : arith_uint256 bnTarget;
134 : 700957 : bool fNegative;
135 : 700957 : bool fOverflow;
136 : 700957 : bnTarget.SetCompact(block.nBits, &fNegative, &fOverflow);
137 [ + - + - : 1401914 : if (fNegative || fOverflow || bnTarget == 0)
+ + ]
138 : 29 : 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 : 2102784 : return (~bnTarget / (bnTarget + 1)) + 1;
144 : : }
145 : :
146 : 1374 : int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params& params)
147 : : {
148 : 1374 : arith_uint256 r;
149 : 1374 : int sign = 1;
150 [ + + ]: 1374 : if (to.nChainWork > from.nChainWork) {
151 [ + + ]: 8940 : r = to.nChainWork - from.nChainWork;
152 : : } else {
153 [ + + ]: 4800 : r = from.nChainWork - to.nChainWork;
154 : : sign = -1;
155 : : }
156 [ + + ]: 15114 : r = r * arith_uint256(params.nPowTargetSpacing) / GetBlockProof(tip);
157 [ - + ]: 1374 : if (r.bits() > 63) {
158 : 0 : return sign * std::numeric_limits<int64_t>::max();
159 : : }
160 : 1374 : return sign * int64_t(r.GetLow64());
161 : : }
162 : :
163 : : /** Find the last common ancestor two blocks have.
164 : : * Both pa and pb must be non-nullptr. */
165 : 210338 : const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb) {
166 [ - + ]: 210338 : if (pa->nHeight > pb->nHeight) {
167 : 0 : pa = pa->GetAncestor(pb->nHeight);
168 [ + + ]: 210338 : } else if (pb->nHeight > pa->nHeight) {
169 : 95378 : pb = pb->GetAncestor(pa->nHeight);
170 : : }
171 : :
172 [ + + + - ]: 240296 : while (pa != pb && pa && pb) {
173 : 29958 : pa = pa->pprev;
174 : 29958 : pb = pb->pprev;
175 : : }
176 : :
177 : : // Eventually all chain branches meet at the genesis block.
178 [ - + ]: 210338 : assert(pa == pb);
179 : 210338 : return pa;
180 : : }
|
