xrpld
Loading...
Searching...
No Matches
base58.cpp
1#include <xrpl/protocol/detail/token_errors.h>
2
3#include <boost/multiprecision/cpp_int.hpp> // IWYU pragma: keep
4
5#include <gtest/gtest.h>
6
7#include <algorithm>
8#include <cassert>
9#include <cstdint>
10#include <cstring>
11#include <iomanip>
12#include <iostream>
13#include <limits>
14#include <ranges>
15#include <stdexcept>
16#include <string>
17#include <tuple>
18#include <vector>
19#ifndef _MSC_VER
20
21#include <xrpl/protocol/detail/b58_utils.h>
22#include <xrpl/protocol/tokens.h>
23
24#include <array>
25#include <cstddef>
26#include <random>
27#include <span>
28#include <sstream>
29
30namespace xrpl::test {
31namespace {
32
33[[nodiscard]] inline auto
34randEngine() -> std::mt19937&
35{
36 static std::mt19937 kR = [] {
37 std::random_device rd;
38 return std::mt19937{rd()};
39 }();
40 return kR;
41}
42
43constexpr int kNumTokenTypeIndexes = 9;
44
45[[nodiscard]] inline auto
46tokenTypeAndSize(int i) -> std::tuple<xrpl::TokenType, std::size_t>
47{
48 assert(i < kNumTokenTypeIndexes);
49
50 switch (i)
51 {
52 using enum xrpl::TokenType;
53 case 0:
54 return {None, 20};
55 case 1:
56 return {NodePublic, 32};
57 case 2:
58 return {NodePublic, 33};
59 case 3:
60 return {NodePrivate, 32};
61 case 4:
62 return {AccountID, 20};
63 case 5:
64 return {AccountPublic, 32};
65 case 6:
66 return {AccountPublic, 33};
67 case 7:
68 return {AccountSecret, 32};
69 case 8:
70 return {FamilySeed, 16};
71 default:
72 throw std::invalid_argument(
73 "Invalid token selection passed to tokenTypeAndSize() "
74 "in " __FILE__);
75 }
76}
77
78[[nodiscard]] inline auto
79randomTokenTypeAndSize() -> std::tuple<xrpl::TokenType, std::size_t>
80{
81 using namespace xrpl;
82 auto& rng = randEngine();
83 std::uniform_int_distribution<> d(0, 8);
84 return tokenTypeAndSize(d(rng));
85}
86
87// Return the token type and subspan of `d` to use as test data.
88[[nodiscard]] inline auto
89randomB256TestData(std::span<std::uint8_t> d)
90 -> std::tuple<xrpl::TokenType, std::span<std::uint8_t>>
91{
92 auto& rng = randEngine();
93 std::uniform_int_distribution<std::uint8_t> dist(0, 255);
94 auto [tokType, tokSize] = randomTokenTypeAndSize();
95 std::generate(d.begin(), d.begin() + tokSize, [&] { return dist(rng); });
96 return {tokType, d.subspan(0, tokSize)};
97}
98
99inline void
100printAsChar(std::span<std::uint8_t> a, std::span<std::uint8_t> b)
101{
102 auto const asString = [](std::span<std::uint8_t> s) {
103 std::string r;
104 r.resize(s.size());
105 std::ranges::copy(s, r.begin());
106 return r;
107 };
108 auto const sa = asString(a);
109 auto const sb = asString(b);
110 std::cerr << "\n\n" << sa << "\n" << sb << "\n";
111}
112
113inline void
114printAsInt(std::span<std::uint8_t> a, std::span<std::uint8_t> b)
115{
116 auto const asString = [](std::span<std::uint8_t> s) -> std::string {
117 std::stringstream sstr;
118 for (auto const i : s)
119 {
120 sstr << std::setw(3) << int(i) << ',';
121 }
122 return sstr.str();
123 };
124 auto const sa = asString(a);
125 auto const sb = asString(b);
126 std::cerr << "\n\n" << sa << "\n" << sb << "\n";
127}
128
129} // namespace
130
131namespace multiprecision_utils {
132
133[[nodiscard]] boost::multiprecision::checked_uint512_t
134toBoostMP(std::span<std::uint64_t> in)
135{
136 boost::multiprecision::checked_uint512_t mbp = 0;
137 for (auto const& i : std::views::reverse(in))
138 {
139 mbp <<= 64;
140 mbp += i;
141 }
142 return mbp;
143}
144
145[[nodiscard]] std::vector<std::uint64_t>
146randomBigInt(std::uint8_t minSize = 1, std::uint8_t maxSize = 5)
147{
148 auto& eng = randEngine();
149 std::uniform_int_distribution<std::uint8_t> numCoeffDist(minSize, maxSize);
150 std::uniform_int_distribution<std::uint64_t> dist;
151 auto const numCoeff = numCoeffDist(eng);
152 std::vector<std::uint64_t> coeffs;
153 coeffs.reserve(numCoeff);
154 for (auto i = 0uz; i < numCoeff; ++i)
155 {
156 coeffs.push_back(dist(eng));
157 }
158 return coeffs;
159}
160} // namespace multiprecision_utils
161
162struct Base58MultiprecisionTest : public ::testing::Test
163{
164 static constexpr std::size_t kIters = 100000;
165
166 std::mt19937& eng = randEngine();
167 std::uniform_int_distribution<std::uint64_t> dist;
168 std::uniform_int_distribution<std::uint64_t> dist1{1};
169};
170
171TEST_F(Base58MultiprecisionTest, div_rem_matches_boost)
172{
173 using namespace boost::multiprecision;
174
175 for (auto i = 0uz; i < kIters; ++i)
176 {
177 std::uint64_t const d = dist(eng);
178 if (d == 0u)
179 continue;
180 auto bigInt = multiprecision_utils::randomBigInt();
181 auto const boostBigInt =
182 multiprecision_utils::toBoostMP(std::span<std::uint64_t>(bigInt.data(), bigInt.size()));
183
184 auto const refDiv = boostBigInt / d;
185 auto const refMod = boostBigInt % d;
186
187 auto const mod = b58_fast::detail::inplaceBigintDivRem(
188 std::span<uint64_t>(bigInt.data(), bigInt.size()), d);
189 auto const foundDiv = multiprecision_utils::toBoostMP(bigInt);
190 EXPECT_EQ(refMod.convert_to<std::uint64_t>(), mod);
191 EXPECT_EQ(foundDiv, refDiv);
192 }
193}
194
195TEST_F(Base58MultiprecisionTest, add_matches_boost)
196{
197 using namespace boost::multiprecision;
198
199 for (auto i = 0uz; i < kIters; ++i)
200 {
201 std::uint64_t const d = dist(eng);
202 auto bigInt = multiprecision_utils::randomBigInt(/*minSize*/ 2);
203 if (bigInt[bigInt.size() - 1] == std::numeric_limits<std::uint64_t>::max())
204 {
205 bigInt[bigInt.size() - 1] -= 1; // Prevent overflow
206 }
207 auto const boostBigInt =
208 multiprecision_utils::toBoostMP(std::span<std::uint64_t>(bigInt.data(), bigInt.size()));
209
210 auto const refAdd = boostBigInt + d;
211
212 auto const result = b58_fast::detail::inplaceBigintAdd(
213 std::span<uint64_t>(bigInt.data(), bigInt.size()), d);
214 EXPECT_EQ(result, TokenCodecErrc::Success);
215 auto const foundAdd = multiprecision_utils::toBoostMP(bigInt);
216 EXPECT_EQ(refAdd, foundAdd);
217 }
218}
219
220TEST_F(Base58MultiprecisionTest, add_reports_overflow)
221{
222 using namespace boost::multiprecision;
223
224 for (auto i = 0uz; i < kIters; ++i)
225 {
226 std::uint64_t const d = dist1(eng);
227 // Force overflow
228 std::vector<std::uint64_t> bigInt(5, std::numeric_limits<std::uint64_t>::max());
229
230 auto const boostBigInt =
231 multiprecision_utils::toBoostMP(std::span<std::uint64_t>(bigInt.data(), bigInt.size()));
232
233 auto const refAdd = boostBigInt + d;
234
235 auto const result = b58_fast::detail::inplaceBigintAdd(
236 std::span<uint64_t>(bigInt.data(), bigInt.size()), d);
237 EXPECT_EQ(result, TokenCodecErrc::OverflowAdd);
238 auto const foundAdd = multiprecision_utils::toBoostMP(bigInt);
239 EXPECT_NE(refAdd, foundAdd);
240 }
241}
242
243TEST_F(Base58MultiprecisionTest, mul_matches_boost)
244{
245 using namespace boost::multiprecision;
246
247 for (auto i = 0uz; i < kIters; ++i)
248 {
249 std::uint64_t const d = dist(eng);
250 auto bigInt = multiprecision_utils::randomBigInt(/* minSize */ 2);
251 // inplace mul requires the most significant coeff to be zero to
252 // hold the result.
253 bigInt[bigInt.size() - 1] = 0;
254 auto const boostBigInt =
255 multiprecision_utils::toBoostMP(std::span<std::uint64_t>(bigInt.data(), bigInt.size()));
256
257 auto const refMul = boostBigInt * d;
258
259 auto const result = b58_fast::detail::inplaceBigintMul(
260 std::span<uint64_t>(bigInt.data(), bigInt.size()), d);
261 EXPECT_EQ(result, TokenCodecErrc::Success);
262 auto const foundMul = multiprecision_utils::toBoostMP(bigInt);
263 EXPECT_EQ(refMul, foundMul);
264 }
265}
266
267TEST_F(Base58MultiprecisionTest, mul_reports_input_too_large)
268{
269 using namespace boost::multiprecision;
270
271 for (auto i = 0uz; i < kIters; ++i)
272 {
273 std::uint64_t const d = dist1(eng);
274 // Force overflow
275 std::vector<std::uint64_t> bigInt(5, std::numeric_limits<std::uint64_t>::max());
276 auto const boostBigInt =
277 multiprecision_utils::toBoostMP(std::span<std::uint64_t>(bigInt.data(), bigInt.size()));
278
279 auto const refMul = boostBigInt * d;
280
281 auto const result = b58_fast::detail::inplaceBigintMul(
282 std::span<uint64_t>(bigInt.data(), bigInt.size()), d);
283 EXPECT_EQ(result, TokenCodecErrc::InputTooLarge);
284 auto const foundMul = multiprecision_utils::toBoostMP(bigInt);
285 EXPECT_NE(refMul, foundMul);
286 }
287}
288
289// b58_fast must agree with the reference implementation for both raw and
290// token-framed data, in each direction.
291struct Base58FastMatchesRefTest : public ::testing::Test
292{
293 static void
294 testRawEncode(std::span<std::uint8_t> b256Data)
295 {
296 std::array<std::uint8_t, 64> b58ResultBuf[2];
297 std::array<std::span<std::uint8_t>, 2> b58Result;
298
299 std::array<std::uint8_t, 64> b256ResultBuf[2];
300 std::array<std::span<std::uint8_t>, 2> b256Result;
301 for (auto i = 0uz; i < 2; ++i)
302 {
303 std::span const outBuf{b58ResultBuf[i]};
304 if (i == 0)
305 {
306 auto const r = xrpl::b58_fast::detail::b256ToB58Be(b256Data, outBuf);
307 EXPECT_TRUE(r);
308 b58Result[i] = r.value();
309 }
310 else
311 {
312 std::array<std::uint8_t, 128> tmpBuf{};
313 std::string const s = xrpl::b58_ref::detail::encodeBase58(
314 b256Data.data(), b256Data.size(), tmpBuf.data(), tmpBuf.size());
315 EXPECT_TRUE(s.size());
316 b58Result[i] = outBuf.subspan(0, s.size());
317 std::ranges::copy(s, b58Result[i].begin());
318 }
319 }
320 auto const rawB58SameSize = b58Result[0].size() == b58Result[1].size();
321 EXPECT_TRUE(rawB58SameSize);
322 if (rawB58SameSize)
323 {
324 auto const rawB58SameData =
325 memcmp(b58Result[0].data(), b58Result[1].data(), b58Result[0].size()) == 0;
326 EXPECT_TRUE(rawB58SameData);
327 if (!rawB58SameData)
328 {
329 printAsChar(b58Result[0], b58Result[1]);
330 }
331 }
332
333 for (auto i = 0uz; i < 2; ++i)
334 {
335 std::span const outBuf{b256ResultBuf[i].data(), b256ResultBuf[i].size()};
336 if (i == 0)
337 {
338 std::string const in(
339 b58Result[i].data(), b58Result[i].data() + b58Result[i].size());
340 auto const r = xrpl::b58_fast::detail::b58ToB256Be(in, outBuf);
341 EXPECT_TRUE(r);
342 b256Result[i] = r.value();
343 }
344 else
345 {
346 std::string const st(b58Result[i].begin(), b58Result[i].end());
347 std::string const s = xrpl::b58_ref::detail::decodeBase58(st);
348 EXPECT_TRUE(s.size());
349 b256Result[i] = outBuf.subspan(0, s.size());
350 std::ranges::copy(s, b256Result[i].begin());
351 }
352 }
353
354 auto const rawB256SameSize = b256Result[0].size() == b256Result[1].size();
355 EXPECT_TRUE(rawB256SameSize);
356 if (rawB256SameSize)
357 {
358 auto const rawB256SameData =
359 memcmp(b256Result[0].data(), b256Result[1].data(), b256Result[0].size()) == 0;
360 EXPECT_TRUE(rawB256SameData);
361 if (!rawB256SameData)
362 {
363 printAsInt(b256Result[0], b256Result[1]);
364 }
365 }
366 }
367
368 static void
369 testTokenEncode(xrpl::TokenType const tokType, std::span<std::uint8_t> b256Data)
370 {
371 std::array<std::uint8_t, 64> b58ResultBuf[2];
372 std::array<std::span<std::uint8_t>, 2> b58Result;
373
374 std::array<std::uint8_t, 64> b256ResultBuf[2];
375 std::array<std::span<std::uint8_t>, 2> b256Result;
376 for (auto i = 0uz; i < 2; ++i)
377 {
378 std::span const outBuf{b58ResultBuf[i].data(), b58ResultBuf[i].size()};
379 if (i == 0)
380 {
381 auto const r = xrpl::b58_fast::encodeBase58Token(tokType, b256Data, outBuf);
382 EXPECT_TRUE(r);
383 b58Result[i] = r.value();
384 }
385 else
386 {
387 std::string const s =
388 xrpl::b58_ref::encodeBase58Token(tokType, b256Data.data(), b256Data.size());
389 EXPECT_TRUE(s.size());
390 b58Result[i] = outBuf.subspan(0, s.size());
391 std::ranges::copy(s, b58Result[i].begin());
392 }
393 }
394 auto const tokenB58SameSize = b58Result[0].size() == b58Result[1].size();
395 EXPECT_TRUE(tokenB58SameSize);
396 if (tokenB58SameSize)
397 {
398 auto const tokenB58SameData =
399 memcmp(b58Result[0].data(), b58Result[1].data(), b58Result[0].size()) == 0;
400 EXPECT_TRUE(tokenB58SameData);
401 if (!tokenB58SameData)
402 {
403 printAsChar(b58Result[0], b58Result[1]);
404 }
405 }
406
407 for (auto i = 0uz; i < 2; ++i)
408 {
409 std::span const outBuf{b256ResultBuf[i].data(), b256ResultBuf[i].size()};
410 if (i == 0)
411 {
412 std::string const in(
413 b58Result[i].data(), b58Result[i].data() + b58Result[i].size());
414 auto const r = xrpl::b58_fast::decodeBase58Token(tokType, in, outBuf);
415 EXPECT_TRUE(r);
416 b256Result[i] = r.value();
417 }
418 else
419 {
420 std::string const st(b58Result[i].begin(), b58Result[i].end());
421 std::string const s = xrpl::b58_ref::decodeBase58Token(st, tokType);
422 EXPECT_TRUE(s.size());
423 b256Result[i] = outBuf.subspan(0, s.size());
424 std::ranges::copy(s, b256Result[i].begin());
425 }
426 }
427
428 auto const tokenB256SameSize = b256Result[0].size() == b256Result[1].size();
429 EXPECT_TRUE(tokenB256SameSize);
430 if (tokenB256SameSize)
431 {
432 auto const tokenB256SameData =
433 memcmp(b256Result[0].data(), b256Result[1].data(), b256Result[0].size()) == 0;
434 EXPECT_TRUE(tokenB256SameData);
435 if (!tokenB256SameData)
436 {
437 printAsInt(b256Result[0], b256Result[1]);
438 }
439 }
440 }
441
442 static void
443 testIt(xrpl::TokenType const tokType, std::span<std::uint8_t> b256Data)
444 {
445 testRawEncode(b256Data);
446 testTokenEncode(tokType, b256Data);
447 }
448};
449
450TEST_F(Base58FastMatchesRefTest, every_token_type_over_every_byte_value)
451{
452 // Data where every byte is the same, for byte values 0-255.
453 for (int i = 0; i < kNumTokenTypeIndexes; ++i)
454 {
455 std::array<std::uint8_t, 128> b256DataBuf{};
456 auto const [tokType, tokSize] = tokenTypeAndSize(i);
457 for (int d = 0; d <= 255; ++d)
458 {
459 memset(b256DataBuf.data(), d, tokSize);
460 testIt(tokType, std::span(b256DataBuf.data(), tokSize));
461 }
462 }
463}
464
465TEST_F(Base58FastMatchesRefTest, random_data)
466{
467 constexpr std::size_t kIters = 100000;
468
469 for (auto i = 0uz; i < kIters; ++i)
470 {
471 std::array<std::uint8_t, 128> b256DataBuf{};
472 auto const [tokType, b256Data] = randomB256TestData(b256DataBuf);
473 testIt(tokType, b256Data);
474 }
475}
476
477} // namespace xrpl::test
478
479#endif // _MSC_VER
T begin(T... args)
T copy(T... args)
T data(T... args)
T end(T... args)
T generate(T... args)
T max(T... args)
T memcmp(T... args)
T memset(T... args)
std::string decodeBase58(std::string const &s)
Definition tokens.cpp:252
std::string encodeBase58(void const *message, std::size_t size, void *temp, std::size_t tempSize)
Definition tokens.cpp:205
std::string encodeBase58Token(TokenType type, void const *token, std::size_t size)
Definition tokens.cpp:300
std::string decodeBase58Token(std::string const &s, TokenType type)
Definition tokens.cpp:323
TEST_F(BaseUintDeathTest, from_raw_size_mismatch)
Definition base_uint.cpp:73
TokenType
Definition tokens.h:19
BaseUInt< 160, detail::AccountIDTag > AccountID
A 160-bit unsigned that uniquely identifies an account.
Definition AccountID.h:34
T push_back(T... args)
T reserve(T... args)
T resize(T... args)
T setw(T... args)
T size(T... args)
T str(T... args)
T subspan(T... args)