X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/24e1e862d1cf06eb08af7c44468c1d12fcffc747..d34decd2b2b88240cf4ca68a2a5feb7bf36de6e7:/mp.h diff --git a/mp.h b/mp.h index 13bcd3d..92f1209 100644 --- a/mp.h +++ b/mp.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mp.h,v 1.4 1999/11/21 22:13:02 mdw Exp $ + * $Id: mp.h,v 1.7 2000/06/17 11:45:09 mdw Exp $ * * Simple multiprecision arithmetic * @@ -30,6 +30,17 @@ /*----- Revision history --------------------------------------------------* * * $Log: mp.h,v $ + * 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. * @@ -41,8 +52,8 @@ * */ -#ifndef MP_H -#define MP_H +#ifndef CATACOMB_MP_H +#define CATACOMB_MP_H #ifdef __cplusplus extern "C" { @@ -55,11 +66,19 @@ #include -#ifndef MPW_H +#ifndef CATACOMB_MPW_H # include "mpw.h" #endif -#ifndef MPX_H +#ifndef CATACOMB_ARENA_H +# include "arena.h" +#endif + +#ifndef CATACOMB_MPARENA_H +# include "mparena.h" +#endif + +#ifndef CATACOMB_MPX_H # include "mpx.h" #endif @@ -68,6 +87,7 @@ typedef struct mp { mpw *v, *vl; size_t sz; + mparena *a; unsigned f; unsigned ref; } mp; @@ -76,6 +96,7 @@ typedef struct mp { #define MP_BURN 2u #define MP_CONST 4u #define MP_UNDEF 8u +#define MP_DESTROYED 16u /*----- Useful constants --------------------------------------------------*/ @@ -88,81 +109,53 @@ extern mp mp_const[]; #define MP_FOUR (&mp_const[4]) #define MP_FIVE (&mp_const[5]) #define MP_TEN (&mp_const[6]) -#define MP_MONE (&mp_const[7]) +#define MP_256 (&mp_const[7]) +#define MP_MONE (&mp_const[8]) #define MP_NEW ((mp *)0) +#define MP_NEWSEC (&mp_const[9]) -/*----- Memory allocation hooks -------------------------------------------*/ - -#ifndef MPARENA_H -# include "mparena.h" -#endif - -/* --- @MP_ARENA@ --- * - * - * This selects where memory is allocated from. Tweak to use more fancy - * things like custom arenas. - */ - -#ifndef MP_ARENA -# define MP_ARENA MPARENA_GLOBAL -#endif - -/* --- @MP_ALLOC@ --- * - * - * Arguments: @size_t sz@ = size required - * - * Returns: Pointer to an allocated vector of the requested size. - * - * Use: Hook for vector allocation. - */ - -#ifndef MP_ALLOC -# define MP_ALLOC(sz) mpalloc(MP_ARENA, (sz)) -#endif +/*----- Trivial macros ----------------------------------------------------*/ -/* --- @MP_FREE@ --- * - * - * Arguments: @mpw *v@ = pointer to vector +/* --- @MP_LEN@ --- * * - * Returns: --- + * Arguments: @mp *m@ = pointer to a multiprecision integer * - * Use: Hook for vector deallocation. + * Returns: Length of the integer, in words. */ -#ifndef MP_FREE -# define MP_FREE(v) mpfree(MP_ARENA, (v)) -#endif +#define MP_LEN(m) ((m)->vl - ((m)->v)) -/*----- Paranoia management -----------------------------------------------*/ +/*----- Memory management and reference counting --------------------------*/ -/* --- @mp_burn@ --- * +/* --- @mp_new@ --- * * - * Arguments: @mp *m@ = pointer to a multiprecision integer + * Arguments: @size_t sz@ = size of vector required + * @unsigned f@ = flags to set * - * Returns: --- + * Returns: Pointer to a new MP structure. * - * Use: Marks the integer as `burn-after-use'. When the integer's - * memory is deallocated, it is deleted so that traces can't - * remain in the swap file. In theory. + * 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. */ -extern void mp_burn(mp */*m*/); +extern mp *mp_new(size_t /*sz*/, unsigned /*f*/); -/*----- Trivial macros ----------------------------------------------------*/ - -/* --- @MP_LEN@ --- * +/* --- @mp_create@ --- * * - * Arguments: @mp *m@ = pointer to a multiprecision integer + * Arguments: @size_t sz@ = size of vector required * - * Returns: Length of the integer, in words. + * Returns: Pointer to pristine new MP structure with enough memory + * bolted onto it. + * + * Use: Creates a new multiprecision integer with indeterminate + * contents. The integer has a single reference. */ -#define MP_LEN(m) ((m)->vl - ((m)->v)) - -/*----- Memory management and reference counting --------------------------*/ +extern mp *mp_create(size_t /*sz*/); -/* --- @mp_create@ --- * +/* --- @mp_createsecure@ --- * * * Arguments: @size_t sz@ = size of vector required * @@ -170,10 +163,12 @@ extern void mp_burn(mp */*m*/); * bolted onto it. * * Use: Creates a new multiprecision integer with indeterminate - * contents. The integer has a single reference. + * contents. The integer has a single reference. The integer's + * data space is allocated from the secure arena. Its burn flag + * is set. */ -extern mp *mp_create(size_t /*sz*/); +extern mp *mp_createsecure(size_t /*sz*/); /* --- @mp_build@ --- * * @@ -232,9 +227,8 @@ extern void mp_drop(mp */*m*/); #define MP_DROP(m) do { \ mp *_mm = (m); \ - if (_mm->ref > 1) \ - _mm->ref--; \ - else if (!(_mm->f & MP_CONST)) \ + _mm->ref--; \ + if (_mm->ref == 0 && !(_mm->f & MP_CONST)) \ mp_destroy(_mm); \ } while (0) @@ -251,16 +245,16 @@ extern void mp_drop(mp */*m*/); extern mp *mp_split(mp */*m*/); #define MP_SPLIT(m) do { \ - mp *_mm = (m); \ - if ((_mm->f & MP_CONST) || _mm->ref != 1) { \ - mp *_dd = mp_create(_mm->sz); \ - _dd->vl = _dd->v + MP_LEN(_mm); \ - _dd->f = _mm->f & (MP_NEG | MP_BURN); \ - memcpy(_dd->v, _mm->v, MPWS(MP_LEN(_mm))); \ - _dd->ref = 1; \ - _mm->ref--; \ - (m) = _dd; \ + 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_resize@ --- * @@ -272,9 +266,7 @@ extern mp *mp_split(mp */*m*/); * * Use: Resizes the vector containing the integer's digits. The new * size must be at least as large as the current integer's - * length. The integer's length is increased and new digits are - * filled with zeroes. This isn't really intended for client - * use. + * length. This isn't really intended for client use. */ extern void mp_resize(mp */*m*/, size_t /*sz*/); @@ -282,15 +274,19 @@ 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); \ - mpw *_v = MP_ALLOC(_sz); \ - memcpy(_v, _m->v, MPWS(_len)); \ + 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)); \ - MP_FREE(_m->v); \ + mpfree(_m->a, _m->v); \ + _m->a = _a; \ _m->v = _v; \ _m->vl = _v + _len; \ - _m->sz = _sz; \ } while (0) /* --- @mp_ensure@ --- * @@ -307,41 +303,55 @@ extern void mp_resize(mp */*m*/, size_t /*sz*/); extern void mp_ensure(mp */*m*/, size_t /*sz*/); #define MP_ENSURE(m, ssz) do { \ - mp *_mm = (m); \ + mp *_m = (m); \ size_t _ssz = (ssz); \ - size_t _len = MP_LEN(_mm); \ - if (_ssz > _mm->sz) \ - MP_RESIZE(_mm, _ssz); \ - if (!(_mm->f & MP_UNDEF) && _ssz > _len) { \ - memset(_mm->vl, 0, MPWS(_ssz - _len)); \ - _mm->vl = _mm->v + _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_modify@ --- * +/* --- @mp_dest@ --- * * - * Arguments: @mp *m@ = pointer to a multiprecision integer - * @size_t sz@ = size required + * Arguments: @mp *m@ = a suggested destination integer + * @size_t sz@ = size required for result, in digits + * @unsigned f@ = various flags + * + * Returns: A pointer to an appropriate destination. + * + * 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: + * + * * @d@ will have exactly one reference. * - * Returns: Pointer to the integer (possibly different). + * * If @m@ is not @MP_NEW@, then the contents of @m@ will not + * change, unless @f@ has the @MP_UNDEF@ flag set. * - * Use: Prepares an integer to be overwritten. It's split off from - * other references to the same integer, and sufficient space is - * allocated. + * * 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 mp *mp_modify(mp */*m*/, size_t /*sz*/); +extern mp *mp_dest(mp */*m*/, size_t /*sz*/, unsigned /*f*/); -#define MP_MODIFY(m, sz) do { \ - size_t _rq = (sz); \ +#define MP_DEST(m, ssz, f) do { \ mp *_m = (m); \ - if (_m == MP_NEW) \ - _m = mp_create(_rq); \ - else { \ - MP_SPLIT(_m); \ - MP_ENSURE(_m, _rq); \ - } \ - _m->vl = _m->v + _rq; \ + size_t _ssz = (ssz); \ + unsigned _f = (f); \ + _m = mp_dest(_m, _ssz, _f); \ (m) = _m; \ } while (0) @@ -385,7 +395,7 @@ extern void mp_minimize(mp */*m*/); /*----- Bit scanning ------------------------------------------------------*/ -#ifndef MPSCAN_H +#ifndef CATACOMB_MPSCAN_H # include "mpscan.h" #endif @@ -537,24 +547,24 @@ extern mp *mp_sm(mp */*d*/, mp */*a*/); /* --- @mp_lsl@ --- * * * Arguments: @mp *d@ = destination - * @const mp *a@ = source + * @mp *a@ = source * @size_t n@ = number of bits to move * * Returns: Result, @a@ shifted left by @n@. */ -extern mp *mp_lsl(mp */*d*/, const mp */*a*/, size_t /*n*/); +extern mp *mp_lsl(mp */*d*/, mp */*a*/, size_t /*n*/); /* --- @mp_lsr@ --- * * * Arguments: @mp *d@ = destination - * @const mp *a@ = source + * @mp *a@ = source * @size_t n@ = number of bits to move * * Returns: Result, @a@ shifted left by @n@. */ -extern mp *mp_lsr(mp */*d*/, const mp */*a*/, size_t /*n*/); +extern mp *mp_lsr(mp */*d*/, mp */*a*/, size_t /*n*/); /* --- @mp_cmp@ --- * * @@ -571,54 +581,53 @@ extern int mp_cmp(const mp */*a*/, const mp */*b*/); /* --- @mp_add@ --- * * * Arguments: @mp *d@ = destination - * @const mp *a, *b@ = sources + * @mp *a, *b@ = sources * * Returns: Result, @a@ added to @b@. */ -extern mp *mp_add(mp */*d*/, const mp */*a*/, const mp */*b*/); +extern mp *mp_add(mp */*d*/, mp */*a*/, mp */*b*/); /* --- @mp_sub@ --- * * * Arguments: @mp *d@ = destination - * @const mp *a, *b@ = sources + * @mp *a, *b@ = sources * * Returns: Result, @b@ subtracted from @a@. */ -extern mp *mp_sub(mp */*d*/, const mp */*a*/, const mp */*b*/); +extern mp *mp_sub(mp */*d*/, mp */*a*/, mp */*b*/); /* --- @mp_mul@ --- * * * Arguments: @mp *d@ = destination - * @const mp *a, *b@ = sources + * @mp *a, *b@ = sources * * Returns: Result, @a@ multiplied by @b@. */ -extern mp *mp_mul(mp */*d*/, const mp */*a*/, const mp */*b*/); +extern mp *mp_mul(mp */*d*/, mp */*a*/, mp */*b*/); /* --- @mp_sqr@ --- * * * Arguments: @mp *d@ = destination - * @const mp *a@ = source + * @mp *a@ = source * * Returns: Result, @a@ squared. */ -extern mp *mp_sqr(mp */*d*/, const mp */*a*/); +extern mp *mp_sqr(mp */*d*/, mp */*a*/); /* --- @mp_div@ --- * * * Arguments: @mp **qq, **rr@ = destination, quotient and remainder - * @const mp *a, *b@ = sources + * @mp *a, *b@ = sources * * Use: Calculates the quotient and remainder when @a@ is divided by * @b@. */ -extern void mp_div(mp **/*qq*/, mp **/*rr*/, - const mp */*a*/, const mp */*b*/); +extern void mp_div(mp **/*qq*/, mp **/*rr*/, mp */*a*/, mp */*b*/); /*----- More advanced algorithms ------------------------------------------*/ @@ -631,19 +640,32 @@ extern void mp_div(mp **/*qq*/, mp **/*rr*/, * * 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. Note that, - * unlike @mp_div@ for example, it is not possible to specify - * explicit destinations -- new MPs are always allocated. + * inverses. Neither @a@ nor @b@ may be zero. */ extern void mp_gcd(mp **/*gcd*/, mp **/*xx*/, mp **/*yy*/, mp */*a*/, mp */*b*/); +/* --- @mp_jacobi@ --- * + * + * Arguments: @mp *a@ = an integer less than @n@ + * @mp *n@ = an odd integer + * + * Returns: @-1@, @0@ or @1@ -- the Jacobi symbol %$J(a, n)$%. + * + * 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. + */ + +int mp_jacobi(mp */*a*/, mp */*n*/); + /*----- Test harness support ----------------------------------------------*/ #include -#ifndef MPTEXT_H +#ifndef CATACOMB_MPTEXT_H # include "mptext.h" #endif