fix_fft problem

hello

i’m studing fft and this code

/*
modified by varind in 2013
this code is public domain, enjoy!
 */

#include <LiquidCrystal.h>
#include <fix_fft.h>
#include <Servo.h> 
#define LCHAN 5
#define RCHAN 4
const int channels = 2;
const int xres = 16;
const int yres = 8;
const int gain = 3;
//int decayrate = 2; // larger number is longer decay
int decaytest = 1;
char im[64], data[64];
char Rim[64], Rdata[64];
char data_avgs[32];
float peaks[32];
int i = 0,val,Rval;
int x = 0, y=0, z=0;
LiquidCrystal lcd(2, 3, 4, 7, 8, 12); //saves 5 pwm pins for servos, leds, etc

Servo servo1, servo2, servo3, servo4;
int startpos = 90;
int calibrate = 0;  //locks servos at startpos (lowest value)
int pos1 = startpos, pos2 = startpos, pos3 = startpos, pos4 = startpos;
int servomap, servomap2;

// VU METER CHARACTERS
byte v1[8] = {
  B00000,B00000,B00000,B00000,B00000,B00000,B00000,B11111};
byte v2[8] = {
  B00000,B00000,B00000,B00000,B00000,B00000,B11111,B11111};
byte v3[8] = {
  B00000,B00000,B00000,B00000,B00000,B11111,B11111,B11111};
byte v4[8] = {
  B00000,B00000,B00000,B00000,B11111,B11111,B11111,B11111};
byte v5[8] = {
  B00000,B00000,B00000,B11111,B11111,B11111,B11111,B11111};
byte v6[8] = {
  B00000,B00000,B11111,B11111,B11111,B11111,B11111,B11111};
byte v7[8] = {
  B00000,B11111,B11111,B11111,B11111,B11111,B11111,B11111};
byte v8[8] = {
  B11111,B11111,B11111,B11111,B11111,B11111,B11111,B11111};


void setup() {
  //  Serial.begin(9600);

  lcd.begin(16, 2);
  lcd.clear();
  lcd.createChar(1, v1);
  lcd.createChar(2, v2);
  lcd.createChar(3, v3);
  lcd.createChar(4, v4);
  lcd.createChar(5, v5);
  lcd.createChar(6, v6);
  lcd.createChar(7, v7);
  lcd.createChar(8, v8);

  //analogReference(DEFAULT);

  //  servo1.attach(5);
  //  servo2.attach(6);
  //  servo3.attach(9);
  //  servo4.attach(10);

  //  servo1.write(pos1);
  //  servo2.write(pos2);
  //  servo3.write(pos3);
  //  servo4.write(pos4);
}

void loop() {
//  delay(10);
  for (i=0; i < 64; i++){    
    val = ((analogRead(LCHAN) / 4 ) - 128);  // chose how to interpret the data from analog in
    data[i] = val;                                      
    im[i] = 0;   
    if (channels ==2){
      Rval = ((analogRead(RCHAN) / 4 ) - 128);  // chose how to interpret the data from analog in
      Rdata[i] = Rval;                                      
      Rim[i] = 0;   
    }
  };
fix_fft(data,im,6,0); // Send the data through fft
  if (channels == 2){
    fix_fft(Rdata,Rim,6,0); // Send the data through fft
  }

  // get the absolute value of the values in the array, so we're only dealing with positive numbers
  for (i=0; i< 32 ;i++){  
    data[i] = sqrt(data[i] * data[i] + im[i] * im[i]); 
  }
  if (channels ==2){
    for (i=16; i< 32 ;i++){  
      data[i] = sqrt(Rdata[i-16] * Rdata[i-16] + Rim[i-16] * Rim[i-16]); 
    }
  }

  // todo: average as many or as little dynamically based on yres
  for (i=0; i<32; i++) {
    data_avgs[i] = (data[i]);// + data[i*2+1]);// + data[i*3 + 2]);// + data[i*4 + 3]);  // add 3 samples to be averaged, use 4 when yres < 16
    data_avgs[i] = constrain(data_avgs[i],0,9-gain);  //data samples * range (0-9) = 9
    data_avgs[i] = map(data_avgs[i], 0, 9-gain, 0, yres);        // remap averaged values
  }



  //servos();
  decay(1);
  //thirtytwoband();
  //mono();
  //stereo8();
  stereo16();


} // end loop








