Return to gengenblitter.c CVS log

Up to [UNIX Amiga Emulator] / uae / src

Annotation of uae/src/gengenblitter.c, revision 1.1.1.2

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.2 ! 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       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:        {
        !           176:            
        !           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;
        !           303:        
        !           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.