d03ab969 |
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 |