Obfuscated Hello World Program


                    #include<stdio.h>
                    #include<math.h>
                    #include<stdlib.h>
                    #define w(h)copysign(1,h)
                    #define R return
                    #define P pow
                    #define T typedef
                    T int D;T float I;struct _{I a;I b;};T struct _ F;D
                    /*                               Hello World Abomination in C by Finian Blackett: https://finblackett.com/hello-world                               */

                                                      f(D p){                                               if(p                                          <1){R
                                                     1;}else{R                                              p*f(p-                                      1);}}I u
                                                    (D s){I z=                                           0;for(D k=0                                   ;k<s;k++){
                                                    z+=P(-1,k)                                          *(f(6*k))/(                                    (P(f(k),3))
                                                    *(f(3*k)))                                          *(13591409                                      +545140134*
                                                     k)/(P/**/                                         (640320,(3                                        *k)));}R P(
                            (z*P(10005,.5                           )/(96715l      *44160)            ),-1);}I e(      D n){I j=2         ;for(D i=2      ;i<n;i++){
                         j+=1/f(i);}R j;}I r        (I h,I g){      if(h>1||h  <-1){R-r(1/h,g         )+w(h)*g/2       ;}if(h==1||       h==-1){R g/       4;}I j=0;;
                       for(D z=0;z<100;z++){j       +=P(-1,(I)      z)*(P(h,(2*(I)z+1))/(2*(I)       z+1));}R j          ;}F s(I n,I     g,I a[]){         if(n<-g/2||
                      n>g/2){F j;if(n<0){j=s(n      +g,g,a);}       else{j=s(n-g,g,a);}I x=j.a;      I y=j.b;F            v={-x,-y};R   v;}I x=1,y          =0;for(D i
                      =0;i<50;i++){I d=w(n);I       u=x,v=y;x=      u-(d*P(2,-i)*v);y=(d*P(2,-i      )*u)+v;n=n            -(d*a[i]);}I k=/****/            .607252935
                      ;F V={x*k       ,y*k};R V     ;}I h(I a,      I b){I u,x;D v,  y;u=frexp(a    ,&v); *&x=              frexp(b,&y);I h=u*x             ;I j=v+y;R
                      ldexp(h,j);}D    t(D s){D      k=0;while      (s>0){k++;        s>>=1;}R k    ;}D j(D e,                D h){if(e<10||h<              10){R e*h;
                      }D y=(t(e)>t(h)?t(e):         t(h))/2;D       l=P(2,y);D         a=e/l;D b    =e%l;D c=h                 /l;D d=h%l;D u               =j(a,c);D
                       v=j(b,d);D z=j(a+b,c+d       )-u-v;R u*      P(2,(y*2))        +(z*l)+v;}    I m(I a,I                   b){double x,                y,u,v;x=/*
                        */modf(a,&y);u=modf(b,      &v);R h(x,      u)+h(y,u)+        h(x,v)+j(y    ,v);}F o(F                   a,F b){I x=                a.a,y=a.b;
                          I u=b.a,v=b.b;F r={m(     x,u)-m(y,v      ),m(x,v)+m        (y,u)};R r     ;}F k(F p,                I g,I b,I a[])               {I q=P(b,p
                     .a);F v=     s(p.b,g,a);F      r={v.a*q,v      .b*q};R r;        }void/***/     dark_magic              (I*c,size_t f,D l             ){I g=u(5);
                     I b=e(30)        ;I a[50];     for(D i=0;      i<50;i++){        a[i]=r(P(2     ,-i),g);}/*            */for(D i=0;i<l;i++            ){I s[f/2]
                     ;for(D j=0;j  <f;j+=2){F z     ={c[j],c[j      +1]};F x={        0,2};F v={      g*j*i/f,0}           ;s[j/2]=o(z,k(o(v,x),          g,b,a)).a;}
                     I O=0;for(D j=0;j<f/2;j++)     {O+=s[j];}      putchar(0+        round(O/(f       /2)));}}D          main(){I c[  ]={1129,0.,        23.497200,
                      22.2116,-179.723000000,-      157.50370,      7.80620000        ,20.79880,       4.2757000,-       116.59630,-    3.9410000,-      17.579200,
                       51.585,-6.9775,51.585,       6.977500,-      3.9410000,        17.579200,        4.27570000,    116.5963000,      7.8062000,-    20.79880,-
                          179.723,157.5037          ,23.4972,-      22.2116};D         l=13;/**/         dark_magic(   c,sizeof(c)        /sizeof(c[   0]),l);}//
                

