i5i.c

calc大数库

/* i5I.c */
/* programs for inputting and printing MPI's. */

#ifdef _WIN32
#include "unistd_DOS.h"
#else
#include <unistd.h>
#endif
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "integer.h"
#include "fun.h"


/*
This code implements a memory bank for allocated (but finished with) MPI's.
Please see the code below for more comments on what is happening.
		Peter Adams, 1/4/1993.

To turn the MPIBANK off, include the following line INSIDE these comments.
To turn the MPIBANK on,  move the line outside the comments.
#define WANTMPIBANK 
*/

#define WANTMPIBANK 
/*
Only maintain 4 MPIBANKS with at most 500 MPI's in each bank on a PC, due to
memory restrictions.
Maintain 20 MPIBANKS with no size limit on other machines
*/

#ifdef WANTMPIBANK
#ifdef _WIN32
#define NMPIBANKS 4
#define MAXMPIBSIZE 500
int MPI_BANKSIZE[NMPIBANKS];
#else
#define NMPIBANKS 20
#endif
#else    /* do not want the MPI bank at all */
#define NMPIBANKS 0
#endif

/* the +1 in the array dimension following is just to allow for the case when
NMPIBANKS is 0. We do not use the array in that case, but to simplify location
of the array definition inside #define statements, we just always define of
array of size at least 1 */

MPI *MPI_BANK[NMPIBANKS+1];

/*
The MPI Bank works like this:
MPI's are of different sizes. Hence it does not work to place all free'd MPI's
into the one bank. Now (in theory) MPI's can be of ANY size. However, in most
cases they are small. Hence much malloc'ing and free'ing was being done on
MPI's of the same small sizes. 

We maintain n=NMPIBANKS of free'd MPI's. Each of these banks is just a linked
list of MPI's of that size. 
*/

void INITMPIBANK()
/*
Initially, set the banks to being empty (a null pointer). On a PC, because we
restrict the length allowed for each list, set a counter to 0.
*/
{
	int i;

	for(i = 0; i < NMPIBANKS; i++)
	{
	  MPI_BANK[i] = NULL;
#ifdef _WIN32
	  MPI_BANKSIZE[i] = 0;
#endif
	}
}

MPI *BUILDMPI(unsigned int n)
/*
 * mallocs space for an MPI of length n.
 * If there is an MPI in the bank of this size, then use it rather than malloc.
 */
{
	MPI *Mptr;
	unsigned int m;

	m = n - 1;
	if(m < NMPIBANKS && MPI_BANK[m])
	{
	  Mptr = MPI_BANK[m];
	  MPI_BANK[m] = MPI_BANK[m]->NEXT;
#ifdef _WIN32
	  MPI_BANKSIZE[m]--;
#endif
	}
	else
	{
	  Mptr = (MPI *)mmalloc(sizeof(MPI));
	  Mptr->V = (unsigned long *)mmalloc(n * sizeof(unsigned long));
	  Mptr->D = n - 1;
	}
	return (Mptr);
}

void FREEMPIBANK()
/*
This routine should be called to clear out the MPI bank, usually at the end of
execution. If you like, you can call it during execution, and all of the MPI's
in the list will be free'd up. 
The only time you will probably want to call this during execution is if the
algorithm just performed a lot of very memory intensive operations, and so there
will be many many MPI's on the list. Freeing them up will free up some memory,
but it will mean that subsequent calls to create MPI's will need to perform the
(slow) malloc command until there are some more free ones.
*/
{
	int i;
	MPI *tmp,*this;
	unsigned int m;

	for(i=0; i<NMPIBANKS; i++)
	{
	  this=MPI_BANK[i];
	  while(this)
	  {
	    tmp=this->NEXT;
	    m = this->D;
	    ffree ((char *)(this->V), (1 + m) * sizeof(unsigned long));
	    ffree ((char *)this, sizeof(MPI));
	    this=tmp;
	  }
	  MPI_BANK[i]=NULL;
	}
	return;
}

