/*  * This file is part of the UCB release of Plan 9. It is subject to the license * terms in the LICENSE file found in the top-level directory of this * distribution and at http://akaros.cs.berkeley.edu/files/Plan9License. No * part of the UCB release of Plan 9, including this file, may be copied, * modified, propagated, or distributed except according to the terms contained * in the LICENSE file. */ #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	multabp;static	long	mulval;static	char*	mulcp;static	long	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, long r1);static int	gen3(int len, long r0, long 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(long 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 %ld\n", v);	m->code[0] = 0;	return 0; no:	/*	 * try to search	 */	hint[0] = 0;	for(g=1; g<=6; g++) {		if(g >= 6 && v >= 65535)			break;		mulcp = hint+g;		*mulcp = 0;		if(gen1(g)) {			if(docode(hint, m->code, 1, 0))				return m;			print("multiply table failure %ld\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 intdocode(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 intgen1(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 intgen2(int len, long 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 intgen3(int len, long r0, long r1, int flag){	int i, f1, f2;	long 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+",

Lines 1–500 of 617. Load more