flac dev - Jul 2013 - exhaustive-model-search issue results in multi-gigabyte FLAC file

Miroslav Lichvar wrote:
> On Wed, Jul 17, 2013 at 07:45:53PM +1000, Erik de Castro Lopo wrote:
> > The fix was changing one local variable from FLAC_uint32 to
FLAC_uint64
> > in function precompute_partition_info_sums_().
> > 
> >    
https://git.xiph.org/?p=flac.git;a=commit;h=6f7ec60c7e7f05f5ab0b1cf6b7b0945e44afcd4b
> 
> I don't like this fix. It will probably hurt performance with 16-bit
> data and it won't fix the problem in the assembly code.
> 
> I think the check if 32-bit accumulator is enough should be improved
> instead if possible.
Miroslav,

I have committed an improvement on the above fix.

   
https://git.xiph.org/?p=flac.git;a=commit;h=f34f31dac0032887887b5bbcb0944de055b757d0

that reverts to the use of a FLAC_uint32 accumulator for files of less
than 24 bits per sample.

I still have no proof that this overflow cannot occur for 16 bit files.

Erik
-- 
----------------------------------------------------------------------
Erik de Castro Lopo
http://www.mega-nerd.com/

Erik de Castro Lopo wrote:
> I have committed an improvement on the above fix.
>
>    
https://git.xiph.org/?p=flac.git;a=commit;h=f34f31dac0032887887b5bbcb0944de055b757d0
>
> that reverts to the use of a FLAC_uint32 accumulator for files of less
> than 24 bits per sample.
>
> I still have no proof that this overflow cannot occur for 16 bit files.
>
> Erik

If the least significant bit in all samples of a 24-bit WAV file is set to 0,
the encoder sets 'bps' variable to 23 and the description of this patch
-

"This fix [...] restores the use of a FLAC_uint32 accumulator for 16 (and
less) bit files"

- is not correct: this fix restores the use of a FLAC_uint32 accumulator for 23
(and less) bit files. I slightly modified snippet6.wav and the current version
hangs on it when I add -b 8192 --lax options.


The code to enable 32-bit accumulator only for 16 (and less) bit files should
be:

"if(bps <= 16 && FLAC__bitmath_ilog2(default_partition_samples)
+ bps < 32)"

...and it seems that default_partition_samples must be less or equal to 65535;
this means that FLAC__bitmath_ilog2(default_partition_samples) is less or equal
to 15 and the code above is equivalent to:

"if(bps <= 16)"

On Sun, Jul 21, 2013 at 09:19:46PM +1000, Erik de Castro Lopo
wrote:
> Miroslav Lichvar wrote:
> > >    
https://git.xiph.org/?p=flac.git;a=commit;h=6f7ec60c7e7f05f5ab0b1cf6b7b0945e44afcd4b
> > 
> > I don't like this fix. It will probably hurt performance with
16-bit
> > data and it won't fix the problem in the assembly code.
> I have committed an improvement on the above fix.
> 
>    
https://git.xiph.org/?p=flac.git;a=commit;h=f34f31dac0032887887b5bbcb0944de055b757d0
> 
> that reverts to the use of a FLAC_uint32 accumulator for files of less
> than 24 bits per sample.
> 
> I still have no proof that this overflow cannot occur for 16 bit files.
I think it could happen with 16-bit files too if a very long block is
used.

My understanding of the problem is that after the prediction there are
samples in the residual signal which are wider than the original
samples, i.e. the bps argument in precompute_partition_info_sums_ is
wrong. I think such results should be ignored and never allowed to be
encoded to prevent problems in the decoder.

At the moment I don't see how it can be done efficiently. I'll try to
look into it more later. As a temporary workaround for the encoder I'd
suggest to use something like this instead of the bps < 24 check. I'm
not sure if 4 extra bits is enough to cover all possibilities.

--- a/src/libFLAC/stream_encoder.c
+++ b/src/libFLAC/stream_encoder.c
@@ -3515,7 +3515,7 @@ unsigned evaluate_fixed_subframe_(
                        rice_parameter_limit,
                        min_partition_order,
                        max_partition_order,
-                       subframe_bps,
+                       subframe_bps + 4,
                        do_escape_coding,
                        rice_parameter_search_dist,
                        &subframe->data.fixed.entropy_coding_method
@@ -3598,7 +3598,7 @@ unsigned evaluate_lpc_subframe_(
                        rice_parameter_limit,
                        min_partition_order,
                        max_partition_order,
-                       subframe_bps,
+                       subframe_bps + 4,
                        do_escape_coding,
                        rice_parameter_search_dist,
                        &subframe->data.lpc.entropy_coding_method


-- 
Miroslav Lichvar

lvqcl wrote:
> If the least significant bit in all samples of a 24-bit WAV file is set to
0,
> the encoder sets 'bps' variable to 23 and the description of this
patch -
> 
> "This fix [...] restores the use of a FLAC_uint32 accumulator for 16
(and less) bit files"
> 
> - is not correct: this fix restores the use of a FLAC_uint32 accumulator
for 23 (and
> less) bit files. I slightly modified snippet6.wav and the current version
hangs on it when
> I add -b 8192 --lax options.
> 
> 
> The code to enable 32-bit accumulator only for 16 (and less) bit files
should be:
> 
> "if(bps <= 16 &&
FLAC__bitmath_ilog2(default_partition_samples) + bps < 32)"
> 
> ...and it seems that default_partition_samples must be less or equal to
65535; this means that FLAC__bitmath_ilog2(default_partition_samples) is less or
equal to 15 and the code above is equivalent to:
> 
> "if(bps <= 16)"
Thanks, I've updated the fix to use this test to determine whether a 32 bit
accumulator can be used.

Cheers,
Erik
-- 
----------------------------------------------------------------------
Erik de Castro Lopo
http://www.mega-nerd.com/