code:
/*
 * Secure Remote Password 6a implementation
 * https://github.com/est31/csrp-gmp
 *
 * The MIT License (MIT)
 *
 * Copyright (c) 2010, 2013 Tom Cocagne, 2015 est31 <MTest31@outlook.com>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in
 * the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
 * of the Software, and to permit persons to whom the Software is furnished to do
 * so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 *
 */

/*
 *
 * Purpose:       This is a direct implementation of the Secure Remote Password
 *                Protocol version 6a as described by
 *                http://srp.stanford.edu/design.html
 *
 * Author:        tom.cocagne@gmail.com (Tom Cocagne)
 *
 * Dependencies:  LibGMP
 *
 * Usage:         Refer to test_srp.c for a demonstration
 *
 * Notes:
 *    This library allows multiple combinations of hashing algorithms and
 *    prime number constants. For authentication to succeed, the hash and
 *    prime number constants must match between
 *    srp_create_salted_verification_key(), srp_user_new(),
 *    and srp_verifier_new(). A recommended approach is to determine the
 *    desired level of security for an application and globally define the
 *    hash and prime number constants to the predetermined values.
 *
 *    As one might suspect, more bits means more security. As one might also
 *    suspect, more bits also means more processing time. The test_srp.c
 *    program can be easily modified to profile various combinations of
 *    hash & prime number pairings.
 */

#ifndef SRP_H
#define SRP_H

struct SRPVerifier;
struct SRPUser;

typedef enum {
	SRP_NG_1024,
	SRP_NG_2048,
	SRP_NG_4096,
	SRP_NG_8192,
	SRP_NG_CUSTOM
} SRP_NGType;

typedef enum {
	/*SRP_SHA1,*/
	/*SRP_SHA224,*/
	SRP_SHA256,
	/*SRP_SHA384,
	SRP_SHA512*/
} SRP_HashAlgorithm;

typedef enum {
	SRP_ERR,
	SRP_OK,
} SRP_Result;

// clang-format off

/* Sets the memory functions used by srp.
 * Note: this doesn't set the memory functions used by gmp,
 * but it is supported to have different functions for srp and gmp.
 * Don't call this after you have already allocated srp structures.
 */
void srp_set_memory_functions(
	void *(*new_srp_alloc) (size_t),
	void *(*new_srp_realloc) (void *, size_t),
	void (*new_srp_free) (void *));

/* Out: bytes_v, len_v
 *
 * The caller is responsible for freeing the memory allocated for bytes_v
 *
 * The n_hex and g_hex parameters should be 0 unless SRP_NG_CUSTOM is used for ng_type.
 * If provided, they must contain ASCII text of the hexidecimal notation.
 *
 * If bytes_s == NULL, it is filled with random data.
 * The caller is responsible for freeing.
 *
 * Returns SRP_OK on success, and SRP_ERR on error.
 * bytes_s might be in this case invalid, don't free it.
 */
SRP_Result srp_create_salted_verification_key(SRP_HashAlgorithm alg,
	SRP_NGType ng_type, const char *username_for_verifier,
	const unsigned char *password, size_t len_password,
	unsigned char **bytes_s,  size_t *len_s,
	unsigned char **bytes_v, size_t *len_v,
	const char *n_hex, const char *g_hex);

/* Out: bytes_B, len_B.
 *
 * On failure, bytes_B will be set to NULL and len_B will be set to 0
 *
 * The n_hex and g_hex parameters should be 0 unless SRP_NG_CUSTOM is used for ng_type
 *
 * If bytes_b == NULL, random data is used for b.
 *
 * Returns pointer to SRPVerifier on success, and NULL on error.
 */
struct SRPVerifier* srp_verifier_new(SRP_HashAlgorithm alg, SRP_NGType ng_type,
	const char *username,
	const unsigned char *bytes_s, size_t len_s,
	const unsigned char *bytes_v, size_t len_v,
	const unsigned char *bytes_A, size_t len_A,
	const unsigned char *bytes_b, size_t len_b,
	unsigned char** bytes_B, size_t *len_B,
	const char* n_hex, const char* g_hex);

// clang-format on

void srp_verifier_delete(struct SRPVerifier *ver);

// srp_verifier_verify_session must have been called before
int srp_verifier_is_authenticated(struct SRPVerifier *ver);

const char *srp_verifier_get_username(struct SRPVerifier *ver);

/* key_length may be null */
const unsigned char *srp_verifier_get_session_key(
	struct SRPVerifier *ver, size_t *key_length);

size_t srp_verifier_get_session_key_length(struct SRPVerifier *ver);

/* Verifies session, on success, it writes bytes_HAMK.
 * user_M must be exactly srp_verifier_get_session_key_length() bytes in size
 */
void srp_verifier_verify_session(
	struct SRPVerifier *ver, const unsigned char *user_M, unsigned char **bytes_HAMK);

/*******************************************************************************/

/* The n_hex and g_hex parameters should be 0 unless SRP_NG_CUSTOM is used for ng_type */
struct SRPUser *srp_user_new(SRP_HashAlgorithm alg, SRP_NGType ng_type,
	const char *username, const char *username_for_verifier,
	const unsigned char *bytes_password, size_t len_password, const char *n_hex,
	const char *g_hex);

void srp_user_delete(struct SRPUser *usr);

int srp_user_is_authenticated(struct SRPUser *usr);

const char *srp_user_get_username(struct SRPUser *usr);

/* key_length may be null */
const unsigned char *srp_user_get_session_key(struct SRPUser *usr, size_t *key_length);

size_t srp_user_get_session_key_length(struct SRPUser *usr);

// clang-format off

/* Output: username, bytes_A, len_A.
 * If you don't want it get written, set username to NULL.
 * If bytes_a == NULL, random data is used for a. */
SRP_Result srp_user_start_authentication(struct SRPUser* usr, char **username,
	const unsigned char *bytes_a, size_t len_a,
	unsigned char **bytes_A, size_t* len_A);

/* Output: bytes_M, len_M  (len_M may be null and will always be
 *                          srp_user_get_session_key_length() bytes in size) */
void srp_user_process_challenge(struct SRPUser *usr,
	const unsigned char *bytes_s, size_t len_s,
	const unsigned char *bytes_B, size_t len_B,
	unsigned char **bytes_M, size_t *len_M);
// clang-format on

/* bytes_HAMK must be exactly srp_user_get_session_key_length() bytes in size */
void srp_user_verify_session(struct SRPUser *usr, const unsigned char *bytes_HAMK);

#endif /* Include Guard */


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

#ifndef STRFND_HEADER
#define STRFND_HEADER

#include <string>

template <typename T>
class BasicStrfnd {
	typedef std::basic_string<T> String;
	String str;
	size_t pos;
public:
	BasicStrfnd(const String &s) : str(s), pos(0) {}
	void start(const String &s) { str = s; pos = 0; }
	size_t where() { return pos; }
	void to(size_t i) { pos = i; }
	bool at_end() { return pos >= str.size(); }
	String what() { return str; }

	String next(const String &sep)
	{
		if (pos >= str.size())
			return String();

		size_t n;
		if (sep.empty() || (n = str.find(sep, pos)) == String::npos) {
			n = str.size();
		}
		String ret = str.substr(pos, n - pos);
		pos = n + sep.size();
		return ret;
	}

	// Returns substr up to the next occurence of sep that isn't escaped with esc ('\\')
	String next_esc(const String &sep, T esc=static_cast<T>('\\'))
	{
		if (pos >= str.size())
			return String();

		size_t n, old_p = pos;
		do {
			if (sep.empty() || (n = str.find(sep, pos)) == String::npos) {
				pos = n = str.size();
				break;
			}
			pos = n + sep.length();
		} while (n > 0 && str[n - 1] == esc);

		return str.substr(old_p, n - old_p);
	}

	void skip_over(const String &chars)
	{
		size_t p = str.find_first_not_of(chars, pos);
		if (p != String::npos)
			pos = p;
	}
};

typedef BasicStrfnd<char> Strfnd;
typedef BasicStrfnd<wchar_t> WStrfnd;

#endif

repo_name: pgimeno/minetest

license: unknown


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 "string.h"
#include "pointer.h"
#include "numeric.h"
#include "log.h"

#include "hex.h"
#include "../porting.h"

#include <algorithm>
#include <sstream>
#include <iomanip>
#include <map>

#ifndef _WIN32
	#include <iconv.h>
#else
	#define _WIN32_WINNT 0x0501
	#include <windows.h>
#endif

#if defined(_ICONV_H_) && (defined(__FreeBSD__) || defined(__NetBSD__) || \
	defined(__OpenBSD__) || defined(__DragonFly__))
	#define BSD_ICONV_USED
#endif

static bool parseHexColorString(const std::string &value, video::SColor &color);
static bool parseNamedColorString(const std::string &value, video::SColor &color);

#ifndef _WIN32

bool convert(const char *to, const char *from, char *outbuf,
		size_t outbuf_size, char *inbuf, size_t inbuf_size)
{
	iconv_t cd = iconv_open(to, from);

#ifdef BSD_ICONV_USED
	const char *inbuf_ptr = inbuf;
#else
	char *inbuf_ptr = inbuf;
#endif

	char *outbuf_ptr = outbuf;

	size_t *inbuf_left_ptr = &inbuf_size;
	size_t *outbuf_left_ptr = &outbuf_size;

	size_t old_size = inbuf_size;
	while (inbuf_size > 0) {
		iconv(cd, &inbuf_ptr, inbuf_left_ptr, &outbuf_ptr, outbuf_left_ptr);
		if (inbuf_size == old_size) {
			iconv_close(cd);
			return false;
		}
		old_size = inbuf_size;
	}

	iconv_close(cd);
	return true;
}

std::wstring utf8_to_wide(const std::string &input)
{
	size_t inbuf_size = input.length() + 1;
	// maximum possible size, every character is sizeof(wchar_t) bytes
	size_t outbuf_size = (input.length() + 1) * sizeof(wchar_t);

	char *inbuf = new char[inbuf_size];
	memcpy(inbuf, input.c_str(), inbuf_size);
	char *outbuf = new char[outbuf_size];
	memset(outbuf, 0, outbuf_size);

	if (!convert("WCHAR_T", "UTF-8", outbuf, outbuf_size, inbuf, inbuf_size)) {
		infostream << "Couldn't convert UTF-8 string 0x" << hex_encode(input)
			<< " into wstring" << std::endl;
		delete[] inbuf;
		delete[] outbuf;
		return L"<invalid UTF-8 string>";
	}
	std::wstring out((wchar_t *)outbuf);

	delete[] inbuf;
	delete[] outbuf;

	return out;
}

