imath.c

samba最新软件

}

/* }}} */

/* {{{ mp_int_add_value(a, value, c) */

mp_result mp_int_add_value(mp_int a, int value, mp_int c)
{
  mpz_t     vtmp;
  mp_digit  vbuf[MP_VALUE_DIGITS(value)];

  s_fake(&vtmp, value, vbuf);

  return mp_int_add(a, &vtmp, c);
}

/* }}} */

/* {{{ mp_int_sub(a, b, c) */

mp_result mp_int_sub(mp_int a, mp_int b, mp_int c)
{
  mp_size  ua, ub, uc, max;

  CHECK(a != NULL && b != NULL && c != NULL);

  ua = MP_USED(a); ub = MP_USED(b); uc = MP_USED(c);
  max = MAX(ua, ub);

  if(MP_SIGN(a) != MP_SIGN(b)) {
    /* Different signs -- add magnitudes and keep sign of a */
    mp_digit carry;

    if(!s_pad(c, max))
      return MP_MEMORY;

    carry = s_uadd(MP_DIGITS(a), MP_DIGITS(b), MP_DIGITS(c), ua, ub);
    uc = max;

    if(carry) {
      if(!s_pad(c, max + 1))
	return MP_MEMORY;

      c->digits[max] = carry;
      ++uc;
    }

    MP_USED(c) = uc;
    MP_SIGN(c) = MP_SIGN(a);

  } 
  else {
    /* Same signs -- subtract magnitudes */
    mp_int  x, y;
    mp_sign osign;
    int     cmp = s_ucmp(a, b);

    if(!s_pad(c, max))
      return MP_MEMORY;

    if(cmp >= 0) {
      x = a; y = b; osign = MP_ZPOS;
    } 
    else {
      x = b; y = a; osign = MP_NEG;
    }

    if(MP_SIGN(a) == MP_NEG && cmp != 0)
      osign = 1 - osign;

    s_usub(MP_DIGITS(x), MP_DIGITS(y), MP_DIGITS(c), MP_USED(x), MP_USED(y));
    MP_USED(c) = MP_USED(x);
    CLAMP(c);

    MP_SIGN(c) = osign;
  }

  return MP_OK;
}

/* }}} */

/* {{{ mp_int_sub_value(a, value, c) */

mp_result mp_int_sub_value(mp_int a, int value, mp_int c)
{
  mpz_t     vtmp;
  mp_digit  vbuf[MP_VALUE_DIGITS(value)];

  s_fake(&vtmp, value, vbuf);

  return mp_int_sub(a, &vtmp, c);
}

/* }}} */

/* {{{ mp_int_mul(a, b, c) */

mp_result mp_int_mul(mp_int a, mp_int b, mp_int c)
{ 
  mp_digit *out;
  mp_size   osize, ua, ub, p = 0;
  mp_sign   osign;

  CHECK(a != NULL && b != NULL && c != NULL);

  /* If either input is zero, we can shortcut multiplication */
  if(mp_int_compare_zero(a) == 0 || mp_int_compare_zero(b) == 0) {
    mp_int_zero(c);
    return MP_OK;
  }
  
  /* Output is positive if inputs have same sign, otherwise negative */
  osign = (MP_SIGN(a) == MP_SIGN(b)) ? MP_ZPOS : MP_NEG;

  /* If the output is not identical to any of the inputs, we'll write
     the results directly; otherwise, allocate a temporary space. */
  ua = MP_USED(a); ub = MP_USED(b);
  osize = MAX(ua, ub);
  osize = 4 * ((osize + 1) / 2);

  if(c == a || c == b) {
    p = ROUND_PREC(osize);
    p = MAX(p, default_precision);

    if((out = s_alloc(p)) == NULL)
      return MP_MEMORY;
  } 
  else {
    if(!s_pad(c, osize))
      return MP_MEMORY;
    
    out = MP_DIGITS(c);
  }
  ZERO(out, osize);

  if(!s_kmul(MP_DIGITS(a), MP_DIGITS(b), out, ua, ub))
    return MP_MEMORY;

  /* If we allocated a new buffer, get rid of whatever memory c was
     already using, and fix up its fields to reflect that.
   */
  if(out != MP_DIGITS(c)) {
    if((void *) MP_DIGITS(c) != (void *) c)
      s_free(MP_DIGITS(c));
    MP_DIGITS(c) = out;
    MP_ALLOC(c) = p;
  }

  MP_USED(c) = osize; /* might not be true, but we'll fix it ... */
  CLAMP(c);           /* ... right here */
  MP_SIGN(c) = osign;
  
  return MP_OK;
}

