[FFmpeg-devel] [PATCH] avutil/eval: Use integer for random() state

[FFmpeg-devel] [PATCH] avutil/eval: Use integer for random() state

[Michael Niedermayer]

rounding the 64bit integer state to double between each iteration
causes a reduction in quality of the random number generator.
For example its period drops from 2^64 to around 200 million

Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
---
 libavutil/eval.c | 16 +++++++++++++---
 1 file changed, 13 insertions(+), 3 deletions(-)

diff --git a/libavutil/eval.c b/libavutil/eval.c
index bad9e4ecb8d..89c61ba4bf5 100644
--- a/libavutil/eval.c
+++ b/libavutil/eval.c
@@ -55,6 +55,7 @@ typedef struct Parser {
     void *log_ctx;
 #define VARS 10
     double *var;
+    uint64_t *var_uint64;
 } Parser;
 
 static const AVClass eval_class = {
@@ -173,6 +174,7 @@ struct AVExpr {
     } a;
     struct AVExpr *param[3];
     double *var;
+    uint64_t *var_uint64;
 };
 
 static double etime(double v)
@@ -230,9 +232,10 @@ static double eval_expr(Parser *p, AVExpr *e)
         }
         case e_random:{
             int idx= av_clip(eval_expr(p, e->param[0]), 0, VARS-1);
-            uint64_t r= isnan(p->var[idx]) ? 0 : p->var[idx];
+            uint64_t r= p->var_uint64[idx] ? p->var_uint64[idx] : (isnan(p->var[idx]) ? 0 : p->var[idx]);
             r= r*1664525+1013904223;
             p->var[idx]= r;
+            p->var_uint64[idx]= r;
             return e->value * (r * (1.0/UINT64_MAX));
         }
         case e_while: {
@@ -319,7 +322,11 @@ static double eval_expr(Parser *p, AVExpr *e)
                 case e_div: return e->value * (d2 ? (d / d2) : d * INFINITY);
                 case e_add: return e->value * (d + d2);
                 case e_last:return e->value * d2;
-                case e_st : return e->value * (p->var[av_clip(d, 0, VARS-1)]= d2);
+                case e_st :  {
+                    int index = av_clip(d, 0, VARS-1);
+                    p->var_uint64[index] = 0;
+                    return e->value * (p->var[index]= d2);
+                }
                 case e_hypot:return e->value * hypot(d, d2);
                 case e_atan2:return e->value * atan2(d, d2);
                 case e_bitand: return isnan(d) || isnan(d2) ? NAN : e->value * ((long int)d & (long int)d2);
@@ -339,6 +346,7 @@ void av_expr_free(AVExpr *e)
     av_expr_free(e->param[1]);
     av_expr_free(e->param[2]);
     av_freep(&e->var);
+    av_freep(&e->var_uint64);
     av_freep(&e);
 }
 
@@ -724,7 +732,8 @@ int av_expr_parse(AVExpr **expr, const char *s,
         goto end;
     }
     e->var= av_mallocz(sizeof(double) *VARS);
