diff options
Diffstat (limited to 'src/cmd/5c/mul.c')
| -rw-r--r-- | src/cmd/5c/mul.c | 640 |
1 files changed, 0 insertions, 640 deletions
diff --git a/src/cmd/5c/mul.c b/src/cmd/5c/mul.c deleted file mode 100644 index ff50c4845..000000000 --- a/src/cmd/5c/mul.c +++ /dev/null @@ -1,640 +0,0 @@ -// 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); |