Can somebody help explain what is happening in this fft code snippet

Question

first post here

I have been looking into the fft and in particular the Rosetta Code C implementation http://rosettacode.org/wiki/Fast_Fourier_transform#C

I have been trying to actually understand the code rather than just copy it however I have a problem with a particular line and more specifically a part of the line.

_fft(out+step, buf+step, n , step*2);

so we have a

typedef double complex cplx;

then an array of type cplx is declared

cplx buf[] = {1, 1, 1, 1, 0, 0, 0, 0};

We have step as an int 1

now the problem I am having understanding is what is happening when the int is added to the cplx

so I wrote a test program

#include <stdio.h>
#include <math.h>
#include <complex.h>

typedef double complex cplx;

void test(cplx buff[]) 
{
    for(int a = 0; a < 8; a++) {
        printf("%g \n", creal(buff[a]));
    }
}

int main(int argc, char **argv)
{
    cplx buff[] = {1,1,1,1,0,0,0,0};

    int step = 1;

    test(buff);

    test(buff + step);

    getchar();

    return 0;
}

what I get is:

1 1 1 1 0 0 0 0
1 1 1 0 0 0 0 2.1231e-314

I cannot make heads or tails of it, I may be missing something pretty fundamental about C99 as I cannot seem to be able to find it on here or by google

Answer 1

now the problem I am having understanding is what is happening when the int is added to the cplx

Actually the addition is not <int> + <cplx> but <int> + <cplx>* (in words an integer plus a pointer to a complex). So what you're dealing with here is what's called pointer arithmetic. Why a pointer you ask? Because in C array types degrade into a pointer to the array's element type when used in an expression which expects a pointer at its place.

So what is pointer arithmetic?

Well, let' s assume we got an object a which is an array of int (the length doesn't matter, as long as we don't access past its boundaries).

int a[N];

Then pointer arithmetic has been defined that the following three expressions have exactly the same meaning:

*(a + i)
a[i]
i[a]

Yes, the last one is perfectly valid C, go ahead, try it out.

What does it mean for your code snippet. Well for one thing, when you add 1 to the buffer pointer you pass to test, you're adding an offset of one. But since the buffer is only 8 elements long and your test function accesses 8 consecutive elements starting from the pointer given it performs an out-of-bounds access which invokes undefined behavior any in fact anything may legally happen.