Hejka! Po długim zastanawianiu się opracowałem interesujący format pikseli indeksowanych na Amidze.

Pozbawiony jest on wszystkich wad formatu Chunky, który bardzo trudno się konwertuje do postaci Planar.

Jednocześnie posiada on wszystkie zalety formatu Chunky i umożliwia mapowanie pikseli oraz dowolne inne funkcje na indeksach pikseli.

Ponadto ten nowy format można w banalny i błyskawiczny sposób przekonwertować zarówno do postaci Planar, jak i Chunky oraz na odwrót w razie potrzeby.

Jak przedstawia się ten format pikseli indeksowanych?

Otóż idea jest prosta. Format ten jest bardzo zbliżony do postaci Planar.

Obieramy sobie 256-elementową tablicę, bądź listę (nie wszystkie pola muszą być wykorzystywane), w której przechowujemy zestawy 32-bitowych liczb, gdzie każdy bit odpowiada za jeden piksel (podobnie jak w Planar), ale informuje on nas, czy na danej pozycji leży piksel o danym indeksie.

Wiemy zatem od razu, czy dany indeks/kolor piksela leży na danej pozycji.

Przykład:
Mamy 8 pikseli o wartościach:

0, 1, 2, 2, 5, 4, 3, 1

Teraz tworzymy tę tablicę.

tab[0] = %10000000 ; Położenie pikseli nr 0
tab[1] = %01000001 ; Położenie pikseli nr 1
tab[2] = %00110000 ; Położenie pikseli nr 2
tab[3] = %00000010 ; ...
tab[4] = %00000100 ; ...
tab[5] = %00001000 ; Położenie pikseli nr 5

Jak obliczyłem pesymistyczny koszt konwersji zestawu 32 pikseli w 8 bitplanach (kolory 0-255) z tej postaci (nazwijmy ją Index) do/z postaci Planar wynosi 64 operacje! Optymistyczny koszt zajmuje 1 operację! Koszt średni jest zatem niewielki. Wykorzystuje się ogromne możliwośći optymalizacyjne tej budowy.

Koszt do/z postaci Chunky jest niewielki, gdyż wiemy czy dany numer piksela leży na danej pozycji po 1 odczycie.

I co Wy na to? Jakieś pytania?

• Odpowiedz

@Hexmage960, post #1

• Odpowiedz

@Krashan, post #2

No i przyszedl imć PAN Kraszan i zadeptal kielkujace ziarno baobabu.

Z tego ziarna chleba nie bedzie

• Odpowiedz

@Krashan, post #2

Ten format jest przerażająco rozrzutny pod względem ilości zajmowanej pamięci. Weźmy linię w PAL LowRes (320 pikseli), w 256 kolorach. Przy zapisie bitplanowym każdy bitplan zajmie 40 bajtów, łącznie więc będziemy mieli 320 bajtów (8 bitplanów). W paletowym chunky wprost mamy 320 pikseli po 1 bajt każdy, czyli również 320 bajtów. W Twoim trybie każde 32 piksele zajmują 1 kB, zatem linia zajmuje 10 kB.

Dla typowego ekranu 320×256 w 256 kolorach mamy 80 kB danych zarówno dla planar jak i chunky, oraz 2560 kB (!!!) w Twoim trybie index.

Oczywiście ta tablica nie będzie nigdy zawierać 256 elementów, ale co najwyżej 32. Reszta będzie wyzerowana i nie brana pod uwagę, bo nie pomieści się więcej niż 32 różnych pikseli w 32 bitach.

Kwestia sposobu przechowania danych. Najbardziej narzuca się drzewo wyszukiwań binarnych, bo jest to bardziej dynamiczna struktura danych niż tablica, a wkładać elementy jest łatwo.

