![[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.1.2 root 1: /*
1.1 root 2: * UAE - The Un*x Amiga Emulator
1.1.1.2 root 3: *
1.1 root 4: * Optimized blitter minterm function generator
1.1.1.2 root 5: *
1.1 root 6: * Copyright 1995,1996 Bernd Schmidt
7: * Copyright 1996 Alessandro Bissacco
1.1.1.2 root 8: *
1.1 root 9: * Overkill, n: cf. genblitter
10: */
11:
12: #include "sysconfig.h"
13: #include "sysdeps.h"
14:
15: #include "options.h"
16:
17: static void nop(int);
18:
19: #define xmalloc malloc
20: #define xfree free
21: #define xrealloc realloc
22:
23: typedef struct tree_n {
1.1.1.2 root 24: enum tree_op { op_and, op_or, op_xor, op_not, op_a, op_b, op_c, op_d, op_e, op_f } op;
1.1 root 25: struct tree_n *left, *right;
26: } *tree;
27:
1.1.1.2 root 28: static struct tree_n TRA = { op_a, NULL, NULL };
29: static struct tree_n TRB = { op_b, NULL, NULL };
30: static struct tree_n TRC = { op_c, NULL, NULL };
31: static struct tree_n TRD = { op_d, NULL, NULL };
32: static struct tree_n TRE = { op_e, NULL, NULL };
33: static struct tree_n TRF = { op_f, NULL, NULL };
34: static tree tree_a = &TRA;
35: static tree tree_b = &TRB;
36: static tree tree_c = &TRC;
37: static tree tree_d = &TRD;
38: static tree tree_e = &TRE;
39: static tree tree_f = &TRF;
1.1 root 40:
41: typedef struct {
42: tree *trees;
43: int space;
44: int ntrees;
45: } tree_vec;
46:
1.1.1.3 root 47: STATIC_INLINE int issrc (tree t)
1.1 root 48: {
1.1.1.2 root 49: return t == tree_a || t == tree_b || t == tree_c || t == tree_d || t == tree_e || t == tree_f;
1.1 root 50: }
51:
52: static tree new_op_tree(enum tree_op op, tree l, tree r)
53: {
54: tree t;
55: if (op == op_not && l->op == op_not) {
56: t = l->left;
57: xfree(l);
58: return t;
59: }
60: t = (tree)xmalloc(sizeof(struct tree_n));
61: t->left = l;
62: t->right = r;
63: t->op = op;
64: return t;
65: }
66:
1.1.1.2 root 67: static int opidx (tree t)
1.1 root 68: {
1.1.1.2 root 69: switch (t->op) {
1.1 root 70: case op_a:
1.1.1.2 root 71: return 0;
1.1 root 72: case op_b:
1.1.1.2 root 73: return 1;
1.1 root 74: case op_c:
1.1.1.2 root 75: return 2;
76: case op_d:
77: return 3;
78: case op_e:
79: return 4;
80: case op_f:
81: return 5;
82: default:
83: return -1;
84: }
85: }
86:
87: static int tree_cst (tree t, unsigned int *src, unsigned int *notsrc)
88: {
89: int idx = opidx (t);
90: if (idx >= 0) {
91: src[idx] = 1;
1.1 root 92: return 0;
1.1.1.2 root 93: }
94: switch (t->op) {
1.1 root 95: case op_not:
1.1.1.2 root 96: idx = opidx (t->left);
97: if (idx >= 0) {
98: notsrc[idx] = 1;
99: return 3;
1.1 root 100: }
1.1.1.2 root 101: return 3 + tree_cst (t->left, src, notsrc);
1.1 root 102:
103: case op_and:
104: case op_xor:
105: case op_or:
1.1.1.2 root 106: return 4 + tree_cst (t->left, src, notsrc) + tree_cst (t->right, src, notsrc);
1.1.1.4 root 107:
1.1.1.2 root 108: default:
109: abort ();
1.1 root 110: }
111: }
112:
1.1.1.2 root 113: static int tree_cost (tree t)
1.1 root 114: {
1.1.1.2 root 115: int i, cost;
116: unsigned int src[6], notsrc[6];
117: memset (src, 0, sizeof src);
118: memset (notsrc, 0, sizeof notsrc);
1.1 root 119:
1.1.1.2 root 120: cost = tree_cst (t, src, notsrc);
121: for (i = 0; i < 6; i++)
122: if (src[i] && notsrc[i])
123: cost++;
124: return cost;
1.1 root 125: }
126:
1.1.1.2 root 127: static int add_vec(tree_vec *tv, tree t)
1.1 root 128: {
1.1.1.2 root 129: int i;
130: #if 0
131: if (! tree_isnormal(t))
1.1 root 132: nop(2);
1.1.1.2 root 133: #endif
134: if (tv->ntrees == tv->space) {
135: tv->trees = (tree *)xrealloc(tv->trees, sizeof(tree)*(tv->space += 40));
1.1 root 136: }
1.1.1.2 root 137: tv->trees[tv->ntrees++] = t;
1.1 root 138:
1.1.1.2 root 139: return 1;
1.1 root 140: }
141:
142: static void init_vec(tree_vec *tv)
143: {
144: tv->ntrees = tv->space = 0;
145: tv->trees = NULL;
146: }
147:
1.1.1.2 root 148: static void do_sprint_tree (char *s, tree t)
1.1 root 149: {
1.1.1.2 root 150: enum tree_op op = t->op;
151: switch (op) {
1.1 root 152: case op_a:
1.1.1.2 root 153: strcat (s, "srca");
1.1 root 154: break;
155: case op_b:
1.1.1.2 root 156: strcat (s, "srcb");
1.1 root 157: break;
158: case op_c:
1.1.1.2 root 159: strcat (s, "srcc");
1.1 root 160: break;
1.1.1.2 root 161: case op_d:
162: strcat (s, "srcd");
1.1 root 163: break;
1.1.1.2 root 164: case op_e:
165: strcat (s, "srce");
1.1 root 166: break;
1.1.1.2 root 167: case op_f:
168: strcat (s, "srcf");
169: break;
170:
171: case op_and:
172: case op_or:
1.1 root 173: case op_xor:
1.1.1.2 root 174: {
1.1.1.4 root 175:
1.1.1.2 root 176: char *c = op == op_and ? " & " : op == op_or ? " | " : " ^ ";
177: strcat (s, "(");
178: do_sprint_tree (s, t->left);
179: strcat (s, c);
180: while (t->right->op == op) {
181: t = t->right;
182: do_sprint_tree (s, t->left);
183: strcat (s, c);
184: }
185: do_sprint_tree(s, t->right);
186: strcat (s, ")");
1.1 root 187: }
188: break;
1.1.1.2 root 189:
1.1 root 190: case op_not:
1.1.1.2 root 191: strcat (s, "~");
192: do_sprint_tree (s, t->left);
1.1 root 193: break;
194: }
195: }
196:
1.1.1.2 root 197: static tree_vec size_trees[20];
1.1 root 198:
1.1.1.2 root 199: static struct tree_n bad_tree = { op_and, &bad_tree, &bad_tree };
1.1 root 200:
1.1.1.2 root 201: static unsigned int used_mask[256];
202: static tree best_trees[256];
203: static unsigned int best_cost[256];
204: static int n_unknown;
1.1 root 205:
1.1.1.2 root 206: static unsigned long which_fn (tree t)
1.1 root 207: {
1.1.1.2 root 208: switch (t->op) {
209: case op_a:
210: return 0xf0;
211: case op_b:
212: return 0xcc;
213: case op_c:
214: return 0xaa;
215: case op_and:
216: return which_fn (t->left) & which_fn (t->right);
217: case op_or:
218: return which_fn (t->left) | which_fn (t->right);
219: case op_xor:
220: return which_fn (t->left) ^ which_fn (t->right);
221: case op_not:
222: return 0xFF & ~which_fn (t->left);
223: default:
224: abort ();
1.1 root 225: }
226: }
227:
1.1.1.2 root 228: static unsigned long tree_used_mask (tree t)
1.1 root 229: {
1.1.1.2 root 230: switch (t->op) {
231: case op_a:
232: return 1;
233: case op_b:
234: return 2;
235: case op_c:
236: return 4;
237: case op_and:
238: case op_or:
239: case op_xor:
240: return tree_used_mask (t->left) | tree_used_mask (t->right);
241: case op_not:
242: return tree_used_mask (t->left);
243: default:
244: abort ();
1.1 root 245: }
246: }
247:
1.1.1.2 root 248: static void candidate (tree_vec *v, tree t)
1.1 root 249: {
1.1.1.2 root 250: unsigned long fn = which_fn (t);
251: unsigned int cost = tree_cost (t);
252: if (best_trees[fn] == 0)
253: n_unknown--;
254: if (cost < best_cost[fn])
255: best_trees[fn] = t, best_cost[fn] = cost;
256: add_vec (v, t);
1.1 root 257: }
258:
1.1.1.2 root 259: static void cand_and_not (tree_vec *v, tree t)
1.1 root 260: {
1.1.1.2 root 261: candidate (v, t);
262: t = new_op_tree (op_not, t, 0);
263: candidate (v, t);
1.1 root 264: }
265:
1.1.1.2 root 266: static void try_tree (tree_vec *v, tree t)
1.1 root 267: {
1.1.1.2 root 268: int fnl = which_fn (t->left);
269: int fnr = which_fn (t->right);
270: int fn = which_fn (t);
271: if (fn == fnl
272: || fn == fnr
273: || fn == 0
274: || fn == 0xFF
275: || (tree_used_mask (t) & ~used_mask[fn]) != 0
276: || best_cost[fn] + 6 < tree_cost (t))
277: {
278: xfree (t);
1.1 root 279: return;
280: }
1.1.1.2 root 281: cand_and_not (v, t);
1.1 root 282: }
283:
1.1.1.2 root 284: static void find_best_trees (void)
1.1 root 285: {
1.1.1.2 root 286: int i, size, do_stop;
287: for (i = 0; i < 256; i++) {
288: best_trees[i] = i == 0 || i == 255 ? &bad_tree : 0;
289: best_cost[i] = 65535;
290: }
291: n_unknown = 254;
292:
293: init_vec (size_trees);
294: cand_and_not (size_trees, tree_a);
295: cand_and_not (size_trees, tree_b);
296: cand_and_not (size_trees, tree_c);
297:
298: do_stop = 0;
299: for (size = 2; ! do_stop && size < 20; size++) {
300: int split, last_split;
301: tree_vec *sv = size_trees + size - 1;
1.1.1.4 root 302:
1.1.1.2 root 303: if (n_unknown == 0)
304: do_stop = 1;
305: last_split = (size >> 1) + 1;
306: for (split = 1; split < last_split; split++) {
307: int szl = split;
308: int szr = size - split;
309: tree_vec *lv = size_trees + szl - 1;
310: tree_vec *rv = size_trees + szr - 1;
311: int i;
1.1 root 312:
1.1.1.2 root 313: for (i = 0; i < lv->ntrees; i++) {
314: tree l = lv->trees[i];
315: int j;
316: for (j = szl == szr ? i + 1 : 0; j < rv->ntrees; j++) {
317: tree r = rv->trees[j];
318:
319: if (l->op != op_and || r->op != op_and) {
320: tree tmp = (l->op == op_and
321: ? new_op_tree (op_and, r, l)
322: : new_op_tree (op_and, l, r));
323: try_tree (sv, tmp);
324: }
325: if (l->op != op_or || r->op != op_or) {
326: tree tmp = (l->op == op_or
327: ? new_op_tree (op_or, r, l)
328: : new_op_tree (op_or, l, r));
329: try_tree (sv, tmp);
330: }
331: if (l->op != op_xor || r->op != op_xor) {
332: tree tmp = (l->op == op_xor
333: ? new_op_tree (op_xor, r, l)
334: : new_op_tree (op_xor, l, r));
335: try_tree (sv, tmp);
336: }
337: }
338: }
1.1 root 339: }
1.1.1.2 root 340: /* An additional pass doesn't seem to create better solutions
341: * (not that much of a surprise). */
342: if (n_unknown == 0)
343: do_stop = 1;
1.1 root 344: }
345: }
346:
1.1.1.2 root 347: static int bitset (int mt, int bit)
1.1 root 348: {
349: return mt & (1 << bit);
350: }
351:
1.1.1.2 root 352: static unsigned int generate_expr (int minterm)
1.1 root 353: {
354: int bits = 0;
355: int i;
1.1.1.2 root 356: int expr_dc[8], nexp = 0;
1.1 root 357: int expr_used[8];
358:
1.1.1.2 root 359: if (minterm == 0 || minterm == 0xFF)
1.1 root 360: return 0;
1.1.1.2 root 361:
362: for (i = 0; i < 8; i++) {
363: if (bitset (minterm, i) && !bitset (bits, i)) {
1.1 root 364: int j;
365: int dontcare = 0;
366: int firstand = 1;
367: int bitbucket[8], bitcount;
1.1.1.2 root 368:
1.1 root 369: bits |= 1<<i;
1.1.1.2 root 370: bitcount = 1; bitbucket[0] = i;
1.1 root 371: for(j=1; j<8; j *= 2) {
372: int success = 1;
373: int k;
1.1.1.2 root 374: for(k=0; k < bitcount; k++) {
375: if (!bitset (minterm, bitbucket[k] ^ j)) {
1.1 root 376: success = 0;
377: }
378: }
379: if (success) {
380: int l;
381: dontcare |= j;
382: for(l=bitcount; l < bitcount*2; l++) {
383: bitbucket[l] = bitbucket[l-bitcount] ^ j;
384: bits |= 1 << bitbucket[l];
385: }
386: bitcount *= 2;
387: }
388: }
389: expr_used[nexp] = 1;
390: expr_dc[nexp] = dontcare;
1.1.1.2 root 391: nexp++;
1.1 root 392: }
393: }
1.1.1.2 root 394:
395: {
396: unsigned int result = 0;
397: for (i = 0; i < nexp; i++) {
398: int j;
399:
400: for (j = 1; j < 8; j *= 2) {
401: if (!(expr_dc[i] & j))
402: result |= (j == 1 ? 4 : j == 2 ? 2 : 1);
1.1 root 403: }
404: }
1.1.1.2 root 405: return result;
1.1 root 406: }
407: }
408:
409: static void print_tree(tree t)
410: {
1.1.1.2 root 411: char buf[300] = "";
412: do_sprint_tree (buf, t);
413: printf ("%s", buf);
1.1 root 414: }
415:
416: static void generate_optable(void)
417: {
418: int minterm;
419: printf(" /* This file generated automatically - do not edit */\n\n");
420: printf("#include \"genblitter.h\"\n\n");
421: printf("struct blitop blitops[256] = {\n");
422: for (minterm = 0; minterm < 256; minterm++) {
423: printf(" /* %02x */ { \"", minterm);
1.1.1.2 root 424: if (minterm == 0)
425: printf ("0");
426: else if (minterm == 255)
427: printf ("0xFFFFFFFF");
428: else
429: print_tree (best_trees[minterm]);
430:
431: printf("\", %d }%s\n", used_mask[minterm], minterm == 255 ? "" : ",");
1.1 root 432: fflush(stdout);
433: }
434: printf("};\n");
435: }
436:
1.1.1.2 root 437: int main (int argc, char **argv)
1.1 root 438: {
1.1.1.2 root 439: int minterm;
440: for (minterm = 0; minterm < 256; minterm++)
441: used_mask[minterm] = generate_expr (minterm);
442: find_best_trees ();
443: generate_optable ();
1.1 root 444:
445: return 0;
446: }
447:
1.1.1.2 root 448: void nop(int a)
449: {
450: }
451:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.