[Ffmpeg-devel] [RFC] av_random...

[Michael Niedermayer]

Hi

On Mon, Jan 08, 2007 at 11:56:24AM -0600, Ryan Martell wrote:
[...]
> >>{
> >>    unsigned int y= 0;
> >
> >y is not read before its written so the =0 is redundant
> 
> Fixed.
> 
> How's this?
> 

[...]
> #include <stdio.h>
> #include "random.h"
> 
> //#define DEBUG
> 
> /* Period parameters */
> #define M 397
> #define A 0x9908b0df	/* constant vector a */
> #define UPPER_MASK 0x80000000	/* most significant w-r bits */
> #define LOWER_MASK 0x7fffffff	/* least significant r bits */
> 
> /** initializes mt[AV_RANDOM_N] with a seed */
> void av_init_random(unsigned long seed, AVRandomState *state)
> {
>     int index;
> 
>     /*
>      This differs from the wikipedia article.  Source is from the Makoto
>      Makoto Matsumoto and Takuji Nishimura code, with the following comment:
>      */
>      /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
>      /* In the previous versions, MSBs of the seed affect   */
>      /* only MSBs of the array mt[].                        */
>     state->mt[0] = seed & 0xffffffff;

if seed is a uint32_t then the & 0xffffffff; becomes unneeded


>     for (index = 1; index < AV_RANDOM_N; index++) {
>         state->mt[index] = (((unsigned long) 1812433253 * (state->mt[index - 1] ^ (state->mt[index - 1] >> 30)) + index)) & 0xffffffff;

(unsigned long) 1812433253 -> 1812433253U or UL

also there are (( ... )) (double brackets)

maybe the following would be more readable? but iam fine with your variant
too

unsigned int prev= state->mt[index - 1];
state->mt[index] = (1812433253UL * (prev ^ (prev>>30)) + index) & 0xffffffff;


>     }
>     state->index= index; // will cause it to generate untempered numbers the first iteration
> }
> 
> /** generate AV_RANDOM_N words at one time (which will then be tempered later) */
> void av_random_generate_untempered_numbers(AVRandomState *state)
> {
>     if (state->index >= AV_RANDOM_N) {		

trailing tabs

and maybe this function should have a comment like "this should not be called
directly by the user" or is there some advantage if the user calls it?

if he isnt supposed to call it then the if() also becomes fairly useless ...


>         unsigned int mag01[2] = {0x0, A};
>         int kk;
>         unsigned int y;
> 
>         for (kk = 0; kk < AV_RANDOM_N - M; kk++) {
>             y = (state->mt[kk] & UPPER_MASK) | (state->mt[kk + 1] & LOWER_MASK);
>             state->mt[kk] = state->mt[kk + M] ^ (y >> 1) ^ mag01[y & 0x1];
>         }
>         for (; kk < AV_RANDOM_N - 1; kk++) {
>             y = (state->mt[kk] & UPPER_MASK) | (state->mt[kk + 1] & LOWER_MASK);
>             state->mt[kk] = state->mt[kk + (M - AV_RANDOM_N)] ^ (y >> 1) ^ mag01[y & 0x1];
>         }
>         y = (state->mt[AV_RANDOM_N - 1] & UPPER_MASK) | (state->mt[0] & LOWER_MASK);
>         state->mt[AV_RANDOM_N - 1] = state->mt[M - 1] ^ (y >> 1) ^ mag01[y & 0x1];
>         state->index = 0;
>     }
> }

is mag01[y & 0x1] faster then (y&1)*A or (-(y&1))&A ?
and mag01 should if it is faster be static const

and see START/STOP_TIMER for simple benchmarking


[...]
> /** return random in range [0-1] as double */
> static inline double av_random_real1(AVRandomState *state)
> {
>     /* divided by 2^32-1 */
>     return av_random(state) * (1.0 / 4294967295.0);

something tells me that 4294967296 is a better choice, is there some reason
why you choose 4294967295 ?
the thing is that 1.0 / 4294967295 cannot be represented exactly as
a floating point variable ...

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

When you are offended at any man's fault, turn to yourself and study your
own failings. Then you will forget your anger. -- Epictetus
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20070109/e2c278c2/attachment.pgp>