/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2009-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 USA
   
   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., 51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include "bigint.h"
#include "igraph_error.h"
#include "igraph_memory.h"

int igraph_biguint_init(igraph_biguint_t *b) {
  IGRAPH_CHECK(igraph_vector_limb_init(&b->v, IGRAPH_BIGUINT_DEFAULT_SIZE));
  igraph_vector_limb_clear(&b->v);
  return 0;
}

void igraph_biguint_destroy(igraph_biguint_t *b) {
  igraph_vector_limb_destroy(&b->v);
}

int igraph_biguint_copy(igraph_biguint_t *to, igraph_biguint_t *from) {
  return igraph_vector_limb_copy(&to->v, &from->v);
}

int igraph_biguint_extend(igraph_biguint_t *b, limb_t l) {
  return igraph_vector_limb_push_back(&b->v, l);
}

int igraph_biguint_size(igraph_biguint_t *b) {
  return (int) igraph_vector_limb_size(&b->v);
}

int igraph_biguint_resize(igraph_biguint_t *b, int newlength) {
  int origlen=igraph_biguint_size(b);
  IGRAPH_CHECK(igraph_vector_limb_resize(&b->v, newlength));
  if (newlength > origlen) {
    memset(VECTOR(b->v) + origlen, 0,
	   (size_t) (newlength-origlen) * sizeof(limb_t));
  }
  return 0;
}

int igraph_biguint_reserve(igraph_biguint_t *b, int length) {
  return igraph_vector_limb_reserve(&b->v, length);
}

int igraph_biguint_zero(igraph_biguint_t *b) {
  igraph_vector_limb_clear(&b->v);
  return 0;
}

int igraph_biguint_set_limb(igraph_biguint_t *b, int value) {
  IGRAPH_CHECK(igraph_vector_limb_resize(&b->v, 1));
  VECTOR(b->v)[0]=(limb_t) value;
  return 0;
}

igraph_real_t igraph_biguint_get(igraph_biguint_t *b) {
  int size=igraph_biguint_size(b);
  int i;
  double val=VECTOR(b->v)[size-1];
  if (size==0) { return 0.0; }
  for (i=size-2; i>=0; i--) {
    val = val * LIMBMASK + VECTOR(b->v)[i];
    if (!IGRAPH_FINITE(val)) break;
  }
  return val;
}

int igraph_biguint_compare_limb(igraph_biguint_t *b, limb_t l) {
  int n=igraph_biguint_size(b);
  return bn_cmp_limb(VECTOR(b->v), l, (count_t) n);
}

int igraph_biguint_compare(igraph_biguint_t *left, igraph_biguint_t *right) {
  /* bn_cmp requires the two numbers to have the same number of limbs,
     so we do this partially by hand here */
  int size_left=igraph_biguint_size(left);
  int size_right=igraph_biguint_size(right);
  while (size_left > size_right) { 
    if (VECTOR(left->v)[--size_left] > 0) { return +1; }
  }
  while (size_right > size_left) {
    if (VECTOR(right->v)[--size_right] > 0) { return -1; }
  }
  return bn_cmp( VECTOR(left->v), VECTOR(right->v), (count_t) size_right );
}


igraph_bool_t igraph_biguint_equal(igraph_biguint_t *left, igraph_biguint_t *right) {
  return 0 == igraph_biguint_compare(left, right);
}


igraph_bool_t igraph_biguint_bigger(igraph_biguint_t *left, 
				   igraph_biguint_t *right) {
  return 0 < igraph_biguint_compare(left, right);
}


igraph_bool_t igraph_biguint_biggerorequal(igraph_biguint_t *left, 
					  igraph_biguint_t *right) {
  return 0 <= igraph_biguint_compare(left, right);
}

int igraph_biguint_inc(igraph_biguint_t *res, igraph_biguint_t *b) {
  return igraph_biguint_add_limb(res, b, 1);
}

int igraph_biguint_dec(igraph_biguint_t *res, igraph_biguint_t *b) {
  return igraph_biguint_sub_limb(res, b, 1);
}


int igraph_biguint_add_limb(igraph_biguint_t *res, igraph_biguint_t *b, 
			    limb_t l) {
  int nlimb=igraph_biguint_size(b);
  limb_t carry;
  
  if (res != b) { IGRAPH_CHECK(igraph_biguint_resize(res, nlimb)); }
  
  carry=bn_add_limb( VECTOR(res->v), VECTOR(b->v), l, (count_t) nlimb);
  if (carry) { 
    IGRAPH_CHECK(igraph_biguint_extend(res, carry));
  }
  return 0;
}

int igraph_biguint_sub_limb(igraph_biguint_t *res, igraph_biguint_t *b, 
			    limb_t l) {
  int nlimb=igraph_biguint_size(b);
  
  if (res != b) { IGRAPH_CHECK(igraph_biguint_resize(res, nlimb)); }

  /* We don't check the return value here */
  bn_sub_limb( VECTOR(res->v), VECTOR(b->v), l, (count_t) nlimb);

  return 0;
}

int igraph_biguint_mul_limb(igraph_biguint_t *res, igraph_biguint_t *b,
			    limb_t l) {
  int nlimb=igraph_biguint_size(b);
  limb_t carry;
  
  if (res!= b) { IGRAPH_CHECK(igraph_biguint_resize(res, nlimb)); }
  
  carry=bn_mul_limb( VECTOR(res->v), VECTOR(b->v), l, (count_t) nlimb);
  if (carry) { 
    IGRAPH_CHECK(igraph_biguint_extend(res, carry));
  }
  return 0;
}

