integer.cc

Gambit 是一个游戏库理论软件

          ++s;
          a >>= 1;
        }
      }
    }

    if (s != 0) t = lshift(t, -s, t);

    if (t->sgn == I_POSITIVE)
    {
      u = Icopy(u, t);
      t = add(t, 0, v, 1, t);
    }
    else
    {
      v = Ialloc(v, t->s, t->len, !t->sgn, t->len);
      t = add(t, 0, u, 0, t);
    }
  }
  if (!STATIC_IntRep(t)) delete t;
  if (!STATIC_IntRep(v)) delete v;
  if (k != 0) u = lshift(u, k, u);
  return u;
}



long lg(const IntRep* x)
{
  nonnil(x);
  int xl = x->len;
  if (xl == 0)
    return 0;

  long l = (xl - 1) * I_SHIFT - 1;
  unsigned short a = x->s[xl-1];

  while (a != 0)
  {
    a = a >> 1;
    ++l;
  }
  return l;
}
  
IntRep* power(const IntRep* x, long y, IntRep* r)
{
  nonnil(x);
  int sgn;
  if (x->sgn == I_POSITIVE || (!(y & 1)))
    sgn = I_POSITIVE;
  else
    sgn = I_NEGATIVE;

  int xl = x->len;

  if (y == 0 || (xl == 1 && x->s[0] == 1))
    r = Icopy_one(r, sgn);
  else if (xl == 0 || y < 0)
    r = Icopy_zero(r);
  else if (y == 1 || y == -1)
    r = Icopy(r, x);
  else
  {
	 int maxsize = (int) (((lg(x) + 1) * y) / I_SHIFT + 2);     // pre-allocate space
    IntRep* b = Ialloc(0, x->s, xl, I_POSITIVE, maxsize);
    b->len = xl;
    r = Icalloc(r, maxsize);
    r = Icopy_one(r, I_POSITIVE);
    for(;;)
    {
      if (y & 1)
        r = multiply(r, b, r);
      if ((y >>= 1) == 0)
        break;
      else
        b = multiply(b, b, b);
    }
    if (!STATIC_IntRep(b)) delete b;
  }
  r->sgn = sgn;
  Icheck(r);
  return r;
}

IntRep* abs(const IntRep* src, IntRep* dest)
{
  nonnil(src);
  if (src != dest)
    dest = Icopy(dest, src);
  dest->sgn = I_POSITIVE;
  return dest;
}

IntRep* negate(const IntRep* src, IntRep* dest)
{
  nonnil(src);
  if (src != dest)
    dest = Icopy(dest, src);
  if (dest->len != 0) 
    dest->sgn = !dest->sgn;
  return dest;
}

#if defined(__GNUG__) && !defined(NO_NRV)

gInteger sqrt(const gInteger& x)
{
  gInteger r;
  int s = sign(x);
  if (s < 0) x.error("Attempted square root of negative gInteger");
  if (s != 0)
  {
    r >>= (lg(x) / 2); // get close
    gInteger q;
    div(x, r, q);
    while (q < r)
    {
      r += q;
      r >>= 1;
      div(x, r, q);
    }
  }
  return r;
}

gInteger lcm(const gInteger& x, const gInteger& y)
{
  gInteger r;
  if (!x.initialized() || !y.initialized())
    x.error("operation on uninitialized gInteger");
  gInteger g;
  if (sign(x) == 0 || sign(y) == 0)
    g = 1;
  else 
    g = gcd(x, y);
  div(x, g, r);
  mul(r, y, r);
  return r;
}

#else 
gInteger sqrt(const gInteger& x) 
{
  gInteger r(x);
  int s = sign(x);
  if (s < 0) x.error("Attempted square root of negative gInteger");
  if (s != 0)
  {
    r >>= (lg(x) / 2); // get close
    gInteger q;
    div(x, r, q);
    while (q < r)
    {
      r += q;
      r >>= 1;
      div(x, r, q);
    }
  }
  return r;
}

