Return to diff1.c CVS log

Up to [MW Coherent from dump] / coherent / d / bin / diff

Annotation of coherent/d/bin/diff/diff1.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Parts of diff that depend on the minimal common
        !             3:  * subsequence algorithm of Hirschberg.
        !             4:  */
        !             5: 
        !             6: #include "diff.h"
        !             7: #include <sys/mdata.h>
        !             8: 
        !             9: #define        NSBRK   512             /* Size of each sbrk -- allocator */
        !            10: #define BADSBRK ((char *)-1)           /* fail return from sbrk */
        !            11:        /* Marks last of each hash-equivalence class */
        !            12: #define        LAST    ((unsigned)MININT)
        !            13:                                /* Assume MININT is a single bit */
        !            14: 
        !            15: static char    partial[] = "diff: partial line omitted from %s\n";
        !            16: static char    jackpot[] = "Jackpot %d %d\n";
        !            17: 
        !            18: /*
        !            19:  * Tables for the table-driven CRC16 algorithm.
        !            20:  * This is used as the hash of the input lines
        !            21:  * and should be relatively uniform statistically.
        !            22:  */
        !            23: static unsigned short crctab1[] = {
        !            24:        0000000,        0140301,        0140601,        0000500,
        !            25:        0141401,        0001700,        0001200,        0141101,
        !            26:        0143001,        0003300,        0003600,        0143501,
        !            27:        0002400,        0142701,        0142201,        0002100
        !            28: };
        !            29: 
        !            30: static unsigned short crctab2[] = {
        !            31:        0000000,        0146001,        0154001,        0012000,
        !            32:        0170001,        0036000,        0024000,        0162001,
        !            33:        0120001,        0066000,        0074000,        0132001,
        !            34:        0050000,        0116001,        0104001,        0043000
        !            35: };
        !            36: 
        !            37: typedef        struct  LINES {
        !            38:        unsigned        l_num;
        !            39:        unsigned short  l_hash;
        !            40: }      LINES;
        !            41: 
        !            42: /*
        !            43:  * A K-candidate entry
        !            44:  */
        !            45: typedef        struct  CAND {
        !            46:        unsigned        a;
        !            47:        unsigned        b;
        !            48:        struct CAND     *prev;
        !            49: }      CAND;
        !            50: 
        !            51: int    compar();
        !            52: unsigned short inhash();
        !            53: CAND   *candidate();
        !            54: 
        !            55: char   line1[LSIZE];           /* First file's input line buffer */
        !            56: char   line2[LSIZE];
        !            57: char   nomem[] = "Out of memory";
        !            58: 
        !            59: int    *allrp;
        !            60: int    *allep;
        !            61: 
        !            62: /*
        !            63:  * Called to invoke heuristic version of
        !            64:  * diff.
        !            65:  */
        !            66: diffh(args)
        !            67: char **args;
        !            68: {
        !            69: #ifdef COHERENT
        !            70:        execv("/usr/lib/diffh", args);
        !            71: #endif
        !            72: #ifdef MSDOS
        !            73: #define        MAXTAIL 128             /* Maximum command tail length */
        !            74:        char tail[MAXTAIL];
        !            75: 
        !            76:        tail[0] = '\0';
        !            77:        while (*++args != NULL) {
        !            78:                if (strlen(tail) + strlen(*args) + 2 > MAXTAIL)
        !            79:                        cerr("command tail too long");
        !            80:                if (tail[0] != '\0')
        !            81:                        strcat(tail, " ");
        !            82:                strcat(tail, *args);
        !            83:        }
        !            84:        exit(execall("diffh", tail));
        !            85: #endif
        !            86:        cerr("-h doesn't work");
        !            87: }
        !            88: 
        !            89: /*
        !            90:  * Routine is given two file streams and
        !            91:  * it produces the minimal list of
        !            92:  * differences by the Hirschberg algorithm
        !            93:  */
        !            94: diff(fp1, fp2)
        !            95: FILE *fp1, *fp2;
        !            96: {
        !            97:        register unsigned short hash;
        !            98:        register unsigned ln1;
        !            99:        register unsigned ln2;
        !           100:        register LINES *V;
        !           101:        register unsigned *P;
        !           102:        register unsigned *E;
        !           103:        register unsigned *K;
        !           104:        register unsigned *J;
        !           105: 
        !           106:        /*
        !           107:         * Calculate the hash tables for
        !           108:         * the second file
        !           109:         * and sort with hash as primary key,
        !           110:         * line-number secondary.
        !           111:         */
        !           112:        V = (LINES *)alloc(sizeof (LINES));
        !           113:        V->l_num = V->l_hash = 0;       /* unneeded? */
        !           114:        ln2 = 0;
        !           115:        while ((hash = inhash(fp2, fn2)) != 0) {
        !           116:                register LINES *Vp;
        !           117: 
        !           118:                Vp = (LINES *)alloc(sizeof (LINES));
        !           119:                Vp->l_num = ++ln2;
        !           120:                Vp->l_hash = hash;
        !           121:        }
        !           122:        qsort(V+1, ln2, sizeof (LINES), compar);
        !           123:        /*
        !           124:         * Read first file, building
        !           125:         * a table per line of
        !           126:         * pointers to the first elements
        !           127:         * of the hash-equivalent list in file2.
        !           128:         */
        !           129:        P = (unsigned *)alloc(sizeof (unsigned));
        !           130:        for (ln1=0; (hash = inhash(fp1, fn1))!=0; ln1++) {
        !           131:                register unsigned *Pp;
        !           132:                register unsigned lo, mid, hi;
        !           133: 
        !           134:                Pp = (unsigned *)alloc(sizeof(unsigned));
        !           135:                lo = 1;
        !           136:                hi = ln2;
        !           137:                while (lo <= hi) {
        !           138:                        mid = (lo+hi)/2;
        !           139:                        if (hash <= V[mid].l_hash)
        !           140:                                hi = mid-1; 
        !           141:                        else
        !           142:                                lo = mid+1;
        !           143:                }
        !           144:                if (hi!=0 && V[hi].l_hash==V[hi+1].l_hash)
        !           145:                        cerr("fatal search botch");
        !           146:                if (hash == V[++hi].l_hash)
        !           147:                        *Pp = hi; else
        !           148:                        *Pp = 0;
        !           149:        }
        !           150: 
        !           151:        /*
        !           152:         * Throw away the hash values.
        !           153:         * Mark the last line of each hash-equivalent
        !           154:         * class of lines and fake line 0.
        !           155:         */
        !           156:        {
        !           157:                register unsigned *Ep, *eEp;
        !           158:                register LINES *Vp;
        !           159: 
        !           160:                E = V;
        !           161:                E[0] = LAST;
        !           162:                for (Ep=E+1, Vp=V+1, eEp=&E[ln2]; Ep <= eEp; Vp++, Ep++) {
        !           163:                        *Ep = Vp->l_num;
        !           164:                        if (Ep==eEp || Vp->l_hash!=(Vp+1)->l_hash)
        !           165:                                *Ep |= LAST;
        !           166:                }
        !           167:        }
        !           168:        {
        !           169:                register int i;
        !           170:                register unsigned *Pp;
        !           171: 
        !           172:                Pp = &E[ln2+3];
        !           173:                for (i=1; i<=ln1; i++)
        !           174:                        Pp[i] = P[i];
        !           175:                P = Pp;
        !           176:                ralloc(&Pp[ln1+1]);
        !           177:        }
        !           178:        /*
        !           179:         * Set up to build list of K-candidates for
        !           180:         * all k.  The K table overwrites P (when
        !           181:         * we add K[k+2] to the table we no longer
        !           182:         * need P[k].
        !           183:         */
        !           184:        {
        !           185:                register int k;
        !           186:                register int i;
        !           187:                register CAND *cp;
        !           188: 
        !           189:                K = &E[ln2+1];
        !           190:                K[0] = candidate(0, 0, NULL);
        !           191:                K[1] = candidate(ln1+1, ln2+1, NULL);
        !           192:                k = 0;
        !           193:                for (i=1; i<=ln1; i++)
        !           194:                        if (P[i] != 0)
        !           195:                                k = merge(K, k, i, E, P[i]);
        !           196: 
        !           197:                /*
        !           198:                 * `k' is the length of the maximal
        !           199:                 * common subsequence, thus K[k] points
        !           200:                 * to the list of lines in the subsequnce.
        !           201:                 * Store the list in `J' in a handier
        !           202:                 * format.  E, K (all but K[k]) and P
        !           203:                 * are redundant so J overlays them.
        !           204:                 */
        !           205:                cp = K[k];
        !           206:                J = E;
        !           207:                for (i=0; i<=ln1; i++)
        !           208:                        J[i] = 0;
        !           209:                J[ln1+1] = ln2+1;       /* fence */
        !           210:                while (cp != NULL) {
        !           211:                        J[cp->a] = cp->b;
        !           212:                        cp = cp->prev;
        !           213:                }
        !           214:        }
        !           215:        {
        !           216:                register unsigned i, j, k, l;
        !           217: 
        !           218:                /*
        !           219:                 * Matching lines are now stored as pairs
        !           220:                 * (i, J[i]), J[i]!=0.  Produce output
        !           221:                 * scripts and look for jackpots.
        !           222:                 */
        !           223:                rewind(fp1);
        !           224:                rewind(fp2);
        !           225:                fgets(line1, LSIZE, fp1);
        !           226:                fgets(line2, LSIZE, fp2);
        !           227:                for (i=j=1; i<=ln1 || j<=ln2; ) {
        !           228:                        if (j == J[i]) {
        !           229:                                if (!(*equal)(line1, line2)) {
        !           230:                                        /*
        !           231:                                         * This can be avoided at
        !           232:                                         * the expense of another
        !           233:                                         * pass.  So we settle for this
        !           234:                                         * potentially non-minimal result.
        !           235:                                         * Possibly this printout could
        !           236:                                         * disappear.
        !           237:                                         */
        !           238:                                        fprintf(stderr, jackpot, i, j);
        !           239:                                        change(i, i, j, j);
        !           240:                                        text1(line1);
        !           241:                                        prsep();
        !           242:                                        text2(line2);
        !           243:                                        prend();
        !           244:                                } else
        !           245:                                        text(line1);
        !           246:                                i++;
        !           247:                                fgets(line1, LSIZE, fp1);
        !           248:                                j++;
        !           249:                                fgets(line2, LSIZE, fp2);
        !           250:                                continue;
        !           251:                        }
        !           252:                        for (k=i; J[k]==0; k++)
        !           253:                                ;
        !           254:                        l = J[k];
        !           255:                        if (i == k)
        !           256:                                append(i, j, l-1);
        !           257:                        else if (j == l)
        !           258:                                delete(i, k-1, j);
        !           259:                        else
        !           260:                                change(i, k-1, j, l-1);
        !           261:                        while (i != k) {
        !           262:                                text1(line1);
        !           263:                                i++;
        !           264:                                fgets(line1, LSIZE, fp1);
        !           265:                        }
        !           266:                        prsep();
        !           267:                        while (j != l) {
        !           268:                                text2(line2);
        !           269:                                j++;
        !           270:                                fgets(line2, LSIZE, fp2);
        !           271:                        }
        !           272:                        prend();
        !           273:                }
        !           274:        }
        !           275: }
        !           276: 
        !           277: /*
        !           278:  * Read input characters and hash for each
        !           279:  * line.  Return the hash value computed
        !           280:  * using CRC-16 methods.  A zero value
        !           281:  * means EOF or error and thus will not
        !           282:  * be returned as a hash value.
        !           283:  */
        !           284: unsigned short
        !           285: inhash(fp, fn)
        !           286: register FILE *fp;
        !           287: char *fn;
        !           288: {
        !           289:        register int c;
        !           290:        register int tmp;
        !           291:        register int short hash;
        !           292:        register int space;
        !           293: 
        !           294:        space = hash = 0;
        !           295:        while ((c = getc(fp)) != '\n') {
        !           296:                if (c == EOF) {
        !           297:                        if (hash != 0)
        !           298:                                fprintf(stderr, partial, fn);
        !           299:                        return (0);
        !           300:                }
        !           301:                if (bflag && (c==' ' || c=='\t')) {
        !           302:                        space++;
        !           303:                        continue;
        !           304:                }
        !           305:        compute:
        !           306:                tmp = c^hash;
        !           307:                hash = (hash>>8) ^ crctab1[tmp&017] ^ crctab2[(tmp&0360)>>4];
        !           308:                if (space) {
        !           309:                        c = ' ';
        !           310:                        space = 0;
        !           311:                        goto compute;
        !           312:                }
        !           313:        }
        !           314:        if (hash == 0)
        !           315:                hash++;
        !           316:        return (hash);
        !           317: }
        !           318: 
        !           319: /*
        !           320:  * Sort comparison routine.
        !           321:  * Hash value is primary key,
        !           322:  * line number secondary.
        !           323:  */
        !           324: compar(a, b)
        !           325: register LINES *a, *b;
        !           326: {
        !           327:        if (a->l_hash < b->l_hash)
        !           328:                return (-1);
        !           329:        if (a->l_hash > b->l_hash)
        !           330:                return (1);
        !           331:        if (a->l_num < b->l_num)
        !           332:                return (-1);
        !           333:        if (a->l_num > b->l_num)
        !           334:                return (1);
        !           335:        return (0);
        !           336: }
        !           337: 
        !           338: /*
        !           339:  * Build an entry in the K-candidates
        !           340:  * table
        !           341:  */
        !           342: CAND *
        !           343: candidate(a, b, prev)
        !           344: unsigned a;
        !           345: unsigned b;
        !           346: CAND *prev;
        !           347: {
        !           348:        register CAND *v;
        !           349: 
        !           350:        v = (CAND *)alloc(sizeof(CAND));
        !           351:        v->a = a;
        !           352:        v->b = b;
        !           353:        v->prev = prev;
        !           354:        return (v);
        !           355: }
        !           356: 
        !           357: /*
        !           358:  * The merge step, called for
        !           359:  * each index in file 1.
        !           360:  * `k' is index of last filled element
        !           361:  * of `K', `i' is current index in
        !           362:  * file 1, and `p' is first element
        !           363:  * of class of lines in file 2
        !           364:  * equivalent to line `i' by hash value.
        !           365:  */
        !           366: merge(K, k, i, E, p)
        !           367: CAND **K;
        !           368: unsigned k, i;
        !           369: unsigned *E;
        !           370: unsigned p;
        !           371: {
        !           372:        register unsigned r;
        !           373:        register CAND *c;
        !           374: 
        !           375:        r = 0;
        !           376:        c = K[0];
        !           377:        do {
        !           378:                register unsigned lo, mid, hi;
        !           379:                register unsigned j;
        !           380: 
        !           381:                j = E[p]&~LAST;
        !           382:                lo = r;
        !           383:                hi = k;
        !           384:                if (K[lo]->b >= j)
        !           385:                        continue;
        !           386:                while (lo <= hi) {
        !           387:                        mid = (lo+hi)/2;
        !           388:                        if (j <= K[mid]->b)
        !           389:                                hi = mid-1; else
        !           390:                                lo = mid+1;
        !           391:                }
        !           392:                if (K[hi]->b<j && j<=K[hi+1]->b) {
        !           393:                        if (j < K[hi+1]->b) {
        !           394: #if SIMUL
        !           395:                                register CAND *prev;
        !           396:                                prev = K[hi];
        !           397: #endif
        !           398:                                K[r] = c;
        !           399:                                r = hi+1;
        !           400: #if SIMUL
        !           401:                                c = candidate(i, j, prev);
        !           402: #else
        !           403:                                c = candidate(i, j, K[hi]);
        !           404: #endif
        !           405:                        }
        !           406:                        if (hi == k) {
        !           407:                                K[k+2] = K[k+1];
        !           408:                                k++;
        !           409:                                break;
        !           410:                        }
        !           411:                }
        !           412:        } while (!(E[p++] & LAST));
        !           413:        K[r] = c;
        !           414:        return (k);
        !           415: }
        !           416: 
        !           417: /*
        !           418:  * This allocator simply does sbrk calls so that
        !           419:  * it can grow (easily) the space as it needs without
        !           420:  * threading it.  It also checks and prints and error
        !           421:  * if out of space.
        !           422:  */
        !           423: char *
        !           424: alloc(size)
        !           425: register unsigned size;
        !           426: {
        !           427:        register int *cp;
        !           428: 
        !           429:        if ((size = (size+sizeof(int)-1)/sizeof(int)) == 0)
        !           430:                cerr(nomem);
        !           431:        if (allrp==NULL || allrp+size>=allep) {
        !           432:                if ((allep = (int *)sbrk(NSBRK)) == BADSBRK)
        !           433:                        cerr(nomem);
        !           434:                if (allrp == NULL)
        !           435:                        allrp = allep;
        !           436:                allep += NSBRK/sizeof(int);
        !           437:        }
        !           438:        cp = allrp;
        !           439:        allrp += size;
        !           440:        return (cp);
        !           441: }
        !           442: 
        !           443: /*
        !           444:  * Like the brk system call, reset
        !           445:  * current end of memory to `ep'.
        !           446:  */
        !           447: ralloc(ep)
        !           448: register int *ep;
        !           449: {
        !           450:        allrp = ep;
        !           451: }

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