source: source/ariba/utility/vtypes/detail/vint_big.hpp @ 8606

// vint_big.hpp, created on 04.11.2008 by Sebastian Mies
//
// [The FreeBSD Licence]
// Copyright (c) 2008
//     Sebastian Mies, Institute of Telematics, UniversitÀt Karlsruhe (TH)
//     All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// * Redistributions of source code must retain the above copyright notice,
//   this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright
//   notice, this list of conditions and the following disclaimer in the
//   documentation and/or other materials provided with the distribution.
// * Neither the name of the author nor the names of its contributors may be
//   used to endorse or promote products derived from this software without
//   specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
// IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
// THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
// OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
// WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
// OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
// ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
#ifndef VINT_BIG_HPP_
#define VINT_BIG_HPP_

#include <memory>

namespace _vint {
namespace detail {
        //forward declarations
        template<size_t l, bool s>
        class vint_big;
}} // namespace _vint::detail

template<size_t l, bool s>
std::ostream& operator<<(std::ostream&, const _vint::detail::vint_big<l,s>& v);

// utility includes
#include "helper.hpp"
#include "../varray.hpp"

// std lib includes
#include <cmath>
#include <string.h>
#include <typeinfo>
#include <iostream>
#include <sstream>

// gnu mp library include
#include <gmp.h>

namespace _vint { namespace detail {

/**
 * This class implements an adaptive integer type.
 *
 * SIGNED values are currently unsupported!!!
 *
 * @author Sebastian Mies
 */
template<size_t __length = 0, bool __sign = false>
class vint_big {
        friend class vint_big<> ;
        friend std::ostream& operator<< <__length,__sign>
                (std::ostream&, const vint_big<__length,__sign>&);
private:

        /* own type */
        typedef vint_big<__length> _self;
        static const size_t limb_size = sizeof(mp_limb_t) * 8;

        /* adaptive identifier storage */
        varray<mp_limb_t, __length> mp;

        /* this method masks off the most significant bits which are not needed */
        finline void trim() {
                const size_t bitp = length() & (sizeof(mp_limb_t) * 8 - 1);
                if (bitp != 0) {
                        const size_t indexp = length() / (sizeof(mp_limb_t) * 8);
                        array()[indexp] &= (((mp_limb_t) 1) << bitp) - 1;
                }
        }

public:
        /* returns the array length */
        finline size_t array_length() const {
                return mp.array_size();
        }

        /* returns the limb array */
        finline mp_limb_t* array() {
                return mp.array();
        }

        /* returns the limb array */
        finline const mp_limb_t* array() const {
                return mp.array_const();
        }
        /* returns reference to a limb */
        finline mp_limb_t& array(int index) {
                return mp.array()[index];
        }

        /* returns reference to a limb */
        finline mp_limb_t array(int index) const {
                return mp.array_const()[index];
        }

        /* sets all bits to zero */
        finline void clear() {
                for (size_t i = 0; i < array_length(); i++)
                        array( i) = 0;
        }

public:
        /* construct an zero integer */
        inline vint_big() {
                clear();
        }

        template<typename T>
        inline vint_big( const T value, if_integral(T) ) {
                set_length( sizeof(T)*8 );
                clear();
                array(0) = value;
        }

        /* construct a variable integer from a given string */
        inline vint_big(const char* text, int base = 10) {
                assign(text, base);
        }

        //-- conversion -----------------------------------------------------------