/* }}} */

/* {{{ mp_int_mul_value(a, value, c) */

mp_result mp_int_mul_value(mp_int a, int value, mp_int c)
{
  mpz_t     vtmp;
  mp_digit  vbuf[MP_VALUE_DIGITS(value)];

  s_fake(&vtmp, value, vbuf);

  return mp_int_mul(a, &vtmp, c);
}

/* }}} */

/* {{{ mp_int_mul_pow2(a, p2, c) */

mp_result mp_int_mul_pow2(mp_int a, int p2, mp_int c)
{
  mp_result res;
  CHECK(a != NULL && c != NULL && p2 >= 0);

  if((res = mp_int_copy(a, c)) != MP_OK)
    return res;

  if(s_qmul(c, (mp_size) p2))
    return MP_OK;
  else
    return MP_MEMORY;
}

/* }}} */

/* {{{ mp_int_sqr(a, c) */

mp_result mp_int_sqr(mp_int a, mp_int c)
{ 
  mp_digit *out;
  mp_size   osize, p = 0;

  CHECK(a != NULL && c != NULL);

  /* Get a temporary buffer big enough to hold the result */
  osize = (mp_size) 4 * ((MP_USED(a) + 1) / 2);
  if(a == c) {
    p = ROUND_PREC(osize);
    p = MAX(p, default_precision);

    if((out = s_alloc(p)) == NULL)
      return MP_MEMORY;
  } 
  else {
    if(!s_pad(c, osize)) 
      return MP_MEMORY;

    out = MP_DIGITS(c);
  }
  ZERO(out, osize);

  s_ksqr(MP_DIGITS(a), out, MP_USED(a));

  /* Get rid of whatever memory c was already using, and fix up its
     fields to reflect the new digit array it's using
   */
  if(out != MP_DIGITS(c)) {
    if((void *) MP_DIGITS(c) != (void *) c)
      s_free(MP_DIGITS(c));
    MP_DIGITS(c) = out;
    MP_ALLOC(c) = p;
  }

  MP_USED(c) = osize; /* might not be true, but we'll fix it ... */
  CLAMP(c);           /* ... right here */
  MP_SIGN(c) = MP_ZPOS;
  
  return MP_OK;
}

/* }}} */

/* {{{ mp_int_div(a, b, q, r) */

