Re-enable UBsan on AGC.

webrtc/modules/audio_processing/agc/legacy/digital_agc.c

Index: webrtc/modules/audio_processing/agc/legacy/digital_agc.c
diff --git a/webrtc/modules/audio_processing/agc/legacy/digital_agc.c b/webrtc/modules/audio_processing/agc/legacy/digital_agc.c
index 2ca967a4aae1a0d0a00758b4861a4838b1d11d46..bd3e60c2e5262e7d00dec858f332dbc1480ec9c2 100644
--- a/webrtc/modules/audio_processing/agc/legacy/digital_agc.c
+++ b/webrtc/modules/audio_processing/agc/legacy/digital_agc.c
@@ -189,7 +189,7 @@ int32_t WebRtcAgc_CalculateGainTable(int32_t* gainTable,       // Q16
     // Calculate ratio
     // Shift |numFIX| as much as possible.
     // Ensure we avoid wrap-around in |den| as well.
-    if (numFIX > (den >> 8))  // |den| is Q8.
+    if (numFIX > (den >> 8) || -numFIX > (den >> 8))  // |den| is Q8.

[minyue-webrtc, 2016/05/23 07:40:48]

this part is switched back to the old style, but added a new condition "||
-numFIX > (den >> 8)", which is indeed an error of the old code (error when
numFIX is negative)

[peah-webrtc, 2016/05/23 12:00:19]

Nice!

     {
       zeros = WebRtcSpl_NormW32(numFIX);
     } else {
@@ -199,12 +199,17 @@ int32_t WebRtcAgc_CalculateGainTable(int32_t* gainTable,       // Q16
 
     // Shift den so we end up in Qy1
     tmp32no1 = WEBRTC_SPL_SHIFT_W32(den, zeros - 8);  // Q(zeros)
-    if (numFIX < 0) {
-      numFIX -= tmp32no1 / 2;
-    } else {
-      numFIX += tmp32no1 / 2;
-    }
     y32 = numFIX / tmp32no1;  // in Q14

[peah-webrtc, 2016/05/23 12:00:19]

I don't think this is the right approach, even though it may work.
It is quite complicated and it also makes use of the % operator which I expect
to be as complex as a division in fixed point code.

The standard way of solving this is to normalize one step less, which will give
you headroom in the addition. I think you should do that, as it leads to much
simpler code and is cheaper as well.

Furthermore, I don't think the addition of
tmp32no1 / 2 is really needed. It should be sufficient to add 1<< (zeros-1) (or
subtract that, dependent on the sign of numFix). 
That is the standard way of doing rounding in fixed point code.

[minyue-webrtc, 2016/05/24 01:32:26]

+ 1<<(zeros-1) is to do ceil(), what we want here is round(). WDYT

[peah-webrtc, 2016/05/24 06:16:20]

Sorry, I realize that I was wrong about that the addition of tmp32no1 / 2 not
being needed. My comment about that was not correct at all.

However, I still think that setting zeros to one less than it is done now is the
correct solution, as that will should give headroom for the addition of
tmp32nol/2. 

Changing the value of zeros to one less does not change the rounding to a ceil.
It only affects the accuracy of the division.
WDYT?

[minyue-webrtc, 2016/05/24 07:16:12]

I also realized that +1<<(zero-1) does not do ceil(). But that is not the core
part of the discussion. What worth discuss is weather we want a precise round()
or not. In my opinion, finding the nearest integer should be most reasonable. 1)
it is well defined, 2) we do all shifting above to improve accuracy, and we
should not be too relaxed here, 3) Computationally, it should not be much more
complex. and if you think % will do another /, we may calculate remainder by
numFIX - y32 * tmp32nol.

[peah-webrtc, 2016/05/24 10:46:29]

I strongly doubt that we really need a rounding division here as this is a
gaintable computation. Do you know what negative impact a truncating division
would have?

The drawback of doing a zeros-1 normalization instead of a zeros normalization
is that you lose 1 bit accuracy in the 32 bit divisions. I would say that is
acceptable, in particular as the rest of the computations are in a fixed Q
value. 

Furthermore, looking at your code for this, I'm actually not sure it is
sufficient to avoid overflow. How can you guarantee that y32++ does not
overflow? (I could not come up with a good example for that though.)

[minyue-webrtc, 2016/05/24 13:05:45]

1) y32++ and -- is surely safe, since as long as |den| > 1,  the ratio will be
able to add/minus 1.

2) Regarding shifting zero -1 bits, I have thought about it. It is not totally
safe. what numFIX is already large (zero = 0)?

3) Not adding tmp32nol / 2 is good, but we loose the precision of nearest
integer.

If you like, I can go for 3).

[peah-webrtc, 2016/05/24 13:37:10]

Looking at it again, I see that the division is wrongly done. It should be
zeros = WebRtcSpl_NormW32(numFIX);
numFIX *= 1 << zeros;  // Q(14+zeros)
int sft = WebRtcSpl_NormW32(den) - 16;
tmp32no1 = WEBRTC_SPL_SHIFT_W32(den, -sft); // Q(8-sft) (ensures 16 bit
precision of the division)
y32 = numFIX / tmp32no1;  // Q(14+zeros-8+sft)
sft = 8 - (14+zeros-8+sft);
y32 += (1<<(sft-1)); // Adding 0.5 Q8 to ensure proper rounding 
y32 = WEBRTC_SPL_SHIFT_W32(y32, -sft);  // Q(8) (rounded)

Please doublecheck the above though.
 

[minyue-webrtc, 2016/05/26 02:28:20]

