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