3 * $Id: mp.h,v 1.3 1999/11/19 13:19:14 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.3 1999/11/19 13:19:14 mdw
34 * Fix const annotation.
36 * Revision 1.2 1999/11/17 18:02:16 mdw
37 * New multiprecision integer arithmetic suite.
48 /*----- Header files ------------------------------------------------------*/
63 /*----- Data structures ---------------------------------------------------*/
77 /*----- Useful constants --------------------------------------------------*/
81 #define MP_ZERO (&mp_const[0])
82 #define MP_ONE (&mp_const[1])
83 #define MP_TWO (&mp_const[2])
84 #define MP_THREE (&mp_const[3])
85 #define MP_FOUR (&mp_const[4])
86 #define MP_FIVE (&mp_const[5])
87 #define MP_TEN (&mp_const[6])
88 #define MP_MONE (&mp_const[7])
90 #define MP_NEW ((mp *)0)
92 /*----- Memory allocation hooks -------------------------------------------*/
98 /* --- @MP_ARENA@ --- *
100 * This selects where memory is allocated from. Tweak to use more fancy
101 * things like custom arenas.
105 # define MP_ARENA MPARENA_GLOBAL
108 /* --- @MP_ALLOC@ --- *
110 * Arguments: @size_t sz@ = size required
112 * Returns: Pointer to an allocated vector of the requested size.
114 * Use: Hook for vector allocation.
118 # define MP_ALLOC(sz) mpalloc(MP_ARENA, (sz))
121 /* --- @MP_FREE@ --- *
123 * Arguments: @mpw *v@ = pointer to vector
127 * Use: Hook for vector deallocation.
131 # define MP_FREE(v) mpfree(MP_ARENA, (v))
134 /*----- Paranoia management -----------------------------------------------*/
136 /* --- @mp_burn@ --- *
138 * Arguments: @mp *m@ = pointer to a multiprecision integer
142 * Use: Marks the integer as `burn-after-use'. When the integer's
143 * memory is deallocated, it is deleted so that traces can't
144 * remain in the swap file. In theory.
147 extern void mp_burn(mp */
*m*/
);
149 /*----- Trivial macros ----------------------------------------------------*/
151 /* --- @MP_LEN@ --- *
153 * Arguments: @mp *m@ = pointer to a multiprecision integer
155 * Returns: Length of the integer, in words.
158 #define MP_LEN(m) ((m)->vl - ((m)->v))
160 /*----- Memory management and reference counting --------------------------*/
162 /* --- @mp_create@ --- *
164 * Arguments: @size_t sz@ = size of vector required
166 * Returns: Pointer to pristine new MP structure with enough memory
169 * Use: Creates a new multiprecision integer with indeterminate
170 * contents. The integer has a single reference.
173 extern mp
*mp_create(size_t /*sz*/);
175 /* --- @mp_build@ --- *
177 * Arguments: @mp *m@ = pointer to an MP block to fill in
178 * @mpw *v@ = pointer to a word array
179 * @mpw *vl@ = pointer just past end of array
183 * Use: Creates a multiprecision integer representing some smallish
184 * number. You must provide storage for the number and dispose
185 * of it when you've finished with it. The number is marked as
186 * constant while it exists.
189 extern void mp_build(mp */
*m*/
, mpw */
*v*/
, mpw */
*vl*/
);
191 /* --- @mp_destroy@ --- *
193 * Arguments: @mp *m@ = pointer to a multiprecision integer
197 * Use: Destroys a multiprecision integer. The reference count isn't
198 * checked. Don't use this function if you don't know what
199 * you're doing: use @mp_drop@ instead.
202 extern void mp_destroy(mp */
*m*/
);
204 /* --- @mp_copy@ --- *
206 * Arguments: @mp *m@ = pointer to a multiprecision integer
208 * Returns: A copy of the given multiprecision integer.
210 * Use: Copies the given integer. In fact you just get another
211 * reference to the same old one again.
214 extern mp
*mp_copy(mp */
*m*/
);
216 #define MP_COPY(m) ((m)->ref++, (m))
218 /* --- @mp_drop@ --- *
220 * Arguments: @mp *m@ = pointer to a multiprecision integer
224 * Use: Drops a reference to an integer which isn't wanted any more.
225 * If there are no more references, the integer is destroyed.
228 extern void mp_drop(mp */
*m*/
);
230 #define MP_DROP(m) do { \
234 else if (!(_mm->f & MP_CONST)) \
238 /* --- @mp_split@ --- *
240 * Arguments: @mp *m@ = pointer to a multiprecision integer
242 * Returns: A reference to the same integer, possibly with a different
245 * Use: Splits off a modifiable version of the integer referred to.
248 extern mp
*mp_split(mp */
*m*/
);
250 #define MP_SPLIT(m) do { \
252 if ((_mm->f & MP_CONST) || _mm->ref != 1) { \
253 mp *_dd = mp_create(_mm->sz); \
254 _dd->vl = _dd->v + MP_LEN(_mm); \
255 _dd->f = _mm->f & (MP_NEG | MP_BURN); \
256 memcpy(_dd->v, _mm->v, MPWS(MP_LEN(_mm))); \
263 /* --- @mp_resize@ --- *
265 * Arguments: @mp *m@ = pointer to a multiprecision integer
266 * @size_t sz@ = new size
270 * Use: Resizes the vector containing the integer's digits. The new
271 * size must be at least as large as the current integer's
272 * length. The integer's length is increased and new digits are
273 * filled with zeroes. This isn't really intended for client
277 extern void mp_resize(mp */
*m*/
, size_t /*sz*/);
279 #define MP_RESIZE(m, ssz) do { \
281 size_t _sz = (ssz); \
282 size_t _len = MP_LEN(_m); \
283 mpw *_v = MP_ALLOC(_sz); \
284 memcpy(_v, _m->v, MPWS(_len)); \
285 if (_m->f & MP_BURN) \
286 memset(_m->v, 0, MPWS(_m->sz)); \
289 _m->vl = _v + _len; \
293 /* --- @mp_ensure@ --- *
295 * Arguments: @mp *m@ = pointer to a multiprecision integer
296 * @size_t sz@ = required size
300 * Use: Ensures that the integer has enough space for @sz@ digits.
301 * The value is not changed.
304 extern void mp_ensure(mp */
*m*/
, size_t /*sz*/);
306 #define MP_ENSURE(m, ssz) do { \
308 size_t _ssz = (ssz); \
309 size_t _len = MP_LEN(_mm); \
310 if (_ssz > _mm->sz) \
311 MP_RESIZE(_mm, _ssz); \
312 if (!(_mm->f & MP_UNDEF) && _ssz > _len) { \
313 memset(_mm->vl, 0, MPWS(_ssz - _len)); \
314 _mm->vl = _mm->v + _ssz; \
318 /* --- @mp_modify@ --- *
320 * Arguments: @mp *m@ = pointer to a multiprecision integer
321 * @size_t sz@ = size required
323 * Returns: Pointer to the integer (possibly different).
325 * Use: Prepares an integer to be overwritten. It's split off from
326 * other references to the same integer, and sufficient space is
330 extern mp
*mp_modify(mp */
*m*/
, size_t /*sz*/);
332 #define MP_MODIFY(m, sz) do { \
336 _m = mp_create(_rq); \
339 MP_ENSURE(_m, _rq); \
341 _m->vl = _m->v + _rq; \
345 /*----- Size manipulation -------------------------------------------------*/
347 /* --- @mp_shrink@ --- *
349 * Arguments: @mp *m@ = pointer to a multiprecision integer
353 * Use: Reduces the recorded length of an integer. This doesn't
354 * reduce the amount of memory used, although it can improve
355 * performance a bit. To reduce memory, use @mp_minimize@
356 * instead. This can't change the value of an integer, and is
357 * therefore safe to use even when there are multiple
361 extern void mp_shrink(mp */
*m*/
);
363 #define MP_SHRINK(m) do { \
365 MPX_SHRINK(_mm->v, _mm->vl); \
370 /* --- @mp_minimize@ --- *
372 * Arguments: @mp *m@ = pointer to a multiprecision integer
376 * Use: Reduces the amount of memory an integer uses. It's best to
377 * do this to numbers which aren't going to change in the
381 extern void mp_minimize(mp */
*m*/
);
383 /*----- Bit scanning ------------------------------------------------------*/
389 /* --- @mp_scan@ --- *
391 * Arguments: @mpscan *sc@ = pointer to bitscanner block
392 * @const mp *m@ = pointer to a multiprecision integer
396 * Use: Initializes a bitscanner on a multiprecision integer.
399 extern void mp_scan(mpscan */
*sc*/
, const mp */
*m*/
);
401 #define MP_SCAN(sc, m) do { \
402 const mp *_mm = (m); \
403 mpscan *_sc = (sc); \
404 MPSCAN_INITX(_sc, _mm->v, _mm->vl); \
407 /* --- Other bitscanning aliases --- */
409 #define mp_step mpscan_step
410 #define mp_bit mpscan_bit
412 #define MP_STEP MPSCAN_STEP
413 #define MP_BIT MPSCAN_BIT
415 /*----- Loading and storing -----------------------------------------------*/
417 /* --- @mp_octets@ --- *
419 * Arguments: @const mp *m@ = a multiprecision integer
421 * Returns: The number of octets required to represent @m@.
423 * Use: Calculates the external storage required for a multiprecision
427 extern size_t mp_octets(const mp
*m
);
429 /* --- @mp_loadl@ --- *
431 * Arguments: @mp *d@ = destination
432 * @const void *pv@ = pointer to source data
433 * @size_t sz@ = size of the source data
435 * Returns: Resulting multiprecision number.
437 * Use: Loads a multiprecision number from an array of octets. The
438 * first byte in the array is the least significant. More
439 * formally, if the bytes are %$b_0, b_1, \ldots, b_{n-1}$%
440 * then the result is %$N = \sum_{0 \le i < n} b_i 2^{8i}$%.
443 extern mp
*mp_loadl(mp */
*d*/
, const void */
*pv*/
, size_t /*sz*/);
445 /* --- @mp_storel@ --- *
447 * Arguments: @const mp *m@ = source
448 * @void *pv@ = pointer to output array
449 * @size_t sz@ = size of the output array
453 * Use: Stores a multiprecision number in an array of octets. The
454 * first byte in the array is the least significant. If the
455 * array is too small to represent the number, high-order bits
456 * are truncated; if the array is too large, high order bytes
457 * are filled with zeros. More formally, if the number is
458 * %$N = \sum{0 \le i} b_i 2^{8i}$% where %$0 \le b_i < 256$%,
459 * then the array is %$b_0, b_1, \ldots, b_{n-1}$%.
462 extern void mp_storel(const mp */
*m*/
, void */
*pv*/
, size_t /*sz*/);
464 /* --- @mp_loadb@ --- *
466 * Arguments: @mp *d@ = destination
467 * @const void *pv@ = pointer to source data
468 * @size_t sz@ = size of the source data
470 * Returns: Resulting multiprecision number.
472 * Use: Loads a multiprecision number from an array of octets. The
473 * last byte in the array is the least significant. More
474 * formally, if the bytes are %$b_{n-1}, b_{n-2}, \ldots, b_0$%
475 * then the result is %$N = \sum_{0 \le i < n} b_i 2^{8i}$%.
478 extern mp
*mp_loadb(mp */
*d*/
, const void */
*pv*/
, size_t /*sz*/);
480 /* --- @mp_storeb@ --- *
482 * Arguments: @const mp *m@ = source
483 * @void *pv@ = pointer to output array
484 * @size_t sz@ = size of the output array
488 * Use: Stores a multiprecision number in an array of octets. The
489 * last byte in the array is the least significant. If the
490 * array is too small to represent the number, high-order bits
491 * are truncated; if the array is too large, high order bytes
492 * are filled with zeros. More formally, if the number is
493 * %$N = \sum{0 \le i} b_i 2^{8i}$% where %$0 \le b_i < 256$%,
494 * then the array is %$b_{n-1}, b_{n-2}, \ldots, b_0$%.
497 extern void mp_storeb(const mp */
*m*/
, void */
*pv*/
, size_t /*sz*/);
499 /*----- Simple arithmetic -------------------------------------------------*/
503 * Arguments: @mp *d@ = destination
506 * Returns: Result, @a@ converted to two's complement notation.
509 extern mp
*mp_2c(mp */
*d*/
, mp */
*a*/
);
513 * Arguments: @mp *d@ = destination
516 * Returns: Result, @a@ converted to the native signed-magnitude
520 extern mp
*mp_sm(mp */
*d*/
, mp */
*a*/
);
522 /* --- @mp_lsl@ --- *
524 * Arguments: @mp *d@ = destination
525 * @const mp *a@ = source
526 * @size_t n@ = number of bits to move
528 * Returns: Result, @a@ shifted left by @n@.
531 extern mp
*mp_lsl(mp */
*d*/
, const mp */
*a*/
, size_t /*n*/);
533 /* --- @mp_lsr@ --- *
535 * Arguments: @mp *d@ = destination
536 * @const mp *a@ = source
537 * @size_t n@ = number of bits to move
539 * Returns: Result, @a@ shifted left by @n@.
542 extern mp
*mp_lsr(mp */
*d*/
, const mp */
*a*/
, size_t /*n*/);
544 /* --- @mp_cmp@ --- *
546 * Arguments: @const mp *a, *b@ = two numbers
548 * Returns: Less than, equal to or greater than zero, according to
549 * whether @a@ is less than, equal to or greater than @b@.
552 extern int mp_cmp(const mp */
*a*/
, const mp */
*b*/
);
554 #define MP_CMP(a, op, b) (mp_cmp((a), (b)) op 0)
556 /* --- @mp_add@ --- *
558 * Arguments: @mp *d@ = destination
559 * @const mp *a, *b@ = sources
561 * Returns: Result, @a@ added to @b@.
564 extern mp
*mp_add(mp */
*d*/
, const mp */
*a*/
, const mp */
*b*/
);
566 /* --- @mp_sub@ --- *
568 * Arguments: @mp *d@ = destination
569 * @const mp *a, *b@ = sources
571 * Returns: Result, @b@ subtracted from @a@.
574 extern mp
*mp_sub(mp */
*d*/
, const mp */
*a*/
, const mp */
*b*/
);
576 /* --- @mp_mul@ --- *
578 * Arguments: @mp *d@ = destination
579 * @const mp *a, *b@ = sources
581 * Returns: Result, @a@ multiplied by @b@.
584 extern mp
*mp_mul(mp */
*d*/
, const mp */
*a*/
, const mp */
*b*/
);
586 /* --- @mp_sqr@ --- *
588 * Arguments: @mp *d@ = destination
589 * @const mp *a@ = source
591 * Returns: Result, @a@ squared.
594 extern mp
*mp_sqr(mp */
*d*/
, const mp */
*a*/
);
596 /* --- @mp_div@ --- *
598 * Arguments: @mp **qq, **rr@ = destination, quotient and remainder
599 * @const mp *a, *b@ = sources
601 * Use: Calculates the quotient and remainder when @a@ is divided by
605 extern void mp_div(mp
**/
*qq*/
, mp
**/
*rr*/
,
606 const mp */
*a*/
, const mp */
*b*/
);
608 /*----- More advanced algorithms ------------------------------------------*/
610 /* --- @mp_gcd@ --- *
612 * Arguments: @mp **gcd, **xx, **yy@ = where to write the results
613 * @mp *a, *b@ = sources (must be nonzero)
617 * Use: Calculates @gcd(a, b)@, and two numbers @x@ and @y@ such that
618 * @ax + by = gcd(a, b)@. This is useful for computing modular
619 * inverses. Neither @a@ nor @b@ may be zero. Note that,
620 * unlike @mp_div@ for example, it is not possible to specify
621 * explicit destinations -- new MPs are always allocated.
624 extern void mp_gcd(mp
**/
*gcd*/
, mp
**/
*xx*/
, mp
**/
*yy*/
,
625 mp */
*a*/
, mp */
*b*/
);
627 /*----- Test harness support ----------------------------------------------*/
629 #include <mLib/testrig.h>
635 extern const test_type type_mp
;
637 /*----- That's all, folks -------------------------------------------------*/