LibCrypto: Cache the "trimmed length" of UnsignedBigIntegers

This avoids repeated traversals of the underlying words and gives a
30% speed-up on "test-crypto -t pk" :^)

2 files changed, 24 insertions, 9 deletions

diff --git a/Libraries/LibCrypto/BigInt/UnsignedBigInteger.cpp b/Libraries/LibCrypto/BigInt/UnsignedBigInteger.cpp
index d51cc66914..81367f1250 100644
--- a/Libraries/LibCrypto/BigInt/UnsignedBigInteger.cpp
+++ b/Libraries/LibCrypto/BigInt/UnsignedBigInteger.cpp
@@ -49,7 +49,7 @@ UnsignedBigInteger UnsignedBigInteger::import_data(const u8* ptr, size_t length)
     return integer;
 }
 
-size_t UnsignedBigInteger::export_data(AK::ByteBuffer& data)
+size_t UnsignedBigInteger::export_data(AK::ByteBuffer& data) const
 {
     UnsignedBigInteger copy { *this };
     UnsignedBigInteger quotient;
@@ -105,6 +105,7 @@ void UnsignedBigInteger::set_to_0()
 {
     m_words.clear_with_capacity();
     m_is_invalid = false;
+    m_cached_trimmed_length = {};
 }
 
 void UnsignedBigInteger::set_to(u32 other)
@@ -112,6 +113,7 @@ void UnsignedBigInteger::set_to(u32 other)
     m_is_invalid = false;
     m_words.resize_and_keep_capacity(1);
     m_words[0] = other;
+    m_cached_trimmed_length = {};
 }
 
 void UnsignedBigInteger::set_to(const UnsignedBigInteger& other)
@@ -119,16 +121,20 @@ void UnsignedBigInteger::set_to(const UnsignedBigInteger& other)
     m_is_invalid = other.m_is_invalid;
     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 = {};
 }
 
 size_t UnsignedBigInteger::trimmed_length() const
 {
-    size_t num_leading_zeroes = 0;
-    for (int i = length() - 1; i >= 0; --i, ++num_leading_zeroes) {
-        if (m_words[i] != 0)
-            break;
+    if (!m_cached_trimmed_length.has_value()) {
+        size_t num_leading_zeroes = 0;
+        for (int i = length() - 1; i >= 0; --i, ++num_leading_zeroes) {
+            if (m_words[i] != 0)
+                break;
+        }
+        m_cached_trimmed_length = length() - num_leading_zeroes;
     }
-    return length() - num_leading_zeroes;
+    return m_cached_trimmed_length.value();
 }
 
 FLATTEN UnsignedBigInteger UnsignedBigInteger::plus(const UnsignedBigInteger& other) const
@@ -206,6 +212,8 @@ void UnsignedBigInteger::set_bit_inplace(size_t bit_index)
         m_words.unchecked_append(0);
     }
     m_words[word_index] |= (1 << inner_word_index);
+
+    m_cached_trimmed_length = {};
 }
 
 bool UnsignedBigInteger::operator==(const UnsignedBigInteger& other) const
diff --git a/Libraries/LibCrypto/BigInt/UnsignedBigInteger.h b/Libraries/LibCrypto/BigInt/UnsignedBigInteger.h
index f6aa6b4232..d28a938bb4 100644
--- a/Libraries/LibCrypto/BigInt/UnsignedBigInteger.h
+++ b/Libraries/LibCrypto/BigInt/UnsignedBigInteger.h
@@ -52,8 +52,8 @@ public:
     static UnsignedBigInteger import_data(const AK::StringView& data) { return import_data((const u8*)data.characters_without_null_termination(), data.length()); }
     static UnsignedBigInteger import_data(const u8* ptr, size_t length);
 
-    size_t export_data(AK::ByteBuffer& data);
-    size_t export_data(const u8* ptr, size_t length)
+    size_t export_data(AK::ByteBuffer& data) const;
+    size_t export_data(const u8* ptr, size_t length) const
     {
         auto buffer = ByteBuffer::wrap(ptr, length);
         return export_data(buffer);
@@ -67,7 +67,12 @@ public:
     void set_to_0();
     void set_to(u32 other);
     void set_to(const UnsignedBigInteger& other);
-    void invalidate() { m_is_invalid = true; }
+
+    void invalidate()
+    {
+        m_is_invalid = true;
+        m_cached_trimmed_length = {};
+    }
 
     bool is_invalid() const { return m_is_invalid; }
 
@@ -103,6 +108,8 @@ private:
 
     // Used to indicate a negative result, or a result of an invalid operation
     bool m_is_invalid { false };
+
+    mutable Optional<size_t> m_cached_trimmed_length;
 };
 
 struct UnsignedDivisionResult {