Fix UBSan errors (signed integer overflow)

Fix UBSan errors (signed integer overflow)

WebRtcSpl_CrossCorrelation and WebRtcSpl_DotProductWithScale compute
the int32 sum of pairwise products from two int16 arrays. So as to
avoid overflow (which could otherwise happen when as little as two
products were summed), the products are right-shifted by an amount
specified by the caller.

This CL changes WebRtcIlbcfix_MyCorr and WebRtcIlbcfix_Smooth to give
sufficient right-shift amounts, instead of ones that may be too small
and cause overflow.

BUG=chromium:601787
Committed: https://crrev.com/a10740239dd0f40f54d65288055e128496e2da3f
Cr-Commit-Position: refs/heads/master@{#13066}

[kwiberg-webrtc, 2016-05-25 22:42:20]

Patchset #1 (id:1) has been deleted

[kwiberg-webrtc, 2016-05-25 23:49:46]

kwiberg@webrtc.org changed reviewers:
+ tina.legrand@webrtc.org

[tlegrand-webrtc, 2016-05-26 09:39:44]

This CL seem to actually change the behavior. I wonder if a suitable test can be
added, that shows that the behavior only changes when we otherwise would have
had an overflow?

https://codereview.chromium.org/2014033002/diff/20001/webrtc/modules/audio_co...
File webrtc/modules/audio_coding/codecs/ilbc/my_corr.c (right):

https://codereview.chromium.org/2014033002/diff/20001/webrtc/modules/audio_co...
webrtc/modules/audio_coding/codecs/ilbc/my_corr.c:45: right_shift = 0;
Does the old "scale" and the new "right_shift" differ much, or only in cases
where the result would overflow for sure?

[kwiberg-webrtc, 2016-05-26 11:35:09]

On 2016/05/26 09:39:44, tlegrand-webrtc wrote:
> This CL seem to actually change the behavior. I wonder if a suitable test can
be
> added, that shows that the behavior only changes when we otherwise would have
> had an overflow?

Well, such a test would fail currently, I think. The new code tries to do the
computation properly, but the old one was more or less pulling numbers out of a
hat. (Possibly a hat that was well correlated with the actual requirements, but
it's hard to tell.) I've made no effort to mimic the old computations in cases
where they would have given the correct result.

I think the only way to get the behavior you're asking for is to compute the
right shift in both the old and the new way, and using whichever number is
larger. The resulting code will be beautiful.

[kwiberg-webrtc, 2016-05-26 11:43:55]

https://codereview.webrtc.org/2014033002/diff/20001/webrtc/modules/audio_codi...
File webrtc/modules/audio_coding/codecs/ilbc/my_corr.c (right):

https://codereview.webrtc.org/2014033002/diff/20001/webrtc/modules/audio_codi...
webrtc/modules/audio_coding/codecs/ilbc/my_corr.c:45: right_shift = 0;
On 2016/05/26 09:39:44, tlegrand-webrtc wrote:
> Does the old "scale" and the new "right_shift" differ much, or only in cases
> where the result would overflow for sure?

I don't know, but in general they should differ. The new code tries to
approximate the required right-shift by counting how many bits the sum of
pairwise products could be in the worst case by actually looking at the vector
elements and the number of terms in the sum; the old code looked at just one of
the vectors and assumed the other one was the same, assumed that the number of
terms (the variable seq2) was a constant (32, if I math correctly), and
overestimated the number of bits by counting the bits separately and then adding
instead of multiplying and then counting the bits.

[tlegrand-webrtc, 2016-05-26 12:18:21]

Comments inline.

https://codereview.webrtc.org/2014033002/diff/20001/webrtc/modules/audio_codi...
File webrtc/modules/audio_coding/codecs/ilbc/my_corr.c (right):

https://codereview.webrtc.org/2014033002/diff/20001/webrtc/modules/audio_codi...
webrtc/modules/audio_coding/codecs/ilbc/my_corr.c:45: right_shift = 0;
On 2016/05/26 11:43:55, kwiberg-webrtc wrote:
> On 2016/05/26 09:39:44, tlegrand-webrtc wrote:
> > Does the old "scale" and the new "right_shift" differ much, or only in cases
> > where the result would overflow for sure?
> 
> I don't know, but in general they should differ. The new code tries to
> approximate the required right-shift by counting how many bits the sum of
> pairwise products could be in the worst case by actually looking at the vector
> elements and the number of terms in the sum; the old code looked at just one
of
> the vectors and assumed the other one was the same, assumed that the number of
> terms (the variable seq2) was a constant (32, if I math correctly), and
> overestimated the number of bits by counting the bits separately and then
adding
> instead of multiplying and then counting the bits.

This code confuses me a bit, so bare with me if I haven't gotten it right. It
looks like the limitation here is not about making sure the cross correlation
calculation doesn't overflow (because it can, if the two most negative values
are multiplied). I think it has to do with code later on, and it requires the
result of the correlation not to exceed 26 bits.
I think you need to keep the "max 26 bits", not to risk getting overflow later
on.

https://codereview.webrtc.org/2014033002/diff/20001/webrtc/modules/audio_codi...
File webrtc/modules/audio_coding/codecs/ilbc/smooth.c (right):

https://codereview.webrtc.org/2014033002/diff/20001/webrtc/modules/audio_codi...
webrtc/modules/audio_coding/codecs/ilbc/smooth.c:56:
WebRtcSpl_CountLeadingZeros64((max1 * max2) * (uint64_t)ENH_BLOCKL);
I think you need to keep the "max 26 bits" not to get overflow later on.

[kwiberg-webrtc, 2016-05-26 13:52:10]

https://codereview.webrtc.org/2014033002/diff/20001/webrtc/modules/audio_codi...
File webrtc/modules/audio_coding/codecs/ilbc/my_corr.c (right):

https://codereview.webrtc.org/2014033002/diff/20001/webrtc/modules/audio_codi...
webrtc/modules/audio_coding/codecs/ilbc/my_corr.c:45: right_shift = 0;
On 2016/05/26 12:18:21, tlegrand-webrtc wrote:
> On 2016/05/26 11:43:55, kwiberg-webrtc wrote:
> > On 2016/05/26 09:39:44, tlegrand-webrtc wrote:
> > > Does the old "scale" and the new "right_shift" differ much, or only in
cases
> > > where the result would overflow for sure?
> > 
> > I don't know, but in general they should differ. The new code tries to
> > approximate the required right-shift by counting how many bits the sum of
> > pairwise products could be in the worst case by actually looking at the
vector
> > elements and the number of terms in the sum; the old code looked at just one
> of
> > the vectors and assumed the other one was the same, assumed that the number
of
> > terms (the variable seq2) was a constant (32, if I math correctly), and
> > overestimated the number of bits by counting the bits separately and then
> adding
> > instead of multiplying and then counting the bits.
> 
> This code confuses me a bit, so bare with me if I haven't gotten it right. It
> looks like the limitation here is not about making sure the cross correlation
> calculation doesn't overflow (because it can, if the two most negative values
> are multiplied). I think it has to do with code later on, and it requires the
> result of the correlation not to exceed 26 bits.
> I think you need to keep the "max 26 bits", not to risk getting overflow later
> on.

