diff --git a/src/Makefile.am b/src/Makefile.am --- a/src/Makefile.am +++ b/src/Makefile.am @@ -79,6 +79,7 @@ addrdb.h \ addrman.h \ base58.h \ + cashaddr.h \ bloom.h \ blockencodings.h \ chain.h \ @@ -309,6 +310,7 @@ libbitcoin_common_a_SOURCES = \ amount.cpp \ base58.cpp \ + cashaddr.cpp \ chainparams.cpp \ coins.cpp \ compressor.cpp \ diff --git a/src/Makefile.test.include b/src/Makefile.test.include --- a/src/Makefile.test.include +++ b/src/Makefile.test.include @@ -75,6 +75,7 @@ test/base32_tests.cpp \ test/base58_tests.cpp \ test/base64_tests.cpp \ + test/cashaddr_tests.cpp \ test/bip32_tests.cpp \ test/blockcheck_tests.cpp \ test/blockencodings_tests.cpp \ diff --git a/src/base58.h b/src/base58.h --- a/src/base58.h +++ b/src/base58.h @@ -19,7 +19,6 @@ #include "chainparams.h" #include "key.h" #include "pubkey.h" -#include "script/script.h" #include "script/standard.h" #include "support/allocators/zeroafterfree.h" diff --git a/src/base58.cpp b/src/base58.cpp --- a/src/base58.cpp +++ b/src/base58.cpp @@ -3,9 +3,12 @@ // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include "base58.h" +#include "cashaddr.h" #include "hash.h" +#include "script/script.h" #include "uint256.h" +#include "utilstrencodings.h" #include #include @@ -208,83 +211,95 @@ } namespace { -/** base58-encoded Bitcoin addresses. - * Public-key-hash-addresses have version 0 (or 111 testnet). - * The data vector contains RIPEMD160(SHA256(pubkey)), where pubkey is the - * serialized public key. - * Script-hash-addresses have version 5 (or 196 testnet). - * The data vector contains RIPEMD160(SHA256(cscript)), where cscript is the - * serialized redemption script. - */ -class CBitcoinAddress : public CBase58Data { -public: - bool Set(const CKeyID &id); - bool Set(const CScriptID &id); - bool Set(const CTxDestination &dest); - bool IsValid() const; - bool IsValid(const CChainParams ¶ms) const; - - CBitcoinAddress() {} - CBitcoinAddress(const CTxDestination &dest) { Set(dest); } - CBitcoinAddress(const std::string &strAddress) { SetString(strAddress); } - CBitcoinAddress(const char *pszAddress) { SetString(pszAddress); } - - CTxDestination Get() const; -}; -class CBitcoinAddressVisitor : public boost::static_visitor { +const uint8_t CASHADDR_VERSION_PUBKEY = 0; +const uint8_t CASHADDR_VERISON_SCRIPT = 8; + +class DestinationEncoder : public boost::static_visitor { private: - CBitcoinAddress *addr; + const CChainParams &m_params; public: - CBitcoinAddressVisitor(CBitcoinAddress *addrIn) : addr(addrIn) {} + DestinationEncoder(const CChainParams ¶ms) : m_params(params) {} + + std::string operator()(const CKeyID &id) const { + std::vector data = {CASHADDR_VERSION_PUBKEY}; + ConvertBits<8, 5, true>(data, id.begin(), id.end()); + return cashaddr::Encode(m_params.CashAddrHRP(), data); + } + + std::string operator()(const CScriptID &id) const { + std::vector data = {CASHADDR_VERISON_SCRIPT}; + ConvertBits<8, 5, true>(data, id.begin(), id.end()); + return cashaddr::Encode(m_params.CashAddrHRP(), data); + } - bool operator()(const CKeyID &id) const { return addr->Set(id); } - bool operator()(const CScriptID &id) const { return addr->Set(id); } - bool operator()(const CNoDestination &no) const { return false; } + std::string operator()(const CNoDestination &no) const { return ""; } }; -} // anon namespace +CTxDestination +DecodeCashAddr(const std::pair> &bech, + const CChainParams ¶ms) { -bool CBitcoinAddress::Set(const CKeyID &id) { - SetData(Params().Base58Prefix(CChainParams::PUBKEY_ADDRESS), &id, 20); - return true; -} + if (bech.first != params.CashAddrHRP()) { + return CNoDestination{}; + } -bool CBitcoinAddress::Set(const CScriptID &id) { - SetData(Params().Base58Prefix(CChainParams::SCRIPT_ADDRESS), &id, 20); - return true; -} + if (bech.second.empty()) { + return CNoDestination{}; + } -bool CBitcoinAddress::Set(const CTxDestination &dest) { - return boost::apply_visitor(CBitcoinAddressVisitor(this), dest); -} + std::vector data; + if (!ConvertBits<5, 8, false>(data, begin(bech.second) + 1, + end(bech.second))) { + return CNoDestination(); + } -bool CBitcoinAddress::IsValid() const { - return IsValid(Params()); -} + if (data.size() != 20) { + return CNoDestination{}; + } + + uint160 hash; + memcpy(hash.begin(), &data[0], 20); -bool CBitcoinAddress::IsValid(const CChainParams ¶ms) const { - bool fCorrectSize = vchData.size() == 20; - bool fKnownVersion = - vchVersion == params.Base58Prefix(CChainParams::PUBKEY_ADDRESS) || - vchVersion == params.Base58Prefix(CChainParams::SCRIPT_ADDRESS); - return fCorrectSize && fKnownVersion; + int version = bech.second.at(0); + if (version == CASHADDR_VERSION_PUBKEY) { + return CKeyID(hash); + } + if (version == CASHADDR_VERISON_SCRIPT) { + return CScriptID(hash); + } + + // unknown version + return CNoDestination{}; } -CTxDestination CBitcoinAddress::Get() const { - if (!IsValid()) return CNoDestination(); - uint160 id; - memcpy(&id, &vchData[0], 20); - if (vchVersion == Params().Base58Prefix(CChainParams::PUBKEY_ADDRESS)) { - return CKeyID(id); - } else if (vchVersion == - Params().Base58Prefix(CChainParams::SCRIPT_ADDRESS)) { - return CScriptID(id); - } else { - return CNoDestination(); +CTxDestination DecodeDestination(const std::string &str, + const CChainParams ¶ms) { + std::vector data; + uint160 hash; + if (DecodeBase58Check(str, data)) { + // Base58Check decoding + const std::vector &pubkey_prefix = + params.Base58Prefix(CChainParams::PUBKEY_ADDRESS); + if (data.size() == 20 + pubkey_prefix.size() && + std::equal(pubkey_prefix.begin(), pubkey_prefix.end(), + data.begin())) { + memcpy(hash.begin(), &data[pubkey_prefix.size()], 20); + return CKeyID(hash); + } + const std::vector &script_prefix = + params.Base58Prefix(CChainParams::SCRIPT_ADDRESS); + if (data.size() == 20 + script_prefix.size() && + std::equal(script_prefix.begin(), script_prefix.end(), + data.begin())) { + memcpy(hash.begin(), &data[script_prefix.size()], 20); + return CScriptID(hash); + } } + return DecodeCashAddr(cashaddr::Decode(str), params); } +} // namespace void CBitcoinSecret::SetKey(const CKey &vchSecret) { assert(vchSecret.IsValid()); @@ -318,20 +333,18 @@ } std::string EncodeDestination(const CTxDestination &dest) { - CBitcoinAddress addr(dest); - if (!addr.IsValid()) return ""; - return addr.ToString(); + return boost::apply_visitor(DestinationEncoder(Params()), dest); } CTxDestination DecodeDestination(const std::string &str) { - return CBitcoinAddress(str).Get(); + return DecodeDestination(str, Params()); } bool IsValidDestinationString(const std::string &str, const CChainParams ¶ms) { - return CBitcoinAddress(str).IsValid(params); + return IsValidDestination(DecodeDestination(str, params)); } bool IsValidDestinationString(const std::string &str) { - return CBitcoinAddress(str).IsValid(); + return IsValidDestination(DecodeDestination(str, Params())); } diff --git a/src/cashaddr.h b/src/cashaddr.h new file mode 100644 --- /dev/null +++ b/src/cashaddr.h @@ -0,0 +1,26 @@ +// Copyright (c) 2017 Pieter Wuille +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +// Cashaddr is a bech32 with a few modification. + +// Bech32 is a string encoding format used in newer address types. +// The output consists of a human-readable part (alphanumeric), a +// separator character (1), and a base32 data section, the last +// 6 characters of which are a checksum. +// +// For more information, see BIP 173. + +#include +#include +#include + +namespace cashaddr { + +/** Encode a Bech32 string. Returns the empty string in case of failure. */ +std::string Encode(const std::string &hrp, const std::vector &values); + +/** Decode a Bech32 string. Returns (hrp, data). Empty hrp means failure. */ +std::pair> Decode(const std::string &str); + +} // namespace cashaddr diff --git a/src/cashaddr.cpp b/src/cashaddr.cpp new file mode 100644 --- /dev/null +++ b/src/cashaddr.cpp @@ -0,0 +1,219 @@ +// Copyright (c) 2017 Pieter Wuille +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include "cashaddr.h" + +namespace { + +typedef std::vector data; + +/** The Bech32 character set for encoding. */ +const char *CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l"; + +/** The Bech32 character set for decoding. */ +const int8_t CHARSET_REV[128] = { + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 15, -1, 10, 17, 21, 20, 26, 30, 7, + 5, -1, -1, -1, -1, -1, -1, -1, 29, -1, 24, 13, 25, 9, 8, 23, -1, 18, 22, + 31, 27, 19, -1, 1, 0, 3, 16, 11, 28, 12, 14, 6, 4, 2, -1, -1, -1, -1, + -1, -1, 29, -1, 24, 13, 25, 9, 8, 23, -1, 18, 22, 31, 27, 19, -1, 1, 0, + 3, 16, 11, 28, 12, 14, 6, 4, 2, -1, -1, -1, -1, -1}; + +/** Concatenate two byte arrays. */ +data Cat(data x, const data &y) { + x.insert(x.end(), y.begin(), y.end()); + return x; +} + +/** + * This function will compute what 6 5-bit values to XOR into the last 6 input + * values, in order to make the checksum 0. These 6 values are packed together + * in a single 30-bit integer. The higher bits correspond to earlier values. + */ +uint32_t PolyMod(const data &v) { + /** + * The input is interpreted as a list of coefficients of a polynomial over F + * = GF(32), with an implicit 1 in front. If the input is [v0,v1,v2,v3,v4], + * that polynomial is v(x) = 1*x^5 + v0*x^4 + v1*x^3 + v2*x^2 + v3*x + v4. + * The implicit 1 guarantees that [v0,v1,v2,...] has a distinct checksum + * from [0,v0,v1,v2,...]. + * + * The output is a 30-bit integer whose 5-bit groups are the coefficients of + * the remainder of v(x) mod g(x), where g(x) is the Bech32 generator, x^6 + + * {29}x^5 + {22}x^4 + {20}x^3 + {21}x^2 + {29}x + {18}. g(x) is chosen in + * such a way that the resulting code is a BCH code, guaranteeing detection + * of up to 3 errors within a window of 1023 characters. Among the various + * possible BCH codes, one was selected to in fact guarantee detection of up + * to 4 errors within a window of 89 characters. + * + * Note that the coefficients are elements of GF(32), here represented as + * decimal numbers between {}. In this finite field, addition is just XOR of + * the corresponding numbers. For example, {27} + {13} = {27 ^ 13} = {22}. + * Multiplication is more complicated, and requires treating the bits of + * values themselves as coefficients of a polynomial over a smaller field, + * GF(2), and multiplying those polynomials mod a^5 + a^3 + 1. For example, + * {5} * {26} = (a^2 + 1) * (a^4 + a^3 + a) = (a^4 + a^3 + a) * a^2 + (a^4 + + * a^3 + a) = a^6 + a^5 + a^4 + a = a^3 + 1 (mod a^5 + a^3 + 1) = {9}. + * + * During the course of the loop below, `c` contains the bitpacked + * coefficients of the polynomial constructed from just the values of v that + * were processed so far, mod g(x). In the above example, `c` initially + * corresponds to 1 mod (x), and after processing 2 inputs of v, it + * corresponds to x^2 + v0*x + v1 mod g(x). As 1 mod g(x) = 1, that is the + * starting value for `c`. + */ + uint32_t c = 1; + for (size_t i = 0; i < v.size(); ++i) { + /* + * We want to update `c` to correspond to a polynomial with one extra + * term. If the initial value of `c` consists of the coefficients of + * c(x) = f(x) mod g(x), we modify it to correspond to c'(x) = (f(x) * x + * + v[i]) mod g(x), where v[i] is the next input to process. + * Simplifying: + * c'(x) = (f(x) * x + v[i]) mod g(x) + * ((f(x) mod g(x)) * x + v[i]) mod g(x) + * (c(x) * x + v[i]) mod g(x) + * If c(x) = c0*x^5 + c1*x^4 + c2*x^3 + c3*x^2 + c4*x + c5, we want to + * compute + * c'(x) = (c0*x^5 + c1*x^4 + c2*x^3 + c3*x^2 + c4*x + c5) * x + v[i] + * mod g(x) + * = c0*x^6 + c1*x^5 + c2*x^4 + c3*x^3 + c4*x^2 + c5*x + v[i] mod + * g(x) + * = c0*(x^6 mod g(x)) + c1*x^5 + c2*x^4 + c3*x^3 + c4*x^2 + c5*x + * + v[i] + * If we call (x^6 mod g(x)) = k(x), this can be written as + * c'(x) = (c1*x^5 + c2*x^4 + c3*x^3 + c4*x^2 + c5*x + v[i]) + c0*k(x) + */ + + // First, determine the value of c0: + uint8_t c0 = c >> 25; + + // Then compute c1*x^5 + c2*x^4 + c3*x^3 + c4*x^2 + c5*x + v[i]: + c = ((c & 0x1ffffff) << 5) ^ v[i]; + + // Finally, for each set bit n in c0, conditionally add {2^n}k(x): + if (c0 & 1) { + // k(x) = {29}x^5 + {22}x^4 + {20}x^3 + {21}x^2 + {29}x + {18} + c ^= 0x3b6a57b2; + } + + if (c0 & 2) { + // {2}k(x) = {19}x^5 + {5}x^4 + x^3 + {3}x^2 + {19}x + {13} + c ^= 0x26508e6d; + } + + if (c0 & 4) { + // {4}k(x) = {15}x^5 + {10}x^4 + {2}x^3 + {6}x^2 + {15}x + {26} + c ^= 0x1ea119fa; + } + + if (c0 & 8) { + // {8}k(x) = {30}x^5 + {20}x^4 + {4}x^3 + {12}x^2 + {30}x + {29} + c ^= 0x3d4233dd; + } + + if (c0 & 16) { + // {16}k(x) = {21}x^5 + x^4 + {8}x^3 + {24}x^2 + {21}x + {19} + c ^= 0x2a1462b3; + } + } + return c; +} + +/** Convert to lower case. */ +inline unsigned char LowerCase(unsigned char c) { + return (c >= 'A' && c <= 'Z') ? (c - 'A') + 'a' : c; +} + +/** Expand a HRP for use in checksum computation. */ +data ExpandHRP(const std::string &hrp) { + data ret; + ret.resize(hrp.size() * 2 + 1); + for (size_t i = 0; i < hrp.size(); ++i) { + unsigned char c = hrp[i]; + ret[i] = c >> 5; + ret[i + hrp.size() + 1] = c & 0x1f; + } + ret[hrp.size()] = 0; + return ret; +} + +/** Verify a checksum. */ +bool VerifyChecksum(const std::string &hrp, const data &values) { + // PolyMod computes what value to xor into the final values to make the + // checksum 0. However, if we required that the checksum was 0, it would be + // the case that appending a 0 to a valid list of values would result in a + // new valid list. For that reason, Bech32 requires the resulting checksum + // to be 1 instead. + return PolyMod(Cat(ExpandHRP(hrp), values)) == 1; +} + +/** Create a checksum. */ +data CreateChecksum(const std::string &hrp, const data &values) { + data enc = Cat(ExpandHRP(hrp), values); + enc.resize(enc.size() + 6); // Append 6 zeroes + // Determine what to XOR into those 6 zeroes. + uint32_t mod = PolyMod(enc) ^ 1; + data ret; + ret.resize(6); + for (size_t i = 0; i < 6; ++i) { + // Convert the 5-bit groups in mod to checksum values. + ret[i] = (mod >> (5 * (5 - i))) & 31; + } + return ret; +} + +} // namespace + +namespace cashaddr { + +/** Encode a Bech32 string. */ +std::string Encode(const std::string &hrp, const data &values) { + data checksum = CreateChecksum(hrp, values); + data combined = Cat(values, checksum); + std::string ret = hrp + ':'; + ret.reserve(ret.size() + combined.size()); + for (size_t i = 0; i < combined.size(); ++i) { + ret += CHARSET[combined[i]]; + } + return ret; +} + +/** Decode a Bech32 string. */ +std::pair Decode(const std::string &str) { + bool lower = false, upper = false; + for (size_t i = 0; i < str.size(); ++i) { + unsigned char c = str[i]; + if (c != ':' && (c < 33 || c > 126)) + return std::make_pair(std::string(), data()); + if (c >= 'a' && c <= 'z') lower = true; + if (c >= 'A' && c <= 'Z') upper = true; + } + if (lower && upper) return std::make_pair(std::string(), data()); + size_t pos = str.rfind(':'); + if (str.size() > 90 || pos == str.npos || pos == 0 || + pos + 7 > str.size()) { + return std::make_pair(std::string(), data()); + } + data values; + values.resize(str.size() - 1 - pos); + for (size_t i = 0; i < str.size() - 1 - pos; ++i) { + unsigned char c = str[i + pos + 1]; + if (CHARSET_REV[c] == -1) { + return std::make_pair(std::string(), data()); + } + values[i] = CHARSET_REV[c]; + } + std::string hrp; + for (size_t i = 0; i < pos; ++i) { + hrp += LowerCase(str[i]); + } + if (!VerifyChecksum(hrp, values)) { + return std::make_pair(std::string(), data()); + } + return std::make_pair(hrp, data(values.begin(), values.end() - 6)); +} + +} // namespace cashaddr diff --git a/src/chainparams.h b/src/chainparams.h --- a/src/chainparams.h +++ b/src/chainparams.h @@ -86,6 +86,7 @@ const std::vector &Base58Prefix(Base58Type type) const { return base58Prefixes[type]; } + const std::string &CashAddrHRP() const { return cashaddrHDR; } const std::vector &FixedSeeds() const { return vFixedSeeds; } const CCheckpointData &Checkpoints() const { return checkpointData; } const ChainTxData &TxData() const { return chainTxData; } @@ -100,6 +101,7 @@ uint64_t nPruneAfterHeight; std::vector vSeeds; std::vector base58Prefixes[MAX_BASE58_TYPES]; + std::string cashaddrHDR; std::string strNetworkID; CBlock genesis; std::vector vFixedSeeds; diff --git a/src/chainparams.cpp b/src/chainparams.cpp --- a/src/chainparams.cpp +++ b/src/chainparams.cpp @@ -195,6 +195,7 @@ base58Prefixes[SECRET_KEY] = std::vector(1, 128); base58Prefixes[EXT_PUBLIC_KEY] = {0x04, 0x88, 0xB2, 0x1E}; base58Prefixes[EXT_SECRET_KEY] = {0x04, 0x88, 0xAD, 0xE4}; + cashaddrHDR = "bitcoincash"; vFixedSeeds = std::vector( pnSeed6_main, pnSeed6_main + ARRAYLEN(pnSeed6_main)); @@ -358,6 +359,7 @@ base58Prefixes[SECRET_KEY] = std::vector(1, 239); base58Prefixes[EXT_PUBLIC_KEY] = {0x04, 0x35, 0x87, 0xCF}; base58Prefixes[EXT_SECRET_KEY] = {0x04, 0x35, 0x83, 0x94}; + cashaddrHDR = "bcctest"; vFixedSeeds = std::vector( pnSeed6_test, pnSeed6_test + ARRAYLEN(pnSeed6_test)); @@ -474,6 +476,7 @@ base58Prefixes[SECRET_KEY] = std::vector(1, 239); base58Prefixes[EXT_PUBLIC_KEY] = {0x04, 0x35, 0x87, 0xCF}; base58Prefixes[EXT_SECRET_KEY] = {0x04, 0x35, 0x83, 0x94}; + cashaddrHDR = "bccreg"; } void UpdateBIP9Parameters(Consensus::DeploymentPos d, int64_t nStartTime, diff --git a/src/test/base58_tests.cpp b/src/test/base58_tests.cpp --- a/src/test/base58_tests.cpp +++ b/src/test/base58_tests.cpp @@ -236,7 +236,7 @@ continue; } std::string address = EncodeDestination(dest); - BOOST_CHECK_MESSAGE(address == exp_base58string, + BOOST_CHECK_MESSAGE(dest == DecodeDestination(address), "mismatch: " + strTest); } } diff --git a/src/test/cashaddr_tests.cpp b/src/test/cashaddr_tests.cpp new file mode 100644 --- /dev/null +++ b/src/test/cashaddr_tests.cpp @@ -0,0 +1,57 @@ +// Copyright (c) 2017 Pieter Wuille +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include "cashaddr.h" +#include "test/test_bitcoin.h" + +#include + +BOOST_FIXTURE_TEST_SUITE(cashaddr_tests, BasicTestingSetup) + +bool CaseInsensitiveEqual(const std::string &s1, const std::string &s2) { + if (s1.size() != s2.size()) return false; + for (size_t i = 0; i < s1.size(); ++i) { + char c1 = s1[i]; + if (c1 >= 'A' && c1 <= 'Z') c1 -= ('A' - 'a'); + char c2 = s2[i]; + if (c2 >= 'A' && c2 <= 'Z') c2 -= ('A' - 'a'); + if (c1 != c2) return false; + } + return true; +} + +BOOST_AUTO_TEST_CASE(bip173_testvectors_valid) { + static const std::string CASES[] = { + "A:2UEL5L", "an83characterlonghumanreadablepartthatcontainsthenumber1an" + "dtheexcludedcharactersbio:tt5tgs", + "abcdef:qpzry9x8gf2tvdw0s3jn54khce6mua7lmqqqxw", + "1:qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq" + "qqqqqqqqqqqqqqc8247j", + "split:checkupstagehandshakeupstreamerranterredcaperred2y9e3w", + }; + for (const std::string &str : CASES) { + auto ret = cashaddr::Decode(str); + BOOST_CHECK_MESSAGE(!ret.first.empty(), str); + std::string recode = cashaddr::Encode(ret.first, ret.second); + BOOST_CHECK(!recode.empty()); + BOOST_CHECK(CaseInsensitiveEqual(str, recode)); + } +} + +BOOST_AUTO_TEST_CASE(bip173_testvectors_invalid) { + static const std::string CASES[] = { + " :nwldj5", "\x7f" + ":axkwrx", + "an84characterslonghumanreadablepartthatcontainsthenumber1andtheexclude" + "dcharactersbio:569pvx", + "pzry9x0s0muk", ":pzry9x0s0muk", "x:b4n0q5v", "li:dgmt3", + "de:lg7wt\xff", + }; + for (const std::string &str : CASES) { + auto ret = cashaddr::Decode(str); + BOOST_CHECK(ret.first.empty()); + } +} + +BOOST_AUTO_TEST_SUITE_END() diff --git a/src/utilstrencodings.h b/src/utilstrencodings.h --- a/src/utilstrencodings.h +++ b/src/utilstrencodings.h @@ -142,4 +142,28 @@ */ bool ParseFixedPoint(const std::string &val, int decimals, int64_t *amount_out); +/** Convert from one power-of-2 number base to another. */ +template +bool ConvertBits(O &out, I it, I end) { + size_t acc = 0; + size_t bits = 0; + constexpr size_t maxv = (1 << tobits) - 1; + constexpr size_t max_acc = (1 << (frombits + tobits - 1)) - 1; + while (it != end) { + acc = ((acc << frombits) | *it) & max_acc; + bits += frombits; + while (bits >= tobits) { + bits -= tobits; + out.push_back((acc >> bits) & maxv); + } + ++it; + } + if (pad) { + if (bits) out.push_back((acc << (tobits - bits)) & maxv); + } else if (bits >= frombits || ((acc << (tobits - bits)) & maxv)) { + return false; + } + return true; +} + #endif // BITCOIN_UTILSTRENCODINGS_H