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