integer.h

Go to the documentation of this file.

/**************************************************************
 **
 ** @file base/integer.h
 **
 ** Copyright (C) 2012  Xpace, LLC.  All rights reserved
 **
 ** www.xpace.net
 **
 **************************************************************/

#ifndef XPACE_INTEGER_H
#define XPACE_INTEGER_H

#ifdef _WIN32
#undef min
#undef max
#endif

#include <limits>
#include <vector>
#include <limits>
#include <cstring>

#include "base/types.h"

namespace Xpace
{
  template<size_t SIZE>
  class BigInt;

  template<size_t SIZE>
  class BigUint
  {
    friend class BigInt<SIZE>;
  public:
    BigUint
      (uint64 = 0);

    template<size_t RS>
    BigUint
      (const BigUint<RS>&);

    bool operator==
      (const BigUint<SIZE>&)
      const;
    bool operator==
      (uint)
      const;
    bool operator!=
      (const BigUint<SIZE>&)
      const;
    bool operator<
      (const BigUint<SIZE>& rhs)
      const
    {
      return lt(rhs);
    }
    bool operator>
      (const BigUint<SIZE>& rhs)
      const
    {
      return gt(rhs);
    }

    BigUint<SIZE> operator+
      (const BigUint<SIZE>&)
      const;
    BigUint<SIZE> operator+
      (uint64)
      const;
    BigUint<SIZE> operator-
      (const BigUint<SIZE>&)
      const;
    BigUint<SIZE> operator*
      (uint32)
      const;
    BigUint<SIZE> operator/
      (uint32)
      const;
    BigUint<SIZE> div
      (uint32, 
       uint32* rem)
      const;

    uint64 operator[]
      (size_t)
      const;
    uint64& operator[]
      (size_t);
    const BytesRef get
      ()
      const;
    void set
      (const BytesRef&);

    #ifdef QBYTEARRAY_H
    operator const QByteArray
      ()
      const;
    #endif

  protected:
    bool lt
      (const BigUint&)
      const;
    bool gt
      (const BigUint&)
      const;

    uint64 vals[SIZE];

  private:
    static
    uint64 add_carry
      (uint64 a,
       uint64 b,
       bool* c);

    static
    uint64 sub_borrow
      (uint64 a,
       uint64 b,
       bool* borrow);
  };

  template<size_t SIZE>
  class BigInt : public BigUint<SIZE>
  {
  public:
    BigInt
      (int64 = 0);
    template<size_t RS>
    BigInt
      (const BigInt<RS>&);

    BigInt
      (const BigUint<SIZE>& rhs)
    {
      memcpy(this, &rhs, sizeof(this));    // MSVC can't see rhs.vals
      set_minus(false);
    }
    operator BigUint<SIZE>
      ()
      const
    {
      BigUint<SIZE> ret;
      memcpy(&ret.vals, &this->vals, sizeof(this->vals));
    }

    bool operator==
      (const BigInt&)
      const;
    bool operator==
      (int)
      const;
    bool operator!=
      (const BigInt&)
      const;
    bool operator<
      (const BigInt&)
      const;
    bool operator>
      (const BigInt&)
      const;

    BigInt operator+
      (const BigInt& rhs)
      const
    {
      return BigUint<SIZE>(*this) + rhs;
    }
    BigInt operator+
      (int64 n)
      const
    {
      return BigUint<SIZE>(*this) + n;
    }
    BigInt operator-
      (const BigInt& rhs)
      const
    {
      return BigUint<SIZE>(*this) - rhs;
    }
    BigInt operator*
      (uint32)
      const;
    BigInt operator/
      (uint32)
      const;
    BigInt div
      (uint32, 
       uint32* rem)
      const;

  private:
    bool is_minus
      ()
      const
    {
      return !!(this->vals[SIZE - 1] & 0xF000000000000000);
    }

    uint64 strip_minus
      (uint64 n)
    {
      return n & 0x7FFFFFFFFFFFFFFF;
    }

    void set_minus
      (bool m)
    {
      this->vals[SIZE - 1] = strip_minus(this->vals[SIZE - 1]) | (m ? 0xF000000000000000 : 0);
    }
  };

  inline
  static int type_max
    (int)
  {
    return std::numeric_limits<int>::max();
  }

