imath.c

samba最新软件

  --uz;
  nbits = uz * MP_DIGIT_BIT;
  d = z->digits[uz];

  while(d != 0) {
    d >>= 1;
    ++nbits;
  }

  return nbits;
}

/* }}} */

/* {{{ mp_int_to_binary(z, buf, limit) */

mp_result mp_int_to_binary(mp_int z, unsigned char *buf, int limit)
{
  static const int PAD_FOR_2C = 1;

  mp_result res;
  int       limpos = limit;

  CHECK(z != NULL && buf != NULL);
  
  res = s_tobin(z, buf, &limpos, PAD_FOR_2C);

  if(MP_SIGN(z) == MP_NEG)
    s_2comp(buf, limpos);

  return res;
}

/* }}} */

/* {{{ mp_int_read_binary(z, buf, len) */

mp_result mp_int_read_binary(mp_int z, unsigned char *buf, int len)
{
  mp_size need, i;
  unsigned char *tmp;
  mp_digit *dz;

  CHECK(z != NULL && buf != NULL && len > 0);

  /* Figure out how many digits are needed to represent this value */
  need = ((len * CHAR_BIT) + (MP_DIGIT_BIT - 1)) / MP_DIGIT_BIT;
  if(!s_pad(z, need))
    return MP_MEMORY;

  mp_int_zero(z);

  /* If the high-order bit is set, take the 2's complement before
     reading the value (it will be restored afterward) */
  if(buf[0] >> (CHAR_BIT - 1)) {
    MP_SIGN(z) = MP_NEG;
    s_2comp(buf, len);
  }
  
  dz = MP_DIGITS(z);
  for(tmp = buf, i = len; i > 0; --i, ++tmp) {
    s_qmul(z, (mp_size) CHAR_BIT);
    *dz |= *tmp;
  }

  /* Restore 2's complement if we took it before */
  if(MP_SIGN(z) == MP_NEG)
    s_2comp(buf, len);

  return MP_OK;
}

/* }}} */

/* {{{ mp_int_binary_len(z) */

mp_result mp_int_binary_len(mp_int z)
{
  mp_result  res = mp_int_count_bits(z);
  int        bytes = mp_int_unsigned_len(z);

  if(res <= 0)
    return res;

  bytes = (res + (CHAR_BIT - 1)) / CHAR_BIT;

  /* If the highest-order bit falls exactly on a byte boundary, we
     need to pad with an extra byte so that the sign will be read
     correctly when reading it back in. */
  if(bytes * CHAR_BIT == res)
    ++bytes;

  return bytes;
}

/* }}} */

/* {{{ mp_int_to_unsigned(z, buf, limit) */

mp_result mp_int_to_unsigned(mp_int z, unsigned char *buf, int limit)
{
  static const int NO_PADDING = 0;

  CHECK(z != NULL && buf != NULL);

  return s_tobin(z, buf, &limit, NO_PADDING);
}

/* }}} */

/* {{{ mp_int_read_unsigned(z, buf, len) */

mp_result mp_int_read_unsigned(mp_int z, unsigned char *buf, int len)
{
  mp_size need, i;
  unsigned char *tmp;
  mp_digit *dz;

  CHECK(z != NULL && buf != NULL && len > 0);

  /* Figure out how many digits are needed to represent this value */
  need = ((len * CHAR_BIT) + (MP_DIGIT_BIT - 1)) / MP_DIGIT_BIT;
  if(!s_pad(z, need))
    return MP_MEMORY;

  mp_int_zero(z);

  dz = MP_DIGITS(z);
  for(tmp = buf, i = len; i > 0; --i, ++tmp) {
    (void) s_qmul(z, CHAR_BIT);
    *dz |= *tmp;
  }

  return MP_OK;
}

/* }}} */

/* {{{ mp_int_unsigned_len(z) */

mp_result mp_int_unsigned_len(mp_int z)
{
  mp_result  res = mp_int_count_bits(z);
  int        bytes;

  if(res <= 0)
    return res;

  bytes = (res + (CHAR_BIT - 1)) / CHAR_BIT;

  return bytes;
}

/* }}} */

/* {{{ mp_error_string(res) */

const char *mp_error_string(mp_result res)
{
  int ix;
  if(res > 0)
    return s_unknown_err;

  res = -res;
  for(ix = 0; ix < res && s_error_msg[ix] != NULL; ++ix)
    ;

  if(s_error_msg[ix] != NULL)
    return s_error_msg[ix];
  else
    return s_unknown_err;
}