mp_result mp_int_div(mp_int a, mp_int b, mp_int q, mp_int r)
{
  int       cmp, last = 0, lg;
  mp_result res = MP_OK;
  mpz_t     temp[2];
  mp_int    qout, rout;
  mp_sign   sa = MP_SIGN(a), sb = MP_SIGN(b);

  CHECK(a != NULL && b != NULL && q != r);
  
  if(CMPZ(b) == 0)
    return MP_UNDEF;
  else if((cmp = s_ucmp(a, b)) < 0) {
    /* If |a| < |b|, no division is required:
       q = 0, r = a
     */
    if(r && (res = mp_int_copy(a, r)) != MP_OK)
      return res;

    if(q)
      mp_int_zero(q);

    return MP_OK;
  } 
  else if(cmp == 0) {
    /* If |a| = |b|, no division is required:
       q = 1 or -1, r = 0
     */
    if(r)
      mp_int_zero(r);

    if(q) {
      mp_int_zero(q);
      q->digits[0] = 1;

      if(sa != sb)
	MP_SIGN(q) = MP_NEG;
    }

    return MP_OK;
  } 

  /* When |a| > |b|, real division is required.  We need someplace to
     store quotient and remainder, but q and r are allowed to be NULL
     or to overlap with the inputs.
   */
  if((lg = s_isp2(b)) < 0) {
    if(q && b != q && (res = mp_int_copy(a, q)) == MP_OK) {
      qout = q;
    } 
    else {
      qout = TEMP(last);
      SETUP(mp_int_init_copy(TEMP(last), a), last);
    }

    if(r && a != r && (res = mp_int_copy(b, r)) == MP_OK) {
      rout = r;
    } 
    else {
      rout = TEMP(last);
      SETUP(mp_int_init_copy(TEMP(last), b), last);
    }

    if((res = s_udiv(qout, rout)) != MP_OK) goto CLEANUP;
  } 
  else {
    if(q && (res = mp_int_copy(a, q)) != MP_OK) goto CLEANUP;
    if(r && (res = mp_int_copy(a, r)) != MP_OK) goto CLEANUP;

    if(q) s_qdiv(q, (mp_size) lg); qout = q;
    if(r) s_qmod(r, (mp_size) lg); rout = r;
  }

  /* Recompute signs for output */
  if(rout) { 
    MP_SIGN(rout) = sa;
    if(CMPZ(rout) == 0)
      MP_SIGN(rout) = MP_ZPOS;
  }
  if(qout) {
    MP_SIGN(qout) = (sa == sb) ? MP_ZPOS : MP_NEG;
    if(CMPZ(qout) == 0)
      MP_SIGN(qout) = MP_ZPOS;
  }

  if(q && (res = mp_int_copy(qout, q)) != MP_OK) goto CLEANUP;
  if(r && (res = mp_int_copy(rout, r)) != MP_OK) goto CLEANUP;

 CLEANUP:
  while(--last >= 0)
    mp_int_clear(TEMP(last));

  return res;
}

/* }}} */

/* {{{ mp_int_mod(a, m, c) */

mp_result mp_int_mod(mp_int a, mp_int m, mp_int c)
{
  mp_result res;
  mpz_t     tmp;
  mp_int    out;

  if(m == c) {
    mp_int_init(&tmp);
    out = &tmp;
  } 
  else {
    out = c;
  }

  if((res = mp_int_div(a, m, NULL, out)) != MP_OK)
    goto CLEANUP;

  if(CMPZ(out) < 0)
    res = mp_int_add(out, m, c);
  else
    res = mp_int_copy(out, c);

 CLEANUP:
  if(out != c)
    mp_int_clear(&tmp);

  return res;
}

/* }}} */

/* {{{ mp_int_div_value(a, value, q, r) */

mp_result mp_int_div_value(mp_int a, int value, mp_int q, int *r)
{
  mpz_t     vtmp, rtmp;
  mp_digit  vbuf[MP_VALUE_DIGITS(value)];
  mp_result res;

  mp_int_init(&rtmp);
  s_fake(&vtmp, value, vbuf);

  if((res = mp_int_div(a, &vtmp, q, &rtmp)) != MP_OK)
    goto CLEANUP;

  if(r)
    (void) mp_int_to_int(&rtmp, r); /* can't fail */

 CLEANUP:
  mp_int_clear(&rtmp);
  return res;
}

/* }}} */

/* {{{ mp_int_div_pow2(a, p2, q, r) */

mp_result mp_int_div_pow2(mp_int a, int p2, mp_int q, mp_int r)
{
  mp_result res = MP_OK;

  CHECK(a != NULL && p2 >= 0 && q != r);

  if(q != NULL && (res = mp_int_copy(a, q)) == MP_OK)
    s_qdiv(q, (mp_size) p2);
  
  if(res == MP_OK && r != NULL && (res = mp_int_copy(a, r)) == MP_OK)
    s_qmod(r, (mp_size) p2);

  return res;
}

/* }}} */

/* {{{ mp_int_expt(a, b, c) */

mp_result mp_int_expt(mp_int a, int b, mp_int c)
{
  mpz_t     t;
  mp_result res;
  unsigned int v = abs(b);
  
  CHECK(b >= 0 && c != NULL);

  if((res = mp_int_init_copy(&t, a)) != MP_OK)
    return res;

  (void) mp_int_set_value(c, 1);
  while(v != 0) {
    if(v & 1) {
      if((res = mp_int_mul(c, &t, c)) != MP_OK)
	goto CLEANUP;
    }

    v >>= 1;
    if(v == 0) break;

    if((res = mp_int_sqr(&t, &t)) != MP_OK)
      goto CLEANUP;
  }
  
 CLEANUP:
  mp_int_clear(&t);
  return res;
}

