The Output
Amazingly, the output is[mm@noise]$ xmas On the first day of Christmas my true love gave to me a partridge in a pear tree. On the second day of Christmas my true love gave to me two turtle doves and a partridge in a pear tree. On the third day of Christmas my true love gave to me three french hens, two turtle doves and a partridge in a pear tree. On the fourth day of Christmas my true love gave to me four calling birds, three french hens, two turtle doves and a partridge in a pear tree. On the fifth day of Christmas my true love gave to me five gold rings; four calling birds, three french hens, two turtle doves and a partridge in a pear tree. On the sixth day of Christmas my true love gave to me six geese a-laying, five gold rings; four calling birds, three french hens, two turtle doves and a partridge in a pear tree. On the seventh day of Christmas my true love gave to me 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. On the eigth day of Christmas my true love gave to me 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. On the ninth day of Christmas my true love gave to me 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. On the tenth day of Christmas my true love gave to me 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. On the eleventh day of Christmas my true love gave to me 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. On the 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.
Analysis
So, how in the world was this accomplished? First, the code needs to be rewritten in a more legible manner. Let's replace all a ? b : c constructs with explicit if-then-else blocks. Additionally, it is helpful to define character strings whose names will become clear shortly.#includechar *words = "@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' ')# \ }'+}##(!!/"; char *shift = "!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"; main() { xmas(1, 0, '\0'); } xmas(int t, int _, char *a) { if (t Already we can see some hint of what is happening. The variable t has special significance in controlling the direction of recursion. The first conditional, if (t , is just misdirection mostly for the fun of it. It swaps the first two arguments and recurses using the encrypted string of words for the final argument. The utility of the conditional is how it allows nested recursion as seen in the if (t == 2) block by ignoring the third argument. The second block has more real work going on. If the character stored in the variable _ does not match the first character of the string a, the code recurses in such a way that this same block of code will again be entered. That is, t=-65 forces a return to the if (t block. The recursion steps through string a, character by character. When finally _ == a, the character at a+31 is printed and returned.
Further study shows why this is done. The string I renamed to shift is really two strings concatenated. A character found in the first half of the string is 31 places away from its decoded equivalent. For instance, the exclamation point at the first place in the string is followed 31 places later by a newline. So the string offers the solution to a substitution cipher.
In the code below, comments are added. The variable shift has a comment under it lining up the decoded (shifted by 31) values of the string. For example, under the first character !, is character in the string shifted by 31 places, the newline character. The encoded/decoded halves of the string are separated at the colon character.
The other variable, newly named words in the code below, is the set of encrypted words used to print the Christmas carol lyrics. Using the cipher solution string, the words have been decoded in the comments of the source code below. Notice that the ordinal numbers and lines of verses are separated by slash characters.
The third conditional, if (t is used to find |t| slash characters and then after t recursions, to return xmas(0, _, a+1), where a+1 is the string starting at the character after the slash. Again, through recursion it simply gets us to the character after |t|'th slash. The next call goes into the conditional block described next.
The fourth conditional, if (t == 0), uses recursion with the 2nd conditional block, t , to print out the decoded string up to the next slash and then returns 1.
The t == 1 block is used just a single time at the start to get the recursion going properly, that is, with xmas(2, 2, "%s") where the string is unimportant because it is never used.
The t == 2 block is used to print "On the [ordinal] day of Christmas my true love gave to me\n".
The final two conditional blocks keep the recursion running in two directions. First, the final block counts up to day 12. The second to last block, counts down from the current day to print lyrics of the current verse in reverse order.
#include/* * Substitution cipher solution. Letters up to and including the colon are * shifted by 31 places to the right to find the decoded value. */ char *shift = "!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"; /* "\nuwloca-O;m .vpbks,fxntdCeghiry"; */ char *words = "@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' ')# \ }'+}##(!!/"; /* Decoded values of 'words' using the substitution cipher string 'shift': "@n'+,#'/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l+,/n{n+,/+#n+,/#\ On the /first/second/third/fourth/fifth/sixth/seventh/eigth/ninth/tenth/e ;#q#n+,/+k#;*+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l \ leventh/twelfth/ day of Christmas my true love ga q#'+d'K#!/+k#;q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;# \ ve to me0/twelve drummers drumming, /eleven pipers piping, /ten lords a-lea ){nl]!/n{n#'; r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#n'wk nw' \ ping,0/nine ladies dancing, /eight maids a-milking, /seven swans a\ iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c \ -swimming,0/six geese a-laying, /five gold rings;0/four ca ;;{nl'-{}rw]'/+,}##'*}#nc,',#nw]'/+kd'+e}+;#'rdq#w! nr'/ ') }+}{rl#'{n' ')# \ lling birds, /three french hens, /two turtle doves0and /a partridge in a pea }'+}##(!!/"; r tree.00/ */ main() { xmas(1, 0, '\0'); } xmas(int t, int _, char *a) { /* Swap first two args and use new 3rd. */ if (t /* * Loop through a till a==_, then print char at a+31. * That is, given character in variable '_' and substitution cipher * solution in 'a', decode character '_' and print & return it. */ if (t /* Loop until _ == *a. */ return xmas(-65, _, a+1); } } /* * Loop until finding -t number of slash characters in a[] and * return string starting at character after that slash. */ if (t /* * Decode & print word up to next slash character and then return 1. */ if (t == 0) { if (*a == '/') { return 1; } else { return xmas(0, xmas(-61, *a, shift), a+1); } } /* * Start off recursion. Only called once at very start. */ if (t == 1) { return xmas(2, 2, "%s"); } if (t == 2) xmas(-79, /* " day of Christmas my true love gave to me\n" */ -13, a + xmas(-87, /* print which day of Christmas it is */ 1-_, a + xmas(-86, 0, a+1))); /* "On the " */ /* * Recurse, count down days of Christmas * from '_' to print lyrics of current verse in reverse day order. * I.e., day 12, day 11, etc. */ if (t /* * Print phrase for current verse. * E.g., t == 2: "a partridge in a pear tree\n\n" * etc. */ if (xmas(-94, -27+t, a) && t == 2) { if (_ /* Recurse to next higher day of Christmas. String not used. */ return xmas(2, _+1, "%s %d %d\n"); else /* Just misdirection, return value not used. */ return 9; } else { /* More misdirection! */ return 16; } } Simpler
With new understanding of what's going on, the program can be simplified by using some iteration and C string library routines. I have to admit to preferring recursion myself, but since the analysis has gone this far, let's not stop now. Here's what we might see after further simplification:#include#include char *words = "@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' ')# \ }'+}##(!!/"; char *shift = "!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"; main() { xmas(2, 2, ""); } xmas(int t, int _, char *a) { /* * Loop until finding |t| number of slash characters in a[] and * return string starting at character after that slash. */ if (t /* * Decode & print word up to next slash character and return 0 or any int. */ if (t == 0) { while (*a != '/') putchar(index(shift, *a++)[31]); /* Decode *a and print it. */ return 0; } if (t == 2) { /* 2nd arg is a don't-care since it's unused. */ xmas(0, 0, words); /* "On the " */ xmas(1-_, 0, words); /* print which day of Christmas it is */ xmas(-13, 0, words); /* " my true love gave to me\n" */ } /* * Recurse and count down days of Christmas * from '_' down to and including day 2. */ if (t /* * t==2: "a partridge in a pear tree\n\n" * etc. */ xmas(-27+t, 0, words); if (t == 2 && _ /* Next higher day of Christmas. */ } In Conclusion...
This could go on till the ultimate simplification of doing nothing more than printing out the lyrics, but you get the idea. This is one of the better obfuscated C programs I've come across because of using the substitution cipher along with recursion. That was followed by the addition of a small bit of unnecessary code and use of random arguments when the arguments were in fact not made use of. A very nice little bundle of C code!Understanding what's happening is still a long way from writing it. What a great example of creativity.
Merry Christmas!
Mike Markowski, mike.ab3ap -A- gmail -D- com