// Inferno utils/6c/mul.c
// http://code.google.com/p/inferno-os/source/browse/utils/6c/mul.c
//
// Copyright © 1994-1999 Lucent Technologies Inc. All rights reserved.
// Portions Copyright © 1995-1997 C H Forsyth (forsyth@terzarima.net)
// Portions Copyright © 1997-1999 Vita Nuova Limited
// Portions Copyright © 2000-2007 Vita Nuova Holdings Limited (www.vitanuova.com)
// Portions Copyright © 2004,2006 Bruce Ellis
// Portions Copyright © 2005-2007 C H Forsyth (forsyth@terzarima.net)
// Revisions Copyright © 2000-2007 Lucent Technologies Inc. and others
// Portions Copyright © 2009 The Go Authors. All rights reserved.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
#include "gc.h"
typedef struct Malg Malg;
typedef struct Mparam Mparam;
struct Malg
{
schar vals[10];
};
struct Mparam
{
uint32 value;
schar alg;
char neg;
char shift;
char arg;
schar off;
};
static Mparam multab[32];
static int mulptr;
static Malg malgs[] =
{
{0, 100},
{-1, 1, 100},
{-9, -5, -3, 3, 5, 9, 100},
{6, 10, 12, 18, 20, 24, 36, 40, 72, 100},
{-8, -4, -2, 2, 4, 8, 100},
};
/*
* return position of lowest 1
*/
int
lowbit(uint32 v)
{
int s, i;
uint32 m;
s = 0;
m = 0xFFFFFFFFUL;
for(i = 16; i > 0; i >>= 1) {
m >>= i;
if((v & m) == 0) {
v >>= i;
s += i;
}
}
return s;
}
void
genmuladd(Node *d, Node *s, int m, Node *a)
{
Node nod;
nod.op = OINDEX;
nod.left = a;
nod.right = s;
nod.scale = m;
nod.type = types[TIND];
nod.xoffset = 0;
xcom(&nod);
gopcode(OADDR, d->type, &nod, d);
}
void
mulparam(uint32 m, Mparam *mp)
{
int c, i, j, n, o, q, s;
int bc, bi, bn, bo, bq, bs, bt;
schar *p;
int32 u;
uint32 t;
bc = bq = 10;
bi = bn = bo = bs = bt = 0;
for(i = 0; i < nelem(malgs); i++) {
for(p = malgs[i].vals, j = 0; (o = p[j]) < 100; j++)
for(s = 0; s < 2; s++) {
c = 10;
q = 10;
u = m - o;
if(u == 0)
continue;
if(s) {
o = -o;
if(o > 0)
continue;
u = -u;
}
n = lowbit(u);
t = (uint32)u >> n;
switch(i) {
case 0:
if(t == 1) {
c = s + 1;
q = 0;
break;
}
switch(t) {
case 3:
case 5:
case 9:
c = s + 1;
if(n)
c++;
q = 0;
break;
}
if(s)
break;
switch(t) {
case 15:
case 25:
case 27:
case 45:
case 81:
c = 2;
if(n)
c++;
q = 1;
break;
}
break;
case 1:
if(t == 1) {
c = 3;
q = 3;
break;
}
switch(t) {
case 3:
case 5:
case 9:
c = 3;
q = 2;
break;
}
break;
case 2:
if(t == 1) {
c = 3;
q = 2;
break;
}
break;
case 3:
if(s)
break;
if(t == 1) {
c = 3;
q = 1;
break;
}
break;
case 4:
if(t == 1) {
c = 3;
q = 0;
break;
}
break;
}
if(c < bc || (c == bc && q > bq)) {
bc = c;
bi = i;
bn = n;
bo = o;
bq = q;
bs = s;
bt = t;
}
}
}
mp->value = m;
if(bc <= 3) {
mp->alg = bi;
mp->shift = bn;
mp->off = bo;
mp->neg = bs;
mp->arg = bt;
}
else
mp->alg = -1;
}
int
m0(int a)
{
switch(a) {
case -2:
case 2:
return 2;
case -3:
case 3:
return 2;
case -4:
case 4:
return 4;
case -5:
case 5:
return 4;
case 6:
return 2;
case -8:
case 8:
return 8;
case -9:
case 9:
return 8;
case 10:
return 4;
case 12:
return 2;
case 15:
return 2;
case 18:
return 8;
case 20:
return 4;
case 24:
return 2;
case 25:
return 4;
case 27:
return 2;
case 36:
return 8;
case 40:
return 4;
case 45:
return 4;
case 72:
return 8;
case 81:
return 8;
}
diag(Z, "bad m0");
return 0;
}
int
m1(int a)
{
switch(a) {
case 15:
return 4;
case 25:
return 4;
case 27:
return 8;
case 45:
return 8;
case 81:
return 8;
}
diag(Z, "bad m1");
return 0;
}
int
m2(int a)
{
switch(a) {
case 6:
return 2;
case 10:
return 2;
case 12:
return 4;
case 18:
return 2;
case 20:
return 4;
case 24:
return 8;
case 36:
return 4;
case 40:
return 8;
case 72:
return 8;
}
diag(Z, "bad m2");
return 0;
}
void
shiftit(Type *t, Node *s, Node *d)
{
int32 c;
c = (int32)s->vconst & 31;
switch(c) {
case 0:
break;
case 1:
gopcode(OADD, t, d, d);
break;
default:
gopcode(OASHL, t, s, d);
}
}
static int
mulgen1(uint32 v, Node *n)
{
int i, o;
Mparam *p;
Node nod, nods;
for(i = 0; i < nelem(multab); i++) {
p = &multab[i];
if(p->value == v)
goto found;
}
p = &multab[mulptr];
if(++mulptr == nelem(multab))
mulptr = 0;
mulparam(v, p);
found:
// print("v=%.x a=%d n=%d s=%d g=%d o=%d \n", p->value, p->alg, p->neg, p->shift, p->arg, p->off);
if(p->alg < 0)
return 0;
nods = *nodconst(p->shift);
o = OADD;
if(p->alg > 0) {
regalloc(&nod, n, Z);
if(p->off < 0)
o = OSUB;
}
switch(p->alg) {
case 0:
switch(p->arg) {
case 1:
shiftit(n->type, &nods, n);
break;
case 15:
case 25:
case 27:
case 45:
case 81:
genmuladd(n, n, m1(p->arg), n);
/* fall thru */
case 3:
case 5:
case 9:
genmuladd(n, n, m0(p->arg), n);
shiftit(n->type, &nods, n);
break;
default:
goto bad;
}
if(p->neg == 1)
gins(ANEGL, Z, n);
break;
case 1:
switch(p->arg) {
case 1:
gmove(n, &nod);
shiftit(n->type, &nods, &nod);
break;
case 3:
case 5:
case 9:
genmuladd(&nod, n, m0(p->arg), n);
shiftit(n->type, &nods, &nod);
break;
default:
goto bad;
}
if(p->neg)
gopcode(o, n->type, &nod, n);
else {
gopcode(o, n->type, n, &nod);
gmove(&nod, n);
}
break;
case 2:
genmuladd(&nod, n, m0(p->off), n);
shiftit(n->type, &nods, n);
goto comop;
case 3:
genmuladd(&nod, n, m0(p->off), n);
shiftit(n->type, &nods, n);
genmuladd(n, &nod, m2(p->off), n);
break;
case 4:
genmuladd(&nod, n, m0(p->off), nodconst(0));
shiftit(n->type, &nods, n);
goto comop;
default:
diag(Z, "bad mul alg");
break;
comop:
if(p->neg) {
gopcode(o, n->type, n, &nod);
gmove(&nod, n);
}
else
gopcode(o, n->type, &nod, n);
}
if(p->alg > 0)
regfree(&nod);
return 1;
bad:
diag(Z, "mulgen botch");
return 1;
}
void
mulgen(Type *t, Node *r, Node *n)
{
if(!mulgen1(r->vconst, n))
gopcode(OMUL, t, r, n);
}