| 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 |
|
---|
| 38 | namespace _vint {
|
---|
| 39 | namespace detail {
|
---|
| 40 | //forward declarations
|
---|
| 41 | template<size_t l, bool s>
|
---|
| 42 | class vint_big;
|
---|
| 43 | }} // namespace _vint::detail
|
---|
| 44 |
|
---|
| 45 | template<size_t l, bool s>
|
---|
| 46 | std::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 |
|
---|
| 62 | namespace _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 | */
|
---|
| 71 | template<size_t __length = 0, bool __sign = false>
|
---|
| 72 | class vint_big {
|
---|
| 73 | friend class vint_big<> ;
|
---|
| 74 | friend std::ostream& operator<< <__length,__sign>
|
---|
| 75 | (std::ostream&, const vint_big<__length,__sign>&);
|
---|
| 76 | private:
|
---|
| 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 |
|
---|
| 94 | public:
|
---|
| 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 |
|
---|
| 125 | public:
|
---|
| 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 ---------------------------------------------------------
|
---|
| 226 | public:
|
---|
| 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 |
|
---|
| 260 | public:
|
---|
| 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 |
|
---|
| 310 | public:
|
---|
| 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 |
|
---|
| 336 | private:
|
---|
| 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 |
|
---|
| 346 | public:
|
---|
| 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 |
|
---|
| 456 | template<size_t __length, bool __sign>
|
---|
| 457 | std::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_ */
|
---|