/Users/mourrain/Devel/mmx/basix/include/basix/int.hpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : int.hpp
* DESCRIPTION: additional operations for hardware integers
* COPYRIGHT  : (C) 2008  Gregoire Lecerf
*******************************************************************************
* This software falls under the GNU general public license and comes WITHOUT
* ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details.
* If you don't have this file, write to the Free Software Foundation, Inc.,
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
******************************************************************************/

#ifndef __MMX__INT__HPP
#define __MMX__INT__HPP
#include "basix/port.hpp"

namespace mmx {

inline void set_maximal (int& x) {
  x= (int) (((nat) (-1)) >> 1); }
inline void set_minimal (int& x) {
  x= (int) ((((nat) (-1)) >> 1) + 1); }
inline void set_maximal (nat& x) {
  x= (nat) (-1); }
inline void set_minimal (nat& x) {
  x= (nat) 0; }
inline void set_maximal (long int& x) {
  x= (long int) (((long unsigned int) (-1)) >> 1); }
inline void set_minimal (long int& x) {
  x= (long int) ((((long unsigned int) (-1)) >> 1) + 1); }
inline void set_maximal (long unsigned int& x) {
  x= (long unsigned int) (-1); }
inline void set_minimal (long unsigned int& x) {
  x= (long unsigned int) 0; }

inline nat
log_2 (nat p) {
  nat i=0;
  while (p>1) {
    p >>= 1;
    i++;
  }
  return i;
}

inline nat
next_power_of_two (nat p) {
  // return 0 in case of overflow
  nat n= 1;
  while (n < p && n != 0)
    n = n << 1;
  return n;
}

inline bool
is_power_of_two (nat p) {
  if (p == 0) return false;
  while ((p & 1) == 0) p >>= 1;
  return p == 1;
}

inline nat // inline instead of static in order to avoid warnings
log_3 (nat p) {
  nat i=0;
  while (p>1) {
    p /= 3;
    i++;
  }
  return i;
}

inline nat
next_power_of_three (nat p) {
  // return 0 in case of overflow
  nat n= 1;
  while (n < p)
    n *= 3;
  return (n<p) ? 0 : n;
}


// These two macro prevent the compiler from complaining
// when n = 8 * sizeof(C)
#define MMX_SAFE_LEFT_SHIFT_INT(C,a,n)                          \
  (((n) >= 8*sizeof(C)) ? ((C) 0) : (((C) a) << ((n)/2)) << ((n)-(n)/2))

#define MMX_SAFE_RIGHT_SHIFT_INT(C,a,n)                         \
  (((n) >= 8*sizeof(C)) ? ((C) 0) : (((C) a) >> ((n)/2)) >> ((n)-(n)/2))

template<nat s>
struct unsigned_int_with_size_at_least_helper {
private:
  template<bool b, typename T, typename E>
  struct if_helper { typedef T ret; };
  template<typename T, typename E>
  struct if_helper<false,T,E> { typedef E ret; };
public:
  typedef
    typename if_helper<sizeof(unsigned char)>=s, unsigned char,
    typename if_helper<sizeof(short unsigned int)>=s, short unsigned int,
    typename if_helper<sizeof(unsigned int)>=s, unsigned int,
    typename if_helper<sizeof(long unsigned int)>=s, long unsigned int,
    typename if_helper<sizeof(long long unsigned int)>=s,
                              long long unsigned int,
      void >::ret >::ret >::ret >::ret >::ret type ; };

template<typename C>
struct unsigned_int_with_double_size_helper {
  typedef typename
  unsigned_int_with_size_at_least_helper<2*sizeof(C)>::type
  type; };

template<typename C>
struct signed_of_helper {
  typedef void type; };

template<>
struct signed_of_helper<double> {
  typedef double type; };

template<>
struct signed_of_helper<char> {
  typedef signed char type; };

template<>
struct signed_of_helper<signed char> {
  typedef signed char type; };

template<>
struct signed_of_helper<short int> {
  typedef short int type; };

template<>
struct signed_of_helper<int> {
  typedef int type; };

template<>
struct signed_of_helper<long int> {
  typedef long int type; };

template<>
struct signed_of_helper<long long int> {
  typedef long long int type; };

template<>
struct signed_of_helper<unsigned char> {
  typedef signed char type; };

template<>
struct signed_of_helper<short unsigned int> {
  typedef short int type; };

template<>
struct signed_of_helper<unsigned int> {
  typedef int type; };

template<>
struct signed_of_helper<long unsigned int> {
  typedef long int type; };

template<>
struct signed_of_helper<long long unsigned int> {
  typedef long long int type; };

template<typename C>
struct unsigned_of_helper {
  typedef void type; };

template<>
struct unsigned_of_helper<char> {
  typedef unsigned char type; };

template<>
struct unsigned_of_helper<signed char> {
  typedef unsigned char type; };

template<>
struct unsigned_of_helper<short int> {
  typedef unsigned short int type; };

template<>
struct unsigned_of_helper<int> {
  typedef unsigned int type; };

template<>
struct unsigned_of_helper<long int> {
  typedef long unsigned int type; };

template<>
struct unsigned_of_helper<long long int> {
  typedef long long unsigned int type; };

template<>
struct unsigned_of_helper<unsigned char> {
  typedef unsigned char type; };

template<>
struct unsigned_of_helper<short unsigned int> {
  typedef short unsigned int type; };

template<>
struct unsigned_of_helper<unsigned int> {
  typedef unsigned int type; };

template<>
struct unsigned_of_helper<long unsigned int> {
  typedef long unsigned int type; };

template<>
struct unsigned_of_helper<long long unsigned int> {
  typedef long long unsigned int type; };

template<typename C>
struct is_signed_helper {
  static const bool value = false; };

template<>
struct is_signed_helper<signed char> {
  static const bool value = true; };

template<>
struct is_signed_helper<char> {
  static const bool value = true; };

template<>
struct is_signed_helper<short int> {
  static const bool value = true; };

template<>
struct is_signed_helper<int> {
  static const bool value = true; };

template<>
struct is_signed_helper<long int> {
  static const bool value = true; };

template<>
struct is_signed_helper<long long int> {
  static const bool value = true; };

template<typename uC, nat s, uC x>
struct int_bitsize_helper_rec {
  static const nat s2  = s >> 1;
  static const uC mask = (uC) MMX_SAFE_LEFT_SHIFT_INT(uC,-1,s2);
  static const uC size = (x & mask) ?
    (s2 + int_bitsize_helper_rec< uC, s2, (x >> s2)>::size) :
    int_bitsize_helper_rec< uC, s2, x >::size;
};
  
template<typename uC, uC x>
struct int_bitsize_helper_rec <uC, 1, x> {
  static const uC size = (x == 0) ? 0 : 1; };

template<typename uC, uC x>
struct int_bitsize_helper_rec <uC, 0, x> {
  static const uC size = 0; };

template<typename C, C p>
struct int_bitsize_helper {
  typedef typename unsigned_of_helper<C>::type uC;
  static const uC up = (p < 0) ? -p : p;

