chiark - git - mdw - catacomb/blob - mp.h

   1 /* -*-c-*-
   2  *
   3  * $Id: mp.h,v 1.2 1999/11/17 18:02:16 mdw Exp $
   4  *
   5  * Simple multiprecision arithmetic
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  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.
  18  *
  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.
  23  *
  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,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: mp.h,v $
  33  * Revision 1.2  1999/11/17 18:02:16  mdw
  34  * New multiprecision integer arithmetic suite.
  35  *
  36  */
  37
  38 #ifndef MP_H
  39 #define MP_H
  40
  41 #ifdef __cplusplus
  42   extern "C" {
  43 #endif
  44
  45 /*----- Header files ------------------------------------------------------*/
  46
  47 #include <assert.h>
  48 #include <string.h>
  49
  50 #include <mLib/sub.h>
  51
  52 #ifndef MPW_H
  53 #  include "mpw.h"
  54 #endif
  55
  56 #ifndef MPX_H
  57 #  include "mpx.h"
  58 #endif
  59
  60 /*----- Data structures ---------------------------------------------------*/
  61
  62 typedef struct mp {
  63   mpw *v, *vl;
  64   size_t sz;
  65   unsigned f;
  66   unsigned ref;
  67 } mp;
  68
  69 #define MP_NEG 1u
  70 #define MP_BURN 2u
  71 #define MP_CONST 4u
  72 #define MP_UNDEF 8u
  73
  74 /*----- Useful constants --------------------------------------------------*/
  75
  76 extern mp mp_const[];
  77
  78 #define MP_ZERO  (&mp_const[0])
  79 #define MP_ONE   (&mp_const[1])
  80 #define MP_TWO   (&mp_const[2])
  81 #define MP_THREE (&mp_const[3])
  82 #define MP_FOUR  (&mp_const[4])
  83 #define MP_FIVE  (&mp_const[5])
  84 #define MP_TEN   (&mp_const[6])
  85 #define MP_MONE  (&mp_const[7])
  86
  87 #define MP_NEW ((mp *)0)
  88
  89 /*----- Memory allocation hooks -------------------------------------------*/
  90
  91 #ifndef MPARENA_H
  92 #  include "mparena.h"
  93 #endif
  94
  95 /* --- @MP_ARENA@ --- *
  96  *
  97  * This selects where memory is allocated from.  Tweak to use more fancy
  98  * things like custom arenas.
  99  */
 100
 101 #ifndef MP_ARENA
 102 #  define MP_ARENA MPARENA_GLOBAL
 103 #endif
 104
 105 /* --- @MP_ALLOC@ --- *
 106  *
 107  * Arguments:   @size_t sz@ = size required
 108  *
 109  * Returns:     Pointer to an allocated vector of the requested size.
 110  *
 111  * Use:         Hook for vector allocation.
 112  */
 113
 114 #ifndef MP_ALLOC
 115 #  define MP_ALLOC(sz) mpalloc(MP_ARENA, (sz))
 116 #endif
 117
 118 /* --- @MP_FREE@ --- *
 119  *
 120  * Arguments:   @mpw *v@ = pointer to vector
 121  *
 122  * Returns:     ---
 123  *
 124  * Use:         Hook for vector deallocation.
 125  */
 126
 127 #ifndef MP_FREE
 128 #  define MP_FREE(v) mpfree(MP_ARENA, (v))
 129 #endif
 130
 131 /*----- Paranoia management -----------------------------------------------*/
 132
 133 /* --- @mp_burn@ --- *
 134  *
 135  * Arguments:   @mp *m@ = pointer to a multiprecision integer
 136  *
 137  * Returns:     ---
 138  *
 139  * Use:         Marks the integer as `burn-after-use'.  When the integer's
 140  *              memory is deallocated, it is deleted so that traces can't
 141  *              remain in the swap file.  In theory.
 142  */
 143
 144 extern void mp_burn(mp */*m*/);
 145
 146 /*----- Trivial macros ----------------------------------------------------*/
 147
 148 /* --- @MP_LEN@ --- *
 149  *
 150  * Arguments:   @mp *m@ = pointer to a multiprecision integer
 151  *
 152  * Returns:     Length of the integer, in words.
 153  */
 154
 155 #define MP_LEN(m) ((m)->vl - ((m)->v))
 156
 157 /*----- Memory management and reference counting --------------------------*/
 158
 159 /* --- @mp_create@ --- *
 160  *
 161  * Arguments:   @size_t sz@ = size of vector required
 162  *
 163  * Returns:     Pointer to pristine new MP structure with enough memory
 164  *              bolted onto it.
 165  *
 166  * Use:         Creates a new multiprecision integer with indeterminate
 167  *              contents.  The integer has a single reference.
 168  */
 169
 170 extern mp *mp_create(size_t /*sz*/);
 171
 172 /* --- @mp_build@ --- *
 173  *
 174  * Arguments:   @mp *m@ = pointer to an MP block to fill in
 175  *              @mpw *v@ = pointer to a word array
 176  *              @mpw *vl@ = pointer just past end of array
 177  *
 178  * Returns:     ---
 179  *
 180  * Use:         Creates a multiprecision integer representing some smallish
 181  *              number.  You must provide storage for the number and dispose
 182  *              of it when you've finished with it.  The number is marked as
 183  *              constant while it exists.
 184  */
 185
 186 extern void mp_build(mp */*m*/, mpw */*v*/, mpw */*vl*/);
 187
 188 /* --- @mp_destroy@ --- *
 189  *
 190  * Arguments:   @mp *m@ = pointer to a multiprecision integer
 191  *
 192  * Returns:     ---
 193  *
 194  * Use:         Destroys a multiprecision integer. The reference count isn't
 195  *              checked.  Don't use this function if you don't know what
 196  *              you're doing: use @mp_drop@ instead.
 197  */
 198
 199 extern void mp_destroy(mp */*m*/);
 200
 201 /* --- @mp_copy@ --- *
 202  *
 203  * Arguments:   @mp *m@ = pointer to a multiprecision integer
 204  *
 205  * Returns:     A copy of the given multiprecision integer.
 206  *
 207  * Use:         Copies the given integer.  In fact you just get another
 208  *              reference to the same old one again.
 209  */
 210
 211 extern mp *mp_copy(mp */*m*/);
 212
 213 #define MP_COPY(m) ((m)->ref++, (m))
 214
 215 /* --- @mp_drop@ --- *
 216  *
 217  * Arguments:   @mp *m@ = pointer to a multiprecision integer
 218  *
 219  * Returns:     ---
 220  *
 221  * Use:         Drops a reference to an integer which isn't wanted any more.
 222  *              If there are no more references, the integer is destroyed.
 223  */
 224
 225 extern void mp_drop(mp */*m*/);
 226
 227 #define MP_DROP(m) do {                                                 \
 228   mp *_mm = (m);                                                        \
 229   if (_mm->ref > 1)                                                     \
 230     _mm->ref--;                                                         \
 231   else if (!(_mm->f & MP_CONST))                                        \
 232     mp_destroy(_mm);                                                    \
 233 } while (0)
 234
 235 /* --- @mp_split@ --- *
 236  *
 237  * Arguments:   @mp *m@ = pointer to a multiprecision integer
 238  *
 239  * Returns:     A reference to the same integer, possibly with a different
 240  *              address.
 241  *
 242  * Use:         Splits off a modifiable version of the integer referred to.
 243  */
 244
 245 extern mp *mp_split(mp */*m*/);
 246
 247 #define MP_SPLIT(m) do {                                                \
 248   mp *_mm = (m);                                                        \
 249   if ((_mm->f & MP_CONST) || _mm->ref != 1) {                           \
 250     mp *_dd = mp_create(_mm->sz);                                       \
 251     _dd->vl = _dd->v + MP_LEN(_mm);                                     \
 252     _dd->f = _mm->f & (MP_NEG | MP_BURN);                               \
 253     memcpy(_dd->v, _mm->v, MPWS(MP_LEN(_mm)));                          \
 254     _dd->ref = 1;                                                       \
 255     _mm->ref--;                                                         \
 256     (m) = _dd;                                                          \
 257   }                                                                     \
 258 } while (0)
 259
 260 /* --- @mp_resize@ --- *
 261  *
 262  * Arguments:   @mp *m@ = pointer to a multiprecision integer
 263  *              @size_t sz@ = new size
 264  *
 265  * Returns:     ---
 266  *
 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.  The integer's length is increased and new digits are
 270  *              filled with zeroes.  This isn't really intended for client
 271  *              use.
 272  */
 273
 274 extern void mp_resize(mp */*m*/, size_t /*sz*/);
 275
 276 #define MP_RESIZE(m, ssz) do {                                          \
 277   mp *_m = (m);                                                         \
 278   size_t _sz = (ssz);                                                   \
 279   size_t _len = MP_LEN(_m);                                             \
 280   mpw *_v = MP_ALLOC(_sz);                                              \
 281   memcpy(_v, _m->v, MPWS(_len));                                        \
 282   if (_m->f & MP_BURN)                                                  \
 283     memset(_m->v, 0, MPWS(_m->sz));                                     \
 284   MP_FREE(_m->v);                                                       \
 285   _m->v = _v;                                                           \
 286   _m->vl = _v + _len;                                                   \
 287   _m->sz = _sz;                                                         \
 288 } while (0)
 289
 290 /* --- @mp_ensure@ --- *
 291  *
 292  * Arguments:   @mp *m@ = pointer to a multiprecision integer
 293  *              @size_t sz@ = required size
 294  *
 295  * Returns:     ---
 296  *
 297  * Use:         Ensures that the integer has enough space for @sz@ digits.
 298  *              The value is not changed.
 299  */
 300
 301 extern void mp_ensure(mp */*m*/, size_t /*sz*/);
 302
 303 #define MP_ENSURE(m, ssz) do {                                          \
 304   mp *_mm = (m);                                                        \
 305   size_t _ssz = (ssz);                                                  \
 306   size_t _len = MP_LEN(_mm);                                            \
 307   if (_ssz > _mm->sz)                                                   \
 308     MP_RESIZE(_mm, _ssz);                                               \
 309   if (!(_mm->f & MP_UNDEF) && _ssz > _len) {                            \
 310     memset(_mm->vl, 0, MPWS(_ssz - _len));                              \
 311     _mm->vl = _mm->v + _ssz;                                            \
 312   }                                                                     \
 313 } while (0)
 314
 315 /* --- @mp_modify@ --- *
 316  *
 317  * Arguments:   @mp *m@ = pointer to a multiprecision integer
 318  *              @size_t sz@ = size required
 319  *
 320  * Returns:     Pointer to the integer (possibly different).
 321  *
 322  * Use:         Prepares an integer to be overwritten.  It's split off from
 323  *              other references to the same integer, and sufficient space is
 324  *              allocated.
 325  */
 326
 327 extern mp *mp_modify(mp */*m*/, size_t /*sz*/);
 328
 329 #define MP_MODIFY(m, sz) do {                                           \
 330   size_t _rq = (sz);                                                    \
 331   mp *_m = (m);                                                         \
 332   if (_m == MP_NEW)                                                     \
 333     _m = mp_create(_rq);                                                \
 334   else {                                                                \
 335     MP_SPLIT(_m);                                                       \
 336     MP_ENSURE(_m, _rq);                                                 \
 337   }                                                                     \
 338   _m->vl = _m->v + _rq;                                                 \
 339   (m) = _m;                                                             \
 340 } while (0)
 341
 342 /*----- Size manipulation -------------------------------------------------*/
 343
 344 /* --- @mp_shrink@ --- *
 345  *
 346  * Arguments:   @mp *m@ = pointer to a multiprecision integer
 347  *
 348  * Returns:     ---
 349  *
 350  * Use:         Reduces the recorded length of an integer.  This doesn't
 351  *              reduce the amount of memory used, although it can improve
 352  *              performance a bit.  To reduce memory, use @mp_minimize@
 353  *              instead.  This can't change the value of an integer, and is
 354  *              therefore safe to use even when there are multiple
 355  *              references.
 356  */
 357
 358 extern void mp_shrink(mp */*m*/);
 359
 360 #define MP_SHRINK(m) do {                                               \
 361   mp *_mm = (m);                                                        \
 362   MPX_SHRINK(_mm->v, _mm->vl);                                          \
 363   if (!MP_LEN(_mm))                                                     \
 364     _mm->f &= ~MP_NEG;                                                  \
 365 } while (0)
 366
 367 /* --- @mp_minimize@ --- *
 368  *
 369  * Arguments:   @mp *m@ = pointer to a multiprecision integer
 370  *
 371  * Returns:     ---
 372  *
 373  * Use:         Reduces the amount of memory an integer uses.  It's best to
 374  *              do this to numbers which aren't going to change in the
 375  *              future.
 376  */
 377
 378 extern void mp_minimize(mp */*m*/);
 379
 380 /*----- Bit scanning ------------------------------------------------------*/
 381
 382 #ifndef MPSCAN_H
 383 #  include "mpscan.h"
 384 #endif
 385
 386 /* --- @mp_scan@ --- *
 387  *
 388  * Arguments:   @mpscan *sc@ = pointer to bitscanner block
 389  *              @const mp *m@ = pointer to a multiprecision integer
 390  *
 391  * Returns:     ---
 392  *
 393  * Use:         Initializes a bitscanner on a multiprecision integer.
 394  */
 395
 396 extern void mp_scan(mpscan */*sc*/, const mp */*m*/);
 397
 398 #define MP_SCAN(sc, m) do {                                             \
 399   mp *_mm = (m);                                                        \
 400   mpscan *_sc = (sc);                                                   \
 401   MPSCAN_INITX(_sc, _mm->v, _mm->vl);                                   \
 402 } while (0)
 403
 404 /* --- Other bitscanning aliases --- */
 405
 406 #define mp_step mpscan_step
 407 #define mp_bit mpscan_bit
 408
 409 #define MP_STEP MPSCAN_STEP
 410 #define MP_BIT MPSCAN_BIT
 411
 412 /*----- Loading and storing -----------------------------------------------*/
 413
 414 /* --- @mp_octets@ --- *
 415  *
 416  * Arguments:   @const mp *m@ = a multiprecision integer
 417  *
 418  * Returns:     The number of octets required to represent @m@.
 419  *
 420  * Use:         Calculates the external storage required for a multiprecision
 421  *              integer.
 422  */
 423
 424 extern size_t mp_octets(const mp *m);
 425
 426 /* --- @mp_loadl@ --- *
 427  *
 428  * Arguments:   @mp *d@ = destination
 429  *              @const void *pv@ = pointer to source data
 430  *              @size_t sz@ = size of the source data
 431  *
 432  * Returns:     Resulting multiprecision number.
 433  *
 434  * Use:         Loads a multiprecision number from an array of octets.  The
 435  *              first byte in the array is the least significant.  More
 436  *              formally, if the bytes are %$b_0, b_1, \ldots, b_{n-1}$%
 437  *              then the result is %$N = \sum_{0 \le i < n} b_i 2^{8i}$%.
 438  */
 439
 440 extern mp *mp_loadl(mp */*d*/, const void */*pv*/, size_t /*sz*/);
 441
 442 /* --- @mp_storel@ --- *
 443  *
 444  * Arguments:   @const mp *m@ = source
 445  *              @void *pv@ = pointer to output array
 446  *              @size_t sz@ = size of the output array
 447  *
 448  * Returns:     ---
 449  *
 450  * Use:         Stores a multiprecision number in an array of octets.  The
 451  *              first byte in the array is the least significant.  If the
 452  *              array is too small to represent the number, high-order bits
 453  *              are truncated; if the array is too large, high order bytes
 454  *              are filled with zeros.  More formally, if the number is
 455  *              %$N = \sum{0 \le i} b_i 2^{8i}$% where %$0 \le b_i < 256$%,
 456  *              then the array is %$b_0, b_1, \ldots, b_{n-1}$%.
 457  */
 458
 459 extern void mp_storel(const mp */*m*/, void */*pv*/, size_t /*sz*/);
 460
 461 /* --- @mp_loadb@ --- *
 462  *
 463  * Arguments:   @mp *d@ = destination
 464  *              @const void *pv@ = pointer to source data
 465  *              @size_t sz@ = size of the source data
 466  *
 467  * Returns:     Resulting multiprecision number.
 468  *
 469  * Use:         Loads a multiprecision number from an array of octets.  The
 470  *              last byte in the array is the least significant.  More
 471  *              formally, if the bytes are %$b_{n-1}, b_{n-2}, \ldots, b_0$%
 472  *              then the result is %$N = \sum_{0 \le i < n} b_i 2^{8i}$%.
 473  */
 474
 475 extern mp *mp_loadb(mp */*d*/, const void */*pv*/, size_t /*sz*/);
 476
 477 /* --- @mp_storeb@ --- *
 478  *
 479  * Arguments:   @const mp *m@ = source
 480  *              @void *pv@ = pointer to output array
 481  *              @size_t sz@ = size of the output array
 482  *
 483  * Returns:     ---
 484  *
 485  * Use:         Stores a multiprecision number in an array of octets.  The
 486  *              last byte in the array is the least significant.  If the
 487  *              array is too small to represent the number, high-order bits
 488  *              are truncated; if the array is too large, high order bytes
 489  *              are filled with zeros.  More formally, if the number is
 490  *              %$N = \sum{0 \le i} b_i 2^{8i}$% where %$0 \le b_i < 256$%,
 491  *              then the array is %$b_{n-1}, b_{n-2}, \ldots, b_0$%.
 492  */
 493
 494 extern void mp_storeb(const mp */*m*/, void */*pv*/, size_t /*sz*/);
 495
 496 /*----- Simple arithmetic -------------------------------------------------*/
 497
 498 /* --- @mp_2c@ --- *
 499  *
 500  * Arguments:   @mp *d@ = destination
 501  *              @mp *a@ = source
 502  *
 503  * Returns:     Result, @a@ converted to two's complement notation.
 504  */
 505
 506 extern mp *mp_2c(mp */*d*/, mp */*a*/);
 507
 508 /* --- @mp_sm@ --- *
 509  *
 510  * Arguments:   @mp *d@ = destination
 511  *              @mp *a@ = source
 512  *
 513  * Returns:     Result, @a@ converted to the native signed-magnitude
 514  *              notation.
 515  */
 516
 517 extern mp *mp_sm(mp */*d*/, mp */*a*/);
 518
 519 /* --- @mp_lsl@ --- *
 520  *
 521  * Arguments:   @mp *d@ = destination
 522  *              @const mp *a@ = source
 523  *              @size_t n@ = number of bits to move
 524  *
 525  * Returns:     Result, @a@ shifted left by @n@.
 526  */
 527
 528 extern mp *mp_lsl(mp */*d*/, const mp */*a*/, size_t /*n*/);
 529
 530 /* --- @mp_lsr@ --- *
 531  *
 532  * Arguments:   @mp *d@ = destination
 533  *              @const mp *a@ = source
 534  *              @size_t n@ = number of bits to move
 535  *
 536  * Returns:     Result, @a@ shifted left by @n@.
 537  */
 538
 539 extern mp *mp_lsr(mp */*d*/, const mp */*a*/, size_t /*n*/);
 540
 541 /* --- @mp_cmp@ --- *
 542  *
 543  * Arguments:   @const mp *a, *b@ = two numbers
 544  *
 545  * Returns:     Less than, equal to or greater than zero, according to
 546  *              whether @a@ is less than, equal to or greater than @b@.
 547  */
 548
 549 extern int mp_cmp(const mp */*a*/, const mp */*b*/);
 550
 551 #define MP_CMP(a, op, b) (mp_cmp((a), (b)) op 0)
 552
 553 /* --- @mp_add@ --- *
 554  *
 555  * Arguments:   @mp *d@ = destination
 556  *              @const mp *a, *b@ = sources
 557  *
 558  * Returns:     Result, @a@ added to @b@.
 559  */
 560
 561 extern mp *mp_add(mp */*d*/, const mp */*a*/, const mp */*b*/);
 562
 563 /* --- @mp_sub@ --- *
 564  *
 565  * Arguments:   @mp *d@ = destination
 566  *              @const mp *a, *b@ = sources
 567  *
 568  * Returns:     Result, @b@ subtracted from @a@.
 569  */
 570
 571 extern mp *mp_sub(mp */*d*/, const mp */*a*/, const mp */*b*/);
 572
 573 /* --- @mp_mul@ --- *
 574  *
 575  * Arguments:   @mp *d@ = destination
 576  *              @const mp *a, *b@ = sources
 577  *
 578  * Returns:     Result, @a@ multiplied by @b@.
 579  */
 580
 581 extern mp *mp_mul(mp */*d*/, const mp */*a*/, const mp */*b*/);
 582
 583 /* --- @mp_sqr@ --- *
 584  *
 585  * Arguments:   @mp *d@ = destination
 586  *              @const mp *a@ = source
 587  *
 588  * Returns:     Result, @a@ squared.
 589  */
 590
 591 extern mp *mp_sqr(mp */*d*/, const mp */*a*/);
 592
 593 /* --- @mp_div@ --- *
 594  *
 595  * Arguments:   @mp **qq, **rr@ = destination, quotient and remainder
 596  *              @const mp *a, *b@ = sources
 597  *
 598  * Use:         Calculates the quotient and remainder when @a@ is divided by
 599  *              @b@.
 600  */
 601
 602 extern void mp_div(mp **/*qq*/, mp **/*rr*/,
 603                    const mp */*a*/, const mp */*b*/);
 604
 605 /*----- More advanced algorithms ------------------------------------------*/
 606
 607 /* --- @mp_gcd@ --- *
 608  *
 609  * Arguments:   @mp **gcd, **xx, **yy@ = where to write the results
 610  *              @mp *a, *b@ = sources (must be nonzero)
 611  *
 612  * Returns:     ---
 613  *
 614  * Use:         Calculates @gcd(a, b)@, and two numbers @x@ and @y@ such that
 615  *              @ax + by = gcd(a, b)@.  This is useful for computing modular
 616  *              inverses.  Neither @a@ nor @b@ may be zero.  Note that,
 617  *              unlike @mp_div@ for example, it is not possible to specify
 618  *              explicit destinations -- new MPs are always allocated.
 619  */
 620
 621 extern void mp_gcd(mp **/*gcd*/, mp **/*xx*/, mp **/*yy*/,
 622                    mp */*a*/, mp */*b*/);
 623
 624 /*----- Test harness support ----------------------------------------------*/
 625
 626 #include <mLib/testrig.h>
 627
 628 #ifndef MPTEXT_H
 629 #  include "mptext.h"
 630 #endif
 631
 632 extern const test_type type_mp;
 633
 634 /*----- That's all, folks -------------------------------------------------*/
 635
 636 #ifdef __cplusplus
 637   }
 638 #endif
 639
 640 #endif