bignum.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 1,299 行 · 第 1/4 页

//
// 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 11/01/89 -- Initial implementation
// Updated: CLJ 04/19/90 -- Finished initial implementation of all functions
// Updated: MJF 05/24/90 -- Added group names to RAISE
// Updated: MJF 07/31/90 -- Added terse print
// Updated: DAN 01/08/91 -- Fixed bug in add and multiply_aux
// Updated: MJF 01/17/91 -- Fixed delete operations
// Updated: MJF 01/21/91 -- Fixed multiply_aux, divide_aux and left_shift
// Updated: DLS 03/22/91 -- New lite version
// Updated: JAM 08/12/92 -- removed DOS specifics, stdized #includes
// Updated: JAM 08/12/92 -- anach. form() replaced with iomanips
// Updated: JAM 08/12/92 -- added DBLRET_HACK in CoolBigNum(double)
// Updated: JAM 08/12/92 -- fixed(?) normalize() bug where 1 was being added
//                          to dividend Data which could cause it to wrap to 0
//
// The Bignum class implements  infinite precision integers  and arithmetic.  A
// Bignum  object storage  will grow and  shrink  in 16-bit chunks as necessary
// based upon  its current value.   Implicit  conversion to the  system defined
// types short, int, long,  float, and  double is supported by virtual operator
// member functions from   the  base Number   class.  Addition  and subtraction
// operations are performed by simple bitwise addition or subtraction on 32-bit
// boundaries with checks for carry flag propagation.   The  multiplication and
// division  operations  utilize  the 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.
//

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

#include <string.h>             // Include standard strings
#define C_STRINGH

#include <math.h>               // Include the standard math library
#include <ctype.h>              // Include character macros
#include <stdlib.h>             // Include standard c library support
#include <limits.h>             // for CHAR_BIT

#include <iomanip.h>          // Include stream maniplutors (eg, hex, setw)

int CoolBignum_Init::count;                     
int    data_bits_s;                             // Initialize to 0 by default
long   radix_s;    

CoolBignum zero_s;                              // There is only 1 set of
CoolBignum one_s;                               // these Bignums
CoolBignum eight_s;                             
CoolBignum ten_s;                               // Constructors are called 
CoolBignum sixteen_s;                           // for static libraries.
CoolBignum max_short_s;
CoolBignum max_int_s;                           // No constructor called
CoolBignum max_long_s;                          // for dynamic libraries,
CoolBignum max_float_s;                         // so these bignums are blank
CoolBignum negmax_float_s;                              // so these bignums are blank
CoolBignum max_double_s;                        
CoolBignum negmax_double_s;

// Reinitialize one more time, if default constructor is called for 
// above globals.

CoolBignum_Init bignum_init2_s;         // Offset static/dynamic difference

CoolBignum_Init::CoolBignum_Init() {
  if ((count++ == 0) ||                         // from bignum_init1_s
      (((double)(max_double_s)) == 0.0)) {              // from bignum_init2_s
    data_bits_s   = BITS(Data);                 // This initializer creates
    radix_s       = long(pow(2.0,data_bits_s)); // correct values for
    zero_s       = CoolBignum();                // above global objects,
    one_s        = CoolBignum(long(1));         // as soon as Bignum.h is
    eight_s      = CoolBignum(long(8));         // included as header in
    ten_s        = CoolBignum(long(10));        // main.C
    sixteen_s    = CoolBignum(long(16));
    max_short_s  = CoolBignum(long(MAXSHORT));
    max_int_s    = CoolBignum(long(MAXINT));
    max_long_s   = CoolBignum(MAXLONG);
    max_float_s  = CoolBignum(MAXFLOAT);
    max_double_s = CoolBignum(MAXDOUBLE);
    negmax_float_s  = CoolBignum(-MAXFLOAT);
    negmax_double_s = CoolBignum(-MAXDOUBLE);
  }
}

CoolBignum_Init::~CoolBignum_Init() {}          // no clean up needed





// CoolBignum - simple constructor
// Inputs:  none
// Outputs:  initialized CoolBignum

