1 /* $OpenBSD: diffreg.c,v 1.49 2003/08/13 20:44:15 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.49 2003/08/13 20:44:15 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 puts("\n\\ No newline at end of file"); 1123 return (0);; 1124 } 1125 if (c == '\t' && tflag) { 1126 do { 1127 putchar(' '); 1128 } while (++col & 7); 1129 } else { 1130 if (format == D_EDIT && j == 1 && c == '\n' 1131 && lastc == '.') { 1132 /* 1133 * Don't print a bare "." line 1134 * since that will confuse ed(1). 1135 * Print ".." instead and return, 1136 * giving the caller an offset 1137 * from which to restart. 1138 */ 1139 puts("."); 1140 return (i - a + 1); 1141 } 1142 putchar(c); 1143 col++; 1144 } 1145 } 1146 } 1147 return (0); 1148 } 1149 1150 /* 1151 * Hash function taken from Robert Sedgewick, Algorithms in C, 3d ed., p 578. 1152 */ 1153 static int 1154 readhash(FILE *f) 1155 { 1156 int i, t, space; 1157 int sum; 1158 1159 sum = 1; 1160 space = 0; 1161 if (!bflag && !wflag) { 1162 if (iflag) 1163 for (i = 0; (t = getc(f)) != '\n'; i++) { 1164 if (t == EOF) { 1165 if (i == 0) 1166 return (0); 1167 break; 1168 } 1169 sum = sum * 127 + chrtran[t]; 1170 } 1171 else 1172 for (i = 0; (t = getc(f)) != '\n'; i++) { 1173 if (t == EOF) { 1174 if (i == 0) 1175 return (0); 1176 break; 1177 } 1178 sum = sum * 127 + t; 1179 } 1180 } else { 1181 for (i = 0;;) { 1182 switch (t = getc(f)) { 1183 case '\t': 1184 case ' ': 1185 space++; 1186 continue; 1187 default: 1188 if (space && !wflag) { 1189 i++; 1190 space = 0; 1191 } 1192 sum = sum * 127 + chrtran[t]; 1193 i++; 1194 continue; 1195 case EOF: 1196 if (i == 0) 1197 return (0); 1198 /* FALLTHROUGH */ 1199 case '\n': 1200 break; 1201 } 1202 break; 1203 } 1204 } 1205 /* 1206 * There is a remote possibility that we end up with a zero sum. 1207 * Zero is used as an EOF marker, so return 1 instead. 1208 */ 1209 return (sum == 0 ? 1 : sum); 1210 } 1211 1212 int 1213 asciifile(FILE *f) 1214 { 1215 char buf[BUFSIZ], *cp; 1216 int i, cnt; 1217 1218 if (aflag || f == NULL) 1219 return (1); 1220 1221 rewind(f); 1222 cnt = fread(buf, 1, sizeof(buf), f); 1223 cp = buf; 1224 for (i = 0; i < cnt; i++) 1225 if (!isprint(*cp) && !isspace(*cp)) 1226 return (0); 1227 return (1); 1228 } 1229 1230 static __inline int min(int a, int b) 1231 { 1232 return (a < b ? a : b); 1233 } 1234 1235 static __inline int max(int a, int b) 1236 { 1237 return (a > b ? a : b); 1238 } 1239 1240 /* dump accumulated "context" diff changes */ 1241 static void 1242 dump_context_vec(FILE *f1, FILE *f2) 1243 { 1244 struct context_vec *cvp = context_vec_start; 1245 int lowa, upb, lowc, upd, do_output; 1246 int a, b, c, d; 1247 char ch; 1248 1249 if (context_vec_start > context_vec_ptr) 1250 return; 1251 1252 b = d = 0; /* gcc */ 1253 lowa = max(1, cvp->a - context); 1254 upb = min(len[0], context_vec_ptr->b + context); 1255 lowc = max(1, cvp->c - context); 1256 upd = min(len[1], context_vec_ptr->d + context); 1257 1258 printf("***************\n*** "); 1259 range(lowa, upb, ","); 1260 printf(" ****\n"); 1261 1262 /* 1263 * Output changes to the "old" file. The first loop suppresses 1264 * output if there were no changes to the "old" file (we'll see 1265 * the "old" lines as context in the "new" list). 1266 */ 1267 do_output = 0; 1268 for (; cvp <= context_vec_ptr; cvp++) 1269 if (cvp->a <= cvp->b) { 1270 cvp = context_vec_start; 1271 do_output++; 1272 break; 1273 } 1274 if (do_output) { 1275 while (cvp <= context_vec_ptr) { 1276 a = cvp->a; 1277 b = cvp->b; 1278 c = cvp->c; 1279 d = cvp->d; 1280 1281 if (a <= b && c <= d) 1282 ch = 'c'; 1283 else 1284 ch = (a <= b) ? 'd' : 'a'; 1285 1286 if (ch == 'a') 1287 fetch(ixold, lowa, b, f1, ' ', 0); 1288 else { 1289 fetch(ixold, lowa, a - 1, f1, ' ', 0); 1290 fetch(ixold, a, b, f1, 1291 ch == 'c' ? '!' : '-', 0); 1292 } 1293 lowa = b + 1; 1294 cvp++; 1295 } 1296 fetch(ixold, b + 1, upb, f1, ' ', 0); 1297 } 1298 /* output changes to the "new" file */ 1299 printf("--- "); 1300 range(lowc, upd, ","); 1301 printf(" ----\n"); 1302 1303 do_output = 0; 1304 for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++) 1305 if (cvp->c <= cvp->d) { 1306 cvp = context_vec_start; 1307 do_output++; 1308 break; 1309 } 1310 if (do_output) { 1311 while (cvp <= context_vec_ptr) { 1312 a = cvp->a; 1313 b = cvp->b; 1314 c = cvp->c; 1315 d = cvp->d; 1316 1317 if (a <= b && c <= d) 1318 ch = 'c'; 1319 else 1320 ch = (a <= b) ? 'd' : 'a'; 1321 1322 if (ch == 'd') 1323 fetch(ixnew, lowc, d, f2, ' ', 0); 1324 else { 1325 fetch(ixnew, lowc, c - 1, f2, ' ', 0); 1326 fetch(ixnew, c, d, f2, 1327 ch == 'c' ? '!' : '+', 0); 1328 } 1329 lowc = d + 1; 1330 cvp++; 1331 } 1332 fetch(ixnew, d + 1, upd, f2, ' ', 0); 1333 } 1334 context_vec_ptr = context_vec_start - 1; 1335 } 1336 1337 /* dump accumulated "unified" diff changes */ 1338 static void 1339 dump_unified_vec(FILE *f1, FILE *f2) 1340 { 1341 struct context_vec *cvp = context_vec_start; 1342 int lowa, upb, lowc, upd; 1343 int a, b, c, d; 1344 char ch; 1345 1346 if (context_vec_start > context_vec_ptr) 1347 return; 1348 1349 b = d = 0; /* gcc */ 1350 lowa = max(1, cvp->a - context); 1351 upb = min(len[0], context_vec_ptr->b + context); 1352 lowc = max(1, cvp->c - context); 1353 upd = min(len[1], context_vec_ptr->d + context); 1354 1355 fputs("@@ -", stdout); 1356 uni_range(lowa, upb); 1357 fputs(" +", stdout); 1358 uni_range(lowc, upd); 1359 fputs(" @@\n", stdout); 1360 1361 /* 1362 * Output changes in "unified" diff format--the old and new lines 1363 * are printed together. 1364 */ 1365 for (; cvp <= context_vec_ptr; cvp++) { 1366 a = cvp->a; 1367 b = cvp->b; 1368 c = cvp->c; 1369 d = cvp->d; 1370 1371 /* 1372 * c: both new and old changes 1373 * d: only changes in the old file 1374 * a: only changes in the new file 1375 */ 1376 if (a <= b && c <= d) 1377 ch = 'c'; 1378 else 1379 ch = (a <= b) ? 'd' : 'a'; 1380 1381 switch (ch) { 1382 case 'c': 1383 fetch(ixold, lowa, a - 1, f1, ' ', 0); 1384 fetch(ixold, a, b, f1, '-', 0); 1385 fetch(ixnew, c, d, f2, '+', 0); 1386 break; 1387 case 'd': 1388 fetch(ixold, lowa, a - 1, f1, ' ', 0); 1389 fetch(ixold, a, b, f1, '-', 0); 1390 break; 1391 case 'a': 1392 fetch(ixnew, lowc, c - 1, f2, ' ', 0); 1393 fetch(ixnew, c, d, f2, '+', 0); 1394 break; 1395 } 1396 lowa = b + 1; 1397 lowc = d + 1; 1398 } 1399 fetch(ixnew, d + 1, upd, f2, ' ', 0); 1400 1401 context_vec_ptr = context_vec_start - 1; 1402 } 1403