Implementation notes One time pad. ---------------------------------------------------------------------- 0. Concept I was very happy that Akari from Yuruyuri is a winner for the 20th IOCCC. Coincidentally, the 21st IOCCC started a few months after results from the 20th has been published, and my favorite series that was on air at the time was Yuruyuri season 2. Since I didn't want to enter with another Yuruyuri character, I was somewhat at a loss of ideas. The thought simply never occurred to me to *not* enter IOCCC with an ASCII art girl. Looking back at the previous season, and from some feedback that I have received for Akari, I thought the next most fitting character for IOCCC would be Nyaruko, also known as "the chaos that always crawls up to you with a smile, Nyarlathotep," along with the chaotic opening song. This chaos seems perfect for IOCCC. ---------------------------------------------------------------------- 1. Chaos The most obvious thing to do with chaos is to build a random number generator. I figured random numbers by themselves would be quite useless, the most obvious application for a good random number generator would be to build a one-time pad, more accurately known as a stream cipher in this case. Never mind the new Nyaruko, the original Nyarlathotep was known as "Great Messenger, bringer of strange joy to Yuggoth through the void" (see "The Whisperer in Darkness" by H.P. Lovecraft). A data encoding/encapsulation utility seems very fitting. With that in mind, I went to look for state of the art random number generators instead of designing my own from scratch, and settled on ISAAC: http://www.burtleburtle.net/bob/rand/isaacafa.html The other choices were Mersenne Twister, which wasn't cryptographically secure, and Blum Blum Shub, which has a cool name but handling large prime numbers is going to be troublesome. ISAAC was fairly easy to implement and takes only a small amount of code, but the seeding procedure is troublesome. Instead of the proposed seeding procedure, I just through away the first 2**24 numbers, following the guidelines here: http://en.wikipedia.org/wiki/Key_stretching ---------------------------------------------------------------------- 2. Binary to text Nyaruko is meant to encode any arbitrary binary input data. I could just encrypt things and spit out binary on stdout, but since this is IOCCC, it's only fitting that the output would be C code as well. There are a number of ways to encode binary as text, the most popular being some variant of base64 or base85. Base85 is preferred here because it's more space efficient, and also because it operates on 32bit words, which works better with the 32bit nature of ISAAC. I wanted to simplify the decoder code as much as possible, something of the form: base85_digit = (ascii_byte + offset) % modulus The offset and modulus parameters were determined to be 83 and 89, the corresponding encoder required an extra conditional but was otherwise fairly short as well. One last detail to be resolved is to encode the length of the data. Initially I thought about encoding this in some header, but eventually settled on appending a length marker at the end. This allows the encoder to operate in streaming mode (i.e. without having to know the length of input before writing output). The marker is one of 4 bytes that specifies the number of excess bytes in the final block: 0 = # 1 = ! 2 = % 3 = $ These were chosen because there were the only so few characters left. The sequence was chosen to make it easy to compute length by doing modulus with 5. ---------------------------------------------------------------------- 3. Implementation Having implemented a binary to text encoder with encryption, it seems like it was lacking a bit of impact. So I made the output a trivial polyglot, the primary intent was to make it more convenient to separate key and data, and also because IOCCC readers tend to appreciate polyglots, however trivial. It's still not quite over the top (compared to Akari which had no less than 3 different behaviors), but after the ISAAC encoder/decoder bits, I counted the characters and didn't think I can fit in more functions if I still wanted my ASCII art character, so Nyaruko is only an encoder, no extra functionalities. This time around though, I made sure to record progression of the code from the very beginning, making a snapshot of the recording log every few hours to rollback bad edits more easily. This is why there are 38 in-progress versions of the code (usually I only needed 10). I generated the HTML to replay the recording and packaged it with the submission, in the end I think it was this spoiler.html.gz that won the IOCCC. I mean while a stream cipher can be obfuscated, it's not as complicated as smoothed particle hydrodynamics. ---------------------------------------------------------------------- 4. Finally... Nyaruko won the "Most surreptitious" award in the 21st IOCCC. I am very happy about this of course, with the previous IOCCC results and 3rd place at ICFP, this year has been a particularly good year for me. I just wished they picked an award that was more easily pronounceable...