code:
/*
Minetest
Copyright (C) 2013 celeron55, Perttu Ahola <celeron55@gmail.com>

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 "util/numeric.h"
#include "util/string.h"

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

	void runTests(IGameDef *gamedef);

	void testAngleWrapAround();
	void testLowercase();
	void testTrim();
	void testIsYes();
	void testRemoveStringEnd();
	void testUrlEncode();
	void testUrlDecode();
	void testPadString();
	void testStartsWith();
	void testStrEqual();
	void testStringTrim();
	void testStrToIntConversion();
	void testStringReplace();
	void testStringAllowed();
	void testAsciiPrintableHelper();
	void testUTF8();
	void testRemoveEscapes();
	void testWrapRows();
	void testIsNumber();
	void testIsPowerOfTwo();
	void testMyround();
};

static TestUtilities g_test_instance;

void TestUtilities::runTests(IGameDef *gamedef)
{
	TEST(testAngleWrapAround);
	TEST(testLowercase);
	TEST(testTrim);
	TEST(testIsYes);
	TEST(testRemoveStringEnd);
	TEST(testUrlEncode);
	TEST(testUrlDecode);
	TEST(testPadString);
	TEST(testStartsWith);
	TEST(testStrEqual);
	TEST(testStringTrim);
	TEST(testStrToIntConversion);
	TEST(testStringReplace);
	TEST(testStringAllowed);
	TEST(testAsciiPrintableHelper);
	TEST(testUTF8);
	TEST(testRemoveEscapes);
	TEST(testWrapRows);
	TEST(testIsNumber);
	TEST(testIsPowerOfTwo);
	TEST(testMyround);
}

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

inline float ref_WrapDegrees180(float f)
{
	// This is a slower alternative to the wrapDegrees_180() function;
	// used as a reference for testing
	float value = fmodf(f + 180, 360);
	if (value < 0)
		value += 360;
	return value - 180;
}

inline float ref_WrapDegrees_0_360(float f)
{
	// This is a slower alternative to the wrapDegrees_0_360() function;
	// used as a reference for testing
	float value = fmodf(f, 360);
	if (value < 0)
		value += 360;
	return value < 0 ? value + 360 : value;
}

void TestUtilities::testAngleWrapAround()
{
	UASSERT(fabs(modulo360f(100.0) - 100.0) < 0.001);
	UASSERT(fabs(modulo360f(720.5) - 0.5) < 0.001);
	UASSERT(fabs(modulo360f(-0.5) - (-0.5)) < 0.001);
	UASSERT(fabs(modulo360f(-365.5) - (-5.5)) < 0.001);

	for (float f = -720; f <= -360; f += 0.25) {
		UASSERT(fabs(modulo360f(f) - modulo360f(f + 360)) < 0.001);
	}

	for (float f = -1440; f <= 1440; f += 0.25) {
		UASSERT(fabs(modulo360f(f) - fmodf(f, 360)) < 0.001);
		UASSERT(fabs(wrapDegrees_180(f) - ref_WrapDegrees180(f)) < 0.001);
		UASSERT(fabs(wrapDegrees_0_360(f) - ref_WrapDegrees_0_360(f)) < 0.001);
		UASSERT(wrapDegrees_0_360(fabs(wrapDegrees_180(f) - wrapDegrees_0_360(f))) < 0.001);
	}
}

void TestUtilities::testLowercase()
{
	UASSERT(lowercase("Foo bAR") == "foo bar");
}

void TestUtilities::testTrim()
{
	UASSERT(trim("") == "");
	UASSERT(trim("dirt_with_grass") == "dirt_with_grass");
	UASSERT(trim("\n \t\r  Foo bAR  \r\n\t\t  ") == "Foo bAR");
	UASSERT(trim("\n \t\r    \r\n\t\t  ") == "");
}

void TestUtilities::testIsYes()
{
	UASSERT(is_yes("YeS") == true);
	UASSERT(is_yes("") == false);
	UASSERT(is_yes("FAlse") == false);
	UASSERT(is_yes("-1") == true);
	UASSERT(is_yes("0") == false);
	UASSERT(is_yes("1") == true);
	UASSERT(is_yes("2") == true);
}

void TestUtilities::testRemoveStringEnd()
{
	const char *ends[] = {"abc", "c", "bc", "", NULL};
	UASSERT(removeStringEnd("abc", ends) == "");
	UASSERT(removeStringEnd("bc", ends) == "b");
	UASSERT(removeStringEnd("12c", ends) == "12");
	UASSERT(removeStringEnd("foo", ends) == "");
}

void TestUtilities::testUrlEncode()
{
	UASSERT(urlencode("\"Aardvarks lurk, OK?\"")
			== "%22Aardvarks%20lurk%2C%20OK%3F%22");
}

void TestUtilities::testUrlDecode()
{
	UASSERT(urldecode("%22Aardvarks%20lurk%2C%20OK%3F%22")
			== "\"Aardvarks lurk, OK?\"");
}

void TestUtilities::testPadString()
{
	UASSERT(padStringRight("hello", 8) == "hello   ");
}

void TestUtilities::testStartsWith()
{
	UASSERT(str_starts_with(std::string(), std::string()) == true);
	UASSERT(str_starts_with(std::string("the sharp pickaxe"),
		std::string()) == true);
	UASSERT(str_starts_with(std::string("the sharp pickaxe"),
		std::string("the")) == true);
	UASSERT(str_starts_with(std::string("the sharp pickaxe"),
		std::string("The")) == false);
	UASSERT(str_starts_with(std::string("the sharp pickaxe"),
		std::string("The"), true) == true);
	UASSERT(str_starts_with(std::string("T"), std::string("The")) == false);
}

void TestUtilities::testStrEqual()
{
	UASSERT(str_equal(narrow_to_wide("abc"), narrow_to_wide("abc")));
	UASSERT(str_equal(narrow_to_wide("ABC"), narrow_to_wide("abc"), true));
}

void TestUtilities::testStringTrim()
{
	UASSERT(trim("  a") == "a");
	UASSERT(trim("   a  ") == "a");
	UASSERT(trim("a   ") == "a");
	UASSERT(trim("") == "");
}

void TestUtilities::testStrToIntConversion()
{
	UASSERT(mystoi("123", 0, 1000) == 123);
	UASSERT(mystoi("123", 0, 10) == 10);
}

void TestUtilities::testStringReplace()
{
	std::string test_str;
	test_str = "Hello there";
	str_replace(test_str, "there", "world");
	UASSERT(test_str == "Hello world");
	test_str = "ThisAisAaAtest";
	str_replace(test_str, 'A', ' ');
	UASSERT(test_str == "This is a test");
}

void TestUtilities::testStringAllowed()
{
	UASSERT(string_allowed("hello", "abcdefghijklmno") == true);
	UASSERT(string_allowed("123", "abcdefghijklmno") == false);
	UASSERT(string_allowed_blacklist("hello", "123") == true);
	UASSERT(string_allowed_blacklist("hello123", "123") == false);
}

void TestUtilities::testAsciiPrintableHelper()
{
	UASSERT(IS_ASCII_PRINTABLE_CHAR('e') == true);
	UASSERT(IS_ASCII_PRINTABLE_CHAR('\0') == false);

	// Ensures that there is no cutting off going on...
	// If there were, 331 would be cut to 75 in this example
	// and 73 is a valid ASCII char.
	int ch = 331;
	UASSERT(IS_ASCII_PRINTABLE_CHAR(ch) == false);
}

void TestUtilities::testUTF8()
{
	UASSERT(wide_to_utf8(utf8_to_wide("")) == "");
	UASSERT(wide_to_utf8(utf8_to_wide("the shovel dug a crumbly node!"))
		== "the shovel dug a crumbly node!");
}

void TestUtilities::testRemoveEscapes()
{
	UASSERT(unescape_enriched<wchar_t>(
		L"abc\x1bXdef") == L"abcdef");
	UASSERT(unescape_enriched<wchar_t>(
		L"abc\x1b(escaped)def") == L"abcdef");
	UASSERT(unescape_enriched<wchar_t>(
		L"abc\x1b((escaped with parenthesis\\))def") == L"abcdef");
	UASSERT(unescape_enriched<wchar_t>(
		L"abc\x1b(incomplete") == L"abc");
	UASSERT(unescape_enriched<wchar_t>(
		L"escape at the end\x1b") == L"escape at the end");
	// Nested escapes not supported
	UASSERT(unescape_enriched<wchar_t>(
		L"abc\x1b(outer \x1b(inner escape)escape)def") == L"abcescape)def");
}

void TestUtilities::testWrapRows()
{
	UASSERT(wrap_rows("12345678",4) == "1234\n5678");
	// test that wrap_rows doesn't wrap inside multibyte sequences
	{
		const unsigned char s[] = {
			0x2f, 0x68, 0x6f, 0x6d, 0x65, 0x2f, 0x72, 0x61, 0x70, 0x74, 0x6f,
			0x72, 0x2f, 0xd1, 0x82, 0xd0, 0xb5, 0xd1, 0x81, 0xd1, 0x82, 0x2f,
			0x6d, 0x69, 0x6e, 0x65, 0x74, 0x65, 0x73, 0x74, 0x2f, 0x62, 0x69,
			0x6e, 0x2f, 0x2e, 0x2e, 0};
		std::string str((char *)s);
		UASSERT(utf8_to_wide(wrap_rows(str, 20)) != L"<invalid UTF-8 string>");
	};
	{
		const unsigned char s[] = {
			0x74, 0x65, 0x73, 0x74, 0x20, 0xd1, 0x82, 0xd0, 0xb5, 0xd1, 0x81,
			0xd1, 0x82, 0x20, 0xd1, 0x82, 0xd0, 0xb5, 0xd1, 0x81, 0xd1, 0x82,
			0x20, 0xd1, 0x82, 0xd0, 0xb5, 0xd1, 0x81, 0xd1, 0x82, 0};
		std::string str((char *)s);
		UASSERT(utf8_to_wide(wrap_rows(str, 8)) != L"<invalid UTF-8 string>");
	}
}

void TestUtilities::testIsNumber()
{
	UASSERT(is_number("123") == true);
	UASSERT(is_number("") == false);
	UASSERT(is_number("123a") == false);
}

void TestUtilities::testIsPowerOfTwo()
{
	UASSERT(is_power_of_two(0) == false);
	UASSERT(is_power_of_two(1) == true);
	UASSERT(is_power_of_two(2) == true);
	UASSERT(is_power_of_two(3) == false);
	for (int exponent = 2; exponent <= 31; ++exponent) {
		UASSERT(is_power_of_two((1 << exponent) - 1) == false);
		UASSERT(is_power_of_two((1 << exponent)) == true);
		UASSERT(is_power_of_two((1 << exponent) + 1) == false);
	}
	UASSERT(is_power_of_two(U32_MAX) == false);
}

void TestUtilities::testMyround()
{
	UASSERT(myround(4.6f) == 5);
	UASSERT(myround(1.2f) == 1);
	UASSERT(myround(-3.1f) == -3);
	UASSERT(myround(-6.5f) == -7);
}


code:
/*
Minetest
Copyright (C) 2013 celeron55, Perttu Ahola <celeron55@gmail.com>

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 "gamedef.h"
#include "voxelalgorithms.h"
#include "util/numeric.h"

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

	void runTests(IGameDef *gamedef);

	void testPropogateSunlight(INodeDefManager *ndef);
	void testClearLightAndCollectSources(INodeDefManager *ndef);
	void testVoxelLineIterator(INodeDefManager *ndef);
};

static TestVoxelAlgorithms g_test_instance;

void TestVoxelAlgorithms::runTests(IGameDef *gamedef)
{
	INodeDefManager *ndef = gamedef->getNodeDefManager();

	TEST(testPropogateSunlight, ndef);
	TEST(testClearLightAndCollectSources, ndef);
	TEST(testVoxelLineIterator, ndef);
}

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

void TestVoxelAlgorithms::testPropogateSunlight(INodeDefManager *ndef)
{
	VoxelManipulator v;

	for (u16 z = 0; z < 3; z++)
	for (u16 y = 0; y < 3; y++)
	for (u16 x = 0; x < 3; x++) {
		v3s16 p(x,y,z);
		v.setNodeNoRef(p, MapNode(CONTENT_AIR));
	}

	VoxelArea a(v3s16(0,0,0), v3s16(2,2,2));

	{
		std::set<v3s16> light_sources;
		voxalgo::setLight(v, a, 0, ndef);
		voxalgo::SunlightPropagateResult res = voxalgo::propagateSunlight(
				v, a, true, light_sources, ndef);
		//v.print(dstream, ndef, VOXELPRINT_LIGHT_DAY);
		UASSERT(res.bottom_sunlight_valid == true);
		UASSERT(v.getNode(v3s16(1,1,1)).getLight(LIGHTBANK_DAY, ndef)
				== LIGHT_SUN);
	}

	v.setNodeNoRef(v3s16(0,0,0), MapNode(t_CONTENT_STONE));

	{
		std::set<v3s16> light_sources;
		voxalgo::setLight(v, a, 0, ndef);
		voxalgo::SunlightPropagateResult res = voxalgo::propagateSunlight(
				v, a, true, light_sources, ndef);
		UASSERT(res.bottom_sunlight_valid == true);
		UASSERT(v.getNode(v3s16(1,1,1)).getLight(LIGHTBANK_DAY, ndef)
				== LIGHT_SUN);
	}

	{
		std::set<v3s16> light_sources;
		voxalgo::setLight(v, a, 0, ndef);
		voxalgo::SunlightPropagateResult res = voxalgo::propagateSunlight(
				v, a, false, light_sources, ndef);
		UASSERT(res.bottom_sunlight_valid == true);
		UASSERT(v.getNode(v3s16(2,0,2)).getLight(LIGHTBANK_DAY, ndef)
				== 0);
	}

	v.setNodeNoRef(v3s16(1,3,2), MapNode(t_CONTENT_STONE));

	{
		std::set<v3s16> light_sources;
		voxalgo::setLight(v, a, 0, ndef);
		voxalgo::SunlightPropagateResult res = voxalgo::propagateSunlight(
				v, a, true, light_sources, ndef);
		UASSERT(res.bottom_sunlight_valid == true);
		UASSERT(v.getNode(v3s16(1,1,2)).getLight(LIGHTBANK_DAY, ndef)
				== 0);
	}

	{
		std::set<v3s16> light_sources;
		voxalgo::setLight(v, a, 0, ndef);
		voxalgo::SunlightPropagateResult res = voxalgo::propagateSunlight(
				v, a, false, light_sources, ndef);
		UASSERT(res.bottom_sunlight_valid == true);
		UASSERT(v.getNode(v3s16(1,0,2)).getLight(LIGHTBANK_DAY, ndef)
				== 0);
	}

	{
		MapNode n(CONTENT_AIR);
		n.setLight(LIGHTBANK_DAY, 10, ndef);
		v.setNodeNoRef(v3s16(1,-1,2), n);
	}

	{
		std::set<v3s16> light_sources;
		voxalgo::setLight(v, a, 0, ndef);
		voxalgo::SunlightPropagateResult res = voxalgo::propagateSunlight(
				v, a, true, light_sources, ndef);
		UASSERT(res.bottom_sunlight_valid == true);
	}

	{
		std::set<v3s16> light_sources;
		voxalgo::setLight(v, a, 0, ndef);
		voxalgo::SunlightPropagateResult res = voxalgo::propagateSunlight(
				v, a, false, light_sources, ndef);
		UASSERT(res.bottom_sunlight_valid == true);
	}

	{
		MapNode n(CONTENT_AIR);
		n.setLight(LIGHTBANK_DAY, LIGHT_SUN, ndef);
		v.setNodeNoRef(v3s16(1,-1,2), n);
	}

	{
		std::set<v3s16> light_sources;
		voxalgo::setLight(v, a, 0, ndef);
		voxalgo::SunlightPropagateResult res = voxalgo::propagateSunlight(
				v, a, true, light_sources, ndef);
		UASSERT(res.bottom_sunlight_valid == false);
	}

	{
		std::set<v3s16> light_sources;
		voxalgo::setLight(v, a, 0, ndef);
		voxalgo::SunlightPropagateResult res = voxalgo::propagateSunlight(
				v, a, false, light_sources, ndef);
		UASSERT(res.bottom_sunlight_valid == false);
	}

	v.setNodeNoRef(v3s16(1,3,2), MapNode(CONTENT_IGNORE));

	{
		std::set<v3s16> light_sources;
		voxalgo::setLight(v, a, 0, ndef);
		voxalgo::SunlightPropagateResult res = voxalgo::propagateSunlight(
				v, a, true, light_sources, ndef);
		UASSERT(res.bottom_sunlight_valid == true);
	}
}

void TestVoxelAlgorithms::testClearLightAndCollectSources(INodeDefManager *ndef)
{
	VoxelManipulator v;

	for (u16 z = 0; z < 3; z++)
	for (u16 y = 0; y < 3; y++)
	for (u16 x = 0; x < 3; x++) {
		v3s16 p(x,y,z);
		v.setNode(p, MapNode(CONTENT_AIR));
	}

	VoxelArea a(v3s16(0,0,0), v3s16(2,2,2));
	v.setNodeNoRef(v3s16(0,0,0), MapNode(t_CONTENT_STONE));
	v.setNodeNoRef(v3s16(1,1,1), MapNode(t_CONTENT_TORCH));

	{
		MapNode n(CONTENT_AIR);
		n.setLight(LIGHTBANK_DAY, 1, ndef);
		v.setNode(v3s16(1,1,2), n);
	}

	{
		std::set<v3s16> light_sources;
		std::map<v3s16, u8> unlight_from;
		voxalgo::clearLightAndCollectSources(v, a, LIGHTBANK_DAY,
				ndef, light_sources, unlight_from);
		//v.print(dstream, ndef, VOXELPRINT_LIGHT_DAY);
		UASSERT(v.getNode(v3s16(0,1,1)).getLight(LIGHTBANK_DAY, ndef) == 0);
		UASSERT(light_sources.find(v3s16(1,1,1)) != light_sources.end());
		UASSERT(light_sources.size() == 1);
		UASSERT(unlight_from.find(v3s16(1,1,2)) != unlight_from.end());
		UASSERT(unlight_from.size() == 1);
	}
}

void TestVoxelAlgorithms::testVoxelLineIterator(INodeDefManager *ndef)
{
	// Test some lines
	// Do not test lines that start or end on the border of
	// two voxels as rounding errors can make the test fail!
	std::vector<core::line3d<f32> > lines;
	for (f32 x = -9.1; x < 9; x += 3.124) {
	for (f32 y = -9.2; y < 9; y += 3.123) {
	for (f32 z = -9.3; z < 9; z += 3.122) {
		lines.push_back(core::line3d<f32>(-x, -y, -z, x, y, z));
	}
	}
	}
	lines.push_back(core::line3d<f32>(0, 0, 0, 0, 0, 0));
	// Test every line
	std::vector<core::line3d<f32> >::iterator it = lines.begin();
	for (; it < lines.end(); it++) {
		core::line3d<f32> l = *it;

		// Initialize test
		voxalgo::VoxelLineIterator iterator(l.start, l.getVector());

		//Test the first voxel
		v3s16 start_voxel = floatToInt(l.start, 1);
		UASSERT(iterator.m_current_node_pos == start_voxel);

		// Values for testing
		v3s16 end_voxel = floatToInt(l.end, 1);
		v3s16 voxel_vector = end_voxel - start_voxel;
		int nodecount = abs(voxel_vector.X) + abs(voxel_vector.Y)
			+ abs(voxel_vector.Z);
		int actual_nodecount = 0;
		v3s16 old_voxel = iterator.m_current_node_pos;

		while (iterator.hasNext()) {
			iterator.next();
			actual_nodecount++;
			v3s16 new_voxel = iterator.m_current_node_pos;
			// This must be a neighbor of the old voxel
			UASSERTEQ(f32, (new_voxel - old_voxel).getLengthSQ(), 1);
			// The line must intersect with the voxel
			v3f voxel_center = intToFloat(iterator.m_current_node_pos, 1);
			aabb3f box(voxel_center - v3f(0.5, 0.5, 0.5),
				voxel_center + v3f(0.5, 0.5, 0.5));
			UASSERT(box.intersectsWithLine(l));
			// Update old voxel
			old_voxel = new_voxel;
		}

		// Test last node
		UASSERT(iterator.m_current_node_pos == end_voxel);
		// Test node count
		UASSERTEQ(int, actual_nodecount, nodecount);
	}
}

repo_name: pgimeno/minetest

license: unknown


code:
/*
Minetest
Copyright (C) 2013 celeron55, Perttu Ahola <celeron55@gmail.com>

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 <algorithm>

#include "gamedef.h"
#include "log.h"
#include "voxel.h"

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

	void runTests(IGameDef *gamedef);

	void testVoxelArea();
	void testVoxelManipulator(INodeDefManager *nodedef);
};

static TestVoxelManipulator g_test_instance;

void TestVoxelManipulator::runTests(IGameDef *gamedef)
{
	TEST(testVoxelArea);
	TEST(testVoxelManipulator, gamedef->getNodeDefManager());
}

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

void TestVoxelManipulator::testVoxelArea()
{
	VoxelArea a(v3s16(-1,-1,-1), v3s16(1,1,1));
	UASSERT(a.index(0,0,0) == 1*3*3 + 1*3 + 1);
	UASSERT(a.index(-1,-1,-1) == 0);

	VoxelArea c(v3s16(-2,-2,-2), v3s16(2,2,2));
	// An area that is 1 bigger in x+ and z-
	VoxelArea d(v3s16(-2,-2,-3), v3s16(3,2,2));

	std::list<VoxelArea> aa;
	d.diff(c, aa);

	// Correct results
	std::vector<VoxelArea> results;
	results.push_back(VoxelArea(v3s16(-2,-2,-3), v3s16(3,2,-3)));
	results.push_back(VoxelArea(v3s16(3,-2,-2), v3s16(3,2,2)));

	UASSERT(aa.size() == results.size());

	infostream<<"Result of diff:"<<std::endl;
	for (std::list<VoxelArea>::const_iterator
			it = aa.begin(); it != aa.end(); ++it) {
		it->print(infostream);
		infostream << std::endl;

		std::vector<VoxelArea>::iterator j;
		j = std::find(results.begin(), results.end(), *it);
		UASSERT(j != results.end());
		results.erase(j);
	}
}

void TestVoxelManipulator::testVoxelManipulator(INodeDefManager *nodedef)
{
	VoxelManipulator v;

	v.print(infostream, nodedef);

	infostream << "*** Setting (-1,0,-1)=2 ***" << std::endl;
	v.setNodeNoRef(v3s16(-1,0,-1), MapNode(t_CONTENT_GRASS));

	v.print(infostream, nodedef);
	UASSERT(v.getNode(v3s16(-1,0,-1)).getContent() == t_CONTENT_GRASS);

	infostream << "*** Reading from inexistent (0,0,-1) ***" << std::endl;

	EXCEPTION_CHECK(InvalidPositionException, v.getNode(v3s16(0,0,-1)));
	v.print(infostream, nodedef);

	infostream << "*** Adding area ***" << std::endl;

	VoxelArea a(v3s16(-1,-1,-1), v3s16(1,1,1));
	v.addArea(a);
	v.print(infostream, nodedef);

	UASSERT(v.getNode(v3s16(-1,0,-1)).getContent() == t_CONTENT_GRASS);
	EXCEPTION_CHECK(InvalidPositionException, v.getNode(v3s16(0,1,1)));
}


code:
set(UTIL_SRCS
	${CMAKE_CURRENT_SOURCE_DIR}/areastore.cpp
	${CMAKE_CURRENT_SOURCE_DIR}/auth.cpp
	${CMAKE_CURRENT_SOURCE_DIR}/base64.cpp
	${CMAKE_CURRENT_SOURCE_DIR}/directiontables.cpp
	${CMAKE_CURRENT_SOURCE_DIR}/enriched_string.cpp
	${CMAKE_CURRENT_SOURCE_DIR}/numeric.cpp
	${CMAKE_CURRENT_SOURCE_DIR}/pointedthing.cpp
	${CMAKE_CURRENT_SOURCE_DIR}/serialize.cpp
	${CMAKE_CURRENT_SOURCE_DIR}/sha1.cpp
	${CMAKE_CURRENT_SOURCE_DIR}/sha256.c
	${CMAKE_CURRENT_SOURCE_DIR}/string.cpp
	${CMAKE_CURRENT_SOURCE_DIR}/srp.cpp
	${CMAKE_CURRENT_SOURCE_DIR}/timetaker.cpp
	PARENT_SCOPE)


code:
/*
Minetest
Copyright (C) 2015 est31 <mtest31@outlook.com>

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 "util/areastore.h"
#include "util/serialize.h"
#include "util/container.h"

#if USE_SPATIAL
	#include <spatialindex/SpatialIndex.h>
	#include <spatialindex/RTree.h>
	#include <spatialindex/Point.h>
#endif

#define AST_SMALLER_EQ_AS(p, q) (((p).X <= (q).X) && ((p).Y <= (q).Y) && ((p).Z <= (q).Z))

#define AST_OVERLAPS_IN_DIMENSION(amine, amaxe, b, d) \
	(!(((amine).d > (b)->maxedge.d) || ((amaxe).d < (b)->minedge.d)))

#define AST_CONTAINS_PT(a, p) (AST_SMALLER_EQ_AS((a)->minedge, (p)) && \
	AST_SMALLER_EQ_AS((p), (a)->maxedge))

#define AST_CONTAINS_AREA(amine, amaxe, b)         \
	(AST_SMALLER_EQ_AS((amine), (b)->minedge) \
	&& AST_SMALLER_EQ_AS((b)->maxedge, (amaxe)))

#define AST_AREAS_OVERLAP(amine, amaxe, b)                \
	(AST_OVERLAPS_IN_DIMENSION((amine), (amaxe), (b), X) && \
	AST_OVERLAPS_IN_DIMENSION((amine), (amaxe), (b), Y) &&  \
	AST_OVERLAPS_IN_DIMENSION((amine), (amaxe), (b), Z))

AreaStore *AreaStore::getOptimalImplementation()
{
#if USE_SPATIAL
	return new SpatialAreaStore();
#else
	return new VectorAreaStore();
#endif
}

const Area *AreaStore::getArea(u32 id) const
{
	AreaMap::const_iterator it = areas_map.find(id);
	if (it == areas_map.end())
		return NULL;
	return &it->second;
}

void AreaStore::serialize(std::ostream &os) const
{
	writeU8(os, 0); // Serialisation version

	// TODO: Compression?
	writeU16(os, areas_map.size());
	for (AreaMap::const_iterator it = areas_map.begin();
			it != areas_map.end(); ++it) {
		const Area &a = it->second;
		writeV3S16(os, a.minedge);
		writeV3S16(os, a.maxedge);
		writeU16(os, a.data.size());
		os.write(a.data.data(), a.data.size());
	}
}

void AreaStore::deserialize(std::istream &is)
{
	u8 ver = readU8(is);
	if (ver != 0)
		throw SerializationError("Unknown AreaStore "
				"serialization version!");

	u16 num_areas = readU16(is);
	for (u32 i = 0; i < num_areas; ++i) {
		Area a;
		a.minedge = readV3S16(is);
		a.maxedge = readV3S16(is);
		u16 data_len = readU16(is);
		char *data = new char[data_len];
		is.read(data, data_len);
		a.data = std::string(data, data_len);
		insertArea(&a);
		delete [] data;
	}
}

void AreaStore::invalidateCache()
{
	if (m_cache_enabled) {
		m_res_cache.invalidate();
	}
}

void AreaStore::setCacheParams(bool enabled, u8 block_radius, size_t limit)
{
	m_cache_enabled = enabled;
	m_cacheblock_radius = MYMAX(block_radius, 16);
	m_res_cache.setLimit(MYMAX(limit, 20));
	invalidateCache();
}

void AreaStore::cacheMiss(void *data, const v3s16 &mpos, std::vector<Area *> *dest)
{
	AreaStore *as = (AreaStore *)data;
	u8 r = as->m_cacheblock_radius;

	// get the points at the edges of the mapblock
	v3s16 minedge(mpos.X * r, mpos.Y * r, mpos.Z * r);
	v3s16 maxedge(
		minedge.X + r - 1,
		minedge.Y + r - 1,
		minedge.Z + r - 1);

	as->getAreasInArea(dest, minedge, maxedge, true);

	/* infostream << "Cache miss with " << dest->size() << " areas, between ("
			<< minedge.X << ", " << minedge.Y << ", " << minedge.Z
			<< ") and ("
			<< maxedge.X << ", " << maxedge.Y << ", " << maxedge.Z
			<< ")" << std::endl; // */
}

