An Overlay-based
Virtual Network Substrate
SpoVNet

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

Last change on this file since 10700 was 10700, checked in by Michael Tänzer, 8 years ago

Merge CMake branch into trunk

File size: 11.5 KB
Line 
1// vint_big.hpp, created on 04.11.2008 by Sebastian Mies
2//
3// [The FreeBSD Licence]
4// Copyright (c) 2008
5//     Sebastian Mies, Institute of Telematics, UniversitÀt Karlsruhe (TH)
6//     All rights reserved.
7//
8// Redistribution and use in source and binary forms, with or without
9// modification, are permitted provided that the following conditions are
10// met:
11//
12// * Redistributions of source code must retain the above copyright notice,
13//   this list of conditions and the following disclaimer.
14// * Redistributions in binary form must reproduce the above copyright
15//   notice, this list of conditions and the following disclaimer in the
16//   documentation and/or other materials provided with the distribution.
17// * Neither the name of the author nor the names of its contributors may be
18//   used to endorse or promote products derived from this software without
19//   specific prior written permission.
20//
21// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
22// IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
23// THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
24// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
25// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
26// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
27// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
28// OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
29// WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
30// OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
31// ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32//
33#ifndef VINT_BIG_HPP_
34#define VINT_BIG_HPP_
35
36#include <memory>
37
38namespace _vint {
39namespace detail {
40        //forward declarations
41        template<size_t l, bool s>
42        class vint_big;
43}} // namespace _vint::detail
44
45template<size_t l, bool s>
46std::ostream& operator<<(std::ostream&, const _vint::detail::vint_big<l,s>& v);
47
48// utility includes
49#include "helper.hpp"
50#include "../varray.hpp"
51
52// std lib includes
53#include <cmath>
54#include <string.h>
55#include <typeinfo>
56#include <iostream>
57#include <sstream>
58
59// gnu mp library include
60#include <gmp.h>
61
62namespace _vint { namespace detail {
63
64/**
65 * This class implements an adaptive integer type.
66 *
67 * SIGNED values are currently unsupported!!!
68 *
69 * @author Sebastian Mies
70 */
71template<size_t __length = 0, bool __sign = false>
72class vint_big {
73        friend class vint_big<> ;
74        friend std::ostream& operator<< <__length,__sign>
75                (std::ostream&, const vint_big<__length,__sign>&);
76private:
77
78        /* own type */
79        typedef vint_big<__length> _self;
80        static const size_t limb_size = sizeof(mp_limb_t) * 8;
81
82        /* adaptive identifier storage */
83        varray<mp_limb_t, __length> mp;
84
85        /* this method masks off the most significant bits which are not needed */
86        finline void trim() {
87                const size_t bitp = length() & (sizeof(mp_limb_t) * 8 - 1);
88                if (bitp != 0) {
89                        const size_t indexp = length() / (sizeof(mp_limb_t) * 8);
90                        array()[indexp] &= (((mp_limb_t) 1) << bitp) - 1;
91                }
92        }
93
94public:
95        /* returns the array length */
96        finline size_t array_length() const {
97                return mp.array_size();
98        }
99
100        /* returns the limb array */
101        finline mp_limb_t* array() {
102                return mp.array();
103        }
104
105        /* returns the limb array */
106        finline const mp_limb_t* array() const {
107                return mp.array_const();
108        }
109        /* returns reference to a limb */
110        finline mp_limb_t& array(int index) {
111                return mp.array()[index];
112        }
113
114        /* returns reference to a limb */
115        finline mp_limb_t array(int index) const {
116                return mp.array_const()[index];
117        }
118
119        /* sets all bits to zero */
120        finline void clear() {
121                for (size_t i = 0; i < array_length(); i++)
122                        array( i) = 0;
123        }
124
125public:
126        /* construct an zero integer */
127        inline vint_big() {
128                clear();
129        }
130
131        template<typename T>
132        inline vint_big( const T value, if_integral(T) ) {
133                set_length( sizeof(T)*8 );
134                clear();
135                array(0) = value;
136        }
137
138        /* construct a variable integer from a given string */
139        inline vint_big(const char* text, int base = 10) {
140                assign(text, base);
141        }
142
143        //-- conversion -----------------------------------------------------------
144
145        std::string to_string(int base = 10, int str_size = 0, char str_fill = '0') const {
146
147                // alloc buffers
148                size_t size = mp.array_size();
149                mp_limb_t* buffer = new mp_limb_t[size * 2];
150                mp_limb_t* _div = buffer;
151                mp_limb_t* _val = buffer + size;
152
153                // copy value
154                memcpy(_val, mp.array_const(), size * sizeof(mp_limb_t));
155
156                // convert to another base
157                std::string s = "\0";
158                int last_non_zero = 0;
159                int last = 0;
160
161                while (size != 0) {
162                        // evaluate highest non-zero limb
163                        while (size != 0 && _val[size - 1] == 0)
164                                size--;
165
166                        // divide by base
167                        mp_limb_t rem = mpn_divrem_1(_div, 0, _val, size, base);
168
169                        // set char
170                        s += (char) rem;
171                        if (rem != 0) last_non_zero = last;
172                        last++;
173
174                        // divided value as new
175                        _val = _div;
176                }
177                last = last_non_zero + 1;
178
179                // reverse
180                for (int i = 0; i < last / 2; i++) {
181                        char dummy = s[i];
182                        s[i] = s[last - i - 1];
183                        s[last - i - 1] = (int) dummy;
184                }
185
186                // convert string
187                s.resize(last);
188                for (int i = 0; i < last; i++)
189                        s[i] = ("0123456789ABCDEF")[(int) s[i]];
190
191                // free buffer
192                delete buffer;
193
194                // add leading zeros
195                if (last < str_size) {
196                        char zeros[str_size - last+1];
197                        memset(zeros, str_fill, str_size - last);
198                        zeros[str_size - last] = 0;
199                        return std::string(zeros) + s;
200                } else {
201                        return s;
202                }
203        }
204
205        std::string to_debug_string(int base = 10, int str_size = 0, char str_fill =
206                        '0') const {
207                std::ostringstream str;
208                str << "vint_big(" << (mp.is_dynamic() ? "dynamic" : "static ") << ",";
209                str << "length=" << length() << ",";
210                str << "mem=" << mp.get_memory_consumption() << ",";
211                str << "val=" << to_string(base, str_size, str_fill) << ")";
212                return str.str();
213        }
214
215        template<typename T>
216        inline void convert_to(T& value, if_integral(T) ) const {
217                value = (T)array(0);
218        }
219
220        template<size_t _l, bool _s>
221        inline void convert_to(vint_big<_l,_s>& value) const {
222                value.assign(*this);
223        }
224
225        //-- sub integers ---------------------------------------------------------
226public:
227
228        inline bool get_bit( size_t index ) const {
229                size_t aidx = index / limb_size;
230                size_t bidx = index % limb_size;
231                return (array()[aidx] >> bidx) & 1;
232        }
233
234        inline void set_bit( size_t index, bool value ) {
235                size_t aidx = index / limb_size;
236                size_t bidx = index % limb_size;
237                array()[aidx] &= ~(1 << bidx);
238                array()[aidx] |=  (value << bidx);
239        }
240
241        inline void set_subint( _self& value, size_t index ) {
242
243        }
244
245        template<typename X>
246        inline void set_subint( X& value, size_t index ) {
247
248        }
249
250        inline _self get_subint( size_t index, size_t length ) const {
251                return 0;
252        }
253
254        inline uintmax_t get_subint( size_t index ) const {
255                return 0;
256        }
257
258        //-- assignment -----------------------------------------------------------
259
260public:
261
262        template<size_t _len, bool _sign>
263        inline void assign(const vint_big<_len,_sign>& cpy) {
264                vint_big<_len,_sign>& copy = const_cast<vint_big<_len,_sign>&> (cpy);
265                mp.resize( copy.length() );
266                clear();
267                size_t len = std::min(array_length(), copy.array_length());
268                for (size_t i = 0; i < len; i++)
269                        array(i) = copy.array(i);
270                trim();
271        }
272
273        template<typename T>
274        inline void assign( const T& value, if_integral(T) ) {
275                set_length( sizeof(T) * 8 );
276                clear();
277                bitcpy(value, 0, array(), 0, sizeof(T) * 8);
278        }
279
280        inline void assign( const std::string& text, int base = 10) {
281                std::string s = text;
282                size_t blen = ::log2(base) * s.size() + 1;
283                if ((blen % 8) != 0) blen += 8 - (blen % 8);
284                set_length(blen);
285                clear();
286                for (size_t i = 0; i < s.size(); i++) {
287                        if ((s[i] >= '0') && (s[i] <= '9')) s[i] -= '0';
288                        else if ((s[i] >= 'a') && (s[i] <= 'z')) s[i] -= ('a' - 10);
289                        else if ((s[i] >= 'A') && (s[i] <= 'Z')) s[i] -= ('A' - 10);
290                }
291                mpn_set_str(array(), (unsigned char*) s.c_str(), s.size(), base);
292        }
293
294        //-- compare operations ---------------------------------------------------
295
296        inline int compare_to(const _self& v) const {
297                return mpn_cmp(array(), v.array(), array_length());
298        }
299
300        template<class T>
301        inline int compare_to(const T& v, if_integral(T) ) const {
302                int i = array_length();
303                while (i != 0 && array(i - 1) == 0)
304                        i--;
305                return (i > 1) ? 1 : (int) (array(0) - v);
306        }
307
308        //-- arithmetic operations ------------------------------------------------
309
310public:
311
312        finline void add(const _self& v) {
313                mpn_add_n(array(), array(), const_cast<_self&> (v).array(),
314                                array_length());
315                trim();
316        }
317
318        template<class T>
319        finline void add( const T& v, if_uint(T) ) {
320                mpn_add_1(array(), array(), array_length(), v);
321                trim();
322        }
323
324        finline void sub(const _self& v) {
325                mpn_sub_n(array(), array(), const_cast<_self&> (v).array(),
326                                array_length());
327                trim();
328        }
329
330
331        template<class T>
332        finline T mod(const T& v, if_uint(T) ) {
333                return (T) mpn_mod_1(array(), array_length(), v);
334        }
335
336private:
337
338        finline vint_big<__length*2> mul(const _self& v) const {
339                vint_big<__length * 2> result;
340                result.set_length( length() );
341                mpn_mul_n(result.array(), mp.array_const(), v.mp.array_const(),
342                                array_length());
343                return result;
344        }
345
346public:
347
348        inline uintmax_t log2() const {
349                int size = array_length();
350                while (size != 0 && array(size-1) == 0) size--;
351                if (size == 0) return 0;
352                else return (size - 1) * sizeof(mp_limb_t) * 8 + ::log2(array(size-1));
353        }
354
355        //-- logical bit operations -----------------------------------------------
356
357        inline void or_(const _self& v) {
358                for (size_t i = 0; i < array_length(); i++)
359                        array()[i] |= v.array()[i];
360        }
361
362        inline void and_(const _self& v) {
363                for (size_t i = 0; i < array_length(); i++)
364                        array()[i] &= v.array()[i];
365        }
366
367        inline void xor_(const _self& v) {
368                for (size_t i = 0; i < array_length(); i++)
369                        array()[i] ^= v.array()[i];
370        }
371
372        inline void complement() {
373                for (size_t i = 0; i < array_length(); i++)
374                        array()[i] = ~array()[i];
375                trim();
376        }
377
378        inline void lshift(size_t steps) {
379                size_t i = steps / GMP_LIMB_BITS;
380                steps %= GMP_LIMB_BITS;
381                if (i >= array_length()) clear();
382                else {
383                        for (size_t j = 0; j < array_length() - i; j++)
384                                array()[j + i] = array()[j];
385                        mpn_lshift(array(), array(), array_length(), steps);
386                        trim();
387                }
388        }
389
390        inline void rshift(size_t steps) {
391                size_t i = steps / GMP_LIMB_BITS;
392                steps %= GMP_LIMB_BITS;
393                if (i >= array_length()) clear();
394                else {
395                        for (size_t j = 0; j < array_length() - i; j++)
396                                array()[j] = array()[j + i];
397                        mpn_rshift(array(), array(), array_length(), steps);
398                        trim();
399                }
400        }
401
402        //-- integer dynamic ------------------------------------------------------
403
404        inline vint_big<> normalized() const {
405                vint_big<> v;
406                int width = log2();
407                int a = (sizeof(mp_limb_t)*8);
408                if ((width % a)!=0) width += a-(width%a);
409                v.set_length( width );
410                for (size_t i=0; i<v.array_length(); i++) v.array(i) = array(i);
411                return v;
412        }
413
414        //-- general information --------------------------------------------------
415
416        finline size_t length() const {
417                return mp.size();
418        }
419
420        finline void set_length(size_t length) {
421                mp.resize(length);
422        }
423
424        finline bool is_unspecified() {
425                return (length() == 0);
426        }
427
428        /**
429         * This method returns the maximum number according to its size in bits.
430         *
431         * @return The maximum number according to its size in bits.
432         */
433        finline _self max() const {
434                _self v;
435                v.set_length(length());
436                for (size_t i=0; i<v.array_length(); i++) v.array(i) = ~0;
437                v.trim();
438                return v;
439        }
440
441        finline _self zero() const {
442                _self v;
443                v.set_length(length());
444                for (size_t i=0; i<v.array_length(); i++) v.array(i) = 0;
445                v.trim();
446                return v;
447        }
448
449        finline _self min() const {
450                return zero();
451        }
452};
453
454}}
455
456template<size_t __length, bool __sign>
457std::ostream& operator<<(std::ostream& os, const _vint::detail::vint_big<__length,__sign>& v) {
458        return os << v.to_string();
459}
460
461
462#endif /* VINTBIG_HPP_ */
Note: See TracBrowser for help on using the repository browser.