Indeksowanie od tyłu

Pewna programistyczna mądrość ludowa uczy, że jedynymi liczbami bezpośrednio występującymi w kodzie powinny być tylko 0 lub 1. Brak lub nadmiar tej drugiej jest przy tym często pojawiającym się błędem, który zyskał swoją własną nazwę pomyłek o jedynkę (off-by-one errors).

Okazji do popełnienia tego rodzaju gaf jest sporo, a objawiają się one przede wszystkim wtedy, gdy mamy do czynienia z tablicami, łańcuchami znaków, kolekcjami, itd. – innymi słowy wszystkim, co da się indeksować. Jako rzecze C++ i większość innych “normalnych” języków, indeksy tablic rozpoczynają się od zera. Startowanie ich od jedynki ma aczkolwiek pewną zaletę: pętle przeglądające zawartość tablic mają wtedy prawie identyczne postaci niezależnie od kierunku przeglądania:

W przypadku indeksowania od zera pętla odliczająca wstecz jest wyraźnie różna:

Pisząc ją, trzeba więc zwrócić baczniejszą uwagę na to, co się robi.

Jednak nawet wtedy można potknąć się o pewien kruczek, gdy pod n podstawimy rzeczywiście używane wartości. Niech to będzie np. wielkość kolekcji STL czy długość łańcucha znaków std::string – a więc coś w stylu x.size(). Otóż takie wyrażenie zwraca liczbę typu równoważnego size_t, który z kolei jest równy ni mniej, ni więcej, jak tylko unsigned int. Jest to więc liczba bez znaku.
W zwykłej wersji pętli (liczonej do przodu) powoduje to ostrzeżenie kompilatora o niezgodności typów ze znakiem i bez znaku (signed/unsigned mismatch) w warunku i < x.size(), gdy i jest typu int. Jednym ze sposobów na pozbycie się tego warninga jest oczywiście zamiana typu licznika na size_t. Jeśli teraz mamy wystarczająco zły dzień, to przez analogię będziemy licznikiem tego typu indeksować również pętlę odwrotną:

I nieszczęście gotowe. Zauważmy bowiem, że odliczanie do tyłu tablicy/kolekcji indeksowanej od zera wymaga, by na koniec licznik przyjął na koniec wartość ujemną; inaczej warunek i >= 0 nigdy nie stanie się fałszywy. To się jednak nigdy nie stanie, gdy i jest liczbą bez znaku; zamiast tego nastąpi przekręcenie na maksymalną wartość dodatnią. Skutkiem będzie pętla nieskończona lub (częściej) access violation.

Co z tego wynika? Ano to, żeby… indeksowania generalnie unikać :) Po to bowiem zarówno STL, jak i każda inna biblioteka pojemników w każdym sensownym języku ma inne sposoby dostępu do elementów – choćby iteratory – aby z nich korzystać. I unikać takich “ciekawych” błędów jak powyższy :)

Triki z PowerShellem #13 – Prędkość czasu

Ostatni dzień roku to dobry moment na różne dziwne przemyślenia na temat czasu. Kiedyś z tej okazji wymyśliłem zupełnie nowy system kalendarza, a dzisiaj przypomniałem sobie o niezupełnie poważnym pomyśle autorstwa Rega, ze zbliżonej dziedziny.
Chodzi o oryginalną wielkość “fizyczną”: prędkość czasu. Ma ona ilościowo mierzyć znany wszystkim fakt, że wrażenie upływającego czasu jest różne w różnych sytuacjach. Gdy w rzeczywistości upłynął pewien czas , a nam wydawało się, że minął raczej czas , to odczuwana przez nas prędkość czasu wynosi

.

Dla przykładu: na nudnym wykładzie mogło minąć ledwie 15 minut, podczas gdy nam wydaje się, że siedzimy na nim już godzinę; wówczas . Z kolei grając przez trzy godziny możemy mieć wrażenie, że upłynęło tylko 30 minut – wtedy . Jak widać , zatem teoria zgadza się tutaj z intuicją, co pozwala wnioskować, że wielkość jest dobrze zdefiniowana :)

