← Back to branch summary

~ubuntu-branches/ubuntu/maverick/ultrastar-ng/maverick

« back to all changes in this revision

Viewing changes to audio/fft.hpp

  • Committer: Bazaar Package Importer
  • Author(s): Miriam Ruiz, Miriam Ruiz, Mario Bonino, Jon Dowland, Ansgar Burchardt
  • Date: 2008-06-07 16:43:18 UTC
  • mfrom: (4.1.1 lenny)
  • Revision ID: james.westby@ubuntu.com-20080607164318-4cnzizck1tp8mrwp
Tags: 0.2.1-1
http://bugs.debian.org/453132
http://bugs.debian.org/478634
[ Miriam Ruiz ]
* New Upstream Release (Closes: #453132)
* Removed unneeded patches
* Added packages to build deps:
  + libtool
  + portaudio19-dev | portaudio-dev
  + libboost-dev, libboost-thread-dev, libboost-serialization-dev
  + libboost-program-options-dev, libboost-regex-dev
* Moved shared objects to private directory: /usr/lib/ultraster-ng
* Added rpath to binaries to search for shared objects in the private dir
* Uses ultrastar-ng-gstreamer as default, instead of ultrastar-ng-xine,
  since there are significantly less issues with GStreamer.
* Added patch to fix upstream desktop file
* Added -Wl,-as-needed to LDFLAGS
* Replaced fftw3-dev by libfftw3-dev in build dependencies.
* Standards-Version upgraded to 3.7.3

[ Mario Bonino ]
* Fixed data/Makefile.am to install .desktop file and icon

[ Jon Dowland ]
* add Homepage: control field to source stanza
* fix a bashism in debian/rules (Closes: #478634)

[ Ansgar Burchardt ]
* debian/control: Change XS-Vcs-* to Vcs-*
* Remove Homepage semi-field from description

Show diffs side-by-side

added added

removed removed

Lines of Context:
audio/fft.hpp
 
1
#ifndef AUDIO_FFT_HPP_INCLUDED
 
2
#define AUDIO_FFT_HPP_INCLUDED
 
3
 
 
4
/**
 
5
@file fft.hpp FFT and related facilities.
 
6
 
 
7
Header only, no need to link with libda.
 
8
**/
 
9
 
 
10
#include <complex>
 
11
#include <cstddef>
 
12
 
 
13
namespace da {
 
14
 
 
15
        namespace math {
 
16
 
 
17
                /** Calculate the square of val. **/
 
18
                static inline double sqr(double val) { return val * val; }
 
19
                
 
20
                template <unsigned M, unsigned N, unsigned B, unsigned A> struct SinCosSeries {
 
21
                        static double value() {
 
22
                                return 1 - sqr(A * M_PI / B) / M / (M+1) * SinCosSeries<M + 2, N, B, A>::value();
 
23
                        }
 
24
                };
 
25
                template <unsigned N, unsigned B, unsigned A> struct SinCosSeries<N, N, B, A> {
 
26
                        static double value() { return 1.0; }
 
27
                };
 
28
 
 
29
                template <unsigned A, unsigned B> struct Sin {
 
30
                        static double value() { return (A * M_PI / B) * SinCosSeries<2, 34, B, A>::value(); }
 
31
                };
 
32
 
 
33
                template <unsigned A, unsigned B> struct Cos {
 
34
                        static double value() { return SinCosSeries<1, 33, B, A>::value(); }
 
35
                };
 
36
                
 
37
                /** Calculate sin(2 pi A / B). **/
 
38
                template <unsigned A, unsigned B> double sin() { return Sin<A, B>::value(); }
 
39
 
 
40
                /** Calculate cos(2 pi A / B). **/
 
41
                template <unsigned A, unsigned B> double cos() { return Cos<A, B>::value(); }
 
42
        }
 
43
        
 
44
        namespace fourier {
 
45
                // Based on the description of Volodymyr Myrnyy in
 
46
                // http://www.dspdesignline.com/showArticle.jhtml?printableArticle=true&articleId=199903272
 
47
                template<unsigned P, typename T> struct DanielsonLanczos {
 
48
                        static void apply(std::complex<T>* data) {
 
49
                                const std::size_t N = 1 << P;
 
50
                                const std::size_t M = N / 2;
 
51
                                // Compute even and odd halves
 
52
                                DanielsonLanczos<P - 1, T>().apply(data);
 
53
                                DanielsonLanczos<P - 1, T>().apply(data + M);
 
54
                                // Combine the results
 
55
                                using math::sqr;
 
56
                                using math::sin;
 
57
                                const std::complex<T> wp(-2.0 * sqr(sin<1, N>()), -sin<2, N>());
 
58
                                std::complex<T> w(1.0);
 
59
                                for (std::size_t i = 0; i < M; ++i) {
 
60
                                        std::complex<T> temp = data[i + M] * w;
 
61
                                        data[M + i] = data[i] - temp;
 
62
                                        data[i] += temp;
 
63
                                        w += w * wp;
 
64
                                }
 
65
                        }
 
66
                };
 
67
 
 
68
                template<typename T> struct DanielsonLanczos<0, T> { static void apply(std::complex<T>*) {} };
 
69
        }
 
70
 
 
71
        /** Perform FFT on data. **/
 
72
        template<unsigned P, typename T> void fft(std::complex<T>* data) {
 
73
                // Perform bit-reversal sorting of sample data.
 
74
                const std::size_t N = 1 << P;
 
75
                std::size_t j = 0;
 
76
                for (std::size_t i = 0; i < N; ++i) {
 
77
                        if (i < j) std::swap(data[i], data[j]);
 
78
                        std::size_t m = N / 2;
 
79
                        while (m > 1 && m <= j) { j -= m; m >>= 1; }
 
80
                        j += m;
 
81
                }
 
82
                // Do the actual calculation
 
83
                fourier::DanielsonLanczos<P, T>::apply(data);
 
84
        }
 
85
 
 
86
        /** Perform FFT on data from floating point iterator, windowing the input. **/
 
87
        template<unsigned P, typename InIt, typename Window> std::vector<std::complex<float> > fft(InIt begin, Window window) {
 
88
                std::vector<std::complex<float> > data(1 << P);
 
89
                // Perform bit-reversal sorting of sample data.
 
90
                const std::size_t N = 1 << P;
 
91
                std::size_t j = 0;
 
92
                for (std::size_t i = 0; i < N; ++i) {
 
93
                        data[j] = *begin++ * window[i];
 
94
                        std::size_t m = N / 2;
 
95
                        while (m > 1 && m <= j) { j -= m; m >>= 1; }
 
96
                        j += m;
 
97
                }
 
98
                // Do the actual calculation
 
99
                fourier::DanielsonLanczos<P, float>::apply(&data[0]);
 
100
                return data;
 
101
        }
 
102
 
 
103
}
 
104
 
 
105
#endif
 
106