X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/75263f25a1ce8e7b38ad4bd61a9a893723ec1db3..6ec3a4cf4aaa7cd375e1aa18f85861986259b8e5:/mpx.h diff --git a/mpx.h b/mpx.h index 3364137..19f5cc7 100644 --- a/mpx.h +++ b/mpx.h @@ -1,13 +1,13 @@ /* -*-c-*- * - * $Id: mpx.h,v 1.15 2002/10/19 17:56: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,68 +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.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. - * - * 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 @@ -137,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; \ @@ -217,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@ --- * @@ -369,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 @@ -419,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@ --- * * @@ -527,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 @@ -574,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 @@ -677,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: --- *