FS#10065 - FFT: A frequency analyzer plugin

Attached to Project: Rockbox
Opened by Delyan Kratunov (archivator) - Saturday, 28 March 2009, 21:52 GMT
Last edited by Frank Gevaerts (fg) - Wednesday, 10 February 2010, 19:55 GMT
Task Type Patches
Category Plugins
Status Closed
Assigned To No-one
Operating System All players
Severity Low
Priority Normal
Reported Version Version 3.1
Due in Version Undecided
Due Date Undecided
Percent Complete 100%
Votes 0
Private No


This task is a placeholder for my frequency analyzer work. In its current state, it should build on almost all targets (it will try at least - it doesn't do any feature checks - I am not sure what to check for.. ).

By default, it uses FFT with N = 512 (leading to 256 real values) and 10 Hz refresh rate. I think anything above 10 Hz is actually annoying and unusable.

It has two modes: lines and bars, attached are screenshots of both. The ultimate goal is to have it draw a spectrogram - a task that would require a bit of work but is far from impossible.

On an iPod Video 5.5G, there are sporadic freezes which are not directly related to user interaction or anything obvious for that matter. The simulator doesn't crash.

This is a pre-Alpha version. This plugin might lead to molten DAPs or burning frogs falling from the sky.
This task depends upon

Closed by  Frank Gevaerts (fg)
Wednesday, 10 February 2010, 19:55 GMT
Reason for closing:  Accepted
Additional comments about closing:  Committed as r24587
Comment by Jonas Häggqvist (rasher) - Saturday, 28 March 2009, 21:57 GMT
A good check for apps/plugins/SUBDIRS would be at least SWCODEC and LCD_BITMAP (all current swcodec targets have lcd_bitmap, but just in case, I guess)
Comment by Frank Gevaerts (fg) - Saturday, 28 March 2009, 23:06 GMT
I tried the file from (also attached), and I seem to get randomly distributed lines. I'd expect a single line moving from left to right (or multiple ones, depending on sampling speed, but still very grouped). Am I misunderstanding things, or is this a bug? This is on gigabeat F
Comment by Delyan Kratunov (archivator) - Wednesday, 01 April 2009, 10:06 GMT
So, it turns out, the math in the previous patch was all messed up. This version works as expected.

Due to the low number of samples the FFT has to work with (merely 1024 samples per channel), the results are less than optimal (the simulator tends to become unusable with N > 2048; I am yet to investigate the behavior on target).

The freeze bug has not been fixed but who knows, all the rework that was put in might have fixed it.

Next on my TODO list: logarithmic scaling. After that come the pretty colors. Only then can I start work on the spectrogram mode.
Comment by Delyan Kratunov (archivator) - Friday, 03 April 2009, 22:22 GMT
Added window function (Hamming)
Added logarithmic scaling
Added status message
Changed keymap in preparation for a third mode

The freeze bug still exists - I believe it occurs when calling pcm_get_peak_buffer though that's just a hunch.
Comment by Delyan Kratunov (archivator) - Tuesday, 07 April 2009, 10:08 GMT
Added second window function (Hann window)
Added horizontal orientation
Added colored lines mode
Added spectrogram mode
Removed the unused kiss_fftr* module
Fixed the freeze bug
Prettified the code in some places

The only thing left to do is to determine whether it's feasible to have spectrogram mode on grayscale targets. Currently, it built only on HAVE_LCD_COLOR targets.

The math needs a major review (I *feel* that it's off). I have no intention of adding a logarithmic scale to the frequency axis - I leave that as an exercise for the reader.

Also, the keymap could use some work.
Comment by Delyan Kratunov (archivator) - Tuesday, 28 April 2009, 19:28 GMT
I did initial review of my math and changed the way the code handled 32-bit overflows. Now, it does a 64-bit (s47.16) sqrt and then clips the value to the s15.16-bit range needed for the fixed-point logarithm. Not the most elegant of solutions and certainly quite CPU-intensive (all the 64-bit math in fsqrt64, in particular) but good enough for the time being.

The target refresh rate is now configured on a per-mode basis - this needs testing to find the optimal values for each platform.
The plugin now unboosts the CPU on exiting (sorry about that, I somehow missed it).
Fixed spectrogram mode on 320x240 screens (other sizes possibly affected, too; there were some spikes every 8 or so rows).

I began making the bitmaps external, though that is going to take some time. Right now, there are only 320x240 and 160x128 bitmaps. I need advice - do I keep the entire image as a bitmap or do I keep just one line and blit it over and over again?

Most importantly, there is initial work on greylib support though that is proving kind of hard, any and all help on this part will be appreciated.
Comment by Will Hauck (moonscapex) - Sunday, 13 September 2009, 20:05 GMT
Can someone please resync this?
Comment by Will Hauck (moonscapex) - Saturday, 19 September 2009, 19:56 GMT
Never mind... Just some files need to be manually patched.
Comment by Delyan Kratunov (archivator) - Monday, 14 December 2009, 01:00 GMT
It's been a long time but I actually want to get this done and possibly committed, so here goes the next patch:

- Make the code multi-threaded (needs some work in this area) - shouldn't make playback skip now
- Greylib support - should work on targets with greyscale screens
- Use LUTs for the window function coefficients - should have speeded things up a bit
- Bumped the transform size up to 4096 for the time being (can be from 512 up to 8192 - those are the only tables I've generated) - this is a bit too much for PP devices but I'm looking for feedback from beast users
- Switch to a kiss_fftr for the transform (i.e. do things properly :) )
- Dropped colored mode - wasn't particularly useful or pretty - requires just one bitmap now - the one with the colors

- Add a few more keymaps (can someone help me make proper keymaps? I kinda did them randomly when I started)
- Take a stab at the post-transform math - this needs to be rewritten - all help will be appreciated.
- No precompiled transform size? (this is actually quite difficult)
- Cleanup the kiss_fft code - there are radix-3 and -5 butterflies in there - we'll never use those..

The attached file is a git binary patch - use "git apply"
Comment by Delyan Kratunov (archivator) - Monday, 14 December 2009, 10:32 GMT
Apparently, you can use the standard patch tool to apply the last patch (I thought it would bail out on the binary part, my bad). If you do that, however, you'll end up missing a file.

The attached file goes in the apps/plugins/bitmaps/native directory. You'll already have it if you used git apply.
Comment by Delyan Kratunov (archivator) - Monday, 14 December 2009, 18:46 GMT
- Apparently, some targets don't have enough data in their peak buffer to do a 4096 transform. Hence, lower the buffer size to 2048 samples
- Use the second core on dual core targets
- Split the LUTs into multiple lines

Again, use "git apply" or see the previous post for instructions regarding the color map.
Comment by Delyan Kratunov (archivator) - Monday, 14 December 2009, 21:53 GMT
The whole "use second core" bit doesn't work and will eventually deadlock.
This patch reverts that change while I work out a better way to fetch data and parallelize the whole plugin.
Comment by Dave Hooper (stripwax) - Sunday, 20 December 2009, 10:44 GMT
Out of interest, how does the performance of the kiss_fft compare to the fft in the mdctexp branch of svn (currently in apps/codecs/lib/fft-ffmpeg) ?

Ideally we would want to encourage code reuse across the codebase - one fft available to both plugins and codecs as necessary - and it should make sense to ensure that the choice of fft is optimal in each case. We're currently evaluating a derivative of the ffmpeg fft code, for codec use (as part of the imdct used for transform codecs like mp3, vorbis). See page FasterMDCT on the wiki for more details.
Comment by Delyan Kratunov (archivator) - Sunday, 20 December 2009, 13:22 GMT
Dave, kiss fft is undoubtedly slower than the library in the new branch. However, the speed of the fft library is not the bottleneck here. What's limiting the speed of the plugin is the availability of pcm data.

I am currently trying to improve the way it's getting the data in order to reduce polling (or eliminate it entirely) and hopefully increase the speed a bit. However, I'm not too optimistic as each target apparently has its own peak buffer with its own size (the reason some targets can't do a 4096 transform). That is, at the end of the day, you only have so much data and the speed of the fft is not going to be that much of an issue.

I agree that it can and should eventually be optimized but right now I'm not touching it.
Comment by nofish (nofish) - Monday, 21 December 2009, 18:19 GMT
I'm interested in your FFT analyzer plugin and I'd gladly like to beta-test it on a iRiver h120.

However, I've no programming skills and would need a compiled version to test.

If you're interested, just send me a mail.

Comment by nofish (nofish) - Thursday, 24 December 2009, 23:23 GMT
Hi again,
I finally managed to compile the v8.patch.
Runs with no problems on my iRiver h120. May I ask if it will be possible in future versions to have also realtime FFT analysis on Mic and Line input ?

I'm recording a lot with the iRiver and such a feature would be really handy.
I'm also interested in testing future versions when available.

Comment by Delyan Kratunov (archivator) - Tuesday, 09 February 2010, 14:30 GMT
nofish, that can be done relatively easily, though I don't have a target to test it on. I also don't have the time to put into this plugin.

Thus, I would like to request that this plugin is committed as the changes I had envisioned proved much too time-consuming and difficult. This is the best I can do without touching the core. Of course, KISS FFT can be improved (or even replaced with a better implementation) but that's an insignificant improvement.

If someone is willing to go over the keymaps (I have no experience with keymaps and just hacked together a few keymaps - experience has shown that, except for iPods, they're horrible), I think this can safely be committed.

In any case, I really don't have the time for it any more and would hate to see it die in the FS graveyard. :)