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