number.c

操作系统源代码

/* number.c: Implements arbitrary precision numbers. */

/*  This file is part of bc written for MINIX.
    Copyright (C) 1991, 1992 Free Software Foundation, Inc.

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License , or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; see the file COPYING.  If not, write to
    the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.

    You may contact the author by:
       e-mail:  [e-mail]
      us-mail:  Philip A. Nelson
                Computer Science Department, 9062
                Western Washington University
                Bellingham, WA 98226-9062
       
*************************************************************************/

#include "bcdefs.h"
#include "proto.h"

/* Storage used for special numbers. */
bc_num _zero_;
bc_num _one_;
bc_num _two_;


/* "Frees" a bc_num NUM.  Actually decreases reference count and only
   frees the storage if reference count is zero. */

void
free_num (num)
    bc_num *num;
{
  if (*num == NULL) return;
  (*num)->n_refs--; 
  if ((*num)->n_refs == 0) free(*num);
  *num = NULL;
}


/* new_num allocates a number and sets fields to known values. */

bc_num
new_num (length, scale)
     int length, scale;
{
  bc_num temp;

  temp = (bc_num) malloc (sizeof(bc_struct)+length+scale);
  if (temp == NULL) out_of_memory ();
  temp->n_sign = PLUS;
  temp->n_len = length;
  temp->n_scale = scale;
  temp->n_refs = 1;
  temp->n_value[0] = 0;
  return temp;
}


/* Intitialize the number package! */

void
init_numbers ()
{
  _zero_ = new_num (1,0);
  _one_  = new_num (1,0);
  _one_->n_value[0] = 1;
  _two_  = new_num (1,0);
  _two_->n_value[0] = 2;
}


/* Make a copy of a number!  Just increments the reference count! */

bc_num
copy_num (num)
     bc_num num;
{
  num->n_refs++;
  return num;
}


/* Initialize a number NUM by making it a copy of zero. */

void
init_num (num)
     bc_num *num;
{
  *num = copy_num (_zero_);
}


/* Convert an integer VAL to a bc number NUM. */

void
int2num (num, val)
     bc_num *num;
     int val;
{
  char buffer[30];
  char *bptr, *vptr;
  int  ix = 1;
  char neg = 0;
  
  /* Sign. */
  if (val < 0)
    {
      neg = 1;
      val = -val;
    }
  
  /* Get things going. */
  bptr = buffer;
  *bptr++ = val % 10;
  val = val / 10;
  
  /* Extract remaining digits. */
  while (val != 0)
    {
      *bptr++ = val % 10;
      val = val / 10;
      ix++; 		/* Count the digits. */
    }
  
  /* Make the number. */
  free_num (num);
  *num = new_num (ix, 0);
  if (neg) (*num)->n_sign = MINUS;
  
  /* Assign the digits. */
  vptr = (*num)->n_value;
  while (ix-- > 0)
    *vptr++ = *--bptr;
}


/* Convert a number NUM to a long.  The function returns only the integer 
   part of the number.  For numbers that are too large to represent as
   a long, this function returns a zero.  This can be detected by checking
   the NUM for zero after having a zero returned. */

long
num2long (num)
     bc_num num;
{
  long val;
  char *nptr;
  int  index;

  /* Extract the int value, ignore the fraction. */
  val = 0;
  nptr = num->n_value;
  for (index=num->n_len; (index>0) && (val<=(LONG_MAX/10)); index--)
    val = val*10 + *nptr++;
  
  /* Check for overflow.  If overflow, return zero. */
  if (index>0) val = 0;
  if (val < 0) val = 0;
 
  /* Return the value. */
  if (num->n_sign == PLUS)
    return (val);
  else
    return (-val);
}


/* The following are some math routines for numbers. */
_PROTOTYPE(static int _do_compare, (bc_num n1, bc_num n2, int use_sign,
				    int ignore_last));
