ladybird/Libraries/LibCrypto/BigInt/SignedBigInteger.cpp

/*
 * Copyright (c) 2020, the SerenityOS developers.
 * Copyright (c) 2022, David Tuin <davidot@serenityos.org>
 *
 * SPDX-License-Identifier: BSD-2-Clause
 */

#include "SignedBigInteger.h"
#include <AK/StringBuilder.h>
#include <math.h>

namespace Crypto {

SignedBigInteger::SignedBigInteger(double value)
    : m_sign(value < 0.0)
    , m_unsigned_data(fabs(value))
{
}

SignedBigInteger SignedBigInteger::import_data(u8 const* ptr, size_t length)
{
    bool sign = *ptr;
    auto unsigned_data = UnsignedBigInteger::import_data(ptr + 1, length - 1);
    return { move(unsigned_data), sign };
}

size_t SignedBigInteger::export_data(Bytes data, bool remove_leading_zeros) const
{
    // FIXME: Support this:
    //        m <0XX> -> m <XX> (if remove_leading_zeros)
    VERIFY(!remove_leading_zeros);

    data[0] = m_sign;
    auto bytes_view = data.slice(1, data.size() - 1);
    return m_unsigned_data.export_data(bytes_view, remove_leading_zeros) + 1;
}

ErrorOr<SignedBigInteger> SignedBigInteger::from_base(u16 N, StringView str)
{
    auto sign = false;
    if (str.length() > 1) {
        auto maybe_sign = str[0];
        if (maybe_sign == '-') {
            str = str.substring_view(1);
            sign = true;
        }
        if (maybe_sign == '+')
            str = str.substring_view(1);
    }
    auto unsigned_data = TRY(UnsignedBigInteger::from_base(N, str));
    return SignedBigInteger { move(unsigned_data), sign };
}

ErrorOr<String> SignedBigInteger::to_base(u16 N) const
{
    StringBuilder builder;

    if (m_sign)
        TRY(builder.try_append('-'));

    auto unsigned_as_base = TRY(m_unsigned_data.to_base(N));
    TRY(builder.try_append(unsigned_as_base.bytes_as_string_view()));

    return builder.to_string();
}

ByteString SignedBigInteger::to_base_deprecated(u16 N) const
{
    return MUST(to_base(N)).to_byte_string();
}

u64 SignedBigInteger::to_u64() const
{
    u64 unsigned_value = m_unsigned_data.to_u64();
    if (!m_sign)
        return unsigned_value;
    return ~(unsigned_value - 1); // equivalent to `-unsigned_value`, but doesn't trigger UBSAN
}

double SignedBigInteger::to_double(UnsignedBigInteger::RoundingMode rounding_mode) const
{
    double unsigned_value = m_unsigned_data.to_double(rounding_mode);
    if (!m_sign)
        return unsigned_value;

    VERIFY(!is_zero());
    return -unsigned_value;
}

FLATTEN SignedBigInteger SignedBigInteger::plus(SignedBigInteger const& other) const
{
    // If both are of the same sign, just add the unsigned data and return.
    if (m_sign == other.m_sign)
        return { other.m_unsigned_data.plus(m_unsigned_data), m_sign };

    // One value is signed while the other is not.
    return m_sign ? other.minus(this->m_unsigned_data) : minus(other.m_unsigned_data);
}

FLATTEN SignedBigInteger SignedBigInteger::minus(SignedBigInteger const& other) const
{
    // If the signs are different, convert the op to an addition.
    if (m_sign != other.m_sign) {
        // -x - y = - (x + y)
        // x - -y = (x + y)
        SignedBigInteger result { other.m_unsigned_data.plus(this->m_unsigned_data) };
        if (m_sign)
            result.negate();
        return result;
    }

    if (!m_sign) {
        // Both operands are positive.
        // x - y = - (y - x)
        if (m_unsigned_data < other.m_unsigned_data) {
            // The result will be negative.
            return { other.m_unsigned_data.minus(m_unsigned_data), true };
        }

        // The result will be either zero, or positive.
        return SignedBigInteger { m_unsigned_data.minus(other.m_unsigned_data) };
    }

    // Both operands are negative.
    // -x - -y = y - x
    if (m_unsigned_data < other.m_unsigned_data) {
        // The result will be positive.
        return SignedBigInteger { other.m_unsigned_data.minus(m_unsigned_data) };
    }
    // y - x = - (x - y)
    if (m_unsigned_data > other.m_unsigned_data) {
        // The result will be negative.
        return SignedBigInteger { m_unsigned_data.minus(other.m_unsigned_data), true };
    }
    // Both operands have the same magnitude, the result is positive zero.
    return SignedBigInteger { 0 };
}

FLATTEN SignedBigInteger SignedBigInteger::plus(UnsignedBigInteger const& other) const
{
    if (m_sign) {
        if (other < m_unsigned_data)
            return { m_unsigned_data.minus(other), true };

        return { other.minus(m_unsigned_data), false };
    }

    return { m_unsigned_data.plus(other), false };
}

FLATTEN SignedBigInteger SignedBigInteger::minus(UnsignedBigInteger const& other) const
{
    if (m_sign)
        return { m_unsigned_data.plus(m_unsigned_data), true };

    if (other < m_unsigned_data)
        return { m_unsigned_data.minus(other), false };

    return { other.minus(m_unsigned_data), true };
}

FLATTEN SignedBigInteger SignedBigInteger::bitwise_not() const
{
    // Bitwise operators assume two's complement, while SignedBigInteger uses sign-magnitude.
    // In two's complement, -x := ~x + 1.
    // Hence, ~x == -x -1 == -(x + 1).
    SignedBigInteger result = plus(SignedBigInteger { 1 });
    result.negate();
    return result;
}

FLATTEN SignedBigInteger SignedBigInteger::multiplied_by(UnsignedBigInteger const& other) const
{
    return { unsigned_value().multiplied_by(other), m_sign };
}

FLATTEN SignedDivisionResult SignedBigInteger::divided_by(UnsignedBigInteger const& divisor) const
{
    auto division_result = unsigned_value().divided_by(divisor);
    return {
        { move(division_result.quotient), m_sign },
        { move(division_result.remainder), m_sign },
    };
}

FLATTEN SignedBigInteger SignedBigInteger::bitwise_or(SignedBigInteger const& other) const
{
    // See bitwise_and() for derivations.
    if (!is_negative() && !other.is_negative())
        return { unsigned_value().bitwise_or(other.unsigned_value()), false };

    // -A | B == (~A + 1) | B == ~(A - 1) | B. The result is negative, so need to two's complement at the end to move the sign into the m_sign field.
    // That can be simplified to:
    //   -(-A | B) == ~(~(A - 1) | B) + 1 = (A - 1) & ~B + 1
    // This saves one ~.
    if (is_negative() && !other.is_negative()) {
        size_t index = unsigned_value().one_based_index_of_highest_set_bit();
        return { unsigned_value().minus(1).bitwise_and(other.unsigned_value().bitwise_not_fill_to_one_based_index(index)).plus(1), true };
    }

    // -(A | -B) == ~A & (B - 1) + 1
    if (!is_negative() && other.is_negative()) {
        size_t index = other.unsigned_value().one_based_index_of_highest_set_bit();
        return { unsigned_value().bitwise_not_fill_to_one_based_index(index).bitwise_and(other.unsigned_value().minus(1)).plus(1), true };
    }

    return { unsigned_value().minus(1).bitwise_and(other.unsigned_value().minus(1)).plus(1), true };
}

FLATTEN SignedBigInteger SignedBigInteger::bitwise_and(SignedBigInteger const& other) const
{
    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()) {
        size_t index = other.unsigned_value().one_based_index_of_highest_set_bit();
        return { unsigned_value().bitwise_not_fill_to_one_based_index(index).plus(1).bitwise_and(other.unsigned_value()), false };
    }

