How does the 12 Days of Christmas program work?

One of the best pieces from the Obfuscated C Contest is the code below. Believe it or not, it prints out the text of the 12 days of Christmas!

#include <stdio.h>
main(t,_,a)
char *a;
{
return!0<t?t<3?main(-79,-13,a+main(-87,1-_,main(-86,0,a+1)+a)):
1,t<_?main(t+1,_,a):3,main(-94,-27+t,a)&&t==2?_<13?
main(2,_+1,"%s %d %d\n"):9:16:t<0?t<-72?main(_,t,
"@n'+,#'/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l+,/n{n+,/+#n+,/#\
;#q#n+,/+k#;*+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l \
q#'+d'K#!/+k#;q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;# \
){nl]!/n{n#'; r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#n'wk nw' \
iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c \
;;{nl'-{}rw]'/+,}##'*}#nc,',#nw]'/+kd'+e}+;#'rdq#w! nr'/ ') }+}{rl#'{n' ')# \
}'+}##(!!/")
:t<-50?_==*a?putchar(31[a]):main(-65,_,a+1):main((*a=='/')+t,_,a+1)
:0<t?main(2,2,"%s"):*a=='/'||main(0,main(-61,*a,
"!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"),a+1);
}

One day, I just got sick of not knowing how it worked, and decided to take it apart.

The Strings

There are 2 major strings in the program. The first one is encrypted with a substitution cypher - the second string is the key of the cypher.

The key string is:
"!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"

For an encrypted character at index X in the key, the decrypted value is at index X+31 in the key. So '@' at index 8, decrypts to the character at index 39, 'O'. Notice that '!' (index 0) translates to '\n' (index 31).

The first string in the program - the one encrypted with they cypher is:

"@n'+,#'/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l+,/n{n+,/+#n+,/#\
;#q#n+,/+k#;*+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l \
q#'+d'K#!/+k#;q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;# \
){nl]!/n{n#'; r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#n'wk nw' \
iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c \
;;{nl'-{}rw]'/+,}##'*}#nc,',#nw]'/+kd'+e}+;#'rdq#w! nr'/ ') }+}{rl#'{n' ')# \
}'+}##(!!/"

When it is decrypted it looks like this:

"On the /first/second/third/fourth/fifth/sixth/seventh/eigth/ninth/tenth/eleventh/twelfth/ day of Christmas my true love gave to me
/twelve drummers drumming, /eleven pipers piping, /ten lords a-leaping,
/nine ladies dancing, /eight maids a-milking, /seven swans a-swimming,
/six geese a-laying, /five gold rings;
/four calling birds, /three french hens, /two turtle doves
and /a partridge in a pear tree.

The slashes are not in the cypher key; they are used to divide the encrypted string into a sequence of substrings. One of the functions of the program decrypts and prints the Nth substring in the sequence.

For more on substitution cyphers, you can check out my solver, which I wrote as an example of using STL.

Basic Outline of How it Works

You probably have a good idea of how it works right now:

main(){
    for(day = 1; day <= 12; day++) {
        decrypt_and_print_substring(0);
        decrypt_and_print_substring(day);
        decrypt_and_print_substring(13);
        for(gift = day; gift >= 1; gift--)
            decrypt_and_print_substring(26 - gift);
    }
}

