# [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

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

[...]

--

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>
```