void decay(int decayrate){
  //// reduce the values of the last peaks by 1 
  if (decaytest == decayrate){
    for (x=0; x < 32; x++) {
      peaks[x] = peaks[x] - 1;  // subtract 1 from each column peaks
      decaytest = 0;
      
    }
  }
  decaytest++;

}

void mono(){ 
  for (x=0; x < xres; x++) {  // repeat for each column of the display horizontal resolution
    y = data_avgs[x];  // get current column value 
        z= peaks[x];
    if (y > z){
      peaks[x]=y;
    }
    y= peaks[x]; 

    if (y <= 8){            
      lcd.setCursor(x,0); // clear first row
      lcd.print(" ");
      lcd.setCursor(x,1); // draw second row
      if (y == 0){
        lcd.print(" "); // save a glyph
      }
      else {
        lcd.write(y);
      }
    }
    else{
      lcd.setCursor(x,0);  // draw first row
      if (y == 9){
        lcd.write(" ");  
      }
      else {
        lcd.write(y-8);  // same chars 1-8 as 9-16
      }
      lcd.setCursor(x,1);
      lcd.write(8);  
    } // end display
  }  // end xres
}

void stereo8(){
  for (x=0; x < 8; x++) {
    y = data_avgs[x];
        z= peaks[x];
    if (y > z){
      peaks[x]=y;
    }
    y= peaks[x]; 

    if (y <= 8){            
      lcd.setCursor(x,0); // clear first row
      lcd.print(" ");
      lcd.setCursor(x,1); // draw second row
      if (y == 0){
        lcd.print(" "); // save a glyph
      }
      else {
        lcd.write(y);
      }
    }
    else{
      lcd.setCursor(x,0);  // draw first row
      if (y == 9){
        lcd.write(" ");  
      }
      else {
        lcd.write(y-8);  // same chars 1-8 as 9-16
      }
      lcd.setCursor(x,1);
      lcd.write(8);  
    }
  }
  for (x=16; x < 32; x++) {
    y = data_avgs[x];
       z= peaks[x];
    if (y > z){
      peaks[x]=y;
    }
    y= peaks[x]; 

    if (y <= 8){            
      lcd.setCursor(x-8,0); // clear first row
      lcd.print(" ");
      lcd.setCursor(x-8,1); // draw second row
      if (y == 0){
        lcd.print(" "); // save a glyph
      }
      else {
        lcd.write(y);
      }
    }
    else{
      lcd.setCursor(x-8,0);  // draw first row
      if (y == 9){
        lcd.write(" ");  
      }
      else {
        lcd.write(y-8);  // same chars 1-8 as 9-16
      }
      lcd.setCursor(x-8,1);
      lcd.write(8);  
    }
  }
}

void stereo16(){
  for (x=0; x < 16; x++) {
    y = data_avgs[x];
         z= peaks[x];
    if (y > z){
      peaks[x]=y;
    }
    y= peaks[x]; 
    if (x < xres){            
      lcd.setCursor(x,0); // draw first row
      if (y == 0){
        lcd.print(" "); // save a glyph
      }
      else {
        lcd.write(y);
      }
    }
  }

  for (x=16; x < 32; x++) {
    y = data_avgs[x];
        z= peaks[x];
    if (y > z){
      peaks[x]=y;
    }
    y= peaks[x]; 
    if (x-16 < xres){            
      lcd.setCursor(x-16,1); // draw second row
      if (y == 0){
        lcd.print(" "); // save a glyph
      }
      else {
        lcd.write(y);
      }
    }
  }
}


