uint128_t UnitClassFile

 avatar
unknown
c_cpp
a year ago
28 kB
4
Indexable
#include "UnsignedInteger128Bit.hpp"

namespace TwilightDream::WideIntegers
{
	const uint128_t uint128_0( 0 );
	const uint128_t uint128_1( 1 );

	uint128_t::uint128_t( const std::string& characters, uint8_t base )
	{
		from_string( characters.c_str(), characters.size(), base );
	}

	uint128_t::uint128_t( const char* characters, const std::size_t size, uint8_t base )
	{
		from_string( characters, size, base );
	}

	uint128_t::uint128_t( const bool& b ) : uint128_t( ( uint8_t )b ) {}

	uint128_t::~uint128_t()
	{
		this->high_bits = ZERO_BITS;
		this->low_bits = ZERO_BITS;
	}

	void uint128_t::from_string( const char* characters, std::size_t size, uint8_t base )
	{
		if ( ( characters == nullptr ) || !size || ( characters[ 0 ] == '\x00' ) )
		{
			low_bits = high_bits = 0;
			return;
		}

		while ( *characters && size && std::isspace( *characters ) )
		{
			++characters;
			size--;
		}

		// no prefixes
		switch ( base )
		{
			case 16:
				_initialize_with_hexadecimal( characters, size );
				break;
			case 10:
				_initialize_with_decimal( characters, size );
				break;
			case 8:
				_initialize_with_octal( characters, size );
				break;
			case 2:
				_initialize_with_binary( characters, size );
				break;
			default:
				throw std::invalid_argument("");
				break;
		}
	}

	void uint128_t::_initialize_with_hexadecimal( const char* characters, std::size_t len )
	{
		// 2**128 = 0x100000000000000000000000000000000.
		static const std::size_t MAX_SIZE = 32;

		low_bits = high_bits = 0;
		if ( !characters || !len )
		{
			return;
		}

		const std::size_t max_size = std::min( len, MAX_SIZE );
		const std::size_t starting_index = ( MAX_SIZE < len ) ? ( len - MAX_SIZE ) : 0;
		const std::size_t double_lower = sizeof( low_bits ) * 2;
		const std::size_t lower_size = ( max_size >= double_lower ) ? double_lower : max_size;
		const std::size_t upper_size = ( max_size >= double_lower ) ? ( max_size - double_lower ) : 0;

		std::stringstream lower_s, upper_s;
		upper_s << std::hex << std::string( characters + starting_index, upper_size );
		lower_s << std::hex << std::string( characters + starting_index + upper_size, lower_size );

		// should check for errors
		upper_s >> high_bits;
		lower_s >> low_bits;
	}

	void uint128_t::_initialize_with_decimal( const char* characters, std::size_t size )
	{
		// 2**128 = 340282366920938463463374607431768211456.
		static const std::size_t MAX_SIZE = 39;

		low_bits = high_bits = 0;
		if ( !characters || !size )
		{
			return;
		}

		const std::size_t max_size = std::min( size, MAX_SIZE );
		const std::size_t starting_index = ( MAX_SIZE < size ) ? ( size - MAX_SIZE ) : 0;
		characters += starting_index;

		for ( std::size_t i = 0; *characters && ( '0' <= *characters ) && ( *characters <= '9' ) && ( i < max_size ); ++characters, ++i )
		{
			*this *= 10;
			*this += *characters - '0';
		}
	}

	void uint128_t::_initialize_with_octal( const char* characters, std::size_t size )
	{
		// 2**128 = 0o4000000000000000000000000000000000000000000.
		static const std::size_t MAX_SIZE = 43;

		low_bits = high_bits = 0;
		if ( !characters || !size )
		{
			return;
		}

		const std::size_t max_size = std::min( size, MAX_SIZE );
		const std::size_t starting_index = ( MAX_SIZE < size ) ? ( size - MAX_SIZE ) : 0;
		characters += starting_index;

		for ( std::size_t i = 0; *characters && ( '0' <= *characters ) && ( *characters <= '7' ) && ( i < max_size ); ++characters, ++i )
		{
			*this *= 8;
			*this += *characters - '0';
		}
	}

