/* $Id$ */

/*
 * This file is part of OpenTTD.
 * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
 * OpenTTD 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 General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
 */

/** @file strings.cpp Handling of translated strings. */

#include "stdafx.h"
#include "currency.h"
#include "station_base.h"
#include "town.h"
#include "screenshot.h"
#include "waypoint_base.h"
#include "depot_base.h"
#include "industry.h"
#include "newgrf_text.h"
#include "fileio_func.h"
#include "group.h"
#include "signs_base.h"
#include "cargotype.h"
#include "fontcache.h"
#include "gui.h"
#include "strings_func.h"
#include "rev.h"
#include "core/alloc_type.hpp"
#include "core/endian_func.hpp"
#include "date_func.h"
#include "vehicle_base.h"
#include "engine_base.h"
#include "language.h"
#include "townname_func.h"
#include "string_func.h"
#include "company_base.h"
#include "smallmap_gui.h"
#include "window_func.h"
#include "debug.h"
#include <stack>

#include "table/strings.h"
#include "table/control_codes.h"

char _config_language_file[MAX_PATH];             ///< The file (name) stored in the configuration.
LanguageList _languages;                          ///< The actual list of language meta data.
const LanguageMetadata *_current_language = NULL; ///< The currently loaded language.

TextDirection _current_text_dir; ///< Text direction of the currently selected language.

#ifdef WITH_ICU
Collator *_current_collator = NULL;               ///< Collator for the language currently in use.
#endif /* WITH_ICU */

static uint64 _global_string_params_data[20];     ///< Global array of string parameters. To access, use #SetDParam.
static WChar _global_string_params_type[20];      ///< Type of parameters stored in #_decode_parameters
StringParameters _global_string_params(_global_string_params_data, 20, _global_string_params_type);

/** Reset the type array. */
void StringParameters::ClearTypeInformation()
{
	assert(this->type != NULL);
	MemSetT(this->type, 0, this->num_param);
}

/**
 * Shift all data in the data array by the given amount to make
 * room for some extra parameters.
 */
void StringParameters::ShiftParameters(uint amount)
{
	assert(amount <= this->num_param);
	MemMoveT(this->data + amount, this->data, this->num_param - amount);
}

/**
 * Copy \a num string parameters from array \a src into the global string parameter array.
 * @param offs Index in the global array to copy the first string parameter to.
 * @param src  Source array of string parameters.
 * @param num  Number of string parameters to copy.
 */
void CopyInDParam(int offs, const uint64 *src, int num)
{
	MemCpyT(_global_string_params.GetPointerToOffset(offs), src, num);
}

/**
 * Copy \a num string parameters from the global string parameter array to the \a dst array.
 * @param dst  Destination array of string parameters.
 * @param offs Index in the global array to copy the first string parameter from.
 * @param num  Number of string parameters to copy.
 */
void CopyOutDParam(uint64 *dst, int offs, int num)
{
	MemCpyT(dst, _global_string_params.GetPointerToOffset(offs), num);
}

static char *StationGetSpecialString(char *buff, int x, const char *last);
static char *GetSpecialTownNameString(char *buff, int ind, uint32 seed, const char *last);
static char *GetSpecialNameString(char *buff, int ind, StringParameters *args, const char *last);

static char *FormatString(char *buff, const char *str, StringParameters *args, uint case_index, const char *last, bool dry_run = false);

struct LanguagePack : public LanguagePackHeader {
	char data[]; // list of strings
};

static char **_langpack_offs;
static LanguagePack *_langpack;
static uint _langtab_num[32];   ///< Offset into langpack offs
static uint _langtab_start[32]; ///< Offset into langpack offs
static bool _keep_gender_data = false;  ///< Should we retain the gender data in the current string?


const char *GetStringPtr(StringID string)
{
	switch (GB(string, 11, 5)) {
		/* GetGRFStringPtr doesn't handle 0xD4xx ids, we need to convert those to 0xD0xx. */
		case 26: return GetStringPtr(GetGRFStringID(0, 0xD000 + GB(string, 0, 10)));
		case 28: return GetGRFStringPtr(GB(string, 0, 11));
		case 29: return GetGRFStringPtr(GB(string, 0, 11) + 0x0800);
		case 30: return GetGRFStringPtr(GB(string, 0, 11) + 0x1000);
		default: return _langpack_offs[_langtab_start[string >> 11] + (string & 0x7FF)];
	}
}

/**
 * Get a parsed string with most special stringcodes replaced by the string parameters.
 * @param buffr  Pointer to a string buffer where the formatted string should be written to.
 * @param string
 * @param args   Arguments for the string.
 * @param last   Pointer just past the end of buffr.
 * @param case_index  The "case index". This will only be set when FormatString wants to print the string in a different case.
 * @return       Pointer to the final zero byte of the formatted string.
 */
char *GetStringWithArgs(char *buffr, StringID string, StringParameters *args, const char *last, uint case_index)
{
	if (string == 0) return GetStringWithArgs(buffr, STR_UNDEFINED, args, last);

	uint index = GB(string,  0, 11);
	uint tab   = GB(string, 11,  5);

	switch (tab) {
		case 4:
			if (index >= 0xC0) {
				return GetSpecialTownNameString(buffr, index - 0xC0, args->GetInt32(), last);
			}
			break;

		case 14:
			if (index >= 0xE4) {
				return GetSpecialNameString(buffr, index - 0xE4, args, last);
			}
			break;

		case 15:
			/* Old table for custom names. This is no longer used */
			error("Incorrect conversion of custom name string.");

		case 26:
			/* Include string within newgrf text (format code 81) */
			if (HasBit(index, 10)) {
				StringID string = GetGRFStringID(0, 0xD000 + GB(index, 0, 10));
				return GetStringWithArgs(buffr, string, args, last, case_index);
			}
			break;

		case 28:
			return FormatString(buffr, GetGRFStringPtr(index), args, case_index, last);

		case 29:
			return FormatString(buffr, GetGRFStringPtr(index + 0x0800), args, case_index, last);

		case 30:
			return FormatString(buffr, GetGRFStringPtr(index + 0x1000), args, case_index, last);

		case 31:
			NOT_REACHED();
	}

	if (index >= _langtab_num[tab]) {
		error("String 0x%X is invalid. You are probably using an old version of the .lng file.\n", string);
	}

	return FormatString(buffr, GetStringPtr(string), args, case_index, last);
}

char *GetString(char *buffr, StringID string, const char *last)
{
	_global_string_params.ClearTypeInformation();
	_global_string_params.offset = 0;
	return GetStringWithArgs(buffr, string, &_global_string_params, last);
}


char *InlineString(char *buf, StringID string)
{
	buf += Utf8Encode(buf, SCC_STRING_ID);
	buf += Utf8Encode(buf, string);
	return buf;
}


/**
 * This function is used to "bind" a C string to a OpenTTD dparam slot.
 * @param n slot of the string
 * @param str string to bind
 */
void SetDParamStr(uint n, const char *str)
{
	SetDParam(n, (uint64)(size_t)str);
}

/**
 * Shift the string parameters in the global string parameter array by \a amount positions, making room at the beginning.
 * @param amount Number of positions to shift.
 */
void InjectDParam(uint amount)
{
	_global_string_params.ShiftParameters(amount);
}

/**
 * Format a number into a string.
 * @param buff      the buffer to write to
 * @param number    the number to write down
 * @param last      the last element in the buffer
 * @param separator the thousands-separator to use
 * @param zerofill  minimum number of digits to print for the integer part. The number will be filled with zeros at the front if necessary.
 * @param fractional_digits number of fractional digits to display after a decimal separator. The decimal separator is inserted
 *                          in front of the \a fractional_digits last digit of \a number.
 * @return till where we wrote
 */
static char *FormatNumber(char *buff, int64 number, const char *last, const char *separator, int zerofill = 1, int fractional_digits = 0)
{
	static const int max_digits = 20;
	uint64 divisor = 10000000000000000000ULL;
	zerofill += fractional_digits;
	int thousands_offset = (max_digits - fractional_digits - 1) % 3;

	if (number < 0) {
		buff += seprintf(buff, last, "-");
		number = -number;
	}

	uint64 num = number;
	uint64 tot = 0;
	for (int i = 0; i < max_digits; i++) {
		if (i == max_digits - fractional_digits) {
			const char *decimal_separator = _settings_game.locale.digit_decimal_separator;
			if (decimal_separator == NULL) decimal_separator = _langpack->digit_decimal_separator;
			buff += seprintf(buff, last, "%s", decimal_separator);
		}

		uint64 quot = 0;
		if (num >= divisor) {
			quot = num / divisor;
			num = num % divisor;
		}
		if (tot |= quot || i >= max_digits - zerofill) {
			buff += seprintf(buff, last, "%i", (int)quot);
			if ((i % 3) == thousands_offset && i < max_digits - 1 - fractional_digits) buff = strecpy(buff, separator, last);
		}

		divisor /= 10;
	}

	*buff = '\0';

	return buff;
}