2. Zamiast rysować w trybie chunky, rysujemy od razu w trybie index, a potem konwersja index->planar jest szybsza niż chunky->planar. Postawienie piksela w chunky to jedno MOVE.B. Postawienie go w index, to operacja logiczna na pamięci (odczyt/modyfikacja/zapis). To może miałoby szansę być (wraz z konwersją) mimo wszystko szybsze niż tradycyjne C2P, gdyby nie ten prosty fakt, że procedura "I2P" będzie miała do odczytania z pamięci 32 razy więcej danych. To też trzeba uwzględnić w szacowaniu wydajności, a nie tylko liczbę operacji arytmetyczno-logicznych. A najlepiej po prostu zmierzyć.

Format Index ma spore możliwości optymalizacyjne.

Uwzględnia on to, że piksele mogą mieć wspólne bitplany. Jeżeli takie bitplany istnieją, to konwersja następuje raz dla takich wspólnych bitplanów.

W pesymistycznym przypadku i tak co najmniej 4 bitplany będą wspólne dla najbardziej zróżnicowanych 32 pikseli (bo jest max. 8 bitplanów).

Napisałem już fragment programu, który to testuje (najpierw konwertuje z tradycyjnego Chunky do Index, a następnie do Planar).

Także rzeczywiście taka tablica zajmuje dość sporo miejsca, ale jest to format bardzo bliski Planarnemu z jednoczesnymi cechami Chunky, bo wystarczy jeden zapis, by zapisać dowolny piksel (a nie 8 zapisów). I uwaga: w praktyce wystarczy jeden zapis by zapisać 32 piksele o tej samej wartości.

@Selur
Będzie z tego chleb, będzie. Pomysł jest przemyślany.

Ostatnia aktualizacja: 09.09.2018 17:36:32 przez Hexmage960

• Odpowiedz

@Hexmage960, post #4

• Odpowiedz

@Krashan, post #5

• Odpowiedz

@Hexmage960, post #6

• Odpowiedz

@Krashan, post #7

A moze by tak skompresowac drzewo binarne zipem i wrzucic do jpg'a ??

• Odpowiedz

@Krashan, post #7

• Odpowiedz

@Hexmage960, post #9

• Odpowiedz

@Hexmage960, post #9

• Odpowiedz

@Krashan, post #11

• Odpowiedz

@Hexmage960, post #12

Po prostu teoria teorią a dopiero w praktyce wyjdzie czy to będzie jakiś postęp czy nie.
Zawsze dobrze jest szukać nowych rozwiązań .

• Odpowiedz

@pisklak, post #13

Jako autor pomysłu może czasami widzę go w zbyt różowych barwach.

Zawsze dobrze jest szukać nowych rozwiązań szeroki uśmiech.

Dużo pracy zajęło mi opracowanie tego formatu i dlatego podkreślam jego zalety, ale nie oznacza to, że nie jestem otwarty na dyskusję. Myślę, że staram się odpowiadać na zagadnienia poruszane przez kolegów, w szczególności kolegi Krashana, który jest aktywny w wątku.

@Krashan

Ja pisałem o koszcie obliczeniowym postawienia piksela, który w przypadku użycia drzewa łatwo przekroczy koszt postawienia piksela bezpośrednio na ekranie planarnym. A to niweczy cały sens stosowania tego formatu i późniejszej konwersji I2P.

W przypadku drzewa jego głębokość to będzie max. 5 (przy 32 elementach zakładając zrównoważenie drzewa), przy czym może to być też tablica, którą sortuje się na bieżąco (koszt liniowo-logarytmiczny). Nie jest to duży koszt i podejrzewam, że wklejenie pikseli w tym formacie będzie efektywniejsze niż wklejanie bezpośrednio w formacie planarnym, ponieważ mój format dostarcza dokładnych informacji o wartości pikseli.

Oczywiście mój format może być też używany pomocniczo do struktury planarnej. Zresztą konwersję Planar -> Index zrobiłem w pierwszej kolejności i na tej podstawie opracowałem ten format.

Zrobimy później praktyczne testy, to będzie o czym dalej rozmawiać.

Ostatnia aktualizacja: 09.09.2018 21:02:46 przez Hexmage960

• Odpowiedz

@Hexmage960, post #12

• Odpowiedz

@Krashan, post #15

• Odpowiedz

@Krashan, post #15

• Odpowiedz

