Twelve Ways to Style The Twelve Days

By: Kevin Jones
Senior Consultant, Embedded Systems

6th December 2018

Home » Blog » Page 2

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.

Ai, healthcare, alzheimers, medical imaging

The Future Impact of Artificial Intelligence in Medical Practice

Nigel Whittle - Head of Medical & Healthcare

By: Nigel Whittle
Head of Medical & Healthcare

5th December 2018

Home » Blog » Page 2

We are all aware of the challenges facing healthcare in general, and the NHS in particular. Shortage of funding, increased demands for services, rising costs of innovative drug treatments, the needs of an ageing population. All these issues limit the efficacy of our healthcare service.

There is only so much that can be done with improved efficiency. But what if we could improve diagnosis, so that diseases are detected and treated earlier? In almost every disease, early diagnosis would allow cheaper and more effective treatment, with improved patient outcomes. But of course accuracy is important too, so that scarce resources can be targeted to the right patients.

And that is what makes clinical diagnosis so difficult, requiring skilled and knowledgeable practitioners, whether the local GP or the Harley Street physician. These skills, developed by years of medical training, allow effective diagnosis of disease based not just on clinical information, but also on the patients past history, social background, age and ethnicity.

But at the end of the day, the clinician is simply processing data. And this is the primary strength of Artificial Intelligence.

So which areas are likely to be most impacted by AI?

Medical Imaging

medical imaging, HEALTHCARE , AIUK hospitals generate a staggering 50 petabytes of data every year, of which the vast majority comes from medical imaging. But more than 97% of that data is unused or unanalysed, perhaps because it is unusable, or redundant, or simply swamping the capacities of the clinicians. But AI-powered medical imaging systems can now reliably produce scans that help radiologists identify subtle patterns, helping them treat patients with emergent conditions more quickly. Will this lead to the disappearance of radiology as a clinical profession? Perhaps a more likely outcome is that radiologists will be able to allocate their time more effectively, to work closely with patients with the most serious or complex conditions.

Similarly, cancer diagnosis can be made more accurate through the use of AI systems running scans linked to complex recognition algorithms. When cancer is detected early, treatment is more likely to be successful. But too often, cancers are diagnosed at a late stage when they’re much harder to treat. But AI systems are beginning to take on some of the workload: for example, an algorithm has been developed to diagnose skin cancer more accurately than dermatologists (95% compared with 87%). But in doing so, we must remember that AI systems are not infallible, and the relationship between the patient and the doctor is important so that false negatives are not dismissed out of hand.

In another example, researchers at Imperial College London are working with DeepMind Health to develop AI-based techniques to improve the accuracy of breast cancer screening, using a database of 7,500 anonymised mammograms to develop screening algorithms that can spot early signs of breast cancer whilst reducing over-diagnosis.

But perhaps more interestingly, could there be ways to detect hidden clues in people’s lives that point to cancer? As we generate, collect and share more data than ever before, some of which may be relevant to our health, is there a way to gather this information and help detect diseases such as cancer earlier? And even if it is possible, is it something that we would allow big data systems and corporations to do?

Alzheimer’s Disease

Currently, there’s no easy way to diagnose Alzheimer’s Disease: no single test exists, and brain scans alone can’t determine whether someone has the disease. But alterations in the brain can cause subtle changes in behaviour and sleep patterns years before people start experiencing confusion and memory loss. Artificial intelligence could recognize these changes early and identify patients at risk of developing the most severe forms of the disease, allowing clinicians to target drug and behavioural therapies most effectively.

ai, healthcare, patient doctor

The role of the doctor

It is clear that managing patient data is a core component of the healthcare delivery process, and AI systems will increasingly play an important role in this process. AI is capable of processing larger amounts of data and at a faster rate than human clinicians, is capable of achieving a higher level of accuracy and is not subject to fatigue or burnout.

Which naturally raises a question, what will be the future role of the doctor?

