Dune Core Modules (2.6.0)

bigunsignedint.hh
Go to the documentation of this file.
1// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2// vi: set et ts=4 sw=2 sts=2:
3
4#ifndef DUNE_BIGUNSIGNEDINT_HH
5#define DUNE_BIGUNSIGNEDINT_HH
6
7#include <iostream>
8#include <limits>
9#include <cstdint>
10#include <cstdlib>
11#include <type_traits>
13#include <dune/common/hash.hh>
14
21namespace Dune
22{
23#if HAVE_MPI
24 template<class K>
25 struct MPITraits;
26#endif
27
33 namespace Impl {
34
35 // numeric_limits_helper provides std::numeric_limits access to the internals
36 // of bigunsignedint. Previously, the correct specialization of std::numeric_limits
37 // was a friend of bigunsignedint, but that creates problems on recent versions
38 // of clang with the alternative libc++ library, because that library declares the
39 // base template of std::numeric_limits as a class and clang subsequently complains
40 // if the friend declaration uses 'struct'. Unfortunately, libstdc++ uses a struct,
41 // making it impossible to keep clang happy for both standard libraries.
42 // So we move the access helper functionality into a custom struct and simply let
43 // the numeric_limits specialization inherit from the helper.
44
45 template<typename T>
46 struct numeric_limits_helper
47 {
48
49 protected:
50
51 static std::uint16_t& digit(T& big_unsigned_int, std::size_t i)
52 {
53 return big_unsigned_int.digit[i];
54 }
55
56 };
57
58 }
59
69 template<int k>
71 public:
72
73 // unsigned short is 16 bits wide, n is the number of digits needed
74 enum { bits=std::numeric_limits<std::uint16_t>::digits, n=k/bits+(k%bits!=0),
75 hexdigits=4, bitmask=0xFFFF, compbitmask=0xFFFF0000,
76 overflowmask=0x1 };
77
80
82 template<typename Signed>
83 bigunsignedint (Signed x, typename std::enable_if<std::is_integral<Signed>::value && std::is_signed<Signed>::value>::type* = 0);
84
86 bigunsignedint (std::uintmax_t x);
87
89 void print (std::ostream& s) const ;
90
93 bigunsignedint<k>& operator+= (const bigunsignedint<k>& x);
94
97 bigunsignedint<k>& operator-= (const bigunsignedint<k>& x);
98
101 bigunsignedint<k>& operator*= (const bigunsignedint<k>& x);
102
105
110 bigunsignedint<k>& operator/= (const bigunsignedint<k>& x);
111
116 bigunsignedint<k>& operator%= (const bigunsignedint<k>& x);
117
120 bigunsignedint<k>& operator&= (const bigunsignedint<k>& x);
121
124 bigunsignedint<k>& operator^= (const bigunsignedint<k>& x);
125
128 bigunsignedint<k>& operator|= (const bigunsignedint<k>& x);
129
132
133
135 bigunsignedint<k> operator<< (int i) const;
136
138 bigunsignedint<k> operator>> (int i) const;
139
140
142 bool operator< (const bigunsignedint<k>& x) const;
143
145 bool operator<= (const bigunsignedint<k>& x) const;
146
148 bool operator> (const bigunsignedint<k>& x) const;
149
151 bool operator>= (const bigunsignedint<k>& x) const;
152
154 bool operator== (const bigunsignedint<k>& x) const;
155
157 bool operator!= (const bigunsignedint<k>& x) const;
158
159
161 // operator unsigned int () const;
162 std::uint_least32_t touint() const;
168 double todouble() const;
169
170 friend class bigunsignedint<k/2>;
171 friend struct Impl::numeric_limits_helper< bigunsignedint<k> >;
172
173 inline friend std::size_t hash_value(const bigunsignedint& arg)
174 {
175 return hash_range(arg.digit,arg.digit + arg.n);
176 }
177
178 private:
179 std::uint16_t digit[n];
180#if HAVE_MPI
181 friend struct MPITraits<bigunsignedint<k> >;
182#endif
183 inline void assign(std::uintmax_t x);
184
185
186 } ;
187
188 // Constructors
189 template<int k>
191 {
192 assign(0u);
193 }
194
195 template<int k>
196 template<typename Signed>
197 bigunsignedint<k>::bigunsignedint (Signed y, typename std::enable_if<std::is_integral<Signed>::value && std::is_signed<Signed>::value>::type*)
198 {
199 if (y < 0)
200 DUNE_THROW(Dune::Exception, "Trying to construct a Dune::bigunsignedint from a negative integer: " << y);
201 assign(y);
202 }
203
204 template<int k>
206 {
207 assign(x);
208 }
209 template<int k>
210 void bigunsignedint<k>::assign(std::uintmax_t x)
211 {
212 static const int no=std::min(static_cast<int>(n),
213 static_cast<int>(std::numeric_limits<std::uintmax_t>::digits/bits));
214
215 for(int i=0; i<no; ++i) {
216 digit[i] = (x&bitmask);
217 x=x>>bits;
218 }
219 for (unsigned int i=no; i<n; i++) digit[i]=0;
220 }
221
222 // export
223 template<int k>
224 inline std::uint_least32_t bigunsignedint<k>::touint () const
225 {
226 return (digit[1]<<bits)+digit[0];
227 }
228
229 template<int k>
230 inline double bigunsignedint<k>::todouble() const
231 {
232 int firstInZeroRange=n;
233 for(int i=n-1; i>=0; --i)
234 if(digit[i]!=0)
235 break;
236 else
237 --firstInZeroRange;
238 int representableDigits=std::numeric_limits<double>::digits/bits;
239 int lastInRepresentableRange=0;
240 if(representableDigits<firstInZeroRange)
241 lastInRepresentableRange=firstInZeroRange-representableDigits;
242 double val=0;
243 for(int i=firstInZeroRange-1; i>=lastInRepresentableRange; --i)
244 val =val*(1<<bits)+digit[i];
245 return val*(1<<(bits*lastInRepresentableRange));
246 }
247 // print
248 template<int k>
249 inline void bigunsignedint<k>::print (std::ostream& s) const
250 {
251 bool leading=false;
252
253 // print from left to right
254 for (int i=n-1; i>=0; i--)
255 for (int d=hexdigits-1; d>=0; d--)
256 {
257 // extract one hex digit
258 int current = (digit[i]>>(d*4))&0xF;
259 if (current!=0)
260 {
261 // s.setf(std::ios::noshowbase);
262 s << std::hex << current;
263 leading = false;
264 }
265 else if (!leading) s << std::hex << current;
266 }
267 if (leading) s << "0";
268 s << std::dec;
269 }
270
271 template <int k>
272 inline std::ostream& operator<< (std::ostream& s, const bigunsignedint<k>& x)
273 {
274 x.print(s);
275 return s;
276 }
277
278 #define DUNE_BINOP(OP) \
279 template <int k> \
280 inline bigunsignedint<k> bigunsignedint<k>::operator OP (const bigunsignedint<k> &x) const \
281 { \
282 auto temp = *this; \
283 temp OP##= x; \
284 return temp; \
285 }
286
287 DUNE_BINOP(+)
288 DUNE_BINOP(-)
289 DUNE_BINOP(*)
290 DUNE_BINOP(/)
291 DUNE_BINOP(%)
292 DUNE_BINOP(&)
293 DUNE_BINOP(^)
294 DUNE_BINOP(|)
295
296 #undef DUNE_BINOP
297
298 template <int k>
299 inline bigunsignedint<k>& bigunsignedint<k>::operator+= (const bigunsignedint<k>& x)
300 {
301 std::uint_fast32_t overflow=0;
302
303 for (unsigned int i=0; i<n; i++)
304 {
305 std::uint_fast32_t sum = static_cast<std::uint_fast32_t>(digit[i]) + static_cast<std::uint_fast32_t>(x.digit[i]) + overflow;
306 digit[i] = sum&bitmask;
307 overflow = (sum>>bits)&overflowmask;
308 }
309 return *this;
310 }
311
312 template <int k>
313 inline bigunsignedint<k>& bigunsignedint<k>::operator-= (const bigunsignedint<k>& x)
314 {
315 std::int_fast32_t overflow=0;
316
317 for (unsigned int i=0; i<n; i++)
318 {
319 std::int_fast32_t diff = static_cast<std::int_fast32_t>(digit[i]) - static_cast<std::int_fast32_t>(x.digit[i]) - overflow;
320 if (diff>=0)
321 {
322 digit[i] = static_cast<std::uint16_t>(diff);
323 overflow = 0;
324 }
325 else
326 {
327 digit[i] = static_cast<std::uint16_t>(diff+bitmask+1);
328 overflow = 1;
329 }
330 }
331 return *this;
332 }
333
334 template <int k>
335 inline bigunsignedint<k>& bigunsignedint<k>::operator*= (const bigunsignedint<k>& x)
336 {
337 bigunsignedint<2*k> finalproduct(0);
338
339 for (unsigned int m=0; m<n; m++) // digit in right factor
340 {
341 bigunsignedint<2*k> singleproduct(0);
342 std::uint_fast32_t overflow(0);
343 for (unsigned int i=0; i<n; i++)
344 {
345 std::uint_fast32_t digitproduct = static_cast<std::uint_fast32_t>(digit[i])*static_cast<std::uint_fast32_t>(x.digit[m])+overflow;
346 singleproduct.digit[i+m] = static_cast<std::uint16_t>(digitproduct&bitmask);
347 overflow = (digitproduct>>bits)&bitmask;
348 }
349 finalproduct = finalproduct+singleproduct;
350 }
351
352 for (unsigned int i=0; i<n; i++) digit[i] = finalproduct.digit[i];
353 return *this;
354 }
355
356 template <int k>
358 {
359 std::uint_fast32_t overflow=1;
360
361 for (unsigned int i=0; i<n; i++)
362 {
363 std::uint_fast32_t sum = static_cast<std::uint_fast32_t>(digit[i]) + overflow;
364 digit[i] = sum&bitmask;
365 overflow = (sum>>bits)&overflowmask;
366 }
367 return *this;
368 }
369
370 template <int k>
372 {
373 if(x==0)
374 DUNE_THROW(Dune::MathError, "division by zero!");
375
376 // better slow than nothing
377 bigunsignedint<k> result(0);
378
379 while (*this>=x)
380 {
381 ++result;
382 *this -= x;
383 }
384
385 *this = result;
386 return *this;
387 }
388
389 template <int k>
390 inline bigunsignedint<k>& bigunsignedint<k>::operator%= (const bigunsignedint<k>& x)
391 {
392 // better slow than nothing
393 while (*this>=x)
394 {
395 *this -= x;
396 }
397
398 return *this;
399 }
400
401 template <int k>
402 inline bigunsignedint<k>& bigunsignedint<k>::operator&= (const bigunsignedint<k>& x)
403 {
404 for (unsigned int i=0; i<n; i++)
405 digit[i] = digit[i]&x.digit[i];
406 return *this;
407 }
408
409 template <int k>
410 inline bigunsignedint<k>& bigunsignedint<k>::operator^= (const bigunsignedint<k>& x)
411 {
412 for (unsigned int i=0; i<n; i++)
413 digit[i] = digit[i]^x.digit[i];
414 return *this;
415 }
416
417 template <int k>
418 inline bigunsignedint<k>& bigunsignedint<k>::operator|= (const bigunsignedint<k>& x)
419 {
420 for (unsigned int i=0; i<n; i++)
421 digit[i] = digit[i]|x.digit[i];
422 return *this;
423 }
424
425 template <int k>
427 {
428 bigunsignedint<k> result;
429 for (unsigned int i=0; i<n; i++)
430 result.digit[i] = ~digit[i];
431 return result;
432 }
433
434 template <int k>
436 {
437 bigunsignedint<k> result(0);
438
439 // multiples of bits
440 int j=shift/bits;
441 for (int i=n-1-j; i>=0; i--)
442 result.digit[i+j] = digit[i];
443
444 // remainder
445 j=shift%bits;
446 for (int i=n-1; i>=0; i--)
447 {
448 unsigned int temp = result.digit[i];
449 temp = temp<<j;
450 result.digit[i] = static_cast<std::uint16_t>(temp&bitmask);
451 temp = temp>>bits;
452 if (i+1<(int)n)
453 result.digit[i+1] = result.digit[i+1]|temp;
454 }
455
456 return result;
457 }
458
459 template <int k>
461 {
462 bigunsignedint<k> result(0);
463
464 // multiples of bits
465 int j=shift/bits;
466 for (unsigned int i=0; i<n-j; i++)
467 result.digit[i] = digit[i+j];
468
469 // remainder
470 j=shift%bits;
471 for (unsigned int i=0; i<n; i++)
472 {
473 std::uint_fast32_t temp = result.digit[i];
474 temp = temp<<(bits-j);
475 result.digit[i] = static_cast<std::uint16_t>((temp&compbitmask)>>bits);
476 if (i>0)
477 result.digit[i-1] = result.digit[i-1] | (temp&bitmask);
478 }
479
480 return result;
481 }
482
483 template <int k>
485 {
486 for (unsigned int i=0; i<n; i++)
487 if (digit[i]!=x.digit[i]) return true;
488 return false;
489 }
490
491 template <int k>
493 {
494 return !((*this)!=x);
495 }
496
497 template <int k>
499 {
500 for (int i=n-1; i>=0; i--)
501 if (digit[i]<x.digit[i]) return true;
502 else if (digit[i]>x.digit[i]) return false;
503 return false;
504 }
505
506 template <int k>
508 {
509 for (int i=n-1; i>=0; i--)
510 if (digit[i]<x.digit[i]) return true;
511 else if (digit[i]>x.digit[i]) return false;
512 return true;
513 }
514
515 template <int k>
517 {
518 return !((*this)<=x);
519 }
520
521 template <int k>
523 {
524 return !((*this)<x);
525 }
526
527
528 template <int k>
529 inline bigunsignedint<k> operator+ (const bigunsignedint<k>& x, std::uintmax_t y)
530 {
531 bigunsignedint<k> temp(y);
532 return x+temp;
533 }
534
535 template <int k>
536 inline bigunsignedint<k> operator- (const bigunsignedint<k>& x, std::uintmax_t y)
537 {
538 bigunsignedint<k> temp(y);
539 return x-temp;
540 }
541
542 template <int k>
543 inline bigunsignedint<k> operator* (const bigunsignedint<k>& x, std::uintmax_t y)
544 {
545 bigunsignedint<k> temp(y);
546 return x*temp;
547 }
548
549 template <int k>
550 inline bigunsignedint<k> operator/ (const bigunsignedint<k>& x, std::uintmax_t y)
551 {
552 bigunsignedint<k> temp(y);
553 return x/temp;
554 }
555
556 template <int k>
557 inline bigunsignedint<k> operator% (const bigunsignedint<k>& x, std::uintmax_t y)
558 {
559 bigunsignedint<k> temp(y);
560 return x%temp;
561 }
562
563 template <int k>
564 inline bigunsignedint<k> operator+ (std::uintmax_t x, const bigunsignedint<k>& y)
565 {
566 bigunsignedint<k> temp(x);
567 return temp+y;
568 }
569
570 template <int k>
571 inline bigunsignedint<k> operator- (std::uintmax_t x, const bigunsignedint<k>& y)
572 {
573 bigunsignedint<k> temp(x);
574 return temp-y;
575 }
576
577 template <int k>
578 inline bigunsignedint<k> operator* (std::uintmax_t x, const bigunsignedint<k>& y)
579 {
580 bigunsignedint<k> temp(x);
581 return temp*y;
582 }
583
584 template <int k>
585 inline bigunsignedint<k> operator/ (std::uintmax_t x, const bigunsignedint<k>& y)
586 {
587 bigunsignedint<k> temp(x);
588 return temp/y;
589 }
590
591 template <int k>
592 inline bigunsignedint<k> operator% (std::uintmax_t x, const bigunsignedint<k>& y)
593 {
594 bigunsignedint<k> temp(x);
595 return temp%y;
596 }
597
598
600}
601
602namespace std
603{
604 template<int k>
605 struct numeric_limits<Dune::bigunsignedint<k> >
606 : private Dune::Impl::numeric_limits_helper<Dune::bigunsignedint<k> > // for access to internal state of bigunsignedint
607 {
608 public:
609 static const bool is_specialized = true;
610
611 static Dune::bigunsignedint<k> min()
612 {
613 return static_cast<Dune::bigunsignedint<k> >(0);
614 }
615
616 static Dune::bigunsignedint<k> max()
617 {
619 for(std::size_t i=0; i < Dune::bigunsignedint<k>::n; ++i)
620 // access internal state via the helper base class
621 Dune::Impl::numeric_limits_helper<Dune::bigunsignedint<k> >::
622 digit(max_,i)=std::numeric_limits<std::uint16_t>::max();
623 return max_;
624 }
625
626
627 static const int digits = Dune::bigunsignedint<k>::bits *
629 static const bool is_signed = false;
630 static const bool is_integer = true;
631 static const bool is_exact = true;
632 static const int radix = 2;
633
634 static Dune::bigunsignedint<k> epsilon()
635 {
636 return static_cast<Dune::bigunsignedint<k> >(0);
637 }
638
639 static Dune::bigunsignedint<k> round_error()
640 {
641 return static_cast<Dune::bigunsignedint<k> >(0);
642 }
643
644 static const int min_exponent = 0;
645 static const int min_exponent10 = 0;
646 static const int max_exponent = 0;
647 static const int max_exponent10 = 0;
648
649 static const bool has_infinity = false;
650 static const bool has_quiet_NaN = false;
651 static const bool has_signaling_NaN = false;
652
653 static const float_denorm_style has_denorm = denorm_absent;
654 static const bool has_denorm_loss = false;
655
656 static Dune::bigunsignedint<k> infinity() noexcept
657 {
658 return static_cast<Dune::bigunsignedint<k> >(0);
659 }
660
661 static Dune::bigunsignedint<k> quiet_NaN() noexcept
662 {
663 return static_cast<Dune::bigunsignedint<k> >(0);
664 }
665
666 static Dune::bigunsignedint<k> signaling_NaN() noexcept
667 {
668 return static_cast<Dune::bigunsignedint<k> >(0);
669 }
670
671 static Dune::bigunsignedint<k> denorm_min() noexcept
672 {
673 return static_cast<Dune::bigunsignedint<k> >(0);
674 }
675
676 static const bool is_iec559 = false;
677 static const bool is_bounded = true;
678 static const bool is_modulo = true;
679
680 static const bool traps = false;
681 static const bool tinyness_before = false;
682 static const float_round_style round_style = round_toward_zero;
683
684 };
685
686}
687
689
690#endif
Base class for Dune-Exceptions.
Definition: exceptions.hh:94
Default exception class for mathematical errors.
Definition: exceptions.hh:239
Portable very large unsigned integers.
Definition: bigunsignedint.hh:70
bigunsignedint< k > operator|(const bigunsignedint< k > &x) const
bitwise or
bigunsignedint< k > operator^(const bigunsignedint< k > &x) const
bitwise exor
bigunsignedint< k > operator*(const bigunsignedint< k > &x) const
multiply
bigunsignedint< k > operator%(const bigunsignedint< k > &x) const
bigunsignedint< k > operator-(const bigunsignedint< k > &x) const
subtract
bigunsignedint< k > operator&(const bigunsignedint< k > &x) const
bitwise and
bigunsignedint< k > operator/(const bigunsignedint< k > &x) const
bigunsignedint< k > operator+(const bigunsignedint< k > &x) const
add
A few common exception classes.
#define DUNE_THROW(E, m)
Definition: exceptions.hh:216
bigunsignedint< k > operator<<(int i) const
left shift
Definition: bigunsignedint.hh:435
bool operator<=(const bigunsignedint< k > &x) const
less than or equal
Definition: bigunsignedint.hh:507
void print(std::ostream &s) const
Print number in hex notation.
Definition: bigunsignedint.hh:249
bool operator<(const bigunsignedint< k > &x) const
less than
Definition: bigunsignedint.hh:498
bool operator==(const bigunsignedint< k > &x) const
equal
Definition: bigunsignedint.hh:492
bool operator!=(const bigunsignedint< k > &x) const
not equal
Definition: bigunsignedint.hh:484
bigunsignedint()
Construct uninitialized.
Definition: bigunsignedint.hh:190
bool operator>=(const bigunsignedint< k > &x) const
greater or equal
Definition: bigunsignedint.hh:522
bigunsignedint< k > operator>>(int i) const
right shift
Definition: bigunsignedint.hh:460
bigunsignedint< k > operator~() const
bitwise complement
Definition: bigunsignedint.hh:426
bigunsignedint< k > & operator++()
prefix increment
Definition: bigunsignedint.hh:357
double todouble() const
Convert to a double.
Definition: bigunsignedint.hh:230
bool operator>(const bigunsignedint< k > &x) const
greater than
Definition: bigunsignedint.hh:516
std::uint_least32_t touint() const
export to other types
Definition: bigunsignedint.hh:224
Support for calculating hash values of objects.
#define DUNE_DEFINE_HASH(template_args, type)
Defines the required struct specialization to make type hashable via Dune::hash.
Definition: hash.hh:98
#define DUNE_HASH_TYPE(...)
Wrapper macro for the type to be hashed in DUNE_DEFINE_HASH.
Definition: hash.hh:115
#define DUNE_HASH_TEMPLATE_ARGS(...)
Wrapper macro for the template arguments in DUNE_DEFINE_HASH.
Definition: hash.hh:107
Dune namespace.
Definition: alignedallocator.hh:10
std::size_t hash_range(It first, It last)
Hashes all elements in the range [first,last) and returns the combined hash.
Definition: hash.hh:320
void assign(T &dst, const T &src, bool mask)
masked Simd assignment (scalar version)
Definition: simd.hh:421
STL namespace.
A traits class describing the mapping of types onto MPI_Datatypes.
Definition: mpitraits.hh:38
Creative Commons License   |  Legal Statements / Impressum  |  Hosted by TU Dresden  |  generated with Hugo v0.111.3 (Nov 24, 23:30, 2024)