#ifdef __ANDROID__
// TODO: this is an ugly fix for wide_to_utf8 somehow not working on android
std::string wide_to_utf8(const std::wstring &input)
{
	return wide_to_narrow(input);
}
#else
std::string wide_to_utf8(const std::wstring &input)
{
	size_t inbuf_size = (input.length() + 1) * sizeof(wchar_t);
	// maximum possible size: utf-8 encodes codepoints using 1 up to 6 bytes
	size_t outbuf_size = (input.length() + 1) * 6;

	char *inbuf = new char[inbuf_size];
	memcpy(inbuf, input.c_str(), inbuf_size);
	char *outbuf = new char[outbuf_size];
	memset(outbuf, 0, outbuf_size);

	if (!convert("UTF-8", "WCHAR_T", outbuf, outbuf_size, inbuf, inbuf_size)) {
		infostream << "Couldn't convert wstring 0x" << hex_encode(inbuf, inbuf_size)
			<< " into UTF-8 string" << std::endl;
		delete[] inbuf;
		delete[] outbuf;
		return "<invalid wstring>";
	}
	std::string out(outbuf);

	delete[] inbuf;
	delete[] outbuf;

	return out;
}

#endif
#else // _WIN32

std::wstring utf8_to_wide(const std::string &input)
{
	size_t outbuf_size = input.size() + 1;
	wchar_t *outbuf = new wchar_t[outbuf_size];
	memset(outbuf, 0, outbuf_size * sizeof(wchar_t));
	MultiByteToWideChar(CP_UTF8, 0, input.c_str(), input.size(),
		outbuf, outbuf_size);
	std::wstring out(outbuf);
	delete[] outbuf;
	return out;
}

std::string wide_to_utf8(const std::wstring &input)
{
	size_t outbuf_size = (input.size() + 1) * 6;
	char *outbuf = new char[outbuf_size];
	memset(outbuf, 0, outbuf_size);
	WideCharToMultiByte(CP_UTF8, 0, input.c_str(), input.size(),
		outbuf, outbuf_size, NULL, NULL);
	std::string out(outbuf);
	delete[] outbuf;
	return out;
}

#endif // _WIN32

wchar_t *utf8_to_wide_c(const char *str)
{
	std::wstring ret = utf8_to_wide(std::string(str)).c_str();
	size_t len = ret.length();
	wchar_t *ret_c = new wchar_t[len + 1];
	memset(ret_c, 0, (len + 1) * sizeof(wchar_t));
	memcpy(ret_c, ret.c_str(), len * sizeof(wchar_t));
	return ret_c;
}

// You must free the returned string!
// The returned string is allocated using new
wchar_t *narrow_to_wide_c(const char *str)
{
	wchar_t *nstr = NULL;
#if defined(_WIN32)
	int nResult = MultiByteToWideChar(CP_UTF8, 0, (LPCSTR) str, -1, 0, 0);
	if (nResult == 0) {
		errorstream<<"gettext: MultiByteToWideChar returned null"<<std::endl;
	} else {
		nstr = new wchar_t[nResult];
		MultiByteToWideChar(CP_UTF8, 0, (LPCSTR) str, -1, (WCHAR *) nstr, nResult);
	}
#else
	size_t len = strlen(str);
	nstr = new wchar_t[len + 1];

	std::wstring intermediate = narrow_to_wide(str);
	memset(nstr, 0, (len + 1) * sizeof(wchar_t));
	memcpy(nstr, intermediate.c_str(), len * sizeof(wchar_t));
#endif

	return nstr;
}

#ifdef __ANDROID__

const wchar_t* wide_chars =
	L" !\"#$%&'()*+,-./0123456789:;<=>?@"
	L"ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`"
	L"abcdefghijklmnopqrstuvwxyz{|}~";

int wctomb(char *s, wchar_t wc)
{
	for (unsigned int j = 0; j < (sizeof(wide_chars)/sizeof(wchar_t));j++) {
		if (wc == wide_chars[j]) {
			*s = (char) (j+32);
			return 1;
		}
		else if (wc == L'\n') {
			*s = '\n';
			return 1;
		}
	}
	return -1;
}

int mbtowc(wchar_t *pwc, const char *s, size_t n)
{
	std::wstring intermediate = narrow_to_wide(s);

	if (intermediate.length() > 0) {
		*pwc = intermediate[0];
		return 1;
	}
	else {
		return -1;
	}
}

std::wstring narrow_to_wide(const std::string &mbs) {
	size_t wcl = mbs.size();

	std::wstring retval = L"";

	for (unsigned int i = 0; i < wcl; i++) {
		if (((unsigned char) mbs[i] >31) &&
		 ((unsigned char) mbs[i] < 127)) {

			retval += wide_chars[(unsigned char) mbs[i] -32];
		}
		//handle newline
		else if (mbs[i] == '\n') {
			retval += L'\n';
		}
	}

	return retval;
}

#else // not Android

std::wstring narrow_to_wide(const std::string &mbs)
{
	size_t wcl = mbs.size();
	Buffer<wchar_t> wcs(wcl + 1);
	size_t len = mbstowcs(*wcs, mbs.c_str(), wcl);
	if (len == (size_t)(-1))
		return L"<invalid multibyte string>";
	wcs[len] = 0;
	return *wcs;
}

#endif

#ifdef __ANDROID__

std::string wide_to_narrow(const std::wstring &wcs) {
	size_t mbl = wcs.size()*4;

	std::string retval = "";
	for (unsigned int i = 0; i < wcs.size(); i++) {
		wchar_t char1 = (wchar_t) wcs[i];

		if (char1 == L'\n') {
			retval += '\n';
			continue;
		}

		for (unsigned int j = 0; j < wcslen(wide_chars);j++) {
			wchar_t char2 = (wchar_t) wide_chars[j];

			if (char1 == char2) {
				char toadd = (j+32);
				retval += toadd;
				break;
			}
		}
	}

	return retval;
}

#else // not Android

std::string wide_to_narrow(const std::wstring &wcs)
{
	size_t mbl = wcs.size() * 4;
	SharedBuffer<char> mbs(mbl+1);
	size_t len = wcstombs(*mbs, wcs.c_str(), mbl);
	if (len == (size_t)(-1))
		return "Character conversion failed!";
	else
		mbs[len] = 0;
	return *mbs;
}

#endif

std::string urlencode(const std::string &str)
{
	// Encodes non-unreserved URI characters by a percent sign
	// followed by two hex digits. See RFC 3986, section 2.3.
	static const char url_hex_chars[] = "0123456789ABCDEF";
	std::ostringstream oss(std::ios::binary);
	for (u32 i = 0; i < str.size(); i++) {
		unsigned char c = str[i];
		if (isalnum(c) || c == '-' || c == '.' || c == '_' || c == '~') {
			oss << c;
		} else {
			oss << "%"
				<< url_hex_chars[(c & 0xf0) >> 4]
				<< url_hex_chars[c & 0x0f];
		}
	}
	return oss.str();
}

std::string urldecode(const std::string &str)
{
	// Inverse of urlencode
	std::ostringstream oss(std::ios::binary);
	for (u32 i = 0; i < str.size(); i++) {
		unsigned char highvalue, lowvalue;
		if (str[i] == '%' &&
				hex_digit_decode(str[i+1], highvalue) &&
				hex_digit_decode(str[i+2], lowvalue)) {
			oss << (char) ((highvalue << 4) | lowvalue);
			i += 2;
		} else {
			oss << str[i];
		}
	}
	return oss.str();
}

u32 readFlagString(std::string str, const FlagDesc *flagdesc, u32 *flagmask)
{
	u32 result = 0;
	u32 mask = 0;
	char *s = &str[0];
	char *flagstr;
	char *strpos = NULL;

	while ((flagstr = strtok_r(s, ",", &strpos))) {
		s = NULL;

		while (*flagstr == ' ' || *flagstr == '\t')
			flagstr++;

		bool flagset = true;
		if (!strncasecmp(flagstr, "no", 2)) {
			flagset = false;
			flagstr += 2;
		}

		for (int i = 0; flagdesc[i].name; i++) {
			if (!strcasecmp(flagstr, flagdesc[i].name)) {
				mask |= flagdesc[i].flag;
				if (flagset)
					result |= flagdesc[i].flag;
				break;
			}
		}
	}

	if (flagmask)
		*flagmask = mask;

	return result;
}

std::string writeFlagString(u32 flags, const FlagDesc *flagdesc, u32 flagmask)
{
	std::string result;

	for (int i = 0; flagdesc[i].name; i++) {
		if (flagmask & flagdesc[i].flag) {
			if (!(flags & flagdesc[i].flag))
				result += "no";

			result += flagdesc[i].name;
			result += ", ";
		}
	}

	size_t len = result.length();
	if (len >= 2)
		result.erase(len - 2, 2);

	return result;
}

size_t mystrlcpy(char *dst, const char *src, size_t size)
{
	size_t srclen  = strlen(src) + 1;
	size_t copylen = MYMIN(srclen, size);

	if (copylen > 0) {
		memcpy(dst, src, copylen);
		dst[copylen - 1] = '\0';
	}

	return srclen;
}

char *mystrtok_r(char *s, const char *sep, char **lasts)
{
	char *t;

	if (!s)
		s = *lasts;

	while (*s && strchr(sep, *s))
		s++;

	if (!*s)
		return NULL;

	t = s;
	while (*t) {
		if (strchr(sep, *t)) {
			*t++ = '\0';
			break;
		}
		t++;
	}

	*lasts = t;
	return s;
}

u64 read_seed(const char *str)
{
	char *endptr;
	u64 num;

	if (str[0] == '0' && str[1] == 'x')
		num = strtoull(str, &endptr, 16);
	else
		num = strtoull(str, &endptr, 10);

	if (*endptr)
		num = murmur_hash_64_ua(str, (int)strlen(str), 0x1337);

	return num;
}

bool parseColorString(const std::string &value, video::SColor &color, bool quiet)
{
	bool success;

	if (value[0] == '#')
		success = parseHexColorString(value, color);
	else
		success = parseNamedColorString(value, color);

	if (!success && !quiet)
		errorstream << "Invalid color: \"" << value << "\"" << std::endl;

	return success;
}

static bool parseHexColorString(const std::string &value, video::SColor &color)
{
	unsigned char components[] = { 0x00, 0x00, 0x00, 0xff }; // R,G,B,A

	if (value[0] != '#')
		return false;

	size_t len = value.size();
	bool short_form;

	if (len == 9 || len == 7) // #RRGGBBAA or #RRGGBB
		short_form = false;
	else if (len == 5 || len == 4) // #RGBA or #RGB
		short_form = true;
	else
		return false;

	bool success = true;

	for (size_t pos = 1, cc = 0; pos < len; pos++, cc++) {
		assert(cc < sizeof components / sizeof components[0]);
		if (short_form) {
			unsigned char d;
			if (!hex_digit_decode(value[pos], d)) {
				success = false;
				break;
			}
			components[cc] = (d & 0xf) << 4 | (d & 0xf);
		} else {
			unsigned char d1, d2;
			if (!hex_digit_decode(value[pos], d1) ||
					!hex_digit_decode(value[pos+1], d2)) {
				success = false;
				break;
			}
			components[cc] = (d1 & 0xf) << 4 | (d2 & 0xf);
			pos++;	// skip the second digit -- it's already used
		}
	}

	if (success) {
		color.setRed(components[0]);
		color.setGreen(components[1]);
		color.setBlue(components[2]);
		color.setAlpha(components[3]);
	}

	return success;
}

