X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/698bd937e9f4e5e32d536757fc0631bc8e7b9d85..d1c733526062c5e1a2fb87edc35ebbaa4f9aa0fc:/mpx.h diff --git a/mpx.h b/mpx.h index 076f14a..948e7dd 100644 --- a/mpx.h +++ b/mpx.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mpx.h,v 1.9 1999/12/22 15:49:07 mdw Exp $ + * $Id: mpx.h,v 1.13 2002/10/06 22:52:50 mdw Exp $ * * Low level multiprecision arithmetic * @@ -30,6 +30,18 @@ /*----- 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. * @@ -142,25 +154,24 @@ */ #define MPX_OCTETS(o, v, vl) do { \ - const mpw *_v = (v), *_vl = (vl); \ - MPX_SHRINK(_v, _vl); \ - if (_v == _vl) \ - (o) = 0; \ - else { \ - size_t _o = (MPW_BITS / 8) * (_vl - _v - 1); \ - mpw _w = _vl[-1]; \ - unsigned _k = MPW_BITS / 2; \ - while (_k >= 8) { \ - if (_w >> _k) { \ - _w >>= _k; \ - _o += _k >> 3; \ - } \ - _k >>= 1; \ - } \ - if (_w) \ - _o++; \ - (o) = _o; \ - } \ + unsigned long _bb; \ + MPX_BITS(_bb, (v), (vl)); \ + (o) = (_bb + 7) >> 3; \ +} while (0) + +/* --- @MPX_OCTETS2C@ --- * + * + * Arguments: @size_t o@ = result variable + * @const mpw *v, *vl@ = pointer to array of words + * + * Use: Calculates the number of octets in a multiprecision value, if + * you represent it as two's complement. + */ + +#define MPX_OCTETS2C(o, v, vl) do { \ + unsigned long _bb; \ + MPX_BITS(_bb, (v), (vl)); \ + (o) = (_bb >> 3) + 1; \ } while (0) /* --- @MPX_COPY@ --- * @@ -266,6 +277,75 @@ extern void mpx_storeb(const mpw */*v*/, const mpw */*vl*/, extern void mpx_loadb(mpw */*v*/, mpw */*vl*/, const void */*p*/, size_t /*sz*/); +/* --- @mpx_storel2cn@ --- * + * + * Arguments: @const mpw *v, *vl@ = base and limit of source vector + * @void *pp@ = pointer to octet array + * @size_t sz@ = size of octet array + * + * Returns: --- + * + * Use: Stores a negative MP in an octet array, least significant + * octet first, as two's complement. High-end octets are + * silently discarded if there isn't enough space for them. + * This obviously makes the output bad. + */ + +extern void mpx_storel2cn(const mpw */*v*/, const mpw */*vl*/, + void */*p*/, size_t /*sz*/); + +/* --- @mpx_loadl2cn@ --- * + * + * Arguments: @mpw *v, *vl@ = base and limit of destination vector + * @const void *pp@ = pointer to octet array + * @size_t sz@ = size of octet array + * + * Returns: --- + * + * Use: Loads a negative MP in an octet array, least significant + * octet first, as two's complement. High-end octets are + * ignored if there isn't enough space for them. This probably + * means you made the wrong choice coming here. + */ + +extern void mpx_loadl2cn(mpw */*v*/, mpw */*vl*/, + const void */*p*/, size_t /*sz*/); + +/* --- @mpx_storeb2cn@ --- * + * + * Arguments: @const mpw *v, *vl@ = base and limit of source vector + * @void *pp@ = pointer to octet array + * @size_t sz@ = size of octet array + * + * Returns: --- + * + * Use: Stores a negative MP in an octet array, most significant + * octet first, as two's complement. High-end octets are + * silently discarded if there isn't enough space for them, + * which probably isn't what you meant. + */ + +extern void mpx_storeb2cn(const mpw */*v*/, const mpw */*vl*/, + void */*p*/, size_t /*sz*/); + +/* --- @mpx_loadb2cn@ --- * + * + * Arguments: @mpw *v, *vl@ = base and limit of destination vector + * @const void *pp@ = pointer to octet array + * @size_t sz@ = size of octet array + * + * Returns: --- + * + * Use: Loads a negative MP in an octet array, most significant octet + * first as two's complement. High-end octets are ignored if + * there isn't enough space for them. This probably means you + * chose this function wrongly. + */ + +extern void mpx_loadb2cn(mpw */*v*/, mpw */*vl*/, + const void */*p*/, size_t /*sz*/); + + /*----- Logical shifting --------------------------------------------------*/ /* --- @mpx_lsl@ --- * @@ -298,6 +378,83 @@ extern void mpx_lsr(mpw */*dv*/, mpw */*dvl*/, const mpw */*av*/, const mpw */*avl*/, size_t /*n*/); +/*----- 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 + * @const mpw *av, *avl@ = first source vector + * @const mpw *bv, *bvl@ = second source vector + * + * Returns: --- + * + * Use: Provide the dyadic boolean functions. The functions are + * named after the truth table they generate: + * + * a: 0011 + * b: 0101 + * @mpx_bitXXXX@ + */ + +#define MPX_DOBIN(what) \ + what(0000) what(0001) what(0010) what(0011) \ + what(0100) what(0101) what(0110) what(0111) \ + what(1000) what(1001) what(1010) what(1011) \ + what(1100) what(1101) what(1110) what(1111) + +#define MPX_BITDECL(string) \ + extern void mpx_bit##string(mpw */*dv*/, mpw */*dvl*/, \ + const mpw */*av*/, const mpw */*avl*/, \ + const mpw */*bv*/, const mpw */*bvl*/); +MPX_DOBIN(MPX_BITDECL) + +/* --- @mpx_[n]and@, @mpx_[n]or@, @mpx_xor@ --- * + * + * Synonyms for the commonly-used functions above. + */ + +#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 + +/* --- @mpx_not@ --- * + * + * Arguments: @mpw *dv, *dvl@ = destination vector + * @const mpw *av, *avl@ = first source vector + * + * Returns: --- + * + * Use; Bitwise NOT. + */ + +extern void mpx_not(mpw */*dv*/, mpw */*dvl*/, + const mpw */*av*/, const mpw */*avl*/); + /*----- Unsigned arithmetic -----------------------------------------------*/ /* --- @mpx_2c@ --- * @@ -313,6 +470,19 @@ extern void mpx_lsr(mpw */*dv*/, mpw */*dvl*/, extern void mpx_2c(mpw */*dv*/, mpw */*dvl*/, const mpw */*v*/, const mpw */*vl*/); +/* --- @mpx_ueq@ --- * + * + * Arguments: @const mpw *av, *avl@ = first argument vector base and limit + * @const mpw *bv, *bvl@ = second argument vector base and limit + * + * Returns: Nonzero if the two vectors are equal. + * + * Use: Performs an unsigned integer test for equality. + */ + +extern int mpx_ueq(const mpw */*av*/, const mpw */*avl*/, + const mpw */*bv*/, const mpw */*bvl*/); + /* --- @mpx_ucmp@ --- * * * Arguments: @const mpw *av, *avl@ = first argument vector base and limit @@ -559,23 +729,23 @@ extern mpw mpx_udivn(mpw */*qv*/, mpw */*qvl*/, /*----- Karatsuba multiplication algorithms -------------------------------*/ -/* --- @KARATSUBA_CUTOFF@ --- * +/* --- @MPK_THRESH@ --- * * * This is the limiting length for using Karatsuba algorithms. It's best to * use the simpler classical multiplication method on numbers smaller than * this. */ -#define KARATSUBA_CUTOFF 16 +#define MPK_THRESH 16 -/* --- @KARATSUBA_SLOP@ --- * +/* --- @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 KARATSUBA_SLOP 64 +#define MPK_SLOP 64 /* --- @mpx_kmul@ --- * * @@ -594,7 +764,7 @@ extern mpw mpx_udivn(mpw */*qv*/, mpw */*qvl*/, * 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 - * @KARATSUBA_SLOP@. + * @MPK_SLOP@. */ extern void mpx_kmul(mpw */*dv*/, mpw */*dvl*/, @@ -618,7 +788,7 @@ extern void mpx_kmul(mpw */*dv*/, mpw */*dvl*/, * * 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 @KARATSUBA_SLOP@. + * the magic number @MPK_SLOP@. */ extern void mpx_ksqr(mpw */*dv*/, mpw */*dvl*/,