Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
2621693002:
Fix for left shift of potentially negative value. (Closed)
DescriptionFix for left shift of potentially negative value.
Left shifting of negative integers is undefined behavior, and should be prevented. This CL fixes one such instance in the Levinson Durbin function.
BUG=chromium:675349
Review-Url: https://codereview.webrtc.org/2621693002
Cr-Commit-Position: refs/heads/master@{#15984}
Committed: https://chromium.googlesource.com/external/webrtc/+/abf1752ff44481cff17b5bfada8e18bf537fe27d
Patch Set 1 #
Total comments: 11
Messages
Total messages: 14 (4 generated)
ivoc@webrtc.org changed reviewers: + henrik.lundin@webrtc.org, kwiberg@webrtc.org
PTAL. https://codereview.webrtc.org/2621693002/diff/1/webrtc/common_audio/signal_pr... File webrtc/common_audio/signal_processing/levinson_durbin.c (right): https://codereview.webrtc.org/2621693002/diff/1/webrtc/common_audio/signal_pr... webrtc/common_audio/signal_processing/levinson_durbin.c:151: K_low = (int16_t)((temp3W32 - ((int32_t)K_hi * 65536)) >> 1); When temp3W32 is a negative number (which can happen), K_hi will be negative while K_low will be a positive number. https://codereview.webrtc.org/2621693002/diff/1/webrtc/common_audio/signal_pr... webrtc/common_audio/signal_processing/levinson_durbin.c:196: temp1W32 = ((K_hi * K_low >> 14) + K_hi * K_hi) * 2; // K*K in Q31 When K_hi is negative and K_low is positive, ((K_hi * K_low >> 14) + K_hi * K_hi) can be negative.
https://codereview.webrtc.org/2621693002/diff/1/webrtc/common_audio/signal_pr... File webrtc/common_audio/signal_processing/levinson_durbin.c (right): https://codereview.webrtc.org/2621693002/diff/1/webrtc/common_audio/signal_pr... webrtc/common_audio/signal_processing/levinson_durbin.c:151: K_low = (int16_t)((temp3W32 - ((int32_t)K_hi * 65536)) >> 1); On 2017/01/09 16:52:35, ivoc wrote: > When temp3W32 is a negative number (which can happen), K_hi will be negative > while K_low will be a positive number. So the value that's being shifted (the "shiftee"?) is always nonzero? https://codereview.webrtc.org/2621693002/diff/1/webrtc/common_audio/signal_pr... webrtc/common_audio/signal_processing/levinson_durbin.c:196: temp1W32 = ((K_hi * K_low >> 14) + K_hi * K_hi) * 2; // K*K in Q31 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?
lgtm, based purely on the actual change. Your discussion with kwiberg may lead to new revelations, but I'll risk it...
https://codereview.webrtc.org/2621693002/diff/1/webrtc/common_audio/signal_pr... File webrtc/common_audio/signal_processing/levinson_durbin.c (right): https://codereview.webrtc.org/2621693002/diff/1/webrtc/common_audio/signal_pr... webrtc/common_audio/signal_processing/levinson_durbin.c:151: K_low = (int16_t)((temp3W32 - ((int32_t)K_hi * 65536)) >> 1); On 2017/01/09 17:51:37, kwiberg-webrtc wrote: > On 2017/01/09 16:52:35, ivoc wrote: > > When temp3W32 is a negative number (which can happen), K_hi will be negative > > while K_low will be a positive number. > > So the value that's being shifted (the "shiftee"?) is always nonzero? 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. https://codereview.webrtc.org/2621693002/diff/1/webrtc/common_audio/signal_pr... webrtc/common_audio/signal_processing/levinson_durbin.c:196: temp1W32 = ((K_hi * K_low >> 14) + K_hi * K_hi) * 2; // K*K in Q31 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?
https://codereview.webrtc.org/2621693002/diff/1/webrtc/common_audio/signal_pr... File webrtc/common_audio/signal_processing/levinson_durbin.c (right): https://codereview.webrtc.org/2621693002/diff/1/webrtc/common_audio/signal_pr... webrtc/common_audio/signal_processing/levinson_durbin.c:151: K_low = (int16_t)((temp3W32 - ((int32_t)K_hi * 65536)) >> 1); On 2017/01/10 09:18:27, ivoc wrote: > On 2017/01/09 17:51:37, kwiberg-webrtc wrote: > > On 2017/01/09 16:52:35, ivoc wrote: > > > When temp3W32 is a negative number (which can happen), K_hi will be negative > > > while K_low will be a positive number. > > > > So the value that's being shifted (the "shiftee"?) is always nonzero? > > 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. Got it. https://codereview.webrtc.org/2621693002/diff/1/webrtc/common_audio/signal_pr... webrtc/common_audio/signal_processing/levinson_durbin.c:196: temp1W32 = ((K_hi * K_low >> 14) + K_hi * K_hi) * 2; // K*K in Q31 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.
https://codereview.webrtc.org/2621693002/diff/1/webrtc/common_audio/signal_pr... File webrtc/common_audio/signal_processing/levinson_durbin.c (right): https://codereview.webrtc.org/2621693002/diff/1/webrtc/common_audio/signal_pr... webrtc/common_audio/signal_processing/levinson_durbin.c:196: temp1W32 = ((K_hi * K_low >> 14) + K_hi * K_hi) * 2; // K*K in Q31 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?
https://codereview.webrtc.org/2621693002/diff/1/webrtc/common_audio/signal_pr... File webrtc/common_audio/signal_processing/levinson_durbin.c (right): https://codereview.webrtc.org/2621693002/diff/1/webrtc/common_audio/signal_pr... webrtc/common_audio/signal_processing/levinson_durbin.c:196: temp1W32 = ((K_hi * K_low >> 14) + K_hi * K_hi) * 2; // K*K in Q31 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.
lgtm https://codereview.webrtc.org/2621693002/diff/1/webrtc/common_audio/signal_pr... File webrtc/common_audio/signal_processing/levinson_durbin.c (right): https://codereview.webrtc.org/2621693002/diff/1/webrtc/common_audio/signal_pr... webrtc/common_audio/signal_processing/levinson_durbin.c:196: temp1W32 = ((K_hi * K_low >> 14) + K_hi * K_hi) * 2; // K*K in Q31 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.)
The CQ bit was checked by ivoc@webrtc.org
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.webrtc.org/...
CQ is committing da patch.
Bot data: {"patchset_id": 1, "attempt_start_ts": 1484044630196530, "parent_rev":
"6969c56871852a2b4dead7a98b738fde9291a135", "commit_rev":
"abf1752ff44481cff17b5bfada8e18bf537fe27d"}
Message was sent while issue was closed.
Description was changed from ========== Fix for left shift of potentially negative value. Left shifting of negative integers is undefined behavior, and should be prevented. This CL fixes one such instance in the Levinson Durbin function. BUG=chromium:675349 ========== to ========== Fix for left shift of potentially negative value. Left shifting of negative integers is undefined behavior, and should be prevented. This CL fixes one such instance in the Levinson Durbin function. BUG=chromium:675349 Review-Url: https://codereview.webrtc.org/2621693002 Cr-Commit-Position: refs/heads/master@{#15984} Committed: https://chromium.googlesource.com/external/webrtc/+/abf1752ff44481cff17b5bfad... ==========
Message was sent while issue was closed.
Committed patchset #1 (id:1) as https://chromium.googlesource.com/external/webrtc/+/abf1752ff44481cff17b5bfad... |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
