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
815 lines
33 KiB
HTML
815 lines
33 KiB
HTML
<!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">↑ jump to 2024/burton/index.html ↑</a>
|
||
<a class="Right" href="https://validator.w3.org/nu/?doc=https%3A%2F%2Fwww.ioccc.org%2F2024%2Fburton%2Fdeobfuscated.html">✓</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 < 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>&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 < 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 < 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 > 0 ? 1 : 0;
|
||
filter(input, num_green);
|
||
return choose("xyzzy");
|
||
}</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 > B, swap. If A <= 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>&a[a[O]]</code> to <code>&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: &a[a[9]] + 1 or the set { 1 }
|
||
3 13 - 10 = 3: &a[a[10]] + 3 or the set { 18, 2, 1 }
|
||
4 18 - 13 = 5: &a[a[13]] + 5 or the set { 1, 35, 2, 19, 18 }
|
||
...
|
||
7 55 - 39 = 16: &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] > s[2]) swap();
|
||
if (s[3] > s[4]) swap();
|
||
if (s[5] > s[6]) swap();
|
||
if (s[0] > s[2]) swap();
|
||
if (s[3] > 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><< 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 < 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 < len && w < len; ) {
|
||
|
||
// first call: to=0, len=7, mult_o=0, mult_w=1
|
||
// a1[0++] = a2[0 + 7*0] >= a2[0 + 7*1]
|
||
// ? a2[0 + 7*0] : a2[0 + 7*1]
|
||
// a1[0++] = a2[0] > a2[7] ? a[0++] : a2[7++]
|
||
|
||
// second call: to=14, len=7, mult_o=2, mult_w=3
|
||
// a1[14++] = a2[0 + 7*2] >= a2[0 + 7*3]
|
||
// ? a2[0 + 7*2] : a2[0 + 7*3]
|
||
// a1[14++] = a2[14] > a2[21] ? a2[14++] : a2[21++]
|
||
|
||
// third call: to=0, len=14, mult_o=0, mult_w=1
|
||
// a1[0++] = a2[0 + 14*0] >= a2[0 + 14*1]
|
||
// ? a2[0 + 14*0] : a2[0 + 14*1];
|
||
// a1[0++] = a[0] >= a2[14] ? a2[0++] : a2[14++]
|
||
|
||
a1[to++] = a2[o + len * mult_o] >= 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 © 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 -->
|