uint256.test.cpp

Go to the documentation of this file.

#include "uint256.hpp"
#include "../random/engine.hpp"
#include <gtest/gtest.h>
 
using namespace bb;
using namespace bb::numeric;
namespace {
auto& engine = numeric::get_debug_randomness();
}
 
TEST(uint256, TestStringConstructors)
{
    std::string input = "9a807b615c4d3e2fa0b1c2d3e4f56789fedcba9876543210abcdef0123456789";
    const std::string input4("0x9a807b615c4d3e2fa0b1c2d3e4f56789fedcba9876543210abcdef0123456789");
 
    const uint256_t result1(input);
    constexpr uint256_t result2("9a807b615c4d3e2fa0b1c2d3e4f56789fedcba9876543210abcdef0123456789");
    const uint256_t result3("0x9a807b615c4d3e2fa0b1c2d3e4f56789fedcba9876543210abcdef0123456789");
    const uint256_t result4(input4);
    constexpr uint256_t expected{
        0xabcdef0123456789,
        0xfedcba9876543210,
        0xa0b1c2d3e4f56789,
        0x9a807b615c4d3e2f,
    };
    EXPECT_EQ(result1, result2);
    EXPECT_EQ(result1, result3);
    EXPECT_EQ(result1, result4);
    EXPECT_EQ(result1, expected);
}
 
TEST(uint256, GetBit)
{
    constexpr uint256_t a{ 0b0110011001110010011001100111001001100110011100100110011001110011,
                           0b1001011101101010101010100100101101101001001010010101110101010111,
                           0b0101010010010101111100001011011010101010110101110110110111010101,
                           0b0101011010101010100010001000101011010101010101010010000100000000 };
 
    uint256_t res;
    for (size_t i = 0; i < 256; ++i) {
        res += a.get_bit(i) ? (uint256_t(1) << i) : 0;
    }
 
    EXPECT_EQ(a, res);
}
 
TEST(uint256, Add)
{
    constexpr uint256_t a{ 1, 2, 3, 4 };
    constexpr uint256_t b{ 5, 6, 7, 8 };
 
    constexpr uint256_t c = a + b;
    uint256_t d = a;
    d += b;
    EXPECT_EQ(c.data[0], 6ULL);
    EXPECT_EQ(c.data[1], 8ULL);
    EXPECT_EQ(c.data[2], 10ULL);
    EXPECT_EQ(c.data[3], 12ULL);
    EXPECT_EQ(d.data[0], 6ULL);
    EXPECT_EQ(d.data[1], 8ULL);
    EXPECT_EQ(d.data[2], 10ULL);
    EXPECT_EQ(d.data[3], 12ULL);
}
 
TEST(uint256, GetMsb)
{
    uint256_t a{ 0, 0, 1, 1 };
    uint256_t b{ 1, 0, 1, 0 };
    uint256_t c{ 0, 1, 0, 0 };
    uint256_t d{ 1, 0, 0, 0 };
 
    EXPECT_EQ(a.get_msb(), 192ULL);
    EXPECT_EQ(b.get_msb(), 128ULL);
    EXPECT_EQ(c.get_msb(), 64ULL);
    EXPECT_EQ(d.get_msb(), 0ULL);
}
 
TEST(uint256, Mul)
{
    uint256_t a = engine.get_random_uint256();
    uint256_t b = engine.get_random_uint256();
 
    uint256_t c = (a + b) * (a + b);
    uint256_t d = (a * a) + (b * b) + (a * b) + (a * b);
    EXPECT_EQ(c.data[0], d.data[0]);
    EXPECT_EQ(c.data[1], d.data[1]);
    EXPECT_EQ(c.data[2], d.data[2]);
    EXPECT_EQ(c.data[3], d.data[3]);
}
 
