libzahl

big integer library
git clone git://git.suckless.org/libzahl
Log | Files | Refs | README | LICENSE

zdivmod.c (1979B)

      1 /* See LICENSE file for copyright and license details. */
      2 #include "internals.h"
      3 
      4 #define ta          libzahl_tmp_divmod_a
      5 #define tb          libzahl_tmp_divmod_b
      6 #define td          libzahl_tmp_divmod_d
      7 #define tds_proper  libzahl_tmp_divmod_ds
      8 
      9 
     10 static inline void
     11 zdivmod_impl(z_t a, z_t b, z_t c, z_t d)
     12 {
     13 	size_t c_bits, d_bits, bit, i;
     14 	static z_t tds[BITS_PER_CHAR];
     15 
     16 	c_bits = zbits(c);
     17 	d_bits = zbits(d);
     18 
     19 	bit = c_bits - d_bits;
     20 	zlsh(td, d, bit);
     21 	SET_SIGNUM(td, 1);
     22 	if (zcmpmag(td, c) > 0) {
     23 		zrsh(td, td, 1);
     24 		bit -= 1;
     25 	}
     26 
     27 	SET_SIGNUM(ta, 0);
     28 	zabs(tb, c);
     29 
     30 	if (unlikely(bit <= BITS_PER_CHAR)) {
     31 		for (;;) {
     32 			if (zcmpmag(td, tb) <= 0) {
     33 				zsub_unsigned(tb, tb, td);
     34 				zbset(ta, ta, bit, 1);
     35 			}
     36 			if (!bit-- || zzero(tb))
     37 				goto done;
     38 			zrsh(td, td, 1);
     39 		}
     40 	} else {
     41 		for (i = 0; i < BITS_PER_CHAR; i++) {
     42 			zrsh(tds_proper[i], td, i);
     43 			tds[i]->used = tds_proper[i]->used;
     44 			tds[i]->sign = tds_proper[i]->sign;
     45 			tds[i]->chars = tds_proper[i]->chars;
     46 		}
     47 		for (;;) {
     48 			for (i = 0; i < BITS_PER_CHAR; i++) {
     49 				if (zcmpmag(tds[i], tb) <= 0) {
     50 					zsub_unsigned(tb, tb, tds[i]);
     51 					zbset(ta, ta, bit, 1);
     52 				}
     53 				if (!bit-- || zzero(tb))
     54 					goto done;
     55 			}
     56 			for (i = MIN(bit, BITS_PER_CHAR - 1) + 1; i--;)
     57 				zrsh_taint(tds[i], BITS_PER_CHAR);
     58 		}
     59 	}
     60 done:
     61 
     62 	zswap(a, ta);
     63 	zswap(b, tb);
     64 }
     65 
     66 
     67 void
     68 zdivmod(z_t a, z_t b, z_t c, z_t d)
     69 {
     70 	int c_sign, sign, cmpmag;
     71 
     72 	c_sign = zsignum(c);
     73 	sign = c_sign * zsignum(d);
     74 
     75 	if (unlikely(!sign)) {
     76 		if (check(!zzero(c))) {
     77 			libzahl_failure(-ZERROR_DIV_0);
     78 		} else if (check(zzero(d))) {
     79 			libzahl_failure(-ZERROR_0_DIV_0);
     80 		} else {
     81 			SET_SIGNUM(a, 0);
     82 			SET_SIGNUM(b, 0);
     83 		}
     84 		return;
     85 	} else if (cmpmag = zcmpmag(c, d), unlikely(cmpmag <= 0)) {
     86 		if (unlikely(cmpmag == 0)) {
     87 			zseti(a, sign);
     88 			SET_SIGNUM(b, 0);
     89 		} else {
     90 			SET(b, c);
     91 			SET_SIGNUM(a, 0);
     92 		}
     93 		return;
     94 	}
     95 
     96 	zdivmod_impl(a, b, c, d);
     97 	SET_SIGNUM(a, sign);
     98 	if (zsignum(b) > 0)
     99 		SET_SIGNUM(b, c_sign);
    100 }