File: | src/gnu/usr.bin/cvs/diff/io.c |
Warning: | line 456, column 12 Array access (from variable 'p0') results in a null pointer dereference |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | /* File I/O for GNU DIFF. | |||
2 | Copyright (C) 1988, 1989, 1992, 1993, 1994 Free Software Foundation, Inc. | |||
3 | ||||
4 | This file is part of GNU DIFF. | |||
5 | ||||
6 | GNU DIFF is free software; you can redistribute it and/or modify | |||
7 | it under the terms of the GNU General Public License as published by | |||
8 | the Free Software Foundation; either version 2, or (at your option) | |||
9 | any later version. | |||
10 | ||||
11 | GNU DIFF is distributed in the hope that it will be useful, | |||
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |||
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |||
14 | GNU General Public License for more details. | |||
15 | ||||
16 | */ | |||
17 | ||||
18 | #include "diff.h" | |||
19 | ||||
20 | /* Rotate a value n bits to the left. */ | |||
21 | #define UINT_BIT(sizeof (unsigned) * 8) (sizeof (unsigned) * CHAR_BIT8) | |||
22 | #define ROL(v, n)((v) << (n) | (v) >> ((sizeof (unsigned) * 8) - ( n))) ((v) << (n) | (v) >> (UINT_BIT(sizeof (unsigned) * 8) - (n))) | |||
23 | ||||
24 | /* Given a hash value and a new character, return a new hash value. */ | |||
25 | #define HASH(h, c)((c) + ((h) << (7) | (h) >> ((sizeof (unsigned) * 8) - (7)))) ((c) + ROL (h, 7)((h) << (7) | (h) >> ((sizeof (unsigned) * 8) - ( 7)))) | |||
26 | ||||
27 | /* Guess remaining number of lines from number N of lines so far, | |||
28 | size S so far, and total size T. */ | |||
29 | #define GUESS_LINES(n,s,t)(((t) - (s)) / ((n) < 10 ? 32 : (s) / ((n)-1)) + 5) (((t) - (s)) / ((n) < 10 ? 32 : (s) / ((n)-1)) + 5) | |||
30 | ||||
31 | /* Type used for fast prefix comparison in find_identical_ends. */ | |||
32 | #ifndef wordint | |||
33 | #define wordint int | |||
34 | #endif | |||
35 | ||||
36 | /* Lines are put into equivalence classes (of lines that match in line_cmp). | |||
37 | Each equivalence class is represented by one of these structures, | |||
38 | but only while the classes are being computed. | |||
39 | Afterward, each class is represented by a number. */ | |||
40 | struct equivclass | |||
41 | { | |||
42 | int next; /* Next item in this bucket. */ | |||
43 | unsigned hash; /* Hash of lines in this class. */ | |||
44 | char const *line; /* A line that fits this class. */ | |||
45 | size_t length; /* That line's length, not counting its newline. */ | |||
46 | }; | |||
47 | ||||
48 | /* Hash-table: array of buckets, each being a chain of equivalence classes. | |||
49 | buckets[-1] is reserved for incomplete lines. */ | |||
50 | static int *buckets; | |||
51 | ||||
52 | /* Number of buckets in the hash table array, not counting buckets[-1]. */ | |||
53 | static int nbuckets; | |||
54 | ||||
55 | /* Array in which the equivalence classes are allocated. | |||
56 | The bucket-chains go through the elements in this array. | |||
57 | The number of an equivalence class is its index in this array. */ | |||
58 | static struct equivclass *equivs; | |||
59 | ||||
60 | /* Index of first free element in the array `equivs'. */ | |||
61 | static int equivs_index; | |||
62 | ||||
63 | /* Number of elements allocated in the array `equivs'. */ | |||
64 | static int equivs_alloc; | |||
65 | ||||
66 | static void find_and_hash_each_line PARAMS((struct file_data *))(struct file_data *); | |||
67 | static void find_identical_ends PARAMS((struct file_data[]))(struct file_data[]); | |||
68 | static void prepare_text_end PARAMS((struct file_data *))(struct file_data *); | |||
69 | ||||
70 | /* Check for binary files and compare them for exact identity. */ | |||
71 | ||||
72 | /* Return 1 if BUF contains a non text character. | |||
73 | SIZE is the number of characters in BUF. */ | |||
74 | ||||
75 | #define binary_file_p(buf, size)(memchr (buf, '\0', size) != 0) (memchr (buf, '\0', size) != 0) | |||
76 | ||||
77 | /* Get ready to read the current file. | |||
78 | Return nonzero if SKIP_TEST is zero, | |||
79 | and if it appears to be a binary file. */ | |||
80 | ||||
81 | int | |||
82 | sip (current, skip_test) | |||
83 | struct file_data *current; | |||
84 | int skip_test; | |||
85 | { | |||
86 | /* If we have a nonexistent file at this stage, treat it as empty. */ | |||
87 | if (current->desc < 0) | |||
88 | { | |||
89 | /* Leave room for a sentinel. */ | |||
90 | current->bufsize = sizeof (wordint); | |||
91 | current->buffer = xmalloc (current->bufsize); | |||
92 | } | |||
93 | else | |||
94 | { | |||
95 | current->bufsize = STAT_BLOCKSIZE (current->stat)(current->stat).st_blksize; | |||
96 | current->buffer = xmalloc (current->bufsize); | |||
97 | ||||
98 | if (! skip_test) | |||
99 | { | |||
100 | /* Check first part of file to see if it's a binary file. */ | |||
101 | #if HAVE_SETMODE0 | |||
102 | int oldmode = setmode (current->desc, O_BINARY); | |||
103 | #endif | |||
104 | size_t n = read (current->desc, current->buffer, current->bufsize); | |||
105 | if (n == -1) | |||
106 | pfatal_with_name (current->name); | |||
107 | current->buffered_chars = n; | |||
108 | #if HAVE_SETMODE0 | |||
109 | if (oldmode != O_BINARY) | |||
110 | { | |||
111 | if (lseek (current->desc, - (off_t) n, SEEK_CUR1) == -1) | |||
112 | pfatal_with_name (current->name); | |||
113 | setmode (current->desc, oldmode); | |||
114 | current->buffered_chars = 0; | |||
115 | } | |||
116 | #endif | |||
117 | return binary_file_p (current->buffer, n)(memchr (current->buffer, '\0', n) != 0); | |||
118 | } | |||
119 | } | |||
120 | ||||
121 | current->buffered_chars = 0; | |||
122 | return 0; | |||
123 | } | |||
124 | ||||
125 | /* Slurp the rest of the current file completely into memory. */ | |||
126 | ||||
127 | void | |||
128 | slurp (current) | |||
129 | struct file_data *current; | |||
130 | { | |||
131 | size_t cc; | |||
132 | ||||
133 | if (current->desc < 0) | |||
134 | /* The file is nonexistent. */ | |||
135 | ; | |||
136 | else if (S_ISREG (current->stat.st_mode)((current->stat.st_mode & 0170000) == 0100000)) | |||
137 | { | |||
138 | /* It's a regular file; slurp in the rest all at once. */ | |||
139 | ||||
140 | /* Get the size out of the stat block. | |||
141 | Allocate enough room for appended newline and sentinel. */ | |||
142 | cc = current->stat.st_size + 1 + sizeof (wordint); | |||
143 | if (current->bufsize < cc) | |||
144 | { | |||
145 | current->bufsize = cc; | |||
146 | current->buffer = xrealloc (current->buffer, cc); | |||
147 | } | |||
148 | ||||
149 | if (current->buffered_chars < current->stat.st_size) | |||
150 | { | |||
151 | cc = read (current->desc, | |||
152 | current->buffer + current->buffered_chars, | |||
153 | current->stat.st_size - current->buffered_chars); | |||
154 | if (cc == -1) | |||
155 | pfatal_with_name (current->name); | |||
156 | current->buffered_chars += cc; | |||
157 | } | |||
158 | } | |||
159 | /* It's not a regular file; read it, growing the buffer as needed. */ | |||
160 | else if (always_text_flag || current->buffered_chars != 0) | |||
161 | { | |||
162 | for (;;) | |||
163 | { | |||
164 | if (current->buffered_chars == current->bufsize) | |||
165 | { | |||
166 | current->bufsize = current->bufsize * 2; | |||
167 | current->buffer = xrealloc (current->buffer, current->bufsize); | |||
168 | } | |||
169 | cc = read (current->desc, | |||
170 | current->buffer + current->buffered_chars, | |||
171 | current->bufsize - current->buffered_chars); | |||
172 | if (cc == 0) | |||
173 | break; | |||
174 | if (cc == -1) | |||
175 | pfatal_with_name (current->name); | |||
176 | current->buffered_chars += cc; | |||
177 | } | |||
178 | /* Allocate just enough room for appended newline and sentinel. */ | |||
179 | current->bufsize = current->buffered_chars + 1 + sizeof (wordint); | |||
180 | current->buffer = xrealloc (current->buffer, current->bufsize); | |||
181 | } | |||
182 | } | |||
183 | ||||
184 | /* Split the file into lines, simultaneously computing the equivalence class for | |||
185 | each line. */ | |||
186 | ||||
187 | static void | |||
188 | find_and_hash_each_line (current) | |||
189 | struct file_data *current; | |||
190 | { | |||
191 | unsigned h; | |||
192 | unsigned char const *p = (unsigned char const *) current->prefix_end; | |||
193 | unsigned char c; | |||
194 | int i, *bucket; | |||
195 | size_t length; | |||
196 | ||||
197 | /* Cache often-used quantities in local variables to help the compiler. */ | |||
198 | char const **linbuf = current->linbuf; | |||
199 | int alloc_lines = current->alloc_lines; | |||
200 | int line = 0; | |||
201 | int linbuf_base = current->linbuf_base; | |||
202 | int *cureqs = (int *) xmalloc (alloc_lines * sizeof (int)); | |||
203 | struct equivclass *eqs = equivs; | |||
204 | int eqs_index = equivs_index; | |||
205 | int eqs_alloc = equivs_alloc; | |||
206 | char const *suffix_begin = current->suffix_begin; | |||
207 | char const *bufend = current->buffer + current->buffered_chars; | |||
208 | int use_line_cmp = ignore_some_line_changes; | |||
209 | ||||
210 | while ((char const *) p < suffix_begin) | |||
211 | { | |||
212 | char const *ip = (char const *) p; | |||
213 | ||||
214 | /* Compute the equivalence class for this line. */ | |||
215 | ||||
216 | h = 0; | |||
217 | ||||
218 | /* Hash this line until we find a newline. */ | |||
219 | if (ignore_case_flag) | |||
220 | { | |||
221 | if (ignore_all_space_flag) | |||
222 | while ((c = *p++) != '\n') | |||
223 | { | |||
224 | if (! ISSPACE (c)(1 && isspace (c))) | |||
225 | h = HASH (h, ISUPPER (c) ? tolower (c) : c)(((1 && isupper (c)) ? tolower (c) : c) + ((h) << (7) | (h) >> ((sizeof (unsigned) * 8) - (7)))); | |||
226 | } | |||
227 | else if (ignore_space_change_flag) | |||
228 | while ((c = *p++) != '\n') | |||
229 | { | |||
230 | if (ISSPACE (c)(1 && isspace (c))) | |||
231 | { | |||
232 | for (;;) | |||
233 | { | |||
234 | c = *p++; | |||
235 | if (!ISSPACE (c)(1 && isspace (c))) | |||
236 | break; | |||
237 | if (c == '\n') | |||
238 | goto hashing_done; | |||
239 | } | |||
240 | h = HASH (h, ' ')((' ') + ((h) << (7) | (h) >> ((sizeof (unsigned) * 8) - (7)))); | |||
241 | } | |||
242 | /* C is now the first non-space. */ | |||
243 | h = HASH (h, ISUPPER (c) ? tolower (c) : c)(((1 && isupper (c)) ? tolower (c) : c) + ((h) << (7) | (h) >> ((sizeof (unsigned) * 8) - (7)))); | |||
244 | } | |||
245 | else | |||
246 | while ((c = *p++) != '\n') | |||
247 | h = HASH (h, ISUPPER (c) ? tolower (c) : c)(((1 && isupper (c)) ? tolower (c) : c) + ((h) << (7) | (h) >> ((sizeof (unsigned) * 8) - (7)))); | |||
248 | } | |||
249 | else | |||
250 | { | |||
251 | if (ignore_all_space_flag) | |||
252 | while ((c = *p++) != '\n') | |||
253 | { | |||
254 | if (! ISSPACE (c)(1 && isspace (c))) | |||
255 | h = HASH (h, c)((c) + ((h) << (7) | (h) >> ((sizeof (unsigned) * 8) - (7)))); | |||
256 | } | |||
257 | else if (ignore_space_change_flag) | |||
258 | while ((c = *p++) != '\n') | |||
259 | { | |||
260 | if (ISSPACE (c)(1 && isspace (c))) | |||
261 | { | |||
262 | for (;;) | |||
263 | { | |||
264 | c = *p++; | |||
265 | if (!ISSPACE (c)(1 && isspace (c))) | |||
266 | break; | |||
267 | if (c == '\n') | |||
268 | goto hashing_done; | |||
269 | } | |||
270 | h = HASH (h, ' ')((' ') + ((h) << (7) | (h) >> ((sizeof (unsigned) * 8) - (7)))); | |||
271 | } | |||
272 | /* C is now the first non-space. */ | |||
273 | h = HASH (h, c)((c) + ((h) << (7) | (h) >> ((sizeof (unsigned) * 8) - (7)))); | |||
274 | } | |||
275 | else | |||
276 | while ((c = *p++) != '\n') | |||
277 | h = HASH (h, c)((c) + ((h) << (7) | (h) >> ((sizeof (unsigned) * 8) - (7)))); | |||
278 | } | |||
279 | hashing_done:; | |||
280 | ||||
281 | bucket = &buckets[h % nbuckets]; | |||
282 | length = (char const *) p - ip - 1; | |||
283 | ||||
284 | if ((char const *) p == bufend | |||
285 | && current->missing_newline | |||
286 | && ROBUST_OUTPUT_STYLE (output_style)((output_style) != OUTPUT_ED && (output_style) != OUTPUT_FORWARD_ED )) | |||
287 | { | |||
288 | /* This line is incomplete. If this is significant, | |||
289 | put the line into bucket[-1]. */ | |||
290 | if (! (ignore_space_change_flag | ignore_all_space_flag)) | |||
291 | bucket = &buckets[-1]; | |||
292 | ||||
293 | /* Omit the inserted newline when computing linbuf later. */ | |||
294 | p--; | |||
295 | bufend = suffix_begin = (char const *) p; | |||
296 | } | |||
297 | ||||
298 | for (i = *bucket; ; i = eqs[i].next) | |||
299 | if (!i) | |||
300 | { | |||
301 | /* Create a new equivalence class in this bucket. */ | |||
302 | i = eqs_index++; | |||
303 | if (i == eqs_alloc) | |||
304 | eqs = (struct equivclass *) | |||
305 | xrealloc (eqs, (eqs_alloc*=2) * sizeof(*eqs)); | |||
306 | eqs[i].next = *bucket; | |||
307 | eqs[i].hash = h; | |||
308 | eqs[i].line = ip; | |||
309 | eqs[i].length = length; | |||
310 | *bucket = i; | |||
311 | break; | |||
312 | } | |||
313 | else if (eqs[i].hash == h) | |||
314 | { | |||
315 | char const *eqline = eqs[i].line; | |||
316 | ||||
317 | /* Reuse existing equivalence class if the lines are identical. | |||
318 | This detects the common case of exact identity | |||
319 | faster than complete comparison would. */ | |||
320 | if (eqs[i].length == length && memcmp (eqline, ip, length) == 0) | |||
321 | break; | |||
322 | ||||
323 | /* Reuse existing class if line_cmp reports the lines equal. */ | |||
324 | if (use_line_cmp && line_cmp (eqline, ip) == 0) | |||
325 | break; | |||
326 | } | |||
327 | ||||
328 | /* Maybe increase the size of the line table. */ | |||
329 | if (line == alloc_lines) | |||
330 | { | |||
331 | /* Double (alloc_lines - linbuf_base) by adding to alloc_lines. */ | |||
332 | alloc_lines = 2 * alloc_lines - linbuf_base; | |||
333 | cureqs = (int *) xrealloc (cureqs, alloc_lines * sizeof (*cureqs)); | |||
334 | linbuf = (char const **) xrealloc (linbuf + linbuf_base, | |||
335 | (alloc_lines - linbuf_base) | |||
336 | * sizeof (*linbuf)) | |||
337 | - linbuf_base; | |||
338 | } | |||
339 | linbuf[line] = ip; | |||
340 | cureqs[line] = i; | |||
341 | ++line; | |||
342 | } | |||
343 | ||||
344 | current->buffered_lines = line; | |||
345 | ||||
346 | for (i = 0; ; i++) | |||
347 | { | |||
348 | /* Record the line start for lines in the suffix that we care about. | |||
349 | Record one more line start than lines, | |||
350 | so that we can compute the length of any buffered line. */ | |||
351 | if (line == alloc_lines) | |||
352 | { | |||
353 | /* Double (alloc_lines - linbuf_base) by adding to alloc_lines. */ | |||
354 | alloc_lines = 2 * alloc_lines - linbuf_base; | |||
355 | linbuf = (char const **) xrealloc (linbuf + linbuf_base, | |||
356 | (alloc_lines - linbuf_base) | |||
357 | * sizeof (*linbuf)) | |||
358 | - linbuf_base; | |||
359 | } | |||
360 | linbuf[line] = (char const *) p; | |||
361 | ||||
362 | if ((char const *) p == bufend) | |||
363 | break; | |||
364 | ||||
365 | if (context <= i && no_diff_means_no_output) | |||
366 | break; | |||
367 | ||||
368 | line++; | |||
369 | ||||
370 | while (*p++ != '\n') | |||
371 | ; | |||
372 | } | |||
373 | ||||
374 | /* Done with cache in local variables. */ | |||
375 | current->linbuf = linbuf; | |||
376 | current->valid_lines = line; | |||
377 | current->alloc_lines = alloc_lines; | |||
378 | current->equivs = cureqs; | |||
379 | equivs = eqs; | |||
380 | equivs_alloc = eqs_alloc; | |||
381 | equivs_index = eqs_index; | |||
382 | } | |||
383 | ||||
384 | /* Prepare the end of the text. Make sure it's initialized. | |||
385 | Make sure text ends in a newline, | |||
386 | but remember that we had to add one. */ | |||
387 | ||||
388 | static void | |||
389 | prepare_text_end (current) | |||
390 | struct file_data *current; | |||
391 | { | |||
392 | size_t buffered_chars = current->buffered_chars; | |||
393 | char *p = current->buffer; | |||
394 | ||||
395 | if (buffered_chars == 0 || p[buffered_chars - 1] == '\n') | |||
396 | current->missing_newline = 0; | |||
397 | else | |||
398 | { | |||
399 | p[buffered_chars++] = '\n'; | |||
400 | current->buffered_chars = buffered_chars; | |||
401 | current->missing_newline = 1; | |||
402 | } | |||
403 | ||||
404 | /* Don't use uninitialized storage when planting or using sentinels. */ | |||
405 | if (p) | |||
406 | bzero (p + buffered_chars, sizeof (word))memset (p + buffered_chars, 0, sizeof (int)); | |||
407 | } | |||
408 | ||||
409 | /* Given a vector of two file_data objects, find the identical | |||
410 | prefixes and suffixes of each object. */ | |||
411 | ||||
412 | static void | |||
413 | find_identical_ends (filevec) | |||
414 | struct file_data filevec[]; | |||
415 | { | |||
416 | wordint *w0, *w1; | |||
417 | char *p0, *p1, *buffer0, *buffer1; | |||
418 | char const *end0, *beg0; | |||
419 | char const **linbuf0, **linbuf1; | |||
420 | int i, lines; | |||
421 | size_t n0, n1, tem; | |||
422 | int alloc_lines0, alloc_lines1; | |||
423 | int buffered_prefix, prefix_count, prefix_mask; | |||
424 | ||||
425 | slurp (&filevec[0]); | |||
426 | if (filevec[0].desc != filevec[1].desc) | |||
| ||||
427 | slurp (&filevec[1]); | |||
428 | else | |||
429 | { | |||
430 | filevec[1].buffer = filevec[0].buffer; | |||
431 | filevec[1].bufsize = filevec[0].bufsize; | |||
432 | filevec[1].buffered_chars = filevec[0].buffered_chars; | |||
433 | } | |||
434 | for (i = 0; i < 2; i++) | |||
435 | prepare_text_end (&filevec[i]); | |||
436 | ||||
437 | /* Find identical prefix. */ | |||
438 | ||||
439 | p0 = buffer0 = filevec[0].buffer; | |||
440 | p1 = buffer1 = filevec[1].buffer; | |||
441 | ||||
442 | n0 = filevec[0].buffered_chars; | |||
443 | n1 = filevec[1].buffered_chars; | |||
444 | ||||
445 | if (p0
| |||
446 | /* The buffers are the same; sentinels won't work. */ | |||
447 | p0 = p1 += n1; | |||
448 | else | |||
449 | { | |||
450 | /* Insert end sentinels, in this case characters that are guaranteed | |||
451 | to make the equality test false, and thus terminate the loop. */ | |||
452 | ||||
453 | if (n0
| |||
454 | p0[n0] = ~p1[n0]; | |||
455 | else | |||
456 | p1[n1] = ~p0[n1]; | |||
| ||||
457 | ||||
458 | /* Loop until first mismatch, or to the sentinel characters. */ | |||
459 | ||||
460 | /* Compare a word at a time for speed. */ | |||
461 | w0 = (wordint *) p0; | |||
462 | w1 = (wordint *) p1; | |||
463 | while (*w0++ == *w1++) | |||
464 | ; | |||
465 | --w0, --w1; | |||
466 | ||||
467 | /* Do the last few bytes of comparison a byte at a time. */ | |||
468 | p0 = (char *) w0; | |||
469 | p1 = (char *) w1; | |||
470 | while (*p0++ == *p1++) | |||
471 | ; | |||
472 | --p0, --p1; | |||
473 | ||||
474 | /* Don't mistakenly count missing newline as part of prefix. */ | |||
475 | if (ROBUST_OUTPUT_STYLE (output_style)((output_style) != OUTPUT_ED && (output_style) != OUTPUT_FORWARD_ED ) | |||
476 | && (buffer0 + n0 - filevec[0].missing_newline < p0) | |||
477 | != | |||
478 | (buffer1 + n1 - filevec[1].missing_newline < p1)) | |||
479 | --p0, --p1; | |||
480 | } | |||
481 | ||||
482 | /* Now P0 and P1 point at the first nonmatching characters. */ | |||
483 | ||||
484 | /* Skip back to last line-beginning in the prefix, | |||
485 | and then discard up to HORIZON_LINES lines from the prefix. */ | |||
486 | i = horizon_lines; | |||
487 | while (p0 != buffer0 && (p0[-1] != '\n' || i--)) | |||
488 | --p0, --p1; | |||
489 | ||||
490 | /* Record the prefix. */ | |||
491 | filevec[0].prefix_end = p0; | |||
492 | filevec[1].prefix_end = p1; | |||
493 | ||||
494 | /* Find identical suffix. */ | |||
495 | ||||
496 | /* P0 and P1 point beyond the last chars not yet compared. */ | |||
497 | p0 = buffer0 + n0; | |||
498 | p1 = buffer1 + n1; | |||
499 | ||||
500 | if (! ROBUST_OUTPUT_STYLE (output_style)((output_style) != OUTPUT_ED && (output_style) != OUTPUT_FORWARD_ED ) | |||
501 | || filevec[0].missing_newline == filevec[1].missing_newline) | |||
502 | { | |||
503 | end0 = p0; /* Addr of last char in file 0. */ | |||
504 | ||||
505 | /* Get value of P0 at which we should stop scanning backward: | |||
506 | this is when either P0 or P1 points just past the last char | |||
507 | of the identical prefix. */ | |||
508 | beg0 = filevec[0].prefix_end + (n0 < n1 ? 0 : n0 - n1); | |||
509 | ||||
510 | /* Scan back until chars don't match or we reach that point. */ | |||
511 | while (p0 != beg0) | |||
512 | if (*--p0 != *--p1) | |||
513 | { | |||
514 | /* Point at the first char of the matching suffix. */ | |||
515 | ++p0, ++p1; | |||
516 | beg0 = p0; | |||
517 | break; | |||
518 | } | |||
519 | ||||
520 | /* Are we at a line-beginning in both files? If not, add the rest of | |||
521 | this line to the main body. Discard up to HORIZON_LINES lines from | |||
522 | the identical suffix. Also, discard one extra line, | |||
523 | because shift_boundaries may need it. */ | |||
524 | i = horizon_lines + !((buffer0 == p0 || p0[-1] == '\n') | |||
525 | && | |||
526 | (buffer1 == p1 || p1[-1] == '\n')); | |||
527 | while (i-- && p0 != end0) | |||
528 | while (*p0++ != '\n') | |||
529 | ; | |||
530 | ||||
531 | p1 += p0 - beg0; | |||
532 | } | |||
533 | ||||
534 | /* Record the suffix. */ | |||
535 | filevec[0].suffix_begin = p0; | |||
536 | filevec[1].suffix_begin = p1; | |||
537 | ||||
538 | /* Calculate number of lines of prefix to save. | |||
539 | ||||
540 | prefix_count == 0 means save the whole prefix; | |||
541 | we need this with for options like -D that output the whole file. | |||
542 | We also need it for options like -F that output some preceding line; | |||
543 | at least we will need to find the last few lines, | |||
544 | but since we don't know how many, it's easiest to find them all. | |||
545 | ||||
546 | Otherwise, prefix_count != 0. Save just prefix_count lines at start | |||
547 | of the line buffer; they'll be moved to the proper location later. | |||
548 | Handle 1 more line than the context says (because we count 1 too many), | |||
549 | rounded up to the next power of 2 to speed index computation. */ | |||
550 | ||||
551 | if (no_diff_means_no_output && ! function_regexp_list) | |||
552 | { | |||
553 | for (prefix_count = 1; prefix_count < context + 1; prefix_count *= 2) | |||
554 | ; | |||
555 | prefix_mask = prefix_count - 1; | |||
556 | alloc_lines0 | |||
557 | = prefix_count | |||
558 | + GUESS_LINES (0, 0, p0 - filevec[0].prefix_end)(((p0 - filevec[0].prefix_end) - (0)) / ((0) < 10 ? 32 : ( 0) / ((0)-1)) + 5) | |||
559 | + context; | |||
560 | } | |||
561 | else | |||
562 | { | |||
563 | prefix_count = 0; | |||
564 | prefix_mask = ~0; | |||
565 | alloc_lines0 = GUESS_LINES (0, 0, n0)(((n0) - (0)) / ((0) < 10 ? 32 : (0) / ((0)-1)) + 5); | |||
566 | } | |||
567 | ||||
568 | lines = 0; | |||
569 | linbuf0 = (char const **) xmalloc (alloc_lines0 * sizeof (*linbuf0)); | |||
570 | ||||
571 | /* If the prefix is needed, find the prefix lines. */ | |||
572 | if (! (no_diff_means_no_output | |||
573 | && filevec[0].prefix_end == p0 | |||
574 | && filevec[1].prefix_end == p1)) | |||
575 | { | |||
576 | p0 = buffer0; | |||
577 | end0 = filevec[0].prefix_end; | |||
578 | while (p0 != end0) | |||
579 | { | |||
580 | int l = lines++ & prefix_mask; | |||
581 | if (l == alloc_lines0) | |||
582 | linbuf0 = (char const **) xrealloc (linbuf0, (alloc_lines0 *= 2) | |||
583 | * sizeof(*linbuf0)); | |||
584 | linbuf0[l] = p0; | |||
585 | while (*p0++ != '\n') | |||
586 | ; | |||
587 | } | |||
588 | } | |||
589 | buffered_prefix = prefix_count && context < lines ? context : lines; | |||
590 | ||||
591 | /* Allocate line buffer 1. */ | |||
592 | tem = prefix_count ? filevec[1].suffix_begin - buffer1 : n1; | |||
593 | ||||
594 | alloc_lines1 | |||
595 | = (buffered_prefix | |||
596 | + GUESS_LINES (lines, filevec[1].prefix_end - buffer1, tem)(((tem) - (filevec[1].prefix_end - buffer1)) / ((lines) < 10 ? 32 : (filevec[1].prefix_end - buffer1) / ((lines)-1)) + 5) | |||
597 | + context); | |||
598 | linbuf1 = (char const **) xmalloc (alloc_lines1 * sizeof (*linbuf1)); | |||
599 | ||||
600 | if (buffered_prefix != lines) | |||
601 | { | |||
602 | /* Rotate prefix lines to proper location. */ | |||
603 | for (i = 0; i < buffered_prefix; i++) | |||
604 | linbuf1[i] = linbuf0[(lines - context + i) & prefix_mask]; | |||
605 | for (i = 0; i < buffered_prefix; i++) | |||
606 | linbuf0[i] = linbuf1[i]; | |||
607 | } | |||
608 | ||||
609 | /* Initialize line buffer 1 from line buffer 0. */ | |||
610 | for (i = 0; i < buffered_prefix; i++) | |||
611 | linbuf1[i] = linbuf0[i] - buffer0 + buffer1; | |||
612 | ||||
613 | /* Record the line buffer, adjusted so that | |||
614 | linbuf*[0] points at the first differing line. */ | |||
615 | filevec[0].linbuf = linbuf0 + buffered_prefix; | |||
616 | filevec[1].linbuf = linbuf1 + buffered_prefix; | |||
617 | filevec[0].linbuf_base = filevec[1].linbuf_base = - buffered_prefix; | |||
618 | filevec[0].alloc_lines = alloc_lines0 - buffered_prefix; | |||
619 | filevec[1].alloc_lines = alloc_lines1 - buffered_prefix; | |||
620 | filevec[0].prefix_lines = filevec[1].prefix_lines = lines; | |||
621 | } | |||
622 | ||||
623 | /* Largest primes less than some power of two, for nbuckets. Values range | |||
624 | from useful to preposterous. If one of these numbers isn't prime | |||
625 | after all, don't blame it on me, blame it on primes (6) . . . */ | |||
626 | static int const primes[] = | |||
627 | { | |||
628 | 509, | |||
629 | 1021, | |||
630 | 2039, | |||
631 | 4093, | |||
632 | 8191, | |||
633 | 16381, | |||
634 | 32749, | |||
635 | #if 32767 < INT_MAX2147483647 | |||
636 | 65521, | |||
637 | 131071, | |||
638 | 262139, | |||
639 | 524287, | |||
640 | 1048573, | |||
641 | 2097143, | |||
642 | 4194301, | |||
643 | 8388593, | |||
644 | 16777213, | |||
645 | 33554393, | |||
646 | 67108859, /* Preposterously large . . . */ | |||
647 | 134217689, | |||
648 | 268435399, | |||
649 | 536870909, | |||
650 | 1073741789, | |||
651 | 2147483647, | |||
652 | #endif | |||
653 | 0 | |||
654 | }; | |||
655 | ||||
656 | /* Given a vector of two file_data objects, read the file associated | |||
657 | with each one, and build the table of equivalence classes. | |||
658 | Return 1 if either file appears to be a binary file. | |||
659 | If PRETEND_BINARY is nonzero, pretend they are binary regardless. */ | |||
660 | ||||
661 | int | |||
662 | read_files (filevec, pretend_binary) | |||
663 | struct file_data filevec[]; | |||
664 | int pretend_binary; | |||
665 | { | |||
666 | int i; | |||
667 | int skip_test = always_text_flag | pretend_binary; | |||
668 | int appears_binary = pretend_binary | sip (&filevec[0], skip_test); | |||
669 | ||||
670 | if (filevec[0].desc != filevec[1].desc) | |||
671 | appears_binary |= sip (&filevec[1], skip_test | appears_binary); | |||
672 | else | |||
673 | { | |||
674 | filevec[1].buffer = filevec[0].buffer; | |||
675 | filevec[1].bufsize = filevec[0].bufsize; | |||
676 | filevec[1].buffered_chars = filevec[0].buffered_chars; | |||
677 | } | |||
678 | if (appears_binary) | |||
679 | { | |||
680 | #if HAVE_SETMODE0 | |||
681 | setmode (filevec[0].desc, O_BINARY); | |||
682 | setmode (filevec[1].desc, O_BINARY); | |||
683 | #endif | |||
684 | return 1; | |||
685 | } | |||
686 | ||||
687 | find_identical_ends (filevec); | |||
688 | ||||
689 | equivs_alloc = filevec[0].alloc_lines + filevec[1].alloc_lines + 1; | |||
690 | equivs = (struct equivclass *) xmalloc (equivs_alloc * sizeof (struct equivclass)); | |||
691 | /* Equivalence class 0 is permanently safe for lines that were not | |||
692 | hashed. Real equivalence classes start at 1. */ | |||
693 | equivs_index = 1; | |||
694 | ||||
695 | for (i = 0; primes[i] < equivs_alloc / 3; i++) | |||
696 | if (! primes[i]) | |||
697 | abort (); | |||
698 | nbuckets = primes[i]; | |||
699 | ||||
700 | buckets = (int *) xmalloc ((nbuckets + 1) * sizeof (*buckets)); | |||
701 | bzero (buckets++, (nbuckets + 1) * sizeof (*buckets))memset (buckets++, 0, (nbuckets + 1) * sizeof (*buckets)); | |||
702 | ||||
703 | for (i = 0; i < 2; i++) | |||
704 | find_and_hash_each_line (&filevec[i]); | |||
705 | ||||
706 | filevec[0].equiv_max = filevec[1].equiv_max = equivs_index; | |||
707 | ||||
708 | free (equivs); | |||
709 | free (buckets - 1); | |||
710 | ||||
711 | return 0; | |||
712 | } |