static char *FormatCommaNumber(char *buff, int64 number, const char *last, int fractional_digits = 0)
{
	const char *separator = _settings_game.locale.digit_group_separator;
	if (separator == NULL) separator = _langpack->digit_group_separator;
	return FormatNumber(buff, number, last, separator, 1, fractional_digits);
}

static char *FormatNoCommaNumber(char *buff, int64 number, const char *last)
{
	return FormatNumber(buff, number, last, "");
}

static char *FormatZerofillNumber(char *buff, int64 number, int64 count, const char *last)
{
	return FormatNumber(buff, number, last, "", count);
}

static char *FormatHexNumber(char *buff, uint64 number, const char *last)
{
	return buff + seprintf(buff, last, "0x" OTTD_PRINTFHEX64, number);
}

/**
 * Format a given number as a number of bytes with the SI prefix.
 * @param buff   the buffer to write to
 * @param number the number of bytes to write down
 * @param last   the last element in the buffer
 * @return till where we wrote
 */
static char *FormatBytes(char *buff, int64 number, const char *last)
{
	assert(number >= 0);

	/*                                   1   2^10  2^20  2^30  2^40  2^50  2^60 */
	const char * const iec_prefixes[] = {"", "Ki", "Mi", "Gi", "Ti", "Pi", "Ei"};
	uint id = 1;
	while (number >= 1024 * 1024) {
		number /= 1024;
		id++;
	}

	const char *decimal_separator = _settings_game.locale.digit_decimal_separator;
	if (decimal_separator == NULL) decimal_separator = _langpack->digit_decimal_separator;

	if (number < 1024) {
		id = 0;
		buff += seprintf(buff, last, "%i", (int)number);
	} else if (number < 1024 * 10) {
		buff += seprintf(buff, last, "%i%s%02i", (int)number / 1024, decimal_separator, (int)(number % 1024) * 100 / 1024);
	} else if (number < 1024 * 100) {
		buff += seprintf(buff, last, "%i%s%01i", (int)number / 1024, decimal_separator, (int)(number % 1024) * 10 / 1024);
	} else {
		assert(number < 1024 * 1024);
		buff += seprintf(buff, last, "%i", (int)number / 1024);
	}

	assert(id < lengthof(iec_prefixes));
	buff += seprintf(buff, last, " %sB", iec_prefixes[id]);

	return buff;
}

static char *FormatYmdString(char *buff, Date date, uint case_index, const char *last)
{
	YearMonthDay ymd;
	ConvertDateToYMD(date, &ymd);

	int64 args[] = {ymd.day + STR_ORDINAL_NUMBER_1ST - 1, STR_MONTH_ABBREV_JAN + ymd.month, ymd.year};
	StringParameters tmp_params(args);
	return FormatString(buff, GetStringPtr(STR_FORMAT_DATE_LONG), &tmp_params, case_index, last);
}

static char *FormatMonthAndYear(char *buff, Date date, uint case_index, const char *last)
{
	YearMonthDay ymd;
	ConvertDateToYMD(date, &ymd);

	int64 args[] = {STR_MONTH_JAN + ymd.month, ymd.year};
	StringParameters tmp_params(args);
	return FormatString(buff, GetStringPtr(STR_FORMAT_DATE_SHORT), &tmp_params, case_index, last);
}

static char *FormatTinyOrISODate(char *buff, Date date, StringID str, const char *last)
{
	YearMonthDay ymd;
	ConvertDateToYMD(date, &ymd);

	char day[3];
	char month[3];
	/* We want to zero-pad the days and months */
	snprintf(day,   lengthof(day),   "%02i", ymd.day);
	snprintf(month, lengthof(month), "%02i", ymd.month + 1);

	int64 args[] = {(int64)(size_t)day, (int64)(size_t)month, ymd.year};
	StringParameters tmp_params(args);
	return FormatString(buff, GetStringPtr(str), &tmp_params, 0, last);
}

static char *FormatGenericCurrency(char *buff, const CurrencySpec *spec, Money number, bool compact, const char *last)
{
	/* We are going to make number absolute for printing, so
	 * keep this piece of data as we need it later on */
	bool negative = number < 0;
	const char *multiplier = "";

	number *= spec->rate;

	/* convert from negative */
	if (number < 0) {
		if (buff + Utf8CharLen(SCC_RED) > last) return buff;
		buff += Utf8Encode(buff, SCC_RED);
		buff = strecpy(buff, "-", last);
		number = -number;
	}

	/* Add prefix part, folowing symbol_pos specification.
	 * Here, it can can be either 0 (prefix) or 2 (both prefix anf suffix).
	 * The only remaining value is 1 (suffix), so everything that is not 1 */
	if (spec->symbol_pos != 1) buff = strecpy(buff, spec->prefix, last);

	/* for huge numbers, compact the number into k or M */
	if (compact) {
		/* Take care of the 'k' rounding. Having 1 000 000 k
		 * and 1 000 M is inconsistent, so always use 1 000 M. */
		if (number >= 1000000000 - 500) {
			number = (number + 500000) / 1000000;
			multiplier = "M";
		} else if (number >= 1000000) {
			number = (number + 500) / 1000;
			multiplier = "k";
		}
	}

	const char *separator = _settings_game.locale.digit_group_separator_currency;
	if (separator == NULL && !StrEmpty(_currency->separator)) separator = _currency->separator;
	if (separator == NULL) separator = _langpack->digit_group_separator_currency;
	buff = FormatNumber(buff, number, last, separator);
	buff = strecpy(buff, multiplier, last);

	/* Add suffix part, folowing symbol_pos specification.
	 * Here, it can can be either 1 (suffix) or 2 (both prefix anf suffix).
	 * The only remaining value is 1 (prefix), so everything that is not 0 */
	if (spec->symbol_pos != 0) buff = strecpy(buff, spec->suffix, last);

	if (negative) {
		if (buff + Utf8CharLen(SCC_PREVIOUS_COLOUR) > last) return buff;
		buff += Utf8Encode(buff, SCC_PREVIOUS_COLOUR);
		*buff = '\0';
	}

	return buff;
}

/**
 * Determine the "plural" index given a plural form and a number.
 * @param count       The number to get the plural index of.
 * @param plural_form The plural form we want an index for.
 * @return The plural index for the given form.
 */
static int DeterminePluralForm(int64 count, int plural_form)
{
	/* The absolute value determines plurality */
	uint64 n = abs(count);

	switch (plural_form) {
		default:
			NOT_REACHED();

		/* Two forms, singular used for one only
		 * Used in:
		 *   Danish, Dutch, English, German, Norwegian, Swedish, Estonian, Finnish,
		 *   Greek, Hebrew, Italian, Portuguese, Spanish, Esperanto */
		case 0:
			return n != 1;

		/* Only one form
		 * Used in:
		 *   Hungarian, Japanese, Korean, Turkish */
		case 1:
			return 0;

		/* Two forms, singular used for zero and one
		 * Used in:
		 *   French, Brazilian Portuguese */
		case 2:
			return n > 1;

		/* Three forms, special case for 0 and ending in 1, except those ending in 11
		 * Used in:
		 *   Latvian */
		case 3:
			return n % 10 == 1 && n % 100 != 11 ? 0 : n != 0 ? 1 : 2;

		/* Five forms, special case for one, two, 3 to 6 and 7 to 10
		 * Used in:
		 *   Gaelige (Irish) */
		case 4:
			return n == 1 ? 0 : n == 2 ? 1 : n < 7 ? 2 : n < 11 ? 3 : 4;

		/* Three forms, special case for numbers ending in 1[2-9]
		 * Used in:
		 *   Lithuanian */
		case 5:
			return n % 10 == 1 && n % 100 != 11 ? 0 : n % 10 >= 2 && (n % 100 < 10 || n % 100 >= 20) ? 1 : 2;

		/* Three forms, special cases for numbers ending in 1 and 2, 3, 4, except those ending in 1[1-4]
		 * Used in:
		 *   Croatian, Russian, Ukrainian */
		case 6:
			return n % 10 == 1 && n % 100 != 11 ? 0 : n % 10 >= 2 && n % 10 <= 4 && (n % 100 < 10 || n % 100 >= 20) ? 1 : 2;

		/* Three forms, special case for one and some numbers ending in 2, 3, or 4
		 * Used in:
		 *   Polish */
		case 7:
			return n == 1 ? 0 : n % 10 >= 2 && n % 10 <= 4 && (n % 100 < 10 || n % 100 >= 20) ? 1 : 2;

		/* Four forms, special case for one and all numbers ending in 02, 03, or 04
		 * Used in:
		 *   Slovenian */
		case 8:
			return n % 100 == 1 ? 0 : n % 100 == 2 ? 1 : n % 100 == 3 || n % 100 == 4 ? 2 : 3;

		/* Two forms; singular used for everything ending in 1 but not in 11.
		 * Used in:
		 *   Icelandic */
		case 9:
			return n % 10 == 1 && n % 100 != 11 ? 0 : 1;

		/* Three forms, special cases for one and 2, 3, or 4
		 * Used in:
		 *   Czech, Slovak */
		case 10:
			return n == 1 ? 0 : n >= 2 && n <= 4 ? 1 : 2;

		/* Two forms, special 'hack' for Korean; singular for numbers ending
		 *   in a consonant and plural for numbers ending in a vowel.
		 * Korean doesn't have the concept of plural, but depending on how a
		 * number is pronounced it needs another version of a particle.
		 * As such the plural system is misused to give this distinction.
		 */
		case 11:
			switch (n % 10) {
				case 0: // yeong
				case 1: // il
				case 3: // sam
				case 6: // yuk
				case 7: // chil
				case 8: // pal
					return 0;

				case 2: // i
				case 4: // sa
				case 5: // o
				case 9: // gu
					return 1;

				default:
					NOT_REACHED();
			}

		/* Four forms: one, 0 and everything ending in 02..10, everything ending in 11..19.
		 * Used in:
		 *  Maltese */
		case 12:
			return (n == 1 ? 0 : n == 0 || (n % 100 > 1 && n % 100 < 11) ? 1 : (n % 100 > 10 && n % 100 < 20) ? 2 : 3);
	}
}