struct ColorContainer {
	ColorContainer();
	std::map<const std::string, u32> colors;
};

ColorContainer::ColorContainer()
{
	colors["aliceblue"]              = 0xf0f8ff;
	colors["antiquewhite"]           = 0xfaebd7;
	colors["aqua"]                   = 0x00ffff;
	colors["aquamarine"]             = 0x7fffd4;
	colors["azure"]                  = 0xf0ffff;
	colors["beige"]                  = 0xf5f5dc;
	colors["bisque"]                 = 0xffe4c4;
	colors["black"]                  = 00000000;
	colors["blanchedalmond"]         = 0xffebcd;
	colors["blue"]                   = 0x0000ff;
	colors["blueviolet"]             = 0x8a2be2;
	colors["brown"]                  = 0xa52a2a;
	colors["burlywood"]              = 0xdeb887;
	colors["cadetblue"]              = 0x5f9ea0;
	colors["chartreuse"]             = 0x7fff00;
	colors["chocolate"]              = 0xd2691e;
	colors["coral"]                  = 0xff7f50;
	colors["cornflowerblue"]         = 0x6495ed;
	colors["cornsilk"]               = 0xfff8dc;
	colors["crimson"]                = 0xdc143c;
	colors["cyan"]                   = 0x00ffff;
	colors["darkblue"]               = 0x00008b;
	colors["darkcyan"]               = 0x008b8b;
	colors["darkgoldenrod"]          = 0xb8860b;
	colors["darkgray"]               = 0xa9a9a9;
	colors["darkgreen"]              = 0x006400;
	colors["darkgrey"]               = 0xa9a9a9;
	colors["darkkhaki"]              = 0xbdb76b;
	colors["darkmagenta"]            = 0x8b008b;
	colors["darkolivegreen"]         = 0x556b2f;
	colors["darkorange"]             = 0xff8c00;
	colors["darkorchid"]             = 0x9932cc;
	colors["darkred"]                = 0x8b0000;
	colors["darksalmon"]             = 0xe9967a;
	colors["darkseagreen"]           = 0x8fbc8f;
	colors["darkslateblue"]          = 0x483d8b;
	colors["darkslategray"]          = 0x2f4f4f;
	colors["darkslategrey"]          = 0x2f4f4f;
	colors["darkturquoise"]          = 0x00ced1;
	colors["darkviolet"]             = 0x9400d3;
	colors["deeppink"]               = 0xff1493;
	colors["deepskyblue"]            = 0x00bfff;
	colors["dimgray"]                = 0x696969;
	colors["dimgrey"]                = 0x696969;
	colors["dodgerblue"]             = 0x1e90ff;
	colors["firebrick"]              = 0xb22222;
	colors["floralwhite"]            = 0xfffaf0;
	colors["forestgreen"]            = 0x228b22;
	colors["fuchsia"]                = 0xff00ff;
	colors["gainsboro"]              = 0xdcdcdc;
	colors["ghostwhite"]             = 0xf8f8ff;
	colors["gold"]                   = 0xffd700;
	colors["goldenrod"]              = 0xdaa520;
	colors["gray"]                   = 0x808080;
	colors["green"]                  = 0x008000;
	colors["greenyellow"]            = 0xadff2f;
	colors["grey"]                   = 0x808080;
	colors["honeydew"]               = 0xf0fff0;
	colors["hotpink"]                = 0xff69b4;
	colors["indianred"]              = 0xcd5c5c;
	colors["indigo"]                 = 0x4b0082;
	colors["ivory"]                  = 0xfffff0;
	colors["khaki"]                  = 0xf0e68c;
	colors["lavender"]               = 0xe6e6fa;
	colors["lavenderblush"]          = 0xfff0f5;
	colors["lawngreen"]              = 0x7cfc00;
	colors["lemonchiffon"]           = 0xfffacd;
	colors["lightblue"]              = 0xadd8e6;
	colors["lightcoral"]             = 0xf08080;
	colors["lightcyan"]              = 0xe0ffff;
	colors["lightgoldenrodyellow"]   = 0xfafad2;
	colors["lightgray"]              = 0xd3d3d3;
	colors["lightgreen"]             = 0x90ee90;
	colors["lightgrey"]              = 0xd3d3d3;
	colors["lightpink"]              = 0xffb6c1;
	colors["lightsalmon"]            = 0xffa07a;
	colors["lightseagreen"]          = 0x20b2aa;
	colors["lightskyblue"]           = 0x87cefa;
	colors["lightslategray"]         = 0x778899;
	colors["lightslategrey"]         = 0x778899;
	colors["lightsteelblue"]         = 0xb0c4de;
	colors["lightyellow"]            = 0xffffe0;
	colors["lime"]                   = 0x00ff00;
	colors["limegreen"]              = 0x32cd32;
	colors["linen"]                  = 0xfaf0e6;
	colors["magenta"]                = 0xff00ff;
	colors["maroon"]                 = 0x800000;
	colors["mediumaquamarine"]       = 0x66cdaa;
	colors["mediumblue"]             = 0x0000cd;
	colors["mediumorchid"]           = 0xba55d3;
	colors["mediumpurple"]           = 0x9370db;
	colors["mediumseagreen"]         = 0x3cb371;
	colors["mediumslateblue"]        = 0x7b68ee;
	colors["mediumspringgreen"]      = 0x00fa9a;
	colors["mediumturquoise"]        = 0x48d1cc;
	colors["mediumvioletred"]        = 0xc71585;
	colors["midnightblue"]           = 0x191970;
	colors["mintcream"]              = 0xf5fffa;
	colors["mistyrose"]              = 0xffe4e1;
	colors["moccasin"]               = 0xffe4b5;
	colors["navajowhite"]            = 0xffdead;
	colors["navy"]                   = 0x000080;
	colors["oldlace"]                = 0xfdf5e6;
	colors["olive"]                  = 0x808000;
	colors["olivedrab"]              = 0x6b8e23;
	colors["orange"]                 = 0xffa500;
	colors["orangered"]              = 0xff4500;
	colors["orchid"]                 = 0xda70d6;
	colors["palegoldenrod"]          = 0xeee8aa;
	colors["palegreen"]              = 0x98fb98;
	colors["paleturquoise"]          = 0xafeeee;
	colors["palevioletred"]          = 0xdb7093;
	colors["papayawhip"]             = 0xffefd5;
	colors["peachpuff"]              = 0xffdab9;
	colors["peru"]                   = 0xcd853f;
	colors["pink"]                   = 0xffc0cb;
	colors["plum"]                   = 0xdda0dd;
	colors["powderblue"]             = 0xb0e0e6;
	colors["purple"]                 = 0x800080;
	colors["red"]                    = 0xff0000;
	colors["rosybrown"]              = 0xbc8f8f;
	colors["royalblue"]              = 0x4169e1;
	colors["saddlebrown"]            = 0x8b4513;
	colors["salmon"]                 = 0xfa8072;
	colors["sandybrown"]             = 0xf4a460;
	colors["seagreen"]               = 0x2e8b57;
	colors["seashell"]               = 0xfff5ee;
	colors["sienna"]                 = 0xa0522d;
	colors["silver"]                 = 0xc0c0c0;
	colors["skyblue"]                = 0x87ceeb;
	colors["slateblue"]              = 0x6a5acd;
	colors["slategray"]              = 0x708090;
	colors["slategrey"]              = 0x708090;
	colors["snow"]                   = 0xfffafa;
	colors["springgreen"]            = 0x00ff7f;
	colors["steelblue"]              = 0x4682b4;
	colors["tan"]                    = 0xd2b48c;
	colors["teal"]                   = 0x008080;
	colors["thistle"]                = 0xd8bfd8;
	colors["tomato"]                 = 0xff6347;
	colors["turquoise"]              = 0x40e0d0;
	colors["violet"]                 = 0xee82ee;
	colors["wheat"]                  = 0xf5deb3;
	colors["white"]                  = 0xffffff;
	colors["whitesmoke"]             = 0xf5f5f5;
	colors["yellow"]                 = 0xffff00;
	colors["yellowgreen"]            = 0x9acd32;

}

static const ColorContainer named_colors;

static bool parseNamedColorString(const std::string &value, video::SColor &color)
{
	std::string color_name;
	std::string alpha_string;

	/* If the string has a # in it, assume this is the start of a specified
	 * alpha value (if it isn't the string is invalid and the error will be
	 * caught later on, either because the color name won't be found or the
	 * alpha value will fail conversion)
	 */
	size_t alpha_pos = value.find('#');
	if (alpha_pos != std::string::npos) {
		color_name = value.substr(0, alpha_pos);
		alpha_string = value.substr(alpha_pos + 1);
	} else {
		color_name = value;
	}

	color_name = lowercase(value);

	std::map<const std::string, unsigned>::const_iterator it;
	it = named_colors.colors.find(color_name);
	if (it == named_colors.colors.end())
		return false;

	u32 color_temp = it->second;

	/* An empty string for alpha is ok (none of the color table entries
	 * have an alpha value either). Color strings without an alpha specified
	 * are interpreted as fully opaque
	 *
	 * For named colors the supplied alpha string (representing a hex value)
	 * must be exactly two digits. For example:  colorname#08
	 */
	if (!alpha_string.empty()) {
		if (alpha_string.length() != 2)
			return false;

		unsigned char d1, d2;
		if (!hex_digit_decode(alpha_string.at(0), d1)
				|| !hex_digit_decode(alpha_string.at(1), d2))
			return false;
		color_temp |= ((d1 & 0xf) << 4 | (d2 & 0xf)) << 24;
	} else {
		color_temp |= 0xff << 24;  // Fully opaque
	}

	color = video::SColor(color_temp);

	return true;
}

void str_replace(std::string &str, char from, char to)
{
	std::replace(str.begin(), str.end(), from, to);
}


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_STRING_HEADER
#define UTIL_STRING_HEADER

#include "irrlichttypes_bloated.h"
#include "cpp11_container.h"
#include <stdlib.h>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <sstream>
#include <iomanip>
#include <cctype>

#define STRINGIFY(x) #x
#define TOSTRING(x) STRINGIFY(x)

// Checks whether a value is an ASCII printable character
#define IS_ASCII_PRINTABLE_CHAR(x)   \
	(((unsigned int)(x) >= 0x20) &&  \
	( (unsigned int)(x) <= 0x7e))

// Checks whether a byte is an inner byte for an utf-8 multibyte sequence
#define IS_UTF8_MULTB_INNER(x)       \
	(((unsigned char)(x) >= 0x80) && \
	( (unsigned char)(x) <= 0xbf))

// Checks whether a byte is a start byte for an utf-8 multibyte sequence
#define IS_UTF8_MULTB_START(x)       \
	(((unsigned char)(x) >= 0xc2) && \
	( (unsigned char)(x) <= 0xf4))