  inline
  static uint type_max
    (uint)
  {
    return std::numeric_limits<uint>::max();
  }

  inline
  static int64 type_max
    (int64)
  {
    return std::numeric_limits<int64>::max();
  }

  inline
  static uint64 type_max
    (uint64)
  {
    return std::numeric_limits<uint64>::max();
  }

  template <size_t SIZE>
  inline
  static BigInt<SIZE> type_max
    (BigInt<SIZE>)
  {
      Xpace::BigInt<SIZE> ret;
      for (size_t i(0); i < SIZE - 1; ++i)
        ret[i] = ~0;
      ret[SIZE - 1] = std::numeric_limits<Xpace::int64>::max();
      return ret;
  }

  template <size_t SIZE>
  inline
  static BigUint<SIZE> type_max
    (BigUint<SIZE>)
  {
    BigUint<SIZE> ret;
    for (size_t i(0); i < SIZE; ++i)
      ret[i] = ~0;
    return ret;
  }

  inline
  static int type_min
    (int)
  {
    return std::numeric_limits<int>::min();
  }

  inline
  static uint type_min
    (uint)
  {
    return std::numeric_limits<uint>::min();
  }

  inline
  static int64 type_min
    (int64)
  {
    return std::numeric_limits<int64>::min();
  }

  inline
  static uint64 type_min
    (uint64)
  {
    return std::numeric_limits<uint64>::min();
  }
  
  template <size_t SIZE>
  inline
  static BigInt<SIZE> type_min
    (BigInt<SIZE>)
  {
      Xpace::BigInt<SIZE> ret;
      for (size_t i(0); i < SIZE - 1; ++i)
        ret[i] = 0;
      ret[SIZE - 1] = std::numeric_limits<Xpace::int64>::min();
      return ret;
  }

  template <size_t SIZE>
  inline
  static BigUint<SIZE> type_min
    (BigUint<SIZE>)
  {
      Xpace::BigUint<SIZE> ret;
      for (size_t i(0); i < SIZE; ++i)
        ret[i] = 0;
      return ret;
  }

  template<size_t SIZE> struct Unsigned<BigInt<SIZE> >  { typedef BigUint<SIZE> Type; };
  template<size_t SIZE> struct Unsigned<BigUint<SIZE> > { typedef BigUint<SIZE> Type; };

  template<size_t SIZE> struct Signed<BigInt<SIZE> >  { typedef BigInt<SIZE> Type; };
  template<size_t SIZE> struct Signed<BigUint<SIZE> > { typedef BigInt<SIZE> Type; };

  // ================================ STRING -> INT ===========

  bool stringToUint
    (const String8& str,
     uint radix,
     std::vector<uint64>* val);

  bool stringToUint
    (const String16& str,
     uint radix,
     std::vector<uint64>* val);

  bool stringToInt
    (const String8& str,
     uint radix,
     std::vector<uint64>* val);

  bool stringToInt
    (const String16& str,
     uint radix,
     std::vector<uint64>* val);

  // ==========================================================
  // ==========================================================
  // ==========================================================

  // ================================ UINT ====================

  template<size_t SIZE>
  inline
  BigUint<SIZE>::BigUint
    (uint64 v)
  {
    for (size_t i(SIZE); --i > 0; )
      vals[i] = 0;
    vals[0] = v;
  }

  template<size_t SIZE>
    template<size_t RS>
  inline
  BigUint<SIZE>::BigUint
    (const BigUint<RS>& rhs)
  {
    if (SIZE > RS)
    {
      memset(vals, 0, sizeof(vals));
      memcpy(vals, rhs.vals, sizeof(rhs.vals));
    }
    else
      memcpy(vals, rhs.vals, sizeof(vals));
  }
    
  template<size_t SIZE>
  inline
  bool BigUint<SIZE>::operator==
    (const BigUint<SIZE>& rhs)
    const
  {
    return !memcmp(vals, rhs.vals, sizeof(vals));
  }

  template<size_t SIZE>
  inline
  bool BigUint<SIZE>::operator==
    (uint rhs)
    const
  {
    if (rhs != vals[0])
      return false;
    for (size_t i(1); i < SIZE; ++i)
      if (vals[i])
        return false;    
    return true;
  }

  template<size_t SIZE>
  inline
  bool BigUint<SIZE>::operator!=
    (const BigUint<SIZE>& rhs)
    const
  {
    return !(*this == rhs);
  }

