/* -*-c-*-
*
- * $Id: mp-arith.c,v 1.5 1999/12/22 15:54:41 mdw Exp $
+ * $Id: mp-arith.c,v 1.6 2000/06/17 11:45:09 mdw Exp $
*
* Basic arithmetic on multiprecision integers
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mp-arith.c,v $
+ * Revision 1.6 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.5 1999/12/22 15:54:41 mdw
* Adjust Karatsuba parameters. Calculate destination size better.
*
if (!(a->f & MP_NEG))
return (MP_COPY(a));
- MP_MODIFY(d, MP_LEN(a));
+ MP_DEST(d, MP_LEN(a), a->f);
mpx_2c(d->v, d->vl, a->v, a->vl);
d->f = a->f & MP_BURN;
MP_SHRINK(d);
if (!MP_LEN(a) || a->vl[-1] < MPW_MAX / 2)
return (MP_COPY(a));
- MP_MODIFY(d, MP_LEN(a));
+ MP_DEST(d, MP_LEN(a), a->f);
mpx_2c(d->v, d->vl, a->v, a->vl);
d->f = (a->f & (MP_BURN | MP_NEG)) ^ MP_NEG;
MP_SHRINK(d);
mp *mp_lsl(mp *d, mp *a, size_t n)
{
- MP_MODIFY(d, MP_LEN(a) + (n + MPW_BITS - 1) / MPW_BITS);
+ MP_DEST(d, MP_LEN(a) + (n + MPW_BITS - 1) / MPW_BITS, a->f);
mpx_lsl(d->v, d->vl, a->v, a->vl, n);
d->f = a->f & (MP_NEG | MP_BURN);
MP_SHRINK(d);
mp *mp_lsr(mp *d, mp *a, size_t n)
{
- MP_MODIFY(d, MP_LEN(a));
+ MP_DEST(d, MP_LEN(a), a->f);
mpx_lsr(d->v, d->vl, a->v, a->vl, n);
d->f = a->f & (MP_NEG | MP_BURN);
MP_SHRINK(d);
mp *mp_add(mp *d, mp *a, mp *b)
{
- MP_MODIFY(d, MAX(MP_LEN(a), MP_LEN(b)) + 1);
+ MP_DEST(d, MAX(MP_LEN(a), MP_LEN(b)) + 1, a->f | b->f);
if (!((a->f ^ b->f) & MP_NEG))
mpx_uadd(d->v, d->vl, a->v, a->vl, b->v, b->vl);
else {
mp *mp_sub(mp *d, mp *a, mp *b)
{
unsigned sgn = 0;
- MP_MODIFY(d, MAX(MP_LEN(a), MP_LEN(b)) + 1);
+ MP_DEST(d, MAX(MP_LEN(a), MP_LEN(b)) + 1, a->f | b->f);
if ((a->f ^ b->f) & MP_NEG)
mpx_uadd(d->v, d->vl, a->v, a->vl, b->v, b->vl);
else {
b = MP_COPY(b);
if (MP_LEN(a) <= KARATSUBA_CUTOFF || MP_LEN(b) <= KARATSUBA_CUTOFF) {
- MP_MODIFY(d, MP_LEN(a) + MP_LEN(b));
+ MP_DEST(d, MP_LEN(a) + MP_LEN(b), a->f | b->f | MP_UNDEF);
mpx_umul(d->v, d->vl, a->v, a->vl, b->v, b->vl);
} else {
size_t m = 2 * MAX(MP_LEN(a), MP_LEN(b)) + 2;
mpw *s;
- MP_MODIFY(d, m);
+ MP_DEST(d, m, a->f | b->f | MP_UNDEF);
m += KARATSUBA_SLOP;
- s = MP_ALLOC(m);
+ s = mpalloc(d->a, m);
mpx_kmul(d->v, d->vl, a->v, a->vl, b->v, b->vl, s, s + m);
- MP_FREE(s);
+ mpfree(d->a, s);
}
d->f = ((a->f | b->f) & MP_BURN) | ((a->f ^ b->f) & MP_NEG);
size_t m = MP_LEN(a);
a = MP_COPY(a);
- MP_MODIFY(d, 2 * m + 2);
+ MP_DEST(d, 2 * m + 2, a->f | MP_UNDEF);
if (m > KARATSUBA_CUTOFF) {
mpw *s;
m = 2 * (m + 1) + KARATSUBA_SLOP;
- s = MP_ALLOC(m);
+ s = mpalloc(d->a, m);
mpx_ksqr(d->v, d->vl, a->v, a->vl, s, s + m);
- MP_FREE(s);
+ mpfree(d->a, s);
} else
mpx_usqr(d->v, d->vl, a->v, a->vl);
d->f = a->f & MP_BURN;
mp *q = qq ? *qq : MP_NEW;
mpw *sv, *svl;
- /* --- Set up some temporary workspace --- */
-
- {
- size_t rq = MP_LEN(b) + 1;
- sv = MP_ALLOC(rq);
- svl = sv + rq;
- }
-
/* --- Set the remainder up right --- *
*
* Just in case the divisor is larger, be able to cope with this. It's not
* important in @mpx_udiv@, but it is here because of the sign correction.
*/
- {
- size_t rq = MP_LEN(a) + 2;
- if (MP_LEN(b) > rq)
- rq = MP_LEN(b);
-
- b = MP_COPY(b);
- if (r == a) {
- MP_SPLIT(a);
- a = r = MP_COPY(a);
- MP_ENSURE(r, MP_LEN(r) + 2);
- } else {
- a = MP_COPY(a);
- MP_MODIFY(r, MP_LEN(a) + 2);
- memcpy(r->v, a->v, MPWS(MP_LEN(a)));
- memset(r->v + MP_LEN(a), 0, MPWS(2));
- }
- }
+ b = MP_COPY(b);
+ a = MP_COPY(a);
+ if (r)
+ MP_DROP(r);
+ r = a;
+ MP_DEST(r, MP_LEN(a) + 2, a->f | b->f);
/* --- Fix up the quotient too --- */
- MP_MODIFY(q, MP_LEN(a));
+ r = MP_COPY(r);
+ MP_DEST(q, MP_LEN(r), r->f | MP_UNDEF);
+ MP_DROP(r);
+
+ /* --- Set up some temporary workspace --- */
+
+ {
+ size_t rq = MP_LEN(b) + 1;
+ sv = mpalloc(r->a, rq);
+ svl = sv + rq;
+ }
/* --- Perform the calculation --- */
* remainder from @b@.
*/
- q->f = ((a->f | b->f) & MP_BURN) | ((a->f ^ b->f) & MP_NEG);
+ q->f = ((r->f | b->f) & MP_BURN) | ((r->f ^ b->f) & MP_NEG);
if (q->f & MP_NEG) {
mpw *v;
for (v = r->v; v < r->vl; v++) {
}
}
- r->f = ((a->f | b->f) & MP_BURN) | (b->f & MP_NEG);
+ r->f = ((r->f | b->f) & MP_BURN) | (b->f & MP_NEG);
/* --- Store the return values --- */
+ mpfree(r->a, sv);
+ MP_DROP(b);
+
if (!qq)
MP_DROP(q);
else {
MP_SHRINK(r);
*rr = r;
}
-
- MP_DROP(a);
- MP_DROP(b);
- MP_FREE(sv);
}
/*----- Test rig ----------------------------------------------------------*/
/* -*-c-*-
*
- * $Id: mp-const.c,v 1.1 1999/11/17 18:02:16 mdw Exp $
+ * $Id: mp-const.c,v 1.2 2000/06/17 11:45:09 mdw Exp $
*
* Useful multiprecision constants
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mp-const.c,v $
+ * Revision 1.2 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.1 1999/11/17 18:02:16 mdw
* New multiprecision integer arithmetic suite.
*
/*----- Global variables --------------------------------------------------*/
-static mpw mpw_const[] = { 1, 2, 3, 4, 5, 10 };
+static mpw mpw_const[] = { 1, 2, 3, 4, 5, 10, 256 };
mp mp_const[] = {
- { &mpw_const[0], &mpw_const[0], 0, MP_CONST, 0 },
- { &mpw_const[0], &mpw_const[0] + 1, 1, MP_CONST, 0 },
- { &mpw_const[1], &mpw_const[1] + 1, 1, MP_CONST, 0 },
- { &mpw_const[2], &mpw_const[2] + 1, 1, MP_CONST, 0 },
- { &mpw_const[3], &mpw_const[3] + 1, 1, MP_CONST, 0 },
- { &mpw_const[4], &mpw_const[4] + 1, 1, MP_CONST, 0 },
- { &mpw_const[5], &mpw_const[5] + 1, 1, MP_CONST, 0 },
- { &mpw_const[0], &mpw_const[0] + 1, 1, MP_CONST | MP_NEG, 0 },
+ { &mpw_const[0], &mpw_const[0], 0, 0, MP_CONST, 0 },
+ { &mpw_const[0], &mpw_const[0] + 1, 1, 0, MP_CONST, 0 },
+ { &mpw_const[1], &mpw_const[1] + 1, 1, 0, MP_CONST, 0 },
+ { &mpw_const[2], &mpw_const[2] + 1, 1, 0, MP_CONST, 0 },
+ { &mpw_const[3], &mpw_const[3] + 1, 1, 0, MP_CONST, 0 },
+ { &mpw_const[4], &mpw_const[4] + 1, 1, 0, MP_CONST, 0 },
+ { &mpw_const[5], &mpw_const[5] + 1, 1, 0, MP_CONST, 0 },
+ { &mpw_const[6], &mpw_const[6] + 1, 1, 0, MP_CONST, 0 },
+ { &mpw_const[0], &mpw_const[0] + 1, 1, 0, MP_CONST | MP_NEG, 0 },
+ { 0, mpw_const, 1, 0, MP_CONST | MP_BURN, 0 },
};
/*----- That's all, folks -------------------------------------------------*/
/* -*-c-*-
*
- * $Id: mp-io.c,v 1.3 1999/11/21 22:13:02 mdw Exp $
+ * $Id: mp-io.c,v 1.4 2000/06/17 11:45:09 mdw Exp $
*
* Loading and storing of multiprecision integers
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mp-io.c,v $
+ * Revision 1.4 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.3 1999/11/21 22:13:02 mdw
* Add mp version of MPX_BITS.
*
mp *mp_loadl(mp *d, const void *pv, size_t sz)
{
- MP_MODIFY(d, MPW_RQ(sz));
+ MP_DEST(d, MPW_RQ(sz), MP_UNDEF);
mpx_loadl(d->v, d->vl, pv, sz);
d->f &= ~(MP_UNDEF | MP_NEG);
mp_shrink(d);
mp *mp_loadb(mp *d, const void *pv, size_t sz)
{
- MP_MODIFY(d, MPW_RQ(sz));
+ MP_DEST(d, MPW_RQ(sz), MP_UNDEF);
mpx_loadb(d->v, d->vl, pv, sz);
d->f &= ~(MP_UNDEF | MP_NEG);
mp_shrink(d);
/* -*-c-*-
*
- * $Id: mp-mem.c,v 1.2 1999/12/10 23:19:02 mdw Exp $
+ * $Id: mp-mem.c,v 1.3 2000/06/17 11:45:09 mdw Exp $
*
* Memory management for multiprecision numbers
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mp-mem.c,v $
+ * Revision 1.3 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.2 1999/12/10 23:19:02 mdw
* Improve error-checking.
*
/*----- Header files ------------------------------------------------------*/
+#include <mLib/sub.h>
+
+
#include "mp.h"
/*----- Main code ---------------------------------------------------------*/
+/* --- @mp_new@ --- *
+ *
+ * Arguments: @size_t sz@ = size of vector required
+ * @unsigned f@ = flags to set
+ *
+ * Returns: Pointer to a new MP structure.
+ *
+ * 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.
+ */
+
+mp *mp_new(size_t sz, unsigned f)
+{
+ mp *m = CREATE(mp);
+ m->a = (f & MP_BURN) ? MPARENA_SECURE : MPARENA_GLOBAL;
+ m->v = mpalloc(m->a, sz);
+ m->vl = m->v + sz;
+ m->sz = sz;
+ m->f = f & ~(MP_CONST | MP_DESTROYED);
+ m->ref = 1;
+ return (m);
+}
+
/* --- @mp_create@ --- *
*
* Arguments: @size_t sz@ = size of vector required
mp *mp_create(size_t sz)
{
mp *m = CREATE(mp);
- m->v = MP_ALLOC(sz);
+ m->v = mpalloc(MPARENA_GLOBAL, sz);
m->vl = m->v + sz;
m->sz = sz;
+ m->a = MPARENA_GLOBAL;
m->f = MP_UNDEF;
m->ref = 1;
return (m);
}
+/* --- @mp_createsecure@ --- *
+ *
+ * Arguments: @size_t sz@ = size of vector required
+ *
+ * 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. The integer's
+ * data space is allocated from the secure arena. Its burn flag
+ * is set.
+ */
+
+mp *mp_createsecure(size_t sz)
+{
+ mp *m = CREATE(mp);
+ m->v = mpalloc(MPARENA_SECURE, sz);
+ m->vl = m->v + sz;
+ m->sz = sz;
+ m->a = MPARENA_SECURE;
+ m->f = MP_UNDEF | MP_BURN;
+ m->ref = 1;
+ return (m);
+}
+
/* --- @mp_build@ --- *
*
* Arguments: @mp *m@ = pointer to an MP block to fill in
assert(((void)"Attempted to destroy a constant", !(m->f & MP_CONST)));
if (m->f & MP_BURN)
memset(m->v, 0, MPWS(m->sz));
- MP_FREE(m->v);
+ mpfree(m->a, m->v);
m->f |= MP_DESTROYED;
DESTROY(m);
}
* Use: Splits off a modifiable version of the integer referred to.
*/
-mp *mp_split(mp *m) { MP_SPLIT(m); return (m); }
+mp *mp_split(mp *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; */
+/* } */
+ MP_SPLIT(m);
+ return (m);
+}
/* --- @mp_resize@ --- *
*
*
* Returns: ---
*
- * 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.
+ * Use: Changes an integer's size. The length and value are not
+ * changed. It is an error to
*/
-void mp_resize(mp *m, size_t sz) { MP_RESIZE(m, sz); }
+void mp_resize(mp *m, size_t sz)
+{
+/* 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; */
+}
/* --- @mp_ensure@ --- *
*
* Arguments: @mp *m@ = pointer to a multiprecision integer
- * @size_t sz@ = required size
+ * @size_t sz@ = required length
*
* Returns: ---
*
- * Use: Ensures that the integer has enough space for @sz@ digits.
- * The value is not changed.
+ * Use: Changes an integer's length. If there is not enough space
+ * allocated for the new length then the size is increased. It
*/
-void mp_ensure(mp *m, size_t sz) { MP_ENSURE(m, sz); }
+void mp_ensure(mp *m, size_t sz)
+{
+/* size_t len = MP_LEN(m); */
+/* if (sz >= len) { */
+/* if (sz > m->sz) */
+/* mp_resize(m, sz); */
+/* if (!(m->f & MP_UNDEF) && sz > len) */
+/* memset(m->vl, 0, MPWS(sz - len)); */
+/* m->vl = m->v + sz; */
+/* } */
+}
-/* --- @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:
*
- * Returns: Pointer to the integer (possibly different).
+ * * @d@ will have exactly one reference.
*
- * 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 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.
*/
-mp *mp_modify(mp *m, size_t sz) { MP_MODIFY(m, sz); return (m); }
+mp *mp_dest(mp *m, size_t sz, unsigned f)
+{
+ /* --- If no destination, make one --- */
+
+ if (m == MP_NEWSEC)
+ m = mp_new(sz, f | MP_UNDEF | MP_BURN);
+ else if (m == MP_NEW)
+ m = mp_new(sz, f | MP_UNDEF);
+ else {
+ size_t len = MP_LEN(m);
+ unsigned undef = (m->f | f) & MP_UNDEF;
+
+ /* --- If the value must be preserved, the block can't shrink --- */
+
+ if (!undef && sz < len)
+ sz = len;
+
+ /* --- Otherwise check whether the destination is suitable --- */
+
+ if (m->ref > 1 || (m->f & MP_CONST) ||
+ m->sz > len || !((f & ~m->f) & MP_BURN)) {
+
+ /* --- No -- allocate a new buffer --- *
+ *
+ * The buffer must be secure if (a) the caller requested a secure
+ * buffer, or (b) the old buffer is secure and I'm not allowed to
+ * discard the old contents.
+ */
+
+ mparena *a;
+ mpw *v;
+
+ if ((f & MP_BURN) || (!undef && (m->f & MP_BURN)))
+ a = MPARENA_SECURE;
+ else
+ a = MPARENA_GLOBAL;
+ v = mpalloc(a, sz);
+
+ /* --- Copy the data over --- */
+
+ if (!undef) {
+ memcpy(v, m->v, MPWS(len));
+ if (sz - len > 0)
+ memset(v + len, 0, MPWS(sz - len));
+ }
+
+ /* --- If @m@ has other references, make a new node --- *
+ *
+ * Otherwise dispose of the old buffer.
+ */
+
+ if (!(m->f & MP_CONST) && m->ref == 1) {
+ if (m->f & MP_BURN)
+ memset(m->v, 0, MPWS(m->sz));
+ mpfree(m->a, m->v);
+ } else {
+ mp *mm = CREATE(mp);
+ mm->ref = 1;
+ mm->f = m->f;
+ m->ref--;
+ m = mm;
+ }
+
+ /* --- Fix up the node --- */
+
+ m->v = v;
+ m->vl = v + sz;
+ m->sz = sz;
+ m->f = ((m->f & ~(MP_CONST | MP_BURN)) |
+ (f & (MP_BURN | MP_UNDEF)));
+ m->a = a;
+ }
+
+ /* --- If the number is growing in its buffer, fix it up --- */
+
+ else if (sz > len) {
+ if (!undef)
+ memset(m->vl, 0, MPWS(sz - len));
+ m->vl = m->v + sz;
+ }
+ }
+
+ /* --- Done --- */
+
+ return (m);
+}
/*----- That's all, folks -------------------------------------------------*/
/* -*-c-*-
*
- * $Id: mp-misc.c,v 1.1 1999/11/17 18:02:16 mdw Exp $
+ * $Id: mp-misc.c,v 1.2 2000/06/17 11:45:09 mdw Exp $
*
* Miscellaneous multiprecision support functions
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mp-misc.c,v $
+ * Revision 1.2 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.1 1999/11/17 18:02:16 mdw
* New multiprecision integer arithmetic suite.
*
#include "mp.h"
-/*----- Paranoia management -----------------------------------------------*/
-
-/* --- @mp_burn@ --- *
- *
- * Arguments: @mp *m@ = pointer to a multiprecision integer
- *
- * Returns: ---
- *
- * 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.
- */
-
-void mp_burn(mp *m)
-{
- m->f |= MP_BURN;
-}
-
/*----- Basic manipulation ------------------------------------------------*/
/* --- @mp_shrink@ --- *
/* -*-c-*-
*
- * $Id: mp.h,v 1.6 1999/12/10 23:19:46 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.
*
# include "mpw.h"
#endif
+#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_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 CATACOMB_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
*
* 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); \
+ 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->ref > 1 || (_m->f & MP_CONST)) { \
- if (_m) \
- MP_DROP(_m); \
- _m = mp_create(_rq); \
- } else \
- MP_ENSURE(_m, _rq); \
+ size_t _ssz = (ssz); \
+ unsigned _f = (f); \
+ _m = mp_dest(_m, _ssz, _f); \
(m) = _m; \
} while (0)
/* -*-c-*-
*
- * $Id: mpbarrett.c,v 1.3 1999/12/12 15:08:52 mdw Exp $
+ * $Id: mpbarrett.c,v 1.4 2000/06/17 11:45:09 mdw Exp $
*
* Barrett modular reduction
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpbarrett.c,v $
+ * Revision 1.4 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.3 1999/12/12 15:08:52 mdw
* Don't bother shifting %$q$% in @mpbarrett_reduce@, just skip the least
* significant digits.
mp_shrink(m);
mb->k = MP_LEN(m);
mb->m = MP_COPY(m);
- b = mp_create(2 * mb->k + 1);
+ b = mp_new(2 * mb->k + 1, 0);
MPX_ZERO(b->v, b->vl - 1);
b->vl[-1] = 1;
mp_div(&b, 0, b, m);
if (MP_LEN(m) < k) {
m = MP_COPY(m);
- MP_DROP(d);
+ if (d)
+ MP_DROP(d);
return (m);
}
q = mp_mul(MP_NEW, &qq, mb->mu);
if (MP_LEN(q) <= k) {
m = MP_COPY(m);
- MP_DROP(d);
+ if (d)
+ MP_DROP(d);
return (m);
}
}
mvl = m->vl;
else
mvl = m->v + k + 1;
- r = mp_create(k + 1);
+ r = mp_new(k + 1, (q->f | mb->m->f) & MP_BURN);
mpx_umul(r->v, r->vl, q->v + k + 1, q->vl, mb->m->v, mb->m->vl);
- r->f = (q->f | mb->m->f) & MP_BURN;
- MP_MODIFY(d, k + 1);
+ MP_DEST(d, k + 1, r->f);
mpx_usub(d->v, d->vl, m->v, mvl, r->v, r->vl);
d->f = (m->f | r->f) & MP_BURN;
MP_DROP(r);
a = MP_COPY(a);
mp_scan(&sc, e);
+ if (e->f & MP_BURN)
+ spare = MP_NEWSEC;
if (MP_STEP(&sc)) {
size_t sq = 0;
for (;;) {
/* -*-c-*-
*
- * $Id: mpint.h,v 1.2 1999/12/10 23:22:53 mdw Exp $
+ * $Id: mpint.h,v 1.3 2000/06/17 11:45:09 mdw Exp $
*
* Conversion between MPs and standard C integers
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpint.h,v $
+ * Revision 1.3 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.2 1999/12/10 23:22:53 mdw
* Support for uint32.
*
mp *_d = (d); \
size_t _sz = 4; \
\
- MP_MODIFY(_d, _sz); \
+ MP_DEST(_d, _sz, 0); \
_d->f &= ~(MP_NEG | MP_UNDEF); \
\
/* --- Set the sign on the MP --- * \
/* -*-c-*-
*
- * $Id: mpmont-mexp.c,v 1.3 1999/12/10 23:18:39 mdw Exp $
+ * $Id: mpmont-mexp.c,v 1.4 2000/06/17 11:45:09 mdw Exp $
*
- * Multiplle simultaneous exponentiations
+ * Multiple simultaneous exponentiations
*
* (c) 1999 Straylight/Edgeware
*/
/*----- Revision history --------------------------------------------------*
*
* $Log: mpmont-mexp.c,v $
+ * Revision 1.4 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.3 1999/12/10 23:18:39 mdw
* Change interface for suggested destinations.
*
*
* I must scan the exponents from left to right, which is a shame. It
* means that I can't use the standard @mpscan@ stuff, in particular.
+ *
+ * If any of the exponents are considered secret then make the accumulator
+ * automatically set the secret bit.
*/
{
s[i].len = MP_LEN(f[i].exp);
if (s[i].len > o)
o = s[i].len;
+ if (f[i].exp->f & MP_BURN)
+ spare = MP_NEWSEC;
}
b = 0;
}
/* -*-c-*-
*
- * $Id: mpmont.c,v 1.8 1999/12/22 15:55:00 mdw Exp $
+ * $Id: mpmont.c,v 1.9 2000/06/17 11:45:09 mdw Exp $
*
* Montgomery reduction
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpmont.c,v $
+ * Revision 1.9 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.8 1999/12/22 15:55:00 mdw
* Adjust Karatsuba parameters.
*
void mpmont_create(mpmont *mm, mp *m)
{
size_t n = MP_LEN(m);
- mp *r2 = mp_create(2 * n + 1);
+ mp *r2 = mp_new(2 * n + 1, 0);
mp r;
/* --- Validate the arguments --- */
/* --- Initial conditioning of the arguments --- */
- if (d == a)
- MP_MODIFY(d, 2 * n + 1);
- else {
- MP_MODIFY(d, 2 * n + 1);
- MPX_COPY(d->v, d->vl, a->v, a->vl);
- }
-
+ a = MP_COPY(a);
+ if (d)
+ MP_DROP(d);
+ d = a;
+ MP_DEST(d, 2 * n + 1, a->f);
+
dv = d->v; dvl = d->vl;
mv = mm->m->v; mvl = mm->m->vl;
/* --- Wrap everything up --- */
- d->f = a->f & MP_BURN;
memmove(d->v, d->v + n, MPWS(MP_LEN(d) - n));
d->vl -= n;
if (MP_CMP(d, >=, mm->m))
a = MP_COPY(a);
b = MP_COPY(b);
- MP_MODIFY(d, 2 * n + 1);
+ MP_DEST(d, 2 * n + 1, a->f | b->f | MP_UNDEF);
dv = d->v; dvl = d->vl;
MPX_ZERO(dv, dvl);
av = a->v; avl = a->vl;
mpscan sc;
mp *ar = mpmont_mul(mm, MP_NEW, a, mm->r2);
mp *x = MP_COPY(mm->r);
- mp *spare = MP_NEW;
+ mp *spare = (e->f & MP_BURN) ? MP_NEWSEC : MP_NEW;
mp_scan(&sc, e);
/* -*-c-*-
*
- * $Id: mprand.c,v 1.2 1999/12/22 15:55:33 mdw Exp $
+ * $Id: mprand.c,v 1.3 2000/06/17 11:45:09 mdw Exp $
*
* Generate a random multiprecision integer
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mprand.c,v $
+ * Revision 1.3 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.2 1999/12/22 15:55:33 mdw
* Modify `mprand' slightly. Add `mprand_range'.
*
mp *mprand(mp *d, unsigned b, grand *r, mpw or)
{
size_t sz = (b + 7) >> 3;
- octet *v = xmalloc(sz);
+ arena *a = (d && (d->f & MP_BURN)) ? arena_secure : arena_global;
+ octet *v = x_alloc(a, sz);
unsigned m;
/* --- Fill buffer with random data --- */
d = mp_loadb(d, v, sz);
d->v[0] |= or;
- free(v);
+ memset(v, 0, sz);
+ x_free(a, v);
return (d);
}
{
size_t b = mp_bits(l);
size_t sz = (b + 7) >> 3;
- octet *v = xmalloc(sz);
+ arena *a = (d && (d->f & MP_BURN)) ? arena_secure : arena_global;
+ octet *v = x_alloc(a, sz);
unsigned m;
/* --- The algorithm --- *
/* --- Done --- */
- free(v);
+ memset(v, 0, sz);
+ x_free(a, v);
return (d);
}
projects / u / mdw / catacomb / commitdiff