/**
 * \file Integer.cpp
 * Classe de gestion d'entier de precision arbitraire.
 * 
 * @author Nicolas Janey
 * @author nicolas.janey@univ-fcomte.fr
 * @version 1.0, 01/01/10
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "Integer.h"

Integer::Integer(short bits) {
  this->bits = bits;
  t =(int *) calloc(bits,sizeof(int));
}

Integer::Integer(int bits,int *b) {
  this->bits = bits;
  t =(int *) calloc(bits,sizeof(int));
  set(bits,b);
}

Integer::Integer(int bits,int v) {
  this->bits = bits;
  t =(int *) calloc(bits,sizeof(int));
  set(v);
}

Integer::Integer(int bits,long v) {
  this->bits = bits;
  t =(int *) calloc(bits,sizeof(int));
  set(v);
}

Integer::Integer(int bits,Integer *v) {
  this->bits = bits;
  t =(int *) calloc(bits,sizeof(int));
  set(v);
}

Integer::Integer(int v) {
  bits = 8*sizeof(int);
  t =(int *) calloc(bits,sizeof(int));
  set(v);
}

Integer::Integer(long v) {
  bits = 8*sizeof(long);
  t =(int *) calloc(bits,sizeof(int));
  set(v);
}

Integer::Integer(Integer *v) {
  bits = v->bits;
  t =(int *) calloc(bits,sizeof(int));
  set(v);
}

Integer::~Integer(void) {
  free(t);
}

void Integer::set(int sbits,int *b) {
  memset(t,0x00,sbits*sizeof(int));
  for ( int i = 0 ; i < sbits ; i++ )
    t[sbits-i-1] = b[i];
}

void Integer::set(int v) {
  memset(t,0x00,bits*sizeof(int));
  int min = ( bits < 8*sizeof(int) ) ? bits : 8*sizeof(int);
  unsigned int mask = 0x0001;
  for ( int i = 0 ; i < min ; i++ ) {
    t[i] = (v&mask)>>i;
    mask <<= 1; }
}

void Integer::set(long v) {
  memset(t,0x00,bits*sizeof(int));
  int min = ( bits < 8*sizeof(long) ) ? bits : 8*sizeof(long);
  unsigned long mask = 0x0001;
  for ( int i = 0 ; i < min ; i++ ) {
    t[i] = (v&mask)>>i;
    mask <<= 1; }
}

void Integer::set(Integer *v) {
  memset(t,0x00,bits*sizeof(int));
  int min = ( bits < v->bits ) ? bits : v->bits;
  for ( int i = 0 ; i < min ; i++ )
    t[i] = v->t[i];
}

int Integer::getInt(void) {
  int v = 0;
  int min = ( bits < 8*sizeof(int) ) ? bits : 8*sizeof(int);
  unsigned int mask = 0x0001;
  for ( int i = 0 ; i < min ; i++ ) {
    if ( t[i] )
      v += mask;
    mask <<= 1; }
  return(v);
}

long Integer::getLong(void) {
  long v = 0;
  int min = ( bits < 8*sizeof(long) ) ? bits : 8*sizeof(long);
  unsigned long mask = 0x0001;
  for ( int i = 0 ; i < min ; i++ ) {
    if ( t[i] )
      v += mask;
    mask <<= 1; }
  return(v);
}

int Integer::nul(void) {
  for ( int i = 0 ; i < bits ; i++ )
    if ( t[i] )
      return(0);
  return(1);
}

int Integer::equal(Integer *v) {
  Integer *longest;
  Integer *shortest;
  int lc;
  if ( bits < v->bits ) {
    lc = bits;
    shortest = this;
    longest = v; }
    else {
    lc = v->bits;
    shortest = v;
    longest = this; }
  for ( int i = lc ; i < longest->bits ; i++ )
    if ( longest->t[i] )
      return(0);
  for ( int i = 0 ; i < lc ; i++ )
    if ( longest->t[i] != shortest->t[i] )
      return(0);
  return(1);
}

int Integer::sup(Integer *v) {
  if ( bits < v->bits ) {
    for ( int i = bits ; i < v->bits ; i++ )
      if ( v->t[i] ) {
        return(0); }
    for ( int i = bits-1 ; i >= 0 ; i-- ) {
      if ( t[i] > v->t[i] ) {
        return(1); }
      if ( t[i] < v->t[i] ) {
        return(0); } } }
    else {
    for ( int i = v->bits ; i < bits ; i++ )
      if ( t[i] ) {
        return(1); } 
    for ( int i = v->bits-1 ; i >= 0 ; i-- ) {
      if ( t[i] > v->t[i] ) {
        return(1); }
      if ( t[i] < v->t[i] ) {
        return(0); } } }
  return(0);
}

int Integer::inf(Integer *v) {
  if ( bits < v->bits ) {
    for ( int i = bits ; i < v->bits ; i++ )
      if ( v->t[i] ) {
        return(1); }
    for ( int i = bits-1 ; i >= 0 ; i-- ) {
      if ( t[i] < v->t[i] ) {
        return(1); }
      if ( t[i] > v->t[i] ) {
        return(0); } } }
    else {
    for ( int i = v->bits ; i < bits ; i++ )
      if ( t[i] ) {
        return(0); }
    for ( int i = v->bits-1 ; i >= 0 ; i-- ) {
      if ( t[i] < v->t[i] ) {
        return(1); }
      if ( t[i] > v->t[i] ) {
        return(0); } } }
  return(0);
}

int Integer::supOuEgal(Integer *v) {
  return(!inf(v));
}

int Integer::infOuEgal(Integer *v) {
  return(!sup(v));
}

int Integer::inc(void) {
  int retenu = 0;
  for ( int i = 0 ; i < bits ; i++ ) {
    int val = retenu+t[i]+((i==0) ? 1 : 0);
    t[i] = val%2;
    retenu = val>>1; }
  return(!retenu);
}

int Integer::dec(void) {
  return(1);
}

int Integer::drift(int v) {
  if ( v > 0 ) {
    int res = 1;
    int i = 0;
    while( i < v ) {
      if ( t[bits-1-i] ) {
        res = 0;
        i = v; }
      i++; }
    for ( i = bits-1 ; i >= 0 ; i-- ) {
      int pos = i-v;
      t[i] = ( pos >= 0 ) ? t[pos] : 0; }
    return(res); }
  if ( v < 0 ) {
    int res = 1;
    int i = 0;
    while( i < -v ) {
      if ( t[i] ) {
        res = 0;
        i = -v; }
      i++; }
    for ( int ii = 0 ; ii <= bits-1 ; ii++ ) {
      int pos = ii-v;
      t[ii] = ( pos < bits ) ? t[pos] : 0; }
    return(res); }
  return(1);
}

int Integer::add(Integer *v) {
  int min = ( bits < v->bits ) ? bits : v->bits;
  int retenu = 0;
  for ( int i = 0 ; i < bits ; i++ ) {
    if ( i < min ) {
      int val = retenu+t[i]+v->t[i];
      t[i] = val%2;
      retenu = val>>1; }
      else { 
      int val = retenu+t[i];
      t[i] = val%2;
      retenu = val>>1; } }
  return(!retenu);
}

int Integer::sub(Integer *v) {
  if ( inf(v) )
    return(0);
  int min = ( bits < v->bits ) ? bits : v->bits;
  int retenu = 0;
  for ( int i = 0 ; i < bits ; i++ ) {
    if ( i < min ) {
      int val = (t[i]-v->t[i]-retenu);
      switch (val) {
        case  1 :
        case  0 :
          t[i] = val;
          retenu = 0;
          break;
        case -1 :
          t[i] = 1;
          retenu = 1;
          break; } }
      else { 
      int val = (t[i]-retenu);
      switch (val) {
        case  1 :
        case  0 :
          t[i] = val;
          retenu = 0;
          break;
        case -1 :
          t[i] = 1;
          retenu = 1;
          break; } } }
  return(1);
}

int Integer::mul(Integer *v) {
  Integer *cp = new Integer(this);
  for ( int i = 0 ; i < bits ; i++ )
    t[i] = 0;
  int res = 1;
  for ( int i = 0 ; i < v->bits ; i++ )
    if ( v->t[i] ) {
      Integer *c = new Integer(cp);
      if ( !c->drift(i) )
        res = 0;
      if ( !add(c) )
        res = 0;
      delete(c); }
  delete(cp);
  return(res);
}

int Integer::div(Integer *v) {
  if ( v->nul() )
    return(0);
  if ( inf(v) ) {
    set(0);
    return(1); }
  Integer *aux = new Integer((short) (bits+1));
  aux->set(v);
  int n = 0;
  while ( aux->inf(this) ) {
    aux->drift(1);
    n++; }
  Integer *r = new Integer(this);
  set(0);
  while ( n > 0 ) {
    aux->drift(-1);
    n--;
    if ( r->inf(aux) ) {
      drift(1); }
      else {
      drift(1);
      inc();
      r->sub(aux); } }
  delete(r);
  delete(aux);
  return(1);
}

int Integer::mod(Integer *v) {
  if ( v->nul() )
    return(0);
  if ( inf(v) ) {
    return(1); }
  Integer *aux = new Integer((short) (bits+1));
  aux->set(v);
  int n = 0;
  while ( aux->inf(this) ) {
    aux->drift(1);
    n++; }
  Integer *q = new Integer(bits);
  while ( n > 0 ) {
    aux->drift(-1);
    n--;
    if ( inf(aux) ) {
      q->drift(1); }
      else {
      q->drift(1);
      q->inc();
      sub(aux); } }
  delete(q);
  delete(aux);
  return(1);
}

int Integer::nombreChiffres(int base) {
  Integer *v = new Integer(this);
  Integer *bs = new Integer(base);
  int cpt = 0;
  do {
    cpt++;
    v->div(bs); }
  while( !v->nul() );
  delete(v);
  delete(bs);
  return(cpt);
}

void Integer::sprintfb(char *s) {
  int l = nombreChiffres(2);
  for ( int i = l-1 ; i >= 0 ; i-- )
    sprintf(&s[l-1-i],"%d",t[i]);
  s[bits] = 0x00;
}

void Integer::printfb(void) {
  int l = nombreChiffres(2);
  char *s =(char *) calloc(l+1,sizeof(char));
  sprintfb(s);
  printf("%s",s);
  free(s);
}

void Integer::sprintfd(char *s) {
  int l = nombreChiffres(10);
  Integer *v = new Integer(this);
  Integer *b = new Integer(10);
  for ( int i = l-1 ; i >= 0 ; i-- ) {
    Integer *vv = new Integer(v);
    vv->mod(b);
    s[i] =(char) (48+vv->getInt());
    delete(vv);
    v->div(b); }
  delete(v);
  delete(b);
  s[l] = 0x00;
}

void Integer::printfd(void) {
  int l = nombreChiffres(10);
  char *s =(char *) calloc(l+1,sizeof(char));
  sprintfd(s);
  printf("%s",s);
  free(s);
}

void Integer::sprintfo(char *s) {
  int l = nombreChiffres(8);
  int p = 0;
  for ( int i = 0 ; i < l ; i++ ) {
    int v = 0;
    for ( int j = 0 ; j < 3 ; j++ ) {
      if ( p < bits ) {
        v += t[p]<<j;
        p++; } }
    s[l-1-i] =(char) (v+48); }
  s[l] = 0x00;
}

void Integer::printfo(void) {
  int l = nombreChiffres(8);
  char *s =(char *) calloc(l+1,sizeof(char));
  sprintfo(s);
  printf("%s",s);
  free(s);
}

void Integer::sprintfh(char *s) {
  int l = nombreChiffres(16);
  int p = 0;
  for ( int i = 0 ; i < l ; i++ ) {
    int v = 0;
    for ( int j = 0 ; j < 4 ; j++ ) {
      if ( p < bits ) {
        v += t[p]<<j;
        p++; } }
    s[l-1-i] =(char) (( v < 10 ) ? v+48 : v+55); }
  s[l] = 0x00;
}

void Integer::printfh(void) {
  int l = nombreChiffres(16);
  char *s =(char *) calloc(l+1,sizeof(char));
  sprintfh(s);
  printf("%s",s);
  free(s);
}

#ifdef VISUAL_STUDIO

Integer::Integer(int bits,long long v) {
  this->bits = bits;
  t =(int *) calloc(bits,sizeof(int));
  set(v);
}

Integer::Integer(long long v) {
  bits = 8*sizeof(long long);
  t =(int *) calloc(bits,sizeof(int));
  set(v);
}

void Integer::set(long long v) {
  int min = ( bits < 8*sizeof(long long) ) ? bits : 8*sizeof(long long);
  unsigned long long mask = 0x0001;
  for ( int i = 0 ; i < min ; i++ ) {
    t[i] =(int) ((v&mask)>>i);
    mask <<= 1; }
}

long long Integer::getLongLong(void) {
  long long v = 0;
  int min = ( bits < 8*sizeof(long long) ) ? bits : 8*sizeof(long long);
  unsigned long long mask = 0x0001;
  for ( int i = 0 ; i < min ; i++ ) {
    if ( t[i] )
      v += mask;
    mask <<= 1; }
  return(v);
}

#endif
