Kawałek Kodu

Jeśli rejestrowałeś domenę z ogonkami, to pewnie choć przez chwilę przeszło Ci na myśl dlaczego trzeba ją konwertować na ciąg dziwnych znaczków. Pewnie myślałeś też skąd się biorą te znaczki. Może polskie znaki kodowane są za pomocą dwóch innych znaków(?) Zapnij pasy poławiaczu domen! Wypływamy na szerokie wody alfabetu.

Robimy boot naszego kotwicznego łańcucha (znaków)!

Na potrzeby przechowywania i przesyłania domeny ze znakami międzynarodowymi utworzono algorytm Punycode. A dokładnie Bootstring, bowiem Punycode to jeden z przykładów jego użycia z odpowiednimi parametrami. Przekonwertowana domena ma postać ACE (ASCII encoded). Pomimo użycia liter charakterystycznych dla danego języka, postać wynikowa zawiera tylko podstawowe litery alfabetu oraz cyfry (a-z oraz 0-9). Występuje jeszcze znak -, który w tym przypadku jest używany do odzielenia znaków podstawowych od rozszerzonych (jeśli podstawowe występują), oraz jest częścią prefiksu ACE, czyli ciągu xn--, który występuje na początku takiej domeny.

Ten blog oprócz domeny kawalekkodu.pl używa również spolszczonej wersji, czyli kawałekkodu.pl. Ta druga w reprezentacji ACE ma postać:

xn--kawaekkodu-d0b.pl

Po środku oceanu.

Jak już pewnie dostrzegasz połowa tajemnicy wyjaśniła się. Wiemy skąd się bierze xn--, dlaczego potem widać naszą dziurawą domenę, co robi kolejny minus. Nie znamy jednak drugiej połowy tajemnicy, czyli jak zakodowane są polskie znaki. Tu do akcji wkracza wcześniej wspomniany Punycode. Do działania Punycode będą potrzebne następujące parametry:

• base = 36 (podstawa systemu trzydziestoszóstkowego - a-z oraz 0-9, to 36 znaków),
• tmin = 1 (parametr ograniczający z dołu),
• tmax = 26 (parametr ograniczający z góry),
• bias = 72 (parametr obcinający).

Przyda nam się też tablica kodowań Unicode ASCII dla polskich znaków:

Wartości obliczane w koderze, będziemy reprezentować jako znaki, według zasady:

• 0-25, to znaki a-z
• 26-35, to znaki 0-9

Serce kodera Punycode składa się z następujących elementów:

1. mechanizmu sortującego znaki narodowe (wybieramy kolejno znaki o najmniejszych kodach, aby obliczana delta była jak najmniejsza),
2. funkcji konwertującej różnice pomiędzy kolejnymi wartościami kodów znakowych na system 36,
   wraz z obcinaniem wartości i użyciem zmiennej bias,
3. funkcji dopasowującej wartość bias.

Dla pierwszego znaku narodowego musimy musimy obliczyć deltę (2) w następujący sposób:
delta = (kod znaku - 128) * (ilość znaków o mniejszym kodzie + 1)
128 w tym przypadku, to pula kodów znaków podstawowych w ASCII (kodowanie na 7 bitach - 2⁷=128).

Dla kolejnego znaku narodowego delta jest obliczana jako:
delta = delta + (kod znaku - (kod poprzedniego znaku + 1)) * (ilość znaków o mniejszym kodzie + 1)

Delta zawsze będzie mieć wartość dodatnią, bo znaki międzynarodowe wybieramy według ich rosnących wartości kodów (1). Czyli najpierw przetwarzamy znak o najmniejszym kodzie Unicode, potem o kolejnym większym, a na końcu o największym z puli. Następnie w pętli zwiększamy o deltę 1, jeśli aktualnie przetwarzany znak ma kod wiekszy od kolejnego, a jeśli kody będa równe (czyli to ten sam znak), to możemy przystąpić do jej konwersji. Po konwersji (nadal w pętli) zerujemy deltę i porównujemy kod z pozostałymi kodami (jeśli są) i ewentualnie zwiększamy deltę o 1.

Głębiny i gąbki.

Myślę, że najprostszym przykładem będzie domena ą.pl. Nie mamy w niej podstawowych znaków, więc zacznie się standardowym prefiksem, potem będzie zakodowana litera ą i końcówka domeny, czyli bez separatora. Kod ASCII litery ą, to 261. Delta będzie mieć wartość (261-128)*(0+1)=133. Nie będziemy jej już zwiększać, bo nie napotkamy w domenie innego znaku, w porównaniu z którym ą jest większe. Konwertujemy więc wartość 133.

Kroki konwersji są następujące:

Domena będzie mieć więc postać:
xn--2da.pl

Spóbujmy teraz z trudniejsza domeną: łódź.pl. Mamy aż trzy znaki polskie nie występujące obok siebie. Domena będzie mieć postać mniej więcej: xn--d-KOD.pl. Znaki będziemy kodować według kolejności rosnącej:
ó (243), ł (322), ź (378).

Dla ó delta=(243-128)*2=230. Mnożymy przez 2, bo mamy już jeden kod mniejszy od przetwarzanego (jest nim litera d).

W tym momencie do porównania zostały znaki d oraz ź. Kod ó jest większy tylko od d, więc zwiększamy deltę. Po konwersji znaku również zwiększamy deltę. Na koniec ma wartość 2.

