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