static const char *ParseStringChoice(const char *b, uint form, char **dst, const char *last)
{
	/* <NUM> {Length of each string} {each string} */
	uint n = (byte)*b++;
	uint pos, i, mypos = 0;

	for (i = pos = 0; i != n; i++) {
		uint len = (byte)*b++;
		if (i == form) mypos = pos;
		pos += len;
	}

	*dst += seprintf(*dst, last, "%s", b + mypos);
	return b + pos;
}

/** Helper for unit conversion. */
struct UnitConversion {
	int multiplier; ///< Amount to multiply upon conversion.
	int shift;      ///< Amount to shift upon conversion.

	/**
	 * Convert value from OpenTTD's internal unit into the displayed value.
	 * @param input The input to convert.
	 * @param round Whether to round the value or not.
	 * @return The converted value.
	 */
	int64 ToDisplay(int64 input, bool round = true) const
	{
		return ((input * this->multiplier) + (round && this->shift != 0 ? 1 << (this->shift - 1) : 0)) >> this->shift;
	}

	/**
	 * Convert the displayed value back into a value of OpenTTD's internal unit.
	 * @param input The input to convert.
	 * @param round Whether to round the value or not.
	 * @return The converted value.
	 */
	int64 FromDisplay(int64 input, bool round = true) const
	{
		return ((input << this->shift) + (round ? this->multiplier / 2 : 0)) / this->multiplier;
	}
};

struct Units {
	UnitConversion c_velocity; ///< Conversion for velocity
	StringID velocity;         ///< String for velocity
	UnitConversion c_power;    ///< Conversion for power
	StringID power;            ///< String for power
	UnitConversion c_weight;   ///< Conversion for weight
	StringID s_weight;         ///< Short string for weight
	StringID l_weight;         ///< Long string for weight
	UnitConversion c_volume;   ///< Conversion for volume
	StringID s_volume;         ///< Short string for volume
	StringID l_volume;         ///< Long string for volume
	UnitConversion c_force;    ///< Conversion for force
	StringID force;            ///< String for force
	UnitConversion c_height;   ///< Conversion for height
	StringID height;           ///< String for height
};

/* Unit conversions */
static const Units _units[] = {
	{ // Imperial (Original, mph, hp, metric ton, litre, kN, ft)
		{   1,  0}, STR_UNITS_VELOCITY_IMPERIAL,
		{   1,  0}, STR_UNITS_POWER_IMPERIAL,
		{   1,  0}, STR_UNITS_WEIGHT_SHORT_METRIC, STR_UNITS_WEIGHT_LONG_METRIC,
		{1000,  0}, STR_UNITS_VOLUME_SHORT_METRIC, STR_UNITS_VOLUME_LONG_METRIC,
		{   1,  0}, STR_UNITS_FORCE_SI,
		{   3,  0}, STR_UNITS_HEIGHT_IMPERIAL, // "Wrong" conversion factor for more nicer GUI values
	},
	{ // Metric (km/h, hp, metric ton, litre, kN, metre)
		{ 103,  6}, STR_UNITS_VELOCITY_METRIC,
		{4153, 12}, STR_UNITS_POWER_METRIC,
		{   1,  0}, STR_UNITS_WEIGHT_SHORT_METRIC, STR_UNITS_WEIGHT_LONG_METRIC,
		{1000,  0}, STR_UNITS_VOLUME_SHORT_METRIC, STR_UNITS_VOLUME_LONG_METRIC,
		{   1,  0}, STR_UNITS_FORCE_SI,
		{   1,  0}, STR_UNITS_HEIGHT_SI,
	},
	{ // SI (m/s, kilowatt, kilogram, cubic metre, kilonewton, metre)
		{1831, 12}, STR_UNITS_VELOCITY_SI,
		{6109, 13}, STR_UNITS_POWER_SI,
		{1000,  0}, STR_UNITS_WEIGHT_SHORT_SI, STR_UNITS_WEIGHT_LONG_SI,
		{   1,  0}, STR_UNITS_VOLUME_SHORT_SI, STR_UNITS_VOLUME_LONG_SI,
		{   1,  0}, STR_UNITS_FORCE_SI,
		{   1,  0}, STR_UNITS_HEIGHT_SI,
	},
};

/**
 * Convert the given (internal) speed to the display speed.
 * @param speed the speed to convert
 * @return the converted speed.
 */
uint ConvertSpeedToDisplaySpeed(uint speed)
{
	/* For historical reasons we don't want to mess with the
	 * conversion for speed. So, don't round it and keep the
	 * original conversion factors instead of the real ones. */
	return _units[_settings_game.locale.units].c_velocity.ToDisplay(speed, false);
}

/**
 * Convert the given display speed to the (internal) speed.
 * @param speed the speed to convert
 * @return the converted speed.
 */
uint ConvertDisplaySpeedToSpeed(uint speed)
{
	return _units[_settings_game.locale.units].c_velocity.FromDisplay(speed);
}

/**
 * Parse most format codes within a string and write the result to a buffer.
 * @param buff  The buffer to write the final string to.
 * @param str   The original string with format codes.
 * @param args  Pointer to extra arguments used by various string codes.
 * @param case_index
 * @param last  Pointer to just past the end of the buff array.
 * @param dry_run True when the argt array is not yet initialized.
 */