gInteger lcm(const gInteger& x, const gInteger& y) 
{
  gInteger r;
  if (!x.initialized() || !y.initialized())
    x.error("operation on uninitialized gInteger");
  gInteger g;
  if (sign(x) == 0 || sign(y) == 0)
    g = 1;
  else 
    g = gcd(x, y);
  div(x, g, r);
  mul(r, y, r);
  return r;
}

#endif



IntRep* atoIntRep(const char* s, int base)
{
  int sl = strlen(s);
  IntRep* r = Icalloc(0, (int) (sl * (lg(base) + 1) / I_SHIFT + 1));
  if (s != 0)
  {
    char sgn;
    while (isspace(*s)) ++s;
    if (*s == '-')
    {
      sgn = I_NEGATIVE;
      s++;
    }
    else if (*s == '+')
    {
      sgn = I_POSITIVE;
      s++;
    }
    else
      sgn = I_POSITIVE;
    for (;;)
    {
      long digit;
      if (*s >= '0' && *s <= '9') digit = *s - '0';
      else if (*s >= 'a' && *s <= 'z') digit = *s - 'a' + 10;
      else if (*s >= 'A' && *s <= 'Z') digit = *s - 'A' + 10;
      else break;
      if (digit >= base) break;
      r = multiply(r, base, r);
      r = add(r, 0, digit, r);
      ++s;
    }
    r->sgn = sgn;
  }
  return r;
}


static const int _libgxx_maxfmt = 20;
AllocRing _libgxx_fmtq(_libgxx_maxfmt);

char* Itoa(const IntRep* x, int base, int width)
{
  int fmtlen = (int) ((x->len + 1) * I_SHIFT / lg(base) + 4 + width);
  char* fmtbase = (char *) _libgxx_fmtq.alloc(fmtlen);
  char* f = cvtItoa(x, fmtbase, fmtlen, base, 0, width, 0, ' ', 'X', 0);
  return f;
}

gOutput& operator<<(gOutput &s, const gInteger &y)
{
  return s << Itoa(y.rep);
}

char*  cvtItoa(const IntRep* x, char* fmt, int& fmtlen, int base, int showbase,
              int width, int align_right, char fillchar, char Xcase, 
              int showpos)
{
  char* e = fmt + fmtlen - 1;
  char* s = e;
  *--s = 0;

  if (x->len == 0)
    *--s = '0';
  else
  {
    IntRep* z = Icopy(0, x);

    // split division by base into two parts: 
    // first divide by biggest power of base that fits in an unsigned short,
    // then use straight signed div/mods from there. 

    // find power
    int bpower = 1;
    unsigned short b = base;
	 unsigned short maxb = (unsigned short) (I_MAXNUM / base);
    while (b < maxb)
    {
      b *= base;
      ++bpower;
    }
    for(;;)
    {
      int rem = unscale(z->s, z->len, b, z->s);
      Icheck(z);
      if (z->len == 0)
      {
        while (rem != 0)
        {
          char ch = rem % base;
          rem /= base;
          if (ch >= 10)
            ch += 'a' - 10;
          else
            ch += '0';
          *--s = ch;
        }
	if (!STATIC_IntRep(z)) delete z;
        break;
      }
      else
      {
        for (int i = 0; i < bpower; ++i)
        {
          char ch = rem % base;
          rem /= base;
          if (ch >= 10)
            ch += 'a' - 10;
          else
            ch += '0';
          *--s = ch;
        }
      }
    }
  }

  if (base == 8 && showbase) 
    *--s = '0';
  else if (base == 16 && showbase) 
  { 
    *--s = Xcase; 
    *--s = '0'; 
  }
  if (x->sgn == I_NEGATIVE) *--s = '-';
  else if (showpos) *--s = '+';
  int w = (int) (e - s - 1);
  if (!align_right || w >= width)
  {
    while (w++ < width)
      *--s = fillchar;
	 fmtlen = (int) (e - s - 1);
    return s;
  }
  else
  {
    char* p = fmt;
#ifdef UNUSED
	 int gap = (int) (s - p);
#endif   // UNUSED
	 for (char* t = s; *t != 0; ++t, ++p) *p = *t;
    while (w++ < width) *p++ = fillchar;
    *p = 0;
	 fmtlen = (int) (p - fmt);
    return fmt;
  }
}

