From patchwork Tue Jan 9 01:55:21 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Michael Niedermayer X-Patchwork-Id: 45541 Delivered-To: ffmpegpatchwork2@gmail.com Received: by 2002:a05:6a20:bf2f:b0:199:de12:6fa6 with SMTP id gc47csp135263pzb; Mon, 8 Jan 2024 17:55:33 -0800 (PST) X-Google-Smtp-Source: AGHT+IGfZQGLGHTr3w1jEp/s+7DWE2l/3EHR07XjI1L/wf3zdrnqOAt4H30oqp/Ismc9kMIgMpuU X-Received: by 2002:a17:907:1b0b:b0:a29:459d:a168 with SMTP id mp11-20020a1709071b0b00b00a29459da168mr164249ejc.155.1704765332990; Mon, 08 Jan 2024 17:55:32 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1704765332; cv=none; d=google.com; s=arc-20160816; b=KcE3fQy5jwEvAZxehb4GGwVDFqf5CVLOTXoMh0k3IP9ppmqDgnNN2YoTRNkr2lBAJd Tgx+fMbZsZZU+Hc58PLIiLzEutVohSiqG+vsVoVKqoRX/S9ZLloQMm+Upv8VhCNoZyUP O4uYvcoQcSc1VxEOvl3OFiPu5QEZ7OvVSZCf+s8i5ZTjbbKJAEvlfznY4OrYfcn1KnT9 qhxoEnnUKe0SlJF6OCQqKrrqnvP+IQaHMFFZn+sMsiw4VsSaO1MfyHOhfXKDnwEgG4PE JjdeJCwYvVg4HaKHw9mKScSK821bZhsrJETxGDwOZnJsw/QxLwZpKSu7t+1eWVSvLLqW z83w== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:content-transfer-encoding:mime-version:reply-to :list-subscribe:list-help:list-post:list-archive:list-unsubscribe :list-id:precedence:subject:message-id:date:to:from:dkim-signature :delivered-to; bh=CbX4j/Y/fSRGPNx7/ie5kf5QC0m0qFN3wzvwMuVA6f8=; fh=e5zN9xSzcxLA6bGo3lF+CqTbY/oLwzApV03EO/RBfgQ=; b=RVsXW5G01qfdxeS/cwKsyYOxQdz31y2DctgptTvk9mgxkQUdAeyBoYuGH/2p1cJIem 1onGua10vxD5RUPYKpo0d9TC0R0xih21iHemKmzVI8fApeGPB3npagCKnqITM6jjTcP+ mdzlqIa1wYQdo92wlkvF58hW4d0I2+jM/upqzJc87VN0iGu/McW2mBwsVBJ5Sdy8SKZN lqOMkAONc9PUJy1bV9JXwruTgpG+TMaov31GboMzhqpOGD6u6cooHjnSD5LhSnjHS5zY Y4/5SfQEzxttSF5eHzZG6wnEn0mBuR/PfDCarvi9BxbvuP96QbmG/UpUR7IPNQoMlHfL qMXw== ARC-Authentication-Results: i=1; mx.google.com; dkim=neutral (body hash did not verify) header.i=@niedermayer.cc header.s=gm1 header.b=OWkXFiF1; spf=pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) smtp.mailfrom=ffmpeg-devel-bounces@ffmpeg.org Return-Path: Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org. [79.124.17.100]) by mx.google.com with ESMTP id q1-20020a1709060e4100b00a28c04e3171si402789eji.174.2024.01.08.17.55.32; Mon, 08 Jan 2024 17:55:32 -0800 (PST) Received-SPF: pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) client-ip=79.124.17.100; Authentication-Results: mx.google.com; dkim=neutral (body hash did not verify) header.i=@niedermayer.cc header.s=gm1 header.b=OWkXFiF1; spf=pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) smtp.mailfrom=ffmpeg-devel-bounces@ffmpeg.org Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id 93CAC68BCEC; Tue, 9 Jan 2024 03:55:29 +0200 (EET) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org 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 505A168BCEC for ; Tue, 9 Jan 2024 03:55:23 +0200 (EET) Received: by mail.gandi.net (Postfix) with ESMTPSA id 77C65240005 for ; Tue, 9 Jan 2024 01:55:22 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=niedermayer.cc; s=gm1; t=1704765322; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc; bh=NQUmqz30J8VgiQcjt6Bba5xtwuid1OHG3aducpo4k6A=; b=OWkXFiF19EF/GIaATbHU2InxQ/aPfraFO4oHACHpKgqM8RgmCacNIXmpWFeVz/RDMTAJb0 8KPqECqE5h3FKyctMa2LTN1qSo2XNZlj7NDB3jL0SULAUfu5Hvauizis3ZPrHYIDr9sxvk YTSRvHTkfq8+han6yaPQSCxv1t+fYsXUZkC3kH3j157jX4+Gah/rok8weWmM0K5yPXj6d9 20ERPWP6RNDRZom5TnsCnMS0Qe4Qo0OI2u5Y+ocDcgwuSQ+ICiUZ/QpexRSpmoSlDdUhel JJT5NNNwt9TObhzX/f429+xl3nQ3PBB4TWtmf1aMAQriuvLKTwRz2g3t3X+HzA== From: Michael Niedermayer To: FFmpeg development discussions and patches Date: Tue, 9 Jan 2024 02:55:21 +0100 Message-Id: <20240109015521.26231-1-michael@niedermayer.cc> X-Mailer: git-send-email 2.17.1 X-GND-Sasl: michael@niedermayer.cc Subject: [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 MIME-Version: 1.0 Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" X-TUID: w3m4eQs9LymU 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 could be merged with the change to integer LCG Also a few fate tests need an update. I will update fate if SFC64 is the chosen PRNG Signed-off-by: Michael Niedermayer --- libavutil/eval.c | 26 ++++++++++++-------- libavutil/sfc64.h | 59 +++++++++++++++++++++++++++++++++++++++++++++ tests/ref/fate/eval | 2 +- 3 files changed, 76 insertions(+), 11 deletions(-) create mode 100644 libavutil/sfc64.h diff --git a/libavutil/eval.c b/libavutil/eval.c index 9d41140056c..d15becf9cda 100644 --- a/libavutil/eval.c +++ b/libavutil/eval.c @@ -33,6 +33,7 @@ #include "eval.h" #include "ffmath.h" #include "internal.h" +#include "sfc64.h" #include "log.h" #include "mathematics.h" #include "time.h" @@ -55,7 +56,7 @@ typedef struct Parser { void *log_ctx; #define VARS 10 double *var; - uint64_t *var_uint64; + SFC64 *prng_state; } Parser; static const AVClass eval_class = { @@ -174,7 +175,7 @@ struct AVExpr { } a; struct AVExpr *param[3]; double *var; - uint64_t *var_uint64; + SFC64 *prng_state; }; static double etime(double v) @@ -233,10 +234,15 @@ 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 = p->var_uint64[idx] ? p->var_uint64[idx] : (isnan(p->var[idx]) ? 0 : p->var[idx]);\ - r = r * 1664525 + 1013904223; \ + SFC64 *s = p->prng_state + idx; \ + uint64_t r; \ + \ + if (!s->counter) { \ + r = isnan(p->var[idx]) ? 0 : p->var[idx]; \ + sfc64_init(s, r, r, r, 12); \ + } \ + r = sfc64_get(s); \ p->var[idx] = r; \ - p->var_uint64[idx]= r; case e_random: { COMPUTE_NEXT_RANDOM(); @@ -334,7 +340,7 @@ static double eval_expr(Parser *p, AVExpr *e) case e_last:return e->value * d2; case e_st : { int index = av_clip(d, 0, VARS-1); - p->var_uint64[index] = 0; + p->prng_state[index].counter = 0; return e->value * (p->var[index]= d2); } case e_hypot:return e->value * hypot(d, d2); @@ -356,7 +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->var_uint64); + av_freep(&e->prng_state); av_freep(&e); } @@ -744,8 +750,8 @@ int av_expr_parse(AVExpr **expr, const char *s, goto end; } e->var= av_mallocz(sizeof(double) *VARS); - e->var_uint64= av_mallocz(sizeof(uint64_t) *VARS); - if (!e->var || !e->var_uint64) { + e->prng_state = av_mallocz(sizeof(*e->prng_state) *VARS); + if (!e->var || !e->prng_state) { ret = AVERROR(ENOMEM); goto end; } @@ -787,7 +793,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.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..25bc43abef1 --- /dev/null +++ b/libavutil/sfc64.h @@ -0,0 +1,59 @@ +/* + * 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. + * + */ + +/** + * @file + * simple Pseudo Random Number Generator + * + */ + +#ifndef AVUTIL_SFC64_H +#define AVUTIL_SFC64_H + +#include + +typedef struct SFC64 { + uint64_t a,b,c,counter; +} SFC64; + +static inline uint64_t sfc64_get(SFC64 *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; +} + +static inline void sfc64_init(SFC64 *s, uint64_t seeda, uint64_t seedb, uint64_t seedc, int rounds) { + s->a = seeda; + s->b = seedb; + s->c = seedc; + s->counter = 1; + while (rounds--) + sfc64_get(s); +} + +#endif // AVUTIL_SFC64_H diff --git a/tests/ref/fate/eval b/tests/ref/fate/eval index 5b4d93f4274..441f9846c46 100644 --- a/tests/ref/fate/eval +++ b/tests/ref/fate/eval @@ -257,7 +257,7 @@ Evaluating 'root(sin(ld(0))+6+sin(ld(0)/12)-log(ld(0)), 100)' 'root(sin(ld(0))+6+sin(ld(0)/12)-log(ld(0)), 100)' -> 60.965601 Evaluating '7000000B*random(0)' -'7000000B*random(0)' -> 0.003078 +'7000000B*random(0)' -> 12864914.486611 Evaluating 'squish(2)' 'squish(2)' -> 0.000335