15.09.2017 14:45
[#1]
W temacie mojej procedury konwersji c2p
Jako, że w opisie działu są "szybkie rutynki" chciałbym tylko tu dać znać, że opracowałem całkiem fajną procedurę konwersji c2p. Jest o wiele wiele lepsza, aniżeli procedura zakodowana przeze mnie kilka lat temu.
Liniowo ułożone piksele, maski w rejestrach procesora. Z obliczeń wyszło, że MC68020 potrzebuje (przeciętnie) 14,25 taktów na jeden piksel.
Szczegóły tutaj!
Liniowo ułożone piksele, maski w rejestrach procesora. Z obliczeń wyszło, że MC68020 potrzebuje (przeciętnie) 14,25 taktów na jeden piksel.
Szczegóły tutaj!
15.09.2017 15:09
[#2]
Re: W temacie mojej procedury konwersji c2p
@Hexmage960, post #1
Umieściłeś wątek w dziale scena, więc pozwolę sobie na komentarz. Demoscena nie lubi suchych teoretycznych tekstów z których mało wynika, lubi natomiast konkrety. Myślę, że byłoby 100 x lepiej, gdybyś na bazie swojej procedury przygotował choć najprostsze 1- efektowe demo / intro i pokazał je światu, chociażby na najbliższym party w Gdańsku w smaller exe compo 
12.11.2017 21:02
[#7]
Re: W temacie mojej procedury konwersji c2p
@Hexmage960, post #6
Moja praca nad własnym modelem c2p wreszcie dobiega końca.
Oznacza to, że doszedłem do konkluzji, na bazie której mogę stworzyć efektywną procedurę c2p oraz, w analogiczny sposób - p2c. Mam nadzieję, że następnie wykorzystam tą procedurę w praktyce.
Mój model różni się nieco od modelu Kalmsa. Kalms rozumie c2p jako transpozycję macierzy.
Ja rozumiem c2p jako skalowanie wektora.
Te modele różnią się od siebie zasadniczo.
W moim modelu proces c2p jest nieco przejrzystszy i łatwiejszy do zrozumienia i implementacji na każdym etapie.
W rzeczywistości mój model ma koszt liniowy względem liczby bitplanów razy liczba pikseli.
Otóż określiłem formaty: planarny, chunky 2-pikselowy, chunky 4-pikselowy oraz ten właściwy chunky 8-pikselowy oraz opisałem konwersję.
Chunky 2-pikselowy oznacza, że dwa sąsiadujące ze sobą bity opisują piksel.
Konwersja przebiega od Chunky 8-pikselowego do planarnego. Stosowane są wspomniane formaty pośrednie.
Opiszę teraz co to jest to skalowanie. Dla każdego formatu stosowany jest odpowiedni algorytm skalowania.
Otóż skalowanie to zawężanie lub rozszerzanie bitów w słowie. Zawężanie stosuje się przy konwersji chunky to planar, zaś rozszerzanie w procesie odwrotnym (planar to chunky).
Zawężanie polega na tym, że każdy bit (lub bloki 2/4 bitów) słowa przesuwa się w lewo na pozycję n/2.
Oto przykład:
Co ciekawe okazuje się, że skalowanie bloków o większej długości jest mniej kosztowne aniżeli ta sama operacja dla bloków o mniejszej długości. W przypadku chunky 2-pikselowego najlepiej użyć wartości umieszczonych w tablicy o długości 256 lub 65 tys. elementów. W przypadku chunky 8-pikselowego można zrobić to algorytmicznie.
Pozostałe dwa etapy:
Mam nadzieję, że przejrzystość tego rozwiązania jest dobrze widoczna. Algorytm odwrotny, czyli planar to chunky jest realizowany identycznie z tą różnicą, że skalujemy w drugą stronę.
Ostatnia aktualizacja: 12.11.2017 21:04:15 przez Hexmage960
Oznacza to, że doszedłem do konkluzji, na bazie której mogę stworzyć efektywną procedurę c2p oraz, w analogiczny sposób - p2c. Mam nadzieję, że następnie wykorzystam tą procedurę w praktyce.
Mój model różni się nieco od modelu Kalmsa. Kalms rozumie c2p jako transpozycję macierzy.
Ja rozumiem c2p jako skalowanie wektora.
Te modele różnią się od siebie zasadniczo.
W moim modelu proces c2p jest nieco przejrzystszy i łatwiejszy do zrozumienia i implementacji na każdym etapie.
W rzeczywistości mój model ma koszt liniowy względem liczby bitplanów razy liczba pikseli.
Otóż określiłem formaty: planarny, chunky 2-pikselowy, chunky 4-pikselowy oraz ten właściwy chunky 8-pikselowy oraz opisałem konwersję.
Chunky 2-pikselowy oznacza, że dwa sąsiadujące ze sobą bity opisują piksel.
Konwersja przebiega od Chunky 8-pikselowego do planarnego. Stosowane są wspomniane formaty pośrednie.
Opiszę teraz co to jest to skalowanie. Dla każdego formatu stosowany jest odpowiedni algorytm skalowania.
Otóż skalowanie to zawężanie lub rozszerzanie bitów w słowie. Zawężanie stosuje się przy konwersji chunky to planar, zaś rozszerzanie w procesie odwrotnym (planar to chunky).
Zawężanie polega na tym, że każdy bit (lub bloki 2/4 bitów) słowa przesuwa się w lewo na pozycję n/2.
Oto przykład:
Skalowanie chunky 8-pikselowego do chunky 4-pikselowego a7a6a5a4a3a2a1a0 b7b6b5b4b3b2b1b0 c7c6c5c4c3c21c0 d7d6d5d4d3d2d1d0 - chunky 8-pikselowe a7a6a5a4........ b7b6b5b4........ c7c6c5c4........ d7d6d5d4........ ........a3a2a1a0 ........b3b2b1b0 ........c3c2c1c0 ........d3d2d1d0 Po przeskalowaniu: a7a6a5a4 b7b6b5b4 c7c6c5c4 d7d6d5d4 - chunky 4-pikselowe (bitplany wyższe) a3a2a1a0 b3b2b1b0 c3c2c1c0 d3d2d1d0 - chunky 4-pikselowe (bitplany niższe)
Co ciekawe okazuje się, że skalowanie bloków o większej długości jest mniej kosztowne aniżeli ta sama operacja dla bloków o mniejszej długości. W przypadku chunky 2-pikselowego najlepiej użyć wartości umieszczonych w tablicy o długości 256 lub 65 tys. elementów. W przypadku chunky 8-pikselowego można zrobić to algorytmicznie.
Pozostałe dwa etapy:
a7a6a5a4 b7b6b5b4 c7c6c5c4 d7d6d5d4 e7e6e5e4 f7f6f5f4 g7g6g5g4 h7h6h5h4 - chunky 4-pikselowe a7a6.... b7b6.... c7c6.... d7d6.... e7e6.... f7f6.... g7g6.... h7h6.... ....a5a4 ....b5b4 ....c5c4 ....d5d4 ....e5e4 ....f5f4 ....g5g4 ....h5h4 Po przeskalowaniu: a7a6 b7b6 c7c6 d7d6 e7e6 f7f6 g7g6 h7h6 - chunky 2-pikselowe a5a4 b5b4 c5c4 d5d4 e5e4 f5f4 g5g4 h5h4 - chunky 2-pikselowe a7a6 b7b6 c7c6 d7d6 e7e6 f7f6 g7g6 h7h6 i7i6 j7j6 k7k6 l7l6 m7m6 n7n6 o7o6 p7p6 a7.. b7.. c7.. d7.. e7.. f7.. g7.. h7.. i7.. j7.. k7.. l7.. m7.. n7.. o7.. p7.. ..a6 ..b6 ..c6 ..d6 ..e6 ..f6 ..g6 ..h6 ..i6 ..j6 ..k6 ..l6 ..m6 ..n6 ..o6 ..p6 Po przeskalowaniu: a7b7c7d7e7f7g7h7 i7j7k7l7m7n7o7p7 - format planarny a6b6c6d6e6f6g6h6 i6j6k6l6m6n6o6p6
Mam nadzieję, że przejrzystość tego rozwiązania jest dobrze widoczna.
Algorytm odwrotny, czyli planar to chunky jest realizowany identycznie z tą różnicą, że skalujemy w drugą stronę.Ostatnia aktualizacja: 12.11.2017 21:04:15 przez Hexmage960
12.11.2017 21:38
[#9]
Re: W temacie mojej procedury konwersji c2p
@] SKOLMAN_MWS ˇ agrEssOr [, post #8
OK, po zapisaniu implementacji rzucę okiem do tego wątku i przetestuję algorytm. Póki co moim głównym celem to zrobienie naprawdę przejrzystej i łatwej w zrozumieniu realizacji zagadnienia konwersji pikseli w formatach chunky i planar, co myślę, że mi się udało.
Spodziewam się, że procedura realizująca ten algorytm będzie dość szybka.
Ostatnia aktualizacja: 12.11.2017 21:38:44 przez Hexmage960
Spodziewam się, że procedura realizująca ten algorytm będzie dość szybka.
Ostatnia aktualizacja: 12.11.2017 21:38:44 przez Hexmage960
13.11.2017 10:16
[#11]
Re: W temacie mojej procedury konwersji c2p
@] SKOLMAN_MWS ˇ agrEssOr [, post #10
Tak się zastanawiam, że można robić konwersję w jednym kroku z chunky-8 do planar dzięki mojej metodzie. Nie trzeba korzystać z formatów przejściowych, które okazały się gmatwać w tym przypadku sytuację.
Mam pomysł, żeby skalowanie przy c2p odbywało się na zasadzie wyszukiwania binarnego z tablicy 256-elementowej, które będzie powtarzane 4 razy dla kolejnych 8 pikseli, a następnie dla każdego bitplanu.
Średnia liczba poszukiwań dla losowych danych wynosiłaby wówczas 16 dla 32 pikseli.
Oznacza to:
Z minusów:
Myślę, że gra jest warta świeczki.
Ostatnia aktualizacja: 13.11.2017 10:18:16 przez Hexmage960
Mam pomysł, żeby skalowanie przy c2p odbywało się na zasadzie wyszukiwania binarnego z tablicy 256-elementowej, które będzie powtarzane 4 razy dla kolejnych 8 pikseli, a następnie dla każdego bitplanu.
Średnia liczba poszukiwań dla losowych danych wynosiłaby wówczas 16 dla 32 pikseli.
Oznacza to:
- bardzo krótką i prostą procedurę (zmieści się w cache 256-bajtów),
- dosyć szybki czas wykonania,
- tani zapis 32-bitowy.
Z minusów:
- iteracje wewnątrz procedury
Myślę, że gra jest warta świeczki.
Ostatnia aktualizacja: 13.11.2017 10:18:16 przez Hexmage960
13.11.2017 11:36
[#13]
Re: W temacie mojej procedury konwersji c2p
@Hexmage960, post #11
020 nie ma data cache więc tablicowanie potencjalnie grozi dodatkowym spowolnieniem - tu musisz rozważyć korzyści ze zmiany podejścia. Poprzednia wersja zdaje się że mieściła się w instruction cache 020, więc potencjalnie mogła być szybsza od stablicowanej. Ale wszystko zależy od ilości odwołań do tablic które chcesz wprowadzić.
13.11.2017 16:25
[#14]
Re: W temacie mojej procedury konwersji c2p
@makarsky, post #13
W c2p (tak jak zresztą w różnych przekształceniach) jest zawsze "coś za coś" i zabawa polega na znalezieniu optymalizacji, dzięki której koszt będzie jak najmniejszy. 
W moim modelu skalowanie jest operacją najbardziej kosztowną, bo chyba nie istnieje prosta sekwencja poleceń procesora, by to ładnie uzyskać dla c2p.
Jednak właśnie skalowanie to jest to co czyni moją procedurę dość przejrzystą i stanowi jej mocną stronę.
Dla operacji odwrotnej, czyli p2c jest to realizowane łatwiej, bo tutaj można odwołać się bezpośrednio do elementów w tablicy (czyli koszt O(1)), bo skalujemy bajt do poczwórnego słowa.
W przypadku c2p skalujemy coś większego do czegoś mniejszego, więc warto użyć tutaj operacji wyszukiwania binarnego, które w optymistycznym przypadku ma koszt O(1), ale w pesymistycznym - O(n), gdzie n to liczba pikseli. Średnio wychodzi koszt n/2.
Ciekaw jestem czy wyszukiwanie binarne, w którym jednak ilość operacji zależy sporo od typu danych nie przyniesie ogólnych oszczędności.
Tablica jest rozmiaru zaledwie 256 bajtów (czyli tyle ile wynosi data cache 030). W podstawowym algorytmie skalujemy 64 bity do 8 bitów.
W każdym razie moja kilkuletnia praca nad tym tematem przyniosła sporo ciekawych wniosków.
W wolnym czasie zakoduję procedurę realizującą ten ostatni pomysł. Może nawet dzisiaj.
W moim modelu skalowanie jest operacją najbardziej kosztowną, bo chyba nie istnieje prosta sekwencja poleceń procesora, by to ładnie uzyskać dla c2p.
Jednak właśnie skalowanie to jest to co czyni moją procedurę dość przejrzystą i stanowi jej mocną stronę.
Dla operacji odwrotnej, czyli p2c jest to realizowane łatwiej, bo tutaj można odwołać się bezpośrednio do elementów w tablicy (czyli koszt O(1)), bo skalujemy bajt do poczwórnego słowa.
W przypadku c2p skalujemy coś większego do czegoś mniejszego, więc warto użyć tutaj operacji wyszukiwania binarnego, które w optymistycznym przypadku ma koszt O(1), ale w pesymistycznym - O(n), gdzie n to liczba pikseli. Średnio wychodzi koszt n/2.
Ciekaw jestem czy wyszukiwanie binarne, w którym jednak ilość operacji zależy sporo od typu danych nie przyniesie ogólnych oszczędności.
Tablica jest rozmiaru zaledwie 256 bajtów (czyli tyle ile wynosi data cache 030). W podstawowym algorytmie skalujemy 64 bity do 8 bitów.
W każdym razie moja kilkuletnia praca nad tym tematem przyniosła sporo ciekawych wniosków.
W wolnym czasie zakoduję procedurę realizującą ten ostatni pomysł. Może nawet dzisiaj.
13.11.2017 17:19
[#15]
Re: W temacie mojej procedury konwersji c2p
@Hexmage960, post #14
Nie chce Cie zniechecac ale juz kilka osob powiedzialo to w tym watku a nawet w kilku innych
Jak mozesz porownywac dzialanie swoich modyfikacji procedury (nie mowiac o porownywaniu wzgledem innych) jak nie tobisz benchmarka? Skad wieez czy to co napisales dziala albo jak szybko dziala? Skad wiesz jak to wypada wzgledem innych procedur ktorych kod podano Ci tutaj
Skad bedziesz wiedzial jak dobrze robisz optymalizacje?
Napisz kod ktory wykorzystuje Twoja (i inne procedury) przy przeksztalceniach
Pomierz (ale poprawnie) czasy i zuzycie procka
A potem gmeraj w kodzie i optymalizuj
Bez teorii i wywodow tutaj
Show the code or didnt happen
Jak mozesz porownywac dzialanie swoich modyfikacji procedury (nie mowiac o porownywaniu wzgledem innych) jak nie tobisz benchmarka? Skad wieez czy to co napisales dziala albo jak szybko dziala? Skad wiesz jak to wypada wzgledem innych procedur ktorych kod podano Ci tutaj
Skad bedziesz wiedzial jak dobrze robisz optymalizacje?
Napisz kod ktory wykorzystuje Twoja (i inne procedury) przy przeksztalceniach
Pomierz (ale poprawnie) czasy i zuzycie procka
A potem gmeraj w kodzie i optymalizuj
Bez teorii i wywodow tutaj
Show the code or didnt happen
13.11.2017 17:42
[#16]
Re: W temacie mojej procedury konwersji c2p
@Hexmage960, post #14
W c2p (tak jak zresztą w różnych przekształceniach) jest zawsze "coś za coś" i zabawa polega na znalezieniu optymalizacji, dzięki której koszt będzie jak najmniejszy.A ostatecznym weryfikatorem teorii jest zawsze eksperyment. Dopóki nie testujesz kodu wydajnościowo, pozostaje to miłą zabawą.
13.11.2017 17:43
[#17]
Re: W temacie mojej procedury konwersji c2p
@WojT_GL, post #15
Jak mozesz porownywac dzialanie swoich modyfikacji procedury (nie mowiac o porownywaniu wzgledem innych) jak nie tobisz benchmarka?
Na razie przygotowałem model teoretyczny. Ten ostatni można łatwo zaimplementować do właściwego kodu, co zamierzam uczynić. Następnie zrobię benchmarki.
Wtedy wyjdzie jak szybki jest mój algorytm i czy rzeczywiście szedłem dobrym tropem.
Skad wieez czy to co napisales dziala albo jak szybko dziala?
Działać, to działa na pewno, co przedstawiłem.
Z szybkością - tu wszystko zależy od tego, ile będzie kosztować skalowanie (wyszukiwanie binarne), bo operacja izolacji planów i łączenia kolejnych bloków jest operacją trywialną.Skad wiesz jak to wypada wzgledem innych procedur ktorych kod podano Ci tutaj
Jeżeli ktoś dysponuje testem to porównamy.
Skad bedziesz wiedzial jak dobrze robisz optymalizacje?
No cóż, to rzecz najtrudniejsza. Sam nie wiem jak daleko model mój i Kalmsa mają wpływ na szybkość wykonania.
Mam jednak wrażenie, że mój pomysł ze skalowaniem jest dość fajny i taki naturalny.
Będę publikował kod, podam wyniki testów i wspólnie zobaczymy gdzie można ulepszyć algorytm.
P.S. Pomyliłem się z tym rozmiarem tablicy - to będzie 256 poczwórnych słów, nie bajtów.
Ostatnia aktualizacja: 13.11.2017 17:47:55 przez Hexmage960
14.11.2017 13:34
[#18]
Re: W temacie mojej procedury konwersji c2p
@Hexmage960, post #17
No i wpadłem na pomysł, żeby skalowanie zrobić bez odnoszenia się do pamięci w zaledwie kilku prostych instrukcjach procesora (dwie instrukcje na bit) z wykorzystaniem dwóch rejestrów danych.
Ostatnia aktualizacja: 14.11.2017 13:35:27 przez Hexmage960
; d0: %a0000000b0000000c0000000d0000000 rol.l #4,d0 ; d0: %0000b0000000c0000000d0000000a000 move.b d0,d1 rol.l #7,d0 ; d0: %00000c0000000d0000000a0000000b00 or.b d0,d1 rol.l #7,d0 ; d0: %000000d0000000a0000000b0000000c0 or.b d0,d1 rol.l #7,d0 or.b d0,d1 ; d1: %0000000000000000000000000000abcd
Ostatnia aktualizacja: 14.11.2017 13:35:27 przez Hexmage960
07.12.2017 08:29
[#20]
Re: W temacie mojej procedury konwersji c2p
@Hexmage960, post #19
No więc napisałem nowe c2p, które jest super krótkie i działa naprawdę szybko. Jednak metoda operowania na całych 32-bitowych rejestrach jest lepsza, bo za jednym zamachem operuje na większej liczbie danych.
Ja zmieniłem troszkę kolejność składania bitów (najpierw 2 bity, później 8 bitów, następnie 1 bit i wreszcie 4 bity) i wyszło mi lepsze wykorzystanie rejestrów, jak i dużo mniej instrukcji.
Jest drobna usterka w kodzie, którą muszę poprawić. Poza tym postaram się teraz na poważnie przygotować procedurę testującą.
Poniżej cała procedura konwersji (bez zapisywania wyniku - w polach "gotowe"), która konwertuje 16 pikseli w 8 planach.
Ja zmieniłem troszkę kolejność składania bitów (najpierw 2 bity, później 8 bitów, następnie 1 bit i wreszcie 4 bity) i wyszło mi lepsze wykorzystanie rejestrów, jak i dużo mniej instrukcji.
Jest drobna usterka w kodzie, którą muszę poprawić. Poza tym postaram się teraz na poważnie przygotować procedurę testującą.
Poniżej cała procedura konwersji (bez zapisywania wyniku - w polach "gotowe"), która konwertuje 16 pikseli w 8 planach.
; Konwersja chunky-to-planar ; Właściwa konwersja c2p: ; Wejście: ; a0: bufor chunky ; a1: koniec bufora chunky ; a2: kopia struktury bitmapy ; Przygotowanie: move.l #$3333cccc,d7 ; maski move.l #$00ff00ff,d6 move.l #$55555555,a6 move.l #$0f0f0f0f,a5 ; Konwersja: ; etap 1: move.l (a0)+,d0 ; pobieramy 4 piksele chunky move.l d0,d1 ; kopia w d1 and.l d7,d0 eor.l d0,d1 lsr.w #2,d0 swap d0 lsl.w #2,d0 or.l d1,d0 move.l (a0)+,d1 ; pobieramy 4 piksele move.l d1,d2 and.l d7,d1 eor.l d1,d2 lsr.w #2,d1 swap d1 lsl.w #2,d1 or.l d2,d1 move.l (a0)+,d2 ; pobieramy 4 piksele move.l d2,d3 and.l d7,d2 eor.l d2,d3 lsr.w #2,d2 swap d2 lsl.w #2,d2 or.l d3,d2 move.l (a0)+,d3 ; pobieramy 4 piksele move.l d3,d4 and.l d7,d3 eor.l d3,d4 lsr.w #2,d3 swap d3 lsl.w #2,d3 or.l d4,d3 ; etap 2A: exg d7,a6 move.l d0,d4 move.l d2,d5 and.l d6,d0 and.l d6,d2 eor.l d0,d4 eor.l d2,d5 lsr.l #8,d5 lsl.l #8,d0 or.l d2,d0 or.l d5,d4 ; etap 3A: move.l d0,d2 move.l d4,d5 and.l d7,d0 and.l d7,d4 eor.l d0,d2 eor.l d4,d5 add.l d0,d0 lsr.l #1,d5 or.l d5,d2 or.l d4,d0 ; etap 2B: move.l d1,d4 move.l d3,d5 and.l d6,d1 and.l d6,d3 eor.l d1,d4 eor.l d3,d5 lsr.l #8,d5 lsl.l #8,d1 or.l d3,d1 or.l d5,d4 ; etap 3B: move.l d1,d3 move.l d4,d5 and.l d7,d1 and.l d7,d4 eor.l d1,d3 eor.l d4,d5 add.l d1,d1 lsr.l #1,d5 or.l d5,d3 or.l d4,d1 exg d7,a6 ; etap 4A: exg d7,a5 move.l d0,d4 move.l d1,d5 and.l d7,d0 and.l d7,d1 eor.l d0,d4 eor.l d1,d5 lsl.l #4,d0 lsr.l #4,d5 or.l d1,d0 or.l d5,d4 ; gotowe! ; etap 4B: move.l d2,d1 move.l d3,d5 and.l d7,d2 and.l d7,d3 eor.l d2,d1 eor.l d3,d5 lsl.l #4,d2 lsr.l #4,d5 or.l d3,d2 or.l d5,d1 ; gotowe! exg d7,a5 rts
07.12.2017 15:15
[#23]
Re: W temacie mojej procedury konwersji c2p
@Hexmage960, post #22
Namierzyłem poszukiwany błąd! Zabiorę się zatem za procedurę testującą (chyba zrobię w C dla wygody), jak i dopiszę zapis danych wyjściowych do pamięci.
Jak już to zrobię opublikuję pełny kod i wyniki testów.
Oto opis poprawek:
Jak już to zrobię opublikuję pełny kod i wyniki testów.
Oto opis poprawek:
; Poprawki do kodu ... add.l d4,d4 ; było add.l d0,d0 lsr.l #1,d2 ; było lsr.l #1,d5 ... add.l d4,d4 ; było add.l d1,d1 lsr.l #1,d3 ; było lsr.l #1,d5 ...
