#include <psemek/util/big_int.hpp>

#include <algorithm>

namespace psemek::util
{

	namespace
	{

		struct adder
		{
			std::uint32_t sum = 0;
			std::uint32_t carry = 0;

			void add(std::uint32_t x)
			{
				auto result = static_cast<std::uint64_t>(sum) + x;
				sum = result & std::uint32_t(-1);
				carry += result >> 32;
			}
		};

	}

	void big_int::canonicalize()
	{
		auto size = this->size();
		auto negative = this->negative();

		while (size > 0 && digits_[size - 1] == 0)
			--size;

		set_size(size);
		set_negative(size > 0 && negative);
	}

	void big_int::ensure_capacity(std::uint32_t new_capacity)
	{
		if (new_capacity == 0)
		{
			digits_ = nullptr;
			size_ = 0;
			capacity_ = 0;
		}
		else if (new_capacity > capacity_)
		{
			new_capacity = std::max({static_cast<std::uint32_t>(1.6 * size()), static_cast<std::uint32_t>(16), new_capacity});

			auto new_digits = std::make_unique<digit[]>(new_capacity);

			std::size_t i = 0;
			for (; i < size(); ++i)
				new_digits[i] = digits_[i];
			for (; i < new_capacity; ++i)
				new_digits[i] = 0;

			digits_ = std::move(new_digits);
			capacity_ = new_capacity;
		}
	}

	void big_int::add_positive(span<digit const> digits)
	{
		digit carry = 0;

		std::size_t i = 0;
		std::size_t min_size = std::min<std::size_t>(size(), digits.size());

		for (; i < min_size; ++i)
		{
			adder adder{digits_[i]};
			adder.add(digits[i]);
			adder.add(carry);
			std::tie(digits_[i], carry) = {adder.sum, adder.carry};
		}

		if (i < digits.size())
		{
			ensure_capacity(digits.size());
			for (; i < digits.size(); ++i)
			{
				adder adder{digits[i]};
				adder.add(carry);
				std::tie(digits_[i], carry) = {adder.sum, adder.carry};
			}
			set_size(digits.size());
		}

		if (i < size())
		{
			for (; i < size() && carry != 0; ++i)
			{
				adder adder{digits_[i]};
				adder.add(carry);
				std::tie(digits_[i], carry) = {adder.sum, adder.carry};
			}
		}

		if (carry != 0)
		{
			ensure_capacity(size() + 1);
			digits_[size()] = carry;
			set_size(size() + 1);
		}

		canonicalize();
	}

}