No matter is strengths, AI lacks human sensitivity; clinical applications still require human expertise in the interpretation of data and recommendations. As the role of the physician evolves in the era of AI, the humanity of healthcare delivery will remain critical, and rituals (‘the bedside manner’) that may have been lost in the rush for efficiency savings may emerge with a new-found focus on the patient at the centre of treatment.

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

 

 

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save


If you are interested in talking to Nigel Whittle, our Head of Medical & Healthcare about how Plextek can assist with your project, please email nigel.whittle@plextek.com

We are all aware of the challenges facing healthcare in general, and the NHS in particular. Shortage of funding, increased demands for services, rising costs of innovative drug treatments, the needs of an ageing population. All these issues limit the efficacy of our healthcare service.

There is only so much that can be done with improved efficiency. But what if we could improve diagnosis, so that diseases are detected and treated earlier? In almost every disease, early diagnosis would allow cheaper and more effective treatment, with improved patient outcomes. But of course accuracy is important too, so that scarce resources can be targeted to the right patients.

And that is what makes clinical diagnosis so difficult, requiring skilled and knowledgeable practitioners, whether the local GP or the Harley Street physician. These skills, developed by years of medical training, allow effective diagnosis of disease based not just on clinical information, but also on the patients past history, social background, age and ethnicity.

But at the end of the day, the clinician is simply processing data. And this is the primary strength of Artificial Intelligence.

So which areas are likely to be most impacted by AI?

Medical Imaging

medical imaging, HEALTHCARE , AIUK hospitals generate a staggering 50 petabytes of data every year, of which the vast majority comes from medical imaging. But more than 97% of that data is unused or unanalysed, perhaps because it is unusable, or redundant, or simply swamping the capacities of the clinicians. But AI-powered medical imaging systems can now reliably produce scans that help radiologists identify subtle patterns, helping them treat patients with emergent conditions more quickly. Will this lead to the disappearance of radiology as a clinical profession? Perhaps a more likely outcome is that radiologists will be able to allocate their time more effectively, to work closely with patients with the most serious or complex conditions.

Similarly, cancer diagnosis can be made more accurate through the use of AI systems running scans linked to complex recognition algorithms. When cancer is detected early, treatment is more likely to be successful. But too often, cancers are diagnosed at a late stage when they’re much harder to treat. But AI systems are beginning to take on some of the workload: for example, an algorithm has been developed to diagnose skin cancer more accurately than dermatologists (95% compared with 87%). But in doing so, we must remember that AI systems are not infallible, and the relationship between the patient and the doctor is important so that false negatives are not dismissed out of hand.

In another example, researchers at Imperial College London are working with DeepMind Health to develop AI-based techniques to improve the accuracy of breast cancer screening, using a database of 7,500 anonymised mammograms to develop screening algorithms that can spot early signs of breast cancer whilst reducing over-diagnosis.
But perhaps more interestingly, could there be ways to detect hidden clues in people’s lives that point to cancer? As we generate, collect and share more data than ever before, some of which may be relevant to our health, is there a way to gather this information and help detect diseases such as cancer earlier? And even if it is possible, is it something that we would allow big data systems and corporations to do?

Alzheimer’s Disease

ai, healthcare, patient doctorCurrently, there’s no easy way to diagnose Alzheimer’s Disease: no single test exists, and brain scans alone can’t determine whether someone has the disease. But alterations in the brain can cause subtle changes in behaviour and sleep patterns years before people start experiencing confusion and memory loss. Artificial intelligence could recognize these changes early and identify patients at risk of developing the most severe forms of the disease, allowing clinicians to target drug and behavioural therapies most effectively.

The role of the doctor

It is clear that managing patient data is a core component of the healthcare delivery process, and AI systems will increasingly play an important role in this process. AI is capable of processing larger amounts of data and at a faster rate than human clinicians, is capable of achieving a higher level of accuracy and is not subject to fatigue or burnout.

Which naturally raises a question, what will be the future role of the doctor?