Pozostaje jeszcze kwestia jej pomiaru. W swoim oryginalnym artykule (który w tajemniczy sposób zniknął z sieci) Reg zaproponował, że można by go przeprowadzić za pomocą odpowiedniego programu. Miałby on działać w tle, losować pewien interwał czasu i po jego upływie pytać użytkownika, ile czasu według niego upłynęło od ostatniego pytania. Z dokładnością do małych błędów pomiarowych (np. czasu potrzebnego na wpisanie odpowiedzi) metoda wydaje się dobra – czemu więc by jej nie zaimplementować? :]
To właśnie uczyniłem, posługując się oczywiście swoim ulubionym narzędziem na takie okazje, czyli PowerShellem. Pewnym problemem było to, jak w skrypcie konsolowym postarać się o mierzenie czasu w sposób, który byłby niezauważalny dla użytkownika. Da się to jednak łatwo zrobić, posługując się… wbudowanym w system Harmonogramem zadań (Task Scheduler). Istnieje bowiem do niego dobrze udokumentowane, ładne i przejrzyste COM-owe API (dostępne od Visty wzwyż), którego użycie w PowerShellu wygląda zresztą kilka razy lepiej niż w C++ ;P
Wynikowy skrypt wygląda więc następująco:

Przy swoim pierwszym uruchomieniu tworzy on nowe zadanie w Harmonogramie, które polega na jego ponownym odpaleniu po upływie losowej liczby minut (5, 10, 15, itd. aż do maks. 60 minut). Wtedy użytkownik jest pytany o to, ile czasu według niego upłynęło, a następnie wyświetlają się częściowe wyniki pomiaru. Wówczas można zdecydować o jego kontynuowaniu lub zakończeniu. (Zawsze można też ręcznie usunąć zadanie z Harmonogramu, rzecz jasna).

I to w sumie tyle. Można już przystąpić do badań określających dokładnie, jak bardzo dłuży nam się czas do północy :))

Odczytywanie tekstu z gwiazdek

Aplikacje wymagające podania od użytkownika jakichś haseł zwykle ukrywają ich znaki, zastępując je “gwiazdkami”, czyli np. znakami asterisk (*) lub dużymi kropkami. Dzięki temu lekko zwiększa się poziom bezpieczeństwa programu, gdyż osoba niepowołana nie może tak po prostu odczytać hasła, patrząc na ekran.
Niezbyt imponujące określenie ‘lekko’ jest tu jednak bardzo na miejscu, bo istnieje całe mnóstwo narzędzi, które potrafią takie “zagwiazdkowane” hasła bez trudu odczytać. W jaki sposób to robią?

Otóż pola tekstowe dla haseł często są po prostu zwykłymi editboksami. Różnicą jest to, że mają przy tym ustawioną specjalną flagę: styl ES_PASSWORD; sprawia ona, że zawartość pola jest wyświetlana w sposób zamaskowany. Zakładając, że znamy jego uchwyt (HWND) – pozyskany na przykład z pozycji myszy i funkcji WindowFromPoint – możemy ów styl po prostu wyłączyć:

a następnie ustawić jeszcze znak zastępczy (“gwiazdkę”) na \0:

Wtedy kontrolka powinna zacząć normalnie wyświetlać swoją zawartość bez zamaskowania, więc użytkownik będzie w stanie ją odczytać. Jeśli natomiast chcielibyśmy programowo się do niej dostać, trzeba wysłać do kontrolki komunikat WM_GETTEXT. (Funkcja GetWindowText nie zadziała, jeśli editbox jest w innym procesie – a w tym przypadku właśnie tak jest).

Czy można swój własny program zabezpieczyć przed takim “hackiem”? Oczywiście można – wystarczy nadpisać domyślny sposób obsługi wspomnianego wyżej komunikatu WM_GETTEXT, by nie zwracał on rzeczywistego tekstu zapisanego w polu tekstowym. Da się to zrobić przy pomocy techniki subclassingu, czyli podmiany procedury zdarzeniowej okna (tutaj: pola tekstowego). Trzeba tylko pamiętać, żeby zapewnić przy okazji jakiś sposób, żeby ten tekst jednak jakoś pobierać – np. poprzez zupełnie nową wiadomość:

Najpewniejszą metodą jest aczkolwiek zupełne zrezygonowanie z przechowywania sensownej zawartości w samym editboksie i użycie do tego jakiegoś zewnętrznego bufora w postaci zmiennej. To jednak wymaga obsługi komunikatów związanych z całym procesem edycji, aby ten zewnętrzny bufor uaktualniać.

Istnieją oczywiście gotowe implementacje kontrolek, które działają właśnie w ten sposób. Czy warto ich używać? Sądzę, że niekoniecznie – z dwóch powodów.
Po pierwsze, pole tekstowe do wprowadzania hasła nie musi być wcale najwęższym gardłem bezpieczeństwa aplikacji. Niewiele przyjdzie z nawet najlepszego zabezpieczenia go, jeśli potem wpisane doń hasło jest np. przesyłane otwartym tekstem przez sieć lub zapisywane w pliku w postaci hasha MD5.
Po drugie, użytkownicy są generalnie przyzwyczajeni do jednokrotnego wpisywania haseł, które są następnie zapisywane między sesjami. Tak się dzieje chociażby na stronach WWW, gdzie w tym celu korzysta się z ciasteczek (cookies). Hasła więc bywają zapominane, lecz w sieci nie jest to wielkim problemem ze względu na powszechne mechanizmy przypominania. Tradycyjne aplikacje ich nie posiadają, więc istnienie jakieś metody pozwalającej użytkownikowi na odzyskanie z nich haseł (czyli użycie “odgwiazdkowujących” programów) nie jest wcale rzeczą złą.

A że przy okazji może to zrobić ktoś niepowołany? No cóż… Jeśli posiada on już dostęp do komputera ofiary oraz prawa administratora w jej systemie (bo to jest potrzebne, by wymienione wyżej triki działały), to jest wątpliwe, żeby poprzestał tylko na zabawie z gwiazdkami w editboksach ;-)

Unikalne łańcuchy znaków

Okazjonalnie zachodzi potrzeba, aby do jakiegoś celu wygenerować niepowtarzalny ciąg znaków. Jednym z zastosowań może być tutaj nadanie plikowi nazwy gwarantującej brak kolizji z jakąkolwiek inną nazwą pliku w systemie albo chociaż w aktualnym katalogu. W przypadku gdy ów plik ma istnieć tylko przez chwilę – a więc być plikiem tymczasowym (tempfile), sprawa jest prosta i sprowadza się do wywołania GetTempFileName jako funkcji WinAPI lub metody klasy System.IO.Path z .NET.

Stworzona w ten sposób nazwa jest z definicji “krótko żyjąca”. Na drugim biegunie w zakresie unikalności znajdują się tzw. UUID-y, czyli specjalnie ustandaryzowane 128-bitowe identyfikatory konstruowane tak, by zapewnić, że prawdopodobieństwo wygenerowania duplikatów jest mikroskopijnie małe. Każdy, kto grzebał trochę w Rejestrze Windows lub miał do czynienia z technologią COM, zna na pewno ich kuzynów, czyli GUID-y, opartych w gruncie rzeczy na podobnych zasadach.
Ponieważ tworzenie nowych GUID-ów/UUID-ów jest proste, można je wykorzystać w celu uzyskania niepowtarzalnych ciągów znaków. W czystym Windows API unikalny string oparty na UUID-zie można otrzymać np. tak:

Z kolei w .NET istnieje wyspecjalizowana klasa System.Guid, którą można wykorzystać w podobnym celu. W wyniku otrzymamy oczywiście teksty w stylu:

0DF44EAA-FF21-4412-828E-260A8728E7F1

co w wielu zastosowaniach może być strzelaniem z armaty do komara. Nie zawsze potrzebujemy przecież aż tak wielkiej unikalności, a UUID-y w formie tekstowej są długie i nieporęczne.

Są więc i inne rozwiązania, stosowalne jeśli nasz losowy ciąg musi być unikalny tylko przez stosunkowo niedługi czas, np. podczas jednego uruchomienia programu. W takim wypadku możemy użyć chociażby:

• wartości zwracanych przez GetTickCount/QueryPerformanceCounter lub asemblerową instrukcję rdtsc. Jest to czas (lub liczba cykli procesora) od momentu rozruchu systemu, więc z definicji wartość taka nie powtórzy się w trakcie działania aplikacji. Warto wiedzieć aczkolwiek, że używanie rdtsc jest generalnie niezalecane.
• aktualnego systemowego czasu – pobranego przez GetSystemTime z Windows API czy System.DateTime.Now z .NET – przekonwertowanego na string. Wadą jest tutaj wynikowa długość łańcucha i zbyt oczywisty format; prawdopodobnie więc należałoby jeszcze poddać go jakiemuś post-processingowi.
• zwykłego ciągu losowych znaków. W zależności od jakości generatora liczb losowych oraz losowości początkowego ziarna seed, możemy otrzymać nawet całkiem dobre wyniki. Metoda jest dobra zwłaszcza wtedy, gdy generowanych identyfikatorów jest na tyle mało, że możemy je efektywnie przechowywać i po prostu sprawdzać, czy nowy string jeszcze nie wystąpił (przykładem mogą być uchwyty w menedżerze zasobów w silniku gry).

Najważniejsze jest to, aby właściwie dobrać metodę do sytuacji, w której potrzebujemy unikalnego łańcucha znaków. Często wystarczy coś w stylu:

Nie myślmy nawet jednak, żeby tak stworzonego stringa używać do jakiejkolwiek formy komunikacji przez sieć. W takich przypadkach trzeba w zasadzie użyć UUID-ów.

Dlaczego nie lubię typów referencyjnych

Jeśli chodzi o C++, to nietrudno zauważyć, że często pozwalam sobie na sporo uwag krytycznych pod adresem tego języka. Oczywiście zawsze jest to krytyka konstruktywna :) Tym niemniej wiele jest tu rzeczy, o których można powiedzieć, że w innych językach zostały pomyślane lepiej (łącznie z takimi, których w C++ nie ma, a przydałyby się).
Dlatego dzisiaj będzie trochę nietypowo. Chcę bowiem wspomnieć o problemie, który w językach pokroju C# czy Javy potrafi doprowadzić do powstawania trudnych do wykrycia błędów – i który jednocześnie w C++ w zasadzie nie występuje wcale.

Mam tu na myśli semantykę referencji, czyli pewien szczególny sposób odwoływania się do szeroko rozumianych obiektów w kodzie. Klasy, a właściwie to prawie wszystkie typy poza podstawowymi (jak liczby czy znaki), są w C# i Javie obsługiwane w ten właśnie sposób; dlatego czasami nazywa się je typami referencyjnymi.
Najważniejszą cechą takich typów jest fakt, że należące do nich zmienne nie zawierają bezpośrednio instancji obiektów. Jeśli na przykład Foo jest klasą, to deklaracja:

nie sprawi, że pod nazwą x będzie siedział obiekt typu Foo. x będzie tutaj zaledwie odwołaniem do takiego obiektu – w tym przypadku zresztą odwołaniem pustym, niepokazującym na nic.
Jest to zachowanie diametralnie różne od typów podstawowych, jak choćby int. Ale idźmy dalej – skoro mamy zmienną mogącą trzymać odwołanie (czyli referencję) do obiektu, to pokażmy nią na jakiś obiekt, na przykład taki zupełnie nowy:

A że w prawdziwym programie zmiennych i obiektów jest zawsze mnóstwo, to wprowadźmy na scenę jeszcze parę:

No i zonk, można powiedzieć… Nikt aczkolwiek tego nie powie, bo dla każdego programisty C#, Javy itp. istnienie wielu referencji do tego samego obiektu jest rzeczą całkowicie naturalną. Jednak wiem, że podobny kod dla dowolnego typu liczbowego (zastąpiwszy ostatnią linijkę przez y += 4; lub coś tym w guście) zachowałby się zupełnie inaczej. Wiem też, że kiedyś byłem zmuszony wykonać kilka empirycznych testów, by się o tym naocznie przekonać; było to jeszcze w Delphi, a powodem były oczywiście jakieś “dziwne” błędy, na które natrafiłem w jednym ze swoich programów. Źle użyte typy referencyjne łatwo mogą być bowiem przyczyną takich błędów, które zresztą bywają potem trudne do wykrycia.

