-rw-r--r-- 17135 cryptattacktester-20230614/bigint_mpz.cpp raw
#include <iostream>
#include <cassert>
#include <string>
#include <map>
#include "bigint_mpz.h"

#define BIT_LIMIT 1073741824

using namespace std;

mpz_ptr bigint::unsafe_get_mpz_t(void)
{
  return x;
}

bool bigint::bit(bigint e)
{
  if (e < 0) return 0;
  assert(e < BIT_LIMIT); // XXX
  return mpz_tstbit(x,e);
}

bigint::operator bool() const { return mpz_sgn(x) != 0; }

bigint::operator int() const { assert(mpz_fits_sint_p(x)); return mpz_get_si(x); }
bigint::operator long() const { assert(mpz_fits_slong_p(x)); return mpz_get_si(x); }
bigint::operator unsigned int() const { assert(mpz_fits_uint_p(x)); return mpz_get_ui(x); }
bigint::operator unsigned long() const { assert(mpz_fits_ulong_p(x)); return mpz_get_ui(x); }

bigint::operator unsigned long long() const
{
  assert(mpz_sgn(x) >= 0);
  assert(mpz_sizeinbase(x,256) <= sizeof(long long));

  unsigned char r[sizeof(long long)];
  for (long long i = 0;i < sizeof r;++i) r[i] = 0;
  mpz_export(r,0,-1,1,0,0,x);
  unsigned long long result = 0;
  for (long long i = (sizeof r)-1;i >= 0;--i)
    result = result*256+r[i];
  return result;
}

bigint::operator long long() const
{
  mpz_t top;
  mpz_t bot;
  mpz_init_set_ui(top,1);
  mpz_init_set_si(bot,-1);
  mpz_mul_2exp(top,top,8*sizeof(long long)-1);
  mpz_mul_2exp(bot,bot,8*sizeof(long long)-1);
  assert(mpz_cmp(x,top) <= 0);
  assert(mpz_cmp(x,bot) >= 0);
  mpz_clear(top);
  mpz_clear(bot);

  unsigned char r[sizeof(long long)];
  for (long long i = 0;i < sizeof r;++i) r[i] = 0;
  mpz_export(r,0,-1,1,0,0,x);
  unsigned long long result = 0;
  for (long long i = (sizeof r)-1;i >= 0;--i)
    result = result*256+r[i];
  if (mpz_sgn(x) < 0) result = -result;
  return result;
}

bigint& operator+=(bigint &a,const bigint &b)
{
  mpz_add(a.x,a.x,b.x);
  return a;
}

bigint& operator+=(bigint &a,int b) { return a += bigint(b); }

bigint operator-(const bigint &a)
{
  bigint result;
  mpz_neg(result.x,a.x);
  return result;
}

bigint& operator-=(bigint &a,const bigint &b)
{
  mpz_sub(a.x,a.x,b.x);
  return a;
}

bigint& operator*=(bigint &a,const bigint &b)
{
  mpz_mul(a.x,a.x,b.x);
  return a;
}

bigint& operator/=(bigint &a,const bigint &b)
{
  mpz_fdiv_q(a.x,a.x,b.x);
  return a;
}

bigint& operator%=(bigint &a,const bigint &b)
{
  mpz_fdiv_r(a.x,a.x,b.x);
  return a;
}

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

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

bool operator==(const bigint &a,const bigint &b) { return mpz_cmp(a.x,b.x) == 0; }
bool operator==(const bigint &a,int b) { return mpz_cmp_si(a.x,b) == 0; }
bool operator==(const bigint &a,long b) { return mpz_cmp_si(a.x,b) == 0; }
bool operator==(const bigint &a,long long b) { return a == bigint(b); }
bool operator==(const bigint &a,unsigned int b) { return mpz_cmp_ui(a.x,b) == 0; }
bool operator==(const bigint &a,unsigned long b) { return mpz_cmp_ui(a.x,b) == 0; }
bool operator==(const bigint &a,unsigned long long b) { return a == bigint(b); }
bool operator==(int b,const bigint &a) { return mpz_cmp_si(a.x,b) == 0; }
bool operator==(long b,const bigint &a) { return mpz_cmp_si(a.x,b) == 0; }
bool operator==(long long b,const bigint &a) { return a == bigint(b); }
bool operator==(unsigned int b,const bigint &a) { return mpz_cmp_ui(a.x,b) == 0; }
bool operator==(unsigned long b,const bigint &a) { return mpz_cmp_ui(a.x,b) == 0; }
bool operator==(unsigned long long b,const bigint &a) { return a == bigint(b); }

