diff options
Diffstat (limited to 'include/jsoncons/bigint.hpp')
| -rw-r--r-- | include/jsoncons/bigint.hpp | 1611 |
1 files changed, 1611 insertions, 0 deletions
diff --git a/include/jsoncons/bigint.hpp b/include/jsoncons/bigint.hpp new file mode 100644 index 0000000..223b697 --- /dev/null +++ b/include/jsoncons/bigint.hpp @@ -0,0 +1,1611 @@ +// Copyright 2018 vDaniel Parker +// Distributed under the Boost license, Version 1.0. +// (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) + +// See https://github.com/danielaparker/jsoncons for latest version + +#ifndef JSONCONS_BIGINT_HPP +#define JSONCONS_BIGINT_HPP + +#include <cstdint> +#include <vector> // std::vector +#include <iostream> +#include <climits> +#include <cassert> // assert +#include <limits> // std::numeric_limits +#include <algorithm> // std::max, std::min, std::reverse +#include <string> // std::string +#include <cstring> // std::memcpy +#include <cmath> // std::fmod +#include <memory> // std::allocator +#include <initializer_list> // std::initializer_list +#include <type_traits> // std::enable_if +#include <jsoncons/config/jsoncons_config.hpp> + +namespace jsoncons { + +/* +This implementation is based on Chapter 2 and Appendix A of +Ammeraal, L. (1996) Algorithms and Data Structures in C++, +Chichester: John Wiley. + +*/ + + +namespace detail { + + template <class Allocator> + class basic_bigint_base + { + public: + using allocator_type = Allocator; + using basic_type_allocator_type = typename std::allocator_traits<allocator_type>:: template rebind_alloc<uint64_t>; + + private: + basic_type_allocator_type alloc_; + public: + using allocator_traits_type = std::allocator_traits<allocator_type>; + using stored_allocator_type = allocator_type; + using pointer = typename allocator_traits_type::pointer; + using value_type = typename allocator_traits_type::value_type; + using size_type = typename allocator_traits_type::size_type; + using pointer_traits = std::pointer_traits<pointer>; + + basic_bigint_base() + : alloc_() + { + } + explicit basic_bigint_base(const allocator_type& alloc) + : alloc_(basic_type_allocator_type(alloc)) + { + } + + basic_type_allocator_type get_allocator() const + { + return alloc_; + } + }; + +} // namespace detail + +template <class Allocator = std::allocator<uint64_t>> +class basic_bigint : protected detail::basic_bigint_base<Allocator> +{ + using base_t = detail::basic_bigint_base<Allocator>; + +public: + + using size_type = typename base_t::size_type; + using value_type = typename base_t::value_type; + using base_t::get_allocator; + using bigint_type = basic_bigint<Allocator>; + + static constexpr uint64_t max_basic_type = (std::numeric_limits<uint64_t>::max)(); + static constexpr uint64_t basic_type_bits = sizeof(uint64_t) * 8; // Number of bits + static constexpr uint64_t basic_type_halfBits = basic_type_bits/2; + + static constexpr uint16_t word_length = 4; // Use multiples of word_length words + static constexpr uint64_t r_mask = (uint64_t(1) << basic_type_halfBits) - 1; + static constexpr uint64_t l_mask = max_basic_type - r_mask; + static constexpr uint64_t l_bit = max_basic_type - (max_basic_type >> 1); + +private: + + struct common_storage + { + uint8_t is_dynamic_:1; + uint8_t is_negative_:1; + size_type length_; + }; + + struct short_storage + { + uint8_t is_dynamic_:1; + uint8_t is_negative_:1; + size_type length_; + uint64_t values_[2]; + + short_storage() + : is_dynamic_(false), + is_negative_(false), + length_(0), + values_{0,0} + { + } + + template <class T> + short_storage(T n, + typename std::enable_if<std::is_integral<T>::value && + sizeof(T) <= sizeof(int64_t) && + std::is_signed<T>::value>::type* = 0) + : is_dynamic_(false), + is_negative_(n < 0), + length_(n == 0 ? 0 : 1) + { + values_[0] = n < 0 ? (uint64_t(0)-static_cast<uint64_t>(n)) : static_cast<uint64_t>(n); + values_[1] = 0; + } + + template <class T> + short_storage(T n, + typename std::enable_if<std::is_integral<T>::value && + sizeof(T) <= sizeof(int64_t) && + !std::is_signed<T>::value>::type* = 0) + : is_dynamic_(false), + is_negative_(false), + length_(n == 0 ? 0 : 1) + { + values_[0] = n; + values_[1] = 0; + } + + template <class T> + short_storage(T n, + typename std::enable_if<std::is_integral<T>::value && + sizeof(int64_t) < sizeof(T) && + std::is_signed<T>::value>::type* = 0) + : is_dynamic_(false), + is_negative_(n < 0), + length_(n == 0 ? 0 : 2) + { + using unsigned_type = typename std::make_unsigned<T>::type; + + auto u = n < 0 ? (unsigned_type(0)-static_cast<unsigned_type>(n)) : static_cast<unsigned_type>(n); + values_[0] = uint64_t(u & max_basic_type);; + u >>= basic_type_bits; + values_[1] = uint64_t(u & max_basic_type);; + } + + template <class T> + short_storage(T n, + typename std::enable_if<std::is_integral<T>::value && + sizeof(int64_t) < sizeof(T) && + !std::is_signed<T>::value>::type* = 0) + : is_dynamic_(false), + is_negative_(false), + length_(n == 0 ? 0 : 2) + { + values_[0] = uint64_t(n & max_basic_type);; + n >>= basic_type_bits; + values_[1] = uint64_t(n & max_basic_type);; + } + + short_storage(const short_storage& stor) + : is_dynamic_(false), + is_negative_(stor.is_negative_), + length_(stor.length_) + { + values_[0] = stor.values_[0]; + values_[1] = stor.values_[1]; + } + + short_storage& operator=(const short_storage& stor) = delete; + }; + + struct dynamic_storage + { + using real_allocator_type = typename std::allocator_traits<Allocator>:: template rebind_alloc<uint64_t>; + using pointer = typename std::allocator_traits<real_allocator_type>::pointer; + + uint8_t is_dynamic_:1; + uint8_t is_negative_:1; + size_type length_; + size_type capacity_; + pointer data_; + + dynamic_storage() + : is_dynamic_(true), + is_negative_(false), + length_(0), + capacity_(0), + data_(nullptr) + { + } + + dynamic_storage(const dynamic_storage& stor, const real_allocator_type& alloc) + : is_dynamic_(true), + is_negative_(stor.is_negative_), + length_(stor.length_), + capacity_(0), + data_(nullptr) + { + create(stor.length_, alloc); + std::memcpy(data_, stor.data_, stor.length_*sizeof(uint64_t)); + } + + dynamic_storage(dynamic_storage&& stor) noexcept + : is_dynamic_(true), + is_negative_(stor.is_negative_), + length_(stor.length_), + capacity_(stor.capacity_), + data_(stor.data_) + { + stor.length_ = 0; + stor.capacity_ = 0; + stor.data_ = nullptr; + } + + void create(size_type length, real_allocator_type alloc) + { + capacity_ = round_up(length); + data_ = std::allocator_traits<real_allocator_type>::allocate(alloc, capacity_); + JSONCONS_TRY + { + std::allocator_traits<real_allocator_type>::construct(alloc, type_traits::to_plain_pointer(data_)); + } + JSONCONS_CATCH(...) + { + std::allocator_traits<real_allocator_type>::deallocate(alloc, data_, capacity_); + JSONCONS_RETHROW; + } + } + + void destroy(const real_allocator_type& a) noexcept + { + if (data_ != nullptr) + { + real_allocator_type alloc(a); + + std::allocator_traits<real_allocator_type>::destroy(alloc, type_traits::to_plain_pointer(data_)); + std::allocator_traits<real_allocator_type>::deallocate(alloc, data_,capacity_); + } + } + + void reserve(size_type n, const real_allocator_type& a) + { + real_allocator_type alloc(a); + + size_type capacity_new = round_up(n); + uint64_t* data_old = data_; + data_ = std::allocator_traits<real_allocator_type>::allocate(alloc, capacity_new); + if (length_ > 0) + { + std::memcpy( data_, data_old, length_*sizeof(uint64_t)); + } + if (capacity_ > 0 && data_ != nullptr) + { + std::allocator_traits<real_allocator_type>::deallocate(alloc, data_old, capacity_); + } + capacity_ = capacity_new; + } + + // Find suitable new block size + constexpr size_type round_up(size_type i) const + { + return (i/word_length + 1) * word_length; + } + }; + + union + { + common_storage common_stor_; + short_storage short_stor_; + dynamic_storage dynamic_stor_; + }; + +public: + basic_bigint() + { + ::new (&short_stor_) short_storage(); + } + + explicit basic_bigint(const Allocator& alloc) + : base_t(alloc) + { + ::new (&short_stor_) short_storage(); + } + + + basic_bigint(const basic_bigint<Allocator>& n) + : base_t(n.get_allocator()) + { + if (!n.is_dynamic()) + { + ::new (&short_stor_) short_storage(n.short_stor_); + } + else + { + ::new (&dynamic_stor_) dynamic_storage(n.dynamic_stor_, get_allocator()); + } + } + + basic_bigint(basic_bigint<Allocator>&& other) noexcept + : base_t(other.get_allocator()) + { + if (!other.is_dynamic()) + { + ::new (&short_stor_) short_storage(other.short_stor_); + } + else + { + ::new (&dynamic_stor_) dynamic_storage(std::move(other.dynamic_stor_)); + } + } + + template <class Integer> + basic_bigint(Integer n, + typename std::enable_if<std::is_integral<Integer>::value>::type* = 0) + { + ::new (&short_stor_) short_storage(n); + } + + ~basic_bigint() noexcept + { + destroy(); + } + + constexpr bool is_dynamic() const + { + return common_stor_.is_dynamic_; + } + + constexpr size_type length() const + { + return common_stor_.length_; + } + + constexpr size_type capacity() const + { + return is_dynamic() ? dynamic_stor_.capacity_ : 2; + } + + bool is_negative() const + { + return common_stor_.is_negative_; + } + + void is_negative(bool value) + { + common_stor_.is_negative_ = value; + } + + constexpr const uint64_t* data() const + { + return is_dynamic() ? dynamic_stor_.data_ : short_stor_.values_; + } + + uint64_t* data() + { + return is_dynamic() ? dynamic_stor_.data_ : short_stor_.values_; + } + + template <class CharT> + static basic_bigint<Allocator> from_string(const std::basic_string<CharT>& s) + { + return from_string(s.data(), s.length()); + } + + template <class CharT> + static basic_bigint<Allocator> from_string(const CharT* s) + { + return from_string(s, std::char_traits<CharT>::length(s)); + } + + template <class CharT> + static basic_bigint<Allocator> from_string(const CharT* data, size_type length) + { + bool neg; + if (*data == '-') + { + neg = true; + data++; + --length; + } + else + { + neg = false; + } + + basic_bigint<Allocator> v = 0; + for (size_type i = 0; i < length; i++) + { + CharT c = data[i]; + switch (c) + { + case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8': case '9': + v = (v * 10) + (uint64_t)(c - '0'); + break; + default: + JSONCONS_THROW(std::runtime_error(std::string("Invalid digit ") + "\'" + (char)c + "\'")); + } + } + + if (neg) + { + v.common_stor_.is_negative_ = true; + } + + return v; + } + + template <class CharT> + static basic_bigint<Allocator> from_string_radix(const CharT* data, size_type length, uint8_t radix) + { + if (!(radix >= 2 && radix <= 16)) + { + JSONCONS_THROW(std::runtime_error("Unsupported radix")); + } + + bool neg; + if (*data == '-') + { + neg = true; + data++; + --length; + } + else + { + neg = false; + } + + basic_bigint<Allocator> v = 0; + for (size_type i = 0; i < length; i++) + { + CharT c = data[i]; + uint64_t d; + switch (c) + { + case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8': case '9': + d = (uint64_t)(c - '0'); + break; + case 'a':case 'b':case 'c':case 'd':case 'e':case 'f': + d = (uint64_t)(c - ('a' - 10)); + break; + case 'A':case 'B':case 'C':case 'D':case 'E':case 'F': + d = (uint64_t)(c - ('A' - 10)); + break; + default: + JSONCONS_THROW(std::runtime_error(std::string("Invalid digit in radix ") + std::to_string(radix) + ": \'" + (char)c + "\'")); + } + if (d >= radix) + { + JSONCONS_THROW(std::runtime_error(std::string("Invalid digit in radix ") + std::to_string(radix) + ": \'" + (char)c + "\'")); + } + v = (v * radix) + d; + } + + if ( neg ) + { + v.common_stor_.is_negative_ = true; + } + return v; + } + + static basic_bigint from_bytes_be(int signum, const uint8_t* str, std::size_t n) + { + static const double radix_log2 = std::log2(next_power_of_two(256)); + // Estimate how big the result will be, so we can pre-allocate it. + double bits = radix_log2 * n; + double big_digits = std::ceil(bits / 64.0); + //std::cout << "ESTIMATED: " << big_digits << "\n"; + + bigint_type v = 0; + v.reserve(static_cast<std::size_t>(big_digits)); + + if (n > 0) + { + for (std::size_t i = 0; i < n; i++) + { + v = (v * 256) + (uint64_t)(str[i]); + } + } + //std::cout << "ACTUAL: " << v.length() << "\n"; + + if (signum < 0) + { + v.common_stor_.is_negative_ = true; + } + + return v; + } + + uint64_t* begin() { return is_dynamic() ? dynamic_stor_.data_ : short_stor_.values_; } + const uint64_t* begin() const { return is_dynamic() ? dynamic_stor_.data_ : short_stor_.values_; } + uint64_t* end() { return begin() + length(); } + const uint64_t* end() const { return begin() + length(); } + + void resize(size_type n) + { + size_type len_old = common_stor_.length_; + reserve(n); + common_stor_.length_ = n; + if ( common_stor_.length_ > len_old ) + { + memset( data()+len_old, 0, (common_stor_.length_ - len_old)*sizeof(uint64_t) ); + } + } + + void reserve(size_type n) + { + if (capacity() < n) + { + if (!is_dynamic()) + { + size_type size = short_stor_.length_; + size_type is_neg = short_stor_.is_negative_; + uint64_t values[2] = {short_stor_.values_[0], short_stor_.values_[1]}; + + ::new (&dynamic_stor_) dynamic_storage(); + dynamic_stor_.reserve(n, get_allocator()); + dynamic_stor_.length_ = size; + dynamic_stor_.is_negative_ = is_neg; + dynamic_stor_.data_[0] = values[0]; + dynamic_stor_.data_[1] = values[1]; + } + else + { + dynamic_stor_.reserve(n, get_allocator()); + } + } + } + + // operators + + bool operator!() const + { + return length() == 0 ? true : false; + } + + basic_bigint operator-() const + { + basic_bigint<Allocator> v(*this); + v.common_stor_.is_negative_ = !v.is_negative(); + return v; + } + + basic_bigint& operator=( const basic_bigint<Allocator>& y ) + { + if ( this != &y ) + { + resize( y.length() ); + common_stor_.is_negative_ = y.is_negative(); + if ( y.length() > 0 ) + { + std::memcpy( data(), y.data(), y.length()*sizeof(uint64_t) ); + } + } + return *this; + } + + basic_bigint& operator+=( const basic_bigint<Allocator>& y ) + { + if ( is_negative() != y.is_negative() ) + return *this -= -y; + uint64_t d; + uint64_t carry = 0; + + resize( (std::max)(y.length(), length()) + 1 ); + + for (size_type i = 0; i < length(); i++ ) + { + if ( i >= y.length() && carry == 0 ) + break; + d = data()[i] + carry; + carry = d < carry; + if ( i < y.length() ) + { + data()[i] = d + y.data()[i]; + if ( data()[i] < d ) + carry = 1; + } + else + data()[i] = d; + } + reduce(); + return *this; + } + + basic_bigint& operator-=( const basic_bigint<Allocator>& y ) + { + if ( is_negative() != y.is_negative() ) + return *this += -y; + if ( (!is_negative() && y > *this) || (is_negative() && y < *this) ) + return *this = -(y - *this); + uint64_t borrow = 0; + uint64_t d; + for (size_type i = 0; i < length(); i++ ) + { + if ( i >= y.length() && borrow == 0 ) + break; + d = data()[i] - borrow; + borrow = d > data()[i]; + if ( i < y.length()) + { + data()[i] = d - y.data()[i]; + if ( data()[i] > d ) + borrow = 1; + } + else + data()[i] = d; + } + reduce(); + return *this; + } + + basic_bigint& operator*=( int64_t y ) + { + *this *= uint64_t(y < 0 ? -y : y); + if ( y < 0 ) + common_stor_.is_negative_ = !is_negative(); + return *this; + } + + basic_bigint& operator*=( uint64_t y ) + { + size_type len0 = length(); + uint64_t hi; + uint64_t lo; + uint64_t dig = data()[0]; + uint64_t carry = 0; + + resize( length() + 1 ); + + size_type i = 0; + for (i = 0; i < len0; i++ ) + { + DDproduct( dig, y, hi, lo ); + data()[i] = lo + carry; + dig = data()[i+1]; + carry = hi + (data()[i] < lo); + } + data()[i] = carry; + reduce(); + return *this; + } + + basic_bigint& operator*=( basic_bigint<Allocator> y ) + { + if ( length() == 0 || y.length() == 0 ) + return *this = 0; + bool difSigns = is_negative() != y.is_negative(); + if ( length() + y.length() == 2 ) // length() = y.length() = 1 + { + uint64_t a = data()[0], b = y.data()[0]; + data()[0] = a * b; + if ( data()[0] / a != b ) + { + resize( 2 ); + DDproduct( a, b, data()[1], data()[0] ); + } + common_stor_.is_negative_ = difSigns; + return *this; + } + if ( length() == 1 ) // && y.length() > 1 + { + uint64_t digit = data()[0]; + *this = y; + *this *= digit; + } + else + { + if ( y.length() == 1 ) + *this *= y.data()[0]; + else + { + size_type lenProd = length() + y.length(), jA, jB; + uint64_t sumHi = 0, sumLo, hi, lo, + sumLo_old, sumHi_old, carry=0; + basic_bigint<Allocator> x = *this; + resize( lenProd ); // Give *this length lenProd + + for (size_type i = 0; i < lenProd; i++ ) + { + sumLo = sumHi; + sumHi = carry; + carry = 0; + for ( jA=0; jA < x.length(); jA++ ) + { + jB = i - jA; + if ( jB >= 0 && jB < y.length() ) + { + DDproduct( x.data()[jA], y.data()[jB], hi, lo ); + sumLo_old = sumLo; + sumHi_old = sumHi; + sumLo += lo; + if ( sumLo < sumLo_old ) + sumHi++; + sumHi += hi; + carry += (sumHi < sumHi_old); + } + } + data()[i] = sumLo; + } + } + } + reduce(); + common_stor_.is_negative_ = difSigns; + return *this; + } + + basic_bigint& operator/=( const basic_bigint<Allocator>& divisor ) + { + basic_bigint<Allocator> r; + divide( divisor, *this, r, false ); + return *this; + } + + basic_bigint& operator%=( const basic_bigint<Allocator>& divisor ) + { + basic_bigint<Allocator> q; + divide( divisor, q, *this, true ); + return *this; + } + + basic_bigint& operator<<=( uint64_t k ) + { + size_type q = (size_type)(k / basic_type_bits); + if ( q ) // Increase common_stor_.length_ by q: + { + resize(length() + q); + for (size_type i = length(); i-- > 0; ) + data()[i] = ( i < q ? 0 : data()[i - q]); + k %= basic_type_bits; + } + if ( k ) // 0 < k < basic_type_bits: + { + uint64_t k1 = basic_type_bits - k; + uint64_t mask = (uint64_t(1) << k) - uint64_t(1); + resize( length() + 1 ); + for (size_type i = length(); i-- > 0; ) + { + data()[i] <<= k; + if ( i > 0 ) + data()[i] |= (data()[i-1] >> k1) & mask; + } + } + reduce(); + return *this; + } + + basic_bigint& operator>>=(uint64_t k) + { + size_type q = (size_type)(k / basic_type_bits); + if ( q >= length() ) + { + resize( 0 ); + return *this; + } + if (q > 0) + { + memmove( data(), data()+q, (size_type)((length() - q)*sizeof(uint64_t)) ); + resize( length() - q ); + k %= basic_type_bits; + if ( k == 0 ) + { + reduce(); + return *this; + } + } + + size_type n = (size_type)(length() - 1); + int64_t k1 = basic_type_bits - k; + uint64_t mask = (uint64_t(1) << k) - 1; + for (size_type i = 0; i <= n; i++) + { + data()[i] >>= k; + if ( i < n ) + data()[i] |= ((data()[i+1] & mask) << k1); + } + reduce(); + return *this; + } + + basic_bigint& operator++() + { + *this += 1; + return *this; + } + + basic_bigint<Allocator> operator++(int) + { + basic_bigint<Allocator> old = *this; + ++(*this); + return old; + } + + basic_bigint<Allocator>& operator--() + { + *this -= 1; + return *this; + } + + basic_bigint<Allocator> operator--(int) + { + basic_bigint<Allocator> old = *this; + --(*this); + return old; + } + + basic_bigint& operator|=( const basic_bigint<Allocator>& a ) + { + if ( length() < a.length() ) + { + resize( a.length() ); + } + + const uint64_t* qBegin = a.begin(); + const uint64_t* q = a.end() - 1; + uint64_t* p = begin() + a.length() - 1; + + while ( q >= qBegin ) + { + *p-- |= *q--; + } + + reduce(); + + return *this; + } + + basic_bigint& operator^=( const basic_bigint<Allocator>& a ) + { + if ( length() < a.length() ) + { + resize( a.length() ); + } + + const uint64_t* qBegin = a.begin(); + const uint64_t* q = a.end() - 1; + uint64_t* p = begin() + a.length() - 1; + + while ( q >= qBegin ) + { + *p-- ^= *q--; + } + + reduce(); + + return *this; + } + + basic_bigint& operator&=( const basic_bigint<Allocator>& a ) + { + size_type old_length = length(); + + resize( (std::min)( length(), a.length() ) ); + + const uint64_t* pBegin = begin(); + uint64_t* p = end() - 1; + const uint64_t* q = a.begin() + length() - 1; + + while ( p >= pBegin ) + { + *p-- &= *q--; + } + + if ( old_length > length() ) + { + memset( data() + length(), 0, old_length - length() ); + } + + reduce(); + + return *this; + } + + explicit operator bool() const + { + return length() != 0 ? true : false; + } + + explicit operator int64_t() const + { + int64_t x = 0; + if ( length() > 0 ) + { + x = data() [0]; + } + + return is_negative() ? -x : x; + } + + explicit operator uint64_t() const + { + uint64_t u = 0; + if ( length() > 0 ) + { + u = data() [0]; + } + + return u; + } + + explicit operator double() const + { + double x = 0.0; + double factor = 1.0; + double values = (double)max_basic_type + 1.0; + + const uint64_t* p = begin(); + const uint64_t* pEnd = end(); + while ( p < pEnd ) + { + x += *p*factor; + factor *= values; + ++p; + } + + return is_negative() ? -x : x; + } + + explicit operator long double() const + { + long double x = 0.0; + long double factor = 1.0; + long double values = (long double)max_basic_type + 1.0; + + const uint64_t* p = begin(); + const uint64_t* pEnd = end(); + while ( p < pEnd ) + { + x += *p*factor; + factor *= values; + ++p; + } + + return is_negative() ? -x : x; + } + + template <typename Alloc> + void write_bytes_be(int& signum, std::vector<uint8_t,Alloc>& data) const + { + basic_bigint<Allocator> n(*this); + signum = (n < 0) ? -1 : (n > 0 ? 1 : 0); + + basic_bigint<Allocator> divisor(256); + + while (n >= 256) + { + basic_bigint<Allocator> q; + basic_bigint<Allocator> r; + n.divide(divisor, q, r, true); + n = q; + data.push_back((uint8_t)(uint64_t)r); + } + if (n >= 0) + { + data.push_back((uint8_t)(uint64_t)n); + } + std::reverse(data.begin(),data.end()); + } + + std::string to_string() const + { + std::string s; + write_string(s); + return s; + } + + template <typename Ch, typename Traits, typename Alloc> + void write_string(std::basic_string<Ch,Traits,Alloc>& data) const + { + basic_bigint<Allocator> v(*this); + + size_t len = (v.length() * basic_type_bits / 3) + 2; + data.reserve(len); + + static uint64_t p10 = 1; + static uint64_t ip10 = 0; + + if ( v.length() == 0 ) + { + data.push_back('0'); + } + else + { + uint64_t r; + if ( p10 == 1 ) + { + while ( p10 <= (std::numeric_limits<uint64_t>::max)()/10 ) + { + p10 *= 10; + ip10++; + } + } + // p10 is max unsigned power of 10 + basic_bigint<Allocator> R; + basic_bigint<Allocator> LP10 = p10; // LP10 = p10 = ::pow(10, ip10) + + do + { + v.divide( LP10, v, R, true ); + r = (R.length() ? R.data()[0] : 0); + for ( size_type j=0; j < ip10; j++ ) + { + data.push_back(char(r % 10 + '0')); + r /= 10; + if ( r + v.length() == 0 ) + break; + } + } + while ( v.length() ); + if (is_negative()) + { + data.push_back('-'); + } + std::reverse(data.begin(),data.end()); + } + } + + std::string to_string_hex() const + { + std::string s; + write_string_hex(s); + return s; + } + + template <typename Ch, typename Traits, typename Alloc> + void write_string_hex(std::basic_string<Ch,Traits,Alloc>& data) const + { + basic_bigint<Allocator> v(*this); + + std::size_t len = (v.length() * basic_bigint<Allocator>::basic_type_bits / 3) + 2; + data.reserve(len); + // 1/3 > ln(2)/ln(10) + static uint64_t p10 = 1; + static uint64_t ip10 = 0; + + if ( v.length() == 0 ) + { + data.push_back('0'); + } + else + { + uint64_t r; + if ( p10 == 1 ) + { + while ( p10 <= (std::numeric_limits<uint64_t>::max)()/16 ) + { + p10 *= 16; + ip10++; + } + } // p10 is max unsigned power of 16 + basic_bigint<Allocator> R; + basic_bigint<Allocator> LP10 = p10; // LP10 = p10 = ::pow(16, ip10) + do + { + v.divide( LP10, v, R, true ); + r = (R.length() ? R.data()[0] : 0); + for ( size_type j=0; j < ip10; j++ ) + { + uint8_t c = r % 16; + data.push_back((c < 10) ? ('0' + c) : ('A' - 10 + c)); + r /= 16; + if ( r + v.length() == 0 ) + break; + } + } + while (v.length()); + + if (is_negative()) + { + data.push_back('-'); + } + std::reverse(data.begin(),data.end()); + } + } + +// Global Operators + + friend bool operator==( const basic_bigint<Allocator>& x, const basic_bigint<Allocator>& y ) noexcept + { + return x.compare(y) == 0 ? true : false; + } + + friend bool operator==( const basic_bigint<Allocator>& x, int y ) noexcept + { + return x.compare(y) == 0 ? true : false; + } + + friend bool operator!=( const basic_bigint<Allocator>& x, const basic_bigint<Allocator>& y ) noexcept + { + return x.compare(y) != 0 ? true : false; + } + + friend bool operator!=( const basic_bigint<Allocator>& x, int y ) noexcept + { + return x.compare(basic_bigint<Allocator>(y)) != 0 ? true : false; + } + + friend bool operator<( const basic_bigint<Allocator>& x, const basic_bigint<Allocator>& y ) noexcept + { + return x.compare(y) < 0 ? true : false; + } + + friend bool operator<( const basic_bigint<Allocator>& x, int64_t y ) noexcept + { + return x.compare(y) < 0 ? true : false; + } + + friend bool operator>( const basic_bigint<Allocator>& x, const basic_bigint<Allocator>& y ) noexcept + { + return x.compare(y) > 0 ? true : false; + } + + friend bool operator>( const basic_bigint<Allocator>& x, int y ) noexcept + { + return x.compare(basic_bigint<Allocator>(y)) > 0 ? true : false; + } + + friend bool operator<=( const basic_bigint<Allocator>& x, const basic_bigint<Allocator>& y ) noexcept + { + return x.compare(y) <= 0 ? true : false; + } + + friend bool operator<=( const basic_bigint<Allocator>& x, int y ) noexcept + { + return x.compare(y) <= 0 ? true : false; + } + + friend bool operator>=( const basic_bigint<Allocator>& x, const basic_bigint<Allocator>& y ) noexcept + { + return x.compare(y) >= 0 ? true : false; + } + + friend bool operator>=( const basic_bigint<Allocator>& x, int y ) noexcept + { + return x.compare(y) >= 0 ? true : false; + } + + friend basic_bigint<Allocator> operator+( basic_bigint<Allocator> x, const basic_bigint<Allocator>& y ) + { + return x += y; + } + + friend basic_bigint<Allocator> operator+( basic_bigint<Allocator> x, int64_t y ) + { + return x += y; + } + + friend basic_bigint<Allocator> operator-( basic_bigint<Allocator> x, const basic_bigint<Allocator>& y ) + { + return x -= y; + } + + friend basic_bigint<Allocator> operator-( basic_bigint<Allocator> x, int64_t y ) + { + return x -= y; + } + + friend basic_bigint<Allocator> operator*( int64_t x, const basic_bigint<Allocator>& y ) + { + return basic_bigint<Allocator>(y) *= x; + } + + friend basic_bigint<Allocator> operator*( basic_bigint<Allocator> x, const basic_bigint<Allocator>& y ) + { + return x *= y; + } + + friend basic_bigint<Allocator> operator*( basic_bigint<Allocator> x, int64_t y ) + { + return x *= y; + } + + friend basic_bigint<Allocator> operator/( basic_bigint<Allocator> x, const basic_bigint<Allocator>& y ) + { + return x /= y; + } + + friend basic_bigint<Allocator> operator/( basic_bigint<Allocator> x, int y ) + { + return x /= y; + } + + friend basic_bigint<Allocator> operator%( basic_bigint<Allocator> x, const basic_bigint<Allocator>& y ) + { + return x %= y; + } + + friend basic_bigint<Allocator> operator<<( basic_bigint<Allocator> u, unsigned k ) + { + return u <<= k; + } + + friend basic_bigint<Allocator> operator<<( basic_bigint<Allocator> u, int k ) + { + return u <<= k; + } + + friend basic_bigint<Allocator> operator>>( basic_bigint<Allocator> u, unsigned k ) + { + return u >>= k; + } + + friend basic_bigint<Allocator> operator>>( basic_bigint<Allocator> u, int k ) + { + return u >>= k; + } + + friend basic_bigint<Allocator> operator|( basic_bigint<Allocator> x, const basic_bigint<Allocator>& y ) + { + return x |= y; + } + + friend basic_bigint<Allocator> operator|( basic_bigint<Allocator> x, int y ) + { + return x |= y; + } + + friend basic_bigint<Allocator> operator|( basic_bigint<Allocator> x, unsigned y ) + { + return x |= y; + } + + friend basic_bigint<Allocator> operator^( basic_bigint<Allocator> x, const basic_bigint<Allocator>& y ) + { + return x ^= y; + } + + friend basic_bigint<Allocator> operator^( basic_bigint<Allocator> x, int y ) + { + return x ^= y; + } + + friend basic_bigint<Allocator> operator^( basic_bigint<Allocator> x, unsigned y ) + { + return x ^= y; + } + + friend basic_bigint<Allocator> operator&( basic_bigint<Allocator> x, const basic_bigint<Allocator>& y ) + { + return x &= y; + } + + friend basic_bigint<Allocator> operator&( basic_bigint<Allocator> x, int y ) + { + return x &= y; + } + + friend basic_bigint<Allocator> operator&( basic_bigint<Allocator> x, unsigned y ) + { + return x &= y; + } + + friend basic_bigint<Allocator> abs( const basic_bigint<Allocator>& a ) + { + if ( a.is_negative() ) + { + return -a; + } + return a; + } + + friend basic_bigint<Allocator> power( basic_bigint<Allocator> x, unsigned n ) + { + basic_bigint<Allocator> y = 1; + + while ( n ) + { + if ( n & 1 ) + { + y *= x; + } + x *= x; + n >>= 1; + } + + return y; + } + + friend basic_bigint<Allocator> sqrt( const basic_bigint<Allocator>& a ) + { + basic_bigint<Allocator> x = a; + basic_bigint<Allocator> b = a; + basic_bigint<Allocator> q; + + b <<= 1; + while ( b >>= 2, b > 0 ) + { + x >>= 1; + } + while ( x > (q = a/x) + 1 || x < q - 1 ) + { + x += q; + x >>= 1; + } + return x < q ? x : q; + } + + template <class CharT> + friend std::basic_ostream<CharT>& operator<<(std::basic_ostream<CharT>& os, const basic_bigint<Allocator>& v) + { + std::basic_string<CharT> s; + v.write_string(s); + os << s; + + return os; + } + + int compare( const basic_bigint<Allocator>& y ) const noexcept + { + if ( is_negative() != y.is_negative() ) + return y.is_negative() - is_negative(); + int code = 0; + if ( length() == 0 && y.length() == 0 ) + code = 0; + else if ( length() < y.length() ) + code = -1; + else if ( length() > y.length() ) + code = +1; + else + { + for (size_type i = length(); i-- > 0; ) + { + if (data()[i] > y.data()[i]) + { + code = 1; + break; + } + else if (data()[i] < y.data()[i]) + { + code = -1; + break; + } + } + } + return is_negative() ? -code : code; + } + + void divide( basic_bigint<Allocator> denom, basic_bigint<Allocator>& quot, basic_bigint<Allocator>& rem, bool remDesired ) const + { + if ( denom.length() == 0 ) + { + JSONCONS_THROW(std::runtime_error( "Zero divide." )); + } + bool quot_neg = is_negative() ^ denom.is_negative(); + bool rem_neg = is_negative(); + int x = 0; + basic_bigint<Allocator> num = *this; + num.common_stor_.is_negative_ = denom.common_stor_.is_negative_ = false; + if ( num < denom ) + { + quot = uint64_t(0); + rem = num; + rem.common_stor_.is_negative_ = rem_neg; + return; + } + if ( denom.length() == 1 && num.length() == 1 ) + { + quot = uint64_t( num.data()[0]/denom.data()[0] ); + rem = uint64_t( num.data()[0]%denom.data()[0] ); + quot.common_stor_.is_negative_ = quot_neg; + rem.common_stor_.is_negative_ = rem_neg; + return; + } + else if (denom.length() == 1 && (denom.data()[0] & l_mask) == 0 ) + { + // Denominator fits into a half word + uint64_t divisor = denom.data()[0], dHi = 0, + q1, r, q2, dividend; + quot.resize(length()); + for (size_type i=length(); i-- > 0; ) + { + dividend = (dHi << basic_type_halfBits) | (data()[i] >> basic_type_halfBits); + q1 = dividend/divisor; + r = dividend % divisor; + dividend = (r << basic_type_halfBits) | (data()[i] & r_mask); + q2 = dividend/divisor; + dHi = dividend % divisor; + quot.data()[i] = (q1 << basic_type_halfBits) | q2; + } + quot.reduce(); + rem = dHi; + quot.common_stor_.is_negative_ = quot_neg; + rem.common_stor_.is_negative_ = rem_neg; + return; + } + basic_bigint<Allocator> num0 = num, denom0 = denom; + int second_done = normalize(denom, num, x); + size_type l = denom.length() - 1; + size_type n = num.length() - 1; + quot.resize(n - l); + for (size_type i=quot.length(); i-- > 0; ) + quot.data()[i] = 0; + rem = num; + if ( rem.data()[n] >= denom.data()[l] ) + { + rem.resize(rem.length() + 1); + n++; + quot.resize(quot.length() + 1); + } + uint64_t d = denom.data()[l]; + for ( size_type k = n; k > l; k-- ) + { + uint64_t q = DDquotient(rem.data()[k], rem.data()[k-1], d); + subtractmul( rem.data() + k - l - 1, denom.data(), l + 1, q ); + quot.data()[k - l - 1] = q; + } + quot.reduce(); + quot.common_stor_.is_negative_ = quot_neg; + if ( remDesired ) + { + unnormalize(rem, x, second_done); + rem.common_stor_.is_negative_ = rem_neg; + } + } +private: + void destroy() noexcept + { + if (is_dynamic()) + { + dynamic_stor_.destroy(get_allocator()); + } + } + void DDproduct( uint64_t A, uint64_t B, + uint64_t& hi, uint64_t& lo ) const + // Multiplying two digits: (hi, lo) = A * B + { + uint64_t hiA = A >> basic_type_halfBits, loA = A & r_mask, + hiB = B >> basic_type_halfBits, loB = B & r_mask, + mid1, mid2, old; + + lo = loA * loB; + hi = hiA * hiB; + mid1 = loA * hiB; + mid2 = hiA * loB; + old = lo; + lo += mid1 << basic_type_halfBits; + hi += (lo < old) + (mid1 >> basic_type_halfBits); + old = lo; + lo += mid2 << basic_type_halfBits; + hi += (lo < old) + (mid2 >> basic_type_halfBits); + } + + uint64_t DDquotient( uint64_t A, uint64_t B, uint64_t d ) const + // Divide double word (A, B) by d. Quotient = (qHi, qLo) + { + uint64_t left, middle, right, qHi, qLo, x, dLo1, + dHi = d >> basic_type_halfBits, dLo = d & r_mask; + qHi = A/(dHi + 1); + // This initial guess of qHi may be too small. + middle = qHi * dLo; + left = qHi * dHi; + x = B - (middle << basic_type_halfBits); + A -= (middle >> basic_type_halfBits) + left + (x > B); + B = x; + dLo1 = dLo << basic_type_halfBits; + // Increase qHi if necessary: + while ( A > dHi || (A == dHi && B >= dLo1) ) + { + x = B - dLo1; + A -= dHi + (x > B); + B = x; + qHi++; + } + qLo = ((A << basic_type_halfBits) | (B >> basic_type_halfBits))/(dHi + 1); + // This initial guess of qLo may be too small. + right = qLo * dLo; + middle = qLo * dHi; + x = B - right; + A -= (x > B); + B = x; + x = B - (middle << basic_type_halfBits); + A -= (middle >> basic_type_halfBits) + (x > B); + B = x; + // Increase qLo if necessary: + while ( A || B >= d ) + { + x = B - d; + A -= (x > B); + B = x; + qLo++; + } + return (qHi << basic_type_halfBits) + qLo; + } + + void subtractmul( uint64_t* a, uint64_t* b, size_type n, uint64_t& q ) const + // a -= q * b: b in n positions; correct q if necessary + { + uint64_t hi, lo, d, carry = 0; + size_type i; + for ( i = 0; i < n; i++ ) + { + DDproduct( b[i], q, hi, lo ); + d = a[i]; + a[i] -= lo; + if ( a[i] > d ) + carry++; + d = a[i + 1]; + a[i + 1] -= hi + carry; + carry = a[i + 1] > d; + } + if ( carry ) // q was too large + { + q--; + carry = 0; + for ( i = 0; i < n; i++ ) + { + d = a[i] + carry; + carry = d < carry; + a[i] = d + b[i]; + if ( a[i] < d ) + carry = 1; + } + a[n] = 0; + } + } + + int normalize( basic_bigint<Allocator>& denom, basic_bigint<Allocator>& num, int& x ) const + { + size_type r = denom.length() - 1; + uint64_t y = denom.data()[r]; + + x = 0; + while ( (y & l_bit) == 0 ) + { + y <<= 1; + x++; + } + denom <<= x; + num <<= x; + if ( r > 0 && denom.data()[r] < denom.data()[r-1] ) + { + denom *= max_basic_type; + num *= max_basic_type; + return 1; + } + return 0; + } + + void unnormalize( basic_bigint<Allocator>& rem, int x, int secondDone ) const + { + if ( secondDone ) + { + rem /= max_basic_type; + } + if ( x > 0 ) + { + rem >>= x; + } + else + { + rem.reduce(); + } + } + + size_type round_up(size_type i) const // Find suitable new block size + { + return (i/word_length + 1) * word_length; + } + + void reduce() + { + uint64_t* p = end() - 1; + uint64_t* pBegin = begin(); + while ( p >= pBegin ) + { + if ( *p ) + { + break; + } + --common_stor_.length_; + --p; + } + if ( length() == 0 ) + { + common_stor_.is_negative_ = false; + } + } + + static uint64_t next_power_of_two(uint64_t n) { + n = n - 1; + n |= n >> 1; + n |= n >> 2; + n |= n >> 4; + n |= n >> 8; + n |= n >> 16; + n |= n >> 32; + return n + 1; + } +}; + +using bigint = basic_bigint<std::allocator<uint8_t>>; + +#if !defined(JSONCONS_NO_DEPRECATED) +JSONCONS_DEPRECATED_MSG("Instead, use bigint") typedef bigint bignum; +#endif + +} + +#endif |