1 /* $OpenBSD: diffreg.c,v 1.40 2003/07/22 00:20:40 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.40 2003/07/22 00:20:40 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 *, char *, 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 printf("%s %s %s", format == D_CONTEXT ? "***" : "---", 951 file1, ctime(&stb1.st_mtime)); 952 printf("%s %s %s", format == D_CONTEXT ? "---" : "+++", 953 file2, ctime(&stb2.st_mtime)); 954 anychange = 1; 955 } else if (a > context_vec_ptr->b + (2 * context) && 956 c > context_vec_ptr->d + (2 * context)) { 957 /* 958 * If this change is more than 'context' lines from the 959 * previous change, dump the record and reset it. 960 */ 961 if (format == D_CONTEXT) 962 dump_context_vec(f1, f2); 963 else 964 dump_unified_vec(f1, f2); 965 } 966 context_vec_ptr++; 967 context_vec_ptr->a = a; 968 context_vec_ptr->b = b; 969 context_vec_ptr->c = c; 970 context_vec_ptr->d = d; 971 return; 972 } 973 if (anychange == 0) 974 anychange = 1; 975 switch (format) { 976 977 case D_NORMAL: 978 case D_EDIT: 979 range(a, b, ","); 980 putchar(a > b ? 'a' : c > d ? 'd' : 'c'); 981 if (format == D_NORMAL) 982 range(c, d, ","); 983 putchar('\n'); 984 break; 985 case D_REVERSE: 986 putchar(a > b ? 'a' : c > d ? 'd' : 'c'); 987 range(a, b, " "); 988 putchar('\n'); 989 break; 990 case D_NREVERSE: 991 if (a > b) 992 printf("a%d %d\n", b, d - c + 1); 993 else { 994 printf("d%d %d\n", a, b - a + 1); 995 if (!(c > d)) 996 /* add changed lines */ 997 printf("a%d %d\n", b, d - c + 1); 998 } 999 break; 1000 } 1001 if (format == D_NORMAL || format == D_IFDEF) { 1002 fetch(ixold, a, b, f1, "< ", 1); 1003 if (a <= b && c <= d && format == D_NORMAL) 1004 puts("---"); 1005 } 1006 i = fetch(ixnew, c, d, f2, format == D_NORMAL ? "> " : "", 0); 1007 if (i != 0 && format == D_EDIT) { 1008 /* 1009 * A non-zero return value for D_EDIT indicates that the 1010 * last line printed was a bare dot (".") that has been 1011 * escaped as ".." to prevent ed(1) from misinterpreting 1012 * it. We have to add a substitute command to change this 1013 * back and restart where we left off. 1014 */ 1015 puts("."); 1016 printf("%ds/^\\.\\././\n", a); 1017 a += i; 1018 c += i; 1019 goto restart; 1020 } 1021 if ((format == D_EDIT || format == D_REVERSE) && c <= d) 1022 puts("."); 1023 if (inifdef) { 1024 printf("#endif /* %s */\n", ifdefname); 1025 inifdef = 0; 1026 } 1027 } 1028 1029 static int 1030 fetch(long *f, int a, int b, FILE *lb, char *s, int oldfile) 1031 { 1032 int i, j, c, lastc, col, nc; 1033 1034 /* 1035 * When doing #ifdef's, copy down to current line 1036 * if this is the first file, so that stuff makes it to output. 1037 */ 1038 if (format == D_IFDEF && oldfile) { 1039 long curpos = ftell(lb); 1040 /* print through if append (a>b), else to (nb: 0 vs 1 orig) */ 1041 nc = f[a > b ? b : a - 1] - curpos; 1042 for (i = 0; i < nc; i++) 1043 putchar(getc(lb)); 1044 } 1045 if (a > b) 1046 return (0); 1047 if (format == D_IFDEF) { 1048 if (inifdef) { 1049 printf("#else /* %s%s */\n", 1050 oldfile == 1 ? "!" : "", ifdefname); 1051 } else { 1052 if (oldfile) 1053 printf("#ifndef %s\n", ifdefname); 1054 else 1055 printf("#ifdef %s\n", ifdefname); 1056 } 1057 inifdef = 1 + oldfile; 1058 } 1059 for (i = a; i <= b; i++) { 1060 fseek(lb, f[i - 1], SEEK_SET); 1061 nc = f[i] - f[i - 1]; 1062 if (format != D_IFDEF) 1063 fputs(s, stdout); 1064 col = 0; 1065 for (j = 0, lastc = '\0'; j < nc; j++, lastc = c) { 1066 if ((c = getc(lb)) == EOF) { 1067 puts("\n\\ No newline at end of file"); 1068 return (0);; 1069 } 1070 if (c == '\t' && tflag) { 1071 do { 1072 putchar(' '); 1073 } while (++col & 7); 1074 } else { 1075 if (format == D_EDIT && j == 1 && c == '\n' 1076 && lastc == '.') { 1077 /* 1078 * Don't print a bare "." line 1079 * since that will confuse ed(1). 1080 * Print ".." instead and return, 1081 * giving the caller an offset 1082 * from which to restart. 1083 */ 1084 puts("."); 1085 return (i - a + 1); 1086 } 1087 putchar(c); 1088 col++; 1089 } 1090 } 1091 } 1092 return (0); 1093 } 1094 1095 #define HASHMASK (16 - 1) /* for masking out 16 bytes */ 1096 1097 /* 1098 * hashing has the effect of 1099 * arranging line in 7-bit bytes and then 1100 * summing 1-s complement in 16-bit hunks 1101 */ 1102 static int 1103 readhash(FILE *f) 1104 { 1105 unsigned int shift; 1106 int t, space; 1107 long sum; 1108 1109 sum = 1; 1110 space = 0; 1111 if (!bflag && !wflag) { 1112 if (iflag) 1113 for (shift = 0; (t = getc(f)) != '\n'; shift += 7) { 1114 if (t == EOF) { 1115 if (shift == 0) 1116 return (0); 1117 break; 1118 } 1119 sum += (long)chrtran[t] << (shift &= HASHMASK); 1120 } 1121 else 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)t << (shift &= HASHMASK); 1129 } 1130 } else { 1131 for (shift = 0;;) { 1132 switch (t = getc(f)) { 1133 case '\t': 1134 case ' ': 1135 space++; 1136 continue; 1137 default: 1138 if (space && !wflag) { 1139 shift += 7; 1140 space = 0; 1141 } 1142 sum += (long)chrtran[t] << (shift &= HASHMASK); 1143 shift += 7; 1144 continue; 1145 case EOF: 1146 if (shift == 0) 1147 return (0); 1148 /* FALLTHROUGH */ 1149 case '\n': 1150 break; 1151 } 1152 break; 1153 } 1154 } 1155 return (sum); 1156 } 1157 1158 int 1159 asciifile(FILE *f) 1160 { 1161 char buf[BUFSIZ], *cp; 1162 int cnt; 1163 1164 if (aflag || f == NULL) 1165 return (1); 1166 1167 rewind(f); 1168 cnt = fread(buf, 1, sizeof(buf), f); 1169 cp = buf; 1170 while (--cnt >= 0) 1171 if (*cp++ & 0200) 1172 return (0); 1173 return (1); 1174 } 1175 1176 static __inline int min(int a, int b) 1177 { 1178 return (a < b ? a : b); 1179 } 1180 1181 static __inline int max(int a, int b) 1182 { 1183 return (a > b ? a : b); 1184 } 1185 1186 /* dump accumulated "context" diff changes */ 1187 static void 1188 dump_context_vec(FILE *f1, FILE *f2) 1189 { 1190 struct context_vec *cvp = context_vec_start; 1191 int lowa, upb, lowc, upd, do_output; 1192 int a, b, c, d; 1193 char ch; 1194 1195 if (context_vec_start > context_vec_ptr) 1196 return; 1197 1198 b = d = 0; /* gcc */ 1199 lowa = max(1, cvp->a - context); 1200 upb = min(len[0], context_vec_ptr->b + context); 1201 lowc = max(1, cvp->c - context); 1202 upd = min(len[1], context_vec_ptr->d + context); 1203 1204 printf("***************\n*** "); 1205 range(lowa, upb, ","); 1206 printf(" ****\n"); 1207 1208 /* 1209 * Output changes to the "old" file. The first loop suppresses 1210 * output if there were no changes to the "old" file (we'll see 1211 * the "old" lines as context in the "new" list). 1212 */ 1213 do_output = 0; 1214 for (; cvp <= context_vec_ptr; cvp++) 1215 if (cvp->a <= cvp->b) { 1216 cvp = context_vec_start; 1217 do_output++; 1218 break; 1219 } 1220 if (do_output) { 1221 while (cvp <= context_vec_ptr) { 1222 a = cvp->a; 1223 b = cvp->b; 1224 c = cvp->c; 1225 d = cvp->d; 1226 1227 if (a <= b && c <= d) 1228 ch = 'c'; 1229 else 1230 ch = (a <= b) ? 'd' : 'a'; 1231 1232 if (ch == 'a') 1233 fetch(ixold, lowa, b, f1, " ", 0); 1234 else { 1235 fetch(ixold, lowa, a - 1, f1, " ", 0); 1236 fetch(ixold, a, b, f1, 1237 ch == 'c' ? "! " : "- ", 0); 1238 } 1239 lowa = b + 1; 1240 cvp++; 1241 } 1242 fetch(ixold, b + 1, upb, f1, " ", 0); 1243 } 1244 /* output changes to the "new" file */ 1245 printf("--- "); 1246 range(lowc, upd, ","); 1247 printf(" ----\n"); 1248 1249 do_output = 0; 1250 for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++) 1251 if (cvp->c <= cvp->d) { 1252 cvp = context_vec_start; 1253 do_output++; 1254 break; 1255 } 1256 if (do_output) { 1257 while (cvp <= context_vec_ptr) { 1258 a = cvp->a; 1259 b = cvp->b; 1260 c = cvp->c; 1261 d = cvp->d; 1262 1263 if (a <= b && c <= d) 1264 ch = 'c'; 1265 else 1266 ch = (a <= b) ? 'd' : 'a'; 1267 1268 if (ch == 'd') 1269 fetch(ixnew, lowc, d, f2, " ", 0); 1270 else { 1271 fetch(ixnew, lowc, c - 1, f2, " ", 0); 1272 fetch(ixnew, c, d, f2, 1273 ch == 'c' ? "! " : "+ ", 0); 1274 } 1275 lowc = d + 1; 1276 cvp++; 1277 } 1278 fetch(ixnew, d + 1, upd, f2, " ", 0); 1279 } 1280 context_vec_ptr = context_vec_start - 1; 1281 } 1282 1283 /* dump accumulated "unified" diff changes */ 1284 static void 1285 dump_unified_vec(FILE *f1, FILE *f2) 1286 { 1287 struct context_vec *cvp = context_vec_start; 1288 int lowa, upb, lowc, upd; 1289 int a, b, c, d; 1290 char ch; 1291 1292 if (context_vec_start > context_vec_ptr) 1293 return; 1294 1295 b = d = 0; /* gcc */ 1296 lowa = max(1, cvp->a - context); 1297 upb = min(len[0], context_vec_ptr->b + context); 1298 lowc = max(1, cvp->c - context); 1299 upd = min(len[1], context_vec_ptr->d + context); 1300 1301 fputs("@@ -", stdout); 1302 uni_range(lowa, upb); 1303 fputs(" +", stdout); 1304 uni_range(lowc, upd); 1305 fputs(" @@\n", stdout); 1306 1307 /* 1308 * Output changes in "unified" diff format--the old and new lines 1309 * are printed together. 1310 */ 1311 for (; cvp <= context_vec_ptr; cvp++) { 1312 a = cvp->a; 1313 b = cvp->b; 1314 c = cvp->c; 1315 d = cvp->d; 1316 1317 /* 1318 * c: both new and old changes 1319 * d: only changes in the old file 1320 * a: only changes in the new file 1321 */ 1322 if (a <= b && c <= d) 1323 ch = 'c'; 1324 else 1325 ch = (a <= b) ? 'd' : 'a'; 1326 1327 switch (ch) { 1328 case 'c': 1329 fetch(ixold, lowa, a - 1, f1, " ", 0); 1330 fetch(ixold, a, b, f1, "-", 0); 1331 fetch(ixnew, c, d, f2, "+", 0); 1332 break; 1333 case 'd': 1334 fetch(ixold, lowa, a - 1, f1, " ", 0); 1335 fetch(ixold, a, b, f1, "-", 0); 1336 break; 1337 case 'a': 1338 fetch(ixnew, lowc, c - 1, f2, " ", 0); 1339 fetch(ixnew, c, d, f2, "+", 0); 1340 break; 1341 } 1342 lowa = b + 1; 1343 lowc = d + 1; 1344 } 1345 fetch(ixnew, d + 1, upd, f2, " ", 0); 1346 1347 context_vec_ptr = context_vec_start - 1; 1348 } 1349