GopherProxy

	internals.h - libzahl - big integer library
	git clone git://git.suckless.org/libzahl
	Log
	Files
	Refs
	README
	LICENSE
	---
	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 …
	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, …
	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, …
	101 #define MIN_MAX_2(min, max, a, b) ((min) = (a) + (b) - ((max) = MAX(a…
	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…
	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 …
	168 # define libzahl_msb_nz_llu(x) (8 * sizeof(unsigned long long int)…
	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,…
	190 # else
	191 # define libzahl_add_overflow(rp, a, b) __builtin_uaddll_overflow(a, b…
	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 …
	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_tem…
	327 void* old = libzahl_temp_stack;
	328 libzahl_temp_stack = realloc(old, 2 * n * sizeof(*libzah…
	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__ -…
	366 a__[i__ - 2] = b__[i__ - 2] OP c__[i__ -…
	367 a__[i__ - 3] = b__[i__ - 3] OP c__[i__ -…
	368 a__[i__ - 4] = b__[i__ - 4] OP c__[i__ -…
	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)