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.
BitCount(uint32_t u32)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 //
BitCountComparison(uint32_t binary_vector,const uint32_t * binary_matrix,int matrix_size,int32_t * bit_counts)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.
UpdateRobustValidationStatistics(BinaryDelayEstimator * self,int candidate_delay,int32_t valley_depth_q14,int32_t valley_level_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.
HistogramBasedValidation(const BinaryDelayEstimator * self,int candidate_delay)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.
RobustValidation(const BinaryDelayEstimator * self,int candidate_delay,int is_instantaneous_valid,int is_histogram_valid)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
WebRtc_FreeBinaryDelayEstimatorFarend(BinaryDelayEstimatorFarend * self)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
WebRtc_CreateBinaryDelayEstimatorFarend(int history_size)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
WebRtc_AllocateFarendBufferMemory(BinaryDelayEstimatorFarend * self,int history_size)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
WebRtc_InitBinaryDelayEstimatorFarend(BinaryDelayEstimatorFarend * self)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
WebRtc_SoftResetBinaryDelayEstimatorFarend(BinaryDelayEstimatorFarend * self,int delay_shift)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
WebRtc_AddBinaryFarSpectrum(BinaryDelayEstimatorFarend * handle,uint32_t binary_far_spectrum)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
WebRtc_FreeBinaryDelayEstimator(BinaryDelayEstimator * self)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
WebRtc_CreateBinaryDelayEstimator(BinaryDelayEstimatorFarend * farend,int max_lookahead)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
WebRtc_AllocateHistoryBufferMemory(BinaryDelayEstimator * self,int history_size)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
WebRtc_InitBinaryDelayEstimator(BinaryDelayEstimator * self)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
WebRtc_SoftResetBinaryDelayEstimator(BinaryDelayEstimator * self,int delay_shift)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
WebRtc_ProcessBinarySpectrum(BinaryDelayEstimator * self,uint32_t binary_near_spectrum)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 UpdateRobustValidationStatistics(self, candidate_delay, valley_depth,
619 value_best_candidate);
620 if (self->robust_validation_enabled) {
621 int is_histogram_valid = HistogramBasedValidation(self, candidate_delay);
622 valid_candidate = RobustValidation(self, candidate_delay, valid_candidate,
623 is_histogram_valid);
624
625 }
626 if (valid_candidate) {
627 if (candidate_delay != self->last_delay) {
628 self->last_delay_histogram =
629 (self->histogram[candidate_delay] > kLastHistogramMax ?
630 kLastHistogramMax : self->histogram[candidate_delay]);
631 // Adjust the histogram if we made a change to |last_delay|, though it was
632 // not the most likely one according to the histogram.
633 if (self->histogram[candidate_delay] <
634 self->histogram[self->compare_delay]) {
635 self->histogram[self->compare_delay] = self->histogram[candidate_delay];
636 }
637 }
638 self->last_delay = candidate_delay;
639 if (value_best_candidate < self->last_delay_probability) {
640 self->last_delay_probability = value_best_candidate;
641 }
642 self->compare_delay = self->last_delay;
643 }
644
645 return self->last_delay;
646 }
647
WebRtc_binary_last_delay(BinaryDelayEstimator * self)648 int WebRtc_binary_last_delay(BinaryDelayEstimator* self) {
649 assert(self != NULL);
650 return self->last_delay;
651 }
652
WebRtc_binary_last_delay_quality(BinaryDelayEstimator * self)653 float WebRtc_binary_last_delay_quality(BinaryDelayEstimator* self) {
654 float quality = 0;
655 assert(self != NULL);
656
657 if (self->robust_validation_enabled) {
658 // Simply a linear function of the histogram height at delay estimate.
659 quality = self->histogram[self->compare_delay] / kHistogramMax;
660 } else {
661 // Note that |last_delay_probability| states how deep the minimum of the
662 // cost function is, so it is rather an error probability.
663 quality = (float) (kMaxBitCountsQ9 - self->last_delay_probability) /
664 kMaxBitCountsQ9;
665 if (quality < 0) {
666 quality = 0;
667 }
668 }
669 return quality;
670 }
671
WebRtc_MeanEstimatorFix(int32_t new_value,int factor,int32_t * mean_value)672 void WebRtc_MeanEstimatorFix(int32_t new_value,
673 int factor,
674 int32_t* mean_value) {
675 int32_t diff = new_value - *mean_value;
676
677 // mean_new = mean_value + ((new_value - mean_value) >> factor);
678 if (diff < 0) {
679 diff = -((-diff) >> factor);
680 } else {
681 diff = (diff >> factor);
682 }
683 *mean_value += diff;
684 }
685