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