#include <sourcemod>
#include <sdktools>
#include <regex>

#pragma semicolon 1
#pragma newdecls required

#define CHAT_PREFIX "\x04[NameFilter]\x01"
#define MAX_STACKED_MARKS 2 // combining marks allowed on one letter (Vietnamese needs 2)
#define RELOAD_FILE "data/namefilter2_reload.dat"
#define RELOAD_MAX_AGE 120 // seconds; older saves are from a previous server run

enum struct SavedName
{
	int iUserId;
	char sOriginal[MAX_NAME_LENGTH];
	char sAssigned[MAX_NAME_LENGTH];
	char sCurrent[MAX_NAME_LENGTH];
}

char g_sOriginalName[MAXPLAYERS + 1][MAX_NAME_LENGTH];
char g_sAssignedName[MAXPLAYERS + 1][MAX_NAME_LENGTH]; // the filtered name we gave the player
ArrayList g_SavedNames; // original names saved over a plugin reload
int g_iBlockNameChangeEvents[MAXPLAYERS + 1] = {0, ...};
bool g_bFilteredOnConnect[MAXPLAYERS + 1];
bool g_bReplacedOnConnect[MAXPLAYERS + 1];
bool g_bLastFilterReplaced; // whether the last FilterName() assigned a replacement name

ArrayList g_AdvertExprs;
ArrayList g_BannedExprs;
ArrayList g_ReplacementNames;
ArrayList g_ConfusableFrom;
ArrayList g_ConfusableTo;
ArrayList g_WhitelistCps;
int g_iMinNameLength = 2;
int g_iMinSurvivedPct = 50;
int g_iKeepTypeableRun = 5;

public Plugin myinfo =
{
	name = "NameFilter2",
	author = "marisakirisame.net",
	description = "Normalises and filters player names",
	version = "1.0"
}

public void OnPluginStart()
{
	HookEvent("player_changename", Event_ChangeName, EventHookMode_Pre);
	HookUserMessage(GetUserMessageId("SayText2"), UserMessage_SayText2, true);

	RegConsoleCmd("sm_originalname", Command_OriginalName, "Show a player's original name");
	RegConsoleCmd("sm_changednames", Command_ChangedNames, "List all players whose names were changed");
	RegAdminCmd("sm_namefilter2_reload", Command_Reload, ADMFLAG_CONFIG, "Reload the NameFilter2 config");

	LoadConfig();
	LoadSavedNames();

	for(int i = 1; i <= MaxClients; i++)
	{
		if(IsClientConnected(i))
			OnClientConnected(i);
	}
}

public void OnPluginEnd()
{
	char sPath[PLATFORM_MAX_PATH];
	BuildPath(Path_SM, sPath, sizeof(sPath), RELOAD_FILE);

	File hFile = OpenFile(sPath, "wb");
	if(!hFile)
		return;

	// null-terminated strings, as names may contain any printable character
	hFile.WriteInt32(GetTime());
	for(int i = 1; i <= MaxClients; i++)
	{
		if(!IsClientConnected(i) || IsFakeClient(i) || !g_sOriginalName[i][0])
			continue;

		char sCurrent[MAX_NAME_LENGTH];
		GetClientName(i, sCurrent, sizeof(sCurrent));

		hFile.WriteInt32(GetClientUserId(i));
		hFile.WriteString(g_sOriginalName[i], true);
		hFile.WriteString(g_sAssignedName[i], true);
		hFile.WriteString(sCurrent, true);
	}

	delete hFile;
}

void LoadSavedNames()
{
	g_SavedNames = new ArrayList(sizeof(SavedName));

	char sPath[PLATFORM_MAX_PATH];
	BuildPath(Path_SM, sPath, sizeof(sPath), RELOAD_FILE);

	File hFile = OpenFile(sPath, "rb");
	if(!hFile)
		return;

	int iSaved;
	if(hFile.ReadInt32(iSaved) && GetTime() - iSaved <= RELOAD_MAX_AGE)
	{
		SavedName saved;
		while(hFile.ReadInt32(saved.iUserId)
			&& hFile.ReadString(saved.sOriginal, sizeof(saved.sOriginal)) != -1
			&& hFile.ReadString(saved.sAssigned, sizeof(saved.sAssigned)) != -1
			&& hFile.ReadString(saved.sCurrent, sizeof(saved.sCurrent)) != -1)
		{
			g_SavedNames.PushArray(saved);
		}
	}

	delete hFile;
	DeleteFile(sPath);
}

// restores a late-loaded client's state saved by OnPluginEnd, as long as
// they still have the same name. Entries are kept: userids are never reused
bool RestoreSavedName(int client, const char[] sName)
{
	int iUserId = GetClientUserId(client);

	for(int i = 0; i < g_SavedNames.Length; i++)
	{
		SavedName saved;
		g_SavedNames.GetArray(i, saved);
		if(saved.iUserId != iUserId)
			continue;

		if(!StrEqual(saved.sCurrent, sName))
			return false;

		strcopy(g_sOriginalName[client], MAX_NAME_LENGTH, saved.sOriginal);
		strcopy(g_sAssignedName[client], MAX_NAME_LENGTH, saved.sAssigned);
		return true;
	}

	return false;
}