-    if (!e->var) {
+    e->var_uint64= av_mallocz(sizeof(uint64_t) *VARS);
+    if (!e->var || !e->var_uint64) {
         ret = AVERROR(ENOMEM);
         goto end;
     }
@@ -766,6 +775,7 @@ double av_expr_eval(AVExpr *e, const double *const_values, void *opaque)
 {
     Parser p = { 0 };
     p.var= e->var;
+    p.var_uint64= e->var_uint64;
 
     p.const_values = const_values;
     p.opaque     = opaque;
-- 
2.17.1

_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".

Re: [FFmpeg-devel] [PATCH] avutil/eval: Use integer for random() state

[Stefano Sabatini]

On date Tuesday 2024-01-02 03:28:45 +0100, Michael Niedermayer wrote:
> rounding the 64bit integer state to double between each iteration
> causes a reduction in quality of the random number generator.
> For example its period drops from 2^64 to around 200 million
> 
> Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
> ---
>  libavutil/eval.c | 16 +++++++++++++---
>  1 file changed, 13 insertions(+), 3 deletions(-)
> 
> diff --git a/libavutil/eval.c b/libavutil/eval.c
> index bad9e4ecb8d..89c61ba4bf5 100644
> --- a/libavutil/eval.c
> +++ b/libavutil/eval.c
> @@ -55,6 +55,7 @@ typedef struct Parser {
>      void *log_ctx;
>  #define VARS 10
>      double *var;
> +    uint64_t *var_uint64;
>  } Parser;
>  
>  static const AVClass eval_class = {
> @@ -173,6 +174,7 @@ struct AVExpr {
>      } a;
>      struct AVExpr *param[3];
>      double *var;
> +    uint64_t *var_uint64;
>  };
>  
>  static double etime(double v)
> @@ -230,9 +232,10 @@ static double eval_expr(Parser *p, AVExpr *e)
>          }
>          case e_random:{
>              int idx= av_clip(eval_expr(p, e->param[0]), 0, VARS-1);
> -            uint64_t r= isnan(p->var[idx]) ? 0 : p->var[idx];
> +            uint64_t r= p->var_uint64[idx] ? p->var_uint64[idx] : (isnan(p->var[idx]) ? 0 : p->var[idx]);
>              r= r*1664525+1013904223;
>              p->var[idx]= r;
> +            p->var_uint64[idx]= r;
>              return e->value * (r * (1.0/UINT64_MAX));
>          }
>          case e_while: {
> @@ -319,7 +322,11 @@ static double eval_expr(Parser *p, AVExpr *e)
>                  case e_div: return e->value * (d2 ? (d / d2) : d * INFINITY);
>                  case e_add: return e->value * (d + d2);
>                  case e_last:return e->value * d2;
> -                case e_st : return e->value * (p->var[av_clip(d, 0, VARS-1)]= d2);
> +                case e_st :  {
> +                    int index = av_clip(d, 0, VARS-1);

> +                    p->var_uint64[index] = 0;

can't you set this to d2 and then in case e_random:

uint64_t r = isnan(p->var[idx]) ? 0 : p->var_uint64[idx];

?

_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".

Re: [FFmpeg-devel] [PATCH] avutil/eval: Use integer for random() state

[Michael Niedermayer]

[-- Attachment #1.1: Type: text/plain, Size: 3125 bytes --]

On Tue, Jan 02, 2024 at 12:06:29PM +0100, Stefano Sabatini wrote:
> On date Tuesday 2024-01-02 03:28:45 +0100, Michael Niedermayer wrote:
> > rounding the 64bit integer state to double between each iteration
> > causes a reduction in quality of the random number generator.
> > For example its period drops from 2^64 to around 200 million
> > 
> > Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
> > ---
> >  libavutil/eval.c | 16 +++++++++++++---
> >  1 file changed, 13 insertions(+), 3 deletions(-)
> > 
> > diff --git a/libavutil/eval.c b/libavutil/eval.c
> > index bad9e4ecb8d..89c61ba4bf5 100644
> > --- a/libavutil/eval.c
> > +++ b/libavutil/eval.c
> > @@ -55,6 +55,7 @@ typedef struct Parser {
> >      void *log_ctx;
> >  #define VARS 10
> >      double *var;
> > +    uint64_t *var_uint64;
> >  } Parser;
> >  
> >  static const AVClass eval_class = {
> > @@ -173,6 +174,7 @@ struct AVExpr {
> >      } a;
> >      struct AVExpr *param[3];
> >      double *var;
> > +    uint64_t *var_uint64;
> >  };
> >  
> >  static double etime(double v)
> > @@ -230,9 +232,10 @@ static double eval_expr(Parser *p, AVExpr *e)
> >          }
> >          case e_random:{
> >              int idx= av_clip(eval_expr(p, e->param[0]), 0, VARS-1);
> > -            uint64_t r= isnan(p->var[idx]) ? 0 : p->var[idx];
> > +            uint64_t r= p->var_uint64[idx] ? p->var_uint64[idx] : (isnan(p->var[idx]) ? 0 : p->var[idx]);
> >              r= r*1664525+1013904223;
> >              p->var[idx]= r;
> > +            p->var_uint64[idx]= r;
> >              return e->value * (r * (1.0/UINT64_MAX));
> >          }
> >          case e_while: {
> > @@ -319,7 +322,11 @@ static double eval_expr(Parser *p, AVExpr *e)
> >                  case e_div: return e->value * (d2 ? (d / d2) : d * INFINITY);
> >                  case e_add: return e->value * (d + d2);
> >                  case e_last:return e->value * d2;
> > -                case e_st : return e->value * (p->var[av_clip(d, 0, VARS-1)]= d2);
> > +                case e_st :  {
> > +                    int index = av_clip(d, 0, VARS-1);
> 
> > +                    p->var_uint64[index] = 0;
> 
> can't you set this to d2 and then in case e_random:
> 
> uint64_t r = isnan(p->var[idx]) ? 0 : p->var_uint64[idx];
> 
> ?

setting var_uint64[] to d2 would require us to check for non representable
cases like outside 0..UINT64_MAX and NAN.
We would have to do this for every st() even though very few actually get used
as seeds. So it would slow it down.

if we set it to 0, then we only need to do these checks in the first call to random
(or just require the user not to use random with such values)
subsequent calls use integers and need not check the double value

thx

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

The day soldiers stop bringing you their problems is the day you have stopped 
leading them. They have either lost confidence that you can help or concluded 
you do not care. Either case is a failure of leadership. - Colin Powell

[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

[-- Attachment #2: Type: text/plain, Size: 251 bytes --]

_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".