//
// LiDIA - a library for computational number theory
//   Copyright (c) 1996 by the LiDIA Group
//
// File        : bigint.c (implementation of the cln interface)
// Author      : Thomas Papanikolaou (TP), Bruno Haible (HB)
// Last change : HB, 1996-11-17, initial version
//               HB, 1996-11-20, introduce BITOPS_ASSUME_ABS, off by default.
//               HB, 1996-11-22, call functions cl_I_to_long() etc. just
//                               introduced in CLN.
//

#include <LiDIA/bigint.h>
#include <cl_dfloat.h>
#include <cl_random.h>
#include <cl_malloc.h>
#include <cl_abort.h>
#include <stdio.h>

#include "cl_print.h"
#include "cl_spushstring.h"
#undef swap
#undef bit

/*
 * It is not clear to me whether bit operations assume a sign/magnitude
 * representation (the doc seems to indicate this) or a two's complement
 * representation (Thomas Papanikolaou says so). HB
 */
/* #define BITOPS_ASSUME_ABS */

/**
** constructors and destructor; we could leave out some of these
**/

bigint::bigint()
: I () {}

bigint::bigint(int i)
: I ((long)i) {}

bigint::bigint(long l)
: I (l) {}

bigint::bigint(unsigned long ul)
: I (ul) {}

bigint::bigint(double d)
: I (round1((cl_DF)d)) {}

bigint::bigint(const bigint & a)
: I (a.I) {}

bigint::~bigint()
{}

/**
** inline member functions
**/

int bigint::bit(unsigned int i) const
{
#ifdef BITOPS_ASSUME_ABS
  if (minusp(I))
    return (int)logbitp(i,-I);
  else
#endif
    return (int)logbitp(i,I);
}

int bigint::length() const
{
#ifdef BITOPS_ASSUME_ABS
  if (minusp(I))
    return (integer_length(-I)+intDsize-1)/intDsize;
  else
#endif
    return (integer_length(I)+intDsize-1)/intDsize;
}

int bigint::bit_length() const
{
#ifdef BITOPS_ASSUME_ABS
  if (minusp(I))
    return integer_length(-I);
  else
#endif
    return integer_length(I);
}

int bigint::sign() const
{
  if (minusp(I))
    return -1;
  else if (zerop(I))
    return 0;
  else
    return 1;
}

int bigint::is_positive() const
{ if (!minusp(I))
    if (!zerop(I));
      return 1;
  return 0;
}

int bigint::is_negative() const
{ return (int)minusp(I); }

int bigint::is_even() const
{ return (int)evenp(I); }

int bigint::is_odd() const
{ return (int)oddp(I); }

int bigint::is_zero() const
{ return (int)zerop(I); }

int bigint::is_gt_zero() const
{ if (!minusp(I))
    if (!zerop(I));
      return 1;
  return 0;
}

int bigint::is_ge_zero() const
{ return (int)!minusp(I); }

int bigint::is_lt_zero() const
{ return (int)minusp(I); }

int bigint::is_le_zero() const
{ if (!minusp(I))
    if (!zerop(I));
      return 0;
  return 1;
}

int bigint::is_one() const
{ return (int)(I == 1); }

int bigint::intify(int & i) const
{
  if (integer_length(I) >= int_bitsize)
    return 1;
  i = cl_I_to_L(I);
  return 0;
}

int bigint::longify(long & i) const
{
  if (integer_length(I) >= long_bitsize)
    return 1;
  i = cl_I_to_long(I);
  return 0;
}

int bigint::abs_compare(const bigint & a) const
{
  return (int)cl_compare(abs(I),abs(a.I));
}

int bigint::compare(const bigint & a) const
{
  return (int)cl_compare(I,a.I);
}

unsigned long bigint::most_significant_digit() const
{
  if (zerop(I)) return 0;
  cl_I aI = abs(I);
  return cl_I_to_UL(ldb(aI,cl_byte(intDsize,((integer_length(aI)-1)/intDsize)*intDsize)));
}

unsigned long bigint::least_significant_digit() const
{
  cl_I aI = abs(I);
  return cl_I_to_UL(ldb(aI,cl_byte(intDsize,0)));
}

const double bigint::radix()
{ return ldexp(1.0,intDsize); }

const int bigint::bits_per_digit()
{ return intDsize; }

void bigint::absolute_value()
{ if (minusp(I)) { I = -I; } }

void bigint::negate()
{ I = -I; }

void bigint::assign_zero()
{ I = 0; }

