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