After an evaluation, GNOME has moved from Bugzilla to GitLab. Learn more about GitLab.
No new issues can be reported in GNOME Bugzilla anymore.
To report an issue in a GNOME project, go to GNOME GitLab.
Do not go to GNOME Gitlab for: Bluefish, Doxygen, GnuCash, GStreamer, java-gnome, LDTP, NetworkManager, Tomboy.
Bug 468619 - New library gstfft: FFT library for integer and float types based on kiss
New library gstfft: FFT library for integer and float types based on kiss
Status: RESOLVED FIXED
Product: GStreamer
Classification: Platform
Component: gst-plugins-base
git master
Other Linux
: Normal normal
: 0.10.15
Assigned To: GStreamer Maintainers
GStreamer Maintainers
Depends on:
Blocks:
 
 
Reported: 2007-08-20 18:31 UTC by Sebastian Dröge (slomo)
Modified: 2007-09-06 06:59 UTC
See Also:
GNOME target: ---
GNOME version: ---


Attachments
Sources and build system integration (157.36 KB, patch)
2007-08-20 18:32 UTC, Sebastian Dröge (slomo)
none Details | Review
Docs integration (4.00 KB, patch)
2007-08-20 18:32 UTC, Sebastian Dröge (slomo)
none Details | Review
Many improvements and changes to spectrum, including use of libgstfft (46.30 KB, patch)
2007-08-20 18:36 UTC, Sebastian Dröge (slomo)
none Details | Review
Sources and build system integration (version 2) (157.48 KB, patch)
2007-08-20 18:57 UTC, Sebastian Dröge (slomo)
reviewed Details | Review
Docs integration (version 2) (4.00 KB, patch)
2007-08-20 18:58 UTC, Sebastian Dröge (slomo)
committed Details | Review
Many improvements and changes to spectrum, including use of libgstfft (version 2) (47.84 KB, patch)
2007-08-22 17:42 UTC, Sebastian Dröge (slomo)
committed Details | Review
Unit tests for libgstfft (12.47 KB, patch)
2007-08-23 21:32 UTC, Sebastian Dröge (slomo)
committed Details | Review
Sources and build system integration (version 3) (157.59 KB, patch)
2007-08-23 21:36 UTC, Sebastian Dröge (slomo)
committed Details | Review

Description Sebastian Dröge (slomo) 2007-08-20 18:31:36 UTC
Hi,
the attached patches add libgstfft to gst-plugins-base. This is a FFT library, wrapping kiss fft, and working for int16, int32, float and double data.

kiss fft is a BSD licensed FFT library, I'm wrapping the optimization for real input here which is about 45% faster than a standard FFT.
http://kissfft.sourceforge.net

Also attached is a patch to gstspectrum which uses this new library (and unfortunately also has many many other improvements and changes).

Bye
Comment 1 Sebastian Dröge (slomo) 2007-08-20 18:32:13 UTC
Created attachment 94005 [details] [review]
Sources and build system integration
Comment 2 Sebastian Dröge (slomo) 2007-08-20 18:32:31 UTC
Created attachment 94006 [details] [review]
Docs integration
Comment 3 Sebastian Dröge (slomo) 2007-08-20 18:36:45 UTC
Created attachment 94008 [details] [review]
Many improvements and changes to spectrum, including use of libgstfft

This does the following to spectrum:
- porting to GstAudioFilter
- averaging all FFTs done in one interval
- adding support for int32, float and double
- use libgstfft
- use a better windowing function, giving much better results
- use floats for the GstMessage contents
- allow posting phase together with the magnitude in one message
- actually do an FFT with the specified number of bands instead of always doing a 1024 FFT and interpolate the bands
- improve the unit test much by using a 11025 hz signal and checking the FFT of that for all 4 supported input types
Comment 4 Sebastian Dröge (slomo) 2007-08-20 18:40:04 UTC
The only changes to kiss fft are limiting to a specific data type btw... in the kiss_fft.h and _kiss_fft_guts.h header files. Should be very easy to sync from time to time with kiss fft... not that there are many changes lately, it's a very solid, mature and fairly bug free (I didn't find a single one) implementation already.
Comment 5 Sebastian Dröge (slomo) 2007-08-20 18:41:07 UTC
Also it might make sense to add an additional unit test to this, not only using the spectrum one as an indirect unit test ;)
I'll write one if everything else is good and reviewed.
Comment 6 Sebastian Dröge (slomo) 2007-08-20 18:57:42 UTC
Created attachment 94010 [details] [review]
Sources and build system integration (version 2)

