#define DIAG(T,V)
#endif
-/*
+/*
If MP_LOGTAB is not defined, use the math library to compute the
logarithms on the fly. Otherwise, use the static table below.
Pick which works best for your system.
/*
A table of the logs of 2 for various bases (the 0 and 1 entries of
- this table are meaningless and should not be referenced).
+ this table are meaningless and should not be referenced).
This table is used to compute output lengths for the mp_toradix()
function. Since a number n in radix r takes up about log_r(n)
log_r(n) = log_2(n) * log_r(2)
This table, therefore, is a table of log_r(2) for 2 <= r <= 36,
- which are the output bases supported.
+ which are the output bases supported.
*/
#include "logtab.h"
/* Value to digit maps for radix conversion */
/* s_dmap_1 - standard digits and letters */
-static const char *s_dmap_1 =
+static const char *s_dmap_1 =
"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";
#if 0
/* {{{ Static function declarations */
-/*
+/*
If MP_MACRO is false, these will be defined as actual functions;
otherwise, suitable macro definitions will be used. This works
around the fact that ANSI C89 doesn't support an 'inline' keyword
return MP_OKAY;
CLEANUP:
- while(--pos >= 0)
+ while(--pos >= 0)
mp_clear(&mp[pos]);
return res;
if(ALLOC(to) >= USED(from)) {
s_mp_setz(DIGITS(to) + USED(from), ALLOC(to) - USED(from));
s_mp_copy(DIGITS(from), DIGITS(to), USED(from));
-
+
} else {
if((tmp = s_mp_alloc(USED(from), sizeof(mp_digit))) == NULL)
return MP_MEM;
{
ARGCHK(mp != NULL && count > 0, MP_BADARG);
- while(--count >= 0)
+ while(--count >= 0)
mp_clear(&mp[count]);
} /* end mp_clear_array() */
/* {{{ mp_zero(mp) */
/*
- mp_zero(mp)
+ mp_zero(mp)
Set mp to zero. Does not change the allocated size of the structure,
and therefore cannot fail (except on a bad argument, which we ignore)
if((res = s_mp_mul_2d(mp, CHAR_BIT)) != MP_OKAY)
return res;
- res = s_mp_add_d(mp,
+ res = s_mp_add_d(mp,
(mp_digit)((v >> (ix * CHAR_BIT)) & UCHAR_MAX));
if(res != MP_OKAY)
return res;
if((res = mp_copy(a, b)) != MP_OKAY)
return res;
- if(s_mp_cmp_d(b, 0) == MP_EQ)
+ if(s_mp_cmp_d(b, 0) == MP_EQ)
SIGN(b) = MP_ZPOS;
- else
+ else
SIGN(b) = (SIGN(b) == MP_NEG) ? MP_ZPOS : MP_NEG;
return MP_OKAY;
if(SIGN(a) == SIGN(b)) { /* same sign: add values, keep sign */
/* Commutativity of addition lets us do this in either order,
- so we avoid having to use a temporary even if the result
+ so we avoid having to use a temporary even if the result
is supposed to replace the output
*/
if(c == b) {
if(c != a && (res = mp_copy(a, c)) != MP_OKAY)
return res;
- if((res = s_mp_add(c, b)) != MP_OKAY)
+ if((res = s_mp_add(c, b)) != MP_OKAY)
return res;
}
} else if((cmp = s_mp_cmp(a, b)) > 0) { /* different sign: a > b */
/* If the output is going to be clobbered, we will use a temporary
- variable; otherwise, we'll do it without touching the memory
+ variable; otherwise, we'll do it without touching the memory
allocator at all, if possible
*/
if(c == b) {
mp_clear(&tmp);
} else {
- if(c != b && ((res = mp_copy(b, c)) != MP_OKAY))
+ if(c != b && ((res = mp_copy(b, c)) != MP_OKAY))
return res;
if((res = s_mp_sub(c, a)) != MP_OKAY)
if((res = s_mp_mul(c, b)) != MP_OKAY)
return res;
}
-
+
if(sgn == MP_ZPOS || s_mp_cmp_d(c, 0) == MP_EQ)
SIGN(c) = MP_ZPOS;
else
SIGN(c) = sgn;
-
+
return MP_OKAY;
} /* end mp_mul() */
return res;
}
- if(q)
+ if(q)
mp_zero(q);
return MP_OKAY;
SIGN(&rtmp) = MP_ZPOS;
/* Copy output, if it is needed */
- if(q)
+ if(q)
s_mp_exch(&qtmp, q);
- if(r)
+ if(r)
s_mp_exch(&rtmp, r);
CLEANUP:
/* Loop over bits of each non-maximal digit */
for(bit = 0; bit < DIGIT_BIT; bit++) {
if(d & 1) {
- if((res = s_mp_mul(&s, &x)) != MP_OKAY)
+ if((res = s_mp_mul(&s, &x)) != MP_OKAY)
goto CLEANUP;
}
d >>= 1;
-
+
if((res = s_mp_sqr(&x)) != MP_OKAY)
goto CLEANUP;
}
if((res = s_mp_sqr(&x)) != MP_OKAY)
goto CLEANUP;
}
-
+
if(mp_iseven(b))
SIGN(&s) = SIGN(a);
/*
If |a| > m, we need to divide to get the remainder and take the
- absolute value.
+ absolute value.
If |a| < m, we don't need to do any division, just copy and adjust
the sign (if a is negative).
if((mag = s_mp_cmp(a, m)) > 0) {
if((res = mp_div(a, m, NULL, c)) != MP_OKAY)
return res;
-
+
if(SIGN(c) == MP_NEG) {
if((res = mp_add(c, m, c)) != MP_OKAY)
return res;
return res;
}
-
+
} else {
mp_zero(c);
return MP_RANGE;
/* Special cases for zero and one, trivial */
- if(mp_cmp_d(a, 0) == MP_EQ || mp_cmp_d(a, 1) == MP_EQ)
+ if(mp_cmp_d(a, 0) == MP_EQ || mp_cmp_d(a, 1) == MP_EQ)
return mp_copy(a, b);
-
+
/* Initialize the temporaries we'll use below */
if((res = mp_init_size(&t, USED(a))) != MP_OKAY)
return res;
CLEANUP:
mp_clear(&x);
X:
- mp_clear(&t);
+ mp_clear(&t);
return res;
Compute c = (a ** b) mod m. Uses a standard square-and-multiply
method with modular reductions at each step. (This is basically the
same code as mp_expt(), except for the addition of the reductions)
-
+
The modular reductions are done using Barrett's algorithm (see
s_mp_reduce() below for details)
*/
mp_set(&s, 1);
/* mu = b^2k / m */
- s_mp_add_d(&mu, 1);
+ s_mp_add_d(&mu, 1);
s_mp_lshd(&mu, 2 * USED(m));
if((res = mp_div(&mu, m, &mu, NULL)) != MP_OKAY)
goto CLEANUP;
int out;
ARGCHK(a != NULL, MP_EQ);
-
+
mp_init(&tmp); mp_set_int(&tmp, z);
out = mp_cmp(a, &tmp);
mp_clear(&tmp);
if(mp_isodd(&u)) {
if((res = mp_copy(&v, &t)) != MP_OKAY)
goto CLEANUP;
-
+
/* t = -v */
if(SIGN(&v) == MP_ZPOS)
SIGN(&t) = MP_NEG;
else
SIGN(&t) = MP_ZPOS;
-
+
} else {
if((res = mp_copy(&u, &t)) != MP_OKAY)
goto CLEANUP;
if(y)
if((res = mp_copy(&D, y)) != MP_OKAY) goto CLEANUP;
-
+
if(g)
if((res = mp_mul(&gx, &v, g)) != MP_OKAY) goto CLEANUP;
/* {{{ mp_read_signed_bin(mp, str, len) */
-/*
+/*
mp_read_signed_bin(mp, str, len)
Read in a raw value (base 256) into the given mp_int
if((res = mp_add_d(mp, str[ix], mp)) != MP_OKAY)
return res;
}
-
+
return MP_OKAY;
-
+
} /* end mp_read_unsigned_bin() */
/* }}} */
/* {{{ mp_unsigned_bin_size(mp) */
-int mp_unsigned_bin_size(mp_int *mp)
+int mp_unsigned_bin_size(mp_int *mp)
{
mp_digit topdig;
int count;
}
return len;
-
+
} /* end mp_count_bits() */
/* }}} */
mp_err res;
mp_sign sig = MP_ZPOS;
- ARGCHK(mp != NULL && str != NULL && radix >= 2 && radix <= MAX_RADIX,
+ ARGCHK(mp != NULL && str != NULL && radix >= 2 && radix <= MAX_RADIX,
MP_BADARG);
mp_zero(mp);
/* Skip leading non-digit characters until a digit or '-' or '+' */
- while(str[ix] &&
- (s_mp_tovalue(str[ix], radix) < 0) &&
+ while(str[ix] &&
+ (s_mp_tovalue(str[ix], radix) < 0) &&
str[ix] != '-' &&
str[ix] != '+') {
++ix;
/* num = number of digits
qty = number of bits per digit
radix = target base
-
+
Return the number of digits in the specified radix that would be
needed to express 'num' digits of 'qty' bits each.
*/
++ix;
--pos;
}
-
+
mp_clear(&tmp);
}
/* {{{ s_mp_lshd(mp, p) */
-/*
+/*
Shift mp leftward by p digits, growing if needed, and zero-filling
the in-shifted digits at the right end. This is a convenient
alternative to multiplication by powers of the radix
- */
+ */
mp_err s_mp_lshd(mp_int *mp, mp_size p)
{
dp = DIGITS(mp);
/* Shift all the significant figures over as needed */
- for(ix = pos - p; ix >= 0; ix--)
+ for(ix = pos - p; ix >= 0; ix--)
dp[ix + p] = dp[ix];
/* Fill the bottom digits with zeroes */
/* {{{ s_mp_rshd(mp, p) */
-/*
+/*
Shift mp rightward by p digits. Maintains the invariant that
digits above the precision are all zero. Digits shifted off the
end are lost. Cannot fail.
end of the division process).
We multiply by the smallest power of 2 that gives us a leading digit
- at least half the radix. By choosing a power of 2, we simplify the
+ at least half the radix. By choosing a power of 2, we simplify the
multiplication and division steps to simple shifts.
*/
mp_digit s_mp_norm(mp_int *a, mp_int *b)
t <<= 1;
++d;
}
-
+
if(d != 0) {
s_mp_mul_2d(a, d);
s_mp_mul_2d(b, d);
test guarantees we have enough storage to do this safely.
*/
if(k) {
- dp[max] = k;
+ dp[max] = k;
USED(a) = max + 1;
}
s_mp_clamp(a);
return MP_OKAY;
-
+
} /* end s_mp_mul_d() */
/* }}} */
}
/* If we run out of 'b' digits before we're actually done, make
- sure the carries get propagated upward...
+ sure the carries get propagated upward...
*/
used = USED(a);
while(w && ix < used) {
/* Clobber any leading zeroes we created */
s_mp_clamp(a);
- /*
+ /*
If there was a borrow out, then |b| > |a| in violation
of our input invariant. We've already done the work,
but we'll at least complain about it...
s_mp_mod_2d(&q, (mp_digit)(DIGIT_BIT * (um + 1)));
#else
s_mp_mul_dig(&q, m, um + 1);
-#endif
+#endif
/* x = x - q */
if((res = mp_sub(x, &q, x)) != MP_OKAY)
pb = DIGITS(b);
for(ix = 0; ix < ub; ++ix, ++pb) {
- if(*pb == 0)
+ if(*pb == 0)
continue;
/* Inner product: Digits of a */
for(ix = 0; ix < len; ++ix, ++b) {
if(*b == 0)
continue;
-
+
pa = a;
for(jx = 0; jx < len; ++jx, ++pa) {
pt = out + ix + jx;
*/
for(jx = ix + 1, pa2 = DIGITS(a) + jx; jx < used; ++jx, ++pa2) {
mp_word u = 0, v;
-
+
/* Store this in a temporary to avoid indirections later */
pt = pbt + ix + jx;
v = *pt + k;
/* If we do not already have an overflow carry, check to see
- if the addition will cause one, and set the carry out if so
+ if the addition will cause one, and set the carry out if so
*/
u |= ((MP_WORD_MAX - v) < w);
/* If we are carrying out, propagate the carry to the next digit
in the output. This may cascade, so we have to be somewhat
circumspect -- but we will have enough precision in the output
- that we won't overflow
+ that we won't overflow
*/
kx = 1;
while(k) {
while(ix >= 0) {
/* Find a partial substring of a which is at least b */
while(s_mp_cmp(&rem, b) < 0 && ix >= 0) {
- if((res = s_mp_lshd(&rem, 1)) != MP_OKAY)
+ if((res = s_mp_lshd(&rem, 1)) != MP_OKAY)
goto CLEANUP;
if((res = s_mp_lshd(", 1)) != MP_OKAY)
}
/* If we didn't find one, we're finished dividing */
- if(s_mp_cmp(&rem, b) < 0)
- break;
+ if(s_mp_cmp(&rem, b) < 0)
+ break;
/* Compute a guess for the next quotient digit */
q = DIGIT(&rem, USED(&rem) - 1);
if((res = s_mp_mul_d(&t, q)) != MP_OKAY)
goto CLEANUP;
- /*
+ /*
If it's too big, back it off. We should not have to do this
more than once, or, in rare cases, twice. Knuth describes a
method by which this could be reduced to a maximum of once, but
}
/* Denormalize remainder */
- if(d != 0)
+ if(d != 0)
s_mp_div_2d(&rem, d);
s_mp_clamp(");
/* Copy quotient back to output */
s_mp_exch(", a);
-
+
/* Copy remainder back to output */
s_mp_exch(&rem, b);
mp_zero(a);
if((res = s_mp_pad(a, dig + 1)) != MP_OKAY)
return res;
-
+
DIGIT(a, dig) |= (1 << bit);
return MP_OKAY;
if(ua > 1)
return MP_GT;
- if(*ap < d)
+ if(*ap < d)
return MP_LT;
else if(*ap > d)
return MP_GT;
}
return ((uv - 1) * DIGIT_BIT) + extra;
- }
+ }
return -1;
int s_mp_tovalue(char ch, int r)
{
int val, xch;
-
+
if(r > 36)
xch = ch;
else
val = 62;
else if(xch == '/')
val = 63;
- else
+ else
return -1;
if(val < 0 || val >= r)
The results may be odd if you use a radix < 2 or > 64, you are
expected to know what you're doing.
*/
-
+
char s_mp_todigit(int val, int r, int low)
{
char ch;
/* {{{ s_mp_outlen(bits, radix) */
-/*
+/*
Return an estimate for how long a string is needed to hold a radix
r representation of a number with 'bits' significant bits.
git.samba.org / amitay / samba.git / blobdiff