#include "big.h"

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

#define CAPACITY 10
#define BASE 0x100000000

void bign_create_empty(struct bign *self) {
  //initializing an empty bign
  self->data=NULL;
  self->capacity= 0;
  self->size=0;
}
 

void bign_create_from_value(struct bign *self, uint32_t val) {
  //creating a bign out of a value
  self->capacity=CAPACITY;
  self->size=1;
  self->data=malloc(self->capacity*sizeof(uint32_t));
  self->data[0]=val;
  
}


//function that doubles the maximum capacity of a bign 
void extend_capacity(struct bign *self){
  self->capacity=self->capacity*2;
  //temp points to the curr array to keep the location
  uint32_t *temp=self->data;
  self->data=NULL;

  // allocating another mem segment to self->data
  self->data=calloc(self->capacity,sizeof(uint32_t));
  for(size_t i=0;i<self->size;i++){
    self->data[i]=temp[i];
  }
  //freeing the previous array to avoid memory leaks
  free(temp);
}

//function that converts a hex char into an integer
uint32_t hex_char_to_int(char val){

  //--------------------------------converting every char to an int
  //case '0'<str[index]<'9' 
  if(val>='0' && val<='9'){
    return (int)(val-'0');

  //case 'A'<str[index]<'Z' 
  } else if(val>='A' && val<='Z'){
    return (int)(val-'0'-('A'-'9'-1));

  //case 'a'<str[index]<'z' 
  } else if(val>='a' && val<='z'){
    return (int)(val-'0'-('a'-'9'-1));

  } 
  return -1;
}



void bign_create_from_string(struct bign *self, const char *str) {
  //getting the index of the first digit that s not a 0
  size_t length=strlen(str);
  size_t i=0;
  while(str[i]=='0'&& i<length-1){
    i++;
  }
  size_t first_digit=i;

  //initializing the bign
  self->size=0;
  self->capacity=CAPACITY;
  self->data=calloc(self->capacity,sizeof(uint32_t));

  int pow_16=1;
  size_t index_curr=length-1;    //index_curr is the index of the current  char we re treating 
  size_t digit_bign=0;          // index of the uint32_t we re working on
  uint32_t tmp=0;               //tmp is a temporary uint32_t used to add the char*pow16s together 
  size_t count=1;

  while(index_curr>first_digit ){

    //ading up the hex digits with the powers of 16
    tmp+=hex_char_to_int(str[index_curr])*pow_16;

    pow_16=pow_16*16; //incrementing the power of 16
    index_curr--;
    
    //every 8 hex chars assining the uint32 digit the value of tmp and giving every variable their default value
    if(count%8==0){
      self->size++;
      //checking if we need to extend the capacity 
      if(self->size>=self->capacity){
        extend_capacity(self);
      }
      
      self->data[digit_bign]=tmp;
      digit_bign++;
      pow_16=1;
      tmp=0;
      count=0;
    }
    count ++;
    
  }
  // case when the initial str size%8!=0 or if the the size of the bign is still 0
  // which can occur if the index of the first non 0 diigt is 0
  if(count!=0 || self->size==0){
    self->size++;
    self->data[digit_bign]=tmp+hex_char_to_int(str[index_curr])*pow_16;
  }
}



void bign_copy_from_other(struct bign *self, const struct bign *other) {
  //if data was already allocated we re freeing it
  if (self->data!=NULL){
    free(self->data);
  }

  //allocating a new array to self->data
  self->capacity=other->capacity;
  self->data=calloc(self->capacity,sizeof(uint32_t));
  self->size=other->size;
  
  //copying every digit
  for(size_t i=0;i<self->size;i++){
    self->data[i]=other->data[i];
  }
}

void bign_move_from_other(struct bign *self, struct bign *other) {
  //if data was already allocated we re freeing it
  if (self->data!=NULL){
    free(self->data);
  }
  //giving every value of other to self
  self->capacity=other->capacity;
  self->size=other->size;
  self->data=other->data;

  //not freeing other->data cause it would erase the array that s also pointed by self->data
  other->data=NULL;
  other->capacity=0;
  other->size=0;
}

void bign_destroy(struct bign *self) {
  //if data was already allocated we re freeing it
  if(self->data!=NULL){
    free(self->data);
  }
  self->size=0;
  self->capacity=0;
  
}

void bign_print(const struct bign *self) {

  if(self->size>0){
    //we re printing the number backwords 
    for(size_t i=self->size-1;i>0;i--){
    
      printf("%08X_",self->data[i]);  //%08x prints a uint32_t with the non significant 0s included
    } 
    // and printing data[0] separately to avoid having an underscore after the number
    printf("%08X",self->data[0]);
    printf("\n");

  }
  

}

