Commit | Line | Data |
---|---|---|
d03ab969 | 1 | /* -*-c-*- |
2 | * | |
a69a3efd | 3 | * $Id$ |
d03ab969 | 4 | * |
d3409d5e | 5 | * Simple multiprecision arithmetic |
d03ab969 | 6 | * |
7 | * (c) 1999 Straylight/Edgeware | |
8 | */ | |
9 | ||
10 | /*----- Licensing notice --------------------------------------------------* | |
11 | * | |
12 | * This file is part of Catacomb. | |
13 | * | |
14 | * Catacomb is free software; you can redistribute it and/or modify | |
15 | * it under the terms of the GNU Library General Public License as | |
16 | * published by the Free Software Foundation; either version 2 of the | |
17 | * License, or (at your option) any later version. | |
18 | * | |
19 | * Catacomb is distributed in the hope that it will be useful, | |
20 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
21 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
22 | * GNU Library General Public License for more details. | |
23 | * | |
24 | * You should have received a copy of the GNU Library General Public | |
25 | * License along with Catacomb; if not, write to the Free | |
26 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, | |
27 | * MA 02111-1307, USA. | |
28 | */ | |
29 | ||
d9a8ae10 | 30 | #ifndef CATACOMB_MP_H |
31 | #define CATACOMB_MP_H | |
d03ab969 | 32 | |
33 | #ifdef __cplusplus | |
34 | extern "C" { | |
35 | #endif | |
36 | ||
37 | /*----- Header files ------------------------------------------------------*/ | |
38 | ||
d3409d5e | 39 | #include <assert.h> |
d03ab969 | 40 | #include <string.h> |
41 | ||
d3409d5e | 42 | #include <mLib/sub.h> |
43 | ||
d9a8ae10 | 44 | #ifndef CATACOMB_MPW_H |
d3409d5e | 45 | # include "mpw.h" |
d03ab969 | 46 | #endif |
47 | ||
d34decd2 | 48 | #ifndef CATACOMB_ARENA_H |
49 | # include "arena.h" | |
50 | #endif | |
51 | ||
52 | #ifndef CATACOMB_MPARENA_H | |
53 | # include "mparena.h" | |
54 | #endif | |
55 | ||
d9a8ae10 | 56 | #ifndef CATACOMB_MPX_H |
d03ab969 | 57 | # include "mpx.h" |
58 | #endif | |
59 | ||
d03ab969 | 60 | /*----- Data structures ---------------------------------------------------*/ |
61 | ||
3bc0a0fe | 62 | /* --- A multiprecision integer --- */ |
63 | ||
d03ab969 | 64 | typedef struct mp { |
3bc0a0fe | 65 | mpw *v, *vl; /* Vector of digits, current limit */ |
66 | size_t sz; /* Size of digit buffer in words */ | |
67 | mparena *a; /* Arena for buffer allocation */ | |
68 | unsigned f; /* Flags (see below) */ | |
69 | unsigned ref; /* Reference counter */ | |
d03ab969 | 70 | } mp; |
71 | ||
3bc0a0fe | 72 | #define MP_NEG 1u /* Negative (signed magnitude) */ |
73 | #define MP_BURN 2u /* Secret (viral flag) */ | |
74 | #define MP_CONST 4u /* Uses strange memory allocation */ | |
75 | #define MP_UNDEF 8u /* Contains nothing interesting */ | |
76 | #define MP_DESTROYED 16u /* Has been destroyed */ | |
77 | ||
78 | /* --- A factor for simultaneous exponentation --- * | |
79 | * | |
80 | * Used by the Montgomery and Barrett exponentiators. | |
81 | */ | |
82 | ||
83 | typedef struct mp_expfactor { | |
84 | mp *base; | |
85 | mp *exp; | |
86 | } mp_expfactor; | |
d03ab969 | 87 | |
d3409d5e | 88 | /*----- Useful constants --------------------------------------------------*/ |
d03ab969 | 89 | |
d3409d5e | 90 | extern mp mp_const[]; |
d03ab969 | 91 | |
d3409d5e | 92 | #define MP_ZERO (&mp_const[0]) |
93 | #define MP_ONE (&mp_const[1]) | |
94 | #define MP_TWO (&mp_const[2]) | |
95 | #define MP_THREE (&mp_const[3]) | |
96 | #define MP_FOUR (&mp_const[4]) | |
97 | #define MP_FIVE (&mp_const[5]) | |
98 | #define MP_TEN (&mp_const[6]) | |
d34decd2 | 99 | #define MP_256 (&mp_const[7]) |
100 | #define MP_MONE (&mp_const[8]) | |
d03ab969 | 101 | |
d3409d5e | 102 | #define MP_NEW ((mp *)0) |
d34decd2 | 103 | #define MP_NEWSEC (&mp_const[9]) |
d03ab969 | 104 | |
d34decd2 | 105 | /*----- Trivial macros ----------------------------------------------------*/ |
d03ab969 | 106 | |
d34decd2 | 107 | /* --- @MP_LEN@ --- * |
d03ab969 | 108 | * |
d34decd2 | 109 | * Arguments: @mp *m@ = pointer to a multiprecision integer |
d03ab969 | 110 | * |
d34decd2 | 111 | * Returns: Length of the integer, in words. |
d03ab969 | 112 | */ |
113 | ||
d34decd2 | 114 | #define MP_LEN(m) ((m)->vl - ((m)->v)) |
d03ab969 | 115 | |
d34decd2 | 116 | /*----- Memory management and reference counting --------------------------*/ |
d3409d5e | 117 | |
d34decd2 | 118 | /* --- @mp_new@ --- * |
d03ab969 | 119 | * |
d34decd2 | 120 | * Arguments: @size_t sz@ = size of vector required |
121 | * @unsigned f@ = flags to set | |
d03ab969 | 122 | * |
d34decd2 | 123 | * Returns: Pointer to a new MP structure. |
d03ab969 | 124 | * |
d34decd2 | 125 | * Use: Allocates a new multiprecision integer. The data space is |
126 | * allocated from either the standard global or secret arena, | |
127 | * depending on the initial flags requested. | |
d03ab969 | 128 | */ |
129 | ||
d34decd2 | 130 | extern mp *mp_new(size_t /*sz*/, unsigned /*f*/); |
d03ab969 | 131 | |
d34decd2 | 132 | /* --- @mp_create@ --- * |
d03ab969 | 133 | * |
d34decd2 | 134 | * Arguments: @size_t sz@ = size of vector required |
d03ab969 | 135 | * |
d34decd2 | 136 | * Returns: Pointer to pristine new MP structure with enough memory |
137 | * bolted onto it. | |
138 | * | |
139 | * Use: Creates a new multiprecision integer with indeterminate | |
140 | * contents. The integer has a single reference. | |
d03ab969 | 141 | */ |
142 | ||
d34decd2 | 143 | extern mp *mp_create(size_t /*sz*/); |
d3409d5e | 144 | |
d34decd2 | 145 | /* --- @mp_createsecure@ --- * |
d03ab969 | 146 | * |
d3409d5e | 147 | * Arguments: @size_t sz@ = size of vector required |
d03ab969 | 148 | * |
d3409d5e | 149 | * Returns: Pointer to pristine new MP structure with enough memory |
150 | * bolted onto it. | |
d03ab969 | 151 | * |
d3409d5e | 152 | * Use: Creates a new multiprecision integer with indeterminate |
d34decd2 | 153 | * contents. The integer has a single reference. The integer's |
154 | * data space is allocated from the secure arena. Its burn flag | |
155 | * is set. | |
d03ab969 | 156 | */ |
157 | ||
d34decd2 | 158 | extern mp *mp_createsecure(size_t /*sz*/); |
d03ab969 | 159 | |
d3409d5e | 160 | /* --- @mp_build@ --- * |
d03ab969 | 161 | * |
d3409d5e | 162 | * Arguments: @mp *m@ = pointer to an MP block to fill in |
163 | * @mpw *v@ = pointer to a word array | |
164 | * @mpw *vl@ = pointer just past end of array | |
d03ab969 | 165 | * |
166 | * Returns: --- | |
167 | * | |
d3409d5e | 168 | * Use: Creates a multiprecision integer representing some smallish |
169 | * number. You must provide storage for the number and dispose | |
170 | * of it when you've finished with it. The number is marked as | |
171 | * constant while it exists. | |
d03ab969 | 172 | */ |
173 | ||
d3409d5e | 174 | extern void mp_build(mp */*m*/, mpw */*v*/, mpw */*vl*/); |
d03ab969 | 175 | |
d3409d5e | 176 | /* --- @mp_destroy@ --- * |
d03ab969 | 177 | * |
d3409d5e | 178 | * Arguments: @mp *m@ = pointer to a multiprecision integer |
d03ab969 | 179 | * |
180 | * Returns: --- | |
181 | * | |
d3409d5e | 182 | * Use: Destroys a multiprecision integer. The reference count isn't |
183 | * checked. Don't use this function if you don't know what | |
184 | * you're doing: use @mp_drop@ instead. | |
d03ab969 | 185 | */ |
186 | ||
d3409d5e | 187 | extern void mp_destroy(mp */*m*/); |
d03ab969 | 188 | |
d3409d5e | 189 | /* --- @mp_copy@ --- * |
d03ab969 | 190 | * |
d3409d5e | 191 | * Arguments: @mp *m@ = pointer to a multiprecision integer |
d03ab969 | 192 | * |
d3409d5e | 193 | * Returns: A copy of the given multiprecision integer. |
194 | * | |
195 | * Use: Copies the given integer. In fact you just get another | |
196 | * reference to the same old one again. | |
d03ab969 | 197 | */ |
198 | ||
d3409d5e | 199 | extern mp *mp_copy(mp */*m*/); |
d03ab969 | 200 | |
d3409d5e | 201 | #define MP_COPY(m) ((m)->ref++, (m)) |
202 | ||
203 | /* --- @mp_drop@ --- * | |
d03ab969 | 204 | * |
d3409d5e | 205 | * Arguments: @mp *m@ = pointer to a multiprecision integer |
d03ab969 | 206 | * |
207 | * Returns: --- | |
208 | * | |
d3409d5e | 209 | * Use: Drops a reference to an integer which isn't wanted any more. |
210 | * If there are no more references, the integer is destroyed. | |
d03ab969 | 211 | */ |
212 | ||
d3409d5e | 213 | extern void mp_drop(mp */*m*/); |
d03ab969 | 214 | |
d3409d5e | 215 | #define MP_DROP(m) do { \ |
216 | mp *_mm = (m); \ | |
d34decd2 | 217 | _mm->ref--; \ |
218 | if (_mm->ref == 0 && !(_mm->f & MP_CONST)) \ | |
d3409d5e | 219 | mp_destroy(_mm); \ |
220 | } while (0) | |
221 | ||
222 | /* --- @mp_split@ --- * | |
d03ab969 | 223 | * |
d3409d5e | 224 | * Arguments: @mp *m@ = pointer to a multiprecision integer |
d03ab969 | 225 | * |
d3409d5e | 226 | * Returns: A reference to the same integer, possibly with a different |
227 | * address. | |
d03ab969 | 228 | * |
d3409d5e | 229 | * Use: Splits off a modifiable version of the integer referred to. |
d03ab969 | 230 | */ |
231 | ||
d3409d5e | 232 | extern 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 | 259 | extern 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 | 290 | extern 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 | 335 | extern 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 | 361 | extern 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 | 381 | extern 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 | 399 | extern 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 | ||
418 | extern 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 | 450 | extern 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 | ||
462 | extern 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 | ||
474 | extern 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 | 490 | extern 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 | 509 | extern 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 | 525 | extern 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 | 544 | extern 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 | 559 | extern 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 | ||
576 | extern 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 | 591 | extern 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 | ||
608 | extern void mp_storeb2c(const mp */*m*/, void */*pv*/, size_t /*sz*/); | |
609 | ||
397041a9 | 610 | /*----- Bit operations ----------------------------------------------------*/ |
d03ab969 | 611 | |
397041a9 | 612 | /* --- @mp_not@ --- * |
d03ab969 | 613 | * |
d3409d5e | 614 | * Arguments: @mp *d@ = destination |
d9a8ae10 | 615 | * @mp *a@ = source |
d03ab969 | 616 | * |
397041a9 | 617 | * Returns: The bitwise complement of the source. |
618 | */ | |
d3409d5e | 619 | |
397041a9 | 620 | extern 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*/); | |
639 | MPX_DOBIN(MP_BITDECL) | |
f09e814a | 640 | |
397041a9 | 641 | /* --- @mp_[n]and@, @mp_[n]or@, @mp_[n]xor@, @mp_not@ --- * |
f09e814a | 642 | * |
397041a9 | 643 | * Synonyms for the commonly-used functions. |
f09e814a | 644 | */ |
645 | ||
397041a9 | 646 | #define mp_and mp_bit0001 |
647 | #define mp_or mp_bit0111 | |
648 | #define mp_nand mp_bit1110 | |
649 | #define mp_nor mp_bit1000 | |
650 | #define mp_xor mp_bit0110 | |
f09e814a | 651 | |
397041a9 | 652 | /* --- @mp_testbit@ --- * |
f09e814a | 653 | * |
654 | * Arguments: @mp *x@ = a large integer | |
09d00c6b | 655 | * @unsigned long n@ = which bit to test |
f09e814a | 656 | * |
397041a9 | 657 | * Returns: Nonzero if the bit is set, zero if not. |
d3409d5e | 658 | */ |
659 | ||
397041a9 | 660 | extern 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 | ||
671 | extern mp *mp_setbit(mp */*d*/, mp */*x*/, unsigned long /*n*/); | |
672 | extern 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 | 688 | extern mp *mp_lsl(mp */*d*/, mp */*a*/, size_t /*n*/); |
81578196 | 689 | extern mp *mp_lslc(mp */*d*/, mp */*a*/, size_t /*n*/); |
397041a9 | 690 | extern 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 | 700 | extern 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*/); | |
719 | MPX_DOBIN(MP_BIT2CDECL) | |
720 | ||
721 | /* --- @mp_[n]and@, @mp_[n]or@, @mp_[n]xor@, @mp_not@ --- * | |
722 | * | |
723 | * Synonyms for the commonly-used functions. | |
724 | */ | |
725 | ||
726 | #define mp_and2c mp_bit00012c | |
727 | #define mp_or2c mp_bit01112c | |
728 | #define mp_nand2c mp_bit11102c | |
729 | #define mp_nor2c mp_bit10002c | |
730 | #define mp_xor2c mp_bit01102c | |
731 | ||
397041a9 | 732 | /* --- @mp_lsl2c@, @mp_lsr2c@ --- * |
f09e814a | 733 | * |
734 | * Arguments: @mp *d@ = destination | |
735 | * @mp *a@ = source | |
397041a9 | 736 | * @size_t n@ = number of bits to move |
f09e814a | 737 | * |
397041a9 | 738 | * Returns: Result, @a@ shifted left or right by @n@. Handles the |
739 | * pretence of sign-extension for negative numbers. | |
f09e814a | 740 | */ |
741 | ||
397041a9 | 742 | extern mp *mp_lsl2c(mp */*d*/, mp */*a*/, size_t /*n*/); |
743 | extern 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 | ||
754 | extern 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 | ||
766 | extern mp *mp_setbit2c(mp */*d*/, mp */*x*/, unsigned long /*n*/); | |
767 | extern 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 | ||
778 | extern 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 | ||
792 | extern 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 | ||
816 | extern 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 | 826 | extern 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 | 836 | extern 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 | 846 | extern 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 | 856 | extern 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 | 867 | extern 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 | ||
878 | extern 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 | ||
893 | extern mp *mp_odd(mp */*d*/, mp */*m*/, size_t */*s*/); | |
894 | ||
d3409d5e | 895 | /*----- More advanced algorithms ------------------------------------------*/ |
d03ab969 | 896 | |
22a073c0 | 897 | /* --- @mp_sqrt@ --- * |
898 | * | |
899 | * Arguments: @mp *d@ = pointer to destination integer | |
900 | * @mp *a@ = (nonnegative) integer to take square root of | |
901 | * | |
902 | * Returns: The largest integer %$x$% such that %$x^2 \le a$%. | |
903 | * | |
904 | * Use: Computes integer square roots. | |
905 | * | |
906 | * The current implementation isn't very good: it uses the | |
907 | * Newton-Raphson method to find an approximation to %$a$%. If | |
908 | * there's any demand for a better version, I'll write one. | |
909 | */ | |
910 | ||
911 | extern mp *mp_sqrt(mp */*d*/, mp */*a*/); | |
912 | ||
d3409d5e | 913 | /* --- @mp_gcd@ --- * |
d03ab969 | 914 | * |
d3409d5e | 915 | * Arguments: @mp **gcd, **xx, **yy@ = where to write the results |
916 | * @mp *a, *b@ = sources (must be nonzero) | |
d03ab969 | 917 | * |
918 | * Returns: --- | |
919 | * | |
d3409d5e | 920 | * Use: Calculates @gcd(a, b)@, and two numbers @x@ and @y@ such that |
921 | * @ax + by = gcd(a, b)@. This is useful for computing modular | |
d9a8ae10 | 922 | * inverses. Neither @a@ nor @b@ may be zero. |
d03ab969 | 923 | */ |
924 | ||
d3409d5e | 925 | extern void mp_gcd(mp **/*gcd*/, mp **/*xx*/, mp **/*yy*/, |
926 | mp */*a*/, mp */*b*/); | |
927 | ||
b817bfc6 | 928 | /* -- @mp_modinv@ --- * |
929 | * | |
930 | * Arguments: @mp *d@ = destination | |
931 | * @mp *x@ = argument | |
932 | * @mp *p@ = modulus | |
933 | * | |
934 | * Returns: The inverse %$x^{-1} \bmod p$%. | |
935 | * | |
936 | * Use: Computes a modular inverse. An assertion fails if %$p$% | |
937 | * has no inverse. | |
938 | */ | |
939 | ||
940 | extern mp *mp_modinv(mp */*d*/, mp */*x*/, mp */*p*/); | |
941 | ||
5b00a0ea | 942 | /* --- @mp_jacobi@ --- * |
943 | * | |
944 | * Arguments: @mp *a@ = an integer less than @n@ | |
945 | * @mp *n@ = an odd integer | |
946 | * | |
947 | * Returns: @-1@, @0@ or @1@ -- the Jacobi symbol %$J(a, n)$%. | |
948 | * | |
949 | * Use: Computes the Jacobi symbol. If @n@ is prime, this is the | |
950 | * Legendre symbol and is equal to 1 if and only if @a@ is a | |
951 | * quadratic residue mod @n@. The result is zero if and only if | |
952 | * @a@ and @n@ have a common factor greater than one. | |
953 | */ | |
954 | ||
22a073c0 | 955 | extern int mp_jacobi(mp */*a*/, mp */*n*/); |
956 | ||
957 | /* --- @mp_modsqrt@ --- * | |
958 | * | |
959 | * Arguments: @mp *d@ = destination integer | |
960 | * @mp *a@ = source integer | |
961 | * @mp *p@ = modulus (must be prime) | |
962 | * | |
963 | * Returns: If %$a$% is a quadratic residue, a square root of %$a$%; else | |
964 | * a null pointer. | |
965 | * | |
966 | * Use: Returns an integer %$x$% such that %$x^2 \equiv a \pmod{p}$%, | |
967 | * if one exists; else a null pointer. This function will not | |
968 | * work if %$p$% is composite: you must factor the modulus, take | |
969 | * a square root mod each factor, and recombine the results | |
970 | * using the Chinese Remainder Theorem. | |
222c8a43 MW |
971 | * |
972 | * We guarantee that the square root returned is the smallest | |
973 | * one (i.e., the `positive' square root). | |
22a073c0 | 974 | */ |
975 | ||
976 | extern mp *mp_modsqrt(mp */*d*/, mp */*a*/, mp */*p*/); | |
5b00a0ea | 977 | |
d3409d5e | 978 | /*----- Test harness support ----------------------------------------------*/ |
979 | ||
980 | #include <mLib/testrig.h> | |
981 | ||
d9a8ae10 | 982 | #ifndef CATACOMB_MPTEXT_H |
d3409d5e | 983 | # include "mptext.h" |
984 | #endif | |
985 | ||
986 | extern const test_type type_mp; | |
d03ab969 | 987 | |
988 | /*----- That's all, folks -------------------------------------------------*/ | |
989 | ||
990 | #ifdef __cplusplus | |
991 | } | |
992 | #endif | |
993 | ||
994 | #endif |