23046865986

Committed 13 Mar 2026 10:32AM UTC coverage: 91.936% (+1.7%) from 90.206%

Build # 23046865986

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #5437 from randombit/jack/base58-swar

Use SWAR during base58 decoding

Run Details

106147 of 115457 relevant lines covered (91.94%)

11189778.79 hits per line

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

99.12

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

/*
* (C) 2018,2020,2026 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/int_utils.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)
      const 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(const 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) {
   /*
   * Alphabet: "123456789 ABCDEFGH JKLMN PQRSTUVWXYZ abcdefghijk mnopqrstuvwxyz"
   *
   * Valid input ranges are:
   *
   * '1'-'9' (length 9)
   * 'A'-'H' (length 8)
   * 'J'-'N' (length 5)
   * 'P'-'Z' (length 11)
   * 'a'-'k' (length 11)
   * 'm'-'z' (length 14)
   */
   constexpr uint64_t v_lo = make_uint64(0, '1', 'A', 'J', 'P', 'a', 'm', 0);
   constexpr uint64_t v_range = make_uint64(0, 9, 8, 5, 11, 11, 14, 0);

   const uint8_t x = static_cast<uint8_t>(input);
   const uint64_t x8 = x * 0x0101010101010101;  // replicate x to each byte

   // is x8 in any of the ranges?
   const uint64_t v_mask = swar_in_range<uint64_t>(x8, v_lo, v_range) ^ 0x8000000000000000;

   /*
   * Offsets mapping from the character code x to the base58 value of x in each range
   *
   * For example '2' (50) + 0xCF == 1
   *
   * Fallback byte 7 is set to 0xFF - x so that if used it results in 0xFF to indicate invalid.
   */
   constexpr uint64_t val_v_const = make_uint64(0, 0xCF, 0xC8, 0xC7, 0xC6, 0xC0, 0xBF, 0);
   const uint64_t val_v = val_v_const ^ (static_cast<uint64_t>(0xFF - x) << 56);

   return x + static_cast<uint8_t>(val_v >> (8 * index_of_first_set_byte(v_mask)));
}

}  // namespace

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

randombit / botan / 23046865986

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