Return to diff1.c CVS log

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

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

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