  template<size_t SIZE>
  inline
  bool BigUint<SIZE>::lt
    (const BigUint<SIZE>& rhs)
    const
  {
    for (size_t i(SIZE); --i; )
      if (vals[i] > rhs.vals[i])
        return false;
    return vals[0] < rhs.vals[0];
  }

  template<size_t SIZE>
  inline
  bool BigUint<SIZE>::gt
    (const BigUint<SIZE>& rhs)
    const
  {
    for (size_t i(SIZE); --i; )
      if (vals[i] < rhs.vals[i])
        return false;
    return vals[0] > rhs.vals[0];
  }

  template<size_t SIZE>
  inline
  BigUint<SIZE> BigUint<SIZE>::operator+
    (const BigUint<SIZE>& rhs)
    const
  {
    BigUint<SIZE> ret;
    bool carry(false);
    for (size_t i(0); i < SIZE; ++i)
      ret.vals[i] = add_carry(vals[i], rhs.vals[i], &carry);
    return ret;
  }

  template<size_t SIZE>
  inline
  BigUint<SIZE> BigUint<SIZE>::operator+
    (uint64 n)
    const
  {
    BigUint<SIZE> ret;
    bool carry(false);
    ret.vals[0] = add_carry(vals[0], n, &carry);
    for (size_t i(1); i < SIZE; ++i)
      ret.vals[i] = add_carry(vals[i], 0, &carry);
    return ret;
  }

  template<size_t SIZE>
  inline
  BigUint<SIZE> BigUint<SIZE>::operator-
    (const BigUint<SIZE>& rhs)
    const
  {
    BigUint<SIZE> ret;
    bool borrow(false);
    for (size_t i(0); i < SIZE; ++i)
      ret.vals[i] = sub_borrow(vals[i], rhs.vals[i], &borrow);
    return ret;
  }

  template<size_t SIZE>
  inline
  BigUint<SIZE> BigUint<SIZE>::operator*
    (uint32 n)
    const
  {
    BigUint<SIZE> ret;
    uint64 rr[SIZE * 2];
    uint64 *r(rr);
     
    const uint32* vv(reinterpret_cast<const uint32*>(vals));
    for (const uint32* v(vv); v < &vv[SIZE * 2]; ++v, ++r)
      *r = *v * n;
      
    bool carry(false);
    for (uint s(0); s < SIZE; ++s)
      ret.vals[s] = add_carry(rr[s * 2], rr[s * 2 + 1] << 32, &carry);

    return ret;    
  }

  template<size_t SIZE>
  inline
  BigUint<SIZE> BigUint<SIZE>::div
    (uint32 n, 
     uint32* rem)
    const
  {
    BigUint<SIZE> ret;

    if (n == 1)
    {
      *rem = 0;
      return *this;
    }

    if (n == 2)
    {
      *rem = vals[0] & 1;
      for (uint s(0); ; ++s)
      {
        ret.vals[s] = vals[s] >> 1;
        if (s == SIZE - 1)
          break;
        ret.vals[s] |= (vals[s + 1] << 63);
      }
    }
    else
    {
      // TODO: 64-bit version
      const uint32* vals32(reinterpret_cast<const uint32*>(vals));
      uint32* quot(reinterpret_cast<uint32*>(ret.vals));

      uint s(SIZE * 2 - 1);
      uint64 div(vals32[s]);
      while (1)
      {
        quot[s] = div / n;
        div %= n;
        if (s == 0)
        {
          *rem = div;
          break;
        }
        div <<= 32;
        div += vals32[--s];
      }
    }
    return ret;      
  }

  template<size_t SIZE>
  inline
  BigUint<SIZE> BigUint<SIZE>::operator/
    (uint32 n)
    const
  {
    uint rem;
    return div(n, &rem);
  }
   
  template<size_t SIZE>
  inline
  uint64 BigUint<SIZE>::operator[]
    (size_t i)
    const
  {
    return vals[i];
  }

  template<size_t SIZE>
  inline
  uint64& BigUint<SIZE>::operator[]
    (size_t i)
  {
    return vals[i];
  }

  template<size_t SIZE>
  inline
  const BytesRef BigUint<SIZE>::get
    ()
    const
  {
    return BytesRef(reinterpret_cast<const byte*>(vals), sizeof(vals));
  }
    
