3 * $Id: mp.h,v 1.1 1999/09/03 08:41:12 mdw Exp $
5 * Multiprecision arithmetic
7 * (c) 1999 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
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.
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.
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,
30 /*----- Revision history --------------------------------------------------*
33 * Revision 1.1 1999/09/03 08:41:12 mdw
45 /*----- Header files ------------------------------------------------------*/
62 /*----- Data structures ---------------------------------------------------*/
65 mpw
*v
; /* Vector of words */
66 unsigned f
; /* Various flags */
67 size_t sz
; /* Size allocated to word vector */
68 size_t len
; /* Length of current word vector */
72 MPF_SIGN
= 1, /* Sign bit */
73 MPF_BURN
= 2 /* Burn word vector after use */
76 typedef struct mp_bitscan
{
77 const mp
*x
; /* Pointer to target MP */
78 size_t i
; /* Index into MP vector */
79 mpw w
; /* Current value being examined */
80 unsigned bits
; /* Number of bits left in @w@ */
83 /*----- External variables ------------------------------------------------*/
87 #define MP_ZERO (mp_std + 0)
88 #define MP_ONE (mp_std + 1)
89 #define MP_TWO (mp_std + 2)
90 #define MP_THREE (mp_std + 3)
91 #define MP_FOUR (mp_std + 4)
92 #define MP_FIVE (mp_std + 5)
93 #define MP_TEN (mp_std + 6)
94 #define MP_MONE (mp_std + 7)
96 /*----- Memory allocation and low-level fiddling --------------------------*/
98 /* --- @mp_create@ --- *
100 * Arguments @mp *x@ = pointer to MP head
104 * Use: Initializes an MP ready for use. The initial value is zero.
107 #define MP_INIT { 0, 0, 0, 0 }
109 extern void mp_create(mp */
*x*/
);
111 /* --- @MP_BURN@ --- *
113 * Arguments: @x@ = pointer to MP head
115 * Use: Burns the contents of the MP, if it contains sensitive data.
118 #define MP_BURN(x) do { \
120 if (_y->v && _y->f & mpf_burn) { \
121 memset(_y->v, 0, _y->sz * sizeof(mpw)); \
122 _y->f &= ~MPF_BURN; \
126 /* --- @mp_free@ --- *
128 * Arguments: @mp *x@ = pointer to MP head
132 * Use: Releases the memory used by an MP.
135 #define MP_DESTROY(x) do { \
146 extern void mp_free(mp */
*x*/
);
148 /* --- @MP_ENSURE@ --- *
150 * Arguments: @x@ = pointer to MP head
151 * @len@ = length required (in words)
153 * Use: Ensures that the MP has enough memory to store a @len@-word
157 #define MP_ENSURE(x, len) do { \
159 size_t _len = (len); \
161 mp_resize(_x, _len); \
164 /* --- @mp_resize@ --- *
166 * Arguments: @mp *x@ = pointer to MP head
167 * @size_t sz@ = size required (in words)
171 * Use: Resizes the MP so that its word vector has space for
172 * exactly @sz@ words.
175 extern void mp_resize(mp */
*x*/
, size_t /*sz*/);
177 /* --- @mp_norm@ --- *
179 * Arguments: @mp *x@ = pointer to MP head
183 * Use: `Normalizes' an MP. Fixes the @len@ field so that it's
184 * correct. Assumes that @len@ is either already correct or
188 #define MP_NORM(x) do { \
190 MPX_LEN(_y->len, _y->v, _y->len); \
193 extern void mp_norm(mp */
*x*/
);
195 /* --- @mp_dump@ --- *
197 * Arguments: @mp *x@ = pointer to MP head
198 * @FILE *fp@ = pointer to stream to write on
202 * Use: Dumps an MP to a stream.
205 extern void mp_dump(mp */
*x*/
, FILE */
*fp*/
);
207 /* --- @MP_PARANOID@ --- *
209 * Arguments: @x@ = pointer to MP head
211 * Use: Marks the MP as containing sensitive data which should be
212 * burnt when no longer required.
215 #define MP_PARANOID(x) ((x)->f |= MPF_BURN)
217 /* --- @mp_copy@ --- *
219 * Arguments: @mp *d@ = pointer to MP head for destination
220 * @const mp *s@ = pointer to MP head for source
227 extern void mp_copy(mp */
*d*/
, const mp */
*s*/
);
229 /* --- @mp_bits@ --- *
231 * Arguments: @mp *x@ = pointer to MP head
233 * Returns: Length of the number in bits.
235 * Use: Calculates the number of bits required to represent a number.
236 * The number must be normalized.
239 unsigned long mp_bits(mp */
*x*/
);
241 /* --- @mp_octets@ --- *
243 * Arguments: @mp *x@ = pointer to MP head
245 * Returns: Length of number in octets.
247 * Use: Calculates the number of octets required to represent a
248 * number. The number must be normalized.
251 extern size_t mp_octets(mp */
*x*/
);
253 /*----- Loading and storing as binary data --------------------------------*/
255 /* --- @mp_storel@ --- *
257 * Arguments: @mp *x@ = pointer to MP head
258 * @octet *p@ = pointer to octet array
259 * @size_t sz@ = size of octet array
263 * Use: Stores an MP in an octet array, least significant octet
264 * first. High-end octets are silently discarded if there
265 * isn't enough space for them.
268 extern void mp_storel(mp */
*x*/
, octet */
*p*/
, size_t /*sz*/);
270 /* --- @mp_loadl@ --- *
272 * Arguments: @mp *x@ = pointer to MP head
273 * @const octet *p@ = pointer to octet array
274 * @size_t sz@ = size of octet array
278 * Use: Loads an MP in an octet array, least significant octet
282 extern void mp_loadl(mp */
*x*/
, const octet */
*p*/
, size_t /*sz*/);
284 /* --- @mp_storeb@ --- *
286 * Arguments: @mp *x@ = pointer to MP head
287 * @octet *p@ = pointer to octet array
288 * @size_t sz@ = size of octet array
292 * Use: Stores an MP in an octet array, most significant octet
293 * first. High-end octets are silently discarded if there
294 * isn't enough space for them.
297 extern void mp_storeb(mp */
*x*/
, octet */
*p*/
, size_t /*sz*/);
299 /* --- @mp_loadb@ --- *
301 * Arguments: @mp *x@ = pointer to MP head
302 * @const octet *p@ = pointer to octet array
303 * @size_t sz@ = size of octet array
307 * Use: Loads an MP in an octet array, most significant octet
311 extern void mp_loadb(mp */
*x*/
, const octet */
*p*/
, size_t /*sz*/);
313 /*----- Iterating through bits --------------------------------------------*/
315 /* --- @mp_mkbitscan@ --- *
317 * Arguments: @mp_bitscan *sc@ = pointer to bitscan object
318 * @const mp *x@ = pointer to MP head
322 * Use: Initializes a bitscan object.
325 extern void mp_mkbitscan(mp_bitscan */
*sc*/
, const mp */
*x*/
);
327 /* --- @mp_bstep@ --- *
329 * Arguments: @mp_bitscan *sc@ = pointer to bitscanner object
331 * Returns: Nonzero if there is another bit to read.
333 * Use: Steps on to the next bit, and tells the caller whether one
337 extern int mp_bstep(mp_bitscan */
*sc*/
);
339 /* --- @mp_bit@ --- *
341 * Arguments: @const mp_bitscan *sc@ = pointer to bitscanner
343 * Returns: Current bit value.
345 * Use: Returns the value of the current bit.
348 #define MP_BIT(sc) ((sc)->w & 1)
350 extern int mp_bit(const mp_bitscan */
*sc*/
);
352 /*----- Shifting ----------------------------------------------------------*/
354 /* --- @mp_lsl@ --- *
356 * Arguments: @mp *d@ = pointer to MP head of destination
357 * @const mp *x@ = pointer to MP head of source
358 * @size_t n@ = number of bits to shift
362 * Use: Shifts a number left by a given number of bit positions.
365 extern void mp_lsl(mp */
*d*/
, const mp */
*x*/
, size_t /*n*/);
367 /* --- @mp_lsr@ --- *
369 * Arguments: @mp *d@ = pointer to MP head of destination
370 * @const mp *x@ = pointer to MP head of source
371 * @size_t n@ = number of bits to shift
375 * Use: Shifts a number right by a given number of bit positions.
378 extern void mp_lsr(mp */
*d*/
, const mp */
*x*/
, size_t /*n*/);
380 /*----- Unsigned arithmetic -----------------------------------------------*/
382 /* --- @mp_uadd@ --- *
384 * Arguments: @const mp *d@ = pointers to MP head of destination
385 * @const mp *x, *y@ = pointers to MP heads of operands
389 * Use: Performs unsigned MP addition.
392 extern void mp_uadd(mp */
*d*/
, const mp */
*x*/
, const mp */
*y*/
);
394 /* --- @mp_usub@ --- *
396 * Arguments: @const mp *d@ = pointers to MP head of destination
397 * @const mp *x, *y@ = pointers to MP heads of operands
401 * Use: Performs unsigned MP subtraction.
404 extern void mp_usub(mp */
*d*/
, const mp */
*x*/
, const mp */
*y*/
);
406 /* --- @mp_ucmp@ --- *
408 * Arguments: @const mp *x, *y@ = pointers to MP heads of operands
410 * Returns: Less than, equal to, or greater than zero.
412 * Use: Performs unsigned MP comparison.
415 #define MP_UCMP(x, op, y) (mp_ucmp((x), (y)) op 0)
417 extern int mp_ucmp(const mp */
*x*/
, const mp */
*y*/
);
419 /* --- @mp_umul@ --- *
421 * Arguments: @mp *d@ = pointer to MP head of destination
422 * @const mp *x, *y@ = pointes to MP heads of operands
426 * Use: Performs unsigned MP multiplication.
429 extern void mp_umul(mp */
*d*/
, const mp */
*x*/
, const mp */
*y*/
);
431 /* --- @mp_udiv@ --- *
433 * Arguments: @mp *q, *r@ = pointers to MP heads for quotient, remainder
434 * @const mp *x, *y@ = pointers to MP heads for operands
438 * Use: Performs unsigned MP division.
441 extern void mp_udiv(mp */
*q*/
, mp */
*r*/
, const mp */
*x*/
, const mp */
*y*/
);
443 /*----- That's all, folks -------------------------------------------------*/