/* }}} */

/*------------------------------------------------------------------------*/
/* Private functions for internal use.  These make assumptions.           */

/* {{{ s_alloc(num) */

static mp_digit *s_alloc(mp_size num)
{
  mp_digit *out = malloc(num * sizeof(mp_digit));

  assert(out != NULL); /* for debugging */
#if DEBUG > 1
  {
    mp_digit v = (mp_digit) 0xdeadbeef;
    int      ix;

    for(ix = 0; ix < num; ++ix)
      out[ix] = v;
  }
#endif

  return out;
}

/* }}} */

/* {{{ s_realloc(old, osize, nsize) */

static mp_digit *s_realloc(mp_digit *old, mp_size osize, mp_size nsize)
{
#if DEBUG > 1
  mp_digit *new = s_alloc(nsize);
  int       ix;

  for(ix = 0; ix < nsize; ++ix)
    new[ix] = (mp_digit) 0xdeadbeef;

  memcpy(new, old, osize * sizeof(mp_digit));
#else
  mp_digit *new = realloc(old, nsize * sizeof(mp_digit));

  assert(new != NULL); /* for debugging */
#endif
  return new;
}

/* }}} */

/* {{{ s_free(ptr) */

static void s_free(void *ptr)
{
  free(ptr);
}

/* }}} */

/* {{{ s_pad(z, min) */

static int      s_pad(mp_int z, mp_size min)
{
  if(MP_ALLOC(z) < min) {
    mp_size nsize = ROUND_PREC(min);
    mp_digit *tmp;

    if((void *)z->digits == (void *)z) {
      if((tmp = s_alloc(nsize)) == NULL)
        return 0;

      COPY(MP_DIGITS(z), tmp, MP_USED(z));
    }
    else if((tmp = s_realloc(MP_DIGITS(z), MP_ALLOC(z), nsize)) == NULL)
      return 0;
    
    MP_DIGITS(z) = tmp;
    MP_ALLOC(z) = nsize;
  }

  return 1;
}

/* }}} */

/* {{{ s_clamp(z) */

#if TRACEABLE_CLAMP
static void     s_clamp(mp_int z)
{
  mp_size   uz = MP_USED(z);
  mp_digit *zd = MP_DIGITS(z) + uz - 1;

  while(uz > 1 && (*zd-- == 0))
    --uz;

  MP_USED(z) = uz;
}
#endif

/* }}} */

/* {{{ s_fake(z, value, vbuf) */

static void      s_fake(mp_int z, int value, mp_digit vbuf[])
{
  mp_size uv = (mp_size) s_vpack(value, vbuf);

  z->used = uv;
  z->alloc = MP_VALUE_DIGITS(value);
  z->sign = (value < 0) ? MP_NEG : MP_ZPOS;
  z->digits = vbuf;
}

/* }}} */

/* {{{ s_cdig(da, db, len) */

static int      s_cdig(mp_digit *da, mp_digit *db, mp_size len)
{
  mp_digit *dat = da + len - 1, *dbt = db + len - 1;

  for(/* */; len != 0; --len, --dat, --dbt) {
    if(*dat > *dbt)
      return 1;
    else if(*dat < *dbt)
      return -1;
  }

  return 0;
}

/* }}} */

/* {{{ s_vpack(v, t[]) */

static int       s_vpack(int v, mp_digit t[])
{
  unsigned int uv = (unsigned int)((v < 0) ? -v : v);
  int          ndig = 0;
  
  if(uv == 0)
    t[ndig++] = 0;
  else {
    while(uv != 0) {
      t[ndig++] = (mp_digit) uv;
      uv >>= MP_DIGIT_BIT/2;
      uv >>= MP_DIGIT_BIT/2;
    }
  }

  return ndig;
}

/* }}} */

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

static int      s_ucmp(mp_int a, mp_int b)
{
  mp_size  ua = MP_USED(a), ub = MP_USED(b);
  
  if(ua > ub)
    return 1;
  else if(ub > ua) 
    return -1;
  else 
    return s_cdig(MP_DIGITS(a), MP_DIGITS(b), ua);
}

/* }}} */

/* {{{ s_vcmp(a, v) */