void AreaStore::getAreasForPos(std::vector<Area *> *result, v3s16 pos)
{
	if (m_cache_enabled) {
		v3s16 mblock = getContainerPos(pos, m_cacheblock_radius);
		const std::vector<Area *> *pre_list = m_res_cache.lookupCache(mblock);

		size_t s_p_l = pre_list->size();
		for (size_t i = 0; i < s_p_l; i++) {
			Area *b = (*pre_list)[i];
			if (AST_CONTAINS_PT(b, pos)) {
				result->push_back(b);
			}
		}
	} else {
		return getAreasForPosImpl(result, pos);
	}
}

////
// VectorAreaStore
////

bool VectorAreaStore::insertArea(Area *a)
{
	if (a->id == U32_MAX)
		a->id = getNextId();
	std::pair<AreaMap::iterator, bool> res =
			areas_map.insert(std::make_pair(a->id, *a));
	if (!res.second)
		// ID is not unique
		return false;
	m_areas.push_back(&res.first->second);
	invalidateCache();
	return true;
}

bool VectorAreaStore::removeArea(u32 id)
{
	AreaMap::iterator it = areas_map.find(id);
	if (it == areas_map.end())
		return false;
	Area *a = &it->second;
	for (std::vector<Area *>::iterator v_it = m_areas.begin();
			v_it != m_areas.end(); ++v_it) {
		if (*v_it == a) {
			m_areas.erase(v_it);
			break;
		}
	}
	areas_map.erase(it);
	invalidateCache();
	return true;
}

