[FFmpeg-devel] [PATCH] SBG decoder

[Michael Niedermayer]

On Sat, Dec 03, 2011 at 11:20:24AM +0100, Nicolas George wrote:
[...]
> [PATCH 3/5] lavu: add noise generator.
> 
>   White and pink noise generator. Seekable: you can jump to four hours into
>   the stream of random numbers in constant time and get exactly the same
>   result each time. 


>   The usual PRNG are not seekable, and the common block
>   ciphers are too slow.

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


[...]


-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Concerning the gods, I have no means of knowing whether they exist or not
or of what sort they may be, because of the obscurity of the subject, and
the brevity of human life -- Protagoras
-------------- 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/27688ef0/attachment.asc>