iutil.c

Arithmetic for integers of almost unlimited size for C and C++. Developed and copyrighted by Ra

/* Integer Version 2.0, RD, 21.1.93	iutil.c	*/

#include <config.h>
#include <math.h>
#include <iint.h>
#include <idigit.h>
#include <imem.h>
#include <stdio.h>

/* For the conversion from/to int and long */
#ifdef BASE32
#define int2DigitType  ((sizeof(int)+sizeof(DigitType)-1)/sizeof(DigitType))
#define uint2DigitType ((sizeof(unsigned int)+sizeof(DigitType)-1)/sizeof(DigitType))
#endif

#ifdef BASE64
#define int2DigitType  1 
#define uint2DigitType 1 
#endif

#define long2DigitType ((sizeof(long)+sizeof(DigitType)-1)/sizeof(DigitType))
#define ulong2DigitType ((sizeof(unsigned long)+sizeof(DigitType)-1)/sizeof(DigitType))

/* Standard maxlength at creation of Integer */
#define INITLENGTH 4

void
cI(a)
    register Integer *a;
{
    a->sign = PLUS;
    a->length = 0;
    a->maxlength = INITLENGTH;
    a->vec = newDigitVec(&a->maxlength);
}				/* cI */

void
cIasint(a, i)
    register Integer *a;
    register int i;
{
    if (i < 0)
    {
	a->sign = MINUS;
	i = -i;
    }
    else
	a->sign = PLUS;
    a->maxlength = int2DigitType;
    a->vec = newDigitVec(&a->maxlength);
    if (int2DigitType == 1)
    {
	a->vec[0] = i;
	if (i)
	    a->length = 1;
	else
	    a->length = 0;
	return;
    }
}				/* cIasint */

void
cIasuint(a, i)
    register Integer *a;
    register unsigned int i;
{
    a->sign = PLUS;
    a->maxlength = int2DigitType;
    a->vec = newDigitVec(&a->maxlength);
    if (int2DigitType == 1)
    {
	a->vec[0] = i;
	if (i)
	    a->length = 1;
	else
	    a->length = 0;
	return;
    }
}				/* cIasuint */

void
cIaslong(a, i)
    register Integer *a;
    register long i;
{
    if (i < 0)
    {
	a->sign = MINUS;
	i = -i;
    }
    else
	a->sign = PLUS;
    a->maxlength = long2DigitType;
    a->vec = newDigitVec(&a->maxlength);
    if (long2DigitType == 1)
    {
	a->vec[0] = i;
	if (i)
	    a->length = 1;
	else
	    a->length = 0;
	return;
    }
}				/* cIaslong */

void
cIasulong(a, i)
    register Integer *a;
    register unsigned long i;
{
    a->sign = PLUS;
    a->maxlength = long2DigitType;
    a->vec = newDigitVec(&a->maxlength);
    if (long2DigitType == 1)
    {
	a->vec[0] = i;
	if (i)
	    a->length = 1;
	else
	    a->length = 0;
	return;
    }
}				/* cIasulong */

void
cIasI(a, b)
/* create a from b */
    register Integer *a;
    register const Integer *b;
{
    register int i;
    a->sign = b->sign;
    a->length = b->length;
    a->maxlength = b->length;
    a->vec = newDigitVec(&a->maxlength);
    for (i = 0; i < b->length; i++)
	a->vec[i] = b->vec[i];
}				/* cIasI */

void
cImaxlength(a, l)
    register Integer *a;
    int l;
{
    a->sign = PLUS;
    a->length = 0;
    a->maxlength = l;
    a->vec = newDigitVec(&a->maxlength);
}				/* cI */

void
dI(a)
    register Integer *a;
{
    delDigitVec(a->vec, a->maxlength);
    a->vec = NULL;
}

Integer *
ncI()
{
    register Integer *a;
    a = _newInteger();
    cI(a);
    return a;
}

Integer *
ncIasint(i)
    int i;
{
    register Integer *a;
    a = _newInteger();
    cIasint(a, i);
    return a;
}

Integer *
ncIasuint(i)
    unsigned int i;
{
    register Integer *a;
    a = _newInteger();
    cIasuint(a, i);
    return a;
}

Integer *
ncIaslong(i)
    long i;
{
    register Integer *a;
    a = _newInteger();
    cIaslong(a, i);
    return a;
}

Integer *
ncIasulong(i)
    unsigned long i;
{
    register Integer *a;
    a = _newInteger();
    cIasulong(a, i);
    return a;
}

Integer *
ncIasI(b)
    Integer *b;
{
    register Integer *a;
    a = _newInteger();
    cIasI(a, b);
    return a;
}

Integer *
ncImaxlength(l)
    int l;
{
    register Integer *a;
    a = _newInteger();
    cImaxlength(a, l);
    return a;
}

void
ddI(a)
    Integer *a;
{
    dI(a);
    _delInteger(a);
}

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