	void uint128_t::_initialize_with_binary( const char* characters, std::size_t size )
	{
		// 2**128 = 0b100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.
		static const std::size_t MAX_SIZE = 128;

		low_bits = high_bits = 0;
		if ( !characters || !size )
		{
			return;
		}

		const std::size_t max_size = std::min( size, MAX_SIZE );
		const std::size_t starting_index = ( MAX_SIZE < size ) ? ( size - MAX_SIZE ) : 0;
		const std::size_t eight_lower = sizeof( low_bits ) * 8;
		const std::size_t lower_size = ( max_size >= eight_lower ) ? eight_lower : max_size;
		const std::size_t upper_size = ( max_size >= eight_lower ) ? ( max_size - eight_lower ) : 0;
		characters += starting_index;

		for ( std::size_t i = 0; *characters && ( '0' <= *characters ) && ( *characters <= '1' ) && ( i < upper_size ); ++characters, ++i )
		{
			high_bits <<= 1;
			high_bits |= *characters - '0';
		}

		for ( std::size_t i = 0; *characters && ( '0' <= *characters ) && ( *characters <= '1' ) && ( i < lower_size ); ++characters, ++i )
		{
			low_bits <<= 1;
			low_bits |= *characters - '0';
		}
	}

	uint128_t& uint128_t::operator=( const bool& other )
	{
		high_bits = 0;
		low_bits = other;
		return *this;
	}

	void uint128_t::import_bytes( const std::vector<uint8_t>& bytes )
	{
		size_t byte_counter = 0;
		std::size_t byte_amount = std::min( bytes.size(), (size_t)16 );
		auto ConvertFromVector = [&byte_counter, byte_amount](const std::vector<uint8_t>& bytes, uint64_t& value) -> void
		{
			value = 0;
			while( byte_counter < byte_amount )
			{
				value <<= 8;
				value |= bytes[byte_counter];
				byte_counter++;
			}
		};

		ConvertFromVector(bytes, high_bits);
		ConvertFromVector(bytes, low_bits);
	}

	void uint128_t::export_bytes( std::vector<uint8_t>& bytes ) const
	{
		auto ConvertToVector = [](std::vector<uint8_t> & result, const uint64_t& value) -> void
		{
			result.push_back(static_cast<uint8_t>(value >> 56));
			result.push_back(static_cast<uint8_t>(value >> 48));
			result.push_back(static_cast<uint8_t>(value >> 40));
			result.push_back(static_cast<uint8_t>(value >> 32));
			result.push_back(static_cast<uint8_t>(value >> 24));
			result.push_back(static_cast<uint8_t>(value >> 16));
			result.push_back(static_cast<uint8_t>(value >> 8));
			result.push_back(static_cast<uint8_t>(value));
		};

		ConvertToVector(bytes, high_bits);
		ConvertToVector(bytes, low_bits);
	}

	uint128_t::operator bool() const
	{
		return ( bool )( high_bits | low_bits );
	}

	uint128_t::operator uint8_t() const
	{
		return ( uint8_t )low_bits;
	}

	uint128_t::operator uint16_t() const
	{
		return ( uint16_t )low_bits;
	}

	uint128_t::operator uint32_t() const
	{
		return ( uint32_t )low_bits;
	}

	uint128_t::operator uint64_t() const
	{
		return ( uint64_t )low_bits;
	}

	/*
		Basic bit manipulation function (BMF)
	*/

	// Check if all bits are set
	bool uint128_t::check_all_bits() const
	{
		if ( this->high_bits == ONE_BITS && this->low_bits == ONE_BITS )
		{
			return true;
		}
		return false;
	}

	// Check if any bits are set
	bool uint128_t::check_any_bit() const
	{
		if ( this->high_bits != ZERO_BITS || this->low_bits != ZERO_BITS )
		{
			return true;
		}
		return false;
	}

	// Check if no bits are set
	bool uint128_t::check_none_bits() const
	{
		if ( this->high_bits == ZERO_BITS && this->low_bits == ZERO_BITS )
		{
			return true;
		}
		return false;
	}

	void uint128_t::swap( uint128_t& other )
	{
		std::swap( this->high_bits, other.high_bits );
		std::swap( this->low_bits, other.low_bits );
	}

