PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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 <http://spinning-yarns.org/michael/sw/>
5  Info: Id: imath.h 21 2006-04-02 18:58:36Z sting
6 
7  Copyright (C) 2002 Michael J. Fromberger, All Rights Reserved.
8 
9  Permission is hereby granted, free of charge, to any person
10  obtaining a copy of this software and associated documentation files
11  (the "Software"), to deal in the Software without restriction,
12  including without limitation the rights to use, copy, modify, merge,
13  publish, distribute, sublicense, and/or sell copies of the Software,
14  and to permit persons to whom the Software is furnished to do so,
15  subject to the following conditions:
16 
17  The above copyright notice and this permission notice shall be
18  included in all copies or substantial portions of the Software.
19 
20  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
21  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
22  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
23  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
24  BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
25  ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
26  CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
27  SOFTWARE.
28  */
29 /* contrib/pgcrypto/imath.h */
30 
31 #ifndef IMATH_H_
32 #define IMATH_H_
33 
34 /* use always 32bit digits - should some arch use 16bit digits? */
35 #define USE_LONG_LONG
36 
37 #include <limits.h>
38 
39 typedef unsigned char mp_sign;
40 typedef unsigned int mp_size;
41 typedef int mp_result;
42 
43 #ifdef USE_LONG_LONG
44 typedef uint32 mp_digit;
45 typedef uint64 mp_word;
46 
47 #define MP_DIGIT_MAX 0xFFFFFFFFULL
48 #define MP_WORD_MAX 0xFFFFFFFFFFFFFFFFULL
49 #else
50 typedef uint16 mp_digit;
51 typedef uint32 mp_word;
52 
53 #define MP_DIGIT_MAX 0xFFFFUL
54 #define MP_WORD_MAX 0xFFFFFFFFUL
55 #endif
56 
57 typedef struct mpz
58 {
63 } mpz_t ,
64  *mp_int;
65 
66 #define MP_DIGITS(Z) ((Z)->digits)
67 #define MP_ALLOC(Z) ((Z)->alloc)
68 #define MP_USED(Z) ((Z)->used)
69 #define MP_SIGN(Z) ((Z)->sign)
70 
71 extern const mp_result MP_OK;
72 extern const mp_result MP_FALSE;
73 extern const mp_result MP_TRUE;
74 extern const mp_result MP_MEMORY;
75 extern const mp_result MP_RANGE;
76 extern const mp_result MP_UNDEF;
77 extern const mp_result MP_TRUNC;
78 extern const mp_result MP_BADARG;
79 
80 #define MP_DIGIT_BIT (sizeof(mp_digit) * CHAR_BIT)
81 #define MP_WORD_BIT (sizeof(mp_word) * CHAR_BIT)
82 
83 #define MP_MIN_RADIX 2
84 #define MP_MAX_RADIX 36
85 
86 extern const mp_sign MP_NEG;
87 extern const mp_sign MP_ZPOS;
88 
89 #define mp_int_is_odd(Z) ((Z)->digits[0] & 1)
90 #define mp_int_is_even(Z) !((Z)->digits[0] & 1)
91 
96 
97 mp_result mp_int_init(mp_int z);
98 mp_int mp_int_alloc(void);
99 mp_result mp_int_init_size(mp_int z, mp_size prec);
100 mp_result mp_int_init_copy(mp_int z, mp_int old);
101 mp_result mp_int_init_value(mp_int z, int value);
102 mp_result mp_int_set_value(mp_int z, int value);
103 void mp_int_clear(mp_int z);
104 void mp_int_free(mp_int z);
105 
106 mp_result mp_int_copy(mp_int a, mp_int c); /* c = a */
107 void mp_int_swap(mp_int a, mp_int c); /* swap a, c */
108 void mp_int_zero(mp_int z); /* z = 0 */
109 mp_result mp_int_abs(mp_int a, mp_int c); /* c = |a| */
110 mp_result mp_int_neg(mp_int a, mp_int c); /* c = -a */
111 mp_result mp_int_add(mp_int a, mp_int b, mp_int c); /* c = a + b */
112 mp_result mp_int_add_value(mp_int a, int value, mp_int c);
113 mp_result mp_int_sub(mp_int a, mp_int b, mp_int c); /* c = a - b */
114 mp_result mp_int_sub_value(mp_int a, int value, mp_int c);
115 mp_result mp_int_mul(mp_int a, mp_int b, mp_int c); /* c = a * b */
116 mp_result mp_int_mul_value(mp_int a, int value, mp_int c);
117 mp_result mp_int_mul_pow2(mp_int a, int p2, mp_int c);
118 mp_result mp_int_sqr(mp_int a, mp_int c); /* c = a * a */
119 
120 mp_result mp_int_div(mp_int a, mp_int b, /* q = a / b */
121  mp_int q, mp_int r); /* r = a % b */
122 mp_result mp_int_div_value(mp_int a, int value, /* q = a / value */
123  mp_int q, int *r); /* r = a % value */
124 mp_result mp_int_div_pow2(mp_int a, int p2, /* q = a / 2^p2 */
125  mp_int q, mp_int r); /* r = q % 2^p2 */
126 mp_result mp_int_mod(mp_int a, mp_int m, mp_int c); /* c = a % m */
127 
128 #define mp_int_mod_value(A, V, R) mp_int_div_value((A), (V), 0, (R))
129 mp_result mp_int_expt(mp_int a, int b, mp_int c); /* c = a^b */
130 mp_result mp_int_expt_value(int a, int b, mp_int c); /* c = a^b */
131 
132 int mp_int_compare(mp_int a, mp_int b); /* a <=> b */
133 int mp_int_compare_unsigned(mp_int a, mp_int b); /* |a| <=> |b| */
134 int mp_int_compare_zero(mp_int z); /* a <=> 0 */
135 int mp_int_compare_value(mp_int z, int value); /* a <=> v */
136 
137 /* Returns true if v|a, false otherwise (including errors) */
138 int mp_int_divisible_value(mp_int a, int v);
139 
140 /* Returns k >= 0 such that z = 2^k, if one exists; otherwise < 0 */
141 int mp_int_is_pow2(mp_int z);
142 
143 mp_result mp_int_exptmod(mp_int a, mp_int b, mp_int m,
144  mp_int c); /* c = a^b (mod m) */
146  mp_int m, mp_int c); /* c = a^v (mod m) */
148  mp_int m, mp_int c); /* c = v^b (mod m) */
149 mp_result mp_int_exptmod_known(mp_int a, mp_int b,
150  mp_int m, mp_int mu,
151  mp_int c); /* c = a^b (mod m) */
152 mp_result mp_int_redux_const(mp_int m, mp_int c);
153 
154 mp_result mp_int_invmod(mp_int a, mp_int m, mp_int c); /* c = 1/a (mod m) */
155 
156 mp_result mp_int_gcd(mp_int a, mp_int b, mp_int c); /* c = gcd(a, b) */
157 
158 mp_result mp_int_egcd(mp_int a, mp_int b, mp_int c, /* c = gcd(a, b) */
159  mp_int x, mp_int y); /* c = ax + by */
160 
161 mp_result mp_int_sqrt(mp_int a, mp_int c); /* c = floor(sqrt(q)) */
162 
163 /* Convert to an int, if representable (returns MP_RANGE if not). */
164 mp_result mp_int_to_int(mp_int z, int *out);
165 
166 /* Convert to nul-terminated string with the specified radix, writing at
167  most limit characters including the nul terminator */
168 mp_result mp_int_to_string(mp_int z, mp_size radix,
169  char *str, int limit);
170 
171 /* Return the number of characters required to represent
172  z in the given radix. May over-estimate. */
173 mp_result mp_int_string_len(mp_int z, mp_size radix);
174 
175 /* Read zero-terminated string into z */
176 mp_result mp_int_read_string(mp_int z, mp_size radix, const char *str);
177 mp_result mp_int_read_cstring(mp_int z, mp_size radix, const char *str,
178  char **end);
179 
180 /* Return the number of significant bits in z */
181 mp_result mp_int_count_bits(mp_int z);
182 
183 /* Convert z to two's complement binary, writing at most limit bytes */
184 mp_result mp_int_to_binary(mp_int z, unsigned char *buf, int limit);
185 
186 /* Read a two's complement binary value into z from the given buffer */
187 mp_result mp_int_read_binary(mp_int z, unsigned char *buf, int len);
188 
189 /* Return the number of bytes required to represent z in binary. */
190 mp_result mp_int_binary_len(mp_int z);
191 
192 /* Convert z to unsigned binary, writing at most limit bytes */
193 mp_result mp_int_to_unsigned(mp_int z, unsigned char *buf, int limit);
194 
195 /* Read an unsigned binary value into z from the given buffer */
196 mp_result mp_int_read_unsigned(mp_int z, unsigned char *buf, int len);
197 
198 /* Return the number of bytes required to represent z as unsigned output */
200 
201 /* Return a statically allocated string describing error code res */
202 const char *mp_error_string(mp_result res);
203 
204 #if 0
205 void s_print(char *tag, mp_int z);
206 void s_print_buf(char *tag, mp_digit *buf, mp_size num);
207 #endif
208 
209 #endif /* end IMATH_H_ */
mp_result mp_int_unsigned_len(mp_int z)
Definition: imath.c:2241
mp_result mp_int_exptmod_bvalue(int value, mp_int b, mp_int m, mp_int c)
Definition: imath.c:1404
mp_result mp_int_exptmod(mp_int a, mp_int b, mp_int m, mp_int c)
Definition: imath.c:1336
static struct @76 value
void mp_int_free(mp_int z)
Definition: imath.c:495
mp_result mp_int_count_bits(mp_int z)
Definition: imath.c:2073
mp_result mp_int_expt_value(int a, int b, mp_int c)
Definition: imath.c:1204
mp_result mp_int_sqr(mp_int a, mp_int c)
Definition: imath.c:902
mp_int mp_int_alloc(void)
Definition: imath.c:371
void mp_int_swap(mp_int a, mp_int c)
Definition: imath.c:539
mp_result mp_int_exptmod_evalue(mp_int a, int value, mp_int m, mp_int c)
Definition: imath.c:1389
mp_digit * digits
Definition: imath.h:59
mp_size used
Definition: imath.h:61
mp_result mp_int_neg(mp_int a, mp_int c)
Definition: imath.c:587
mp_result mp_int_sub(mp_int a, mp_int b, mp_int c)
Definition: imath.c:699
mp_result mp_int_egcd(mp_int a, mp_int b, mp_int c, mp_int x, mp_int y)
Definition: imath.c:1631
const mp_result MP_TRUNC
Definition: imath.c:49
mp_result mp_int_string_len(mp_int z, mp_size radix)
Definition: imath.c:1969
mp_result mp_int_expt(mp_int a, int b, mp_int c)
Definition: imath.c:1166
mp_size mp_get_multiply_threshold(void)
Definition: imath.c:341
int mp_int_compare(mp_int a, mp_int b)
Definition: imath.c:1242
mp_result mp_int_init(mp_int z)
Definition: imath.c:361
mp_result mp_int_mul(mp_int a, mp_int b, mp_int c)
Definition: imath.c:794
mp_result mp_int_add(mp_int a, mp_int b, mp_int c)
Definition: imath.c:607
const mp_result MP_UNDEF
Definition: imath.c:48
struct mpz * mp_int
mp_result mp_int_div(mp_int a, mp_int b, mp_int q, mp_int r)
Definition: imath.c:955
mp_result mp_int_init_value(mp_int z, int value)
Definition: imath.c:438
mp_result mp_int_to_binary(mp_int z, unsigned char *buf, int limit)
Definition: imath.c:2103
mp_result mp_int_to_string(mp_int z, mp_size radix, char *str, int limit)
Definition: imath.c:1901
const mp_sign MP_NEG
Definition: imath.c:52
int mp_int_is_pow2(mp_int z)
Definition: imath.c:1796
mp_result mp_int_sub_value(mp_int a, int value, mp_int c)
Definition: imath.c:779
unsigned short uint16
Definition: c.h:267
mp_size mp_get_default_precision(void)
Definition: imath.c:319
const mp_result MP_OK
Definition: imath.c:43
const mp_result MP_BADARG
Definition: imath.c:50
void mp_set_default_precision(mp_size s)
Definition: imath.c:329
mp_result mp_int_mod(mp_int a, mp_int m, mp_int c)
Definition: imath.c:1080
mp_result mp_int_invmod(mp_int a, mp_int m, mp_int c)
Definition: imath.c:1481
char * c
const mp_result MP_MEMORY
Definition: imath.c:46
static char * buf
Definition: pg_test_fsync.c:65
mp_result mp_int_read_unsigned(mp_int z, unsigned char *buf, int len)
Definition: imath.c:2210
unsigned int uint32
Definition: c.h:268
mp_result mp_int_redux_const(mp_int m, mp_int c)
Definition: imath.c:1469
mp_result mp_int_div_value(mp_int a, int value, mp_int q, int *r)
Definition: imath.c:1119
void mp_int_clear(mp_int z)
Definition: imath.c:478
mp_sign sign
Definition: imath.h:62
mp_result mp_int_binary_len(mp_int z)
Definition: imath.c:2170
mp_result mp_int_div_pow2(mp_int a, int p2, mp_int q, mp_int r)
Definition: imath.c:1146
mp_result mp_int_read_cstring(mp_int z, mp_size radix, const char *str, char **end)
Definition: imath.c:2004
int mp_int_compare_unsigned(mp_int a, mp_int b)
Definition: imath.c:1277
mp_result mp_int_to_unsigned(mp_int z, unsigned char *buf, int limit)
Definition: imath.c:2196
struct mpz mpz_t
mp_result mp_int_mul_value(mp_int a, int value, mp_int c)
Definition: imath.c:867
const mp_result MP_TRUE
Definition: imath.c:45
mp_result mp_int_to_int(mp_int z, int *out)
Definition: imath.c:1865
int mp_int_compare_zero(mp_int z)
Definition: imath.c:1289
int mp_int_compare_value(mp_int z, int value)
Definition: imath.c:1306
mp_result mp_int_read_string(mp_int z, mp_size radix, const char *str)
Definition: imath.c:1993
void mp_set_multiply_threshold(mp_size s)
Definition: imath.c:351
mp_result mp_int_gcd(mp_int a, mp_int b, mp_int c)
Definition: imath.c:1536
void mp_int_zero(mp_int z)
Definition: imath.c:555
unsigned char mp_sign
Definition: imath.h:39
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:510
mp_result mp_int_init_copy(mp_int z, mp_int old)
Definition: imath.c:412
const mp_result MP_FALSE
Definition: imath.c:44
mp_result mp_int_add_value(mp_int a, int value, mp_int c)
Definition: imath.c:684
int mp_result
Definition: imath.h:41
unsigned int mp_size
Definition: imath.h:40
mp_size alloc
Definition: imath.h:60
const mp_result MP_RANGE
Definition: imath.c:47
mp_result mp_int_set_value(mp_int z, int value)
Definition: imath.c:455
mp_result mp_int_exptmod_known(mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c)
Definition: imath.c:1420
uint32 mp_digit
Definition: imath.h:44
int mp_int_divisible_value(mp_int a, int v)
Definition: imath.c:1781
const char * mp_error_string(mp_result res)
Definition: imath.c:2259
mp_result mp_int_sqrt(mp_int a, mp_int c)
Definition: imath.c:1808
mp_result mp_int_mul_pow2(mp_int a, int p2, mp_int c)
Definition: imath.c:882
const mp_sign MP_ZPOS
Definition: imath.c:53
Definition: imath.h:57
uint64 mp_word
Definition: imath.h:45
mp_result mp_int_init_size(mp_int z, mp_size prec)
Definition: imath.c:389
mp_result mp_int_read_binary(mp_int z, unsigned char *buf, int len)
Definition: imath.c:2125
mp_result mp_int_abs(mp_int a, mp_int c)
Definition: imath.c:569