LibCrypto+LibJS: Better bigint bitwise_and binop

Bitwise and is defined in terms of two's complement, so some converting
needs to happen for SignedBigInteger's sign/magnitude representation to
work out.

UnsignedBigInteger::bitwise_not() is repurposed to convert all
high-order zero bits to ones up to a limit, for the two's complement
conversion to work.

Fixes test262/test/language/expressions/bitwise-and/bigint.js.

6 files changed, 50 insertions, 23 deletions

diff --git a/Userland/Libraries/LibCrypto/BigInt/Algorithms/BitwiseOperations.cpp b/Userland/Libraries/LibCrypto/BigInt/Algorithms/BitwiseOperations.cpp
index 51bc227cf6..e8d474ec54 100644
--- a/Userland/Libraries/LibCrypto/BigInt/Algorithms/BitwiseOperations.cpp
+++ b/Userland/Libraries/LibCrypto/BigInt/Algorithms/BitwiseOperations.cpp
@@ -7,6 +7,7 @@
 
 #include "UnsignedBigIntegerAlgorithms.h"
 #include <AK/BuiltinWrappers.h>
+#include <AK/NumericLimits.h>
 
 namespace Crypto {
 
@@ -130,8 +131,9 @@ FLATTEN void UnsignedBigIntegerAlgorithms::bitwise_xor_without_allocation(
 /**
  * Complexity: O(N) where N is the number of words
  */
-FLATTEN void UnsignedBigIntegerAlgorithms::bitwise_not_without_allocation(
+FLATTEN void UnsignedBigIntegerAlgorithms::bitwise_not_fill_to_size_without_allocation(
     UnsignedBigInteger const& right,
+    size_t size,
     UnsignedBigInteger& output)
 {
     // If the value is invalid, the output value is invalid as well.
@@ -139,22 +141,17 @@ FLATTEN void UnsignedBigIntegerAlgorithms::bitwise_not_without_allocation(
         output.invalidate();
         return;
     }
-    if (right.length() == 0) {
+    if (size == 0) {
         output.set_to_0();
         return;
     }
 
-    output.m_words.resize_and_keep_capacity(right.length());
-
-    if (right.length() > 1) {
-        for (size_t i = 0; i < right.length() - 1; ++i)
-            output.m_words[i] = ~right.words()[i];
-    }
-
-    auto last_word_index = right.length() - 1;
-    auto last_word = right.words()[last_word_index];
-
-    output.m_words[last_word_index] = ((u32)0xffffffffffffffff >> count_leading_zeroes(last_word)) & ~last_word;
+    output.m_words.resize_and_keep_capacity(size);
+    size_t i;
+    for (i = 0; i < min(size, right.length()); ++i)
+        output.m_words[i] = ~right.words()[i];
+    for (; i < size; ++i)
+        output.m_words[i] = NumericLimits<UnsignedBigInteger::Word>::max();
 }
 
 /**
diff --git a/Userland/Libraries/LibCrypto/BigInt/Algorithms/UnsignedBigIntegerAlgorithms.h b/Userland/Libraries/LibCrypto/BigInt/Algorithms/UnsignedBigIntegerAlgorithms.h
index 36ef290dc5..62843635bd 100644
--- a/Userland/Libraries/LibCrypto/BigInt/Algorithms/UnsignedBigIntegerAlgorithms.h
+++ b/Userland/Libraries/LibCrypto/BigInt/Algorithms/UnsignedBigIntegerAlgorithms.h
@@ -18,7 +18,7 @@ public:
     static void bitwise_or_without_allocation(UnsignedBigInteger const& left, UnsignedBigInteger const& right, UnsignedBigInteger& output);
     static void bitwise_and_without_allocation(UnsignedBigInteger const& left, UnsignedBigInteger const& right, UnsignedBigInteger& output);
     static void bitwise_xor_without_allocation(UnsignedBigInteger const& left, UnsignedBigInteger const& right, UnsignedBigInteger& output);
-    static void bitwise_not_without_allocation(UnsignedBigInteger const& left, UnsignedBigInteger& output);
+    static void bitwise_not_fill_to_size_without_allocation(UnsignedBigInteger const& left, size_t, UnsignedBigInteger& output);
     static void shift_left_without_allocation(UnsignedBigInteger const& number, size_t bits_to_shift_by, UnsignedBigInteger& temp_result, UnsignedBigInteger& temp_plus, UnsignedBigInteger& output);
     static void multiply_without_allocation(UnsignedBigInteger const& left, UnsignedBigInteger const& right, UnsignedBigInteger& temp_shift_result, UnsignedBigInteger& temp_shift_plus, UnsignedBigInteger& temp_shift, UnsignedBigInteger& output);
     static void divide_without_allocation(UnsignedBigInteger const& numerator, UnsignedBigInteger const& denominator, UnsignedBigInteger& temp_shift_result, UnsignedBigInteger& temp_shift_plus, UnsignedBigInteger& temp_shift, UnsignedBigInteger& temp_minus, UnsignedBigInteger& quotient, UnsignedBigInteger& remainder);
diff --git a/Userland/Libraries/LibCrypto/BigInt/SignedBigInteger.cpp b/Userland/Libraries/LibCrypto/BigInt/SignedBigInteger.cpp
index 9d860f4c43..92cb384e19 100644
--- a/Userland/Libraries/LibCrypto/BigInt/SignedBigInteger.cpp
+++ b/Userland/Libraries/LibCrypto/BigInt/SignedBigInteger.cpp
@@ -194,12 +194,36 @@ FLATTEN SignedBigInteger SignedBigInteger::bitwise_or(const SignedBigInteger& ot
 
 FLATTEN SignedBigInteger SignedBigInteger::bitwise_and(const SignedBigInteger& other) const
 {
-    auto result = bitwise_and(other.unsigned_value());
-
-    // The sign bit will have to be AND'd manually.
-    result.m_sign = is_negative() && other.is_negative();
-
-    return result;
+    if (!is_negative() && !other.is_negative())
+        return { unsigned_value().bitwise_and(other.unsigned_value()), false };
+
+    // These two just use that -x == ~x + 1 (see below).
+
+    // -A & B == (~A + 1) & B.
+    if (is_negative() && !other.is_negative())
+        return { unsigned_value().bitwise_not_fill_to_size(other.trimmed_length()).plus(1).bitwise_and(other.unsigned_value()), false };
+
+    // A & -B == A & (~B + 1).
+    if (!is_negative() && other.is_negative())
+        return { unsigned_value().bitwise_and(other.unsigned_value().bitwise_not_fill_to_size(trimmed_length()).plus(1)), false };
+
+    // Both numbers are negative.
+    // x + ~x == 0xff...ff, up to however many bits x is wide.
+    // In two's complement, x + ~x + 1 == 0 since the 1 in the overflowing bit position is masked out.
+    // Rearranging terms, ~x = -x - 1 (eq1).
+    // Substituting x = y - 1, ~(y - 1) == -(y - 1) - 1 == -y +1 -1 == -y, or ~(y - 1) == -y (eq2).
+    // Since both numbers are negative, we want to compute -A & -B.
+    // Per (eq2):
+    //   -A & -B == ~(A - 1) & ~(B - 1)
+    // Inverting both sides:
+    //   ~(-A & -B) == ~(~(A - 1) & ~(B - 1)) == ~~(A - 1) | ~~(B - 1) == (A - 1) | (B - 1).
+    // Applying (q1) on the LHS:
+    //   -(-A & -B) - 1 == (A - 1) | (B - 1)
+    // Adding 1 on both sides and then multiplying both sides by -1:
+    //   -A & -B == -( (A - 1) | (B - 1) + 1)
+    // So we can compute the bitwise and by returning a negative number with magnitude (A - 1) | (B - 1) + 1.
+    // This is better than the naive (~A + 1) & (~B + 1) because it needs just one O(n) scan for the or instead of 2 for the ~s.
+    return { unsigned_value().minus(1).bitwise_or(other.unsigned_value().minus(1)).plus(1), true };
 }
 
 FLATTEN SignedBigInteger SignedBigInteger::bitwise_xor(const SignedBigInteger& other) const
diff --git a/Userland/Libraries/LibCrypto/BigInt/UnsignedBigInteger.cpp b/Userland/Libraries/LibCrypto/BigInt/UnsignedBigInteger.cpp
index 48ca0a6050..3f9cc0d6e9 100644
--- a/Userland/Libraries/LibCrypto/BigInt/UnsignedBigInteger.cpp
+++ b/Userland/Libraries/LibCrypto/BigInt/UnsignedBigInteger.cpp
@@ -218,11 +218,11 @@ FLATTEN UnsignedBigInteger UnsignedBigInteger::bitwise_xor(const UnsignedBigInte
     return result;
 }
 
-FLATTEN UnsignedBigInteger UnsignedBigInteger::bitwise_not() const
+FLATTEN UnsignedBigInteger UnsignedBigInteger::bitwise_not_fill_to_size(size_t size) const
 {
     UnsignedBigInteger result;
 
-    UnsignedBigIntegerAlgorithms::bitwise_not_without_allocation(*this, result);
+    UnsignedBigIntegerAlgorithms::bitwise_not_fill_to_size_without_allocation(*this, size, result);
 
     return result;
 }
diff --git a/Userland/Libraries/LibCrypto/BigInt/UnsignedBigInteger.h b/Userland/Libraries/LibCrypto/BigInt/UnsignedBigInteger.h
index 5f031b6781..c3826c532f 100644
--- a/Userland/Libraries/LibCrypto/BigInt/UnsignedBigInteger.h
+++ b/Userland/Libraries/LibCrypto/BigInt/UnsignedBigInteger.h
@@ -87,7 +87,7 @@ public:
     UnsignedBigInteger bitwise_or(const UnsignedBigInteger& other) const;
     UnsignedBigInteger bitwise_and(const UnsignedBigInteger& other) const;
     UnsignedBigInteger bitwise_xor(const UnsignedBigInteger& other) const;
-    UnsignedBigInteger bitwise_not() const;
+    UnsignedBigInteger bitwise_not_fill_to_size(size_t) const;
     UnsignedBigInteger shift_left(size_t num_bits) const;
     UnsignedBigInteger multiplied_by(const UnsignedBigInteger& other) const;
     UnsignedDivisionResult divided_by(const UnsignedBigInteger& divisor) const;
diff --git a/Userland/Libraries/LibJS/Tests/builtins/BigInt/bigint-basic.js b/Userland/Libraries/LibJS/Tests/builtins/BigInt/bigint-basic.js
index 7981551703..0a20f5751b 100644
--- a/Userland/Libraries/LibJS/Tests/builtins/BigInt/bigint-basic.js
+++ b/Userland/Libraries/LibJS/Tests/builtins/BigInt/bigint-basic.js
@@ -37,8 +37,14 @@ describe("correct behavior", () => {
 
     test("bitwise operators", () => {
         expect(12n & 5n).toBe(4n);
+        expect(3n & -2n).toBe(2n);
+        expect(-3n & -2n).toBe(-4n);
+        expect(-3n & 2n).toBe(0n);
+
         expect(1n | 2n).toBe(3n);
+
         expect(5n ^ 3n).toBe(6n);
+
         expect(~1n).toBe(-2n);
         expect(~-1n).toBe(0n);