	void uint128_t::change_all_bits( bool value )
	{
		this->high_bits = value ? ONE_BITS : ZERO_BITS;
		this->low_bits = value ? ONE_BITS : ZERO_BITS;
	}

	void uint128_t::change_high_bits( uint64_t value )
	{
		this->high_bits = value;
	}

	void uint128_t::change_low_bits( uint64_t value )
	{
		this->low_bits = value;
	}

	void uint128_t::set_bit( size_t position, bool value )
	{
		if ( position >= BITS_SIZE )
		{
			return;
		}

		if ( position >= BITS_SIZE_HALF )
		{
			if ( value )
			{
				this->high_bits |= ( BIT_ONE << ( position - BITS_SIZE_HALF ) );
			}
			else
			{
				this->high_bits &= ~( BIT_ONE << ( position - BITS_SIZE_HALF ) );
			}
		}
		else
		{
			if ( value )
			{
				this->low_bits |= ( BIT_ONE << position );
			}
			else
			{
				this->low_bits &= ~( BIT_ONE << position );
			}
		}
	}

	bool uint128_t::get_bit( size_t position )
	{
		if ( position >= BITS_SIZE )
		{
			return false;
		}

		if ( position >= BITS_SIZE_HALF )
		{
			return ( this->high_bits & ( BIT_ONE << ( position - BITS_SIZE_HALF ) ) ) != ZERO_BITS;
		}
		else
		{
			return ( this->low_bits & ( BIT_ONE << position ) ) != ZERO_BITS;
		}
	}

	void uint128_t::bit_not_xor( const uint128_t& other )
	{
		this->high_bits ^= ~other.high_bits;
		this->low_bits ^= ~other.low_bits;
	}

	void uint128_t::bit_not_and( const uint128_t& other )
	{
		this->high_bits &= ~other.high_bits;
		this->low_bits &= ~other.low_bits;
	}

	void uint128_t::bit_not_xor( uint64_t other )
	{
		this->low_bits ^= ~other;
	}

	void uint128_t::bit_not_and( uint64_t other )
	{
		this->low_bits &= ~other;
	}

	/*
		Logical Operators
	*/
	bool uint128_t::operator!() const
	{
		return !( bool )( high_bits | low_bits );
	}

	bool uint128_t::operator&&( const uint128_t& other ) const
	{
		return ( ( bool )*this && other );
	}

	bool uint128_t::operator||( const uint128_t& other ) const
	{
		return ( ( bool )*this || other );
	}

	/*
		Comparison Operators
	*/
	bool uint128_t::operator==( const uint128_t& other ) const
	{
		return ( ( high_bits == other.high_bits ) && ( low_bits == other.low_bits ) );
	}

	bool uint128_t::operator!=( const uint128_t& other ) const
	{
		return ( ( high_bits != other.high_bits ) || ( low_bits != other.low_bits ) );
	}

	bool uint128_t::operator>( const uint128_t& other ) const
	{
		if ( high_bits == other.high_bits )
		{
			return ( low_bits > other.low_bits );
		}
		return ( high_bits > other.high_bits );
	}

	bool uint128_t::operator<( const uint128_t& other ) const
	{
		if ( high_bits == other.high_bits )
		{
			return ( low_bits < other.low_bits );
		}
		return ( high_bits < other.high_bits );
	}

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

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

	/*
		Internal helper functions
	*/
	uint64_t uint128_t::population_count() const
	{
		uint64_t low_population_count = low_bits;
		uint64_t high_population_count = high_bits;
		auto	 population_count_64bit = [ &low_population_count, &high_population_count ]() -> uint64_t {
			low_population_count -= ( low_population_count >> 1 ) & 0x5555555555555555;
			low_population_count = ( low_population_count & 0x3333333333333333 ) + ( ( low_population_count >> 2 ) & 0x3333333333333333 );
			low_population_count = ( low_population_count + ( low_population_count >> 4 ) ) & 0x0f0f0f0f0f0f0f0f;
			low_population_count = ( low_population_count * 0x0101010101010101 ) >> 56;

			high_population_count -= ( high_population_count >> 1 ) & 0x5555555555555555;
			high_population_count = ( high_population_count & 0x3333333333333333 ) + ( ( high_population_count >> 2 ) & 0x3333333333333333 );
			high_population_count = ( high_population_count + ( high_population_count >> 4 ) ) & 0x0f0f0f0f0f0f0f0f;
			high_population_count = ( high_population_count * 0x0101010101010101 ) >> 56;

			return low_population_count + high_population_count;
		};

		return population_count_64bit();
	}