static int      s_vcmp(mp_int a, int v)
{
  mp_digit     vdig[MP_VALUE_DIGITS(v)];
  int          ndig = 0;
  mp_size      ua = MP_USED(a);

  ndig = s_vpack(v, vdig);

  if(ua > ndig)
    return 1;
  else if(ua < ndig)
    return -1;
  else
    return s_cdig(MP_DIGITS(a), vdig, ndig);
}

/* }}} */

/* {{{ s_uadd(da, db, dc, size_a, size_b) */

static mp_digit s_uadd(mp_digit *da, mp_digit *db, mp_digit *dc, 
		       mp_size size_a, mp_size size_b)
{
  mp_size pos;
  mp_word w = 0;

  /* Insure that da is the longer of the two to simplify later code */
  if(size_b > size_a) {
    SWAP(mp_digit *, da, db);
    SWAP(mp_size, size_a, size_b);
  }

  /* Add corresponding digits until the shorter number runs out */
  for(pos = 0; pos < size_b; ++pos, ++da, ++db, ++dc) {
    w = w + (mp_word) *da + (mp_word) *db;
    *dc = LOWER_HALF(w);
    w = UPPER_HALF(w);
  }

  /* Propagate carries as far as necessary */
  for(/* */; pos < size_a; ++pos, ++da, ++dc) {
    w = w + *da;

    *dc = LOWER_HALF(w);
    w = UPPER_HALF(w);
  }

  /* Return carry out */
  return (mp_digit)w;
}

/* }}} */

/* {{{ s_usub(da, db, dc, size_a, size_b) */

static void     s_usub(mp_digit *da, mp_digit *db, mp_digit *dc,
		       mp_size size_a, mp_size size_b)
{
  mp_size pos;
  mp_word w = 0;

  /* We assume that |a| >= |b| so this should definitely hold */
  assert(size_a >= size_b);

  /* Subtract corresponding digits and propagate borrow */
  for(pos = 0; pos < size_b; ++pos, ++da, ++db, ++dc) {
    w = ((mp_word)MP_DIGIT_MAX + 1 +  /* MP_RADIX */
	 (mp_word)*da) - w - (mp_word)*db;

    *dc = LOWER_HALF(w);
    w = (UPPER_HALF(w) == 0);
  }

  /* Finish the subtraction for remaining upper digits of da */
  for(/* */; pos < size_a; ++pos, ++da, ++dc) {
    w = ((mp_word)MP_DIGIT_MAX + 1 +  /* MP_RADIX */
	 (mp_word)*da) - w; 

    *dc = LOWER_HALF(w);
    w = (UPPER_HALF(w) == 0);
  }

  /* If there is a borrow out at the end, it violates the precondition */
  assert(w == 0);
}

/* }}} */

/* {{{ s_kmul(da, db, dc, size_a, size_b) */

static int       s_kmul(mp_digit *da, mp_digit *db, mp_digit *dc,
			mp_size size_a, mp_size size_b)
{
  mp_size  bot_size;

  /* Make sure b is the smaller of the two input values */
  if(size_b > size_a) {
    SWAP(mp_digit *, da, db);
    SWAP(mp_size, size_a, size_b);
  }

  /* Insure that the bottom is the larger half in an odd-length split;
     the code below relies on this being true.
   */
  bot_size = (size_a + 1) / 2;

  /* If the values are big enough to bother with recursion, use the
     Karatsuba algorithm to compute the product; otherwise use the
     normal multiplication algorithm
   */
  if(multiply_threshold && 
     size_a >= multiply_threshold && 
     size_b > bot_size) {

    mp_digit *t1, *t2, *t3, carry;

    mp_digit *a_top = da + bot_size; 
    mp_digit *b_top = db + bot_size;

    mp_size  at_size = size_a - bot_size;
    mp_size  bt_size = size_b - bot_size;
    mp_size  buf_size = 2 * bot_size;

    /* Do a single allocation for all three temporary buffers needed;
       each buffer must be big enough to hold the product of two
       bottom halves, and one buffer needs space for the completed 
       product; twice the space is plenty.
     */
    if((t1 = s_alloc(4 * buf_size)) == NULL) return 0;
    t2 = t1 + buf_size;
    t3 = t2 + buf_size;
    ZERO(t1, 4 * buf_size);

    /* t1 and t2 are initially used as temporaries to compute the inner product
       (a1 + a0)(b1 + b0) = a1b1 + a1b0 + a0b1 + a0b0
     */
    carry = s_uadd(da, a_top, t1, bot_size, at_size);      /* t1 = a1 + a0 */
    t1[bot_size] = carry;

    carry = s_uadd(db, b_top, t2, bot_size, bt_size);      /* t2 = b1 + b0 */
    t2[bot_size] = carry;

    (void) s_kmul(t1, t2, t3, bot_size + 1, bot_size + 1); /* t3 = t1 * t2 */

    /* Now we'll get t1 = a0b0 and t2 = a1b1, and subtract them out so that
       we're left with only the pieces we want:  t3 = a1b0 + a0b1
     */
    ZERO(t1, buf_size);
    ZERO(t2, buf_size);
    (void) s_kmul(da, db, t1, bot_size, bot_size);     /* t1 = a0 * b0 */
    (void) s_kmul(a_top, b_top, t2, at_size, bt_size); /* t2 = a1 * b1 */

    /* Subtract out t1 and t2 to get the inner product */
    s_usub(t3, t1, t3, buf_size + 2, buf_size);
    s_usub(t3, t2, t3, buf_size + 2, buf_size);

    /* Assemble the output value */
    COPY(t1, dc, buf_size);
    carry = s_uadd(t3, dc + bot_size, dc + bot_size,
		   buf_size + 1, buf_size); 
    assert(carry == 0);
    
    carry = s_uadd(t2, dc + 2*bot_size, dc + 2*bot_size,
		   buf_size, buf_size); 
    assert(carry == 0);
    
    s_free(t1); /* note t2 and t3 are just internal pointers to t1 */
  } 
  else {
    s_umul(da, db, dc, size_a, size_b);
  }

  return 1;
}