  static const nat value =
    int_bitsize_helper_rec < uC, 8*sizeof(C), up >::size;
};

template<typename C> static inline nat
bit_size (const C& p) {
  typedef typename unsigned_of_helper<C>::type uC;
  if (p == 0) return 0;
  uC up = abs (p);
  nat s = 0;
  nat k = 4 * sizeof(C);
  uC mask = ((uC) -1) << k;
  while (k != 0) {
    if (up & mask) { up >>= k; s += k; }
    k >>= 1;
    mask >>= k;
  }
  return up == 0 ? s : s + 1;
}

template<typename C>
class long_int_mul_op {
  typedef typename unsigned_of_helper<C>::type uC;
  static const nat n2 = 4 * sizeof (uC);
  static const nat n  = 2 * n2;
  static const uC lo_mask = ((uC) -1) >> n2;
  static const uC carry = ((uC) 1) << n2;
  // Let B = (1 << n2),  R = B^2.

  static inline uC
  lo (const uC& s) { return s & lo_mask; }
    
  static inline uC
  hi (const uC& s) { return s >> n2; }

public:
  static void
  op (uC& dest1, uC& dest0, const uC& a, const uC& b) {
    uC t0, t1;
    uC lo_a = lo (a);
    uC hi_a = hi (a);
    uC lo_b = lo (b);
    uC hi_b = hi (b);
    dest0 = lo_a * lo_b;
    dest1 = hi_a * hi_b;
    t0 = hi_a * lo_b;
    t1 = t0 + lo_a * hi_b;
    if (t1 < t0) dest1 += carry;
    t0 = lo (t1) << n2;
    dest0 += t0;
    dest1 += hi (t1);
    if (dest0 < t0) dest1++;
  }
};

template<typename C>
struct long_int_rshift_op {
  typedef typename unsigned_of_helper<C>::type uC;
  static const nat n2 = 4 * sizeof (uC);
  static const nat n  = 2 * n2;
  // Let B = (1 << n2),  R = B^2.

