webrtc/common_audio/signal_processing/levinson_durbin.c - Issue 2621693002: Fix for left shift of potentially negative value.

Unified Diff: webrtc/common_audio/signal_processing/levinson_durbin.c

Issue 2621693002: Fix for left shift of potentially negative value. (Closed)

Patch Set: Created 3 years, 11 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

View side-by-side diff with in-line comments

Index: webrtc/common_audio/signal_processing/levinson_durbin.c

diff --git a/webrtc/common_audio/signal_processing/levinson_durbin.c b/webrtc/common_audio/signal_processing/levinson_durbin.c

index 2983c56dd61f8f44f92c622601c3c3876ec69ba8..61f3721977ccb2fc16def78694aef13c0cbd99b6 100644

--- a/webrtc/common_audio/signal_processing/levinson_durbin.c

+++ b/webrtc/common_audio/signal_processing/levinson_durbin.c

@@ -193,7 +193,7 @@ int16_t WebRtcSpl_LevinsonDurbin(const int32_t* R, int16_t* A, int16_t* K,

// 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_h

kwiberg-webrtc 2017/01/09 17:51:36 Umm... I would've thought that K*K would always be

ivoc 2017/01/10 09:18:27 This is from the testcase that the fuzzer came up

kwiberg-webrtc 2017/01/10 10:08:01 Hmm. (a+b)^2 = a^2 + 2*a*b + b^2 should be nonzero

ivoc 2017/01/10 10:17:24 In the line below this one they guard against temp

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.

On 2017/01/10 10:17:24, ivoc wrote: > On 2017/01/10 10:08:01, kwiberg-webrtc wrote: > > On 2017/01/10 09:18:27, ivoc wrote: > > > On 2017/01/09 17:51:36, kwiberg-webrtc wrote: > > > > On 2017/01/09 16:52:35, ivoc wrote: > > > > > When K_hi is negative and K_low is positive, ((K_hi * K_low >> 14) + > K_hi > > * > > > > > K_hi) can be negative. > > > > > > > > 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? > > > > > > 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? > > > > 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. > > 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?

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

On 2017/01/10 10:18:40, hlundin-webrtc wrote: > On 2017/01/10 10:17:24, ivoc wrote: > > On 2017/01/10 10:08:01, kwiberg-webrtc wrote: > > > On 2017/01/10 09:18:27, ivoc wrote: > > > > On 2017/01/09 17:51:36, kwiberg-webrtc wrote: > > > > > On 2017/01/09 16:52:35, ivoc wrote: > > > > > > When K_hi is negative and K_low is positive, ((K_hi * K_low >> 14) + > > K_hi > > > * > > > > > > K_hi) can be negative. > > > > > > > > > > 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? > > > > > > > > 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? > > > > > > 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. > > > > 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? > > I say leave it like this.

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

« no previous file with comments | « no previous file | no next file » | no next file with comments »