libgmp.h (5179B)
1 #define __GMP_NO_ATTRIBUTE_CONST_PURE 2 3 #include <gmp.h> 4 5 #include <setjmp.h> 6 #include <stddef.h> 7 #include <stdint.h> 8 #include <stdio.h> 9 #include <stdlib.h> 10 11 #define BIGINT_LIBRARY "GMP" 12 13 typedef mpz_t z_t; 14 15 static z_t _0, _1, _a, _b; 16 static FILE *_fbuf; 17 static gmp_randstate_t _randstate; 18 19 static inline void 20 zsetup(jmp_buf env) 21 { 22 static char buf[1000]; 23 (void) env; 24 mpz_init_set_ui(_0, 0); 25 mpz_init_set_ui(_1, 1); 26 mpz_init(_a); 27 mpz_init(_b); 28 _fbuf = fmemopen(buf, sizeof(buf), "r+"); 29 gmp_randinit_mt(_randstate); 30 } 31 32 static inline void 33 zunsetup(void) 34 { 35 mpz_clear(_0); 36 mpz_clear(_1); 37 mpz_clear(_a); 38 mpz_clear(_b); 39 fclose(_fbuf); 40 gmp_randclear(_randstate); 41 } 42 43 #define FAST_RANDOM 0 44 #define SECURE_RANDOM 0 45 #define DEFAULT_RANDOM 0 46 #define FASTEST_RANDOM 0 47 #define LIBC_RAND_RANDOM 0 48 #define LIBC_RANDOM_RANDOM 0 49 #define LIBC_RAND48_RANDOM 0 50 #define QUASIUNIFORM 0 51 #define UNIFORM 1 52 #define MODUNIFORM 2 53 54 #define zperror(x) ((void)0) 55 #define zinit mpz_init 56 #define zfree mpz_clear 57 58 #define zset mpz_set 59 #define zneg mpz_neg 60 #define zabs mpz_abs 61 #define zadd_unsigned(r, a, b) (zabs(_a, a), zabs(_b, b), mpz_add(r, _a, _b)) 62 #define zsub_unsigned(r, a, b) (zabs(_a, a), zabs(_b, b), mpz_sub(r, _a, _b)) 63 #define zadd mpz_add 64 #define zsub mpz_sub 65 #define zand mpz_and 66 #define zor mpz_ior 67 #define zxor mpz_xor 68 #define zbtest mpz_tstbit 69 #define zeven_nonzero zeven 70 #define zodd_nonzero zodd 71 #define zzero(a) (!mpz_sgn(a)) 72 #define zsignum mpz_sgn 73 #define zbits(a) mpz_sizeinbase(a, 2) 74 #define zlsb(a) mpz_scan1(a, 0) 75 #define zswap mpz_swap 76 #define zlsh mpz_mul_2exp 77 #define zrsh mpz_tdiv_q_2exp 78 #define ztrunc mpz_tdiv_r_2exp 79 #define zcmpmag mpz_cmpabs 80 #define zcmp mpz_cmp 81 #define zcmpi(a, b) (zseti(_b, b), zcmp(a, _b)) 82 #define zcmpu(a, b) (zsetu(_b, b), zcmp(a, _b)) 83 #define zgcd mpz_gcd 84 #define zmul mpz_mul 85 #define zsqr(r, a) mpz_mul(r, a, a) 86 #define zmodmul(r, a, b, m) (zmul(r, a, b), zmod(r, r, m)) 87 #define zmodsqr(r, a, m) (zsqr(r, a), zmod(r, r, m)) 88 #define zpow(r, a, b) mpz_pow_ui(r, a, mpz_get_ui(b)) 89 #define zpowu mpz_pow_ui 90 #define zmodpow mpz_powm 91 #define zmodpowu mpz_powm_ui 92 #define zsets(a, s) mpz_set_str(a, s, 10) 93 #define zstr_length(a, b) (mpz_sizeinbase(a, 10) + (zsignum(a) < 0)) 94 #define zstr(a, s, n) (mpz_get_str(s, 10, a)) 95 #define zptest(w, a, t) mpz_probab_prime_p(a, t) /* Note, the witness is not returned. */ 96 #define zdiv mpz_tdiv_q 97 #define zmod mpz_tdiv_r 98 #define zdivmod mpz_tdiv_qr 99 100 static inline int 101 zeven(z_t a) 102 { 103 return mpz_even_p(a); 104 } 105 106 static inline int 107 zodd(z_t a) 108 { 109 return mpz_odd_p(a); 110 } 111 112 static inline void 113 zsetu(z_t r, unsigned long long int val) 114 { 115 uint32_t high = (uint32_t)(val >> 32); 116 uint32_t low = (uint32_t)val; 117 118 if (high) { 119 mpz_set_ui(r, high); 120 mpz_set_ui(_a, low); 121 zlsh(r, r, 32); 122 zadd(r, r, _a); 123 } else { 124 mpz_set_ui(r, low); 125 } 126 127 } 128 129 static inline void 130 zseti(z_t r, long long int val) 131 { 132 if (val >= 0) { 133 zsetu(r, (unsigned long long int)val); 134 } else { 135 zsetu(r, (unsigned long long int)-val); 136 zneg(r, r); 137 } 138 } 139 140 static inline void 141 znot(z_t r, z_t a) 142 { 143 size_t bits = zbits(a); 144 mpz_set_ui(_b, 0); 145 mpz_setbit(_b, bits); 146 zsub(_b, _b, _1); 147 zxor(r, a, _b); 148 zneg(r, r); 149 } 150 151 static inline void 152 zsplit(z_t high, z_t low, z_t a, size_t brk) 153 { 154 if (low == a) { 155 zrsh(high, a, brk); 156 ztrunc(low, a, brk); 157 } else { 158 ztrunc(low, a, brk); 159 zrsh(high, a, brk); 160 } 161 } 162 163 static inline void 164 zbset(z_t r, z_t a, size_t bit, int mode) 165 { 166 if (r != a) 167 zset(r, a); 168 if (mode > 0) 169 mpz_setbit(r, bit); 170 else if (mode == 0) 171 mpz_clrbit(r, bit); 172 else 173 mpz_combit(r, bit); 174 } 175 176 static inline size_t 177 zsave(z_t a, void *buffer) 178 { 179 size_t n = mpz_out_raw(_fbuf, a); 180 (void)buffer; 181 fseek(_fbuf, -(long)n, SEEK_CUR); 182 return n; 183 } 184 185 static inline size_t 186 zload(z_t a, const void *buffer) 187 { 188 size_t n = mpz_inp_raw(a, _fbuf); 189 (void)buffer; 190 fseek(_fbuf, -(long)n, SEEK_CUR); 191 return n; 192 } 193 194 static inline void 195 zrand(z_t r, int dev, int dist, z_t n) 196 { 197 size_t bits; 198 (void) dev; 199 200 if (zzero(n)) { 201 mpz_set_ui(r, 0); 202 return; 203 } 204 if (zsignum(n) < 0) { 205 return; 206 } 207 208 switch (dist) { 209 case QUASIUNIFORM: 210 bits = zbits(n); 211 mpz_urandomb(r, _randstate, bits); 212 zadd(r, r, _1); 213 zmul(r, r, n); 214 zrsh(r, r, bits); 215 break; 216 217 case UNIFORM: /* Note, n is exclusive in this implementation. */ 218 mpz_urandomm(r, _randstate, n); 219 break; 220 221 case MODUNIFORM: 222 bits = zbits(n); 223 mpz_urandomb(r, _randstate, bits); 224 if (zcmp(r, n) > 0) 225 zsub(r, r, n); 226 break; 227 228 default: 229 abort(); 230 } 231 }