// Given a start byte x for an utf-8 multibyte sequence
// it gives the length of the whole sequence in bytes.
#define UTF8_MULTB_START_LEN(x)            \
	(((unsigned char)(x) < 0xe0) ? 2 :     \
	(((unsigned char)(x) < 0xf0) ? 3 : 4))

typedef UNORDERED_MAP<std::string, std::string> StringMap;

struct FlagDesc {
	const char *name;
	u32 flag;
};

// try not to convert between wide/utf8 encodings; this can result in data loss
// try to only convert between them when you need to input/output stuff via Irrlicht
std::wstring utf8_to_wide(const std::string &input);
std::string wide_to_utf8(const std::wstring &input);

wchar_t *utf8_to_wide_c(const char *str);

// NEVER use those two functions unless you have a VERY GOOD reason to
// they just convert between wide and multibyte encoding
// multibyte encoding depends on current locale, this is no good, especially on Windows

// You must free the returned string!
// The returned string is allocated using new
wchar_t *narrow_to_wide_c(const char *str);
std::wstring narrow_to_wide(const std::string &mbs);
std::string wide_to_narrow(const std::wstring &wcs);

std::string urlencode(const std::string &str);
std::string urldecode(const std::string &str);
u32 readFlagString(std::string str, const FlagDesc *flagdesc, u32 *flagmask);
std::string writeFlagString(u32 flags, const FlagDesc *flagdesc, u32 flagmask);
size_t mystrlcpy(char *dst, const char *src, size_t size);
char *mystrtok_r(char *s, const char *sep, char **lasts);
u64 read_seed(const char *str);
bool parseColorString(const std::string &value, video::SColor &color, bool quiet);

/**
 * Returns a copy of \p str with spaces inserted at the right hand side to ensure
 * that the string is \p len characters in length. If \p str is <= \p len then the
 * returned string will be identical to str.
 */
inline std::string padStringRight(std::string str, size_t len)
{
	if (len > str.size())
		str.insert(str.end(), len - str.size(), ' ');

	return str;
}

/**
 * Returns a version of \p str with the first occurrence of a string
 * contained within ends[] removed from the end of the string.
 *
 * @param str
 * @param ends A NULL- or ""- terminated array of strings to remove from s in
 *	the copy produced.  Note that once one of these strings is removed
 *	that no further postfixes contained within this array are removed.
 *
 * @return If no end could be removed then "" is returned.
 */
inline std::string removeStringEnd(const std::string &str,
		const char *ends[])
{
	const char **p = ends;

	for (; *p && (*p)[0] != '\0'; p++) {
		std::string end = *p;
		if (str.size() < end.size())
			continue;
		if (str.compare(str.size() - end.size(), end.size(), end) == 0)
			return str.substr(0, str.size() - end.size());
	}

	return "";
}

/**
 * Check two strings for equivalence.  If \p case_insensitive is true
 * then the case of the strings is ignored (default is false).
 *
 * @param s1
 * @param s2
 * @param case_insensitive
 * @return true if the strings match
 */
template <typename T>
inline bool str_equal(const std::basic_string<T> &s1,
		const std::basic_string<T> &s2,
		bool case_insensitive = false)
{
	if (!case_insensitive)
		return s1 == s2;

	if (s1.size() != s2.size())
		return false;

	for (size_t i = 0; i < s1.size(); ++i)
		if(tolower(s1[i]) != tolower(s2[i]))
			return false;

	return true;
}

/**
 * Check whether \p str begins with the string prefix. If \p case_insensitive
 * is true then the check is case insensitve (default is false; i.e. case is
 * significant).
 *
 * @param str
 * @param prefix
 * @param case_insensitive
 * @return true if the str begins with prefix
 */
template <typename T>
inline bool str_starts_with(const std::basic_string<T> &str,
		const std::basic_string<T> &prefix,
		bool case_insensitive = false)
{
	if (str.size() < prefix.size())
		return false;

	if (!case_insensitive)
		return str.compare(0, prefix.size(), prefix) == 0;

	for (size_t i = 0; i < prefix.size(); ++i)
		if (tolower(str[i]) != tolower(prefix[i]))
			return false;
	return true;
}

/**
 * Check whether \p str begins with the string prefix. If \p case_insensitive
 * is true then the check is case insensitve (default is false; i.e. case is
 * significant).
 *
 * @param str
 * @param prefix
 * @param case_insensitive
 * @return true if the str begins with prefix
 */
template <typename T>
inline bool str_starts_with(const std::basic_string<T> &str,
		const T *prefix,
		bool case_insensitive = false)
{
	return str_starts_with(str, std::basic_string<T>(prefix),
			case_insensitive);
}

/**
 * Splits a string into its component parts separated by the character
 * \p delimiter.
 *
 * @return An std::vector<std::basic_string<T> > of the component parts
 */
template <typename T>
inline std::vector<std::basic_string<T> > str_split(
		const std::basic_string<T> &str,
		T delimiter)
{
	std::vector<std::basic_string<T> > parts;
	std::basic_stringstream<T> sstr(str);
	std::basic_string<T> part;

	while (std::getline(sstr, part, delimiter))
		parts.push_back(part);

	return parts;
}

/**
 * @param str
 * @return A copy of \p str converted to all lowercase characters.
 */
inline std::string lowercase(const std::string &str)
{
	std::string s2 = "";

	s2.reserve(str.size());

	for (size_t i = 0; i < str.size(); i++)
		s2 += tolower(str[i]);

	return s2;
}

/**
 * @param str
 * @return A copy of \p str with leading and trailing whitespace removed.
 */
inline std::string trim(const std::string &str)
{
	size_t front = 0;

	while (std::isspace(str[front]))
		++front;

	size_t back = str.size();
	while (back > front && std::isspace(str[back - 1]))
		--back;

	return str.substr(front, back - front);
}

/**
 * Returns whether \p str should be regarded as (bool) true.  Case and leading
 * and trailing whitespace are ignored.  Values that will return
 * true are "y", "yes", "true" and any number that is not 0.
 * @param str
 */
inline bool is_yes(const std::string &str)
{
	std::string s2 = lowercase(trim(str));

	return s2 == "y" || s2 == "yes" || s2 == "true" || atoi(s2.c_str()) != 0;
}

/**
 * Converts the string \p str to a signed 32-bit integer. The converted value
 * is constrained so that min <= value <= max.
 *
 * @see atoi(3) for limitations
 *
 * @param str
 * @param min Range minimum
 * @param max Range maximum
 * @return The value converted to a signed 32-bit integer and constrained
 *	within the range defined by min and max (inclusive)
 */
inline s32 mystoi(const std::string &str, s32 min, s32 max)
{
	s32 i = atoi(str.c_str());

	if (i < min)
		i = min;
	if (i > max)
		i = max;

	return i;
}

// MSVC2010 includes it's own versions of these
//#if !defined(_MSC_VER) || _MSC_VER < 1600

/**
 * Returns a 32-bit value reprensented by the string \p str (decimal).
 * @see atoi(3) for further limitations
 */
inline s32 mystoi(const std::string &str)
{
	return atoi(str.c_str());
}

/**
 * Returns s 32-bit value represented by the wide string \p str (decimal).
 * @see atoi(3) for further limitations
 */
inline s32 mystoi(const std::wstring &str)
{
	return mystoi(wide_to_narrow(str));
}

/**
 * Returns a float reprensented by the string \p str (decimal).
 * @see atof(3)
 */
inline float mystof(const std::string &str)
{
	return atof(str.c_str());
}

//#endif

#define stoi mystoi
#define stof mystof

/// Returns a value represented by the string \p val.
template <typename T>
inline T from_string(const std::string &str)
{
	std::stringstream tmp(str);
	T t;
	tmp >> t;
	return t;
}

/// Returns a 64-bit signed value represented by the string \p str (decimal).
inline s64 stoi64(const std::string &str) { return from_string<s64>(str); }

#if __cplusplus < 201103L
namespace std {

/// Returns a string representing the value \p val.
template <typename T>
inline string to_string(T val)
{
	ostringstream oss;
	oss << val;
	return oss.str();
}
#define DEFINE_STD_TOSTRING_FLOATINGPOINT(T)		\
	template <>					\
	inline string to_string<T>(T val)		\
	{						\
		ostringstream oss;			\
		oss << std::fixed			\
			<< std::setprecision(6)		\
			<< val;				\
		return oss.str();			\
	}
DEFINE_STD_TOSTRING_FLOATINGPOINT(float)
DEFINE_STD_TOSTRING_FLOATINGPOINT(double)
DEFINE_STD_TOSTRING_FLOATINGPOINT(long double)

#undef DEFINE_STD_TOSTRING_FLOATINGPOINT

/// Returns a wide string representing the value \p val
template <typename T>
inline wstring to_wstring(T val)
{
      return utf8_to_wide(to_string(val));
}
}
#endif

/// Returns a string representing the decimal value of the 32-bit value \p i.
inline std::string itos(s32 i) { return std::to_string(i); }
/// Returns a string representing the decimal value of the 64-bit value \p i.
inline std::string i64tos(s64 i) { return std::to_string(i); }

// std::to_string uses the '%.6f' conversion, which is inconsistent with
// std::ostream::operator<<() and impractical too.  ftos() uses the
// more generic and std::ostream::operator<<()-compatible '%G' format.
/// Returns a string representing the decimal value of the float value \p f.
inline std::string ftos(float f)
{
	std::ostringstream oss;
	oss << f;
	return oss.str();
}

/**
 * Replace all occurrences of \p pattern in \p str with \p replacement.
 *
 * @param str String to replace pattern with replacement within.
 * @param pattern The pattern to replace.
 * @param replacement What to replace the pattern with.
 */
inline void str_replace(std::string &str, const std::string &pattern,
		const std::string &replacement)
{
	std::string::size_type start = str.find(pattern, 0);
	while (start != str.npos) {
		str.replace(start, pattern.size(), replacement);
		start = str.find(pattern, start + replacement.size());
	}
}

/**
 * Escapes characters [ ] \ , ; that can not be used in formspecs
 */
inline void str_formspec_escape(std::string &str)
{
	str_replace(str, "\\", "\\\\");
	str_replace(str, "]", "\\]");
	str_replace(str, "[", "\\[");
	str_replace(str, ";", "\\;");
	str_replace(str, ",", "\\,");
}

/**
 * Replace all occurrences of the character \p from in \p str with \p to.
 *
 * @param str The string to (potentially) modify.
 * @param from The character in str to replace.
 * @param to The replacement character.
 */
void str_replace(std::string &str, char from, char to);

/**
 * Check that a string only contains whitelisted characters. This is the
 * opposite of string_allowed_blacklist().
 *
 * @param str The string to be checked.
 * @param allowed_chars A string containing permitted characters.
 * @return true if the string is allowed, otherwise false.
 *
 * @see string_allowed_blacklist()
 */
inline bool string_allowed(const std::string &str, const std::string &allowed_chars)
{
	return str.find_first_not_of(allowed_chars) == str.npos;
}

