The navigation bar for a winning entry now has a "_Original C_" link
(between the ✅ and the Inventory on the right hand side) so that one
may easily view the original C code that was submitted for IOCCC judging.
Ran `make www timestamp` to perform the above.
1204 lines
54 KiB
HTML
1204 lines
54 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>2015/schweikhardt - Best documented</title>
|
||
<link rel="icon" type="image/x-icon" href="../../favicon.ico">
|
||
<meta name="description" content="2015 IOCCC entry schweikhardt - Best documented">
|
||
<meta name="keywords" content="IOCCC, 2015, IOCCC 2015, IOCCC entry, schweikhardt, Best documented">
|
||
</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/readme2index.sh -->
|
||
<!-- The content of main section of this web page came from: 2015/schweikhardt/README.md -->
|
||
<!-- -->
|
||
|
||
<!-- !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! -->
|
||
<!-- !!! Do not modify this web page, instead modify the file: 2015/schweikhardt/README.md !!! -->
|
||
<!-- !!! Do not modify this web page, instead modify the file: 2015/schweikhardt/README.md !!! -->
|
||
<!-- !!! Do not modify this web page, instead modify the file: 2015/schweikhardt/README.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>2015/schweikhardt - Best documented</h2>
|
||
<h3>Collatz bignum computation</h3>
|
||
</div>
|
||
|
||
<!-- END: this line ends content from: inc/header.default.html -->
|
||
<!-- START: this line starts content from: inc/navbar.mid.html -->
|
||
|
||
<div class="navbar">
|
||
<a class="Left" href="../muth/index.html">← 2015/muth</a>
|
||
<a class="Left" href="../index.html">↑ 2015 ↑</a>
|
||
<a class="Left" href="../yang/index.html">2015/yang →</a>
|
||
<a class="Right" href="https://github.com/ioccc-src/winner/blob/master/2015/schweikhardt/prog.c">C code</a>
|
||
<a class="Right" href="https://github.com/ioccc-src/winner/blob/master/2015/schweikhardt/Makefile">Makefile</a>
|
||
<a class="Right" href="#inventory">Inventory</a>
|
||
<a class="Right" href="https://github.com/ioccc-src/winner/blob/master/2015/schweikhardt/prog.orig.c">Original C</a>
|
||
<a class="Right" href="https://validator.w3.org/nu/?doc=https%3A%2F%2Fwww.ioccc.org%2F2015%2Fschweikhardt%2Findex.html">✓</a>
|
||
</div>
|
||
|
||
<!-- END: this line ends content from: inc/navbar.mid.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 20 by: bin/output-index-author.sh via bin/md2html.sh -->
|
||
|
||
<!-- START: this line starts content generated by: bin/output-index-author.sh -->
|
||
|
||
<h2 id="author">Author:</h2>
|
||
<ul>
|
||
<li>Name: <a href="../../authors.html#Jens_Schweikhardt">Jens Schweikhardt</a><br>
|
||
Location: <a href="../../location.html#DE">DE</a> - <em>Federal Republic of Germany</em> (<em>Germany</em>)</li>
|
||
</ul>
|
||
|
||
<!-- END: next line ends content generated by: bin/output-index-author.sh -->
|
||
|
||
<!-- END: this line ends content for HTML phase 20 by: bin/output-index-author.sh via bin/md2html.sh -->
|
||
<!-- START: this line starts content for HTML phase 21 by: bin/pandoc-wrapper.sh via bin/md2html.sh -->
|
||
|
||
<!-- BEFORE: 1st line of markdown file: 2015/schweikhardt/README.md -->
|
||
<h2 id="to-build">To build:</h2>
|
||
<pre><code> make</code></pre>
|
||
<h3 id="bugs-and-misfeatures">Bugs and (Mis)features:</h3>
|
||
<p>The current status of this entry is:</p>
|
||
<blockquote>
|
||
<p><strong>STATUS: INABIAF - please DO NOT fix</strong></p>
|
||
</blockquote>
|
||
<p>For more detailed information see <a href="../../bugs.html#2015_schweikhardt">2015/schweikhardt in bugs.html</a>.</p>
|
||
<h2 id="to-use">To use:</h2>
|
||
<pre><code> ./prog n</code></pre>
|
||
<p>where <code>n</code> is a base 16 number of any size.</p>
|
||
<p><strong>NOTE</strong>: although it’s supposed to be a base 16 number nothing will stop you from
|
||
doing something else. The author explains this in more details.</p>
|
||
<h2 id="try">Try:</h2>
|
||
<pre><code> ./try.sh</code></pre>
|
||
<p>After running it once to see what commands are run, you might wish to run it a
|
||
second time and just hold down space to see a fun scroll of numbers especially
|
||
where zeroes move to the right.</p>
|
||
<h2 id="judges-remarks">Judges’ remarks:</h2>
|
||
<p>This code is clean. When you compile with all warnings enabled,
|
||
such as with clang:</p>
|
||
<pre><code> cc -Weverything -pedantic -std=c11 -Dtyp=uint64\_t -O3 prog.c -o prog</code></pre>
|
||
<p>The code compiles without warnings on the systems that we tested!</p>
|
||
<p>Even more, the code was 100% clean when we ran it against various
|
||
static source checkers.</p>
|
||
<p>This tool references a problem that <a href="http://members.tip.net.au/~dbell/">David I.
|
||
Bell</a> once described
|
||
as having one of the largest “yummo quotients” in number theory:</p>
|
||
<pre><code> complexity of the solution
|
||
yummo quotient = -----------------------------------
|
||
complexity of the problem statement</code></pre>
|
||
<p><a href="https://en.wikipedia.org/wiki/Paul_Erdős">Erdős</a> privately told one of the IOCCC judges:</p>
|
||
<p>Solving the <a href="https://en.wikipedia.org/wiki/Generalized_Riemann_hypothesis#Extended_Riemann_hypothesis_.28ERH.29">Generalized Riemann
|
||
hypothesis</a>
|
||
would be a good warm-up exercise for someone to get ready to begin to work on
|
||
the <a href="https://en.wikipedia.org/wiki/Collatz_conjecture">Collatz conjecture</a>.</p>
|
||
<p>You may explore this famous conjecture using this entry:</p>
|
||
<pre><code> ./prog 2410
|
||
./prog abfff
|
||
./prog 27f8cebf
|
||
./prog 246f8fddf
|
||
./prog 2e95ab51ffea9de
|
||
./prog e6a5c22fd7bde9f
|
||
./prog 1b7dd73a937485bf
|
||
./prog 7d3237680d190a77e53751b
|
||
./prog 302ab3d052fb87c06228d249581be0e4</code></pre>
|
||
<p><strong>NOTE</strong>: <a href="https://github.com/ioccc-src/winner/blob/master/2015/schweikhardt/try.sh">try.sh</a> runs these for you, filtered through <code>less(1)</code>.</p>
|
||
<p>When you first look at the source, the code looks fairly straightforward.
|
||
But look again. Like the Collatz conjecture, simplicity is deceptive!
|
||
Oh, and the variable names? They are not simple single letter variables,
|
||
they are names of various <a href="https://en.wikipedia.org/wiki/Proteinogenic_amino_acid">Proteinogenic amino
|
||
acid</a>:
|
||
which is yet another simple building block that can be used to
|
||
build some very complex structures. :-)</p>
|
||
<p>p.s. We appreciated that apart from a few powers of 2, the source
|
||
code is magic number free.</p>
|
||
<h2 id="authors-remarks">Author’s remarks:</h2>
|
||
<h3 id="the-tldr-version">The TL;DR version</h3>
|
||
<p>This is the cleanest program ever submitted. If for some input it enters
|
||
a non-terminating loop or runs out of memory you will be insta-famous.
|
||
It’s a bit like a lottery without the need to buy a ticket and you can
|
||
play as often as you like. One notable historic person has even offered
|
||
some prize money.</p>
|
||
<p>The program illustrates the bloat caused by adherence to too many rules,
|
||
each of which may sound sane in isolation, but in their entirety lead to
|
||
an obfuscated, hard to read and understand monster.</p>
|
||
<h3 id="what-this-program-does.">What this program does.</h3>
|
||
<p>The program tests whether a given natural number satisfies the
|
||
<a href="https://en.wikipedia.org/wiki/Collatz_conjecture">Collatz Conjecture</a>:</p>
|
||
<p>Take any natural number <code>n</code>. If <code>n</code> is even, divide it by <code>2</code> to get <code>n/2</code>. If
|
||
<code>n</code> is odd, multiply it by <code>3</code> and add <code>1</code> to obtain <code>3n + 1</code>. Repeat the
|
||
process indefinitely.</p>
|
||
<p>The conjecture is that no matter what number you start with,
|
||
you eventually reach <code>1</code>.</p>
|
||
<p>Paul Erdős said about the Collatz conjecture:</p>
|
||
<pre><code> "Mathematics may not be ready for such problems."</code></pre>
|
||
<p>He also offered $500 for its solution.</p>
|
||
<p>For example, the sequence of numbers for <code>n</code> = 6 is</p>
|
||
<pre><code> 6, 3, 10, 5, 16, 8, 4, 2, 1.</code></pre>
|
||
<p>Continuing past one leads to the <em>cycle</em> 1, 4, 2, 1, 4, 2, 1, …
|
||
Interesting factoid: if you allow <em>negative</em> start values, there are
|
||
a few more cycles, each of different length:</p>
|
||
<pre><code> −1, −2, −1
|
||
|
||
−5, −14, −7, −20, −10, −5
|
||
|
||
−17, −50, −25, −74, −37, −110, −55, −164,
|
||
−82, −41, −122, −61, −182, −91, −272, −136,
|
||
−68, −34, −17</code></pre>
|
||
<p>The program computes the sequence for a given positive natural number
|
||
and stops at <code>1</code>. The number <code>n</code> is specified in hexadecimal (without <code>0x</code>
|
||
prefix) as the first argument. The program prints the given number in
|
||
zero-padded hex and each iteration along with a line count in decimal.
|
||
The example above looks like this (compiled with 64 bit word size):</p>
|
||
<pre><code> $ ./prog 6
|
||
0000000000000006
|
||
0000000000000003 1
|
||
000000000000000A 2
|
||
0000000000000005 3
|
||
0000000000000010 4
|
||
0000000000000008 5
|
||
0000000000000004 6
|
||
0000000000000002 7
|
||
0000000000000001 8</code></pre>
|
||
<p>The size of <code>n</code> is only limited by the argument size limit of your
|
||
shell/OS (the program implements arbitrary size <code>bignum</code>s).
|
||
To query this on your POSIX system, run</p>
|
||
<pre><code> $ getconf ARG_MAX
|
||
262144</code></pre>
|
||
<p>which reports the limit in bytes, here 256KB. This allows to test
|
||
whether a <a href="https://en.wikipedia.org/wiki/Googol">Googol</a>, which is
|
||
10<sup>100</sup>, satisfies the conjecture. But what is a googol in hex?
|
||
Fear not,
|
||
<a href="http://pubs.opengroup.org/onlinepubs/9699919799/utilities/bc.html">bc()</a>
|
||
to the rescue:</p>
|
||
<pre><code> $ printf 'obase=16;10^100\n' | bc
|
||
1249AD2594C37CEB0B2784C4CE0BF38ACE408E211A7CAAB24308A82E8F10000000000000000000000000
|
||
$ ./prog 1249AD2594C37CEB0B2784C4CE0BF38ACE408E211A7CAAB24308A82E8F10000000000000000000000000 | less
|
||
[...]</code></pre>
|
||
<p>Observe how the first 100 iterations melt the zeros to the right. Can you explain
|
||
why?</p>
|
||
<p>For a given <code>n</code> the program behavior is one of the following 3:</p>
|
||
<ol type="1">
|
||
<li>The sequence stops at 1. No fame. No money. Thanks for playing. Computational
|
||
mathematicians have tested all <code>n < 4FFDD776055A0000</code> (~10<sup>18</sup>) so
|
||
don’t try anything less than that.</li>
|
||
<li>The chosen <code>n</code> leads to a sequence with ever bigger numbers, so that
|
||
eventually the <code>bignum</code> cannot be stored in memory. If this happens, the program
|
||
outputs <code>laugh</code> (more likely) or <code>throw up</code> (less likely) and stops. You <em>might</em>
|
||
have found a number for which the sequence <em>diverges</em>. If confirmed, this
|
||
disproves the conjecture.</li>
|
||
<li>The chosen <code>n</code> leads to a cycle not including 1 (i.e. runs forever, repeating
|
||
the same sequence over and over). You have disproved the conjecture and should
|
||
certainly submit a paper to the nearest mathematical journal.</li>
|
||
</ol>
|
||
<h3 id="design-objectives">Design objectives</h3>
|
||
<p>I gave myself the following objectives. Like in real world programming,
|
||
not all of them can be met 100%. Think of them as a multidimensional
|
||
continuum, where trade-offs have to be made.</p>
|
||
<ol type="1">
|
||
<li>No arbitrary limits on the input number. 64 bits might be enough
|
||
for everybody, but is not enough for exploring new Collatz-territory.
|
||
Thus <code>bignums</code> are required.</li>
|
||
<li>Ultra-portable. Must run on C89 systems and self-adapt to C99 and C11
|
||
features like exact width types.</li>
|
||
<li>Super-efficient. Must be able to run with the widest type as the
|
||
base of the <code>bignums</code>. Make the user select the widest type supported
|
||
by the implementation and then crunch away. If a non-standard
|
||
128bit type is available, it should be usable.</li>
|
||
<li>Pentagon level lint cleanliness and MISRA compliance.</li>
|
||
<li>Easy to understand, self-documenting clear code. A joy for maintenance
|
||
programmers. The epitome of best practice demonstration for all
|
||
future textbooks on C.</li>
|
||
</ol>
|
||
<h3 id="program-obfuscation">Program Obfuscation</h3>
|
||
<p>In the following I address all the <em>tests</em> as specified by your honors in the
|
||
<em>guidelines</em>.</p>
|
||
<ul>
|
||
<li>look at the original source</li>
|
||
<li>convert ANSI trigraphs to ASCII</li>
|
||
<li>C pre-process the source ignoring <code>#include</code> lines</li>
|
||
<li>C pre-process the source ignoring <code>#define</code> and <code>#include</code> lines</li>
|
||
<li>run it through a C beautifier</li>
|
||
<li>examine the algorithm</li>
|
||
<li>compile it (with flags to enable all warnings)</li>
|
||
<li>execute it</li>
|
||
</ul>
|
||
<h3 id="look-at-the-original-source">Look at the original source</h3>
|
||
<p>Using one letter identifiers is quite old. I decided to use TLI (three
|
||
letter identifiers). Not the random kind, rather with a connection to
|
||
the meaning of life, the universe and the rest. Enter amino acids! Among
|
||
the myriad of possible amino acids there are 23 from which proteins are
|
||
built. In biochemistry, each is assigned a TLI (see <a href="https://en.wikipedia.org/wiki/Proteinogenic_amino_acid">Proteinogenic amino
|
||
acid</a> for more info):</p>
|
||
<pre><code> ala Alanine
|
||
cys Cysteine
|
||
asp Aspartic acid
|
||
glu Glutamic acid
|
||
phe Phenylalanine
|
||
gly Glycine
|
||
his Histidine
|
||
ile Isoleucine
|
||
lys Lysine
|
||
leu Leucine
|
||
met Methionine
|
||
asn Asparagine
|
||
pyl Pyrrolysine
|
||
pro Proline
|
||
gln Glutamine
|
||
arg Arginine
|
||
ser Serine
|
||
thr Threonine
|
||
sec Selenocysteine
|
||
val Valine
|
||
trp Tryptophan
|
||
tyr Tyrosine
|
||
asx Asparagine or Aspartic acid
|
||
glx Glutamic acid or Glutamine
|
||
xle Leucine or Isoleucine
|
||
unk Unknown</code></pre>
|
||
<p>My own research results complete this list (not yet in Wikipedia due to
|
||
the rule “<a href="https://en.wikipedia.org/wiki/Wikipedia:No_original_research">No original
|
||
research</a>”):</p>
|
||
<pre><code> and Androgynine
|
||
xor Xenoricine
|
||
not Notanamine
|
||
tla Triletramine</code></pre>
|
||
<p>Interestingly, the TLI are the perfect mnemonics for C language source.
|
||
For example, <code>met</code> is “<code>main()'s Exit Type</code>” (<code>int</code>), <code>ala</code> is “<code>A Large Algebraic</code>” (<code>bignum</code>), <code>ile</code> an “<code>Incremented Local Entity</code>” (index
|
||
counter), <code>gly</code> means “<code>Grow Larger memorY</code>”, <code>gln</code> is “<code>Grown Larger Now</code>”
|
||
(after <code>realloc(3)</code>), <code>not</code> is a “<code>Not Overflowing Type</code>” (recursive!), <code>unk</code>
|
||
is the “<code>UNit (Known as 1)</code>”, <code>trp</code> is the “<code>Tabula Rasa Product</code>” (zero),
|
||
<code>phe</code> is “<code>Print HEx</code>” and so on.</p>
|
||
<h3 id="convert-ansi-trigraphs-to-ascii">Convert ANSI trigraphs to ASCII</h3>
|
||
<p>Huh??!</p>
|
||
<h3 id="c-pre-process-the-source-ignoring-include-lines">C pre-process the source ignoring <code>#include</code> lines</h3>
|
||
<p>Wow, an identity operation (except for the <code><stdint.h></code> and <code>EOF + __STDC__</code>
|
||
trivialities). Did you gain any insight through this?</p>
|
||
<h3 id="c-pre-process-the-source-ignoring-define-and-include-lines">C pre-process the source ignoring ‘#define’ and ‘#include’ lines</h3>
|
||
<p><code>#define</code>? Which <code>#define</code> directives? How many 4K source files do you
|
||
see that don’t use a single <code>#define</code> directive <em>or</em> abuse the build
|
||
file? Even though the “no <code>#define</code>” rule I submitted myself to made it
|
||
hard, I could use <code>__LINE__</code> and <code>stdio.h</code> macros <code>EOF</code>, <code>L_tmpnam</code>,
|
||
<code>BUFSIZ</code>, <code>FILENAME_MAX</code>, <code>TMP_MAX</code> to obfuscate at least something.</p>
|
||
<h3 id="run-it-through-a-c-beautifier">Run it through a C beautifier</h3>
|
||
<p>Another identity operation. I’ve done it for you already. Use this
|
||
<code>.indent.pro</code> with FreeBSD indent:</p>
|
||
<pre><code> $ cat .indent.pro
|
||
-bad /* blank line after decls */
|
||
-bap /* blank line after functions */
|
||
-br /* braces on if line */
|
||
-i8 /* indent */
|
||
-l999 /* line length */
|
||
-npcs /* no space after function call names */
|
||
-npsl /* don't break procedure type */
|
||
-ut /* use tabs */
|
||
-ce /* cuddle else */
|
||
-nip /* no parameter indentation */
|
||
-di1 /* declaration indent */
|
||
-Tand
|
||
-Tmet
|
||
-Tthr
|
||
-Tpro
|
||
-Tser
|
||
-Tala</code></pre>
|
||
<p>It looks like a perfect program should have:</p>
|
||
<ul>
|
||
<li>two and a half <code>#include</code>s of non-suspicious standard headers</li>
|
||
<li>followed by self protection against goofy implementations</li>
|
||
<li>followed by a handful of <code>typedef</code>s</li>
|
||
<li>and a pair of file scope objects by necessity</li>
|
||
<li>prototypes! With parameter names! <code>static</code> for internal linkage even! This <strong>must</strong> be a first in IOCCC history.</li>
|
||
<li>function definitions, <code>main</code> last</li>
|
||
<li>everything is fully <code>const</code>-poisoned: automatics, statics, arguments, even <code>main</code></li>
|
||
<li>everything is fully curly braced, even single statements</li>
|
||
<li>plenty of meaningful TLC (Three Letter Comments)</li>
|
||
</ul>
|
||
<p>The program contains not a single <em>magic number</em> (only 0 and powers of
|
||
2, each power from 1 to 512) which are obvious to competent software
|
||
engineers). How many programs have <em>that</em> property? The check for
|
||
<code>__STDC_VERSION__</code> was a bit tough to arrive at, since 199901L has too
|
||
many bits set. But I realized that I only needed a number larger than
|
||
199409 and less than 199901. 199680 has only 4 bits set and writing it
|
||
as <code>(256 + 128 + 4 + 2) * 512</code> minimizes the character count. That’s what
|
||
judges get when they don’t like programs that are longer than they need
|
||
to be.</p>
|
||
<h3 id="examine-the-algorithm">Examine the algorithm</h3>
|
||
<p>Obfuscation information ahead. Duh!</p>
|
||
<p>Pseudocode, with comments matching those in the C source:</p>
|
||
<pre><code> /* run */
|
||
if (non-NULL and nonempty argv[1]) {
|
||
n = convert(argv[1])
|
||
print n /* 2hx */
|
||
while (n != 1) { /* one */
|
||
if (n is odd) { /* odd */
|
||
m = deep copy of n /* cpy */
|
||
n <<= 1 /* shl */
|
||
n += m /* add */
|
||
increment n /* inc */
|
||
} else { /* eve */
|
||
n >>= 1 /* shr */
|
||
}
|
||
print n /* 2hx */
|
||
}
|
||
}</code></pre>
|
||
<p><code>Bignum</code>s are represented as the two member <code>struct</code>s:</p>
|
||
<pre><code> typedef struct {
|
||
size_t places; /* number of places in base 2 to the power of (8*sizeof(type)) */
|
||
type *number; /* dynamically allocated memory for number */
|
||
} bignum</code></pre>
|
||
<h3 id="compile-it-with-flags-to-enable-all-warnings">Compile it (with flags to enable all warnings)</h3>
|
||
<p>Here’s where the program shines brighter than a <a href="https://en.wikipedia.org/wiki/Gamma-ray_burst">gamma-ray
|
||
burst</a>!</p>
|
||
<p>I challenge you to throw all kinds of compilers, lints, checkers and
|
||
analyzers at my program and make it find the slightest of issues.</p>
|
||
<p>Is <code>clang -Wall -Wextra -Weverything -Dtyp=uint32_t prog.c</code> all you can
|
||
do? Clang has implemented a new warning? Bring it on!</p>
|
||
<h3 id="execute-it">Execute it</h3>
|
||
<p>May you win the jackpot!</p>
|
||
<p>For least surprising results, the execution character set should be ASCII. The
|
||
program computes four bits from every character in <code>argv[1]</code> and interprets them
|
||
as a hex digit. In ASCII the characters <code>a-f</code>, <code>A-F</code> and <code>0-9</code> are converted as
|
||
expected.</p>
|
||
<p>This means however, that the program accepts <strong>any string</strong>, turns it
|
||
into a starting number (which is output as the first line), and starts
|
||
crunching. Nothing stops you from executing</p>
|
||
<pre><code> ./prog "$(cat prog.c)" # Kind of quine?
|
||
./prog "$(cat rules guidelines)" # A jackpot? Maybe next year...
|
||
./prog "$(cat /bin/ls)" # Number cut short at first NUL byte.</code></pre>
|
||
<p>In a certain way, the program is character set and encoding agnostic.</p>
|
||
<h3 id="assumptions-made">Assumptions made</h3>
|
||
<ul>
|
||
<li>The <code>EOF</code> macro from <code><stdio.h></code> must expand to <code>-1</code> since it is used
|
||
to decrement a pointer and do some other math.
|
||
None of the tools catch this one. The program self-protects against unusual
|
||
systems with <code>#if EOF + __STDC__</code> followed by <code>#error goofy!</code>. In the rare event
|
||
your system is goofy, replace all <code>EOF</code> tokens with <code>(-1)</code> and remove the
|
||
<code>#error</code> directive.</li>
|
||
</ul>
|
||
<p>While the program works best when bytes/characters are octets and the
|
||
number of bits in a type is <code>sizeof(typ) << 3</code>, it will work correctly
|
||
on 24-bit or 36-bit systems with 9 bits/byte, or systems where
|
||
<code>sizeof(typ)</code> is 1 even for <code>int</code> and so on. On such systems, it will only
|
||
use <code>8 * sizeof(typ)</code> bits per place. It does not work when <code>CHAR_BIT <= 7</code>.</p>
|
||
<h3 id="results-of-various-checkers">Results of various checkers</h3>
|
||
<h3 id="cppcheck">cppcheck</h3>
|
||
<p>The open source static checker <a href="http://cppcheck.sourceforge.net/">cppcheck</a>
|
||
checks various problems with respect to style, performance, portability
|
||
and general fishiness. To enable all checks, run</p>
|
||
<pre><code> cppcheck --enable=all --force -I/usr/include -Dtyp=uint32_t prog.c</code></pre>
|
||
<p>No issues found.</p>
|
||
<h3 id="flawfinder">flawfinder</h3>
|
||
<p>The open source static checker <a href="http://www.dwheeler.com/flawfinder/">flawfinder</a>
|
||
checks various problems with respect to security like buffer overflows,
|
||
function arguments to known troublemaker functions and more. It doesn’t need to
|
||
pre-process code, so can be run without the <code>typ</code> macro being defined:</p>
|
||
<pre><code> $ flawfinder prog.c
|
||
Flawfinder version 1.31, (C) 2001-2014 David A. Wheeler.
|
||
Number of rules (primarily dangerous function names) in C/C++ ruleset: 169
|
||
Examining prog.c
|
||
FINAL RESULTS:
|
||
ANALYSIS SUMMARY:
|
||
No hits found.</code></pre>
|
||
<h4 id="valgrind">valgrind</h4>
|
||
<p>The open source dynamic checker <a href="http://valgrind.org/">valgrind</a> runs an
|
||
executable and verifies all memory accesses and (de)allocations for proper
|
||
bounds and memory leaks. Since the program frees all memory in all possible
|
||
execution paths, even when it must bail out, valgrind should be happy. An early
|
||
version of my program however reported this:</p>
|
||
<pre><code> valgrind --leak-check=full --show-leak-kinds=all ./prog 6
|
||
[...]
|
||
==14615== HEAP SUMMARY:
|
||
==14615== in use at exit: 4,096 bytes in 1 blocks
|
||
==14615== total heap usage: 4 allocs, 3 frees, 4,108 bytes allocated
|
||
==14615==
|
||
==14615== 4,096 bytes in 1 blocks are still reachable in loss record 1 of 1
|
||
==14615== at 0x4C236C0: malloc (in /usr/local/lib/valgrind/vgpreload_memcheck-amd64-freebsd.so)
|
||
==14615== by 0x4F62175: ??? (in /lib/libc.so.7)
|
||
==14615== by 0x4F62073: ??? (in /lib/libc.so.7)
|
||
==14615== by 0x4F514EE: ??? (in /lib/libc.so.7)
|
||
==14615== by 0x4F51265: vfprintf_l (in /lib/libc.so.7)
|
||
==14615== by 0x4F3E001: printf (in /lib/libc.so.7)
|
||
==14615== by 0x40101E: phe (in ./prog)
|
||
==14615== by 0x400A9F: main (in ./prog)
|
||
==14615==
|
||
==14615== LEAK SUMMARY:
|
||
==14615== definitely lost: 0 bytes in 0 blocks
|
||
==14615== indirectly lost: 0 bytes in 0 blocks
|
||
==14615== possibly lost: 0 bytes in 0 blocks
|
||
==14615== still reachable: 4,096 bytes in 1 blocks
|
||
==14615== suppressed: 0 bytes in 0 blocks
|
||
==14615==
|
||
==14615== For counts of detected and suppressed errors, rerun with: -v
|
||
==14615== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)</code></pre>
|
||
<p>From which I concluded that <code>printf(3)</code> allocated a single 4K block for
|
||
which no matching <code>free(3)</code> existed. But how to free memory allocated deep
|
||
down in the guts of the Standard I/O library? After some serious head
|
||
scratching it hit me. The only chance I have is telling the system I no
|
||
longer want to do I/O, maybe then it would free that buffer. A reading
|
||
of C99 7.19.5.1, “The fclose function”, was encouraging:</p>
|
||
<pre><code> Whether or not the call succeeds, the stream is disassociated from the file
|
||
and any buffer set by the `setbuf` or `setvbuf` function is disassociated from the stream
|
||
(and deallocated if it was automatically allocated).</code></pre>
|
||
<p>So I <code>fclose(stdout)</code> before returning and now:</p>
|
||
<pre><code> valgrind --leak-check=full --show-leak-kinds=all ./prog 6
|
||
==14571== Memcheck, a memory error detector
|
||
==14571== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
|
||
==14571== Using Valgrind-3.10.0 and LibVEX; rerun with -h for copyright info
|
||
==14571== Command: ./prog 6
|
||
==14571==
|
||
0000000000000006
|
||
0000000000000003 1
|
||
000000000000000A 2
|
||
0000000000000005 3
|
||
0000000000000010 4
|
||
0000000000000008 5
|
||
0000000000000004 6
|
||
0000000000000002 7
|
||
0000000000000001 8
|
||
==14571==
|
||
==14571== HEAP SUMMARY:
|
||
==14571== in use at exit: 0 bytes in 0 blocks
|
||
==14571== total heap usage: 4 allocs, 4 frees, 4,120 bytes allocated
|
||
==14571==
|
||
==14571== All heap blocks were freed -- no leaks are possible
|
||
==14571==
|
||
==14571== For counts of detected and suppressed errors, rerun with: -v
|
||
==14571== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)</code></pre>
|
||
<p>A squeaky clean valgrind result!</p>
|
||
<h4 id="flexelint">FlexeLint</h4>
|
||
<p>FlexeLint is a commercial lint tool by <a href="http://www.gimpel.com/html/index.htm">Gimpel
|
||
Software</a>. It supports nearly a
|
||
thousand checks, broadly categorized into 4 levels,</p>
|
||
<ol type="1">
|
||
<li>Syntax errors only (messages 1 to 399)</li>
|
||
<li>Warnings (messages 400 to 699)</li>
|
||
<li>Informational messages (700 to 899)</li>
|
||
<li>Elective notes (900 to 1000 and > 9000)</li>
|
||
</ol>
|
||
<p>There is an <a href="http://www.gimpel-online.com/OnlineTesting.html">on-line
|
||
demonstrator</a> you can
|
||
use for checking your C programs and I highly recommend trying it. For a start,
|
||
paste the well know first program in the form and press “Analyze Code”. Note
|
||
the FlexeLint configuration options in comments (no space between <code>/*</code> and <code>lint</code>).</p>
|
||
<pre><code> /*lint -w4 turn on everything */
|
||
/*lint +esym(534,*) no demonstrator defaults */
|
||
/*lint -e966 indirectly included header file not used */
|
||
/*lint -esym(9058,_*) tag not used outside typedef */
|
||
/*lint -misra(2) */
|
||
|
||
#include <stdio.h>
|
||
int main(void)
|
||
{
|
||
printf("hello, world\n");
|
||
return 0;
|
||
}</code></pre>
|
||
<p>Possible checks include those for MISRA 2004 compliance verification.
|
||
The <a href="https://en.wikipedia.org/wiki/Motor_Industry_Software_Reliability_Association">Motor Industry Software Reliability
|
||
Association</a>
|
||
has produced a <a href="http://doc.hcc-embedded.com/display/CODING/MISRA+Rules">list of 121 required and 20 advisory
|
||
rules</a> for C
|
||
programming. I am proud to report that my program fulfills <em>almost all</em>
|
||
rules. To assess the few exceptions, one has to understand that MISRA
|
||
rules are geared towards embedded systems used in the automotive
|
||
industry. That’s why features like <code>malloc(3)</code> and <code>printf(3)</code> are right out.
|
||
But that’s too restrictive for an IOCCC hosted application, so I ignored
|
||
these:</p>
|
||
<ul>
|
||
<li>17.1 Pointer arithmetic shall only be applied to pointers that address an array or array element.</li>
|
||
<li>17.4 Array indexing shall be the only allowed form of pointer arithmetic.</li>
|
||
<li>20.4 Dynamic heap memory allocation shall not be used.</li>
|
||
<li>20.9 The input/output library stdio.h shall not be used in production code.</li>
|
||
<li>20.11 The functions abort, exit, getenv, and system from the library stdlib.h shall not be used.</li>
|
||
</ul>
|
||
<p>I started out with enabling <em>all</em> messages using <code>FlexeLint</code>’s <code>-w4</code>
|
||
option and disabling all noise from system headers. Then I dealt with
|
||
the remaining messages by addressing them or suppressing them in such a way
|
||
that the set of suppressions was minimal. At the end of the day, this is
|
||
what remained:</p>
|
||
<pre><code> // === Tested with FlexeLint 9.00L on FreeBSD 11 ===
|
||
// Compiler:
|
||
// "4.2.1 Compatible FreeBSD Clang 3.6.1 (tags/RELEASE_361/final 237755)"
|
||
|
||
-w4 // Enable maximum pickiness
|
||
-passes(6) // Recommended in FlexeLint manual for torture testing
|
||
+fsc // Make string literals have type const char*
|
||
+fnr // ptr-returning functions may return NULL
|
||
-strong(AJX,and,pro,ser,ala) // strong types
|
||
-strong(AcJcm,thr) // thr is strong, but most arithmetic is okay
|
||
-strong(AarJemorX,met) // met is strong, but some use is okay
|
||
+libclass(angle) // All <headers> are system headers
|
||
-wlib(1) // Only errors for system headers
|
||
-i/usr/include // System headers
|
||
-i/usr/local/lib/supp/ansi // Comes with FlexeLint
|
||
-d__GNUC__=4 // Pretend...
|
||
-d__GNUC_MINOR__=2 // I'm...
|
||
-d__GNUC_PATCHLEVEL__=1 // someone else.
|
||
-d__builtin_va_list=char* // Fake this compiler extension
|
||
-d__inline= // Delete this compiler extension
|
||
-d__attribute__(x)= // Delete this compiler extension
|
||
+e900 // Announce number of messages produced
|
||
|
||
// MISRA 2004 checking
|
||
|
||
/usr/local/lib/supp/lnt/au-misra2.lnt // Enable all MISRA checking
|
||
-elib(960) // Don't check FreeBSD system headers for required rules
|
||
-elib(961) // Don't check FreeBSD system headers for advisory rules
|
||
-e829 // stdio.h used
|
||
-e522 // MISRA 14.2 Highest operation, lacks side-effects
|
||
-esym(960,17.4) // pointer arithmetic other than array indexing used
|
||
-e971 // char without signed/unsigned
|
||
-e974 // stack usage report
|
||
// Use verboten functions, Req. Rules 20.4 malloc() et al., 20.11, exit()
|
||
-esym(586,malloc,realloc,calloc,free,exit)
|
||
|
||
-e911 // implicit promotion of smaller than int to int
|
||
-e921 // cast from integral to integral
|
||
-e925 // cast from pointer to pointer
|
||
-e958 // padding required in struct
|
||
|
||
+e9??? // Enable all 9xxx informational messages, except:
|
||
-e9079 // conversion from pointer to void to pointer to other type
|
||
-e9087 // cast performed between a pointer to object type and a
|
||
// pointer to a different object type
|
||
-e9141 // global declaration of symbol
|
||
|
||
// Messages due to code in FreeBSD headers.
|
||
//
|
||
-dlint // The "lint" macro is tested in x86/_types.h
|
||
-elib(537) // Repeated include file
|
||
-e793 // external identifiers > 6 chars
|
||
-e935 // (unsigned) int within struct (actually the size_t)
|
||
-estring(960,_*) // Could be defined at block scope
|
||
-e964 // Header file not directly used
|
||
-e966 // Indirectly included header file not used
|
||
-elib(970) // int outside typedef
|
||
-esym(9003,_*) // could be defined at block scope
|
||
-elib(9047) // FILE pointer dereferenced
|
||
-esym(9058,__*) // tag not used outside typedef
|
||
-e9092 // NULL does not expand to a pointer (but plain 0)</code></pre>
|
||
<h3 id="compulsory-obfuscations">Compulsory obfuscations</h3>
|
||
<p>Which of the rules cause which obfuscation?</p>
|
||
<p>MISRA 6.1: “The plain <code>char</code> type shall be used only for the storage and
|
||
use of character values.” This forbids using character constants in
|
||
expressions other than assignments to <code>char</code> objects. A consequence is
|
||
that printing digits with <code>'0' + digit</code> is not allowed (even though
|
||
<code>'0'</code> is technically an <code>int</code>!) so I am forced to output hex digits with</p>
|
||
<pre><code> printf("%c", (met)tyr + 32 + 16 + ((8 + EOF) * ((met)tyr / (8 + 2))));</code></pre>
|
||
<p>because of the “no magic numbers other than powers of two” rule. How is this
|
||
an improvement over <code>printf("%c", '0' + tyr + 7 * (tyr / 10)</code>, MISRA?</p>
|
||
<p>MISRA 6.3: “<code>typedef</code>s that indicate size and signedness should be used in
|
||
place of the basic types.” Well, if you can’t infer the size and
|
||
signedness from <code>typedef int met</code>, you’re not a real C programmer.</p>
|
||
<p>MISRA 10.5: “If the bitwise operators <code>~</code> and <code><<</code> are applied to an
|
||
operand of underlying type <code>unsigned char</code> or <code>unsigned short</code>, the
|
||
result shall be immediately cast to the underlying type of the operand.”
|
||
Because the program must work for any unsigned type chosen for the <code>typ</code>
|
||
macro, including the narrow types enumerated in the rule, a lot of
|
||
redundant casting ensues. It gets worse with the next rule…</p>
|
||
<p>MISRA 12.1: “Limited dependence should be placed on the C operator
|
||
precedence rules in expressions.” This requires parentheses for almost
|
||
all expressions involving more than one operator, especially those for which
|
||
a cast is required, leading to hard to understand expressions such as</p>
|
||
<pre><code> const ser glx = (ser)((asx > (ser)64u) ? (ser)((ser)asx + (ser)8u + (ser)1u) : (ser)asx);
|
||
not.not[leu] = (and)((and)not.not[leu] | (and)(((and)glx % (and)16u) << (and)lys));</code></pre>
|
||
<p>MISRA 14.7: “A function shall have a single point of exit at the end of
|
||
the function.” Sigh. Since I must use eloquent prototypes (8.1, 16.3,
|
||
16.4) and static functions (8.10, 8.11), I can only use a few functions.
|
||
Everything usually written with an early <code>return</code> now cause <em>another
|
||
useless indent level</em>. The first three <code>if</code> statements in <code>main()</code> cause a
|
||
silly 24 character indent. The maximum indent is forced to 8, which is way
|
||
too high for a sane function.</p>
|
||
<p>MISRA 16.10: “If a function returns error information, then that error
|
||
information shall be tested.” A cast to <code>void</code> would draw a lint warning, so
|
||
I use the <code>printf(3)</code> result in expressions,</p>
|
||
<pre><code> lys -= 4 * printf("%c", (met)tyr + 32 + 16 + ((8 + EOF) * ((met)tyr / (8 + 2))));
|
||
val += printf("\n") / ((__LINE__ * L_tmpnam) + TMP_MAX);
|
||
val -= (printf(" %d\n", val) > BUFSIZ) ? FILENAME_MAX : EOF;</code></pre>
|
||
<p>which are, in the absence of errors, equivalent to</p>
|
||
<pre><code> lys -= 4;
|
||
/*nop*/
|
||
++val;</code></pre>
|
||
<p>MISRA 13.1: “Assignment operators shall not be used in expressions that
|
||
yield a Boolean value.” Forbids the idiomatic <code>if ((p = malloc(n)) == NULL)</code> and requires separate statements, in other words, bloat.</p>
|
||
<p>MISRA 16.7: “A pointer parameter in a function prototype should be
|
||
declared as pointer to <code>const</code> if the pointer is not used to modify the
|
||
addressed object.” in conjunction with lint’s “Note 952: Parameter could
|
||
be declared <code>const</code>” causes <code>const</code>-poisoning for all functions,</p>
|
||
<pre><code> static void phe(const ala not);
|
||
static void gly(ala *const not, const and his);
|
||
met main(met val, const pro *const his[]);</code></pre>
|
||
<p>and quite a number of automatic variables.</p>
|
||
<h3 id="why-the-laugh-and-throw-up-messages">Why the “laugh” and “throw up” messages?</h3>
|
||
<p>The guidelines state “We like programs that: make us laugh and/or throw
|
||
up :-) (humor really helps!)”</p>
|
||
<h3 id="if-you-have-a-128-bit-type">If you have a 128 bit type</h3>
|
||
<p>If your compiler supports a 128 bit wide type (e.g. clang, gcc) then
|
||
you can use it via the <code>typ</code> macro:</p>
|
||
<pre><code> clang -Dtyp=__uint128_t -o prog prog.c</code></pre>
|
||
<p>Indeed, the program can use (and lints clean for) all of</p>
|
||
<pre><code> clang -Dtyp=uint8_t -o prog8 prog.c
|
||
clang -Dtyp=uint16_t -o prog16 prog.c
|
||
clang -Dtyp=uint32_t -o prog32 prog.c
|
||
clang -Dtyp=uint64_t -o prog64 prog.c
|
||
clang -std=c89 -Dtyp="unsigned long" -o prog89 prog.c</code></pre>
|
||
<p>This works because the program has no need for corresponding <code>SCN</code> or <code>PRI</code>
|
||
macros to do the scanning and printing of variables of these types. With a 128
|
||
bit type the program can represent numbers up to
|
||
340282366920938463463374607431768211457 (<code>3.4 * 1000000000000000000000000000000000000000</code>) as a single “place”, enough to
|
||
explore yet untested numbers for the rest of your life.</p>
|
||
<h3 id="how-big-a-number-can-i-test-with-4-gb-of-ram">How big a number can I test with 4 GB of RAM?</h3>
|
||
<p>The number of hex digits in the start number is limited by <code>ARG_MAX</code>,
|
||
probably minus some overhead for the environment variables (use
|
||
<a href="http://pubs.opengroup.org/onlinepubs/9699919799/utilities/env.html">env()</a>
|
||
to trim your environment). In bits this leaves you with <code>2 to the power of (4 * ARG_MAX)</code>.</p>
|
||
<p>The algorithm requires two <code>bignum</code>s in memory for addition.
|
||
If you hit a divergent number, this will cause out-of-memory (“laugh”)
|
||
somewhere near 2<sup>16,000,000,000</sup> (<code>4GB/2 * 8bits/byte</code>).
|
||
Sadly, I don’t have a test case :-)</p>
|
||
<p>How long would it take to overflow the <em>Not Overflowing Type</em>? Lets
|
||
assume we’re processing 2GB numbers. The program copies, shifts by one,
|
||
adds and increments 2GB long bit strings, each time completely thrashing
|
||
the data cache – at <em>all</em> levels. We have a fast machine that can do an
|
||
iteration in one second, on average. To make things easy, we round up
|
||
<code>3*n* + 1</code> to <code>4*n</code>, and assume we never need to divide by two (which is
|
||
quite optimistic). Then each iteration shifts left by 2. This would take
|
||
8 billion seconds, or about 250 years. If you want to get famous, you
|
||
better <em>remove</em> some of the RAM, use an ancient box, or reduce available
|
||
memory resources with the <code>ulimit(1)</code> built-in of your shell.</p>
|
||
<p>For all intents and purposes, the <em>Not Overflowing Type</em> keeps the promise!</p>
|
||
<!--
|
||
|
||
Copyright © 1984-2024 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/
|
||
|
||
-->
|
||
<!-- AFTER: last line of markdown file: 2015/schweikhardt/README.md -->
|
||
|
||
<!-- END: this line ends content for HTML phase 21 by: bin/pandoc-wrapper.sh via bin/md2html.sh -->
|
||
<!-- START: this line starts content for HTML phase 22 by: bin/output-index-inventory.sh via bin/md2html.sh -->
|
||
|
||
<!-- START: this line starts content generated by: bin/output-index-inventory.sh -->
|
||
|
||
<div id="inventory">
|
||
<h1 id="inventory-for-2015schweikhardt">Inventory for 2015/schweikhardt</h1>
|
||
</div>
|
||
<h2 id="primary-files">Primary files</h2>
|
||
<ul>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2015/schweikhardt/prog.c">prog.c</a> - entry source code</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2015/schweikhardt/Makefile">Makefile</a> - entry Makefile</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2015/schweikhardt/prog.orig.c">prog.orig.c</a> - original source code</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2015/schweikhardt/try.sh">try.sh</a> - script to try entry</li>
|
||
</ul>
|
||
<h2 id="secondary-files">Secondary files</h2>
|
||
<ul>
|
||
<li><a href="2015_schweikhardt.tar.bz2">2015_schweikhardt.tar.bz2</a> - download entry tarball</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2015/schweikhardt/README.md">README.md</a> - markdown source for this web page</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2015/schweikhardt/.entry.json">.entry.json</a> - entry summary and manifest in JSON</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2015/schweikhardt/.gitignore">.gitignore</a> - list of files that should not be committed under git</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2015/schweikhardt/.path">.path</a> - directory path from top level directory</li>
|
||
<li><a href="index.html">index.html</a> - this web page</li>
|
||
</ul>
|
||
<hr style="width:10%;text-align:left;margin-left:0">
|
||
<h4>
|
||
Jump to: <a href="#">top</a>
|
||
</h4>
|
||
|
||
<!-- END: next line ends content generated by: bin/output-index-inventory.sh -->
|
||
|
||
<!-- END: this line ends content for HTML phase 22 by: bin/output-index-inventory.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.inventory.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%2F2015%2Fschweikhardt%2Findex.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> <a href="#inventory">Jump to Inventory</a><br>
|
||
</p>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<!-- END: this line ends content from: inc/footer.inventory.html -->
|
||
<!-- START: this line starts content from: inc/bottom.default.html -->
|
||
|
||
</body>
|
||
</html>
|
||
|
||
<!-- END: this line ends content from: inc/bottom.default.html -->
|