/**

*

* @package utf

* @version $Id: utf_normalizer.php 8479 2008-03-29 00:22:48Z naderman $

* @copyright (c) 2005 phpBB Group

* @license http://opensource.org/licenses/gpl-license.php GNU Public License

*

*/

/**

*/

if (!defined('IN_PHPBB'))

{

	exit;

}

/**

* Some Unicode characters encoded in UTF-8

*

* Preserved for compatibility

*/

define('UTF8_REPLACEMENT', "\xEF\xBF\xBD");

define('UTF8_MAX', "\xF4\x8F\xBF\xBF");

define('UTF8_FFFE', "\xEF\xBF\xBE");

define('UTF8_FFFF', "\xEF\xBF\xBF");

define('UTF8_SURROGATE_FIRST', "\xED\xA0\x80");

define('UTF8_SURROGATE_LAST', "\xED\xBF\xBF");

define('UTF8_HANGUL_FIRST', "\xEA\xB0\x80");

define('UTF8_HANGUL_LAST', "\xED\x9E\xA3");

define('UTF8_CJK_FIRST', "\xE4\xB8\x80");

define('UTF8_CJK_LAST', "\xE9\xBE\xBB");

define('UTF8_CJK_B_FIRST', "\xF0\xA0\x80\x80");

define('UTF8_CJK_B_LAST', "\xF0\xAA\x9B\x96");

// Unset global variables

unset($GLOBALS['utf_jamo_index'], $GLOBALS['utf_jamo_type'], $GLOBALS['utf_nfc_qc'], $GLOBALS['utf_combining_class'], $GLOBALS['utf_canonical_comp'], $GLOBALS['utf_canonical_decomp'], $GLOBALS['utf_nfkc_qc'], $GLOBALS['utf_compatibility_decomp']);

// NFC_QC and NFKC_QC values

define('UNICODE_QC_MAYBE', 0);

define('UNICODE_QC_NO', 1);

// Contains all the ASCII characters appearing in UTF-8, sorted by frequency

define('UTF8_ASCII_RANGE', "\x20\x65\x69\x61\x73\x6E\x74\x72\x6F\x6C\x75\x64\x5D\x5B\x63\x6D\x70\x27\x0A\x67\x7C\x68\x76\x2E\x66\x62\x2C\x3A\x3D\x2D\x71\x31\x30\x43\x32\x2A\x79\x78\x29\x28\x4C\x39\x41\x53\x2F\x50\x22\x45\x6A\x4D\x49\x6B\x33\x3E\x35\x54\x3C\x44\x34\x7D\x42\x7B\x38\x46\x77\x52\x36\x37\x55\x47\x4E\x3B\x4A\x7A\x56\x23\x48\x4F\x57\x5F\x26\x21\x4B\x3F\x58\x51\x25\x59\x5C\x09\x5A\x2B\x7E\x5E\x24\x40\x60\x7F\x00\x01\x02\x03\x04\x05\x06\x07\x08\x0B\x0C\x0D\x0E\x0F\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1A\x1B\x1C\x1D\x1E\x1F");

// Contains all the tail bytes that can appear in the composition of a UTF-8 char

define('UTF8_TRAILING_BYTES', "\xA9\xA0\xA8\x80\xAA\x99\xA7\xBB\xAB\x89\x94\x82\xB4\xA2\xAE\x83\xB0\xB9\xB8\x93\xAF\xBC\xB3\x81\xA4\xB2\x9C\xA1\xB5\xBE\xBD\xBA\x98\xAD\xB1\x84\x95\xA6\xB6\x88\x8D\x90\xB7\xBF\x92\x85\xA5\x97\x8C\x86\xA3\x8E\x9F\x8F\x87\x91\x9D\xAC\x9E\x8B\x96\x9B\x8A\x9A");

// Constants used by the Hangul [de]composition algorithms

define('UNICODE_HANGUL_SBASE', 0xAC00);

define('UNICODE_HANGUL_LBASE', 0x1100);

define('UNICODE_HANGUL_VBASE', 0x1161);

define('UNICODE_HANGUL_TBASE', 0x11A7);

define('UNICODE_HANGUL_SCOUNT', 11172);

define('UNICODE_HANGUL_LCOUNT', 19);

define('UNICODE_HANGUL_VCOUNT', 21);

define('UNICODE_HANGUL_TCOUNT', 28);

define('UNICODE_HANGUL_NCOUNT', 588);

define('UNICODE_JAMO_L', 0);

