Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
2571483002:
Fix for integer overflow in NetEq. (Closed)
DescriptionFix for integer overflow in NetEq.
BUG=chromium:668736
Review-Url: https://codereview.webrtc.org/2571483002
Cr-Commit-Position: refs/heads/master@{#15654}
Committed: https://chromium.googlesource.com/external/webrtc/+/ffecbbf5d0602147d644c94ee9a8f25e6c25733d
Patch Set 1 #
Total comments: 6
Patch Set 2 : Changed int32_t to int64_t #Patch Set 3 : Used different approach to fix the issue. #
Total comments: 3
Patch Set 4 : Improved version of the fix. #Patch Set 5 : Update to bitexactness tests. #Patch Set 6 : Update to BitExactness for arm64. #
Total comments: 6
Patch Set 7 : Comments by kwiberg. #
Total comments: 2
Patch Set 8 : More comments. #
Messages
Total messages: 35 (11 generated)
ivoc@webrtc.org changed reviewers: + henrik.lundin@webrtc.org
Hi Henrik, PTAL.
LGTM, provided I'm wrong... :) https://codereview.webrtc.org/2571483002/diff/1/webrtc/modules/audio_coding/n... File webrtc/modules/audio_coding/neteq/expand.cc (right): https://codereview.webrtc.org/2571483002/diff/1/webrtc/modules/audio_coding/n... webrtc/modules/audio_coding/neteq/expand.cc:684: int32_t unvoiced_energy = WebRtcSpl_DotProductWithScale_64b( Will you not end up with the same overflow problem when casting the results to int32_t?
https://codereview.webrtc.org/2571483002/diff/1/webrtc/modules/audio_coding/n... File webrtc/modules/audio_coding/neteq/expand.cc (right): https://codereview.webrtc.org/2571483002/diff/1/webrtc/modules/audio_coding/n... webrtc/modules/audio_coding/neteq/expand.cc:684: int32_t unvoiced_energy = WebRtcSpl_DotProductWithScale_64b( On 2016/12/12 21:40:41, hlundin-webrtc wrote: > Will you not end up with the same overflow problem when casting the results to > int32_t? Oops, good catch, I'll change this to int64_t.
kwiberg@webrtc.org changed reviewers: + kwiberg@webrtc.org
https://codereview.webrtc.org/2571483002/diff/1/webrtc/common_audio/signal_pr... File webrtc/common_audio/signal_processing/dot_product_with_scale.c (right): https://codereview.webrtc.org/2571483002/diff/1/webrtc/common_audio/signal_pr... webrtc/common_audio/signal_processing/dot_product_with_scale.c:52: return sum; IIUC, the reason for having the right shifts in this function is to avoid the sum from overflowing. Now that you're accumulating in a 64-bit register, you can no longer have overflow unless length is 2^33 or thereabouts. So it will be faster and more accurate to not shift here, and just let the caller shift the final sum afterwards. Unless you need to be bit compatible with the 32-bit version, that is. https://codereview.webrtc.org/2571483002/diff/1/webrtc/common_audio/signal_pr... File webrtc/common_audio/signal_processing/include/signal_processing_library.h (right): https://codereview.webrtc.org/2571483002/diff/1/webrtc/common_audio/signal_pr... webrtc/common_audio/signal_processing/include/signal_processing_library.h:619: size_t length, Please consider using ArrayView when creating new functions. https://codereview.webrtc.org/2571483002/diff/1/webrtc/modules/audio_coding/n... File webrtc/modules/audio_coding/neteq/expand.cc (right): https://codereview.webrtc.org/2571483002/diff/1/webrtc/modules/audio_coding/n... webrtc/modules/audio_coding/neteq/expand.cc:684: int32_t unvoiced_energy = WebRtcSpl_DotProductWithScale_64b( On 2016/12/12 21:40:41, hlundin-webrtc wrote: > Will you not end up with the same overflow problem when casting the results to > int32_t? I would imagine so. Since all the partial sums are positive, you can't have overflow in an intermediate value without also having overflow in the final sum.
The CQ bit was checked by ivoc@webrtc.org
The patchset sent to the CQ was uploaded after l-g-t-m from henrik.lundin@webrtc.org Link to the patchset: https://codereview.webrtc.org/2571483002/#ps20001 (title: "Changed int32_t to int64_t")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.webrtc.org/...
The CQ bit was unchecked by ivoc@webrtc.org
I used a different approach to fix the problem now. The problem with the previous approach was that the int64_t was used in follow-up calculations that were expecting an int32_t, so it caused a domino effect where I would have to increase the precision of several other variables and functions as well. The approach I used now is simpler, but I'm not 100% sure it makes sense from an algorithmic POV. PTAL. https://codereview.webrtc.org/2571483002/diff/1/webrtc/common_audio/signal_pr... File webrtc/common_audio/signal_processing/dot_product_with_scale.c (right): https://codereview.webrtc.org/2571483002/diff/1/webrtc/common_audio/signal_pr... webrtc/common_audio/signal_processing/dot_product_with_scale.c:52: return sum; On 2016/12/13 08:45:36, kwiberg-webrtc wrote: > IIUC, the reason for having the right shifts in this function is to avoid the > sum from overflowing. Now that you're accumulating in a 64-bit register, you can > no longer have overflow unless length is 2^33 or thereabouts. So it will be > faster and more accurate to not shift here, and just let the caller shift the > final sum afterwards. Unless you need to be bit compatible with the 32-bit > version, that is. You're right that it's more accurate to not shift here and shift afterwards. However, that will result in larger values being calculated than previously (less rounding downward of intermediate values -> larger outputs), and I don't know what affect that has on the expand algorithm. I think the safest thing to do is to keep the result the same as before.
lgtm
lgtm. Following the train of thought I suggested is optional. https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... File webrtc/modules/audio_coding/neteq/expand.cc (right): https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... webrtc/modules/audio_coding/neteq/expand.cc:681: unvoiced_prescale = 6; So, let's see... you sum 2^7 values that are all less than 2^30, and divide by 2^6, so the shifted sum ends up being less than 2^31. Sounds right. https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... webrtc/modules/audio_coding/neteq/expand.cc:683: unvoiced_prescale = 4; Sum of 2^7 values that are all less than 2^28, and divide by 2^4, giving a sum less than 2^31. Good. https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... webrtc/modules/audio_coding/neteq/expand.cc:685: unvoiced_prescale = 0; Sum of 2^7 values that are all less than 2^24 (actually, less than 16000000), giving a sum less than 2^31. Check. So, good. But why not simply calculate unvoiced_prescale as 31 - 7 - 2*bits_in_max_element? I know we do that in other places?
On 2016/12/13 13:09:46, kwiberg-webrtc wrote: > lgtm. Following the train of thought I suggested is optional. > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > File webrtc/modules/audio_coding/neteq/expand.cc (right): > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > webrtc/modules/audio_coding/neteq/expand.cc:681: unvoiced_prescale = 6; > So, let's see... you sum 2^7 values that are all less than 2^30, and divide by > 2^6, so the shifted sum ends up being less than 2^31. Sounds right. > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > webrtc/modules/audio_coding/neteq/expand.cc:683: unvoiced_prescale = 4; > Sum of 2^7 values that are all less than 2^28, and divide by 2^4, giving a sum > less than 2^31. Good. > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > webrtc/modules/audio_coding/neteq/expand.cc:685: unvoiced_prescale = 0; > Sum of 2^7 values that are all less than 2^24 (actually, less than 16000000), > giving a sum less than 2^31. Check. > > So, good. But why not simply calculate unvoiced_prescale as 31 - 7 - > 2*bits_in_max_element? I know we do that in other places? Hmm, is that formula correct? I would think that if the max element has more bits (i.e. is a larger number), then we should get a higher prescale value, but in your formula it seems to be the opposite. Or am I misunderstanding? I would expect something like max(0, 2*nr_bits_in_max_element - 12), which would result in similar factors as we currently use.
On 2016/12/13 13:36:15, ivoc wrote: > On 2016/12/13 13:09:46, kwiberg-webrtc wrote: > > lgtm. Following the train of thought I suggested is optional. > > > > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > > File webrtc/modules/audio_coding/neteq/expand.cc (right): > > > > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > > webrtc/modules/audio_coding/neteq/expand.cc:681: unvoiced_prescale = 6; > > So, let's see... you sum 2^7 values that are all less than 2^30, and divide by > > 2^6, so the shifted sum ends up being less than 2^31. Sounds right. > > > > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > > webrtc/modules/audio_coding/neteq/expand.cc:683: unvoiced_prescale = 4; > > Sum of 2^7 values that are all less than 2^28, and divide by 2^4, giving a sum > > less than 2^31. Good. > > > > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > > webrtc/modules/audio_coding/neteq/expand.cc:685: unvoiced_prescale = 0; > > Sum of 2^7 values that are all less than 2^24 (actually, less than 16000000), > > giving a sum less than 2^31. Check. > > > > So, good. But why not simply calculate unvoiced_prescale as 31 - 7 - > > 2*bits_in_max_element? I know we do that in other places? > > Hmm, is that formula correct? I would think that if the max element has more > bits (i.e. is a larger number), then we should get a higher prescale value, but > in your formula it seems to be the opposite. Or am I misunderstanding? I would > expect something like max(0, 2*nr_bits_in_max_element - 12), which would result > in similar factors as we currently use. Ehh, sorry that should be max(0, 2*nr_bits_in_max_element - 24), of course.
On 2016/12/13 13:41:56, ivoc wrote: > On 2016/12/13 13:36:15, ivoc wrote: > > On 2016/12/13 13:09:46, kwiberg-webrtc wrote: > > > lgtm. Following the train of thought I suggested is optional. > > > > > > > > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > > > File webrtc/modules/audio_coding/neteq/expand.cc (right): > > > > > > > > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > > > webrtc/modules/audio_coding/neteq/expand.cc:681: unvoiced_prescale = 6; > > > So, let's see... you sum 2^7 values that are all less than 2^30, and divide > by > > > 2^6, so the shifted sum ends up being less than 2^31. Sounds right. > > > > > > > > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > > > webrtc/modules/audio_coding/neteq/expand.cc:683: unvoiced_prescale = 4; > > > Sum of 2^7 values that are all less than 2^28, and divide by 2^4, giving a > sum > > > less than 2^31. Good. > > > > > > > > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > > > webrtc/modules/audio_coding/neteq/expand.cc:685: unvoiced_prescale = 0; > > > Sum of 2^7 values that are all less than 2^24 (actually, less than > 16000000), > > > giving a sum less than 2^31. Check. > > > > > > So, good. But why not simply calculate unvoiced_prescale as 31 - 7 - > > > 2*bits_in_max_element? I know we do that in other places? > > > > Hmm, is that formula correct? I would think that if the max element has more > > bits (i.e. is a larger number), then we should get a higher prescale value, > but > > in your formula it seems to be the opposite. Or am I misunderstanding? I > would > > expect something like max(0, 2*nr_bits_in_max_element - 12), which would > result > > in similar factors as we currently use. > > Ehh, sorry that should be max(0, 2*nr_bits_in_max_element - 24), of course. I'm sure you're righter than me. Let's see... we have 2*nr_bits_in_max_element + 7 - unvoiced_prescale <= 31, so unvoiced_prescale >= 2*nr_bits_in_max_element + 7 - 31. Which, given that we want it as small as possible in order to minimize errors, and that it's inconvenient as well as useless to allow negative values, gives exactly max(0, 2*nr_bits_in_max_element - 24).
On 2016/12/13 14:42:39, kwiberg-webrtc wrote: > On 2016/12/13 13:41:56, ivoc wrote: > > On 2016/12/13 13:36:15, ivoc wrote: > > > On 2016/12/13 13:09:46, kwiberg-webrtc wrote: > > > > lgtm. Following the train of thought I suggested is optional. > > > > > > > > > > > > > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > > > > File webrtc/modules/audio_coding/neteq/expand.cc (right): > > > > > > > > > > > > > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > > > > webrtc/modules/audio_coding/neteq/expand.cc:681: unvoiced_prescale = 6; > > > > So, let's see... you sum 2^7 values that are all less than 2^30, and > divide > > by > > > > 2^6, so the shifted sum ends up being less than 2^31. Sounds right. > > > > > > > > > > > > > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > > > > webrtc/modules/audio_coding/neteq/expand.cc:683: unvoiced_prescale = 4; > > > > Sum of 2^7 values that are all less than 2^28, and divide by 2^4, giving a > > sum > > > > less than 2^31. Good. > > > > > > > > > > > > > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > > > > webrtc/modules/audio_coding/neteq/expand.cc:685: unvoiced_prescale = 0; > > > > Sum of 2^7 values that are all less than 2^24 (actually, less than > > 16000000), > > > > giving a sum less than 2^31. Check. > > > > > > > > So, good. But why not simply calculate unvoiced_prescale as 31 - 7 - > > > > 2*bits_in_max_element? I know we do that in other places? > > > > > > Hmm, is that formula correct? I would think that if the max element has more > > > bits (i.e. is a larger number), then we should get a higher prescale value, > > but > > > in your formula it seems to be the opposite. Or am I misunderstanding? I > > would > > > expect something like max(0, 2*nr_bits_in_max_element - 12), which would > > result > > > in similar factors as we currently use. > > > > Ehh, sorry that should be max(0, 2*nr_bits_in_max_element - 24), of course. > > I'm sure you're righter than me. Let's see... we have 2*nr_bits_in_max_element + > 7 - unvoiced_prescale <= 31, so unvoiced_prescale >= 2*nr_bits_in_max_element + > 7 - 31. Which, given that we want it as small as possible in order to minimize > errors, and that it's inconvenient as well as useless to allow negative values, > gives exactly max(0, 2*nr_bits_in_max_element - 24). I tried doing it this way, but it fails the bitexactness tests, while the approach in this CL doesn't. Do you think it's worth it to update them?
On 2016/12/13 15:44:59, ivoc wrote: > On 2016/12/13 14:42:39, kwiberg-webrtc wrote: > > On 2016/12/13 13:41:56, ivoc wrote: > > > On 2016/12/13 13:36:15, ivoc wrote: > > > > On 2016/12/13 13:09:46, kwiberg-webrtc wrote: > > > > > lgtm. Following the train of thought I suggested is optional. > > > > > > > > > > > > > > > > > > > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > > > > > File webrtc/modules/audio_coding/neteq/expand.cc (right): > > > > > > > > > > > > > > > > > > > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > > > > > webrtc/modules/audio_coding/neteq/expand.cc:681: unvoiced_prescale = 6; > > > > > So, let's see... you sum 2^7 values that are all less than 2^30, and > > divide > > > by > > > > > 2^6, so the shifted sum ends up being less than 2^31. Sounds right. > > > > > > > > > > > > > > > > > > > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > > > > > webrtc/modules/audio_coding/neteq/expand.cc:683: unvoiced_prescale = 4; > > > > > Sum of 2^7 values that are all less than 2^28, and divide by 2^4, giving > a > > > sum > > > > > less than 2^31. Good. > > > > > > > > > > > > > > > > > > > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > > > > > webrtc/modules/audio_coding/neteq/expand.cc:685: unvoiced_prescale = 0; > > > > > Sum of 2^7 values that are all less than 2^24 (actually, less than > > > 16000000), > > > > > giving a sum less than 2^31. Check. > > > > > > > > > > So, good. But why not simply calculate unvoiced_prescale as 31 - 7 - > > > > > 2*bits_in_max_element? I know we do that in other places? > > > > > > > > Hmm, is that formula correct? I would think that if the max element has > more > > > > bits (i.e. is a larger number), then we should get a higher prescale > value, > > > but > > > > in your formula it seems to be the opposite. Or am I misunderstanding? I > > > would > > > > expect something like max(0, 2*nr_bits_in_max_element - 12), which would > > > result > > > > in similar factors as we currently use. > > > > > > Ehh, sorry that should be max(0, 2*nr_bits_in_max_element - 24), of course. > > > > I'm sure you're righter than me. Let's see... we have 2*nr_bits_in_max_element > + > > 7 - unvoiced_prescale <= 31, so unvoiced_prescale >= 2*nr_bits_in_max_element > + > > 7 - 31. Which, given that we want it as small as possible in order to minimize > > errors, and that it's inconvenient as well as useless to allow negative > values, > > gives exactly max(0, 2*nr_bits_in_max_element - 24). > > I tried doing it this way, but it fails the bitexactness tests, while the > approach in this CL doesn't. Do you think it's worth it to update them? I guess you could make a compromise, like so: int unvoiced_prescale = <whatever that expression was>; if (unvoiced_max_abs < 16384) { // Legacy calculation that preserves historical behavior. unvoiced_prescale = unvoiced_max_abs > 4000 ? 4 : 0; } But it's probably better for the soul to go with either patch set #3 (the minimal fix) or the correct calculation that requires you to update the tests. It's your time vs. your eternal soul, so I'll leave the judgement call to you. :-) I'll be happy to review if you go for the latter choice (and if you do, you might want to take a look at https://codereview.webrtc.org/2014033002, where I do pretty much the same thing).
On 2016/12/14 09:15:19, kwiberg-webrtc wrote: > On 2016/12/13 15:44:59, ivoc wrote: > > On 2016/12/13 14:42:39, kwiberg-webrtc wrote: > > > On 2016/12/13 13:41:56, ivoc wrote: > > > > On 2016/12/13 13:36:15, ivoc wrote: > > > > > On 2016/12/13 13:09:46, kwiberg-webrtc wrote: > > > > > > lgtm. Following the train of thought I suggested is optional. > > > > > > > > > > > > > > > > > > > > > > > > > > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > > > > > > File webrtc/modules/audio_coding/neteq/expand.cc (right): > > > > > > > > > > > > > > > > > > > > > > > > > > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > > > > > > webrtc/modules/audio_coding/neteq/expand.cc:681: unvoiced_prescale = > 6; > > > > > > So, let's see... you sum 2^7 values that are all less than 2^30, and > > > divide > > > > by > > > > > > 2^6, so the shifted sum ends up being less than 2^31. Sounds right. > > > > > > > > > > > > > > > > > > > > > > > > > > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > > > > > > webrtc/modules/audio_coding/neteq/expand.cc:683: unvoiced_prescale = > 4; > > > > > > Sum of 2^7 values that are all less than 2^28, and divide by 2^4, > giving > > a > > > > sum > > > > > > less than 2^31. Good. > > > > > > > > > > > > > > > > > > > > > > > > > > > https://codereview.webrtc.org/2571483002/diff/40001/webrtc/modules/audio_codi... > > > > > > webrtc/modules/audio_coding/neteq/expand.cc:685: unvoiced_prescale = > 0; > > > > > > Sum of 2^7 values that are all less than 2^24 (actually, less than > > > > 16000000), > > > > > > giving a sum less than 2^31. Check. > > > > > > > > > > > > So, good. But why not simply calculate unvoiced_prescale as 31 - 7 - > > > > > > 2*bits_in_max_element? I know we do that in other places? > > > > > > > > > > Hmm, is that formula correct? I would think that if the max element has > > more > > > > > bits (i.e. is a larger number), then we should get a higher prescale > > value, > > > > but > > > > > in your formula it seems to be the opposite. Or am I misunderstanding? > I > > > > would > > > > > expect something like max(0, 2*nr_bits_in_max_element - 12), which would > > > > result > > > > > in similar factors as we currently use. > > > > > > > > Ehh, sorry that should be max(0, 2*nr_bits_in_max_element - 24), of > course. > > > > > > I'm sure you're righter than me. Let's see... we have > 2*nr_bits_in_max_element > > + > > > 7 - unvoiced_prescale <= 31, so unvoiced_prescale >= > 2*nr_bits_in_max_element > > + > > > 7 - 31. Which, given that we want it as small as possible in order to > minimize > > > errors, and that it's inconvenient as well as useless to allow negative > > values, > > > gives exactly max(0, 2*nr_bits_in_max_element - 24). > > > > I tried doing it this way, but it fails the bitexactness tests, while the > > approach in this CL doesn't. Do you think it's worth it to update them? > > I guess you could make a compromise, like so: > > int unvoiced_prescale = <whatever that expression was>; > if (unvoiced_max_abs < 16384) { > // Legacy calculation that preserves historical behavior. > unvoiced_prescale = unvoiced_max_abs > 4000 ? 4 : 0; > } > > But it's probably better for the soul to go with either patch set #3 (the > minimal fix) or the correct calculation that requires you to update the tests. > It's your time vs. your eternal soul, so I'll leave the judgement call to you. > :-) I'll be happy to review if you go for the latter choice (and if you do, you > might want to take a look at https://codereview.webrtc.org/2014033002, where I > do pretty much the same thing). I'd like to hang on to my eternal soul for a bit longer, so I used the new approach and updated the bitexactness tests to match. PTAL.
lgtm
https://codereview.webrtc.org/2571483002/diff/100001/webrtc/modules/audio_cod... File webrtc/modules/audio_coding/neteq/expand.cc (right): https://codereview.webrtc.org/2571483002/diff/100001/webrtc/modules/audio_cod... webrtc/modules/audio_coding/neteq/expand.cc:678: int16_t unvoiced_max_abs = WebRtcSpl_MaxAbsValueW16(unvoiced_vector, 128); const? Also, won't the calculation break if the abs-max element is -2^15? IIRC WebRtcSpl_MaxAbsValueW16 returns 2^15 - 1 in that case. I think I handle that case in the CL I linked to earlier. https://codereview.webrtc.org/2571483002/diff/100001/webrtc/modules/audio_cod... webrtc/modules/audio_coding/neteq/expand.cc:679: // The maximum value of the dot product is 2^7 * 2^(2*n) = 2^(2*n + 7), so "is less than", since unvoiced_max_abs < 2^n. Also, you never define n. Maybe say that "Pick the smallest n such that 2^n > unvoiced_max_abs; then the maximum value of the dot product is less than 2^7 * 2^(2*n) = 2^(2*n + 7) [...]" https://codereview.webrtc.org/2571483002/diff/100001/webrtc/modules/audio_cod... webrtc/modules/audio_coding/neteq/expand.cc:682: int16_t unvoiced_prescale = const int?
https://codereview.webrtc.org/2571483002/diff/100001/webrtc/modules/audio_cod... File webrtc/modules/audio_coding/neteq/expand.cc (right): https://codereview.webrtc.org/2571483002/diff/100001/webrtc/modules/audio_cod... webrtc/modules/audio_coding/neteq/expand.cc:678: int16_t unvoiced_max_abs = WebRtcSpl_MaxAbsValueW16(unvoiced_vector, 128); On 2016/12/15 14:11:16, kwiberg-webrtc wrote: > const? > > Also, won't the calculation break if the abs-max element is -2^15? IIRC > WebRtcSpl_MaxAbsValueW16 returns 2^15 - 1 in that case. I think I handle that > case in the CL I linked to earlier. Wow, good catch. I added an if-statement to increase the prescale by one when unvoiced_max_abs is equal to 2^15-1, which should prevent this from happening. https://codereview.webrtc.org/2571483002/diff/100001/webrtc/modules/audio_cod... webrtc/modules/audio_coding/neteq/expand.cc:679: // The maximum value of the dot product is 2^7 * 2^(2*n) = 2^(2*n + 7), so On 2016/12/15 14:11:16, kwiberg-webrtc wrote: > "is less than", since unvoiced_max_abs < 2^n. > > Also, you never define n. Maybe say that "Pick the smallest n such that 2^n > > unvoiced_max_abs; then the maximum value of the dot product is less than 2^7 * > 2^(2*n) = 2^(2*n + 7) [...]" Done. https://codereview.webrtc.org/2571483002/diff/100001/webrtc/modules/audio_cod... webrtc/modules/audio_coding/neteq/expand.cc:682: int16_t unvoiced_prescale = On 2016/12/15 14:11:16, kwiberg-webrtc wrote: > const int? Due to the newly added if statement, this can no longer be a const.
https://codereview.webrtc.org/2571483002/diff/120001/webrtc/modules/audio_cod... File webrtc/modules/audio_coding/neteq/expand.cc (right): https://codereview.webrtc.org/2571483002/diff/120001/webrtc/modules/audio_cod... webrtc/modules/audio_coding/neteq/expand.cc:690: unvoiced_prescale++; Wouldn't you need to add 2, not just 1? And it's probably easier to follow if you modify unvoiced_abs_max earlier: const int unvoiced_max_abs = [&]{ const int16_t max_abs = WebRtcSpl_MaxAbsValueW16(unvoiced_vector, 128); // Since WebRtcSpl_MaxAbsValueW16 returns 2^15 - 1 when the input contains // -2^15, we have to conservatively bump the return value by 1 // if it is 2^15 - 1. return max_abs == WEBRTC_SPL_WORD16_MAX ? max_abs + 1 : max_abs; }();
https://codereview.webrtc.org/2571483002/diff/120001/webrtc/modules/audio_cod... File webrtc/modules/audio_coding/neteq/expand.cc (right): https://codereview.webrtc.org/2571483002/diff/120001/webrtc/modules/audio_cod... webrtc/modules/audio_coding/neteq/expand.cc:690: unvoiced_prescale++; On 2016/12/16 10:23:32, kwiberg-webrtc wrote: > Wouldn't you need to add 2, not just 1? And it's probably easier to follow if > you modify unvoiced_abs_max earlier: > > const int unvoiced_max_abs = [&]{ > const int16_t max_abs = WebRtcSpl_MaxAbsValueW16(unvoiced_vector, 128); > // Since WebRtcSpl_MaxAbsValueW16 returns 2^15 - 1 when the input contains > // -2^15, we have to conservatively bump the return value by 1 > // if it is 2^15 - 1. > return max_abs == WEBRTC_SPL_WORD16_MAX ? max_abs + 1 : max_abs; > }(); The worst case is if the whole array is filled with -2^15, in that case the value of the dot product will be 2^7 * 2^15 * 2^15, which is 2^37. If we shift this by 7 (which is what the +1 will do), the sum will be 2^30, which can easily be represented as a 32-bit int. With a shift of 6 it would be 2^31 and it overflows by 1, because int32 only goes up to 2^31 - 1. Your method looks nicer however, so I'll use that instead.
On 2016/12/16 11:45:01, ivoc wrote: > https://codereview.webrtc.org/2571483002/diff/120001/webrtc/modules/audio_cod... > File webrtc/modules/audio_coding/neteq/expand.cc (right): > > https://codereview.webrtc.org/2571483002/diff/120001/webrtc/modules/audio_cod... > webrtc/modules/audio_coding/neteq/expand.cc:690: unvoiced_prescale++; > On 2016/12/16 10:23:32, kwiberg-webrtc wrote: > > Wouldn't you need to add 2, not just 1? And it's probably easier to follow if > > you modify unvoiced_abs_max earlier: > > > > const int unvoiced_max_abs = [&]{ > > const int16_t max_abs = WebRtcSpl_MaxAbsValueW16(unvoiced_vector, 128); > > // Since WebRtcSpl_MaxAbsValueW16 returns 2^15 - 1 when the input contains > > // -2^15, we have to conservatively bump the return value by 1 > > // if it is 2^15 - 1. > > return max_abs == WEBRTC_SPL_WORD16_MAX ? max_abs + 1 : max_abs; > > }(); > > The worst case is if the whole array is filled with -2^15, in that case the > value of the dot product will be 2^7 * 2^15 * 2^15, which is 2^37. If we shift > this by 7 (which is what the +1 will do), the sum will be 2^30, which can easily > be represented as a 32-bit int. With a shift of 6 it would be 2^31 and it > overflows by 1, because int32 only goes up to 2^31 - 1. Ah, right---2^15 - 1 squared has 30 bits, but 2^15 squared has 31 bits, not 32. I was assuming the product would have twice as many bits, which is true in general, but here we have a specific case where 1 bit less will do. > Your method looks nicer however, so I'll use that instead. Good. Alternatively, you can use the same trick to implement your previous algorithm without dropping the const. lgtm either way.
The CQ bit was checked by ivoc@webrtc.org
The patchset sent to the CQ was uploaded after l-g-t-m from henrik.lundin@webrtc.org Link to the patchset: https://codereview.webrtc.org/2571483002/#ps140001 (title: "More comments.")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.webrtc.org/...
The CQ bit was unchecked by commit-bot@chromium.org
CLs for remote refs other than refs/pending/heads/master must contain NOTRY=true and NOPRESUBMIT=true in order for the CQ to process them
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": 140001, "attempt_start_ts": 1481896210219340,
"parent_rev": "70f39a30e96082a49809850422c8fe5275accdf8", "commit_rev":
"ffecbbf5d0602147d644c94ee9a8f25e6c25733d"}
Message was sent while issue was closed.
Description was changed from ========== Fix for integer overflow in NetEq. BUG=chromium:668736 ========== to ========== Fix for integer overflow in NetEq. BUG=chromium:668736 Review-Url: https://codereview.webrtc.org/2571483002 Cr-Commit-Position: refs/heads/master@{#15654} Committed: https://chromium.googlesource.com/external/webrtc/+/ffecbbf5d0602147d644c94ee... ==========
Message was sent while issue was closed.
Committed patchset #8 (id:140001) as https://chromium.googlesource.com/external/webrtc/+/ffecbbf5d0602147d644c94ee... |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