        std::string to_string(int base = 10, int str_size = 0, char str_fill = '0') const {

                // alloc buffers
                size_t size = mp.array_size();
                mp_limb_t* buffer = new mp_limb_t[size * 2];
                mp_limb_t* _div = buffer;
                mp_limb_t* _val = buffer + size;

                // copy value
                memcpy(_val, mp.array_const(), size * sizeof(mp_limb_t));

                // convert to another base
                std::string s = "\0";
                int last_non_zero = 0;
                int last = 0;

                while (size != 0) {
                        // evaluate highest non-zero limb
                        while (size != 0 && _val[size - 1] == 0)
                                size--;

                        // divide by base
                        mp_limb_t rem = mpn_divrem_1(_div, 0, _val, size, base);

                        // set char
                        s += (char) rem;
                        if (rem != 0) last_non_zero = last;
                        last++;

                        // divided value as new
                        _val = _div;
                }
                last = last_non_zero + 1;

                // reverse
                for (int i = 0; i < last / 2; i++) {
                        char dummy = s[i];
                        s[i] = s[last - i - 1];
                        s[last - i - 1] = (int) dummy;
                }

                // convert string
                s.resize(last);
                for (int i = 0; i < last; i++)
                        s[i] = ("0123456789ABCDEF")[(int) s[i]];

                // free buffer
                delete buffer;

                // add leading zeros
                if (last < str_size) {
                        char zeros[str_size - last+1];
                        memset(zeros, str_fill, str_size - last);
                        zeros[str_size - last] = 0;
                        return std::string(zeros) + s;
                } else {
                        return s;
                }
        }

        std::string to_debug_string(int base = 10, int str_size = 0, char str_fill =
                        '0') const {
                std::ostringstream str;
                str << "vint_big(" << (mp.is_dynamic() ? "dynamic" : "static ") << ",";
                str << "length=" << length() << ",";
                str << "mem=" << mp.get_memory_consumption() << ",";
                str << "val=" << to_string(base, str_size, str_fill) << ")";
                return str.str();
        }

        template<typename T>
        inline void convert_to(T& value, if_integral(T) ) const {
                value = (T)array(0);
        }

        template<size_t _l, bool _s>
        inline void convert_to(vint_big<_l,_s>& value) const {
                value.assign(*this);
        }

        //-- sub integers ---------------------------------------------------------
public:

        inline bool get_bit( size_t index ) const {
                size_t aidx = index / limb_size;
                size_t bidx = index % limb_size;
                return (array()[aidx] >> bidx) & 1;
        }

        inline void set_bit( size_t index, bool value ) {
                size_t aidx = index / limb_size;
                size_t bidx = index % limb_size;
                array()[aidx] &= ~(1 << bidx);
                array()[aidx] |=  (value << bidx);
        }

        inline void set_subint( _self& value, size_t index ) {

        }

        template<typename X>
        inline void set_subint( X& value, size_t index ) {

        }

        inline _self get_subint( size_t index, size_t length ) const {
                return 0;
        }

        inline uintmax_t get_subint( size_t index ) const {
                return 0;
        }

        //-- assignment -----------------------------------------------------------

public:

        template<size_t _len, bool _sign>
        inline void assign(const vint_big<_len,_sign>& cpy) {
                vint_big<_len,_sign>& copy = const_cast<vint_big<_len,_sign>&> (cpy);
                mp.resize( copy.length() );
                clear();
                size_t len = std::min(array_length(), copy.array_length());
                for (size_t i = 0; i < len; i++)
                        array(i) = copy.array(i);
                trim();
        }

        template<typename T>
        inline void assign( const T& value, if_integral(T) ) {
                set_length( sizeof(T) * 8 );
                clear();
                bitcpy(value, 0, array(), 0, sizeof(T) * 8);
        }

        inline void assign( const std::string& text, int base = 10) {
                std::string s = text;
                size_t blen = ::log2(base) * s.size() + 1;
                if ((blen % 8) != 0) blen += 8 - (blen % 8);
                set_length(blen);
                clear();
                for (size_t i = 0; i < s.size(); i++) {
                        if ((s[i] >= '0') && (s[i] <= '9')) s[i] -= '0';
                        else if ((s[i] >= 'a') && (s[i] <= 'z')) s[i] -= ('a' - 10);
                        else if ((s[i] >= 'A') && (s[i] <= 'Z')) s[i] -= ('A' - 10);
                }
                mpn_set_str(array(), (unsigned char*) s.c_str(), s.size(), base);
        }

        //-- compare operations ---------------------------------------------------

        inline int compare_to(const _self& v) const {
                return mpn_cmp(array(), v.array(), array_length());
        }

        template<class T>
        inline int compare_to(const T& v, if_integral(T) ) const {
                int i = array_length();
                while (i != 0 && array(i - 1) == 0)
                        i--;
                return (i > 1) ? 1 : (int) (array(0) - v);
        }

