path: root/src/unittest/test_random.cpp

 /*
Minetest
Copyright (C) 2010-2014 kwolekr, Ryan Kwolek <kwolekr@minetest.net>

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/

#include "test.h"

#include <cmath>
#include "util/numeric.h"
#include "exceptions.h"
#include "noise.h"

class TestRandom : public TestBase {
public:
	TestRandom() { TestManager::registerTestModule(this); }
	const char *getName() { return "TestRandom"; }

	void runTests(IGameDef *gamedef);

	void testPseudoRandom();
	void testPseudoRandomRange();
	void testPcgRandom();
	void testPcgRandomRange();
	void testPcgRandomBytes();
	void testPcgRandomNormalDist();

	static const int expected_pseudorandom_results[256];
	static const u32 expected_pcgrandom_results[256];
	static const u8 expected_pcgrandom_bytes_result[24];
	static const u8 expected_pcgrandom_bytes_result2[24];
};

static TestRandom g_test_instance;

void TestRandom::runTests(IGameDef *gamedef)
{
	TEST(testPseudoRandom);
	TEST(testPseudoRandomRange);
	TEST(testPcgRandom);
	TEST(testPcgRandomRange);
	TEST(testPcgRandomBytes);
	TEST(testPcgRandomNormalDist);
}

////////////////////////////////////////////////////////////////////////////////

void TestRandom::testPseudoRandom()
{
	PseudoRandom pr(814538);

	for (u32 i = 0; i != 256; i++)
		UASSERTEQ(int, pr.next(), expected_pseudorandom_results[i]);
}


void TestRandom::testPseudoRandomRange()
{
	PseudoRandom pr((int)time(NULL));

	EXCEPTION_CHECK(PrngException, pr.range(2000, 6000));
	EXCEPTION_CHECK(PrngException, pr.range(5, 1));

	for (u32 i = 0; i != 32768; i++) {
		int min = (pr.next() % 3000) - 500;
		int max = (pr.next() % 3000) - 500;
		if (min > max)
			SWAP(int, min, max);

		int randval = pr.range(min, max);
		UASSERT(randval >= min);
		UASSERT(randval <= max);
	}
}


void TestRandom::testPcgRandom()
{
	PcgRandom pr(814538, 998877);

	for (u32 i = 0; i != 256; i++)
		UASSERTEQ(u32, pr.next(), expected_pcgrandom_results[i]);
}


void TestRandom::testPcgRandomRange()
{
	PcgRandom pr((int)time(NULL));

	EXCEPTION_CHECK(PrngException, pr.range(5, 1));

	// Regression test for bug 3027
	pr.range(pr.RANDOM_MIN, pr.RANDOM_MAX);

	for (u32 i = 0; i != 32768; i++) {
		int min = (pr.next() % 3000) - 500;
		int max = (pr.next() % 3000) - 500;
		if (min > max)
			SWAP(int, min, max);

		int randval = pr.range(min, max);
		UASSERT(randval >= min);
		UASSERT(randval <= max);
	}
}


void TestRandom::testPcgRandomBytes()
{
	char buf[32];
	PcgRandom r(1538, 877);

	memset(buf, 0, sizeof(buf));
	r.bytes(buf + 5, 23);
	UASSERT(memcmp(buf + 5, expected_pcgrandom_bytes_result,
		sizeof(expected_pcgrandom_bytes_result)) == 0);

	memset(buf, 0, sizeof(buf));
	r.bytes(buf, 17);
	UASSERT(memcmp(buf, expected_pcgrandom_bytes_result2,
		sizeof(expected_pcgrandom_bytes_result2)) == 0);
}


void TestRandom::testPcgRandomNormalDist()
{
	static const int max = 120;
	static const int min = -120;
	static const int num_trials = 20;
	static const u32 num_samples = 61000;
	s32 bins[max - min + 1];
	memset(bins, 0, sizeof(bins));

	PcgRandom r(486179 + (int)time(NULL));

	for (u32 i = 0; i != num_samples; i++) {
		s32 randval = r.randNormalDist(min, max, num_trials);
		UASSERT(randval <= max);
		UASSERT(randval >= min);
		bins[randval - min]++;
	}

	// Note that here we divide variance by the number of trials;
	// this is because variance is a biased estimator.
	int range      = (max - min + 1);
	float mean     = (max + min) / 2;
	float variance = ((range * range - 1) / 12) / num_trials;
	float stddev   = std::sqrt(variance);

	static const float prediction_intervals[] = {
		0.68269f, // 1.0
		0.86639f, // 1.5
		0.95450f, // 2.0
		0.98758f, // 2.5
		0.99730f, // 3.0
	};

	//// Simple normality test using the 68-95-99.7% rule
	for (u32 i = 0; i != ARRLEN(prediction_intervals); i++) {
		float deviations = i / 2.f + 1.f;
		int lbound = myround(mean - deviations * stddev);
		int ubound = myround(mean + deviations * stddev);
		UASSERT(lbound >= min);
		UASSERT(ubound <= max);

		int accum = 0;
		for (int j = lbound; j != ubound; j++)
			accum += bins[j - min];

		float actual = (float)accum / num_samples;
		UASSERT(std::fabs(actual - prediction_intervals[i]) < 0.02f);
	}
}


const int TestRandom::expected_pseudorandom_results[256] = {
	0x02fa, 0x60d5, 0x6c10, 0x606b, 0x098b, 0x5f1e, 0x4f56, 0x3fbd, 0x77af,
	0x4fe9, 0x419a, 0x6fe1, 0x177b, 0x6858, 0x36f8, 0x6d83, 0x14fc, 0x2d62,
	0x1077, 0x23e2, 0x041b, 0x7a7e, 0x5b52, 0x215d, 0x682b, 0x4716, 0x47e3,
	0x08c0, 0x1952, 0x56ae, 0x146d, 0x4b4f, 0x239f, 0x3fd0, 0x6794, 0x7796,
	0x7be2, 0x75b7, 0x5691, 0x28ee, 0x2656, 0x40c0, 0x133c, 0x63cd, 0x2aeb,
	0x518f, 0x7dbc, 0x6ad8, 0x736e, 0x5b05, 0x160b, 0x589f, 0x6f64, 0x5edc,
	0x092c, 0x0a39, 0x199e, 0x1927, 0x562b, 0x2689, 0x3ba3, 0x366f, 0x46da,
	0x4e49, 0x0abb, 0x40a1, 0x3846, 0x40db, 0x7adb, 0x6ec1, 0x6efa, 0x01cc,
	0x6335, 0x4352, 0x72fb, 0x4b2d, 0x509a, 0x257e, 0x2f7d, 0x5891, 0x2195,
	0x6107, 0x5269, 0x56e3, 0x4849, 0x38f7, 0x2791, 0x04f2, 0x4e05, 0x78ff,
	0x6bae, 0x50b3, 0x74ad, 0x31af, 0x531e, 0x7d56, 0x11c9, 0x0b5e, 0x405e,
	0x1e15, 0x7f6a, 0x5bd3, 0x6649, 0x71b4, 0x3ec2, 0x6ab4, 0x520e, 0x6ad6,
	0x287e, 0x10b8, 0x18f2, 0x7107, 0x46ea, 0x1d85, 0x25cc, 0x2689, 0x35c1,
	0x3065, 0x6237, 0x3edd, 0x23d9, 0x6fb5, 0x37a1, 0x3211, 0x526a, 0x4b09,
	0x23f1, 0x58cc, 0x2e42, 0x341f, 0x5e16, 0x3d1a, 0x5e8c, 0x7a82, 0x4635,
	0x2bf8, 0x6577, 0x3603, 0x1daf, 0x539f, 0x2e91, 0x6bd8, 0x42d3, 0x7a93,
	0x26e3, 0x5a91, 0x6c67&& x >= 0 && x < MAP_BLOCKSIZE
			&& y >= 0 && y < MAP_BLOCKSIZE
			&& z >= 0 && z < MAP_BLOCKSIZE;
	}

	inline bool isValidPosition(v3s16 p)
	{
		return isValidPosition(p.X, p.Y, p.Z);
	}

	inline MapNode getNode(s16 x, s16 y, s16 z, bool *valid_position)
	{
		*valid_position = isValidPosition(x, y, z);

		if (!*valid_position)
			return {CONTENT_IGNORE};

		return data[z * zstride + y * ystride + x];
	}

	inline MapNode getNode(v3s16 p, bool *valid_position)
	{
		return getNode(p.X, p.Y, p.Z, valid_position);
	}

	inline MapNode getNodeNoEx(v3s16 p)
	{
		bool is_valid;
		return getNode(p.X, p.Y, p.Z, &is_valid);
	}

	inline void setNode(s16 x, s16 y, s16 z, MapNode & n)
	{
		if (!isValidPosition(x, y, z))
			throw InvalidPositionException();

		data[z * zstride + y * ystride + x] = n;
		raiseModified(MOD_STATE_WRITE_NEEDED, MOD_REASON_SET_NODE);
	}

	inline void setNode(v3s16 p, MapNode & n)
	{
		setNode(p.X, p.Y, p.Z, n);
	}

	////
	//// Non-checking variants of the above
	////

	inline MapNode getNodeNoCheck(s16 x, s16 y, s16 z, bool *valid_position)
	{
		*valid_position = data != nullptr;
		if (!*valid_position)
			return {CONTENT_IGNORE};

		return data[z * zstride + y * ystride + x];
	}

	inline MapNode getNodeNoCheck(v3s16 p, bool *valid_position)
	{
		return getNodeNoCheck(p.X, p.Y, p.Z, valid_position);
	}

	////
	//// Non-checking, unsafe variants of the above
	//// MapBlock must be loaded by another function in the same scope/function
	//// Caller must ensure that this is not a dummy block (by calling isDummy())
	////

	inline const MapNode &getNodeUnsafe(s16 x, s16 y, s16 z)
	{
		return data[z * zstride + y * ystride + x];
	}

	inline const MapNode &getNodeUnsafe(v3s16 &p)
	{
		return getNodeUnsafe(p.X, p.Y, p.Z);
	}

	inline void setNodeNoCheck(s16 x, s16 y, s16 z, MapNode & n)
	{
		if (!data)
			throw InvalidPositionException();

		data[z * zstride + y * ystride + x] = n;
		raiseModified(MOD_STATE_WRITE_NEEDED, MOD_REASON_SET_NODE_NO_CHECK);
	}

	inline void setNodeNoCheck(v3s16 p, MapNode & n)
	{
		setNodeNoCheck(p.X, p.Y, p.Z, n);
	}

	// These functions consult the parent container if the position
	// is not valid on this MapBlock.">, 0xbbfde2bf, 0x91188009,
	0x966b394d, 0xbb9d2012, 0x7e6926cb, 0x95183860, 0x5ff4c59b, 0x035f628a,
	0xb67085ef, 0x33867e23, 0x68d1b887, 0x2e3298d7, 0x84fd0650, 0x8bc91141,
	0x6fcb0452, 0x2836fee9, 0x2e83c0a3, 0xf1bafdc5, 0x9ff77777, 0xfdfbba87,
	0x527aebeb, 0x423e5248, 0xd1756490, 0xe41148fa, 0x3361f7b4, 0xa2824f23,
	0xf4e08072, 0xc50442be, 0x35adcc21, 0x36be153c, 0xc7709012, 0xf0eeb9f2,
	0x3d73114e, 0x1c1574ee, 0x92095b9c, 0x1503d01c, 0xd6ce0677, 0x026a8ec1,
	0x76d0084d, 0x86c23633, 0x36f75ce6, 0x08fa7bbe, 0x35f6ff2a, 0x31cc9525,
	0x2c1a35e6, 0x8effcd62, 0xc782fa07, 0x8a86e248, 0x8fdb7a9b, 0x77246626,
	0x5767723f, 0x3a78b699, 0xe548ce1c, 0x5820f37d, 0x148ed9b8, 0xf6796254,
	0x32232c20, 0x392bf3a2, 0xe9af6625, 0xd40b0d88, 0x636cfa23, 0x6a5de514,
	0xc4a69183, 0xc785c853, 0xab0de901, 0x16ae7e44, 0x376f13b5, 0x070f7f31,
	0x34cbc93b, 0xe6184345, 0x1b7f911f, 0x631fbe4b, 0x86d6e023, 0xc689b518,
	0x88ef4f7c, 0xddf06b45, 0xc97f18d4, 0x2aaee94b, 0x45694723, 0x6db111d2,
	0x91974fce, 0xe33e29e2, 0xc5e99494, 0x8017e02b, 0x3ebd8143, 0x471ffb80,
	0xc0d7ca1b, 0x4954c860, 0x48935d6a, 0xf2d27999, 0xb93d608d, 0x40696e90,
	0x60b18162, 0x1a156998, 0x09b8bbab, 0xc80a79b6, 0x8adbcfbc, 0xc375248c,
	0xa584e2ea, 0x5b46fe11, 0x58e84680, 0x8a8bc456, 0xd668b94f, 0x8b9035be,
	0x278509d4, 0x6663a140, 0x81a9817a, 0xd4f9d3cf, 0x6dc5f607, 0x6ae04450,
	0x694f22a4, 0x1d061788, 0x2e39ad8b, 0x748f4db2, 0xee569b52, 0xd157166d,
	0xdabc161e, 0xc8d50176, 0x7e3110e5, 0x9f7d033b, 0x128df67f, 0xb0078583,
	0xa3a75d26, 0xc1ad8011, 0x07dd89ec, 0xef04f456, 0x91bf866c, 0x6aac5306,
	0xdd5a1573, 0xf73ff97a, 0x4e1186ad, 0xb9680680, 0xc8894515, 0xdc95a08e,
	0xc894fd8e, 0xf84ade15, 0xd787f8c1, 0x40dcecca, 0x1b24743e, 0x1ce6ab23,
	0x72321653, 0xb80fbaf7, 0x1bcf099b, 0x1ff26805, 0x78f66c8e, 0xf93bf51a,
	0xfb0c06fe, 0xe50d48cf, 0x310947e0, 0x1b78804a, 0xe73e2c14, 0x8deb8381,
	0xe576122a, 0xe5a8df39, 0x42397c5e, 0xf5503f3c, 0xbe3dbf8d, 0x1b360e(std::istream &is, u8 version, bool disk);

	void serializeNetworkSpecific(std::ostream &os);
	void deSerializeNetworkSpecific(std::istream &is);
private:
	/*
		Private methods
	*/

	void deSerialize_pre22(std::istream &is, u8 version, bool disk);

	/*
		Used only internally, because changes can't be tracked
	*/

	inline MapNode &getNodeRef(s16 x, s16 y, s16 z)
	{
		if (!isValidPosition(x, y, z))
			throw InvalidPositionException();

		return data[z * zstride + y * ystride + x];
	}

	inline MapNode &getNodeRef(v3s16 &p)
	{
		return getNodeRef(p.X, p.Y, p.Z);
	}

