PostgreSQL Source Code  git master
imath.h
Go to the documentation of this file.
1 /*
2  Name: imath.h
3  Purpose: Arbitrary precision integer arithmetic routines.
4  Author: M. J. Fromberger
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 <limits.h>
31 
32 typedef unsigned char mp_sign;
33 typedef unsigned int mp_size;
34 typedef int mp_result;
35 typedef long mp_small; /* must be a signed type */
36 typedef unsigned long mp_usmall; /* must be an unsigned type */
37 
38 
39 /* Build with words as uint64 by default. */
40 #ifdef USE_32BIT_WORDS
41 typedef uint16 mp_digit;
42 typedef uint32 mp_word;
43 #define MP_DIGIT_MAX (PG_UINT16_MAX * 1UL)
44 #define MP_WORD_MAX (PG_UINT32_MAX * 1UL)
45 #else
46 typedef uint32 mp_digit;
47 typedef uint64 mp_word;
48 #define MP_DIGIT_MAX (PG_UINT32_MAX * UINT64CONST(1))
49 #define MP_WORD_MAX (PG_UINT64_MAX)
50 #endif
51 
52 typedef struct
53 {
59 } mpz_t ,
60 
61  *mp_int;
62 
63 static inline mp_digit *
64 MP_DIGITS(mp_int Z)
65 {
66  return Z->digits;
67 }
68 static inline mp_size
69 MP_ALLOC(mp_int Z)
70 {
71  return Z->alloc;
72 }
73 static inline mp_size
74 MP_USED(mp_int Z)
75 {
76  return Z->used;
77 }
78 static inline mp_sign
79 MP_SIGN(mp_int Z)
80 {
81  return Z->sign;
82 }
83 
84 extern const mp_result MP_OK;
85 extern const mp_result MP_FALSE;
86 extern const mp_result MP_TRUE;
87 extern const mp_result MP_MEMORY;
88 extern const mp_result MP_RANGE;
89 extern const mp_result MP_UNDEF;
90 extern const mp_result MP_TRUNC;
91 extern const mp_result MP_BADARG;
92 extern const mp_result MP_MINERR;
93 
94 #define MP_DIGIT_BIT (sizeof(mp_digit) * CHAR_BIT)
95 #define MP_WORD_BIT (sizeof(mp_word) * CHAR_BIT)
96 #define MP_SMALL_MIN LONG_MIN
97 #define MP_SMALL_MAX LONG_MAX
98 #define MP_USMALL_MAX ULONG_MAX
99 
100 #define MP_MIN_RADIX 2
101 #define MP_MAX_RADIX 36
102 
107 void mp_int_default_precision(mp_size ndigits);
108 
112 void mp_int_multiply_threshold(mp_size ndigits);
113 
115 extern const mp_sign MP_NEG;
116 
118 extern const mp_sign MP_ZPOS;
119 
121 static inline bool
122 mp_int_is_odd(mp_int z)
123 {
124  return (z->digits[0] & 1) != 0;
125 }
126 
128 static inline bool
129 mp_int_is_even(mp_int z)
130 {
131  return (z->digits[0] & 1) == 0;
132 }
133 
136 mp_result mp_int_init(mp_int z);
137 
140 mp_int mp_int_alloc(void);
141 
145 mp_result mp_int_init_size(mp_int z, mp_size prec);
146 
149 mp_result mp_int_init_copy(mp_int z, mp_int old);
150 
153 
155 mp_result mp_int_init_uvalue(mp_int z, mp_usmall uvalue);
156 
159 
161 mp_result mp_int_set_uvalue(mp_int z, mp_usmall uvalue);
162 
164 void mp_int_clear(mp_int z);
165 
168 void mp_int_free(mp_int z);
169 
172 mp_result mp_int_copy(mp_int a, mp_int c);
173 
175 void mp_int_swap(mp_int a, mp_int c);
176 
178 void mp_int_zero(mp_int z);
179 
181 mp_result mp_int_abs(mp_int a, mp_int c);
182 
184 mp_result mp_int_neg(mp_int a, mp_int c);
185 
187 mp_result mp_int_add(mp_int a, mp_int b, mp_int c);
188 
190 mp_result mp_int_add_value(mp_int a, mp_small value, mp_int c);
191 
193 mp_result mp_int_sub(mp_int a, mp_int b, mp_int c);
194 
196 mp_result mp_int_sub_value(mp_int a, mp_small value, mp_int c);
197 
199 mp_result mp_int_mul(mp_int a, mp_int b, mp_int c);
200 
202 mp_result mp_int_mul_value(mp_int a, mp_small value, mp_int c);
203 
205 mp_result mp_int_mul_pow2(mp_int a, mp_small p2, mp_int c);
206 
208 mp_result mp_int_sqr(mp_int a, mp_int c);
209 
216 mp_result mp_int_div(mp_int a, mp_int b, mp_int q, mp_int r);
217 
221 mp_result mp_int_div_value(mp_int a, mp_small value, mp_int q, mp_small *r);
222 
227 mp_result mp_int_div_pow2(mp_int a, mp_small p2, mp_int q, mp_int r);
228 
231 mp_result mp_int_mod(mp_int a, mp_int m, mp_int c);
232 
235 mp_result mp_int_expt(mp_int a, mp_small b, mp_int c);
236 
240 
243 mp_result mp_int_expt_full(mp_int a, mp_int b, mp_int c);
244 
247 static inline
248 mp_result
250 {
251  return mp_int_div_value(a, value, 0, r);
252 }
253 
255 int mp_int_compare(mp_int a, mp_int b);
256 
259 int mp_int_compare_unsigned(mp_int a, mp_int b);
260 
262 int mp_int_compare_zero(mp_int z);
263 
265 int mp_int_compare_value(mp_int z, mp_small v);
266 
268 int mp_int_compare_uvalue(mp_int z, mp_usmall uv);
269 
271 bool mp_int_divisible_value(mp_int a, mp_small v);
272 
275 int mp_int_is_pow2(mp_int z);
276 
279 mp_result mp_int_exptmod(mp_int a, mp_int b, mp_int m, mp_int c);
280 
283 mp_result mp_int_exptmod_evalue(mp_int a, mp_small value, mp_int m, mp_int c);
284 
287 mp_result mp_int_exptmod_bvalue(mp_small value, mp_int b, mp_int m, mp_int c);
288 
294 mp_result mp_int_exptmod_known(mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c);
295 
298 mp_result mp_int_redux_const(mp_int m, mp_int c);
299 
305 mp_result mp_int_invmod(mp_int a, mp_int m, mp_int c);
306 
311 mp_result mp_int_gcd(mp_int a, mp_int b, mp_int c);
312 
318 mp_result mp_int_egcd(mp_int a, mp_int b, mp_int c, mp_int x, mp_int y);
319 
324 mp_result mp_int_lcm(mp_int a, mp_int b, mp_int c);
325 
329 mp_result mp_int_root(mp_int a, mp_small b, mp_int c);
330 
333 static inline
334 mp_result
335 mp_int_sqrt(mp_int a, mp_int c)
336 {
337  return mp_int_root(a, 2, c);
338 }
339 
342 mp_result mp_int_to_int(mp_int z, mp_small *out);
343 
346 mp_result mp_int_to_uint(mp_int z, mp_usmall *out);
347 
354 mp_result mp_int_to_string(mp_int z, mp_size radix, char *str, int limit);
355 
359 mp_result mp_int_string_len(mp_int z, mp_size radix);
360 
374 mp_result mp_int_read_string(mp_int z, mp_size radix, const char *str);
375 
392 mp_result mp_int_read_cstring(mp_int z, mp_size radix, const char *str, char **end);
393 
395 mp_result mp_int_count_bits(mp_int z);
396 
410 mp_result mp_int_to_binary(mp_int z, unsigned char *buf, int limit);
411 
415 mp_result mp_int_read_binary(mp_int z, unsigned char *buf, int len);
416 
418 mp_result mp_int_binary_len(mp_int z);
419 
429 mp_result mp_int_to_unsigned(mp_int z, unsigned char *buf, int limit);
430 
434 mp_result mp_int_read_unsigned(mp_int z, unsigned char *buf, int len);
435 
439 
443 const char *mp_error_string(mp_result res);
444 
445 #endif /* end IMATH_H_ */
mp_result mp_int_unsigned_len(mp_int z)
Definition: imath.c:2171
mp_result mp_int_lcm(mp_int a, mp_int b, mp_int c)
Definition: imath.c:1716
mp_result mp_int_exptmod(mp_int a, mp_int b, mp_int m, mp_int c)
Definition: imath.c:1369
void mp_int_free(mp_int z)
Definition: imath.c:602
mp_result mp_int_count_bits(mp_int z)
Definition: imath.c:2038
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
mp_result mp_int_sqr(mp_int a, mp_int c)
Definition: imath.c:954
mp_result mp_int_root(mp_int a, mp_small b, mp_int c)
Definition: imath.c:1762
mp_int mp_int_alloc(void)
Definition: imath.c:479
long mp_small
Definition: imath.h:35
void mp_int_swap(mp_int a, mp_int c)
Definition: imath.c:636
mp_digit * digits
Definition: imath.h:55
mp_result mp_int_init_uvalue(mp_int z, mp_usmall uvalue)
Definition: imath.c:557
mp_result mp_int_to_int(mp_int z, mp_small *out)
Definition: imath.c:1822
mp_result mp_int_expt_full(mp_int a, mp_int b, mp_int c)
Definition: imath.c:1241
static mp_sign MP_SIGN(mp_int Z)
Definition: imath.h:79
mp_result mp_int_neg(mp_int a, mp_int c)
Definition: imath.c:677
mp_result mp_int_sub(mp_int a, mp_int b, mp_int c)
Definition: imath.c:778
mp_result mp_int_egcd(mp_int a, mp_int b, mp_int c, mp_int x, mp_int y)
Definition: imath.c:1593
const mp_result MP_TRUNC
Definition: imath.c:81
mp_result mp_int_string_len(mp_int z, mp_size radix)
Definition: imath.c:1948
Definition: imath.h:52
static struct @145 value
int mp_int_compare(mp_int a, mp_int b)
Definition: imath.c:1274
mp_result mp_int_init(mp_int z)
Definition: imath.c:464
mp_result mp_int_set_value(mp_int z, mp_small value)
Definition: imath.c:567
mp_result mp_int_set_uvalue(mp_int z, mp_usmall uvalue)
Definition: imath.c:577
mp_result mp_int_mul(mp_int a, mp_int b, mp_int c)
Definition: imath.c:857
mp_size alloc
Definition: imath.h:56
mp_result mp_int_add(mp_int a, mp_int b, mp_int c)
Definition: imath.c:693
const mp_result MP_UNDEF
Definition: imath.c:80
mp_result mp_int_div(mp_int a, mp_int b, mp_int q, mp_int r)
Definition: imath.c:1002
mp_result mp_int_to_binary(mp_int z, unsigned char *buf, int limit)
Definition: imath.c:2061
mp_result mp_int_to_string(mp_int z, mp_size radix, char *str, int limit)
Definition: imath.c:1883
int mp_int_compare_value(mp_int z, mp_small v)
Definition: imath.c:1335
static mp_result mp_int_mod_value(mp_int a, mp_small value, mp_small *r)
Definition: imath.h:249
const mp_sign MP_NEG
Definition: imath.c:85
int mp_int_is_pow2(mp_int z)
Definition: imath.c:1750
mp_result mp_int_exptmod_bvalue(mp_small value, mp_int b, mp_int m, mp_int c)
Definition: imath.c:1418
unsigned short uint16
Definition: c.h:358
mp_result mp_int_div_value(mp_int a, mp_small value, mp_int q, mp_small *r)
Definition: imath.c:1141
static bool mp_int_is_odd(mp_int z)
Definition: imath.h:122
const mp_result MP_OK
Definition: imath.c:75
const mp_result MP_BADARG
Definition: imath.c:82
struct mpz_t * mp_int
mp_result mp_int_mod(mp_int a, mp_int m, mp_int c)
Definition: imath.c:1122
mp_result mp_int_invmod(mp_int a, mp_int m, mp_int c)
Definition: imath.c:1474
char * c
const mp_result MP_MEMORY
Definition: imath.c:78
static char * buf
Definition: pg_test_fsync.c:67
mp_result mp_int_expt(mp_int a, mp_small b, mp_int c)
Definition: imath.c:1179
mp_result mp_int_read_unsigned(mp_int z, unsigned char *buf, int len)
Definition: imath.c:2147
mp_result mp_int_mul_pow2(mp_int a, mp_small p2, mp_int c)
Definition: imath.c:934
unsigned int uint32
Definition: c.h:359
mp_result mp_int_redux_const(mp_int m, mp_int c)
Definition: imath.c:1466
mp_result mp_int_exptmod_evalue(mp_int a, mp_small value, mp_int m, mp_int c)
Definition: imath.c:1407
static mp_result mp_int_sqrt(mp_int a, mp_int c)
Definition: imath.h:335
mp_result mp_int_sub_value(mp_int a, mp_small value, mp_int c)
Definition: imath.c:846
void mp_int_clear(mp_int z)
Definition: imath.c:587
const mp_result MP_MINERR
Definition: imath.c:83
mp_digit single
Definition: imath.h:54
mp_result mp_int_binary_len(mp_int z)
Definition: imath.c:2116
static mp_size MP_ALLOC(mp_int Z)
Definition: imath.h:69
mp_result mp_int_read_cstring(mp_int z, mp_size radix, const char *str, char **end)
Definition: imath.c:1970
int mp_int_compare_unsigned(mp_int a, mp_int b)
Definition: imath.c:1308
mp_result mp_int_to_unsigned(mp_int z, unsigned char *buf, int limit)
Definition: imath.c:2137
mp_result mp_int_init_value(mp_int z, mp_small value)
Definition: imath.c:547
const mp_result MP_TRUE
Definition: imath.c:77
mp_result mp_int_to_uint(mp_int z, mp_usmall *out)
Definition: imath.c:1853
bool mp_int_divisible_value(mp_int a, mp_small v)
Definition: imath.c:1738
int mp_int_compare_zero(mp_int z)
Definition: imath.c:1316
mp_sign sign
Definition: imath.h:58
static bool mp_int_is_even(mp_int z)
Definition: imath.h:129
mp_result mp_int_read_string(mp_int z, mp_size radix, const char *str)
Definition: imath.c:1964
mp_result mp_int_gcd(mp_int a, mp_int b, mp_int c)
Definition: imath.c:1514
void mp_int_zero(mp_int z)
Definition: imath.c:653
mp_result mp_int_div_pow2(mp_int a, mp_small p2, mp_int q, mp_int r)
Definition: imath.c:1159
unsigned char mp_sign
Definition: imath.h:32
mp_size used
Definition: imath.h:57
mp_result mp_int_mul_value(mp_int a, mp_small value, mp_int c)
Definition: imath.c:923
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:611
mp_result mp_int_expt_value(mp_small a, mp_small b, mp_int c)
Definition: imath.c:1210
mp_result mp_int_init_copy(mp_int z, mp_int old)
Definition: imath.c:520
const mp_result MP_FALSE
Definition: imath.c:76
void mp_int_default_precision(mp_size ndigits)
Definition: imath.c:284
int mp_result
Definition: imath.h:34
unsigned int mp_size
Definition: imath.h:33
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
const mp_result MP_RANGE
Definition: imath.c:79
mp_result mp_int_exptmod_known(mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c)
Definition: imath.c:1429
uint32 mp_digit
Definition: imath.h:46
const char * mp_error_string(mp_result res)
Definition: imath.c:2184
void mp_int_multiply_threshold(mp_size ndigits)
Definition: imath.c:294
const mp_sign MP_ZPOS
Definition: imath.c:86
unsigned long mp_usmall
Definition: imath.h:36
uint64 mp_word
Definition: imath.h:47
mp_result mp_int_init_size(mp_int z, mp_size prec)
Definition: imath.c:490
mp_result mp_int_read_binary(mp_int z, unsigned char *buf, int len)
Definition: imath.c:2077
mp_result mp_int_add_value(mp_int a, mp_small value, mp_int c)
Definition: imath.c:767
int mp_int_compare_uvalue(mp_int z, mp_usmall uv)
Definition: imath.c:1354
mp_result mp_int_abs(mp_int a, mp_int c)
Definition: imath.c:663