From b17a282b4b0a1f2831ea133b42aeec9e3d3e1208 Mon Sep 17 00:00:00 2001
From: Idan Horowitz <idan.horowitz@gmail.com>
Date: Tue, 8 Jun 2021 23:43:44 +0300
Subject: LibCrypto: Add hash methods to {Signed, Unsigned}BigInteger

These just use hash the underlying bytes that make up the integer words
---
 Userland/Libraries/LibCrypto/BigInt/SignedBigInteger.cpp   |  5 +++++
 Userland/Libraries/LibCrypto/BigInt/SignedBigInteger.h     |  2 ++
 Userland/Libraries/LibCrypto/BigInt/UnsignedBigInteger.cpp | 13 +++++++++++++
 Userland/Libraries/LibCrypto/BigInt/UnsignedBigInteger.h   |  5 +++++
 4 files changed, 25 insertions(+)

(limited to 'Userland/Libraries/LibCrypto')

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 };
 
-- 
cgit v1.2.3