//
// Copyright (C) 1991 Texas Instruments Incorporated.
//
// Permission is granted to any individual or institution to use, copy, modify,
// and distribute this software, provided that this complete copyright and
// permission notice is maintained, intact, in all copies and supporting
// documentation.
//
// Texas Instruments Incorporated provides this software "as is" without
// express or implied warranty.
//
// Created: MBN 10/24/89 -- Initial design and implementation
// Updated: MJF 07/31/90 -- Added terse print
//

// The Bignum class implements infinite precision integer arithmetic.  A Bignum
// object grows and  shrinks in size as  necessary to  accommodate its  current
// value.  All of the  standard C operations defined on  integers  in Kernighan
// and Ritchie,   Appendix  A carry  over  directly  to  Bignums   by means  of
// overloading,  except for those  operations that  make assumptions  about the
// underlying representation.   For  example, we have  not  implemented bitwise
// operators &,|,^ because they would have to make assumptions about our Bignum
// implementation.  On the other  hand,  we have,  for example  implemented the
// operators   << and   >>,  because   these can   be always   be   interpreted
// arithmetically  as multiplication  or  division   by 2, respectively, of the
// underlying integer type.  The four standard arithmetic operations +,-,*, and
// / utilize algorithms from Knuth, Volume 2 for efficiency.  However, the user
// is warned that the  Bignum integer  arithmetic class  is  still considerably
// slower than the built-in integer data types.
//
// The  Bignum class  implements   common  arithmetic exception  handling   and
// provides  the  application  with support  for  detecting negative  infinity,
// positive infinity, overflow,  and underflow as a result  of some  arithmetic
// expression. If  one of these   conditions or an attempt  to  convert from  a
// Bignum with no value to  a built-in type  is detected, an Error exception is
// raised. The application programmer can provide an exception handler  to take
// care of this problem. If  no such handler  is available, an error message is
// printed and the application terminates.
//
// The Bignum class requires several constants be defined to  insure precision
// and  accuracy of conversion.   The preprocessor  symbols  MINSHORT, MININT,
// MINLONG, MAXSHORT, MAXINT, and MAXLONG  are calculated in the <COOL/misc.h>
// header file via  various  bit manipulation  macros. The  symbols  MINFLOAT,
// MINDOUBLE,  MAXFLOAT,  and MAXDOUBLE  are system   dependent  and cannot be
// calculated.  Most systems typically have values for these constants  in the
// system  header file <values.h>.  Values  for a  specific machine  should be
// copied into the <COOL/misc.h> header file as necessary.
//
// The  private  data section of  the Bignum class  has a pointer to storage of
// consecutive short  blocks large enough  to  hold the  value.  The number of
// blocks is  contained in  a  private integer  slot.   The Bignum  class  also
// contains a private data slot providing  arithmetic  exception status.  There
// are  five constructors for the  Bignum class.  The first  is a simple inline
// constructor  that initializes the state and  private data slots.  The second
// takes an integer (short, int, or long)  and uses that  as  the initial value
// for the object.  The third takes a real  (float or double)  and uses that as
// the  initial   value for the object.    The  fourth takes  a null-termianted
// character string  in either octal, decimal, hex, or exponential format   and
// converts it  to the appropriate  Bignum value.   Finally,  the fifth takes a
// const reference to another Bignum object and duplicates its state and value.
// The Bignum class provides overloaded  operators  for addition,  subtraction,
// multiplication,  division, and  modulus.  Also  available  are equality  and
// inequality,  assignment, increment, decrement, unary minus, ones-complement,
// output,  less than, greater than,  less than  or equal, and  greater than or
// equal.  Finally, five type conversion functions to  short, int, long, float,
// and double are provided.

#ifndef BIGNUMH					// If no definition for Bignum
#define BIGNUMH					// define the bignum symbol

#ifndef GENERIC_H				// If no definition for class
#include <cool/Generic.h>			// include definition file
#endif

#ifndef REGEXPH					// If no regular expressions
#include <cool/Regexp.h>			// include definition
#endif

typedef unsigned int Counter;
typedef unsigned short Data;

