16818395385

Committed 07 Aug 2025 11:51PM UTC coverage: 90.663% (-0.01%) from 90.675%

Build # 16818395385

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #5051 from randombit/jack/base58-improvements

Base58 optimizations

Run Details

100010 of 110309 relevant lines covered (90.66%)

12254698.18 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

99.21

/src/lib/codec/base58/base58.cpp

/*
* (C) 2018,2020 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/base58.h>

#include <botan/bigint.h>
#include <botan/exceptn.h>
#include <botan/hash.h>
#include <botan/internal/ct_utils.h>
#include <botan/internal/divide.h>
#include <botan/internal/loadstor.h>
#include <botan/internal/mul128.h>

namespace Botan {

namespace {

uint32_t sha256_d_checksum(const uint8_t input[], size_t input_length) {
   auto sha256 = HashFunction::create_or_throw("SHA-256");

   std::vector<uint8_t> checksum(32);

   sha256->update(input, input_length);
   sha256->final(checksum);

   sha256->update(checksum);
   sha256->final(checksum);

   return load_be<uint32_t>(checksum.data(), 0);
}

char lookup_base58_char(uint8_t x) {
   // "123456789 ABCDEFGH JKLMN PQRSTUVWXYZ abcdefghijk mnopqrstuvwxyz"
   BOTAN_DEBUG_ASSERT(x < 58);

   // This works by computing offset(x) such that x + offset(x) is equal to the
   // desired character

   size_t offset = 49;

   offset += CT::Mask<uint8_t>::is_gt(x, 8).if_set_return(7);
   offset += CT::Mask<uint8_t>::is_gt(x, 16).if_set_return(1);
   offset += CT::Mask<uint8_t>::is_gt(x, 21).if_set_return(1);
   offset += CT::Mask<uint8_t>::is_gt(x, 32).if_set_return(6);
   offset += CT::Mask<uint8_t>::is_gt(x, 43).if_set_return(1);
   return static_cast<char>(x + offset);
}

consteval word base58_conversion_radix() {
   if constexpr(sizeof(word) == 8) {
      // 58^10 largest that fits into a 64 bit word
      return 430804206899405824U;
   } else {
      // 58^5 largest that fits into a 32 bit word
      return 656356768U;
   }
}

consteval size_t base58_conversion_radix_digits() {
   if constexpr(sizeof(word) == 8) {
      return 10;
   } else {
      return 5;
   }
}

constexpr std::pair<uint8_t, word> divmod_58(word x) {
   BOTAN_DEBUG_ASSERT(x < base58_conversion_radix());

   word q = 0;

   // Division by constant 58
   //
   // Compilers will *usually* convert an expression like `x / 58` into
   // exactly this kind of operation, but not necessarily always...
   if constexpr(sizeof(word) == 4) {
      const uint64_t magic = 2369637129;  // ceil(2**36 / 29)
      uint64_t z = magic * x;
      q = z >> 37;
   } else {
      const uint64_t magic = 5088756985850910791;  // ceil(2**67 / 29)
      uint64_t lo = 0;                             // unused
      uint64_t hi = 0;
      mul64x64_128(magic, x >> 1, &lo, &hi);
      q = static_cast<word>(hi >> 3);
   }

   const uint8_t r = static_cast<uint8_t>(x - q * 58);
   return std::make_pair(r, q);
}

std::string base58_encode(BigInt v, size_t leading_zeros) {
   constexpr word radix = base58_conversion_radix();
   constexpr size_t radix_digits = base58_conversion_radix_digits();

   BigInt q;
   std::vector<uint8_t> digits;

   while(v.is_nonzero()) {
      word r = 0;
      ct_divide_word(v, radix, q, r);

      for(size_t i = 0; i != radix_digits; ++i) {
         const auto [r58, q58] = divmod_58(r);
         digits.push_back(r58);
         r = q58;
      }
      v.swap(q);
   }

   // remove leading zeros
   while(!digits.empty() && digits.back() == 0) {
      digits.pop_back();
   }

   std::string result;

   for(uint8_t d : digits) {
      result.push_back(lookup_base58_char(d));
   }

   for(size_t i = 0; i != leading_zeros; ++i) {
      result.push_back('1');  // 'zero' byte
   }

   return std::string(result.rbegin(), result.rend());
}

template <typename T, typename Z>
size_t count_leading_zeros(const T input[], size_t input_length, Z zero) {
   size_t leading_zeros = 0;

   while(leading_zeros < input_length && input[leading_zeros] == zero) {
      leading_zeros += 1;
   }

   return leading_zeros;
}

uint8_t base58_value_of(char input) {
   // "123456789 ABCDEFGH JKLMN PQRSTUVWXYZ abcdefghijk mnopqrstuvwxyz"

   const uint8_t c = static_cast<uint8_t>(input);

   const auto is_dec_19 = CT::Mask<uint8_t>::is_within_range(c, uint8_t('1'), uint8_t('9'));
   const auto is_alpha_AH = CT::Mask<uint8_t>::is_within_range(c, uint8_t('A'), uint8_t('H'));
   const auto is_alpha_JN = CT::Mask<uint8_t>::is_within_range(c, uint8_t('J'), uint8_t('N'));
   const auto is_alpha_PZ = CT::Mask<uint8_t>::is_within_range(c, uint8_t('P'), uint8_t('Z'));

   const auto is_alpha_ak = CT::Mask<uint8_t>::is_within_range(c, uint8_t('a'), uint8_t('k'));
   const auto is_alpha_mz = CT::Mask<uint8_t>::is_within_range(c, uint8_t('m'), uint8_t('z'));

   const uint8_t c_dec_19 = c - uint8_t('1');
   const uint8_t c_AH = c - uint8_t('A') + 9;
   const uint8_t c_JN = c - uint8_t('J') + 17;
   const uint8_t c_PZ = c - uint8_t('P') + 22;

   const uint8_t c_ak = c - uint8_t('a') + 33;
   const uint8_t c_mz = c - uint8_t('m') + 44;

   uint8_t ret = 0xFF;  // default value

   ret = is_dec_19.select(c_dec_19, ret);
   ret = is_alpha_AH.select(c_AH, ret);
   ret = is_alpha_JN.select(c_JN, ret);
   ret = is_alpha_PZ.select(c_PZ, ret);
   ret = is_alpha_ak.select(c_ak, ret);
   ret = is_alpha_mz.select(c_mz, ret);
   return ret;
}

}  // namespace

std::string base58_encode(const uint8_t input[], size_t input_length) {
   BigInt v(input, input_length);
   return base58_encode(v, count_leading_zeros(input, input_length, 0));
}

std::string base58_check_encode(const uint8_t input[], size_t input_length) {
   BigInt v(input, input_length);
   v <<= 32;
   v += sha256_d_checksum(input, input_length);
   return base58_encode(v, count_leading_zeros(input, input_length, 0));
}

std::vector<uint8_t> base58_decode(const char input[], size_t input_length) {
   const size_t leading_zeros = count_leading_zeros(input, input_length, '1');

   std::vector<uint8_t> digits;

   for(size_t i = leading_zeros; i != input_length; ++i) {
      const char c = input[i];

      if(c == ' ' || c == '\n') {
         continue;
      }

      const uint8_t idx = base58_value_of(c);

      if(idx == 0xFF) {
         throw Decoding_Error("Invalid base58");
      }

      digits.push_back(idx);
   }

   BigInt v;

   constexpr word radix1 = 58;
   constexpr word radix2 = 58 * 58;
   constexpr word radix3 = 58 * 58 * 58;
   constexpr word radix4 = 58 * 58 * 58 * 58;

   std::span<uint8_t> remaining{digits};

   while(remaining.size() >= 4) {
      const word accum = radix3 * remaining[0] + radix2 * remaining[1] + radix1 * remaining[2] + remaining[3];
      v *= radix4;
      v += accum;
      remaining = remaining.subspan(4);
   }

   while(!remaining.empty()) {
      v *= 58;
      v += remaining[0];
      remaining = remaining.subspan(1);
   }

   return v.serialize(v.bytes() + leading_zeros);
}

std::vector<uint8_t> base58_check_decode(const char input[], size_t input_length) {
   std::vector<uint8_t> dec = base58_decode(input, input_length);

   if(dec.size() < 4) {
      throw Decoding_Error("Invalid base58 too short for checksum");
   }

   const uint32_t computed_checksum = sha256_d_checksum(dec.data(), dec.size() - 4);
   const uint32_t checksum = load_be<uint32_t>(&dec[dec.size() - 4], 0);

   if(checksum != computed_checksum) {
      throw Decoding_Error("Invalid base58 checksum");
   }

   dec.resize(dec.size() - 4);

   return dec;
}

}  // namespace Botan

1	/*
2	* (C) 2018,2020 Jack Lloyd
3	*
4	* Botan is released under the Simplified BSD License (see license.txt)
5	*/
6
7	#include <botan/base58.h>
8
9	#include <botan/bigint.h>
10	#include <botan/exceptn.h>
11	#include <botan/hash.h>
12	#include <botan/internal/ct_utils.h>
13	#include <botan/internal/divide.h>
14	#include <botan/internal/loadstor.h>
15	#include <botan/internal/mul128.h>
16
17	namespace Botan {
18
19	namespace {
20
21	uint32_t sha256_d_checksum(const uint8_t input[], size_t input_length) {	16✔
22	auto sha256 = HashFunction::create_or_throw("SHA-256");	16✔
23
24	std::vector<uint8_t> checksum(32);	16✔
25
26	sha256->update(input, input_length);	16✔
27	sha256->final(checksum);	16✔
28
29	sha256->update(checksum);	16✔
30	sha256->final(checksum);	16✔
31
32	return load_be<uint32_t>(checksum.data(), 0);	16✔
33	}	32✔
34
35	char lookup_base58_char(uint8_t x) {	333✔
36	// "123456789 ABCDEFGH JKLMN PQRSTUVWXYZ abcdefghijk mnopqrstuvwxyz"
37	BOTAN_DEBUG_ASSERT(x < 58);	333✔
38
39	// This works by computing offset(x) such that x + offset(x) is equal to the
40	// desired character
41
42	size_t offset = 49;	333✔
43
44	offset += CT::Mask<uint8_t>::is_gt(x, 8).if_set_return(7);	333✔
45	offset += CT::Mask<uint8_t>::is_gt(x, 16).if_set_return(1);	333✔
46	offset += CT::Mask<uint8_t>::is_gt(x, 21).if_set_return(1);	333✔
47	offset += CT::Mask<uint8_t>::is_gt(x, 32).if_set_return(6);	333✔
48	offset += CT::Mask<uint8_t>::is_gt(x, 43).if_set_return(1);	333✔
49	return static_cast<char>(x + offset);	333✔
50	}
51
52	consteval word base58_conversion_radix() {
53	if constexpr(sizeof(word) == 8) {
54	// 58^10 largest that fits into a 64 bit word
55	return 430804206899405824U;
56	} else {
57	// 58^5 largest that fits into a 32 bit word
58	return 656356768U;
59	}
60	}
61
62	consteval size_t base58_conversion_radix_digits() {
63	if constexpr(sizeof(word) == 8) {
64	return 10;
65	} else {
66	return 5;
67	}
68	}
69
70	constexpr std::pair<uint8_t, word> divmod_58(word x) {	490✔
71	BOTAN_DEBUG_ASSERT(x < base58_conversion_radix());	490✔
72
73	word q = 0;	490✔
74
75	// Division by constant 58
76	//
77	// Compilers will usually convert an expression like `x / 58` into
78	// exactly this kind of operation, but not necessarily always...
79	if constexpr(sizeof(word) == 4) {	490✔
80	const uint64_t magic = 2369637129; // ceil(2**36 / 29)
81	uint64_t z = magic * x;
82	q = z >> 37;
83	} else {
84	const uint64_t magic = 5088756985850910791; // ceil(2**67 / 29)	490✔
85	uint64_t lo = 0; // unused	490✔
86	uint64_t hi = 0;	490✔
87	mul64x64_128(magic, x >> 1, &lo, &hi);	490✔
88	q = static_cast<word>(hi >> 3);	490✔
89	}
90
91	const uint8_t r = static_cast<uint8_t>(x - q * 58);	490✔
92	return std::make_pair(r, q);	490✔
93	}
94
95	std::string base58_encode(BigInt v, size_t leading_zeros) {	26✔
96	constexpr word radix = base58_conversion_radix();	26✔
97	constexpr size_t radix_digits = base58_conversion_radix_digits();	26✔
98
99	BigInt q;	26✔
100	std::vector<uint8_t> digits;	26✔
101
102	while(v.is_nonzero()) {	150✔
103	word r = 0;	49✔
104	ct_divide_word(v, radix, q, r);	49✔
105
106	for(size_t i = 0; i != radix_digits; ++i) {	539✔
107	const auto [r58, q58] = divmod_58(r);	490✔
108	digits.push_back(r58);	490✔
109	r = q58;	490✔
110	}
111	v.swap(q);	49✔
112	}
113
114	// remove leading zeros
115	while(!digits.empty() && digits.back() == 0) {	183✔
116	digits.pop_back();	157✔
117	}
118
119	std::string result;	26✔
120
121	for(uint8_t d : digits) {	359✔
122	result.push_back(lookup_base58_char(d));	333✔
123	}
124
125	for(size_t i = 0; i != leading_zeros; ++i) {	38✔
126	result.push_back('1'); // 'zero' byte	12✔
127	}
128
129	return std::string(result.rbegin(), result.rend());	52✔
130	}	51✔
131
132	template <typename T, typename Z>
133	size_t count_leading_zeros(const T input[], size_t input_length, Z zero) {	45✔
134	size_t leading_zeros = 0;	45✔
135
136	while(leading_zeros < input_length && input[leading_zeros] == zero) {	88✔
137	leading_zeros += 1;	24✔
138	}
139
140	return leading_zeros;
141	}
142
143	uint8_t base58_value_of(char input) {	336✔
144	// "123456789 ABCDEFGH JKLMN PQRSTUVWXYZ abcdefghijk mnopqrstuvwxyz"
145
146	const uint8_t c = static_cast<uint8_t>(input);	336✔
147
148	const auto is_dec_19 = CT::Mask<uint8_t>::is_within_range(c, uint8_t('1'), uint8_t('9'));	336✔
149	const auto is_alpha_AH = CT::Mask<uint8_t>::is_within_range(c, uint8_t('A'), uint8_t('H'));	336✔
150	const auto is_alpha_JN = CT::Mask<uint8_t>::is_within_range(c, uint8_t('J'), uint8_t('N'));	336✔
151	const auto is_alpha_PZ = CT::Mask<uint8_t>::is_within_range(c, uint8_t('P'), uint8_t('Z'));	336✔
152
153	const auto is_alpha_ak = CT::Mask<uint8_t>::is_within_range(c, uint8_t('a'), uint8_t('k'));	336✔
154	const auto is_alpha_mz = CT::Mask<uint8_t>::is_within_range(c, uint8_t('m'), uint8_t('z'));	336✔
155
156	const uint8_t c_dec_19 = c - uint8_t('1');	336✔
157	const uint8_t c_AH = c - uint8_t('A') + 9;	336✔
158	const uint8_t c_JN = c - uint8_t('J') + 17;	336✔
159	const uint8_t c_PZ = c - uint8_t('P') + 22;	336✔
160
161	const uint8_t c_ak = c - uint8_t('a') + 33;	336✔
162	const uint8_t c_mz = c - uint8_t('m') + 44;	336✔
163
164	uint8_t ret = 0xFF; // default value	336✔
165
166	ret = is_dec_19.select(c_dec_19, ret);	336✔
167	ret = is_alpha_AH.select(c_AH, ret);	336✔
168	ret = is_alpha_JN.select(c_JN, ret);	336✔
169	ret = is_alpha_PZ.select(c_PZ, ret);	336✔
170	ret = is_alpha_ak.select(c_ak, ret);	336✔
171	ret = is_alpha_mz.select(c_mz, ret);	336✔
172	return ret;	336✔
173	}
174
175	} // namespace
176
177	std::string base58_encode(const uint8_t input[], size_t input_length) {	19✔
178	BigInt v(input, input_length);	19✔
179	return base58_encode(v, count_leading_zeros(input, input_length, 0));	38✔
180	}	19✔
181
182	std::string base58_check_encode(const uint8_t input[], size_t input_length) {	7✔
183	BigInt v(input, input_length);	7✔
184	v <<= 32;	7✔
185	v += sha256_d_checksum(input, input_length);	7✔
186	return base58_encode(v, count_leading_zeros(input, input_length, 0));	21✔
187	}	7✔
188
189	std::vector<uint8_t> base58_decode(const char input[], size_t input_length) {	38✔
190	const size_t leading_zeros = count_leading_zeros(input, input_length, '1');	38✔
191
192	std::vector<uint8_t> digits;	38✔
193
194	for(size_t i = leading_zeros; i != input_length; ++i) {	363✔
195	const char c = input[i];	336✔
196
197	if(c == ' ' \|\| c == '\n') {	336✔
198	continue;	×
199	}
200
201	const uint8_t idx = base58_value_of(c);	336✔
202
203	if(idx == 0xFF) {	336✔
204	throw Decoding_Error("Invalid base58");	11✔
205	}
206
207	digits.push_back(idx);	325✔
208	}
209
210	BigInt v;	27✔
211
212	constexpr word radix1 = 58;	27✔
213	constexpr word radix2 = 58 * 58;	27✔
214	constexpr word radix3 = 58 * 58 * 58;	27✔
215	constexpr word radix4 = 58 * 58 * 58 * 58;	27✔
216
217	std::span<uint8_t> remaining{digits};	27✔
218
219	while(remaining.size() >= 4) {	91✔
220	const word accum = radix3 * remaining[0] + radix2 * remaining[1] + radix1 * remaining[2] + remaining[3];	64✔
221	v *= radix4;	64✔
222	v += accum;	64✔
223	remaining = remaining.subspan(4);	64✔
224	}
225
226	while(!remaining.empty()) {	61✔
227	v *= 58;	34✔
228	v += remaining[0];	34✔
229	remaining = remaining.subspan(1);	34✔
230	}
231
232	return v.serialize(v.bytes() + leading_zeros);	27✔
233	}	53✔
234
235	std::vector<uint8_t> base58_check_decode(const char input[], size_t input_length) {	10✔
236	std::vector<uint8_t> dec = base58_decode(input, input_length);	10✔
237
238	if(dec.size() < 4) {	10✔
239	throw Decoding_Error("Invalid base58 too short for checksum");	1✔
240	}
241
242	const uint32_t computed_checksum = sha256_d_checksum(dec.data(), dec.size() - 4);	9✔
243	const uint32_t checksum = load_be<uint32_t>(&dec[dec.size() - 4], 0);	9✔
244
245	if(checksum != computed_checksum) {	9✔
246	throw Decoding_Error("Invalid base58 checksum");	4✔
247	}
248
249	dec.resize(dec.size() - 4);	5✔
250
251	return dec;	5✔
252	}	5✔
253
254	} // namespace Botan

randombit / botan / 16818395385

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous