DSP_fft
_nassert((int)x % 8 == 0); _nassert((int)y % 8 == 0); _nassert((int)w % 8 == 0); _nassert(n >= 16); _nassert(n < 32768); #endif
/* −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− */
/* Perform initial stages of FFT in place w/out digit reversal. */ /* −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− */ #ifndef NOASSUME
#pragma MUST_ITERATE(1,,1); #endif
for (stride = n, t = 0; stride > 4; stride >>= 2)
{
/* −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− */
/* Perform each of the butterflies for this particular stride. */
/* −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− */ s = stride >> 2; /*−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−*/ /* stride represents the seperation between the inputs of the radix */ /* 4 butterfly. The C code breaks the FFT, into two cases, one when */
/* the stride between the elements is greater than 4, other when | */ |
/* the stride is less than 4. Since stride is greater than 16, it | */ |
/* can be guaranteed that ”s” is greater than or equal to 4. | */ |
/* In addition, it can also be shown that the loop that shares this | */ |
/* stride will iterate at least once. The number of times this | */ |
/* loop iterates depends on how many butterflies in this stage | */ |
/* share a twiddle factor. | */ |
/*−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−*/
#ifndef NOASSUME
_nassert(stride >= 16);
_nassert(s >= 4);
#pragma MUST_ITERATE(1,,1); #endif
for (i = 0; i < n; i += stride)