char* dec(const gInteger& x, int width)
{
  return Itoa(x, 10, width);
}

char* oct(const gInteger& x, int width)
{
  return Itoa(x, 8, width);
}

char* hex(const gInteger& x, int width)
{
  return Itoa(x, 16, width);
}

//
// The >> operator is currently commented out... should be modified to
// work with the input/output classes later...
//

gInput &operator>>(gInput& s, gInteger& y)
{
  char sgn = 0;
  char ch;
  y.rep = Icopy_zero(y.rep);

  do  {
	 s.get(ch);
  }  while (isspace(ch));

  s.unget(ch);

  while (s.get(ch))
  {
	 if (ch == '-')
	 {
		if (sgn == 0)
		  sgn = '-';
		else
		  break;
	 }
	 else
	 {
		if (ch >= '0' && ch <= '9')
		{
		  long digit = ch - '0';
		  y *= 10;
		  y += digit;
		}
		else
		  break;
	 }
  }
  s.unget(ch);

  if (sgn == '-')
	 y.negate();

  return s;
}

int gInteger::OK() const
{
  if (rep != 0)
	 {
      int l = rep->len;
      int s = rep->sgn;
      int v = l <= rep->sz || STATIC_IntRep(rep);    // length within bounds
      v &= s == 0 || s == 1;        // legal sign
      Icheck(rep);                  // and correctly adjusted
      v &= rep->len == l;
      v &= rep->sgn == s;
      if (v)
	  return v;
    }
  error("invariant failure");
  return 0;
}

void gInteger::error(const char* msg) const
{
  // (*lib_error_handler)("gInteger", msg);
  //  gerr << msg << '\n';
}



// The following were moved from the header file to stop BC from squealing
// endless quantities of warnings

gInteger::gInteger() :rep(&_ZeroRep) {}

gInteger::gInteger(IntRep* r) :rep(r) {}

gInteger::gInteger(int y) :rep(Icopy_long(0, (long)y)) {}

gInteger::gInteger(long y) :rep(Icopy_long(0, y)) {}

gInteger::gInteger(unsigned long y) :rep(Icopy_ulong(0, y)) {}

gInteger::gInteger(const gInteger&  y) :rep(Icopy(0, y.rep)) {}

gInteger::~gInteger() { if (rep && !STATIC_IntRep(rep)) delete rep; }

void  gInteger::operator = (const gInteger&  y)
{
  rep = Icopy(rep, y.rep);
}

void gInteger::operator = (long y)
{
  rep = Icopy_long(rep, y); 
}

int gInteger::initialized() const
{
  return rep != 0;
}

// procedural versions

int compare(const gInteger& x, const gInteger& y)
{
  return compare(x.rep, y.rep);
}

int ucompare(const gInteger& x, const gInteger& y)
{
  return ucompare(x.rep, y.rep);
}

int compare(const gInteger& x, long y)
{
  return compare(x.rep, y);
}

int ucompare(const gInteger& x, long y)
{
  return ucompare(x.rep, y);
}

int compare(long x, const gInteger& y)
{
  return -compare(y.rep, x);
}

int ucompare(long x, const gInteger& y)
{
  return -ucompare(y.rep, x);
}

void  add(const gInteger& x, const gInteger& y, gInteger& dest)
{
  dest.rep = add(x.rep, 0, y.rep, 0, dest.rep);
}

void  sub(const gInteger& x, const gInteger& y, gInteger& dest)
{
  dest.rep = add(x.rep, 0, y.rep, 1, dest.rep);
}

void  mul(const gInteger& x, const gInteger& y, gInteger& dest)
{
  dest.rep = multiply(x.rep, y.rep, dest.rep);
}

void  div(const gInteger& x, const gInteger& y, gInteger& dest)
{
  dest.rep = div(x.rep, y.rep, dest.rep);
}

void  mod(const gInteger& x, const gInteger& y, gInteger& dest)
{
  dest.rep = mod(x.rep, y.rep, dest.rep);
}