/**
 * Check that a string contains no blacklisted characters. This is the
 * opposite of string_allowed().
 *
 * @param str The string to be checked.
 * @param blacklisted_chars A string containing prohibited characters.
 * @return true if the string is allowed, otherwise false.

 * @see string_allowed()
 */
inline bool string_allowed_blacklist(const std::string &str,
		const std::string &blacklisted_chars)
{
	return str.find_first_of(blacklisted_chars) == str.npos;
}

/**
 * Create a string based on \p from where a newline is forcefully inserted
 * every \p row_len characters.
 *
 * @note This function does not honour word wraps and blindy inserts a newline
 *	every \p row_len characters whether it breaks a word or not.  It is
 *	intended to be used for, for example, showing paths in the GUI.
 *
 * @note This function doesn't wrap inside utf-8 multibyte sequences and also
 * 	counts multibyte sequences correcly as single characters.
 *
 * @param from The (utf-8) string to be wrapped into rows.
 * @param row_len The row length (in characters).
 * @return A new string with the wrapping applied.
 */
inline std::string wrap_rows(const std::string &from,
		unsigned row_len)
{
	std::string to;

	size_t character_idx = 0;
	for (size_t i = 0; i < from.size(); i++) {
		if (!IS_UTF8_MULTB_INNER(from[i])) {
			// Wrap string after last inner byte of char
			if (character_idx > 0 && character_idx % row_len == 0)
				to += '\n';
			character_idx++;
		}
		to += from[i];
	}

	return to;
}

/**
 * Removes backslashes from an escaped string (FormSpec strings)
 */
template <typename T>
inline std::basic_string<T> unescape_string(const std::basic_string<T> &s)
{
	std::basic_string<T> res;

	for (size_t i = 0; i < s.length(); i++) {
		if (s[i] == '\\') {
			i++;
			if (i >= s.length())
				break;
		}
		res += s[i];
	}

	return res;
}

/**
 * Remove all escape sequences in \p s.
 *
 * @param s The string in which to remove escape sequences.
 * @return \p s, with escape sequences removed.
 */
template <typename T>
std::basic_string<T> unescape_enriched(const std::basic_string<T> &s)
{
	std::basic_string<T> output;
	size_t i = 0;
	while (i < s.length()) {
		if (s[i] == '\x1b') {
			++i;
			if (i == s.length()) continue;
			if (s[i] == '(') {
				++i;
				while (i < s.length() && s[i] != ')') {
					if (s[i] == '\\') {
						++i;
					}
					++i;
				}
				++i;
			} else {
				++i;
			}
			continue;
		}
		output += s[i];
		++i;
	}
	return output;
}

template <typename T>
std::vector<std::basic_string<T> > split(const std::basic_string<T> &s, T delim)
{
	std::vector<std::basic_string<T> > tokens;

	std::basic_string<T> current;
	bool last_was_escape = false;
	for (size_t i = 0; i < s.length(); i++) {
		T si = s[i];
		if (last_was_escape) {
			current += '\\';
			current += si;
			last_was_escape = false;
		} else {
			if (si == delim) {
				tokens.push_back(current);
				current = std::basic_string<T>();
				last_was_escape = false;
			} else if (si == '\\') {
				last_was_escape = true;
			} else {
				current += si;
				last_was_escape = false;
			}
		}
	}
	//push last element
	tokens.push_back(current);

	return tokens;
}

/**
 * Checks that all characters in \p to_check are a decimal digits.
 *
 * @param to_check
 * @return true if to_check is not empty and all characters in to_check are
 *	decimal digits, otherwise false
 */
inline bool is_number(const std::string &to_check)
{
	for (size_t i = 0; i < to_check.size(); i++)
		if (!std::isdigit(to_check[i]))
			return false;

	return !to_check.empty();
}

/**
 * Returns a C-string, either "true" or "false", corresponding to \p val.
 *
 * @return If \p val is true, then "true" is returned, otherwise "false".
 */
inline const char *bool_to_cstr(bool val)
{
	return val ? "true" : "false";
}

inline const std::string duration_to_string(int sec)
{
	int min = sec / 60;
	sec %= 60;
	int hour = min / 60;
	min %= 60;

	std::stringstream ss;
	if (hour > 0) {
		ss << hour << "h ";
	}

	if (min > 0) {
		ss << min << "m ";
	}

	if (sec > 0) {
		ss << sec << "s ";
	}

	return ss.str();
}

#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_THREAD_HEADER
#define UTIL_THREAD_HEADER

#include "../irrlichttypes.h"
#include "../threading/thread.h"
#include "../threading/mutex.h"
#include "../threading/mutex_auto_lock.h"
#include "porting.h"
#include "log.h"
#include "container.h"

template<typename T>
class MutexedVariable
{
public:
	MutexedVariable(const T &value):
		m_value(value)
	{}

	T get()
	{
		MutexAutoLock lock(m_mutex);
		return m_value;
	}

	void set(const T &value)
	{
		MutexAutoLock lock(m_mutex);
		m_value = value;
	}

	// You pretty surely want to grab the lock when accessing this
	T m_value;
private:
	Mutex m_mutex;
};

/*
	A single worker thread - multiple client threads queue framework.
*/
template<typename Key, typename T, typename Caller, typename CallerData>
class GetResult {
public:
	Key key;
	T item;
	std::pair<Caller, CallerData> caller;
};

template<typename Key, typename T, typename Caller, typename CallerData>
class ResultQueue : public MutexedQueue<GetResult<Key, T, Caller, CallerData> > {
};

template<typename Caller, typename Data, typename Key, typename T>
class CallerInfo {
public:
	Caller caller;
	Data data;
	ResultQueue<Key, T, Caller, Data> *dest;
};

template<typename Key, typename T, typename Caller, typename CallerData>
class GetRequest {
public:
	GetRequest() {}
	~GetRequest() {}

	GetRequest(const Key &a_key): key(a_key)
	{
	}

	Key key;
	std::list<CallerInfo<Caller, CallerData, Key, T> > callers;
};

/**
 * Notes for RequestQueue usage
 * @param Key unique key to identify a request for a specific resource
 * @param T ?
 * @param Caller unique id of calling thread
 * @param CallerData data passed back to caller
 */
template<typename Key, typename T, typename Caller, typename CallerData>
class RequestQueue {
public:
	bool empty()
	{
		return m_queue.empty();
	}

	void add(const Key &key, Caller caller, CallerData callerdata,
		ResultQueue<Key, T, Caller, CallerData> *dest)
	{
		typename std::deque<GetRequest<Key, T, Caller, CallerData> >::iterator i;
		typename std::list<CallerInfo<Caller, CallerData, Key, T> >::iterator j;

		{
			MutexAutoLock lock(m_queue.getMutex());

			/*
				If the caller is already on the list, only update CallerData
			*/
			for (i = m_queue.getQueue().begin(); i != m_queue.getQueue().end(); ++i) {
				GetRequest<Key, T, Caller, CallerData> &request = *i;
				if (request.key != key)
					continue;

				for (j = request.callers.begin(); j != request.callers.end(); ++j) {
					CallerInfo<Caller, CallerData, Key, T> &ca = *j;
					if (ca.caller == caller) {
						ca.data = callerdata;
						return;
					}
				}

				CallerInfo<Caller, CallerData, Key, T> ca;
				ca.caller = caller;
				ca.data = callerdata;
				ca.dest = dest;
				request.callers.push_back(ca);
				return;
			}
		}

		/*
			Else add a new request to the queue
		*/

		GetRequest<Key, T, Caller, CallerData> request;
		request.key = key;
		CallerInfo<Caller, CallerData, Key, T> ca;
		ca.caller = caller;
		ca.data = callerdata;
		ca.dest = dest;
		request.callers.push_back(ca);

		m_queue.push_back(request);
	}

	GetRequest<Key, T, Caller, CallerData> pop(unsigned int timeout_ms)
	{
		return m_queue.pop_front(timeout_ms);
	}

	GetRequest<Key, T, Caller, CallerData> pop()
	{
		return m_queue.pop_frontNoEx();
	}

	void pushResult(GetRequest<Key, T, Caller, CallerData> req, T res)
	{
		for (typename std::list<CallerInfo<Caller, CallerData, Key, T> >::iterator
				i = req.callers.begin();
				i != req.callers.end(); ++i) {
			CallerInfo<Caller, CallerData, Key, T> &ca = *i;

			GetResult<Key,T,Caller,CallerData> result;

			result.key = req.key;
			result.item = res;
			result.caller.first = ca.caller;
			result.caller.second = ca.data;

			ca.dest->push_back(result);
		}
	}

private:
	MutexedQueue<GetRequest<Key, T, Caller, CallerData> > m_queue;
};

class UpdateThread : public Thread
{
public:
	UpdateThread(const std::string &name) : Thread(name + "Update") {}
	~UpdateThread() {}

	void deferUpdate() { m_update_sem.post(); }

	void stop()
	{
		Thread::stop();

		// give us a nudge
		m_update_sem.post();
	}

	void *run()
	{
		DSTACK(FUNCTION_NAME);
		BEGIN_DEBUG_EXCEPTION_HANDLER

		while (!stopRequested()) {
			m_update_sem.wait();
			// Set semaphore to 0
			while (m_update_sem.wait(0));

			if (stopRequested()) break;

			doUpdate();
		}

		END_DEBUG_EXCEPTION_HANDLER

		return NULL;
	}

protected:
	virtual void doUpdate() = 0;

private:
	Semaphore m_update_sem;
};

#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 "timetaker.h"

#include "../porting.h"
#include "../log.h"
#include <ostream>

TimeTaker::TimeTaker(const std::string &name, u64 *result, TimePrecision prec)
{
	m_name = name;
	m_result = result;
	m_running = true;
	m_precision = prec;
	m_time1 = porting::getTime(prec);
}

u64 TimeTaker::stop(bool quiet)
{
	if (m_running) {
		u64 dtime = porting::getTime(m_precision) - m_time1;
		if (m_result != NULL) {
			(*m_result) += dtime;
		} else {
			if (!quiet) {
				static const char* const units[] = {
					"s"  /* PRECISION_SECONDS */,
					"ms" /* PRECISION_MILLI */,
					"us" /* PRECISION_MICRO */,
					"ns" /* PRECISION_NANO */,
				};
				infostream << m_name << " took "
				           << dtime << units[m_precision]
					   << std::endl;
			}
		}
		m_running = false;
		return dtime;
	}
	return 0;
}

u64 TimeTaker::getTimerTime()
{
	return porting::getTime(m_precision) - m_time1;
}


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_TIMETAKER_HEADER
#define UTIL_TIMETAKER_HEADER

#include "../irrlichttypes.h"
#include "../gettime.h"

/*
	TimeTaker
*/

class TimeTaker
{
public:
	TimeTaker(const std::string &name, u64 *result=NULL,
		TimePrecision prec=PRECISION_MILLI);

	~TimeTaker()
	{
		stop();
	}

	u64 stop(bool quiet=false);

	u64 getTimerTime();

private:
	std::string m_name;
	u64 m_time1;
	bool m_running;
	TimePrecision m_precision;
	u64 *m_result;
};

