Line | Branch | Exec | Source |
---|---|---|---|
1 | /* | ||
2 | * (I)RDFT transforms | ||
3 | * Copyright (c) 2009 Alex Converse <alex dot converse at gmail dot com> | ||
4 | * | ||
5 | * This file is part of FFmpeg. | ||
6 | * | ||
7 | * FFmpeg is free software; you can redistribute it and/or | ||
8 | * modify it under the terms of the GNU Lesser General Public | ||
9 | * License as published by the Free Software Foundation; either | ||
10 | * version 2.1 of the License, or (at your option) any later version. | ||
11 | * | ||
12 | * FFmpeg 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 GNU | ||
15 | * Lesser General Public License for more details. | ||
16 | * | ||
17 | * You should have received a copy of the GNU Lesser General Public | ||
18 | * License along with FFmpeg; if not, write to the Free Software | ||
19 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA | ||
20 | */ | ||
21 | #include <stdlib.h> | ||
22 | #include <math.h> | ||
23 | #include "libavutil/error.h" | ||
24 | #include "libavutil/mathematics.h" | ||
25 | #include "rdft.h" | ||
26 | |||
27 | /** | ||
28 | * @file | ||
29 | * (Inverse) Real Discrete Fourier Transforms. | ||
30 | */ | ||
31 | |||
32 | /** Map one real FFT into two parallel real even and odd FFTs. Then interleave | ||
33 | * the two real FFTs into one complex FFT. Unmangle the results. | ||
34 | * ref: http://www.engineeringproductivitytools.com/stuff/T0001/PT10.HTM | ||
35 | */ | ||
36 | 39298 | static void rdft_calc_c(RDFTContext *s, FFTSample *data) | |
37 | { | ||
38 | int i, i1, i2; | ||
39 | FFTComplex ev, od, odsum; | ||
40 | 39298 | const int n = 1 << s->nbits; | |
41 | 39298 | const float k1 = 0.5; | |
42 | 39298 | const float k2 = 0.5 - s->inverse; | |
43 | 39298 | const FFTSample *tcos = s->tcos; | |
44 | 39298 | const FFTSample *tsin = s->tsin; | |
45 | |||
46 |
2/2✓ Branch 0 taken 28070 times.
✓ Branch 1 taken 11228 times.
|
39298 | if (!s->inverse) { |
47 | 28070 | s->fft.fft_permute(&s->fft, (FFTComplex*)data); | |
48 | 28070 | s->fft.fft_calc(&s->fft, (FFTComplex*)data); | |
49 | } | ||
50 | /* i=0 is a special case because of packing, the DC term is real, so we | ||
51 | are going to throw the N/2 term (also real) in with it. */ | ||
52 | 39298 | ev.re = data[0]; | |
53 | 39298 | data[0] = ev.re+data[1]; | |
54 | 39298 | data[1] = ev.re-data[1]; | |
55 | |||
56 | #define RDFT_UNMANGLE(sign0, sign1) \ | ||
57 | for (i = 1; i < (n>>2); i++) { \ | ||
58 | i1 = 2*i; \ | ||
59 | i2 = n-i1; \ | ||
60 | /* Separate even and odd FFTs */ \ | ||
61 | ev.re = k1*(data[i1 ]+data[i2 ]); \ | ||
62 | od.im = k2*(data[i2 ]-data[i1 ]); \ | ||
63 | ev.im = k1*(data[i1+1]-data[i2+1]); \ | ||
64 | od.re = k2*(data[i1+1]+data[i2+1]); \ | ||
65 | /* Apply twiddle factors to the odd FFT and add to the even FFT */ \ | ||
66 | odsum.re = od.re*tcos[i] sign0 od.im*tsin[i]; \ | ||
67 | odsum.im = od.im*tcos[i] sign1 od.re*tsin[i]; \ | ||
68 | data[i1 ] = ev.re + odsum.re; \ | ||
69 | data[i1+1] = ev.im + odsum.im; \ | ||
70 | data[i2 ] = ev.re - odsum.re; \ | ||
71 | data[i2+1] = odsum.im - ev.im; \ | ||
72 | } | ||
73 | |||
74 |
2/2✓ Branch 0 taken 28070 times.
✓ Branch 1 taken 11228 times.
|
39298 | if (s->negative_sin) { |
75 |
2/2✓ Branch 0 taken 690522 times.
✓ Branch 1 taken 28070 times.
|
718592 | RDFT_UNMANGLE(+,-) |
76 | } else { | ||
77 |
2/2✓ Branch 0 taken 348068 times.
✓ Branch 1 taken 11228 times.
|
359296 | RDFT_UNMANGLE(-,+) |
78 | } | ||
79 | |||
80 | 39298 | data[2*i+1]=s->sign_convention*data[2*i+1]; | |
81 |
2/2✓ Branch 0 taken 11228 times.
✓ Branch 1 taken 28070 times.
|
39298 | if (s->inverse) { |
82 | 11228 | data[0] *= k1; | |
83 | 11228 | data[1] *= k1; | |
84 | 11228 | s->fft.fft_permute(&s->fft, (FFTComplex*)data); | |
85 | 11228 | s->fft.fft_calc(&s->fft, (FFTComplex*)data); | |
86 | } | ||
87 | 39298 | } | |
88 | |||
89 | 32 | av_cold int ff_rdft_init(RDFTContext *s, int nbits, enum RDFTransformType trans) | |
90 | { | ||
91 | 32 | int n = 1 << nbits; | |
92 | int ret; | ||
93 | |||
94 | 32 | s->nbits = nbits; | |
95 |
3/4✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 24 times.
|
32 | s->inverse = trans == IDFT_C2R || trans == DFT_C2R; |
96 |
2/4✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 32 times.
|
32 | s->sign_convention = trans == IDFT_R2C || trans == DFT_C2R ? 1 : -1; |
97 |
3/4✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 8 times.
|
32 | s->negative_sin = trans == DFT_C2R || trans == DFT_R2C; |
98 | |||
99 |
2/4✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 32 times.
|
32 | if (nbits < 4 || nbits > 16) |
100 | ✗ | return AVERROR(EINVAL); | |
101 | |||
102 |
4/6✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 24 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 32 times.
|
32 | if ((ret = ff_fft_init(&s->fft, nbits-1, trans == IDFT_C2R || trans == IDFT_R2C)) < 0) |
103 | ✗ | return ret; | |
104 | |||
105 | 32 | ff_init_ff_cos_tabs(nbits); | |
106 | 32 | s->tcos = ff_cos_tabs[nbits]; | |
107 | 32 | s->tsin = ff_cos_tabs[nbits] + (n >> 2); | |
108 | 32 | s->rdft_calc = rdft_calc_c; | |
109 | |||
110 | #if ARCH_ARM | ||
111 | ff_rdft_init_arm(s); | ||
112 | #endif | ||
113 | |||
114 | 32 | return 0; | |
115 | } | ||
116 | |||
117 | 32 | av_cold void ff_rdft_end(RDFTContext *s) | |
118 | { | ||
119 | 32 | ff_fft_end(&s->fft); | |
120 | 32 | } | |
121 |