FFmpeg
dct.c
Go to the documentation of this file.
1 /*
2  * (I)DCT Transforms
3  * Copyright (c) 2009 Peter Ross <pross@xvid.org>
4  * Copyright (c) 2010 Alex Converse <alex.converse@gmail.com>
5  * Copyright (c) 2010 Vitor Sessak
6  *
7  * This file is part of FFmpeg.
8  *
9  * FFmpeg is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU Lesser General Public
11  * License as published by the Free Software Foundation; either
12  * version 2.1 of the License, or (at your option) any later version.
13  *
14  * FFmpeg is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17  * Lesser General Public License for more details.
18  *
19  * You should have received a copy of the GNU Lesser General Public
20  * License along with FFmpeg; if not, write to the Free Software
21  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22  */
23 
24 /**
25  * @file
26  * (Inverse) Discrete Cosine Transforms. These are also known as the
27  * type II and type III DCTs respectively.
28  */
29 
30 #include <math.h>
31 #include <string.h>
32 
33 #include "libavutil/error.h"
34 #include "libavutil/mathematics.h"
35 #include "libavutil/mem.h"
36 #include "dct.h"
37 #include "dct32.h"
38 
39 /* sin((M_PI * x / (2 * n)) */
40 #define SIN(s, n, x) (s->costab[(n) - (x)])
41 
42 /* cos((M_PI * x / (2 * n)) */
43 #define COS(s, n, x) (s->costab[x])
44 
46 {
47  int n = 1 << ctx->nbits;
48  int i;
49 
50  data[0] = 0;
51  for (i = 1; i < n / 2; i++) {
52  float tmp1 = data[i ];
53  float tmp2 = data[n - i];
54  float s = SIN(ctx, n, 2 * i);
55 
56  s *= tmp1 + tmp2;
57  tmp1 = (tmp1 - tmp2) * 0.5f;
58  data[i] = s + tmp1;
59  data[n - i] = s - tmp1;
60  }
61 
62  data[n / 2] *= 2;
63  ctx->rdft.rdft_calc(&ctx->rdft, data);
64 
65  data[0] *= 0.5f;
66 
67  for (i = 1; i < n - 2; i += 2) {
68  data[i + 1] += data[i - 1];
69  data[i] = -data[i + 2];
70  }
71 
72  data[n - 1] = 0;
73 }
74 
76 {
77  int n = 1 << ctx->nbits;
78  int i;
79  float next = -0.5f * (data[0] - data[n]);
80 
81  for (i = 0; i < n / 2; i++) {
82  float tmp1 = data[i];
83  float tmp2 = data[n - i];
84  float s = SIN(ctx, n, 2 * i);
85  float c = COS(ctx, n, 2 * i);
86 
87  c *= tmp1 - tmp2;
88  s *= tmp1 - tmp2;
89 
90  next += c;
91 
92  tmp1 = (tmp1 + tmp2) * 0.5f;
93  data[i] = tmp1 - s;
94  data[n - i] = tmp1 + s;
95  }
96 
97  ctx->rdft.rdft_calc(&ctx->rdft, data);
98  data[n] = data[1];
99  data[1] = next;
100 
101  for (i = 3; i <= n; i += 2)
102  data[i] = data[i - 2] - data[i];
103 }
104 
106 {
107  int n = 1 << ctx->nbits;
108  int i;
109 
110  float next = data[n - 1];
111  float inv_n = 1.0f / n;
112 
113  for (i = n - 2; i >= 2; i -= 2) {
114  float val1 = data[i];
115  float val2 = data[i - 1] - data[i + 1];
116  float c = COS(ctx, n, i);
117  float s = SIN(ctx, n, i);
118 
119  data[i] = c * val1 + s * val2;
120  data[i + 1] = s * val1 - c * val2;
121  }
122 
123  data[1] = 2 * next;
124 
125  ctx->rdft.rdft_calc(&ctx->rdft, data);
126 
127  for (i = 0; i < n / 2; i++) {
128  float tmp1 = data[i] * inv_n;
129  float tmp2 = data[n - i - 1] * inv_n;
130  float csc = ctx->csc2[i] * (tmp1 - tmp2);
131 
132  tmp1 += tmp2;
133  data[i] = tmp1 + csc;
134  data[n - i - 1] = tmp1 - csc;
135  }
136 }
137 
139 {
140  int n = 1 << ctx->nbits;
141  int i;
142  float next;
143 
144  for (i = 0; i < n / 2; i++) {
145  float tmp1 = data[i];
146  float tmp2 = data[n - i - 1];
147  float s = SIN(ctx, n, 2 * i + 1);
148 
149  s *= tmp1 - tmp2;
150  tmp1 = (tmp1 + tmp2) * 0.5f;
151 
152  data[i] = tmp1 + s;
153  data[n-i-1] = tmp1 - s;
154  }
155 
156  ctx->rdft.rdft_calc(&ctx->rdft, data);
157 
158  next = data[1] * 0.5;
159  data[1] *= -1;
160 
161  for (i = n - 2; i >= 0; i -= 2) {
162  float inr = data[i ];
163  float ini = data[i + 1];
164  float c = COS(ctx, n, i);
165  float s = SIN(ctx, n, i);
166 
167  data[i] = c * inr + s * ini;
168  data[i + 1] = next;
169 
170  next += s * inr - c * ini;
171  }
172 }
173 
175 {
176  ctx->dct32(data, data);
177 }
178 
180 {
181  int n = 1 << nbits;
182  int i;
183  int ret;
184 
185  memset(s, 0, sizeof(*s));
186 
187  s->nbits = nbits;
188  s->inverse = inverse;
189 
190  if (inverse == DCT_II && nbits == 5) {
191  s->dct_calc = dct32_func;
192  } else {
193  ff_init_ff_cos_tabs(nbits + 2);
194 
195  s->costab = ff_cos_tabs[nbits + 2];
196  s->csc2 = av_malloc_array(n / 2, sizeof(FFTSample));
197  if (!s->csc2)
198  return AVERROR(ENOMEM);
199 
200  if ((ret = ff_rdft_init(&s->rdft, nbits, inverse == DCT_III)) < 0) {
201  av_freep(&s->csc2);
202  return ret;
203  }
204 
205  for (i = 0; i < n / 2; i++)
206  s->csc2[i] = 0.5 / sin((M_PI / (2 * n) * (2 * i + 1)));
207 
208  switch (inverse) {
209  case DCT_I : s->dct_calc = dct_calc_I_c; break;
210  case DCT_II : s->dct_calc = dct_calc_II_c; break;
211  case DCT_III: s->dct_calc = dct_calc_III_c; break;
212  case DST_I : s->dct_calc = dst_calc_I_c; break;
213  }
214  }
215 
216  s->dct32 = ff_dct32_float;
217 #if ARCH_X86
219 #endif
220 
221  return 0;
222 }
223 
225 {
226  ff_rdft_end(&s->rdft);
227  av_freep(&s->csc2);
228 }
DCT_I
@ DCT_I
Definition: avfft.h:96
ff_init_ff_cos_tabs
#define ff_init_ff_cos_tabs
Definition: fft.h:107
AVERROR
Filter the word “frame” indicates either a video frame or a group of audio as stored in an AVFrame structure Format for each input and each output the list of supported formats For video that means pixel format For audio that means channel sample they are references to shared objects When the negotiation mechanism computes the intersection of the formats supported at each end of a all references to both lists are replaced with a reference to the intersection And when a single format is eventually chosen for a link amongst the remaining all references to the list are updated That means that if a filter requires that its input and output have the same format amongst a supported all it has to do is use a reference to the same list of formats query_formats can leave some formats unset and return AVERROR(EAGAIN) to cause the negotiation mechanism toagain later. That can be used by filters with complex requirements to use the format negotiated on one link to set the formats supported on another. Frame references ownership and permissions
inverse
inverse
Definition: af_crystalizer.c:122
data
const char data[16]
Definition: mxf.c:143
mathematics.h
DCT_III
@ DCT_III
Definition: avfft.h:95
ff_rdft_end
av_cold void ff_rdft_end(RDFTContext *s)
Definition: rdft.c:117
av_cold
#define av_cold
Definition: attributes.h:90
dct.h
dct_calc_I_c
static void dct_calc_I_c(DCTContext *ctx, FFTSample *data)
Definition: dct.c:75
s
#define s(width, name)
Definition: cbs_vp9.c:256
ctx
AVFormatContext * ctx
Definition: movenc.c:48
SIN
#define SIN(s, n, x)
Definition: dct.c:40
dct32_func
static void dct32_func(DCTContext *ctx, FFTSample *data)
Definition: dct.c:174
dct_calc_II_c
static void dct_calc_II_c(DCTContext *ctx, FFTSample *data)
Definition: dct.c:138
dct32.h
FFTSample
float FFTSample
Definition: avfft.h:35
c
Undefined Behavior In the C some operations are like signed integer dereferencing freed accessing outside allocated Undefined Behavior must not occur in a C it is not safe even if the output of undefined operations is unused The unsafety may seem nit picking but Optimizing compilers have in fact optimized code on the assumption that no undefined Behavior occurs Optimizing code based on wrong assumptions can and has in some cases lead to effects beyond the output of computations The signed integer overflow problem in speed critical code Code which is highly optimized and works with signed integers sometimes has the problem that often the output of the computation does not c
Definition: undefined.txt:32
error.h
ff_dct_init_x86
void ff_dct_init_x86(DCTContext *s)
Definition: dct_init.c:28
dst_calc_I_c
static void dst_calc_I_c(DCTContext *ctx, FFTSample *data)
Definition: dct.c:45
f
f
Definition: af_crystalizer.c:122
dct_calc_III_c
static void dct_calc_III_c(DCTContext *ctx, FFTSample *data)
Definition: dct.c:105
ff_dct_end
av_cold void ff_dct_end(DCTContext *s)
Definition: dct.c:224
M_PI
#define M_PI
Definition: mathematics.h:52
DST_I
@ DST_I
Definition: avfft.h:97
ff_rdft_init
av_cold int ff_rdft_init(RDFTContext *s, int nbits, enum RDFTransformType trans)
Set up a real FFT.
Definition: rdft.c:89
ff_dct32_float
void ff_dct32_float(float *dst, const float *src)
ff_dct_init
av_cold int ff_dct_init(DCTContext *s, int nbits, enum DCTTransformType inverse)
Set up DCT.
Definition: dct.c:179
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:269
av_malloc_array
#define av_malloc_array(a, b)
Definition: tableprint_vlc.h:31
DCTContext
Definition: dct.h:32
ret
ret
Definition: filter_design.txt:187
COS
#define COS(s, n, x)
Definition: dct.c:43
mem.h
av_freep
#define av_freep(p)
Definition: tableprint_vlc.h:34
DCT_II
@ DCT_II
Definition: avfft.h:94
DCTTransformType
DCTTransformType
Definition: avfft.h:93