diff --git a/src/base58.cpp b/src/base58.cpp index 4f05afe9e..0eb8a87b2 100644 --- a/src/base58.cpp +++ b/src/base58.cpp @@ -1,189 +1,185 @@ // Copyright (c) 2014-2016 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 #include #include #include #include #include #include #include #include /** All alphanumeric characters except for "0", "I", "O", and "l" */ static const char *pszBase58 = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"; static const int8_t mapBase58[256] = { -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, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, -1, -1, -1, -1, -1, -1, -1, 9, 10, 11, 12, 13, 14, 15, 16, -1, 17, 18, 19, 20, 21, -1, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, -1, -1, -1, -1, -1, -1, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, -1, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, -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, -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, -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, }; bool DecodeBase58(const char *psz, std::vector &vch, int max_ret_len) { // Skip leading spaces. while (*psz && IsSpace(*psz)) { psz++; } // Skip and count leading '1's. int zeroes = 0; int length = 0; while (*psz == '1') { zeroes++; if (zeroes > max_ret_len) { return false; } psz++; } // Allocate enough space in big-endian base256 representation. // log(58) / log(256), rounded up. int size = strlen(psz) * 733 / 1000 + 1; std::vector b256(size); // Process the characters. // guarantee not out of range static_assert(sizeof(mapBase58) / sizeof(mapBase58[0]) == 256, "mapBase58.size() should be 256"); while (*psz && !IsSpace(*psz)) { // Decode base58 character int carry = mapBase58[(uint8_t)*psz]; // Invalid b58 character if (carry == -1) { return false; } int i = 0; for (std::vector::reverse_iterator it = b256.rbegin(); (carry != 0 || i < length) && (it != b256.rend()); ++it, ++i) { carry += 58 * (*it); *it = carry % 256; carry /= 256; } assert(carry == 0); length = i; if (length + zeroes > max_ret_len) { return false; } psz++; } // Skip trailing spaces. while (IsSpace(*psz)) { psz++; } if (*psz != 0) { return false; } // Skip leading zeroes in b256. std::vector::iterator it = b256.begin() + (size - length); // Copy result into output vector. vch.reserve(zeroes + (b256.end() - it)); vch.assign(zeroes, 0x00); while (it != b256.end()) { vch.push_back(*(it++)); } return true; } -std::string EncodeBase58(const uint8_t *pbegin, const uint8_t *pend) { +std::string EncodeBase58(Span input) { // Skip & count leading zeroes. int zeroes = 0; int length = 0; - while (pbegin != pend && *pbegin == 0) { - pbegin++; + while (input.size() > 0 && input[0] == 0) { + input = input.subspan(1); zeroes++; } // Allocate enough space in big-endian base58 representation. // log(256) / log(58), rounded up. - int size = (pend - pbegin) * 138 / 100 + 1; + int size = input.size() * 138 / 100 + 1; std::vector b58(size); // Process the bytes. - while (pbegin != pend) { - int carry = *pbegin; + while (input.size() > 0) { + int carry = input[0]; int i = 0; // Apply "b58 = b58 * 256 + ch". for (std::vector::reverse_iterator it = b58.rbegin(); (carry != 0 || i < length) && (it != b58.rend()); it++, i++) { carry += 256 * (*it); *it = carry % 58; carry /= 58; } assert(carry == 0); length = i; - pbegin++; + input = input.subspan(1); } // Skip leading zeroes in base58 result. std::vector::iterator it = b58.begin() + (size - length); while (it != b58.end() && *it == 0) { it++; } // Translate the result into a string. std::string str; str.reserve(zeroes + (b58.end() - it)); str.assign(zeroes, '1'); while (it != b58.end()) { str += pszBase58[*(it++)]; } return str; } -std::string EncodeBase58(const std::vector &vch) { - return EncodeBase58(vch.data(), vch.data() + vch.size()); -} - bool DecodeBase58(const std::string &str, std::vector &vchRet, int max_ret_len) { if (!ValidAsCString(str)) { return false; } return DecodeBase58(str.c_str(), vchRet, max_ret_len); } -std::string EncodeBase58Check(const std::vector &vchIn) { +std::string EncodeBase58Check(Span input) { // add 4-byte hash check to the end - std::vector vch(vchIn); + std::vector vch(input.begin(), input.end()); uint256 hash = Hash(vch); vch.insert(vch.end(), (uint8_t *)&hash, (uint8_t *)&hash + 4); return EncodeBase58(vch); } bool DecodeBase58Check(const char *psz, std::vector &vchRet, int max_ret_len) { if (!DecodeBase58(psz, vchRet, max_ret_len > std::numeric_limits::max() - 4 ? std::numeric_limits::max() : max_ret_len + 4) || (vchRet.size() < 4)) { vchRet.clear(); return false; } // re-calculate the checksum, ensure it matches the included 4-byte checksum uint256 hash = Hash(MakeSpan(vchRet).first(vchRet.size() - 4)); if (memcmp(&hash, &vchRet[vchRet.size() - 4], 4) != 0) { vchRet.clear(); return false; } vchRet.resize(vchRet.size() - 4); return true; } bool DecodeBase58Check(const std::string &str, std::vector &vchRet, int max_ret) { if (!ValidAsCString(str)) { return false; } return DecodeBase58Check(str.c_str(), vchRet, max_ret); } diff --git a/src/base58.h b/src/base58.h index 68f22b80b..a841b0527 100644 --- a/src/base58.h +++ b/src/base58.h @@ -1,69 +1,64 @@ // 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. /** * Why base-58 instead of standard base-64 encoding? * - Don't want 0OIl characters that look the same in some fonts and * could be used to create visually identical looking data. * - A string with non-alphanumeric characters is not as easily accepted as * input. * - E-mail usually won't line-break if there's no punctuation to break at. * - Double-clicking selects the whole string as one word if it's all * alphanumeric. */ #ifndef BITCOIN_BASE58_H #define BITCOIN_BASE58_H #include +#include #include #include /** - * Encode a byte sequence as a base58-encoded string. - * pbegin and pend cannot be nullptr, unless both are. + * Encode a byte span as a base58-encoded string */ -std::string EncodeBase58(const uint8_t *pbegin, const uint8_t *pend); - -/** - * Encode a byte vector as a base58-encoded string - */ -std::string EncodeBase58(const std::vector &vch); +std::string EncodeBase58(Span input); /** * Decode a base58-encoded string (psz) into a byte vector (vchRet). * return true if decoding is successful. * psz cannot be nullptr. */ NODISCARD bool DecodeBase58(const char *psz, std::vector &vchRet, int max_ret_len); /** * Decode a base58-encoded string (str) into a byte vector (vchRet). * return true if decoding is successful. */ NODISCARD bool DecodeBase58(const std::string &str, std::vector &vchRet, int max_ret_len); /** - * Encode a byte vector into a base58-encoded string, including checksum + * Encode a byte span into a base58-encoded string, including checksum */ -std::string EncodeBase58Check(const std::vector &vchIn); +std::string EncodeBase58Check(Span input); /** * Decode a base58-encoded string (psz) that includes a checksum into a byte * vector (vchRet), return true if decoding is successful */ NODISCARD bool DecodeBase58Check(const char *psz, std::vector &vchRet, int max_ret_len); /** * Decode a base58-encoded string (str) that includes a checksum into a byte * vector (vchRet), return true if decoding is successful */ NODISCARD bool DecodeBase58Check(const std::string &str, std::vector &vchRet, int max_ret_len); #endif // BITCOIN_BASE58_H diff --git a/src/test/base58_tests.cpp b/src/test/base58_tests.cpp index 51612559c..740aa3131 100644 --- a/src/test/base58_tests.cpp +++ b/src/test/base58_tests.cpp @@ -1,113 +1,110 @@ // Copyright (c) 2011-2019 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 #include #include #include #include #include #include #include BOOST_FIXTURE_TEST_SUITE(base58_tests, BasicTestingSetup) // Goal: test low-level base58 encoding functionality BOOST_AUTO_TEST_CASE(base58_EncodeBase58) { UniValue tests = read_json(std::string(json_tests::base58_encode_decode, json_tests::base58_encode_decode + sizeof(json_tests::base58_encode_decode))); for (unsigned int idx = 0; idx < tests.size(); idx++) { UniValue test = tests[idx]; std::string strTest = test.write(); // Allow for extra stuff (useful for comments) if (test.size() < 2) { BOOST_ERROR("Bad test: " << strTest); continue; } std::vector sourcedata = ParseHex(test[0].get_str()); std::string base58string = test[1].get_str(); - BOOST_CHECK_MESSAGE( - EncodeBase58(sourcedata.data(), - sourcedata.data() + sourcedata.size()) == base58string, - strTest); + BOOST_CHECK_MESSAGE(EncodeBase58(sourcedata) == base58string, strTest); } } // Goal: test low-level base58 decoding functionality BOOST_AUTO_TEST_CASE(base58_DecodeBase58) { UniValue tests = read_json(std::string(json_tests::base58_encode_decode, json_tests::base58_encode_decode + sizeof(json_tests::base58_encode_decode))); std::vector result; for (unsigned int idx = 0; idx < tests.size(); idx++) { UniValue test = tests[idx]; std::string strTest = test.write(); // Allow for extra stuff (useful for comments) if (test.size() < 2) { BOOST_ERROR("Bad test: " << strTest); continue; } std::vector expected = ParseHex(test[0].get_str()); std::string base58string = test[1].get_str(); BOOST_CHECK_MESSAGE(DecodeBase58(base58string, result, 256), strTest); BOOST_CHECK_MESSAGE( result.size() == expected.size() && std::equal(result.begin(), result.end(), expected.begin()), strTest); } BOOST_CHECK(!DecodeBase58("invalid", result, 100)); BOOST_CHECK(!DecodeBase58(std::string("invalid"), result, 100)); BOOST_CHECK(!DecodeBase58(std::string("\0invalid", 8), result, 100)); BOOST_CHECK(DecodeBase58(std::string("good", 4), result, 100)); BOOST_CHECK(!DecodeBase58(std::string("bad0IOl", 7), result, 100)); BOOST_CHECK(!DecodeBase58(std::string("goodbad0IOl", 11), result, 100)); BOOST_CHECK(!DecodeBase58(std::string("good\0bad0IOl", 12), result, 100)); // check that DecodeBase58 skips whitespace, but still fails with unexpected // non-whitespace at the end. BOOST_CHECK(!DecodeBase58(" \t\n\v\f\r skip \r\f\v\n\t a", result, 3)); BOOST_CHECK(DecodeBase58(" \t\n\v\f\r skip \r\f\v\n\t ", result, 3)); std::vector expected = ParseHex("971a55"); BOOST_CHECK_EQUAL_COLLECTIONS(result.begin(), result.end(), expected.begin(), expected.end()); BOOST_CHECK(DecodeBase58Check(std::string("3vQB7B6MrGQZaxCuFg4oh", 21), result, 100)); BOOST_CHECK(!DecodeBase58Check(std::string("3vQB7B6MrGQZaxCuFg4oi", 21), result, 100)); BOOST_CHECK(!DecodeBase58Check(std::string("3vQB7B6MrGQZaxCuFg4oh0IOl", 25), result, 100)); BOOST_CHECK(!DecodeBase58Check( std::string("3vQB7B6MrGQZaxCuFg4oh\00IOl", 26), result, 100)); } BOOST_AUTO_TEST_CASE(base58_random_encode_decode) { for (int n = 0; n < 1000; ++n) { unsigned int len = 1 + InsecureRandBits(8); unsigned int zeroes = InsecureRandBool() ? InsecureRandRange(len + 1) : 0; auto data = Cat(std::vector(zeroes, '\000'), g_insecure_rand_ctx.randbytes(len - zeroes)); auto encoded = EncodeBase58Check(data); std::vector decoded; auto ok_too_small = DecodeBase58Check(encoded, decoded, InsecureRandRange(len)); BOOST_CHECK(!ok_too_small); auto ok = DecodeBase58Check(encoded, decoded, len + InsecureRandRange(257 - len)); BOOST_CHECK(ok); BOOST_CHECK(data == decoded); } } BOOST_AUTO_TEST_SUITE_END()