3 * $Id: mp.h,v 1.7 2000/06/17 11:45:09 mdw Exp $
5 * Simple multiprecision arithmetic
7 * (c) 1999 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
14 * Catacomb is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU Library General Public License as
16 * published by the Free Software Foundation; either version 2 of the
17 * License, or (at your option) any later version.
19 * Catacomb is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU Library General Public License for more details.
24 * You should have received a copy of the GNU Library General Public
25 * License along with Catacomb; if not, write to the Free
26 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
30 /*----- Revision history --------------------------------------------------*
33 * Revision 1.7 2000/06/17 11:45:09 mdw
34 * Major memory management overhaul. Added arena support. Use the secure
35 * arena for secret integers. Replace and improve the MP management macros
36 * (e.g., replace MP_MODIFY by MP_DEST).
38 * Revision 1.6 1999/12/10 23:19:46 mdw
39 * Minor bugfixes. New interface for suggested destinations.
41 * Revision 1.5 1999/11/22 20:50:37 mdw
42 * Add support for computing Jacobi symbols.
44 * Revision 1.4 1999/11/21 22:13:02 mdw
45 * Add mp version of MPX_BITS.
47 * Revision 1.3 1999/11/19 13:19:14 mdw
48 * Fix const annotation.
50 * Revision 1.2 1999/11/17 18:02:16 mdw
51 * New multiprecision integer arithmetic suite.
62 /*----- Header files ------------------------------------------------------*/
69 #ifndef CATACOMB_MPW_H
73 #ifndef CATACOMB_ARENA_H
77 #ifndef CATACOMB_MPARENA_H
81 #ifndef CATACOMB_MPX_H
85 /*----- Data structures ---------------------------------------------------*/
99 #define MP_DESTROYED 16u
101 /*----- Useful constants --------------------------------------------------*/
103 extern mp mp_const
[];
105 #define MP_ZERO (&mp_const[0])
106 #define MP_ONE (&mp_const[1])
107 #define MP_TWO (&mp_const[2])
108 #define MP_THREE (&mp_const[3])
109 #define MP_FOUR (&mp_const[4])
110 #define MP_FIVE (&mp_const[5])
111 #define MP_TEN (&mp_const[6])
112 #define MP_256 (&mp_const[7])
113 #define MP_MONE (&mp_const[8])
115 #define MP_NEW ((mp *)0)
116 #define MP_NEWSEC (&mp_const[9])
118 /*----- Trivial macros ----------------------------------------------------*/
120 /* --- @MP_LEN@ --- *
122 * Arguments: @mp *m@ = pointer to a multiprecision integer
124 * Returns: Length of the integer, in words.
127 #define MP_LEN(m) ((m)->vl - ((m)->v))
129 /*----- Memory management and reference counting --------------------------*/
131 /* --- @mp_new@ --- *
133 * Arguments: @size_t sz@ = size of vector required
134 * @unsigned f@ = flags to set
136 * Returns: Pointer to a new MP structure.
138 * Use: Allocates a new multiprecision integer. The data space is
139 * allocated from either the standard global or secret arena,
140 * depending on the initial flags requested.
143 extern mp
*mp_new(size_t /*sz*/, unsigned /*f*/);
145 /* --- @mp_create@ --- *
147 * Arguments: @size_t sz@ = size of vector required
149 * Returns: Pointer to pristine new MP structure with enough memory
152 * Use: Creates a new multiprecision integer with indeterminate
153 * contents. The integer has a single reference.
156 extern mp
*mp_create(size_t /*sz*/);
158 /* --- @mp_createsecure@ --- *
160 * Arguments: @size_t sz@ = size of vector required
162 * Returns: Pointer to pristine new MP structure with enough memory
165 * Use: Creates a new multiprecision integer with indeterminate
166 * contents. The integer has a single reference. The integer's
167 * data space is allocated from the secure arena. Its burn flag
171 extern mp
*mp_createsecure(size_t /*sz*/);
173 /* --- @mp_build@ --- *
175 * Arguments: @mp *m@ = pointer to an MP block to fill in
176 * @mpw *v@ = pointer to a word array
177 * @mpw *vl@ = pointer just past end of array
181 * Use: Creates a multiprecision integer representing some smallish
182 * number. You must provide storage for the number and dispose
183 * of it when you've finished with it. The number is marked as
184 * constant while it exists.
187 extern void mp_build(mp */
*m*/
, mpw */
*v*/
, mpw */
*vl*/
);
189 /* --- @mp_destroy@ --- *
191 * Arguments: @mp *m@ = pointer to a multiprecision integer
195 * Use: Destroys a multiprecision integer. The reference count isn't
196 * checked. Don't use this function if you don't know what
197 * you're doing: use @mp_drop@ instead.
200 extern void mp_destroy(mp */
*m*/
);
202 /* --- @mp_copy@ --- *
204 * Arguments: @mp *m@ = pointer to a multiprecision integer
206 * Returns: A copy of the given multiprecision integer.
208 * Use: Copies the given integer. In fact you just get another
209 * reference to the same old one again.
212 extern mp
*mp_copy(mp */
*m*/
);
214 #define MP_COPY(m) ((m)->ref++, (m))
216 /* --- @mp_drop@ --- *
218 * Arguments: @mp *m@ = pointer to a multiprecision integer
222 * Use: Drops a reference to an integer which isn't wanted any more.
223 * If there are no more references, the integer is destroyed.
226 extern void mp_drop(mp */
*m*/
);
228 #define MP_DROP(m) do { \
231 if (_mm->ref == 0 && !(_mm->f & MP_CONST)) \
235 /* --- @mp_split@ --- *
237 * Arguments: @mp *m@ = pointer to a multiprecision integer
239 * Returns: A reference to the same integer, possibly with a different
242 * Use: Splits off a modifiable version of the integer referred to.
245 extern mp
*mp_split(mp */
*m*/
);
247 #define MP_SPLIT(m) do { \
249 if ((_m->f & MP_CONST) || _m->ref > 1) { \
250 size_t _len = MP_LEN(_m); \
251 mp *_mm = mp_new(_len, _m->f); \
252 if (!(_m->f & MP_UNDEF)) \
253 memcpy(_mm->v, _m->v, MPWS(_len)); \
260 /* --- @mp_resize@ --- *
262 * Arguments: @mp *m@ = pointer to a multiprecision integer
263 * @size_t sz@ = new size
267 * Use: Resizes the vector containing the integer's digits. The new
268 * size must be at least as large as the current integer's
269 * length. This isn't really intended for client use.
272 extern void mp_resize(mp */
*m*/
, size_t /*sz*/);
274 #define MP_RESIZE(m, ssz) do { \
276 size_t _sz = (ssz); \
277 mparena *_a = (_m->f & MP_BURN) ? MPARENA_SECURE : MPARENA_GLOBAL; \
279 size_t _len = MP_LEN(_m); \
280 assert(((void)"can't make size less than length", _sz >= _len)); \
281 _v = mpalloc(_a, _sz); \
282 if (!(_m->f & MP_UNDEF)) \
283 memcpy(_v, _m->v, MPWS(_len)); \
284 if (_m->f & MP_BURN) \
285 memset(_m->v, 0, MPWS(_m->sz)); \
286 mpfree(_m->a, _m->v); \
289 _m->vl = _v + _len; \
292 /* --- @mp_ensure@ --- *
294 * Arguments: @mp *m@ = pointer to a multiprecision integer
295 * @size_t sz@ = required size
299 * Use: Ensures that the integer has enough space for @sz@ digits.
300 * The value is not changed.
303 extern void mp_ensure(mp */
*m*/
, size_t /*sz*/);
305 #define MP_ENSURE(m, ssz) do { \
307 size_t _ssz = (ssz); \
308 size_t _len = MP_LEN(_m); \
309 if (_ssz >= _len) { \
311 mp_resize(_m, _ssz); \
312 if (!(_m->f & MP_UNDEF) && _ssz > _len) \
313 memset(_m->vl, 0, MPWS(_ssz - _len)); \
314 _m->vl = _m->v + _ssz; \
318 /* --- @mp_dest@ --- *
320 * Arguments: @mp *m@ = a suggested destination integer
321 * @size_t sz@ = size required for result, in digits
322 * @unsigned f@ = various flags
324 * Returns: A pointer to an appropriate destination.
326 * Use: Converts a suggested destination into a real destination with
327 * the required properties. If the real destination is @d@,
328 * then the following properties will hold:
330 * * @d@ will have exactly one reference.
332 * * If @m@ is not @MP_NEW@, then the contents of @m@ will not
333 * change, unless @f@ has the @MP_UNDEF@ flag set.
335 * * If @m@ is not @MP_NEW@, then he reference count of @m@ on
336 * entry is equal to the sum of the counts of @d@ and @m@ on
339 * * The size of @d@ will be at least @sz@.
341 * * If @f@ has the @MP_BURN@ flag set, then @d@ will be
342 * allocated from @MPARENA_SECURE@.
344 * Understanding this function is crucial to using Catacomb's
345 * multiprecision integer library effectively.
348 extern mp
*mp_dest(mp */
*m*/
, size_t /*sz*/, unsigned /*f*/);
350 #define MP_DEST(m, ssz, f) do { \
352 size_t _ssz = (ssz); \
354 _m = mp_dest(_m, _ssz, _f); \
358 /*----- Size manipulation -------------------------------------------------*/
360 /* --- @mp_shrink@ --- *
362 * Arguments: @mp *m@ = pointer to a multiprecision integer
366 * Use: Reduces the recorded length of an integer. This doesn't
367 * reduce the amount of memory used, although it can improve
368 * performance a bit. To reduce memory, use @mp_minimize@
369 * instead. This can't change the value of an integer, and is
370 * therefore safe to use even when there are multiple
374 extern void mp_shrink(mp */
*m*/
);
376 #define MP_SHRINK(m) do { \
378 MPX_SHRINK(_mm->v, _mm->vl); \
383 /* --- @mp_minimize@ --- *
385 * Arguments: @mp *m@ = pointer to a multiprecision integer
389 * Use: Reduces the amount of memory an integer uses. It's best to
390 * do this to numbers which aren't going to change in the
394 extern void mp_minimize(mp */
*m*/
);
396 /*----- Bit scanning ------------------------------------------------------*/
398 #ifndef CATACOMB_MPSCAN_H
402 /* --- @mp_scan@ --- *
404 * Arguments: @mpscan *sc@ = pointer to bitscanner block
405 * @const mp *m@ = pointer to a multiprecision integer
409 * Use: Initializes a bitscanner on a multiprecision integer.
412 extern void mp_scan(mpscan */
*sc*/
, const mp */
*m*/
);
414 #define MP_SCAN(sc, m) do { \
415 const mp *_mm = (m); \
416 mpscan *_sc = (sc); \
417 MPSCAN_INITX(_sc, _mm->v, _mm->vl); \
420 /* --- Other bitscanning aliases --- */
422 #define mp_step mpscan_step
423 #define mp_bit mpscan_bit
425 #define MP_STEP MPSCAN_STEP
426 #define MP_BIT MPSCAN_BIT
428 /*----- Loading and storing -----------------------------------------------*/
430 /* --- @mp_octets@ --- *
432 * Arguments: @const mp *m@ = a multiprecision integer
434 * Returns: The number of octets required to represent @m@.
436 * Use: Calculates the external storage required for a multiprecision
440 extern size_t mp_octets(const mp */
*m*/
);
442 /* --- @mp_bits@ --- *
444 * Arguments: @const mp *m@ = a multiprecision integer
446 * Returns: The number of bits required to represent @m@.
448 * Use: Calculates the external storage required for a multiprecision
452 extern unsigned long mp_bits(const mp */
*m*/
);
454 /* --- @mp_loadl@ --- *
456 * Arguments: @mp *d@ = destination
457 * @const void *pv@ = pointer to source data
458 * @size_t sz@ = size of the source data
460 * Returns: Resulting multiprecision number.
462 * Use: Loads a multiprecision number from an array of octets. The
463 * first byte in the array is the least significant. More
464 * formally, if the bytes are %$b_0, b_1, \ldots, b_{n-1}$%
465 * then the result is %$N = \sum_{0 \le i < n} b_i 2^{8i}$%.
468 extern mp
*mp_loadl(mp */
*d*/
, const void */
*pv*/
, size_t /*sz*/);
470 /* --- @mp_storel@ --- *
472 * Arguments: @const mp *m@ = source
473 * @void *pv@ = pointer to output array
474 * @size_t sz@ = size of the output array
478 * Use: Stores a multiprecision number in an array of octets. The
479 * first byte in the array is the least significant. If the
480 * array is too small to represent the number, high-order bits
481 * are truncated; if the array is too large, high order bytes
482 * are filled with zeros. More formally, if the number is
483 * %$N = \sum{0 \le i} b_i 2^{8i}$% where %$0 \le b_i < 256$%,
484 * then the array is %$b_0, b_1, \ldots, b_{n-1}$%.
487 extern void mp_storel(const mp */
*m*/
, void */
*pv*/
, size_t /*sz*/);
489 /* --- @mp_loadb@ --- *
491 * Arguments: @mp *d@ = destination
492 * @const void *pv@ = pointer to source data
493 * @size_t sz@ = size of the source data
495 * Returns: Resulting multiprecision number.
497 * Use: Loads a multiprecision number from an array of octets. The
498 * last byte in the array is the least significant. More
499 * formally, if the bytes are %$b_{n-1}, b_{n-2}, \ldots, b_0$%
500 * then the result is %$N = \sum_{0 \le i < n} b_i 2^{8i}$%.
503 extern mp
*mp_loadb(mp */
*d*/
, const void */
*pv*/
, size_t /*sz*/);
505 /* --- @mp_storeb@ --- *
507 * Arguments: @const mp *m@ = source
508 * @void *pv@ = pointer to output array
509 * @size_t sz@ = size of the output array
513 * Use: Stores a multiprecision number in an array of octets. The
514 * last byte in the array is the least significant. If the
515 * array is too small to represent the number, high-order bits
516 * are truncated; if the array is too large, high order bytes
517 * are filled with zeros. More formally, if the number is
518 * %$N = \sum{0 \le i} b_i 2^{8i}$% where %$0 \le b_i < 256$%,
519 * then the array is %$b_{n-1}, b_{n-2}, \ldots, b_0$%.
522 extern void mp_storeb(const mp */
*m*/
, void */
*pv*/
, size_t /*sz*/);
524 /*----- Simple arithmetic -------------------------------------------------*/
528 * Arguments: @mp *d@ = destination
531 * Returns: Result, @a@ converted to two's complement notation.
534 extern mp
*mp_2c(mp */
*d*/
, mp */
*a*/
);
538 * Arguments: @mp *d@ = destination
541 * Returns: Result, @a@ converted to the native signed-magnitude
545 extern mp
*mp_sm(mp */
*d*/
, mp */
*a*/
);
547 /* --- @mp_lsl@ --- *
549 * Arguments: @mp *d@ = destination
551 * @size_t n@ = number of bits to move
553 * Returns: Result, @a@ shifted left by @n@.
556 extern mp
*mp_lsl(mp */
*d*/
, mp */
*a*/
, size_t /*n*/);
558 /* --- @mp_lsr@ --- *
560 * Arguments: @mp *d@ = destination
562 * @size_t n@ = number of bits to move
564 * Returns: Result, @a@ shifted left by @n@.
567 extern mp
*mp_lsr(mp */
*d*/
, mp */
*a*/
, size_t /*n*/);
569 /* --- @mp_cmp@ --- *
571 * Arguments: @const mp *a, *b@ = two numbers
573 * Returns: Less than, equal to or greater than zero, according to
574 * whether @a@ is less than, equal to or greater than @b@.
577 extern int mp_cmp(const mp */
*a*/
, const mp */
*b*/
);
579 #define MP_CMP(a, op, b) (mp_cmp((a), (b)) op 0)
581 /* --- @mp_add@ --- *
583 * Arguments: @mp *d@ = destination
584 * @mp *a, *b@ = sources
586 * Returns: Result, @a@ added to @b@.
589 extern mp
*mp_add(mp */
*d*/
, mp */
*a*/
, mp */
*b*/
);
591 /* --- @mp_sub@ --- *
593 * Arguments: @mp *d@ = destination
594 * @mp *a, *b@ = sources
596 * Returns: Result, @b@ subtracted from @a@.
599 extern mp
*mp_sub(mp */
*d*/
, mp */
*a*/
, mp */
*b*/
);
601 /* --- @mp_mul@ --- *
603 * Arguments: @mp *d@ = destination
604 * @mp *a, *b@ = sources
606 * Returns: Result, @a@ multiplied by @b@.
609 extern mp
*mp_mul(mp */
*d*/
, mp */
*a*/
, mp */
*b*/
);
611 /* --- @mp_sqr@ --- *
613 * Arguments: @mp *d@ = destination
616 * Returns: Result, @a@ squared.
619 extern mp
*mp_sqr(mp */
*d*/
, mp */
*a*/
);
621 /* --- @mp_div@ --- *
623 * Arguments: @mp **qq, **rr@ = destination, quotient and remainder
624 * @mp *a, *b@ = sources
626 * Use: Calculates the quotient and remainder when @a@ is divided by
630 extern void mp_div(mp
**/
*qq*/
, mp
**/
*rr*/
, mp */
*a*/
, mp */
*b*/
);
632 /*----- More advanced algorithms ------------------------------------------*/
634 /* --- @mp_gcd@ --- *
636 * Arguments: @mp **gcd, **xx, **yy@ = where to write the results
637 * @mp *a, *b@ = sources (must be nonzero)
641 * Use: Calculates @gcd(a, b)@, and two numbers @x@ and @y@ such that
642 * @ax + by = gcd(a, b)@. This is useful for computing modular
643 * inverses. Neither @a@ nor @b@ may be zero.
646 extern void mp_gcd(mp
**/
*gcd*/
, mp
**/
*xx*/
, mp
**/
*yy*/
,
647 mp */
*a*/
, mp */
*b*/
);
649 /* --- @mp_jacobi@ --- *
651 * Arguments: @mp *a@ = an integer less than @n@
652 * @mp *n@ = an odd integer
654 * Returns: @-1@, @0@ or @1@ -- the Jacobi symbol %$J(a, n)$%.
656 * Use: Computes the Jacobi symbol. If @n@ is prime, this is the
657 * Legendre symbol and is equal to 1 if and only if @a@ is a
658 * quadratic residue mod @n@. The result is zero if and only if
659 * @a@ and @n@ have a common factor greater than one.
662 int mp_jacobi(mp */
*a*/
, mp */
*n*/
);
664 /*----- Test harness support ----------------------------------------------*/
666 #include <mLib/testrig.h>
668 #ifndef CATACOMB_MPTEXT_H
672 extern const test_type type_mp
;
674 /*----- That's all, folks -------------------------------------------------*/