| 1 | static char sccsid[] = "@(#)diffreg.c 4.18 %G%"; |
| 2 | |
| 3 | #include "diff.h" |
| 4 | /* |
| 5 | * diff - compare two files. |
| 6 | */ |
| 7 | |
| 8 | /* |
| 9 | * Uses an algorithm due to Harold Stone, which finds |
| 10 | * a pair of longest identical subsequences in the two |
| 11 | * files. |
| 12 | * |
| 13 | * The major goal is to generate the match vector J. |
| 14 | * J[i] is the index of the line in file1 corresponding |
| 15 | * to line i file0. J[i] = 0 if there is no |
| 16 | * such line in file1. |
| 17 | * |
| 18 | * Lines are hashed so as to work in core. All potential |
| 19 | * matches are located by sorting the lines of each file |
| 20 | * on the hash (called ``value''). In particular, this |
| 21 | * collects the equivalence classes in file1 together. |
| 22 | * Subroutine equiv replaces the value of each line in |
| 23 | * file0 by the index of the first element of its |
| 24 | * matching equivalence in (the reordered) file1. |
| 25 | * To save space equiv squeezes file1 into a single |
| 26 | * array member in which the equivalence classes |
| 27 | * are simply concatenated, except that their first |
| 28 | * members are flagged by changing sign. |
| 29 | * |
| 30 | * Next the indices that point into member are unsorted into |
| 31 | * array class according to the original order of file0. |
| 32 | * |
| 33 | * The cleverness lies in routine stone. This marches |
| 34 | * through the lines of file0, developing a vector klist |
| 35 | * of "k-candidates". At step i a k-candidate is a matched |
| 36 | * pair of lines x,y (x in file0 y in file1) such that |
| 37 | * there is a common subsequence of length k |
| 38 | * between the first i lines of file0 and the first y |
| 39 | * lines of file1, but there is no such subsequence for |
| 40 | * any smaller y. x is the earliest possible mate to y |
| 41 | * that occurs in such a subsequence. |
| 42 | * |
| 43 | * Whenever any of the members of the equivalence class of |
| 44 | * lines in file1 matable to a line in file0 has serial number |
| 45 | * less than the y of some k-candidate, that k-candidate |
| 46 | * with the smallest such y is replaced. The new |
| 47 | * k-candidate is chained (via pred) to the current |
| 48 | * k-1 candidate so that the actual subsequence can |
| 49 | * be recovered. When a member has serial number greater |
| 50 | * that the y of all k-candidates, the klist is extended. |
| 51 | * At the end, the longest subsequence is pulled out |
| 52 | * and placed in the array J by unravel |
| 53 | * |
| 54 | * With J in hand, the matches there recorded are |
| 55 | * check'ed against reality to assure that no spurious |
| 56 | * matches have crept in due to hashing. If they have, |
| 57 | * they are broken, and "jackpot" is recorded--a harmless |
| 58 | * matter except that a true match for a spuriously |
| 59 | * mated line may now be unnecessarily reported as a change. |
| 60 | * |
| 61 | * Much of the complexity of the program comes simply |
| 62 | * from trying to minimize core utilization and |
| 63 | * maximize the range of doable problems by dynamically |
| 64 | * allocating what is needed and reusing what is not. |
| 65 | * The core requirements for problems larger than somewhat |
| 66 | * are (in words) 2*length(file0) + length(file1) + |
| 67 | * 3*(number of k-candidates installed), typically about |
| 68 | * 6n words for files of length n. |
| 69 | */ |
| 70 | |
| 71 | #define prints(s) fputs(s,stdout) |
| 72 | |
| 73 | FILE *input[2]; |
| 74 | FILE *fopen(); |
| 75 | |
| 76 | struct cand { |
| 77 | int x; |
| 78 | int y; |
| 79 | int pred; |
| 80 | } cand; |
| 81 | struct line { |
| 82 | int serial; |
| 83 | int value; |
| 84 | } *file[2], line; |
| 85 | int len[2]; |
| 86 | struct line *sfile[2]; /* shortened by pruning common prefix and suffix */ |
| 87 | int slen[2]; |
| 88 | int pref, suff; /* length of prefix and suffix */ |
| 89 | int *class; /* will be overlaid on file[0] */ |
| 90 | int *member; /* will be overlaid on file[1] */ |
| 91 | int *klist; /* will be overlaid on file[0] after class */ |
| 92 | struct cand *clist; /* merely a free storage pot for candidates */ |
| 93 | int clen = 0; |
| 94 | int *J; /* will be overlaid on class */ |
| 95 | long *ixold; /* will be overlaid on klist */ |
| 96 | long *ixnew; /* will be overlaid on file[1] */ |
| 97 | char *chrtran; /* translation table for case-folding */ |
| 98 | |
| 99 | /* chrtran points to one of 2 translation tables: |
| 100 | * cup2low if folding upper to lower case |
| 101 | * clow2low if not folding case |
| 102 | */ |
| 103 | char clow2low[256] = { |
| 104 | 0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f, |
| 105 | 0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,0x18,0x19,0x1a,0x1b,0x1c,0x1d,0x1e,0x1f, |
| 106 | 0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,0x28,0x29,0x2a,0x2b,0x2c,0x2d,0x2e,0x2f, |
| 107 | 0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38,0x39,0x3a,0x3b,0x3c,0x3d,0x3e,0x3f, |
| 108 | 0x40,0x41,0x42,0x43,0x44,0x45,0x46,0x47,0x48,0x49,0x4a,0x4b,0x4c,0x4d,0x4e,0x4f, |
| 109 | 0x50,0x51,0x52,0x53,0x54,0x55,0x56,0x57,0x58,0x59,0x5a,0x5b,0x5c,0x5d,0x5e,0x5f, |
| 110 | 0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67,0x68,0x69,0x6a,0x6b,0x6c,0x6d,0x6e,0x6f, |
| 111 | 0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,0x78,0x79,0x7a,0x7b,0x7c,0x7d,0x7e,0x7f, |
| 112 | 0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87,0x88,0x89,0x8a,0x8b,0x8c,0x8d,0x8e,0x8f, |
| 113 | 0x90,0x91,0x92,0x93,0x94,0x95,0x96,0x97,0x98,0x99,0x9a,0x9b,0x9c,0x9d,0x9e,0x9f, |
| 114 | 0xa0,0xa1,0xa2,0xa3,0xa4,0xa5,0xa6,0xa7,0xa8,0xa9,0xaa,0xab,0xac,0xad,0xae,0xaf, |
| 115 | 0xb0,0xb1,0xb2,0xb3,0xb4,0xb5,0xb6,0xb7,0xb8,0xb9,0xba,0xbb,0xbc,0xbd,0xbe,0xbf, |
| 116 | 0xc0,0xc1,0xc2,0xc3,0xc4,0xc5,0xc6,0xc7,0xc8,0xc9,0xca,0xcb,0xcc,0xcd,0xce,0xcf, |
| 117 | 0xd0,0xd1,0xd2,0xd3,0xd4,0xd5,0xd6,0xd7,0xd8,0xd9,0xda,0xdb,0xdc,0xdd,0xde,0xdf, |
| 118 | 0xe0,0xe1,0xe2,0xe3,0xe4,0xe5,0xe6,0xe7,0xe8,0xe9,0xea,0xeb,0xec,0xed,0xee,0xef, |
| 119 | 0xf0,0xf1,0xf2,0xf3,0xf4,0xf5,0xf6,0xf7,0xf8,0xf9,0xfa,0xfb,0xfc,0xfd,0xfe,0xff |
| 120 | }; |
| 121 | |
| 122 | char cup2low[256] = { |
| 123 | 0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f, |
| 124 | 0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,0x18,0x19,0x1a,0x1b,0x1c,0x1d,0x1e,0x1f, |
| 125 | 0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,0x28,0x29,0x2a,0x2b,0x2c,0x2d,0x2e,0x2f, |
| 126 | 0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38,0x39,0x3a,0x3b,0x3c,0x3d,0x3e,0x3f, |
| 127 | 0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67,0x68,0x69,0x6a,0x6b,0x6c,0x6d,0x6e,0x6f, |
| 128 | 0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,0x78,0x79,0x7a,0x7b,0x7c,0x7d,0x7e,0x7f, |
| 129 | 0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67,0x68,0x69,0x6a,0x6b,0x6c,0x6d,0x6e,0x6f, |
| 130 | 0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,0x78,0x79,0x7a,0x7b,0x7c,0x7d,0x7e,0x7f, |
| 131 | 0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87,0x88,0x89,0x8a,0x8b,0x8c,0x8d,0x8e,0x8f, |
| 132 | 0x90,0x91,0x92,0x93,0x94,0x95,0x96,0x97,0x98,0x99,0x9a,0x9b,0x9c,0x9d,0x9e,0x9f, |
| 133 | 0xa0,0xa1,0xa2,0xa3,0xa4,0xa5,0xa6,0xa7,0xa8,0xa9,0xaa,0xab,0xac,0xad,0xae,0xaf, |
| 134 | 0xb0,0xb1,0xb2,0xb3,0xb4,0xb5,0xb6,0xb7,0xb8,0xb9,0xba,0xbb,0xbc,0xbd,0xbe,0xbf, |
| 135 | 0xc0,0xc1,0xc2,0xc3,0xc4,0xc5,0xc6,0xc7,0xc8,0xc9,0xca,0xcb,0xcc,0xcd,0xce,0xcf, |
| 136 | 0xd0,0xd1,0xd2,0xd3,0xd4,0xd5,0xd6,0xd7,0xd8,0xd9,0xda,0xdb,0xdc,0xdd,0xde,0xdf, |
| 137 | 0xe0,0xe1,0xe2,0xe3,0xe4,0xe5,0xe6,0xe7,0xe8,0xe9,0xea,0xeb,0xec,0xed,0xee,0xef, |
| 138 | 0xf0,0xf1,0xf2,0xf3,0xf4,0xf5,0xf6,0xf7,0xf8,0xf9,0xfa,0xfb,0xfc,0xfd,0xfe,0xff |
| 139 | }; |
| 140 | |
| 141 | diffreg() |
| 142 | { |
| 143 | register int i, j; |
| 144 | FILE *f1, *f2; |
| 145 | char buf1[BUFSIZ], buf2[BUFSIZ]; |
| 146 | |
| 147 | if (hflag) { |
| 148 | diffargv[0] = "diffh"; |
| 149 | execv(diffh, diffargv); |
| 150 | fprintf(stderr, "diff: "); |
| 151 | perror(diffh); |
| 152 | done(); |
| 153 | } |
| 154 | chrtran = (iflag? cup2low : clow2low); |
| 155 | if ((stb1.st_mode & S_IFMT) == S_IFDIR) { |
| 156 | file1 = splice(file1, file2); |
| 157 | if (stat(file1, &stb1) < 0) { |
| 158 | fprintf(stderr, "diff: "); |
| 159 | perror(file1); |
| 160 | done(); |
| 161 | } |
| 162 | } else if ((stb2.st_mode & S_IFMT) == S_IFDIR) { |
| 163 | file2 = splice(file2, file1); |
| 164 | if (stat(file2, &stb2) < 0) { |
| 165 | fprintf(stderr, "diff: "); |
| 166 | perror(file2); |
| 167 | done(); |
| 168 | } |
| 169 | } else if (!strcmp(file1, "-")) { |
| 170 | if (!strcmp(file2, "-")) { |
| 171 | fprintf(stderr, "diff: can't specify - -\n"); |
| 172 | done(); |
| 173 | } |
| 174 | file1 = copytemp(); |
| 175 | if (stat(file1, &stb1) < 0) { |
| 176 | fprintf(stderr, "diff: "); |
| 177 | perror(file1); |
| 178 | done(); |
| 179 | } |
| 180 | } else if (!strcmp(file2, "-")) { |
| 181 | file2 = copytemp(); |
| 182 | if (stat(file2, &stb2) < 0) { |
| 183 | fprintf(stderr, "diff: "); |
| 184 | perror(file2); |
| 185 | done(); |
| 186 | } |
| 187 | } |
| 188 | if ((f1 = fopen(file1, "r")) == NULL) { |
| 189 | fprintf(stderr, "diff: "); |
| 190 | perror(file1); |
| 191 | done(); |
| 192 | } |
| 193 | if ((f2 = fopen(file2, "r")) == NULL) { |
| 194 | fprintf(stderr, "diff: "); |
| 195 | perror(file2); |
| 196 | fclose(f1); |
| 197 | done(); |
| 198 | } |
| 199 | if (stb1.st_size != stb2.st_size) |
| 200 | goto notsame; |
| 201 | for (;;) { |
| 202 | i = fread(buf1, 1, BUFSIZ, f1); |
| 203 | j = fread(buf2, 1, BUFSIZ, f2); |
| 204 | if (i < 0 || j < 0 || i != j) |
| 205 | goto notsame; |
| 206 | if (i == 0 && j == 0) { |
| 207 | fclose(f1); |
| 208 | fclose(f2); |
| 209 | status = 0; /* files don't differ */ |
| 210 | goto same; |
| 211 | } |
| 212 | for (j = 0; j < i; j++) |
| 213 | if (buf1[j] != buf2[j]) |
| 214 | goto notsame; |
| 215 | } |
| 216 | notsame: |
| 217 | /* |
| 218 | * Files certainly differ at this point; set status accordingly |
| 219 | */ |
| 220 | status = 1; |
| 221 | if (!asciifile(f1) || !asciifile(f2)) { |
| 222 | printf("Binary files %s and %s differ\n", file1, file2); |
| 223 | fclose(f1); |
| 224 | fclose(f2); |
| 225 | done(); |
| 226 | } |
| 227 | prepare(0, f1); |
| 228 | prepare(1, f2); |
| 229 | fclose(f1); |
| 230 | fclose(f2); |
| 231 | prune(); |
| 232 | sort(sfile[0],slen[0]); |
| 233 | sort(sfile[1],slen[1]); |
| 234 | |
| 235 | member = (int *)file[1]; |
| 236 | equiv(sfile[0], slen[0], sfile[1], slen[1], member); |
| 237 | member = (int *)ralloc((char *)member,(slen[1]+2)*sizeof(int)); |
| 238 | |
| 239 | class = (int *)file[0]; |
| 240 | unsort(sfile[0], slen[0], class); |
| 241 | class = (int *)ralloc((char *)class,(slen[0]+2)*sizeof(int)); |
| 242 | |
| 243 | klist = (int *)talloc((slen[0]+2)*sizeof(int)); |
| 244 | clist = (struct cand *)talloc(sizeof(cand)); |
| 245 | i = stone(class, slen[0], member, klist); |
| 246 | free((char *)member); |
| 247 | free((char *)class); |
| 248 | |
| 249 | J = (int *)talloc((len[0]+2)*sizeof(int)); |
| 250 | unravel(klist[i]); |
| 251 | free((char *)clist); |
| 252 | free((char *)klist); |
| 253 | |
| 254 | ixold = (long *)talloc((len[0]+2)*sizeof(long)); |
| 255 | ixnew = (long *)talloc((len[1]+2)*sizeof(long)); |
| 256 | check(); |
| 257 | output(); |
| 258 | status = anychange; |
| 259 | same: |
| 260 | if (opt == D_CONTEXT && anychange == 0) |
| 261 | printf("No differences encountered\n"); |
| 262 | done(); |
| 263 | } |
| 264 | |
| 265 | char *tempfile = "/tmp/dXXXXX"; |
| 266 | |
| 267 | char * |
| 268 | copytemp() |
| 269 | { |
| 270 | char buf[BUFSIZ]; |
| 271 | register int i, f; |
| 272 | |
| 273 | signal(SIGHUP,done); |
| 274 | signal(SIGINT,done); |
| 275 | signal(SIGPIPE,done); |
| 276 | signal(SIGTERM,done); |
| 277 | mktemp(tempfile); |
| 278 | f = creat(tempfile,0600); |
| 279 | if (f < 0) { |
| 280 | fprintf(stderr, "diff: "); |
| 281 | perror(tempfile); |
| 282 | done(); |
| 283 | } |
| 284 | while ((i = read(0,buf,BUFSIZ)) > 0) |
| 285 | if (write(f,buf,i) != i) { |
| 286 | fprintf(stderr, "diff: "); |
| 287 | perror(tempfile); |
| 288 | done(); |
| 289 | } |
| 290 | close(f); |
| 291 | return (tempfile); |
| 292 | } |
| 293 | |
| 294 | char * |
| 295 | splice(dir, file) |
| 296 | char *dir, *file; |
| 297 | { |
| 298 | char *tail; |
| 299 | char buf[BUFSIZ]; |
| 300 | |
| 301 | if (!strcmp(file, "-")) { |
| 302 | fprintf(stderr, "diff: can't specify - with other arg directory\n"); |
| 303 | done(); |
| 304 | } |
| 305 | tail = rindex(file, '/'); |
| 306 | if (tail == 0) |
| 307 | tail = file; |
| 308 | else |
| 309 | tail++; |
| 310 | (void)sprintf(buf, "%s/%s", dir, tail); |
| 311 | return (savestr(buf)); |
| 312 | } |
| 313 | |
| 314 | prepare(i, fd) |
| 315 | int i; |
| 316 | FILE *fd; |
| 317 | { |
| 318 | register struct line *p; |
| 319 | register j,h; |
| 320 | |
| 321 | fseek(fd, (long)0, 0); |
| 322 | p = (struct line *)talloc(3*sizeof(line)); |
| 323 | for(j=0; h=readhash(fd);) { |
| 324 | p = (struct line *)ralloc((char *)p,(++j+3)*sizeof(line)); |
| 325 | p[j].value = h; |
| 326 | } |
| 327 | len[i] = j; |
| 328 | file[i] = p; |
| 329 | } |
| 330 | |
| 331 | prune() |
| 332 | { |
| 333 | register i,j; |
| 334 | for(pref=0;pref<len[0]&&pref<len[1]&& |
| 335 | file[0][pref+1].value==file[1][pref+1].value; |
| 336 | pref++ ) ; |
| 337 | for(suff=0;suff<len[0]-pref&&suff<len[1]-pref&& |
| 338 | file[0][len[0]-suff].value==file[1][len[1]-suff].value; |
| 339 | suff++) ; |
| 340 | for(j=0;j<2;j++) { |
| 341 | sfile[j] = file[j]+pref; |
| 342 | slen[j] = len[j]-pref-suff; |
| 343 | for(i=0;i<=slen[j];i++) |
| 344 | sfile[j][i].serial = i; |
| 345 | } |
| 346 | } |
| 347 | |
| 348 | equiv(a,n,b,m,c) |
| 349 | struct line *a, *b; |
| 350 | int *c; |
| 351 | { |
| 352 | register int i, j; |
| 353 | i = j = 1; |
| 354 | while(i<=n && j<=m) { |
| 355 | if(a[i].value <b[j].value) |
| 356 | a[i++].value = 0; |
| 357 | else if(a[i].value == b[j].value) |
| 358 | a[i++].value = j; |
| 359 | else |
| 360 | j++; |
| 361 | } |
| 362 | while(i <= n) |
| 363 | a[i++].value = 0; |
| 364 | b[m+1].value = 0; |
| 365 | j = 0; |
| 366 | while(++j <= m) { |
| 367 | c[j] = -b[j].serial; |
| 368 | while(b[j+1].value == b[j].value) { |
| 369 | j++; |
| 370 | c[j] = b[j].serial; |
| 371 | } |
| 372 | } |
| 373 | c[j] = -1; |
| 374 | } |
| 375 | |
| 376 | stone(a,n,b,c) |
| 377 | int *a; |
| 378 | int *b; |
| 379 | register int *c; |
| 380 | { |
| 381 | register int i, k,y; |
| 382 | int j, l; |
| 383 | int oldc, tc; |
| 384 | int oldl; |
| 385 | k = 0; |
| 386 | c[0] = newcand(0,0,0); |
| 387 | for(i=1; i<=n; i++) { |
| 388 | j = a[i]; |
| 389 | if(j==0) |
| 390 | continue; |
| 391 | y = -b[j]; |
| 392 | oldl = 0; |
| 393 | oldc = c[0]; |
| 394 | do { |
| 395 | if(y <= clist[oldc].y) |
| 396 | continue; |
| 397 | l = search(c, k, y); |
| 398 | if(l!=oldl+1) |
| 399 | oldc = c[l-1]; |
| 400 | if(l<=k) { |
| 401 | if(clist[c[l]].y <= y) |
| 402 | continue; |
| 403 | tc = c[l]; |
| 404 | c[l] = newcand(i,y,oldc); |
| 405 | oldc = tc; |
| 406 | oldl = l; |
| 407 | } else { |
| 408 | c[l] = newcand(i,y,oldc); |
| 409 | k++; |
| 410 | break; |
| 411 | } |
| 412 | } while((y=b[++j]) > 0); |
| 413 | } |
| 414 | return(k); |
| 415 | } |
| 416 | |
| 417 | newcand(x,y,pred) |
| 418 | { |
| 419 | register struct cand *q; |
| 420 | clist = (struct cand *)ralloc((char *)clist,++clen*sizeof(cand)); |
| 421 | q = clist + clen -1; |
| 422 | q->x = x; |
| 423 | q->y = y; |
| 424 | q->pred = pred; |
| 425 | return(clen-1); |
| 426 | } |
| 427 | |
| 428 | search(c, k, y) |
| 429 | int *c; |
| 430 | { |
| 431 | register int i, j, l; |
| 432 | int t; |
| 433 | if(clist[c[k]].y<y) /*quick look for typical case*/ |
| 434 | return(k+1); |
| 435 | i = 0; |
| 436 | j = k+1; |
| 437 | while (1) { |
| 438 | l = i + j; |
| 439 | if ((l >>= 1) <= i) |
| 440 | break; |
| 441 | t = clist[c[l]].y; |
| 442 | if(t > y) |
| 443 | j = l; |
| 444 | else if(t < y) |
| 445 | i = l; |
| 446 | else |
| 447 | return(l); |
| 448 | } |
| 449 | return(l+1); |
| 450 | } |
| 451 | |
| 452 | unravel(p) |
| 453 | { |
| 454 | register int i; |
| 455 | register struct cand *q; |
| 456 | for(i=0; i<=len[0]; i++) |
| 457 | J[i] = i<=pref ? i: |
| 458 | i>len[0]-suff ? i+len[1]-len[0]: |
| 459 | 0; |
| 460 | for(q=clist+p;q->y!=0;q=clist+q->pred) |
| 461 | J[q->x+pref] = q->y+pref; |
| 462 | } |
| 463 | |
| 464 | /* check does double duty: |
| 465 | 1. ferret out any fortuitous correspondences due |
| 466 | to confounding by hashing (which result in "jackpot") |
| 467 | 2. collect random access indexes to the two files */ |
| 468 | |
| 469 | check() |
| 470 | { |
| 471 | register int i, j; |
| 472 | int jackpot; |
| 473 | long ctold, ctnew; |
| 474 | register int c,d; |
| 475 | |
| 476 | if ((input[0] = fopen(file1,"r")) == NULL) { |
| 477 | perror(file1); |
| 478 | done(); |
| 479 | } |
| 480 | if ((input[1] = fopen(file2,"r")) == NULL) { |
| 481 | perror(file2); |
| 482 | done(); |
| 483 | } |
| 484 | j = 1; |
| 485 | ixold[0] = ixnew[0] = 0; |
| 486 | jackpot = 0; |
| 487 | ctold = ctnew = 0; |
| 488 | for(i=1;i<=len[0];i++) { |
| 489 | if(J[i]==0) { |
| 490 | ixold[i] = ctold += skipline(0); |
| 491 | continue; |
| 492 | } |
| 493 | while(j<J[i]) { |
| 494 | ixnew[j] = ctnew += skipline(1); |
| 495 | j++; |
| 496 | } |
| 497 | if(bflag || wflag || iflag) { |
| 498 | for(;;) { |
| 499 | c = getc(input[0]); |
| 500 | d = getc(input[1]); |
| 501 | ctold++; |
| 502 | ctnew++; |
| 503 | if(bflag && isspace(c) && isspace(d)) { |
| 504 | do { |
| 505 | if(c=='\n') |
| 506 | break; |
| 507 | ctold++; |
| 508 | } while(isspace(c=getc(input[0]))); |
| 509 | do { |
| 510 | if(d=='\n') |
| 511 | break; |
| 512 | ctnew++; |
| 513 | } while(isspace(d=getc(input[1]))); |
| 514 | } else if ( wflag ) { |
| 515 | while( isspace(c) && c!='\n' ) { |
| 516 | c=getc(input[0]); |
| 517 | ctold++; |
| 518 | } |
| 519 | while( isspace(d) && d!='\n' ) { |
| 520 | d=getc(input[1]); |
| 521 | ctnew++; |
| 522 | } |
| 523 | } |
| 524 | if(chrtran[c] != chrtran[d]) { |
| 525 | jackpot++; |
| 526 | J[i] = 0; |
| 527 | if(c!='\n') |
| 528 | ctold += skipline(0); |
| 529 | if(d!='\n') |
| 530 | ctnew += skipline(1); |
| 531 | break; |
| 532 | } |
| 533 | if(c=='\n') |
| 534 | break; |
| 535 | } |
| 536 | } else { |
| 537 | for(;;) { |
| 538 | ctold++; |
| 539 | ctnew++; |
| 540 | if((c=getc(input[0])) != (d=getc(input[1]))) { |
| 541 | /* jackpot++; */ |
| 542 | J[i] = 0; |
| 543 | if(c!='\n') |
| 544 | ctold += skipline(0); |
| 545 | if(d!='\n') |
| 546 | ctnew += skipline(1); |
| 547 | break; |
| 548 | } |
| 549 | if(c=='\n') |
| 550 | break; |
| 551 | } |
| 552 | } |
| 553 | ixold[i] = ctold; |
| 554 | ixnew[j] = ctnew; |
| 555 | j++; |
| 556 | } |
| 557 | for(;j<=len[1];j++) { |
| 558 | ixnew[j] = ctnew += skipline(1); |
| 559 | } |
| 560 | fclose(input[0]); |
| 561 | fclose(input[1]); |
| 562 | /* |
| 563 | if(jackpot) |
| 564 | fprintf(stderr, "jackpot\n"); |
| 565 | */ |
| 566 | } |
| 567 | |
| 568 | sort(a,n) /*shellsort CACM #201*/ |
| 569 | struct line *a; |
| 570 | { |
| 571 | struct line w; |
| 572 | register int j,m; |
| 573 | struct line *ai; |
| 574 | register struct line *aim; |
| 575 | int k; |
| 576 | |
| 577 | if (n == 0) |
| 578 | return; |
| 579 | for(j=1;j<=n;j*= 2) |
| 580 | m = 2*j - 1; |
| 581 | for(m/=2;m!=0;m/=2) { |
| 582 | k = n-m; |
| 583 | for(j=1;j<=k;j++) { |
| 584 | for(ai = &a[j]; ai > a; ai -= m) { |
| 585 | aim = &ai[m]; |
| 586 | if(aim < ai) |
| 587 | break; /*wraparound*/ |
| 588 | if(aim->value > ai[0].value || |
| 589 | aim->value == ai[0].value && |
| 590 | aim->serial > ai[0].serial) |
| 591 | break; |
| 592 | w.value = ai[0].value; |
| 593 | ai[0].value = aim->value; |
| 594 | aim->value = w.value; |
| 595 | w.serial = ai[0].serial; |
| 596 | ai[0].serial = aim->serial; |
| 597 | aim->serial = w.serial; |
| 598 | } |
| 599 | } |
| 600 | } |
| 601 | } |
| 602 | |
| 603 | unsort(f, l, b) |
| 604 | struct line *f; |
| 605 | int *b; |
| 606 | { |
| 607 | register int *a; |
| 608 | register int i; |
| 609 | a = (int *)talloc((l+1)*sizeof(int)); |
| 610 | for(i=1;i<=l;i++) |
| 611 | a[f[i].serial] = f[i].value; |
| 612 | for(i=1;i<=l;i++) |
| 613 | b[i] = a[i]; |
| 614 | free((char *)a); |
| 615 | } |
| 616 | |
| 617 | skipline(f) |
| 618 | { |
| 619 | register i, c; |
| 620 | |
| 621 | for(i=1;(c=getc(input[f]))!='\n';i++) |
| 622 | if (c < 0) |
| 623 | return(i); |
| 624 | return(i); |
| 625 | } |
| 626 | |
| 627 | output() |
| 628 | { |
| 629 | int m; |
| 630 | register int i0, i1, j1; |
| 631 | int j0; |
| 632 | input[0] = fopen(file1,"r"); |
| 633 | input[1] = fopen(file2,"r"); |
| 634 | m = len[0]; |
| 635 | J[0] = 0; |
| 636 | J[m+1] = len[1]+1; |
| 637 | if(opt!=D_EDIT) for(i0=1;i0<=m;i0=i1+1) { |
| 638 | while(i0<=m&&J[i0]==J[i0-1]+1) i0++; |
| 639 | j0 = J[i0-1]+1; |
| 640 | i1 = i0-1; |
| 641 | while(i1<m&&J[i1+1]==0) i1++; |
| 642 | j1 = J[i1+1]-1; |
| 643 | J[i1] = j1; |
| 644 | change(i0,i1,j0,j1); |
| 645 | } else for(i0=m;i0>=1;i0=i1-1) { |
| 646 | while(i0>=1&&J[i0]==J[i0+1]-1&&J[i0]!=0) i0--; |
| 647 | j0 = J[i0+1]-1; |
| 648 | i1 = i0+1; |
| 649 | while(i1>1&&J[i1-1]==0) i1--; |
| 650 | j1 = J[i1-1]+1; |
| 651 | J[i1] = j1; |
| 652 | change(i1,i0,j1,j0); |
| 653 | } |
| 654 | if(m==0) |
| 655 | change(1,0,1,len[1]); |
| 656 | if (opt==D_IFDEF) { |
| 657 | for (;;) { |
| 658 | #define c i0 |
| 659 | c = getc(input[0]); |
| 660 | if (c < 0) |
| 661 | return; |
| 662 | putchar(c); |
| 663 | } |
| 664 | #undef c |
| 665 | } |
| 666 | if (anychange && opt == D_CONTEXT) |
| 667 | dump_context_vec(); |
| 668 | } |
| 669 | |
| 670 | /* |
| 671 | * The following struct is used to record change information when |
| 672 | * doing a "context" diff. (see routine "change" to understand the |
| 673 | * highly mneumonic field names) |
| 674 | */ |
| 675 | struct context_vec { |
| 676 | int a; /* start line in old file */ |
| 677 | int b; /* end line in old file */ |
| 678 | int c; /* start line in new file */ |
| 679 | int d; /* end line in new file */ |
| 680 | }; |
| 681 | |
| 682 | struct context_vec *context_vec_start, |
| 683 | *context_vec_end, |
| 684 | *context_vec_ptr; |
| 685 | |
| 686 | #define MAX_CONTEXT 128 |
| 687 | |
| 688 | /* indicate that there is a difference between lines a and b of the from file |
| 689 | to get to lines c to d of the to file. |
| 690 | If a is greater then b then there are no lines in the from file involved |
| 691 | and this means that there were lines appended (beginning at b). |
| 692 | If c is greater than d then there are lines missing from the to file. |
| 693 | */ |
| 694 | change(a,b,c,d) |
| 695 | { |
| 696 | int ch; |
| 697 | int lowa,upb,lowc,upd; |
| 698 | struct stat stbuf; |
| 699 | |
| 700 | if (opt != D_IFDEF && a>b && c>d) |
| 701 | return; |
| 702 | if (anychange == 0) { |
| 703 | anychange = 1; |
| 704 | if(opt == D_CONTEXT) { |
| 705 | printf("*** %s ", file1); |
| 706 | stat(file1, &stbuf); |
| 707 | printf("%s--- %s ", |
| 708 | ctime(&stbuf.st_mtime), file2); |
| 709 | stat(file2, &stbuf); |
| 710 | printf("%s", ctime(&stbuf.st_mtime)); |
| 711 | |
| 712 | context_vec_start = (struct context_vec *) |
| 713 | malloc(MAX_CONTEXT * |
| 714 | sizeof(struct context_vec)); |
| 715 | context_vec_end = context_vec_start + MAX_CONTEXT; |
| 716 | context_vec_ptr = context_vec_start - 1; |
| 717 | } |
| 718 | } |
| 719 | if (a <= b && c <= d) |
| 720 | ch = 'c'; |
| 721 | else |
| 722 | ch = (a <= b) ? 'd' : 'a'; |
| 723 | if(opt == D_CONTEXT) { |
| 724 | /* |
| 725 | * if this new change is within 'context' lines of |
| 726 | * the previous change, just add it to the change |
| 727 | * record. If the record is full or if this |
| 728 | * change is more than 'context' lines from the previous |
| 729 | * change, dump the record, reset it & add the new change. |
| 730 | */ |
| 731 | if ( context_vec_ptr >= context_vec_end || |
| 732 | ( context_vec_ptr >= context_vec_start && |
| 733 | a > (context_vec_ptr->b + 2*context) && |
| 734 | c > (context_vec_ptr->d + 2*context) ) ) |
| 735 | dump_context_vec(); |
| 736 | |
| 737 | context_vec_ptr++; |
| 738 | context_vec_ptr->a = a; |
| 739 | context_vec_ptr->b = b; |
| 740 | context_vec_ptr->c = c; |
| 741 | context_vec_ptr->d = d; |
| 742 | return; |
| 743 | } |
| 744 | switch (opt) { |
| 745 | |
| 746 | case D_NORMAL: |
| 747 | case D_EDIT: |
| 748 | range(a,b,","); |
| 749 | putchar(a>b?'a':c>d?'d':'c'); |
| 750 | if(opt==D_NORMAL) |
| 751 | range(c,d,","); |
| 752 | putchar('\n'); |
| 753 | break; |
| 754 | case D_REVERSE: |
| 755 | putchar(a>b?'a':c>d?'d':'c'); |
| 756 | range(a,b," "); |
| 757 | putchar('\n'); |
| 758 | break; |
| 759 | case D_NREVERSE: |
| 760 | if (a>b) |
| 761 | printf("a%d %d\n",b,d-c+1); |
| 762 | else { |
| 763 | printf("d%d %d\n",a,b-a+1); |
| 764 | if (!(c>d)) |
| 765 | /* add changed lines */ |
| 766 | printf("a%d %d\n",b, d-c+1); |
| 767 | } |
| 768 | break; |
| 769 | } |
| 770 | if(opt == D_NORMAL || opt == D_IFDEF) { |
| 771 | fetch(ixold,a,b,input[0],"< ", 1); |
| 772 | if(a<=b&&c<=d && opt == D_NORMAL) |
| 773 | prints("---\n"); |
| 774 | } |
| 775 | fetch(ixnew,c,d,input[1],opt==D_NORMAL?"> ":"", 0); |
| 776 | if ((opt ==D_EDIT || opt == D_REVERSE) && c<=d) |
| 777 | prints(".\n"); |
| 778 | if (inifdef) { |
| 779 | fprintf(stdout, "#endif %s\n", endifname); |
| 780 | inifdef = 0; |
| 781 | } |
| 782 | } |
| 783 | |
| 784 | range(a,b,separator) |
| 785 | char *separator; |
| 786 | { |
| 787 | printf("%d", a>b?b:a); |
| 788 | if(a<b) { |
| 789 | printf("%s%d", separator, b); |
| 790 | } |
| 791 | } |
| 792 | |
| 793 | fetch(f,a,b,lb,s,oldfile) |
| 794 | long *f; |
| 795 | FILE *lb; |
| 796 | char *s; |
| 797 | { |
| 798 | register int i, j; |
| 799 | register int c; |
| 800 | register int col; |
| 801 | register int nc; |
| 802 | int oneflag = (*ifdef1!='\0') != (*ifdef2!='\0'); |
| 803 | |
| 804 | /* |
| 805 | * When doing #ifdef's, copy down to current line |
| 806 | * if this is the first file, so that stuff makes it to output. |
| 807 | */ |
| 808 | if (opt == D_IFDEF && oldfile){ |
| 809 | long curpos = ftell(lb); |
| 810 | /* print through if append (a>b), else to (nb: 0 vs 1 orig) */ |
| 811 | nc = f[a>b? b : a-1 ] - curpos; |
| 812 | for (i = 0; i < nc; i++) |
| 813 | putchar(getc(lb)); |
| 814 | } |
| 815 | if (a > b) |
| 816 | return; |
| 817 | if (opt == D_IFDEF) { |
| 818 | if (inifdef) |
| 819 | fprintf(stdout, "#else %s%s\n", oneflag && oldfile==1 ? "!" : "", ifdef2); |
| 820 | else { |
| 821 | if (oneflag) { |
| 822 | /* There was only one ifdef given */ |
| 823 | endifname = ifdef2; |
| 824 | if (oldfile) |
| 825 | fprintf(stdout, "#ifndef %s\n", endifname); |
| 826 | else |
| 827 | fprintf(stdout, "#ifdef %s\n", endifname); |
| 828 | } |
| 829 | else { |
| 830 | endifname = oldfile ? ifdef1 : ifdef2; |
| 831 | fprintf(stdout, "#ifdef %s\n", endifname); |
| 832 | } |
| 833 | } |
| 834 | inifdef = 1+oldfile; |
| 835 | } |
| 836 | |
| 837 | for(i=a;i<=b;i++) { |
| 838 | fseek(lb,f[i-1],0); |
| 839 | nc = f[i]-f[i-1]; |
| 840 | if (opt != D_IFDEF) |
| 841 | prints(s); |
| 842 | col = 0; |
| 843 | for(j=0;j<nc;j++) { |
| 844 | c = getc(lb); |
| 845 | if (c == '\t' && tflag) |
| 846 | do |
| 847 | putchar(' '); |
| 848 | while (++col & 7); |
| 849 | else { |
| 850 | putchar(c); |
| 851 | col++; |
| 852 | } |
| 853 | } |
| 854 | } |
| 855 | |
| 856 | if (inifdef && !wantelses) { |
| 857 | fprintf(stdout, "#endif %s\n", endifname); |
| 858 | inifdef = 0; |
| 859 | } |
| 860 | } |
| 861 | |
| 862 | #define POW2 /* define only if HALFLONG is 2**n */ |
| 863 | #define HALFLONG 16 |
| 864 | #define low(x) (x&((1L<<HALFLONG)-1)) |
| 865 | #define high(x) (x>>HALFLONG) |
| 866 | |
| 867 | /* |
| 868 | * hashing has the effect of |
| 869 | * arranging line in 7-bit bytes and then |
| 870 | * summing 1-s complement in 16-bit hunks |
| 871 | */ |
| 872 | readhash(f) |
| 873 | register FILE *f; |
| 874 | { |
| 875 | register long sum; |
| 876 | register unsigned shift; |
| 877 | register t; |
| 878 | register space; |
| 879 | |
| 880 | sum = 1; |
| 881 | space = 0; |
| 882 | if(!bflag && !wflag) { |
| 883 | if(iflag) |
| 884 | for(shift=0;(t=getc(f))!='\n';shift+=7) { |
| 885 | if(t==-1) |
| 886 | return(0); |
| 887 | sum += (long)chrtran[t] << (shift |
| 888 | #ifdef POW2 |
| 889 | &= HALFLONG - 1); |
| 890 | #else |
| 891 | %= HALFLONG); |
| 892 | #endif |
| 893 | } |
| 894 | else |
| 895 | for(shift=0;(t=getc(f))!='\n';shift+=7) { |
| 896 | if(t==-1) |
| 897 | return(0); |
| 898 | sum += (long)t << (shift |
| 899 | #ifdef POW2 |
| 900 | &= HALFLONG - 1); |
| 901 | #else |
| 902 | %= HALFLONG); |
| 903 | #endif |
| 904 | } |
| 905 | } else { |
| 906 | for(shift=0;;) { |
| 907 | switch(t=getc(f)) { |
| 908 | case -1: |
| 909 | return(0); |
| 910 | case '\t': |
| 911 | case ' ': |
| 912 | space++; |
| 913 | continue; |
| 914 | default: |
| 915 | if(space && !wflag) { |
| 916 | shift += 7; |
| 917 | space = 0; |
| 918 | } |
| 919 | sum += (long)chrtran[t] << (shift |
| 920 | #ifdef POW2 |
| 921 | &= HALFLONG - 1); |
| 922 | #else |
| 923 | %= HALFLONG); |
| 924 | #endif |
| 925 | shift += 7; |
| 926 | continue; |
| 927 | case '\n': |
| 928 | break; |
| 929 | } |
| 930 | break; |
| 931 | } |
| 932 | } |
| 933 | sum = low(sum) + high(sum); |
| 934 | return((short)low(sum) + (short)high(sum)); |
| 935 | } |
| 936 | |
| 937 | #include <a.out.h> |
| 938 | |
| 939 | asciifile(f) |
| 940 | FILE *f; |
| 941 | { |
| 942 | char buf[BUFSIZ]; |
| 943 | register int cnt; |
| 944 | register char *cp; |
| 945 | |
| 946 | fseek(f, (long)0, 0); |
| 947 | cnt = fread(buf, 1, BUFSIZ, f); |
| 948 | if (cnt >= sizeof (struct exec)) { |
| 949 | struct exec hdr; |
| 950 | hdr = *(struct exec *)buf; |
| 951 | if (!N_BADMAG(hdr)) |
| 952 | return (0); |
| 953 | } |
| 954 | cp = buf; |
| 955 | while (--cnt >= 0) |
| 956 | if (*cp++ & 0200) |
| 957 | return (0); |
| 958 | return (1); |
| 959 | } |
| 960 | |
| 961 | |
| 962 | /* dump accumulated "context" diff changes */ |
| 963 | dump_context_vec() |
| 964 | { |
| 965 | register int a, b, c, d; |
| 966 | register char ch; |
| 967 | register struct context_vec *cvp = context_vec_start; |
| 968 | register int lowa, upb, lowc, upd; |
| 969 | register int do_output; |
| 970 | |
| 971 | if ( cvp > context_vec_ptr ) |
| 972 | return; |
| 973 | |
| 974 | lowa = max(1, cvp->a - context); |
| 975 | upb = min(len[0], context_vec_ptr->b + context); |
| 976 | lowc = max(1, cvp->c - context); |
| 977 | upd = min(len[1], context_vec_ptr->d + context); |
| 978 | |
| 979 | printf("***************\n*** "); |
| 980 | range(lowa,upb,","); |
| 981 | printf(" ****\n"); |
| 982 | |
| 983 | /* |
| 984 | * output changes to the "old" file. The first loop suppresses |
| 985 | * output if there were no changes to the "old" file (we'll see |
| 986 | * the "old" lines as context in the "new" list). |
| 987 | */ |
| 988 | do_output = 0; |
| 989 | for ( ; cvp <= context_vec_ptr; cvp++) |
| 990 | if (cvp->a <= cvp->b) { |
| 991 | cvp = context_vec_start; |
| 992 | do_output++; |
| 993 | break; |
| 994 | } |
| 995 | |
| 996 | if ( do_output ) { |
| 997 | while (cvp <= context_vec_ptr) { |
| 998 | a = cvp->a; b = cvp->b; c = cvp->c; d = cvp->d; |
| 999 | |
| 1000 | if (a <= b && c <= d) |
| 1001 | ch = 'c'; |
| 1002 | else |
| 1003 | ch = (a <= b) ? 'd' : 'a'; |
| 1004 | |
| 1005 | if (ch == 'a') |
| 1006 | fetch(ixold,lowa,b,input[0]," "); |
| 1007 | else { |
| 1008 | fetch(ixold,lowa,a-1,input[0]," "); |
| 1009 | fetch(ixold,a,b,input[0],ch == 'c' ? "! " : "- "); |
| 1010 | } |
| 1011 | lowa = b + 1; |
| 1012 | cvp++; |
| 1013 | } |
| 1014 | fetch(ixold, b+1, upb, input[0], " "); |
| 1015 | } |
| 1016 | |
| 1017 | /* output changes to the "new" file */ |
| 1018 | printf("--- "); |
| 1019 | range(lowc,upd,","); |
| 1020 | printf(" ----\n"); |
| 1021 | |
| 1022 | do_output = 0; |
| 1023 | for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++) |
| 1024 | if (cvp->c <= cvp->d) { |
| 1025 | cvp = context_vec_start; |
| 1026 | do_output++; |
| 1027 | break; |
| 1028 | } |
| 1029 | |
| 1030 | if (do_output) { |
| 1031 | while (cvp <= context_vec_ptr) { |
| 1032 | a = cvp->a; b = cvp->b; c = cvp->c; d = cvp->d; |
| 1033 | |
| 1034 | if (a <= b && c <= d) |
| 1035 | ch = 'c'; |
| 1036 | else |
| 1037 | ch = (a <= b) ? 'd' : 'a'; |
| 1038 | |
| 1039 | if (ch == 'd') |
| 1040 | fetch(ixnew,lowc,d,input[1]," "); |
| 1041 | else { |
| 1042 | fetch(ixnew,lowc,c-1,input[1]," "); |
| 1043 | fetch(ixnew,c,d,input[1],ch == 'c' ? "! " : "+ "); |
| 1044 | } |
| 1045 | lowc = d + 1; |
| 1046 | cvp++; |
| 1047 | } |
| 1048 | fetch(ixnew, d+1, upd, input[1], " "); |
| 1049 | } |
| 1050 | |
| 1051 | context_vec_ptr = context_vec_start - 1; |
| 1052 | } |