TEST(uint256, DivAndMod)
{
    for (size_t i = 0; i < 256; ++i) {
        uint256_t a = engine.get_random_uint256();
        uint256_t b = engine.get_random_uint256();
 
        b.data[3] = (i > 0) ? 0 : b.data[3];
        b.data[2] = (i > 1) ? 0 : b.data[2];
        b.data[1] = (i > 2) ? 0 : b.data[1];
        if (b == 0) {
            b = 1;
        }
        uint256_t q = a / b;
        uint256_t r = a % b;
 
        uint256_t c = q * b + r;
        EXPECT_EQ(c.data[0], a.data[0]);
        EXPECT_EQ(c.data[1], a.data[1]);
        EXPECT_EQ(c.data[2], a.data[2]);
        EXPECT_EQ(c.data[3], a.data[3]);
    }
 
    uint256_t a = engine.get_random_uint256();
    uint256_t b = a;
    uint256_t q = a / b;
    uint256_t r = a % b;
 
    EXPECT_EQ(q, uint256_t(1));
    EXPECT_EQ(r, uint256_t(0));
}
 
TEST(uint256, Sub)
{
    uint256_t a = engine.get_random_uint256();
    uint256_t b = engine.get_random_uint256();
 
    uint256_t c = (a - b) * (a + b);
    uint256_t d = (a * a) - (b * b);
 
    EXPECT_EQ(c.data[0], d.data[0]);
    EXPECT_EQ(c.data[1], d.data[1]);
    EXPECT_EQ(c.data[2], d.data[2]);
    EXPECT_EQ(c.data[3], d.data[3]);
 
    uint256_t e = 0;
    e = e - 1;
 
    EXPECT_EQ(e.data[0], UINT64_MAX);
    EXPECT_EQ(e.data[1], UINT64_MAX);
    EXPECT_EQ(e.data[2], UINT64_MAX);
    EXPECT_EQ(e.data[3], UINT64_MAX);
}
 
TEST(uint256, RightShift)
{
    constexpr uint256_t a{ 0xaaaaaaaaaaaaaaaa, 0xbbbbbbbbbbbbbbbb, 0xcccccccccccccccc, 0xdddddddddddddddd };
 
    constexpr uint256_t b = a >> 256;
    EXPECT_EQ(b, uint256_t(0));
 
    constexpr uint256_t c = a >> 0;
    EXPECT_EQ(a, c);
 
    constexpr uint256_t d = a >> 64;
    EXPECT_EQ(d, uint256_t(0xbbbbbbbbbbbbbbbb, 0xcccccccccccccccc, 0xdddddddddddddddd, 0));
 
    constexpr uint256_t e = a >> 123;
    constexpr uint256_t f = e * (uint256_t{ 0, 1ULL << 59ULL, 0, 0 });
    EXPECT_EQ(f, uint256_t(0, 0xb800000000000000, 0xcccccccccccccccc, 0xdddddddddddddddd));
}
 
TEST(uint256, LeftShift)
{
    uint256_t a{ 0xaaaaaaaaaaaaaaaa, 0xbbbbbbbbbbbbbbbb, 0xcccccccccccccccc, 0xdddddddddddddddd };
 
    uint256_t b = a << 256;
    EXPECT_EQ(b, uint256_t(0));
 
    uint256_t c = a << 0;
    EXPECT_EQ(a, c);
 
    uint256_t d = a << 64;
    EXPECT_EQ(d, uint256_t(0, 0xaaaaaaaaaaaaaaaa, 0xbbbbbbbbbbbbbbbb, 0xcccccccccccccccc));
 
    uint256_t e = a << 123;
    e = e >> 123;
    EXPECT_EQ(e, uint256_t(0xaaaaaaaaaaaaaaaa, 0xbbbbbbbbbbbbbbbb, 0xc, 0));
 
    uint256_t large_shift = uint256_t(1) << 64;
    uint256_t f = a << large_shift;
    EXPECT_EQ(f, uint256_t(0));
}
 
TEST(uint256, And)
{
    uint256_t a = engine.get_random_uint256();
    uint256_t b = engine.get_random_uint256();
 
    uint256_t c = a & b;
 
    EXPECT_EQ(c.data[0], a.data[0] & b.data[0]);
    EXPECT_EQ(c.data[1], a.data[1] & b.data[1]);
    EXPECT_EQ(c.data[2], a.data[2] & b.data[2]);
    EXPECT_EQ(c.data[3], a.data[3] & b.data[3]);
}
 