bool operator!=(const bigint &a,const bigint &b) { return mpz_cmp(a.x,b.x) != 0; }
bool operator!=(const bigint &a,int b) { return mpz_cmp_si(a.x,b) != 0; }
bool operator!=(const bigint &a,long b) { return mpz_cmp_si(a.x,b) != 0; }
bool operator!=(const bigint &a,long long b) { return a != bigint(b); }
bool operator!=(const bigint &a,unsigned int b) { return mpz_cmp_ui(a.x,b) != 0; }
bool operator!=(const bigint &a,unsigned long b) { return mpz_cmp_ui(a.x,b) != 0; }
bool operator!=(const bigint &a,unsigned long long b) { return a != bigint(b); }
bool operator!=(int b,const bigint &a) { return mpz_cmp_si(a.x,b) != 0; }
bool operator!=(long b,const bigint &a) { return mpz_cmp_si(a.x,b) != 0; }
bool operator!=(long long b,const bigint &a) { return a != bigint(b); }
bool operator!=(unsigned int b,const bigint &a) { return mpz_cmp_ui(a.x,b) != 0; }
bool operator!=(unsigned long b,const bigint &a) { return mpz_cmp_ui(a.x,b) != 0; }
bool operator!=(unsigned long long b,const bigint &a) { return a != bigint(b); }

bool operator<(const bigint &a,const bigint &b) { return mpz_cmp(a.x,b.x) < 0; }
bool operator<(const bigint &a,int b) { return mpz_cmp_si(a.x,b) < 0; }
bool operator<(const bigint &a,long b) { return mpz_cmp_si(a.x,b) < 0; }
bool operator<(const bigint &a,long long b) { return a < bigint(b); }
bool operator<(const bigint &a,unsigned int b) { return mpz_cmp_ui(a.x,b) < 0; }
bool operator<(const bigint &a,unsigned long b) { return mpz_cmp_ui(a.x,b) < 0; }
bool operator<(const bigint &a,unsigned long long b) { return a < bigint(b); }
bool operator<(int b,const bigint &a) { return a > b; }
bool operator<(long b,const bigint &a) { return a > b; }
bool operator<(long long b,const bigint &a) { return a > b; }
bool operator<(unsigned int b,const bigint &a) { return a > b; }
bool operator<(unsigned long b,const bigint &a) { return a > b; }
bool operator<(unsigned long long b,const bigint &a) { return a > b; }

bool operator<=(const bigint &a,const bigint &b) { return mpz_cmp(a.x,b.x) <= 0; }
bool operator<=(const bigint &a,int b) { return mpz_cmp_si(a.x,b) <= 0; }
bool operator<=(const bigint &a,long b) { return mpz_cmp_si(a.x,b) <= 0; }
bool operator<=(const bigint &a,long long b) { return a <= bigint(b); }
bool operator<=(const bigint &a,unsigned int b) { return mpz_cmp_ui(a.x,b) <= 0; }
bool operator<=(const bigint &a,unsigned long b) { return mpz_cmp_ui(a.x,b) <= 0; }
bool operator<=(const bigint &a,unsigned long long b) { return a <= bigint(b); }
bool operator<=(int b,const bigint &a) { return a >= b; }
bool operator<=(long b,const bigint &a) { return a >= b; }
bool operator<=(long long b,const bigint &a) { return a >= b; }
bool operator<=(unsigned int b,const bigint &a) { return a >= b; }
bool operator<=(unsigned long b,const bigint &a) { return a >= b; }
bool operator<=(unsigned long long b,const bigint &a) { return a >= b; }