void VectorAreaStore::getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos)
{
	for (size_t i = 0; i < m_areas.size(); ++i) {
		Area *b = m_areas[i];
		if (AST_CONTAINS_PT(b, pos)) {
			result->push_back(b);
		}
	}
}

void VectorAreaStore::getAreasInArea(std::vector<Area *> *result,
		v3s16 minedge, v3s16 maxedge, bool accept_overlap)
{
	for (size_t i = 0; i < m_areas.size(); ++i) {
		Area *b = m_areas[i];
		if (accept_overlap ? AST_AREAS_OVERLAP(minedge, maxedge, b) :
				AST_CONTAINS_AREA(minedge, maxedge, b)) {
			result->push_back(b);
		}
	}
}

#if USE_SPATIAL

static inline SpatialIndex::Region get_spatial_region(const v3s16 minedge,
		const v3s16 maxedge)
{
	const double p_low[] = {(double)minedge.X,
		(double)minedge.Y, (double)minedge.Z};
	const double p_high[] = {(double)maxedge.X, (double)maxedge.Y,
		(double)maxedge.Z};
	return SpatialIndex::Region(p_low, p_high, 3);
}

static inline SpatialIndex::Point get_spatial_point(const v3s16 pos)
{
	const double p[] = {(double)pos.X, (double)pos.Y, (double)pos.Z};
	return SpatialIndex::Point(p, 3);
}

bool SpatialAreaStore::insertArea(Area *a)
{
	if (a->id == U32_MAX)
		a->id = getNextId();
	if (!areas_map.insert(std::make_pair(a->id, *a)).second)
		// ID is not unique
		return false;
	m_tree->insertData(0, NULL, get_spatial_region(a->minedge, a->maxedge), a->id);
	invalidateCache();
	return true;
}

bool SpatialAreaStore::removeArea(u32 id)
{
	std::map<u32, Area>::iterator itr = areas_map.find(id);
	if (itr != areas_map.end()) {
		Area *a = &itr->second;
		bool result = m_tree->deleteData(get_spatial_region(a->minedge,
			a->maxedge), id);
		areas_map.erase(itr);
		invalidateCache();
		return result;
	} else {
		return false;
	}
}

void SpatialAreaStore::getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos)
{
	VectorResultVisitor visitor(result, this);
	m_tree->pointLocationQuery(get_spatial_point(pos), visitor);
}

void SpatialAreaStore::getAreasInArea(std::vector<Area *> *result,
		v3s16 minedge, v3s16 maxedge, bool accept_overlap)
{
	VectorResultVisitor visitor(result, this);
	if (accept_overlap) {
		m_tree->intersectsWithQuery(get_spatial_region(minedge, maxedge),
			visitor);
	} else {
		m_tree->containsWhatQuery(get_spatial_region(minedge, maxedge), visitor);
	}
}

SpatialAreaStore::~SpatialAreaStore()
{
	delete m_tree;
}

SpatialAreaStore::SpatialAreaStore()
{
	m_storagemanager =
		SpatialIndex::StorageManager::createNewMemoryStorageManager();
	SpatialIndex::id_type id;
	m_tree = SpatialIndex::RTree::createNewRTree(
		*m_storagemanager,
		.7, // Fill factor
		100, // Index capacity
		100, // Leaf capacity
		3, // dimension :)
		SpatialIndex::RTree::RV_RSTAR,
		id);
}

#endif


code:
/*
Minetest
Copyright (C) 2015 est31 <mtest31@outlook.com>

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.
*/

#ifndef AREA_STORE_H_
#define AREA_STORE_H_

#include "irr_v3d.h"
#include "noise.h" // for PcgRandom
#include <map>
#include <list>
#include <vector>
#include <istream>
#include "util/container.h"
#include "util/numeric.h"
#ifndef ANDROID
	#include "cmake_config.h"
#endif
#if USE_SPATIAL
	#include <spatialindex/SpatialIndex.h>
	#include "util/serialize.h"
#endif

struct Area {
	Area() : id(U32_MAX) {}
	Area(const v3s16 &mine, const v3s16 &maxe) :
		id(U32_MAX), minedge(mine), maxedge(maxe)
	{
		sortBoxVerticies(minedge, maxedge);
	}

	u32 id;
	v3s16 minedge, maxedge;
	std::string data;
};

class AreaStore {
public:
	AreaStore() :
		m_cache_enabled(true),
		m_cacheblock_radius(64),
		m_res_cache(1000, &cacheMiss, this),
		m_next_id(0)
	{}

	virtual ~AreaStore() {}

	static AreaStore *getOptimalImplementation();

	virtual void reserve(size_t count) {};
	size_t size() const { return areas_map.size(); }

	/// Add an area to the store.
	/// Updates the area's ID if it hasn't already been set.
	/// @return Whether the area insertion was successful.
	virtual bool insertArea(Area *a) = 0;

	/// Removes an area from the store by ID.
	/// @return Whether the area was in the store and removed.
	virtual bool removeArea(u32 id) = 0;

	/// Finds areas that the passed position is contained in.
	/// Stores output in passed vector.
	void getAreasForPos(std::vector<Area *> *result, v3s16 pos);

	/// Finds areas that are completely contained inside the area defined
	/// by the passed edges.  If @p accept_overlap is true this finds any
	/// areas that intersect with the passed area at any point.
	virtual void getAreasInArea(std::vector<Area *> *result,
		v3s16 minedge, v3s16 maxedge, bool accept_overlap) = 0;

	/// Sets cache parameters.
	void setCacheParams(bool enabled, u8 block_radius, size_t limit);

	/// Returns a pointer to the area coresponding to the passed ID,
	/// or NULL if it doesn't exist.
	const Area *getArea(u32 id) const;

	/// Serializes the store's areas to a binary ostream.
	void serialize(std::ostream &is) const;

	/// Deserializes the Areas from a binary istream.
	/// This does not currently clear the AreaStore before adding the
	/// areas, making it possible to deserialize multiple serialized
	/// AreaStores.
	void deserialize(std::istream &is);

protected:
	/// Invalidates the getAreasForPos cache.
	/// Call after adding or removing an area.
	void invalidateCache();

	/// Implementation of getAreasForPos.
	/// getAreasForPos calls this if the cache is disabled.
	virtual void getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos) = 0;

	/// Returns the next area ID and increments it.
	u32 getNextId() { return m_next_id++; }

	// Note: This can't be an unordered_map, since all
	// references would be invalidated on rehash.
	typedef std::map<u32, Area> AreaMap;
	AreaMap areas_map;

private:
	/// Called by the cache when a value isn't found in the cache.
	static void cacheMiss(void *data, const v3s16 &mpos, std::vector<Area *> *dest);

	bool m_cache_enabled;
	/// Range, in nodes, of the getAreasForPos cache.
	/// If you modify this, call invalidateCache()
	u8 m_cacheblock_radius;
	LRUCache<v3s16, std::vector<Area *> > m_res_cache;

	u32 m_next_id;
};

class VectorAreaStore : public AreaStore {
public:
	virtual void reserve(size_t count) { m_areas.reserve(count); }
	virtual bool insertArea(Area *a);
	virtual bool removeArea(u32 id);
	virtual void getAreasInArea(std::vector<Area *> *result,
		v3s16 minedge, v3s16 maxedge, bool accept_overlap);

protected:
	virtual void getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos);

private:
	std::vector<Area *> m_areas;
};

#if USE_SPATIAL

class SpatialAreaStore : public AreaStore {
public:
	SpatialAreaStore();
	virtual ~SpatialAreaStore();

