/workdir/bitcoin/src/chain.cpp

Source (jump to first uncovered line)
// Copyright (c) 2009-2010 Satoshi Nakamoto
// Copyright (c) 2009-2022 The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.

#include <chain.h>
#include <tinyformat.h>
#include <util/time.h>

std::string CBlockFileInfo::ToString() const
{
    return strprintf("CBlockFileInfo(blocks=%u, size=%u, heights=%u...%u, time=%s...%s)", nBlocks, nSize, nHeightFirst, nHeightLast, FormatISO8601Date(nTimeFirst), FormatISO8601Date(nTimeLast));
}

std::string CBlockIndex::ToString() const
{
    return strprintf("CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)",
                     pprev, nHeight, hashMerkleRoot.ToString(), GetBlockHash().ToString());
}

void CChain::SetTip(CBlockIndex& block)
{
    CBlockIndex* pindex = &block;
    vChain.resize(pindex->nHeight + 1);
    while (pindex && vChain[pindex->nHeight] != pindex) {
        vChain[pindex->nHeight] = pindex;
        pindex = pindex->pprev;
    }
}

std::vector<uint256> LocatorEntries(const CBlockIndex* index)
{
    int step = 1;
    std::vector<uint256> have;
    if (index == nullptr) return have;

    have.reserve(32);
    while (index) {
        have.emplace_back(index->GetBlockHash());
        if (index->nHeight == 0) break;
        // Exponentially larger steps back, plus the genesis block.
        int height = std::max(index->nHeight - step, 0);
        // Use skiplist.
        index = index->GetAncestor(height);
        if (have.size() > 10) step *= 2;
    }
    return have;
}

CBlockLocator GetLocator(const CBlockIndex* index)
{
    return CBlockLocator{LocatorEntries(index)};
}

CBlockLocator CChain::GetLocator() const
{
    return ::GetLocator(Tip());
}

const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const {
    if (pindex == nullptr) {
        return nullptr;
    }
    if (pindex->nHeight > Height())
        pindex = pindex->GetAncestor(Height());
    while (pindex && !Contains(pindex))
        pindex = pindex->pprev;
    return pindex;
}

CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime, int height) const
{
    std::pair<int64_t, int> blockparams = std::make_pair(nTime, height);
    std::vector<CBlockIndex*>::const_iterator lower = std::lower_bound(vChain.begin(), vChain.end(), blockparams,
        [](CBlockIndex* pBlock, const std::pair<int64_t, int>& blockparams) -> bool { return pBlock->GetBlockTimeMax() < blockparams.first || pBlock->nHeight < blockparams.second; });
    return (lower == vChain.end() ? nullptr : *lower);
}

/** Turn the lowest '1' bit in the binary representation of a number into a '0'. */
int static inline InvertLowestOne(int n) { return n & (n - 1); }

/** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
int static inline GetSkipHeight(int height) {
    if (height < 2)
        return 0;

    // Determine which height to jump back to. Any number strictly lower than height is acceptable,
    // but the following expression seems to perform well in simulations (max 110 steps to go back
    // up to 2**18 blocks).
    return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height);
}

const CBlockIndex* CBlockIndex::GetAncestor(int height) const
{
    if (height > nHeight || height < 0) {
        return nullptr;
    }

    const CBlockIndex* pindexWalk = this;
    int heightWalk = nHeight;
    while (heightWalk > height) {
        int heightSkip = GetSkipHeight(heightWalk);
        int heightSkipPrev = GetSkipHeight(heightWalk - 1);
        if (pindexWalk->pskip != nullptr &&
            (heightSkip == height ||
             (heightSkip > height && !(heightSkipPrev < heightSkip - 2 &&
                                       heightSkipPrev >= height)))) {
            // Only follow pskip if pprev->pskip isn't better than pskip->pprev.
            pindexWalk = pindexWalk->pskip;
            heightWalk = heightSkip;
        } else {
            assert(pindexWalk->pprev);
            pindexWalk = pindexWalk->pprev;
            heightWalk--;
        }
    }
    return pindexWalk;
}

CBlockIndex* CBlockIndex::GetAncestor(int height)
{
    return const_cast<CBlockIndex*>(static_cast<const CBlockIndex*>(this)->GetAncestor(height));
}

void CBlockIndex::BuildSkip()
{
    if (pprev)
        pskip = pprev->GetAncestor(GetSkipHeight(nHeight));
}

arith_uint256 GetBlockProof(const CBlockIndex& block)
{
    arith_uint256 bnTarget;
    bool fNegative;
    bool fOverflow;
    bnTarget.SetCompact(block.nBits, &fNegative, &fOverflow);
    if (fNegative || fOverflow || bnTarget == 0)
        return 0;
    // We need to compute 2**256 / (bnTarget+1), but we can't represent 2**256
    // as it's too large for an arith_uint256. However, as 2**256 is at least as large
    // as bnTarget+1, it is equal to ((2**256 - bnTarget - 1) / (bnTarget+1)) + 1,
    // or ~bnTarget / (bnTarget+1) + 1.
    return (~bnTarget / (bnTarget + 1)) + 1;
}

int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params& params)
{
    arith_uint256 r;
    int sign = 1;
    if (to.nChainWork > from.nChainWork) {
        r = to.nChainWork - from.nChainWork;
    } else {
        r = from.nChainWork - to.nChainWork;
        sign = -1;
    }
    r = r * arith_uint256(params.nPowTargetSpacing) / GetBlockProof(tip);
    if (r.bits() > 63) {
        return sign * std::numeric_limits<int64_t>::max();
    }
    return sign * int64_t(r.GetLow64());
}

/** Find the last common ancestor two blocks have.
 *  Both pa and pb must be non-nullptr. */
