Unicode

Posted in Stand-up philosophy on September 19th, 2012 by Mihnea

De ce pula mea ai vrea sa poti scrie nume de fisiere in telugu? Ok, stramosii tai n-au fost in stare sa realizeze ca 20 si ceva de semne sint suficiente pentru a reprezenta pe foaie sunetele care le ies pe gura, dar s-au prins altii intre timp. Cum cacat sa insisti sa scrii cu viermisori si iatagane dupa ce ai vazut alfabetul latin? Si, mai rau, cum sa-ti vina ideea sa aduci haosul asta in software, in loc sa le faci un bine inapoiatilor si sa le spui ca daca vor tehnica de virf pentru vazut porn, trebuie sa se invete si cu tehnica de virf pentru scris si citit? الجهاد!

Faptul ca lumea civilizata i-a bagat in seama p-astia a fost prima greseala. A doua greseala a fost formarea unui Comitet responsabil cu recensamintul alfabetului si incartiruirea mazgaliturilor intr-un Standard International. Acest Comitet ar fi putut sa adune literele latine, chirilice, kana si eventual grecesti (cu perversiunile lor gen ăâöé etc.), sa le puna intr-o tabela si sa termine treaba (ignorind ostentativ ideogramele si jihadistii), dar nu asa functioneaza comitetele. Cind ti se confera puterea de a Gindi O Solutie, trebuie sa faci ceva complicat, ca sa le arati celorlalti ca esti destept. Orice prost poate sa puna citeva sute de caractere intr-o tabela, dar tu esti un erudit patrunzator si vezi imaginea de ansamblu, asa ca tabela ta va contine hieroglifele egiptene, caracterele ugaritice, cartile de joc, emoticoane, piesele de domino si mahjong etc. Si privind tu asa la cele un milion de semne adunate, simti ca tot nu-i destul si tot se vor gasi diversi sa conteste valoarea ta, valoarea ta, asa ca adaugi si scrijeliturile de pe discul din Phaistos (caracterele 0x101D0 – 0x101FF), care nu a fost descifrat inca. CINE-I CEL MAI ERUDIT ACUM?

Si nu te opresti aici. Nefiind prost si tinind cu tarie sa arati lumii asta, te apuci sa incurajezi creativitatea in exprimare prin intermediul semnelor diacritice. Desi ai bagat in tabela toate formele de A cu cerculet, accente, sedila, puncte si combinatii, faci caractere separate pentru toate aceste semne, ca sa poata omul sa scrie A cu trema fie ca Ä, fie ca A urmat de ¨.

Astfel s-a nascut Unicode, un standard menit sa ingreuneze pe cit posibil reprezentarea digitala a textului. Unicode se asigura ca orice operatiune de bun simt pe care ai vrea s-o faci pe un string devine imposibila. De exemplu, daca ai avut ghinionul sa inveti ca un string e o insiruire de caractere, imperialistul dornic de globalizare din tine va avea pretentia ca al 5-lea caracter dintr-un string sa fie la pozitia 5. In termeni stiintifici, vei dori ca accesul la caractere sa fie in timp O(1). Ei bine, Unicode se pisa pe pretentia ta din multiple directii.

In primul rind, cea mai folosita encodare pentru Unicode este UTF-8, care e un cod cu lungime variabila. Asta s-a intimplat din cauza ca, desi sint vreo 1.1 milioane de caractere in Unicode, oamenii normali folosesc cam 100 din ele, deci s-a simtit nevoia unei reprezentari compacte. Astfel, un caracter poate avea intre 1 si 4 bytes, deci textu’ e mic, dar ca sa ajungi la un caracter trebuie ori sa treci prin toate caracterele de dinainte, adica O(N), ori sa tii si sa actualizezi o tabela de index impreuna cu string-ul, care ar fi mai mare decit spatiul cistigat prin encodarea cu lungime variabila.

Minerii se vor grabi sa observe ca Microsoft au rezolvat demult problema asta prin intermediul string-urilor wide, unde un caracter e tinut pe 16 biti. Minerii sint prosti si nu realizeaza faptul ca 1.1 milioane de caractere nu incap in 16 biti. String-urile wide din Windows folosesc de fapt UTF-16, care este tot un cod cu lungime variabila si are aceleasi probleme ca UTF-8, plus ca ocupa de doua ori mai mult spatiu pentru textul de oameni normali, trebuie convertit la UTF-8 pentru a discuta cu restul lumii si e endian-dependent, asa ca inainte sa te exprimi pe limba lui trebuie sa semnalezi ce endianness preferi cu un cacat numit byte order mark.

