chiark / gitweb /
Merge branch '2.4.x' into 2.5.x
[catacomb] / math / mp.h
CommitLineData
d03ab969 1/* -*-c-*-
d03ab969 2 *
d3409d5e 3 * Simple multiprecision arithmetic
d03ab969 4 *
5 * (c) 1999 Straylight/Edgeware
6 */
7
45c0fd36 8/*----- Licensing notice --------------------------------------------------*
d03ab969 9 *
10 * This file is part of Catacomb.
11 *
12 * Catacomb is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
45c0fd36 16 *
d03ab969 17 * Catacomb is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
45c0fd36 21 *
d03ab969 22 * You should have received a copy of the GNU Library General Public
23 * License along with Catacomb; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
25 * MA 02111-1307, USA.
26 */
27
d9a8ae10 28#ifndef CATACOMB_MP_H
29#define CATACOMB_MP_H
d03ab969 30
31#ifdef __cplusplus
32 extern "C" {
33#endif
34
35/*----- Header files ------------------------------------------------------*/
36
d3409d5e 37#include <assert.h>
d03ab969 38#include <string.h>
39
a6d8eb54 40#include <mLib/macros.h>
d3409d5e 41#include <mLib/sub.h>
42
d9a8ae10 43#ifndef CATACOMB_MPW_H
d3409d5e 44# include "mpw.h"
d03ab969 45#endif
46
d34decd2 47#ifndef CATACOMB_ARENA_H
48# include "arena.h"
49#endif
50
51#ifndef CATACOMB_MPARENA_H
52# include "mparena.h"
53#endif
54
d9a8ae10 55#ifndef CATACOMB_MPX_H
d03ab969 56# include "mpx.h"
57#endif
58
d03ab969 59/*----- Data structures ---------------------------------------------------*/
60
3bc0a0fe 61/* --- A multiprecision integer --- */
62
d03ab969 63typedef struct mp {
3bc0a0fe 64 mpw *v, *vl; /* Vector of digits, current limit */
65 size_t sz; /* Size of digit buffer in words */
66 mparena *a; /* Arena for buffer allocation */
67 unsigned f; /* Flags (see below) */
68 unsigned ref; /* Reference counter */
d03ab969 69} mp;
70
3bc0a0fe 71#define MP_NEG 1u /* Negative (signed magnitude) */
72#define MP_BURN 2u /* Secret (viral flag) */
73#define MP_CONST 4u /* Uses strange memory allocation */
74#define MP_UNDEF 8u /* Contains nothing interesting */
75#define MP_DESTROYED 16u /* Has been destroyed */
76
77/* --- A factor for simultaneous exponentation --- *
78 *
79 * Used by the Montgomery and Barrett exponentiators.
80 */
81
82typedef struct mp_expfactor {
83 mp *base;
84 mp *exp;
85} mp_expfactor;
d03ab969 86
d3409d5e 87/*----- Useful constants --------------------------------------------------*/
d03ab969 88
d3409d5e 89extern mp mp_const[];
d03ab969 90
d3409d5e 91#define MP_ZERO (&mp_const[0])
45c0fd36
MW
92#define MP_ONE (&mp_const[1])
93#define MP_TWO (&mp_const[2])
d3409d5e 94#define MP_THREE (&mp_const[3])
45c0fd36
MW
95#define MP_FOUR (&mp_const[4])
96#define MP_FIVE (&mp_const[5])
97#define MP_TEN (&mp_const[6])
d34decd2 98#define MP_256 (&mp_const[7])
45c0fd36 99#define MP_MONE (&mp_const[8])
d03ab969 100
d3409d5e 101#define MP_NEW ((mp *)0)
d34decd2 102#define MP_NEWSEC (&mp_const[9])
d03ab969 103
d34decd2 104/*----- Trivial macros ----------------------------------------------------*/
d03ab969 105
d34decd2 106/* --- @MP_LEN@ --- *
d03ab969 107 *
d34decd2 108 * Arguments: @mp *m@ = pointer to a multiprecision integer
d03ab969 109 *
d34decd2 110 * Returns: Length of the integer, in words.
d03ab969 111 */
112
d34decd2 113#define MP_LEN(m) ((m)->vl - ((m)->v))
d03ab969 114
d34decd2 115/*----- Memory management and reference counting --------------------------*/
d3409d5e 116
d34decd2 117/* --- @mp_new@ --- *
d03ab969 118 *
d34decd2 119 * Arguments: @size_t sz@ = size of vector required
120 * @unsigned f@ = flags to set
d03ab969 121 *
d34decd2 122 * Returns: Pointer to a new MP structure.
d03ab969 123 *
d34decd2 124 * Use: Allocates a new multiprecision integer. The data space is
125 * allocated from either the standard global or secret arena,
126 * depending on the initial flags requested.
d03ab969 127 */
128
d34decd2 129extern mp *mp_new(size_t /*sz*/, unsigned /*f*/);
d03ab969 130
d34decd2 131/* --- @mp_create@ --- *
d03ab969 132 *
d34decd2 133 * Arguments: @size_t sz@ = size of vector required
d03ab969 134 *
d34decd2 135 * Returns: Pointer to pristine new MP structure with enough memory
136 * bolted onto it.
137 *
138 * Use: Creates a new multiprecision integer with indeterminate
139 * contents. The integer has a single reference.
d03ab969 140 */
141
d34decd2 142extern mp *mp_create(size_t /*sz*/);
d3409d5e 143
d34decd2 144/* --- @mp_createsecure@ --- *
d03ab969 145 *
d3409d5e 146 * Arguments: @size_t sz@ = size of vector required
d03ab969 147 *
d3409d5e 148 * Returns: Pointer to pristine new MP structure with enough memory
149 * bolted onto it.
d03ab969 150 *
d3409d5e 151 * Use: Creates a new multiprecision integer with indeterminate
d34decd2 152 * contents. The integer has a single reference. The integer's
153 * data space is allocated from the secure arena. Its burn flag
154 * is set.
d03ab969 155 */
156
d34decd2 157extern mp *mp_createsecure(size_t /*sz*/);
d03ab969 158
d3409d5e 159/* --- @mp_build@ --- *
d03ab969 160 *
d3409d5e 161 * Arguments: @mp *m@ = pointer to an MP block to fill in
162 * @mpw *v@ = pointer to a word array
163 * @mpw *vl@ = pointer just past end of array
d03ab969 164 *
165 * Returns: ---
166 *
d3409d5e 167 * Use: Creates a multiprecision integer representing some smallish
168 * number. You must provide storage for the number and dispose
169 * of it when you've finished with it. The number is marked as
170 * constant while it exists.
d03ab969 171 */
172
d3409d5e 173extern void mp_build(mp */*m*/, mpw */*v*/, mpw */*vl*/);
d03ab969 174
d3409d5e 175/* --- @mp_destroy@ --- *
d03ab969 176 *
d3409d5e 177 * Arguments: @mp *m@ = pointer to a multiprecision integer
d03ab969 178 *
179 * Returns: ---
180 *
d3409d5e 181 * Use: Destroys a multiprecision integer. The reference count isn't
182 * checked. Don't use this function if you don't know what
183 * you're doing: use @mp_drop@ instead.
d03ab969 184 */
185
d3409d5e 186extern void mp_destroy(mp */*m*/);
d03ab969 187
d3409d5e 188/* --- @mp_copy@ --- *
d03ab969 189 *
d3409d5e 190 * Arguments: @mp *m@ = pointer to a multiprecision integer
d03ab969 191 *
d3409d5e 192 * Returns: A copy of the given multiprecision integer.
193 *
194 * Use: Copies the given integer. In fact you just get another
195 * reference to the same old one again.
d03ab969 196 */
197
d3409d5e 198extern mp *mp_copy(mp */*m*/);
d03ab969 199
a6d8eb54
MW
200#define MP_COPY(m) MUFFLE_WARNINGS_EXPR(GCC_WARNING("-Wunused-value"), \
201 ((m)->ref++, (m)))
d3409d5e 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)
45c0fd36 221
d3409d5e 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.
45c0fd36 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
45c0fd36
MW
646#define mp_and mp_bit0001
647#define mp_or mp_bit0111
397041a9 648#define mp_nand mp_bit1110
45c0fd36
MW
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
45c0fd36 727#define mp_or2c mp_bit01112c
f09e814a 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
0c4f06c0
MW
895/* --- @mp_leastcongruent@ --- *
896 *
897 * Arguments: @mp *d@ = pointer to destination
898 * @mp *b@ = lower bound
899 * @mp *r@ = representative
900 * @mp *m@ = modulus
901 *
902 * Returns: The smallest integer %$x \equiv r \pmod{m}$% such that
903 * %$x \ge b$%.
904 */
905
906extern mp *mp_leastcongruent(mp */*d*/, mp */*b*/, mp */*r*/, mp */*m*/);
907
d3409d5e 908/*----- More advanced algorithms ------------------------------------------*/
d03ab969 909
22a073c0 910/* --- @mp_sqrt@ --- *
911 *
912 * Arguments: @mp *d@ = pointer to destination integer
913 * @mp *a@ = (nonnegative) integer to take square root of
914 *
915 * Returns: The largest integer %$x$% such that %$x^2 \le a$%.
916 *
917 * Use: Computes integer square roots.
918 *
919 * The current implementation isn't very good: it uses the
920 * Newton-Raphson method to find an approximation to %$a$%. If
921 * there's any demand for a better version, I'll write one.
922 */
923
924extern mp *mp_sqrt(mp */*d*/, mp */*a*/);
925
d3409d5e 926/* --- @mp_gcd@ --- *
d03ab969 927 *
d3409d5e 928 * Arguments: @mp **gcd, **xx, **yy@ = where to write the results
929 * @mp *a, *b@ = sources (must be nonzero)
d03ab969 930 *
931 * Returns: ---
932 *
d3409d5e 933 * Use: Calculates @gcd(a, b)@, and two numbers @x@ and @y@ such that
934 * @ax + by = gcd(a, b)@. This is useful for computing modular
d9a8ae10 935 * inverses. Neither @a@ nor @b@ may be zero.
d03ab969 936 */
937
d3409d5e 938extern void mp_gcd(mp **/*gcd*/, mp **/*xx*/, mp **/*yy*/,
939 mp */*a*/, mp */*b*/);
940
b817bfc6 941/* -- @mp_modinv@ --- *
942 *
943 * Arguments: @mp *d@ = destination
944 * @mp *x@ = argument
945 * @mp *p@ = modulus
946 *
947 * Returns: The inverse %$x^{-1} \bmod p$%.
948 *
949 * Use: Computes a modular inverse. An assertion fails if %$p$%
950 * has no inverse.
951 */
952
953extern mp *mp_modinv(mp */*d*/, mp */*x*/, mp */*p*/);
954
5b00a0ea 955/* --- @mp_jacobi@ --- *
956 *
6791ed17
MW
957 * Arguments: @mp *a@ = an integer
958 * @mp *n@ = another integer
5b00a0ea 959 *
960 * Returns: @-1@, @0@ or @1@ -- the Jacobi symbol %$J(a, n)$%.
961 *
6791ed17
MW
962 * Use: Computes the Kronecker symbol %$\jacobi{a}{n}$%. If @n@ is
963 * prime, this is the Legendre symbol and is equal to 1 if and
964 * only if @a@ is a quadratic residue mod @n@. The result is
965 * zero if and only if @a@ and @n@ have a common factor greater
966 * than one.
967 *
968 * If @n@ is composite, then this computes the Kronecker symbol
969 *
970 * %$\jacobi{a}{n}=\jacobi{a}{u}\prod_i\jacobi{a}{p_i}^{e_i}$%
971 *
972 * where %$n = u p_0^{e_0} \ldots p_{n-1}^{e_{n-1}}$% is the
973 * prime factorization of %$n$%. The missing bits are:
974 *
975 * * %$\jacobi{a}{1} = 1$%;
976 * * %$\jacobi{a}{-1} = 1$% if @a@ is negative, or 1 if
977 * positive;
978 * * %$\jacobi{a}{0} = 0$%;
075af359 979 * * %$\jacobi{a}{2}$ is 0 if @a@ is even, 1 if @a@ is
6791ed17
MW
980 * congruent to 1 or 7 (mod 8), or %$-1$% otherwise.
981 *
982 * If %$n$% is positive and odd, then this is the Jacobi
27b1fbee 983 * symbol. (The Kronecker symbol is a consistent domain
6791ed17
MW
984 * extension; the Jacobi symbol was implemented first, and the
985 * name stuck.)
5b00a0ea 986 */
987
22a073c0 988extern int mp_jacobi(mp */*a*/, mp */*n*/);
989
990/* --- @mp_modsqrt@ --- *
991 *
992 * Arguments: @mp *d@ = destination integer
993 * @mp *a@ = source integer
994 * @mp *p@ = modulus (must be prime)
995 *
996 * Returns: If %$a$% is a quadratic residue, a square root of %$a$%; else
997 * a null pointer.
998 *
999 * Use: Returns an integer %$x$% such that %$x^2 \equiv a \pmod{p}$%,
1000 * if one exists; else a null pointer. This function will not
1001 * work if %$p$% is composite: you must factor the modulus, take
1002 * a square root mod each factor, and recombine the results
1003 * using the Chinese Remainder Theorem.
222c8a43
MW
1004 *
1005 * We guarantee that the square root returned is the smallest
1006 * one (i.e., the `positive' square root).
22a073c0 1007 */
1008
1009extern mp *mp_modsqrt(mp */*d*/, mp */*a*/, mp */*p*/);
5b00a0ea 1010
ffec4880
MW
1011/* --- @mp_modexp@ --- *
1012 *
1013 * Arguments: @mp *d@ = fake destination
1014 * @mp *x@ = base of exponentiation
1015 * @mp *e@ = exponent
1016 * @mp *n@ = modulus (must be positive)
1017 *
1018 * Returns: The value %$x^e \bmod n$%.
1019 */
1020
1021extern mp *mp_modexp(mp */*d*/, mp */*x*/, mp */*e*/, mp */*n*/);
1022
d3409d5e 1023/*----- Test harness support ----------------------------------------------*/
1024
1025#include <mLib/testrig.h>
1026
d9a8ae10 1027#ifndef CATACOMB_MPTEXT_H
d3409d5e 1028# include "mptext.h"
1029#endif
1030
1031extern const test_type type_mp;
d03ab969 1032
1033/*----- That's all, folks -------------------------------------------------*/
1034
1035#ifdef __cplusplus
1036 }
1037#endif
1038
1039#endif