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

Last change on this file since 5638 was 5638, checked in by Christoph Mayer, 15 years ago

adress detection aufgeräumt, network info für bleutooth, data stream (hopeful crash fix), logging auf maemo nur warn, ...

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.