projects / u / mdw / catacomb / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Split into several parts.
[u/mdw/catacomb] / mp.h
1 /* -*-c-*-
2 *
3 * $Id: mp.h,v 1.1 1999/09/03 08:41:12 mdw Exp $
4 *
5 * Multiprecision arithmetic
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 $
33 * Revision 1.1 1999/09/03 08:41:12 mdw
34 * Initial import.
35 *
36 */
37
38 #ifndef MP_H
39 #define MP_H
40
41 #ifdef __cplusplus
42 extern "C" {
43 #endif
44
45 /*----- Header files ------------------------------------------------------*/
46
47 #include <stdlib.h>
48 #include <string.h>
49
50 #ifndef MPTYPES_H
51 # include "mptypes.h"
52 #endif
53
54 #ifndef MPX_H
55 # include "mpx.h"
56 #endif
57
58 #ifndef MPSCAN_H
59 # include "mpscan.h"
60 #endif
61
62 /*----- Data structures ---------------------------------------------------*/
63
64 typedef struct mp {
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 */
69 } mp;
70
71 enum {
72 MPF_SIGN = 1, /* Sign bit */
73 MPF_BURN = 2 /* Burn word vector after use */
74 };
75
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@ */
81 } mp_bitscan;
82
83 /*----- External variables ------------------------------------------------*/
84
85 extern mp mp_std;
86
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)
95
96 /*----- Memory allocation and low-level fiddling --------------------------*/
97
98 /* --- @mp_create@ --- *
99 *
100 * Arguments @mp *x@ = pointer to MP head
101 *
102 * Returns: ---
103 *
104 * Use: Initializes an MP ready for use. The initial value is zero.
105 */
106
107 #define MP_INIT { 0, 0, 0, 0 }
108
109 extern void mp_create(mp */*x*/);
110
111 /* --- @MP_BURN@ --- *
112 *
113 * Arguments: @x@ = pointer to MP head
114 *
115 * Use: Burns the contents of the MP, if it contains sensitive data.
116 */
117
118 #define MP_BURN(x) do { \
119 mp *_y = (x) \
120 if (_y->v && _y->f & mpf_burn) { \
121 memset(_y->v, 0, _y->sz * sizeof(mpw)); \
122 _y->f &= ~MPF_BURN; \
123 } \
124 } while (0)
125
126 /* --- @mp_free@ --- *
127 *
128 * Arguments: @mp *x@ = pointer to MP head
129 *
130 * Returns: ---
131 *
132 * Use: Releases the memory used by an MP.
133 */
134
135 #define MP_DESTROY(x) do { \
136 mp *_x = (x); \
137 MP_BURN(_x); \
138 if (_x->v) \
139 free(_x->v); \
140 _x->v = 0; \
141 _x->f = 0; \
142 _x->sz = 0; \
143 _x->len = 0; \
144 } while (0)
145
146 extern void mp_free(mp */*x*/);
147
148 /* --- @MP_ENSURE@ --- *
149 *
150 * Arguments: @x@ = pointer to MP head
151 * @len@ = length required (in words)
152 *
153 * Use: Ensures that the MP has enough memory to store a @len@-word
154 * value.
155 */
156
157 #define MP_ENSURE(x, len) do { \
158 mp *_x = (x); \
159 size_t _len = (len); \
160 if (_x->sz < _len) \
161 mp_resize(_x, _len); \
162 } while (0)
163
164 /* --- @mp_resize@ --- *
165 *
166 * Arguments: @mp *x@ = pointer to MP head
167 * @size_t sz@ = size required (in words)
168 *
169 * Returns: ---
170 *
171 * Use: Resizes the MP so that its word vector has space for
172 * exactly @sz@ words.
173 */
174
175 extern void mp_resize(mp */*x*/, size_t /*sz*/);
176
177 /* --- @mp_norm@ --- *
178 *
179 * Arguments: @mp *x@ = pointer to MP head
180 *
181 * Returns: ---
182 *
183 * Use: `Normalizes' an MP. Fixes the @len@ field so that it's
184 * correct. Assumes that @len@ is either already correct or
185 * too large.
186 */
187
188 #define MP_NORM(x) do { \
189 mp *_y = (x); \
190 MPX_LEN(_y->len, _y->v, _y->len); \
191 } while (0)
192
193 extern void mp_norm(mp */*x*/);
194
195 /* --- @mp_dump@ --- *
196 *
197 * Arguments: @mp *x@ = pointer to MP head
198 * @FILE *fp@ = pointer to stream to write on
199 *
200 * Returns: ---
201 *
202 * Use: Dumps an MP to a stream.
203 */
204
205 extern void mp_dump(mp */*x*/, FILE */*fp*/);
206
207 /* --- @MP_PARANOID@ --- *
208 *
209 * Arguments: @x@ = pointer to MP head
210 *
211 * Use: Marks the MP as containing sensitive data which should be
212 * burnt when no longer required.
213 */
214
215 #define MP_PARANOID(x) ((x)->f |= MPF_BURN)
216
217 /* --- @mp_copy@ --- *
218 *
219 * Arguments: @mp *d@ = pointer to MP head for destination
220 * @const mp *s@ = pointer to MP head for source
221 *
222 * Returns: ---
223 *
224 * Use: Copies an MP.
225 */
226
227 extern void mp_copy(mp */*d*/, const mp */*s*/);
228
229 /* --- @mp_bits@ --- *
230 *
231 * Arguments: @mp *x@ = pointer to MP head
232 *
233 * Returns: Length of the number in bits.
234 *
235 * Use: Calculates the number of bits required to represent a number.
236 * The number must be normalized.
237 */
238
239 unsigned long mp_bits(mp */*x*/);
240
241 /* --- @mp_octets@ --- *
242 *
243 * Arguments: @mp *x@ = pointer to MP head
244 *
245 * Returns: Length of number in octets.
246 *
247 * Use: Calculates the number of octets required to represent a
248 * number. The number must be normalized.
249 */
250
251 extern size_t mp_octets(mp */*x*/);
252
253 /*----- Loading and storing as binary data --------------------------------*/
254
255 /* --- @mp_storel@ --- *
256 *
257 * Arguments: @mp *x@ = pointer to MP head
258 * @octet *p@ = pointer to octet array
259 * @size_t sz@ = size of octet array
260 *
261 * Returns: ---
262 *
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.
266 */
267
268 extern void mp_storel(mp */*x*/, octet */*p*/, size_t /*sz*/);
269
270 /* --- @mp_loadl@ --- *
271 *
272 * Arguments: @mp *x@ = pointer to MP head
273 * @const octet *p@ = pointer to octet array
274 * @size_t sz@ = size of octet array
275 *
276 * Returns: ---
277 *
278 * Use: Loads an MP in an octet array, least significant octet
279 * first.
280 */
281
282 extern void mp_loadl(mp */*x*/, const octet */*p*/, size_t /*sz*/);
283
284 /* --- @mp_storeb@ --- *
285 *
286 * Arguments: @mp *x@ = pointer to MP head
287 * @octet *p@ = pointer to octet array
288 * @size_t sz@ = size of octet array
289 *
290 * Returns: ---
291 *
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.
295 */
296
297 extern void mp_storeb(mp */*x*/, octet */*p*/, size_t /*sz*/);
298
299 /* --- @mp_loadb@ --- *
300 *
301 * Arguments: @mp *x@ = pointer to MP head
302 * @const octet *p@ = pointer to octet array
303 * @size_t sz@ = size of octet array
304 *
305 * Returns: ---
306 *
307 * Use: Loads an MP in an octet array, most significant octet
308 * first.
309 */
310
311 extern void mp_loadb(mp */*x*/, const octet */*p*/, size_t /*sz*/);
312
313 /*----- Iterating through bits --------------------------------------------*/
314
315 /* --- @mp_mkbitscan@ --- *
316 *
317 * Arguments: @mp_bitscan *sc@ = pointer to bitscan object
318 * @const mp *x@ = pointer to MP head
319 *
320 * Returns: ---
321 *
322 * Use: Initializes a bitscan object.
323 */
324
325 extern void mp_mkbitscan(mp_bitscan */*sc*/, const mp */*x*/);
326
327 /* --- @mp_bstep@ --- *
328 *
329 * Arguments: @mp_bitscan *sc@ = pointer to bitscanner object
330 *
331 * Returns: Nonzero if there is another bit to read.
332 *
333 * Use: Steps on to the next bit, and tells the caller whether one
334 * exists.
335 */
336
337 extern int mp_bstep(mp_bitscan */*sc*/);
338
339 /* --- @mp_bit@ --- *
340 *
341 * Arguments: @const mp_bitscan *sc@ = pointer to bitscanner
342 *
343 * Returns: Current bit value.
344 *
345 * Use: Returns the value of the current bit.
346 */
347
348 #define MP_BIT(sc) ((sc)->w & 1)
349
350 extern int mp_bit(const mp_bitscan */*sc*/);
351
352 /*----- Shifting ----------------------------------------------------------*/
353
354 /* --- @mp_lsl@ --- *
355 *
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
359 *
360 * Returns: ---
361 *
362 * Use: Shifts a number left by a given number of bit positions.
363 */
364
365 extern void mp_lsl(mp */*d*/, const mp */*x*/, size_t /*n*/);
366
367 /* --- @mp_lsr@ --- *
368 *
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
372 *
373 * Returns: ---
374 *
375 * Use: Shifts a number right by a given number of bit positions.
376 */
377
378 extern void mp_lsr(mp */*d*/, const mp */*x*/, size_t /*n*/);
379
380 /*----- Unsigned arithmetic -----------------------------------------------*/
381
382 /* --- @mp_uadd@ --- *
383 *
384 * Arguments: @const mp *d@ = pointers to MP head of destination
385 * @const mp *x, *y@ = pointers to MP heads of operands
386 *
387 * Returns: ---
388 *
389 * Use: Performs unsigned MP addition.
390 */
391
392 extern void mp_uadd(mp */*d*/, const mp */*x*/, const mp */*y*/);
393
394 /* --- @mp_usub@ --- *
395 *
396 * Arguments: @const mp *d@ = pointers to MP head of destination
397 * @const mp *x, *y@ = pointers to MP heads of operands
398 *
399 * Returns: ---
400 *
401 * Use: Performs unsigned MP subtraction.
402 */
403
404 extern void mp_usub(mp */*d*/, const mp */*x*/, const mp */*y*/);
405
406 /* --- @mp_ucmp@ --- *
407 *
408 * Arguments: @const mp *x, *y@ = pointers to MP heads of operands
409 *
410 * Returns: Less than, equal to, or greater than zero.
411 *
412 * Use: Performs unsigned MP comparison.
413 */
414
415 #define MP_UCMP(x, op, y) (mp_ucmp((x), (y)) op 0)
416
417 extern int mp_ucmp(const mp */*x*/, const mp */*y*/);
418
419 /* --- @mp_umul@ --- *
420 *
421 * Arguments: @mp *d@ = pointer to MP head of destination
422 * @const mp *x, *y@ = pointes to MP heads of operands
423 *
424 * Returns: ---
425 *
426 * Use: Performs unsigned MP multiplication.
427 */
428
429 extern void mp_umul(mp */*d*/, const mp */*x*/, const mp */*y*/);
430
431 /* --- @mp_udiv@ --- *
432 *
433 * Arguments: @mp *q, *r@ = pointers to MP heads for quotient, remainder
434 * @const mp *x, *y@ = pointers to MP heads for operands
435 *
436 * Returns: ---
437 *
438 * Use: Performs unsigned MP division.
439 */
440
441 extern void mp_udiv(mp */*q*/, mp */*r*/, const mp */*x*/, const mp */*y*/);
442
443 /*----- That's all, folks -------------------------------------------------*/
444
445 #ifdef __cplusplus
446 }
447 #endif
448
449 #endif
Catacomb cryptographic library (downstream of http://git.distorted.org.uk/~mdw/catacomb/)