UnsignedBigInteger.h 5.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154
  1. /*
  2. * Copyright (c) 2020, Itamar S. <itamar8910@gmail.com>
  3. * Copyright (c) 2022, the SerenityOS developers.
  4. * Copyright (c) 2022, David Tuin <davidot@serenityos.org>
  5. *
  6. * SPDX-License-Identifier: BSD-2-Clause
  7. */
  8. #pragma once
  9. #include <AK/ByteBuffer.h>
  10. #include <AK/Span.h>
  11. #include <AK/String.h>
  12. #include <AK/Types.h>
  13. #include <AK/Vector.h>
  14. namespace Crypto {
  15. struct UnsignedDivisionResult;
  16. constexpr size_t STARTING_WORD_SIZE = 32;
  17. class UnsignedBigInteger {
  18. public:
  19. using Word = u32;
  20. static constexpr size_t BITS_IN_WORD = 32;
  21. // This constructor accepts any unsigned with size up to Word.
  22. template<typename T>
  23. requires(IsIntegral<T> && sizeof(T) <= sizeof(Word))
  24. UnsignedBigInteger(T value)
  25. {
  26. m_words.append(static_cast<Word>(value));
  27. }
  28. explicit UnsignedBigInteger(Vector<Word, STARTING_WORD_SIZE>&& words)
  29. : m_words(move(words))
  30. {
  31. }
  32. explicit UnsignedBigInteger(u8 const* ptr, size_t length);
  33. explicit UnsignedBigInteger(double value);
  34. explicit UnsignedBigInteger(u64 value)
  35. {
  36. static_assert(sizeof(u64) == sizeof(Word) * 2);
  37. m_words.resize_and_keep_capacity(2);
  38. m_words[0] = static_cast<Word>(value & 0xFFFFFFFF);
  39. m_words[1] = static_cast<Word>((value >> 32) & 0xFFFFFFFF);
  40. }
  41. UnsignedBigInteger() = default;
  42. [[nodiscard]] static UnsignedBigInteger create_invalid();
  43. [[nodiscard]] static UnsignedBigInteger import_data(StringView data) { return import_data((u8 const*)data.characters_without_null_termination(), data.length()); }
  44. [[nodiscard]] static UnsignedBigInteger import_data(u8 const* ptr, size_t length)
  45. {
  46. return UnsignedBigInteger(ptr, length);
  47. }
  48. size_t export_data(Bytes, bool remove_leading_zeros = false) const;
  49. [[nodiscard]] static UnsignedBigInteger from_base(u16 N, StringView str);
  50. [[nodiscard]] String to_base(u16 N) const;
  51. [[nodiscard]] u64 to_u64() const;
  52. enum class RoundingMode {
  53. IEEERoundAndTiesToEvenMantissa,
  54. RoundTowardZero,
  55. // “the Number value for x”, https://tc39.es/ecma262/#number-value-for
  56. ECMAScriptNumberValueFor = IEEERoundAndTiesToEvenMantissa,
  57. };
  58. [[nodiscard]] double to_double(RoundingMode rounding_mode = RoundingMode::IEEERoundAndTiesToEvenMantissa) const;
  59. [[nodiscard]] Vector<Word, STARTING_WORD_SIZE> const& words() const { return m_words; }
  60. void set_to_0();
  61. void set_to(Word other);
  62. void set_to(UnsignedBigInteger const& other);
  63. void invalidate()
  64. {
  65. m_is_invalid = true;
  66. m_cached_trimmed_length = {};
  67. m_cached_hash = 0;
  68. }
  69. [[nodiscard]] bool is_zero() const;
  70. [[nodiscard]] bool is_odd() const { return m_words.size() && (m_words[0] & 1); }
  71. [[nodiscard]] bool is_invalid() const { return m_is_invalid; }
  72. [[nodiscard]] size_t length() const { return m_words.size(); }
  73. // The "trimmed length" is the number of words after trimming leading zeroed words
  74. [[nodiscard]] size_t trimmed_length() const;
  75. void clamp_to_trimmed_length();
  76. void resize_with_leading_zeros(size_t num_words);
  77. size_t one_based_index_of_highest_set_bit() const;
  78. [[nodiscard]] UnsignedBigInteger plus(UnsignedBigInteger const& other) const;
  79. [[nodiscard]] UnsignedBigInteger minus(UnsignedBigInteger const& other) const;
  80. [[nodiscard]] UnsignedBigInteger bitwise_or(UnsignedBigInteger const& other) const;
  81. [[nodiscard]] UnsignedBigInteger bitwise_and(UnsignedBigInteger const& other) const;
  82. [[nodiscard]] UnsignedBigInteger bitwise_xor(UnsignedBigInteger const& other) const;
  83. [[nodiscard]] UnsignedBigInteger bitwise_not_fill_to_one_based_index(size_t) const;
  84. [[nodiscard]] UnsignedBigInteger shift_left(size_t num_bits) const;
  85. [[nodiscard]] UnsignedBigInteger multiplied_by(UnsignedBigInteger const& other) const;
  86. [[nodiscard]] UnsignedDivisionResult divided_by(UnsignedBigInteger const& divisor) const;
  87. [[nodiscard]] u32 hash() const;
  88. void set_bit_inplace(size_t bit_index);
  89. [[nodiscard]] bool operator==(UnsignedBigInteger const& other) const;
  90. [[nodiscard]] bool operator!=(UnsignedBigInteger const& other) const;
  91. [[nodiscard]] bool operator<(UnsignedBigInteger const& other) const;
  92. [[nodiscard]] bool operator>(UnsignedBigInteger const& other) const;
  93. [[nodiscard]] bool operator>=(UnsignedBigInteger const& other) const;
  94. private:
  95. friend class UnsignedBigIntegerAlgorithms;
  96. // Little endian
  97. // m_word[0] + m_word[1] * Word::MAX + m_word[2] * Word::MAX * Word::MAX + ...
  98. Vector<Word, STARTING_WORD_SIZE> m_words;
  99. mutable u32 m_cached_hash { 0 };
  100. // Used to indicate a negative result, or a result of an invalid operation
  101. bool m_is_invalid { false };
  102. mutable Optional<size_t> m_cached_trimmed_length;
  103. };
  104. struct UnsignedDivisionResult {
  105. Crypto::UnsignedBigInteger quotient;
  106. Crypto::UnsignedBigInteger remainder;
  107. };
  108. }
  109. template<>
  110. struct AK::Formatter<Crypto::UnsignedBigInteger> : Formatter<StringView> {
  111. ErrorOr<void> format(FormatBuilder&, Crypto::UnsignedBigInteger const&);
  112. };
  113. inline Crypto::UnsignedBigInteger
  114. operator""_bigint(char const* string, size_t length)
  115. {
  116. return Crypto::UnsignedBigInteger::from_base(10, { string, length });
  117. }