public void OnClientConnected(int client)
{
	g_iBlockNameChangeEvents[client] = 0;
	g_bFilteredOnConnect[client] = false;
	g_bReplacedOnConnect[client] = false;
	g_sAssignedName[client][0] = '\0';

	char sName[MAX_NAME_LENGTH];
	GetClientName(client, sName, sizeof(sName));
	strcopy(g_sOriginalName[client], MAX_NAME_LENGTH, sName);

	if(IsFakeClient(client))
		return;

	if(RestoreSavedName(client, sName))
		return;

	if(FilterName(client, sName))
	{
		g_bFilteredOnConnect[client] = true;
		g_bReplacedOnConnect[client] = g_bLastFilterReplaced;
		strcopy(g_sAssignedName[client], MAX_NAME_LENGTH, sName);
		SetClientName(client, sName);
	}
}

public void OnClientPutInServer(int client)
{
	if(IsFakeClient(client))
		return;

	char sName[MAX_NAME_LENGTH];
	GetClientName(client, sName, sizeof(sName));

	if(FilterName(client, sName))
	{
		g_bFilteredOnConnect[client] = true;
		if(g_bLastFilterReplaced)
			g_bReplacedOnConnect[client] = true;
		g_iBlockNameChangeEvents[client] = 2;
		strcopy(g_sAssignedName[client], MAX_NAME_LENGTH, sName);
		SetClientName(client, sName);
	}

	if(g_bFilteredOnConnect[client])
	{
		NotifyAdminsFiltered(client, sName, g_bReplacedOnConnect[client]);
		NotifyClientRenamed(client, sName, g_bReplacedOnConnect[client]);
	}
}

public void OnClientDisconnect(int client)
{
	g_sOriginalName[client][0] = '\0';
	g_sAssignedName[client][0] = '\0';
	g_iBlockNameChangeEvents[client] = 0;
	g_bFilteredOnConnect[client] = false;
	g_bReplacedOnConnect[client] = false;
}

void NotifyAdminsFiltered(int client, const char[] sNewName, bool bReplaced)
{
	PrintToServer("[NameFilter2] \"%s\" (#%d) was %s \"%s\"", g_sOriginalName[client], GetClientUserId(client),
		bReplaced ? "given replacement name" : "renamed to", sNewName);

	for(int i = 1; i <= MaxClients; i++)
	{
		if(!IsClientInGame(i) || IsFakeClient(i))
			continue;

		if(!CheckCommandAccess(i, "sm_namefilter2_notify", ADMFLAG_GENERIC))
			continue;

		PrintToChat(i, CHAT_PREFIX ... " \x07FF6060%s\x01 (#%d) was renamed to \x0760FF60%s\x01", g_sOriginalName[client], GetClientUserId(client), sNewName);
	}
}

void NotifyClientRenamed(int client, const char[] sNewName, bool bReplaced)
{
	if(bReplaced)
		PrintToChat(client, CHAT_PREFIX ... " Your name was unable to be filtered and was replaced with \x0760FF60%s\x01.", sNewName);
	else
		PrintToChat(client, CHAT_PREFIX ... " Your name was filtered to \x0760FF60%s\x01.", sNewName);
}

public Action Event_ChangeName(Event event, const char[] name, bool dontBroadcast)
{
	int client = GetClientOfUserId(event.GetInt("userid"));
	if(g_iBlockNameChangeEvents[client])
	{
		g_iBlockNameChangeEvents[client]--;
		SetEventBroadcast(event, true);
		return Plugin_Handled;
	}

	return Plugin_Continue;
}

public Action UserMessage_SayText2(UserMsg msg_id, BfRead msg, const int[] players, int playersNum, bool reliable, bool init)
{
	if(!reliable)
		return Plugin_Continue;

	int client;
	char sMessage[32];
	char sOldName[MAX_NAME_LENGTH];
	char sNewName[MAX_NAME_LENGTH];

	if(GetUserMessageType() == UM_Protobuf)
	{
		PbReadString(msg, "msg_name", sMessage, sizeof(sMessage));

		if(!(sMessage[0] == '#' && StrContains(sMessage, "Name_Change") != -1))
			return Plugin_Continue;

		client = PbReadInt(msg, "ent_idx");
		PbReadString(msg, "params", sOldName, sizeof(sOldName), 1);
		PbReadString(msg, "params", sNewName, sizeof(sNewName), 2);
	}
	else
	{
		client = BfReadByte(msg);
		BfReadByte(msg);
		BfReadString(msg, sMessage, sizeof(sMessage));

		if(!(sMessage[0] == '#' && StrContains(sMessage, "Name_Change") != -1))
			return Plugin_Continue;

		BfReadString(msg, sOldName, sizeof(sOldName));
		BfReadString(msg, sNewName, sizeof(sNewName));
	}

	if(client < 1 || client > MaxClients)
		return Plugin_Continue;

	if(g_iBlockNameChangeEvents[client])
	{
		g_iBlockNameChangeEvents[client]--;
		return Plugin_Handled;
	}

	// the name we gave them (Timer_ChangeName's re-apply or any later echo of
	// it); let it broadcast but keep the original it was filtered from
	if(g_sAssignedName[client][0] && StrEqual(sNewName, g_sAssignedName[client]))
		return Plugin_Continue;

	strcopy(g_sOriginalName[client], MAX_NAME_LENGTH, sNewName);
	g_sAssignedName[client][0] = '\0';

	if(FilterName(client, sNewName))
	{
		strcopy(g_sAssignedName[client], MAX_NAME_LENGTH, sNewName);

		// CCSPlayer::ChangeName sends this SayText2 before it fires the event
		// and stores the new name, so a SetClientName from in here is undone
		// as soon as we return. Re-apply later instead, even when the filtered
		// name equals the old one: 3 = this change's event, then the timer's
		// SayText2 and event
		g_iBlockNameChangeEvents[client] = 3;

		DataPack pack = new DataPack();
		pack.WriteCell(GetClientUserId(client));
		pack.WriteString(sNewName);
		pack.WriteCell(g_bLastFilterReplaced);

		CreateTimer(0.1, Timer_ChangeName, pack);

		return Plugin_Handled;
	}

	return Plugin_Continue;
}

