xrpld
Loading...
Searching...
No Matches
base_uint.cpp
1#include <xrpl/basics/base_uint.h>
2
3#include <xrpl/basics/Blob.h>
4#include <xrpl/basics/hardened_hash.h>
5#include <xrpl/beast/utility/Zero.h>
6
7#include <boost/endian/detail/order.hpp>
8
9#include <gmock/gmock.h>
10#include <gtest/gtest.h>
11
12#include <array>
13#include <cassert>
14#include <complex>
15#include <cstddef>
16#include <cstdint>
17#include <format>
18#include <iterator>
19#include <stdexcept>
20#include <string>
21#include <string_view>
22#include <type_traits>
23#include <unordered_set>
24#include <utility>
25#include <vector>
26
27namespace xrpl::test {
28
29// a non-hashing Hasher that just copies the bytes.
30// Used to test hash_append in base_uint
31template <std::size_t Bits>
32struct Nonhash
33{
34 static constexpr auto const kEndian = boost::endian::order::big;
35 static constexpr std::size_t kWidth = Bits / 8;
36
38
39 Nonhash() = default;
40
41 void
42 operator()(void const* key, std::size_t len) noexcept
43 {
44 assert(len == kWidth);
45 memcpy(data.data(), key, len);
46 }
47
48 explicit
49 operator std::size_t() noexcept
50 {
51 return kWidth;
52 }
53};
54
55struct BaseUintTest : public ::testing::Test
56{
62
63 Blob const raw{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
67 // All ones XOR one: every bit set except the lowest.
69};
70
72
73TEST_F(BaseUintDeathTest, from_raw_size_mismatch)
74{
75 // ENABLE_VOIDSTAR is a debug build, but does not crash on failed asserts. Rather than twist
76 // these tests into knots to make them work, just skip them.
77#ifdef ENABLE_VOIDSTAR
78 GTEST_SKIP() << "ENABLE_VOIDSTAR is a debug build, but does not crash on failed asserts.";
79#else
80 auto const smallConstruct = [] {
81 // Container smaller than the base_uint (8 bytes vs 12 bytes for
82 // test96). Only the first 8 bytes are copied; the remaining 4 bytes
83 // stay zero.
84 Blob const tooSmall{1, 2, 3, 4, 5, 6, 7, 8};
85 BaseUInt96 const result = BaseUInt96::fromRaw(tooSmall);
86 auto const resultText = to_string(result);
87 EXPECT_EQ(resultText, "010203040506070800000000") << resultText;
88 };
89 EXPECT_DEBUG_DEATH(smallConstruct(), "input size match");
90
91 auto const largeConstruct = [] {
92 // Container larger than the base_uint (16 bytes vs 12 bytes for
93 // test96). Only the first 12 bytes are copied; the extra bytes are
94 // ignored.
95 Blob const tooBig{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
96 BaseUInt96 const result = BaseUInt96::fromRaw(tooBig);
97 auto const resultText = to_string(result);
98 EXPECT_EQ(resultText, "0102030405060708090A0B0C") << resultText;
99 };
100 EXPECT_DEBUG_DEATH(largeConstruct(), "input size match");
101
102 auto const smallCopy = [] {
103 // Container smaller than the base_uint (8 bytes vs 12 bytes for
104 // test96). Only the first 8 bytes are copied; the remaining 4 bytes
105 // stay zero.
106 Blob const tooSmall{1, 2, 3, 4, 5, 6, 7, 8};
107 BaseUInt96 result{};
108 --result;
109 {
110 auto const originalText = to_string(result);
111 EXPECT_EQ(originalText, "FFFFFFFFFFFFFFFFFFFFFFFF") << originalText;
112 }
113 result = tooSmall;
114 auto const resultText = to_string(result);
115 EXPECT_EQ(resultText, "010203040506070800000000") << resultText;
116 };
117 EXPECT_DEBUG_DEATH(smallCopy(), "input size match");
118
119 auto const largeCopy = [] {
120 // Container larger than the base_uint (16 bytes vs 12 bytes for
121 // test96). Only the first 12 bytes are copied; the extra bytes are
122 // ignored.
123 Blob const tooBig{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
124 BaseUInt96 result{};
125 --result;
126 {
127 auto const originalText = to_string(result);
128 EXPECT_EQ(originalText, "FFFFFFFFFFFFFFFFFFFFFFFF") << originalText;
129 }
130 result = tooBig;
131 auto const resultText = to_string(result);
132 EXPECT_EQ(resultText, "0102030405060708090A0B0C") << resultText;
133 };
134 EXPECT_DEBUG_DEATH(largeCopy(), "input size match");
135#endif
136}
137
138TEST_F(BaseUintTest, comparisons)
139{
141
142 {
143 static constexpr auto kTestArgs = std::to_array<HexPair>({
144 {"0000000000000000", "0000000000000001"},
145 {"0000000000000000", "ffffffffffffffff"},
146 {"1234567812345678", "2345678923456789"},
147 {"8000000000000000", "8000000000000001"},
148 {"aaaaaaaaaaaaaaa9", "aaaaaaaaaaaaaaaa"},
149 {"fffffffffffffffe", "ffffffffffffffff"},
150 });
151
152 for (auto const& [smallerText, largerText] : kTestArgs)
153 {
154 xrpl::BaseUInt<64> const smaller{smallerText}, larger{largerText};
155 // For code readability, we want to use general boolean
156 // expectations instead of specific EXPECT_LT etc.
157 EXPECT_TRUE(smaller < larger);
158 EXPECT_TRUE(smaller <= larger);
159 EXPECT_TRUE(smaller != larger);
160 EXPECT_FALSE(smaller == larger);
161 EXPECT_FALSE(smaller > larger);
162 EXPECT_FALSE(smaller >= larger);
163 EXPECT_FALSE(larger < smaller);
164 EXPECT_FALSE(larger <= smaller);
165 EXPECT_TRUE(larger != smaller);
166 EXPECT_FALSE(larger == smaller);
167 EXPECT_TRUE(larger > smaller);
168 EXPECT_TRUE(larger >= smaller);
169 EXPECT_TRUE(smaller == smaller);
170 EXPECT_TRUE(larger == larger);
171 }
172 }
173
174 {
175 static constexpr auto kTestArgs = std::to_array<HexPair>({
176 {"000000000000000000000000", "000000000000000000000001"},
177 {"000000000000000000000000", "ffffffffffffffffffffffff"},
178 {"0123456789ab0123456789ab", "123456789abc123456789abc"},
179 {"555555555555555555555555", "55555555555a555555555555"},
180 {"aaaaaaaaaaaaaaa9aaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaaaa"},
181 {"fffffffffffffffffffffffe", "ffffffffffffffffffffffff"},
182 });
183
184 for (auto const& [smallerText, largerText] : kTestArgs)
185 {
186 xrpl::BaseUInt<96> const smaller{smallerText}, larger{largerText};
187 EXPECT_TRUE(smaller < larger);
188 EXPECT_TRUE(smaller <= larger);
189 EXPECT_TRUE(smaller != larger);
190 EXPECT_FALSE(smaller == larger);
191 EXPECT_FALSE(smaller > larger);
192 EXPECT_FALSE(smaller >= larger);
193 EXPECT_FALSE(larger < smaller);
194 EXPECT_FALSE(larger <= smaller);
195 EXPECT_TRUE(larger != smaller);
196 EXPECT_FALSE(larger == smaller);
197 EXPECT_TRUE(larger > smaller);
198 EXPECT_TRUE(larger >= smaller);
199 EXPECT_TRUE(smaller == smaller);
200 EXPECT_TRUE(larger == larger);
201 }
202 }
203}
204
206{
207 EXPECT_EQ(BaseUInt96::kBytes, raw.size());
208 EXPECT_EQ(raw.size(), ascending.size());
209 EXPECT_EQ(to_string(ascending), "0102030405060708090A0B0C");
210 EXPECT_EQ(toShortString(ascending), "01020304...");
211 EXPECT_EQ(*ascending.data(), 1);
212 EXPECT_EQ(ascending.signum(), 1);
213 EXPECT_FALSE(!ascending);
214 EXPECT_FALSE(ascending.isZero());
215 EXPECT_TRUE(ascending.isNonZero());
216
217 unsigned char expectedByte = 0;
218 for (auto const& byte : ascending)
219 EXPECT_EQ(byte, ++expectedByte);
220}
221
222TEST_F(BaseUintTest, hash_append_writes_the_raw_bytes)
223{
224 // "Hash" with a no-op hasher and read the bytes it was handed back into
225 // another base_uint, which must then equal the original.
226 Nonhash<96> hasher{};
227 hash_append(hasher, ascending);
228
229 BaseUInt96 const rehashed =
230 BaseUInt96::fromRaw(std::vector<std::uint8_t>(hasher.data.begin(), hasher.data.end()));
231 EXPECT_EQ(rehashed, ascending);
232}
233
235{
236 EXPECT_EQ(to_string(complement), "FEFDFCFBFAF9F8F7F6F5F4F3");
237 EXPECT_EQ(toShortString(complement), "FEFDFCFB...");
238 EXPECT_EQ(*complement.data(), 0xfe);
239 EXPECT_EQ(complement.signum(), 1);
240 EXPECT_FALSE(!complement);
241 EXPECT_FALSE(complement.isZero());
242 EXPECT_TRUE(complement.isNonZero());
243
244 unsigned char expectedByte = 0xff;
245 for (auto const& byte : complement)
246 EXPECT_EQ(byte, --expectedByte);
247
248 EXPECT_LT(ascending, complement);
249 EXPECT_GT(complement, ascending);
250
251 BaseUInt96 assigned{complement};
252 assigned = ascending;
253 EXPECT_EQ(assigned, ascending);
254}
255
257{
258 EXPECT_EQ(to_string(zero), "000000000000000000000000");
259 EXPECT_EQ(toShortString(zero), "00000000...");
260 EXPECT_EQ(*zero.data(), 0);
261 EXPECT_EQ(*zero.begin(), 0);
262 EXPECT_EQ(*std::prev(zero.end(), 1), 0);
263 EXPECT_EQ(zero.signum(), 0);
264 EXPECT_TRUE(!zero);
265 EXPECT_TRUE(zero.isZero());
266 EXPECT_FALSE(zero.isNonZero());
267
268 for (auto const& byte : zero)
269 EXPECT_EQ(byte, 0);
270}
271
272TEST_F(BaseUintTest, the_several_ways_of_spelling_zero_agree)
273{
274 BaseUInt96 const defaultZero;
275 EXPECT_EQ(defaultZero, zero) << to_string(defaultZero);
276
277 BaseUInt96 const bracedZero{};
278 EXPECT_EQ(bracedZero, zero) << to_string(bracedZero);
279
280 BaseUInt96 const zeroFromUInt{0u};
281 EXPECT_EQ(zeroFromUInt, zero) << to_string(zeroFromUInt);
282}
283
284TEST_F(BaseUintTest, increment_and_decrement)
285{
286 BaseUInt96 counter{zero};
287
288 counter++;
289 EXPECT_EQ(counter, BaseUInt96(1));
290
291 counter--;
292 EXPECT_EQ(counter, beast::kZero);
293 EXPECT_EQ(counter, zero);
294
295 // Decrementing past zero wraps to all-ones.
296 counter--;
297 EXPECT_EQ(to_string(counter), "FFFFFFFFFFFFFFFFFFFFFFFF");
298 EXPECT_EQ(toShortString(counter), "FFFFFFFF...");
299
300 counter = beast::kZero;
301 EXPECT_EQ(counter, zero);
302}
303
304TEST_F(BaseUintTest, exclusive_or)
305{
306 EXPECT_EQ(to_string(xored), "FFFFFFFFFFFFFFFFFFFFFFFE") << to_string(xored);
307 EXPECT_EQ(toShortString(xored), "FFFFFFFF...") << toShortString(xored);
308}
309
310TEST_F(BaseUintTest, distinct_values_hash_into_a_set)
311{
312 // Requires hashing to work; four distinct values must stay four entries.
314
315 uset.insert(ascending);
316 uset.insert(complement);
317 uset.insert(zero);
318 uset.insert(xored);
319
320 EXPECT_EQ(uset.size(), 4);
321}
322
323TEST_F(BaseUintTest, parse_hex_round_trip)
324{
325 BaseUInt96 parsed;
326
327 EXPECT_TRUE(parsed.parseHex(to_string(ascending)));
328 EXPECT_EQ(parsed, ascending);
329}
330
331TEST_F(BaseUintTest, parse_hex_rejects_an_extra_leading_character)
332{
333 BaseUInt96 parsed{zero};
334
335 EXPECT_FALSE(parsed.parseHex(std::format("A{}", to_string(ascending))));
336}
337
338TEST_F(BaseUintTest, parse_hex_rejects_an_extra_trailing_character)
339{
340 BaseUInt96 parsed{zero};
341
342 EXPECT_FALSE(parsed.parseHex(std::format("{}A", to_string(ascending))));
343}
344
345TEST_F(BaseUintTest, parse_hex_rejects_a_non_hex_character_at_any_position)
346{
347 BaseUInt96 parsed{zero};
348
349 for (std::size_t i = 0; i != 24; ++i)
350 {
351 std::string corrupted = to_string(zero);
352 corrupted[i] = ('G' + (i % 10));
353 EXPECT_FALSE(parsed.parseHex(corrupted));
354 }
355}
356
357TEST_F(BaseUintTest, parse_hex_walking_ones)
358{
359 BaseUInt96 parsed;
360
361 for (std::size_t i = 0; i != 24; ++i)
362 {
363 std::string text = "000000000000000000000000";
364 text[i] = '1';
365
366 EXPECT_TRUE(parsed.parseHex(text));
367 EXPECT_EQ(to_string(parsed), text);
368 }
369}
370
371TEST_F(BaseUintTest, parse_hex_walking_zeroes)
372{
373 BaseUInt96 parsed;
374
375 for (std::size_t i = 0; i != 24; ++i)
376 {
377 std::string text = "111111111111111111111111";
378 text[i] = '0';
379
380 EXPECT_TRUE(parsed.parseHex(text));
381 EXPECT_EQ(to_string(parsed), text);
382 }
383}
384
385TEST_F(BaseUintTest, constexpr_construction)
386{
387 static_assert(BaseUInt96{}.signum() == 0);
388 static_assert(BaseUInt96("0").signum() == 0);
389 static_assert(BaseUInt96("000000000000000000000000").signum() == 0);
390 static_assert(BaseUInt96("000000000000000000000001").signum() == 1);
391 static_assert(BaseUInt96("800000000000000000000000").signum() == 1);
392}
393
394TEST_F(BaseUintTest, constexpr_constructor_throws_on_a_bad_length)
395{
396 // The vector keeps this out of a constant expression, so the constructor
397 // throws instead of failing to compile.
398 auto const tooShort = [] {
399 std::vector<char> const str(23, '7');
400 std::string_view const sView(str.data(), str.size());
401 [[maybe_unused]] BaseUInt96 const t96(sView);
402 };
403
404 EXPECT_THAT(
405 tooShort, ::testing::ThrowsMessage<std::invalid_argument>("invalid length for hex string"));
406}
407
408TEST_F(BaseUintTest, constexpr_constructor_throws_on_a_bad_character)
409{
410 auto const badCharacter = [] {
411 std::vector<char> str(23, '7');
412 str.push_back('G');
413 std::string_view const sView(str.data(), str.size());
414 [[maybe_unused]] BaseUInt96 const t96(sView);
415 };
416
417 EXPECT_THAT(badCharacter, ::testing::ThrowsMessage<std::range_error>("invalid hex character"));
418}
419
420TEST_F(BaseUintTest, constexpr_construction_agrees_with_parse_hex)
421{
422 struct StrBaseUInt
423 {
424 char const* const str;
425 BaseUInt96 tst;
426
427 constexpr StrBaseUInt(char const* s) : str(s), tst(s)
428 {
429 }
430 };
431
432 constexpr auto kTestCases = std::to_array<StrBaseUInt>({
433 "000000000000000000000000",
434 "000000000000000000000001",
435 "fedcba9876543210ABCDEF91",
436 "19FEDCBA0123456789abcdef",
437 "800000000000000000000000",
438 "fFfFfFfFfFfFfFfFfFfFfFfF",
439 });
440
441 for (StrBaseUInt const& testCase : kTestCases)
442 {
443 BaseUInt96 t96;
444 EXPECT_TRUE(t96.parseHex(testCase.str));
445 EXPECT_EQ(t96, testCase.tst);
446 }
447}
448
449} // namespace xrpl::test
T begin(T... args)
Integers of any length that is a multiple of 32-bits.
Definition base_uint.h:82
static BaseUInt fromRaw(Container const &c)
Definition base_uint.h:303
T data(T... args)
T end(T... args)
T format(T... args)
T insert(T... args)
T is_assignable_v
T is_constructible_v
T is_copy_assignable_v
T is_copy_constructible_v
constexpr Zero kZero
Definition Zero.h:30
void hash_append(Hasher &h, Account const &v) noexcept
BaseUintTest BaseUintDeathTest
Definition base_uint.cpp:71
TEST_F(BaseUintDeathTest, from_raw_size_mismatch)
Definition base_uint.cpp:73
std::string to_string(BaseUInt< Bits, Tag > const &a)
Definition base_uint.h:658
std::string toShortString(BaseUInt< Bits, Tag > const &a)
Definition base_uint.h:665
std::vector< unsigned char > Blob
Storage for linear binary data.
Definition Blob.h:11
T prev(T... args)
T push_back(T... args)
T size(T... args)
BaseUInt96 const xored
Definition base_uint.cpp:68
BaseUInt96 const zero
Definition base_uint.cpp:65
BaseUInt96 const ascending
Definition base_uint.cpp:64
BaseUInt< 96 > BaseUInt96
Definition base_uint.cpp:57
BaseUInt96 const complement
Definition base_uint.cpp:66
void operator()(void const *key, std::size_t len) noexcept
Definition base_uint.cpp:42
std::array< std::uint8_t, kWidth > data
Definition base_uint.cpp:37
static constexpr std::size_t kWidth
Definition base_uint.cpp:35
static constexpr auto const kEndian
Definition base_uint.cpp:34