void thirtytwoband(){
  for (x=0; x < 32; x++) {
    y = data_avgs[x];

        z= peaks[x];
    if (y > z){
      peaks[x]=y;
    }
    y= peaks[x]; 
    if (x < 16){            
      lcd.setCursor(x,0); // draw second row
      if (y == 0){
        lcd.print(" "); // save a glyph
      }
      else {
        lcd.write(y);
      }
    }
    else{
      lcd.setCursor(x-16,1);
      if (y == 0){
        lcd.print(" ");
      }
      else {
        lcd.write(y);
      }
    }
  }
}


void goservo(){
  for (x=0; x < xres; x++) {  // repeat for each column of the display horizontal resolution
    y = data_avgs[x];  // get current column value 
    if (calibrate != 1){
      servomap = map(y, 0, yres, 90, 180);
      servomap2 = map(y, 0, yres, 90, 00);
      if ( x== xres/8){
        servo1.write(servomap);    
      }
      if (x == xres/4){
        servo2.write(servomap2);
      }  
      if (x == xres/2){
        servo3.write(servomap);    
      }
      if (x == xres/1){
        servo4.write(servomap2);
      }
    }
  }
}

It’s an Audio-Spectrum-Analyzer.ino based on hte fix_ftt lib.

My problem :

/home/seb/Arduino/Audio-Spectrum-Analyzer.ino/Audio-Spectrum-Analyzer.ino.ino:90: undefined reference to `fix_fft(char*, char*, int, int)'

The lib is installed.
The var send into the functions are the good type (i think)?

Have you an idea to help me please?

Post the link from which you downloaded the fix_fft library.

Uh!
You are quick! Thanks

I am searching the link…

Here :

Is there different fix_fft libs?

Thanks for your interrest

Is there different fix_fft libs?

Yes, several.

Post the code, using code tags, for both the .c and .h files from the fix_fft library you are using, because it is not the same as the one you linked. That one triggers a Wprogram.h error.

The error message may result from a previously mentioned C/C++ preprocessor bug that fails to correctly position some or all of the function prototypes.

I fixed that particular problem by including the fft function code directly into the main program, before setup(), assuming that you are using the 8 bit version of fix_fft.

Code appended as attachment. It compiles with no errors, but there are no guarantees that it will work as you expect.

fix_fft2.ino (13.2 KB)

Thanks.
So many responses:)

I will see this tonight, here i wil work (i am in south of France).

Thanks to this comunity

fix_fft .c & .h

#ifndef FIXFFT_H
#define FIXFFT_H

//#include <WProgram.h>




/*
  fix_fft() - perform forward/inverse fast Fourier transform.
  fr[n],fi[n] are real and imaginary arrays, both INPUT AND
  RESULT (in-place FFT), with 0 <= n < 2**m; set inverse to
  0 for forward transform (FFT), or 1 for iFFT.
*/
int fix_fft(char fr[], char fi[], int m, int inverse);



/*
  fix_fftr() - forward/inverse FFT on array of real numbers.
  Real FFT/iFFT using half-size complex FFT by distributing
  even/odd samples into real/imaginary arrays respectively.
  In order to save data space (i.e. to avoid two arrays, one
  for real, one for imaginary samples), we proceed in the
  following two steps: a) samples are rearranged in the real
  array so that all even samples are in places 0-(N/2-1) and
  all imaginary samples in places (N/2)-(N-1), and b) fix_fft
  is called with fr and fi pointing to index 0 and index N/2
  respectively in the original array. The above guarantees
  that fix_fft "sees" consecutive real samples as alternating
  real and imaginary samples in the complex array.
*/
int fix_fftr(char f[], int m, int inverse);




#endif
#include <avr/pgmspace.h>
#include "fix_fft.h"
#include <Arduino.h>

/* fix_fft.c - Fixed-point in-place Fast Fourier Transform  */
/*
  All data are fixed-point short integers, in which -32768
  to +32768 represent -1.0 to +1.0 respectively. Integer
  arithmetic is used for speed, instead of the more natural
  floating-point.
  For the forward FFT (time -> freq), fixed scaling is
  performed to prevent arithmetic overflow, and to map a 0dB
  sine/cosine wave (i.e. amplitude = 32767) to two -6dB freq
  coefficients. The return value is always 0.
  For the inverse FFT (freq -> time), fixed scaling cannot be
  done, as two 0dB coefficients would sum to a peak amplitude
  of 64K, overflowing the 32k range of the fixed-point integers.
  Thus, the fix_fft() routine performs variable scaling, and
  returns a value which is the number of bits LEFT by which
  the output must be shifted to get the actual amplitude
  (i.e. if fix_fft() returns 3, each value of fr[] and fi[]
  must be multiplied by 8 (2**3) for proper scaling.
  Clearly, this cannot be done within fixed-point short
  integers. In practice, if the result is to be used as a
  filter, the scale_shift can usually be ignored, as the
  result will be approximately correctly normalized as is.
  Written by:  Tom Roberts  11/8/89
  Made portable:  Malcolm Slaney 12/15/94 malcolm@interval.com
  Enhanced:  Dimitrios P. Bouras  14 Jun 2006 dbouras@ieee.org
  Modified for 8bit values David Keller  10.10.2010
*/


#define N_WAVE	256    /* full length of Sinewave[] */
#define LOG2_N_WAVE 8	/* log2(N_WAVE) */




/*
  Since we only use 3/4 of N_WAVE, we define only
  this many samples, in order to conserve data space.
*/


//const prog_int8_t Sinewave[N_WAVE-N_WAVE/4] PROGMEM = {
const int8_t Sinewave[N_WAVE-N_WAVE/4] PROGMEM = {
0, 3, 6, 9, 12, 15, 18, 21,
24, 28, 31, 34, 37, 40, 43, 46,
48, 51, 54, 57, 60, 63, 65, 68,
71, 73, 76, 78, 81, 83, 85, 88,
90, 92, 94, 96, 98, 100, 102, 104,
106, 108, 109, 111, 112, 114, 115, 117,
118, 119, 120, 121, 122, 123, 124, 124,
125, 126, 126, 127, 127, 127, 127, 127,

127, 127, 127, 127, 127, 127, 126, 126,
125, 124, 124, 123, 122, 121, 120, 119,
118, 117, 115, 114, 112, 111, 109, 108,
106, 104, 102, 100, 98, 96, 94, 92,
90, 88, 85, 83, 81, 78, 76, 73,
71, 68, 65, 63, 60, 57, 54, 51,
48, 46, 43, 40, 37, 34, 31, 28,
24, 21, 18, 15, 12, 9, 6, 3,

0, -3, -6, -9, -12, -15, -18, -21,
-24, -28, -31, -34, -37, -40, -43, -46,
-48, -51, -54, -57, -60, -63, -65, -68,
-71, -73, -76, -78, -81, -83, -85, -88,
-90, -92, -94, -96, -98, -100, -102, -104,
-106, -108, -109, -111, -112, -114, -115, -117,
-118, -119, -120, -121, -122, -123, -124, -124,
-125, -126, -126, -127, -127, -127, -127, -127,

/*-127, -127, -127, -127, -127, -127, -126, -126,
-125, -124, -124, -123, -122, -121, -120, -119,
-118, -117, -115, -114, -112, -111, -109, -108,
-106, -104, -102, -100, -98, -96, -94, -92,
-90, -88, -85, -83, -81, -78, -76, -73,
-71, -68, -65, -63, -60, -57, -54, -51,
-48, -46, -43, -40, -37, -34, -31, -28,
-24, -21, -18, -15, -12, -9, -6, -3, */
};






/*
  FIX_MPY() - fixed-point multiplication & scaling.
  Substitute inline assembly for hardware-specific
  optimization suited to a particluar DSP processor.
  Scaling ensures that result remains 16-bit.
*/
inline char FIX_MPY(char a, char b)
{
  
  //Serial.println(a);
 //Serial.println(b);
  
  
    /* shift right one less bit (i.e. 15-1) */
    int c = ((int)a * (int)b) >> 6;  //6
    /* last bit shifted out = rounding-bit */
    b = c & 0x01;
    /* last shift + rounding bit */
    a = (c >> 1) + b;

	  /*
	  Serial.println(Sinewave[3]);
	  Serial.println(c);
	  Serial.println(a);
	  while(1);*/

    return a;
}

/*
  fix_fft() - perform forward/inverse fast Fourier transform.
  fr[n],fi[n] are real and imaginary arrays, both INPUT AND
  RESULT (in-place FFT), with 0 <= n < 2**m; set inverse to
  0 for forward transform (FFT), or 1 for iFFT.
*/
int fix_fft(char fr[], char fi[], int m, int inverse)
{
    int mr, nn, i, j, l, k, istep, n, scale, shift;
    char qr, qi, tr, ti, wr, wi;

    n = 1 << m;

    /* max FFT size = N_WAVE */
    if (n > N_WAVE)
	  return -1;

    mr = 0;
    nn = n - 1;
    scale = 0;

    /* decimation in time - re-order data */
    for (m=1; m<=nn; ++m) {
	  l = n;
	  do {
		l >>= 1;
	  } while (mr+l > nn);
	  mr = (mr & (l-1)) + l;

	  if (mr <= m)
		continue;
	  tr = fr[m];
	  fr[m] = fr[mr];
	  fr[mr] = tr;
	  ti = fi[m];
	  fi[m] = fi[mr];
	  fi[mr] = ti;
    }

    l = 1;
    k = LOG2_N_WAVE-1;
    while (l < n) {
	  if (inverse) {
		/* variable scaling, depending upon data */
		shift = 0;
		for (i=0; i<n; ++i) {
		    j = fr[i];
		    if (j < 0)
			  j = -j;
		    m = fi[i];
		    if (m < 0)
			  m = -m;
		    if (j > 16383 || m > 16383) {
			  shift = 1;
			  break;
		    }
		}
		if (shift)
		    ++scale;
	  } else {
		/*
		  fixed scaling, for proper normalization --
		  there will be log2(n) passes, so this results
		  in an overall factor of 1/n, distributed to
		  maximize arithmetic accuracy.
		*/
		shift = 1;
	  }
	  /*
	    it may not be obvious, but the shift will be
	    performed on each data point exactly once,
	    during this pass.
	  */
	  istep = l << 1;
	  for (m=0; m<l; ++m) {
		j = m << k;
		/* 0 <= j < N_WAVE/2 */
		wr =  pgm_read_word_near(Sinewave + j+N_WAVE/4);
		wi = -pgm_read_word_near(Sinewave + j);
		if (inverse)
		    wi = -wi;
		if (shift) {
		    wr >>= 1;
		    wi >>= 1;
		}
		for (i=m; i<n; i+=istep) {
		    j = i + l;
		    tr = FIX_MPY(wr,fr[j]) - FIX_MPY(wi,fi[j]);
		    ti = FIX_MPY(wr,fi[j]) + FIX_MPY(wi,fr[j]);
		    qr = fr[i];
		    qi = fi[i];
		    if (shift) {
			  qr >>= 1;
			  qi >>= 1;
		    }
		    fr[j] = qr - tr;
		    fi[j] = qi - ti;
		    fr[i] = qr + tr;
		    fi[i] = qi + ti;
		}
	  }
	  --k;
	  l = istep;
    }
    return scale;
}

/*
  fix_fftr() - forward/inverse FFT on array of real numbers.
  Real FFT/iFFT using half-size complex FFT by distributing
  even/odd samples into real/imaginary arrays respectively.
  In order to save data space (i.e. to avoid two arrays, one
  for real, one for imaginary samples), we proceed in the
  following two steps: a) samples are rearranged in the real
  array so that all even samples are in places 0-(N/2-1) and
  all imaginary samples in places (N/2)-(N-1), and b) fix_fft
  is called with fr and fi pointing to index 0 and index N/2
  respectively in the original array. The above guarantees
  that fix_fft "sees" consecutive real samples as alternating
  real and imaginary samples in the complex array.
*/
int fix_fftr(char f[], int m, int inverse)
{
    int i, N = 1<<(m-1), scale = 0;
    char tt, *fr=f, *fi=&f[N];

    if (inverse)
	  scale = fix_fft(fi, fr, m-1, inverse);
    for (i=1; i<N; i+=2) {
	  tt = f[N+i-1];
	  f[N+i-1] = f[i];
	  f[i] = tt;
    }
    if (! inverse)
	  scale = fix_fft(fi, fr, m-1, inverse);
    return scale;
}

I will try to include the function in my main.

It's ok with the function in before the setup.

I should study the probleme of the lib if i wish augment my understandment of the C...

@jremington

you're living in Oregon.
With my childrens, we love Gravity Falls, with stan, dipper & mabel.
Is it a true place?? :slight_smile:

Gravity Falls, with stan, dipper & mabel.
Is it a true place??

No, not a real place. The name is great, though.

I should study the probleme of the lib if i wish augment my understandment of the C

Don't bother, because what you did should work, at least with Arduino. There is a problem with the Arduino IDE.

However, if you program in standard C/C++ you usually do need to include function prototypes. The Arduino IDE tries to do this for you and sometimes fails.

Ok.
I was getting crazy with this.
Thanks

But, why((in the errors wrote by the compiler) the «*» appears? IDE's problem?

Do you mean the asterisks (*) in this line?

undefined reference to `fix_fft(char*, char*, int, int)'