        //-- arithmetic operations ------------------------------------------------

public:

        finline void add(const _self& v) {
                mpn_add_n(array(), array(), const_cast<_self&> (v).array(),
                                array_length());
                trim();
        }

        template<class T>
        finline void add( const T& v, if_uint(T) ) {
                mpn_add_1(array(), array(), array_length(), v);
                trim();
        }

        finline void sub(const _self& v) {
                mpn_sub_n(array(), array(), const_cast<_self&> (v).array(),
                                array_length());
                trim();
        }


        template<class T>
        finline T mod(const T& v, if_uint(T) ) {
                return (T) mpn_mod_1(array(), array_length(), v);
        }

private:

        finline vint_big<__length*2> mul(const _self& v) const {
                vint_big<__length * 2> result;
                result.set_length( length() );
                mpn_mul_n(result.array(), mp.array_const(), v.mp.array_const(),
                                array_length());
                return result;
        }

public:

        inline uintmax_t log2() const {
                int size = array_length();
                while (size != 0 && array(size-1) == 0) size--;
                if (size == 0) return 0;
                else return (size - 1) * sizeof(mp_limb_t) * 8 + ::log2(array(size-1));
        }

        //-- logical bit operations -----------------------------------------------

        inline void or_(const _self& v) {
                for (size_t i = 0; i < array_length(); i++)
                        array()[i] |= v.array()[i];
        }

        inline void and_(const _self& v) {
                for (size_t i = 0; i < array_length(); i++)
                        array()[i] &= v.array()[i];
        }

        inline void xor_(const _self& v) {
                for (size_t i = 0; i < array_length(); i++)
                        array()[i] ^= v.array()[i];
        }

        inline void complement() {
                for (size_t i = 0; i < array_length(); i++)
                        array()[i] = ~array()[i];
                trim();
        }

        inline void lshift(size_t steps) {
                size_t i = steps / GMP_LIMB_BITS;
                steps %= GMP_LIMB_BITS;
                if (i >= array_length()) clear();
                else {
                        for (size_t j = 0; j < array_length() - i; j++)
                                array()[j + i] = array()[j];
                        mpn_lshift(array(), array(), array_length(), steps);
                        trim();
                }
        }

        inline void rshift(size_t steps) {
                size_t i = steps / GMP_LIMB_BITS;
                steps %= GMP_LIMB_BITS;
                if (i >= array_length()) clear();
                else {
                        for (size_t j = 0; j < array_length() - i; j++)
                                array()[j] = array()[j + i];
                        mpn_rshift(array(), array(), array_length(), steps);
                        trim();
                }
        }

        //-- integer dynamic ------------------------------------------------------

        inline vint_big<> normalized() const {
                vint_big<> v;
                int width = log2();
                int a = (sizeof(mp_limb_t)*8);
                if ((width % a)!=0) width += a-(width%a);
                v.set_length( width );
                for (size_t i=0; i<v.array_length(); i++) v.array(i) = array(i);
                return v;
        }

        //-- general information --------------------------------------------------

        finline size_t length() const {
                return mp.size();
        }

        finline void set_length(size_t length) {
                mp.resize(length);
        }

        finline bool is_unspecified() {
                return (length() == 0);
        }

        /**
         * This method returns the maximum number according to its size in bits.
         *
         * @return The maximum number according to its size in bits.
         */
        finline _self max() const {
                _self v;
                v.set_length(length());
                for (size_t i=0; i<v.array_length(); i++) v.array(i) = ~0;
                v.trim();
                return v;
        }

        finline _self zero() const {
                _self v;
                v.set_length(length());
                for (size_t i=0; i<v.array_length(); i++) v.array(i) = 0;
                v.trim();
                return v;
        }

        finline _self min() const {
                return zero();
        }
};

}}

template<size_t __length, bool __sign>
std::ostream& operator<<(std::ostream& os, const _vint::detail::vint_big<__length,__sign>& v) {
        return os << v.to_string();
}


#endif /* VINTBIG_HPP_ */