Upgrade AudioRendererAlgorithm to use WSOLA,

media/filters/audio_renderer_algorithm_unittest.cc

Index: media/filters/audio_renderer_algorithm_unittest.cc
diff --git a/media/filters/audio_renderer_algorithm_unittest.cc b/media/filters/audio_renderer_algorithm_unittest.cc
index d5119c00c2b116022f095c868bd059b7f5d67a5b..102533ad70bab3803692196bff27a8ad91cc8229 100644
--- a/media/filters/audio_renderer_algorithm_unittest.cc
+++ b/media/filters/audio_renderer_algorithm_unittest.cc
@@ -8,23 +8,57 @@
 // correct rate.  We always pass in a very large destination buffer with the
 // expectation that FillBuffer() will fill as much as it can but no more.
 
+#include <algorithm>  // For std::min().
 #include <cmath>
 
 #include "base/bind.h"
 #include "base/callback.h"
+#include "base/memory/scoped_ptr.h"
 #include "media/base/audio_buffer.h"
 #include "media/base/audio_bus.h"
 #include "media/base/buffers.h"
 #include "media/base/channel_layout.h"
 #include "media/base/test_helpers.h"
 #include "media/filters/audio_renderer_algorithm.h"
+#include "media/filters/wsola_internals.h"
 #include "testing/gtest/include/gtest/gtest.h"