void bigint::assign_one()
{ I = 1; }

void bigint::assign(int i)
{ I = (long)i; }

void bigint::assign(long i)
{ I = i; }

void bigint::assign(unsigned long ui)
{ I = ui; }

void bigint::assign(const bigint & a)
{ I = a.I; }

void bigint::multiply_by_2()
{ I = ash(I,1); }

void bigint::divide_by_2()
{ I = ash(I,-1); }

/**
** Type checking
**/

int is_char(const bigint & a)
{ if (integer_length(a.I) < char_bitsize)
    return 1;
  return 0;
}

int is_uchar(const bigint & a)
{ if (!minusp(a.I))
    if (integer_length(a.I) <= char_bitsize)
      return 1;
  return 0;
}

int is_short(const bigint & a)
{ if (integer_length(a.I) < short_bitsize)
    return 1;
  return 0;
}

int is_ushort(const bigint & a)
{ if (!minusp(a.I))
    if (integer_length(a.I) <= short_bitsize)
      return 1;
  return 0;
}

int is_int(const bigint & a)
{ if (integer_length(a.I) < int_bitsize)
    return 1;
  return 0;
}

int is_uint(const bigint & a)
{ if (!minusp(a.I))
    if (integer_length(a.I) <= int_bitsize)
      return 1;
  return 0;
}

int is_long(const bigint & a)
{ if (integer_length(a.I) < long_bitsize)
    return 1;
  return 0;
}

int is_ulong(const bigint & a)
{ if (!minusp(a.I))
    if (integer_length(a.I) <= long_bitsize)
      return 1;
  return 0;
}

/**
** assignments
**/


int bigint::operator = (int i)
{ I = (long)i; return i; }

long bigint::operator = (long l)
{ I = l; return l; }

unsigned long bigint::operator = (unsigned long ul)
{ I = ul; return ul; }

double bigint::operator = (double d)
{ I = round1((cl_DF)d); return d; }

bigint & bigint::operator = (const bigint & a)
{ I = a.I; return *this; }

/**
** comparisons
**/

int operator == (const bigint & a, const bigint & b)
{ return (int)(a.I == b.I); }

int operator != (const bigint & a, const bigint & b)
{ return (int)(a.I != b.I); }

int operator > (const bigint & a, const bigint & b)
{ return (int)(a.I > b.I); }

int operator >= (const bigint & a, const bigint & b)
{ return (int)(a.I >= b.I); }

int operator < (const bigint & a, const bigint & b)
{ return (int)(a.I < b.I); }

int operator <= (const bigint & a, const bigint & b)
{ return (int)(a.I <= b.I); }

/**
** operator overloading
**/

bigint operator - (const bigint & a)
{ return bigint(-a.I); }

bigint operator + (const bigint & a, const bigint & b)
{ return bigint(a.I + b.I); }

bigint operator - (const bigint & a, const bigint & b)
{ return bigint(a.I - b.I); }

bigint operator * (const bigint & a, const bigint & b)
{ return bigint(a.I * b.I); }

bigint operator / (const bigint & a, const bigint & b)
{ return bigint(truncate1(a.I,b.I)); }

bigint operator % (const bigint & a, const bigint & b)
{ return bigint(rem(a.I,b.I)); }

bigint operator << (const bigint & a, long ui)
{
  if (ui < 0)
    lidia_error_handler("bigint", "operator<<::index is negative.");
  return bigint(ash(a.I,(cl_I)ui));
}

bigint operator >> (const bigint & a, long ui)
{
  if (ui < 0)
    lidia_error_handler("bigint", "operator>>::index is negative.");
  return bigint(ash(a.I,-(cl_I)ui));
}

bigint operator & (const bigint & a, const bigint & b)
{ return bigint(logand(a.I,b.I)); }

bigint operator | (const bigint & a, const bigint & b)
{ return bigint(logior(a.I,b.I)); }

bigint operator ^ (const bigint & a, const bigint & b)
{ return bigint(logxor(a.I,b.I)); }

bigint & bigint::operator += (const bigint & a)
{ I = I + a.I; return *this; }

bigint & bigint::operator -= (const bigint & a)
{ I = I - a.I; return *this; }

bigint & bigint::operator *= (const bigint & a)
{ I = I * a.I; return *this; }

bigint & bigint::operator /= (const bigint & a)
{ I = truncate1(I,a.I); return *this; }

bigint & bigint::operator %= (const bigint & a)
{ I = rem(I,a.I); return *this; }