void
IasI(a, b)
    register Integer *a;
    register const Integer *b;
{
    register int i;
    register int neededlength;
    a->sign = b->sign;
    neededlength = b->length;
    if (a->maxlength < neededlength)
    {
	delDigitVec(a->vec, a->maxlength);
	a->maxlength = neededlength;
	a->vec = newDigitVec(&a->maxlength);
    }
    a->length = neededlength;
    for (i = b->length - 1; i >= 0; i--)
	a->vec[i] = b->vec[i];
}				/* IasI */


#ifdef USE_IEEE_IASDBL

void
Iasdbl(x, d)
  register pInteger x;
  double d;
{
  long *mantisse;
  int exponent;
  double fraction;

  if (d == 0.0)
  {
    x->length = 0;
    x->sign = PLUS;
  }
  else
  {
    fraction = frexp(d, &exponent);
    mantisse = (long *) &fraction;
    x->length = 2;
#ifdef DOUBLES_HIGH_LOW
    x->sign = mantisse[0] >> 31;
    x->vec[1] = (mantisse[0] & 0x000fffff) | 0x00100000;
    x->vec[0] = mantisse[1];
#endif
#ifdef DOUBLES_LOW_HIGH
    x->sign = mantisse[1] >> 31;
    x->vec[1] = (mantisse[1] & 0x000fffff) | 0x00100000;
    x->vec[0] = mantisse[0];
#endif
    exponent -= 53;
    if (exponent >= 0)
      IslasD(x, exponent);
    else
      IsrasD(x, -exponent);

  }
}

#else

#define DigitsPerDouble	sizeof(double)/sizeof(long)

void
Iasdbl(x, d)
  pInteger x;
  double d;
{
  DigitType m;
  int ex;
  int i;

  x->sign = PLUS;
  if (d == 0.0)
  {
    x->length = 0;
    return;
  }
  if (d < 0.0)
  {
    x->sign = MINUS;
    d = -d;
  }
  x->length = DigitsPerDouble;
  d = frexp(d, &ex);
  if (ex <= 0)
  {
    x->length = 0;
    x->sign = PLUS;
    return;
  }
  for (i = 0; i < DigitsPerDouble; i++)
  {
    d = ldexp(d, BitsPerDigit);
    m = (DigitType) d;
    d -= m;
    x->vec[DigitsPerDouble - i - 1] = m;
  }
  ex -= (DigitsPerDouble * BitsPerDigit);
  if (ex >= 0)
    IslasD(x, ex);
  else
    IsrasD(x, -ex);
}

#endif

void
Iasint(a, i)
    register Integer *a;
    register int i;
{
    if (i < 0)
    {
	a->sign = MINUS;
	i = -i;
    }
    else
	a->sign = PLUS;
    if (int2DigitType == 1)
    {
	a->vec[0] = i;
	if (i)
	    a->length = 1;
	else
	    a->length = 0;
	return;
    }
}				/* Iasint */

void
Iaslong(a, i)
    register Integer *a;
    register long i;

{
    if (i < 0)
    {
	a->sign = MINUS;
	i = -i;
    }
    else
	a->sign = PLUS;

    if (long2DigitType == 1)
    {
	a->vec[0] = i;
	if (i)
	    a->length = 1;
	else
	    a->length = 0;
	return;
    }
}				/* Iaslong */

void
Iasuint(a, i)
    register Integer *a;
    register unsigned int i;

{
    a->sign = PLUS;

    if (uint2DigitType == 1)
    {
	a->vec[0] = i;
	if (i)
	    a->length = 1;
	else
	    a->length = 0;
	return;
    }
}				/* Iasuint */

void
Iasulong(a, i)
    register Integer *a;
    register unsigned long i;

{
    a->sign = PLUS;

    if (ulong2DigitType == 1)
    {
	a->vec[0] = i;
	if (i)
	    a->length = 1;
	else
	    a->length = 0;
	return;
    }
}				/* Iasulong */

void
Ias0(a)
    register Integer *a;
{
    a->length = 0;
    a->sign = PLUS;
}

void
Ias1(a)
    register Integer *a;
{
    a->length = 1;
    a->sign = PLUS;
    *(a->vec) = 1;
}

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

int
Ilog(a)
    const Integer *a;
/* return (groesste Ganze von log_2(|a|), bzw -1 falls a==0); */
{
    register DigitType m;
    register int i, j;

    i = a->length;
    if (!i)
	return -1;
    j = 0;
    m = a->vec[i - 1];
    m >>= 1;
    while (m)
    {
	m >>= 1;
	j++;
    }
    return j + (i - 1) * BitsPerDigit;
}

int
intlog(i)
    register int i;
/* return (groesste Ganze von log_2(|i|), bzw -1 falls a==0); */
{
    register int j;

    if (!i)
	return -1;
    j = 0;
    i >>= 1;
    while (i)
    {
	i >>= 1;
	j++;
    }
    return j;
}				/* intlog */