_PROTOTYPE(static void _rm_leading_zeros, (bc_num num));
_PROTOTYPE(static bc_num _do_add, (bc_num n1, bc_num n2));
_PROTOTYPE(static bc_num _do_sub, (bc_num n1, bc_num n2));
_PROTOTYPE(static void _one_mult, (unsigned char *num, int size, int digit,
				   unsigned char *result));



/* Compare two bc numbers.  Return value is 0 if equal, -1 if N1 is less
   than N2 and +1 if N1 is greater than N2.  If USE_SIGN is false, just
   compare the magnitudes. */

static int
_do_compare (n1, n2, use_sign, ignore_last)
     bc_num n1, n2;
     int use_sign;
     int ignore_last;
{
  char *n1ptr, *n2ptr;
  int  count;
  
  /* First, compare signs. */
  if (use_sign && n1->n_sign != n2->n_sign)
    {
      if (n1->n_sign == PLUS)
	return (1);	/* Positive N1 > Negative N2 */
      else
	return (-1);	/* Negative N1 < Positive N1 */
    }
  
  /* Now compare the magnitude. */
  if (n1->n_len != n2->n_len)
    {
      if (n1->n_len > n2->n_len)
	{
	  /* Magnitude of n1 > n2. */
	  if (!use_sign || n1->n_sign == PLUS)
	    return (1);
	  else
	    return (-1);
	}
      else
	{
	  /* Magnitude of n1 < n2. */
	  if (!use_sign || n1->n_sign == PLUS)
	    return (-1);
	  else
	    return (1);
	}
    }

  /* If we get here, they have the same number of integer digits.
     check the integer part and the equal length part of the fraction. */
  count = n1->n_len + MIN (n1->n_scale, n2->n_scale);
  n1ptr = n1->n_value;
  n2ptr = n2->n_value;

  while ((count > 0) && (*n1ptr == *n2ptr))
    {
      n1ptr++;
      n2ptr++;
      count--;
    }
  if (ignore_last && count == 1 && n1->n_scale == n2->n_scale)
    return (0);
  if (count != 0)
    {
      if (*n1ptr > *n2ptr)
	{
	  /* Magnitude of n1 > n2. */
	  if (!use_sign || n1->n_sign == PLUS)
	    return (1);
	  else
	    return (-1);
	}
      else
	{
	  /* Magnitude of n1 < n2. */
	  if (!use_sign || n1->n_sign == PLUS)
	    return (-1);
	  else
	    return (1);
	}
    }

  /* They are equal up to the last part of the equal part of the fraction. */
  if (n1->n_scale != n2->n_scale) 
    if (n1->n_scale > n2->n_scale)
      {
	for (count = n1->n_scale-n2->n_scale; count>0; count--)
	  if (*n1ptr++ != 0)
	    {
	      /* Magnitude of n1 > n2. */
	      if (!use_sign || n1->n_sign == PLUS)
		return (1);
	      else
		return (-1);
	    }
      }
    else
      {
	for (count = n2->n_scale-n1->n_scale; count>0; count--)
	  if (*n2ptr++ != 0)
	    {
	      /* Magnitude of n1 < n2. */
	      if (!use_sign || n1->n_sign == PLUS)
		return (-1);
	      else
		return (1);
	    }
      }
  
  /* They must be equal! */
  return (0);
}


/* This is the "user callable" routine to compare numbers N1 and N2. */

int
bc_compare (n1, n2)
     bc_num n1, n2;
{
  return _do_compare (n1, n2, TRUE, FALSE);
}


/* In some places we need to check if the number NUM is zero. */

char
is_zero (num)
     bc_num num;
{
  int  count;
  char *nptr;

  /* Quick check. */
  if (num == _zero_) return TRUE;

  /* Initialize */
  count = num->n_len + num->n_scale;
  nptr = num->n_value;

  /* The check */
  while ((count > 0) && (*nptr++ == 0)) count--;

  if (count != 0)
    return FALSE;
  else 
    return TRUE;
}


