1 /* $OpenBSD: diffreg.c,v 1.46 2003/07/31 02:53:57 millert Exp $ */ 2 3 /* 4 * Copyright (C) Caldera International Inc. 2001-2002. 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code and documentation must retain the above 11 * copyright notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. All advertising materials mentioning features or use of this software 16 * must display the following acknowledgement: 17 * This product includes software developed or owned by Caldera 18 * International, Inc. 19 * 4. Neither the name of Caldera International, Inc. nor the names of other 20 * contributors may be used to endorse or promote products derived from 21 * this software without specific prior written permission. 22 * 23 * USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA 24 * INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR 25 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 26 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 27 * IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE FOR ANY DIRECT, 28 * INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 29 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 30 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 32 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 33 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 34 * POSSIBILITY OF SUCH DAMAGE. 35 */ 36 /*- 37 * Copyright (c) 1991, 1993 38 * The Regents of the University of California. All rights reserved. 39 * 40 * Redistribution and use in source and binary forms, with or without 41 * modification, are permitted provided that the following conditions 42 * are met: 43 * 1. Redistributions of source code must retain the above copyright 44 * notice, this list of conditions and the following disclaimer. 45 * 2. Redistributions in binary form must reproduce the above copyright 46 * notice, this list of conditions and the following disclaimer in the 47 * documentation and/or other materials provided with the distribution. 48 * 3. Neither the name of the University nor the names of its contributors 49 * may be used to endorse or promote products derived from this software 50 * without specific prior written permission. 51 * 52 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 53 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 54 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 55 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 56 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 57 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 58 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 59 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 60 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 61 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 62 * SUCH DAMAGE. 63 * 64 * @(#)diffreg.c 8.1 (Berkeley) 6/6/93 65 */ 66 67 #ifndef lint 68 static const char rcsid[] = "$OpenBSD: diffreg.c,v 1.46 2003/07/31 02:53:57 millert Exp $"; 69 #endif /* not lint */ 70 71 #include <sys/param.h> 72 #include <sys/stat.h> 73 #include <sys/wait.h> 74 75 #include <ctype.h> 76 #include <err.h> 77 #include <errno.h> 78 #include <fcntl.h> 79 #include <stddef.h> 80 #include <stdio.h> 81 #include <stdlib.h> 82 #include <string.h> 83 #include <unistd.h> 84 85 #include "diff.h" 86 #include "pathnames.h" 87 88 /* 89 * diff - compare two files. 90 */ 91 92 /* 93 * Uses an algorithm due to Harold Stone, which finds 94 * a pair of longest identical subsequences in the two 95 * files. 96 * 97 * The major goal is to generate the match vector J. 98 * J[i] is the index of the line in file1 corresponding 99 * to line i file0. J[i] = 0 if there is no 100 * such line in file1. 101 * 102 * Lines are hashed so as to work in core. All potential 103 * matches are located by sorting the lines of each file 104 * on the hash (called ``value''). In particular, this 105 * collects the equivalence classes in file1 together. 106 * Subroutine equiv replaces the value of each line in 107 * file0 by the index of the first element of its 108 * matching equivalence in (the reordered) file1. 109 * To save space equiv squeezes file1 into a single 110 * array member in which the equivalence classes 111 * are simply concatenated, except that their first 112 * members are flagged by changing sign. 113 * 114 * Next the indices that point into member are unsorted into 115 * array class according to the original order of file0. 116 * 117 * The cleverness lies in routine stone. This marches 118 * through the lines of file0, developing a vector klist 119 * of "k-candidates". At step i a k-candidate is a matched 120 * pair of lines x,y (x in file0 y in file1) such that 121 * there is a common subsequence of length k 122 * between the first i lines of file0 and the first y 123 * lines of file1, but there is no such subsequence for 124 * any smaller y. x is the earliest possible mate to y 125 * that occurs in such a subsequence. 126 * 127 * Whenever any of the members of the equivalence class of 128 * lines in file1 matable to a line in file0 has serial number 129 * less than the y of some k-candidate, that k-candidate 130 * with the smallest such y is replaced. The new 131 * k-candidate is chained (via pred) to the current 132 * k-1 candidate so that the actual subsequence can 133 * be recovered. When a member has serial number greater 134 * that the y of all k-candidates, the klist is extended. 135 * At the end, the longest subsequence is pulled out 136 * and placed in the array J by unravel 137 * 138 * With J in hand, the matches there recorded are 139 * check'ed against reality to assure that no spurious 140 * matches have crept in due to hashing. If they have, 141 * they are broken, and "jackpot" is recorded--a harmless 142 * matter except that a true match for a spuriously 143 * mated line may now be unnecessarily reported as a change. 144 * 145 * Much of the complexity of the program comes simply 146 * from trying to minimize core utilization and 147 * maximize the range of doable problems by dynamically 148 * allocating what is needed and reusing what is not. 149 * The core requirements for problems larger than somewhat 150 * are (in words) 2*length(file0) + length(file1) + 151 * 3*(number of k-candidates installed), typically about 152 * 6n words for files of length n. 153 */ 154 155 struct cand { 156 int x; 157 int y; 158 int pred; 159 } cand; 160 161 struct line { 162 int serial; 163 int value; 164 } *file[2]; 165 166 /* 167 * The following struct is used to record change information when 168 * doing a "context" or "unified" diff. (see routine "change" to 169 * understand the highly mnemonic field names) 170 */ 171 struct context_vec { 172 int a; /* start line in old file */ 173 int b; /* end line in old file */ 174 int c; /* start line in new file */ 175 int d; /* end line in new file */ 176 }; 177 178 static int *J; /* will be overlaid on class */ 179 static int *class; /* will be overlaid on file[0] */ 180 static int *klist; /* will be overlaid on file[0] after class */ 181 static int *member; /* will be overlaid on file[1] */ 182 static int clen; 183 static int inifdef; /* whether or not we are in a #ifdef block */ 184 static int len[2]; 185 static int pref, suff; /* length of prefix and suffix */ 186 static int slen[2]; 187 static int anychange; 188 static long *ixnew; /* will be overlaid on file[1] */ 189 static long *ixold; /* will be overlaid on klist */ 190 static struct cand *clist; /* merely a free storage pot for candidates */ 191 static int clistlen; /* the length of clist */ 192 static struct line *sfile[2]; /* shortened by pruning common prefix/suffix */ 193 static u_char *chrtran; /* translation table for case-folding */ 194 static struct context_vec *context_vec_start; 195 static struct context_vec *context_vec_end; 196 static struct context_vec *context_vec_ptr; 197 198 static FILE *opentemp(const char *); 199 static void output(char *, FILE *, char *, FILE *); 200 static void check(char *, FILE *, char *, FILE *); 201 static void range(int, int, char *); 202 static void uni_range(int, int); 203 static void dump_context_vec(FILE *, FILE *); 204 static void dump_unified_vec(FILE *, FILE *); 205 static void prepare(int, FILE *); 206 static void prune(void); 207 static void equiv(struct line *, int, struct line *, int, int *); 208 static void unravel(int); 209 static void unsort(struct line *, int, int *); 210 static void change(char *, FILE *, char *, FILE *, int, int, int, int); 211 static void sort(struct line *, int); 212 static int asciifile(FILE *); 213 static int fetch(long *, int, int, FILE *, int, int); 214 static int newcand(int, int, int); 215 static int search(int *, int, int); 216 static int skipline(FILE *); 217 static int isqrt(int); 218 static int stone(int *, int, int *, int *); 219 static int readhash(FILE *); 220 static int files_differ(FILE *, FILE *, int); 221 static __inline int min(int, int); 222 static __inline int max(int, int); 223 224 225 /* 226 * chrtran points to one of 2 translation tables: cup2low if folding upper to 227 * lower case clow2low if not folding case 228 */ 229 u_char clow2low[256] = { 230 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 231 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 232 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20, 233 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 234 0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 235 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x40, 0x41, 236 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c, 237 0x4d, 0x4e, 0x4f, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 238 0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, 0x60, 0x61, 0x62, 239 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 240 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 241 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83, 242 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 243 0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 244 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 245 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 246 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 247 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 248 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0, 249 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb, 250 0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 251 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1, 252 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 253 0xfd, 0xfe, 0xff 254 }; 255 256 u_char cup2low[256] = { 257 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 258 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 259 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20, 260 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 261 0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 262 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x60, 0x61, 263 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 264 0x6d, 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 265 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x60, 0x61, 0x62, 266 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 267 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 268 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83, 269 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 270 0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 271 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 272 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 273 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 274 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 275 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0, 276 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb, 277 0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 278 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1, 279 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 280 0xfd, 0xfe, 0xff 281 }; 282 283 int 284 diffreg(char *ofile1, char *ofile2, int flags) 285 { 286 char *file1 = ofile1; 287 char *file2 = ofile2; 288 FILE *f1 = NULL; 289 FILE *f2 = NULL; 290 int rval = D_SAME; 291 int i, ostdout = -1; 292 pid_t pid = -1; 293 294 anychange = 0; 295 context_vec_ptr = context_vec_start - 1; 296 chrtran = (iflag ? cup2low : clow2low); 297 if (S_ISDIR(stb1.st_mode) != S_ISDIR(stb2.st_mode)) 298 return (S_ISDIR(stb1.st_mode) ? D_MISMATCH1 : D_MISMATCH2); 299 if (strcmp(file1, "-") == 0 && strcmp(file2, "-") == 0) 300 goto closem; 301 302 if (flags & D_EMPTY1) 303 f1 = fopen(_PATH_DEVNULL, "r"); 304 else { 305 if (!S_ISREG(stb1.st_mode)) { 306 if ((f1 = opentemp(file1)) == NULL || 307 fstat(fileno(f1), &stb1) < 0) { 308 warn("%s", file1); 309 status |= 2; 310 goto closem; 311 } 312 } else if (strcmp(file1, "-") == 0) 313 f1 = stdin; 314 else 315 f1 = fopen(file1, "r"); 316 } 317 if (f1 == NULL) { 318 warn("%s", file1); 319 status |= 2; 320 goto closem; 321 } 322 323 if (flags & D_EMPTY2) 324 f2 = fopen(_PATH_DEVNULL, "r"); 325 else { 326 if (!S_ISREG(stb2.st_mode)) { 327 if ((f2 = opentemp(file2)) == NULL || 328 fstat(fileno(f2), &stb2) < 0) { 329 warn("%s", file2); 330 status |= 2; 331 goto closem; 332 } 333 } else if (strcmp(file2, "-") == 0) 334 f2 = stdin; 335 else 336 f2 = fopen(file2, "r"); 337 } 338 if (f2 == NULL) { 339 warn("%s", file2); 340 status |= 2; 341 goto closem; 342 } 343 344 switch (files_differ(f1, f2, flags)) { 345 case 0: 346 goto closem; 347 case 1: 348 break; 349 default: 350 /* error */ 351 status |= 2; 352 goto closem; 353 } 354 355 /* 356 * Files certainly differ at this point; set status accordingly 357 */ 358 status |= 1; 359 rval = D_DIFFER; 360 if (!asciifile(f1) || !asciifile(f2)) { 361 rval = D_BINARY; 362 goto closem; 363 } 364 if (format == D_BRIEF) 365 goto closem; 366 if (lflag) { 367 /* redirect stdout to pr */ 368 int pfd[2]; 369 char *header; 370 char *prargv[] = { "pr", "-h", NULL, "-f", NULL }; 371 372 easprintf(&header, "%s %s %s", diffargs, file1, file2); 373 prargv[2] = header; 374 fflush(stdout); 375 rewind(stdout); 376 pipe(pfd); 377 switch ((pid = fork())) { 378 case -1: 379 warnx("No more processes"); 380 status |= 2; 381 free(header); 382 return (D_ERROR); 383 case 0: 384 /* child */ 385 if (pfd[0] != STDIN_FILENO) { 386 dup2(pfd[0], STDIN_FILENO); 387 close(pfd[0]); 388 } 389 close(pfd[1]); 390 execv(_PATH_PR, prargv); 391 _exit(127); 392 default: 393 /* parent */ 394 if (pfd[1] != STDOUT_FILENO) { 395 ostdout = dup(STDOUT_FILENO); 396 dup2(pfd[1], STDOUT_FILENO); 397 close(pfd[1]); 398 } 399 close(pfd[0]); 400 rewind(stdout); 401 free(header); 402 } 403 } else if (flags & D_HEADER) 404 printf("%s %s %s\n", diffargs, file1, file2); 405 prepare(0, f1); 406 prepare(1, f2); 407 prune(); 408 sort(sfile[0], slen[0]); 409 sort(sfile[1], slen[1]); 410 411 member = (int *)file[1]; 412 equiv(sfile[0], slen[0], sfile[1], slen[1], member); 413 member = erealloc(member, (slen[1] + 2) * sizeof(int)); 414 415 class = (int *)file[0]; 416 unsort(sfile[0], slen[0], class); 417 class = erealloc(class, (slen[0] + 2) * sizeof(int)); 418 419 klist = emalloc((slen[0] + 2) * sizeof(int)); 420 clen = 0; 421 clistlen = 100; 422 clist = emalloc(clistlen * sizeof(cand)); 423 i = stone(class, slen[0], member, klist); 424 free(member); 425 free(class); 426 427 J = erealloc(J, (len[0] + 2) * sizeof(int)); 428 unravel(klist[i]); 429 free(clist); 430 free(klist); 431 432 ixold = erealloc(ixold, (len[0] + 2) * sizeof(long)); 433 ixnew = erealloc(ixnew, (len[1] + 2) * sizeof(long)); 434 check(file1, f1, file2, f2); 435 output(file1, f1, file2, f2); 436 if (ostdout != -1) { 437 int wstatus; 438 439 /* close the pipe to pr and restore stdout */ 440 fflush(stdout); 441 rewind(stdout); 442 if (ostdout != STDOUT_FILENO) { 443 close(STDOUT_FILENO); 444 dup2(ostdout, STDOUT_FILENO); 445 close(ostdout); 446 } 447 waitpid(pid, &wstatus, 0); 448 } 449 closem: 450 if (f1 != NULL) 451 fclose(f1); 452 if (f2 != NULL) 453 fclose(f2); 454 if (file1 != ofile1) 455 free(file1); 456 if (file2 != ofile2) 457 free(file2); 458 return (rval); 459 } 460 461 /* 462 * Check to see if the given files differ. 463 * Returns 0 if they are the same, 1 if different, and -1 on error. 464 * XXX - could use code from cmp(1) [faster] 465 */ 466 static int 467 files_differ(FILE *f1, FILE *f2, int flags) 468 { 469 char buf1[BUFSIZ], buf2[BUFSIZ]; 470 size_t i, j; 471 472 if ((flags & (D_EMPTY1|D_EMPTY2)) || stb1.st_size != stb2.st_size || 473 (stb1.st_mode & S_IFMT) != (stb2.st_mode & S_IFMT)) 474 return (1); 475 for (;;) { 476 i = fread(buf1, 1, sizeof(buf1), f1); 477 j = fread(buf2, 1, sizeof(buf2), f2); 478 if (i != j) 479 return (1); 480 if (i == 0 && j == 0) { 481 if (ferror(f1) || ferror(f2)) 482 return (1); 483 return (0); 484 } 485 if (memcmp(buf1, buf2, i) != 0) 486 return (1); 487 } 488 } 489 490 static FILE * 491 opentemp(const char *file) 492 { 493 char buf[BUFSIZ], *tempdir, tempfile[MAXPATHLEN]; 494 ssize_t nread; 495 int ifd, ofd; 496 497 if (strcmp(file, "-") == 0) 498 ifd = STDIN_FILENO; 499 else if ((ifd = open(file, O_RDONLY, 0644)) < 0) 500 return (NULL); 501 502 if ((tempdir = getenv("TMPDIR")) == NULL) 503 tempdir = _PATH_TMP; 504 if (snprintf(tempfile, sizeof(tempfile), "%s/diff.XXXXXXXX", 505 tempdir) >= sizeof(tempfile)) { 506 close(ifd); 507 errno = ENAMETOOLONG; 508 return (NULL); 509 } 510 511 if ((ofd = mkstemp(tempfile)) < 0) 512 return (NULL); 513 unlink(tempfile); 514 while ((nread = read(ifd, buf, BUFSIZ)) > 0) { 515 if (write(ofd, buf, nread) != nread) { 516 close(ifd); 517 close(ofd); 518 return (NULL); 519 } 520 } 521 close(ifd); 522 lseek(ofd, (off_t)0, SEEK_SET); 523 return (fdopen(ofd, "r")); 524 } 525 526 char * 527 splice(char *dir, char *file) 528 { 529 char *tail, *buf; 530 531 if ((tail = strrchr(file, '/')) == NULL) 532 tail = file; 533 else 534 tail++; 535 easprintf(&buf, "%s/%s", dir, tail); 536 return (buf); 537 } 538 539 static void 540 prepare(int i, FILE *fd) 541 { 542 struct line *p; 543 int j, h; 544 545 rewind(fd); 546 p = emalloc(3 * sizeof(struct line)); 547 for (j = 0; (h = readhash(fd));) { 548 p = erealloc(p, (++j + 3) * sizeof(struct line)); 549 p[j].value = h; 550 } 551 len[i] = j; 552 file[i] = p; 553 } 554 555 static void 556 prune(void) 557 { 558 int i, j; 559 560 for (pref = 0; pref < len[0] && pref < len[1] && 561 file[0][pref + 1].value == file[1][pref + 1].value; 562 pref++) 563 ; 564 for (suff = 0; suff < len[0] - pref && suff < len[1] - pref && 565 file[0][len[0] - suff].value == file[1][len[1] - suff].value; 566 suff++) 567 ; 568 for (j = 0; j < 2; j++) { 569 sfile[j] = file[j] + pref; 570 slen[j] = len[j] - pref - suff; 571 for (i = 0; i <= slen[j]; i++) 572 sfile[j][i].serial = i; 573 } 574 } 575 576 static void 577 equiv(struct line *a, int n, struct line *b, int m, int *c) 578 { 579 int i, j; 580 581 i = j = 1; 582 while (i <= n && j <= m) { 583 if (a[i].value < b[j].value) 584 a[i++].value = 0; 585 else if (a[i].value == b[j].value) 586 a[i++].value = j; 587 else 588 j++; 589 } 590 while (i <= n) 591 a[i++].value = 0; 592 b[m + 1].value = 0; 593 j = 0; 594 while (++j <= m) { 595 c[j] = -b[j].serial; 596 while (b[j + 1].value == b[j].value) { 597 j++; 598 c[j] = b[j].serial; 599 } 600 } 601 c[j] = -1; 602 } 603 604 /* Code taken from ping.c */ 605 static int 606 isqrt(int n) 607 { 608 int y, x = 1; 609 610 if (n == 0) 611 return(0); 612 613 do { /* newton was a stinker */ 614 y = x; 615 x = n / x; 616 x += y; 617 x /= 2; 618 } while ((x - y) > 1 || (x - y) < -1); 619 620 return (x); 621 } 622 623 static int 624 stone(int *a, int n, int *b, int *c) 625 { 626 int i, k, y, j, l; 627 int oldc, tc, oldl; 628 u_int loopcount; 629 630 const u_int bound = dflag ? UINT_MAX : max(256, isqrt(n)); 631 632 k = 0; 633 c[0] = newcand(0, 0, 0); 634 for (i = 1; i <= n; i++) { 635 j = a[i]; 636 if (j == 0) 637 continue; 638 y = -b[j]; 639 oldl = 0; 640 oldc = c[0]; 641 loopcount = 0; 642 do { 643 loopcount++; 644 if (y <= clist[oldc].y) 645 continue; 646 l = search(c, k, y); 647 if (l != oldl + 1) 648 oldc = c[l - 1]; 649 if (l <= k) { 650 if (clist[c[l]].y <= y) 651 continue; 652 tc = c[l]; 653 c[l] = newcand(i, y, oldc); 654 oldc = tc; 655 oldl = l; 656 } else { 657 c[l] = newcand(i, y, oldc); 658 k++; 659 break; 660 } 661 } while ((y = b[++j]) > 0 && loopcount < bound); 662 } 663 return (k); 664 } 665 666 static int 667 newcand(int x, int y, int pred) 668 { 669 struct cand *q; 670 671 if (clen == clistlen) { 672 clistlen = clistlen * 11 / 10; 673 clist = erealloc(clist, clistlen * sizeof(cand)); 674 } 675 q = clist + clen; 676 q->x = x; 677 q->y = y; 678 q->pred = pred; 679 return (clen++); 680 } 681 682 static int 683 search(int *c, int k, int y) 684 { 685 int i, j, l, t; 686 687 if (clist[c[k]].y < y) /* quick look for typical case */ 688 return (k + 1); 689 i = 0; 690 j = k + 1; 691 while (1) { 692 l = i + j; 693 if ((l >>= 1) <= i) 694 break; 695 t = clist[c[l]].y; 696 if (t > y) 697 j = l; 698 else if (t < y) 699 i = l; 700 else 701 return (l); 702 } 703 return (l + 1); 704 } 705 706 static void 707 unravel(int p) 708 { 709 struct cand *q; 710 int i; 711 712 for (i = 0; i <= len[0]; i++) 713 J[i] = i <= pref ? i : 714 i > len[0] - suff ? i + len[1] - len[0] : 0; 715 for (q = clist + p; q->y != 0; q = clist + q->pred) 716 J[q->x + pref] = q->y + pref; 717 } 718 719 /* 720 * Check does double duty: 721 * 1. ferret out any fortuitous correspondences due 722 * to confounding by hashing (which result in "jackpot") 723 * 2. collect random access indexes to the two files 724 */ 725 static void 726 check(char *file1, FILE *f1, char *file2, FILE *f2) 727 { 728 int i, j, jackpot, c, d; 729 long ctold, ctnew; 730 731 rewind(f1); 732 rewind(f2); 733 j = 1; 734 ixold[0] = ixnew[0] = 0; 735 jackpot = 0; 736 ctold = ctnew = 0; 737 for (i = 1; i <= len[0]; i++) { 738 if (J[i] == 0) { 739 ixold[i] = ctold += skipline(f1); 740 continue; 741 } 742 while (j < J[i]) { 743 ixnew[j] = ctnew += skipline(f2); 744 j++; 745 } 746 if (bflag || wflag || iflag) { 747 for (;;) { 748 c = getc(f1); 749 d = getc(f2); 750 /* 751 * GNU diff ignores a missing newline 752 * in one file if bflag || wflag. 753 */ 754 if ((bflag || wflag) && 755 ((c == EOF && d == '\n') || 756 (c == '\n' && d == EOF))) { 757 break; 758 } 759 ctold++; 760 ctnew++; 761 if (bflag && isspace(c) && isspace(d)) { 762 do { 763 if (c == '\n') 764 break; 765 ctold++; 766 } while (isspace(c = getc(f1))); 767 do { 768 if (d == '\n') 769 break; 770 ctnew++; 771 } while (isspace(d = getc(f2))); 772 } else if (wflag) { 773 while (isspace(c) && c != '\n') { 774 c = getc(f1); 775 ctold++; 776 } 777 while (isspace(d) && d != '\n') { 778 d = getc(f2); 779 ctnew++; 780 } 781 } 782 if (chrtran[c] != chrtran[d]) { 783 jackpot++; 784 J[i] = 0; 785 if (c != '\n' && c != EOF) 786 ctold += skipline(f1); 787 if (d != '\n' && c != EOF) 788 ctnew += skipline(f2); 789 break; 790 } 791 if (c == '\n' || c == EOF) 792 break; 793 } 794 } else { 795 for (;;) { 796 ctold++; 797 ctnew++; 798 if ((c = getc(f1)) != (d = getc(f2))) { 799 /* jackpot++; */ 800 J[i] = 0; 801 if (c != '\n' && c != EOF) 802 ctold += skipline(f1); 803 if (d != '\n' && c != EOF) 804 ctnew += skipline(f2); 805 break; 806 } 807 if (c == '\n' || c == EOF) 808 break; 809 } 810 } 811 ixold[i] = ctold; 812 ixnew[j] = ctnew; 813 j++; 814 } 815 for (; j <= len[1]; j++) 816 ixnew[j] = ctnew += skipline(f2); 817 /* 818 * if (jackpot) 819 * fprintf(stderr, "jackpot\n"); 820 */ 821 } 822 823 /* shellsort CACM #201 */ 824 static void 825 sort(struct line *a, int n) 826 { 827 struct line *ai, *aim, w; 828 int j, m = 0, k; 829 830 if (n == 0) 831 return; 832 for (j = 1; j <= n; j *= 2) 833 m = 2 * j - 1; 834 for (m /= 2; m != 0; m /= 2) { 835 k = n - m; 836 for (j = 1; j <= k; j++) { 837 for (ai = &a[j]; ai > a; ai -= m) { 838 aim = &ai[m]; 839 if (aim < ai) 840 break; /* wraparound */ 841 if (aim->value > ai[0].value || 842 (aim->value == ai[0].value && 843 aim->serial > ai[0].serial)) 844 break; 845 w.value = ai[0].value; 846 ai[0].value = aim->value; 847 aim->value = w.value; 848 w.serial = ai[0].serial; 849 ai[0].serial = aim->serial; 850 aim->serial = w.serial; 851 } 852 } 853 } 854 } 855 856 static void 857 unsort(struct line *f, int l, int *b) 858 { 859 int *a, i; 860 861 a = emalloc((l + 1) * sizeof(int)); 862 for (i = 1; i <= l; i++) 863 a[f[i].serial] = f[i].value; 864 for (i = 1; i <= l; i++) 865 b[i] = a[i]; 866 free(a); 867 } 868 869 static int 870 skipline(FILE *f) 871 { 872 int i, c; 873 874 for (i = 1; (c = getc(f)) != '\n' && c != EOF; i++) 875 continue; 876 return (i); 877 } 878 879 static void 880 output(char *file1, FILE *f1, char *file2, FILE *f2) 881 { 882 int m, i0, i1, j0, j1; 883 884 rewind(f1); 885 rewind(f2); 886 m = len[0]; 887 J[0] = 0; 888 J[m + 1] = len[1] + 1; 889 if (format != D_EDIT) { 890 for (i0 = 1; i0 <= m; i0 = i1 + 1) { 891 while (i0 <= m && J[i0] == J[i0 - 1] + 1) 892 i0++; 893 j0 = J[i0 - 1] + 1; 894 i1 = i0 - 1; 895 while (i1 < m && J[i1 + 1] == 0) 896 i1++; 897 j1 = J[i1 + 1] - 1; 898 J[i1] = j1; 899 change(file1, f1, file2, f2, i0, i1, j0, j1); 900 } 901 } else { 902 for (i0 = m; i0 >= 1; i0 = i1 - 1) { 903 while (i0 >= 1 && J[i0] == J[i0 + 1] - 1 && J[i0] != 0) 904 i0--; 905 j0 = J[i0 + 1] - 1; 906 i1 = i0 + 1; 907 while (i1 > 1 && J[i1 - 1] == 0) 908 i1--; 909 j1 = J[i1 - 1] + 1; 910 J[i1] = j1; 911 change(file1, f1, file2, f2, i1, i0, j1, j0); 912 } 913 } 914 if (m == 0) 915 change(file1, f1, file2, f2, 1, 0, 1, len[1]); 916 if (format == D_IFDEF) { 917 for (;;) { 918 #define c i0 919 if ((c = getc(f1)) == EOF) 920 return; 921 putchar(c); 922 } 923 #undef c 924 } 925 if (anychange != 0) { 926 if (format == D_CONTEXT) 927 dump_context_vec(f1, f2); 928 else if (format == D_UNIFIED) 929 dump_unified_vec(f1, f2); 930 } 931 } 932 933 static __inline void 934 range(int a, int b, char *separator) 935 { 936 printf("%d", a > b ? b : a); 937 if (a < b) 938 printf("%s%d", separator, b); 939 } 940 941 static __inline void 942 uni_range(int a, int b) 943 { 944 if (a < b) 945 printf("%d,%d", a, b - a + 1); 946 else if (a == b) 947 printf("%d", b); 948 else 949 printf("%d,0", b); 950 } 951 952 /* 953 * Indicate that there is a difference between lines a and b of the from file 954 * to get to lines c to d of the to file. If a is greater then b then there 955 * are no lines in the from file involved and this means that there were 956 * lines appended (beginning at b). If c is greater than d then there are 957 * lines missing from the to file. 958 */ 959 static void 960 change(char *file1, FILE *f1, char *file2, FILE *f2, int a, int b, int c, int d) 961 { 962 static size_t max_context = 64; 963 int i; 964 965 restart: 966 if (format != D_IFDEF && a > b && c > d) 967 return; 968 if (format == D_CONTEXT || format == D_UNIFIED) { 969 /* 970 * Allocate change records as needed. 971 */ 972 if (context_vec_ptr == context_vec_end - 1) { 973 ptrdiff_t offset = context_vec_ptr - context_vec_start; 974 max_context <<= 1; 975 context_vec_start = erealloc(context_vec_start, 976 max_context * sizeof(struct context_vec)); 977 context_vec_end = context_vec_start + max_context; 978 context_vec_ptr = context_vec_start + offset; 979 } 980 if (anychange == 0) { 981 /* 982 * Print the context/unidiff header first time through. 983 */ 984 if (label != NULL) 985 printf("%s %s\n", 986 format == D_CONTEXT ? "***" : "---", label); 987 else 988 printf("%s %s %s", 989 format == D_CONTEXT ? "***" : "---", file1, 990 ctime(&stb1.st_mtime)); 991 printf("%s %s %s", 992 format == D_CONTEXT ? "---" : "+++", file2, 993 ctime(&stb2.st_mtime)); 994 anychange = 1; 995 } else if (a > context_vec_ptr->b + (2 * context) && 996 c > context_vec_ptr->d + (2 * context)) { 997 /* 998 * If this change is more than 'context' lines from the 999 * previous change, dump the record and reset it. 1000 */ 1001 if (format == D_CONTEXT) 1002 dump_context_vec(f1, f2); 1003 else 1004 dump_unified_vec(f1, f2); 1005 } 1006 context_vec_ptr++; 1007 context_vec_ptr->a = a; 1008 context_vec_ptr->b = b; 1009 context_vec_ptr->c = c; 1010 context_vec_ptr->d = d; 1011 return; 1012 } 1013 if (anychange == 0) 1014 anychange = 1; 1015 switch (format) { 1016 1017 case D_NORMAL: 1018 case D_EDIT: 1019 range(a, b, ","); 1020 putchar(a > b ? 'a' : c > d ? 'd' : 'c'); 1021 if (format == D_NORMAL) 1022 range(c, d, ","); 1023 putchar('\n'); 1024 break; 1025 case D_REVERSE: 1026 putchar(a > b ? 'a' : c > d ? 'd' : 'c'); 1027 range(a, b, " "); 1028 putchar('\n'); 1029 break; 1030 case D_NREVERSE: 1031 if (a > b) 1032 printf("a%d %d\n", b, d - c + 1); 1033 else { 1034 printf("d%d %d\n", a, b - a + 1); 1035 if (!(c > d)) 1036 /* add changed lines */ 1037 printf("a%d %d\n", b, d - c + 1); 1038 } 1039 break; 1040 } 1041 if (format == D_NORMAL || format == D_IFDEF) { 1042 fetch(ixold, a, b, f1, '<', 1); 1043 if (a <= b && c <= d && format == D_NORMAL) 1044 puts("---"); 1045 } 1046 i = fetch(ixnew, c, d, f2, format == D_NORMAL ? '>' : '\0', 0); 1047 if (i != 0 && format == D_EDIT) { 1048 /* 1049 * A non-zero return value for D_EDIT indicates that the 1050 * last line printed was a bare dot (".") that has been 1051 * escaped as ".." to prevent ed(1) from misinterpreting 1052 * it. We have to add a substitute command to change this 1053 * back and restart where we left off. 1054 */ 1055 puts("."); 1056 printf("%ds/^\\.\\././\n", a); 1057 a += i; 1058 c += i; 1059 goto restart; 1060 } 1061 if ((format == D_EDIT || format == D_REVERSE) && c <= d) 1062 puts("."); 1063 if (inifdef) { 1064 printf("#endif /* %s */\n", ifdefname); 1065 inifdef = 0; 1066 } 1067 } 1068 1069 static int 1070 fetch(long *f, int a, int b, FILE *lb, int ch, int oldfile) 1071 { 1072 int i, j, c, lastc, col, nc; 1073 1074 /* 1075 * When doing #ifdef's, copy down to current line 1076 * if this is the first file, so that stuff makes it to output. 1077 */ 1078 if (format == D_IFDEF && oldfile) { 1079 long curpos = ftell(lb); 1080 /* print through if append (a>b), else to (nb: 0 vs 1 orig) */ 1081 nc = f[a > b ? b : a - 1] - curpos; 1082 for (i = 0; i < nc; i++) 1083 putchar(getc(lb)); 1084 } 1085 if (a > b) 1086 return (0); 1087 if (format == D_IFDEF) { 1088 if (inifdef) { 1089 printf("#else /* %s%s */\n", 1090 oldfile == 1 ? "!" : "", ifdefname); 1091 } else { 1092 if (oldfile) 1093 printf("#ifndef %s\n", ifdefname); 1094 else 1095 printf("#ifdef %s\n", ifdefname); 1096 } 1097 inifdef = 1 + oldfile; 1098 } 1099 for (i = a; i <= b; i++) { 1100 fseek(lb, f[i - 1], SEEK_SET); 1101 nc = f[i] - f[i - 1]; 1102 if (format != D_IFDEF && ch != '\0') { 1103 putchar(ch); 1104 if (Tflag && (format == D_NORMAL || format == D_CONTEXT 1105 || format == D_UNIFIED)) 1106 putchar('\t'); 1107 else if (format != D_UNIFIED) 1108 putchar(' '); 1109 } 1110 col = 0; 1111 for (j = 0, lastc = '\0'; j < nc; j++, lastc = c) { 1112 if ((c = getc(lb)) == EOF) { 1113 puts("\n\\ No newline at end of file"); 1114 return (0);; 1115 } 1116 if (c == '\t' && tflag) { 1117 do { 1118 putchar(' '); 1119 } while (++col & 7); 1120 } else { 1121 if (format == D_EDIT && j == 1 && c == '\n' 1122 && lastc == '.') { 1123 /* 1124 * Don't print a bare "." line 1125 * since that will confuse ed(1). 1126 * Print ".." instead and return, 1127 * giving the caller an offset 1128 * from which to restart. 1129 */ 1130 puts("."); 1131 return (i - a + 1); 1132 } 1133 putchar(c); 1134 col++; 1135 } 1136 } 1137 } 1138 return (0); 1139 } 1140 1141 #define HASHMASK (16 - 1) /* for masking out 16 bytes */ 1142 1143 /* 1144 * hashing has the effect of 1145 * arranging line in 7-bit bytes and then 1146 * summing 1-s complement in 16-bit hunks 1147 */ 1148 static int 1149 readhash(FILE *f) 1150 { 1151 unsigned int shift; 1152 int t, space; 1153 long sum; 1154 1155 sum = 1; 1156 space = 0; 1157 if (!bflag && !wflag) { 1158 if (iflag) 1159 for (shift = 0; (t = getc(f)) != '\n'; shift += 7) { 1160 if (t == EOF) { 1161 if (shift == 0) 1162 return (0); 1163 break; 1164 } 1165 sum += (long)chrtran[t] << (shift &= HASHMASK); 1166 } 1167 else 1168 for (shift = 0; (t = getc(f)) != '\n'; shift += 7) { 1169 if (t == EOF) { 1170 if (shift == 0) 1171 return (0); 1172 break; 1173 } 1174 sum += (long)t << (shift &= HASHMASK); 1175 } 1176 } else { 1177 for (shift = 0;;) { 1178 switch (t = getc(f)) { 1179 case '\t': 1180 case ' ': 1181 space++; 1182 continue; 1183 default: 1184 if (space && !wflag) { 1185 shift += 7; 1186 space = 0; 1187 } 1188 sum += (long)chrtran[t] << (shift &= HASHMASK); 1189 shift += 7; 1190 continue; 1191 case EOF: 1192 if (shift == 0) 1193 return (0); 1194 /* FALLTHROUGH */ 1195 case '\n': 1196 break; 1197 } 1198 break; 1199 } 1200 } 1201 return (sum); 1202 } 1203 1204 int 1205 asciifile(FILE *f) 1206 { 1207 char buf[BUFSIZ], *cp; 1208 int i, cnt; 1209 1210 if (aflag || f == NULL) 1211 return (1); 1212 1213 rewind(f); 1214 cnt = fread(buf, 1, sizeof(buf), f); 1215 cp = buf; 1216 for (i = 0; i < cnt; i++) 1217 if (!isprint(*cp) && !isspace(*cp)) 1218 return (0); 1219 return (1); 1220 } 1221 1222 static __inline int min(int a, int b) 1223 { 1224 return (a < b ? a : b); 1225 } 1226 1227 static __inline int max(int a, int b) 1228 { 1229 return (a > b ? a : b); 1230 } 1231 1232 /* dump accumulated "context" diff changes */ 1233 static void 1234 dump_context_vec(FILE *f1, FILE *f2) 1235 { 1236 struct context_vec *cvp = context_vec_start; 1237 int lowa, upb, lowc, upd, do_output; 1238 int a, b, c, d; 1239 char ch; 1240 1241 if (context_vec_start > context_vec_ptr) 1242 return; 1243 1244 b = d = 0; /* gcc */ 1245 lowa = max(1, cvp->a - context); 1246 upb = min(len[0], context_vec_ptr->b + context); 1247 lowc = max(1, cvp->c - context); 1248 upd = min(len[1], context_vec_ptr->d + context); 1249 1250 printf("***************\n*** "); 1251 range(lowa, upb, ","); 1252 printf(" ****\n"); 1253 1254 /* 1255 * Output changes to the "old" file. The first loop suppresses 1256 * output if there were no changes to the "old" file (we'll see 1257 * the "old" lines as context in the "new" list). 1258 */ 1259 do_output = 0; 1260 for (; cvp <= context_vec_ptr; cvp++) 1261 if (cvp->a <= cvp->b) { 1262 cvp = context_vec_start; 1263 do_output++; 1264 break; 1265 } 1266 if (do_output) { 1267 while (cvp <= context_vec_ptr) { 1268 a = cvp->a; 1269 b = cvp->b; 1270 c = cvp->c; 1271 d = cvp->d; 1272 1273 if (a <= b && c <= d) 1274 ch = 'c'; 1275 else 1276 ch = (a <= b) ? 'd' : 'a'; 1277 1278 if (ch == 'a') 1279 fetch(ixold, lowa, b, f1, ' ', 0); 1280 else { 1281 fetch(ixold, lowa, a - 1, f1, ' ', 0); 1282 fetch(ixold, a, b, f1, 1283 ch == 'c' ? '!' : '-', 0); 1284 } 1285 lowa = b + 1; 1286 cvp++; 1287 } 1288 fetch(ixold, b + 1, upb, f1, ' ', 0); 1289 } 1290 /* output changes to the "new" file */ 1291 printf("--- "); 1292 range(lowc, upd, ","); 1293 printf(" ----\n"); 1294 1295 do_output = 0; 1296 for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++) 1297 if (cvp->c <= cvp->d) { 1298 cvp = context_vec_start; 1299 do_output++; 1300 break; 1301 } 1302 if (do_output) { 1303 while (cvp <= context_vec_ptr) { 1304 a = cvp->a; 1305 b = cvp->b; 1306 c = cvp->c; 1307 d = cvp->d; 1308 1309 if (a <= b && c <= d) 1310 ch = 'c'; 1311 else 1312 ch = (a <= b) ? 'd' : 'a'; 1313 1314 if (ch == 'd') 1315 fetch(ixnew, lowc, d, f2, ' ', 0); 1316 else { 1317 fetch(ixnew, lowc, c - 1, f2, ' ', 0); 1318 fetch(ixnew, c, d, f2, 1319 ch == 'c' ? '!' : '+', 0); 1320 } 1321 lowc = d + 1; 1322 cvp++; 1323 } 1324 fetch(ixnew, d + 1, upd, f2, ' ', 0); 1325 } 1326 context_vec_ptr = context_vec_start - 1; 1327 } 1328 1329 /* dump accumulated "unified" diff changes */ 1330 static void 1331 dump_unified_vec(FILE *f1, FILE *f2) 1332 { 1333 struct context_vec *cvp = context_vec_start; 1334 int lowa, upb, lowc, upd; 1335 int a, b, c, d; 1336 char ch; 1337 1338 if (context_vec_start > context_vec_ptr) 1339 return; 1340 1341 b = d = 0; /* gcc */ 1342 lowa = max(1, cvp->a - context); 1343 upb = min(len[0], context_vec_ptr->b + context); 1344 lowc = max(1, cvp->c - context); 1345 upd = min(len[1], context_vec_ptr->d + context); 1346 1347 fputs("@@ -", stdout); 1348 uni_range(lowa, upb); 1349 fputs(" +", stdout); 1350 uni_range(lowc, upd); 1351 fputs(" @@\n", stdout); 1352 1353 /* 1354 * Output changes in "unified" diff format--the old and new lines 1355 * are printed together. 1356 */ 1357 for (; cvp <= context_vec_ptr; cvp++) { 1358 a = cvp->a; 1359 b = cvp->b; 1360 c = cvp->c; 1361 d = cvp->d; 1362 1363 /* 1364 * c: both new and old changes 1365 * d: only changes in the old file 1366 * a: only changes in the new file 1367 */ 1368 if (a <= b && c <= d) 1369 ch = 'c'; 1370 else 1371 ch = (a <= b) ? 'd' : 'a'; 1372 1373 switch (ch) { 1374 case 'c': 1375 fetch(ixold, lowa, a - 1, f1, ' ', 0); 1376 fetch(ixold, a, b, f1, '-', 0); 1377 fetch(ixnew, c, d, f2, '+', 0); 1378 break; 1379 case 'd': 1380 fetch(ixold, lowa, a - 1, f1, ' ', 0); 1381 fetch(ixold, a, b, f1, '-', 0); 1382 break; 1383 case 'a': 1384 fetch(ixnew, lowc, c - 1, f2, ' ', 0); 1385 fetch(ixnew, c, d, f2, '+', 0); 1386 break; 1387 } 1388 lowa = b + 1; 1389 lowc = d + 1; 1390 } 1391 fetch(ixnew, d + 1, upd, f2, ' ', 0); 1392 1393 context_vec_ptr = context_vec_start - 1; 1394 } 1395