void FREEMPI(MPI *Mptr)
/*
 * deallocates the space alloted for the MPI Mptr.
 * This involves placing it onto the appropriate MPI Bank, if there is such a
 * bank, and (on a PC) if there is room in the bank.
 * If it doesn't go into a bank, then it is free'd.
 */
{
	unsigned int m;
	
	if(Mptr==NULL)
		return;
	m = Mptr->D;

	if(m < NMPIBANKS) 
	{
#ifdef _WIN32
	  if(MPI_BANKSIZE[m] == MAXMPIBSIZE)
	  {
	    ffree (Mptr->V, (1 + m) * sizeof(unsigned long));
	    ffree (Mptr, sizeof(MPI));
	  }
	  else
	  {
	    Mptr->NEXT = MPI_BANK[m];
	    MPI_BANK[m] = Mptr;
	    MPI_BANKSIZE[m]++;
	  }
#else
	  Mptr->NEXT = MPI_BANK[m];
	  MPI_BANK[m] = Mptr;
#endif
	}
	else
	{
	  ffree (Mptr->V, (1 + m) * sizeof(unsigned long));
	  ffree (Mptr, sizeof(MPI));
	}
}

MPI *COPYI(MPI *Aptr)
/*
 * returns a pointer to a copy of *Aptr.
 */
{
        MPI *Bptr;
	if (Aptr == NULL)
	  return NULL;
	Bptr = BUILDMPI(1 + Aptr->D);
	Bptr->S = Aptr->S;
	memcpy(Bptr->V, Aptr->V, (1 + Aptr->D) * sizeof(unsigned long));
	return Bptr;
}

void FPRINTI(FILE *outfile, MPI *Mptr)
/*
 * the MPI *Mptr is printed in decimal notation to *outfile.
 * no new-line is incorporated. 
 */
{
	MPI *F, *Temp;
	unsigned long *A, l;
	int i = 0;
	
	if (Mptr->S == 0) 
	{
		fprintf(outfile, "%lu", (USL)0);
		return;
	}
	if (Mptr->S == -1) 
		fprintf(outfile, "-");
	F = ABSI(Mptr);
	l = LENGTHI(F);
	A = (unsigned long *)mmalloc((USL)(l * sizeof(unsigned long)));
	do 
	{
		A[i] = MOD0_(F, (USL)10);
		Temp = F;
		F = INT0_(F, (USL)10);
		FREEMPI(Temp);
		i++;
	}
        while (F->S);
	i--;
	FREEMPI(F);
	while (i >= 0) 
	{
		fprintf(outfile, "%lu", A[i]);
		i--;
	}
	ffree((char *)A, l * sizeof(unsigned long)); 
	return;
}

void PRINTI(MPI *Mptr)
{
	if (Mptr == NULL)
		printf("NULL");
	else
		FPRINTI(stdout, Mptr);
	return;

}

MPI *ZEROI()
/*
 * Returns the MPI ZERO.
 */
{
	MPI *Eptr;

	Eptr = BUILDMPI(1);
	Eptr->S = 0;
	Eptr->V[0] = 0;
	return Eptr;
}

MPI *ONEI()
/*
 * Returns the MPI ONE.
 */
{
	MPI *Eptr;

	Eptr = BUILDMPI(1);
	Eptr->S = 1;
	Eptr->V[0] = 1;
	return Eptr;
}

MPI *TWOI()
/*
 * Returns the MPI TWO.
 */
{
	MPI *Eptr;

	Eptr = BUILDMPI(1);
	Eptr->S = 1;
	Eptr->V[0] = 2;
	return Eptr;
}

MPI *THREEI()
/*
 * Returns the MPI THREE.
 */
{
	MPI *Eptr;

	Eptr = BUILDMPI(1);
	Eptr->S = 1;
	Eptr->V[0] = 3;
	return Eptr;
}

MPI *MINUS_ONEI()
/*
 * Returns the MPI MINUS_ONE.
 */
{
	MPI *Eptr;

	Eptr = BUILDMPI(1);
	Eptr->S = -1;
	Eptr->V[0] = 1;
	return Eptr;
}

MPI *CHANGE(unsigned long n)
/*
 * converts n, 0 <= n < R0*R0 to an MPI *Mptr. 
 */
{
	MPI *Mptr;

	if (n == 0)
        	Mptr = ZEROI();
	else if (n == 1)
        	Mptr = ONEI();
	else if (n < R0)
	{
		Mptr = BUILDMPI(1);
		Mptr->S = 1;
		Mptr->V[0] = n;
	}
	else
	{
		Mptr = BUILDMPI(2);
		Mptr->S = 1;
		Mptr->V[0] = n % R0;
		Mptr->V[1] = n / R0;
	}
	return Mptr;
}

