1/*
2 *  Copyright (c) 2011 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 "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.
19static const int kShiftsAtZero = 13;  // Right shifts at zero binary spectrum.
20static const int kShiftsLinearSlope = 3;
21
22static const int32_t kProbabilityOffset = 1024;  // 2 in Q9.
23static const int32_t kProbabilityLowerLimit = 8704;  // 17 in Q9.
24static const int32_t kProbabilityMinSpread = 2816;  // 5.5 in Q9.
25
26// Counts and returns number of bits of a 32-bit word.
27static int BitCount(uint32_t u32) {
28  uint32_t tmp = u32 - ((u32 >> 1) & 033333333333) -
29      ((u32 >> 2) & 011111111111);
30  tmp = ((tmp + (tmp >> 3)) & 030707070707);
31  tmp = (tmp + (tmp >> 6));
32  tmp = (tmp + (tmp >> 12) + (tmp >> 24)) & 077;
33
34  return ((int) tmp);
35}
36
37// Compares the |binary_vector| with all rows of the |binary_matrix| and counts
38// per row the number of times they have the same value.
39//
40// Inputs:
41//      - binary_vector     : binary "vector" stored in a long
42//      - binary_matrix     : binary "matrix" stored as a vector of long
43//      - matrix_size       : size of binary "matrix"
44//
45// Output:
46//      - bit_counts        : "Vector" stored as a long, containing for each
47//                            row the number of times the matrix row and the
48//                            input vector have the same value
49//
50static void BitCountComparison(uint32_t binary_vector,
51                               const uint32_t* binary_matrix,
52                               int matrix_size,
53                               int32_t* bit_counts) {
54  int n = 0;
55
56  // Compare |binary_vector| with all rows of the |binary_matrix|
57  for (; n < matrix_size; n++) {
58    bit_counts[n] = (int32_t) BitCount(binary_vector ^ binary_matrix[n]);
59  }
60}
61
62int WebRtc_FreeBinaryDelayEstimator(BinaryDelayEstimator* handle) {
63  assert(handle != NULL);
64
65  if (handle->mean_bit_counts != NULL) {
66    free(handle->mean_bit_counts);
67    handle->mean_bit_counts = NULL;
68  }
69  if (handle->bit_counts != NULL) {
70    free(handle->bit_counts);
71    handle->bit_counts = NULL;
72  }
73  if (handle->binary_far_history != NULL) {
74    free(handle->binary_far_history);
75    handle->binary_far_history = NULL;
76  }
77  if (handle->binary_near_history != NULL) {
78    free(handle->binary_near_history);
79    handle->binary_near_history = NULL;
80  }
81  if (handle->far_bit_counts != NULL) {
82    free(handle->far_bit_counts);
83    handle->far_bit_counts = NULL;
84  }
85
86  free(handle);
87
88  return 0;
89}
90
91int WebRtc_CreateBinaryDelayEstimator(BinaryDelayEstimator** handle,
92                                      int max_delay,
93                                      int lookahead) {
94  BinaryDelayEstimator* self = NULL;
95  int history_size = max_delay + lookahead;
96
97  if (handle == NULL) {
98    return -1;
99  }
100  if (max_delay < 0) {
101    return -1;
102  }
103  if (lookahead < 0) {
104    return -1;
105  }
106  if (history_size < 2) {
107    // Must be this large for buffer shifting.
108    return -1;
109  }
110
111  self = malloc(sizeof(BinaryDelayEstimator));
112  *handle = self;
113  if (self == NULL) {
114    return -1;
115  }
116
117  self->mean_bit_counts = NULL;
118  self->bit_counts = NULL;
119  self->binary_far_history = NULL;
120  self->far_bit_counts = NULL;
121
122  self->history_size = history_size;
123  self->near_history_size = lookahead + 1;
124
125  // Allocate memory for spectrum buffers.
126  self->mean_bit_counts = malloc(history_size * sizeof(int32_t));
127  if (self->mean_bit_counts == NULL) {
128    WebRtc_FreeBinaryDelayEstimator(self);
129    self = NULL;
130    return -1;
131  }
132  self->bit_counts = malloc(history_size * sizeof(int32_t));
133  if (self->bit_counts == NULL) {
134    WebRtc_FreeBinaryDelayEstimator(self);
135    self = NULL;
136    return -1;
137  }
138  // Allocate memory for history buffers.
139  self->binary_far_history = malloc(history_size * sizeof(uint32_t));
140  if (self->binary_far_history == NULL) {
141    WebRtc_FreeBinaryDelayEstimator(self);
142    self = NULL;
143    return -1;
144  }
145  self->binary_near_history = malloc(self->near_history_size *
146      sizeof(uint32_t));
147  if (self->binary_near_history == NULL) {
148    WebRtc_FreeBinaryDelayEstimator(self);
149    self = NULL;
150    return -1;
151  }
152  self->far_bit_counts = malloc(history_size * sizeof(int));
153  if (self->far_bit_counts == NULL) {
154    WebRtc_FreeBinaryDelayEstimator(self);
155    self = NULL;
156    return -1;
157  }
158
159  return 0;
160}
161
162int WebRtc_InitBinaryDelayEstimator(BinaryDelayEstimator* handle) {
163  int i = 0;
164  assert(handle != NULL);
165
166  memset(handle->bit_counts, 0, sizeof(int32_t) * handle->history_size);
167  memset(handle->binary_far_history, 0,
168         sizeof(uint32_t) * handle->history_size);
169  memset(handle->binary_near_history, 0,
170         sizeof(uint32_t) * handle->near_history_size);
171  memset(handle->far_bit_counts, 0, sizeof(int) * handle->history_size);
172  for (i = 0; i < handle->history_size; ++i) {
173    handle->mean_bit_counts[i] = (20 << 9);  // 20 in Q9.
174  }
175  handle->minimum_probability = (32 << 9);  // 32 in Q9.
176  handle->last_delay_probability = (32 << 9);  // 32 in Q9.
177
178  // Default return value if we're unable to estimate. -1 is used for errors.
179  handle->last_delay = -2;
180
181  return 0;
182}
183
184int WebRtc_ProcessBinarySpectrum(BinaryDelayEstimator* handle,
185                                 uint32_t binary_far_spectrum,
186                                 uint32_t binary_near_spectrum) {
187  int i = 0;
188  int candidate_delay = -1;
189
190  int32_t value_best_candidate = 16384;  // 32 in Q9, (max |mean_bit_counts|).
191  int32_t value_worst_candidate = 0;
192
193  assert(handle != NULL);
194  // Shift binary spectrum history and insert current |binary_far_spectrum|.
195  memmove(&(handle->binary_far_history[1]), &(handle->binary_far_history[0]),
196          (handle->history_size - 1) * sizeof(uint32_t));
197  handle->binary_far_history[0] = binary_far_spectrum;
198
199  // Shift history of far-end binary spectrum bit counts and insert bit count
200  // of current |binary_far_spectrum|.
201  memmove(&(handle->far_bit_counts[1]), &(handle->far_bit_counts[0]),
202          (handle->history_size - 1) * sizeof(int));
203  handle->far_bit_counts[0] = BitCount(binary_far_spectrum);
204
205  if (handle->near_history_size > 1) {
206    // If we apply lookahead, shift near-end binary spectrum history. Insert
207    // current |binary_near_spectrum| and pull out the delayed one.
208    memmove(&(handle->binary_near_history[1]),
209            &(handle->binary_near_history[0]),
210            (handle->near_history_size - 1) * sizeof(uint32_t));
211    handle->binary_near_history[0] = binary_near_spectrum;
212    binary_near_spectrum =
213        handle->binary_near_history[handle->near_history_size - 1];
214  }
215
216  // Compare with delayed spectra and store the |bit_counts| for each delay.
217  BitCountComparison(binary_near_spectrum,
218                     handle->binary_far_history,
219                     handle->history_size,
220                     handle->bit_counts);
221
222  // Update |mean_bit_counts|, which is the smoothed version of |bit_counts|.
223  for (i = 0; i < handle->history_size; i++) {
224    // |bit_counts| is constrained to [0, 32], meaning we can smooth with a
225    // factor up to 2^26. We use Q9.
226    int32_t bit_count = (handle->bit_counts[i] << 9);  // Q9.
227
228    // Update |mean_bit_counts| only when far-end signal has something to
229    // contribute. If |far_bit_counts| is zero the far-end signal is weak and
230    // we likely have a poor echo condition, hence don't update.
231    if (handle->far_bit_counts[i] > 0) {
232      // Make number of right shifts piecewise linear w.r.t. |far_bit_counts|.
233      int shifts = kShiftsAtZero;
234      shifts -= (kShiftsLinearSlope * handle->far_bit_counts[i]) >> 4;
235      WebRtc_MeanEstimatorFix(bit_count, shifts, &(handle->mean_bit_counts[i]));
236    }
237  }
238
239  // Find |candidate_delay|, |value_best_candidate| and |value_worst_candidate|
240  // of |mean_bit_counts|.
241  for (i = 0; i < handle->history_size; i++) {
242    if (handle->mean_bit_counts[i] < value_best_candidate) {
243      value_best_candidate = handle->mean_bit_counts[i];
244      candidate_delay = i;
245    }
246    if (handle->mean_bit_counts[i] > value_worst_candidate) {
247      value_worst_candidate = handle->mean_bit_counts[i];
248    }
249  }
250
251  // The |value_best_candidate| is a good indicator on the probability of
252  // |candidate_delay| being an accurate delay (a small |value_best_candidate|
253  // means a good binary match). In the following sections we make a decision
254  // whether to update |last_delay| or not.
255  // 1) If the difference bit counts between the best and the worst delay
256  //    candidates is too small we consider the situation to be unreliable and
257  //    don't update |last_delay|.
258  // 2) If the situation is reliable we update |last_delay| if the value of the
259  //    best candidate delay has a value less than
260  //     i) an adaptive threshold |minimum_probability|, or
261  //    ii) this corresponding value |last_delay_probability|, but updated at
262  //        this time instant.
263
264  // Update |minimum_probability|.
265  if ((handle->minimum_probability > kProbabilityLowerLimit) &&
266      (value_worst_candidate - value_best_candidate > kProbabilityMinSpread)) {
267    // The "hard" threshold can't be lower than 17 (in Q9).
268    // The valley in the curve also has to be distinct, i.e., the
269    // difference between |value_worst_candidate| and |value_best_candidate| has
270    // to be large enough.
271    int32_t threshold = value_best_candidate + kProbabilityOffset;
272    if (threshold < kProbabilityLowerLimit) {
273      threshold = kProbabilityLowerLimit;
274    }
275    if (handle->minimum_probability > threshold) {
276      handle->minimum_probability = threshold;
277    }
278  }
279  // Update |last_delay_probability|.
280  // We use a Markov type model, i.e., a slowly increasing level over time.
281  handle->last_delay_probability++;
282  if (value_worst_candidate > value_best_candidate + kProbabilityOffset) {
283    // Reliable delay value for usage.
284    if (value_best_candidate < handle->minimum_probability) {
285      handle->last_delay = candidate_delay;
286    }
287    if (value_best_candidate < handle->last_delay_probability) {
288      handle->last_delay = candidate_delay;
289      // Reset |last_delay_probability|.
290      handle->last_delay_probability = value_best_candidate;
291    }
292  }
293
294  return handle->last_delay;
295}
296
297int WebRtc_binary_last_delay(BinaryDelayEstimator* handle) {
298  assert(handle != NULL);
299  return handle->last_delay;
300}
301
302int WebRtc_history_size(BinaryDelayEstimator* handle) {
303  assert(handle != NULL);
304  return handle->history_size;
305}
306
307void WebRtc_MeanEstimatorFix(int32_t new_value,
308                             int factor,
309                             int32_t* mean_value) {
310  int32_t diff = new_value - *mean_value;
311
312  // mean_new = mean_value + ((new_value - mean_value) >> factor);
313  if (diff < 0) {
314    diff = -((-diff) >> factor);
315  } else {
316    diff = (diff >> factor);
317  }
318  *mean_value += diff;
319}
320