Bez jakiegoś rodzaju referencji nie da się rzecz jasna wyobrazić sobie użytecznego języka programowania. Sęk w tym, że w C# czy Javie używanie ich nie jest opcją do stosowania w tych przypadkach, które tego wymagają – jest koniecznością wymuszoną przez sam fakt programowania z użyciem klas i obiektów. To całkiem inaczej niż w C++, gdzie w tym celu trzeba wyraźnie zaznaczyć swoje intencje (najczęściej poprzez użycie typów wskaźnikowych).
W tworzeniu oprogramowania istnieje tzw. zasada najmniejszego zdziwienia (principle of least astonishment). Mówi ona, że przy alternatywie równoważnych przypadków powinno się wybrać ten, który u użytkownika końcowego będzie powodował mniejsze zdziwienie. Czy typy referencyjne zachowujące się zupełnie inaczej niż typy podstawowe i “same” zmieniające swoją zawartość nie są przypadkiem złamaniem tej reguły?…

Naprawianie IntelliSense

Wbudowany w Visual Studio system autouzupełniania kodu w przypadku C++ często działa całkiem dobrze, ale wiele osób pewnie stwierdziłoby, że częściej nie działa w ogóle. Każdy na pewno spotkał się z sytuacją, że po wpisaniu operatora kropki czy strzałki (->) jego oczom nie ukazywała się wcale lista składników klasy, a jedynie mało pomocny komunikat na pasku stanu. Sugeruje on zapoznanie się z określonym artykułem w MSDN, traktującym o rozwiązywaniu problemów z IntelliSense.

Przyznajmy teraz: czy ktoś rzeczony rzeczywiście artykuł przeczytał? :) Mam co do tego spore wątpliwości, lecz od razu zapewniam: nic straconego. Nie ma tam bowiem nic specjalnie użytecznego ;> Nie istnieje niestety żaden specjalny trik, który sprawiłby, aby mechanizm autouzupełniania w VS dla kodu C++ działał co najmniej w połowie tak dobrze jak chociażby dla C#. Jeśli więc chcemy, by był on dla nas choć trochę użyteczny, musimy sami mu pomóc. Jak?

• Poprawmy błędy kompilacji. Dotyczy to zwłaszcza błędów w nagłówkach (jako że są one dołączane wielokrotnie w różnych plikach .cpp) oraz błędów powodujących trudności w określeniu, gdzie kończą się poszczególne fragmenty kodu (czyli wszelkiego rodzaju nieprawidłowych nawiasowań). Drobne pomyłki w rodzaju literówek w identyfikatorach wpływają zwykle tylko na tę linijkę kodu, w której występują, a po korekcie IS potrafi bardzo szybko wrócić do działania.
• Uważajmy na preprocesor i nagłówki. MSDN jawnie specyfikuje jedną sytuację, w której IntelliSense nie musi działać. Dotyczy to wielokrotnego dołączania tego samego pliku nagłówkowego w taki sposób, że makra (#define‘y) wpływają na sposób, w jaki jest on przetwarzany. Przykładem może być dołączenie windows.h raz normalnie, a drugi raz z uprzednio zdefiniowanym makrem WIN32_LEAN_AND_MEAN.
• Jeśli wszystko zawodzi, wygenerujmy od początku plik .ncb. W tym pliku (często największym w całym projekcie) IntelliSense przechowuje informacje o strukturze kodu. Jeśli często “rozgrzebujemy” nasz projekt, czynimy w nim duże zmiany i dokonujemy refaktoringu, to plik ten może zawierać nieaktualne, nadmiarowe lub nieprawidłowe informacje albo po prostu być uszkodzony. W takim wypadku należy go po prostu usunąć, a następnie przeprowadzić ponowne kompilację całego solution.

Nie ma oczywiście gwarancji, że powyższe kroki sprawią, że IntelliSense poradzi sobie z podpowiadaniem w każdej sytuacji. Kod C++, zwłaszcza skomplikowany i korzystający z wielu “sztuczek językowych” (jak np. bibliotek Boost) nie jest łatwy do programowej analizy. Pozostaje więc mieć nadzieję, że w przyszłych wersjach VS z autouzupełnianiem będzie już lepiej; podobno w wersji 2010 jest z tym już całkiem nieźle :)

Shadery i pliki efektów – sprostowanie

