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