diff options
author | Kevin B Kenny <kennykb@acm.org> | 2005-01-19 22:41:26 (GMT) |
---|---|---|
committer | Kevin B Kenny <kennykb@acm.org> | 2005-01-19 22:41:26 (GMT) |
commit | ef78ca64ce6ba6a8786f083318fe536f2bd52925 (patch) | |
tree | 47f8ad0d7291237c7f9af988c5e05275ed9286ee /libtommath/bn_mp_div_3.c | |
parent | b23d942a1e86ddee18c2309afd7fa7e9afa79ef8 (diff) | |
download | tcl-ef78ca64ce6ba6a8786f083318fe536f2bd52925.zip tcl-ef78ca64ce6ba6a8786f083318fe536f2bd52925.tar.gz tcl-ef78ca64ce6ba6a8786f083318fe536f2bd52925.tar.bz2 |
Import of libtommath 0.33
Diffstat (limited to 'libtommath/bn_mp_div_3.c')
-rw-r--r-- | libtommath/bn_mp_div_3.c | 75 |
1 files changed, 75 insertions, 0 deletions
diff --git a/libtommath/bn_mp_div_3.c b/libtommath/bn_mp_div_3.c new file mode 100644 index 0000000..7cbafc1 --- /dev/null +++ b/libtommath/bn_mp_div_3.c @@ -0,0 +1,75 @@ +#include <tommath.h> +#ifdef BN_MP_DIV_3_C +/* LibTomMath, multiple-precision integer library -- Tom St Denis + * + * LibTomMath is a library that provides multiple-precision + * integer arithmetic as well as number theoretic functionality. + * + * The library was designed directly after the MPI library by + * Michael Fromberger but has been written from scratch with + * additional optimizations in place. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org + */ + +/* divide by three (based on routine from MPI and the GMP manual) */ +int +mp_div_3 (mp_int * a, mp_int *c, mp_digit * d) +{ + mp_int q; + mp_word w, t; + mp_digit b; + int res, ix; + + /* b = 2**DIGIT_BIT / 3 */ + b = (((mp_word)1) << ((mp_word)DIGIT_BIT)) / ((mp_word)3); + + if ((res = mp_init_size(&q, a->used)) != MP_OKAY) { + return res; + } + + q.used = a->used; + q.sign = a->sign; + w = 0; + for (ix = a->used - 1; ix >= 0; ix--) { + w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]); + + if (w >= 3) { + /* multiply w by [1/3] */ + t = (w * ((mp_word)b)) >> ((mp_word)DIGIT_BIT); + + /* now subtract 3 * [w/3] from w, to get the remainder */ + w -= t+t+t; + + /* fixup the remainder as required since + * the optimization is not exact. + */ + while (w >= 3) { + t += 1; + w -= 3; + } + } else { + t = 0; + } + q.dp[ix] = (mp_digit)t; + } + + /* [optional] store the remainder */ + if (d != NULL) { + *d = (mp_digit)w; + } + + /* [optional] store the quotient */ + if (c != NULL) { + mp_clamp(&q); + mp_exch(&q, c); + } + mp_clear(&q); + + return res; +} + +#endif |