We talked face-to-face, but for the record, my understanding is that "scale" is
just the right-shift required to not get overflows inside
WebRtcSpl_CrossCorrelation. The 26 in the old code means that we limit each
product to 26 bits, so that we can sum up to 32 of them (2**5) without overflow.
(The old code thus assumes---without checking---that dim2 is at most 32. And if
it's much less than 32, it right-shifts more than necessary, losing precision.)

https://codereview.webrtc.org/2014033002/diff/20001/webrtc/modules/audio_codi...
File webrtc/modules/audio_coding/codecs/ilbc/smooth.c (right):

https://codereview.webrtc.org/2014033002/diff/20001/webrtc/modules/audio_codi...
webrtc/modules/audio_coding/codecs/ilbc/smooth.c:56:
WebRtcSpl_CountLeadingZeros64((max1 * max2) * (uint64_t)ENH_BLOCKL);
On 2016/05/26 12:18:21, tlegrand-webrtc wrote:
> I think you need to keep the "max 26 bits" not to get overflow later on.

No, this piece of code works mostly the same as the other one. Except for
actually checking the max of both arrays instead of just one. And the number of
products to sum (ENH_BLOCKL) is a constant, not a variable, but still assumed to
be at most 32.

Curiously, ENH_BLOCKL is in fact 80. Meaning that the old code systematically
underestimated the required right-shift by more than one step.

[kwiberg-webrtc, 2016-05-26 13:58:28]

Uploaded a new patch set with a small logic fix: we actually do three dot
products, A*A, B*B, and A*B, so in the worst case we multiply the max element by
itself.

[kwiberg-webrtc, 2016-06-01 13:46:57]

As a sanity check, I tried replacing the computed right shift with 30 in both
places (which has the effect of throwing away lots of precision). Replacing
either one of the right shifts like that caused the iLBC bit-exactness tests to
fail. We can thus have some confidence that this CL isn't entirely crazy, since
it doesn't break those tests.

[tlegrand-webrtc, 2016-06-03 06:22:05]

On 2016/06/01 13:46:57, kwiberg-webrtc wrote:
> As a sanity check, I tried replacing the computed right shift with 30 in both
> places (which has the effect of throwing away lots of precision). Replacing
> either one of the right shifts like that caused the iLBC bit-exactness tests
to
> fail. We can thus have some confidence that this CL isn't entirely crazy,
since
> it doesn't break those tests.

Thanks for running the extra tests! LGTM

[kwiberg-webrtc, 2016-06-08 11:39:16]

The CQ bit was checked by kwiberg@webrtc.org

[commit-bot: I haz the power, 2016-06-08 11:39:21]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/2014033002/40001

[commit-bot: I haz the power, 2016-06-08 12:24:43]

Committed patchset #2 (id:40001)

[commit-bot: I haz the power, 2016-06-08 12:24:50]

Description was changed from

==========
Fix UBSan errors (signed integer overflow)

WebRtcSpl_CrossCorrelation and WebRtcSpl_DotProductWithScale compute
the int32 sum of pairwise products from two int16 arrays. So as to
avoid overflow (which could otherwise happen when as little as two
products were summed), the products are right-shifted by an amount
specified by the caller.

This CL changes WebRtcIlbcfix_MyCorr and WebRtcIlbcfix_Smooth to give
sufficient right-shift amounts, instead of ones that may be too small
and cause overflow.

BUG=chromium:601787
==========

to

==========
Fix UBSan errors (signed integer overflow)

WebRtcSpl_CrossCorrelation and WebRtcSpl_DotProductWithScale compute
the int32 sum of pairwise products from two int16 arrays. So as to
avoid overflow (which could otherwise happen when as little as two
products were summed), the products are right-shifted by an amount
specified by the caller.

This CL changes WebRtcIlbcfix_MyCorr and WebRtcIlbcfix_Smooth to give
sufficient right-shift amounts, instead of ones that may be too small
and cause overflow.

BUG=chromium:601787

Committed: https://crrev.com/a10740239dd0f40f54d65288055e128496e2da3f
Cr-Commit-Position: refs/heads/master@{#13066}
==========

[commit-bot: I haz the power, 2016-06-08 12:24:51]

Patchset 2 (id:??) landed as
https://crrev.com/a10740239dd0f40f54d65288055e128496e2da3f
Cr-Commit-Position: refs/heads/master@{#13066}