Fundamenty

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ć.