public Action Timer_ChangeName(Handle timer, any data)
{
	DataPack pack = view_as<DataPack>(data);
	pack.Reset();

	int client = GetClientOfUserId(pack.ReadCell());
	char sName[MAX_NAME_LENGTH];
	pack.ReadString(sName, sizeof(sName));
	bool bReplaced = view_as<bool>(pack.ReadCell());

	delete pack;

	if(client)
	{
		SetClientName(client, sName);
		NotifyAdminsFiltered(client, sName, bReplaced);
		NotifyClientRenamed(client, sName, bReplaced);
	}

	return Plugin_Stop;
}

public Action Command_OriginalName(int client, int args)
{
	if(args < 1)
	{
		ReplyToCommand(client, "[SM] Usage: sm_originalname <target>");
		return Plugin_Handled;
	}

	char sPattern[MAX_TARGET_LENGTH];
	GetCmdArg(1, sPattern, sizeof(sPattern));

	char sTargetName[MAX_TARGET_LENGTH];
	int aTargets[MAXPLAYERS];
	bool bTnIsMl;

	int iCount = ProcessTargetString(sPattern, client, aTargets, MAXPLAYERS,
		COMMAND_FILTER_CONNECTED | COMMAND_FILTER_NO_IMMUNITY,
		sTargetName, sizeof(sTargetName), bTnIsMl);

	if(iCount <= 0)
	{
		ReplyToTargetError(client, iCount);
		return Plugin_Handled;
	}

	for(int i = 0; i < iCount; i++)
	{
		char sCurrent[MAX_NAME_LENGTH];
		GetClientName(aTargets[i], sCurrent, sizeof(sCurrent));

		if(StrEqual(sCurrent, g_sOriginalName[aTargets[i]]))
			ReplyToCommand(client, "[SM] %N's name was not changed.", aTargets[i]);
		else
			ReplyToCommand(client, "[SM] %N's original name: %s", aTargets[i], g_sOriginalName[aTargets[i]]);
	}

	return Plugin_Handled;
}

public Action Command_ChangedNames(int client, int args)
{
	int iFound = 0;
	char sCurrent[MAX_NAME_LENGTH];

	for(int i = 1; i <= MaxClients; i++)
	{
		if(!IsClientConnected(i) || IsFakeClient(i))
			continue;

		GetClientName(i, sCurrent, sizeof(sCurrent));
		if(StrEqual(sCurrent, g_sOriginalName[i]))
			continue;

		PrintToConsole(client, "%s - original name: %s", sCurrent, g_sOriginalName[i]);
		iFound++;
	}

	if(!iFound)
		PrintToConsole(client, "[SM] No changed names.");
	else if(client && GetCmdReplySource() == SM_REPLY_TO_CHAT)
		PrintToChat(client, "[SM] %d changed name%s listed in console.", iFound, (iFound == 1) ? "" : "s");

	return Plugin_Handled;
}

public Action Command_Reload(int client, int args)
{
	LoadConfig();
	ReplyToCommand(client, "[SM] NameFilter2 config reloaded.");
	return Plugin_Handled;
}

void CloseRegexList(ArrayList list)
{
	if(!list)
		return;

	for(int i = 0; i < list.Length; i++)
	{
		Handle hRegex = list.Get(i);
		CloseHandle(hRegex);
	}
	delete list;
}

