UnsignedBigInteger.h 4.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133
  1. /*
  2. * Copyright (c) 2020, Itamar S. <itamar8910@gmail.com>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #pragma once
  7. #include <AK/ByteBuffer.h>
  8. #include <AK/Span.h>
  9. #include <AK/String.h>
  10. #include <AK/Types.h>
  11. #include <AK/Vector.h>
  12. namespace Crypto {
  13. struct UnsignedDivisionResult;
  14. constexpr size_t STARTING_WORD_SIZE = 32;
  15. class UnsignedBigInteger {
  16. public:
  17. using Word = u32;
  18. static constexpr size_t BITS_IN_WORD = 32;
  19. UnsignedBigInteger(Word x) { m_words.append(x); }
  20. explicit UnsignedBigInteger(Vector<Word, STARTING_WORD_SIZE>&& words)
  21. : m_words(move(words))
  22. {
  23. }
  24. explicit UnsignedBigInteger(const u8* ptr, size_t length);
  25. UnsignedBigInteger() { }
  26. static UnsignedBigInteger create_invalid();
  27. static UnsignedBigInteger import_data(const StringView& data) { return import_data((const u8*)data.characters_without_null_termination(), data.length()); }
  28. static UnsignedBigInteger import_data(const u8* ptr, size_t length)
  29. {
  30. return UnsignedBigInteger(ptr, length);
  31. }
  32. static UnsignedBigInteger create_from(u64 value)
  33. {
  34. VERIFY(sizeof(Word) == 4);
  35. UnsignedBigInteger integer;
  36. integer.m_words.resize(2);
  37. integer.m_words[0] = static_cast<Word>(value & 0xFFFFFFFF);
  38. integer.m_words[1] = static_cast<Word>((value >> 32) & 0xFFFFFFFF);
  39. return integer;
  40. }
  41. size_t export_data(Bytes, bool remove_leading_zeros = false) const;
  42. static UnsignedBigInteger from_base(u16 N, const String& str);
  43. String to_base(u16 N) const;
  44. u64 to_u64() const;
  45. const Vector<Word, STARTING_WORD_SIZE>& words() const { return m_words; }
  46. void set_to_0();
  47. void set_to(Word other);
  48. void set_to(const UnsignedBigInteger& other);
  49. void invalidate()
  50. {
  51. m_is_invalid = true;
  52. m_cached_trimmed_length = {};
  53. m_cached_hash = 0;
  54. }
  55. bool is_odd() const { return m_words.size() && (m_words[0] & 1); }
  56. bool is_invalid() const { return m_is_invalid; }
  57. size_t length() const { return m_words.size(); }
  58. // The "trimmed length" is the number of words after trimming leading zeroed words
  59. size_t trimmed_length() const;
  60. void clamp_to_trimmed_length();
  61. void resize_with_leading_zeros(size_t num_words);
  62. UnsignedBigInteger plus(const UnsignedBigInteger& other) const;
  63. UnsignedBigInteger minus(const UnsignedBigInteger& other) const;
  64. UnsignedBigInteger bitwise_or(const UnsignedBigInteger& other) const;
  65. UnsignedBigInteger bitwise_and(const UnsignedBigInteger& other) const;
  66. UnsignedBigInteger bitwise_xor(const UnsignedBigInteger& other) const;
  67. UnsignedBigInteger bitwise_not() const;
  68. UnsignedBigInteger shift_left(size_t num_bits) const;
  69. UnsignedBigInteger multiplied_by(const UnsignedBigInteger& other) const;
  70. UnsignedDivisionResult divided_by(const UnsignedBigInteger& divisor) const;
  71. u32 hash() const;
  72. void set_bit_inplace(size_t bit_index);
  73. bool operator==(const UnsignedBigInteger& other) const;
  74. bool operator!=(const UnsignedBigInteger& other) const;
  75. bool operator<(const UnsignedBigInteger& other) const;
  76. bool operator>(const UnsignedBigInteger& other) const;
  77. private:
  78. friend class UnsignedBigIntegerAlgorithms;
  79. // Little endian
  80. // m_word[0] + m_word[1] * Word::MAX + m_word[2] * Word::MAX * Word::MAX + ...
  81. Vector<Word, STARTING_WORD_SIZE> m_words;
  82. mutable u32 m_cached_hash { 0 };
  83. // Used to indicate a negative result, or a result of an invalid operation
  84. bool m_is_invalid { false };
  85. mutable Optional<size_t> m_cached_trimmed_length;
  86. };
  87. struct UnsignedDivisionResult {
  88. Crypto::UnsignedBigInteger quotient;
  89. Crypto::UnsignedBigInteger remainder;
  90. };
  91. }
  92. template<>
  93. struct AK::Formatter<Crypto::UnsignedBigInteger> : Formatter<StringView> {
  94. void format(FormatBuilder&, const Crypto::UnsignedBigInteger&);
  95. };
  96. inline Crypto::UnsignedBigInteger
  97. operator""_bigint(const char* string, size_t length)
  98. {
  99. return Crypto::UnsignedBigInteger::from_base(10, { string, length });
  100. }