	virtual bool insertArea(Area *a);
	virtual bool removeArea(u32 id);
	virtual void getAreasInArea(std::vector<Area *> *result,
		v3s16 minedge, v3s16 maxedge, bool accept_overlap);

protected:
	virtual void getAreasForPosImpl(std::vector<Area *> *result, v3s16 pos);

private:
	SpatialIndex::ISpatialIndex *m_tree;
	SpatialIndex::IStorageManager *m_storagemanager;

	class VectorResultVisitor : public SpatialIndex::IVisitor {
	public:
		VectorResultVisitor(std::vector<Area *> *result, SpatialAreaStore *store) :
			m_store(store),
			m_result(result)
		{}
		~VectorResultVisitor() {}

		virtual void visitNode(const SpatialIndex::INode &in) {}

		virtual void visitData(const SpatialIndex::IData &in)
		{
			u32 id = in.getIdentifier();

			std::map<u32, Area>::iterator itr = m_store->areas_map.find(id);
			assert(itr != m_store->areas_map.end());
			m_result->push_back(&itr->second);
		}

		virtual void visitData(std::vector<const SpatialIndex::IData *> &v)
		{
			for (size_t i = 0; i < v.size(); i++)
				visitData(*(v[i]));
		}

	private:
		SpatialAreaStore *m_store;
		std::vector<Area *> *m_result;
	};
};

#endif // USE_SPATIAL

#endif // AREA_STORE_H_


code:
/*
Minetest
Copyright (C) 2015, 2016 est31 <MTest31@outlook.com>

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 <algorithm>
#include <string>
#include "auth.h"
#include "base64.h"
#include "sha1.h"
#include "srp.h"
#include "string.h"
#include "debug.h"

// Get an sha-1 hash of the player's name combined with
// the password entered. That's what the server uses as
// their password. (Exception : if the password field is
// blank, we send a blank password - this is for backwards
// compatibility with password-less players).
std::string translate_password(const std::string &name,
	const std::string &password)
{
	if (password.length() == 0)
		return "";

	std::string slt = name + password;
	SHA1 sha1;
	sha1.addBytes(slt.c_str(), slt.length());
	unsigned char *digest = sha1.getDigest();
	std::string pwd = base64_encode(digest, 20);
	free(digest);
	return pwd;
}

// Call lower level SRP code to generate a verifier with the
// given pointers. Contains the preparations, call parameters
// and error checking common to all srp verifier generation code.
// See docs of srp_create_salted_verification_key for more info.
static inline void gen_srp_v(const std::string &name,
	const std::string &password, char **salt, size_t *salt_len,
	char **bytes_v, size_t *len_v)
{
	std::string n_name = lowercase(name);
	SRP_Result res = srp_create_salted_verification_key(SRP_SHA256, SRP_NG_2048,
		n_name.c_str(), (const unsigned char *)password.c_str(),
		password.size(), (unsigned char **)salt, salt_len,
		(unsigned char **)bytes_v, len_v, NULL, NULL);
	FATAL_ERROR_IF(res != SRP_OK, "Couldn't create salted SRP verifier");
}

/// Creates a verification key with given salt and password.
std::string generate_srp_verifier(const std::string &name,
	const std::string &password, const std::string &salt)
{
	size_t salt_len = salt.size();
	// The API promises us that the salt doesn't
	// get modified if &salt_ptr isn't NULL.
	char *salt_ptr = (char *)salt.c_str();

	char *bytes_v = NULL;
	size_t verifier_len = 0;
	gen_srp_v(name, password, &salt_ptr, &salt_len, &bytes_v, &verifier_len);
	std::string verifier = std::string(bytes_v, verifier_len);
	free(bytes_v);
	return verifier;
}

/// Creates a verification key and salt with given password.
void generate_srp_verifier_and_salt(const std::string &name,
	const std::string &password, std::string *verifier,
	std::string *salt)
{
	char *bytes_v = NULL;
	size_t verifier_len;
	char *salt_ptr = NULL;
	size_t salt_len;
	gen_srp_v(name, password, &salt_ptr, &salt_len, &bytes_v, &verifier_len);
	*verifier = std::string(bytes_v, verifier_len);
	*salt = std::string(salt_ptr, salt_len);
	free(bytes_v);
	free(salt_ptr);
}

/// Gets an SRP verifier, generating a salt,
/// and encodes it as DB-ready string.
std::string get_encoded_srp_verifier(const std::string &name,
	const std::string &password)
{
	std::string verifier;
	std::string salt;
	generate_srp_verifier_and_salt(name, password, &verifier, &salt);
	return encode_srp_verifier(verifier, salt);
}

/// Converts the passed SRP verifier into a DB-ready format.
std::string encode_srp_verifier(const std::string &verifier,
	const std::string &salt)
{
	std::ostringstream ret_str;
	ret_str << "#1#"
		<< base64_encode((unsigned char *)salt.c_str(), salt.size()) << "#"
		<< base64_encode((unsigned char *)verifier.c_str(), verifier.size());
	return ret_str.str();
}

/// Reads the DB-formatted SRP verifier and gets the verifier
/// and salt components.
bool decode_srp_verifier_and_salt(const std::string &encoded,
	std::string *verifier, std::string *salt)
{
	std::vector<std::string> components = str_split(encoded, '#');

	if ((components.size() != 4)
			|| (components[1] != "1") // 1 means srp
			|| !base64_is_valid(components[2])
			|| !base64_is_valid(components[3]))
		return false;

	*salt = base64_decode(components[2]);
	*verifier = base64_decode(components[3]);
	return true;

}


code:
/*
Minetest
Copyright (C) 2015, 2016 est31 <MTest31@outlook.com>

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.
*/

#ifndef AUTH_H
#define AUTH_H

/// Gets the base64 encoded legacy password db entry.
std::string translate_password(const std::string &name,
	const std::string &password);

/// Creates a verification key with given salt and password.
std::string generate_srp_verifier(const std::string &name,
	const std::string &password, const std::string &salt);

/// Creates a verification key and salt with given password.
void generate_srp_verifier_and_salt(const std::string &name,
	const std::string &password, std::string *verifier,
	std::string *salt);

/// Gets an SRP verifier, generating a salt,
/// and encodes it as DB-ready string.
std::string get_encoded_srp_verifier(const std::string &name,
	const std::string &password);

/// Converts the passed SRP verifier into a DB-ready format.
std::string encode_srp_verifier(const std::string &verifier,
	const std::string &salt);

/// Reads the DB-formatted SRP verifier and gets the verifier
/// and salt components.
bool decode_srp_verifier_and_salt(const std::string &encoded,
	std::string *verifier, std::string *salt);

#endif


code:
/*
base64.cpp and base64.h

Copyright (C) 2004-2008 René Nyffenegger

This source code is provided 'as-is', without any express or implied
warranty. In no event will the author be held liable for any damages
arising from the use of this software.

Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it
freely, subject to the following restrictions:

1. The origin of this source code must not be misrepresented; you must not
   claim that you wrote the original source code. If you use this source code
   in a product, an acknowledgment in the product documentation would be
   appreciated but is not required.

2. Altered source versions must be plainly marked as such, and must not be
   misrepresented as being the original source code.

3. This notice may not be removed or altered from any source distribution.

René Nyffenegger rene.nyffenegger@adp-gmbh.ch

*/

#include "base64.h"
#include <iostream>

static const std::string base64_chars =
		"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
		"abcdefghijklmnopqrstuvwxyz"
		"0123456789+/";

static inline bool is_base64(unsigned char c) {
	return (isalnum(c) || (c == '+') || (c == '/'));
}

bool base64_is_valid(std::string const& s)
{
	for(size_t i=0; i<s.size(); i++)
		if(!is_base64(s[i])) return false;
	return true;
}

std::string base64_encode(unsigned char const* bytes_to_encode, unsigned int in_len) {
	std::string ret;
	int i = 0;
	int j = 0;
	unsigned char char_array_3[3];
	unsigned char char_array_4[4];

	while (in_len--) {
		char_array_3[i++] = *(bytes_to_encode++);
		if (i == 3) {
			char_array_4[0] = (char_array_3[0] & 0xfc) >> 2;
			char_array_4[1] = ((char_array_3[0] & 0x03) << 4) + ((char_array_3[1] & 0xf0) >> 4);
			char_array_4[2] = ((char_array_3[1] & 0x0f) << 2) + ((char_array_3[2] & 0xc0) >> 6);
			char_array_4[3] = char_array_3[2] & 0x3f;

			for(i = 0; (i <4) ; i++)
				ret += base64_chars[char_array_4[i]];
			i = 0;
		}
	}

	if (i)
	{
		for(j = i; j < 3; j++)
			char_array_3[j] = '\0';

		char_array_4[0] = (char_array_3[0] & 0xfc) >> 2;
		char_array_4[1] = ((char_array_3[0] & 0x03) << 4) + ((char_array_3[1] & 0xf0) >> 4);
		char_array_4[2] = ((char_array_3[1] & 0x0f) << 2) + ((char_array_3[2] & 0xc0) >> 6);
		char_array_4[3] = char_array_3[2] & 0x3f;

		for (j = 0; (j < i + 1); j++)
			ret += base64_chars[char_array_4[j]];

	// Don't pad it with =
		/*while((i++ < 3))
			ret += '=';*/

	}

	return ret;

}

std::string base64_decode(std::string const& encoded_string) {
	int in_len = encoded_string.size();
	int i = 0;
	int j = 0;
	int in_ = 0;
	unsigned char char_array_4[4], char_array_3[3];
	std::string ret;

	while (in_len-- && ( encoded_string[in_] != '=') && is_base64(encoded_string[in_])) {
		char_array_4[i++] = encoded_string[in_]; in_++;
		if (i ==4) {
			for (i = 0; i <4; i++)
				char_array_4[i] = base64_chars.find(char_array_4[i]);

			char_array_3[0] = (char_array_4[0] << 2) + ((char_array_4[1] & 0x30) >> 4);
			char_array_3[1] = ((char_array_4[1] & 0xf) << 4) + ((char_array_4[2] & 0x3c) >> 2);
			char_array_3[2] = ((char_array_4[2] & 0x3) << 6) + char_array_4[3];

			for (i = 0; (i < 3); i++)
				ret += char_array_3[i];
			i = 0;
		}
	}

	if (i) {
		for (j = i; j <4; j++)
			char_array_4[j] = 0;

		for (j = 0; j <4; j++)
			char_array_4[j] = base64_chars.find(char_array_4[j]);

		char_array_3[0] = (char_array_4[0] << 2) + ((char_array_4[1] & 0x30) >> 4);
		char_array_3[1] = ((char_array_4[1] & 0xf) << 4) + ((char_array_4[2] & 0x3c) >> 2);
		char_array_3[2] = ((char_array_4[2] & 0x3) << 6) + char_array_4[3];

		for (j = 0; (j < i - 1); j++) ret += char_array_3[j];
	}

	return ret;
}


code:
#ifndef BASE64_HEADER
#define BASE64_HEADER

#include <string>

bool base64_is_valid(std::string const& s);
std::string base64_encode(unsigned char const* , unsigned int len);
std::string base64_decode(std::string const& s);

#endif // BASE64_HEADER


code:
/*
Minetest
Copyright (C) 2010-2013 celeron55, Perttu Ahola <celeron55@gmail.com>

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.
*/

#ifndef BASICMACROS_HEADER
#define BASICMACROS_HEADER

#define ARRLEN(x) (sizeof(x) / sizeof((x)[0]))

#define MYMIN(a, b) ((a) < (b) ? (a) : (b))

#define MYMAX(a, b) ((a) > (b) ? (a) : (b))

// Requires <algorithm>
#define CONTAINS(c, v) (std::find((c).begin(), (c).end(), (v)) != (c).end())

// To disable copy constructors and assignment operations for some class
// 'Foobar', add the macro DISABLE_CLASS_COPY(Foobar) as a private member.
// Note this also disables copying for any classes derived from 'Foobar' as well
// as classes having a 'Foobar' member.
#define DISABLE_CLASS_COPY(C) \
	C(const C &);             \
	C &operator=(const C &)

#ifndef _MSC_VER
	#define UNUSED_ATTRIBUTE __attribute__ ((unused))
#else
	#define UNUSED_ATTRIBUTE
#endif

// Fail compilation if condition expr is not met.
// Note that 'msg' must follow the format of a valid identifier, e.g.
// STATIC_ASSERT(sizeof(foobar_t) == 40), foobar_t_is_wrong_size);
#define STATIC_ASSERT(expr, msg) \
	UNUSED_ATTRIBUTE typedef char msg[!!(expr) * 2 - 1]

// Macros to facilitate writing position vectors to a stream
// Usage:
//	v3s16 pos(1,2,3);
//	mystream << "message " << PP(pos) << std::endl;

