joachim99@52: /* File I/O for GNU DIFF.
joachim99@52: 
joachim99@52:    Modified for KDiff3 by Joachim Eibl 2003.
joachim99@53:    The original file was part of GNU DIFF.
joachim99@52: 
joachim99@52:    Copyright (C) 1988, 1989, 1992, 1993, 1994, 1995, 1998, 2001, 2002
joachim99@52:    Free Software Foundation, Inc.
joachim99@52: 
joachim99@52:    GNU DIFF is free software; you can redistribute it and/or modify
joachim99@52:    it under the terms of the GNU General Public License as published by
joachim99@52:    the Free Software Foundation; either version 2, or (at your option)
joachim99@52:    any later version.
joachim99@52: 
joachim99@52:    GNU DIFF is distributed in the hope that it will be useful,
joachim99@52:    but WITHOUT ANY WARRANTY; without even the implied warranty of
joachim99@52:    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
joachim99@52:    GNU General Public License for more details.
joachim99@52: 
joachim99@52:    You should have received a copy of the GNU General Public License
joachim99@52:    along with this program; see the file COPYING.
joachim99@52:    If not, write to the Free Software Foundation,
joachim99@52:    59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
joachim99@52: 
joachim99@52: #include "gnudiff_diff.h"
joachim99@52: #include <stdlib.h>
joachim99@52: 
joachim99@52: /* Rotate an unsigned value to the left.  */
joachim99@52: #define ROL(v, n) ((v) << (n) | (v) >> (sizeof (v) * CHAR_BIT - (n)))
joachim99@52: 
joachim99@52: /* Given a hash value and a new character, return a new hash value.  */
joachim99@52: #define HASH(h, c) ((c) + ROL (h, 7))
joachim99@52: 
joachim99@52: /* The type of a hash value.  */
joachim99@52: typedef size_t hash_value;
joachim99@52: verify (hash_value_is_unsigned, ! TYPE_SIGNED (hash_value));
joachim99@52: 
joachim99@52: /* Lines are put into equivalence classes of lines that match in lines_differ.
joachim99@52:    Each equivalence class is represented by one of these structures,
joachim99@52:    but only while the classes are being computed.
joachim99@52:    Afterward, each class is represented by a number.  */
joachim99@52: struct equivclass
joachim99@52: {
joachim99@52:   lin next;		/* Next item in this bucket.  */
joachim99@52:   hash_value hash;	/* Hash of lines in this class.  */
joachim99@52:   char const *line;	/* A line that fits this class.  */
joachim99@52:   size_t length;	/* That line's length, not counting its newline.  */
joachim99@52: };
joachim99@52: 
joachim99@52: /* Hash-table: array of buckets, each being a chain of equivalence classes.
joachim99@52:    buckets[-1] is reserved for incomplete lines.  */
joachim99@52: static lin *buckets;
joachim99@52: 
joachim99@52: /* Number of buckets in the hash table array, not counting buckets[-1].  */
joachim99@52: static size_t nbuckets;
joachim99@52: 
joachim99@52: /* Array in which the equivalence classes are allocated.
joachim99@52:    The bucket-chains go through the elements in this array.
joachim99@52:    The number of an equivalence class is its index in this array.  */
joachim99@52: static struct equivclass *equivs;
joachim99@52: 
joachim99@52: /* Index of first free element in the array `equivs'.  */
joachim99@52: static lin equivs_index;
joachim99@52: 
joachim99@52: /* Number of elements allocated in the array `equivs'.  */
joachim99@52: static lin equivs_alloc;
joachim99@52: 
joachim99@52: 
joachim99@52: /* Check for binary files and compare them for exact identity.  */
joachim99@52: 
joachim99@52: /* Return 1 if BUF contains a non text character.
joachim99@52:    SIZE is the number of characters in BUF.  */
joachim99@52: 
joachim99@52: #define binary_file_p(buf, size) (memchr (buf, 0, size) != 0)
joachim99@52: 
joachim99@52: 
joachim99@52: /* Split the file into lines, simultaneously computing the equivalence
joachim99@52:    class for each line.  */
joachim99@52: 
joachim99@53: void GnuDiff::find_and_hash_each_line (struct file_data *current)
joachim99@52: {
joachim99@52:   hash_value h;
joachim99@52:   unsigned char const *p = (unsigned char const *) current->prefix_end;
joachim99@52:   unsigned char c;
joachim99@52:   lin i, *bucket;
joachim99@52:   size_t length;
joachim99@52: 
joachim99@52:   /* Cache often-used quantities in local variables to help the compiler.  */
joachim99@52:   char const **linbuf = current->linbuf;
joachim99@52:   lin alloc_lines = current->alloc_lines;
joachim99@52:   lin line = 0;
joachim99@52:   lin linbuf_base = current->linbuf_base;
joachim99@52:   lin *cureqs = (lin*)xmalloc (alloc_lines * sizeof *cureqs);
joachim99@52:   struct equivclass *eqs = equivs;
joachim99@52:   lin eqs_index = equivs_index;
joachim99@52:   lin eqs_alloc = equivs_alloc;
joachim99@52:   char const *suffix_begin = current->suffix_begin;
joachim99@52:   char const *bufend = FILE_BUFFER (current) + current->buffered;
joachim99@52:   bool diff_length_compare_anyway =
joachim99@52:     ignore_white_space != IGNORE_NO_WHITE_SPACE || bIgnoreNumbers;
joachim99@52:   bool same_length_diff_contents_compare_anyway =
joachim99@52:     diff_length_compare_anyway | ignore_case;
joachim99@52: 
joachim99@52:   while ((char const *) p < suffix_begin)
joachim99@52:     {
joachim99@52:       char const *ip = (char const *) p;
joachim99@52: 
joachim99@52:       h = 0;
joachim99@52: 
joachim99@52:       /* Hash this line until we find a newline.  */
joachim99@52:       if (ignore_case)
joachim99@52: 	switch (ignore_white_space)
joachim99@52: 	  {
joachim99@52: 	  case IGNORE_ALL_SPACE:
joachim99@52: 	    while ((c = *p++) != '\n')
joachim99@52: 	      if (! (ISSPACE (c) || bIgnoreNumbers && (isdigit( c ) || c=='-' || c=='.' ) ))
joachim99@52: 		h = HASH (h, TOLOWER (c));
joachim99@52: 	    break;
joachim99@52: 
joachim99@52: 	  case IGNORE_SPACE_CHANGE:
joachim99@52: 	    while ((c = *p++) != '\n')
joachim99@52: 	      {
joachim99@52: 		if (ISSPACE (c))
joachim99@52: 		  {
joachim99@52: 		    do
joachim99@52: 		      if ((c = *p++) == '\n')
joachim99@52: 			goto hashing_done;
joachim99@52: 		    while (ISSPACE (c));
joachim99@52: 
joachim99@52: 		    h = HASH (h, ' ');
joachim99@52: 		  }
joachim99@52: 
joachim99@52: 		/* C is now the first non-space.  */
joachim99@52: 		h = HASH (h, TOLOWER (c));
joachim99@52: 	      }
joachim99@52: 	    break;
joachim99@52: 
joachim99@52: 	  case IGNORE_TAB_EXPANSION:
joachim99@52: 	    {
joachim99@52: 	      size_t column = 0;
joachim99@52: 	      while ((c = *p++) != '\n')
joachim99@52: 		{
joachim99@52: 		  int repetitions = 1;
joachim99@52: 
joachim99@52: 		  switch (c)
joachim99@52: 		    {
joachim99@52: 		    case '\b':
joachim99@52: 		      column -= 0 < column;
joachim99@52: 		      break;
joachim99@52: 
joachim99@52: 		    case '\t':
joachim99@52: 		      c = ' ';
joachim99@52: 		      repetitions = TAB_WIDTH - column % TAB_WIDTH;
joachim99@52: 		      column += repetitions;
joachim99@52: 		      break;
joachim99@52: 
joachim99@52: 		    case '\r':
joachim99@52: 		      column = 0;
joachim99@52: 		      break;
joachim99@52: 
joachim99@52: 		    default:
joachim99@52: 		      c = TOLOWER (c);
joachim99@52: 		      column++;
joachim99@52: 		      break;
joachim99@52: 		    }
joachim99@52: 
joachim99@52: 		  do
joachim99@52: 		    h = HASH (h, c);
joachim99@52: 		  while (--repetitions != 0);
joachim99@52: 		}
joachim99@52: 	    }
joachim99@52: 	    break;
joachim99@52: 
joachim99@52: 	  default:
joachim99@52: 	    while ((c = *p++) != '\n')
joachim99@52: 	      h = HASH (h, TOLOWER (c));
joachim99@52: 	    break;
joachim99@52: 	  }
joachim99@52:       else
joachim99@52: 	switch (ignore_white_space)
joachim99@52: 	  {
joachim99@52: 	  case IGNORE_ALL_SPACE:
joachim99@52: 	    while ((c = *p++) != '\n')
joachim99@52: 	      if (! (ISSPACE (c)|| bIgnoreNumbers && (isdigit( c ) || c=='-' || c=='.' ) ))
joachim99@52: 		h = HASH (h, c);
joachim99@52: 	    break;
joachim99@52: 
joachim99@52: 	  case IGNORE_SPACE_CHANGE:
joachim99@52: 	    while ((c = *p++) != '\n')
joachim99@52: 	      {
joachim99@52: 		if (ISSPACE (c))
joachim99@52: 		  {
joachim99@52: 		    do
joachim99@52: 		      if ((c = *p++) == '\n')
joachim99@52: 			goto hashing_done;
joachim99@52: 		    while (ISSPACE (c));
joachim99@52: 
joachim99@52: 		    h = HASH (h, ' ');
joachim99@52: 		  }
joachim99@52: 
joachim99@52: 		/* C is now the first non-space.  */
joachim99@52: 		h = HASH (h, c);
joachim99@52: 	      }
joachim99@52: 	    break;
joachim99@52: 
joachim99@52: 	  case IGNORE_TAB_EXPANSION:
joachim99@52: 	    {
joachim99@52: 	      size_t column = 0;
joachim99@52: 	      while ((c = *p++) != '\n')
joachim99@52: 		{
joachim99@52: 		  int repetitions = 1;
joachim99@52: 
joachim99@52: 		  switch (c)
joachim99@52: 		    {
joachim99@52: 		    case '\b':
joachim99@52: 		      column -= 0 < column;
joachim99@52: 		      break;
joachim99@52: 
joachim99@52: 		    case '\t':
joachim99@52: 		      c = ' ';
joachim99@52: 		      repetitions = TAB_WIDTH - column % TAB_WIDTH;
joachim99@52: 		      column += repetitions;
joachim99@52: 		      break;
joachim99@52: 
joachim99@52: 		    case '\r':
joachim99@52: 		      column = 0;
joachim99@52: 		      break;
joachim99@52: 
joachim99@52: 		    default:
joachim99@52: 		      column++;
joachim99@52: 		      break;
joachim99@52: 		    }
joachim99@52: 
joachim99@52: 		  do
joachim99@52: 		    h = HASH (h, c);
joachim99@52: 		  while (--repetitions != 0);
joachim99@52: 		}
joachim99@52: 	    }
joachim99@52: 	    break;
joachim99@52: 
joachim99@52: 	  default:
joachim99@52: 	    while ((c = *p++) != '\n')
joachim99@52: 	      h = HASH (h, c);
joachim99@52: 	    break;
joachim99@52: 	  }
joachim99@52: 
joachim99@52:    hashing_done:;
joachim99@52: 
joachim99@52:       bucket = &buckets[h % nbuckets];
joachim99@52:       length = (char const *) p - ip - 1;
joachim99@52: 
joachim99@52:       if ((char const *) p == bufend
joachim99@52: 	  && current->missing_newline
joachim99@52: 	  && ROBUST_OUTPUT_STYLE (output_style))
joachim99@52: 	{
joachim99@52: 	  /* This line is incomplete.  If this is significant,
joachim99@52: 	     put the line into buckets[-1].  */
joachim99@52: 	  if (ignore_white_space < IGNORE_SPACE_CHANGE)
joachim99@52: 	    bucket = &buckets[-1];
joachim99@52: 
joachim99@52: 	  /* Omit the inserted newline when computing linbuf later.  */
joachim99@52: 	  p--;
joachim99@52: 	  bufend = suffix_begin = (char const *) p;
joachim99@52: 	}
joachim99@52: 
joachim99@52:       for (i = *bucket;  ;  i = eqs[i].next)
joachim99@52: 	if (!i)
joachim99@52: 	  {
joachim99@52: 	    /* Create a new equivalence class in this bucket.  */
joachim99@52: 	    i = eqs_index++;
joachim99@52: 	    if (i == eqs_alloc)
joachim99@52: 	      {
joachim99@66: 		if ((lin)(PTRDIFF_MAX / (2 * sizeof *eqs)) <= eqs_alloc)
joachim99@52: 		  xalloc_die ();
joachim99@52: 		eqs_alloc *= 2;
joachim99@52: 		eqs = (equivclass*)xrealloc (eqs, eqs_alloc * sizeof *eqs);
joachim99@52: 	      }
joachim99@52: 	    eqs[i].next = *bucket;
joachim99@52: 	    eqs[i].hash = h;
joachim99@52: 	    eqs[i].line = ip;
joachim99@52: 	    eqs[i].length = length;
joachim99@52: 	    *bucket = i;
joachim99@52: 	    break;
joachim99@52: 	  }
joachim99@52: 	else if (eqs[i].hash == h)
joachim99@52: 	  {
joachim99@52: 	    char const *eqline = eqs[i].line;
joachim99@52: 
joachim99@52: 	    /* Reuse existing class if lines_differ reports the lines
joachim99@52:                equal.  */
joachim99@52: 	    if (eqs[i].length == length)
joachim99@52: 	      {
joachim99@52: 		/* Reuse existing equivalence class if the lines are identical.
joachim99@52: 		   This detects the common case of exact identity
joachim99@52: 		   faster than lines_differ would.  */
joachim99@52: 		if (memcmp (eqline, ip, length) == 0)
joachim99@52: 		  break;
joachim99@52: 		if (!same_length_diff_contents_compare_anyway)
joachim99@52: 		  continue;
joachim99@52: 	      }
joachim99@52: 	    else if (!diff_length_compare_anyway)
joachim99@52: 	      continue;
joachim99@52: 
joachim99@52: 	    if (! lines_differ (eqline, ip))
joachim99@52: 	      break;
joachim99@52: 	  }
joachim99@52: 
joachim99@52:       /* Maybe increase the size of the line table.  */
joachim99@52:       if (line == alloc_lines)
joachim99@52: 	{
joachim99@52: 	  /* Double (alloc_lines - linbuf_base) by adding to alloc_lines.  */
joachim99@66: 	  if ((lin)(PTRDIFF_MAX / 3) <= alloc_lines
joachim99@66: 	      || (lin)(PTRDIFF_MAX / sizeof *cureqs) <= 2 * alloc_lines - linbuf_base
joachim99@66: 	      || (lin)(PTRDIFF_MAX / sizeof *linbuf) <= alloc_lines - linbuf_base)
joachim99@52: 	    xalloc_die ();
joachim99@52: 	  alloc_lines = 2 * alloc_lines - linbuf_base;
joachim99@52: 	  cureqs =(lin*) xrealloc (cureqs, alloc_lines * sizeof *cureqs);
joachim99@52: 	  linbuf += linbuf_base;
joachim99@52: 	  linbuf = (const char**) xrealloc (linbuf,
joachim99@52: 			     (alloc_lines - linbuf_base) * sizeof *linbuf);
joachim99@52: 	  linbuf -= linbuf_base;
joachim99@52: 	}
joachim99@52:       linbuf[line] = ip;
joachim99@52:       cureqs[line] = i;
joachim99@52:       ++line;
joachim99@52:     }
joachim99@52: 
joachim99@52:   current->buffered_lines = line;
joachim99@52: 
joachim99@52:   for (i = 0;  ;  i++)
joachim99@52:     {
joachim99@52:       /* Record the line start for lines in the suffix that we care about.
joachim99@52: 	 Record one more line start than lines,
joachim99@52: 	 so that we can compute the length of any buffered line.  */
joachim99@52:       if (line == alloc_lines)
joachim99@52: 	{
joachim99@52: 	  /* Double (alloc_lines - linbuf_base) by adding to alloc_lines.  */
joachim99@66: 	  if ((lin)(PTRDIFF_MAX / 3) <= alloc_lines
joachim99@66: 	      || (lin)(PTRDIFF_MAX / sizeof *cureqs) <= 2 * alloc_lines - linbuf_base
joachim99@66: 	      || (lin)(PTRDIFF_MAX / sizeof *linbuf) <= alloc_lines - linbuf_base)
joachim99@52: 	    xalloc_die ();
joachim99@52: 	  alloc_lines = 2 * alloc_lines - linbuf_base;
joachim99@52: 	  linbuf += linbuf_base;
joachim99@52: 	  linbuf = (const char**)xrealloc (linbuf,
joachim99@52: 			     (alloc_lines - linbuf_base) * sizeof *linbuf);
joachim99@52: 	  linbuf -= linbuf_base;
joachim99@52: 	}
joachim99@52:       linbuf[line] = (char const *) p;
joachim99@52: 
joachim99@52:       if ((char const *) p == bufend)
joachim99@52: 	break;
joachim99@52: 
joachim99@52:       if (context <= i && no_diff_means_no_output)
joachim99@52: 	break;
joachim99@52: 
joachim99@52:       line++;
joachim99@52: 
joachim99@52:       while (*p++ != '\n')
joachim99@52: 	continue;
joachim99@52:     }
joachim99@52: 
joachim99@52:   /* Done with cache in local variables.  */
joachim99@52:   current->linbuf = linbuf;
joachim99@52:   current->valid_lines = line;
joachim99@52:   current->alloc_lines = alloc_lines;
joachim99@52:   current->equivs = cureqs;
joachim99@52:   equivs = eqs;
joachim99@52:   equivs_alloc = eqs_alloc;
joachim99@52:   equivs_index = eqs_index;
joachim99@52: }
joachim99@52: 
joachim99@52: /* Prepare the text.  Make sure the text end is initialized.
joachim99@52:    Make sure text ends in a newline,
joachim99@52:    but remember that we had to add one.
joachim99@52:    Strip trailing CRs, if that was requested.  */
joachim99@52: 
joachim99@53: void GnuDiff::prepare_text (struct file_data *current)
joachim99@52: {
joachim99@52:   size_t buffered = current->buffered;
joachim99@52:   char *p = FILE_BUFFER (current);
joachim99@52:   char *dst;
joachim99@52: 
joachim99@52:   if (buffered == 0 || p[buffered - 1] == '\n')
joachim99@52:     current->missing_newline = 0;
joachim99@52:   else
joachim99@52:     {
joachim99@52:       p[buffered++] = '\n';
joachim99@52:       current->missing_newline = 1;
joachim99@52:     }
joachim99@52: 
joachim99@52:   if (!p)
joachim99@52:     return;
joachim99@52: 
joachim99@52:   /* Don't use uninitialized storage when planting or using sentinels.  */
joachim99@52:   memset (p + buffered, 0, sizeof (word));
joachim99@52: 
joachim99@52:   if (strip_trailing_cr && (dst = (char*)memchr (p, '\r', buffered)))
joachim99@52:     {
joachim99@52:       char const *src = dst;
joachim99@52:       char const *srclim = p + buffered;
joachim99@52: 
joachim99@52:       do
joachim99@52: 	dst += ! ((*dst = *src++) == '\r' && *src == '\n');
joachim99@52:       while (src < srclim);
joachim99@52: 
joachim99@52:       buffered -= src - dst;
joachim99@52:     }
joachim99@52: 
joachim99@52:   current->buffered = buffered;
joachim99@52: }
joachim99@52: 
joachim99@52: /* We have found N lines in a buffer of size S; guess the
joachim99@52:    proportionate number of lines that will be found in a buffer of
joachim99@52:    size T.  However, do not guess a number of lines so large that the
joachim99@52:    resulting line table might cause overflow in size calculations.  */
joachim99@52: static lin
joachim99@52: guess_lines (lin n, size_t s, size_t t)
joachim99@52: {
joachim99@52:   size_t guessed_bytes_per_line = n < 10 ? 32 : s / (n - 1);
joachim99@52:   lin guessed_lines = MAX (1, t / guessed_bytes_per_line);
joachim99@66:   return MIN (guessed_lines, (lin)(PTRDIFF_MAX / (2 * sizeof (char *) + 1) - 5)) + 5;
joachim99@52: }
joachim99@52: 
joachim99@52: /* Given a vector of two file_data objects, find the identical
joachim99@52:    prefixes and suffixes of each object.  */
joachim99@52: 
joachim99@53: void GnuDiff::find_identical_ends (struct file_data filevec[])
joachim99@52: {
joachim99@52:   word *w0, *w1;
joachim99@52:   char *p0, *p1, *buffer0, *buffer1;
joachim99@52:   char const *end0, *beg0;
joachim99@52:   char const **linbuf0, **linbuf1;
joachim99@52:   lin i, lines;
joachim99@52:   size_t n0, n1;
joachim99@52:   lin alloc_lines0, alloc_lines1;
joachim99@52:   lin buffered_prefix, prefix_count, prefix_mask;
joachim99@52:   lin middle_guess, suffix_guess;
joachim99@52: 
joachim99@52:   prepare_text (&filevec[0]);
joachim99@52:   prepare_text (&filevec[1]);
joachim99@52: 
joachim99@52:   /* Find identical prefix.  */
joachim99@52: 
joachim99@52:   w0 = filevec[0].buffer;
joachim99@52:   w1 = filevec[1].buffer;
joachim99@52:   p0 = buffer0 = (char *) w0;
joachim99@52:   p1 = buffer1 = (char *) w1;
joachim99@52:   n0 = filevec[0].buffered;
joachim99@52:   n1 = filevec[1].buffered;
joachim99@52: 
joachim99@52:   if (p0 == p1)
joachim99@52:     /* The buffers are the same; sentinels won't work.  */
joachim99@52:     p0 = p1 += n1;
joachim99@52:   else
joachim99@52:     {
joachim99@52:       /* Insert end sentinels, in this case characters that are guaranteed
joachim99@52: 	 to make the equality test false, and thus terminate the loop.  */
joachim99@52: 
joachim99@52:       if (n0 < n1)
joachim99@52: 	p0[n0] = ~p1[n0];
joachim99@52:       else
joachim99@52: 	p1[n1] = ~p0[n1];
joachim99@52: 
joachim99@52:       /* Loop until first mismatch, or to the sentinel characters.  */
joachim99@52: 
joachim99@52:       /* Compare a word at a time for speed.  */
joachim99@52:       while (*w0 == *w1)
joachim99@52: 	w0++, w1++;
joachim99@52: 
joachim99@52:       /* Do the last few bytes of comparison a byte at a time.  */
joachim99@52:       p0 = (char *) w0;
joachim99@52:       p1 = (char *) w1;
joachim99@52:       while (*p0 == *p1)
joachim99@52: 	p0++, p1++;
joachim99@52: 
joachim99@52:       /* Don't mistakenly count missing newline as part of prefix.  */
joachim99@52:       if (ROBUST_OUTPUT_STYLE (output_style)
joachim99@52: 	  && ((buffer0 + n0 - filevec[0].missing_newline < p0)
joachim99@52: 	      !=
joachim99@52: 	      (buffer1 + n1 - filevec[1].missing_newline < p1)))
joachim99@52: 	p0--, p1--;
joachim99@52:     }
joachim99@52: 
joachim99@52:   /* Now P0 and P1 point at the first nonmatching characters.  */
joachim99@52: 
joachim99@52:   /* Skip back to last line-beginning in the prefix,
joachim99@52:      and then discard up to HORIZON_LINES lines from the prefix.  */
joachim99@52:   i = horizon_lines;
joachim99@52:   while (p0 != buffer0 && (p0[-1] != '\n' || i--))
joachim99@52:     p0--, p1--;
joachim99@52: 
joachim99@52:   /* Record the prefix.  */
joachim99@52:   filevec[0].prefix_end = p0;
joachim99@52:   filevec[1].prefix_end = p1;
joachim99@52: 
joachim99@52:   /* Find identical suffix.  */
joachim99@52: 
joachim99@52:   /* P0 and P1 point beyond the last chars not yet compared.  */
joachim99@52:   p0 = buffer0 + n0;
joachim99@52:   p1 = buffer1 + n1;
joachim99@52: 
joachim99@52:   if (! ROBUST_OUTPUT_STYLE (output_style)
joachim99@52:       || filevec[0].missing_newline == filevec[1].missing_newline)
joachim99@52:     {
joachim99@52:       end0 = p0;	/* Addr of last char in file 0.  */
joachim99@52: 
joachim99@52:       /* Get value of P0 at which we should stop scanning backward:
joachim99@52: 	 this is when either P0 or P1 points just past the last char
joachim99@52: 	 of the identical prefix.  */
joachim99@52:       beg0 = filevec[0].prefix_end + (n0 < n1 ? 0 : n0 - n1);
joachim99@52: 
joachim99@52:       /* Scan back until chars don't match or we reach that point.  */
joachim99@52:       for (; p0 != beg0; p0--, p1--)
joachim99@52: 	if (*p0 != *p1)
joachim99@52: 	  {
joachim99@52: 	    /* Point at the first char of the matching suffix.  */
joachim99@52: 	    beg0 = p0;
joachim99@52: 	    break;
joachim99@52: 	  }
joachim99@52: 
joachim99@52:       /* Are we at a line-beginning in both files?  If not, add the rest of
joachim99@52: 	 this line to the main body.  Discard up to HORIZON_LINES lines from
joachim99@52: 	 the identical suffix.  Also, discard one extra line,
joachim99@52: 	 because shift_boundaries may need it.  */
joachim99@52:       i = horizon_lines + !((buffer0 == p0 || p0[-1] == '\n')
joachim99@52: 			    &&
joachim99@52: 			    (buffer1 == p1 || p1[-1] == '\n'));
joachim99@52:       while (i-- && p0 != end0)
joachim99@52: 	while (*p0++ != '\n')
joachim99@52: 	  continue;
joachim99@52: 
joachim99@52:       p1 += p0 - beg0;
joachim99@52:     }
joachim99@52: 
joachim99@52:   /* Record the suffix.  */
joachim99@52:   filevec[0].suffix_begin = p0;
joachim99@52:   filevec[1].suffix_begin = p1;
joachim99@52: 
joachim99@52:   /* Calculate number of lines of prefix to save.
joachim99@52: 
joachim99@52:      prefix_count == 0 means save the whole prefix;
joachim99@52:      we need this for options like -D that output the whole file,
joachim99@52:      or for enormous contexts (to avoid worrying about arithmetic overflow).
joachim99@52:      We also need it for options like -F that output some preceding line;
joachim99@52:      at least we will need to find the last few lines,
joachim99@52:      but since we don't know how many, it's easiest to find them all.
joachim99@52: 
joachim99@52:      Otherwise, prefix_count != 0.  Save just prefix_count lines at start
joachim99@52:      of the line buffer; they'll be moved to the proper location later.
joachim99@52:      Handle 1 more line than the context says (because we count 1 too many),
joachim99@52:      rounded up to the next power of 2 to speed index computation.  */
joachim99@52: 
joachim99@52:   if (no_diff_means_no_output
joachim99@66:       && context < (lin)(LIN_MAX / 4) && context < (lin)(n0))
joachim99@52:     {
joachim99@52:       middle_guess = guess_lines (0, 0, p0 - filevec[0].prefix_end);
joachim99@52:       suffix_guess = guess_lines (0, 0, buffer0 + n0 - p0);
joachim99@52:       for (prefix_count = 1;  prefix_count <= context;  prefix_count *= 2)
joachim99@52: 	continue;
joachim99@52:       alloc_lines0 = (prefix_count + middle_guess
joachim99@52: 		      + MIN (context, suffix_guess));
joachim99@52:     }
joachim99@52:   else
joachim99@52:     {
joachim99@52:       prefix_count = 0;
joachim99@52:       alloc_lines0 = guess_lines (0, 0, n0);
joachim99@52:     }
joachim99@52: 
joachim99@52:   prefix_mask = prefix_count - 1;
joachim99@52:   lines = 0;
joachim99@52:   linbuf0 = (const char**) xmalloc (alloc_lines0 * sizeof *linbuf0);
joachim99@52:   p0 = buffer0;
joachim99@52: 
joachim99@52:   /* If the prefix is needed, find the prefix lines.  */
joachim99@52:   if (! (no_diff_means_no_output
joachim99@52: 	 && filevec[0].prefix_end == p0
joachim99@52: 	 && filevec[1].prefix_end == p1))
joachim99@52:     {
joachim99@52:       end0 = filevec[0].prefix_end;
joachim99@52:       while (p0 != end0)
joachim99@52: 	{
joachim99@52: 	  lin l = lines++ & prefix_mask;
joachim99@52: 	  if (l == alloc_lines0)
joachim99@52: 	    {
joachim99@66: 	      if ((lin)(PTRDIFF_MAX / (2 * sizeof *linbuf0)) <= alloc_lines0)
joachim99@52: 		xalloc_die ();
joachim99@52: 	      alloc_lines0 *= 2;
joachim99@52: 	      linbuf0 = (const char**) xrealloc (linbuf0, alloc_lines0 * sizeof *linbuf0);
joachim99@52: 	    }
joachim99@52: 	  linbuf0[l] = p0;
joachim99@52: 	  while (*p0++ != '\n')
joachim99@52: 	    continue;
joachim99@52: 	}
joachim99@52:     }
joachim99@52:   buffered_prefix = prefix_count && context < lines ? context : lines;
joachim99@52: 
joachim99@52:   /* Allocate line buffer 1.  */
joachim99@52: 
joachim99@52:   middle_guess = guess_lines (lines, p0 - buffer0, p1 - filevec[1].prefix_end);
joachim99@52:   suffix_guess = guess_lines (lines, p0 - buffer0, buffer1 + n1 - p1);
joachim99@52:   alloc_lines1 = buffered_prefix + middle_guess + MIN (context, suffix_guess);
joachim99@52:   if (alloc_lines1 < buffered_prefix
joachim99@66:       || (lin)(PTRDIFF_MAX / sizeof *linbuf1) <= alloc_lines1)
joachim99@52:     xalloc_die ();
joachim99@52:   linbuf1 = (const char**)xmalloc (alloc_lines1 * sizeof *linbuf1);
joachim99@52: 
joachim99@52:   if (buffered_prefix != lines)
joachim99@52:     {
joachim99@52:       /* Rotate prefix lines to proper location.  */
joachim99@52:       for (i = 0;  i < buffered_prefix;  i++)
joachim99@52: 	linbuf1[i] = linbuf0[(lines - context + i) & prefix_mask];
joachim99@52:       for (i = 0;  i < buffered_prefix;  i++)
joachim99@52: 	linbuf0[i] = linbuf1[i];
joachim99@52:     }
joachim99@52: 
joachim99@52:   /* Initialize line buffer 1 from line buffer 0.  */
joachim99@52:   for (i = 0; i < buffered_prefix; i++)
joachim99@52:     linbuf1[i] = linbuf0[i] - buffer0 + buffer1;
joachim99@52: 
joachim99@52:   /* Record the line buffer, adjusted so that
joachim99@52:      linbuf[0] points at the first differing line.  */
joachim99@52:   filevec[0].linbuf = linbuf0 + buffered_prefix;
joachim99@52:   filevec[1].linbuf = linbuf1 + buffered_prefix;
joachim99@52:   filevec[0].linbuf_base = filevec[1].linbuf_base = - buffered_prefix;
joachim99@52:   filevec[0].alloc_lines = alloc_lines0 - buffered_prefix;
joachim99@52:   filevec[1].alloc_lines = alloc_lines1 - buffered_prefix;
joachim99@52:   filevec[0].prefix_lines = filevec[1].prefix_lines = lines;
joachim99@52: }
joachim99@52: 
joachim99@52: /* If 1 < k, then (2**k - prime_offset[k]) is the largest prime less
joachim99@52:    than 2**k.  This table is derived from Chris K. Caldwell's list
joachim99@52:    <http://www.utm.edu/research/primes/lists/2small/>.  */
joachim99@52: 
joachim99@52: static unsigned char const prime_offset[] =
joachim99@52: {
joachim99@52:   0, 0, 1, 1, 3, 1, 3, 1, 5, 3, 3, 9, 3, 1, 3, 19, 15, 1, 5, 1, 3, 9, 3,
joachim99@52:   15, 3, 39, 5, 39, 57, 3, 35, 1, 5, 9, 41, 31, 5, 25, 45, 7, 87, 21,
joachim99@52:   11, 57, 17, 55, 21, 115, 59, 81, 27, 129, 47, 111, 33, 55, 5, 13, 27,
joachim99@52:   55, 93, 1, 57, 25
joachim99@52: };
joachim99@52: 
joachim99@52: /* Verify that this host's size_t is not too wide for the above table.  */
joachim99@52: 
joachim99@52: verify (enough_prime_offsets,
joachim99@52: 	sizeof (size_t) * CHAR_BIT <= sizeof prime_offset);
joachim99@52: 
joachim99@52: /* Given a vector of two file_data objects, read the file associated
joachim99@52:    with each one, and build the table of equivalence classes.
joachim99@52:    Return nonzero if either file appears to be a binary file.
joachim99@52:    If PRETEND_BINARY is nonzero, pretend they are binary regardless.  */
joachim99@52: 
joachim99@52: bool
joachim99@53: GnuDiff::read_files (struct file_data filevec[], bool /*pretend_binary*/)
joachim99@52: {
joachim99@52:   int i;
joachim99@52: 
joachim99@52:   find_identical_ends (filevec);
joachim99@52: 
joachim99@52:   equivs_alloc = filevec[0].alloc_lines + filevec[1].alloc_lines + 1;
joachim99@66:   if ((lin)(PTRDIFF_MAX / sizeof *equivs) <= equivs_alloc)
joachim99@52:     xalloc_die ();
joachim99@52:   equivs = (equivclass*)xmalloc (equivs_alloc * sizeof *equivs);
joachim99@52:   /* Equivalence class 0 is permanently safe for lines that were not
joachim99@52:      hashed.  Real equivalence classes start at 1.  */
joachim99@52:   equivs_index = 1;
joachim99@52: 
joachim99@52:   /* Allocate (one plus) a prime number of hash buckets.  Use a prime
joachim99@52:      number between 1/3 and 2/3 of the value of equiv_allocs,
joachim99@52:      approximately.  */
joachim99@52:   for (i = 9;  1 << i < equivs_alloc / 3; i++)
joachim99@52:     continue;
joachim99@52:   nbuckets = ((size_t) 1 << i) - prime_offset[i];
joachim99@52:   if (PTRDIFF_MAX / sizeof *buckets <= nbuckets)
joachim99@52:     xalloc_die ();
joachim99@52:   buckets = (lin*)zalloc ((nbuckets + 1) * sizeof *buckets);
joachim99@52:   buckets++;
joachim99@52: 
joachim99@52:   for (i = 0; i < 2; i++)
joachim99@52:     find_and_hash_each_line (&filevec[i]);
joachim99@52: 
joachim99@52:   filevec[0].equiv_max = filevec[1].equiv_max = equivs_index;
joachim99@52: 
joachim99@52:   free (equivs);
joachim99@52:   free (buckets - 1);
joachim99@52: 
joachim99@52:   return 0;
joachim99@52: }