No matter is strengths, AI lacks human sensitivity; clinical applications still require human expertise in the interpretation of data and recommendations. As the role of the physician evolves in the era of AI, the humanity of healthcare delivery will remain critical, and rituals (‘the bedside manner’) that may have been lost in the rush for efficiency savings may emerge with a new-found focus on the patient at the centre of treatment.

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save


If you are interested in talking to Nigel Whittle, our Head of Medical & Healthcare about how Plextek can assist with your project, please email nigel.whittle@plextek.com

Distance Finding in Mobile Autonomous Systems

Damien Clarke - Senior Consultant, Data Exploitation

By: Damien Clarke
Lead Consultant, Data Exploitation

7th November 2018

Home » Blog » Page 2

You might already be familiar with FiveAI, a driverless car startup based in Cambridge, and their recent work making headlines but for those that aren’t, allow me to bring you up to speed. FiveAI’s vision is to bring a shared driverless taxi service to London by next year and they have already started gathering data of London’s streets with their iconic blue branded cars.

A key component in the development of mobile autonomous systems is the ability to produce a 3D map of the local environment which can be used for route planning and collision avoidance (e.g. sense and avoid). There are various sensors which can be used to achieve this and each one has specific advantages and disadvantages.

Stereo Vision

The first approach (and one that many animals, including humans, use) is to combine images from a pair of cameras placed at slightly different positions to enable depth perception. This is achieved by determining the horizontal disparity between the same object in both cameras. Nearby objects produce a large disparity in position between the two cameras whereas far objects have a small disparity.

This technique can also be used with a single camera if it is moving as the video is effectively a series of images taken at different positions. This is known as Structure from Motion and is commonly used with airborne cameras, such as those used on small consumer drones.

The primary advantage of this technique is that cameras are small and inexpensive. At close range, good depth resolution can be achieved and fused with the image content itself to produce a 3D colour image. A large number of cameras with overlapping fields of view can potentially produce a 360° panoramic 3D map of the environment around a vehicle.

The main limitation of this approach is that it will only work when suitable images can be produced and therefore adverse environmental conditions (e.g. dust, fog, rain, etc.) will prevent the production of a 3D map. Operation at night time is potentially possible with illumination or the use of thermal imagers rather than standard cameras. Poor camera dynamic range can also be a problem as bright lights (e.g. headlights or the sun) will cause glare. In addition, the processing required to locate features within both images and match them is complex and adds computational burden when using this technique to produce a 3D map.

Lidar

An alternative optical approach to stereo vision is a scanning laser range finder, also known as lidar. This approach uses a laser to send a pulse towards a surface and a sensor to record how long it takes for the reflection to return. The measurement of the time of flight can then be used to determine the range. To produce a 3D map of a scene, this beam must then be scanned in azimuth and elevation. To reduce the amount of scanning, some lidar sensors use multiple beams at different elevation angles and then only scan in azimuth.

Lidar has very good depth resolution and due to the narrow beam can also produce very good lateral resolution. In general, the technology for emitting and sensing light is entirely solid state, however, at present many lidar system still use the mechanical method to scan the beam across the scene. Fully solid state systems would be small and cheap, though this promise has not yet been fully realised in commercial lidar systems which are often large and expensive.

As simple lidar sensors only record the time for the first reflection to return, a drawback of some lidar systems is that they will only detect the nearest object in a specific direction. This is problematic when the environment is dusty or foggy as the first reflection may not be from a solid object and the resulting 3D map will be degraded. More sophisticated (and costly) systems measure the entire reflection over time which then allows a full range profile to be measured through the obscurant. Direct sunlight can also produce problems as the large level of background illumination can make it difficult to detect weak reflections. Similarly, if a surface has low reflectivity (i.e. it is black) then it may not be detected by the lidar. This can be a problem for autonomous vehicles as black car surfaces will only be detected at a closer range than more reflective vehicles.

Radar