define('UNICODE_JAMO_V', 1);

define('UNICODE_JAMO_T', 2);

/**

* Unicode normalization routines

*

* @package utf

*/

class utf_normalizer

{

	/**

	* Validate, cleanup and normalize a string

	*

	* The ultimate convenience function! Clean up invalid UTF-8 sequences,

	* and convert to Normal Form C, canonical composition.

	*

	* @param	string	&$str	The dirty string

	* @return	string			The same string, all shiny and cleaned-up

	*/

	function cleanup(&$str)

	{

		// The string below is the list of all autorized characters, sorted by frequency in latin text

		$pos = strspn($str, "\x20\x65\x69\x61\x73\x6E\x74\x72\x6F\x6C\x75\x64\x5D\x5B\x63\x6D\x70\x27\x0A\x67\x7C\x68\x76\x2E\x66\x62\x2C\x3A\x3D\x2D\x71\x31\x30\x43\x32\x2A\x79\x78\x29\x28\x4C\x39\x41\x53\x2F\x50\x22\x45\x6A\x4D\x49\x6B\x33\x3E\x35\x54\x3C\x44\x34\x7D\x42\x7B\x38\x46\x77\x52\x36\x37\x55\x47\x4E\x3B\x4A\x7A\x56\x23\x48\x4F\x57\x5F\x26\x21\x4B\x3F\x58\x51\x25\x59\x5C\x09\x5A\x2B\x7E\x5E\x24\x40\x60\x7F\x0D");

		$len = strlen($str);

		if ($pos == $len)

		{

			// ASCII strings with no special chars return immediately

			return;

		}

		// Note: we do not check for $GLOBALS['utf_canonical_decomp']. It is assumed they are always loaded together

		if (!isset($GLOBALS['utf_nfc_qc']))

		{

			global $phpbb_root_path, $phpEx;

			include($phpbb_root_path . 'includes/utf/data/utf_nfc_qc.' . $phpEx);

		}

		if (!isset($GLOBALS['utf_canonical_decomp']))

		{

			global $phpbb_root_path, $phpEx;

			include($phpbb_root_path . 'includes/utf/data/utf_canonical_decomp.' . $phpEx);

		}

		// Replace any byte in the range 0x00..0x1F, except for \r, \n and \t

		// We replace those characters with a 0xFF byte, which is illegal in UTF-8 and will in turn be replaced with a UTF replacement char

		$str = strtr(

			$str,

			"\x00\x01\x02\x03\x04\x05\x06\x07\x08\x0B\x0C\x0E\x0F\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1A\x1B\x1C\x1D\x1E\x1F",

			"\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF"

		);

		$str = utf_normalizer::recompose($str, $pos, $len, $GLOBALS['utf_nfc_qc'], $GLOBALS['utf_canonical_decomp']);

	}

	/**

	* Validate and normalize a UTF string to NFC

	*

	* @param	string	&$str	Unchecked UTF string

	* @return	string			The string, validated and in normal form

	*/

	function nfc(&$str)

	{

		$pos = strspn($str, UTF8_ASCII_RANGE);

		$len = strlen($str);

		if ($pos == $len)

		{

			// ASCII strings return immediately

			return;

		}

		if (!isset($GLOBALS['utf_nfc_qc']))

		{

			global $phpbb_root_path, $phpEx;

			include($phpbb_root_path . 'includes/utf/data/utf_nfc_qc.' . $phpEx);

		}

		if (!isset($GLOBALS['utf_canonical_decomp']))

		{

			global $phpbb_root_path, $phpEx;

			include($phpbb_root_path . 'includes/utf/data/utf_canonical_decomp.' . $phpEx);

		}

		$str = utf_normalizer::recompose($str, $pos, $len, $GLOBALS['utf_nfc_qc'], $GLOBALS['utf_canonical_decomp']);

	}

	/**

	* Validate and normalize a UTF string to NFKC

	*

	* @param	string	&$str	Unchecked UTF string

	* @return	string			The string, validated and in normal form

	*/

	function nfkc(&$str)

	{

		$pos = strspn($str, UTF8_ASCII_RANGE);

		$len = strlen($str);

		if ($pos == $len)

		{

			// ASCII strings return immediately

			return;

		}

		if (!isset($GLOBALS['utf_nfkc_qc']))

		{

			global $phpbb_root_path, $phpEx;

			include($phpbb_root_path . 'includes/utf/data/utf_nfkc_qc.' . $phpEx);

		}

		if (!isset($GLOBALS['utf_compatibility_decomp']))

		{

			global $phpbb_root_path, $phpEx;

			include($phpbb_root_path . 'includes/utf/data/utf_compatibility_decomp.' . $phpEx);

		}

		$str = utf_normalizer::recompose($str, $pos, $len, $GLOBALS['utf_nfkc_qc'], $GLOBALS['utf_compatibility_decomp']);

	}

