Home | History | Annotate | Download | only in utility
      1 /*
      2  *  Copyright (c) 2012 The WebRTC project authors. All Rights Reserved.
      3  *
      4  *  Use of this source code is governed by a BSD-style license
      5  *  that can be found in the LICENSE file in the root of the source
      6  *  tree. An additional intellectual property rights grant can be found
      7  *  in the file PATENTS.  All contributing project authors may
      8  *  be found in the AUTHORS file in the root of the source tree.
      9  */
     10 
     11 #include "webrtc/modules/audio_processing/utility/delay_estimator.h"
     12 
     13 #include <assert.h>
     14 #include <stdlib.h>
     15 #include <string.h>
     16 
     17 // Number of right shifts for scaling is linearly depending on number of bits in
     18 // the far-end binary spectrum.
     19 static const int kShiftsAtZero = 13;  // Right shifts at zero binary spectrum.
     20 static const int kShiftsLinearSlope = 3;
     21 
     22 static const int32_t kProbabilityOffset = 1024;  // 2 in Q9.
     23 static const int32_t kProbabilityLowerLimit = 8704;  // 17 in Q9.
     24 static const int32_t kProbabilityMinSpread = 2816;  // 5.5 in Q9.
     25 
     26 // Robust validation settings
     27 static const float kHistogramMax = 3000.f;
     28 static const float kLastHistogramMax = 250.f;
     29 static const float kMinHistogramThreshold = 1.5f;
     30 static const int kMinRequiredHits = 10;
     31 static const int kMaxHitsWhenPossiblyNonCausal = 10;
     32 static const int kMaxHitsWhenPossiblyCausal = 1000;
     33 static const float kQ14Scaling = 1.f / (1 << 14);  // Scaling by 2^14 to get Q0.
     34 static const float kFractionSlope = 0.05f;
     35 static const float kMinFractionWhenPossiblyCausal = 0.5f;
     36 static const float kMinFractionWhenPossiblyNonCausal = 0.25f;
     37 
     38 // Counts and returns number of bits of a 32-bit word.
     39 static int BitCount(uint32_t u32) {
     40   uint32_t tmp = u32 - ((u32 >> 1) & 033333333333) -
     41       ((u32 >> 2) & 011111111111);
     42   tmp = ((tmp + (tmp >> 3)) & 030707070707);
     43   tmp = (tmp + (tmp >> 6));
     44   tmp = (tmp + (tmp >> 12) + (tmp >> 24)) & 077;
     45 
     46   return ((int) tmp);
     47 }
     48 
     49 // Compares the |binary_vector| with all rows of the |binary_matrix| and counts
     50 // per row the number of times they have the same value.
     51 //
     52 // Inputs:
     53 //      - binary_vector     : binary "vector" stored in a long
     54 //      - binary_matrix     : binary "matrix" stored as a vector of long
     55 //      - matrix_size       : size of binary "matrix"
     56 //
     57 // Output:
     58 //      - bit_counts        : "Vector" stored as a long, containing for each
     59 //                            row the number of times the matrix row and the
     60 //                            input vector have the same value
     61 //
     62 static void BitCountComparison(uint32_t binary_vector,
     63                                const uint32_t* binary_matrix,
     64                                int matrix_size,
     65                                int32_t* bit_counts) {
     66   int n = 0;
     67 
     68   // Compare |binary_vector| with all rows of the |binary_matrix|
     69   for (; n < matrix_size; n++) {
     70     bit_counts[n] = (int32_t) BitCount(binary_vector ^ binary_matrix[n]);
     71   }
     72 }
     73 
     74 // Collects necessary statistics for the HistogramBasedValidation().  This
     75 // function has to be called prior to calling HistogramBasedValidation().  The
     76 // statistics updated and used by the HistogramBasedValidation() are:
     77 //  1. the number of |candidate_hits|, which states for how long we have had the
     78 //     same |candidate_delay|
     79 //  2. the |histogram| of candidate delays over time.  This histogram is
     80 //     weighted with respect to a reliability measure and time-varying to cope
     81 //     with possible delay shifts.
     82 // For further description see commented code.
     83 //
     84 // Inputs:
     85 //  - candidate_delay   : The delay to validate.
     86 //  - valley_depth_q14  : The cost function has a valley/minimum at the
     87 //                        |candidate_delay| location.  |valley_depth_q14| is the
     88 //                        cost function difference between the minimum and
     89 //                        maximum locations.  The value is in the Q14 domain.
     90 //  - valley_level_q14  : Is the cost function value at the minimum, in Q14.
     91 static void UpdateRobustValidationStatistics(BinaryDelayEstimator* self,
     92                                              int candidate_delay,
     93                                              int32_t valley_depth_q14,
     94                                              int32_t valley_level_q14) {
     95   const float valley_depth = valley_depth_q14 * kQ14Scaling;
     96   float decrease_in_last_set = valley_depth;
     97   const int max_hits_for_slow_change = (candidate_delay < self->last_delay) ?
     98       kMaxHitsWhenPossiblyNonCausal : kMaxHitsWhenPossiblyCausal;
     99   int i = 0;
    100 
    101   assert(self->history_size == self->farend->history_size);
    102   // Reset |candidate_hits| if we have a new candidate.
    103   if (candidate_delay != self->last_candidate_delay) {
    104     self->candidate_hits = 0;
    105     self->last_candidate_delay = candidate_delay;
    106   }
    107   self->candidate_hits++;
    108 
    109   // The |histogram| is updated differently across the bins.
    110   // 1. The |candidate_delay| histogram bin is increased with the
    111   //    |valley_depth|, which is a simple measure of how reliable the
    112   //    |candidate_delay| is.  The histogram is not increased above
    113   //    |kHistogramMax|.
    114   self->histogram[candidate_delay] += valley_depth;
    115   if (self->histogram[candidate_delay] > kHistogramMax) {
    116     self->histogram[candidate_delay] = kHistogramMax;
    117   }
    118   // 2. The histogram bins in the neighborhood of |candidate_delay| are
    119   //    unaffected.  The neighborhood is defined as x + {-2, -1, 0, 1}.
    120   // 3. The histogram bins in the neighborhood of |last_delay| are decreased
    121   //    with |decrease_in_last_set|.  This value equals the difference between
    122   //    the cost function values at the locations |candidate_delay| and
    123   //    |last_delay| until we reach |max_hits_for_slow_change| consecutive hits
    124   //    at the |candidate_delay|.  If we exceed this amount of hits the
    125   //    |candidate_delay| is a "potential" candidate and we start decreasing
    126   //    these histogram bins more rapidly with |valley_depth|.
    127   if (self->candidate_hits < max_hits_for_slow_change) {
    128     decrease_in_last_set = (self->mean_bit_counts[self->compare_delay] -
    129         valley_level_q14) * kQ14Scaling;
    130   }
    131   // 4. All other bins are decreased with |valley_depth|.
    132   // TODO(bjornv): Investigate how to make this loop more efficient.  Split up
    133   // the loop?  Remove parts that doesn't add too much.
    134   for (i = 0; i < self->history_size; ++i) {
    135     int is_in_last_set = (i >= self->last_delay - 2) &&
    136         (i <= self->last_delay + 1) && (i != candidate_delay);
    137     int is_in_candidate_set = (i >= candidate_delay - 2) &&
    138         (i <= candidate_delay + 1);
    139     self->histogram[i] -= decrease_in_last_set * is_in_last_set +
    140         valley_depth * (!is_in_last_set && !is_in_candidate_set);
    141     // 5. No histogram bin can go below 0.
    142     if (self->histogram[i] < 0) {
    143       self->histogram[i] = 0;
    144     }
    145   }
    146 }
    147 
    148 // Validates the |candidate_delay|, estimated in WebRtc_ProcessBinarySpectrum(),
    149 // based on a mix of counting concurring hits with a modified histogram
    150 // of recent delay estimates.  In brief a candidate is valid (returns 1) if it
    151 // is the most likely according to the histogram.  There are a couple of
    152 // exceptions that are worth mentioning:
    153 //  1. If the |candidate_delay| < |last_delay| it can be that we are in a
    154 //     non-causal state, breaking a possible echo control algorithm.  Hence, we
    155 //     open up for a quicker change by allowing the change even if the
    156 //     |candidate_delay| is not the most likely one according to the histogram.
    157 //  2. There's a minimum number of hits (kMinRequiredHits) and the histogram
    158 //     value has to reached a minimum (kMinHistogramThreshold) to be valid.
    159 //  3. The action is also depending on the filter length used for echo control.
    160 //     If the delay difference is larger than what the filter can capture, we
    161 //     also move quicker towards a change.
    162 // For further description see commented code.
    163 //
    164 // Input:
    165 //  - candidate_delay     : The delay to validate.
    166 //
    167 // Return value:
    168 //  - is_histogram_valid  : 1 - The |candidate_delay| is valid.
    169 //                          0 - Otherwise.
    170 static int HistogramBasedValidation(const BinaryDelayEstimator* self,
    171                                     int candidate_delay) {
    172   float fraction = 1.f;
    173   float histogram_threshold = self->histogram[self->compare_delay];
    174   const int delay_difference = candidate_delay - self->last_delay;
    175   int is_histogram_valid = 0;
    176 
    177   // The histogram based validation of |candidate_delay| is done by comparing
    178   // the |histogram| at bin |candidate_delay| with a |histogram_threshold|.
    179   // This |histogram_threshold| equals a |fraction| of the |histogram| at bin
    180   // |last_delay|.  The |fraction| is a piecewise linear function of the
    181   // |delay_difference| between the |candidate_delay| and the |last_delay|
    182   // allowing for a quicker move if
    183   //  i) a potential echo control filter can not handle these large differences.
    184   // ii) keeping |last_delay| instead of updating to |candidate_delay| could
    185   //     force an echo control into a non-causal state.
    186   // We further require the histogram to have reached a minimum value of
    187   // |kMinHistogramThreshold|.  In addition, we also require the number of
    188   // |candidate_hits| to be more than |kMinRequiredHits| to remove spurious
    189   // values.
    190 
    191   // Calculate a comparison histogram value (|histogram_threshold|) that is
    192   // depending on the distance between the |candidate_delay| and |last_delay|.
    193   // TODO(bjornv): How much can we gain by turning the fraction calculation
    194   // into tables?
    195   if (delay_difference > self->allowed_offset) {
    196     fraction = 1.f - kFractionSlope * (delay_difference - self->allowed_offset);
    197     fraction = (fraction > kMinFractionWhenPossiblyCausal ? fraction :
    198         kMinFractionWhenPossiblyCausal);
    199   } else if (delay_difference < 0) {
    200     fraction = kMinFractionWhenPossiblyNonCausal -
    201         kFractionSlope * delay_difference;
    202     fraction = (fraction > 1.f ? 1.f : fraction);
    203   }
    204   histogram_threshold *= fraction;
    205   histogram_threshold = (histogram_threshold > kMinHistogramThreshold ?
    206       histogram_threshold : kMinHistogramThreshold);
    207 
    208   is_histogram_valid =
    209       (self->histogram[candidate_delay] >= histogram_threshold) &&
    210       (self->candidate_hits > kMinRequiredHits);
    211 
    212   return is_histogram_valid;
    213 }
    214 
    215 // Performs a robust validation of the |candidate_delay| estimated in
    216 // WebRtc_ProcessBinarySpectrum().  The algorithm takes the
    217 // |is_instantaneous_valid| and the |is_histogram_valid| and combines them
    218 // into a robust validation.  The HistogramBasedValidation() has to be called
    219 // prior to this call.
    220 // For further description on how the combination is done, see commented code.
    221 //
    222 // Inputs:
    223 //  - candidate_delay         : The delay to validate.
    224 //  - is_instantaneous_valid  : The instantaneous validation performed in
    225 //                              WebRtc_ProcessBinarySpectrum().
    226 //  - is_histogram_valid      : The histogram based validation.
    227 //
    228 // Return value:
    229 //  - is_robust               : 1 - The candidate_delay is valid according to a
    230 //                                  combination of the two inputs.
    231 //                            : 0 - Otherwise.
    232 static int RobustValidation(const BinaryDelayEstimator* self,
    233                             int candidate_delay,
    234                             int is_instantaneous_valid,
    235                             int is_histogram_valid) {
    236   int is_robust = 0;
    237 
    238   // The final robust validation is based on the two algorithms; 1) the
    239   // |is_instantaneous_valid| and 2) the histogram based with result stored in
    240   // |is_histogram_valid|.
    241   //   i) Before we actually have a valid estimate (|last_delay| == -2), we say
    242   //      a candidate is valid if either algorithm states so
    243   //      (|is_instantaneous_valid| OR |is_histogram_valid|).
    244   is_robust = (self->last_delay < 0) &&
    245       (is_instantaneous_valid || is_histogram_valid);
    246   //  ii) Otherwise, we need both algorithms to be certain
    247   //      (|is_instantaneous_valid| AND |is_histogram_valid|)
    248   is_robust |= is_instantaneous_valid && is_histogram_valid;
    249   // iii) With one exception, i.e., the histogram based algorithm can overrule
    250   //      the instantaneous one if |is_histogram_valid| = 1 and the histogram
    251   //      is significantly strong.
    252   is_robust |= is_histogram_valid &&
    253       (self->histogram[candidate_delay] > self->last_delay_histogram);
    254 
    255   return is_robust;
    256 }
    257 
    258 void WebRtc_FreeBinaryDelayEstimatorFarend(BinaryDelayEstimatorFarend* self) {
    259 
    260   if (self == NULL) {
    261     return;
    262   }
    263 
    264   free(self->binary_far_history);
    265   self->binary_far_history = NULL;
    266 
    267   free(self->far_bit_counts);
    268   self->far_bit_counts = NULL;
    269 
    270   free(self);
    271 }
    272 
    273 BinaryDelayEstimatorFarend* WebRtc_CreateBinaryDelayEstimatorFarend(
    274     int history_size) {
    275   BinaryDelayEstimatorFarend* self = NULL;
    276 
    277   if (history_size > 1) {
    278     // Sanity conditions fulfilled.
    279     self = malloc(sizeof(BinaryDelayEstimatorFarend));
    280   }
    281   if (self == NULL) {
    282     return NULL;
    283   }
    284 
    285   self->history_size = 0;
    286   self->binary_far_history = NULL;
    287   self->far_bit_counts = NULL;
    288   if (WebRtc_AllocateFarendBufferMemory(self, history_size) == 0) {
    289     WebRtc_FreeBinaryDelayEstimatorFarend(self);
    290     self = NULL;
    291   }
    292   return self;
    293 }
    294 
    295 int WebRtc_AllocateFarendBufferMemory(BinaryDelayEstimatorFarend* self,
    296                                       int history_size) {
    297   assert(self != NULL);
    298   // (Re-)Allocate memory for history buffers.
    299   self->binary_far_history =
    300       realloc(self->binary_far_history,
    301               history_size * sizeof(*self->binary_far_history));
    302   self->far_bit_counts = realloc(self->far_bit_counts,
    303                                  history_size * sizeof(*self->far_bit_counts));
    304   if ((self->binary_far_history == NULL) || (self->far_bit_counts == NULL)) {
    305     history_size = 0;
    306   }
    307   // Fill with zeros if we have expanded the buffers.
    308   if (history_size > self->history_size) {
    309     int size_diff = history_size - self->history_size;
    310     memset(&self->binary_far_history[self->history_size],
    311            0,
    312            sizeof(*self->binary_far_history) * size_diff);
    313     memset(&self->far_bit_counts[self->history_size],
    314            0,
    315            sizeof(*self->far_bit_counts) * size_diff);
    316   }
    317   self->history_size = history_size;
    318 
    319   return self->history_size;
    320 }
    321 
    322 void WebRtc_InitBinaryDelayEstimatorFarend(BinaryDelayEstimatorFarend* self) {
    323   assert(self != NULL);
    324   memset(self->binary_far_history, 0, sizeof(uint32_t) * self->history_size);
    325   memset(self->far_bit_counts, 0, sizeof(int) * self->history_size);
    326 }
    327 
    328 void WebRtc_SoftResetBinaryDelayEstimatorFarend(
    329     BinaryDelayEstimatorFarend* self, int delay_shift) {
    330   int abs_shift = abs(delay_shift);
    331   int shift_size = 0;
    332   int dest_index = 0;
    333   int src_index = 0;
    334   int padding_index = 0;
    335 
    336   assert(self != NULL);
    337   shift_size = self->history_size - abs_shift;
    338   assert(shift_size > 0);
    339   if (delay_shift == 0) {
    340     return;
    341   } else if (delay_shift > 0) {
    342     dest_index = abs_shift;
    343   } else if (delay_shift < 0) {
    344     src_index = abs_shift;
    345     padding_index = shift_size;
    346   }
    347 
    348   // Shift and zero pad buffers.
    349   memmove(&self->binary_far_history[dest_index],
    350           &self->binary_far_history[src_index],
    351           sizeof(*self->binary_far_history) * shift_size);
    352   memset(&self->binary_far_history[padding_index], 0,
    353          sizeof(*self->binary_far_history) * abs_shift);
    354   memmove(&self->far_bit_counts[dest_index],
    355           &self->far_bit_counts[src_index],
    356           sizeof(*self->far_bit_counts) * shift_size);
    357   memset(&self->far_bit_counts[padding_index], 0,
    358          sizeof(*self->far_bit_counts) * abs_shift);
    359 }
    360 
    361 void WebRtc_AddBinaryFarSpectrum(BinaryDelayEstimatorFarend* handle,
    362                                  uint32_t binary_far_spectrum) {
    363   assert(handle != NULL);
    364   // Shift binary spectrum history and insert current |binary_far_spectrum|.
    365   memmove(&(handle->binary_far_history[1]), &(handle->binary_far_history[0]),
    366           (handle->history_size - 1) * sizeof(uint32_t));
    367   handle->binary_far_history[0] = binary_far_spectrum;
    368 
    369   // Shift history of far-end binary spectrum bit counts and insert bit count
    370   // of current |binary_far_spectrum|.
    371   memmove(&(handle->far_bit_counts[1]), &(handle->far_bit_counts[0]),
    372           (handle->history_size - 1) * sizeof(int));
    373   handle->far_bit_counts[0] = BitCount(binary_far_spectrum);
    374 }
    375 
    376 void WebRtc_FreeBinaryDelayEstimator(BinaryDelayEstimator* self) {
    377 
    378   if (self == NULL) {
    379     return;
    380   }
    381 
    382   free(self->mean_bit_counts);
    383   self->mean_bit_counts = NULL;
    384 
    385   free(self->bit_counts);
    386   self->bit_counts = NULL;
    387 
    388   free(self->binary_near_history);
    389   self->binary_near_history = NULL;
    390 
    391   free(self->histogram);
    392   self->histogram = NULL;
    393 
    394   // BinaryDelayEstimator does not have ownership of |farend|, hence we do not
    395   // free the memory here. That should be handled separately by the user.
    396   self->farend = NULL;
    397 
    398   free(self);
    399 }
    400 
    401 BinaryDelayEstimator* WebRtc_CreateBinaryDelayEstimator(
    402     BinaryDelayEstimatorFarend* farend, int max_lookahead) {
    403   BinaryDelayEstimator* self = NULL;
    404 
    405   if ((farend != NULL) && (max_lookahead >= 0)) {
    406     // Sanity conditions fulfilled.
    407     self = malloc(sizeof(BinaryDelayEstimator));
    408   }
    409   if (self == NULL) {
    410     return NULL;
    411   }
    412 
    413   self->farend = farend;
    414   self->near_history_size = max_lookahead + 1;
    415   self->history_size = 0;
    416   self->robust_validation_enabled = 0;  // Disabled by default.
    417   self->allowed_offset = 0;
    418 
    419   self->lookahead = max_lookahead;
    420 
    421   // Allocate memory for spectrum and history buffers.
    422   self->mean_bit_counts = NULL;
    423   self->bit_counts = NULL;
    424   self->histogram = NULL;
    425   self->binary_near_history =
    426       malloc((max_lookahead + 1) * sizeof(*self->binary_near_history));
    427   if (self->binary_near_history == NULL ||
    428       WebRtc_AllocateHistoryBufferMemory(self, farend->history_size) == 0) {
    429     WebRtc_FreeBinaryDelayEstimator(self);
    430     self = NULL;
    431   }
    432 
    433   return self;
    434 }
    435 
    436 int WebRtc_AllocateHistoryBufferMemory(BinaryDelayEstimator* self,
    437                                        int history_size) {
    438   BinaryDelayEstimatorFarend* far = self->farend;
    439   // (Re-)Allocate memory for spectrum and history buffers.
    440   if (history_size != far->history_size) {
    441     // Only update far-end buffers if we need.
    442     history_size = WebRtc_AllocateFarendBufferMemory(far, history_size);
    443   }
    444   // The extra array element in |mean_bit_counts| and |histogram| is a dummy
    445   // element only used while |last_delay| == -2, i.e., before we have a valid
    446   // estimate.
    447   self->mean_bit_counts =
    448       realloc(self->mean_bit_counts,
    449               (history_size + 1) * sizeof(*self->mean_bit_counts));
    450   self->bit_counts =
    451       realloc(self->bit_counts, history_size * sizeof(*self->bit_counts));
    452   self->histogram =
    453       realloc(self->histogram, (history_size + 1) * sizeof(*self->histogram));
    454 
    455   if ((self->mean_bit_counts == NULL) ||
    456       (self->bit_counts == NULL) ||
    457       (self->histogram == NULL)) {
    458     history_size = 0;
    459   }
    460   // Fill with zeros if we have expanded the buffers.
    461   if (history_size > self->history_size) {
    462     int size_diff = history_size - self->history_size;
    463     memset(&self->mean_bit_counts[self->history_size],
    464            0,
    465            sizeof(*self->mean_bit_counts) * size_diff);
    466     memset(&self->bit_counts[self->history_size],
    467            0,
    468            sizeof(*self->bit_counts) * size_diff);
    469     memset(&self->histogram[self->history_size],
    470            0,
    471            sizeof(*self->histogram) * size_diff);
    472   }
    473   self->history_size = history_size;
    474 
    475   return self->history_size;
    476 }
    477 
    478 void WebRtc_InitBinaryDelayEstimator(BinaryDelayEstimator* self) {
    479   int i = 0;
    480   assert(self != NULL);
    481 
    482   memset(self->bit_counts, 0, sizeof(int32_t) * self->history_size);
    483   memset(self->binary_near_history,
    484          0,
    485          sizeof(uint32_t) * self->near_history_size);
    486   for (i = 0; i <= self->history_size; ++i) {
    487     self->mean_bit_counts[i] = (20 << 9);  // 20 in Q9.
    488     self->histogram[i] = 0.f;
    489   }
    490   self->minimum_probability = kMaxBitCountsQ9;  // 32 in Q9.
    491   self->last_delay_probability = (int) kMaxBitCountsQ9;  // 32 in Q9.
    492 
    493   // Default return value if we're unable to estimate. -1 is used for errors.
    494   self->last_delay = -2;
    495 
    496   self->last_candidate_delay = -2;
    497   self->compare_delay = self->history_size;
    498   self->candidate_hits = 0;
    499   self->last_delay_histogram = 0.f;
    500 }
    501 
    502 int WebRtc_SoftResetBinaryDelayEstimator(BinaryDelayEstimator* self,
    503                                          int delay_shift) {
    504   int lookahead = 0;
    505   assert(self != NULL);
    506   lookahead = self->lookahead;
    507   self->lookahead -= delay_shift;
    508   if (self->lookahead < 0) {
    509     self->lookahead = 0;
    510   }
    511   if (self->lookahead > self->near_history_size - 1) {
    512     self->lookahead = self->near_history_size - 1;
    513   }
    514   return lookahead - self->lookahead;
    515 }
    516 
    517 int WebRtc_ProcessBinarySpectrum(BinaryDelayEstimator* self,
    518                                  uint32_t binary_near_spectrum) {
    519   int i = 0;
    520   int candidate_delay = -1;
    521   int valid_candidate = 0;
    522 
    523   int32_t value_best_candidate = kMaxBitCountsQ9;
    524   int32_t value_worst_candidate = 0;
    525   int32_t valley_depth = 0;
    526 
    527   assert(self != NULL);
    528   if (self->farend->history_size != self->history_size) {
    529     // Non matching history sizes.
    530     return -1;
    531   }
    532   if (self->near_history_size > 1) {
    533     // If we apply lookahead, shift near-end binary spectrum history. Insert
    534     // current |binary_near_spectrum| and pull out the delayed one.
    535     memmove(&(self->binary_near_history[1]), &(self->binary_near_history[0]),
    536             (self->near_history_size - 1) * sizeof(uint32_t));
    537     self->binary_near_history[0] = binary_near_spectrum;
    538     binary_near_spectrum = self->binary_near_history[self->lookahead];
    539   }
    540 
    541   // Compare with delayed spectra and store the |bit_counts| for each delay.
    542   BitCountComparison(binary_near_spectrum, self->farend->binary_far_history,
    543                      self->history_size, self->bit_counts);
    544 
    545   // Update |mean_bit_counts|, which is the smoothed version of |bit_counts|.
    546   for (i = 0; i < self->history_size; i++) {
    547     // |bit_counts| is constrained to [0, 32], meaning we can smooth with a
    548     // factor up to 2^26. We use Q9.
    549     int32_t bit_count = (self->bit_counts[i] << 9);  // Q9.
    550 
    551     // Update |mean_bit_counts| only when far-end signal has something to
    552     // contribute. If |far_bit_counts| is zero the far-end signal is weak and
    553     // we likely have a poor echo condition, hence don't update.
    554     if (self->farend->far_bit_counts[i] > 0) {
    555       // Make number of right shifts piecewise linear w.r.t. |far_bit_counts|.
    556       int shifts = kShiftsAtZero;
    557       shifts -= (kShiftsLinearSlope * self->farend->far_bit_counts[i]) >> 4;
    558       WebRtc_MeanEstimatorFix(bit_count, shifts, &(self->mean_bit_counts[i]));
    559     }
    560   }
    561 
    562   // Find |candidate_delay|, |value_best_candidate| and |value_worst_candidate|
    563   // of |mean_bit_counts|.
    564   for (i = 0; i < self->history_size; i++) {
    565     if (self->mean_bit_counts[i] < value_best_candidate) {
    566       value_best_candidate = self->mean_bit_counts[i];
    567       candidate_delay = i;
    568     }
    569     if (self->mean_bit_counts[i] > value_worst_candidate) {
    570       value_worst_candidate = self->mean_bit_counts[i];
    571     }
    572   }
    573   valley_depth = value_worst_candidate - value_best_candidate;
    574 
    575   // The |value_best_candidate| is a good indicator on the probability of
    576   // |candidate_delay| being an accurate delay (a small |value_best_candidate|
    577   // means a good binary match). In the following sections we make a decision
    578   // whether to update |last_delay| or not.
    579   // 1) If the difference bit counts between the best and the worst delay
    580   //    candidates is too small we consider the situation to be unreliable and
    581   //    don't update |last_delay|.
    582   // 2) If the situation is reliable we update |last_delay| if the value of the
    583   //    best candidate delay has a value less than
    584   //     i) an adaptive threshold |minimum_probability|, or
    585   //    ii) this corresponding value |last_delay_probability|, but updated at
    586   //        this time instant.
    587 
    588   // Update |minimum_probability|.
    589   if ((self->minimum_probability > kProbabilityLowerLimit) &&
    590       (valley_depth > kProbabilityMinSpread)) {
    591     // The "hard" threshold can't be lower than 17 (in Q9).
    592     // The valley in the curve also has to be distinct, i.e., the
    593     // difference between |value_worst_candidate| and |value_best_candidate| has
    594     // to be large enough.
    595     int32_t threshold = value_best_candidate + kProbabilityOffset;
    596     if (threshold < kProbabilityLowerLimit) {
    597       threshold = kProbabilityLowerLimit;
    598     }
    599     if (self->minimum_probability > threshold) {
    600       self->minimum_probability = threshold;
    601     }
    602   }
    603   // Update |last_delay_probability|.
    604   // We use a Markov type model, i.e., a slowly increasing level over time.
    605   self->last_delay_probability++;
    606   // Validate |candidate_delay|.  We have a reliable instantaneous delay
    607   // estimate if
    608   //  1) The valley is distinct enough (|valley_depth| > |kProbabilityOffset|)
    609   // and
    610   //  2) The depth of the valley is deep enough
    611   //      (|value_best_candidate| < |minimum_probability|)
    612   //     and deeper than the best estimate so far
    613   //      (|value_best_candidate| < |last_delay_probability|)
    614   valid_candidate = ((valley_depth > kProbabilityOffset) &&
    615       ((value_best_candidate < self->minimum_probability) ||
    616           (value_best_candidate < self->last_delay_probability)));
    617 
    618   if (self->robust_validation_enabled) {
    619     int is_histogram_valid = 0;
    620     UpdateRobustValidationStatistics(self, candidate_delay, valley_depth,
    621                                      value_best_candidate);
    622     is_histogram_valid = HistogramBasedValidation(self, candidate_delay);
    623     valid_candidate = RobustValidation(self, candidate_delay, valid_candidate,
    624                                        is_histogram_valid);
    625 
    626   }
    627   if (valid_candidate) {
    628     if (candidate_delay != self->last_delay) {
    629       self->last_delay_histogram =
    630           (self->histogram[candidate_delay] > kLastHistogramMax ?
    631               kLastHistogramMax : self->histogram[candidate_delay]);
    632       // Adjust the histogram if we made a change to |last_delay|, though it was
    633       // not the most likely one according to the histogram.
    634       if (self->histogram[candidate_delay] <
    635           self->histogram[self->compare_delay]) {
    636         self->histogram[self->compare_delay] = self->histogram[candidate_delay];
    637       }
    638     }
    639     self->last_delay = candidate_delay;
    640     if (value_best_candidate < self->last_delay_probability) {
    641       self->last_delay_probability = value_best_candidate;
    642     }
    643     self->compare_delay = self->last_delay;
    644   }
    645 
    646   return self->last_delay;
    647 }
    648 
    649 int WebRtc_binary_last_delay(BinaryDelayEstimator* self) {
    650   assert(self != NULL);
    651   return self->last_delay;
    652 }
    653 
    654 float WebRtc_binary_last_delay_quality(BinaryDelayEstimator* self) {
    655   float quality = 0;
    656   assert(self != NULL);
    657 
    658   if (self->robust_validation_enabled) {
    659     // Simply a linear function of the histogram height at delay estimate.
    660     quality = self->histogram[self->compare_delay] / kHistogramMax;
    661   } else {
    662     // Note that |last_delay_probability| states how deep the minimum of the
    663     // cost function is, so it is rather an error probability.
    664     quality = (float) (kMaxBitCountsQ9 - self->last_delay_probability) /
    665         kMaxBitCountsQ9;
    666     if (quality < 0) {
    667       quality = 0;
    668     }
    669   }
    670   return quality;
    671 }
    672 
    673 void WebRtc_MeanEstimatorFix(int32_t new_value,
    674                              int factor,
    675                              int32_t* mean_value) {
    676   int32_t diff = new_value - *mean_value;
    677 
    678   // mean_new = mean_value + ((new_value - mean_value) >> factor);
    679   if (diff < 0) {
    680     diff = -((-diff) >> factor);
    681   } else {
    682     diff = (diff >> factor);
    683   }
    684   *mean_value += diff;
    685 }
    686