	uint32_t uint128_t::counter_one_bits_from_left() const
	{
		uint32_t result = 0;
		if ( this->high_bits )
		{
			result = 64;
			uint64_t high = this->high_bits;
			//For each bit with high bits
			while ( high )
			{
				high >>= 1;
				result++;
			}
		}
		else
		{
			uint64_t low = this->low_bits;
			while ( low )
			{
				low >>= 1;
				result++;
			}
		}

		return result;
	}

	/*
		Binary bitwise operator
	*/
	uint128_t uint128_t::operator&( const uint128_t& other ) const
	{
		return uint128_t( high_bits & other.high_bits, low_bits & other.low_bits );
	}

	uint128_t& uint128_t::operator&=( const uint128_t& other )
	{
		high_bits &= other.high_bits;
		low_bits &= other.low_bits;
		return *this;
	}

	uint128_t uint128_t::operator|( const uint128_t& other ) const
	{
		return uint128_t( high_bits | other.high_bits, low_bits | other.low_bits );
	}

	uint128_t& uint128_t::operator|=( const uint128_t& other )
	{
		high_bits |= other.high_bits;
		low_bits |= other.low_bits;
		return *this;
	}

	uint128_t uint128_t::operator^( const uint128_t& other ) const
	{
		return uint128_t( high_bits ^ other.high_bits, low_bits ^ other.low_bits );
	}

	uint128_t& uint128_t::operator^=( const uint128_t& other )
	{
		high_bits ^= other.high_bits;
		low_bits ^= other.low_bits;
		return *this;
	}

	uint128_t uint128_t::operator~() const
	{
		return uint128_t( ~high_bits, ~low_bits );
	}

	uint128_t uint128_t::operator<<( const uint128_t& shift_amount ) const
	{
		const uint64_t shift = shift_amount.low_bits;
		if ( ( ( bool )shift_amount.high_bits ) || ( shift >= BITS_SIZE ) )
		{
			return uint128_0;
		}
		else if ( shift == BITS_SIZE_HALF )
		{
			return uint128_t( low_bits, BIT_ZERO );
		}
		else if ( shift == 0 )
		{
			return *this;
		}
		else if ( shift < BITS_SIZE_HALF )
		{
			return uint128_t( ( high_bits << shift ) + ( low_bits >> ( BITS_SIZE_HALF - shift ) ), low_bits << shift );
		}
		else if ( ( BITS_SIZE > shift ) && ( shift > BITS_SIZE_HALF ) )
		{
			return uint128_t( low_bits << ( shift - BITS_SIZE_HALF ), BIT_ZERO );
		}
		else
		{
			return uint128_0;
		}
	}

	uint128_t& uint128_t::operator<<=( const uint128_t& shift_amount )
	{
		*this = *this << shift_amount;
		return *this;
	}

	uint128_t uint128_t::operator>>( const uint128_t& shift_amount ) const
	{
		const uint64_t shift = shift_amount.low_bits;
		if ( ( ( bool )shift_amount.high_bits ) || ( shift >= BITS_SIZE ) )
		{
			return uint128_0;
		}
		else if ( shift == BITS_SIZE_HALF )
		{
			return uint128_t( BIT_ZERO, high_bits );
		}
		else if ( shift == 0 )
		{
			return *this;
		}
		else if ( shift < BITS_SIZE_HALF )
		{
			return uint128_t( high_bits >> shift, ( high_bits << ( BITS_SIZE_HALF - shift ) ) + ( low_bits >> shift ) );
		}
		else if ( ( BITS_SIZE > shift ) && ( shift > BITS_SIZE_HALF ) )
		{
			return uint128_t( BIT_ZERO, ( high_bits >> ( shift - BITS_SIZE_HALF ) ) );
		}
		else
		{
			return uint128_0;
		}
	}