#endif


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 "version.h"
#include "config.h"

#if defined(__ANDROID__)
	#include "android_version.h"
	#include "android_version_githash.h"
#elif defined(USE_CMAKE_CONFIG_H)
	#include "cmake_config_githash.h"
#endif

#ifndef VERSION_GITHASH
	#define VERSION_GITHASH VERSION_STRING
#endif

const char *g_version_string = VERSION_STRING;
const char *g_version_hash = VERSION_GITHASH;
const char *g_build_info = "VER=" VERSION_GITHASH " " BUILD_INFO;


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

#ifndef VERSION_HEADER
#define VERSION_HEADER

extern const char *g_version_string;
extern const char *g_version_hash;
extern const char *g_build_info;

#endif


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 "voxel.h"
#include "map.h"
#include "gettime.h"
#include "nodedef.h"
#include "util/timetaker.h"
#include <string.h>  // memcpy, memset

/*
	Debug stuff
*/
u64 addarea_time = 0;
u64 emerge_time = 0;
u64 emerge_load_time = 0;
u64 clearflag_time = 0;

VoxelManipulator::VoxelManipulator():
	m_data(NULL),
	m_flags(NULL)
{
}

VoxelManipulator::~VoxelManipulator()
{
	clear();
}

void VoxelManipulator::clear()
{
	// Reset area to volume=0
	m_area = VoxelArea();
	delete[] m_data;
	m_data = NULL;
	delete[] m_flags;
	m_flags = NULL;
}

void VoxelManipulator::print(std::ostream &o, INodeDefManager *ndef,
		VoxelPrintMode mode)
{
	v3s16 em = m_area.getExtent();
	v3s16 of = m_area.MinEdge;
	o<<"size: "<<em.X<<"x"<<em.Y<<"x"<<em.Z
	 <<" offset: ("<<of.X<<","<<of.Y<<","<<of.Z<<")"<<std::endl;

	for(s32 y=m_area.MaxEdge.Y; y>=m_area.MinEdge.Y; y--)
	{
		if(em.X >= 3 && em.Y >= 3)
		{
			if     (y==m_area.MinEdge.Y+2) o<<"^     ";
			else if(y==m_area.MinEdge.Y+1) o<<"|     ";
			else if(y==m_area.MinEdge.Y+0) o<<"y x-> ";
			else                           o<<"      ";
		}

		for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
		{
			for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
			{
				u8 f = m_flags[m_area.index(x,y,z)];
				char c;
				if(f & VOXELFLAG_NO_DATA)
					c = 'N';
				else
				{
					c = 'X';
					MapNode n = m_data[m_area.index(x,y,z)];
					content_t m = n.getContent();
					u8 pr = n.param2;
					if(mode == VOXELPRINT_MATERIAL)
					{
						if(m <= 9)
							c = m + '0';
					}
					else if(mode == VOXELPRINT_WATERPRESSURE)
					{
						if(ndef->get(m).isLiquid())
						{
							c = 'w';
							if(pr <= 9)
								c = pr + '0';
						}
						else if(m == CONTENT_AIR)
						{
							c = ' ';
						}
						else
						{
							c = '#';
						}
					}
					else if(mode == VOXELPRINT_LIGHT_DAY)
					{
						if(ndef->get(m).light_source != 0)
							c = 'S';
						else if(ndef->get(m).light_propagates == false)
							c = 'X';
						else
						{
							u8 light = n.getLight(LIGHTBANK_DAY, ndef);
							if(light < 10)
								c = '0' + light;
							else
								c = 'a' + (light-10);
						}
					}
				}
				o<<c;
			}
			o<<' ';
		}
		o<<std::endl;
	}
}

void VoxelManipulator::addArea(const VoxelArea &area)
{
	// Cancel if requested area has zero volume
	if (area.hasEmptyExtent())
		return;

	// Cancel if m_area already contains the requested area
	if(m_area.contains(area))
		return;

	TimeTaker timer("addArea", &addarea_time);

	// Calculate new area
	VoxelArea new_area;
	// New area is the requested area if m_area has zero volume
	if(m_area.hasEmptyExtent())
	{
		new_area = area;
	}
	// Else add requested area to m_area
	else
	{
		new_area = m_area;
		new_area.addArea(area);
	}

	s32 new_size = new_area.getVolume();

	/*dstream<<"adding area ";
	area.print(dstream);
	dstream<<", old area ";
	m_area.print(dstream);
	dstream<<", new area ";
	new_area.print(dstream);
	dstream<<", new_size="<<new_size;
	dstream<<std::endl;*/

	// Allocate new data and clear flags
	MapNode *new_data = new MapNode[new_size];
	assert(new_data);
	u8 *new_flags = new u8[new_size];
	assert(new_flags);
	memset(new_flags, VOXELFLAG_NO_DATA, new_size);

	// Copy old data
	s32 old_x_width = m_area.MaxEdge.X - m_area.MinEdge.X + 1;
	for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
	for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++)
	{
		unsigned int old_index = m_area.index(m_area.MinEdge.X,y,z);
		unsigned int new_index = new_area.index(m_area.MinEdge.X,y,z);

		memcpy(&new_data[new_index], &m_data[old_index],
				old_x_width * sizeof(MapNode));
		memcpy(&new_flags[new_index], &m_flags[old_index],
				old_x_width * sizeof(u8));
	}

	// Replace area, data and flags

	m_area = new_area;

	MapNode *old_data = m_data;
	u8 *old_flags = m_flags;

	/*dstream<<"old_data="<<(int)old_data<<", new_data="<<(int)new_data
	<<", old_flags="<<(int)m_flags<<", new_flags="<<(int)new_flags<<std::endl;*/

	m_data = new_data;
	m_flags = new_flags;

	delete[] old_data;
	delete[] old_flags;

	//dstream<<"addArea done"<<std::endl;
}

void VoxelManipulator::copyFrom(MapNode *src, const VoxelArea& src_area,
		v3s16 from_pos, v3s16 to_pos, v3s16 size)
{
	/* The reason for this optimised code is that we're a member function
	 * and the data type/layout of m_data is know to us: it's stored as
	 * [z*h*w + y*h + x]. Therefore we can take the calls to m_area index
	 * (which performs the preceding mapping/indexing of m_data) out of the
	 * inner loop and calculate the next index as we're iterating to gain
	 * performance.
	 *
	 * src_step and dest_step is the amount required to be added to our index
	 * every time y increments. Because the destination area may be larger
	 * than the source area we need one additional variable (otherwise we could
	 * just continue adding dest_step as is done for the source data): dest_mod.
	 * dest_mod is the difference in size between a "row" in the source data
	 * and a "row" in the destination data (I am using the term row loosely
	 * and for illustrative purposes). E.g.
	 *
	 * src       <-------------------->|'''''' dest mod ''''''''
	 * dest      <--------------------------------------------->
	 *
	 * dest_mod (it's essentially a modulus) is added to the destination index
	 * after every full iteration of the y span.
	 *
	 * This method falls under the category "linear array and incrementing
	 * index".
	 */

	s32 src_step = src_area.getExtent().X;
	s32 dest_step = m_area.getExtent().X;
	s32 dest_mod = m_area.index(to_pos.X, to_pos.Y, to_pos.Z + 1)
			- m_area.index(to_pos.X, to_pos.Y, to_pos.Z)
			- dest_step * size.Y;

	s32 i_src = src_area.index(from_pos.X, from_pos.Y, from_pos.Z);
	s32 i_local = m_area.index(to_pos.X, to_pos.Y, to_pos.Z);

	for (s16 z = 0; z < size.Z; z++) {
		for (s16 y = 0; y < size.Y; y++) {
			memcpy(&m_data[i_local], &src[i_src], size.X * sizeof(*m_data));
			memset(&m_flags[i_local], 0, size.X);
			i_src += src_step;
			i_local += dest_step;
		}
		i_local += dest_mod;
	}
}

void VoxelManipulator::copyTo(MapNode *dst, const VoxelArea& dst_area,
		v3s16 dst_pos, v3s16 from_pos, v3s16 size)
{
	for(s16 z=0; z<size.Z; z++)
	for(s16 y=0; y<size.Y; y++)
	{
		s32 i_dst = dst_area.index(dst_pos.X, dst_pos.Y+y, dst_pos.Z+z);
		s32 i_local = m_area.index(from_pos.X, from_pos.Y+y, from_pos.Z+z);
		for (s16 x = 0; x < size.X; x++) {
			if (m_data[i_local].getContent() != CONTENT_IGNORE)
				dst[i_dst] = m_data[i_local];
			i_dst++;
			i_local++;
		}
	}
}

/*
	Algorithms
	-----------------------------------------------------
*/

void VoxelManipulator::clearFlag(u8 flags)
{
	// 0-1ms on moderate area
	TimeTaker timer("clearFlag", &clearflag_time);

	//v3s16 s = m_area.getExtent();

	/*dstream<<"clearFlag clearing area of size "
			<<""<<s.X<<"x"<<s.Y<<"x"<<s.Z<<""
			<<std::endl;*/

	//s32 count = 0;

	/*for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
	for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++)
	for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
	{
		u8 f = m_flags[m_area.index(x,y,z)];
		m_flags[m_area.index(x,y,z)] &= ~flags;
		if(m_flags[m_area.index(x,y,z)] != f)
			count++;
	}*/

	s32 volume = m_area.getVolume();
	for(s32 i=0; i<volume; i++)
	{
		m_flags[i] &= ~flags;
	}

	/*s32 volume = m_area.getVolume();
	for(s32 i=0; i<volume; i++)
	{
		u8 f = m_flags[i];
		m_flags[i] &= ~flags;
		if(m_flags[i] != f)
			count++;
	}

	dstream<<"clearFlag changed "<<count<<" flags out of "
			<<volume<<" nodes"<<std::endl;*/
}

void VoxelManipulator::unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
		std::set<v3s16> & light_sources, INodeDefManager *nodemgr)
{
	v3s16 dirs[6] = {
		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
	};

	VoxelArea voxel_area(p - v3s16(1,1,1), p + v3s16(1,1,1));
	addArea(voxel_area);

	// Loop through 6 neighbors
	for(u16 i=0; i<6; i++)
	{
		// Get the position of the neighbor node
		v3s16 n2pos = p + dirs[i];

		u32 n2i = m_area.index(n2pos);

		if(m_flags[n2i] & VOXELFLAG_NO_DATA)
			continue;

		MapNode &n2 = m_data[n2i];

		/*
			If the neighbor is dimmer than what was specified
			as oldlight (the light of the previous node)
		*/
		u8 light2 = n2.getLight(bank, nodemgr);
		if(light2 < oldlight)
		{
			/*
				And the neighbor is transparent and it has some light
			*/
			if(nodemgr->get(n2).light_propagates && light2 != 0)
			{
				/*
					Set light to 0 and add to queue
				*/

				n2.setLight(bank, 0, nodemgr);

				unspreadLight(bank, n2pos, light2, light_sources, nodemgr);

				/*
					Remove from light_sources if it is there
					NOTE: This doesn't happen nearly at all
				*/
				/*if(light_sources.find(n2pos))
				{
					std::cout<<"Removed from light_sources"<<std::endl;
					light_sources.remove(n2pos);
				}*/
			}
		}
		else{
			light_sources.insert(n2pos);
		}
	}
}