void LoadConfig()
{
	CloseRegexList(g_AdvertExprs);
	g_AdvertExprs = null;
	CloseRegexList(g_BannedExprs);
	g_BannedExprs = null;

	delete g_ReplacementNames;
	delete g_ConfusableFrom;
	delete g_ConfusableTo;
	delete g_WhitelistCps;

	static char sConfigFile[PLATFORM_MAX_PATH];
	BuildPath(Path_SM, sConfigFile, sizeof(sConfigFile), "configs/NameFilter2.cfg");
	if(!FileExists(sConfigFile))
		SetFailState("Could not find config: \"%s\"", sConfigFile);

	KeyValues Config = new KeyValues("NameFilter2");
	if(!Config.ImportFromFile(sConfigFile))
	{
		delete Config;
		SetFailState("ImportFromFile() failed!");
	}

	char sWhitelist[64] = "äöüÄÖܧğĞšŠ";
	if(Config.JumpToKey("settings"))
	{
		g_iMinNameLength = Config.GetNum("min_length", 2);
		g_iMinSurvivedPct = Config.GetNum("min_survived_letters", 50);
		g_iKeepTypeableRun = Config.GetNum("keep_typeable_run", 5);
		Config.GetString("whitelist", sWhitelist, sizeof(sWhitelist), sWhitelist);
		Config.GoBack();
	}

	g_WhitelistCps = new ArrayList();
	int iPos = 0;
	while(sWhitelist[iPos] != '\0')
	{
		int cp = DecodeUTF8Char(sWhitelist, iPos);
		if(cp > 0x7E)
			g_WhitelistCps.Push(cp);
	}

	static char sBuffer[256];
	char sError[256];
	RegexError iError;

	g_ConfusableFrom = new ArrayList(ByteCountToCells(16));
	g_ConfusableTo = new ArrayList(ByteCountToCells(16));
	if(Config.JumpToKey("confusables"))
	{
		if(Config.GotoFirstSubKey(false))
		{
			do
			{
				char sFrom[16];
				Config.GetSectionName(sFrom, sizeof(sFrom));
				Config.GetString(NULL_STRING, sBuffer, sizeof(sBuffer));

				if(sFrom[0])
				{
					g_ConfusableFrom.PushString(sFrom);
					g_ConfusableTo.PushString(sBuffer);
				}
			} while(Config.GotoNextKey(false));
			Config.GoBack();
		}
		Config.GoBack();
	}

	g_AdvertExprs = new ArrayList();
	if(Config.JumpToKey("adverts"))
	{
		if(Config.GotoFirstSubKey(false))
		{
			do
			{
				Config.GetString(NULL_STRING, sBuffer, sizeof(sBuffer));

				Handle hRegex = CompileRegex(sBuffer, PCRE_CASELESS, sError, sizeof(sError), iError);
				if(iError != REGEX_ERROR_NONE)
					LogError("Error parsing advert filter \"%s\": %s", sBuffer, sError);
				else
					g_AdvertExprs.Push(hRegex);
			} while(Config.GotoNextKey(false));
			Config.GoBack();
		}
		Config.GoBack();
	}

	g_BannedExprs = new ArrayList();
	if(Config.JumpToKey("banned"))
	{
		if(Config.GotoFirstSubKey(false))
		{
			do
			{
				Config.GetString(NULL_STRING, sBuffer, sizeof(sBuffer));

				Handle hRegex = CompileRegex(sBuffer, PCRE_CASELESS, sError, sizeof(sError), iError);
				if(iError != REGEX_ERROR_NONE)
					LogError("Error parsing banned filter \"%s\": %s", sBuffer, sError);
				else
					g_BannedExprs.Push(hRegex);
			} while(Config.GotoNextKey(false));
			Config.GoBack();
		}
		Config.GoBack();
	}

	g_ReplacementNames = new ArrayList(ByteCountToCells(MAX_NAME_LENGTH));
	if(Config.JumpToKey("names"))
	{
		if(Config.GotoFirstSubKey(false))
		{
			do
			{
				Config.GetString(NULL_STRING, sBuffer, sizeof(sBuffer));

				g_ReplacementNames.PushString(sBuffer);
			} while(Config.GotoNextKey(false));
			Config.GoBack();
		}
		Config.GoBack();
	}

	if(!g_ReplacementNames.Length)
	{
		LogError("Warning, you didn't specify any replacement names!");
		g_ReplacementNames.PushString("BAD_NAME");
	}

	delete Config;
}

bool FilterName(int client, char[] sName, int Length = MAX_NAME_LENGTH)
{
	g_bLastFilterReplaced = false;

	char sBefore[MAX_NAME_LENGTH];
	strcopy(sBefore, sizeof(sBefore), sName);

	// applies to kept names too, so none can hide characters or pose as another
	StripInvisible(sName);

	char sClean[MAX_NAME_LENGTH];
	strcopy(sClean, sizeof(sClean), sName);

	// a name an admin can target by typing an ASCII run may keep its
	// unicode decoration, as long as the checks below find nothing bad
	bool bKeepOriginal = HasTypeableRun(sClean);
	bool bContentRemoved = false;

	ApplyConfusables(sName, Length);

	int iLettersBefore = CountLetters(sName);

	FoldToASCII(sName, true);
	NormalizeWhitespace(sName);

	// accented Latin letters are only allowed when the name starts with
	// at least two plain Latin letters
	if(!HasLatinPrefix(sName))
	{
		FoldToASCII(sName, false);
		NormalizeWhitespace(sName);
	}

	// folding lost too many of the name's letters; the remnant no longer
	// resembles the name the player chose. Still run the advert/banned
	// checks on the remnant first if the original might be kept
	bool bSurvivedFail = CountLetters(sName) * 100 < iLettersBefore * g_iMinSurvivedPct;
	if(bSurvivedFail && !bKeepOriginal)
	{
		AssignReplacementName(client, sName, Length);
		return true;
	}

	RegexError iError;

	for(int i = 0; i < g_AdvertExprs.Length; i++)
	{
		Handle hRegex = g_AdvertExprs.Get(i);

		// SourceMod Regex bug, bounded loop
		int Guard;
		for(Guard = 0; Guard < 100; Guard++)
		{
			if(!strlen(sName))
				break;

			int Match = MatchRegex(hRegex, sName, iError);
			if(iError != REGEX_ERROR_NONE)
			{
				LogError("Regex Error: %d", iError);
				break;
			}

			if(Match <= 0)
				break;

			char sMatch[MAX_NAME_LENGTH];
			if(!GetRegexSubString(hRegex, 0, sMatch, sizeof(sMatch)) || !sMatch[0])
				break;

			if(ReplaceStringEx(sName, Length, sMatch, "") == -1)
				break;

			bContentRemoved = true;
		}
		if(Guard == 100)
			LogError("SourceMod Regex failed! \"%s\"", sName);
	}

	NormalizeWhitespace(sName);

	for(int i = 0; i < g_BannedExprs.Length; i++)
	{
		if(!strlen(sName))
			break;

		Handle hRegex = g_BannedExprs.Get(i);
		int Match = MatchRegex(hRegex, sName, iError);
		if(iError != REGEX_ERROR_NONE)
		{
			LogError("Regex Error: %d", iError);
			continue;
		}

		if(Match <= 0)
			continue;

		AssignReplacementName(client, sName, Length);
		return true;
	}

	TrimString(sName);

	if(strlen(sName) < g_iMinNameLength || !HasLetterOrDigit(sName))
	{
		AssignReplacementName(client, sName, Length);
		return true;
	}

	if(bKeepOriginal && !bContentRemoved)
	{
		strcopy(sName, Length, sClean);
		return !StrEqual(sBefore, sClean);
	}

	if(bSurvivedFail)
	{
		AssignReplacementName(client, sName, Length);
		return true;
	}

	return !StrEqual(sBefore, sName);
}

