X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/d03ab969116fe715d569304c1c474749b2f64529..d34decd2b2b88240cf4ca68a2a5feb7bf36de6e7:/mp.h diff --git a/mp.h b/mp.h index fcccee2..92f1209 100644 --- a/mp.h +++ b/mp.h @@ -1,8 +1,8 @@ /* -*-c-*- * - * $Id: mp.h,v 1.1 1999/09/03 08:41:12 mdw Exp $ + * $Id: mp.h,v 1.7 2000/06/17 11:45:09 mdw Exp $ * - * Multiprecision arithmetic + * Simple multiprecision arithmetic * * (c) 1999 Straylight/Edgeware */ @@ -30,13 +30,30 @@ /*----- Revision history --------------------------------------------------* * * $Log: mp.h,v $ - * Revision 1.1 1999/09/03 08:41:12 mdw - * Initial import. + * Revision 1.7 2000/06/17 11:45:09 mdw + * Major memory management overhaul. Added arena support. Use the secure + * arena for secret integers. Replace and improve the MP management macros + * (e.g., replace MP_MODIFY by MP_DEST). + * + * Revision 1.6 1999/12/10 23:19:46 mdw + * Minor bugfixes. New interface for suggested destinations. + * + * Revision 1.5 1999/11/22 20:50:37 mdw + * Add support for computing Jacobi symbols. + * + * Revision 1.4 1999/11/21 22:13:02 mdw + * Add mp version of MPX_BITS. + * + * Revision 1.3 1999/11/19 13:19:14 mdw + * Fix const annotation. + * + * Revision 1.2 1999/11/17 18:02:16 mdw + * New multiprecision integer arithmetic suite. * */ -#ifndef MP_H -#define MP_H +#ifndef CATACOMB_MP_H +#define CATACOMB_MP_H #ifdef __cplusplus extern "C" { @@ -44,401 +61,615 @@ /*----- Header files ------------------------------------------------------*/ -#include +#include #include -#ifndef MPTYPES_H -# include "mptypes.h" +#include + +#ifndef CATACOMB_MPW_H +# include "mpw.h" #endif -#ifndef MPX_H -# include "mpx.h" +#ifndef CATACOMB_ARENA_H +# include "arena.h" #endif -#ifndef MPSCAN_H -# include "mpscan.h" +#ifndef CATACOMB_MPARENA_H +# include "mparena.h" +#endif + +#ifndef CATACOMB_MPX_H +# include "mpx.h" #endif /*----- Data structures ---------------------------------------------------*/ typedef struct mp { - mpw *v; /* Vector of words */ - unsigned f; /* Various flags */ - size_t sz; /* Size allocated to word vector */ - size_t len; /* Length of current word vector */ + mpw *v, *vl; + size_t sz; + mparena *a; + unsigned f; + unsigned ref; } mp; -enum { - MPF_SIGN = 1, /* Sign bit */ - MPF_BURN = 2 /* Burn word vector after use */ -}; +#define MP_NEG 1u +#define MP_BURN 2u +#define MP_CONST 4u +#define MP_UNDEF 8u +#define MP_DESTROYED 16u -typedef struct mp_bitscan { - const mp *x; /* Pointer to target MP */ - size_t i; /* Index into MP vector */ - mpw w; /* Current value being examined */ - unsigned bits; /* Number of bits left in @w@ */ -} mp_bitscan; +/*----- Useful constants --------------------------------------------------*/ -/*----- External variables ------------------------------------------------*/ +extern mp mp_const[]; -extern mp mp_std; +#define MP_ZERO (&mp_const[0]) +#define MP_ONE (&mp_const[1]) +#define MP_TWO (&mp_const[2]) +#define MP_THREE (&mp_const[3]) +#define MP_FOUR (&mp_const[4]) +#define MP_FIVE (&mp_const[5]) +#define MP_TEN (&mp_const[6]) +#define MP_256 (&mp_const[7]) +#define MP_MONE (&mp_const[8]) -#define MP_ZERO (mp_std + 0) -#define MP_ONE (mp_std + 1) -#define MP_TWO (mp_std + 2) -#define MP_THREE (mp_std + 3) -#define MP_FOUR (mp_std + 4) -#define MP_FIVE (mp_std + 5) -#define MP_TEN (mp_std + 6) -#define MP_MONE (mp_std + 7) +#define MP_NEW ((mp *)0) +#define MP_NEWSEC (&mp_const[9]) -/*----- Memory allocation and low-level fiddling --------------------------*/ +/*----- Trivial macros ----------------------------------------------------*/ -/* --- @mp_create@ --- * +/* --- @MP_LEN@ --- * * - * Arguments @mp *x@ = pointer to MP head + * Arguments: @mp *m@ = pointer to a multiprecision integer * - * Returns: --- - * - * Use: Initializes an MP ready for use. The initial value is zero. + * Returns: Length of the integer, in words. */ -#define MP_INIT { 0, 0, 0, 0 } +#define MP_LEN(m) ((m)->vl - ((m)->v)) -extern void mp_create(mp */*x*/); +/*----- Memory management and reference counting --------------------------*/ -/* --- @MP_BURN@ --- * +/* --- @mp_new@ --- * + * + * Arguments: @size_t sz@ = size of vector required + * @unsigned f@ = flags to set * - * Arguments: @x@ = pointer to MP head + * Returns: Pointer to a new MP structure. * - * Use: Burns the contents of the MP, if it contains sensitive data. + * Use: Allocates a new multiprecision integer. The data space is + * allocated from either the standard global or secret arena, + * depending on the initial flags requested. */ -#define MP_BURN(x) do { \ - mp *_y = (x) \ - if (_y->v && _y->f & mpf_burn) { \ - memset(_y->v, 0, _y->sz * sizeof(mpw)); \ - _y->f &= ~MPF_BURN; \ - } \ -} while (0) +extern mp *mp_new(size_t /*sz*/, unsigned /*f*/); -/* --- @mp_free@ --- * +/* --- @mp_create@ --- * * - * Arguments: @mp *x@ = pointer to MP head + * Arguments: @size_t sz@ = size of vector required * - * Returns: --- + * Returns: Pointer to pristine new MP structure with enough memory + * bolted onto it. * - * Use: Releases the memory used by an MP. + * Use: Creates a new multiprecision integer with indeterminate + * contents. The integer has a single reference. */ -#define MP_DESTROY(x) do { \ - mp *_x = (x); \ - MP_BURN(_x); \ - if (_x->v) \ - free(_x->v); \ - _x->v = 0; \ - _x->f = 0; \ - _x->sz = 0; \ - _x->len = 0; \ -} while (0) - -extern void mp_free(mp */*x*/); +extern mp *mp_create(size_t /*sz*/); -/* --- @MP_ENSURE@ --- * +/* --- @mp_createsecure@ --- * + * + * Arguments: @size_t sz@ = size of vector required * - * Arguments: @x@ = pointer to MP head - * @len@ = length required (in words) + * Returns: Pointer to pristine new MP structure with enough memory + * bolted onto it. * - * Use: Ensures that the MP has enough memory to store a @len@-word - * value. + * Use: Creates a new multiprecision integer with indeterminate + * contents. The integer has a single reference. The integer's + * data space is allocated from the secure arena. Its burn flag + * is set. */ -#define MP_ENSURE(x, len) do { \ - mp *_x = (x); \ - size_t _len = (len); \ - if (_x->sz < _len) \ - mp_resize(_x, _len); \ -} while (0) +extern mp *mp_createsecure(size_t /*sz*/); -/* --- @mp_resize@ --- * +/* --- @mp_build@ --- * * - * Arguments: @mp *x@ = pointer to MP head - * @size_t sz@ = size required (in words) + * Arguments: @mp *m@ = pointer to an MP block to fill in + * @mpw *v@ = pointer to a word array + * @mpw *vl@ = pointer just past end of array * * Returns: --- * - * Use: Resizes the MP so that its word vector has space for - * exactly @sz@ words. + * Use: Creates a multiprecision integer representing some smallish + * number. You must provide storage for the number and dispose + * of it when you've finished with it. The number is marked as + * constant while it exists. */ -extern void mp_resize(mp */*x*/, size_t /*sz*/); +extern void mp_build(mp */*m*/, mpw */*v*/, mpw */*vl*/); -/* --- @mp_norm@ --- * +/* --- @mp_destroy@ --- * * - * Arguments: @mp *x@ = pointer to MP head + * Arguments: @mp *m@ = pointer to a multiprecision integer * * Returns: --- * - * Use: `Normalizes' an MP. Fixes the @len@ field so that it's - * correct. Assumes that @len@ is either already correct or - * too large. + * Use: Destroys a multiprecision integer. The reference count isn't + * checked. Don't use this function if you don't know what + * you're doing: use @mp_drop@ instead. */ -#define MP_NORM(x) do { \ - mp *_y = (x); \ - MPX_LEN(_y->len, _y->v, _y->len); \ -} while (0) +extern void mp_destroy(mp */*m*/); + +/* --- @mp_copy@ --- * + * + * Arguments: @mp *m@ = pointer to a multiprecision integer + * + * Returns: A copy of the given multiprecision integer. + * + * Use: Copies the given integer. In fact you just get another + * reference to the same old one again. + */ -extern void mp_norm(mp */*x*/); +extern mp *mp_copy(mp */*m*/); -/* --- @mp_dump@ --- * +#define MP_COPY(m) ((m)->ref++, (m)) + +/* --- @mp_drop@ --- * * - * Arguments: @mp *x@ = pointer to MP head - * @FILE *fp@ = pointer to stream to write on + * Arguments: @mp *m@ = pointer to a multiprecision integer * * Returns: --- * - * Use: Dumps an MP to a stream. + * Use: Drops a reference to an integer which isn't wanted any more. + * If there are no more references, the integer is destroyed. */ -extern void mp_dump(mp */*x*/, FILE */*fp*/); +extern void mp_drop(mp */*m*/); -/* --- @MP_PARANOID@ --- * +#define MP_DROP(m) do { \ + mp *_mm = (m); \ + _mm->ref--; \ + if (_mm->ref == 0 && !(_mm->f & MP_CONST)) \ + mp_destroy(_mm); \ +} while (0) + +/* --- @mp_split@ --- * + * + * Arguments: @mp *m@ = pointer to a multiprecision integer * - * Arguments: @x@ = pointer to MP head + * Returns: A reference to the same integer, possibly with a different + * address. * - * Use: Marks the MP as containing sensitive data which should be - * burnt when no longer required. + * Use: Splits off a modifiable version of the integer referred to. */ -#define MP_PARANOID(x) ((x)->f |= MPF_BURN) +extern mp *mp_split(mp */*m*/); + +#define MP_SPLIT(m) do { \ + mp *_m = (m); \ + if ((_m->f & MP_CONST) || _m->ref > 1) { \ + size_t _len = MP_LEN(_m); \ + mp *_mm = mp_new(_len, _m->f); \ + if (!(_m->f & MP_UNDEF)) \ + memcpy(_mm->v, _m->v, MPWS(_len)); \ + _m->ref--; \ + _m = _mm; \ + } \ + (m) = _m; \ +} while (0) -/* --- @mp_copy@ --- * +/* --- @mp_resize@ --- * * - * Arguments: @mp *d@ = pointer to MP head for destination - * @const mp *s@ = pointer to MP head for source + * Arguments: @mp *m@ = pointer to a multiprecision integer + * @size_t sz@ = new size * * Returns: --- * - * Use: Copies an MP. + * Use: Resizes the vector containing the integer's digits. The new + * size must be at least as large as the current integer's + * length. This isn't really intended for client use. */ -extern void mp_copy(mp */*d*/, const mp */*s*/); +extern void mp_resize(mp */*m*/, size_t /*sz*/); + +#define MP_RESIZE(m, ssz) do { \ + mp *_m = (m); \ + size_t _sz = (ssz); \ + mparena *_a = (_m->f & MP_BURN) ? MPARENA_SECURE : MPARENA_GLOBAL; \ + mpw *_v; \ + size_t _len = MP_LEN(_m); \ + assert(((void)"can't make size less than length", _sz >= _len)); \ + _v = mpalloc(_a, _sz); \ + if (!(_m->f & MP_UNDEF)) \ + memcpy(_v, _m->v, MPWS(_len)); \ + if (_m->f & MP_BURN) \ + memset(_m->v, 0, MPWS(_m->sz)); \ + mpfree(_m->a, _m->v); \ + _m->a = _a; \ + _m->v = _v; \ + _m->vl = _v + _len; \ +} while (0) -/* --- @mp_bits@ --- * +/* --- @mp_ensure@ --- * * - * Arguments: @mp *x@ = pointer to MP head + * Arguments: @mp *m@ = pointer to a multiprecision integer + * @size_t sz@ = required size * - * Returns: Length of the number in bits. + * Returns: --- * - * Use: Calculates the number of bits required to represent a number. - * The number must be normalized. + * Use: Ensures that the integer has enough space for @sz@ digits. + * The value is not changed. */ -unsigned long mp_bits(mp */*x*/); +extern void mp_ensure(mp */*m*/, size_t /*sz*/); + +#define MP_ENSURE(m, ssz) do { \ + mp *_m = (m); \ + size_t _ssz = (ssz); \ + size_t _len = MP_LEN(_m); \ + if (_ssz >= _len) { \ + if (_ssz > _m->sz) \ + mp_resize(_m, _ssz); \ + if (!(_m->f & MP_UNDEF) && _ssz > _len) \ + memset(_m->vl, 0, MPWS(_ssz - _len)); \ + _m->vl = _m->v + _ssz; \ + } \ +} while (0) -/* --- @mp_octets@ --- * +/* --- @mp_dest@ --- * + * + * Arguments: @mp *m@ = a suggested destination integer + * @size_t sz@ = size required for result, in digits + * @unsigned f@ = various flags * - * Arguments: @mp *x@ = pointer to MP head + * Returns: A pointer to an appropriate destination. * - * Returns: Length of number in octets. + * Use: Converts a suggested destination into a real destination with + * the required properties. If the real destination is @d@, + * then the following properties will hold: * - * Use: Calculates the number of octets required to represent a - * number. The number must be normalized. + * * @d@ will have exactly one reference. + * + * * If @m@ is not @MP_NEW@, then the contents of @m@ will not + * change, unless @f@ has the @MP_UNDEF@ flag set. + * + * * If @m@ is not @MP_NEW@, then he reference count of @m@ on + * entry is equal to the sum of the counts of @d@ and @m@ on + * exit. + * + * * The size of @d@ will be at least @sz@. + * + * * If @f@ has the @MP_BURN@ flag set, then @d@ will be + * allocated from @MPARENA_SECURE@. + * + * Understanding this function is crucial to using Catacomb's + * multiprecision integer library effectively. */ -extern size_t mp_octets(mp */*x*/); +extern mp *mp_dest(mp */*m*/, size_t /*sz*/, unsigned /*f*/); + +#define MP_DEST(m, ssz, f) do { \ + mp *_m = (m); \ + size_t _ssz = (ssz); \ + unsigned _f = (f); \ + _m = mp_dest(_m, _ssz, _f); \ + (m) = _m; \ +} while (0) -/*----- Loading and storing as binary data --------------------------------*/ +/*----- Size manipulation -------------------------------------------------*/ -/* --- @mp_storel@ --- * +/* --- @mp_shrink@ --- * * - * Arguments: @mp *x@ = pointer to MP head - * @octet *p@ = pointer to octet array - * @size_t sz@ = size of octet array + * Arguments: @mp *m@ = pointer to a multiprecision integer * * Returns: --- * - * Use: Stores an MP in an octet array, least significant octet - * first. High-end octets are silently discarded if there - * isn't enough space for them. + * Use: Reduces the recorded length of an integer. This doesn't + * reduce the amount of memory used, although it can improve + * performance a bit. To reduce memory, use @mp_minimize@ + * instead. This can't change the value of an integer, and is + * therefore safe to use even when there are multiple + * references. */ -extern void mp_storel(mp */*x*/, octet */*p*/, size_t /*sz*/); +extern void mp_shrink(mp */*m*/); -/* --- @mp_loadl@ --- * +#define MP_SHRINK(m) do { \ + mp *_mm = (m); \ + MPX_SHRINK(_mm->v, _mm->vl); \ + if (!MP_LEN(_mm)) \ + _mm->f &= ~MP_NEG; \ +} while (0) + +/* --- @mp_minimize@ --- * * - * Arguments: @mp *x@ = pointer to MP head - * @const octet *p@ = pointer to octet array - * @size_t sz@ = size of octet array + * Arguments: @mp *m@ = pointer to a multiprecision integer * * Returns: --- * - * Use: Loads an MP in an octet array, least significant octet - * first. + * Use: Reduces the amount of memory an integer uses. It's best to + * do this to numbers which aren't going to change in the + * future. */ -extern void mp_loadl(mp */*x*/, const octet */*p*/, size_t /*sz*/); +extern void mp_minimize(mp */*m*/); -/* --- @mp_storeb@ --- * +/*----- Bit scanning ------------------------------------------------------*/ + +#ifndef CATACOMB_MPSCAN_H +# include "mpscan.h" +#endif + +/* --- @mp_scan@ --- * * - * Arguments: @mp *x@ = pointer to MP head - * @octet *p@ = pointer to octet array - * @size_t sz@ = size of octet array + * Arguments: @mpscan *sc@ = pointer to bitscanner block + * @const mp *m@ = pointer to a multiprecision integer * * Returns: --- * - * Use: Stores an MP in an octet array, most significant octet - * first. High-end octets are silently discarded if there - * isn't enough space for them. + * Use: Initializes a bitscanner on a multiprecision integer. */ -extern void mp_storeb(mp */*x*/, octet */*p*/, size_t /*sz*/); +extern void mp_scan(mpscan */*sc*/, const mp */*m*/); -/* --- @mp_loadb@ --- * +#define MP_SCAN(sc, m) do { \ + const mp *_mm = (m); \ + mpscan *_sc = (sc); \ + MPSCAN_INITX(_sc, _mm->v, _mm->vl); \ +} while (0) + +/* --- Other bitscanning aliases --- */ + +#define mp_step mpscan_step +#define mp_bit mpscan_bit + +#define MP_STEP MPSCAN_STEP +#define MP_BIT MPSCAN_BIT + +/*----- Loading and storing -----------------------------------------------*/ + +/* --- @mp_octets@ --- * * - * Arguments: @mp *x@ = pointer to MP head - * @const octet *p@ = pointer to octet array - * @size_t sz@ = size of octet array + * Arguments: @const mp *m@ = a multiprecision integer * - * Returns: --- + * Returns: The number of octets required to represent @m@. + * + * Use: Calculates the external storage required for a multiprecision + * integer. + */ + +extern size_t mp_octets(const mp */*m*/); + +/* --- @mp_bits@ --- * * - * Use: Loads an MP in an octet array, most significant octet - * first. + * Arguments: @const mp *m@ = a multiprecision integer + * + * Returns: The number of bits required to represent @m@. + * + * Use: Calculates the external storage required for a multiprecision + * integer. */ -extern void mp_loadb(mp */*x*/, const octet */*p*/, size_t /*sz*/); +extern unsigned long mp_bits(const mp */*m*/); + +/* --- @mp_loadl@ --- * + * + * Arguments: @mp *d@ = destination + * @const void *pv@ = pointer to source data + * @size_t sz@ = size of the source data + * + * Returns: Resulting multiprecision number. + * + * Use: Loads a multiprecision number from an array of octets. The + * first byte in the array is the least significant. More + * formally, if the bytes are %$b_0, b_1, \ldots, b_{n-1}$% + * then the result is %$N = \sum_{0 \le i < n} b_i 2^{8i}$%. + */ -/*----- Iterating through bits --------------------------------------------*/ +extern mp *mp_loadl(mp */*d*/, const void */*pv*/, size_t /*sz*/); -/* --- @mp_mkbitscan@ --- * +/* --- @mp_storel@ --- * * - * Arguments: @mp_bitscan *sc@ = pointer to bitscan object - * @const mp *x@ = pointer to MP head + * Arguments: @const mp *m@ = source + * @void *pv@ = pointer to output array + * @size_t sz@ = size of the output array * * Returns: --- * - * Use: Initializes a bitscan object. + * Use: Stores a multiprecision number in an array of octets. The + * first byte in the array is the least significant. If the + * array is too small to represent the number, high-order bits + * are truncated; if the array is too large, high order bytes + * are filled with zeros. More formally, if the number is + * %$N = \sum{0 \le i} b_i 2^{8i}$% where %$0 \le b_i < 256$%, + * then the array is %$b_0, b_1, \ldots, b_{n-1}$%. */ -extern void mp_mkbitscan(mp_bitscan */*sc*/, const mp */*x*/); +extern void mp_storel(const mp */*m*/, void */*pv*/, size_t /*sz*/); -/* --- @mp_bstep@ --- * +/* --- @mp_loadb@ --- * * - * Arguments: @mp_bitscan *sc@ = pointer to bitscanner object + * Arguments: @mp *d@ = destination + * @const void *pv@ = pointer to source data + * @size_t sz@ = size of the source data * - * Returns: Nonzero if there is another bit to read. + * Returns: Resulting multiprecision number. * - * Use: Steps on to the next bit, and tells the caller whether one - * exists. + * Use: Loads a multiprecision number from an array of octets. The + * last byte in the array is the least significant. More + * formally, if the bytes are %$b_{n-1}, b_{n-2}, \ldots, b_0$% + * then the result is %$N = \sum_{0 \le i < n} b_i 2^{8i}$%. */ -extern int mp_bstep(mp_bitscan */*sc*/); +extern mp *mp_loadb(mp */*d*/, const void */*pv*/, size_t /*sz*/); -/* --- @mp_bit@ --- * +/* --- @mp_storeb@ --- * + * + * Arguments: @const mp *m@ = source + * @void *pv@ = pointer to output array + * @size_t sz@ = size of the output array * - * Arguments: @const mp_bitscan *sc@ = pointer to bitscanner + * Returns: --- + * + * Use: Stores a multiprecision number in an array of octets. The + * last byte in the array is the least significant. If the + * array is too small to represent the number, high-order bits + * are truncated; if the array is too large, high order bytes + * are filled with zeros. More formally, if the number is + * %$N = \sum{0 \le i} b_i 2^{8i}$% where %$0 \le b_i < 256$%, + * then the array is %$b_{n-1}, b_{n-2}, \ldots, b_0$%. + */ + +extern void mp_storeb(const mp */*m*/, void */*pv*/, size_t /*sz*/); + +/*----- Simple arithmetic -------------------------------------------------*/ + +/* --- @mp_2c@ --- * * - * Returns: Current bit value. + * Arguments: @mp *d@ = destination + * @mp *a@ = source * - * Use: Returns the value of the current bit. + * Returns: Result, @a@ converted to two's complement notation. */ -#define MP_BIT(sc) ((sc)->w & 1) +extern mp *mp_2c(mp */*d*/, mp */*a*/); -extern int mp_bit(const mp_bitscan */*sc*/); +/* --- @mp_sm@ --- * + * + * Arguments: @mp *d@ = destination + * @mp *a@ = source + * + * Returns: Result, @a@ converted to the native signed-magnitude + * notation. + */ -/*----- Shifting ----------------------------------------------------------*/ +extern mp *mp_sm(mp */*d*/, mp */*a*/); /* --- @mp_lsl@ --- * * - * Arguments: @mp *d@ = pointer to MP head of destination - * @const mp *x@ = pointer to MP head of source - * @size_t n@ = number of bits to shift - * - * Returns: --- + * Arguments: @mp *d@ = destination + * @mp *a@ = source + * @size_t n@ = number of bits to move * - * Use: Shifts a number left by a given number of bit positions. + * Returns: Result, @a@ shifted left by @n@. */ -extern void mp_lsl(mp */*d*/, const mp */*x*/, size_t /*n*/); +extern mp *mp_lsl(mp */*d*/, mp */*a*/, size_t /*n*/); /* --- @mp_lsr@ --- * * - * Arguments: @mp *d@ = pointer to MP head of destination - * @const mp *x@ = pointer to MP head of source - * @size_t n@ = number of bits to shift + * Arguments: @mp *d@ = destination + * @mp *a@ = source + * @size_t n@ = number of bits to move * - * Returns: --- + * Returns: Result, @a@ shifted left by @n@. + */ + +extern mp *mp_lsr(mp */*d*/, mp */*a*/, size_t /*n*/); + +/* --- @mp_cmp@ --- * * - * Use: Shifts a number right by a given number of bit positions. + * Arguments: @const mp *a, *b@ = two numbers + * + * Returns: Less than, equal to or greater than zero, according to + * whether @a@ is less than, equal to or greater than @b@. */ -extern void mp_lsr(mp */*d*/, const mp */*x*/, size_t /*n*/); +extern int mp_cmp(const mp */*a*/, const mp */*b*/); -/*----- Unsigned arithmetic -----------------------------------------------*/ +#define MP_CMP(a, op, b) (mp_cmp((a), (b)) op 0) -/* --- @mp_uadd@ --- * - * - * Arguments: @const mp *d@ = pointers to MP head of destination - * @const mp *x, *y@ = pointers to MP heads of operands +/* --- @mp_add@ --- * * - * Returns: --- + * Arguments: @mp *d@ = destination + * @mp *a, *b@ = sources * - * Use: Performs unsigned MP addition. + * Returns: Result, @a@ added to @b@. */ -extern void mp_uadd(mp */*d*/, const mp */*x*/, const mp */*y*/); +extern mp *mp_add(mp */*d*/, mp */*a*/, mp */*b*/); -/* --- @mp_usub@ --- * +/* --- @mp_sub@ --- * * - * Arguments: @const mp *d@ = pointers to MP head of destination - * @const mp *x, *y@ = pointers to MP heads of operands + * Arguments: @mp *d@ = destination + * @mp *a, *b@ = sources * - * Returns: --- + * Returns: Result, @b@ subtracted from @a@. + */ + +extern mp *mp_sub(mp */*d*/, mp */*a*/, mp */*b*/); + +/* --- @mp_mul@ --- * * - * Use: Performs unsigned MP subtraction. + * Arguments: @mp *d@ = destination + * @mp *a, *b@ = sources + * + * Returns: Result, @a@ multiplied by @b@. */ -extern void mp_usub(mp */*d*/, const mp */*x*/, const mp */*y*/); +extern mp *mp_mul(mp */*d*/, mp */*a*/, mp */*b*/); -/* --- @mp_ucmp@ --- * +/* --- @mp_sqr@ --- * * - * Arguments: @const mp *x, *y@ = pointers to MP heads of operands + * Arguments: @mp *d@ = destination + * @mp *a@ = source * - * Returns: Less than, equal to, or greater than zero. + * Returns: Result, @a@ squared. + */ + +extern mp *mp_sqr(mp */*d*/, mp */*a*/); + +/* --- @mp_div@ --- * * - * Use: Performs unsigned MP comparison. + * Arguments: @mp **qq, **rr@ = destination, quotient and remainder + * @mp *a, *b@ = sources + * + * Use: Calculates the quotient and remainder when @a@ is divided by + * @b@. */ -#define MP_UCMP(x, op, y) (mp_ucmp((x), (y)) op 0) +extern void mp_div(mp **/*qq*/, mp **/*rr*/, mp */*a*/, mp */*b*/); -extern int mp_ucmp(const mp */*x*/, const mp */*y*/); +/*----- More advanced algorithms ------------------------------------------*/ -/* --- @mp_umul@ --- * +/* --- @mp_gcd@ --- * * - * Arguments: @mp *d@ = pointer to MP head of destination - * @const mp *x, *y@ = pointes to MP heads of operands + * Arguments: @mp **gcd, **xx, **yy@ = where to write the results + * @mp *a, *b@ = sources (must be nonzero) * * Returns: --- * - * Use: Performs unsigned MP multiplication. + * Use: Calculates @gcd(a, b)@, and two numbers @x@ and @y@ such that + * @ax + by = gcd(a, b)@. This is useful for computing modular + * inverses. Neither @a@ nor @b@ may be zero. */ -extern void mp_umul(mp */*d*/, const mp */*x*/, const mp */*y*/); +extern void mp_gcd(mp **/*gcd*/, mp **/*xx*/, mp **/*yy*/, + mp */*a*/, mp */*b*/); -/* --- @mp_udiv@ --- * +/* --- @mp_jacobi@ --- * * - * Arguments: @mp *q, *r@ = pointers to MP heads for quotient, remainder - * @const mp *x, *y@ = pointers to MP heads for operands + * Arguments: @mp *a@ = an integer less than @n@ + * @mp *n@ = an odd integer * - * Returns: --- + * Returns: @-1@, @0@ or @1@ -- the Jacobi symbol %$J(a, n)$%. * - * Use: Performs unsigned MP division. + * Use: Computes the Jacobi symbol. If @n@ is prime, this is the + * Legendre symbol and is equal to 1 if and only if @a@ is a + * quadratic residue mod @n@. The result is zero if and only if + * @a@ and @n@ have a common factor greater than one. */ -extern void mp_udiv(mp */*q*/, mp */*r*/, const mp */*x*/, const mp */*y*/); +int mp_jacobi(mp */*a*/, mp */*n*/); + +/*----- Test harness support ----------------------------------------------*/ + +#include + +#ifndef CATACOMB_MPTEXT_H +# include "mptext.h" +#endif + +extern const test_type type_mp; /*----- That's all, folks -------------------------------------------------*/