From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org [79.124.17.100]) by master.gitmailbox.com (Postfix) with ESMTP id BA09B4763B for ; Sun, 14 Jan 2024 14:14:35 +0000 (UTC) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id A65BC68CD4E; Sun, 14 Jan 2024 16:14:32 +0200 (EET) Received: from mail-wm1-f51.google.com (mail-wm1-f51.google.com [209.85.128.51]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id BA63F68CA2D for ; Sun, 14 Jan 2024 16:14:26 +0200 (EET) Received: by mail-wm1-f51.google.com with SMTP id 5b1f17b1804b1-40e69b31366so16720275e9.1 for ; Sun, 14 Jan 2024 06:14:26 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1705241666; x=1705846466; darn=ffmpeg.org; h=user-agent:in-reply-to:content-disposition:mime-version:references :mail-followup-to:message-id:subject:to:from:date:from:to:cc:subject :date:message-id:reply-to; bh=9jEqQSPWL+uRM3aXyEGKqqGcwvBZ3mz9H3mm6xSxrmU=; b=HXXDYPLjCEDQKmHEmv7JZZhrhfEkBhGAvZxwr4oKR0KFB6X1fZRXmYjkIoVH59d/Ov cYT009gtkdE9lQ2o+JCkmPN2sWVLO5//c0ZLTb0k+Zr14GiPI5pcIhKE9MlBP+b1z+cW xduYqZ4xS7cT5EAH82KcQneOyjgaoELeUhGt5mSmMHeWCLffoClSmw7aDbE9yIKsyMrD Ta8fZInwlWKm5ctW4KByaoawHtvjYJM3pMVh3dLbuKyTN39PVcNdbYOh6/kaHxbqYHt8 Lg7ffXoKdPBfBJsWPyl2oX3e7C1k7Ezl5wLSSi9IOovWCa3tPVqYSdtAxX5dHkTeHts4 JmkQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705241666; x=1705846466; h=user-agent:in-reply-to:content-disposition:mime-version:references :mail-followup-to:message-id:subject:to:from:date:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=9jEqQSPWL+uRM3aXyEGKqqGcwvBZ3mz9H3mm6xSxrmU=; b=G1byloCskqOkV1KVqRQ7gY+M+5le5mWWqFiRgI+AOA0TebNJw51g58VHBg10ugRn2t 5phX9i7wFZAihlavdRmkmWGIb6zr4xfPEkAhd8CbeBRWaH5k6b2DrYcwSs0gPlGvdZaZ pAXXtSF5+4rSdG2NjFrm/FViqizcWUI9cRohTLXFGVOY3T8m+6/eW92oZYIBb9q0UJw/ GwCchKb0R++sFbeDAsvNGWRucKKwlcTuW9t+EMJfr35z1hqDPJhNW4p8pdAlcOKoKtBZ KrEWyHzjJnFOwLGbXgIP+VOtjdeE0plAYeiR+5CvXF2HSq1pPrDBpqbnVyW+9xCXdiUJ LauA== X-Gm-Message-State: AOJu0YzfA4di3Nul23PF4Qgi0LtviiBuEbLBMLVJcFg1lXX/vOwbSYh0 38VuNR+lN0yS/SOYjkh9jlN4uo/WJqk= X-Google-Smtp-Source: AGHT+IFFpsyWQiKvhk+2FAYgfINa3xCnhFf5iwKaxEHA//KP3k7KcX5IoB5vuD4nIzRd0MPoyx+/7A== X-Received: by 2002:a5d:5009:0:b0:336:7903:3675 with SMTP id e9-20020a5d5009000000b0033679033675mr2498038wrt.1.1705241665539; Sun, 14 Jan 2024 06:14:25 -0800 (PST) Received: from mariano (dynamic-adsl-84-220-189-10.clienti.tiscali.it. [84.220.189.10]) by smtp.gmail.com with ESMTPSA id m8-20020adfe948000000b00336710ddea0sm9256959wrn.59.2024.01.14.06.14.24 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 14 Jan 2024 06:14:25 -0800 (PST) Received: by mariano (Postfix, from userid 1000) id 7150FBFCDC; Sun, 14 Jan 2024 15:14:23 +0100 (CET) Date: Sun, 14 Jan 2024 15:14:23 +0100 From: Stefano Sabatini To: FFmpeg development discussions and patches Message-ID: Mail-Followup-To: FFmpeg development discussions and patches References: <20240113035106.26365-1-michael@niedermayer.cc> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20240113035106.26365-1-michael@niedermayer.cc> User-Agent: Mutt/2.1.4 (2021-12-11) Subject: Re: [FFmpeg-devel] [PATCH] avutil/eval: Use even better PRNG X-BeenThere: ffmpeg-devel@ffmpeg.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: FFmpeg development discussions and patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: FFmpeg development discussions and patches Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" Archived-At: List-Archive: List-Post: On date Saturday 2024-01-13 04:51:06 +0100, Michael Niedermayer wrote: > This is the 64bit version of Chris Doty-Humphreys SFC64 > > Compared to the LCGs these produce much better quality numbers. > Compared to LFGs this needs less state. (our LFG has 224 byte > state for its 32bit version) this has 32byte state > Also the initialization for our LFG is slower. > This is also much faster than KISS or PCG. > > This commit replaces the broken LCG used before. > (broken as it had only a period ~200M due to being put in a double) > > This changes the output from random() which is why libswresample.mak > is updated, update was done using the command in libswresample.mak > > Signed-off-by: Michael Niedermayer > --- > libavutil/eval.c | 24 +++- > libavutil/sfc64.h | 85 ++++++++++++++ > tests/fate/libswresample.mak | 208 +++++++++++++++++------------------ > tests/ref/fate/eval | 2 +- > 4 files changed, 210 insertions(+), 109 deletions(-) > create mode 100644 libavutil/sfc64.h > > diff --git a/libavutil/eval.c b/libavutil/eval.c > index dc6b3697bc2..349015d4fa3 100644 > --- a/libavutil/eval.c > +++ b/libavutil/eval.c > @@ -35,6 +35,7 @@ > #include "internal.h" > #include "log.h" > #include "mathematics.h" > +#include "sfc64.h" > #include "time.h" > #include "avstring.h" > #include "timer.h" > @@ -55,6 +56,7 @@ typedef struct Parser { > void *log_ctx; > #define VARS 10 > double *var; > + FFSFC64 *prng_state; > } Parser; > > static const AVClass eval_class = { > @@ -173,6 +175,7 @@ struct AVExpr { > } a; > struct AVExpr *param[3]; > double *var; > + FFSFC64 *prng_state; > }; > > static double etime(double v) > @@ -231,8 +234,14 @@ static double eval_expr(Parser *p, AVExpr *e) > > #define COMPUTE_NEXT_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]; \ > - r = r * 1664525 + 1013904223; \ > + FFSFC64 *s = p->prng_state + idx; \ > + uint64_t r; \ > + \ > + if (!s->counter) { \ > + r = isnan(p->var[idx]) ? 0 : p->var[idx]; \ > + ff_sfc64_init(s, r, r, r, 12); \ > + } \ > + r = ff_sfc64_get(s); \ > p->var[idx] = r; \ > > case e_random: { > @@ -329,7 +338,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->prng_state[index].counter = 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); > @@ -349,6 +362,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->prng_state); > av_freep(&e); > } > > @@ -736,7 +750,8 @@ int av_expr_parse(AVExpr **expr, const char *s, > goto end; > } > e->var= av_mallocz(sizeof(double) *VARS); > - if (!e->var) { > + e->prng_state = av_mallocz(sizeof(*e->prng_state) *VARS); > + if (!e->var || !e->prng_state) { > ret = AVERROR(ENOMEM); > goto end; > } > @@ -778,6 +793,7 @@ double av_expr_eval(AVExpr *e, const double *const_values, void *opaque) > { > Parser p = { 0 }; > p.var= e->var; > + p.prng_state= e->prng_state; > > p.const_values = const_values; > p.opaque = opaque; > diff --git a/libavutil/sfc64.h b/libavutil/sfc64.h > new file mode 100644 > index 00000000000..05f1e84cc68 > --- /dev/null > +++ b/libavutil/sfc64.h > @@ -0,0 +1,85 @@ > +/* > + * Copyright (c) 2024 Michael Niedermayer > + * > + * This file is part of FFmpeg. > + * > + * FFmpeg is free software; you can redistribute it and/or > + * modify it under the terms of the GNU Lesser General Public > + * License as published by the Free Software Foundation; either > + * version 2.1 of the License, or (at your option) any later version. > + * > + * FFmpeg is distributed in the hope that it will be useful, > + * but WITHOUT ANY WARRANTY; without even the implied warranty of > + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU > + * Lesser General Public License for more details. > + * > + * You should have received a copy of the GNU Lesser General Public > + * License along with FFmpeg; if not, write to the Free Software > + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA > + * > + * This is a implementation of SFC64, a 64-bit PRNG by Chris Doty-Humphrey. > + * > + * This Generator is much faster (0m1.872s) than 64bit KISS (0m3.823s) and PCG-XSH-RR-64/32 (0m2.700s) > + * And passes testu01 and practrand test suits. > + * nit: possibly better to put this in @file > + */ > + > +/** > + * @file > + * simple Pseudo Random Number Generator > + * > + */ > + > +#ifndef AVUTIL_SFC64_H > +#define AVUTIL_SFC64_H > + > +#include > + > +typedef struct FFSFC64 { > + uint64_t a,b,c,counter; > +} FFSFC64; > + > +static inline uint64_t ff_sfc64_get(FFSFC64 *s) { > + uint64_t tmp = s->a + s->b + s->counter++; > + s->a = s->b ^ (s->b >> 11); > + s->b = s->c + (s->c << 3); // This is a multiply by 9 > + s->c = (s->c << 24 | s->c >> 40) + tmp; > + return tmp; > +} > + > +/** > + * returns the previous random value, and steps the generator backward. > + * > + * Its safe to take values before the first, but such values can be highly > + * correlated to the seeds. Return ..., and step the generator... It is safe to take values before the first, but such values can be highly correlated to the seeds. > + */ > +static inline uint64_t ff_sfc64_reverse_get(FFSFC64 *s) { > + uint64_t prev_c = s->b * 0x8E38E38E38E38E39; > + uint64_t tmp = s->c - (prev_c << 24 | prev_c >> 40); > + s->b = s->a ^ (s->a >> 11); > + s->b ^= s->b >> 22; > + s->b ^= s->b >> 44; > + > + s->a = tmp - s->b - --s->counter; > + s->c = prev_c; > + > + return tmp; > +} > + > +/** > + * Initialize sfc64 with up to 3 seeds. > + * > + * @param rounds number of rounds mixing up state during init. generally 8-18, larger numbers will help with bad quality seeds. > + * 12 is a good choice if all 3 seeds are equal uppercase Generally after the dot. Looks good to me apart for the minor nits. Thanks!! _______________________________________________ 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".