#define PP(x) "("<<(x).X<<","<<(x).Y<<","<<(x).Z<<")"

#define PP2(x) "("<<(x).X<<","<<(x).Y<<")"

#endif


code:
/*
Minetest
Copyright (C) 2010-2013 celeron55, Perttu Ahola <celeron55@gmail.com>

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.
*/

#ifndef UTIL_CONTAINER_HEADER
#define UTIL_CONTAINER_HEADER

#include "../irrlichttypes.h"
#include "../exceptions.h"
#include "../threading/mutex.h"
#include "../threading/mutex_auto_lock.h"
#include "../threading/semaphore.h"
#include <list>
#include <vector>
#include <map>
#include <set>
#include <queue>

/*
Queue with unique values with fast checking of value existence
*/

template<typename Value>
class UniqueQueue
{
public:

	/*
	Does nothing if value is already queued.
	Return value:
	true: value added
	false: value already exists
	*/
	bool push_back(const Value& value)
	{
		if (m_set.insert(value).second)
		{
			m_queue.push(value);
			return true;
		}
		return false;
	}

	void pop_front()
	{
		m_set.erase(m_queue.front());
		m_queue.pop();
	}

	const Value& front() const
	{
		return m_queue.front();
	}

	u32 size() const
	{
		return m_queue.size();
	}

private:
	std::set<Value> m_set;
	std::queue<Value> m_queue;
};

template<typename Key, typename Value>
class MutexedMap
{
public:
	MutexedMap() {}

	void set(const Key &name, const Value &value)
	{
		MutexAutoLock lock(m_mutex);
		m_values[name] = value;
	}

	bool get(const Key &name, Value *result) const
	{
		MutexAutoLock lock(m_mutex);
		typename std::map<Key, Value>::const_iterator n =
			m_values.find(name);
		if (n == m_values.end())
			return false;
		if (result)
			*result = n->second;
		return true;
	}

	std::vector<Value> getValues() const
	{
		MutexAutoLock lock(m_mutex);
		std::vector<Value> result;
		for (typename std::map<Key, Value>::const_iterator
				it = m_values.begin();
				it != m_values.end(); ++it){
			result.push_back(it->second);
		}
		return result;
	}

	void clear() { m_values.clear(); }

private:
	std::map<Key, Value> m_values;
	mutable Mutex m_mutex;
};

// Thread-safe Double-ended queue

template<typename T>
class MutexedQueue
{
public:
	template<typename Key, typename U, typename Caller, typename CallerData>
	friend class RequestQueue;

	MutexedQueue() {}
	bool empty() const
	{
		MutexAutoLock lock(m_mutex);
		return m_queue.empty();
	}

	void push_back(T t)
	{
		MutexAutoLock lock(m_mutex);
		m_queue.push_back(t);
		m_signal.post();
	}

	/* this version of pop_front returns a empty element of T on timeout.
	* Make sure default constructor of T creates a recognizable "empty" element
	*/
	T pop_frontNoEx(u32 wait_time_max_ms)
	{
		if (m_signal.wait(wait_time_max_ms)) {
			MutexAutoLock lock(m_mutex);

			T t = m_queue.front();
			m_queue.pop_front();
			return t;
		} else {
			return T();
		}
	}

	T pop_front(u32 wait_time_max_ms)
	{
		if (m_signal.wait(wait_time_max_ms)) {
			MutexAutoLock lock(m_mutex);

			T t = m_queue.front();
			m_queue.pop_front();
			return t;
		} else {
			throw ItemNotFoundException("MutexedQueue: queue is empty");
		}
	}

	T pop_frontNoEx()
	{
		m_signal.wait();

		MutexAutoLock lock(m_mutex);

		T t = m_queue.front();
		m_queue.pop_front();
		return t;
	}

	T pop_back(u32 wait_time_max_ms=0)
	{
		if (m_signal.wait(wait_time_max_ms)) {
			MutexAutoLock lock(m_mutex);

			T t = m_queue.back();
			m_queue.pop_back();
			return t;
		} else {
			throw ItemNotFoundException("MutexedQueue: queue is empty");
		}
	}

	/* this version of pop_back returns a empty element of T on timeout.
	* Make sure default constructor of T creates a recognizable "empty" element
	*/
	T pop_backNoEx(u32 wait_time_max_ms)
	{
		if (m_signal.wait(wait_time_max_ms)) {
			MutexAutoLock lock(m_mutex);

			T t = m_queue.back();
			m_queue.pop_back();
			return t;
		} else {
			return T();
		}
	}

	T pop_backNoEx()
	{
		m_signal.wait();

		MutexAutoLock lock(m_mutex);

		T t = m_queue.back();
		m_queue.pop_back();
		return t;
	}

protected:
	Mutex &getMutex() { return m_mutex; }

	std::deque<T> &getQueue() { return m_queue; }

	std::deque<T> m_queue;
	mutable Mutex m_mutex;
	Semaphore m_signal;
};

template<typename K, typename V>
class LRUCache
{
public:
	LRUCache(size_t limit, void (*cache_miss)(void *data, const K &key, V *dest),
			void *data)
	{
		m_limit = limit;
		m_cache_miss = cache_miss;
		m_cache_miss_data = data;
	}

	void setLimit(size_t limit)
	{
		m_limit = limit;
		invalidate();
	}

	void invalidate()
	{
		m_map.clear();
		m_queue.clear();
	}

	const V *lookupCache(K key)
	{
		typename cache_type::iterator it = m_map.find(key);
		V *ret;
		if (it != m_map.end()) {
			// found!

			cache_entry_t &entry = it->second;

			ret = &entry.second;

			// update the usage information
			m_queue.erase(entry.first);
			m_queue.push_front(key);
			entry.first = m_queue.begin();
		} else {
			// cache miss -- enter into cache
			cache_entry_t &entry =
				m_map[key];
			ret = &entry.second;
			m_cache_miss(m_cache_miss_data, key, &entry.second);

			// delete old entries
			if (m_queue.size() == m_limit) {
				const K &id = m_queue.back();
				m_map.erase(id);
				m_queue.pop_back();
			}

			m_queue.push_front(key);
			entry.first = m_queue.begin();
		}
		return ret;
	}
private:
	void (*m_cache_miss)(void *data, const K &key, V *dest);
	void *m_cache_miss_data;
	size_t m_limit;
	typedef typename std::template pair<typename std::template list<K>::iterator, V> cache_entry_t;
	typedef std::template map<K, cache_entry_t> cache_type;
	cache_type m_map;
	// we can't use std::deque here, because its iterators get invalidated
	std::list<K> m_queue;
};

#endif


code:
/*
Minetest
Copyright (C) 2016 nerzhul, Loic Blot <loic.blot@unix-experience.fr>

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.
*/

#ifndef MT_CPP11_HEADER
#define MT_CPP11_HEADER

#if __cplusplus < 201103L || _MSC_VER < 1600
#define USE_CPP11_FAKE_KEYWORD
#endif

#ifdef USE_CPP11_FAKE_KEYWORD
#define constexpr const
#define nullptr NULL
#endif

#endif


code:
/*
Minetest
Copyright (C) 2016 nerzhul, Loic Blot <loic.blot@unix-experience.fr>

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.
*/

#ifndef MT_CPP11CONTAINER_HEADER
#define MT_CPP11CONTAINER_HEADER

#if __cplusplus >= 201103L
#define USE_UNORDERED_CONTAINERS
#endif

#if _MSC_VER >= 1600
#define USE_UNORDERED_CONTAINERS
#endif

#ifdef USE_UNORDERED_CONTAINERS
#include <unordered_map>
#include <unordered_set>
#define UNORDERED_MAP std::unordered_map
#define UNORDERED_SET std::unordered_set
#else
#include <map>
#include <set>
#define UNORDERED_MAP std::map
#define UNORDERED_SET std::set
#endif

#endif


code:
/*
Minetest
Copyright (C) 2010-2013 celeron55, Perttu Ahola <celeron55@gmail.com>

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 "directiontables.h"

const v3s16 g_6dirs[6] =
{
	// +right, +top, +back
	v3s16( 0, 0, 1), // back
	v3s16( 0, 1, 0), // top
	v3s16( 1, 0, 0), // right
	v3s16( 0, 0,-1), // front
	v3s16( 0,-1, 0), // bottom
	v3s16(-1, 0, 0) // left
};

const v3s16 g_26dirs[26] =
{
	// +right, +top, +back
	v3s16( 0, 0, 1), // back
	v3s16( 0, 1, 0), // top
	v3s16( 1, 0, 0), // right
	v3s16( 0, 0,-1), // front
	v3s16( 0,-1, 0), // bottom
	v3s16(-1, 0, 0), // left
	// 6
	v3s16(-1, 1, 0), // top left
	v3s16( 1, 1, 0), // top right
	v3s16( 0, 1, 1), // top back
	v3s16( 0, 1,-1), // top front
	v3s16(-1, 0, 1), // back left
	v3s16( 1, 0, 1), // back right
	v3s16(-1, 0,-1), // front left
	v3s16( 1, 0,-1), // front right
	v3s16(-1,-1, 0), // bottom left
	v3s16( 1,-1, 0), // bottom right
	v3s16( 0,-1, 1), // bottom back
	v3s16( 0,-1,-1), // bottom front
	// 18
	v3s16(-1, 1, 1), // top back-left
	v3s16( 1, 1, 1), // top back-right
	v3s16(-1, 1,-1), // top front-left
	v3s16( 1, 1,-1), // top front-right
	v3s16(-1,-1, 1), // bottom back-left
	v3s16( 1,-1, 1), // bottom back-right
	v3s16(-1,-1,-1), // bottom front-left
	v3s16( 1,-1,-1), // bottom front-right
	// 26
};

const v3s16 g_27dirs[27] =
{
	// +right, +top, +back
	v3s16( 0, 0, 1), // back
	v3s16( 0, 1, 0), // top
	v3s16( 1, 0, 0), // right
	v3s16( 0, 0,-1), // front
	v3s16( 0,-1, 0), // bottom
	v3s16(-1, 0, 0), // left
	// 6
	v3s16(-1, 1, 0), // top left
	v3s16( 1, 1, 0), // top right
	v3s16( 0, 1, 1), // top back
	v3s16( 0, 1,-1), // top front
	v3s16(-1, 0, 1), // back left
	v3s16( 1, 0, 1), // back right
	v3s16(-1, 0,-1), // front left
	v3s16( 1, 0,-1), // front right
	v3s16(-1,-1, 0), // bottom left
	v3s16( 1,-1, 0), // bottom right
	v3s16( 0,-1, 1), // bottom back
	v3s16( 0,-1,-1), // bottom front
	// 18
	v3s16(-1, 1, 1), // top back-left
	v3s16( 1, 1, 1), // top back-right
	v3s16(-1, 1,-1), // top front-left
	v3s16( 1, 1,-1), // top front-right
	v3s16(-1,-1, 1), // bottom back-left
	v3s16( 1,-1, 1), // bottom back-right
	v3s16(-1,-1,-1), // bottom front-left
	v3s16( 1,-1,-1), // bottom front-right
	// 26
	v3s16(0,0,0),
};


code:
/*
Minetest
Copyright (C) 2010-2013 celeron55, Perttu Ahola <celeron55@gmail.com>

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.
*/

#ifndef UTIL_DIRECTIONTABLES_HEADER
#define UTIL_DIRECTIONTABLES_HEADER

#include "../irrlichttypes.h"
#include "../irr_v3d.h"

extern const v3s16 g_6dirs[6];

extern const v3s16 g_26dirs[26];

// 26th is (0,0,0)
extern const v3s16 g_27dirs[27];

/// Direction in the 6D format. g_27dirs contains corresponding vectors.
/// Here P means Positive, N stands for Negative.
enum Direction6D {
// 0
	D6D_ZP,
	D6D_YP,
	D6D_XP,
	D6D_ZN,
	D6D_YN,
	D6D_XN,
// 6
	D6D_XN_YP,
	D6D_XP_YP,
	D6D_YP_ZP,
	D6D_YP_ZN,
	D6D_XN_ZP,
	D6D_XP_ZP,
	D6D_XN_ZN,
	D6D_XP_ZN,
	D6D_XN_YN,
	D6D_XP_YN,
	D6D_YN_ZP,
	D6D_YN_ZN,
// 18
	D6D_XN_YP_ZP,
	D6D_XP_YP_ZP,
	D6D_XN_YP_ZN,
	D6D_XP_YP_ZN,
	D6D_XN_YN_ZP,
	D6D_XP_YN_ZP,
	D6D_XN_YN_ZN,
	D6D_XP_YN_ZN,
// 26
	D6D,

// aliases
	D6D_BACK   = D6D_ZP,
	D6D_TOP    = D6D_YP,
	D6D_RIGHT  = D6D_XP,
	D6D_FRONT  = D6D_ZN,
	D6D_BOTTOM = D6D_YN,
	D6D_LEFT   = D6D_XN,
};