static char *FormatString(char *buff, const char *str_arg, StringParameters *args, uint case_index, const char *last, bool dry_run)
{
	uint orig_offset = args->offset;

	/* When there is no array with types there is no need to do a dry run. */
	if (args->HasTypeInformation() && !dry_run) {
		if (UsingNewGRFTextStack()) {
			/* Values from the NewGRF text stack are only copied to the normal
			 * argv array at the time they are encountered. That means that if
			 * another string command references a value later in the string it
			 * would fail. We solve that by running FormatString twice. The first
			 * pass makes sure the argv array is correctly filled and the second
			 * pass can reference later values without problems. */
			struct TextRefStack *backup = CreateTextRefStackBackup();
			FormatString(buff, str_arg, args, case_index, last, true);
			RestoreTextRefStackBackup(backup);
		} else {
			FormatString(buff, str_arg, args, case_index, last, true);
		}
		/* We have to restore the original offset here to to read the correct values. */
		args->offset = orig_offset;
	}
	WChar b;
	uint next_substr_case_index = 0;
	char *buf_start = buff;
	std::stack<const char *> str_stack;
	str_stack.push(str_arg);

	for (;;) {
		while (!str_stack.empty() && (b = Utf8Consume(&str_stack.top())) == '\0') {
			str_stack.pop();
		}
		if (str_stack.empty()) break;
		const char *&str = str_stack.top();

		if (SCC_NEWGRF_FIRST <= b && b <= SCC_NEWGRF_LAST) {
			/* We need to pass some stuff as it might be modified; oh boy. */
			//todo: should argve be passed here too?
			b = RemapNewGRFStringControlCode(b, buf_start, &buff, &str, (int64 *)args->GetDataPointer(), dry_run);
			if (b == 0) continue;
		}

		switch (b) {
			case SCC_NEWGRF_STRINL: {
				StringID substr = Utf8Consume(&str);
				str_stack.push(GetStringPtr(substr));
				break;
			}

			case SCC_NEWGRF_PRINT_WORD_STRING_ID: {
				StringID substr = args->GetInt32(SCC_NEWGRF_PRINT_WORD_STRING_ID);
				str_stack.push(GetStringPtr(substr));
				case_index = next_substr_case_index;
				next_substr_case_index = 0;
				break;
			}


			case SCC_SETX: // {SETX}
				if (buff + Utf8CharLen(SCC_SETX) + 1 < last) {
					buff += Utf8Encode(buff, SCC_SETX);
					*buff++ = *str++;
				}
				break;

			case SCC_SETXY: // {SETXY}
				if (buff + Utf8CharLen(SCC_SETXY) + 2 < last) {
					buff += Utf8Encode(buff, SCC_SETXY);
					*buff++ = *str++;
					*buff++ = *str++;
				}
				break;

			case SCC_STRING_ID: // {STRINL}
				buff = GetStringWithArgs(buff, Utf8Consume(&str), args, last);
				break;

			case SCC_RAW_STRING_POINTER: { // {RAW_STRING}
				const char *str = (const char *)(size_t)args->GetInt64();
				buff = FormatString(buff, str, args, case_index, last);
				break;
			}

			case SCC_DATE_LONG: // {DATE_LONG}
				buff = FormatYmdString(buff, args->GetInt32(SCC_DATE_LONG), next_substr_case_index, last);
				next_substr_case_index = 0;
				break;

			case SCC_DATE_SHORT: // {DATE_SHORT}
				buff = FormatMonthAndYear(buff, args->GetInt32(SCC_DATE_SHORT), next_substr_case_index, last);
				next_substr_case_index = 0;
				break;

			case SCC_VELOCITY: { // {VELOCITY}
				assert(_settings_game.locale.units < lengthof(_units));
				int64 args_array[] = {ConvertSpeedToDisplaySpeed(args->GetInt64(SCC_VELOCITY) * 10 / 16)};
				StringParameters tmp_params(args_array);
				buff = FormatString(buff, GetStringPtr(_units[_settings_game.locale.units].velocity), &tmp_params, 0, last);
				break;
			}

			case SCC_HEIGHT: { // {HEIGHT}
				int64 args_array[] = {_units[_settings_game.locale.units].c_height.ToDisplay(args->GetInt64())};
				StringParameters tmp_params(args_array);
				buff = FormatString(buff, GetStringPtr(_units[_settings_game.locale.units].height), &tmp_params, 0, last);
				break;
			}

			case SCC_CURRENCY_COMPACT: // {CURRCOMPACT}
				buff = FormatGenericCurrency(buff, _currency, args->GetInt64(), true, last);
				break;

			case SCC_REVISION: // {REV}
				buff = strecpy(buff, _openttd_revision, last);
				break;

			case SCC_CARGO_SHORT: { // {SHORTCARGO}
				/* Short description of cargotypes. Layout:
				 * 8-bit = cargo type
				 * 16-bit = cargo count */
				StringID cargo_str = CargoSpec::Get(args->GetInt32(SCC_CARGO_SHORT))->units_volume;
				switch (cargo_str) {
					case STR_TONS: {
						assert(_settings_game.locale.units < lengthof(_units));
						int64 args_array[] = {_units[_settings_game.locale.units].c_weight.ToDisplay(args->GetInt64())};
						StringParameters tmp_params(args_array);
						buff = FormatString(buff, GetStringPtr(_units[_settings_game.locale.units].l_weight), &tmp_params, 0, last);
						break;
					}

					case STR_LITERS: {
						assert(_settings_game.locale.units < lengthof(_units));
						int64 args_array[] = {_units[_settings_game.locale.units].c_volume.ToDisplay(args->GetInt64())};
						StringParameters tmp_params(args_array);
						buff = FormatString(buff, GetStringPtr(_units[_settings_game.locale.units].l_volume), &tmp_params, 0, last);
						break;
					}

					default: {
						StringParameters tmp_params(*args, 1);
						buff = GetStringWithArgs(buff, cargo_str, &tmp_params, last);
						break;
					}
				}
				break;
			}

			case SCC_STRING1: { // {STRING1}
				/* String that consumes ONE argument */
				StringID str = args->GetInt32(SCC_STRING1);
				StringParameters sub_args(*args, 1);
				buff = GetStringWithArgs(buff, str, &sub_args, last, next_substr_case_index);
				next_substr_case_index = 0;
				break;
			}

			case SCC_STRING2: { // {STRING2}
				/* String that consumes TWO arguments */
				StringID str = args->GetInt32(SCC_STRING2);
				StringParameters sub_args(*args, 2);
				buff = GetStringWithArgs(buff, str, &sub_args, last, next_substr_case_index);
				next_substr_case_index = 0;
				break;
			}

			case SCC_STRING3: { // {STRING3}
				/* String that consumes THREE arguments */
				StringID str = args->GetInt32(SCC_STRING3);
				StringParameters sub_args(*args, 3);
				buff = GetStringWithArgs(buff, str, &sub_args, last, next_substr_case_index);
				next_substr_case_index = 0;
				break;
			}

			case SCC_STRING4: { // {STRING4}
				/* String that consumes FOUR arguments */
				StringID str = args->GetInt32(SCC_STRING4);
				StringParameters sub_args(*args, 4);
				buff = GetStringWithArgs(buff, str, &sub_args, last, next_substr_case_index);
				next_substr_case_index = 0;
				break;
			}

			case SCC_STRING5: { // {STRING5}
				/* String that consumes FIVE arguments */
				StringID str = args->GetInt32(SCC_STRING5);
				StringParameters sub_args(*args, 5);
				buff = GetStringWithArgs(buff, str, &sub_args, last, next_substr_case_index);
				next_substr_case_index = 0;
				break;
			}

			case SCC_STATION_FEATURES: { // {STATIONFEATURES}
				buff = StationGetSpecialString(buff, args->GetInt32(SCC_STATION_FEATURES), last);
				break;
			}

			case SCC_INDUSTRY_NAME: { // {INDUSTRY}
				const Industry *i = Industry::Get(args->GetInt32(SCC_INDUSTRY_NAME));

				/* industry not valid anymore? */
				assert(i != NULL);

				/* First print the town name and the industry type name. */
				int64 args_array[2] = {i->town->index, GetIndustrySpec(i->type)->name};
				StringParameters tmp_params(args_array);

				buff = FormatString(buff, GetStringPtr(STR_FORMAT_INDUSTRY_NAME), &tmp_params, next_substr_case_index, last);
				next_substr_case_index = 0;
				break;
			}

			case SCC_VOLUME: { // {VOLUME}
				assert(_settings_game.locale.units < lengthof(_units));
				int64 args_array[1] = {_units[_settings_game.locale.units].c_volume.ToDisplay(args->GetInt64(SCC_VOLUME))};
				StringParameters tmp_params(args_array);
				buff = FormatString(buff, GetStringPtr(_units[_settings_game.locale.units].l_volume), &tmp_params, 0, last);
				break;
			}

			case SCC_GENDER_LIST: { // {G 0 Der Die Das}
				/* First read the meta data from the language file. */
				uint offset = orig_offset + (byte)*str++;
				int gender = 0;
				if (!dry_run && args->GetTypeAtOffset(offset) != 0) {
					/* Now we need to figure out what text to resolve, i.e.
					 * what do we need to draw? So get the actual raw string
					 * first using the control code to get said string. */
					char input[4 + 1];
					char *p = input + Utf8Encode(input, args->GetTypeAtOffset(offset));
					*p = '\0';

					/* Now do the string formatting. */
					char buf[256];
					bool old_kgd = _keep_gender_data;
					_keep_gender_data = true;
					StringParameters tmp_params(args->GetPointerToOffset(offset), args->num_param - offset, NULL);
					p = FormatString(buf, input, &tmp_params, 0, lastof(buf));
					_keep_gender_data = old_kgd;
					*p = '\0';

					/* And determine the string. */
					const char *s = buf;
					WChar c = Utf8Consume(&s);
					/* Does this string have a gender, if so, set it */
					if (c == SCC_GENDER_INDEX) gender = (byte)s[0];
				}
				str = ParseStringChoice(str, gender, &buff, last);
				break;
			}

			case SCC_DATE_TINY: { // {DATE_TINY}
				buff = FormatTinyOrISODate(buff, args->GetInt32(SCC_DATE_TINY), STR_FORMAT_DATE_TINY, last);
				break;
			}

			case SCC_DATE_ISO: { // {DATE_ISO}
				buff = FormatTinyOrISODate(buff, args->GetInt32(), STR_FORMAT_DATE_ISO, last);
				break;
			}

			case SCC_CARGO: { // {CARGO}
				/* First parameter is cargo type, second parameter is cargo count */
				CargoID cargo = args->GetInt32(SCC_CARGO);
				StringID cargo_str = (cargo == CT_INVALID) ? STR_QUANTITY_N_A : CargoSpec::Get(cargo)->quantifier;
				StringParameters tmp_args(*args, 1);
				buff = GetStringWithArgs(buff, cargo_str, &tmp_args, last);
				break;
			}

			case SCC_POWER: { // {POWER}
				assert(_settings_game.locale.units < lengthof(_units));
				int64 args_array[1] = {_units[_settings_game.locale.units].c_power.ToDisplay(args->GetInt64())};
				StringParameters tmp_params(args_array);
				buff = FormatString(buff, GetStringPtr(_units[_settings_game.locale.units].power), &tmp_params, 0, last);
				break;
			}

			case SCC_VOLUME_SHORT: { // {VOLUME_S}
				assert(_settings_game.locale.units < lengthof(_units));
				int64 args_array[1] = {_units[_settings_game.locale.units].c_volume.ToDisplay(args->GetInt64())};
				StringParameters tmp_params(args_array);
				buff = FormatString(buff, GetStringPtr(_units[_settings_game.locale.units].s_volume), &tmp_params, 0, last);
				break;
			}

			case SCC_WEIGHT: { // {WEIGHT}
				assert(_settings_game.locale.units < lengthof(_units));
				int64 args_array[1] = {_units[_settings_game.locale.units].c_weight.ToDisplay(args->GetInt64(SCC_WEIGHT))};
				StringParameters tmp_params(args_array);
				buff = FormatString(buff, GetStringPtr(_units[_settings_game.locale.units].l_weight), &tmp_params, 0, last);
				break;
			}

			case SCC_WEIGHT_SHORT: { // {WEIGHT_S}
				assert(_settings_game.locale.units < lengthof(_units));
				int64 args_array[1] = {_units[_settings_game.locale.units].c_weight.ToDisplay(args->GetInt64())};
				StringParameters tmp_params(args_array);
				buff = FormatString(buff, GetStringPtr(_units[_settings_game.locale.units].s_weight), &tmp_params, 0, last);
				break;
			}

			case SCC_FORCE: { // {FORCE}
				assert(_settings_game.locale.units < lengthof(_units));
				int64 args_array[1] = {_units[_settings_game.locale.units].c_force.ToDisplay(args->GetInt64())};
				StringParameters tmp_params(args_array);
				buff = FormatString(buff, GetStringPtr(_units[_settings_game.locale.units].force), &tmp_params, 0, last);
				break;
			}

			/* This sets up the gender for the string.
			 * We just ignore this one. It's used in {G 0 Der Die Das} to determine the case. */
			case SCC_GENDER_INDEX: // {GENDER 0}
				if (_keep_gender_data) {
					buff += Utf8Encode(buff, SCC_GENDER_INDEX);
					*buff++ = *str++;
				} else {
					str++;
				}
				break;

			case SCC_STRING: {// {STRING}
				StringID str = args->GetInt32(SCC_STRING);
				/* WARNING. It's prohibited for the included string to consume any arguments.
				 * For included strings that consume argument, you should use STRING1, STRING2 etc.
				 * To debug stuff you can set argv to NULL and it will tell you */
				StringParameters tmp_params(args->GetDataPointer(), args->num_param - args->offset, NULL);
				buff = GetStringWithArgs(buff, str, &tmp_params, last, next_substr_case_index);
				next_substr_case_index = 0;
				break;
			}

			case SCC_COMMA: // {COMMA}
				buff = FormatCommaNumber(buff, args->GetInt64(SCC_COMMA), last);
				break;

			case SCC_DECIMAL: {// {DECIMAL}
				int64 number = args->GetInt64(SCC_DECIMAL);
				int digits = args->GetInt32(SCC_DECIMAL);
				buff = FormatCommaNumber(buff, number, last, digits);
				break;
			}

			case SCC_ARG_INDEX: { // Move argument pointer
				args->offset = orig_offset + (byte)*str++;
				break;
			}

			case SCC_PLURAL_LIST: { // {P}
				int plural_form = *str++;          // contains the plural form for this string
				uint offset = orig_offset + (byte)*str++;
				int64 v = *args->GetPointerToOffset(offset); // contains the number that determines plural
				str = ParseStringChoice(str, DeterminePluralForm(v, plural_form), &buff, last);
				break;
			}

			case SCC_NUM: // {NUM}
				buff = FormatNoCommaNumber(buff, args->GetInt64(SCC_NUM), last);
				break;

			case SCC_ZEROFILL_NUM: { // {ZEROFILL_NUM}
				int64 num = args->GetInt64();
				buff = FormatZerofillNumber(buff, num, args->GetInt64(), last);
				break;
			}

			case SCC_HEX: // {HEX}
				buff = FormatHexNumber(buff, (uint64)args->GetInt64(SCC_HEX), last);
				break;

			case SCC_BYTES: // {BYTES}
				buff = FormatBytes(buff, args->GetInt64(), last);
				break;

			case SCC_CURRENCY: // {CURRENCY}
				buff = FormatGenericCurrency(buff, _currency, args->GetInt64(SCC_CURRENCY), false, last);
				break;

			case SCC_WAYPOINT_NAME: { // {WAYPOINT}
				Waypoint *wp = Waypoint::Get(args->GetInt32(SCC_WAYPOINT_NAME));

				assert(wp != NULL);

				if (wp->name != NULL) {
					buff = strecpy(buff, wp->name, last);
				} else {
					int64 args_array[] = {wp->town->index, wp->town_cn + 1};
					StringParameters tmp_params(args_array);
					StringID str = ((wp->string_id == STR_SV_STNAME_BUOY) ? STR_FORMAT_BUOY_NAME : STR_FORMAT_WAYPOINT_NAME);
					if (wp->town_cn != 0) str++;
					buff = GetStringWithArgs(buff, str, &tmp_params, last);
				}
				break;
			}

			case SCC_STATION_NAME: { // {STATION}
				StationID sid = args->GetInt32(SCC_STATION_NAME);
				const Station *st = Station::GetIfValid(sid);

				if (st == NULL) {
					/* The station doesn't exist anymore. The only place where we might
					 * be "drawing" an invalid station is in the case of cargo that is
					 * in transit. */
					StringParameters tmp_params(NULL, 0, NULL);
					buff = GetStringWithArgs(buff, STR_UNKNOWN_STATION, &tmp_params, last);
					break;
				}

				if (st->name != NULL) {
					buff = strecpy(buff, st->name, last);
				} else {
					StringID str = st->string_id;
					if (st->indtype != IT_INVALID) {
						/* Special case where the industry provides the name for the station */
						const IndustrySpec *indsp = GetIndustrySpec(st->indtype);

						/* Industry GRFs can change which might remove the station name and
						 * thus cause very strange things. Here we check for that before we
						 * actually set the station name. */
						if (indsp->station_name != STR_NULL && indsp->station_name != STR_UNDEFINED) {
							str = indsp->station_name;
						}
					}

					int64 args_array[] = {STR_TOWN_NAME, st->town->index, st->index};
					StringParameters tmp_params(args_array);
					buff = GetStringWithArgs(buff, str, &tmp_params, last);
				}
				break;
			}

			case SCC_DEPOT_NAME: { // {DEPOT}
				VehicleType vt = (VehicleType)args->GetInt32(SCC_DEPOT_NAME);
				if (vt == VEH_AIRCRAFT) {
					int64 args_array[] = {args->GetInt32()};
					StringParameters tmp_params(args_array);
					buff = GetStringWithArgs(buff, STR_FORMAT_DEPOT_NAME_AIRCRAFT, &tmp_params, last);
					break;
				}

				const Depot *d = Depot::Get(args->GetInt32());
				if (d->name != NULL) {
					buff = strecpy(buff, d->name, last);
				} else {
					int64 args_array[] = {d->town->index, d->town_cn + 1};
					StringParameters tmp_params(args_array);
					buff = GetStringWithArgs(buff, STR_FORMAT_DEPOT_NAME_TRAIN + 2 * vt + (d->town_cn == 0 ? 0 : 1), &tmp_params, last);
				}
				break;
			}

			case SCC_TOWN_NAME: { // {TOWN}
				const Town *t = Town::Get(args->GetInt32(SCC_TOWN_NAME));

				assert(t != NULL);

				if (t->name != NULL) {
					buff = strecpy(buff, t->name, last);
				} else {
					buff = GetTownName(buff, t, last);
				}
				break;
			}

			case SCC_GROUP_NAME: { // {GROUP}
				const Group *g = Group::Get(args->GetInt32());

				assert(g != NULL);

				if (g->name != NULL) {
					buff = strecpy(buff, g->name, last);
				} else {
					int64 args_array[] = {g->index};
					StringParameters tmp_params(args_array);

					buff = GetStringWithArgs(buff, STR_FORMAT_GROUP_NAME, &tmp_params, last);
				}
				break;
			}

			case SCC_ENGINE_NAME: { // {ENGINE}
				EngineID engine = (EngineID)args->GetInt32(SCC_ENGINE_NAME);
				const Engine *e = Engine::Get(engine);

				assert(e != NULL);

				if (e->name != NULL && e->IsEnabled()) {
					buff = strecpy(buff, e->name, last);
				} else {
					StringParameters tmp_params(NULL, 0, NULL);
					buff = GetStringWithArgs(buff, e->info.string_id, &tmp_params, last);
				}
				break;
			}

			case SCC_VEHICLE_NAME: { // {VEHICLE}
				const Vehicle *v = Vehicle::Get(args->GetInt32(SCC_VEHICLE_NAME));

				assert(v != NULL);

				if (v->name != NULL) {
					buff = strecpy(buff, v->name, last);
				} else {
					int64 args_array[] = {v->unitnumber};
					StringParameters tmp_params(args_array);

					StringID str;
					switch (v->type) {
						default: NOT_REACHED();
						case VEH_TRAIN:    str = STR_SV_TRAIN_NAME; break;
						case VEH_ROAD:     str = STR_SV_ROAD_VEHICLE_NAME; break;
						case VEH_SHIP:     str = STR_SV_SHIP_NAME; break;
						case VEH_AIRCRAFT: str = STR_SV_AIRCRAFT_NAME; break;
					}

					buff = GetStringWithArgs(buff, str, &tmp_params, last);
				}
				break;
			}

			case SCC_SIGN_NAME: { // {SIGN}
				const Sign *si = Sign::Get(args->GetInt32());
				if (si->name != NULL) {
					buff = strecpy(buff, si->name, last);
				} else {
					StringParameters tmp_params(NULL, 0, NULL);
					buff = GetStringWithArgs(buff, STR_DEFAULT_SIGN_NAME, &tmp_params, last);
				}
				break;
			}

			case SCC_COMPANY_NAME: { // {COMPANY}
				const Company *c = Company::Get((CompanyID)args->GetInt32());

				if (c->name != NULL) {
					buff = strecpy(buff, c->name, last);
				} else {
					int64 args_array[] = {c->name_2};
					StringParameters tmp_params(args_array);
					buff = GetStringWithArgs(buff, c->name_1, &tmp_params, last);
				}
				break;
			}

			case SCC_COMPANY_NUM: { // {COMPANYNUM}
				CompanyID company = (CompanyID)args->GetInt32();

				/* Nothing is added for AI or inactive companies */
				if (Company::IsValidHumanID(company)) {
					int64 args_array[] = {company + 1};
					StringParameters tmp_params(args_array);
					buff = GetStringWithArgs(buff, STR_FORMAT_COMPANY_NUM, &tmp_params, last);
				}
				break;
			}

			case SCC_PRESIDENT_NAME: { // {PRESIDENTNAME}
				const Company *c = Company::Get((CompanyID)args->GetInt32(SCC_PRESIDENT_NAME));

				if (c->president_name != NULL) {
					buff = strecpy(buff, c->president_name, last);
				} else {
					int64 args_array[] = {c->president_name_2};
					StringParameters tmp_params(args_array);
					buff = GetStringWithArgs(buff, c->president_name_1, &tmp_params, last);
				}
				break;
			}

			case SCC_SETCASE: { // {SETCASE}
				/* This is a pseudo command, it's outputted when someone does {STRING.ack}
				 * The modifier is added to all subsequent GetStringWithArgs that accept the modifier. */
				next_substr_case_index = (byte)*str++;
				break;
			}

			case SCC_SWITCH_CASE: { // {Used to implement case switching}
				/* <0x9E> <NUM CASES> <CASE1> <LEN1> <STRING1> <CASE2> <LEN2> <STRING2> <CASE3> <LEN3> <STRING3> <STRINGDEFAULT>
				 * Each LEN is printed using 2 bytes in big endian order. */
				uint num = (byte)*str++;
				while (num) {
					if ((byte)str[0] == case_index) {
						/* Found the case, adjust str pointer and continue */
						str += 3;
						break;
					}
					/* Otherwise skip to the next case */
					str += 3 + (str[1] << 8) + str[2];
					num--;
				}
				break;
			}

			default:
				if (buff + Utf8CharLen(b) < last) buff += Utf8Encode(buff, b);
				break;
		}
	}
	*buff = '\0';
	return buff;
}


