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