1 /* $OpenBSD: diff.c,v 1.25 2007/09/11 15:47:17 gilles Exp $ */ 2 /* 3 * Copyright (C) Caldera International Inc. 2001-2002. 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code and documentation must retain the above 10 * copyright notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 3. All advertising materials mentioning features or use of this software 15 * must display the following acknowledgement: 16 * This product includes software developed or owned by Caldera 17 * International, Inc. 18 * 4. Neither the name of Caldera International, Inc. nor the names of other 19 * contributors may be used to endorse or promote products derived from 20 * this software without specific prior written permission. 21 * 22 * USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA 23 * INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR 24 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 25 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 26 * IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE FOR ANY DIRECT, 27 * INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 28 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 29 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 31 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 32 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 33 * POSSIBILITY OF SUCH DAMAGE. 34 */ 35 /*- 36 * Copyright (c) 1991, 1993 37 * The Regents of the University of California. All rights reserved. 38 * Copyright (c) 2004 Jean-Francois Brousseau. 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 #include <sys/param.h> 68 #include <sys/stat.h> 69 70 #include <ctype.h> 71 #include <err.h> 72 #include <limits.h> 73 #include <stdarg.h> 74 #include <stddef.h> 75 #include <stdio.h> 76 #include <string.h> 77 #include <unistd.h> 78 79 #include "buf.h" 80 #include "diff.h" 81 #include "xmalloc.h" 82 83 /* 84 * diff - compare two files. 85 */ 86 87 /* 88 * Uses an algorithm due to Harold Stone, which finds 89 * a pair of longest identical subsequences in the two 90 * files. 91 * 92 * The major goal is to generate the match vector J. 93 * J[i] is the index of the line in file1 corresponding 94 * to line i file0. J[i] = 0 if there is no 95 * such line in file1. 96 * 97 * Lines are hashed so as to work in core. All potential 98 * matches are located by sorting the lines of each file 99 * on the hash (called ``value''). In particular, this 100 * collects the equivalence classes in file1 together. 101 * Subroutine equiv replaces the value of each line in 102 * file0 by the index of the first element of its 103 * matching equivalence in (the reordered) file1. 104 * To save space equiv squeezes file1 into a single 105 * array member in which the equivalence classes 106 * are simply concatenated, except that their first 107 * members are flagged by changing sign. 108 * 109 * Next the indices that point into member are unsorted into 110 * array class according to the original order of file0. 111 * 112 * The cleverness lies in routine stone. This marches 113 * through the lines of file0, developing a vector klist 114 * of "k-candidates". At step i a k-candidate is a matched 115 * pair of lines x,y (x in file0 y in file1) such that 116 * there is a common subsequence of length k 117 * between the first i lines of file0 and the first y 118 * lines of file1, but there is no such subsequence for 119 * any smaller y. x is the earliest possible mate to y 120 * that occurs in such a subsequence. 121 * 122 * Whenever any of the members of the equivalence class of 123 * lines in file1 matable to a line in file0 has serial number 124 * less than the y of some k-candidate, that k-candidate 125 * with the smallest such y is replaced. The new 126 * k-candidate is chained (via pred) to the current 127 * k-1 candidate so that the actual subsequence can 128 * be recovered. When a member has serial number greater 129 * that the y of all k-candidates, the klist is extended. 130 * At the end, the longest subsequence is pulled out 131 * and placed in the array J by unravel 132 * 133 * With J in hand, the matches there recorded are 134 * check'ed against reality to assure that no spurious 135 * matches have crept in due to hashing. If they have, 136 * they are broken, and "jackpot" is recorded--a harmless 137 * matter except that a true match for a spuriously 138 * mated line may now be unnecessarily reported as a change. 139 * 140 * Much of the complexity of the program comes simply 141 * from trying to minimize core utilization and 142 * maximize the range of doable problems by dynamically 143 * allocating what is needed and reusing what is not. 144 * The core requirements for problems larger than somewhat 145 * are (in words) 2*length(file0) + length(file1) + 146 * 3*(number of k-candidates installed), typically about 147 * 6n words for files of length n. 148 */ 149 150 struct cand { 151 int x; 152 int y; 153 int pred; 154 }; 155 156 struct line { 157 int serial; 158 int value; 159 } *file[2]; 160 161 /* 162 * The following struct is used to record change information when 163 * doing a "context" or "unified" diff. (see routine "change" to 164 * understand the highly mnemonic field names) 165 */ 166 struct context_vec { 167 int a; /* start line in old file */ 168 int b; /* end line in old file */ 169 int c; /* start line in new file */ 170 int d; /* end line in new file */ 171 }; 172 173 static void output(FILE *, FILE *, int); 174 static void check(FILE *, FILE *, int); 175 static void range(int, int, char *); 176 static void uni_range(int, int); 177 static void dump_context_vec(FILE *, FILE *, int); 178 static void dump_unified_vec(FILE *, FILE *, int); 179 static void prepare(int, FILE *, off_t, int); 180 static void prune(void); 181 static void equiv(struct line *, int, struct line *, int, int *); 182 static void unravel(int); 183 static void unsort(struct line *, int, int *); 184 static void change(FILE *, FILE *, int, int, int, int, int); 185 static void sort(struct line *, int); 186 static int ignoreline(char *); 187 static int asciifile(FILE *); 188 static void fetch(long *, int, int, FILE *, int, int, int); 189 static int newcand(int, int, int); 190 static int search(int *, int, int); 191 static int skipline(FILE *); 192 static int isqrt(int); 193 static int stone(int *, int, int *, int *, int); 194 static int readhash(FILE *, int); 195 static int files_differ(FILE *, FILE *); 196 static char *match_function(const long *, int, FILE *); 197 static char *preadline(int, size_t, off_t); 198 199 200 int diff_context = 3; 201 int diff_format = D_NORMAL; 202 char *diff_file = NULL; 203 RCSNUM *diff_rev1 = NULL; 204 RCSNUM *diff_rev2 = NULL; 205 char diffargs[512]; /* XXX */ 206 static struct stat stb1, stb2; 207 static char *ifdefname; 208 regex_t *diff_ignore_re; 209 210 static int *J; /* will be overlaid on class */ 211 static int *class; /* will be overlaid on file[0] */ 212 static int *klist; /* will be overlaid on file[0] after class */ 213 static int *member; /* will be overlaid on file[1] */ 214 static int clen; 215 static int inifdef; /* whether or not we are in a #ifdef block */ 216 static int len[2]; 217 static int pref, suff; /* length of prefix and suffix */ 218 static int slen[2]; 219 static int anychange; 220 static long *ixnew; /* will be overlaid on file[1] */ 221 static long *ixold; /* will be overlaid on klist */ 222 static struct cand *clist; /* merely a free storage pot for candidates */ 223 static int clistlen; /* the length of clist */ 224 static struct line *sfile[2]; /* shortened by pruning common prefix/suffix */ 225 static u_char *chrtran; /* translation table for case-folding */ 226 static struct context_vec *context_vec_start; 227 static struct context_vec *context_vec_end; 228 static struct context_vec *context_vec_ptr; 229 230 #define FUNCTION_CONTEXT_SIZE 55 231 static char lastbuf[FUNCTION_CONTEXT_SIZE]; 232 static int lastline; 233 static int lastmatchline; 234 BUF *diffbuf = NULL; 235 236 237 /* 238 * chrtran points to one of 2 translation tables: cup2low if folding upper to 239 * lower case clow2low if not folding case 240 */ 241 u_char clow2low[256] = { 242 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 243 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 244 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20, 245 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 246 0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 247 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x40, 0x41, 248 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c, 249 0x4d, 0x4e, 0x4f, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 250 0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, 0x60, 0x61, 0x62, 251 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 252 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 253 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83, 254 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 255 0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 256 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 257 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 258 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 259 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 260 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0, 261 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb, 262 0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 263 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1, 264 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 265 0xfd, 0xfe, 0xff 266 }; 267 268 u_char cup2low[256] = { 269 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 270 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 271 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20, 272 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 273 0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 274 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x60, 0x61, 275 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 276 0x6d, 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 277 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x60, 0x61, 0x62, 278 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 279 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 280 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83, 281 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 282 0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 283 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 284 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 285 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 286 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 287 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0, 288 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb, 289 0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 290 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1, 291 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 292 0xfd, 0xfe, 0xff 293 }; 294 295 int 296 diffreg(const char *file1, const char *file2, BUF *out, int flags) 297 { 298 FILE *f1, *f2; 299 int i, rval; 300 301 f1 = f2 = NULL; 302 rval = D_SAME; 303 anychange = 0; 304 lastline = 0; 305 lastmatchline = 0; 306 context_vec_ptr = context_vec_start - 1; 307 if (flags & D_IGNORECASE) 308 chrtran = cup2low; 309 else 310 chrtran = clow2low; 311 if (out != NULL) 312 diffbuf = out; 313 314 f1 = fopen(file1, "r"); 315 if (f1 == NULL) { 316 warn("%s", file1); 317 goto closem; 318 } 319 320 f2 = fopen(file2, "r"); 321 if (f2 == NULL) { 322 warn("%s", file2); 323 goto closem; 324 } 325 326 if (fstat(fileno(f1), &stb1) < 0) { 327 warn("%s", file1); 328 goto closem; 329 } 330 331 if (fstat(fileno(f2), &stb2) < 0) { 332 warn("%s", file2); 333 goto closem; 334 } 335 336 switch (files_differ(f1, f2)) { 337 case 1: 338 break; 339 case -1: 340 rval = D_ERROR; 341 /* FALLTHROUGH */ 342 case 0: 343 goto closem; 344 default: 345 errx(D_ERROR, "files_differ: invalid case"); 346 } 347 348 if ((flags & D_FORCEASCII) == 0 && 349 (!asciifile(f1) || !asciifile(f2))) { 350 rval = D_ERROR; 351 goto closem; 352 } 353 354 prepare(0, f1, stb1.st_size, flags); 355 prepare(1, f2, stb2.st_size, flags); 356 357 prune(); 358 sort(sfile[0], slen[0]); 359 sort(sfile[1], slen[1]); 360 361 member = (int *)file[1]; 362 equiv(sfile[0], slen[0], sfile[1], slen[1], member); 363 member = xrealloc(member, slen[1] + 2, sizeof(*member)); 364 365 class = (int *)file[0]; 366 unsort(sfile[0], slen[0], class); 367 class = xrealloc(class, slen[0] + 2, sizeof(*class)); 368 369 klist = xcalloc(slen[0] + 2, sizeof(*klist)); 370 clen = 0; 371 clistlen = 100; 372 clist = xcalloc(clistlen, sizeof(*clist)); 373 i = stone(class, slen[0], member, klist, flags); 374 xfree(member); 375 xfree(class); 376 377 J = xrealloc(J, len[0] + 2, sizeof(*J)); 378 unravel(klist[i]); 379 xfree(clist); 380 xfree(klist); 381 382 ixold = xrealloc(ixold, len[0] + 2, sizeof(*ixold)); 383 ixnew = xrealloc(ixnew, len[1] + 2, sizeof(*ixnew)); 384 check(f1, f2, flags); 385 output(f1, f2, flags); 386 387 closem: 388 if (anychange) { 389 if (rval == D_SAME) 390 rval = D_DIFFER; 391 } 392 if (f1 != NULL) 393 fclose(f1); 394 if (f2 != NULL) 395 fclose(f2); 396 397 return (rval); 398 } 399 400 /* 401 * Check to see if the given files differ. 402 * Returns 0 if they are the same, 1 if different, and -1 on error. 403 * XXX - could use code from cmp(1) [faster] 404 */ 405 static int 406 files_differ(FILE *f1, FILE *f2) 407 { 408 char buf1[BUFSIZ], buf2[BUFSIZ]; 409 size_t i, j; 410 411 if (stb1.st_size != stb2.st_size) 412 return (1); 413 for (;;) { 414 i = fread(buf1, 1, sizeof(buf1), f1); 415 j = fread(buf2, 1, sizeof(buf2), f2); 416 if (i != j) 417 return (1); 418 if (i == 0 && j == 0) { 419 if (ferror(f1) || ferror(f2)) 420 return (-1); 421 return (0); 422 } 423 if (memcmp(buf1, buf2, i) != 0) 424 return (1); 425 } 426 } 427 428 static void 429 prepare(int i, FILE *fd, off_t filesize, int flags) 430 { 431 struct line *p; 432 int j, h; 433 size_t sz; 434 435 rewind(fd); 436 437 sz = (filesize <= SIZE_MAX ? filesize : SIZE_MAX) / 25; 438 if (sz < 100) 439 sz = 100; 440 441 p = xcalloc(sz + 3, sizeof(*p)); 442 for (j = 0; (h = readhash(fd, flags));) { 443 if (j == sz) { 444 sz = sz * 3 / 2; 445 p = xrealloc(p, sz + 3, sizeof(*p)); 446 } 447 p[++j].value = h; 448 } 449 len[i] = j; 450 file[i] = p; 451 } 452 453 static void 454 prune(void) 455 { 456 int i, j; 457 458 for (pref = 0; pref < len[0] && pref < len[1] && 459 file[0][pref + 1].value == file[1][pref + 1].value; 460 pref++) 461 ; 462 for (suff = 0; suff < len[0] - pref && suff < len[1] - pref && 463 file[0][len[0] - suff].value == file[1][len[1] - suff].value; 464 suff++) 465 ; 466 for (j = 0; j < 2; j++) { 467 sfile[j] = file[j] + pref; 468 slen[j] = len[j] - pref - suff; 469 for (i = 0; i <= slen[j]; i++) 470 sfile[j][i].serial = i; 471 } 472 } 473 474 static void 475 equiv(struct line *a, int n, struct line *b, int m, int *c) 476 { 477 int i, j; 478 479 i = j = 1; 480 while (i <= n && j <= m) { 481 if (a[i].value < b[j].value) 482 a[i++].value = 0; 483 else if (a[i].value == b[j].value) 484 a[i++].value = j; 485 else 486 j++; 487 } 488 while (i <= n) 489 a[i++].value = 0; 490 b[m + 1].value = 0; 491 j = 0; 492 while (++j <= m) { 493 c[j] = -b[j].serial; 494 while (b[j + 1].value == b[j].value) { 495 j++; 496 c[j] = b[j].serial; 497 } 498 } 499 c[j] = -1; 500 } 501 502 /* Code taken from ping.c */ 503 static int 504 isqrt(int n) 505 { 506 int y, x = 1; 507 508 if (n == 0) 509 return (0); 510 511 do { /* newton was a stinker */ 512 y = x; 513 x = n / x; 514 x += y; 515 x /= 2; 516 } while ((x - y) > 1 || (x - y) < -1); 517 518 return (x); 519 } 520 521 static int 522 stone(int *a, int n, int *b, int *c, int flags) 523 { 524 int i, k, y, j, l; 525 int oldc, tc, oldl; 526 u_int numtries; 527 528 /* XXX move the isqrt() out of the macro to avoid multiple calls */ 529 const u_int bound = (flags & D_MINIMAL) ? UINT_MAX : 530 MAX(256, (u_int)isqrt(n)); 531 532 k = 0; 533 c[0] = newcand(0, 0, 0); 534 for (i = 1; i <= n; i++) { 535 j = a[i]; 536 if (j == 0) 537 continue; 538 y = -b[j]; 539 oldl = 0; 540 oldc = c[0]; 541 numtries = 0; 542 do { 543 if (y <= clist[oldc].y) 544 continue; 545 l = search(c, k, y); 546 if (l != oldl + 1) 547 oldc = c[l - 1]; 548 if (l <= k) { 549 if (clist[c[l]].y <= y) 550 continue; 551 tc = c[l]; 552 c[l] = newcand(i, y, oldc); 553 oldc = tc; 554 oldl = l; 555 numtries++; 556 } else { 557 c[l] = newcand(i, y, oldc); 558 k++; 559 break; 560 } 561 } while ((y = b[++j]) > 0 && numtries < bound); 562 } 563 return (k); 564 } 565 566 static int 567 newcand(int x, int y, int pred) 568 { 569 struct cand *q; 570 571 if (clen == clistlen) { 572 clistlen = clistlen * 11 / 10; 573 clist = xrealloc(clist, clistlen, sizeof(*clist)); 574 } 575 q = clist + clen; 576 q->x = x; 577 q->y = y; 578 q->pred = pred; 579 return (clen++); 580 } 581 582 static int 583 search(int *c, int k, int y) 584 { 585 int i, j, l, t; 586 587 if (clist[c[k]].y < y) /* quick look for typical case */ 588 return (k + 1); 589 i = 0; 590 j = k + 1; 591 for (;;) { 592 l = (i + j) / 2; 593 if (l <= i) 594 break; 595 t = clist[c[l]].y; 596 if (t > y) 597 j = l; 598 else if (t < y) 599 i = l; 600 else 601 return (l); 602 } 603 return (l + 1); 604 } 605 606 static void 607 unravel(int p) 608 { 609 struct cand *q; 610 int i; 611 612 for (i = 0; i <= len[0]; i++) 613 J[i] = i <= pref ? i : 614 i > len[0] - suff ? i + len[1] - len[0] : 0; 615 for (q = clist + p; q->y != 0; q = clist + q->pred) 616 J[q->x + pref] = q->y + pref; 617 } 618 619 /* 620 * Check does double duty: 621 * 1. ferret out any fortuitous correspondences due 622 * to confounding by hashing (which result in "jackpot") 623 * 2. collect random access indexes to the two files 624 */ 625 static void 626 check(FILE *f1, FILE *f2, int flags) 627 { 628 int i, j, jackpot, c, d; 629 long ctold, ctnew; 630 631 rewind(f1); 632 rewind(f2); 633 j = 1; 634 ixold[0] = ixnew[0] = 0; 635 jackpot = 0; 636 ctold = ctnew = 0; 637 for (i = 1; i <= len[0]; i++) { 638 if (J[i] == 0) { 639 ixold[i] = ctold += skipline(f1); 640 continue; 641 } 642 while (j < J[i]) { 643 ixnew[j] = ctnew += skipline(f2); 644 j++; 645 } 646 if (flags & (D_FOLDBLANKS|D_IGNOREBLANKS|D_IGNORECASE)) { 647 for (;;) { 648 c = getc(f1); 649 d = getc(f2); 650 /* 651 * GNU diff ignores a missing newline 652 * in one file for -b or -w. 653 */ 654 if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) && 655 ((c == EOF && d == '\n') || 656 (c == '\n' && d == EOF))) { 657 break; 658 } 659 ctold++; 660 ctnew++; 661 if ((flags & D_FOLDBLANKS) && isspace(c) && 662 isspace(d)) { 663 do { 664 if (c == '\n') 665 break; 666 ctold++; 667 } while (isspace(c = getc(f1))); 668 do { 669 if (d == '\n') 670 break; 671 ctnew++; 672 } while (isspace(d = getc(f2))); 673 } else if ((flags & D_IGNOREBLANKS)) { 674 while (isspace(c) && c != '\n') { 675 c = getc(f1); 676 ctold++; 677 } 678 while (isspace(d) && d != '\n') { 679 d = getc(f2); 680 ctnew++; 681 } 682 } 683 if (chrtran[c] != chrtran[d]) { 684 jackpot++; 685 J[i] = 0; 686 if (c != '\n' && c != EOF) 687 ctold += skipline(f1); 688 if (d != '\n' && c != EOF) 689 ctnew += skipline(f2); 690 break; 691 } 692 if (c == '\n' || c == EOF) 693 break; 694 } 695 } else { 696 for (;;) { 697 ctold++; 698 ctnew++; 699 if ((c = getc(f1)) != (d = getc(f2))) { 700 /* jackpot++; */ 701 J[i] = 0; 702 if (c != '\n' && c != EOF) 703 ctold += skipline(f1); 704 if (d != '\n' && c != EOF) 705 ctnew += skipline(f2); 706 break; 707 } 708 if (c == '\n' || c == EOF) 709 break; 710 } 711 } 712 ixold[i] = ctold; 713 ixnew[j] = ctnew; 714 j++; 715 } 716 for (; j <= len[1]; j++) 717 ixnew[j] = ctnew += skipline(f2); 718 /* 719 * if (jackpot) 720 * fprintf(stderr, "jackpot\n"); 721 */ 722 } 723 724 /* shellsort CACM #201 */ 725 static void 726 sort(struct line *a, int n) 727 { 728 struct line *ai, *aim, w; 729 int j, m = 0, k; 730 731 if (n == 0) 732 return; 733 for (j = 1; j <= n; j *= 2) 734 m = 2 * j - 1; 735 for (m /= 2; m != 0; m /= 2) { 736 k = n - m; 737 for (j = 1; j <= k; j++) { 738 for (ai = &a[j]; ai > a; ai -= m) { 739 aim = &ai[m]; 740 if (aim < ai) 741 break; /* wraparound */ 742 if (aim->value > ai[0].value || 743 (aim->value == ai[0].value && 744 aim->serial > ai[0].serial)) 745 break; 746 w.value = ai[0].value; 747 ai[0].value = aim->value; 748 aim->value = w.value; 749 w.serial = ai[0].serial; 750 ai[0].serial = aim->serial; 751 aim->serial = w.serial; 752 } 753 } 754 } 755 } 756 757 static void 758 unsort(struct line *f, int l, int *b) 759 { 760 int *a, i; 761 762 a = xcalloc(l + 1, sizeof(*a)); 763 for (i = 1; i <= l; i++) 764 a[f[i].serial] = f[i].value; 765 for (i = 1; i <= l; i++) 766 b[i] = a[i]; 767 xfree(a); 768 } 769 770 static int 771 skipline(FILE *f) 772 { 773 int i, c; 774 775 for (i = 1; (c = getc(f)) != '\n' && c != EOF; i++) 776 continue; 777 return (i); 778 } 779 780 static void 781 output(FILE *f1, FILE *f2, int flags) 782 { 783 int m, i0, i1, j0, j1; 784 785 rewind(f1); 786 rewind(f2); 787 m = len[0]; 788 J[0] = 0; 789 J[m + 1] = len[1] + 1; 790 for (i0 = 1; i0 <= m; i0 = i1 + 1) { 791 while (i0 <= m && J[i0] == J[i0 - 1] + 1) 792 i0++; 793 j0 = J[i0 - 1] + 1; 794 i1 = i0 - 1; 795 while (i1 < m && J[i1 + 1] == 0) 796 i1++; 797 j1 = J[i1 + 1] - 1; 798 J[i1] = j1; 799 change(f1, f2, i0, i1, j0, j1, flags); 800 } 801 if (m == 0) 802 change(f1, f2, 1, 0, 1, len[1], flags); 803 if (diff_format == D_IFDEF) { 804 for (;;) { 805 #define c i0 806 if ((c = getc(f1)) == EOF) 807 return; 808 diff_output("%c", c); 809 } 810 #undef c 811 } 812 if (anychange != 0) { 813 if (diff_format == D_CONTEXT) 814 dump_context_vec(f1, f2, flags); 815 else if (diff_format == D_UNIFIED) 816 dump_unified_vec(f1, f2, flags); 817 } 818 } 819 820 static void 821 range(int a, int b, char *separator) 822 { 823 diff_output("%d", a > b ? b : a); 824 if (a < b) 825 diff_output("%s%d", separator, b); 826 } 827 828 static void 829 uni_range(int a, int b) 830 { 831 if (a < b) 832 diff_output("%d,%d", a, b - a + 1); 833 else if (a == b) 834 diff_output("%d", b); 835 else 836 diff_output("%d,0", b); 837 } 838 839 static char * 840 preadline(int fd, size_t rlen, off_t off) 841 { 842 char *line; 843 ssize_t nr; 844 845 line = xmalloc(rlen + 1); 846 if ((nr = pread(fd, line, rlen, off)) < 0) { 847 warn("preadline failed"); 848 xfree(line); 849 return (NULL); 850 } 851 line[nr] = '\0'; 852 return (line); 853 } 854 855 static int 856 ignoreline(char *line) 857 { 858 int ret; 859 860 ret = regexec(diff_ignore_re, line, 0, NULL, 0); 861 xfree(line); 862 return (ret == 0); /* if it matched, it should be ignored. */ 863 } 864 865 /* 866 * Indicate that there is a difference between lines a and b of the from file 867 * to get to lines c to d of the to file. If a is greater then b then there 868 * are no lines in the from file involved and this means that there were 869 * lines appended (beginning at b). If c is greater than d then there are 870 * lines missing from the to file. 871 */ 872 static void 873 change(FILE *f1, FILE *f2, int a, int b, int c, int d, int flags) 874 { 875 static size_t max_context = 64; 876 char buf[64]; 877 struct tm *t; 878 int i; 879 880 if (diff_format != D_IFDEF && a > b && c > d) 881 return; 882 if (diff_ignore_re != NULL) { 883 char *line; 884 /* 885 * All lines in the change, insert, or delete must 886 * match an ignore pattern for the change to be 887 * ignored. 888 */ 889 if (a <= b) { /* Changes and deletes. */ 890 for (i = a; i <= b; i++) { 891 line = preadline(fileno(f1), 892 ixold[i] - ixold[i - 1], ixold[i - 1]); 893 if (!ignoreline(line)) 894 goto proceed; 895 } 896 } 897 if (a > b || c <= d) { /* Changes and inserts. */ 898 for (i = c; i <= d; i++) { 899 line = preadline(fileno(f2), 900 ixnew[i] - ixnew[i - 1], ixnew[i - 1]); 901 if (!ignoreline(line)) 902 goto proceed; 903 } 904 } 905 return; 906 } 907 proceed: 908 if (diff_format == D_CONTEXT || diff_format == D_UNIFIED) { 909 /* 910 * Allocate change records as needed. 911 */ 912 if (context_vec_ptr == context_vec_end - 1) { 913 ptrdiff_t offset = context_vec_ptr - context_vec_start; 914 max_context <<= 1; 915 context_vec_start = xrealloc(context_vec_start, 916 max_context, sizeof(*context_vec_start)); 917 context_vec_end = context_vec_start + max_context; 918 context_vec_ptr = context_vec_start + offset; 919 } 920 if (anychange == 0) { 921 /* 922 * Print the context/unidiff header first time through. 923 */ 924 t = localtime(&stb1.st_mtime); 925 (void)strftime(buf, sizeof(buf), 926 "%Y/%m/%d %H:%M:%S", t); 927 928 diff_output("%s %s %s", 929 diff_format == D_CONTEXT ? "***" : "---", diff_file, 930 buf); 931 932 if (diff_rev1 != NULL) { 933 rcsnum_tostr(diff_rev1, buf, sizeof(buf)); 934 diff_output("\t%s", buf); 935 } 936 937 printf("\n"); 938 939 t = localtime(&stb2.st_mtime); 940 (void)strftime(buf, sizeof(buf), 941 "%Y/%m/%d %H:%M:%S", t); 942 943 diff_output("%s %s %s", 944 diff_format == D_CONTEXT ? "---" : "+++", diff_file, 945 buf); 946 947 if (diff_rev2 != NULL) { 948 rcsnum_tostr(diff_rev2, buf, sizeof(buf)); 949 diff_output("\t%s", buf); 950 } 951 952 printf("\n"); 953 anychange = 1; 954 } else if (a > context_vec_ptr->b + (2 * diff_context) + 1 && 955 c > context_vec_ptr->d + (2 * diff_context) + 1) { 956 /* 957 * If this change is more than 'diff_context' lines from the 958 * previous change, dump the record and reset it. 959 */ 960 if (diff_format == D_CONTEXT) 961 dump_context_vec(f1, f2, flags); 962 else 963 dump_unified_vec(f1, f2, flags); 964 } 965 context_vec_ptr++; 966 context_vec_ptr->a = a; 967 context_vec_ptr->b = b; 968 context_vec_ptr->c = c; 969 context_vec_ptr->d = d; 970 return; 971 } 972 if (anychange == 0) 973 anychange = 1; 974 switch (diff_format) { 975 case D_BRIEF: 976 return; 977 case D_NORMAL: 978 range(a, b, ","); 979 diff_output("%c", a > b ? 'a' : c > d ? 'd' : 'c'); 980 if (diff_format == D_NORMAL) 981 range(c, d, ","); 982 diff_output("\n"); 983 break; 984 case D_RCSDIFF: 985 if (a > b) 986 diff_output("a%d %d\n", b, d - c + 1); 987 else { 988 diff_output("d%d %d\n", a, b - a + 1); 989 990 if (!(c > d)) /* add changed lines */ 991 diff_output("a%d %d\n", b, d - c + 1); 992 } 993 break; 994 } 995 if (diff_format == D_NORMAL || diff_format == D_IFDEF) { 996 fetch(ixold, a, b, f1, '<', 1, flags); 997 if (a <= b && c <= d && diff_format == D_NORMAL) 998 diff_output("---\n"); 999 } 1000 fetch(ixnew, c, d, f2, diff_format == D_NORMAL ? '>' : '\0', 0, flags); 1001 if (inifdef) { 1002 diff_output("#endif /* %s */\n", ifdefname); 1003 inifdef = 0; 1004 } 1005 } 1006 1007 static void 1008 fetch(long *f, int a, int b, FILE *lb, int ch, int oldfile, int flags) 1009 { 1010 long j, nc; 1011 int i, c, col; 1012 1013 /* 1014 * When doing #ifdef's, copy down to current line 1015 * if this is the first file, so that stuff makes it to output. 1016 */ 1017 if (diff_format == D_IFDEF && oldfile) { 1018 long curpos = ftell(lb); 1019 /* print through if append (a>b), else to (nb: 0 vs 1 orig) */ 1020 nc = f[a > b ? b : a - 1] - curpos; 1021 for (i = 0; i < nc; i++) 1022 diff_output("%c", getc(lb)); 1023 } 1024 if (a > b) 1025 return; 1026 if (diff_format == D_IFDEF) { 1027 if (inifdef) { 1028 diff_output("#else /* %s%s */\n", 1029 oldfile == 1 ? "!" : "", ifdefname); 1030 } else { 1031 if (oldfile) 1032 diff_output("#ifndef %s\n", ifdefname); 1033 else 1034 diff_output("#ifdef %s\n", ifdefname); 1035 } 1036 inifdef = 1 + oldfile; 1037 } 1038 for (i = a; i <= b; i++) { 1039 fseek(lb, f[i - 1], SEEK_SET); 1040 nc = f[i] - f[i - 1]; 1041 if (diff_format != D_IFDEF && ch != '\0') { 1042 diff_output("%c", ch); 1043 if (diff_format != D_UNIFIED) 1044 diff_output(" "); 1045 } 1046 col = 0; 1047 for (j = 0; j < nc; j++) { 1048 if ((c = getc(lb)) == EOF) { 1049 if (diff_format == D_RCSDIFF) 1050 warn("No newline at end of file"); 1051 else 1052 diff_output("\n\\ No newline at end of " 1053 "file"); 1054 return; 1055 } 1056 if (c == '\t' && (flags & D_EXPANDTABS)) { 1057 do { 1058 diff_output(" "); 1059 } while (++col & 7); 1060 } else { 1061 diff_output("%c", c); 1062 col++; 1063 } 1064 } 1065 } 1066 } 1067 1068 /* 1069 * Hash function taken from Robert Sedgewick, Algorithms in C, 3d ed., p 578. 1070 */ 1071 static int 1072 readhash(FILE *f, int flags) 1073 { 1074 int i, t, space; 1075 int sum; 1076 1077 sum = 1; 1078 space = 0; 1079 if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) == 0) { 1080 if (flags & D_IGNORECASE) 1081 for (i = 0; (t = getc(f)) != '\n'; i++) { 1082 if (t == EOF) { 1083 if (i == 0) 1084 return (0); 1085 break; 1086 } 1087 sum = sum * 127 + chrtran[t]; 1088 } 1089 else 1090 for (i = 0; (t = getc(f)) != '\n'; i++) { 1091 if (t == EOF) { 1092 if (i == 0) 1093 return (0); 1094 break; 1095 } 1096 sum = sum * 127 + t; 1097 } 1098 } else { 1099 for (i = 0;;) { 1100 switch (t = getc(f)) { 1101 case '\t': 1102 case '\r': 1103 case '\v': 1104 case '\f': 1105 case ' ': 1106 space++; 1107 continue; 1108 default: 1109 if (space && (flags & D_IGNOREBLANKS) == 0) { 1110 i++; 1111 space = 0; 1112 } 1113 sum = sum * 127 + chrtran[t]; 1114 i++; 1115 continue; 1116 case EOF: 1117 if (i == 0) 1118 return (0); 1119 /* FALLTHROUGH */ 1120 case '\n': 1121 break; 1122 } 1123 break; 1124 } 1125 } 1126 /* 1127 * There is a remote possibility that we end up with a zero sum. 1128 * Zero is used as an EOF marker, so return 1 instead. 1129 */ 1130 return (sum == 0 ? 1 : sum); 1131 } 1132 1133 static int 1134 asciifile(FILE *f) 1135 { 1136 unsigned char buf[BUFSIZ]; 1137 size_t i, cnt; 1138 1139 if (f == NULL) 1140 return (1); 1141 1142 rewind(f); 1143 cnt = fread(buf, 1, sizeof(buf), f); 1144 for (i = 0; i < cnt; i++) 1145 if (!isprint(buf[i]) && !isspace(buf[i])) 1146 return (0); 1147 return (1); 1148 } 1149 1150 #define begins_with(s, pre) (strncmp(s, pre, sizeof(pre)-1) == 0) 1151 1152 static char * 1153 match_function(const long *f, int pos, FILE *fp) 1154 { 1155 unsigned char buf[FUNCTION_CONTEXT_SIZE]; 1156 size_t nc; 1157 int last = lastline; 1158 char *state = NULL; 1159 1160 lastline = pos; 1161 while (pos > last) { 1162 fseek(fp, f[pos - 1], SEEK_SET); 1163 nc = f[pos] - f[pos - 1]; 1164 if (nc >= sizeof(buf)) 1165 nc = sizeof(buf) - 1; 1166 nc = fread(buf, 1, nc, fp); 1167 if (nc > 0) { 1168 buf[nc] = '\0'; 1169 1170 buf[strcspn(buf, "\n")] = '\0'; 1171 1172 if (isalpha(buf[0]) || buf[0] == '_' || buf[0] == '$') { 1173 if (begins_with(buf, "private:")) { 1174 if (!state) 1175 state = " (private)"; 1176 } else if (begins_with(buf, "protected:")) { 1177 if (!state) 1178 state = " (protected)"; 1179 } else if (begins_with(buf, "public:")) { 1180 if (!state) 1181 state = " (public)"; 1182 } else { 1183 if (strlcpy(lastbuf, buf, 1184 sizeof(lastbuf)) >= sizeof(lastbuf)) 1185 errx(1, 1186 "match_function: strlcpy"); 1187 lastmatchline = pos; 1188 return lastbuf; 1189 } 1190 } 1191 } 1192 pos--; 1193 } 1194 return lastmatchline > 0 ? lastbuf : NULL; 1195 } 1196 1197 /* dump accumulated "context" diff changes */ 1198 static void 1199 dump_context_vec(FILE *f1, FILE *f2, int flags) 1200 { 1201 struct context_vec *cvp = context_vec_start; 1202 int lowa, upb, lowc, upd, do_output; 1203 int a, b, c, d; 1204 char ch, *f; 1205 1206 if (context_vec_start > context_vec_ptr) 1207 return; 1208 1209 b = d = 0; /* gcc */ 1210 lowa = MAX(1, cvp->a - diff_context); 1211 upb = MIN(len[0], context_vec_ptr->b + diff_context); 1212 lowc = MAX(1, cvp->c - diff_context); 1213 upd = MIN(len[1], context_vec_ptr->d + diff_context); 1214 1215 diff_output("***************"); 1216 if ((flags & D_PROTOTYPE)) { 1217 f = match_function(ixold, lowa-1, f1); 1218 if (f != NULL) { 1219 diff_output(" "); 1220 diff_output("%s", f); 1221 } 1222 } 1223 diff_output("\n*** "); 1224 range(lowa, upb, ","); 1225 diff_output(" ****\n"); 1226 1227 /* 1228 * Output changes to the "old" file. The first loop suppresses 1229 * output if there were no changes to the "old" file (we'll see 1230 * the "old" lines as context in the "new" list). 1231 */ 1232 do_output = 0; 1233 for (; cvp <= context_vec_ptr; cvp++) 1234 if (cvp->a <= cvp->b) { 1235 cvp = context_vec_start; 1236 do_output++; 1237 break; 1238 } 1239 if (do_output) { 1240 while (cvp <= context_vec_ptr) { 1241 a = cvp->a; 1242 b = cvp->b; 1243 c = cvp->c; 1244 d = cvp->d; 1245 1246 if (a <= b && c <= d) 1247 ch = 'c'; 1248 else 1249 ch = (a <= b) ? 'd' : 'a'; 1250 1251 if (ch == 'a') 1252 fetch(ixold, lowa, b, f1, ' ', 0, flags); 1253 else { 1254 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1255 fetch(ixold, a, b, f1, 1256 ch == 'c' ? '!' : '-', 0, flags); 1257 } 1258 lowa = b + 1; 1259 cvp++; 1260 } 1261 fetch(ixold, b + 1, upb, f1, ' ', 0, flags); 1262 } 1263 /* output changes to the "new" file */ 1264 diff_output("--- "); 1265 range(lowc, upd, ","); 1266 diff_output(" ----\n"); 1267 1268 do_output = 0; 1269 for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++) 1270 if (cvp->c <= cvp->d) { 1271 cvp = context_vec_start; 1272 do_output++; 1273 break; 1274 } 1275 if (do_output) { 1276 while (cvp <= context_vec_ptr) { 1277 a = cvp->a; 1278 b = cvp->b; 1279 c = cvp->c; 1280 d = cvp->d; 1281 1282 if (a <= b && c <= d) 1283 ch = 'c'; 1284 else 1285 ch = (a <= b) ? 'd' : 'a'; 1286 1287 if (ch == 'd') 1288 fetch(ixnew, lowc, d, f2, ' ', 0, flags); 1289 else { 1290 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags); 1291 fetch(ixnew, c, d, f2, 1292 ch == 'c' ? '!' : '+', 0, flags); 1293 } 1294 lowc = d + 1; 1295 cvp++; 1296 } 1297 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags); 1298 } 1299 context_vec_ptr = context_vec_start - 1; 1300 } 1301 1302 /* dump accumulated "unified" diff changes */ 1303 static void 1304 dump_unified_vec(FILE *f1, FILE *f2, int flags) 1305 { 1306 struct context_vec *cvp = context_vec_start; 1307 int lowa, upb, lowc, upd; 1308 int a, b, c, d; 1309 char ch, *f; 1310 1311 if (context_vec_start > context_vec_ptr) 1312 return; 1313 1314 b = d = 0; /* gcc */ 1315 lowa = MAX(1, cvp->a - diff_context); 1316 upb = MIN(len[0], context_vec_ptr->b + diff_context); 1317 lowc = MAX(1, cvp->c - diff_context); 1318 upd = MIN(len[1], context_vec_ptr->d + diff_context); 1319 1320 diff_output("@@ -"); 1321 uni_range(lowa, upb); 1322 diff_output(" +"); 1323 uni_range(lowc, upd); 1324 diff_output(" @@"); 1325 if ((flags & D_PROTOTYPE)) { 1326 f = match_function(ixold, lowa-1, f1); 1327 if (f != NULL) { 1328 diff_output(" "); 1329 diff_output("%s", f); 1330 } 1331 } 1332 diff_output("\n"); 1333 1334 /* 1335 * Output changes in "unified" diff format--the old and new lines 1336 * are printed together. 1337 */ 1338 for (; cvp <= context_vec_ptr; cvp++) { 1339 a = cvp->a; 1340 b = cvp->b; 1341 c = cvp->c; 1342 d = cvp->d; 1343 1344 /* 1345 * c: both new and old changes 1346 * d: only changes in the old file 1347 * a: only changes in the new file 1348 */ 1349 if (a <= b && c <= d) 1350 ch = 'c'; 1351 else 1352 ch = (a <= b) ? 'd' : 'a'; 1353 1354 switch (ch) { 1355 case 'c': 1356 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1357 fetch(ixold, a, b, f1, '-', 0, flags); 1358 fetch(ixnew, c, d, f2, '+', 0, flags); 1359 break; 1360 case 'd': 1361 fetch(ixold, lowa, a - 1, f1, ' ', 0, flags); 1362 fetch(ixold, a, b, f1, '-', 0, flags); 1363 break; 1364 case 'a': 1365 fetch(ixnew, lowc, c - 1, f2, ' ', 0, flags); 1366 fetch(ixnew, c, d, f2, '+', 0, flags); 1367 break; 1368 } 1369 lowa = b + 1; 1370 lowc = d + 1; 1371 } 1372 fetch(ixnew, d + 1, upd, f2, ' ', 0, flags); 1373 1374 context_vec_ptr = context_vec_start - 1; 1375 } 1376 1377 void 1378 diff_output(const char *fmt, ...) 1379 { 1380 va_list vap; 1381 int i; 1382 char *str; 1383 1384 va_start(vap, fmt); 1385 i = vasprintf(&str, fmt, vap); 1386 va_end(vap); 1387 if (i == -1) 1388 err(1, "diff_output"); 1389 if (diffbuf != NULL) 1390 rcs_buf_append(diffbuf, str, strlen(str)); 1391 else 1392 printf("%s", str); 1393 xfree(str); 1394 } 1395