Miesiąc: Sierpień 2011

Maski bitowe

Dzisiejszy post rozpoczyna cykl fundamenty, w którym będę pisał o różnych rzeczach, które same z siebie nie są zbyt ciekawe ale, czasem ich zrozumienie może okazać się niezwykle przydatne. Będzie tu mowa o reprezentacji danych w pamięci (U2, c-string), strukturach danych(stos, kolejka), algorytmach czy konwencjach wywołania funkcji.
Na pierwszy ogień idą maski bitowe. Posłużmy się przykładem. Wyobraźmy sobie system plików w którym możemy nadać takie oto atrybuty: systemowy, ukryty, archiwalny, tylko do odczytu, wykonywalny, skompresowany, zaszyfrowany, indeksowany. Zastanówmy się teraz w jaki sposób przechować informacje o nich. W tym celu możemy skorzystać z masek bitowych. Atrybutów jest 8, każdy z nich jest(1) albo nie jest(0) aktywny. Potrzebujemy co najmniej 8 bitów – akurat tyle ile ma unsigned char. Każdemu bitowi przypisujemy jeden atrybut:

Systemowy          00 00 00 01
Ukryty             00 00 00 10
Archiwalny         00 00 01 00
Tylko do odczytu   00 00 10 00
Skompresowany      00 01 00 00
Wykonywalny        00 10 00 00
Zaszyfrowany       01 00 00 00
Indeksowany        10 00 00 00

Chcąc przypisać atrybuty danemu plikowi wykorzystujemy alternatywę logiczną (OR). Np. mamy plik ukryty i chcemy go dodatkowo uczynić systemowym.

Oryginalne atrybuty:    00 00 00 10
Systemowy:              00 00 00 01
                    OR  -----------
Wynikowe atrybuty:      00 00 00 11

Chcąc zdjąć atrybut moglibyśmy wykorzystać alternatywę wykluczającą (XOR). Np. z pliku oznaczonego jako skompresowany, wykonywalny i zaszyfrowany zdejmujemy atrybut skompresowany.

Oryginalne atrybuty:    01 11 00 00
Skompresowany:          00 01 00 00
                    XOR -----------
Wynikowe atrybuty:      01 10 00 00

Wszystko jest OK, ale rozważmy przykład gdy atrybut skompresowany nie był ustawiony:

Oryginalne atrybuty:    01 10 00 00
Skompresowany:          00 01 00 00
                    XOR -----------
Wynikowe atrybuty:      01 11 00 00

Jak widać pomimo tego że naszą intencją było zdjęcie tego atrybutu stało się inaczej. Jeżeli chcemy mieć pewność że dany bit zostanie zdjęty należy wykonać dwie operacje. Po pierwsze zanegować(NEG) flagę którą chcemy zdjąć, a następnie skorzystać z iloczynu. Analogicznie:

Systemowy:                00 01 00 00
                      NEG -----------
Zanegowany systemowy:     11 10 11 11
Oryginalne atrybuty:      01 10 00 00
                      AND -----------
Wynikowe atrybuty:        01 10 00 00

Aby odczytać czy dany atrybut jest ustawiony korzystamy z iloczynu (AND). Np sprawdzamy czy poprzedni plik jest wykonywalny:

Oryginalne atrybuty:    01 11 00 00
Wykonywalny:            00 10 00 00
                    AND -----------
Wynik:                  00 10 00 00
 Prawda (różne od zera)

oraz archiwalny:

Oryginalne atrybuty:    01 11 00 00
Archiwalny:             00 00 01 00
                    AND -----------
Wynik:                  00 00 00 00
 Fałsz (równe zero)

Maski można łączyć. Nadajmy plikowi A (wykonywalny, systemowy, ukryty) atrybuty archiwalny i skompresowany:

Archiwalny:                00 00 01 00
Skompresowany:             00 01 00 00
                        OR -----------
Wynikowa maska:            00 01 01 00
Oryginalne atrybuty:       00 10 00 11
                        OR -----------
Wynik:                     00 11 01 11

Tyle teorii. Sprawdźmy zatem jak takie rozwiązanie wygląda zaimplementowane w C.

Na początek zdefiniujmy flagi. Jak pamiętamy każda z nich musi mieć ustawiony jeden, unikalny bit. Są przynajmniej trzy sposoby aby to zrobić:
Każda kolejna flaga to po prostu kolejna potęga dwójki.


#define SYSTEM         1
#define HIDDEN         2
#define ARCHIVED       4
#define READONLY       8
#define ZIPPED         16
#define EXECUTABLE     32
#define ENCRYPTED      64
#define INDEXED        128

Możemy zapisać to heksadecymalnie:

