X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/f09e814abfcb58c0bb5423589e2940c205106e8d..1589affab225db500965e2cb869c534d6860e6bd:/mpx.h diff --git a/mpx.h b/mpx.h index 948e7dd..13b63cc 100644 --- a/mpx.h +++ b/mpx.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mpx.h,v 1.13 2002/10/06 22:52:50 mdw Exp $ + * $Id: mpx.h,v 1.17 2004/03/27 00:04:46 mdw Exp $ * * Low level multiprecision arithmetic * @@ -30,6 +30,18 @@ /*----- Revision history --------------------------------------------------* * * $Log: mpx.h,v $ + * Revision 1.17 2004/03/27 00:04:46 mdw + * Implement efficient reduction for pleasant-looking primes. + * + * Revision 1.16 2003/05/16 09:09:24 mdw + * Fix @mp_lsl2c@. Turns out to be surprisingly tricky. + * + * Revision 1.15 2002/10/19 17:56:50 mdw + * Fix bit operations. Test them (a bit) better. + * + * Revision 1.14 2002/10/09 00:36:03 mdw + * Fix bounds on workspace for Karatsuba operations. + * * Revision 1.13 2002/10/06 22:52:50 mdw * Pile of changes for supporting two's complement properly. * @@ -211,6 +223,20 @@ memset(_v, 0, MPWS(_vl - _v)); \ } while (0) +/* --- @MPX_ONE@ --- * + * + * Arguments: @v, vl@ = base and limit of vector to clear + * + * Use: Fills the area between the two vector pointers with ones. + */ + +#define MPX_ONE(v, vl) do { \ + mpw * _v = (v); \ + const mpw *_vl = (vl); \ + while (_v < _vl) \ + *_v++ = MPW_MAX; \ +} while (0) + /*----- Loading and storing -----------------------------------------------*/ /* --- @mpx_storel@ --- * @@ -363,6 +389,22 @@ extern void mpx_lsl(mpw */*dv*/, mpw */*dvl*/, const mpw */*av*/, const mpw */*avl*/, size_t /*n*/); +/* --- @mpx_lslc@ --- * + * + * Arguments: @mpw *dv, *dvl@ = destination vector base and limit + * @const mpw *av, *avl@ = source vector base and limit + * @size_t n@ = number of bit positions to shift by + * + * Returns: --- + * + * Use: Performs a logical shift left operation on an integer, only + * it fills in the bits with ones instead of zeroes. + */ + +extern void mpx_lslc(mpw */*dv*/, mpw */*dvl*/, + const mpw */*av*/, const mpw */*avl*/, + size_t /*n*/); + /* --- @mpx_lsr@ --- * * * Arguments: @mpw *dv, *dvl@ = destination vector base and limit @@ -380,29 +422,6 @@ extern void mpx_lsr(mpw */*dv*/, mpw */*dvl*/, /*----- Bitwise operations ------------------------------------------------*/ -/* --- How to implement them --- * - * - * x: 0011 - * y: 0101 - */ - -#define MPX_B0000(x, y) (0u) -#define MPX_B0001(x, y) ((x) & (y)) -#define MPX_B0010(x, y) ((x) & ~(y)) -#define MPX_B0011(x, y) (x) -#define MPX_B0100(x, y) (~(x) & ~(y)) -#define MPX_B0101(x, y) (y) -#define MPX_B0110(x, y) ((x) ^ (y)) -#define MPX_B0111(x, y) ((x) | (y)) -#define MPX_B1000(x, y) (~((x) | (y))) -#define MPX_B1001(x, y) (~((x) ^ (y))) -#define MPX_B1010(x, y) (~(y)) -#define MPX_B1011(x, y) ((x) | ~(y)) -#define MPX_B1100(x, y) (~(x)) -#define MPX_B1101(x, y) (~(x) | (y)) -#define MPX_B1110(x, y) (~((x) & (y))) -#define MPX_B1111(x, y) (~0u) - /* --- @mpx_bitop@ --- * * * Arguments: @mpw *dv, *dvl@ = destination vector @@ -544,6 +563,22 @@ extern void mpx_uadd(mpw */*dv*/, mpw */*dvl*/, extern void mpx_uaddn(mpw */*dv*/, mpw */*dvl*/, mpw /*n*/); +/* --- @mpx_uaddnlsl@ --- * + * + * Arguments: @mpw *dv, *dvl@ = destination and first argument vector + * @mpw a@ = second argument + * @unsigned o@ = offset in bits + * + * Returns: --- + * + * Use: Computes %$d + 2^o a$%. If the result overflows then + * high-order bits are discarded, as usual. We must have + * @0 < o < MPW_BITS@. + */ + +extern void mpx_uaddnlsl(mpw */*dv*/, mpw */*dvl*/, + mpw /*a*/, unsigned /*o*/); + /* --- @mpx_usub@ --- * * * Arguments: @mpw *dv, *dvl@ = destination vector base and limit @@ -591,6 +626,23 @@ extern void mpx_usub(mpw */*dv*/, mpw */*dvl*/, extern void mpx_usubn(mpw */*dv*/, mpw */*dvl*/, mpw /*n*/); +/* --- @mpx_usubnlsl@ --- * + * + * Arguments: @mpw *dv, *dvl@ = destination and first argument vector + * @mpw a@ = second argument + * @unsigned o@ = offset in bits + * + * Returns: --- + * + * Use: Computes %$d - 2^o a$%. If the result overflows then + * high-order bits are discarded, as usual, so you get two's + * complement. Which might be what you wanted... We must have + * @0 < o < MPW_BITS@. + */ + +extern void mpx_usubnlsl(mpw */*dv*/, mpw */*dvl*/, + mpw /*a*/, unsigned /*o*/); + /* --- @mpx_umul@ --- * * * Arguments: @mpw *dv, *dvl@ = destination vector base and limit @@ -733,20 +785,12 @@ extern mpw mpx_udivn(mpw */*qv*/, mpw */*qvl*/, * * This is the limiting length for using Karatsuba algorithms. It's best to * use the simpler classical multiplication method on numbers smaller than - * this. + * this. It is unsafe to make this constant less than four (i.e., the + * algorithms will fail). */ #define MPK_THRESH 16 -/* --- @MPK_SLOP@ --- * - * - * The extra number of words required as scratch space by the Karatsuba - * routines. This is a (generous) guess, since the actual amount of space - * required is proportional to the recursion depth. - */ - -#define MPK_SLOP 64 - /* --- @mpx_kmul@ --- * * * Arguments: @mpw *dv, *dvl@ = pointer to destination buffer @@ -761,10 +805,9 @@ extern mpw mpx_udivn(mpw */*qv*/, mpw */*qvl*/, * 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. The scratch space must be twice as - * large as the larger argument, plus the magic number - * @MPK_SLOP@. + * The destination must be three times as large as the larger + * argument. The scratch space must be five times as large as + * the larger argument. */ extern void mpx_kmul(mpw */*dv*/, mpw */*dvl*/, @@ -786,9 +829,9 @@ extern void mpx_kmul(mpw */*dv*/, mpw */*dvl*/, * large numbers, although more expensive on small ones, and * rather simpler than full-blown Karatsuba multiplication. * - * The destination must be twice as large as the argument. The - * scratch space must be twice as large as the argument, plus - * the magic number @MPK_SLOP@. + * The destination must be three times as large as the larger + * argument. The scratch space must be five times as large as + * the larger argument. */ extern void mpx_ksqr(mpw */*dv*/, mpw */*dvl*/,