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

Last change on this file since 2390 was 2390, checked in by mies, 16 years ago
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.