What kind of output should I see from getFft?

Question

Alright, so I am working on creating an Android audio visualization app. The problem is, what I get form the method getFft() doesn't jive with what google says it should produce. I traced the source code all the way back to C++, but I am not familiar enough with C++ or FFT to actually understand what is happening.

I will try and include everything needed here:

(Java) Visualizer.getFft(byte[] fft)

 /**
 * Returns a frequency capture of currently playing audio content. The capture is a 8-bit
 * magnitude FFT. Note that the size of the FFT is half of the specified capture size but both
 * sides of the spectrum are returned yielding in a number of bytes equal to the capture size.
 * {@see #getCaptureSize()}.
 * <p>This method must be called when the Visualizer is enabled.
 * @param fft array of bytes where the FFT should be returned
 * @return {@link #SUCCESS} in case of success,
 * {@link #ERROR_NO_MEMORY}, {@link #ERROR_INVALID_OPERATION} or {@link #ERROR_DEAD_OBJECT}
 * in case of failure.
 * @throws IllegalStateException
 */
public int getFft(byte[] fft)
throws IllegalStateException {
    synchronized (mStateLock) {
        if (mState != STATE_ENABLED) {
            throw(new IllegalStateException("getFft() called in wrong state: "+mState));
        }
        return native_getFft(fft);
    }
}

(C++) Visualizer.getFft(uint8_t *fft)

status_t Visualizer::getFft(uint8_t *fft)
{
if (fft == NULL) {
    return BAD_VALUE;
}
if (mCaptureSize == 0) {
    return NO_INIT;
}

status_t status = NO_ERROR;
if (mEnabled) {
    uint8_t buf[mCaptureSize];
    status = getWaveForm(buf);
    if (status == NO_ERROR) {
        status = doFft(fft, buf);
    }
} else {
    memset(fft, 0, mCaptureSize);
}
return status;
}

(C++) Visualizer.doFft(uint8_t *fft, uint8_t *waveform)

status_t Visualizer::doFft(uint8_t *fft, uint8_t *waveform)
{
int32_t workspace[mCaptureSize >> 1];
int32_t nonzero = 0;

for (uint32_t i = 0; i < mCaptureSize; i += 2) {
    workspace[i >> 1] = (waveform[i] ^ 0x80) << 23;
    workspace[i >> 1] |= (waveform[i + 1] ^ 0x80) << 7;
    nonzero |= workspace[i >> 1];
}

if (nonzero) {
    fixed_fft_real(mCaptureSize >> 1, workspace);
}

for (uint32_t i = 0; i < mCaptureSize; i += 2) {
    fft[i] = workspace[i >> 1] >> 23;
    fft[i + 1] = workspace[i >> 1] >> 7;
}

return NO_ERROR;
}

(C++) fixedfft.fixed_fft_real(int n, int32_t *v)

void fixed_fft_real(int n, int32_t *v)
{
int scale = LOG_FFT_SIZE, m = n >> 1, i;

fixed_fft(n, v);
for (i = 1; i <= n; i <<= 1, --scale);
v[0] = mult(~v[0], 0x80008000);
v[m] = half(v[m]);

for (i = 1; i < n >> 1; ++i) {
    int32_t x = half(v[i]);
    int32_t z = half(v[n - i]);
    int32_t y = z - (x ^ 0xFFFF);
    x = half(x + (z ^ 0xFFFF));
    y = mult(y, twiddle[i << scale]);
    v[i] = x - y;
    v[n - i] = (x + y) ^ 0xFFFF;
}
}

(C++) fixedfft.fixed_fft(int n, int32_t *v)

void fixed_fft(int n, int32_t *v)
{
int scale = LOG_FFT_SIZE, i, p, r;

for (r = 0, i = 1; i < n; ++i) {
    for (p = n; !(p & r); p >>= 1, r ^= p);
    if (i < r) {
        int32_t t = v[i];
        v[i] = v[r];
        v[r] = t;
    }
}

for (p = 1; p < n; p <<= 1) {
    --scale;

    for (i = 0; i < n; i += p << 1) {
        int32_t x = half(v[i]);
        int32_t y = half(v[i + p]);
        v[i] = x + y;
        v[i + p] = x - y;
    }

    for (r = 1; r < p; ++r) {
        int32_t w = MAX_FFT_SIZE / 4 - (r << scale);
        i = w >> 31;
        w = twiddle[(w ^ i) - i] ^ (i << 16);
        for (i = r; i < n; i += p << 1) {
            int32_t x = half(v[i]);
            int32_t y = mult(w, v[i + p]);
            v[i] = x - y;
            v[i + p] = x + y;
        }
    }
}
}

If you made it through all that, you are awesome! So my issue, is when I call the java method getFft() I end up with negative values, which shouldn't exist if the returned array is meant to represent magnitude. So my question is, what do I need to do to make the array represent magnitude?

EDIT: It appears my data may actually be the Fourier coefficients. I was poking around the web and found this. The applet "Start Function FFT" displays a graphed representation of coefficients and it is a spitting image of what happens when I graph the data from getFft(). So new question: Is this what my data is? and if so, how do I go from the coefficients to a spectral analysis of it?

Answer 1

One possible explanation why you see negative values: byte is a signed data type in Java. All values, that are greater or equal 1000 0000₂ are interpreted as negative integers.

If we know that all values should are expected to be in the range [0..255], then we have map the values to a larger type and filter the upper bits:

byte signedByte = 0xff;  // = -1
short unsignedByte = ((short) signedByte) & 0xff;   // = 255

Answer 2

An FFT doesn't just produce magnitude; it produces phase as well (the output for each sample is a complex number). If you want magnitude, then you need to explicitly calculate it for each output sample, as re*re + im*im, where re and im are the real and imaginary components of each complex number, respectively.

Unfortunately, I can't see anywhere in your code where you're working with complex numbers, so perhaps some rewrite is required.

UPDATE

If I had to guess (after glancing at the code), I'd say that real components were at even indices, and odd components were at odd indices. So to get magnitudes, you'd need to do something like:

uint32_t mag[N/2];
for (int i = 0; i < N/2; i++)
{
    mag[i] = fft[2*i]*fft[2*i] + fft[2*i+1]*fft[2*i+1];
}

Answer 3

"The capture is a 8-bit magnitude FFT" probably means that the return values have an 8-bit magnitude, not that they are magnitudes themselves.

According to Jason

For real-valued signals, like the ones you have in audio processing, the negative frequency output will be a mirror image of the positive frequencies.

Android 2.3 Visualizer - Trouble understanding getFft()