int bign_cmp(const struct bign *lhs, const struct bign *rhs) {
  // comparing sizes
  if(lhs->size<rhs->size){
    return -1;
  }else if(lhs->size>rhs->size){
    return 1;
  } else {

    //if sizes are equal comparing every digit 
    for(size_t i =lhs->size;i>0;i--){
      if(lhs->data[i-1]>rhs->data[i-1]){
        return 1;
      }else if(lhs->data[i-1]<rhs->data[i-1]){
        return -1;
      }

    }
    
  }
  return 0;


  
}

int bign_cmp_zero(const struct bign *self) {
  if(self->data[0]==0 && self->size==1){
    return 0;
  }
    return 1;
}
/*
 *Les fonctions complémentaires
 *
 */
uint32_t bign_get(const struct bign *self,size_t i){
  if(i<self->size){
    return self->data[i];
  }
  return 0;
}

void bign_normalize(struct bign *self){
  size_t i = self->size-1;
  while(self->data[i]==0 && i>0){
    self->size--;
    i--;
  }

}

//function that returns the bigger size out of 2 bigns
size_t max(size_t nb1, size_t nb2){
  if(nb1>nb2){
    return nb1;
  } 
  return nb2;
}


void bign_add(struct bign *self, const struct bign *lhs, const struct bign *rhs) {
  //if self is empty we create it from 0
  if(self->data==NULL){
    bign_create_from_value(self, 0);
  }

  //initializing every local variable needed to calculate
  size_t n = max(lhs->size,rhs->size);
  uint64_t c=0;
  uint64_t sum = 0;

  uint64_t digit1=0;
  uint64_t digit2=0;

  //extending self's size/capacity to n+1
  size_t size=n+1;
  while(size>self->capacity){
    extend_capacity(self);
  }
  self->size=size;
  self->data[n]=0;   //setting data[n]to 0 because it s the only value that we might not change (if c= 0 at the end)

  for(size_t i=0;i<n;i++){

    //cases when i is higher than the size of one of the numbers
    if(i>=lhs->size){
      digit1=0;
    }else{digit1 = lhs->data[i]; }

    if(i>=rhs->size){
      digit2=0;
    }else{ digit2 = rhs->data[i]; }

    //add algorithm application
    sum = digit1+digit2+c;
    self->data[i]=sum%BASE;
    c=sum/BASE;
  }
  //adding c to data[n]
  self->data[n]+=c;
  
  bign_normalize(self);

}


void bign_sub(struct bign *self, const struct bign *lhs, const struct bign *rhs) {
  //if self is empty we create it from 0
  if(self->data==NULL){
    bign_create_from_value(self, 0);
  }
  
  //checking if the first number is bigger or equal to he second
  if(bign_cmp(lhs,rhs)>=0){

    uint32_t b=0;
    uint64_t diff=0;
    uint64_t digit2=0;

    //extending self's size/capacity to n+1
    size_t n = lhs->size;
    size_t size=n+1;
    while(size>self->capacity){
      extend_capacity(self);
    }
    self->size=size;
    self->data[n]=0;

    for(size_t i=0;i<n;i++){

      // case when the size of rhs is smaller than lhs's
      if(i>=rhs->size){
        digit2=0;
      }else{ digit2 = rhs->data[i]; }


      //main algorithm
      diff= lhs->data[i]-digit2-b;
      self->data[i]=diff%BASE;
      //making sure b(orrow) is [0;1]
      if(diff/BASE>0){
        b=1;  
      } else { b=0; }
      
    }

    bign_normalize(self);
  }
  
}

void bign_mul(struct bign *self, const struct bign *lhs, const struct bign *rhs) {
  if(self->data==NULL){
    bign_create_from_value(self, 0);
  }
  
  uint32_t c=0;
  uint64_t tmp=0;

  size_t n = lhs->size;
  size_t m = rhs->size;
  size_t size=n+m+1;
  //temporary array that holds the result
  uint32_t *tmp_data=calloc(size+1,sizeof(uint32_t));

  for (size_t i = 0; i < n; i++){

    c=0;
    for (size_t j = 0; j < m; j++){
      //casting the sum of uint32_t
      tmp= (uint64_t)lhs->data[i]*rhs->data[j]+ tmp_data[i+j]+c;

      tmp_data[i+j]= tmp%BASE;
      c= tmp/BASE;
    }
    if(c>0){
      tmp_data[i+m]=c;
    }
  } 
  //creating self out of the temporary array we allocated right above
  free(self->data);
  self->size=size;
  self->data=tmp_data;
  self->capacity=size+1;
  bign_normalize(self);

}


void bign_mul_karatsuba(struct bign *self, const struct bign *lhs, const struct bign *rhs) {
}

void bign_mul_short(struct bign *self, const struct bign *lhs, uint32_t rhs) {
  //making a bign out of the initial uint32_t to be able to use the mul functions
  struct bign tmp_big;
  bign_create_from_value(&tmp_big,rhs);

  bign_mul(self,lhs,&tmp_big);
  bign_destroy(&tmp_big);
}

