![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to gengenblitter.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [UNIX Amiga Emulator] / uae / src|
Return to gengenblitter.c CVS log | Up to [UNIX Amiga Emulator] / uae / src |
1.1 root 1: /*
2: * UAE - The Un*x Amiga Emulator
3: *
4: * Optimized blitter minterm function generator
5: *
6: * Copyright 1995,1996 Bernd Schmidt
7: * Copyright 1996 Alessandro Bissacco
8: *
9: * Overkill, n: cf. genblitter
10: */
11:
12: #include "sysconfig.h"
13: #include "sysdeps.h"
14:
15: #include "config.h"
16: #include "options.h"
17:
18: static void nop(int);
19:
20: #if 0
21: typedef struct alloc_hdr
22: {
23: int size;
24: struct alloc_hdr *next, *prev;
25: void *from, *from2;
26: } *ahead;
27:
28: static struct alloc_hdr ah_top = { 0, &ah_top, &ah_top, 0, 0 };
29:
30: int nbytesmalloced = 0;
31: int malloc_cnt = 0;
32:
33: static void *xmalloc(int sz)
34: {
35: ahead mem = (ahead)malloc(sz + sizeof(struct alloc_hdr));
36: mem->size = sz;
37: mem->next = &ah_top;
38: mem->prev = ah_top.prev;
39: ah_top.prev->next = mem;
40: ah_top.prev = mem;
41:
42: mem->from = __builtin_return_address(0);
43: mem->from2 = __builtin_return_address(1);
44:
45: malloc_cnt++;
46: nbytesmalloced += sz;
47:
48: return mem + 1;
49: }
50:
51: static void *xrealloc(void *mem, int sz)
52: {
53: if (mem == NULL)
54: return xmalloc(sz);
55: else {
56: ahead m = (ahead)mem;
57: m--;
58:
59: nbytesmalloced += sz - m->size;
60: m->size = sz;
61: return ((ahead)realloc(m, sz + sizeof(struct alloc_hdr))) + 1;
62: }
63: }
64:
65: static void xfree(void *mem)
66: {
67: ahead m = (ahead)mem;
68:
69: m--;
70:
71: m->next->prev = m->prev;
72: m->prev->next = m->next;
73: nbytesmalloced -= m->size;
74: malloc_cnt--;
75: free(m);
76: }
77: #else
78: #define xmalloc malloc
79: #define xfree free
80: #define xrealloc realloc
81: #endif
82:
83: typedef struct tree_n {
84: enum tree_op { op_and, op_or, op_xor, op_not, op_a, op_b, op_c } op;
85: struct tree_n *left, *right;
86: } *tree;
87:
88: static struct tree_n TRA = { op_a, NULL, NULL }, TRB = { op_b, NULL, NULL }, TRC = { op_c, NULL, NULL };
89: static tree tree_a = &TRA, tree_b = &TRB, tree_c = &TRC;
90:
91: typedef struct {
92: tree *trees;
93: int space;
94: int ntrees;
95: } tree_vec;
96:
97: static tree best_tree, main_tree;
98: static int best_cost = 65535;
99:
100: static void kill_tree(tree *t)
101: {
102: if (*t != NULL && *t != tree_a && *t != tree_b && *t != tree_c) {
103: if ((*t)->left) kill_tree(&(*t)->left);
104: if ((*t)->right) kill_tree(&(*t)->right);
105: xfree(*t);
106: }
107: *t = NULL;
108: }
109:
110: static tree dup_tree(tree t)
111: {
112: if (t == NULL || t == tree_a || t == tree_b || t == tree_c)
113: return t;
114: else {
115: tree nt = (tree)xmalloc(sizeof(struct tree_n));
116: nt->op = t->op;
117: nt->left = dup_tree(t->left);
118: nt->right = dup_tree(t->right);
119: return nt;
120: }
121: }
122:
123: static tree new_op_tree(enum tree_op op, tree l, tree r)
124: {
125: tree t;
126: if (op == op_not && l->op == op_not) {
127: t = l->left;
128: xfree(l);
129: return t;
130: }
131: t = (tree)xmalloc(sizeof(struct tree_n));
132: t->left = l;
133: t->right = r;
134: t->op = op;
135: return t;
136: }
137:
138: static int tree_cst(tree t, int *nota, int *notb, int *notc)
139: {
140: switch(t->op) {
141: case op_a:
142: case op_b:
143: case op_c:
144: return 0;
145: case op_not:
146: switch (t->left->op) {
147: case op_a:
148: if (*nota)
149: return 0;
150: *nota = 1;
151: return 4;
152:
153: case op_b:
154: if (*notb)
155: return 0;
156: *notb = 1;
157: return 4;
158:
159: case op_c:
160: if (*notc)
161: return 0;
162: *notc = 1;
163: return 4;
164: #if 0
165: case op_not:
166: return tree_cst(t->left->left, nota, notb, notc);
167: #endif
168: default:
169: break;
170: }
171: return 3 + tree_cst(t->left, nota, notb, notc);
172:
173: case op_and:
174: case op_xor:
175: case op_or:
176: return 3 + tree_cst(t->left, nota, notb, notc) + tree_cst(t->right, nota, notb, notc);
177: }
178: return 0;
179: }
180:
181: static int tree_cost(tree t)
182: {
183: int a = 0,b = 0,c = 0;
184:
185: return tree_cst(t,&a,&b,&c);
186: }
187:
188: static int eval(tree t)
189: {
190: int v = tree_cost(t);
191: if (v < best_cost) {
192: best_cost = v;
193: if (best_tree != NULL)
194: kill_tree(&best_tree);
195: best_tree = dup_tree(t);
196: }
197: return v;
198: }
199:
200: static int tree_equal(tree a, tree b)
201: {
202: unsigned long mask = 0;
203: int i;
204: tree t2, t3;
205:
206: if (a == b)
207: return 1;
208: if (a->op != b->op)
209: return 0;
210: if (a->op == op_not)
211: return tree_equal(a->left, b->left);
212:
213: if (a->op != op_xor && a->op != op_or && a->op != op_and)
214: return 0;
215:
216: if (tree_equal(a->left, b->left))
217: return tree_equal(a->right, b->right);
218:
219: for (i = 0, t2 = a; t2->op == a->op; t2 = t2->right, i++)
220: ;
221: for (t3 = b; t3->op == b->op; t3 = t3->right, i--)
222: ;
223:
224: if (i != 0)
225: return 0;
226:
227: t2 = a;
228: for (;;) {
229: tree ttmp;
230: tree t3;
231:
232: if (t2->op == a->op)
233: ttmp = t2->left;
234: else
235: ttmp = t2;
236:
237: t3 = b;
238: for (i = 0;; i++) {
239: tree ttmp2;
240:
241: if (t3->op == b->op)
242: ttmp2 = t3->left;
243: else
244: ttmp2 = t3;
245:
246: if ((mask & (1 << i)) == 0 && tree_equal(ttmp, ttmp2)) {
247: mask |= 1 << i;
248: break;
249: }
250:
251: if (t3->op != b->op)
252: return 0;
253:
254: t3 = t3->right;
255: }
256:
257: if (t2->op != a->op)
258: break;
259:
260: t2 = t2->right;
261: }
262: return 1;
263: }
264:
265: static int tree_isnormal(tree t)
266: {
267: if ((t->op == op_xor || t->op == op_and || t->op == op_or)
268: && t->left->op == t->op)
269: return 0;
270: return 1;
271: }
272:
273: static void normalize(tree *t)
274: {
275: if (*t == NULL)
276: return;
277:
278: if ((*t)->op == op_not && (*t)->left->op == op_not) {
279: tree t2 = (*t)->left->left;
280: xfree((*t)->left);
281: xfree(*t);
282: *t = t2;
283: }
284:
285: while (((*t)->op == op_xor || (*t)->op == op_and || (*t)->op == op_or)
286: && (*t)->left->op == (*t)->op)
287: {
288: tree tmp = (*t)->left->left;
289: (*t)->left->left = (*t)->left->right;
290: (*t)->left->right = (*t)->right;
291: (*t)->right = (*t)->left;
292: (*t)->left = tmp;
293: }
294: normalize(&(*t)->left);
295: normalize(&(*t)->right);
296: }
297:
298: static void add_vec(tree_vec *tv, tree t)
299: {
300: if (!tree_isnormal(t))
301: nop(2);
302:
303: if (tv == NULL) {
304: eval(t);
305: kill_tree(&t);
306: } else {
307: int i;
308: for (i = 0; i < tv->ntrees; i++)
309: if (tree_equal(tv->trees[i], t)) {
310: kill_tree(&t);
311: return;
312: }
313:
314: if (tv->ntrees == tv->space) {
315: tv->trees = (tree *)xrealloc(tv->trees, sizeof(tree)*(tv->space += 40));
316: }
317: tv->trees[tv->ntrees++] = t;
318: }
319: }
320:
321: static void kill_vec(tree_vec *tv)
322: {
323: int i;
324: for (i = 0; i < tv->ntrees; i++)
325: kill_tree(tv->trees + i);
326: xfree(tv->trees);
327: }
328:
329: static void init_vec(tree_vec *tv)
330: {
331: tv->ntrees = tv->space = 0;
332: tv->trees = NULL;
333: }
334:
335: static void do_sprint_tree(char *s, tree *t)
336: {
337: switch ((*t)->op) {
338: case op_a:
339: strcat(s, "srca");
340: break;
341: case op_b:
342: strcat(s, "srcb");
343: break;
344: case op_c:
345: strcat(s, "srcc");
346: break;
347:
348: case op_and:
349: strcat(s, "(");
350: do_sprint_tree(s, &(*t)->left);
351: strcat(s, " & ");
352: while ((*t)->right->op == op_and) {
353: t = &(*t)->right;
354: do_sprint_tree(s, &(*t)->left);
355: strcat(s, " & ");
356: }
357: do_sprint_tree(s, &(*t)->right);
358: strcat(s, ")");
359: break;
360:
361: case op_or:
362: strcat(s, "(");
363: do_sprint_tree(s, &(*t)->left);
364: strcat(s, " | ");
365: while ((*t)->right->op == op_or) {
366: t = &(*t)->right;
367: do_sprint_tree(s, &(*t)->left);
368: strcat(s, " | ");
369: }
370: do_sprint_tree(s, &(*t)->right);
371: strcat(s, ")");
372: break;
373:
374: case op_xor:
375: strcat(s, "(");
376: do_sprint_tree(s, &(*t)->left);
377: strcat(s, " ^ ");
378: while ((*t)->right->op == op_xor) {
379: t = &(*t)->right;
380: do_sprint_tree(s, &(*t)->left);
381: strcat(s, " ^ ");
382: }
383: do_sprint_tree(s, &(*t)->right);
384: strcat(s, ")");
385: break;
386:
387: case op_not:
388: strcat(s, "~");
389: do_sprint_tree(s,&(*t)->left);
390: break;
391: }
392: }
393:
394: static void sprint_tree(char *s, tree t)
395: {
396: tree tt = dup_tree(t);
397: *s = 0;
398: do_sprint_tree(s, &tt);
399: kill_tree(&tt);
400: }
401:
402: static int treecmp(tree a, tree b)
403: {
404: if (b->op != a->op)
405: return 1;
406:
407: if (a == b)
408: return 0;
409:
410: if (a->op == op_not)
411: return treecmp(a->left, b->left);
412:
413: return 1;
414: }
415:
416: static int issrc(tree t)
417: {
418: return t->op == op_a || t->op == op_b || t->op == op_c;
419: }
420:
421: static void do_opt(tree, tree_vec *, int);
422: static void opt_xor(tree t, tree_vec *tv);
423: static void opt_distrib(tree t, tree_vec *tv);
424: static void opt_demorgan(tree t, tree_vec *tv);
425:
426: static void opt_not(tree_vec *tv_dst, tree_vec *tv_src)
427: {
428: int i;
429: for (i = 0; i < tv_src->ntrees; i++) {
430: tree t = tv_src->trees[i];
431:
432: add_vec(tv_dst, new_op_tree(op_not, dup_tree(t), NULL));
433: }
434: }
435:
436: static void demorgan(tree t, tree_vec *tv)
437: {
438: tree newt = NULL, t_l = NULL;
439: int neednot = 0;
440:
441: if (t->op == op_not && (t->left->op == op_and || t->left->op == op_or))
442: t_l = dup_tree(t->left);
443: else if (t->op == op_and || t->op == op_or)
444: t_l = dup_tree(t), neednot = 1;
445: else
446: return;
447:
448: if (t_l->op == op_and)
449: t_l->op = op_or;
450: else
451: t_l->op = op_and;
452:
453: t_l->left = new_op_tree(op_not, t_l->left, NULL);
454: t_l->right = new_op_tree(op_not, t_l->right, NULL);
455: normalize(&t_l);
456:
457: if (neednot) {
458: tree_vec tv2;
459: int i;
460:
461: init_vec(&tv2);
462: opt_xor(t_l, &tv2);
463: opt_distrib(t_l, &tv2);
464: add_vec(&tv2, t_l);
465: #if 0
466: for (i = 0; i < tv2.ntrees; i++) {
467: add_vec(tv, new_op_tree(op_not, dup_tree(tv2.trees[i]), NULL));
468: }
469: #endif
470: opt_not(tv, &tv2);
471: kill_vec(&tv2);
472: } else {
473: opt_xor(t_l, tv);
474: opt_distrib(t_l, tv);
475: add_vec(tv, t_l);
476: }
477: }
478:
479: static void opt_xor(tree t, tree_vec *tv)
480: {
481: tree_vec tv1, tv2;
482: tree tt1, tt2;
483: int i;
484:
485: enum tree_op top, sop;
486: tree t1, t2, t3;
487: int n1 = 0, n2 = 0, ok1 = 0, ok2 = 0;
488:
489: top = t->op;
490: if (top != op_or)
491: return;
492:
493: sop = t->left->op;
494: if (sop != op_and || t->right->op != sop)
495: return;
496:
497: if (t->left->left->op == op_not) {
498: n1 = 1;
499: t1 = t->left->left->left;
500: } else {
501: t1 = t->left->left;
502: }
503:
504: if (t->left->right->op == op_not) {
505: n2 = 1;
506: t2 = t->left->right->left;
507: } else {
508: t2 = t->left->right;
509: }
510:
511: if (t->right->left->op == op_not) {
512: if (n1 == 0 && tree_equal(t->right->left->left, t1))
513: ok1++;
514: if (n2 == 0 && tree_equal(t->right->left->left, t2))
515: ok2++;
516: } else {
517: if (n1 == 1 && tree_equal(t->right->left, t1))
518: ok1++;
519: if (n2 == 1 && tree_equal(t->right->left, t2))
520: ok2++;
521: }
522:
523: if (t->right->right->op == op_not) {
524: if (n1 == 0 && tree_equal(t->right->right->left, t1))
525: ok1++;
526: if (n2 == 0 && tree_equal(t->right->right->left, t2))
527: ok2++;
528: } else {
529: if (n1 == 1 && tree_equal(t->right->right, t1))
530: ok1++;
531: if (n2 == 1 && tree_equal(t->right->right, t2))
532: ok2++;
533: }
534:
535: if (ok1 != 1 || ok2 != 1)
536: return;
537:
538: t3 = new_op_tree(op_xor, dup_tree(t1), dup_tree(t2));
539: if (n1 == n2)
540: t3 = new_op_tree(op_not, t3, NULL);
541: normalize(&t3);
542: add_vec(tv, t3);
543:
544: init_vec(&tv1); init_vec(&tv2);
545: tt1 = new_op_tree(op_not, dup_tree(t1), NULL);
546: tt2 = new_op_tree(op_not, dup_tree(t2), NULL);
547:
548: do_opt(tt1, &tv1, 0); do_opt(tt2, &tv2, 0);
549: kill_tree(&tt1); kill_tree(&tt2);
550:
551: for (i = 0; i < tv1.ntrees; i++) {
552: t3 = new_op_tree(op_xor, dup_tree(tv1.trees[i]), dup_tree(t2));
553: if (n1 != n2)
554: t3 = new_op_tree(op_not, t3, NULL);
555: normalize(&t3);
556: add_vec(tv, t3);
557: }
558:
559: for (i = 0; i < tv2.ntrees; i++) {
560: t3 = new_op_tree(op_xor, dup_tree(t1), dup_tree(tv2.trees[i]));
561: if (n1 != n2)
562: t3 = new_op_tree(op_not, t3, NULL);
563: normalize(&t3);
564: add_vec(tv, t3);
565: }
566:
567: for (i = 0; i < tv1.ntrees; i++) {
568: int j;
569:
570: for (j = 0; j < tv2.ntrees; j++) {
571: t3 = new_op_tree(op_xor, dup_tree(tv1.trees[i]), dup_tree(tv2.trees[j]));
572: if (n1 == n2)
573: t3 = new_op_tree(op_not, t3, NULL);
574: normalize(&t3);
575: add_vec(tv, t3);
576: }
577: }
578:
579: kill_vec(&tv1); kill_vec(&tv2);
580: }
581:
582: static tree opt_factor_tree(tree old, tree f, enum tree_op top, enum tree_op sop,
583: tree *remainder)
584: {
585: tree t1 = old;
586: tree t2 = NULL;
587: *remainder = NULL;
588:
589: for (;;) {
590: int found_factor = 0;
591: tree t3 = NULL;
592: tree t4;
593:
594: if (t1->op == top)
595: t4 = t1->left;
596: else
597: t4 = t1;
598:
599: if (t4->op != sop) {
600: if (*remainder == NULL)
601: *remainder = dup_tree(t4);
602: else
603: *remainder = new_op_tree(top, *remainder, dup_tree(t4));
604: } else {
605: for (;;) {
606: tree t5;
607:
608: if (t4->op == sop)
609: t5 = t4->left;
610: else
611: t5 = t4;
612:
613: if (treecmp(t5, f) != 0) {
614: if (t3 == NULL)
615: t3 = dup_tree(t5);
616: else
617: t3 = new_op_tree(sop, t3, dup_tree(t5));
618: } else
619: found_factor = 1;
620:
621: if (t4->op != sop)
622: break;
623: t4 = t4->right;
624: }
625: if (!found_factor) {
626: if (*remainder == NULL)
627: *remainder = t3;
628: else
629: *remainder = new_op_tree(top, *remainder, t3);
630: } else {
631: if (t2 == NULL)
632: t2 = t3;
633: else
634: t2 = new_op_tree(top, t2, t3);
635: }
636: }
637:
638: if (t1->op != top)
639: break;
640:
641: t1 = t1->right;
642: }
643: if (t2 == NULL || t2->op != top) {
644: if (*remainder != NULL)
645: kill_tree(remainder);
646: if (t2 != NULL)
647: kill_tree(&t2);
648: return NULL;
649: }
650: return t2;
651: }
652:
653: static void opt_distrib(tree t, tree_vec *tv)
654: {
655: enum tree_op top, sop;
656: tree t1;
657:
658: top = t->op;
659:
660: if (top != op_and && top != op_or)
661: return;
662:
663: sop = t->left->op;
664: if ((top == op_and && sop != op_or) || (top == op_or && sop != op_and))
665: return;
666: #if 0
667: t1 = t->right;
668: for (;;) {
669: if (t1->op == sop)
670: break;
671: if (t1->op != top)
672: return;
673: if (t1->left->op != sop)
674: return;
675: t1 = t1->right;
676: }
677: #endif
678:
679: t1 = t->left;
680: for (;;) {
681: tree t3, t4, t5;
682:
683: if (t1->op == sop)
684: t3 = t1->left;
685: else
686: t3 = t1;
687:
688: t4 = opt_factor_tree(t, t3, top, sop, &t5);
689: if (t4 != NULL) {
690: tree_vec tv2;
691: int i;
692:
693: init_vec(&tv2);
694: normalize(&t4);
695: do_opt(t4, &tv2, 0);
696: kill_tree(&t4);
697:
698: for (i = 0; i < tv2.ntrees; i++) {
699: t4 = new_op_tree(sop, dup_tree(t3), dup_tree(tv2.trees[i]));
700: if (t5 != NULL)
701: t4 = new_op_tree(top, t4, dup_tree(t5));
702: normalize(&t4);
703: if (t5 != NULL) {
704: demorgan(t4, tv);
705: opt_xor(t4, tv);
706: }
707: add_vec(tv, t4);
708: }
709: kill_vec(&tv2);
710:
711: if (t5 != NULL)
712: kill_tree(&t5);
713: }
714: if (t1->op != sop)
715: break;
716: t1 = t1->right;
717: }
718: }
719:
720: struct perm_data {
721: int n;
722: int *a;
723: tree_vec *tvar;
724: tree_vec *tvparent;
725: enum tree_op op;
726: int neednot;
727: int didmorgan;
728: };
729:
730: static void allperms(struct perm_data *pd, int p,
731: void (*f)(struct perm_data *))
732: {
733: if (p == pd->n)
734: f(pd);
735: else {
736: int i;
737: for (i = p; i < pd->n; i++) {
738: int tmp = pd->a[i];
739: pd->a[i] = pd->a[p];
740: pd->a[p] = tmp;
741: allperms(pd, p + 1, f);
742: tmp = pd->a[i];
743: pd->a[i] = pd->a[p];
744: pd->a[p] = tmp;
745: }
746: }
747:
748: }
749:
750: static void optimize(tree_vec *tv, tree subt, enum tree_op top)
751: {
752: tree_vec sub_tv;
753: int i;
754:
755: if (subt->op != top) {
756: add_vec(tv, dup_tree(subt));
757: return;
758: }
759:
760: init_vec(&sub_tv);
761: optimize(&sub_tv, subt->right, top);
762:
763: for (i = 0; i < sub_tv.ntrees; i++) {
764: tree t1 = new_op_tree(top, dup_tree(subt->left), dup_tree(sub_tv.trees[i]));
765: demorgan(t1, tv);
766: opt_xor(t1, tv);
767: opt_distrib(t1, tv);
768: add_vec(tv, t1);
769: }
770: kill_vec(&sub_tv);
771: }
772:
773: static void do_opt_perm_1(struct perm_data *pd, int i, tree rhs)
774: {
775: int j = pd->a[i];
776: int k;
777:
778: i++;
779: for (k = 0; k < pd->tvar[j].ntrees; k++) {
780: tree lhs;
781:
782: if (rhs == NULL)
783: lhs = dup_tree(pd->tvar[j].trees[k]);
784: else
785: lhs = new_op_tree(pd->op, dup_tree(pd->tvar[j].trees[k]), dup_tree(rhs));
786:
787: if (i < pd->n) {
788: do_opt_perm_1(pd, i, lhs);
789: } else {
790: normalize(&lhs);
791:
792: if (pd->neednot) {
793: int i;
794: tree_vec tvs;
795: init_vec(&tvs);
796:
797: optimize(&tvs, lhs, lhs->op);
798: #if 0
799: for (i = 0; i < tvs.ntrees; i++)
800: add_vec(pd->tvparent, new_op_tree(op_not, dup_tree(tvs.trees[i]), NULL));
801: #endif
802: opt_not(pd->tvparent, &tvs);
803: kill_vec(&tvs);
804: } else
805: optimize(pd->tvparent, lhs, lhs->op);
806: }
807:
808: kill_tree(&lhs);
809: }
810: nop(j);
811: }
812:
813: void nop(int a)
814: {
815: }
816:
817: static void do_opt_perm(struct perm_data *pd)
818: {
819: do_opt_perm_1(pd, 0, NULL);
820: }
821:
822: static void do_opt(tree t, tree_vec *tv, int did_morgan)
823: {
824: /* if (!did_morgan)
825: demorgan(t, tv);
826: opt_distrib(t, tv);
827: opt_xor(t, tv);*/
828:
829: if ((t->op == op_and || t->op == op_or)
830: || (t->op == op_not
831: && (t->left->op == op_and || t->left->op == op_or)))
832: {
833: int i, j;
834: struct perm_data pd;
835: tree t2, t3;
836: int neednot = t->op == op_not;
837:
838: if (neednot)
839: t3 = t->left;
840: else
841: t3 = t;
842:
843: pd.didmorgan = did_morgan;
844: pd.op = t3->op;
845: pd.neednot = neednot;
846: pd.tvparent = tv;
847: pd.n = 2;
848:
849: t2 = t3->right;
850: while (t2->op == t3->op) {
851: pd.n++;
852: t2 = t2->right;
853: }
854:
855: pd.a = (int *)xmalloc(sizeof(int)*pd.n);
856: pd.tvar = (tree_vec *)xmalloc(sizeof(tree_vec)*pd.n);
857: for (i = 0; i < pd.n; i++)
858: pd.a[i] = i;
859:
860: t2 = t3; i = 0;
861: while (t2->op == t3->op) {
862: init_vec(pd.tvar + i);
863: do_opt(t2->left, pd.tvar + i, neednot && did_morgan);
864: t2 = t2->right;
865: i++;
866: }
867: init_vec(pd.tvar + i);
868: do_opt(t2, pd.tvar + i, 0);
869:
870: allperms(&pd, 0, do_opt_perm);
871:
872: for (i = 0; i < pd.n; i++) {
873: kill_vec(pd.tvar + i);
874: }
875: xfree(pd.tvar);
876: xfree(pd.a);
877: } else {
878: demorgan(t, tv);
879: opt_xor(t, tv);
880: opt_distrib(t, tv);
881: add_vec(tv, dup_tree(t));
882: }
883: }
884:
885: static int bitset(int mt, int bit)
886: {
887: return mt & (1 << bit);
888: }
889:
890: static char buffer[4096];
891:
892: static int generate_expr(int minterm, int print)
893: {
894: int result = 0;
895: int firstor = 1;
896: int bits = 0;
897: int i;
898: int expr_bit[8], expr_dc[8], nexp = 0;
899: int expr_used[8];
900: tree t, t1 = NULL;
901:
902: if (minterm == 0) {
903: if (print)
904: printf("0");
905: return 0;
906: }
907: if (minterm == 0xFF) {
908: if (print)
909: printf("0xFFFFFFFF");
910: return 0;
911: }
912:
913: for(i=0; i<8; i++) {
914: if (bitset(minterm, i) && !bitset(bits,i)) {
915: int j;
916: int dontcare = 0;
917: int firstand = 1;
918: int bitbucket[8], bitcount;
919:
920: bits |= 1<<i;
921: bitcount = 1; bitbucket[0] = i;
922: for(j=1; j<8; j *= 2) {
923: int success = 1;
924: int k;
925: for(k=0; k < bitcount; k++) {
926: if (!bitset(minterm, bitbucket[k] ^ j)) {
927: success = 0;
928: }
929: }
930: if (success) {
931: int l;
932: dontcare |= j;
933: for(l=bitcount; l < bitcount*2; l++) {
934: bitbucket[l] = bitbucket[l-bitcount] ^ j;
935: bits |= 1 << bitbucket[l];
936: }
937: bitcount *= 2;
938: }
939: }
940: expr_used[nexp] = 1;
941: expr_dc[nexp] = dontcare;
942: expr_bit[nexp++] = i;
943: }
944: }
945:
946: t1 = NULL;
947: for (i = 0; i < nexp; i++) {
948: int j, firstand = 1;
949: tree t2 = NULL;
950:
951: for (j = 1; j < 8; j *= 2) {
952: if (!(expr_dc[i] & j)) {
953: tree t3 = j == 1 ? tree_c : j == 2 ? tree_b : tree_a;
954:
955: if ((expr_bit[i] & j) == 0)
956: t3 = new_op_tree(op_not, t3, NULL);
957:
958: if (t2 != NULL)
959: t2 = new_op_tree(op_and, t3, t2);
960: else
961: t2 = t3;
962: result |= (j == 1 ? 4 : j == 2 ? 2 : 1);
963: }
964: }
965: if (t1 != NULL)
966: t1 = new_op_tree(op_or, t2, t1);
967: else
968: t1 = t2;
969: }
970: if (t1 != NULL) {
971: best_tree = NULL;
972: best_cost = 65535;
973: normalize(&t1);
974: main_tree = t1;
975: do_opt(main_tree, NULL, 0);
976: sprint_tree(buffer, best_tree);
977: printf("%s", buffer);
978: kill_tree(&main_tree);
979: kill_tree(&best_tree);
980: }
981:
982: return result;
983: }
984:
985: static void print_expr(int minterm)
986: {
987: generate_expr(minterm, 1);
988: printf("\n");
989: }
990:
991: static void print_tree(tree t)
992: {
993: char buf[32768];
994:
995: sprint_tree(buf, t);
996: printf("%s\n", buf);
997: }
998:
999: static void generate_optable(void)
1000: {
1001: int minterm;
1002: printf(" /* This file generated automatically - do not edit */\n\n");
1003: printf("#include \"genblitter.h\"\n\n");
1004: printf("struct blitop blitops[256] = {\n");
1005: for (minterm = 0; minterm < 256; minterm++) {
1006: int r;
1007: printf(" /* %02x */ { \"", minterm);
1008: r = generate_expr(minterm, 1);
1009: printf("\", %d }%s\n", r, minterm == 255 ? "" : ",");
1010: fflush(stdout);
1011: }
1012: printf("};\n");
1013: }
1014:
1015: int main(int argc, char **argv)
1016: {
1017: #if 0
1018: tree t, t1, t2, t3;
1019: tree_vec tv1;
1020: int i;
1021:
1022: t1 = new_op_tree(op_or, tree_b, tree_a);
1023: t2 = new_op_tree(op_or, tree_c, tree_a);
1024: t3 = new_op_tree(op_not, new_op_tree(op_xor, tree_c, tree_b), NULL);
1025:
1026: t = new_op_tree(op_and, t1, new_op_tree(op_and, t2, t3));
1027: init_vec(&tv1);
1028:
1029: opt_distrib(t, &tv1);
1030: for (i = 0; i < tv1.ntrees; i++)
1031: print_tree(tv1.trees[i]);
1032: kill_vec(&tv1);
1033: #endif
1034: generate_optable();
1035:
1036: return 0;
1037: }
1038:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.