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