/**********************************************************
*  Math operations on strings - Module used by calc.cpp,  *
*  calculator on huge integers.                           *
* ------------------------------------------------------- *
* Ref.: "PC Magazine Turbo Pascal for Windows, Techniques *
*        and Utilities By Neil J. Rubenking, Ziff Davis   *
*        Press, 1992.                                     *
*                                                         *
*                  C++ Release 1.0 By J-P Moreau, Paris.  *
**********************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

const 
      int cer_Ok 	 = 0; 
      int cer_Overflow   = 1; 
      int cer_LowMemory  = 2; 
      int cer_DivideBy0  = 3; 
      int cer_Quit       = 4; 
      int cer_Invalid    = 5; 

#define  FALSE  0
#define  TRUE   1
#define  MAX    5000   //Max. length of result string


char SubChar(char C1, char C2, bool *borrow) {
  int tmp;
  *borrow=FALSE;
  tmp= C1-C2;
  if (tmp<0) {
    tmp += 10;
    *borrow=TRUE;
  }
  return (char) tmp+48;
}

char AddChar(char C1, char C2, bool *carry) {
  int tmp;
  *carry=FALSE;
  tmp= C1+C2-96;
  if (tmp>=10) {
    tmp -= 10;
    *carry=TRUE;
  }
  return (char) tmp+48;
}

void TrimLead0(char *P, int Len) { 
// Trims leading zeros from a string P. up to length Len
  int Psn;
  Psn = 0; 
  while (Psn <= Len && P[Psn] == '0')  Psn++; 
  if (Psn > 0)  strcpy(P, P+Psn);
  if (P[0] == '\0')  strcpy(P, "0");
} 

//return A + B*10^TrailB
char *addWTrail(char *A, char *B, int TrailB, int MaxLen, int *Status) { 
  int i, LnA, LnB, Len; 
  bool carry; 
  long PsnA, PsnB; 
  char ChA, ChB; 
  char TB[MAX];

  LnA = strlen(A); 
  LnB = strlen(B) + TrailB; 
  Len = LnA; 
  if (LnB > Len)  Len = LnB; 
  Len++; 

  *Status = cer_Overflow; 
  if (LnA >= MaxLen-1 || LnB >= MaxLen-1 || LnA == 0 || LnB == 0) return A;
  
  *Status = cer_Ok; 
//make copy of parameter B and pad with 
//trailing 0's, if any are required. 
  strcpy(TB, B);
//FillChar(TB[StrLen(B)], TrailB, '0');  
  for (i=0; i<TrailB; i++)  TB[strlen(B)+i]='0';
  TB[LnB] = '\0'; 
  carry = FALSE;

//"Grow" A to hold result
//StrMove(A+Len-LnA, A, Succ(Lna));
//memcpy(A+Len-LnA, A, strlen(A));
  for (i=Len; i>Len-LnA-1; i--)  A[i]=A[i-Len+LnA];
  A[Len+1]='\0';

//FillChar(A^, Len-LnA, '0');
  for (i=0; i<Len-LnA; i++)  A[i]='0';
 
  PsnA = Len; 
  PsnB = LnB; 
//add digits from right to left 
  while (PsnB >= 0 || PsnA > 0) { 
    PsnB--; PsnA--; 
    ChA = A[PsnA]; 
    if (PsnB >= 0)  ChB = TB[PsnB]; 
    else ChB = '0'; 
    if (carry) 
      A[PsnA] = AddChar(ChA+1, ChB, &carry);
    else
      A[PsnA] = AddChar(ChA, ChB, &carry); 
  } 
  if (carry)  A[PsnA] = 'l'; 
  TrimLead0(A, MaxLen);
  return A;
}

//return A+B
char *add(char *A, char *B, int MaxLen, int *Status) { 
  return (addWTrail(A, B, 0, MaxLen, Status)); 
}
 
int Compare(char *X, char *Y) { 
// Returns -n if X < Y, 0 if equal, +n if X > Y 
  int  Xl, Yl, Xs, Ys; 
  Xl = strlen(X); Xs = 0;
  while (Xs <= Xl && X[Xs]=='0')  Xs++; 
  Yl = strlen(Y); Ys = 0; 
  while (Ys <= Yl && Y[Ys]=='0')  Ys++; 
  if ((Xl-Xs) == (Yl-Ys)) 
    return (strcmp(X+Xs, Y+Ys)); 
  else if ((Xl-Xs) > (Yl-Ys)) return (1); 
  else return (-1); 
}
 
//return A-B
char *sub(char *A, char *B, int MaxLen, int *Status) {
  int i, Len, LnA, LnB; 
  char TB[500]; 
  long PsnA, PsnB; 
  bool borrow, minus; 
  char ChA, ChB; 
 
  LnA = strlen(A); 
  LnB = strlen(B); 
 
  if (LnA >= MaxLen-1 || LnB >= MaxLen-1
    || LnA == 0 || LnB == 0) return A; 
// subtract smaller from larger 
  if (Compare(A, B) < 0) { 
    strcpy(TB,A);
    strcpy(A, B); 
    Len = LnA; 
    LnA	= LnB; 
    LnB	= Len; 
    minus = TRUE;
  } 
  else { 
    strcpy(TB,B);
    minus=FALSE;
  }

  *Status = cer_LowMemory;
  if (strlen(TB) == 0) return A; 
  *Status = cer_Ok; 
  borrow = FALSE; 
  Len = LnA;

  if (LnB > Len) Len = LnB; 
  Len++; 

// "Grow" A to hold result 
//memcpy(A+(Len-LnA), A, LnA+1);
  for (i=LnA; i>=Len-LnA; i--)  A[i]=A[i-1];
  A[LnA+1]='\0'; 
//FillChar(A^, Len-LnA, '0');  
  for (i=0; i<Len-LnA; i++)  A[i]='0';  
  PsnA = Len; 
  PsnB = LnB;

// subtract digits fram right to left 
  while (PsnB >= 0 || PsnA > 0) { 
    PsnA--; PsnB--; 

    if (PsnA >= 0)  ChA = A[PsnA];
    else ChA = '0';

    if (PsnB >= 0)  ChB = TB[PsnB];
    else ChB = '0';
    if (borrow) 
      A[PsnA] = SubChar(ChA-1, ChB, &borrow);
    else
      A[PsnA] = SubChar(ChA, ChB, &borrow);
  } 
  PsnA = 0;

  while (PsnA <- Len && A[PsnA] == '0')  PsnA++; 
  if (minus) { 
    PsnA--; 
    A[PsnA] = '-'; 
  } 
  strcpy(A, A+PsnA); 

  if (A[0] == '\0')  strcpy(A, "0"); 
  
  TrimLead0(A, MaxLen);
  return A;
  
} //sub 

// return product A*B 
char *prod(char *A, char *B, int MaxLen, int *Status) {
  char TB[MAX], TA[MAX];
  int i, PsnB, N, times, LnA, LnB, Len; 

  if (*Status != cer_Ok) return A; 
  LnA = strlen(A); 
  LnB = strlen(B); 
 
  if (LnA + LnB >= MaxLen || LnA == 0 || LnB == 0) return A; 
// multiply larger by smaller 
  if (Compare(A, B) < 0) { 
    strcpy(TB, A); 
    strcpy(A, B); 
    Len = LnA; 
    LnA = LnB; 
    LnB = Len; 
  } 
  else
    strcpy(TB, B); 
  strcpy(TA, A);
  Len = LnA + LnB; 
//Pascal: FillChar(A^, Len, '0');
  for (i=0; i<Len; i++)  A[i]='0';  
  A[Len] = '\0';
   
// for each digit of multiplier, right to left, 
// add together an appropriate number of copies 
// of multiplicand, tack the right number of 
// zeros on the end, and add the result to the 
// running total in T2.
  PsnB = LnB; 
  while (PsnB > 0 && *Status == cer_Ok) {
    PsnB--; 
    times = TB[PsnB]-48;
	for (N=1; N<=times; N++) 
      addWTrail(A, TA, LnB-1 - PsnB, MaxLen, Status);
  } 

  TrimLead0(A, MaxLen); 
  return A;
}  

// return A/B and remainder
char *divide(char *A, char *B, char *remainder, int MaxLen, int *Status) { 
  char Tl[MAX], T2[MAX]; 
  int psn1 , psn2, LnTl; 
 
  *Status = cer_Overflow; 

  if (A[0] == '\0' || B[0] == '\0') return A; 
  *Status = cer_DivideBy0; 
  if (Compare(B, "0") == 0) return A; 
  *Status = cer_Ok; 

  if (Compare(A, B) == 0) { 
    strcpy(A, "1"); 
    strcpy(remainder, "0"); 
  } 
  else if (Compare(A, B) < 0) { 
    strcpy(remainder, A); 
    strcpy(A, "0"); 
  } 
  else { 
//  A is larger than B 
    LnTl = strlen(A) + 3; 
    strcpy(Tl, B); 
    strcpy(T2, "1"); 
    strcpy(remainder, A); 
    *Status = cer_Ok; 
//  While dividend is > Tl. add 0s to Tl and to T2 
    while (Compare(A, Tl) > 0) { 
      strcat(Tl, "0"); 
      strcat(T2, "0"); 
    } 
    strcpy(A, "0"); 
    psn1 = strlen(Tl); psn2 = strlen(T2); 

//  get individual digits of quotient by repeated 
//  subtraction of Tl. Tl is the divisor with a 
//  steadily decreasing number of zeros after it. 
    while (Compare(Tl, B) != 0) { 
      psn1--; psn2--; 
      Tl[psn1] = '\0'; 
      T2[psn2] = '\0'; 
      while (Compare(remainder, Tl) >= 0) {
        sub(remainder, Tl, MaxLen, Status); 
        if (*Status != cer_Ok) return A; 
        add(A, T2, MaxLen, Status); 
        if (*Status != cer_Ok) return A; 
      } 
    } 
  }
  return A;	
}

//return A!
char *fact(char *A, int MaxLen, int *Status) { 
  char TA[MAX]; 
  int LnA;
  int i, N;
 
  *Status = cer_Overflow; 
  if (A[0] == '\0') return A; 
 
  LnA = strlen(A) + 3; 

  *Status = cer_Ok; 

  strcpy(TA, A);
  strcpy(A, "1"); 

  N = atoi(TA);

  for (i=2; i<=N; i++) {
    sprintf(TA,"%d", i);
    prod(A, TA, MaxLen, Status);
    if (*Status != cer_Ok) return A;
  }
  return A;
} 

//return B^E
char *power(char *B, char *E, int MaxLen, int *Status) { 
  char TH[MAX], TS[MAX]; 
  int LnT;
  int Ex, i;

  *Status = cer_Overflow; 
  if (B[0] == '\0' || E[0] == '\0') return B; 

  *Status = cer_Ok; 
  if (strcmp(B,"0")==0 || strcmp(E,"0")==0) {
    strcpy(B,"1"); 
    return B; 
  } 
  LnT = strlen(E) + 3; 

  strcpy(TH, E); 
  strcpy(TS, B); 

  Ex = atoi(TH);

  for (i=2; i<=Ex; i++) {
    prod(TS, B, MaxLen, Status);
    if (*Status != cer_Ok) return B;
  }

  strcpy(B, TS);

  return B;

} //power()


// return WW with added commas (Ex.: 4096300 --> 4,096,300)
char *AddComma(char *WW) { 
  int i, posn, MinLoc, newLen; 
  newLen = strlen(WW); 
  posn = newLen; 
  MinLoc = 3; 
  if (WW[1] == '-')  MinLoc++; 
  while (posn > MinLoc && newLen<MAX) { 
    posn -= 3;
//  Pascal: StrMove(WW+succ(posn), WW+posn, succ(NewLen-posn));	
    for (i=newLen; i>posn; i--) WW[i]=WW[i-1];
	WW[newLen+1]='\0';
    WW[posn] = ','; 
    newLen++; 
  }
  return WW;
}

// return WW with no commas (Ex.: 4,096,300 --> 4096300)
char *StripComma(char *WW) { 
  char *P; int i, Len; 
  Len = strlen(WW); 

  P=NULL;
  for (i=0; i<Len; i++) 
    if (WW[i]==',') P=&WW[i];

  while (P != NULL) { 
    memcpy(P, P+1, Len - (P-WW)); 
    Len--;
    P=NULL;
    for (i=0; i<Len; i++) 
      if (WW[i]==',') P=&WW[i];	
  }
  return WW;
}

// return TRUE if P is a valid (long) integer
bool AllNums(char *P) { 
  unsigned int N; 
  for (N=0; N<strlen(P); N++)
    if (P[N] < '0' || P[N] > '9') return FALSE;
  return TRUE;
}

// end of file pcalcfun.cpp