Fix UBSan errors (signed integer overflow)

webrtc/modules/audio_coding/codecs/ilbc/my_corr.c

Index: webrtc/modules/audio_coding/codecs/ilbc/my_corr.c
diff --git a/webrtc/modules/audio_coding/codecs/ilbc/my_corr.c b/webrtc/modules/audio_coding/codecs/ilbc/my_corr.c
index bd6ff561c2c5643e8961f2e0ab1f2594205a801a..80847b6099cd856aaccf5c00c8ed4d4c31295389 100644
--- a/webrtc/modules/audio_coding/codecs/ilbc/my_corr.c
+++ b/webrtc/modules/audio_coding/codecs/ilbc/my_corr.c
@@ -29,25 +29,26 @@ void WebRtcIlbcfix_MyCorr(
     const int16_t* seq2, /* (i) second sequence */
     size_t dim2   /* (i) dimension seq2 */
                           ){
-  int16_t max;
+  uint32_t max1, max2;
   size_t loops;
-  int scale;
-
-  /* Calculate correlation between the two sequences. Scale the
-     result of the multiplcication to maximum 26 bits in order
-     to avoid overflow */
-  max=WebRtcSpl_MaxAbsValueW16(seq1, dim1);
-  scale=WebRtcSpl_GetSizeInBits(max);
-
-  scale = 2 * scale - 26;
-  if (scale<0) {
-    scale=0;
+  int right_shift;
+
+  // Calculate a right shift that will let us sum dim2 pairwise products of
+  // values from the two sequences without overflowing an int32_t. (The +1 in
+  // max1 and max2 are because WebRtcSpl_MaxAbsValueW16 will return 2**15 - 1
+  // if the input array contains -2**15.)
+  max1 = WebRtcSpl_MaxAbsValueW16(seq1, dim1) + 1;
+  max2 = WebRtcSpl_MaxAbsValueW16(seq2, dim2) + 1;
+  right_shift =
+      (64 - 31) - WebRtcSpl_CountLeadingZeros64((max1 * max2) * (uint64_t)dim2);
+  if (right_shift < 0) {
+    right_shift = 0;

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

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:43:55]

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]

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.

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

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.)

   }
 
   loops=dim1-dim2+1;
 
   /* Calculate the cross correlations */
-  WebRtcSpl_CrossCorrelation(corr, seq2, seq1, dim2, loops, scale, 1);
+  WebRtcSpl_CrossCorrelation(corr, seq2, seq1, dim2, loops, right_shift, 1);
 
   return;
 }