MRVarBigInt.h

Go to the documentation of this file.

#pragma once
 
#include "MRMeshFwd.h"
#include "MRBuffer.h"
#include "MRFastInt.h"
#include "MRFastInt128.h"
#include <MRPch/MRBindingMacros.h>
#include <algorithm>
#include <array>
#include <cassert>
#include <compare>
#include <cstdint>
#include <variant>
 
namespace MR
{


class MR_BIND_IGNORE VarBigInt
{
public:
    VarBigInt() noexcept = default;

    VarBigInt( const VarBigInt & o ) { assignLimbs( o.sign_, o.limbs(), o.len_ ); }
    VarBigInt( VarBigInt && ) noexcept = default;
    VarBigInt & operator =( const VarBigInt & o ) { if ( this != &o ) assignLimbs( o.sign_, o.limbs(), o.len_ ); return *this; }
    VarBigInt & operator =( VarBigInt && ) noexcept = default;

    VarBigInt( std::int64_t v )
    {
        if ( v == 0 )
            return;
        const std::uint64_t m = v < 0 ? ~std::uint64_t( v ) + 1 : std::uint64_t( v );
        assignLimbs( v < 0 ? -1 : 1, &m, 1 );
    }

    explicit VarBigInt( FastInt128 v )
    {
        if ( v == 0 )
            return;
        const FastUInt128 u = v < 0 ? FastUInt128( 0 ) - FastUInt128( v ) : FastUInt128( v );
        const std::uint64_t w[2] = { std::uint64_t( u ), std::uint64_t( u >> 64 ) };
        assignLimbs( v < 0 ? -1 : 1, w, magNorm( w, 2 ) );
    }

    template <int nBits>
    explicit VarBigInt( const FastInt<nBits> & v )
    {
        const int s = v.sign();
        if ( s == 0 )
            return;
        auto w = v.w; 
        if ( s < 0 )
        {
            std::uint64_t borrow = 0;
            for ( auto & x : w )
                x = detail::subBorrow64( 0, x, borrow );
        }
        assignLimbs( s, w.data(), magNorm( w.data(), w.size() ) );
    }

    [[nodiscard]] int sign() const noexcept { return sign_; }
 
    [[nodiscard]] VarBigInt operator -() const
    {
        VarBigInt res = *this;
        res.sign_ = -res.sign_;
        return res;
    }
 
    VarBigInt & operator +=( const VarBigInt & b ) { return *this = *this + b; }
    VarBigInt & operator -=( const VarBigInt & b ) { return *this = *this - b; }
 
    [[nodiscard]] friend VarBigInt operator +( const VarBigInt & a, const VarBigInt & b )
    {
        if ( a.sign_ == 0 )
            return b;
        if ( b.sign_ == 0 )
            return a;
        if ( a.sign_ == b.sign_ )
            return make( a.sign_, std::max( a.len_, b.len_ ) + 1, false,
                [&]( std::uint64_t * out ) { return magAdd( a.limbs(), a.len_, b.limbs(), b.len_, out ); } );
        const int c = magCmp( a.limbs(), a.len_, b.limbs(), b.len_ );
        if ( c == 0 )
            return VarBigInt{}; 
        if ( c > 0 )
            return make( a.sign_, a.len_, false,
                [&]( std::uint64_t * out ) { return magSub( a.limbs(), a.len_, b.limbs(), b.len_, out ); } );
        return make( b.sign_, b.len_, false,
            [&]( std::uint64_t * out ) { return magSub( b.limbs(), b.len_, a.limbs(), a.len_, out ); } );
    }
 
    [[nodiscard]] friend VarBigInt operator -( const VarBigInt & a, const VarBigInt & b ) { return a + ( -b ); }
 
    [[nodiscard]] friend VarBigInt operator *( const VarBigInt & a, const VarBigInt & b )
    {
        if ( a.sign_ == 0 || b.sign_ == 0 )
            return VarBigInt{};
        return make( a.sign_ * b.sign_, a.len_ + b.len_, true,
            [&]( std::uint64_t * out ) { return magMul( a.limbs(), a.len_, b.limbs(), b.len_, out ); } );
    }
 
    [[nodiscard]] friend bool operator ==( const VarBigInt & a, const VarBigInt & b ) noexcept
    {
        if ( a.sign_ != b.sign_ || a.len_ != b.len_ )
            return false;
        const std::uint64_t * pa = a.limbs();
        const std::uint64_t * pb = b.limbs();
        for ( std::size_t i = 0; i < a.len_; ++i )
            if ( pa[i] != pb[i] )
                return false;
        return true;
    }
 
