![[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.