fix integer overflow in mapgen (#11641)

* fix integer overflow in mapgen

Some calculations involving the magic seed had overflow because the result of an intermediate arithmetic step could not fit in an s32. By making the magic seed unsigned, the other operand in the equation will be cast to unsigned, and possibly other operands or intermediate operands. This will result in unexpected behavior if an operand is negative, which is technically possible, but logically should not happen.

* comment noise2d bitshift

While working through the code I was momentarily concerned that the right bitshift in noise2d could fill ones in some cases. It turns out that with signed integers, this is indeed true, but this one is shifting an unsigned integer, so the behavior is as expected. I put a comment here to clarify this, in case someone else wonders the same thing down the line.

* noise2d and noise3d unittests

I have added 3 tests each for noise2d and noise3d, testing all zero inputs, a very large seed (case which caused UB in the old implementation) and some fun primes I picked for no particular reason. This should be sufficient to demonstrate that the behavior of the new implementation has not changed. I used uniform initialization because it is a good feature of C++11. Please do not explode.

* uncomment the noise2d bitshift

This reverts commit 583b77ee9f1ad6bb77340ebb5ba51eb9a88ff51c. It's a
well-defined language semantic; it doesn't need to be commented.

* code cleanliness

diff --git a/src/mapgen/mapgen.cpp b/src/mapgen/mapgen.cpp
index d767bd264dd350b8741842581ed4719ada575e64..1f2ac491e952331e41aac3249760d5d18be5c3f7 100644 (file)
--- a/src/mapgen/mapgen.cpp
+++ b/src/mapgen/mapgen.cpp
@@ -238,7 +238,8 @@ u32 Mapgen::getBlockSeed(v3s16 p, s32 seed)
 
 u32 Mapgen::getBlockSeed2(v3s16 p, s32 seed)
 {
-       u32 n = 1619 * p.X + 31337 * p.Y + 52591 * p.Z + 1013 * seed;
+       // Multiply by unsigned number to avoid signed overflow (UB)
+       u32 n = 1619U * p.X + 31337U * p.Y + 52591U * p.Z + 1013U * seed;
        n = (n >> 13) ^ n;
        return (n * (n * n * 60493 + 19990303) + 1376312589);
 }

diff --git a/src/noise.cpp b/src/noise.cpp
index 2f4de6855ac0afb1331c9a818f3519fdc1b18cea..d98d4dafb01186efc558c8e517f42be8e8b35da2 100644 (file)
--- a/src/noise.cpp
+++ b/src/noise.cpp
@@ -35,7 +35,8 @@
 #define NOISE_MAGIC_X    1619
 #define NOISE_MAGIC_Y    31337
 #define NOISE_MAGIC_Z    52591
-#define NOISE_MAGIC_SEED 1013
+// Unsigned magic seed prevents undefined behavior.
+#define NOISE_MAGIC_SEED 1013U
 
 typedef float (*Interp2dFxn)(
                float v00, float v10, float v01, float v11,

diff --git a/src/unittest/test_noise.cpp b/src/unittest/test_noise.cpp
index 421f3b66e5c29442b1841c7ef049336f225dbb00..12b155f46c1f0ba714af2571a82d76ddc12628bc 100644 (file)
--- a/src/unittest/test_noise.cpp
+++ b/src/unittest/test_noise.cpp
@@ -30,8 +30,14 @@ class TestNoise : public TestBase {
 
        void runTests(IGameDef *gamedef);
 
+       void testNoise2dAtOriginWithZeroSeed();
+       void testNoise2dWithMaxSeed();
+       void testNoise2dWithFunPrimes();
        void testNoise2dPoint();
        void testNoise2dBulk();
+       void testNoise3dAtOriginWithZeroSeed();
+       void testNoise3dWithMaxSeed();
+       void testNoise3dWithFunPrimes();
        void testNoise3dPoint();
        void testNoise3dBulk();
        void testNoiseInvalidParams();
@@ -44,8 +50,14 @@ static TestNoise g_test_instance;
 
 void TestNoise::runTests(IGameDef *gamedef)
 {
+       TEST(testNoise2dAtOriginWithZeroSeed);
+       TEST(testNoise2dWithMaxSeed);
+       TEST(testNoise2dWithFunPrimes);
        TEST(testNoise2dPoint);
        TEST(testNoise2dBulk);
+       TEST(testNoise3dAtOriginWithZeroSeed);
+       TEST(testNoise3dWithMaxSeed);
+       TEST(testNoise3dWithFunPrimes);
        TEST(testNoise3dPoint);
        TEST(testNoise3dBulk);
        TEST(testNoiseInvalidParams);
@@ -53,6 +65,27 @@ void TestNoise::runTests(IGameDef *gamedef)
 
 ////////////////////////////////////////////////////////////////////////////////
 
+void TestNoise::testNoise2dAtOriginWithZeroSeed()
+{
+       float actual{ noise2d(0, 0, 0) };
+       constexpr float expected{ -0.281791f };
+       UASSERT(std::fabs(actual - expected) <= 0.00001);
+}
+
+void TestNoise::testNoise2dWithMaxSeed()
+{
+       float actual{ noise2d(4096, 4096, 2147483647) };
+       constexpr float expected{ 0.950606f };
+       UASSERT(std::fabs(actual - expected) <= 0.00001);
+}
+
+void TestNoise::testNoise2dWithFunPrimes()
+{
+       float actual{ noise2d(-3947, -2333, 7027) };
+       constexpr float expected{ -0.294907f };
+       UASSERT(std::fabs(actual - expected) <= 0.00001);
+}
+
 void TestNoise::testNoise2dPoint()
 {
        NoiseParams np_normal(20, 40, v3f(50, 50, 50), 9,  5, 0.6, 2.0);
@@ -79,6 +112,27 @@ void TestNoise::testNoise2dBulk()
        }
 }
 
+void TestNoise::testNoise3dAtOriginWithZeroSeed()
+{
+       float actual{ noise2d(0, 0, 0) };
+       constexpr float expected{ -0.281791f };
+       UASSERT(std::fabs(actual - expected) <= 0.00001);
+}
+
+void TestNoise::testNoise3dWithMaxSeed()
+{
+       float actual{ noise3d(4096, 4096, 4096, 2147483647) };
+       constexpr float expected{ -0.775243f };
+       UASSERT(std::fabs(actual - expected) <= 0.00001);
+}
+
+void TestNoise::testNoise3dWithFunPrimes()
+{
+       float actual{ noise2d(3903, -1723, 7411) };
+       constexpr float expected{ 0.989124f };
+       UASSERT(std::fabs(actual - expected) <= 0.00001);
+}
+
 void TestNoise::testNoise3dPoint()
 {
        NoiseParams np_normal(20, 40, v3f(50, 50, 50), 9,  5, 0.6, 2.0);