/// Direction in the wallmounted format.
/// P is Positive, N is Negative.
enum DirectionWallmounted {
	DWM_YP,
	DWM_YN,
	DWM_XP,
	DWM_XN,
	DWM_ZP,
	DWM_ZN,
};

#endif


code:
/*
Copyright (C) 2013 xyz, Ilya Zhuravlev <whatever@xyz.is>
Copyright (C) 2016 Nore, Nathanaël Courant <nore@mesecons.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 "enriched_string.h"
#include "util/string.h"
#include "log.h"
using namespace irr::video;

EnrichedString::EnrichedString()
{
	clear();
}

EnrichedString::EnrichedString(const std::wstring &string,
		const std::vector<SColor> &colors):
	m_string(string),
	m_colors(colors),
	m_has_background(false)
{}

EnrichedString::EnrichedString(const std::wstring &s, const SColor &color)
{
	clear();
	addAtEnd(s, color);
}

EnrichedString::EnrichedString(const wchar_t *str, const SColor &color)
{
	clear();
	addAtEnd(std::wstring(str), color);
}

void EnrichedString::operator=(const wchar_t *str)
{
	clear();
	addAtEnd(std::wstring(str), SColor(255, 255, 255, 255));
}

void EnrichedString::addAtEnd(const std::wstring &s, const SColor &initial_color)
{
	SColor color(initial_color);
	size_t i = 0;
	while (i < s.length()) {
		if (s[i] != L'\x1b') {
			m_string += s[i];
			m_colors.push_back(color);
			++i;
			continue;
		}
		++i;
		size_t start_index = i;
		size_t length;
		if (i == s.length()) {
			break;
		}
		if (s[i] == L'(') {
			++i;
			++start_index;
			while (i < s.length() && s[i] != L')') {
				if (s[i] == L'\\') {
					++i;
				}
				++i;
			}
			length = i - start_index;
			++i;
		} else {
			++i;
			length = 1;
		}
		std::wstring escape_sequence(s, start_index, length);
		std::vector<std::wstring> parts = split(escape_sequence, L'@');
		if (parts[0] == L"c") {
			if (parts.size() < 2) {
				continue;
			}
			parseColorString(wide_to_utf8(parts[1]), color, true);
		} else if (parts[0] == L"b") {
			if (parts.size() < 2) {
				continue;
			}
			parseColorString(wide_to_utf8(parts[1]), m_background, true);
			m_has_background = true;
		}
		continue;
	}
}

void EnrichedString::addChar(const EnrichedString &source, size_t i)
{
	m_string += source.m_string[i];
	m_colors.push_back(source.m_colors[i]);
}

void EnrichedString::addCharNoColor(wchar_t c)
{
	m_string += c;
	if (m_colors.empty()) {
		m_colors.push_back(SColor(255, 255, 255, 255));
	} else {
		m_colors.push_back(m_colors[m_colors.size() - 1]);
	}
}

EnrichedString EnrichedString::operator+(const EnrichedString &other) const
{
	std::vector<SColor> result;
	result.insert(result.end(), m_colors.begin(), m_colors.end());
	result.insert(result.end(), other.m_colors.begin(), other.m_colors.end());
	return EnrichedString(m_string + other.m_string, result);
}

void EnrichedString::operator+=(const EnrichedString &other)
{
	m_string += other.m_string;
	m_colors.insert(m_colors.end(), other.m_colors.begin(), other.m_colors.end());
}

EnrichedString EnrichedString::substr(size_t pos, size_t len) const
{
	if (pos == m_string.length()) {
		return EnrichedString();
	}
	if (len == std::string::npos || pos + len > m_string.length()) {
		return EnrichedString(
		           m_string.substr(pos, std::string::npos),
		           std::vector<SColor>(m_colors.begin() + pos, m_colors.end())
		       );
	} else {
		return EnrichedString(
		           m_string.substr(pos, len),
		           std::vector<SColor>(m_colors.begin() + pos, m_colors.begin() + pos + len)
		       );
	}
}

const wchar_t *EnrichedString::c_str() const
{
	return m_string.c_str();
}

const std::vector<SColor> &EnrichedString::getColors() const
{
	return m_colors;
}

const std::wstring &EnrichedString::getString() const
{
	return m_string;
}


code:
/*
Copyright (C) 2013 xyz, Ilya Zhuravlev <whatever@xyz.is>
Copyright (C) 2016 Nore, Nathanaël Courant <nore@mesecons.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.
*/

#ifndef ENRICHEDSTRING_HEADER
#define ENRICHEDSTRING_HEADER

#include <string>
#include <vector>
#include <SColor.h>

class EnrichedString {
public:
	EnrichedString();
	EnrichedString(const std::wstring &s,
		const irr::video::SColor &color = irr::video::SColor(255, 255, 255, 255));
	EnrichedString(const wchar_t *str,
		const irr::video::SColor &color = irr::video::SColor(255, 255, 255, 255));
	EnrichedString(const std::wstring &string,
		const std::vector<irr::video::SColor> &colors);
	void operator=(const wchar_t *str);
	void addAtEnd(const std::wstring &s, const irr::video::SColor &color);

	// Adds the character source[i] at the end.
	// An EnrichedString should always be able to be copied
	// to the end of an existing EnrichedString that way.
	void addChar(const EnrichedString &source, size_t i);

	// Adds a single character at the end, without specifying its
	// color. The color used will be the one from the last character.
	void addCharNoColor(wchar_t c);

	EnrichedString substr(size_t pos = 0, size_t len = std::string::npos) const;
	EnrichedString operator+(const EnrichedString &other) const;
	void operator+=(const EnrichedString &other);
	const wchar_t *c_str() const;
	const std::vector<irr::video::SColor> &getColors() const;
	const std::wstring &getString() const;
	inline bool operator==(const EnrichedString &other) const
	{
		return (m_string == other.m_string && m_colors == other.m_colors);
	}
	inline bool operator!=(const EnrichedString &other) const
	{
		return !(*this == other);
	}
	inline void clear()
	{
		m_string.clear();
		m_colors.clear();
		m_has_background = false;
	}
	inline bool empty() const
	{
		return m_string.empty();
	}
	inline size_t size() const
	{
		return m_string.size();
	}
	inline bool hasBackground() const
	{
		return m_has_background;
	}
	inline irr::video::SColor getBackground() const
	{
		return m_background;
	}
private:
	std::wstring m_string;
	std::vector<irr::video::SColor> m_colors;
	bool m_has_background;
	irr::video::SColor m_background;
};

#endif


code:
/*
Minetest
Copyright (C) 2013 Jonathan Neuschäfer <j.neuschaefer@gmx.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.
*/

#ifndef HEX_HEADER
#define HEX_HEADER

#include <string>

static const char hex_chars[] = "0123456789abcdef";

static inline std::string hex_encode(const char *data, unsigned int data_size)
{
	std::string ret;
	char buf2[3];
	buf2[2] = '\0';

	for (unsigned int i = 0; i < data_size; i++) {
		unsigned char c = (unsigned char)data[i];
		buf2[0] = hex_chars[(c & 0xf0) >> 4];
		buf2[1] = hex_chars[c & 0x0f];
		ret.append(buf2);
	}

	return ret;
}

static inline std::string hex_encode(const std::string &data)
{
	return hex_encode(data.c_str(), data.size());
}

static inline bool hex_digit_decode(char hexdigit, unsigned char &value)
{
	if (hexdigit >= '0' && hexdigit <= '9')
		value = hexdigit - '0';
	else if (hexdigit >= 'A' && hexdigit <= 'F')
		value = hexdigit - 'A' + 10;
	else if (hexdigit >= 'a' && hexdigit <= 'f')
		value = hexdigit - 'a' + 10;
	else
		return false;
	return true;
}

#endif


code:
/* md32_common.h file used by sha256 implementation */
/* ====================================================================
 * Copyright (c) 1999-2007 The OpenSSL Project.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. All advertising materials mentioning features or use of this
 *    software must display the following acknowledgment:
 *    "This product includes software developed by the OpenSSL Project
 *    for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)"
 *
 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
 *    endorse or promote products derived from this software without
 *    prior written permission. For written permission, please contact
 *    licensing@OpenSSL.org.
 *
 * 5. Products derived from this software may not be called "OpenSSL"
 *    nor may "OpenSSL" appear in their names without prior written
 *    permission of the OpenSSL Project.
 *
 * 6. Redistributions of any form whatsoever must retain the following
 *    acknowledgment:
 *    "This product includes software developed by the OpenSSL Project
 *    for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)"
 *
 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 * ====================================================================
 *
 */

/*-
 * This is a generic 32 bit "collector" for message digest algorithms.
 * Whenever needed it collects input character stream into chunks of
 * 32 bit values and invokes a block function that performs actual hash
 * calculations.
 *
 * Porting guide.
 *
 * Obligatory macros:
 *
 * DATA_ORDER_IS_BIG_ENDIAN or DATA_ORDER_IS_LITTLE_ENDIAN
 *      this macro defines byte order of input stream.
 * HASH_CBLOCK
 *      size of a unit chunk HASH_BLOCK operates on.
 * HASH_LONG
 *      has to be at lest 32 bit wide, if it's wider, then
 *      HASH_LONG_LOG2 *has to* be defined along
 * HASH_CTX
 *      context structure that at least contains following
 *      members:
 *              typedef struct {
 *                      ...
 *                      HASH_LONG       Nl,Nh;
 *                      either {
 *                      HASH_LONG       data[HASH_LBLOCK];
 *                      unsigned char   data[HASH_CBLOCK];
 *                      };
 *                      unsigned int    num;
 *                      ...
 *                      } HASH_CTX;
 *      data[] vector is expected to be zeroed upon first call to
 *      HASH_UPDATE.
 * HASH_UPDATE
 *      name of "Update" function, implemented here.
 * HASH_TRANSFORM
 *      name of "Transform" function, implemented here.
 * HASH_FINAL
 *      name of "Final" function, implemented here.
 * HASH_BLOCK_DATA_ORDER
 *      name of "block" function capable of treating *unaligned* input
 *      message in original (data) byte order, implemented externally.
 * HASH_MAKE_STRING
 *      macro convering context variables to an ASCII hash string.
 *
 * MD5 example:
 *
 *      #define DATA_ORDER_IS_LITTLE_ENDIAN
 *
 *      #define HASH_LONG               MD5_LONG
 *      #define HASH_LONG_LOG2          MD5_LONG_LOG2
 *      #define HASH_CTX                MD5_CTX
 *      #define HASH_CBLOCK             MD5_CBLOCK
 *      #define HASH_UPDATE             MD5_Update
 *      #define HASH_TRANSFORM          MD5_Transform
 *      #define HASH_FINAL              MD5_Final
 *      #define HASH_BLOCK_DATA_ORDER   md5_block_data_order
 *
 *                                      <appro@fy.chalmers.se>
 */

#if !defined(DATA_ORDER_IS_BIG_ENDIAN) && !defined(DATA_ORDER_IS_LITTLE_ENDIAN)
# error "DATA_ORDER must be defined!"
#endif

#ifndef HASH_CBLOCK
# error "HASH_CBLOCK must be defined!"
#endif
#ifndef HASH_LONG
# error "HASH_LONG must be defined!"
#endif
#ifndef HASH_CTX
# error "HASH_CTX must be defined!"
#endif

#ifndef HASH_UPDATE
# error "HASH_UPDATE must be defined!"
#endif
#ifndef HASH_TRANSFORM
# error "HASH_TRANSFORM must be defined!"
#endif
#ifndef HASH_FINAL
# error "HASH_FINAL must be defined!"
#endif

#ifndef HASH_BLOCK_DATA_ORDER
# error "HASH_BLOCK_DATA_ORDER must be defined!"
#endif

/*
 * Engage compiler specific rotate intrinsic function if available.
 */
#undef ROTATE
#ifndef PEDANTIC
# if defined(_MSC_VER)
#  define ROTATE(a,n)   _lrotl(a,n)
# elif defined(__ICC)
#  define ROTATE(a,n)   _rotl(a,n)
# elif defined(__MWERKS__)
#  if defined(__POWERPC__)
#   define ROTATE(a,n)  __rlwinm(a,n,0,31)
#  elif defined(__MC68K__)
    /* Motorola specific tweak. <appro@fy.chalmers.se> */
