Line data    Source code

       1             : /*
       2             :  *  Copyright (c) 2016 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_coding/neteq/cross_correlation.h"
      12             : 
      13             : #include <cstdlib>
      14             : #include <limits>
      15             : 
      16             : #include "webrtc/common_audio/signal_processing/include/signal_processing_library.h"
      17             : 
      18             : namespace webrtc {
      19             : 
      20             : // This function decides the overflow-protecting scaling and calls
      21             : // WebRtcSpl_CrossCorrelation.
      22           0 : int CrossCorrelationWithAutoShift(const int16_t* sequence_1,
      23             :                                   const int16_t* sequence_2,
      24             :                                   size_t sequence_1_length,
      25             :                                   size_t cross_correlation_length,
      26             :                                   int cross_correlation_step,
      27             :                                   int32_t* cross_correlation) {
      28             :   // Find the maximum absolute value of sequence_1 and 2.
      29           0 :   const int16_t max_1 = WebRtcSpl_MaxAbsValueW16(sequence_1, sequence_1_length);
      30             :   const int sequence_2_shift =
      31           0 :       cross_correlation_step * (static_cast<int>(cross_correlation_length) - 1);
      32             :   const int16_t* sequence_2_start =
      33           0 :       sequence_2_shift >= 0 ? sequence_2 : sequence_2 + sequence_2_shift;
      34             :   const size_t sequence_2_length =
      35           0 :       sequence_1_length + std::abs(sequence_2_shift);
      36             :   const int16_t max_2 =
      37           0 :       WebRtcSpl_MaxAbsValueW16(sequence_2_start, sequence_2_length);
      38             : 
      39             :   // In order to avoid overflow when computing the sum we should scale the
      40             :   // samples so that (in_vector_length * max_1 * max_2) will not overflow.
      41             :   // Expected scaling fulfills
      42             :   // 1) sufficient:
      43             :   //    sequence_1_length * (max_1 * max_2 >> scaling) <= 0x7fffffff;
      44             :   // 2) necessary:
      45             :   //    if (scaling > 0)
      46             :   //      sequence_1_length * (max_1 * max_2 >> (scaling - 1)) > 0x7fffffff;
      47             :   // The following calculation fulfills 1) and almost fulfills 2).
      48             :   // There are some corner cases that 2) is not satisfied, e.g.,
      49             :   // max_1 = 17, max_2 = 30848, sequence_1_length = 4095, in such case,
      50             :   // optimal scaling is 0, while the following calculation results in 1.
      51           0 :   const int32_t factor = (max_1 * max_2) / (std::numeric_limits<int32_t>::max()
      52           0 :       / static_cast<int32_t>(sequence_1_length));
      53           0 :   const int scaling = factor == 0 ? 0 : 31 - WebRtcSpl_NormW32(factor);
      54             : 
      55             :   WebRtcSpl_CrossCorrelation(cross_correlation, sequence_1, sequence_2,
      56             :                              sequence_1_length, cross_correlation_length,
      57           0 :                              scaling, cross_correlation_step);
      58             : 
      59           0 :   return scaling;
      60             : }
      61             : 
      62             : }  // namespace webrtc