1 /* mini-gmp, a minimalistic implementation of a GNU GMP subset. 2 3 Copyright 2011-2014 Free Software Foundation, Inc. 4 5 This file is part of the GNU MP Library. 6 7 The GNU MP Library is free software; you can redistribute it and/or modify 8 it under the terms of either: 9 10 * the GNU Lesser General Public License as published by the Free 11 Software Foundation; either version 3 of the License, or (at your 12 option) any later version. 13 14 or 15 16 * the GNU General Public License as published by the Free Software 17 Foundation; either version 2 of the License, or (at your option) any 18 later version. 19 20 or both in parallel, as here. 21 22 The GNU MP Library is distributed in the hope that it will be useful, but 23 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 24 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 25 for more details. 26 27 You should have received copies of the GNU General Public License and the 28 GNU Lesser General Public License along with the GNU MP Library. If not, 29 see https://www.gnu.org/licenses/. */ 30 31 /* About mini-gmp: This is a minimal implementation of a subset of the 32 GMP interface. It is intended for inclusion into applications which 33 have modest bignums needs, as a fallback when the real GMP library 34 is not installed. 35 36 This file defines the public interface. */ 37 38 #ifndef __MINI_GMP_H__ 39 #define __MINI_GMP_H__ 40 41 /* For size_t */ 42 #include <stddef.h> 43 44 #if defined (__cplusplus) 45 extern "C" { 46 #endif 47 48 void mp_set_memory_functions (void *(*) (size_t), 49 void *(*) (void *, size_t, size_t), 50 void (*) (void *, size_t)); 51 52 void mp_get_memory_functions (void *(**) (size_t), 53 void *(**) (void *, size_t, size_t), 54 void (**) (void *, size_t)); 55 56 typedef unsigned long mp_limb_t; 57 typedef long mp_size_t; 58 typedef unsigned long mp_bitcnt_t; 59 60 typedef mp_limb_t *mp_ptr; 61 typedef const mp_limb_t *mp_srcptr; 62 63 typedef struct 64 { 65 mp_size_t _mp_alloc; /* Number of *limbs* allocated and pointed 66 to by the _mp_d field. */ 67 mp_size_t _mp_size; /* abs(_mp_size) is the number of limbs the 68 last field points to. If _mp_size is 69 negative this is a negative number. */ 70 mp_limb_t *_mp_d; /* Pointer to the limbs. */ 71 } __mpz_struct; 72 73 typedef __mpz_struct mpz_t[1]; 74 75 typedef __mpz_struct *mpz_ptr; 76 typedef const __mpz_struct *mpz_srcptr; 77 78 extern const int mp_bits_per_limb; 79 80 void mpn_copyi (mp_ptr, mp_srcptr, mp_size_t); 81 void mpn_copyd (mp_ptr, mp_srcptr, mp_size_t); 82 void mpn_zero (mp_ptr, mp_size_t); 83 84 int mpn_cmp (mp_srcptr, mp_srcptr, mp_size_t); 85 86 mp_limb_t mpn_add_1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t); 87 mp_limb_t mpn_add_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t); 88 mp_limb_t mpn_add (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t); 89 90 mp_limb_t mpn_sub_1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t); 91 mp_limb_t mpn_sub_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t); 92 mp_limb_t mpn_sub (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t); 93 94 mp_limb_t mpn_mul_1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t); 95 mp_limb_t mpn_addmul_1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t); 96 mp_limb_t mpn_submul_1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t); 97 98 mp_limb_t mpn_mul (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t); 99 void mpn_mul_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t); 100 void mpn_sqr (mp_ptr, mp_srcptr, mp_size_t); 101 int mpn_perfect_square_p (mp_srcptr, mp_size_t); 102 mp_size_t mpn_sqrtrem (mp_ptr, mp_ptr, mp_srcptr, mp_size_t); 103 104 mp_limb_t mpn_lshift (mp_ptr, mp_srcptr, mp_size_t, unsigned int); 105 mp_limb_t mpn_rshift (mp_ptr, mp_srcptr, mp_size_t, unsigned int); 106 107 mp_bitcnt_t mpn_scan0 (mp_srcptr, mp_bitcnt_t); 108 mp_bitcnt_t mpn_scan1 (mp_srcptr, mp_bitcnt_t); 109 110 mp_bitcnt_t mpn_popcount (mp_srcptr, mp_size_t); 111 112 mp_limb_t mpn_invert_3by2 (mp_limb_t, mp_limb_t); 113 #define mpn_invert_limb(x) mpn_invert_3by2 ((x), 0) 114 115 size_t mpn_get_str (unsigned char *, int, mp_ptr, mp_size_t); 116 mp_size_t mpn_set_str (mp_ptr, const unsigned char *, size_t, int); 117 118 void mpz_init (mpz_t); 119 void mpz_init2 (mpz_t, mp_bitcnt_t); 120 void mpz_clear (mpz_t); 121 122 #define mpz_odd_p(z) (((z)->_mp_size != 0) & (int) (z)->_mp_d[0]) 123 #define mpz_even_p(z) (! mpz_odd_p (z)) 124 125 int mpz_sgn (const mpz_t); 126 int mpz_cmp_si (const mpz_t, long); 127 int mpz_cmp_ui (const mpz_t, unsigned long); 128 int mpz_cmp (const mpz_t, const mpz_t); 129 int mpz_cmpabs_ui (const mpz_t, unsigned long); 130 int mpz_cmpabs (const mpz_t, const mpz_t); 131 int mpz_cmp_d (const mpz_t, double); 132 int mpz_cmpabs_d (const mpz_t, double); 133 134 void mpz_abs (mpz_t, const mpz_t); 135 void mpz_neg (mpz_t, const mpz_t); 136 void mpz_swap (mpz_t, mpz_t); 137 138 void mpz_add_ui (mpz_t, const mpz_t, unsigned long); 139 void mpz_add (mpz_t, const mpz_t, const mpz_t); 140 void mpz_sub_ui (mpz_t, const mpz_t, unsigned long); 141 void mpz_ui_sub (mpz_t, unsigned long, const mpz_t); 142 void mpz_sub (mpz_t, const mpz_t, const mpz_t); 143 144 void mpz_mul_si (mpz_t, const mpz_t, long int); 145 void mpz_mul_ui (mpz_t, const mpz_t, unsigned long int); 146 void mpz_mul (mpz_t, const mpz_t, const mpz_t); 147 void mpz_mul_2exp (mpz_t, const mpz_t, mp_bitcnt_t); 148 void mpz_addmul_ui (mpz_t, const mpz_t, unsigned long int); 149 void mpz_addmul (mpz_t, const mpz_t, const mpz_t); 150 void mpz_submul_ui (mpz_t, const mpz_t, unsigned long int); 151 void mpz_submul (mpz_t, const mpz_t, const mpz_t); 152 153 void mpz_cdiv_qr (mpz_t, mpz_t, const mpz_t, const mpz_t); 154 void mpz_fdiv_qr (mpz_t, mpz_t, const mpz_t, const mpz_t); 155 void mpz_tdiv_qr (mpz_t, mpz_t, const mpz_t, const mpz_t); 156 void mpz_cdiv_q (mpz_t, const mpz_t, const mpz_t); 157 void mpz_fdiv_q (mpz_t, const mpz_t, const mpz_t); 158 void mpz_tdiv_q (mpz_t, const mpz_t, const mpz_t); 159 void mpz_cdiv_r (mpz_t, const mpz_t, const mpz_t); 160 void mpz_fdiv_r (mpz_t, const mpz_t, const mpz_t); 161 void mpz_tdiv_r (mpz_t, const mpz_t, const mpz_t); 162 163 void mpz_cdiv_q_2exp (mpz_t, const mpz_t, mp_bitcnt_t); 164 void mpz_fdiv_q_2exp (mpz_t, const mpz_t, mp_bitcnt_t); 165 void mpz_tdiv_q_2exp (mpz_t, const mpz_t, mp_bitcnt_t); 166 void mpz_cdiv_r_2exp (mpz_t, const mpz_t, mp_bitcnt_t); 167 void mpz_fdiv_r_2exp (mpz_t, const mpz_t, mp_bitcnt_t); 168 void mpz_tdiv_r_2exp (mpz_t, const mpz_t, mp_bitcnt_t); 169 170 void mpz_mod (mpz_t, const mpz_t, const mpz_t); 171 172 void mpz_divexact (mpz_t, const mpz_t, const mpz_t); 173 174 int mpz_divisible_p (const mpz_t, const mpz_t); 175 int mpz_congruent_p (const mpz_t, const mpz_t, const mpz_t); 176 177 unsigned long mpz_cdiv_qr_ui (mpz_t, mpz_t, const mpz_t, unsigned long); 178 unsigned long mpz_fdiv_qr_ui (mpz_t, mpz_t, const mpz_t, unsigned long); 179 unsigned long mpz_tdiv_qr_ui (mpz_t, mpz_t, const mpz_t, unsigned long); 180 unsigned long mpz_cdiv_q_ui (mpz_t, const mpz_t, unsigned long); 181 unsigned long mpz_fdiv_q_ui (mpz_t, const mpz_t, unsigned long); 182 unsigned long mpz_tdiv_q_ui (mpz_t, const mpz_t, unsigned long); 183 unsigned long mpz_cdiv_r_ui (mpz_t, const mpz_t, unsigned long); 184 unsigned long mpz_fdiv_r_ui (mpz_t, const mpz_t, unsigned long); 185 unsigned long mpz_tdiv_r_ui (mpz_t, const mpz_t, unsigned long); 186 unsigned long mpz_cdiv_ui (const mpz_t, unsigned long); 187 unsigned long mpz_fdiv_ui (const mpz_t, unsigned long); 188 unsigned long mpz_tdiv_ui (const mpz_t, unsigned long); 189 190 unsigned long mpz_mod_ui (mpz_t, const mpz_t, unsigned long); 191 192 void mpz_divexact_ui (mpz_t, const mpz_t, unsigned long); 193 194 int mpz_divisible_ui_p (const mpz_t, unsigned long); 195 196 unsigned long mpz_gcd_ui (mpz_t, const mpz_t, unsigned long); 197 void mpz_gcd (mpz_t, const mpz_t, const mpz_t); 198 void mpz_gcdext (mpz_t, mpz_t, mpz_t, const mpz_t, const mpz_t); 199 void mpz_lcm_ui (mpz_t, const mpz_t, unsigned long); 200 void mpz_lcm (mpz_t, const mpz_t, const mpz_t); 201 int mpz_invert (mpz_t, const mpz_t, const mpz_t); 202 203 void mpz_sqrtrem (mpz_t, mpz_t, const mpz_t); 204 void mpz_sqrt (mpz_t, const mpz_t); 205 int mpz_perfect_square_p (const mpz_t); 206 207 void mpz_pow_ui (mpz_t, const mpz_t, unsigned long); 208 void mpz_ui_pow_ui (mpz_t, unsigned long, unsigned long); 209 void mpz_powm (mpz_t, const mpz_t, const mpz_t, const mpz_t); 210 void mpz_powm_ui (mpz_t, const mpz_t, unsigned long, const mpz_t); 211 212 void mpz_rootrem (mpz_t, mpz_t, const mpz_t, unsigned long); 213 int mpz_root (mpz_t, const mpz_t, unsigned long); 214 215 void mpz_fac_ui (mpz_t, unsigned long); 216 void mpz_bin_uiui (mpz_t, unsigned long, unsigned long); 217 218 int mpz_probab_prime_p (const mpz_t, int); 219 220 int mpz_tstbit (const mpz_t, mp_bitcnt_t); 221 void mpz_setbit (mpz_t, mp_bitcnt_t); 222 void mpz_clrbit (mpz_t, mp_bitcnt_t); 223 void mpz_combit (mpz_t, mp_bitcnt_t); 224 225 void mpz_com (mpz_t, const mpz_t); 226 void mpz_and (mpz_t, const mpz_t, const mpz_t); 227 void mpz_ior (mpz_t, const mpz_t, const mpz_t); 228 void mpz_xor (mpz_t, const mpz_t, const mpz_t); 229 230 mp_bitcnt_t mpz_popcount (const mpz_t); 231 mp_bitcnt_t mpz_hamdist (const mpz_t, const mpz_t); 232 mp_bitcnt_t mpz_scan0 (const mpz_t, mp_bitcnt_t); 233 mp_bitcnt_t mpz_scan1 (const mpz_t, mp_bitcnt_t); 234 235 int mpz_fits_slong_p (const mpz_t); 236 int mpz_fits_ulong_p (const mpz_t); 237 long int mpz_get_si (const mpz_t); 238 unsigned long int mpz_get_ui (const mpz_t); 239 double mpz_get_d (const mpz_t); 240 size_t mpz_size (const mpz_t); 241 mp_limb_t mpz_getlimbn (const mpz_t, mp_size_t); 242 243 void mpz_realloc2 (mpz_t, mp_bitcnt_t); 244 mp_srcptr mpz_limbs_read (mpz_srcptr); 245 mp_ptr mpz_limbs_modify (mpz_t, mp_size_t); 246 mp_ptr mpz_limbs_write (mpz_t, mp_size_t); 247 void mpz_limbs_finish (mpz_t, mp_size_t); 248 mpz_srcptr mpz_roinit_n (mpz_t, mp_srcptr, mp_size_t); 249 250 #define MPZ_ROINIT_N(xp, xs) {{0, (xs),(xp) }} 251 252 void mpz_set_si (mpz_t, signed long int); 253 void mpz_set_ui (mpz_t, unsigned long int); 254 void mpz_set (mpz_t, const mpz_t); 255 void mpz_set_d (mpz_t, double); 256 257 void mpz_init_set_si (mpz_t, signed long int); 258 void mpz_init_set_ui (mpz_t, unsigned long int); 259 void mpz_init_set (mpz_t, const mpz_t); 260 void mpz_init_set_d (mpz_t, double); 261 262 size_t mpz_sizeinbase (const mpz_t, int); 263 char *mpz_get_str (char *, int, const mpz_t); 264 int mpz_set_str (mpz_t, const char *, int); 265 int mpz_init_set_str (mpz_t, const char *, int); 266 267 /* This long list taken from gmp.h. */ 268 /* For reference, "defined(EOF)" cannot be used here. In g++ 2.95.4, 269 <iostream> defines EOF but not FILE. */ 270 #if defined (FILE) \ 271 || defined (H_STDIO) \ 272 || defined (_H_STDIO) /* AIX */ \ 273 || defined (_STDIO_H) /* glibc, Sun, SCO */ \ 274 || defined (_STDIO_H_) /* BSD, OSF */ \ 275 || defined (__STDIO_H) /* Borland */ \ 276 || defined (__STDIO_H__) /* IRIX */ \ 277 || defined (_STDIO_INCLUDED) /* HPUX */ \ 278 || defined (__dj_include_stdio_h_) /* DJGPP */ \ 279 || defined (_FILE_DEFINED) /* Microsoft */ \ 280 || defined (__STDIO__) /* Apple MPW MrC */ \ 281 || defined (_MSL_STDIO_H) /* Metrowerks */ \ 282 || defined (_STDIO_H_INCLUDED) /* QNX4 */ \ 283 || defined (_ISO_STDIO_ISO_H) /* Sun C++ */ \ 284 || defined (__STDIO_LOADED) /* VMS */ 285 size_t mpz_out_str (FILE *, int, const mpz_t); 286 #endif 287 288 void mpz_import (mpz_t, size_t, int, size_t, int, size_t, const void *); 289 void *mpz_export (void *, size_t *, int, size_t, int, size_t, const mpz_t); 290 291 #if defined (__cplusplus) 292 } 293 #endif 294 #endif /* __MINI_GMP_H__ */ 295