X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/f09e814abfcb58c0bb5423589e2940c205106e8d..6ec3a4cf4aaa7cd375e1aa18f85861986259b8e5:/mpx.h diff --git a/mpx.h b/mpx.h index 948e7dd..19f5cc7 100644 --- a/mpx.h +++ b/mpx.h @@ -1,13 +1,13 @@ /* -*-c-*- * - * $Id: mpx.h,v 1.13 2002/10/06 22:52:50 mdw Exp $ + * $Id: mpx.h,v 1.18 2004/04/08 01:36:15 mdw Exp $ * * Low level multiprecision arithmetic * * (c) 1999 Straylight/Edgeware */ -/*----- Licensing notice --------------------------------------------------* +/*----- Licensing notice --------------------------------------------------* * * This file is part of Catacomb. * @@ -15,62 +15,18 @@ * it under the terms of the GNU Library General Public License as * published by the Free Software Foundation; either version 2 of the * License, or (at your option) any later version. - * + * * Catacomb is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Library General Public License for more details. - * + * * You should have received a copy of the GNU Library General Public * License along with Catacomb; if not, write to the Free * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, * MA 02111-1307, USA. */ -/*----- Revision history --------------------------------------------------* - * - * $Log: mpx.h,v $ - * Revision 1.13 2002/10/06 22:52:50 mdw - * Pile of changes for supporting two's complement properly. - * - * Revision 1.12 2001/04/03 19:36:05 mdw - * Add some simple bitwise operations so that Perl can use them. - * - * Revision 1.11 2000/10/08 15:48:35 mdw - * Rename Karatsuba constants now that we have @gfx_kmul@ too. - * - * Revision 1.10 2000/10/08 12:06:12 mdw - * Provide @mpx_ueq@ for rapidly testing equality of two integers. - * - * Revision 1.9 1999/12/22 15:49:07 mdw - * New function for division by a small integer. - * - * Revision 1.8 1999/12/11 10:57:43 mdw - * Karatsuba squaring algorithm. - * - * Revision 1.7 1999/12/11 01:51:28 mdw - * Change Karatsuba parameters slightly. - * - * 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. - * - * Revision 1.2 1999/11/11 17:47:55 mdw - * Minor changes for different `mptypes.h' format. - * - * Revision 1.1 1999/09/03 08:41:12 mdw - * Initial import. - * - */ - #ifndef CATACOMB_MPX_H #define CATACOMB_MPX_H @@ -131,9 +87,9 @@ if (_v == _vl) \ (b) = 0; \ else { \ - unsigned long _b = MPW_BITS * (_vl - _v - 1) + 1; \ + unsigned long _b = MPW_BITS * (_vl - _v - 1) + 1; \ mpw _w = _vl[-1]; \ - unsigned _k = MPW_BITS / 2; \ + unsigned _k = MPW_P2; \ while (_k) { \ if (_w >> _k) { \ _w >>= _k; \ @@ -211,6 +167,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 +333,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 +366,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 @@ -436,11 +399,11 @@ MPX_DOBIN(MPX_BITDECL) * Synonyms for the commonly-used functions above. */ -#define mpx_and mpx_bit0001 -#define mpx_or mpx_bit0111 +#define mpx_and mpx_bit0001 +#define mpx_or mpx_bit0111 #define mpx_nand mpx_bit1110 -#define mpx_nor mpx_bit1000 -#define mpx_xor mpx_bit0110 +#define mpx_nor mpx_bit1000 +#define mpx_xor mpx_bit0110 /* --- @mpx_not@ --- * * @@ -544,6 +507,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 +570,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 @@ -694,7 +690,7 @@ extern void mpx_usqr(mpw */*dv*/, mpw */*dvl*/, * Arguments: @mpw *qv, *qvl@ = quotient vector base and limit * @mpw *rv, *rvl@ = dividend/remainder vector base and limit * @const mpw *dv, *dvl@ = divisor vector base and limit - * @mpw *sv, *svl@ = scratch workspace + * @mpw *sv, *svl@ = scratch workspace * * Returns: --- * @@ -733,20 +729,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 +749,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 +773,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*/,