X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/3c9ede175eabf2276f9ff99e8b886562f8b661a3..bba24c1d073873d99fd56ef038e9306bdfafe8cc:/mpx.h diff --git a/mpx.h b/mpx.h index 9429e91..7d8a2cd 100644 --- a/mpx.h +++ b/mpx.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mpx.h,v 1.3 1999/11/13 01:51:29 mdw Exp $ + * $Id: mpx.h,v 1.6 1999/12/10 23:23:51 mdw Exp $ * * Low level multiprecision arithmetic * @@ -30,6 +30,15 @@ /*----- Revision history --------------------------------------------------* * * $Log: mpx.h,v $ + * Revision 1.6 1999/12/10 23:23:51 mdw + * Karatsuba-Ofman multiplication algorithm. + * + * Revision 1.5 1999/11/20 22:23:27 mdw + * Add function versions of some low-level macros with wider use. + * + * Revision 1.4 1999/11/17 18:04:43 mdw + * Add two's complement support. Fix a bug in MPX_UMLAN. + * * Revision 1.3 1999/11/13 01:51:29 mdw * Minor interface changes. Should be stable now. * @@ -41,8 +50,8 @@ * */ -#ifndef MPX_H -#define MPX_H +#ifndef CATACOMB_MPX_H +#define CATACOMB_MPX_H #ifdef __cplusplus extern "C" { @@ -65,7 +74,7 @@ #include -#ifndef MPW_H +#ifndef CATACOMB_MPW_H # include "mpw.h" #endif @@ -282,6 +291,19 @@ extern void mpx_lsr(mpw */*dv*/, mpw */*dvl*/, /*----- Unsigned arithmetic -----------------------------------------------*/ +/* --- @mpx_2c@ --- * + * + * Arguments: @mpw *dv, *dvl@ = destination vector + * @const mpw *v, *vl@ = source vector + * + * Returns: --- + * + * Use: Calculates the two's complement of @v@. + */ + +extern void mpx_2c(mpw */*dv*/, mpw */*dvl*/, + const mpw */*v*/, const mpw */*vl*/); + /* --- @mpx_ucmp@ --- * * * Arguments: @const mpw *av, *avl@ = first argument vector base and limit @@ -320,10 +342,12 @@ extern void mpx_uadd(mpw */*dv*/, mpw */*dvl*/, const mpw */*av*/, const mpw */*avl*/, const mpw */*bv*/, const mpw */*bvl*/); -/* --- @MPX_UADDN@ --- * +/* --- @mpx_uaddn@ --- * * - * Arguments: @dv, dvl@ = source and destination vector base and limit - * @n@ = other addend + * Arguments: @mpw *dv, *dvl@ = source and destination base and limit + * @mpw n@ = other addend + * + * Returns: --- * * Use: Adds a small integer to a multiprecision number. */ @@ -339,6 +363,8 @@ extern void mpx_uadd(mpw */*dv*/, mpw */*dvl*/, } \ } while (0) +extern void mpx_uaddn(mpw */*dv*/, mpw */*dvl*/, mpw /*n*/); + /* --- @mpx_usub@ --- * * * Arguments: @mpw *dv, *dvl@ = destination vector base and limit @@ -360,10 +386,12 @@ extern void mpx_usub(mpw */*dv*/, mpw */*dvl*/, const mpw */*av*/, const mpw */*avl*/, const mpw */*bv*/, const mpw */*bvl*/); -/* --- @MPX_USUBN@ --- * +/* --- @mpx_usubn@ --- * * - * Arguments: @@dv, dvl@ = destination vector base and limit - * @n@ = other addend + * Arguments: @mpw *dv, *dvl@ = source and destination base and limit + * @n@ = subtrahend + * + * Returns: --- * * Use: Subtracts a small integer from a multiprecision number. */ @@ -382,6 +410,8 @@ extern void mpx_usub(mpw */*dv*/, mpw */*dvl*/, } \ } while (0) +extern void mpx_usubn(mpw */*dv*/, mpw */*dvl*/, mpw /*n*/); + /* --- @mpx_umul@ --- * * * Arguments: @mpw *dv, *dvl@ = destination vector base and limit @@ -400,11 +430,13 @@ extern void mpx_umul(mpw */*dv*/, mpw */*dvl*/, const mpw */*av*/, const mpw */*avl*/, const mpw */*bv*/, const mpw */*bvl*/); -/* --- @MPX_UMULN@ --- * +/* --- @mpx_umuln@ --- * * - * Arguments: @dv, dvl@ = destination vector base and limit - * @av, avl@ = multiplicand vector base and limit - * @m@ = multiplier + * Arguments: @mpw *dv, *dvl@ = destination vector base and limit + * @const mpw *av, *avl@ = multiplicand vector base and limit + * @mpw m@ = multiplier + * + * Returns: --- * * Use: Multiplies a multiprecision integer by a single-word value. * The destination and source may be equal. The destination @@ -431,11 +463,16 @@ extern void mpx_umul(mpw */*dv*/, mpw */*dvl*/, } \ } while (0) -/* --- @MPX_UMLAN@ --- * +extern void mpx_umuln(mpw */*dv*/, mpw */*dvl*/, + const mpw */*av*/, const mpw */*avl*/, mpw m); + +/* --- @mpx_umlan@ --- * * - * Arguments: @dv, dvl@ = destination/accumulator vector base and limit - * @av, avl@ = multiplicand vector base and limit - * @m@ = multiplier + * Arguments: @mpw *dv, *dvl@ = destination/accumulator base and limit + * @const mpw *av, *avl@ = multiplicand vector base and limit + * @mpw m@ = multiplier + * + * Returns: --- * * Use: Multiplies a multiprecision integer by a single-word value * and adds the result to an accumulator. @@ -444,20 +481,23 @@ extern void mpx_umul(mpw */*dv*/, mpw */*dvl*/, #define MPX_UMLAN(dv, dvl, av, avl, m) do { \ mpw *_dv = (dv), *_dvl = (dvl); \ const mpw *_av = (av), *_avl = (avl); \ - mpw _c = 0; \ + mpw _cc = 0; \ mpd _m = (m); \ \ while (_av < _avl) { \ mpd _x; \ if (_dv >= _dvl) \ break; \ - _x = (mpd)*_dv + (mpd)_m * (mpd)*_av++ + _c; \ + _x = (mpd)*_dv + (mpd)_m * (mpd)*_av++ + _cc; \ *_dv++ = MPW(_x); \ - _c = _x >> MPW_BITS; \ + _cc = _x >> MPW_BITS; \ } \ - MPX_UADDN(_dv, _dvl, _c); \ + MPX_UADDN(_dv, _dvl, _cc); \ } while (0) +extern void mpx_umlan(mpw */*dv*/, mpw */*dvl*/, + const mpw */*av*/, const mpw */*avl*/, mpw m); + /* --- @mpx_usqr@ --- * * * Arguments: @mpw *dv, *dvl@ = destination vector base and limit @@ -472,6 +512,32 @@ extern void mpx_umul(mpw */*dv*/, mpw */*dvl*/, extern void mpx_usqr(mpw */*dv*/, mpw */*dvl*/, const mpw */*av*/, const mpw */*avl*/); +/* --- @mpx_kmul@ --- * + * + * Arguments: @mpw *dv, *dvl@ = pointer to destination buffer + * @const mpw *av, *avl@ = pointer to first argument + * @const mpw *bv, *bvl@ = pointer to second argument + * @mpw *sv, *svl@ = pointer to scratch workspace + * + * Returns: --- + * + * Use: Multiplies two multiprecision integers using Karatsuba's + * algorithm. This is rather faster than traditional long + * multiplication (e.g., @mpx_umul@) on large numbers, although + * more expensive on small ones. + * + * The destination and scratch buffers must be twice as large as + * the larger argument. + */ + +#define KARATSUBA_CUTOFF 16 +#define KARATSUBA_SLOP 32 + +extern void mpx_kmul(mpw */*dv*/, mpw */*dvl*/, + const mpw */*av*/, const mpw */*avl*/, + const mpw */*bv*/, const mpw */*bvl*/, + mpw */*sv*/, mpw */*svl*/); + /* --- @mpx_udiv@ --- * * * Arguments: @mpw *qv, *qvl@ = quotient vector base and limit @@ -488,8 +554,7 @@ extern void mpx_usqr(mpw */*dv*/, mpw */*dvl*/, * requiring the dividend to be in the result position but it * does make some sense really. The remainder must have * headroom for at least two extra words. The scratch space - * must be at least two words larger than twice the size of the - * divisor. + * must be at least one word larger than the divisor. */ extern void mpx_udiv(mpw */*qv*/, mpw */*qvl*/, mpw */*rv*/, mpw */*rvl*/,