bug in public domain diff?

[D. Hugh Redelmeier]

Various versions of a public domain diff have been broadcast across
the net over the years (including comp.sources.misc 2.1, 2.8, and
2.59).  The original version was on the DECUS C tape, author unknown
(Conroy?).  This program is based on the same algorithm as UNIX diff.

Anyway, all the versions I have checked seem to produce suboptimal
output when diffing the following two files.  UNIX diff does not
have this problem.  Am I right, is this a bug?  Does anyone know a
fix?  The code is currently beyond my comprehension.

file a:
	9
	1
	2
	3
	4
	5
	6
	9

file b:
	8
	1
	2
	x
	x
	4
	3
	4
	5
	6
	8

pd-diff says:
	1c1
	< 9
	---
	> 8
	4c4,5
	< 3
	---
	> x
	> x
	5a7,8
	> 3
	> 4
	8c11
	< 9
	---
	> 8

SunOS3.5 diff says:
	1c1
	< 9
	---
	> 8
	3a4,6
	> x
	> x
	> 4
	8c11
	< 9
	---
	> 8

Notice that pd-diff uselessly deletes and re-inserts 3.  This is not
wrong, just suboptimal.  Perhaps there is a simple off-by-one error
in the code.

Hugh Redelmeier
{utcsri, yunexus, uunet!attcan!utzoo, hcr}!redvax!hugh
When all else fails: hugh at csri.toronto.edu
+1 416 482-8253