/Users/mourrain/Devel/mmx/realroot/include/realroot/scalar_bigunsigned.hpp

Go to the documentation of this file.

#ifndef realroot_BIG_UNSIGNED_H
#define realroot_BIG_UNSIGNED_H

#include <assert.h>
#include <ostream>
#include <realroot/numerics_hdwi.hpp>

namespace mmx {

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

} //namespace mmx

#endif