Adding upstream version 1:115.7.0.upstream/1%115.7.0upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 249 insertions, 0 deletions

diff --git a/third_party/libwebrtc/common_audio/signal_processing/levinson_durbin.c b/third_party/libwebrtc/common_audio/signal_processing/levinson_durbin.c
new file mode 100644
index 0000000000..2c5cbaeeaa
--- /dev/null
+++ b/third_party/libwebrtc/common_audio/signal_processing/levinson_durbin.c
@@ -0,0 +1,249 @@
+/*
+ *  Copyright (c) 2011 The WebRTC project authors. All Rights Reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+
+/*
+ * This file contains the function WebRtcSpl_LevinsonDurbin().
+ * The description header can be found in signal_processing_library.h
+ *
+ */
+
+#include "common_audio/signal_processing/include/signal_processing_library.h"
+#include "rtc_base/sanitizer.h"
+
+#define SPL_LEVINSON_MAXORDER 20
+
+int16_t RTC_NO_SANITIZE("signed-integer-overflow")  // bugs.webrtc.org/5486
+WebRtcSpl_LevinsonDurbin(const int32_t* R, int16_t* A, int16_t* K,
+                         size_t order)
+{
+    size_t i, j;
+    // Auto-correlation coefficients in high precision
+    int16_t R_hi[SPL_LEVINSON_MAXORDER + 1], R_low[SPL_LEVINSON_MAXORDER + 1];
+    // LPC coefficients in high precision
+    int16_t A_hi[SPL_LEVINSON_MAXORDER + 1], A_low[SPL_LEVINSON_MAXORDER + 1];
+    // LPC coefficients for next iteration
+    int16_t A_upd_hi[SPL_LEVINSON_MAXORDER + 1], A_upd_low[SPL_LEVINSON_MAXORDER + 1];
+    // Reflection coefficient in high precision
+    int16_t K_hi, K_low;
+    // Prediction gain Alpha in high precision and with scale factor
+    int16_t Alpha_hi, Alpha_low, Alpha_exp;
+    int16_t tmp_hi, tmp_low;
+    int32_t temp1W32, temp2W32, temp3W32;
+    int16_t norm;
+
+    // Normalize the autocorrelation R[0]...R[order+1]
+
+    norm = WebRtcSpl_NormW32(R[0]);
+
+    for (i = 0; i <= order; ++i)
+    {
+        temp1W32 = R[i] * (1 << norm);
+        // UBSan: 12 * 268435456 cannot be represented in type 'int'
+
+        // Put R in hi and low format
+        R_hi[i] = (int16_t)(temp1W32 >> 16);
+        R_low[i] = (int16_t)((temp1W32 - ((int32_t)R_hi[i] * 65536)) >> 1);
+    }
+
+    // K = A[1] = -R[1] / R[0]
+
+    temp2W32 = R[1] * (1 << norm); // R[1] in Q31
+    temp3W32 = WEBRTC_SPL_ABS_W32(temp2W32); // abs R[1]
+    temp1W32 = WebRtcSpl_DivW32HiLow(temp3W32, R_hi[0], R_low[0]); // abs(R[1])/R[0] in Q31
+    // Put back the sign on R[1]
+    if (temp2W32 > 0)
+    {
+        temp1W32 = -temp1W32;
+    }
+
+    // Put K in hi and low format
+    K_hi = (int16_t)(temp1W32 >> 16);
+    K_low = (int16_t)((temp1W32 - ((int32_t)K_hi * 65536)) >> 1);
+
+    // Store first reflection coefficient
+    K[0] = K_hi;
+
+    temp1W32 >>= 4;  // A[1] in Q27.
+
+    // Put A[1] in hi and low format
+    A_hi[1] = (int16_t)(temp1W32 >> 16);
+    A_low[1] = (int16_t)((temp1W32 - ((int32_t)A_hi[1] * 65536)) >> 1);
+
+    // Alpha = R[0] * (1-K^2)
+
+    temp1W32 = ((K_hi * K_low >> 14) + K_hi * K_hi) * 2;  // = k^2 in Q31
+
+    temp1W32 = WEBRTC_SPL_ABS_W32(temp1W32); // Guard against <0
+    temp1W32 = (int32_t)0x7fffffffL - temp1W32; // temp1W32 = (1 - K[0]*K[0]) in Q31
+
+    // Store temp1W32 = 1 - K[0]*K[0] on hi and low format
+    tmp_hi = (int16_t)(temp1W32 >> 16);
+    tmp_low = (int16_t)((temp1W32 - ((int32_t)tmp_hi << 16)) >> 1);
+
+    // Calculate Alpha in Q31
+    temp1W32 = (R_hi[0] * tmp_hi + (R_hi[0] * tmp_low >> 15) +
+        (R_low[0] * tmp_hi >> 15)) << 1;
+
+    // Normalize Alpha and put it in hi and low format
+
+    Alpha_exp = WebRtcSpl_NormW32(temp1W32);
+    temp1W32 = WEBRTC_SPL_LSHIFT_W32(temp1W32, Alpha_exp);
+    Alpha_hi = (int16_t)(temp1W32 >> 16);
+    Alpha_low = (int16_t)((temp1W32 - ((int32_t)Alpha_hi << 16)) >> 1);
+
+    // Perform the iterative calculations in the Levinson-Durbin algorithm
+
+    for (i = 2; i <= order; i++)
+    {
+        /*                    ----
+         temp1W32 =  R[i] + > R[j]*A[i-j]
+         /
+         ----
+         j=1..i-1
+         */
+
+        temp1W32 = 0;
+
+        for (j = 1; j < i; j++)
+        {
+          // temp1W32 is in Q31
+          temp1W32 += (R_hi[j] * A_hi[i - j] * 2) +
+              (((R_hi[j] * A_low[i - j] >> 15) +
+              (R_low[j] * A_hi[i - j] >> 15)) * 2);
+        }
+
+        temp1W32 = temp1W32 * 16;
+        temp1W32 += ((int32_t)R_hi[i] * 65536)
+                + WEBRTC_SPL_LSHIFT_W32((int32_t)R_low[i], 1);
+
+        // K = -temp1W32 / Alpha
+        temp2W32 = WEBRTC_SPL_ABS_W32(temp1W32); // abs(temp1W32)
+        temp3W32 = WebRtcSpl_DivW32HiLow(temp2W32, Alpha_hi, Alpha_low); // abs(temp1W32)/Alpha
+
+        // Put the sign of temp1W32 back again
+        if (temp1W32 > 0)
+        {
+            temp3W32 = -temp3W32;
+        }
+
+        // Use the Alpha shifts from earlier to de-normalize
+        norm = WebRtcSpl_NormW32(temp3W32);
+        if ((Alpha_exp <= norm) || (temp3W32 == 0))
+        {
+            temp3W32 = temp3W32 * (1 << Alpha_exp);
+        } else
+        {
+            if (temp3W32 > 0)
+            {
+                temp3W32 = (int32_t)0x7fffffffL;
+            } else
+            {
+                temp3W32 = (int32_t)0x80000000L;
+            }
+        }
+
+        // Put K on hi and low format
+        K_hi = (int16_t)(temp3W32 >> 16);
+        K_low = (int16_t)((temp3W32 - ((int32_t)K_hi * 65536)) >> 1);
+
+        // Store Reflection coefficient in Q15
+        K[i - 1] = K_hi;
+
+        // Test for unstable filter.
+        // If unstable return 0 and let the user decide what to do in that case
+
+        if ((int32_t)WEBRTC_SPL_ABS_W16(K_hi) > (int32_t)32750)
+        {
+            return 0; // Unstable filter
+        }
+
+        /*
+         Compute updated LPC coefficient: Anew[i]
+         Anew[j]= A[j] + K*A[i-j]   for j=1..i-1
+         Anew[i]= K
+         */
+
+        for (j = 1; j < i; j++)
+        {
+            // temp1W32 = A[j] in Q27
+            temp1W32 = (int32_t)A_hi[j] * 65536
+                    + WEBRTC_SPL_LSHIFT_W32((int32_t)A_low[j],1);
+
+            // temp1W32 += K*A[i-j] in Q27
+            temp1W32 += (K_hi * A_hi[i - j] + (K_hi * A_low[i - j] >> 15) +
+                (K_low * A_hi[i - j] >> 15)) * 2;
+
+            // Put Anew in hi and low format
+            A_upd_hi[j] = (int16_t)(temp1W32 >> 16);
+            A_upd_low[j] = (int16_t)(
+                (temp1W32 - ((int32_t)A_upd_hi[j] * 65536)) >> 1);
+        }
+
+        // temp3W32 = K in Q27 (Convert from Q31 to Q27)
+        temp3W32 >>= 4;
+
+        // Store Anew in hi and low format
+        A_upd_hi[i] = (int16_t)(temp3W32 >> 16);
+        A_upd_low[i] = (int16_t)(
+            (temp3W32 - ((int32_t)A_upd_hi[i] * 65536)) >> 1);
+
+        // Alpha = Alpha * (1-K^2)
+
+        temp1W32 = ((K_hi * K_low >> 14) + K_hi * K_hi) * 2;  // K*K in Q31
+
+        temp1W32 = WEBRTC_SPL_ABS_W32(temp1W32); // Guard against <0
+        temp1W32 = (int32_t)0x7fffffffL - temp1W32; // 1 - K*K  in Q31
+
+        // Convert 1- K^2 in hi and low format
+        tmp_hi = (int16_t)(temp1W32 >> 16);
+        tmp_low = (int16_t)((temp1W32 - ((int32_t)tmp_hi << 16)) >> 1);
+
+        // Calculate Alpha = Alpha * (1-K^2) in Q31
+        temp1W32 = (Alpha_hi * tmp_hi + (Alpha_hi * tmp_low >> 15) +
+            (Alpha_low * tmp_hi >> 15)) << 1;
+
+        // Normalize Alpha and store it on hi and low format
+
+        norm = WebRtcSpl_NormW32(temp1W32);
+        temp1W32 = WEBRTC_SPL_LSHIFT_W32(temp1W32, norm);
+
+        Alpha_hi = (int16_t)(temp1W32 >> 16);
+        Alpha_low = (int16_t)((temp1W32 - ((int32_t)Alpha_hi << 16)) >> 1);
+
+        // Update the total normalization of Alpha
+        Alpha_exp = Alpha_exp + norm;
+
+        // Update A[]
+
+        for (j = 1; j <= i; j++)
+        {
+            A_hi[j] = A_upd_hi[j];
+            A_low[j] = A_upd_low[j];
+        }
+    }
+
+    /*
+     Set A[0] to 1.0 and store the A[i] i=1...order in Q12
+     (Convert from Q27 and use rounding)
+     */
+
+    A[0] = 4096;
+
+    for (i = 1; i <= order; i++)
+    {
+        // temp1W32 in Q27
+        temp1W32 = (int32_t)A_hi[i] * 65536
+                + WEBRTC_SPL_LSHIFT_W32((int32_t)A_low[i], 1);
+        // Round and store upper word
+        A[i] = (int16_t)(((temp1W32 * 2) + 32768) >> 16);
+    }
+    return 1; // Stable filters
+}