/* -*-c-*-
*
- * $Id: mp.h,v 1.1 1999/09/03 08:41:12 mdw Exp $
+ * $Id: mp.h,v 1.8 2000/06/22 19:02:01 mdw Exp $
*
- * Multiprecision arithmetic
+ * Simple multiprecision arithmetic
*
* (c) 1999 Straylight/Edgeware
*/
/*----- Revision history --------------------------------------------------*
*
* $Log: mp.h,v $
- * Revision 1.1 1999/09/03 08:41:12 mdw
- * Initial import.
+ * Revision 1.8 2000/06/22 19:02:01 mdw
+ * Add new functions.
+ *
+ * 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" {
/*----- Header files ------------------------------------------------------*/
-#include <stdlib.h>
+#include <assert.h>
#include <string.h>
-#ifndef MPTYPES_H
-# include "mptypes.h"
+#include <mLib/sub.h>
+
+#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
+
+/*----- Useful constants --------------------------------------------------*/
+
+extern mp mp_const[];
+
+#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_NEW ((mp *)0)
+#define MP_NEWSEC (&mp_const[9])
+
+/*----- Trivial macros ----------------------------------------------------*/
-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;
+/* --- @MP_LEN@ --- *
+ *
+ * Arguments: @mp *m@ = pointer to a multiprecision integer
+ *
+ * Returns: Length of the integer, in words.
+ */
-/*----- External variables ------------------------------------------------*/
+#define MP_LEN(m) ((m)->vl - ((m)->v))
-extern mp mp_std;
+/*----- Memory management and reference counting --------------------------*/
-#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)
+/* --- @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.
+ */
-/*----- Memory allocation and low-level fiddling --------------------------*/
+extern mp *mp_new(size_t /*sz*/, unsigned /*f*/);
/* --- @mp_create@ --- *
*
- * Arguments @mp *x@ = pointer to MP head
+ * 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.
+ */
+
+extern mp *mp_create(size_t /*sz*/);
+
+/* --- @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.
+ */
+
+extern mp *mp_createsecure(size_t /*sz*/);
+
+/* --- @mp_build@ --- *
+ *
+ * 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: Initializes an MP ready for use. The initial value is zero.
+ * 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.
*/
-#define MP_INIT { 0, 0, 0, 0 }
+extern void mp_build(mp */*m*/, mpw */*v*/, mpw */*vl*/);
-extern void mp_create(mp */*x*/);
+/* --- @mp_destroy@ --- *
+ *
+ * Arguments: @mp *m@ = pointer to a multiprecision integer
+ *
+ * Returns: ---
+ *
+ * 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.
+ */
-/* --- @MP_BURN@ --- *
+extern void mp_destroy(mp */*m*/);
+
+/* --- @mp_copy@ --- *
*
- * Arguments: @x@ = pointer to MP head
+ * Arguments: @mp *m@ = pointer to a multiprecision integer
*
- * Use: Burns the contents of the MP, if it contains sensitive data.
+ * 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.
*/
-#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_copy(mp */*m*/);
+
+#define MP_COPY(m) ((m)->ref++, (m))
-/* --- @mp_free@ --- *
+/* --- @mp_drop@ --- *
*
- * Arguments: @mp *x@ = pointer to MP head
+ * Arguments: @mp *m@ = pointer to a multiprecision integer
*
* Returns: ---
*
- * Use: Releases the memory used by an MP.
+ * Use: Drops a reference to an integer which isn't wanted any more.
+ * If there are no more references, the integer is destroyed.
*/
-#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 void mp_drop(mp */*m*/);
-/* --- @MP_ENSURE@ --- *
+#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
- * @len@ = length required (in words)
+ * Returns: A reference to the same integer, possibly with a different
+ * address.
*
- * Use: Ensures that the MP has enough memory to store a @len@-word
- * value.
+ * Use: Splits off a modifiable version of the integer referred to.
*/
-#define MP_ENSURE(x, len) do { \
- mp *_x = (x); \
- size_t _len = (len); \
- if (_x->sz < _len) \
- mp_resize(_x, _len); \
+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_resize@ --- *
*
- * Arguments: @mp *x@ = pointer to MP head
- * @size_t sz@ = size required (in words)
+ * Arguments: @mp *m@ = pointer to a multiprecision integer
+ * @size_t sz@ = new size
*
* Returns: ---
*
- * Use: Resizes the MP so that its word vector has space for
- * exactly @sz@ words.
+ * 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_resize(mp */*x*/, size_t /*sz*/);
+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_norm@ --- *
+/* --- @mp_ensure@ --- *
*
- * Arguments: @mp *x@ = pointer to MP head
+ * Arguments: @mp *m@ = pointer to a multiprecision integer
+ * @size_t sz@ = required size
*
* 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: Ensures that the integer has enough space for @sz@ digits.
+ * The value is not changed.
*/
-#define MP_NORM(x) do { \
- mp *_y = (x); \
- MPX_LEN(_y->len, _y->v, _y->len); \
+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)
-extern void mp_norm(mp */*x*/);
-
-/* --- @mp_dump@ --- *
+/* --- @mp_dest@ --- *
*
- * Arguments: @mp *x@ = pointer to MP head
- * @FILE *fp@ = pointer to stream to write on
+ * Arguments: @mp *m@ = a suggested destination integer
+ * @size_t sz@ = size required for result, in digits
+ * @unsigned f@ = various flags
*
- * Returns: ---
+ * 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.
+ *
+ * * 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.
*
- * Use: Dumps an MP to a stream.
+ * * 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 void mp_dump(mp */*x*/, FILE */*fp*/);
+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)
+
+/*----- Size manipulation -------------------------------------------------*/
-/* --- @MP_PARANOID@ --- *
+/* --- @mp_shrink@ --- *
+ *
+ * Arguments: @mp *m@ = pointer to a multiprecision integer
*
- * Arguments: @x@ = pointer to MP head
+ * Returns: ---
*
- * Use: Marks the MP as containing sensitive data which should be
- * burnt when no longer required.
+ * 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.
*/
-#define MP_PARANOID(x) ((x)->f |= MPF_BURN)
+extern void mp_shrink(mp */*m*/);
-/* --- @mp_copy@ --- *
+#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 *d@ = pointer to MP head for destination
- * @const mp *s@ = pointer to MP head for source
+ * Arguments: @mp *m@ = pointer to a multiprecision integer
*
* Returns: ---
*
- * Use: Copies an MP.
+ * 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_copy(mp */*d*/, const mp */*s*/);
+extern void mp_minimize(mp */*m*/);
-/* --- @mp_bits@ --- *
+/*----- Bit scanning ------------------------------------------------------*/
+
+#ifndef CATACOMB_MPSCAN_H
+# include "mpscan.h"
+#endif
+
+/* --- @mp_scan@ --- *
*
- * Arguments: @mp *x@ = pointer to MP head
+ * Arguments: @mpscan *sc@ = pointer to bitscanner block
+ * @const mp *m@ = pointer to a multiprecision integer
*
- * 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: Initializes a bitscanner on a multiprecision integer.
*/
-unsigned long mp_bits(mp */*x*/);
+extern void mp_scan(mpscan */*sc*/, const mp */*m*/);
+
+#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
+ * Arguments: @const mp *m@ = a multiprecision integer
*
- * Returns: Length of number in octets.
+ * Returns: The number of octets required to represent @m@.
*
- * Use: Calculates the number of octets required to represent a
- * number. The number must be normalized.
+ * Use: Calculates the external storage required for a multiprecision
+ * integer.
*/
-extern size_t mp_octets(mp */*x*/);
-
-/*----- Loading and storing as binary data --------------------------------*/
+extern size_t mp_octets(const mp */*m*/);
-/* --- @mp_storel@ --- *
+/* --- @mp_bits@ --- *
*
- * Arguments: @mp *x@ = pointer to MP head
- * @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 bits required to represent @m@.
*
- * 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: Calculates the external storage required for a multiprecision
+ * integer.
*/
-extern void mp_storel(mp */*x*/, octet */*p*/, size_t /*sz*/);
+extern unsigned long mp_bits(const mp */*m*/);
/* --- @mp_loadl@ --- *
*
- * Arguments: @mp *x@ = pointer to MP head
- * @const octet *p@ = pointer to octet array
- * @size_t sz@ = size of octet array
+ * Arguments: @mp *d@ = destination
+ * @const void *pv@ = pointer to source data
+ * @size_t sz@ = size of the source data
*
- * Returns: ---
+ * Returns: Resulting multiprecision number.
*
- * Use: Loads an MP in an octet array, least significant octet
- * first.
+ * 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}$%.
*/
-extern void mp_loadl(mp */*x*/, const octet */*p*/, size_t /*sz*/);
+extern mp *mp_loadl(mp */*d*/, const void */*pv*/, size_t /*sz*/);
-/* --- @mp_storeb@ --- *
+/* --- @mp_storel@ --- *
*
- * Arguments: @mp *x@ = pointer to MP head
- * @octet *p@ = pointer to octet array
- * @size_t sz@ = size of octet array
+ * Arguments: @const mp *m@ = source
+ * @void *pv@ = pointer to output array
+ * @size_t sz@ = size of the output array
*
* 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: 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_storeb(mp */*x*/, octet */*p*/, size_t /*sz*/);
+extern void mp_storel(const mp */*m*/, void */*pv*/, size_t /*sz*/);
/* --- @mp_loadb@ --- *
*
- * Arguments: @mp *x@ = pointer to MP head
- * @const octet *p@ = pointer to octet array
- * @size_t sz@ = size of octet array
+ * Arguments: @mp *d@ = destination
+ * @const void *pv@ = pointer to source data
+ * @size_t sz@ = size of the source data
*
- * Returns: ---
+ * Returns: Resulting multiprecision number.
*
- * Use: Loads an MP in an octet array, most significant octet
- * first.
+ * 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 void mp_loadb(mp */*x*/, const octet */*p*/, size_t /*sz*/);
+extern mp *mp_loadb(mp */*d*/, const void */*pv*/, size_t /*sz*/);
-/*----- Iterating through bits --------------------------------------------*/
-
-/* --- @mp_mkbitscan@ --- *
+/* --- @mp_storeb@ --- *
*
- * 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
+ * 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_mkbitscan(mp_bitscan */*sc*/, const mp */*x*/);
+extern void mp_storeb(const mp */*m*/, void */*pv*/, size_t /*sz*/);
-/* --- @mp_bstep@ --- *
+/*----- Simple arithmetic -------------------------------------------------*/
+
+/* --- @mp_2c@ --- *
*
- * Arguments: @mp_bitscan *sc@ = pointer to bitscanner object
+ * Arguments: @mp *d@ = destination
+ * @mp *a@ = source
*
- * Returns: Nonzero if there is another bit to read.
+ * Returns: Result, @a@ converted to two's complement notation.
+ */
+
+extern mp *mp_2c(mp */*d*/, mp */*a*/);
+
+/* --- @mp_sm@ --- *
*
- * Use: Steps on to the next bit, and tells the caller whether one
- * exists.
+ * Arguments: @mp *d@ = destination
+ * @mp *a@ = source
+ *
+ * Returns: Result, @a@ converted to the native signed-magnitude
+ * notation.
*/
-extern int mp_bstep(mp_bitscan */*sc*/);
+extern mp *mp_sm(mp */*d*/, mp */*a*/);
-/* --- @mp_bit@ --- *
+/* --- @mp_lsl@ --- *
*
- * Arguments: @const mp_bitscan *sc@ = pointer to bitscanner
+ * Arguments: @mp *d@ = destination
+ * @mp *a@ = source
+ * @size_t n@ = number of bits to move
+ *
+ * Returns: Result, @a@ shifted left by @n@.
+ */
+
+extern mp *mp_lsl(mp */*d*/, mp */*a*/, size_t /*n*/);
+
+/* --- @mp_lsr@ --- *
*
- * Returns: Current bit value.
+ * Arguments: @mp *d@ = destination
+ * @mp *a@ = source
+ * @size_t n@ = number of bits to move
*
- * Use: Returns the value of the current bit.
+ * Returns: Result, @a@ shifted left by @n@.
*/
-#define MP_BIT(sc) ((sc)->w & 1)
+extern mp *mp_lsr(mp */*d*/, mp */*a*/, size_t /*n*/);
-extern int mp_bit(const mp_bitscan */*sc*/);
+/* --- @mp_cmp@ --- *
+ *
+ * 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@.
+ */
-/*----- Shifting ----------------------------------------------------------*/
+extern int mp_cmp(const mp */*a*/, const mp */*b*/);
-/* --- @mp_lsl@ --- *
+#define MP_CMP(a, op, b) (mp_cmp((a), (b)) op 0)
+
+/* --- @mp_add@ --- *
*
- * 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, *b@ = sources
*
- * Returns: ---
+ * Returns: Result, @a@ added to @b@.
+ */
+
+extern mp *mp_add(mp */*d*/, mp */*a*/, mp */*b*/);
+
+/* --- @mp_sub@ --- *
+ *
+ * Arguments: @mp *d@ = destination
+ * @mp *a, *b@ = sources
*
- * Use: Shifts a number left by a given number of bit positions.
+ * Returns: Result, @b@ subtracted from @a@.
*/
-extern void mp_lsl(mp */*d*/, const mp */*x*/, size_t /*n*/);
+extern mp *mp_sub(mp */*d*/, mp */*a*/, mp */*b*/);
-/* --- @mp_lsr@ --- *
+/* --- @mp_mul@ --- *
*
- * 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, *b@ = sources
*
- * Returns: ---
+ * Returns: Result, @a@ multiplied by @b@.
+ */
+
+extern mp *mp_mul(mp */*d*/, mp */*a*/, mp */*b*/);
+
+/* --- @mp_sqr@ --- *
+ *
+ * Arguments: @mp *d@ = destination
+ * @mp *a@ = source
*
- * Use: Shifts a number right by a given number of bit positions.
+ * Returns: Result, @a@ squared.
*/
-extern void mp_lsr(mp */*d*/, const mp */*x*/, size_t /*n*/);
+extern mp *mp_sqr(mp */*d*/, mp */*a*/);
-/*----- Unsigned arithmetic -----------------------------------------------*/
+/* --- @mp_div@ --- *
+ *
+ * Arguments: @mp **qq, **rr@ = destination, quotient and remainder
+ * @mp *a, *b@ = sources
+ *
+ * Use: Calculates the quotient and remainder when @a@ is divided by
+ * @b@.
+ */
-/* --- @mp_uadd@ --- *
+extern void mp_div(mp **/*qq*/, mp **/*rr*/, mp */*a*/, mp */*b*/);
+
+/* --- @mp_odd@ --- *
*
- * Arguments: @const mp *d@ = pointers to MP head of destination
- * @const mp *x, *y@ = pointers to MP heads of operands
+ * Arguments: @mp *d@ = pointer to destination integer
+ * @mp *m@ = pointer to source integer
+ * @size_t *s@ = where to store the power of 2
*
- * Returns: ---
+ * Returns: An odd integer integer %$t$% such that %$m = 2^s t$%.
*
- * Use: Performs unsigned MP addition.
+ * Use: Computes a power of two and an odd integer which, when
+ * multiplied, give a specified result. This sort of thing is
+ * useful in number theory quite often.
*/
-extern void mp_uadd(mp */*d*/, const mp */*x*/, const mp */*y*/);
+extern mp *mp_odd(mp */*d*/, mp */*m*/, size_t */*s*/);
-/* --- @mp_usub@ --- *
+/*----- More advanced algorithms ------------------------------------------*/
+
+/* --- @mp_sqrt@ --- *
*
- * Arguments: @const mp *d@ = pointers to MP head of destination
- * @const mp *x, *y@ = pointers to MP heads of operands
+ * Arguments: @mp *d@ = pointer to destination integer
+ * @mp *a@ = (nonnegative) integer to take square root of
*
- * Returns: ---
+ * Returns: The largest integer %$x$% such that %$x^2 \le a$%.
*
- * Use: Performs unsigned MP subtraction.
+ * Use: Computes integer square roots.
+ *
+ * The current implementation isn't very good: it uses the
+ * Newton-Raphson method to find an approximation to %$a$%. If
+ * there's any demand for a better version, I'll write one.
*/
-extern void mp_usub(mp */*d*/, const mp */*x*/, const mp */*y*/);
+extern mp *mp_sqrt(mp */*d*/, mp */*a*/);
-/* --- @mp_ucmp@ --- *
+/* --- @mp_gcd@ --- *
*
- * Arguments: @const mp *x, *y@ = pointers to MP heads of operands
+ * Arguments: @mp **gcd, **xx, **yy@ = where to write the results
+ * @mp *a, *b@ = sources (must be nonzero)
*
- * Returns: Less than, equal to, or greater than zero.
+ * Returns: ---
*
- * Use: Performs unsigned MP comparison.
+ * 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.
*/
-#define MP_UCMP(x, op, y) (mp_ucmp((x), (y)) op 0)
+extern void mp_gcd(mp **/*gcd*/, mp **/*xx*/, mp **/*yy*/,
+ mp */*a*/, mp */*b*/);
-extern int mp_ucmp(const mp */*x*/, const mp */*y*/);
-
-/* --- @mp_umul@ --- *
+/* --- @mp_jacobi@ --- *
*
- * Arguments: @mp *d@ = pointer to MP head of destination
- * @const mp *x, *y@ = pointes to MP heads of 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 multiplication.
+ * 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_umul(mp */*d*/, const mp */*x*/, const mp */*y*/);
+extern int mp_jacobi(mp */*a*/, mp */*n*/);
-/* --- @mp_udiv@ --- *
+/* --- @mp_modsqrt@ --- *
*
- * Arguments: @mp *q, *r@ = pointers to MP heads for quotient, remainder
- * @const mp *x, *y@ = pointers to MP heads for operands
+ * Arguments: @mp *d@ = destination integer
+ * @mp *a@ = source integer
+ * @mp *p@ = modulus (must be prime)
*
- * Returns: ---
+ * Returns: If %$a$% is a quadratic residue, a square root of %$a$%; else
+ * a null pointer.
*
- * Use: Performs unsigned MP division.
+ * Use: Returns an integer %$x$% such that %$x^2 \equiv a \pmod{p}$%,
+ * if one exists; else a null pointer. This function will not
+ * work if %$p$% is composite: you must factor the modulus, take
+ * a square root mod each factor, and recombine the results
+ * using the Chinese Remainder Theorem.
*/
-extern void mp_udiv(mp */*q*/, mp */*r*/, const mp */*x*/, const mp */*y*/);
+extern mp *mp_modsqrt(mp */*d*/, mp */*a*/, mp */*p*/);
+
+/*----- Test harness support ----------------------------------------------*/
+
+#include <mLib/testrig.h>
+
+#ifndef CATACOMB_MPTEXT_H
+# include "mptext.h"
+#endif
+
+extern const test_type type_mp;
/*----- That's all, folks -------------------------------------------------*/
projects / u / mdw / catacomb / blobdiff