LibCrypto: Small fixes in BigInteger & test-crypto

2 files changed, 113 insertions, 114 deletions

diff --git a/Libraries/LibCrypto/BigInt/UnsignedBigInteger.cpp b/Libraries/LibCrypto/BigInt/UnsignedBigInteger.cpp
index 29bc5eb7b5..4dfbb30b1f 100644
--- a/Libraries/LibCrypto/BigInt/UnsignedBigInteger.cpp
+++ b/Libraries/LibCrypto/BigInt/UnsignedBigInteger.cpp
@@ -29,6 +29,41 @@
 
 namespace Crypto {
 
+UnsignedBigInteger UnsignedBigInteger::create_invalid()
+{
+    UnsignedBigInteger invalid(0);
+    invalid.invalidate();
+    return invalid;
+}
+
+// FIXME: in great need of optimisation
+UnsignedBigInteger UnsignedBigInteger::import_data(const u8* ptr, size_t length)
+{
+    UnsignedBigInteger integer { 0 };
+
+    for (size_t i = 0; i < length; ++i) {
+        auto part = UnsignedBigInteger { ptr[length - i - 1] }.shift_left(8 * i);
+        integer = integer.plus(part);
+    }
+
+    return integer;
+}
+
+size_t UnsignedBigInteger::export_data(AK::ByteBuffer& data)
+{
+    UnsignedBigInteger copy { *this };
+
+    size_t size = trimmed_length() * sizeof(u32);
+    size_t i = 0;
+    for (; i < size; ++i) {
+        if (copy.length() == 0)
+            break;
+        data[size - i - 1] = copy.m_words[0] & 0xff;
+        copy = copy.divided_by(256).quotient;
+    }
+    return i;
+}
+
 UnsignedBigInteger UnsignedBigInteger::from_base10(const String& str)
 {
     UnsignedBigInteger result;
@@ -61,9 +96,14 @@ String UnsignedBigInteger::to_base10() const
     return builder.to_string();
 }
 
-bool UnsignedBigInteger::operator!=(const UnsignedBigInteger& other) const
+size_t UnsignedBigInteger::trimmed_length() const
 {
-    return !(*this == other);
+    size_t num_leading_zeroes = 0;
+    for (int i = length() - 1; i >= 0; --i, ++num_leading_zeroes) {
+        if (m_words[i] != 0)
+            break;
+    }
+    return length() - num_leading_zeroes;
 }
 
 /**
@@ -141,6 +181,32 @@ UnsignedBigInteger UnsignedBigInteger::minus(const UnsignedBigInteger& other) co
     return result;
 }
 
+UnsignedBigInteger UnsignedBigInteger::shift_left(size_t num_bits) const
+{
+    // We can only do shift operations on individual words
+    // where the shift amount is <= size of word (32).
+    // But we do know how to shift by a multiple of word size (e.g 64=32*2)
+    // So we first shift the result by how many whole words fit in 'num_bits'
+    UnsignedBigInteger temp_result = shift_left_by_n_words(num_bits / UnsignedBigInteger::BITS_IN_WORD);
+
+    // And now we shift by the leftover amount of bits
+    num_bits %= UnsignedBigInteger::BITS_IN_WORD;
+
+    UnsignedBigInteger result(temp_result);
+
+    for (size_t i = 0; i < temp_result.length(); ++i) {
+        u32 current_word_of_temp_result = temp_result.shift_left_get_one_word(num_bits, i);
+        result.m_words[i] = current_word_of_temp_result;
+    }
+
+    // Shifting the last word can produce a carry
+    u32 carry_word = temp_result.shift_left_get_one_word(num_bits, temp_result.length());
+    if (carry_word != 0) {
+        result = result.plus(UnsignedBigInteger(carry_word).shift_left_by_n_words(temp_result.length()));
+    }
+    return result;
+}
+
 /**
  * Complexity: O(N^2) where N is the number of words in the larger number
  * Multiplcation method:
@@ -210,69 +276,6 @@ void UnsignedBigInteger::set_bit_inplace(size_t bit_index)
     m_words[word_index] |= (1 << inner_word_index);
 }
 
-UnsignedBigInteger UnsignedBigInteger::shift_left(size_t num_bits) const
-{
-    // We can only do shift operations on individual words
-    // where the shift amount is <= size of word (32).
-    // But we do know how to shift by a multiple of word size (e.g 64=32*2)
-    // So we first shift the result by how many whole words fit in 'num_bits'
-    UnsignedBigInteger temp_result = shift_left_by_n_words(num_bits / UnsignedBigInteger::BITS_IN_WORD);
-
-    // And now we shift by the leftover amount of bits
-    num_bits %= UnsignedBigInteger::BITS_IN_WORD;
-
-    UnsignedBigInteger result(temp_result);
-
-    for (size_t i = 0; i < temp_result.length(); ++i) {
-        u32 current_word_of_temp_result = temp_result.shift_left_get_one_word(num_bits, i);
-        result.m_words[i] = current_word_of_temp_result;
-    }
-
-    // Shifting the last word can produce a carry
-    u32 carry_word = temp_result.shift_left_get_one_word(num_bits, temp_result.length());
-    if (carry_word != 0) {
-        result = result.plus(UnsignedBigInteger(carry_word).shift_left_by_n_words(temp_result.length()));
-    }
-    return result;
-}
-
-ALWAYS_INLINE UnsignedBigInteger UnsignedBigInteger::shift_left_by_n_words(const size_t number_of_words) const
-{
-    // shifting left by N words means just inserting N zeroes to the beginning of the words vector
-    UnsignedBigInteger result;
-
-    result.m_words.ensure_capacity(number_of_words + length());
-
-    for (size_t i = 0; i < number_of_words; ++i) {
-        result.m_words.unchecked_append(0);
-    }
-    for (size_t i = 0; i < length(); ++i) {
-        result.m_words.unchecked_append(m_words[i]);
-    }
-    return result;
-}
-
-/**
- * Returns the word at a requested index in the result of a shift operation
- */
-ALWAYS_INLINE u32 UnsignedBigInteger::shift_left_get_one_word(const size_t num_bits, const size_t result_word_index) const
-{
-    // "<= length()" (rather than length() - 1) is intentional,
-    // The result inedx of length() is used when calculating the carry word
-    ASSERT(result_word_index <= length());
-    ASSERT(num_bits <= UnsignedBigInteger::BITS_IN_WORD);
-    u32 result = 0;
-
-    // we need to check for "num_bits != 0" since shifting right by 32 is apparently undefined behaviour!
-    if (result_word_index > 0 && num_bits != 0) {
-        result += m_words[result_word_index - 1] >> (UnsignedBigInteger::BITS_IN_WORD - num_bits);
-    }
-    if (result_word_index < length() && num_bits < 32) {
-        result += m_words[result_word_index] << num_bits;
-    }
-    return result;
-}
-
 bool UnsignedBigInteger::operator==(const UnsignedBigInteger& other) const
 {
     auto length = trimmed_length();
@@ -288,6 +291,11 @@ bool UnsignedBigInteger::operator==(const UnsignedBigInteger& other) const
     return !__builtin_memcmp(m_words.data(), other.words().data(), length);
 }
 
+bool UnsignedBigInteger::operator!=(const UnsignedBigInteger& other) const
+{
+    return !(*this == other);
+}
+
 bool UnsignedBigInteger::operator<(const UnsignedBigInteger& other) const
 {
     auto length = trimmed_length();
@@ -312,48 +320,40 @@ bool UnsignedBigInteger::operator<(const UnsignedBigInteger& other) const
     return false;
 }
 
-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;
-    }
-    return length() - num_leading_zeroes;
-}
-
-UnsignedBigInteger UnsignedBigInteger::create_invalid()
+ALWAYS_INLINE UnsignedBigInteger UnsignedBigInteger::shift_left_by_n_words(const size_t number_of_words) const
 {
-    UnsignedBigInteger invalid(0);
-    invalid.invalidate();
-    return invalid;
-}
+    // shifting left by N words means just inserting N zeroes to the beginning of the words vector
+    UnsignedBigInteger result;
 
