Twelve Ways to Style The Twelve Days

By: Kevin Jones
Senior Consultant, Embedded Systems

6th December 2018

Home » software

At this time of year I sometimes think about a now-famous piece of obfuscated C code. This was the winning entry in the 1988 International Obfuscated C Code Contest [see reference 1] and, believe it or not, will print the entire lyrics to “The Twelve 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);
}

There are plenty of articles online that explain how this works; just use your favourite search engine to find out more [see reference 2]. Rather than repeat those descriptions, I’ll stick to the festive theme that prompted this blog and illustrate twelve ways to improve the readability of this wonderful algorithm.

1) Extract the Constant Strings

There are two strings lurking in the source code. The longer string contains an encoded version of the song lyrics and the shorter string contains a substitution cipher to decode the lyrics. The source code is immediately much clearer if these strings are declared near the beginning of the file. In the following example, “static” limits the scope of the strings to one source file and “const” declares them as read-only. I like to use uppercase symbols for constants but that’s nothing more than personal choice. Here’s the modified source code:

#include <stdio.h>

static const char *CIPHER =
"!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry";

static const char *LYRICS =
"@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' ')# \
}'+}##(!!/";

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,LYRICS)
: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,CIPHER),a+1);
}

2) Reformat the Strings

The two strings are recursively indexed to decode and display the lyrics. Reformatting these strings helps to understand the algorithm. In the next step the lyrics and the cipher are declared using C’s alternative string concatenation syntax. The substitution cipher is split after the 31st character, the lyrics are split at each “/” character and the original code’s “\” concatenation in the lyrics string has been eliminated. There’s also some indentation to improve readability:

#include <stdio.h>

static const char *CIPHER =
     "!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:"
    "\nuwloca-O;m .vpbks,fxntdCeghiry";

static const char *LYRICS =
    "@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' ')# }'+}##(!!/";

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,LYRICS)
: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,CIPHER),a+1);
}

3) Add Some Comments

All good programmers know that comments are useful. Annotating the constant strings immediately helps understand the algorithm even before any changes are made to the function. I prefer block comments for maximum portability but end-of-line comments would work just as well:

static const char *CIPHER =
    /*
    * Substitution cipher:
    * Replace '!' with '\n'
    * Replace 'e' with 'u'
    * ...
    * Replace ':' with 'y'
    */
     "!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:"
    "\nuwloca-O;m .vpbks,fxntdCeghiry";

static const char *LYRICS =
    "@n'+,#'/"  /* On the */
    "*{}w+/"    /* first */
    "w#cdnr/"   /* second */
    "+,{}r/"    /* third */
    "*de}+,/"   /* fourth */
    "*{*+,/"    /* fifth */
    "w{%+,/"    /* sixth */
    "w#q#n+,/"  /* seventh */
    "#{l+,/"    /* eighth */
    "n{n+,/"    /* ninth */
    "+#n+,/"    /* tenth */
    "#;#q#n+,/" /* eleventh */
    "+k#;*+,/"  /* twelfth */

    /* day of Christmas my true love gave to me\n */
    "'r :'d*'3,}{w+K w'K:'+}e#';dq#'l q#'+d'K#!/"

    /* twelve drummers drumming, */
    "+k#;q#'r}eKK#}w'r}eKK{nl]'/"

    /* eleven pipers piping, */
    "#;#q#n'){)#}w'){){nl]'/"

    /* ten lords a-leaping,\n */
    "+#n';d}rw' i;# ){nl]!/"

    /* nine ladies dancing, */
    "n{n#'; r{#w'r nc{nl]'/"

    /* eight maids a-milking, */
    "#{l,+'K {rw' iK{;[{nl]'/"

    /* seven swans a-swimming,\n */
    "w#q#n'wk nw' iwk{KK{nl]!/"

    /* six geese a-laying, */
    "w{%'l##w#' i; :{nl]'/"

    /* five gold rings;\n */
    "*{q#'ld;r'}{nlwb!/"

    /* four calling birds, */
    "*de}'c ;;{nl'-{}rw]'/"

    /* three french hens, */
    "+,}##'*}#nc,',#nw]'/"

    /* two turtle doves\nand */
    "+kd'+e}+;#'rdq#w! nr'/"

    /* a partridge in a pear tree */
    " ') }+}{rl#'{n' ')# }'+}##(!!/";

4) Indent the Function Contents

This step is straight forward… simply indent the contents of the single function:

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,LYRICS)
    :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,CIPHER),a+1);
}

5) Eliminate Implicit Types

If you’re compiling the examples then you may have noticed that there are plenty of implicit type warnings. The main function uses an old C syntax to declare parameter “a” as pointer-to-char. The remaining parameters are implicit integers and the return type of the main function is also an implicit integer. These are fixed in the next sample while taking the opportunity to include the “const” type qualifier:

int main(int t, int _, const 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,LYRICS)
    :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,CIPHER),a+1);
}

6) Rename the Underscore Parameter

The second parameter of the main function is a single underscore. While this is perfectly legal in C, it’s a lot harder to read than an alphabetic character. The next sample has replaced all instances of the underscore parameter with the single character “b”:

int main(int t, int b, const char *a)
{
    return!0<t?t<3?main(-79,-13,a+main(-87,1-b,main(-86,0,a+1)+a)):
    1,t<b?main(t+1,b,a):3,main(-94,-27+t,a)&&t==2?b<13?
    main(2,b+1,"%s %d %d\n"):9:16:t<0?t<-72?main(b,t,LYRICS)
    :t<-50?b==*a?putchar(31[a]):main(-65,b,a+1):main((*a=='/')+t,b,a+1)
    :0<t?main(2,2,"%s"):*a=='/'||main(0,main(-61,*a,CIPHER),a+1);
}

7) Reformat the Ternary Conditional Operator

The obfuscated implementation makes extensive use of the ternary conditional operator. The next sample reformats these ternary operators with some additional whitespace:

int main(int t, int b, const char *a)
{
    return
    !0<t
    ?
        t<3
        ?
            main(-79,-13,a+main(-87,1-b,main(-86,0,a+1)+a))
        :
            1, t<b
            ?
                main(t+1,b,a)
            :
                3, main(-94,-27+t,a)&&t==2
                ?
                    b<13
                    ?
                        main(2,b+1,"%s %d %d\n")
                    :
                        9
                :
                    16
    :
        t<0
        ?
            t<-72
            ?
                main(b,t,LYRICS)
            :
                t<-50
                ?
                    b==*a
                    ?
                        putchar(31[a])
                    :
                        main(-65,b,a+1)
                :
                    main((*a=='/')+t,b,a+1)
        :
            0<t
            ?
                main(2,2,"%s")
            :
                *a=='/'||main(0,main(-61,*a,CIPHER),a+1);
}

8) Replace the Ternary Conditional Statements with If-Else

A simple replacement of the ternary conditional statements with if-else statements improves the presentation of the algorithm. In the following sample, there is yet more white space and the multiple return points have been rationalised into a single point of return by using a temporary integer variable “r”:

int main(int t, int b, const char *a)
{
    int r;
    if (!0 < t)
    {
        if (t < 3)
        {
            main(-79, -13, a + main(-87, 1 - b, main(-86, 0, a + 1) + a));
        }
        else
        {
            1;
        }
        if (t < b)
        {
            main(t + 1, b, a);
        }
        else
        {
            3;
        }
        if (main(-94, -27 + t, a) && t == 2)
        {
            if (b < 13)
            {
                r = main(2, b + 1, "%s %d %d\n");
            }
            else
            {
                r = 9;
            }
        }
        else
        {
            r = 16;
        }
    }
    else
    {
        if (t < 0)
        {
            if (t < -72)
            {
                r = main(b, t, LYRICS);
            }
            else
            {
                if (t < -50)
                {
                    if (b == *a)
                    {
                        r = putchar(31[a]);
                    }
                    else
                    {
                        r = main(-65, b, a + 1);
                    }
                }
                else
                {
                    r = main((*a == '/') + t, b, a + 1);
                }
            }
        }
        else
        {
            if (0 < t)
            {
                r = main(2, 2, "%s");
            }
            else
            {
                r = *a == '/' || main(0, main(-61, *a, CIPHER), a + 1);
            }
        }
    }
    return r;
}

9) Simplify an Array Access

This change is straight forward. The array access “31[a]” is exactly the same as “a[31]” yet the latter is much easier to understand in the context of the 31 character substitution cipher:

    ...
    r = putchar(a[31]);
    ...

10) Add Brackets to Logical Expressions

Personally, I prefer plenty of brackets in compound logical expressions. The following snips are small improvements:

    ...
    if (main(-94, -27 + t, a) && (t == 2))
    ...

    ...
    r = ((*a == '/') || (main(0, main(-61, *a, CIPHER), a + 1)));
    ...

11) Remove Misdirection

There are several instances where the implementation is deliberately misleading. Given the reformatted source code so far, it’s easy to see that there are two “else” clauses with no side effects (“else {1;}” and “else {3;}”). Less obvious is that the parameters that look like string formatting specifiers passed to the main function are unused in that iteration of the function and can be replaced with zero:

    ...
    if (b < 13)
    {
        r = main(2, b + 1, 0);
    }
    ...

    ...
    r = main(2, 2, 0);
    ...

12) Implement a Stand-Alone Recursive Function

The entire algorithm so far uses the single “main” function in an unusual recursive manner. After the last of the twelve changes, the main function looks like a standard C main function and there’s a separate local-scope (static) recursive function which, in time-honoured programmer’s tradition, is called “foo”. This gives the final complete sample after all twelve changes:

#include <stdio.h>

static const char *CIPHER =
    /*
    * Substitution cipher:
    * Replace '!' with '\n'
    * Replace 'e' with 'u'
    * ...
    * Replace ':' with 'y'
    */
     "!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:"
    "\nuwloca-O;m .vpbks,fxntdCeghiry";

