• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2   Name:     imath.h
3   Purpose:  Arbitrary precision integer arithmetic routines.
4   Author:   M. J. Fromberger <http://spinning-yarns.org/michael/>
5 
6   Copyright (C) 2002-2007 Michael J. Fromberger, All Rights Reserved.
7 
8   Permission is hereby granted, free of charge, to any person obtaining a copy
9   of this software and associated documentation files (the "Software"), to deal
10   in the Software without restriction, including without limitation the rights
11   to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12   copies of the Software, and to permit persons to whom the Software is
13   furnished to do so, subject to the following conditions:
14 
15   The above copyright notice and this permission notice shall be included in
16   all copies or substantial portions of the Software.
17 
18   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19   IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20   FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
21   AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22   LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23   OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
24   SOFTWARE.
25  */
26 
27 #ifndef IMATH_H_
28 #define IMATH_H_
29 
30 #include <stdint.h>
31 #include <limits.h>
32 
33 #ifdef __cplusplus
34 extern "C" {
35 #endif
36 
37 typedef unsigned char      mp_sign;
38 typedef unsigned int       mp_size;
39 typedef int                mp_result;
40 typedef long               mp_small;  /* must be a signed type */
41 typedef unsigned long      mp_usmall; /* must be an unsigned type */
42 
43 /* Force building with uint64_t so that the library builds consistently
44  * whether we build from the makefile or by embedding imath in another project.
45  */
46 #undef  USE_64BIT_WORDS
47 #define USE_64BIT_WORDS
48 #ifdef  USE_64BIT_WORDS
49 typedef uint32_t           mp_digit;
50 typedef uint64_t           mp_word;
51 #else
52 typedef uint16_t           mp_digit;
53 typedef uint32_t           mp_word;
54 #endif
55 
56 typedef struct mpz {
57   mp_digit    single;
58   mp_digit   *digits;
59   mp_size     alloc;
60   mp_size     used;
61   mp_sign     sign;
62 } mpz_t, *mp_int;
63 
64 #define MP_DIGITS(Z) ((Z)->digits)
65 #define MP_ALLOC(Z)  ((Z)->alloc)
66 #define MP_USED(Z)   ((Z)->used)
67 #define MP_SIGN(Z)   ((Z)->sign)
68 
69 extern const mp_result MP_OK;
70 extern const mp_result MP_FALSE;
71 extern const mp_result MP_TRUE;
72 extern const mp_result MP_MEMORY;
73 extern const mp_result MP_RANGE;
74 extern const mp_result MP_UNDEF;
75 extern const mp_result MP_TRUNC;
76 extern const mp_result MP_BADARG;
77 extern const mp_result MP_MINERR;
78 
79 #define MP_DIGIT_BIT    (sizeof(mp_digit) * CHAR_BIT)
80 #define MP_WORD_BIT     (sizeof(mp_word) * CHAR_BIT)
81 #define MP_SMALL_MIN    LONG_MIN
82 #define MP_SMALL_MAX    LONG_MAX
83 #define MP_USMALL_MIN   ULONG_MIN
84 #define MP_USMALL_MAX   ULONG_MAX
85 
86 #ifdef USE_64BIT_WORDS
87 #  define MP_DIGIT_MAX   (UINT32_MAX * UINT64_C(1))
88 #  define MP_WORD_MAX    (UINT64_MAX)
89 #else
90 #  define MP_DIGIT_MAX   (UINT16_MAX * 1UL)
91 #  define MP_WORD_MAX    (UINT32_MAX * 1UL)
92 #endif
93 
94 #define MP_MIN_RADIX    2
95 #define MP_MAX_RADIX    36
96 
97 /* Values with fewer than this many significant digits use the standard
98    multiplication algorithm; otherwise, a recursive algorithm is used.
99    Choose a value to suit your platform.
100  */
101 #define MP_MULT_THRESH  22
102 
103 #define MP_DEFAULT_PREC 8   /* default memory allocation, in digits */
104 
105 extern const mp_sign   MP_NEG;
106 extern const mp_sign   MP_ZPOS;
107 
108 #define mp_int_is_odd(Z)  ((Z)->digits[0] & 1)
109 #define mp_int_is_even(Z) !((Z)->digits[0] & 1)
110 
111 mp_result mp_int_init(mp_int z);
112 mp_int    mp_int_alloc(void);
113 mp_result mp_int_init_size(mp_int z, mp_size prec);
114 mp_result mp_int_init_copy(mp_int z, mp_int old);
115 mp_result mp_int_init_value(mp_int z, mp_small value);
116 mp_result mp_int_init_uvalue(mp_int z, mp_usmall uvalue);
117 mp_result mp_int_set_value(mp_int z, mp_small value);
118 mp_result mp_int_set_uvalue(mp_int z, mp_usmall uvalue);
119 void      mp_int_clear(mp_int z);
120 void      mp_int_free(mp_int z);
121 
122 mp_result mp_int_copy(mp_int a, mp_int c);           /* c = a     */
123 void      mp_int_swap(mp_int a, mp_int c);           /* swap a, c */
124 void      mp_int_zero(mp_int z);                     /* z = 0     */
125 mp_result mp_int_abs(mp_int a, mp_int c);            /* c = |a|   */
126 mp_result mp_int_neg(mp_int a, mp_int c);            /* c = -a    */
127 mp_result mp_int_add(mp_int a, mp_int b, mp_int c);  /* c = a + b */
128 mp_result mp_int_add_value(mp_int a, mp_small value, mp_int c);
129 mp_result mp_int_sub(mp_int a, mp_int b, mp_int c);  /* c = a - b */
130 mp_result mp_int_sub_value(mp_int a, mp_small value, mp_int c);
131 mp_result mp_int_mul(mp_int a, mp_int b, mp_int c);  /* c = a * b */
132 mp_result mp_int_mul_value(mp_int a, mp_small value, mp_int c);
133 mp_result mp_int_mul_pow2(mp_int a, mp_small p2, mp_int c);
134 mp_result mp_int_sqr(mp_int a, mp_int c);            /* c = a * a */
135 mp_result mp_int_div(mp_int a, mp_int b,             /* q = a / b */
136 		     mp_int q, mp_int r);            /* r = a % b */
137 mp_result mp_int_div_value(mp_int a, mp_small value, /* q = a / value */
138 			   mp_int q, mp_small *r);   /* r = a % value */
139 mp_result mp_int_div_pow2(mp_int a, mp_small p2,     /* q = a / 2^p2  */
140 			  mp_int q, mp_int r);       /* r = q % 2^p2  */
141 mp_result mp_int_mod(mp_int a, mp_int m, mp_int c);  /* c = a % m */
142 #define   mp_int_mod_value(A, V, R) mp_int_div_value((A), (V), 0, (R))
143 mp_result mp_int_expt(mp_int a, mp_small b, mp_int c);         /* c = a^b */
144 mp_result mp_int_expt_value(mp_small a, mp_small b, mp_int c); /* c = a^b */
145 mp_result mp_int_expt_full(mp_int a, mp_int b, mp_int c);      /* c = a^b */
146 
147 int       mp_int_compare(mp_int a, mp_int b);          /* a <=> b     */
148 int       mp_int_compare_unsigned(mp_int a, mp_int b); /* |a| <=> |b| */
149 int       mp_int_compare_zero(mp_int z);                 /* a <=> 0  */
150 int       mp_int_compare_value(mp_int z, mp_small v);    /* a <=> v  */
151 int       mp_int_compare_uvalue(mp_int z, mp_usmall uv); /* a <=> uv */
152 
153 /* Returns true if v|a, false otherwise (including errors) */
154 int       mp_int_divisible_value(mp_int a, mp_small v);
155 
156 /* Returns k >= 0 such that z = 2^k, if one exists; otherwise < 0 */
157 int       mp_int_is_pow2(mp_int z);
158 
159 mp_result mp_int_exptmod(mp_int a, mp_int b, mp_int m,
160 			 mp_int c);                    /* c = a^b (mod m) */
161 mp_result mp_int_exptmod_evalue(mp_int a, mp_small value,
162 				mp_int m, mp_int c);   /* c = a^v (mod m) */
163 mp_result mp_int_exptmod_bvalue(mp_small value, mp_int b,
164 				mp_int m, mp_int c);   /* c = v^b (mod m) */
165 mp_result mp_int_exptmod_known(mp_int a, mp_int b,
166 			       mp_int m, mp_int mu,
167 			       mp_int c);              /* c = a^b (mod m) */
168 mp_result mp_int_redux_const(mp_int m, mp_int c);
169 
170 mp_result mp_int_invmod(mp_int a, mp_int m, mp_int c); /* c = 1/a (mod m) */
171 
172 mp_result mp_int_gcd(mp_int a, mp_int b, mp_int c);    /* c = gcd(a, b)   */
173 
174 mp_result mp_int_egcd(mp_int a, mp_int b, mp_int c,    /* c = gcd(a, b)   */
175 		      mp_int x, mp_int y);             /* c = ax + by     */
176 
177 mp_result mp_int_lcm(mp_int a, mp_int b, mp_int c);    /* c = lcm(a, b)   */
178 
179 mp_result mp_int_root(mp_int a, mp_small b, mp_int c); /* c = floor(a^{1/b}) */
180 #define   mp_int_sqrt(a, c) mp_int_root(a, 2, c)       /* c = floor(sqrt(a)) */
181 
182 /* Convert to a small int, if representable; else MP_RANGE */
183 mp_result mp_int_to_int(mp_int z, mp_small *out);
184 mp_result mp_int_to_uint(mp_int z, mp_usmall *out);
185 
186 /* Convert to nul-terminated string with the specified radix, writing at
187    most limit characters including the nul terminator  */
188 mp_result mp_int_to_string(mp_int z, mp_size radix,
189 			   char *str, int limit);
190 
191 /* Return the number of characters required to represent
192    z in the given radix.  May over-estimate. */
193 mp_result mp_int_string_len(mp_int z, mp_size radix);
194 
195 /* Read zero-terminated string into z */
196 mp_result mp_int_read_string(mp_int z, mp_size radix, const char *str);
197 mp_result mp_int_read_cstring(mp_int z, mp_size radix, const char *str,
198 			      char **end);
199 
200 /* Return the number of significant bits in z */
201 mp_result mp_int_count_bits(mp_int z);
202 
203 /* Convert z to two's complement binary, writing at most limit bytes */
204 mp_result mp_int_to_binary(mp_int z, unsigned char *buf, int limit);
205 
206 /* Read a two's complement binary value into z from the given buffer */
207 mp_result mp_int_read_binary(mp_int z, unsigned char *buf, int len);
208 
209 /* Return the number of bytes required to represent z in binary. */
210 mp_result mp_int_binary_len(mp_int z);
211 
212 /* Convert z to unsigned binary, writing at most limit bytes */
213 mp_result mp_int_to_unsigned(mp_int z, unsigned char *buf, int limit);
214 
215 /* Read an unsigned binary value into z from the given buffer */
216 mp_result mp_int_read_unsigned(mp_int z, unsigned char *buf, int len);
217 
218 /* Return the number of bytes required to represent z as unsigned output */
219 mp_result mp_int_unsigned_len(mp_int z);
220 
221 /* Return a statically allocated string describing error code res */
222 const char *mp_error_string(mp_result res);
223 
224 #if DEBUG
225 void      s_print(char *tag, mp_int z);
226 void      s_print_buf(char *tag, mp_digit *buf, mp_size num);
227 #endif
228 
229 #ifdef __cplusplus
230 }
231 #endif
232 #endif /* end IMATH_H_ */
233