not really. y32 is supposed to be Q14, and the rounding by "+tmp32no1 / 2"
(before my change) is only to +/-2^(-14), rather than +/-2^(-8). So the division
was meant to be very precise. What you propose makes y32 Q8 rounded, that is
different from the original code.

[peah-webrtc, 2016/05/26 07:48:38]

Good find, sorry about that.  I also realized that I did not add 1 bit of
headroom for the rounding addition With this, I think that the below should be
the correct code. Note, however, that furthermore, adding 0.5 Q14 only is valid
for positive numbers so the code example needs to be modified accordingly. 

zeros = WebRtcSpl_NormW32(abs(numFIX)) -1;
numFIX = abs(numFix) * (1 << zeros);  // Q(14+zeros)
int sft = WebRtcSpl_NormW32(den) - 16;
tmp32no1 = WEBRTC_SPL_SHIFT_W32(den, -sft); // Q(8-sft) (ensures 16 bit
precision of the division)
y32 = numFIX / tmp32no1;  // Q(14+zeros-8+sft)
sft = 14 - (14+zeros-8+sft);
y32  += ((numFix > 0) - (numFix < 0)) * (1<<(sft-1)); // Adding 0.5 Q14 to
ensure proper rounding 
y32 = WEBRTC_SPL_SHIFT_W32(y32, -sft);  // Q(14) (rounded)


My point with the above is, however, that adding tmp32no1 / 2 is not necessary
for the rounding as the rounding is based on the bit that is shifted out when
placing y32 into Q14. 

To illustrate
5 (Q0)  is
3 (Q1) if rounded
2 (Q1) if not rounded

For this the rounding operation would be
101 (Q0) => (101 + 001) >> 1 (Q1) = 11 (Q1)
and the non-rounding operation would be
101 (Q0) => 101 >> 1 (Q1) = 10 (Q1)

If you really want to avoid the extra bit of headroom that avoids overflow when
doing the rounding addition you could check the value of numFIX = abs(numFix) *
(1 << zeros); and if that is so large that the addition will overflow then re-do
the shift with zeros-1. I do, however, not think that is worthwhile.

The above described scheme is the standard fixed-point way of doing this. If you
want to do a simple fix, I would go for zeros-1 shifts. It is, as you point out,
not perfect either if numFix is already normalized (zeros=0), but you will then
anyway have potential problems with cases when den < 2^8 as then zeros==0 will
cause den to be shifted to zero which will cause a division by zero. I think
this division have several implicit assumptions about the magnitude of the
variables anyway and those needs to be taken into account when designing the
division.

[peah-webrtc, 2016/05/26 12:27:54]

Having looked at it again, I think the proper code should be as below. But
please doublecheck it as it is really easy to get that wrong.

int sign_numfix = (numFix > 0) - (numFix < 0);                                  
                                                          
numFIX = abs(numFIX);                                                           
                                                          
zeros = WebRtcSpl_NormW32(numFIX) - 1;                                          
                                                          

// Doing this in proper shifts is faster than using WEBRTC_SPL_SHIFT_W32 as that
one both shifts and multiplies.
if (zeros < 0)
  numFIX = numFix >> abs(zeros);            // Q(14+zeros)                      
                                                          
else if (sft > 0)
  numFIX = numFix << zeros;                 // Q(14+zeros)                      
                                                          

int sign_den = (den > 0) - (den < 0);                                           
                                                          
den = abs(den);                             // Q(8)                             
                                                          
int sft = WebRtcSpl_NormW32(den) - 16;      // -16 to ensure 16 bit precision in
the result of the division.                               

// Doing this in proper shifts is faster than using WEBRTC_SPL_SHIFT_W32 as that
one both shifts and multiplies.
if (sft < 0)
  tmp32no1 = den >> abs(sft);               // Q(8-sft)                         
                                                          
else if (sft > 0)
  tmp32no1 = den << sft;                    // Q(8-sft)                         
                                                          


y32 = numFIX / tmp32no1;                    // Q(14+zeros-(8-sft))              
                                                          
sft = 14 - (14+zeros-8+sft);                                                    
                                                          

// Only round if shifting downwards.
if ((sft-1) <= 0)                                                               
                                                          
  y32  +=  (1<<abs((sft-1)));                      // Adding 0.5 Q14 to ensure
proper rounding                                             

if (sft < 0)
  y32 = y32 >> abs(sft);                    // Q(14) (rounded)                  
                                                          
else if (sft > 0)
  y32 = y32 << sft;                         // Q(14) (rounded)                  
                                                          

y32 *= int sign_numfix * int sign_den;  

[minyue-webrtc, 2016/06/01 04:45:11]

I see the point: do division so that the quotient is Q15 or more, then add 1 and
right shift. I think Q15 is just right, no need for more. I simplify it and see
the new patch set.

+    int remainder = numFIX % tmp32no1;

[minyue-webrtc, 2016/05/23 07:40:48]

this part is a new solution to rounding numFIX / tmp32no1.

The bitexactness test showed that this solution is equivalent in normal
conditions, but it is safer since it avoids overflow risk in line 201/203 in the
old code.

+    int round_threshold = den / 2 + den % 2;
+    if (remainder != 0) {
+      if (remainder >= round_threshold) {
+        y32++;  // Valid since |den| is always positive.
+      } else if (remainder <= -round_threshold) {
+        y32--;  // Valid since |den| is always positive.
+      }
+    }
+
     if (limiterEnable && (i < limiterIdx)) {
       tmp32 = WEBRTC_SPL_MUL_16_U16(i - 1, kLog10_2);  // Q14
       tmp32 -= limiterLvl * (1 << 14);                 // Q14