/* -*-c-*-
*
- * $Id: mp.h,v 1.5 1999/11/22 20:50:37 mdw Exp $
+ * $Id: mp.h,v 1.7 2000/06/17 11:45:09 mdw Exp $
*
* Simple multiprecision arithmetic
*
/*----- 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.
*
*
*/
-#ifndef MP_H
-#define MP_H
+#ifndef CATACOMB_MP_H
+#define CATACOMB_MP_H
#ifdef __cplusplus
extern "C" {
#include <mLib/sub.h>
-#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
typedef struct mp {
mpw *v, *vl;
size_t sz;
+ mparena *a;
unsigned f;
unsigned ref;
} mp;
#define MP_BURN 2u
#define MP_CONST 4u
#define MP_UNDEF 8u
+#define MP_DESTROYED 16u
/*----- Useful constants --------------------------------------------------*/
#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*/);
-
-/*----- Trivial macros ----------------------------------------------------*/
+extern mp *mp_new(size_t /*sz*/, unsigned /*f*/);
-/* --- @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
*
* 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@ --- *
*
#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)
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@ --- *
*
* 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*/);
#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@ --- *
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)
/*----- Bit scanning ------------------------------------------------------*/
-#ifndef MPSCAN_H
+#ifndef CATACOMB_MPSCAN_H
# include "mpscan.h"
#endif
/* --- @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@ --- *
*
/* --- @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 ------------------------------------------*/
*
* 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*/,
#include <mLib/testrig.h>
-#ifndef MPTEXT_H
+#ifndef CATACOMB_MPTEXT_H
# include "mptext.h"
#endif
projects / u / mdw / catacomb / blobdiff