Sigur, 1.1 milioane de caractere pot fi reprezentate pe 32 de biti. Se pare ca problemele noastre se rezolva daca folosim UTF-32 si acceptam ca 75% din text sa fie 0, ca memoria si discurile sint ieftine in zilele noastre. Ei bine, gratie diacriticelor separate (sau “combining marks” cum se numesc ele oficial) se rezolva o pula. Daca pentru codul tau “un caracter” inseamna “o litera” si nu “o litera sau un semn de cacat care face parte din litera anterioara”, tot trebuie sa parcurgi string-ul ca sa ajungi la o anumita pozitie si ca bonus trebuie sa si stii care sint semnele alea ca sa tii cont de ele cind numeri. Evident, celelalte reprezentari au si ele problema asta.

Sa facem un efort de imaginatie: un miner-arhitect este insarcinat sa toarne fundatia unui cod ce va folosi UTF-8. Sesizind problema indexarii, dinsul infaptuieste o functie numita CharacterAt() care parcurge string-ul in cautarea pozitiei date, tinind cont de lungime variabila, diactritice separate si alte mui. In urma sa trudeste minerul-programator ce este insarcinat sa caute slash-urile dintr-un string. Miinile lui negre iti vor intinde o floare asemanatoare cu codul ce urmeaza:

for(size_t i = 0; i < Length(str); ++i)
{
    if(CharacterAt(str, i) == '/')
    {
        // ceva
    }
}

Am incercat aici sa cuprind cit mai bine mentalitatea de miner, folosind size_t pentru variabila i, ca asa a auzit ca-i bine, dar chemind Length() la fiecare iteratie, deoarece minerii nu inteleg ce face de fapt functia aia. Oricum, chiar daca minerul muta apelul catre Length() in afara buclei, cautarea asta e tot O(N^2). Cam ca atoi-ul Minerului Suprem, mai tineti minte?

Apropo, Length() ala trebuie sa aplice aceleasi principii de convietuire globala ca CharacterAt() ca sa afle cite caractere sint de fapt in sir, nu merge sa cauti primul 0.

Exista diversi mintosi care sustin ca accesul aleatoriu la caractere este necesar foarte rar. De obicei cauti ceva printr-un string, deci oricum iei la rind toate caracterele, asa ca ai nevoie doar de niste facilitati de iteratie care sa stie de regulile pulii. Chiar daca le dam dreptate, ramine comparatia, un alt detaliu prin care Unicode da muie programatorilor din lumea intreaga.

Un om sanatos s-ar astepta sa poata compara doua string-uri byte cu byte: cind gasesti valori diferite la aceeasi pozitie, string-urile difera. Asta ar fi prea simplu, asa ca din nou diacriticele separate salveaza situatia. Ca sa compari doua string-uri trebuie intii sa le normalizezi, o operatiune cit se poate de simpla si naturala cu o descriere concisa, de doar 27 de pagini. Pentru a stimula si mai tare creativitatea, exista de fapt 4 moduri de normalizare, numite intuitiv D, C, KD si KC. Pe linga disclaimer-ul ala despre OOP ce insoteste codul Java din descriere, supun amuzamentului dumneavoastra si metoda recomandata de utilizare a implementarii din WINAPI: deoarece nu poti sti cit de mare o sa fie string-ul normalizat, chemi functia aia intr-o bucla pina cind o nimereste.

Dupa ce reusesti sa normalizezi string-ul ala trebuie sa incepi cu intrebarile filosofice: este sau nu string-ul ’10’ echivalent cu ‘Ⅹ’, ‘Δ’ sau ‘١٠’? Apropo, Ⅹ ala nu e X, este 0x2169, “Roman Numeral Ten” si in UTF-8 se scrie pe 3 bytes: 0xE2 0x85 0xA9. Ce ne faceam daca nu aveam in Unicode numerele romane de la 1 la 12? UNDE MAI ERA ERUDITIA NOASTRA?!

Deci muie Unicode, muie alfabet!

Tags: , , , , , , , , , , ,

Asamblorul

Posted in Codare cu premeditare, Regula 0 on September 2nd, 2012 by Mihnea