static char *StationGetSpecialString(char *buff, int x, const char *last)
{
	if ((x & FACIL_TRAIN)      && (buff + Utf8CharLen(SCC_TRAIN) < last)) buff += Utf8Encode(buff, SCC_TRAIN);
	if ((x & FACIL_TRUCK_STOP) && (buff + Utf8CharLen(SCC_LORRY) < last)) buff += Utf8Encode(buff, SCC_LORRY);
	if ((x & FACIL_BUS_STOP)   && (buff + Utf8CharLen(SCC_BUS)   < last)) buff += Utf8Encode(buff, SCC_BUS);
	if ((x & FACIL_DOCK)       && (buff + Utf8CharLen(SCC_SHIP)  < last)) buff += Utf8Encode(buff, SCC_SHIP);
	if ((x & FACIL_AIRPORT)    && (buff + Utf8CharLen(SCC_PLANE) < last)) buff += Utf8Encode(buff, SCC_PLANE);
	*buff = '\0';
	return buff;
}

static char *GetSpecialTownNameString(char *buff, int ind, uint32 seed, const char *last)
{
	return GenerateTownNameString(buff, last, ind, seed);
}

static const char * const _silly_company_names[] = {
	"Bloggs Brothers",
	"Tiny Transport Ltd.",
	"Express Travel",
	"Comfy-Coach & Co.",
	"Crush & Bump Ltd.",
	"Broken & Late Ltd.",
	"Sam Speedy & Son",
	"Supersonic Travel",
	"Mike's Motors",
	"Lightning International",
	"Pannik & Loozit Ltd.",
	"Inter-City Transport",
	"Getout & Pushit Ltd."
};