-
 namespace media {
 
 static const int kFrameSize = 250;
 static const int kSamplesPerSecond = 3000;
 static const SampleFormat kSampleFormat = kSampleFormatS16;
+static const int kOutputDurationInSec = 10;

[DaleCurtis, 2013/08/13 21:11:04]

As mentioned below, these tests are traditionally very slow w/o good reason. 
You should run this under valgrind and see how long it takes to run.  If it's
more than 10 or 15 seconds for all the tests, it's too long.

[turaj, 2013/08/16 22:13:56]

I run WSOLA for 4 seconds, if that results in too long test we can always reduce
iterations.

On 2013/08/13 21:11:04, DaleCurtis wrote:

+
+static void FillWithSquarePulseTrain(
+    int half_pulse_width, int offset, int channel, AudioBus* audio_bus) {
+  ASSERT_GE(offset, 0);
+  ASSERT_LT(offset, audio_bus->frames());
+
+  float* ch = audio_bus->channel(channel);
+
+  // Fill backward from |offset| - 1 toward zero, starting with -1, alternating
+  // between -1 and 1 every |pulse_width| samples.
+  float pulse = -1.0f;
+  for (int n = offset - 1, k = 0; n >= 0; --n, ++k) {
+    if (k >= half_pulse_width) {
+      pulse = -pulse;
+      k = 0;
+    }
+    ch[n] = pulse;
+  }
+
+  // Fill forward from |offset| towards the end, starting with 1, alternating
+  // between 1 and -1 every |pulse_width| samples.
+  pulse = 1.0f;
+  for (int n = offset, k = 0; n < audio_bus->frames(); ++n, ++k) {
+    if (k >= half_pulse_width) {
+      pulse = -pulse;
+      k = 0;
+    }
+    ch[n] = pulse;
+  }
+}
+
 
 class AudioRendererAlgorithmTest : public testing::Test {
  public:
@@ -118,7 +152,8 @@ class AudioRendererAlgorithmTest : public testing::Test {
 
   void TestPlaybackRate(double playback_rate) {
     const int kDefaultBufferSize = algorithm_.samples_per_second() / 100;
-    const int kDefaultFramesRequested = 2 * algorithm_.samples_per_second();
+    const int kDefaultFramesRequested = kOutputDurationInSec *
+        algorithm_.samples_per_second();
 
     TestPlaybackRate(
         playback_rate, kDefaultBufferSize, kDefaultFramesRequested);
@@ -175,6 +210,89 @@ class AudioRendererAlgorithmTest : public testing::Test {
     EXPECT_NEAR(playback_rate, actual_playback_rate, playback_rate / 100.0);
   }
 
+  void WsolaTest(float playback_rate) {
+    const int kSampleRateHz = 48000;
+    const media::ChannelLayout kChannelLayout = CHANNEL_LAYOUT_STEREO;
+    const int kBytesPerSample = 2;
+    const int kNumFrames = kSampleRateHz / 100;  // 10 milliseconds.
+
+    channels_ = ChannelLayoutToChannelCount(kChannelLayout);
+    AudioParameters params(AudioParameters::AUDIO_PCM_LINEAR, kChannelLayout,
+                           kSampleRateHz, kBytesPerSample * 8, kNumFrames);
+    algorithm_.Initialize(playback_rate, params);
+
+    // A pulse is 6 milliseconds (even number of samples).
+    const int kPulseWidthSamples = 6 * kSampleRateHz / 1000;
+    const int kHalfPulseWidthSamples = kPulseWidthSamples / 2;
+
+    // For the ease of implementation get 1 frame every call to FillBuffer().
+    scoped_ptr<AudioBus> output = AudioBus::Create(channels_, 1);
+
+    scoped_ptr<AudioBus> ref =
+        AudioBus::Create(channels_, kPulseWidthSamples);
+
+    FillWithSquarePulseTrain(kHalfPulseWidthSamples, 0, 0, ref.get());
+    FillWithSquarePulseTrain(kHalfPulseWidthSamples, kHalfPulseWidthSamples, 1,
+                             ref.get());
+
+    const int all_channels_samples = channels_ * kPulseWidthSamples;
+    scoped_ptr<int16_t[]> ref_memory_buffer(new int16_t[all_channels_samples]);
+    uint8_t* pp[] = { reinterpret_cast<uint8_t*>(ref_memory_buffer.get()) };
+
+    ref->ToInterleaved(kPulseWidthSamples, sizeof(*(ref_memory_buffer.get())),

[DaleCurtis, 2013/08/13 21:11:04]

Is it necessary to convert to int16? The AudioBuffer can take float samples.

[turaj, 2013/08/16 22:13:56]

I looked at the implementation of AudioBus::ToInterleaved (|ref| is audio bus
not AudioBuffer) and it seems that float is not supported.

On 2013/08/13 21:11:04, DaleCurtis wrote:

[DaleCurtis, 2013/08/19 22:15:23]

Do you need the data to be interleaved?  It seems like you are creating float
data, interleaving it to int16, passing it to AudioRendererAlgorithm which
converts it back to float upon FillBuffer(), then converting the result back to
int16 for your final comparison.  At the very least it seems like you could just
pass in the float data directly in the beginning, no?  I also don't see why you
couldn't do the comparison in float after the fact either.

[turaj, 2013/08/21 01:01:19]

I believe I have a better solution.

On 2013/08/19 22:15:23, DaleCurtis wrote:

+                       ref_memory_buffer.get());
+
+    base::TimeDelta timestamp = base::TimeDelta::FromInternalValue(0);

[DaleCurtis, 2013/08/13 21:11:04]

const these two.

[turaj, 2013/08/16 22:13:56]

Done.

+    base::TimeDelta duration = base::TimeDelta::FromInternalValue(5000);
+
+    // |input| has a whole pulse, therefore, we can inject it
+    // into |algorithm_| multiple of times to create a periodic input.
+    scoped_refptr<AudioBuffer> input = AudioBuffer::CopyFrom(

[DaleCurtis, 2013/08/13 21:11:04]

Technically you should be able to create an AudioBuffer w/o copying and then a
wrapped AudioBus() using AudioBuffer::writable_data().  These unittests are
usually very slow in valgrind, so avoiding any copies here can be helpful.

I'm investigating whether this works right now though, so don't take my advice
yet :)

[turaj, 2013/08/16 22:13:56]

I guess you are pointing to WrapMemory(), the pain with that is the requirement
of byte-alignment. 

On 2013/08/13 21:11:04, DaleCurtis wrote:

[DaleCurtis, 2013/08/19 22:15:23]

AudioBuffer alignment should take care of this for you.  You should be able to
say AudioBuffer::Create(kSampleFormatPlanarF32, ...), then
AudioBus::CreateWrapper(), for(ch in AudioBuffer) AudioBus::SetChannel(ch,
AudioBuffer::channel_data(ch));

You can then call FillWithSqurePulseTrain() on that AudioBus and the AudioBuffer
will be populated automatically.

[turaj, 2013/08/21 01:01:19]

I guess the current implementation is simpler. Thanks for the tip.

On 2013/08/19 22:15:23, DaleCurtis wrote:

+        kSampleFormatS16, channels_, kPulseWidthSamples, pp, timestamp,
+        duration);
+
+    // Equivalent of 4 seconds.
+    const int kNumRequestedPulses = kSampleRateHz * 4 / kPulseWidthSamples;
+    for (int n = 0; n < kNumRequestedPulses; ++n) {
+      // The output is buffered here until we have a pulse is created. Then
+      // reference file is compared with this buffer.
+      scoped_ptr<AudioBus> out_buffer =

[DaleCurtis, 2013/08/13 21:11:04]

Don't recreate inside loop.  Also what's the difference between out_buffer and
output?  Some better names would be nice :)

[turaj, 2013/08/16 22:13:56]

Done.

+          AudioBus::Create(channels_, kPulseWidthSamples);
+
+      int num_buffered_frames = 0;
+      while (num_buffered_frames < kPulseWidthSamples) {
+        int num_samples = algorithm_.FillBuffer(output.get(), 1);
+        EXPECT_LE(num_samples, 1);
+        if (num_samples > 0) {
+          output->CopyPartialFramesTo(0, num_samples, num_buffered_frames,
+                                      out_buffer.get());
+          num_buffered_frames++;
+        } else {
+          algorithm_.EnqueueBuffer(input);
+        }
+      }
+
+      // Pulses in the first half of WSOLA AOL frame are not constructed

[DaleCurtis, 2013/08/13 21:11:04]

Is this a bug?  Will glitches be heard?

[turaj, 2013/08/16 22:13:56]

No this is not a bug. WSOLA is overlap-and-add based. For the first block, there
is no previous block to add-overlap. The AOL result in a smooth ramp-in for the
first block. 

On 2013/08/13 21:11:04, DaleCurtis wrote:

+      // perfectly. Do not check them.
+      if (n > 3) {
+        scoped_ptr<int16_t[]> test_memory_buffer(

[DaleCurtis, 2013/08/13 21:11:04]

Again, don't allocate inside of the loops.  Allocation is extremely slow
relative to the rest of the operations here.

Also if you can avoid interleaving for comparison that'd be helpful.

[turaj, 2013/08/16 22:13:56]

Done.

+            new int16_t[all_channels_samples]);
+        out_buffer->ToInterleaved(kPulseWidthSamples,
+                                  sizeof(*(test_memory_buffer.get())),
+                                  test_memory_buffer.get());
+
+        // Because of overlap-and-add we might have round off error.
+        for (int k = 0; k < all_channels_samples - 1; ++k) {
+          ASSERT_NEAR(ref_memory_buffer[k], test_memory_buffer[k], 1)
+                  << " loop " << n << " at sample " << k;
+        }
+      }
+
+      // Zero out the buffer to be sure the next comparison is relevant.
+      out_buffer->Zero();
+    }
+  }
+
  protected:
   AudioRendererAlgorithm algorithm_;
   int frames_enqueued_;
@@ -270,7 +388,7 @@ TEST_F(AudioRendererAlgorithmTest, FillBuffer_JumpAroundSpeeds) {
 TEST_F(AudioRendererAlgorithmTest, FillBuffer_SmallBufferSize) {
   Initialize();
   static const int kBufferSizeInFrames = 1;
-  static const int kFramesRequested = 2 * kSamplesPerSecond;
+  static const int kFramesRequested = kOutputDurationInSec * kSamplesPerSecond;
   TestPlaybackRate(1.0, kBufferSizeInFrames, kFramesRequested);
   TestPlaybackRate(0.5, kBufferSizeInFrames, kFramesRequested);
   TestPlaybackRate(1.5, kBufferSizeInFrames, kFramesRequested);
@@ -297,4 +415,185 @@ TEST_F(AudioRendererAlgorithmTest, FillBuffer_HigherQualityAudio) {
   TestPlaybackRate(1.5);
 }
 
+TEST_F(AudioRendererAlgorithmTest, DotProduct) {
+  const int kChannels = 3;
+  const int kFrames = 20;
+  const int kHalfPulseWidth = 2;
+
+  scoped_ptr<AudioBus> a = AudioBus::Create(kChannels, kFrames);
+  scoped_ptr<AudioBus> b = AudioBus::Create(kChannels, kFrames);
+
+  scoped_ptr<float[]> dot_prod(new float[kChannels]);
+
+  FillWithSquarePulseTrain(kHalfPulseWidth, 0, 0, a.get());
+  FillWithSquarePulseTrain(kHalfPulseWidth, 1, 1, a.get());
+  FillWithSquarePulseTrain(kHalfPulseWidth, 2, 2, a.get());
+
+  FillWithSquarePulseTrain(kHalfPulseWidth, 0, 0, b.get());
+  FillWithSquarePulseTrain(kHalfPulseWidth, 0, 1, b.get());
+  FillWithSquarePulseTrain(kHalfPulseWidth, 0, 2, b.get());
+
+  internal::MultiChannelDotProduct(a.get(), 0, b.get(), 0, kFrames,
+                                   dot_prod.get());
+
+  EXPECT_FLOAT_EQ(kFrames, dot_prod[0]);
+  EXPECT_FLOAT_EQ(0, dot_prod[1]);
+  EXPECT_FLOAT_EQ(-kFrames, dot_prod[2]);
+
+  internal::MultiChannelDotProduct(a.get(), 4, b.get(), 8, kFrames / 2,
+                                   dot_prod.get());
+
+  EXPECT_FLOAT_EQ(kFrames / 2, dot_prod[0]);
+  EXPECT_FLOAT_EQ(0, dot_prod[1]);
+  EXPECT_FLOAT_EQ(-kFrames / 2, dot_prod[2]);
+}
+
+TEST_F(AudioRendererAlgorithmTest, MovingBlockEnergy) {
+  const int kChannels = 2;
+  const int kFrames = 20;
+  const int kFramesPerBlock = 3;
+  const int kNumBlocks = kFrames - (kFramesPerBlock - 1);
+  scoped_ptr<AudioBus> a = AudioBus::Create(kChannels, kFrames);
+  scoped_ptr<float[]> energies(new float[kChannels * kNumBlocks]);
+  float* ch_left = a->channel(0);
+  float* ch_right = a->channel(1);
+
+  // Fill up both channels.
+  for (int n = 0; n < kFrames; ++n) {
+    ch_left[n] = n;
+    ch_right[n] = kFrames - 1 - n;
+  }
+
+  internal::MultiChannelMovingBlockEnergies(a.get(), kFramesPerBlock,
+                                            energies.get());
+
+  for (int n = 0; n < kNumBlocks; ++n) {

[DaleCurtis, 2013/08/13 21:11:04]

Comment on what you're testing here.

[turaj, 2013/08/16 22:13:56]

Done.

+    float expected_energy = 0;
+    for (int k = 0; k < kFramesPerBlock; ++k)
+      expected_energy += ch_left[n + k] * ch_left[n + k];
+    EXPECT_FLOAT_EQ(expected_energy, energies[2 * n]);
+
+    expected_energy = 0;
+    for (int k = 0; k < kFramesPerBlock; ++k)
+      expected_energy += ch_right[n + k] * ch_right[n + k];
+    EXPECT_FLOAT_EQ(expected_energy, energies[2 * n + 1]);
+  }
+}
+
+TEST_F(AudioRendererAlgorithmTest, FullAndDecimatedSearch) {
+  const int kFramesInSearchRegion = 12;
+  const int kChannels = 2;
+  float ch_0[] = {0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0};
+  float ch_1[] = {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.1, 1.0, 0.1, 0.0, 0.0};
+  ASSERT_EQ(sizeof(ch_0), sizeof(ch_1));
+  ASSERT_EQ(static_cast<size_t>(kFramesInSearchRegion),
+            sizeof(ch_0) / sizeof(*ch_0));
+  scoped_ptr<AudioBus> search_region = AudioBus::CreateWrapper(kChannels);
+
+  search_region->SetChannelData(0, ch_0);
+  search_region->SetChannelData(1, ch_1);
+  search_region->set_frames(kFramesInSearchRegion);
+  ASSERT_EQ(kFramesInSearchRegion, search_region->frames());
+
+  const int kFramePerBlock = 4;
+  float target_0[] = {1.0, 1.0, 1.0, 0.0};
+  float target_1[] = {0.0, 1.0, 0.1, 1.0};
+  ASSERT_EQ(sizeof(target_0), sizeof(target_1));
+  ASSERT_EQ(static_cast<size_t>(kFramePerBlock),
+            sizeof(target_0) / sizeof(*target_0));
+
+  scoped_ptr<AudioBus> target = AudioBus::CreateWrapper(2);
+  target->SetChannelData(0, target_0);
+  target->SetChannelData(1, target_1);
+  target->set_frames(kFramePerBlock);
+  ASSERT_EQ(kFramePerBlock, target->frames());
+
+  scoped_ptr<float[]> energy_target(new float[kChannels]);
+
+  internal::MultiChannelDotProduct(target.get(), 0, target.get(), 0,
+                                   kFramePerBlock, energy_target.get());
+
+  ASSERT_EQ(3.f, energy_target[0]);
+  ASSERT_EQ(2.01f, energy_target[1]);
+
+  const int kNumCandidBlocks = kFramesInSearchRegion - (kFramePerBlock - 1);
+  scoped_ptr<float[]> energy_candid_blocks(new float[kNumCandidBlocks *
+                                                     kChannels]);
+
+  internal::MultiChannelMovingBlockEnergies(
+      search_region.get(), kFramePerBlock, energy_candid_blocks.get());
+
+  ASSERT_FLOAT_EQ(0, energy_candid_blocks[0]);

[DaleCurtis, 2013/08/13 21:11:04]

Comments on what's being tested.

[turaj, 2013/08/16 22:13:56]

Done.

+  ASSERT_FLOAT_EQ(0, energy_candid_blocks[2]);
+  ASSERT_FLOAT_EQ(1, energy_candid_blocks[4]);
+  ASSERT_FLOAT_EQ(2, energy_candid_blocks[6]);
+  ASSERT_FLOAT_EQ(3, energy_candid_blocks[8]);
+  ASSERT_FLOAT_EQ(3, energy_candid_blocks[10]);
+  ASSERT_FLOAT_EQ(2, energy_candid_blocks[12]);
+  ASSERT_FLOAT_EQ(1, energy_candid_blocks[14]);
+  ASSERT_FLOAT_EQ(0, energy_candid_blocks[16]);
+
+  ASSERT_FLOAT_EQ(0, energy_candid_blocks[1]);
+  ASSERT_FLOAT_EQ(0, energy_candid_blocks[3]);
+  ASSERT_FLOAT_EQ(0, energy_candid_blocks[5]);
+  ASSERT_FLOAT_EQ(0, energy_candid_blocks[7]);
+  ASSERT_FLOAT_EQ(0.01, energy_candid_blocks[9]);
+  ASSERT_FLOAT_EQ(1.01, energy_candid_blocks[11]);
+  ASSERT_FLOAT_EQ(1.02, energy_candid_blocks[13]);
+  ASSERT_FLOAT_EQ(1.02, energy_candid_blocks[15]);
+  ASSERT_FLOAT_EQ(1.01, energy_candid_blocks[17]);
+
+  // An interval which is of no effect.
+  internal::Interval exclude_interval = std::make_pair(-100, -10);
+  EXPECT_EQ(5, internal::FullSearch(
+      0, kNumCandidBlocks - 1, exclude_interval, target.get(),
+      search_region.get(), energy_target.get(), energy_candid_blocks.get()));
+
+  // Exclude the the best match.
+  exclude_interval = std::make_pair(2, 5);
+  EXPECT_EQ(7, internal::FullSearch(
+      0, kNumCandidBlocks - 1, exclude_interval, target.get(),
+      search_region.get(), energy_target.get(), energy_candid_blocks.get()));
+
+  // An interval which is of no effect.
+  exclude_interval = std::make_pair(-100, -10);
+  EXPECT_EQ(4, internal::DecimatedSearch(
+      4, exclude_interval, target.get(), search_region.get(),
+      energy_target.get(), energy_candid_blocks.get()));
+
+  EXPECT_EQ(5, internal::OptimalIndex(search_region.get(), target.get(),
+                                      exclude_interval));
+}
+
+TEST_F(AudioRendererAlgorithmTest, CubicInterpolation) {
+  // Arbitrary coefficients.
+  const float kA = 0.7;
+  const float kB = 1.2;
+  const float kC = 0.8;
+
+  float y_values[3];
+  y_values[0] = kA - kB + kC;
+  y_values[1] = kC;
+  y_values[2] = kA + kB + kC;
+
+  float extremum;
+  float extremum_value;
+
+  internal::CubicInterpolation(y_values, &extremum, &extremum_value);
+
+  float x_star = -kB / (2.f * kA);
+  float y_star = kA * x_star * x_star + kB * x_star + kC;
+
+  EXPECT_FLOAT_EQ(x_star, extremum);
+  EXPECT_FLOAT_EQ(y_star, extremum_value);
+}
+
+TEST_F(AudioRendererAlgorithmTest, WsolaSlowdown) {
+  WsolaTest(1.6f);
+}
+
+TEST_F(AudioRendererAlgorithmTest, WsolaSpeedup) {
+  WsolaTest(0.6f);
+}
+
 }  // namespace media