public:
	/*
		Public member variables
	*/

#ifndef SERVER // Only on client
	MapBlockMesh *mesh = nullptr;
#endif

	NodeMetadataList m_node_metadata;
	NodeTimerList m_node_timers;
	StaticObjectList m_static_objects;

	static const u32 ystride = MAP_BLOCKSIZE;
	static const u32 zstride = MAP_BLOCKSIZE * MAP_BLOCKSIZE;

	static const u32 nodecount = MAP_BLOCKSIZE * MAP_BLOCKSIZE * MAP_BLOCKSIZE;

	//// ABM optimizations ////
	// Cache of content types
	std::unordered_set<content_t> contents;
	// True if content types are cached
	bool contents_cached = false;
	// True if we never want to cache content types for this block
	bool do_not_cache_contents = false;

private:
	/*
		Private member variables
	*/

	// NOTE: Lots of things rely on this being the Map
	Map *m_parent;
	// Position in blocks on parent
	v3s16 m_pos;

	/* This is the precalculated m_pos_relative value
	* This caches the value, improving performance by removing 3 s16 multiplications
	* at runtime on each getPosRelative call
	* For a 5 minutes runtime with valgrind this removes 3 * 19M s16 multiplications
	* The gain can be estimated in Release Build to 3 * 100M multiply operations for 5 mins
	*/
	v3s16 m_pos_relative;

	IGameDef *m_gamedef;

	/*
		If NULL, block is a dummy block.
		Dummy blocks are used for caching not-found-on-disk blocks.
	*/
	MapNode *data = nullptr;

	/*
		- On the server, this is used for telling whether the
		  block has been modified from the one on disk.
		- On the client, this is used for nothing.
	*/
	u32 m_modified = MOD_STATE_WRITE_NEEDED;
	u32 m_modified_reason = MOD_REASON_INITIAL;

	/*
		When propagating sunlight and the above block doesn't exist,
		sunlight is assumed if this is false.

		In practice this is set to true if the block is completely
		undeground with nothing visible above the ground except
		caves.
	*/
	bool is_underground = false