	/**

	* Validate and normalize a UTF string to NFD

	*

	* @param	string	&$str	Unchecked UTF string

	* @return	string			The string, validated and in normal form

	*/

	function nfd(&$str)

	{

		$pos = strspn($str, UTF8_ASCII_RANGE);

		$len = strlen($str);

		if ($pos == $len)

		{

			// ASCII strings return immediately

			return;

		}

		if (!isset($GLOBALS['utf_canonical_decomp']))

		{

			global $phpbb_root_path, $phpEx;

			include($phpbb_root_path . 'includes/utf/data/utf_canonical_decomp.' . $phpEx);

		}

		$str = utf_normalizer::decompose($str, $pos, $len, $GLOBALS['utf_canonical_decomp']);

	}

	/**

	* Validate and normalize a UTF string to NFKD

	*

	* @param	string	&$str	Unchecked UTF string

	* @return	string			The string, validated and in normal form

	*/

	function nfkd(&$str)

	{

		$pos = strspn($str, UTF8_ASCII_RANGE);

		$len = strlen($str);

		if ($pos == $len)

		{

			// ASCII strings return immediately

			return;

		}

		if (!isset($GLOBALS['utf_compatibility_decomp']))

		{

			global $phpbb_root_path, $phpEx;

			include($phpbb_root_path . 'includes/utf/data/utf_compatibility_decomp.' . $phpEx);

		}

		$str = utf_normalizer::decompose($str, $pos, $len, $GLOBALS['utf_compatibility_decomp']);

	}

	/**

	* Recompose a UTF string

	*

	* @param	string	$str			Unchecked UTF string

	* @param	integer	$pos			Position of the first UTF char (in bytes)

	* @param	integer	$len			Length of the string (in bytes)

	* @param	array	&$qc			Quick-check array, passed by reference but never modified

	* @param	array	&$decomp_map	Decomposition mapping, passed by reference but never modified

	* @return	string					The string, validated and recomposed

	*

	* @access	private

	*/

	function recompose($str, $pos, $len, &$qc, &$decomp_map)