/* }}} */

/* {{{ mp_int_expt_value(a, b, c) */

mp_result mp_int_expt_value(int a, int b, mp_int c)
{
  mpz_t     t;
  mp_result res;
  unsigned int v = abs(b);
  
  CHECK(b >= 0 && c != NULL);

  if((res = mp_int_init_value(&t, a)) != MP_OK)
    return res;

  (void) mp_int_set_value(c, 1);
  while(v != 0) {
    if(v & 1) {
      if((res = mp_int_mul(c, &t, c)) != MP_OK)
	goto CLEANUP;
    }

    v >>= 1;
    if(v == 0) break;

    if((res = mp_int_sqr(&t, &t)) != MP_OK)
      goto CLEANUP;
  }
  
 CLEANUP:
  mp_int_clear(&t);
  return res;
}

/* }}} */

/* {{{ mp_int_compare(a, b) */

int       mp_int_compare(mp_int a, mp_int b)
{ 
  mp_sign sa;

  CHECK(a != NULL && b != NULL);

  sa = MP_SIGN(a);
  if(sa == MP_SIGN(b)) {
    int cmp = s_ucmp(a, b);

    /* If they're both zero or positive, the normal comparison
       applies; if both negative, the sense is reversed. */
    if(sa == MP_ZPOS) 
      return cmp;
    else
      return -cmp;

  } 
  else {
    if(sa == MP_ZPOS)
      return 1;
    else
      return -1;
  }
}

/* }}} */

/* {{{ mp_int_compare_unsigned(a, b) */

int       mp_int_compare_unsigned(mp_int a, mp_int b)
{ 
  NRCHECK(a != NULL && b != NULL);

  return s_ucmp(a, b);
}

/* }}} */

/* {{{ mp_int_compare_zero(z) */

int       mp_int_compare_zero(mp_int z)
{ 
  NRCHECK(z != NULL);

  if(MP_USED(z) == 1 && z->digits[0] == 0)
    return 0;
  else if(MP_SIGN(z) == MP_ZPOS)
    return 1;
  else 
    return -1;
}

/* }}} */

/* {{{ mp_int_compare_value(z, value) */

int       mp_int_compare_value(mp_int z, int value)
{
  mp_sign vsign = (value < 0) ? MP_NEG : MP_ZPOS;
  int     cmp;

  CHECK(z != NULL);

  if(vsign == MP_SIGN(z)) {
    cmp = s_vcmp(z, value);

    if(vsign == MP_ZPOS)
      return cmp;
    else
      return -cmp;
  } 
  else {
    if(value < 0)
      return 1;
    else
      return -1;
  }
}

/* }}} */

/* {{{ mp_int_exptmod(a, b, m, c) */

mp_result mp_int_exptmod(mp_int a, mp_int b, mp_int m, mp_int c)
{ 
  mp_result res;
  mp_size   um;
  mpz_t     temp[3];
  mp_int    s;
  int       last = 0;

  CHECK(a != NULL && b != NULL && c != NULL && m != NULL);

  /* Zero moduli and negative exponents are not considered. */
  if(CMPZ(m) == 0)
    return MP_UNDEF;
  if(CMPZ(b) < 0)
    return MP_RANGE;

  um = MP_USED(m);
  SETUP(mp_int_init_size(TEMP(0), 2 * um), last);
  SETUP(mp_int_init_size(TEMP(1), 2 * um), last);

  if(c == b || c == m) {
    SETUP(mp_int_init_size(TEMP(2), 2 * um), last);
    s = TEMP(2);
  } 
  else {
    s = c;
  }
  
  if((res = mp_int_mod(a, m, TEMP(0))) != MP_OK) goto CLEANUP;

  if((res = s_brmu(TEMP(1), m)) != MP_OK) goto CLEANUP;

  if((res = s_embar(TEMP(0), b, m, TEMP(1), s)) != MP_OK)
    goto CLEANUP;

  res = mp_int_copy(s, c);

 CLEANUP:
  while(--last >= 0)
    mp_int_clear(TEMP(last));

  return res;
}

/* }}} */