[FFmpeg-devel] [PATCH] SBG decoder

[Michael Niedermayer]

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

  
                           a,b,c,d,e,0,0,0,...,0,0,0,-1
                        *a+
a,b,c,d,e,0,0,0,...,0,0,0,-1  
                        *b+
 a,b,c,d,e,0,0,0,...,0,0,0,-1  
                        *c+
   a,b,c,d,e,0,0,0,...,0,0,0,-1  
                        *d+
     a,b,c,d,e,0,0,0,...,0,0,0,-1  
                        *e+
       a,b,c,d,e,0,0,0,...,0,0,0,-1  

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>