Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
437 lines (347 sloc) 8.31 KB
/*
* The MIT License (MIT)
*
* Copyright (c) 2015 Evan Teran
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in all
* copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*/
#ifndef UINT128_20050119_H_
#define UINT128_20050119_H_
#include <climits>
#include <cstdint>
#include <iostream>
#include <stdexcept>
#include <string>
#include <boost/operators.hpp>
namespace numeric {
namespace detail {
template <typename T>
static void divide(const T &numerator, const T &denominator, T &quotient, T &remainder) {
static const int bits = sizeof(T) * CHAR_BIT;
if (denominator == 0) {
throw std::domain_error("divide by zero");
} else {
T n = numerator;
T d = denominator;
T x = 1;
T answer = 0;
while ((n >= d) && (((d >> (bits - 1)) & 1) == 0)) {
x <<= 1;
d <<= 1;
}
while (x != 0) {
if (n >= d) {
n -= d;
answer |= x;
}
x >>= 1;
d >>= 1;
}
quotient = answer;
remainder = n;
}
}
}
// convinience macro
#define U128_C(s) uint128(#s)
class uint128 : public boost::shiftable<uint128, boost::totally_ordered<uint128, boost::integer_arithmetic<uint128, boost::bitwise<uint128, boost::unit_steppable<uint128 > > > > > {
public:
typedef uint64_t base_type;
public:
static const unsigned int size = (sizeof(base_type) + sizeof(base_type)) * CHAR_BIT;
private:
base_type lo;
base_type hi;
public:
// constructors for all basic types
uint128() : lo(0), hi(0) {
}
uint128(int value) : lo(static_cast<base_type>(value)), hi(0) {
if (value < 0)
hi = static_cast<base_type>(-1);
}
uint128(unsigned int value) : lo(static_cast<base_type>(value)), hi(0) {
}
uint128(float value) : lo(static_cast<base_type>(value)), hi(0) {
}
uint128(double value) : lo(static_cast<base_type>(value)), hi(0) {
}
uint128(const uint128 &value) : lo(value.lo), hi(value.hi) {
}
uint128(base_type value) : lo(value), hi(0) {
}
uint128(const std::string &sz) : lo(0), hi(0) {
// do we have at least one character?
if (!sz.empty()) {
// make some reasonable assumptions
int radix = 10;
bool minus = false;
auto i = sz.begin();
// check for minus sign, i suppose technically this should only apply
// to base 10, but who says that -0x1 should be invalid?
if (*i == '-') {
++i;
minus = true;
}
// check if there is radix changing prefix (0 or 0x)
if (i != sz.end()) {
if (*i == '0') {
radix = 8;
++i;
if (i != sz.end()) {
if (*i == 'x') {
radix = 16;
++i;
}
}
}
while (i != sz.end()) {
unsigned int n;
const char ch = *i;
if (ch >= 'A' && ch <= 'Z') {
if (((ch - 'A') + 10) < radix) {
n = (ch - 'A') + 10;
} else {
break;
}
} else if (ch >= 'a' && ch <= 'z') {
if (((ch - 'a') + 10) < radix) {
n = (ch - 'a') + 10;
} else {
break;
}
} else if (ch >= '0' && ch <= '9') {
if ((ch - '0') < radix) {
n = (ch - '0');
} else {
break;
}
} else {
/* completely invalid character */
break;
}
(*this) *= radix;
(*this) += n;
++i;
}
}
// if this was a negative number, do that two's compliment madness :-P
if (minus) {
*this = -*this;
}
}
}
uint128 &operator=(const uint128 &other) {
if (&other != this) {
lo = other.lo;
hi = other.hi;
}
return *this;
}
public: // comparison operators
bool operator==(const uint128 &o) const {
return hi == o.hi && lo == o.lo;
}
bool operator<(const uint128 &o) const {
return (hi == o.hi) ? lo < o.lo : hi < o.hi;
}
public: // unary operators
bool operator!() const {
return !(hi != 0 || lo != 0);
}
uint128 operator-() const {
// standard 2's compliment negation
return ~uint128(*this) + 1;
}
uint128 operator~() const {
uint128 t(*this);
t.lo = ~t.lo;
t.hi = ~t.hi;
return t;
}
uint128 &operator++() {
if (++lo == 0) {
++hi;
}
return *this;
}
uint128 &operator--() {
if (lo-- == 0) {
--hi;
}
return *this;
}
public: // basic math operators
uint128 &operator+=(const uint128 &b) {
const base_type old_lo = lo;
lo += b.lo;
hi += b.hi;
if (lo < old_lo) {
++hi;
}
return *this;
}
uint128 &operator-=(const uint128 &b) {
// it happens to be way easier to write it
// this way instead of make a subtraction algorithm
return *this += -b;
}
uint128 &operator*=(const uint128 &b) {
// check for multiply by 0
// result is always 0 :-P
if (b == 0) {
hi = 0;
lo = 0;
} else if (b != 1) {
// check we aren't multiplying by 1
uint128 a(*this);
uint128 t = b;
lo = 0;
hi = 0;
for (unsigned int i = 0; i < size; ++i) {
if ((t & 1) != 0) {
*this += (a << i);
}
t >>= 1;
}
}
return *this;
}
uint128 &operator|=(const uint128 &b) {
hi |= b.hi;
lo |= b.lo;
return *this;
}
uint128 &operator&=(const uint128 &b) {
hi &= b.hi;
lo &= b.lo;
return *this;
}
uint128 &operator^=(const uint128 &b) {
hi ^= b.hi;
lo ^= b.lo;
return *this;
}
uint128 &operator/=(const uint128 &b) {
uint128 remainder;
detail::divide(*this, b, *this, remainder);
return *this;
}
uint128 &operator%=(const uint128 &b) {
uint128 quotient;
detail::divide(*this, b, quotient, *this);
return *this;
}
uint128 &operator<<=(const uint128 &rhs) {
unsigned int n = rhs.to_integer();
if (n >= size) {
hi = 0;
lo = 0;
} else {
const unsigned int halfsize = size / 2;
if (n >= halfsize) {
n -= halfsize;
hi = lo;
lo = 0;
}
if (n != 0) {
// shift high half
hi <<= n;
const base_type mask(~(base_type(-1) >> n));
// and add them to high half
hi |= (lo & mask) >> (halfsize - n);
// and finally shift also low half
lo <<= n;
}
}
return *this;
}
uint128 &operator>>=(const uint128 &rhs) {
unsigned int n = rhs.to_integer();
if (n >= size) {
hi = 0;
lo = 0;
} else {
const unsigned int halfsize = size / 2;
if (n >= halfsize) {
n -= halfsize;
lo = hi;
hi = 0;
}
if (n != 0) {
// shift low half
lo >>= n;
// get lower N bits of high half
const base_type mask(~(base_type(-1) << n));
// and add them to low qword
lo |= (hi & mask) << (halfsize - n);
// and finally shift also high half
hi >>= n;
}
}
return *this;
}
public:
int to_integer() const {
return static_cast<int>(lo);
}
base_type to_base_type() const {
return lo;
}
std::string to_string(unsigned int radix = 10) const {
if (*this == 0) {
return "0";
}
if (radix < 2 || radix > 37) {
return "(invalid radix)";
}
// at worst it will be size digits (base 2) so make our buffer
// that plus room for null terminator
static char sz[size + 1];
sz[sizeof(sz) - 1] = '\0';
uint128 ii(*this);
int i = size - 1;
while (ii != 0 && i) {
uint128 remainder;
detail::divide(ii, uint128(radix), ii, remainder);
sz[--i] = "0123456789abcdefghijklmnopqrstuvwxyz"[remainder.to_integer()];
}
return &sz[i];
}
};
std::ostream &operator<<(std::ostream &o, const uint128 &n) {
switch (o.flags() & (std::ios_base::hex | std::ios_base::dec | std::ios_base::oct)) {
case std::ios_base::hex:
o << n.to_string(16);
break;
case std::ios_base::dec:
o << n.to_string(10);
break;
case std::ios_base::oct:
o << n.to_string(8);
break;
default:
o << n.to_string();
break;
}
return o;
}
typedef uint128 uint128_t;
}
#endif