Re: [flac-dev] [PATCH] stream_encoder : Improve selection of residual accumulator width
Miroslav Lichvar wrote: In the precompute_partition_info_sums_ function, instead of selecting 64-bit accumulator when the signal bps is larger than 16, revert to the original approach based on partition size, but make room for few extra bits to not overflow with unusual signals where the average residual magnitude may be larger than bps. It slightly improves the performance with standard encoding levels and 16-bit files as the 17-bit side channel can still be processed with the 32-bit accumulator and correctly selects the 64-bit accumulator with very large 16-bit partitions. This is related to commits 6f7ec60c and 187e596e. Applied. Thanks. Erik -- -- Erik de Castro Lopo http://www.mega-nerd.com/ ___ flac-dev mailing list flac-dev@xiph.org http://lists.xiph.org/mailman/listinfo/flac-dev
Re: [flac-dev] [PATCH] stream_encoder : Improve selection of residual accumulator width
lvqcl wrote: As I see it: FLAC 1.2.1 and 1.3.0 cannot encode snippet6.wav with -7 and -8 encoding modes. But they are able to do this with --disable-fixed-subframes option. This implies that snippet6.wav triggers a problem somewthere inside FLAC__fixed_compute_residual(data[], data_len, order, residual[]) function. Can someone please provide me with a copy of the file snippet6.wav ? I'd like to test this some more. Erik -- -- Erik de Castro Lopo http://www.mega-nerd.com/ ___ flac-dev mailing list flac-dev@xiph.org http://lists.xiph.org/mailman/listinfo/flac-dev
Re: [flac-dev] [PATCH] stream_encoder : Improve selection of residual accumulator width
On Mon, Jun 30, 2014 at 08:08:42PM +1000, Erik de Castro Lopo wrote: Can someone please provide me with a copy of the file snippet6.wav ? I'd like to test this some more. I got it from http://wootangent.net/~lsd/blah/snippet6.wav -- Miroslav Lichvar ___ flac-dev mailing list flac-dev@xiph.org http://lists.xiph.org/mailman/listinfo/flac-dev
Re: [flac-dev] [PATCH] stream_encoder : Improve selection of residual accumulator width
Miroslav Lichvar wrote: Adding the extra bits to bps in evaluate_fixed_subframe_ instead of precompute_partition_info_sums_ is ok with me, that's what I suggested in the original thread discussing this problem, found it: http://lists.xiph.org/pipermail/flac-dev/2013-July/004303.html but I think it should be done also in the lpc function. Adding order instead of 4 might work for fixed frames, for LPC it looks too pessimistic. I'm OK with any version. To me it looks like (order * subframe_bps) in the calculation is the number of bits for the warmup samples in the fixed subframe. Thanks! ___ flac-dev mailing list flac-dev@xiph.org http://lists.xiph.org/mailman/listinfo/flac-dev
Re: [flac-dev] [PATCH] stream_encoder : Improve selection of residual accumulator width
Miroslav Lichvar wrote: In the precompute_partition_info_sums_ function, instead of selecting 64-bit accumulator when the signal bps is larger than 16, revert to the original approach based on partition size, but make room for few extra bits to not overflow with unusual signals where the average residual magnitude may be larger than bps. It slightly improves the performance with standard encoding levels and 16-bit files as the 17-bit side channel can still be processed with the 32-bit accumulator and correctly selects the 64-bit accumulator with very large 16-bit partitions. This is related to commits 6f7ec60c and 187e596e. Sorry I wasn't able to deal with this patch when it came in because I was busy with $day_job. There was a lot of discussion about this patch but I can't really figure out from the thread what the conclusion was. The patch still applies, and the test suite passes. If there is a problem with this patch that the test suite doesn't catch, we should write a test that does catch it. If there is no problem with the patch I'll push it. Erik -- -- Erik de Castro Lopo http://www.mega-nerd.com/ ___ flac-dev mailing list flac-dev@xiph.org http://lists.xiph.org/mailman/listinfo/flac-dev
Re: [flac-dev] [PATCH] stream_encoder : Improve selection of residual accumulator width
On Thu, Jun 19, 2014 at 09:23:26PM +0200, Martijn van Beurden wrote: op 19-06-14 20:17, lvqcl schreef: It seems quite common for 16-bit files: I second that. Apparently it depends on the kind of music, some albums have no warnings (mostly classical music it seems), some have over 20 per file. I've seen a few with 100 per file (things like rock and heavy metal). Most of the FLAC files were encoded with FLAC 1.2.1. Thanks for the data. I think I was just confused. The residual seems to be always handled as 32-bit and it's only added to the original signal, there is no multiplication, so it shouldn't be a problem. -- Miroslav Lichvar ___ flac-dev mailing list flac-dev@xiph.org http://lists.xiph.org/mailman/listinfo/flac-dev
Re: [flac-dev] [PATCH] stream_encoder : Improve selection of residual accumulator width
On Fri, Jun 20, 2014 at 01:21:03PM +0400, lvqcl wrote: Miroslav Lichvar цкщеу: +/* + * This is used to avoid overflow with unusual signals in 32-bit + * accumulator in the *precompute_partition_info_sums_* functions. + */ +#define FLAC__MAX_EXTRA_RESIDUAL_BPS 4 + /* WATCHOUT: + bps + FLAC__MAX_EXTRA_RESIDUAL_BPS is the maximum +* assumed size of the average residual magnitude */ + if(FLAC__bitmath_ilog2(default_partition_samples) + bps + FLAC__MAX_EXTRA_RESIDUAL_BPS 32) { From FLAC__fixed_compute_residual: residual[i] = data[i] - 4*data[i-1] + 6*data[i-2] - 4*data[i-3] + data[i-4]; so max(residual[i]) == 16 * max(data[j]), or: max_bps(residual[]) == 4 + max_bps(data[]). Am I right that it's the reason why FLAC__MAX_EXTRA_RESIDUAL_BPS is equal to 4? Not really, it's just a guess. With LPC the maximum possible residual could be much larger than with the fixed predictor if the coefficients were chosen randomly, but the autocorrelation routine should keep them more reasonable. The snippet6.wav file needed 2, so I made it slightly larger to have some extra room. As overflow in the accumulator won't result in a data loss, I think this is good enough until someone can figure out a better approach. -- Miroslav Lichvar ___ flac-dev mailing list flac-dev@xiph.org http://lists.xiph.org/mailman/listinfo/flac-dev
Re: [flac-dev] [PATCH] stream_encoder : Improve selection of residual accumulator width
On Fri, Jun 20, 2014 at 02:15:31PM +0400, lvqcl wrote: Miroslav Lichvar wrote: As overflow in the accumulator won't result in a data loss, I think this is good enough until someone can figure out a better approach. FLAC calculates real bitdepth of input signal for every block. Is it feasible to calculate real bitdepth of residual signal and use this value instead of (bps + 4) ? That would be expensive and I'm not sure if it's worth the cost. It could be a separate function or it could be integrated in the fixed and LPC encoding functions. The later would be probably faster, but it would require patching the assembly code. -- Miroslav Lichvar ___ flac-dev mailing list flac-dev@xiph.org http://lists.xiph.org/mailman/listinfo/flac-dev
Re: [flac-dev] [PATCH] stream_encoder : Improve selection of residual accumulator width
Miroslav Lichvar wrote: In the precompute_partition_info_sums_ function, instead of selecting 64-bit accumulator when the signal bps is larger than 16, revert to the original approach based on partition size, but make room for few extra bits to not overflow with unusual signals where the average residual magnitude may be larger than bps. It slightly improves the performance with standard encoding levels and 16-bit files as the 17-bit side channel can still be processed with the 32-bit accumulator and correctly selects the 64-bit accumulator with very large 16-bit partitions. 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) * ((1subframe-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? ___ flac-dev mailing list flac-dev@xiph.org http://lists.xiph.org/mailman/listinfo/flac-dev
Re: [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) * ((1subframe-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)132, 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 ___ flac-dev mailing list flac-dev@xiph.org http://lists.xiph.org/mailman/listinfo/flac-dev
Re: [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(...); ___ flac-dev mailing list flac-dev@xiph.org http://lists.xiph.org/mailman/listinfo/flac-dev
Re: [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 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,
Re: [flac-dev] [PATCH] stream_encoder : Improve selection of residual accumulator width
On Thu, Jun 19, 2014 at 05:04:23PM +0200, Miroslav Lichvar wrote: 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) On second thought, this is probably not necessary. The residual seems to be always treated as 32-bit in the LPC encoding and decoding functions, even in the MMX assembly if I'm reading it correctly. It doesn't matter if it's wider than the original signal. -- Miroslav Lichvar ___ flac-dev mailing list flac-dev@xiph.org http://lists.xiph.org/mailman/listinfo/flac-dev
Re: [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 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. ___ flac-dev mailing list flac-dev@xiph.org http://lists.xiph.org/mailman/listinfo/flac-dev
Re: [flac-dev] [PATCH] stream_encoder : Improve selection of residual accumulator width
op 19-06-14 20:17, lvqcl schreef: It seems quite common for 16-bit files: I second that. Apparently it depends on the kind of music, some albums have no warnings (mostly classical music it seems), some have over 20 per file. I've seen a few with 100 per file (things like rock and heavy metal). Most of the FLAC files were encoded with FLAC 1.2.1. The same is true for 24-bit files. I checked some orchestral music with no warnings, while NIN's The Slip (downloadable free of charge in 96/24) does, track 2 gives ~ 1900 warnings. These files too, were encoded with FLAC 1.2.1 ___ flac-dev mailing list flac-dev@xiph.org http://lists.xiph.org/mailman/listinfo/flac-dev