  static inline void
  op (uC& dest1, uC& dest0, nat s) {
    if (s == 0) return;
    if (s < n) {
      dest0 = (dest0 >> s) | (dest1 << (n - s));
      dest1 = dest1 >> s;
    }
    else {
      dest0 = dest1 >> (s - n);
      dest1 = 0;
    }
  }
    
  static inline bool
  op_b (uC& dest1, uC& dest0, nat s) {
    bool ans;
    if (s == 0) return false;
    if (s < n) {
      ans = (dest0 & (((uC) -1) >> (n - s))) != 0;
      dest0 = (dest0 >> s) | (dest1 << (n - s));
      dest1 = dest1 >> s;
    }
    else {
      ans = dest0 != 0 || (dest1 & (((uC) -1) >> (2*n - s))) != 0;
      dest0 = dest1 >> (s - n);
      dest1 = 0;
    }
    return ans;
  }
};

template<typename C>
struct long_int_lshift_op {
  typedef typename unsigned_of_helper<C>::type uC;
  static const nat n2 = 4 * sizeof (uC);
  static const nat n  = 2 * n2;
  // Let B = (1 << n2),  R = B^2.

  static inline void
  op (uC& dest1, uC& dest0, nat s) {
    if (s == 0) return;
    if (s < n) {
      dest1 = (dest1 << s) | (dest0 >> (n - s));
      dest0 = dest0 << s;
    }
    else {
      dest1 = dest0 << (s - n);
      dest0 = 0;
    }
  }
};

template<typename C>
struct long_int_sub_op {
  typedef typename unsigned_of_helper<C>::type uC;

  static inline void
  op (uC& dest1, uC& dest0, const uC& s1, const uC& s0) {
    if (dest0 >= s0) {
      dest0 -= s0;
      dest1 -= s1;
    }
    else {
      dest0 -= s0;
      dest1 -= s1 + 1;
    }
  }
};

template<typename C>
struct long_int_ge_op {
  typedef typename unsigned_of_helper<C>::type uC;

  static inline bool
  op (const uC& s1, const uC& s0, const uC& t1, const uC& t0) {
    if (s1 > t1) return true;
    if (s1 < t1) return false;
    return s0 >= t0;
  }
};

/******************************************************************************
* Division
******************************************************************************/

#define INT_DIV_DECLARE(I)                                              \
  inline bool divides (const I& n, const I& m) { return (m % n) == 0; } \
  inline I rem (const I& n, const I& m) { return m == 0 ? n : n % m; }  \
  inline I quo (const I& n, const I& m) { return m == 0 ? 0 : n / m; }  \
  inline I rem (const I& n, const I& m, I& q) {                         \
    I _q= quo (n, m); I _r= n - _q * m; q= _q; return _r; }
INT_DIV_DECLARE(signed char)
INT_DIV_DECLARE(short int)
INT_DIV_DECLARE(int)
INT_DIV_DECLARE(long int)
INT_DIV_DECLARE(long long int)
INT_DIV_DECLARE(unsigned char)
INT_DIV_DECLARE(unsigned short int)
INT_DIV_DECLARE(unsigned int)
INT_DIV_DECLARE(unsigned long int)
INT_DIV_DECLARE(unsigned long long int)
#undef INT_DIV_DECLARE

/******************************************************************************
* Gcd
******************************************************************************/

struct int_gcd_helper {
  template<typename I>
  static I gcd (const I& a, const I& b) {
    typedef typename unsigned_of_helper<I>::type U;
    I r0 = a, r1 = b, q, t;
    if ((r0 == 0) && (r1 != 0)) {
      q = (((U) r0) - ((U) r1)) / ((U) r1) + 1;
      t = r0 - q * r1;
      r0 = r1;
      r1 = t;
    }
    while (r1 != 0) {
      q = r0 / r1;
      t = r0 - q * r1;
      r0 = r1;
      r1 = t;
    }
    return r0;
  }