	uint128_t& uint128_t::operator>>=( const uint128_t& shift_amount )
	{
		*this = *this >> shift_amount;
		return *this;
	}

	uint128_t operator<<( const bool& self, const uint128_t& other )
	{
		return uint128_t( self ) << other;
	}

	uint128_t operator<<( const uint8_t& self, const uint128_t& other )
	{
		return uint128_t( self ) << other;
	}

	uint128_t operator<<( const uint16_t& self, const uint128_t& other )
	{
		return uint128_t( self ) << other;
	}

	uint128_t operator<<( const uint32_t& self, const uint128_t& other )
	{
		return uint128_t( self ) << other;
	}

	uint128_t operator<<( const uint64_t& self, const uint128_t& other )
	{
		return uint128_t( self ) << other;
	}

	uint128_t operator<<( const int8_t& self, const uint128_t& other )
	{
		return uint128_t( self ) << other;
	}

	uint128_t operator<<( const int16_t& self, const uint128_t& other )
	{
		return uint128_t( self ) << other;
	}

	uint128_t operator<<( const int32_t& self, const uint128_t& other )
	{
		return uint128_t( self ) << other;
	}

	uint128_t operator<<( const int64_t& self, const uint128_t& other )
	{
		return uint128_t( self ) << other;
	}

	uint128_t operator>>( const bool& self, const uint128_t& other )
	{
		return uint128_t( self ) >> other;
	}

	uint128_t operator>>( const uint8_t& self, const uint128_t& other )
	{
		return uint128_t( self ) >> other;
	}

	uint128_t operator>>( const uint16_t& self, const uint128_t& other )
	{
		return uint128_t( self ) >> other;
	}

	uint128_t operator>>( const uint32_t& self, const uint128_t& other )
	{
		return uint128_t( self ) >> other;
	}

	uint128_t operator>>( const uint64_t& self, const uint128_t& other )
	{
		return uint128_t( self ) >> other;
	}

	uint128_t operator>>( const int8_t& self, const uint128_t& other )
	{
		return uint128_t( self ) >> other;
	}

	uint128_t operator>>( const int16_t& self, const uint128_t& other )
	{
		return uint128_t( self ) >> other;
	}

	uint128_t operator>>( const int32_t& self, const uint128_t& other )
	{
		return uint128_t( self ) >> other;
	}

	uint128_t operator>>( const int64_t& self, const uint128_t& other )
	{
		return uint128_t( self ) >> other;
	}


	/*
		Arithmetic Operators
	*/
	uint128_t uint128_t::operator+( const uint128_t& other ) const
	{
		return uint128_t( high_bits + other.high_bits + ( ( low_bits + other.low_bits ) < low_bits ), low_bits + other.low_bits );
	}

	uint128_t& uint128_t::operator+=( const uint128_t& other )
	{
		high_bits += other.high_bits + ( ( low_bits + other.low_bits ) < low_bits );
		low_bits += other.low_bits;
		return *this;
	}

	uint128_t uint128_t::operator-( const uint128_t& other ) const
	{
		return uint128_t( high_bits - other.high_bits - ( ( low_bits - other.low_bits ) > low_bits ), low_bits - other.low_bits );
	}

	uint128_t& uint128_t::operator-=( const uint128_t& other )
	{
		*this = *this - other;
		return *this;
	}

	uint128_t& uint128_t::operator++()
	{
		return *this += uint128_1;
	}

	uint128_t uint128_t::operator++( int )
	{
		uint128_t temp( *this );
		++*this;
		return temp;
	}

	uint128_t& uint128_t::operator--()
	{
		return *this -= uint128_1;
	}

	uint128_t uint128_t::operator--( int )
	{
		uint128_t temp( *this );
		--*this;
		return temp;
	}

	uint128_t uint128_t::operator+() const{
		return *this;
	}

	uint128_t uint128_t::operator-() const{
		return ~*this + uint128_1;
	}

	uint128_t uint128_t::operator*( const uint128_t& other ) const
	{
		return multiplication( *this, other );
	}

	uint128_t& uint128_t::operator*=( const uint128_t& other )
	{
		*this = *this * other;
		return *this;
	}

	uint128_t uint128_t::operator/( const uint128_t& other ) const
	{
		return division( *this, other ).first;
	}