// removes characters that render as nothing or reorder the text around them
// (zero-width, bidi controls, fillers, tags) and caps stacked combining marks
void StripInvisible(char[] sName)
{
	int r = 0;
	int w = 0;
	int iMarks = 0;

	while(sName[r] != '\0')
	{
		int rStart = r;
		int cp = DecodeUTF8Char(sName, r);
		if(cp < 0 || IsInvisibleCp(cp))
			continue;

		if(IsCombiningMarkCp(cp))
		{
			if(++iMarks > MAX_STACKED_MARKS)
				continue;
		}
		else
			iMarks = 0;

		for(int k = rStart; k < r; k++)
			sName[w++] = sName[k];
	}
	sName[w] = '\0';
}

bool IsInvisibleCp(int cp)
{
	return cp < 0x20 || (cp >= 0x7F && cp <= 0x9F) // C0/C1 controls, DEL
		|| cp == 0xAD                        // soft hyphen
		|| cp == 0x34F                       // combining grapheme joiner
		|| cp == 0x61C                       // arabic letter mark
		|| cp == 0x115F || cp == 0x1160      // hangul fillers
		|| cp == 0x3164 || cp == 0xFFA0      // hangul fillers
		|| cp == 0x17B4 || cp == 0x17B5      // khmer inherent vowels
		|| (cp >= 0x180B && cp <= 0x180F)    // mongolian selectors, vowel separator
		|| (cp >= 0x200B && cp <= 0x200F)    // zero-width space/joiners, LRM/RLM
		|| (cp >= 0x2028 && cp <= 0x202E)    // line/paragraph separators, bidi embeds/overrides
		|| (cp >= 0x2060 && cp <= 0x206F)    // word joiner, invisible operators, bidi isolates
		|| cp == 0x2800                      // braille blank
		|| (cp >= 0xFE00 && cp <= 0xFE0F)    // variation selectors
		|| cp == 0xFEFF                      // zero-width no-break space (BOM)
		|| (cp >= 0xFFF9 && cp <= 0xFFFB)    // interlinear annotation
		|| (cp >= 0x1D173 && cp <= 0x1D17A)  // musical formatting
		|| (cp >= 0xE0000 && cp <= 0xE0FFF); // tags, variation selectors supplement
}

bool IsCombiningMarkCp(int cp)
{
	return (cp >= 0x300 && cp <= 0x36F)  // combining diacritical marks
		|| (cp >= 0x1AB0 && cp <= 0x1AFF) // extended
		|| (cp >= 0x1DC0 && cp <= 0x1DFF) // supplement
		|| (cp >= 0x20D0 && cp <= 0x20FF) // for symbols
		|| (cp >= 0xFE20 && cp <= 0xFE2F); // half marks
}

void ApplyConfusables(char[] sName, int Length)
{
	char sFrom[16];
	char sTo[16];

	for(int i = 0; i < g_ConfusableFrom.Length; i++)
	{
		g_ConfusableFrom.GetString(i, sFrom, sizeof(sFrom));
		g_ConfusableTo.GetString(i, sTo, sizeof(sTo));

		if(sFrom[0])
			ReplaceString(sName, Length, sFrom, sTo, true);
	}
}

// decodes + folds in-place; output is never longer than input.
// whitelisted codepoints are always kept; accented Latin only when
// bAllowAccents, otherwise it is reduced to its base letter
void FoldToASCII(char[] sName, bool bAllowAccents)
{
	int r = 0;
	int w = 0;

	while(sName[r] != '\0')
	{
		int rStart = r;
		int cp = DecodeUTF8Char(sName, r);
		if(cp < 0)
			continue;

		int c = FoldCodepoint(cp);
		if(c > 0)
		{
			sName[w++] = c;
			continue;
		}

		if(IsWhitelistedCp(cp) || (bAllowAccents && IsAccentedLatin(cp)))
		{
			for(int k = rStart; k < r; k++)
				sName[w++] = sName[k];
			continue;
		}

		// every codepoint FoldLatinLetter maps is >= 2 UTF-8 bytes
		char sBase[3];
		int iBase = FoldLatinLetter(cp, sBase, sizeof(sBase));
		for(int k = 0; k < iBase; k++)
			sName[w++] = sBase[k];
	}
	sName[w] = '\0';
}

int CountLetters(const char[] s)
{
	int i = 0;
	int iLetters = 0;

	while(s[i] != '\0')
	{
		int cp = DecodeUTF8Char(s, i);
		if(cp > 0 && IsLetterCp(cp))
			iLetters++;
	}

	return iLetters;
}

// letters that either survive folding (ASCII, foldable, kept accents) or
// belong to an alphabetic script that FoldToASCII strips
bool IsLetterCp(int cp)
{
	int c = FoldCodepoint(cp);
	if(c)
		return IsCharAlpha(c);

	char sBase[3];
	if(IsAccentedLatin(cp) || FoldLatinLetter(cp, sBase, sizeof(sBase)))
		return true;

	return (cp >= 0x370 && cp <= 0x3FF)   // Greek
		|| (cp >= 0x400 && cp <= 0x52F)   // Cyrillic
		|| (cp >= 0x530 && cp <= 0x58F)   // Armenian
		|| (cp >= 0x590 && cp <= 0x5FF)   // Hebrew
		|| (cp >= 0x600 && cp <= 0x6FF)   // Arabic
		|| (cp >= 0x900 && cp <= 0xDFF)   // Indic scripts
		|| (cp >= 0xE00 && cp <= 0xE7F)   // Thai
		|| (cp >= 0x1E00 && cp <= 0x1FFF) // Latin ext. additional, Greek ext.
		|| (cp >= 0x3040 && cp <= 0x30FF) // kana
		|| (cp >= 0x3400 && cp <= 0x9FFF) // CJK
		|| (cp >= 0xAC00 && cp <= 0xD7AF);// Hangul
}

