/* -*-c-*-
*
- * $Id: mp.h,v 1.4 1999/11/21 22:13:02 mdw Exp $
+ * $Id: mp.h,v 1.6 1999/12/10 23:19:46 mdw Exp $
*
* Simple multiprecision arithmetic
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mp.h,v $
+ * 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.
*
*
*/
-#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_MPX_H
# include "mpx.h"
#endif
#define MP_BURN 2u
#define MP_CONST 4u
#define MP_UNDEF 8u
+#define MP_DESTROYED 16u
/*----- Useful constants --------------------------------------------------*/
/*----- Memory allocation hooks -------------------------------------------*/
-#ifndef MPARENA_H
+#ifndef CATACOMB_MPARENA_H
# include "mparena.h"
#endif
size_t _sz = (ssz); \
size_t _len = MP_LEN(_m); \
mpw *_v = MP_ALLOC(_sz); \
- memcpy(_v, _m->v, MPWS(_len)); \
+ 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); \
size_t _len = MP_LEN(_mm); \
if (_ssz > _mm->sz) \
MP_RESIZE(_mm, _ssz); \
- if (!(_mm->f & MP_UNDEF) && _ssz > _len) { \
+ if (!(_mm->f & MP_UNDEF) && _ssz > _len) \
memset(_mm->vl, 0, MPWS(_ssz - _len)); \
- _mm->vl = _mm->v + _ssz; \
- } \
+ _mm->vl = _mm->v + _ssz; \
} while (0)
/* --- @mp_modify@ --- *
#define MP_MODIFY(m, sz) do { \
size_t _rq = (sz); \
mp *_m = (m); \
- if (_m == MP_NEW) \
+ if (_m == MP_NEW || m->ref > 1 || (_m->f & MP_CONST)) { \
+ if (_m) \
+ MP_DROP(_m); \
_m = mp_create(_rq); \
- else { \
- MP_SPLIT(_m); \
+ } else \
MP_ENSURE(_m, _rq); \
- } \
- _m->vl = _m->v + _rq; \
(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*/,
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 <mLib/testrig.h>
-#ifndef MPTEXT_H
+#ifndef CATACOMB_MPTEXT_H
# include "mptext.h"
#endif