// https://janmr.com/blog/2012/11/basic-multiple-precision-short-division/
void bign_div_short(struct bign *quo, uint32_t *rem, const struct bign *lhs, uint32_t rhs) {

  if(rhs !=0){
    uint64_t temp=0;

    for(size_t k =lhs->size; k>0; k--){
        
      temp=(uint64_t)(*rem*BASE+lhs->data[k-1]);
      quo->data[k-1]=temp/rhs;
      *rem=temp%rhs;
    }

  }

}


// https://janmr.com/blog/2014/04/basic-multiple-precision-long-division/
void bign_div(struct bign *quo, struct bign *rem, const struct bign *lhs, const struct bign *rhs) {
  //initializing  quo and rem at 0x0
  if(quo->data!=NULL){
    bign_destroy(quo);
  }
  if(rem->data!=NULL){
    bign_destroy(rem);
  }
  bign_create_from_value(quo, 0);
  bign_create_from_value(rem, 0);
  
  
  //case when rhs is a one digit bign
  if(rhs->size==1){
    while(lhs->size>=quo->capacity){
      extend_capacity(quo);
    }
    quo->size=lhs->size;

    bign_div_short(quo, rem->data, lhs, rhs->data[0]);
  }

  //normalizing the bigns
  bign_normalize(quo);
  bign_normalize(rem);

}


void expo(struct bign *lhs, struct bign *rhs, struct bign *self){
  //the bign that s going to be returned
  struct bign tmp;
  bign_create_from_value(&tmp, 1);

  uint32_t r=0;
  

  //case when n = 0
  if(bign_cmp_zero(rhs)== 0){
    bign_move_from_other(self, &tmp);

  //case when n=1
  }else if(bign_cmp(rhs,&tmp)==0 ){
    bign_move_from_other(self, lhs);
  }else{

    //dividing the n by 2 
    bign_div_short(&tmp, &r, rhs, 2);

    //n is even
    if(r==0){
      // rhs = rhs/2
      bign_move_from_other(rhs, &tmp);
      //lhs = lhs²
      bign_mul(lhs,lhs,lhs);
      
      expo(lhs,rhs,self);

    //n is odd
    } else {

      // rhs = (rhs-1)/2
      bign_move_from_other(rhs, &tmp);

      //keeping in memory the value of lhs
      bign_copy_from_other(&tmp, lhs);

      //lhs = lhs²
      bign_mul(lhs,lhs,lhs);
      
      expo(lhs,rhs,self);

      bign_mul(lhs, lhs, &tmp); //multiplication by lhs
    }
    
  }

  bign_destroy(&tmp);
  
}


void bign_exp(struct bign *self, const struct bign *lhs, const struct bign *rhs) {

  bign_destroy(self);

  //copies of lhs and rhs 
  struct bign big_l;
  bign_create_empty(&big_l);
  bign_copy_from_other(&big_l, lhs);

  struct bign big_r;
  bign_create_empty(&big_r);
  bign_copy_from_other(&big_r, rhs);


  //isolating the case when lhs ==0
  if(bign_cmp_zero(lhs)==0){
    bign_create_from_value(self, 0);
  } else {
    expo(&big_l, &big_r, self);
  }

  //destroying the copies 
  bign_destroy(&big_l);
  bign_destroy(&big_r);

  bign_normalize(self);
}


/*
 *
 * bigz
 *
 */

void bigz_create_empty(struct bigz *self) {
  self->positive=true;
  bign_create_empty(&self->n);
}

void bigz_create_from_value(struct bigz *self, int32_t val) {
  if(val<0){
    self->positive=false;
    val=-val;
  }else{
    self->positive=true;
  }
  bign_create_from_value(&self->n,val);

}



void bigz_create_from_string(struct bigz *self, const char *str, unsigned base) {
  size_t i=1;
  //checking if the number is >=0 or <0
  if(str[0]=='-'){
    bigz_create_from_value(self,hex_char_to_int(str[1]));
    self->positive=false;
    i=2;
  } else {
    bigz_create_from_value(self,hex_char_to_int(str[0]));  
  }

  struct bign tmp_big;
  //using the algorithm to transform a str to an int
  while(str[i]!='\0'){
    bign_create_from_value(&tmp_big,hex_char_to_int(str[i]));
    bign_mul_short(&self->n,&self->n,base);                     //multiply the number by base
    bign_add(&self->n,&self->n,&tmp_big);                       //add the next digit

    bign_destroy(&tmp_big);

    i++;
  }

}