bool HasLetterOrDigit(const char[] s)
{
	int i = 0;
	while(s[i] != '\0')
	{
		int cp = DecodeUTF8Char(s, i);
		if(cp > 0 && (IsLetterCp(cp) || (cp >= '0' && cp <= '9')))
			return true;
	}
	return false;
}

// true if the name has a contiguous printable-ASCII run containing at
// least g_iKeepTypeableRun letters/digits; an admin can target such a
// name without being able to type its unicode parts
bool HasTypeableRun(const char[] s)
{
	if(g_iKeepTypeableRun <= 0)
		return false;

	int iRun = 0;
	for(int i = 0; s[i] != '\0'; i++)
	{
		int c = s[i] & 0xFF;
		if(c < 0x20 || c > 0x7E)
		{
			iRun = 0;
			continue;
		}

		if(IsCharAlpha(c) || IsCharNumeric(c))
		{
			if(++iRun >= g_iKeepTypeableRun)
				return true;
		}
	}

	return false;
}

bool HasLatinPrefix(const char[] sName)
{
	return IsCharAlpha(sName[0]) && IsCharAlpha(sName[1]);
}

bool IsWhitelistedCp(int cp)
{
	return g_WhitelistCps.FindValue(cp) != -1;
}

bool IsAccentedLatin(int cp)
{
	if(cp >= 0xC0 && cp <= 0xFF) // Latin-1 letters
		return cp != 0xD7 && cp != 0xF7; // × ÷
	return cp >= 0x100 && cp <= 0x17F; // Latin Extended-A
}

// returns the codepoint and advances i, or -1 on an invalid byte (advances past it)
int DecodeUTF8Char(const char[] s, int &i)
{
	int b = s[i] & 0xFF;
	if(b < 0x80)
	{
		i++;
		return b;
	}

	int len;
	int cp;
	if((b & 0xE0) == 0xC0)      { len = 2; cp = b & 0x1F; }
	else if((b & 0xF0) == 0xE0) { len = 3; cp = b & 0x0F; }
	else if((b & 0xF8) == 0xF0) { len = 4; cp = b & 0x07; }
	else
	{
		i++;
		return -1;
	}

	for(int k = 1; k < len; k++)
	{
		int cb = s[i + k] & 0xFF;
		if((cb & 0xC0) != 0x80)
		{
			i++;
			return -1;
		}
		cp = (cp << 6) | (cb & 0x3F);
	}

	i += len;
	return cp;
}

// writes the plain ASCII form of a Latin letter with diacritics, stroke or
// ligature (Å -> A, ø -> o, æ -> ae) to sOut; returns its length, 0 if none
int FoldLatinLetter(int cp, char[] sOut, int Length)
{
	char sLig[3];
	switch(cp)
	{
		case 0xC6, 0x1E2, 0x1FC: strcopy(sLig, sizeof(sLig), "AE"); // Æ Ǣ Ǽ
		case 0xDE: strcopy(sLig, sizeof(sLig), "Th"); // Þ
		case 0xDF: strcopy(sLig, sizeof(sLig), "ss"); // ß
		case 0xE6, 0x1E3, 0x1FD: strcopy(sLig, sizeof(sLig), "ae"); // æ ǣ ǽ
		case 0xFE: strcopy(sLig, sizeof(sLig), "th"); // þ
		case 0x132: strcopy(sLig, sizeof(sLig), "IJ"); // IJ
		case 0x133: strcopy(sLig, sizeof(sLig), "ij"); // ij
		case 0x152: strcopy(sLig, sizeof(sLig), "OE"); // Œ
		case 0x153: strcopy(sLig, sizeof(sLig), "oe"); // œ
		case 0x1C4, 0x1F1: strcopy(sLig, sizeof(sLig), "DZ"); // DŽ DZ
		case 0x1C5, 0x1F2: strcopy(sLig, sizeof(sLig), "Dz"); // Dž Dz
		case 0x1C6, 0x1F3: strcopy(sLig, sizeof(sLig), "dz"); // dž dz
		case 0x1C7: strcopy(sLig, sizeof(sLig), "LJ"); // LJ
		case 0x1C8: strcopy(sLig, sizeof(sLig), "Lj"); // Lj
		case 0x1C9: strcopy(sLig, sizeof(sLig), "lj"); // lj
		case 0x1CA: strcopy(sLig, sizeof(sLig), "NJ"); // NJ
		case 0x1CB: strcopy(sLig, sizeof(sLig), "Nj"); // Nj
		case 0x1CC: strcopy(sLig, sizeof(sLig), "nj"); // nj
		case 0x1E9E: strcopy(sLig, sizeof(sLig), "SS"); // ẞ
	}
	if(sLig[0])
		return strcopy(sOut, Length, sLig);

	// '.' = no base letter
	static const char aLatinBase[] = "AAAAAA.CEEEEIIIIDNOOOOO.OUUUUY.." // U+00C0
		... "aaaaaa.ceeeeiiiidnooooo.ouuuuy.y" // U+00E0
		... "AaAaAaCcCcCcCcDdDdEeEeEeEeEeGgGg" // U+0100
		... "GgGgHhHhIiIiIiIiIi..JjKkkLlLlLlL" // U+0120
		... "lLlNnNnNnnNnOoOoOo..RrRrRrSsSsSs" // U+0140
		... "SsTtTtTtUuUuUuUuUuUuWwYyYZzZzZzs" // U+0160
		... "bBBb...CcDDDd.E..FfG...IKkl..NnO" // U+0180
		... "Oo..Pp.....tTtTUu.VYyZz........." // U+01A0
		... ".............AaIiOoUuUuUuUuUu.Aa" // U+01C0
		... "Aa..GgGgKkOoOo..j...Gg..NnAa..Oo" // U+01E0
		... "AaAaEeEeIiIiOoOoRrRrUuUuSsTt..Hh" // U+0200
		... "Nd..ZzAaEeOoOoOoOoYylntj..ACcLTs" // U+0220
		... "z..BUAEeJj.qRrYy" // U+0240
		;
	static const char aLatinExtBase[] = "AaBbBbBbCcDdDdDdDdDdEeEeEeEeEeFf" // U+1E00
		... "GgHhHhHhHhHhIiIiKkKkKkLlLlLlLlMm" // U+1E20
		... "MmMmNnNnNnNnOoOoOoOoPpPpRrRrRrRr" // U+1E40
		... "SsSsSsSsSsTtTtTtTtUuUuUuUuUuVvVv" // U+1E60
		... "WwWwWwWwWwXxXxYyZzZzZzhtwyasss.." // U+1E80
		... "AaAaAaAaAaAaAaAaAaAaAaAaEeEeEeEe" // U+1EA0
		... "EeEeEeEeIiIiOoOoOoOoOoOoOoOoOoOo" // U+1EC0
		... "OoOoUuUuUuUuUuUuUuYyYyYyYy....Yy" // U+1EE0
		;

	int c = '.';
	if(cp >= 0xC0 && cp <= 0x24F)
		c = aLatinBase[cp - 0xC0];
	else if(cp >= 0x1E00 && cp <= 0x1EFF)
		c = aLatinExtBase[cp - 0x1E00];

	if(c == '.')
		return 0;

	sOut[0] = c;
	sOut[1] = '\0';
	return 1;
}