  template<size_t SIZE>
  inline
  void BigUint<SIZE>::set
    (const BytesRef& ref)
  {
    if (vals.size() * sizeof(uint64) < ref.length)
      memcpy(reinterpret_cast<byte*>(vals), ref.data, vals.size() * sizeof(uint64));
    else
    {
      memcpy(reinterpret_cast<byte*>(vals), ref.data, ref.length);
      memset(reinterpret_cast<byte*>(vals) + ref.length, 0, sizeof(vals) - ref.length);
    }
  }

  #ifdef QBYTEARRAY_H
  template<size_t SIZE>
  inline
  BigUint<SIZE>::operator const QByteArray
    ()
    const
  {
    return QByteArray(reinterpret_cast<const char*>(vals), sizeof(vals));
  }
  #endif

  template<size_t SIZE>
  inline
  uint64 BigUint<SIZE>::add_carry
    (uint64 a,
     uint64 b,
     bool* c)
  {
    *c = (*c && (a++ == ~uint64(0)))
      ? true
      : type_max(uint64(0)) - a < b;
    return a + b;
  }

  template<size_t SIZE>
  inline
  uint64 BigUint<SIZE>::sub_borrow
    (uint64 a,
     uint64 b,
     bool* borrow)
  {
    *borrow = (*borrow && (a-- == 0)) ? true : a < b;
    return a - b;
  }

  // ================================ INT =====================

  template<size_t SIZE>
  inline
  BigInt<SIZE>::BigInt
    (int64 n) 
  {
    this->vals[0] = strip_minus(n);
    set_minus(n < 0);
  }

  template<size_t SIZE>
    template<size_t RS>
  inline
  BigInt<SIZE>::BigInt
    (const BigInt<RS>& rhs) 
  {
    if (this->vals.size() > rhs.vals.size())
    {
      memcpy(this->vals, rhs.vals, sizeof(rhs.vals));
      memset(&this->vals[rhs.vals.size()], 0, rhs.vals.size() - this->vals.size());
    }
    else
      memcpy(this->vals, rhs.vals, sizeof(this->vals));
  }

  template<size_t SIZE>
  inline
  bool BigInt<SIZE>::operator==
    (const BigInt<SIZE>& rhs)
    const
  {
    return !memcmp(this->vals, rhs.vals, sizeof(this->vals));
  }

  template<size_t SIZE>
  inline
  bool BigInt<SIZE>::operator==
    (int rhs)
    const
  {
    if ((uint64(rhs) != this->vals[0]) || (is_minus() != (rhs < 0)))
      return false;
    for (size_t i(1); i < SIZE; ++i)
      if (this->vals[i])
        return false;    
    return true;    
  }

  template<size_t SIZE>
  inline
  bool BigInt<SIZE>::operator!=
    (const BigInt& rhs)
    const
  {
    return !(*this == rhs);
  }

  template<size_t SIZE>
  inline
  bool BigInt<SIZE>::operator<
    (const BigInt<SIZE>& rhs)
    const
  {
    return (is_minus() == rhs.is_minus()) ? lt(rhs) : is_minus();
  }

  template<size_t SIZE>
  inline
  bool BigInt<SIZE>::operator>
    (const BigInt<SIZE>& rhs)
    const
  {
    return (is_minus() == rhs.is_minus()) ? gt(rhs) : rhs.is_minus();
  }

  template<size_t SIZE>
  inline
  BigInt<SIZE> BigInt<SIZE>::operator*
    (uint32 rhs)
    const
  {
    BigUint<SIZE> m(*this);
    BigInt ret(m * rhs);
    ret.set_minus(is_minus());
    return ret;
  }

  template<size_t SIZE>
  inline
  BigInt<SIZE> BigInt<SIZE>::operator/
    (uint32 rhs)
     const
  {
    uint32 rem;
    return div(rhs, &rem);
  }

  template<size_t SIZE>
  inline
  BigInt<SIZE> BigInt<SIZE>::div
    (uint32 rhs, 
     uint32* rem)
    const
  {
    BigUint<SIZE> d(*this);
    BigInt<SIZE> ret(d.div(rhs, rem));
    ret.set_minus(is_minus());
    return ret;
  }
}

#endif