/*
 * This file is part of the Flowee project
 * Copyright (C) 2009-2010 Satoshi Nakamoto
 * Copyright (C) 2009-2015 The Bitcoin Core developers
 * Copyright (C) 2018 Jason B. Cox <contact@jasonbcox.com>
 * Copyright (C) 2018-2026 Tom Zander <tom@flowee.org>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "script.h"
#include "ScriptBigNum_p.h"
#include "FastBigNum_p.h"
#include "PublicKeyUtils.h"

#include <hash.h>
#include <tinyformat.h>
#include <uint256.h>
#include <utilstrencodings.h>

#include <map>
#include <utility>

const char* GetOpName(opcodetype opcode)
{
    switch (opcode)
    {
    // push value
    case OP_0                      : return "0";
    case OP_PUSHDATA1              : return "OP_PUSHDATA1";
    case OP_PUSHDATA2              : return "OP_PUSHDATA2";
    case OP_PUSHDATA4              : return "OP_PUSHDATA4";
    case OP_1NEGATE                : return "-1";
    case OP_RESERVED               : return "OP_RESERVED";
    case OP_1                      : return "1";
    case OP_2                      : return "2";
    case OP_3                      : return "3";
    case OP_4                      : return "4";
    case OP_5                      : return "5";
    case OP_6                      : return "6";
    case OP_7                      : return "7";
    case OP_8                      : return "8";
    case OP_9                      : return "9";
    case OP_10                     : return "10";
    case OP_11                     : return "11";
    case OP_12                     : return "12";
    case OP_13                     : return "13";
    case OP_14                     : return "14";
    case OP_15                     : return "15";
    case OP_16                     : return "16";

    // control
    case OP_NOP                    : return "OP_NOP";
    case OP_VER                    : return "OP_VER";
    case OP_IF                     : return "OP_IF";
    case OP_NOTIF                  : return "OP_NOTIF";
    case OP_BEGIN                  : return "OP_BEGIN";
    case OP_UNTIL                  : return "OP_UNTIL";
    case OP_ELSE                   : return "OP_ELSE";
    case OP_ENDIF                  : return "OP_ENDIF";
    case OP_VERIFY                 : return "OP_VERIFY";
    case OP_RETURN                 : return "OP_RETURN";

    // stack ops
    case OP_TOALTSTACK             : return "OP_TOALTSTACK";
    case OP_FROMALTSTACK           : return "OP_FROMALTSTACK";
    case OP_2DROP                  : return "OP_2DROP";
    case OP_2DUP                   : return "OP_2DUP";
    case OP_3DUP                   : return "OP_3DUP";
    case OP_2OVER                  : return "OP_2OVER";
    case OP_2ROT                   : return "OP_2ROT";
    case OP_2SWAP                  : return "OP_2SWAP";
    case OP_IFDUP                  : return "OP_IFDUP";
    case OP_DEPTH                  : return "OP_DEPTH";
    case OP_DROP                   : return "OP_DROP";
    case OP_DUP                    : return "OP_DUP";
    case OP_NIP                    : return "OP_NIP";
    case OP_OVER                   : return "OP_OVER";
    case OP_PICK                   : return "OP_PICK";
    case OP_ROLL                   : return "OP_ROLL";
    case OP_ROT                    : return "OP_ROT";
    case OP_SWAP                   : return "OP_SWAP";
    case OP_TUCK                   : return "OP_TUCK";

    // splice ops
    case OP_CAT                    : return "OP_CAT";
    case OP_SPLIT                  : return "OP_SPLIT";
    case OP_NUM2BIN                : return "OP_NUM2BIN";
    case OP_BIN2NUM                  : return "OP_BIN2NUM";
    case OP_SIZE                   : return "OP_SIZE";

    // bit logic
    case OP_INVERT                 : return "OP_INVERT";
    case OP_AND                    : return "OP_AND";
    case OP_OR                     : return "OP_OR";
    case OP_XOR                    : return "OP_XOR";
    case OP_EQUAL                  : return "OP_EQUAL";
    case OP_EQUALVERIFY            : return "OP_EQUALVERIFY";
    case OP_DEFINE                 : return "OP_DEFINE";
    case OP_INVOKE                 : return "OP_INVOKE";

    // numeric
    case OP_1ADD                   : return "OP_1ADD";
    case OP_1SUB                   : return "OP_1SUB";
    case OP_LSHIFTNUM              : return "OP_LSHIFTNUM";
    case OP_RSHIFTNUM              : return "OP_RSHIFTNUM";
    case OP_NEGATE                 : return "OP_NEGATE";
    case OP_ABS                    : return "OP_ABS";
    case OP_NOT                    : return "OP_NOT";
    case OP_0NOTEQUAL              : return "OP_0NOTEQUAL";
    case OP_ADD                    : return "OP_ADD";
    case OP_SUB                    : return "OP_SUB";
    case OP_MUL                    : return "OP_MUL";
    case OP_DIV                    : return "OP_DIV";
    case OP_MOD                    : return "OP_MOD";
    case OP_LSHIFTBIN              : return "OP_LSHIFTBIN";
    case OP_RSHIFTBIN              : return "OP_RSHIFTBIN";
    case OP_BOOLAND                : return "OP_BOOLAND";
    case OP_BOOLOR                 : return "OP_BOOLOR";
    case OP_NUMEQUAL               : return "OP_NUMEQUAL";
    case OP_NUMEQUALVERIFY         : return "OP_NUMEQUALVERIFY";
    case OP_NUMNOTEQUAL            : return "OP_NUMNOTEQUAL";
    case OP_LESSTHAN               : return "OP_LESSTHAN";
    case OP_GREATERTHAN            : return "OP_GREATERTHAN";
    case OP_LESSTHANOREQUAL        : return "OP_LESSTHANOREQUAL";
    case OP_GREATERTHANOREQUAL     : return "OP_GREATERTHANOREQUAL";
    case OP_MIN                    : return "OP_MIN";
    case OP_MAX                    : return "OP_MAX";
    case OP_WITHIN                 : return "OP_WITHIN";

    // crypto
    case OP_RIPEMD160              : return "OP_RIPEMD160";
    case OP_SHA1                   : return "OP_SHA1";
    case OP_SHA256                 : return "OP_SHA256";
    case OP_HASH160                : return "OP_HASH160";
    case OP_HASH256                : return "OP_HASH256";
    case OP_CODESEPARATOR          : return "OP_CODESEPARATOR";
    case OP_CHECKSIG               : return "OP_CHECKSIG";
    case OP_CHECKSIGVERIFY         : return "OP_CHECKSIGVERIFY";
    case OP_CHECKMULTISIG          : return "OP_CHECKMULTISIG";
    case OP_CHECKMULTISIGVERIFY    : return "OP_CHECKMULTISIGVERIFY";

    // soft-forkable expansion
    case OP_NOP1                   : return "OP_NOP1";
    case OP_CHECKLOCKTIMEVERIFY    : return "OP_CHECKLOCKTIMEVERIFY";
    case OP_NOP3                   : return "OP_NOP3";
    case OP_NOP4                   : return "OP_NOP4";
    case OP_NOP5                   : return "OP_NOP5";
    case OP_NOP6                   : return "OP_NOP6";
    case OP_NOP7                   : return "OP_NOP7";
    case OP_NOP8                   : return "OP_NOP8";
    case OP_NOP9                   : return "OP_NOP9";
    case OP_NOP10                  : return "OP_NOP10";

    // new opcodes hard-forked in.
    case OP_CHECKDATASIG: return "OP_CHECKDATASIG";
    case OP_CHECKDATASIGVERIFY: return "OP_CHECKDATASIGVERIFY";
    case OP_REVERSEBYTES: return "OP_REVERSEBYTES";
    case OP_INPUTINDEX: return "OP_INPUTINDEX";
    case OP_ACTIVEBYTECODE: return "OP_ACTIVEBYTECODE";
    case OP_TXVERSION: return "OP_TXVERSION";
    case OP_TXINPUTCOUNT: return "OP_TXINPUTCOUNT";
    case OP_TXOUTPUTCOUNT: return "OP_TXOUTPUTCOUNT";
    case OP_TXLOCKTIME: return "OP_TXLOCKTIME";
    case OP_UTXOVALUE: return "OP_UTXOVALUE";
    case OP_UTXOBYTECODE: return "OP_UTXOBYTECODE";
    case OP_OUTPOINTTXHASH: return "OP_OUTPOINTTXHASH";
    case OP_OUTPOINTINDEX: return "OP_OUTPOINTINDEX";
    case OP_INPUTBYTECODE: return "OP_INPUTBYTECODE";
    case OP_INPUTSEQUENCENUMBER: return "OP_INPUTSEQUENCENUMBER";
    case OP_OUTPUTVALUE: return "OP_OUTPUTVALUE";
    case OP_OUTPUTBYTECODE: return "OP_OUTPUTBYTECODE";
    case OP_UTXOTOKENCATEGORY: return "OP_UTXOTOKENCATEGORY";
    case OP_UTXOTOKENCOMMITMENT: return "OP_UTXOTOKENCOMMITMENT";
    case OP_UTXOTOKENAMOUNT: return "OP_UTXOTOKENAMOUNT";
    case OP_OUTPUTTOKENCATEGORY: return "OP_OUTPUTTOKENCATEGORY";
    case OP_OUTPUTTOKENCOMMITMENT: return "OP_OUTPUTTOKENCOMMITMENT";
    case OP_OUTPUTTOKENAMOUNT: return "OP_OUTPUTTOKENAMOUNT";

    // Note:
    //  The template matching params OP_SMALLINTEGER/etc are defined in opcodetype enum
    //  as kind of implementation hack, they are *NOT* real opcodes.  If found in real
    //  Script, just let the default: case deal with them.

    default:
        return "OP_UNKNOWN";
    }
}

bool CheckMinimalPush(const std::vector<uint8_t> &data, opcodetype opcode)
{
    // Excludes OP_1NEGATE, OP_1-16 since they are by definition minimal.

    if (opcode <= OP_0 || opcode > OP_PUSHDATA4)
        // Anything outside of this range has nothing to do with data push
        return true;
    if (data.size() == 0) // Should use OP_0.
        return opcode == OP_0;
    if (data.size() == 1 && data[0] >= 1 && data[0] <= 16) // Should use OP_1 .. OP_16.
        return false;
    if (data.size() == 1 && data[0] == 0x81) // Should use OP_1NEGATE.
        return false;
    if (data.size() <= 75)
        // Should use a direct push (opcode indicating number of bytes pushed + those bytes).
        return opcode == data.size();
    if (data.size() <= 255) // Should use OP_PUSHDATA.
        return opcode == OP_PUSHDATA1;
    if (data.size() <= 65535) // Should use OP_PUSHDATA2.
        return opcode == OP_PUSHDATA2;
    return true;
}

CScript &CScript::operator<<(const ScriptBigNum &b) {
    *this << b.getvch();
    return *this;
}

bool CScript::IsPayToScriptHash(std::vector<unsigned char> *hashBytesOut) const
{
    if (this->size() == 23
            && (*this)[0] == OP_HASH160
            && (*this)[1] == 0x14
            && (*this)[22] == OP_EQUAL) {
        if (hashBytesOut)
            hashBytesOut->assign(begin() + 2, begin() + 22);
        return true;
    }

    if (this->size() == 35
            && (*this)[0] == OP_HASH256
            && (*this)[1] == 0x20
            && (*this)[34] == OP_EQUAL) {
        if (hashBytesOut)
            hashBytesOut->assign(begin() + 2, begin() + 34);
        return true;
    }

    return false;
}

// A witness program is a BTC concept based on segwit, that is not available on BitcoinCash.
// We can recognize it on it being any valid CScript that consists of a 1-byte push opcode
// followed by a data push between 2 and 40 bytes.
bool CScript::IsWitnessProgram() const
{
    if (this->size() < 4 || this->size() > 42)
        return false;
    if ((*this)[0] != OP_0 && ((*this)[0] < OP_1 || (*this)[0] > OP_16))
        return false;
    if (size_t((*this)[1] + 2) == this->size())
        return true;
    return false;
}

bool CScript::IsPushOnly(const_iterator pc) const
{
    while (pc < end())
    {
        opcodetype opcode;
        if (!GetOp(pc, opcode))
            return false;
        // Note that IsPushOnly() *does* consider OP_RESERVED to be a
        // push-type opcode, however execution of OP_RESERVED fails, so
        // it's not relevant to P2SH/BIP62 as the scriptSig would fail prior to
        // the P2SH special validation code being executed.
        if (opcode > OP_16)
            return false;
    }
    return true;
}

bool CScript::IsPushOnly() const
{
    return this->IsPushOnly(begin());
}

std::vector<uint8_t>

MinimalizeBigEndianArray(const std::vector<uint8_t> &data)
{
    std::vector<uint8_t> answer;
    // Can't encode more than this, go ahead and grab as much room as we could
    // possibly need
    answer.reserve(data.size());

    if (data.empty()) // Ensure we have a byte to work with.
        return answer;

    // Store the MSB
    uint8_t neg = data[0] & 0x80;
    bool havePushed = false;
    for (size_t i = 0; i < data.size(); ++i) {
        uint8_t x = data[i];
        if (i == 0) // Remove any MSB that might exist
            x &= 0x7f;

        if (!havePushed && x == 0) // If we haven't pushed anything, and the current value is zero, keep ignoring bytes.
            continue;

        // Record that we have begun pushing, and store the current value.
        havePushed = true;
        answer.push_back(x);
    }
    if (answer.size() == 0) // Give us at least one byte
        return answer;

    // Only add back the sign if a value has been pushed.  This implies the
    // result is non-zero.
    if (havePushed) {
        // If the MSB is currently occupied, we need one extra byte.
        if ((answer[0] & 0x80) != 0) {
            answer.insert(answer.begin(), 0);
        }
        answer[0] |= neg;
    }
    return answer;
}

bool CScriptNum::isSmallestFormat(const std::vector<uint8_t> &vch, const size_t nMaxNumSize)
{
    if (vch.size() > nMaxNumSize)
        return false;
    if (vch.size() > 0) {
        // If the most-significant-byte - excluding the sign bit - is zero
        // then we're not minimal. Note how this test also rejects the
        // negative-zero encoding, 0x80.
        if ((vch.back() & 0x7f) == 0) {
            // One exception: if there's more than one byte and the most
            // significant bit of the second-most-significant-byte is set it
            // would conflict with the sign bit. An example of this case is
            // +-255, which encode to 0xff00 and 0xff80 respectively.
            // (big-endian).
            if (vch.size() <= 1 || (vch[vch.size() - 2] & 0x80) == 0) {
                return false;
            }
        }
    }
    return true;
}

bool CScriptNum::createSmallestFormat(std::vector<uint8_t> &data)
{
    if (data.empty())
        return false;

    // If the last byte is not 0x00 or 0x80, we are minimally encoded.
    uint8_t last = data.back();
    if (last & 0x7f)
        return false;

    // If the script is one byte long, then we have a zero, which encodes as an
    // empty array.
    if (data.size() == 1) {
        data = {};
        return true;
    }

    // If the next byte has it sign bit set, then we are minimaly encoded.
    if (data[data.size() - 2] & 0x80)
        return false;

    // We are not minimally encoded, we need to figure out how much to trim.
    for (size_t i = data.size() - 1; i > 0; i--) {
        // We found a non zero byte, time to encode.
        if (data[i - 1] != 0) {
            if (data[i - 1] & 0x80) {
                // We found a byte with it sign bit set so we need one more
                // byte.
                data[i++] = last;
            } else {
                // the sign bit is clear, we can use it.
                data[i - 1] |= last;
            }

            data.resize(i);
            return true;
        }
    }

    // If we the whole thing is zeros, then we have a zero.
    data = {};
    return true;
}

namespace {

using ScriptBigInt = ScriptBigNum::BigInt;

size_t GetAbsBitCount(const ScriptBigInt &value)
{
    if (value == 0)
        return 1;
    const ScriptBigInt magnitude = value < 0 ? -value : value;
    return boost::multiprecision::msb(magnitude) + 1;
}

} // namespace

ScriptBigNum::ScriptBigNum(int64_t value)
    : m_value(value)
{
}

ScriptBigNum::ScriptBigNum(const BigInt &value)
    : m_value(value)
{
}

ScriptBigNum::ScriptBigNum(BigInt &&value)
    : m_value(std::move(value))
{
}

ScriptBigNum::ScriptBigNum(const std::vector<unsigned char> &vch, bool fRequireMinimal,
                           size_t maxIntegerSize)
{
    if (vch.size() > maxIntegerSize)
        throw scriptnum_error("script number overflow",
                              maxIntegerSize > CScriptNum::MAXIMUM_ELEMENT_SIZE_64_BIT
                                  ? SCRIPT_ERR_INVALID_NUMBER_RANGE_BIG_INT
                                  : SCRIPT_ERR_INVALID_NUMBER_RANGE);
    if (fRequireMinimal && !CScriptNum::isSmallestFormat(vch, maxIntegerSize))
        throw scriptnum_error("non-minimally encoded script number", SCRIPT_ERR_MINIMALDATA);
    m_value = set_vch(vch);
}

size_t ScriptBigNum::absValNumBits(const BigInt &value)
{
    return GetAbsBitCount(value);
}

bool ScriptBigNum::validRange(const BigInt &value)
{
    return absValNumBits(value) <= MAX_BIG_INT_BITS;
}

bool ScriptBigNum::safeIncr()
{
    return safeAddInPlace(1);
}

bool ScriptBigNum::safeDecr()
{
    return safeSubInPlace(1);
}

bool ScriptBigNum::safeAddInPlace(const ScriptBigNum &rhs)
{
    const BigInt previous = m_value;
    m_value += rhs.m_value;
    if (!validRange(m_value)) {
        m_value = previous;
        return false;
    }
    return true;
}

bool ScriptBigNum::safeAddInPlace(int64_t rhs)
{
    const BigInt previous = m_value;
    m_value += rhs;
    if (!validRange(m_value)) {
        m_value = previous;
        return false;
    }
    return true;
}

bool ScriptBigNum::safeSubInPlace(const ScriptBigNum &rhs)
{
    const BigInt previous = m_value;
    m_value -= rhs.m_value;
    if (!validRange(m_value)) {
        m_value = previous;
        return false;
    }
    return true;
}

bool ScriptBigNum::safeSubInPlace(int64_t rhs)
{
    const BigInt previous = m_value;
    m_value -= rhs;
    if (!validRange(m_value)) {
        m_value = previous;
        return false;
    }
    return true;
}

bool ScriptBigNum::safeMulInPlace(const ScriptBigNum &rhs)
{
    const BigInt previous = m_value;
    m_value *= rhs.m_value;
    if (!validRange(m_value)) {
        m_value = previous;
        return false;
    }
    return true;
}

bool ScriptBigNum::safeMulInPlace(int64_t rhs)
{
    const BigInt previous = m_value;
    m_value *= rhs;
    if (!validRange(m_value)) {
        m_value = previous;
        return false;
    }
    return true;
}

ScriptBigNum& ScriptBigNum::operator/=(const ScriptBigNum &rhs)
{
    m_value /= rhs.m_value;
    return *this;
}

ScriptBigNum& ScriptBigNum::operator%=(const ScriptBigNum &rhs)
{
#if BOOST_VERSION < 108600
    // a mod by zero was not caught prior to boost 1.86, so we handle it here.
    if (rhs.m_value == 0)
        throw std::overflow_error("Mod by zero.");
#endif
    m_value %= rhs.m_value;
    return *this;
}

ScriptBigNum& ScriptBigNum::negate()
{
    m_value = -m_value;
    return *this;
}

bool ScriptBigNum::checkedLeftShift(unsigned bitcount)
{
    if (m_value == 0)
        return true;
    if (bitcount + absValNumBits() > MAX_BIG_INT_BITS)
        return false;
    m_value <<= bitcount;
    return validRange(m_value);
}

bool ScriptBigNum::checkedRightShift(unsigned bitcount)
{
    if (m_value == 0)
        return true;
    if (bitcount >= absValNumBits()) {
        m_value = m_value < 0 ? -1 : 0;
        return true;
    }

    if (m_value > 0) {
        m_value >>= bitcount;
        return validRange(m_value);
    }

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wstringop-overflow"
    const BigInt divisor = BigInt(1) << bitcount;
#pragma GCC diagnostic pop
    BigInt magnitude = -m_value;
    BigInt quotient = magnitude / divisor;
    const BigInt remainder = magnitude % divisor;
    if (remainder != 0)
        ++quotient;
    m_value = -quotient;
    return validRange(m_value);
}

bool ScriptBigNum::isZero() const
{
    return m_value == 0;
}

int32_t ScriptBigNum::getint32() const
{
    static const BigInt kMin = std::numeric_limits<int32_t>::min();
    static const BigInt kMax = std::numeric_limits<int32_t>::max();
    if (m_value < kMin)
        return std::numeric_limits<int32_t>::min();
    if (m_value > kMax)
        return std::numeric_limits<int32_t>::max();
    return m_value.convert_to<int32_t>();
}

std::optional<int64_t> ScriptBigNum::getint64() const
{
    static const BigInt kMin = std::numeric_limits<int64_t>::min();
    static const BigInt kMax = std::numeric_limits<int64_t>::max();
    if (m_value < kMin || m_value > kMax)
        return std::nullopt;
    return m_value.convert_to<int64_t>();
}

std::vector<unsigned char> ScriptBigNum::getvch() const
{
    return serialize(m_value);
}

size_t ScriptBigNum::absValNumBits() const
{
    return absValNumBits(m_value);
}

int ScriptBigNum::compare(const ScriptBigNum &rhs) const
{
    if (m_value < rhs.m_value)
        return -1;
    if (m_value > rhs.m_value)
        return 1;
    return 0;
}

ScriptBigNum::BigInt ScriptBigNum::set_vch(const std::vector<unsigned char> &vch)
{
    if (vch.empty())
        return 0;

    BigInt result = 0;
    const bool neg = (vch.back() & 0x80) != 0;
    for (size_t i = vch.size(); i-- > 0;) {
        uint8_t byte = vch[i];
        if (neg && i == vch.size() - 1)
            byte &= 0x7f;
        result <<= 8;
        result += byte;
    }
    if (neg)
        result = -result;
    return result;
}

std::vector<unsigned char> ScriptBigNum::serialize(const BigInt &value)
{
    if (value == 0)
        return {};

    std::vector<unsigned char> result;
    const bool neg = value < 0;
    BigInt magnitude = neg ? -value : value;
    while (magnitude != 0) {
        result.push_back((magnitude & 0xff).convert_to<unsigned char>());
        magnitude >>= 8;
    }

    if (result.back() & 0x80)
        result.push_back(neg ? 0x80 : 0x00);
    else if (neg)
        result.back() |= 0x80;

    return result;
}

FastBigNum::FastBigNum(const std::vector<unsigned char> &vch, bool fRequireMinimal, size_t maxIntegerSize)
    : m_value(CScriptNum(0))
{
    if (maxIntegerSize > CScriptNum::MAXIMUM_ELEMENT_SIZE_64_BIT)
        m_value = ScriptBigNum(vch, fRequireMinimal, maxIntegerSize);
    else
        m_value = CScriptNum(vch, fRequireMinimal, maxIntegerSize);
}

FastBigNum::FastBigNum(const CScriptNum &value)
    : m_value(value)
{
}

FastBigNum::FastBigNum(const ScriptBigNum &value)
    : m_value(value)
{
}

FastBigNum FastBigNum::fromIntUnchecked(int64_t value, bool useBigInt)
{
    if (useBigInt)
        return FastBigNum(ScriptBigNum(value));
    return FastBigNum(CScriptNum(value));
}

bool FastBigNum::usesNative() const
{
    return std::holds_alternative<CScriptNum>(m_value);
}

int32_t FastBigNum::getint32() const
{
    if (usesNative())
        return std::get<CScriptNum>(m_value).getint();
    return std::get<ScriptBigNum>(m_value).getint32();
}

std::optional<int64_t> FastBigNum::getint64() const
{
    if (usesNative())
        return std::get<CScriptNum>(m_value).getint64();
    return std::get<ScriptBigNum>(m_value).getint64();
}

std::vector<unsigned char> FastBigNum::getvch() const
{
    if (usesNative())
        return std::get<CScriptNum>(m_value).getvch();
    return std::get<ScriptBigNum>(m_value).getvch();
}

size_t FastBigNum::absValNumBits() const
{
    if (usesNative()) {
        const int64_t value = std::get<CScriptNum>(m_value).getint64();
        const uint64_t magnitude = value < 0 ? -static_cast<uint64_t>(value) : static_cast<uint64_t>(value);
        if (magnitude == 0)
            return 1;
        size_t bits = 0;
        uint64_t remaining = magnitude;
        while (remaining != 0) {
            ++bits;
            remaining >>= 1;
        }
        return bits;
    }
    return std::get<ScriptBigNum>(m_value).absValNumBits();
}

bool FastBigNum::safeAddInPlace(const FastBigNum &rhs)
{
    if (usesNative() && rhs.usesNative())
        return std::get<CScriptNum>(m_value).safeAddInPlace(std::get<CScriptNum>(rhs.m_value));

    ScriptBigNum value = asBigNum();
    if (!value.safeAddInPlace(rhs.asBigNum()))
        return false;
    m_value = std::move(value);
    return true;
}

bool FastBigNum::safeIncr()
{
    if (usesNative())
        return std::get<CScriptNum>(m_value).safeIncr();
    return std::get<ScriptBigNum>(m_value).safeIncr();
}

bool FastBigNum::safeSubInPlace(const FastBigNum &rhs)
{
    if (usesNative() && rhs.usesNative())
        return std::get<CScriptNum>(m_value).safeSubInPlace(std::get<CScriptNum>(rhs.m_value));

    ScriptBigNum value = asBigNum();
    if (!value.safeSubInPlace(rhs.asBigNum()))
        return false;
    m_value = std::move(value);
    return true;
}

bool FastBigNum::safeDecr()
{
    if (usesNative())
        return std::get<CScriptNum>(m_value).safeDecr();
    return std::get<ScriptBigNum>(m_value).safeDecr();
}

bool FastBigNum::safeMulInPlace(const FastBigNum &rhs)
{
    if (usesNative() && rhs.usesNative())
        return std::get<CScriptNum>(m_value).safeMulInPlace(std::get<CScriptNum>(rhs.m_value));

    ScriptBigNum value = asBigNum();
    if (!value.safeMulInPlace(rhs.asBigNum()))
        return false;
    m_value = std::move(value);
    return true;
}

FastBigNum& FastBigNum::operator/=(const FastBigNum &rhs)
{
    if (usesNative() && rhs.usesNative()) {
        m_value = std::get<CScriptNum>(m_value) / std::get<CScriptNum>(rhs.m_value);
        return *this;
    }

    ScriptBigNum value = asBigNum();
    value /= rhs.asBigNum();
    m_value = std::move(value);
    return *this;
}

FastBigNum& FastBigNum::operator%=(const FastBigNum &rhs)
{
    if (usesNative() && rhs.usesNative()) {
        m_value = std::get<CScriptNum>(m_value) % std::get<CScriptNum>(rhs.m_value);
        return *this;
    }

    ScriptBigNum value = asBigNum();
    value %= rhs.asBigNum();
    m_value = std::move(value);
    return *this;
}

FastBigNum& FastBigNum::negate()
{
    if (usesNative())
        std::get<CScriptNum>(m_value).negate();
    else
        std::get<ScriptBigNum>(m_value).negate();
    return *this;
}

bool FastBigNum::checkedLeftShift(unsigned bitcount)
{
    if (!usesNative())
        return std::get<ScriptBigNum>(m_value).checkedLeftShift(bitcount);

    ScriptBigNum value = asBigNum();
    if (!value.checkedLeftShift(bitcount))
        return false;
    m_value = std::move(value);
    return true;
}

bool FastBigNum::checkedRightShift(unsigned bitcount)
{
    if (!usesNative())
        return std::get<ScriptBigNum>(m_value).checkedRightShift(bitcount);

    ScriptBigNum value = asBigNum();
    if (!value.checkedRightShift(bitcount))
        return false;
    m_value = std::move(value);
    return true;
}

bool FastBigNum::isZero() const
{
    if (usesNative())
        return std::get<CScriptNum>(m_value).getint64() == 0;
    return std::get<ScriptBigNum>(m_value).isZero();
}

int FastBigNum::compare(const FastBigNum &rhs) const
{
    if (usesNative() && rhs.usesNative()) {
        const CScriptNum &lhsNum = std::get<CScriptNum>(m_value);
        const CScriptNum &rhsNum = std::get<CScriptNum>(rhs.m_value);
        if (lhsNum < rhsNum)
            return -1;
        if (lhsNum > rhsNum)
            return 1;
        return 0;
    }

    return asBigNum().compare(rhs.asBigNum());
}

ScriptBigNum FastBigNum::asBigNum() const
{
    if (usesNative())
        return ScriptBigNum(std::get<CScriptNum>(m_value).getint64());
    return std::get<ScriptBigNum>(m_value);
}


const char* Script::getTxnOutputType(Script::TxnOutType t)
{
    switch (t)
    {
    case TX_NONSTANDARD: return "nonstandard";
    case TX_PUBKEY: return "pubkey";
    case TX_PUBKEYHASH: return "pubkeyhash";
    case TX_SCRIPTHASH: return "scripthash";
    case TX_MULTISIG: return "multisig";
    case TX_NULL_DATA: return "nulldata";
    case TX_SCRIPT: return "script";
    }
    return nullptr;
}


CScriptID::CScriptID(const CScript& in) : uint160(Hash160(in.begin(), in.end())) {}


struct SolverHelper {
    std::multimap<Script::TxnOutType, CScript> templates;
    SolverHelper() {
        // Standard tx, sender provides pubkey, receiver adds signature
        templates.insert(std::make_pair(Script::TX_PUBKEY, CScript() << PUBKEY_PLACEHOLDER << OP_CHECKSIG));

        // Bitcoin address tx, sender provides hash of pubkey, receiver provides signature and pubkey
        templates.insert(std::make_pair(Script::TX_PUBKEYHASH, CScript() << OP_DUP << OP_HASH160
                                        << PUBKEYHASH_PLACEHOLDER << OP_EQUALVERIFY << OP_CHECKSIG));

        // Sender provides N pubkeys, receivers provides M signatures
        templates.insert(std::make_pair(Script::TX_MULTISIG, CScript() << SMALLINTEGER_PLACEHOLDER << PUBKEYS_PLACEHOLDER
                                        << SMALLINTEGER_PLACEHOLDER << OP_CHECKMULTISIG));
    }
};

/**
 * Return public keys or hashes from scriptPubKey, for 'standard' transaction types.
 */