Those indicate that the function template expects the calling program to provide pointers to character variables or character arrays.

The construction is correct in the calling program, but the IDE can't find a matching function in the library, or it can't find the library. This is clearly a problem with the Arduino IDE, because it is fixed by including the identical code in the original source program.

The problem is not a bug in the Arduino IDE. The problem is that fix_fft() is a C function but the .ino files of Arduino sketches are compiled as C++. If you want to use a C function from C++, you need to wrap it in extern “C” {}. You can do that from the sketch by changing line 9 of the sketch from:

#include <fix_fft.h>

to:

extern "C" {
#include <fix_fft.h>
}

After that there’s a new error:

C:\Users\per\AppData\Local\Temp\ccvDWnSv.ltrans0.ltrans.o: In function `fix_fft.constprop.0':

<artificial>:(.text+0x4a2): undefined reference to `FIX_MPY'

I don’t understand that cause of that, but it does go away when you remove the inline keyword from the definition of FIX_MPY() in fix_fft.c.

Probably the most easy way to fix the library is to change the filename fix_fft.c to fix_fft.cpp. After that it will compile without any changes to the library or sketch code.

Ahh, not a "bug" but a "feature"!

The problem was trivially fixed in reply #5.

jremington:
The problem was trivially fixed in reply #5.

That's not a fix. That's a hacky workaround based on a faulty assumption of what the problem was. Better to learn how to make the code work left in a library, as intended.

That's a hacky workaround based on a faulty assumption of what the problem was.

No, it was a perfectly acceptable and efficient solution to a problem.

Have you noticed that people often include function code other than setup() and loop() in their .ino files? If not, try it, the approach is popular and works quite well.

Plus, it is pretty silly to make a single, short function into a "library", don't you think?

OK
Thank you.
Your discussion about the "bug" or the "future" give to me a lot of reflexion.
I'll study this.

I include the code in the mail for the moment.

"feature" -- a popular term.