/* Added this to simplify error handling for lc TP */ 

void
default_Ierror(s)
    const char *s;
{
    fprintf(stderr, "I: %s\n", s);
    abort();
}				/* Ierror */

Ierror_handler Ierror = default_Ierror;

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

static unsigned long maxint = (1UL << (sizeof(int) * 8 - 1)) - 1;
static unsigned long maxnegint = (1UL << (sizeof(int) * 8 - 1));
static unsigned long maxuint = ~(0UL);
static unsigned long maxlong = (1UL << (sizeof(long) * 8 - 1)) - 1;
static unsigned long maxneglong = (1UL << (sizeof(long) * 8 - 1));

BOOLEAN
Iisint(a)
    const Integer *a;
{
    register DigitType u;
    if (!a->length)
	return TRUE;
    if (a->length > int2DigitType)
	return FALSE;
/* Maybe sizeof(int)<sizeof(DigitType), then int2DigitType==1 */
/* We assume that sizeof(long)>=sizeof(DigitType) */
    if (sizeof(int) < sizeof(DigitType))
    {
	if (a->sign == PLUS)
	    return a->vec[0] <= maxint;
	else
	    return a->vec[0] <= maxnegint;
    }
/* Now we assume that sizeof(DigitType) divides sizeof(int) ! */
    u = a->vec[0];
    if (a->sign == PLUS)
	return u <= maxint;
    else
	return u <= maxnegint;
}				/* Iisint */

BOOLEAN
Iisuint(a)
    const Integer *a;
{
    if (a->sign == MINUS)
	return FALSE;
    if (!a->length)
	return TRUE;
    if (a->length > int2DigitType)
	return FALSE;
/* Maybe sizeof(int)<sizeof(DigitType), then int2DigitType==1 */
/* We assume, that sizeof(long)>=sizeof(DigitType) */
    if (sizeof(int) < sizeof(DigitType))
	return a->vec[0] <= maxuint;
/* Now we assume, that sizeof(DigitType) divides sizeof(int) ! */
    return TRUE;
}				/* Iisuint */

BOOLEAN
Iislong(a)
    const Integer *a;
{
/* We assume that sizeof(long)>=sizeof(DigitType) and
   that sizeof(DigitType) divides sizeof(long) ! */
    register unsigned long u;
    if (!a->length)
	return TRUE;
    if (a->length > long2DigitType)
	return FALSE;
    u = a->vec[0];
    if (a->sign == PLUS)
	return u <= maxlong;
    else
	return u <= maxneglong;
}				/* Iislong */

BOOLEAN
Iisulong(a)
    const Integer *a;
{
    if (a->sign == MINUS)
	return FALSE;
/* We assume, that sizeof(DigitType) divides sizeof(long) ! */
    if (a->length <= long2DigitType)
	return TRUE;
    else
	return FALSE;
}				/* Iisulong */


int
intasI(a)
    const Integer *a;
/* We assume Iisint(a) to be true ! */
{
    register DigitType u;
    if (!a->length)
	return 0;
/* Maybe sizeof(int)<sizeof(DigitType), then int2DigitType==1 */
/* We assume that sizeof(long)>=sizeof(DigitType) */
    if (sizeof(int) < sizeof(DigitType))
    {
	if (a->sign == PLUS)
	    return a->vec[0];
	else
	    return -a->vec[0];
    }
/* Now we assume that sizeof(DigitType) divides sizeof(int) ! */
    u = a->vec[0];
    if (a->sign == PLUS)
	return u;
    else
	return -u;
}				/* intasI */

unsigned int
uintasI(a)
    const Integer *a;
/* We assume Iisuint(a) to be true ! */
{
    register DigitType u;
    if (!a->length)
	return 0;
/* Maybe sizeof(int)<sizeof(DigitType), then int2DigitType==1 */
/* We assume that sizeof(long)>=sizeof(DigitType) */
    if (sizeof(int) < sizeof(DigitType))
	return a->vec[0];
/* Now we assume that sizeof(DigitType) divides sizeof(int) ! */
    u = a->vec[0];
    return u;
}				/* uintasI */

long
longasI(a)
    const Integer *a;
/* We assume Iislong(a) to be true ! */
{
/* We assume that sizeof(long)>=sizeof(DigitType) and
   that sizeof(DigitType) divides sizeof(long) ! */
    register unsigned long u;
    if (!a->length)
	return 0;
    u = a->vec[0];
    if (a->sign == PLUS)
	return u;
    else
	return -u;
}				/* longasI */

unsigned long
ulongasI(a)
    const Integer *a;
/* We assume Iisulong(a) to be true ! */
{
/* We assume, that sizeof(DigitType) divides sizeof(long) ! */
    register unsigned long u;
    if (!a->length)
	return 0;
    u = a->vec[0];
    return u;
}				/* ulongasI */