#define SYSTEM         0x1
#define HIDDEN         0x2
#define ARCHIVED       0x4
#define READONLY       0x8
#define ZIPPED         0x10
#define EXECUTABLE     0x20
#define ENCRYPTED      0x40
#define INDEXED        0x80

Lub jawnie określić który (od prawej) bit będzie zapalony:

#define SYSTEM         (1 << 0)
#define HIDDEN         (1 << 1)
#define ARCHIVED       (1 << 2)
#define READONLY       (1 << 3)
#define ZIPPED         (1 << 4)
#define EXECUTABLE     (1 << 5)
#define ENCRYPTED      (1 << 6)
#define INDEXED        (1 << 7)

Które rozwiązanie jest najlepsze? Trudno powiedzieć. Osobiście przy niedużej liczbie flag (<15) korzystam z pierwszej. Gdyby trzeba było ich więcej to trzeci sposób sprawdziłby się prawdopodobnie lepiej. Ważne tylko aby w jednej fladze był zapalony tylko jeden bit.

Następnie napiszmy funkcję która wypisze atrybuty pliku:

void print_attributes(unsigned char file)
{
printf("Atrybuty pliku\n");
if(file & SYSTEM)
    printf("systemowy, ");
if(file & HIDDEN)
    printf("ukryty, ");
if(file & ARCHIVED)
    printf("archiwalny, ");
if(file & READOLNY)
    printf("tylko do odczytu, ");
if(file & ZIPPED)
    printf("skompresowany, ");
if(file & EXECUTABLE)
    printf("wykonywalny, ");
if(file & ENCRYPTED)
    printf("zaszyfrowany, ");
if(file & INDEXED)
    printf("indeksowany, ");
}

Za pomocą koniunkcji sprawdzamy czy bit przy danym atrybucie jest ustawiony, jeśli tak wypisujemy nazwę atrybutu.

Teraz możemy sprawdzić działanie:

#include <stdio.h>

#define SYSTEM         1
#define HIDDEN         2
#define ARCHIVED       4
#define READONLY       8
#define ZIPPED         16
#define EXECUTABLE     32
#define ENCRYPTED      64
#define INDEXED        128

void print_attributes(unsigned char file)
{
printf("Atrybuty pliku: ");
if(file & SYSTEM)
    printf("systemowy, ");
if(file & HIDDEN)
    printf("ukryty, ");
if(file & ARCHIVED)
    printf("archiwalny, ");
if(file & READONLY)
    printf("tylko do odczytu, ");
if(file & ZIPPED)
    printf("skompresowany, ");
if(file & EXECUTABLE)
    printf("wykonywalny, ");
if(file & ENCRYPTED)
    printf("zaszyfrowany, ");
if(file & INDEXED)
    printf("indeksowany, ");
printf("\n");
}

int main()
{
/*dla przypomnienia:
| - OR - suma
^ - XOR - alternatywa wykluczająca
&amp; - AND - iloczyn/koniunkcja
~ - NEG - negacja
plik zainicjowany jako ukryty i systemowy*/
unsigned char file = SYSTEM | HIDDEN;
printf("Oczekiwany ukryty, systemowy:\n");
print_attributes(file);

/*dodanie tylko do odczytu i skompresowany*/
file |= READONLY | ZIPPED;
printf("Oczekiwany ukryty, systemowy, tylko do odczytu, skompresowany:\n");
print_attributes(file);

/*usunięcie systemowy*/
file &= ~SYSTEM;
printf("Oczekiwany ukryty, tylko do odczytu, skompresowany:\n");
print_attributes(file);

/*Spróbujmy usunąć jeszcze raz bay upewnić się że teoria się sprawdza*/
file &= ~SYSTEM;
printf("Oczekiwany ukryty, tylko do odczytu, skompresowany:\n");
print_attributes(file);

/*sprawdzenie czy ukryty */
int cond = file & HIDDEN;
if(cond)
printf("ukryty - prawda\n");
else
printf("ukryty - fałsz\n");

/*sprawdzenie czy zaszyfrowany*/
cond = file & ENCRYPTED;
if(cond)
printf("zaszyfrowany - prawda\n");
else
printf("zaszyfrowany - fałsz\n");

return 0;
}

Na koniec warto ostrzec o jednym. Konstrukcja taka jak:

if(file & (SYSTEM | HIDDEN))
   /*....*/

NIE spowoduje sprawdzenia czy SYSTEM i HIDDEN są ustawione. Sprawdzi czy którykolwiek z nich jest ustawiony. Warto o tym pamiętać.

Ikonki folderów programów.

Lubię kiedy foldery w Program Files mają ikonki programów. Nie widziałem żeby ktokolwiek inny tak miał więc to chyba nie jest normalne 😛 W każdym razie często otwieram Program Files i własna ikonka każdego programu pozwala mi szybciej znajdować to czego szukam. Do tej pory zmieniałem je ręcznie co zajmowało dużo czasu i było bardzo nudnym zajęciem. Dziś wpadłem wreszcie na genialny pomysł – przecież jestem programista więc mogę sobie to zautomatyzować.Implementacja