@recedent, post #16

To może odnośnie testów/benchmarków na początek procedura konwersji Planar -> Index, czyli odczyt pikseli.

Napisałem ją rekurencyjnie. Oczywiście można napisać też wersję iteracyjną, pomijając optymalizacje w asemblerze.

To jest tylko przykładowa implementacja.

Dane wejściowe to osiem 32-bitowych słów.
Dane wyjściowe to 256-elementowa tablica 32-bitowych słów.

http://coreprogramming.pl/Pixels/Planar2Index.txt

Celem testu jest wyznaczenie średniej złożoności czasowej i pamięciowej algorytmu, bo to podstawowe parametry algorytmu. Jeszcze nie chodzi o wyznaczenie czasu wykonania na MC680x0.

Przykładowe wyniki testu:

32 piksele o wartościach po kolei 0, 1, 2, 3, ..., 31 w 8 bitplanach.
Wywołania funkcji (operacje dominujące): 34 = 31 + 3 (31 to max. koszt dla 5 bitplanów + 3 to minimalny koszt dla 3 pozostałych bitplanów - bo w tym przypadku pozostałe bitplany są wyzerowane).

Minimalny koszt dla 8 bitplanów: 8 (bo taka jest wysokość drzewa).

Maksymalny koszt dla danych pesymistycznych można obliczyć.
Dla 1 bitplanu mamy koszt 1.
Dla 2 bitplanów mamy koszt (2*1)+1=3
Dla 3 bitplanów mamy koszt (2*3)+1=7
Dla 4 bitplanów - koszt (2*7)+1=15
Dla 5 bitplanów - koszt (2*15)+1=31
Dla 6 bitplanów piksele mogą się już powtarzać. Dodajemy zatem stały koszt 32. Max. koszt 31+32 = 63
Dla 7 bitplanów - 63+32 = 95
Dla 8 bitplanów - 95+32 = 127

Uważam, że jest to niezły wynik. Gdy wszystkie 32 piksele są takie same (np. tło - wynik to 8 wywołań/iteracji). Dla losowych danych należy uśrednić koszt.

Ważne:
Gdy wiemy, że piksele należą do pewnego przedziału (parametry min, max) albo chcemy wyodrębnić wybrane piksele spośród tej puli 32 pikseli (parametr mask) - koszt jest odpowiednio niższy. Gdy piksele współdzielą bitplany, również koszt jest odpowiednio niższy.

Ta struktura danych daje duże możliwości optymalizacji, jak również można wykorzystać Blitter do operacji na niej.

W kolejności porobię Index -> Planar, ale to nieco później, bo dziś będę zajęty.

Ostatnia aktualizacja: 10.09.2018 05:56:39 przez Hexmage960

• Odpowiedz

@Krashan, post #15

Hej,

Krashan, do tej Twojej wypowiedzi się jeszcze odniosę.

Przy czym opracowałem już konwersję Chunky-Planar z użyciem postaci przejściowej INDEX.

Oto tak się ona przedstawia. Jest ona bardzo prosta i składa się z ... dwóch kroków mapowania.

Weźmy 32-piksele.

KROK 1: Mapujemy kolejne piksele do tablicy 256-elementowej INDEX używając numeru piksela jako indeksu. Koszt zależy liniowo od liczby pikseli i wynosi 32.

KROK 2: Ponownie mapujemy kolejne piksele tym razem jednak biorąc pod uwagę bitplany, z których się składają. Wykorzystujemy 8-elementową tablicę docelowych danych planarnych dla bitplanów. Po prostu pobieramy odpowiednią dla tego piksela wartość z tablicy INDEX, a następnie wykonujemy operację logiczną OR dla wszystkich bitplanów, które ten piksel obejmuje.

Koszt kroku nr 2 to suma liczby bitplanów zajmowanych przez wszystkie różne piksele. Być może da się to jeszcze zoptymalizować pod kątem wspólnych bitplanów (czyli lepiej wykorzystując podobieństwo pikseli), ale na razie nie mam do tego głowy.

