21    59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
25 #include <file-type.h>
29 /* Rotate an unsigned value to the left.  */
30 #define ROL(v, n) ((v) << (n) | (v) >> (sizeof (v) * CHAR_BIT - (n)))
51 /* Hash-table: array of buckets, each being a chain of equivalence classes.
52    buckets[-1] is reserved for incomplete lines.  */
55 /* Number of buckets in the hash table array, not counting buckets[-1].  */
59    The bucket-chains go through the elements in this array.
72 file_block_read (struct file_data *current, size_t size)  in file_block_read()  argument
74   if (size && ! current->eof)  in file_block_read()
76       size_t s = block_read (current->desc,  in file_block_read()
77 			     FILE_BUFFER (current) + current->buffered, size);  in file_block_read()
79 	pfatal_with_name (current->name);  in file_block_read()
80       current->buffered += s;  in file_block_read()
81       current->eof = s < size;  in file_block_read()
92 /* Get ready to read the current file.
97 sip (struct file_data *current, bool skip_test)  in sip()  argument
100   if (current->desc < 0)  in sip()
103       current->bufsize = sizeof (word);  in sip()
104       current->buffer = xmalloc (current->bufsize);  in sip()
108       current->bufsize = buffer_lcm (sizeof (word),  in sip()
109 				     STAT_BLOCKSIZE (current->stat),  in sip()
110 				     PTRDIFF_MAX - 2 * sizeof (word));  in sip()
111       current->buffer = xmalloc (current->bufsize);  in sip()
117 	  bool was_binary = set_binary_mode (current->desc, true);  in sip()
119 	  file_block_read (current, current->bufsize);  in sip()
120 	  buffered = current->buffered;  in sip()
129 	      if (lseek (current->desc, - buffered, SEEK_CUR) == -1)  in sip()
130 		pfatal_with_name (current->name);  in sip()
131 	      set_binary_mode (current->desc, false);  in sip()
132 	      current->buffered = 0;  in sip()
133 	      current->eof = false;  in sip()
136 	  return binary_file_p (current->buffer, buffered);  in sip()
140   current->buffered = 0;  in sip()
141   current->eof = false;  in sip()
145 /* Slurp the rest of the current file completely into memory.  */
148 slurp (struct file_data *current)  in slurp()  argument
152   if (current->desc < 0)  in slurp()
158   if (S_ISREG (current->stat.st_mode))  in slurp()
164 	 plus word-alignment since we want the buffer word-aligned.  */  in slurp()
165       size_t file_size = current->stat.st_size;  in slurp()
166       cc = file_size + 2 * sizeof (word) - file_size % sizeof (word);  in slurp()
167       if (file_size != current->stat.st_size || cc < file_size  in slurp()
171       if (current->bufsize < cc)  in slurp()
173 	  current->bufsize = cc;  in slurp()
174 	  current->buffer = xrealloc (current->buffer, cc);  in slurp()
181       if (current->buffered <= file_size)  in slurp()
183 	  file_block_read (current, file_size + 1 - current->buffered);  in slurp()
184 	  if (current->buffered <= file_size)  in slurp()
192   file_block_read (current, current->bufsize - current->buffered);  in slurp()
194   if (current->buffered)  in slurp()
196       while (current->buffered == current->bufsize)  in slurp()
198 	  if (PTRDIFF_MAX / 2 - sizeof (word) < current->bufsize)  in slurp()
200 	  current->bufsize *= 2;  in slurp()
201 	  current->buffer = xrealloc (current->buffer, current->bufsize);  in slurp()
202 	  file_block_read (current, current->bufsize - current->buffered);  in slurp()
206 	 sentinel, plus word-alignment.  */  in slurp()
207       cc = current->buffered + 2 * sizeof (word);  in slurp()
208       current->bufsize = cc - cc % sizeof (word);  in slurp()
209       current->buffer = xrealloc (current->buffer, current->bufsize);  in slurp()
217 find_and_hash_each_line (struct file_data *current)  in find_and_hash_each_line()  argument
220   char const *p = current->prefix_end;  in find_and_hash_each_line()
225   /* Cache often-used quantities in local variables to help the compiler.  */  in find_and_hash_each_line()
226   char const **linbuf = current->linbuf;  in find_and_hash_each_line()
227   lin alloc_lines = current->alloc_lines;  in find_and_hash_each_line()
229   lin linbuf_base = current->linbuf_base;  in find_and_hash_each_line()
234   char const *suffix_begin = current->suffix_begin;  in find_and_hash_each_line()
235   char const *bufend = FILE_BUFFER (current) + current->buffered;  in find_and_hash_each_line()
270 		/* C is now the first non-space.  */  in find_and_hash_each_line()
285 		      column -= 0 < column;  in find_and_hash_each_line()
290 		      repetitions = tabsize - column % tabsize;  in find_and_hash_each_line()
308 		  while (--repetitions != 0);  in find_and_hash_each_line()
340 		/* C is now the first non-space.  */  in find_and_hash_each_line()
355 		      column -= 0 < column;  in find_and_hash_each_line()
360 		      repetitions = tabsize - column % tabsize;  in find_and_hash_each_line()
377 		  while (--repetitions != 0);  in find_and_hash_each_line()
391       length = p - ip - 1;  in find_and_hash_each_line()
394 	  && current->missing_newline  in find_and_hash_each_line()
398 	     put the line into buckets[-1].  */  in find_and_hash_each_line()
400 	    bucket = &buckets[-1];  in find_and_hash_each_line()
403 	  p--;  in find_and_hash_each_line()
452 	  /* Double (alloc_lines - linbuf_base) by adding to alloc_lines.  */  in find_and_hash_each_line()
454 	      || PTRDIFF_MAX / sizeof *cureqs <= 2 * alloc_lines - linbuf_base  in find_and_hash_each_line()
455 	      || PTRDIFF_MAX / sizeof *linbuf <= alloc_lines - linbuf_base)  in find_and_hash_each_line()
457 	  alloc_lines = 2 * alloc_lines - linbuf_base;  in find_and_hash_each_line()
461 			     (alloc_lines - linbuf_base) * sizeof *linbuf);  in find_and_hash_each_line()
462 	  linbuf -= linbuf_base;  in find_and_hash_each_line()
469   current->buffered_lines = line;  in find_and_hash_each_line()
478 	  /* Double (alloc_lines - linbuf_base) by adding to alloc_lines.  */  in find_and_hash_each_line()
480 	      || PTRDIFF_MAX / sizeof *cureqs <= 2 * alloc_lines - linbuf_base  in find_and_hash_each_line()
481 	      || PTRDIFF_MAX / sizeof *linbuf <= alloc_lines - linbuf_base)  in find_and_hash_each_line()
483 	  alloc_lines = 2 * alloc_lines - linbuf_base;  in find_and_hash_each_line()
486 			     (alloc_lines - linbuf_base) * sizeof *linbuf);  in find_and_hash_each_line()
487 	  linbuf -= linbuf_base;  in find_and_hash_each_line()
504   current->linbuf = linbuf;  in find_and_hash_each_line()
505   current->valid_lines = line;  in find_and_hash_each_line()
506   current->alloc_lines = alloc_lines;  in find_and_hash_each_line()
507   current->equivs = cureqs;  in find_and_hash_each_line()
519 prepare_text (struct file_data *current)  in prepare_text()  argument
521   size_t buffered = current->buffered;  in prepare_text()
522   char *p = FILE_BUFFER (current);  in prepare_text()
525   if (buffered == 0 || p[buffered - 1] == '\n')  in prepare_text()
526     current->missing_newline = false;  in prepare_text()
530       current->missing_newline = true;  in prepare_text()
548       buffered -= src - dst;  in prepare_text()
551   current->buffered = buffered;  in prepare_text()
561   size_t guessed_bytes_per_line = n < 10 ? 32 : s / (n - 1);  in guess_lines()
563   return MIN (guessed_lines, PTRDIFF_MAX / (2 * sizeof (char *) + 1) - 5) + 5;  in guess_lines()
633 	  && ((buffer0 + n0 - filevec[0].missing_newline < p0)  in find_identical_ends()
635 	      (buffer1 + n1 - filevec[1].missing_newline < p1)))  in find_identical_ends()
636 	p0--, p1--;  in find_identical_ends()
641   /* Skip back to last line-beginning in the prefix,  in find_identical_ends()
644   while (p0 != buffer0 && (p0[-1] != '\n' || i--))  in find_identical_ends()
645     p0--, p1--;  in find_identical_ends()
665       beg0 = filevec[0].prefix_end + (n0 < n1 ? 0 : n0 - n1);  in find_identical_ends()
668       for (; p0 != beg0; p0--, p1--)  in find_identical_ends()
676       /* Are we at a line-beginning in both files?  If not, add the rest of  in find_identical_ends()
680       i = horizon_lines + !((buffer0 == p0 || p0[-1] == '\n')  in find_identical_ends()
682 			    (buffer1 == p1 || p1[-1] == '\n'));  in find_identical_ends()
683       while (i-- && p0 != end0)  in find_identical_ends()
687       p1 += p0 - beg0;  in find_identical_ends()
697      we need this for options like -D that output the whole file,  in find_identical_ends()
699      We also need it for options like -F that output some preceding line;  in find_identical_ends()
711       middle_guess = guess_lines (0, 0, p0 - filevec[0].prefix_end);  in find_identical_ends()
712       suffix_guess = guess_lines (0, 0, buffer0 + n0 - p0);  in find_identical_ends()
724   prefix_mask = prefix_count - 1;  in find_identical_ends()
754   middle_guess = guess_lines (lines, p0 - buffer0, p1 - filevec[1].prefix_end);  in find_identical_ends()
755   suffix_guess = guess_lines (lines, p0 - buffer0, buffer1 + n1 - p1);  in find_identical_ends()
764       /* Rotate prefix lines to proper location.  */  in find_identical_ends()
766 	linbuf1[i] = linbuf0[(lines - context + i) & prefix_mask];  in find_identical_ends()
773     linbuf1[i] = linbuf0[i] - buffer0 + buffer1;  in find_identical_ends()
779   filevec[0].linbuf_base = filevec[1].linbuf_base = - buffered_prefix;  in find_identical_ends()
780   filevec[0].alloc_lines = alloc_lines0 - buffered_prefix;  in find_identical_ends()
781   filevec[1].alloc_lines = alloc_lines1 - buffered_prefix;  in find_identical_ends()
785 /* If 1 < k, then (2**k - prime_offset[k]) is the largest prime less
844   nbuckets = ((size_t) 1 << i) - prime_offset[i];  in read_files()
856   free (buckets - 1);  in read_files()