diff options
author | Idan Horowitz <idan.horowitz@gmail.com> | 2021-06-08 23:43:44 +0300 |
---|---|---|
committer | Linus Groh <mail@linusgroh.de> | 2021-06-09 11:48:04 +0100 |
commit | b17a282b4b0a1f2831ea133b42aeec9e3d3e1208 (patch) | |
tree | 89836c67f5dd2743b9d7bd7732dd853a0b3ec52c /Userland/Libraries/LibCrypto | |
parent | 71c54198fa733efd6bfc99a73cbc024fe9bdc901 (diff) | |
download | serenity-b17a282b4b0a1f2831ea133b42aeec9e3d3e1208.zip |
LibCrypto: Add hash methods to {Signed, Unsigned}BigInteger
These just use hash the underlying bytes that make up the integer words
Diffstat (limited to 'Userland/Libraries/LibCrypto')
4 files changed, 25 insertions, 0 deletions
diff --git a/Userland/Libraries/LibCrypto/BigInt/SignedBigInteger.cpp b/Userland/Libraries/LibCrypto/BigInt/SignedBigInteger.cpp index 256cd3e923..98b91e4c3d 100644 --- a/Userland/Libraries/LibCrypto/BigInt/SignedBigInteger.cpp +++ b/Userland/Libraries/LibCrypto/BigInt/SignedBigInteger.cpp @@ -217,6 +217,11 @@ FLATTEN SignedDivisionResult SignedBigInteger::divided_by(const SignedBigInteger }; } +u32 SignedBigInteger::hash() const +{ + return m_unsigned_data.hash() * (1 - (2 * m_sign)); +} + void SignedBigInteger::set_bit_inplace(size_t bit_index) { m_unsigned_data.set_bit_inplace(bit_index); diff --git a/Userland/Libraries/LibCrypto/BigInt/SignedBigInteger.h b/Userland/Libraries/LibCrypto/BigInt/SignedBigInteger.h index 2d6aa2598a..5ac98d9662 100644 --- a/Userland/Libraries/LibCrypto/BigInt/SignedBigInteger.h +++ b/Userland/Libraries/LibCrypto/BigInt/SignedBigInteger.h @@ -99,6 +99,8 @@ public: SignedBigInteger multiplied_by(const UnsignedBigInteger& other) const; SignedDivisionResult divided_by(const UnsignedBigInteger& divisor) const; + u32 hash() const; + void set_bit_inplace(size_t bit_index); bool operator==(const SignedBigInteger& other) const; diff --git a/Userland/Libraries/LibCrypto/BigInt/UnsignedBigInteger.cpp b/Userland/Libraries/LibCrypto/BigInt/UnsignedBigInteger.cpp index d99ab08176..1039811ed3 100644 --- a/Userland/Libraries/LibCrypto/BigInt/UnsignedBigInteger.cpp +++ b/Userland/Libraries/LibCrypto/BigInt/UnsignedBigInteger.cpp @@ -6,6 +6,7 @@ #include "UnsignedBigInteger.h" #include <AK/StringBuilder.h> +#include <AK/StringHash.h> #include <LibCrypto/BigInt/Algorithms/UnsignedBigIntegerAlgorithms.h> namespace Crypto { @@ -106,6 +107,7 @@ void UnsignedBigInteger::set_to_0() m_words.clear_with_capacity(); m_is_invalid = false; m_cached_trimmed_length = {}; + m_cached_hash = 0; } void UnsignedBigInteger::set_to(UnsignedBigInteger::Word other) @@ -114,6 +116,7 @@ void UnsignedBigInteger::set_to(UnsignedBigInteger::Word other) m_words.resize_and_keep_capacity(1); m_words[0] = other; m_cached_trimmed_length = {}; + m_cached_hash = 0; } void UnsignedBigInteger::set_to(const UnsignedBigInteger& other) @@ -122,6 +125,7 @@ void UnsignedBigInteger::set_to(const UnsignedBigInteger& other) m_words.resize_and_keep_capacity(other.m_words.size()); __builtin_memcpy(m_words.data(), other.m_words.data(), other.m_words.size() * sizeof(u32)); m_cached_trimmed_length = {}; + m_cached_hash = 0; } size_t UnsignedBigInteger::trimmed_length() const @@ -252,6 +256,14 @@ FLATTEN UnsignedDivisionResult UnsignedBigInteger::divided_by(const UnsignedBigI return UnsignedDivisionResult { quotient, remainder }; } +u32 UnsignedBigInteger::hash() const +{ + if (m_cached_hash != 0) + return m_cached_hash; + + return m_cached_hash = string_hash((const char*)m_words.data(), sizeof(Word) * m_words.size()); +} + void UnsignedBigInteger::set_bit_inplace(size_t bit_index) { const size_t word_index = bit_index / UnsignedBigInteger::BITS_IN_WORD; @@ -265,6 +277,7 @@ void UnsignedBigInteger::set_bit_inplace(size_t bit_index) m_words[word_index] |= (1 << inner_word_index); m_cached_trimmed_length = {}; + m_cached_hash = 0; } bool UnsignedBigInteger::operator==(const UnsignedBigInteger& other) const diff --git a/Userland/Libraries/LibCrypto/BigInt/UnsignedBigInteger.h b/Userland/Libraries/LibCrypto/BigInt/UnsignedBigInteger.h index 489cd5c634..ff5bad7897 100644 --- a/Userland/Libraries/LibCrypto/BigInt/UnsignedBigInteger.h +++ b/Userland/Libraries/LibCrypto/BigInt/UnsignedBigInteger.h @@ -56,6 +56,7 @@ public: { m_is_invalid = true; m_cached_trimmed_length = {}; + m_cached_hash = 0; } bool is_odd() const { return m_words.size() && (m_words[0] & 1); } @@ -78,6 +79,8 @@ public: UnsignedBigInteger multiplied_by(const UnsignedBigInteger& other) const; UnsignedDivisionResult divided_by(const UnsignedBigInteger& divisor) const; + u32 hash() const; + void set_bit_inplace(size_t bit_index); bool operator==(const UnsignedBigInteger& other) const; @@ -90,6 +93,8 @@ private: // m_word[0] + m_word[1] * Word::MAX + m_word[2] * Word::MAX * Word::MAX + ... Vector<Word, STARTING_WORD_SIZE> m_words; + mutable u32 m_cached_hash { 0 }; + // Used to indicate a negative result, or a result of an invalid operation bool m_is_invalid { false }; |