Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00504 010252 11030910 na godz. na dobę w sumie
Uczta programistów - książka
Uczta programistów - książka
Autor: Liczba stron: 336
Wydawca: Helion Język publikacji: polski
ISBN: 83-7361-220-3 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> techniki programowania
Porównaj ceny (książka, ebook, audiobook).

Praktyczne rozwiązania dla zaawansowanych programistów

Do tworzenia wydajnych programów nie wystarczy teoretyczna wiedza o algorytmach, strukturach danych i inżynierii oprogramowania. Istnieje pokaźna liczba sztuczek, sprytnych technik i praktycznych rozwiązań, których znajomość jest niezbędna każdemu programiście.

Niniejsza książka zawiera pokaźny zestaw technik, które pomogą zaoszczędzić sporo czasu. Techniki te zostały opracowane przez twórców kodu poszukujących eleganckich i wydajnych sposobów tworzenia lepszego oprogramowania. W 'Uczcie programistów' doświadczony programista Hank Warren dzieli się z Czytelnikami znanymi sobie sztuczkami, które zgromadził wraz z imponującym doświadczeniem w dziedzinie programowania aplikacji i systemów operacyjnych. Większość z tych sztuczek jest niezwykle praktyczna, niektóre zostały przedstawione jako ciekawostki lub zaskakujące rozwiązania. Ich zestawienie stanowi niesamowitą kolekcję, która będzie pomocna nawet dla najbardziej doświadczonych programistów w rozszerzeniu ich umiejętności.

W książce opisano następujące zagadnienia:

