[FFmpeg-devel] [PATCH] mxf umid generation

[Michael Niedermayer]

On Sat, Mar 07, 2009 at 07:25:54PM -0800, Baptiste Coudurier wrote:
> On 3/7/2009 7:16 PM, Michael Niedermayer wrote:
> > 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
> 
> Well, "instance number" is 3 bytes and umid is 16 bytes, these are
> different numbers, this is what the code is trying to achieve, see the
> patch.
> 
> >> 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.
> 
> Is it still true now you know that these numbers are different ?

a design that cannot be implemented in ANSI C or for the matter of fact
any deterministic language is broken


> 
> Is the method ok at least for the "instance number" ?
> 
> > [...]
> > 
> > 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.
> > 
> 
> So there is no way we could be able to generate the 128 bits umid
> according to the method ? Can I use the md5 of the 4 bytes of the seed ?

you can but it will have a collision in ~64k umids thats the same as if you
just take the 32bit seed + some constant like your name.
also it violates the spec because it is neither unpredictable not uniform.

If you want to follow the spec you need 128 strong random bits per umid.
a md5 of 32 LSB from the timer does not qualify ...

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

The misfortune of the wise is better than the prosperity of the fool.
-- Epicurus
-------------- 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/65170193/attachment.pgp>