	{

		global $utf_combining_class, $utf_canonical_comp, $utf_jamo_type, $utf_jamo_index;

		// Load some commonly-used tables

		if (!isset($utf_jamo_index, $utf_jamo_type, $utf_combining_class))

		{

			global $phpbb_root_path, $phpEx;

			include($phpbb_root_path . 'includes/utf/data/utf_normalizer_common.' . $phpEx);

		}

		// Load the canonical composition table

		if (!isset($utf_canonical_comp))

		{

			global $phpbb_root_path, $phpEx;

			include($phpbb_root_path . 'includes/utf/data/utf_canonical_comp.' . $phpEx);

		}

		// Buffer the last ASCII char before the UTF-8 stuff if applicable

		$tmp = '';

		$i = $tmp_pos = $last_cc = 0;

		$buffer = ($pos) ? array(++$i => $str[$pos - 1]) : array();

		// UTF char length array

		// This array is used to determine the length of a UTF character.

		// Be $c the result of ($str[$pos] & "\xF0") --where $str is the string we're operating on and $pos

		// the position of the cursor--, if $utf_len_mask[$c] does not exist, the byte is an ASCII char.

		// Otherwise, if $utf_len_mask[$c] is greater than 0, we have a the leading byte of a multibyte character

		// whose length is $utf_len_mask[$c] and if it is equal to 0, the byte is a trailing byte.

		$utf_len_mask = array(

			// Leading bytes masks

			"\xC0" => 2, "\xD0" => 2, "\xE0" => 3, "\xF0" => 4,

			// Trailing bytes masks

			"\x80" => 0, "\x90" => 0, "\xA0" => 0, "\xB0" => 0

		);

		$extra_check = array(

			"\xED" => 1, "\xEF" => 1, "\xC0" => 1, "\xC1" => 1, "\xE0" => 1, "\xF0" => 1,

			"\xF4" => 1, "\xF5" => 1, "\xF6" => 1, "\xF7" => 1, "\xF8" => 1, "\xF9" => 1,

			"\xFA" => 1, "\xFB" => 1, "\xFC" => 1, "\xFD" => 1, "\xFE" => 1, "\xFF" => 1

		);

		$utf_validation_mask = array(

			2	=> "\xE0\xC0",

			3	=> "\xF0\xC0\xC0",

			4	=> "\xF8\xC0\xC0\xC0"

		);

		$utf_validation_check = array(

			2	=> "\xC0\x80",

			3	=> "\xE0\x80\x80",

			4	=> "\xF0\x80\x80\x80"

		);

		// Main loop

		do

		{

			// STEP 0: Capture the current char and buffer it

			$c = $str[$pos];

			$c_mask = $c & "\xF0";

			if (isset($utf_len_mask[$c_mask]))

			{

				// Byte at $pos is either a leading byte or a missplaced trailing byte

				if ($utf_len = $utf_len_mask[$c_mask])

				{

					// Capture the char

					$buffer[++$i & 7] = $utf_char = substr($str, $pos, $utf_len);

					// Let's find out if a thorough check is needed

					if (isset($qc[$utf_char]))

					{

						// If the UTF char is in the qc array then it may not be in normal form. We do nothing here, the actual processing is below this "if" block

					}

					else if (isset($utf_combining_class[$utf_char]))

					{

						if ($utf_combining_class[$utf_char] < $last_cc)

						{

							// A combining character that is NOT canonically ordered

						}

						else

						{

							// A combining character that IS canonically ordered, skip to the next char

							$last_cc = $utf_combining_class[$utf_char];

							$pos += $utf_len;

							continue;

						}

					}

					else

					{

						// At this point, $utf_char holds a UTF char that we know is not a NF[K]C_QC and is not a combining character.

						// It can be a singleton, a canonical composite, a replacement char or an even an ill-formed bunch of bytes. Let's find out

						$last_cc = 0;

						// Check that we have the correct number of trailing bytes

						if (($utf_char & $utf_validation_mask[$utf_len]) != $utf_validation_check[$utf_len])

						{

							// Current char isn't well-formed or legal: either one or several trailing bytes are missing, or the Unicode char

							// has been encoded in a five- or six- byte sequence

							if ($utf_char[0] >= "\xF8")

							{

								if ($utf_char[0] < "\xFC")

								{

									$trailing_bytes = 4;

								}

								else if ($utf_char[0] > "\xFD")

								{

									$trailing_bytes = 0;

								}

								else

								{

									$trailing_bytes = 5;

								}

							}

							else

							{

								$trailing_bytes = $utf_len - 1;

							}

							$tmp .= substr($str, $tmp_pos, $pos - $tmp_pos) . UTF8_REPLACEMENT;

							$pos += strspn($str, UTF8_TRAILING_BYTES, ++$pos, $trailing_bytes);

							$tmp_pos = $pos;

							continue;

						}

						if (isset($extra_check[$c]))

						{

							switch ($c)

							{

								// Note: 0xED is quite common in Korean

								case "\xED":

									if ($utf_char >= "\xED\xA0\x80")

									{

										// Surrogates (U+D800..U+DFFF) are not allowed in UTF-8 (UTF sequence 0xEDA080..0xEDBFBF)

										$tmp .= substr($str, $tmp_pos, $pos - $tmp_pos) . UTF8_REPLACEMENT;

										$pos += $utf_len;

										$tmp_pos = $pos;

										continue 2;

									}

								break;

								// Note: 0xEF is quite common in Japanese

								case "\xEF":

									if ($utf_char == "\xEF\xBF\xBE" || $utf_char == "\xEF\xBF\xBF")

									{

										// U+FFFE and U+FFFF are explicitly disallowed (UTF sequence 0xEFBFBE..0xEFBFBF)

										$tmp .= substr($str, $tmp_pos, $pos - $tmp_pos) . UTF8_REPLACEMENT;

										$pos += $utf_len;

										$tmp_pos = $pos;

										continue 2;

									}

								break;

								case "\xC0":

								case "\xC1":

									if ($utf_char <= "\xC1\xBF")

									{

										// Overlong sequence: Unicode char U+0000..U+007F encoded as a double-byte UTF char

										$tmp .= substr($str, $tmp_pos, $pos - $tmp_pos) . UTF8_REPLACEMENT;

										$pos += $utf_len;

										$tmp_pos = $pos;

										continue 2;

									}

								break;

								case "\xE0":

									if ($utf_char <= "\xE0\x9F\xBF")

									{

										// Unicode char U+0000..U+07FF encoded in 3 bytes

										$tmp .= substr($str, $tmp_pos, $pos - $tmp_pos) . UTF8_REPLACEMENT;

										$pos += $utf_len;

										$tmp_pos = $pos;

										continue 2;

									}

								break;

								case "\xF0":

									if ($utf_char <= "\xF0\x8F\xBF\xBF")

									{

										// Unicode char U+0000..U+FFFF encoded in 4 bytes

										$tmp .= substr($str, $tmp_pos, $pos - $tmp_pos) . UTF8_REPLACEMENT;

										$pos += $utf_len;

										$tmp_pos = $pos;

										continue 2;

									}

								break;

								default:

									// Five- and six- byte sequences do not need being checked for here anymore

									if ($utf_char > UTF8_MAX)

									{

										// Out of the Unicode range

										if ($utf_char[0] < "\xF8")

										{

											$trailing_bytes = 3;

										}

										else if ($utf_char[0] < "\xFC")

										{

											$trailing_bytes = 4;

										}

										else if ($utf_char[0] > "\xFD")

										{

											$trailing_bytes = 0;

										}

										else

										{

											$trailing_bytes = 5;

										}

										$tmp .= substr($str, $tmp_pos, $pos - $tmp_pos) . UTF8_REPLACEMENT;

										$pos += strspn($str, UTF8_TRAILING_BYTES, ++$pos, $trailing_bytes);

										$tmp_pos = $pos;

										continue 2;

									}

								break;

							}

						}

						// The char is a valid starter, move the cursor and go on

						$pos += $utf_len;

						continue;

					}

				}

				else

				{

					// A trailing byte came out of nowhere, we will advance the cursor and treat the this byte and all following trailing bytes as if

					// each of them was a Unicode replacement char

					$spn = strspn($str, UTF8_TRAILING_BYTES, $pos);

					$tmp .= substr($str, $tmp_pos, $pos - $tmp_pos) . str_repeat(UTF8_REPLACEMENT, $spn);

					$pos += $spn;

					$tmp_pos = $pos;

					continue;

				}

				// STEP 1: Decompose current char

				// We have found a character that is either:

				//  - in the NFC_QC/NFKC_QC list

				//  - a non-starter char that is not canonically ordered

				//

				// We are going to capture the shortest UTF sequence that satisfies these two conditions:

				//

				//  1 - If the sequence does not start at the begginning of the string, it must begin with a starter,

				// and that starter must not have the NF[K]C_QC property equal to "MAYBE"

				//

				//  2 - If the sequence does not end at the end of the string, it must end with a non-starter and be

				// immediately followed by a starter that is not on the QC list

				//

				$utf_seq = array();

				$last_cc = 0;

				$lpos = $pos;

				$pos += $utf_len;

				if (isset($decomp_map[$utf_char]))

				{

					$_pos = 0;

					$_len = strlen($decomp_map[$utf_char]);

					do

					{

						$_utf_len =& $utf_len_mask[$decomp_map[$utf_char][$_pos] & "\xF0"];

						if (isset($_utf_len))

						{

							$utf_seq[] = substr($decomp_map[$utf_char], $_pos, $_utf_len);

							$_pos += $_utf_len;

						}

						else

						{

							$utf_seq[] = $decomp_map[$utf_char][$_pos];

							++$_pos;

						}

					}

					while ($_pos < $_len);

				}

				else

				{

					// The char is not decomposable

					$utf_seq = array($utf_char);

				}

				// STEP 2: Capture the starter

				// Check out the combining class of the first character of the UTF sequence

				$k = 0;

				if (isset($utf_combining_class[$utf_seq[0]]) || $qc[$utf_char] == UNICODE_QC_MAYBE)

				{

					// Not a starter, inspect previous characters

					// The last 8 characters are kept in a buffer so that we don't have to capture them everytime.

					// This is enough for all real-life strings but even if it wasn't, we can capture characters in backward mode,

					// although it is slower than this method.

					//

					// In the following loop, $j starts at the previous buffered character ($i - 1, because current character is

					// at offset $i) and process them in backward mode until we find a starter.

					//

					// $k is the index on each UTF character inside of our UTF sequence. At this time, $utf_seq contains one or more

					// characters numbered 0 to n. $k starts at 0 and for each char we prepend we pre-decrement it and for numbering

					$starter_found = 0;

					$j_min = max(1, $i - 7);

					for ($j = $i - 1; $j >= $j_min && $lpos > $tmp_pos; --$j)

					{

						$utf_char = $buffer[$j & 7];

						$lpos -= strlen($utf_char);

						if (isset($decomp_map[$utf_char]))

						{

							// The char is a composite, decompose for storage

							$decomp_seq = array();

							$_pos = 0;

							$_len = strlen($decomp_map[$utf_char]);

							do

							{

								$c = $decomp_map[$utf_char][$_pos];

								$_utf_len =& $utf_len_mask[$c & "\xF0"];

								if (isset($_utf_len))

								{

									$decomp_seq[] = substr($decomp_map[$utf_char], $_pos, $_utf_len);

									$_pos += $_utf_len;

								}

								else

								{

									$decomp_seq[] = $c;

									++$_pos;

								}

							}

							while ($_pos < $_len);

							// Prepend the UTF sequence with our decomposed sequence

							if (isset($decomp_seq[1]))

							{

								// The char expanded into several chars

								$decomp_cnt = sizeof($decomp_seq);

								foreach ($decomp_seq as $decomp_i => $decomp_char)

								{

									$utf_seq[$k + $decomp_i - $decomp_cnt] = $decomp_char;

								}

								$k -= $decomp_cnt;

							}

							else

							{

								// Decomposed to a single char, easier to prepend

								$utf_seq[--$k] = $decomp_seq[0];

							}

						}

						else

						{

							$utf_seq[--$k] = $utf_char;

						}

						if (!isset($utf_combining_class[$utf_seq[$k]]))

						{

							// We have found our starter

							$starter_found = 1;

							break;

						}

					}

					if (!$starter_found && $lpos > $tmp_pos)

					{

						// The starter was not found in the buffer, let's rewind some more

						do

						{

							// $utf_len_mask contains the masks of both leading bytes and trailing bytes. If $utf_en > 0 then it's a leading byte, otherwise it's a trailing byte.

							$c = $str[--$lpos];

							$c_mask = $c & "\xF0";

							if (isset($utf_len_mask[$c_mask]))

							{

								// UTF byte

								if ($utf_len = $utf_len_mask[$c_mask])

								{

									// UTF *leading* byte

									$utf_char = substr($str, $lpos, $utf_len);

									if (isset($decomp_map[$utf_char]))

									{

										// Decompose the character

										$decomp_seq = array();

										$_pos = 0;

										$_len = strlen($decomp_map[$utf_char]);

										do

										{

											$c = $decomp_map[$utf_char][$_pos];

											$_utf_len =& $utf_len_mask[$c & "\xF0"];

											if (isset($_utf_len))

											{

												$decomp_seq[] = substr($decomp_map[$utf_char], $_pos, $_utf_len);

												$_pos += $_utf_len;

											}

											else

											{

												$decomp_seq[] = $c;

												++$_pos;

											}

										}

										while ($_pos < $_len);

										// Prepend the UTF sequence with our decomposed sequence

										if (isset($decomp_seq[1]))

										{

											// The char expanded into several chars

											$decomp_cnt = sizeof($decomp_seq);

											foreach ($decomp_seq as $decomp_i => $utf_char)

											{

												$utf_seq[$k + $decomp_i - $decomp_cnt] = $utf_char;

											}

											$k -= $decomp_cnt;

										}

										else

										{

											// Decomposed to a single char, easier to prepend

											$utf_seq[--$k] = $decomp_seq[0];

										}

									}

									else

									{

										$utf_seq[--$k] = $utf_char;

									}

								}

							}

							else

							{

								// ASCII char

								$utf_seq[--$k] = $c;

							}

						}

						while ($lpos > $tmp_pos);

					}

				}

				// STEP 3: Capture following combining modifiers

				while ($pos < $len)

				{

					$c_mask = $str[$pos] & "\xF0";

					if (isset($utf_len_mask[$c_mask]))

					{

						if ($utf_len = $utf_len_mask[$c_mask])

						{

							$utf_char = substr($str, $pos, $utf_len);

						}

						else

						{

							// A trailing byte came out of nowhere

							// Trailing bytes are replaced with Unicode replacement chars, we will just ignore it for now, break out of the loop

							// as if it was a starter (replacement chars ARE starters) and let the next loop replace it

							break;

						}

						if (isset($utf_combining_class[$utf_char]) || isset($qc[$utf_char]))

						{

							// Combining character, add it to the sequence and move the cursor

							if (isset($decomp_map[$utf_char]))

							{

								// Decompose the character

								$_pos = 0;

								$_len = strlen($decomp_map[$utf_char]);

								do

								{