  template<typename I>
  static I gcd (const I& a, const I& b, I& co_a) {
    typedef typename unsigned_of_helper<I>::type U;
    I r0 = a, r1 = b, co_a0 = 1, co_a1 = 0, q, t;
    if ((r0 == 0) && (r1 != 0)) {
      q = (((U) r0) - ((U) r1)) / ((U) r1) + 1;
      t = r0 - q * r1;
      r0 = r1;
      r1 = t;
      t = co_a1;
      co_a1 = co_a0 - q * co_a1;
      co_a0 = t;
    }
    while (r1 != 0) {
      q = r0 / r1;
      t = r0 - q * r1;
      r0 = r1;
      r1 = t;
      t = co_a1;
      co_a1 = co_a0 - q * co_a1;
      co_a0 = t;
    }
    co_a = co_a0;
    return r0;
  }
  
  template<typename I>
  static I gcd (const I& a, const I& b, I& co_a, I& co_b) {
    typedef typename unsigned_of_helper<I>::type U;
    I r0 = a, r1 = b, co_a0 = 1, co_a1 = 0, co_b0 = 0, co_b1 = 1, q, t;
    if ((r0 == 0) && (r1 != 0)) {
      q = (((U) r0) - ((U) r1)) / ((U) r1) + 1;
      t = r0 - q * r1;
      r0 = r1;
      r1 = t;
      t = co_a1;
      co_a1 = co_a0 - q * co_a1;
      co_a0 = t;
      t = co_b1;
      co_b1 = co_b0 - q * co_b1;
      co_b0 = t;
    }
    while (r1 != 0) {
      q = r0 / r1;
      t = r0 - q * r1;
      r0 = r1;
      r1 = t;
      t = co_a1;
      co_a1 = co_a0 - q * co_a1;
      co_a0 = t;
      t = co_b1;
      co_b1 = co_b0 - q * co_b1;
      co_b0 = t;
    }
    co_a = co_a0;
    co_b = co_b0;
    return r0;
  }
};

struct unsigned_int_gcd_helper {
  template<typename I>
  static I gcd (const I& a, const I& b) {
    I r0=a, r1=b, q, t; 
    if ((r0 == 0) && (r1 != 0)) {
      q = (r0-r1) / r1 + 1;
      t = r0 - q * r1;
      r0 = r1;
      r1 = t;
    }
    while (r1 != 0) {
      q = r0 / r1;
      t = r0 - q * r1;
      r0 = r1;
      r1 = t;
    }
    return r0;
  }
};

#define INT_GCD_DECLARE(I)                                              \
  inline I gcd (const I a, const I b) {                                 \
    return int_gcd_helper::gcd (a, b); }                                \
                                                                        \
  inline I gcd (const I a, const I b, I& co_a) {                        \
    return int_gcd_helper::gcd (a, b, co_a); }                          \
                                                                        \
  inline I gcd (const I a, const I b, I& co_a, I& co_b) {               \
    return int_gcd_helper::gcd (a, b, co_a, co_b); }
  
INT_GCD_DECLARE(signed char)
INT_GCD_DECLARE(short int)
INT_GCD_DECLARE(int)
INT_GCD_DECLARE(long int)
INT_GCD_DECLARE(long long int)
#undef INT_GCD_DECLARE

#define UINT_GCD_DECLARE(I)                                             \
  inline I gcd (const I a, const I b) {                                 \
    return unsigned_int_gcd_helper::gcd (a, b); }

UINT_GCD_DECLARE(unsigned char)
UINT_GCD_DECLARE(unsigned short int)
UINT_GCD_DECLARE(unsigned int)
UINT_GCD_DECLARE(unsigned long int)
UINT_GCD_DECLARE(unsigned long long int)
#undef UINT_GCD_DECLARE

}// namespace mmx
#endif //__MMX__INT__HPP