The above program is an obfuscated C program to print "Hello, World!" exactly when compiled. The program uses a host of tricks in order to obfuscate the mechanism not through syntax or use of C coding constructs, but by manner of mathematical trickery. For people who do not have easy access to a C compiler, you can try running the above code on REPL.it, an online IDE.

Basic Overview

The hello world program operates by means of the inverse discrete Fourier transform. The Fourier transform is a method of taking a continuous function of time and turning it into a function of frequency. This is similar to the process of taking an audio signal, and converting it back into the individual notes that add up to make it, in which case the notes are specific frequencies that there can be more or less of in the signal. The inverse Fourier transform reverses this process, taking a function of frequencies and turning it back into a function of time.

For this program, we use the discrete Fourier transform (DFT) since it operates on a set of finite data points instead of a continuous function. This is how the actual audio signal reconstructions work, since it's impossible to actually get a reading for every infinitesimal point in time. Instead, we take single readings at some interval and then plug them into the DFT to get a series of single frequencies, again at some interval. We specifically use the inverse discrete Fourier transform (IDFT) to decode the hello world text from a set of complex number coefficients representing frequencies, which we get by taking the DFT of the ASCII values of "Hello, World!"

The way the program converts numbers, like in the output of the IDFT, to letters, like in the text "Hello, World!" is through the ASCII encoding, which maps numbers in the range 0 to 255 to letters, numbers and symbols that you type on your keyboard and that appear on your screen. Specifically, the program takes the inverse discrete Fourier transform, which ends up being a function, and takes the value of that function at every point from 0-12, then it turns those numbers into characters, and prints them to the screen. These end up being the text you see.

Computing the Coefficients

The DFT is a function defined as below, where \(x_n\) is a series of \(N\) input numbers, and \(X_k\) is the resulting output. $$\begin{align} X_k &= \sum_{n=0}^{N-1} x_n\cdot e^{-\frac {i 2\pi}{N}kn}\\ &= \sum_{n=0}^{N-1} x_n\cdot [\cos(2 \pi k n / N) - i\cdot \sin(2 \pi k n / N)] \end{align}$$ This means that it consists of a summation of complex numbers for each value in \(X_k\). While the mechanics of this function are beyond the scope of this explanation, Wikipedia has a solid explanation of why it works, and 3Blue1Brown has an absolutely phenomenal visualization of the continuous Fourier Transform, which mostly applies to the discrete variant (his other videos are also top-notch).

Fortunately for us, computing a DFT is such a common task in math, science, and engineering that it is provided by default in most major mathematical libraries for any programming language. In my case, I used NumPy, a great Python library for all manners of scientific and mathematical computing.

Here is the code to generate the array we need (FFT is the Fast Fourier Transform, an optimized DFT):


            from numpy.fft import fft
            from pprint import pformat
            text = b"Hello, World!"
            truncation = 6
            array = fft(list(text))
            array = [(x.real, x.imag) for x in array]
            array = [item for sublist in array for item in sublist]
            array = [round(x, truncation) for x in array]
            print("float c[] = %s;\nint l = %s;" % (pformat(array)
                        .replace('[', '{')
                        .replace(']', '}'),
                        len(text)))
        

Note the fact that it outputs complex numbers, which we turn into a pair of real numbers by taking the real and imaginary parts and flattening them out into a single-dimensional array, and then truncate these numbers. This is because by default we do not need nearly the amount of precision given to us by NumPy to reproduce 13 characters of text.

Also note that we output the length of the text, which is necessary because the DFT's values only specify the shape of the output curve, but not the length we must cut it to to avoid garbage output.

The Obfuscation Part 1: Complex Number Multiplication

Now that we have computed the values for our array, how do we reconstruct them? Well, looking at the IDFT's definition: $$x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k\cdot e^{i 2 \pi k n / N}$$ We can see that it follows a similar format to the DFT. The points of note here are the fact that the constant \(e\) is exponentiated to a complex power, and that the division by \(N\), the total number of input values, is moved. Every function used in this equation are provided in the C standard library header complex.h and math.h, but we won't be using them in favor of our own implementations, to add obscurity.

The multiplication of two complex numbers is a simple application of the middle-school level FOIL, resulting in the formula: $$ (a + b i) \cdot (c + d i) = (a c - b d) + (a d + b c) i $$ This ends up implemented in the C code (after preprocessing) as the function:


                complex o(complex a, complex b) {
                    float x = a.a, y = a.b;
                    float u = b.a, v = b.b;

                    complex r = {m(x, u) - m(y, v), m(x, v) + m(y, u)};
                    return r;
                }
            