Kolejnym znakiem do konwersji będzie znak ł.
delta=2+(322-(243+1))*3=236
W momencie konwersji ł znów porównujemy jej kod z każdym znakiem. Akurat teraz ł stoi na pierwszym miejscu więc nie zwiększamy delty, ale przystępujemy do konwersji. Przed tym jednak obliczamy nową wartość zmiennej bias (na końcu podaję źródło do jej pseudokodu). Teraz bias=0

Teraz zwiększamy deltę o 2 (kod ł jest większ od d oraz ó) i dodatkowo po pętli o 1, delta=3.

Teraz czas na ź. delta=3+(378-(322+1))*4=223
Znów w pętli konwerującej porównujemy ź z każdym znakiem, ponieważ ma największy kod, zwiększamy deltę kolejno i otrzymujemy delta=226.
Nowoobliczony bias ma wartość 28.

Przybiliśmy łodzią do brzegu.

Tak więc:

• ó to kod: uga
• ł to kod: 0v
• ź to kod: 4h

Cała domena ma postać: xn--d-uga0v4h.pl

Można zauważyć, że w przypadku obydwu domen (kawałekkodu.pl oraz łódź.pl), litera ł ma inne kodowanie. I nie ma w tym nic nadzwyczajnego, bo wszystko zależy na którym miejscu stoi dany znak, czy są znaki podstawowe i jakie są inne znaki narodowe (jeśli inne znaki mają mniejsze kody, to zostaną zakodowane wcześniej, a co za tym idzie parametry dla kodowania danego znaku będą inne).

I przykładowy kod w JavaScript:

/* parametry początkowe
   dla Punycode
*/
var base = 36;
var tMin = 1;
var tMax = 26;
var skew = 38;
var damp = 700;
var bias = 72;
var n = 128;

var output = [];
var input = 'łódź';

var delta = 0;

/* funkcja dopasowująca zmienną bias,
   jej pseudokod znajdziesz w dokumentacji RFC
*/
function adapt(delta, numPoints, isFirstTime) {
  if (isFirstTime) {
    delta /= damp;
  } else {
    delta >>= 1;
  }
  delta += delta / numPoints;
  for (var k = 0; delta > ((base - tMin) * tMax) >> 1; k += base) {
    delta /= base - tMin;

  }
  return parseInt(k + (base - tMin + 1) * delta / (delta + skew));
}

/* funkcja zmieniające kod ASCII
   na znak
*/
function digitToChar(d) {
  return String.fromCharCode(parseInt(d) + (d > 25 ? 22 : 97));
}

/* główna funkcja kodująca */
function encode() {
/* spisujemy wszystkie znaki podstawowe */
  for (var i = 0; i < input.length; i++) {
    if (input.charCodeAt(i) < 128) {
      output.push(input[i]);
    }
  }

/* ile znaków wstawiliśmy,
   a co za tym idzie,
   ile możliwych miejsc
   do wstawienia
*/
  h = b = output.length;

/* jeśli były jakieś znaki podstawowe,
   to dodajemy separator za nimi
*/
  if (b > 0) {
    output.push('-');
  }

/* kodujemy pozostałe znaki */
  while (h < input.length) {

/* szukamy najmniejszego kodu
   spośród znaków niepodstawowych,
   których jeszcze nie kodowaliśmy
*/
    var m = 65535;
    for (var i = 0; i < input.length; i++) {
      if (input.charCodeAt(i) < m && input.charCodeAt(i) >= n) {
        m = input.charCodeAt(i);
      }
    }

/* obliczamy deltę */
    delta += (m - n) * (h + 1);

    if (delta < 0) {
      throw ('Nieprawidłowa delta');
    }
/* zapamiętujemy kod znaku
   dla następnej iteracji
*/
    n = m;

/* porównujemy kod z każdym znakiem
   ciągu wejściowego
*/
    for (var i = 0; i < input.length; i++) {
      if (n > input.charCodeAt(i)) {
        if (++delta > 65535) throw ('Delta poza zakresem Unicode');
      }
/* to ten znak, kodujemy go */
      if (n === input.charCodeAt(i)) {
        var q = delta;
        for (var k = base;; k += base) {
/* obliczamy t i ewentualnie
   docinamy do tMin i tMax
*/
          var t = parseInt(k - bias);
          if (t < tMin) {
            t = tMin;
          } else if (t > tMax) {
            t = tMax;
          }
/* jeśli nam coś zostało,
   ale wiemy, że to już
   najmniej znacząca cyfra,
   to kończymy
*/
          if (q < t) {
            break;
          }
/* jeśli nie, to obliczamy wartość
   i zapisujemy znak
*/
          output.push(digitToChar(t + (q - t) % (base - t)));
          q = Math.floor((q - t) / (base - t));
        }
/* zapisujemy również znak
   odpowiadający najmniej znaczącej
   cyfrze
*/
        output.push(digitToChar(q));
/* dopasowujemy bias */
        bias = adapt(delta, h + 1, h === b);
/* wstawiliśmy znak, więc zerujemy deltę
   oraz zwiększamy licznik możliwych
   miejsc do wstawienia
*/
        delta = 0;
        h++;
      }
    }
    delta++;
    n++;
  }

  console.log('xn--' + output.join(''));
}

encode();

Mam nadzieję, że trochę rozwiałem tajemnicę dziwnych znaczków i podobnie jak mnie, Ciebie już tak nie gryzie ten temat. Ahoj!

Przydatne linki:
Dokumentacja opisująca algorytm Bootstring (tam znajdziesz też pseudokod funkcji adaptującej bias)
Konwerter Unicode<->ACE
idn_to_ascii - funkcja konwertująca w PHP