	uint128_t& uint128_t::operator/=( const uint128_t& other )
	{
		*this = *this / other;
		return *this;
	}

	uint128_t uint128_t::operator%( const uint128_t& other ) const
	{
		return division( *this, other ).second;
	}

	uint128_t& uint128_t::operator%=( const uint128_t& other )
	{
		*this = *this % other;
		return *this;
	}

	/*
		Internal implementation of arithmetic operations
	*/

	uint128_t uint128_t::multiplication( const uint128_t& multiplied, const uint128_t& multiplier ) const
	{
		// Karatsuba algorithm
		constexpr uint64_t bit_mask = ( ONE_BITS >> BITS_SIZE_QUARTER );
		// split values into 4 32-bit parts
		uint64_t top[ 4 ] = { multiplied.high_bits >> BITS_SIZE_QUARTER, multiplied.high_bits & bit_mask, multiplied.low_bits >> BITS_SIZE_QUARTER, multiplied.low_bits & bit_mask };
		uint64_t bottom[ 4 ] = { multiplier.high_bits >> BITS_SIZE_QUARTER, multiplier.high_bits & bit_mask, multiplier.low_bits >> BITS_SIZE_QUARTER, multiplier.low_bits & bit_mask };
		uint64_t products[ 4 ][ 4 ];

		// multiply each component of the values
		for ( int y = 3; y > -1; y-- )
		{
			for ( int x = 3; x > -1; x-- )
			{
				products[ 3 - x ][ y ] = top[ x ] * bottom[ y ];
			}
		}

		// first row
		uint64_t fourth32 = ( products[ 0 ][ 3 ] & bit_mask );
		uint64_t third32 = ( products[ 0 ][ 2 ] & bit_mask ) + ( products[ 0 ][ 3 ] >> BITS_SIZE_QUARTER );
		uint64_t second32 = ( products[ 0 ][ 1 ] & bit_mask ) + ( products[ 0 ][ 2 ] >> BITS_SIZE_QUARTER );
		uint64_t first32 = ( products[ 0 ][ 0 ] & bit_mask ) + ( products[ 0 ][ 1 ] >> BITS_SIZE_QUARTER );

		// second row
		third32 += ( products[ 1 ][ 3 ] & bit_mask );
		second32 += ( products[ 1 ][ 2 ] & bit_mask ) + ( products[ 1 ][ 3 ] >> BITS_SIZE_QUARTER );
		first32 += ( products[ 1 ][ 1 ] & bit_mask ) + ( products[ 1 ][ 2 ] >> BITS_SIZE_QUARTER );

		// third row
		second32 += ( products[ 2 ][ 3 ] & bit_mask );
		first32 += ( products[ 2 ][ 2 ] & bit_mask ) + ( products[ 2 ][ 3 ] >> BITS_SIZE_QUARTER );

		// fourth row
		first32 += ( products[ 3 ][ 3 ] & bit_mask );

		// move carry to next digit
		third32 += fourth32 >> BITS_SIZE_QUARTER;
		second32 += third32 >> BITS_SIZE_QUARTER;
		first32 += second32 >> BITS_SIZE_QUARTER;

		// remove carry from current digit
		fourth32 &= bit_mask;
		third32 &= bit_mask;
		second32 &= bit_mask;
		first32 &= bit_mask;

		// combine components
		return uint128_t( ( first32 << BITS_SIZE_QUARTER ) | second32, ( third32 << BITS_SIZE_QUARTER ) | fourth32 );
	}