Założenia są proste: folder posiadający własną ikonkę zawiera plik desktop.ini z odpowiednimi informacjami. Wygląda to mniej więcej tak:

[.ShellClassInfo]
IconFile=C:\Program Files\Synthesia.exe
IconIndex=0

Jest to prosty plik ini w którym zawierają się dwie istotne z naszego punktu widzenia informacje (o pozostałych można poczytać chociażby tu). IconFile to ścieżka do pliku z ikonką. Jak widać poza *.ico może to być exe lub dll – jeśli w zasobach programu znajdują się ikony (a jest tak praktycznie zawsze). IconIndex to numer ikonki – gdyż może być ich wiele w programie.

Sądziłem że to już koniec, ale okazuje się że nie. Plik desktop.ini musi posiadać atrybuty systemowy i ukryty. Ponadto folder zawierający ów plik również musi być oznaczony atrybutem systemowy.

I to w zasadzie wszystko. Napisany przeze mnie programik ustawia pierwszą ikonę jaką znajdzie na ikonę folderu więc czasem zdarza się że ikona deinstalatora nawinie się wcześniej, jest to jednak niewielka cena, ponadto można to poprawić ręcznie.

Quo vadis?

Ostatni miesiąc przeznaczyłem głównie na rozmyślania nad swoimi celami. Tutaj podzielę się tym co wymyśliłem w sferze związanej z programowaniem. W trakcie mojej krótkiej aczkolwiek burzliwej kariery zapoznałem (mniej lub bardziej) pobieżnie się z wieloma językami i zastosowaniami programowania. Były to głównie:

  • HTML + CSS + JavaScript
  • PHP/Ruby on Rails
  • Python
  • C# i .NET oraz XNA
  • Java
  • C++ i SDL/Allegro/SFML/DirectX/OpenGL/Irrlicht/OGRE
  • PowersShell i Bash
  • Assembler
  • Delphi/Object Pascal

Jak widać rozrzut technologii dosyć spory ale sądzę, że dało mi to wystarczająco dużo doświadczeń aby móc zdecydować na czym się skupić (jak coś jest do wszystkiego to jest do niczego). Epizod związany z gamedev był chyba najdłuższy i najbardziej zaawansowany, ale ostatecznie wiem że nie chcę się tym zajmować. Technologie webowe również mnie nie pociągają.

Wybrałem sobie trzy które intensywnie będę zgłębiać dalej:

  1.  Assembler – tak wiem, że tego się już nie używa, że trudny, że błędogenny, że długo się w nim pisze a rezultaty nie są spektakularne. Ale assembler ma dla mnie jedną niezwykle istotną cechę: jest na bardzo niskim poziomie abstrakcji co pozwala mi zrozumieć jak wszystko dokładnie działa. Pisząc w C++ wiedziałem, że „argumenty wrzuca się na stos od końca”. Pisząc w assemblerze wiem, że „argumenty umieszczane są na stosie instrukcją push, która… […] …rejestr esp wskazuje na ostatni element stosu…”. Po co mi to wiedzieć? Prawdę powiedziawszy nie wiem, ale czuję się dużo bardziej komfortowo rozumiejąc co dzieje się za kulisami.
  2. C++ – w tym języku programuję w sumie najdłużej i najintensywniej. Podoba mi się w nim jego względna wysokopoziomowość programowania obiektowego jak względna niskopoziomowość (wstawki asm, wskaźniki ❤ ). Ponadto w tym języku zwykle widać co się tak naprawdę dzieje, można swobodnie kontrolować czy przekazać parametr przez wartość czy przez referencje oraz stosować magiczne szablony i makra 😉
  3.  Java – rozwiązanie wysokopoziomowe. W tej kategorii wygrała dzięki swojej przenośności. Javę mają prawie wszyscy, ile znacie osób które na Windows mają Pythona? .NET to z kolei w mojej opinii takie trochę niewiadomo-co. Ani to przenośne, ani przywiązane do Windows (do użycia natywnych funkcji trzeba użyć platform invocation). Kończąc wątek .NET szkoda mi C# w którym pisze mi się doprawdy sympatycznie (lambdy, LINQ). W zasadzie dopiero zaczynam poznawać Javę lecz sugerując się powszechną opinią odnośnie jej podobieństwa do C# jestem nastawiony optymistycznie.

Z niecierpliwością czekam na nowy PC (to będzie najdłuższy miesiąc w moim życiu 😉 ). Wtedy zacznę pisać super-pure-64-bit-mega-ultra OS który na wzór i podobieństwo Mac OS będzie kompatybilny tylko sam ze sobą 😉 .