Files
ioccc/2024/burton/deobfuscated.html
Landon Curt Noll 09750f8899 release winning entries of IOCCC28 under the year 2024
Congratulations to:

* 2024/anders - Prize in sound coding - layered music generator
* 2024/burton - Prize in pentagrammatology - wordle hard mode solver
* 2024/cable1 - Prize in bot talk - LLM inference engine
* 2024/cable2 - Prize in murky waters - salmon recipe
* 2024/carlini - Prize in perfect timing - Intel 4004 emulation
* 2024/codemeow - Prize in tray planting - bonsai generator
* 2024/endoh1 - Prize in patient pointillism - slow ray tracer in CPP
* 2024/endoh2 - Prize in solid body physics - rotating rigid body simulation
* 2024/ferguson1 - Prize in diabolical logistics - Oregon trail pact with the devil
* 2024/ferguson2 - Prize in yil-tas - Navajo code talker translator
* 2024/howe - Nice accent eh-ward - mini vi
* 2024/kramer - Prize in linguistic arithmetic - natural language numerical calculator
* 2024/kurdyukov1 - Prize in phased periodicity - phase of the Moon
* 2024/kurdyukov2 - Prize in art restoration - JPEG artifact removal
* 2024/kurdyukov3 - Prize in virtual quietus - gaming VM and doom
* 2024/kurdyukov4 - Prize in embiggening - encode without literals
* 2024/maffiodo - Prize in creative interpretation - Jav\*script interpreter
* 2024/mills - Prize in ℤ₃ - Infocom v3 story interpreter
* 2024/stedolan - Best one liner - icon from MD5
* 2024/straadt - Prize in imitative rebooting - OpenRISC CPU and Linux
* 2024/tmarrec - Prize in cyclonic coding - 3D tornado simulation
* 2024/tompng - Prize in quasi bijection - vortex encryptor decryptor
* 2024/weaver - Sur prize - rickroll

Ran `make update` to perform the above.
 	new file:   2024/burton/.entry.json
2025-08-02 14:43:07 -07:00