static const char * const _surname_list[] = {
	"Adams",
	"Allan",
	"Baker",
	"Bigwig",
	"Black",
	"Bloggs",
	"Brown",
	"Campbell",
	"Gordon",
	"Hamilton",
	"Hawthorn",
	"Higgins",
	"Green",
	"Gribble",
	"Jones",
	"McAlpine",
	"MacDonald",
	"McIntosh",
	"Muir",
	"Murphy",
	"Nelson",
	"O'Donnell",
	"Parker",
	"Phillips",
	"Pilkington",
	"Quigley",
	"Sharkey",
	"Thomson",
	"Watkins"
};

static const char * const _silly_surname_list[] = {
	"Grumpy",
	"Dozy",
	"Speedy",
	"Nosey",
	"Dribble",
	"Mushroom",
	"Cabbage",
	"Sniffle",
	"Fishy",
	"Swindle",
	"Sneaky",
	"Nutkins"
};

static const char _initial_name_letters[] = {
	'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',
	'K', 'L', 'M', 'N', 'P', 'R', 'S', 'T', 'W',
};

static char *GenAndCoName(char *buff, uint32 arg, const char *last)
{
	const char * const *base;
	uint num;

	if (_settings_game.game_creation.landscape == LT_TOYLAND) {
		base = _silly_surname_list;
		num  = lengthof(_silly_surname_list);
	} else {
		base = _surname_list;
		num  = lengthof(_surname_list);
	}

	buff = strecpy(buff, base[num * GB(arg, 16, 8) >> 8], last);
	buff = strecpy(buff, " & Co.", last);

	return buff;
}

static char *GenPresidentName(char *buff, uint32 x, const char *last)
{
	char initial[] = "?. ";
	const char * const *base;
	uint num;
	uint i;

	initial[0] = _initial_name_letters[sizeof(_initial_name_letters) * GB(x, 0, 8) >> 8];
	buff = strecpy(buff, initial, last);

	i = (sizeof(_initial_name_letters) + 35) * GB(x, 8, 8) >> 8;
	if (i < sizeof(_initial_name_letters)) {
		initial[0] = _initial_name_letters[i];
		buff = strecpy(buff, initial, last);
	}

	if (_settings_game.game_creation.landscape == LT_TOYLAND) {
		base = _silly_surname_list;
		num  = lengthof(_silly_surname_list);
	} else {
		base = _surname_list;
		num  = lengthof(_surname_list);
	}

	buff = strecpy(buff, base[num * GB(x, 16, 8) >> 8], last);

	return buff;
}