CoolBignum::CoolBignum () {
  this->data = NULL;                            // No need to allocate yet
  this->count = 0;                              // Size of data is 0
  this->sign = 1;                               // CoolBignum >= 0
  this->state = N_OK;                           // State is ok
}



// ~CoolBignum - destructor
// Inputs:  none
// Outputs:  none

CoolBignum::~CoolBignum () {
  delete [] this->data;                 // Delete any allocated data
}



// CoolBignum - CoolBignum constructor with long argument
// Inputs:  long to be converted to CoolBignum
// Outputs:  new CoolBignum

CoolBignum::CoolBignum (const long inval) {
  long l = inval;
  if (l >= 0)                                   // Get correct sign
    this->sign = 1;
  else {
    l = -l;                                     // Get absolute value of l
    this->sign = -1;
  }
  Data buf[sizeof(l)];                  // Temp buffer to store l in
  Counter i = 0;                        // buffer index
  while (l) {                           // While more bits in l
    if (i >= sizeof(l)) {               // If no more buffer space
      this->state = N_NO_CONVERSION;    //   raise an exception
      no_conversion("CoolBignum(long)");
    }
    buf[i] = Data(l);                           // Peel off lower order bits
    l >>= data_bits_s;                          // Shift next bits into place
    i++;                                
  }
  this->data = ((this->count = i) > 0 ? // Allocate permanent data
    new Data[i] : 0);
  i = 0;                                       
  while (i < this->count) {                     // Save buffer into perm. data
    this->data[i] = buf[i];
    i++;
  }
  this->state = N_OK;                           // Set status to OK
}


// CoolBignum - CoolBignum constructor with double argument
// Inputs:  double to be converted to CoolBignum
// Outputs:  new CoolBignum

CoolBignum::CoolBignum (const double inval) {
  double d = inval;
  if (d >= 0)                                   // Get sign of d
    this->sign = 1;
  else {
    d = -d;                                     // Get absolute value of d
    this->sign = -1;
  }
#if 1
  // need to assign 'double' return value to temporary because of small error
  const double LOG10_MAXDOUBLE = log10(MAXDOUBLE);
  const double LOG10_RADIX_S = log10(double(radix_s));
  const int buf_size_s = int(LOG10_MAXDOUBLE/LOG10_RADIX_S);
  if (buf_size_s==63 && d==MAXDOUBLE) {
    printf("buf_size_s is 63 for MAXDOUBLE!\n");
    cout << setprecision(16) << MAXDOUBLE << ' ' << radix_s << ' ' << LOG10_MAXDOUBLE << ' ' << LOG10_RADIX_S << ' ' << buf_size_s << endl;
    abort();
    }
#else  // 
  static int buf_size_s = 
    int (log10(MAXDOUBLE)/log10(radix_s));      // Size of buffer to convert d
#endif
  Data *buf = new Data[buf_size_s];             // Buffer to convert d into
  Counter i = 0;                                // buffer index
    while (d >= 1.0) {                          
    if (i >= buf_size_s) {                      // If no more buffer space
      this->state = N_NO_CONVERSION;            //   raise an exception
      no_conversion("CoolBignum(double)");
    }
    buf[i] = Data(fmod(d,radix_s));             // Get next data "digit" from d
    d /= radix_s;                               // Shift d right 1 data "digit"
    i++;                                        // Increment buffer index
  }
  this->data = (i > 0 ? new Data[i] : 0);       // Allocate permanent data
  this->count = i;                              // Save count
  i = 0;                                       
  while (i < this->count) {                     // Copy temp buffer into 
    this->data[i] = buf[i];                     //   permanent data
    i++;
  }
  this->state = N_OK;                           // Set status to OK
  delete [] buf;                                // Deallocate buffer
}



// dtoBignum -- convert decimal string to CoolBignum
// Inputs:  string representation of decimal literal to be converted
// Outputs:  number of characters actually converted

