internals.h (11600B)
1 /* See LICENSE file for copyright and license details. */ 2 #include "../zahl.h" 3 4 #include <errno.h> 5 #include <stdlib.h> 6 #include <string.h> 7 8 /* clang pretends to be GCC... */ 9 #if defined(__GNUC__) && defined(__clang__) 10 # undef __GNUC__ 11 #endif 12 13 #define BITS_PER_CHAR ZAHL_BITS_PER_CHAR 14 #define LB_BITS_PER_CHAR ZAHL_LB_BITS_PER_CHAR 15 16 #define FLOOR_BITS_TO_CHARS(bits) ZAHL_FLOOR_BITS_TO_CHARS(bits) 17 #define CEILING_BITS_TO_CHARS(bits) ZAHL_CEILING_BITS_TO_CHARS(bits) 18 #define BITS_IN_LAST_CHAR(bits) ZAHL_BITS_IN_LAST_CHAR(bits) 19 #define TRUNCATE_TO_CHAR(bits) ZAHL_TRUNCATE_TO_CHAR(bits) 20 21 #define O0 ZAHL_O0 22 #define O1 ZAHL_O1 23 #define O2 ZAHL_O2 24 #define O3 ZAHL_O3 25 #define Ofast ZAHL_Ofast 26 #define Os ZAHL_Os 27 #define Oz ZAHL_Oz 28 29 #define LIST_TEMPS_HERE\ 30 X(libzahl_tmp_str_num, 0)\ 31 X(libzahl_tmp_str_mag, 0)\ 32 X(libzahl_tmp_str_div, 0)\ 33 X(libzahl_tmp_str_rem, 0)\ 34 X(libzahl_tmp_gcd_u, 0)\ 35 X(libzahl_tmp_gcd_v, 0)\ 36 X(libzahl_tmp_sub, 0)\ 37 X(libzahl_tmp_modmul, 0)\ 38 X(libzahl_tmp_pow_b, 0)\ 39 X(libzahl_tmp_pow_c, 0)\ 40 X(libzahl_tmp_pow_d, 0)\ 41 X(libzahl_tmp_modsqr, 0)\ 42 X(libzahl_tmp_divmod_a, 0)\ 43 X(libzahl_tmp_divmod_b, 0)\ 44 X(libzahl_tmp_divmod_d, 0)\ 45 X(libzahl_tmp_ptest_x, 0)\ 46 X(libzahl_tmp_ptest_a, 0)\ 47 X(libzahl_tmp_ptest_d, 0)\ 48 X(libzahl_tmp_ptest_n1, 0)\ 49 X(libzahl_tmp_ptest_n4, 0) 50 51 #define LIST_TEMPS\ 52 X(libzahl_tmp_div, 0)\ 53 X(libzahl_tmp_mod, 0)\ 54 LIST_TEMPS_HERE 55 56 #define LIST_CONSTS\ 57 X(0, libzahl_const_1e19, zsetu, 10000000000000000000ULL) /* The largest power of 10 < 2⁶⁴. */\ 58 X(1, libzahl_const_1, zsetu, 1)\ 59 X(2, libzahl_const_2, zsetu, 2)\ 60 X(3, libzahl_const_4, zsetu, 4) 61 62 #define X(x, s) extern z_t x; 63 LIST_TEMPS_HERE 64 #undef X 65 #define X(i, x, f, v) extern z_t x; 66 LIST_CONSTS 67 #undef X 68 69 extern z_t libzahl_tmp_divmod_ds[BITS_PER_CHAR]; 70 extern jmp_buf libzahl_jmp_buf; 71 extern int libzahl_set_up; 72 extern int libzahl_error; 73 extern zahl_char_t **libzahl_pool[sizeof(size_t) * 8]; 74 extern size_t libzahl_pool_n[sizeof(size_t) * 8]; 75 extern size_t libzahl_pool_alloc[sizeof(size_t) * 8]; 76 extern struct zahl **libzahl_temp_stack; 77 extern struct zahl **libzahl_temp_stack_head; 78 extern struct zahl **libzahl_temp_stack_end; 79 extern void *libzahl_temp_allocation; 80 81 #define likely(expr) ZAHL_LIKELY(expr) 82 #define unlikely(expr) ZAHL_UNLIKELY(expr) 83 84 #if defined(ZAHL_UNSAFE) 85 # define check(expr) 0 86 #else 87 # define check(expr) unlikely(expr) 88 #endif 89 90 #define SET_SIGNUM(a, signum) ZAHL_SET_SIGNUM(a, signum) 91 #define SET(a, b) ZAHL_SET(a, b) 92 #define ENSURE_SIZE(a, n) ZAHL_ENSURE_SIZE(a, n) 93 #define TRIM(a) ZAHL_TRIM(a) 94 #define TRIM_NONZERO(a) ZAHL_TRIM_NONZERO(a) 95 #define TRIM_AND_ZERO(a) ZAHL_TRIM_AND_ZERO(a) 96 #define TRIM_AND_SIGN(a, s) ZAHL_TRIM_AND_SIGN(a, s) 97 #define SWAP(a, b, t, m) ((t)->m = (a)->m, (a)->m = (b)->m, (b)->m = (t)->m) 98 #define MIN(a, b) ((a) < (b) ? (a) : (b)) 99 #define MAX(a, b) ((a) > (b) ? (a) : (b)) 100 #define MIN_MAX_1(min, max, a, b) ((min) = MIN(a, b), (max) = MAX(a, b)) 101 #define MIN_MAX_2(min, max, a, b) ((min) = (a) + (b) - ((max) = MAX(a, b))) 102 #define znegative(a) (zsignum(a) < 0) 103 #define znegative1(a, b) ((zsignum(a) | zsignum(b)) < 0) 104 #define znegative2(a, b) ((zsignum(a) & zsignum(b)) < 0) 105 #define zpositive(a) (zsignum(a) > 0) 106 #define zpositive1(a, b) (zpositive(a) + zpositive(b) > 0) 107 #define zpositive2(a, b) (zsignum(a) + zsignum(b) == 2) 108 #define zzero2(a, b) (!(zsignum(a) | zsignum(b))) 109 #define zmemcpy(d, s, n) libzahl_memcpy(d, s, n) 110 #define zmemmove(d, s, n) libzahl_memmove(d, s, n) 111 #define zmemmovef(d, s, n) libzahl_memmovef(d, s, n) 112 #define zmemmoveb(d, s, n) libzahl_memmoveb(d, s, n) 113 #define zmemset(a, v, n) libzahl_memset(a, v, n) 114 #define zmemset_precise(a, v, n) libzahl_memset_precise(a, v, n) 115 116 static inline int 117 zzero1(z_t a, z_t b) 118 { 119 return zzero(a) || zzero(b); 120 } 121 122 static inline void 123 zmemcpy_range(register zahl_char_t *restrict d, register const zahl_char_t *restrict s, size_t i, size_t n) 124 { 125 d += i; 126 s += i; 127 n -= i; 128 zmemcpy(d, s, n); 129 } 130 131 static void 132 libzahl_failure(int error) 133 { 134 libzahl_error = (error); 135 if (libzahl_temp_stack) 136 while (libzahl_temp_stack_head != libzahl_temp_stack) 137 zfree(*--libzahl_temp_stack_head); 138 free(libzahl_temp_allocation); 139 libzahl_temp_allocation = 0; 140 longjmp(libzahl_jmp_buf, 1); 141 } 142 143 static inline void 144 libzahl_memfailure(void) 145 { 146 if (!errno) /* sigh... */ 147 errno = ENOENT; 148 libzahl_failure(errno); 149 } 150 151 /* 152 * libzahl_msb_nz_zu 153 * ^^^ ^^ ^^ 154 * | | | 155 * | | \- size_t parameter 156 * | \- non-zero input 157 * \- most significant bit 158 */ 159 160 #if SIZE_MAX == ULONG_MAX 161 # define libzahl_msb_nz_zu(x) libzahl_msb_nz_lu(x) 162 #else 163 # define libzahl_msb_nz_zu(x) libzahl_msb_nz_llu(x) 164 #endif 165 166 #if defined(__GNUC__) || defined(__clang__) 167 # define libzahl_msb_nz_lu(x) (8 * sizeof(unsigned long int) - 1 - (size_t)__builtin_clzl(x)) 168 # define libzahl_msb_nz_llu(x) (8 * sizeof(unsigned long long int) - 1 - (size_t)__builtin_clzll(x)) 169 #else 170 static inline size_t 171 libzahl_msb_nz_lu(unsigned long int x) 172 { 173 size_t r = 0; 174 for (; x; x >>= 1, r++); 175 return r - 1; 176 } 177 178 static inline size_t 179 libzahl_msb_nz_llu(unsigned long long int x) 180 { 181 size_t r = 0; 182 for (; x; x >>= 1, r++); 183 return r - 1; 184 } 185 #endif 186 187 #if defined(__GNUC__) || defined(__clang__) 188 # if INT64_MAX == LONG_MAX 189 # define libzahl_add_overflow(rp, a, b) __builtin_uaddl_overflow(a, b, rp) 190 # else 191 # define libzahl_add_overflow(rp, a, b) __builtin_uaddll_overflow(a, b, rp) 192 # endif 193 #else 194 static inline int 195 libzahl_add_overflow(zahl_char_t *rp, zahl_char_t a, zahl_char_t b) 196 { 197 int carry = ZAHL_CHAR_MAX - a < b; 198 *rp = a + b; 199 return carry; 200 } 201 #endif 202 203 static inline void 204 zsplit_pz(z_t high, z_t low, z_t a, size_t delim) 205 { 206 if (unlikely(zzero(a))) { 207 SET_SIGNUM(high, 0); 208 SET_SIGNUM(low, 0); 209 } else { 210 zsplit(high, low, a, delim); 211 } 212 } 213 214 static inline void 215 zrsh_taint(z_t a, size_t bits) 216 { 217 size_t i, chars, cbits; 218 219 if (unlikely(!bits)) 220 return; 221 if (unlikely(zzero(a))) 222 return; 223 224 chars = FLOOR_BITS_TO_CHARS(bits); 225 226 if (unlikely(chars >= a->used || zbits(a) <= bits)) { 227 SET_SIGNUM(a, 0); 228 return; 229 } 230 231 bits = BITS_IN_LAST_CHAR(bits); 232 cbits = BITS_PER_CHAR - bits; 233 234 if (likely(chars)) { 235 a->used -= chars; 236 a->chars += chars; 237 } 238 239 if (unlikely(bits)) { /* This if statement is very important in C. */ 240 a->chars[0] >>= bits; 241 for (i = 1; i < a->used; i++) { 242 a->chars[i - 1] |= a->chars[i] << cbits; 243 a->chars[i] >>= bits; 244 } 245 TRIM_NONZERO(a); 246 } 247 } 248 249 static inline void 250 zswap_tainted_unsigned(z_t a, z_t b) 251 { 252 z_t t; 253 SWAP(a, b, t, used); 254 SWAP(b, a, t, chars); 255 } 256 257 static inline void 258 zsplit_unsigned_fast_large_taint(z_t high, z_t low, z_t a, size_t n) 259 { 260 n >>= LB_BITS_PER_CHAR; 261 high->sign = 1; 262 high->used = a->used - n; 263 high->chars = a->chars + n; 264 #if 0 265 TRIM_AND_ZERO(high); 266 #endif 267 low->sign = 1; 268 low->used = n; 269 low->chars = a->chars; 270 TRIM_AND_ZERO(low); 271 } 272 273 static inline void 274 zsplit_unsigned_fast_small_auto(z_t high, z_t low, z_t a, size_t n) 275 { 276 zahl_char_t mask = 1; 277 mask = (mask << n) - 1; 278 279 high->sign = 1; 280 high->used = 1; 281 high->chars[0] = a->chars[0] >> n; 282 if (a->used == 2) { 283 high->chars[1] = a->chars[1] >> n; 284 high->used += !!high->chars[1]; 285 n = BITS_PER_CHAR - n; 286 high->chars[0] |= (a->chars[1] & mask) << n; 287 } 288 #if 0 289 if (unlikely(!high->chars[high->used - 1])) 290 high->sign = 0; 291 #endif 292 293 low->sign = 1; 294 low->used = 1; 295 low->chars[0] = a->chars[0] & mask; 296 if (unlikely(!low->chars[0])) 297 low->sign = 0; 298 } 299 300 /* Calls to these functions must be called in stack-order 301 * For example, 302 * 303 * zinit_temp(a); 304 * zinit_temp(b); 305 * zfree_temp(b); 306 * zinit_temp(c); 307 * zfree_temp(c); 308 * zfree_temp(a); 309 * 310 * And not (swap the two last lines) 311 * 312 * zinit_temp(a); 313 * zinit_temp(b); 314 * zfree_temp(b); 315 * zinit_temp(c); 316 * zfree_temp(a); 317 * zfree_temp(c); 318 * 319 * { */ 320 321 static inline void 322 zinit_temp(z_t a) 323 { 324 zinit(a); 325 if (unlikely(libzahl_temp_stack_head == libzahl_temp_stack_end)) { 326 size_t n = (size_t)(libzahl_temp_stack_end - libzahl_temp_stack); 327 void* old = libzahl_temp_stack; 328 libzahl_temp_stack = realloc(old, 2 * n * sizeof(*libzahl_temp_stack)); 329 if (check(!libzahl_temp_stack)) { 330 libzahl_temp_stack = old; 331 libzahl_memfailure(); 332 } 333 libzahl_temp_stack_head = libzahl_temp_stack + n; 334 libzahl_temp_stack_end = libzahl_temp_stack_head + n; 335 } 336 *libzahl_temp_stack_head++ = a; 337 } 338 339 static inline void 340 zfree_temp(z_t a) 341 { 342 zfree(a); 343 libzahl_temp_stack_head--; 344 } 345 346 /* } */ 347 348 #define ZMEM_2OP_PRECISE(a, b, c, n, OP) \ 349 do { \ 350 zahl_char_t *a__ = (a); \ 351 const zahl_char_t *b__ = (b); \ 352 const zahl_char_t *c__ = (c); \ 353 size_t i__, n__ = (n); \ 354 if (n__ <= 4) { \ 355 if (n__ >= 1) \ 356 a__[0] = b__[0] OP c__[0]; \ 357 if (n__ >= 2) \ 358 a__[1] = b__[1] OP c__[1]; \ 359 if (n__ >= 3) \ 360 a__[2] = b__[2] OP c__[2]; \ 361 if (n__ >= 4) \ 362 a__[3] = b__[3] OP c__[3]; \ 363 } else { \ 364 for (i__ = 0; (i__ += 4) < n__;) { \ 365 a__[i__ - 1] = b__[i__ - 1] OP c__[i__ - 1]; \ 366 a__[i__ - 2] = b__[i__ - 2] OP c__[i__ - 2]; \ 367 a__[i__ - 3] = b__[i__ - 3] OP c__[i__ - 3]; \ 368 a__[i__ - 4] = b__[i__ - 4] OP c__[i__ - 4]; \ 369 } \ 370 if (i__ > n__) \ 371 for (i__ -= 4; i__ < n__; i__++) \ 372 a__[i__] = b__[i__] OP c__[i__]; \ 373 } \ 374 } while (0) 375 376 #define ZMEM_2OP(a, b, c, n, OP) \ 377 do { \ 378 zahl_char_t *a__ = (a); \ 379 const zahl_char_t *b__ = (b); \ 380 const zahl_char_t *c__ = (c); \ 381 size_t i__, n__ = (n); \ 382 for (i__ = 0; i__ < n__; i__ += 4) { \ 383 a__[i__ + 0] = b__[i__ + 0] OP c__[i__ + 0]; \ 384 a__[i__ + 1] = b__[i__ + 1] OP c__[i__ + 1]; \ 385 a__[i__ + 2] = b__[i__ + 2] OP c__[i__ + 2]; \ 386 a__[i__ + 3] = b__[i__ + 3] OP c__[i__ + 3]; \ 387 } \ 388 } while (0) 389 390 #define ZMEM_1OP(a, b, n, OP) \ 391 do { \ 392 zahl_char_t *a__ = (a); \ 393 const zahl_char_t *b__ = (b); \ 394 size_t i__, n__ = (n); \ 395 for (i__ = 0; i__ < n__; i__ += 4) { \ 396 a__[i__ + 0] = OP(b__[i__ + 0]); \ 397 a__[i__ + 1] = OP(b__[i__ + 1]); \ 398 a__[i__ + 2] = OP(b__[i__ + 2]); \ 399 a__[i__ + 3] = OP(b__[i__ + 3]); \ 400 } \ 401 } while (0)