diff options
Diffstat (limited to 'thirdparty/misc')
| -rw-r--r-- | thirdparty/misc/open-simplex-noise.c | 11 | ||||
| -rw-r--r-- | thirdparty/misc/pcg.cpp | 33 | ||||
| -rw-r--r-- | thirdparty/misc/pcg.h | 1 | ||||
| -rw-r--r-- | thirdparty/misc/triangulator.h | 4 |
4 files changed, 42 insertions, 7 deletions
diff --git a/thirdparty/misc/open-simplex-noise.c b/thirdparty/misc/open-simplex-noise.c index 42f2fbb5be..88fbd3e51d 100644 --- a/thirdparty/misc/open-simplex-noise.c +++ b/thirdparty/misc/open-simplex-noise.c @@ -189,14 +189,15 @@ int open_simplex_noise(int64_t seed, struct osn_context *ctx) permGradIndex3D = ctx->permGradIndex3D; // -- GODOT end -- + uint64_t seedU = seed; for (i = 0; i < 256; i++) source[i] = (int16_t) i; - seed = seed * 6364136223846793005LL + 1442695040888963407LL; - seed = seed * 6364136223846793005LL + 1442695040888963407LL; - seed = seed * 6364136223846793005LL + 1442695040888963407LL; + seedU = seedU * 6364136223846793005ULL + 1442695040888963407ULL; + seedU = seedU * 6364136223846793005ULL + 1442695040888963407ULL; + seedU = seedU * 6364136223846793005ULL + 1442695040888963407ULL; for (i = 255; i >= 0; i--) { - seed = seed * 6364136223846793005LL + 1442695040888963407LL; - r = (int)((seed + 31) % (i + 1)); + seedU = seedU * 6364136223846793005ULL + 1442695040888963407ULL; + r = (int)((seedU + 31) % (i + 1)); if (r < 0) r += (i + 1); perm[i] = source[r]; diff --git a/thirdparty/misc/pcg.cpp b/thirdparty/misc/pcg.cpp index c421e16f89..914a353874 100644 --- a/thirdparty/misc/pcg.cpp +++ b/thirdparty/misc/pcg.cpp @@ -23,3 +23,36 @@ void pcg32_srandom_r(pcg32_random_t* rng, uint64_t initstate, uint64_t initseq) rng->state += initstate; pcg32_random_r(rng); } + +// Source from https://github.com/imneme/pcg-c-basic/blob/master/pcg_basic.c +// pcg32_boundedrand_r(rng, bound): +// Generate a uniformly distributed number, r, where 0 <= r < bound +uint32_t pcg32_boundedrand_r(pcg32_random_t *rng, uint32_t bound) { + // To avoid bias, we need to make the range of the RNG a multiple of + // bound, which we do by dropping output less than a threshold. + // A naive scheme to calculate the threshold would be to do + // + // uint32_t threshold = 0x100000000ull % bound; + // + // but 64-bit div/mod is slower than 32-bit div/mod (especially on + // 32-bit platforms). In essence, we do + // + // uint32_t threshold = (0x100000000ull-bound) % bound; + // + // because this version will calculate the same modulus, but the LHS + // value is less than 2^32. + uint32_t threshold = -bound % bound; + + // Uniformity guarantees that this loop will terminate. In practice, it + // should usually terminate quickly; on average (assuming all bounds are + // equally likely), 82.25% of the time, we can expect it to require just + // one iteration. In the worst case, someone passes a bound of 2^31 + 1 + // (i.e., 2147483649), which invalidates almost 50% of the range. In + // practice, bounds are typically small and only a tiny amount of the range + // is eliminated. + for (;;) { + uint32_t r = pcg32_random_r(rng); + if (r >= threshold) + return r % bound; + } +} diff --git a/thirdparty/misc/pcg.h b/thirdparty/misc/pcg.h index 6f42b3b094..0faab73e64 100644 --- a/thirdparty/misc/pcg.h +++ b/thirdparty/misc/pcg.h @@ -11,5 +11,6 @@ typedef struct { uint64_t state; uint64_t inc; } pcg32_random_t; uint32_t pcg32_random_r(pcg32_random_t* rng); void pcg32_srandom_r(pcg32_random_t* rng, uint64_t initstate, uint64_t initseq); +uint32_t pcg32_boundedrand_r(pcg32_random_t* rng, uint32_t bound); #endif // RANDOM_H diff --git a/thirdparty/misc/triangulator.h b/thirdparty/misc/triangulator.h index c85792fd50..24b79e7d34 100644 --- a/thirdparty/misc/triangulator.h +++ b/thirdparty/misc/triangulator.h @@ -21,9 +21,9 @@ #ifndef TRIANGULATOR_H #define TRIANGULATOR_H -#include "core/list.h" +#include "core/templates/list.h" #include "core/math/vector2.h" -#include "core/set.h" +#include "core/templates/set.h" //2D point structure |