bigint & bigint::operator <<= (long ui)
{
  if (ui < 0)
    lidia_error_handler("bigint", "operator<<=::index is negative.");
  I = ash(I,(cl_I)ui);
  return *this;
}

bigint & bigint::operator >>= (long ui)
{
  if (ui < 0)
    lidia_error_handler("bigint", "operator>>=::index is negative.");
  I = ash(I,-(cl_I)ui);
  return *this;
}

bigint & bigint::operator &= (const bigint & a)
{ I = logand(I,a.I); return *this; }

bigint & bigint::operator |= (const bigint & a)
{ I = logior(I,a.I); return *this; }

bigint & bigint::operator ^= (const bigint & a)
{ I = logxor(I,a.I); return *this; }

bigint & bigint::operator++ ()
{ I = plus1(I); return *this; }

bigint & bigint::operator-- ()
{ I = minus1(I); return *this; }

void bigint::operator++ (int)
{ I = plus1(I); }

void bigint::operator-- (int)
{ I = minus1(I); }

int bigint::operator ! () const
{ return (int)zerop(I); }

bigint bigint::operator ~ () const
{ return bigint(lognot(I)); }

/**
** Procedural versions
**/

void negate(bigint & a, const bigint & b)
{ a.I = -b.I; }

void add(bigint & c, const bigint & a, const bigint & b)
{ c.I = a.I + b.I; }

void subtract(bigint & c, const bigint & a, const bigint & b)
{ c.I = a.I - b.I; }

void multiply(bigint & c, const bigint & a, const bigint & b)
{ c.I = a.I * b.I; }

void divide(bigint & c, const bigint & a, const bigint & b)
{ c.I = truncate1(a.I,b.I); }

void remainder(bigint & c, const bigint & a, const bigint & b)
{ c.I = rem(a.I,b.I); }

void div_rem(bigint & q, bigint & r, const bigint & a, const bigint & b)
{
  cl_I_div_t q_r = truncate2(a.I,b.I);
  q.I = q_r.quotient;
  r.I = q_r.remainder;
}

void invert(bigint & a, const bigint & b)
{
  if ((b.I == 1) || (b.I == -1))
    a.I = b.I;
  else
    lidia_error_handler("bigint", "invert::inverting of a non-unit.");
}

void shift_left(bigint & c, const bigint & a, long ui)
{
  if (ui < 0)
    lidia_error_handler("bigint", "shift_left()::index is negative.");
  c.I = ash(a.I,(cl_I)ui);
}

void shift_right(bigint & c, const bigint & a, long ui)
{
  if (ui < 0)
    lidia_error_handler("bigint", "shift_right()::index is negative.");
  c.I = ash(a.I,-(cl_I)ui);
}

void power(bigint & c, const bigint & a, const bigint & b)
{
  if (b.is_zero() || a.is_one())
    c.assign_one();
  else if (b.is_negative())
    c.assign_zero();
  else
    c.I = expt_pos(a.I,b.I);
}

void power(bigint & c, const bigint & a, long i)
{
  if (i == 0 || a.is_one())
    c.assign_one();
  else if (i < 0)
    c.assign_zero();
  else
    c.I = expt_pos(a.I,(cl_I)i);
}

void and(bigint & c, const bigint & a, const bigint & b)
{ c.I = logand(a.I,b.I); }

void or(bigint & c, const bigint & a, const bigint & b)
{ c.I = logior(a.I,b.I); }

void xor(bigint & c, const bigint & a, const bigint & b)
{ c.I = logxor(a.I,b.I); }

void not(bigint & b, const bigint & a)
{ b.I = lognot(a.I); }

void inc(bigint & c)
{ c.I = plus1(c.I); }

void dec(bigint & c)
{ c.I = minus1(c.I); }

void add(bigint & c, const bigint & a, long i)
{ c.I = a.I + i; }

void subtract(bigint & c, const bigint & a, long i)
{ c.I = a.I - i; }

void multiply(bigint & c, const bigint & a, long i)
{ c.I = a.I * i; }

void divide(bigint & c, const bigint & a, long i)
{ c.I = truncate1(a.I,i); }

void remainder(long &r, const bigint & a, long i)
{
  r = cl_I_to_long(rem(a.I,i));
}

long remainder(const bigint & a, long i)
{
  return cl_I_to_long(rem(a.I,i));
}

void div_rem(bigint & q, long &r, const bigint & a, long i)
{
  cl_I_div_t q_r = truncate2(a.I,i);
  q.I = q_r.quotient;
  r = cl_I_to_long(q_r.remainder);
}

