summaryrefslogtreecommitdiff
path: root/thirdparty/misc
diff options
context:
space:
mode:
Diffstat (limited to 'thirdparty/misc')
-rw-r--r--thirdparty/misc/easing_equations.cpp35
-rw-r--r--thirdparty/misc/open-simplex-noise.c31
-rw-r--r--thirdparty/misc/open-simplex-noise.h6
-rw-r--r--thirdparty/misc/pcg.cpp33
-rw-r--r--thirdparty/misc/pcg.h1
-rw-r--r--thirdparty/misc/r128.h10
-rw-r--r--thirdparty/misc/triangulator.cpp20
-rw-r--r--thirdparty/misc/triangulator.h4
8 files changed, 93 insertions, 47 deletions
diff --git a/thirdparty/misc/easing_equations.cpp b/thirdparty/misc/easing_equations.cpp
index bc84564b19..af48aaf079 100644
--- a/thirdparty/misc/easing_equations.cpp
+++ b/thirdparty/misc/easing_equations.cpp
@@ -188,7 +188,8 @@ static real_t out_in(real_t t, real_t b, real_t c, real_t d) {
///////////////////////////////////////////////////////////////////////////
namespace cubic {
static real_t in(real_t t, real_t b, real_t c, real_t d) {
- return c * (t /= d) * t * t + b;
+ t /= d;
+ return c * t * t * t + b;
}
static real_t out(real_t t, real_t b, real_t c, real_t d) {
@@ -197,8 +198,10 @@ static real_t out(real_t t, real_t b, real_t c, real_t d) {
}
static real_t in_out(real_t t, real_t b, real_t c, real_t d) {
- if ((t /= d / 2) < 1) return c / 2 * t * t * t + b;
- return c / 2 * ((t -= 2) * t * t + 2) + b;
+ t /= d / 2;
+ if (t < 1) return c / 2 * t * t * t + b;
+ t -= 2;
+ return c / 2 * (t * t * t + 2) + b;
}
static real_t out_in(real_t t, real_t b, real_t c, real_t d) {
@@ -210,16 +213,22 @@ static real_t out_in(real_t t, real_t b, real_t c, real_t d) {
///////////////////////////////////////////////////////////////////////////
namespace circ {
static real_t in(real_t t, real_t b, real_t c, real_t d) {
- return -c * (sqrt(1 - (t /= d) * t) - 1) + b; // TODO: ehrich: operation with t is undefined
+ t /= d;
+ return -c * (sqrt(1 - t * t) - 1) + b;
}
static real_t out(real_t t, real_t b, real_t c, real_t d) {
- return c * sqrt(1 - (t = t / d - 1) * t) + b; // TODO: ehrich: operation with t is undefined
+ t = t / d - 1;
+ return c * sqrt(1 - t * t) + b;
}
static real_t in_out(real_t t, real_t b, real_t c, real_t d) {
- if ((t /= d / 2) < 1) return -c / 2 * (sqrt(1 - t * t) - 1) + b;
- return c / 2 * (sqrt(1 - t * (t -= 2)) + 1) + b; // TODO: ehrich: operation with t is undefined
+ t /= d / 2;
+ if (t < 1) {
+ return -c / 2 * (sqrt(1 - t * t) - 1) + b;
+ }
+ t -= 2;
+ return c / 2 * (sqrt(1 - t * t) + 1) + b;
}
static real_t out_in(real_t t, real_t b, real_t c, real_t d) {
@@ -271,14 +280,16 @@ static real_t in(real_t t, real_t b, real_t c, real_t d) {
static real_t out(real_t t, real_t b, real_t c, real_t d) {
float s = 1.70158f;
- return c * ((t = t / d - 1) * t * ((s + 1) * t + s) + 1) + b; // TODO: ehrich: operation with t is undefined
+ t = t / d - 1;
+ return c * (t * t * ((s + 1) * t + s) + 1) + b;
}
static real_t in_out(real_t t, real_t b, real_t c, real_t d) {
- float s = 1.70158f;
- if ((t /= d / 2) < 1) return c / 2 * (t * t * (((s *= (1.525f)) + 1) * t - s)) + b; // TODO: ehrich: operation with s is undefined
- float postFix = t -= 2;
- return c / 2 * ((postFix)*t * (((s *= (1.525f)) + 1) * t + s) + 2) + b; // TODO: ehrich: operation with s is undefined
+ float s = 1.70158f * 1.525f;
+ t /= d / 2;
+ if (t < 1) return c / 2 * (t * t * ((s + 1) * t - s)) + b;
+ t -= 2;
+ return c / 2 * (t * t * ((s + 1) * t + s) + 2) + b;
}
static real_t out_in(real_t t, real_t b, real_t c, real_t d) {
diff --git a/thirdparty/misc/open-simplex-noise.c b/thirdparty/misc/open-simplex-noise.c
index 42f2fbb5be..44a072cad1 100644
--- a/thirdparty/misc/open-simplex-noise.c
+++ b/thirdparty/misc/open-simplex-noise.c
@@ -100,27 +100,27 @@ static const signed char gradients4D[] = {
-3, -1, -1, -1, -1, -3, -1, -1, -1, -1, -3, -1, -1, -1, -1, -3,
};
-static double extrapolate2(struct osn_context *ctx, int xsb, int ysb, double dx, double dy)
+static double extrapolate2(const struct osn_context *ctx, int xsb, int ysb, double dx, double dy)
{
- int16_t *perm = ctx->perm;
+ const int16_t *perm = ctx->perm;
int index = perm[(perm[xsb & 0xFF] + ysb) & 0xFF] & 0x0E;
return gradients2D[index] * dx
+ gradients2D[index + 1] * dy;
}
-static double extrapolate3(struct osn_context *ctx, int xsb, int ysb, int zsb, double dx, double dy, double dz)
+static double extrapolate3(const struct osn_context *ctx, int xsb, int ysb, int zsb, double dx, double dy, double dz)
{
- int16_t *perm = ctx->perm;
- int16_t *permGradIndex3D = ctx->permGradIndex3D;
+ const int16_t *perm = ctx->perm;
+ const int16_t *permGradIndex3D = ctx->permGradIndex3D;
int index = permGradIndex3D[(perm[(perm[xsb & 0xFF] + ysb) & 0xFF] + zsb) & 0xFF];
return gradients3D[index] * dx
+ gradients3D[index + 1] * dy
+ gradients3D[index + 2] * dz;
}
-static double extrapolate4(struct osn_context *ctx, int xsb, int ysb, int zsb, int wsb, double dx, double dy, double dz, double dw)
+static double extrapolate4(const struct osn_context *ctx, int xsb, int ysb, int zsb, int wsb, double dx, double dy, double dz, double dw)
{
- int16_t *perm = ctx->perm;
+ const int16_t *perm = ctx->perm;
int index = perm[(perm[(perm[(perm[xsb & 0xFF] + ysb) & 0xFF] + zsb) & 0xFF] + wsb) & 0xFF] & 0xFC;
return gradients4D[index] * dx
+ gradients4D[index + 1] * dy
@@ -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];
@@ -226,7 +227,7 @@ void open_simplex_noise_free(struct osn_context *ctx)
// -- GODOT end --
/* 2D OpenSimplex (Simplectic) Noise. */
-double open_simplex_noise2(struct osn_context *ctx, double x, double y)
+double open_simplex_noise2(const struct osn_context *ctx, double x, double y)
{
/* Place input coordinates onto grid. */
@@ -354,7 +355,7 @@ double open_simplex_noise2(struct osn_context *ctx, double x, double y)
/*
* 3D OpenSimplex (Simplectic) Noise
*/
-double open_simplex_noise3(struct osn_context *ctx, double x, double y, double z)
+double open_simplex_noise3(const struct osn_context *ctx, double x, double y, double z)
{
/* Place input coordinates on simplectic honeycomb. */
@@ -927,7 +928,7 @@ double open_simplex_noise3(struct osn_context *ctx, double x, double y, double z
/*
* 4D OpenSimplex (Simplectic) Noise.
*/
-double open_simplex_noise4(struct osn_context *ctx, double x, double y, double z, double w)
+double open_simplex_noise4(const struct osn_context *ctx, double x, double y, double z, double w)
{
double uins;
double dx1, dy1, dz1, dw1;
diff --git a/thirdparty/misc/open-simplex-noise.h b/thirdparty/misc/open-simplex-noise.h
index 89e0df8218..fd9248c3a1 100644
--- a/thirdparty/misc/open-simplex-noise.h
+++ b/thirdparty/misc/open-simplex-noise.h
@@ -47,9 +47,9 @@ int open_simplex_noise(int64_t seed, struct osn_context *ctx);
//int open_simplex_noise_init_perm(struct osn_context *ctx, int16_t p[], int nelements);
// -- GODOT end --
void open_simplex_noise_free(struct osn_context *ctx);
-double open_simplex_noise2(struct osn_context *ctx, double x, double y);
-double open_simplex_noise3(struct osn_context *ctx, double x, double y, double z);
-double open_simplex_noise4(struct osn_context *ctx, double x, double y, double z, double w);
+double open_simplex_noise2(const struct osn_context *ctx, double x, double y);
+double open_simplex_noise3(const struct osn_context *ctx, double x, double y, double z);
+double open_simplex_noise4(const struct osn_context *ctx, double x, double y, double z, double w);
#ifdef __cplusplus
}
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/r128.h b/thirdparty/misc/r128.h
index 1f7aab78fb..a345cc47ba 100644
--- a/thirdparty/misc/r128.h
+++ b/thirdparty/misc/r128.h
@@ -1,5 +1,5 @@
/*
-r128.h: 128-bit (64.64) signed fixed-point arithmetic. Version 1.4.3
+r128.h: 128-bit (64.64) signed fixed-point arithmetic. Version 1.4.4
COMPILATION
-----------
@@ -76,8 +76,8 @@ OTHER DEALINGS IN THE SOFTWARE.
# include <stdint.h>
# define R128_S32 int32_t
# define R128_U32 uint32_t
-# define R128_S64 int64_t
-# define R128_U64 uint64_t
+# define R128_S64 long long
+# define R128_U64 unsigned long long
# define R128_LIT_S64(x) x##ll
# define R128_LIT_U64(x) x##ull
#endif
@@ -701,7 +701,7 @@ static R128_U32 r128__udiv64(R128_U32 nlo, R128_U32 nhi, R128_U32 d, R128_U32 *r
return (R128_U32)(n64 / d);
# endif
}
-#elif !defined(_M_X64) || defined(R128_STDC_ONLY)
+#elif defined(R128_STDC_ONLY) || !R128_INTEL
#define r128__umul64(a, b) ((a) * (R128_U64)(b))
static R128_U32 r128__udiv64(R128_U32 nlo, R128_U32 nhi, R128_U32 d, R128_U32 *rem)
{
@@ -799,7 +799,7 @@ static void r128__umul128(R128 *dst, R128_U64 a, R128_U64 b)
// MSVC x64 provides neither inline assembly nor (pre-2019) a div intrinsic, so we do fake
// "inline assembly" to avoid long division or outline assembly.
#pragma code_seg(".text")
-__declspec(allocate(".text")) static const unsigned char r128__udiv128Code[] = {
+__declspec(allocate(".text") align(16)) static const unsigned char r128__udiv128Code[] = {
0x48, 0x8B, 0xC1, //mov rax, rcx
0x49, 0xF7, 0xF0, //div rax, r8
0x49, 0x89, 0x11, //mov qword ptr [r9], rdx
diff --git a/thirdparty/misc/triangulator.cpp b/thirdparty/misc/triangulator.cpp
index 75b2b064c4..d6b63c6638 100644
--- a/thirdparty/misc/triangulator.cpp
+++ b/thirdparty/misc/triangulator.cpp
@@ -665,7 +665,7 @@ int TriangulatorPartition::Triangulate_OPT(TriangulatorPoly *poly, List<Triangul
newdiagonal.index1 = 0;
newdiagonal.index2 = n-1;
diagonals.push_back(newdiagonal);
- while(!diagonals.empty()) {
+ while(!diagonals.is_empty()) {
diagonal = (diagonals.front()->get());
diagonals.pop_front();
bestvertex = dpstates[diagonal.index2][diagonal.index1].bestvertex;
@@ -712,8 +712,8 @@ void TriangulatorPartition::UpdateState(long a, long b, long w, long i, long j,
pairs->push_front(newdiagonal);
dpstates[a][b].weight = w;
} else {
- if((!pairs->empty())&&(i <= pairs->front()->get().index1)) return;
- while((!pairs->empty())&&(pairs->front()->get().index2 >= j)) pairs->pop_front();
+ if((!pairs->is_empty())&&(i <= pairs->front()->get().index1)) return;
+ while((!pairs->is_empty())&&(pairs->front()->get().index2 >= j)) pairs->pop_front();
pairs->push_front(newdiagonal);
}
}
@@ -771,7 +771,7 @@ void TriangulatorPartition::TypeB(long i, long j, long k, PartitionVertex *verti
pairs = &(dpstates[j][k].pairs);
iter = pairs->front();
- if((!pairs->empty())&&(!IsReflex(vertices[i].p,vertices[j].p,vertices[iter->get().index1].p))) {
+ if((!pairs->is_empty())&&(!IsReflex(vertices[i].p,vertices[j].p,vertices[iter->get().index1].p))) {
lastiter = iter;
while(iter!=NULL) {
if(!IsReflex(vertices[i].p,vertices[j].p,vertices[iter->get().index1].p)) {
@@ -906,12 +906,12 @@ int TriangulatorPartition::ConvexPartition_OPT(TriangulatorPoly *poly, List<Tria
newdiagonal.index1 = 0;
newdiagonal.index2 = n-1;
diagonals.push_front(newdiagonal);
- while(!diagonals.empty()) {
+ while(!diagonals.is_empty()) {
diagonal = (diagonals.front()->get());
diagonals.pop_front();
if((diagonal.index2 - diagonal.index1) <=1) continue;
pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs);
- if(pairs->empty()) {
+ if(pairs->is_empty()) {
ret = 0;
break;
}
@@ -926,7 +926,7 @@ int TriangulatorPartition::ConvexPartition_OPT(TriangulatorPoly *poly, List<Tria
if(iter->get().index1 != iter->get().index2) {
pairs2 = &(dpstates[diagonal.index1][j].pairs);
while(1) {
- if(pairs2->empty()) {
+ if(pairs2->is_empty()) {
ret = 0;
break;
}
@@ -951,7 +951,7 @@ int TriangulatorPartition::ConvexPartition_OPT(TriangulatorPoly *poly, List<Tria
if(iter->get().index1 != iter->get().index2) {
pairs2 = &(dpstates[j][diagonal.index2].pairs);
while(1) {
- if(pairs2->empty()) {
+ if(pairs2->is_empty()) {
ret = 0;
break;
}
@@ -981,7 +981,7 @@ int TriangulatorPartition::ConvexPartition_OPT(TriangulatorPoly *poly, List<Tria
newdiagonal.index1 = 0;
newdiagonal.index2 = n-1;
diagonals.push_front(newdiagonal);
- while(!diagonals.empty()) {
+ while(!diagonals.is_empty()) {
diagonal = (diagonals.front())->get();
diagonals.pop_front();
if((diagonal.index2 - diagonal.index1) <= 1) continue;
@@ -992,7 +992,7 @@ int TriangulatorPartition::ConvexPartition_OPT(TriangulatorPoly *poly, List<Tria
indices.push_back(diagonal.index2);
diagonals2.push_front(diagonal);
- while(!diagonals2.empty()) {
+ while(!diagonals2.is_empty()) {
diagonal = (diagonals2.front()->get());
diagonals2.pop_front();
if((diagonal.index2 - diagonal.index1) <= 1) continue;
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
generated by cgit v1.2.3 (git 2.25.1) at 2025-02-09 10:54:25 +0000