flac dev - Jun 2014 - [PATCH] stream_encoder : Improve selection of residual accumulator width

On Thu, Jun 19, 2014 at 03:30:22PM +0400, lvqcl wrote:
> BTW, what can you say about the following place in stream_decoder.c
> in read_subframe_lpc_() function:
> 
>      /*@@@@@@ technically not pessimistic enough, should be more like
>      if( (FLAC__uint64)order * ((((FLAC__uint64)1)<<bps)-1) *
((1<<subframe->qlp_coeff_precision)-1) < (((FLAC__uint64)-1)
<< 32) )
>      */
>      if(bps + subframe->qlp_coeff_precision + FLAC__bitmath_ilog2(order)
<= 32)
> 
> Is it really "not pessimistic enough"? Can it be changed
similarly to your patch
> for stream_encoder.c?
Good question. I'm not sure what exactly Josh meant by that comment.
The git message says just "minor comments".

I think the right size of the expression was meant to be
(FLAC__uint64)1<<32, otherwise it doesn't make much sense to me. With
that it can rewritten in log2 as

bps + subframe->qlp_coeff_precision + FLAC__bitmath_ilog2(order - 1) < 32

This is indeed more pessimistic that the currently used check (< 32 vs
<= 32), but I think both make a mistake that the qlp coefficients and
residuals are unsigned integers and are actually more pessimistic than
they would need to be if residuals were at most bps wide. With signed
multiplication I think the correct check would actually be

bps + subframe->qlp_coeff_precision + FLAC__bitmath_ilog2(order) - 1 <= 32

But, as we have seen with unusual data the residual signal can be
wider than bps. The FLAC format specification doesn't seem to mention
this. Should it be treated as a valid FLAC stream? Based on the
analysis above, the currently used check allows residuals at most 1
bit wider than bps. Another problem could be that the
local_lpc_restore_signal_16bit function may truncate the residual to
16 bits.

-- 
Miroslav Lichvar

Miroslav Lichvar wrote:
>>      if(bps + subframe->qlp_coeff_precision +
FLAC__bitmath_ilog2(order) <= 32)
>>
>> Is it really "not pessimistic enough"? Can it be changed
similarly to your patch
>> for stream_encoder.c?
>
> Good question. I'm not sure what exactly Josh meant by that comment.
> The git message says just "minor comments".
Now I wonder why evaluate_lpc_subframe_() function in stream_encoder.c contains
almost the same code, but without any comments that it's not enough
pessimistic:


evaluate_lpc_subframe_():

if(subframe_bps + qlp_coeff_precision + FLAC__bitmath_ilog2(order) <= 32)
	if(subframe_bps <= 16 && qlp_coeff_precision <= 16)
	
encoder->private_->local_lpc_compute_residual_from_qlp_coefficients_16bit(...);
	else
	
encoder->private_->local_lpc_compute_residual_from_qlp_coefficients(...);
else
	encoder->private_->local_lpc_compute_residual_from_qlp_coefficients_64bit(...);


vs. read_subframe_lpc_():

if(bps + subframe->qlp_coeff_precision + FLAC__bitmath_ilog2(order) <= 32)
	if(bps <= 16 && subframe->qlp_coeff_precision <= 16)
		decoder->private_->local_lpc_restore_signal_16bit(...);
	else
		decoder->private_->local_lpc_restore_signal(...);
else
	decoder->private_->local_lpc_restore_signal_64bit(...);

On Thu, Jun 19, 2014 at 03:30:06PM +0200, Miroslav Lichvar
wrote:
> But, as we have seen with unusual data the residual signal can be
> wider than bps. The FLAC format specification doesn't seem to mention
> this. Should it be treated as a valid FLAC stream?
I think it would be interesting to know how common are such streams. I
patched flac to print a warning on decoding or testing when this is
detected, but didn't find any files with this problem in my (small)
music collection.

If someone has a large collection and some cycles to spare, can you please 
consider compiling flac from git with the attached patch and see if
you have any files that fail with "flac -t" ?

With the known problem file (snippet6.wav) encoded by 1.3.0 it prints
this:

WARNING: residual -11025151 wider than bps 24
WARNING: residual 41873263 wider than bps 24
WARNING: residual -67175215 wider than bps 24
WARNING: residual 69950995 wider than bps 24
WARNING: residual -67108864 wider than bps 24
...
WARNING: residual 11227392 wider than bps 24
WARNING: residual -8754288 wider than bps 24
snippet6.flac: ERROR, MD5 signature mismatch

Thanks,

