DUNE-FEM (unstable)

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