From 8e5bd82c4d19c405fbb4f2592bf91ad8b110294b Mon Sep 17 00:00:00 2001
From: JosiahWI <41302989+JosiahWI@users.noreply.github.com>
Date: Fri, 3 Jun 2022 19:51:58 -0500
Subject: [PATCH] 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
---
 src/mapgen/mapgen.cpp       |  3 ++-
 src/noise.cpp               |  3 ++-
 src/unittest/test_noise.cpp | 54 +++++++++++++++++++++++++++++++++++++
 3 files changed, 58 insertions(+), 2 deletions(-)

diff --git a/src/mapgen/mapgen.cpp b/src/mapgen/mapgen.cpp
index d767bd264..1f2ac491e 100644
--- 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 2f4de6855..d98d4dafb 100644
--- 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 421f3b66e..12b155f46 100644
--- 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);
-- 
2.44.0