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