#   define ROTATE(a,n)  ( n<24 ? __rol(a,n) : __ror(a,32-n) )
#  else
#   define ROTATE(a,n)  __rol(a,n)
#  endif
# elif defined(__GNUC__) && __GNUC__>=2 && !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM)
  /*
   * Some GNU C inline assembler templates. Note that these are
   * rotates by *constant* number of bits! But that's exactly
   * what we need here...
   *                                    <appro@fy.chalmers.se>
   */
#  if defined(__i386) || defined(__i386__) || defined(__x86_64) || defined(__x86_64__)
#   define ROTATE(a,n)  ({ register unsigned int ret;   \
                                asm (                   \
                                "roll %1,%0"            \
                                : "=r"(ret)             \
                                : "I"(n), "0"((unsigned int)(a))        \
                                : "cc");                \
                           ret;                         \
                        })
#  elif defined(_ARCH_PPC) || defined(_ARCH_PPC64) || \
        defined(__powerpc) || defined(__ppc__) || defined(__powerpc64__)
#   define ROTATE(a,n)  ({ register unsigned int ret;   \
                                asm (                   \
                                "rlwinm %0,%1,%2,0,31"  \
                                : "=r"(ret)             \
                                : "r"(a), "I"(n));      \
                           ret;                         \
                        })
#  elif defined(__s390x__)
#   define ROTATE(a,n) ({ register unsigned int ret;    \
                                asm ("rll %0,%1,%2"     \
                                : "=r"(ret)             \
                                : "r"(a), "I"(n));      \
                          ret;                          \
                        })
#  endif
# endif
#endif                          /* PEDANTIC */

#ifndef ROTATE
# define ROTATE(a,n)     (((a)<<(n))|(((a)&0xffffffff)>>(32-(n))))
#endif

#if defined(DATA_ORDER_IS_BIG_ENDIAN)

# ifndef PEDANTIC
#  if defined(__GNUC__) && __GNUC__>=2 && !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM)
#   if ((defined(__i386) || defined(__i386__)) && !defined(I386_ONLY)) || \
      (defined(__x86_64) || defined(__x86_64__))
#    if !defined(B_ENDIAN)
    /*
     * This gives ~30-40% performance improvement in SHA-256 compiled
     * with gcc [on P4]. Well, first macro to be frank. We can pull
     * this trick on x86* platforms only, because these CPUs can fetch
     * unaligned data without raising an exception.
     */
#     define HOST_c2l(c,l)        ({ unsigned int r=*((const unsigned int *)(c)); \
                                   asm ("bswapl %0":"=r"(r):"0"(r));    \
                                   (c)+=4; (l)=r;                       })
#     define HOST_l2c(l,c)        ({ unsigned int r=(l);                  \
                                   asm ("bswapl %0":"=r"(r):"0"(r));    \
                                   *((unsigned int *)(c))=r; (c)+=4; r; })
#    endif
#   elif defined(__aarch64__)
#    if defined(__BYTE_ORDER__)
#     if defined(__ORDER_LITTLE_ENDIAN__) && __BYTE_ORDER__==__ORDER_LITTLE_ENDIAN__
#      define HOST_c2l(c,l)      ({ unsigned int r;              \
                                   asm ("rev    %w0,%w1"        \
                                        :"=r"(r)                \
                                        :"r"(*((const unsigned int *)(c))));\
                                   (c)+=4; (l)=r;               })
#      define HOST_l2c(l,c)      ({ unsigned int r;              \
                                   asm ("rev    %w0,%w1"        \
                                        :"=r"(r)                \
                                        :"r"((unsigned int)(l)));\
                                   *((unsigned int *)(c))=r; (c)+=4; r; })
#     elif defined(__ORDER_BIG_ENDIAN__) && __BYTE_ORDER__==__ORDER_BIG_ENDIAN__
#      define HOST_c2l(c,l)      ((l)=*((const unsigned int *)(c)), (c)+=4, (l))
#      define HOST_l2c(l,c)      (*((unsigned int *)(c))=(l), (c)+=4, (l))
#     endif
#    endif
#   endif
#  endif
#  if defined(__s390__) || defined(__s390x__)
#   define HOST_c2l(c,l) ((l)=*((const unsigned int *)(c)), (c)+=4, (l))
#   define HOST_l2c(l,c) (*((unsigned int *)(c))=(l), (c)+=4, (l))
#  endif
# endif

# ifndef HOST_c2l
#  define HOST_c2l(c,l)   (l =(((unsigned long)(*((c)++)))<<24),          \
                         l|=(((unsigned long)(*((c)++)))<<16),          \
                         l|=(((unsigned long)(*((c)++)))<< 8),          \
                         l|=(((unsigned long)(*((c)++)))    )           )
# endif
# ifndef HOST_l2c
#  define HOST_l2c(l,c)   (*((c)++)=(unsigned char)(((l)>>24)&0xff),      \
                         *((c)++)=(unsigned char)(((l)>>16)&0xff),      \
                         *((c)++)=(unsigned char)(((l)>> 8)&0xff),      \
                         *((c)++)=(unsigned char)(((l)    )&0xff),      \
                         l)
# endif

#elif defined(DATA_ORDER_IS_LITTLE_ENDIAN)

# ifndef PEDANTIC
#  if defined(__GNUC__) && __GNUC__>=2 && !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM)
#   if defined(__s390x__)
#    define HOST_c2l(c,l)        ({ asm ("lrv    %0,%1"                  \
                                   :"=d"(l) :"m"(*(const unsigned int *)(c)));\
                                   (c)+=4; (l);                         })
#    define HOST_l2c(l,c)        ({ asm ("strv   %1,%0"                  \
                                   :"=m"(*(unsigned int *)(c)) :"d"(l));\
                                   (c)+=4; (l);                         })
#   endif
#  endif
#  if defined(__i386) || defined(__i386__) || defined(__x86_64) || defined(__x86_64__)
#   ifndef B_ENDIAN
    /* See comment in DATA_ORDER_IS_BIG_ENDIAN section. */
#    define HOST_c2l(c,l)        ((l)=*((const unsigned int *)(c)), (c)+=4, l)
#    define HOST_l2c(l,c)        (*((unsigned int *)(c))=(l), (c)+=4, l)
#   endif
#  endif
# endif

# ifndef HOST_c2l
#  define HOST_c2l(c,l)   (l =(((unsigned long)(*((c)++)))    ),          \
                         l|=(((unsigned long)(*((c)++)))<< 8),          \
                         l|=(((unsigned long)(*((c)++)))<<16),          \
                         l|=(((unsigned long)(*((c)++)))<<24)           )
# endif
# ifndef HOST_l2c
#  define HOST_l2c(l,c)   (*((c)++)=(unsigned char)(((l)    )&0xff),      \
                         *((c)++)=(unsigned char)(((l)>> 8)&0xff),      \
                         *((c)++)=(unsigned char)(((l)>>16)&0xff),      \
                         *((c)++)=(unsigned char)(((l)>>24)&0xff),      \
                         l)
# endif

#endif

/*
 * Time for some action:-)
 */

int HASH_UPDATE(HASH_CTX *c, const void *data_, size_t len)
{
    const unsigned char *data = data_;
    unsigned char *p;
    HASH_LONG l;
    size_t n;

    if (len == 0)
        return 1;

    l = (c->Nl + (((HASH_LONG) len) << 3)) & 0xffffffffUL;
    /*
     * 95-05-24 eay Fixed a bug with the overflow handling, thanks to Wei Dai
     * <weidai@eskimo.com> for pointing it out.
     */
    if (l < c->Nl)              /* overflow */
        c->Nh++;
    c->Nh += (HASH_LONG) (len >> 29); /* might cause compiler warning on
                                       * 16-bit */
    c->Nl = l;

    n = c->num;
    if (n != 0) {
        p = (unsigned char *)c->data;

        if (len >= HASH_CBLOCK || len + n >= HASH_CBLOCK) {
            memcpy(p + n, data, HASH_CBLOCK - n);
            HASH_BLOCK_DATA_ORDER(c, p, 1);
            n = HASH_CBLOCK - n;
            data += n;
            len -= n;
            c->num = 0;
            memset(p, 0, HASH_CBLOCK); /* keep it zeroed */
        } else {
            memcpy(p + n, data, len);
            c->num += (unsigned int)len;
            return 1;
        }
    }

    n = len / HASH_CBLOCK;
    if (n > 0) {
        HASH_BLOCK_DATA_ORDER(c, data, n);
        n *= HASH_CBLOCK;
        data += n;
        len -= n;
    }

    if (len != 0) {
        p = (unsigned char *)c->data;
        c->num = (unsigned int)len;
        memcpy(p, data, len);
    }
    return 1;
}

void HASH_TRANSFORM(HASH_CTX *c, const unsigned char *data)
{
    HASH_BLOCK_DATA_ORDER(c, data, 1);
}

int HASH_FINAL(unsigned char *md, HASH_CTX *c)
{
    unsigned char *p = (unsigned char *)c->data;
    size_t n = c->num;

    p[n] = 0x80;                /* there is always room for one */
    n++;

    if (n > (HASH_CBLOCK - 8)) {
        memset(p + n, 0, HASH_CBLOCK - n);
        n = 0;
        HASH_BLOCK_DATA_ORDER(c, p, 1);
    }
    memset(p + n, 0, HASH_CBLOCK - 8 - n);

    p += HASH_CBLOCK - 8;
#if   defined(DATA_ORDER_IS_BIG_ENDIAN)
    (void)HOST_l2c(c->Nh, p);
    (void)HOST_l2c(c->Nl, p);
#elif defined(DATA_ORDER_IS_LITTLE_ENDIAN)
    (void)HOST_l2c(c->Nl, p);
    (void)HOST_l2c(c->Nh, p);
#endif
    p -= HASH_CBLOCK;
    HASH_BLOCK_DATA_ORDER(c, p, 1);
    c->num = 0;
    memset(p, 0, HASH_CBLOCK);

#ifndef HASH_MAKE_STRING
# error "HASH_MAKE_STRING must be defined!"
#else
    HASH_MAKE_STRING(c, md);
#endif

    return 1;
}

#ifndef MD32_REG_T
# if defined(__alpha) || defined(__sparcv9) || defined(__mips)
#  define MD32_REG_T long
/*
 * This comment was originaly written for MD5, which is why it
 * discusses A-D. But it basically applies to all 32-bit digests,
 * which is why it was moved to common header file.
 *
 * In case you wonder why A-D are declared as long and not
 * as MD5_LONG. Doing so results in slight performance
 * boost on LP64 architectures. The catch is we don't
 * really care if 32 MSBs of a 64-bit register get polluted
 * with eventual overflows as we *save* only 32 LSBs in
 * *either* case. Now declaring 'em long excuses the compiler
 * from keeping 32 MSBs zeroed resulting in 13% performance
 * improvement under SPARC Solaris7/64 and 5% under AlphaLinux.
 * Well, to be honest it should say that this *prevents*
 * performance degradation.
 *                              <appro@fy.chalmers.se>
 */
# else
/*
 * Above is not absolute and there are LP64 compilers that
 * generate better code if MD32_REG_T is defined int. The above
 * pre-processor condition reflects the circumstances under which
 * the conclusion was made and is subject to further extension.
 *                              <appro@fy.chalmers.se>
 */
#  define MD32_REG_T int
# endif
#endif


code:
/*
Minetest
Copyright (C) 2010-2013 celeron55, Perttu Ahola <celeron55@gmail.com>

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 "numeric.h"

#include "log.h"
#include "../constants.h" // BS, MAP_BLOCKSIZE
#include "../noise.h" // PseudoRandom, PcgRandom
#include "../threading/mutex_auto_lock.h"
#include <string.h>

// myrand

PcgRandom g_pcgrand;

u32 myrand()
{
	return g_pcgrand.next();
}

void mysrand(unsigned int seed)
{
	g_pcgrand.seed(seed);
}

void myrand_bytes(void *out, size_t len)
{
	g_pcgrand.bytes(out, len);
}

int myrand_range(int min, int max)
{
	return g_pcgrand.range(min, max);
}

/*
	64-bit unaligned version of MurmurHash
*/
u64 murmur_hash_64_ua(const void *key, int len, unsigned int seed)
{
	const u64 m = 0xc6a4a7935bd1e995ULL;
	const int r = 47;
	u64 h = seed ^ (len * m);

	const u64 *data = (const u64 *)key;
	const u64 *end = data + (len / 8);

	while (data != end) {
		u64 k;
		memcpy(&k, data, sizeof(u64));
		data++;

		k *= m;
		k ^= k >> r;
		k *= m;

		h ^= k;
		h *= m;
	}

	const unsigned char *data2 = (const unsigned char *)data;
	switch (len & 7) {
		case 7: h ^= (u64)data2[6] << 48;
		case 6: h ^= (u64)data2[5] << 40;
		case 5: h ^= (u64)data2[4] << 32;
		case 4: h ^= (u64)data2[3] << 24;
		case 3: h ^= (u64)data2[2] << 16;
		case 2: h ^= (u64)data2[1] << 8;
		case 1: h ^= (u64)data2[0];
				h *= m;
	}

	h ^= h >> r;
	h *= m;
	h ^= h >> r;

	return h;
}

