1 /* ScummVM - Graphic Adventure Engine
2 *
3 * ScummVM is the legal property of its developers, whose names
4 * are too numerous to list here. Please refer to the COPYRIGHT
5 * file distributed with this source distribution.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 *
21 */
22
23 // Based on eos' (I)RDFT code which is in turn
24 // Based upon the (I)DCT code in FFmpeg
25 // Copyright (c) 2009 Peter Ross <pross@xvid.org>
26 // Copyright (c) 2010 Alex Converse <alex.converse@gmail.com>
27 // Copyright (c) 2010 Vitor Sessak
28
29 #include "common/dct.h"
30
31 namespace Common {
32
DCT(int bits,TransformType trans)33 DCT::DCT(int bits, TransformType trans) : _bits(bits), _cos(1 << (_bits + 2) ), _trans(trans), _rdft(nullptr) {
34 int n = 1 << _bits;
35
36 _tCos = _cos.getTable();
37
38 _csc2 = new float[n / 2];
39
40 _rdft = new RDFT(_bits, (_trans == DCT_III) ? RDFT::IDFT_C2R : RDFT::DFT_R2C);
41
42 for (int i = 0; i < (n / 2); i++)
43 _csc2[i] = 0.5 / sin((M_PI / (2 * n) * (2 * i + 1)));
44 }
45
~DCT()46 DCT::~DCT() {
47 delete _rdft;
48 delete[] _csc2;
49 }
50
calc(float * data)51 void DCT::calc(float *data) {
52 switch (_trans) {
53 case DCT_I:
54 calcDCTI(data);
55 break;
56 case DCT_II:
57 calcDCTII(data);
58 break;
59 case DCT_III:
60 calcDCTIII(data);
61 break;
62 case DST_I:
63 calcDSTI(data);
64 break;
65 }
66 }
67
68 /* sin((M_PI * x / (2*n)) */
69 #define SIN(n,x) (_tCos[(n) - (x)])
70 /* cos((M_PI * x / (2*n)) */
71 #define COS(n,x) (_tCos[x])
72
calcDCTI(float * data)73 void DCT::calcDCTI(float *data) {
74 int n = 1 << _bits;
75
76 float next = -0.5f * (data[0] - data[n]);
77
78 for (int i = 0; i < (n / 2); i++) {
79 float tmp1 = data[i ];
80 float tmp2 = data[n - i];
81
82 float s = SIN(n, 2 * i);
83 float c = COS(n, 2 * i);
84
85 c *= tmp1 - tmp2;
86 s *= tmp1 - tmp2;
87
88 next += c;
89
90 tmp1 = (tmp1 + tmp2) * 0.5f;
91
92 data[i ] = tmp1 - s;
93 data[n - i] = tmp1 + s;
94 }
95
96 _rdft->calc(data);
97
98 data[n] = data[1];
99 data[1] = next;
100
101 for (int i = 3; i <= n; i += 2)
102 data[i] = data[i - 2] - data[i];
103 }
104
calcDCTII(float * data)105 void DCT::calcDCTII(float *data) {
106 int n = 1 << _bits;
107
108 for (int i = 0; i < (n / 2); i++) {
109 float tmp1 = data[i ];
110 float tmp2 = data[n - i - 1];
111
112 float s = SIN(n, 2 * i + 1);
113
114 s *= tmp1 - tmp2;
115
116 tmp1 = (tmp1 + tmp2) * 0.5f;
117
118 data[i ] = tmp1 + s;
119 data[n - i - 1] = tmp1 - s;
120 }
121
122 _rdft->calc(data);
123
124 float next = data[1] * 0.5f;
125
126 data[1] *= -1;
127
128 for (int i = n - 2; i >= 0; i -= 2) {
129 float inr = data[i ];
130 float ini = data[i + 1];
131
132 float c = COS(n, i);
133 float s = SIN(n, i);
134
135 data[i ] = c * inr + s * ini;
136 data[i + 1] = next;
137
138 next += s * inr - c * ini;
139 }
140 }
141
calcDCTIII(float * data)142 void DCT::calcDCTIII(float *data) {
143 int n = 1 << _bits;
144
145 float next = data[n - 1];
146 float inv_n = 1.0f / n;
147
148 for (int i = n - 2; i >= 2; i -= 2) {
149 float val1 = data[i ];
150 float val2 = data[i - 1] - data[i + 1];
151
152 float c = COS(n, i);
153 float s = SIN(n, i);
154
155 data[i ] = c * val1 + s * val2;
156 data[i + 1] = s * val1 - c * val2;
157 }
158
159 data[1] = 2 * next;
160
161 _rdft->calc(data);
162
163 for (int i = 0; i < (n / 2); i++) {
164 float tmp1 = data[i ] * inv_n;
165 float tmp2 = data[n - i - 1] * inv_n;
166
167 float csc = _csc2[i] * (tmp1 - tmp2);
168
169 tmp1 += tmp2;
170
171 data[i ] = tmp1 + csc;
172 data[n - i - 1] = tmp1 - csc;
173 }
174 }
175
calcDSTI(float * data)176 void DCT::calcDSTI(float *data) {
177 int n = 1 << _bits;
178
179 data[0] = 0;
180
181 for (int i = 1; i < (n / 2); i++) {
182 float tmp1 = data[i ];
183 float tmp2 = data[n - i];
184 float s = SIN(n, 2 * i);
185
186 s *= tmp1 + tmp2;
187 tmp1 = (tmp1 - tmp2) * 0.5f;
188
189 data[i ] = s + tmp1;
190 data[n - i] = s - tmp1;
191 }
192
193 data[n / 2] *= 2;
194
195 _rdft->calc(data);
196
197 data[0] *= 0.5f;
198
199 for (int i = 1; i < (n - 2); i += 2) {
200 data[i + 1] += data[i - 1];
201 data[i ] = -data[i + 2];
202 }
203
204 data[n - 1] = 0;
205 }
206
207 } // End of namespace Common
208