Radar is similar to lidar but uses microwaves rather than light (typically 25 or 77 GHz). Lidar was in fact inspired by radar (e.g. laser radar) and only became possible once lasers were invented. The exact mechanism by which the distance is measured varies slightly between different radar systems; however, the concept is the same. A signal is emitted, the length of time it takes for a reflection to return is measured and this is then converted into a range profile. While panoramic mechanically scanned radars are available, it is more common to use an antenna array and calculate the angle of arrival of a reflection by the difference in signal across the array.

One advantage of radar is the ability to measure speed directly via Doppler shift without complex processing. Therefore, objects moving relative to a mainly static scene are generally easy to detect. Poor environmental conditions (e.g. fog, rain and snow) have little impact on the performance of the radar which provides a useful all-weather capability for autonomous vehicles. Single chip radars with integrated processing capabilities are also available for use as small and inexpensive sensor solutions.

A disadvantage of radar is the limited lateral resolution. While the depth resolution can be good, the angular resolution is significantly lower than for optical sensors. However, this is partially mitigated if an object can be uniquely separated from other objects and clutter by its range or velocity value.

Ultrasonic

The final sensor used for range finding on autonomous vehicles is an ultrasonic sensor which emits high-frequency sounds beyond the range of human hearing. Bats are, of course, well-known users of this approach. Ultrasonic sensors are very similar to lidar sensors; however, as the speed of sound in air is vastly slower than the speed of light it is much easier to measure the time for a reflection to return from a surface.

Ultrasonic sensors work well regardless of light level or environmental conditions and are very small and inexpensive. This makes the technology ideal for ultra-short range collision avoidance sensors on small or slow moving vehicles which can be placed in many locations to provide wide area coverage.

The main disadvantage of ultrasonic sensors is their extremely short range as they can only produce distance measurements for surfaces up to a few metres away. For this reason, it is also uncommon for an ultrasonic sensor to be used to explicitly form a 3D map.

Data Fusion

In practice, to achieve a robust and effective sensor solution for autonomous vehicles it is necessary to combine different sensors and perform sensor fusion. As yet there is no standard sensor suite and research is still ongoing to determine the optimum combination with an acceptable performance across all weather conditions.

Furthermore, as an example, Tesla’s latest models that are claimed to be suitable for autonomous operation have eight cameras (with varying fields of view) and twelve ultrasonic sensors to enable panoramic sensing while a single forward-looking radar measures range and speed of objects up to 160m away.

The combination of cameras with radar is a common sensor choice as it provides good lateral and range resolution under various weather conditions for a relatively low price. It remains to be seen whether or not it is sufficient for safe autonomous operation without the addition of lidar.

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

You might already be familiar with FiveAI, a driverless car startup based in Cambridge, and their recent work making headlines but for those that aren’t, allow me to bring you up to speed. FiveAI’s vision is to bring a shared driverless taxi service to London by next year and they have already started gathering data of London’s streets with their iconic blue branded cars.

A key component in the development of mobile autonomous systems is the ability to produce a 3D map of the local environment which can be used for route planning and collision avoidance (e.g. sense and avoid). There are various sensors which can be used to achieve this and each one has specific advantages and disadvantages.

Stereo Vision

The first approach (and one that many animals, including humans, use) is to combine images from a pair of cameras placed at slightly different positions to enable depth perception. This is achieved by determining the horizontal disparity between the same object in both cameras. Nearby objects produce a large disparity in position between the two cameras whereas far objects have a small disparity.

This technique can also be used with a single camera if it is moving as the video is effectively a series of images taken at different positions. This is known as Structure from Motion and is commonly used with airborne cameras, such as those used on small consumer drones.

The primary advantage of this technique is that cameras are small and inexpensive. At close range, good depth resolution can be achieved and fused with the image content itself to produce a 3D colour image. A large number of cameras with overlapping fields of view can potentially produce a 360° panoramic 3D map of the environment around a vehicle.

