/*
* Copyright (c) 2008
* Evan Teran
*
* Permission to use, copy, modify, and distribute this software and its
* documentation for any purpose and without fee is hereby granted, provided
* that the above copyright notice appears in all copies and that both the
* copyright notice and this permission notice appear in supporting
* documentation, and that the same name not be used in advertising or
* publicity pertaining to distribution of the software without specific,
* written prior permission. We make no representations about the
* suitability this software for any purpose. It is provided "as is"
* without express or implied warranty.
*/
#ifndef UINT128_20050119_H_
#define UINT128_20050119_H_
#include <stdexcept>
#include <string>
#include <iostream>
#include <climits>
#include <boost/config.hpp>
#include <boost/static_assert.hpp>
#include <boost/operators.hpp>
#include <boost/cstdint.hpp> // for uint64_t
namespace {
template <typename T>
static void divide(const T &numerator, const T &denominator, T "ient, 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 : boost:
perators<uint128>, boost::shiftable<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;
std::string::const_iterator 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
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
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;
divide(*this, b, *this, remainder);
return *this;
}
uint128 &operator%=(const uint128 &b) {
uint128 quotient;
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;
divide(ii, uint128(radix), ii, remainder);
sz [--i] = "0123456789abcdefghijklmnopqrstuvwxyz"[remainder.to_integer()];
}
return &sz
;
}
};
std:stream &operator<<(std:stream &o, const uint128 &n) {
switch(o.flags() & (std::ios_base::hex | std::ios_base::dec | std::ios_base:ct)) {
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:ct:
o << n.to_string(8);
break;
default:
o << n.to_string();
break;
}
return o;
}
typedef uint128 uint128_t;
#endif