avfilter/f_loop: make sure duration of frame is never zero
[ffmpeg.git] / libavfilter / af_atempo.c
1 /*
2  * Copyright (c) 2012 Pavel Koshevoy <pkoshevoy at gmail dot com>
3  *
4  * This file is part of FFmpeg.
5  *
6  * FFmpeg is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Lesser General Public
8  * License as published by the Free Software Foundation; either
9  * version 2.1 of the License, or (at your option) any later version.
10  *
11  * FFmpeg is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with FFmpeg; if not, write to the Free Software
18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19  */
20
21 /**
22  * @file
23  * tempo scaling audio filter -- an implementation of WSOLA algorithm
24  *
25  * Based on MIT licensed yaeAudioTempoFilter.h and yaeAudioFragment.h
26  * from Apprentice Video player by Pavel Koshevoy.
27  * https://sourceforge.net/projects/apprenticevideo/
28  *
29  * An explanation of SOLA algorithm is available at
30  * http://www.surina.net/article/time-and-pitch-scaling.html
31  *
32  * WSOLA is very similar to SOLA, only one major difference exists between
33  * these algorithms.  SOLA shifts audio fragments along the output stream,
34  * where as WSOLA shifts audio fragments along the input stream.
35  *
36  * The advantage of WSOLA algorithm is that the overlap region size is
37  * always the same, therefore the blending function is constant and
38  * can be precomputed.
39  */
40
41 #include <float.h>
42 #include "libavcodec/avfft.h"
43 #include "libavutil/avassert.h"
44 #include "libavutil/avstring.h"
45 #include "libavutil/channel_layout.h"
46 #include "libavutil/eval.h"
47 #include "libavutil/opt.h"
48 #include "libavutil/samplefmt.h"
49 #include "avfilter.h"
50 #include "audio.h"
51 #include "internal.h"
52
53 /**
54  * A fragment of audio waveform
55  */
56 typedef struct AudioFragment {
57     // index of the first sample of this fragment in the overall waveform;
58     // 0: input sample position
59     // 1: output sample position
60     int64_t position[2];
61
62     // original packed multi-channel samples:
63     uint8_t *data;
64
65     // number of samples in this fragment:
66     int nsamples;
67
68     // rDFT transform of the down-mixed mono fragment, used for
69     // fast waveform alignment via correlation in frequency domain:
70     FFTSample *xdat;
71 } AudioFragment;
72
73 /**
74  * Filter state machine states
75  */
76 typedef enum {
77     YAE_LOAD_FRAGMENT,
78     YAE_ADJUST_POSITION,
79     YAE_RELOAD_FRAGMENT,
80     YAE_OUTPUT_OVERLAP_ADD,
81     YAE_FLUSH_OUTPUT,
82 } FilterState;
83
84 /**
85  * Filter state machine
86  */
87 typedef struct ATempoContext {
88     const AVClass *class;
89
90     // ring-buffer of input samples, necessary because some times
91     // input fragment position may be adjusted backwards:
92     uint8_t *buffer;
93
94     // ring-buffer maximum capacity, expressed in sample rate time base:
95     int ring;
96
97     // ring-buffer house keeping:
98     int size;
99     int head;
100     int tail;
101
102     // 0: input sample position corresponding to the ring buffer tail
103     // 1: output sample position
104     int64_t position[2];
105
106     // sample format:
107     enum AVSampleFormat format;
108
109     // number of channels:
110     int channels;
111
112     // row of bytes to skip from one sample to next, across multple channels;
113     // stride = (number-of-channels * bits-per-sample-per-channel) / 8
114     int stride;
115
116     // fragment window size, power-of-two integer:
117     int window;
118
119     // Hann window coefficients, for feathering
120     // (blending) the overlapping fragment region:
121     float *hann;
122
123     // tempo scaling factor:
124     double tempo;
125
126     // a snapshot of previous fragment input and output position values
127     // captured when the tempo scale factor was set most recently:
128     int64_t origin[2];
129
130     // current/previous fragment ring-buffer:
131     AudioFragment frag[2];
132
133     // current fragment index:
134     uint64_t nfrag;
135
136     // current state:
137     FilterState state;
138
139     // for fast correlation calculation in frequency domain:
140     RDFTContext *real_to_complex;
141     RDFTContext *complex_to_real;
142     FFTSample *correlation;
143
144     // for managing AVFilterPad.request_frame and AVFilterPad.filter_frame
145     AVFrame *dst_buffer;
146     uint8_t *dst;
147     uint8_t *dst_end;
148     uint64_t nsamples_in;
149     uint64_t nsamples_out;
150 } ATempoContext;
151
152 #define YAE_ATEMPO_MIN 0.5
153 #define YAE_ATEMPO_MAX 100.0
154
155 #define OFFSET(x) offsetof(ATempoContext, x)
156
157 static const AVOption atempo_options[] = {
158     { "tempo", "set tempo scale factor",
159       OFFSET(tempo), AV_OPT_TYPE_DOUBLE, { .dbl = 1.0 },
160       YAE_ATEMPO_MIN,
161       YAE_ATEMPO_MAX,
162       AV_OPT_FLAG_AUDIO_PARAM | AV_OPT_FLAG_FILTERING_PARAM },
163     { NULL }
164 };
165
166 AVFILTER_DEFINE_CLASS(atempo);
167
168 inline static AudioFragment *yae_curr_frag(ATempoContext *atempo)
169 {
170     return &atempo->frag[atempo->nfrag % 2];
171 }
172
173 inline static AudioFragment *yae_prev_frag(ATempoContext *atempo)
174 {
175     return &atempo->frag[(atempo->nfrag + 1) % 2];
176 }
177
178 /**
179  * Reset filter to initial state, do not deallocate existing local buffers.
180  */
181 static void yae_clear(ATempoContext *atempo)
182 {
183     atempo->size = 0;
184     atempo->head = 0;
185     atempo->tail = 0;
186
187     atempo->nfrag = 0;
188     atempo->state = YAE_LOAD_FRAGMENT;
189
190     atempo->position[0] = 0;
191     atempo->position[1] = 0;
192
193     atempo->origin[0] = 0;
194     atempo->origin[1] = 0;
195
196     atempo->frag[0].position[0] = 0;
197     atempo->frag[0].position[1] = 0;
198     atempo->frag[0].nsamples    = 0;
199
200     atempo->frag[1].position[0] = 0;
201     atempo->frag[1].position[1] = 0;
202     atempo->frag[1].nsamples    = 0;
203
204     // shift left position of 1st fragment by half a window
205     // so that no re-normalization would be required for
206     // the left half of the 1st fragment:
207     atempo->frag[0].position[0] = -(int64_t)(atempo->window / 2);
208     atempo->frag[0].position[1] = -(int64_t)(atempo->window / 2);
209
210     av_frame_free(&atempo->dst_buffer);
211     atempo->dst     = NULL;
212     atempo->dst_end = NULL;
213
214     atempo->nsamples_in       = 0;
215     atempo->nsamples_out      = 0;
216 }
217
218 /**
219  * Reset filter to initial state and deallocate all buffers.
220  */
221 static void yae_release_buffers(ATempoContext *atempo)
222 {
223     yae_clear(atempo);
224
225     av_freep(&atempo->frag[0].data);
226     av_freep(&atempo->frag[1].data);
227     av_freep(&atempo->frag[0].xdat);
228     av_freep(&atempo->frag[1].xdat);
229
230     av_freep(&atempo->buffer);
231     av_freep(&atempo->hann);
232     av_freep(&atempo->correlation);
233
234     av_rdft_end(atempo->real_to_complex);
235     atempo->real_to_complex = NULL;
236
237     av_rdft_end(atempo->complex_to_real);
238     atempo->complex_to_real = NULL;
239 }
240
241 /* av_realloc is not aligned enough; fortunately, the data does not need to
242  * be preserved */
243 #define RE_MALLOC_OR_FAIL(field, field_size)                    \
244     do {                                                        \
245         av_freep(&field);                                       \
246         field = av_malloc(field_size);                          \
247         if (!field) {                                           \
248             yae_release_buffers(atempo);                        \
249             return AVERROR(ENOMEM);                             \
250         }                                                       \
251     } while (0)
252
253 /**
254  * Prepare filter for processing audio data of given format,
255  * sample rate and number of channels.
256  */
257 static int yae_reset(ATempoContext *atempo,
258                      enum AVSampleFormat format,
259                      int sample_rate,
260                      int channels)
261 {
262     const int sample_size = av_get_bytes_per_sample(format);
263     uint32_t nlevels  = 0;
264     uint32_t pot;
265     int i;
266
267     atempo->format   = format;
268     atempo->channels = channels;
269     atempo->stride   = sample_size * channels;
270
271     // pick a segment window size:
272     atempo->window = sample_rate / 24;
273
274     // adjust window size to be a power-of-two integer:
275     nlevels = av_log2(atempo->window);
276     pot = 1 << nlevels;
277     av_assert0(pot <= atempo->window);
278
279     if (pot < atempo->window) {
280         atempo->window = pot * 2;
281         nlevels++;
282     }
283
284     // initialize audio fragment buffers:
285     RE_MALLOC_OR_FAIL(atempo->frag[0].data, atempo->window * atempo->stride);
286     RE_MALLOC_OR_FAIL(atempo->frag[1].data, atempo->window * atempo->stride);
287     RE_MALLOC_OR_FAIL(atempo->frag[0].xdat, atempo->window * sizeof(FFTComplex));
288     RE_MALLOC_OR_FAIL(atempo->frag[1].xdat, atempo->window * sizeof(FFTComplex));
289
290     // initialize rDFT contexts:
291     av_rdft_end(atempo->real_to_complex);
292     atempo->real_to_complex = NULL;
293
294     av_rdft_end(atempo->complex_to_real);
295     atempo->complex_to_real = NULL;
296
297     atempo->real_to_complex = av_rdft_init(nlevels + 1, DFT_R2C);
298     if (!atempo->real_to_complex) {
299         yae_release_buffers(atempo);
300         return AVERROR(ENOMEM);
301     }
302
303     atempo->complex_to_real = av_rdft_init(nlevels + 1, IDFT_C2R);
304     if (!atempo->complex_to_real) {
305         yae_release_buffers(atempo);
306         return AVERROR(ENOMEM);
307     }
308
309     RE_MALLOC_OR_FAIL(atempo->correlation, atempo->window * sizeof(FFTComplex));
310
311     atempo->ring = atempo->window * 3;
312     RE_MALLOC_OR_FAIL(atempo->buffer, atempo->ring * atempo->stride);
313
314     // initialize the Hann window function:
315     RE_MALLOC_OR_FAIL(atempo->hann, atempo->window * sizeof(float));
316
317     for (i = 0; i < atempo->window; i++) {
318         double t = (double)i / (double)(atempo->window - 1);
319         double h = 0.5 * (1.0 - cos(2.0 * M_PI * t));
320         atempo->hann[i] = (float)h;
321     }
322
323     yae_clear(atempo);
324     return 0;
325 }
326
327 static int yae_set_tempo(AVFilterContext *ctx, const char *arg_tempo)
328 {
329     const AudioFragment *prev;
330     ATempoContext *atempo = ctx->priv;
331     char   *tail = NULL;
332     double tempo = av_strtod(arg_tempo, &tail);
333
334     if (tail && *tail) {
335         av_log(ctx, AV_LOG_ERROR, "Invalid tempo value '%s'\n", arg_tempo);
336         return AVERROR(EINVAL);
337     }
338
339     if (tempo < YAE_ATEMPO_MIN || tempo > YAE_ATEMPO_MAX) {
340         av_log(ctx, AV_LOG_ERROR, "Tempo value %f exceeds [%f, %f] range\n",
341                tempo, YAE_ATEMPO_MIN, YAE_ATEMPO_MAX);
342         return AVERROR(EINVAL);
343     }
344
345     prev = yae_prev_frag(atempo);
346     atempo->origin[0] = prev->position[0] + atempo->window / 2;
347     atempo->origin[1] = prev->position[1] + atempo->window / 2;
348     atempo->tempo = tempo;
349     return 0;
350 }
351
352 /**
353  * A helper macro for initializing complex data buffer with scalar data
354  * of a given type.
355  */
356 #define yae_init_xdat(scalar_type, scalar_max)                          \
357     do {                                                                \
358         const uint8_t *src_end = src +                                  \
359             frag->nsamples * atempo->channels * sizeof(scalar_type);    \
360                                                                         \
361         FFTSample *xdat = frag->xdat;                                   \
362         scalar_type tmp;                                                \
363                                                                         \
364         if (atempo->channels == 1) {                                    \
365             for (; src < src_end; xdat++) {                             \
366                 tmp = *(const scalar_type *)src;                        \
367                 src += sizeof(scalar_type);                             \
368                                                                         \
369                 *xdat = (FFTSample)tmp;                                 \
370             }                                                           \
371         } else {                                                        \
372             FFTSample s, max, ti, si;                                   \
373             int i;                                                      \
374                                                                         \
375             for (; src < src_end; xdat++) {                             \
376                 tmp = *(const scalar_type *)src;                        \
377                 src += sizeof(scalar_type);                             \
378                                                                         \
379                 max = (FFTSample)tmp;                                   \
380                 s = FFMIN((FFTSample)scalar_max,                        \
381                           (FFTSample)fabsf(max));                       \
382                                                                         \
383                 for (i = 1; i < atempo->channels; i++) {                \
384                     tmp = *(const scalar_type *)src;                    \
385                     src += sizeof(scalar_type);                         \
386                                                                         \
387                     ti = (FFTSample)tmp;                                \
388                     si = FFMIN((FFTSample)scalar_max,                   \
389                                (FFTSample)fabsf(ti));                   \
390                                                                         \
391                     if (s < si) {                                       \
392                         s   = si;                                       \
393                         max = ti;                                       \
394                     }                                                   \
395                 }                                                       \
396                                                                         \
397                 *xdat = max;                                            \
398             }                                                           \
399         }                                                               \
400     } while (0)
401
402 /**
403  * Initialize complex data buffer of a given audio fragment
404  * with down-mixed mono data of appropriate scalar type.
405  */
406 static void yae_downmix(ATempoContext *atempo, AudioFragment *frag)
407 {
408     // shortcuts:
409     const uint8_t *src = frag->data;
410
411     // init complex data buffer used for FFT and Correlation:
412     memset(frag->xdat, 0, sizeof(FFTComplex) * atempo->window);
413
414     if (atempo->format == AV_SAMPLE_FMT_U8) {
415         yae_init_xdat(uint8_t, 127);
416     } else if (atempo->format == AV_SAMPLE_FMT_S16) {
417         yae_init_xdat(int16_t, 32767);
418     } else if (atempo->format == AV_SAMPLE_FMT_S32) {
419         yae_init_xdat(int, 2147483647);
420     } else if (atempo->format == AV_SAMPLE_FMT_FLT) {
421         yae_init_xdat(float, 1);
422     } else if (atempo->format == AV_SAMPLE_FMT_DBL) {
423         yae_init_xdat(double, 1);
424     }
425 }
426
427 /**
428  * Populate the internal data buffer on as-needed basis.
429  *
430  * @return
431  *   0 if requested data was already available or was successfully loaded,
432  *   AVERROR(EAGAIN) if more input data is required.
433  */
434 static int yae_load_data(ATempoContext *atempo,
435                          const uint8_t **src_ref,
436                          const uint8_t *src_end,
437                          int64_t stop_here)
438 {
439     // shortcut:
440     const uint8_t *src = *src_ref;
441     const int read_size = stop_here - atempo->position[0];
442
443     if (stop_here <= atempo->position[0]) {
444         return 0;
445     }
446
447     // samples are not expected to be skipped, unless tempo is greater than 2:
448     av_assert0(read_size <= atempo->ring || atempo->tempo > 2.0);
449
450     while (atempo->position[0] < stop_here && src < src_end) {
451         int src_samples = (src_end - src) / atempo->stride;
452
453         // load data piece-wise, in order to avoid complicating the logic:
454         int nsamples = FFMIN(read_size, src_samples);
455         int na;
456         int nb;
457
458         nsamples = FFMIN(nsamples, atempo->ring);
459         na = FFMIN(nsamples, atempo->ring - atempo->tail);
460         nb = FFMIN(nsamples - na, atempo->ring);
461
462         if (na) {
463             uint8_t *a = atempo->buffer + atempo->tail * atempo->stride;
464             memcpy(a, src, na * atempo->stride);
465
466             src += na * atempo->stride;
467             atempo->position[0] += na;
468
469             atempo->size = FFMIN(atempo->size + na, atempo->ring);
470             atempo->tail = (atempo->tail + na) % atempo->ring;
471             atempo->head =
472                 atempo->size < atempo->ring ?
473                 atempo->tail - atempo->size :
474                 atempo->tail;
475         }
476
477         if (nb) {
478             uint8_t *b = atempo->buffer;
479             memcpy(b, src, nb * atempo->stride);
480
481             src += nb * atempo->stride;
482             atempo->position[0] += nb;
483
484             atempo->size = FFMIN(atempo->size + nb, atempo->ring);
485             atempo->tail = (atempo->tail + nb) % atempo->ring;
486             atempo->head =
487                 atempo->size < atempo->ring ?
488                 atempo->tail - atempo->size :
489                 atempo->tail;
490         }
491     }
492
493     // pass back the updated source buffer pointer:
494     *src_ref = src;
495
496     // sanity check:
497     av_assert0(atempo->position[0] <= stop_here);
498
499     return atempo->position[0] == stop_here ? 0 : AVERROR(EAGAIN);
500 }
501
502 /**
503  * Populate current audio fragment data buffer.
504  *
505  * @return
506  *   0 when the fragment is ready,
507  *   AVERROR(EAGAIN) if more input data is required.
508  */
509 static int yae_load_frag(ATempoContext *atempo,
510                          const uint8_t **src_ref,
511                          const uint8_t *src_end)
512 {
513     // shortcuts:
514     AudioFragment *frag = yae_curr_frag(atempo);
515     uint8_t *dst;
516     int64_t missing, start, zeros;
517     uint32_t nsamples;
518     const uint8_t *a, *b;
519     int i0, i1, n0, n1, na, nb;
520
521     int64_t stop_here = frag->position[0] + atempo->window;
522     if (src_ref && yae_load_data(atempo, src_ref, src_end, stop_here) != 0) {
523         return AVERROR(EAGAIN);
524     }
525
526     // calculate the number of samples we don't have:
527     missing =
528         stop_here > atempo->position[0] ?
529         stop_here - atempo->position[0] : 0;
530
531     nsamples =
532         missing < (int64_t)atempo->window ?
533         (uint32_t)(atempo->window - missing) : 0;
534
535     // setup the output buffer:
536     frag->nsamples = nsamples;
537     dst = frag->data;
538
539     start = atempo->position[0] - atempo->size;
540     zeros = 0;
541
542     if (frag->position[0] < start) {
543         // what we don't have we substitute with zeros:
544         zeros = FFMIN(start - frag->position[0], (int64_t)nsamples);
545         av_assert0(zeros != nsamples);
546
547         memset(dst, 0, zeros * atempo->stride);
548         dst += zeros * atempo->stride;
549     }
550
551     if (zeros == nsamples) {
552         return 0;
553     }
554
555     // get the remaining data from the ring buffer:
556     na = (atempo->head < atempo->tail ?
557           atempo->tail - atempo->head :
558           atempo->ring - atempo->head);
559
560     nb = atempo->head < atempo->tail ? 0 : atempo->tail;
561
562     // sanity check:
563     av_assert0(nsamples <= zeros + na + nb);
564
565     a = atempo->buffer + atempo->head * atempo->stride;
566     b = atempo->buffer;
567
568     i0 = frag->position[0] + zeros - start;
569     i1 = i0 < na ? 0 : i0 - na;
570
571     n0 = i0 < na ? FFMIN(na - i0, (int)(nsamples - zeros)) : 0;
572     n1 = nsamples - zeros - n0;
573
574     if (n0) {
575         memcpy(dst, a + i0 * atempo->stride, n0 * atempo->stride);
576         dst += n0 * atempo->stride;
577     }
578
579     if (n1) {
580         memcpy(dst, b + i1 * atempo->stride, n1 * atempo->stride);
581     }
582
583     return 0;
584 }
585
586 /**
587  * Prepare for loading next audio fragment.
588  */
589 static void yae_advance_to_next_frag(ATempoContext *atempo)
590 {
591     const double fragment_step = atempo->tempo * (double)(atempo->window / 2);
592
593     const AudioFragment *prev;
594     AudioFragment       *frag;
595
596     atempo->nfrag++;
597     prev = yae_prev_frag(atempo);
598     frag = yae_curr_frag(atempo);
599
600     frag->position[0] = prev->position[0] + (int64_t)fragment_step;
601     frag->position[1] = prev->position[1] + atempo->window / 2;
602     frag->nsamples    = 0;
603 }
604
605 /**
606  * Calculate cross-correlation via rDFT.
607  *
608  * Multiply two vectors of complex numbers (result of real_to_complex rDFT)
609  * and transform back via complex_to_real rDFT.
610  */
611 static void yae_xcorr_via_rdft(FFTSample *xcorr,
612                                RDFTContext *complex_to_real,
613                                const FFTComplex *xa,
614                                const FFTComplex *xb,
615                                const int window)
616 {
617     FFTComplex *xc = (FFTComplex *)xcorr;
618     int i;
619
620     // NOTE: first element requires special care -- Given Y = rDFT(X),
621     // Im(Y[0]) and Im(Y[N/2]) are always zero, therefore av_rdft_calc
622     // stores Re(Y[N/2]) in place of Im(Y[0]).
623
624     xc->re = xa->re * xb->re;
625     xc->im = xa->im * xb->im;
626     xa++;
627     xb++;
628     xc++;
629
630     for (i = 1; i < window; i++, xa++, xb++, xc++) {
631         xc->re = (xa->re * xb->re + xa->im * xb->im);
632         xc->im = (xa->im * xb->re - xa->re * xb->im);
633     }
634
635     // apply inverse rDFT:
636     av_rdft_calc(complex_to_real, xcorr);
637 }
638
639 /**
640  * Calculate alignment offset for given fragment
641  * relative to the previous fragment.
642  *
643  * @return alignment offset of current fragment relative to previous.
644  */
645 static int yae_align(AudioFragment *frag,
646                      const AudioFragment *prev,
647                      const int window,
648                      const int delta_max,
649                      const int drift,
650                      FFTSample *correlation,
651                      RDFTContext *complex_to_real)
652 {
653     int       best_offset = -drift;
654     FFTSample best_metric = -FLT_MAX;
655     FFTSample *xcorr;
656
657     int i0;
658     int i1;
659     int i;
660
661     yae_xcorr_via_rdft(correlation,
662                        complex_to_real,
663                        (const FFTComplex *)prev->xdat,
664                        (const FFTComplex *)frag->xdat,
665                        window);
666
667     // identify search window boundaries:
668     i0 = FFMAX(window / 2 - delta_max - drift, 0);
669     i0 = FFMIN(i0, window);
670
671     i1 = FFMIN(window / 2 + delta_max - drift, window - window / 16);
672     i1 = FFMAX(i1, 0);
673
674     // identify cross-correlation peaks within search window:
675     xcorr = correlation + i0;
676
677     for (i = i0; i < i1; i++, xcorr++) {
678         FFTSample metric = *xcorr;
679
680         // normalize:
681         FFTSample drifti = (FFTSample)(drift + i);
682         metric *= drifti * (FFTSample)(i - i0) * (FFTSample)(i1 - i);
683
684         if (metric > best_metric) {
685             best_metric = metric;
686             best_offset = i - window / 2;
687         }
688     }
689
690     return best_offset;
691 }
692
693 /**
694  * Adjust current fragment position for better alignment
695  * with previous fragment.
696  *
697  * @return alignment correction.
698  */
699 static int yae_adjust_position(ATempoContext *atempo)
700 {
701     const AudioFragment *prev = yae_prev_frag(atempo);
702     AudioFragment       *frag = yae_curr_frag(atempo);
703
704     const double prev_output_position =
705         (double)(prev->position[1] - atempo->origin[1] + atempo->window / 2) *
706         atempo->tempo;
707
708     const double ideal_output_position =
709         (double)(prev->position[0] - atempo->origin[0] + atempo->window / 2);
710
711     const int drift = (int)(prev_output_position - ideal_output_position);
712
713     const int delta_max  = atempo->window / 2;
714     const int correction = yae_align(frag,
715                                      prev,
716                                      atempo->window,
717                                      delta_max,
718                                      drift,
719                                      atempo->correlation,
720                                      atempo->complex_to_real);
721
722     if (correction) {
723         // adjust fragment position:
724         frag->position[0] -= correction;
725
726         // clear so that the fragment can be reloaded:
727         frag->nsamples = 0;
728     }
729
730     return correction;
731 }
732
733 /**
734  * A helper macro for blending the overlap region of previous
735  * and current audio fragment.
736  */
737 #define yae_blend(scalar_type)                                          \
738     do {                                                                \
739         const scalar_type *aaa = (const scalar_type *)a;                \
740         const scalar_type *bbb = (const scalar_type *)b;                \
741                                                                         \
742         scalar_type *out     = (scalar_type *)dst;                      \
743         scalar_type *out_end = (scalar_type *)dst_end;                  \
744         int64_t i;                                                      \
745                                                                         \
746         for (i = 0; i < overlap && out < out_end;                       \
747              i++, atempo->position[1]++, wa++, wb++) {                  \
748             float w0 = *wa;                                             \
749             float w1 = *wb;                                             \
750             int j;                                                      \
751                                                                         \
752             for (j = 0; j < atempo->channels;                           \
753                  j++, aaa++, bbb++, out++) {                            \
754                 float t0 = (float)*aaa;                                 \
755                 float t1 = (float)*bbb;                                 \
756                                                                         \
757                 *out =                                                  \
758                     frag->position[0] + i < 0 ?                         \
759                     *aaa :                                              \
760                     (scalar_type)(t0 * w0 + t1 * w1);                   \
761             }                                                           \
762         }                                                               \
763         dst = (uint8_t *)out;                                           \
764     } while (0)
765
766 /**
767  * Blend the overlap region of previous and current audio fragment
768  * and output the results to the given destination buffer.
769  *
770  * @return
771  *   0 if the overlap region was completely stored in the dst buffer,
772  *   AVERROR(EAGAIN) if more destination buffer space is required.
773  */
774 static int yae_overlap_add(ATempoContext *atempo,
775                            uint8_t **dst_ref,
776                            uint8_t *dst_end)
777 {
778     // shortcuts:
779     const AudioFragment *prev = yae_prev_frag(atempo);
780     const AudioFragment *frag = yae_curr_frag(atempo);
781
782     const int64_t start_here = FFMAX(atempo->position[1],
783                                      frag->position[1]);
784
785     const int64_t stop_here = FFMIN(prev->position[1] + prev->nsamples,
786                                     frag->position[1] + frag->nsamples);
787
788     const int64_t overlap = stop_here - start_here;
789
790     const int64_t ia = start_here - prev->position[1];
791     const int64_t ib = start_here - frag->position[1];
792
793     const float *wa = atempo->hann + ia;
794     const float *wb = atempo->hann + ib;
795
796     const uint8_t *a = prev->data + ia * atempo->stride;
797     const uint8_t *b = frag->data + ib * atempo->stride;
798
799     uint8_t *dst = *dst_ref;
800
801     av_assert0(start_here <= stop_here &&
802                frag->position[1] <= start_here &&
803                overlap <= frag->nsamples);
804
805     if (atempo->format == AV_SAMPLE_FMT_U8) {
806         yae_blend(uint8_t);
807     } else if (atempo->format == AV_SAMPLE_FMT_S16) {
808         yae_blend(int16_t);
809     } else if (atempo->format == AV_SAMPLE_FMT_S32) {
810         yae_blend(int);
811     } else if (atempo->format == AV_SAMPLE_FMT_FLT) {
812         yae_blend(float);
813     } else if (atempo->format == AV_SAMPLE_FMT_DBL) {
814         yae_blend(double);
815     }
816
817     // pass-back the updated destination buffer pointer:
818     *dst_ref = dst;
819
820     return atempo->position[1] == stop_here ? 0 : AVERROR(EAGAIN);
821 }
822
823 /**
824  * Feed as much data to the filter as it is able to consume
825  * and receive as much processed data in the destination buffer
826  * as it is able to produce or store.
827  */
828 static void
829 yae_apply(ATempoContext *atempo,
830           const uint8_t **src_ref,
831           const uint8_t *src_end,
832           uint8_t **dst_ref,
833           uint8_t *dst_end)
834 {
835     while (1) {
836         if (atempo->state == YAE_LOAD_FRAGMENT) {
837             // load additional data for the current fragment:
838             if (yae_load_frag(atempo, src_ref, src_end) != 0) {
839                 break;
840             }
841
842             // down-mix to mono:
843             yae_downmix(atempo, yae_curr_frag(atempo));
844
845             // apply rDFT:
846             av_rdft_calc(atempo->real_to_complex, yae_curr_frag(atempo)->xdat);
847
848             // must load the second fragment before alignment can start:
849             if (!atempo->nfrag) {
850                 yae_advance_to_next_frag(atempo);
851                 continue;
852             }
853
854             atempo->state = YAE_ADJUST_POSITION;
855         }
856
857         if (atempo->state == YAE_ADJUST_POSITION) {
858             // adjust position for better alignment:
859             if (yae_adjust_position(atempo)) {
860                 // reload the fragment at the corrected position, so that the
861                 // Hann window blending would not require normalization:
862                 atempo->state = YAE_RELOAD_FRAGMENT;
863             } else {
864                 atempo->state = YAE_OUTPUT_OVERLAP_ADD;
865             }
866         }
867
868         if (atempo->state == YAE_RELOAD_FRAGMENT) {
869             // load additional data if necessary due to position adjustment:
870             if (yae_load_frag(atempo, src_ref, src_end) != 0) {
871                 break;
872             }
873
874             // down-mix to mono:
875             yae_downmix(atempo, yae_curr_frag(atempo));
876
877             // apply rDFT:
878             av_rdft_calc(atempo->real_to_complex, yae_curr_frag(atempo)->xdat);
879
880             atempo->state = YAE_OUTPUT_OVERLAP_ADD;
881         }
882
883         if (atempo->state == YAE_OUTPUT_OVERLAP_ADD) {
884             // overlap-add and output the result:
885             if (yae_overlap_add(atempo, dst_ref, dst_end) != 0) {
886                 break;
887             }
888
889             // advance to the next fragment, repeat:
890             yae_advance_to_next_frag(atempo);
891             atempo->state = YAE_LOAD_FRAGMENT;
892         }
893     }
894 }
895
896 /**
897  * Flush any buffered data from the filter.
898  *
899  * @return
900  *   0 if all data was completely stored in the dst buffer,
901  *   AVERROR(EAGAIN) if more destination buffer space is required.
902  */
903 static int yae_flush(ATempoContext *atempo,
904                      uint8_t **dst_ref,
905                      uint8_t *dst_end)
906 {
907     AudioFragment *frag = yae_curr_frag(atempo);
908     int64_t overlap_end;
909     int64_t start_here;
910     int64_t stop_here;
911     int64_t offset;
912
913     const uint8_t *src;
914     uint8_t *dst;
915
916     int src_size;
917     int dst_size;
918     int nbytes;
919
920     atempo->state = YAE_FLUSH_OUTPUT;
921
922     if (!atempo->nfrag) {
923         // there is nothing to flush:
924         return 0;
925     }
926
927     if (atempo->position[0] == frag->position[0] + frag->nsamples &&
928         atempo->position[1] == frag->position[1] + frag->nsamples) {
929         // the current fragment is already flushed:
930         return 0;
931     }
932
933     if (frag->position[0] + frag->nsamples < atempo->position[0]) {
934         // finish loading the current (possibly partial) fragment:
935         yae_load_frag(atempo, NULL, NULL);
936
937         if (atempo->nfrag) {
938             // down-mix to mono:
939             yae_downmix(atempo, frag);
940
941             // apply rDFT:
942             av_rdft_calc(atempo->real_to_complex, frag->xdat);
943
944             // align current fragment to previous fragment:
945             if (yae_adjust_position(atempo)) {
946                 // reload the current fragment due to adjusted position:
947                 yae_load_frag(atempo, NULL, NULL);
948             }
949         }
950     }
951
952     // flush the overlap region:
953     overlap_end = frag->position[1] + FFMIN(atempo->window / 2,
954                                             frag->nsamples);
955
956     while (atempo->position[1] < overlap_end) {
957         if (yae_overlap_add(atempo, dst_ref, dst_end) != 0) {
958             return AVERROR(EAGAIN);
959         }
960     }
961
962     // check whether all of the input samples have been consumed:
963     if (frag->position[0] + frag->nsamples < atempo->position[0]) {
964         yae_advance_to_next_frag(atempo);
965         return AVERROR(EAGAIN);
966     }
967
968     // flush the remainder of the current fragment:
969     start_here = FFMAX(atempo->position[1], overlap_end);
970     stop_here  = frag->position[1] + frag->nsamples;
971     offset     = start_here - frag->position[1];
972     av_assert0(start_here <= stop_here && frag->position[1] <= start_here);
973
974     src = frag->data + offset * atempo->stride;
975     dst = (uint8_t *)*dst_ref;
976
977     src_size = (int)(stop_here - start_here) * atempo->stride;
978     dst_size = dst_end - dst;
979     nbytes = FFMIN(src_size, dst_size);
980
981     memcpy(dst, src, nbytes);
982     dst += nbytes;
983
984     atempo->position[1] += (nbytes / atempo->stride);
985
986     // pass-back the updated destination buffer pointer:
987     *dst_ref = (uint8_t *)dst;
988
989     return atempo->position[1] == stop_here ? 0 : AVERROR(EAGAIN);
990 }
991
992 static av_cold int init(AVFilterContext *ctx)
993 {
994     ATempoContext *atempo = ctx->priv;
995     atempo->format = AV_SAMPLE_FMT_NONE;
996     atempo->state  = YAE_LOAD_FRAGMENT;
997     return 0;
998 }
999
1000 static av_cold void uninit(AVFilterContext *ctx)
1001 {
1002     ATempoContext *atempo = ctx->priv;
1003     yae_release_buffers(atempo);
1004 }
1005
1006 static int query_formats(AVFilterContext *ctx)
1007 {
1008     AVFilterChannelLayouts *layouts = NULL;
1009     AVFilterFormats        *formats = NULL;
1010
1011     // WSOLA necessitates an internal sliding window ring buffer
1012     // for incoming audio stream.
1013     //
1014     // Planar sample formats are too cumbersome to store in a ring buffer,
1015     // therefore planar sample formats are not supported.
1016     //
1017     static const enum AVSampleFormat sample_fmts[] = {
1018         AV_SAMPLE_FMT_U8,
1019         AV_SAMPLE_FMT_S16,
1020         AV_SAMPLE_FMT_S32,
1021         AV_SAMPLE_FMT_FLT,
1022         AV_SAMPLE_FMT_DBL,
1023         AV_SAMPLE_FMT_NONE
1024     };
1025     int ret;
1026
1027     layouts = ff_all_channel_counts();
1028     if (!layouts) {
1029         return AVERROR(ENOMEM);
1030     }
1031     ret = ff_set_common_channel_layouts(ctx, layouts);
1032     if (ret < 0)
1033         return ret;
1034
1035     formats = ff_make_format_list(sample_fmts);
1036     if (!formats) {
1037         return AVERROR(ENOMEM);
1038     }
1039     ret = ff_set_common_formats(ctx, formats);
1040     if (ret < 0)
1041         return ret;
1042
1043     formats = ff_all_samplerates();
1044     if (!formats) {
1045         return AVERROR(ENOMEM);
1046     }
1047     return ff_set_common_samplerates(ctx, formats);
1048 }
1049
1050 static int config_props(AVFilterLink *inlink)
1051 {
1052     AVFilterContext  *ctx = inlink->dst;
1053     ATempoContext *atempo = ctx->priv;
1054
1055     enum AVSampleFormat format = inlink->format;
1056     int sample_rate = (int)inlink->sample_rate;
1057
1058     return yae_reset(atempo, format, sample_rate, inlink->channels);
1059 }
1060
1061 static int push_samples(ATempoContext *atempo,
1062                         AVFilterLink *outlink,
1063                         int n_out)
1064 {
1065     int ret;
1066
1067     atempo->dst_buffer->sample_rate = outlink->sample_rate;
1068     atempo->dst_buffer->nb_samples  = n_out;
1069
1070     // adjust the PTS:
1071     atempo->dst_buffer->pts =
1072         av_rescale_q(atempo->nsamples_out,
1073                      (AVRational){ 1, outlink->sample_rate },
1074                      outlink->time_base);
1075
1076     ret = ff_filter_frame(outlink, atempo->dst_buffer);
1077     atempo->dst_buffer = NULL;
1078     atempo->dst        = NULL;
1079     atempo->dst_end    = NULL;
1080     if (ret < 0)
1081         return ret;
1082
1083     atempo->nsamples_out += n_out;
1084     return 0;
1085 }
1086
1087 static int filter_frame(AVFilterLink *inlink, AVFrame *src_buffer)
1088 {
1089     AVFilterContext  *ctx = inlink->dst;
1090     ATempoContext *atempo = ctx->priv;
1091     AVFilterLink *outlink = ctx->outputs[0];
1092
1093     int ret = 0;
1094     int n_in = src_buffer->nb_samples;
1095     int n_out = (int)(0.5 + ((double)n_in) / atempo->tempo);
1096
1097     const uint8_t *src = src_buffer->data[0];
1098     const uint8_t *src_end = src + n_in * atempo->stride;
1099
1100     while (src < src_end) {
1101         if (!atempo->dst_buffer) {
1102             atempo->dst_buffer = ff_get_audio_buffer(outlink, n_out);
1103             if (!atempo->dst_buffer) {
1104                 av_frame_free(&src_buffer);
1105                 return AVERROR(ENOMEM);
1106             }
1107             av_frame_copy_props(atempo->dst_buffer, src_buffer);
1108
1109             atempo->dst = atempo->dst_buffer->data[0];
1110             atempo->dst_end = atempo->dst + n_out * atempo->stride;
1111         }
1112
1113         yae_apply(atempo, &src, src_end, &atempo->dst, atempo->dst_end);
1114
1115         if (atempo->dst == atempo->dst_end) {
1116             int n_samples = ((atempo->dst - atempo->dst_buffer->data[0]) /
1117                              atempo->stride);
1118             ret = push_samples(atempo, outlink, n_samples);
1119             if (ret < 0)
1120                 goto end;
1121         }
1122     }
1123
1124     atempo->nsamples_in += n_in;
1125 end:
1126     av_frame_free(&src_buffer);
1127     return ret;
1128 }
1129
1130 static int request_frame(AVFilterLink *outlink)
1131 {
1132     AVFilterContext  *ctx = outlink->src;
1133     ATempoContext *atempo = ctx->priv;
1134     int ret;
1135
1136     ret = ff_request_frame(ctx->inputs[0]);
1137
1138     if (ret == AVERROR_EOF) {
1139         // flush the filter:
1140         int n_max = atempo->ring;
1141         int n_out;
1142         int err = AVERROR(EAGAIN);
1143
1144         while (err == AVERROR(EAGAIN)) {
1145             if (!atempo->dst_buffer) {
1146                 atempo->dst_buffer = ff_get_audio_buffer(outlink, n_max);
1147                 if (!atempo->dst_buffer)
1148                     return AVERROR(ENOMEM);
1149
1150                 atempo->dst = atempo->dst_buffer->data[0];
1151                 atempo->dst_end = atempo->dst + n_max * atempo->stride;
1152             }
1153
1154             err = yae_flush(atempo, &atempo->dst, atempo->dst_end);
1155
1156             n_out = ((atempo->dst - atempo->dst_buffer->data[0]) /
1157                      atempo->stride);
1158
1159             if (n_out) {
1160                 ret = push_samples(atempo, outlink, n_out);
1161                 if (ret < 0)
1162                     return ret;
1163             }
1164         }
1165
1166         av_frame_free(&atempo->dst_buffer);
1167         atempo->dst     = NULL;
1168         atempo->dst_end = NULL;
1169
1170         return AVERROR_EOF;
1171     }
1172
1173     return ret;
1174 }
1175
1176 static int process_command(AVFilterContext *ctx,
1177                            const char *cmd,
1178                            const char *arg,
1179                            char *res,
1180                            int res_len,
1181                            int flags)
1182 {
1183     return !strcmp(cmd, "tempo") ? yae_set_tempo(ctx, arg) : AVERROR(ENOSYS);
1184 }
1185
1186 static const AVFilterPad atempo_inputs[] = {
1187     {
1188         .name         = "default",
1189         .type         = AVMEDIA_TYPE_AUDIO,
1190         .filter_frame = filter_frame,
1191         .config_props = config_props,
1192     },
1193     { NULL }
1194 };
1195
1196 static const AVFilterPad atempo_outputs[] = {
1197     {
1198         .name          = "default",
1199         .request_frame = request_frame,
1200         .type          = AVMEDIA_TYPE_AUDIO,
1201     },
1202     { NULL }
1203 };
1204
1205 AVFilter ff_af_atempo = {
1206     .name            = "atempo",
1207     .description     = NULL_IF_CONFIG_SMALL("Adjust audio tempo."),
1208     .init            = init,
1209     .uninit          = uninit,
1210     .query_formats   = query_formats,
1211     .process_command = process_command,
1212     .priv_size       = sizeof(ATempoContext),
1213     .priv_class      = &atempo_class,
1214     .inputs          = atempo_inputs,
1215     .outputs         = atempo_outputs,
1216 };