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