changes:
 - call gst_fft_next_fast_size gst_fft_next_fast_length for consistency reasons
Comment 7 Sebastian Dröge (slomo) 2007-08-20 18:58:53 UTC
Created attachment 94011 [details] [review]
Docs integration (version 2)

changes:
 - call gst_fft_next_fast_size gst_fft_next_fast_length

PS: I also changed gst_fft_next_fast_length in the last patch to always return an even number as required by the real fft optimization.
Comment 8 Sebastian Dröge (slomo) 2007-08-22 17:42:44 UTC
Created attachment 94132 [details] [review]
Many improvements and changes to spectrum, including use of libgstfft (version 2)

changes: probably none, but the old patch had rejects for Stefan for some reason.
Comment 9 Stefan Sauer (gstreamer, gtkdoc dev) 2007-08-23 06:10:33 UTC
wow! this is much better! In gstspectrum.c please add this:

  #ifdef HAVE_CONFIG_H
  #include "config.h"
  #endif
  #include <string.h>
+ #include <stdlib.h>
  #include <gst/audio/audio.h>

and then commit! thanks a lot.
Comment 10 Sebastian Dröge (slomo) 2007-08-23 21:32:07 UTC
Created attachment 94220 [details] [review]
Unit tests for libgstfft
Comment 11 Sebastian Dröge (slomo) 2007-08-23 21:36:03 UTC
Created attachment 94221 [details] [review]
Sources and build system integration (version 3)

Fixes the _magnitude() functions.
Comment 12 Sebastian Dröge (slomo) 2007-08-27 09:44:41 UTC
One thing that might be worth a change is making the length parameter the actual length of the FFT in the frequency domain when creating a context for the inverse FFT. OTOH this might be confusing, not sure :)
Anybody have an oppinion on this?
Comment 13 Stefan Sauer (gstreamer, gtkdoc dev) 2007-08-29 13:56:18 UTC
So when one would do
  fft()
  tweak_the_spectrum()
  inverse_fft()
you need two fft-instances? The change you suggest is that one can use the same value for length on both, right?
Comment 14 Sebastian Dröge (slomo) 2007-08-29 14:34:32 UTC
You need two instances already because of kiss_fftr (and kiss_fft). The kiss instances create some data they will need for each call when initializing.

The change would only change the meaning of the length parameter to "length in the input domain" while before it was "length in the time domain".

The change would have the problem, that it's not easy anymore to see which lengths are fast lengths as for an inverse fft one would need 2*len - 2 (== length in the time domain) to be factorizable completely by 2, 3 and 5.

I guess we should keep it as is...
Comment 15 Sebastian Dröge (slomo) 2007-08-31 05:49:05 UTC
Ok, I'm going to commit this once my CVS account works again and unless someone wants to see some things changed.
Comment 16 Sebastian Dröge (slomo) 2007-09-06 06:59:02 UTC
Committed:

2007-09-06  Sebastian Dröge  <slomo@circular-chaos.org>

        Reviewed by:  Stefan Kost  <ensonic@users.sf.net>

        * configure.ac:
        * gst-libs/gst/Makefile.am:
        * gst-libs/gst/fft/Makefile.am:
        * gst-libs/gst/fft/_kiss_fft_guts_f32.h:
        * gst-libs/gst/fft/_kiss_fft_guts_f64.h:
        * gst-libs/gst/fft/_kiss_fft_guts_s16.h:
        * gst-libs/gst/fft/_kiss_fft_guts_s32.h:
        * gst-libs/gst/fft/gstfft.c: (gst_fft_next_fast_length):
        * gst-libs/gst/fft/gstfft.h:
        * gst-libs/gst/fft/gstfftf32.c: (gst_fft_f32_new),
        (gst_fft_f32_fft), (gst_fft_f32_inverse_fft), (gst_fft_f32_free),
        (gst_fft_f32_window), (gst_fft_f32_magnitude), (gst_fft_f32_phase):
        * gst-libs/gst/fft/gstfftf32.h:
        * gst-libs/gst/fft/gstfftf64.c: (gst_fft_f64_new),
        (gst_fft_f64_fft), (gst_fft_f64_inverse_fft), (gst_fft_f64_free),
        (gst_fft_f64_window), (gst_fft_f64_magnitude), (gst_fft_f64_phase):
        * gst-libs/gst/fft/gstfftf64.h:
        * gst-libs/gst/fft/gstffts16.c: (gst_fft_s16_new),
        (gst_fft_s16_fft), (gst_fft_s16_inverse_fft), (gst_fft_s16_free),
        (gst_fft_s16_window), (gst_fft_s16_magnitude), (gst_fft_s16_phase):
        * gst-libs/gst/fft/gstffts16.h:
        * gst-libs/gst/fft/gstffts32.c: (gst_fft_s32_new),
        (gst_fft_s32_fft), (gst_fft_s32_inverse_fft), (gst_fft_s32_free),
        (gst_fft_s32_window), (gst_fft_s32_magnitude), (gst_fft_s32_phase):
        * gst-libs/gst/fft/gstffts32.h:
        * gst-libs/gst/fft/kiss_fft_f32.c: (kf_bfly2), (kf_bfly4),
        (kf_bfly3), (kf_bfly5), (kf_bfly_generic), (kf_work), (kf_factor),
        (kiss_fft_f32_alloc), (kiss_fft_f32_stride), (kiss_fft_f32),
        (kiss_fft_f32_cleanup), (kiss_fft_f32_next_fast_size):
        * gst-libs/gst/fft/kiss_fft_f32.h:
        * gst-libs/gst/fft/kiss_fft_f64.c: (kf_bfly2), (kf_bfly4),
        (kf_bfly3), (kf_bfly5), (kf_bfly_generic), (kf_work), (kf_factor),
        (kiss_fft_f64_alloc), (kiss_fft_f64_stride), (kiss_fft_f64),
        (kiss_fft_f64_cleanup), (kiss_fft_f64_next_fast_size):
        * gst-libs/gst/fft/kiss_fft_f64.h:
        * gst-libs/gst/fft/kiss_fft_s16.c: (kf_bfly2), (kf_bfly4),
        (kf_bfly3), (kf_bfly5), (kf_bfly_generic), (kf_work), (kf_factor),
        (kiss_fft_s16_alloc), (kiss_fft_s16_stride), (kiss_fft_s16),
        (kiss_fft_s16_cleanup), (kiss_fft_s16_next_fast_size):
        * gst-libs/gst/fft/kiss_fft_s16.h:
        * gst-libs/gst/fft/kiss_fft_s32.c: (kf_bfly2), (kf_bfly4),
        (kf_bfly3), (kf_bfly5), (kf_bfly_generic), (kf_work), (kf_factor),
        (kiss_fft_s32_alloc), (kiss_fft_s32_stride), (kiss_fft_s32),
        (kiss_fft_s32_cleanup), (kiss_fft_s32_next_fast_size):
        * gst-libs/gst/fft/kiss_fft_s32.h:
        * gst-libs/gst/fft/kiss_fftr_f32.c: (kiss_fftr_f32_alloc),
        (kiss_fftr_f32), (kiss_fftri_f32):
        * gst-libs/gst/fft/kiss_fftr_f32.h:
        * gst-libs/gst/fft/kiss_fftr_f64.c: (kiss_fftr_f64_alloc),
        (kiss_fftr_f64), (kiss_fftri_f64):
        * gst-libs/gst/fft/kiss_fftr_f64.h:
        * gst-libs/gst/fft/kiss_fftr_s16.c: (kiss_fftr_s16_alloc),
        (kiss_fftr_s16), (kiss_fftri_s16):
        * gst-libs/gst/fft/kiss_fftr_s16.h:
        * gst-libs/gst/fft/kiss_fftr_s32.c: (kiss_fftr_s32_alloc),
        (kiss_fftr_s32), (kiss_fftri_s32):
        * gst-libs/gst/fft/kiss_fftr_s32.h:
        * gst-libs/gst/fft/kiss_version:
        * pkgconfig/gstreamer-plugins-base-uninstalled.pc.in:
        * pkgconfig/gstreamer-plugins-base.pc.in:
        Add libgstfft, a FFT library based on Kiss FFT which is
        BSD licensed. Supported sample formats are int16, int32,
        float and double. For those formats a real FFT and IFFT
        can be done, different windowing functions can be applied
        and functions for extracting the magnitude and phase exist.
        Fixes #468619.

        * docs/libs/Makefile.am:
        * docs/libs/gst-plugins-base-libs-docs.sgml:
        * docs/libs/gst-plugins-base-libs-sections.txt:
        Integrate libgstfft into the docs.

        * tests/check/Makefile.am:
        * tests/check/libs/fft.c: (GST_START_TEST), (fft_suite), (main):
        Add unit tests for libgstfft, currently only testing the FFT.
        Unit tests for IFFT will follow soon.