The main limitation of this approach is that it will only work when suitable images can be produced and therefore adverse environmental conditions (e.g. dust, fog, rain, etc.) will prevent the production of a 3D map. Operation at night time is potentially possible with illumination or the use of thermal imagers rather than standard cameras. Poor camera dynamic range can also be a problem as bright lights (e.g. headlights or the sun) will cause glare. In addition, the processing required to locate features within both images and match them is complex and adds computational burden when using this technique to produce a 3D map.

Lidar

An alternative optical approach to stereo vision is a scanning laser range finder, also known as lidar. This approach uses a laser to send a pulse towards a surface and a sensor to record how long it takes for the reflection to return. The measurement of the time of flight can then be used to determine the range. To produce a 3D map of a scene, this beam must then be scanned in azimuth and elevation. To reduce the amount of scanning, some lidar sensors use multiple beams at different elevation angles and then only scan in azimuth.

Lidar has very good depth resolution and due to the narrow beam can also produce very good lateral resolution. In general, the technology for emitting and sensing light is entirely solid state, however, at present many lidar system still use the mechanical method to scan the beam across the scene. Fully solid state systems would be small and cheap, though this promise has not yet been fully realised in commercial lidar systems which are often large and expensive.

As simple lidar sensors only record the time for the first reflection to return, a drawback of some lidar systems is that they will only detect the nearest object in a specific direction. This is problematic when the environment is dusty or foggy as the first reflection may not be from a solid object and the resulting 3D map will be degraded. More sophisticated (and costly) systems measure the entire reflection over time which then allows a full range profile to be measured through the obscurant. Direct sunlight can also produce problems as the large level of background illumination can make it difficult to detect weak reflections. Similarly, if a surface has low reflectivity (i.e. it is black) then it may not be detected by the lidar. This can be a problem for autonomous vehicles as black car surfaces will only be detected at a closer range than more reflective vehicles.

Radar

Radar is similar to lidar but uses microwaves rather than light (typically 25 or 77 GHz). Lidar was in fact inspired by radar (e.g. laser radar) and only became possible once lasers were invented. The exact mechanism by which the distance is measured varies slightly between different radar systems; however, the concept is the same. A signal is emitted, the length of time it takes for a reflection to return is measured and this is then converted into a range profile. While panoramic mechanically scanned radars are available, it is more common to use an antenna array and calculate the angle of arrival of a reflection by the difference in signal across the array.

One advantage of radar is the ability to measure speed directly via Doppler shift without complex processing. Therefore, objects moving relative to a mainly static scene are generally easy to detect. Poor environmental conditions (e.g. fog, rain and snow) have little impact on the performance of the radar which provides a useful all-weather capability for autonomous vehicles. Single chip radars with integrated processing capabilities are also available for use as small and inexpensive sensor solutions.

A disadvantage of radar is the limited lateral resolution. While the depth resolution can be good, the angular resolution is significantly lower than for optical sensors. However, this is partially mitigated if an object can be uniquely separated from other objects and clutter by its range or velocity value.

Ultrasonic

The final sensor used for range finding on autonomous vehicles is an ultrasonic sensor which emits high-frequency sounds beyond the range of human hearing. Bats are, of course, well-known users of this approach. Ultrasonic sensors are very similar to lidar sensors; however, as the speed of sound in air is vastly slower than the speed of light it is much easier to measure the time for a reflection to return from a surface.

Ultrasonic sensors work well regardless of light level or environmental conditions and are very small and inexpensive. This makes the technology ideal for ultra-short range collision avoidance sensors on small or slow moving vehicles which can be placed in many locations to provide wide area coverage.

The main disadvantage of ultrasonic sensors is their extremely short range as they can only produce distance measurements for surfaces up to a few metres away. For this reason, it is also uncommon for an ultrasonic sensor to be used to explicitly form a 3D map.

Data Fusion

In practice, to achieve a robust and effective sensor solution for autonomous vehicles it is necessary to combine different sensors and perform sensor fusion. As yet there is no standard sensor suite and research is still ongoing to determine the optimum combination with an acceptable performance across all weather conditions.

