trunk/src/modules/audio_processing/utility/delay_estimator.c - vendor/opensource/webrtc - Git at Google

 /*
  *  Copyright (c) 2011 The WebRTC project authors. All Rights Reserved.
  *
  *  Use of this source code is governed by a BSD-style license
  *  that can be found in the LICENSE file in the root of the source
  *  tree. An additional intellectual property rights grant can be found
  *  in the file PATENTS.  All contributing project authors may
  *  be found in the AUTHORS file in the root of the source tree.
  */

 #include "delay_estimator.h"

 #include <assert.h>
 #include <stdlib.h>
 #include <string.h>

 // Number of right shifts for scaling is linearly depending on number of bits in
 // the far-end binary spectrum.
 static const int kShiftsAtZero = 13;  // Right shifts at zero binary spectrum.
 static const int kShiftsLinearSlope = 3;

 static const int32_t kProbabilityOffset = 1024;  // 2 in Q9.
 static const int32_t kProbabilityLowerLimit = 8704;  // 17 in Q9.
 static const int32_t kProbabilityMinSpread = 2816;  // 5.5 in Q9.

 // Counts and returns number of bits of a 32-bit word.
 static int BitCount(uint32_t u32) {
   uint32_t tmp = u32 - ((u32 >> 1) & 033333333333) -
       ((u32 >> 2) & 011111111111);
   tmp = ((tmp + (tmp >> 3)) & 030707070707);
   tmp = (tmp + (tmp >> 6));
   tmp = (tmp + (tmp >> 12) + (tmp >> 24)) & 077;

   return ((int) tmp);
 }

 // Compares the |binary_vector| with all rows of the |binary_matrix| and counts
 // per row the number of times they have the same value.
 //
 // Inputs:
 //      - binary_vector     : binary "vector" stored in a long
 //      - binary_matrix     : binary "matrix" stored as a vector of long
 //      - matrix_size       : size of binary "matrix"
 //
 // Output:
 //      - bit_counts        : "Vector" stored as a long, containing for each
 //                            row the number of times the matrix row and the
 //                            input vector have the same value
 //
 static void BitCountComparison(uint32_t binary_vector,
                                const uint32_t* binary_matrix,
                                int matrix_size,
                                int32_t* bit_counts) {
   int n = 0;

   // Compare |binary_vector| with all rows of the |binary_matrix|
   for (; n < matrix_size; n++) {
     bit_counts[n] = (int32_t) BitCount(binary_vector ^ binary_matrix[n]);
   }
 }

 int WebRtc_FreeBinaryDelayEstimator(BinaryDelayEstimator* handle) {
   assert(handle != NULL);

   if (handle->mean_bit_counts != NULL) {
     free(handle->mean_bit_counts);
     handle->mean_bit_counts = NULL;
   }
   if (handle->bit_counts != NULL) {
     free(handle->bit_counts);
     handle->bit_counts = NULL;
   }
   if (handle->binary_far_history != NULL) {
     free(handle->binary_far_history);
     handle->binary_far_history = NULL;
   }
   if (handle->binary_near_history != NULL) {
     free(handle->binary_near_history);
     handle->binary_near_history = NULL;
   }
   if (handle->far_bit_counts != NULL) {
     free(handle->far_bit_counts);
     handle->far_bit_counts = NULL;
   }

   free(handle);

   return 0;
 }

 int WebRtc_CreateBinaryDelayEstimator(BinaryDelayEstimator** handle,
                                       int max_delay,
                                       int lookahead) {
   BinaryDelayEstimator* self = NULL;
   int history_size = max_delay + lookahead;

   if (handle == NULL) {
     return -1;
   }
   if (max_delay < 0) {
     return -1;
   }
   if (lookahead < 0) {
     return -1;
   }
   if (history_size < 2) {
     // Must be this large for buffer shifting.
     return -1;
   }

   self = malloc(sizeof(BinaryDelayEstimator));
   *handle = self;
   if (self == NULL) {
     return -1;
   }

   self->mean_bit_counts = NULL;
   self->bit_counts = NULL;
   self->binary_far_history = NULL;
   self->far_bit_counts = NULL;

   self->history_size = history_size;
   self->near_history_size = lookahead + 1;

   // Allocate memory for spectrum buffers.
   self->mean_bit_counts = malloc(history_size * sizeof(int32_t));
   if (self->mean_bit_counts == NULL) {
     WebRtc_FreeBinaryDelayEstimator(self);
     self = NULL;
     return -1;
   }
   self->bit_counts = malloc(history_size * sizeof(int32_t));
   if (self->bit_counts == NULL) {
     WebRtc_FreeBinaryDelayEstimator(self);
     self = NULL;
     return -1;
   }
   // Allocate memory for history buffers.
   self->binary_far_history = malloc(history_size * sizeof(uint32_t));
   if (self->binary_far_history == NULL) {
     WebRtc_FreeBinaryDelayEstimator(self);
     self = NULL;
     return -1;
   }
   self->binary_near_history = malloc(self->near_history_size *
       sizeof(uint32_t));
   if (self->binary_near_history == NULL) {
     WebRtc_FreeBinaryDelayEstimator(self);
     self = NULL;
     return -1;
   }
   self->far_bit_counts = malloc(history_size * sizeof(int));
   if (self->far_bit_counts == NULL) {
     WebRtc_FreeBinaryDelayEstimator(self);
     self = NULL;
     return -1;
   }

   return 0;
 }

 int WebRtc_InitBinaryDelayEstimator(BinaryDelayEstimator* handle) {
   int i = 0;
   assert(handle != NULL);

   memset(handle->bit_counts, 0, sizeof(int32_t) * handle->history_size);
   memset(handle->binary_far_history, 0,
          sizeof(uint32_t) * handle->history_size);
   memset(handle->binary_near_history, 0,
          sizeof(uint32_t) * handle->near_history_size);
   memset(handle->far_bit_counts, 0, sizeof(int) * handle->history_size);
   for (i = 0; i < handle->history_size; ++i) {
     handle->mean_bit_counts[i] = (20 << 9);  // 20 in Q9.
   }
   handle->minimum_probability = (32 << 9);  // 32 in Q9.
   handle->last_delay_probability = (32 << 9);  // 32 in Q9.

   // Default return value if we're unable to estimate. -1 is used for errors.
   handle->last_delay = -2;

   return 0;
 }

 int WebRtc_ProcessBinarySpectrum(BinaryDelayEstimator* handle,
                                  uint32_t binary_far_spectrum,
                                  uint32_t binary_near_spectrum) {
   int i = 0;
   int candidate_delay = -1;

   int32_t value_best_candidate = 16384;  // 32 in Q9, (max |mean_bit_counts|).
   int32_t value_worst_candidate = 0;

   assert(handle != NULL);
   // Shift binary spectrum history and insert current |binary_far_spectrum|.
   memmove(&(handle->binary_far_history[1]), &(handle->binary_far_history[0]),
           (handle->history_size - 1) * sizeof(uint32_t));
   handle->binary_far_history[0] = binary_far_spectrum;

   // Shift history of far-end binary spectrum bit counts and insert bit count
   // of current |binary_far_spectrum|.
   memmove(&(handle->far_bit_counts[1]), &(handle->far_bit_counts[0]),
           (handle->history_size - 1) * sizeof(int));
   handle->far_bit_counts[0] = BitCount(binary_far_spectrum);

   if (handle->near_history_size > 1) {
     // If we apply lookahead, shift near-end binary spectrum history. Insert
     // current |binary_near_spectrum| and pull out the delayed one.
     memmove(&(handle->binary_near_history[1]),
             &(handle->binary_near_history[0]),
             (handle->near_history_size - 1) * sizeof(uint32_t));
     handle->binary_near_history[0] = binary_near_spectrum;
     binary_near_spectrum =
         handle->binary_near_history[handle->near_history_size - 1];
   }

   // Compare with delayed spectra and store the |bit_counts| for each delay.
   BitCountComparison(binary_near_spectrum,
                      handle->binary_far_history,
                      handle->history_size,
                      handle->bit_counts);

   // Update |mean_bit_counts|, which is the smoothed version of |bit_counts|.
   for (i = 0; i < handle->history_size; i++) {
     // |bit_counts| is constrained to [0, 32], meaning we can smooth with a
     // factor up to 2^26. We use Q9.
     int32_t bit_count = (handle->bit_counts[i] << 9);  // Q9.

     // Update |mean_bit_counts| only when far-end signal has something to
     // contribute. If |far_bit_counts| is zero the far-end signal is weak and
     // we likely have a poor echo condition, hence don't update.
     if (handle->far_bit_counts[i] > 0) {
       // Make number of right shifts piecewise linear w.r.t. |far_bit_counts|.
       int shifts = kShiftsAtZero;
       shifts -= (kShiftsLinearSlope * handle->far_bit_counts[i]) >> 4;
       WebRtc_MeanEstimatorFix(bit_count, shifts, &(handle->mean_bit_counts[i]));
     }
   }

   // Find |candidate_delay|, |value_best_candidate| and |value_worst_candidate|
   // of |mean_bit_counts|.
   for (i = 0; i < handle->history_size; i++) {
     if (handle->mean_bit_counts[i] < value_best_candidate) {
       value_best_candidate = handle->mean_bit_counts[i];
       candidate_delay = i;
     }
     if (handle->mean_bit_counts[i] > value_worst_candidate) {
       value_worst_candidate = handle->mean_bit_counts[i];
     }
   }

   // The |value_best_candidate| is a good indicator on the probability of
   // |candidate_delay| being an accurate delay (a small |value_best_candidate|
   // means a good binary match). In the following sections we make a decision
   // whether to update |last_delay| or not.
   // 1) If the difference bit counts between the best and the worst delay
   //    candidates is too small we consider the situation to be unreliable and
   //    don't update |last_delay|.
   // 2) If the situation is reliable we update |last_delay| if the value of the
   //    best candidate delay has a value less than
   //     i) an adaptive threshold |minimum_probability|, or
   //    ii) this corresponding value |last_delay_probability|, but updated at
   //        this time instant.

   // Update |minimum_probability|.
   if ((handle->minimum_probability > kProbabilityLowerLimit) &&
       (value_worst_candidate - value_best_candidate > kProbabilityMinSpread)) {
     // The "hard" threshold can't be lower than 17 (in Q9).
     // The valley in the curve also has to be distinct, i.e., the
     // difference between |value_worst_candidate| and |value_best_candidate| has
     // to be large enough.
     int32_t threshold = value_best_candidate + kProbabilityOffset;
     if (threshold < kProbabilityLowerLimit) {
       threshold = kProbabilityLowerLimit;
     }
     if (handle->minimum_probability > threshold) {
       handle->minimum_probability = threshold;
     }
   }
   // Update |last_delay_probability|.
   // We use a Markov type model, i.e., a slowly increasing level over time.
   handle->last_delay_probability++;
   if (value_worst_candidate > value_best_candidate + kProbabilityOffset) {
     // Reliable delay value for usage.
     if (value_best_candidate < handle->minimum_probability) {
       handle->last_delay = candidate_delay;
     }
     if (value_best_candidate < handle->last_delay_probability) {
       handle->last_delay = candidate_delay;
       // Reset |last_delay_probability|.
       handle->last_delay_probability = value_best_candidate;
     }
   }

   return handle->last_delay;
 }

 int WebRtc_binary_last_delay(BinaryDelayEstimator* handle) {
   assert(handle != NULL);
   return handle->last_delay;
 }

 int WebRtc_history_size(BinaryDelayEstimator* handle) {
   assert(handle != NULL);
   return handle->history_size;
 }

 void WebRtc_MeanEstimatorFix(int32_t new_value,
                              int factor,
                              int32_t* mean_value) {
   int32_t diff = new_value - *mean_value;

   // mean_new = mean_value + ((new_value - mean_value) >> factor);
   if (diff < 0) {
     diff = -((-diff) >> factor);
   } else {
     diff = (diff >> factor);
   }
   *mean_value += diff;
 }
	/*
	* Copyright (c) 2011 The WebRTC project authors. All Rights Reserved.
	*
	* Use of this source code is governed by a BSD-style license
	* that can be found in the LICENSE file in the root of the source
	* tree. An additional intellectual property rights grant can be found
	* in the file PATENTS. All contributing project authors may
	* be found in the AUTHORS file in the root of the source tree.
	*/

	#include "delay_estimator.h"

	#include <assert.h>
	#include <stdlib.h>
	#include <string.h>

	// Number of right shifts for scaling is linearly depending on number of bits in
	// the far-end binary spectrum.
	static const int kShiftsAtZero = 13; // Right shifts at zero binary spectrum.
	static const int kShiftsLinearSlope = 3;

	static const int32_t kProbabilityOffset = 1024; // 2 in Q9.
	static const int32_t kProbabilityLowerLimit = 8704; // 17 in Q9.
	static const int32_t kProbabilityMinSpread = 2816; // 5.5 in Q9.

	// Counts and returns number of bits of a 32-bit word.
	static int BitCount(uint32_t u32) {
	uint32_t tmp = u32 - ((u32 >> 1) & 033333333333) -
	((u32 >> 2) & 011111111111);
	tmp = ((tmp + (tmp >> 3)) & 030707070707);
	tmp = (tmp + (tmp >> 6));
	tmp = (tmp + (tmp >> 12) + (tmp >> 24)) & 077;

	return ((int) tmp);
	}

	// Compares the \|binary_vector\| with all rows of the \|binary_matrix\| and counts
	// per row the number of times they have the same value.
	//
	// Inputs:
	// - binary_vector : binary "vector" stored in a long
	// - binary_matrix : binary "matrix" stored as a vector of long
	// - matrix_size : size of binary "matrix"
	//
	// Output:
	// - bit_counts : "Vector" stored as a long, containing for each
	// row the number of times the matrix row and the
	// input vector have the same value
	//
	static void BitCountComparison(uint32_t binary_vector,
	const uint32_t* binary_matrix,
	int matrix_size,
	int32_t* bit_counts) {
	int n = 0;

	// Compare \|binary_vector\| with all rows of the \|binary_matrix\|
	for (; n < matrix_size; n++) {
	bit_counts[n] = (int32_t) BitCount(binary_vector ^ binary_matrix[n]);
	}
	}

	int WebRtc_FreeBinaryDelayEstimator(BinaryDelayEstimator* handle) {
	assert(handle != NULL);

	if (handle->mean_bit_counts != NULL) {
	free(handle->mean_bit_counts);
	handle->mean_bit_counts = NULL;
	}
	if (handle->bit_counts != NULL) {
	free(handle->bit_counts);
	handle->bit_counts = NULL;
	}
	if (handle->binary_far_history != NULL) {
	free(handle->binary_far_history);
	handle->binary_far_history = NULL;
	}
	if (handle->binary_near_history != NULL) {
	free(handle->binary_near_history);
	handle->binary_near_history = NULL;
	}
	if (handle->far_bit_counts != NULL) {
	free(handle->far_bit_counts);
	handle->far_bit_counts = NULL;
	}

	free(handle);

	return 0;
	}

	int WebRtc_CreateBinaryDelayEstimator(BinaryDelayEstimator** handle,
	int max_delay,
	int lookahead) {
	BinaryDelayEstimator* self = NULL;
	int history_size = max_delay + lookahead;

	if (handle == NULL) {
	return -1;
	}
	if (max_delay < 0) {
	return -1;
	}
	if (lookahead < 0) {
	return -1;
	}
	if (history_size < 2) {
	// Must be this large for buffer shifting.
	return -1;
	}

	self = malloc(sizeof(BinaryDelayEstimator));
	*handle = self;
	if (self == NULL) {
	return -1;
	}

	self->mean_bit_counts = NULL;
	self->bit_counts = NULL;
	self->binary_far_history = NULL;
	self->far_bit_counts = NULL;

	self->history_size = history_size;
	self->near_history_size = lookahead + 1;

	// Allocate memory for spectrum buffers.
	self->mean_bit_counts = malloc(history_size * sizeof(int32_t));
	if (self->mean_bit_counts == NULL) {
	WebRtc_FreeBinaryDelayEstimator(self);
	self = NULL;
	return -1;
	}
	self->bit_counts = malloc(history_size * sizeof(int32_t));
	if (self->bit_counts == NULL) {
	WebRtc_FreeBinaryDelayEstimator(self);
	self = NULL;
	return -1;
	}
	// Allocate memory for history buffers.
	self->binary_far_history = malloc(history_size * sizeof(uint32_t));
	if (self->binary_far_history == NULL) {
	WebRtc_FreeBinaryDelayEstimator(self);
	self = NULL;
	return -1;
	}
	self->binary_near_history = malloc(self->near_history_size *
	sizeof(uint32_t));
	if (self->binary_near_history == NULL) {
	WebRtc_FreeBinaryDelayEstimator(self);
	self = NULL;
	return -1;
	}
	self->far_bit_counts = malloc(history_size * sizeof(int));
	if (self->far_bit_counts == NULL) {
	WebRtc_FreeBinaryDelayEstimator(self);
	self = NULL;
	return -1;
	}

	return 0;
	}

	int WebRtc_InitBinaryDelayEstimator(BinaryDelayEstimator* handle) {
	int i = 0;
	assert(handle != NULL);

	memset(handle->bit_counts, 0, sizeof(int32_t) * handle->history_size);
	memset(handle->binary_far_history, 0,
	sizeof(uint32_t) * handle->history_size);
	memset(handle->binary_near_history, 0,
	sizeof(uint32_t) * handle->near_history_size);
	memset(handle->far_bit_counts, 0, sizeof(int) * handle->history_size);
	for (i = 0; i < handle->history_size; ++i) {
	handle->mean_bit_counts[i] = (20 << 9); // 20 in Q9.
	}
	handle->minimum_probability = (32 << 9); // 32 in Q9.
	handle->last_delay_probability = (32 << 9); // 32 in Q9.

	// Default return value if we're unable to estimate. -1 is used for errors.
	handle->last_delay = -2;

	return 0;
	}

	int WebRtc_ProcessBinarySpectrum(BinaryDelayEstimator* handle,
	uint32_t binary_far_spectrum,
	uint32_t binary_near_spectrum) {
	int i = 0;
	int candidate_delay = -1;

	int32_t value_best_candidate = 16384; // 32 in Q9, (max \|mean_bit_counts\|).
	int32_t value_worst_candidate = 0;

	assert(handle != NULL);
	// Shift binary spectrum history and insert current \|binary_far_spectrum\|.
	memmove(&(handle->binary_far_history[1]), &(handle->binary_far_history[0]),
	(handle->history_size - 1) * sizeof(uint32_t));
	handle->binary_far_history[0] = binary_far_spectrum;

	// Shift history of far-end binary spectrum bit counts and insert bit count
	// of current \|binary_far_spectrum\|.
	memmove(&(handle->far_bit_counts[1]), &(handle->far_bit_counts[0]),
	(handle->history_size - 1) * sizeof(int));
	handle->far_bit_counts[0] = BitCount(binary_far_spectrum);

	if (handle->near_history_size > 1) {
	// If we apply lookahead, shift near-end binary spectrum history. Insert
	// current \|binary_near_spectrum\| and pull out the delayed one.
	memmove(&(handle->binary_near_history[1]),
	&(handle->binary_near_history[0]),
	(handle->near_history_size - 1) * sizeof(uint32_t));
	handle->binary_near_history[0] = binary_near_spectrum;
	binary_near_spectrum =
	handle->binary_near_history[handle->near_history_size - 1];
	}

	// Compare with delayed spectra and store the \|bit_counts\| for each delay.
	BitCountComparison(binary_near_spectrum,
	handle->binary_far_history,
	handle->history_size,
	handle->bit_counts);

	// Update \|mean_bit_counts\|, which is the smoothed version of \|bit_counts\|.
	for (i = 0; i < handle->history_size; i++) {
	// \|bit_counts\| is constrained to [0, 32], meaning we can smooth with a
	// factor up to 2^26. We use Q9.
	int32_t bit_count = (handle->bit_counts[i] << 9); // Q9.

	// Update \|mean_bit_counts\| only when far-end signal has something to
	// contribute. If \|far_bit_counts\| is zero the far-end signal is weak and
	// we likely have a poor echo condition, hence don't update.
	if (handle->far_bit_counts[i] > 0) {
	// Make number of right shifts piecewise linear w.r.t. \|far_bit_counts\|.
	int shifts = kShiftsAtZero;
	shifts -= (kShiftsLinearSlope * handle->far_bit_counts[i]) >> 4;
	WebRtc_MeanEstimatorFix(bit_count, shifts, &(handle->mean_bit_counts[i]));
	}
	}

	// Find \|candidate_delay\|, \|value_best_candidate\| and \|value_worst_candidate\|
	// of \|mean_bit_counts\|.
	for (i = 0; i < handle->history_size; i++) {
	if (handle->mean_bit_counts[i] < value_best_candidate) {
	value_best_candidate = handle->mean_bit_counts[i];
	candidate_delay = i;
	}
	if (handle->mean_bit_counts[i] > value_worst_candidate) {
	value_worst_candidate = handle->mean_bit_counts[i];
	}
	}

	// The \|value_best_candidate\| is a good indicator on the probability of
	// \|candidate_delay\| being an accurate delay (a small \|value_best_candidate\|
	// means a good binary match). In the following sections we make a decision
	// whether to update \|last_delay\| or not.
	// 1) If the difference bit counts between the best and the worst delay
	// candidates is too small we consider the situation to be unreliable and
	// don't update \|last_delay\|.
	// 2) If the situation is reliable we update \|last_delay\| if the value of the
	// best candidate delay has a value less than
	// i) an adaptive threshold \|minimum_probability\|, or
	// ii) this corresponding value \|last_delay_probability\|, but updated at
	// this time instant.

	// Update \|minimum_probability\|.
	if ((handle->minimum_probability > kProbabilityLowerLimit) &&
	(value_worst_candidate - value_best_candidate > kProbabilityMinSpread)) {
	// The "hard" threshold can't be lower than 17 (in Q9).
	// The valley in the curve also has to be distinct, i.e., the
	// difference between \|value_worst_candidate\| and \|value_best_candidate\| has
	// to be large enough.
	int32_t threshold = value_best_candidate + kProbabilityOffset;
	if (threshold < kProbabilityLowerLimit) {
	threshold = kProbabilityLowerLimit;
	}
	if (handle->minimum_probability > threshold) {
	handle->minimum_probability = threshold;
	}
	}
	// Update \|last_delay_probability\|.
	// We use a Markov type model, i.e., a slowly increasing level over time.
	handle->last_delay_probability++;
	if (value_worst_candidate > value_best_candidate + kProbabilityOffset) {
	// Reliable delay value for usage.
	if (value_best_candidate < handle->minimum_probability) {
	handle->last_delay = candidate_delay;
	}
	if (value_best_candidate < handle->last_delay_probability) {
	handle->last_delay = candidate_delay;
	// Reset \|last_delay_probability\|.
	handle->last_delay_probability = value_best_candidate;
	}
	}

	return handle->last_delay;
	}

	int WebRtc_binary_last_delay(BinaryDelayEstimator* handle) {
	assert(handle != NULL);
	return handle->last_delay;
	}

	int WebRtc_history_size(BinaryDelayEstimator* handle) {
	assert(handle != NULL);
	return handle->history_size;
	}

	void WebRtc_MeanEstimatorFix(int32_t new_value,
	int factor,
	int32_t* mean_value) {
	int32_t diff = new_value - *mean_value;

	// mean_new = mean_value + ((new_value - mean_value) >> factor);
	if (diff < 0) {
	diff = -((-diff) >> factor);
	} else {
	diff = (diff >> factor);
	}
	*mean_value += diff;
	}