[Speex-dev] Re: speex echo cancellation limitations

[Jean-Marc Valin]

Hi Ted,

Thanks a lot for this analysis.

> In FLOAT_DIVU() it hangs at the following:
>    while (a.m >= b.m)
>    {
>       e++;
>       a.m >>= 1;
>    }
> for the case where a and b are both zero (yes, division by zero).
> This happens from mdf.c:

True, that needs to be fixed even after I fix the rest.

> leak_estimate = FLOAT_EXTRACT16(FLOAT_SHL(FLOAT_DIVU(st->Pey, st->Pyy),14));
> where st->Pey and st->Pyy are both zero, which happens for the following input 
> data to testecho program:
> -- first arg is file containing sine wave of magnitude +/- 32767
> -- 2nd arg is file containing all zeroes
> 
> The division by zero appears to be caused by the calculation:
> See = inner_prod(st->e+st->frame_size, st->e+st->frame_size, st->frame_size)

Does that also happen with "real life" signals or just high-amplitude
sinusoids (probably worth fixing anyway).

> which returns negative due to overflow occuring in mdf.c:inner_prod() :
>       part = MAC16_16(part,*x++,*y++);
>       part = MAC16_16(part,*x++,*y++);
>       part = MAC16_16(part,*x++,*y++);
>       part = MAC16_16(part,*x++,*y++);
>      sum = ADD32(sum,SHR32(part,6));
> This overflow can be avoided by rewriting this as:
>       part = part + ((*x++ * *y++)>>1);
>       part = part + ((*x++ * *y++)>>1);
>       part = part + ((*x++ * *y++)>>1);
>       part = part + ((*x++ * *y++)>>1);
>       sum += part>>5;
> I am assuming that the value 0x8000 is avoided in the input.

I think we can safely assume that -- or actually enforce that because it
would likely break other stuff.

> Even with this fix there is definitely some bad stuff going on; the output 
> data is corrupted looking.
> I put assertions into FLOAT_MUL32U(), FLOAT_DIV32_FLOAT() and FLOAT_DIV32() to 
> assert that the "a" arguments were non-negative. 

Technically these functions *should* work (they don't at the moment) for
negative inputs, but mdf.c isn't supposed to use that in the first
place. I guess it comes down to the same problem as above...

> Using some real life data, i 
> found that i had to shift the real life data right by two (i shifted both 
> inputs by same amount) to avoid asserting; shifting by just one almost worked 
> but failed for some case (i don't remember what that case was... not the one 
> i mentioned above).

I'd be interested in that sample if you can find it.

> [Alternately i could just clip the input to some threshold].

Except for the -32768 value, I don't want to do that because clipping is
highly non-linear and thus something the AEC doesn't like at all.

> To be on the safe side with the above functions, i removed the asserts and 
> modified the tests for == 0 to <= 0 ...
> 
> Clearly, some sort of automated testing scheme could help here...

One thing I used to do (should do it more often) is test with
FIXED_DEBUG (--enable-fixed-point-debug) which puts assertions in all
fixed-point operators (except the pseudofloat stuff, which is rather
new). Helps a lot tracking problems down.

	Jean-Marc