1 /* $OpenBSD: diffreg.c,v 1.41 2003/07/22 01:16:01 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.41 2003/07/22 01:16:01 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 struct line *sfile[2]; /* shortened by pruning common prefix/suffix */ 192 static u_char *chrtran; /* translation table for case-folding */ 193 static struct context_vec *context_vec_start; 194 static struct context_vec *context_vec_end; 195 static struct context_vec *context_vec_ptr; 196 197 static FILE *opentemp(const char *); 198 static void output(char *, FILE *, char *, FILE *); 199 static void check(char *, FILE *, char *, FILE *); 200 static void range(int, int, char *); 201 static void uni_range(int, int); 202 static void dump_context_vec(FILE *, FILE *); 203 static void dump_unified_vec(FILE *, FILE *); 204 static void prepare(int, FILE *); 205 static void prune(void); 206 static void equiv(struct line *, int, struct line *, int, int *); 207 static void unravel(int); 208 static void unsort(struct line *, int, int *); 209 static void change(char *, FILE *, char *, FILE *, int, int, int, int); 210 static void sort(struct line *, int); 211 static int asciifile(FILE *); 212 static int fetch(long *, int, int, FILE *, int, int); 213 static int newcand(int, int, int); 214 static int search(int *, int, int); 215 static int skipline(FILE *); 216 static int stone(int *, int, int *, int *); 217 static int readhash(FILE *); 218 static int files_differ(FILE *, FILE *, int); 219 220 /* 221 * chrtran points to one of 2 translation tables: cup2low if folding upper to 222 * lower case clow2low if not folding case 223 */ 224 u_char clow2low[256] = { 225 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 226 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 227 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20, 228 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 229 0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 230 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x40, 0x41, 231 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c, 232 0x4d, 0x4e, 0x4f, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 233 0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, 0x60, 0x61, 0x62, 234 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 235 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 236 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83, 237 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 238 0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 239 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 240 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 241 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 242 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 243 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0, 244 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb, 245 0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 246 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1, 247 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 248 0xfd, 0xfe, 0xff 249 }; 250 251 u_char cup2low[256] = { 252 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 253 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 254 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20, 255 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 256 0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 257 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x60, 0x61, 258 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 259 0x6d, 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 260 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x60, 0x61, 0x62, 261 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 262 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 263 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83, 264 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 265 0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 266 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 267 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 268 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 269 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 270 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0, 271 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb, 272 0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 273 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1, 274 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 275 0xfd, 0xfe, 0xff 276 }; 277 278 int 279 diffreg(char *ofile1, char *ofile2, int flags) 280 { 281 char *file1 = ofile1; 282 char *file2 = ofile2; 283 FILE *f1 = NULL; 284 FILE *f2 = NULL; 285 int rval = D_SAME; 286 int i, ostdout = -1; 287 pid_t pid = -1; 288 289 anychange = 0; 290 context_vec_ptr = context_vec_start - 1; 291 chrtran = (iflag ? cup2low : clow2low); 292 if (S_ISDIR(stb1.st_mode) != S_ISDIR(stb2.st_mode)) 293 return (S_ISDIR(stb1.st_mode) ? D_MISMATCH1 : D_MISMATCH2); 294 if (strcmp(file1, "-") == 0 && strcmp(file2, "-") == 0) 295 goto notsame; 296 297 if (flags & D_EMPTY1) 298 f1 = fopen(_PATH_DEVNULL, "r"); 299 else { 300 if (!S_ISREG(stb1.st_mode)) { 301 if ((f1 = opentemp(file1)) == NULL || 302 fstat(fileno(f1), &stb1) < 0) { 303 warn("%s", file1); 304 status |= 2; 305 goto closem; 306 } 307 } else if (strcmp(file1, "-") == 0) 308 f1 = stdin; 309 else 310 f1 = fopen(file1, "r"); 311 } 312 if (f1 == NULL) { 313 warn("%s", file1); 314 status |= 2; 315 goto closem; 316 } 317 318 if (flags & D_EMPTY2) 319 f2 = fopen(_PATH_DEVNULL, "r"); 320 else { 321 if (!S_ISREG(stb2.st_mode)) { 322 if ((f2 = opentemp(file2)) == NULL || 323 fstat(fileno(f2), &stb2) < 0) { 324 warn("%s", file2); 325 status |= 2; 326 goto closem; 327 } 328 } else if (strcmp(file2, "-") == 0) 329 f2 = stdin; 330 else 331 f2 = fopen(file2, "r"); 332 } 333 if (f2 == NULL) { 334 warn("%s", file2); 335 status |= 2; 336 goto closem; 337 } 338 339 switch (files_differ(f1, f2, flags)) { 340 case 0: 341 goto closem; 342 case 1: 343 break; 344 default: 345 /* error */ 346 status |= 2; 347 goto closem; 348 } 349 350 notsame: 351 /* 352 * Files certainly differ at this point; set status accordingly 353 */ 354 status |= 1; 355 rval = D_DIFFER; 356 if (!asciifile(f1) || !asciifile(f2)) { 357 rval = D_BINARY; 358 goto closem; 359 } 360 if (format == D_BRIEF) 361 goto closem; 362 if (lflag) { 363 /* redirect stdout to pr */ 364 int pfd[2]; 365 char *header; 366 char *prargv[] = { "pr", "-h", NULL, "-f", NULL }; 367 368 easprintf(&header, "%s %s %s", diffargs, file1, file2); 369 prargv[2] = header; 370 fflush(stdout); 371 rewind(stdout); 372 pipe(pfd); 373 switch ((pid = fork())) { 374 case -1: 375 warnx("No more processes"); 376 status |= 2; 377 free(header); 378 return (D_ERROR); 379 case 0: 380 /* child */ 381 if (pfd[0] != STDIN_FILENO) { 382 dup2(pfd[0], STDIN_FILENO); 383 close(pfd[0]); 384 } 385 close(pfd[1]); 386 execv(_PATH_PR, prargv); 387 _exit(127); 388 default: 389 /* parent */ 390 if (pfd[1] != STDOUT_FILENO) { 391 ostdout = dup(STDOUT_FILENO); 392 dup2(pfd[1], STDOUT_FILENO); 393 close(pfd[1]); 394 } 395 close(pfd[0]); 396 rewind(stdout); 397 free(header); 398 } 399 } else if (flags & D_HEADER) 400 printf("%s %s %s\n", diffargs, file1, file2); 401 prepare(0, f1); 402 prepare(1, f2); 403 prune(); 404 sort(sfile[0], slen[0]); 405 sort(sfile[1], slen[1]); 406 407 member = (int *)file[1]; 408 equiv(sfile[0], slen[0], sfile[1], slen[1], member); 409 member = erealloc(member, (slen[1] + 2) * sizeof(int)); 410 411 class = (int *)file[0]; 412 unsort(sfile[0], slen[0], class); 413 class = erealloc(class, (slen[0] + 2) * sizeof(int)); 414 415 klist = emalloc((slen[0] + 2) * sizeof(int)); 416 clist = emalloc(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 (f1 != NULL) 445 fclose(f1); 446 if (f2 != NULL) 447 fclose(f2); 448 if (file1 != ofile1) 449 free(file1); 450 if (file2 != ofile2) 451 free(file2); 452 return (rval); 453 } 454 455 /* 456 * Check to see if the given files differ. 457 * Returns 0 if they are the same, 1 if different, and -1 on error. 458 * XXX - could use code from cmp(1) [faster] 459 */ 460 static int 461 files_differ(FILE *f1, FILE *f2, int flags) 462 { 463 char buf1[BUFSIZ], buf2[BUFSIZ]; 464 size_t i, j; 465 466 if ((flags & (D_EMPTY1|D_EMPTY2)) || stb1.st_size != stb2.st_size || 467 (stb1.st_mode & S_IFMT) != (stb2.st_mode & S_IFMT)) 468 return (1); 469 for (;;) { 470 i = fread(buf1, 1, sizeof(buf1), f1); 471 j = fread(buf2, 1, sizeof(buf2), f2); 472 if (i != j) 473 return (1); 474 if (i == 0 && j == 0) { 475 if (ferror(f1) || ferror(f2)) 476 return (1); 477 return (0); 478 } 479 if (memcmp(buf1, buf2, i) != 0) 480 return (1); 481 } 482 } 483 484 static FILE * 485 opentemp(const char *file) 486 { 487 char buf[BUFSIZ], *tempdir, tempfile[MAXPATHLEN]; 488 ssize_t nread; 489 int ifd, ofd; 490 491 if (strcmp(file, "-") == 0) 492 ifd = STDIN_FILENO; 493 else if ((ifd = open(file, O_RDONLY, 0644)) < 0) 494 return (NULL); 495 496 if ((tempdir = getenv("TMPDIR")) == NULL) 497 tempdir = _PATH_TMP; 498 if (snprintf(tempfile, sizeof(tempfile), "%s/diff.XXXXXXXX", 499 tempdir) >= sizeof(tempfile)) { 500 close(ifd); 501 errno = ENAMETOOLONG; 502 return (NULL); 503 } 504 505 if ((ofd = mkstemp(tempfile)) < 0) 506 return (NULL); 507 unlink(tempfile); 508 while ((nread = read(ifd, buf, BUFSIZ)) > 0) { 509 if (write(ofd, buf, nread) != nread) { 510 close(ifd); 511 close(ofd); 512 return (NULL); 513 } 514 } 515 close(ifd); 516 return (fdopen(ofd, "r")); 517 } 518 519 char * 520 splice(char *dir, char *file) 521 { 522 char *tail, *buf; 523 524 if ((tail = strrchr(file, '/')) == NULL) 525 tail = file; 526 else 527 tail++; 528 easprintf(&buf, "%s/%s", dir, tail); 529 return (buf); 530 } 531 532 static void 533 prepare(int i, FILE *fd) 534 { 535 struct line *p; 536 int j, h; 537 538 rewind(fd); 539 p = emalloc(3 * sizeof(struct line)); 540 for (j = 0; (h = readhash(fd));) { 541 p = erealloc(p, (++j + 3) * sizeof(struct line)); 542 p[j].value = h; 543 } 544 len[i] = j; 545 file[i] = p; 546 } 547 548 static void 549 prune(void) 550 { 551 int i, j; 552 553 for (pref = 0; pref < len[0] && pref < len[1] && 554 file[0][pref + 1].value == file[1][pref + 1].value; 555 pref++) 556 ; 557 for (suff = 0; suff < len[0] - pref && suff < len[1] - pref && 558 file[0][len[0] - suff].value == file[1][len[1] - suff].value; 559 suff++) 560 ; 561 for (j = 0; j < 2; j++) { 562 sfile[j] = file[j] + pref; 563 slen[j] = len[j] - pref - suff; 564 for (i = 0; i <= slen[j]; i++) 565 sfile[j][i].serial = i; 566 } 567 } 568 569 static void 570 equiv(struct line *a, int n, struct line *b, int m, int *c) 571 { 572 int i, j; 573 574 i = j = 1; 575 while (i <= n && j <= m) { 576 if (a[i].value < b[j].value) 577 a[i++].value = 0; 578 else if (a[i].value == b[j].value) 579 a[i++].value = j; 580 else 581 j++; 582 } 583 while (i <= n) 584 a[i++].value = 0; 585 b[m + 1].value = 0; 586 j = 0; 587 while (++j <= m) { 588 c[j] = -b[j].serial; 589 while (b[j + 1].value == b[j].value) { 590 j++; 591 c[j] = b[j].serial; 592 } 593 } 594 c[j] = -1; 595 } 596 597 static int 598 stone(int *a, int n, int *b, int *c) 599 { 600 int i, k, y, j, l; 601 int oldc, tc, oldl; 602 603 k = 0; 604 c[0] = newcand(0, 0, 0); 605 for (i = 1; i <= n; i++) { 606 j = a[i]; 607 if (j == 0) 608 continue; 609 y = -b[j]; 610 oldl = 0; 611 oldc = c[0]; 612 do { 613 if (y <= clist[oldc].y) 614 continue; 615 l = search(c, k, y); 616 if (l != oldl + 1) 617 oldc = c[l - 1]; 618 if (l <= k) { 619 if (clist[c[l]].y <= y) 620 continue; 621 tc = c[l]; 622 c[l] = newcand(i, y, oldc); 623 oldc = tc; 624 oldl = l; 625 } else { 626 c[l] = newcand(i, y, oldc); 627 k++; 628 break; 629 } 630 } while ((y = b[++j]) > 0); 631 } 632 return (k); 633 } 634 635 static int 636 newcand(int x, int y, int pred) 637 { 638 struct cand *q; 639 640 clist = erealloc(clist, ++clen * sizeof(cand)); 641 q = clist + clen - 1; 642 q->x = x; 643 q->y = y; 644 q->pred = pred; 645 return (clen - 1); 646 } 647 648 static int 649 search(int *c, int k, int y) 650 { 651 int i, j, l, t; 652 653 if (clist[c[k]].y < y) /* quick look for typical case */ 654 return (k + 1); 655 i = 0; 656 j = k + 1; 657 while (1) { 658 l = i + j; 659 if ((l >>= 1) <= i) 660 break; 661 t = clist[c[l]].y; 662 if (t > y) 663 j = l; 664 else if (t < y) 665 i = l; 666 else 667 return (l); 668 } 669 return (l + 1); 670 } 671 672 static void 673 unravel(int p) 674 { 675 struct cand *q; 676 int i; 677 678 for (i = 0; i <= len[0]; i++) 679 J[i] = i <= pref ? i : 680 i > len[0] - suff ? i + len[1] - len[0] : 0; 681 for (q = clist + p; q->y != 0; q = clist + q->pred) 682 J[q->x + pref] = q->y + pref; 683 } 684 685 /* 686 * Check does double duty: 687 * 1. ferret out any fortuitous correspondences due 688 * to confounding by hashing (which result in "jackpot") 689 * 2. collect random access indexes to the two files 690 */ 691 static void 692 check(char *file1, FILE *f1, char *file2, FILE *f2) 693 { 694 int i, j, jackpot, c, d; 695 long ctold, ctnew; 696 697 rewind(f1); 698 rewind(f2); 699 j = 1; 700 ixold[0] = ixnew[0] = 0; 701 jackpot = 0; 702 ctold = ctnew = 0; 703 for (i = 1; i <= len[0]; i++) { 704 if (J[i] == 0) { 705 ixold[i] = ctold += skipline(f1); 706 continue; 707 } 708 while (j < J[i]) { 709 ixnew[j] = ctnew += skipline(f2); 710 j++; 711 } 712 if (bflag || wflag || iflag) { 713 for (;;) { 714 c = getc(f1); 715 d = getc(f2); 716 /* 717 * GNU diff ignores a missing newline 718 * in one file if bflag || wflag. 719 */ 720 if ((bflag || wflag) && 721 ((c == EOF && d == '\n') || 722 (c == '\n' && d == EOF))) { 723 break; 724 } 725 ctold++; 726 ctnew++; 727 if (bflag && isspace(c) && isspace(d)) { 728 do { 729 if (c == '\n') 730 break; 731 ctold++; 732 } while (isspace(c = getc(f1))); 733 do { 734 if (d == '\n') 735 break; 736 ctnew++; 737 } while (isspace(d = getc(f2))); 738 } else if (wflag) { 739 while (isspace(c) && c != '\n') { 740 c = getc(f1); 741 ctold++; 742 } 743 while (isspace(d) && d != '\n') { 744 d = getc(f2); 745 ctnew++; 746 } 747 } 748 if (chrtran[c] != chrtran[d]) { 749 jackpot++; 750 J[i] = 0; 751 if (c != '\n' && c != EOF) 752 ctold += skipline(f1); 753 if (d != '\n' && c != EOF) 754 ctnew += skipline(f2); 755 break; 756 } 757 if (c == '\n' || c == EOF) 758 break; 759 } 760 } else { 761 for (;;) { 762 ctold++; 763 ctnew++; 764 if ((c = getc(f1)) != (d = getc(f2))) { 765 /* jackpot++; */ 766 J[i] = 0; 767 if (c != '\n' && c != EOF) 768 ctold += skipline(f1); 769 if (d != '\n' && c != EOF) 770 ctnew += skipline(f2); 771 break; 772 } 773 if (c == '\n' || c == EOF) 774 break; 775 } 776 } 777 ixold[i] = ctold; 778 ixnew[j] = ctnew; 779 j++; 780 } 781 for (; j <= len[1]; j++) 782 ixnew[j] = ctnew += skipline(f2); 783 /* 784 * if (jackpot) 785 * fprintf(stderr, "jackpot\n"); 786 */ 787 } 788 789 /* shellsort CACM #201 */ 790 static void 791 sort(struct line *a, int n) 792 { 793 struct line *ai, *aim, w; 794 int j, m = 0, k; 795 796 if (n == 0) 797 return; 798 for (j = 1; j <= n; j *= 2) 799 m = 2 * j - 1; 800 for (m /= 2; m != 0; m /= 2) { 801 k = n - m; 802 for (j = 1; j <= k; j++) { 803 for (ai = &a[j]; ai > a; ai -= m) { 804 aim = &ai[m]; 805 if (aim < ai) 806 break; /* wraparound */ 807 if (aim->value > ai[0].value || 808 (aim->value == ai[0].value && 809 aim->serial > ai[0].serial)) 810 break; 811 w.value = ai[0].value; 812 ai[0].value = aim->value; 813 aim->value = w.value; 814 w.serial = ai[0].serial; 815 ai[0].serial = aim->serial; 816 aim->serial = w.serial; 817 } 818 } 819 } 820 } 821 822 static void 823 unsort(struct line *f, int l, int *b) 824 { 825 int *a, i; 826 827 a = emalloc((l + 1) * sizeof(int)); 828 for (i = 1; i <= l; i++) 829 a[f[i].serial] = f[i].value; 830 for (i = 1; i <= l; i++) 831 b[i] = a[i]; 832 free(a); 833 } 834 835 static int 836 skipline(FILE *f) 837 { 838 int i, c; 839 840 for (i = 1; (c = getc(f)) != '\n' && c != EOF; i++) 841 continue; 842 return (i); 843 } 844 845 static void 846 output(char *file1, FILE *f1, char *file2, FILE *f2) 847 { 848 int m, i0, i1, j0, j1; 849 850 rewind(f1); 851 rewind(f2); 852 m = len[0]; 853 J[0] = 0; 854 J[m + 1] = len[1] + 1; 855 if (format != D_EDIT) { 856 for (i0 = 1; i0 <= m; i0 = i1 + 1) { 857 while (i0 <= m && J[i0] == J[i0 - 1] + 1) 858 i0++; 859 j0 = J[i0 - 1] + 1; 860 i1 = i0 - 1; 861 while (i1 < m && J[i1 + 1] == 0) 862 i1++; 863 j1 = J[i1 + 1] - 1; 864 J[i1] = j1; 865 change(file1, f1, file2, f2, i0, i1, j0, j1); 866 } 867 } else { 868 for (i0 = m; i0 >= 1; i0 = i1 - 1) { 869 while (i0 >= 1 && J[i0] == J[i0 + 1] - 1 && J[i0] != 0) 870 i0--; 871 j0 = J[i0 + 1] - 1; 872 i1 = i0 + 1; 873 while (i1 > 1 && J[i1 - 1] == 0) 874 i1--; 875 j1 = J[i1 - 1] + 1; 876 J[i1] = j1; 877 change(file1, f1, file2, f2, i1, i0, j1, j0); 878 } 879 } 880 if (m == 0) 881 change(file1, f1, file2, f2, 1, 0, 1, len[1]); 882 if (format == D_IFDEF) { 883 for (;;) { 884 #define c i0 885 if ((c = getc(f1)) == EOF) 886 return; 887 putchar(c); 888 } 889 #undef c 890 } 891 if (anychange != 0) { 892 if (format == D_CONTEXT) 893 dump_context_vec(f1, f2); 894 else if (format == D_UNIFIED) 895 dump_unified_vec(f1, f2); 896 } 897 } 898 899 static __inline void 900 range(int a, int b, char *separator) 901 { 902 printf("%d", a > b ? b : a); 903 if (a < b) 904 printf("%s%d", separator, b); 905 } 906 907 static __inline void 908 uni_range(int a, int b) 909 { 910 if (a < b) 911 printf("%d,%d", a, b - a + 1); 912 else if (a == b) 913 printf("%d", b); 914 else 915 printf("%d,0", b); 916 } 917 918 /* 919 * Indicate that there is a difference between lines a and b of the from file 920 * to get to lines c to d of the to file. If a is greater then b then there 921 * are no lines in the from file involved and this means that there were 922 * lines appended (beginning at b). If c is greater than d then there are 923 * lines missing from the to file. 924 */ 925 static void 926 change(char *file1, FILE *f1, char *file2, FILE *f2, int a, int b, int c, int d) 927 { 928 static size_t max_context = 64; 929 int i; 930 931 restart: 932 if (format != D_IFDEF && a > b && c > d) 933 return; 934 if (format == D_CONTEXT || format == D_UNIFIED) { 935 /* 936 * Allocate change records as needed. 937 */ 938 if (context_vec_ptr == context_vec_end - 1) { 939 ptrdiff_t offset = context_vec_ptr - context_vec_start; 940 max_context <<= 1; 941 context_vec_start = erealloc(context_vec_start, 942 max_context * sizeof(struct context_vec)); 943 context_vec_end = context_vec_start + max_context; 944 context_vec_ptr = context_vec_start + offset; 945 } 946 if (anychange == 0) { 947 /* 948 * Print the context/unidiff header first time through. 949 */ 950 if (label != NULL) 951 printf("%s %s\n", 952 format == D_CONTEXT ? "***" : "---", label); 953 else 954 printf("%s %s %s", 955 format == D_CONTEXT ? "***" : "---", file1, 956 ctime(&stb1.st_mtime)); 957 printf("%s %s %s", 958 format == D_CONTEXT ? "---" : "+++", file2, 959 ctime(&stb2.st_mtime)); 960 anychange = 1; 961 } else if (a > context_vec_ptr->b + (2 * context) && 962 c > context_vec_ptr->d + (2 * context)) { 963 /* 964 * If this change is more than 'context' lines from the 965 * previous change, dump the record and reset it. 966 */ 967 if (format == D_CONTEXT) 968 dump_context_vec(f1, f2); 969 else 970 dump_unified_vec(f1, f2); 971 } 972 context_vec_ptr++; 973 context_vec_ptr->a = a; 974 context_vec_ptr->b = b; 975 context_vec_ptr->c = c; 976 context_vec_ptr->d = d; 977 return; 978 } 979 if (anychange == 0) 980 anychange = 1; 981 switch (format) { 982 983 case D_NORMAL: 984 case D_EDIT: 985 range(a, b, ","); 986 putchar(a > b ? 'a' : c > d ? 'd' : 'c'); 987 if (format == D_NORMAL) 988 range(c, d, ","); 989 putchar('\n'); 990 break; 991 case D_REVERSE: 992 putchar(a > b ? 'a' : c > d ? 'd' : 'c'); 993 range(a, b, " "); 994 putchar('\n'); 995 break; 996 case D_NREVERSE: 997 if (a > b) 998 printf("a%d %d\n", b, d - c + 1); 999 else { 1000 printf("d%d %d\n", a, b - a + 1); 1001 if (!(c > d)) 1002 /* add changed lines */ 1003 printf("a%d %d\n", b, d - c + 1); 1004 } 1005 break; 1006 } 1007 if (format == D_NORMAL || format == D_IFDEF) { 1008 fetch(ixold, a, b, f1, '<', 1); 1009 if (a <= b && c <= d && format == D_NORMAL) 1010 puts("---"); 1011 } 1012 i = fetch(ixnew, c, d, f2, format == D_NORMAL ? '>' : '\0', 0); 1013 if (i != 0 && format == D_EDIT) { 1014 /* 1015 * A non-zero return value for D_EDIT indicates that the 1016 * last line printed was a bare dot (".") that has been 1017 * escaped as ".." to prevent ed(1) from misinterpreting 1018 * it. We have to add a substitute command to change this 1019 * back and restart where we left off. 1020 */ 1021 puts("."); 1022 printf("%ds/^\\.\\././\n", a); 1023 a += i; 1024 c += i; 1025 goto restart; 1026 } 1027 if ((format == D_EDIT || format == D_REVERSE) && c <= d) 1028 puts("."); 1029 if (inifdef) { 1030 printf("#endif /* %s */\n", ifdefname); 1031 inifdef = 0; 1032 } 1033 } 1034 1035 static int 1036 fetch(long *f, int a, int b, FILE *lb, int ch, int oldfile) 1037 { 1038 int i, j, c, lastc, col, nc; 1039 1040 /* 1041 * When doing #ifdef's, copy down to current line 1042 * if this is the first file, so that stuff makes it to output. 1043 */ 1044 if (format == D_IFDEF && oldfile) { 1045 long curpos = ftell(lb); 1046 /* print through if append (a>b), else to (nb: 0 vs 1 orig) */ 1047 nc = f[a > b ? b : a - 1] - curpos; 1048 for (i = 0; i < nc; i++) 1049 putchar(getc(lb)); 1050 } 1051 if (a > b) 1052 return (0); 1053 if (format == D_IFDEF) { 1054 if (inifdef) { 1055 printf("#else /* %s%s */\n", 1056 oldfile == 1 ? "!" : "", ifdefname); 1057 } else { 1058 if (oldfile) 1059 printf("#ifndef %s\n", ifdefname); 1060 else 1061 printf("#ifdef %s\n", ifdefname); 1062 } 1063 inifdef = 1 + oldfile; 1064 } 1065 for (i = a; i <= b; i++) { 1066 fseek(lb, f[i - 1], SEEK_SET); 1067 nc = f[i] - f[i - 1]; 1068 if (format != D_IFDEF && ch != '\0') { 1069 putchar(ch); 1070 if (Tflag && (format == D_NORMAL || format == D_CONTEXT 1071 || format == D_UNIFIED)) 1072 putchar('\t'); 1073 else if (format != D_UNIFIED) 1074 putchar(' '); 1075 } 1076 col = 0; 1077 for (j = 0, lastc = '\0'; j < nc; j++, lastc = c) { 1078 if ((c = getc(lb)) == EOF) { 1079 puts("\n\\ No newline at end of file"); 1080 return (0);; 1081 } 1082 if (c == '\t' && tflag) { 1083 do { 1084 putchar(' '); 1085 } while (++col & 7); 1086 } else { 1087 if (format == D_EDIT && j == 1 && c == '\n' 1088 && lastc == '.') { 1089 /* 1090 * Don't print a bare "." line 1091 * since that will confuse ed(1). 1092 * Print ".." instead and return, 1093 * giving the caller an offset 1094 * from which to restart. 1095 */ 1096 puts("."); 1097 return (i - a + 1); 1098 } 1099 putchar(c); 1100 col++; 1101 } 1102 } 1103 } 1104 return (0); 1105 } 1106 1107 #define HASHMASK (16 - 1) /* for masking out 16 bytes */ 1108 1109 /* 1110 * hashing has the effect of 1111 * arranging line in 7-bit bytes and then 1112 * summing 1-s complement in 16-bit hunks 1113 */ 1114 static int 1115 readhash(FILE *f) 1116 { 1117 unsigned int shift; 1118 int t, space; 1119 long sum; 1120 1121 sum = 1; 1122 space = 0; 1123 if (!bflag && !wflag) { 1124 if (iflag) 1125 for (shift = 0; (t = getc(f)) != '\n'; shift += 7) { 1126 if (t == EOF) { 1127 if (shift == 0) 1128 return (0); 1129 break; 1130 } 1131 sum += (long)chrtran[t] << (shift &= HASHMASK); 1132 } 1133 else 1134 for (shift = 0; (t = getc(f)) != '\n'; shift += 7) { 1135 if (t == EOF) { 1136 if (shift == 0) 1137 return (0); 1138 break; 1139 } 1140 sum += (long)t << (shift &= HASHMASK); 1141 } 1142 } else { 1143 for (shift = 0;;) { 1144 switch (t = getc(f)) { 1145 case '\t': 1146 case ' ': 1147 space++; 1148 continue; 1149 default: 1150 if (space && !wflag) { 1151 shift += 7; 1152 space = 0; 1153 } 1154 sum += (long)chrtran[t] << (shift &= HASHMASK); 1155 shift += 7; 1156 continue; 1157 case EOF: 1158 if (shift == 0) 1159 return (0); 1160 /* FALLTHROUGH */ 1161 case '\n': 1162 break; 1163 } 1164 break; 1165 } 1166 } 1167 return (sum); 1168 } 1169 1170 int 1171 asciifile(FILE *f) 1172 { 1173 char buf[BUFSIZ], *cp; 1174 int cnt; 1175 1176 if (aflag || f == NULL) 1177 return (1); 1178 1179 rewind(f); 1180 cnt = fread(buf, 1, sizeof(buf), f); 1181 cp = buf; 1182 while (--cnt >= 0) 1183 if (*cp++ & 0200) 1184 return (0); 1185 return (1); 1186 } 1187 1188 static __inline int min(int a, int b) 1189 { 1190 return (a < b ? a : b); 1191 } 1192 1193 static __inline int max(int a, int b) 1194 { 1195 return (a > b ? a : b); 1196 } 1197 1198 /* dump accumulated "context" diff changes */ 1199 static void 1200 dump_context_vec(FILE *f1, FILE *f2) 1201 { 1202 struct context_vec *cvp = context_vec_start; 1203 int lowa, upb, lowc, upd, do_output; 1204 int a, b, c, d; 1205 char ch; 1206 1207 if (context_vec_start > context_vec_ptr) 1208 return; 1209 1210 b = d = 0; /* gcc */ 1211 lowa = max(1, cvp->a - context); 1212 upb = min(len[0], context_vec_ptr->b + context); 1213 lowc = max(1, cvp->c - context); 1214 upd = min(len[1], context_vec_ptr->d + context); 1215 1216 printf("***************\n*** "); 1217 range(lowa, upb, ","); 1218 printf(" ****\n"); 1219 1220 /* 1221 * Output changes to the "old" file. The first loop suppresses 1222 * output if there were no changes to the "old" file (we'll see 1223 * the "old" lines as context in the "new" list). 1224 */ 1225 do_output = 0; 1226 for (; cvp <= context_vec_ptr; cvp++) 1227 if (cvp->a <= cvp->b) { 1228 cvp = context_vec_start; 1229 do_output++; 1230 break; 1231 } 1232 if (do_output) { 1233 while (cvp <= context_vec_ptr) { 1234 a = cvp->a; 1235 b = cvp->b; 1236 c = cvp->c; 1237 d = cvp->d; 1238 1239 if (a <= b && c <= d) 1240 ch = 'c'; 1241 else 1242 ch = (a <= b) ? 'd' : 'a'; 1243 1244 if (ch == 'a') 1245 fetch(ixold, lowa, b, f1, ' ', 0); 1246 else { 1247 fetch(ixold, lowa, a - 1, f1, ' ', 0); 1248 fetch(ixold, a, b, f1, 1249 ch == 'c' ? '!' : '-', 0); 1250 } 1251 lowa = b + 1; 1252 cvp++; 1253 } 1254 fetch(ixold, b + 1, upb, f1, ' ', 0); 1255 } 1256 /* output changes to the "new" file */ 1257 printf("--- "); 1258 range(lowc, upd, ","); 1259 printf(" ----\n"); 1260 1261 do_output = 0; 1262 for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++) 1263 if (cvp->c <= cvp->d) { 1264 cvp = context_vec_start; 1265 do_output++; 1266 break; 1267 } 1268 if (do_output) { 1269 while (cvp <= context_vec_ptr) { 1270 a = cvp->a; 1271 b = cvp->b; 1272 c = cvp->c; 1273 d = cvp->d; 1274 1275 if (a <= b && c <= d) 1276 ch = 'c'; 1277 else 1278 ch = (a <= b) ? 'd' : 'a'; 1279 1280 if (ch == 'd') 1281 fetch(ixnew, lowc, d, f2, ' ', 0); 1282 else { 1283 fetch(ixnew, lowc, c - 1, f2, ' ', 0); 1284 fetch(ixnew, c, d, f2, 1285 ch == 'c' ? '!' : '+', 0); 1286 } 1287 lowc = d + 1; 1288 cvp++; 1289 } 1290 fetch(ixnew, d + 1, upd, f2, ' ', 0); 1291 } 1292 context_vec_ptr = context_vec_start - 1; 1293 } 1294 1295 /* dump accumulated "unified" diff changes */ 1296 static void 1297 dump_unified_vec(FILE *f1, FILE *f2) 1298 { 1299 struct context_vec *cvp = context_vec_start; 1300 int lowa, upb, lowc, upd; 1301 int a, b, c, d; 1302 char ch; 1303 1304 if (context_vec_start > context_vec_ptr) 1305 return; 1306 1307 b = d = 0; /* gcc */ 1308 lowa = max(1, cvp->a - context); 1309 upb = min(len[0], context_vec_ptr->b + context); 1310 lowc = max(1, cvp->c - context); 1311 upd = min(len[1], context_vec_ptr->d + context); 1312 1313 fputs("@@ -", stdout); 1314 uni_range(lowa, upb); 1315 fputs(" +", stdout); 1316 uni_range(lowc, upd); 1317 fputs(" @@\n", stdout); 1318 1319 /* 1320 * Output changes in "unified" diff format--the old and new lines 1321 * are printed together. 1322 */ 1323 for (; cvp <= context_vec_ptr; cvp++) { 1324 a = cvp->a; 1325 b = cvp->b; 1326 c = cvp->c; 1327 d = cvp->d; 1328 1329 /* 1330 * c: both new and old changes 1331 * d: only changes in the old file 1332 * a: only changes in the new file 1333 */ 1334 if (a <= b && c <= d) 1335 ch = 'c'; 1336 else 1337 ch = (a <= b) ? 'd' : 'a'; 1338 1339 switch (ch) { 1340 case 'c': 1341 fetch(ixold, lowa, a - 1, f1, ' ', 0); 1342 fetch(ixold, a, b, f1, '-', 0); 1343 fetch(ixnew, c, d, f2, '+', 0); 1344 break; 1345 case 'd': 1346 fetch(ixold, lowa, a - 1, f1, ' ', 0); 1347 fetch(ixold, a, b, f1, '-', 0); 1348 break; 1349 case 'a': 1350 fetch(ixnew, lowc, c - 1, f2, ' ', 0); 1351 fetch(ixnew, c, d, f2, '+', 0); 1352 break; 1353 } 1354 lowa = b + 1; 1355 lowc = d + 1; 1356 } 1357 fetch(ixnew, d + 1, upd, f2, ' ', 0); 1358 1359 context_vec_ptr = context_vec_start - 1; 1360 } 1361