synaps/arithm/BigUnsigned.h

#ifndef SYNAPS_BIG_UNSIGNED_H
#define SYNAPS_BIG_UNSIGNED_H

#include <synaps/init.h>
#include <assert.h>
#include <ostream>
#include <synaps/arithm/hdwi.h>

__BEGIN_NAMESPACE_SYNAPS

template <unsigned N>
struct BigUnsigned
{
  typedef unsigned hi; 
  typedef unsigned hdwi_t;
  static bool s_overflow;
  
  hi data[N];    
  BigUnsigned(){};
  
  BigUnsigned( unsigned n )
  {
    data[0] = n;
    for (unsigned  i = 1; i < N; data[i] = 0, i ++ );
  };
  
  BigUnsigned& operator=( unsigned n ) 
  { 
     new (this) BigUnsigned(n); 
  };
  
  BigUnsigned& operator=( const BigUnsigned& b ) 
  { 
     new (this) BigUnsigned(b); 
  };
  
  inline bool operator<( const BigUnsigned<N>& bi )
  {
    for ( int i = N-1; i >= 0; i ++ )
      if ( bi[i] > data[i] ) return true;
    return false;
  };
  
  inline bool operator>( const BigUnsigned<N>& bi )
  {
    for ( int i = N-1; i >= 0; i ++ )
      if ( bi[i] < data[i] ) return true;
    return false;
  };
  
  inline bool operator==( const BigUnsigned<N>& bi )
  {
    for (unsigned i = 0; i < N; i ++ )
      if ( data[i] != bi[i] ) return false;
    return true;
  };
  
  inline BigUnsigned& operator<<=( unsigned n )
  {
    if ( n >= numerics::hdwi<hi>::nbit )
      {
        do
          {
            for ( unsigned i = N-1; i > 0; i -- )
              data[i]  = data[i-1];
            data[0] = 0;
            n -= numerics::hdwi<hi>::nbit;
          }
        while ( n >= numerics::hdwi<hi>::nbit );
      };
    if ( n )
      {
        data[N-1] <<= n;
        for ( int i = N-1; i > 0; i -- )
          {
            data[i] |= (data[i-1]>>(numerics::hdwi<hi>::nbit-n));
            data[i-1] <<= n;
          };
      };
    return *this;
  };
  
  inline BigUnsigned& operator>>=( unsigned n )
  {
    if ( n >= numerics::hdwi<hi>::nbit )
      {
        do 
          {
            for ( unsigned i = 0; i < N-1; data[i] = data[i+1], i ++ );
            data[N-1] = 0;
            n -= numerics::hdwi<hi>::nbit;
          }
        while ( n >= numerics::hdwi<hi>::nbit );
      };
    
    if ( n )
      {
        data[0] >>= n; 
        for ( int i = 0; i < int(N-1); i ++ )
          {
            data[i] |= (data[i+1]<<(numerics::hdwi<hi>::nbit-n));
            data[i+1] >>= n;
          };
      };
    return *this;
  };
  
  inline BigUnsigned& operator|=( unsigned n ) 
  { 
    data[0] |= n; 
    return *this; 
  };
  
  inline BigUnsigned& operator|=( const BigUnsigned& bu )
  {
    for ( unsigned i = 0; i < N; data[i] |= bu[i], i ++ );
    return *this;
  };
  
  inline       BigUnsigned<N-1>& next() 
  { 
    return *((BigUnsigned<N-1>*)(this->data+1)); 
  };
  
  inline const BigUnsigned<N-1>& next()  const 
  { 
    return *((const BigUnsigned<N-1>*)(this->data+1)); 
  };
  
  inline BigUnsigned& operator+=( unsigned n )           
  { 
    add(*this,n); 
    return *this; 
  };
  
  inline BigUnsigned& operator+=( const BigUnsigned& a ) 
  { 
    add(*this,a); 
    return *this;
  };
  
  unsigned& operator[]( int i )       
  { 
    return data[i]; 
  };
  
  unsigned  operator[]( int i ) const 
  { 
    return data[i]; 
  };

};

template<unsigned N>
BigUnsigned<N> operator<<( const BigUnsigned<N>& b, unsigned n )
{
  BigUnsigned<N> tmp = b;
  tmp <<= n;
  return tmp;
};

template<unsigned N>
BigUnsigned<N> operator|( const BigUnsigned<N>& b, unsigned n )
{
  BigUnsigned<N> tmp = b;
  tmp <<= n;
  return tmp;
};

template<unsigned N> inline
BigUnsigned<N> operator+( const BigUnsigned<N>& b, unsigned n )
{
  BigUnsigned<N> tmp;
  tmp = b;
  add(tmp,n);
  return tmp;
};
template<unsigned N>
unsigned operator&( const BigUnsigned<N>& b, unsigned n )
{
  return b[0] & n;
};

template< unsigned N> bool BigUnsigned<N>::s_overflow = false;

template<unsigned N> inline
void add( BigUnsigned<N>& r, typename BigUnsigned<N>::hdwi_t n  )
{
  typedef typename BigUnsigned<N>::hdwi_t hdwi_t;
  unsigned i = 0;
  while ( n )
    {
      hdwi_t delta = numerics::hdwi<hdwi_t>::nmax - r[i];
      if ( delta < n ) 
        { 
          r[i] += n; 
          n -= r[i]; 
        }
      else
        {
          r[i] += n;
          n     = 0;
          break;
        };
      i = i + 1;
      if ( i == N ) break;
    };
  
  BigUnsigned<N>::s_overflow = (n != 0);
  
};

inline void add( BigUnsigned<1>& r, const BigUnsigned<1>& a ) { add(r,a[0]); };

template <unsigned N> inline
void add( BigUnsigned<N>& r, const BigUnsigned<N>& a )
{
  add(r,a[0]);
  if ( ! BigUnsigned<N>::s_overflow ) 
    {
      add(r.next(),a.next());
      if (  BigUnsigned<N-1>::s_overflow ) 
        {
          BigUnsigned<N>::s_overflow   = true;
          BigUnsigned<N-1>::s_overflow = false;
        };
    };
};

template <unsigned N> 
void reverse( BigUnsigned<N>& r, const BigUnsigned<N>& lu )
{
  typedef typename BigUnsigned<N>::hdwi_t hdwi_t;
  for ( unsigned i = 0; i < N/2; i ++ )
    {
      r[i] = numerics::hdwi<hdwi_t>::reverse(lu[N-1-i]);
      r[N-1-i] = numerics::hdwi<hdwi_t>::reverse(lu[i]);
    };
  if ( N & 1 ) r[N/2] = numerics::hdwi<hdwi_t>::reverse(lu[N/2]);
};

inline void rprint( std::ostream& o, unsigned n )
{
  for ( unsigned b = 0; b < numerics::hdwi<unsigned>::nbit; b ++ )
    {
        o << ( n& 1);
        n >>= 1;
    };
};

template< unsigned N >
void rprint( std::ostream& o, BigUnsigned<N>& bu )
{
  for ( unsigned i = 0; i < N; i ++ )
    rprint(o,bu[i]);
};

template< unsigned N >
void print ( std::ostream& o, const BigUnsigned<N>& bi )
{
  BigUnsigned<N> tmp;
  reverse(tmp,bi);
  rprint(o,tmp);
  
};

template<unsigned N>
std::ostream& operator<<( std::ostream& o, const BigUnsigned<N>& bi )
{
  print(o,bi);
  return o;
};

__END_NAMESPACE_SYNAPS

#endif