Now, the program does not have loops, so both for-loops are done via recursion. It may appear that there are no sequential pieces to the actual code, but there are. For sequential operations the author either uses the comma operator or does multiple function calls in a single line (e.g. main(main(main()) - the inner most call must be done first).

The code for decrypt_and_print_substring (using a few of the author's tricks) is:

decrypt_and_print_substring(index){
s = ENCRYPTED_STRING;
substr_count = 0;

    /* advance to the correct substring */
    while (substr_count != index) {
        substr_count += (*(s++) == '/');
    }

    /* print the substring */
    while (*s != '/') {
        decrypt_and_print_char(*(s++));
   }
}

Decrypt_and_print_char is pretty simple:

decrypt_and_print_char(encrypted_char) {
s = ENCRYPTION_KEY;

    /* advance to place of encrypted character in string */
    while (*s != encrypted_char)
        s++;

/* print the character 31 places after it. */
putchar( *(s+31));
}

Under the Hood

The 12 days of Christmas program recursively calls main(). The different operations performed by main() are selected by the first argument.

Decrypt_and_print_char:

First argument must be in the range -51 to -72

Second argument is the character to be decrypted

Third argument is the encryption key string

Example: main(-61,*a, "!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry")

Algorithm: Recursively calls itself via main(-65,_,a+1) until (_==*a), at which time it prints the decrypted character using putchar(31[a])

Decrypt_and_print_substring:

First argument must be less than -72

Second argument is the -1 times the index of the substring to be printed. E.g. -2 to print the substring at index 2.

Third argument: unused

Example: main(-86,0,a+1)

Algorithm: First, it calls main() with new arguments: The first is the index of the substring times -1, the second is now irrelavent, and the third argument is the encrypted string. Then it recursively calls main() processing the encrypted string one character at a time, increasing the first argument every time it encounters a '/'. When the first argument is 0, it invokes the decrypt_and_print_char functionality on every character up to the next '/'.

"main":

First argument must be 1 (Note: in the first call (with no command-line arguments) value will be 1.)

Second argument: unused

Third argument: unused

Algorithm: First, it calls main() again with this call: main(2,2,"%s"). When the first argument is 2, the second argument indicates the current day of Christmas plus 1. So main(2,2,"%s") means we are on the first day of Christmas. (The third argument is unused.) While the first argument is 2, the function invokes decrypt_and_print_substring with seconds arguments of 0, 1-second_argument, -13, and (via recursion) all items from-27+second_argument through -25.

Note: If you want to test this out, you have to modify the program so that the command-line arguments are translated before becoming arguments to the function. Otherwise, you can never make the first argument to main() negative.

Cute Tricks by the Author:

main() : I never saw a recursive call to main() before this program. I never even considered it possible!
_ : Underscore is one of the legal characters in a label. Using it by itself is unusual. (NOTE: You should not begin you variable names with an underscore; most libraries begin their variable names with underscore with the intention of avoiding name conflicts. Starting you variable names with an underscore could cause the very name conflicts library writers are trying to avoid.)
?: and , : Questionmark-colon (a.k.a. Teriary operator) and the comma are two of the least used operators in C and C++. They are used to combine multiple statements into a single operation. The author was able to write the entire main() in a single return statement!
|| : The author uses the short-cut operator "or" to act like a ?: operation. Due to the short-cut, if the first part is true, the second part is never executed.
!0 and (*a == '\')+t : The author used these boolean logic statements as integers, relying on the fact that true is returned as 1 by the system.
31[a] : A very cool usage of the array opertor. Why does it work? The compiler translates any array invocation like s[i] into *(s+i). So 31[a] is translated into *(31+a) which is equivalent to *(a+31), the translation of a[31]!

The author also used a large number of red herrings - irrelavent strings like "%s" and %s %d %d\n" and calls like main(-79,-13,a+main(-87,1-_,main(-86,0,a+1)+a)) (which is merely a serial operation because the third arguments are irrelavent) - to throw people like me off the track.

How did I do it?

I figured out how it worked by slowly picking it apart.

xmassong.c Source
First, I went through and organized the ?: and , operations Source
then I translated it into if-then-else notation Source
then I changed variable names to get rid of "_" Source
then I modified it to produce a callgraph - tracking the path of recursive calls Source Output
Knowing the callgraph, I was able to separate out the decrypt_and_print_char (foo8 in file) and decrypt_and_print_substring (foo7 in file) functions. Source

I realized that it was doing a substitution cypher and wrote a small program to print the decrypted string Source Output

Lastly, I pulled decrypt_and_print_substring a little more apart Source