7#include <botan/base58.h>
9#include <botan/exceptn.h>
10#include <botan/hash.h>
11#include <botan/mem_ops.h>
12#include <botan/secmem.h>
13#include <botan/internal/ct_utils.h>
14#include <botan/internal/int_utils.h>
15#include <botan/internal/loadstor.h>
16#include <botan/internal/mem_utils.h>
17#include <botan/internal/mp_core.h>
26uint32_t sha256_d_checksum(
const uint8_t input[],
size_t input_length) {
29 std::vector<uint8_t> checksum(32);
31 sha256->update(input, input_length);
32 sha256->final(checksum);
34 sha256->update(checksum);
35 sha256->final(checksum);
40char lookup_base58_char(uint8_t x) {
54 return static_cast<char>(x + offset);
57consteval word base58_conversion_radix() {
58 if constexpr(
sizeof(
word) == 8) {
60 return 430804206899405824U;
67consteval size_t base58_conversion_radix_digits() {
68 if constexpr(
sizeof(
word) == 8) {
79word ct_divmod_base58radix(std::span<word> x) {
84 for(
size_t i = x.size(); i > 0; --i) {
85 const auto [q, r] = radix58_div.divmod_2to1_ct(rem, x[i - 1]);
94void ct_mul_add_word(std::span<word> v,
word mul,
word add) {
107size_t ct_count_leading_eq(std::span<const uint8_t> input, uint8_t c) {
108 constexpr uint64_t lo1 = 0x0101010101010101;
109 constexpr uint64_t hi1 = lo1 << 7;
110 constexpr uint64_t lo7 = ~hi1;
115 while(input.size() >= 8) {
118 const uint64_t z = ~(((x & lo7) + lo7) | x) & hi1;
120 uint64_t p = z & ((z << 8) | 0x80);
121 p &= (p << 16) | 0x8080;
122 p &= (p << 32) | 0x80808080;
124 const uint64_t n = ((p >> 7) * lo1) >> 56;
125 count +=
static_cast<size_t>(all_eq.if_set_return(n));
127 input = input.subspan(8);
130 for(
const uint8_t b : input) {
132 count +=
static_cast<size_t>(all_eq.if_set_return(1));
138size_t ct_count_trailing_zeros(std::span<const uint8_t> input) {
142 for(
size_t i = input.size(); i > 0; --i) {
144 count += all_zero.if_set_return(1);
154 for(
size_t i = 0; i != input.size(); ++i) {
155 const uint8_t b = input[input.size() - 1 - i];
156 v[i /
sizeof(
word)] |=
static_cast<word>(b) << (8 * (i %
sizeof(
word)));
162std::string
base58_encode(std::span<word> v,
size_t leading_zeros) {
163 constexpr size_t radix_digits = base58_conversion_radix_digits();
167 constexpr size_t radix_bits = std::bit_width(base58_conversion_radix()) - 1;
171 digits.reserve(chunks * radix_digits);
175 for(
size_t c = 0; c != chunks; ++c) {
176 word r = ct_divmod_base58radix(v);
178 for(
size_t i = 0; i != radix_digits; ++i) {
179 const auto [q58, r58] = div_58.divmod_2to1_ct(0, r);
180 digits.push_back(
static_cast<uint8_t
>(r58));
186 std::string result(leading_zeros + digits.size(),
'1');
188 for(
size_t i = 0; i != digits.size(); ++i) {
189 result[result.size() - 1 - i] = lookup_base58_char(digits[i]);
193 const size_t zero_digits = ct_count_trailing_zeros(digits);
196 result.erase(0, zero_digits);
200uint8_t base58_value_of(
char input) {
213 constexpr uint64_t v_lo =
make_uint64(0,
'1',
'A',
'J',
'P',
'a',
'm', 0);
214 constexpr uint64_t v_range =
make_uint64(0, 9, 8, 5, 11, 11, 14, 0);
216 constexpr uint64_t expand8 = 0x0101010101010101;
218 const uint8_t x =
static_cast<uint8_t
>(input);
219 const uint64_t x8 = x * expand8;
231 constexpr uint64_t val_v_const =
make_uint64(0, 0xCF, 0xC8, 0xC7, 0xC6, 0xC0, 0xBF, 0);
232 const uint64_t val_v = val_v_const ^ (
static_cast<uint64_t
>(0xFF - x) << 56);
243std::optional<uint64_t> base58_values_of_8(uint64_t w) {
244 constexpr uint64_t lo1 = 0x0101010101010101;
245 constexpr uint64_t hi1 = 0x8080808080808080;
248 const uint64_t w80 = w | hi1;
249 const auto gt = [w80](
char c) {
return (w80 - lo1 *
static_cast<uint8_t
>(c + 1)) & hi1; };
259 const uint64_t gt_0 = gt(
'0');
260 const uint64_t gt_9 = gt(
'9');
261 const uint64_t gt_at = gt(
'@');
262 const uint64_t gt_H = gt(
'H');
263 const uint64_t gt_I = gt(
'I');
264 const uint64_t gt_N = gt(
'N');
265 const uint64_t gt_O = gt(
'O');
266 const uint64_t gt_Z = gt(
'Z');
267 const uint64_t gt_bt = gt(
'`');
268 const uint64_t gt_k = gt(
'k');
269 const uint64_t gt_l = gt(
'l');
270 const uint64_t gt_z = gt(
'z');
273 const uint64_t in_gap = (gt_9 & ~gt_at) | (gt_H & ~gt_I) | (gt_N & ~gt_O) | (gt_Z & ~gt_bt) | (gt_k & ~gt_l);
274 const uint64_t invalid = (w & hi1) | (~gt_0 & hi1) | gt_z | in_gap;
282 const uint64_t offsets = lo1 * 49 + 7 * (gt_at >> 7) + (gt_I >> 7) + (gt_O >> 7) + 6 * (gt_Z >> 7) + (gt_l >> 7);
289 const auto in = std::span{input, input_length};
292 const size_t leading_zeros = ct_count_leading_eq(in, 0);
295 auto v = to_le_words(in);
300 const auto in = std::span{input, input_length};
303 const size_t leading_zeros = ct_count_leading_eq(in, 0);
307 copy_mem(buf.data(), input, input_length);
308 store_be(sha256_d_checksum(input, input_length), buf.data() + input_length);
310 auto v = to_le_words(buf);
314std::vector<uint8_t>
base58_decode(
const char input[],
size_t input_length) {
317 const size_t leading_zeros = ct_count_leading_eq(in,
static_cast<uint8_t
>(
'1'));
320 size_t digit_count = 0;
322 auto chars = in.subspan(leading_zeros);
324 while(!chars.empty()) {
325 if(chars.size() >= 8) {
327 store_le(std::span{digits}.subspan(digit_count).first<8>(), *values);
329 chars = chars.subspan(8);
335 const size_t n = std::min<size_t>(chars.size(), 8);
336 for(
size_t i = 0; i != n; ++i) {
337 const char c =
static_cast<char>(chars[i]);
339 if(c ==
' ' || c ==
'\n') {
343 const uint8_t idx = base58_value_of(c);
349 digits[digit_count++] = idx;
351 chars = chars.subspan(n);
354 digits.resize(digit_count);
359 constexpr size_t radix_digits = base58_conversion_radix_digits();
366 const auto accum_digits = [](std::span<const uint8_t> chunk) {
369 for(
const uint8_t d : chunk) {
370 accum = accum * 58 + d;
375 std::span<const uint8_t> remaining{digits};
379 if(
const size_t partial = remaining.size() % radix_digits; partial > 0) {
380 v[0] = accum_digits(remaining.first(partial));
381 remaining = remaining.subspan(partial);
384 while(!remaining.empty()) {
385 ct_mul_add_word(v, base58_conversion_radix(), accum_digits(remaining.first(radix_digits)));
386 remaining = remaining.subspan(radix_digits);
390 for(
size_t i = 0; i != v.size(); ++i) {
391 store_be(v[v.size() - 1 - i], vbytes.data() + i *
sizeof(
word));
394 const size_t sig_bytes = vbytes.size() - ct_count_leading_eq(vbytes, 0);
397 std::vector<uint8_t> output(leading_zeros + sig_bytes);
398 copy_mem(output.data() + leading_zeros, vbytes.data() + vbytes.size() - sig_bytes, sig_bytes);
404 std::vector<uint8_t> dec =
base58_decode(input, input_length);
410 const uint32_t computed_checksum = sha256_d_checksum(dec.data(), dec.size() - 4);
413 if(checksum != computed_checksum) {
417 dec.resize(dec.size() - 4);
#define BOTAN_DEBUG_ASSERT(expr)
static constexpr Mask< T > set()
static constexpr Mask< T > is_equal(T x, T y)
static constexpr Mask< T > is_gt(T x, T y)
static constexpr Mask< T > is_zero(T x)
static std::unique_ptr< HashFunction > create_or_throw(std::string_view algo_spec, std::string_view provider="")
static constexpr divide_precomp setup(W divisor)
constexpr auto scoped_poison(const Ts &... xs)
constexpr void unpoison(const T *p, size_t n)
std::span< const uint8_t > as_span_of_bytes(const char *s, size_t len)
constexpr uint64_t make_uint64(uint8_t i0, uint8_t i1, uint8_t i2, uint8_t i3, uint8_t i4, uint8_t i5, uint8_t i6, uint8_t i7)
std::vector< uint8_t > base58_check_decode(const char input[], size_t input_length)
constexpr T swar_in_range(T v, T lower, T upper)
constexpr auto word_madd2(W a, W b, W *c) -> W
std::string base58_encode(const uint8_t input[], size_t input_length)
constexpr size_t index_of_first_set_byte(T v)
constexpr void copy_mem(T *out, const T *in, size_t n)
constexpr auto store_le(ParamTs &&... params)
std::string base58_check_encode(const uint8_t input[], size_t input_length)
std::vector< uint8_t > base58_decode(const char input[], size_t input_length)
constexpr auto load_le(ParamTs &&... params)
std::vector< T, secure_allocator< T > > secure_vector
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.
constexpr auto store_be(ParamTs &&... params)
constexpr auto load_be(ParamTs &&... params)