![[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 / z8001|
Return to diff1.c CVS log | Up to [MW Coherent from dump] / coherent / d / bin / diff / z8001 |
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.