1 5993a8f2 2003-11-23 devnull #include <u.h>
2 5993a8f2 2003-11-23 devnull #include <libc.h>
3 5993a8f2 2003-11-23 devnull #include <bio.h>
4 5993a8f2 2003-11-23 devnull #include "diff.h"
6 5993a8f2 2003-11-23 devnull /* diff - differential file comparison
8 5993a8f2 2003-11-23 devnull * Uses an algorithm due to Harold Stone, which finds
9 5993a8f2 2003-11-23 devnull * a pair of longest identical subsequences in the two
12 5993a8f2 2003-11-23 devnull * The major goal is to generate the match vector J.
13 5993a8f2 2003-11-23 devnull * J[i] is the index of the line in file1 corresponding
14 5993a8f2 2003-11-23 devnull * to line i file0. J[i] = 0 if there is no
15 5993a8f2 2003-11-23 devnull * such line in file1.
17 5993a8f2 2003-11-23 devnull * Lines are hashed so as to work in core. All potential
18 5993a8f2 2003-11-23 devnull * matches are located by sorting the lines of each file
19 5993a8f2 2003-11-23 devnull * on the hash (called value). In particular, this
20 5993a8f2 2003-11-23 devnull * collects the equivalence classes in file1 together.
21 5993a8f2 2003-11-23 devnull * Subroutine equiv replaces the value of each line in
22 fa325e9b 2020-01-10 cross * file0 by the index of the first element of its
23 5993a8f2 2003-11-23 devnull * matching equivalence in (the reordered) file1.
24 5993a8f2 2003-11-23 devnull * To save space equiv squeezes file1 into a single
25 5993a8f2 2003-11-23 devnull * array member in which the equivalence classes
26 5993a8f2 2003-11-23 devnull * are simply concatenated, except that their first
27 5993a8f2 2003-11-23 devnull * members are flagged by changing sign.
29 5993a8f2 2003-11-23 devnull * Next the indices that point into member are unsorted into
30 5993a8f2 2003-11-23 devnull * array class according to the original order of file0.
32 5993a8f2 2003-11-23 devnull * The cleverness lies in routine stone. This marches
33 5993a8f2 2003-11-23 devnull * through the lines of file0, developing a vector klist
34 5993a8f2 2003-11-23 devnull * of "k-candidates". At step i a k-candidate is a matched
35 5993a8f2 2003-11-23 devnull * pair of lines x,y (x in file0 y in file1) such that
36 5993a8f2 2003-11-23 devnull * there is a common subsequence of lenght k
37 fa325e9b 2020-01-10 cross * between the first i lines of file0 and the first y
38 5993a8f2 2003-11-23 devnull * lines of file1, but there is no such subsequence for
39 5993a8f2 2003-11-23 devnull * any smaller y. x is the earliest possible mate to y
40 5993a8f2 2003-11-23 devnull * that occurs in such a subsequence.
42 5993a8f2 2003-11-23 devnull * Whenever any of the members of the equivalence class of
43 fa325e9b 2020-01-10 cross * lines in file1 matable to a line in file0 has serial number
44 fa325e9b 2020-01-10 cross * less than the y of some k-candidate, that k-candidate
45 fa325e9b 2020-01-10 cross * with the smallest such y is replaced. The new
46 5993a8f2 2003-11-23 devnull * k-candidate is chained (via pred) to the current
47 5993a8f2 2003-11-23 devnull * k-1 candidate so that the actual subsequence can
48 5993a8f2 2003-11-23 devnull * be recovered. When a member has serial number greater
49 5993a8f2 2003-11-23 devnull * that the y of all k-candidates, the klist is extended.
50 5993a8f2 2003-11-23 devnull * At the end, the longest subsequence is pulled out
51 5993a8f2 2003-11-23 devnull * and placed in the array J by unravel.
53 5993a8f2 2003-11-23 devnull * With J in hand, the matches there recorded are
54 5993a8f2 2003-11-23 devnull * check'ed against reality to assure that no spurious
55 5993a8f2 2003-11-23 devnull * matches have crept in due to hashing. If they have,
56 5993a8f2 2003-11-23 devnull * they are broken, and "jackpot " is recorded--a harmless
57 5993a8f2 2003-11-23 devnull * matter except that a true match for a spuriously
58 5993a8f2 2003-11-23 devnull * mated line may now be unnecessarily reported as a change.
60 5993a8f2 2003-11-23 devnull * Much of the complexity of the program comes simply
61 5993a8f2 2003-11-23 devnull * from trying to minimize core utilization and
62 5993a8f2 2003-11-23 devnull * maximize the range of doable problems by dynamically
63 5993a8f2 2003-11-23 devnull * allocating what is needed and reusing what is not.
64 5993a8f2 2003-11-23 devnull * The core requirements for problems larger than somewhat
65 5993a8f2 2003-11-23 devnull * are (in words) 2*length(file0) + length(file1) +
66 5993a8f2 2003-11-23 devnull * 3*(number of k-candidates installed), typically about
67 fa325e9b 2020-01-10 cross * 6n words for files of length n.
70 d4a4b66a 2020-05-19 rsc #define class diffclass
72 5993a8f2 2003-11-23 devnull /* TIDY THIS UP */
73 5993a8f2 2003-11-23 devnull struct cand {
76 5993a8f2 2003-11-23 devnull int pred;
78 5993a8f2 2003-11-23 devnull struct line {
79 5993a8f2 2003-11-23 devnull int serial;
80 5993a8f2 2003-11-23 devnull int value;
81 5993a8f2 2003-11-23 devnull } *file[2], line;
82 5993a8f2 2003-11-23 devnull int len[2];
83 5993a8f2 2003-11-23 devnull int binary;
84 5993a8f2 2003-11-23 devnull struct line *sfile[2]; /*shortened by pruning common prefix and suffix*/
85 5993a8f2 2003-11-23 devnull int slen[2];
86 5993a8f2 2003-11-23 devnull int pref, suff; /*length of prefix and suffix*/
87 5993a8f2 2003-11-23 devnull int *class; /*will be overlaid on file[0]*/
88 5993a8f2 2003-11-23 devnull int *member; /*will be overlaid on file[1]*/
89 5993a8f2 2003-11-23 devnull int *klist; /*will be overlaid on file[0] after class*/
90 5993a8f2 2003-11-23 devnull struct cand *clist; /* merely a free storage pot for candidates */
91 5993a8f2 2003-11-23 devnull int clen;
92 5993a8f2 2003-11-23 devnull int *J; /*will be overlaid on class*/
93 5993a8f2 2003-11-23 devnull long *ixold; /*will be overlaid on klist*/
94 5993a8f2 2003-11-23 devnull long *ixnew; /*will be overlaid on file[1]*/
95 5993a8f2 2003-11-23 devnull /* END OF SOME TIDYING */
97 fa325e9b 2020-01-10 cross static void
98 5993a8f2 2003-11-23 devnull sort(struct line *a, int n) /*shellsort CACM #201*/
101 5993a8f2 2003-11-23 devnull struct line *ai, *aim, *j, *k;
102 5993a8f2 2003-11-23 devnull struct line w;
106 5993a8f2 2003-11-23 devnull for (i = 1; i <= n; i *= 2)
107 5993a8f2 2003-11-23 devnull m = 2*i - 1;
108 5993a8f2 2003-11-23 devnull for (m /= 2; m != 0; m /= 2) {
109 5993a8f2 2003-11-23 devnull k = a+(n-m);
110 5993a8f2 2003-11-23 devnull for (j = a+1; j <= k; j++) {
112 5993a8f2 2003-11-23 devnull aim = ai+m;
114 5993a8f2 2003-11-23 devnull if (aim->value > ai->value ||
115 5993a8f2 2003-11-23 devnull aim->value == ai->value &&
116 5993a8f2 2003-11-23 devnull aim->serial > ai->serial)
118 5993a8f2 2003-11-23 devnull w = *ai;
119 5993a8f2 2003-11-23 devnull *ai = *aim;
120 5993a8f2 2003-11-23 devnull *aim = w;
122 5993a8f2 2003-11-23 devnull aim = ai;
123 5993a8f2 2003-11-23 devnull ai -= m;
124 5993a8f2 2003-11-23 devnull } while (ai > a && aim >= ai);
129 5993a8f2 2003-11-23 devnull static void
130 5993a8f2 2003-11-23 devnull unsort(struct line *f, int l, int *b)
135 5993a8f2 2003-11-23 devnull a = MALLOC(int, (l+1));
136 5993a8f2 2003-11-23 devnull for(i=1;i<=l;i++)
137 5993a8f2 2003-11-23 devnull a[f[i].serial] = f[i].value;
138 5993a8f2 2003-11-23 devnull for(i=1;i<=l;i++)
139 5993a8f2 2003-11-23 devnull b[i] = a[i];
140 5993a8f2 2003-11-23 devnull FREE(a);
143 5993a8f2 2003-11-23 devnull static void
144 5993a8f2 2003-11-23 devnull prune(void)
146 5993a8f2 2003-11-23 devnull int i,j;
148 5993a8f2 2003-11-23 devnull for(pref=0;pref<len[0]&&pref<len[1]&&
149 5993a8f2 2003-11-23 devnull file[0][pref+1].value==file[1][pref+1].value;
150 5993a8f2 2003-11-23 devnull pref++ ) ;
151 5993a8f2 2003-11-23 devnull for(suff=0;suff<len[0]-pref&&suff<len[1]-pref&&
152 5993a8f2 2003-11-23 devnull file[0][len[0]-suff].value==file[1][len[1]-suff].value;
153 5993a8f2 2003-11-23 devnull suff++) ;
154 5993a8f2 2003-11-23 devnull for(j=0;j<2;j++) {
155 5993a8f2 2003-11-23 devnull sfile[j] = file[j]+pref;
156 5993a8f2 2003-11-23 devnull slen[j] = len[j]-pref-suff;
157 5993a8f2 2003-11-23 devnull for(i=0;i<=slen[j];i++)
158 5993a8f2 2003-11-23 devnull sfile[j][i].serial = i;
162 5993a8f2 2003-11-23 devnull static void
163 5993a8f2 2003-11-23 devnull equiv(struct line *a, int n, struct line *b, int m, int *c)
165 5993a8f2 2003-11-23 devnull int i, j;
167 5993a8f2 2003-11-23 devnull i = j = 1;
168 5993a8f2 2003-11-23 devnull while(i<=n && j<=m) {
169 5993a8f2 2003-11-23 devnull if(a[i].value < b[j].value)
170 5993a8f2 2003-11-23 devnull a[i++].value = 0;
171 5993a8f2 2003-11-23 devnull else if(a[i].value == b[j].value)
172 5993a8f2 2003-11-23 devnull a[i++].value = j;
176 5993a8f2 2003-11-23 devnull while(i <= n)
177 5993a8f2 2003-11-23 devnull a[i++].value = 0;
178 5993a8f2 2003-11-23 devnull b[m+1].value = 0;
180 5993a8f2 2003-11-23 devnull while(++j <= m) {
181 5993a8f2 2003-11-23 devnull c[j] = -b[j].serial;
182 5993a8f2 2003-11-23 devnull while(b[j+1].value == b[j].value) {
184 5993a8f2 2003-11-23 devnull c[j] = b[j].serial;
187 5993a8f2 2003-11-23 devnull c[j] = -1;
190 5993a8f2 2003-11-23 devnull static int
191 5993a8f2 2003-11-23 devnull newcand(int x, int y, int pred)
193 5993a8f2 2003-11-23 devnull struct cand *q;
195 5993a8f2 2003-11-23 devnull clist = REALLOC(clist, struct cand, (clen+1));
196 5993a8f2 2003-11-23 devnull q = clist + clen;
197 5993a8f2 2003-11-23 devnull q->x = x;
198 5993a8f2 2003-11-23 devnull q->y = y;
199 5993a8f2 2003-11-23 devnull q->pred = pred;
200 5993a8f2 2003-11-23 devnull return clen++;
203 5993a8f2 2003-11-23 devnull static int
204 5993a8f2 2003-11-23 devnull search(int *c, int k, int y)
206 5993a8f2 2003-11-23 devnull int i, j, l;
209 5993a8f2 2003-11-23 devnull if(clist[c[k]].y < y) /*quick look for typical case*/
210 5993a8f2 2003-11-23 devnull return k+1;
212 5993a8f2 2003-11-23 devnull j = k+1;
213 5993a8f2 2003-11-23 devnull while((l=(i+j)/2) > i) {
214 5993a8f2 2003-11-23 devnull t = clist[c[l]].y;
215 5993a8f2 2003-11-23 devnull if(t > y)
217 5993a8f2 2003-11-23 devnull else if(t < y)
220 5993a8f2 2003-11-23 devnull return l;
222 5993a8f2 2003-11-23 devnull return l+1;
225 5993a8f2 2003-11-23 devnull static int
226 5993a8f2 2003-11-23 devnull stone(int *a, int n, int *b, int *c)
228 5993a8f2 2003-11-23 devnull int i, k,y;
229 5993a8f2 2003-11-23 devnull int j, l;
230 5993a8f2 2003-11-23 devnull int oldc, tc;
231 5993a8f2 2003-11-23 devnull int oldl;
234 5993a8f2 2003-11-23 devnull c[0] = newcand(0,0,0);
235 5993a8f2 2003-11-23 devnull for(i=1; i<=n; i++) {
236 5993a8f2 2003-11-23 devnull j = a[i];
237 5993a8f2 2003-11-23 devnull if(j==0)
238 5993a8f2 2003-11-23 devnull continue;
239 5993a8f2 2003-11-23 devnull y = -b[j];
240 5993a8f2 2003-11-23 devnull oldl = 0;
241 5993a8f2 2003-11-23 devnull oldc = c[0];
243 5993a8f2 2003-11-23 devnull if(y <= clist[oldc].y)
244 5993a8f2 2003-11-23 devnull continue;
245 5993a8f2 2003-11-23 devnull l = search(c, k, y);
246 5993a8f2 2003-11-23 devnull if(l!=oldl+1)
247 5993a8f2 2003-11-23 devnull oldc = c[l-1];
248 5993a8f2 2003-11-23 devnull if(l<=k) {
249 5993a8f2 2003-11-23 devnull if(clist[c[l]].y <= y)
250 5993a8f2 2003-11-23 devnull continue;
251 5993a8f2 2003-11-23 devnull tc = c[l];
252 5993a8f2 2003-11-23 devnull c[l] = newcand(i,y,oldc);
253 5993a8f2 2003-11-23 devnull oldc = tc;
254 5993a8f2 2003-11-23 devnull oldl = l;
255 5993a8f2 2003-11-23 devnull } else {
256 5993a8f2 2003-11-23 devnull c[l] = newcand(i,y,oldc);
260 5993a8f2 2003-11-23 devnull } while((y=b[++j]) > 0);
262 5993a8f2 2003-11-23 devnull return k;
265 5993a8f2 2003-11-23 devnull static void
266 5993a8f2 2003-11-23 devnull unravel(int p)
269 5993a8f2 2003-11-23 devnull struct cand *q;
271 5993a8f2 2003-11-23 devnull for(i=0; i<=len[0]; i++) {
272 5993a8f2 2003-11-23 devnull if (i <= pref)
273 5993a8f2 2003-11-23 devnull J[i] = i;
274 5993a8f2 2003-11-23 devnull else if (i > len[0]-suff)
275 5993a8f2 2003-11-23 devnull J[i] = i+len[1]-len[0];
277 5993a8f2 2003-11-23 devnull J[i] = 0;
279 5993a8f2 2003-11-23 devnull for(q=clist+p;q->y!=0;q=clist+q->pred)
280 5993a8f2 2003-11-23 devnull J[q->x+pref] = q->y+pref;
283 5993a8f2 2003-11-23 devnull static void
284 5993a8f2 2003-11-23 devnull output(void)
286 5993a8f2 2003-11-23 devnull int m, i0, i1, j0, j1;
288 5993a8f2 2003-11-23 devnull m = len[0];
289 5993a8f2 2003-11-23 devnull J[0] = 0;
290 5993a8f2 2003-11-23 devnull J[m+1] = len[1]+1;
291 5993a8f2 2003-11-23 devnull if (mode != 'e') {
292 5993a8f2 2003-11-23 devnull for (i0 = 1; i0 <= m; i0 = i1+1) {
293 5993a8f2 2003-11-23 devnull while (i0 <= m && J[i0] == J[i0-1]+1)
295 5993a8f2 2003-11-23 devnull j0 = J[i0-1]+1;
296 5993a8f2 2003-11-23 devnull i1 = i0-1;
297 5993a8f2 2003-11-23 devnull while (i1 < m && J[i1+1] == 0)
299 5993a8f2 2003-11-23 devnull j1 = J[i1+1]-1;
300 5993a8f2 2003-11-23 devnull J[i1] = j1;
301 5993a8f2 2003-11-23 devnull change(i0, i1, j0, j1);
305 5993a8f2 2003-11-23 devnull for (i0 = m; i0 >= 1; i0 = i1-1) {
306 5993a8f2 2003-11-23 devnull while (i0 >= 1 && J[i0] == J[i0+1]-1 && J[i0])
308 5993a8f2 2003-11-23 devnull j0 = J[i0+1]-1;
309 5993a8f2 2003-11-23 devnull i1 = i0+1;
310 5993a8f2 2003-11-23 devnull while (i1 > 1 && J[i1-1] == 0)
312 5993a8f2 2003-11-23 devnull j1 = J[i1-1]+1;
313 5993a8f2 2003-11-23 devnull J[i1] = j1;
314 5993a8f2 2003-11-23 devnull change(i1 , i0, j1, j0);
317 5993a8f2 2003-11-23 devnull if (m == 0)
318 5993a8f2 2003-11-23 devnull change(1, 0, 1, len[1]);
319 4ac5f249 2005-01-26 devnull flushchanges();
322 5993a8f2 2003-11-23 devnull #define BUF 4096
323 5993a8f2 2003-11-23 devnull static int
324 5993a8f2 2003-11-23 devnull cmp(Biobuf* b1, Biobuf* b2)
327 5993a8f2 2003-11-23 devnull uchar buf1[BUF], buf2[BUF];
328 5993a8f2 2003-11-23 devnull int f1, f2;
329 5993a8f2 2003-11-23 devnull vlong nc = 1;
330 5993a8f2 2003-11-23 devnull uchar *b1s, *b1e, *b2s, *b2e;
332 5993a8f2 2003-11-23 devnull f1 = Bfildes(b1);
333 5993a8f2 2003-11-23 devnull f2 = Bfildes(b2);
334 5993a8f2 2003-11-23 devnull seek(f1, 0, 0);
335 5993a8f2 2003-11-23 devnull seek(f2, 0, 0);
336 5993a8f2 2003-11-23 devnull b1s = b1e = buf1;
337 5993a8f2 2003-11-23 devnull b2s = b2e = buf2;
338 5993a8f2 2003-11-23 devnull for(;;){
339 5993a8f2 2003-11-23 devnull if(b1s >= b1e){
340 5993a8f2 2003-11-23 devnull if(b1s >= &buf1[BUF])
341 5993a8f2 2003-11-23 devnull b1s = buf1;
342 5993a8f2 2003-11-23 devnull n = read(f1, b1s, &buf1[BUF] - b1s);
343 5993a8f2 2003-11-23 devnull b1e = b1s + n;
345 5993a8f2 2003-11-23 devnull if(b2s >= b2e){
346 5993a8f2 2003-11-23 devnull if(b2s >= &buf2[BUF])
347 5993a8f2 2003-11-23 devnull b2s = buf2;
348 5993a8f2 2003-11-23 devnull n = read(f2, b2s, &buf2[BUF] - b2s);
349 5993a8f2 2003-11-23 devnull b2e = b2s + n;
351 5993a8f2 2003-11-23 devnull n = b2e - b2s;
352 5993a8f2 2003-11-23 devnull if(n > b1e - b1s)
353 5993a8f2 2003-11-23 devnull n = b1e - b1s;
354 5993a8f2 2003-11-23 devnull if(n <= 0)
356 5993a8f2 2003-11-23 devnull if(memcmp((void *)b1s, (void *)b2s, n) != 0){
357 5993a8f2 2003-11-23 devnull return 1;
359 5993a8f2 2003-11-23 devnull nc += n;
360 5993a8f2 2003-11-23 devnull b1s += n;
361 5993a8f2 2003-11-23 devnull b2s += n;
363 5993a8f2 2003-11-23 devnull if(b1e - b1s == b2e - b2s)
364 5993a8f2 2003-11-23 devnull return 0;
369 5993a8f2 2003-11-23 devnull diffreg(char *f, char *t)
371 5993a8f2 2003-11-23 devnull Biobuf *b0, *b1;
374 5993a8f2 2003-11-23 devnull binary = 0;
375 5993a8f2 2003-11-23 devnull b0 = prepare(0, f);
376 5993a8f2 2003-11-23 devnull if (!b0)
378 5993a8f2 2003-11-23 devnull b1 = prepare(1, t);
379 5993a8f2 2003-11-23 devnull if (!b1) {
380 5993a8f2 2003-11-23 devnull FREE(file[0]);
381 5993a8f2 2003-11-23 devnull Bterm(b0);
384 5993a8f2 2003-11-23 devnull if (binary){
385 cbeb0b26 2006-04-01 devnull /* could use b0 and b1 but this is simpler. */
386 5993a8f2 2003-11-23 devnull if (cmp(b0, b1))
387 5993a8f2 2003-11-23 devnull print("binary files %s %s differ\n", f, t);
388 5993a8f2 2003-11-23 devnull Bterm(b0);
389 5993a8f2 2003-11-23 devnull Bterm(b1);
392 5993a8f2 2003-11-23 devnull clen = 0;
393 5993a8f2 2003-11-23 devnull prune();
394 5993a8f2 2003-11-23 devnull sort(sfile[0], slen[0]);
395 5993a8f2 2003-11-23 devnull sort(sfile[1], slen[1]);
397 5993a8f2 2003-11-23 devnull member = (int *)file[1];
398 5993a8f2 2003-11-23 devnull equiv(sfile[0], slen[0], sfile[1], slen[1], member);
399 5993a8f2 2003-11-23 devnull member = REALLOC(member, int, slen[1]+2);
401 5993a8f2 2003-11-23 devnull class = (int *)file[0];
402 5993a8f2 2003-11-23 devnull unsort(sfile[0], slen[0], class);
403 5993a8f2 2003-11-23 devnull class = REALLOC(class, int, slen[0]+2);
405 5993a8f2 2003-11-23 devnull klist = MALLOC(int, slen[0]+2);
406 5993a8f2 2003-11-23 devnull clist = MALLOC(struct cand, 1);
407 5993a8f2 2003-11-23 devnull k = stone(class, slen[0], member, klist);
408 5993a8f2 2003-11-23 devnull FREE(member);
409 5993a8f2 2003-11-23 devnull FREE(class);
411 5993a8f2 2003-11-23 devnull J = MALLOC(int, len[0]+2);
412 5993a8f2 2003-11-23 devnull unravel(klist[k]);
413 5993a8f2 2003-11-23 devnull FREE(clist);
414 5993a8f2 2003-11-23 devnull FREE(klist);
416 5993a8f2 2003-11-23 devnull ixold = MALLOC(long, len[0]+2);
417 5993a8f2 2003-11-23 devnull ixnew = MALLOC(long, len[1]+2);
418 5993a8f2 2003-11-23 devnull Bseek(b0, 0, 0); Bseek(b1, 0, 0);
419 5993a8f2 2003-11-23 devnull check(b0, b1);
420 5993a8f2 2003-11-23 devnull output();
421 5993a8f2 2003-11-23 devnull FREE(J); FREE(ixold); FREE(ixnew);
422 5993a8f2 2003-11-23 devnull Bterm(b0); Bterm(b1); /* ++++ */
