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 { 59 mp_digit *digits; 60 mp_size alloc; 61 mp_size used; 62 mp_sign sign; 63 } mpz_t , 64 65 *mp_int; 66 67 #define MP_DIGITS(Z) ((Z)->digits) 68 #define MP_ALLOC(Z) ((Z)->alloc) 69 #define MP_USED(Z) ((Z)->used) 70 #define MP_SIGN(Z) ((Z)->sign) 71 72 extern const mp_result MP_OK; 73 extern const mp_result MP_FALSE; 74 extern const mp_result MP_TRUE; 75 extern const mp_result MP_MEMORY; 76 extern const mp_result MP_RANGE; 77 extern const mp_result MP_UNDEF; 78 extern const mp_result MP_TRUNC; 79 extern const mp_result MP_BADARG; 80 81 #define MP_DIGIT_BIT (sizeof(mp_digit) * CHAR_BIT) 82 #define MP_WORD_BIT (sizeof(mp_word) * CHAR_BIT) 83 84 #define MP_MIN_RADIX 2 85 #define MP_MAX_RADIX 36 86 87 extern const mp_sign MP_NEG; 88 extern const mp_sign MP_ZPOS; 89 90 #define mp_int_is_odd(Z) ((Z)->digits[0] & 1) 91 #define mp_int_is_even(Z) !((Z)->digits[0] & 1) 92 93 mp_size mp_get_default_precision(void); 94 void mp_set_default_precision(mp_size s); 95 mp_size mp_get_multiply_threshold(void); 96 void mp_set_multiply_threshold(mp_size s); 97 98 mp_result mp_int_init(mp_int z); 99 mp_int mp_int_alloc(void); 100 mp_result mp_int_init_size(mp_int z, mp_size prec); 101 mp_result mp_int_init_copy(mp_int z, mp_int old); 102 mp_result mp_int_init_value(mp_int z, int value); 103 mp_result mp_int_set_value(mp_int z, int value); 104 void mp_int_clear(mp_int z); 105 void mp_int_free(mp_int z); 106 107 mp_result mp_int_copy(mp_int a, mp_int c); /* c = a */ 108 void mp_int_swap(mp_int a, mp_int c); /* swap a, c */ 109 void mp_int_zero(mp_int z); /* z = 0 */ 110 mp_result mp_int_abs(mp_int a, mp_int c); /* c = |a| */ 111 mp_result mp_int_neg(mp_int a, mp_int c); /* c = -a */ 112 mp_result mp_int_add(mp_int a, mp_int b, mp_int c); /* c = a + b */ 113 mp_result mp_int_add_value(mp_int a, int value, mp_int c); 114 mp_result mp_int_sub(mp_int a, mp_int b, mp_int c); /* c = a - b */ 115 mp_result mp_int_sub_value(mp_int a, int value, mp_int c); 116 mp_result mp_int_mul(mp_int a, mp_int b, mp_int c); /* c = a * b */ 117 mp_result mp_int_mul_value(mp_int a, int value, mp_int c); 118 mp_result mp_int_mul_pow2(mp_int a, int p2, mp_int c); 119 mp_result mp_int_sqr(mp_int a, mp_int c); /* c = a * a */ 120 121 mp_result mp_int_div(mp_int a, mp_int b, /* q = a / b */ 122 mp_int q, mp_int r); /* r = a % b */ 123 mp_result mp_int_div_value(mp_int a, int value, /* q = a / value */ 124 mp_int q, int *r); /* r = a % value */ 125 mp_result mp_int_div_pow2(mp_int a, int p2, /* q = a / 2^p2 */ 126 mp_int q, mp_int r); /* r = q % 2^p2 */ 127 mp_result mp_int_mod(mp_int a, mp_int m, mp_int c); /* c = a % m */ 128 129 #define mp_int_mod_value(A, V, R) mp_int_div_value((A), (V), 0, (R)) 130 mp_result mp_int_expt(mp_int a, int b, mp_int c); /* c = a^b */ 131 mp_result mp_int_expt_value(int a, int b, mp_int c); /* c = a^b */ 132 133 int mp_int_compare(mp_int a, mp_int b); /* a <=> b */ 134 int mp_int_compare_unsigned(mp_int a, mp_int b); /* |a| <=> |b| */ 135 int mp_int_compare_zero(mp_int z); /* a <=> 0 */ 136 int mp_int_compare_value(mp_int z, int value); /* a <=> v */ 137 138 /* Returns true if v|a, false otherwise (including errors) */ 139 int mp_int_divisible_value(mp_int a, int v); 140 141 /* Returns k >= 0 such that z = 2^k, if one exists; otherwise < 0 */ 142 int mp_int_is_pow2(mp_int z); 143 144 mp_result mp_int_exptmod(mp_int a, mp_int b, mp_int m, 145 mp_int c); /* c = a^b (mod m) */ 146 mp_result mp_int_exptmod_evalue(mp_int a, int value, 147 mp_int m, mp_int c); /* c = a^v (mod m) */ 148 mp_result mp_int_exptmod_bvalue(int value, mp_int b, 149 mp_int m, mp_int c); /* c = v^b (mod m) */ 150 mp_result mp_int_exptmod_known(mp_int a, mp_int b, 151 mp_int m, mp_int mu, 152 mp_int c); /* c = a^b (mod m) */ 153 mp_result mp_int_redux_const(mp_int m, mp_int c); 154 155 mp_result mp_int_invmod(mp_int a, mp_int m, mp_int c); /* c = 1/a (mod m) */ 156 157 mp_result mp_int_gcd(mp_int a, mp_int b, mp_int c); /* c = gcd(a, b) */ 158 159 mp_result mp_int_egcd(mp_int a, mp_int b, mp_int c, /* c = gcd(a, b) */ 160 mp_int x, mp_int y); /* c = ax + by */ 161 162 mp_result mp_int_sqrt(mp_int a, mp_int c); /* c = floor(sqrt(q)) */ 163 164 /* Convert to an int, if representable (returns MP_RANGE if not). */ 165 mp_result mp_int_to_int(mp_int z, int *out); 166 167 /* Convert to nul-terminated string with the specified radix, writing at 168 most limit characters including the nul terminator */ 169 mp_result mp_int_to_string(mp_int z, mp_size radix, 170 char *str, int limit); 171 172 /* Return the number of characters required to represent 173 z in the given radix. May over-estimate. */ 174 mp_result mp_int_string_len(mp_int z, mp_size radix); 175 176 /* Read zero-terminated string into z */ 177 mp_result mp_int_read_string(mp_int z, mp_size radix, const char *str); 178 mp_result mp_int_read_cstring(mp_int z, mp_size radix, const char *str, 179 char **end); 180 181 /* Return the number of significant bits in z */ 182 mp_result mp_int_count_bits(mp_int z); 183 184 /* Convert z to two's complement binary, writing at most limit bytes */ 185 mp_result mp_int_to_binary(mp_int z, unsigned char *buf, int limit); 186 187 /* Read a two's complement binary value into z from the given buffer */ 188 mp_result mp_int_read_binary(mp_int z, unsigned char *buf, int len); 189 190 /* Return the number of bytes required to represent z in binary. */ 191 mp_result mp_int_binary_len(mp_int z); 192 193 /* Convert z to unsigned binary, writing at most limit bytes */ 194 mp_result mp_int_to_unsigned(mp_int z, unsigned char *buf, int limit); 195 196 /* Read an unsigned binary value into z from the given buffer */ 197 mp_result mp_int_read_unsigned(mp_int z, unsigned char *buf, int len); 198 199 /* Return the number of bytes required to represent z as unsigned output */ 200 mp_result mp_int_unsigned_len(mp_int z); 201 202 /* Return a statically allocated string describing error code res */ 203 const char *mp_error_string(mp_result res); 204 205 #if 0 206 void s_print(char *tag, mp_int z); 207 void s_print_buf(char *tag, mp_digit *buf, mp_size num); 208 #endif 209 210 #endif /* end IMATH_H_ */ 211