class Bignum {
private:
  Counter count;				// Number of data elements
  int sign;					// Sign of Bignum (+,-,or 0)
  Data* data;					// Pointer to data value
  N_status state;				// Exception status

  void xtoBignum(const char *s);		// convert hex to Bignum
  int  dtoBignum(const char *s);		// convert decimal to Bignum
  void otoBignum(const char *s);		// convert octal to Bignum
  void exptoBignum(const char *s);		// convert exponential to Big.

  friend int magnitude_cmp(const Bignum&, const Bignum&); // Compare magnitudes
  friend void add(const Bignum&, const Bignum&, Bignum&); // Unsigned add
  friend void subtract(const Bignum&, const Bignum&, Bignum&); // Unsigned sub.
  friend void multiply_aux(const Bignum&, Data d, Bignum&, Counter i); 
  friend Data normalize(const Bignum&, const Bignum&,
			Bignum&, Bignum&);	// Normalize for division
  friend void divide_aux(const Bignum&, Data,
			 Bignum&, Data&);	// Divide single digit
  friend Data estimate_q_hat(const Bignum&, const Bignum&,
			     Counter);		// Estimate quotient
  friend Data multiply_subtract(Bignum&, const Bignum&, Data q_hat,
				Counter);	// Multiply quotient and subt.
  friend void divide(const Bignum&, const Bignum&,
		     Bignum&, Bignum&);		// Divide Bignum
  void resize(Counter);				// Resize Bignum data
  Bignum& trim();				// Trim Bignum data
  friend Bignum left_shift(const Bignum& b1, long l);
  friend Bignum right_shift(const Bignum& b1, long l);

protected:
  void minus_infinity (const char*) CONST;	// Raise - infinity exception
  void plus_infinity (const char*) CONST;	// Raise + infinity exception
  void overflow (const char*) CONST;		// Raise overflow error
  void underflow (const char*) CONST;		// Raise overflow error
  void no_conversion (const char*) CONST;	// Raise no conversion error
  void divide_by_zero (const char*) CONST;	// Raise divide by zero

public:
  inline N_status status() CONST;		// Return Bignum status      

  // Bignum constructors
  Bignum ();					// Void constructor
  Bignum (long);				// Long constructor
  Bignum (const char*);				// String constructor
  Bignum (double);				// Double constructor
  Bignum (const Bignum&);			// Bignum& Constructor 
  ~Bignum ();					// Bignum destructor

  // Conversion operators
  operator short () CONST;			// Implicit type conversion
  operator int () CONST;			// Implicit type conversion
  operator long () CONST;			// Implicit type conversion
  operator float () CONST;			// Implicit type conversion
  operator double () CONST;			// Implicit type conversion

  // Overloaded operators
  Bignum& operator= (const Bignum&);            // Assignment operator
  Bignum operator- () CONST;			// Unary minus operator
  inline Boolean operator! () CONST;		// Not operator
  friend Bignum operator+ (const Bignum&,
			   const Bignum&);	// Plus operator
  inline friend Bignum operator- (const Bignum&,
			          const Bignum&); // Minus operator
  friend Bignum operator* (const Bignum&,
			   const Bignum&);	// Multiplication operator
  friend Bignum operator/ (const Bignum&,
			   const Bignum&);	// Division operator
  friend Bignum operator% (const Bignum&,
			   const Bignum&);	// Modulus operator
  friend Bignum operator<< (const Bignum&,
			    long l);		// Arithmetic left shift
  friend Bignum operator>> (const Bignum&,
			    long l);		// Arithmetic right shift
  inline void operator+= (const Bignum&);	// plus/assign
  inline void operator-= (const Bignum&);	// minus/assign
  inline void operator*= (const Bignum&);	// multiply/assign
  inline void operator/= (const Bignum&);	// division/assign
  inline void operator%= (const Bignum&);	// modulus/assign
  inline void operator<<= (const Bignum&);	// left shift/assign
  inline void operator>>= (const Bignum&);	// right shift/assign
  
  Bignum& operator++ ();			// increment
  Bignum& operator-- ();			// decrement