static const char *LYRICS =
    "@n'+,#'/"  /* On the */
    "*{}w+/"    /* first */
    "w#cdnr/"   /* second */
    "+,{}r/"    /* third */
    "*de}+,/"   /* fourth */
    "*{*+,/"    /* fifth */
    "w{%+,/"    /* sixth */
    "w#q#n+,/"  /* seventh */
    "#{l+,/"    /* eighth */
    "n{n+,/"    /* ninth */
    "+#n+,/"    /* tenth */
    "#;#q#n+,/" /* eleventh */
    "+k#;*+,/"  /* twelfth */

    /* day of Christmas my true love gave to me\n */
    "'r :'d*'3,}{w+K w'K:'+}e#';dq#'l q#'+d'K#!/"

    /* twelve drummers drumming, */
    "+k#;q#'r}eKK#}w'r}eKK{nl]'/"

    /* eleven pipers piping, */
    "#;#q#n'){)#}w'){){nl]'/"

    /* ten lords a-leaping,\n */
    "+#n';d}rw' i;# ){nl]!/"

    /* nine ladies dancing, */
    "n{n#'; r{#w'r nc{nl]'/"

    /* eight maids a-milking, */
    "#{l,+'K {rw' iK{;[{nl]'/"

    /* seven swans a-swimming,\n */
    "w#q#n'wk nw' iwk{KK{nl]!/"

    /* six geese a-laying, */
    "w{%'l##w#' i; :{nl]'/"

    /* five gold rings;\n */
    "*{q#'ld;r'}{nlwb!/"

    /* four calling birds, */
    "*de}'c ;;{nl'-{}rw]'/"

    /* three french hens, */
    "+,}##'*}#nc,',#nw]'/"

    /* two turtle doves\nand */
    "+kd'+e}+;#'rdq#w! nr'/"

    /* a partridge in a pear tree */
    " ') }+}{rl#'{n' ')# }'+}##(!!/";

static int foo(int t, int b, const char *a)
{
    int r;
    if (!0 < t)
    {
        if (t < 3)
        {
            foo(-79, -13, a + foo(-87, 1 - b, foo(-86, 0, a + 1) + a));
        }
        if (t < b)
        {
            foo(t + 1, b, a);
        }
        if (foo(-94, -27 + t, a) && (t == 2))
        {
            if (b < 13)
            {
                r = foo(2, b + 1, 0);
            }
            else
            {
                r = 9;
            }
        }
        else
        {
            r = 16;
        }
    }
    else
    {
        if (t < 0)
        {
            if (t < -72)
            {
                r = foo(b, t, LYRICS);
            }
            else
            {
                if (t < -50)
                {
                    if (b == *a)
                    {
                        r = putchar(a[31]);
                    }
                    else
                    {
                        r = foo(-65, b, a + 1);
                    }
                }
                else
                {
                    r = foo((*a == '/') + t, b, a + 1);
                }
            }
        }
        else
        {
            if (0 < t)
            {
                r = foo(2, 2, 0);
            }
            else
            {
                r = ((*a == '/') || (foo(0, foo(-61, *a, CIPHER), a + 1)));
            }
        }
    }
    return r;
}

int main(int argc, char *argv[])
{
    return foo(1, 0, 0);
}

There are plenty of changes that could still be made to improve readability, such as more comments and replacing the recursive algorithm with iterative loops… but I’ve made my promised twelve improvements, leaving you with plenty of opportunity to make some of your own.



[1] At the time of writing this blog, the original code can be found on the International Obfuscated C Code Contest website on the “Winning Entries” web page, listed as “phillipps.c” under the 1988 sub-heading.

[2] Credit goes to an analysis by Mike Markowski and to a similar exercise in reformatting the source code by Michael Nahas.

At this time of year I sometimes think about a now-famous piece of obfuscated C code. This was the winning entry in the 1988 International Obfuscated C Code Contest [see reference 1] and, believe it or not, will print the entire lyrics to “The Twelve 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);
}

There are plenty of articles online that explain how this works; just use your favourite search engine to find out more [see reference 2]. Rather than repeat those descriptions, I’ll stick to the festive theme that prompted this blog and illustrate twelve ways to improve the readability of this wonderful algorithm.

1) Extract the Constant Strings

There are two strings lurking in the source code. The longer string contains an encoded version of the song lyrics and the shorter string contains a substitution cipher to decode the lyrics. The source code is immediately much clearer if these strings are declared near the beginning of the file. In the following example, “static” limits the scope of the strings to one source file and “const” declares them as read-only. I like to use uppercase symbols for constants but that’s nothing more than personal choice. Here’s the modified source code:

#include <stdio.h>

static const char *CIPHER =
"!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry";

static const char *LYRICS =
"@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' ')# \
}'+}##(!!/";

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,LYRICS)
: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,CIPHER),a+1);
}

2) Reformat the Strings

The two strings are recursively indexed to decode and display the lyrics. Reformatting these strings helps to understand the algorithm. In the next step the lyrics and the cipher are declared using C’s alternative string concatenation syntax. The substitution cipher is split after the 31st character, the lyrics are split at each “/” character and the original code’s “\” concatenation in the lyrics string has been eliminated. There’s also some indentation to improve readability:

#include <stdio.h>

static const char *CIPHER =
     "!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:"
    "\nuwloca-O;m .vpbks,fxntdCeghiry";

static const char *LYRICS =
    "@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' ')# }'+}##(!!/";

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,LYRICS)
: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,CIPHER),a+1);
}

3) Add Some Comments

All good programmers know that comments are useful. Annotating the constant strings immediately helps understand the algorithm even before any changes are made to the function. I prefer block comments for maximum portability but end-of-line comments would work just as well:

static const char *CIPHER =
    /*
    * Substitution cipher:
    * Replace '!' with '\n'
    * Replace 'e' with 'u'
    * ...
    * Replace ':' with 'y'
    */
     "!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:"
    "\nuwloca-O;m .vpbks,fxntdCeghiry";

static const char *LYRICS =
    "@n'+,#'/"  /* On the */
    "*{}w+/"    /* first */
    "w#cdnr/"   /* second */
    "+,{}r/"    /* third */
    "*de}+,/"   /* fourth */
    "*{*+,/"    /* fifth */
    "w{%+,/"    /* sixth */
    "w#q#n+,/"  /* seventh */
    "#{l+,/"    /* eighth */
    "n{n+,/"    /* ninth */
    "+#n+,/"    /* tenth */
    "#;#q#n+,/" /* eleventh */
    "+k#;*+,/"  /* twelfth */

    /* day of Christmas my true love gave to me\n */
    "'r :'d*'3,}{w+K w'K:'+}e#';dq#'l q#'+d'K#!/"

    /* twelve drummers drumming, */
    "+k#;q#'r}eKK#}w'r}eKK{nl]'/"

    /* eleven pipers piping, */
    "#;#q#n'){)#}w'){){nl]'/"

    /* ten lords a-leaping,\n */
    "+#n';d}rw' i;# ){nl]!/"

    /* nine ladies dancing, */
    "n{n#'; r{#w'r nc{nl]'/"

    /* eight maids a-milking, */
    "#{l,+'K {rw' iK{;[{nl]'/"

    /* seven swans a-swimming,\n */
    "w#q#n'wk nw' iwk{KK{nl]!/"

    /* six geese a-laying, */
    "w{%'l##w#' i; :{nl]'/"

    /* five gold rings;\n */
    "*{q#'ld;r'}{nlwb!/"

    /* four calling birds, */
    "*de}'c ;;{nl'-{}rw]'/"

    /* three french hens, */
    "+,}##'*}#nc,',#nw]'/"

    /* two turtle doves\nand */
    "+kd'+e}+;#'rdq#w! nr'/"

    /* a partridge in a pear tree */
    " ') }+}{rl#'{n' ')# }'+}##(!!/";

4) Indent the Function Contents

This step is straight forward… simply indent the contents of the single function:

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,LYRICS)
    :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,CIPHER),a+1);
}

5) Eliminate Implicit Types

If you’re compiling the examples then you may have noticed that there are plenty of implicit type warnings. The main function uses an old C syntax to declare parameter “a” as pointer-to-char. The remaining parameters are implicit integers and the return type of the main function is also an implicit integer. These are fixed in the next sample while taking the opportunity to include the “const” type qualifier:

int main(int t, int _, const 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,LYRICS)
    :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,CIPHER),a+1);
}

6) Rename the Underscore Parameter

The second parameter of the main function is a single underscore. While this is perfectly legal in C, it’s a lot harder to read than an alphabetic character. The next sample has replaced all instances of the underscore parameter with the single character “b”:

int main(int t, int b, const char *a)
{
    return!0<t?t<3?main(-79,-13,a+main(-87,1-b,main(-86,0,a+1)+a)):
    1,t<b?main(t+1,b,a):3,main(-94,-27+t,a)&&t==2?b<13?
    main(2,b+1,"%s %d %d\n"):9:16:t<0?t<-72?main(b,t,LYRICS)
    :t<-50?b==*a?putchar(31[a]):main(-65,b,a+1):main((*a=='/')+t,b,a+1)
    :0<t?main(2,2,"%s"):*a=='/'||main(0,main(-61,*a,CIPHER),a+1);
}

7) Reformat the Ternary Conditional Operator

The obfuscated implementation makes extensive use of the ternary conditional operator. The next sample reformats these ternary operators with some additional whitespace:

int main(int t, int b, const char *a)
{
    return
    !0<t
    ?
        t<3
        ?
            main(-79,-13,a+main(-87,1-b,main(-86,0,a+1)+a))
        :
            1, t<b
            ?
                main(t+1,b,a)
            :
                3, main(-94,-27+t,a)&&t==2
                ?
                    b<13
                    ?
                        main(2,b+1,"%s %d %d\n")
                    :
                        9
                :
                    16
    :
        t<0
        ?
            t<-72
            ?
                main(b,t,LYRICS)
            :
                t<-50
                ?
                    b==*a
                    ?
                        putchar(31[a])
                    :
                        main(-65,b,a+1)
                :
                    main((*a=='/')+t,b,a+1)
        :
            0<t
            ?
                main(2,2,"%s")
            :
                *a=='/'||main(0,main(-61,*a,CIPHER),a+1);
}

8) Replace the Ternary Conditional Statements with If-Else

A simple replacement of the ternary conditional statements with if-else statements improves the presentation of the algorithm. In the following sample, there is yet more white space and the multiple return points have been rationalised into a single point of return by using a temporary integer variable “r”:

int main(int t, int b, const char *a)
{
    int r;
    if (!0 < t)
    {
        if (t < 3)
        {
            main(-79, -13, a + main(-87, 1 - b, main(-86, 0, a + 1) + a));
        }
        else
        {
            1;
        }
        if (t < b)
        {
            main(t + 1, b, a);
        }
        else
        {
            3;
        }
        if (main(-94, -27 + t, a) && t == 2)
        {
            if (b < 13)
            {
                r = main(2, b + 1, "%s %d %d\n");
            }
            else
            {
                r = 9;
            }
        }
        else
        {
            r = 16;
        }
    }
    else
    {
        if (t < 0)
        {
            if (t < -72)
            {
                r = main(b, t, LYRICS);
            }
            else
            {
                if (t < -50)
                {
                    if (b == *a)
                    {
                        r = putchar(31[a]);
                    }
                    else
                    {
                        r = main(-65, b, a + 1);
                    }
                }
                else
                {
                    r = main((*a == '/') + t, b, a + 1);
                }
            }
        }
        else
        {
            if (0 < t)
            {
                r = main(2, 2, "%s");
            }
            else
            {
                r = *a == '/' || main(0, main(-61, *a, CIPHER), a + 1);
            }
        }
    }
    return r;
}

9) Simplify an Array Access

This change is straight forward. The array access “31[a]” is exactly the same as “a[31]” yet the latter is much easier to understand in the context of the 31 character substitution cipher:

    ...
    r = putchar(a[31]);
    ...

10) Add Brackets to Logical Expressions

Personally, I prefer plenty of brackets in compound logical expressions. The following snips are small improvements:

    ...
    if (main(-94, -27 + t, a) && (t == 2))
    ...

    ...
    r = ((*a == '/') || (main(0, main(-61, *a, CIPHER), a + 1)));
    ...

11) Remove Misdirection

There are several instances where the implementation is deliberately misleading. Given the reformatted source code so far, it’s easy to see that there are two “else” clauses with no side effects (“else {1;}” and “else {3;}”). Less obvious is that the parameters that look like string formatting specifiers passed to the main function are unused in that iteration of the function and can be replaced with zero:

    ...
    if (b < 13)
    {
        r = main(2, b + 1, 0);
    }
    ...

    ...
    r = main(2, 2, 0);
    ...

12) Implement a Stand-Alone Recursive Function

The entire algorithm so far uses the single “main” function in an unusual recursive manner. After the last of the twelve changes, the main function looks like a standard C main function and there’s a separate local-scope (static) recursive function which, in time-honoured programmer’s tradition, is called “foo”. This gives the final complete sample after all twelve changes:

#include <stdio.h>

static const char *CIPHER =
    /*
    * Substitution cipher:
    * Replace '!' with '\n'
    * Replace 'e' with 'u'
    * ...
    * Replace ':' with 'y'
    */
     "!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:"
    "\nuwloca-O;m .vpbks,fxntdCeghiry";

static const char *LYRICS =
    "@n'+,#'/"  /* On the */
    "*{}w+/"    /* first */
    "w#cdnr/"   /* second */
    "+,{}r/"    /* third */
    "*de}+,/"   /* fourth */
    "*{*+,/"    /* fifth */
    "w{%+,/"    /* sixth */
    "w#q#n+,/"  /* seventh */
    "#{l+,/"    /* eighth */
    "n{n+,/"    /* ninth */
    "+#n+,/"    /* tenth */
    "#;#q#n+,/" /* eleventh */
    "+k#;*+,/"  /* twelfth */

    /* day of Christmas my true love gave to me\n */
    "'r :'d*'3,}{w+K w'K:'+}e#';dq#'l q#'+d'K#!/"

    /* twelve drummers drumming, */
    "+k#;q#'r}eKK#}w'r}eKK{nl]'/"

    /* eleven pipers piping, */
    "#;#q#n'){)#}w'){){nl]'/"

    /* ten lords a-leaping,\n */
    "+#n';d}rw' i;# ){nl]!/"

    /* nine ladies dancing, */
    "n{n#'; r{#w'r nc{nl]'/"

    /* eight maids a-milking, */
    "#{l,+'K {rw' iK{;[{nl]'/"

    /* seven swans a-swimming,\n */
    "w#q#n'wk nw' iwk{KK{nl]!/"

    /* six geese a-laying, */
    "w{%'l##w#' i; :{nl]'/"

    /* five gold rings;\n */
    "*{q#'ld;r'}{nlwb!/"

    /* four calling birds, */
    "*de}'c ;;{nl'-{}rw]'/"

    /* three french hens, */
    "+,}##'*}#nc,',#nw]'/"

    /* two turtle doves\nand */
    "+kd'+e}+;#'rdq#w! nr'/"

    /* a partridge in a pear tree */
    " ') }+}{rl#'{n' ')# }'+}##(!!/";

static int foo(int t, int b, const char *a)
{
    int r;
    if (!0 < t)
    {
        if (t < 3)
        {
            foo(-79, -13, a + foo(-87, 1 - b, foo(-86, 0, a + 1) + a));
        }
        if (t < b)
        {
            foo(t + 1, b, a);
        }
        if (foo(-94, -27 + t, a) && (t == 2))
        {
            if (b < 13)
            {
                r = foo(2, b + 1, 0);
            }
            else
            {
                r = 9;
            }
        }
        else
        {
            r = 16;
        }
    }
    else
    {
        if (t < 0)
        {
            if (t < -72)
            {
                r = foo(b, t, LYRICS);
            }
            else
            {
                if (t < -50)
                {
                    if (b == *a)
                    {
                        r = putchar(a[31]);
                    }
                    else
                    {
                        r = foo(-65, b, a + 1);
                    }
                }
                else
                {
                    r = foo((*a == '/') + t, b, a + 1);
                }
            }
        }
        else
        {
            if (0 < t)
            {
                r = foo(2, 2, 0);
            }
            else
            {
                r = ((*a == '/') || (foo(0, foo(-61, *a, CIPHER), a + 1)));
            }
        }
    }
    return r;
}

int main(int argc, char *argv[])
{
    return foo(1, 0, 0);
}

There are plenty of changes that could still be made to improve readability, such as more comments and replacing the recursive algorithm with iterative loops… but I’ve made my promised twelve improvements, leaving you with plenty of opportunity to make some of your own.

[1] At the time of writing this blog, the original code can be found on the International Obfuscated C Code Contest website on the “Winning Entries” web page, listed as “phillipps.c” under the 1988 sub-heading.

[2] Credit goes to an analysis by Mike Markowski and to a similar exercise in reformatting the source code by Michael Nahas.

Twelve Ways to Style The Twelve Days

Twelve Ways to Style The Twelve Days

Kevin Jones - Senior Consultant, Embedded Systems

By: Kevin Jones
Senior Consultant, Embedded Systems

10th January 2018

Home » software

During the Christmas period, I was reminded of a now-famous piece of obfuscated C code. This was the winning entry in the 1988 International Obfuscated C Code Contest [see reference 1] and, believe it or not, will print the entire lyrics to “The Twelve Days of Christmas”:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save


#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);
}

There are plenty of articles online that explain how this works; just use your favourite search engine to find out more [see reference 2]. Rather than repeat those descriptions, I’ll stick to the festive theme that prompted this blog and illustrate twelve ways to improve the readability of this wonderful algorithm.

1) Extract the Constant Strings

There are two strings lurking in the source code. The longer string contains an encoded version of the song lyrics and the shorter string contains a substitution cipher to decode the lyrics. The source code is immediately much clearer if these strings are declared near the beginning of the file. In the following example, “static” limits the scope of the strings to one source file and “const” declares them as read-only. I like to use uppercase symbols for constants but that’s nothing more than personal choice. Here’s the modified source code:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

#include 

static const char *CIPHER =
"!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry";

static const char *LYRICS =
"@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' ')# \
}'+}##(!!/";

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,LYRICS)
: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,CIPHER),a+1);
}

2) Reformat the Strings

The two strings are recursively indexed to decode and display the lyrics. Reformatting these strings helps to understand the algorithm. In the next step the lyrics and the cipher are declared using C’s alternative string concatenation syntax. The substitution cipher is split after the 31st character, the lyrics are split at each “/” character and the original code’s “\” concatenation in the lyrics string has been eliminated. There’s also some indentation to improve readability:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

#include 

static const char *CIPHER =
     &quot;!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:&quot;
    &quot;\nuwloca-O;m .vpbks,fxntdCeghiry&quot;;

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

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,&quot;%s %d %d\n&quot;):9:16:t<0?t<-72?main(_,t,LYRICS)
:t<-50?_==*a?putchar(31[a]):main(-65,_,a+1):main((*a=='/')+t,_,a+1)
:0<t?main(2,2,&quot;%s&quot;):*a=='/'||main(0,main(-61,*a,CIPHER),a+1);
}

3) Add Some Comments

All good programmers know that comments are useful. Annotating the constant strings immediately helps understand the algorithm even before any changes are made to the function. I prefer block comments for maximum portability but end-of-line comments would work just as well:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

static const char *CIPHER =
    /*
    * Substitution cipher:
    * Replace '!' with '\n'
    * Replace 'e' with 'u'
    * ...
    * Replace ':' with 'y'
    */
     &quot;!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:&quot;
    &quot;\nuwloca-O;m .vpbks,fxntdCeghiry&quot;;

static const char *LYRICS =
    &quot;@n'+,#'/&quot;  /* On the */
    &quot;*{}w+/&quot;    /* first */
    &quot;w#cdnr/&quot;   /* second */
    &quot;+,{}r/&quot;    /* third */
    &quot;*de}+,/&quot;   /* fourth */
    &quot;*{*+,/&quot;    /* fifth */
    &quot;w{%+,/&quot;    /* sixth */
    &quot;w#q#n+,/&quot;  /* seventh */
    &quot;#{l+,/&quot;    /* eighth */
    &quot;n{n+,/&quot;    /* ninth */
    &quot;+#n+,/&quot;    /* tenth */
    &quot;#;#q#n+,/&quot; /* eleventh */
    &quot;+k#;*+,/&quot;  /* twelfth */

    /* day of Christmas my true love gave to me\n */
    &quot;'r :'d*'3,}{w+K w'K:'+}e#';dq#'l q#'+d'K#!/&quot;

    /* twelve drummers drumming, */
    &quot;+k#;q#'r}eKK#}w'r}eKK{nl]'/&quot;

    /* eleven pipers piping, */
    &quot;#;#q#n'){)#}w'){){nl]'/&quot;

    /* ten lords a-leaping,\n */
    &quot;+#n';d}rw' i;# ){nl]!/&quot;

    /* nine ladies dancing, */
    &quot;n{n#'; r{#w'r nc{nl]'/&quot;

    /* eight maids a-milking, */
    &quot;#{l,+'K {rw' iK{;[{nl]'/&quot;

    /* seven swans a-swimming,\n */
    &quot;w#q#n'wk nw' iwk{KK{nl]!/&quot;

    /* six geese a-laying, */
    &quot;w{%'l##w#' i; :{nl]'/&quot;

    /* five gold rings;\n */
    &quot;*{q#'ld;r'}{nlwb!/&quot;

    /* four calling birds, */
    &quot;*de}'c ;;{nl'-{}rw]'/&quot;

    /* three french hens, */
    &quot;+,}##'*}#nc,',#nw]'/&quot;

    /* two turtle doves\nand */
    &quot;+kd'+e}+;#'rdq#w! nr'/&quot;

    /* a partridge in a pear tree */
    &quot; ') }+}{rl#'{n' ')# }'+}##(!!/&quot;;

4) Indent the Function Contents

This step is straight forward… simply indent the contents of the single function:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

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,LYRICS)
    :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,CIPHER),a+1);
}

