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

Ryan Martell rdm4
Tue Jan 9 21:13:51 CET 2007


On Jan 8, 2007, at 8:24 PM, Michael Niedermayer wrote:

> 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

if i don't use a uint32_t, then the code has no dependencies on  
ffmpeg header files, and it can be compiled with gcc random.c.  I  
kind of like that better than getting rid of the single and on  
something that only happens infrequently.  Okay?

>>     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;

Like yours better.  Fixed.

>>     }
>>     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 ...

Fixed.

>>         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
>

1000 calls of this function:

91655340 dezicycles in Generate Untempered, 1 runs, 0 skips (as above)
88512620 dezicycles in Generate Untempered, 1 runs, 0 skips (static  
const)
84501480 dezicycles in Generate Untempered, 1 runs, 0 skips (y&1)*A

>
> [...]
>> /** 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 ...
nope. Fixed.

How's this?
-------------- next part --------------
A non-text attachment was scrubbed...
Name: random.c
Type: application/octet-stream
Size: 3618 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20070109/9453748d/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: random.h
Type: application/octet-stream
Size: 2408 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20070109/9453748d/attachment-0001.obj>



More information about the ffmpeg-devel mailing list