void bigz_copy_from_other(struct bigz *self, const struct bigz *other) {
  bigz_destroy(self);
  //assigning the values of other to self
  self->n.capacity=other->n.capacity;
  self->n.size=other->n.size;
  self->positive=other->positive;

  //copying every digit to self
  self->n.data=calloc(self->n.capacity, sizeof(uint32_t));
  for (size_t i = 0; i < self->n.size; i++)
  {
    self->n.data[i]=other->n.data[i];
  }
  

}

void bigz_move_from_other(struct bigz *self, struct bigz *other) {
  bigz_destroy(self);
  //assigning the values of other to self
  self->n.capacity=other->n.capacity;
  self->n.size=other->n.size;
  self->positive=other->positive;

  //self->data points the same array as other->data
  self->n.data=other->n.data;
  //other points to NULL to make other destroyable
  other->n.data=NULL;
  bigz_destroy(other);

}

void bigz_destroy(struct bigz *self) {
  bign_destroy(&self->n);
  self->positive=true;

}

void bigz_print(const struct bigz *self) {
  if(!self->positive){
    printf("-");
  }
  bign_print(&self->n);
}

int bigz_cmp(const struct bigz *lhs, const struct bigz *rhs) {
  if(bigz_cmp_zero(lhs)==0 && bigz_cmp_zero(rhs)==0){
    return 0;
  }

  if(lhs->positive && !rhs->positive){
    return 1;
  }
  if(!lhs->positive && rhs->positive){
    return -1;
  }
  if(!lhs->positive && !rhs->positive){
    return -bign_cmp(&lhs->n, &rhs->n);
  }
  return bign_cmp(&lhs->n, &rhs->n);

}

int bigz_cmp_zero(const struct bigz *self) {
  if(self->n.size==1 && self->n.data[0]==0){
    return 0;
  }
  if(!self->positive){
    return -1;
  }
  return 1;
}

void bigz_add(struct bigz *self, const struct bigz *lhs, const struct bigz *rhs) {
  if(self->n.data==NULL){
    bigz_create_from_value(self, 0);
  }

  // if same sign
  if(lhs->positive==rhs->positive){
    self->positive=lhs->positive;
    bign_add(&self->n,&lhs->n,&rhs->n);

  // if rhs <0
  } else if(lhs->positive && !rhs->positive){
    //if lhs value greater than rhs value
    if(bign_cmp(&lhs->n,&rhs->n)>=0){
      self->positive=true;
      bign_sub(&self->n, &lhs->n, &rhs->n);
    //if rhs value greater than lhs value
    } else {
      self->positive=false;
      bign_sub (&self->n, &rhs->n, &lhs->n);

    }

  //if lhs<0
  }else {
    //if lhs value greater than rhs value
    if(bign_cmp(&lhs->n,&rhs->n)>=0){
      self->positive=false;
      bign_sub(&self->n, &lhs->n, &rhs->n);
    //if rhs value greater than lhs value
    } else {
      self->positive=true;
      bign_sub (&self->n, &rhs->n, &lhs->n);

    }
  }


}

void bigz_sub(struct bigz *self, const struct bigz *lhs, const struct bigz *rhs) {
  if(self->n.data==NULL){
    bigz_create_from_value(self, 0);
  }
 
  //lhs=>0 && rhs<0 
  if(lhs->positive && !rhs->positive){
    self->positive=true;
    bign_add(&self->n, &lhs->n, &rhs->n);

  //lhs<0 && rhs>=0  
  } else if(!lhs->positive && rhs->positive){
    self->positive=false;
    bign_add(&self->n, &lhs->n, &rhs->n);

  //lhs>=0 && rhs>=0  
  } else if(lhs->positive && rhs->positive){
    if(bign_cmp(&lhs->n,&rhs->n)>=0){
      self->positive=true;
      bign_sub(&self->n, &lhs->n, &rhs->n);
    } else {
      self->positive=false;
      bign_sub(&self->n, &rhs->n, &lhs->n);
    }
  //lhs<0 && rhs<0
  } else {
    if(bign_cmp(&lhs->n,&rhs->n)>=0){
      self->positive=false;
      bign_sub(&self->n, &lhs->n, &rhs->n);
    } else {
      self->positive=true;
      bign_sub(&self->n, &rhs->n, &lhs->n);
    }

  }



}

void bigz_mul(struct bigz *self, const struct bigz *lhs, const struct bigz *rhs) {
  if(self->n.data==NULL){
    bigz_create_from_value(self, 0);
  }
 
  bign_mul(&self->n, &lhs->n, &rhs->n);
  //case when same sign
  if(lhs->positive==rhs->positive){
    self->positive=true;
  //case when different signs
  } else {
    self->positive=false;
  }


}

void bigz_div(struct bigz *quo, struct bigz *rem, const struct bigz *lhs, const struct bigz *rhs) {
}

void bigz_gcd(struct bigz *self, const struct bigz *lhs, const struct bigz *rhs) {
}