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