TEST(uint256, Or)
{
    uint256_t a = engine.get_random_uint256();
    uint256_t b = engine.get_random_uint256();
 
    uint256_t c = a | b;
 
    EXPECT_EQ(c.data[0], a.data[0] | b.data[0]);
    EXPECT_EQ(c.data[1], a.data[1] | b.data[1]);
    EXPECT_EQ(c.data[2], a.data[2] | b.data[2]);
    EXPECT_EQ(c.data[3], a.data[3] | b.data[3]);
}
 
TEST(uint256, Xor)
{
    uint256_t a = engine.get_random_uint256();
    uint256_t b = engine.get_random_uint256();
 
    uint256_t c = a ^ b;
 
    EXPECT_EQ(c.data[0], a.data[0] ^ b.data[0]);
    EXPECT_EQ(c.data[1], a.data[1] ^ b.data[1]);
    EXPECT_EQ(c.data[2], a.data[2] ^ b.data[2]);
    EXPECT_EQ(c.data[3], a.data[3] ^ b.data[3]);
}
 
TEST(uint256, BitNot)
{
    uint256_t a = engine.get_random_uint256();
 
    uint256_t c = ~a;
 
    EXPECT_EQ(c.data[0], ~a.data[0]);
    EXPECT_EQ(c.data[1], ~a.data[1]);
    EXPECT_EQ(c.data[2], ~a.data[2]);
    EXPECT_EQ(c.data[3], ~a.data[3]);
}
 
TEST(uint256, LogicNot)
{
    uint256_t a{ 1, 0, 0, 0 };
 
    bool b = !a;
 
    EXPECT_EQ(b, false);
 
    uint256_t c{ 0, 0, 0, 0 };
 
    EXPECT_EQ(!c, true);
}
 
TEST(uint256, Equality)
{
    uint256_t a{ 1, 0, 0, 0 };
    uint256_t b{ 1, 0, 0, 0 };
    EXPECT_EQ(a == b, true);
 
    a = uint256_t{ 0, 1, 0, 0 };
    EXPECT_EQ(a == b, false);
 
    a = uint256_t{ 0, 0, 1, 0 };
    EXPECT_EQ(a == b, false);
 
    a = uint256_t{ 0, 0, 0, 1 };
    EXPECT_EQ(a == b, false);
 
    a = uint256_t{ 555, 0, 0, 1 };
    b = uint256_t{ 535, 0, 0, 1 };
    EXPECT_EQ(a == b, false);
}
 
TEST(uint256, NotEqual)
{
    uint256_t a{ 1, 0, 0, 0 };
    uint256_t b{ 1, 0, 0, 0 };
    EXPECT_EQ(a != b, false);
 
    a = uint256_t{ 0, 1, 0, 0 };
    EXPECT_EQ(a != b, true);
 
    a = uint256_t{ 0, 0, 1, 0 };
    EXPECT_EQ(a != b, true);
 
    a = uint256_t{ 0, 0, 0, 1 };
    EXPECT_EQ(a != b, true);
 
    a = uint256_t{ 555, 0, 0, 1 };
    b = uint256_t{ 535, 0, 0, 1 };
    EXPECT_EQ(a != b, true);
}
 
TEST(uint256, GreaterThan)
{
    constexpr uint256_t a{ UINT64_MAX, UINT64_MAX, UINT64_MAX, UINT64_MAX };
    constexpr uint256_t b{ UINT64_MAX, UINT64_MAX, UINT64_MAX, UINT64_MAX };
    EXPECT_EQ(a > b, false);
 
    constexpr uint256_t c = uint256_t{ UINT64_MAX, UINT64_MAX, UINT64_MAX, UINT64_MAX - 1 };
    EXPECT_EQ(a > c, true);
 
    constexpr uint256_t d = uint256_t{ UINT64_MAX, UINT64_MAX, UINT64_MAX - 1, UINT64_MAX };
    EXPECT_EQ(a > d, true);
 
    constexpr uint256_t e = uint256_t{ UINT64_MAX, UINT64_MAX - 1, UINT64_MAX, UINT64_MAX };
    EXPECT_EQ(a > e, true);
 
    constexpr uint256_t f = uint256_t{ UINT64_MAX - 1, UINT64_MAX, UINT64_MAX, UINT64_MAX };
    EXPECT_EQ(a > f, true);
}
 