/*
	blockpos_b: position of block in block coordinates
	camera_pos: position of camera in nodes
	camera_dir: an unit vector pointing to camera direction
	range: viewing range
	distance_ptr: return location for distance from the camera
*/
bool isBlockInSight(v3s16 blockpos_b, v3f camera_pos, v3f camera_dir,
		f32 camera_fov, f32 range, f32 *distance_ptr)
{
	// Maximum radius of a block.  The magic number is
	// sqrt(3.0) / 2.0 in literal form.
	const f32 block_max_radius = 0.866025403784 * MAP_BLOCKSIZE * BS;

	v3s16 blockpos_nodes = blockpos_b * MAP_BLOCKSIZE;

	// Block center position
	v3f blockpos(
			((float)blockpos_nodes.X + MAP_BLOCKSIZE/2) * BS,
			((float)blockpos_nodes.Y + MAP_BLOCKSIZE/2) * BS,
			((float)blockpos_nodes.Z + MAP_BLOCKSIZE/2) * BS
	);

	// Block position relative to camera
	v3f blockpos_relative = blockpos - camera_pos;

	// Total distance
	f32 d = MYMAX(0, blockpos_relative.getLength() - block_max_radius);

	if(distance_ptr)
		*distance_ptr = d;

	// If block is far away, it's not in sight
	if(d > range)
		return false;

	// If block is (nearly) touching the camera, don't
	// bother validating further (that is, render it anyway)
	if(d == 0)
		return true;

	// Adjust camera position, for purposes of computing the angle,
	// such that a block that has any portion visible with the
	// current camera position will have the center visible at the
	// adjusted postion
	f32 adjdist = block_max_radius / cos((M_PI - camera_fov) / 2);

	// Block position relative to adjusted camera
	v3f blockpos_adj = blockpos - (camera_pos - camera_dir * adjdist);

	// Distance in camera direction (+=front, -=back)
	f32 dforward = blockpos_adj.dotProduct(camera_dir);

	// Cosine of the angle between the camera direction
	// and the block direction (camera_dir is an unit vector)
	f32 cosangle = dforward / blockpos_adj.getLength();

	// If block is not in the field of view, skip it
	// HOTFIX: use sligthly increased angle (+10%) to fix too agressive
	// culling. Somebody have to find out whats wrong with the math here.
	// Previous value: camera_fov / 2
	if(cosangle < cos(camera_fov * 0.55))
		return false;

	return true;
}


code:
/*
Minetest
Copyright (C) 2010-2013 celeron55, Perttu Ahola <celeron55@gmail.com>

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.
*/

#ifndef UTIL_NUMERIC_HEADER
#define UTIL_NUMERIC_HEADER

#include "basic_macros.h"
#include "../irrlichttypes.h"
#include "../irr_v2d.h"
#include "../irr_v3d.h"
#include "../irr_aabb3d.h"
#include "../threading/mutex.h"

#define rangelim(d, min, max) ((d) < (min) ? (min) : ((d) > (max) ? (max) : (d)))
#define myfloor(x) ((x) < 0.0 ? (int)(x) - 1 : (int)(x))
// The naive swap performs better than the xor version
#define SWAP(t, x, y) do { \
	t temp = x; \
	x = y; \
	y = temp; \
} while (0)

inline s16 getContainerPos(s16 p, s16 d)
{
	return (p >= 0 ? p : p - d + 1) / d;
}

inline v2s16 getContainerPos(v2s16 p, s16 d)
{
	return v2s16(
		getContainerPos(p.X, d),
		getContainerPos(p.Y, d)
	);
}

inline v3s16 getContainerPos(v3s16 p, s16 d)
{
	return v3s16(
		getContainerPos(p.X, d),
		getContainerPos(p.Y, d),
		getContainerPos(p.Z, d)
	);
}

inline v2s16 getContainerPos(v2s16 p, v2s16 d)
{
	return v2s16(
		getContainerPos(p.X, d.X),
		getContainerPos(p.Y, d.Y)
	);
}

inline v3s16 getContainerPos(v3s16 p, v3s16 d)
{
	return v3s16(
		getContainerPos(p.X, d.X),
		getContainerPos(p.Y, d.Y),
		getContainerPos(p.Z, d.Z)
	);
}

inline void getContainerPosWithOffset(s16 p, s16 d, s16 &container, s16 &offset)
{
	container = (p >= 0 ? p : p - d + 1) / d;
	offset = p & (d - 1);
}

inline void getContainerPosWithOffset(const v2s16 &p, s16 d, v2s16 &container, v2s16 &offset)
{
	getContainerPosWithOffset(p.X, d, container.X, offset.X);
	getContainerPosWithOffset(p.Y, d, container.Y, offset.Y);
}

inline void getContainerPosWithOffset(const v3s16 &p, s16 d, v3s16 &container, v3s16 &offset)
{
	getContainerPosWithOffset(p.X, d, container.X, offset.X);
	getContainerPosWithOffset(p.Y, d, container.Y, offset.Y);
	getContainerPosWithOffset(p.Z, d, container.Z, offset.Z);
}

inline bool isInArea(v3s16 p, s16 d)
{
	return (
		p.X >= 0 && p.X < d &&
		p.Y >= 0 && p.Y < d &&
		p.Z >= 0 && p.Z < d
	);
}

inline bool isInArea(v2s16 p, s16 d)
{
	return (
		p.X >= 0 && p.X < d &&
		p.Y >= 0 && p.Y < d
	);
}

inline bool isInArea(v3s16 p, v3s16 d)
{
	return (
		p.X >= 0 && p.X < d.X &&
		p.Y >= 0 && p.Y < d.Y &&
		p.Z >= 0 && p.Z < d.Z
	);
}

inline void sortBoxVerticies(v3s16 &p1, v3s16 &p2) {
	if (p1.X > p2.X)
		SWAP(s16, p1.X, p2.X);
	if (p1.Y > p2.Y)
		SWAP(s16, p1.Y, p2.Y);
	if (p1.Z > p2.Z)
		SWAP(s16, p1.Z, p2.Z);
}

inline v3s16 componentwise_min(const v3s16 &a, const v3s16 &b)
{
	return v3s16(MYMIN(a.X, b.X), MYMIN(a.Y, b.Y), MYMIN(a.Z, b.Z));
}

inline v3s16 componentwise_max(const v3s16 &a, const v3s16 &b)
{
	return v3s16(MYMAX(a.X, b.X), MYMAX(a.Y, b.Y), MYMAX(a.Z, b.Z));
}

/** Returns \p f wrapped to the range [-360, 360]
 *
 *  See test.cpp for example cases.
 *
 *  \note This is also used in cases where degrees wrapped to the range [0, 360]
 *  is innapropriate (e.g. pitch needs negative values)
 *
 *  \internal functionally equivalent -- although precision may vary slightly --
 *  to fmodf((f), 360.0f) however empirical tests indicate that this approach is
 *  faster.
 */
inline float modulo360f(float f)
{
	int sign;
	int whole;
	float fraction;

	if (f < 0) {
		f = -f;
		sign = -1;
	} else {
		sign = 1;
	}

	whole = f;

	fraction = f - whole;
	whole %= 360;

	return sign * (whole + fraction);
}

/** Returns \p f wrapped to the range [0, 360]
  */
inline float wrapDegrees_0_360(float f)
{
	float value = modulo360f(f);
	return value < 0 ? value + 360 : value;
}

/** Returns \p f wrapped to the range [-180, 180]
  */
inline float wrapDegrees_180(float f)
{
	float value = modulo360f(f + 180);
	if (value < 0)
		value += 360;
	return value - 180;
}

/*
	Pseudo-random (VC++ rand() sucks)
*/
#define MYRAND_RANGE 0xffffffff
u32 myrand();
void mysrand(unsigned int seed);
void myrand_bytes(void *out, size_t len);
int myrand_range(int min, int max);

/*
	Miscellaneous functions
*/

inline u32 get_bits(u32 x, u32 pos, u32 len)
{
	u32 mask = (1 << len) - 1;
	return (x >> pos) & mask;
}

inline void set_bits(u32 *x, u32 pos, u32 len, u32 val)
{
	u32 mask = (1 << len) - 1;
	*x &= ~(mask << pos);
	*x |= (val & mask) << pos;
}

inline u32 calc_parity(u32 v)
{
	v ^= v >> 16;
	v ^= v >> 8;
	v ^= v >> 4;
	v &= 0xf;
	return (0x6996 >> v) & 1;
}

u64 murmur_hash_64_ua(const void *key, int len, unsigned int seed);

bool isBlockInSight(v3s16 blockpos_b, v3f camera_pos, v3f camera_dir,
		f32 camera_fov, f32 range, f32 *distance_ptr=NULL);

/*
	Returns nearest 32-bit integer for given floating point number.
	<cmath> and <math.h> in VC++ don't provide round().
*/
inline s32 myround(f32 f)
{
	return (s32)(f < 0.f ? (f - 0.5f) : (f + 0.5f));
}

/*
	Returns integer position of node in given floating point position
*/
inline v3s16 floatToInt(v3f p, f32 d)
{
	return v3s16(
		(p.X + (p.X > 0 ? d / 2 : -d / 2)) / d,
		(p.Y + (p.Y > 0 ? d / 2 : -d / 2)) / d,
		(p.Z + (p.Z > 0 ? d / 2 : -d / 2)) / d);
}

/*
	Returns floating point position of node in given integer position
*/
inline v3f intToFloat(v3s16 p, f32 d)
{
	return v3f(
		(f32)p.X * d,
		(f32)p.Y * d,
		(f32)p.Z * d
	);
}

// Random helper. Usually d=BS
inline aabb3f getNodeBox(v3s16 p, float d)
{
	return aabb3f(
		(float)p.X * d - 0.5 * d,
		(float)p.Y * d - 0.5 * d,
		(float)p.Z * d - 0.5 * d,
		(float)p.X * d + 0.5 * d,
		(float)p.Y * d + 0.5 * d,
		(float)p.Z * d + 0.5 * d
	);
}

class IntervalLimiter
{
public:
	IntervalLimiter() : m_accumulator(0) {}
	/*
		dtime: time from last call to this method
		wanted_interval: interval wanted
		return value:
			true: action should be skipped
			false: action should be done
	*/
	bool step(float dtime, float wanted_interval)
	{
		m_accumulator += dtime;
		if (m_accumulator < wanted_interval)
			return false;
		m_accumulator -= wanted_interval;
		return true;
	}

private:
	float m_accumulator;
};

/*
	Splits a list into "pages". For example, the list [1,2,3,4,5] split
	into two pages would be [1,2,3],[4,5]. This function computes the
	minimum and maximum indices of a single page.

	length: Length of the list that should be split
	page: Page number, 1 <= page <= pagecount
	pagecount: The number of pages, >= 1
	minindex: Receives the minimum index (inclusive).
	maxindex: Receives the maximum index (exclusive).

	Ensures 0 <= minindex <= maxindex <= length.
*/
inline void paging(u32 length, u32 page, u32 pagecount, u32 &minindex, u32 &maxindex)
{
	if (length < 1 || pagecount < 1 || page < 1 || page > pagecount) {
		// Special cases or invalid parameters
		minindex = maxindex = 0;
	} else if(pagecount <= length) {
		// Less pages than entries in the list:
		// Each page contains at least one entry
		minindex = (length * (page-1) + (pagecount-1)) / pagecount;
		maxindex = (length * page + (pagecount-1)) / pagecount;
	} else {
		// More pages than entries in the list:
		// Make sure the empty pages are at the end
		if (page < length) {
			minindex = page-1;
			maxindex = page;
		} else {
			minindex = 0;
			maxindex = 0;
		}
	}
}

inline float cycle_shift(float value, float by = 0, float max = 1)
{
    if (value + by < 0)   return value + by + max;
    if (value + by > max) return value + by - max;
    return value + by;
}

inline bool is_power_of_two(u32 n)
{
	return n != 0 && (n & (n - 1)) == 0;
}

// Compute next-higher power of 2 efficiently, e.g. for power-of-2 texture sizes.
// Public Domain: https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
inline u32 npot2(u32 orig) {
	orig--;
	orig |= orig >> 1;
	orig |= orig >> 2;
	orig |= orig >> 4;
	orig |= orig >> 8;
	orig |= orig >> 16;
	return orig + 1;
}

#endif