/*
    bigint.c - Manage big positive integer numbers
    Copyright (c) 1996,2001,5  Martin Schulze <joey@infodrom.org>

    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; if not, write to the Free Software
    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

    $Id$
 */

#include "bigint.h"
#include <stdio.h>
#include <string.h>
#include <malloc.h>

bigint bigint_add(bigint a, bigint b)
{
  int i;
  unsigned long int tmp;
  bigint c;

  for (i=0; i<BIGINT_LEN; i++) {
    tmp = a.val[i] + b.val[i];
    if (tmp >= BIGINT_MAX) {
      c.val[i] = tmp - BIGINT_MAX;
      if (i<BIGINT_LEN-1)
	a.val[i+1]++;
      else
	fprintf(stderr, "Overflow in bigint addition.\n");
    } else
      c.val[i] = tmp;
  }
  return c;
}

bigint bigint_sub(bigint a, bigint b)
{
  unsigned long int tmp;
  int t;
  int i;
  int cmp = bigint_cmp(a,b);
  bigint rem = bigint_int(0);;

  if (cmp == -1) {
    fprintf(stderr, "Error in bigint_sub: result is negative.\n");
    return bigint_int(0);
  }
  if (cmp == 0)
    return bigint_int(0);

  for (i=0;i<BIGINT_LEN;i++) {
    if (a.val[i] >= b.val[i]) {
      a.val[i] = a.val[i] - b.val[i];
      continue;
    }
    tmp = b.val[i];
    tmp = tmp - a.val[i];
    a.val[i] = 0;
    t = i;
    while (1) {
      if (t+1 >= BIGINT_LEN) {
	fprintf(stderr, "Error in bigint_sub.\n");
	return bigint_int(0);
      }
      if ( a.val[t+1] == 0 ) {
	t++;
	continue;
      }
      a.val[t+1] = a.val[t+1] - 1;
      while(t >= 0) {
	rem = bigint_add(rem, bigint_int(a.val[t]));
	a.val[t] = BIGINT_MAX - 1;
	t--;
      }
      a.val[i] = a.val[i] - tmp;
      a = bigint_add(a, bigint_int(1));
      a = bigint_add(a, rem);
      break;
    }
  }
  
  return a;
}

bigint bigint_int(int num)
{
  bigint x;
  int i;

  if (num < 0) {
    fprintf(stderr, "Trying to assign negative value to bigint.\n");
    num = 0;
  }

  for (i=0; i<BIGINT_LEN; i++) x.val[i] = 0L;
  if (num < BIGINT_MAX)
    x.val[0] = num;
  else {
    x.val[0] = num-BIGINT_MAX;
    x.val[1] = num/BIGINT_MAX;
  }

  return x;
}

bigint bigint_string(char *s)
{
  char tmp[BIGINT_PREC+1];
  bigint a;
  int i;
  char *cp, *x;

  for (i=0; i<BIGINT_LEN; i++) a.val[i] = 0L;
  if ((x = (char *)malloc(strlen(s)+1))) {
    strcpy(x, s);
    for (i=0; i<BIGINT_LEN; i++) {
      if (strlen(x)) {
	cp = x;
	if (strlen(x) > BIGINT_PREC)
	  cp += (strlen(x) - BIGINT_PREC);
	strcpy(tmp, cp);
	*cp = '\0';
	sscanf(tmp, "%lu", &a.val[i]);
      }
    }
    free (x);
  }

  return a;
}

void bigint_sprintf (char *res, char *format, bigint a)
{
  char s[(BIGINT_PREC*BIGINT_LEN)+1];
  char tmp[BIGINT_PREC+1];
  char form[6];
  int i, max;

  memset (s, 0, sizeof(s));
  sprintf(form, "%%0%dlu", BIGINT_PREC);
  max = BIGINT_LEN;
  for (;max>0 && !a.val[max-1];max--);
  if (max == 0) s[0] = '0';
  for (i=0; i<max; i++) {
    if (i<max-1)
      sprintf(tmp, form, a.val[i]);
    else
      sprintf(tmp, "%lu", a.val[i]);
    sprintf (res, "%s%s", tmp, s);
    sprintf (s, "%s", res);
  }
  sprintf (res, format, s);
}

int bigint_cmp(bigint a, bigint b)
{
  int i;

  for (i=BIGINT_LEN-1; i>=0; i--) {
    if (a.val[i] > b.val[i])
      return 1;
    if (a.val[i] < b.val[i])
      return -1;
    if (a.val[i] == b.val[i])
      continue;
  }

  return 0;
}