[Toybox] histogram diff

[Ray Gardner]

> [patience diff] may have predated the "histogram" algorithm which is
> surprisingly hard to google for...
> ...
> I was really hoping I could implement just ONE algorithm and call it good.
> Right now it looks like "histogram" would be that one (it's an improvement
> upon "patience" which is the one I'd planned to implement before somebody
> else sent in a contribution). ...

Yes, there was nothing on the Web explaining it well enough to implement it.
I had to dig to figure it out.

I have attached a patch to your "branch" diff.c that you've set aside for a
few years. It replaces the hunky-dory code with a histogram diff
implementation. Also implements diff "default" output as well as unified.
It does not at present support -p, -B, -q, -s. I can work on them a bit if
you are interested. I would leave -r to you, as well as color, label, etc.

It does produce pretty decent diffs quickly, that match git's closely and
jgit's exactly. I used it to produce the attached patch, of course. There is
an explanation of the algo and code at the end after main(), and I've
written a couple of posts about it at raygard.net. And have a working
standalone version at github.com/raygard/hdiff/.

Ray
-------------- next part --------------
A non-text attachment was scrubbed...
Name: diff.patch
Type: application/x-patch
Size: 29190 bytes
Desc: not available
URL: <http://lists.landley.net/pipermail/toybox-landley.net/attachments/20250130/abca4d84/attachment-0001.bin>