Niniejsza książka jest doskonałą pozycją dla wszystkich programistów, którzy mają zamiar tworzyć wydajny kod. 'Uczta programistów' nauczy Cię tworzenia aplikacji wysokiej jakości -- wyższej niż wymagana na uczelniach i kursach programowania.

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 Uczta programistów 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 Autorzy: Henry S. Warren, Jr. T³umaczenie: Marek Pêtlicki (rozdz. 1 – 9), Bart³omiej Garbacz (rozdz. 10 – 16, dod. A, B) ISBN: 83-7361-220-3 Tytu³ orygina³u: Hacker s Delight Format: B5, stron: 336 Do tworzenia wydajnych programów nie wystarczy teoretyczna wiedza o algorytmach, strukturach danych i in¿ynierii oprogramowania. Istnieje pokaĥna liczba sztuczek, sprytnych technik i praktycznych rozwi¹zañ, których znajomoġæ jest niezbêdna ka¿demu programiġcie. Niniejsza ksi¹¿ka zawiera pokaĥny zestaw technik, które pomog¹ zaoszczêdziæ sporo czasu. Techniki te zosta³y opracowane przez twórców kodu poszukuj¹cych eleganckich i wydajnych sposobów tworzenia lepszego oprogramowania. W „Uczcie programistów” doġwiadczony programista Hank Warren dzieli siê z Czytelnikami znanymi sobie sztuczkami, które zgromadzi³ wraz z imponuj¹cym doġwiadczeniem w dziedzinie programowania aplikacji i systemów operacyjnych. Wiêkszoġæ z tych sztuczek jest niezwykle praktyczna, niektóre zosta³y przedstawione jako ciekawostki lub zaskakuj¹ce rozwi¹zania. Ich zestawienie stanowi niesamowit¹ kolekcjê, która jest w bêdzie pomocna nawet dla najbardziej doġwiadczonych programistów w rozszerzeniu ich umiejêtnoġci. W ksi¹¿ce opisano nastêpuj¹ce zagadnienia: • Obszerna kolekcja u¿ytecznych sztuczek programistycznych • Drobne algorytmy rozwi¹zuj¹ce czêsto spotykane problemy • Algorytmy kontroli przekroczenia ograniczeñ • Zmiana kolejnoġci bitów i bajtów • Dzielenie ca³kowite i dzielenie przez sta³e • Elementarne operacje na liczbach ca³kowitych • Kod Gray a • Krzywa Hilberta • Formu³y wyznaczania liczb pierwszych Niniejsza ksi¹¿ka jest doskona³¹ pozycj¹ dla wszystkich programistów, którzy maj¹ zamiar tworzyæ wydajny kod. „Uczta programistów” nauczy Ciê tworzenia aplikacji wysokiej jakoġci — wy¿szej ni¿ wymagana a uczelniach i kursach programowania. Spis treści Przedmowa.............................................................................................................9 Wstęp ..................................................................................................................11 Rozdział 1. Wprowadzenie ..................................................................................13 1.1. Notacja ...................................................3...................................................3.................13 1.2. Zestaw instrukcji i model wykonawczy ...................................................3..................17 Rozdział 2. Podstawy .........................................................................................23 2.1. Manipulowanie prawostronnymi bitami ...................................................3.................23 2.2. Łączenie dodawania z operacjami logicznymi...................................................3........27 2.3. Nierówności w wyrażeniach logicznych i arytmetycznych .......................................29 2.4. Wartość bezwzględna...................................................3..............................................30 2.5. Rozszerzenie o znak ...................................................3................................................31 2.6. Przesunięcie w prawo ze znakiem za pomocą instrukcji przesunięcia bez znaku .....32 2.7. Funkcja signum ...................................................3...................................................3....32 2.8. Funkcja porównania trójwartościowego ...................................................3.................33 2.9. Przeniesienie znaku ...................................................3.................................................34 2.10. Dekodowanie pola „zero oznacza 2n” ...................................................3...................34 2.11. Predykaty porównań...................................................3..............................................35 2.12. Wykrywanie przepełnienia...................................................3....................................40 2.13. Kod warunkowy operacji dodawania, odejmowania i mnożenia.............................49 2.14. Przesunięcia cykliczne ...................................................3..........................................50 2.15. Dodawanie i odejmowanie liczb o podwójnej długości...........................................51 2.16. Przesunięcia liczb o podwójnej długości ...................................................3..............52 2.17. Operacje dodawania, odejmowania i wyznaczania wartości bezwzględnej na wartościach wielobajtowych ...................................................3...................................53 2.18. Doz, Max oraz Min ...................................................3...............................................54 2.19. Wymiana wartości między rejestrami ...................................................3...................56 2.20. Wymiana dwóch lub większej liczby wartości ...................................................3.....59 Rozdział 3. Ograniczenia potęg dwójki ..................................................................63 3.1. Zaokrąglanie do wielokrotności znanych potęg liczby 2 ...........................................63 3.2. Zaokrąglanie w górę lub w dół do następnej potęgi liczby 2.....................................64 3.3. Wykrywanie przekroczenia ograniczeń potęgi dwójki ..............................................67 Rozdział 4. Ograniczenia arytmetyczne................................................................71 4.1. Kontrola ograniczeń liczb całkowitych...................................................3...................71 4.2. Ograniczenia zakresów w operacjach sumy i różnicy ...............................................74 4.3. Ograniczenia zakresów w operacjach logicznych...................................................3...78 6 Uczta programistów Rozdział 5. Zliczanie bitów .................................................................................85 5.1. Zliczanie jedynek ...................................................3...................................................3.85 5.2. Parzystość...................................................3...................................................3.............94 5.3. Zliczanie zer wiodących...................................................3..........................................97 5.4. Zliczanie zer końcowych...................................................3.......................................104 Rozdział 6. Przeszukiwanie słów .......................................................................111 6.1 Wyszukiwanie pierwszego bajtu o wartości 0 ...................................................3.......111 6.2. Wyszukiwanie pierwszego ciągu jedynek o zadanej długości.................................117 Rozdział 7. Manipulacja bitami i bajtami ...........................................................121 7.1. Odwracanie kolejności bitów i bajtów ...................................................3..................121 7.2. Tasowanie bitów ...................................................3...................................................3126 7.3. Transponowanie macierzy bitów ...................................................3..........................128 7.4. Kompresja lub uogólniona ekstrakcja ...................................................3...................137 7.5. Uogólnione permutacje, operacja typu „owce i kozły”............................................143 7.6. Zmiana kolejności oraz transformacje oparte na indeksach.....................................148 Rozdział 8. Mnożenie........................................................................................151 8.1. Mnożenie czynników wieloelementowych ...................................................3...........151 8.2. Bardziej znacząca połowa 64-bitowego iloczynu ...................................................3.154 8.3. Konwersje między bardziej znaczącą połową 64-bitowego iloczynu ze znakiem i bez znaku ...................................................3...................................................3..............155 8.4. Mnożenie przez stałe...................................................3.............................................156 Rozdział 9. Dzielenie całkowitoliczbowe ............................................................161 9.1. Warunki wstępne...................................................3...................................................3161 9.2. Dzielenie wartości wieloelementowych...................................................3................165 9.3. Krótkie dzielenie bez znaku za pomocą dzielenia ze znakiem ................................170 9.4. Długie dzielenie bez znaku ...................................................3...................................173 Rozdział 10. Dzielenie liczb całkowitych przez stałe................................................181 10.1. Dzielenie ze znakiem przez znaną potęgę liczby 2 ................................................181 10.2. Reszta ze znakiem z dzielenia przez znaną potęgę liczby 2 ..................................182 10.3. Dzielenie i reszta ze znakiem w przypadku innych wartości niż potęgi liczby 2 ..184 10.4. Dzielenie ze znakiem przez dzielniki ≥ 2...................................................3............187 10.6. Zawieranie obsługi w kompilatorze ...................................................3....................197 10.7. Inne zagadnienia...................................................3..................................................201 10.8. Dzielenie bez znaku ...................................................3............................................205 10.9. Dzielenie bez znaku przez dzielniki ≥ 1...................................................3..............207 10.10. Zawieranie obsługi w kompilatorze ...................................................3..................210 10.11. Inne zagadnienia (dzielenia bez znaku) ...................................................3............212 10.12. Zastosowalność w przypadku dzielenia z modułem i dzielenia z funkcją podłoga .. 215 10.13. Podobne metody...................................................3................................................215 10.14. Przykładowe liczby magiczne...................................................3...........................216 10.15. Dzielenie dokładne przez stałe ...................................................3..........................217 10.16. Sprawdzanie zerowej reszty po wykonaniu dzielenia przez stałą........................225 Rozdział 11. Niektóre funkcje podstawowe .........................................................231 11.1. Całkowitoliczbowy pierwiastek kwadratowy ...................................................3.....231 11.2 Całkowitoliczbowy pierwiastek sześcienny...................................................3.........239 11.3. Całkowitoliczbowe podnoszenie do potęgi...................................................3.........241 11.4. Logarytm całkowitoliczbowy...................................................3..............................243 Spis treści 7 Rozdział 12. Niezwykłe podstawy systemów liczbowych .....................................251 12.1. Podstawa –2...............................................3...................................................3..........251 12.2. Podstawa –1 + i ...................................................3...................................................3258 12.3. Inne podstawy ...................................................3...................................................3..261 12.4. Najbardziej wydajna podstawa...................................................3............................262 Rozdział 13. Kod Graya ......................................................................................263 13.1. Kod Graya ...................................................3...................................................3........263 13.2. Zwiększanie wartości liczb całkowitych zakodowanych w kodzie Graya ............266 13.3. Ujemno-binarny kod Graya...................................................3.................................267 13.4. Rys historyczny i zastosowania...................................................3...........................268 Rozdział 14. Krzywa Hilberta ..............................................................................269 14.1. Rekurencyjny algorytm generowania krzywej Hilberta.........................................271 14.2. Określanie współrzędnych na podstawie odległości wzdłuż krzywej Hilberta .....273 14.3. Określanie odległości na podstawie współrzędnych na krzywej Hilberta .............280 14.4. Zwiększanie wartości współrzędnych na krzywej Hilberta ...................................282 14.5. Nierekurencyjny algorytm generowania ...................................................3.............285 14.6. Inne krzywe wypełniające przestrzeń ...................................................3.................285 14.7. Zastosowania...................................................3...................................................3....286 Rozdział 15. Liczby zmiennopozycyjne .................................................................289 15.1. Standard IEEE ...................................................3...................................................3..289 15.2. Porównywanie liczb zmiennopozycyjnych za pomocą 3operacji całkowitoliczbowych ...................................................3.................................................292 15.3. Rozkład cyfr wiodących...................................................3......................................293 15.4. Tabela różnych wartości...................................................3......................................295 Rozdział 16. Wzory na liczby pierwsze.................................................................299 16.1. Wprowadzenie...................................................3...................................................3..299 16.2. Wzory Willansa...................................................3...................................................3301 16.3. Wzory Wormella ...................................................3.................................................305 16.4. Wzory na inne trudne funkcje ...................................................3.............................306 Dodatek A Tablice arytmetyczne dla maszyny 4-bitowej ...................................313 Dodatek B Metoda Newtona ............................................................................319 Bibliografia.........................................................................................................321 Skorowidz...........................................................................................................325 Rozdział 7. Manipulacja bitami i bajtami 7.1. Odwracanie kolejności bitów i bajtów Przez operacje odwrócenia kolejności bitów (ang. reversing bits) rozumiemy wykonanie „odbicia lustrzanego”, na przykład: rev(0x01234567) = 0xE6A2C480 Przez operację odwrócenia bajtów rozumiemy podobne odbicie, z tym, że w tym przy- padku odwracamy kolejność bajtów w słowie. Odwracanie kolejności bajtów jest opera- cją konieczną w przypadku konwersji pomiędzy formatami little-endian, stosowanymi w procesorach DEC oraz Intel a formatem big-endian, stosowanym przez większość po- zostałych producentów procesorów. Odwrócenie kolejności bitów może zostać wykonane w stosunkowo wydajny sposób przez zamianę kolejności sąsiadujących bitów, następnie zamianę kolejności w sąsiadu- jących parach pól 2-bitowych itd. [Aus1]. Poniżej przedstawjiamy przykład realizacji tego mechanizmu. Wszystkie operacje przypisania można wykojnać w dowolnej kolejności. Z ZZ ^ ZZ########   Z ZZ ^ ZZ   Z ZZ(((( ^ ZZ((((   Z ZZ(((( ^ ZZ((((   Z ZZ(((( ^ ZZ((((   Na większości maszyn jest możliwe dokonanie niewielkiego usprawnienia, polegające- go na wykorzystaniu mniejszej liczby różnych stałych oraz na wykonaniu ostatnich dwóch przypisań w bardziej bezpośredni sposób, tak jak zostało przedstawione na listingu 7.1 (30 instrukcji z podstawowego zestawu RISC, bez rozgałęzjień). 122 Uczta programistów Listing 7.1. Odwracanie kolejności bitów WPUKIPGFTGX WPUKIPGFZ ] Z ZZ ^ Z  Z Z ZZ ^ Z  Z Z ZZ(((( ^ Z  Z(((( Z Z ^ ZZ((  ^  Z  Z(( ^ Z   TGVWTPZ _ Ostatnie przypisanie zmiennej x w tym kodzie realizuje odwrócenie bajtów w dziewię- ciu instrukcjach zestawu podstawowego RISC. W przypadku, gdy maszyna udostęp- nia instrukcje przesunięć cyklicznych, można tego dokonać w siedmiu instrukcjach, wykorzystując następującą formułę: x = (( x ) 0x00FF00FF ((|)8 x )8 ) 0x00FF00FF . rot rot Na procesorach PowerPC operację odwrócenia bajtów można wykonać w zaledwie trzech instrukcjach [Hay1]: przesunięcie cykliczne w lewo o 8, które umieszcza dwa bajty na odpowiednich miejscach, po którym wykonuje się dwa wywołania instrukcji TNYKOK (ang. rotate left word immediate then mask insert — przesunięcie cykliczne w lewo a na- stępnie podstawienie wartości z zastosowaniem maski). Uogólnienie operacji odwrócenia bitów W publikacji [GLS1] zasugerowano następujący sposób uogólnienia operacji odwróce- nia bitów. Sposób ten nazwano HNKR. Bardzo dobrze nadaje się on do zastosowania jako nowa instrukcja w zestawie instrukcji procesora: KH M Z ZZ ^ ZZ########   KH M Z ZZ ^ ZZ    KH M Z ZZ(((( ^ ZZ((((   KH M Z ZZ(((( ^ ZZ((((   KH M Z ZZ(((( ^ ZZ((((   Można pominąć ostatnie dwa wywołania instrukcji and. Dla k = 31 operacja ta dokonuje odwrócenia bitów w słowie. Dla k = 24 odwraca bajty w słowie. Dla k = 7 odwraca bity w każdym bajcie bez dokonywania zmian położenia bajtów. Dla k = 16 dokonuje zamiany półsłów w słowie itd. Ogólnie mówiąc, operacja ta przenosi bit z pozycji m na pozycję m ⊕ k. Instrukcja ta może zostać zaimplementowana w sprzęcie w podobny sposób, w jaki z reguły są implementowane instrukcje przesunięcia cyklicznego (pięć segmentów MUX, z których każdy jest kontrolowany za pomocą jednego bitu roz- miaru przesunięcia k). Wariacje na temat odwracania bitów Pozycja 167 w [HAK] przedstawia dość nietypowe wyrażenia wyjkonujące odwracanie 6, 7 i 8-bitowych liczb całkowitych. Wyrażenia te są zaprojektowane dla 36-bitowych Rozdział 7. ♦ Manipulacja bitami i bajtami 123 maszyn, lecz wersja dla wartości 6-bitowych działa również na maszynie 32-bitowej, natomiast wersje dla liczb 7 i 8-bitowych działają na jmaszynach 64-bitowych. 6 bitów: remu((x ∗ 0x00082082) 0x01122408, 255) 7 bitów: remu((x ∗ 0x40100401) 0x442211008, 255) 8 bitów: remu((x ∗ 0x202020202) 0x10884422010, 1023) W wyniku powyższych wyrażeń powstaje „czysta” liczba całkowita — wyrównana do prawej, bez zostawiania żadnego niepotrzebnego bardjziej znaczącego bitu. W każdej z tych sytuacji funkcja TGOW może zostać zastąpiona funkcją TGO lub OQF, ponieważ jej argumenty są liczbami dodatnimi. Funkcja TGO (ang. reminder — reszta z dzielenia) po prostu sumuje cyfry liczby o podstawie 256 lub 1024, co działa zupeł- nie tak samo, jak w przypadku metody odrzucania dzijewiątek (ang. casting out nines). Dzięki temu można ją zastąpić za pomocą kombinacji mnożenia i przesunięć w prawo. Na przykład 6-bitowa formuła posiada na maszynie 32-bitowej następującą postać al- ternatywną (mnożenie musi być wykonywane modulo 232): t ← (x ∗ 0x00082082) 0x01122408 ( t ) ∗ 0x01010101 24 u Przedstawione formuły mają dość ograniczone zastosowanie z powodu wykorzystania operacji reszty z dzielenia (20 cykli lub więcej) oraz kilku dodatkowych mnożeń i ope- racji ładowania dużych wartości bezpośrednich. Ostatnia z powyższych formuł wykorzy- stuje dziesięć instrukcji z podstawowego zestawu RISC, z których dwie są instrukcjami mnożenia, co na współczesnych procesorach klasy RISC daje w sumie około 20 cykli. Z drugiej strony wykorzystanie kodu z listingu 7.1 w celu odwracania liczb 6-bitowych wymaga zastosowania około 15 instrukcji oraz około 9 do 15 cykli, w zależności od moż- liwości procesora w zakresie równoległego wykonania niezależnych instrukcji. Techni- ki te można jednak zaimplementować za pomocą prostego i zwartego kodu. Poniżej pre- zentujemy techniki, które mogą być przydatne w maszynach 32-bitowych. Wykorzystują one coś na kształt podwójnego zastosowania pomysłu z [HAK], co posłużyło do rozwi- nięcia tej techniki do liczb 8 i 9-bitowych na maszynach 32-bitowych. Poniższa formuła służy do odwracania bitów w 8-bitowej jliczbie całkowitej: s ← (x ∗ 0x02020202) 0x84422010 t ← (x ∗ 8) 0x00000420 remu(s + t, 1023) W tym przypadku funkcji TGOW nie można zastąpić kombinacją mnożenia i przesunię- cia. Wyjaśnienie przyczyny pozostawiamy Czytelnikowi. Dla ułatwienia proponujemy przyjrzeć się układowi bitów w stałych, wykorzystywanyjch przez formułę. 124 Uczta programistów Oto podobna formuła służąca do odwracania bitów w 8-bitowych liczbach całkowitych. Jest ona ciekawa dlatego, że możemy ją dodatkowo niecjo uprościć: s ← (x ∗ 0x00020202) 0x01044010 t ← (x ∗ 0x00080808) 0x02088020 remu(s + t, 4095) Uproszczenia polegają na tym, że drugi iloczyn jest po prostu przesunięciem w lewo pierwszego iloczynu, natomiast ostatnią z zastosowanych stałych można wyliczyć z dru- giej za pomocą pojedynczej instrukcji przesunięcia a operację wyliczania reszty z dzie- lenia można w tym przypadku zastąpić kombinacją mnożenia i przesunięcia. Dzięki te- mu formułą ta upraszcza się do 14 instrukcji z podstawowego zestawu instrukcji RISC, z których dwie to instrukcje mnożenia: u ← x ∗ 0x00020202 m ← 0x01044010 s ← u m t ← (u 2) (m 1) (0x01001001 ∗ (s + t)) 24 u Formuła służąca do odwracania bitów w liczbach 9-bitowycjh jest następująca: s ← (x ∗ 0x01001001) 0x84108010 t ← (x ∗ 0x00040040) 0x00841080 remu(s + t, 1023) Drugie z mnożeń można wyeliminować, ponieważ jego iloczyn jest równy pierwszemu iloczynowi przesuniętemu o sześć miejsc w prawo. Ostatnia stała jest równa drugiej prze- suniętej w prawo o osiem pozycji. Wykorzystując te uproszczenia można tę formułę sprowadzić do postaci wykorzystującej 12 instrukcji z podstawowego zestawu RISC, w tym dwa mnożenia i jedną resztę z dzielenia. Operacja wyznaczania reszty musi być bez znaku i nie można jej zastąpić kombinacją mnożenia i przesunięcia. Czytelnik może samodzielnie skonstruować podobny kod dla innych operacji mani- pulujących bitami. W charakterze prostego (i sztucznego) przykładu posłużymy się ope- racją wydobycia co drugiego bitu z 8-bitowej wartości a następnie kompresji czterech wydobytych bitów z wyrównaniem do prawej. To znaczy mamy zamiar wykonać nastę- pującą operację: CDEFGHIJ DFHJ Operację tę można zaimplementować w następujący sposób: t ← (x ∗ 0x01010101) 0x40100401 (t ∗ 0x08040201) 27 u Rozdział 7. ♦ Manipulacja bitami i bajtami 125 Na większości maszyn najpraktyczniejszy sposób realizacji tego zadania polega na utwo- rzeniu tablicy przeglądowej wszystkich wartości (na przykład jednobajtowych lub 9-bi- towych). Zwiększanie wartości odwróconej liczby całkowitej Algorytm szybkiego przekształcenia Fouriera (ang. Fast Fourier Transform — FFT) wymaga zastosowania liczby całkowitej i oraz jej odwróconej wersji rev(i) w pętli, w któ- rej wartość i jest za każdym razem zwiększana o 1 [PB]. W najprostszym rozwiązaniu w każdej iteracji wyliczalibyśmy nową wartość liczby i a następnie wyliczalibyśmy rev(i). Dla niewielkich liczb całkowitych zastosowanie tablicy przeglądowej jest proste i prak- tyczne. Dla dużych wartości i technika taka nie jest praktyczna, a jak już wiemy wylicze- nie rev(i) wymaga 29 instrukcji. Jeśli jest wykluczone zastosowanie tablicy przeglądowej, bardziej wydajne byłoby osob- ne przechowywanie wartości i oraz rev(i), w każdej iteracji zwiększając obydwie te wartości. W tym momencie pojawia się problem zwiększenia liczby, której wartość po- siadamy w odwróconej formie. W celu ilustracji prezentujemy zastosowanie tej techniki na maszynie 4-bitowej w postaci kolejnych wartości w njotacji szesnastkowej:  #  $( W algorytmie FFT zarówno liczba, i jak jej odwrócona wersja stanowią określoną licz- bę bitów o określonej długości, która nigdy nie przekracza 32 i obydwie są wyrówna- ne do prawej w ramach rejestru. Załóżmy, że i jest 32-bitową liczbą całkowitą. Po zwięk- szeniu o 1 jej odwróconej wartości przesunięcie w prawo o odpowiednią liczbę bitów spowoduje, że liczba wynikowa stanie się właściwą wartością w algorytmie FFT (za- równo i, jak i rev(i) są wykorzystywane jako indeksy w tablicy). Najprostszym sposób zwiększenia wartości odwróconej liczby całkowitej jest wyszu- kanie lewostronnego zera, zmiana jego wartości na 1 a następnie ustawienie wszystkich bitów na lewo od tego miejsca na 0. Jeden ze sposobów realizacji tego algorytmu pre- zentuje następujący listing: WPUKIPGFZO OZ ZZ@O KH KPV Z  ] FQ] OO  ZZ@O _YJKNG ZO  _ W przypadku, gdy pierwszy bit od lewej ma wartość 0, powyższy kod wykonuje się w trzech instrukcjach z podstawowego zestawu RISC i w każdej iteracji są wykorzysty- wane cztery kolejne instrukcje. Wartość Z rozpoczyna się bitem 0 w połowie przypad- ków, sekwencją 10 w jeden czwartej przypadków i tak dalej, zatem średnia liczba in- strukcji wykorzystywanych przez ten algorytm wynosij w przybliżeniu: 126 Uczta programistów 3 1 1 +⋅+⋅ 2 4 7 11 1 +⋅ 8 15 ⋅ 1 16 + K 1 4 12 1 +⋅ 8 16 ⋅ 1 16 + K − 1 2 3 +++ 4 + K 4 8 16  −  1 1 +⋅+⋅= 8 4 2 1 2 =   4  = .7 W drugim wierszu powyższych obliczeń dodaliśmy i odjęliśmy 1, pierwsza z tych je- dynek została rozpisana jako 1/2 + 1/4 + 1/8 + 1/16 + …. Pod tym względem oblicze- nia te są podobne do przedstawionych na stronie 107). W najgorszym przypadku po- wyższy algorytm wymaga wykonania dość dużej liczby insjtrukcji, bo aż 131. W przypadku, gdy dostępna jest instrukcja wyliczająca liczbę zer wiodących, zwiększe- nie o 1 wartości odwróconej liczby całkowitej można zrjealizować w następujący sposób: Najpierw wyliczamy s ← nlz(¬x) następnie: x ← x ⊕ (0x80000000 s) s lub: x ← ((x s) + 0x80000000) s u Każdy ze sposobów wykorzystuje pięć instrukcji z pełnego zestawu RISC a dodatko- wo wymagane jest, aby przesunięcia były wykonywane modulo 64, w celu obsłużenia przypadku, gdy następuje zawinięcie wartości 0xFFFFFFFF do 0 (dlatego powyższe formuły nie będą działać na maszynach z rodziny Intel x86, ponieważ w tych proceso- rach przesunięcia są wykonywane modulo 32). 7.2. Tasowanie bitów Kolejnym ważnym sposobem manipulowania bitami jest operacja „tasowania zupełne- go” (ang. perfect shuffle), wykorzystywana w kryptografii. Istnieją dwie odmiany tej operacji, znane jako „wewnętrzna” (ang. inner) oraz „zewnętrzna” (ang. outer). Obydwie w wyniku dają ułożone naprzemiennie bity z dwóch połówek słowa w sposób przypo- minający dokładne potasowanie dwóch połówek talii złożonej z 32 kart. Różnica po- między tymi dwoma odmianami polega na tym, z której części talii pobieramy pierwszą kartę. W tasowaniu zewnętrznym zewnętrzne bity pozostają na pozycjach zewnętrznych, w odmianie wewnętrznej bit na pozycji 15 przesuwa się na lewą stronę wyniku (pozy- cję 31). Załóżmy, że nasze słowo składa się z bitów oznacjzonych w następujący sposób: CDEFGHIJKLMNOPQR#$  ()*+,-./012 W wyniku tasowania zewnętrznego uzyskamy następujące jsłowo: C#D$E F G H(I)J*K+L,M-N.O/P0Q1R2 Rozdział 7. ♦ Manipulacja bitami i bajtami 127 W wyniku tasowania wewnętrznego uzyskamy następujący jwynik: #C$D E F G(H)I*J+K,L-M.N/O0P1Q2R Załóżmy, że rozmiar słowa W jest potęgą liczby dwa. W tym przypadku operację ta- sowania zupełnego można wykonać za pomocą instrukcji podstawowego zestawu RISC w log2(W/2) kroków. Każdy z kroków składa się z zamiany kolejności drugiej i trzeciej ćwiartki coraz mniejszego fragmentu słowa. Ilustruje jto następujący przykład: CDEFGHIJKLMNOPQR#$  ()*+,-./012 CDEFGHIJ#$  ()*KLMNOPQR+,-./012 CDEF#$ GHIJ ()*KLMN+,-.OPQR/012 CD#$EF GH (IJ)*KL+,MN-.OP/0QR12 C#D$E F G H(I)J*K+L,M-N.O/P0Q1R2 Oto najprostszy sposób realizacji tego zadania: Z ZZ(( ^ Z  Z((^ZZ(((( Z ZZ(( ^ Z  Z((^ZZ(((( Z ZZ    ^ Z  Z    ^ZZ     Z ZZ ^ Z  Z^ZZ Powyższy sposób wymaga zastosowania 42 instrukcji z podstawowego zestawu in- strukcji RISC. Liczbę tę można zredukować do 30 lecz kosztem zwiększenia liczby instrukcji w przypadku procesorów o nieograniczonej liczbie jednocześnie wykonywa- nych, niezależnych instrukcji. W tym celu wykorzystujemy instrukcję różnicy symetrycz- nej w celu wymiany sąsiadujących pól w rejestrze (opisywanej na stronie 57). W poniż- szym kodzie wszystkie wartości są liczbami bez znaku: V Z@ Z  Z((ZZ@V@ V  V Z@ Z  Z((ZZ@V@ V  V Z@ Z  Z    ZZ@V@ V  V Z@ Z  ZZZ@V@ V  Operacja odwrotna, zewnętrzne odtasowanie (ang. outer unshuffle), może zostać zreali- zowana za pomocą odwrócenia kolejności operacji w powyższym kodzie: V Z@ Z  ZZZ@V@ V  V Z@ Z  Z    ZZ@V@ V  V Z@ Z  Z((ZZ@V@ V  V Z@ Z  Z((ZZ@V@ V  Wykorzystanie dwóch ostatnich kroków z dowolnego z powyższych algorytmów taso- wania spowoduje potasowanie każdego z bajtów osobno. Wykorzystanie ostatnich trzech kroków spowoduje potasowanie każdego z półsłów osobno itd. Podobne uwagi dotyczą operacji odtasowania, z tą różnicą, że kroki liczymy od początku. W celu uzyskania wewnętrznego tasowania zupełnego (ang. inner perfect shuffle) na początku każdego z powyższych sposobów należy dodać następujące wyrażenie, zamie- niające stronami połówki słowa: Z Z  ^ Z  128 Uczta programistów Można również zastosować przesunięcie cykliczne o 16 pozycji. Operację odtasowania można zrealizować za pomocą zakończenia procedury tymj samym wyrażeniem. Efektem zmodyfikowania algorytmu w ten sposób, że zamiana miejscami będzie doty- czyła pierwszej i czwartej ćwiartki kolejno pomniejszanych pól, jest słowo będące od- wróceniem wewnętrznego tasowania zupełnego. Warto wspomnieć o przypadku szczególnym, gdy lewa połówka słowa ma wszystkie bity o wartości 0. Innymi słowy, chcemy przenieść bity prawej połówki do co drugiego bitu, przekształcając słowo o następującej strukturzje: #$  ()*+,-./012 W wyniku uzyskamy następujące słowo: #$   ()*+,-./012 Algorytm zewnętrznego tasowania zupełnego można zmodyfikować w taki sposób, aby to zadanie było realizowane w 22 instrukcjach podstawowego zestawu RISC. Po- niższy kod wykonuje to zadanie w 19 instrukcjach bez dodatkowego kosztu, w przypad- ku wykonywania go na maszynach o nieograniczonych możliwościach jednoczesnego wykonania niezależnych instrukcji (12 cykli w przypadku każdej z metod). Metoda ta nie wymaga, aby zawartość bardziej znaczącej połówki słowja była wstępnie wyczyszczona. Z ZZ((  ^ ZZ((  Z Z ^Z Z(((( Z Z ^Z Z Z Z ^Z Z Istnieje także możliwość skonstruowania podobnej do metody tasowania połówkowe- go metody odwrócenia tego przypadku tasowania (będącą szczególnym przypadkiem operacji kompresji, omówionej na stronie 137). Metoda ta wymaga od 26 do 29 in- strukcji podstawowego zestawu RISC, w zależności od tego, czy wymagane jest wstęp- ne wyczyszczenie bitów na nieparzystych pozycjach. Poniższy kod wymaga jednak od 18 do 21 instrukcji z podstawowego zestawu RISC, natomiast w przypadku maszyny obsługującej równoległe wykonanie niezależnych instrukcji kod ten może zostać wy- konany w 12 do 15 cyklach procesora. ZZZLGħNKMQPKGEPG Z Z  ^Z Z Z Z  ^Z Z(((( Z Z  ^Z Z(((( Z Z  ^Z Z(((( 7.3. Transponowanie macierzy bitów Transpozycja macierzy A to taka macierz, która powstaje w wyniku przestawienia wier- szy macierzy A w miejsce kolumn z zachowaniem ich kolejności. W tym podrozdziale zajmiemy się transpozycją macierzy bitów. Elementy omawianej macierzy są zgrupowane Rozdział 7. ♦ Manipulacja bitami i bajtami 129 w bajty. Wiersze i kolumny tej macierzy rozpoczynają się na granicy bajtu. Taka pozor- nie prosta operacja, jaką jest transpozycja tego typu macierzy jest bardzo kosztowna pod względem liczby wykorzystywanych instrukcji. Na większości maszyn ładowanie i przechowywanie pojedynczych bitów byłoby bar- dzo powolne, głównie z powodu kodu, wymaganego w celu wyodrębnienia i (co gorsza) przechowywania pojedynczych bitów. Lepszy sposób polega na podzieleniu macierzy na podmacierze o rozmiarach 8×8 bitów. Każdą z takich macierzy 8×8 bitów ładujemy do rejestrów, wyliczamy transpozycję podmacierzy a następnie macierz wynikową 8×8 zapisujemy w odpowiednim miejscu macierzy wynikowejj. W niniejszym podrozdziale w pierwszej kolejności zajmiemy się problemem wyznacza- nia transpozycji macierzy 8×8 bitów. Sposób przechowywania tablicy, to znaczy kolejność wiersze-kolumny (ang. row-major) lub kolumny-wiersze (ang. column-major) nie ma znaczenia. Wyznaczenie macierzy transponowanej w każdym z tych przypadków wymaga takich samych operacji. Dla celów dalszych rozważań przyjmijmy stosowanie kolejności wiersze-kolumny, w przy- padku której podmacierz 8×8 jest ładowana do ośmiu rejestrów za pomocą ośmiu instruk- cji ładowania wartości z pamięci. Oznacza to, że adresy kolejnych instrukcji ładowania bajtów różnią się o wielokrotność szerokości oryginalnej macierzy liczonej w bajtach. Po wykonaniu transpozycji podmacierz 8×8 zostaje umieszczona w kolumnie macierzy docelowej. Podmacierz ta jest zapisywana za pomocą czterech instrukcji zapisu bajtu w pamięci, z adresami poszczególnych bajtów różniącymi się od siebie o wielokrotność szerokości w bajtach tabeli docelowej (która będzie różna od szerokości w bajtach tabeli źródłowej, jeśli ta nie była kwadratowa). Załóżmy zatem, że mamy osiem 8-bitowych wartości, wyrównanych do prawej w rejestrach C, C, … C. Chcemy wyliczyć osiem 8-bitowych wartości, wyrównanych do prawej w rejestrach D, D, … D, które będą wykorzystane w instrukcjach zapisu bajtów w pamięci. Sytuacje tę ilustrujemy poni- żej, każdy z bitów oznaczając inną cyfrą lub literą. Warto zwrócić uwagę na fakt, że główna przekątna przebiega od bitu 7. bajtu 0 do bitu 0. bajtu 7. Czytelnicy przywykli do notacji big-endian mogliby oczekiwać, że główna przekątna przebiega od bitu 0. bajtu 0 do bitu 7. bajtu 7. C DIQY /7 CCDEFGH DJRZ(08 CIJKLMNOP DCKS[)19 CQRSTUVWX == DDLT*2: CYZ[#$ DEMU#+3; C ()*+,-. DFNV$,4 C/0123456 DGOW -5 C789:;  DHPX .6 130 Uczta programistów Najprostszy kod wykonujący to zadanie obrabiałby każdy bit indywidualnie w sposób przedstawiony poniżej. Mnożenia i dzielenia reprezentują, odpowiednio, przesunięcia w prawo lub w lewo. D C ^ C ^ C ^ C ^  C ^ C ^ C ^ C  D C ^ C ^ C ^ C ^  C ^ C ^ C ^ C  D C ^ C ^ C ^ C ^  C ^ C ^ C ^ C  D C ^ C ^ C ^ C ^  C ^ C ^ C ^ C  D C ^ C ^ C ^ C ^  C ^ C ^ C ^ C  D C ^ C ^ C ^ C ^  C ^ C ^ C ^ C  D C ^ C ^ C ^ C ^  C ^ C ^ C ^ C  D C ^ C ^ C ^ C ^  C ^ C ^ C ^ C  Powyższy kod na większości maszyn wymaga 174 instrukcji (62 koniunkcje, 56 prze- sunięć oraz 56 alternatyw). Instrukcje alternatywy można oczywiście zastąpić instruk- cjami dodawania. Na procesorach PowerPC kod ten może zostać wykonany w 63 in- strukcjach, co może być dość zaskakujące (siedem instrukcji przeniesienia wartości i 56 instrukcji przesunięcia cyklicznego w lewo z następującym podstawieniem wartości z za- stosowaniem maski). Nie liczymy instrukcji ładowania i zapisywania wartości bajtów ani kodu niezbędnego do wyliczenia ich adresów. Nie jest powszechnie znany żaden algorytm, który rozwiązywał by ten problem i który można by uznać za doskonały. Mimo to kolejna z omawianych technik jest dwukrotnie lepsza od powyższej, w każdym razie w przypadku procesorów obsługujących instruk- cje podstawowego zestawu RISC. W pierwszej kolejności należy potraktować macierz 8×8 jako 16 macierzy 2×2 i wyko- nać transpozycje każdej z tych macierzy 2×2. Następnie całą macierz 8×8 traktujemy jak cztery macierze 2×2, z których każda zawiera macierze 2×2 z poprzedniego kroku i ponownie wykonujemy transpozycję. Na końcu całą macierz traktujemy jako ma- cierz 2×2 składającą się z macierzy z poprzedniego kroku i wykonujemy transpozycję tej macierzy. Odpowiednie przekształcenia będą miałyj następujący przebieg:  CEG IQEMU IQY /7 CDEFGH DFH JRFNV JRZ(08 IJKLMNOP IQKSMUOW CKSGOW CKS[)19 QRSTUVWX == JRLTNVPX == DLTHPX == DLT*2: EMU#+3; YZ[#$ Y /7#+3; Y [)#+ - ()*+,-. Z(*$, . Z(P8$,4 FNV$,4 /0123456 /7193;5 [)19 -5 GOW -5 789:;  082:4 6 *2: .6 HPX .6 Rozdział 7. ♦ Manipulacja bitami i bajtami 131 Zamiast wykonywać opisane kroki na ośmiu niezależnych bajtach w ośmiu rejestrach, główne usprawnienie wykorzystuje możliwość spakowania wspomnianych bajtów po cztery do jednego rejestru, następnie można wykonać wymianę bitów na powstałych w ten sposób dwóch rejestrach a następnie rozpakować wynik. Kompletna procedura została zaprezentowana na listingu 7.2. Parametr # określa adres pierwszego bajtu pod- macierzy 8×8 macierzy źródłowej o wymiarach 8O×8P bitów. Podobnie parametr $ sta- nowi adres pierwszego bajtu podmacierzy 8×8 macierzy docelowej o wymiarach 8P×8O bitów. Oznacza to, że cała macierz źródłowa ma wymiary 8O×P bajtów, natomiast ma- cierz wyjściowa ma wymiary 8P×O bajtów. Listing 7.2. Transponowanie macierzy 8×8 bitów XQKFVTCPURQUG WPUKIPGFEJCT#=?KPVOKPVP WPUKIPGFEJCT$=? ] WPUKIPGFZ[V đCFWLGO[VCDNKEúKWOKGUECO[LæYZQTC[ Z #=? ^ #=O? ^ #= O? ^#= O? [ #= O? ^ #= O? ^ #= O? ^#= O? V Z@ Z  Z####ZZ@V@ V  V [@ [  Z####[[@V@ V  V Z@ Z  Z ZZ@V@ V  V [@ [  Z [[@V@ V  V ZZ(((( ^ [  Z((((  [ Z Z(((( ^ [Z((((  ZV $=?Z $=P?Z $= P?Z $= P?Z $= P?[ $= P?[ $= P?[ $= P?[ _ Z całą pewnością mało zrozumiały może wydać się następujjący wiersz kodu: V Z@ Z  Z####ZZ@V@ V  Jego zadaniem jest zamiana miejscami w słowie Z bitów 1. i 8. (licząc od prawej), 3. i 10., 5. i 12. itd., nie naruszając zawartości bitów 0., 2., 4. itd. Zamiana bitów miejscami jest realizowana za pomocą metody wykorzystującej różnicę symetryczną, opisanej na stronie 56. Zawartość słowa Z przed i po pierwszej zamianie wygląda następująco: CDEFGHIJKLMNOPQRSTUVWX CEGDFHIQKSMUOWJRLTNVPX W celu uzyskania realistycznego porównania opisanych metod, „naiwną” metodę ze strony 129 zastosowano w programie podobnym do przedstawionego na listingu 7.2. Obydwie procedury skompilowano za pomocą kompilatora GNU C na maszynie o para- metrach bardzo przypominających parametry podstawowego zestawu instrukcji RISC. W wyniku uzyskano kod składający się z 219 instrukcji dla metody „naiwnej” (licząc 132 Uczta programistów instrukcje ładowania, zapisu, adresowania oraz instrukcje przygotowujące oraz koń- czące procedurę) oraz 101 instrukcji dla kodu z listingu 7.2 (instrukcje wstępne i kończą- ce nie występowały, za wyjątkiem instrukcji powrotu z rozgałęzienia). Adaptacja kodu z listingu 7.2 do 64-bitowej wersji standardowego zestawu RISC (w której Z i [ były- by zapisane w tym samym rejestrze) wykona się w 85 injstrukcjach. Algorytm z listingu 7.2 wykonuje przetwarzanie od największego do najmniejszego roz- drobnienia (biorąc pod uwagę wielkość grup bitów zamienianych miejscami). Metodę tę można również zmodyfikować w taki sposób, aby wykonywała przetwarzanie od naj- mniejszego do największego rozdrobnienia. W tym celu traktujemy macierz 8×8 bitów jako macierz 2×2, składającą się z macierzy 4×4 bity i wykonujemy transpozycję tej macierzy. Następnie każdą z macierzy 4×4 traktujemy jako macierze 2×2 złożone z ma- cierzy 2×2 bity i wykonujemy transpozycje tych macierzy itd. Kod wynikowy takiego algorytmu będzie taki sam, jak na listingu 7.2 za wyjątkiem trzech grup wyrażeń mo- dyfikujących kolejność bitów, które wystąpią w odwróconejj kolejności. Transponowanie macierzy o wymiarach 32×32 bity Podobna technika do zastosowanej w przypadku macierzy 8×8 może być oczywiście za- stosowana dla macierzy o większych rozmiarach. Na przykład w przypadku macierzy 32×32 metoda ta wymaga zastosowania pięciu kroków. Szczegóły implementacji różnią się jednak w stosunku do kodu przedstawionego na li- stingu 7.2, ponieważ zakładamy, że cała macierz 32×32 nie mieści się w dostępnej prze- strzeni rejestrów. Dlatego należy znaleźć zwarty sposób indeksowania odpowiednich słów macierzy bitowej, za pomocą którego będzie możliwe przeprowadzenie odpowied- nich operacji na bitach. Poniższy algorytm działa najlepiej w przypadku techniki od najmniejszego do największego rozdrobnienia. W pierwszym etapie traktujemy macierz jako cztery macierze 16×16 bitów i dokonuje- my ich transpozycji w następujący sposób: BA    DC  ⇒     CA DB    A oznacza lewą połówkę pierwszych 16 słów macierzy, B oznacza prawą połówkę pierw- szych 16 słów macierzy itd. Powyższa transformacja może zostać zrealizowana za po- mocą następujących zamian: Prawa połówka słowa 0 z lewą połówką słowa 16, Prawa połówka słowa 1 z lewą połówką słowa 17, … Prawa połówka słowa 15 z lewą połówką słowa 31, Rozdział 7. ♦ Manipulacja bitami i bajtami 133 W celu implementacji tego mechanizmu posłużymy się indeksem k o wartościach od 0 do 15. W pętli kontrolowanej wartością k, prawa połówka słowa k zostanie lewą po- łówką słowa k + 16. W drugiej fazie macierz jest traktowana jako 16 macierzy 8×8 bitów, na której przepro- wadzamy następujące przekształcenie:       DCBA HGFE I LKJ PONM       ⇒       GCEA HDFB OKMI PLNJ       Transformację tę można zrealizować za pomocą następującycjh przekształceń: Bity 0x00FF00FF słowa 0 zamieniamy z bitami 0xFF00FF00 słowa 8 Bity 0x00FF00FF słowa 1 zamieniamy z bitami 0xFF00FF00 słowa 9, itd.j Oznacza to, że bity 0 – 7 (osiem najmniej znaczących bitów) słowa 0 zamieniamy z bi- tami 8 – 15 słowa 8 itd. Indeksy pierwszego słowa w tych zamianach to k = 0, 1, 2, 3, 4, 5, 6, 7, 16, 17, 18, 19, 20, 21, 22, 23. Sposobem na przejście zmiennej k przez wymie- nione wartości jest następujące wyrażenie: k′ = (k + 9) ¬8 W pętli kontrolowanej wartością zmiennej k bity słowa o indeksie k są zamieniane z bi- tami słowa o indeksie k + 8. Podobnie trzecia faza wykonuje następujące zamiany: Bity 0x0F0F0F0F słowa 0 zamieniamy z bitami 0xF0F0F0F0 słowa 4, Bity 0x0F0F0F0F słowa 1 zamieniamy z bitami 0xF0F0F0F0 słowa 5, itd.j Indeksy pierwszego słowa w tych zamianach to k = 0, 1, 2, 3, 8, 9, 10, 11, 16, 17, 18, 19, 24, 25, 26, 27. Sposobem na przejście zmiennej k przez wymienione wartości jest nastę- pujące wyrażenie: k′ = (k + 5) ¬4 W pętli kontrolowanej wartością zmiennej k, bity słowa o indeksie k są zamieniane z bi- tami słowa o indeksie k + 4. Wynik powyższych rozważań można zakodować w języku C w dość zwarty sposób, przedstawiony na listingu 7.3.[GLS1]. Zewnętrzna pętla kontroluje pięć etapów prze- twarzania, zmienna L przyjmuje wartości 16, 8, 4, 2 oraz 1. Pętla ta również kontro- luje zmianę maski o wartościach odpowiednio dla każdego przebiegu: 0x0000FFFF, 0x00FF00FF, 0x0F0F0F0F, 0x33333333 oraz 0x55555555 (kod generujący maskę to OO@ OL ). Algorytm ten nie posiada wersji odwracającej operację, jest to je- den z głównych powodów najlepszego funkcjonowania przekształceń od najmniejszego 134 Uczta programistów do największego rozdrobnienia macierzy. Wewnętrzna pętla jest kontrolowana warto- ścią zmiennej M, która przyjmuje kolejno wartości wymienione wyżej. Wewnętrzna pę- tla powoduje wymianę bitów C=M? określonych maską O z bitami C=M L? przesuniętymi w prawo o L i również określonymi maską O, co odpowiada bitom C=M L? określo- nym dopełnieniem maski O. Kod wykonujący wspomniane zamiany bitów jest adaptacją techniki wykorzystującej trzy różnice symetryczne przedstawionej w podrozdziale Wy- miana wartości między rejestrami na stronie 56 w kolumnie (c). Listing 7.3. Transpozycja macierzy o wymiarach 32×32 bity XQKFVTCPURQUG WPUKIPGF#=? ] KPVLM WPUKIPGFOV OZ(((( HQT LLLL OO@ OL ] HQT MMM M L  `L ] V #=M?@ #=M L? L O #=M?#=M?@V #=M L?#=M L?@ VL  _ _ _ Po skompilowaniu tej funkcji za pomocą kompilatora GNU C na maszynie o właści- wościach zbliżonych do podstawowego zestawu instrukcji RISC kod ten zawiera 31 instrukcji, 20 w wewnętrznej pętli i 7 w zewnętrznej. Funkcja ta wykonuje się zatem w 4 + 5(7 + 16 ⋅ 20) = 1639 instrukcjach. Dla porównania: gdyby funkcje tę wywoła- no z wykorzystaniem 16 wywołań programu z listingu 7.2, wykonującego transpozy- cję macierzy 8×8, zajęłoby to 16(101 + 5) = 1696 instrukcji, z założeniem, że te 16 wy- wołań zostałoby wykonanych jedno po drugim. Obliczenia te obejmują również pięć instrukcji niezbędnych do wykonania wywołania funkcji (własność zaobserwowana w skompilowanym kodzie). Stąd wynika, że obydwie opisane funkcje są bardzo zbliżone pod względem czasuj wykonania. Z drugiej strony dla maszyn 64-bitowych kod z listingu 7.3 można z łatwością zmo- dyfikować w taki sposób, że wykonuje transpozycję macierzy 64×64 bity w około 4 + 6 (7 + 32 ⋅ 20) = 3886 instrukcjach. Realizacja tego celu za pomocą 64 wywołań trans- pozycji macierzy 8×8 wymagałoby około 64(85 + 5) = 5760 instrukcji. Algorytm ten wykonuje się „w miejscu” (na oryginalnej macierzy), dlatego w przy- padku transpozycji większych macierzy wymaga się dodatkowego kopiowania pod- macierzy 32×32-bitowych. Algorytm ten można zmusić do dokonywania zapisu w osob- nym obszarze pamięci. W tym celu należy wyodrębnić pierwszy lub ostatni krok pętli HQTLi wynik w tym kroku zapisać w osobnym obszarze pamijęci1. 1 Jeśli zrobimy to w pierwszym kroku, unikniemy nadpibsania oryginalnej zawartości macierzy źródłowej — przyp. tłum. Rozdział 7. ♦ Manipulacja bitami i bajtami 135 Około połowę instrukcji definiujących funkcję na listingu 7.3 stanowią instrukcje kon- trolne pętli oraz funkcje odczytujące i zapisujące pięciokrotnie całą macierz. Czy roz- sądne byłoby zmniejszenie tego nakładu za pomocą rozwinięcia pętli? Byłoby w przy- padku, gdyby programiście zależało na jak największej prędkości wykonania i gdyby zwiększona objętość kodu nie stanowiła problemu. Ważnym też jest, aby mechanizm pobierania instrukcji (ang. I-fetching) w procesorze poradził sobie z płynnym wyko- nywaniem tak długiego bloku nierozgałęzionego kodu. Przede wszystkim jednak me- chanizm ten byłby warty rozważenia, jeśli rozgałęzienia i procedury ładowania i zapisu danych z i do pamięci byłyby kosztownymi operacjami pod względem czasu wykony- wania. Większość programu będzie stanowiło sześć wierszy wykonujących zamianę bitów, powtórzone 16 razy (co w wyniku da 80 wierszy). Dodatkowo program będzie potrzebował 32 instrukcji ładowania danych, pobierających macierz źródłową oraz 32 in- strukcje zapisu danych, zapisujące macierz wynikową. Wszystko to da w wyniku 544 in- strukcje. Nasz kompilator GNU C nie rozwija pętli w tak dużej liczbie przebiegów (15 w we- wnętrznej pętli, 5 w zewnętrznej). Listing 7.4 przedstawia wersję funkcji, w której roz- winięć dokonano ręcznie. Program ten prezentujemy w wersji niepracującej „w miej- scu”, jednak w razie konieczności będzie on poprawnie działał w takiej wersji. W tym celu funkcję należy wywołać z obydwoma identycznymi argumentami. W programie występuje 80 wierszy wywołujących makro UYCR. Nasz kompilator GNU C kompiluje ten kod na maszynę obsługującą podstawowy zestaw instrukcji RISC z wykorzysta- niem 576 instrukcji (bez rozgałęzień, za wyjątkiem powrotu z funkcji), wliczając w to czynności przygotowawcze i kończące procedurę. Wykorzystana maszyna nie obsługuje instrukcji ładowania ani zapisu wielu wartości (ang. load multiple oraz store multiple), lecz potrafi zapisać i odczytać wartość dwóch rejestrów na raz, z wykorzystaniem in- strukcji store double oraz load double (zapis oraz odczyt podwójnej wartości). Listing 7.4. Transpozycja macierzy o rozmiarze 32x32 bitów w poistaci rozwiniętej FGHKPGUYCR CCLO V C@ C L O CC@V CC@ VL  XQKFVTCPURQUG WPUKIPGF#=?WPUKIPGF$=? ] WPUKIPGFOV WPUKIPGFCCCCCCCC CCCCCCCC CCCCCCCC CCCCCCCC C#=?C#=?C#=?C#=? C#=?C#=?C#=?C#=?  C#=?C#=?C#=?C#=? OZ(((( UYCR CCO UYCR CCO  136 Uczta programistów UYCR CCO OZ(((( UYCR CCO UYCR CCO   UYCR CCO UYCR CCO $=?C$=?C$=?C$=?C $=?C$=?C$=?C$=?C  $=?C$=?C$=?C$=?C _ Istnieje sposób na dalsze zwiększenie wydajności, o ile maszyna obsługuje instrukcje przesunięcia cyklicznego (w lewo lub w prawo, bez różnicy). Pomysł polega na zastąpie- nie wszystkich wywołań makra UYCR na listingu 7.4 (z których każde wykorzystuje sześć instrukcji) prostszą formą zamiany, niewykorzystującą przesunięć i wykorzystującą tyl- ko cztery instrukcje (w istniejącym makrze UYCR należy usunąć operacje przesunięć). Najpierw należy przesunąć cyklicznie o 16 pozycji w prawo słowa A[16..31] (to znaczy A[k], gdzie 16 ≤ k ≤ 31). Następnie należy zamienić miejscami prawe połówki słów A[0] z A[16], A[1] z A[17] itd., jak to przedstawiono na listingu 7.4. Następnie należy obrócić o osiem pozycji w prawo słowa A[0..8] oraz A[24..31] i zamienić miejscami bity oznaczone w masce 0x00FF00FF w słowach A[0] z A[8], A[1] z A[9] itd., jak to przedstawiono na listingu 7.4. Po pięciu etapach takich zamian transpozycja nie będzie jeszcze wykonana. Należy na końcu przesunąć cyklicznie A[1] w lewo o jedną pozy- cję, A[2] o dwie pozycje itd. (31 instrukcji). Nie prezentujemy kompletnego kodu, na- tomiast przedstawiamy przykład działania dla macierzy 4×4. CDEF CDEF CDKL CDKL CGKO CGKO GHIJ == GHIJ == GHOP == PGHO == PDHL == DHLP KLMN OPQR MNKL QROP MNEF QRIJ MNEF JQRI MQEI JNRF EIMQ FJNR Fragment programu na listingu 7.4 odpowiedzialny za manipulację bitami wykorzystuje 480 instrukcji (80 zamian po sześć instrukcji każda). Zmodyfikowany program wykorzy- stujący instrukcję przesunięcia cyklicznego wykorzystuje 80 zamian po cztery instrukcje każda, plus 80 instrukcji przesunięcia cyklicznego (16 ⋅ 5) w pięciu etapach plus koń- cowe 31 instrukcji przesunięcia cyklicznego, co w sumie daje 431 instrukcji. Kod przy- gotowujący oraz kończący funkcję nie ulegnie zmianie, zatem wykorzystanie przesunięć cyklicznych pozwala na zaoszczędzenie 49 instrukcji. Istnieje inny sposób realizacji transpozycji macierzy, wykorzystujący trzy przekształce- nia poprzeczne (ang. shearing transformation) [GLS1]. W przypadku, gdy macierz ma wymiary n×n wykorzystywane są następujące etapy: Rozdział 7. ♦ Manipulacja bitami i bajtami 137     przesunięcie cykliczne wiersza i w prawo o i bitów; przesunięcie cykliczne kolumny j w górę o (j + 1) mod n bitów; przesunięcie cykliczne wiersza i w prawo o (i + 1) mod n bitów; pionowe odbicie macierzy względem środka. W celu ilustracji tej techniki przedstawiamy jej zasjtosowanie na macierzy 4×4: CDEF CDEF JNRF FJNR CGKO GHIJ == JGHI == MQEI == EIMQ == DHLP KLMN OPQR MNKL PQRO PDHL CGKO DHLP CGKO EIMQ FJNR Metoda ta nie stanowi konkurencji dla pozostałych z powodu dużej kosztowności kroku 2. Aby wykonać ten krok w rozsądnej liczbie operacji, należałoby wykonać przesunięcie cykliczne o n/2 pozycji wszystkich kolumn, które wykonują przesunięcie o n/2 lub większą liczbę pozycji (są to kolumny od n/2 – 1 do n – 2] a następnie wykonać prze- sunięcie cykliczne odpowiednich kolumn o n/4 pozycji w górę itd. Kroki 1. oraz 3. wy- magają tylko n – 1 instrukcji, natomiast krok 4. nie wymaga żadnych instrukcji, jeśli wyniki są od razu zapisywane do odpowiednich obszarówj w pamięci. W przypadku macierzy 8×8 zapisanej w pojedynczym słowie 64-bitowym w oczywisty sposób (to znaczy górny wiersz macierzy jest zapisany w najbardziej znaczących ośmiu bitach rejestru) operacja transpozycji jest równoważna trzem operacjom zewnętrznego tasowania zupełnego i odtasowania [GLS1]. Jest to doskonały sposób realizacji tego za- dania, o ile maszyna udostępnia instrukcję tasowania, lecz w przypadku maszyny ze standardowym zestawem instrukcji RISC nie jest to dobrje rozwiązanie. 7.4. Kompresja lub uogólniona ekstrakcja Język programowania APL posiada operację kompresji (ang. compress) zapisywaną B/V, gdzie B jest wektorem bitów, natomiast V jest wektorem o tej samej długości co B, zawierającym dowolne elementy. Wynikiem operacji jest wektor składający się z ele- mentów V, dla których odpowiadające im bity wektora B mają wartość 1. Długość wek- tora wynikowego jest równa liczbie jedynek w B. W niniejszym podrozdziale zajmiemy się podobną operacją na bitach w słowie. Po poda- niu maski m i słowa x, bity w x, dla których odpowiednie bity w masce m mają war- tość 1 zostają skopiowane do wyniku i przesunięte (skompresowane) do prawej. Załóż- my na przykład, że operujemy na słowie x o następującej strukturze: CDEFGHIJKLMNOPQRSTUVWXZ[#$ ( 138 Uczta programistów Maska w naszej operacji będzie następująca:  W takim przypadku wynikiem operacji EQORTGUU będzie następujące słowo: GHIJMNQRSUWY$ ( Operację tę można również nazwać uogólnioną ekstrakcją (ang. generalized extract), przez analogię do instrukcji GZVTCEV udostępnianej przez wiele komputerów. Interesuje nas kod wykonujący te operacje o jak najmniejszym koszcie wykonawczym w najgorszym przypadku. Jako element wyjściowy posłużymy się kodem na listingu 7.5, który postaramy się usprawnić. Kod ten nie wykorzystuje rozgałęzień i wykonuje się w najgorszym wypadku w 260 instrukcjach, wliczając opejracje wstępne i końcowe. Listing 7.5. Prosta forma operacji compress WPUKIPGFEQORTGUU WPUKIPGFZWPUKIPGFO ] WPUKIPGFTUDY[PKMRTGUWPKúEKGOCUMCDKVQYC T U FQ] DO TT^ ZD U  UU D ZZ  OO  _YJKNG O  TGVWTPT _ Można usprawnić ten kod za pomocą metody prefiksu równoległego (zob. rozdział 5., strona 85) z wykorzystaniem operacji różnicy symetrycznej [GLS1]. Operację prefiksu równoległego z wykorzystaniem różnicy symetrycznej oznaczmy PP-XOR. Główny pomysł polega tu na wyodrębnieniu bitów argumentu x, które należy przesunąć w pra- wo o nieparzystą liczbę pozycji i na wykonaniu tego przesunięcia. Operację tę można uprościć przez koniunkcję x z maską w celu usunięcia niepotrzebnych bitów. Bity ma- ski przesuwamy w ten sam sposób. Następnie identyfikujemy te bity w x, które należy przesunąć o liczbę miejsc będącą nieparzystą wielokrotnością dwójki (2, 6, 10 itd.) i przesuwamy te bity w x oraz w masce. Następnie identyfikujemy i przesuwamy bity, które należy przesunąć o nieparzystą wielokrotność liczby 4, następnie powtarzamy tę operację dla nieparzystej wielokrotności 8 a następnie dla bitów, które należy przesu- nąć o 16 pozycji. Algorytm ten (którego pierwszą publikację przypisuje się [GLS1]) wydaje się być dość trudny do zrozumienia i taki sposób zrealizowania czegokolwiek nie wydaje się być w ogóle możliwy, zatem operacje wykorzystywane przez ten algorytm omówimy z nie- co większą szczegółowością. Załóżmy, że naszymi wartościami wejściowymi są: Rozdział 7. ♦ Manipulacja bitami i bajtami 139 ZCDEFGHIJKLMNOPQRSTUVWXYZ[#$ ( O       Każda litera w Z symbolizuje jeden bit (o wartości 0 lub 1). Liczba poniżej każdej jedyn- ki w masce oznacza liczbę miejsc, o które należy przesunąć w prawo dany bit słowa Z. Jest to liczba zer w masce na prawo od tego miejsca. Jak wspomniano wcześniej, wy- godnie jest oczyścić Z z niepotrzebnych bitów, co da w wyniku: ZCGKLMWXYZ$ ( Plan polega na określeniu bitów, które przesuwają się o nieparzystą liczbę miejsc w pra- wo i przesunąć je o jedną pozycję. Przypomnijmy, że operacja PP-XOR w wyniku daje 1 na każdej pozycji, na której liczba jedynek od tego miejsca (włącznie) w prawo jest nie- parzysta. My chcemy natomiast zidentyfikować miejsca, od których w prawo liczba zer jest nieparzysta. Możemy to wyliczyć za pomocą zmiennej pomocniczej OM`O, wyliczając na niej PP-XOR. Otrzymamy: OM OR Zaobserwujemy, że OM identyfikuje bity, które zawierają zera bezpośrednio po swojej prawej stronie, natomiast OR sumuje te zera, modulo 2, od prawej strony. W ten sposób OR identyfikuje bity w O, które posiadają nieparzystą liczbę zer po swojej prjawej stronie. Bity, które chcemy przesunąć o 1 to są te bity, które posiadają nieparzystą liczbę zer po swojej prawej stronie (zidentyfikowane przez OR) oraz w oryginalnej masce mają war- tość 1. Dlatego bity te zidentyfikujemy za pomocą OXORO: OX Bity te można przesunąć za pomocą następującego wyrażenija: O O@OX ^ OX   Natomiast odpowiadające im bity w Z przesuwamy za pomocą następującego wyrażenia: VZOX Z Z@V ^ V   Przesuwanie odpowiednich bitów w O jest prostsze, ponieważ wszystkie odpowiednie bity mają wartość 1. W tym przypadku operacja różnicy symetrycznej wyłącza bity, bę- dące jedynkami w Z, natomiast alternatywa bitowa włącza bity mające wartość 0 w O oraz w Z. Operacja ta może również wykorzystywać dwie operacje różnicy symetrycznej lub, odpowiednio, odejmowania i dodawania. Wyniki, po odpowiednim przesunięciu wybranych bitów, będą wyglądać następująco: O ZCGKLMWXYZZ$ ( 140 Uczta programistów W następnej kolejności musimy przygotować maskę dla drugiej iteracji, gdzie nastąpi wy- krywanie bitów, które należy przesunąć w prawo o nieparzystą wielokrotność dwójki. Zauważmy, że wartość OM`OR identyfikuje bity, które mają wartość 0 bezpośrednio z prawej strony w oryginalnej masce O oraz które posiadają parzystą liczbę zer po pra- wej stronie w oryginalnej masce. Własności te łączą się, tworząc własności zmienionej maski O (oznacza to, że OM identyfikuje wszystkie miejsca w nowej masce O, które są- siadują z prawej strony z zerem oraz posiadają parzystą liczbę zer ze swojej prawej stro- ny). Wartość ta, po podsumowaniu przez PP-XOR, zidentyfikuje bity, które należy przesunąć w prawo o nieparzystą wielokrotność dwójki (2, 6, 10 itd.) Procedura nasza będzie polegała na przypisaniu tej własności do OM i wykonaniu drugiej iteracji wymie-
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Uczta programistów
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ą: