text: // Copyright (c) 2009-2010 Satoshi Nakamoto
  // Copyright (c) 2009-2015 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 "pow.h"
  
  #include "arith_uint256.h"
  #include "chain.h"
  #include "chainparams.h"
  #include "primitives/block.h"
  #include "uint256.h"
  #include "util.h"
  
  #include <math.h>
  
  unsigned int static KimotoGravityWell(const CBlockIndex* pindexLast, const Consensus::Params& params) {
      const CBlockIndex *BlockLastSolved = pindexLast;
      const CBlockIndex *BlockReading = pindexLast;
      uint64_t PastBlocksMass = 0;
      int64_t PastRateActualSeconds = 0;
      int64_t PastRateTargetSeconds = 0;
      double PastRateAdjustmentRatio = double(1);
      arith_uint256 PastDifficultyAverage;
      arith_uint256 PastDifficultyAveragePrev;
      double EventHorizonDeviation;
      double EventHorizonDeviationFast;
      double EventHorizonDeviationSlow;
  
      uint64_t pastSecondsMin = params.nPowTargetTimespan * 0.025;
      uint64_t pastSecondsMax = params.nPowTargetTimespan * 7;
      uint64_t PastBlocksMin = pastSecondsMin / params.nPowTargetSpacing;
      uint64_t PastBlocksMax = pastSecondsMax / params.nPowTargetSpacing;
  
      if (BlockLastSolved == NULL || BlockLastSolved->nHeight == 0 || (uint64_t)BlockLastSolved->nHeight < PastBlocksMin) { return UintToArith256(params.powLimit).GetCompact(); }
  
      for (unsigned int i = 1; BlockReading && BlockReading->nHeight > 0; i++) {
          if (PastBlocksMax > 0 && i > PastBlocksMax) { break; }
          PastBlocksMass++;
  
          PastDifficultyAverage.SetCompact(BlockReading->nBits);
          if (i > 1) {
              // handle negative arith_uint256
              if(PastDifficultyAverage >= PastDifficultyAveragePrev)
                  PastDifficultyAverage = ((PastDifficultyAverage - PastDifficultyAveragePrev) / i) + PastDifficultyAveragePrev;
              else
                  PastDifficultyAverage = PastDifficultyAveragePrev - ((PastDifficultyAveragePrev - PastDifficultyAverage) / i);
          }
          PastDifficultyAveragePrev = PastDifficultyAverage;
  
          PastRateActualSeconds = BlockLastSolved->GetBlockTime() - BlockReading->GetBlockTime();
          PastRateTargetSeconds = params.nPowTargetSpacing * PastBlocksMass;
          PastRateAdjustmentRatio = double(1);
          if (PastRateActualSeconds < 0) { PastRateActualSeconds = 0; }
          if (PastRateActualSeconds != 0 && PastRateTargetSeconds != 0) {
              PastRateAdjustmentRatio = double(PastRateTargetSeconds) / double(PastRateActualSeconds);
          }
          EventHorizonDeviation = 1 + (0.7084 * pow((double(PastBlocksMass)/double(28.2)), -1.228));
          EventHorizonDeviationFast = EventHorizonDeviation;
          EventHorizonDeviationSlow = 1 / EventHorizonDeviation;
  
          if (PastBlocksMass >= PastBlocksMin) {
                  if ((PastRateAdjustmentRatio <= EventHorizonDeviationSlow) || (PastRateAdjustmentRatio >= EventHorizonDeviationFast))
                  { assert(BlockReading); break; }
          }
          if (BlockReading->pprev == NULL) { assert(BlockReading); break; }
          BlockReading = BlockReading->pprev;
      }
  
      arith_uint256 bnNew(PastDifficultyAverage);
      if (PastRateActualSeconds != 0 && PastRateTargetSeconds != 0) {
          bnNew *= PastRateActualSeconds;
          bnNew /= PastRateTargetSeconds;
      }
  
      if (bnNew > UintToArith256(params.powLimit)) {
          bnNew = UintToArith256(params.powLimit);
      }
  
      return bnNew.GetCompact();
  }
  
  unsigned int static DarkGravityWave(const CBlockIndex* pindexLast, const Consensus::Params& params) {
      /* current difficulty formula, vivo - DarkGravity v3, written by Evan Duffield - evan@vivo.org */
      const CBlockIndex *BlockLastSolved = pindexLast;
      const CBlockIndex *BlockReading = pindexLast;
      int64_t nActualTimespan = 0;
      int64_t LastBlockTime = 0;
      int64_t PastBlocksMin = 24;
      int64_t PastBlocksMax = 24;
      int64_t CountBlocks = 0;
      arith_uint256 PastDifficultyAverage;
      arith_uint256 PastDifficultyAveragePrev;
  
      if (BlockLastSolved == NULL || BlockLastSolved->nHeight == 0 || BlockLastSolved->nHeight < PastBlocksMin) {
          return UintToArith256(params.powLimit).GetCompact();
      }
  
      for (unsigned int i = 1; BlockReading && BlockReading->nHeight > 0; i++) {
          if (PastBlocksMax > 0 && i > PastBlocksMax) { break; }
          CountBlocks++;
  
          if(CountBlocks <= PastBlocksMin) {
              if (CountBlocks == 1) { PastDifficultyAverage.SetCompact(BlockReading->nBits); }
              else { PastDifficultyAverage = ((PastDifficultyAveragePrev * CountBlocks) + (arith_uint256().SetCompact(BlockReading->nBits))) / (CountBlocks + 1); }
              PastDifficultyAveragePrev = PastDifficultyAverage;
          }
  
          if(LastBlockTime > 0){
              int64_t Diff = (LastBlockTime - BlockReading->GetBlockTime());
              nActualTimespan += Diff;
          }
          LastBlockTime = BlockReading->GetBlockTime();
  
          if (BlockReading->pprev == NULL) { assert(BlockReading); break; }
          BlockReading = BlockReading->pprev;
      }
  
      arith_uint256 bnNew(PastDifficultyAverage);
  
      int64_t _nTargetTimespan = CountBlocks * params.nPowTargetSpacing;
  
      if (nActualTimespan < _nTargetTimespan/3)
          nActualTimespan = _nTargetTimespan/3;
      if (nActualTimespan > _nTargetTimespan*3)
          nActualTimespan = _nTargetTimespan*3;
  
      // Retarget
      bnNew *= nActualTimespan;
      bnNew /= _nTargetTimespan;
  
      if (bnNew > UintToArith256(params.powLimit)){
          bnNew = UintToArith256(params.powLimit);
      }
  
      return bnNew.GetCompact();
  }
  
  unsigned int GetNextWorkRequired(const CBlockIndex* pindexLast, const CBlockHeader *pblock, const Consensus::Params& params)
  {
      unsigned int retarget = DIFF_DGW;
  
      // mainnet/regtest share a configuration 
      if (Params().NetworkIDString() == CBaseChainParams::MAIN || Params().NetworkIDString() == CBaseChainParams::REGTEST) {
          if (pindexLast->nHeight + 1 >= 15200) retarget = DIFF_DGW;
          else retarget = DIFF_BTC;
      // testnet -- we want a lot of coins in existance early on 
      } else {
          if (pindexLast->nHeight + 1 >= 3000) retarget = DIFF_DGW;
          else retarget = DIFF_BTC;
      }
  
      // Default Bitcoin style retargeting
      if (retarget == DIFF_BTC)
      {
          unsigned int nProofOfWorkLimit = UintToArith256(params.powLimit).GetCompact();
  
          // Genesis block
          if (pindexLast == NULL)
              return nProofOfWorkLimit;
  
          // Only change once per interval
          if ((pindexLast->nHeight+1) % params.DifficultyAdjustmentInterval() != 0)
          {
              if (params.fPowAllowMinDifficultyBlocks)
              {
                  // Special difficulty rule for testnet:
                  // If the new block's timestamp is more than 2* 2.5 minutes
                  // then allow mining of a min-difficulty block.
                  if (pblock->GetBlockTime() > pindexLast->GetBlockTime() + params.nPowTargetSpacing*2)
                      return nProofOfWorkLimit;
                  else
                  {
                      // Return the last non-special-min-difficulty-rules-block
                      const CBlockIndex* pindex = pindexLast;
                      while (pindex->pprev && pindex->nHeight % params.DifficultyAdjustmentInterval() != 0 && pindex->nBits == nProofOfWorkLimit)
                          pindex = pindex->pprev;
                      return pindex->nBits;
                  }
              }
              return pindexLast->nBits;
          }
  
          // Go back by what we want to be 1 day worth of blocks
          int nHeightFirst = pindexLast->nHeight - (params.DifficultyAdjustmentInterval()-1);
          assert(nHeightFirst >= 0);
          const CBlockIndex* pindexFirst = pindexLast->GetAncestor(nHeightFirst);
          assert(pindexFirst);
  
         return CalculateNextWorkRequired(pindexLast, pindexFirst->GetBlockTime(), params);
      }
  
      // Retarget using Kimoto Gravity Wave
      else if (retarget == DIFF_KGW)
      {
          return KimotoGravityWell(pindexLast, params);
      }
  
      // Retarget using Dark Gravity Wave 3
      else if (retarget == DIFF_DGW)
      {
          return DarkGravityWave(pindexLast, params);
      }
  
      return DarkGravityWave(pindexLast, params);
  }
  
  // for DIFF_BTC only!
  unsigned int CalculateNextWorkRequired(const CBlockIndex* pindexLast, int64_t nFirstBlockTime, const Consensus::Params& params)
  {
      if (params.fPowNoRetargeting)
          return pindexLast->nBits;
  
      // Limit adjustment step
      int64_t nActualTimespan = pindexLast->GetBlockTime() - nFirstBlockTime;
      LogPrintf("  nActualTimespan = %d  before bounds\n", nActualTimespan);
      if (nActualTimespan < params.nPowTargetTimespan/4)
          nActualTimespan = params.nPowTargetTimespan/4;
      if (nActualTimespan > params.nPowTargetTimespan*4)
          nActualTimespan = params.nPowTargetTimespan*4;
  
      // Retarget
      const arith_uint256 bnPowLimit = UintToArith256(params.powLimit);
      arith_uint256 bnNew;
      arith_uint256 bnOld;
      bnNew.SetCompact(pindexLast->nBits);
      bnOld = bnNew;
      bnNew *= nActualTimespan;
      bnNew /= params.nPowTargetTimespan;
  
      if (bnNew > bnPowLimit)
          bnNew = bnPowLimit;
  
      /// debug print
      LogPrintf("GetNextWorkRequired RETARGET\n");
      LogPrintf("params.nPowTargetTimespan = %d    nActualTimespan = %d\n", params.nPowTargetTimespan, nActualTimespan);
      LogPrintf("Before: %08x  %s\n", pindexLast->nBits, bnOld.ToString());
      LogPrintf("After:  %08x  %s\n", bnNew.GetCompact(), bnNew.ToString());
  
      return bnNew.GetCompact();
  }
  
  bool CheckProofOfWork(uint256 hash, unsigned int nBits, const Consensus::Params& params)
  {
      bool fNegative;
      bool fOverflow;
      arith_uint256 bnTarget;
  
      bnTarget.SetCompact(nBits, &fNegative, &fOverflow);
  
      // Check range
      if (fNegative || bnTarget == 0 || fOverflow || bnTarget > UintToArith256(params.powLimit))
          return error("CheckProofOfWork(): nBits below minimum work");
  
      // Check proof of work matches claimed amount
      if (UintToArith256(hash) > bnTarget)
          return error("CheckProofOfWork(): hash doesn't match nBits");
  
      return true;
  }
  
  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 a 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 / (nTarget+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 * r.GetLow64();
  }
  