![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to diff1.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / d / bin / diff|
Return to diff1.c CVS log | Up to [MW Coherent from dump] / coherent / d / bin / diff |
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.