bool operator>(const bigint &a,const bigint &b) { return mpz_cmp(a.x,b.x) > 0; }
bool operator>(const bigint &a,int b) { return mpz_cmp_si(a.x,b) > 0; }
bool operator>(const bigint &a,long b) { return mpz_cmp_si(a.x,b) > 0; }
bool operator>(const bigint &a,long long b) { return a > bigint(b); }
bool operator>(const bigint &a,unsigned int b) { return mpz_cmp_ui(a.x,b) > 0; }
bool operator>(const bigint &a,unsigned long b) { return mpz_cmp_ui(a.x,b) > 0; }
bool operator>(const bigint &a,unsigned long long b) { return a > bigint(b); }
bool operator>(int b,const bigint &a) { return a < b; }
bool operator>(long b,const bigint &a) { return a < b; }
bool operator>(long long b,const bigint &a) { return a < b; }
bool operator>(unsigned int b,const bigint &a) { return a < b; }
bool operator>(unsigned long b,const bigint &a) { return a < b; }
bool operator>(unsigned long long b,const bigint &a) { return a < b; }

bool operator>=(const bigint &a,const bigint &b) { return mpz_cmp(a.x,b.x) >= 0; }
bool operator>=(const bigint &a,int b) { return mpz_cmp_si(a.x,b) >= 0; }
bool operator>=(const bigint &a,long b) { return mpz_cmp_si(a.x,b) >= 0; }
bool operator>=(const bigint &a,long long b) { return a >= bigint(b); }
bool operator>=(const bigint &a,unsigned int b) { return mpz_cmp_ui(a.x,b) >= 0; }
bool operator>=(const bigint &a,unsigned long b) { return mpz_cmp_ui(a.x,b) >= 0; }
bool operator>=(const bigint &a,unsigned long long b) { return a >= bigint(b); }
bool operator>=(int b,const bigint &a) { return a <= b; }
bool operator>=(long b,const bigint &a) { return a <= b; }
bool operator>=(long long b,const bigint &a) { return a <= b; }
bool operator>=(unsigned int b,const bigint &a) { return a <= b; }
bool operator>=(unsigned long b,const bigint &a) { return a <= b; }
bool operator>=(unsigned long long b,const bigint &a) { return a <= b; }

bigint operator&(const bigint &a,const bigint &b)
{
  bigint result;
  mpz_and(result.x,a.x,b.x);
  return result;
}

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

bigint operator+(const bigint &a,const bigint &b) { bigint result; mpz_add(result.x,a.x,b.x); return result; }
bigint operator+(const bigint &a,int b) { return a+bigint(b); }
bigint operator+(const bigint &a,unsigned int b) { bigint result; mpz_add_ui(result.x,a.x,b); return result; }
bigint operator+(const bigint &a,long b) { return a+bigint(b); }
bigint operator+(const bigint &a,unsigned long b) { bigint result; mpz_add_ui(result.x,a.x,b); return result; }
bigint operator+(const bigint &a,long long b) { return a+bigint(b); }
bigint operator+(const bigint &a,unsigned long long b) { return a+bigint(b); }
bigint operator+(int b,const bigint &a) { return a+bigint(b); }
bigint operator+(unsigned int b,const bigint &a) { bigint result; mpz_add_ui(result.x,a.x,b); return result; }
bigint operator+(long b,const bigint &a) { return a+bigint(b); }
bigint operator+(unsigned long b,const bigint &a) { bigint result; mpz_add_ui(result.x,a.x,b); return result; }
bigint operator+(long long b,const bigint &a) { return a+bigint(b); }
bigint operator+(unsigned long long b,const bigint &a) { return a+bigint(b); }

bigint operator*(const bigint &a,const bigint &b) { bigint result; mpz_mul(result.x,a.x,b.x); return result; }
bigint operator*(const bigint &a,int b) { return a*bigint(b); }
bigint operator*(const bigint &a,unsigned int b) { bigint result; mpz_mul_ui(result.x,a.x,b); return result; }
bigint operator*(const bigint &a,long b) { return a*bigint(b); }
bigint operator*(const bigint &a,unsigned long b) { bigint result; mpz_mul_ui(result.x,a.x,b); return result; }
bigint operator*(const bigint &a,long long b) { return a*bigint(b); }
bigint operator*(const bigint &a,unsigned long long b) { return a*bigint(b); }
bigint operator*(int b,const bigint &a) { return a*bigint(b); }
bigint operator*(unsigned int b,const bigint &a) { bigint result; mpz_mul_ui(result.x,a.x,b); return result; }
bigint operator*(long b,const bigint &a) { return a*bigint(b); }
bigint operator*(unsigned long b,const bigint &a) { bigint result; mpz_mul_ui(result.x,a.x,b); return result; }
bigint operator*(long long b,const bigint &a) { return a*bigint(b); }
bigint operator*(unsigned long long b,const bigint &a) { return a*bigint(b); }