5) Eliminate Implicit Types

If you’re compiling the examples then you may have noticed that there are plenty of implicit type warnings. The main function uses an old C syntax to declare parameter “a” as pointer-to-char. The remaining parameters are implicit integers and the return type of the main function is also an implicit integer. These are fixed in the next sample while taking the opportunity to include the “const” type qualifier:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

int main(int t, int _, const 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,LYRICS)
    :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,CIPHER),a+1);
}

6) Rename the Underscore Parameter

The second parameter of the main function is a single underscore. While this is perfectly legal in C, it’s a lot harder to read than an alphabetic character. The next sample has replaced all instances of the underscore parameter with the single character “b”:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

int main(int t, int b, const char *a)
{
    return!0<t?t<3?main(-79,-13,a+main(-87,1-b,main(-86,0,a+1)+a)):
    1,t<b?main(t+1,b,a):3,main(-94,-27+t,a)&&t==2?b<13?
    main(2,b+1,"%s %d %d\n"):9:16:t<0?t<-72?main(b,t,LYRICS)
    :t<-50?b==*a?putchar(31[a]):main(-65,b,a+1):main((*a=='/')+t,b,a+1)
    :0<t?main(2,2,"%s"):*a=='/'||main(0,main(-61,*a,CIPHER),a+1);
}

7) Reformat the Ternary Conditional Operator

The obfuscated implementation makes extensive use of the ternary conditional operator. The next sample reformats these ternary operators with some additional whitespace:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

int main(int t, int b, const char *a)
{
return
!0

<pre> 

8) Replace the Ternary Conditional Statements with If-Else

A simple replacement of the ternary conditional statements with if-else statements improves the presentation of the algorithm. In the following sample, there is yet more white space and the multiple return points have been rationalised into a single point of return by using a temporary integer variable “r”:

int main(int t, int b, const char *a)
{
    int r;
    if (!0 < t)
    {
        if (t < 3)
        {
            main(-79, -13, a + main(-87, 1 - b, main(-86, 0, a + 1) + a));
        }
        else
        {
            1;
        }
        if (t < b)
        {
            main(t + 1, b, a);
        }
        else
        {
            3;
        }
        if (main(-94, -27 + t, a) && t == 2)
        {
            if (b < 13)
            {
                r = main(2, b + 1, "%s %d %d\n");
            }
            else
            {
                r = 9;
            }
        }
        else
        {
            r = 16;
        }
    }
    else
    {
        if (t < 0)
        {
            if (t < -72)
            {
                r = main(b, t, LYRICS);
            }
            else
            {
                if (t < -50)
                {
                    if (b == *a)
                    {
                        r = putchar(31[a]);
                    }
                    else
                    {
                        r = main(-65, b, a + 1);
                    }
                }
                else
                {
                    r = main((*a == '/') + t, b, a + 1);
                }
            }
        }
        else
        {
            if (0 < t)
            {
                r = main(2, 2, "%s");
            }
            else
            {
                r = *a == '/' || main(0, main(-61, *a, CIPHER), a + 1);
            }
        }
    }
    return r;
}

9) Simplify an Array Access

This change is straight forward. The array access “31[a]” is exactly the same as “a[31]” yet the latter is much easier to understand in the context of the 31 character substitution cipher:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

    ...
    r = putchar(a[31]);
    ...

10) Add Brackets to Logical Expressions

Personally, I prefer plenty of brackets in compound logical expressions. The following snips are small improvements:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

    ...
    if (main(-94, -27 + t, a) && (t == 2))
    ...

    ...
    r = ((*a == '/') || (main(0, main(-61, *a, CIPHER), a + 1)));
    ...

11) Remove Misdirection

There are several instances where the implementation is deliberately misleading. Given the reformatted source code so far, it’s easy to see that there are two “else” clauses with no side effects (“else {1;}” and “else {3;}”). Less obvious is that the parameters that look like string formatting specifiers passed to the main function are unused in that iteration of the function and can be replaced with zero:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

    ...
    if (b < 13)
    {
        r = main(2, b + 1, 0);
    }
    ...

    ...
    r = main(2, 2, 0);
    ...

12) Implement a Stand-Alone Recursive Function

The entire algorithm so far uses the single “main” function in an unusual recursive manner. After the last of the twelve changes, the main function looks like a standard C main function and there’s a separate local-scope (static) recursive function which, in time-honoured programmer’s tradition, is called “foo”. This gives the final complete sample after all twelve changes:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

#include 

static const char *CIPHER =
    /*
    * Substitution cipher:
    * Replace '!' with '\n'
    * Replace 'e' with 'u'
    * ...
    * Replace ':' with 'y'
    */
     "!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:"
    "\nuwloca-O;m .vpbks,fxntdCeghiry";

static const char *LYRICS =
    "@n'+,#'/"  /* On the */
    "*{}w+/"    /* first */
    "w#cdnr/"   /* second */
    "+,{}r/"    /* third */
    "*de}+,/"   /* fourth */
    "*{*+,/"    /* fifth */
    "w{%+,/"    /* sixth */
    "w#q#n+,/"  /* seventh */
    "#{l+,/"    /* eighth */
    "n{n+,/"    /* ninth */
    "+#n+,/"    /* tenth */
    "#;#q#n+,/" /* eleventh */
    "+k#;*+,/"  /* twelfth */

    /* day of Christmas my true love gave to me\n */
    "'r :'d*'3,}{w+K w'K:'+}e#';dq#'l q#'+d'K#!/"

    /* twelve drummers drumming, */
    "+k#;q#'r}eKK#}w'r}eKK{nl]'/"

    /* eleven pipers piping, */
    "#;#q#n'){)#}w'){){nl]'/"

    /* ten lords a-leaping,\n */
    "+#n';d}rw' i;# ){nl]!/"

    /* nine ladies dancing, */
    "n{n#'; r{#w'r nc{nl]'/"

    /* eight maids a-milking, */
    "#{l,+'K {rw' iK{;[{nl]'/"

    /* seven swans a-swimming,\n */
    "w#q#n'wk nw' iwk{KK{nl]!/"

    /* six geese a-laying, */
    "w{%'l##w#' i; :{nl]'/"

    /* five gold rings;\n */
    "*{q#'ld;r'}{nlwb!/"

    /* four calling birds, */
    "*de}'c ;;{nl'-{}rw]'/"

    /* three french hens, */
    "+,}##'*}#nc,',#nw]'/"

    /* two turtle doves\nand */
    "+kd'+e}+;#'rdq#w! nr'/"

    /* a partridge in a pear tree */
    " ') }+}{rl#'{n' ')# }'+}##(!!/";

static int foo(int t, int b, const char *a)
{
    int r;
    if (!0 < t)
    {
        if (t < 3)
        {
            foo(-79, -13, a + foo(-87, 1 - b, foo(-86, 0, a + 1) + a));
        }
        if (t < b)
        {
            foo(t + 1, b, a);
        }
        if (foo(-94, -27 + t, a) && (t == 2))
        {
            if (b < 13)
            {
                r = foo(2, b + 1, 0);
            }
            else
            {
                r = 9;
            }
        }
        else
        {
            r = 16;
        }
    }
    else
    {
        if (t < 0)
        {
            if (t < -72)
            {
                r = foo(b, t, LYRICS);
            }
            else
            {
                if (t < -50)
                {
                    if (b == *a)
                    {
                        r = putchar(a[31]);
                    }
                    else
                    {
                        r = foo(-65, b, a + 1);
                    }
                }
                else
                {
                    r = foo((*a == '/') + t, b, a + 1);
                }
            }
        }
        else
        {
            if (0 < t)
            {
                r = foo(2, 2, 0);
            }
            else
            {
                r = ((*a == '/') || (foo(0, foo(-61, *a, CIPHER), a + 1)));
            }
        }
    }
    return r;
}

int main(int argc, char *argv[])
{
    return foo(1, 0, 0);
}

There are plenty of changes that could still be made to improve readability, such as more comments and replacing the recursive algorithm with iterative loops… but I’ve made my promised twelve improvements, leaving you with plenty of opportunity to make some of your own.





[1] At the time of writing this blog, the original code can be found on the International Obfuscated C Code Contest website on the “Winning Entries” web page, listed as “phillipps.c” under the 1988 sub-heading.

[2] Credit goes to an analysis by Mike Markowski and to a similar exercise in reformatting the source code by Michael Nahas.

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

During the Christmas period, I was reminded of a now-famous piece of obfuscated C code. This was the winning entry in the 1988 International Obfuscated C Code Contest [see reference 1] and, believe it or not, will print the entire lyrics to “The Twelve Days of Christmas”:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save


#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);
}

There are plenty of articles online that explain how this works; just use your favourite search engine to find out more [see reference 2]. Rather than repeat those descriptions, I’ll stick to the festive theme that prompted this blog and illustrate twelve ways to improve the readability of this wonderful algorithm.

1) Extract the Constant Strings

There are two strings lurking in the source code. The longer string contains an encoded version of the song lyrics and the shorter string contains a substitution cipher to decode the lyrics. The source code is immediately much clearer if these strings are declared near the beginning of the file. In the following example, “static” limits the scope of the strings to one source file and “const” declares them as read-only. I like to use uppercase symbols for constants but that’s nothing more than personal choice. Here’s the modified source code:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

#include <stdio.h>

static const char *CIPHER =
&quot;!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry&quot;;