Furthermore, as an example, Tesla’s latest models that are claimed to be suitable for autonomous operation have eight cameras (with varying fields of view) and twelve ultrasonic sensors to enable panoramic sensing while a single forward-looking radar measures range and speed of objects up to 160m away.

The combination of cameras with radar is a common sensor choice as it provides good lateral and range resolution under various weather conditions for a relatively low price. It remains to be seen whether or not it is sufficient for safe autonomous operation without the addition of lidar.

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

A Look Back in Events: Engineering Design Show 2018

A Look Back in Events: Engineering Design Show 2018

By: Ehsan Abedi
Product Designer

24th October 2018

Home » Blog » Page 2

The Engineering Design Show (EDS) exhibition was packed with over 220 exhibitors offering different areas of expertise and services. Being Plextek’s first time attending the show as exhibitors we were keen to show our creative and technical capabilities, observe how the industry is changing and exemplify how we can help others adapt to these changes.

Power of being genuine

As designers and engineers at Plextek, we are rarely involved in selling our capabilities but this proved to be of our benefit at the engineering design show. A lot of industry events are filled with slick salesmen who can sometimes intimidate or detract attention of designers, engineers and others looking to solve their own problems. As individuals untrained in selling, I found that by simply being our natural selves we felt that people at the show could chat to us genuinely and naturally on a range of matters.

We had great pleasure in meeting many like-minded engineers and designers which we hope to collaborate with. And they themselves faced a massive variety of problems, in everything from developing new wind farm technology to difficulties in intricate medical device development.

Breadth and depth in design & development

Plextek’s capabilities across the whole design and development process and history of working in a diverse range of sectors mean that we were able to interact with a lot of people at the show and think which experts within Plextek would be able to help them overcome their specific issues.


So how is the design engineering industry changing?

With a diverse range of exhibitors, workshops and conferences at the Engineering Design Show, it was possible to make observations on how the industry is changing.

Rate of change

Many people I met at EDS thought that the current rate of technological change is beginning to exceed our ability to adapt. This signifies how important it is for companies to implement a collaborative approach and ensure they are able to evolve and adapt to these rapid changes.

Automation

The technology on show at EDS demonstrated some of the major advances being made in automation. There was a range of mechatronic devices on show and it is easy to see how these technologies could be implemented within robotics and for the automation of more production processes.

Newer and more effective rapid prototyping technologies were also on show, which are continually making it cheaper and easier to rapidly design and test ideas to help inform the usability of the final products.

User Centric Design

Whether it is a small component being optimised for assembly or a final product optimised for comfort and usability, user centred design is clearly becoming more prevalent.

Designers in close contact to users are likely to build a sense of empathy for their users and hence develop more pleasing products.

The implementation of user centred design methods means products: reduce misuse, are safer to use and meet a user’s expectations and requirements. This in turn can lead to increased product sales and a reduction in the costs incurred by customer services.

Source: http://www.engineering-design-show.co.uk/gallery/

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

The Engineering Design Show (EDS) exhibition was packed with over 220 exhibitors offering different areas of expertise and services. Being Plextek’s first time attending the show as exhibitors we were keen to show our creative and technical capabilities, observe how the industry is changing and exemplify how we can help others adapt to these changes.

Power of being genuine

As designers and engineers at Plextek, we are rarely involved in selling our capabilities but this proved to be of our benefit at the engineering design show. A lot of industry events are filled with slick salesmen who can sometimes intimidate or detract attention of designers, engineers and others looking to solve their own problems. As individuals untrained in selling, I found that by simply being our natural selves we felt that people at the show could chat to us genuinely and naturally on a range of matters.

We had great pleasure in meeting many like-minded engineers and designers which we hope to collaborate with. And they themselves faced a massive variety of problems, in everything from developing new wind farm technology to difficulties in intricate medical device development.

Breadth and depth in design & development