/*
	Goes recursively through the neighbours of the node.

	Alters only transparent nodes.

	If the lighting of the neighbour is lower than the lighting of
	the node was (before changing it to 0 at the step before), the
	lighting of the neighbour is set to 0 and then the same stuff
	repeats for the neighbour.

	The ending nodes of the routine are stored in light_sources.
	This is useful when a light is removed. In such case, this
	routine can be called for the light node and then again for
	light_sources to re-light the area without the removed light.

	values of from_nodes are lighting values.
*/
void VoxelManipulator::unspreadLight(enum LightBank bank,
		std::map<v3s16, u8> & from_nodes,
		std::set<v3s16> & light_sources, INodeDefManager *nodemgr)
{
	if(from_nodes.empty())
		return;

	for(std::map<v3s16, u8>::iterator j = from_nodes.begin();
		j != from_nodes.end(); ++j)
	{
		unspreadLight(bank, j->first, j->second, light_sources, nodemgr);
	}
}

void VoxelManipulator::spreadLight(enum LightBank bank, v3s16 p,
		INodeDefManager *nodemgr)
{
	const v3s16 dirs[6] = {
		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
	};

	VoxelArea voxel_area(p - v3s16(1,1,1), p + v3s16(1,1,1));
	addArea(voxel_area);

	u32 i = m_area.index(p);

	if(m_flags[i] & VOXELFLAG_NO_DATA)
		return;

	MapNode &n = m_data[i];

	u8 oldlight = n.getLight(bank, nodemgr);
	u8 newlight = diminish_light(oldlight);

	// Loop through 6 neighbors
	for(u16 i=0; i<6; i++)
	{
		// Get the position of the neighbor node
		v3s16 n2pos = p + dirs[i];

		u32 n2i = m_area.index(n2pos);

		if(m_flags[n2i] & VOXELFLAG_NO_DATA)
			continue;

		MapNode &n2 = m_data[n2i];

		u8 light2 = n2.getLight(bank, nodemgr);

		/*
			If the neighbor is brighter than the current node,
			add to list (it will light up this node on its turn)
		*/
		if(light2 > undiminish_light(oldlight))
		{
			spreadLight(bank, n2pos, nodemgr);
		}
		/*
			If the neighbor is dimmer than how much light this node
			would spread on it, add to list
		*/
		if(light2 < newlight)
		{
			if(nodemgr->get(n2).light_propagates)
			{
				n2.setLight(bank, newlight, nodemgr);
				spreadLight(bank, n2pos, nodemgr);
			}
		}
	}
}

const MapNode VoxelManipulator::ContentIgnoreNode = MapNode(CONTENT_IGNORE);

/*
	Lights neighbors of from_nodes, collects all them and then
	goes on recursively.
*/
void VoxelManipulator::spreadLight(enum LightBank bank,
		std::set<v3s16> & from_nodes, INodeDefManager *nodemgr)
{
	const v3s16 dirs[6] = {
		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
	};

	if(from_nodes.empty())
		return;

	std::set<v3s16> lighted_nodes;

	for(std::set<v3s16>::iterator j = from_nodes.begin();
		j != from_nodes.end(); ++j)
	{
		v3s16 pos = *j;

		VoxelArea voxel_area(pos - v3s16(1,1,1), pos + v3s16(1,1,1));
		addArea(voxel_area);

		u32 i = m_area.index(pos);

		if(m_flags[i] & VOXELFLAG_NO_DATA)
			continue;

		MapNode &n = m_data[i];

		u8 oldlight = n.getLight(bank, nodemgr);
		u8 newlight = diminish_light(oldlight);

		// Loop through 6 neighbors
		for(u16 i=0; i<6; i++)
		{
			// Get the position of the neighbor node
			v3s16 n2pos = pos + dirs[i];

			try
			{
				u32 n2i = m_area.index(n2pos);

				if(m_flags[n2i] & VOXELFLAG_NO_DATA)
					continue;

				MapNode &n2 = m_data[n2i];

				u8 light2 = n2.getLight(bank, nodemgr);

				/*
					If the neighbor is brighter than the current node,
					add to list (it will light up this node on its turn)
				*/
				if(light2 > undiminish_light(oldlight))
				{
					lighted_nodes.insert(n2pos);
				}
				/*
					If the neighbor is dimmer than how much light this node
					would spread on it, add to list
				*/
				if(light2 < newlight)
				{
					if(nodemgr->get(n2).light_propagates)
					{
						n2.setLight(bank, newlight, nodemgr);
						lighted_nodes.insert(n2pos);
					}
				}
			}
			catch(InvalidPositionException &e)
			{
				continue;
			}
		}
	}

	/*dstream<<"spreadLight(): Changed block "
			<<blockchangecount<<" times"
			<<" for "<<from_nodes.size()<<" nodes"
			<<std::endl;*/

	if(!lighted_nodes.empty())
		spreadLight(bank, lighted_nodes, nodemgr);
}

//END


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

#ifndef VOXEL_HEADER
#define VOXEL_HEADER

#include "irrlichttypes.h"
#include "irr_v3d.h"
#include <iostream>
#include "debug.h"
#include "exceptions.h"
#include "mapnode.h"
#include <set>
#include <list>
#include <map>

class INodeDefManager;

// For VC++
#undef min
#undef max

/*
	A fast voxel manipulator class.

	In normal operation, it fetches more map when it is requested.
	It can also be used so that all allowed area is fetched at the
	start, using ManualMapVoxelManipulator.

	Not thread-safe.
*/

/*
	Debug stuff
*/
extern u64 emerge_time;
extern u64 emerge_load_time;

/*
	This class resembles aabbox3d<s16> a lot, but has inclusive
	edges for saner handling of integer sizes
*/
class VoxelArea
{
public:
	// Starts as zero sized
	VoxelArea():
		MinEdge(1,1,1),
		MaxEdge(0,0,0)
	{
	}
	VoxelArea(v3s16 min_edge, v3s16 max_edge):
		MinEdge(min_edge),
		MaxEdge(max_edge)
	{
	}
	VoxelArea(v3s16 p):
		MinEdge(p),
		MaxEdge(p)
	{
	}

	/*
		Modifying methods
	*/

	void addArea(const VoxelArea &a)
	{
		if (hasEmptyExtent())
		{
			*this = a;
			return;
		}
		if(a.MinEdge.X < MinEdge.X) MinEdge.X = a.MinEdge.X;
		if(a.MinEdge.Y < MinEdge.Y) MinEdge.Y = a.MinEdge.Y;
		if(a.MinEdge.Z < MinEdge.Z) MinEdge.Z = a.MinEdge.Z;
		if(a.MaxEdge.X > MaxEdge.X) MaxEdge.X = a.MaxEdge.X;
		if(a.MaxEdge.Y > MaxEdge.Y) MaxEdge.Y = a.MaxEdge.Y;
		if(a.MaxEdge.Z > MaxEdge.Z) MaxEdge.Z = a.MaxEdge.Z;
	}
	void addPoint(const v3s16 &p)
	{
		if(hasEmptyExtent())
		{
			MinEdge = p;
			MaxEdge = p;
			return;
		}
		if(p.X < MinEdge.X) MinEdge.X = p.X;
		if(p.Y < MinEdge.Y) MinEdge.Y = p.Y;
		if(p.Z < MinEdge.Z) MinEdge.Z = p.Z;
		if(p.X > MaxEdge.X) MaxEdge.X = p.X;
		if(p.Y > MaxEdge.Y) MaxEdge.Y = p.Y;
		if(p.Z > MaxEdge.Z) MaxEdge.Z = p.Z;
	}

	// Pad with d nodes
	void pad(const v3s16 &d)
	{
		MinEdge -= d;
		MaxEdge += d;
	}

	/*void operator+=(v3s16 off)
	{
		MinEdge += off;
		MaxEdge += off;
	}

	void operator-=(v3s16 off)
	{
		MinEdge -= off;
		MaxEdge -= off;
	}*/

	/*
		const methods
	*/

	v3s16 getExtent() const
	{
		return MaxEdge - MinEdge + v3s16(1,1,1);
	}

	/* Because MaxEdge and MinEdge are included in the voxel area an empty extent
	 * is not represented by (0, 0, 0), but instead (-1, -1, -1)
	 */
	bool hasEmptyExtent() const
	{
		return MaxEdge - MinEdge == v3s16(-1, -1, -1);
	}

	s32 getVolume() const
	{
		v3s16 e = getExtent();
		return (s32)e.X * (s32)e.Y * (s32)e.Z;
	}
	bool contains(const VoxelArea &a) const
	{
		// No area contains an empty area
		// NOTE: Algorithms depend on this, so do not change.
		if(a.hasEmptyExtent())
			return false;

		return(
			a.MinEdge.X >= MinEdge.X && a.MaxEdge.X <= MaxEdge.X &&
			a.MinEdge.Y >= MinEdge.Y && a.MaxEdge.Y <= MaxEdge.Y &&
			a.MinEdge.Z >= MinEdge.Z && a.MaxEdge.Z <= MaxEdge.Z
		);
	}
	bool contains(v3s16 p) const
	{
		return(
			p.X >= MinEdge.X && p.X <= MaxEdge.X &&
			p.Y >= MinEdge.Y && p.Y <= MaxEdge.Y &&
			p.Z >= MinEdge.Z && p.Z <= MaxEdge.Z
		);
	}
	bool contains(s32 i) const
	{
		return (i >= 0 && i < getVolume());
	}
	bool operator==(const VoxelArea &other) const
	{
		return (MinEdge == other.MinEdge
				&& MaxEdge == other.MaxEdge);
	}

	VoxelArea operator+(v3s16 off) const
	{
		return VoxelArea(MinEdge+off, MaxEdge+off);
	}

	VoxelArea operator-(v3s16 off) const
	{
		return VoxelArea(MinEdge-off, MaxEdge-off);
	}