const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb) {
    if (pa->nHeight > pb->nHeight) {
        pa = pa->GetAncestor(pb->nHeight);
    } else if (pb->nHeight > pa->nHeight) {
        pb = pb->GetAncestor(pa->nHeight);
    }

    while (pa != pb && pa && pb) {
        pa = pa->pprev;
        pb = pb->pprev;
    }

    // Eventually all chain branches meet at the genesis block.
    assert(pa == pb);
    return pa;
}

Line	Count	Source (jump to first uncovered line)
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		std::string CBlockFileInfo::ToString() const
11	0	{
12	0	return strprintf("CBlockFileInfo(blocks=%u, size=%u, heights=%u...%u, time=%s...%s)", nBlocks, nSize, nHeightFirst, nHeightLast, FormatISO8601Date(nTimeFirst), FormatISO8601Date(nTimeLast));
13	0	}
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	6.84k	{
23	6.84k	CBlockIndex* pindex = &block;
24	6.84k	vChain.resize(pindex->nHeight + 1);
25	13.6k	while (pindex && vChain[pindex->nHeight] != pindex) { Branch (25:12): [True: 6.84k, False: 6.84k] Branch (25:22): [True: 6.84k, False: 0]
26	6.84k	vChain[pindex->nHeight] = pindex;
27	6.84k	pindex = pindex->pprev;
28	6.84k	}
29	6.84k	}
30
31		std::vector<uint256> LocatorEntries(const CBlockIndex* index)
32	4.01k	{
33	4.01k	int step = 1;
34	4.01k	std::vector<uint256> have;
35	4.01k	if (index == nullptr) return have; Branch (35:9): [True: 0, False: 4.01k]
36
37	4.01k	have.reserve(32);
38	4.01k	while (index) { Branch (38:12): [True: 4.01k, False: 0]
39	4.01k	have.emplace_back(index->GetBlockHash());
40	4.01k	if (index->nHeight == 0) break; Branch (40:13): [True: 4.01k, False: 0]
41		// Exponentially larger steps back, plus the genesis block.
42	0	int height = std::max(index->nHeight - step, 0);
43		// Use skiplist.
44	0	index = index->GetAncestor(height);
45	0	if (have.size() > 10) step *= 2; Branch (45:13): [True: 0, False: 0]
46	0	}
47	4.01k	return have;
48	4.01k	}
49
50		CBlockLocator GetLocator(const CBlockIndex* index)
51	2.42k	{
52	2.42k	return CBlockLocator{LocatorEntries(index)};
53	2.42k	}
54
55		CBlockLocator CChain::GetLocator() const
56	0	{
57	0	return ::GetLocator(Tip());
58	0	}
59
60	0	const CBlockIndex CChain::FindFork(const CBlockIndex pindex) const {
61	0	if (pindex == nullptr) { Branch (61:9): [True: 0, False: 0]
62	0	return nullptr;
63	0	}
64	0	if (pindex->nHeight > Height()) Branch (64:9): [True: 0, False: 0]
65	0	pindex = pindex->GetAncestor(Height());
66	0	while (pindex && !Contains(pindex)) Branch (66:12): [True: 0, False: 0] Branch (66:22): [True: 0, False: 0]
67	0	pindex = pindex->pprev;
68	0	return pindex;
69	0	}
70
71		CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime, int height) const
72	0	{
73	0	std::pair<int64_t, int> blockparams = std::make_pair(nTime, height);
74	0	std::vector<CBlockIndex*>::const_iterator lower = std::lower_bound(vChain.begin(), vChain.end(), blockparams,
75	0	[](CBlockIndex* pBlock, const std::pair<int64_t, int>& blockparams) -> bool { return pBlock->GetBlockTimeMax() < blockparams.first \|\| pBlock->nHeight < blockparams.second; }); Branch (75:94): [True: 0, False: 0] Branch (75:143): [True: 0, False: 0]
76	0	return (lower == vChain.end() ? nullptr : *lower); Branch (76:13): [True: 0, False: 0]
77	0	}
78
79		/** Turn the lowest '1' bit in the binary representation of a number into a '0'. */
80	0	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	0	int static inline GetSkipHeight(int height) {
84	0	if (height < 2) Branch (84:9): [True: 0, False: 0]
85	0	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	0	return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height); Branch (90:12): [True: 0, False: 0]
91	0	}
92
93		const CBlockIndex* CBlockIndex::GetAncestor(int height) const
94	0	{
95	0	if (height > nHeight \|\| height < 0) { Branch (95:9): [True: 0, False: 0] Branch (95:29): [True: 0, False: 0]
96	0	return nullptr;
97	0	}
98
99	0	const CBlockIndex* pindexWalk = this;
100	0	int heightWalk = nHeight;
101	0	while (heightWalk > height) { Branch (101:12): [True: 0, False: 0]
102	0	int heightSkip = GetSkipHeight(heightWalk);
103	0	int heightSkipPrev = GetSkipHeight(heightWalk - 1);
104	0	if (pindexWalk->pskip != nullptr && Branch (104:13): [True: 0, False: 0]
105	0	(heightSkip == height \|\| Branch (105:14): [True: 0, False: 0]
106	0	(heightSkip > height && !(heightSkipPrev < heightSkip - 2 && Branch (106:15): [True: 0, False: 0] Branch (106:40): [True: 0, False: 0]
107	0	heightSkipPrev >= height)))) { Branch (107:40): [True: 0, False: 0]
108		// Only follow pskip if pprev->pskip isn't better than pskip->pprev.
109	0	pindexWalk = pindexWalk->pskip;
110	0	heightWalk = heightSkip;
111	0	} else {
112	0	assert(pindexWalk->pprev);
113	0	pindexWalk = pindexWalk->pprev;
114	0	heightWalk--;
115	0	}
116	0	}
117	0	return pindexWalk;
118	0	}
119
120		CBlockIndex* CBlockIndex::GetAncestor(int height)
121	0	{
122	0	return const_cast<CBlockIndex>(static_cast<const CBlockIndex>(this)->GetAncestor(height));
123	0	}
124
125		void CBlockIndex::BuildSkip()
126	0	{
127	0	if (pprev) Branch (127:9): [True: 0, False: 0]
128	0	pskip = pprev->GetAncestor(GetSkipHeight(nHeight));
129	0	}
130
131		arith_uint256 GetBlockProof(const CBlockIndex& block)
132	46.2k	{
133	46.2k	arith_uint256 bnTarget;
134	46.2k	bool fNegative;
135	46.2k	bool fOverflow;
136	46.2k	bnTarget.SetCompact(block.nBits, &fNegative, &fOverflow);
137	46.2k	if (fNegative \|\| fOverflow \|\| bnTarget == 0) Branch (137:9): [True: 320, False: 45.9k] Branch (137:22): [True: 0, False: 45.9k] Branch (137:35): [True: 43, False: 45.9k]
138	363	return 0;
139		// We need to compute 2256 / (bnTarget+1), but we can't represent 2256
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	45.9k	return (~bnTarget / (bnTarget + 1)) + 1;
144	46.2k	}
145
146		int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params& params)
147	0	{
148	0	arith_uint256 r;
149	0	int sign = 1;
150	0	if (to.nChainWork > from.nChainWork) { Branch (150:9): [True: 0, False: 0]
151	0	r = to.nChainWork - from.nChainWork;
152	0	} else {
153	0	r = from.nChainWork - to.nChainWork;
154	0	sign = -1;
155	0	}
156	0	r = r * arith_uint256(params.nPowTargetSpacing) / GetBlockProof(tip);
157	0	if (r.bits() > 63) { Branch (157:9): [True: 0, False: 0]
158	0	return sign * std::numeric_limits<int64_t>::max();
159	0	}
160	0	return sign * int64_t(r.GetLow64());
161	0	}
162
163		/** Find the last common ancestor two blocks have.
164		* Both pa and pb must be non-nullptr. */
165	0	const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb) {
166	0	if (pa->nHeight > pb->nHeight) { Branch (166:9): [True: 0, False: 0]
167	0	pa = pa->GetAncestor(pb->nHeight);
168	0	} else if (pb->nHeight > pa->nHeight) { Branch (168:16): [True: 0, False: 0]
169	0	pb = pb->GetAncestor(pa->nHeight);
170	0	}
171
172	0	while (pa != pb && pa && pb) { Branch (172:12): [True: 0, False: 0] Branch (172:24): [True: 0, False: 0] Branch (172:30): [True: 0, False: 0]
173	0	pa = pa->pprev;
174	0	pb = pb->pprev;
175	0	}
176
177		// Eventually all chain branches meet at the genesis block.
178	0	assert(pa == pb);
179	0	return pa;
180	0	}

Coverage Report

Created: 2024-08-21 05:08