	std::pair<uint128_t, uint128_t> uint128_t::division( const uint128_t& dividend, const uint128_t& divisor ) const
	{
		// Check for division by zero
		if ( divisor == uint128_0 )
		{
			throw std::runtime_error( "Division by zero" );
		}

		// If the divisor is 1, the quotient is the dividend and the remainder is 0
		if ( divisor == uint128_1 )
		{
			return std::pair<uint128_t, uint128_t>( dividend, uint128_0 );
		}

		// If the dividend is 1, the quotient is 0 and the remainder is the 1
		if ( dividend == uint128_1 )
		{
			return std::pair<uint128_t, uint128_t>( uint128_0, uint128_1 );
		}

		//If the dividend equal to divisor
		if ( dividend == divisor )
		{
			return std::pair<uint128_t, uint128_t>( uint128_1, uint128_0 );
		}

		// If the dividend is 0, the quotient and remainder are both 0
		if ( ( dividend == uint128_0 ) || ( dividend < divisor ) )
		{
			return std::pair<uint128_t, uint128_t>( uint128_0, dividend );
		}

		std::pair<uint128_t, uint128_t> quotient_and_remainder( uint128_0, uint128_0 );

		for ( uint32_t bit_size = dividend.counter_one_bits_from_left(); bit_size > 0; bit_size-- )
		{
			quotient_and_remainder.first <<= uint128_1;
			quotient_and_remainder.second <<= uint128_1;

			if ( ( dividend >> ( bit_size - BIT_ONE ) ) & 1 )
			{
				++quotient_and_remainder.second;
			}

			if ( quotient_and_remainder.second >= divisor )
			{
				quotient_and_remainder.second -= divisor;
				++quotient_and_remainder.first;
			}
		}
		return quotient_and_remainder;
	}

	//The bit position of the highest valid bit.
	uint32_t uint128_t::get_most_significant_bit_index() const
	{
		if ( this->high_bits )
		{
			//For each bit with high bits
			for ( int index = BITS_SIZE - 1; index >= BITS_SIZE_HALF; index-- )
			{
				if ( this->high_bits & ( BIT_ONE << index ) )
				{
					return index + BITS_SIZE_HALF;
				}
			}
		}
		else
		{
			//For each bit with low bits
			for ( int index = BITS_SIZE_HALF - 1; index >= 0; index-- )
			{
				if ( this->low_bits & ( BIT_ONE << index ) )
				{
					return index;
				}
			}
		}
	}

	uint64_t& uint128_t::operator[]( size_t index )
	{
		index %= 2;
		if(index)
			return this->low_bits;
		else
			return this->high_bits;
	}