-- 
Miroslav Lichvar
-------------- next part --------------
diff --git a/src/libFLAC/stream_decoder.c b/src/libFLAC/stream_decoder.c
index ddd8979..82318ae 100644
--- a/src/libFLAC/stream_decoder.c
+++ b/src/libFLAC/stream_decoder.c
@@ -99,7 +99,7 @@ static FLAC__bool read_subframe_constant_(FLAC__StreamDecoder
*decoder, unsigned
 static FLAC__bool read_subframe_fixed_(FLAC__StreamDecoder *decoder, unsigned
channel, unsigned bps, const unsigned order, FLAC__bool do_full_decode);
 static FLAC__bool read_subframe_lpc_(FLAC__StreamDecoder *decoder, unsigned
channel, unsigned bps, const unsigned order, FLAC__bool do_full_decode);
 static FLAC__bool read_subframe_verbatim_(FLAC__StreamDecoder *decoder,
unsigned channel, unsigned bps, FLAC__bool do_full_decode);
-static FLAC__bool read_residual_partitioned_rice_(FLAC__StreamDecoder *decoder,
unsigned predictor_order, unsigned partition_order,
FLAC__EntropyCodingMethod_PartitionedRiceContents *partitioned_rice_contents,
FLAC__int32 *residual, FLAC__bool is_extended);
+static FLAC__bool read_residual_partitioned_rice_(FLAC__StreamDecoder *decoder,
unsigned predictor_order, unsigned partition_order,
FLAC__EntropyCodingMethod_PartitionedRiceContents *partitioned_rice_contents,
FLAC__int32 *residual, FLAC__bool is_extended, int bps);
 static FLAC__bool read_zero_padding_(FLAC__StreamDecoder *decoder);
 static FLAC__bool read_callback_(FLAC__byte buffer[], size_t *bytes, void
*client_data);
 #if FLAC__HAS_OGG
@@ -2572,7 +2572,7 @@ FLAC__bool read_subframe_fixed_(FLAC__StreamDecoder
*decoder, unsigned channel,
 	switch(subframe->entropy_coding_method.type) {
 		case FLAC__ENTROPY_CODING_METHOD_PARTITIONED_RICE:
 		case FLAC__ENTROPY_CODING_METHOD_PARTITIONED_RICE2:
-			if(!read_residual_partitioned_rice_(decoder, order,
subframe->entropy_coding_method.data.partitioned_rice.order,
&decoder->private_->partitioned_rice_contents[channel],
decoder->private_->residual[channel],
/*is_extended=*/subframe->entropy_coding_method.type ==
FLAC__ENTROPY_CODING_METHOD_PARTITIONED_RICE2))
+			if(!read_residual_partitioned_rice_(decoder, order,
subframe->entropy_coding_method.data.partitioned_rice.order,
&decoder->private_->partitioned_rice_contents[channel],
decoder->private_->residual[channel],
/*is_extended=*/subframe->entropy_coding_method.type ==
FLAC__ENTROPY_CODING_METHOD_PARTITIONED_RICE2, bps))
 				return false;
 			break;
 		default:
@@ -2651,7 +2651,7 @@ FLAC__bool read_subframe_lpc_(FLAC__StreamDecoder
*decoder, unsigned channel, un
 	switch(subframe->entropy_coding_method.type) {
 		case FLAC__ENTROPY_CODING_METHOD_PARTITIONED_RICE:
 		case FLAC__ENTROPY_CODING_METHOD_PARTITIONED_RICE2:
-			if(!read_residual_partitioned_rice_(decoder, order,
subframe->entropy_coding_method.data.partitioned_rice.order,
&decoder->private_->partitioned_rice_contents[channel],
decoder->private_->residual[channel],
/*is_extended=*/subframe->entropy_coding_method.type ==
FLAC__ENTROPY_CODING_METHOD_PARTITIONED_RICE2))
+			if(!read_residual_partitioned_rice_(decoder, order,
subframe->entropy_coding_method.data.partitioned_rice.order,
&decoder->private_->partitioned_rice_contents[channel],
decoder->private_->residual[channel],
/*is_extended=*/subframe->entropy_coding_method.type ==
FLAC__ENTROPY_CODING_METHOD_PARTITIONED_RICE2, bps))
 				return false;
 			break;
 		default:
@@ -2703,7 +2703,7 @@ FLAC__bool read_subframe_verbatim_(FLAC__StreamDecoder
*decoder, unsigned channe
 	return true;
 }
 
-FLAC__bool read_residual_partitioned_rice_(FLAC__StreamDecoder *decoder,
unsigned predictor_order, unsigned partition_order,
FLAC__EntropyCodingMethod_PartitionedRiceContents *partitioned_rice_contents,
FLAC__int32 *residual, FLAC__bool is_extended)
+FLAC__bool read_residual_partitioned_rice_(FLAC__StreamDecoder *decoder,
unsigned predictor_order, unsigned partition_order,
FLAC__EntropyCodingMethod_PartitionedRiceContents *partitioned_rice_contents,
FLAC__int32 *residual, FLAC__bool is_extended, int bps)
 {
 	FLAC__uint32 rice_parameter;
 	int i;
@@ -2744,6 +2744,15 @@ FLAC__bool
read_residual_partitioned_rice_(FLAC__StreamDecoder *decoder, unsigne
 			u = (partition_order == 0 || partition > 0)? partition_samples :
partition_samples - predictor_order;
 		
if(!decoder->private_->local_bitreader_read_rice_signed_block(decoder->private_->input,
residual + sample, u, rice_parameter))
 				return false; /* read_callback_ sets the state for us */
+#if 1
+			for (i = sample; (unsigned)i < sample + u; i++)  {
+				if (abs(residual[i]) > (1 << (bps - 1))) {
+					fprintf(stderr, "WARNING: residual %d wider than bps %d\n",
+							residual[i], bps);
+					residual[i]--; /* corrupt the value to fail decoding test */
+				}
+			}
+#endif
 			sample += u;
 		}
 		else {

On Thu, Jun 19, 2014 at 06:25:57PM +0400, lvqcl wrote:
> Now I wonder why evaluate_lpc_subframe_() function in stream_encoder.c
contains
> almost the same code, but without any comments that it's not enough
pessimistic:
> evaluate_lpc_subframe_():
> 
> if(subframe_bps + qlp_coeff_precision + FLAC__bitmath_ilog2(order) <=
32)
> 	if(subframe_bps <= 16 && qlp_coeff_precision <= 16)
> 	
encoder->private_->local_lpc_compute_residual_from_qlp_coefficients_16bit(...);
> 	else
> 	
encoder->private_->local_lpc_compute_residual_from_qlp_coefficients(...);
> else
> 
encoder->private_->local_lpc_compute_residual_from_qlp_coefficients_64bit(...);
Yes, it's the same check. Assuming residual can be at most
FLAC__MAX_EXTRA_RESIDUAL_BPS bits wider than subframe_bps, I think it
should be:

if(subframe_bps + qlp_coeff_precision + FLAC__bitmath_ilog2(order) +
FLAC__MAX_EXTRA_RESIDUAL_BPS - 1 <= 32)
	if(subframe_bps + FLAC__MAX_EXTRA_RESIDUAL_BPS <= 16 &&
qlp_coeff_precision <= 16)
> vs. read_subframe_lpc_():
> 
> if(bps + subframe->qlp_coeff_precision + FLAC__bitmath_ilog2(order)
<= 32)
> 	if(bps <= 16 && subframe->qlp_coeff_precision <= 16)
> 		decoder->private_->local_lpc_restore_signal_16bit(...);
> 	else
> 		decoder->private_->local_lpc_restore_signal(...);
> else
> 	decoder->private_->local_lpc_restore_signal_64bit(...);
-- 
Miroslav Lichvar

Another interesting comment is inside src/libFLAC/include/private/fixed.h:

"The _wide() version uses 64-bit integers which is statistically necessary
when bits-per-sample + log2(blocksize) > 30"

I mean the word "statistically".

libFLAC uses FLAC__fixed_compute_best_predictor_wide()
if "bits_per_sample + FLAC__bitmath_ilog2(blocksize)+1 > 30" is
true
(see encoder->private_->use_wide_by_block  variable in stream_encoder.c)

Miroslav Lichvar wrote:
> I think it would be interesting to know how common are such streams. I
> patched flac to print a warning on decoding or testing when this is
> detected, but didn't find any files with this problem in my (small)
> music collection.
>
> If someone has a large collection and some cycles to spare, can you please
> consider compiling flac from git with the attached patch and see if
> you have any files that fail with "flac -t" ?
>
> With the known problem file (snippet6.wav) encoded by 1.3.0 it prints
> this:
>
> WARNING: residual -11025151 wider than bps 24
> WARNING: residual 41873263 wider than bps 24
> WARNING: residual -67175215 wider than bps 24
> WARNING: residual 69950995 wider than bps 24
> WARNING: residual -67108864 wider than bps 24
> ...
> WARNING: residual 11227392 wider than bps 24
> WARNING: residual -8754288 wider than bps 24
> snippet6.flac: ERROR, MD5 signature mismatch
It seems quite common for 16-bit files:

WARNING: residual 43536 wider than bps 16
WARNING: residual 38012 wider than bps 16
WARNING: residual 35263 wider than bps 16
WARNING: residual 40668 wider than bps 16
WARNING: residual -34199 wider than bps 16
WARNING: residual -33828 wider than bps 16
WARNING: residual -33891 wider than bps 16
WARNING: residual -33540 wider than bps 16
WARNING: residual -36793 wider than bps 16
WARNING: residual -38870 wider than bps 16
WARNING: residual -35610 wider than bps 16
WARNING: residual -39849 wider than bps 16
WARNING: residual -38411 wider than bps 16
WARNING: residual -33430 wider than bps 16
WARNING: residual -34989 wider than bps 16

I don't have 24-bit FLAC files in my music library.