/**
** gcd's
**/

bigint gcd(const bigint & a, const bigint & b)
{ return bigint(gcd(a.I,b.I)); }

bigint bgcd(const bigint & a, const bigint & b)
{ return bigint(gcd(a.I,b.I)); }

bigint dgcd(const bigint & a, const bigint & b)
{ return bigint(gcd(a.I,b.I)); }

bigint xgcd(bigint & u, bigint & v, const bigint & a, const bigint & b)
{ return bigint(xgcd(a.I,b.I,&u.I,&v.I)); }

bigint xgcd_left(bigint & u, const bigint & a, const bigint & b)
{ cl_I v; return bigint(xgcd(a.I,b.I,&u.I,&v)); }

bigint xgcd_right(bigint & v, const bigint & a, const bigint & b)
{ cl_I u; return bigint(xgcd(a.I,b.I,&u,&v.I)); }

/**
** functions
**/

bigint abs(const bigint & a)
{ return bigint(abs(a.I)); }

void seed(const bigint & a)
{
  cl_default_random_state.seed.lo = cl_I_to_UL(ldb(a.I,cl_byte(32,0)));
  cl_default_random_state.seed.hi = cl_I_to_UL(ldb(a.I,cl_byte(32,32)));
}

bigint randomize(const bigint & a)
{
  if (minusp(a.I))
    return bigint(-random_I(-a.I));
  else
    return bigint(random_I(a.I));
}

double dbl(const bigint & a)
{ return cl_double_approx(a.I); }

void sqrt(bigint & a, const bigint & b)
{ a.I = isqrt(b.I); }

void square(bigint & a, const bigint & b)
{ a.I = square(b.I); }

void swap(bigint & a, bigint & b)
{
  void* tmp = a.I.pointer;
  a.I.pointer = b.I.pointer;
  b.I.pointer = tmp;
}

/**
** input / output
**/

istream & operator >> (istream & in, bigint & a)
{
#ifdef __GNUG__
                if (!in.ipfx0())
#else
                if (!in.ipfx(0))
#endif
                  return in;

                char s[10000];
                int ndigits = 0;

                char* p = s;
                int c;
                *p = '\0';
                do {
                  c = in.get();
                  if (c == EOF)
                  {
                    in.setf(ios::failbit|ios::eofbit);
                    return in;
                  }
                  if ((c == '+') || (c == '-')) { *p++ = c; }
                } while (isspace(c) || (c == '+') || (c == '-'));

                if (!isdigit(c)) { cerr << "digit expected" << flush; }
                while (isdigit(c)) {
                  ndigits++;
                  *p++ = c;
                  c = in.get();
                  if (c == EOF)
                  {
                    *p = '\0';
                    string_to_bigint(s, a);
                    return in;
                  }

                }
                if (ndigits == 0)
                  {
                    in.setf(ios::failbit);
                    return in;
                  }

                *p = '\0';
                string_to_bigint(s, a);
                // if (c != '\n' && c != '\r')
                  in.putback(c);
                return in;
}

ostream & operator << (ostream & out, const bigint & a)
{ out << a.I; return out; }

int string_to_bigint(char *s, bigint & a)
{ a.I = (cl_I)s; }

int bigint_to_string(const bigint & a, char *s)
{
  char* r = cl_decimal_string(a.I);
  strcpy(s,r);
  cl_free_hook(r);
  return strlen(s);
}

/**
** using fread/fwrite
**/

void bigint::read_from_file(FILE * fp)
{
  scan_from_file(fp);
  int c = getc(fp); if (c != EOF && c != '\n') { ungetc(c,fp); }
}

void bigint::write_to_file(FILE * fp)
{
  print_to_file(fp);
  putc('\n',fp);
}

/**
** using fscanf/fprintf
**/

void bigint::scan_from_file(FILE * fp)
{
  cl_spushstring buffer;
  int c;
  while ((c = getc(fp)) != EOF) {
    switch (c)
      { case '0': case '1': case '2': case '3': case '4':
        case '5': case '6': case '7': case '8': case '9':
        case '+': case '-':
          buffer.push((char)c); break;
        default:
          ungetc(c,fp); goto end;
      }
  }
end:
  char* s = buffer.contents();
  I = (cl_I)s;
  cl_free_hook(s);
}

void bigint::print_to_file(FILE * fp)
{
  char* s = cl_decimal_string(I);
  fprintf(fp,"%s",s);
  cl_free_hook(s);
}