Po wykonaniu kroku drugiego w tej 8-elementowej tablicy już znajdują się dane planarne do wklejenia.

• Odpowiedz

@Hexmage960, post #19

• Odpowiedz

@Krashan, post #20

I w ten oto sposób będziesz miał 8 odczytów długich słów z pamięci na każdy piksel (tablica INDEX w kroku 2). Samo to zniszczy ten kod wydajnościowo.

8 odczytów na każdy piksel? A skąd to wziąłeś? Jest tylko jeden odczyt na piksel. W tym polu znajduje się już pełna informacja o tym, gdzie piksele o tej wartości się znajdują.

Ponadto (zapomniałem dodać), w drugim kroku bierzemy pod uwagę tylko piksele niepowtarzające się, przygotowane po kroku pierwszym.

Ostatnia aktualizacja: 12.09.2018 17:46:08 przez Hexmage960

• Odpowiedz

@Hexmage960, post #21

• Odpowiedz

@Krashan, post #22

• Odpowiedz

@Hexmage960, post #23

To już brzmi lepiej. Teraz zaczniesz optymalizować zauważając, że można uniknąć tych pomocniczych tablic umieszczając je w rejestrach procesora i... dojdziesz do klasycznego algorytmu C2P. Idę o zakład, że nie pobijesz szybkościowo np. tych procedur: https://github.com/Kalmalyzer/kalms-c2p.

• Odpowiedz

@Krashan, post #24

• Odpowiedz

@Hexmage960, post #25

Zatem po wielu przemyśleniach i analizach, doszedłem do całkiem ciekawej konkluzji.

Otóż udało mi się zoptymalizować algorytm pod kątem podobieństwa pikseli ze względu na wspólne bitplany. Najwięcej korzystają z tego piksele o indeksach z dużą liczbą jedynek (czyli o dużej wadze), czyli tak jak być powinno.

Przyznam, że nie było to zadanie proste. Opracowałem kilka nieefektywnych algorytmów po drodze.

Oto jak się przedstawia mój algorytm C2P z użyciem przejściowej postaci Index, w praktyce o koszcie min. O(n), max. O(n*log(k)) względem liczby pikseli (n) i bitplanów (k). A im piksele bardziej podobne, tym algorytm szybszy.

Przykładowo dla pikseli 255, 254, 253, 252, .... itd. koszt nie będzie wynosić ~32*8 jak dotychczas, ale ~32*3.

Dla 32 identycznych pikseli koszt to ~32.

Na początek przygotowania:

• potrzebujemy tablicę 256-elementową INDEX, która przechowuje wartość wagi dla danego indeksu (liczba z zakresu od 0 do 7) oraz dane planarne typu INDEX o długości długiego słowa.
• W tablicy INDEX przechowujemy również sekwencję max. 8-elementową liczb uporządkowanych rosnąco z zakresu od 0 do 7 opisującą z jakich bitplanów składa się dany indeks. Jest to tablica pre-kalkulowana. Nazwijmy ją BITPLANY.
• Potrzebujemy również 8 tablic o rozmiarze 32 bajty każda, gdzie będziemy przechowywać różne wartości pikseli według wag. Maksymalnie we wszystkich 8 tablicach łącznie będą 32 elementy. Nazwijmy ją WAGI.

KROK 1.
Mapujemy piksele typu Chunky w ten sposób, że wstawiamy (operacja OR) do tablicy 256-elementowej o indeksie określonym przez ten piksel bit zapalony na pozycji, gdzie dany piksel się znajduje w 32-pikselowym bloku (koszt jednostkowy). Pikseli o wartości 0 nie bierzemy pod uwagę.

Jeżeli piksel się nie powtórzył (sprawdzenie to koszt jednostkowy), to dodatkowo liczymy wagę dla danego indeksu pobierając odpowiednią wartość z tablicy (koszt jednostkowy). A następnie dopisujemy go do tej tablicy złożonej z ciągów pikseli o tej samej wadze (koszt jednostkowy) w tablicy WAGI.