bigint operator-(const bigint &a,const bigint &b) { bigint result; mpz_sub(result.x,a.x,b.x); return result; }
bigint operator-(const bigint &a,int b) { return a-bigint(b); }
bigint operator-(const bigint &a,unsigned int b) { bigint result; mpz_sub_ui(result.x,a.x,b); return result; }
bigint operator-(const bigint &a,long b) { return a-bigint(b); }
bigint operator-(const bigint &a,unsigned long b) { bigint result; mpz_sub_ui(result.x,a.x,b); return result; }
bigint operator-(const bigint &a,long long b) { return a-bigint(b); }
bigint operator-(const bigint &a,unsigned long long b) { return a-bigint(b); }
bigint operator-(int b,const bigint &a) { return bigint(b)-a; }
bigint operator-(unsigned int b,const bigint &a) { return bigint(b)-a; }
bigint operator-(long b,const bigint &a) { return bigint(b)-a; }
bigint operator-(unsigned long b,const bigint &a) { return bigint(b)-a; }
bigint operator-(long long b,const bigint &a) { return bigint(b)-a; }
bigint operator-(unsigned long long b,const bigint &a) { return bigint(b)-a; }

bigint operator/(const bigint &a,const bigint &b) { bigint result; mpz_fdiv_q(result.x,a.x,b.x); return result; }
bigint operator/(const bigint &a,int b) { return a/bigint(b); }
bigint operator/(const bigint &a,unsigned int b) { return a/bigint(b); }
bigint operator/(const bigint &a,long b) { return a/bigint(b); }
bigint operator/(const bigint &a,unsigned long b) { return a/bigint(b); }
bigint operator/(const bigint &a,long long b) { return a/bigint(b); }
bigint operator/(const bigint &a,unsigned long long b) { return a/bigint(b); }
bigint operator/(int b,const bigint &a) { return bigint(b)/a; }
bigint operator/(unsigned int b,const bigint &a) { return bigint(b)/a; }
bigint operator/(long b,const bigint &a) { return bigint(b)/a; }
bigint operator/(unsigned long b,const bigint &a) { return bigint(b)/a; }
bigint operator/(long long b,const bigint &a) { return bigint(b)/a; }
bigint operator/(unsigned long long b,const bigint &a) { return bigint(b)/a; }

bigint operator%(const bigint &a,const bigint &b) { bigint result; mpz_fdiv_r(result.x,a.x,b.x); return result; }
bigint operator%(const bigint &a,int b) { return a%bigint(b); }
bigint operator%(const bigint &a,unsigned int b) { return a%bigint(b); }
bigint operator%(const bigint &a,long b) { return a%bigint(b); }
bigint operator%(const bigint &a,unsigned long b) { return a%bigint(b); }
bigint operator%(const bigint &a,long long b) { return a%bigint(b); }
bigint operator%(const bigint &a,unsigned long long b) { return a%bigint(b); }
bigint operator%(int b,const bigint &a) { return bigint(b)%a; }
bigint operator%(unsigned int b,const bigint &a) { return bigint(b)%a; }
bigint operator%(long b,const bigint &a) { return bigint(b)%a; }
bigint operator%(unsigned long b,const bigint &a) { return bigint(b)%a; }
bigint operator%(long long b,const bigint &a) { return bigint(b)%a; }
bigint operator%(unsigned long long b,const bigint &a) { return bigint(b)%a; }

bigint &operator++(bigint &a)
{
  mpz_add_ui(a.x,a.x,1);
  return a;
}

bigint operator++(bigint &a,int)
{
  bigint result = a;
  mpz_add_ui(a.x,a.x,1);
  return result;
}

