Miroslav Lichvar
2014-Jun-19 13:30 UTC
[flac-dev] [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
lvqcl
2014-Jun-19 14:25 UTC
[flac-dev] [PATCH] stream_encoder : Improve selection of residual accumulator width
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(...);
Miroslav Lichvar
2014-Jun-19 14:47 UTC
[flac-dev] [PATCH] stream_encoder : Improve selection of residual accumulator width
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 {
Miroslav Lichvar
2014-Jun-19 15:04 UTC
[flac-dev] [PATCH] stream_encoder : Improve selection of residual accumulator width
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)
lvqcl
2014-Jun-19 18:17 UTC
[flac-dev] [PATCH] stream_encoder : Improve selection of residual accumulator width
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 mismatchIt 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.