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