bigint& operator--(bigint &a)
{
  mpz_sub_ui(a.x,a.x,1);
  return a;
}

bigint operator--(bigint &a,int)
{
  bigint result = a;
  mpz_sub_ui(a.x,a.x,1);
  return result;
}

bigint operator<<(const bigint &a,const bigint &b)
{
  bigint result;
  assert(mpz_fits_slong_p(b.x)); // XXX
  long shiftcount = mpz_get_si(b.x);
  assert(shiftcount >= 0);
  assert(shiftcount <= BIT_LIMIT); // XXX
  mpz_mul_2exp(result.x,a.x,shiftcount);
  return result;
}

bigint operator<<(const bigint &a,int b) { return a<<(bigint) b; }
bigint operator<<(const bigint &a,long b) { return a<<(bigint) b; }
bigint operator<<(const bigint &a,long long b) { return a<<(bigint) b; }
bigint operator<<(const bigint &a,unsigned int b) { return a<<(bigint) b; }
bigint operator<<(const bigint &a,unsigned long b) { return a<<(bigint) b; }
bigint operator<<(const bigint &a,unsigned long long b) { return a<<(bigint) b; }
bigint operator<<(int a,const bigint &b) { return bigint(a)<<b; }
bigint operator<<(long a,const bigint &b) { return bigint(a)<<b; }
bigint operator<<(long long a,const bigint &b) { return bigint(a)<<b; }
bigint operator<<(unsigned int a,const bigint &b) { return bigint(a)<<b; }
bigint operator<<(unsigned long a,const bigint &b) { return bigint(a)<<b; }
bigint operator<<(unsigned long long a,const bigint &b) { return bigint(a)<<b; }

bigint operator>>(const bigint &a,const bigint &b)
{
  bigint bits(mpz_sizeinbase(a.x,2));
  if (b > bits) {
    if (a < 0) return -1;
    return 0;
  }
  bigint result;
  long shiftcount = mpz_get_si(b.x);
  assert(shiftcount >= 0);
  assert(shiftcount <= BIT_LIMIT);
  mpz_fdiv_q_2exp(result.x,a.x,shiftcount);
  return result;
}

bigint operator>>(const bigint &a,int b) { return a>>(bigint) b; }
bigint operator>>(const bigint &a,long b) { return a>>(bigint) b; }
bigint operator>>(const bigint &a,long long b) { return a>>(bigint) b; }
bigint operator>>(const bigint &a,unsigned int b) { return a>>(bigint) b; }
bigint operator>>(const bigint &a,unsigned long b) { return a>>(bigint) b; }
bigint operator>>(const bigint &a,unsigned long long b) { return a>>(bigint) b; }
bigint operator>>(int a,const bigint &b) { return bigint(a)>>b; }
bigint operator>>(long a,const bigint &b) { return bigint(a)>>b; }
bigint operator>>(long long a,const bigint &b) { return bigint(a)>>b; }
bigint operator>>(unsigned int a,const bigint &b) { return bigint(a)>>b; }
bigint operator>>(unsigned long a,const bigint &b) { return bigint(a)>>b; }
bigint operator>>(unsigned long long a,const bigint &b) { return bigint(a)>>b; }

std::string bigint::get_str(void) const
{
  char *s = mpz_get_str(0,10,x);
  assert(s);
  std::string result(s);
  free(s);
  return result;
}

ostream &operator<<(ostream &o,const bigint &a)
{
  return o << a.get_str();
}

static map<pair<bigint,bigint>,bigint> binomial_cache;

bigint binomial(bigint n,bigint k)
{
  if (k < 0) return 0;
  if (k == 0) return 1;
  if (n >= 0) if (k > n) return 0;
  pair<bigint,bigint> nk = make_pair(n,k);
  if (binomial_cache.count(nk))
    return binomial_cache[nk];
  bigint result = binomial(n-1,k-1)*n/k;
  binomial_cache[nk] = result;
  return result;
}

bigint nbits(bigint bits)
{
  if (bits <= 0) return 1;
  bigint result = 0;
  while (bits > 0) {
    ++result;
    bits >>= 1;
  }
  return result;
}

bigint nbits0(bigint bits)
{
  if (bits <= 0) return 0;
  return nbits(bits);
}