Не так давно передо мною встала задача использовать русские символы в имеющемся у меня скрипте конструктора сайтов, авторы которого почему-то не позаботились о том, чтобы сделать данную возможность. После бессмысленных поисков алгоритма работа Punycode, я начал интересоваться на форумах, и задал данный вопрос на нескольких десятках форумах соответствующей тематики. Но лучшее, что я получил в результате своих исканий, это несколько ссылок на уже готовые классы и методы и англоязычную документацию rfc, а также некоторые небольшие пояснения, которые помогли мне разобраться, но не раскрыли самого алгоритма работы.
Поэтому взяв за основу один из классов я стал его разбирать, и узнал, что основной алгоритм кодирования (до декодирования еще дело не дошло), кроется в php классе в методе _encode. Именно на его примере мы и будем разбирать работу всего алгоритма кодирования.
До цикла
while ($codecount < $deco_len) {
все более менее понятно и довольно просто.
Все символы преобразовываются в свои десятичные представления Юникода, передаются посимвольно в массив $decoded, вначале ставим «xn--», затем ставим все символы ascii по порядку исключая все не ascii и в конце добавляем "-". И все это в том случае если наши символы имеют интернациональные символы. Я не рассматриваю все дополнительные проверки, т.к. подразумевается, что мы вне всяких сомнений рассматирваем строку, где хотя бы один из символов не входит в ascii, соответственно все, что у нас есть для кодирования строки описано выше.
Я пытаюсь закодировать строку f-мрив-ff-ветмf согласно вышеуказанной логике получаю
xn--f--ff-f. Дальше идет цикл
while ($codecount < $deco_len) {
и две его переменные
codecount — которая равна 7 и соответственно количеству символов ascii из строки f--ff-f
и deco_len — которая равна 15, т.е. количеству символов заданной строки т.е. f-мрив-ff-ветмf.
Цикл должен споткнуться как только выполнится условие
} elseif ($decoded[$i] == $cur_code) {
столько раз, сколько у него не ascii символов, в нашем случае 8 раз.
Также есть массив
$decoded — содержащий последовательно все символы в десятичном представлении юникода
и есть переменная
$cur_code — которая равна 127, т.е. количеству ascii символов
Оснавная задача цикла while это увеличение $delta++ и $cur_code++;
В данном цикле у нас идет цикл
for ($i = 0; $i < $deco_len; $i++) {В котором заключаются два условия
Первое условие
if ($decoded[$i] < $cur_code) {Единственная задача которого увеличивать delta++ если десятичное представление символов из основной строки ($decoded[$i]) меньше $cur_code (которое изначально равно 127, т.е. количеству символов ascii), и которое увеличивается после каждого завершения цикла
for ($i = 0; $i < $deco_len; $i++) {те. в нашем случае каждые 15 раз до тех пор пока не выполнится
второе условие
} elseif ($decoded[$i] == $cur_code) {
те. пока $cur_code, которая увеличивается на 1 через каждые 15 дельта, не станет равна не-ascii коду символа. Так мы сверяем 15 строк нашего домена f-мрив-ff-ветмf, и ищем в нем наименьшее число после 127. И, соответственно, т.к. наименьший символ — это 1074 т.е. буква «м», то это первый символ и первое значение из нашего перебора на котором мы споткнемся, прибавляя по одному к 127 через каждые 15 раз.
И вот мы спотыкаемся первый раз на букве «м» = 1074, имея $delta = 7570. Что впринципе равно тому, сколько раз мы находили (ascii символы + 1) учитывая, что мы отсчитывали с нуля т.е. 7571 раз. Теперь обратим внимание, на всякий случай, сколько раз мы увеличивали дельту, а это (7 символов) + 1 раз (когда прибавляли дельту по завершению цикла while), т.е. мы увеличивали дельту на 8 с каждым while циклом.
946 * 8 = 7568 ( 7571-7568 = 3 (остаток))
Т.е. 946 раз мы прибавляли по одному к 127, и на 947 разе споткнулись на третьем символе с номером 1074.
Теперь обратим внимания на константы, которые у нас были в самом начале
$this->_base = 36. В качестве базисных символов выступают символы латинского алфавита от a до z (без различия между прописными и строчными буквами), цифры от 0 до 9.
$_tmin = 1 и $_tmax = 26 — это латинский алфавит от 1 до 26 символов
Далее я так и не понял, что это за initial_bias и буду КРАЙНЕ ПРИЗНАТЕЛЕН, если кто-нибудь ОБЪЯСНИТ, но bias = $this->_initial_bias = 72, а еще согласно rfc initial_bias mod base <= base — tmin. Последняя строка возможно подскажет, что-нибудь более опытным людям, а они в свою очередь подскажут мне, за что я им буду очень признателен, но к сожалению пока я знаю только что есть initial_bias равная 72.
Далее идет цикл, по завершению которого функция $this->_encode_digit волшебным образом вернет нам «kgg».
Условия цикла таковы
for ($q = $delta, $k = $this->_base; 1; $k += $this->_base) {те. $q = 7570, $k = 36, 1 это я так понимаю, до тех пор, пока наше условие верно, те. 1 это true, а может просто для красоты написано (я с такой записью раньше не сталкивался), т.к. цикл все равно останавливает break. Отмечу, что $k всегда статично вначале цикла и равно 36, т.к. у нас всего 36 символов доступных для использования в адресной строке. Она больше определяет количество циклов, те. например сколько символов будет использовано после того, как мы найдем первую букву «м». Поэтому при каждом прохождении цикла оно увеличивается на 36, пока не превысит значения $bias
Далее мы определяем переменную $t которая равна ($k <= $bias)? , т.е. если 36 <= 72, (при этом вдальнейшем 36 будет удваиваться, но пока оно не станет больше 72 ) $t будет равно 1. Чему равна $bias мы обсудим позже. Когда наконец $k станет больше загадочной 72 выполняется следующее условие (($k >= $bias + $this->_tmax)? $this->_tmax: $k — $bias)
И получается если у нас $k которая равна 36 и постоянно удваивается больше или равна загадочной $bias + 26, то $t = 26. При этом цикл остановится как только if ($q < $t) break;
Чему здесь равна $t вроде разобрались. Осталась в данном случае понять чему равна $q. A $q = (int) (($q — $t) / ($this->_base — $t));. Что в нашем случае, т.к. мы нашли первый символ «м» — с номером 1074, получается (7570 — 1)/(36-1) и далее 7569/35 = 216 целых
Далее по порядку
Первый цикл
$t небыло, это самый первый и единственный случай когда переменной не было,
Если ($k=36 <= $bias=72) $t станет 1, т.к. $k <= $bias
а $q было 7570
но в результате $q = (int) ((7570 — 1) / (36 — 1)) = 216
Второй цикл
$t было 1,
Если ($k=36 <= $bias=8) $t станет 1, $k <= $bias
а $q было 216
но в результате $q = (int) ((216 — 1) / (36 — 1)) = 6
Третий цикл
$t было 1,
Если ($k=108 <= $bias=72) $t станет 26, Т.к. $k > $bias,
а $q было 6
но в результате того, что $q(6) < $t(26) break;
Из данного цикла видно, что в результате у нас на выходе будет 3 буквы.
Но рассмотрим сразу следующий цикл, чтобы понять какие из значений еще имеют важность. Это будет все та же буква «м» с номером 1074, т.к. он наименьший, но уже в 14 позиции
Здесь можно обратить внимание, что конечный автомат съедает наименьшее число слева направо. Посмотрим на простом примере те. 1234134 => 234134 => 23434 => 3434 => 434 => 44 и тд.
Как же выглядит у нас буква «м» в 14 позиции и что изменилось
$t было 26, Если ($k=36 <= $bias=8)
$t станет 26,
а $q было 4, т.к. изначально оно равно $delta, но в результате того, что $q(4) < $t(26) break;
Во-первых, учитывая, что прошлый цикл у нас завершился, то delta мы сбросили и она оказалась равно 0, вначале нового цикла while. По дороге нам встретилось еще 4 символа которое меньше ascii + 1 (946 раз), что равно нашему символу с номером 1074. И как итог $delta = 4;
Во-вторых, значение $t оказалось уже не пустым изначально, а равное $t которое мы запомнили, т.е. 26
В-третьих, $k у нас не изменилась, т.к. она всегда равна 36, и увеличивается на 36 с каждым циклом
for ($q = $delta, $k = $this->_base; 1; $k += $this->_base) {В-четвертых осталась лишь $bias, которая в прошлый раз была равна 72, и не меняется внутри вышеуказанного цикла. После которого идет еще один алгоримт, вызываемым условием, как и сам цикл
} elseif ($decoded[$i] == $cur_code) { $bias = $this->_adapt($delta, $codecount+1, $is_first);Вот само тело функции
protected function _adapt($delta, $npoints, $is_first)
{
$delta = intval($is_first ? ($delta / $this->_damp) : ($delta / 2));
$delta += intval($delta / $npoints);
for ($k = 0; $delta > (($this->_base - $this->_tmin) * $this->_tmax) / 2; $k += $this->_base) {
$delta = intval($delta / ($this->_base - $this->_tmin));
}
return intval($k + ($this->_base - $this->_tmin + 1) * $delta / ($delta + $this->_skew));
}Сначала будем рассматривать первое совпадение, когда нам встретилась первая «м», в десятичном формате 1074, которой мы передаем 3 параметра
$delta = количество встретившимся нам ascii + 1 (946 раз)
$npoints = $codecount+1
$is_first = равно true, только перед основным циклом while и принимает значение false после окончания первого цикла
for ($i = 0; $i < $deco_len; $i++) {с выполнение условия
} elseif ($decoded[$i] == $cur_code) { Соответственно условие $delta = intval($is_first? ($delta / $this->_damp): ($delta / 2)); работает только первый раз когда $delta = целому числу (той же дельта деленная на damp) или в нашем случае 7570/700 = 10;
damp — Это тоже какое-то загадочное число, по крайней мере для меня, т.ч. если кто-то раскроет эту тайну буду крайне признателен.
Видимо данное условие выполняется только один раз, т.к. за пределы 700 скорее всего уже перейти невозможно, т.е. после того, как дельта найдет первое совпадение. Учитывая то, что буква от «а» в Юникоде = 1072, до «я» = 1103 — это 31 символ. Правда есть еще «ё» = 1105 и «й» = 1117 и еще не известно, как это будет выглядеть, если добавить еще и другие языки.
Но нас интересуют только кириллические буквы.
Вообще я предполагаю, что число 72 и тем более 700 это лишь ограничители, и не имеют большого логического смысла. Т.е. это могло быть и 699, и 966 и любое другое.
72 = 36*2, т.е. своего рода количество строчных и прописных символов и цифры доступные в названия доменов в ascii. Хотя почему 72, а не 36 или не 108 для меня загадка, как и 72, тоже.
После того, как мы получили первую дельта, мы прибавляем к ней целое число — саму себя поделенную на $codecount+1. Напомню что $codecount мы увеличиваем на один после каждого нахождения символа вконце выполнения алгоритма.
Я немного поменял местами эти значения
$codecount++;
$bias = $this->_adapt($delta, $codecount, $is_first);
и убрал +1, т.к. в этом случае сложение происходит уже до выполенния функции. На мой взгляд так будет несколько понятнее. Как результат дельта будет равна 10 + (10/8) = 10 + 1 (берем только целое число) = 11
Далее следует цикл который я удалил, тк. посчитал, его проверочным,
// for ($k = 0; $delta > (($this->_base - $this->_tmin) * $this->_tmax) / 2; $k += $this->_base) {
// $delta = intval($delta / ($this->_base - $this->_tmin));
// }
Поправьте меня если я ошибаюсь, но на результаты выдачи он ни разу не повлияли.
Напомню, что _base = 36 по количеству символов латинского алфавита и цифр, a _tmin = 1. И еще одно загадочное число _skew = 38.
Последнее, что мы делаем, это возвращаем результат следующего вычисления. intval($k + ($this->_base — $this->_tmin + 1) * $delta / ($delta + $this->_skew)). Как результат уравнение наше выглядет следующим образом intval($k + ($this->_base — $this->_tmin + 1) * $delta / ($delta + $this->_skew)). При этом, учитывая что предыдущий цикл мы удалили, то и $k в общем-то не существует, (может быть я ошибаюсь, и какие-то части кода здесь действительно нужны, но моей задачей было сократить алгоритм до минимума, и сделать его более ясным, поэтому если что-то не так, то прошу меня простить и поправить).
Запишем без нее intval(($this->_base — $this->_tmin + 1) * $delta / ($delta + $this->_skew))
Теперь в числовом варианте (36 — 1 + 1) * 11 / (11 + 38)
-1 + 1 сразу мне кажется лишним, поэтому сокращаю код еще и получаю intval($this->_base * $delta / ($delta + $this->_skew)), т.е. 36 * 11/(11+38) = 8. Это то чему равна $bias
Следующий вызов функции, когда мы находим вторую «м», как и все последующие будут отличается одним условием $is_first = false, а раз так, то согласно условию дельта будет равна половине себя. Поэтому чтобы не использовать функцию, избавиться от лишних переменных, с разными названиями, (навроде $npoints и $codecount) и сделать алгоритм еще более разборчивым, я сделал так, т.к на мой взгляд условия if делают его более наглядным.
if($is_first)
{
$delta = intval($delta / 700);
$delta += intval($delta / $codecount);
$bias = intval(36 * $delta / ($delta + 38));
}
else {
$delta = intval($delta / 2);
$delta += intval($delta / $codecount);
$bias = intval(36 * $delta / ($delta + 38));
}
Здесь вроде бы все понятно, и теперь остается только разобраться с самой главной функцией, которая и формурует нашу строку в кодовое представление. Она находится в переменной $encoded и формируется с помощью функции _encode_digit.
Вот ее код
protected function _encode_digit($d)
{
return chr($d + 22 + 75 * ($d < 26));
}Начнем с того, что сама функция вызывается столько раз, сколько раз у нас будет просходить вход в цикл for ($q = $delta, $k = $this->_base; 1; $k += $this->_base) { сразу после присвоения значения переменой $t. Чтобы было более наглядно я удалил
$encoded .= $this->_encode_digit(intval($t + (($q - $t) % (36 - $t))));после цикла а перед if ($q < $t) break; поставил
if($q < $t) $encoded .= $this->_encode_digit($q);
else $encoded .= $this->_encode_digit(intval($t + (($q - $t) % (36 - $t))));
Влияют на нее 3 параметра
Первый это $this->_base — я сразу заменил это значение на 36.
Второй параметр — это $t, которая зависит от $q и $bias.
Третий — это $q которая меняется только в том случае, если условие $q < $t неверное, и конструкция break не выполнится и равна целому числу полученному из уравнения ($q — $t) / (36 — $t)
Теперь избавимся от функции и перенесем уравнение $q = (int) (($q — $t) / ($this->_base — $t)); в вышеупомянутое условие туда, где оно и должно выполняться, а также перенесем конструкцию break. Теперь для наглядности переведем переменную $t на условия if else для наглядности и заменив все статические данные на цифры.
Получилось
while ($codecount < $deco_len)
{
for ($i = 0; $i < $deco_len; $i++)
{
if ($decoded[$i] < $cur_code)
{
$delta++;
}
elseif ($decoded[$i] == $cur_code)
{
for ($q = $delta, $k = 36; 1; $k += 36)
{
if($k <= $bias)
{
$t = 1;
}
elseif($k >= $bias + 26)
{
$t = 26;
}
else
{
$t = $k - $bias;
}
if($q < $t)
{
$encoded .= chr($q + 22 + 75 * ($q < 26));
break;
}
else
{
$encoded .= chr((intval($t + (($q - $t) % (36 - $t)))) + 22 + 75 * ((intval($t + (($q - $t) % (36 - $t)))) < 26));
$q = (int) (($q - $t) / (36 - $t));
}
}
$codecount++;
if($is_first)
{
$delta = intval($delta / 700);
$delta += intval($delta / $codecount);
$bias = intval(36 * $delta / ($delta + 38));
}
else
{
$delta = intval($delta / 2);
$delta += intval($delta / $codecount);
$bias = intval(36 * $delta / ($delta + 38));
}
$delta = 0;
$is_first = false;
}
}
$delta++;
$cur_code++;
}
return $encoded;
Неясными остались следующие параметры. Что они делают и зачем, я не выяснил. Конечно, они описаны в rfc, но по большей части мне они кажутся совершенно случайными. Надеюсь в комментариях узнаю ответ на этот вопрос.
Так например понятно, что_tmax — это количество букв латинского алфавита, а _base — это количество букв латинского алфавита и цифры, а initial_n — это количество ascii символов. А вот следующие параметры абсолютно непонятны.
skew = 38
damp = 700
initial_bias = 72
Очень хотелось бы узнать, что они значат и для чего служат?
Также в функции _encode_digit неясны, что это за 22, 75 и 26.
Если тема будет достаточно интересной и НЛО не удалит статью, то в следующей статье я постараюсь разложить декодер.
Автор: platedz