static const char *LYRICS =
&quot;@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' ')# \
}'+}##(!!/&quot;;

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,&quot;%s %d %d\n&quot;):9:16:t<0?t<-72?main(_,t,LYRICS)
:t<-50?_==*a?putchar(31[a]):main(-65,_,a+1):main((*a=='/')+t,_,a+1)
:0<t?main(2,2,&quot;%s&quot;):*a=='/'||main(0,main(-61,*a,CIPHER),a+1);
}

2) Reformat the Strings

The two strings are recursively indexed to decode and display the lyrics. Reformatting these strings helps to understand the algorithm. In the next step the lyrics and the cipher are declared using C’s alternative string concatenation syntax. The substitution cipher is split after the 31st character, the lyrics are split at each “/” character and the original code’s “\” concatenation in the lyrics string has been eliminated. There’s also some indentation to improve readability:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

#include 

static const char *CIPHER =
     &quot;!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:&quot;
    &quot;\nuwloca-O;m .vpbks,fxntdCeghiry&quot;;

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

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,&quot;%s %d %d\n&quot;):9:16:t<0?t<-72?main(_,t,LYRICS)
:t<-50?_==*a?putchar(31[a]):main(-65,_,a+1):main((*a=='/')+t,_,a+1)
:0<t?main(2,2,&quot;%s&quot;):*a=='/'||main(0,main(-61,*a,CIPHER),a+1);
}

3) Add Some Comments

All good programmers know that comments are useful. Annotating the constant strings immediately helps understand the algorithm even before any changes are made to the function. I prefer block comments for maximum portability but end-of-line comments would work just as well:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

static const char *CIPHER =
    /*
    * Substitution cipher:
    * Replace '!' with '\n'
    * Replace 'e' with 'u'
    * ...
    * Replace ':' with 'y'
    */
     &quot;!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:&quot;
    &quot;\nuwloca-O;m .vpbks,fxntdCeghiry&quot;;

static const char *LYRICS =
    &quot;@n'+,#'/&quot;  /* On the */
    &quot;*{}w+/&quot;    /* first */
    &quot;w#cdnr/&quot;   /* second */
    &quot;+,{}r/&quot;    /* third */
    &quot;*de}+,/&quot;   /* fourth */
    &quot;*{*+,/&quot;    /* fifth */
    &quot;w{%+,/&quot;    /* sixth */
    &quot;w#q#n+,/&quot;  /* seventh */
    &quot;#{l+,/&quot;    /* eighth */
    &quot;n{n+,/&quot;    /* ninth */
    &quot;+#n+,/&quot;    /* tenth */
    &quot;#;#q#n+,/&quot; /* eleventh */
    &quot;+k#;*+,/&quot;  /* twelfth */

    /* day of Christmas my true love gave to me\n */
    &quot;'r :'d*'3,}{w+K w'K:'+}e#';dq#'l q#'+d'K#!/&quot;

    /* twelve drummers drumming, */
    &quot;+k#;q#'r}eKK#}w'r}eKK{nl]'/&quot;

    /* eleven pipers piping, */
    &quot;#;#q#n'){)#}w'){){nl]'/&quot;

    /* ten lords a-leaping,\n */
    &quot;+#n';d}rw' i;# ){nl]!/&quot;

    /* nine ladies dancing, */
    &quot;n{n#'; r{#w'r nc{nl]'/&quot;

    /* eight maids a-milking, */
    &quot;#{l,+'K {rw' iK{;[{nl]'/&quot;

    /* seven swans a-swimming,\n */
    &quot;w#q#n'wk nw' iwk{KK{nl]!/&quot;

    /* six geese a-laying, */
    &quot;w{%'l##w#' i; :{nl]'/&quot;

    /* five gold rings;\n */
    &quot;*{q#'ld;r'}{nlwb!/&quot;

    /* four calling birds, */
    &quot;*de}'c ;;{nl'-{}rw]'/&quot;

    /* three french hens, */
    &quot;+,}##'*}#nc,',#nw]'/&quot;

    /* two turtle doves\nand */
    &quot;+kd'+e}+;#'rdq#w! nr'/&quot;

    /* a partridge in a pear tree */
    &quot; ') }+}{rl#'{n' ')# }'+}##(!!/&quot;;

4) Indent the Function Contents

This step is straight forward… simply indent the contents of the single function:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

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,&quot;%s %d %d\n&quot;):9:16:t<0?t<-72?main(_,t,LYRICS)
    :t<-50?_==*a?putchar(31[a]):main(-65,_,a+1):main((*a=='/')+t,_,a+1)
    :0<t?main(2,2,&quot;%s&quot;):*a=='/'||main(0,main(-61,*a,CIPHER),a+1);
}

5) Eliminate Implicit Types

If you’re compiling the examples then you may have noticed that there are plenty of implicit type warnings. The main function uses an old C syntax to declare parameter “a” as pointer-to-char. The remaining parameters are implicit integers and the return type of the main function is also an implicit integer. These are fixed in the next sample while taking the opportunity to include the “const” type qualifier:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

int main(int t, int _, const 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,&quot;%s %d %d\n&quot;):9:16:t<0?t<-72?main(_,t,LYRICS)
    :t<-50?_==*a?putchar(31[a]):main(-65,_,a+1):main((*a=='/')+t,_,a+1)
    :0<t?main(2,2,&quot;%s&quot;):*a=='/'||main(0,main(-61,*a,CIPHER),a+1);
}

6) Rename the Underscore Parameter

The second parameter of the main function is a single underscore. While this is perfectly legal in C, it’s a lot harder to read than an alphabetic character. The next sample has replaced all instances of the underscore parameter with the single character “b”:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

int main(int t, int b, const char *a)
{
    return!0<t?t<3?main(-79,-13,a+main(-87,1-b,main(-86,0,a+1)+a)):
    1,t<b?main(t+1,b,a):3,main(-94,-27+t,a)&&t==2?b<13?
    main(2,b+1,&quot;%s %d %d\n&quot;):9:16:t<0?t<-72?main(b,t,LYRICS)
    :t<-50?b==*a?putchar(31[a]):main(-65,b,a+1):main((*a=='/')+t,b,a+1)
    :0<t?main(2,2,&quot;%s&quot;):*a=='/'||main(0,main(-61,*a,CIPHER),a+1);
}

7) Reformat the Ternary Conditional Operator

The obfuscated implementation makes extensive use of the ternary conditional operator. The next sample reformats these ternary operators with some additional whitespace:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

int main(int t, int b, const char *a)
{
    return
    !0<t
    ?
        t<3
        ?
            main(-79,-13,a+main(-87,1-b,main(-86,0,a+1)+a))
        :
            1, t<b
            ?
                main(t+1,b,a)
            :
                3, main(-94,-27+t,a)&&t==2
                ?
                    b<13
                    ?
                        main(2,b+1,&quot;%s %d %d\n&quot;)
                    :
                        9
                :
                    16
    :
        t<0
        ?
            t<-72
            ?
                main(b,t,LYRICS)
            :
                t<-50
                ?
                    b==*a
                    ?
                        putchar(31[a])
                    :
                        main(-65,b,a+1)
                :
                    main((*a=='/')+t,b,a+1)
        :
            0<t
            ?
                main(2,2,&quot;%s&quot;)
            :
                *a=='/'||main(0,main(-61,*a,CIPHER),a+1);
}

8) Replace the Ternary Conditional Statements with If-Else

A simple replacement of the ternary conditional statements with if-else statements improves the presentation of the algorithm. In the following sample, there is yet more white space and the multiple return points have been rationalised into a single point of return by using a temporary integer variable “r”:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

int main(int t, int b, const char *a)
{
    int r;
    if (!0 < t)
    {
        if (t < 3)
        {
            main(-79, -13, a + main(-87, 1 - b, main(-86, 0, a + 1) + a));
        }
        else
        {
            1;
        }
        if (t < b)
        {
            main(t + 1, b, a);
        }
        else
        {
            3;
        }
        if (main(-94, -27 + t, a) && t == 2)
        {
            if (b < 13)
            {
                r = main(2, b + 1, &quot;%s %d %d\n&quot;);
            }
            else
            {
                r = 9;
            }
        }
        else
        {
            r = 16;
        }
    }
    else
    {
        if (t < 0)
        {
            if (t < -72)
            {
                r = main(b, t, LYRICS);
            }
            else
            {
                if (t < -50)
                {
                    if (b == *a)
                    {
                        r = putchar(31[a]);
                    }
                    else
                    {
                        r = main(-65, b, a + 1);
                    }
                }
                else
                {
                    r = main((*a == '/') + t, b, a + 1);
                }
            }
        }
        else
        {
            if (0 < t)
            {
                r = main(2, 2, &quot;%s&quot;);
            }
            else
            {
                r = *a == '/' || main(0, main(-61, *a, CIPHER), a + 1);
            }
        }
    }
    return r;
}

9) Simplify an Array Access

This change is straight forward. The array access “31[a]” is exactly the same as “a[31]” yet the latter is much easier to understand in the context of the 31 character substitution cipher:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

    ...
    r = putchar(a[31]);
    ...

10) Add Brackets to Logical Expressions

Personally, I prefer plenty of brackets in compound logical expressions. The following snips are small improvements:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

    ...
    if (main(-94, -27 + t, a) && (t == 2))
    ...

    ...
    r = ((*a == '/') || (main(0, main(-61, *a, CIPHER), a + 1)));
    ...

11) Remove Misdirection

There are several instances where the implementation is deliberately misleading. Given the reformatted source code so far, it’s easy to see that there are two “else” clauses with no side effects (“else {1;}” and “else {3;}”). Less obvious is that the parameters that look like string formatting specifiers passed to the main function are unused in that iteration of the function and can be replaced with zero:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

    ...
    if (b < 13)
    {
        r = main(2, b + 1, 0);
    }
    ...

    ...
    r = main(2, 2, 0);
    ...

12) Implement a Stand-Alone Recursive Function

The entire algorithm so far uses the single “main” function in an unusual recursive manner. After the last of the twelve changes, the main function looks like a standard C main function and there’s a separate local-scope (static) recursive function which, in time-honoured programmer’s tradition, is called “foo”. This gives the final complete sample after all twelve changes:

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

#include 

