#ifndef UINT128_20050119_H_
#define UINT128_20050119_H_

#include "string.hpp"

#include <climits>
#include <iostream>
#include <stdexcept>
#include <stdint.h>
#include <string>

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;
  }
}
} 

#define U128_C(s) uint128(#s)

class 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:

  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(base_type lo, base_type hi)
      : lo(lo)
      , hi(hi) {}

  uint128(const datastax::String& sz)
      : lo(0)
      , hi(0) {

    if (!sz.empty()) {

      int radix = 10;
      bool minus = false;

      datastax::String::const_iterator i = sz.begin();

      if (*i == '-') {
        ++i;
        minus = true;
      }

      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 {

            break;
          }

          (*this) *= radix;
          (*this) += n;

          ++i;
        }
      }

      if (minus) {
        *this = -*this;
      }
    }
  }

  uint128& operator=(const uint128& other) {
    if (&other != this) {
      lo = other.lo;
      hi = other.hi;
    }
    return *this;
  }

public: 
  bool operator==(const uint128& o) const { return hi == o.hi && lo == o.lo; }

  bool operator!=(const uint128& o) const { return !(*this == o); }

  bool operator<(const uint128& o) const { return (hi == o.hi) ? lo < o.lo : hi < o.hi; }

  bool operator>=(const uint128& o) const { return !(*this < o); }

public: 
  bool operator!() const { return !(hi != 0 || lo != 0); }

  uint128 operator-() const {

    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: 
  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) {

    return *this += -b;
  }

  uint128 operator+(const uint128& b) const { return uint128(*this) += b; }

  uint128& operator*=(const uint128& b) {

    if (b == 0) {
      hi = 0;
      lo = 0;
    } else if (b != 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) const { return uint128(*this) &= b; }

  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) {

        hi <<= n;

        const base_type mask(~(base_type(-1) >> n));

        hi |= (lo & mask) >> (halfsize - n);

        lo <<= n;
      }
    }

    return *this;
  }

  uint128 operator<<(const uint128& rhs) const { return uint128(*this) <<= rhs; }

  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) {

        lo >>= n;

        const base_type mask(~(base_type(-1) << n));

        lo |= (hi & mask) << (halfsize - n);

        hi >>= n;
      }
    }

    return *this;
  }

  uint128 operator>>(const uint128& rhs) const { return uint128(*this) >>= rhs; }

public:
  int to_integer() const { return static_cast<int>(lo); }

  base_type to_base_type() const { return lo; }

  datastax::String to_string(unsigned int radix = 10) const {
    if (*this == 0) {
      return "0";
    }

    if (radix < 2 || radix > 37) {
      return "(invalid radix)";
    }

    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];
  }
};

inline 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
/*
 * 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 "string.hpp"

#include <climits>
#include <iostream>
#include <stdexcept>
#include <stdint.h>
#include <string>

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;
  }
}
} // namespace detail

// convinience macro
#define U128_C(s) uint128(#s)

class 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(base_type lo, base_type hi)
      : lo(lo)
      , hi(hi) {}

  uint128(const datastax::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;

      datastax::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 :-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 !(*this == o); }

  bool operator<(const uint128& o) const { return (hi == o.hi) ? lo < o.lo : hi < o.hi; }

  bool operator>=(const uint128& o) const { return !(*this < o); }

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) const { return uint128(*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) const { return uint128(*this) &= b; }

  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) const { return uint128(*this) <<= rhs; }

  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;
  }

  uint128 operator>>(const uint128& rhs) const { return uint128(*this) >>= rhs; }

public:
  int to_integer() const { return static_cast<int>(lo); }

  base_type to_base_type() const { return lo; }

  datastax::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];
  }
};

inline 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;

} // namespace numeric

#endif
