1 /* $OpenBSD: diffreg.c,v 1.47 2003/07/31 20:00:03 otto 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.47 2003/07/31 20:00:03 otto 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 int sz; 545 546 rewind(fd); 547 sz = 100; 548 p = emalloc((sz + 3) * sizeof(struct line)); 549 for (j = 0; (h = readhash(fd));) { 550 if (j == sz) { 551 sz = sz * 3 / 2; 552 p = erealloc(p, (sz + 3) * sizeof(struct line)); 553 } 554 p[++j].value = h; 555 } 556 len[i] = j; 557 file[i] = p; 558 } 559 560 static void 561 prune(void) 562 { 563 int i, j; 564 565 for (pref = 0; pref < len[0] && pref < len[1] && 566 file[0][pref + 1].value == file[1][pref + 1].value; 567 pref++) 568 ; 569 for (suff = 0; suff < len[0] - pref && suff < len[1] - pref && 570 file[0][len[0] - suff].value == file[1][len[1] - suff].value; 571 suff++) 572 ; 573 for (j = 0; j < 2; j++) { 574 sfile[j] = file[j] + pref; 575 slen[j] = len[j] - pref - suff; 576 for (i = 0; i <= slen[j]; i++) 577 sfile[j][i].serial = i; 578 } 579 } 580 581 static void 582 equiv(struct line *a, int n, struct line *b, int m, int *c) 583 { 584 int i, j; 585 586 i = j = 1; 587 while (i <= n && j <= m) { 588 if (a[i].value < b[j].value) 589 a[i++].value = 0; 590 else if (a[i].value == b[j].value) 591 a[i++].value = j; 592 else 593 j++; 594 } 595 while (i <= n) 596 a[i++].value = 0; 597 b[m + 1].value = 0; 598 j = 0; 599 while (++j <= m) { 600 c[j] = -b[j].serial; 601 while (b[j + 1].value == b[j].value) { 602 j++; 603 c[j] = b[j].serial; 604 } 605 } 606 c[j] = -1; 607 } 608 609 /* Code taken from ping.c */ 610 static int 611 isqrt(int n) 612 { 613 int y, x = 1; 614 615 if (n == 0) 616 return(0); 617 618 do { /* newton was a stinker */ 619 y = x; 620 x = n / x; 621 x += y; 622 x /= 2; 623 } while ((x - y) > 1 || (x - y) < -1); 624 625 return (x); 626 } 627 628 static int 629 stone(int *a, int n, int *b, int *c) 630 { 631 int i, k, y, j, l; 632 int oldc, tc, oldl; 633 u_int loopcount; 634 635 const u_int bound = dflag ? UINT_MAX : max(256, isqrt(n)); 636 637 k = 0; 638 c[0] = newcand(0, 0, 0); 639 for (i = 1; i <= n; i++) { 640 j = a[i]; 641 if (j == 0) 642 continue; 643 y = -b[j]; 644 oldl = 0; 645 oldc = c[0]; 646 loopcount = 0; 647 do { 648 loopcount++; 649 if (y <= clist[oldc].y) 650 continue; 651 l = search(c, k, y); 652 if (l != oldl + 1) 653 oldc = c[l - 1]; 654 if (l <= k) { 655 if (clist[c[l]].y <= y) 656 continue; 657 tc = c[l]; 658 c[l] = newcand(i, y, oldc); 659 oldc = tc; 660 oldl = l; 661 } else { 662 c[l] = newcand(i, y, oldc); 663 k++; 664 break; 665 } 666 } while ((y = b[++j]) > 0 && loopcount < bound); 667 } 668 return (k); 669 } 670 671 static int 672 newcand(int x, int y, int pred) 673 { 674 struct cand *q; 675 676 if (clen == clistlen) { 677 clistlen = clistlen * 11 / 10; 678 clist = erealloc(clist, clistlen * sizeof(cand)); 679 } 680 q = clist + clen; 681 q->x = x; 682 q->y = y; 683 q->pred = pred; 684 return (clen++); 685 } 686 687 static int 688 search(int *c, int k, int y) 689 { 690 int i, j, l, t; 691 692 if (clist[c[k]].y < y) /* quick look for typical case */ 693 return (k + 1); 694 i = 0; 695 j = k + 1; 696 while (1) { 697 l = i + j; 698 if ((l >>= 1) <= i) 699 break; 700 t = clist[c[l]].y; 701 if (t > y) 702 j = l; 703 else if (t < y) 704 i = l; 705 else 706 return (l); 707 } 708 return (l + 1); 709 } 710 711 static void 712 unravel(int p) 713 { 714 struct cand *q; 715 int i; 716 717 for (i = 0; i <= len[0]; i++) 718 J[i] = i <= pref ? i : 719 i > len[0] - suff ? i + len[1] - len[0] : 0; 720 for (q = clist + p; q->y != 0; q = clist + q->pred) 721 J[q->x + pref] = q->y + pref; 722 } 723 724 /* 725 * Check does double duty: 726 * 1. ferret out any fortuitous correspondences due 727 * to confounding by hashing (which result in "jackpot") 728 * 2. collect random access indexes to the two files 729 */ 730 static void 731 check(char *file1, FILE *f1, char *file2, FILE *f2) 732 { 733 int i, j, jackpot, c, d; 734 long ctold, ctnew; 735 736 rewind(f1); 737 rewind(f2); 738 j = 1; 739 ixold[0] = ixnew[0] = 0; 740 jackpot = 0; 741 ctold = ctnew = 0; 742 for (i = 1; i <= len[0]; i++) { 743 if (J[i] == 0) { 744 ixold[i] = ctold += skipline(f1); 745 continue; 746 } 747 while (j < J[i]) { 748 ixnew[j] = ctnew += skipline(f2); 749 j++; 750 } 751 if (bflag || wflag || iflag) { 752 for (;;) { 753 c = getc(f1); 754 d = getc(f2); 755 /* 756 * GNU diff ignores a missing newline 757 * in one file if bflag || wflag. 758 */ 759 if ((bflag || wflag) && 760 ((c == EOF && d == '\n') || 761 (c == '\n' && d == EOF))) { 762 break; 763 } 764 ctold++; 765 ctnew++; 766 if (bflag && isspace(c) && isspace(d)) { 767 do { 768 if (c == '\n') 769 break; 770 ctold++; 771 } while (isspace(c = getc(f1))); 772 do { 773 if (d == '\n') 774 break; 775 ctnew++; 776 } while (isspace(d = getc(f2))); 777 } else if (wflag) { 778 while (isspace(c) && c != '\n') { 779 c = getc(f1); 780 ctold++; 781 } 782 while (isspace(d) && d != '\n') { 783 d = getc(f2); 784 ctnew++; 785 } 786 } 787 if (chrtran[c] != chrtran[d]) { 788 jackpot++; 789 J[i] = 0; 790 if (c != '\n' && c != EOF) 791 ctold += skipline(f1); 792 if (d != '\n' && c != EOF) 793 ctnew += skipline(f2); 794 break; 795 } 796 if (c == '\n' || c == EOF) 797 break; 798 } 799 } else { 800 for (;;) { 801 ctold++; 802 ctnew++; 803 if ((c = getc(f1)) != (d = getc(f2))) { 804 /* jackpot++; */ 805 J[i] = 0; 806 if (c != '\n' && c != EOF) 807 ctold += skipline(f1); 808 if (d != '\n' && c != EOF) 809 ctnew += skipline(f2); 810 break; 811 } 812 if (c == '\n' || c == EOF) 813 break; 814 } 815 } 816 ixold[i] = ctold; 817 ixnew[j] = ctnew; 818 j++; 819 } 820 for (; j <= len[1]; j++) 821 ixnew[j] = ctnew += skipline(f2); 822 /* 823 * if (jackpot) 824 * fprintf(stderr, "jackpot\n"); 825 */ 826 } 827 828 /* shellsort CACM #201 */ 829 static void 830 sort(struct line *a, int n) 831 { 832 struct line *ai, *aim, w; 833 int j, m = 0, k; 834 835 if (n == 0) 836 return; 837 for (j = 1; j <= n; j *= 2) 838 m = 2 * j - 1; 839 for (m /= 2; m != 0; m /= 2) { 840 k = n - m; 841 for (j = 1; j <= k; j++) { 842 for (ai = &a[j]; ai > a; ai -= m) { 843 aim = &ai[m]; 844 if (aim < ai) 845 break; /* wraparound */ 846 if (aim->value > ai[0].value || 847 (aim->value == ai[0].value && 848 aim->serial > ai[0].serial)) 849 break; 850 w.value = ai[0].value; 851 ai[0].value = aim->value; 852 aim->value = w.value; 853 w.serial = ai[0].serial; 854 ai[0].serial = aim->serial; 855 aim->serial = w.serial; 856 } 857 } 858 } 859 } 860 861 static void 862 unsort(struct line *f, int l, int *b) 863 { 864 int *a, i; 865 866 a = emalloc((l + 1) * sizeof(int)); 867 for (i = 1; i <= l; i++) 868 a[f[i].serial] = f[i].value; 869 for (i = 1; i <= l; i++) 870 b[i] = a[i]; 871 free(a); 872 } 873 874 static int 875 skipline(FILE *f) 876 { 877 int i, c; 878 879 for (i = 1; (c = getc(f)) != '\n' && c != EOF; i++) 880 continue; 881 return (i); 882 } 883 884 static void 885 output(char *file1, FILE *f1, char *file2, FILE *f2) 886 { 887 int m, i0, i1, j0, j1; 888 889 rewind(f1); 890 rewind(f2); 891 m = len[0]; 892 J[0] = 0; 893 J[m + 1] = len[1] + 1; 894 if (format != D_EDIT) { 895 for (i0 = 1; i0 <= m; i0 = i1 + 1) { 896 while (i0 <= m && J[i0] == J[i0 - 1] + 1) 897 i0++; 898 j0 = J[i0 - 1] + 1; 899 i1 = i0 - 1; 900 while (i1 < m && J[i1 + 1] == 0) 901 i1++; 902 j1 = J[i1 + 1] - 1; 903 J[i1] = j1; 904 change(file1, f1, file2, f2, i0, i1, j0, j1); 905 } 906 } else { 907 for (i0 = m; i0 >= 1; i0 = i1 - 1) { 908 while (i0 >= 1 && J[i0] == J[i0 + 1] - 1 && J[i0] != 0) 909 i0--; 910 j0 = J[i0 + 1] - 1; 911 i1 = i0 + 1; 912 while (i1 > 1 && J[i1 - 1] == 0) 913 i1--; 914 j1 = J[i1 - 1] + 1; 915 J[i1] = j1; 916 change(file1, f1, file2, f2, i1, i0, j1, j0); 917 } 918 } 919 if (m == 0) 920 change(file1, f1, file2, f2, 1, 0, 1, len[1]); 921 if (format == D_IFDEF) { 922 for (;;) { 923 #define c i0 924 if ((c = getc(f1)) == EOF) 925 return; 926 putchar(c); 927 } 928 #undef c 929 } 930 if (anychange != 0) { 931 if (format == D_CONTEXT) 932 dump_context_vec(f1, f2); 933 else if (format == D_UNIFIED) 934 dump_unified_vec(f1, f2); 935 } 936 } 937 938 static __inline void 939 range(int a, int b, char *separator) 940 { 941 printf("%d", a > b ? b : a); 942 if (a < b) 943 printf("%s%d", separator, b); 944 } 945 946 static __inline void 947 uni_range(int a, int b) 948 { 949 if (a < b) 950 printf("%d,%d", a, b - a + 1); 951 else if (a == b) 952 printf("%d", b); 953 else 954 printf("%d,0", b); 955 } 956 957 /* 958 * Indicate that there is a difference between lines a and b of the from file 959 * to get to lines c to d of the to file. If a is greater then b then there 960 * are no lines in the from file involved and this means that there were 961 * lines appended (beginning at b). If c is greater than d then there are 962 * lines missing from the to file. 963 */ 964 static void 965 change(char *file1, FILE *f1, char *file2, FILE *f2, int a, int b, int c, int d) 966 { 967 static size_t max_context = 64; 968 int i; 969 970 restart: 971 if (format != D_IFDEF && a > b && c > d) 972 return; 973 if (format == D_CONTEXT || format == D_UNIFIED) { 974 /* 975 * Allocate change records as needed. 976 */ 977 if (context_vec_ptr == context_vec_end - 1) { 978 ptrdiff_t offset = context_vec_ptr - context_vec_start; 979 max_context <<= 1; 980 context_vec_start = erealloc(context_vec_start, 981 max_context * sizeof(struct context_vec)); 982 context_vec_end = context_vec_start + max_context; 983 context_vec_ptr = context_vec_start + offset; 984 } 985 if (anychange == 0) { 986 /* 987 * Print the context/unidiff header first time through. 988 */ 989 if (label != NULL) 990 printf("%s %s\n", 991 format == D_CONTEXT ? "***" : "---", label); 992 else 993 printf("%s %s %s", 994 format == D_CONTEXT ? "***" : "---", file1, 995 ctime(&stb1.st_mtime)); 996 printf("%s %s %s", 997 format == D_CONTEXT ? "---" : "+++", file2, 998 ctime(&stb2.st_mtime)); 999 anychange = 1; 1000 } else if (a > context_vec_ptr->b + (2 * context) && 1001 c > context_vec_ptr->d + (2 * context)) { 1002 /* 1003 * If this change is more than 'context' lines from the 1004 * previous change, dump the record and reset it. 1005 */ 1006 if (format == D_CONTEXT) 1007 dump_context_vec(f1, f2); 1008 else 1009 dump_unified_vec(f1, f2); 1010 } 1011 context_vec_ptr++; 1012 context_vec_ptr->a = a; 1013 context_vec_ptr->b = b; 1014 context_vec_ptr->c = c; 1015 context_vec_ptr->d = d; 1016 return; 1017 } 1018 if (anychange == 0) 1019 anychange = 1; 1020 switch (format) { 1021 1022 case D_NORMAL: 1023 case D_EDIT: 1024 range(a, b, ","); 1025 putchar(a > b ? 'a' : c > d ? 'd' : 'c'); 1026 if (format == D_NORMAL) 1027 range(c, d, ","); 1028 putchar('\n'); 1029 break; 1030 case D_REVERSE: 1031 putchar(a > b ? 'a' : c > d ? 'd' : 'c'); 1032 range(a, b, " "); 1033 putchar('\n'); 1034 break; 1035 case D_NREVERSE: 1036 if (a > b) 1037 printf("a%d %d\n", b, d - c + 1); 1038 else { 1039 printf("d%d %d\n", a, b - a + 1); 1040 if (!(c > d)) 1041 /* add changed lines */ 1042 printf("a%d %d\n", b, d - c + 1); 1043 } 1044 break; 1045 } 1046 if (format == D_NORMAL || format == D_IFDEF) { 1047 fetch(ixold, a, b, f1, '<', 1); 1048 if (a <= b && c <= d && format == D_NORMAL) 1049 puts("---"); 1050 } 1051 i = fetch(ixnew, c, d, f2, format == D_NORMAL ? '>' : '\0', 0); 1052 if (i != 0 && format == D_EDIT) { 1053 /* 1054 * A non-zero return value for D_EDIT indicates that the 1055 * last line printed was a bare dot (".") that has been 1056 * escaped as ".." to prevent ed(1) from misinterpreting 1057 * it. We have to add a substitute command to change this 1058 * back and restart where we left off. 1059 */ 1060 puts("."); 1061 printf("%ds/^\\.\\././\n", a); 1062 a += i; 1063 c += i; 1064 goto restart; 1065 } 1066 if ((format == D_EDIT || format == D_REVERSE) && c <= d) 1067 puts("."); 1068 if (inifdef) { 1069 printf("#endif /* %s */\n", ifdefname); 1070 inifdef = 0; 1071 } 1072 } 1073 1074 static int 1075 fetch(long *f, int a, int b, FILE *lb, int ch, int oldfile) 1076 { 1077 int i, j, c, lastc, col, nc; 1078 1079 /* 1080 * When doing #ifdef's, copy down to current line 1081 * if this is the first file, so that stuff makes it to output. 1082 */ 1083 if (format == D_IFDEF && oldfile) { 1084 long curpos = ftell(lb); 1085 /* print through if append (a>b), else to (nb: 0 vs 1 orig) */ 1086 nc = f[a > b ? b : a - 1] - curpos; 1087 for (i = 0; i < nc; i++) 1088 putchar(getc(lb)); 1089 } 1090 if (a > b) 1091 return (0); 1092 if (format == D_IFDEF) { 1093 if (inifdef) { 1094 printf("#else /* %s%s */\n", 1095 oldfile == 1 ? "!" : "", ifdefname); 1096 } else { 1097 if (oldfile) 1098 printf("#ifndef %s\n", ifdefname); 1099 else 1100 printf("#ifdef %s\n", ifdefname); 1101 } 1102 inifdef = 1 + oldfile; 1103 } 1104 for (i = a; i <= b; i++) { 1105 fseek(lb, f[i - 1], SEEK_SET); 1106 nc = f[i] - f[i - 1]; 1107 if (format != D_IFDEF && ch != '\0') { 1108 putchar(ch); 1109 if (Tflag && (format == D_NORMAL || format == D_CONTEXT 1110 || format == D_UNIFIED)) 1111 putchar('\t'); 1112 else if (format != D_UNIFIED) 1113 putchar(' '); 1114 } 1115 col = 0; 1116 for (j = 0, lastc = '\0'; j < nc; j++, lastc = c) { 1117 if ((c = getc(lb)) == EOF) { 1118 puts("\n\\ No newline at end of file"); 1119 return (0);; 1120 } 1121 if (c == '\t' && tflag) { 1122 do { 1123 putchar(' '); 1124 } while (++col & 7); 1125 } else { 1126 if (format == D_EDIT && j == 1 && c == '\n' 1127 && lastc == '.') { 1128 /* 1129 * Don't print a bare "." line 1130 * since that will confuse ed(1). 1131 * Print ".." instead and return, 1132 * giving the caller an offset 1133 * from which to restart. 1134 */ 1135 puts("."); 1136 return (i - a + 1); 1137 } 1138 putchar(c); 1139 col++; 1140 } 1141 } 1142 } 1143 return (0); 1144 } 1145 1146 /* 1147 * Hash function taken from Robert Sedgewick, Algorithms in C, 3d ed., p 578. 1148 */ 1149 static int 1150 readhash(FILE *f) 1151 { 1152 int i, t, space; 1153 int sum; 1154 1155 sum = 1; 1156 space = 0; 1157 if (!bflag && !wflag) { 1158 if (iflag) 1159 for (i = 0; (t = getc(f)) != '\n'; i++) { 1160 if (t == EOF) { 1161 if (i == 0) 1162 return (0); 1163 break; 1164 } 1165 sum = sum * 127 + chrtran[t]; 1166 } 1167 else 1168 for (i = 0; (t = getc(f)) != '\n'; i++) { 1169 if (t == EOF) { 1170 if (i == 0) 1171 return (0); 1172 break; 1173 } 1174 sum = sum * 127 + t; 1175 } 1176 } else { 1177 for (i = 0;;) { 1178 switch (t = getc(f)) { 1179 case '\t': 1180 case ' ': 1181 space++; 1182 continue; 1183 default: 1184 if (space && !wflag) { 1185 i++; 1186 space = 0; 1187 } 1188 sum = sum * 127 + chrtran[t]; 1189 i++; 1190 continue; 1191 case EOF: 1192 if (i == 0) 1193 return (0); 1194 /* FALLTHROUGH */ 1195 case '\n': 1196 break; 1197 } 1198 break; 1199 } 1200 } 1201 /* 1202 * There is a remote possibility that we end up with a zero sum. 1203 * Zero is used as an EOF marker, so return 1 instead. 1204 */ 1205 return (sum == 0 ? 1 : sum); 1206 } 1207 1208 int 1209 asciifile(FILE *f) 1210 { 1211 char buf[BUFSIZ], *cp; 1212 int i, cnt; 1213 1214 if (aflag || f == NULL) 1215 return (1); 1216 1217 rewind(f); 1218 cnt = fread(buf, 1, sizeof(buf), f); 1219 cp = buf; 1220 for (i = 0; i < cnt; i++) 1221 if (!isprint(*cp) && !isspace(*cp)) 1222 return (0); 1223 return (1); 1224 } 1225 1226 static __inline int min(int a, int b) 1227 { 1228 return (a < b ? a : b); 1229 } 1230 1231 static __inline int max(int a, int b) 1232 { 1233 return (a > b ? a : b); 1234 } 1235 1236 /* dump accumulated "context" diff changes */ 1237 static void 1238 dump_context_vec(FILE *f1, FILE *f2) 1239 { 1240 struct context_vec *cvp = context_vec_start; 1241 int lowa, upb, lowc, upd, do_output; 1242 int a, b, c, d; 1243 char ch; 1244 1245 if (context_vec_start > context_vec_ptr) 1246 return; 1247 1248 b = d = 0; /* gcc */ 1249 lowa = max(1, cvp->a - context); 1250 upb = min(len[0], context_vec_ptr->b + context); 1251 lowc = max(1, cvp->c - context); 1252 upd = min(len[1], context_vec_ptr->d + context); 1253 1254 printf("***************\n*** "); 1255 range(lowa, upb, ","); 1256 printf(" ****\n"); 1257 1258 /* 1259 * Output changes to the "old" file. The first loop suppresses 1260 * output if there were no changes to the "old" file (we'll see 1261 * the "old" lines as context in the "new" list). 1262 */ 1263 do_output = 0; 1264 for (; cvp <= context_vec_ptr; cvp++) 1265 if (cvp->a <= cvp->b) { 1266 cvp = context_vec_start; 1267 do_output++; 1268 break; 1269 } 1270 if (do_output) { 1271 while (cvp <= context_vec_ptr) { 1272 a = cvp->a; 1273 b = cvp->b; 1274 c = cvp->c; 1275 d = cvp->d; 1276 1277 if (a <= b && c <= d) 1278 ch = 'c'; 1279 else 1280 ch = (a <= b) ? 'd' : 'a'; 1281 1282 if (ch == 'a') 1283 fetch(ixold, lowa, b, f1, ' ', 0); 1284 else { 1285 fetch(ixold, lowa, a - 1, f1, ' ', 0); 1286 fetch(ixold, a, b, f1, 1287 ch == 'c' ? '!' : '-', 0); 1288 } 1289 lowa = b + 1; 1290 cvp++; 1291 } 1292 fetch(ixold, b + 1, upb, f1, ' ', 0); 1293 } 1294 /* output changes to the "new" file */ 1295 printf("--- "); 1296 range(lowc, upd, ","); 1297 printf(" ----\n"); 1298 1299 do_output = 0; 1300 for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++) 1301 if (cvp->c <= cvp->d) { 1302 cvp = context_vec_start; 1303 do_output++; 1304 break; 1305 } 1306 if (do_output) { 1307 while (cvp <= context_vec_ptr) { 1308 a = cvp->a; 1309 b = cvp->b; 1310 c = cvp->c; 1311 d = cvp->d; 1312 1313 if (a <= b && c <= d) 1314 ch = 'c'; 1315 else 1316 ch = (a <= b) ? 'd' : 'a'; 1317 1318 if (ch == 'd') 1319 fetch(ixnew, lowc, d, f2, ' ', 0); 1320 else { 1321 fetch(ixnew, lowc, c - 1, f2, ' ', 0); 1322 fetch(ixnew, c, d, f2, 1323 ch == 'c' ? '!' : '+', 0); 1324 } 1325 lowc = d + 1; 1326 cvp++; 1327 } 1328 fetch(ixnew, d + 1, upd, f2, ' ', 0); 1329 } 1330 context_vec_ptr = context_vec_start - 1; 1331 } 1332 1333 /* dump accumulated "unified" diff changes */ 1334 static void 1335 dump_unified_vec(FILE *f1, FILE *f2) 1336 { 1337 struct context_vec *cvp = context_vec_start; 1338 int lowa, upb, lowc, upd; 1339 int a, b, c, d; 1340 char ch; 1341 1342 if (context_vec_start > context_vec_ptr) 1343 return; 1344 1345 b = d = 0; /* gcc */ 1346 lowa = max(1, cvp->a - context); 1347 upb = min(len[0], context_vec_ptr->b + context); 1348 lowc = max(1, cvp->c - context); 1349 upd = min(len[1], context_vec_ptr->d + context); 1350 1351 fputs("@@ -", stdout); 1352 uni_range(lowa, upb); 1353 fputs(" +", stdout); 1354 uni_range(lowc, upd); 1355 fputs(" @@\n", stdout); 1356 1357 /* 1358 * Output changes in "unified" diff format--the old and new lines 1359 * are printed together. 1360 */ 1361 for (; cvp <= context_vec_ptr; cvp++) { 1362 a = cvp->a; 1363 b = cvp->b; 1364 c = cvp->c; 1365 d = cvp->d; 1366 1367 /* 1368 * c: both new and old changes 1369 * d: only changes in the old file 1370 * a: only changes in the new file 1371 */ 1372 if (a <= b && c <= d) 1373 ch = 'c'; 1374 else 1375 ch = (a <= b) ? 'd' : 'a'; 1376 1377 switch (ch) { 1378 case 'c': 1379 fetch(ixold, lowa, a - 1, f1, ' ', 0); 1380 fetch(ixold, a, b, f1, '-', 0); 1381 fetch(ixnew, c, d, f2, '+', 0); 1382 break; 1383 case 'd': 1384 fetch(ixold, lowa, a - 1, f1, ' ', 0); 1385 fetch(ixold, a, b, f1, '-', 0); 1386 break; 1387 case 'a': 1388 fetch(ixnew, lowc, c - 1, f2, ' ', 0); 1389 fetch(ixnew, c, d, f2, '+', 0); 1390 break; 1391 } 1392 lowa = b + 1; 1393 lowc = d + 1; 1394 } 1395 fetch(ixnew, d + 1, upd, f2, ' ', 0); 1396 1397 context_vec_ptr = context_vec_start - 1; 1398 } 1399