LCOV - code coverage report
Current view: top level - src - chain.cpp (source / functions) Coverage Total Hit
Test: fuzz_coverage.info Lines: 76.4 % 89 68
Test Date: 2025-10-10 04:04:55 Functions: 85.7 % 14 12
Branches: 69.3 % 88 61

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

Generated by: LCOV version 2.0-1