// 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 %ld\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 %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 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);