/src/ffmpeg/libavutil/sfc64.h
Line | Count | Source |
1 | | /* |
2 | | * Copyright (c) 2024 Michael Niedermayer <michael-ffmpeg@niedermayer.cc> |
3 | | * |
4 | | * This file is part of FFmpeg. |
5 | | * |
6 | | * FFmpeg is free software; you can redistribute it and/or |
7 | | * modify it under the terms of the GNU Lesser General Public |
8 | | * License as published by the Free Software Foundation; either |
9 | | * version 2.1 of the License, or (at your option) any later version. |
10 | | * |
11 | | * FFmpeg is distributed in the hope that it will be useful, |
12 | | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 | | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
14 | | * Lesser General Public License for more details. |
15 | | * |
16 | | * You should have received a copy of the GNU Lesser General Public |
17 | | * License along with FFmpeg; if not, write to the Free Software |
18 | | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
19 | | * |
20 | | */ |
21 | | |
22 | | /** |
23 | | * @file |
24 | | * simple Pseudo Random Number Generator |
25 | | * |
26 | | * This is a implementation of SFC64, a 64-bit PRNG by Chris Doty-Humphrey. |
27 | | * |
28 | | * This Generator is much faster (0m1.872s) than 64bit KISS (0m3.823s) and PCG-XSH-RR-64/32 (0m2.700s) |
29 | | * And passes testu01 and practrand test suits. |
30 | | */ |
31 | | |
32 | | #ifndef AVUTIL_SFC64_H |
33 | | #define AVUTIL_SFC64_H |
34 | | |
35 | | #include <inttypes.h> |
36 | | |
37 | | typedef struct FFSFC64 { |
38 | | uint64_t a,b,c,counter; |
39 | | } FFSFC64; |
40 | | |
41 | 0 | static inline uint64_t ff_sfc64_get(FFSFC64 *s) { |
42 | 0 | uint64_t tmp = s->a + s->b + s->counter++; |
43 | 0 | s->a = s->b ^ (s->b >> 11); |
44 | 0 | s->b = s->c + (s->c << 3); // This is a multiply by 9 |
45 | 0 | s->c = (s->c << 24 | s->c >> 40) + tmp; |
46 | 0 | return tmp; |
47 | 0 | } |
48 | | |
49 | | /** |
50 | | * Return the previous random value, and step the generator backward. |
51 | | * |
52 | | * It is safe to take values before the first, but such values can be highly |
53 | | * correlated to the seeds. |
54 | | */ |
55 | 0 | static inline uint64_t ff_sfc64_reverse_get(FFSFC64 *s) { |
56 | 0 | uint64_t prev_c = s->b * 0x8E38E38E38E38E39; |
57 | 0 | uint64_t tmp = s->c - (prev_c << 24 | prev_c >> 40); |
58 | 0 | s->b = s->a ^ (s->a >> 11); |
59 | 0 | s->b ^= s->b >> 22; |
60 | 0 | s->b ^= s->b >> 44; |
61 | 0 |
|
62 | 0 | s->a = tmp - s->b - --s->counter; |
63 | 0 | s->c = prev_c; |
64 | 0 |
|
65 | 0 | return tmp; |
66 | 0 | } |
67 | | |
68 | | /** |
69 | | * Initialize sfc64 with up to 3 seeds. |
70 | | * |
71 | | * @param rounds number of rounds mixing up state during init. Generally 8-18, larger numbers will help with bad quality seeds. |
72 | | * 12 is a good choice if all 3 seeds are equal |
73 | | * |
74 | | */ |
75 | 0 | static inline void ff_sfc64_init(FFSFC64 *s, uint64_t seeda, uint64_t seedb, uint64_t seedc, int rounds) { |
76 | 0 | s->a = seeda; |
77 | 0 | s->b = seedb; |
78 | 0 | s->c = seedc; |
79 | 0 | s->counter = 1; |
80 | 0 | while (rounds--) |
81 | 0 | ff_sfc64_get(s); |
82 | 0 | } |
83 | | |
84 | | #endif // AVUTIL_SFC64_H |