This repository was archived by the owner on Dec 30, 2024. It is now read-only.
forked from ioccc-src/winner
-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathindex.html
1174 lines (1049 loc) · 53.7 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!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/index.html" class="sub-item-link">
Rules and 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="../../faq.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="../../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/index.html">
Rules and 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="../../faq.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="../../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://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