int CoolBignum::dtoBignum (const char *s) {
  Counter len = 0;                              // No chars converted yet
  if (s[0] == '-' || s[0] == '+') len++;        // Skip over leading +,-
  while (isdigit(s[len])) {                     // If current char is digit
    (*this) = ((*this) * ten_s) +               // Shift CoolBignum left a decimal
      CoolBignum(long(s[len++] - '0'));         //   digit and add new digit
  }
  if (s[0] == '-') this->sign = -1;             // If s had leading -, note it
  return len;                                   // Return # of chars processed
}



// exptoBignum -- convert exponential string to a CoolBignum
// Inputs:  string representation of exponential literal to be converted
// Outputs:  none

void CoolBignum::exptoBignum (const char *s) {
  Counter pos = this->dtoBignum(s) + 1;         // Convert the base, skip [eE]
  long pow = atol(s + pos);                     // Convert the exponent to long
  while (pow-- > 0)                             // Raise CoolBignum to the given
    *this = (*this) * ten_s;                    //   power
}



// ctox - convert hex character to integer hex value (ASCII or EBCDIC)
// Inputs:  character representation of a hex number
// Outputs:  integer value of the hex number

unsigned int ctox (int c) {
  if ('0' <= c && c <= '9')
    return c - '0';
  if ('a' <= c && c <= 'f')
    return c - 'a' + 10;
  return c - 'A' + 10;
}



// xtoBignum -- convert hex string to CoolBignum value
// Inputs:  string representation of hex number to be converted
// Outputs:  none

void CoolBignum::xtoBignum (const char *s) {
  Counter size = strlen(s);
  Counter len = 2;                              // skip leading "0x"
  while (len < size) {                          // While there are more chars
    (*this) = ((*this) * sixteen_s) +           // Shift CoolBignum left one hex
      CoolBignum(long(ctox(s[len++])));         //   digit and add next digit
  }
}


  
// otoBignum -- convert octal string to CoolBignum
// Inputs:  string representation of octal number to be converted
// Outputs:  none

void CoolBignum::otoBignum (const char *s) {
  Counter size = strlen(s);
  Counter len = 0;                              // No chars converted yet
  while (len < size) {                          // While there are more chars
    (*this) = ((*this) * eight_s) +             // Shift CoolBignum left 1 oct dig.
      CoolBignum(long(s[len++] - '0'));         // Add next character value
  }
}



// CoolBignum -- CoolBignum constructor with string argument
// Inputs:  string representation of number to be converted to CoolBignum
// Outputs:  new CoolBignum with converted value

CoolBignum::CoolBignum (const char *s) {
  static CoolRegexp                                     // Declare CoolRegexp's for
    decimal(" *^[-+]?[1-9][0-9]*$"),                  // decimal
    exponential(" *^[-+]?[1-9][0-9]*[eE][1-9][0-9]*$"), // exponential
    hexadecimal(" *^[0][xX][0-9a-fA-F]+$"),           // hex
    octal(" *^[0][0-7]*$");                           // octal.

  // Init *this to a CoolBignum value of 0
  this->data = 0;                       
  this->count = 0;                              
  this->sign = 1;                               
  this->state = N_OK;

  if (decimal.find(s))                          // If string is decimal
    this->dtoBignum(s);                         // convert decimal to CoolBignum
  else if (exponential.find(s))                 // If string is exponential
    this->exptoBignum(s);                       // convert exp. to CoolBignum
  else if (hexadecimal.find(s))                 // If string is hex,
    this->xtoBignum(s);                         // convert hex to CoolBignum
  else if (octal.find(s))                       // If string is octal
    this->otoBignum(s);                         // convert octal to CoolBignum
  else {                                        // Otherwise
    this->state = N_NO_CONVERSION;              // raise an exception
    no_conversion("CoolBignum(const char *)");
  }
}



// CoolBignum - CoolBignum constructor with CoolBignum reference argument
// Inputs:  reference to CoolBignum
// Outputs:  new CoolBignum with same value as input

CoolBignum::CoolBignum (const CoolBignum& b) {
  this->count = b.count;                        // Copy b's count
  this->data =                                  // Allocate data if necessary
    (b.count > 0 ? new Data[b.count] : 0);
  for (Counter i = 0; i < this->count; i++)     // Copy b's data 
    this->data[i] = b.data[i];  
  this->sign = b.sign;                          // Copy b's sign