/* In some places we need to check if the number is negative. */

char
is_neg (num)
     bc_num num;
{
  return num->n_sign == MINUS;
}


/* For many things, we may have leading zeros in a number NUM.
   _rm_leading_zeros just moves the data to the correct
   place and adjusts the length. */

static void
_rm_leading_zeros (num)
     bc_num num;
{
  int bytes;
  char *dst, *src;

  /* Do a quick check to see if we need to do it. */
  if (*num->n_value != 0) return;

  /* The first digit is 0, find the first non-zero digit in the 10's or
     greater place. */
  bytes = num->n_len;
  src = num->n_value;
  while (bytes > 1 && *src == 0) src++, bytes--;
  num->n_len = bytes;
  bytes += num->n_scale;
  dst = num->n_value;
  while (bytes-- > 0) *dst++ = *src++;
  
}


/* Perform addition: N1 is added to N2 and the value is
   returned.  The signs of N1 and N2 are ignored. */

static bc_num
_do_add (n1, n2)
     bc_num n1, n2;
{
  bc_num sum;
  int sum_scale, sum_digits;
  char *n1ptr, *n2ptr, *sumptr;
  int carry, n1bytes, n2bytes;

  /* Prepare sum. */
  sum_scale = MAX (n1->n_scale, n2->n_scale);
  sum_digits = MAX (n1->n_len, n2->n_len) + 1;
  sum = new_num (sum_digits,sum_scale);

  /* Start with the fraction part.  Initialize the pointers. */
  n1bytes = n1->n_scale;
  n2bytes = n2->n_scale;
  n1ptr = (char *) (n1->n_value + n1->n_len + n1bytes - 1);
  n2ptr = (char *) (n2->n_value + n2->n_len + n2bytes - 1);
  sumptr = (char *) (sum->n_value + sum_scale + sum_digits - 1);

  /* Add the fraction part.  First copy the longer fraction.*/
  if (n1bytes != n2bytes)
    {
      if (n1bytes > n2bytes)
	while (n1bytes>n2bytes)
	  { *sumptr-- = *n1ptr--; n1bytes--;}
      else
	while (n2bytes>n1bytes)
	  { *sumptr-- = *n2ptr--; n2bytes--;}
    }

  /* Now add the remaining fraction part and equal size integer parts. */
  n1bytes += n1->n_len;
  n2bytes += n2->n_len;
  carry = 0;
  while ((n1bytes > 0) && (n2bytes > 0))
    {
      *sumptr = *n1ptr-- + *n2ptr-- + carry;
      if (*sumptr > 9)
	{
	   carry = 1;
	   *sumptr -= 10;
	}
      else
	carry = 0;
      sumptr--;
      n1bytes--;
      n2bytes--;
    }

  /* Now add carry the longer integer part. */
  if (n1bytes == 0)
    { n1bytes = n2bytes; n1ptr = n2ptr; }
  while (n1bytes-- > 0)
    {
      *sumptr = *n1ptr-- + carry;
      if (*sumptr > 9)
	{
	   carry = 1;
	   *sumptr -= 10;
	 }
      else
	carry = 0;
      sumptr--;
    }

  /* Set final carry. */
  if (carry == 1)
    *sumptr += 1;
  
  /* Adjust sum and return. */
  _rm_leading_zeros (sum);
  return sum;  
}


/* Perform subtraction: N2 is subtracted from N1 and the value is
   returned.  The signs of N1 and N2 are ignored.  Also, N1 is
   assumed to be larger than N2.  */

static bc_num
_do_sub (n1, n2)
     bc_num n1, n2;
{
  bc_num diff;
  int diff_scale, diff_len;
  int min_scale, min_len;
  char *n1ptr, *n2ptr, *diffptr;
  int borrow, count, val;

  /* Allocate temporary storage. */
  diff_len = MAX (n1->n_len, n2->n_len);
  diff_scale = MAX (n1->n_scale, n2->n_scale);