base58.cpp
1 // Copyright (c) 2014-2022 The Bitcoin Core developers 2 // Distributed under the MIT software license, see the accompanying 3 // file COPYING or http://www.opensource.org/licenses/mit-license.php. 4 5 #include <base58.h> 6 7 #include <hash.h> 8 #include <uint256.h> 9 #include <util/strencodings.h> 10 #include <util/string.h> 11 12 #include <assert.h> 13 #include <string.h> 14 15 #include <limits> 16 17 /** All alphanumeric characters except for "0", "I", "O", and "l" */ 18 static const char* pszBase58 = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"; 19 static const int8_t mapBase58[256] = { 20 -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1, 21 -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1, 22 -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1, 23 -1, 0, 1, 2, 3, 4, 5, 6, 7, 8,-1,-1,-1,-1,-1,-1, 24 -1, 9,10,11,12,13,14,15, 16,-1,17,18,19,20,21,-1, 25 22,23,24,25,26,27,28,29, 30,31,32,-1,-1,-1,-1,-1, 26 -1,33,34,35,36,37,38,39, 40,41,42,43,-1,44,45,46, 27 47,48,49,50,51,52,53,54, 55,56,57,-1,-1,-1,-1,-1, 28 -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1, 29 -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1, 30 -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1, 31 -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1, 32 -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1, 33 -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1, 34 -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1, 35 -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1, 36 }; 37 38 [[nodiscard]] static bool DecodeBase58(const char* psz, std::vector<unsigned char>& vch, int max_ret_len) 39 { 40 // Skip leading spaces. 41 while (*psz && IsSpace(*psz)) 42 psz++; 43 // Skip and count leading '1's. 44 int zeroes = 0; 45 int length = 0; 46 while (*psz == '1') { 47 zeroes++; 48 if (zeroes > max_ret_len) return false; 49 psz++; 50 } 51 // Allocate enough space in big-endian base256 representation. 52 int size = strlen(psz) * 733 /1000 + 1; // log(58) / log(256), rounded up. 53 std::vector<unsigned char> b256(size); 54 // Process the characters. 55 static_assert(std::size(mapBase58) == 256, "mapBase58.size() should be 256"); // guarantee not out of range 56 while (*psz && !IsSpace(*psz)) { 57 // Decode base58 character 58 int carry = mapBase58[(uint8_t)*psz]; 59 if (carry == -1) // Invalid b58 character 60 return false; 61 int i = 0; 62 for (std::vector<unsigned char>::reverse_iterator it = b256.rbegin(); (carry != 0 || i < length) && (it != b256.rend()); ++it, ++i) { 63 carry += 58 * (*it); 64 *it = carry % 256; 65 carry /= 256; 66 } 67 assert(carry == 0); 68 length = i; 69 if (length + zeroes > max_ret_len) return false; 70 psz++; 71 } 72 // Skip trailing spaces. 73 while (IsSpace(*psz)) 74 psz++; 75 if (*psz != 0) 76 return false; 77 // Skip leading zeroes in b256. 78 std::vector<unsigned char>::iterator it = b256.begin() + (size - length); 79 // Copy result into output vector. 80 vch.reserve(zeroes + (b256.end() - it)); 81 vch.assign(zeroes, 0x00); 82 while (it != b256.end()) 83 vch.push_back(*(it++)); 84 return true; 85 } 86 87 std::string EncodeBase58(Span<const unsigned char> input) 88 { 89 // Skip & count leading zeroes. 90 int zeroes = 0; 91 int length = 0; 92 while (input.size() > 0 && input[0] == 0) { 93 input = input.subspan(1); 94 zeroes++; 95 } 96 // Allocate enough space in big-endian base58 representation. 97 int size = input.size() * 138 / 100 + 1; // log(256) / log(58), rounded up. 98 std::vector<unsigned char> b58(size); 99 // Process the bytes. 100 while (input.size() > 0) { 101 int carry = input[0]; 102 int i = 0; 103 // Apply "b58 = b58 * 256 + ch". 104 for (std::vector<unsigned char>::reverse_iterator it = b58.rbegin(); (carry != 0 || i < length) && (it != b58.rend()); it++, i++) { 105 carry += 256 * (*it); 106 *it = carry % 58; 107 carry /= 58; 108 } 109 110 assert(carry == 0); 111 length = i; 112 input = input.subspan(1); 113 } 114 // Skip leading zeroes in base58 result. 115 std::vector<unsigned char>::iterator it = b58.begin() + (size - length); 116 while (it != b58.end() && *it == 0) 117 it++; 118 // Translate the result into a string. 119 std::string str; 120 str.reserve(zeroes + (b58.end() - it)); 121 str.assign(zeroes, '1'); 122 while (it != b58.end()) 123 str += pszBase58[*(it++)]; 124 return str; 125 } 126 127 bool DecodeBase58(const std::string& str, std::vector<unsigned char>& vchRet, int max_ret_len) 128 { 129 if (!ContainsNoNUL(str)) { 130 return false; 131 } 132 return DecodeBase58(str.c_str(), vchRet, max_ret_len); 133 } 134 135 std::string EncodeBase58Check(Span<const unsigned char> input) 136 { 137 // add 4-byte hash check to the end 138 std::vector<unsigned char> vch(input.begin(), input.end()); 139 uint256 hash = Hash(vch); 140 vch.insert(vch.end(), (unsigned char*)&hash, (unsigned char*)&hash + 4); 141 return EncodeBase58(vch); 142 } 143 144 [[nodiscard]] static bool DecodeBase58Check(const char* psz, std::vector<unsigned char>& vchRet, int max_ret_len) 145 { 146 if (!DecodeBase58(psz, vchRet, max_ret_len > std::numeric_limits<int>::max() - 4 ? std::numeric_limits<int>::max() : max_ret_len + 4) || 147 (vchRet.size() < 4)) { 148 vchRet.clear(); 149 return false; 150 } 151 // re-calculate the checksum, ensure it matches the included 4-byte checksum 152 uint256 hash = Hash(Span{vchRet}.first(vchRet.size() - 4)); 153 if (memcmp(&hash, &vchRet[vchRet.size() - 4], 4) != 0) { 154 vchRet.clear(); 155 return false; 156 } 157 vchRet.resize(vchRet.size() - 4); 158 return true; 159 } 160 161 bool DecodeBase58Check(const std::string& str, std::vector<unsigned char>& vchRet, int max_ret) 162 { 163 if (!ContainsNoNUL(str)) { 164 return false; 165 } 166 return DecodeBase58Check(str.c_str(), vchRet, max_ret); 167 }