00001
00002
00003
00004 #ifndef DUNE_BIGUNSIGNEDINT_HH
00005 #define DUNE_BIGUNSIGNEDINT_HH
00006
00007 #include <iostream>
00008 #include <limits>
00009 #include <cstdint>
00010 #include <cstdlib>
00011 #include <type_traits>
00012 #include <dune/common/exceptions.hh>
00013 #include <dune/common/hash.hh>
00014
00021 namespace Dune
00022 {
00023 #if HAVE_MPI
00024 template<class K>
00025 struct MPITraits;
00026 #endif
00027
00033 namespace {
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045 template<typename T>
00046 struct numeric_limits_helper
00047 {
00048
00049 protected:
00050
00051 static std::uint16_t& digit(T& big_unsigned_int, std::size_t i)
00052 {
00053 return big_unsigned_int.digit[i];
00054 }
00055
00056 };
00057
00058 }
00059
00069 template<int k>
00070 class bigunsignedint {
00071 public:
00072
00073
00074 enum { bits=std::numeric_limits<std::uint16_t>::digits, n=k/bits+(k%bits!=0),
00075 hexdigits=4, bitmask=0xFFFF, compbitmask=0xFFFF0000,
00076 overflowmask=0x1 };
00077
00079 bigunsignedint ();
00080
00082 template<typename Signed>
00083 bigunsignedint (Signed x, typename std::enable_if<std::is_integral<Signed>::value && std::is_signed<Signed>::value>::type* = 0);
00084
00086 bigunsignedint (std::uintmax_t x);
00087
00089 void print (std::ostream& s) const ;
00090
00092 bigunsignedint<k> operator+ (const bigunsignedint<k>& x) const;
00093
00095 bigunsignedint<k> operator- (const bigunsignedint<k>& x) const;
00096
00098 bigunsignedint<k> operator* (const bigunsignedint<k>& x) const;
00099
00101 bigunsignedint<k>& operator++ ();
00102
00106 bigunsignedint<k> operator/ (const bigunsignedint<k>& x) const;
00107
00111 bigunsignedint<k> operator% (const bigunsignedint<k>& x) const;
00112
00113
00115 bigunsignedint<k> operator& (const bigunsignedint<k>& x) const;
00116
00118 bigunsignedint<k> operator^ (const bigunsignedint<k>& x) const;
00119
00121 bigunsignedint<k> operator| (const bigunsignedint<k>& x) const;
00122
00124 bigunsignedint<k> operator~ () const;
00125
00126
00128 bigunsignedint<k> operator<< (int i) const;
00129
00131 bigunsignedint<k> operator>> (int i) const;
00132
00133
00135 bool operator< (const bigunsignedint<k>& x) const;
00136
00138 bool operator<= (const bigunsignedint<k>& x) const;
00139
00141 bool operator> (const bigunsignedint<k>& x) const;
00142
00144 bool operator>= (const bigunsignedint<k>& x) const;
00145
00147 bool operator== (const bigunsignedint<k>& x) const;
00148
00150 bool operator!= (const bigunsignedint<k>& x) const;
00151
00152
00154
00155 std::uint_least32_t touint() const;
00161 double todouble() const;
00162
00163 friend class bigunsignedint<k/2>;
00164 friend struct numeric_limits_helper< bigunsignedint<k> >;
00165
00166 inline friend std::size_t hash_value(const bigunsignedint& arg)
00167 {
00168 return hash_range(arg.digit,arg.digit + arg.n);
00169 }
00170
00171 private:
00172 std::uint16_t digit[n];
00173 #if HAVE_MPI
00174 friend struct MPITraits<bigunsignedint<k> >;
00175 #endif
00176 inline void assign(std::uintmax_t x);
00177
00178
00179 } ;
00180
00181
00182 template<int k>
00183 bigunsignedint<k>::bigunsignedint ()
00184 {
00185 assign(0u);
00186 }
00187
00188 template<int k>
00189 template<typename Signed>
00190 bigunsignedint<k>::bigunsignedint (Signed y, typename std::enable_if<std::is_integral<Signed>::value && std::is_signed<Signed>::value>::type*)
00191 {
00192 if (y < 0)
00193 DUNE_THROW(Dune::Exception, "Trying to construct a Dune::bigunsignedint from a negative integer: " << y);
00194 assign(y);
00195 }
00196
00197 template<int k>
00198 bigunsignedint<k>::bigunsignedint (std::uintmax_t x)
00199 {
00200 assign(x);
00201 }
00202 template<int k>
00203 void bigunsignedint<k>::assign(std::uintmax_t x)
00204 {
00205 static const int no=std::min(static_cast<int>(n),
00206 static_cast<int>(std::numeric_limits<std::uintmax_t>::digits/bits));
00207
00208 for(int i=0; i<no; ++i) {
00209 digit[i] = (x&bitmask);
00210 x=x>>bits;
00211 }
00212 for (unsigned int i=no; i<n; i++) digit[i]=0;
00213 }
00214
00215
00216 template<int k>
00217 inline std::uint_least32_t bigunsignedint<k>::touint () const
00218 {
00219 return (digit[1]<<bits)+digit[0];
00220 }
00221
00222 template<int k>
00223 inline double bigunsignedint<k>::todouble() const
00224 {
00225 int firstInZeroRange=n;
00226 for(int i=n-1; i>=0; --i)
00227 if(digit[i]!=0)
00228 break;
00229 else
00230 --firstInZeroRange;
00231 int representableDigits=std::numeric_limits<double>::digits/bits;
00232 int lastInRepresentableRange=0;
00233 if(representableDigits<firstInZeroRange)
00234 lastInRepresentableRange=firstInZeroRange-representableDigits;
00235 double val=0;
00236 for(int i=firstInZeroRange-1; i>=lastInRepresentableRange; --i)
00237 val =val*(1<<bits)+digit[i];
00238 return val*(1<<(bits*lastInRepresentableRange));
00239 }
00240
00241 template<int k>
00242 inline void bigunsignedint<k>::print (std::ostream& s) const
00243 {
00244 bool leading=false;
00245
00246
00247 for (int i=n-1; i>=0; i--)
00248 for (int d=hexdigits-1; d>=0; d--)
00249 {
00250
00251 int current = (digit[i]>>(d*4))&0xF;
00252 if (current!=0)
00253 {
00254
00255 s << std::hex << current;
00256 leading = false;
00257 }
00258 else if (!leading) s << std::hex << current;
00259 }
00260 if (leading) s << "0";
00261 s << std::dec;
00262 }
00263
00264 template <int k>
00265 inline std::ostream& operator<< (std::ostream& s, const bigunsignedint<k>& x)
00266 {
00267 x.print(s);
00268 return s;
00269 }
00270
00271
00272
00273 template <int k>
00274 inline bigunsignedint<k> bigunsignedint<k>::operator+ (const bigunsignedint<k>& x) const
00275 {
00276 bigunsignedint<k> result;
00277 std::uint_fast32_t overflow=0;
00278
00279 for (unsigned int i=0; i<n; i++)
00280 {
00281 std::uint_fast32_t sum = static_cast<std::uint_fast32_t>(digit[i]) + static_cast<std::uint_fast32_t>(x.digit[i]) + overflow;
00282 result.digit[i] = sum&bitmask;
00283 overflow = (sum>>bits)&overflowmask;
00284 }
00285 return result;
00286 }
00287
00288 template <int k>
00289 inline bigunsignedint<k> bigunsignedint<k>::operator- (const bigunsignedint<k>& x) const
00290 {
00291 bigunsignedint<k> result;
00292 std::int_fast32_t overflow=0;
00293
00294 for (unsigned int i=0; i<n; i++)
00295 {
00296 std::int_fast32_t diff = static_cast<std::int_fast32_t>(digit[i]) - static_cast<std::int_fast32_t>(x.digit[i]) - overflow;
00297 if (diff>=0)
00298 {
00299 result.digit[i] = static_cast<std::uint16_t>(diff);
00300 overflow = 0;
00301 }
00302 else
00303 {
00304 result.digit[i] = static_cast<std::uint16_t>(diff+bitmask+1);
00305 overflow = 1;
00306 }
00307 }
00308 return result;
00309 }
00310
00311 template <int k>
00312 inline bigunsignedint<k> bigunsignedint<k>::operator* (const bigunsignedint<k>& x) const
00313 {
00314 bigunsignedint<2*k> finalproduct(0);
00315
00316 for (unsigned int m=0; m<n; m++)
00317 {
00318 bigunsignedint<2*k> singleproduct(0);
00319 std::uint_fast32_t overflow(0);
00320 for (unsigned int i=0; i<n; i++)
00321 {
00322 std::uint_fast32_t digitproduct = static_cast<std::uint_fast32_t>(digit[i])*static_cast<std::uint_fast32_t>(x.digit[m])+overflow;
00323 singleproduct.digit[i+m] = static_cast<std::uint16_t>(digitproduct&bitmask);
00324 overflow = (digitproduct>>bits)&bitmask;
00325 }
00326 finalproduct = finalproduct+singleproduct;
00327 }
00328
00329 bigunsignedint<k> result;
00330 for (unsigned int i=0; i<n; i++) result.digit[i] = finalproduct.digit[i];
00331 return result;
00332 }
00333
00334 template <int k>
00335 inline bigunsignedint<k>& bigunsignedint<k>::operator++ ()
00336 {
00337 std::uint_fast32_t overflow=1;
00338
00339 for (unsigned int i=0; i<n; i++)
00340 {
00341 std::uint_fast32_t sum = static_cast<std::uint_fast32_t>(digit[i]) + overflow;
00342 digit[i] = sum&bitmask;
00343 overflow = (sum>>bits)&overflowmask;
00344 }
00345 return *this;
00346 }
00347
00348 template <int k>
00349 inline bigunsignedint<k> bigunsignedint<k>::operator/ (const bigunsignedint<k>& x) const
00350 {
00351 if(x==0)
00352 DUNE_THROW(Dune::MathError, "division by zero!");
00353
00354
00355 bigunsignedint<k> temp(*this);
00356 bigunsignedint<k> result(0);
00357
00358 while (temp>=x)
00359 {
00360 ++result;
00361 temp = temp-x;
00362 }
00363
00364 return result;
00365 }
00366
00367 template <int k>
00368 inline bigunsignedint<k> bigunsignedint<k>::operator% (const bigunsignedint<k>& x) const
00369 {
00370
00371 bigunsignedint<k> temp(*this);
00372
00373 while (temp>=x)
00374 {
00375 temp = temp-x;
00376 }
00377
00378 return temp;
00379 }
00380
00381
00382 template <int k>
00383 inline bigunsignedint<k> bigunsignedint<k>::operator& (const bigunsignedint<k>& x) const
00384 {
00385 bigunsignedint<k> result;
00386 for (unsigned int i=0; i<n; i++)
00387 result.digit[i] = digit[i]&x.digit[i];
00388 return result;
00389 }
00390
00391 template <int k>
00392 inline bigunsignedint<k> bigunsignedint<k>::operator^ (const bigunsignedint<k>& x) const
00393 {
00394 bigunsignedint<k> result;
00395 for (unsigned int i=0; i<n; i++)
00396 result.digit[i] = digit[i]^x.digit[i];
00397 return result;
00398 }
00399
00400 template <int k>
00401 inline bigunsignedint<k> bigunsignedint<k>::operator| (const bigunsignedint<k>& x) const
00402 {
00403 bigunsignedint<k> result;
00404 for (unsigned int i=0; i<n; i++)
00405 result.digit[i] = digit[i]|x.digit[i];
00406 return result;
00407 }
00408
00409 template <int k>
00410 inline bigunsignedint<k> bigunsignedint<k>::operator~ () const
00411 {
00412 bigunsignedint<k> result;
00413 for (unsigned int i=0; i<n; i++)
00414 result.digit[i] = ~digit[i];
00415 return result;
00416 }
00417
00418 template <int k>
00419 inline bigunsignedint<k> bigunsignedint<k>::operator<< (int shift) const
00420 {
00421 bigunsignedint<k> result(0);
00422
00423
00424 int j=shift/bits;
00425 for (int i=n-1-j; i>=0; i--)
00426 result.digit[i+j] = digit[i];
00427
00428
00429 j=shift%bits;
00430 for (int i=n-1; i>=0; i--)
00431 {
00432 unsigned int temp = result.digit[i];
00433 temp = temp<<j;
00434 result.digit[i] = static_cast<std::uint16_t>(temp&bitmask);
00435 temp = temp>>bits;
00436 if (i+1<(int)n)
00437 result.digit[i+1] = result.digit[i+1]|temp;
00438 }
00439
00440 return result;
00441 }
00442
00443 template <int k>
00444 inline bigunsignedint<k> bigunsignedint<k>::operator>> (int shift) const
00445 {
00446 bigunsignedint<k> result(0);
00447
00448
00449 int j=shift/bits;
00450 for (unsigned int i=0; i<n-j; i++)
00451 result.digit[i] = digit[i+j];
00452
00453
00454 j=shift%bits;
00455 for (unsigned int i=0; i<n; i++)
00456 {
00457 std::uint_fast32_t temp = result.digit[i];
00458 temp = temp<<(bits-j);
00459 result.digit[i] = static_cast<std::uint16_t>((temp&compbitmask)>>bits);
00460 if (i>0)
00461 result.digit[i-1] = result.digit[i-1] | (temp&bitmask);
00462 }
00463
00464 return result;
00465 }
00466
00467 template <int k>
00468 inline bool bigunsignedint<k>::operator!= (const bigunsignedint<k>& x) const
00469 {
00470 for (unsigned int i=0; i<n; i++)
00471 if (digit[i]!=x.digit[i]) return true;
00472 return false;
00473 }
00474
00475 template <int k>
00476 inline bool bigunsignedint<k>::operator== (const bigunsignedint<k>& x) const
00477 {
00478 return !((*this)!=x);
00479 }
00480
00481 template <int k>
00482 inline bool bigunsignedint<k>::operator< (const bigunsignedint<k>& x) const
00483 {
00484 for (int i=n-1; i>=0; i--)
00485 if (digit[i]<x.digit[i]) return true;
00486 else if (digit[i]>x.digit[i]) return false;
00487 return false;
00488 }
00489
00490 template <int k>
00491 inline bool bigunsignedint<k>::operator<= (const bigunsignedint<k>& x) const
00492 {
00493 for (int i=n-1; i>=0; i--)
00494 if (digit[i]<x.digit[i]) return true;
00495 else if (digit[i]>x.digit[i]) return false;
00496 return true;
00497 }
00498
00499 template <int k>
00500 inline bool bigunsignedint<k>::operator> (const bigunsignedint<k>& x) const
00501 {
00502 return !((*this)<=x);
00503 }
00504
00505 template <int k>
00506 inline bool bigunsignedint<k>::operator>= (const bigunsignedint<k>& x) const
00507 {
00508 return !((*this)<x);
00509 }
00510
00511
00512 template <int k>
00513 inline bigunsignedint<k> operator+ (const bigunsignedint<k>& x, std::uintmax_t y)
00514 {
00515 bigunsignedint<k> temp(y);
00516 return x+temp;
00517 }
00518
00519 template <int k>
00520 inline bigunsignedint<k> operator- (const bigunsignedint<k>& x, std::uintmax_t y)
00521 {
00522 bigunsignedint<k> temp(y);
00523 return x-temp;
00524 }
00525
00526 template <int k>
00527 inline bigunsignedint<k> operator* (const bigunsignedint<k>& x, std::uintmax_t y)
00528 {
00529 bigunsignedint<k> temp(y);
00530 return x*temp;
00531 }
00532
00533 template <int k>
00534 inline bigunsignedint<k> operator/ (const bigunsignedint<k>& x, std::uintmax_t y)
00535 {
00536 bigunsignedint<k> temp(y);
00537 return x/temp;
00538 }
00539
00540 template <int k>
00541 inline bigunsignedint<k> operator% (const bigunsignedint<k>& x, std::uintmax_t y)
00542 {
00543 bigunsignedint<k> temp(y);
00544 return x%temp;
00545 }
00546
00547 template <int k>
00548 inline bigunsignedint<k> operator+ (std::uintmax_t x, const bigunsignedint<k>& y)
00549 {
00550 bigunsignedint<k> temp(x);
00551 return temp+y;
00552 }
00553
00554 template <int k>
00555 inline bigunsignedint<k> operator- (std::uintmax_t x, const bigunsignedint<k>& y)
00556 {
00557 bigunsignedint<k> temp(x);
00558 return temp-y;
00559 }
00560
00561 template <int k>
00562 inline bigunsignedint<k> operator* (std::uintmax_t x, const bigunsignedint<k>& y)
00563 {
00564 bigunsignedint<k> temp(x);
00565 return temp*y;
00566 }
00567
00568 template <int k>
00569 inline bigunsignedint<k> operator/ (std::uintmax_t x, const bigunsignedint<k>& y)
00570 {
00571 bigunsignedint<k> temp(x);
00572 return temp/y;
00573 }
00574
00575 template <int k>
00576 inline bigunsignedint<k> operator% (std::uintmax_t x, const bigunsignedint<k>& y)
00577 {
00578 bigunsignedint<k> temp(x);
00579 return temp%y;
00580 }
00581
00582
00584 }
00585
00586 namespace std
00587 {
00588 template<int k>
00589 struct numeric_limits<Dune::bigunsignedint<k> >
00590 : private Dune::numeric_limits_helper<Dune::bigunsignedint<k> >
00591 {
00592 public:
00593 static const bool is_specialized = true;
00594
00595 static Dune::bigunsignedint<k> min()
00596 {
00597 return static_cast<Dune::bigunsignedint<k> >(0);
00598 }
00599
00600 static Dune::bigunsignedint<k> max()
00601 {
00602 Dune::bigunsignedint<k> max_;
00603 for(std::size_t i=0; i < Dune::bigunsignedint<k>::n; ++i)
00604
00605 Dune::numeric_limits_helper<Dune::bigunsignedint<k> >::
00606 digit(max_,i)=std::numeric_limits<std::uint16_t>::max();
00607 return max_;
00608 }
00609
00610
00611 static const int digits = Dune::bigunsignedint<k>::bits *
00612 Dune::bigunsignedint<k>::n;
00613 static const bool is_signed = false;
00614 static const bool is_integer = true;
00615 static const bool is_exact = true;
00616 static const int radix = 2;
00617
00618 static Dune::bigunsignedint<k> epsilon()
00619 {
00620 return static_cast<Dune::bigunsignedint<k> >(0);
00621 }
00622
00623 static Dune::bigunsignedint<k> round_error()
00624 {
00625 return static_cast<Dune::bigunsignedint<k> >(0);
00626 }
00627
00628 static const int min_exponent = 0;
00629 static const int min_exponent10 = 0;
00630 static const int max_exponent = 0;
00631 static const int max_exponent10 = 0;
00632
00633 static const bool has_infinity = false;
00634 static const bool has_quiet_NaN = false;
00635 static const bool has_signaling_NaN = false;
00636
00637 static const float_denorm_style has_denorm = denorm_absent;
00638 static const bool has_denorm_loss = false;
00639
00640 static Dune::bigunsignedint<k> infinity() throw()
00641 {
00642 return static_cast<Dune::bigunsignedint<k> >(0);
00643 }
00644
00645 static Dune::bigunsignedint<k> quiet_NaN() throw()
00646 {
00647 return static_cast<Dune::bigunsignedint<k> >(0);
00648 }
00649
00650 static Dune::bigunsignedint<k> signaling_NaN() throw()
00651 {
00652 return static_cast<Dune::bigunsignedint<k> >(0);
00653 }
00654
00655 static Dune::bigunsignedint<k> denorm_min() throw()
00656 {
00657 return static_cast<Dune::bigunsignedint<k> >(0);
00658 }
00659
00660 static const bool is_iec559 = false;
00661 static const bool is_bounded = true;
00662 static const bool is_modulo = true;
00663
00664 static const bool traps = false;
00665 static const bool tinyness_before = false;
00666 static const float_round_style round_style = round_toward_zero;
00667
00668 };
00669
00670 }
00671
00672 DUNE_DEFINE_HASH(DUNE_HASH_TEMPLATE_ARGS(int k),DUNE_HASH_TYPE(Dune::bigunsignedint<k>))
00673
00674 #endif