mpi.c
by Michael J. Fromberger <sting@linguist.dartmouth.edu>
Copyright (C) 1998 Michael J. Fromberger
Arbitrary precision integer arithmetic library
SPDX-License-Identifier: Unlicense
$Id$
*/
#include "mpi.h"
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#if MP_DEBUG
#include <stdio.h>
#define DIAG(T,V) {fprintf(stderr,T);mp_print(V,stderr);fputc('\n',stderr);}
#else
#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.
*/
#if MP_LOGTAB
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 is used to compute output lengths for the mp_toradix()
function. Since a number n in radix r takes up about log_r(n)
digits, we estimate the output size by taking the least integer
greater than log_r(n), where:
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.
*/
#include "logtab.h"
#define LOG_V_2(R) s_logv_2[(R)]
#else
#include <math.h>
#define LOG_V_2(R) (log(2.0)/log(R))
#endif
static unsigned int s_mp_defprec = MP_DEFPREC;
When adding and multiplying digits, the results can be larger than
can be contained in an mp_digit. Thus, an mp_word is used. These
macros mask off the upper and lower digits of the mp_word (the
mp_word may be more than 2 mp_digits wide, but we only concern
ourselves with the low-order 2 mp_digits)
If your mp_word DOES have more than 2 mp_digits, you need to
uncomment the first line, and comment out the second.
*/
#define CARRYOUT(W) ((W)>>DIGIT_BIT)
#define ACCUM(W) ((W)&MP_DIGIT_MAX)
#define MP_LT -1
#define MP_EQ 0
#define MP_GT 1
static const char *mp_err_string[] = {
"unknown result code",
"boolean true",
"boolean false",
"out of memory",
"argument out of range",
"invalid input parameter",
"result is undefined"
};
static const char *s_dmap_1 =
"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";
#if 0
static const char *s_dmap_2 =
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
#endif
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
(although I hear C9x will ... about bloody time). At present, the
macro definitions are identical to the function bodies, but they'll
expand in place, instead of generating a function call.
I chose these particular functions to be made into macros because
some profiling showed they are called a lot on a typical workload,
and yet they are primarily housekeeping.
*/
#if MP_MACRO == 0
void s_mp_setz(mp_digit *dp, mp_size count);
void s_mp_copy(mp_digit *sp, mp_digit *dp, mp_size count);
void *s_mp_alloc(size_t nb, size_t ni);
void s_mp_free(void *ptr);
#else
of the MP_MEMSET and MP_MEMCPY configuration options...
*/
#if MP_MEMSET == 0
#define s_mp_setz(dp, count) \
{int ix;for(ix=0;ix<(count);ix++)(dp)[ix]=0;}
#else
#define s_mp_setz(dp, count) memset(dp, 0, (count) * sizeof(mp_digit))
#endif
#if MP_MEMCPY == 0
#define s_mp_copy(sp, dp, count) \
{int ix;for(ix=0;ix<(count);ix++)(dp)[ix]=(sp)[ix];}
#else
#define s_mp_copy(sp, dp, count) memcpy(dp, sp, (count) * sizeof(mp_digit))
#endif
#define s_mp_alloc(nb, ni) calloc(nb, ni)
#define s_mp_free(ptr) {if(ptr) free(ptr);}
#endif
mp_err s_mp_grow(mp_int *mp, mp_size min);
mp_err s_mp_pad(mp_int *mp, mp_size min);
void s_mp_clamp(mp_int *mp);
void s_mp_exch(mp_int *a, mp_int *b);
mp_err s_mp_lshd(mp_int *mp, mp_size p);
void s_mp_rshd(mp_int *mp, mp_size p);
void s_mp_div_2d(mp_int *mp, mp_digit d);
void s_mp_mod_2d(mp_int *mp, mp_digit d);
mp_err s_mp_mul_2d(mp_int *mp, mp_digit d);
void s_mp_div_2(mp_int *mp);
mp_err s_mp_mul_2(mp_int *mp);
mp_digit s_mp_norm(mp_int *a, mp_int *b);
mp_err s_mp_add_d(mp_int *mp, mp_digit d);
mp_err s_mp_sub_d(mp_int *mp, mp_digit d);
mp_err s_mp_mul_d(mp_int *mp, mp_digit d);
mp_err s_mp_div_d(mp_int *mp, mp_digit d, mp_digit *r);
mp_err s_mp_reduce(mp_int *x, mp_int *m, mp_int *mu);
mp_err s_mp_add(mp_int *a, mp_int *b);
mp_err s_mp_sub(mp_int *a, mp_int *b);
mp_err s_mp_mul(mp_int *a, mp_int *b);
#if 0
void s_mp_kmul(mp_digit *a, mp_digit *b, mp_digit *out, mp_size len);
#endif
#if MP_SQUARE
mp_err s_mp_sqr(mp_int *a);
#else
#define s_mp_sqr(a) s_mp_mul(a, a)
#endif
mp_err s_mp_div(mp_int *a, mp_int *b);
mp_err s_mp_2expt(mp_int *a, mp_digit k);
int s_mp_cmp(mp_int *a, mp_int *b);
int s_mp_cmp_d(mp_int *a, mp_digit d);
int s_mp_ispow2(mp_int *v);
int s_mp_ispow2d(mp_digit d);
int s_mp_tovalue(char ch, int r);
char s_mp_todigit(int val, int r, int low);
int s_mp_outlen(int bits, int r);
unsigned int mp_get_prec(void)
{
return s_mp_defprec;
}
void mp_set_prec(unsigned int prec)
{
if(prec == 0)
s_mp_defprec = MP_DEFPREC;
else
s_mp_defprec = prec;
}
mp_init(mp)
Initialize a new zero-valued mp_int. Returns MP_OKAY if successful,
MP_MEM if memory could not be allocated for the structure.
*/
mp_err mp_init(mp_int *mp)
{
return mp_init_size(mp, s_mp_defprec);
}
mp_err mp_init_array(mp_int mp[], int count)
{
mp_err res;
int pos;
ARGCHK(mp !=NULL && count > 0, MP_BADARG);
for(pos = 0; pos < count; ++pos) {
if((res = mp_init(&mp[pos])) != MP_OKAY)
goto CLEANUP;
}
return MP_OKAY;
CLEANUP:
while(--pos >= 0)
mp_clear(&mp[pos]);
return res;
}
mp_init_size(mp, prec)
Initialize a new zero-valued mp_int with at least the given
precision; returns MP_OKAY if successful, or MP_MEM if memory could
not be allocated for the structure.
*/
mp_err mp_init_size(mp_int *mp, mp_size prec)
{
ARGCHK(mp != NULL && prec > 0, MP_BADARG);
if((DIGITS(mp) = s_mp_alloc(prec, sizeof(mp_digit))) == NULL)
return MP_MEM;
SIGN(mp) = MP_ZPOS;
USED(mp) = 1;
ALLOC(mp) = prec;
return MP_OKAY;
}
mp_init_copy(mp, from)
Initialize mp as an exact copy of from. Returns MP_OKAY if
successful, MP_MEM if memory could not be allocated for the new
structure.
*/
mp_err mp_init_copy(mp_int *mp, mp_int *from)
{
ARGCHK(mp != NULL && from != NULL, MP_BADARG);
if(mp == from)
return MP_OKAY;
if((DIGITS(mp) = s_mp_alloc(USED(from), sizeof(mp_digit))) == NULL)
return MP_MEM;
s_mp_copy(DIGITS(from), DIGITS(mp), USED(from));
USED(mp) = USED(from);
ALLOC(mp) = USED(from);
SIGN(mp) = SIGN(from);
return MP_OKAY;
}
mp_copy(from, to)
Copies the mp_int 'from' to the mp_int 'to'. It is presumed that
'to' has already been initialized (if not, use mp_init_copy()
instead). If 'from' and 'to' are identical, nothing happens.
*/
mp_err mp_copy(mp_int *from, mp_int *to)
{
ARGCHK(from != NULL && to != NULL, MP_BADARG);
if(from == to)
return MP_OKAY;
{
mp_digit *tmp;
If the allocated buffer in 'to' already has enough space to hold
all the used digits of 'from', we'll re-use it to avoid hitting
the memory allocater more than necessary; otherwise, we'd have
to grow anyway, so we just allocate a hunk and make the copy as
usual
*/
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;
s_mp_copy(DIGITS(from), tmp, USED(from));
if(DIGITS(to) != NULL) {
#if MP_CRYPTO
s_mp_setz(DIGITS(to), ALLOC(to));
#endif
s_mp_free(DIGITS(to));
}
DIGITS(to) = tmp;
ALLOC(to) = USED(from);
}
USED(to) = USED(from);
SIGN(to) = SIGN(from);
}
return MP_OKAY;
}
mp_exch(mp1, mp2)
Exchange mp1 and mp2 without allocating any intermediate memory
(well, unless you count the stack space needed for this call and the
locals it creates...). This cannot fail.
*/
void mp_exch(mp_int *mp1, mp_int *mp2)
{
#if MP_ARGCHK == 2
assert(mp1 != NULL && mp2 != NULL);
#else
if(mp1 == NULL || mp2 == NULL)
return;
#endif
s_mp_exch(mp1, mp2);
}
mp_clear(mp)
Release the storage used by an mp_int, and void its fields so that
if someone calls mp_clear() again for the same int later, we won't
get tollchocked.
*/
void mp_clear(mp_int *mp)
{
if(mp == NULL)
return;
if(DIGITS(mp) != NULL) {
#if MP_CRYPTO
s_mp_setz(DIGITS(mp), ALLOC(mp));
#endif
s_mp_free(DIGITS(mp));
DIGITS(mp) = NULL;
}
USED(mp) = 0;
ALLOC(mp) = 0;
}
void mp_clear_array(mp_int mp[], int count)
{
ARGCHK(mp != NULL && count > 0, MP_BADARG);
while(--count >= 0)
mp_clear(&mp[count]);
}
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)
*/
void mp_zero(mp_int *mp)
{
if(mp == NULL)
return;
s_mp_setz(DIGITS(mp), ALLOC(mp));
USED(mp) = 1;
SIGN(mp) = MP_ZPOS;
}
void mp_set(mp_int *mp, mp_digit d)
{
if(mp == NULL)
return;
mp_zero(mp);
DIGIT(mp, 0) = d;
}
mp_err mp_set_int(mp_int *mp, long z)
{
int ix;
unsigned long v = labs(z);
mp_err res;
ARGCHK(mp != NULL, MP_BADARG);
mp_zero(mp);
if(z == 0)
return MP_OKAY;
for(ix = sizeof(long) - 1; ix >= 0; ix--) {
if((res = s_mp_mul_2d(mp, CHAR_BIT)) != MP_OKAY)
return res;
res = s_mp_add_d(mp,
(mp_digit)((v >> (ix * CHAR_BIT)) & UCHAR_MAX));
if(res != MP_OKAY)
return res;
}
if(z < 0)
SIGN(mp) = MP_NEG;
return MP_OKAY;
}
mp_add_d(a, d, b)
Compute the sum b = a + d, for a single digit d. Respects the sign of
its primary addend (single digits are unsigned anyway).
*/
mp_err mp_add_d(mp_int *a, mp_digit d, mp_int *b)
{
mp_err res = MP_OKAY;
ARGCHK(a != NULL && b != NULL, MP_BADARG);
if((res = mp_copy(a, b)) != MP_OKAY)
return res;
if(SIGN(b) == MP_ZPOS) {
res = s_mp_add_d(b, d);
} else if(s_mp_cmp_d(b, d) >= 0) {
res = s_mp_sub_d(b, d);
} else {
SIGN(b) = MP_ZPOS;
DIGIT(b, 0) = d - DIGIT(b, 0);
}
return res;
}
mp_sub_d(a, d, b)
Compute the difference b = a - d, for a single digit d. Respects the
sign of its subtrahend (single digits are unsigned anyway).
*/
mp_err mp_sub_d(mp_int *a, mp_digit d, mp_int *b)
{
mp_err res;
ARGCHK(a != NULL && b != NULL, MP_BADARG);
if((res = mp_copy(a, b)) != MP_OKAY)
return res;
if(SIGN(b) == MP_NEG) {
if((res = s_mp_add_d(b, d)) != MP_OKAY)
return res;
} else if(s_mp_cmp_d(b, d) >= 0) {
if((res = s_mp_sub_d(b, d)) != MP_OKAY)
return res;
} else {
mp_neg(b, b);
DIGIT(b, 0) = d - DIGIT(b, 0);
SIGN(b) = MP_NEG;
}
if(s_mp_cmp_d(b, 0) == 0)
SIGN(b) = MP_ZPOS;
return MP_OKAY;
}
mp_mul_d(a, d, b)
Compute the product b = a * d, for a single digit d. Respects the sign
of its multiplicand (single digits are unsigned anyway)
*/
mp_err mp_mul_d(mp_int *a, mp_digit d, mp_int *b)
{
mp_err res;
ARGCHK(a != NULL && b != NULL, MP_BADARG);
if(d == 0) {
mp_zero(b);
return MP_OKAY;
}
if((res = mp_copy(a, b)) != MP_OKAY)
return res;
res = s_mp_mul_d(b, d);
return res;
}
mp_err mp_mul_2(mp_int *a, mp_int *c)
{
mp_err res;
ARGCHK(a != NULL && c != NULL, MP_BADARG);
if((res = mp_copy(a, c)) != MP_OKAY)
return res;
return s_mp_mul_2(c);
}
mp_div_d(a, d, q, r)
Compute the quotient q = a / d and remainder r = a mod d, for a
single digit d. Respects the sign of its divisor (single digits are
unsigned anyway).
*/
mp_err mp_div_d(mp_int *a, mp_digit d, mp_int *q, mp_digit *r)
{
mp_err res;
mp_digit rem;
int pow;
ARGCHK(a != NULL, MP_BADARG);
if(d == 0)
return MP_RANGE;
if((pow = s_mp_ispow2d(d)) >= 0) {
mp_digit mask;
mask = (1 << pow) - 1;
rem = DIGIT(a, 0) & mask;
if(q) {
mp_copy(a, q);
s_mp_div_2d(q, pow);
}
if(r)
*r = rem;
return MP_OKAY;
}
If the quotient is actually going to be returned, we'll try to
avoid hitting the memory allocator by copying the dividend into it
and doing the division there. This can't be any _worse_ than
always copying, and will sometimes be better (since it won't make
another copy)
If it's not going to be returned, we need to allocate a temporary
to hold the quotient, which will just be discarded.
*/
if(q) {
if((res = mp_copy(a, q)) != MP_OKAY)
return res;
res = s_mp_div_d(q, d, &rem);
if(s_mp_cmp_d(q, 0) == MP_EQ)
SIGN(q) = MP_ZPOS;
} else {
mp_int qp;
if((res = mp_init_copy(&qp, a)) != MP_OKAY)
return res;
res = s_mp_div_d(&qp, d, &rem);
if(s_mp_cmp_d(&qp, 0) == 0)
SIGN(&qp) = MP_ZPOS;
mp_clear(&qp);
}
if(r)
*r = rem;
return res;
}
mp_div_2(a, c)
Compute c = a / 2, disregarding the remainder.
*/
mp_err mp_div_2(mp_int *a, mp_int *c)
{
mp_err res;
ARGCHK(a != NULL && c != NULL, MP_BADARG);
if((res = mp_copy(a, c)) != MP_OKAY)
return res;
s_mp_div_2(c);
return MP_OKAY;
}
mp_err mp_expt_d(mp_int *a, mp_digit d, mp_int *c)
{
mp_int s, x;
mp_err res;
ARGCHK(a != NULL && c != NULL, MP_BADARG);
if((res = mp_init(&s)) != MP_OKAY)
return res;
if((res = mp_init_copy(&x, a)) != MP_OKAY)
goto X;
DIGIT(&s, 0) = 1;
while(d != 0) {
if(d & 1) {
if((res = s_mp_mul(&s, &x)) != MP_OKAY)
goto CLEANUP;
}
d >>= 1;
if((res = s_mp_sqr(&x)) != MP_OKAY)
goto CLEANUP;
}
s_mp_exch(&s, c);
CLEANUP:
mp_clear(&x);
X:
mp_clear(&s);
return res;
}
mp_abs(a, b)
Compute b = |a|. 'a' and 'b' may be identical.
*/
mp_err mp_abs(mp_int *a, mp_int *b)
{
mp_err res;
ARGCHK(a != NULL && b != NULL, MP_BADARG);
if((res = mp_copy(a, b)) != MP_OKAY)
return res;
SIGN(b) = MP_ZPOS;
return MP_OKAY;
}
mp_neg(a, b)
Compute b = -a. 'a' and 'b' may be identical.
*/
mp_err mp_neg(mp_int *a, mp_int *b)
{
mp_err res;
ARGCHK(a != NULL && b != NULL, MP_BADARG);
if((res = mp_copy(a, b)) != MP_OKAY)
return res;
if(s_mp_cmp_d(b, 0) == MP_EQ)
SIGN(b) = MP_ZPOS;
else
SIGN(b) = (SIGN(b) == MP_NEG) ? MP_ZPOS : MP_NEG;
return MP_OKAY;
}
mp_add(a, b, c)
Compute c = a + b. All parameters may be identical.
*/
mp_err mp_add(mp_int *a, mp_int *b, mp_int *c)
{
mp_err res;
int cmp;
ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
if(SIGN(a) == SIGN(b)) {
so we avoid having to use a temporary even if the result
is supposed to replace the output
*/
if(c == b) {
if((res = s_mp_add(c, a)) != MP_OKAY)
return res;
} else {
if(c != a && (res = mp_copy(a, c)) != MP_OKAY)
return res;
if((res = s_mp_add(c, b)) != MP_OKAY)
return res;
}
} else if((cmp = s_mp_cmp(a, b)) > 0) {
variable; otherwise, we'll do it without touching the memory
allocator at all, if possible
*/
if(c == b) {
mp_int tmp;
if((res = mp_init_copy(&tmp, a)) != MP_OKAY)
return res;
if((res = s_mp_sub(&tmp, b)) != MP_OKAY) {
mp_clear(&tmp);
return res;
}
s_mp_exch(&tmp, c);
mp_clear(&tmp);
} else {
if(c != a && (res = mp_copy(a, c)) != MP_OKAY)
return res;
if((res = s_mp_sub(c, b)) != MP_OKAY)
return res;
}
} else if(cmp == 0) {
mp_zero(c);
return MP_OKAY;
} else {
if(c == a) {
mp_int tmp;
if((res = mp_init_copy(&tmp, b)) != MP_OKAY)
return res;
if((res = s_mp_sub(&tmp, a)) != MP_OKAY) {
mp_clear(&tmp);
return res;
}
s_mp_exch(&tmp, c);
mp_clear(&tmp);
} else {
if(c != b && (res = mp_copy(b, c)) != MP_OKAY)
return res;
if((res = s_mp_sub(c, a)) != MP_OKAY)
return res;
}
}
if(USED(c) == 1 && DIGIT(c, 0) == 0)
SIGN(c) = MP_ZPOS;
return MP_OKAY;
}
mp_sub(a, b, c)
Compute c = a - b. All parameters may be identical.
*/
mp_err mp_sub(mp_int *a, mp_int *b, mp_int *c)
{
mp_err res;
int cmp;
ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
if(SIGN(a) != SIGN(b)) {
if(c == a) {
if((res = s_mp_add(c, b)) != MP_OKAY)
return res;
} else {
if(c != b && ((res = mp_copy(b, c)) != MP_OKAY))
return res;
if((res = s_mp_add(c, a)) != MP_OKAY)
return res;
SIGN(c) = SIGN(a);
}
} else if((cmp = s_mp_cmp(a, b)) > 0) {
if(c == b) {
mp_int tmp;
if((res = mp_init_copy(&tmp, a)) != MP_OKAY)
return res;
if((res = s_mp_sub(&tmp, b)) != MP_OKAY) {
mp_clear(&tmp);
return res;
}
s_mp_exch(&tmp, c);
mp_clear(&tmp);
} else {
if(c != a && ((res = mp_copy(a, c)) != MP_OKAY))
return res;
if((res = s_mp_sub(c, b)) != MP_OKAY)
return res;
}
} else if(cmp == 0) {
mp_zero(c);
return MP_OKAY;
} else {
if(c == a) {
mp_int tmp;
if((res = mp_init_copy(&tmp, b)) != MP_OKAY)
return res;
if((res = s_mp_sub(&tmp, a)) != MP_OKAY) {
mp_clear(&tmp);
return res;
}
s_mp_exch(&tmp, c);
mp_clear(&tmp);
} else {
if(c != b && ((res = mp_copy(b, c)) != MP_OKAY))
return res;
if((res = s_mp_sub(c, a)) != MP_OKAY)
return res;
}
SIGN(c) = !SIGN(b);
}
if(USED(c) == 1 && DIGIT(c, 0) == 0)
SIGN(c) = MP_ZPOS;
return MP_OKAY;
}
mp_mul(a, b, c)
Compute c = a * b. All parameters may be identical.
*/
mp_err mp_mul(mp_int *a, mp_int *b, mp_int *c)
{
mp_err res;
mp_sign sgn;
ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
sgn = (SIGN(a) == SIGN(b)) ? MP_ZPOS : MP_NEG;
if(c == b) {
if((res = s_mp_mul(c, a)) != MP_OKAY)
return res;
} else {
if((res = mp_copy(a, c)) != MP_OKAY)
return res;
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;
}
mp_mul_2d(a, d, c)
Compute c = a * 2^d. a may be the same as c.
*/
mp_err mp_mul_2d(mp_int *a, mp_digit d, mp_int *c)
{
mp_err res;
ARGCHK(a != NULL && c != NULL, MP_BADARG);
if((res = mp_copy(a, c)) != MP_OKAY)
return res;
if(d == 0)
return MP_OKAY;
return s_mp_mul_2d(c, d);
}
#if MP_SQUARE
mp_err mp_sqr(mp_int *a, mp_int *b)
{
mp_err res;
ARGCHK(a != NULL && b != NULL, MP_BADARG);
if((res = mp_copy(a, b)) != MP_OKAY)
return res;
if((res = s_mp_sqr(b)) != MP_OKAY)
return res;
SIGN(b) = MP_ZPOS;
return MP_OKAY;
}
#endif
mp_div(a, b, q, r)
Compute q = a / b and r = a mod b. Input parameters may be re-used
as output parameters. If q or r is NULL, that portion of the
computation will be discarded (although it will still be computed)
Pay no attention to the hacker behind the curtain.
*/
mp_err mp_div(mp_int *a, mp_int *b, mp_int *q, mp_int *r)
{
mp_err res;
mp_int qtmp, rtmp;
int cmp;
ARGCHK(a != NULL && b != NULL, MP_BADARG);
if(mp_cmp_z(b) == MP_EQ)
return MP_RANGE;
avoid any memory allocation
*/
if((cmp = s_mp_cmp(a, b)) < 0) {
if(r) {
if((res = mp_copy(a, r)) != MP_OKAY)
return res;
}
if(q)
mp_zero(q);
return MP_OKAY;
} else if(cmp == 0) {
if(q) {
int qneg = (SIGN(a) != SIGN(b));
mp_set(q, 1);
if(qneg)
SIGN(q) = MP_NEG;
}
if(r)
mp_zero(r);
return MP_OKAY;
}
if((res = mp_init_copy(&qtmp, a)) != MP_OKAY)
return res;
if((res = mp_init_copy(&rtmp, b)) != MP_OKAY)
goto CLEANUP;
if((res = s_mp_div(&qtmp, &rtmp)) != MP_OKAY)
goto CLEANUP;
SIGN(&rtmp) = SIGN(a);
if(SIGN(a) == SIGN(b))
SIGN(&qtmp) = MP_ZPOS;
else
SIGN(&qtmp) = MP_NEG;
if(s_mp_cmp_d(&qtmp, 0) == MP_EQ)
SIGN(&qtmp) = MP_ZPOS;
if(s_mp_cmp_d(&rtmp, 0) == MP_EQ)
SIGN(&rtmp) = MP_ZPOS;
if(q)
s_mp_exch(&qtmp, q);
if(r)
s_mp_exch(&rtmp, r);
CLEANUP:
mp_clear(&rtmp);
mp_clear(&qtmp);
return res;
}
mp_err mp_div_2d(mp_int *a, mp_digit d, mp_int *q, mp_int *r)
{
mp_err res;
ARGCHK(a != NULL, MP_BADARG);
if(q) {
if((res = mp_copy(a, q)) != MP_OKAY)
return res;
s_mp_div_2d(q, d);
}
if(r) {
if((res = mp_copy(a, r)) != MP_OKAY)
return res;
s_mp_mod_2d(r, d);
}
return MP_OKAY;
}
mp_expt(a, b, c)
Compute c = a ** b, that is, raise a to the b power. Uses a
standard iterative square-and-multiply technique.
*/
mp_err mp_expt(mp_int *a, mp_int *b, mp_int *c)
{
mp_int s, x;
mp_err res;
mp_digit d;
unsigned int bit, dig;
ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
if(mp_cmp_z(b) < 0)
return MP_RANGE;
if((res = mp_init(&s)) != MP_OKAY)
return res;
mp_set(&s, 1);
if((res = mp_init_copy(&x, a)) != MP_OKAY)
goto X;
for(dig = 0; dig < (USED(b) - 1); dig++) {
d = DIGIT(b, dig);
for(bit = 0; bit < DIGIT_BIT; bit++) {
if(d & 1) {
if((res = s_mp_mul(&s, &x)) != MP_OKAY)
goto CLEANUP;
}
d >>= 1;
if((res = s_mp_sqr(&x)) != MP_OKAY)
goto CLEANUP;
}
}
d = DIGIT(b, dig);
while(d) {
if(d & 1) {
if((res = s_mp_mul(&s, &x)) != MP_OKAY)
goto CLEANUP;
}
d >>= 1;
if((res = s_mp_sqr(&x)) != MP_OKAY)
goto CLEANUP;
}
if(mp_iseven(b))
SIGN(&s) = SIGN(a);
res = mp_copy(&s, c);
CLEANUP:
mp_clear(&x);
X:
mp_clear(&s);
return res;
}
mp_err mp_2expt(mp_int *a, mp_digit k)
{
ARGCHK(a != NULL, MP_BADARG);
return s_mp_2expt(a, k);
}
mp_mod(a, m, c)
Compute c = a (mod m). Result will always be 0 <= c < m.
*/
mp_err mp_mod(mp_int *a, mp_int *m, mp_int *c)
{
mp_err res;
int mag;
ARGCHK(a != NULL && m != NULL && c != NULL, MP_BADARG);
if(SIGN(m) == MP_NEG)
return MP_RANGE;
If |a| > m, we need to divide to get the remainder and take the
absolute value.
If |a| < m, we don't need to do any division, just copy and adjust
the sign (if a is negative).
If |a| == m, we can simply set the result to zero.
This order is intended to minimize the average path length of the
comparison chain on common workloads -- the most frequent cases are
that |a| != m, so we do those first.
*/
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;
}
} else if(mag < 0) {
if((res = mp_copy(a, c)) != MP_OKAY)
return res;
if(mp_cmp_z(a) < 0) {
if((res = mp_add(c, m, c)) != MP_OKAY)
return res;
}
} else {
mp_zero(c);
}
return MP_OKAY;
}
mp_mod_d(a, d, c)
Compute c = a (mod d). Result will always be 0 <= c < d
*/
mp_err mp_mod_d(mp_int *a, mp_digit d, mp_digit *c)
{
mp_err res;
mp_digit rem;
ARGCHK(a != NULL && c != NULL, MP_BADARG);
if(s_mp_cmp_d(a, d) > 0) {
if((res = mp_div_d(a, d, NULL, &rem)) != MP_OKAY)
return res;
} else {
if(SIGN(a) == MP_NEG)
rem = d - DIGIT(a, 0);
else
rem = DIGIT(a, 0);
}
if(c)
*c = rem;
return MP_OKAY;
}
mp_sqrt(a, b)
Compute the integer square root of a, and store the result in b.
Uses an integer-arithmetic version of Newton's iterative linear
approximation technique to determine this value; the result has the
following two properties:
b^2 <= a
(b+1)^2 >= a
It is a range error to pass a negative value.
*/
mp_err mp_sqrt(mp_int *a, mp_int *b)
{
mp_int x, t;
mp_err res;
ARGCHK(a != NULL && b != NULL, MP_BADARG);
if(SIGN(a) == MP_NEG)
return MP_RANGE;
if(mp_cmp_d(a, 0) == MP_EQ || mp_cmp_d(a, 1) == MP_EQ)
return mp_copy(a, b);
if((res = mp_init_size(&t, USED(a))) != MP_OKAY)
return res;
if((res = mp_init_copy(&x, a)) != MP_OKAY)
goto X;
s_mp_rshd(&x, (USED(&x)/2)+1);
mp_add_d(&x, 1, &x);
for(;;) {
mp_copy(&x, &t);
if((res = mp_sqr(&t, &t)) != MP_OKAY ||
(res = mp_sub(&t, a, &t)) != MP_OKAY)
goto CLEANUP;
s_mp_mul_2(&x);
if((res = mp_div(&t, &x, &t, NULL)) != MP_OKAY)
goto CLEANUP;
s_mp_div_2(&x);
if(mp_cmp_z(&t) == MP_EQ)
break;
if((res = mp_sub(&x, &t, &x)) != MP_OKAY)
goto CLEANUP;
}
mp_sub_d(&x, 1, &x);
s_mp_exch(&x, b);
CLEANUP:
mp_clear(&x);
X:
mp_clear(&t);
return res;
}
#if MP_MODARITH
mp_addmod(a, b, m, c)
Compute c = (a + b) mod m
*/
mp_err mp_addmod(mp_int *a, mp_int *b, mp_int *m, mp_int *c)
{
mp_err res;
ARGCHK(a != NULL && b != NULL && m != NULL && c != NULL, MP_BADARG);
if((res = mp_add(a, b, c)) != MP_OKAY)
return res;
if((res = mp_mod(c, m, c)) != MP_OKAY)
return res;
return MP_OKAY;
}
mp_submod(a, b, m, c)
Compute c = (a - b) mod m
*/
mp_err mp_submod(mp_int *a, mp_int *b, mp_int *m, mp_int *c)
{
mp_err res;
ARGCHK(a != NULL && b != NULL && m != NULL && c != NULL, MP_BADARG);
if((res = mp_sub(a, b, c)) != MP_OKAY)
return res;
if((res = mp_mod(c, m, c)) != MP_OKAY)
return res;
return MP_OKAY;
}
mp_mulmod(a, b, m, c)
Compute c = (a * b) mod m
*/
mp_err mp_mulmod(mp_int *a, mp_int *b, mp_int *m, mp_int *c)
{
mp_err res;
ARGCHK(a != NULL && b != NULL && m != NULL && c != NULL, MP_BADARG);
if((res = mp_mul(a, b, c)) != MP_OKAY)
return res;
if((res = mp_mod(c, m, c)) != MP_OKAY)
return res;
return MP_OKAY;
}
#if MP_SQUARE
mp_err mp_sqrmod(mp_int *a, mp_int *m, mp_int *c)
{
mp_err res;
ARGCHK(a != NULL && m != NULL && c != NULL, MP_BADARG);
if((res = mp_sqr(a, c)) != MP_OKAY)
return res;
if((res = mp_mod(c, m, c)) != MP_OKAY)
return res;
return MP_OKAY;
}
#endif
mp_exptmod(a, b, m, c)
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_err mp_exptmod(mp_int *a, mp_int *b, mp_int *m, mp_int *c)
{
mp_int s, x, mu;
mp_err res;
mp_digit d, *db = DIGITS(b);
mp_size ub = USED(b);
unsigned int bit, dig;
ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
if(mp_cmp_z(b) < 0 || mp_cmp_z(m) <= 0)
return MP_RANGE;
if((res = mp_init(&s)) != MP_OKAY)
return res;
if((res = mp_init_copy(&x, a)) != MP_OKAY)
goto X;
if((res = mp_mod(&x, m, &x)) != MP_OKAY ||
(res = mp_init(&mu)) != MP_OKAY)
goto MU;
mp_set(&s, 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;
for(dig = 0; dig < (ub - 1); dig++) {
d = *db++;
for(bit = 0; bit < DIGIT_BIT; bit++) {
if(d & 1) {
if((res = s_mp_mul(&s, &x)) != MP_OKAY)
goto CLEANUP;
if((res = s_mp_reduce(&s, m, &mu)) != MP_OKAY)
goto CLEANUP;
}
d >>= 1;
if((res = s_mp_sqr(&x)) != MP_OKAY)
goto CLEANUP;
if((res = s_mp_reduce(&x, m, &mu)) != MP_OKAY)
goto CLEANUP;
}
}
d = *db;
while(d) {
if(d & 1) {
if((res = s_mp_mul(&s, &x)) != MP_OKAY)
goto CLEANUP;
if((res = s_mp_reduce(&s, m, &mu)) != MP_OKAY)
goto CLEANUP;
}
d >>= 1;
if((res = s_mp_sqr(&x)) != MP_OKAY)
goto CLEANUP;
if((res = s_mp_reduce(&x, m, &mu)) != MP_OKAY)
goto CLEANUP;
}
s_mp_exch(&s, c);
CLEANUP:
mp_clear(&mu);
MU:
mp_clear(&x);
X:
mp_clear(&s);
return res;
}
mp_err mp_exptmod_d(mp_int *a, mp_digit d, mp_int *m, mp_int *c)
{
mp_int s, x;
mp_err res;
ARGCHK(a != NULL && c != NULL, MP_BADARG);
if((res = mp_init(&s)) != MP_OKAY)
return res;
if((res = mp_init_copy(&x, a)) != MP_OKAY)
goto X;
mp_set(&s, 1);
while(d != 0) {
if(d & 1) {
if((res = s_mp_mul(&s, &x)) != MP_OKAY ||
(res = mp_mod(&s, m, &s)) != MP_OKAY)
goto CLEANUP;
}
d /= 2;
if((res = s_mp_sqr(&x)) != MP_OKAY ||
(res = mp_mod(&x, m, &x)) != MP_OKAY)
goto CLEANUP;
}
s_mp_exch(&s, c);
CLEANUP:
mp_clear(&x);
X:
mp_clear(&s);
return res;
}
#endif
mp_cmp_z(a)
Compare a <=> 0. Returns <0 if a<0, 0 if a=0, >0 if a>0.
*/
int mp_cmp_z(mp_int *a)
{
if(SIGN(a) == MP_NEG)
return MP_LT;
else if(USED(a) == 1 && DIGIT(a, 0) == 0)
return MP_EQ;
else
return MP_GT;
}
mp_cmp_d(a, d)
Compare a <=> d. Returns <0 if a<d, 0 if a=d, >0 if a>d
*/
int mp_cmp_d(mp_int *a, mp_digit d)
{
ARGCHK(a != NULL, MP_EQ);
if(SIGN(a) == MP_NEG)
return MP_LT;
return s_mp_cmp_d(a, d);
}
int mp_cmp(mp_int *a, mp_int *b)
{
ARGCHK(a != NULL && b != NULL, MP_EQ);
if(SIGN(a) == SIGN(b)) {
int mag;
if((mag = s_mp_cmp(a, b)) == MP_EQ)
return MP_EQ;
if(SIGN(a) == MP_ZPOS)
return mag;
else
return -mag;
} else if(SIGN(a) == MP_ZPOS) {
return MP_GT;
} else {
return MP_LT;
}
}
mp_cmp_mag(a, b)
Compares |a| <=> |b|, and returns an appropriate comparison result
*/
int mp_cmp_mag(mp_int *a, mp_int *b)
{
ARGCHK(a != NULL && b != NULL, MP_EQ);
return s_mp_cmp(a, b);
}
This just converts z to an mp_int, and uses the existing comparison
routines. This is sort of inefficient, but it's not clear to me how
frequently this wil get used anyway. For small positive constants,
you can always use mp_cmp_d(), and for zero, there is mp_cmp_z().
*/
int mp_cmp_int(mp_int *a, long z)
{
mp_int tmp;
int out;
ARGCHK(a != NULL, MP_EQ);
mp_init(&tmp); mp_set_int(&tmp, z);
out = mp_cmp(a, &tmp);
mp_clear(&tmp);
return out;
}
mp_isodd(a)
Returns a true (non-zero) value if a is odd, false (zero) otherwise.
*/
int mp_isodd(mp_int *a)
{
ARGCHK(a != NULL, 0);
return (DIGIT(a, 0) & 1);
}
int mp_iseven(mp_int *a)
{
return !mp_isodd(a);
}
#if MP_NUMTH
Like the old mp_gcd() function, except computes the GCD using the
binary algorithm due to Josef Stein in 1961 (via Knuth).
*/
mp_err mp_gcd(mp_int *a, mp_int *b, mp_int *c)
{
mp_err res;
mp_int u, v, t;
mp_size k = 0;
ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
if(mp_cmp_z(a) == MP_EQ && mp_cmp_z(b) == MP_EQ)
return MP_RANGE;
if(mp_cmp_z(a) == MP_EQ) {
return mp_copy(b, c);
} else if(mp_cmp_z(b) == MP_EQ) {
return mp_copy(a, c);
}
if((res = mp_init(&t)) != MP_OKAY)
return res;
if((res = mp_init_copy(&u, a)) != MP_OKAY)
goto U;
if((res = mp_init_copy(&v, b)) != MP_OKAY)
goto V;
SIGN(&u) = MP_ZPOS;
SIGN(&v) = MP_ZPOS;
while(mp_iseven(&u) && mp_iseven(&v)) {
s_mp_div_2(&u);
s_mp_div_2(&v);
++k;
}
if(mp_isodd(&u)) {
if((res = mp_copy(&v, &t)) != MP_OKAY)
goto CLEANUP;
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;
}
for(;;) {
while(mp_iseven(&t)) {
s_mp_div_2(&t);
}
if(mp_cmp_z(&t) == MP_GT) {
if((res = mp_copy(&t, &u)) != MP_OKAY)
goto CLEANUP;
} else {
if((res = mp_copy(&t, &v)) != MP_OKAY)
goto CLEANUP;
if(SIGN(&t) == MP_ZPOS)
SIGN(&v) = MP_NEG;
else
SIGN(&v) = MP_ZPOS;
}
if((res = mp_sub(&u, &v, &t)) != MP_OKAY)
goto CLEANUP;
if(s_mp_cmp_d(&t, 0) == MP_EQ)
break;
}
s_mp_2expt(&v, k);
res = mp_mul(&u, &v, c);
CLEANUP:
mp_clear(&v);
V:
mp_clear(&u);
U:
mp_clear(&t);
return res;
}
ab = [a, b](a, b)
... by computing the product, and dividing out the gcd.
*/
mp_err mp_lcm(mp_int *a, mp_int *b, mp_int *c)
{
mp_int gcd, prod;
mp_err res;
ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
if((res = mp_init(&gcd)) != MP_OKAY)
return res;
if((res = mp_init(&prod)) != MP_OKAY)
goto GCD;
if((res = mp_mul(a, b, &prod)) != MP_OKAY)
goto CLEANUP;
if((res = mp_gcd(a, b, &gcd)) != MP_OKAY)
goto CLEANUP;
res = mp_div(&prod, &gcd, c, NULL);
CLEANUP:
mp_clear(&prod);
GCD:
mp_clear(&gcd);
return res;
}
mp_xgcd(a, b, g, x, y)
Compute g = (a, b) and values x and y satisfying Bezout's identity
(that is, ax + by = g). This uses the extended binary GCD algorithm
based on the Stein algorithm used for mp_gcd()
*/
mp_err mp_xgcd(mp_int *a, mp_int *b, mp_int *g, mp_int *x, mp_int *y)
{
mp_int gx, xc, yc, u, v, A, B, C, D;
mp_int *clean[9];
mp_err res;
int last = -1;
if(mp_cmp_z(b) == 0)
return MP_RANGE;
if((res = mp_init(&u)) != MP_OKAY) goto CLEANUP;
clean[++last] = &u;
if((res = mp_init(&v)) != MP_OKAY) goto CLEANUP;
clean[++last] = &v;
if((res = mp_init(&gx)) != MP_OKAY) goto CLEANUP;
clean[++last] = &gx;
if((res = mp_init(&A)) != MP_OKAY) goto CLEANUP;
clean[++last] = &A;
if((res = mp_init(&B)) != MP_OKAY) goto CLEANUP;
clean[++last] = &B;
if((res = mp_init(&C)) != MP_OKAY) goto CLEANUP;
clean[++last] = &C;
if((res = mp_init(&D)) != MP_OKAY) goto CLEANUP;
clean[++last] = &D;
if((res = mp_init_copy(&xc, a)) != MP_OKAY) goto CLEANUP;
clean[++last] = &xc;
mp_abs(&xc, &xc);
if((res = mp_init_copy(&yc, b)) != MP_OKAY) goto CLEANUP;
clean[++last] = &yc;
mp_abs(&yc, &yc);
mp_set(&gx, 1);
while(mp_iseven(&xc) && mp_iseven(&yc)) {
s_mp_div_2(&xc);
s_mp_div_2(&yc);
if((res = s_mp_mul_2(&gx)) != MP_OKAY)
goto CLEANUP;
}
mp_copy(&xc, &u);
mp_copy(&yc, &v);
mp_set(&A, 1); mp_set(&D, 1);
for(;;) {
while(mp_iseven(&u)) {
s_mp_div_2(&u);
if(mp_iseven(&A) && mp_iseven(&B)) {
s_mp_div_2(&A); s_mp_div_2(&B);
} else {
if((res = mp_add(&A, &yc, &A)) != MP_OKAY) goto CLEANUP;
s_mp_div_2(&A);
if((res = mp_sub(&B, &xc, &B)) != MP_OKAY) goto CLEANUP;
s_mp_div_2(&B);
}
}
while(mp_iseven(&v)) {
s_mp_div_2(&v);
if(mp_iseven(&C) && mp_iseven(&D)) {
s_mp_div_2(&C); s_mp_div_2(&D);
} else {
if((res = mp_add(&C, &yc, &C)) != MP_OKAY) goto CLEANUP;
s_mp_div_2(&C);
if((res = mp_sub(&D, &xc, &D)) != MP_OKAY) goto CLEANUP;
s_mp_div_2(&D);
}
}
if(mp_cmp(&u, &v) >= 0) {
if((res = mp_sub(&u, &v, &u)) != MP_OKAY) goto CLEANUP;
if((res = mp_sub(&A, &C, &A)) != MP_OKAY) goto CLEANUP;
if((res = mp_sub(&B, &D, &B)) != MP_OKAY) goto CLEANUP;
} else {
if((res = mp_sub(&v, &u, &v)) != MP_OKAY) goto CLEANUP;
if((res = mp_sub(&C, &A, &C)) != MP_OKAY) goto CLEANUP;
if((res = mp_sub(&D, &B, &D)) != MP_OKAY) goto CLEANUP;
}
if(mp_cmp_z(&u) == 0) {
if(x)
if((res = mp_copy(&C, x)) != 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;
break;
}
}
CLEANUP:
while(last >= 0)
mp_clear(clean[last--]);
return res;
}
mp_invmod(a, m, c)
Compute c = a^-1 (mod m), if there is an inverse for a (mod m).
This is equivalent to the question of whether (a, m) = 1. If not,
MP_UNDEF is returned, and there is no inverse.
*/
mp_err mp_invmod(mp_int *a, mp_int *m, mp_int *c)
{
mp_int g, x;
mp_err res;
ARGCHK(a && m && c, MP_BADARG);
if(mp_cmp_z(a) == 0 || mp_cmp_z(m) == 0)
return MP_RANGE;
if((res = mp_init(&g)) != MP_OKAY)
return res;
if((res = mp_init(&x)) != MP_OKAY)
goto X;
if((res = mp_xgcd(a, m, &g, &x, NULL)) != MP_OKAY)
goto CLEANUP;
if(mp_cmp_d(&g, 1) != MP_EQ) {
res = MP_UNDEF;
goto CLEANUP;
}
res = mp_mod(&x, m, c);
SIGN(c) = SIGN(a);
CLEANUP:
mp_clear(&x);
X:
mp_clear(&g);
return res;
}
#endif
#if MP_IOFUNC
mp_print(mp, ofp)
Print a textual representation of the given mp_int on the output
stream 'ofp'. Output is generated using the internal radix.
*/
void mp_print(mp_int *mp, FILE *ofp)
{
int ix;
if(mp == NULL || ofp == NULL)
return;
fputc((SIGN(mp) == MP_NEG) ? '-' : '+', ofp);
for(ix = USED(mp) - 1; ix >= 0; ix--) {
fprintf(ofp, DIGIT_FMT, DIGIT(mp, ix));
}
}
#endif
mp_read_signed_bin(mp, str, len)
Read in a raw value (base 256) into the given mp_int
*/
mp_err mp_read_signed_bin(mp_int *mp, unsigned char *str, int len)
{
mp_err res;
ARGCHK(mp != NULL && str != NULL && len > 0, MP_BADARG);
if((res = mp_read_unsigned_bin(mp, str + 1, len - 1)) == MP_OKAY) {
if(str[0])
SIGN(mp) = MP_NEG;
else
SIGN(mp) = MP_ZPOS;
}
return res;
}
int mp_signed_bin_size(mp_int *mp)
{
ARGCHK(mp != NULL, 0);
return mp_unsigned_bin_size(mp) + 1;
}
mp_err mp_to_signed_bin(mp_int *mp, unsigned char *str)
{
ARGCHK(mp != NULL && str != NULL, MP_BADARG);
str[0] = (char)SIGN(mp);
return mp_to_unsigned_bin(mp, str + 1);
}
mp_read_unsigned_bin(mp, str, len)
Read in an unsigned value (base 256) into the given mp_int
*/
mp_err mp_read_unsigned_bin(mp_int *mp, unsigned char *str, int len)
{
int ix;
mp_err res;
ARGCHK(mp != NULL && str != NULL && len > 0, MP_BADARG);
mp_zero(mp);
for(ix = 0; ix < len; ix++) {
if((res = s_mp_mul_2d(mp, CHAR_BIT)) != MP_OKAY)
return res;
if((res = mp_add_d(mp, str[ix], mp)) != MP_OKAY)
return res;
}
return MP_OKAY;
}
int mp_unsigned_bin_size(mp_int *mp)
{
mp_digit topdig;
int count;
ARGCHK(mp != NULL, 0);
if(USED(mp) == 1 && DIGIT(mp, 0) == 0)
return 1;
count = (USED(mp) - 1) * sizeof(mp_digit);
topdig = DIGIT(mp, USED(mp) - 1);
while(topdig != 0) {
++count;
topdig >>= CHAR_BIT;
}
return count;
}
mp_err mp_to_unsigned_bin(mp_int *mp, unsigned char *str)
{
mp_digit *dp, *end, d;
unsigned char *spos;
ARGCHK(mp != NULL && str != NULL, MP_BADARG);
dp = DIGITS(mp);
end = dp + USED(mp) - 1;
spos = str;
if(dp == end && *dp == 0) {
*str = '\0';
return MP_OKAY;
}
while(dp < end) {
unsigned int ix;
d = *dp;
for(ix = 0; ix < sizeof(mp_digit); ++ix) {
*spos = d & UCHAR_MAX;
d >>= CHAR_BIT;
++spos;
}
++dp;
}
d = *end;
while(d != 0) {
*spos = d & UCHAR_MAX;
d >>= CHAR_BIT;
++spos;
}
while(--spos > str) {
unsigned char t = *str;
*str = *spos;
*spos = t;
++str;
}
return MP_OKAY;
}
int mp_count_bits(mp_int *mp)
{
int len;
mp_digit d;
ARGCHK(mp != NULL, MP_BADARG);
len = DIGIT_BIT * (USED(mp) - 1);
d = DIGIT(mp, USED(mp) - 1);
while(d != 0) {
++len;
d >>= 1;
}
return len;
}
mp_read_radix(mp, str, radix)
Read an integer from the given string, and set mp to the resulting
value. The input is presumed to be in base 10. Leading non-digit
characters are ignored, and the function reads until a non-digit
character or the end of the string.
*/
mp_err mp_read_radix(mp_int *mp, unsigned char *str, int radix)
{
int ix = 0, val = 0;
mp_err res;
mp_sign sig = MP_ZPOS;
ARGCHK(mp != NULL && str != NULL && radix >= 2 && radix <= MAX_RADIX,
MP_BADARG);
mp_zero(mp);
while(str[ix] &&
(s_mp_tovalue(str[ix], radix) < 0) &&
str[ix] != '-' &&
str[ix] != '+') {
++ix;
}
if(str[ix] == '-') {
sig = MP_NEG;
++ix;
} else if(str[ix] == '+') {
sig = MP_ZPOS;
++ix;
}
while((val = s_mp_tovalue(str[ix], radix)) >= 0) {
if((res = s_mp_mul_d(mp, radix)) != MP_OKAY)
return res;
if((res = s_mp_add_d(mp, val)) != MP_OKAY)
return res;
++ix;
}
if(s_mp_cmp_d(mp, 0) == MP_EQ)
SIGN(mp) = MP_ZPOS;
else
SIGN(mp) = sig;
return MP_OKAY;
}
int mp_radix_size(mp_int *mp, int radix)
{
int len;
ARGCHK(mp != NULL, 0);
len = s_mp_outlen(mp_count_bits(mp), radix) + 1;
if(mp_cmp_z(mp) < 0)
++len;
return len;
}
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.
*/
int mp_value_radix_size(int num, int qty, int radix)
{
ARGCHK(num >= 0 && qty > 0 && radix >= 2 && radix <= MAX_RADIX, 0);
return s_mp_outlen(num * qty, radix);
}
mp_err mp_toradix(mp_int *mp, char *str, int radix)
{
int ix, pos = 0;
ARGCHK(mp != NULL && str != NULL, MP_BADARG);
ARGCHK(radix > 1 && radix <= MAX_RADIX, MP_RANGE);
if(mp_cmp_z(mp) == MP_EQ) {
str[0] = '0';
str[1] = '\0';
} else {
mp_err res;
mp_int tmp;
mp_sign sgn;
mp_digit rem, rdx = (mp_digit)radix;
char ch;
if((res = mp_init_copy(&tmp, mp)) != MP_OKAY)
return res;
sgn = SIGN(&tmp); SIGN(&tmp) = MP_ZPOS;
while(mp_cmp_z(&tmp) != 0) {
if((res = s_mp_div_d(&tmp, rdx, &rem)) != MP_OKAY) {
mp_clear(&tmp);
return res;
}
ch = s_mp_todigit(rem, radix, 0);
str[pos++] = ch;
}
if(sgn == MP_NEG)
str[pos++] = '-';
str[pos--] = '\0';
ix = 0;
while(ix < pos) {
char _tmp = str[ix];
str[ix] = str[pos];
str[pos] = _tmp;
++ix;
--pos;
}
mp_clear(&tmp);
}
return MP_OKAY;
}
int mp_char2value(char ch, int r)
{
return s_mp_tovalue(ch, r);
}
mp_strerror(ec)
Return a string describing the meaning of error code 'ec'. The
string returned is allocated in static memory, so the caller should
not attempt to modify or free the memory associated with this
string.
*/
const char *mp_strerror(mp_err ec)
{
int aec = (ec < 0) ? -ec : ec;
are accurate */
if(ec < MP_LAST_CODE || ec > MP_OKAY) {
return mp_err_string[0];
} else {
return mp_err_string[aec + 1];
}
}
mp_err s_mp_grow(mp_int *mp, mp_size min)
{
if(min > ALLOC(mp)) {
mp_digit *tmp;
min = ((min + (s_mp_defprec - 1)) / s_mp_defprec) * s_mp_defprec;
if((tmp = s_mp_alloc(min, sizeof(mp_digit))) == NULL)
return MP_MEM;
s_mp_copy(DIGITS(mp), tmp, USED(mp));
#if MP_CRYPTO
s_mp_setz(DIGITS(mp), ALLOC(mp));
#endif
s_mp_free(DIGITS(mp));
DIGITS(mp) = tmp;
ALLOC(mp) = min;
}
return MP_OKAY;
}
mp_err s_mp_pad(mp_int *mp, mp_size min)
{
if(min > USED(mp)) {
mp_err res;
if(min > ALLOC(mp) && (res = s_mp_grow(mp, min)) != MP_OKAY)
return res;
USED(mp) = min;
}
return MP_OKAY;
}
#if MP_MACRO == 0
void s_mp_setz(mp_digit *dp, mp_size count)
{
#if MP_MEMSET == 0
int ix;
for(ix = 0; ix < count; ix++)
dp[ix] = 0;
#else
memset(dp, 0, count * sizeof(mp_digit));
#endif
}
#endif
#if MP_MACRO == 0
void s_mp_copy(mp_digit *sp, mp_digit *dp, mp_size count)
{
#if MP_MEMCPY == 0
int ix;
for(ix = 0; ix < count; ix++)
dp[ix] = sp[ix];
#else
memcpy(dp, sp, count * sizeof(mp_digit));
#endif
}
#endif
#if MP_MACRO == 0
void *s_mp_alloc(size_t nb, size_t ni)
{
return calloc(nb, ni);
}
#endif
#if MP_MACRO == 0
void s_mp_free(void *ptr)
{
if(ptr)
free(ptr);
}
#endif
void s_mp_clamp(mp_int *mp)
{
mp_size du = USED(mp);
mp_digit *zp = DIGITS(mp) + du - 1;
while(du > 1 && !*zp--)
--du;
USED(mp) = du;
}
void s_mp_exch(mp_int *a, mp_int *b)
{
mp_int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
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)
{
mp_err res;
mp_size pos;
mp_digit *dp;
int ix;
if(p == 0)
return MP_OKAY;
if((res = s_mp_pad(mp, USED(mp) + p)) != MP_OKAY)
return res;
pos = USED(mp) - 1;
dp = DIGITS(mp);
for(ix = pos - p; ix >= 0; ix--)
dp[ix + p] = dp[ix];
for(ix = 0; (unsigned)ix < p; ix++)
dp[ix] = 0;
return MP_OKAY;
}
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.
*/
void s_mp_rshd(mp_int *mp, mp_size p)
{
mp_size ix;
mp_digit *dp;
if(p == 0)
return;
if(p >= USED(mp)) {
s_mp_setz(DIGITS(mp), ALLOC(mp));
USED(mp) = 1;
SIGN(mp) = MP_ZPOS;
return;
}
dp = DIGITS(mp);
for(ix = p; ix < USED(mp); ix++)
dp[ix - p] = dp[ix];
ix -= p;
while(ix < USED(mp))
dp[ix++] = 0;
s_mp_clamp(mp);
}
void s_mp_div_2(mp_int *mp)
{
s_mp_div_2d(mp, 1);
}
mp_err s_mp_mul_2(mp_int *mp)
{
unsigned int ix;
mp_digit kin = 0, kout, *dp = DIGITS(mp);
mp_err res;
for(ix = 0; ix < USED(mp); ix++) {
kout = (dp[ix] >> (DIGIT_BIT - 1)) & 1;
dp[ix] = (dp[ix] << 1) | kin;
kin = kout;
}
if(kin) {
if(ix >= ALLOC(mp)) {
if((res = s_mp_grow(mp, ALLOC(mp) + 1)) != MP_OKAY)
return res;
dp = DIGITS(mp);
}
dp[ix] = kin;
USED(mp) += 1;
}
return MP_OKAY;
}
Remainder the integer by 2^d, where d is a number of bits. This
amounts to a bitwise AND of the value, and does not require the full
division code
*/
void s_mp_mod_2d(mp_int *mp, mp_digit d)
{
unsigned int ndig = (d / DIGIT_BIT), nbit = (d % DIGIT_BIT);
unsigned int ix;
mp_digit dmask, *dp = DIGITS(mp);
if(ndig >= USED(mp))
return;
dmask = (1 << nbit) - 1;
dp[ndig] &= dmask;
for(ix = ndig + 1; ix < USED(mp); ix++)
dp[ix] = 0;
s_mp_clamp(mp);
}
Multiply by the integer 2^d, where d is a number of bits. This
amounts to a bitwise shift of the value, and does not require the
full multiplication code.
*/
mp_err s_mp_mul_2d(mp_int *mp, mp_digit d)
{
mp_err res;
mp_digit save, next, mask, *dp;
mp_size used;
unsigned int ix;
if((res = s_mp_lshd(mp, d / DIGIT_BIT)) != MP_OKAY)
return res;
dp = DIGITS(mp); used = USED(mp);
d %= DIGIT_BIT;
mask = (1 << d) - 1;
work with */
if((dp[used - 1] >> (DIGIT_BIT - d)) & mask) {
if((res = s_mp_grow(mp, used + 1)) != MP_OKAY)
return res;
dp = DIGITS(mp);
}
save = 0;
for(ix = 0; ix < used; ix++) {
next = (dp[ix] >> (DIGIT_BIT - d)) & mask;
dp[ix] = (dp[ix] << d) | save;
save = next;
}
digit, we'll increase the size by one digit, and store it...
*/
if(save) {
dp[used] = save;
USED(mp) += 1;
}
s_mp_clamp(mp);
return MP_OKAY;
}
Divide the integer by 2^d, where d is a number of bits. This
amounts to a bitwise shift of the value, and does not require the
full division code (used in Barrett reduction, see below)
*/
void s_mp_div_2d(mp_int *mp, mp_digit d)
{
int ix;
mp_digit save, next, mask, *dp = DIGITS(mp);
s_mp_rshd(mp, d / DIGIT_BIT);
d %= DIGIT_BIT;
mask = (1 << d) - 1;
save = 0;
for(ix = USED(mp) - 1; ix >= 0; ix--) {
next = dp[ix] & mask;
dp[ix] = (dp[ix] >> d) | (save << (DIGIT_BIT - d));
save = next;
}
s_mp_clamp(mp);
}
s_mp_norm(a, b)
Normalize a and b for division, where b is the divisor. In order
that we might make good guesses for quotient digits, we want the
leading digit of b to be at least half the radix, which we
accomplish by multiplying a and b by a constant. This constant is
returned (so that it can be divided back out of the remainder at the
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
multiplication and division steps to simple shifts.
*/
mp_digit s_mp_norm(mp_int *a, mp_int *b)
{
mp_digit t, d = 0;
t = DIGIT(b, USED(b) - 1);
while(t < (RADIX / 2)) {
t <<= 1;
++d;
}
if(d != 0) {
s_mp_mul_2d(a, d);
s_mp_mul_2d(b, d);
}
return d;
}
mp_err s_mp_add_d(mp_int *mp, mp_digit d)
{
mp_word w, k = 0;
mp_size ix = 1, used = USED(mp);
mp_digit *dp = DIGITS(mp);
w = dp[0] + d;
dp[0] = ACCUM(w);
k = CARRYOUT(w);
while(ix < used && k) {
w = dp[ix] + k;
dp[ix] = ACCUM(w);
k = CARRYOUT(w);
++ix;
}
if(k != 0) {
mp_err res;
if((res = s_mp_pad(mp, USED(mp) + 1)) != MP_OKAY)
return res;
DIGIT(mp, ix) = k;
}
return MP_OKAY;
}
mp_err s_mp_sub_d(mp_int *mp, mp_digit d)
{
mp_word w, b = 0;
mp_size ix = 1, used = USED(mp);
mp_digit *dp = DIGITS(mp);
w = (RADIX + dp[0]) - d;
b = CARRYOUT(w) ? 0 : 1;
dp[0] = ACCUM(w);
while(b && ix < used) {
w = (RADIX + dp[ix]) - b;
b = CARRYOUT(w) ? 0 : 1;
dp[ix] = ACCUM(w);
++ix;
}
s_mp_clamp(mp);
if(b)
return MP_RANGE;
else
return MP_OKAY;
}
mp_err s_mp_mul_d(mp_int *a, mp_digit d)
{
mp_word w, k = 0;
mp_size ix, max;
mp_err res;
mp_digit *dp = DIGITS(a);
Single-digit multiplication will increase the precision of the
output by at most one digit. However, we can detect when this
will happen -- if the high-order digit of a, times d, gives a
two-digit result, then the precision of the result will increase;
otherwise it won't. We use this fact to avoid calling s_mp_pad()
unless absolutely necessary.
*/
max = USED(a);
w = dp[max - 1] * d;
if(CARRYOUT(w) != 0) {
if((res = s_mp_pad(a, max + 1)) != MP_OKAY)
return res;
dp = DIGITS(a);
}
for(ix = 0; ix < max; ix++) {
w = (dp[ix] * d) + k;
dp[ix] = ACCUM(w);
k = CARRYOUT(w);
}
test guarantees we have enough storage to do this safely.
*/
if(k) {
dp[max] = k;
USED(a) = max + 1;
}
s_mp_clamp(a);
return MP_OKAY;
}
s_mp_div_d(mp, d, r)
Compute the quotient mp = mp / d and remainder r = mp mod d, for a
single digit d. If r is null, the remainder will be discarded.
*/
mp_err s_mp_div_d(mp_int *mp, mp_digit d, mp_digit *r)
{
mp_word w = 0, t;
mp_int quot;
mp_err res;
mp_digit *dp = DIGITS(mp), *qp;
int ix;
if(d == 0)
return MP_RANGE;
if((res = mp_init_size(", USED(mp))) != MP_OKAY)
return res;
USED(") = USED(mp);
qp = DIGITS(");
for(ix = USED(mp) - 1; ix >= 0; ix--) {
w = (w << DIGIT_BIT) | dp[ix];
if(w >= d) {
t = w / d;
w = w % d;
} else {
t = 0;
}
qp[ix] = t;
}
if(r)
*r = w;
s_mp_clamp(");
mp_exch(", mp);
mp_clear(");
return MP_OKAY;
}
mp_err s_mp_add(mp_int *a, mp_int *b)
{
mp_word w = 0;
mp_digit *pa, *pb;
mp_size ix, used = USED(b);
mp_err res;
if((used > USED(a)) && (res = s_mp_pad(a, used)) != MP_OKAY)
return res;
Add up all digits up to the precision of b. If b had initially
the same precision as a, or greater, we took care of it by the
padding step above, so there is no problem. If b had initially
less precision, we'll have to make sure the carry out is duly
propagated upward among the higher-order digits of the sum.
*/
pa = DIGITS(a);
pb = DIGITS(b);
for(ix = 0; ix < used; ++ix) {
w += *pa + *pb++;
*pa++ = ACCUM(w);
w = CARRYOUT(w);
}
sure the carries get propagated upward...
*/
used = USED(a);
while(w && ix < used) {
w += *pa;
*pa++ = ACCUM(w);
w = CARRYOUT(w);
++ix;
}
it. We could have done this initially, but why touch the memory
allocator unless we're sure we have to?
*/
if(w) {
if((res = s_mp_pad(a, used + 1)) != MP_OKAY)
return res;
DIGIT(a, ix) = w;
}
return MP_OKAY;
}
mp_err s_mp_sub(mp_int *a, mp_int *b)
{
mp_word w = 0;
mp_digit *pa, *pb;
mp_size ix, used = USED(b);
Subtract and propagate borrow. Up to the precision of b, this
accounts for the digits of b; after that, we just make sure the
carries get to the right place. This saves having to pad b out to
the precision of a just to make the loops work right...
*/
pa = DIGITS(a);
pb = DIGITS(b);
for(ix = 0; ix < used; ++ix) {
w = (RADIX + *pa) - w - *pb++;
*pa++ = ACCUM(w);
w = CARRYOUT(w) ? 0 : 1;
}
used = USED(a);
while(ix < used) {
w = RADIX + *pa - w;
*pa++ = ACCUM(w);
w = CARRYOUT(w) ? 0 : 1;
++ix;
}
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...
*/
if(w)
return MP_RANGE;
else
return MP_OKAY;
}
mp_err s_mp_reduce(mp_int *x, mp_int *m, mp_int *mu)
{
mp_int q;
mp_err res;
mp_size um = USED(m);
if((res = mp_init_copy(&q, x)) != MP_OKAY)
return res;
s_mp_rshd(&q, um - 1);
s_mp_mul(&q, mu);
s_mp_rshd(&q, um + 1);
s_mp_mod_2d(x, (mp_digit)(DIGIT_BIT * (um + 1)));
#ifndef SHRT_MUL
s_mp_mul(&q, m);
s_mp_mod_2d(&q, (mp_digit)(DIGIT_BIT * (um + 1)));
#else
s_mp_mul_dig(&q, m, um + 1);
#endif
if((res = mp_sub(x, &q, x)) != MP_OKAY)
goto CLEANUP;
if(mp_cmp_z(x) < 0) {
mp_set(&q, 1);
if((res = s_mp_lshd(&q, um + 1)) != MP_OKAY)
goto CLEANUP;
if((res = mp_add(x, &q, x)) != MP_OKAY)
goto CLEANUP;
}
while(mp_cmp(x, m) >= 0) {
if((res = s_mp_sub(x, m)) != MP_OKAY)
break;
}
CLEANUP:
mp_clear(&q);
return res;
}
mp_err s_mp_mul(mp_int *a, mp_int *b)
{
mp_word w, k = 0;
mp_int tmp;
mp_err res;
mp_size ix, jx, ua = USED(a), ub = USED(b);
mp_digit *pa, *pb, *pt, *pbt;
if((res = mp_init_size(&tmp, ua + ub)) != MP_OKAY)
return res;
USED(&tmp) = ua + ub;
pbt = DIGITS(&tmp);
pb = DIGITS(b);
for(ix = 0; ix < ub; ++ix, ++pb) {
if(*pb == 0)
continue;
pa = DIGITS(a);
for(jx = 0; jx < ua; ++jx, ++pa) {
pt = pbt + ix + jx;
w = *pb * *pa + k + *pt;
*pt = ACCUM(w);
k = CARRYOUT(w);
}
pbt[ix + jx] = k;
k = 0;
}
s_mp_clamp(&tmp);
s_mp_exch(&tmp, a);
mp_clear(&tmp);
return MP_OKAY;
}
#if 0
void s_mp_kmul(mp_digit *a, mp_digit *b, mp_digit *out, mp_size len)
{
mp_word w, k = 0;
mp_size ix, jx;
mp_digit *pa, *pt;
for(ix = 0; ix < len; ++ix, ++b) {
if(*b == 0)
continue;
pa = a;
for(jx = 0; jx < len; ++jx, ++pa) {
pt = out + ix + jx;
w = *b * *pa + k + *pt;
*pt = ACCUM(w);
k = CARRYOUT(w);
}
out[ix + jx] = k;
k = 0;
}
}
#endif
Computes the square of a, in place. This can be done more
efficiently than a general multiplication, because many of the
computation steps are redundant when squaring. The inner product
step is a bit more complicated, but we save a fair number of
iterations of the multiplication loop.
*/
#if MP_SQUARE
mp_err s_mp_sqr(mp_int *a)
{
mp_word w, k = 0;
mp_int tmp;
mp_err res;
mp_size ix, jx, kx, used = USED(a);
mp_digit *pa1, *pa2, *pt, *pbt;
if((res = mp_init_size(&tmp, 2 * used)) != MP_OKAY)
return res;
USED(&tmp) = 2 * used;
pbt = DIGITS(&tmp);
pa1 = DIGITS(a);
for(ix = 0; ix < used; ++ix, ++pa1) {
if(*pa1 == 0)
continue;
w = DIGIT(&tmp, ix + ix) + (*pa1 * *pa1);
pbt[ix + ix] = ACCUM(w);
k = CARRYOUT(w);
The inner product is computed as:
(C, S) = t[i,j] + 2 a[i] a[j] + C
This can overflow what can be represented in an mp_word, and
since C arithmetic does not provide any way to check for
overflow, we have to check explicitly for overflow conditions
before they happen.
*/
for(jx = ix + 1, pa2 = DIGITS(a) + jx; jx < used; ++jx, ++pa2) {
mp_word u = 0, v;
pt = pbt + ix + jx;
w = *pa1 * *pa2;
overflow, and we need to record a carry out into the next
word */
u = (w >> (MP_WORD_BIT - 1)) & 1;
for C arithmetic (we've already noted if it is to occur)
*/
w *= 2;
v = *pt + k;
if the addition will cause one, and set the carry out if so
*/
u |= ((MP_WORD_MAX - v) < w);
w += v;
*pt = ACCUM(w);
This is why k must be an mp_word, instead of an mp_digit */
k = CARRYOUT(w) | (u << DIGIT_BIT);
}
k = DIGIT(&tmp, ix + jx) + k;
pbt[ix + jx] = ACCUM(k);
k = CARRYOUT(k);
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
*/
kx = 1;
while(k) {
k = pbt[ix + jx + kx] + 1;
pbt[ix + jx + kx] = ACCUM(k);
k = CARRYOUT(k);
++kx;
}
}
s_mp_clamp(&tmp);
s_mp_exch(&tmp, a);
mp_clear(&tmp);
return MP_OKAY;
}
#endif
s_mp_div(a, b)
Compute a = a / b and b = a mod b. Assumes b > a.
*/
mp_err s_mp_div(mp_int *a, mp_int *b)
{
mp_int quot, rem, t;
mp_word q;
mp_err res;
mp_digit d;
int ix;
if(mp_cmp_z(b) == 0)
return MP_RANGE;
if((ix = s_mp_ispow2(b)) >= 0) {
mp_copy(a, b);
s_mp_div_2d(a, (mp_digit)ix);
s_mp_mod_2d(b, (mp_digit)ix);
return MP_OKAY;
}
if((res = mp_init_size(", USED(a))) != MP_OKAY)
return res;
if((res = mp_init_size(&t, USED(a))) != MP_OKAY)
goto T;
if((res = mp_init_size(&rem, USED(a))) != MP_OKAY)
goto REM;
d = s_mp_norm(a, b);
ix = USED(a) - 1;
while(ix >= 0) {
while(s_mp_cmp(&rem, b) < 0 && ix >= 0) {
if((res = s_mp_lshd(&rem, 1)) != MP_OKAY)
goto CLEANUP;
if((res = s_mp_lshd(", 1)) != MP_OKAY)
goto CLEANUP;
DIGIT(&rem, 0) = DIGIT(a, ix);
s_mp_clamp(&rem);
--ix;
}
if(s_mp_cmp(&rem, b) < 0)
break;
q = DIGIT(&rem, USED(&rem) - 1);
if(q <= DIGIT(b, USED(b) - 1) && USED(&rem) > 1)
q = (q << DIGIT_BIT) | DIGIT(&rem, USED(&rem) - 2);
q /= DIGIT(b, USED(b) - 1);
if(q >= RADIX)
q = RADIX - 1;
mp_copy(b, &t);
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
I didn't implement that here.
*/
while(s_mp_cmp(&t, &rem) > 0) {
--q;
s_mp_sub(&t, b);
}
if((res = s_mp_sub(&rem, &t)) != MP_OKAY)
goto CLEANUP;
Include the digit in the quotient. We allocated enough memory
for any quotient we could ever possibly get, so we should not
have to check for failures here
*/
DIGIT(", 0) = q;
}
if(d != 0)
s_mp_div_2d(&rem, d);
s_mp_clamp(");
s_mp_clamp(&rem);
s_mp_exch(", a);
s_mp_exch(&rem, b);
CLEANUP:
mp_clear(&rem);
REM:
mp_clear(&t);
T:
mp_clear(");
return res;
}
mp_err s_mp_2expt(mp_int *a, mp_digit k)
{
mp_err res;
mp_size dig, bit;
dig = k / DIGIT_BIT;
bit = k % DIGIT_BIT;
mp_zero(a);
if((res = s_mp_pad(a, dig + 1)) != MP_OKAY)
return res;
DIGIT(a, dig) |= (1 << bit);
return MP_OKAY;
}
int s_mp_cmp(mp_int *a, mp_int *b)
{
mp_size ua = USED(a), ub = USED(b);
if(ua > ub)
return MP_GT;
else if(ua < ub)
return MP_LT;
else {
int ix = ua - 1;
mp_digit *ap = DIGITS(a) + ix, *bp = DIGITS(b) + ix;
while(ix >= 0) {
if(*ap > *bp)
return MP_GT;
else if(*ap < *bp)
return MP_LT;
--ap; --bp; --ix;
}
return MP_EQ;
}
}
int s_mp_cmp_d(mp_int *a, mp_digit d)
{
mp_size ua = USED(a);
mp_digit *ap = DIGITS(a);
if(ua > 1)
return MP_GT;
if(*ap < d)
return MP_LT;
else if(*ap > d)
return MP_GT;
else
return MP_EQ;
}
Returns -1 if the value is not a power of two; otherwise, it returns
k such that v = 2^k, i.e. lg(v).
*/
int s_mp_ispow2(mp_int *v)
{
mp_digit d, *dp;
mp_size uv = USED(v);
int extra = 0, ix;
d = DIGIT(v, uv - 1);
while(d && ((d & 1) == 0)) {
d >>= 1;
++extra;
}
if(d == 1) {
ix = uv - 2;
dp = DIGITS(v) + ix;
while(ix >= 0) {
if(*dp)
return -1;
--dp; --ix;
}
return ((uv - 1) * DIGIT_BIT) + extra;
}
return -1;
}
int s_mp_ispow2d(mp_digit d)
{
int pow = 0;
while((d & 1) == 0) {
++pow; d >>= 1;
}
if(d == 1)
return pow;
return -1;
}
Convert the given character to its digit value, in the given radix.
If the given character is not understood in the given radix, -1 is
returned. Otherwise the digit's numeric value is returned.
The results will be odd if you use a radix < 2 or > 62, you are
expected to know what you're up to.
*/
int s_mp_tovalue(char ch, int r)
{
int val, xch;
if(r > 36)
xch = ch;
else
xch = toupper(ch);
if(isdigit(xch))
val = xch - '0';
else if(isupper(xch))
val = xch - 'A' + 10;
else if(islower(xch))
val = xch - 'a' + 36;
else if(xch == '+')
val = 62;
else if(xch == '/')
val = 63;
else
return -1;
if(val < 0 || val >= r)
return -1;
return val;
}
Convert val to a radix-r digit, if possible. If val is out of range
for r, returns zero. Otherwise, returns an ASCII character denoting
the value in the given radix.
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;
if(val < 0 || val >= r)
return 0;
ch = s_dmap_1[val];
if(r <= 36 && low)
ch = tolower(ch);
return ch;
}
Return an estimate for how long a string is needed to hold a radix
r representation of a number with 'bits' significant bits.
Does not include space for a sign or a NUL terminator.
*/
int s_mp_outlen(int bits, int r)
{
return (int)((double)bits * LOG_V_2(r));
}