[FFmpeg-devel] [PATCH] SBG decoder

[Nicolas George]

Le tridi 13 frimaire, an CCXX, Michael Niedermayer a écrit :
> Actually, i disagree here.
> LCGs have the form n(i+1) = n(i)*A + B mod m
> from this one can trivially calculate
> n(i+2) = n(i)*C + D mod m    (C=A*A mod m, D= B*A + B mod m)
> n(i+4) = n(i)*E + F mod m    ...
> n(i+8) = n(i)*G + H mod m
> ...
> 
> and with above its again trivial and relatively fast O(log n) to find
> any value of the cycle
> 
> LFGs have the form n(i) = n(i-A) + n(i-B) mod m
> 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
> 
> note, above is not a comment to the actual, patch set its just about
> seeking with PRNGs

Indeed, thanks for the trick, I had not thought about that method. I had
tried to apply the usual analysis for real u -> au+b sequences, but it
obviously fails because the coefficient a is selected so that a-1 has no
inverse.

I'll think about your method.

Regards,

-- 
  Nicolas George
-------------- 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/20111203/350088be/attachment.asc>