Reprezentacja bitowa znaków Unicode i UTF-8

Jakiś taki naukowy ten tytuł wyszedł. Ale inaczej się chyba nie da. Potrze­bo­wa­łem pretek­stu żeby się trochę poba­wić w mani­pu­lo­wa­nie bitami. Padło na Unicode z racji fajnego sposobu, w jaki wymy­ślono sam zapis znaków. Jeśli jest jesz­cze ktoś kto nie wie co to jest Unicode to zapra­szam do źródła.

Wszystko zostało tak prze­my­ślane, że im bardziej pokrę­cony język, tym więcej miej­sca potrzeba na jego zapi­sa­nie. Wszyst­kie liczby i litery bez ogon­ków damy radę zapi­sać w postaci 1 bajta. Chodziło o kompa­ty­bil­ność z forma­tem ASCII. Znaczki języka polskiego znaj­dują się w dziale Latin Extended-A. Zapis znaków polskich zajmie 2 bajty w forma­cie UTF-8.

Mając numer znaku z tabeli Unicode najła­twiej wyświe­tlić go za pomocą wbudo­wa­nej w PHP funk­cji html_entity_decode():

echo html_entity_decode('&#' . 0xA7 . ';', ENT_NOQUOTES, 'UTF-8');

Wywo­ła­nie powyż­szego wier­sza spowo­duje wyświe­tle­nie znaku o kodzie 0xA7 — para­grafu §. W jaki więc sposób wyko­nuje się czary-mary i znak Unicode staje się znakiem UTF-8? Weźmy na warsz­tat znak ę opisany w tablicy jako latin small letter e with ogonek. Ma numer 0119 (heksa­de­cy­mal­nie!), czyli można zapi­sać tak:
0x11916 = 28110 = 1000110012
Z powyż­szego widać, że liczbę dzie­siętną 281 możemy zapi­sać w postaci 9 bitów. Doku­men­ta­cja funk­cji utf8_encode() zawiera tabelkę ile bitów znaku zmie­ścimy w ilu bajtach UTF-8. Wygląda na to, że w jedno­baj­to­wym zapi­sie zmie­ścimy znaki o nume­rach od 0 do 12710 (7 bitów). Za to dyspo­nu­jąc 2 bajtami zapi­szemy liczby aż do 204710, czyli w zupeł­no­ści nam wystarczy.

Znak ę w UTF-8 zapi­su­jemy w 2 bajtach, czyli do liczby 110000002 musimy dodać prze­su­niętą o 6 bitów w prawo liczbę 281 (ponie­waż pójdą do drugiego bajtu znaku). Z drugiego wyrzu­camy wszystko poza 6 ostat­nimi bitami, a następ­nie doda­jemy do liczby 100000002.

$uniChar = 0x119;
$byte1 = $uniChar >> 6 | 0xC0;
$byte2 = $uniChar & 0x3F | 0x80

Wyszło na to, że ę w zapi­sie UTF-8 to będzie 11000100 10011001. Po ubra­niu tego wszyst­kiego w funkcję:

function hexToUTF8HexArray($hexNum)
{
   // konwertujemy na liczbe w razie czego
   if (is_string($hexNum)) $hexNum = hexdec($hexNum);
 
   $hexArray = array();
   if ($hexNum < 0x80) {
      $hexArray[0] = '0x' . dechex($hexNum);
      return $hexArray;
   } elseif ($hexNum < 0x800) {
      $hexArray[0] = '0x' . dechex($hexNum >> 6 | 0xC0);
      $hexArray[1] = '0x' . dechex($hexNum & 0x3F | 0x80);
      return $hexArray;
   } else {
      throw new Exception('Not supported');
   }
}

Wywo­łu­jąc hexToUTF8HexArray(0x119) da nam tablicę z warto­ściami 0xc4 i 0x99. No dobra, a co jak chcę odwró­cić proces? Teraz będzie przyjemniej:

function utf8ToUnicode(array $utf8Array)
{
   // konwertujemy na liczby
   $utf8ArrayChecked = array();
   foreach ($utf8Array as $utf8) {
      if (is_string($utf8)) $utf8 = hexdec($utf8);
      $utf8ArrayChecked[] = $utf8;
   }
 
   $bytesCount = count($utf8ArrayChecked);
   switch ($bytesCount) {
      case 1:
         return $utf8ArrayChecked[0];
      case 2:
         // wyrzucamy naglowki
         $b1 = $utf8ArrayChecked[0] & 0x1F;
         $b2 = $utf8ArrayChecked[1] & 0x3F;
 
         // tutaj cala magia
         $number = $b1 << 6 | $b2;
         return '0x' . dechex($number);
      default:
         throw new Exception('Not supported'); 
   }
}

Wywo­łu­jąc utf8ToUnicode(array(0xc4, 0x99)) otrzy­mamy 0x119, czyli gra jak trzeba.

Na koniec cieka­wostka: mając jakiś znak możemy łatwo wydo­być jego wartość UTF-8.

function charToUTF8HexArray($char)
{
   $i = 0;
   $hexArray = array();
   while (isset($char[$i])) {
      $hexArray[] = '0x' . dechex(ord($char[$i++]));
   }
   return $hexArray;
}

