diff --git a/src/base58.cpp b/src/base58.cpp index b0fa20a0b0..f25b580026 100644 --- a/src/base58.cpp +++ b/src/base58.cpp @@ -1,151 +1,169 @@ // 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 /** 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) { // Skip leading spaces. while (*psz && IsSpace(*psz)) { psz++; } // Skip and count leading '1's. int zeroes = 0; int length = 0; while (*psz == '1') { zeroes++; 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 - const char *ch = strchr(pszBase58, *psz); - if (ch == nullptr) { + int carry = mapBase58[(uint8_t)*psz]; + // Invalid b58 character + if (carry == -1) { return false; } - // Apply "b256 = b256 * 58 + ch". - int carry = ch - pszBase58; 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; 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); while (it != b256.end() && *it == 0) it++; // 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) { // Skip & count leading zeroes. int zeroes = 0; int length = 0; while (pbegin != pend && *pbegin == 0) { pbegin++; zeroes++; } // Allocate enough space in big-endian base58 representation. // log(256) / log(58), rounded up. int size = (pend - pbegin) * 138 / 100 + 1; std::vector b58(size); // Process the bytes. while (pbegin != pend) { int carry = *pbegin; 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++; } // 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) { return DecodeBase58(str.c_str(), vchRet); } std::string EncodeBase58Check(const std::vector &vchIn) { // add 4-byte hash check to the end std::vector vch(vchIn); uint256 hash = Hash(vch.begin(), vch.end()); vch.insert(vch.end(), (uint8_t *)&hash, (uint8_t *)&hash + 4); return EncodeBase58(vch); } bool DecodeBase58Check(const char *psz, std::vector &vchRet) { if (!DecodeBase58(psz, vchRet) || (vchRet.size() < 4)) { vchRet.clear(); return false; } // re-calculate the checksum, ensure it matches the included 4-byte checksum uint256 hash = Hash(vchRet.begin(), vchRet.end() - 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) { return DecodeBase58Check(str.c_str(), vchRet); } diff --git a/src/test/data/base58_encode_decode.json b/src/test/data/base58_encode_decode.json index 9448f256d9..1a4bd7f458 100644 --- a/src/test/data/base58_encode_decode.json +++ b/src/test/data/base58_encode_decode.json @@ -1,14 +1,16 @@ [ ["", ""], ["61", "2g"], ["626262", "a3gV"], ["636363", "aPEr"], ["73696d706c792061206c6f6e6720737472696e67", "2cFupjhnEsSn59qHXstmK2ffpLv2"], ["00eb15231dfceb60925886b67d065299925915aeb172c06647", "1NS17iag9jJgTHD1VXjvLCEnZuQ3rJDE9L"], ["516b6fcd0f", "ABnLTmg"], ["bf4f89001e670274dd", "3SEo3LWLoPntC"], ["572e4794", "3EFU7m"], ["ecac89cad93923c02321", "EJDM8drfXA6uyA"], ["10c8511e", "Rt5zm"], -["00000000000000000000", "1111111111"] +["00000000000000000000", "1111111111"], +["000111d38e5fc9071ffcd20b4a763cc9ae4f252bb4e48fd66a835e252ada93ff480d6dd43dc62a641155a5", "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"], +["000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f404142434445464748494a4b4c4d4e4f505152535455565758595a5b5c5d5e5f606162636465666768696a6b6c6d6e6f707172737475767778797a7b7c7d7e7f808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9fa0a1a2a3a4a5a6a7a8a9aaabacadaeafb0b1b2b3b4b5b6b7b8b9babbbcbdbebfc0c1c2c3c4c5c6c7c8c9cacbcccdcecfd0d1d2d3d4d5d6d7d8d9dadbdcdddedfe0e1e2e3e4e5e6e7e8e9eaebecedeeeff0f1f2f3f4f5f6f7f8f9fafbfcfdfeff", "1cWB5HCBdLjAuqGGReWE3R3CguuwSjw6RHn39s2yuDRTS5NsBgNiFpWgAnEx6VQi8csexkgYw3mdYrMHr8x9i7aEwP8kZ7vccXWqKDvGv3u1GxFKPuAkn8JCPPGDMf3vMMnbzm6Nh9zh1gcNsMvH3ZNLmP5fSG6DGbbi2tuwMWPthr4boWwCxf7ewSgNQeacyozhKDDQQ1qL5fQFUW52QKUZDZ5fw3KXNQJMcNTcaB723LchjeKun7MuGW5qyCBZYzA1KjofN1gYBV3NqyhQJ3Ns746GNuf9N2pQPmHz4xpnSrrfCvy6TVVz5d4PdrjeshsWQwpZsZGzvbdAdN8MKV5QsBDY"] ]