[Ffmpeg-devel] FLAC encoder
Justin Ruggles
jruggle
Sat May 27 01:59:08 CEST 2006
Michael Niedermayer wrote:
> Hi
>
> On Fri, May 26, 2006 at 03:24:35AM -0400, Justin Ruggles wrote:
>
>>Hello,
>>
>>My FLAC encoder has progressed to a point that I am happy with. Test it
>>out, and see what you think. If the developers show an interest in
>>including this in FFmpeg, I will consolidate the files and adapt it for
>>inclusion.
>
>
> yes
> requirements for acceptance are at least that the existing crc, rice &
> bitstream facilities of libavcodec are used
Yes indeed. I actually did a test integration on the 1st working
version I made just to see what kind of issues there were to deal with.
It took me a whole day to figure out that I wasn't flushing the
bitwriter before calculating crc's...that was maddening :) Once I got
it working okay I went back to improving the standalone encoder. As far
as issues...FFmpeg seems to cut off the last chunk of audio if it is not
a full block as set at the start of encoding. I'll wait until I come
across it again to explain the problem in detail.
>
> one suggestions:
>
> instead of
> for all partition orders (calc_optimal_partition_order)
> for all partitions (calc_optimal_rice_params)
> do gradient descent search for k to minimize: (calc_optimal_rice_param)
> the number of bits for all symbols in the current partition (rice_encode_count)
>
> which is obviously going to be slow
> O(n * partition_orders * gardient_descent_steps), you can
>
> sum up all bits in O(n) time and then run the optimization based on the sums
> the result is identical
>
> 1. convert everything to unsiged by tmp[i] = (2*data[i]) ^ (data[i]>>31)
> which is equivalent to tmp[i] = (data[i] < 0) ? -2*data[i]-1 : 2*data[i];
> 2. calculate the partial sums (the following is written for readability its
> dead slow if implemented like that:
> part[0][i][j] = tmp[i] & (1<<j)
> part[p][i][j]= part[p-1][2*i][j] + part[p-1][2*i+1][j]
>
> the number of bits for a single symbol is (data>>k) + k + 1 for all symbols
> n to m its obviously (m-n)*(k+1) + sum of (data[i]>>k)
> and "sum of (data[i]>>k)" is just the sum of the corresponding partial sums
> for that area
>
> i hope you understand my suggestion ...
I think I do. Adding in k each time is ineffienct because a certain
value of k will create a constant baseline number of bits no matter
what. The only variant is (data[i]>>k).
>
> now, how to find the partial sums quickly:
> first pass, we want to quickly find the 32 sums of the bits of 2 integers
> sounds like it would need a loop with 32 iterations ... no it needs 2
> instructions only :)
> lsb[i]= d[2i] ^ d[2i+1]
> msb[i]= d[2i] & d[2i+1]
>
> pass 2:
> sum[1][i][0] = lsb[2i] ^ lsb[2i+1]
> sum[1][i][1] = msb[2i] ^ msb[2i+1] ^ (lsb[2i] & lsb[2i+1])
> sum[1][i][2] = msb[2i] & msb[2i+1]
>
> pass n:
> L= sum[n-1][2i]
> R= sum[n-1][2i+1]
> sum[n][i][0] = L[0] ^ R[0]
> carry[0] = L[0] & R[0]
> sum[n][i][j] = L[j] ^ R[j] ^ carry[j-1]
> carry[j] = ((L[j] ^ R[j]) & carry[j-1]) | (L[j] & R[j])
> sum[n][i][n] = L[n-1] & R[n-1]
>
> each pass will work only with half as many elements as the previous so this
> is fast even though each pass is somewhat more complex then the previous
> if you dont understand the whole, keep in mind each variable holds 32 bits not
> 1 bit which are worked on in parallel
>
> alternatively if this is too complex for you then you could at least
> move the "(data[i] < 0) ? -2*data[i]-1 : 2*data[i];" and "k + 1" out
> of the innermost loop
> and cache the partial bit counts (a partition from n..m with param k
> needs exactly as many bits as the sum of the bits needed by the 2 smaller
> partitions)
>
>
> [...]
>
Whew. You lost me a little here. I'll have to work through the bit
math to wrap my head around this. I think I understand the basic idea
though. I'll at least tackle the 1st part. "sum of (data[i]>>k)" I can
do...it's your bit-wise math solution that I'll have to give some mind
time to.
Thanks for the help and suggestions!
-Justin
More information about the ffmpeg-devel
mailing list