usr.bin/diff/diffreg.c

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