Debian Codegraph @

.cargo/vendor/rustdct/src/mdct/mdct_naive.rs

raw
1 use std::f64;
2
3 use rustfft::Length;
4
5 use crate::common::mdct_error_inplace;
6 use crate::RequiredScratch;
7 use crate::{mdct::Mdct, DctNum};
8
9 /// Naive O(n^2 ) MDCT implementation
10 ///
11 /// This implementation is primarily used to test other MDCT algorithms.
12 ///
13 /// ~~~
14 /// // Computes a naive MDCT of output size 124, using the MP3 window function
15 /// use rustdct::mdct::{Mdct, MdctNaive, window_fn};
16 /// use rustdct::RequiredScratch;
17 ///
18 /// let len = 124;
19 ///
20 /// let dct = MdctNaive::new(len, window_fn::mp3);
21 ///
22 /// let input = vec![0f32; len * 2];
23 /// let (input_a, input_b) = input.split_at(len);
24 /// let mut output = vec![0f32; len];
25 /// let mut scratch = vec![0f32; dct.get_scratch_len()];
26 ///
27 /// dct.process_mdct_with_scratch(input_a, input_b, &mut output, &mut scratch);
28 /// ~~~
29 pub struct MdctNaive<T> {
30 twiddles: Box<[T]>,
31 window: Box<[T]>,
32 }
33
34 impl<T: DctNum> MdctNaive<T> {
35 /// Creates a new MDCT context that will process inputs of length `output_len * 2` and produce
36 /// outputs of length `output_len`
37 ///
38 /// `output_len` must be even.
39 ///
40 /// `window_fn` is a function that takes a `size` and returns a `Vec` containing `size` window values.
41 /// See the [`window_fn`](mdct/window_fn/index.html) module for provided window functions.
42 pub fn new<F>(output_len: usize, window_fn: F) -> Self
43 where
44 F: FnOnce(usize) -> Vec<T>,
45 {
46 assert!(
47 output_len % 2 == 0,
48 "The MDCT len must be even. Got {}",
49 output_len
50 );
51
52 let constant_factor = 0.5f64 * f64::consts::PI / (output_len as f64);
53 let twiddles: Vec<T> = (0..output_len * 4)
54 .map(|i| (constant_factor * (i as f64 + 0.5_f64)).cos())
55 .map(|c| T::from_f64(c).unwrap())
56 .collect();
57
58 let window = window_fn(output_len * 2);
59 assert_eq!(
60 window.len(),
61 output_len * 2,
62 "Window function returned incorrect number of values"
63 );
64
65 Self {
66 twiddles: twiddles.into_boxed_slice(),
67 window: window.into_boxed_slice(),
68 }
69 }
70 }
71
72 impl<T: DctNum> Mdct<T> for MdctNaive<T> {
73 fn process_mdct_with_scratch(
74 &self,
75 input_a: &[T],
76 input_b: &[T],
77 output: &mut [T],
78 scratch: &mut [T],
79 ) {
80 validate_buffers_mdct!(
81 input_a,
82 input_b,
83 output,
84 scratch,
85 self.len(),
86 self.get_scratch_len()
87 );
88
89 let output_len = output.len();
90 let half_output = output.len() / 2;
91
92 for k in 0..output_len {
93 let output_cell = output.get_mut(k).unwrap();
94 *output_cell = T::zero();
95
96 let mut twiddle_index = (half_output + k * (output_len + 1)) % self.twiddles.len();
97 let twiddle_stride = k * 2 + 1;
98
99 for i in 0..input_a.len() {
100 let twiddle = self.twiddles[twiddle_index];
101
102 *output_cell = *output_cell + input_a[i] * self.window[i] * twiddle;
103
104 twiddle_index += twiddle_stride;
105 if twiddle_index >= self.twiddles.len() {
106 twiddle_index -= self.twiddles.len();
107 }
108 }
109
110 for i in 0..input_b.len() {
111 let twiddle = self.twiddles[twiddle_index];
112
113 *output_cell = *output_cell + input_b[i] * self.window[i + output_len] * twiddle;
114
115 twiddle_index += twiddle_stride;
116 if twiddle_index >= self.twiddles.len() {
117 twiddle_index -= self.twiddles.len();
118 }
119 }
120 }
121 }
122 fn process_imdct_with_scratch(
123 &self,
124 input: &[T],
125 output_a: &mut [T],
126 output_b: &mut [T],
127 scratch: &mut [T],
128 ) {
129 validate_buffers_mdct!(
130 input,
131 output_a,
132 output_b,
133 scratch,
134 self.len(),
135 self.get_scratch_len()
136 );
137
138 let input_len = input.len();
139 let half_input = input_len / 2;
140
141 for k in 0..input_len {
142 let mut output_val = T::zero();
143
144 let mut twiddle_index = half_input + k;
145 let twiddle_stride = input_len + k * 2 + 1;
146
147 for i in 0..input.len() {
148 let twiddle = self.twiddles[twiddle_index];
149
150 output_val = output_val + input[i] * twiddle;
151
152 twiddle_index += twiddle_stride;
153 if twiddle_index >= self.twiddles.len() {
154 twiddle_index -= self.twiddles.len();
155 }
156 }
157 output_a[k] = output_a[k] + output_val * self.window[k];
158 }
159
160 for k in 0..input_len {
161 let mut output_val = T::zero();
162
163 let twiddle_k = if k < input_len / 2 {
164 k
165 } else {
166 input_len - k - 1
167 };
168
169 let mut twiddle_index =
170 self.twiddles.len() - input_len * 2 + half_input - twiddle_k - 1;
171 let twiddle_stride = input_len - 1 - twiddle_k * 2;
172
173 for i in 0..input.len() {
174 let twiddle = self.twiddles[twiddle_index];
175
176 output_val = output_val + input[i] * twiddle;
177
178 twiddle_index += twiddle_stride;
179 if twiddle_index >= self.twiddles.len() {
180 twiddle_index -= self.twiddles.len();
181 }
182 }
183 output_b[k] = output_b[k] + output_val * self.window[k + input_len];
184 }
185 }
186 }
187 impl<T> Length for MdctNaive<T> {
188 fn len(&self) -> usize {
189 self.twiddles.len() / 4
190 }
191 }
192 impl<T> RequiredScratch for MdctNaive<T> {
193 fn get_scratch_len(&self) -> usize {
194 0
195 }
196 }
197
198 #[cfg(test)]
199 mod unit_tests {
200 use super::*;
201 use crate::mdct::window_fn;
202 use std::f32;
203
204 use crate::test_utils::{compare_float_vectors, random_signal};
205
206 /// Verify our naive implementation against some known values
207 #[test]
208 fn test_known_values_mdct() {
209 let input_list = vec![
210 vec![0_f32, 0_f32, 0_f32, 0_f32],
211 vec![1_f32, 1_f32, -5_f32, 5_f32],
212 vec![7_f32, 3_f32, 8_f32, 4_f32, -1_f32, 3_f32, 0_f32, 4_f32],
213 vec![
214 7_f32, 3_f32, 8_f32, 4_f32, -1_f32, 3_f32, 0_f32, 4_f32, 1f32, 1f32, 1f32, 1f32,
215 ],
216 ];
217 let expected_list = vec![
218 vec![0_f32, 0_f32],
219 vec![0_f32, 0_f32],
220 vec![-4.7455063, -2.073643, -2.2964284, 8.479767],
221 vec![
222 -2.90775651,
223 -12.30026278,
224 6.92661442,
225 2.79403335,
226 3.56420194,
227 -2.40007133,
228 ],
229 ];
230
231 for (input, expected) in input_list.iter().zip(expected_list.iter()) {
232 let output = slow_mdct(&input, window_fn::one);
233
234 assert!(compare_float_vectors(&expected, &output));
235 }
236 }
237
238 /// Verify our naive windowed implementation against some known values
239 #[test]
240 fn test_known_values_windowed_mdct() {
241 let input_list = vec![
242 vec![0_f32, 0_f32, 0_f32, 0_f32],
243 vec![1_f32, 1_f32, -5_f32, 5_f32],
244 vec![7_f32, 3_f32, 8_f32, 4_f32, -1_f32, 3_f32, 0_f32, 4_f32],
245 vec![
246 7_f32, 3_f32, 8_f32, 4_f32, -1_f32, 3_f32, 0_f32, 4_f32, 1f32, 1f32, 1f32, 1f32,
247 ],
248 ];
249 let expected_list = vec![
250 vec![0_f32, 0_f32],
251 vec![2.29289322, 1.53553391],
252 vec![-4.67324308, 3.1647844, -6.22625186, 2.1647844],
253 vec![
254 -5.50153067,
255 -3.46580575,
256 3.79375195,
257 -1.25072987,
258 4.6738204,
259 3.16506351,
260 ],
261 ];
262
263 for (input, expected) in input_list.iter().zip(expected_list.iter()) {
264 let output = slow_mdct(&input, window_fn::mp3);
265
266 assert!(compare_float_vectors(&expected, &output));
267 }
268 }
269
270 /// Verify that our fast implementation of the MDCT gives the same output as the slow version, for many different inputs
271 #[test]
272 fn test_matches_mdct() {
273 for current_window_fn in &[window_fn::one, window_fn::mp3, window_fn::vorbis] {
274 for i in 1..10 {
275 let input_len = i * 4;
276 let output_len = i * 2;
277
278 let input = random_signal(input_len);
279 let (input_a, input_b) = input.split_at(output_len);
280
281 let slow_output = slow_mdct(&input, current_window_fn);
282
283 let mut fast_output = vec![0f32; output_len];
284
285 let dct = MdctNaive::new(output_len, current_window_fn);
286 dct.process_mdct_with_scratch(&input_a, &input_b, &mut fast_output, &mut []);
287
288 println!("{}", output_len);
289 println!("expected: {:?}", slow_output);
290 println!("actual: {:?}", fast_output);
291
292 assert!(
293 compare_float_vectors(&slow_output, &fast_output),
294 "i = {}",
295 i
296 );
297 }
298 }
299 }
300
301 fn slow_mdct<F>(input: &[f32], window_fn: F) -> Vec<f32>
302 where
303 F: Fn(usize) -> Vec<f32>,
304 {
305 let mut output = vec![0f32; input.len() / 2];
306
307 let size_float = output.len() as f32;
308
309 let window = window_fn(input.len());
310 let windowed_input: Vec<f32> = input.iter().zip(window).map(|(i, w)| i * w).collect();
311
312 for k in 0..output.len() {
313 let mut current_value = 0_f32;
314
315 let k_float = k as f32;
316
317 for n in 0..input.len() {
318 let n_float = n as f32;
319
320 let twiddle = (f32::consts::PI
321 * (n_float + 0.5_f32 + size_float * 0.5)
322 * (k_float + 0.5_f32)
323 / size_float)
324 .cos();
325
326 current_value += windowed_input[n] * twiddle;
327 }
328 output[k] = current_value;
329 }
330 output
331 }
332
333 /// Verify our naive implementation against some known values
334 #[test]
335 fn test_known_values_imdct() {
336 let input_list = vec![
337 vec![0f32, 0f32],
338 vec![1f32, 5f32],
339 vec![7f32, 3f32, 8f32, 4f32],
340 vec![7f32, 3f32, 8f32, 4f32, -1f32, 3f32],
341 ];
342 let expected_list = vec![
343 vec![0f32, 0f32, 0f32, 0f32],
344 vec![-4.2367144, 4.2367153, -2.837299, -2.8372989],
345 vec![
346 5.833236, 2.4275358, -2.4275393, -5.833232, 4.8335495, -14.584825, -14.584811,
347 4.8335423,
348 ],
349 vec![
350 2.4138875,
351 8.921771,
352 -2.4359043,
353 2.4359055,
354 -8.921769,
355 -2.4138737,
356 3.1458342,
357 -0.63405657,
358 -18.502512,
359 -18.502502,
360 -0.6340414,
361 3.1458292,
362 ],
363 ];
364
365 for (input, expected) in input_list.iter().zip(expected_list.iter()) {
366 let slow_output = slow_imdct(&input, window_fn::one);
367
368 let mut fast_output = vec![0f32; input.len() * 2];
369 let (fast_output_a, fast_output_b) = fast_output.split_at_mut(input.len());
370
371 let dct = MdctNaive::new(input.len(), window_fn::one);
372 dct.process_imdct_with_scratch(&input, fast_output_a, fast_output_b, &mut []);
373
374 assert!(compare_float_vectors(&expected, &slow_output));
375 assert!(compare_float_vectors(&expected, &fast_output));
376 }
377 }
378
379 /// Verify our naive windowed implementation against some known values
380 #[test]
381 fn test_known_values_windowed_imdct() {
382 let input_list = vec![
383 vec![0f32, 0f32],
384 vec![1_f32, 5_f32],
385 vec![7_f32, 3_f32, 8_f32, 4_f32],
386 vec![7_f32, 3_f32, 8_f32, 4_f32, -1_f32, 3_f32],
387 ];
388 let expected_list = vec![
389 vec![0f32, 0f32, 0f32, 0f32],
390 vec![
391 -1.6213203435596431,
392 3.9142135623730936,
393 -2.6213203435596433,
394 -1.0857864376269069,
395 ],
396 vec![
397 1.1380080486867217,
398 1.3486674811260955,
399 -2.0184235241728627,
400 -5.7211528055198331,
401 4.7406716077536428,
402 -12.126842074178105,
403 -8.1028968193867765,
404 0.94297821246780911,
405 ],
406 vec![
407 0.3150751815802082,
408 3.4142135623730949,
409 -1.4828837895525038,
410 1.9325317795197492,
411 -8.2426406871192732,
412 -2.3932336063055089,
413 3.1189227588735786,
414 -0.58578643762689731,
415 -14.679036212259122,
416 -11.263620643186901,
417 -0.24264068711929426,
418 0.41061397098787894,
419 ],
420 ];
421
422 for (input, expected) in input_list.iter().zip(expected_list.iter()) {
423 let slow_output = slow_imdct(&input, window_fn::mp3);
424
425 let mut fast_output = vec![0f32; input.len() * 2];
426 let (fast_output_a, fast_output_b) = fast_output.split_at_mut(input.len());
427
428 let dct = MdctNaive::new(input.len(), window_fn::mp3);
429 dct.process_imdct_with_scratch(&input, fast_output_a, fast_output_b, &mut []);
430
431 assert!(compare_float_vectors(&expected, &slow_output));
432 assert!(compare_float_vectors(&expected, &fast_output));
433 }
434 }
435
436 /// Verify that our fast implementation of the MDCT gives the same output as the slow version, for many different inputs
437 #[test]
438 fn test_matches_imdct() {
439 for current_window_fn in &[window_fn::one, window_fn::mp3, window_fn::vorbis] {
440 for i in 1..10 {
441 let input_len = i * 2;
442 let output_len = i * 4;
443
444 let input = random_signal(input_len);
445 let slow_output = slow_imdct(&input, current_window_fn);
446
447 let mut fast_output = vec![0f32; output_len];
448 let (fast_output_a, fast_output_b) = fast_output.split_at_mut(input_len);
449
450 let dct = MdctNaive::new(input_len, current_window_fn);
451 dct.process_imdct_with_scratch(&input, fast_output_a, fast_output_b, &mut []);
452
453 assert!(
454 compare_float_vectors(&slow_output, &fast_output),
455 "i = {}",
456 i
457 );
458 }
459 }
460 }
461
462 fn slow_imdct<F>(input: &[f32], window_fn: F) -> Vec<f32>
463 where
464 F: Fn(usize) -> Vec<f32>,
465 {
466 let mut output = vec![0f32; input.len() * 2];
467
468 let size_float = input.len() as f32;
469
470 for n in 0..output.len() {
471 let mut current_value = 0_f32;
472
473 let n_float = n as f32;
474
475 for k in 0..input.len() {
476 let k_float = k as f32;
477
478 let twiddle = (f32::consts::PI
479 * (n_float + 0.5_f32 + size_float * 0.5)
480 * (k_float + 0.5_f32)
481 / size_float)
482 .cos();
483
484 current_value += input[k] * twiddle;
485 }
486 output[n] = current_value;
487 }
488
489 let window = window_fn(output.len());
490 output.iter().zip(window).map(|(e, w)| e * w).collect()
491 }
492 }