Implementation notes

Downsampling source.

----------------------------------------------------------------------
0. Concept

While winning entries for IOCCC have been steadily increasing in
functionality and complexity, I am still sticking to what I like to do
the most, which is making ASCII art code.  For the 20th IOCCC, I made
some efforts to create something new that is still very much ASCII art.

One appeal of ASCII art is the multiple zoom levels: you see an image
made of shapes when viewed from a distance, and an image made of
textures from the individual characters when viewed up close.  This time
around, I want to see if it's possible to get more than these two images
from a single ASCII art.

One way to do this uses the same technique as pointillist paintings,
which is to mix multiple images encoded at different sampling
frequencies.  For example, given the following program:

   #include<stdio.h>
   int main(){return puts("inner");}

If you replace every character with a character and 3 spaces:

    # i n c l u d e < s t d i o . h >

    i n t   m a i n ( ) { r e t u r n   p u t s ( " i n n e r " ) ; }

You see that there is plenty of space between the characters to insert a
new program, overlapping with the old program a bit:

   #include<stdio.h>/*
    # i n c l u d e < s t d i o . h >*/
   int main(){return puts("outer\0"
   "i n t   m a i n ( ) { r e t u r n   p u t s (\" i n n e r " ) ; }

This is a two layer program.  The inner layer would be a be difficult to
spot if you didn't already know it was there, which of course made this
perfect for IOCCC.

----------------------------------------------------------------------
1. Layered programs

The goal is to write layered programs that compile at different sampling
frequencies.  The easiest way to write such a program is from inside
out:
1. Write the innermost layer first
2. Expand this layer by inserting spaces and newlines
3. Fill in the spaces with a new layer of code
4. Repeat until file size exceeds IOCCC size limit.

For this program, I started with the outermost template first, resizing
an image so that it fits just below IOCCC size limits, and downsampled
the image repeatedly until I can no longer fit a program in it.  This is
the innermost program (layer3.c).  Basically it just prints out a
message.

The next layer (level2.c) has a bit more space, but to accommodate the
inner program, it's also limited in functionality -- prints out another
message.

The second highest layer (level1.c) had quite a bit of space.  An
utility to expand a text file (used for writing these layers from inside
out) easily fits in this space, with room to spare.  The extra space was
too good to waste, but not quite enough to fit in anything too complex,
so I added a rot13 filter.

The outermost layer (level0.c) had been planned from the start: this
will be a utility that downsamples ASCII art, so that readers will have
a tool to discover the inner layers.  Since I have the space, I also
implemented a PPM/PGM downsampler.  And since I still have space after
that, a BF program (bf.c) is embedded in the outermost layer.

Because part of the edits were produced using custom tools, I did not
record all the edits that produced the innermost layers.  Edits for the
outermost layer are in edit.html.

----------------------------------------------------------------------
2. Image downsampler

Most of the multiple layers were straightforward to write (with enough
patience) and straightforward to read, except the outermost layer.  Here
I chose an implementation that is not immediately readable, not because
it's for IOCCC, but because it's more space efficient.

Recall that the goal is to add another layer of code on top of the
previous layer in the newly inserted spaces.  These newly inserted
spaces occur at every other line and at every other character.  The
former is continuous and easy to utilize, the latter is very difficult
to mix with C.  What we really needed is a new language where every
other character doesn't matter, so I implemented the downsampling code
as a DFA (deterministic finite automaton), and encoded that inside a
string where every other character is simply ignored.

Since there are only a few possible conditions to test at each state,
and each state has at most 2 outgoing edges, I was able to encode each
DFA state in just 3 characters.  Initially I had only implemented PPM
and text downsamplers, but since this encoding is so efficient, I
decided to support PGM as well.  Since there are still lots of space
after that, I decided to double the DFA to support two downsampling
schemes (even pixels on even scanlines vs. odd pixels on odd scanlines).
And there are still spaces left, so I obscured the DFAs by XORing most
of it, so that I can include some subliminal messages in the encoded
string.

The end result is that the main logic of the downsampler is immune to
all code beautifiers, since it's 6 DFAs mixed together behind a
one-time-pad.  It's IOCCC quality.

----------------------------------------------------------------------
3. Finally...

Template is Akaza Akari from Yuruyuri.  It's an ongoing joke in the
anime and manga on how Akari doesn't stand out at all, little did anyone
know that it would be Akari who would go on to win Best of Show for the
20th IOCCC.  I couldn't be more proud ^_^;