From f311a7ee67d459e1033abe7eed4f23f7ada1f537 Mon Sep 17 00:00:00 2001
From: Matthew Hoops
Date: Sat, 2 Jul 2011 15:28:09 -0400
Subject: COMMON: Add RDFT math code
Based on eos' code which is based on FFmpeg's code
---
common/module.mk | 1 +
common/rdft.cpp | 100 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
common/rdft.h | 64 +++++++++++++++++++++++++++++++++++
3 files changed, 165 insertions(+)
create mode 100644 common/rdft.cpp
create mode 100644 common/rdft.h
(limited to 'common')
diff --git a/common/module.mk b/common/module.mk
index 2ab4c113fa..2a50d9d786 100644
--- a/common/module.mk
+++ b/common/module.mk
@@ -24,6 +24,7 @@ MODULE_OBJS := \
quicktime.o \
random.o \
rational.o \
+ rdft.o \
str.o \
stream.o \
system.o \
diff --git a/common/rdft.cpp b/common/rdft.cpp
new file mode 100644
index 0000000000..ca6a9616dd
--- /dev/null
+++ b/common/rdft.cpp
@@ -0,0 +1,100 @@
+/* ScummVM - Graphic Adventure Engine
+ *
+ * ScummVM is the legal property of its developers, whose names
+ * are too numerous to list here. Please refer to the COPYRIGHT
+ * file distributed with this source distribution.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ */
+
+// Based on eos' (I)RDFT code which is in turn
+// Based upon the (I)RDFT code in FFmpeg
+// Copyright (c) 2009 Alex Converse <alex dot converse at gmail dot com>
+
+#include "common/rdft.h"
+
+namespace Common {
+
+RDFT::RDFT(int bits, TransformType trans) : _bits(bits), _fft(0) {
+ assert ((_bits >= 4) && (_bits <= 16));
+
+ _inverse = trans == IDFT_C2R || trans == DFT_C2R;
+ _signConvention = trans == IDFT_R2C || trans == DFT_C2R ? 1 : -1;
+
+ _fft = new FFT(bits - 1, trans == IDFT_C2R || trans == IDFT_R2C);
+
+ int n = 1 << bits;
+
+ _tSin = getSineTable(bits) + (trans == DFT_R2C || trans == DFT_C2R) * (n >> 2);
+ _tCos = getCosineTable(bits);
+}
+
+RDFT::~RDFT() {
+ delete _fft;
+}
+
+void RDFT::calc(float *data) {
+ const int n = 1 << _bits;
+
+ const float k1 = 0.5;
+ const float k2 = 0.5 - _inverse;
+
+ if (!_inverse) {
+ _fft->permute((Complex *) data);
+ _fft->calc ((Complex *) data);
+ }
+
+ Complex ev, od;
+
+ /* i=0 is a special case because of packing, the DC term is real, so we
+ are going to throw the N/2 term (also real) in with it. */
+
+ ev.re = data[0];
+
+ data[0] = ev.re + data[1];
+ data[1] = ev.re - data[1];
+
+ int i;
+ for (i = 1; i < (n >> 2); i++) {
+ int i1 = 2 * i;
+ int i2 = n - i1;
+
+ /* Separate even and odd FFTs */
+ ev.re = k1 * (data[i1 ] + data[i2 ]);
+ od.im = -k2 * (data[i1 ] - data[i2 ]);
+ ev.im = k1 * (data[i1 + 1] - data[i2 + 1]);
+ od.re = k2 * (data[i1 + 1] + data[i2 + 1]);
+
+ /* Apply twiddle factors to the odd FFT and add to the even FFT */
+ data[i1 ] = ev.re + od.re * _tCos[i] - od.im * _tSin[i];
+ data[i1 + 1] = ev.im + od.im * _tCos[i] + od.re * _tSin[i];
+ data[i2 ] = ev.re - od.re * _tCos[i] + od.im * _tSin[i];
+ data[i2 + 1] = -ev.im + od.im * _tCos[i] + od.re * _tSin[i];
+ }
+
+ data[2 * i + 1] = _signConvention * data[2 * i + 1];
+
+ if (_inverse) {
+ data[0] *= k1;
+ data[1] *= k1;
+
+ _fft->permute((Complex *) data);
+ _fft->calc ((Complex *) data);
+ }
+
+}
+
+} // End of namespace Common
diff --git a/common/rdft.h b/common/rdft.h
new file mode 100644
index 0000000000..33fcdd2b3b
--- /dev/null
+++ b/common/rdft.h
@@ -0,0 +1,64 @@
+/* ScummVM - Graphic Adventure Engine
+ *
+ * ScummVM is the legal property of its developers, whose names
+ * are too numerous to list here. Please refer to the COPYRIGHT
+ * file distributed with this source distribution.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ */
+
+// Based on eos' (I)RDFT code which is in turn
+// Based upon the (I)RDFT code in FFmpeg
+// Copyright (c) 2009 Alex Converse <alex dot converse at gmail dot com>
+
+#ifndef COMMON_RDFT_H
+#define COMMON_RDFT_H
+
+#include "common/scummsys.h"
+#include "common/math.h"
+#include "common/fft.h"
+
+namespace Common {
+
+/** (Inverse) Real Discrete Fourier Transform. */
+class RDFT {
+public:
+ enum TransformType {
+ DFT_R2C,
+ IDFT_C2R,
+ IDFT_R2C,
+ DFT_C2R
+ };
+
+ RDFT(int bits, TransformType trans);
+ ~RDFT();
+
+ void calc(float *data);
+
+private:
+ int _bits;
+ int _inverse;
+ int _signConvention;
+
+ const float *_tSin;
+ const float *_tCos;
+
+ FFT *_fft;
+};
+
+} // End of namespace Common
+
+#endif // COMMON_RDFT_H
--
cgit v1.2.3