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