TEST(uint256, GreaterThanOrEqual)
{
    uint256_t a{ UINT64_MAX, UINT64_MAX, UINT64_MAX, UINT64_MAX - 1 };
    uint256_t b{ UINT64_MAX, UINT64_MAX, UINT64_MAX, UINT64_MAX };
    EXPECT_EQ(a >= b, false);
 
    b = uint256_t{ UINT64_MAX, UINT64_MAX, UINT64_MAX, UINT64_MAX - 1 };
    EXPECT_EQ(a > b, false);
    EXPECT_EQ(a >= b, true);
 
    b = uint256_t{ UINT64_MAX, UINT64_MAX, UINT64_MAX - 1, UINT64_MAX };
    EXPECT_EQ(a >= b, false);
 
    a = uint256_t{ UINT64_MAX, UINT64_MAX - 1, UINT64_MAX - 1, UINT64_MAX };
    EXPECT_EQ(a >= b, false);
 
    b = uint256_t{ UINT64_MAX - 1, UINT64_MAX, UINT64_MAX, UINT64_MAX };
    EXPECT_EQ(a >= b, false);
}
 
TEST(uint256, ToFromBuffer)
{
    uint256_t a{ 1, 2, 3, 4 };
    auto buf = to_buffer(a);
    auto b = from_buffer<uint256_t>(buf);
    EXPECT_EQ(a, b);
}
 
// operator bool: verify all limbs are checked (not just data[0])
TEST(uint256, BoolConversion)
{
    EXPECT_FALSE(static_cast<bool>(uint256_t(0)));
    EXPECT_TRUE(static_cast<bool>(uint256_t(1)));
    // These cases caught the old bug where only data[0] was checked
    EXPECT_TRUE(static_cast<bool>(uint256_t{ 0, 1, 0, 0 }));
    EXPECT_TRUE(static_cast<bool>(uint256_t{ 0, 0, 1, 0 }));
    EXPECT_TRUE(static_cast<bool>(uint256_t{ 0, 0, 0, 1 }));
}
 
// operator uint128_t: verify both lower limbs are preserved
TEST(uint256, Uint128Conversion)
{
    constexpr uint256_t a{ 0xaaaaaaaaaaaaaaaa, 0xbbbbbbbbbbbbbbbb, 0xcccccccccccccccc, 0xdddddddddddddddd };
    auto lo128 = static_cast<uint128_t>(a);
    EXPECT_EQ(static_cast<uint64_t>(lo128), 0xaaaaaaaaaaaaaaaa);
    EXPECT_EQ(static_cast<uint64_t>(lo128 >> 64), 0xbbbbbbbbbbbbbbbb);
 
    // Verify const objects use the correct overload (not the integral template)
    const uint256_t b{ 0x1111111111111111, 0x2222222222222222, 0, 0 };
    auto b128 = static_cast<uint128_t>(b);
    EXPECT_EQ(static_cast<uint64_t>(b128 >> 64), 0x2222222222222222);
}
 
// Addition with carry propagation across all limbs
TEST(uint256, AddCarryPropagation)
{
    // Carry from limb 0 to limb 1
    uint256_t a{ UINT64_MAX, 0, 0, 0 };
    uint256_t b{ 1, 0, 0, 0 };
    uint256_t c = a + b;
    EXPECT_EQ(c, (uint256_t{ 0, 1, 0, 0 }));
 
    // Carry propagates through all limbs
    uint256_t d{ UINT64_MAX, UINT64_MAX, UINT64_MAX, 0 };
    uint256_t e = d + uint256_t(1);
    EXPECT_EQ(e, (uint256_t{ 0, 0, 0, 1 }));
 
    // Full overflow wraps to zero
    uint256_t f{ UINT64_MAX, UINT64_MAX, UINT64_MAX, UINT64_MAX };
    uint256_t g = f + uint256_t(1);
    EXPECT_EQ(g, uint256_t(0));
}
 