However, one thing to notice in this function is the use of one of our defined methods m() which multiplies two floats, the specifics of which will be discussed later. Thus, complex number multiplication is implemented.

The Obfuscation Part 2: Complex Number Exponentiation

The next important thing to implement is a function to raise the constant \(e\) to a complex power. This is an operation which was shown to have a simple equivalence: $$ e^{a + b i} = e^a \cdot (cos(b) + i \cdot sin(b)) $$ In the program, this is implemented in the function k. We use the builtin math.h library's pow() function for the left half, but we use our own implementation of sine and cosine for the right half, which leads perfectly into the next section.

The Obfuscation Part 3: Trigonometric Functions

The C programming provides a very fast and accurate implementation of all the standard trigonometric functions inside the standard library, including the ones we need, sine and cosine. However, for obfuscation's sake, we re-implement these using the CORDIC algorithm, an algorithm for computing trigonometric functions designed to use extremely basic primitives, meaning it can even be implemented on a microprocessor with no multiplier, using just addition, subtraction, bitshifts, and a lookup into a pre-computed table of arctangent values.

The reasoning behind this algorithm is again beyond the scope of this explanation, but you can again look on Wikipedia for more information.

Here's a simple implemenation of the CORDIC algorithm in Python:


            from math import copysign, pi

            def cordics_algorithm(beta):
                # Get beta into the range it should be.
                if beta < -pi / 2 or beta > pi / 2:
                    if beta < 0:
                        x, y = cordics_algorithm(beta + pi)
                    else:
                        x, y = cordics_algorithm(beta - pi)
                    return -x, -y

                x, y = 1, 0

                # Run our step
                for i in range(200):
                    # sign() function workaround
                    d = copysign(1.0, beta)

                    u, v = x, y

                    x = u - (d * (2.0 ** (-i)) * v)
                    y = (d * (2.0 ** (-i)) * u) + v

                    beta = beta - (d * atan_array[i])

                # Pre-calculated K for 200 iterations
                return 0.6072529350088814 * x, 0.6072529350088814 * y
        

In the C code, this is implemented in the function s()

The first 6 lines of the program are used to make sure the input is in the range \([-\frac{\pi}{2}, \frac{\pi}{2}]\), because the CORDIC algorithm does not function properly outside of this range.

The rest of the algorithm uses the array of arctangent values atan_array, which can be computed with the one-liner:


                from math import atan
                atan_array = [atan(2 ** -n) for n in range(200)]
            

In our case we won't be using a builtin arctangent function, we can instead use the taylor series: $$ atan(x) = \sum_{n = 1}^{\infty}\ (-1)^n \cdot \frac{x^{2 n + 1}}{2 n + 1} $$ over the interval \([-1, 1]\). For values outside this range, we can use the identity $$ atan(x) = sign(x) \cdot \frac{\pi}{2} - atan(\frac{1}{x})$$ This is implemented in the function r() in the obfuscated code, and it is used to provide the arctangent array.

The Obfuscation Part 4: Mathematical Constants

In order to further obfuscate the program, the definition series for the constant \(e\) is used: $$ e = \sum_{n = 0}^{\infty} \frac{1}{n!} $$ And a very quickly converging series for \(\pi\) is used: $$ \frac{426880\sqrt{10005}}{\pi} = \sum^\infty_{k=0} \frac{(6k)! (545140134k + 13591409)} {(3k)!(k!)^3 \left(-262537412640768000\right)^{k}} $$ The \(e\) series is implemented in the function e(), and the \(\pi\) summation is in the function u(). The \(\pi\) summation converges quickly enough that only 5 iterations is necessary to give us a value equal to the constants provided in the standard library.

Our code names these variables g for \(\pi\), and b for \(e\)

The Obfuscation Part 5: Floating Point Multiplication

This section will be quick because of the simplicity of the algorithms involved.

In our code, we define the function m which takes two floats and multiplies them. Internally, this is implemented by splitting the two floats into their integer and fractional components and FOILing them out, using the function h to multiply fractions and the function j to multiply the integers together.

We also define the function j, which implements a recursive multiplication algorithm called Karatsuba Multiplication, over base 2.

Finally, we define the function h, which multiplies two floats by breaking them into a fraction \(m\) and an exponent \(exp\) such that \(m \cdot 2^{exp}\) equals the original float. Multiplication is then performed by multiplying the fractions and adding the exponents.

Conclusion