static char *GetSpecialNameString(char *buff, int ind, StringParameters *args, const char *last)
{
	switch (ind) {
		case 1: // not used
			return strecpy(buff, _silly_company_names[min(args->GetInt32() & 0xFFFF, lengthof(_silly_company_names) - 1)], last);

		case 2: // used for Foobar & Co company names
			return GenAndCoName(buff, args->GetInt32(), last);

		case 3: // President name
			return GenPresidentName(buff, args->GetInt32(), last);
	}

	/* town name? */
	if (IsInsideMM(ind - 6, 0, SPECSTR_TOWNNAME_LAST - SPECSTR_TOWNNAME_START + 1)) {
		buff = GetSpecialTownNameString(buff, ind - 6, args->GetInt32(), last);
		return strecpy(buff, " Transport", last);
	}

	/* language name? */
	if (IsInsideMM(ind, (SPECSTR_LANGUAGE_START - 0x70E4), (SPECSTR_LANGUAGE_END - 0x70E4) + 1)) {
		int i = ind - (SPECSTR_LANGUAGE_START - 0x70E4);
		return strecpy(buff,
			&_languages[i] == _current_language ? _current_language->own_name : _languages[i].name, last);
	}

	/* resolution size? */
	if (IsInsideMM(ind, (SPECSTR_RESOLUTION_START - 0x70E4), (SPECSTR_RESOLUTION_END - 0x70E4) + 1)) {
		int i = ind - (SPECSTR_RESOLUTION_START - 0x70E4);
		buff += seprintf(
			buff, last, "%ux%u", _resolutions[i].width, _resolutions[i].height
		);
		return buff;
	}

	/* screenshot format name? */
	if (IsInsideMM(ind, (SPECSTR_SCREENSHOT_START - 0x70E4), (SPECSTR_SCREENSHOT_END - 0x70E4) + 1)) {
		int i = ind - (SPECSTR_SCREENSHOT_START - 0x70E4);
		return strecpy(buff, GetScreenshotFormatDesc(i), last);
	}

	NOT_REACHED();
}

#ifdef ENABLE_NETWORK
extern void SortNetworkLanguages();
#else /* ENABLE_NETWORK */
static inline void SortNetworkLanguages() {}
#endif /* ENABLE_NETWORK */

/**
 * Check whether the header is a valid header for OpenTTD.
 * @return true iff the header is deemed valid.
 */
bool LanguagePackHeader::IsValid() const
{
	return this->ident        == TO_LE32(LanguagePackHeader::IDENT) &&
	       this->version      == TO_LE32(LANGUAGE_PACK_VERSION) &&
	       this->plural_form  <  LANGUAGE_MAX_PLURAL &&
	       this->text_dir     <= 1 &&
	       this->newgrflangid < MAX_LANG &&
	       this->num_genders  < MAX_NUM_GENDERS &&
	       this->num_cases    < MAX_NUM_CASES &&
	       StrValid(this->name,                           lastof(this->name)) &&
	       StrValid(this->own_name,                       lastof(this->own_name)) &&
	       StrValid(this->isocode,                        lastof(this->isocode)) &&
	       StrValid(this->digit_group_separator,          lastof(this->digit_group_separator)) &&
	       StrValid(this->digit_group_separator_currency, lastof(this->digit_group_separator_currency)) &&
	       StrValid(this->digit_decimal_separator,        lastof(this->digit_decimal_separator));
}

/**
 * Read a particular language.
 * @param lang The metadata about the language.
 * @return Whether the loading went okay or not.
 */
bool ReadLanguagePack(const LanguageMetadata *lang)
{
	/* Current language pack */
	size_t len;
	LanguagePack *lang_pack = (LanguagePack *)ReadFileToMem(lang->file, &len, 1U << 20);
	if (lang_pack == NULL) return false;

	/* End of read data (+ terminating zero added in ReadFileToMem()) */
	const char *end = (char *)lang_pack + len + 1;

	/* We need at least one byte of lang_pack->data */
	if (end <= lang_pack->data || !lang_pack->IsValid()) {
		free(lang_pack);
		return false;
	}

#if TTD_ENDIAN == TTD_BIG_ENDIAN
	for (uint i = 0; i < 32; i++) {
		lang_pack->offsets[i] = ReadLE16Aligned(&lang_pack->offsets[i]);
	}
#endif /* TTD_ENDIAN == TTD_BIG_ENDIAN */

	uint count = 0;
	for (uint i = 0; i < 32; i++) {
		uint num = lang_pack->offsets[i];
		_langtab_start[i] = count;
		_langtab_num[i] = num;
		count += num;
	}

	/* Allocate offsets */
	char **langpack_offs = MallocT<char *>(count);

	/* Fill offsets */
	char *s = lang_pack->data;
	len = (byte)*s++;
	for (uint i = 0; i < count; i++) {
		if (s + len >= end) {
			free(lang_pack);
			free(langpack_offs);
			return false;
		}
		if (len >= 0xC0) {
			len = ((len & 0x3F) << 8) + (byte)*s++;
			if (s + len >= end) {
				free(lang_pack);
				free(langpack_offs);
				return false;
			}
		}
		langpack_offs[i] = s;
		s += len;
		len = (byte)*s;
		*s++ = '\0'; // zero terminate the string
	}

	free(_langpack);
	_langpack = lang_pack;

	free(_langpack_offs);
	_langpack_offs = langpack_offs;

	_current_language = lang;
	_current_text_dir = (TextDirection)_current_language->text_dir;
	const char *c_file = strrchr(_current_language->file, PATHSEPCHAR) + 1;
	strecpy(_config_language_file, c_file, lastof(_config_language_file));
	SetCurrentGrfLangID(_current_language->newgrflangid);

#ifdef WITH_ICU
	/* Delete previous collator. */
	if (_current_collator != NULL) {
		delete _current_collator;
		_current_collator = NULL;
	}

	/* Create a collator instance for our current locale. */
	UErrorCode status = U_ZERO_ERROR;
	_current_collator = Collator::createInstance(Locale(_current_language->isocode), status);
	/* Sort number substrings by their numerical value. */
	if (_current_collator != NULL) _current_collator->setAttribute(UCOL_NUMERIC_COLLATION, UCOL_ON, status);
	/* Avoid using the collator if it is not correctly set. */
	if (U_FAILURE(status)) {
		delete _current_collator;
		_current_collator = NULL;
	}
#endif /* WITH_ICU */

	/* Some lists need to be sorted again after a language change. */
	InitializeSortedCargoSpecs();
	SortIndustryTypes();
	BuildIndustriesLegend();
	SortNetworkLanguages();
	InvalidateWindowClassesData(WC_BUILD_VEHICLE);      // Build vehicle window.
	InvalidateWindowClassesData(WC_TRAINS_LIST);        // Train group window.
	InvalidateWindowClassesData(WC_ROADVEH_LIST);       // Road vehicle group window.
	InvalidateWindowClassesData(WC_SHIPS_LIST);         // Ship group window.
	InvalidateWindowClassesData(WC_AIRCRAFT_LIST);      // Aircraft group window.
	InvalidateWindowClassesData(WC_INDUSTRY_DIRECTORY); // Industry directory window.
	InvalidateWindowClassesData(WC_STATION_LIST);       // Station list window.

	return true;
}

/* Win32 implementation in win32.cpp.
 * OS X implementation in os/macosx/macos.mm. */
#if !(defined(WIN32) || defined(__APPLE__))
/**
 * Determine the current charset based on the environment
 * First check some default values, after this one we passed ourselves
 * and if none exist return the value for $LANG
 * @param param environment variable to check conditionally if default ones are not
 *        set. Pass NULL if you don't want additional checks.
 * @return return string containing current charset, or NULL if not-determinable
 */
const char *GetCurrentLocale(const char *param)
{
	const char *env;

	env = getenv("LANGUAGE");
	if (env != NULL) return env;

	env = getenv("LC_ALL");
	if (env != NULL) return env;

	if (param != NULL) {
		env = getenv(param);
		if (env != NULL) return env;
	}

	return getenv("LANG");
}
#else
const char *GetCurrentLocale(const char *param);
#endif /* !(defined(WIN32) || defined(__APPLE__)) */

int CDECL StringIDSorter(const StringID *a, const StringID *b)
{
	char stra[512];
	char strb[512];
	GetString(stra, *a, lastof(stra));
	GetString(strb, *b, lastof(strb));

	return strcmp(stra, strb);
}

/**
 * Get the language with the given NewGRF language ID.
 * @param newgrflangid NewGRF languages ID to check.
 * @return The language's metadata, or NULL if it is not known.
 */
const LanguageMetadata *GetLanguage(byte newgrflangid)
{
	for (const LanguageMetadata *lang = _languages.Begin(); lang != _languages.End(); lang++) {
		if (newgrflangid == lang->newgrflangid) return lang;
	}

	return NULL;
}