Płynne przejście od programowania grafiki 3D przy pomocy fixed pipeline do wykorzystania shaderów nie jest z początku takie proste. Jest oczywiście w sieci mnóstwo tutoriali, które to ułatwiają. Zauważyłem jednak, że mają one tendencję do przekazywania naciąganych – mówiąc delikatnie – faktów na temat tego, w jaki sposób shadery oraz pliki efektów .fx (często omawiane łącznie) muszą być wykorzystywane w aplikacjach DirectX.
Dlatego pomyślałem sobie, że dobrze byłoby sprostować kilka mitów, jakie się tutaj pojawiają i wprowadzają zamieszanie do i tak niełatwej dziedziny programowania. Warto bowiem wiedzieć, iż to nieprawda, że:

• …korzystając z shaderów, musimy używać też plików .fx. Shader wierzchołków czy pikseli możemy samodzielnie wczytać z pliku (w wersji skomplikowanej lub przeprowadzić kompilację przy pomocy funkcji D3DX) czy nawet wygenerować dynamicznie, a potem zwyczajnie ustawić go jako aktualny VS/PS przy pomocy metod SetVertex/PixelShader urządzenia DirectX. Plik efektów nie jest wtedy do niczego potrzebny.
• …pliki .fx są tylko po to, by łatwiej wczytywać/aplikować shadery do renderowania. W rzeczywistości celem istnienia plików efektów jest uproszczenie kodowania różnych efektów graficznych w wersjach zależnych od możliwości poszczególnych kart. Zamiast samodzielnie sprawdzać capsy (możliwości) sprzętu, na którym uruchamia się nasza aplikacja, możemy po prostu pozwolić DirectX-owi wyszukać w pliku .fx tą wersję efektu (tzw. technikę), która na danej konfiguracji sprzętowej będzie działać. W ten sposób możemy na przykład napisać dwie wersje oświetlenia: jedną per pixel z użyciem shaderów i drugą, używającą fixed pipeline i oświetlającą wierzchołkowo. Nie musi ona wtedy korzystać z żadnych shaderów.
• …aby stosować shadery, musimy porzucić FVF na rzecz vertex declaration. Jest to piramidalna bzdura, która na szczęście rzadko bywa wygłaszana wprost, ale często wynika ze sposobu omawiania tematu VD w tutorialach. W istocie stałe D3DFVF tak samo dobrze opisują format danych dla vertex shaderów, jak deklaracje wierzchołków (IDirect3DVertexDeclarationX) i DirectX nie ma problemu z łączeniem jednego z drugim. Analogia działa zresztą też w drugą stroną: użycie fixed pipeline nie wymusza korzystania z FVF.
  Oczywiście bardziej zaawansowane techniki pisane z użyciem shaderów najczęściej potrzebują na wejściu danych, których w FVF zapisać się nie da (np. wektorów stycznych i binormalnych). Wtedy rzecz jasna potrzebne jest określenie formatu wierzchołków poprzez vertex declaration. Dla prostych VS-ów (jak choćby zwykłego m4x4 oPos, v0, c4) sam fakt korzystania z programowalnego potoku grafiki nic nie wymusza w zakresie formatu danych wierzchołków.
• …vertex i pixel shadery musimy zawsze stosować łącznie. To prawie logiczna konsekwencja częstego stwierdzenia (też niespecjalnie prawdziwego), że wyjście VS-a jest wejściem PS-a. W rzeczywistości nie jest to prawdą i łatwo można podać przykłady technik, w których możemy np. użyć pixel shadera bez vertex shadera – jak choćby zamiana wszystkich kolorów w scenie na odcienie szarości.
• …shadery zastępują cały potok renderowania. Chociaż oświetlenie, teksturowanie, transformacje macierzowe wierzchołków itp. to spory kawałek potoku renderowania, zastąpienie ich shaderami wcale nie oznacza, że nic już poza tym nie zostało. Rzeczy takie jak alpha blending, usuwanie tylnich ścian (culling), różne testy pikseli (głębokości, alfa, stencil) i przycinanie (np. płaszczyznami oraz scissor test) to tylko niektóre z elementów potoku, które są dostępne niezależnie od tego, czy obecne są w nim także załadowane przez użytkownika shadery.