Return to mul.c CVS log

Up to [Plan 9 NeXT] / lucent / sys / src / alef / k

Annotation of lucent/sys/src/alef/k/mul.c, revision 1.1

1.1     ! root        1: #include <u.h>
        !             2: #include <libc.h>
        !             3: #include <bio.h>
        !             4: #include <ctype.h>
        !             5: #define Extern extern
        !             6: #include "parl.h"
        !             7: #include "globl.h"
        !             8: 
        !             9: /*
        !            10:  * code sequences for multiply by constant.
        !            11:  * [a-l][0-3]
        !            12:  *     lsl     $(A-'a'),r0,r1
        !            13:  * [+][0-7]
        !            14:  *     add     r0,r1,r2
        !            15:  * [-][0-7]
        !            16:  *     sub     r0,r1,r2
        !            17:  */
        !            18: 
        !            19: static int     multabp;
        !            20: static long    mulval;
        !            21: static char*   mulcp;
        !            22: static long    valmax;
        !            23: static int     shmax;
        !            24: 
        !            25: static int     docode(char *hp, char *cp, int r0, int r1);
        !            26: static int     gen1(int len);
        !            27: static int     gen2(int len, long r1);
        !            28: static int     gen3(int len, long r0, long r1, int flag);
        !            29: enum
        !            30: {
        !            31:        SR1     = 1<<0,         /* r1 has been shifted */
        !            32:        SR0     = 1<<1,         /* r0 has been shifted */
        !            33:        UR1     = 1<<2,         /* r1 has not been used */
        !            34:        UR0     = 1<<3,         /* r0 has not been used */
        !            35: };
        !            36: 
        !            37: Multab*
        !            38: mulcon0(long v)
        !            39: {
        !            40:        int a1, a2, g;
        !            41:        Multab *m, *m1;
        !            42:        char hint[10];
        !            43: 
        !            44:        if(v < 0)
        !            45:                v = -v;
        !            46: 
        !            47:        /*
        !            48:         * look in cache
        !            49:         */
        !            50:        m = multab;
        !            51:        for(g=0; g<nelem(multab); g++) {
        !            52:                if(m->val == v) {
        !            53:                        if(m->code[0] == 0)
        !            54:                                return 0;
        !            55:                        return m;
        !            56:                }
        !            57:                m++;
        !            58:        }
        !            59: 
        !            60:        /*
        !            61:         * select a spot in cache to overwrite
        !            62:         */
        !            63:        multabp++;
        !            64:        if(multabp < 0 || multabp >= nelem(multab))
        !            65:                multabp = 0;
        !            66:        m = multab+multabp;
        !            67:        m->val = v;
        !            68:        mulval = v;
        !            69: 
        !            70:        /*
        !            71:         * look in execption hint table
        !            72:         */
        !            73:        a1 = 0;
        !            74:        a2 = hintabsize;
        !            75:        for(;;) {
        !            76:                if(a1 >= a2)
        !            77:                        goto no;
        !            78:                g = (a2 + a1)/2;
        !            79:                if(v < hintab[g].val) {
        !            80:                        a2 = g;
        !            81:                        continue;
        !            82:                }
        !            83:                if(v > hintab[g].val) {
        !            84:                        a1 = g+1;
        !            85:                        continue;
        !            86:                }
        !            87:                break;
        !            88:        }
        !            89: 
        !            90:        if(docode(hintab[g].hint, m->code, 1, 0))
        !            91:                return m;
        !            92:        print("multiply table failure %ld\n", v);
        !            93:        m->code[0] = 0;
        !            94:        return 0;
        !            95: 
        !            96: no:
        !            97:        /*
        !            98:         * try to search
        !            99:         */
        !           100:        hint[0] = 0;
        !           101:        for(g=1; g<=6; g++) {
        !           102:                if(g >= 6 && v >= 65535)
        !           103:                        break;
        !           104:                mulcp = hint+g;
        !           105:                *mulcp = 0;
        !           106:                if(gen1(g)) {
        !           107:                        if(docode(hint, m->code, 1, 0))
        !           108:                                return m;
        !           109:                        print("multiply table failure %ld\n", v);
        !           110:                        break;
        !           111:                }
        !           112:        }
        !           113: 
        !           114:        /*
        !           115:         * try a recur followed by a shift
        !           116:         */
        !           117:        g = 0;
        !           118:        while(!(v & 1)) {
        !           119:                g++;
        !           120:                v >>= 1;
        !           121:        }
        !           122:        if(g) {
        !           123:                m1 = mulcon0(v);
        !           124:                if(m1) {
        !           125:                        strcpy(m->code, m1->code);
        !           126:                        sprint(strchr(m->code, 0), "%c0", g+'a');
        !           127:                        return m;
        !           128:                }
        !           129:        }
        !           130:        m->code[0] = 0;
        !           131:        return 0;
        !           132: }
        !           133: 
        !           134: static int
        !           135: docode(char *hp, char *cp, int r0, int r1)
        !           136: {
        !           137:        int c, i;
        !           138: 
        !           139:        c = *hp++;
        !           140:        *cp = c;
        !           141:        cp += 2;
        !           142:        switch(c) {
        !           143:        default:
        !           144:                c -= 'a';
        !           145:                if(c < 1 || c >= 30)
        !           146:                        break;
        !           147:                for(i=0; i<4; i++) {
        !           148:                        switch(i) {
        !           149:                        case 0:
        !           150:                                if(docode(hp, cp, r0<<c, r1))
        !           151:                                        goto out;
        !           152:                                break;
        !           153:                        case 1:
        !           154:                                if(docode(hp, cp, r1<<c, r1))
        !           155:                                        goto out;
        !           156:                                break;
        !           157:                        case 2:
        !           158:                                if(docode(hp, cp, r0, r0<<c))
        !           159:                                        goto out;
        !           160:                                break;
        !           161:                        case 3:
        !           162:                                if(docode(hp, cp, r0, r1<<c))
        !           163:                                        goto out;
        !           164:                                break;
        !           165:                        }
        !           166:                }
        !           167:                break;
        !           168: 
        !           169:        case '+':
        !           170:                for(i=0; i<8; i++) {
        !           171:                        cp[-1] = i+'0';
        !           172:                        switch(i) {
        !           173:                        case 1:
        !           174:                                if(docode(hp, cp, r0+r1, r1))
        !           175:                                        goto out;
        !           176:                                break;
        !           177:                        case 5:
        !           178:                                if(docode(hp, cp, r0, r0+r1))
        !           179:                                        goto out;
        !           180:                                break;
        !           181:                        }
        !           182:                }
        !           183:                break;
        !           184: 
        !           185:        case '-':
        !           186:                for(i=0; i<8; i++) {
        !           187:                        cp[-1] = i+'0';
        !           188:                        switch(i) {
        !           189:                        case 1:
        !           190:                                if(docode(hp, cp, r0-r1, r1))
        !           191:                                        goto out;
        !           192:                                break;
        !           193:                        case 2:
        !           194:                                if(docode(hp, cp, r1-r0, r1))
        !           195:                                        goto out;
        !           196:                                break;
        !           197:                        case 5:
        !           198:                                if(docode(hp, cp, r0, r0-r1))
        !           199:                                        goto out;
        !           200:                                break;
        !           201:                        case 6:
        !           202:                                if(docode(hp, cp, r0, r1-r0))
        !           203:                                        goto out;
        !           204:                                break;
        !           205:                        }
        !           206:                }
        !           207:                break;
        !           208: 
        !           209:        case 0:
        !           210:                if(r0 == mulval)
        !           211:                        return 1;
        !           212:        }
        !           213:        return 0;
        !           214: 
        !           215: out:
        !           216:        cp[-1] = i+'0';
        !           217:        return 1;
        !           218: }
        !           219: 
        !           220: static int
        !           221: gen1(int len)
        !           222: {
        !           223:        int i;
        !           224: 
        !           225:        for(shmax=1; shmax<30; shmax++) {
        !           226:                valmax = 1<<shmax;
        !           227:                if(valmax >= mulval)
        !           228:                        break;
        !           229:        }
        !           230:        if(mulval == 1)
        !           231:                return 1;
        !           232: 
        !           233:        len--;
        !           234:        for(i=1; i<=shmax; i++)
        !           235:                if(gen2(len, 1<<i)) {
        !           236:                        *--mulcp = 'a'+i;
        !           237:                        return 1;
        !           238:                }
        !           239:        return 0;
        !           240: }
        !           241: 
        !           242: static int
        !           243: gen2(int len, long r1)
        !           244: {
        !           245:        int i;
        !           246: 
        !           247:        if(len <= 0) {
        !           248:                if(r1 == mulval)
        !           249:                        return 1;
        !           250:                return 0;
        !           251:        }
        !           252: 
        !           253:        len--;
        !           254:        if(len == 0)
        !           255:                goto calcr0;
        !           256: 
        !           257:        if(gen3(len, r1, r1+1, UR1)) {
        !           258:                i = '+';
        !           259:                goto out;
        !           260:        }
        !           261:        if(gen3(len, r1-1, r1, UR0)) {
        !           262:                i = '-';
        !           263:                goto out;
        !           264:        }
        !           265:        if(gen3(len, 1, r1+1, UR1)) {
        !           266:                i = '+';
        !           267:                goto out;
        !           268:        }
        !           269:        if(gen3(len, 1, r1-1, UR1)) {
        !           270:                i = '-';
        !           271:                goto out;
        !           272:        }
        !           273: 
        !           274:        return 0;
        !           275: 
        !           276: calcr0:
        !           277:        if(mulval == r1+1) {
        !           278:                i = '+';
        !           279:                goto out;
        !           280:        }
        !           281:        if(mulval == r1-1) {
        !           282:                i = '-';
        !           283:                goto out;
        !           284:        }
        !           285:        return 0;
        !           286: 
        !           287: out:
        !           288:        *--mulcp = i;
        !           289:        return 1;
        !           290: }
        !           291: 
        !           292: static int
        !           293: gen3(int len, long r0, long r1, int flag)
        !           294: {
        !           295:        int i, f1, f2;
        !           296:        long x;
        !           297: 
        !           298:        if(r0 <= 0 ||
        !           299:           r0 >= r1 ||
        !           300:           r1 > valmax)
        !           301:                return 0;
        !           302: 
        !           303:        len--;
        !           304:        if(len == 0)
        !           305:                goto calcr0;
        !           306: 
        !           307:        if(!(flag & UR1)) {
        !           308:                f1 = UR1|SR1;
        !           309:                for(i=1; i<=shmax; i++) {
        !           310:                        x = r0<<i;
        !           311:                        if(x > valmax)
        !           312:                                break;
        !           313:                        if(gen3(len, r0, x, f1)) {
        !           314:                                i += 'a';
        !           315:                                goto out;
        !           316:                        }
        !           317:                }
        !           318:        }
        !           319: 
        !           320:        if(!(flag & UR0)) {
        !           321:                f1 = UR1|SR1;
        !           322:                for(i=1; i<=shmax; i++) {
        !           323:                        x = r1<<i;
        !           324:                        if(x > valmax)
        !           325:                                break;
        !           326:                        if(gen3(len, r1, x, f1)) {
        !           327:                                i += 'a';
        !           328:                                goto out;
        !           329:                        }
        !           330:                }
        !           331:        }
        !           332: 
        !           333:        if(!(flag & SR1)) {
        !           334:                f1 = UR1|SR1|(flag&UR0);
        !           335:                for(i=1; i<=shmax; i++) {
        !           336:                        x = r1<<i;
        !           337:                        if(x > valmax)
        !           338:                                break;
        !           339:                        if(gen3(len, r0, x, f1)) {
        !           340:                                i += 'a';
        !           341:                                goto out;
        !           342:                        }
        !           343:                }
        !           344:        }
        !           345: 
        !           346:        if(!(flag & SR0)) {
        !           347:                f1 = UR0|SR0|(flag&(SR1|UR1));
        !           348: 
        !           349:                f2 = UR1|SR1;
        !           350:                if(flag & UR1)
        !           351:                        f2 |= UR0;
        !           352:                if(flag & SR1)
        !           353:                        f2 |= SR0;
        !           354: 
        !           355:                for(i=1; i<=shmax; i++) {
        !           356:                        x = r0<<i;
        !           357:                        if(x > valmax)
        !           358:                                break;
        !           359:                        if(x > r1) {
        !           360:                                if(gen3(len, r1, x, f2)) {
        !           361:                                        i += 'a';
        !           362:                                        goto out;
        !           363:                                }
        !           364:                        } else
        !           365:                                if(gen3(len, x, r1, f1)) {
        !           366:                                        i += 'a';
        !           367:                                        goto out;
        !           368:                                }
        !           369:                }
        !           370:        }
        !           371: 
        !           372:        x = r1+r0;
        !           373:        if(gen3(len, r0, x, UR1)) {
        !           374:                i = '+';
        !           375:                goto out;
        !           376:        }
        !           377: 
        !           378:        if(gen3(len, r1, x, UR1)) {
        !           379:                i = '+';
        !           380:                goto out;
        !           381:        }
        !           382: 
        !           383:        x = r1-r0;
        !           384:        if(gen3(len, x, r1, UR0)) {
        !           385:                i = '-';
        !           386:                goto out;
        !           387:        }
        !           388: 
        !           389:        if(x > r0) {
        !           390:                if(gen3(len, r0, x, UR1)) {
        !           391:                        i = '-';
        !           392:                        goto out;
        !           393:                }
        !           394:        } else
        !           395:                if(gen3(len, x, r0, UR0)) {
        !           396:                        i = '-';
        !           397:                        goto out;
        !           398:                }
        !           399: 
        !           400:        return 0;
        !           401: 
        !           402: calcr0:
        !           403:        f1 = flag & (UR0|UR1);
        !           404:        if(f1 == UR1) {
        !           405:                for(i=1; i<=shmax; i++) {
        !           406:                        x = r1<<i;
        !           407:                        if(x >= mulval) {
        !           408:                                if(x == mulval) {
        !           409:                                        i += 'a';
        !           410:                                        goto out;
        !           411:                                }
        !           412:                                break;
        !           413:                        }
        !           414:                }
        !           415:        }
        !           416: 
        !           417:        if(mulval == r1+r0) {
        !           418:                i = '+';
        !           419:                goto out;
        !           420:        }
        !           421:        if(mulval == r1-r0) {
        !           422:                i = '-';
        !           423:                goto out;
        !           424:        }
        !           425: 
        !           426:        return 0;
        !           427: 
        !           428: out:
        !           429:        *--mulcp = i;
        !           430:        return 1;
        !           431: }
        !           432: 
        !           433: /*
        !           434:  * hint table has numbers that
        !           435:  * the search algorithm fails on.
        !           436:  * <1000:
        !           437:  *     all numbers
        !           438:  * <5000:
        !           439:  *     ÷ by 5
        !           440:  * <10000:
        !           441:  *     ÷ by 50
        !           442:  * <65536:
        !           443:  *     ÷ by 250
        !           444:  */
        !           445: Hintab hintab[] =
        !           446: {
        !           447:        683,    "b++d+e+",
        !           448:        687,    "b+e++e-",
        !           449:        691,    "b++d+e+",
        !           450:        731,    "b++d+e+",
        !           451:        811,    "b++d+i+",
        !           452:        821,    "b++e+e+",
        !           453:        843,    "b+d++e+",
        !           454:        851,    "b+f-+e-",
        !           455:        853,    "b++e+e+",
        !           456:        877,    "c++++g-",
        !           457:        933,    "b+c++g-",
        !           458:        981,    "c-+e-d+",
        !           459:        1375,   "b+c+b+h-",
        !           460:        1675,   "d+b++h+",
        !           461:        2425,   "c++f-e+",
        !           462:        2675,   "c+d++f-",
        !           463:        2750,   "b+d-b+h-",
        !           464:        2775,   "c-+g-e-",
        !           465:        3125,   "b++e+g+",
        !           466:        3275,   "b+c+g+e+",
        !           467:        3350,   "c++++i+",
        !           468:        3475,   "c-+e-f-",
        !           469:        3525,   "c-+d+g-",
        !           470:        3625,   "c-+e-j+",
        !           471:        3675,   "b+d+d+e+",
        !           472:        3725,   "b+d-+h+",
        !           473:        3925,   "b+d+f-d-",
        !           474:        4275,   "b+g++e+",
        !           475:        4325,   "b+h-+d+",
        !           476:        4425,   "b+b+g-j-",
        !           477:        4525,   "b+d-d+f+",
        !           478:        4675,   "c++d-g+",
        !           479:        4775,   "b+d+b+g-",
        !           480:        4825,   "c+c-+i-",
        !           481:        4850,   "c++++i-",
        !           482:        4925,   "b++e-g-",
        !           483:        4975,   "c+f++e-",
        !           484:        5500,   "b+g-c+d+",
        !           485:        6700,   "d+b++i+",
        !           486:        9700,   "d++++j-",
        !           487:        11000,  "b+f-c-h-",
        !           488:        11750,  "b+d+g+j-",
        !           489:        12500,  "b+c+e-k+",
        !           490:        13250,  "b+d+e-f+",
        !           491:        13750,  "b+h-c-d+",
        !           492:        14250,  "b+g-c+e-",
        !           493:        14500,  "c+f+j-d-",
        !           494:        14750,  "d-g--f+",
        !           495:        16750,  "b+e-d-n+",
        !           496:        17750,  "c+h-b+e+",
        !           497:        18250,  "d+b+h-d+",
        !           498:        18750,  "b+g-++f+",
        !           499:        19250,  "b+e+b+h+",
        !           500:        19750,  "b++h--f-",
        !           501:        20250,  "b+e-l-c+",
        !           502:        20750,  "c++bi+e-",
        !           503:        21250,  "b+i+l+c+",
        !           504:        22000,  "b+e+d-g-",
        !           505:        22250,  "b+d-h+k-",
        !           506:        22750,  "b+d-e-g+",
        !           507:        23250,  "b+c+h+e-",
        !           508:        23500,  "b+g-c-g-",
        !           509:        23750,  "b+g-b+h-",
        !           510:        24250,  "c++g+m-",
        !           511:        24750,  "b+e+e+j-",
        !           512:        25000,  "b++dh+g+",
        !           513:        25250,  "b+e+d-g-",
        !           514:        25750,  "b+e+b+j+",
        !           515:        26250,  "b+h+c+e+",
        !           516:        26500,  "b+h+c+g+",
        !           517:        26750,  "b+d+e+g-",
        !           518:        27250,  "b+e+e+f+",
        !           519:        27500,  "c-i-c-d+",
        !           520:        27750,  "b+bd++j+",
        !           521:        28250,  "d-d-++i-",
        !           522:        28500,  "c+c-h-e-",
        !           523:        29000,  "b+g-d-f+",
        !           524:        29500,  "c+h+++e-",
        !           525:        29750,  "b+g+f-c+",
        !           526:        30250,  "b+f-g-c+",
        !           527:        33500,  "c-f-d-n+",
        !           528:        33750,  "b+d-b+j-",
        !           529:        34250,  "c+e+++i+",
        !           530:        35250,  "e+b+d+k+",
        !           531:        35500,  "c+e+d-g-",
        !           532:        35750,  "c+i-++e+",
        !           533:        36250,  "b+bh-d+e+",
        !           534:        36500,  "c+c-h-e-",
        !           535:        36750,  "d+e--i+",
        !           536:        37250,  "b+g+g+b+",
        !           537:        37500,  "b+h-b+f+",
        !           538:        37750,  "c+be++j-",
        !           539:        38500,  "b+e+b+i+",
        !           540:        38750,  "d+i-b+d+",
        !           541:        39250,  "b+g-l-+d+",
        !           542:        39500,  "b+g-c+g-",
        !           543:        39750,  "b+bh-c+f-",
        !           544:        40250,  "b+bf+d+g-",
        !           545:        40500,  "b+g-c+g+",
        !           546:        40750,  "c+b+i-e+",
        !           547:        41250,  "d++bf+h+",
        !           548:        41500,  "b+j+c+d-",
        !           549:        41750,  "c+f+b+h-",
        !           550:        42500,  "c+h++g+",
        !           551:        42750,  "b+g+d-f-",
        !           552:        43250,  "b+l-e+d-",
        !           553:        43750,  "c+bd+h+f-",
        !           554:        44000,  "b+f+g-d-",
        !           555:        44250,  "b+d-g--f+",
        !           556:        44500,  "c+e+c+h+",
        !           557:        44750,  "b+e+d-h-",
        !           558:        45250,  "b++g+j-g+",
        !           559:        45500,  "c+d+e-g+",
        !           560:        45750,  "b+d-h-e-",
        !           561:        46250,  "c+bd++j+",
        !           562:        46500,  "b+d-c-j-",
        !           563:        46750,  "e-e-b+g-",
        !           564:        47000,  "b+c+d-j-",
        !           565:        47250,  "b+e+e-g-",
        !           566:        47500,  "b+g-c-h-",
        !           567:        47750,  "b+f-c+h-",
        !           568:        48250,  "d--h+n-",
        !           569:        48500,  "b+c-g+m-",
        !           570:        48750,  "b+e+e-g+",
        !           571:        49500,  "c-f+e+j-",
        !           572:        49750,  "c+c+g++f-",
        !           573:        50000,  "b+e+e+k+",
        !           574:        50250,  "b++i++g+",
        !           575:        50500,  "c+g+f-i+",
        !           576:        50750,  "b+e+d+k-",
        !           577:        51500,  "b+i+c-f+",
        !           578:        51750,  "b+bd+g-e-",
        !           579:        52250,  "b+d+g-j+",
        !           580:        52500,  "c+c+f+g+",
        !           581:        52750,  "b+c+e+i+",
        !           582:        53000,  "b+i+c+g+",
        !           583:        53500,  "c+g+g-n+",
        !           584:        53750,  "b+j+d-c+",
        !           585:        54250,  "b+d-g-j-",
        !           586:        54500,  "c-f+e+f+",
        !           587:        54750,  "b+f-+c+g+",
        !           588:        55000,  "b+g-d-g-",
        !           589:        55250,  "b+e+e+g+",
        !           590:        55500,  "b+cd++j+",
        !           591:        55750,  "b+bh-d-f-",
        !           592:        56250,  "c+d-b+j-",
        !           593:        56500,  "c+d+c+i+",
        !           594:        56750,  "b+e+d++h-",
        !           595:        57000,  "b+d+g-f+",
        !           596:        57250,  "b+f-m+d-",
        !           597:        57750,  "b+i+c+e-",
        !           598:        58000,  "b+e+d+h+",
        !           599:        58250,  "c+b+g+g+",
        !           600:        58750,  "d-e-j--e+",
        !           601:        59000,  "d-i-+e+",
        !           602:        59250,  "e--h-m+",
        !           603:        59500,  "c+c-h+f-",
        !           604:        59750,  "b+bh-e+i-",
        !           605:        60250,  "b+bh-e-e-",
        !           606:        60500,  "c+c-g-g-",
        !           607:        60750,  "b+e-l-e-",
        !           608:        61250,  "b+g-g-c+",
        !           609:        61750,  "b+g-c+g+",
        !           610:        62250,  "f--+c-i-",
        !           611:        62750,  "e+f--+g+",
        !           612:        64750,  "b+f+d+p-",
        !           613: };
        !           614: int    hintabsize      = nelem(hintab);

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.