flac dev - May 2015 - A condition in precompute_partition_info_sums_()

The commit
http://git.xiph.org/?p=flac.git;a=commitdiff;h=0a0a10f358345f749e4a05021301461994f1ffc5
(from 31 Mar 2007) adds the following conditional:

        if(FLAC__bitmath_ilog2(default_partition_samples) + bps < 32)

And the commit
http://git.xiph.org/?p=flac.git;a=commitdiff;h=f081524c19eeafd08f4db6ee5d52a9634c60f475
has this:

        if(FLAC__bitmath_ilog2(default_partition_samples) + bps +
FLAC__MAX_EXTRA_RESIDUAL_BPS < 32)


The question is: why ... < 32, not ... <= 32 ?

Basically we want to know the number of bits that is necessary to represent
the value of (default_partition_samples * max_value_of_residual) product.

Let's assume that the bitness of the residual signal is N. The minimum value
is -2^(N-1), the max is 2^(N-1)-1. For the absolute value: max = 2^(N-1).

The number of bits in default_partition_samples is equal to
     FLAC__bitmath_ilog2(default_partition_samples) + 1.
When we multiply default_partition_samples with 2^(N-1) we add N-1 zeroes to it,
so the number of bits in (default_partition_samples*max_value_of_residual) is
equal to

     FLAC__bitmath_ilog2(default_partition_samples) + 1 + N - 1, i.e.
     FLAC__bitmath_ilog2(default_partition_samples) + N

The value of (default_partition_samples*max_value_of_residual) should fit
into unsigned 32-bit variable, so the condition should be:

     FLAC__bitmath_ilog2(default_partition_samples) + N <= 32

lvqcl wrote:
> The commit
http://git.xiph.org/?p=flac.git;a=commitdiff;h=0a0a10f358345f749e4a05021301461994f1ffc5
> (from 31 Mar 2007) adds the following conditional:
>
>     if(FLAC__bitmath_ilog2(default_partition_samples) + bps < 32)
At that time the 32-bit accumulator was almost always used for both 16-bit and
24-bit input files, because this condition was almost always true. There was
a comment before this code:
/* WATCHOUT: "+ bps" is an assumption that the average residual
magnitude will not be more than "bps" bits */
It turns out that this assumption is too optimistic, and the current code is
>     if(FLAC__bitmath_ilog2(default_partition_samples) + bps +
FLAC__MAX_EXTRA_RESIDUAL_BPS < 32)
But this condition is usually never true for 24-bit signals, and at the same
time the 32-bit accumulator is almost always enough for them.


So my idea is to change the current code:



else { /* have to pessimistically use 64 bits for accumulator */
     FLAC__uint64 abs_residual_partition_sum;

     for(partition = residual_sample = 0; partition < partitions;
partition++) {
         end += default_partition_samples;
         abs_residual_partition_sum = 0;
         for( ; residual_sample < end; residual_sample++)
             abs_residual_partition_sum += abs(residual[residual_sample]);
         abs_residual_partition_sums[partition] = abs_residual_partition_sum;
     }


into something like this:


else {
     FLAC__uint32 abs_residual_partition_sum; /* still try to use 32-bit math */

     for(partition = residual_sample = 0; partition < partitions;
partition++) {
         end += default_partition_samples;
         abs_residual_partition_sum = 0;
         for( ; residual_sample < end; residual_sample++) {
             abs_residual_partition_sum += abs(residual[residual_sample]);
             calculate max_residual_bps = the max bitness of abs(residual[]);
         }

         if(FLAC__bitmath_ilog2(default_partition_samples) + max_residual_bps
<= 32)
             abs_residual_partition_sums[partition] =
abs_residual_partition_sum; /* no overflow */
         else
         { /* repeat the summation for the current partition with 64-bit
accumulator */
             FLAC__uint64 abs_residual_partition_sum64 = 0;

             for(residual_sample=...; residual_sample < end;
residual_sample++)
                 abs_residual_partition_sum64 += abs(residual[residual_sample]);
             abs_residual_partition_sums[partition] =
abs_residual_partition_sum64;
         }
     }

so the encoder first tries to use 32-bit accumulator (which is almost always
enough)
even for 24-bit files, but switches to 64-bit accumulator if the bitness of
residual[]
is too big and it cannot guarantee that there's no overflow.