int igraph_biguint_add(igraph_biguint_t *res, igraph_biguint_t *left, 
		       igraph_biguint_t *right) {

  int size_left=igraph_biguint_size(left);
  int size_right=igraph_biguint_size(right);
  limb_t carry;

  if (size_left > size_right) { 
    IGRAPH_CHECK(igraph_biguint_resize(right, size_left));
    size_right=size_left;
  } else if (size_left < size_right) {
    IGRAPH_CHECK(igraph_biguint_resize(left, size_right));
    size_left=size_right;
  }
  IGRAPH_CHECK(igraph_biguint_resize(res, size_left));
  
  carry=bn_add( VECTOR(res->v), VECTOR(left->v), VECTOR(right->v), 
		(count_t) size_left);
  if (carry) {
    IGRAPH_CHECK(igraph_biguint_extend(res, carry));
  }
  return 0;
}

int igraph_biguint_sub(igraph_biguint_t *res, igraph_biguint_t *left, 
		       igraph_biguint_t *right) {
 
  int size_left=igraph_biguint_size(left);
  int size_right=igraph_biguint_size(right);
  
  if (size_left > size_right) { 
    IGRAPH_CHECK(igraph_biguint_resize(right, size_left));
    size_right=size_left;
  } else if (size_left < size_right) {
    IGRAPH_CHECK(igraph_biguint_resize(left, size_right));
    size_left=size_right;
  }
  IGRAPH_CHECK(igraph_biguint_resize(res, size_left));

  /* We don't check return value, left should not be smaller than right! */
  bn_sub( VECTOR(res->v), VECTOR(left->v), VECTOR(right->v), 
	  (count_t) size_left);
  
  return 0;
}

int igraph_biguint_mul(igraph_biguint_t *res, igraph_biguint_t *left,
		       igraph_biguint_t *right) {

  int size_left=igraph_biguint_size(left);
  int size_right=igraph_biguint_size(right);
  
  if (size_left > size_right) { 
    IGRAPH_CHECK(igraph_biguint_resize(right, size_left));
    size_right=size_left;
  } else if (size_left < size_right) {
    IGRAPH_CHECK(igraph_biguint_resize(left, size_right));
    size_left=size_right;
  }
  IGRAPH_CHECK(igraph_biguint_resize(res, 2*size_left));
  
  bn_mul( VECTOR(res->v), VECTOR(left->v), VECTOR(right->v), 
	  (count_t) size_left );
  return 0;
}

int igraph_biguint_div(igraph_biguint_t *q, igraph_biguint_t *r,
		       igraph_biguint_t *u, igraph_biguint_t *v) {

  int ret;
  int size_q=igraph_biguint_size(q);
  int size_r=igraph_biguint_size(r);
  int size_u=igraph_biguint_size(u);
  int size_v=igraph_biguint_size(v);
  int size_qru = size_q > size_r ? size_q : size_r;
  size_qru = size_u > size_qru ? size_u : size_qru;
  
  if (size_q < size_qru) { IGRAPH_CHECK(igraph_biguint_resize(q, size_qru)); }
  if (size_r < size_qru) { IGRAPH_CHECK(igraph_biguint_resize(r, size_qru)); }
  if (size_u < size_qru) { IGRAPH_CHECK(igraph_biguint_resize(u, size_qru)); }

  ret=bn_div( VECTOR(q->v), VECTOR(r->v), VECTOR(u->v), VECTOR(v->v), 
	      (count_t) size_qru, (count_t) size_v );
  
  if (ret) {
    IGRAPH_ERROR("Bigint division by zero", IGRAPH_EDIVZERO);
  }
  
  return 0;
}

#ifndef USING_R
int igraph_biguint_print(igraph_biguint_t *b) {
  return igraph_biguint_fprint(b, stdout);
}
#endif

int igraph_biguint_fprint(igraph_biguint_t *b, FILE *file) {

  /* It is hard to control memory allocation for the bn2d function,
     so we do our own version */

  int n=igraph_biguint_size(b);
  long int size=12*n+1;
  igraph_biguint_t tmp;
  char *dst;
  limb_t r;

  /* Zero? */
  if (!bn_cmp_limb(VECTOR(b->v), 0, (count_t) n)) {
    fputs("0", file);
    return 0;
  }
  
  IGRAPH_CHECK(igraph_biguint_copy(&tmp, b));
  IGRAPH_FINALLY(igraph_biguint_destroy, &tmp);
  dst=igraph_Calloc(size, char);
  if (!dst) {
    IGRAPH_ERROR("Cannot print big number", IGRAPH_ENOMEM);
  }
  IGRAPH_FINALLY(igraph_free, dst);
  
  size--;
  dst[size]='\0';
  while (0 != bn_cmp_limb(VECTOR(tmp.v), 0, (count_t) n)) {
    r=bn_div_limb(VECTOR(tmp.v), VECTOR(tmp.v), 10, (count_t) n);
    dst[--size] = '0' + (char) r;
  }

  fputs(&dst[size], file);
  
  igraph_Free(dst);
  igraph_biguint_destroy(&tmp);
  IGRAPH_FINALLY_CLEAN(2);
  
  return 0;
}