[flac-dev] encoding complexity

[Ben Allison]

> What we're looking for is a measure of the expected decoding complexity,
> not the encoding complexity. The 2 are probably always going to be
> closely related, but they are different things, and complexity will
> depend on the data being compressed (aswell as on the encoder settings).
>
> There was a request last year for something similar, so that an embedded
> player using a CPU with adjustable clock speed (for power management)
> can anticipate how much CPU power will be needed for the next track or
> stream, before decoding begins. The idea being to adjust performance
> (CPU or memory) in enough time to meet demand.
>
> For known data (a music playlist using files, for example) the required
> metadata could be stored on the playback device, ready for the next time
> each track was played. For unknown data (streamed live audio) this would
> not be much help.

There are two major things in the file that you can look at to determine. 
One is easy, one is more difficult.

The stream info block -
http://flac.sourceforge.net/format.html#metadata_block_streaminfo - occurs
once at the beginning of the file.  You can get a reasonable estimation of
decoding complexity as well as memory usage.
* the maximum block size, combined with the number of channels, will
determine your memory usage requirement
* the sample rate and channel count will influence decoding complexity, as
you will have to calculate more data points per second to play back in
real-time

The MAJOR factor determining decoding complexity is going to be the order
of the LPC filter.  Unfortunately, this can vary frame-by-frame and there
is no maximum order specified in the stream info in the header of the
file.  You could sniff the entire file and find an upper-bound (or perhaps
a time-weighted sliding window average, as you might be buffering enough
to handle occassionally too-high LPC order counts).  The information is
available in each sub-frame header -
http://flac.sourceforge.net/format.html#subframe_header
Keep in mind that each channel has its own sub-frame header for each
frame.  This means (potentially) that the mid channel might be of
different order than the side channel.

Hope that helps,
-Ben Allison