src/starboard/shared/starboard/player/filter/audio_time_stretcher.cc - cobalt - Git at Google

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.

 // Modifications Copyright 2017 Google Inc. All Rights Reserved.
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
 // You may obtain a copy of the License at
 //
 //     http://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS,
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.

 #include "starboard/shared/starboard/player/filter/audio_time_stretcher.h"

 #include <algorithm>
 #include <cmath>

 #include "starboard/log.h"
 #include "starboard/memory.h"
 #include "starboard/shared/starboard/player/filter/wsola_internal.h"

 namespace starboard {
 namespace shared {
 namespace starboard {
 namespace player {
 namespace filter {

 // Waveform Similarity Overlap-and-add (WSOLA).
 //
 // One WSOLA iteration
 //
 // 1) Extract |target_block_| as input frames at indices
 //    [|target_block_index_|, |target_block_index_| + |ola_window_size_|).
 //    Note that |target_block_| is the "natural" continuation of the output.
 //
 // 2) Extract |search_block_| as input frames at indices
 //    [|search_block_index_|,
 //     |search_block_index_| + |num_candidate_blocks_| + |ola_window_size_|).
 //
 // 3) Find a block within the |search_block_| that is most similar
 //    to |target_block_|. Let |optimal_index| be the index of such block and
 //    write it to |optimal_block_|.
 //
 // 4) Update:
 //    |optimal_block_| = |transition_window_| * |target_block_| +
 //    (1 - |transition_window_|) * |optimal_block_|.
 //
 // 5) Overlap-and-add |optimal_block_| to the |wsola_output_|.
 //
 // 6) Update:
 //    |target_block_| = |optimal_index| + |ola_window_size_| / 2.
 //    |output_index_| = |output_index_| + |ola_window_size_| / 2,
 //    |search_block_center_offset_| = |output_index_| * |playback_rate|, and
 //    |search_block_index_| = |search_block_center_offset_| -
 //        |search_block_center_offset_|.

 // Max/min supported playback rates for fast/slow audio. Audio outside of these
 // ranges are muted.
 // Audio at these speeds would sound better under a frequency domain algorithm.
 static const double kMinPlaybackRate = 0.5;
 static const double kMaxPlaybackRate = 4.0;

 // Overlap-and-add window size in milliseconds.
 static const int kOlaWindowSizeMs = 20;

 // Size of search interval in milliseconds. The search interval is
 // [-delta delta] around |output_index_| * |playback_rate|. So the search
 // interval is 2 * delta.
 static const int kWsolaSearchIntervalMs = 30;

 // The maximum size in seconds for the |audio_buffer_|. Arbitrarily determined.
 static const int kMaxCapacityInSeconds = 3;

 // The minimum size in ms for the |audio_buffer_|. Arbitrarily determined.
 static const int kStartingCapacityInMs = 200;

 AudioTimeStretcher::AudioTimeStretcher()
     : channels_(0),
       bytes_per_frame_(0),
       samples_per_second_(0),
       muted_partial_frame_(0),
       capacity_(0),
       output_time_(0.0),
       search_block_center_offset_(0),
       search_block_index_(0),
       num_candidate_blocks_(0),
       target_block_index_(0),
       ola_window_size_(0),
       ola_hop_size_(0),
       num_complete_frames_(0),
       initial_capacity_(0),
       max_capacity_(0) {}

 AudioTimeStretcher::~AudioTimeStretcher() {}

 void AudioTimeStretcher::Initialize(int channels, int samples_per_second) {
   channels_ = channels;
   bytes_per_frame_ = sizeof(float) * channels_;
   samples_per_second_ = samples_per_second;
   initial_capacity_ = capacity_ =
       ConvertMillisecondsToFrames(kStartingCapacityInMs);
   max_capacity_ =
       std::max(initial_capacity_, kMaxCapacityInSeconds * samples_per_second_);
   num_candidate_blocks_ = ConvertMillisecondsToFrames(kWsolaSearchIntervalMs);
   ola_window_size_ = ConvertMillisecondsToFrames(kOlaWindowSizeMs);

   // Make sure window size in an even number.
   ola_window_size_ += ola_window_size_ & 1;
   ola_hop_size_ = ola_window_size_ / 2;

   // |num_candidate_blocks_| / 2 is the offset of the center of the search
   // block to the center of the first (left most) candidate block. The offset
   // of the center of a candidate block to its left most point is
   // |ola_window_size_| / 2 - 1. Note that |ola_window_size_| is even and in
   // our convention the center belongs to the left half, so we need to subtract
   // one frame to get the correct offset.
   //
   //                             Search Block
   //              <------------------------------------------->
   //
   //   |ola_window_size_| / 2 - 1
   //              <----
   //
   //             |num_candidate_blocks_| / 2
   //                   <----------------
   //                                 center
   //              X----X----------------X---------------X-----X
   //              <---------->                     <---------->
   //                Candidate      ...               Candidate
   //                   1,          ...         |num_candidate_blocks_|
   search_block_center_offset_ =
       num_candidate_blocks_ / 2 + (ola_window_size_ / 2 - 1);

   ola_window_.reset(new float[ola_window_size_]);
   internal::GetSymmetricHanningWindow(ola_window_size_, ola_window_.get());

   transition_window_.reset(new float[ola_window_size_ * 2]);
   internal::GetSymmetricHanningWindow(2 * ola_window_size_,
                                       transition_window_.get());

   wsola_output_ =
       new DecodedAudio(channels_, kSbMediaAudioSampleTypeFloat32,
                        kSbMediaAudioFrameStorageTypeInterleaved, 0,
                        (ola_window_size_ + ola_hop_size_) * bytes_per_frame_);
   // Initialize for overlap-and-add of the first block.
   SbMemorySet(wsola_output_->buffer(), 0, wsola_output_->size());

   // Auxiliary containers.
   optimal_block_ = new DecodedAudio(channels_, kSbMediaAudioSampleTypeFloat32,
                                     kSbMediaAudioFrameStorageTypeInterleaved, 0,
                                     ola_window_size_ * bytes_per_frame_);
   search_block_ = new DecodedAudio(
       channels_, kSbMediaAudioSampleTypeFloat32,
       kSbMediaAudioFrameStorageTypeInterleaved, 0,
       (num_candidate_blocks_ + (ola_window_size_ - 1)) * bytes_per_frame_);
   target_block_ = new DecodedAudio(channels_, kSbMediaAudioSampleTypeFloat32,
                                    kSbMediaAudioFrameStorageTypeInterleaved, 0,
                                    ola_window_size_ * bytes_per_frame_);
 }

 scoped_refptr<DecodedAudio> AudioTimeStretcher::Read(int requested_frames,
                                                      double playback_rate) {
   SB_DCHECK(bytes_per_frame_ > 0);
   SB_DCHECK(playback_rate >= 0);

   scoped_refptr<DecodedAudio> dest =
       new DecodedAudio(channels_, kSbMediaAudioSampleTypeFloat32,
                        kSbMediaAudioFrameStorageTypeInterleaved, 0,
                        requested_frames * bytes_per_frame_);

   if (playback_rate == 0) {
     dest->ShrinkTo(0);
     return dest;
   }

   // Optimize the muted case to issue a single clear instead of performing
   // the full crossfade and clearing each crossfaded frame.
   if (playback_rate < kMinPlaybackRate || playback_rate > kMaxPlaybackRate) {
     int frames_to_render =
         std::min(static_cast<int>(audio_buffer_.frames() / playback_rate),
                  requested_frames);

     // Compute accurate number of frames to actually skip in the source data.
     // Includes the leftover partial frame from last request. However, we can
     // only skip over complete frames, so a partial frame may remain for next
     // time.
     muted_partial_frame_ += frames_to_render * playback_rate;
     // Handle the case where muted_partial_frame_ rounds up to
     // audio_buffer_.frames()+1.
     int seek_frames = std::min(static_cast<int>(muted_partial_frame_),
                                audio_buffer_.frames());
     SbMemorySet(dest->buffer(), 0, frames_to_render * bytes_per_frame_);
     audio_buffer_.SeekFrames(seek_frames);

     // Determine the partial frame that remains to be skipped for next call. If
     // the user switches back to playing, it may be off time by this partial
     // frame, which would be undetectable. If they subsequently switch to
     // another playback rate that mutes, the code will attempt to line up the
     // frames again.
     muted_partial_frame_ -= seek_frames;
     dest->ShrinkTo(frames_to_render * bytes_per_frame_);
     return dest;
   }

   int slower_step = static_cast<int>(ceil(ola_window_size_ * playback_rate));
   int faster_step = static_cast<int>(ceil(ola_window_size_ / playback_rate));

   // Optimize the most common |playback_rate| ~= 1 case to use a single copy
   // instead of copying frame by frame.
   if (ola_window_size_ <= faster_step && slower_step >= ola_window_size_) {
     const int frames_to_copy =
         std::min(audio_buffer_.frames(), requested_frames);
     const int frames_read = audio_buffer_.ReadFrames(frames_to_copy, 0, dest);
     SB_DCHECK(frames_read == frames_to_copy);
     dest->ShrinkTo(frames_read * bytes_per_frame_);
     return dest;
   }

   int rendered_frames = 0;
   do {
     rendered_frames += WriteCompletedFramesTo(
         requested_frames - rendered_frames, rendered_frames, dest);
   } while (rendered_frames < requested_frames &&
            RunOneWsolaIteration(playback_rate));
   dest->ShrinkTo(rendered_frames * bytes_per_frame_);
   return dest;
 }

 void AudioTimeStretcher::FlushBuffers() {
   // Clear the queue of decoded packets (releasing the buffers).
   audio_buffer_.Clear();
   output_time_ = 0.0;
   search_block_index_ = 0;
   target_block_index_ = 0;
   SbMemorySet(wsola_output_->buffer(), 0, wsola_output_->size());
   num_complete_frames_ = 0;

   // Reset |capacity_| so growth triggered by underflows doesn't penalize seek
   // time.
   capacity_ = initial_capacity_;
 }

 void AudioTimeStretcher::EnqueueBuffer(
     const scoped_refptr<DecodedAudio>& audio_data) {
   SB_DCHECK(!audio_data->is_end_of_stream());
   audio_buffer_.Append(audio_data);
 }

 bool AudioTimeStretcher::IsQueueFull() const {
   return audio_buffer_.frames() >= capacity_;
 }

 // TODO: Make order of functions in .cc the same as order of functions in .h.
 bool AudioTimeStretcher::CanPerformWsola() const {
   const int search_block_size = num_candidate_blocks_ + (ola_window_size_ - 1);
   const int frames = audio_buffer_.frames();
   return target_block_index_ + ola_window_size_ <= frames &&
          search_block_index_ + search_block_size <= frames;
 }

 int AudioTimeStretcher::ConvertMillisecondsToFrames(int ms) const {
   const double kMillsecondsPerSeconds =
       static_cast<double>(kSbTimeSecond / kSbTimeMillisecond);
   return static_cast<int>(ms * (samples_per_second_ / kMillsecondsPerSeconds));
 }

 bool AudioTimeStretcher::RunOneWsolaIteration(double playback_rate) {
   SB_DCHECK(bytes_per_frame_ > 0);

   if (!CanPerformWsola()) return false;

   GetOptimalBlock();

   // Overlap-and-add.
   for (int k = 0; k < channels_; ++k) {
     const float* const ch_opt_frame =
         reinterpret_cast<const float*>(optimal_block_->buffer()) + k;
     float* ch_output = reinterpret_cast<float*>(wsola_output_->buffer()) + k +
                        num_complete_frames_ * sizeof(float);
     for (int n = 0; n < ola_hop_size_; ++n) {
       ch_output[n * channels_] =
           ch_output[n * channels_] * ola_window_[ola_hop_size_ + n] +
           ch_opt_frame[n * channels_] * ola_window_[n];
     }
   }
   // Copy the second half to the output.
   const float* const ch_opt_frame =
       reinterpret_cast<const float*>(optimal_block_->buffer());
   float* ch_output = reinterpret_cast<float*>(wsola_output_->buffer()) +
                      num_complete_frames_ * sizeof(float);
   SbMemoryCopy(&ch_output[ola_hop_size_ * channels_],
                &ch_opt_frame[ola_hop_size_ * channels_],
                sizeof(*ch_opt_frame) * ola_hop_size_ * channels_);

   num_complete_frames_ += ola_hop_size_;
   UpdateOutputTime(playback_rate, ola_hop_size_);
   RemoveOldInputFrames(playback_rate);
   return true;
 }

 void AudioTimeStretcher::UpdateOutputTime(double playback_rate,
                                           double time_change) {
   output_time_ += time_change;
   // Center of the search region, in frames.
   const int search_block_center_index =
       static_cast<int>(output_time_ * playback_rate + 0.5);
   search_block_index_ = search_block_center_index - search_block_center_offset_;
 }

 void AudioTimeStretcher::RemoveOldInputFrames(double playback_rate) {
   const int earliest_used_index =
       std::min(target_block_index_, search_block_index_);
   if (earliest_used_index <= 0) return;  // Nothing to remove.

   // Remove frames from input and adjust indices accordingly.
   audio_buffer_.SeekFrames(earliest_used_index);
   target_block_index_ -= earliest_used_index;

   // Adjust output index.
   double output_time_change =
       static_cast<double>(earliest_used_index) / playback_rate;
   SB_CHECK(output_time_ >= output_time_change);
   UpdateOutputTime(playback_rate, -output_time_change);
 }

 int AudioTimeStretcher::WriteCompletedFramesTo(int requested_frames,
                                                int dest_offset,
                                                DecodedAudio* dest) {
   SB_DCHECK(bytes_per_frame_ > 0);

   int rendered_frames = std::min(num_complete_frames_, requested_frames);

   if (rendered_frames == 0)
     return 0;  // There is nothing to read from |wsola_output_|, return.

   SbMemoryCopy(dest->buffer() + bytes_per_frame_ * dest_offset,
                wsola_output_->buffer(), rendered_frames * bytes_per_frame_);

   // Remove the frames which are read.
   int frames_to_move = wsola_output_->frames() - rendered_frames;
   SbMemoryMove(wsola_output_->buffer(),
                wsola_output_->buffer() + rendered_frames * bytes_per_frame_,
                frames_to_move * bytes_per_frame_);
   num_complete_frames_ -= rendered_frames;
   return rendered_frames;
 }

 bool AudioTimeStretcher::TargetIsWithinSearchRegion() const {
   const int search_block_size = num_candidate_blocks_ + (ola_window_size_ - 1);

   return target_block_index_ >= search_block_index_ &&
          target_block_index_ + ola_window_size_ <=
              search_block_index_ + search_block_size;
 }

 void AudioTimeStretcher::GetOptimalBlock() {
   int optimal_index = 0;

   // An interval around last optimal block which is excluded from the search.
   // This is to reduce the buzzy sound. The number 160 is rather arbitrary and
   // derived heuristically.
   const int kExcludeIntervalLengthFrames = 160;
   if (TargetIsWithinSearchRegion()) {
     optimal_index = target_block_index_;
     PeekAudioWithZeroPrepend(optimal_index, optimal_block_.get());
   } else {
     PeekAudioWithZeroPrepend(target_block_index_, target_block_.get());
     PeekAudioWithZeroPrepend(search_block_index_, search_block_.get());
     int last_optimal =
         target_block_index_ - ola_hop_size_ - search_block_index_;
     internal::Interval exclude_iterval =
         std::make_pair(last_optimal - kExcludeIntervalLengthFrames / 2,
                        last_optimal + kExcludeIntervalLengthFrames / 2);

     // |optimal_index| is in frames and it is relative to the beginning of the
     // |search_block_|.
     optimal_index = internal::OptimalIndex(
         search_block_.get(), target_block_.get(),
         kSbMediaAudioSampleTypeFloat32,
         kSbMediaAudioFrameStorageTypeInterleaved, exclude_iterval);

     // Translate |index| w.r.t. the beginning of |audio_buffer_| and extract the
     // optimal block.
     optimal_index += search_block_index_;
     PeekAudioWithZeroPrepend(optimal_index, optimal_block_.get());

     // Make a transition from target block to the optimal block if different.
     // Target block has the best continuation to the current output.
     // Optimal block is the most similar block to the target, however, it might
     // introduce some discontinuity when over-lap-added. Therefore, we combine
     // them for a smoother transition. The length of transition window is twice
     // as that of the optimal-block which makes it like a weighting function
     // where target-block has higher weight close to zero (weight of 1 at index
     // 0) and lower weight close the end.
     for (int k = 0; k < channels_; ++k) {
       float* ch_opt = reinterpret_cast<float*>(optimal_block_->buffer()) + k;
       const float* const ch_target =
           reinterpret_cast<float*>(target_block_->buffer()) + k;
       for (int n = 0; n < ola_window_size_; ++n) {
         ch_opt[n * channels_] =
             ch_opt[n * channels_] * transition_window_[n] +
             ch_target[n * channels_] * transition_window_[ola_window_size_ + n];
       }
     }
   }

   // Next target is one hop ahead of the current optimal.
   target_block_index_ = optimal_index + ola_hop_size_;
 }

 void AudioTimeStretcher::PeekAudioWithZeroPrepend(int read_offset_frames,
                                                   DecodedAudio* dest) {
   SB_DCHECK(bytes_per_frame_ > 0);
   SB_CHECK(read_offset_frames + dest->frames() <= audio_buffer_.frames());

   int write_offset = 0;
   int num_frames_to_read = dest->frames();
   if (read_offset_frames < 0) {
     int num_zero_frames_appended =
         std::min(-read_offset_frames, num_frames_to_read);
     read_offset_frames = 0;
     num_frames_to_read -= num_zero_frames_appended;
     write_offset = num_zero_frames_appended;
     SbMemorySet(dest->buffer(), 0, num_zero_frames_appended * bytes_per_frame_);
   }
   audio_buffer_.PeekFrames(num_frames_to_read, read_offset_frames, write_offset,
                            dest);
 }

 }  // namespace filter
 }  // namespace player
 }  // namespace starboard
 }  // namespace shared
 }  // namespace starboard
	// Copyright (c) 2012 The Chromium Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style license that can be
	// found in the LICENSE file.

	// Modifications Copyright 2017 Google Inc. All Rights Reserved.
	//
	// Licensed under the Apache License, Version 2.0 (the "License");
	// you may not use this file except in compliance with the License.
	// You may obtain a copy of the License at
	//
	// http://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing, software
	// distributed under the License is distributed on an "AS IS" BASIS,
	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	// See the License for the specific language governing permissions and
	// limitations under the License.

	#include "starboard/shared/starboard/player/filter/audio_time_stretcher.h"

	#include <algorithm>
	#include <cmath>

	#include "starboard/log.h"
	#include "starboard/memory.h"
	#include "starboard/shared/starboard/player/filter/wsola_internal.h"

	namespace starboard {
	namespace shared {
	namespace starboard {
	namespace player {
	namespace filter {

	// Waveform Similarity Overlap-and-add (WSOLA).
	//
	// One WSOLA iteration
	//
	// 1) Extract \|target_block_\| as input frames at indices
	// [\|target_block_index_\|, \|target_block_index_\| + \|ola_window_size_\|).
	// Note that \|target_block_\| is the "natural" continuation of the output.
	//
	// 2) Extract \|search_block_\| as input frames at indices
	// [\|search_block_index_\|,
	// \|search_block_index_\| + \|num_candidate_blocks_\| + \|ola_window_size_\|).
	//
	// 3) Find a block within the \|search_block_\| that is most similar
	// to \|target_block_\|. Let \|optimal_index\| be the index of such block and
	// write it to \|optimal_block_\|.
	//
	// 4) Update:
	// \|optimal_block_\| = \|transition_window_\| * \|target_block_\| +
	// (1 - \|transition_window_\|) * \|optimal_block_\|.
	//
	// 5) Overlap-and-add \|optimal_block_\| to the \|wsola_output_\|.
	//
	// 6) Update:
	// \|target_block_\| = \|optimal_index\| + \|ola_window_size_\| / 2.
	// \|output_index_\| = \|output_index_\| + \|ola_window_size_\| / 2,
	// \|search_block_center_offset_\| = \|output_index_\| * \|playback_rate\|, and
	// \|search_block_index_\| = \|search_block_center_offset_\| -
	// \|search_block_center_offset_\|.

	// Max/min supported playback rates for fast/slow audio. Audio outside of these
	// ranges are muted.
	// Audio at these speeds would sound better under a frequency domain algorithm.
	static const double kMinPlaybackRate = 0.5;
	static const double kMaxPlaybackRate = 4.0;

	// Overlap-and-add window size in milliseconds.
	static const int kOlaWindowSizeMs = 20;

	// Size of search interval in milliseconds. The search interval is
	// [-delta delta] around \|output_index_\| * \|playback_rate\|. So the search
	// interval is 2 * delta.
	static const int kWsolaSearchIntervalMs = 30;

	// The maximum size in seconds for the \|audio_buffer_\|. Arbitrarily determined.
	static const int kMaxCapacityInSeconds = 3;

	// The minimum size in ms for the \|audio_buffer_\|. Arbitrarily determined.
	static const int kStartingCapacityInMs = 200;

	AudioTimeStretcher::AudioTimeStretcher()
	: channels_(0),
	bytes_per_frame_(0),
	samples_per_second_(0),
	muted_partial_frame_(0),
	capacity_(0),
	output_time_(0.0),
	search_block_center_offset_(0),
	search_block_index_(0),
	num_candidate_blocks_(0),
	target_block_index_(0),
	ola_window_size_(0),
	ola_hop_size_(0),
	num_complete_frames_(0),
	initial_capacity_(0),
	max_capacity_(0) {}

	AudioTimeStretcher::~AudioTimeStretcher() {}

	void AudioTimeStretcher::Initialize(int channels, int samples_per_second) {
	channels_ = channels;
	bytes_per_frame_ = sizeof(float) * channels_;
	samples_per_second_ = samples_per_second;
	initial_capacity_ = capacity_ =
	ConvertMillisecondsToFrames(kStartingCapacityInMs);
	max_capacity_ =
	std::max(initial_capacity_, kMaxCapacityInSeconds * samples_per_second_);
	num_candidate_blocks_ = ConvertMillisecondsToFrames(kWsolaSearchIntervalMs);
	ola_window_size_ = ConvertMillisecondsToFrames(kOlaWindowSizeMs);

	// Make sure window size in an even number.
	ola_window_size_ += ola_window_size_ & 1;
	ola_hop_size_ = ola_window_size_ / 2;

	// \|num_candidate_blocks_\| / 2 is the offset of the center of the search
	// block to the center of the first (left most) candidate block. The offset
	// of the center of a candidate block to its left most point is
	// \|ola_window_size_\| / 2 - 1. Note that \|ola_window_size_\| is even and in
	// our convention the center belongs to the left half, so we need to subtract
	// one frame to get the correct offset.
	//
	// Search Block
	// <------------------------------------------->
	//
	// \|ola_window_size_\| / 2 - 1
	// <----
	//
	// \|num_candidate_blocks_\| / 2
	// <----------------
	// center
	// X----X----------------X---------------X-----X
	// <----------> <---------->
	// Candidate ... Candidate
	// 1, ... \|num_candidate_blocks_\|
	search_block_center_offset_ =
	num_candidate_blocks_ / 2 + (ola_window_size_ / 2 - 1);

	ola_window_.reset(new float[ola_window_size_]);
	internal::GetSymmetricHanningWindow(ola_window_size_, ola_window_.get());

	transition_window_.reset(new float[ola_window_size_ * 2]);
	internal::GetSymmetricHanningWindow(2 * ola_window_size_,
	transition_window_.get());

	wsola_output_ =
	new DecodedAudio(channels_, kSbMediaAudioSampleTypeFloat32,
	kSbMediaAudioFrameStorageTypeInterleaved, 0,
	(ola_window_size_ + ola_hop_size_) * bytes_per_frame_);
	// Initialize for overlap-and-add of the first block.
	SbMemorySet(wsola_output_->buffer(), 0, wsola_output_->size());

	// Auxiliary containers.
	optimal_block_ = new DecodedAudio(channels_, kSbMediaAudioSampleTypeFloat32,
	kSbMediaAudioFrameStorageTypeInterleaved, 0,
	ola_window_size_ * bytes_per_frame_);
	search_block_ = new DecodedAudio(
	channels_, kSbMediaAudioSampleTypeFloat32,
	kSbMediaAudioFrameStorageTypeInterleaved, 0,
	(num_candidate_blocks_ + (ola_window_size_ - 1)) * bytes_per_frame_);
	target_block_ = new DecodedAudio(channels_, kSbMediaAudioSampleTypeFloat32,
	kSbMediaAudioFrameStorageTypeInterleaved, 0,
	ola_window_size_ * bytes_per_frame_);
	}

	scoped_refptr<DecodedAudio> AudioTimeStretcher::Read(int requested_frames,
	double playback_rate) {
	SB_DCHECK(bytes_per_frame_ > 0);
	SB_DCHECK(playback_rate >= 0);

	scoped_refptr<DecodedAudio> dest =
	new DecodedAudio(channels_, kSbMediaAudioSampleTypeFloat32,
	kSbMediaAudioFrameStorageTypeInterleaved, 0,
	requested_frames * bytes_per_frame_);

	if (playback_rate == 0) {
	dest->ShrinkTo(0);
	return dest;
	}

	// Optimize the muted case to issue a single clear instead of performing
	// the full crossfade and clearing each crossfaded frame.
	if (playback_rate < kMinPlaybackRate \|\| playback_rate > kMaxPlaybackRate) {
	int frames_to_render =
	std::min(static_cast<int>(audio_buffer_.frames() / playback_rate),
	requested_frames);

	// Compute accurate number of frames to actually skip in the source data.
	// Includes the leftover partial frame from last request. However, we can
	// only skip over complete frames, so a partial frame may remain for next
	// time.
	muted_partial_frame_ += frames_to_render * playback_rate;
	// Handle the case where muted_partial_frame_ rounds up to
	// audio_buffer_.frames()+1.
	int seek_frames = std::min(static_cast<int>(muted_partial_frame_),
	audio_buffer_.frames());
	SbMemorySet(dest->buffer(), 0, frames_to_render * bytes_per_frame_);
	audio_buffer_.SeekFrames(seek_frames);

	// Determine the partial frame that remains to be skipped for next call. If
	// the user switches back to playing, it may be off time by this partial
	// frame, which would be undetectable. If they subsequently switch to
	// another playback rate that mutes, the code will attempt to line up the
	// frames again.
	muted_partial_frame_ -= seek_frames;
	dest->ShrinkTo(frames_to_render * bytes_per_frame_);
	return dest;
	}

	int slower_step = static_cast<int>(ceil(ola_window_size_ * playback_rate));
	int faster_step = static_cast<int>(ceil(ola_window_size_ / playback_rate));

	// Optimize the most common \|playback_rate\| ~= 1 case to use a single copy
	// instead of copying frame by frame.
	if (ola_window_size_ <= faster_step && slower_step >= ola_window_size_) {
	const int frames_to_copy =
	std::min(audio_buffer_.frames(), requested_frames);
	const int frames_read = audio_buffer_.ReadFrames(frames_to_copy, 0, dest);
	SB_DCHECK(frames_read == frames_to_copy);
	dest->ShrinkTo(frames_read * bytes_per_frame_);
	return dest;
	}

	int rendered_frames = 0;
	do {
	rendered_frames += WriteCompletedFramesTo(
	requested_frames - rendered_frames, rendered_frames, dest);
	} while (rendered_frames < requested_frames &&
	RunOneWsolaIteration(playback_rate));
	dest->ShrinkTo(rendered_frames * bytes_per_frame_);
	return dest;
	}

	void AudioTimeStretcher::FlushBuffers() {
	// Clear the queue of decoded packets (releasing the buffers).
	audio_buffer_.Clear();
	output_time_ = 0.0;
	search_block_index_ = 0;
	target_block_index_ = 0;
	SbMemorySet(wsola_output_->buffer(), 0, wsola_output_->size());
	num_complete_frames_ = 0;

	// Reset \|capacity_\| so growth triggered by underflows doesn't penalize seek
	// time.
	capacity_ = initial_capacity_;
	}

	void AudioTimeStretcher::EnqueueBuffer(
	const scoped_refptr<DecodedAudio>& audio_data) {
	SB_DCHECK(!audio_data->is_end_of_stream());
	audio_buffer_.Append(audio_data);
	}

	bool AudioTimeStretcher::IsQueueFull() const {
	return audio_buffer_.frames() >= capacity_;
	}

	// TODO: Make order of functions in .cc the same as order of functions in .h.
	bool AudioTimeStretcher::CanPerformWsola() const {
	const int search_block_size = num_candidate_blocks_ + (ola_window_size_ - 1);
	const int frames = audio_buffer_.frames();
	return target_block_index_ + ola_window_size_ <= frames &&
	search_block_index_ + search_block_size <= frames;
	}

	int AudioTimeStretcher::ConvertMillisecondsToFrames(int ms) const {
	const double kMillsecondsPerSeconds =
	static_cast<double>(kSbTimeSecond / kSbTimeMillisecond);
	return static_cast<int>(ms * (samples_per_second_ / kMillsecondsPerSeconds));
	}

	bool AudioTimeStretcher::RunOneWsolaIteration(double playback_rate) {
	SB_DCHECK(bytes_per_frame_ > 0);

	if (!CanPerformWsola()) return false;

	GetOptimalBlock();

	// Overlap-and-add.
	for (int k = 0; k < channels_; ++k) {
	const float* const ch_opt_frame =
	reinterpret_cast<const float*>(optimal_block_->buffer()) + k;
	float* ch_output = reinterpret_cast<float*>(wsola_output_->buffer()) + k +
	num_complete_frames_ * sizeof(float);
	for (int n = 0; n < ola_hop_size_; ++n) {
	ch_output[n * channels_] =
	ch_output[n * channels_] * ola_window_[ola_hop_size_ + n] +
	ch_opt_frame[n * channels_] * ola_window_[n];
	}
	}
	// Copy the second half to the output.
	const float* const ch_opt_frame =
	reinterpret_cast<const float*>(optimal_block_->buffer());
	float* ch_output = reinterpret_cast<float*>(wsola_output_->buffer()) +
	num_complete_frames_ * sizeof(float);
	SbMemoryCopy(&ch_output[ola_hop_size_ * channels_],
	&ch_opt_frame[ola_hop_size_ * channels_],
	sizeof(ch_opt_frame) ola_hop_size_ * channels_);

	num_complete_frames_ += ola_hop_size_;
	UpdateOutputTime(playback_rate, ola_hop_size_);
	RemoveOldInputFrames(playback_rate);
	return true;
	}

	void AudioTimeStretcher::UpdateOutputTime(double playback_rate,
	double time_change) {
	output_time_ += time_change;
	// Center of the search region, in frames.
	const int search_block_center_index =
	static_cast<int>(output_time_ * playback_rate + 0.5);
	search_block_index_ = search_block_center_index - search_block_center_offset_;
	}

	void AudioTimeStretcher::RemoveOldInputFrames(double playback_rate) {
	const int earliest_used_index =
	std::min(target_block_index_, search_block_index_);
	if (earliest_used_index <= 0) return; // Nothing to remove.

	// Remove frames from input and adjust indices accordingly.
	audio_buffer_.SeekFrames(earliest_used_index);
	target_block_index_ -= earliest_used_index;

	// Adjust output index.
	double output_time_change =
	static_cast<double>(earliest_used_index) / playback_rate;
	SB_CHECK(output_time_ >= output_time_change);
	UpdateOutputTime(playback_rate, -output_time_change);
	}

	int AudioTimeStretcher::WriteCompletedFramesTo(int requested_frames,
	int dest_offset,
	DecodedAudio* dest) {
	SB_DCHECK(bytes_per_frame_ > 0);

	int rendered_frames = std::min(num_complete_frames_, requested_frames);

	if (rendered_frames == 0)
	return 0; // There is nothing to read from \|wsola_output_\|, return.

	SbMemoryCopy(dest->buffer() + bytes_per_frame_ * dest_offset,
	wsola_output_->buffer(), rendered_frames * bytes_per_frame_);

	// Remove the frames which are read.
	int frames_to_move = wsola_output_->frames() - rendered_frames;
	SbMemoryMove(wsola_output_->buffer(),
	wsola_output_->buffer() + rendered_frames * bytes_per_frame_,
	frames_to_move * bytes_per_frame_);
	num_complete_frames_ -= rendered_frames;
	return rendered_frames;
	}

	bool AudioTimeStretcher::TargetIsWithinSearchRegion() const {
	const int search_block_size = num_candidate_blocks_ + (ola_window_size_ - 1);

	return target_block_index_ >= search_block_index_ &&
	target_block_index_ + ola_window_size_ <=
	search_block_index_ + search_block_size;
	}

	void AudioTimeStretcher::GetOptimalBlock() {
	int optimal_index = 0;

	// An interval around last optimal block which is excluded from the search.
	// This is to reduce the buzzy sound. The number 160 is rather arbitrary and
	// derived heuristically.
	const int kExcludeIntervalLengthFrames = 160;
	if (TargetIsWithinSearchRegion()) {
	optimal_index = target_block_index_;
	PeekAudioWithZeroPrepend(optimal_index, optimal_block_.get());
	} else {
	PeekAudioWithZeroPrepend(target_block_index_, target_block_.get());
	PeekAudioWithZeroPrepend(search_block_index_, search_block_.get());
	int last_optimal =
	target_block_index_ - ola_hop_size_ - search_block_index_;
	internal::Interval exclude_iterval =
	std::make_pair(last_optimal - kExcludeIntervalLengthFrames / 2,
	last_optimal + kExcludeIntervalLengthFrames / 2);

	// \|optimal_index\| is in frames and it is relative to the beginning of the
	// \|search_block_\|.
	optimal_index = internal::OptimalIndex(
	search_block_.get(), target_block_.get(),
	kSbMediaAudioSampleTypeFloat32,
	kSbMediaAudioFrameStorageTypeInterleaved, exclude_iterval);

	// Translate \|index\| w.r.t. the beginning of \|audio_buffer_\| and extract the
	// optimal block.
	optimal_index += search_block_index_;
	PeekAudioWithZeroPrepend(optimal_index, optimal_block_.get());

	// Make a transition from target block to the optimal block if different.
	// Target block has the best continuation to the current output.
	// Optimal block is the most similar block to the target, however, it might
	// introduce some discontinuity when over-lap-added. Therefore, we combine
	// them for a smoother transition. The length of transition window is twice
	// as that of the optimal-block which makes it like a weighting function
	// where target-block has higher weight close to zero (weight of 1 at index
	// 0) and lower weight close the end.
	for (int k = 0; k < channels_; ++k) {
	float* ch_opt = reinterpret_cast<float*>(optimal_block_->buffer()) + k;
	const float* const ch_target =
	reinterpret_cast<float*>(target_block_->buffer()) + k;
	for (int n = 0; n < ola_window_size_; ++n) {
	ch_opt[n * channels_] =
	ch_opt[n * channels_] * transition_window_[n] +
	ch_target[n * channels_] * transition_window_[ola_window_size_ + n];
	}
	}
	}

	// Next target is one hop ahead of the current optimal.
	target_block_index_ = optimal_index + ola_hop_size_;
	}

	void AudioTimeStretcher::PeekAudioWithZeroPrepend(int read_offset_frames,
	DecodedAudio* dest) {
	SB_DCHECK(bytes_per_frame_ > 0);
	SB_CHECK(read_offset_frames + dest->frames() <= audio_buffer_.frames());

	int write_offset = 0;
	int num_frames_to_read = dest->frames();
	if (read_offset_frames < 0) {
	int num_zero_frames_appended =
	std::min(-read_offset_frames, num_frames_to_read);
	read_offset_frames = 0;
	num_frames_to_read -= num_zero_frames_appended;
	write_offset = num_zero_frames_appended;
	SbMemorySet(dest->buffer(), 0, num_zero_frames_appended * bytes_per_frame_);
	}
	audio_buffer_.PeekFrames(num_frames_to_read, read_offset_frames, write_offset,
	dest);
	}

	} // namespace filter
	} // namespace player
	} // namespace starboard
	} // namespace shared
	} // namespace starboard