static const char *CIPHER =
    /*
    * Substitution cipher:
    * Replace '!' with '\n'
    * Replace 'e' with 'u'
    * ...
    * Replace ':' with 'y'
    */
     &quot;!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:&quot;
    &quot;\nuwloca-O;m .vpbks,fxntdCeghiry&quot;;

static const char *LYRICS =
    &quot;@n'+,#'/&quot;  /* On the */
    &quot;*{}w+/&quot;    /* first */
    &quot;w#cdnr/&quot;   /* second */
    &quot;+,{}r/&quot;    /* third */
    &quot;*de}+,/&quot;   /* fourth */
    &quot;*{*+,/&quot;    /* fifth */
    &quot;w{%+,/&quot;    /* sixth */
    &quot;w#q#n+,/&quot;  /* seventh */
    &quot;#{l+,/&quot;    /* eighth */
    &quot;n{n+,/&quot;    /* ninth */
    &quot;+#n+,/&quot;    /* tenth */
    &quot;#;#q#n+,/&quot; /* eleventh */
    &quot;+k#;*+,/&quot;  /* twelfth */

    /* day of Christmas my true love gave to me\n */
    &quot;'r :'d*'3,}{w+K w'K:'+}e#';dq#'l q#'+d'K#!/&quot;

    /* twelve drummers drumming, */
    &quot;+k#;q#'r}eKK#}w'r}eKK{nl]'/&quot;

    /* eleven pipers piping, */
    &quot;#;#q#n'){)#}w'){){nl]'/&quot;

    /* ten lords a-leaping,\n */
    &quot;+#n';d}rw' i;# ){nl]!/&quot;

    /* nine ladies dancing, */
    &quot;n{n#'; r{#w'r nc{nl]'/&quot;

    /* eight maids a-milking, */
    &quot;#{l,+'K {rw' iK{;[{nl]'/&quot;

    /* seven swans a-swimming,\n */
    &quot;w#q#n'wk nw' iwk{KK{nl]!/&quot;

    /* six geese a-laying, */
    &quot;w{%'l##w#' i; :{nl]'/&quot;

    /* five gold rings;\n */
    &quot;*{q#'ld;r'}{nlwb!/&quot;

    /* four calling birds, */
    &quot;*de}'c ;;{nl'-{}rw]'/&quot;

    /* three french hens, */
    &quot;+,}##'*}#nc,',#nw]'/&quot;

    /* two turtle doves\nand */
    &quot;+kd'+e}+;#'rdq#w! nr'/&quot;

    /* a partridge in a pear tree */
    &quot; ') }+}{rl#'{n' ')# }'+}##(!!/&quot;;

static int foo(int t, int b, const char *a)
{
    int r;
    if (!0 < t)
    {
        if (t < 3)
        {
            foo(-79, -13, a + foo(-87, 1 - b, foo(-86, 0, a + 1) + a));
        }
        if (t < b)
        {
            foo(t + 1, b, a);
        }
        if (foo(-94, -27 + t, a) && (t == 2))
        {
            if (b < 13)
            {
                r = foo(2, b + 1, 0);
            }
            else
            {
                r = 9;
            }
        }
        else
        {
            r = 16;
        }
    }
    else
    {
        if (t < 0)
        {
            if (t < -72)
            {
                r = foo(b, t, LYRICS);
            }
            else
            {
                if (t < -50)
                {
                    if (b == *a)
                    {
                        r = putchar(a[31]);
                    }
                    else
                    {
                        r = foo(-65, b, a + 1);
                    }
                }
                else
                {
                    r = foo((*a == '/') + t, b, a + 1);
                }
            }
        }
        else
        {
            if (0 < t)
            {
                r = foo(2, 2, 0);
            }
            else
            {
                r = ((*a == '/') || (foo(0, foo(-61, *a, CIPHER), a + 1)));
            }
        }
    }
    return r;
}

int main(int argc, char *argv[])
{
    return foo(1, 0, 0);
}

There are plenty of changes that could still be made to improve readability, such as more comments and replacing the recursive algorithm with iterative loops… but I’ve made my promised twelve improvements, leaving you with plenty of opportunity to make some of your own.





[1] At the time of writing this blog, the original code can be found on the International Obfuscated C Code Contest website on the “Winning Entries” web page, listed as “phillipps.c” under the 1988 sub-heading.

[2] Credit goes to an analysis by Mike Markowski and to a similar exercise in reformatting the source code by Michael Nahas.

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Virtual Reality: What’s Science Fiction and Science Fact?

Virtual Reality: What’s Science Fiction and Science Fact?

Chris Lancaster - Graduate Software Engineer

By: Chris Lancaster
Graduate Software Engineer

7th June 2017

Home » software

When the term ‘Virtual Reality (VR)’ is brought up, it instantly conjures the picture of a person being placed inside a Computer Generated Image (CGI) environment and them interacting with their newly simulated surroundings. Science fiction has used the concept numerous times to craft this far-fetched idea of what technology can do, but is it really beyond our grasp?

Like all technology, it goes through a lifecycle. At first, some new discovery is made and it seems like it could solve all the world’s problems. As news of such a discovery spreads, expectations grow beyond what is currently possible. In the ‘Technology Hype Cycle’, when expectations are at their highest, it is known as the ‘Peak of Inflated Expectations’. This peak then falls away as people move on with their lives, but that doesn’t mean the technology fades as well.

In fact, it can be quite the opposite, as it is being continually developed and refined over and over again, each time creating new possibilities and applications. Over time, more realistic expectations begin to grow. That’s where virtual reality now sits, on the ‘Slope of Enlightenment’, ready to be put to use in the real world.

The problem isn’t technology, the technology is already here. A simple mobile phone is powerful enough to be able to render an environment in which we can look around and move. Google Cardboard is a cheap way of allowing anyone to take advantage of the power in their pockets. Simply place your phone in the cardboard case and use the Google Cardboard app to render an environment.  On the other end of the scale, there are more complex headsets, such as HTC’s Vive, which not only gives the user the visual experience but allows them to interact with objects in the VR world through the use of controllers.

So if it’s that easy to experience VR, why doesn’t everyone use it?

We have the technology, what we’re lacking is content which the technology can use. It’s a problem that will be solved with time, once content creators understand what can be done with such technology. Currently, the leading market for VR is gaming but what if it could be used for training purposes?

Time Shift Reality

If VR is a CGI environment, then ‘time shift reality’ is the idea of placing someone in another part of the world and in a different time through 360˚ videos /pictures. What you see does actually exist and you can experience it from the comfort of your own home. Take this video for example:

Save

Save

Footage owned by DiscoveryVR

I can take a gondola ride through Venice and choose where I want to look as if I was actually there. While this example is one of the more relaxing VR experiences, the educational implications are staggering.

Medical Realities is a VR/AR company specialising in medical training videos that puts the viewer inside the operating theatre, overseeing an operation through the eyes of the consultant surgeon. Placing someone within such a procedure is an invaluable experience, yet now it can be re-lived again and again. Each time a different focus can be taken, giving any medical student a complete overview of the inner workings of an operating theatre.

A different industry is real estate, Matterport is a company that builds 3D reconstructions of buildings – creating a “dollhouse” which a user can tour and move around in. It is not a virtual tour, as in a slideshow of images, but one which can be moved through and looked at from multiple different angles. Think Google Street View but for a house. This lets retailers show off their houses to a wider audience and give them the same experience as if they were actually there.

VR is on the up and up, with a prediction that the virtual reality market will be worth $120 billion by 2020. It is certainly an area that you should keep your eye on.

Apple has been doing so with their latest iPhone 7 Plus. Their newest device has a dual rear-facing camera setup. I can only speculate that there isn’t really any need for two cameras unless you want to be able to detect depth – a key requirement for augmented reality (AR).

This combined with the fact that Apple bought leading AR company, Metaio, in 2015 suggests that they’re looking to move into the VR/AR market in the near future. Metaio has also been suspiciously quiet on what they have been working on recently.

VR’s potential is large and far-reaching. Once the content issue is solved, I wouldn’t be surprised to see it in classrooms and homes, in much the same way we already have computers in most aspects of our lives. So maybe one day we can all have our own Star Trek Holodeck.

Save

Save

Save

Save

When the term ‘Virtual Reality (VR)’ is brought up, it instantly conjures the picture of a person being placed inside a Computer Generated Image (CGI) environment and them interacting with their newly simulated surroundings. Science fiction has used the concept numerous times to craft this far-fetched idea of what technology can do, but is it really beyond our grasp?

Like all technology, it goes through a lifecycle. At first, some new discovery is made and it seems like it could solve all the world’s problems. As news of such a discovery spreads, expectations grow beyond what is currently possible. In the ‘Technology Hype Cycle’, when expectations are at their highest, it is known as the ‘Peak of Inflated Expectations’. This peak then falls away as people move on with their lives, but that doesn’t mean the technology fades as well.

In fact, it can be quite the opposite, as it is being continually developed and refined over and over again, each time creating new possibilities and applications. Over time, more realistic expectations begin to grow. That’s where virtual reality now sits, on the ‘Slope of Enlightenment’, ready to be put to use in the real world.

The problem isn’t technology, the technology is already here. A simple mobile phone is powerful enough to be able to render an environment in which we can look around and move. Google Cardboard is a cheap way of allowing anyone to take advantage of the power in their pockets. Simply place your phone in the cardboard case and use the Google Cardboard app to render an environment.  On the other end of the scale, there are more complex headsets, such as HTC’s Vive, which not only gives the user the visual experience but allows them to interact with objects in the VR world through the use of controllers.

So if it’s that easy to experience VR, why doesn’t everyone use it?

We have the technology, what we’re lacking is content which the technology can use. It’s a problem that will be solved with time, once content creators understand what can be done with such technology. Currently, the leading market for VR is gaming but what if it could be used for training purposes?

Time Shift Reality

If VR is a CGI environment, then ‘time shift reality’ is the idea of placing someone in another part of the world and in a different time through 360˚ videos /pictures. What you see does actually exist and you can experience it from the comfort of your own home. Take this video for example:

Save

Save

Save

Footage owned by DiscoveryVR

I can take a gondola ride through Venice and choose where I want to look as if I was actually there. While this example is one of the more relaxing VR experiences, the educational implications are staggering.

Medical Realities is a VR/AR company specialising in medical training videos that puts the viewer inside the operating theatre, overseeing an operation through the eyes of the consultant surgeon. Placing someone within such a procedure is an invaluable experience, yet now it can be re-lived again and again. Each time a different focus can be taken, giving any medical student a complete overview of the inner workings of an operating theatre.

A different industry is real estate, Matterport is a company that builds 3D reconstructions of buildings – creating a “dollhouse” which a user can tour and move around in. It is not a virtual tour, as in a slideshow of images, but one which can be moved through and looked at from multiple different angles. Think Google Street View but for a house. This lets retailers show off their houses to a wider audience and give them the same experience as if they were actually there.

VR is on the up and up, with a prediction that the virtual reality market will be worth $120 billion by 2020. It is certainly an area that you should keep your eye on.

Apple has been doing so with their latest iPhone 7 Plus. Their newest device has a dual rear-facing camera setup. I can only speculate that there isn’t really any need for two cameras unless you want to be able to detect depth – a key requirement for augmented reality (AR).

This combined with the fact that Apple bought leading AR company, Metaio, in 2015 suggests that they’re looking to move into the VR/AR market in the near future. Metaio has also been suspiciously quiet on what they have been working on recently.

VR’s potential is large and far-reaching. Once the content issue is solved, I wouldn’t be surprised to see it in classrooms and homes, in much the same way we already have computers in most aspects of our lives. So maybe one day we can all have our own Star Trek Holodeck.

Save

Save

Save

Save

Save

Save

Save

Save

An insight from a Graduate Engineer

An insight from a Graduate Engineer

Edson Da'Silva - Graduate Engineer, Communication Systems

By: Edson Da’Silva
Graduate Engineer, Communication Systems

31st May 2017

Home » software

I’m Edson Da’Silva and I’m a graduate engineer here at Plextek. I joined the company in September 2016 and it’s been a fantastic start to working life. I’ve met so many great people and I’ve been working on a good number of interesting projects, which have been beyond what I ever expected to do. So here is my view of a working day as a graduate at Plextek.

As with every engineer, my day starts with coffee (it appears we can’t function without it), then once the caffeine has kicked in I prioritise my day’s work; due to the demands of a consultancy, prioritisation changes day to day so it’s important to refocus this daily.

An insight from a Graduate Engineer - Edson Da'SilvaOn a normal week, I can be doing anything from assisting clients with technical enquiries, to co-writing project proposals and typing up any relevant documents. I’m involved in many aspects of Plextek’s client service, which I really enjoy; however, a majority of my work is hardware design and testing. Occasionally, I get involved with software design and mechanical prototyping as well. It’s great to get involved in so many aspects, as I get to experience other areas of product development, which I ordinarily wouldn’t be exposed to.

The starting point for most hardware designs is a simulation. This might include testing and simulating the frequency response of a circuit. As for the circuit design, I am responsible for putting together the schematic diagram of the circuit, which gets passed over to the PCB team for the layout and manufacturing.

Depending on the nature of the project, I occasionally get involved with some aspects of mechanical prototyping. For example, the project may have a PCB that will be exposed to extreme weather conditions and will require a protective enclosure for it. My role would be to conduct some testing of materials in the lab and pull a concept together for testing purposes. Once we have proven that the concept is suitable and the whole system works well in the enclosure, I work with the mechanical design team to fully implement it into the product so that it is ready for manufacture.

Sometimes software is required to test the functionality of a hardware design, and I occasionally get to write it myself, which enables me to gain further experience and grow my skillset. While I haven’t done much software design yet, packages, such as “Visual Studios”, are very powerful and flexible, allowing for small test programmes as well as large software packages to be built using the same tools.

At any given moment, the projects I work on can focus on a wide variety of different tasks. On a busy day, I can be working on up to three completely different projects. Whilst that can be challenging at times, since joining Plextek, I have improved my ability to effectively distribute my time between projects. I also enjoy switching between projects and tasks, as it gives me some time to pull away from a problem and come back to it later with a different approach.

An insight from a Graduate Engineer - EdsonAn integral part of being a Graduate Engineer at Plextek is the internal engineering training program. The in-house training scheme incorporates teachings from Plextek’s most experienced members and practical tasks that look to provide training across all areas of the business. So in between project work and other tasks, I try to get on with some of those activities too.

Because the work can be so varied, it is not uncommon for me to come across a piece of technology I am not familiar with. In my mind, it’s all part of the learning curve and I often do my own research when I get home so I can learn a little more about the subject area. An important aspect of being an Electronics Engineer is to continuously progress and learn as technology evolves.

What I enjoy most about being a Graduate Engineer at Plextek is that since joining, every single project I have worked on has been fascinating. The variety of the work, and the challenge of climbing a new learning curve with every new project, makes every day an exciting prospective. A big part of being a graduate engineer is the creative way in which you tackle a hardware, software or mechanical problem. I will often work as part of a team, so we can bounce ideas off each other and come up with inventive ways to solve a problem or design a prototype for example, and although it can be challenging at times, it is always a rewarding experience.


Keep an eye on our careers page for Graduate Career opportunities

Save

Save

Save

I’m Edson Da’Silva and I’m a graduate engineer here at Plextek. I joined the company in September 2016 and it’s been a fantastic start to working life. I’ve met so many great people and I’ve been working on a good number of interesting projects, which have been beyond what I ever expected to do. So here is my view of a working day as a graduate at Plextek.

As with every engineer, my day starts with coffee (it appears we can’t function without it), then once the caffeine has kicked in I prioritise my day’s work; due to the demands of a consultancy, prioritisation changes day to day so it’s important to refocus this daily.

An insight from a Graduate Engineer - Edson Da'SilvaOn a normal week, I can be doing anything from assisting clients with technical enquiries, to co-writing project proposals and typing up any relevant documents. I’m involved in many aspects of Plextek’s client service, which I really enjoy; however, a majority of my work is hardware design and testing. Occasionally, I get involved with software design and mechanical prototyping as well. It’s great to get involved in so many aspect,s as I get to experience other areas of product development, which I ordinarily wouldn’t be exposed to.

The starting point for most hardware designs is a simulation. This might include testing and simulating the frequency response of a circuit. As for the circuit design, I am responsible for putting together the schematic diagram of the circuit, which gets passed over to the PCB team for the layout and manufacturing.

Depending on the nature of the project, I occasionally get involved with some aspects of mechanical prototyping. For example, the project may have a PCB that will be exposed to extreme weather conditions and will require a protective enclosure for it. My role would be to conduct some testing of materials in the lab and pull a concept together for testing purposes. Once we have proven that the concept is suitable and the whole system works well in the enclosure, I work with the mechanical design team to fully implement it into the product so that it is ready for manufacture.

Sometimes software is required to test the functionality of a hardware design, and I occasionally get to write it myself, which enables me to gain further experience and grow my skillset. While I haven’t done much software design yet, packages, such as “Visual Studios”, are very powerful and flexible, allowing for small test programmes as well as large software packages to be built using the same tools.

At any given moment, the projects I work on can focus on a wide variety of different tasks. On a busy day, I can be working on up to three completely different projects. Whilst that can be challenging at times, since joining Plextek, I have improved my ability to effectively distribute my time between projects. I also enjoy switching between projects and tasks, as it gives me some time to pull away from a problem and come back to it later with a different approach.

An insight from a Graduate Engineer - EdsonAn integral part of being a Graduate Engineer at Plextek is the internal engineering training program. The in-house training scheme incorporates teachings from Plextek’s most experienced members and practical tasks that look to provide training across all areas of the business. So in between project work and other tasks, I try to get on with some of those activities too.

Because the work can be so varied, it is not uncommon for me to come across a piece of technology I am not familiar with. In my mind, it’s all part of the learning curve and I often do my own research when I get home so I can learn a little more about the subject area. An important aspect of being an Electronics Engineer is to continuously progress and learn as technology evolves.

What I enjoy most about being a Graduate Engineer at Plextek is that since joining, every single project I have worked on has been fascinating. The variety of the work, and the challenge of climbing a new learning curve with every new project, makes every day an exciting prospective. A big part of being a graduate engineer is the creative way in which you tackle a hardware, software or mechanical problem. I will often work as part of a team, so we can bounce ideas off each other and come up with inventive ways to solve a problem or design a prototype for example, and although it can be challenging at times, it is always a rewarding experience.


Keep an eye on our careers page for Graduate Career opportunities

Save

By Alan Levy, Lead Consultant, Embedded Systems

Who needs Yocto and what does it do for you?

To begin by teaching granny to suck eggs, in order to understand Yocto you need to understand what a Linux distribution (commonly known as a ‘distro’) is.

The first thing to realise is that unlike MS Windows or MacOS there is no owner and no canonical “version” of Linux but rather a sea of different, often competing, components (primarily but not exclusively applications) that can be glued together to create it.

You can do this for yourself but very few people have the expertise, the time or the motivation to do it. As a result, several organisations such as Ubuntu, Red Hat and Debian have emerged in order to provide pre-canned component collections, which are referred to as Linux distros.

The very first set of components required to build a Linux distro originated from the Free Software Foundation and is known as the GNU1 Operating System. The one component that they were initially unable to develop for themselves as the operating system kernel, so they decided to adopt the Linux kernel which was developed and is still maintained by Linus Torvalds. The combination of GNU components and the Linux kernel is referred to as GNU/ Linux – generally shortened to Linux (much to the chagrin of the Free Software Foundation).

However, you will not find a pure “GNU/ Linux” distro because in addition to GNU/ Linux (and in some cases instead of it), many additional components from other sources are also included in every Linux distro to make it fit for purpose. For convenience, components with a common purpose (e.g. a set of networking utilities or a programming language toolset) are grouped into packages that are installed and managed as a single entity. The package is, therefore, the basic unit of a distro.

Each distro defines a minimum set of packages that must be installed to make it run at all, along with a collection of other packages that may be installed/uninstalled at the discretion of the user. Distro developers define a set of packages that are installed by default on a new system. After installation, the user is free to add further packages or delete some of the pre-installed ones, to fine-tune the system to their precise requirements.

If you want a Linux distro to run on standard PC architecture hardware, you have a huge number of choices including Ubuntu, Red Hat, Debian, Mint, SuSE and many more besides. If you want a Linux distro to run on an embedded hardware platform that is not PC architecture your choices have historically been far more limited. These have generally tended to boil down to whatever the hardware manufacturers chose to offer on a ‘take it or leave it’ basis. Making changes to the Linux distro on an embedded system was thus difficult or impossible for the user and upgrades were provided as and when the manufacturers got around to it, if at all. This remains the case for many devices, particularly IoT devices such as access points, routers, TVs and set-top boxes as well as mobile devices based on Android (which has a bare-bones Linux distro carefully concealed under the hood).

A key part of the problem has been the sheer complexity of creating and maintaining embedded distros. While many organisations – including some very large businesses – exist to do this for PCs, they are only able to do so due to the relatively limited variety of processors and hardware architectures on which their software has to run. In the embedded world, processors abound, hardware platforms are legion and mutually incompatible kernel forks have proliferated, especially on ARM-based hardware. This has historically made it impossible for “conventional” Linux distros to support them. Lately, a lot of effort has been put into eliminating An Introduction to Yocto 1. The name GNU is a recursive acronym that stands for “GNU’s Not Unix”. Who says software developers lack a sense of humour? the multiple kernel forks and merging them back into the mainline Linux kernel. However, this is a very difficult task that has resulted in a lot of angry outbursts from Linus Torvalds and others and it remains a work in progress.

Another big problem for the embedded space is that application packages are written and maintained by many different groups around the world, working independently of (and in many cases in competition with) one another. These teams have all had a clear common interest in supporting Linux on x86 processors but, historically, other processors were much lower down on, or completely off, their radar. In recent years, as embedded Linux has become the OS of choice for various classes of embedded devices, this situation has improved and most packages can now be built for a variety of different processors, particularly ARM architectures which are now competing for head-on with x86 in many different markets.

Another big problem in this area is how to keep track of all of the application packages as they are updated and ensure that they still build and run correctly on every platform to which they have been ported. Doing this properly is an enormous undertaking that strains the resources of even large organisations.

Numerous attempts have been made to address these problems by means of toolsets designed to build embedded distros starting from source code, ‘Buildroot’ being probably the best-known example. These toolsets use cross-compilers running under Linux on PC build hosts to generate the embedded distro code.

Whilst one can debate the pros and cons of these toolsets (Google is your friend here), they have historically tended to suffer from several problems:

  • The toolsets were difficult to configure and use and/or limited in their scope.
  • Toolset developers typically select a particular version of each of the underlying packages and only occasionally update them. This means that security vulnerabilities and bugs may remain in the resulting distros for extended periods even though the package developers have already fixed them.
  • The number of supported packages is often quite limited (e.g. a few hundred for Buildroot)
  • Dependency management is often limited, so using the tools to build a functional distro requires quite a lot of knowledge and care on the part of the user.
  • A user who wishes to customise packages in ways that were not anticipated by the toolset developers needs to directly interact with the individual packages to modify them. This makes some packages considerably easier to adapt than others.
  • Toolsets typically output complete system images but do not make the individual packages available separately. This means that the software update requires the replacement of the entire system image. This can be tens of Megabytes, even if only one byte in one file has changed. This also means that post-installation changes to configuration files can easily be overwritten during the update process.
  • Toolsets tend to have a single monolithic build configuration mechanism (e.g. menuconfig in Buildroot) which defines everything about the image, so re-use of common configurations in different projects is difficult.
  • The toolsets rely on packages already installed on the build host (e.g. make, compilers, linkers etc.) and/or download pre-built cross-compilation tools from the Internet. This leads to a configuration control problem where each build host may be using different versions of tools. The result is that it can sometimes be difficult or even impossible to re-create the same target image on two different build hosts or a single build host at different times, even if none of the source code from which the image is built has changed.
  • For a long time, there was no clear favourite build system and processor board manufacturers chose them seemingly at random. This created problems for OEMs wishing to use those boards in their products because, in the worst case, they would have to use a different toolset for every board.

The OpenEmbedded /Yocto Project addresses these issues:

  • It is based on a custom-designed toolset which supports a sophisticated distro build mechanism based on layered scripts known as “recipes”. Each package has its recipe or set of recipes. Users only need to learn how to write these recipes.
  • Recipe maintenance is delegated to individuals associated with the teams that develop the corresponding packages. This means that Yocto support becomes simply another aspect of package maintenance for the corresponding team and all of the details of building an individual package are taken care of by someone who already understands the package.
  • Each distro has at least one “image” recipe that defines which packages are included in the production image used during product manufacture along with a set of tools for creating deployable images in a variety of formats typically used by product manufacturing processes. It is also possible to extend the toolset to use other image generators if required.
  • Everything is a package (including the Linux kernel) and all packages can be updated after initial deployment using package managers such as ‘RPM’ (which is, of course, itself just another updateable package).
  • Yocto understands how to interact with version control systems such as Git and SVN so that it can fetch repositories from the package developers’ public servers and do fine-grained version control as required.
  • Yocto depends on a small number of tools that are already on the host build system just to get itself up and running and then compiles the other tools it needs from source code. This ensures consistent configuration control of the toolset used to build the packages as well as of the packages themselves. The build tools are themselves managed as packages so that they are re-built by Yocto in the same way as the packages that are part of the distro. This means that their output should always be reproducible, regardless of the initial state of the host build system.
  • Yocto has a very sophisticated dependency management/rebuild scheme that can generally detect automatically when anything changes and rebuild the affected packages.
  • Support from major chip design companies such as Intel and ARM and board manufacturers such as Raspberry Pi means that Yocto is becoming the “obvious” toolset to choose. As a result, board manufacturers that do not support it are at increased risk of being left behind.
  • Individual system developers see Yocto as something that they should have on their CVs2.
  • There are now several thousand packages/ recipes and many Board Support Packages (BSPs) ported to Yocto with more being added all the time.
  • Yocto has licence and source code management mechanisms to help its user’s document package usage and avoid licence infringements.
  • Yocto is designed to support the creation of small packages/images for resource-limited hardware. The name ‘Yocto’ was chosen because it is the naming prefix for the smallest measurement scale (10-24) in the SI system of units.

What is inside Yocto?

Yocto is essentially a set of tools running on a Linux build host that build embedded Linux distros, along with a set of recipes that tell the tools what to do. Given the right recipes, it is capable of building distros for ARM, MIPS, PowerPC, x86 hardware and PC architectures. This covers the vast majority of processors that are capable of running Linux.

A key component is a tool called ‘bitbake’ (note the cookery theme). In essence, bitbake is a task scheduling tool that understands how to determine the order in which the build activities have to happen based on the dependencies within and between the individual packages.

For instance, you have to build the cross compiler first and you have to build libraries before you build the applications that link to them. You can think of it as ‘Make’ on steroids (but don’t strain the analogy because it is very different from, and much more capable, than Make).

Bitbake is a command-line tool written in Python and is extensible by means of Python “classes” that give it an understanding of how to perform common build activities (e.g. downloading package source code from remote Git repositories).

The recipes for the individual packages are Linux shell scripts (sh rather than bash), using a large set of variables and functions provided by bitbake, such as its extension classes, user configuration files and the recipes themselves. They understand how to obtain, configure/adapt and build the source code for their packages.

Package developers (or Yocto support teams associated with them) provide the recipes for building their packages. Distro builders can append their recipes that modify/extend or even replace the base package recipes to customise the package to suit their needs. To this end, recipes are organised into prioritised layers, where higher priority layers (e.g. those written by Yocto users) are processed later than (and hence can modify) the lower priority layers provided by the package developers. By convention, layer names start with the string “meta-“, so the layer for the Raspberry Pi is called meta-raspberry pi, the layer for web browsers is called meta-browser and so on.

A very large subset – although by no means all – of the packages developed for Linux on the PC have now been ported to Yocto and can be built for and deployed on any hardware platform that supports the necessary resources (because of course your hardware is going to need a display in order to use a video player package).

In addition to bitbake, Yocto supports several other useful scripts and tools. Of these, the most interesting is probably Toaster. This adds a web interface to Yocto, providing a means to configure and build distros and to visualise key information about them such as dependencies between packages.

What is Poky?

Poky is a workspace that contains both the basic OpenEmbedded toolset (bitbake, Toaster etc.), the core Linux reference layer (meta-poky) and a BSP layer (meta-yocto-BSP) which adds support for several common hardware platforms. It contains the recipes, configuration files etc. required to build a basic embedded Linux distro. For historical reasons, one further layer is required, which does not conform to the “meta-xxx” naming convention but is called open embedded-core. This contains core metadata that is common to all distros.

Other layers allow you to extend the distro by adding additional applications and board support packages for specific hardware platforms.

It is possible to create your distro without using Poky as the starting point. However, a lot of wheels have to be re-invented to do this. There are a few layers such as meta-angstrom that do this for you. There are even layers that emulate some PC distros such as Debian (called meta-debian as you might expect); this supports the same system configuration and packages that you would get if you installed the corresponding Debian release (Jessie at the time of writing) on a PC.

How easy is Yocto to use?

It all depends. Poky provides a small number of pre-canned image recipes (which define the set of packages that go into the distro) such as coreimage-minimal. Pointing bitbake to one of these will build a distro with no further work on the developer’s part.

The first step beyond this is to write your image recipe to define precisely the set of packages that you want in your distro. This step is fairly easy – you copy one of the predefined image recipes, give it a sensible name and edit it to change the laundry list of packages that it includes.

The next step is to add your packages and/ or to tweak the setups of existing packages (e.g. by adding platform-specific configuration files). This takes a bit more work because you have to understand how to write recipes. Yocto does provide a tool (devtool) for creating new recipes or modifying existing ones but it may not always do what you want and you still have to understand what lives inside a recipe.

By the time you get to this stage, I strongly recommend you get yourself some proper training or at least a mentor who knows Yocto. The Yocto documentation is very useful but, like most Open Source documentation, it is primarily for reference and good explanatory material is thin on the ground. Also, in the end, there’s nothing quite like talking to somebody who already knows how to do it.

Conclusion

You might not think it from what I’ve just said, but in the end, there’s no right or wrong answer as to which toolset one should choose when building embedded Linux distros. Buildroot has its advantages over Yocto and other distro generator toolsets are available. Commercial distro builders such as Ubuntu are also now taking embedded devices seriously. If you want an easy life, and you are free to choose a hardware platform that supports them (such as the RaspberryPi or BeagleBone), you can simply take what they give you. However, for embedded developers who need fine grained control over what goes onto their platform, Yocto is the one to beat.

For myself, having used Yocto, Buildroot and commercial distros, the power and flexibility of Yocto gives it the edge when it comes to creating that finely honed product that will take the market by storm. I commend it to the house.

Read more…