/******************************************************************************
			      class word

A computer word with double-precision arithmetic operations.

Type T can be one of the following unsigned long long int, unsigned long int,
unsigned short int, and unsigned char. unsigned char could be used for 
debugging purposes and unsigned long long int or unsigned long int for the 
actual test runs.

Copyright:
Jyrki Katajainen
Department of Computing
University of Copenhagen
DK-2100 Copenhagen East, Denmark
e-mail: jyrki@di.ku.dk

Version: 1.1
January - February 1999

Changes made to version 1.0:

8 Febuary 1999
  return pair<sign, word<T> >(zero, word<T>(0));
==>
  return pair<sign, word<T> >(zero, word<T>(T(0)));

Christian Boesgaard <pink@diku.dk>
  cout << "a + a = " << p2.first << '\t' << p2.second << endl;
==>
  cout << "a + b = " << p2.first << '\t' << p2.second << endl;

Christian Boesgaard <pink@diku.dk>
  friend bool operator==(const word<T>&, const word<T>&);
  friend pair<word<T>, word<T> > operator+(const word<T>&, const word<T>&);
  friend pair<sign, word<T> > operator-(const word<T>&, const word<T>&);
  friend pair<word<T>, word<T> > operator*(const word<T>&, const word<T>&);
  friend ostream& operator<<(ostream&, const word<T>&);
==>
  friend bool operator==<>(const word<T>&, const word<T>&);
  friend pair<word<T>, word<T> > operator+<>(const word<T>&, const word<T>&);
  friend pair<sign, word<T> > operator-<>(const word<T>&, const word<T>&);
  friend pair<word<T>, word<T> > operator*<>(const word<T>&, const word<T>&);
  friend ostream& operator<< <>(ostream&, const word<T>&);

Tommy <di981101@diku.dk>
New operations implemented
operator!=
operator<
operator>
operator<=
operator>=

******************************************************************************/

#if !defined(WORD)
#define WORD

#include <utility>  // defines pair
#include <iostream> // defines ostream

enum sign {zero, plus, minus};

ostream& operator<<(ostream& out, const sign& s) {
  if (s == minus) 
    out << "-";
  else
    out << "";
  return out;
}

template <class T>
class word {
public:
  word();
  word(T);
  word(const word<T>&);

  word<T>  length() const;
  word<T>  most_significant_bit() const;
  word<T>  most_significant_half() const;
  word<T>  least_significant_half() const;
  word<T>& operator>>=(const word<T>&);
  word<T>& operator<<=(const word<T>&);
  word<T>& operator=(const word<T>&);

  friend bool operator==<>(const word<T>&, const word<T>&);
  friend bool operator!=<>(const word<T>&, const word<T>&);
  friend bool operator< <>(const word<T>&, const word<T>&);
  friend bool operator> <>(const word<T>&, const word<T>&);
  friend bool operator<=<>(const word<T>&, const word<T>&);
  friend bool operator>=<>(const word<T>&, const word<T>&);

  friend pair<word<T>, word<T> > operator+<>(const word<T>&, const word<T>&);
  friend pair<sign, word<T> > operator-<>(const word<T>&, const word<T>&);
  friend pair<word<T>, word<T> > operator*<>(const word<T>&, const word<T>&);
  friend ostream& operator<< <>(ostream&, const word<T>&);
private:
  enum {lambda_per_2 = 4 * sizeof(T), 
	lambda_minus_1 = 8 * sizeof(T) - 1,
	lambda = 8 * sizeof(T)};
  T value;
};

template <class T>
inline word<T>::word() : value(T(0)) {
}

template <class T>
inline word<T>::word(T v) : value(v) {
}

template <class T>
inline word<T>::word(const word<T>& w) {
  (*this).value = w.value;
}

template <class T>
inline word<T> word<T>::length() const { // in bits; must be a power of 2
  return word<T>(lambda);
}

template <class T>
inline word<T> word<T>::most_significant_bit() const {
  return word<T>((*this).value >> T(lambda_minus_1));
}

template <class T>
inline word<T> word<T>::most_significant_half() const {
  return word<T>((*this).value >> T(lambda_per_2));
}

template <class T>
inline word<T> word<T>::least_significant_half() const {
  T temp = (*this).value >> T(lambda_per_2);
  temp = temp << T(lambda_per_2);
  return word<T>((*this).value - temp);
}

template <class T>
inline word<T>& word<T>::operator>>=(const word<T>& shift) {
  (*this).value = (*this).value >> shift.value;
  return *this;
}

template <class T>
inline word<T>& word<T>::operator<<=(const word<T>& shift) {
  (*this).value = (*this).value << shift.value;
  return *this;
}

template <class T>
inline word<T>& word<T>::operator=(const word<T>& rhs) {
  if (this == &rhs) 
    return *this;
  (*this).value = rhs.value;
  return *this;
}

// logical operations

template <class T>
bool operator==(const word<T>& x, const word<T>& y) {
  return x.value == y.value;
}

template <class T>
bool operator!=(const word<T>& x, const word<T>& y) {
  return x.value != y.value;
}

template <class T>
bool operator<(const word<T>& x, const word<T>& y) {
  return x.value < y.value;
}