	// Donald Knuth's multi-precision unsigned integer division
	// Implement the algorithm in Knuth[The Art of Computer Programming] Book
	// https://raw.githubusercontent.com/hcs0/Hackers-Delight/master/divmnu.c.txt
	// https://raw.githubusercontent.com/hcs0/Hackers-Delight/master/divmnu64.c.txt
	std::pair<uint128_t, uint128_t> uint128_t::long_division( const uint128_t& dividend, const uint128_t& divisor ) const
	{
		// Check for division by zero
		if ( divisor == uint128_0 )
		{
			throw std::runtime_error( "Division by zero" );
		}

		// If the divisor is 1, the quotient is the dividend and the remainder is 0
		if ( divisor == uint128_1 )
		{
			return std::pair<uint128_t, uint128_t>( dividend, uint128_0 );
		}

		// If the dividend is 1, the quotient is 0 and the remainder is the 1
		if ( dividend == uint128_1 )
		{
			return std::pair<uint128_t, uint128_t>( uint128_0, uint128_1 );
		}

		//If the dividend equal to divisor
		if ( dividend == divisor )
		{
			return std::pair<uint128_t, uint128_t>( uint128_1, uint128_0 );
		}

		// If the dividend is 0, the quotient and remainder are both 0
		if ( ( dividend == uint128_0 ) || ( dividend < divisor ) )
		{
			return std::pair<uint128_t, uint128_t>( uint128_0, dividend );
		}

		std::pair<uint128_t, uint128_t> quotient_and_remainder( uint128_0, uint128_0 );

		//Special case detection in order to simplify arithmetic.
		if ( this->high_bits == ZERO_BITS && divisor.high_bits == ZERO_BITS )
		{
			if ( this->low_bits < divisor.low_bits )
			{
				quotient_and_remainder.first.low_bits = BIT_ZERO;
				quotient_and_remainder.second.low_bits = this->low_bits;
			}
			else
			{
				quotient_and_remainder.first.low_bits = this->low_bits / divisor.low_bits;
				quotient_and_remainder.second.low_bits = this->low_bits % divisor.low_bits;
			}

			return quotient_and_remainder;
		}

		// 1. Initialization and normalization
		if ( dividend.high_bits < divisor.high_bits || ( dividend.high_bits == divisor.high_bits && dividend.low_bits < divisor.low_bits ) )
		{
			quotient_and_remainder.first = uint128_0;
			quotient_and_remainder.second = dividend.high_bits;
			return quotient_and_remainder;
		}

		// Bit shift left to normalize
		int64_t	  shift = get_most_significant_bit_index();	 // count leading zeros of the most significant word of the divisor
		uint128_t u = *this << shift;						 // normalized dividend
		uint128_t v = divisor << shift;						 // normalized divisor
		uint64_t  qhat;										 // estimated quotient digit
		uint64_t  rhat;										 // remainder
		uint64_t  borrow;									 // borrow flag
		uint64_t  carry;									 // carry flag
		int64_t	  n = 2;									 // number of words in the divisor
		int64_t	  m = 2;									 // number of words in the dividend minus n

		// 2. Main loop
		for ( int j = m; j >= 0; j-- )
		{
			// Estimate quotient
			qhat = ( u.high_bits == v.high_bits ) ? ONE_BITS : ( u.high_bits * ONE_BITS + u.low_bits ) / v.high_bits;
			rhat = ( u.high_bits * ONE_BITS + u.low_bits ) - qhat * v.high_bits;
			while ( qhat >= ONE_BITS || qhat * v.low_bits > rhat * ONE_BITS + u[ j ] )
			{
				qhat--;
				rhat += v.high_bits;
				if ( rhat >= ONE_BITS )
					break;
			}

			// Multiply and subtract
			borrow = BIT_ZERO;
			for ( int i = 0; i < n; i++ )
			{
				carry = qhat * v[ i ];
				carry += borrow;
				borrow = ( carry < borrow ) ? BIT_ONE : BIT_ZERO;
				carry += u[ i + j ];
				borrow += ( carry < u[ i + j ] ) ? BIT_ONE : BIT_ZERO;
				u[ i + j ] = carry;
			}
			carry = u[ j + n ];
			carry += borrow;
			u[ j + n ] = carry;

			// If we subtracted too much
			if ( carry < borrow )
			{
				// Add divisor back to dividend
				carry = BIT_ZERO;
				for ( int64_t i = BIT_ZERO; i < n; i++ )
				{
					carry = u[ i + j ] + v[ i ] + carry;
					u[ i + j ] = carry;
					carry = ( carry >= ONE_BITS ) ? BIT_ONE : BIT_ZERO;
				}
				u[ j + n ] += carry;
				qhat--;
			}

			// Store quotient digit
			quotient_and_remainder.first[ j ] = qhat;
		}

		// 3. Get quotient and real remainder
		// Bit shift right to unnormalize
		quotient_and_remainder.second = ( u >> shift ).low_bits;

		return quotient_and_remainder;
	}

	const uint64_t& uint128_t::high_value() const
	{
		return high_bits;
	}

	const uint64_t& uint128_t::low_value() const
	{
		return low_bits;
	}

	std::string uint128_t::to_string( uint8_t base, const unsigned int& size ) const
	{
		if ( ( base < 2 ) || ( base > 16 ) )
		{
			throw std::invalid_argument( "Base must be in the range [2, 16]" );
		}
		std::string result = "";
		if ( !( *this ) )
		{
			result = "0";
		}
		else
		{
			std::pair<uint128_t, uint128_t> quotient_and_remainder( *this, uint128_0 );
			do
			{
				quotient_and_remainder = division( quotient_and_remainder.first, base );
				result = "0123456789abcdef"[ ( uint8_t )quotient_and_remainder.second ] + result;
			} while ( quotient_and_remainder.first );
		}
		if ( result.size() < size )
		{
			result = std::string( size - result.size(), '0' ) + result;
		}
		return result;
	}

	std::ostream& operator<<(std::ostream & stream, const uint128_t & other)
	{
		if (stream.flags() & stream.oct){
			stream << other.to_string(8);
		}
		else if (stream.flags() & stream.dec){
			stream << other.to_string(10);
		}
		else if (stream.flags() & stream.hex){
			stream << other.to_string(16);
		}
		return stream;
	}
}  // namespace TwilightDream
Editor is loading...
Leave a Comment