[FFmpeg-devel] [PATCH] SBG decoder

Michael Niedermayer michaelni at gmx.at
Sun Dec 4 21:32:11 CET 2011

On Sun, Dec 04, 2011 at 07:48:46PM +0100, Nicolas George wrote:
> Le tridi 13 frimaire, an CCXX, Michael Niedermayer a écrit :
> > A similar trick as with LCGs is possible here, allowing to double the
> > distance of the source and destination coefficients (the number of
> > source coeffs is limited to FFMAX(A,B) because more can be simplified
> > by applying the n(i) = n(i-A) + n(i-B).
> > This is a bit more messy but it also allows to quickly calculate any
> > point in the cycle
> This one is in fact a simple matrix exponentiation: if we consider the
> state[index+i] vector, each step is the multiplication by a sparse 64×64
> matrix with an over-diagonal of 1 (corresponding to the index increment)
> except the last column, with 1s in the rows corresponding to A and B.
> Unfortunately, exponentiating a 64×64 matrix has a rather large base cost,
> and if using it to seek is indeed asymptotically faster, a quick benchmark
> shows that simple skipping is faster for up to six millions steps (on my
> box, where it takes 9.5 ms).

i dont think matrix exponentiation is needed, let me elaborate on what
i was suggesting:

if you have a sequence:
 A, B, C, D, E, ?, ?, ?, ?, ?, ?, ?
and the following to calculate the next step
 1, 0, 0, 1

resulting in:
 A, B, C, D, E, A+D, B+E, C+A+D, D+B+E, E+C+A+D, A+2D+B+E, B+2E+C+A+D

note here that a convolution with 
 1, 0, 0, 1, 0,-1

results in 0 everywhere

if we now convolve 1, 0, 0, 1, 0,-1 with anything its clear the result
still must be 0 when its convolved with the infinitely extended
sequence, thus we can build:
1, 0, 0, 1, 0,-1
      1, 0, 0, 1, 0,-1
1, 0, 1, 1, 0, 0, 0,-1

or for larger ones


which will double its length and number of non zero coeffs
by now subtracting 1, 0, 0, 1, 0,-1 from the leading coeffs wisely
(actually the remainder of a polynomial division)
we keep the double length but reduce the number of non zero coeffs
back to where we started

above could probably be written nicer using polynomials


Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Dictatorship naturally arises out of democracy, and the most aggravated
form of tyranny and slavery out of the most extreme liberty. -- Plato
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20111204/106df1aa/attachment.asc>

More information about the ffmpeg-devel mailing list