/* }}} */

/* {{{ s_umul(da, db, dc, size_a, size_b) */

static void     s_umul(mp_digit *da, mp_digit *db, mp_digit *dc,
		       mp_size size_a, mp_size size_b)
{
  mp_size   a, b;
  mp_word   w;

  for(a = 0; a < size_a; ++a, ++dc, ++da) {
    mp_digit *dct = dc;
    mp_digit *dbt = db;

    if(*da == 0)
      continue;

    w = 0;
    for(b = 0; b < size_b; ++b, ++dbt, ++dct) {
      w = (mp_word)*da * (mp_word)*dbt + w + (mp_word)*dct;

      *dct = LOWER_HALF(w);
      w = UPPER_HALF(w);
    }

    *dct = (mp_digit)w;
  }
}

/* }}} */

/* {{{ s_ksqr(da, dc, size_a) */

static int       s_ksqr(mp_digit *da, mp_digit *dc, mp_size size_a)
{
  if(multiply_threshold && size_a > multiply_threshold) {
    mp_size    bot_size = (size_a + 1) / 2;
    mp_digit  *a_top = da + bot_size;
    mp_digit  *t1, *t2, *t3, carry;
    mp_size    at_size = size_a - bot_size;
    mp_size    buf_size = 2 * bot_size;

    if((t1 = s_alloc(4 * buf_size)) == NULL) return 0;
    t2 = t1 + buf_size;
    t3 = t2 + buf_size;
    ZERO(t1, 4 * buf_size);

    (void) s_ksqr(da, t1, bot_size);    /* t1 = a0 ^ 2 */
    (void) s_ksqr(a_top, t2, at_size);  /* t2 = a1 ^ 2 */

    (void) s_kmul(da, a_top, t3, bot_size, at_size);  /* t3 = a0 * a1 */

    /* Quick multiply t3 by 2, shifting left (can't overflow) */
    {
      int     i, top = bot_size + at_size;
      mp_word w, save = 0;

      for(i = 0; i < top; ++i) {
	w = t3[i];
	w = (w << 1) | save;
	t3[i] = LOWER_HALF(w);
	save = UPPER_HALF(w);
      }
      t3[i] = LOWER_HALF(save);
    }

    /* Assemble the output value */
    COPY(t1, dc, 2 * bot_size);
    carry = s_uadd(t3, dc + bot_size, dc + bot_size,
		   buf_size + 1, buf_size);
    assert(carry == 0);

    carry = s_uadd(t2, dc + 2*bot_size, dc + 2*bot_size,
		   buf_size, buf_size);
    assert(carry == 0);

    s_free(t1); /* note that t2 and t2 are internal pointers only */

  } 
  else {
    s_usqr(da, dc, size_a);
  }

  return 1;
}

/* }}} */

/* {{{ s_usqr(da, dc, size_a) */

static void      s_usqr(mp_digit *da, mp_digit *dc, mp_size size_a)