Bogdan Ontanu este un subiect generos, dar n-am scris pina acum despre el deoarece si-a desfasurat activitatea in neoliticul Internetului romanesc, pe cind Ideile se impreunau cu Eterul prin intermediul conturilor moca de Xnet si doar la ceas de seara, ca atunci era mai ieftin impulsu’ la Romtelecom. Desi forma de protoprostie intrupata in Bogdan este bine studiata in mediul academic, n-am vrut sa va indrept atentia catre trecut, atita timp cit prezentul este intesat de atitia mineri, militieni, profeti si alte subspecii de intelectuali care se zbat pentru a ne atrage atentia. Iata insa ca Viorel, un codexpert cel putin atipic prin faptul ca se preocupa in principal cu raspunsurile la obiect, ignorind aproape total exemplul Cucuscian, a decis sa faca jonctiunea intre trecut si prezent. Cind un incepator pingarit de miinile negre ale minerului a intrebat de unde poate sa-si procure un asamblor pentru a-si pune capat zilelor, Viorel a raspuns:

Încearcă şi acest asamblor interesant:

Bogdan Valentin Ontanu, autorul acestui asamblor interesant si posesorul site-ului oby.ro, este un fel de Aristotel al mileniului 3: prozator, filosof, game designer, virusolog, parinte de sistem de operare dar, mai presus de toate, programator ASM. El si-a asigurat locul in cartile de istorie de la scolile ajutatoare cind, in 2001, a anuntat ca lucreaza la RTS-ul Hostile Encounter, ce va avea urmatoarele caracteristici:

  • cel mai tare RTS 2D
  • Jucabilitate mai buna sau la fel de buna ca Star [adica Starcraft, in caz ca v-ati prins dar nu vreti sa credeti – n.r.]
  • Cel mai tare AI ( cu invatzare, dropuri surprize)
  • Poveste originala, fulminanta (si culmea aproape reala)
  • scris in ASM

Inainte de a studia jucabilitatea, povestea fulminanta sau taria, sa ne intrebam de ce vrea Bogdan sa scrie tot jocul in ASM. Din fericire, FAQ-ul cu reminiscente codexpertice de pe site ne lamureste:

We know ASM well. ASM is also very easy to learn
Argumentul e cladit pe proverbul “drumul cunoscut e cel mai scurt”. Cu alte cuvinte, Bogdan nu e in stare sa invete altceva, asa ca foloseste ce stie, indiferent ce implica asta. Also, “we” adica el.

There will allways be ASM code in a GAME so: Why NOT write all in ASM?
Dupa ce a auzit la Teleenciclopedia ca 57% din corpul uman e apa, Bogdan si-a extras creierul si l-a inlocuit cu apa, devenind astfel al doilea cel mai cunoscut programator hidrocefal din Romania.

Speed is of the essence in GAMES. ASM is 100% up to 300% faster than today “optimized” compiler
Iata ca frica de compilatoare si masini de scris automate facea victime cu mult inainte ca Minerul sa-i dea glas pe codexpert. Sa vedem cum se traduce asta in practica:

Cerinte de sistem pentru Starcraft, scris in C++ de catre fraieri:

  • CPU: 90 MHz Pentium I
  • RAM: 16 MB

Cerinte de sistem pentru Hostile Encounter, scris in ASM de catre Bogdan Ontanu:

  • CPU: 400 MHz Pentium II
  • RAM: 64 MB

Nu rideti. Codul ASM al lui Bogdan chiar este de 3 ori mai rapid decit codul amatorilor ce utilizeaza C++, dar necesita de 4.5 ori mai multi megaherzi d-astia deoarece Hostile Encounter e de 3*4.5 = 13.5 ori mai bun decit Starcraft. Dovada in screenshot-urile alaturate:

Starcraft

13.5 * Starcraft

Sint sigur ca se vor gasi guri rele care vor spune ca screenshot-ul din dreapta arata de maxim 7-8 ori mai bine decit cel din stinga, nicidecum de 13.5 ori. Lor le voi atrage atentia ca ignora faptul ca desi este facut de amatori, Starcraft este, totusi, un joc lansat, pe cind Hostile Encounter este inca in dezvoltare, deci are suficient timp pentru a-si realiza potentialul. In plus, trebuie sa vezi jocul in actiune ca sa-ti dai seama ca performanta de 1350% nu e investita doar in grafica ci si in AI si in modul in care toate elementele se imbina fluid, rezultind intr-o experienta ce atinge dezideratul initial de “cel mai tare RTS 2D”. Din fericire exista un demo care poate convinge pe oricine.