KROK 2.
Ten krok polega na scaleniu elementów tablicy BITPLANY dot. pikseli obecnych w 32-pikselowym bloku. Ponieważ składa się ona z ciągów posortowanych rosnąco scalenie jest stosunkowo proste (i ma koszt liniowy względem sumarycznej liczby elementów).

My jednak zrobimy fajną rzecz. Otóż uprościmy i przyśpieszymy zadanie scalenia, gdyż wartości są z zakresu od 0 do 7. Otóż dla pikseli o tych samych wagach przeprowadzimy operację koniunkcji AND. Dostaniemy wówczas nowy indeks, który opisuje bitplany wspólne, czyli te które w scalonej tablicy by się powtórzyły. Liczymy oczywiście następnie różnicę symetryczną EOR względem tych pikseli i otrzymujemy kolejne indeksy.

Teraz suma elementów tablic do scalenia będzie mniejsza, szczególnie dla dużych wag i bitplanów wspólnych. Zatem koszt scalenia będzie mniejszy.

Po scaleniu (z eliminacją elementów jednakowych) otrzymamy max. 8-elementową tablicę z danymi planarnymi oraz informacją gdzie je wklejać.

Ufff.... Trochę mi to zajęło pracy. Tak że wystarczy w zupełności. W tym temacie zaimplementuję później ten algorytm w C lub Asm, ale na razie nie będę się tym już zajmował.

Bardzo bym się cieszył, gdyby ten algorytm okazał się szybszy niż tradycyjne.

Jeśli ktoś ma jakieś pytania, bądź uwagi, niech pisze śmiało.

• Odpowiedz

@Hexmage960, post #26

• Odpowiedz

@swinkamor12, post #27

Daj spokój, niech robi jak sprawia mu to frajdę.

• Odpowiedz

@swinkamor12, post #27

• Odpowiedz

@Hexmage960, post #29

Hej,

Okazuje się to temat bardzo żywy i elastyczny. Właśnie opracowałem pewną wariację tego algorytmu. Udało mi się rozszerzyć tą strukturę danych (INDEX) o pokrewne.

Otóż zauważmy, że można indeksować również nibble (4-bitowe słowa). Wówczas tablica INDEX-4 będzie składać się z 16 (15) elementów, gdzie każdy element to dwa słowa. Podobnie można stworzyć tablicę INDEX-2 składającą się z 4 (3) elementów, gdzie każdy element to cztery słowa oraz PLANAR składającą się z 2 (1) elementów, gdzie każdy element to osiem słów w docelowej formie planarnej. Liczba w nawiasie oznacza, że nie uwzględniamy pikseli (wartości) 0.

Zatem mapujemy CHUNKY na INDEX-4, potem z INDEX-4 na INDEX-2 i z INDEX-2 na PLANAR.

Teraz najlepsze: koszt. Oczywiście algorytm nadal korzysta z optymalizacji (rozpatrujemy tylko różne dane), a jest dużo prostszy co opisany wcześniej.

Otóż jak mamy piksele: $00, $01, $02, $03, $03, ..., $1F, to wówczas:
Koszt CHUNKY -> INDEX-4 to 32 operacje.

INDEX-4:

$0: $ffff0000, $80008000
$1: $0000ffff, $40004000
$2: $00000000, $20002000
$3: $00000000, $10001000
$4: $00000000, $08000800
$5: $00000000, $04000400
$6: $00000000, $02000200
$7: $00000000, $01000100
$8: $00000000, $00800080
$9: $00000000, $00400040
$A: $00000000, $00200020
$B: $00000000, $00100010
$C: $00000000, $00080008
$D: $00000000, $00040004
$E: $00000000, $00020002
$F: $00000000, $00010001

Koszt INDEX-4 -> INDEX-2 to 18 operacji.
Koszt INDEX-2 -> PLANAR to ?? operacji. Jeszcze nie obliczyłem, ale wiem że będzie niewiele.

Sumarycznie to nawet nie przekroczy 64 operacji!

Gra była warta świeczki. Format INDEX pomoże.

Ostatnia aktualizacja: 16.09.2018 15:05:48 przez Hexmage960

• Odpowiedz