	/*
		Returns 0-6 non-overlapping areas that can be added to
		a to make up this area.

		a: area inside *this
	*/
	void diff(const VoxelArea &a, std::list<VoxelArea> &result)
	{
		/*
			This can result in a maximum of 6 areas
		*/

		// If a is an empty area, return the current area as a whole
		if(a.getExtent() == v3s16(0,0,0))
		{
			VoxelArea b = *this;
			if(b.getVolume() != 0)
				result.push_back(b);
			return;
		}

		assert(contains(a));	// pre-condition

		// Take back area, XY inclusive
		{
			v3s16 min(MinEdge.X, MinEdge.Y, a.MaxEdge.Z+1);
			v3s16 max(MaxEdge.X, MaxEdge.Y, MaxEdge.Z);
			VoxelArea b(min, max);
			if(b.getVolume() != 0)
				result.push_back(b);
		}

		// Take front area, XY inclusive
		{
			v3s16 min(MinEdge.X, MinEdge.Y, MinEdge.Z);
			v3s16 max(MaxEdge.X, MaxEdge.Y, a.MinEdge.Z-1);
			VoxelArea b(min, max);
			if(b.getVolume() != 0)
				result.push_back(b);
		}

		// Take top area, X inclusive
		{
			v3s16 min(MinEdge.X, a.MaxEdge.Y+1, a.MinEdge.Z);
			v3s16 max(MaxEdge.X, MaxEdge.Y, a.MaxEdge.Z);
			VoxelArea b(min, max);
			if(b.getVolume() != 0)
				result.push_back(b);
		}

		// Take bottom area, X inclusive
		{
			v3s16 min(MinEdge.X, MinEdge.Y, a.MinEdge.Z);
			v3s16 max(MaxEdge.X, a.MinEdge.Y-1, a.MaxEdge.Z);
			VoxelArea b(min, max);
			if(b.getVolume() != 0)
				result.push_back(b);
		}

		// Take left area, non-inclusive
		{
			v3s16 min(MinEdge.X, a.MinEdge.Y, a.MinEdge.Z);
			v3s16 max(a.MinEdge.X-1, a.MaxEdge.Y, a.MaxEdge.Z);
			VoxelArea b(min, max);
			if(b.getVolume() != 0)
				result.push_back(b);
		}

		// Take right area, non-inclusive
		{
			v3s16 min(a.MaxEdge.X+1, a.MinEdge.Y, a.MinEdge.Z);
			v3s16 max(MaxEdge.X, a.MaxEdge.Y, a.MaxEdge.Z);
			VoxelArea b(min, max);
			if(b.getVolume() != 0)
				result.push_back(b);
		}

	}

	/*
		Translates position from virtual coordinates to array index
	*/
	s32 index(s16 x, s16 y, s16 z) const
	{
		v3s16 em = getExtent();
		v3s16 off = MinEdge;
		s32 i = (s32)(z-off.Z)*em.Y*em.X + (y-off.Y)*em.X + (x-off.X);
		//dstream<<" i("<<x<<","<<y<<","<<z<<")="<<i<<" ";
		return i;
	}
	s32 index(v3s16 p) const
	{
		return index(p.X, p.Y, p.Z);
	}

	// Translate index in the X coordinate
	void add_x(const v3s16 &extent, u32 &i, s16 a)
	{
		i += a;
	}
	// Translate index in the Y coordinate
	void add_y(const v3s16 &extent, u32 &i, s16 a)
	{
		i += a * extent.X;
	}
	// Translate index in the Z coordinate
	void add_z(const v3s16 &extent, u32 &i, s16 a)
	{
		i += a * extent.X*extent.Y;
	}
	// Translate index in space
	void add_p(const v3s16 &extent, u32 &i, v3s16 a)
	{
		i += a.Z*extent.X*extent.Y + a.Y*extent.X + a.X;
	}

	/*
		Print method for debugging
	*/
	void print(std::ostream &o) const
	{
		v3s16 e = getExtent();
		o<<"("<<MinEdge.X
		 <<","<<MinEdge.Y
		 <<","<<MinEdge.Z
		 <<")("<<MaxEdge.X
		 <<","<<MaxEdge.Y
		 <<","<<MaxEdge.Z
		 <<")"
		 <<"="<<e.X<<"x"<<e.Y<<"x"<<e.Z<<"="<<getVolume();
	}

	// Edges are inclusive
	v3s16 MinEdge;
	v3s16 MaxEdge;
};

// unused
#define VOXELFLAG_UNUSED   (1<<0)
// no data about that node
#define VOXELFLAG_NO_DATA  (1<<1)
// Algorithm-dependent
#define VOXELFLAG_CHECKED1 (1<<2)
// Algorithm-dependent
#define VOXELFLAG_CHECKED2 (1<<3)
// Algorithm-dependent
#define VOXELFLAG_CHECKED3 (1<<4)
// Algorithm-dependent
#define VOXELFLAG_CHECKED4 (1<<5)

enum VoxelPrintMode
{
	VOXELPRINT_NOTHING,
	VOXELPRINT_MATERIAL,
	VOXELPRINT_WATERPRESSURE,
	VOXELPRINT_LIGHT_DAY,
};

class VoxelManipulator /*: public NodeContainer*/
{
public:
	VoxelManipulator();
	virtual ~VoxelManipulator();

	/*
		Virtuals from NodeContainer
	*/
	/*virtual u16 nodeContainerId() const
	{
		return NODECONTAINER_ID_VOXELMANIPULATOR;
	}
	bool isValidPosition(v3s16 p)
	{
		addArea(p);
		return !(m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA);
	}*/

	/*
		These are a bit slow and shouldn't be used internally.
		Use m_data[m_area.index(p)] instead.
	*/
	MapNode getNode(v3s16 p)
	{
		VoxelArea voxel_area(p);
		addArea(voxel_area);

		if(m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA)
		{
			/*dstream<<"EXCEPT: VoxelManipulator::getNode(): "
					<<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
					<<", index="<<m_area.index(p)
					<<", flags="<<(int)m_flags[m_area.index(p)]
					<<" is inexistent"<<std::endl;*/
			throw InvalidPositionException
			("VoxelManipulator: getNode: inexistent");
		}

		return m_data[m_area.index(p)];
	}
	MapNode getNodeNoEx(v3s16 p)
	{
		VoxelArea voxel_area(p);
		addArea(voxel_area);

		if(m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA)
		{
			return MapNode(CONTENT_IGNORE);
		}

		return m_data[m_area.index(p)];
	}
	MapNode getNodeNoExNoEmerge(v3s16 p)
	{
		if(m_area.contains(p) == false)
			return MapNode(CONTENT_IGNORE);
		if(m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA)
			return MapNode(CONTENT_IGNORE);
		return m_data[m_area.index(p)];
	}
	// Stuff explodes if non-emerged area is touched with this.
	// Emerge first, and check VOXELFLAG_NO_DATA if appropriate.
	MapNode & getNodeRefUnsafe(const v3s16 &p)
	{
		return m_data[m_area.index(p)];
	}

	const MapNode & getNodeRefUnsafeCheckFlags(const v3s16 &p)
	{
		s32 index = m_area.index(p);

		if (m_flags[index] & VOXELFLAG_NO_DATA)
			return ContentIgnoreNode;

		return m_data[index];
	}

	u8 & getFlagsRefUnsafe(v3s16 p)
	{
		return m_flags[m_area.index(p)];
	}
	bool exists(v3s16 p)
	{
		return m_area.contains(p) &&
			!(getFlagsRefUnsafe(p) & VOXELFLAG_NO_DATA);
	}
	MapNode & getNodeRef(v3s16 p)
	{
		VoxelArea voxel_area(p);
		addArea(voxel_area);
		if(getFlagsRefUnsafe(p) & VOXELFLAG_NO_DATA)
		{
			/*dstream<<"EXCEPT: VoxelManipulator::getNode(): "
					<<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
					<<", index="<<m_area.index(p)
					<<", flags="<<(int)getFlagsRefUnsafe(p)
					<<" is inexistent"<<std::endl;*/
			throw InvalidPositionException
			("VoxelManipulator: getNode: inexistent");
		}
		return getNodeRefUnsafe(p);
	}
	void setNode(v3s16 p, const MapNode &n)
	{
		VoxelArea voxel_area(p);
		addArea(voxel_area);

		m_data[m_area.index(p)] = n;
		m_flags[m_area.index(p)] &= ~VOXELFLAG_NO_DATA;
	}
	// TODO: Should be removed and replaced with setNode
	void setNodeNoRef(v3s16 p, const MapNode &n)
	{
		setNode(p, n);
	}

	/*void setExists(VoxelArea a)
	{
		addArea(a);
		for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
		for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
		for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
		{
			m_flags[m_area.index(x,y,z)] &= ~VOXELFLAG_NO_DATA;
		}
	}*/

	/*MapNode & operator[](v3s16 p)
	{
		//dstream<<"operator[] p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
		if(isValidPosition(p) == false)
			addArea(VoxelArea(p));

		return m_data[m_area.index(p)];
	}*/

	/*
		Set stuff if available without an emerge.
		Return false if failed.
		This is convenient but slower than playing around directly
		with the m_data table with indices.
	*/
	bool setNodeNoEmerge(v3s16 p, MapNode n)
	{
		if(m_area.contains(p) == false)
			return false;
		m_data[m_area.index(p)] = n;
		return true;
	}
	bool setNodeNoEmerge(s32 i, MapNode n)
	{
		if(m_area.contains(i) == false)
			return false;
		m_data[i] = n;
		return true;
	}
	/*bool setContentNoEmerge(v3s16 p, u8 c)
	{
		if(isValidPosition(p) == false)
			return false;
		m_data[m_area.index(p)].d = c;
	}*/

	/*
		Control
	*/

	virtual void clear();

	void print(std::ostream &o, INodeDefManager *nodemgr,
			VoxelPrintMode mode=VOXELPRINT_MATERIAL);

	void addArea(const VoxelArea &area);

	/*
		Copy data and set flags to 0
		dst_area.getExtent() <= src_area.getExtent()
	*/
	void copyFrom(MapNode *src, const VoxelArea& src_area,
			v3s16 from_pos, v3s16 to_pos, v3s16 size);

	// Copy data
	void copyTo(MapNode *dst, const VoxelArea& dst_area,
			v3s16 dst_pos, v3s16 from_pos, v3s16 size);

	/*
		Algorithms
	*/

	void clearFlag(u8 flag);

	// TODO: Move to voxelalgorithms.h

	void unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
			std::set<v3s16> & light_sources, INodeDefManager *nodemgr);
	void unspreadLight(enum LightBank bank,
			std::map<v3s16, u8> & from_nodes,
			std::set<v3s16> & light_sources, INodeDefManager *nodemgr);

	void spreadLight(enum LightBank bank, v3s16 p, INodeDefManager *nodemgr);
	void spreadLight(enum LightBank bank,
			std::set<v3s16> & from_nodes, INodeDefManager *nodemgr);

	/*
		Virtual functions
	*/

	/*
		Member variables
	*/

	/*
		The area that is stored in m_data.
		addInternalBox should not be used if getExtent() == v3s16(0,0,0)
		MaxEdge is 1 higher than maximum allowed position
	*/
	VoxelArea m_area;

	/*
		NULL if data size is 0 (extent (0,0,0))
		Data is stored as [z*h*w + y*h + x]
	*/
	MapNode *m_data;

	/*
		Flags of all nodes
	*/
	u8 *m_flags;

	static const MapNode ContentIgnoreNode;

	//TODO: Use these or remove them
	//TODO: Would these make any speed improvement?
	//bool m_pressure_route_valid;
	//v3s16 m_pressure_route_surface;

	/*
		Some settings
	*/
	//bool m_disable_water_climb;

private:
};

#endif