// maps a codepoint to printable ASCII, or 0 to strip it
int FoldCodepoint(int cp)
{
	if(cp >= 0x20 && cp <= 0x7E)
		return cp;

	if(cp < 0x20 || cp == 0x7F)
		return 0;

	if(cp == 0xA0 || cp == 0x3000 // nbsp / ideographic space
	|| (cp >= 0x2000 && cp <= 0x200A) // en/em/thin/hair spaces
	|| cp == 0x202F || cp == 0x205F) // narrow nbsp / math space
		return ' ';

	if(cp >= 0xFF01 && cp <= 0xFF5E) // fullwidth ASCII forms
		return cp - 0xFEE0;

	if(cp >= 0x1D400 && cp <= 0x1D6A3) // 13 styled Latin alphabets of 52
	{
		int r = (cp - 0x1D400) % 52;
		return (r < 26) ? ('A' + r) : ('a' + r - 26);
	}

	if(cp == 0x1D6A4) // dotless i
		return 'i';
	if(cp == 0x1D6A5) // dotless j
		return 'j';

	if(cp >= 0x1D7CE && cp <= 0x1D7FF) // styled math digits, 5 sets of 10
		return '0' + ((cp - 0x1D7CE) % 10);

	if(cp >= 0x24B6 && cp <= 0x24CF) // circled A-Z
		return 'A' + (cp - 0x24B6);
	if(cp >= 0x24D0 && cp <= 0x24E9) // circled a-z
		return 'a' + (cp - 0x24D0);
	if(cp >= 0x2460 && cp <= 0x2468) // circled 1-9
		return '1' + (cp - 0x2460);
	if(cp == 0x24EA) // circled 0
		return '0';

	if(cp >= 0x249C && cp <= 0x24B5) // parenthesized a-z
		return 'a' + (cp - 0x249C);
	if(cp >= 0x2474 && cp <= 0x247C) // parenthesized 1-9
		return '1' + (cp - 0x2474);
	if(cp >= 0x2488 && cp <= 0x2490) // digit full stop 1.-9.
		return '1' + (cp - 0x2488);
	if(cp >= 0x24F5 && cp <= 0x24FD) // double circled 1-9
		return '1' + (cp - 0x24F5);
	if(cp == 0x24FF) // negative circled 0
		return '0';
	if(cp >= 0x2776 && cp <= 0x277E) // dingbat negative circled 1-9
		return '1' + (cp - 0x2776);
	if(cp >= 0x2780 && cp <= 0x2788) // dingbat circled sans-serif 1-9
		return '1' + (cp - 0x2780);
	if(cp >= 0x278A && cp <= 0x2792) // dingbat negative circled sans-serif 1-9
		return '1' + (cp - 0x278A);

	if(cp >= 0x1F110 && cp <= 0x1F129) // parenthesized A-Z
		return 'A' + (cp - 0x1F110);
	if(cp >= 0x1F130 && cp <= 0x1F149) // squared A-Z
		return 'A' + (cp - 0x1F130);
	if(cp >= 0x1F150 && cp <= 0x1F169) // negative circled A-Z
		return 'A' + (cp - 0x1F150);
	if(cp >= 0x1F170 && cp <= 0x1F189) // negative squared A-Z
		return 'A' + (cp - 0x1F170);
	if(cp >= 0x1F1E6 && cp <= 0x1F1FF) // regional indicator (flag letter) A-Z
		return 'A' + (cp - 0x1F1E6);

	if(cp == 0xB9) // superscript 1
		return '1';
	if(cp == 0xB2 || cp == 0xB3) // superscript 2-3
		return '0' + (cp - 0xB0);
	if(cp == 0x2070) // superscript 0
		return '0';
	if(cp >= 0x2074 && cp <= 0x2079) // superscript 4-9
		return '4' + (cp - 0x2074);
	if(cp >= 0x2080 && cp <= 0x2089) // subscript 0-9
		return '0' + (cp - 0x2080);

	// superscript (modifier) letters, small capitals and letterlike symbols
	// (the BMP "holes" in the styled math alphabets), scattered codepoints
	static const int aLetterCps[] = {
		0x1D2C, 0x1D2E, 0x1D30, 0x1D31, 0x1D33, 0x1D34, 0x1D35, 0x1D36,  // ᴬ ᴮ ᴰ ᴱ ᴳ ᴴ ᴵ ᴶ
		0x1D37, 0x1D38, 0x1D39, 0x1D3A, 0x1D3C, 0x1D3E, 0x1D3F, 0x1D40,  // ᴷ ᴸ ᴹ ᴺ ᴼ ᴾ ᴿ ᵀ
		0x1D41, 0x1D42,                                                  // ᵁ ᵂ
		0x1D43, 0x1D47, 0x1D9C, 0x1D48, 0x1D49, 0x1DA0, 0x1D4D, 0x02B0, // ᵃ ᵇ ᶜ ᵈ ᵉ ᶠ ᵍ ʰ
		0x2071, 0x02B2, 0x1D4F, 0x02E1, 0x1D50, 0x207F, 0x1D52, 0x1D56, // ⁱ ʲ ᵏ ˡ ᵐ ⁿ ᵒ ᵖ
		0x107A5, 0x02B3, 0x02E2, 0x1D57, 0x1D58, 0x1D5B, 0x02B7, 0x02E3, // 𐞥 ʳ ˢ ᵗ ᵘ ᵛ ʷ ˣ
		0x02B8, 0x1DBB,                                                  // ʸ ᶻ
		0x1D00, 0x0299, 0x1D04, 0x1D05, 0x1D07, 0xA730, 0x0262, 0x029C, // ᴀ ʙ ᴄ ᴅ ᴇ ꜰ ɢ ʜ
		0x026A, 0x1D0A, 0x1D0B, 0x029F, 0x1D0D, 0x0274, 0x1D0F, 0x1D18, // ɪ ᴊ ᴋ ʟ ᴍ ɴ ᴏ ᴘ
		0x0280, 0xA731, 0x1D1B, 0x1D1C, 0x1D20, 0x1D21, 0x028F, 0x1D22, // ʀ ꜱ ᴛ ᴜ ᴠ ᴡ ʏ ᴢ
		0x2102, 0x210A, 0x210B, 0x210C, 0x210D, 0x210E, 0x210F, 0x2110, // ℂ ℊ ℋ ℌ ℍ ℎ ℏ ℐ
		0x2111, 0x2112, 0x2113, 0x2115, 0x2119, 0x211A, 0x211B, 0x211C, // ℑ ℒ ℓ ℕ ℙ ℚ ℛ ℜ
		0x211D, 0x2124, 0x2128, 0x212A, 0x212B, 0x212C, 0x212D, 0x212F, // ℝ ℤ ℨ K(elvin) Å ℬ ℭ ℯ
		0x2130, 0x2131, 0x2133, 0x2134, 0x2139, 0x2145, 0x2146, 0x2147, // ℰ ℱ ℳ ℴ ℹ ⅅ ⅆ ⅇ
		0x2148, 0x2149                                                  // ⅈ ⅉ
	};
	static const char aLetterAscii[] = "ABDEGHIJKLMNOPRTUW"
	                               ... "abcdefghijklmnopqrstuvwxyz"
	                               ... "abcdefghijklmnoprstuvwyz"
	                               ... "CgHHHhhIILlNPQRRRZZKABCeEFMoiDdeij";

	for(int i = 0; i < sizeof(aLetterCps); i++)
	{
		if(aLetterCps[i] == cp)
			return aLetterAscii[i];
	}

	return 0;
}

