00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033 #ifndef VINT_BIG_HPP_
00034 #define VINT_BIG_HPP_
00035
00036 #include <memory>
00037
00038 namespace _vint {
00039 namespace detail {
00040
00041 template<size_t l, bool s>
00042 class vint_big;
00043 }}
00044
00045 template<size_t l, bool s>
00046 std::ostream& operator<<(std::ostream&, const _vint::detail::vint_big<l,s>& v);
00047
00048
00049 #include "helper.hpp"
00050 #include "../varray.hpp"
00051
00052
00053 #include <cmath>
00054 #include <string.h>
00055 #include <typeinfo>
00056 #include <iostream>
00057 #include <sstream>
00058
00059
00060 #include <gmp.h>
00061
00062 namespace _vint { namespace detail {
00063
00071 template<size_t __length = 0, bool __sign = false>
00072 class vint_big {
00073 friend class vint_big<> ;
00074 friend std::ostream& operator<< <__length,__sign>
00075 (std::ostream&, const vint_big<__length,__sign>&);
00076 private:
00077
00078
00079 typedef vint_big<__length> _self;
00080 static const size_t limb_size = sizeof(mp_limb_t) * 8;
00081
00082
00083 varray<mp_limb_t, __length> mp;
00084
00085
00086 finline void trim() {
00087 const size_t bitp = length() & (sizeof(mp_limb_t) * 8 - 1);
00088 if (bitp != 0) {
00089 const size_t indexp = length() / (sizeof(mp_limb_t) * 8);
00090 array()[indexp] &= (((mp_limb_t) 1) << bitp) - 1;
00091 }
00092 }
00093
00094 public:
00095
00096 finline size_t array_length() const {
00097 return mp.array_size();
00098 }
00099
00100
00101 finline mp_limb_t* array() {
00102 return mp.array();
00103 }
00104
00105
00106 finline const mp_limb_t* array() const {
00107 return mp.array_const();
00108 }
00109
00110 finline mp_limb_t& array(int index) {
00111 return mp.array()[index];
00112 }
00113
00114
00115 finline mp_limb_t array(int index) const {
00116 return mp.array_const()[index];
00117 }
00118
00119
00120 finline void clear() {
00121 for (size_t i = 0; i < array_length(); i++)
00122 array( i) = 0;
00123 }
00124
00125 public:
00126
00127 inline vint_big() {
00128 clear();
00129 }
00130
00131 template<typename T>
00132 inline vint_big( const T value, if_integral(T) ) {
00133 set_length( sizeof(T)*8 );
00134 clear();
00135 array(0) = value;
00136 }
00137
00138
00139 inline vint_big(const char* text, int base = 10) {
00140 assign(text, base);
00141 }
00142
00143
00144
00145 std::string to_string(int base = 10, int str_size = 0, char str_fill = '0') const {
00146
00147
00148 size_t size = mp.array_size();
00149 mp_limb_t* buffer = new mp_limb_t[size * 2];
00150 mp_limb_t* _div = buffer;
00151 mp_limb_t* _val = buffer + size;
00152
00153
00154 memcpy(_val, mp.array_const(), size * sizeof(mp_limb_t));
00155
00156
00157 std::string s = "\0";
00158 int last_non_zero = 0;
00159 int last = 0;
00160
00161 while (size != 0) {
00162
00163 while (size != 0 && _val[size - 1] == 0)
00164 size--;
00165
00166
00167 mp_limb_t rem = mpn_divrem_1(_div, 0, _val, size, base);
00168
00169
00170 s += (char) rem;
00171 if (rem != 0) last_non_zero = last;
00172 last++;
00173
00174
00175 _val = _div;
00176 }
00177 last = last_non_zero + 1;
00178
00179
00180 for (int i = 0; i < last / 2; i++) {
00181 char dummy = s[i];
00182 s[i] = s[last - i - 1];
00183 s[last - i - 1] = (int) dummy;
00184 }
00185
00186
00187 s.resize(last);
00188 for (int i = 0; i < last; i++)
00189 s[i] = ("0123456789ABCDEF")[(int) s[i]];
00190
00191
00192 delete buffer;
00193
00194
00195 if (last < str_size) {
00196 char zeros[str_size - last+1];
00197 memset(zeros, str_fill, str_size - last);
00198 zeros[str_size - last] = 0;
00199 return std::string(zeros) + s;
00200 } else {
00201 return s;
00202 }
00203 }
00204
00205 std::string to_debug_string(int base = 10, int str_size = 0, char str_fill =
00206 '0') const {
00207 std::ostringstream str;
00208 str << "vint_big(" << (mp.is_dynamic() ? "dynamic" : "static ") << ",";
00209 str << "length=" << length() << ",";
00210 str << "mem=" << mp.get_memory_consumption() << ",";
00211 str << "val=" << to_string(base, str_size, str_fill) << ")";
00212 return str.str();
00213 }
00214
00215 template<typename T>
00216 inline void convert_to(T& value, if_integral(T) ) const {
00217 value = (T)array(0);
00218 }
00219
00220 template<size_t _l, bool _s>
00221 inline void convert_to(vint_big<_l,_s>& value) const {
00222 value.assign(*this);
00223 }
00224
00225
00226 public:
00227
00228 inline bool get_bit( size_t index ) const {
00229 size_t aidx = index / limb_size;
00230 size_t bidx = index % limb_size;
00231 return (array()[aidx] >> bidx) & 1;
00232 }
00233
00234 inline void set_bit( size_t index, bool value ) {
00235 size_t aidx = index / limb_size;
00236 size_t bidx = index % limb_size;
00237 array()[aidx] &= ~(1 << bidx);
00238 array()[aidx] |= (value << bidx);
00239 }
00240
00241 inline void set_subint( _self& value, size_t index ) {
00242
00243 }
00244
00245 template<typename X>
00246 inline void set_subint( X& value, size_t index ) {
00247
00248 }
00249
00250 inline _self get_subint( size_t index, size_t length ) const {
00251 return 0;
00252 }
00253
00254 inline uintmax_t get_subint( size_t index ) const {
00255 return 0;
00256 }
00257
00258
00259
00260 public:
00261
00262 template<size_t _len, bool _sign>
00263 inline void assign(const vint_big<_len,_sign>& cpy) {
00264 vint_big<_len,_sign>& copy = const_cast<vint_big<_len,_sign>&> (cpy);
00265 mp.resize( copy.length() );
00266 clear();
00267 size_t len = std::min(array_length(), copy.array_length());
00268 for (size_t i = 0; i < len; i++)
00269 array(i) = copy.array(i);
00270 trim();
00271 }
00272
00273 template<typename T>
00274 inline void assign( const T& value, if_integral(T) ) {
00275 set_length( sizeof(T) * 8 );
00276 clear();
00277 bitcpy(value, 0, array(), 0, sizeof(T) * 8);
00278 }
00279
00280 inline void assign( const std::string& text, int base = 10) {
00281 std::string s = text;
00282 size_t blen = ::log2(base) * s.size() + 1;
00283 if ((blen % 8) != 0) blen += 8 - (blen % 8);
00284 set_length(blen);
00285 clear();
00286 for (size_t i = 0; i < s.size(); i++) {
00287 if ((s[i] >= '0') && (s[i] <= '9')) s[i] -= '0';
00288 else if ((s[i] >= 'a') && (s[i] <= 'z')) s[i] -= ('a' - 10);
00289 else if ((s[i] >= 'A') && (s[i] <= 'Z')) s[i] -= ('A' - 10);
00290 }
00291 mpn_set_str(array(), (unsigned char*) s.c_str(), s.size(), base);
00292 }
00293
00294
00295
00296 inline int compare_to(const _self& v) const {
00297 return mpn_cmp(array(), v.array(), array_length());
00298 }
00299
00300 template<class T>
00301 inline int compare_to(const T& v, if_integral(T) ) const {
00302 int i = array_length();
00303 while (i != 0 && array(i - 1) == 0)
00304 i--;
00305 return (i > 1) ? 1 : (int) (array(0) - v);
00306 }
00307
00308
00309
00310 public:
00311
00312 finline void add(const _self& v) {
00313 mpn_add_n(array(), array(), const_cast<_self&> (v).array(),
00314 array_length());
00315 trim();
00316 }
00317
00318 template<class T>
00319 finline void add( const T& v, if_uint(T) ) {
00320 mpn_add_1(array(), array(), array_length(), v);
00321 trim();
00322 }
00323
00324 finline void sub(const _self& v) {
00325 mpn_sub_n(array(), array(), const_cast<_self&> (v).array(),
00326 array_length());
00327 trim();
00328 }
00329
00330
00331 template<class T>
00332 finline T mod(const T& v, if_uint(T) ) {
00333 return (T) mpn_mod_1(array(), array_length(), v);
00334 }
00335
00336 private:
00337
00338 finline vint_big<__length*2> mul(const _self& v) const {
00339 vint_big<__length * 2> result;
00340 result.set_length( length() );
00341 mpn_mul_n(result.array(), mp.array_const(), v.mp.array_const(),
00342 array_length());
00343 return result;
00344 }
00345
00346 public:
00347
00348 inline uintmax_t log2() const {
00349 int size = array_length();
00350 while (size != 0 && array(size-1) == 0) size--;
00351 if (size == 0) return 0;
00352 else return (size - 1) * sizeof(mp_limb_t) * 8 + ::log2(array(size-1));
00353 }
00354
00355
00356
00357 inline void or_(const _self& v) {
00358 for (size_t i = 0; i < array_length(); i++)
00359 array()[i] |= v.array()[i];
00360 }
00361
00362 inline void and_(const _self& v) {
00363 for (size_t i = 0; i < array_length(); i++)
00364 array()[i] &= v.array()[i];
00365 }
00366
00367 inline void xor_(const _self& v) {
00368 for (size_t i = 0; i < array_length(); i++)
00369 array()[i] ^= v.array()[i];
00370 }
00371
00372 inline void complement() {
00373 for (size_t i = 0; i < array_length(); i++)
00374 array()[i] = ~array()[i];
00375 trim();
00376 }
00377
00378 inline void lshift(size_t steps) {
00379 size_t i = steps / GMP_LIMB_BITS;
00380 steps %= GMP_LIMB_BITS;
00381 if (i >= array_length()) clear();
00382 else {
00383 for (size_t j = 0; j < array_length() - i; j++)
00384 array()[j + i] = array()[j];
00385 mpn_lshift(array(), array(), array_length(), steps);
00386 trim();
00387 }
00388 }
00389
00390 inline void rshift(size_t steps) {
00391 size_t i = steps / GMP_LIMB_BITS;
00392 steps %= GMP_LIMB_BITS;
00393 if (i >= array_length()) clear();
00394 else {
00395 for (size_t j = 0; j < array_length() - i; j++)
00396 array()[j] = array()[j + i];
00397 mpn_rshift(array(), array(), array_length(), steps);
00398 trim();
00399 }
00400 }
00401
00402
00403
00404 inline vint_big<> normalized() const {
00405 vint_big<> v;
00406 int width = log2();
00407 int a = (sizeof(mp_limb_t)*8);
00408 if ((width % a)!=0) width += a-(width%a);
00409 v.set_length( width );
00410 for (size_t i=0; i<v.array_length(); i++) v.array(i) = array(i);
00411 return v;
00412 }
00413
00414
00415
00416 finline size_t length() const {
00417 return mp.size();
00418 }
00419
00420 finline void set_length(size_t length) {
00421 mp.resize(length);
00422 }
00423
00424 finline bool is_unspecified() {
00425 return (length() == 0);
00426 }
00427
00433 finline _self max() const {
00434 _self v;
00435 v.set_length(length());
00436 for (size_t i=0; i<v.array_length(); i++) v.array(i) = ~0;
00437 v.trim();
00438 return v;
00439 }
00440
00441 finline _self zero() const {
00442 _self v;
00443 v.set_length(length());
00444 for (size_t i=0; i<v.array_length(); i++) v.array(i) = 0;
00445 v.trim();
00446 return v;
00447 }
00448
00449 finline _self min() const {
00450 return zero();
00451 }
00452 };
00453
00454 }}
00455
00456 template<size_t __length, bool __sign>
00457 std::ostream& operator<<(std::ostream& os, const _vint::detail::vint_big<__length,__sign>& v) {
00458 return os << v.to_string();
00459 }
00460
00461
00462 #endif