Subversion Repositories planix.SVN

Rev

Rev 2 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 - 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);