Combining all this math results in the function dark_magic(), which I think is a very apt name if you don't know the underlying principles. The function also takes our previous \(\pi\), \(e\), and \(atan\) functions and computes the constants we need for the IDFT, passing them into the functions which use them as arguments. The end result is our beauty:


                #include<stdio.h>
                #include<math.h>
                #include<stdlib.h>
                #define w(h)copysign(1,h)
                #define R return
                #define P pow
                #define T typedef
                T int D;T float I;struct _{I a;I b;};T struct _ F;D
                /*                               Hello World Abomination in C by Finian Blackett: https://finblackett.com/hello-world                               */

                                                  f(D p){                                               if(p                                          <1){R
                                                 1;}else{R                                              p*f(p-                                      1);}}I u
                                                (D s){I z=                                           0;for(D k=0                                   ;k<s;k++){
                                                z+=P(-1,k)                                          *(f(6*k))/(                                    (P(f(k),3))
                                                *(f(3*k)))                                          *(13591409                                      +545140134*
                                                 k)/(P/**/                                         (640320,(3                                        *k)));}R P(
                        (z*P(10005,.5                           )/(96715l      *44160)            ),-1);}I e(      D n){I j=2         ;for(D i=2      ;i<n;i++){
                     j+=1/f(i);}R j;}I r        (I h,I g){      if(h>1||h  <-1){R-r(1/h,g         )+w(h)*g/2       ;}if(h==1||       h==-1){R g/       4;}I j=0;;
                   for(D z=0;z<100;z++){j       +=P(-1,(I)      z)*(P(h,(2*(I)z+1))/(2*(I)       z+1));}R j          ;}F s(I n,I     g,I a[]){         if(n<-g/2||
                  n>g/2){F j;if(n<0){j=s(n      +g,g,a);}       else{j=s(n-g,g,a);}I x=j.a;      I y=j.b;F            v={-x,-y};R   v;}I x=1,y          =0;for(D i
                  =0;i<50;i++){I d=w(n);I       u=x,v=y;x=      u-(d*P(2,-i)*v);y=(d*P(2,-i      )*u)+v;n=n            -(d*a[i]);}I k=/****/            .607252935
                  ;F V={x*k       ,y*k};R V     ;}I h(I a,      I b){I u,x;D v,  y;u=frexp(a    ,&v); *&x=              frexp(b,&y);I h=u*x             ;I j=v+y;R
                  ldexp(h,j);}D    t(D s){D      k=0;while      (s>0){k++;        s>>=1;}R k    ;}D j(D e,                D h){if(e<10||h<              10){R e*h;
                  }D y=(t(e)>t(h)?t(e):         t(h))/2;D       l=P(2,y);D         a=e/l;D b    =e%l;D c=h                 /l;D d=h%l;D u               =j(a,c);D
                   v=j(b,d);D z=j(a+b,c+d       )-u-v;R u*      P(2,(y*2))        +(z*l)+v;}    I m(I a,I                   b){double x,                y,u,v;x=/*
                    */modf(a,&y);u=modf(b,      &v);R h(x,      u)+h(y,u)+        h(x,v)+j(y    ,v);}F o(F                   a,F b){I x=                a.a,y=a.b;
                      I u=b.a,v=b.b;F r={m(     x,u)-m(y,v      ),m(x,v)+m        (y,u)};R r     ;}F k(F p,                I g,I b,I a[])               {I q=P(b,p
                 .a);F v=     s(p.b,g,a);F      r={v.a*q,v      .b*q};R r;        }void/***/     dark_magic              (I*c,size_t f,D l             ){I g=u(5);
                 I b=e(30)        ;I a[50];     for(D i=0;      i<50;i++){        a[i]=r(P(2     ,-i),g);}/*            */for(D i=0;i<l;i++            ){I s[f/2]
                 ;for(D j=0;j  <f;j+=2){F z     ={c[j],c[j      +1]};F x={        0,2};F v={      g*j*i/f,0}           ;s[j/2]=o(z,k(o(v,x),          g,b,a)).a;}
                 I O=0;for(D j=0;j<f/2;j++)     {O+=s[j];}      putchar(0+        round(O/(f       /2)));}}D          main(){I c[  ]={1129,0.,        23.497200,
                  22.2116,-179.723000000,-      157.50370,      7.80620000        ,20.79880,       4.2757000,-       116.59630,-    3.9410000,-      17.579200,
                   51.585,-6.9775,51.585,       6.977500,-      3.9410000,        17.579200,        4.27570000,    116.5963000,      7.8062000,-    20.79880,-
                      179.723,157.5037          ,23.4972,-      22.2116};D         l=13;/**/         dark_magic(   c,sizeof(c)        /sizeof(c[   0]),l);}//
        

Thanks!

Thanks for reading! If you liked this, check out my GitHub, and my about me page.