Mercurial > dropbear

comparison mtest/mpi.c @ 1:22d5cf7d4b1a libtommath

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Renaming branch
author Matt Johnston <matt@ucc.asn.au>
date Mon, 31 May 2004 18:23:46 +0000
parents
children a96ff234ff19
comparison
equal deleted inserted replaced
-1:000000000000 1:22d5cf7d4b1a
1 /*
2 mpi.c
3
4 by Michael J. Fromberger <[email protected]>
5 Copyright (C) 1998 Michael J. Fromberger, All Rights Reserved
6
7 Arbitrary precision integer arithmetic library
8
9 $Id: mpi.c,v 1.1.1.1 2003/05/19 04:01:19 matt Exp $
10 */
11
12 #include "mpi.h"
13 #include <stdlib.h>
14 #include <string.h>
15 #include <ctype.h>
16
17 #if MP_DEBUG
18 #include <stdio.h>
19
20 #define DIAG(T,V) {fprintf(stderr,T);mp_print(V,stderr);fputc('\n',stderr);}
21 #else
22 #define DIAG(T,V)
23 #endif
24
25 /*
26 If MP_LOGTAB is not defined, use the math library to compute the
27 logarithms on the fly. Otherwise, use the static table below.
28 Pick which works best for your system.
29 */
30 #if MP_LOGTAB
31
32 /* {{{ s_logv_2[] - log table for 2 in various bases */
33
34 /*
35 A table of the logs of 2 for various bases (the 0 and 1 entries of
36 this table are meaningless and should not be referenced).
37
38 This table is used to compute output lengths for the mp_toradix()
39 function. Since a number n in radix r takes up about log_r(n)
40 digits, we estimate the output size by taking the least integer
41 greater than log_r(n), where:
42
43 log_r(n) = log_2(n) * log_r(2)
44
45 This table, therefore, is a table of log_r(2) for 2 <= r <= 36,
46 which are the output bases supported.
47 */
48
49 #include "logtab.h"
50
51 /* }}} */
52 #define LOG_V_2(R) s_logv_2[(R)]
53
54 #else
55
56 #include <math.h>
57 #define LOG_V_2(R) (log(2.0)/log(R))
58
59 #endif
60
61 /* Default precision for newly created mp_int's */
62 static unsigned int s_mp_defprec = MP_DEFPREC;
63
64 /* {{{ Digit arithmetic macros */
65
66 /*
67 When adding and multiplying digits, the results can be larger than
68 can be contained in an mp_digit. Thus, an mp_word is used. These
69 macros mask off the upper and lower digits of the mp_word (the
70 mp_word may be more than 2 mp_digits wide, but we only concern
71 ourselves with the low-order 2 mp_digits)
72
73 If your mp_word DOES have more than 2 mp_digits, you need to
74 uncomment the first line, and comment out the second.
75 */
76
77 /* #define CARRYOUT(W) (((W)>>DIGIT_BIT)&MP_DIGIT_MAX) */
78 #define CARRYOUT(W) ((W)>>DIGIT_BIT)
79 #define ACCUM(W) ((W)&MP_DIGIT_MAX)
80
81 /* }}} */
82
83 /* {{{ Comparison constants */
84
85 #define MP_LT -1
86 #define MP_EQ 0
87 #define MP_GT 1
88
89 /* }}} */
90
91 /* {{{ Constant strings */
92
93 /* Constant strings returned by mp_strerror() */
94 static const char *mp_err_string[] = {
95 "unknown result code", /* say what? */
96 "boolean true", /* MP_OKAY, MP_YES */
97 "boolean false", /* MP_NO */
98 "out of memory", /* MP_MEM */
99 "argument out of range", /* MP_RANGE */
100 "invalid input parameter", /* MP_BADARG */
101 "result is undefined" /* MP_UNDEF */
102 };
103
104 /* Value to digit maps for radix conversion */
105
106 /* s_dmap_1 - standard digits and letters */
107 static const char *s_dmap_1 =
108 "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";
109
110 #if 0
111 /* s_dmap_2 - base64 ordering for digits */
112 static const char *s_dmap_2 =
113 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
114 #endif
115
116 /* }}} */
117
118 /* {{{ Static function declarations */
119
120 /*
121 If MP_MACRO is false, these will be defined as actual functions;
122 otherwise, suitable macro definitions will be used. This works
123 around the fact that ANSI C89 doesn't support an 'inline' keyword
124 (although I hear C9x will ... about bloody time). At present, the
125 macro definitions are identical to the function bodies, but they'll
126 expand in place, instead of generating a function call.
127
128 I chose these particular functions to be made into macros because
129 some profiling showed they are called a lot on a typical workload,
130 and yet they are primarily housekeeping.
131 */
132 #if MP_MACRO == 0
133 void s_mp_setz(mp_digit *dp, mp_size count); /* zero digits */
134 void s_mp_copy(mp_digit *sp, mp_digit *dp, mp_size count); /* copy */
135 void *s_mp_alloc(size_t nb, size_t ni); /* general allocator */
136 void s_mp_free(void *ptr); /* general free function */
137 #else
138
139 /* Even if these are defined as macros, we need to respect the settings
140 of the MP_MEMSET and MP_MEMCPY configuration options...
141 */
142 #if MP_MEMSET == 0
143 #define s_mp_setz(dp, count) \
144 {int ix;for(ix=0;ix<(count);ix++)(dp)[ix]=0;}
145 #else
146 #define s_mp_setz(dp, count) memset(dp, 0, (count) * sizeof(mp_digit))
147 #endif /* MP_MEMSET */
148
149 #if MP_MEMCPY == 0
150 #define s_mp_copy(sp, dp, count) \
151 {int ix;for(ix=0;ix<(count);ix++)(dp)[ix]=(sp)[ix];}
152 #else
153 #define s_mp_copy(sp, dp, count) memcpy(dp, sp, (count) * sizeof(mp_digit))
154 #endif /* MP_MEMCPY */
155
156 #define s_mp_alloc(nb, ni) calloc(nb, ni)
157 #define s_mp_free(ptr) {if(ptr) free(ptr);}
158 #endif /* MP_MACRO */
159
160 mp_err s_mp_grow(mp_int *mp, mp_size min); /* increase allocated size */
161 mp_err s_mp_pad(mp_int *mp, mp_size min); /* left pad with zeroes */
162
163 void s_mp_clamp(mp_int *mp); /* clip leading zeroes */
164
165 void s_mp_exch(mp_int *a, mp_int *b); /* swap a and b in place */
166
167 mp_err s_mp_lshd(mp_int *mp, mp_size p); /* left-shift by p digits */
168 void s_mp_rshd(mp_int *mp, mp_size p); /* right-shift by p digits */
169 void s_mp_div_2d(mp_int *mp, mp_digit d); /* divide by 2^d in place */
170 void s_mp_mod_2d(mp_int *mp, mp_digit d); /* modulo 2^d in place */