-// FIXME: in great need of optimisation
-UnsignedBigInteger UnsignedBigInteger::import_data(const u8* ptr, size_t length)
-{
-    UnsignedBigInteger integer { 0 };
+    result.m_words.ensure_capacity(number_of_words + length());
 
-    for (size_t i = 0; i < length; ++i) {
-        auto part = UnsignedBigInteger { ptr[length - i - 1] }.shift_left(8 * i);
-        integer = integer.plus(part);
+    for (size_t i = 0; i < number_of_words; ++i) {
+        result.m_words.unchecked_append(0);
     }
-
-    return integer;
+    for (size_t i = 0; i < length(); ++i) {
+        result.m_words.unchecked_append(m_words[i]);
+    }
+    return result;
 }
 
-size_t UnsignedBigInteger::export_data(AK::ByteBuffer& data)
+/**
+ * Returns the word at a requested index in the result of a shift operation
+ */
+ALWAYS_INLINE u32 UnsignedBigInteger::shift_left_get_one_word(const size_t num_bits, const size_t result_word_index) const
 {
-    UnsignedBigInteger copy { *this };
+    // "<= length()" (rather than length() - 1) is intentional,
+    // The result inedx of length() is used when calculating the carry word
+    ASSERT(result_word_index <= length());
+    ASSERT(num_bits <= UnsignedBigInteger::BITS_IN_WORD);
+    u32 result = 0;
 
-    size_t size = trimmed_length() * sizeof(u32);
-    size_t i = 0;
-    for (; i < size; ++i) {
-        if (copy.length() == 0)
-            break;
-        data[size - i - 1] = copy.m_words[0] & 0xff;
-        copy = copy.divided_by(256).quotient;
+    // we need to check for "num_bits != 0" since shifting right by 32 is apparently undefined behaviour!
+    if (result_word_index > 0 && num_bits != 0) {
+        result += m_words[result_word_index - 1] >> (UnsignedBigInteger::BITS_IN_WORD - num_bits);
     }
-    return i;
+    if (result_word_index < length() && num_bits < 32) {
+        result += m_words[result_word_index] << num_bits;
+    }
+    return result;
 }
 }
diff --git a/Libraries/LibCrypto/BigInt/UnsignedBigInteger.h b/Libraries/LibCrypto/BigInt/UnsignedBigInteger.h
index 8189d5d9bb..0dd6be3564 100644
--- a/Libraries/LibCrypto/BigInt/UnsignedBigInteger.h
+++ b/Libraries/LibCrypto/BigInt/UnsignedBigInteger.h
@@ -41,13 +41,12 @@ public:
     UnsignedBigInteger(u32 x) { m_words.append(x); }
 
     explicit UnsignedBigInteger(AK::Vector<u32, STARTING_WORD_SIZE>&& words)
-        : m_words(words)
+        : m_words(move(words))
     {
     }
 
-    UnsignedBigInteger() { }
+    UnsignedBigInteger() {}
 
-    static UnsignedBigInteger from_base10(const String& str);
     static UnsignedBigInteger create_invalid();
 
     static UnsignedBigInteger import_data(const AK::StringView& data) { return import_data((const u8*)data.characters_without_null_termination(), data.length()); }
@@ -60,31 +59,31 @@ public:
         return export_data(buffer);
     }
 
