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