zdivmod.c - libzahl - big integer library
 (HTM) git clone git://git.suckless.org/libzahl
 (DIR) Log
 (DIR) Files
 (DIR) Refs
 (DIR) README
 (DIR) 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 }