    // A & -B == A & (~B + 1).
    if (!is_negative() && other.is_negative()) {
        size_t index = unsigned_value().one_based_index_of_highest_set_bit();
        return { unsigned_value().bitwise_and(other.unsigned_value().bitwise_not_fill_to_one_based_index(index).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(SignedBigInteger const& other) const
{
    return bitwise_or(other).minus(bitwise_and(other));
}

bool SignedBigInteger::operator==(UnsignedBigInteger const& other) const
{
    if (m_sign && m_unsigned_data != 0)
        return false;
    return m_unsigned_data == other;
}

bool SignedBigInteger::operator!=(UnsignedBigInteger const& other) const
{
    if (m_sign)
        return true;
    return m_unsigned_data != other;
}

bool SignedBigInteger::operator<(UnsignedBigInteger const& other) const
{
    if (m_sign)
        return true;
    return m_unsigned_data < other;
}

bool SignedBigInteger::operator>(UnsignedBigInteger const& other) const
{
    return *this != other && !(*this < other);
}

FLATTEN SignedBigInteger SignedBigInteger::shift_left(size_t num_bits) const
{
    return SignedBigInteger { m_unsigned_data.shift_left(num_bits), m_sign };
}

FLATTEN SignedBigInteger SignedBigInteger::shift_right(size_t num_bits) const
{
    return SignedBigInteger { m_unsigned_data.shift_right(num_bits), m_sign };
}

FLATTEN SignedBigInteger SignedBigInteger::multiplied_by(SignedBigInteger const& other) const
{
    bool result_sign = m_sign ^ other.m_sign;
    return { m_unsigned_data.multiplied_by(other.m_unsigned_data), result_sign };
}

FLATTEN SignedDivisionResult SignedBigInteger::divided_by(SignedBigInteger const& divisor) const
{
    // Aa / Bb -> (A^B)q, Ar
    bool result_sign = m_sign ^ divisor.m_sign;
    auto unsigned_division_result = m_unsigned_data.divided_by(divisor.m_unsigned_data);
    return {
        { move(unsigned_division_result.quotient), result_sign },
        { move(unsigned_division_result.remainder), m_sign }
    };
}

FLATTEN SignedBigInteger SignedBigInteger::negated_value() const
{
    auto result { *this };
    result.negate();
    return result;
}

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);
}

bool SignedBigInteger::operator==(SignedBigInteger const& other) const
{
    if (is_invalid() != other.is_invalid())
        return false;

    if (m_unsigned_data == 0 && other.m_unsigned_data == 0)
        return true;

    return m_sign == other.m_sign && m_unsigned_data == other.m_unsigned_data;
}

bool SignedBigInteger::operator!=(SignedBigInteger const& other) const
{
    return !(*this == other);
}

bool SignedBigInteger::operator<(SignedBigInteger const& other) const
{
    if (m_sign ^ other.m_sign)
        return m_sign;

    if (m_sign)
        return other.m_unsigned_data < m_unsigned_data;

    return m_unsigned_data < other.m_unsigned_data;
}

bool SignedBigInteger::operator<=(SignedBigInteger const& other) const
{
    return *this < other || *this == other;
}

bool SignedBigInteger::operator>(SignedBigInteger const& other) const
{
    return *this != other && !(*this < other);
}

bool SignedBigInteger::operator>=(SignedBigInteger const& other) const
{
    return !(*this < other);
}

UnsignedBigInteger::CompareResult SignedBigInteger::compare_to_double(double value) const
{
    bool bigint_is_negative = m_sign;

    bool value_is_negative = value < 0;

    if (value_is_negative != bigint_is_negative)
        return bigint_is_negative ? UnsignedBigInteger::CompareResult::DoubleGreaterThanBigInt : UnsignedBigInteger::CompareResult::DoubleLessThanBigInt;

    // Now both bigint and value have the same sign, so let's compare our magnitudes.
    auto magnitudes_compare_result = m_unsigned_data.compare_to_double(fabs(value));

    // If our mangnitudes are euqal, then we're equal.
    if (magnitudes_compare_result == UnsignedBigInteger::CompareResult::DoubleEqualsBigInt)
        return UnsignedBigInteger::CompareResult::DoubleEqualsBigInt;

    // If we're negative, revert the comparison result, otherwise return the same result.
    if (value_is_negative) {
        if (magnitudes_compare_result == UnsignedBigInteger::CompareResult::DoubleLessThanBigInt)
            return UnsignedBigInteger::CompareResult::DoubleGreaterThanBigInt;
        else
            return UnsignedBigInteger::CompareResult::DoubleLessThanBigInt;
    } else {
        return magnitudes_compare_result;
    }
}

}

ErrorOr<void> AK::Formatter<Crypto::SignedBigInteger>::format(FormatBuilder& fmtbuilder, Crypto::SignedBigInteger const& value)
{
    if (value.is_negative())
        TRY(fmtbuilder.put_string("-"sv));
    return Formatter<Crypto::UnsignedBigInteger>::format(fmtbuilder, value.unsigned_value());
}