bool Script::solver(const CScript &scriptPubKey, Script::TxnOutType &typeRet, std::vector<std::vector<unsigned char> > &vSolutionsRet)
{
    static SolverHelper sh;
    vSolutionsRet.clear();

    // Shortcut for pay-to-script-hash, which are more constrained than the other types:
    // it is always OP_HASH160/OP_HASH256, direct hash push, OP_EQUAL
    std::vector<unsigned char> hashBytes;
    if (scriptPubKey.IsPayToScriptHash(&hashBytes)) {
        typeRet = TX_SCRIPTHASH;
        vSolutionsRet.push_back(hashBytes);
        return true;
    }

    // Provably prunable, data-carrying output
    //
    // So long as script passes the IsUnspendable() test and all but the first
    // byte passes the IsPushOnly() test we don't care what exactly is in the
    // script.
    if (scriptPubKey.size() >= 1 && scriptPubKey[0] == OP_RETURN && scriptPubKey.IsPushOnly(scriptPubKey.begin()+1)) {
        typeRet = TX_NULL_DATA;
        return true;
    }

    // Scan templates
    const CScript& script1 = scriptPubKey;
    for (const std::pair<const Script::TxnOutType, CScript> &tplate : sh.templates) {
        const CScript& script2 = tplate.second;
        vSolutionsRet.clear();

        opcodetype opcode1, opcode2;
        std::vector<unsigned char> vch1, vch2;

        // Compare
        CScript::const_iterator pc1 = script1.begin();
        CScript::const_iterator pc2 = script2.begin();
        while (true) {
            if (pc1 == script1.end() && pc2 == script2.end()) {
                // Found a match
                typeRet = tplate.first;
                if (typeRet == TX_MULTISIG) {
                    // Additional checks for TX_MULTISIG:
                    unsigned char m = vSolutionsRet.front()[0];
                    unsigned char n = vSolutionsRet.back()[0];
                    if (m < 1 || n < 1 || m > n || vSolutionsRet.size()-2 != n)
                        break;
                }
                return true;
            }
            if (!script1.GetOp(pc1, opcode1, vch1))
                break;
            if (!script2.GetOp(pc2, opcode2, vch2))
                break;

            // Template matching opcodes:
            if (opcode2 == PUBKEYS_PLACEHOLDER) {
                while (PublicKeyUtils::isValidSize(vch1)) {
                    vSolutionsRet.push_back(vch1);
                    if (!script1.GetOp(pc1, opcode1, vch1))
                        break;
                }
                if (!script2.GetOp(pc2, opcode2, vch2))
                    break;
                // Normal situation is to fall through
                // to other if/else statements
            }

            if (opcode2 == PUBKEY_PLACEHOLDER) {
                if (!PublicKeyUtils::isValidSize(vch1))
                    break;
                vSolutionsRet.push_back(vch1);
            }
            else if (opcode2 == PUBKEYHASH_PLACEHOLDER) {
                if (vch1.size() != sizeof(uint160))
                    break;
                vSolutionsRet.push_back(vch1);
            }
            else if (opcode2 == SMALLINTEGER_PLACEHOLDER) {   // Single-byte small integer pushed onto vSolutions
                if (opcode1 == OP_0 || (opcode1 >= OP_1 && opcode1 <= OP_16)) {
                    unsigned char n = static_cast<unsigned char>(CScript::DecodeOP_N(opcode1));
                    vSolutionsRet.push_back(std::vector<unsigned char>(1, n));
                }
                else
                    break;
            }
            else if (opcode1 != opcode2 || vch1 != vch2) {
                // Others must match exactly
                break;
            }
        }
    }

    vSolutionsRet.clear();
    if (scriptPubKey.size() <= MAX_P2S_SCRIPT_SIZE) {
        typeRet = TX_SCRIPT;
        return true;
    }

    typeRet = TX_NONSTANDARD;
    return false;
}