charToUTF8HexArray('ę') da nam tablicę 0xc4, 0x99.

Ten wpis to taka trochę notatka dla mnie, przez co może trochę chaotycz­nie napisany…

Algorytmy liczące Pi w Pythonie

Dzisiaj będzie o długich licz­bach. Wiedzie­li­ście, że Python w stałej Pi zawiera tylko 48 cyfr po prze­cinku? (a przy­naj­mniej wersja 2.6) 3.141592653589793 (odtąd błęd­nie) 115997963468544185161590576171875. To stanow­czo za mało! Tyle to ja liczy­łem na liczy­dle w przed­szkolu A ja chciał­bym wiedzieć jaka jest liczba pięcio­ty­sięczna po prze­cinku ;-) Zade­mon­struję 3 metody licze­nia liczby Pi.

Od razu mówię, nie pytaj­cie mnie o nic w związku z tymi meto­dami, bo zazwy­czaj rozu­miem tylko wstęp i pierw­szy wzór z opisu.

I. Metoda Wallisa
Posłu­żymy się takim fajnym tworem jak gene­ra­tor (yield w pętli zamiast return)

def wallisFormulaGenerator(counterMax):
   counter = 0
   while(counter <= counterMax):
      counter += 1
      yield (4*(counter**2))/(4*(counter**2)-1)       
 
def gimmePiBaby(loops):
   result = 1
   for value in wallisFormulaGenerator(loops):
      result *= value
      return 2*result
 
print(gimmePiBaby(10000))

Ta metoda jest najsłab­sza, po 18 obro­tach mamy dopiero 3.1, po 492 3.14, a dopiero po 8476 3.1415.

II. Metoda Leib­nitza
W moim przy­padku mocno oszu­kana ta metoda, ale działa popraw­nie. I dużo szybciej!

minus = True
partial = 1
denominator = 3
for i in range(100000):
   if minus:
      partial -= 1/denominator
      minus = False
   else:
      partial += 1/denominator
      minus = True
   denominator += 2
   result = 4 * partial

Jest lepiej, obli­cze­nia wyko­ny­wały się 3x szyb­ciej niż poprzednio.

III. Metoda Abra­hama Sharpa
Najwy­daj­niej­sza z wyżej przed­sta­wio­nych. Na pewno są wydaj­niej­sze, ale dla okre­śle­nia liczby nr 5000 wystar­czy. Aby wypi­sać tyle liczb ile nas inte­re­suje, zwykły obiekt typu float nie wystar­czy, potrze­bu­jemy biblio­teki BigFloat. Niestety nie daje się zain­sta­lo­wać z wersją 3 Pythona mimo użycia 2to3, więc pozo­staje wbudo­wane w Ubuntu 2.6.

import bigfloat
with bigfloat.precision(17000):
   minus = True
   partial = bigfloat.BigFloat(1)
   denominator = 3
   for i in range(1, 500000):
      if minus:
         partial -= (1/((bigfloat.pow(3,i))*denominator))
         minus = False
      else:
         partial += (1/((bigfloat.pow(3,i))*denominator))
         minus = True
      denominator += 2
   result = 6 * ((1/bigfloat.sqrt(3)) * partial)

Mój procek za 45zł 500 000 obro­tów wyko­nał w 2339 sek., a dzisiej­szy wpis spon­so­ruje cyferka 1 będąca warto­ścią pięcio­ty­sięczną po przecinku.

Mam nadzieję, że chociaż gimna­zja­li­stom algo­rytmy się przydadzą…

Śpiechu goes Android

No to teraz wiecie już, że Śpiechu dochra­pał się Andro­idka (2.3.3). Wpraw­dzie na najsłab­szym sprzę­cie jaki istnieje — HTC Wild­fire S, ale zawsze. Udało się wyli­cy­to­wać na Alle­drogo za 500 zł. Czło­wiek, od którego kupi­łem sprzęt wierzył, że zrobił dobry inte­res. Ja również. Kto zrobił lepszy? On w końcu zapła­cił tylko złotówkę, a dostał 499 w zamian ;-)

W związku z tym warto byłoby odpa­lić mały cykl andro­ido­wego how-to. Na począ­tek jak pozbyć się tego uciąż­li­wego powia­do­mie­nia dźwię­ko­wego o nowym mailu i nowej wiado­mo­ści na Google Talk. Jeśli otrzy­mu­je­cie kilka­dzie­siąt maili dzien­nie, jest to spory problem. Dioda wg mnie wystarczy.

Opcja jest na tyle scho­wana, że warto o niej tutaj napi­sać. Znaj­du­jąc się w apli­ka­cji Gmail naci­skamy przy­cisk menu -> więcej -> usta­wie­nia -> swoje konto -> etykiety do powia­do­mień -> odebrane -> dzwo­nek -> Cichy. W Talku jest jesz­cze prościej: menu -> usta­wie­nia -> wybierz dzwo­nek -> cichy.

Tyle na dzisiaj. W ciągu 2 dni nie stałem się jesz­cze smart­fo­no­wym guru, ale wszystko przede mną. I żeby nie było, 7 letnia Nokia 6230i ma się świet­nie. W dalszym ciągu bate­ria trzyma 5 dni, a w nowym HTC 1.