3 * $Id: mp.h,v 1.4 1999/11/21 22:13:02 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.4 1999/11/21 22:13:02 mdw
34 * Add mp version of MPX_BITS.
36 * Revision 1.3 1999/11/19 13:19:14 mdw
37 * Fix const annotation.
39 * Revision 1.2 1999/11/17 18:02:16 mdw
40 * New multiprecision integer arithmetic suite.
51 /*----- Header files ------------------------------------------------------*/
66 /*----- Data structures ---------------------------------------------------*/
80 /*----- Useful constants --------------------------------------------------*/
84 #define MP_ZERO (&mp_const[0])
85 #define MP_ONE (&mp_const[1])
86 #define MP_TWO (&mp_const[2])
87 #define MP_THREE (&mp_const[3])
88 #define MP_FOUR (&mp_const[4])
89 #define MP_FIVE (&mp_const[5])
90 #define MP_TEN (&mp_const[6])
91 #define MP_MONE (&mp_const[7])
93 #define MP_NEW ((mp *)0)
95 /*----- Memory allocation hooks -------------------------------------------*/
101 /* --- @MP_ARENA@ --- *
103 * This selects where memory is allocated from. Tweak to use more fancy
104 * things like custom arenas.
108 # define MP_ARENA MPARENA_GLOBAL
111 /* --- @MP_ALLOC@ --- *
113 * Arguments: @size_t sz@ = size required
115 * Returns: Pointer to an allocated vector of the requested size.
117 * Use: Hook for vector allocation.
121 # define MP_ALLOC(sz) mpalloc(MP_ARENA, (sz))
124 /* --- @MP_FREE@ --- *
126 * Arguments: @mpw *v@ = pointer to vector
130 * Use: Hook for vector deallocation.
134 # define MP_FREE(v) mpfree(MP_ARENA, (v))
137 /*----- Paranoia management -----------------------------------------------*/
139 /* --- @mp_burn@ --- *
141 * Arguments: @mp *m@ = pointer to a multiprecision integer
145 * Use: Marks the integer as `burn-after-use'. When the integer's
146 * memory is deallocated, it is deleted so that traces can't
147 * remain in the swap file. In theory.
150 extern void mp_burn(mp */
*m*/
);
152 /*----- Trivial macros ----------------------------------------------------*/
154 /* --- @MP_LEN@ --- *
156 * Arguments: @mp *m@ = pointer to a multiprecision integer
158 * Returns: Length of the integer, in words.
161 #define MP_LEN(m) ((m)->vl - ((m)->v))
163 /*----- Memory management and reference counting --------------------------*/
165 /* --- @mp_create@ --- *
167 * Arguments: @size_t sz@ = size of vector required
169 * Returns: Pointer to pristine new MP structure with enough memory
172 * Use: Creates a new multiprecision integer with indeterminate
173 * contents. The integer has a single reference.
176 extern mp
*mp_create(size_t /*sz*/);
178 /* --- @mp_build@ --- *
180 * Arguments: @mp *m@ = pointer to an MP block to fill in
181 * @mpw *v@ = pointer to a word array
182 * @mpw *vl@ = pointer just past end of array
186 * Use: Creates a multiprecision integer representing some smallish
187 * number. You must provide storage for the number and dispose
188 * of it when you've finished with it. The number is marked as
189 * constant while it exists.
192 extern void mp_build(mp */
*m*/
, mpw */
*v*/
, mpw */
*vl*/
);
194 /* --- @mp_destroy@ --- *
196 * Arguments: @mp *m@ = pointer to a multiprecision integer
200 * Use: Destroys a multiprecision integer. The reference count isn't
201 * checked. Don't use this function if you don't know what
202 * you're doing: use @mp_drop@ instead.
205 extern void mp_destroy(mp */
*m*/
);
207 /* --- @mp_copy@ --- *
209 * Arguments: @mp *m@ = pointer to a multiprecision integer
211 * Returns: A copy of the given multiprecision integer.
213 * Use: Copies the given integer. In fact you just get another
214 * reference to the same old one again.
217 extern mp
*mp_copy(mp */
*m*/
);
219 #define MP_COPY(m) ((m)->ref++, (m))
221 /* --- @mp_drop@ --- *
223 * Arguments: @mp *m@ = pointer to a multiprecision integer
227 * Use: Drops a reference to an integer which isn't wanted any more.
228 * If there are no more references, the integer is destroyed.
231 extern void mp_drop(mp */
*m*/
);
233 #define MP_DROP(m) do { \
237 else if (!(_mm->f & MP_CONST)) \
241 /* --- @mp_split@ --- *
243 * Arguments: @mp *m@ = pointer to a multiprecision integer
245 * Returns: A reference to the same integer, possibly with a different
248 * Use: Splits off a modifiable version of the integer referred to.
251 extern mp
*mp_split(mp */
*m*/
);
253 #define MP_SPLIT(m) do { \
255 if ((_mm->f & MP_CONST) || _mm->ref != 1) { \
256 mp *_dd = mp_create(_mm->sz); \
257 _dd->vl = _dd->v + MP_LEN(_mm); \
258 _dd->f = _mm->f & (MP_NEG | MP_BURN); \
259 memcpy(_dd->v, _mm->v, MPWS(MP_LEN(_mm))); \
266 /* --- @mp_resize@ --- *
268 * Arguments: @mp *m@ = pointer to a multiprecision integer
269 * @size_t sz@ = new size
273 * Use: Resizes the vector containing the integer's digits. The new
274 * size must be at least as large as the current integer's
275 * length. The integer's length is increased and new digits are
276 * filled with zeroes. This isn't really intended for client
280 extern void mp_resize(mp */
*m*/
, size_t /*sz*/);
282 #define MP_RESIZE(m, ssz) do { \
284 size_t _sz = (ssz); \
285 size_t _len = MP_LEN(_m); \
286 mpw *_v = MP_ALLOC(_sz); \
287 memcpy(_v, _m->v, MPWS(_len)); \
288 if (_m->f & MP_BURN) \
289 memset(_m->v, 0, MPWS(_m->sz)); \
292 _m->vl = _v + _len; \
296 /* --- @mp_ensure@ --- *
298 * Arguments: @mp *m@ = pointer to a multiprecision integer
299 * @size_t sz@ = required size
303 * Use: Ensures that the integer has enough space for @sz@ digits.
304 * The value is not changed.
307 extern void mp_ensure(mp */
*m*/
, size_t /*sz*/);
309 #define MP_ENSURE(m, ssz) do { \
311 size_t _ssz = (ssz); \
312 size_t _len = MP_LEN(_mm); \
313 if (_ssz > _mm->sz) \
314 MP_RESIZE(_mm, _ssz); \
315 if (!(_mm->f & MP_UNDEF) && _ssz > _len) { \
316 memset(_mm->vl, 0, MPWS(_ssz - _len)); \
317 _mm->vl = _mm->v + _ssz; \
321 /* --- @mp_modify@ --- *
323 * Arguments: @mp *m@ = pointer to a multiprecision integer
324 * @size_t sz@ = size required
326 * Returns: Pointer to the integer (possibly different).
328 * Use: Prepares an integer to be overwritten. It's split off from
329 * other references to the same integer, and sufficient space is
333 extern mp
*mp_modify(mp */
*m*/
, size_t /*sz*/);
335 #define MP_MODIFY(m, sz) do { \
339 _m = mp_create(_rq); \
342 MP_ENSURE(_m, _rq); \
344 _m->vl = _m->v + _rq; \
348 /*----- Size manipulation -------------------------------------------------*/
350 /* --- @mp_shrink@ --- *
352 * Arguments: @mp *m@ = pointer to a multiprecision integer
356 * Use: Reduces the recorded length of an integer. This doesn't
357 * reduce the amount of memory used, although it can improve
358 * performance a bit. To reduce memory, use @mp_minimize@
359 * instead. This can't change the value of an integer, and is
360 * therefore safe to use even when there are multiple
364 extern void mp_shrink(mp */
*m*/
);
366 #define MP_SHRINK(m) do { \
368 MPX_SHRINK(_mm->v, _mm->vl); \
373 /* --- @mp_minimize@ --- *
375 * Arguments: @mp *m@ = pointer to a multiprecision integer
379 * Use: Reduces the amount of memory an integer uses. It's best to
380 * do this to numbers which aren't going to change in the
384 extern void mp_minimize(mp */
*m*/
);
386 /*----- Bit scanning ------------------------------------------------------*/
392 /* --- @mp_scan@ --- *
394 * Arguments: @mpscan *sc@ = pointer to bitscanner block
395 * @const mp *m@ = pointer to a multiprecision integer
399 * Use: Initializes a bitscanner on a multiprecision integer.
402 extern void mp_scan(mpscan */
*sc*/
, const mp */
*m*/
);
404 #define MP_SCAN(sc, m) do { \
405 const mp *_mm = (m); \
406 mpscan *_sc = (sc); \
407 MPSCAN_INITX(_sc, _mm->v, _mm->vl); \
410 /* --- Other bitscanning aliases --- */
412 #define mp_step mpscan_step
413 #define mp_bit mpscan_bit
415 #define MP_STEP MPSCAN_STEP
416 #define MP_BIT MPSCAN_BIT
418 /*----- Loading and storing -----------------------------------------------*/
420 /* --- @mp_octets@ --- *
422 * Arguments: @const mp *m@ = a multiprecision integer
424 * Returns: The number of octets required to represent @m@.
426 * Use: Calculates the external storage required for a multiprecision
430 extern size_t mp_octets(const mp */
*m*/
);
432 /* --- @mp_bits@ --- *
434 * Arguments: @const mp *m@ = a multiprecision integer
436 * Returns: The number of bits required to represent @m@.
438 * Use: Calculates the external storage required for a multiprecision
442 extern unsigned long mp_bits(const mp */
*m*/
);
444 /* --- @mp_loadl@ --- *
446 * Arguments: @mp *d@ = destination
447 * @const void *pv@ = pointer to source data
448 * @size_t sz@ = size of the source data
450 * Returns: Resulting multiprecision number.
452 * Use: Loads a multiprecision number from an array of octets. The
453 * first byte in the array is the least significant. More
454 * formally, if the bytes are %$b_0, b_1, \ldots, b_{n-1}$%
455 * then the result is %$N = \sum_{0 \le i < n} b_i 2^{8i}$%.
458 extern mp
*mp_loadl(mp */
*d*/
, const void */
*pv*/
, size_t /*sz*/);
460 /* --- @mp_storel@ --- *
462 * Arguments: @const mp *m@ = source
463 * @void *pv@ = pointer to output array
464 * @size_t sz@ = size of the output array
468 * Use: Stores a multiprecision number in an array of octets. The
469 * first byte in the array is the least significant. If the
470 * array is too small to represent the number, high-order bits
471 * are truncated; if the array is too large, high order bytes
472 * are filled with zeros. More formally, if the number is
473 * %$N = \sum{0 \le i} b_i 2^{8i}$% where %$0 \le b_i < 256$%,
474 * then the array is %$b_0, b_1, \ldots, b_{n-1}$%.
477 extern void mp_storel(const mp */
*m*/
, void */
*pv*/
, size_t /*sz*/);
479 /* --- @mp_loadb@ --- *
481 * Arguments: @mp *d@ = destination
482 * @const void *pv@ = pointer to source data
483 * @size_t sz@ = size of the source data
485 * Returns: Resulting multiprecision number.
487 * Use: Loads a multiprecision number from an array of octets. The
488 * last byte in the array is the least significant. More
489 * formally, if the bytes are %$b_{n-1}, b_{n-2}, \ldots, b_0$%
490 * then the result is %$N = \sum_{0 \le i < n} b_i 2^{8i}$%.
493 extern mp
*mp_loadb(mp */
*d*/
, const void */
*pv*/
, size_t /*sz*/);
495 /* --- @mp_storeb@ --- *
497 * Arguments: @const mp *m@ = source
498 * @void *pv@ = pointer to output array
499 * @size_t sz@ = size of the output array
503 * Use: Stores a multiprecision number in an array of octets. The
504 * last byte in the array is the least significant. If the
505 * array is too small to represent the number, high-order bits
506 * are truncated; if the array is too large, high order bytes
507 * are filled with zeros. More formally, if the number is
508 * %$N = \sum{0 \le i} b_i 2^{8i}$% where %$0 \le b_i < 256$%,
509 * then the array is %$b_{n-1}, b_{n-2}, \ldots, b_0$%.
512 extern void mp_storeb(const mp */
*m*/
, void */
*pv*/
, size_t /*sz*/);
514 /*----- Simple arithmetic -------------------------------------------------*/
518 * Arguments: @mp *d@ = destination
521 * Returns: Result, @a@ converted to two's complement notation.
524 extern mp
*mp_2c(mp */
*d*/
, mp */
*a*/
);
528 * Arguments: @mp *d@ = destination
531 * Returns: Result, @a@ converted to the native signed-magnitude
535 extern mp
*mp_sm(mp */
*d*/
, mp */
*a*/
);
537 /* --- @mp_lsl@ --- *
539 * Arguments: @mp *d@ = destination
540 * @const mp *a@ = source
541 * @size_t n@ = number of bits to move
543 * Returns: Result, @a@ shifted left by @n@.
546 extern mp
*mp_lsl(mp */
*d*/
, const mp */
*a*/
, size_t /*n*/);
548 /* --- @mp_lsr@ --- *
550 * Arguments: @mp *d@ = destination
551 * @const mp *a@ = source
552 * @size_t n@ = number of bits to move
554 * Returns: Result, @a@ shifted left by @n@.
557 extern mp
*mp_lsr(mp */
*d*/
, const mp */
*a*/
, size_t /*n*/);
559 /* --- @mp_cmp@ --- *
561 * Arguments: @const mp *a, *b@ = two numbers
563 * Returns: Less than, equal to or greater than zero, according to
564 * whether @a@ is less than, equal to or greater than @b@.
567 extern int mp_cmp(const mp */
*a*/
, const mp */
*b*/
);
569 #define MP_CMP(a, op, b) (mp_cmp((a), (b)) op 0)
571 /* --- @mp_add@ --- *
573 * Arguments: @mp *d@ = destination
574 * @const mp *a, *b@ = sources
576 * Returns: Result, @a@ added to @b@.
579 extern mp
*mp_add(mp */
*d*/
, const mp */
*a*/
, const mp */
*b*/
);
581 /* --- @mp_sub@ --- *
583 * Arguments: @mp *d@ = destination
584 * @const mp *a, *b@ = sources
586 * Returns: Result, @b@ subtracted from @a@.
589 extern mp
*mp_sub(mp */
*d*/
, const mp */
*a*/
, const mp */
*b*/
);
591 /* --- @mp_mul@ --- *
593 * Arguments: @mp *d@ = destination
594 * @const mp *a, *b@ = sources
596 * Returns: Result, @a@ multiplied by @b@.
599 extern mp
*mp_mul(mp */
*d*/
, const mp */
*a*/
, const mp */
*b*/
);
601 /* --- @mp_sqr@ --- *
603 * Arguments: @mp *d@ = destination
604 * @const mp *a@ = source
606 * Returns: Result, @a@ squared.
609 extern mp
*mp_sqr(mp */
*d*/
, const mp */
*a*/
);
611 /* --- @mp_div@ --- *
613 * Arguments: @mp **qq, **rr@ = destination, quotient and remainder
614 * @const mp *a, *b@ = sources
616 * Use: Calculates the quotient and remainder when @a@ is divided by
620 extern void mp_div(mp
**/
*qq*/
, mp
**/
*rr*/
,
621 const mp */
*a*/
, const mp */
*b*/
);
623 /*----- More advanced algorithms ------------------------------------------*/
625 /* --- @mp_gcd@ --- *
627 * Arguments: @mp **gcd, **xx, **yy@ = where to write the results
628 * @mp *a, *b@ = sources (must be nonzero)
632 * Use: Calculates @gcd(a, b)@, and two numbers @x@ and @y@ such that
633 * @ax + by = gcd(a, b)@. This is useful for computing modular
634 * inverses. Neither @a@ nor @b@ may be zero. Note that,
635 * unlike @mp_div@ for example, it is not possible to specify
636 * explicit destinations -- new MPs are always allocated.
639 extern void mp_gcd(mp
**/
*gcd*/
, mp
**/
*xx*/
, mp
**/
*yy*/
,
640 mp */
*a*/
, mp */
*b*/
);
642 /*----- Test harness support ----------------------------------------------*/
644 #include <mLib/testrig.h>
650 extern const test_type type_mp
;
652 /*----- That's all, folks -------------------------------------------------*/