815 lines
33 KiB
HTML
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<!-- START: two lines up starts content from: inc/top.default.html -->
<!-- END: this line ends content from: inc/top.default.html -->
<!-- START: this line starts content from: inc/head.default.html -->
<head>
<link rel="stylesheet" href="../../ioccc.css">
<link href="https://fonts.googleapis.com/css2?family=Outfit:wght@100..900&display=swap" rel="stylesheet">
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes">
<title>The International Obfuscated C Code Contest</title>
<link rel="icon" type="image/x-icon" href="../../favicon.ico">
<meta name="description" content="deobfuscated.md for 2024/burton">
<meta name="keywords" content="IOCCC, 2024/burton, deobfuscated.md">
</head>
<!-- !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! -->
<!-- !!! DO NOT MODIFY THIS FILE - This file is generated by a tool !!! -->
<!-- !!! DO NOT MODIFY THIS FILE - This file is generated by a tool !!! -->
<!-- !!! DO NOT MODIFY THIS FILE - This file is generated by a tool !!! -->
<!-- !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! -->
<!-- END: this line ends content from: inc/head.default.html -->
<!-- -->
<!-- This web page was formed via the tool: bin/gen-other-html.sh -->
<!-- The content of main section of this web page came from: 2024/burton/deobfuscated.md -->
<!-- -->
<!-- !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! -->
<!-- !!! Do not modify this web page, instead modify the file: 2024/burton/deobfuscated.md !!! -->
<!-- !!! Do not modify this web page, instead modify the file: 2024/burton/deobfuscated.md !!! -->
<!-- !!! Do not modify this web page, instead modify the file: 2024/burton/deobfuscated.md !!! -->
<!-- !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! -->
<!-- Markdown content was converted into HTML via the tool: bin/md2html.sh -->
<!-- START: this line starts content from: inc/body.default.html -->
<body>
<!-- END: this line ends content from: inc/body.default.html -->
<!-- START: this line starts content from: inc/topbar.default.html -->
<div class="theader">
<nav class="topbar">
<div class="container">
<div class="logo">
<a href="../../index.html" class="logo-link">
IOCCC
</a>
</div>
<div class="topbar-items">
<div class="item">
<span class="item-header">
Entries
</span>
<div class="sub-item">
<div class="outfit-font">
<a href="../../years.html" class="sub-item-link">
Winning entries
</a>
</div>
<div class="outfit-font">
<a href="../../authors.html" class="sub-item-link">
Winning authors
</a>
</div>
<div class="outfit-font">
<a href="../../location.html" class="sub-item-link">
Location of authors
</a>
</div>
<div class="outfit-font">
<a href="../../bugs.html" class="sub-item-link">
Bugs and (mis)features
</a>
</div>
<div class="outfit-font">
<a href="../../faq.html#fix_an_entry" class="sub-item-link">
Fixing entries
</a>
</div>
<div class="outfit-font">
<a href="../../faq.html#fix_author" class="sub-item-link">
Updating author info
</a>
</div>
</div>
</div>
<div class="item">
<span class="item-header">
Status
</span>
<div class="sub-item">
<div class="outfit-font">
<a href="../../news.html" class="sub-item-link">
News
</a>
</div>
<div class="outfit-font">
<a href="../../status.html" class="sub-item-link">
Contest status
</a>
</div>
<div class="outfit-font">
<a href="../../next/rules.html" class="sub-item-link">
IOCCC rules
</a>
</div>
<div class="outfit-font">
<a href="../../next/guidelines.html" class="sub-item-link">
IOCCC guidelines
</a>
</div>
<div class="outfit-font">
<a href="../../markdown.html" class="sub-item-link">
Markdown guidelines
</a>
</div>
<div class="outfit-font">
<a href="../../SECURITY.html" class="sub-item-link">
Security policy
</a>
</div>
</div>
</div>
<div class="item">
<span class="item-header">
FAQ
</span>
<div class="sub-item">
<div class="outfit-font">
<a href="../../faq.html" class="sub-item-link">
Frequently asked questions
</a>
</div>
<div class="outfit-font">
<a href="../../quick-start.html#enter" class="sub-item-link">
Enter the IOCCC
</a>
</div>
<div class="outfit-font">
<a href="../../faq.html#compiling" class="sub-item-link">
Compiling entries
</a>
</div>
<div class="outfit-font">
<a href="../../faq.html#running_entries" class="sub-item-link">
Running entries
</a>
</div>
<div class="outfit-font">
<a href="../../faq.html#help" class="sub-item-link">
How to help
</a>
</div>
</div>
</div>
<div class="item">
<span class="item-header">
About
</span>
<div class="sub-item">
<div class="outfit-font">
<a href="../../index.html" class="sub-item-link">
Home page
</a>
</div>
<div class="outfit-font">
<a href="../../social.html" class="sub-item-link">
IOCCC social media
</a>
</div>
<div class="outfit-font">
<a href="../../about.html" class="sub-item-link">
About the IOCCC
</a>
</div>
<div class="outfit-font">
<a href="../../judges.html" class="sub-item-link">
The judges
</a>
</div>
<div class="outfit-font">
<a href="../../thanks-for-help.html" class="sub-item-link">
Thanks for the help
</a>
</div>
<div class="outfit-font">
<a href="../../contact.html" class="sub-item-link">
Contact us
</a>
</div>
</div>
</div>
</div>
</div>
</nav>
<div class="header-mobile-menu">
<noscript>
<a href="../../nojs-menu.html" class="topbar-js-label">
Please Enable JavaScript
</a>
</noscript>
<button id="header-open-menu-button" class="topbar-mobile-menu">
<img
src="../../png/hamburger-icon-open.png"
alt="hamburger style menu icon - open state"
width=48
height=48>
</button>
<button id="header-close-menu-button" class="hide-content">
<img
src="../../png/hamburger-icon-closed.png"
alt="hamburger style menu icon - closed state"
width=48
height=48>
</button>
<div id="mobile-menu-panel" class="hide-content">
<div class="mobile-menu-container">
<div class="mobile-menu-wrapper">
<div class="mobile-menu-item">
Entries
</div>
<div class="mobile-submenu-wrapper">
<a class="mobile-submenu-item" href="../../years.html">
Winning entries
</a>
<a class="mobile-submenu-item" href="../../authors.html">
Winning authors
</a>
<a class="mobile-submenu-item" href="../../location.html">
Location of authors
</a>
<a class="mobile-submenu-item" href="../../bugs.html">
Bugs and (mis)features
</a>
<a class="mobile-submenu-item" href="../../faq.html#fix_an_entry">
Fixing entries
</a>
<a class="mobile-submenu-item" href="../../faq.html#fix_author">
Updating author info
</a>
<a class="mobile-submenu-item" href="../../thanks-for-help.html">
Thanks for the help
</a>
</div>
</div>
<div class="mobile-menu-wrapper">
<div class="mobile-menu-item">
Status
</div>
<div class="mobile-submenu-wrapper">
<a class="mobile-submenu-item" href="../../news.html">
News
</a>
<a class="mobile-submenu-item" href="../../status.html">
Contest status
</a>
<a class="mobile-submenu-item" href="../../next/rules.html">
IOCCC rules
</a>
<a class="mobile-submenu-item" href="../../next/guidelines.html">
IOCCC guidelines
</a>
<a class="mobile-submenu-item" href="../../markdown.html">
Markdown guidelines
</a>
<a class="mobile-submenu-item" href="../../SECURITY.html">
Security policy
</a>
</div>
</div>
<div class="mobile-menu-wrapper">
<div class="mobile-menu-item">
FAQ
</div>
<div class="mobile-submenu-wrapper">
<a class="mobile-submenu-item" href="../../faq.html">
Frequently asked questions
</a>
<a class="mobile-submenu-item" href="../../quick-start.html#enter">
Enter the IOCCC
</a>
<a class="mobile-submenu-item" href="../../faq.html#compiling">
Compiling entries
</a>
<a class="mobile-submenu-item" href="../../faq.html#running_entries">
Running entries
</a>
<a class="mobile-submenu-item" href="../../faq.html#help">
How to help
</a>
</div>
</div>
<div class="mobile-menu-wrapper">
<div class="mobile-menu-item">
About
</div>
<div class="mobile-submenu-wrapper">
<a class="mobile-submenu-item" href="../../index.html">
Home page
</a>
<a class="mobile-submenu-item" href="../../social.html">
IOCCC social media
</a>
<a class="mobile-submenu-item" href="../../about.html">
About the IOCCC
</a>
<a class="mobile-submenu-item" href="../../judges.html">
The judges
</a>
<a class="mobile-submenu-item" href="../../contact.html">
Contact us
</a>
</div>
</div>
</div>
</div>
</div>
</div>
<script>
var headerOpenMenuButton = document.getElementById("header-open-menu-button");
var headerCloseMenuButton = document.getElementById("header-close-menu-button");
var mobileMenuPanel = document.getElementById("mobile-menu-panel");
headerOpenMenuButton.addEventListener("click", () => {
headerOpenMenuButton.classList.remove("topbar-mobile-menu");
headerOpenMenuButton.classList.add("hide-content");
headerCloseMenuButton.classList.remove("hide-content");
headerCloseMenuButton.classList.add("topbar-mobile-menu");
mobileMenuPanel.classList.remove("hide-content");
mobileMenuPanel.classList.add("topbar-mobile-panel");
});
headerCloseMenuButton.addEventListener("click", () => {
headerCloseMenuButton.classList.remove("topbar-mobile-menu");
headerCloseMenuButton.classList.add("hide-content");
mobileMenuPanel.classList.add("hide-content");
mobileMenuPanel.classList.remove("topbar-mobile-panel");
headerOpenMenuButton.classList.add("topbar-mobile-menu");
headerOpenMenuButton.classList.remove("hide-content");
});
</script>
<!-- END: this line ends content from: inc/topbar.default.html -->
<!-- START: this line starts content from: inc/header.default.html -->
<div class="header">
<a href="../../2011/zucker/index.html">
<img src="../../png/ioccc.png"
alt="IOCCC image by Matt Zucker"
width=300
height=110>
</a>
<h1>The International Obfuscated C Code Contest</h1>
<h2>deobfuscated.html for 2024/burton</h2>
</div>
<!-- END: this line ends content from: inc/header.default.html -->
<!-- START: this line starts content from: inc/navbar.up2index.html -->
<div class="navbar">
<a class="Left" href="index.html">&uarr; jump to 2024/burton/index.html &uarr;</a>
<a class="Right" href="https://validator.w3.org/nu/?doc=https%3A%2F%2Fwww.ioccc.org%2F2024%2Fburton%2Fdeobfuscated.html">&#x2713;</a>
</div>
<!-- END: this line ends content from: inc/navbar.up2index.html -->
<!-- START: this line starts content from: inc/before-content.default.html -->
<div class="content" id="content">
<!-- END: this line ends content from: inc/before-content.default.html -->
<!-- START: this line starts content for HTML phase 21 by: bin/pandoc-wrapper.sh via bin/md2html.sh -->
<!-- BEFORE: 1st line of markdown file: 2024/burton/deobfuscated.md -->
<h1 id="do-not-read-this-if-you-want-to-figure-it-out-yourself">Do not read this if you want to figure it out yourself!</h1>
<p>The file <code>deobfuscated.c</code> is simply a pretty-printed version of
<code>prog.c</code> with the macros expanded. It is hopefully just as
difficult to understand as the original presentation:
obfuscation is not just presentation, after all.</p>
<p>If you read further, the remainder talks about how the code
works. If you want to figure it out yourself, stop reading here
and do look at <code>deobfuscated.c</code>.</p>
<h2 id="read-dictionary">Read Dictionary</h2>
<p>The program begins by reading junk ;-) from the dictionary and processing
via <code>D()</code>. The words are stored in <code>t[][]</code>, counted by <code>s</code> and <code>D()</code> ensures
this never has buffer overflow. Notice the swap of index and array in <code>s[t]</code>.
It also ensures only 5 letter words are selected from the dictionary,
and folds uppercase to lowercase. Each call of <code>D()</code> handles one word.</p>
<p>NB: if the dictionary has, for instance, “ARRAY” and “array” and “Array”,
there will be 3 copies of “array” stored in <code>t[][]</code>.
This will degrade performance and may cause a malfunction of the algorithm,
and definitely if the target word is “array”. Thus the <code>makefile</code> builds
<code>usdw</code> with capital letters removed (avoiding this problem completely).
However, if there are duplicate words in the dictionary, use another.</p>
<h2 id="user-input">User Input</h2>
<p>After the dictionary is read, it is time to prompt the user for the
input guess. This happens in <code>main()</code>. The input buffer is the upper
half of <code>i.a</code>, which is never used (ASCII lowercase letters only).
The newline is ignored by <code>n - 10</code>, at most 11 characters (<code>l &lt; j</code>)
can be input, and EOF terminates the input loop.</p>
<p>Here is the explanation of how <code>i.c - 97</code> works to get an input buffer.
Assume <code>struct i</code> has the address 1000, then <code>i.a</code> begins at 1000.
<code>i.b</code> begins at 1257. <code>i.c</code> begins at 9*5 = 45 + 1257 = 1302.
1302 - 97 = 1205. Therefore, the <code>i.c - 97</code> sets the input buffer at
<code>&amp;i.a[205]</code>, ASCII lowercase input ends at <code>i.a[123]</code>, and there are
53 characters before <code>i.b</code> is overwritten - plenty of room for the user IO.
Why 97? The expression <code>x - 97</code> is used several times in the code,
leading to some confusion on the reason for the value.</p>
<p>Note that this abuse is what draws a compiler complaint, requiring:</p>
<pre><code> -Wno-array-bounds-pointer-arithmetic</code></pre>
<p>It is safe. It works. There is no problem here, but the compiler
does not know this.</p>
<h2 id="process-user-input">Process User Input</h2>
<p>Once the user input is received, the program calls <code>r()</code>, which populates
<code>struct i</code> with the guesses. This serves to set the patterns known
and impossible, as well as letters used and required (remember, this is
hard mode Wordle, which requires you to use all green letters in the
same place for all subsequent guesses). <code>r()</code> returns the next word
to guess via <code>E()</code> (aka choose() - see below).</p>
<p>Within <code>r()</code>, it is important to understand the ASCII values for g, y and b.</p>
<pre><code> b 98
g 103
y 121</code></pre>
<p>Within <code>r()</code>, <code>n</code> is the guessed letter, and <code>o</code> is color - 103.
If <code>o</code> is greater than zero (121-103), this guess is correct, but
incorrect location (yellow). If it is less than zero (98-103),
this guess is not possible (black). If it is zero (103-103),
it is the correct letter in the correct location (green).</p>
<p><code>struct i</code> can be re-written this way:</p>
<pre><code> struct {
char black[256]; // wrong letters guessed so far
char words[9][5]; // words used in guesses so far
char green[5]; // correct letters (must reuse these)
char yellow[5]; // incorrect letters (impossible positions)
int num_guesses;
int num_yellow;
} i;</code></pre>
<p>And <code>r()</code> can be rewritten:</p>
<pre><code> char *r(char *input) {
int num_green = 0, l = 0;
for (int j = 0; j &lt; 5; ++j) {
char n = input[j];
signed char o = input[j + 6] - 103; // j - ~5 = j - -6 == j + 6
// if this is a correct guess
if (o == 0) {
i.green[j] = n;
i.black[n] = 0; // remove this from black
++num_green;
} else {
i.words[i.num_guesses][j] = n;
// if not already a yellow letter
if (memchr(i.yellow, n, 5) == NULL) {
l = n;
if (o &lt; 0) i.black[n] = n; // black, impossible
else i.yellow[i.num_yellow++] = n;
}
}
}
// l is 0 if all letters correct, else l = n
i.num_guesses += l &gt; 0 ? 1 : 0;
filter(input, num_green);
return choose(&quot;xyzzy&quot;);
}</code></pre>
<h2 id="filter">Filter</h2>
<p>The next step is to remove the impossible words from the in-memory dictionary.
This is handled by <code>L()</code>. <code>L()</code> iterates over all the remaining words in the
dictionary. <code>L()</code> runs a number of filters, and if the word is plausible,
it is skipped, and if impossible, the current word is replaced from the end
of the list. This prevents holes from appearing in the dictionary, and keeps
the count accurate. The important action is carried out in the expression
<code>o ? W(t[l], t[--s]) : ++l</code>. That is, if <code>o</code> is true, the word is replaced
by the end of the list, else the word is skipped. Note in particular the
expressions <code>--s</code> and <code>++l</code> (decrement and replace, or skip, respectively).</p>
<p>Said another way, think of <code>W()</code> as an analog of <code>strncpy()</code>. Thus, if <code>o</code>
is true, then <code>strncpy(t[l], t[--s], 5)</code>, which overwrites the current word
with the end of the list, and decrements the number of entries. Note the
end of the list is not <code>t[s]</code>, but <code>t[s-1]</code>, thus the pre-decrement achieves
both the desired index and decrements the count.</p>
<h2 id="word-selection">Word Selection</h2>
<p>After the words are filtered, then comes the hard part: selecting which word
to guess next! This is handled by <code>E()</code>, by far the most interesting routine
in the code.</p>
<p>The loops in order:</p>
<ul>
<li>init <code>c[]</code> with ordinal values (a-z plus 6 slop) in the lower 5 bits</li>
<li>in the higher order bits, count the frequency of all remaining letters</li>
<li>sort by the frequency of letters in 3 sets of 7 (21 not 26!)</li>
<li>merge the separate sorts into one via <code>v()</code> (see below on merging)</li>
<li>for letters with same freq, re-sort by English frequency values <code>l()</code></li>
<li>using the sorted list, put the corresponding ordinals into <code>b[]</code></li>
<li>for each word, if scores below 97, put into <code>e[][]</code> (low score wins)</li>
<li>allow up to 5 duplicate scores, only keep first 5 words with same score</li>
<li>search the list for the lowest scoring word (best match)</li>
<li>if more than 2 words remain, find first word without duplicate letters</li>
<li>return whatever we found, if anything</li>
</ul>
<p>The weakness in this scheme is at least two-fold: 1) if there are more than 5
words with the same score, words that come later are not selected, and 2) all
words with the same score are considered the same, without regard to letter
order or letter frequencies. I have run no experiments here,
but I think this is an area for minor improvement.</p>
<h2 id="network-sort">Network Sort</h2>
<p>Network sort<a href="https://en.wikipedia.org/wiki/Sorting_network">1</a> is a simple, compact, constant time sort with minimal compares.</p>
<p>It is obfuscated in a number of ways.
The routine <code>S()</code> looks into the array <code>a[]</code> and determines the number of
elements to sort via the differences in the initial values of <code>a[]</code>.
Consider the possible number of values given in <code>O</code> from 0 (zero) to 7:
if <code>O</code> is 0 or 1, no sort is necessary (an empty list cannot be sorted,
and a list of one does not need to be sorted):</p>
<pre><code> O+1 O
a[1] - a[0] = 9 - 9 = 0
a[2] - a[1] = 9 - 9 = 0
a[3] - a[2] = 10 - 9 = 1</code></pre>
<p>If <code>O</code> is 2, then only one compare and swap is necessary. Why is this?
Consider how many compares are necessary to determine the proper order of
variables A and B: one test and one possible swap are all that is needed.
If A &gt; B, swap. If A &lt;= B, then no swap and the list is already ordered.</p>
<p>Where is this calculation done? Address arithmetic FTW!
<code>e = a[-~O] + s - a[O]</code>. <code>-~O</code> is the identity <code>O+1</code>.
So this expression restated is <code>e = s + a[O+1] - a[O]</code>.
If you look at the first numbers in <code>a[]</code> and their offsets (table 1):</p>
<pre><code> table 1
offsets: 0 1 2 3 4 5 6 7 8
values : 9 9 9 10 13 18 27 39 55</code></pre>
<p>You can see the expression selects for O in 0..7 (table 2):</p>
<pre><code> // table 2
a[0+1] - a[0] = 9 - 9 = 0 // 0 selects no compares
a[1+1] - a[1] = 9 - 9 = 0 // 1 selects no compares
a[2+1] - a[2] = 10 - 9 = 1 // 2 selects 1 compare
a[3+1] - a[3] = 13 - 10 = 3 // 3 selects 3 compares
a[4+1] - a[4] = 18 - 13 = 5 // 4 selects 5 compares
a[5+1] - a[5] = 27 - 18 = 9 // 5 selects 9 compares
a[6+1] - a[6] = 39 - 27 = 12 // 6 selects 12 compares
a[7+1] - a[7] = 55 - 39 = 16 // 7 selects 16 compares</code></pre>
<p>What are we comparing? <code>s</code> ranges from <code>&amp;a[a[O]]</code> to <code>&amp;a[a[O+1]]</code>.</p>
<pre><code> O expr
0 9 - 9 = 0: no compares
1 9 - 9 = 0: no compares
2 10 - 9 = 1: &amp;a[a[9]] + 1 or the set { 1 }
3 13 - 10 = 3: &amp;a[a[10]] + 3 or the set { 18, 2, 1 }
4 18 - 13 = 5: &amp;a[a[13]] + 5 or the set { 1, 35, 2, 19, 18 }
...
7 55 - 39 = 16: &amp;a[a[39]] + 16 or the set
{ 18, 52, 86, 2, 53, 70, 1, 69,
38, 4, 21, 3, 37, 19, 36, 35 }</code></pre>
<p>So what do these numbers mean for sorting? Translate them to hex:</p>
<pre><code> { 0x12, 0x34, 0x56, 0x02, 0x35, 0x46, 0x01, 0x45,
0x26, 0x04, 0x15, 0x03, 0x25, 0x13, 0x24, 0x23 }</code></pre>
<p>This compact arrangement can be split into high and low nibbles:</p>
<pre><code> { (1,2), (3,4), (5,6), (0,2), (3,5), ... }</code></pre>
<p>which means compare and maybe swap (keeping order low to high):</p>
<pre><code> if (s[1] &gt; s[2]) swap();
if (s[3] &gt; s[4]) swap();
if (s[5] &gt; s[6]) swap();
if (s[0] &gt; s[2]) swap();
if (s[3] &gt; s[5]) swap();
....</code></pre>
<p>For instance, when sorting 7 elements, start from <code>a[a[7]]</code> (39) until
<code>a[a[8]]</code> (55), or 16 elements starting at <code>a[39]</code>.</p>
<h2 id="the-array-a-explained-finally">The Array a[] Explained, Finally</h2>
<p>The first set of 9 numbers are both the lengths AND the start and end indexes
into the array <code>a[]</code>, as explained above in the Network Sort. The second set
of numbers runs from indexes 9 through 54, and are the Network Sort comparison
values. At index 55 begins the third part of the array. The final 26 values
encode the inverse frequency of letters in the English language. The first
value is 25 for the letter ‘a’. If you count, then 26 is for the letter ‘e’,
the most common letter in the English language
(or at least for the dictionary used).</p>
<p>This final set of letters is used in the routine <code>l()</code>. Notice the expression:
<code>a[f[j] + a[~-9]]</code>; <code>a[~-9]</code> is an obscure way of writing <code>a[8]</code>, which is the
value 55. So <code>a[f[j]]</code> is an index into this frequency array, offset by 55.
Why is there a <code>&lt;&lt; 5</code>? Again, the letter offsets are in the lowest 5 bits,
and the counts of the letters is in the upper bits.</p>
<p>The reason for putting the counts in the upper bits is simple: it makes the
value larger for larger counts. Thus, sorting based upon frequency is natural.</p>
<h2 id="merge-sort">Merge Sort</h2>
<p>The network sort as implemented handles up to 7 letters in 3 calls.
26 / 7 = 3 r 5. Thus, we need to merge up to 4 sets of 7 letters.
This merge is handled by <code>v()</code>, which calls <code>o()</code> 3 times, once recursively.
This is followed by a rearrangement handled in <code>l()</code>. This last step finds
all the letters with the same frequency, then sorts them according to their
English frequency.</p>
<p>Back to the merge sort, which is really handled in <code>o()</code>. This is rather
difficult to follow. The first call to <code>o()</code> is within the argument list
to the second call. The first call has arguments
W=0, O=1, R=0, D=a, L=w, E=k; and <code>v()</code> was called with <code>v(l=7, w=b, k=c)</code>.
This first merge pass copies to: <code>L[R]</code> (<code>b[0]</code>) and selects from either
<code>c[o]</code> or <code>c[w]</code> depending upon which is greater or equal. That is, it merges
two 7 letter arrays into a single 14 element array twice, then it merges two 14
element arrays into a single 28 element array. Note on the third call
to <code>o()</code>, the last two arguments are swapped, which puts the final sort
into <code>c[]</code>.</p>
<p>Below is a hopefully easier way to read the merge sort code:</p>
<pre><code> // merge residual
int e(int mult_o, int start, int to, int off, int *a1, int *a2)
{
for (; start &lt; off; )
a1[to++] = a2[start++ + off * mult_o];
return to;
}
// merge sort
int o(int mult_o, int mult_w, int to, int len, int *a1, int *a2)
{
// first call: mult_o = 0, mult_w = 1, to = 0, len = 7, a1=b, a2=c
// second: mult_o = 2, mult_w = 3, to = N, len = 7, a1=b, a2=c
// third: mult_o = 0, mult_w = 1, to = 0, len = 14, a1=c, a2=b
int o = 0, w = 0;
for (; o &lt; len &amp;&amp; w &lt; len; ) {
// first call: to=0, len=7, mult_o=0, mult_w=1
// a1[0++] = a2[0 + 7*0] &gt;= a2[0 + 7*1]
// ? a2[0 + 7*0] : a2[0 + 7*1]
// a1[0++] = a2[0] &gt; a2[7] ? a[0++] : a2[7++]
// second call: to=14, len=7, mult_o=2, mult_w=3
// a1[14++] = a2[0 + 7*2] &gt;= a2[0 + 7*3]
// ? a2[0 + 7*2] : a2[0 + 7*3]
// a1[14++] = a2[14] &gt; a2[21] ? a2[14++] : a2[21++]
// third call: to=0, len=14, mult_o=0, mult_w=1
// a1[0++] = a2[0 + 14*0] &gt;= a2[0 + 14*1]
// ? a2[0 + 14*0] : a2[0 + 14*1];
// a1[0++] = a[0] &gt;= a2[14] ? a2[0++] : a2[14++]
a1[to++] = a2[o + len * mult_o] &gt;= a2[w + len * mult_w]
? a2[o++ + len * mult_o]
: a2[w++ + len * mult_w]
}
int n = e(mult_o, o, to, len, a1, a2);
return e(mult_w, w, n, len, a1, a2);
}</code></pre>
<p>Isn’t that as clear as mud? It is far easier to understand the flow when
you add <code>printf()</code> statements to follow the logic. Included is the file
<code>deobfuscated.c</code> for you to start with.</p>
<h2 id="why-name-the-functions-as-they-are">Why name the functions as they are?</h2>
<p>Run <code>make spoiler</code>.</p>
<h2 id="bug-explained">Bug Explained</h2>
<p>If you followed the above explanation, you will notice that only the first
21 of 26 letters are sorted (ignoring { v, w, x, y, z }. But 28 of 26 letters
are merge sorted. It was observed the program performs worse if all 26 letters
are sorted (which tends to over-favor <code>y</code>).
But some words do have <code>y</code> in them, which is why the merge sort takes 28
letters (including the ASCII values <code>{</code> and <code>|</code>), so all letters are still
selected when appropriate. The merge sort puts the { v, w, x, y, z }
letters into the proper frequency set, eventually.</p>
<p>If you change the loop value <code>22</code> to <code>32</code>, then all letters are sorted,
the program will work correctly, but it will change the performance
of the algorithm to be slightly worse than the original.</p>
<p>If you change any values in the array <code>a[]</code>,
the program will no longer work correctly.</p>
<p>Finally, what is the significance of the array size 78557?
<code>usdw</code> only needs 8506. Why was such a large value used?
<!-- AFTER: last line of markdown file: 2024/burton/deobfuscated.md --></p>
<!-- END: this line ends content for HTML phase 21 by: bin/pandoc-wrapper.sh via bin/md2html.sh -->
<!-- START: this line starts content from: inc/after-content.default.html -->
</div>
<!-- END: this line ends content from: inc/after-content.default.html -->
<!-- START: this line starts content from: inc/footer.default.html -->
<!--
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/
-->
<div class="footer">
<div id="copyright"><h3>Copyright &copy; 1984-2025 by Landon Curt Noll:
<a href="https://creativecommons.org/faq/#what-does-some-rights-reserved-mean"
target="_blank"
rel="license noopener noreferrer">Some Rights Reserved</a></h3>
<p>
This work is <b>licensed by Landon Curt Noll</b> under
<b><a href="https://creativecommons.org/licenses/by-sa/4.0/?ref=chooser-v1"
target="_blank"
rel="license noopener noreferrer"
style="display:inline-block;">CC BY-SA 4.0</a></b>.
<img style="height:22px!important;margin-left:3px;vertical-align:text-bottom;"
src="../../png/cc.png"
alt="cc inside circle symbol">
<img style="height:22px!important;margin-left:3px;vertical-align:text-bottom;"
src="../../png/by.png"
alt="person inside circle symbol">
<img style="height:22px!important;margin-left:3px;vertical-align:text-bottom;"
src="../../png/sa.png"
alt="arrow looping back on itself inside circle symbol"><br>
You should <b>carefully review</b> the
<b><a href="https://creativecommons.org/licenses/by-sa/4.0/legalcode.en"
target="_blank"
rel="license noopener noreferrer">CC BY-SA 4.0 LEGAL CODE</a></b>
before using the licensed material.<br>
You may wish to review the
<b><a href="../../license.html"
target="_blank"
rel="license noopener noreferrer">highlights of some of the key features and terms</a></b>
of <b>CC BY-SA 4.0</b>.<br>
</p>
</div>
<div id="coda"><h3>Coda</h3>
<p>
<a href="https://validator.w3.org/nu/?doc=https%3A%2F%2Fwww.ioccc.org%2F2024%2Fburton%2Fdeobfuscated.html" rel="nofollow">Nu HTML check this web page</a><br>
<a href="#top">Jump to top</a> <a href="#content">Jump to Content</a>
</p>
</div>
</div>
<!-- END: this line ends content from: inc/footer.default.html -->
<!-- START: this line starts content from: inc/bottom.default.html -->
</body>
</html>
<!-- END: this line ends content from: inc/bottom.default.html -->