Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00751 010216 10704505 na godz. na dobę w sumie
Profesjonalne programowanie. Część 1. Zrozumieć komputer - książka
Profesjonalne programowanie. Część 1. Zrozumieć komputer - książka
Autor: Liczba stron: 392
Wydawca: Helion Język publikacji: polski
ISBN: 83-7361-859-7 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> inne - programowanie
Porównaj ceny (książka, ebook, audiobook).

Chcesz zostać programistą doskonałym?
Zacznij od poznania szczegółów działania komputera

Kod napisany przez profesjonalnego programistę jest wydajny i efektywny. Aby tworzyć wydajny kod, należy poznać architekturę komputera i sposób, w jaki program jest wykonywany. Zrozumienie tego, w jaki sposób komputer realizuje kolejne instrukcje programu i jak słowa kluczowe języków wysokiego poziomu są przenoszone na rozkazy procesora, jest kluczem do napisania kodu, który po skompilowaniu da szybko i bezbłędnie działający program.

'Profesjonalne programowanie. Część 1. Zrozumieć komputer' to pierwszy tom serii książek przeznaczonych dla tych programistów, którzy chcą podnieść swoje kwalifikacje. Przedstawia wewnętrzną architekturę komputera od strony, której znajomość jest niezbędna programiście. Opisuje sposoby zapisu wartości liczbowych i tekstów, działania na liczbach binarnych i zmiennoprzecinkowych oraz logikę Boole'a. Czytając tę książkę, dowiesz się, w jaki sposób procesor przetwarza rozkazy asemblera, jak odbywa się dostęp do danych zapisanych w pamięci oraz jak przesyłane są dane do i z urządzeń zewnętrznych.

Jeśli chcesz, aby napisane przez Ciebie oprogramowanie budziło podziw, koniecznie przeczytaj tę książkę.

Znajdź podobne książki Ostatnio czytane w tej kategorii

Darmowy fragment publikacji:

IDZ DO IDZ DO PRZYK£ADOWY ROZDZIA£ PRZYK£ADOWY ROZDZIA£ SPIS TREŒCI SPIS TREŒCI KATALOG KSI¥¯EK KATALOG KSI¥¯EK KATALOG ONLINE KATALOG ONLINE ZAMÓW DRUKOWANY KATALOG ZAMÓW DRUKOWANY KATALOG TWÓJ KOSZYK TWÓJ KOSZYK DODAJ DO KOSZYKA DODAJ DO KOSZYKA CENNIK I INFORMACJE CENNIK I INFORMACJE ZAMÓW INFORMACJE ZAMÓW INFORMACJE O NOWOŒCIACH O NOWOŒCIACH ZAMÓW CENNIK ZAMÓW CENNIK CZYTELNIA CZYTELNIA FRAGMENTY KSI¥¯EK ONLINE FRAGMENTY KSI¥¯EK ONLINE Wydawnictwo Helion ul. Chopina 6 44-100 Gliwice tel. (32)230-98-63 e-mail: helion@helion.pl Profesjonalne programowanie. Czêœæ 1. Zrozumieæ komputer Autor: Randall Hyde T³umaczenie: Tomasz ¯mijewski ISBN: 83-7361-859-7 Tytu³ orygina³u: Write Great Code. Volume 1: Understanding the Machine Format: B5, stron: 392 Chcesz zostaæ programist¹ doskona³ym? Zacznij od poznania szczegó³ów dzia³ania komputera (cid:129) Zapis wartoœci liczbowych oraz arytmetyka zmiennoprzecinkowa i binarna (cid:129) Organizacja dostêpu do pamiêci komputera (cid:129) Proces wykonywania programu oraz operacje wejœcia i wyjœcia Kod napisany przez profesjonalnego programistê jest wydajny i efektywny. Aby tworzyæ wydajny kod, nale¿y poznaæ architekturê komputera i sposób, w jaki program jest wykonywany. Zrozumienie tego, w jaki sposób komputer realizuje kolejne instrukcje programu i jak s³owa kluczowe jêzyków wysokiego poziomu s¹ przenoszone na rozkazy procesora, jest kluczem do napisania kodu, który po skompilowaniu da szybko i bezb³êdnie dzia³aj¹cy program. „Profesjonalne programowanie. Czêœæ 1. Zrozumieæ komputer” to pierwszy tom serii ksi¹¿ek przeznaczonych dla tych programistów, którzy chc¹ podnieœæ swoje kwalifikacje. Przedstawia wewnêtrzn¹ architekturê komputera od strony, której znajomoœæ jest niezbêdna programiœcie. Opisuje sposoby zapisu wartoœci liczbowych i tekstów, dzia³ania na liczbach binarnych i zmiennoprzecinkowych oraz logikê Boole’a. Czytaj¹c tê ksi¹¿kê, dowiesz siê, w jaki sposób procesor przetwarza rozkazy asemblera, jak odbywa siê dostêp do danych zapisanych w pamiêci oraz jak przesy³ane s¹ dane do i z urz¹dzeñ zewnêtrznych. (cid:129) Zapis liczb w systemie binarnym, ósemkowym i szesnastkowym (cid:129) Dzia³ania na liczbach binarnych i zmiennoprzecinkowych (cid:129) Sposoby reprezentacji danych znakowych (cid:129) Organizacja pamiêci i tryby adresowania (cid:129) Z³o¿one typy danych (cid:129) Projektowanie uk³adów cyfrowych i logika Boole’a (cid:129) Architektura procesora i rozkazy asemblera (cid:129) Operacje wejœcia i wyjœcia Jeœli chcesz, aby napisane przez Ciebie oprogramowanie budzi³o podziw, koniecznie przeczytaj tê ksi¹¿kê. Spis treści Podziękowania .................................................................................. 9 Rozdział 1. Co trzeba wiedzieć o programowaniu doskonałym ............................ 11 1.1. Seria książek „Profesjonalne programowanie” .................................................... 11 1.2. O czym jest ta książka ......................................................................................... 12 1.3. Wymagania wobec Czytelnika ............................................................................ 15 1.4. Cechy kodu doskonałego ..................................................................................... 15 1.5. Wymagane środowisko ........................................................................................ 16 1.6. Dalsze informacje ................................................................................................ 17 Rozdział 2. Zapis liczb ...................................................................................... 19 2.1. Czym jest liczba? ................................................................................................. 19 2.2. Systemy liczbowe ................................................................................................ 20 2.2.1. Dziesiętny pozycyjny system liczbowy ................................................... 21 2.2.2. Podstawa .................................................................................................. 22 2.2.3. Binarny system liczbowy ......................................................................... 23 2.2.4. Szesnastkowy system liczbowy ............................................................... 24 2.2.5. Liczby ósemkowe .................................................................................... 26 2.3. Konwersja między liczbą a tekstem ..................................................................... 28 2.4. Zapis liczb całkowitych ....................................................................................... 29 2.4.1. Bity .......................................................................................................... 29 2.4.2. Łańcuchy bitowe ...................................................................................... 30 2.5. Liczby ze znakiem i bez znaku ............................................................................ 32 2.6. Pewne przydatne cechy liczb binarnych .............................................................. 34 2.7. Rozszerzenie znakiem, uzupełnienie zerami i zawężenie .................................... 35 2.8. Nasycenie ............................................................................................................ 38 2.9. Zapis dziesiętny kodowany binarnie (BCD) ........................................................ 39 2.10. Zapis stałopozycyjny ........................................................................................... 40 2.11. Skalowane formaty liczbowe ............................................................................... 43 2.12. Zapis wymierny ................................................................................................... 45 2.13. Więcej informacji ................................................................................................ 45 Rozdział 3. Arytmetyka binarna i działania na bitach ......................................... 47 3.1. Działania arytmetyczne na liczbach dwójkowych i szesnastkowych ................... 47 3.1.1. Dodawanie wartości binarnych ................................................................ 48 3.1.2. Odejmowanie liczb binarnych .................................................................. 49 3.1.3. Mnożenie wartości binarnych .................................................................. 50 3.1.4. Dzielenie wartości binarnych ................................................................... 51 3.2. Operacje logiczne na bitach ................................................................................. 52 3.3. Operacje logiczne na liczbach binarnych i ciągach bitów .................................... 54 4 Profesjonalne programowanie. Część 1. Zrozumieć komputer 3.4. Przydatne operacje bitowe ................................................................................... 55 3.4.1. Sprawdzanie poszczególnych bitów łańcucha za pomocą operatora AND ....55 3.4.2. Sprawdzanie, czy grupa bitów zawiera same zera ...........................................56 3.4.3. Porównywanie zestawu bitów z łańcuchem binarnym ....................................56 3.4.4. Tworzenie liczników modulo n za pomocą operacji AND ..............................57 3.5. Przesunięcia i rotacje ........................................................................................... 58 3.6. Pola bitowe i pakowanie danych .......................................................................... 61 3.7. Pakowanie i rozpakowywanie danych ................................................................. 64 3.8. Więcej informacji ................................................................................................ 68 Rozdział 4. Zapis zmiennopozycyjny .................................................................. 69 4.1. Wprowadzenie do arytmetyki zmiennopozycyjnej .............................................. 69 4.2. Formaty zmiennopozycyjne IEEE ....................................................................... 74 4.2.1. Zmiennopozycyjny format pojedynczej precyzji ..................................... 75 4.2.2. Format zmiennopozycyjny o podwójnej precyzji .................................... 77 4.2.3. Format zmiennopozycyjny zwiększonej precyzji ..................................... 77 4.3. Normalizacja i wartości nienormalizowane ......................................................... 78 4.4. Zaokrąglanie ........................................................................................................ 79 4.5. Specjalne wartości zmiennopozycyjne ................................................................ 80 4.6. Wyjątki obliczeń zmiennopozycyjnych ............................................................... 82 4.7. Działania zmiennopozycyjne ............................................................................... 82 4.7.1. Zapis liczb zmiennopozycyjnych ............................................................. 83 4.7.2. Dodawanie i odejmowanie zmiennopozycyjne ........................................ 83 4.7.3. Mnożenie i dzielenie zmiennopozycyjne ................................................. 93 4.8. Więcej informacji ................................................................................................ 99 Rozdział 5. Dane znakowe .............................................................................. 101 5.1. Dane znakowe .................................................................................................... 101 5.1.1. Zestaw znaków ASCII ........................................................................... 101 5.1.2. Zestaw znaków EBCDIC ....................................................................... 104 5.1.3. Dwubajtowe zestawy znaków ................................................................ 105 5.1.4. Zestaw znaków Unicode ........................................................................ 106 5.2. Łańcuchy znakowe ............................................................................................ 108 5.2.1. Formaty łańcuchów znakowych ............................................................. 108 5.2.2. Rodzaje łańcuchów — statyczne, pseudodynamiczne i dynamiczne ..... 112 5.2.3. Zliczanie odwołań do łańcucha .............................................................. 114 5.2.4. Łańcuchy w Delphi i Kyliksie ................................................................ 114 5.2.5. Tworzenie własnych formatów łańcuchów ............................................ 115 5.3. Zbiory znaków ................................................................................................... 115 5.3.1. Zbiory znaków w formie zbioru przynależności .................................... 115 5.3.2. Listowa reprezentacja zbiorów znaków ................................................. 117 5.4. Definiowanie własnego zestawu znaków ........................................................... 117 5.4.1. Tworzenie wydajnego zestawu znaków ................................................. 118 5.4.2. Grupowanie znaków odpowiadających cyfrom ..................................... 120 5.4.3. Grupowanie liter .................................................................................... 120 5.4.4. Porównywanie liter ................................................................................ 122 5.4.5. Inne grupowania znaków ....................................................................... 123 5.5. Dodatkowe informacje ....................................................................................... 124 Rozdział 6. Organizacja pamięci i dostęp do niej ............................................. 127 6.1. Podstawowe elementy systemu .......................................................................... 127 6.1.1. Magistrala systemowa ............................................................................ 128 6.2. Fizyczna organizacja pamięci ............................................................................ 130 6.2.1. 8-bitowe magistrale danych ................................................................... 132 6.2.2. 16-bitowe magistrale danych ................................................................. 133 6.2.3. 32-bitowe magistrale danych ................................................................. 134 Spis treści 5 6.2.4. Magistrale 64-bitowe ............................................................................. 136 6.2.5. Dostęp do pamięci w procesorach innych niż 80x86 ............................. 136 6.3. Kolejność bajtów ............................................................................................... 136 6.4. Zegar systemowy ............................................................................................... 141 6.4.1. Dostęp do pamięci a zegar systemowy ................................................... 142 6.4.2. Stany oczekiwania ................................................................................. 143 6.4.3. Pamięć podręczna .................................................................................. 145 6.5. Dostęp procesora do pamięci ............................................................................. 148 6.5.1. Bezpośredni tryb adresowania pamięci .................................................. 149 6.5.2. Tryb adresowania pośredniego ............................................................... 149 6.5.3. Tryb adresowania indeksowanego ......................................................... 150 6.5.4. Skalowane indeksowane tryby adresowania .......................................... 151 6.6. Dodatkowe informacje ....................................................................................... 151 Rozdział 7. Złożone typy danych i obiekty w pamięci ....................................... 153 7.1. Typy wskaźnikowe ............................................................................................ 153 7.1.1. Implementacja wskaźników ................................................................... 154 7.1.2. Wskaźniki i dynamiczna alokacja pamięci ............................................. 155 7.1.3. Działania na wskaźnikach — arytmetyka wskaźników .......................... 155 7.2. Tablice ............................................................................................................... 159 7.2.1. Deklaracje tablic .................................................................................... 160 7.2.2. Reprezentacja tablic w pamięci .............................................................. 162 7.2.3. Dostęp do elementów tablicy ................................................................. 163 7.2.4. Tablice wielowymiarowe ....................................................................... 164 7.3. Rekordy (struktury) ........................................................................................... 170 7.3.1. Rekordy w Pascalu i Delphi ................................................................... 170 7.3.2. Rekordy w C i C++ ................................................................................ 171 7.3.3. Rekordy w HLA ..................................................................................... 171 7.3.4. Zapis rekordów w pamięci ..................................................................... 171 7.4. Unie ................................................................................................................... 174 7.4.1. Unie w C i C++ ...................................................................................... 174 7.4.2. Unie w Pascalu, Delphi i Kyliksie ......................................................... 174 7.4.3. Unie w asemblerze HLA ........................................................................ 175 7.4.4. Unie w pamięci ...................................................................................... 176 7.4.5. Inne zastosowania unii ........................................................................... 176 7.5. Dodatkowe informacje ....................................................................................... 177 Rozdział 8. Logika boolowska i projektowanie cyfrowe .................................... 179 8.1. Algebra Boole’a ................................................................................................. 179 8.1.1. Operatory boolowskie ............................................................................ 179 8.1.2. Prawa algebry boolowskiej .................................................................... 180 8.1.3. Priorytety operatorów boolowskich ....................................................... 181 8.2. Funkcje logiczne i tabele prawdy ...................................................................... 182 8.3. Numery funkcji .................................................................................................. 183 8.4. Algebraiczne przekształcanie wyrażeń logicznych ............................................ 185 8.5. Formy kanoniczne ............................................................................................. 186 8.5.1. Forma kanoniczna sumy termów minimalnych a tabele prawdy ............ 187 8.5.2. Algebraiczne wyprowadzanie formy kanonicznej sumy termów minimalnych .................................................................... 189 8.5.3. Forma kanoniczna jako iloczyn termów maksymalnych ........................ 189 8.6. Upraszczanie funkcji logicznych ....................................................................... 190 8.7. Ale co to wszystko ma wspólnego z komputerami? .......................................... 197 8.7.1. Równoważność układów elektronicznych i funkcji logicznych ............. 198 8.7.2. Obwody złożone .................................................................................... 199 8.7.3. Sterowanie sekwencyjne i zegarowe ...................................................... 204 8.8. Dodatkowe informacje ....................................................................................... 208 6 Profesjonalne programowanie. Część 1. Zrozumieć komputer Rozdział 9. Architektura procesora ................................................................. 209 9.1. Podstawy budowy procesora ............................................................................. 209 9.2. Dekodowanie i wykonywanie instrukcji — logika przypadku a mikrokod ....... 211 9.3. Wykonywanie instrukcji krok po kroku ............................................................. 213 9.3.1. Instrukcja mov ....................................................................................... 213 9.3.2. Instrukcja add ......................................................................................... 215 9.3.3. Instrukcja jnz .......................................................................................... 217 9.3.4. Instrukcja loop ....................................................................................... 218 9.4. Równoległość — klucz do przyspieszenia ......................................................... 218 9.4.1. Kolejka wstępnego pobrania .................................................................. 222 9.4.2. Okoliczności ograniczające wydajność kolejki wstępnego pobrania ..... 225 9.4.3. Potoki — jednoczesne wykonywanie wielu instrukcji ........................... 226 9.4.4. Bufory instrukcji — wiele dróg do pamięci ........................................... 230 9.4.5. Zagrożenia związane z potokami ........................................................... 231 9.4.6. Działanie superskalarne — równoległe wykonywanie instrukcji ........... 233 9.4.7. Wykonywanie kodu bez zachowania kolejności .................................... 235 9.4.8. Zmiana nazw rejestrów .......................................................................... 235 9.4.9. Architektura z bardzo długim słowem instrukcji (VLIW) ...................... 236 9.4.10. Przetwarzanie równoległe ...................................................................... 237 9.4.11. Wieloprocesorowość .............................................................................. 238 9.5. Dodatkowe informacje ....................................................................................... 239 Rozdział 10. Konstrukcja zbioru instrukcji ......................................................... 241 10.1. Dlaczego projekt zbioru instrukcji jest ważny ................................................... 241 10.2. Podstawowe cele projektowe zestawu instrukcji ............................................... 243 10.2.1. Dobór długości kodu instrukcji .............................................................. 245 10.2.2. Plany na przyszłość ................................................................................ 247 10.2.3. Dobór instrukcji ..................................................................................... 247 10.2.4. Przypisywanie instrukcjom kodów ........................................................ 248 10.3. Hipotetyczny procesor Y86 ............................................................................... 248 10.3.1. Ograniczenia Y86 .................................................................................. 249 10.3.2. Instrukcje Y86 ........................................................................................ 249 10.3.3. Tryby adresowania Y86 ......................................................................... 251 10.3.4. Kodowanie instrukcji Y86 ..................................................................... 252 10.3.5. Przykłady kodowania instrukcji Y86 ..................................................... 254 10.3.6. Rozszerzanie zbioru instrukcji Y86 ....................................................... 257 10.4. Kodowanie instrukcji 80x86 .............................................................................. 259 10.4.1. Kodowanie operandów instrukcji .......................................................... 260 10.4.2. Kodowanie instrukcji add — kilka przykładów ..................................... 266 10.4.3. Stałe jako operandy ................................................................................ 268 10.4.4. Kodowanie operandów 8-, 16- i 32-bitowych ........................................ 269 10.4.5. Alternatywne kodowanie instrukcji ....................................................... 270 10.5. Znaczenie projektu zbioru instrukcji dla programisty ........................................ 270 10.6. Więcej informacji .............................................................................................. 271 Rozdział 11. Architektura pamięci i jej organizacja ............................................ 273 11.1. Hierarchia pamięci ....................................................................................................273 11.2. Jak działa hierarchia pamięci ....................................................................................276 11.3. Względna wydajność podsystemów pamięci ..........................................................277 11.4. Budowa pamięci podręcznej ....................................................................................279 11.4.1. Pamięć odwzorowywana bezpośrednio ..........................................................280 11.4.2. Pamięć w pełni powiązana ..............................................................................281 11.4.3. Pamięć powiązana n-krotnie ...........................................................................281 11.4.4. Dobieranie schematu pamięci podręcznej do rodzaju dostępu do danych ....282 Spis treści 7 11.4.5. Polityka wymiany zawartości wierszy ................................................... 282 11.4.6. Zapis danych w pamięci ......................................................................... 283 11.4.7. Użycie pamięci podręcznej i oprogramowanie ...................................... 284 11.5. Pamięć wirtualna, ochrona i stronicowanie ....................................................... 285 11.6. Zaśmiecanie ....................................................................................................... 288 11.7. NUMA i urządzenia peryferyjne ....................................................................... 289 11.8. Oprogramowanie świadome istnienia hierarchii pamięci .................................. 290 11.9. Organizacja pamięci w trakcie działania programu ........................................... 291 11.9.1. Obiekty statyczne i dynamiczne, wiązanie, czas życia .......................... 293 11.9.2. Kod, segmenty tylko do odczytu i segment stałych ............................... 294 11.9.3. Segment zmiennych statycznych ........................................................... 294 11.9.4. Segment danych niezainicjalizowanych (BSS) ...................................... 295 11.9.5. Segment stosu ........................................................................................ 295 11.9.6. Segment sterty i dynamiczna alokacja pamięci ...................................... 296 11.10. Dodatkowe informacje ...................................................................................... 301 Rozdział 12. Wejście i wyjście (I/O) ................................................................. 303 12.1. Połączenie procesora ze światem zewnętrznym ................................................ 303 12.2. Inne sposoby łączenia portu z systemem ........................................................... 306 12.3. Mechanizmy wejścia-wyjścia ............................................................................ 307 12.3.1. Odwzorowywanie w pamięci ................................................................. 307 12.3.2. Wejście-wyjście i buforowanie .............................................................. 308 12.3.3. Odwzorowywanie na I/O ....................................................................... 308 12.3.4. Bezpośredni dostęp do pamięci (DMA) ................................................. 309 12.4. Hierarchia szybkości wejścia-wyjścia ............................................................... 310 12.5. Szyny systemowe i szybkość transferu danych ................................................. 311 12.5.1. Wydajność magistrali PCI ..................................................................... 312 12.5.2. Wydajność magistrali ISA ..................................................................... 313 12.5.3. Magistrala AGP ..................................................................................... 313 12.6. Buforowanie ...................................................................................................... 314 12.7. Handshaking ...................................................................................................... 315 12.8. Przekroczenia czasu w porcie I/O ...................................................................... 316 12.9. Przerwania i próbkowanie I/O ........................................................................... 317 12.10. Działanie w trybie chronionym i sterowniki urządzeń ...................................... 318 12.10.1. Sterowniki urządzeń ............................................................................. 318 12.10.2. Komunikacja ze sterownikami urządzeń i „plikami” ........................... 319 12.11. Omówienie poszczególnych urządzeń peryferyjnych ........................................ 320 12.12. Klawiatura ......................................................................................................... 320 12.13. Standardowy port równoległy ........................................................................... 322 12.14. Porty szeregowe ................................................................................................ 323 12.15. Stacje dysków .................................................................................................... 324 12.15.1. Dyskietki .............................................................................................. 324 12.15.2. Dyski twarde ........................................................................................ 324 12.15.3. Systemy RAID ..................................................................................... 329 12.15.4. Napędy ZIP i inne miękkie napędy optyczne ....................................... 330 12.15.5. Napędy optyczne .................................................................................. 330 12.15.6. Napędy CD-ROM, CD-R, CD-RW, DVD, DVD-R, DVD-RAM i DVD-RW .............................................. 331 12.16. Napędy taśmowe ............................................................................................... 333 12.17. Pamięć flash ...................................................................................................... 334 12.18. Dyski RAM i dyski półprzewodnikowe ............................................................ 336 12.19. Urządzenia i sterowniki SCSI ............................................................................ 337 12.20. Interfejs IDE/ATA ............................................................................................. 342 8 Profesjonalne programowanie. Część 1. Zrozumieć komputer 12.21. Systemy plików na urządzeniach pamięci masowej .......................................... 344 12.21.1. Użycie mapy bitowej wolnej przestrzeni ............................................. 346 12.21.2. Tablice alokacji plików ........................................................................ 347 12.21.3. Pliki w formie list bloków .................................................................... 350 12.22. Oprogramowanie przetwarzające dane na urządzeniach pamięci masowej ....... 353 12.22.1. Wydajność dostępu do plików ............................................................. 354 12.22.2. Wejście-wyjście synchroniczne i asynchroniczne ................................ 355 12.22.3. Znaczenie typu operacji wejścia-wyjścia ............................................. 356 12.22.4. Pliki odwzorowywane w pamięci ........................................................ 356 12.23. Uniwersalna magistrala szeregowa (USB) ........................................................ 357 12.23.1. Projekt USB ......................................................................................... 358 12.23.2. Wydajność USB ................................................................................... 359 12.23.3. Rodzaje transmisji USB ....................................................................... 360 12.23.4. Sterowniki urządzeń USB .................................................................... 362 12.24. Myszy, trackpady i inne urządzenia wskazujące ............................................... 363 12.25. Joysticki i urządzenia do gier ............................................................................ 364 12.26. Karty dźwiękowe ............................................................................................... 365 12.26.1. Jak dźwiękowe urządzenia peryferyjne wytwarzają dźwięk? .............. 366 12.26.2. Formaty audio i pliki MIDI .................................................................. 368 12.26.3. Programowanie urządzeń audio ........................................................... 369 12.27. Dalsze informacje .............................................................................................. 369 Myśl lokalnie, pisz globalnie .......................................................... 371 Dodatek A Zestaw znaków ASCII ................................................................... 373 Skorowidz ..................................................................................... 377 Rozdział 5. Dane znakowe Wprawdzie komputery są kojarzone głównie z możliwościami obliczeniowymi, ale tak naprawdę znacznie częściej używa się ich do przetwarzania danych znakowych. Jeśli weźmiemy pod uwagę, jak istotne we współczesnych komputerach jest przetwa- rzanie znaków, pojmiemy, że bycie programistą doskonałym wymaga gruntownego zrozumienia danych i łańcuchów znakowych. Pojęcie znaku odnosi się do symbolu zrozumiałego dla człowieka lub dla maszyny, zwykle niebędącego liczbą. W zasadzie znak to symbol, który można wpisać z kla- wiatury i zobaczyć na monitorze. Pamiętajmy, że poza literami do danych znakowych zaliczają się też znaki przestankowe, cyfry, spacje, tabulatory, znaki powrotu karetki (klawisz ENTER), inne znaki kontrolne i znaki specjalne. W tym rozdziale przyjrzymy się, jak w komputerze są zapisywane znaki, łańcuchy i zbiory znaków. Omówimy też różne operacje na tych typach danych. 5.1. Dane znakowe Większość systemów do kodowania różnych znaków wykorzystuje pojedyncze bajty lub pary bajtów. Dotyczy to także systemów Windows i Linux wykorzystujących ze- stawy znaków ASCII lub Unicode, gdzie znaki zapisuje się w pojedynczym bajcie lub w dwubajtowym ciągu. Zestaw znaków EBCDIC używany w maszynach IBM main- frame i w minikomputerach to kolejny przykład jednobajtowego kodu znaków. Omówimy tutaj wszystkie trzy zestawy znaków i ich zapis wewnętrzny. Powiemy też, jak stworzyć własny, dostosowany do specyficznych potrzeb zestaw znaków. 5.1.1. Zestaw znaków ASCII Zestaw znaków ASCII (skrót od ang. American Standard Code for Information Inter- change — Amerykański Kod Standardowy Wymiany Informacji) odwzorowuje 128 znaków na liczby całkowite bez znaku od 0 do 127 ($0..$7F). Wprawdzie dokładny 102 Profesjonalne programowanie. Część 1. Zrozumieć komputer sposób tego odwzorowania jest w gruncie rzeczy dość przypadkowy i niezbyt istotny, ale istnienie takiego standardu pozwala na komunikowanie się rożnych programów i urządzeń peryferyjnych. Standardowe kody ASCII są przydatne, ponieważ niemal wszyscy ich używają. Wobec tego, jeśli użyjemy kodu ASCII 65 do zapisania znaku A, to dowolne urządzenie peryferyjne — na przykład drukarka — prawidłowo zinterpretuje tę wartość jako literę A. Zestaw znaków ASCII zapewnia tylko 128 różnych znaków, więc pojawia się ważne pytanie — co z pozostałymi 128 wartościami ($80..$FF), które można zapisać na jednym bajcie? Odpowiedź brzmi: pomijamy te znaki. I tak właśnie będziemy postępować w niniejszej książce. Inna możliwość to rozszerzenie zestawu ASCII o tych 128 znaków. O ile jednak wszyscy nie będą zgodni co do dokładnego sposobu tego rozszerzenia1, podważony zostanie sens używania standardowego zestawu znaków. A doprowadzenie do zgody wszystkich to niełatwe zadanie2. Mimo poważnych niedostatków, zestaw znaków ASCII jest standardem wymiany danych między programami i komputerami. Większość programów potrafi odczytać dane ASCII, a także je zapisywać. Jako że większość Czytelników zapewne w swoich programach używa znaków ASCII, dobrze byłoby przeanalizować ich układ i zapamiętać kluczowe znaki, takie jak 0, A, a i im podobne. W tabeli A.1 dodatku A wymieniono wszystkie znaki z tego zestawu. Znaki ASCII dzieli się na cztery grupy zawierające po 32 znaki. Pierwsze 32 znaki o kodach od $0 do $1F (od 0 do 31) to specjalny zbiór znaków niedrukowalnych nazy- wanych znakami kontrolnymi. Nazwa ta wzięła się stąd, że realizują one różne funkcje sterujące drukarką i monitorem, a nie są pokazywane jako takie. Przykładami znaków kontrolnych mogą być: powrót karetki, powodujący umieszczenie kursora na początku bieżącego wiersza3; nowy wiersz, przenoszący kursor wiersz niżej; backspace, który przesuwa kursor o jeden znak w lewo. Niestety, niektóre znaki kontrolne powodują różne działania różnych urządzeń wyjściowych. Standaryzacja w tym zakresie jest bardzo niewielka. Aby mieć pewność, że wiemy, co dany znak kontrolny wykonuje w używanym urządzeniu, trzeba sprawdzić to w dokumentacji. Druga grupa 32 znaków ASCII to różne symbole przestankowe, znaki specjalne i cyfry. Najważniejsze znaki z tej grupy to spacja (kod ASCII $20) oraz cyfry (kody $30..$39). 1 Zanim spopularyzował się system Windows, produkty IBM obsługiwały na wyświetlaczach tekstowych 256-elementowy zestaw znaków. Chociaż zestaw ten funkcjonuje obecnie nawet we współczesnych komputerach PC, niewiele aplikacji czy urządzeń peryferyjnych nadal obsługuje te rozszerzone znaki. 2 Powody do niegodzenia się na stosowanie wspomnianego przez Autora zestawu znaków mamy chociażby my, Polacy. Otóż zestaw ten, znany jako ISO-Latin1 lub ISO-8859-1, nie zawiera polskich liter, takich jak ą czy ć, i jest dostosowany do języków zachodnioeuropejskich. Istnieją alternatywne zestawy znaków dodatkowych, zawierające inne znaki; wszystkie one mają takie same 128 pierwszych znaków — ASCII. Przykładowo, zestaw ISO-Latin2 (inaczej ISO-8859-2) zawiera m.in. nasze znaki narodowe — przyp. tłum. 3 Nazwa tego znaku pochodzi z czasów, kiedy chodziło o przesunięcie karetki maszyny do pisania. Powrót karetki polegał na fizycznym przesunięciu tej karetki tak, aby następny znak pojawił się przy lewym brzegu papieru. Rozdział 5. ♦ Dane znakowe 103 Trzecia grupa 32 znaków zawiera wielkie litery. Kody liter od A do Z mieszczą się w zakresie $41..$5A. W alfabecie łacińskim jest tylko 26 liter, więc pozostałych 6 znaków zawiera różne symbole specjalne. Ostatnia grupa 32 znaków zawiera małe litery, pięć dodatkowych znaków specjalnych i jeszcze jeden znak kontrolny, delete (usuwający znak spod kursora). Zwróćmy uwagę na to, że małe litery wykorzystują kody ASCII $61..$7A. Jeśli zamieniamy małe litery na wielkie lub odwrotnie, różnica między małą a odpowiadającą jej wielką literą to tylko jeden bit. Na rysunku 5.1 pokazano przy- kładowo kody liter E i e. Rysunek 5.1. Kody ASCII liter E i e Oba znaki różnią się tylko piątym bitem. Wielkie litery mają piąty bit równy zero, małe — równy jeden. Można skorzystać z tego, aby szybko zamieniać małe litery na wielkie i odwrotnie; wystarczy przełączyć tylko jeden bit. Bity piąty i szósty decydują o przynależności znaku do grupy (tabela 5.1). Wobec tego małe litery na wielkie (lub na znaki specjalne) można zamieniać, ustawiając bity piąty i szósty na zero. Tabela 5.1. Grupy znaków ASCII wyznaczone przez piąty i szósty bit Bit 6. 0 0 1 1 Bit 5. 0 1 0 1 Grupa znaków znaki kontrolne cyfry i znaki przestankowe wielkie litery i znaki specjalne małe litery i znaki specjalne Przyjrzyjmy się przez chwilę kodom ASCII cyfr, pokazanym w tabeli 5.2. Dziesiętny zapis tych kodów niewiele nam mówi. Jednak zapis szesnastkowy ujawnia coś waż- nego — młodszy półbajt kodu ASCII to binarny odpowiednik zapisywanej liczby. Jeśli odrzucimy starszy półbajt kodu (ustawimy go na zero), otrzymamy binarny zapis odpowiedniej cyfry. Z drugiej strony, łatwo możemy zamienić liczbę binarną z zakre- su 0..9 na jej odpowiednik ASCII; wystarczy ustawić starszy półbajt na 0011, czyli dziesiętne 3. Zauważmy, że możemy użyć logicznej operacji AND, aby wymusić wyzerowanie starszych bitów; tak samo za pomocą logicznego OR możemy wymusić ustawienie starszych bitów na 0011 (dziesiętnie 3). Więcej informacji o konwersji łańcuchów na liczby Czytelnik znajdzie w rozdziale 2. Mimo że ASCII jest standardem, kodowanie danych za jego pomocą nie gwarantuje nam pełnej przenośności między różnymi systemami. Chociaż literze A na jednej ma- szynie będzie odpowiadało A na innej, zakres standaryzacji znaków kontrolnych jest niewielki. Faktycznie spośród pierwszych 32 kodów kontrolnych ASCII uzupełnionych kodem delete z grupy ostatniej tylko cztery są powszechnie obsługiwane przez więk- szość urządzeń i programów. Są to: backspace (BS), tabulator, powrót karetki (CR) 104 Profesjonalne programowanie. Część 1. Zrozumieć komputer Tabela 5.2. Kody ASCII cyfr Znak 0 1 2 3 4 5 6 7 8 9 Dziesiętnie 48 49 50 51 52 53 54 55 56 57 Szesnastkowo $30 $31 $32 $33 $34 $35 $36 $37 $38 $39 i nowy wiersz (LF). Co gorsza, na różnych maszynach często te same kody kontrolne są różnie obsługiwane. Szczególnie nieprzyjemnym przypadkiem jest koniec wiersza. W systemach Windows, MS-DOS, CP/M i innych koniec wiersza oznacza się parą znaków CR-LF. Apple Macintosh i wiele innych systemów oznacza koniec wiersza pojedynczym znakiem CR. Z kolei Linux, BeOS i inne systemy z rodziny Unix ozna- czają go pojedynczym znakiem LF. Próba przekazania zwykłego pliku tekstowego między tymi systemami może być źró- dłem poważnej frustracji. Nawet jeśli używamy standardowych znaków ASCII, i tak musimy zawczasu skonwertować dane. Na szczęście konwersje te są proste na tyle, że wiele edytorów tekstu automatycznie obsługuje pliki z różnie kończącymi się wier- szami. Istnieje też wiele darmowych programów wykonujących stosowne konwersje. Nawet jeśli musimy sami oprogramować taką konwersję, jest ona prosta — kopiujemy wszystkie znaki poza końcem wiersza, który odpowiednio zmieniamy. 5.1.2. Zestaw znaków EBCDIC Wprawdzie nie ulega wątpliwości, że zestaw ASCII jest najpopularniejszym zestawem znaków, ale nie jest on jedyny. Na przykład IBM na wielu swoich komputerach main- frame i minikomputerach używa kodu EBCDIC. Kod ten pojawia się głównie na dużych komputerach, natomiast na osobistych spotyka się go bardzo rzadko, więc poświęcimy mu niewiele uwagi. EBCDIC to skrót od angielskiego Extended Binary Coded Decimal Interchange Code, czyli Rozszerzony kod wymiany danych dziesiętnych kodowanych binarnie. Czy istniał kiedyś taki kod nierozszerzony? Owszem, kiedyś w komputerach IBM i w maszynach do dziurkowania kart używano zestawu znaków znanego jako BCDIC. Zestaw ten był oparty na kartach dziurkowanych i na zapisie dziesiętnym (wiązało się to ze stosowa- niem zapisu dziesiętnego w starszych urządzeniach IBM-a). Rozdział 5. ♦ Dane znakowe 105 Pierwsze, co trzeba powiedzieć o EBCDIC — nie jest to pojedynczy zestaw znaków, ale cała rodzina takich zestawów. Zestawy znaków EBCDIC mają wspólną część (na przykład litery zwykle są kodowane tak samo), ale różne wersje EBCDIC (nazywane stronami kodowymi) różnie kodują znaki przestankowe i specjalne. Na pojedynczym bajcie liczba możliwych kodowań jest ograniczona, w różnych stronach kodowych te same kody są używane do zapisu różnych znaków. Jeśli zatem mamy plik ze znakami EBCDIC i mamy go zapisać jako ASCII, szybko okaże się, że to nie jest wcale proste zadanie. Zanim w ogóle zobaczymy zestaw znaków EBCDIC, musimy sobie zdać sprawę, że przodek EBCDIC, czyli BCDIC, istniał na długo przed pojawieniem się współczesnych komputerów. BCDIC powstał na potrzeby maszyn do dziurkowania i czytników kart. EBCDIC pomyślano jako proste rozszerzenie kodowania tak, aby umożliwić stosowanie w komputerach IBM rozszerzonego zestawu znaków. Jednak EBCDIC odziedziczył po BCDIC pewne nietypowe, dzisiaj już archaiczne cechy. Na przykład kodowanie liter alfabetu nie jest ciągłe. Jest to prawdopodobnie bezpo- średni efekt stosowania pierwotnie kodowania dziesiętnego (BCD). Początkowo litery zapewne były kodowane na kolejnych znakach. Jednak kiedy IBM rozszerzył zestaw znaków, użyto kombinacji binarnych niewystępujących w formacie BCD (wartości typu 1010.. 1111). Takie wartości binarne występują między dwiema dotąd sąsia- dującymi wartościami BCD, więc niektóre ciągi znaków (na przykład litery) nie są zapisywane w kodowaniu EBCDIC w sposób ciągły. Niestety, z uwagi na nietypowość zestawu znaków EBCDIC wiele powszechnie sto- sowanych algorytmów działających na zestawie ASCII w przypadku EBCDIC po prostu nie działa. W rozdziale tym nie będziemy zajmowali się kodowaniem EBCDIC bardziej, niż tylko wspominając o tym standardzie tu i ówdzie. Trzeba jednak pamię- tać, że wszystkie funkcje tego kodu mają swoje odpowiedniki w zestawie ASCII. Po szczegółowe informacje odsyłam Czytelnika do dokumentacji IBM. 5.1.3. Dwubajtowe zestawy znaków Z uwagi na ograniczenia kodowania 8-bitowego (co oznacza maksymalnie 128 znaków) oraz na konieczność zapisania większej liczby znaków, w części systemów używa się specjalnych kodów potrzebujących do zapisania jednego znaku dwóch bajtów. Takie dwubajtowe zestawy znaków nie używają 16 bitów do zapisu każdego znaku; w więk- szości przypadków używany jest jeden bajt, a tylko w niektórych — dwa bajty. Typowy dwubajtowy zestaw znaków wykorzystuje standardowy zestaw ASCII z dodat- kowymi znakami z zakresu $80..$FF. Niektóre wartości z tego zakresu to kody roz- szerzenia informujące, że pojawi się drugi bajt. Każdy bajt rozszerzenia pozwala za- pisać 256 dodatkowych znaków. Mając trzy wartości rozszerzające, można obsłużyć maksymalnie 1021 różnych znaków. Z każdego bajta rozszerzającego otrzymujemy 256 znaków, poza tym mamy 253 (256–3) znaków w standardzie jednobajtowym (minus trzy, gdyż tyle znaków służy jako znacznik rozszerzający, który w związku z tym nie powinien być liczony jako zwykły znak). 106 Profesjonalne programowanie. Część 1. Zrozumieć komputer Dawniej, kiedy terminale i komputery wykorzystywały odwzorowanie w pamięci, dwu- bajtowe zestawy znaków były mało przydatne. W przypadku generatorów znaków wbudowanych w urządzenie każdy znak musiał mieć taką samą długość, ograniczano też liczbę obsługiwanych znaków. Jednak kiedy zaczęły dominować matrycowe wyświe- tlacze z programowymi generatorami znaków (Windows, Macintosh, Unix/XWindows), używanie dwubajtowych zestawów znaków stało się wygodne. Wprawdzie zestawy dwubajtowe pozwalają zapisywać w zwartej formie wiele różnych znaków, ale przetwarzanie tekstu w takim formacie wymaga sporo mocy obliczeniowej. Jeśli na przykład mamy zakończone zerami łańcuchy znaków dwubajtowych (kon- strukcja typowa w C i C++), określenie liczby znaków w łańcuchu może być nie lada wyzwaniem. Chodzi o to, że niektóre znaki potrzebują dwóch bajtów, a niektóre tylko jednego. Funkcja określająca długość łańcucha musi przeglądać znak po znaku, aby znaleźć znaki rozszerzające i odkryć w ten sposób miejsca, w których są znaki dwu- bajtowe. To podwójne porównanie podwaja czas określania długości łańcucha. Co gorsza, wiele algorytmów powszechnie stosowanych do obsługi danych łańcuchowych zawodzi w przypadku dwubajtowych zestawów znaków. Na przykład typowy sposób prze- mieszczania się w języku C po łańcuchu to zwiększanie lub zmniejszanie o jeden wskaźnika, na przykład ++ptrChar lub --ptrChar. Wszystkie te mechanizmy nie za- działają w przypadku kodowania dwubajtowego. Osoby korzystające z takich kodowań zwykle posiadają gotowe już funkcje biblioteczne, ale wiele innych funkcji napisanych przez nie lub przez kogoś innego nie zadziała. Z tego i innych powodów, jeśli potrzebne jest nam kodowanie większej niż 124 liczby znaków, powinniśmy nastawić się na korzystanie ze standardu Unicode, który zaraz zostanie opisany. 5.1.4. Zestaw znaków Unicode Jakiś czas temu inżynierowie Apple Computer i Xeroksa stwierdzili, że ich nowe systemy z wyświetlaczami mozaikowymi i czcionkami wybieranymi przez użytkownika mogą wyświetlić o wiele więcej niż 256 znaków naraz. Choć można było zastosować kodowania dwubajtowe, stwierdzono, że występują poważne problemy związane z faktem, że znaki mają po dwa bajty, i poszukiwano innego rozwiązania. Okazał się nim zestaw znaków Unicode. Standard ten przyjął się na całym świecie i jest obsługiwany przez niemalże każdy system komputerowy i system operacyjny (Mac OS, Windows, Linux, Unix i wiele innych). W Unicode do zapisu każdego znaku używa się 16-bitowych słów, więc można zapisać do 65 536 różnych znaków. Jest to oczywiście o wiele, wiele więcej niż dotychczasowe 256 możliwych znaków w 8-bitowym bajcie. Mało tego, Unicode jest zgodny z ASCII. Jeśli najstarszych 9 bitów4 jest ustawionych na zero, młodszych 7 to kod ze standar- dowego zestawu ASCII. Jeśli 9 starszych bitów zawiera wartości niezerowe, całe 16 bitów tworzy znak rozszerzony (rozszerzony względem ASCII). Jeśli ktoś się jeszcze zastanawia, po co właściwie mamy aż tyle kodów znaków, wystarczy przypomnieć, że niektóre azjatyckie zestawy zawierają ich 4096 (tyle znaków mają ich podzbiory 4 ASCII to kod 7-bitowy. Jeśli najstarszych 9 bitów 16-bitowej wartości Unicode jest zerami, pozostałych 7 bitów to kod ASCII danego znaku. Rozdział 5. ♦ Dane znakowe 107 w Unicode). Zestaw znaków Unicode zawiera nawet kody, które mogą być używane jako znaki definiowane na potrzeby poszczególnych aplikacji. W chwili pisania tej książki zdefiniowano około połowę z 65 536 dostępnych znaków; pozostałe są zare- zerwowane na rozszerzenia w przyszłości. Obecnie wiele systemów operacyjnych i bibliotek do różnych języków programowania zawiera doskonałą obsługę Unicode. Na przykład system Microsoft Windows używa standardu Unicode wewnętrznie5, co powoduje, że funkcje systemowe działają szybciej, jeśli przekaże im się łańcuchy Unicode, niż w przypadku przekazania łańcuchów ASCII (kiedy przekazujemy do nowszych wersji Windows łańcuch ASCII, system najpierw zamienia go z ASCII na Unicode i dopiero wtedy używa API funkcji systemowej). Analogicznie, kiedy Windows zwraca aplikacji łańcuch, jest to łańcuch Unicode; jeśli oczekuje ona łańcucha ASCII, Windows musi dodatkowo przeprowadzić stosowną konwersję. Jednak Unicode ma też dwie poważne wady. Po pierwsze, dane znakowe zajmują dwa razy więcej miejsca niż w przypadku ASCII lub innych kodowań jednobajtowych. Chociaż obecnie komputery mają znacznie więcej pamięci niż kiedyś (dotyczy to tak pamięci RAM, jak i pamięci dyskowych), podwojenie rozmiaru plików tekstowych, baz danych i łańcuchów umieszczanych w pamięci (jak łańcuchy przetwarzane przez edytory i procesory tekstu) może znacząco wpłynąć na wydajność systemu. Co gorsza, skoro łańcuchy są obecnie dwukrotnie dłuższe, przetwarzanie łańcucha Unicode wymaga prawie dwukrotnie więcej instrukcji niż przetwarzanie łańcucha, w którym znaki są zapisywane na pojedynczych bajtach. Wobec tego funkcje obsługi łańcuchów mogą działać dwukrotnie wolniej niż funkcje przetwarzające dane jednobajtowe6. Druga wada Unicode jest taka, że większość istniejących gdziekolwiek na świecie plików z danymi jest zapisana jako ASCII lub EBCDIC, więc w przypadku korzystania w aplikacji z Unicode pewną ilość czasu trzeba poświęcić na konwersję między Unicode a innymi zestawami znaków. Choć Unicode jest standardem powszechnie akceptowanym, nadal nie wydaje się, żeby był w powszechnym użyciu (choć stale zyskuje na popularności). Można się spodziewać, że już wkrótce przekroczy on „masę krytyczną” i stanie się wszechobecny. Jednak jest to nadal kwestia przyszłości, więc w większości przykładów w naszej książce nadal ograniczać się będziemy do znaków ASCII. Ale już niedługo zapewne w książce takiej jak ta trzeba będzie się skupić raczej na Unicode. 5 Windows CE używa wyłącznie Unicode. Do funkcji tego systemu w ogóle nie ma możliwości przekazania łańcuchów ASCII. 6 Można by twierdzić, że przetwarzanie łańcuchów Unicode za pomocą instrukcji przetwarzających słowa nie powinno trwać dłużej niż przetwarzanie bajtów za pomocą instrukcji przetwarzających bajty. Jednak zoptymalizowane funkcje przetwarzające łańcuchy przetwarzają zwykle podwójne słowa, a nawet większe jednostki danych. Takie funkcje mogą przetworzyć jednorazowo dwukrotnie mniej znaków Unicode niż znaków jednobajtowych, stąd do wykonania tej samej pracy trzeba dwukrotnie więcej instrukcji maszynowych. 108 Profesjonalne programowanie. Część 1. Zrozumieć komputer 5.2. Łańcuchy znakowe Łańcuchy znakowe są prawdopodobnie drugim najbardziej powszechnie stosowanym typem danych, zaraz za liczbami całkowitymi. Łańcuch znakowy to ciąg znaków mający dwa atrybuty: długość i dane znakowe. Łańcuchy znakowe mają też inne atrybuty, na przykład długość maksymalną, jaką można zapisać w danej zmiennej, czy liczbę od- wołań informującą, ile różnych zmiennych łańcuchowych odwołuje się do tego samego łańcucha. Wkrótce zajmiemy się tymi atrybutami i użyciem ich w programach, gdzie opiszemy różne formaty łańcuchowe oraz opowiemy o możliwych działaniach na łańcuchach. 5.2.1. Formaty łańcuchów znakowych Różne języki różnie zapisują łańcuchy. Niektóre formaty łańcuchów wymagają mniej pamięci, inne pozwalają na szybsze przetwarzanie, jeszcze inne są wygodniejsze w uży- ciu, następne oferują dodatkowe funkcje programiście i systemowi operacyjnemu. Aby lepiej zrozumieć zasady rządzące łańcuchami znakowymi, dobrze jest przyjrzeć się pewnym typowym sposobom ich zapisu, występującym w różnych językach progra- mowania wysokiego poziomu. 5.2.1.1. Łańcuchy zakończone zerem Niewątpliwie łańcuchy zakończone zerem są najpopularniejszą obecnie wykorzysty- waną formą zapisu. Jest to format natywny dla języków C, C++, Java i innych. Poza tym łańcuchy zakończone zerem spotyka się w programach pisanych w językach, które nie mają własnego formatu natywnego łańcuchów, takich jak asemblery. Zakończony zerem łańcuch ASCII to ciąg zawierający zero lub więcej 8-bitowych znaków, kończący się bajtem zerowym (a w przypadku Unicode — ciąg mający zero lub więcej 16-bitowycyh kodów znaków zakończonych 16-bitowym zerowym słowem). Na przykład w C i C++ łańcuch ASCII „abc” wymaga czterech bajtów: po jednym na każdą z liter: a, b i c oraz jednego bajta zerowego. Łańcuchy zakończone zerem mają pewne zalety, których pozbawione są inne formaty: (cid:141) Mogą zawierać praktycznie dowolnie długie ciągi znakowe, z narzutem zaledwie jednego bajta (lub dwóch bajtów w przypadku Unicode). (cid:141) Z uwagi na popularność języków C i C++ dostępne są bardzo dobrze zoptymalizowane biblioteki do ich obsługi. (cid:141) Są łatwe w implementacji. Faktycznie poza przypadkiem stałych literałów łańcuchowych języki C i C++ w ogóle nie zawierają obsługi takich łańcuchów. W tych językach są one po prostu tablicami znakowymi. Dlatego chyba projektanci C wybrali taki właśnie format — nie musieli troszczyć się o wzbogacanie języka o operatory łańcuchowe. (cid:141) Omawiany format pozwala zapisywać łańcuchy zakończone zerem w dowolnym języku umożliwiającym tworzenie tablic znaków. Rozdział 5. ♦ Dane znakowe 109 Jednak łańcuchy zakończone zerem mają też wady, wobec czego nie zawsze są opty- malną strukturą dla danych łańcuchowych. Wady ich używania są następujące: (cid:141) Funkcje do obsługi łańcuchów często działają bardzo niewydajnie w ich przypadku. Wiele operacji łańcuchowych musi znać długość łańcucha przed rozpoczęciem jego przetwarzania. Jedynym sposobem obliczenia długości łańcucha zakończonego zerem jest przejrzenie go od początku do końca. Im jest on dłuższy, tym wolniej działać będzie funkcja. Wobec tego łańcuchy zakończone zerem nie są najlepszym rozwiązaniem w przypadku przetwarzania długich łańcuchów. (cid:141) W ich przypadku trudno jest zapisać znak, którego kod jest zerem — na przykład znak ASCII NUL. Zwykle nie jest to jednak istotne. (cid:141) W takim łańcuchu nie ma nigdzie umieszczonej informacji, jak bardzo może on zostać wydłużony. Wobec tego w przypadku części funkcji do obsługi łańcuchów (takich jak konkatenacja) można dojść tylko do obecnego końca zmiennej lub ewentualnie sprawdzić przepełnienie, jeśli jawnie zostanie przekazana maksymalna dopuszczalna długość. 5.2.1.2. Łańcuchy poprzedzone długością Drugi format łańcuchów znakowych, łańcuchy poprzedzone długością, pozwala uniknąć części problemów charakterystycznych dla łańcuchów zakończonych zerem. Łańcuchy poprzedzone długością są charakterystyczne dla języków takich jak Pascal; składają się zwykle z pojedynczego bajta określającego długość łańcucha, po którym następuje zero lub więcej 8-bitowych znaków. W tym wypadku napis „abc” składałby się z czterech bajtów: długości łańcucha ($03), a następnie znaków a, b i c. Dzięki łańcuchom poprzedzonym długością można uniknąć dwóch problemów, na jakie natknęliśmy się przy poprzednim formacie ich zapisu. Po pierwsze, bez problemu można zapisywać znak NUL. Po drugie, szybciej działają operacje łańcuchowe. Inna ich zaleta jest taka, że jeśli spojrzeć na taki łańcuch jak na tablicę znakową, długość zwykle znaj- duje się na pozycji zerowej, więc indeksy samego łańcucha zaczynają się od jedynki. W przypadku wielu funkcji łańcuchowych indeksowanie znaków od jedynki jest znacznie wygodniejsze niż indeksowanie od zera (jak dzieje się w łańcuchach zakończonych zerem). Łańcuchy poprzedzone długością mają też wady, z których najważniejszą jest narzu- cone ograniczenie długości do 255 znaków (o ile długość jest zapisywana w jednym bajcie). Można ominąć to ograniczenie, zapisując długość na 2 lub 4 bajtach, ale wtedy zwiększa się narzut na każdy łańcuch. 5.2.1.3. Łańcuchy siedmiobitowe Ciekawy format działający na kodach 7-bitowych, takich jak ASCII, zakłada użycie najstarszego bita do oznaczenia końca łańcucha. Wszystkie znaki poza ostatnim w łań- cuchu mają najstarszy bit wyzerowany (lub ustawiony, kwestia gustu), a ostatni znak ma ten bit ustawiony (lub odwrotnie, wyzerowany). 110 Profesjonalne programowanie. Część 1. Zrozumieć komputer Oto wady łańcuchów siedmiobitowych: (cid:141) Aby określić ich długość, trzeba je w całości przejrzeć. (cid:141) W tym formacie nie można zapisać łańcucha o zerowej długości. (cid:141) Niewiele języków programowania pozwala zapisywać stałe literały jako łańcuchy 7-bitowe. (cid:141) Ograniczeni jesteśmy do 128 kodów znaków, choć w przypadku korzystania ze zwykłego ASCII nie stanowi to problemu. Jednak ogromną zaletą łańcuchów 7-bitowych jest to, że nie wymagają żadnego narzutu na kodowanie długości. Do ich obsługi najlepszym wyborem jest asembler (przy czym definiuje się makro do tworzenia stałych literałów takich łańcuchów). Wynika to ze zwartości zapisu tych łańcuchów, co docenią przede wszystkim właśnie programiści asemblerowi. Oto makro asemblera HLA, które konwertuje literał łańcuchowy na łańcuch 7-bitowy: #macro sbs( s ); // Pobranie wszystkich znaków łańcucha poza ostatnim: (@substr( s, 0, @length(s) - 1) + // Złączenie ostatniego znaku z ustawionym najstarszym bitem: char( uns8( char( @substr( s, @length(s) - 1, 1))) | $80 )) #endmacro ... byte sbs( Hello World ); 5.2.1.4. Łańcuchy HLA Póki nie przeszkadza nam kilka dodatkowych bajtów narzutu, można stworzyć format łańcuchów łączących w sobie zalety łańcuchów poprzedzonych długością i zakończo- nych zerem, unikając jednocześnie wad jednych i drugich. Przykładem jest natywny format łańcuchów języka HLA7. Najpoważniejszą wadą łańcuchów w formacie HLA jest duży narzut na każdy łańcuch. Procentowo może on być szczególnie istotny w środowiskach o ograniczonych zaso- bach i w przypadku korzystania z wielu krótkich łańcuchów. Łańcuchy HLA zawierają zarówno długość przed łańcuchem właściwym, jak i kończący bajt zerowy, a także inne informacje; łącznie narzut wynosi dziewięć bajtów na łańcuch8. 7 Zwróćmy uwagę na to, że HLA jest asemblerem, więc można — i to bez trudu — obsłużyć w nim praktycznie dowolny rozsądny format łańcuchów. Natywny format łańcuchów HLA wykorzystywany jest w stałych literałach; jest on też używany przez większość procedur z biblioteki standardowej HLA. 8 Tak naprawdę, w związku z wymaganiami co do wyrównania danych w pamięci, narzut dla niektórych łańcuchów może sięgać 12 bajtów. Rozdział 5. ♦ Dane znakowe 111 Format HLA wykorzystuje 4-bajtowy przedrostek opisujący długość; dzięki temu długość ta może być nieco większa niż cztery miliardy znaków (jest to oczywiście o wiele więcej, niż w ogóle znajduje praktyczne zastosowanie). HLA wstawia też na koniec danych łańcuchowych bajt zerowy, dzięki czemu łańcuchy HLA są zgodne funkcjami obsługującymi łańcuchy zakończone zerem (pod warunkiem, że funkcje te nie zmieniają długości łańcuchów). Następne cztery dodatkowe bajty w łańcuchu HLA zawierają maksymalną dopuszczalną długość łańcucha. Dzięki temu dodatkowemu polu funkcje obsługujące w HLA łańcuchy mogą w razie potrzeby sprawdzić, czy nie wystąpiło przepełnienie. Na rysunku 5.2 pokazano postać łańcucha HLA w pamięci. Rysunek 5.2. Format łańcuchów HLA Cztery bajty znajdujące się tuż przed pierwszym znakiem łańcucha to faktyczna jego długość. Cztery poprzednie bajty to maksymalna długość łańcucha. Za znakami wcho- dzącymi w skład tekstu znajduje się bajt zerowy. HLA gwarantuje, że cała struktura danych łańcucha będzie wielokrotnością czterech bajtów (jest to korzystne z uwagi na wydajność), więc na końcu takiego obiektu może znajdować się do trzech bajtów wy- pełnienia (aby struktura z rysunku 5.2 miała długość będącą wielokrotnością czterech bajtów, wystarczą dwa bajty wypełnienia). Zmienne łańcuchowe HLA to wskaźniki zawierające adres bajta z pierwszym znakiem łańcucha. Aby sięgnąć do pól określających długość, trzeba załadować wartość wskaźnika do rejestru 32-bitowego. Do pola określającego długość sięgamy, podając offset równy –4, a do pola określającego długość maksymalną — offset równy –8. Oto przykład: static s :string := Hello World ; ... mov( s, esi ); // Do esi wstawiamy adres litery H // z napisu Hello World mov( [esi-4], ecx ); // Długość łańcucha wstawiamy do ECX (dla Hello // World jest to 11). ... mov( s, esi ); cmp( eax, [esi-8] ); // Sprawdzamy, czy długość z EAX przekracza // maksymalną długość łańcucha. ja StringOverflow; Miłą cechą zmiennych łańcuchowych HLA jest to, że (jako obiekty tylko do odczytu) są one kompatybilne z łańcuchami zakończonymi zerem. Na przykład, jeśli mamy funkcję języka C (lub innego) spodziewającą się jako parametru łańcucha zakończo- nego zerem, możemy wywołać ją, przekazując jej łańcuch HLA: jakasFunkcjaC( zmiennaLancuchowaHLA ); Jedynym problemem jest to, że funkcja ta nie może w żaden sposób zmieniać długo- ści łańcucha (gdyż kod C nie skorygowałby pola określającego długość). Oczywiście, przy powrocie zawsze można byłoby użyć funkcji C strlen, aby sprawdzić długość łańcucha i w razie potrzeby ją skorygować, ale modyfikowanie długości łańcuchów HLA z zewnątrz w zasadzie jest kiepskim pomysłem. 112 Profesjonalne programowanie. Część 1. Zrozumieć komputer 5.2.1.5. Łańcuchy z deskryptorem Rozważane przez nas dotąd formaty łańcuchów miały wszystkie atrybuty łańcucha (długości i bajty kończące) wraz z samym łańcuchem. Być może nieco elastyczniejszym rozwiązaniem jest trzymanie informacji o maksymalnej i bieżącej długości łańcucha w strukturze zawierającej też wskaźnik do danych znakowych. Takie struktury nazywamy deskryptorami. Oto przykładowa struktura danych języka Pascal (lub Delphi czy Kyliksa): type dString :record curLength :integer; strData :^char; end; Zauważmy, że struktura ta nie zawiera danych znakowych, ale ma wskaź
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Profesjonalne programowanie. Część 1. Zrozumieć komputer
Autor:

Opinie na temat publikacji:


Inne popularne pozycje z tej kategorii:


Czytaj również:


Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: