xrpld
Loading...
Searching...
No Matches
base_uint.h
1// Copyright (c) 2009-2010 Satoshi Nakamoto
2// Copyright (c) 2011 The Bitcoin developers
3// Distributed under the MIT/X11 software license, see the accompanying
4// file license.txt or http://www.opensource.org/licenses/mit-license.php.
5
6#pragma once
7
8#include <xrpl/basics/Slice.h>
9#include <xrpl/basics/contract.h>
10#include <xrpl/basics/hardened_hash.h>
11#include <xrpl/basics/partitioned_unordered_map.h>
12#include <xrpl/basics/strHex.h>
13#include <xrpl/beast/hash/hash_append.h>
14#include <xrpl/beast/utility/Zero.h>
15#include <xrpl/beast/utility/instrumentation.h>
16
17#include <boost/endian/conversion.hpp>
18#include <boost/functional/hash.hpp>
19
20#include <algorithm>
21#include <array>
22#include <compare>
23#include <cstddef>
24#include <cstdint>
25#include <cstring>
26#include <expected>
27#include <iterator>
28#include <optional>
29#include <ostream>
30#include <stdexcept>
31#include <string>
32#include <string_view>
33#include <type_traits>
34
35namespace xrpl {
36
37namespace detail {
38
39template <class Container, class = std::void_t<>>
43
44template <class Container>
46 Container,
47 std::void_t<
48 decltype(std::declval<Container const>().size()),
49 decltype(std::declval<Container const>().data()),
50 typename Container::value_type>> : std::true_type
51{
52};
53
54template <>
58
59template <typename...>
63
64} // namespace detail
65
80template <std::size_t Bits, class Tag = void>
82{
83 static_assert((Bits % 32) == 0, "The length of a base_uint in bits must be a multiple of 32.");
84
85 static_assert(Bits >= 64, "The length of a base_uint in bits must be at least 64.");
86
87 static constexpr std::size_t kWidth = Bits / 32;
88
89 // This is really big-endian in byte order.
90 // We sometimes use std::uint32_t for speed.
91
93
94public:
95 //--------------------------------------------------------------------------
96 //
97 // STL Container Interface
98 //
99
100 static constexpr std::size_t kBytes = Bits / 8;
101 static_assert(sizeof(data_) == kBytes);
102
105 using value_type = unsigned char;
108 using const_pointer = value_type const*;
114 using TagType = Tag;
115
116 pointer
118 {
119 return reinterpret_cast<pointer>(data_.data());
120 }
121 [[nodiscard]] const_pointer
122 data() const
123 {
124 return reinterpret_cast<const_pointer>(data_.data());
125 }
126
127 iterator
129 {
130 return data();
131 }
132 iterator
134 {
135 return data() + kBytes;
136 }
137 [[nodiscard]] const_iterator
138 begin() const
139 {
140 return data();
141 }
142 [[nodiscard]] const_iterator
143 end() const
144 {
145 return data() + kBytes;
146 }
147 [[nodiscard]] const_iterator
148 cbegin() const
149 {
150 return data();
151 }
152 [[nodiscard]] const_iterator
153 cend() const
154 {
155 return data() + kBytes;
156 }
157
164
165 //--------------------------------------------------------------------------
166
167private:
175 // NIKB TODO Remove the need for this constructor.
177 {
178 explicit VoidHelper() = default;
179 };
180
181 explicit BaseUInt(void const* data, VoidHelper)
182 {
183 memcpy(data_.data(), data, kBytes);
184 }
185
186 // Helper function to initialize a base_uint from a std::string_view.
187 enum class ParseResult {
188 Okay,
189 BadLength,
190 BadChar,
191 };
192
193 constexpr std::expected<decltype(data_), ParseResult>
195 {
196 // Local lambda that converts a single hex char to four bits and
197 // ORs those bits into a uint32_t.
198 auto const hexCharToUInt =
199 [](char c, std::uint32_t shift, std::uint32_t& accum) -> ParseResult {
200 std::uint32_t nibble = 0xFFu;
201 if (c < '0' || c > 'f')
202 return ParseResult::BadChar;
203
204 if (c >= 'a')
205 {
206 nibble = static_cast<std::uint32_t>(c - 'a' + 0xA);
207 }
208 else if (c >= 'A')
209 {
210 nibble = static_cast<std::uint32_t>(c - 'A' + 0xA);
211 }
212 else if (c <= '9')
213 {
214 nibble = static_cast<std::uint32_t>(c - '0');
215 }
216
217 if (nibble > 0xFu)
218 return ParseResult::BadChar;
219
220 accum |= (nibble << shift);
221
222 return ParseResult::Okay;
223 };
224
225 decltype(data_) ret{};
226
227 if (sv == "0")
228 {
229 return ret;
230 }
231
232 if (sv.size() != size() * 2)
233 return std::unexpected(ParseResult::BadLength);
234
235 std::size_t i = 0u;
236 auto in = sv.begin();
237 while (in != sv.end())
238 {
239 std::uint32_t accum = {};
240 for (std::uint32_t const shift : {4u, 0u, 12u, 8u, 20u, 16u, 28u, 24u})
241 {
242 if (auto const result = hexCharToUInt(*in++, shift, accum);
243 result != ParseResult::Okay)
244 return std::unexpected(result);
245 }
246 ret[i++] = accum;
247 }
248 return ret;
249 }
250
251 constexpr decltype(data_)
253 {
254 auto const result = parseFromStringView(sv);
255 if (!result)
256 {
257 if (result.error() == ParseResult::BadLength)
258 Throw<std::invalid_argument>("invalid length for hex string");
259
260 Throw<std::range_error>("invalid hex character");
261 }
262 return *result;
263 }
264
265public:
266 constexpr BaseUInt() : data_{}
267 {
268 }
269
271 {
272 }
273
275 {
276 *this = b;
277 }
278
279 // This constructor is intended to be used at compile time since it might
280 // throw at runtime. Consider declaring this constructor consteval once
281 // we get to C++23.
282 explicit constexpr BaseUInt(std::string_view sv) noexcept(false)
284 {
285 }
286
287 template <class Container>
288 explicit BaseUInt(Container const& c)
289 requires(
292 {
293 // Use AlwaysFalseT so the static_assert condition is dependent
294 // and only triggers when this constructor template is instantiated.
295 static_assert(
297 "This constructor is not intended to be used and will be soon removed. "
298 "Use base_uint::fromRaw instead.");
299 }
300
301 template <class Container>
302 static BaseUInt
303 fromRaw(Container const& c)
304 requires(
307 {
308 BaseUInt result;
309 XRPL_ASSERT(
310 c.size() * sizeof(typename Container::value_type) == size(),
311 "xrpl::BaseUInt::fromRaw(Container auto) : input size match");
312 std::size_t const canCopy =
313 std::min(size(), c.size() * sizeof(typename Container::value_type));
314 std::memcpy(result.data_.data(), c.data(), canCopy);
315 return result;
316 }
317
318 template <class Container>
319 BaseUInt&
320 operator=(Container const& c)
321 requires(
324 {
325 XRPL_ASSERT(
326 c.size() * sizeof(typename Container::value_type) == size(),
327 "xrpl::BaseUInt::operator=(Container auto) : input size match");
328 std::size_t const canCopy =
329 std::min(size(), c.size() * sizeof(typename Container::value_type));
330 if (canCopy < size())
331 *this = beast::kZero;
332 std::memcpy(data_.data(), c.data(), canCopy);
333 return *this;
334 }
335
336 /* Construct from a raw pointer.
337 The buffer pointed to by `data` must be at least Bits/8 bytes.
338 */
339 static BaseUInt
340 fromVoid(void const* data)
341 {
342 return BaseUInt(data, VoidHelper());
343 }
344
345 template <class T>
347 fromVoidChecked(T const& from)
348 {
349 if (from.size() != size())
350 return {};
351 return fromVoid(from.data());
352 }
353
354 [[nodiscard]] constexpr int
355 signum() const
356 {
357 for (int i = 0; i < kWidth; i++)
358 {
359 if (data_[i] != 0)
360 return 1;
361 }
362
363 return 0;
364 }
365
366 bool
367 operator!() const
368 {
369 return *this == beast::kZero;
370 }
371
372 constexpr BaseUInt
373 operator~() const
374 {
375 BaseUInt ret;
376
377 for (int i = 0; i < kWidth; i++)
378 ret.data_[i] = ~data_[i];
379
380 return ret;
381 }
382
383 BaseUInt&
385 {
386 *this = beast::kZero;
387 // NOLINTBEGIN(cppcoreguidelines-pro-type-member-init)
388 union
389 {
390 unsigned u[2];
391 std::uint64_t ul;
392 };
393 // NOLINTEND(cppcoreguidelines-pro-type-member-init)
394 // Put in least significant bits.
395 ul = boost::endian::native_to_big(uHost);
396 data_[kWidth - 2] = u[0];
397 data_[kWidth - 1] = u[1];
398 return *this;
399 }
400
401 BaseUInt&
403 {
404 for (int i = 0; i < kWidth; i++)
405 data_[i] ^= b.data_[i];
406
407 return *this;
408 }
409
410 BaseUInt&
412 {
413 for (int i = 0; i < kWidth; i++)
414 data_[i] &= b.data_[i];
415
416 return *this;
417 }
418
419 BaseUInt&
421 {
422 for (int i = 0; i < kWidth; i++)
423 data_[i] |= b.data_[i];
424
425 return *this;
426 }
427
428 BaseUInt&
430 {
431 // prefix operator
432 for (int i = kWidth - 1; i >= 0; --i)
433 {
434 data_[i] = boost::endian::native_to_big(boost::endian::big_to_native(data_[i]) + 1);
435 if (data_[i] != 0)
436 break;
437 }
438
439 return *this;
440 }
441
444 {
445 // postfix operator
446 BaseUInt const ret = *this;
447 ++(*this);
448
449 return ret;
450 }
451
452 BaseUInt&
454 {
455 for (int i = kWidth - 1; i >= 0; --i)
456 {
457 auto const prev = data_[i];
458 data_[i] = boost::endian::native_to_big(boost::endian::big_to_native(data_[i]) - 1);
459
460 if (prev != 0)
461 break;
462 }
463
464 return *this;
465 }
466
469 {
470 // postfix operator
471 BaseUInt const ret = *this;
472 --(*this);
473
474 return ret;
475 }
476
477 [[nodiscard]] BaseUInt
478 next() const
479 {
480 auto ret = *this;
481 return ++ret;
482 }
483
484 [[nodiscard]] BaseUInt
485 prev() const
486 {
487 auto ret = *this;
488 return --ret;
489 }
490
491 BaseUInt&
493 {
494 std::uint64_t carry = 0;
495
496 for (int i = kWidth - 1; i >= 0; i--)
497 {
498 std::uint64_t const n = carry + boost::endian::big_to_native(data_[i]) +
499 boost::endian::big_to_native(b.data_[i]);
500
501 data_[i] = boost::endian::native_to_big(static_cast<std::uint32_t>(n));
502 carry = n >> 32;
503 }
504
505 return *this;
506 }
507
508 template <class Hasher>
509 friend void
510 hash_append(Hasher& h, BaseUInt const& a) noexcept
511 {
512 // Do not allow any endian transformations on this memory
513 h(a.data_.data(), sizeof(a.data_));
514 }
515
525 [[nodiscard]] constexpr bool
527 {
528 auto const result = parseFromStringView(sv);
529 if (!result)
530 return false;
531
532 data_ = *result;
533 return true;
534 }
535
536 [[nodiscard]] constexpr bool
537 parseHex(char const* str)
538 {
539 return parseHex(std::string_view{str});
540 }
541
542 [[nodiscard]] bool
544 {
545 return parseHex(std::string_view{str});
546 }
547
548 static constexpr std::size_t
550 {
551 return kBytes;
552 }
553
556 {
557 data_.fill(0);
558 return *this;
559 }
560
561 // Deprecated.
562 [[nodiscard]] bool
563 isZero() const
564 {
565 return *this == beast::kZero;
566 }
567 [[nodiscard]] bool
568 isNonZero() const
569 {
570 return *this != beast::kZero;
571 }
572 void
574 {
575 *this = beast::kZero;
576 }
577};
578
583
584// TODO [#8340]: Legacy names still used by external consumers of libxrpl (e.g. rpc-spec).
585// Do not use in new code; remove once those consumers have migrated.
586using uint160 = UInt160; // NOLINT(readability-identifier-naming)
587using uint256 = UInt256; // NOLINT(readability-identifier-naming)
588using uint192 = UInt192; // NOLINT(readability-identifier-naming)
589
590template <std::size_t Bits, class Tag>
591[[nodiscard]] constexpr std::strong_ordering
593{
594 // This comparison might seem wrong on a casual inspection because it
595 // compares data internally stored as std::uint32_t byte-by-byte. But
596 // note that the underlying data is stored in big endian, even if the
597 // platform is little endian. This makes the comparison correct.
598 //
599 // FIXME: use std::lexicographical_compare_three_way once support is
600 // added to MacOS.
601
602 auto const ret = std::mismatch(lhs.cbegin(), lhs.cend(), rhs.cbegin());
603
604 // a == b
605 if (ret.first == lhs.cend())
606 return std::strong_ordering::equivalent;
607
608 return (*ret.first > *ret.second) ? std::strong_ordering::greater : std::strong_ordering::less;
609}
610
611template <std::size_t Bits, typename Tag>
612[[nodiscard]] constexpr bool
614{
615 return (lhs <=> rhs) == 0; // NOLINT(modernize-use-nullptr)
616}
617
618//------------------------------------------------------------------------------
619template <std::size_t Bits, class Tag>
620constexpr bool
622{
623 return a == BaseUInt<Bits, Tag>(b);
624}
625
626//------------------------------------------------------------------------------
627template <std::size_t Bits, class Tag>
628constexpr BaseUInt<Bits, Tag>
630{
631 return BaseUInt<Bits, Tag>(a) ^= b;
632}
633
634template <std::size_t Bits, class Tag>
635constexpr BaseUInt<Bits, Tag>
637{
638 return BaseUInt<Bits, Tag>(a) &= b;
639}
640
641template <std::size_t Bits, class Tag>
642constexpr BaseUInt<Bits, Tag>
644{
645 return BaseUInt<Bits, Tag>(a) |= b;
646}
647
648template <std::size_t Bits, class Tag>
649constexpr BaseUInt<Bits, Tag>
651{
652 return BaseUInt<Bits, Tag>(a) += b;
653}
654
655//------------------------------------------------------------------------------
656template <std::size_t Bits, class Tag>
657inline std::string
659{
660 return strHex(a.cbegin(), a.cend());
661}
662
663template <std::size_t Bits, class Tag>
664inline std::string
666{
667 static_assert(BaseUInt<Bits, Tag>::kBytes > 4, "For 4 bytes or less, use a native type");
668 return strHex(a.cbegin(), a.cbegin() + 4) + "...";
669}
670
671template <std::size_t Bits, class Tag>
674{
675 return out << to_string(u);
676}
677
678template <>
679inline std::size_t
680extract(UInt256 const& key)
681{
682 std::size_t result = 0;
683 // Use memcpy to avoid unaligned UB
684 // (will optimize to equivalent code)
685 std::memcpy(&result, key.data(), sizeof(std::size_t));
686 return result;
687}
688
689#ifndef __INTELLISENSE__
690static_assert(sizeof(UInt128) == 128 / 8, "There should be no padding bytes");
691static_assert(sizeof(UInt160) == 160 / 8, "There should be no padding bytes");
692static_assert(sizeof(UInt192) == 192 / 8, "There should be no padding bytes");
693static_assert(sizeof(UInt256) == 256 / 8, "There should be no padding bytes");
694#endif
695
696} // namespace xrpl
697
698namespace beast {
699
700template <std::size_t Bits, class Tag>
701struct IsUniquelyRepresented<xrpl::BaseUInt<Bits, Tag>> : public std::true_type
702{
703 explicit IsUniquelyRepresented() = default;
704};
705
706} // namespace beast
T begin(T... args)
Integers of any length that is a multiple of 32-bits.
Definition base_uint.h:82
std::size_t size_type
Definition base_uint.h:103
bool operator!() const
Definition base_uint.h:367
value_type * pointer
Definition base_uint.h:106
unsigned char value_type
Definition base_uint.h:105
std::reverse_iterator< iterator > reverse_iterator
Definition base_uint.h:112
BaseUInt operator++(int)
Definition base_uint.h:443
BaseUInt(std::uint64_t b)
Definition base_uint.h:274
static BaseUInt fromRaw(Container const &c)
Definition base_uint.h:303
std::ptrdiff_t difference_type
Definition base_uint.h:104
static BaseUInt fromVoid(void const *data)
Definition base_uint.h:340
const_iterator cend() const
Definition base_uint.h:153
BaseUInt & operator++()
Definition base_uint.h:429
constexpr BaseUInt(std::string_view sv) noexcept(false)
Definition base_uint.h:282
BaseUInt & operator&=(BaseUInt const &b)
Definition base_uint.h:411
bool parseHex(std::string const &str)
Definition base_uint.h:543
constexpr int signum() const
Definition base_uint.h:355
BaseUInt & operator+=(BaseUInt const &b)
Definition base_uint.h:492
constexpr bool parseHex(char const *str)
Definition base_uint.h:537
value_type const * const_pointer
Definition base_uint.h:108
const_iterator begin() const
Definition base_uint.h:138
bool isZero() const
Definition base_uint.h:563
constexpr decltype(data_) parseFromStringViewThrows(std::string_view sv) noexcept(false)
Definition base_uint.h:252
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition base_uint.h:113
BaseUInt & operator--()
Definition base_uint.h:453
constexpr std::expected< decltype(data_), ParseResult > parseFromStringView(std::string_view sv) noexcept
Definition base_uint.h:194
bool isNonZero() const
Definition base_uint.h:568
BaseUInt & operator|=(BaseUInt const &b)
Definition base_uint.h:420
BaseUInt(Container const &c)
Definition base_uint.h:288
const_pointer data() const
Definition base_uint.h:122
iterator end()
Definition base_uint.h:133
static constexpr std::size_t kWidth
Definition base_uint.h:87
value_type & reference
Definition base_uint.h:107
BaseUInt< Bits, Tag > & operator=(beast::Zero)
Definition base_uint.h:555
std::array< std::uint32_t, kWidth > data_
Definition base_uint.h:92
pointer data()
Definition base_uint.h:117
BaseUInt & operator=(Container const &c)
Definition base_uint.h:320
constexpr BaseUInt(beast::Zero)
Definition base_uint.h:270
HardenedHash<> hasher
Value hashing function.
Definition base_uint.h:163
BaseUInt(void const *data, VoidHelper)
Definition base_uint.h:181
friend void hash_append(Hasher &h, BaseUInt const &a) noexcept
Definition base_uint.h:510
const_pointer const_iterator
Definition base_uint.h:111
BaseUInt next() const
Definition base_uint.h:478
BaseUInt & operator^=(BaseUInt const &b)
Definition base_uint.h:402
constexpr BaseUInt()
Definition base_uint.h:266
constexpr BaseUInt operator~() const
Definition base_uint.h:373
static constexpr std::size_t kBytes
Definition base_uint.h:100
static std::optional< BaseUInt > fromVoidChecked(T const &from)
Definition base_uint.h:347
const_iterator end() const
Definition base_uint.h:143
BaseUInt & operator=(std::uint64_t uHost)
Definition base_uint.h:384
iterator begin()
Definition base_uint.h:128
static constexpr std::size_t size()
Definition base_uint.h:549
BaseUInt operator--(int)
Definition base_uint.h:468
value_type const & const_reference
Definition base_uint.h:109
BaseUInt prev() const
Definition base_uint.h:485
constexpr bool parseHex(std::string_view sv)
Parse a hex string into a base_uint.
Definition base_uint.h:526
const_iterator cbegin() const
Definition base_uint.h:148
pointer iterator
Definition base_uint.h:110
Seed functor once per construction.
An immutable linear range of bytes.
Definition Slice.h:28
T data(T... args)
T end(T... args)
T is_trivially_copyable_v
T memcpy(T... args)
T min(T... args)
T mismatch(T... args)
constexpr Zero kZero
Definition Zero.h:30
STL namespace.
Use hash_* containers for keys that do not need a cryptographically secure hashing algorithm.
Definition algorithm.h:5
constexpr BaseUInt< Bits, Tag > operator+(BaseUInt< Bits, Tag > const &a, BaseUInt< Bits, Tag > const &b)
Definition base_uint.h:650
constexpr BaseUInt< Bits, Tag > operator^(BaseUInt< Bits, Tag > const &a, BaseUInt< Bits, Tag > const &b)
Definition base_uint.h:629
UInt192 uint192
Definition base_uint.h:588
constexpr BaseUInt< Bits, Tag > operator&(BaseUInt< Bits, Tag > const &a, BaseUInt< Bits, Tag > const &b)
Definition base_uint.h:636
constexpr bool operator==(BaseUInt< Bits, Tag > const &lhs, BaseUInt< Bits, Tag > const &rhs)
Definition base_uint.h:613
std::string strHex(FwdIt begin, FwdIt end)
Definition strHex.h:13
BaseUInt< 128 > UInt128
Definition base_uint.h:579
BaseUInt< 160 > UInt160
Definition base_uint.h:580
constexpr BaseUInt< Bits, Tag > operator|(BaseUInt< Bits, Tag > const &a, BaseUInt< Bits, Tag > const &b)
Definition base_uint.h:643
std::ostream & operator<<(std::ostream &out, BaseUInt< Bits, Tag > const &u)
Definition base_uint.h:673
BaseUInt< 192 > UInt192
Definition base_uint.h:582
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
BaseUInt< 256 > UInt256
Definition base_uint.h:581
constexpr std::strong_ordering operator<=>(BaseUInt< Bits, Tag > const &lhs, BaseUInt< Bits, Tag > const &rhs)
Definition base_uint.h:592
UInt160 uint160
Definition base_uint.h:586
std::size_t extract(UInt256 const &key)
Definition base_uint.h:680
UInt256 uint256
Definition base_uint.h:587
XRPL_NO_SANITIZE_ADDRESS void Throw(Args &&... args)
Definition contract.h:52
T size(T... args)
Zero allows classes to offer efficient comparisons to zero.
Definition Zero.h:26
T unexpected(T... args)