xref: /inferno-os/utils/ic/mul.c (revision e5242bb522d11e83d4ae2e9dab758ec8433940d7) 
1  #include "gc.h"
2  
3  /*
4   * code sequences for multiply by constant.
5   * [a-l][0-3]
6   *	lsl	$(A-'a'),r0,r1
7   * [+][0-7]
8   *	add	r0,r1,r2
9   * [-][0-7]
10   *	sub	r0,r1,r2
11   */
12  
13  static	int	multabp;
14  static	long	mulval;
15  static	char*	mulcp;
16  static	long	valmax;
17  static	int	shmax;
18  
19  static int	docode(char *hp, char *cp, int r0, int r1);
20  static int	gen1(int len);
21  static int	gen2(int len, long r1);
22  static int	gen3(int len, long r0, long r1, int flag);
23  enum
24  {
25  	SR1	= 1<<0,		/* r1 has been shifted */
26  	SR0	= 1<<1,		/* r0 has been shifted */
27  	UR1	= 1<<2,		/* r1 has not been used */
28  	UR0	= 1<<3,		/* r0 has not been used */
29  };
30  
31  Multab*
32  mulcon0(long v)
33  {
34  	int a1, a2, g;
35  	Multab *m, *m1;
36  	char hint[10];
37  
38  	if(v < 0)
39  		v = -v;
40  
41  	/*
42  	 * look in cache
43  	 */
44  	m = multab;
45  	for(g=0; g<nelem(multab); g++) {
46  		if(m->val == v) {
47  			if(m->code[0] == 0)
48  				return 0;
49  			return m;
50  		}
51  		m++;
52  	}
53  
54  	/*
55  	 * select a spot in cache to overwrite
56  	 */
57  	multabp++;
58  	if(multabp < 0 || multabp >= nelem(multab))
59  		multabp = 0;
60  	m = multab+multabp;
61  	m->val = v;
62  	mulval = v;
63  
64  	/*
65  	 * look in execption hint table
66  	 */
67  	a1 = 0;
68  	a2 = hintabsize;
69  	for(;;) {
70  		if(a1 >= a2)
71  			goto no;
72  		g = (a2 + a1)/2;
73  		if(v < hintab[g].val) {
74  			a2 = g;
75  			continue;
76  		}
77  		if(v > hintab[g].val) {
78  			a1 = g+1;
79  			continue;
80  		}
81  		break;
82  	}
83  
84  	if(docode(hintab[g].hint, m->code, 1, 0))
85  		return m;
86  	print("multiply table failure %ld\n", v);
87  	m->code[0] = 0;
88  	return 0;
89  
90  no:
91  	/*
92  	 * try to search
93  	 */
94  	hint[0] = 0;
95  	for(g=1; g<=6; g++) {
96  		if(g >= 6 && v >= 65535)
97  			break;
98  		mulcp = hint+g;
99  		*mulcp = 0;
100  		if(gen1(g)) {
101  			if(docode(hint, m->code, 1, 0))
102  				return m;
103  			print("multiply table failure %ld\n", v);
104  			break;
105  		}
106  	}
107  
108  	/*
109  	 * try a recur followed by a shift
110  	 */
111  	g = 0;
112  	while(!(v & 1)) {
113  		g++;
114  		v >>= 1;
115  	}
116  	if(g) {
117  		m1 = mulcon0(v);
118  		if(m1) {
119  			strcpy(m->code, m1->code);
120  			sprint(strchr(m->code, 0), "%c0", g+'a');
121  			return m;
122  		}
123  	}
124  	m->code[0] = 0;
125  	return 0;
126  }
127  
128  static int
129  docode(char *hp, char *cp, int r0, int r1)
130  {
131  	int c, i;
132  
133  	c = *hp++;
134  	*cp = c;
135  	cp += 2;
136  	switch(c) {
137  	default:
138  		c -= 'a';
139  		if(c < 1 || c >= 30)
140  			break;
141  		for(i=0; i<4; i++) {
142  			switch(i) {
143  			case 0:
144  				if(docode(hp, cp, r0<<c, r1))
145  					goto out;
146  				break;
147  			case 1:
148  				if(docode(hp, cp, r1<<c, r1))
149  					goto out;
150  				break;
151  			case 2:
152  				if(docode(hp, cp, r0, r0<<c))
153  					goto out;
154  				break;
155  			case 3:
156  				if(docode(hp, cp, r0, r1<<c))
157  					goto out;
158  				break;
159  			}
160  		}
161  		break;
162  
163  	case '+':
164  		for(i=0; i<8; i++) {
165  			cp[-1] = i+'0';
166  			switch(i) {
167  			case 1:
168  				if(docode(hp, cp, r0+r1, r1))
169  					goto out;
170  				break;
171  			case 5:
172  				if(docode(hp, cp, r0, r0+r1))
173  					goto out;
174  				break;
175  			}
176  		}
177  		break;
178  
179  	case '-':
180  		for(i=0; i<8; i++) {
181  			cp[-1] = i+'0';
182  			switch(i) {
183  			case 1:
184  				if(docode(hp, cp, r0-r1, r1))
185  					goto out;
186  				break;
187  			case 2:
188  				if(docode(hp, cp, r1-r0, r1))
189  					goto out;
190  				break;
191  			case 5:
192  				if(docode(hp, cp, r0, r0-r1))
193  					goto out;
194  				break;
195  			case 6:
196  				if(docode(hp, cp, r0, r1-r0))
197  					goto out;
198  				break;
199  			}
200  		}
201  		break;
202  
203  	case 0:
204  		if(r0 == mulval)
205  			return 1;
206  	}
207  	return 0;
208  
209  out:
210  	cp[-1] = i+'0';
211  	return 1;
212  }
213  
214  static int
215  gen1(int len)
216  {
217  	int i;
218  
219  	for(shmax=1; shmax<30; shmax++) {
220  		valmax = 1<<shmax;
221  		if(valmax >= mulval)
222  			break;
223  	}
224  	if(mulval == 1)
225  		return 1;
226  
227  	len--;
228  	for(i=1; i<=shmax; i++)
229  		if(gen2(len, 1<<i)) {
230  			*--mulcp = 'a'+i;
231  			return 1;
232  		}
233  	return 0;
234  }
235  
236  static int
237  gen2(int len, long r1)
238  {
239  	int i;
240  
241  	if(len <= 0) {
242  		if(r1 == mulval)
243  			return 1;
244  		return 0;
245  	}
246  
247  	len--;
248  	if(len == 0)
249  		goto calcr0;
250  
251  	if(gen3(len, r1, r1+1, UR1)) {
252  		i = '+';
253  		goto out;
254  	}
255  	if(gen3(len, r1-1, r1, UR0)) {
256  		i = '-';
257  		goto out;
258  	}
259  	if(gen3(len, 1, r1+1, UR1)) {
260  		i = '+';
261  		goto out;
262  	}
263  	if(gen3(len, 1, r1-1, UR1)) {
264  		i = '-';
265  		goto out;
266  	}
267  
268  	return 0;
269  
270  calcr0:
271  	if(mulval == r1+1) {
272  		i = '+';
273  		goto out;
274  	}
275  	if(mulval == r1-1) {
276  		i = '-';
277  		goto out;
278  	}
279  	return 0;
280  
281  out:
282  	*--mulcp = i;
283  	return 1;
284  }
285  
286  static int
287  gen3(int len, long r0, long r1, int flag)
288  {
289  	int i, f1, f2;
290  	long x;
291  
292  	if(r0 <= 0 ||
293  	   r0 >= r1 ||
294  	   r1 > valmax)
295  		return 0;
296  
297  	len--;
298  	if(len == 0)
299  		goto calcr0;
300  
301  	if(!(flag & UR1)) {
302  		f1 = UR1|SR1;
303  		for(i=1; i<=shmax; i++) {
304  			x = r0<<i;
305  			if(x > valmax)
306  				break;
307  			if(gen3(len, r0, x, f1)) {
308  				i += 'a';
309  				goto out;
310  			}
311  		}
312  	}
313  
314  	if(!(flag & UR0)) {
315  		f1 = UR1|SR1;
316  		for(i=1; i<=shmax; i++) {
317  			x = r1<<i;
318  			if(x > valmax)
319  				break;
320  			if(gen3(len, r1, x, f1)) {
321  				i += 'a';
322  				goto out;
323  			}
324  		}
325  	}
326  
327  	if(!(flag & SR1)) {
328  		f1 = UR1|SR1|(flag&UR0);
329  		for(i=1; i<=shmax; i++) {
330  			x = r1<<i;
331  			if(x > valmax)
332  				break;
333  			if(gen3(len, r0, x, f1)) {
334  				i += 'a';
335  				goto out;
336  			}
337  		}
338  	}
339  
340  	if(!(flag & SR0)) {
341  		f1 = UR0|SR0|(flag&(SR1|UR1));
342  
343  		f2 = UR1|SR1;
344  		if(flag & UR1)
345  			f2 |= UR0;
346  		if(flag & SR1)
347  			f2 |= SR0;
348  
349  		for(i=1; i<=shmax; i++) {
350  			x = r0<<i;
351  			if(x > valmax)
352  				break;
353  			if(x > r1) {
354  				if(gen3(len, r1, x, f2)) {
355  					i += 'a';
356  					goto out;
357  				}
358  			} else
359  				if(gen3(len, x, r1, f1)) {
360  					i += 'a';
361  					goto out;
362  				}
363  		}
364  	}
365  
366  	x = r1+r0;
367  	if(gen3(len, r0, x, UR1)) {
368  		i = '+';
369  		goto out;
370  	}
371  
372  	if(gen3(len, r1, x, UR1)) {
373  		i = '+';
374  		goto out;
375  	}
376  
377  	x = r1-r0;
378  	if(gen3(len, x, r1, UR0)) {
379  		i = '-';
380  		goto out;
381  	}
382  
383  	if(x > r0) {
384  		if(gen3(len, r0, x, UR1)) {
385  			i = '-';
386  			goto out;
387  		}
388  	} else
389  		if(gen3(len, x, r0, UR0)) {
390  			i = '-';
391  			goto out;
392  		}
393  
394  	return 0;
395  
396  calcr0:
397  	f1 = flag & (UR0|UR1);
398  	if(f1 == UR1) {
399  		for(i=1; i<=shmax; i++) {
400  			x = r1<<i;
401  			if(x >= mulval) {
402  				if(x == mulval) {
403  					i += 'a';
404  					goto out;
405  				}
406  				break;
407  			}
408  		}
409  	}
410  
411  	if(mulval == r1+r0) {
412  		i = '+';
413  		goto out;
414  	}
415  	if(mulval == r1-r0) {
416  		i = '-';
417  		goto out;
418  	}
419  
420  	return 0;
421  
422  out:
423  	*--mulcp = i;
424  	return 1;
425  }
426  
427  /*
428   * hint table has numbers that
429   * the search algorithm fails on.
430   * <1000:
431   *	all numbers
432   * <5000:
433   * 	÷ by 5
434   * <10000:
435   * 	÷ by 50
436   * <65536:
437   * 	÷ by 250
438   */
439  Hintab	hintab[] =
440  {
441  	683,	"b++d+e+",
442  	687,	"b+e++e-",
443  	691,	"b++d+e+",
444  	731,	"b++d+e+",
445  	811,	"b++d+i+",
446  	821,	"b++e+e+",
447  	843,	"b+d++e+",
448  	851,	"b+f-+e-",
449  	853,	"b++e+e+",
450  	877,	"c++++g-",
451  	933,	"b+c++g-",
452  	981,	"c-+e-d+",
453  	1375,	"b+c+b+h-",
454  	1675,	"d+b++h+",
455  	2425,	"c++f-e+",
456  	2675,	"c+d++f-",
457  	2750,	"b+d-b+h-",
458  	2775,	"c-+g-e-",
459  	3125,	"b++e+g+",
460  	3275,	"b+c+g+e+",
461  	3350,	"c++++i+",
462  	3475,	"c-+e-f-",
463  	3525,	"c-+d+g-",
464  	3625,	"c-+e-j+",
465  	3675,	"b+d+d+e+",
466  	3725,	"b+d-+h+",
467  	3925,	"b+d+f-d-",
468  	4275,	"b+g++e+",
469  	4325,	"b+h-+d+",
470  	4425,	"b+b+g-j-",
471  	4525,	"b+d-d+f+",
472  	4675,	"c++d-g+",
473  	4775,	"b+d+b+g-",
474  	4825,	"c+c-+i-",
475  	4850,	"c++++i-",
476  	4925,	"b++e-g-",
477  	4975,	"c+f++e-",
478  	5500,	"b+g-c+d+",
479  	6700,	"d+b++i+",
480  	9700,	"d++++j-",
481  	11000,	"b+f-c-h-",
482  	11750,	"b+d+g+j-",
483  	12500,	"b+c+e-k+",
484  	13250,	"b+d+e-f+",
485  	13750,	"b+h-c-d+",
486  	14250,	"b+g-c+e-",
487  	14500,	"c+f+j-d-",
488  	14750,	"d-g--f+",
489  	16750,	"b+e-d-n+",
490  	17750,	"c+h-b+e+",
491  	18250,	"d+b+h-d+",
492  	18750,	"b+g-++f+",
493  	19250,	"b+e+b+h+",
494  	19750,	"b++h--f-",
495  	20250,	"b+e-l-c+",
496  	20750,	"c++bi+e-",
497  	21250,	"b+i+l+c+",
498  	22000,	"b+e+d-g-",
499  	22250,	"b+d-h+k-",
500  	22750,	"b+d-e-g+",
501  	23250,	"b+c+h+e-",
502  	23500,	"b+g-c-g-",
503  	23750,	"b+g-b+h-",
504  	24250,	"c++g+m-",
505  	24750,	"b+e+e+j-",
506  	25000,	"b++dh+g+",
507  	25250,	"b+e+d-g-",
508  	25750,	"b+e+b+j+",
509  	26250,	"b+h+c+e+",
510  	26500,	"b+h+c+g+",
511  	26750,	"b+d+e+g-",
512  	27250,	"b+e+e+f+",
513  	27500,	"c-i-c-d+",
514  	27750,	"b+bd++j+",
515  	28250,	"d-d-++i-",
516  	28500,	"c+c-h-e-",
517  	29000,	"b+g-d-f+",
518  	29500,	"c+h+++e-",
519  	29750,	"b+g+f-c+",
520  	30250,	"b+f-g-c+",
521  	33500,	"c-f-d-n+",
522  	33750,	"b+d-b+j-",
523  	34250,	"c+e+++i+",
524  	35250,	"e+b+d+k+",
525  	35500,	"c+e+d-g-",
526  	35750,	"c+i-++e+",
527  	36250,	"b+bh-d+e+",
528  	36500,	"c+c-h-e-",
529  	36750,	"d+e--i+",
530  	37250,	"b+g+g+b+",
531  	37500,	"b+h-b+f+",
532  	37750,	"c+be++j-",
533  	38500,	"b+e+b+i+",
534  	38750,	"d+i-b+d+",
535  	39250,	"b+g-l-+d+",
536  	39500,	"b+g-c+g-",
537  	39750,	"b+bh-c+f-",
538  	40250,	"b+bf+d+g-",
539  	40500,	"b+g-c+g+",
540  	40750,	"c+b+i-e+",
541  	41250,	"d++bf+h+",
542  	41500,	"b+j+c+d-",
543  	41750,	"c+f+b+h-",
544  	42500,	"c+h++g+",
545  	42750,	"b+g+d-f-",
546  	43250,	"b+l-e+d-",
547  	43750,	"c+bd+h+f-",
548  	44000,	"b+f+g-d-",
549  	44250,	"b+d-g--f+",
550  	44500,	"c+e+c+h+",
551  	44750,	"b+e+d-h-",
552  	45250,	"b++g+j-g+",
553  	45500,	"c+d+e-g+",
554  	45750,	"b+d-h-e-",
555  	46250,	"c+bd++j+",
556  	46500,	"b+d-c-j-",
557  	46750,	"e-e-b+g-",
558  	47000,	"b+c+d-j-",
559  	47250,	"b+e+e-g-",
560  	47500,	"b+g-c-h-",
561  	47750,	"b+f-c+h-",
562  	48250,	"d--h+n-",
563  	48500,	"b+c-g+m-",
564  	48750,	"b+e+e-g+",
565  	49500,	"c-f+e+j-",
566  	49750,	"c+c+g++f-",
567  	50000,	"b+e+e+k+",
568  	50250,	"b++i++g+",
569  	50500,	"c+g+f-i+",
570  	50750,	"b+e+d+k-",
571  	51500,	"b+i+c-f+",
572  	51750,	"b+bd+g-e-",
573  	52250,	"b+d+g-j+",
574  	52500,	"c+c+f+g+",
575  	52750,	"b+c+e+i+",
576  	53000,	"b+i+c+g+",
577  	53500,	"c+g+g-n+",
578  	53750,	"b+j+d-c+",
579  	54250,	"b+d-g-j-",
580  	54500,	"c-f+e+f+",
581  	54750,	"b+f-+c+g+",
582  	55000,	"b+g-d-g-",
583  	55250,	"b+e+e+g+",
584  	55500,	"b+cd++j+",
585  	55750,	"b+bh-d-f-",
586  	56250,	"c+d-b+j-",
587  	56500,	"c+d+c+i+",
588  	56750,	"b+e+d++h-",
589  	57000,	"b+d+g-f+",
590  	57250,	"b+f-m+d-",
591  	57750,	"b+i+c+e-",
592  	58000,	"b+e+d+h+",
593  	58250,	"c+b+g+g+",
594  	58750,	"d-e-j--e+",
595  	59000,	"d-i-+e+",
596  	59250,	"e--h-m+",
597  	59500,	"c+c-h+f-",
598  	59750,	"b+bh-e+i-",
599  	60250,	"b+bh-e-e-",
600  	60500,	"c+c-g-g-",
601  	60750,	"b+e-l-e-",
602  	61250,	"b+g-g-c+",
603  	61750,	"b+g-c+g+",
604  	62250,	"f--+c-i-",
605  	62750,	"e+f--+g+",
606  	64750,	"b+f+d+p-",
607  };
608  int	hintabsize	= nelem(hintab);
609