changeset 52:ba22ec30aa4e

GNU-Diff-Algorithms: Adapted for KDiff3-0.9.80

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/kdiff3/src/gnudiff_analyze.cpp	Tue Dec 09 20:34:32 2003 +0000
@@ -0,0 +1,1037 @@
+/* Analyze file differences for GNU DIFF.
+
+   Modified for KDiff3 by Joachim Eibl 2003.
+
+   Copyright (C) 1988, 1989, 1992, 1993, 1994, 1995, 1998, 2001, 2002
+   Free Software Foundation, Inc.
+
+   This file is part of GNU DIFF.
+
+   GNU DIFF is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   GNU DIFF is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; see the file COPYING.
+   If not, write to the Free Software Foundation,
+   59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+/* The basic algorithm is described in:
+   "An O(ND) Difference Algorithm and its Variations", Eugene Myers,
+   Algorithmica Vol. 1 No. 2, 1986, pp. 251-266;
+   see especially section 4.2, which describes the variation used below.
+   Unless the --minimal option is specified, this code uses the TOO_EXPENSIVE
+   heuristic, by Paul Eggert, to limit the cost to O(N**1.5 log N)
+   at the price of producing suboptimal output for large inputs with
+   many differences.
+
+   The basic algorithm was independently discovered as described in:
+   "Algorithms for Approximate String Matching", E. Ukkonen,
+   Information and Control Vol. 64, 1985, pp. 100-118.  */
+
+#define GDIFF_MAIN
+
+#include "gnudiff_diff.h"
+//#include <error.h>
+#include <stdlib.h>
+#include "gnudiff_xalloc.h"
+
+static lin *xvec, *yvec;	/* Vectors being compared. */
+static lin *fdiag;		/* Vector, indexed by diagonal, containing
+				   1 + the X coordinate of the point furthest
+				   along the given diagonal in the forward
+				   search of the edit matrix. */
+static lin *bdiag;		/* Vector, indexed by diagonal, containing
+				   the X coordinate of the point furthest
+				   along the given diagonal in the backward
+				   search of the edit matrix. */
+static lin too_expensive;	/* Edit scripts longer than this are too
+				   expensive to compute.  */
+
+#define SNAKE_LIMIT 20	/* Snakes bigger than this are considered `big'.  */
+namespace GnuDiff {
+
+struct partition
+{
+  lin xmid, ymid;	/* Midpoints of this partition.  */
+  bool lo_minimal;	/* Nonzero if low half will be analyzed minimally.  */
+  bool hi_minimal;	/* Likewise for high half.  */
+};
+
+/* Find the midpoint of the shortest edit script for a specified
+   portion of the two files.
+
+   Scan from the beginnings of the files, and simultaneously from the ends,
+   doing a breadth-first search through the space of edit-sequence.
+   When the two searches meet, we have found the midpoint of the shortest
+   edit sequence.
+
+   If FIND_MINIMAL is nonzero, find the minimal edit script regardless
+   of expense.  Otherwise, if the search is too expensive, use
+   heuristics to stop the search and report a suboptimal answer.
+
+   Set PART->(xmid,ymid) to the midpoint (XMID,YMID).  The diagonal number
+   XMID - YMID equals the number of inserted lines minus the number
+   of deleted lines (counting only lines before the midpoint).
+   Return the approximate edit cost; this is the total number of
+   lines inserted or deleted (counting only lines before the midpoint),
+   unless a heuristic is used to terminate the search prematurely.
+
+   Set PART->lo_minimal to true iff the minimal edit script for the
+   left half of the partition is known; similarly for PART->hi_minimal.
+
+   This function assumes that the first lines of the specified portions
+   of the two files do not match, and likewise that the last lines do not
+   match.  The caller must trim matching lines from the beginning and end
+   of the portions it is going to specify.
+
+   If we return the "wrong" partitions,
+   the worst this can do is cause suboptimal diff output.
+   It cannot cause incorrect diff output.  */
+
+static lin
+diag (lin xoff, lin xlim, lin yoff, lin ylim, bool find_minimal,
+      struct partition *part)
+{
+  lin *const fd = fdiag;	/* Give the compiler a chance. */
+  lin *const bd = bdiag;	/* Additional help for the compiler. */
+  lin const *const xv = xvec;	/* Still more help for the compiler. */
+  lin const *const yv = yvec;	/* And more and more . . . */
+  lin const dmin = xoff - ylim;	/* Minimum valid diagonal. */
+  lin const dmax = xlim - yoff;	/* Maximum valid diagonal. */
+  lin const fmid = xoff - yoff;	/* Center diagonal of top-down search. */
+  lin const bmid = xlim - ylim;	/* Center diagonal of bottom-up search. */
+  lin fmin = fmid, fmax = fmid;	/* Limits of top-down search. */
+  lin bmin = bmid, bmax = bmid;	/* Limits of bottom-up search. */
+  lin c;			/* Cost. */
+  bool odd = (fmid - bmid) & 1;	/* True if southeast corner is on an odd
+				   diagonal with respect to the northwest. */
+
+  fd[fmid] = xoff;
+  bd[bmid] = xlim;
+
+  for (c = 1;; ++c)
+    {
+      lin d;			/* Active diagonal. */
+      bool big_snake = 0;
+
+      /* Extend the top-down search by an edit step in each diagonal. */
+      fmin > dmin ? fd[--fmin - 1] = -1 : ++fmin;
+      fmax < dmax ? fd[++fmax + 1] = -1 : --fmax;
+      for (d = fmax; d >= fmin; d -= 2)
+	{
+	  lin x, y, oldx, tlo = fd[d - 1], thi = fd[d + 1];
+
+	  if (tlo >= thi)
+	    x = tlo + 1;
+	  else
+	    x = thi;
+	  oldx = x;
+	  y = x - d;
+	  while (x < xlim && y < ylim && xv[x] == yv[y])
+	    ++x, ++y;
+	  if (x - oldx > SNAKE_LIMIT)
+	    big_snake = 1;
+	  fd[d] = x;
+	  if (odd && bmin <= d && d <= bmax && bd[d] <= x)
+	    {
+	      part->xmid = x;
+	      part->ymid = y;
+	      part->lo_minimal = part->hi_minimal = 1;
+	      return 2 * c - 1;
+	    }
+	}
+
+      /* Similarly extend the bottom-up search.  */
+      bmin > dmin ? bd[--bmin - 1] = LIN_MAX : ++bmin;
+      bmax < dmax ? bd[++bmax + 1] = LIN_MAX : --bmax;
+      for (d = bmax; d >= bmin; d -= 2)
+	{
+	  lin x, y, oldx, tlo = bd[d - 1], thi = bd[d + 1];
+
+	  if (tlo < thi)
+	    x = tlo;
+	  else
+	    x = thi - 1;
+	  oldx = x;
+	  y = x - d;
+	  while (x > xoff && y > yoff && xv[x - 1] == yv[y - 1])
+	    --x, --y;
+	  if (oldx - x > SNAKE_LIMIT)
+	    big_snake = 1;
+	  bd[d] = x;
+	  if (!odd && fmin <= d && d <= fmax && x <= fd[d])
+	    {
+	      part->xmid = x;
+	      part->ymid = y;
+	      part->lo_minimal = part->hi_minimal = 1;
+	      return 2 * c;
+	    }
+	}
+
+      if (find_minimal)
+	continue;
+
+      /* Heuristic: check occasionally for a diagonal that has made
+	 lots of progress compared with the edit distance.
+	 If we have any such, find the one that has made the most
+	 progress and return it as if it had succeeded.
+
+	 With this heuristic, for files with a constant small density
+	 of changes, the algorithm is linear in the file size.  */
+
+      if (200 < c && big_snake && speed_large_files)
+	{
+	  lin best;
+
+	  best = 0;
+	  for (d = fmax; d >= fmin; d -= 2)
+	    {
+	      lin dd = d - fmid;
+	      lin x = fd[d];
+	      lin y = x - d;
+	      lin v = (x - xoff) * 2 - dd;
+	      if (v > 12 * (c + (dd < 0 ? -dd : dd)))
+		{
+		  if (v > best
+		      && xoff + SNAKE_LIMIT <= x && x < xlim
+		      && yoff + SNAKE_LIMIT <= y && y < ylim)
+		    {
+		      /* We have a good enough best diagonal;
+			 now insist that it end with a significant snake.  */
+		      int k;
+
+		      for (k = 1; xv[x - k] == yv[y - k]; k++)
+			if (k == SNAKE_LIMIT)
+			  {
+			    best = v;
+			    part->xmid = x;
+			    part->ymid = y;
+			    break;
+			  }
+		    }
+		}
+	    }
+	  if (best > 0)
+	    {
+	      part->lo_minimal = 1;
+	      part->hi_minimal = 0;
+	      return 2 * c - 1;
+	    }
+
+	  best = 0;
+	  for (d = bmax; d >= bmin; d -= 2)
+	    {
+	      lin dd = d - bmid;
+	      lin x = bd[d];
+	      lin y = x - d;
+	      lin v = (xlim - x) * 2 + dd;
+	      if (v > 12 * (c + (dd < 0 ? -dd : dd)))
+		{
+		  if (v > best
+		      && xoff < x && x <= xlim - SNAKE_LIMIT
+		      && yoff < y && y <= ylim - SNAKE_LIMIT)
+		    {
+		      /* We have a good enough best diagonal;
+			 now insist that it end with a significant snake.  */
+		      int k;
+
+		      for (k = 0; xv[x + k] == yv[y + k]; k++)
+			if (k == SNAKE_LIMIT - 1)
+			  {
+			    best = v;
+			    part->xmid = x;
+			    part->ymid = y;
+			    break;
+			  }
+		    }
+		}
+	    }
+	  if (best > 0)
+	    {
+	      part->lo_minimal = 0;
+	      part->hi_minimal = 1;
+	      return 2 * c - 1;
+	    }
+	}
+
+      /* Heuristic: if we've gone well beyond the call of duty,
+	 give up and report halfway between our best results so far.  */
+      if (c >= too_expensive)
+	{
+	  lin fxybest, fxbest;
+	  lin bxybest, bxbest;
+
+	  fxbest = bxbest = 0;  /* Pacify `gcc -Wall'.  */
+
+	  /* Find forward diagonal that maximizes X + Y.  */
+	  fxybest = -1;
+	  for (d = fmax; d >= fmin; d -= 2)
+	    {
+	      lin x = MIN (fd[d], xlim);
+	      lin y = x - d;
+	      if (ylim < y)
+		x = ylim + d, y = ylim;
+	      if (fxybest < x + y)
+		{
+		  fxybest = x + y;
+		  fxbest = x;
+		}
+	    }
+
+	  /* Find backward diagonal that minimizes X + Y.  */
+	  bxybest = LIN_MAX;
+	  for (d = bmax; d >= bmin; d -= 2)
+	    {
+	      lin x = MAX (xoff, bd[d]);
+	      lin y = x - d;
+	      if (y < yoff)
+		x = yoff + d, y = yoff;
+	      if (x + y < bxybest)
+		{
+		  bxybest = x + y;
+		  bxbest = x;
+		}
+	    }
+
+	  /* Use the better of the two diagonals.  */
+	  if ((xlim + ylim) - bxybest < fxybest - (xoff + yoff))
+	    {
+	      part->xmid = fxbest;
+	      part->ymid = fxybest - fxbest;
+	      part->lo_minimal = 1;
+	      part->hi_minimal = 0;
+	    }
+	  else
+	    {
+	      part->xmid = bxbest;
+	      part->ymid = bxybest - bxbest;
+	      part->lo_minimal = 0;
+	      part->hi_minimal = 1;
+	    }
+	  return 2 * c - 1;
+	}
+    }
+}
+
+/* Compare in detail contiguous subsequences of the two files
+   which are known, as a whole, to match each other.
+
+   The results are recorded in the vectors files[N].changed, by
+   storing 1 in the element for each line that is an insertion or deletion.
+
+   The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1.
+
+   Note that XLIM, YLIM are exclusive bounds.
+   All line numbers are origin-0 and discarded lines are not counted.
+
+   If FIND_MINIMAL, find a minimal difference no matter how
+   expensive it is.  */
+
+static void
+compareseq (lin xoff, lin xlim, lin yoff, lin ylim, bool find_minimal)
+{
+  lin * const xv = xvec; /* Help the compiler.  */
+  lin * const yv = yvec;
+
+  /* Slide down the bottom initial diagonal. */
+  while (xoff < xlim && yoff < ylim && xv[xoff] == yv[yoff])
+    ++xoff, ++yoff;
+  /* Slide up the top initial diagonal. */
+  while (xlim > xoff && ylim > yoff && xv[xlim - 1] == yv[ylim - 1])
+    --xlim, --ylim;
+
+  /* Handle simple cases. */
+  if (xoff == xlim)
+    while (yoff < ylim)
+      files[1].changed[files[1].realindexes[yoff++]] = 1;
+  else if (yoff == ylim)
+    while (xoff < xlim)
+      files[0].changed[files[0].realindexes[xoff++]] = 1;
+  else
+    {
+      lin c;
+      struct partition part;
+
+      /* Find a point of correspondence in the middle of the files.  */
+
+      c = diag (xoff, xlim, yoff, ylim, find_minimal, &part);
+
+      if (c == 1)
+	{
+	  /* This should be impossible, because it implies that
+	     one of the two subsequences is empty,
+	     and that case was handled above without calling `diag'.
+	     Let's verify that this is true.  */
+	  abort ();
+#if 0
+	  /* The two subsequences differ by a single insert or delete;
+	     record it and we are done.  */
+	  if (part.xmid - part.ymid < xoff - yoff)
+	    files[1].changed[files[1].realindexes[part.ymid - 1]] = 1;
+	  else
+	    files[0].changed[files[0].realindexes[part.xmid]] = 1;
+#endif
+	}
+      else
+	{
+	  /* Use the partitions to split this problem into subproblems.  */
+	  compareseq (xoff, part.xmid, yoff, part.ymid, part.lo_minimal);
+	  compareseq (part.xmid, xlim, part.ymid, ylim, part.hi_minimal);
+	}
+    }
+}
+
+/* Discard lines from one file that have no matches in the other file.
+
+   A line which is discarded will not be considered by the actual
+   comparison algorithm; it will be as if that line were not in the file.
+   The file's `realindexes' table maps virtual line numbers
+   (which don't count the discarded lines) into real line numbers;
+   this is how the actual comparison algorithm produces results
+   that are comprehensible when the discarded lines are counted.
+
+   When we discard a line, we also mark it as a deletion or insertion
+   so that it will be printed in the output.  */
+
+static void
+discard_confusing_lines (struct file_data filevec[])
+{
+  int f;
+  lin i;
+  char *discarded[2];
+  lin *equiv_count[2];
+  lin *p;
+
+  /* Allocate our results.  */
+  p = (lin*)xmalloc ((filevec[0].buffered_lines + filevec[1].buffered_lines)
+	       * (2 * sizeof *p));
+  for (f = 0; f < 2; f++)
+    {
+      filevec[f].undiscarded = p;  p += filevec[f].buffered_lines;
+      filevec[f].realindexes = p;  p += filevec[f].buffered_lines;
+    }
+
+  /* Set up equiv_count[F][I] as the number of lines in file F
+     that fall in equivalence class I.  */
+
+  p = (lin*)zalloc (filevec[0].equiv_max * (2 * sizeof *p));
+  equiv_count[0] = p;
+  equiv_count[1] = p + filevec[0].equiv_max;
+
+  for (i = 0; i < filevec[0].buffered_lines; ++i)
+    ++equiv_count[0][filevec[0].equivs[i]];
+  for (i = 0; i < filevec[1].buffered_lines; ++i)
+    ++equiv_count[1][filevec[1].equivs[i]];
+
+  /* Set up tables of which lines are going to be discarded.  */
+
+  discarded[0] = (char*)zalloc (filevec[0].buffered_lines
+			 + filevec[1].buffered_lines);
+  discarded[1] = discarded[0] + filevec[0].buffered_lines;
+
+  /* Mark to be discarded each line that matches no line of the other file.
+     If a line matches many lines, mark it as provisionally discardable.  */
+
+  for (f = 0; f < 2; f++)
+    {
+      size_t end = filevec[f].buffered_lines;
+      char *discards = discarded[f];
+      lin *counts = equiv_count[1 - f];
+      lin *equivs = filevec[f].equivs;
+      size_t many = 5;
+      size_t tem = end / 64;
+
+      /* Multiply MANY by approximate square root of number of lines.
+	 That is the threshold for provisionally discardable lines.  */
+      while ((tem = tem >> 2) > 0)
+	many *= 2;
+
+      for (i = 0; i < (int)end; i++)
+	{
+	  lin nmatch;
+	  if (equivs[i] == 0)
+	    continue;
+	  nmatch = counts[equivs[i]];
+	  if (nmatch == 0)
+	    discards[i] = 1;
+	  else if (nmatch > (int)many)
+	    discards[i] = 2;
+	}
+    }
+
+  /* Don't really discard the provisional lines except when they occur
+     in a run of discardables, with nonprovisionals at the beginning
+     and end.  */
+
+  for (f = 0; f < 2; f++)
+    {
+      lin end = filevec[f].buffered_lines;
+      register char *discards = discarded[f];
+
+      for (i = 0; i < end; i++)
+	{
+	  /* Cancel provisional discards not in middle of run of discards.  */
+	  if (discards[i] == 2)
+	    discards[i] = 0;
+	  else if (discards[i] != 0)
+	    {
+	      /* We have found a nonprovisional discard.  */
+	      register lin j;
+	      lin length;
+	      lin provisional = 0;
+
+	      /* Find end of this run of discardable lines.
+		 Count how many are provisionally discardable.  */
+	      for (j = i; j < end; j++)
+		{
+		  if (discards[j] == 0)
+		    break;
+		  if (discards[j] == 2)
+		    ++provisional;
+		}
+
+	      /* Cancel provisional discards at end, and shrink the run.  */
+	      while (j > i && discards[j - 1] == 2)
+		discards[--j] = 0, --provisional;
+
+	      /* Now we have the length of a run of discardable lines
+		 whose first and last are not provisional.  */
+	      length = j - i;
+
+	      /* If 1/4 of the lines in the run are provisional,
+		 cancel discarding of all provisional lines in the run.  */
+	      if (provisional * 4 > length)
+		{
+		  while (j > i)
+		    if (discards[--j] == 2)
+		      discards[j] = 0;
+		}
+	      else
+		{
+		  register lin consec;
+		  lin minimum = 1;
+		  lin tem = length >> 2;
+
+		  /* MINIMUM is approximate square root of LENGTH/4.
+		     A subrun of two or more provisionals can stand
+		     when LENGTH is at least 16.
+		     A subrun of 4 or more can stand when LENGTH >= 64.  */
+		  while (0 < (tem >>= 2))
+		    minimum <<= 1;
+		  minimum++;
+
+		  /* Cancel any subrun of MINIMUM or more provisionals
+		     within the larger run.  */
+		  for (j = 0, consec = 0; j < length; j++)
+		    if (discards[i + j] != 2)
+		      consec = 0;
+		    else if (minimum == ++consec)
+		      /* Back up to start of subrun, to cancel it all.  */
+		      j -= consec;
+		    else if (minimum < consec)
+		      discards[i + j] = 0;
+
+		  /* Scan from beginning of run
+		     until we find 3 or more nonprovisionals in a row
+		     or until the first nonprovisional at least 8 lines in.
+		     Until that point, cancel any provisionals.  */
+		  for (j = 0, consec = 0; j < length; j++)
+		    {
+		      if (j >= 8 && discards[i + j] == 1)
+			break;
+		      if (discards[i + j] == 2)
+			consec = 0, discards[i + j] = 0;
+		      else if (discards[i + j] == 0)
+			consec = 0;
+		      else
+			consec++;
+		      if (consec == 3)
+			break;
+		    }
+
+		  /* I advances to the last line of the run.  */
+		  i += length - 1;
+
+		  /* Same thing, from end.  */
+		  for (j = 0, consec = 0; j < length; j++)
+		    {
+		      if (j >= 8 && discards[i - j] == 1)
+			break;
+		      if (discards[i - j] == 2)
+			consec = 0, discards[i - j] = 0;
+		      else if (discards[i - j] == 0)
+			consec = 0;
+		      else
+			consec++;
+		      if (consec == 3)
+			break;
+		    }
+		}
+	    }
+	}
+    }
+
+  /* Actually discard the lines. */
+  for (f = 0; f < 2; f++)
+    {
+      char *discards = discarded[f];
+      lin end = filevec[f].buffered_lines;
+      lin j = 0;
+      for (i = 0; i < end; ++i)
+	if (minimal || discards[i] == 0)
+	  {
+	    filevec[f].undiscarded[j] = filevec[f].equivs[i];
+	    filevec[f].realindexes[j++] = i;
+	  }
+	else
+	  filevec[f].changed[i] = 1;
+      filevec[f].nondiscarded_lines = j;
+    }
+
+  free (discarded[0]);
+  free (equiv_count[0]);
+}
+
+/* Adjust inserts/deletes of identical lines to join changes
+   as much as possible.
+
+   We do something when a run of changed lines include a
+   line at one end and have an excluded, identical line at the other.
+   We are free to choose which identical line is included.
+   `compareseq' usually chooses the one at the beginning,
+   but usually it is cleaner to consider the following identical line
+   to be the "change".  */
+
+static void
+shift_boundaries (struct file_data filevec[])
+{
+  int f;
+
+  for (f = 0; f < 2; f++)
+    {
+      bool *changed = filevec[f].changed;
+      bool const *other_changed = filevec[1 - f].changed;
+      lin const *equivs = filevec[f].equivs;
+      lin i = 0;
+      lin j = 0;
+      lin i_end = filevec[f].buffered_lines;
+
+      while (1)
+	{
+	  lin runlength, start, corresponding;
+
+	  /* Scan forwards to find beginning of another run of changes.
+	     Also keep track of the corresponding point in the other file.  */
+
+	  while (i < i_end && !changed[i])
+	    {
+	      while (other_changed[j++])
+		continue;
+	      i++;
+	    }
+
+	  if (i == i_end)
+	    break;
+
+	  start = i;
+
+	  /* Find the end of this run of changes.  */
+
+	  while (changed[++i])
+	    continue;
+	  while (other_changed[j])
+	    j++;
+
+	  do
+	    {
+	      /* Record the length of this run of changes, so that
+		 we can later determine whether the run has grown.  */
+	      runlength = i - start;
+
+	      /* Move the changed region back, so long as the
+		 previous unchanged line matches the last changed one.
+		 This merges with previous changed regions.  */
+
+	      while (start && equivs[start - 1] == equivs[i - 1])
+		{
+		  changed[--start] = 1;
+		  changed[--i] = 0;
+		  while (changed[start - 1])
+		    start--;
+		  while (other_changed[--j])
+		    continue;
+		}
+
+	      /* Set CORRESPONDING to the end of the changed run, at the last
+		 point where it corresponds to a changed run in the other file.
+		 CORRESPONDING == I_END means no such point has been found.  */
+	      corresponding = other_changed[j - 1] ? i : i_end;
+
+	      /* Move the changed region forward, so long as the
+		 first changed line matches the following unchanged one.
+		 This merges with following changed regions.
+		 Do this second, so that if there are no merges,
+		 the changed region is moved forward as far as possible.  */
+
+	      while (i != i_end && equivs[start] == equivs[i])
+		{
+		  changed[start++] = 0;
+		  changed[i++] = 1;
+		  while (changed[i])
+		    i++;
+		  while (other_changed[++j])
+		    corresponding = i;
+		}
+	    }
+	  while (runlength != i - start);
+
+	  /* If possible, move the fully-merged run of changes
+	     back to a corresponding run in the other file.  */
+
+	  while (corresponding < i)
+	    {
+	      changed[--start] = 1;
+	      changed[--i] = 0;
+	      while (other_changed[--j])
+		continue;
+	    }
+	}
+    }
+}
+
+/* Cons an additional entry onto the front of an edit script OLD.
+   LINE0 and LINE1 are the first affected lines in the two files (origin 0).
+   DELETED is the number of lines deleted here from file 0.
+   INSERTED is the number of lines inserted here in file 1.
+
+   If DELETED is 0 then LINE0 is the number of the line before
+   which the insertion was done; vice versa for INSERTED and LINE1.  */
+
+static struct change *
+add_change (lin line0, lin line1, lin deleted, lin inserted,
+	    struct change *old)
+{
+  struct change *newChange = (change*) xmalloc (sizeof *newChange);
+
+  newChange->line0 = line0;
+  newChange->line1 = line1;
+  newChange->inserted = inserted;
+  newChange->deleted = deleted;
+  newChange->link = old;
+  return newChange;
+}
+
+/* Scan the tables of which lines are inserted and deleted,
+   producing an edit script in reverse order.  */
+
+static struct change *
+build_reverse_script (struct file_data const filevec[])
+{
+  struct change *script = 0;
+  bool *changed0 = filevec[0].changed;
+  bool *changed1 = filevec[1].changed;
+  lin len0 = filevec[0].buffered_lines;
+  lin len1 = filevec[1].buffered_lines;
+
+  /* Note that changedN[len0] does exist, and is 0.  */
+
+  lin i0 = 0, i1 = 0;
+
+  while (i0 < len0 || i1 < len1)
+    {
+      if (changed0[i0] | changed1[i1])
+	{
+	  lin line0 = i0, line1 = i1;
+
+	  /* Find # lines changed here in each file.  */
+	  while (changed0[i0]) ++i0;
+	  while (changed1[i1]) ++i1;
+
+	  /* Record this change.  */
+	  script = add_change (line0, line1, i0 - line0, i1 - line1, script);
+	}
+
+      /* We have reached lines in the two files that match each other.  */
+      i0++, i1++;
+    }
+
+  return script;
+}
+
+/* Scan the tables of which lines are inserted and deleted,
+   producing an edit script in forward order.  */
+
+static struct change *
+build_script (struct file_data const filevec[])
+{
+  struct change *script = 0;
+  bool *changed0 = filevec[0].changed;
+  bool *changed1 = filevec[1].changed;
+  lin i0 = filevec[0].buffered_lines, i1 = filevec[1].buffered_lines;
+
+  /* Note that changedN[-1] does exist, and is 0.  */
+
+  while (i0 >= 0 || i1 >= 0)
+    {
+      if (changed0[i0 - 1] | changed1[i1 - 1])
+	{
+	  lin line0 = i0, line1 = i1;
+
+	  /* Find # lines changed here in each file.  */
+	  while (changed0[i0 - 1]) --i0;
+	  while (changed1[i1 - 1]) --i1;
+
+	  /* Record this change.  */
+	  script = add_change (i0, i1, line0 - i0, line1 - i1, script);
+	}
+
+      /* We have reached lines in the two files that match each other.  */
+      i0--, i1--;
+    }
+
+  return script;
+}
+
+
+/* Report the differences of two files.  */
+struct change* diff_2_files (struct comparison *cmp)
+{
+  lin diags;
+  int f;
+  //struct change *e, *p;
+  struct change *script;
+  int changes;
+
+  read_files (cmp->file, files_can_be_treated_as_binary);
+
+    {
+      /* Allocate vectors for the results of comparison:
+	 a flag for each line of each file, saying whether that line
+	 is an insertion or deletion.
+	 Allocate an extra element, always 0, at each end of each vector.  */
+
+      size_t s = cmp->file[0].buffered_lines + cmp->file[1].buffered_lines + 4;
+      bool *flag_space = (bool*)zalloc (s * sizeof(*flag_space));
+      cmp->file[0].changed = flag_space + 1;
+      cmp->file[1].changed = flag_space + cmp->file[0].buffered_lines + 3;
+
+      /* Some lines are obviously insertions or deletions
+	 because they don't match anything.  Detect them now, and
+	 avoid even thinking about them in the main comparison algorithm.  */
+
+      discard_confusing_lines (cmp->file);
+
+      /* Now do the main comparison algorithm, considering just the
+	 undiscarded lines.  */
+
+      xvec = cmp->file[0].undiscarded;
+      yvec = cmp->file[1].undiscarded;
+      diags = (cmp->file[0].nondiscarded_lines
+	       + cmp->file[1].nondiscarded_lines + 3);
+      fdiag = (lin*)xmalloc (diags * (2 * sizeof *fdiag));
+      bdiag = fdiag + diags;
+      fdiag += cmp->file[1].nondiscarded_lines + 1;
+      bdiag += cmp->file[1].nondiscarded_lines + 1;
+
+      /* Set TOO_EXPENSIVE to be approximate square root of input size,
+	 bounded below by 256.  */
+      too_expensive = 1;
+      for (;  diags != 0;  diags >>= 2)
+	too_expensive <<= 1;
+      too_expensive = MAX (256, too_expensive);
+
+      files[0] = cmp->file[0];
+      files[1] = cmp->file[1];
+
+      compareseq (0, cmp->file[0].nondiscarded_lines,
+		  0, cmp->file[1].nondiscarded_lines, minimal);
+
+      free (fdiag - (cmp->file[1].nondiscarded_lines + 1));
+
+      /* Modify the results slightly to make them prettier
+	 in cases where that can validly be done.  */
+
+      shift_boundaries (cmp->file);
+
+      /* Get the results of comparison in the form of a chain
+	 of `struct change's -- an edit script.  */
+
+      if (output_style == OUTPUT_ED)
+	script = build_reverse_script (cmp->file);
+      else
+	script = build_script (cmp->file);
+
+      changes = (script != 0);
+
+      free (cmp->file[0].undiscarded);
+
+      free (flag_space);
+
+      for (f = 0; f < 2; f++)
+	{
+	  free (cmp->file[f].equivs);
+	  free (cmp->file[f].linbuf + cmp->file[f].linbuf_base);
+	}
+    }
+
+  return script;
+}
+
+inline bool isWhite( char c )
+{
+   return c==' ' || c=='\t' ||  c=='\r';
+}
+
+/* Compare two lines (typically one from each input file)
+   according to the command line options.
+   For efficiency, this is invoked only when the lines do not match exactly
+   but an option like -i might cause us to ignore the difference.
+   Return nonzero if the lines differ.  */
+
+bool
+lines_differ (char const *s1, char const *s2)
+{
+  register unsigned char const *t1 = (unsigned char const *) s1;
+  register unsigned char const *t2 = (unsigned char const *) s2;
+  size_t column = 0;
+
+  while (1)
+    {
+      register unsigned char c1 = *t1++;
+      register unsigned char c2 = *t2++;
+
+      /* Test for exact char equality first, since it's a common case.  */
+      if (c1 != c2)
+	{
+          while ( bIgnoreWhiteSpace && isWhite( c1 )  ||
+                  bIgnoreNumbers    && (isdigit( c1 ) || c1=='-' || c1=='.' ))
+             c1 = *t1++;
+
+          while ( bIgnoreWhiteSpace && isWhite( c2 )  ||
+                  bIgnoreNumbers    && (isdigit( c2 ) || c2=='-' || c2=='.' ))
+             c2 = *t2++;
+
+#if 0
+	  switch (ignore_white_space)
+	    {
+	    case IGNORE_ALL_SPACE:
+	      /* For -w, just skip past any white space.  */
+	      while (ISSPACE (c1) && c1 != '\n') c1 = *t1++;
+	      while (ISSPACE (c2) && c2 != '\n') c2 = *t2++;
+	      break;
+
+	    case IGNORE_SPACE_CHANGE:
+	      /* For -b, advance past any sequence of white space in
+		 line 1 and consider it just one space, or nothing at
+		 all if it is at the end of the line.  */
+	      if (ISSPACE (c1))
+		{
+		  while (c1 != '\n')
+		    {
+		      c1 = *t1++;
+		      if (! ISSPACE (c1))
+			{
+			  --t1;
+			  c1 = ' ';
+			  break;
+			}
+		    }
+		}
+
+	      /* Likewise for line 2.  */
+	      if (ISSPACE (c2))
+		{
+		  while (c2 != '\n')
+		    {
+		      c2 = *t2++;
+		      if (! ISSPACE (c2))
+			{
+			  --t2;
+			  c2 = ' ';
+			  break;
+			}
+		    }
+		}
+
+	      if (c1 != c2)
+		{
+		  /* If we went too far when doing the simple test
+		     for equality, go back to the first non-white-space
+		     character in both sides and try again.  */
+		  if (c2 == ' ' && c1 != '\n'
+		      && (unsigned char const *) s1 + 1 < t1
+		      && ISSPACE (t1[-2]))
+		    {
+		      --t1;
+		      continue;
+		    }
+		  if (c1 == ' ' && c2 != '\n'
+		      && (unsigned char const *) s2 + 1 < t2
+		      && ISSPACE (t2[-2]))
+		    {
+		      --t2;
+		      continue;
+		    }
+		}
+
+	      break;
+
+	    case IGNORE_TAB_EXPANSION:
+	      if ((c1 == ' ' && c2 == '\t')
+		  || (c1 == '\t' && c2 == ' '))
+		{
+		  size_t column2 = column;
+		  for (;; c1 = *t1++)
+		    {
+		      if (c1 == ' ')
+			column++;
+		      else if (c1 == '\t')
+			column += TAB_WIDTH - column % TAB_WIDTH;
+		      else
+			break;
+		    }
+		  for (;; c2 = *t2++)
+		    {
+		      if (c2 == ' ')
+			column2++;
+		      else if (c2 == '\t')
+			column2 += TAB_WIDTH - column2 % TAB_WIDTH;
+		      else
+			break;
+		    }
+		  if (column != column2)
+		    return 1;
+		}
+	      break;
+
+	    case IGNORE_NO_WHITE_SPACE:
+	      break;
+	    }
+#endif
+	  /* Lowercase all letters if -i is specified.  */
+
+	  if (ignore_case)
+	    {
+	      c1 = TOLOWER (c1);
+	      c2 = TOLOWER (c2);
+	    }
+
+	  if (c1 != c2)
+	    break;
+	}
+      if (c1 == '\n')
+	return 0;
+
+      column += c1 == '\t' ? TAB_WIDTH - column % TAB_WIDTH : 1;
+    }
+
+  return 1;
+}
+} // namespace GnuDiff

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/kdiff3/src/gnudiff_diff.h	Tue Dec 09 20:34:32 2003 +0000
@@ -0,0 +1,387 @@
+/* Shared definitions for GNU DIFF
+
+   Modified for KDiff3 by Joachim Eibl 2003.
+
+   Copyright (C) 1988, 1989, 1991, 1992, 1993, 1994, 1995, 1998, 2001,
+   2002 Free Software Foundation, Inc.
+
+   This file is part of GNU DIFF.
+
+   GNU DIFF is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   GNU DIFF is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; see the file COPYING.
+   If not, write to the Free Software Foundation,
+   59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+#include "gnudiff_system.h"
+
+#include <stdio.h>
+
+#define TAB_WIDTH 8
+
+namespace GnuDiff
+{
+
+/* What kind of changes a hunk contains.  */
+enum changes
+{
+  /* No changes: lines common to both files.  */
+  UNCHANGED,
+
+  /* Deletes only: lines taken from just the first file.  */
+  OLD,
+
+  /* Inserts only: lines taken from just the second file.  */
+  NEW,
+
+  /* Both deletes and inserts: a hunk containing both old and new lines.  */
+  CHANGED
+};
+
+/* Variables for command line options */
+
+#ifndef GDIFF_MAIN
+# define XTERN extern
+#else
+# define XTERN
+#endif
+
+enum output_style
+{
+  /* No output style specified.  */
+  OUTPUT_UNSPECIFIED,
+
+  /* Default output style.  */
+  OUTPUT_NORMAL,
+
+  /* Output the differences with lines of context before and after (-c).  */
+  OUTPUT_CONTEXT,
+
+  /* Output the differences in a unified context diff format (-u).  */
+  OUTPUT_UNIFIED,
+
+  /* Output the differences as commands suitable for `ed' (-e).  */
+  OUTPUT_ED,
+
+  /* Output the diff as a forward ed script (-f).  */
+  OUTPUT_FORWARD_ED,
+
+  /* Like -f, but output a count of changed lines in each "command" (-n).  */
+  OUTPUT_RCS,
+
+  /* Output merged #ifdef'd file (-D).  */
+  OUTPUT_IFDEF,
+
+  /* Output sdiff style (-y).  */
+  OUTPUT_SDIFF
+};
+
+/* True for output styles that are robust,
+   i.e. can handle a file that ends in a non-newline.  */
+#define ROBUST_OUTPUT_STYLE(S) ((S) != OUTPUT_ED && (S) != OUTPUT_FORWARD_ED)
+
+XTERN enum output_style output_style;
+
+/* Nonzero if output cannot be generated for identical files.  */
+XTERN bool no_diff_means_no_output;
+
+/* Number of lines of context to show in each set of diffs.
+   This is zero when context is not to be shown.  */
+XTERN lin context;
+
+/* Consider all files as text files (-a).
+   Don't interpret codes over 0177 as implying a "binary file".  */
+XTERN bool text;
+
+/* Number of lines to keep in identical prefix and suffix.  */
+XTERN lin horizon_lines;
+
+/* The significance of white space during comparisons.  */
+XTERN enum
+{
+  /* All white space is significant (the default).  */
+  IGNORE_NO_WHITE_SPACE,
+
+  /* Ignore changes due to tab expansion (-E).  */
+  IGNORE_TAB_EXPANSION,
+
+  /* Ignore changes in horizontal white space (-b).  */
+  IGNORE_SPACE_CHANGE,
+
+  /* Ignore all horizontal white space (-w).  */
+  IGNORE_ALL_SPACE
+} ignore_white_space;
+
+/* Ignore changes that affect only blank lines (-B).  */
+XTERN bool ignore_blank_lines;
+
+/* Ignore changes that affect only numbers. (J. Eibl)  */
+XTERN bool bIgnoreNumbers;
+XTERN bool bIgnoreWhiteSpace;
+
+/* Files can be compared byte-by-byte, as if they were binary.
+   This depends on various options.  */
+XTERN bool files_can_be_treated_as_binary;
+
+/* Ignore differences in case of letters (-i).  */
+XTERN bool ignore_case;
+
+/* Ignore differences in case of letters in file names.  */
+XTERN bool ignore_file_name_case;
+
+/* File labels for `-c' output headers (--label).  */
+XTERN char *file_label[2];
+
+/* Regexp to identify function-header lines (-F).  */
+//XTERN struct re_pattern_buffer function_regexp;
+
+/* Ignore changes that affect only lines matching this regexp (-I).  */
+//XTERN struct re_pattern_buffer ignore_regexp;
+
+/* Say only whether files differ, not how (-q).  */
+XTERN bool brief;
+
+/* Expand tabs in the output so the text lines up properly
+   despite the characters added to the front of each line (-t).  */
+XTERN bool expand_tabs;
+
+/* Use a tab in the output, rather than a space, before the text of an
+   input line, so as to keep the proper alignment in the input line
+   without changing the characters in it (-T).  */
+XTERN bool initial_tab;
+
+/* Remove trailing carriage returns from input.  */
+XTERN bool strip_trailing_cr;
+
+/* In directory comparison, specify file to start with (-S).
+   This is used for resuming an aborted comparison.
+   All file names less than this name are ignored.  */
+XTERN char const *starting_file;
+
+/* Pipe each file's output through pr (-l).  */
+XTERN bool paginate;
+
+/* Line group formats for unchanged, old, new, and changed groups.  */
+XTERN char const *group_format[CHANGED + 1];
+
+/* Line formats for unchanged, old, and new lines.  */
+XTERN char const *line_format[NEW + 1];
+
+/* If using OUTPUT_SDIFF print extra information to help the sdiff filter.  */
+XTERN bool sdiff_merge_assist;
+
+/* Tell OUTPUT_SDIFF to show only the left version of common lines.  */
+XTERN bool left_column;
+
+/* Tell OUTPUT_SDIFF to not show common lines.  */
+XTERN bool suppress_common_lines;
+
+/* The half line width and column 2 offset for OUTPUT_SDIFF.  */
+XTERN unsigned int sdiff_half_width;
+XTERN unsigned int sdiff_column2_offset;
+
+/* String containing all the command options diff received,
+   with spaces between and at the beginning but none at the end.
+   If there were no options given, this string is empty.  */
+XTERN char *switch_string;
+
+/* Use heuristics for better speed with large files with a small
+   density of changes.  */
+XTERN bool speed_large_files;
+
+/* Patterns that match file names to be excluded.  */
+XTERN struct exclude *excluded;
+
+/* Don't discard lines.  This makes things slower (sometimes much
+   slower) but will find a guaranteed minimal set of changes.  */
+XTERN bool minimal;
+
+/* Name of program the user invoked (for error messages).  */
+XTERN char *program_name;
+
+/* The strftime format to use for time strings.  */
+XTERN char const *time_format;
+
+/* The result of comparison is an "edit script": a chain of `struct change'.
+   Each `struct change' represents one place where some lines are deleted
+   and some are inserted.
+
+   LINE0 and LINE1 are the first affected lines in the two files (origin 0).
+   DELETED is the number of lines deleted here from file 0.
+   INSERTED is the number of lines inserted here in file 1.
+
+   If DELETED is 0 then LINE0 is the number of the line before
+   which the insertion was done; vice versa for INSERTED and LINE1.  */
+
+struct change
+{
+  struct change *link;		/* Previous or next edit command  */
+  lin inserted;			/* # lines of file 1 changed here.  */
+  lin deleted;			/* # lines of file 0 changed here.  */
+  lin line0;			/* Line number of 1st deleted line.  */
+  lin line1;			/* Line number of 1st inserted line.  */
+  bool ignore;			/* Flag used in context.c.  */
+};
+
+/* Structures that describe the input files.  */
+
+/* Data on one input file being compared.  */
+
+struct file_data {
+#if 0
+    int             desc;	/* File descriptor  */
+    char const      *name;	/* File name  */
+    struct stat     stat;	/* File status */
+#endif
+    /* Buffer in which text of file is read.  */
+    word *buffer;
+
+    /* Allocated size of buffer, in bytes.  Always a multiple of
+       sizeof *buffer.  */
+    size_t bufsize;
+
+    /* Number of valid bytes now in the buffer.  */
+    size_t buffered;
+
+    /* Array of pointers to lines in the file.  */
+    char const **linbuf;
+
+    /* linbuf_base <= buffered_lines <= valid_lines <= alloc_lines.
+       linebuf[linbuf_base ... buffered_lines - 1] are possibly differing.
+       linebuf[linbuf_base ... valid_lines - 1] contain valid data.
+       linebuf[linbuf_base ... alloc_lines - 1] are allocated.  */
+    lin linbuf_base, buffered_lines, valid_lines, alloc_lines;
+
+    /* Pointer to end of prefix of this file to ignore when hashing.  */
+    char const *prefix_end;
+
+    /* Count of lines in the prefix.
+       There are this many lines in the file before linbuf[0].  */
+    lin prefix_lines;
+
+    /* Pointer to start of suffix of this file to ignore when hashing.  */
+    char const *suffix_begin;
+
+    /* Vector, indexed by line number, containing an equivalence code for
+       each line.  It is this vector that is actually compared with that
+       of another file to generate differences.  */
+    lin *equivs;
+
+    /* Vector, like the previous one except that
+       the elements for discarded lines have been squeezed out.  */
+    lin *undiscarded;
+
+    /* Vector mapping virtual line numbers (not counting discarded lines)
+       to real ones (counting those lines).  Both are origin-0.  */
+    lin *realindexes;
+
+    /* Total number of nondiscarded lines.  */
+    lin nondiscarded_lines;
+
+    /* Vector, indexed by real origin-0 line number,
+       containing TRUE for a line that is an insertion or a deletion.
+       The results of comparison are stored here.  */
+    bool *changed;
+
+    /* 1 if file ends in a line with no final newline.  */
+    bool missing_newline;
+
+    /* 1 if at end of file.  */
+    bool eof;
+
+    /* 1 more than the maximum equivalence value used for this or its
+       sibling file.  */
+    lin equiv_max;
+};
+
+/* The file buffer, considered as an array of bytes rather than
+   as an array of words.  */
+#define FILE_BUFFER(f) ((char *) (f)->buffer)
+
+/* Data on two input files being compared.  */
+
+struct comparison
+  {
+    struct file_data file[2];
+    struct comparison const *parent;  /* parent, if a recursive comparison */
+  };
+
+/* Describe the two files currently being compared.  */
+
+XTERN struct file_data files[2];
+
+/* Stdio stream to output diffs to.  */
+
+XTERN FILE *outfile;
+
+/* Declare various functions.  */
+
+/* analyze.c */
+struct change* diff_2_files (struct comparison *);
+
+/* context.c */
+void print_context_header (struct file_data[], bool);
+void print_context_script (struct change *, bool);
+
+/* dir.c */
+int diff_dirs (struct comparison const *, int (*) (struct comparison const *, char const *, char const *));
+
+/* ed.c */
+void print_ed_script (struct change *);
+void pr_forward_ed_script (struct change *);
+
+/* ifdef.c */
+void print_ifdef_script (struct change *);
+
+/* io.c */
+void file_block_read (struct file_data *, size_t);
+bool read_files (struct file_data[], bool);
+
+/* normal.c */
+void print_normal_script (struct change *);
+
+/* rcs.c */
+void print_rcs_script (struct change *);
+
+/* side.c */
+void print_sdiff_script (struct change *);
+
+/* util.c */
+extern char const change_letter[4];
+extern char const pr_program[];
+char *concat (char const *, char const *, char const *);
+char *dir_file_pathname (char const *, char const *);
+bool lines_differ (char const *, char const *);
+lin translate_line_number (struct file_data const *, lin);
+struct change *find_change (struct change *);
+struct change *find_reverse_change (struct change *);
+void *zalloc (size_t);
+enum changes analyze_hunk (struct change *, lin *, lin *, lin *, lin *);
+void begin_output (void);
+void debug_script (struct change *);
+void fatal (char const *) __attribute__((noreturn));
+void finish_output (void);
+void message (char const *, char const *, char const *);
+void message5 (char const *, char const *, char const *, char const *, char const *);
+void output_1_line (char const *, char const *, char const *, char const *);
+void perror_with_name (char const *);
+void pfatal_with_name (char const *) __attribute__((noreturn));
+void print_1_line (char const *, char const * const *);
+void print_message_queue (void);
+void print_number_range (char, struct file_data *, lin, lin);
+void print_script (struct change *, struct change * (*) (struct change *), void (*) (struct change *));
+void setup_output (char const *, char const *, bool);
+void translate_range (struct file_data const *, lin, lin, long *, long *);
+
+/* version.c */
+extern char const version_string[];
+} // namespace GnuDiff

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

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/kdiff3/src/gnudiff_system.h	Tue Dec 09 20:34:32 2003 +0000
@@ -0,0 +1,133 @@
+/* System dependent declarations.
+
+   Modified for KDiff3 by Joachim Eibl 2003.
+
+   Copyright (C) 1988, 1989, 1992, 1993, 1994, 1995, 1998, 2001, 2002
+   Free Software Foundation, Inc.
+
+   This file is part of GNU DIFF.
+
+   GNU DIFF is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   GNU DIFF is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; see the file COPYING.
+   If not, write to the Free Software Foundation,
+   59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+//#include <config.h>
+
+/* Don't bother to support K&R C compilers any more; it's not worth
+   the trouble.  These macros prevent some library modules from being
+   compiled in K&R C mode.  */
+#define PARAMS(Args) Args
+#define PROTOTYPES 1
+
+/* Define `__attribute__' and `volatile' first
+   so that they're used consistently in all system includes.  */
+#if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 6) || __STRICT_ANSI__
+# define __attribute__(x)
+#endif
+#if defined const && !defined volatile
+# define volatile
+#endif
+
+/* Verify a requirement at compile-time (unlike assert, which is runtime).  */
+#define verify(name, assertion) struct name { char a[(assertion) ? 1 : -1]; }
+
+
+/* Determine whether an integer type is signed, and its bounds.
+   This code assumes two's (or one's!) complement with no holes.  */
+
+/* The extra casts work around common compiler bugs,
+   e.g. Cray C 5.0.3.0 when t == time_t.  */
+#ifndef TYPE_SIGNED
+# define TYPE_SIGNED(t) (! ((t) 0 < (t) -1))
+#endif
+#ifndef TYPE_MINIMUM
+# define TYPE_MINIMUM(t) ((t) (TYPE_SIGNED (t) \
+			       ? ~ (t) 0 << (sizeof (t) * CHAR_BIT - 1) \
+			       : (t) 0))
+#endif
+#ifndef TYPE_MAXIMUM
+# define TYPE_MAXIMUM(t) ((t) (~ (t) 0 - TYPE_MINIMUM (t)))
+#endif
+
+#include <sys/types.h>
+#include <sys/stat.h>
+
+
+# include <stdlib.h>
+#ifndef EXIT_SUCCESS
+# define EXIT_SUCCESS 0
+#endif
+#if !EXIT_FAILURE
+# undef EXIT_FAILURE /* Sony NEWS-OS 4.0C defines EXIT_FAILURE to 0.  */
+# define EXIT_FAILURE 1
+#endif
+#define EXIT_TROUBLE 2
+
+#include <limits.h>
+#ifndef SSIZE_MAX
+# define SSIZE_MAX TYPE_MAXIMUM (ssize_t)
+#endif
+
+#ifndef PTRDIFF_MAX
+# define PTRDIFF_MAX TYPE_MAXIMUM (ptrdiff_t)
+#endif
+#ifndef SIZE_MAX
+# define SIZE_MAX TYPE_MAXIMUM (size_t)
+#endif
+#ifndef UINTMAX_MAX
+# define UINTMAX_MAX TYPE_MAXIMUM (uintmax_t)
+#endif
+
+#include <stddef.h>
+#include <string.h>
+#include <ctype.h>
+
+/* CTYPE_DOMAIN (C) is nonzero if the unsigned char C can safely be given
+   as an argument to <ctype.h> macros like `isspace'.  */
+# define CTYPE_DOMAIN(c) 1
+#define ISPRINT(c) (CTYPE_DOMAIN (c) && isprint (c))
+#define ISSPACE(c) (CTYPE_DOMAIN (c) && isspace (c))
+
+# define TOLOWER(c) tolower (c)
+
+/* ISDIGIT differs from isdigit, as follows:
+   - Its arg may be any int or unsigned int; it need not be an unsigned char.
+   - It's guaranteed to evaluate its argument exactly once.
+   - It's typically faster.
+   POSIX 1003.1-2001 says that only '0' through '9' are digits.
+   Prefer ISDIGIT to isdigit unless it's important to use the locale's
+   definition of `digit' even when the host does not conform to POSIX.  */
+#define ISDIGIT(c) ((unsigned int) (c) - '0' <= 9)
+
+#undef MIN
+#undef MAX
+#define MIN(a, b) ((a) <= (b) ? (a) : (b))
+#define MAX(a, b) ((a) >= (b) ? (a) : (b))
+
+
+
+/* Type used for fast comparison of several bytes at a time.  */
+
+#ifndef word
+# define word unsigned int
+#endif
+
+/* The integer type of a line number.  Since files are read into main
+   memory, ptrdiff_t should be wide enough.  */
+
+typedef ptrdiff_t lin;
+#define LIN_MAX PTRDIFF_MAX
+verify (lin_is_signed, TYPE_SIGNED (lin));
+verify (lin_is_wide_enough, sizeof (ptrdiff_t) <= sizeof (lin));
+verify (lin_is_printable_as_long, sizeof (lin) <= sizeof (long));

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/kdiff3/src/gnudiff_xalloc.h	Tue Dec 09 20:34:32 2003 +0000
@@ -0,0 +1,91 @@
+/* xalloc.h -- malloc with out-of-memory checking
+
+   Modified for KDiff3 by Joachim Eibl 2003.
+
+   Copyright (C) 1990-1998, 1999, 2000, 2002 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software Foundation,
+   Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+#ifndef XALLOC_H_
+# define XALLOC_H_
+
+# ifndef PARAMS
+#  if defined PROTOTYPES || (defined __STDC__ && __STDC__)
+#   define PARAMS(Args) Args
+#  else
+#   define PARAMS(Args) ()
+#  endif
+# endif
+
+# ifndef __attribute__
+#  if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__
+#   define __attribute__(x)
+#  endif
+# endif
+
+# ifndef ATTRIBUTE_NORETURN
+#  define ATTRIBUTE_NORETURN __attribute__ ((__noreturn__))
+# endif
+
+
+namespace GnuDiff
+{
+
+/* If this pointer is non-zero, run the specified function upon each
+   allocation failure.  It is initialized to zero. */
+extern void (*xalloc_fail_func) PARAMS ((void));
+
+/* If XALLOC_FAIL_FUNC is undefined or a function that returns, this
+   message is output.  It is translated via gettext.
+   Its value is "memory exhausted".  */
+extern char const xalloc_msg_memory_exhausted[];
+
+/* This function is always triggered when memory is exhausted.  It is
+   in charge of honoring the three previous items.  This is the
+   function to call when one wants the program to die because of a
+   memory allocation failure.  */
+extern void xalloc_die PARAMS ((void)) ATTRIBUTE_NORETURN;
+
+void *xmalloc PARAMS ((size_t n));
+void *xcalloc PARAMS ((size_t n, size_t s));
+void *xrealloc PARAMS ((void *p, size_t n));
+char *xstrdup PARAMS ((const char *str));
+
+} // namespace GnuDiff
+
+# define XMALLOC(Type, N_items) ((Type *) xmalloc (sizeof (Type) * (N_items)))
+# define XCALLOC(Type, N_items) ((Type *) xcalloc (sizeof (Type), (N_items)))
+# define XREALLOC(Ptr, Type, N_items) \
+  ((Type *) xrealloc ((void *) (Ptr), sizeof (Type) * (N_items)))
+
+/* Declare and alloc memory for VAR of type TYPE. */
+# define NEW(Type, Var)  Type *(Var) = XMALLOC (Type, 1)
+
+/* Free VAR only if non NULL. */
+# define XFREE(Var)	\
+   do {                 \
+      if (Var)          \
+        free (Var);     \
+   } while (0)
+
+/* Return a pointer to a malloc'ed copy of the array SRC of NUM elements. */
+# define CCLONE(Src, Num) \
+  (memcpy (xmalloc (sizeof (*Src) * (Num)), (Src), sizeof (*Src) * (Num)))
+
+/* Return a malloc'ed copy of SRC. */
+# define CLONE(Src) CCLONE (Src, 1)
+
+
+#endif /* !XALLOC_H_ */

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/kdiff3/src/gnudiff_xmalloc.cpp	Tue Dec 09 20:34:32 2003 +0000
@@ -0,0 +1,107 @@
+/* xmalloc.c -- malloc with out of memory checking
+
+   Modified for KDiff3 by Joachim Eibl 2003.
+
+   Copyright (C) 1990-1999, 2000, 2002 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software Foundation,
+   Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+#if HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#include <sys/types.h>
+
+
+#include <stdlib.h>
+#include <string.h>
+
+
+//#include "error.h"
+#include "gnudiff_xalloc.h"
+
+#ifndef EXIT_FAILURE
+# define EXIT_FAILURE 1
+#endif
+
+namespace GnuDiff
+{
+
+/* If non NULL, call this function when memory is exhausted. */
+//void (*xalloc_fail_func) PARAMS ((void)) = 0;
+void (*xalloc_fail_func)(void) = 0;
+
+
+void
+xalloc_die (void)
+{
+  if (xalloc_fail_func)
+    (*xalloc_fail_func) ();
+  //error (exit_failure, 0, "%s", _(xalloc_msg_memory_exhausted));
+  /* The `noreturn' cannot be given to error, since it may return if
+     its first argument is 0.  To help compilers understand the
+     xalloc_die does terminate, call exit. */
+  exit (EXIT_FAILURE);
+}
+
+/* Allocate N bytes of memory dynamically, with error checking.  */
+
+void *
+xmalloc (size_t n)
+{
+  void *p;
+
+  p = malloc (n);
+  if (p == 0)
+    xalloc_die ();
+  return p;
+}
+
+/* Change the size of an allocated block of memory P to N bytes,
+   with error checking.  */
+
+void *
+xrealloc (void *p, size_t n)
+{
+  p = realloc (p, n);
+  if (p == 0)
+    xalloc_die ();
+  return p;
+}
+
+/* Allocate memory for N elements of S bytes, with error checking.  */
+
+void *
+xcalloc (size_t n, size_t s)
+{
+  void *p;
+
+  p = calloc (n, s);
+  if (p == 0)
+    xalloc_die ();
+  return p;
+}
+
+/* Yield a new block of SIZE bytes, initialized to zero.  */
+
+void *
+zalloc (size_t size)
+{
+  void *p = xmalloc (size);
+  memset (p, 0, size);
+  return p;
+}
+
+} // namespace GnuDiff