[#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!
[#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
[#3] Re: W temacie mojej procedury konwersji c2p

@slay, post #2

Słusznie, mimo że nigdy nie robiłem efektów do dem, to myślę, że na 1-efektowe intro byłoby mnie stać. Muszę tylko ten efekt wymyślić. Się zobaczy. W tej chwili finalizuję pewien projekt na studia.

Ostatnia aktualizacja: 15.09.2017 15:38:13 przez Hexmage960
[#4] Re: W temacie mojej procedury konwersji c2p

@slay, post #2

Bardzo dobra podpowiedź- choćby jeden efekt z ocją verbose/ licznik FPS
[#5] Re: W temacie mojej procedury konwersji c2p

@BULI, post #4

... a ja przypomne, ze niedlugo RKLE i 2 amigowe konkursy exe oraz ze caly czas przyjmujemy prodki
[#6] Re: W temacie mojej procedury konwersji c2p

@mccnex, post #5

Mam pytanie: do kiedy przyjmujecie prodki?

@BULI

Całkiem dobry pomysł.

Ostatnia aktualizacja: 16.09.2017 19:56:28 przez Hexmage960
[#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:
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
[#8] Re: W temacie mojej procedury konwersji c2p

@Hexmage960, post #7

Mam nadzieję, że następnie wykorzystam tą procedurę w praktyce.


Przeczytaj ten wątek link, w załącznikach znajdziesz binarke z kodem źródłowym do testownia procedur C2P.
[#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
[#10] Re: W temacie mojej procedury konwersji c2p

@Hexmage960, post #9

Polecam jeszcze paczke z różnymi procedurami c2p link
[#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:
  • 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
[#12] Re: W temacie mojej procedury konwersji c2p

@Hexmage960, post #11

Nie zapomnij benczmarkować kolejnych swoich algorytmów ;)
[#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ć.
[#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. szeroki uśmiech

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.
[#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
[#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ą.
[#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
[#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.

; 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
[#19] Re: W temacie mojej procedury konwersji c2p

@Hexmage960, post #18

Napisałem c2p według tego pomysłu. Działa poprawnie, ale jest dość wolne. Widzę miejsca do poprawienia sytuacji.

Trzeba będzie to skalować większymi blokami.

Ostatnia aktualizacja: 15.11.2017 08:05:58 przez Hexmage960
[#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.

; 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
[#21] Re: W temacie mojej procedury konwersji c2p

@Hexmage960, post #20

To dalej teoria, czy już robiłeś testy "na żywo"?
[#22] Re: W temacie mojej procedury konwersji c2p

@SuperBuster, post #21

Nie teoria, bo procedura jest już zaprogramowana - podałem gotowy kod. Natomiast rzetelnych testów jeszcze nie przeprowadzałem, ale je zrobię. Najpierw tylko namierzę drobną usterkę i dorobię zapis wyniku do pamięci.
[#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:
; 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

	...
[#24] Re: W temacie mojej procedury konwersji c2p

@Hexmage960, post #23

Ok, trzymam kciuki OK
[#25] Re: W temacie mojej procedury konwersji c2p

@Hexmage960, post #22

Nie teoria, bo procedura jest już zaprogramowana - podałem gotowy kod.


Czyli to hipoteza
[#26] Re: W temacie mojej procedury konwersji c2p

@nogorg, post #25

Praktyka.
[#27] Re: W temacie mojej procedury konwersji c2p

@Hexmage960, post #26

Praktyką to będzie dopiero gdy procedurę przetestujesz i to w rzeczywistych warunkach bojowych.
[#28] Re: W temacie mojej procedury konwersji c2p

@nogorg, post #27

Ta a najlepiej na poligonie

[#29] Re: W temacie mojej procedury konwersji c2p

@nogorg, post #27

Jak najbardziej testuję w rzeczywistych warunkach bojowych. Kod piszę na prawdziwej Amidze. Mam Amigę z 1230/50MHz i 1260/50MHz.

Ostatnia aktualizacja: 07.12.2017 17:13:16 przez Hexmage960
[#30] Re: W temacie mojej procedury konwersji c2p

@Hexmage960, post #29

W takim razie zaprezentuj wyniki tych testów, bo określenie "szybko" jest mało miarodajne i ciężko do czegokolwiek porównać.
Na stronie www.PPA.pl, podobnie jak na wielu innych stronach internetowych, wykorzystywane są tzw. cookies (ciasteczka). Służą ona m.in. do tego, aby zalogować się na swoje konto, czy brać udział w ankietach. Ze względu na nowe regulacje prawne jesteśmy zobowiązani do poinformowania Cię o tym w wyraźniejszy niż dotychczas sposób. Dalsze korzystanie z naszej strony bez zmiany ustawień przeglądarki internetowej będzie oznaczać, że zgadzasz się na ich wykorzystywanie.
OK, rozumiem