/**
 * Reads the language file header and checks compatability.
 * @param file the file to read
 * @param hdr  the place to write the header information to
 * @return true if and only if the language file is of a compatible version
 */
static bool GetLanguageFileHeader(const char *file, LanguagePackHeader *hdr)
{
	FILE *f = fopen(file, "rb");
	if (f == NULL) return false;

	size_t read = fread(hdr, sizeof(*hdr), 1, f);
	fclose(f);

	bool ret = read == 1 && hdr->IsValid();

	/* Convert endianness for the windows language ID */
	if (ret) {
		hdr->missing = FROM_LE16(hdr->missing);
		hdr->winlangid = FROM_LE16(hdr->winlangid);
	}
	return ret;
}

/**
 * Gets a list of languages from the given directory.
 * @param path  the base directory to search in
 */
static void GetLanguageList(const char *path)
{
	DIR *dir = ttd_opendir(path);
	if (dir != NULL) {
		struct dirent *dirent;
		while ((dirent = readdir(dir)) != NULL) {
			const char *d_name    = FS2OTTD(dirent->d_name);
			const char *extension = strrchr(d_name, '.');

			/* Not a language file */
			if (extension == NULL || strcmp(extension, ".lng") != 0) continue;

			LanguageMetadata lmd;
			seprintf(lmd.file, lastof(lmd.file), "%s%s", path, d_name);

			/* Check whether the file is of the correct version */
			if (!GetLanguageFileHeader(lmd.file, &lmd)) {
				DEBUG(misc, 3, "%s is not a valid language file", lmd.file);
			} else if (GetLanguage(lmd.newgrflangid) != NULL) {
				DEBUG(misc, 3, "%s's language ID is already known", lmd.file);
			} else {
				*_languages.Append() = lmd;
			}
		}
		closedir(dir);
	}
}

/**
 * Make a list of the available language packs. put the data in
 * _dynlang struct.
 */
void InitializeLanguagePacks()
{
	Searchpath sp;

	FOR_ALL_SEARCHPATHS(sp) {
		char path[MAX_PATH];
		FioAppendDirectory(path, lengthof(path), sp, LANG_DIR);
		GetLanguageList(path);
	}
	if (_languages.Length() == 0) usererror("No available language packs (invalid versions?)");

	/* Acquire the locale of the current system */
	const char *lang = GetCurrentLocale("LC_MESSAGES");
	if (lang == NULL) lang = "en_GB";

	const LanguageMetadata *chosen_language   = NULL; ///< Matching the language in the configuartion file or the current locale
	const LanguageMetadata *language_fallback = NULL; ///< Using pt_PT for pt_BR locale when pt_BR is not available
	const LanguageMetadata *en_GB_fallback    = _languages.Begin(); ///< Fallback when no locale-matching language has been found

	/* Find a proper language. */
	for (const LanguageMetadata *lng = _languages.Begin(); lng != _languages.End(); lng++) {
		/* We are trying to find a default language. The priority is by
		 * configuration file, local environment and last, if nothing found,
		 * english. */
		const char *lang_file = strrchr(lng->file, PATHSEPCHAR) + 1;
		if (strcmp(lang_file, _config_language_file) == 0) {
			chosen_language = lng;
			break;
		}

		if (strcmp (lng->isocode, "en_GB") == 0) en_GB_fallback    = lng;
		if (strncmp(lng->isocode, lang, 5) == 0) chosen_language   = lng;
		if (strncmp(lng->isocode, lang, 2) == 0) language_fallback = lng;
	}

	/* We haven't found the language in the config nor the one in the locale.
	 * Now we set it to one of the fallback languages */
	if (chosen_language == NULL) {
		chosen_language = (language_fallback != NULL) ? language_fallback : en_GB_fallback;
	}

	if (!ReadLanguagePack(chosen_language)) usererror("Can't read language pack '%s'", chosen_language->file);
}

/**
 * Get the ISO language code of the currently loaded language.
 * @return the ISO code.
 */
const char *GetCurrentLanguageIsoCode()
{
	return _langpack->isocode;
}

/**
 * Check whether there are glyphs missing in the current language.
 * @param Pointer to an address for storing the text pointer.
 * @return If glyphs are missing, return \c true, else return \false.
 * @post If \c true is returned and str is not NULL, *str points to a string that is found to contain at least one missing glyph.
 */
static bool FindMissingGlyphs(const char **str)
{
#ifdef WITH_FREETYPE
	UninitFreeType();
	InitFreeType();
#endif
	const Sprite *question_mark[FS_END];
	FontSize size;

	for (size = FS_BEGIN; size < FS_END; size++) {
		question_mark[size] = GetGlyph(size, '?');
	}

	for (uint i = 0; i != 32; i++) {
		for (uint j = 0; j < _langtab_num[i]; j++) {
			size = FS_NORMAL;
			const char *text = _langpack_offs[_langtab_start[i] + j];
			if (str != NULL) *str = text;
			for (WChar c = Utf8Consume(&text); c != '\0'; c = Utf8Consume(&text)) {
				if (c == SCC_SETX) {
					/* SetX is, together with SetXY as special character that
					 * uses the next (two) characters as data points. We have
					 * to skip those, otherwise the UTF8 reading will go haywire. */
					text++;
				} else if (c == SCC_SETXY) {
					text += 2;
				} else if (c == SCC_TINYFONT) {
					size = FS_SMALL;
				} else if (c == SCC_BIGFONT) {
					size = FS_LARGE;
				} else if (IsPrintable(c) && !IsTextDirectionChar(c) && c != '?' && GetGlyph(size, c) == question_mark[size]) {
					/* The character is printable, but not in the normal font. This is the case we were testing for. */
					return true;
				}
			}
		}
	}
	return false;
}

/**
 * Check whether the currently loaded language pack
 * uses characters that the currently loaded font
 * does not support. If this is the case an error
 * message will be shown in English. The error
 * message will not be localized because that would
 * mean it might use characters that are not in the
 * font, which is the whole reason this check has
 * been added.
 */
void CheckForMissingGlyphsInLoadedLanguagePack()
{
	bool bad_font = FindMissingGlyphs(NULL);
#ifdef WITH_FREETYPE
	if (bad_font) {
		/* We found an unprintable character... lets try whether we can find
		 * a fallback font that can print the characters in the current language. */
		FreeTypeSettings backup;
		memcpy(&backup, &_freetype, sizeof(backup));

		bad_font = !SetFallbackFont(&_freetype, _langpack->isocode, _langpack->winlangid, &FindMissingGlyphs);

		memcpy(&_freetype, &backup, sizeof(backup));

		if (bad_font) {
			/* Our fallback font does miss characters too, so keep the
			 * user chosen font as that is more likely to be any good than
			 * the wild guess we made */
			UninitFreeType();
			InitFreeType();
		}
	}
#endif

	if (bad_font) {
		/* All attempts have failed. Display an error. As we do not want the string to be translated by
		 * the translators, we 'force' it into the binary and 'load' it via a BindCString. To do this
		 * properly we have to set the colour of the string, otherwise we end up with a lot of artefacts.
		 * The colour 'character' might change in the future, so for safety we just Utf8 Encode it into
		 * the string, which takes exactly three characters, so it replaces the "XXX" with the colour marker. */
		static char *err_str = strdup("XXXThe current font is missing some of the characters used in the texts for this language. Read the readme to see how to solve this.");
		Utf8Encode(err_str, SCC_YELLOW);
		SetDParamStr(0, err_str);
		ShowErrorMessage(STR_JUST_RAW_STRING, INVALID_STRING_ID, WL_WARNING);

		/* Reset the font width */
		LoadStringWidthTable();
		return;
	}

	/* Update the font with cache */
	LoadStringWidthTable();

#if !defined(WITH_ICU)
	/*
	 * For right-to-left languages we need the ICU library. If
	 * we do not have support for that library we warn the user
	 * about it with a message. As we do not want the string to
	 * be translated by the translators, we 'force' it into the
	 * binary and 'load' it via a BindCString. To do this
	 * properly we have to set the colour of the string,
	 * otherwise we end up with a lot of artefacts. The colour
	 * 'character' might change in the future, so for safety
	 * we just Utf8 Encode it into the string, which takes
	 * exactly three characters, so it replaces the "XXX" with
	 * the colour marker.
	 */
	if (_current_text_dir != TD_LTR) {
		static char *err_str = strdup("XXXThis version of OpenTTD does not support right-to-left languages. Recompile with icu enabled.");
		Utf8Encode(err_str, SCC_YELLOW);
		SetDParamStr(0, err_str);
		ShowErrorMessage(STR_JUST_RAW_STRING, INVALID_STRING_ID, WL_ERROR);
	}
#endif
}