  Boolean operator== (const Bignum&) CONST;	   // equality
  inline Boolean operator!= (const Bignum&) CONST; // inequality
  Boolean operator< (const Bignum&) CONST;	   // less than
  inline Boolean operator<= (const Bignum&) CONST; // less than/equal
  Boolean operator> (const Bignum&) CONST;	   // greater than
  inline Boolean operator>= (const Bignum&) CONST; // greater than/eq.

  friend ostream& operator<< (ostream&, const Bignum&);	// Output reference
  inline friend ostream& operator<< (ostream&, const Bignum*); // Output ptr

  void dump(ostream& = cout) CONST;		// Dump contents of Bignum
  void print(ostream&);				// terse print
};



// status -- returns status of a Bignum
// Inputs:  none
// Outputs:  status of this Bignum
inline N_status Bignum::status() CONST {
  return this->state;				// Return this->state
}



// operator- -- overloaded subtraction operator for Bignums
// Inputs:  references to two Bignums
// Outputs:  the Bignum difference of the two input Bignums
inline Bignum operator- (const Bignum& b1, const Bignum& b2) {
  return (b1 + (-b2));				// negate b2 and add to b1
}



// operator! -- overloaded not operator for Bignums
// Inputs:  none
// Outputs:  Boolean not of this Bignum
inline Boolean Bignum::operator! () CONST {
  return (Boolean) (this->count == 0);		// Return 1 if Bignum's zero
}



// operator!= -- overloaded != comparison operator for Bignums
// Inputs:  reference to Bignum
// Outputs:  Boolean result of the comparison
inline Boolean Bignum::operator!= (const Bignum& b) CONST {
  return !(*this == b);				// call Bignum operator==
}



// operator<= -- overloaded <= operator for Bignums
// Inputs:  reference to Bignum
// Outputs:  Boolean result of <= comparison
inline Boolean Bignum::operator<= (const Bignum& b) CONST {
  return !(*this > b);				// call Bignum operator>
}



// operator>= -- overloaded >= operator for Bignums
// Inputs:  reference to Bignum
// Outputs:  Boolean result of >= comparison
inline Boolean Bignum::operator>= (const Bignum& b) CONST {
  return !(*this < b);			
}



// operator+= -- overloaded addition assignment operator for Bignums
// Inputs:  reference to Bignum
// Outputs:  void
inline void Bignum::operator+= (const Bignum& b) {
  *this = *this + b;				// call Bignum operator+
}



// operator-= -- overloaded subtraction assignment operator for Bignums
// Inputs:  reference to Bignum
// Outputs:  void
inline void Bignum::operator-= (const Bignum& b) {
  *this = *this - b;				// call Bignum operator-
}



// operator*= -- overloaded multiplication assignment operator for Bignums
// Inputs:  reference to Bignum
// Outputs:  void
inline void Bignum::operator*= (const Bignum& b) {
  *this = *this * b;				// call Bignum operator*
}



// operator/= -- overloaded division assignment operator for Bignums
// Inputs:  reference to Bignum
// Outputs:  void
inline void Bignum::operator/= (const Bignum& b) {
  *this = *this / b;				// call Bignum operator/
}



// operator%= -- overloaded modulus assignment operator for Bignums
// Inputs:  reference to Bignum
// Outputs:  void
inline void Bignum::operator%= (const Bignum& b) {
  *this = *this % b;				// call Bignum operator%
}



// operator<<= -- overloaded left shift assignment operator for Bignums
// Inputs:  reference to Bignum
// Outputs:  void
inline void Bignum::operator<<= (const Bignum& b) {
  *this = *this << long(b);			// call Bignum operator<<
}



// operator>>= -- overloaded right shift assignment operator for Bignums
// Inputs:  reference to Bignum
// Outputs:  void
inline void Bignum::operator>>= (const Bignum& b) {
  *this = *this >> long(b);			// call Bignum operator>>
}



// operator<< -- output operator for pointers to Bignums
inline ostream& operator<< (ostream& os, const Bignum* b) {
  return os << *b;				// call Bignum output operator
}

#endif BIGNUMH					// End BIGNUMH

