Fix UBSan errors (signed integer overflow)

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

 /*
  *  Copyright (c) 2011 The WebRTC project authors. All Rights Reserved.
  *
  *  Use of this source code is governed by a BSD-style license
  *  that can be found in the LICENSE file in the root of the source
  *  tree. An additional intellectual property rights grant can be found
  *  in the file PATENTS.  All contributing project authors may
  *  be found in the AUTHORS file in the root of the source tree.
  */
 
@@ skipping 11 matching lines @@
  * compute cross correlation between sequences
  *---------------------------------------------------------------*/
 
 void WebRtcIlbcfix_MyCorr(
     int32_t* corr,  /* (o) correlation of seq1 and seq2 */
     const int16_t* seq1,  /* (i) first sequence */
     size_t dim1,  /* (i) dimension first seq1 */
     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;
+  int right_shift;
 
-  /* 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;
+  // 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;
 }