[FFmpeg-devel] [PATCH] mxf umid generation

[Michael Niedermayer]

On Sat, Mar 07, 2009 at 06:31:53PM -0800, Baptiste Coudurier wrote:
> On 3/7/2009 5:23 PM, Michael Niedermayer wrote:
> > On Sat, Mar 07, 2009 at 04:14:19PM -0800, Baptiste Coudurier wrote:
> >> On 3/7/2009 3:36 PM, Michael Niedermayer wrote:
> >>> On Sat, Mar 07, 2009 at 02:48:49PM -0800, Baptiste Coudurier wrote:
> >>>> On 3/6/2009 7:44 PM, Michael Niedermayer wrote:
> >>>>> On Fri, Mar 06, 2009 at 07:28:55PM -0800, Baptiste Coudurier wrote:
> > [...]
> >>>> Property changes on: libavutil\random_seed.c
> >>>> ___________________________________________________________________
> >>>> Added: svn:eol-style
> >>>>    + LF
> >>> intended?
> >>>
> >>> except these ok
> >>>
> >> I'm not sure, I'm on windows because products I test with only works on
> >> windows, I set ending lines style to unix, but it keeps adding this...
> >>
> >> It should be ok I think.
> >>
> > 
> >> Btw, is lfg ok for this purpose or should I use something else ?
> > 
> > to generate these id numbers out of the seed?
> > id rather use
> > seed += 1LL<<32 :)
> > 
> > lfg seens pointless complexity for this ...
> > 
> > and patch ok
> > 
> 
> Well I'd like to use the defined methods for umid generation, see below:
> 
> "A.3.2 Alternative masking methods
> The masked material number is an unpredictable number uniformly
> distributed over the range 0 thru 2^128-1. Its
> effectiveness as a unique identifier relies on this uniform random
> distribution, and the exact method of its generation is not
> important. Therefore, the use of the reference masking method is not
> normative, and any method providing an equivalent
> level of unpredictability and uniformity of distribution may be used
> with the ?masked method? value in the ?number
> generation method? field of the UMID universal label (reference table 1
> in 5.1.1)."
> 

> And instance generation:
> 
> "B.2 24-bit PRS generator (?2h?)
> Any suitable psuedo-random sequence (PRS) generator polynomial may be
> used provided it has a maximal length of
> 16,777,215 clock cycles. At the point of creating a new instance of the
> material, the 24-bits from the PRS generator are
> sampled to gain a new instance value.
> PRS generators shall not allow a zero value.

am i right in assuming that this "definition" is a 24bit LFSR?
if so, this is neither uniform over 2^128 nor unpredictable.
actually, its trivial to generate all future and past values
from just 2 24bit values even if the used polynomial is not known.

also if my interrpretation of this "definition" is correct you can
expect 1 collision in ~4000 ids


> NOTES
> 1 Any suitable seed may be used to start the pseudo-random sequence
> (PRS) 24-bit generator.
> 2 The PRS generator should use a free-running clock having no time
> relationship with the clock used to generate the sampling strobe.
> 3 The PRS generator clock frequency should be greater than 10 kHz.
> 4 The number of feedback taps resulting from the PRS generator
> polynomial should be between 8 and 16 to ensure the random nature
> of the sequence."
> 
> What do you think ?

sounds like the spec is writen by some really incompetent people.
also id like to repeat my suggestion of seed += 1<<32
it achives the minimum possible amount of collisions for a 32bit seed
a PRNG will perform worse.

proof:
myid(seed, count) = seed + (count<<32);
myid(seed0,count0) = myid(seed1,count1) => seed0=seed1 && count0=count1
 (assuming no overflows and if i understood correctly there are plenty of
  bits so a 32bit seed + 32bit counter would fit)
seed0!=seed1 || count0!=count1 => myid(seed0,count0) != myid(seed1,count1)

a good prng does not gurantee that
prng_n != prng_m => prng_(n+1) != prng_(m+1)
because if it did gurantee this it wouldnt be random, aka not a good PRNG

also you should set any bits left after the seed+counter to a random constant

and if you have a 32bit seed you have 32bit of randomness and a PRNG making
128 out of that still has just a randomness of 32, you could set 96 bits to
your pets name it wont make a difference.

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Rewriting code that is poorly written but fully understood is good.
Rewriting code that one doesnt understand is a sign that one is less smart
then the original author, trying to rewrite it will not make it better.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20090308/fc2eb4e7/attachment.pgp>