Acum ca am stabilit faptul ca Bogdan este cu adevarat o minte luminata a programarii ASM si nu numai, este timpul sa ne aplecam asupra talentului sau de prozator, de unde izvoraste povestea jocului, “fulminanta si culmea aproape reala”. Fundalul actiunii din Hostile Encounter este un o imbinare magistrala a unor idei de baza din scientologie, crestinism, Lorin Fortuna si practic orice SF de cacat din ultimii 50 de ani, relatata cu maiestria unui elev care n-a trecut de clasa a 3-a desi a incercat de 8 ori. Opera este atit de complexa incit sfideaza orice tentativa de a face un rezumat ce ar putea incapea in acest articol, asa ca va invit sa cititi aici schita realizata de autor. Marturisesc ca eram cu sufletul la gura atunci cind Satana voia ca urmatoarea recolta sa aiba 7 “typo logical DNA code”, in timp ce Dumnezeu insista sa bage 12. Pentru cei care nu dau skip la dialoguri, avem aici inca 3 fragmente scrise in aceeasi limba frumos curgatoare a lui Shakespeares ce imping firul epic cu pulanul in coaste de la Iisus, gheizere sfinte si retele neuronale pina la Zamolxis si hackeri romani.

Printr-o inexplicabila si cruda omisiune a Divinitatii, talentul lui Bogdan cu pixul acopera doar sfera cuvintelor, nu si pe cea a formelor. Acest obstacol a fost insa usor depasit, caci s-a gasit imediat un suflet de artist care sa completeze sufletul de prozator-asamblor al subiectului nostru. Un suflet de artista, mai exact, caci slava pentru grafica de exceptie se cuvine Adinei, care, conform spuselor lui Bogdan, a si cistigat “premiul artistic” la concursul “SF Rom” cu o imagine din joc. Privind in galeria intitulata inexplicabil “Artwork” resimtim un sentiment de goliciune, caci din pacate concursul respectiv s-a pierdut in negura vremurilor si nu putem vedea celelalte lucrari care au participat si n-au cistigat. Imaginati-va doar cum erau alea, daca au fost declarate mai proaste ca asta (intutulata, intr-un act de suprema ironie involuntara, ugly_thing.jpg):

De ajuns insa cu Hostile Encounter. Desi e un capitol important din activitatea lui Bogdan, nu e singurul. Trebuie sa mentionam macar in treacat Solar OS, sistemul de operare scris de Bogdan in – ati ghicit – ASM. Dupa cum putem citi in parabola A Day with Solar OS, acesta este primul sistem de operare care pune o intrebare de ordin filosofic hackerilor:

Yes I know you can break me, but since it is so easy by design, there is also no glory in doing this… so why doing it? Creation and Construction my friend are much more honorable, valuable and harder to achieve than entering a simple house that has no locked doors or “windows”. Besides my core shell is read only, small, simple, fast and does not auto run nothing. How on this Earth are you going to convince me to compile and insert your code into my GUI Kernel?

Sublim. Un nou concept in sfera securitatii aplicatiilor: security by philosophy. OS-ul iti vorbeste de dincolo de “GUI Kernel” si face apel la umanitatea ta, ca o poezie de Elena Farago:

De ce m-ai prins în pumnul tau,
Hacker frumos, tu nu stii oare
Ca-s mic si eu si ca ma doare
De ce ma strangi asa de rau?

Fratii mei ceilalti se joaca
Cu hackerii toti, dar eu
Nu pot alerga ca dansii,
Ca sunt scris in ASM!

Bogdan Ontanu lucreaza in prezent la AVIRA, unde sper ca incearca sa patenteze aceasta manevra filosofica si s-o inglobeze in produsul antivirus al companiei.

Mai sint multe de zis despre acest Om Al Renasterii si din fericire avem unde: Bogdan are un forum dedicat ideilor si proiectelor sale. Recomand cu caldura parcurgerea sectiunii “Evolution of Human Race”, unde vizionarul programator ASM continua discutii de pe alte forumuri sub forma de monolog, atingind subiecte de interes maxim si dind solutii pentru iesirea omenirii din criza morala si materiala in care se afla. De exemplu, aici gasim o aspra critica la adresa CERN, care a construit degeaba LHC-ul. Daca l-ar fi consultat intii pe Bogdan, ar fi aflat in primul rind ca trebuia facut in ASM si in al doilea rind ca “whatever technological advancement we might achieve it does not matter until we do not solve our darkness inside“.

In caz ca n-ati inteles, va traduc eu: pentru Bogdan nu conteaza bosonu’ Higgs si compilatoarele, ca la el in minte e bezna.

Tags: , , , , , , , , , , , , , , , , , , ,