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*
mulcon0(long v)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
docode(char * hp,char * cp,int r0,int r1)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
gen1(int len)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
gen2(int len,long r1)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
gen3(int len,long r0,long r1,int flag)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