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