void  And(const gInteger& x, const gInteger& y, gInteger& dest)
{
  dest.rep = bitop(x.rep, y.rep, dest.rep, '&');
}

void  Or(const gInteger& x, const gInteger& y, gInteger& dest)
{
  dest.rep = bitop(x.rep, y.rep, dest.rep, '|');
}

void  Xor(const gInteger& x, const gInteger& y, gInteger& dest)
{
  dest.rep = bitop(x.rep, y.rep, dest.rep, '^');
}

void  lshift(const gInteger& x, const gInteger& y, gInteger& dest)
{
  dest.rep = lshift(x.rep, y.rep, 0, dest.rep);
}

void  rshift(const gInteger& x, const gInteger& y, gInteger& dest)
{
  dest.rep = lshift(x.rep, y.rep, 1, dest.rep);
}

void  pow(const gInteger& x, const gInteger& y, gInteger& dest)
{
  dest.rep = power(x.rep, Itolong(y.rep), dest.rep); // not incorrect
}

void  add(const gInteger& x, long y, gInteger& dest)
{
  dest.rep = add(x.rep, 0, y, dest.rep);
}

void  sub(const gInteger& x, long y, gInteger& dest)
{
  dest.rep = add(x.rep, 0, -y, dest.rep);
}

void  mul(const gInteger& x, long y, gInteger& dest)
{
  dest.rep = multiply(x.rep, y, dest.rep);
}

void  div(const gInteger& x, long y, gInteger& dest)
{
  dest.rep = div(x.rep, y, dest.rep);
}

void  mod(const gInteger& x, long y, gInteger& dest)
{
  dest.rep = mod(x.rep, y, dest.rep);
}

void  And(const gInteger& x, long y, gInteger& dest)
{
  dest.rep = bitop(x.rep, y, dest.rep, '&');
}

void  Or(const gInteger& x, long y, gInteger& dest)
{
  dest.rep = bitop(x.rep, y, dest.rep, '|');
}

void  Xor(const gInteger& x, long y, gInteger& dest)
{
  dest.rep = bitop(x.rep, y, dest.rep, '^');
}

void  lshift(const gInteger& x, long y, gInteger& dest)
{
  dest.rep = lshift(x.rep, y, dest.rep);
}

void  rshift(const gInteger& x, long y, gInteger& dest)
{
  dest.rep = lshift(x.rep, -y, dest.rep);
}

void  pow(const gInteger& x, long y, gInteger& dest)
{
  dest.rep = power(x.rep, y, dest.rep);
}

void abs(const gInteger& x, gInteger& dest)
{
  dest.rep = abs(x.rep, dest.rep);
}

void negate(const gInteger& x, gInteger& dest)
{
  dest.rep = negate(x.rep, dest.rep);
}

void complement(const gInteger& x, gInteger& dest)
{
  dest.rep = Compl(x.rep, dest.rep);
}

void  add(long x, const gInteger& y, gInteger& dest)
{
  dest.rep = add(y.rep, 0, x, dest.rep);
}

void  sub(long x, const gInteger& y, gInteger& dest)
{
  dest.rep = add(y.rep, 1, x, dest.rep);
}

void  mul(long x, const gInteger& y, gInteger& dest)
{
  dest.rep = multiply(y.rep, x, dest.rep);
}

void  And(long x, const gInteger& y, gInteger& dest)
{
  dest.rep = bitop(y.rep, x, dest.rep, '&');
}

void  Or(long x, const gInteger& y, gInteger& dest)
{
  dest.rep = bitop(y.rep, x, dest.rep, '|');
}

void  Xor(long x, const gInteger& y, gInteger& dest)
{
  dest.rep = bitop(y.rep, x, dest.rep, '^');
}


// operator versions

int operator == (const gInteger&  x, const gInteger&  y)
{
  return compare(x, y) == 0; 
}

int operator == (const gInteger&  x, long y)
{
  return compare(x, y) == 0; 
}

int operator != (const gInteger&  x, const gInteger&  y)
{
  return compare(x, y) != 0; 
}

int operator != (const gInteger&  x, long y)
{
  return compare(x, y) != 0; 
}