Plextek’s capabilities across the whole design and development process and history of working in a diverse range of sectors mean that we were able to interact with a lot of people at the show and think which experts within Plextek would be able to help them overcome their specific issues.


So how is the design engineering industry changing?

With a diverse range of exhibitors, workshops and conferences at the Engineering Design Show, it was possible to make observations on how the industry is changing.

Rate of change

Many people I met at EDS thought that the current rate of technological change is beginning to exceed our ability to adapt. This signifies how important it is for companies to implement a collaborative approach and ensure they are able to evolve and adapt to these rapid changes.

Automation

The technology on show at EDS demonstrated some of the major advances being made in automation. There was a range of mechatronic devices on show and it is easy to see how these technologies could be implemented within robotics and for the automation of more production processes.

Newer and more effective rapid prototyping technologies were also on show, which are continually making it cheaper and easier to rapidly design and test ideas to help inform the usability of the final products.

User Centric Design

Whether it is a small component being optimised for assembly or a final product optimised for comfort and usability, user centred design is clearly becoming more prevalent.

Designers in close contact to users are likely to build a sense of empathy for their users and hence develop more pleasing products.

The implementation of user centred design methods means products: reduce misuse, are safer to use and meet a user’s expectations and requirements. This in turn can lead to increased product sales and a reduction in the costs incurred by customer services.

Source: http://www.engineering-design-show.co.uk/gallery/

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Can Technology Ever Beat Face to Face Interactions?

Interview: Agnieszka Krysztul
Events Manager

17th October 2018

Home » Blog » Page 2

This week sees the last large event we are exhibiting at for 2018.  It’s been busy: The Disruption SummitDVD and Mission Critical Technologieswere amongst the highlights of a busy season.

As a technology company, we often rely on technology too much to support our human to human interactions.   We sat down today and chatted to Agnieszka, our Event Manager to discuss whether there really is still a place for business events in today’s modern tech-driven world:

Are business events still popular?

These days we have such a high-tech lifestyle. We are working in highly competitive and fast changing environments dominated by digital technology but what hasn’t changed is that people still buy from people. Like any event, business events are organized for a strong purpose. They bring people together and give an opportunity to talk to different individuals, and meet old contacts. They are also great place to keep up with latest trends and technologies, to learn about and discover new opportunities.

Why do these business events inspire business growth?

We all attend various events in life (whether it’s a social event or for business) and we go there with the purpose to meet contacts who are all there for similar purpose. They brighten up our daily routine in life and give us a fresh view on what’s happening in our interest group.  They often strengthen our relationships, broaden our horizons and bring fresh ideas. Ultimately, it’s easier to understand a person and determine whether you want to work with them when you can see the whites of their eyes!

Whenever I go to one of these events I feel I have gained something positive. I am inspired by talking to different people and by finding out what they have been up to recently. Being in a different environment with different groups of people can give you  fresh ideas and new prospects. They bring value to both the business development team and to all employees who attend.

Is there really an employee benefit to attending events?

Yes. When I see my team getting involved in attending an event, they get engaged with different colleagues in the company that they don’t regularly speak to. It is good for team building inside the organization but also when they come back from the event, the value and the new opportunities get shared across the business. It involves all of us and helps the business work together.

One of our biggest successes for the events team is increasing our company’s reputation in the marketplace, not only as a trusted and valuable partner but also as a growing & successful business. Events are a powerful way to deliver that message.

What’s next for events in the future?

As the business world works more globally, there may be more technology involved in communicating across distance and we work with international clients on that basis. But I haven’t seen that detract from events where you can make great initial contacts. People are still prepared and seem to prefer flying the distances to meet with people face to face and make more valuable human connections in order to accelerate business.

This week we will be showing our product design and concept generation skills at the Engineering Design Show where our Product Designers, who often get stuck back at the studio, have a chance to meet with our customers and prospects on an open platform.  These are real people working on real, exciting projects, and the best way to understand what they do will always be to see them in real life.

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save

Save