xref: /inferno-os/utils/0c/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	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