    [[nodiscard]] friend std::strong_ordering operator <=>( const VarBigInt & a, const VarBigInt & b ) noexcept
    {
        if ( a.sign_ != b.sign_ )
            return a.sign_ <=> b.sign_;
        if ( a.sign_ == 0 )
            return std::strong_ordering::equal;
        const int c = magCmp( a.limbs(), a.len_, b.limbs(), b.len_ ); 
        const int r = a.sign_ > 0 ? c : -c;                          
        return r <=> 0;
    }
 
private:
    int sign_ = 0;         
    std::size_t len_ = 0;  
    std::variant<Buffer<std::uint64_t>, std::array<std::uint64_t, 2>> mag_{ std::array<std::uint64_t, 2>{} };

    [[nodiscard]] const std::uint64_t * limbs() const noexcept
    {
        return std::visit( []( const auto & s ) -> const std::uint64_t * { return s.data(); }, mag_ );
    }

    void assignLimbs( int sign, const std::uint64_t * p, std::size_t n )
    {
        if ( n == 0 )
        {
            sign_ = 0;
            len_ = 0;
            mag_.emplace<1>(); 
            return;
        }
        sign_ = sign;
        len_ = n;
        if ( n <= 2 )
        {
            std::array<std::uint64_t, 2> a{ 0, 0 };
            for ( std::size_t i = 0; i < n; ++i )
                a[i] = p[i];
            mag_.emplace<1>( a );
        }
        else
        {
            Buffer<std::uint64_t> b( n );
            for ( std::size_t i = 0; i < n; ++i )
                b[i] = p[i];
            mag_.emplace<0>( std::move( b ) );
        }
    }

    template <typename Kernel>
    [[nodiscard]] static VarBigInt make( int sign, std::size_t ub, bool zeroInit, Kernel kernel )
    {
        VarBigInt res;
        if ( sign == 0 )
            return res;
        if ( ub <= 2 )
        {
            std::array<std::uint64_t, 2> tmp{ 0, 0 };
            const std::size_t n = kernel( tmp.data() );
            assert( n <= 2 ); 
            if ( n == 0 )
                return res; 
            res.sign_ = sign;
            res.len_ = n;
            res.mag_.emplace<1>( tmp );
        }
        else
        {
            Buffer<std::uint64_t> buf( ub );
            if ( zeroInit )
                std::fill( buf.data(), buf.data() + ub, std::uint64_t( 0 ) );
            const std::size_t n = kernel( buf.data() );
            if ( n <= 2 )
                res.assignLimbs( sign, buf.data(), n ); 
            else
            {
                res.sign_ = sign;
                res.len_ = n;
                res.mag_.emplace<0>( std::move( buf ) );
            }
        }
        return res;
    }

    [[nodiscard]] static std::size_t magNorm( const std::uint64_t * p, std::size_t n ) noexcept
    {
        while ( n > 0 && p[n - 1] == 0 )
            --n;
        return n;
    }

    [[nodiscard]] static int magCmp( const std::uint64_t * a, std::size_t na, const std::uint64_t * b, std::size_t nb ) noexcept
    {
        if ( na != nb )
            return na < nb ? -1 : 1;
        for ( std::size_t i = na; i-- > 0; )
            if ( a[i] != b[i] )
                return a[i] < b[i] ? -1 : 1;
        return 0;
    }

    static std::size_t magAdd( const std::uint64_t * a, std::size_t na, const std::uint64_t * b, std::size_t nb, std::uint64_t * out )
    {
        const std::size_t n = std::max( na, nb );
        std::uint64_t carry = 0;
        for ( std::size_t i = 0; i < n; ++i )
        {
            const std::uint64_t x = i < na ? a[i] : 0;
            const std::uint64_t y = i < nb ? b[i] : 0;
            out[i] = detail::addCarry64( x, y, carry );
        }
        std::size_t m = n;
        if ( carry )
            out[m++] = carry;
        return m; 
    }

    static std::size_t magSub( const std::uint64_t * a, std::size_t na, const std::uint64_t * b, std::size_t nb, std::uint64_t * out )
    {
        std::uint64_t borrow = 0;
        for ( std::size_t i = 0; i < na; ++i )
        {
            const std::uint64_t x = a[i];
            const std::uint64_t y = i < nb ? b[i] : 0;
            out[i] = detail::subBorrow64( x, y, borrow );
        }
        return magNorm( out, na ); 
    }

    static std::size_t magMul( const std::uint64_t * a, std::size_t na, const std::uint64_t * b, std::size_t nb, std::uint64_t * out )
    {
        for ( std::size_t i = 0; i < na; ++i ) 
        {
            std::uint64_t carry = 0;
            for ( std::size_t j = 0; j < nb; ++j )
            {
                const FastUInt128 t = FastUInt128( a[i] ) * FastUInt128( b[j] )
                                    + FastUInt128( out[i + j] ) + FastUInt128( carry );
                out[i + j] = std::uint64_t( t );
                carry = std::uint64_t( t >> 64 );
            }
            out[i + nb] += carry; 
        }
        return magNorm( out, na + nb );
    }
};

 
}