// Inferno utils/5c/mul.c
// http://code.google.com/p/inferno-os/source/browse/utils/5c/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"
/*
* code sequences for multiply by constant.
* [a-l][0-3]
* lsl $(A-'a'),r0,r1
* [+][0-7]
* add r0,r1,r2
* [-][0-7]
* sub r0,r1,r2
*/
static int maxmulops = 3; /* max # of ops to replace mul with */
static int multabp;
static int32 mulval;
static char* mulcp;
static int32 valmax;
static int shmax;
static int docode(char *hp, char *cp, int r0, int r1);
static int gen1(int len);
static int gen2(int len, int32 r1);
static int gen3(int len, int32 r0, int32 r1, int flag);
enum
{
SR1 = 1<<0, /* r1 has been shifted */
SR0 = 1<<1, /* r0 has been shifted */
UR1 = 1<<2, /* r1 has not been used */
UR0 = 1<<3, /* r0 has not been used */
};
Multab*
mulcon0(int32 v)
{
int a1, a2, g;
Multab *m, *m1;
char hint[10];
if(v < 0)
v = -v;
/*
* look in cache
*/
m = multab;
for(g=0; g<nelem(multab); g++) {
if(m->val == v) {
if(m->code[0] == 0)
return 0;
return m;
}
m++;
}
/*
* select a spot in cache to overwrite
*/
multabp++;
if(multabp < 0 || multabp >= nelem(multab))
multabp = 0;
m = multab+multabp;
m->val = v;
mulval = v;
/*
* look in execption hint table
*/
a1 = 0;
a2 = hintabsize;
for(;;) {
if(a1 >= a2)
goto no;
g = (a2 + a1)/2;
if(v < hintab[g].val) {
a2 = g;
continue;
}
if(v > hintab[g].val) {
a1 = g+1;
continue;
}
break;
}
if(docode(hintab[g].hint, m->code, 1, 0))
return m;
print("multiply table failure %d\n", v);
m->code[0] = 0;
return 0;
no:
/*
* try to search
*/
hint[0] = 0;
for(g=1; g<=maxmulops; g++) {
if(g >= maxmulops && v >= 65535)
break;
mulcp = hint+g;
*mulcp = 0;
if(gen1(g)) {
if(docode(hint, m->code, 1, 0))
return m;
print("multiply table failure %d\n", v);
break;
}
}
/*
* try a recur followed by a shift
*/
g = 0;
while(!(v & 1)) {
g++;
v >>= 1;
}
if(g) {
m1 = mulcon0(v);
if(m1) {
strcpy(m->code, m1->code);
sprint(strchr(m->code, 0), "%c0", g+'a');
return m;
}
}
m->code[0] = 0;
return 0;
}
static int
docode(char *hp, char *cp, int r0, int r1)
{
int c, i;
c = *hp++;
*cp = c;
cp += 2;
switch(c) {
default:
c -= 'a';
if(c < 1 || c >= 30)
break;
for(i=0; i<4; i++) {
switch(i) {
case 0:
if(docode(hp, cp, r0<<c, r1))
goto out;
break;
case 1:
if(docode(hp, cp, r1<<c, r1))
goto out;
break;
case 2:
if(docode(hp, cp, r0, r0<<c))
goto out;
break;
case 3:
if(docode(hp, cp, r0, r1<<c))
goto out;
break;
}
}
break;
case '+':
for(i=0; i<8; i++) {
cp[-1] = i+'0';
switch(i) {
case 1:
if(docode(hp, cp, r0+r1, r1))
goto out;
break;
case 5:
if(docode(hp, cp, r0, r0+r1))
goto out;
break;
}
}
break;
case '-':
for(i=0; i<8; i++) {
cp[-1] = i+'0';
switch(i) {
case 1:
if(docode(hp, cp, r0-r1, r1))
goto out;
break;
case 2:
if(docode(hp, cp, r1-r0, r1))
goto out;
break;
case 5:
if(docode(hp, cp, r0, r0-r1))
goto out;
break;
case 6:
if(docode(hp, cp, r0, r1-r0))
goto out;
break;
}
}
break;
case 0:
if(r0 == mulval)
return 1;
}
return 0;
out:
cp[-1] = i+'0';
return 1;
}
static int
gen1(int len)
{
int i;
for(shmax=1; shmax<30; shmax++) {
valmax = 1<<shmax;
if(valmax >= mulval)
break;
}
if(mulval == 1)
return 1;
len--;
for(i=1; i<=shmax; i++)
if(gen2(len, 1<<i)) {
*--mulcp = 'a'+i;
return 1;
}
return 0;
}
static int
gen2(int len, int32 r1)
{
int i;
if(len <= 0) {
if(r1 == mulval)
return 1;
return 0;
}
len--;
if(len == 0)
goto calcr0;
if(gen3(len, r1, r1+1, UR1)) {
i = '+';
goto out;
}
if(gen3(len, r1-1, r1, UR0)) {
i = '-';
goto out;
}
if(gen3(len, 1, r1+1, UR1)) {
i = '+';
goto out;
}
if(gen3(len, 1, r1-1, UR1)) {
i = '-';
goto out;
}
return 0;
calcr0:
if(mulval == r1+1) {
i = '+';
goto out;
}
if(mulval == r1-1) {
i = '-';
goto out;
}
return 0;
out:
*--mulcp = i;
return 1;
}
static int
gen3(int len, int32 r0, int32 r1, int flag)
{
int i, f1, f2;
int32 x;
if(r0 <= 0 ||
r0 >= r1 ||
r1 > valmax)
return 0;
len--;
if(len == 0)
goto calcr0;
if(!(flag & UR1)) {
f1 = UR1|SR1;
for(i=1; i<=shmax; i++) {
x = r0<<i;
if(x > valmax)
break;
if(gen3(len, r0, x, f1)) {
i += 'a';
goto out;
}
}
}
if(!(flag & UR0)) {
f1 = UR1|SR1;
for(i=1; i<=shmax; i++) {
x = r1<<i;
if(x > valmax)
break;
if(gen3(len, r1, x, f1)) {
i += 'a';
goto out;
}
}
}
if(!(flag & SR1)) {
f1 = UR1|SR1|(flag&UR0);
for(i=1; i<=shmax; i++) {
x = r1<<i;
if(x > valmax)
break;
if(gen3(len, r0, x, f1)) {
i += 'a';
goto out;
}
}
}
if(!(flag & SR0)) {
f1 = UR0|SR0|(flag&(SR1|UR1));
f2 = UR1|SR1;
if(flag & UR1)
f2 |= UR0;
if(flag & SR1)
f2 |= SR0;
for(i=1; i<=shmax; i++) {
x = r0<<i;
if(x > valmax)
break;
if(x > r1) {
if(gen3(len, r1, x, f2)) {
i += 'a';
goto out;
}
} else
if(gen3(len, x, r1, f1)) {
i += 'a';
goto out;
}
}
}
x = r1+r0;
if(gen3(len, r0, x, UR1)) {
i = '+';
goto out;
}
if(gen3(len, r1, x, UR1)) {
i = '+';
goto out;
}
x = r1-r0;
if(gen3(len, x, r1, UR0)) {
i = '-';
goto out;
}
if(x > r0) {
if(gen3(len, r0, x, UR1)) {
i = '-';
goto out;
}
} else
if(gen3(len, x, r0, UR0)) {
i = '-';
goto out;
}
return 0;
calcr0:
f1 = flag & (UR0|UR1);
if(f1 == UR1) {
for(i=1; i<=shmax; i++) {
x = r1<<i;
if(x >= mulval) {
if(x == mulval) {
i += 'a';
goto out;
}
break;
}
}
}
if(mulval == r1+r0) {
i = '+';
goto out;
}
if(mulval == r1-r0) {
i = '-';
goto out;
}
return 0;
out:
*--mulcp = i;
return 1;
}
/*
* hint table has numbers that
* the search algorithm fails on.
* <1000:
* all numbers
* <5000:
* ÷ by 5
* <10000:
* ÷ by 50
* <65536:
* ÷ by 250
*/
Hintab hintab[] =
{
683, "b++d+e+",
687, "b+e++e-",
691, "b++d+e+",
731, "b++d+e+",
811, "b++d+i+",
821, "b++e+e+",
843, "b+d++e+",
851, "b+f-+e-",
853, "b++e+e+",
877, "c++++g-",
933, "b+c++g-",
981, "c-+e-d+",
1375, "b+c+b+h-",
1675, "d+b++h+",
2425, "c++f-e+",
2675, "c+d++f-",
2750, "b+d-b+h-",
2775, "c-+g-e-",
3125, "b++e+g+",
3275, "b+c+g+e+",
3350, "c++++i+",
3475, "c-+e-f-",
3525, "c-+d+g-",
3625, "c-+e-j+",
3675, "b+d+d+e+",
3725, "b+d-+h+",
3925, "b+d+f-d-",
4275, "b+g++e+",
4325, "b+h-+d+",
4425, "b+b+g-j-",
4525, "b+d-d+f+",
4675, "c++d-g+",
4775, "b+d+b+g-",
4825, "c+c-+i-",
4850, "c++++i-",
4925, "b++e-g-",
4975, "c+f++e-",
5500, "b+g-c+d+",
6700, "d+b++i+",
9700, "d++++j-",
11000, "b+f-c-h-",
11750, "b+d+g+j-",
12500, "b+c+e-k+",
13250, "b+d+e-f+",
13750, "b+h-c-d+",
14250, "b+g-c+e-",
14500, "c+f+j-d-",
14750, "d-g--f+",
16750, "b+e-d-n+",
17750, "c+h-b+e+",
18250, "d+b+h-d+",
18750, "b+g-++f+",
19250, "b+e+b+h+",
19750, "b++h--f-",
20250, "b+e-l-c+",
20750, "c++bi+e-",
21250, "b+i+l+c+",
22000, "b+e+d-g-",
22250, "b+d-h+k-",
22750, "b+d-e-g+",
23250, "b+c+h+e-",
23500, "b+g-c-g-",
23750, "b+g-b+h-",
24250, "c++g+m-",
24750, "b+e+e+j-",
25000, "b++dh+g+",
25250, "b+e+d-g-",
25750, "b+e+b+j+",
26250, "b+h+c+e+",
26500, "b+h+c+g+",
26750, "b+d+e+g-",
27250, "b+e+e+f+",
27500, "c-i-c-d+",
27750, "b+bd++j+",
28250, "d-d-++i-",
28500, "c+c-h-e-",
29000, "b+g-d-f+",
29500, "c+h+++e-",
29750, "b+g+f-c+",
30250, "b+f-g-c+",
33500, "c-f-d-n+",
33750, "b+d-b+j-",
34250, "c+e+++i+",
35250, "e+b+d+k+",
35500, "c+e+d-g-",
35750, "c+i-++e+",
36250, "b+bh-d+e+",
36500, "c+c-h-e-",
36750, "d+e--i+",
37250, "b+g+g+b+",
37500, "b+h-b+f+",
37750, "c+be++j-",
38500, "b+e+b+i+",
38750, "d+i-b+d+",
39250, "b+g-l-+d+",
39500, "b+g-c+g-",
39750, "b+bh-c+f-",
40250, "b+bf+d+g-",
40500, "b+g-c+g+",
40750, "c+b+i-e+",
41250, "d++bf+h+",
41500, "b+j+c+d-",
41750, "c+f+b+h-",
42500, "c+h++g+",
42750, "b+g+d-f-",
43250, "b+l-e+d-",
43750, "c+bd+h+f-",
44000, "b+f+g-d-",
44250, "b+d-g--f+",
44500, "c+e+c+h+",
44750, "b+e+d-h-",
45250, "b++g+j-g+",
45500, "c+d+e-g+",
45750, "b+d-h-e-",
46250, "c+bd++j+",
46500, "b+d-c-j-",
46750, "e-e-b+g-",
47000, "b+c+d-j-",
47250, "b+e+e-g-",
47500, "b+g-c-h-",
47750, "b+f-c+h-",
48250, "d--h+n-",
48500, "b+c-g+m-",
48750, "b+e+e-g+",
49500, "c-f+e+j-",
49750, "c+c+g++f-",
50000, "b+e+e+k+",
50250, "b++i++g+",
50500, "c+g+f-i+",
50750, "b+e+d+k-",
51500, "b+i+c-f+",
51750, "b+bd+g-e-",
52250, "b+d+g-j+",
52500, "c+c+f+g+",
52750, "b+c+e+i+",
53000, "b+i+c+g+",
53500, "c+g+g-n+",
53750, "b+j+d-c+",
54250, "b+d-g-j-",
54500, "c-f+e+f+",
54750, "b+f-+c+g+",
55000, "b+g-d-g-",
55250, "b+e+e+g+",
55500, "b+cd++j+",
55750, "b+bh-d-f-",
56250, "c+d-b+j-",
56500, "c+d+c+i+",
56750, "b+e+d++h-",
57000, "b+d+g-f+",
57250, "b+f-m+d-",
57750, "b+i+c+e-",
58000, "b+e+d+h+",
58250, "c+b+g+g+",
58750, "d-e-j--e+",
59000, "d-i-+e+",
59250, "e--h-m+",
59500, "c+c-h+f-",
59750, "b+bh-e+i-",
60250, "b+bh-e-e-",
60500, "c+c-g-g-",
60750, "b+e-l-e-",
61250, "b+g-g-c+",
61750, "b+g-c+g+",
62250, "f--+c-i-",
62750, "e+f--+g+",
64750, "b+f+d+p-",
};
int hintabsize = nelem(hintab);