Fix for left shift of potentially negative value.

webrtc/common_audio/signal_processing/levinson_durbin.c

 /*
  *  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.
  */
 
@@ skipping 130 matching lines @@
             {
                 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);

[ivoc, 2017/01/09 16:52:35]

When temp3W32 is a negative number (which can happen), K_hi will be negative
while K_low will be a positive number. 

[kwiberg-webrtc, 2017/01/09 17:51:37]

So the value that's being shifted (the "shiftee"?) is always nonzero?

[ivoc, 2017/01/10 09:18:27]

Well, the shift on this line is not a problem, it's the one down below that's
troublesome. I just thought I'd highlight where K_hi and K_low come from.

[kwiberg-webrtc, 2017/01/10 10:08:00]

Got it.

 
         // 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
@@ skipping 24 matching lines @@
         // 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) << 1;  // K*K in Q31
+        temp1W32 = ((K_hi * K_low >> 14) + K_hi * K_hi) * 2;  // K*K in Q31

[ivoc, 2017/01/09 16:52:35]

When K_hi is negative and K_low is positive, ((K_hi * K_low >> 14) + K_hi *
K_hi) can be negative.

[kwiberg-webrtc, 2017/01/09 17:51:36]

Umm... I would've thought that K*K would always be a positive number. Do you
have a specific example that illustrates the negative case?

[ivoc, 2017/01/10 09:18:27]

This is from the testcase that the fuzzer came up with, if temp3W32 = -20288,
then K_hi will be -1, and K_low will be 22624. With those values, ((K_hi * K_low
>> 14) + K_hi * K_hi) is equal to -1.
I agree that it's strange that K*K results in a negative value, maybe this code
is not calculating the correct result? 

The way I understand it, K = K_hi * 2^16 + K_low * 2
That means that K*K = K_hi^2 * 2^32 + 4 * K_hi * K_low * 2^16 + 4 * K_low^2.
In Q31 that becomes: K_hi^2 + K_hi * K_low * 2^-14 + K_low^2 * 2^-30
It looks to me like the problem in this example is that K_hi has a non-zero
value (due to how bitshifting works on negative integers) while abs(K) is
smaller than 2^16, as I think the correct answer should be 0 for this case.
WDYT?

[kwiberg-webrtc, 2017/01/10 10:08:01]

Hmm. (a+b)^2 = a^2 + 2*a*b + b^2 should be nonzero for any real a and b, no
matter how we came up with the values, and AFAICT we have no overflow in this
expression. Is it simply that it wasn't safe to neglect the (K_low * K_low) >>
28 term? With K_low == 22624, it would have the value 1...

Of course, this error may be on purpose, in which case -1 is simply an
acceptable approximation of 0. And in that case, your original change is the
right one, since the approximate square is not guaranteed to be nonnegative.

[ivoc, 2017/01/10 10:17:24]

In the line below this one they guard against temp1W32 values below zero, so it
seems like the original author was aware that this expression can yield negative
results. Shall we just leave it like this then?

[hlundin-webrtc, 2017/01/10 10:18:40]

I say leave it like this.

[kwiberg-webrtc, 2017/01/10 10:32:58]

Yes. (I'm not sure that leaving out the small term and then doing an abs to
handle the resulting error is actually faster than not leaving it out, but this
CL should not concern itself with that.)

 
         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) +
@@ skipping 29 matching lines @@
     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
 }