MPI *CHANGEL(long n)
/*
 * converts n, -R0*R0/2 <= n < R0*R0/2 to an MPI *Mptr. 
 */
{
	MPI *Mptr;
	unsigned long m;

	if (n >= 0)
		return (CHANGE((USL)n));
	else
	{ 
		m = (USL)(-n);
		Mptr = CHANGE(m);
		Mptr->S = -1;
		return Mptr;
	}
}

MPI *CHANGEI(long n)
/*
 * converts n, |n| < R0 to an MPI *Mptr. 
 */
{
	MPI *Mptr;

	Mptr = BUILDMPI(1);
	Mptr->V[0] = (unsigned long)(abs(n));
	if (n == 0)
		Mptr->S = 0;
	if (n < 0)
		Mptr->S = -1;
	else 
		Mptr->S = 1;
	return Mptr;
}

MPI *FINPUTI(FILE *f, unsigned int *uptr)
/*
 * Converts decimal input from stream into an MPI.
 * Ignores the combination '\' followed by '\n'.
 * If a rubbish character is met before decimal input, Mptr is set to 0
 * and 0 is returned. All characters up to and including the first newline
 * met are wiped.
 * If a rubbish character is met immediately after decimal input, 0 is
 * returned and all characters up to and including the first newline met
 * are wiped. Otherwise 1 is returned.
 * In any case *Mptr is set equal to any inputted decimal.
 */
{
	unsigned long n;
	int s, t;
	MPI *Mptr, *Temp;

	Mptr = ZEROI();
	s = whitespace(f);
	if ((s != '-') && (s < '0' || s > '9')) 
	{
		printf("illegal character1 %c entered:\n", s);
		FFlush(f);
		*uptr = 0;
		return Mptr;
	}
	else if (s == '0')
	{
		s = fgetc(f);
		if (s != ' ' && s != '\n' && s != 'i' && s != '/' && s != '+' && s != '-')
		{
			printf("illegal character2 %c entered:\n", s);
			FFlush(f);
			*uptr = 0;
			return Mptr;
		}
		else 
		{
			ungetc(s, f);
			*uptr = 1;
			return Mptr;
		}
	}
	else if (s == '-') 
	{
		do
			s = fgetc(f);
		while (s == ' ');
		if (s <= '0' || s > '9')
		{
			printf("illegal character3 %c entered:\n", s);
			FFlush(f);
			*uptr = 0;
			return Mptr;
		}
		t = -1;
	}
        else
		t = 1;
	while ((s == '\\') || (s >= '0' && s <= '9')) 
	{
		if (s == '\\')
		/* for use with bc output, where '\' is followed by '\n' */
			s = fgetc(f);
		else 
		{
			Temp = Mptr;
			Mptr = MULT_I(Temp, 10L);
			FREEMPI(Temp);
			n = (unsigned long)(s - '0');
			Temp = Mptr;
			Mptr = ADD0_I(Temp, n);
			FREEMPI(Temp);
		}
	 	s = fgetc(f);
	}
	if (t == -1)
		Mptr->S = -1;
	if (s != ' ' && s != '\n' && s != 'i' && s != '/' && s != '+' && s != '-')
	{
		printf("illegal character4 %c entered:\n", s);
		FFlush(f);
		*uptr = 0;
		return Mptr;
	}
	ungetc(s, f);
	*uptr = 1;
	return Mptr;
}

MPI *INPUTI(unsigned int *uptr)
{
	return  FINPUTI(stdin, uptr);
}

unsigned int EQUALI (MPI *Aptr, MPI *Bptr)
/*
 * EQUALI(Aptr, Bptr) = 1 if *Aptr = *Bptr, otherwise  = 0.
 */
{
	int j;

	if (Aptr->S != Bptr->S)
		return (0);
	else if (Aptr->D != Bptr->D)
		return (0);
	else
	{
		j = Aptr->D;
		while ((Aptr->V[j] == Bptr->V[j]) && (j > 0))
			j--;
		if (Aptr->V[j] == Bptr->V[j])
			return (1);
		else
			return (0);
	}
}

MPI *ABSI(MPI *Aptr)
/*
 * *Bptr = |*Aptr|. 
 */
{
	MPI *Bptr;

	Bptr = COPYI(Aptr);
	Bptr->S = (Aptr->S >= 0 ? Aptr->S : -Aptr->S);
	return Bptr;
}

MPI *MINUSI(MPI *Aptr)
/*
 * *Bptr = -(*Aptr).
 */
{
	MPI *Bptr;

	Bptr = COPYI(Aptr);
	Bptr->S = -(Aptr->S);
	return Bptr;
}