Landon Curt Noll
f29b37e49a
Prepare for the winners of **IOCCC28**. > However these are not the 2024 droids you are looking for. :-) The HTML menu (both JavaScript and non-JavaScript) has been updated. The `Status -> Rules and guidelines' have been replaced with two separate menus `Status -> IOCCC rules` and `Status -> IOCCC guidelines`. Added a new top level `social.html` page: built from a new `social.md`. Sorted rules for building specific web pages in the top level `Makefile`. Added `make social` to make the `social.html` page from `social.md`. The `bin/gen-top-html.sh` now is able to process a argument of **social** to process the new top level `social.html` page. Changed `bin/gen-top-html.sh` VERSION from "2.0.0 2025-03-13" to "2.0.1 2025-07-25". Below `About -> Home page` a new `About -> IOCCC social media` menu item as added. Because the menu change touched every HTML file, we changed the general copyright date range for HTML files from "1984-2024" to "1984-2025" due to the extensive changes made for **IOCCC28**. Those markdown files that were modified in 2025 had their copyright date range also changed from "1984-2024" to "1984-2025". Rebuilt tarballs and sitemap due to the extensive HTML rebuilding. Ran `make update` to perform the above.
199 lines
6.0 KiB
Markdown
199 lines
6.0 KiB
Markdown
## To build:
|
|
|
|
``` <!---sh-->
|
|
make
|
|
```
|
|
|
|
There are two alternate versions provided by the author. See [Alternate
|
|
code](#alternate-code) and the author's remarks below for more details.
|
|
|
|
|
|
### Bugs and (Mis)features:
|
|
|
|
The current status of this entry is:
|
|
|
|
> **STATUS: known bug - please help us fix**
|
|
|
|
For more detailed information see [2015/howe in bugs.html](../../bugs.html#2015_howe).
|
|
|
|
|
|
## To use:
|
|
|
|
``` <!---sh-->
|
|
./prog file1 file2
|
|
|
|
./prog -d file1 file2
|
|
```
|
|
|
|
|
|
## Try:
|
|
|
|
``` <!---sh-->
|
|
./try.sh
|
|
```
|
|
|
|
|
|
## Alternate code:
|
|
|
|
This alternate version does not use a 64-bit FNV hash. This was the original
|
|
entry but was changed to be the alt version. Later, in 2024, the author provided
|
|
an unobfuscated version which is in
|
|
[prog.alt2.c](%%REPO_URL%%/2015/howe/prog.alt2.c).
|
|
|
|
|
|
### Alternate build:
|
|
|
|
To build these versions:
|
|
|
|
``` <!---sh-->
|
|
make alt
|
|
```
|
|
|
|
|
|
### Alternate use:
|
|
|
|
Use `prog.alt` and/or `prog.alt2` as you would `prog` above.
|
|
|
|
|
|
### Alternate try:
|
|
|
|
``` <!---sh-->
|
|
./try.alt.sh
|
|
```
|
|
|
|
|
|
## Judges' remarks:
|
|
|
|
This is the best use of the FNV that we have seen in the IOCCC so far!
|
|
The output, when used without `-d`, is compatible with POSIX `diff(1)` and
|
|
is suitable for use with `patch(1)`.
|
|
|
|
We welcome back Canada 🇨🇦 to the list of nations from where winning
|
|
entries have been submitted.
|
|
|
|
Is this code a bug or a feature? :-) Or is this an attempt to corrupt the
|
|
programming of our youth? Should we heed Kyle's mom words that she uttered
|
|
during a South Park P.T.A. Meeting?
|
|
|
|
> "We must stop dirty (C) language from getting to our children's ears!"
|
|
>
|
|
> [Blame Canada](https://www.youtube.com/watch?v=bOR38552MJA)
|
|
|
|
Or should we teach our youth to understand the intricacies of this code?
|
|
Ying Tong Iddle I Po! We suggest you read the source for yourself, which
|
|
might be easier than the academic papers it was inspired by.
|
|
|
|
**NOTE**: Unlike the original entry source, [prog.alt.c](%%REPO_URL%%/2015/howe/prog.alt.c),
|
|
[prog.c](%%REPO_URL%%/2015/howe/prog.c) uses a
|
|
64 bit FNV hash and fixes a function call warning.
|
|
|
|
|
|
## Author's remarks:
|
|
|
|
### Features
|
|
|
|
* "An O(NP) Sequence Comparison Algorithm" by Wu, Manber, Myers, Miller.
|
|
|
|
* Output compatible with `patch(1)`.
|
|
|
|
* Strokes one of the judge's ego (I couldn't email chocolate or curry).
|
|
|
|
|
|
### Description
|
|
|
|
This is a functioning micro `diff(1)` tool using an [O(NP) algorithm][Wu+89],
|
|
compared to the older [O(ND) difference algorithm][Mye86] used by some versions
|
|
of `diff(1)`. Its output is based on the default `diff(1)` output described by POSIX
|
|
and [the Open Group Base Specifications][SUSV7]. The output is suitable for use
|
|
with `patch(1)`.
|
|
|
|
The `-d` option simply writes the edit distance between `file1` and `file2`.
|
|
|
|
|
|
### Observations
|
|
|
|
The FNV1a hash is a little slow compared to the trivial hash [GNU
|
|
diff](https://www.gnu.org/software/diffutils/) uses. I downloaded a plain text
|
|
copy of "War And Peace" from [Project Gutenberg](https://www.gutenberg.org),
|
|
used [makeholes.c](%%REPO_URL%%/2015/howe/makeholes.c) to make 1000 random changes, then profiled and
|
|
timed the program verses GNU `diff(1)`. The bottleneck appears to be in the
|
|
file I/O and line hashing with an average +0.05s slower. Using a huge file like
|
|
"War And Peace" for testing offsets the `diff(1)` optimised file I/O.
|
|
|
|
There is no hash collision checking, partly because FNV1a appears to generate
|
|
very [few collisions][HshCmp] and an assumption that localised collisions within
|
|
a region of edits are highly unlikely.
|
|
|
|
|
|
### Support Files
|
|
|
|
* [prog-test.sh](%%REPO_URL%%/2015/howe/prog-test.sh)
|
|
Basic test program verifies known test edit distances and `patch(1)` support.
|
|
|
|
* [avgtime.sh](%%REPO_URL%%/2015/howe/avgtime.sh)
|
|
Run `time(1)` on a command `N` times to determine its average runtime.
|
|
|
|
* [makeholes.c](%%REPO_URL%%/2015/howe/makeholes.c)
|
|
Random edits (holes) made to a file in-place.
|
|
|
|
### References
|
|
|
|
Wu, Manber, Myers, and Miller; August 1989;<br>
|
|
"An O(NP) Sequence Comparison Algorithm";<br>
|
|
<http://myerslab.mpi-cbg.de/wp-content/uploads/2014/06/np_diff.pdf>
|
|
|
|
Fowler, Noll, Vo; 1994<br>
|
|
<http://www.isthe.com/chongo/tech/comp/fnv/index.html>
|
|
|
|
Fowler, Noll, Vo on Wikipedia<br>
|
|
<https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function>
|
|
|
|
"diff", The Open Group Base Specifications Issue 7<br>
|
|
IEEE Std 1003.1, 2013 Edition<br>
|
|
<http://pubs.opengroup.org/onlinepubs/9699919799/utilities/diff.html>
|
|
|
|
Eugene W. Myers; "An O(ND) Difference Algorithm and Its Variations";<br>
|
|
Algorithmica, 1986, pages. 251-266<br>
|
|
<http://www.xmailserver.org/diff2.pdf>
|
|
|
|
Webb Miller and Eugene W. Myers; "A File Comparison Program";<br>
|
|
Software-Practice And Experience, Vol. 15(11). 1025-1040 (November 1985)<br>
|
|
<http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.189.70&rep=rep1&type=pdf>
|
|
|
|
D.S. Hirschberg, "A linear space algorithm for computing maximal common subsequence problem";<br>
|
|
Comm. of ACM, Vol. 18, June 1975, pages 341-343<br>
|
|
<http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/DynProg/Docs/Hirschberg-LCS-1975.pdf>
|
|
|
|
Which hashing algorithm is best for uniqueness and speed?<br>
|
|
<http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed>
|
|
|
|
[Wu+89]: http://myerslab.mpi-cbg.de/wp-content/uploads/2014/06/np_diff.pdf
|
|
|
|
[FNV94]: http://www.isthe.com/chongo/tech/comp/fnv/index.html
|
|
|
|
[FNVWi]: https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
|
|
|
|
[Mye86]: http://www.xmailserver.org/diff2.pdf
|
|
|
|
[SUSV7]: http://pubs.opengroup.org/onlinepubs/9699919799/utilities/diff.html
|
|
|
|
[Mil85]: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.189.70&rep=rep1&type=pdf
|
|
|
|
[Hir75]: http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/DynProg/Docs/Hirschberg-LCS-1975.pdf
|
|
|
|
[HshCmp]: http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed
|
|
|
|
<!--
|
|
|
|
Copyright © 1984-2025 by Landon Curt Noll. All Rights Reserved.
|
|
|
|
You are free to share and adapt this file under the terms of this license:
|
|
|
|
Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA 4.0)
|
|
|
|
For more information, see:
|
|
|
|
https://creativecommons.org/licenses/by-sa/4.0/
|
|
|
|
-->
|