template <class T>
bool operator>(const word<T>& x, const word<T>& y) {
  return x.value > y.value;
}

template <class T>
bool operator<=(const word<T>& x, const word<T>& y) {
  return x.value <= y.value;
}

template <class T>
bool operator>=(const word<T>& x, const word<T>& y) {
  return x.value >= y.value;
}

// addition

template <class T>
pair<word<T>, word<T> > operator+(const word<T>& x, const word<T>& y) {

  // Warning: & seems not to work properly. Therefore, I avoided it.

  const T len_minus_1 = x.length().value - T(1);
  const T two_to_len_minus_1 = T(1) << len_minus_1;
  
  word<T> bit_x = x.most_significant_bit();
  word<T> bit_y = y.most_significant_bit();
  word<T> rest_x = x;
  if (x.value >= two_to_len_minus_1)
    rest_x = word<T>(x.value - two_to_len_minus_1);
  word<T> rest_y = y;
  if (y.value >= two_to_len_minus_1)
    rest_y = word<T>(y.value - two_to_len_minus_1);

  word<T> z = word<T>(rest_x.value + rest_y.value);
  word<T> bit_z = z.most_significant_bit();
  word<T> rest_z = z;
  if (z.value >= two_to_len_minus_1)
    rest_z = word<T>(z.value - two_to_len_minus_1);

  T sum = bit_x.value + bit_y.value + bit_z.value;
  word<T> carry = word<T>(sum >> T(1));
  sum = sum - carry.value - carry.value;
  T temp =  sum << len_minus_1;
  word<T> low_order_word = word<T>(temp + rest_z.value);

  return pair<word<T>, word<T> >(carry, low_order_word);
}

// subtraction

template <class T>
pair<sign, word<T> > operator-(const word<T>& x, const word<T>& y) {
  if (x.value < y.value) {
    word<T> z = word<T>(y.value - x.value);
    return pair<sign, word<T> >(minus, z);
  }
  else if (x.value > y.value) {
    word<T> z = word<T>(x.value - y.value);
    return pair<sign, word<T> >(plus, z);
  }      
  else {
    return pair<sign, word<T> >(zero, word<T>(T(0)));
  }
}

// multiplication

template <class T>
pair<word<T>, word<T> > operator*(const word<T>& x, const word<T>& y) {
  const T half_len = x.length().value / T(2);

  word<T> x_left  = x.most_significant_half();
  word<T> x_right = x.least_significant_half();
  word<T> y_left  = y.most_significant_half();
  word<T> y_right = y.least_significant_half();

  word<T> t_1 = word<T>(x_right.value * y_right.value);
  word<T> t_2 = word<T>(x_right.value * y_left.value);
  word<T> t_3 = word<T>(x_left.value * y_right.value);
  word<T> t_4 = word<T>(x_left.value * y_left.value);

  word<T> t_2_left = word<T>(t_2.value >> half_len);
  word<T> t_2_right_shifted = word<T>(t_2.value << half_len);
  word<T> t_3_left = word<T>(t_3.value >> half_len);
  word<T> t_3_right_shifted = word<T>(t_3.value << half_len);

  pair<word<T>, word<T> > temp = t_1 + t_2_right_shifted;
  pair<word<T>, word<T> > sum = temp.second + t_3_right_shifted;
  word<T> low_order_word = sum.second;
  T carry = temp.first.value + sum.first.value;
  word<T> high_order_word = word<T>(carry + t_2_left.value + t_3_left.value + 
				    t_4.value);
  return pair<word<T>, word<T> >(high_order_word, low_order_word);
}

// outputting

template <class T>
ostream& operator<<(ostream& out, const word<T>& w) {
  long unsigned int temp = (long unsigned int)(w.value);
  out << temp;
  return out;
}

#endif

#if defined(UNIT_TEST_WORD)

int main() {
  word<unsigned char> a = word<unsigned char>((unsigned char)(189));
  word<unsigned char> b = word<unsigned char>((unsigned char)(188));  

  cout << "a = " << a << endl;
  cout << "b = " << b << endl;

  pair<word<unsigned char>, word<unsigned char> > p1 = a + a;
  cout << "a + a = " << p1.first << '\t' << p1.second << endl;

  pair<word<unsigned char>, word<unsigned char> > p2 = a + b;
  cout << "a + b = " << p2.first << '\t' << p2.second << endl;

  pair<sign, word<unsigned char> > q1 = a - b;
  cout << "a - b = " << q1.first << '\t' << q1.second << endl;

  q1 = a - a;
  cout << "a - a = " << q1.first << '\t' << q1.second << endl;

  q1 = b - a;
  cout << "b - a = " << q1.first << '\t' << q1.second << endl;

  pair<word<unsigned char>, word<unsigned char> > r = a * a;
  cout << "a * a = " << r.first << '\t' << r.second << endl;

  return(0);
}

/*

freja> g++ word.cc -DUNIT_TEST_WORD
freja> a.out
a = 189
b = 188
a + a = 1       122
a + b = 1       121
a - b = 1       1
a - a = 0       0
b - a = 2       1
a * a = 139     137

*/
#endif