// mul_extended: verify full 512-bit product is correct
TEST(uint256, MulExtended)
{
    // Simple case: known product
    uint256_t a{ 0, 0, 0, 1 }; // 2^192
    uint256_t b{ 0, 0, 0, 1 }; // 2^192
    auto [lo, hi] = a.mul_extended(b);
    // 2^192 * 2^192 = 2^384, which is hi.data[2] bit 0
    EXPECT_EQ(lo, uint256_t(0));
    EXPECT_EQ(hi, (uint256_t{ 0, 0, 1, 0 }));
 
    // Verify with random values
    a = engine.get_random_uint256();
    b = engine.get_random_uint256();
    auto [ab_lo, ab_hi] = a.mul_extended(b);
 
    // Truncated product should match low half
    EXPECT_EQ(a * b, ab_lo);
 
    // Verify commutativity
    auto [ba_lo, ba_hi] = b.mul_extended(a);
    EXPECT_EQ(ab_lo, ba_lo);
    EXPECT_EQ(ab_hi, ba_hi);
 
    // Verify hi is zero when inputs are small
    uint256_t small_a{ 0xFFFFFFFF, 0, 0, 0 };
    uint256_t small_b{ 0xFFFFFFFF, 0, 0, 0 };
    auto [sm_lo, sm_hi] = small_a.mul_extended(small_b);
    EXPECT_EQ(sm_hi, uint256_t(0));
    EXPECT_EQ(sm_lo, small_a * small_b);
}
 
// Single-limb divmod
TEST(uint256, DivModSingleLimb)
{
    for (size_t i = 0; i < 64; ++i) {
        uint256_t a = engine.get_random_uint256();
        uint64_t b = engine.get_random_uint256().data[0];
        if (b == 0) {
            b = 1;
        }
        auto [q, r] = a.divmod(b);
        // Verify roundtrip: q * b + r == a
        uint256_t reconstructed = q * uint256_t(b) + uint256_t(r);
        EXPECT_EQ(reconstructed, a);
        // Remainder must be less than divisor
        EXPECT_LT(r, b);
    }
}
 
// slice
TEST(uint256, Slice)
{
    constexpr uint256_t a{ 0xaaaaaaaaaaaaaaaa, 0xbbbbbbbbbbbbbbbb, 0xcccccccccccccccc, 0xdddddddddddddddd };
 
    // Slice bottom 64 bits
    uint256_t bottom = a.slice(0, 64);
    EXPECT_EQ(bottom, uint256_t(0xaaaaaaaaaaaaaaaa));
 
    // Slice bits [64, 128)
    uint256_t mid = a.slice(64, 128);
    EXPECT_EQ(mid, uint256_t(0xbbbbbbbbbbbbbbbb));
 
    // Slice across limb boundary [32, 96)
    uint256_t cross = a.slice(32, 96);
    uint256_t expected = (a >> 32) & ((uint256_t(1) << 64) - 1);
    EXPECT_EQ(cross, expected);
 
    // Full slice
    uint256_t full = a.slice(0, 256);
    EXPECT_EQ(full, a);
}
 
// pow
TEST(uint256, Pow)
{
    // x^0 = 1
    uint256_t a{ 12345, 0, 0, 0 };
    EXPECT_EQ(a.pow(uint256_t(0)), uint256_t(1));
 
    // x^1 = x
    EXPECT_EQ(a.pow(uint256_t(1)), a);
 
    // 0^n = 0 for n > 0
    EXPECT_EQ(uint256_t(0).pow(uint256_t(5)), uint256_t(0));
 
    // 2^10 = 1024
    EXPECT_EQ(uint256_t(2).pow(uint256_t(10)), uint256_t(1024));
 
    // 3^20 = 3486784401
    EXPECT_EQ(uint256_t(3).pow(uint256_t(20)), uint256_t(3486784401ULL));
 
    // Verify a^2 == a * a for random value
    uint256_t b = engine.get_random_uint256();
    EXPECT_EQ(b.pow(uint256_t(2)), b * b);
 
    // Verify a^3 == a * a * a
    EXPECT_EQ(b.pow(uint256_t(3)), b * b * b);
}