void NormalizeWhitespace(char[] sName)
{
	int r = 0;
	int w = 0;
	bool bLastSpace = false;

	while(sName[r] != '\0')
	{
		char c = sName[r++];
		if(c == ' ' || c == '\t')
		{
			if(bLastSpace)
				continue;
			bLastSpace = true;
			sName[w++] = ' ';
		}
		else
		{
			bLastSpace = false;
			sName[w++] = c;
		}
	}
	sName[w] = '\0';

	TrimString(sName);
}

void AssignReplacementName(int client, char[] sName, int Length)
{
	g_bLastFilterReplaced = true;

	int iCount = g_ReplacementNames.Length;
	int iBase = client % iCount;
	char sCandidate[MAX_NAME_LENGTH];

	for(int i = 0; i < iCount; i++)
	{
		g_ReplacementNames.GetString((iBase + i) % iCount, sCandidate, sizeof(sCandidate));

		bool bTaken = false;
		for(int j = 1; j <= MaxClients; j++)
		{
			if(j == client || !IsClientConnected(j))
				continue;

			char sOther[MAX_NAME_LENGTH];
			GetClientName(j, sOther, sizeof(sOther));
			if(StrEqual(sOther, sCandidate))
			{
				bTaken = true;
				break;
			}
		}

		if(!bTaken)
		{
			strcopy(sName, Length, sCandidate);
			return;
		}
	}

	g_ReplacementNames.GetString(iBase, sCandidate, sizeof(sCandidate));
	Format(sName, Length, "%s %d", sCandidate, GetClientUserId(client));
}