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 458CE486D3 for ; Tue, 16 Jan 2024 00:27:36 +0000 (UTC) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id 4A6BC68CFE4; Tue, 16 Jan 2024 02:27:34 +0200 (EET) Received: from relay1-d.mail.gandi.net (relay1-d.mail.gandi.net [217.70.183.193]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 4AD71680066 for ; Tue, 16 Jan 2024 02:27:27 +0200 (EET) Received: by mail.gandi.net (Postfix) with ESMTPSA id B1B87240004 for ; Tue, 16 Jan 2024 00:27:26 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=niedermayer.cc; s=gm1; t=1705364846; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=vQfsseWdZrzkT+9wcpA2P3IBJ2+LnbMfnwJ+zAlc38E=; b=MWT3tHJb8I7FdPArsv7v1F43xDZ5C6YzQZ5f9AEnIOQzIGQewee9BKjX4lrtzuQBSel0kx RpLY70C6cknRTRT2bWBMF2YZfwJBMKRi8+Nk5+WOA1lOk9EIGgLJFbu5drgORofLfeJotp nNqQVijopSI/o3kjv/PPa2O3ucjDPwvjlGKZZdNoJPkLNEda+36zo/hhnu6RVS7C+V+Trr tYUz+SnOoirQPxA7fMeqWrdHFpAxyCyV3YjTEI8O79BAFtqLlilh/zgNAdZqPFAFJlV2dW TbpvfF4Q9r3SIcA74RSswxoWB+dHdE6a5dzgA0IsF5DXcQBcngCOvkBCp0OffQ== Date: Tue, 16 Jan 2024 01:27:26 +0100 From: Michael Niedermayer To: FFmpeg development discussions and patches Message-ID: <20240116002726.GM6420@pb2> References: <20240113035106.26365-1-michael@niedermayer.cc> MIME-Version: 1.0 In-Reply-To: X-GND-Sasl: michael@niedermayer.cc 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: multipart/mixed; boundary="===============4236510401226717619==" Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" Archived-At: List-Archive: List-Post: --===============4236510401226717619== Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="HtYMPGTR7V/dd7i3" Content-Disposition: inline --HtYMPGTR7V/dd7i3 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Sun, Jan 14, 2024 at 03:14:23PM +0100, Stefano Sabatini wrote: > On date Saturday 2024-01-13 04:51:06 +0100, Michael Niedermayer wrote: > > This is the 64bit version of Chris Doty-Humphreys SFC64 > >=20 > > 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. > >=20 > > This commit replaces the broken LCG used before. > > (broken as it had only a period ~200M due to being put in a double) > >=20 > > This changes the output from random() which is why libswresample.mak > > is updated, update was done using the command in libswresample.mak > >=20 > > 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 > >=20 > > 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; > > =20 > > static const AVClass eval_class =3D { > > @@ -173,6 +175,7 @@ struct AVExpr { > > } a; > > struct AVExpr *param[3]; > > double *var; > > + FFSFC64 *prng_state; > > }; > > =20 > > static double etime(double v) > > @@ -231,8 +234,14 @@ static double eval_expr(Parser *p, AVExpr *e) > > =20 > > #define COMPUTE_NEXT_RANDOM() \ > > int idx =3D av_clip(eval_expr(p, e->param[0]), 0, VARS-1);= \ > > - uint64_t r =3D isnan(p->var[idx]) ? 0 : p->var[idx]; = \ > > - r =3D r * 1664525 + 1013904223; = \ > > + FFSFC64 *s =3D p->prng_state + idx; = \ > > + uint64_t r; \ > > + \ > > + if (!s->counter) { \ > > + r =3D isnan(p->var[idx]) ? 0 : p->var[idx]; = \ > > + ff_sfc64_init(s, r, r, r, 12); \ > > + } \ > > + r =3D ff_sfc64_get(s); = \ > > p->var[idx] =3D r; = \ > > =20 > > 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 * INF= INITY); > > 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, VA= RS-1)]=3D d2); > > + case e_st : { > > + int index =3D av_clip(d, 0, VARS-1); > > + p->prng_state[index].counter =3D 0; > > + return e->value * (p->var[index]=3D 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); > > } > > =20 > > @@ -736,7 +750,8 @@ int av_expr_parse(AVExpr **expr, const char *s, > > goto end; > > } > > e->var=3D av_mallocz(sizeof(double) *VARS); > > - if (!e->var) { > > + e->prng_state =3D av_mallocz(sizeof(*e->prng_state) *VARS); > > + if (!e->var || !e->prng_state) { > > ret =3D AVERROR(ENOMEM); > > goto end; > > } > > @@ -778,6 +793,7 @@ double av_expr_eval(AVExpr *e, const double *const_= values, void *opaque) > > { > > Parser p =3D { 0 }; > > p.var=3D e->var; > > + p.prng_state=3D e->prng_state; > > =20 > > p.const_values =3D const_values; > > p.opaque =3D 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 > > + * >=20 > > + * This is a implementation of SFC64, a 64-bit PRNG by Chris Doty-Hump= hrey. > > + * > > + * 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. > > + * >=20 > nit: possibly better to put this in @file will move >=20 > > + */ > > + > > +/** > > + * @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 =3D s->a + s->b + s->counter++; > > + s->a =3D s->b ^ (s->b >> 11); > > + s->b =3D s->c + (s->c << 3); // This is a multiply by 9 > > + s->c =3D (s->c << 24 | s->c >> 40) + tmp; > > + return tmp; > > +} > > + >=20 > > +/** > > + * returns the previous random value, and steps the generator backward. > > + * > > + * Its safe to take values before the first, but such values can be hi= ghly > > + * correlated to the seeds. >=20 > Return ..., and step the generator... >=20 > It is safe to take values before the first, but such values can be highly > correlated to the seeds. will change >=20 > > + */ > > +static inline uint64_t ff_sfc64_reverse_get(FFSFC64 *s) { > > + uint64_t prev_c =3D s->b * 0x8E38E38E38E38E39; > > + uint64_t tmp =3D s->c - (prev_c << 24 | prev_c >> 40); > > + s->b =3D s->a ^ (s->a >> 11); > > + s->b ^=3D s->b >> 22; > > + s->b ^=3D s->b >> 44; > > + > > + s->a =3D tmp - s->b - --s->counter; > > + s->c =3D prev_c; > > + > > + return tmp; > > +} > > + > > +/** > > + * Initialize sfc64 with up to 3 seeds. > > + * >=20 > > + * @param rounds number of rounds mixing up state during init. general= ly 8-18, larger numbers will help with bad quality seeds. > > + * 12 is a good choice if all 3 seeds are equal >=20 > uppercase Generally after the dot. >=20 > Looks good to me apart for the minor nits. ok, will apply with these changes thx [...] --=20 Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB Everything should be made as simple as possible, but not simpler. -- Albert Einstein --HtYMPGTR7V/dd7i3 Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iF0EABEIAB0WIQSf8hKLFH72cwut8TNhHseHBAsPqwUCZaXNbQAKCRBhHseHBAsP qzXHAJ9YmNSaWLvCyFyjTgM92yapghnffACeIUIhY89WPO1c+FW/H1Nb9c4DjXY= =ruf4 -----END PGP SIGNATURE----- --HtYMPGTR7V/dd7i3-- --===============4236510401226717619== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ 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". --===============4236510401226717619==--