+    static UnsignedBigInteger from_base10(const String& str);
+    String to_base10() const;
+
     const AK::Vector<u32, STARTING_WORD_SIZE>& words() const { return m_words; }
 
+    void invalidate() { m_is_invalid = true; }
+
+    bool is_invalid() const { return m_is_invalid; }
+
+    size_t length() const { return m_words.size(); }
+    // The "trimmed length" is the number of words after trimming leading zeroed words
+    size_t trimmed_length() const;
+
     UnsignedBigInteger plus(const UnsignedBigInteger& other) const;
     UnsignedBigInteger minus(const UnsignedBigInteger& other) const;
-    UnsignedBigInteger multiplied_by(const UnsignedBigInteger& other) const;
     UnsignedBigInteger shift_left(size_t num_bits) const;
-
+    UnsignedBigInteger multiplied_by(const UnsignedBigInteger& other) const;
     UnsignedDivisionResult divided_by(const UnsignedBigInteger& divisor) const;
 
     void set_bit_inplace(size_t bit_index);
 
-    size_t length() const { return m_words.size(); }
-
-    // The "trimmed length" is the number of words after trimming leading zeroed words
-    size_t trimmed_length() const;
-
     bool operator==(const UnsignedBigInteger& other) const;
     bool operator!=(const UnsignedBigInteger& other) const;
     bool operator<(const UnsignedBigInteger& other) const;
 
-    void invalidate() { m_is_invalid = true; }
-    bool is_invalid() const { return m_is_invalid; }
-
-    String to_base10() const;
-
 private:
     ALWAYS_INLINE UnsignedBigInteger shift_left_by_n_words(const size_t number_of_words) const;
     ALWAYS_INLINE u32 shift_left_get_one_word(const size_t num_bits, const size_t result_word_index) const;