chiark / gitweb /
genlimits: New program to generate useful limit MPs for C types.
[catacomb] / mp.h
CommitLineData
d03ab969 1/* -*-c-*-
2 *
a69a3efd 3 * $Id$
d03ab969 4 *
d3409d5e 5 * Simple multiprecision arithmetic
d03ab969 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
d9a8ae10 30#ifndef CATACOMB_MP_H
31#define CATACOMB_MP_H
d03ab969 32
33#ifdef __cplusplus
34 extern "C" {
35#endif
36
37/*----- Header files ------------------------------------------------------*/
38
d3409d5e 39#include <assert.h>
d03ab969 40#include <string.h>
41
d3409d5e 42#include <mLib/sub.h>
43
d9a8ae10 44#ifndef CATACOMB_MPW_H
d3409d5e 45# include "mpw.h"
d03ab969 46#endif
47
d34decd2 48#ifndef CATACOMB_ARENA_H
49# include "arena.h"
50#endif
51
52#ifndef CATACOMB_MPARENA_H
53# include "mparena.h"
54#endif
55
d9a8ae10 56#ifndef CATACOMB_MPX_H
d03ab969 57# include "mpx.h"
58#endif
59
d03ab969 60/*----- Data structures ---------------------------------------------------*/
61
3bc0a0fe 62/* --- A multiprecision integer --- */
63
d03ab969 64typedef struct mp {
3bc0a0fe 65 mpw *v, *vl; /* Vector of digits, current limit */
66 size_t sz; /* Size of digit buffer in words */
67 mparena *a; /* Arena for buffer allocation */
68 unsigned f; /* Flags (see below) */
69 unsigned ref; /* Reference counter */
d03ab969 70} mp;
71
3bc0a0fe 72#define MP_NEG 1u /* Negative (signed magnitude) */
73#define MP_BURN 2u /* Secret (viral flag) */
74#define MP_CONST 4u /* Uses strange memory allocation */
75#define MP_UNDEF 8u /* Contains nothing interesting */
76#define MP_DESTROYED 16u /* Has been destroyed */
77
78/* --- A factor for simultaneous exponentation --- *
79 *
80 * Used by the Montgomery and Barrett exponentiators.
81 */
82
83typedef struct mp_expfactor {
84 mp *base;
85 mp *exp;
86} mp_expfactor;
d03ab969 87
d3409d5e 88/*----- Useful constants --------------------------------------------------*/
d03ab969 89
d3409d5e 90extern mp mp_const[];
d03ab969 91
d3409d5e 92#define MP_ZERO (&mp_const[0])
93#define MP_ONE (&mp_const[1])
94#define MP_TWO (&mp_const[2])
95#define MP_THREE (&mp_const[3])
96#define MP_FOUR (&mp_const[4])
97#define MP_FIVE (&mp_const[5])
98#define MP_TEN (&mp_const[6])
d34decd2 99#define MP_256 (&mp_const[7])
100#define MP_MONE (&mp_const[8])
d03ab969 101
d3409d5e 102#define MP_NEW ((mp *)0)
d34decd2 103#define MP_NEWSEC (&mp_const[9])
d03ab969 104
d34decd2 105/*----- Trivial macros ----------------------------------------------------*/
d03ab969 106
d34decd2 107/* --- @MP_LEN@ --- *
d03ab969 108 *
d34decd2 109 * Arguments: @mp *m@ = pointer to a multiprecision integer
d03ab969 110 *
d34decd2 111 * Returns: Length of the integer, in words.
d03ab969 112 */
113
d34decd2 114#define MP_LEN(m) ((m)->vl - ((m)->v))
d03ab969 115
d34decd2 116/*----- Memory management and reference counting --------------------------*/
d3409d5e 117
d34decd2 118/* --- @mp_new@ --- *
d03ab969 119 *
d34decd2 120 * Arguments: @size_t sz@ = size of vector required
121 * @unsigned f@ = flags to set
d03ab969 122 *
d34decd2 123 * Returns: Pointer to a new MP structure.
d03ab969 124 *
d34decd2 125 * Use: Allocates a new multiprecision integer. The data space is
126 * allocated from either the standard global or secret arena,
127 * depending on the initial flags requested.
d03ab969 128 */
129
d34decd2 130extern mp *mp_new(size_t /*sz*/, unsigned /*f*/);
d03ab969 131
d34decd2 132/* --- @mp_create@ --- *
d03ab969 133 *
d34decd2 134 * Arguments: @size_t sz@ = size of vector required
d03ab969 135 *
d34decd2 136 * Returns: Pointer to pristine new MP structure with enough memory
137 * bolted onto it.
138 *
139 * Use: Creates a new multiprecision integer with indeterminate
140 * contents. The integer has a single reference.
d03ab969 141 */
142
d34decd2 143extern mp *mp_create(size_t /*sz*/);
d3409d5e 144
d34decd2 145/* --- @mp_createsecure@ --- *
d03ab969 146 *
d3409d5e 147 * Arguments: @size_t sz@ = size of vector required
d03ab969 148 *
d3409d5e 149 * Returns: Pointer to pristine new MP structure with enough memory
150 * bolted onto it.
d03ab969 151 *
d3409d5e 152 * Use: Creates a new multiprecision integer with indeterminate
d34decd2 153 * contents. The integer has a single reference. The integer's
154 * data space is allocated from the secure arena. Its burn flag
155 * is set.
d03ab969 156 */
157
d34decd2 158extern mp *mp_createsecure(size_t /*sz*/);
d03ab969 159
d3409d5e 160/* --- @mp_build@ --- *
d03ab969 161 *
d3409d5e 162 * Arguments: @mp *m@ = pointer to an MP block to fill in
163 * @mpw *v@ = pointer to a word array
164 * @mpw *vl@ = pointer just past end of array
d03ab969 165 *
166 * Returns: ---
167 *
d3409d5e 168 * Use: Creates a multiprecision integer representing some smallish
169 * number. You must provide storage for the number and dispose
170 * of it when you've finished with it. The number is marked as
171 * constant while it exists.
d03ab969 172 */
173
d3409d5e 174extern void mp_build(mp */*m*/, mpw */*v*/, mpw */*vl*/);
d03ab969 175
d3409d5e 176/* --- @mp_destroy@ --- *
d03ab969 177 *
d3409d5e 178 * Arguments: @mp *m@ = pointer to a multiprecision integer
d03ab969 179 *
180 * Returns: ---
181 *
d3409d5e 182 * Use: Destroys a multiprecision integer. The reference count isn't
183 * checked. Don't use this function if you don't know what
184 * you're doing: use @mp_drop@ instead.
d03ab969 185 */
186
d3409d5e 187extern void mp_destroy(mp */*m*/);
d03ab969 188
d3409d5e 189/* --- @mp_copy@ --- *
d03ab969 190 *
d3409d5e 191 * Arguments: @mp *m@ = pointer to a multiprecision integer
d03ab969 192 *
d3409d5e 193 * Returns: A copy of the given multiprecision integer.
194 *
195 * Use: Copies the given integer. In fact you just get another
196 * reference to the same old one again.
d03ab969 197 */
198
d3409d5e 199extern mp *mp_copy(mp */*m*/);
d03ab969 200
d3409d5e 201#define MP_COPY(m) ((m)->ref++, (m))
202
203/* --- @mp_drop@ --- *
d03ab969 204 *
d3409d5e 205 * Arguments: @mp *m@ = pointer to a multiprecision integer
d03ab969 206 *
207 * Returns: ---
208 *
d3409d5e 209 * Use: Drops a reference to an integer which isn't wanted any more.
210 * If there are no more references, the integer is destroyed.
d03ab969 211 */
212
d3409d5e 213extern void mp_drop(mp */*m*/);
d03ab969 214
d3409d5e 215#define MP_DROP(m) do { \
216 mp *_mm = (m); \
d34decd2 217 _mm->ref--; \
218 if (_mm->ref == 0 && !(_mm->f & MP_CONST)) \
d3409d5e 219 mp_destroy(_mm); \
220} while (0)
221
222/* --- @mp_split@ --- *
d03ab969 223 *
d3409d5e 224 * Arguments: @mp *m@ = pointer to a multiprecision integer
d03ab969 225 *
d3409d5e 226 * Returns: A reference to the same integer, possibly with a different
227 * address.
d03ab969 228 *
d3409d5e 229 * Use: Splits off a modifiable version of the integer referred to.
d03ab969 230 */
231
d3409d5e 232extern mp *mp_split(mp */*m*/);
233
234#define MP_SPLIT(m) do { \
d34decd2 235 mp *_m = (m); \
236 if ((_m->f & MP_CONST) || _m->ref > 1) { \
237 size_t _len = MP_LEN(_m); \
238 mp *_mm = mp_new(_len, _m->f); \
239 if (!(_m->f & MP_UNDEF)) \
240 memcpy(_mm->v, _m->v, MPWS(_len)); \
241 _m->ref--; \
242 _m = _mm; \
d3409d5e 243 } \
d34decd2 244 (m) = _m; \
d3409d5e 245} while (0)
d03ab969 246
d3409d5e 247/* --- @mp_resize@ --- *
d03ab969 248 *
d3409d5e 249 * Arguments: @mp *m@ = pointer to a multiprecision integer
250 * @size_t sz@ = new size
d03ab969 251 *
d3409d5e 252 * Returns: ---
d03ab969 253 *
d3409d5e 254 * Use: Resizes the vector containing the integer's digits. The new
255 * size must be at least as large as the current integer's
d34decd2 256 * length. This isn't really intended for client use.
d03ab969 257 */
258
d3409d5e 259extern void mp_resize(mp */*m*/, size_t /*sz*/);
260
261#define MP_RESIZE(m, ssz) do { \
262 mp *_m = (m); \
263 size_t _sz = (ssz); \
d34decd2 264 mparena *_a = (_m->f & MP_BURN) ? MPARENA_SECURE : MPARENA_GLOBAL; \
265 mpw *_v; \
d3409d5e 266 size_t _len = MP_LEN(_m); \
d34decd2 267 assert(((void)"can't make size less than length", _sz >= _len)); \
268 _v = mpalloc(_a, _sz); \
d9a8ae10 269 if (!(_m->f & MP_UNDEF)) \
270 memcpy(_v, _m->v, MPWS(_len)); \
d3409d5e 271 if (_m->f & MP_BURN) \
272 memset(_m->v, 0, MPWS(_m->sz)); \
d34decd2 273 mpfree(_m->a, _m->v); \
274 _m->a = _a; \
d3409d5e 275 _m->v = _v; \
276 _m->vl = _v + _len; \
d3409d5e 277} while (0)
d03ab969 278
d3409d5e 279/* --- @mp_ensure@ --- *
d03ab969 280 *
d3409d5e 281 * Arguments: @mp *m@ = pointer to a multiprecision integer
282 * @size_t sz@ = required size
d03ab969 283 *
284 * Returns: ---
285 *
d3409d5e 286 * Use: Ensures that the integer has enough space for @sz@ digits.
287 * The value is not changed.
d03ab969 288 */
289
d3409d5e 290extern void mp_ensure(mp */*m*/, size_t /*sz*/);
291
292#define MP_ENSURE(m, ssz) do { \
d34decd2 293 mp *_m = (m); \
d3409d5e 294 size_t _ssz = (ssz); \
d34decd2 295 size_t _len = MP_LEN(_m); \
296 if (_ssz >= _len) { \
297 if (_ssz > _m->sz) \
298 mp_resize(_m, _ssz); \
299 if (!(_m->f & MP_UNDEF) && _ssz > _len) \
300 memset(_m->vl, 0, MPWS(_ssz - _len)); \
301 _m->vl = _m->v + _ssz; \
302 } \
d3409d5e 303} while (0)
d03ab969 304
d34decd2 305/* --- @mp_dest@ --- *
d03ab969 306 *
d34decd2 307 * Arguments: @mp *m@ = a suggested destination integer
308 * @size_t sz@ = size required for result, in digits
309 * @unsigned f@ = various flags
310 *
311 * Returns: A pointer to an appropriate destination.
312 *
313 * Use: Converts a suggested destination into a real destination with
314 * the required properties. If the real destination is @d@,
315 * then the following properties will hold:
316 *
317 * * @d@ will have exactly one reference.
d03ab969 318 *
d34decd2 319 * * If @m@ is not @MP_NEW@, then the contents of @m@ will not
320 * change, unless @f@ has the @MP_UNDEF@ flag set.
d03ab969 321 *
d34decd2 322 * * If @m@ is not @MP_NEW@, then he reference count of @m@ on
323 * entry is equal to the sum of the counts of @d@ and @m@ on
324 * exit.
325 *
326 * * The size of @d@ will be at least @sz@.
327 *
328 * * If @f@ has the @MP_BURN@ flag set, then @d@ will be
329 * allocated from @MPARENA_SECURE@.
330 *
331 * Understanding this function is crucial to using Catacomb's
332 * multiprecision integer library effectively.
d03ab969 333 */
334
d34decd2 335extern mp *mp_dest(mp */*m*/, size_t /*sz*/, unsigned /*f*/);
d03ab969 336
d34decd2 337#define MP_DEST(m, ssz, f) do { \
d3409d5e 338 mp *_m = (m); \
d34decd2 339 size_t _ssz = (ssz); \
340 unsigned _f = (f); \
341 _m = mp_dest(_m, _ssz, _f); \
d3409d5e 342 (m) = _m; \
343} while (0)
344
345/*----- Size manipulation -------------------------------------------------*/
346
347/* --- @mp_shrink@ --- *
d03ab969 348 *
d3409d5e 349 * Arguments: @mp *m@ = pointer to a multiprecision integer
d03ab969 350 *
351 * Returns: ---
352 *
d3409d5e 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
358 * references.
d03ab969 359 */
360
d3409d5e 361extern void mp_shrink(mp */*m*/);
d03ab969 362
d3409d5e 363#define MP_SHRINK(m) do { \
364 mp *_mm = (m); \
365 MPX_SHRINK(_mm->v, _mm->vl); \
a69a3efd 366 if (MP_ZEROP(_mm)) \
d3409d5e 367 _mm->f &= ~MP_NEG; \
368} while (0)
369
370/* --- @mp_minimize@ --- *
d03ab969 371 *
d3409d5e 372 * Arguments: @mp *m@ = pointer to a multiprecision integer
d03ab969 373 *
374 * Returns: ---
375 *
d3409d5e 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
378 * future.
d03ab969 379 */
380
d3409d5e 381extern void mp_minimize(mp */*m*/);
d03ab969 382
d3409d5e 383/*----- Bit scanning ------------------------------------------------------*/
d03ab969 384
d9a8ae10 385#ifndef CATACOMB_MPSCAN_H
d3409d5e 386# include "mpscan.h"
387#endif
388
389/* --- @mp_scan@ --- *
d03ab969 390 *
d3409d5e 391 * Arguments: @mpscan *sc@ = pointer to bitscanner block
392 * @const mp *m@ = pointer to a multiprecision integer
d03ab969 393 *
394 * Returns: ---
395 *
d3409d5e 396 * Use: Initializes a bitscanner on a multiprecision integer.
d03ab969 397 */
398
d3409d5e 399extern void mp_scan(mpscan */*sc*/, const mp */*m*/);
400
401#define MP_SCAN(sc, m) do { \
a790733d 402 const mp *_mm = (m); \
d3409d5e 403 mpscan *_sc = (sc); \
404 MPSCAN_INITX(_sc, _mm->v, _mm->vl); \
405} while (0)
406
5fbe3846 407/* --- @mp_rscan@ --- *
408 *
409 * Arguments: @mpscan *sc@ = pointer to bitscanner block
410 * @const mp *m@ = pointer to a multiprecision integer
411 *
412 * Returns: ---
413 *
414 * Use: Initializes a reverse bitscanner on a multiprecision
415 * integer.
416 */
417
418extern void mp_rscan(mpscan */*sc*/, const mp */*m*/);
419
420#define MP_RSCAN(sc, m) do { \
421 const mp *_mm = (m); \
422 mpscan *_sc = (sc); \
423 MPSCAN_RINITX(_sc, _mm->v, _mm->vl); \
424} while (0)
425
d3409d5e 426/* --- Other bitscanning aliases --- */
427
428#define mp_step mpscan_step
429#define mp_bit mpscan_bit
5fbe3846 430#define mp_rstep mpscan_rstep
431#define mp_rbit mpscan_rbit
d3409d5e 432
433#define MP_STEP MPSCAN_STEP
434#define MP_BIT MPSCAN_BIT
5fbe3846 435#define MP_RSTEP MPSCAN_RSTEP
436#define MP_RBIT MPSCAN_RBIT
d3409d5e 437
438/*----- Loading and storing -----------------------------------------------*/
d03ab969 439
d3409d5e 440/* --- @mp_octets@ --- *
d03ab969 441 *
d3409d5e 442 * Arguments: @const mp *m@ = a multiprecision integer
d03ab969 443 *
d3409d5e 444 * Returns: The number of octets required to represent @m@.
d03ab969 445 *
d3409d5e 446 * Use: Calculates the external storage required for a multiprecision
447 * integer.
d03ab969 448 */
449
24e1e862 450extern size_t mp_octets(const mp */*m*/);
451
f09e814a 452/* --- @mp_octets2c@ --- *
453 *
454 * Arguments: @const mp *m@ = a multiprecision integer
455 *
456 * Returns: The number of octets required to represent @m@.
457 *
458 * Use: Calculates the external storage required for a multiprecision
459 * integer represented as two's complement.
460 */
461
462extern size_t mp_octets2c(const mp */*m*/);
463
24e1e862 464/* --- @mp_bits@ --- *
465 *
466 * Arguments: @const mp *m@ = a multiprecision integer
467 *
468 * Returns: The number of bits required to represent @m@.
469 *
470 * Use: Calculates the external storage required for a multiprecision
471 * integer.
472 */
473
474extern unsigned long mp_bits(const mp */*m*/);
d03ab969 475
d3409d5e 476/* --- @mp_loadl@ --- *
d03ab969 477 *
d3409d5e 478 * Arguments: @mp *d@ = destination
479 * @const void *pv@ = pointer to source data
480 * @size_t sz@ = size of the source data
d03ab969 481 *
d3409d5e 482 * Returns: Resulting multiprecision number.
d03ab969 483 *
d3409d5e 484 * Use: Loads a multiprecision number from an array of octets. The
485 * first byte in the array is the least significant. More
486 * formally, if the bytes are %$b_0, b_1, \ldots, b_{n-1}$%
487 * then the result is %$N = \sum_{0 \le i < n} b_i 2^{8i}$%.
d03ab969 488 */
489
d3409d5e 490extern mp *mp_loadl(mp */*d*/, const void */*pv*/, size_t /*sz*/);
d03ab969 491
d3409d5e 492/* --- @mp_storel@ --- *
493 *
494 * Arguments: @const mp *m@ = source
495 * @void *pv@ = pointer to output array
496 * @size_t sz@ = size of the output array
497 *
498 * Returns: ---
499 *
500 * Use: Stores a multiprecision number in an array of octets. The
501 * first byte in the array is the least significant. If the
502 * array is too small to represent the number, high-order bits
503 * are truncated; if the array is too large, high order bytes
504 * are filled with zeros. More formally, if the number is
505 * %$N = \sum{0 \le i} b_i 2^{8i}$% where %$0 \le b_i < 256$%,
506 * then the array is %$b_0, b_1, \ldots, b_{n-1}$%.
507 */
d03ab969 508
d3409d5e 509extern void mp_storel(const mp */*m*/, void */*pv*/, size_t /*sz*/);
d03ab969 510
d3409d5e 511/* --- @mp_loadb@ --- *
d03ab969 512 *
d3409d5e 513 * Arguments: @mp *d@ = destination
514 * @const void *pv@ = pointer to source data
515 * @size_t sz@ = size of the source data
d03ab969 516 *
d3409d5e 517 * Returns: Resulting multiprecision number.
d03ab969 518 *
d3409d5e 519 * Use: Loads a multiprecision number from an array of octets. The
520 * last byte in the array is the least significant. More
521 * formally, if the bytes are %$b_{n-1}, b_{n-2}, \ldots, b_0$%
522 * then the result is %$N = \sum_{0 \le i < n} b_i 2^{8i}$%.
d03ab969 523 */
524
d3409d5e 525extern mp *mp_loadb(mp */*d*/, const void */*pv*/, size_t /*sz*/);
d03ab969 526
d3409d5e 527/* --- @mp_storeb@ --- *
d03ab969 528 *
d3409d5e 529 * Arguments: @const mp *m@ = source
530 * @void *pv@ = pointer to output array
531 * @size_t sz@ = size of the output array
d03ab969 532 *
533 * Returns: ---
534 *
d3409d5e 535 * Use: Stores a multiprecision number in an array of octets. The
536 * last byte in the array is the least significant. If the
537 * array is too small to represent the number, high-order bits
538 * are truncated; if the array is too large, high order bytes
539 * are filled with zeros. More formally, if the number is
540 * %$N = \sum{0 \le i} b_i 2^{8i}$% where %$0 \le b_i < 256$%,
541 * then the array is %$b_{n-1}, b_{n-2}, \ldots, b_0$%.
d03ab969 542 */
543
d3409d5e 544extern void mp_storeb(const mp */*m*/, void */*pv*/, size_t /*sz*/);
d03ab969 545
f09e814a 546/* --- @mp_loadl2c@ --- *
d03ab969 547 *
d3409d5e 548 * Arguments: @mp *d@ = destination
f09e814a 549 * @const void *pv@ = pointer to source data
550 * @size_t sz@ = size of the source data
551 *
552 * Returns: Resulting multiprecision number.
d03ab969 553 *
f09e814a 554 * Use: Loads a multiprecision number from an array of octets as
555 * two's complement. The first byte in the array is the least
556 * significant.
d3409d5e 557 */
558
f09e814a 559extern mp *mp_loadl2c(mp */*d*/, const void */*pv*/, size_t /*sz*/);
d3409d5e 560
f09e814a 561/* --- @mp_storel2c@ --- *
562 *
563 * Arguments: @const mp *m@ = source
564 * @void *pv@ = pointer to output array
565 * @size_t sz@ = size of the output array
566 *
567 * Returns: ---
568 *
569 * Use: Stores a multiprecision number in an array of octets as two's
570 * complement. The first byte in the array is the least
571 * significant. If the array is too small to represent the
572 * number, high-order bits are truncated; if the array is too
573 * large, high order bytes are sign-extended.
574 */
575
576extern void mp_storel2c(const mp */*m*/, void */*pv*/, size_t /*sz*/);
577
578/* --- @mp_loadb2c@ --- *
d3409d5e 579 *
580 * Arguments: @mp *d@ = destination
f09e814a 581 * @const void *pv@ = pointer to source data
582 * @size_t sz@ = size of the source data
d03ab969 583 *
f09e814a 584 * Returns: Resulting multiprecision number.
585 *
586 * Use: Loads a multiprecision number from an array of octets as
587 * two's complement. The last byte in the array is the least
588 * significant.
d03ab969 589 */
590
f09e814a 591extern mp *mp_loadb2c(mp */*d*/, const void */*pv*/, size_t /*sz*/);
592
593/* --- @mp_storeb2c@ --- *
594 *
595 * Arguments: @const mp *m@ = source
596 * @void *pv@ = pointer to output array
597 * @size_t sz@ = size of the output array
598 *
599 * Returns: ---
600 *
601 * Use: Stores a multiprecision number in an array of octets, as
602 * two's complement. The last byte in the array is the least
603 * significant. If the array is too small to represent the
604 * number, high-order bits are truncated; if the array is too
605 * large, high order bytes are sign-extended.
606 */
607
608extern void mp_storeb2c(const mp */*m*/, void */*pv*/, size_t /*sz*/);
609
397041a9 610/*----- Bit operations ----------------------------------------------------*/
d03ab969 611
397041a9 612/* --- @mp_not@ --- *
d03ab969 613 *
d3409d5e 614 * Arguments: @mp *d@ = destination
d9a8ae10 615 * @mp *a@ = source
d03ab969 616 *
397041a9 617 * Returns: The bitwise complement of the source.
618 */
d3409d5e 619
397041a9 620extern mp *mp_not(mp */*d*/, mp */*a*/);
d3409d5e 621
397041a9 622/* --- @mp_bitop@ --- *
d3409d5e 623 *
624 * Arguments: @mp *d@ = destination
397041a9 625 * @mp *a, *b@ = sources
d03ab969 626 *
397041a9 627 * Returns: The result of the given bitwise operation. These functions
628 * don't handle negative numbers at all sensibly. For that, use
629 * the @...2c@ variants. The functions are named after the
630 * truth tables they generate:
631 *
632 * a: 0011
633 * b: 0101
634 * @mpx_bitXXXX@
d03ab969 635 */
636
397041a9 637#define MP_BITDECL(string) \
638 extern mp *mp_bit##string(mp */*d*/, mp */*a*/, mp */*b*/);
639MPX_DOBIN(MP_BITDECL)
f09e814a 640
397041a9 641/* --- @mp_[n]and@, @mp_[n]or@, @mp_[n]xor@, @mp_not@ --- *
f09e814a 642 *
397041a9 643 * Synonyms for the commonly-used functions.
f09e814a 644 */
645
397041a9 646#define mp_and mp_bit0001
647#define mp_or mp_bit0111
648#define mp_nand mp_bit1110
649#define mp_nor mp_bit1000
650#define mp_xor mp_bit0110
f09e814a 651
397041a9 652/* --- @mp_testbit@ --- *
f09e814a 653 *
654 * Arguments: @mp *x@ = a large integer
09d00c6b 655 * @unsigned long n@ = which bit to test
f09e814a 656 *
397041a9 657 * Returns: Nonzero if the bit is set, zero if not.
d3409d5e 658 */
659
397041a9 660extern int mp_testbit(mp */*x*/, unsigned long /*n*/);
d3409d5e 661
09d00c6b 662/* --- @mp_setbit@, @mp_clearbit@ --- *
663 *
664 * Arguments: @mp *d@ = a destination
665 * @mp *x@ = a large integer
666 * @unsigned long n@ = which bit to modify
667 *
668 * Returns: The argument @x@, with the appropriate bit set or cleared.
669 */
670
671extern mp *mp_setbit(mp */*d*/, mp */*x*/, unsigned long /*n*/);
672extern mp *mp_clearbit(mp */*d*/, mp */*x*/, unsigned long /*n*/);
673
81578196 674/* --- @mp_lsl@, @mp_lslc@, @mp_lsr@ --- *
0f32e0f8 675 *
676 * Arguments: @mp *d@ = destination
397041a9 677 * @mp *a@ = source
678 * @size_t n@ = number of bits to move
f09e814a 679 *
397041a9 680 * Returns: Result, @a@ shifted left or right by @n@.
81578196 681 *
682 * Use: Bitwise shift operators. @mp_lslc@ fills the bits introduced
683 * on the right with ones instead of zeroes: it's used
684 * internally by @mp_lsl2c@, though it may be useful on its
685 * own.
f09e814a 686 */
687
397041a9 688extern mp *mp_lsl(mp */*d*/, mp */*a*/, size_t /*n*/);
81578196 689extern mp *mp_lslc(mp */*d*/, mp */*a*/, size_t /*n*/);
397041a9 690extern mp *mp_lsr(mp */*d*/, mp */*a*/, size_t /*n*/);
f09e814a 691
397041a9 692/* --- @mp_not2c@ --- *
f09e814a 693 *
694 * Arguments: @mp *d@ = destination
695 * @mp *a@ = source
696 *
397041a9 697 * Returns: The sign-extended complement of the argument.
698 */
f09e814a 699
397041a9 700extern mp *mp_not2c(mp */*d*/, mp */*a*/);
0f32e0f8 701
f09e814a 702/* --- @mp_bitop2c@ --- *
703 *
704 * Arguments: @mp *d@ = destination
705 * @mp *a, *b@ = sources
706 *
707 * Returns: The result of the given bitwise operation. Negative numbers
708 * are treated as two's complement, sign-extended infinitely to
709 * the left. The functions are named after the truth tables
710 * they generate:
711 *
712 * a: 0011
713 * b: 0101
714 * @mpx_bitXXXX@
715 */
716
717#define MP_BIT2CDECL(string) \
718 extern mp *mp_bit##string##2c(mp */*d*/, mp */*a*/, mp */*b*/);
719MPX_DOBIN(MP_BIT2CDECL)
720
721/* --- @mp_[n]and@, @mp_[n]or@, @mp_[n]xor@, @mp_not@ --- *
722 *
723 * Synonyms for the commonly-used functions.
724 */
725
726#define mp_and2c mp_bit00012c
727#define mp_or2c mp_bit01112c
728#define mp_nand2c mp_bit11102c
729#define mp_nor2c mp_bit10002c
730#define mp_xor2c mp_bit01102c
731
397041a9 732/* --- @mp_lsl2c@, @mp_lsr2c@ --- *
f09e814a 733 *
734 * Arguments: @mp *d@ = destination
735 * @mp *a@ = source
397041a9 736 * @size_t n@ = number of bits to move
f09e814a 737 *
397041a9 738 * Returns: Result, @a@ shifted left or right by @n@. Handles the
739 * pretence of sign-extension for negative numbers.
f09e814a 740 */
741
397041a9 742extern mp *mp_lsl2c(mp */*d*/, mp */*a*/, size_t /*n*/);
743extern mp *mp_lsr2c(mp */*d*/, mp */*a*/, size_t /*n*/);
744
745/* --- @mp_testbit2c@ --- *
746 *
747 * Arguments: @mp *x@ = a large integer
748 * @unsigned long n@ = which bit to test
749 *
750 * Returns: Nonzero if the bit is set, zero if not. Fakes up two's
751 * complement representation.
752 */
753
754extern int mp_testbit2c(mp */*x*/, unsigned long /*n*/);
755
756/* --- @mp_setbit2c@, @mp_clearbit2c@ --- *
757 *
758 * Arguments: @mp *d@ = a destination
759 * @mp *x@ = a large integer
760 * @unsigned long n@ = which bit to modify
761 *
762 * Returns: The argument @x@, with the appropriate bit set or cleared.
763 * Fakes up two's complement representation.
764 */
765
766extern mp *mp_setbit2c(mp */*d*/, mp */*x*/, unsigned long /*n*/);
767extern mp *mp_clearbit2c(mp */*d*/, mp */*x*/, unsigned long /*n*/);
768
769/*----- Comparisons -------------------------------------------------------*/
770
771/* --- @mp_eq@ --- *
772 *
773 * Arguments: @const mp *a, *b@ = two numbers
774 *
775 * Returns: Nonzero if the numbers are equal.
776 */
777
778extern int mp_eq(const mp */*a*/, const mp */*b*/);
779
780#define MP_EQ(a, b) \
781 ((((a)->f ^ (b)->f) & MP_NEG) == 0 && \
782 mpx_ueq((a)->v, (a)->vl, (b)->v, (b)->vl))
783
784/* --- @mp_cmp@ --- *
785 *
786 * Arguments: @const mp *a, *b@ = two numbers
787 *
788 * Returns: Less than, equal to or greater than zero, according to
789 * whether @a@ is less than, equal to or greater than @b@.
790 */
791
792extern int mp_cmp(const mp */*a*/, const mp */*b*/);
793
794#define MP_CMP(a, op, b) (mp_cmp((a), (b)) op 0)
795
3cd24abb 796/* --- Other handy macros --- */
797
a69a3efd 798#define MP_NEGP(x) ((x)->f & MP_NEG)
799#define MP_ZEROP(x) (!MP_LEN(x))
800#define MP_POSP(x) (!MP_NEGP(x) && !MP_ZEROP(x))
801#define MP_ODDP(x) (!MP_ZEROP(x) && ((x)->v[0] & 1u))
802#define MP_EVENP(x) (!MP_ODDP(x))
3cd24abb 803
397041a9 804/*----- Arithmetic operations ---------------------------------------------*/
805
806/* --- @mp_neg@ --- *
807 *
808 * Arguments: @mp *d@ = destination
809 * @mp *a@ = argument
810 *
811 * Returns: The negation of the argument.
812 *
813 * Use: Negates its argument.
814 */
815
816extern mp *mp_neg(mp */*d*/, mp */*a*/);
f09e814a 817
d3409d5e 818/* --- @mp_add@ --- *
d03ab969 819 *
d3409d5e 820 * Arguments: @mp *d@ = destination
d9a8ae10 821 * @mp *a, *b@ = sources
d3409d5e 822 *
823 * Returns: Result, @a@ added to @b@.
d03ab969 824 */
825
d9a8ae10 826extern mp *mp_add(mp */*d*/, mp */*a*/, mp */*b*/);
d03ab969 827
d3409d5e 828/* --- @mp_sub@ --- *
829 *
830 * Arguments: @mp *d@ = destination
d9a8ae10 831 * @mp *a, *b@ = sources
d3409d5e 832 *
833 * Returns: Result, @b@ subtracted from @a@.
834 */
d03ab969 835
d9a8ae10 836extern mp *mp_sub(mp */*d*/, mp */*a*/, mp */*b*/);
d3409d5e 837
838/* --- @mp_mul@ --- *
d03ab969 839 *
d3409d5e 840 * Arguments: @mp *d@ = destination
d9a8ae10 841 * @mp *a, *b@ = sources
d03ab969 842 *
d3409d5e 843 * Returns: Result, @a@ multiplied by @b@.
844 */
845
d9a8ae10 846extern mp *mp_mul(mp */*d*/, mp */*a*/, mp */*b*/);
d3409d5e 847
848/* --- @mp_sqr@ --- *
849 *
850 * Arguments: @mp *d@ = destination
d9a8ae10 851 * @mp *a@ = source
d3409d5e 852 *
853 * Returns: Result, @a@ squared.
854 */
855
d9a8ae10 856extern mp *mp_sqr(mp */*d*/, mp */*a*/);
d3409d5e 857
858/* --- @mp_div@ --- *
d03ab969 859 *
d3409d5e 860 * Arguments: @mp **qq, **rr@ = destination, quotient and remainder
d9a8ae10 861 * @mp *a, *b@ = sources
d3409d5e 862 *
863 * Use: Calculates the quotient and remainder when @a@ is divided by
864 * @b@.
d03ab969 865 */
866
d9a8ae10 867extern void mp_div(mp **/*qq*/, mp **/*rr*/, mp */*a*/, mp */*b*/);
d3409d5e 868
f4535c64 869/* --- @mp_exp@ --- *
870 *
871 * Arguments: @mp *d@ = fake destination
872 * @mp *a@ = base
873 * @mp *e@ = exponent
874 *
875 * Returns: Result, %$a^e$%.
876 */
877
878extern mp *mp_exp(mp */*d*/, mp */*a*/, mp */*e*/);
879
22a073c0 880/* --- @mp_odd@ --- *
881 *
882 * Arguments: @mp *d@ = pointer to destination integer
883 * @mp *m@ = pointer to source integer
884 * @size_t *s@ = where to store the power of 2
885 *
886 * Returns: An odd integer integer %$t$% such that %$m = 2^s t$%.
887 *
888 * Use: Computes a power of two and an odd integer which, when
889 * multiplied, give a specified result. This sort of thing is
890 * useful in number theory quite often.
891 */
892
893extern mp *mp_odd(mp */*d*/, mp */*m*/, size_t */*s*/);
894
d3409d5e 895/*----- More advanced algorithms ------------------------------------------*/
d03ab969 896
22a073c0 897/* --- @mp_sqrt@ --- *
898 *
899 * Arguments: @mp *d@ = pointer to destination integer
900 * @mp *a@ = (nonnegative) integer to take square root of
901 *
902 * Returns: The largest integer %$x$% such that %$x^2 \le a$%.
903 *
904 * Use: Computes integer square roots.
905 *
906 * The current implementation isn't very good: it uses the
907 * Newton-Raphson method to find an approximation to %$a$%. If
908 * there's any demand for a better version, I'll write one.
909 */
910
911extern mp *mp_sqrt(mp */*d*/, mp */*a*/);
912
d3409d5e 913/* --- @mp_gcd@ --- *
d03ab969 914 *
d3409d5e 915 * Arguments: @mp **gcd, **xx, **yy@ = where to write the results
916 * @mp *a, *b@ = sources (must be nonzero)
d03ab969 917 *
918 * Returns: ---
919 *
d3409d5e 920 * Use: Calculates @gcd(a, b)@, and two numbers @x@ and @y@ such that
921 * @ax + by = gcd(a, b)@. This is useful for computing modular
d9a8ae10 922 * inverses. Neither @a@ nor @b@ may be zero.
d03ab969 923 */
924
d3409d5e 925extern void mp_gcd(mp **/*gcd*/, mp **/*xx*/, mp **/*yy*/,
926 mp */*a*/, mp */*b*/);
927
b817bfc6 928/* -- @mp_modinv@ --- *
929 *
930 * Arguments: @mp *d@ = destination
931 * @mp *x@ = argument
932 * @mp *p@ = modulus
933 *
934 * Returns: The inverse %$x^{-1} \bmod p$%.
935 *
936 * Use: Computes a modular inverse. An assertion fails if %$p$%
937 * has no inverse.
938 */
939
940extern mp *mp_modinv(mp */*d*/, mp */*x*/, mp */*p*/);
941
5b00a0ea 942/* --- @mp_jacobi@ --- *
943 *
944 * Arguments: @mp *a@ = an integer less than @n@
945 * @mp *n@ = an odd integer
946 *
947 * Returns: @-1@, @0@ or @1@ -- the Jacobi symbol %$J(a, n)$%.
948 *
949 * Use: Computes the Jacobi symbol. If @n@ is prime, this is the
950 * Legendre symbol and is equal to 1 if and only if @a@ is a
951 * quadratic residue mod @n@. The result is zero if and only if
952 * @a@ and @n@ have a common factor greater than one.
953 */
954
22a073c0 955extern int mp_jacobi(mp */*a*/, mp */*n*/);
956
957/* --- @mp_modsqrt@ --- *
958 *
959 * Arguments: @mp *d@ = destination integer
960 * @mp *a@ = source integer
961 * @mp *p@ = modulus (must be prime)
962 *
963 * Returns: If %$a$% is a quadratic residue, a square root of %$a$%; else
964 * a null pointer.
965 *
966 * Use: Returns an integer %$x$% such that %$x^2 \equiv a \pmod{p}$%,
967 * if one exists; else a null pointer. This function will not
968 * work if %$p$% is composite: you must factor the modulus, take
969 * a square root mod each factor, and recombine the results
970 * using the Chinese Remainder Theorem.
222c8a43
MW
971 *
972 * We guarantee that the square root returned is the smallest
973 * one (i.e., the `positive' square root).
22a073c0 974 */
975
976extern mp *mp_modsqrt(mp */*d*/, mp */*a*/, mp */*p*/);
5b00a0ea 977
d3409d5e 978/*----- Test harness support ----------------------------------------------*/
979
980#include <mLib/testrig.h>
981
d9a8ae10 982#ifndef CATACOMB_MPTEXT_H
d3409d5e 983# include "mptext.h"
984#endif
985
986extern const test_type type_mp;
d03ab969 987
988/*----- That's all, folks -------------------------------------------------*/
989
990#ifdef __cplusplus
991 }
992#endif
993
994#endif