sys/src/cmd/8c/div.c

   1 #include "gc.h"
   2
   3 /*
   4  * Based on: Granlund, T.; Montgomery, P.L.
   5  * "Division by Invariant Integers using Multiplication".
   6  * SIGPLAN Notices, Vol. 29, June 1994, page 61.
   7  */
   8
   9 #define TN(n)   ((uvlong)1 << (n))
  10 #define T31     TN(31)
  11 #define T32     TN(32)
  12
  13 int
  14 multiplier(ulong d, int p, uvlong *mp)
  15 {
  16         int l;
  17         uvlong mlo, mhi, tlo, thi;
  18
  19         l = topbit(d - 1) + 1;
  20         mlo = (((TN(l) - d) << 32) / d) + T32;
  21         if(l + p == 64)
  22                 mhi = (((TN(l) + 1 - d) << 32) / d) + T32;
  23         else
  24                 mhi = (TN(32 + l) + TN(32 + l - p)) / d;
  25         assert(mlo < mhi);
  26         while(l > 0) {
  27                 tlo = mlo >> 1;
  28                 thi = mhi >> 1;
  29                 if(tlo == thi)
  30                         break;
  31                 mlo = tlo;
  32                 mhi = thi;
  33                 l--;
  34         }
  35         *mp = mhi;
  36         return l;
  37 }
  38
  39 int
  40 sdiv(ulong d, ulong *mp, int *sp)
  41 {
  42         int s;
  43         uvlong m;
  44
  45         s = multiplier(d, 32 - 1, &m);
  46         *mp = m;
  47         *sp = s;
  48         if(m >= T31)
  49                 return 1;
  50         else
  51                 return 0;
  52 }
  53
  54 int
  55 udiv(ulong d, ulong *mp, int *sp, int *pp)
  56 {
  57         int p, s;
  58         uvlong m;
  59
  60         s = multiplier(d, 32, &m);
  61         p = 0;
  62         if(m >= T32) {
  63                 while((d & 1) == 0) {
  64                         d >>= 1;
  65                         p++;
  66                 }
  67                 s = multiplier(d, 32 - p, &m);
  68         }
  69         *mp = m;
  70         *pp = p;
  71         if(m >= T32) {
  72                 assert(p == 0);
  73                 *sp = s - 1;
  74                 return 1;
  75         }
  76         else {
  77                 *sp = s;
  78                 return 0;
  79         }
  80 }
  81
  82 void
  83 sdivgen(Node *l, Node *r, Node *ax, Node *dx)
  84 {
  85         int a, s;
  86         ulong m;
  87         vlong c;
  88
  89         c = r->vconst;
  90         if(c < 0)
  91                 c = -c;
  92         a = sdiv(c, &m, &s);
  93 //print("a=%d i=%ld s=%d m=%lux\n", a, (long)r->vconst, s, m);
  94         gins(AMOVL, nodconst(m), ax);
  95         gins(AIMULL, l, Z);
  96         gins(AMOVL, l, ax);
  97         if(a)
  98                 gins(AADDL, ax, dx);
  99         gins(ASHRL, nodconst(31), ax);
 100         gins(ASARL, nodconst(s), dx);
 101         gins(AADDL, ax, dx);
 102         if(r->vconst < 0)
 103                 gins(ANEGL, Z, dx);
 104 }
 105
 106 void
 107 udivgen(Node *l, Node *r, Node *ax, Node *dx)
 108 {
 109         int a, s, t;
 110         ulong m;
 111         Node nod;
 112
 113         a = udiv(r->vconst, &m, &s, &t);
 114 //print("a=%ud i=%ld p=%d s=%d m=%lux\n", a, (long)r->vconst, t, s, m);
 115         if(t != 0) {
 116                 gins(AMOVL, l, ax);
 117                 gins(ASHRL, nodconst(t), ax);
 118                 gins(AMOVL, nodconst(m), dx);
 119                 gins(AMULL, dx, Z);
 120         }
 121         else if(a) {
 122                 if(l->op != OREGISTER) {
 123                         regalloc(&nod, l, Z);
 124                         gins(AMOVL, l, &nod);
 125                         l = &nod;
 126                 }
 127                 gins(AMOVL, nodconst(m), ax);
 128                 gins(AMULL, l, Z);
 129                 gins(AADDL, l, dx);
 130                 gins(ARCRL, nodconst(1), dx);
 131                 if(l == &nod)
 132                         regfree(l);
 133         }
 134         else {
 135                 gins(AMOVL, nodconst(m), ax);
 136                 gins(AMULL, l, Z);
 137         }
 138         if(s != 0)
 139                 gins(ASHRL, nodconst(s), dx);
 140 }
 141
 142 void
 143 sext(Node *d, Node *s, Node *l)
 144 {
 145         if(s->reg == D_AX && !nodreg(d, Z, D_DX)) {
 146                 reg[D_DX]++;
 147                 gins(ACDQ, Z, Z);
 148         }
 149         else {
 150                 regalloc(d, l, Z);
 151                 gins(AMOVL, s, d);
 152                 gins(ASARL, nodconst(31), d);
 153         }
 154 }
 155
 156 void
 157 sdiv2(long c, int v, Node *l, Node *n)
 158 {
 159         Node nod;
 160
 161         if(v > 0) {
 162                 if(v > 1) {
 163                         sext(&nod, n, l);
 164                         gins(AANDL, nodconst((1 << v) - 1), &nod);
 165                         gins(AADDL, &nod, n);
 166                         regfree(&nod);
 167                 }
 168                 else {
 169                         gins(ACMPL, n, nodconst(0x80000000));
 170                         gins(ASBBL, nodconst(-1), n);
 171                 }
 172                 gins(ASARL, nodconst(v), n);
 173         }
 174         if(c < 0)
 175                 gins(ANEGL, Z, n);
 176 }
 177
 178 void
 179 smod2(long c, int v, Node *l, Node *n)
 180 {
 181         Node nod;
 182
 183         if(c == 1) {
 184                 zeroregm(n);
 185                 return;
 186         }
 187
 188         sext(&nod, n, l);
 189         if(v == 0) {
 190                 zeroregm(n);
 191                 gins(AXORL, &nod, n);
 192                 gins(ASUBL, &nod, n);
 193         }
 194         else if(v > 1) {
 195                 gins(AANDL, nodconst((1 << v) - 1), &nod);
 196                 gins(AADDL, &nod, n);
 197                 gins(AANDL, nodconst((1 << v) - 1), n);
 198                 gins(ASUBL, &nod, n);
 199         }
 200         else {
 201                 gins(AANDL, nodconst(1), n);
 202                 gins(AXORL, &nod, n);
 203                 gins(ASUBL, &nod, n);
 204         }
 205         regfree(&nod);
 206 }