|
|
|
| PROGRAMOWANIE | |
|
FRAKTALE MANDELBROTA W ASSEMBLERZE |
Jak obiecałem, tak zrobiłem Mandelbrota w assemblerze - jestem zawiedziony, ponieważ rysuje się on aż 20 minut! :-( I nie ma tu takiego przełożenia, jak z trójkątem Sierpińskiego. Cóż, gdyby mnożenie było bez znaku i dwóch liczb ośmiobitowych, byłoby z 10 razy szybciej, a tutaj trzeba operować czasami na 32-bitowych signed integerach, czasami 24... Gdyby...
Jako punkt wyjścia posłużył mi program Przemysława Cieślaka z C&A 1995/04 str. 16/17 'FRAKTALE ZBIÓR MANDELBROTA'. Ponieważ okazało się, że bardziej pamiętam assembler PC niż Amigi - to ku mojemu szczęściu znalazłem ten program przerobiony na PC przez Tomasza Łąckiego. Był on bardzo podobny i nie używał koprocesora. Kolejnym ułatwieniem jest codebase C64 i Seriously fast multiplication (8-bit and 16-bit). To genialny sposób na szybkie mnożenie przy użyciu tablic kwadratów wymyślony przez genialnego George'a Taylor'a. Dołożył się do tego Jackasser, który skrócił rozmiar tablic. Przy okazji podziękowania właśnie dla tych czterech osób oraz dodatkowo dla Oswald'a, który objaśniał mi zasadę działanie tej metody - tak, więc Przemysław Cieślak, Tomasz Łącki, George Taylor, Jackasser, Oswald - mega THX! :-)
Teoria jest w wątku Fraktale w BASIC'u i nie będę jej powtarzał - przechodzę do programowania - na początek wycinek odpowiedzialny za liczenie fraktala (PC code):
[...]
pozx dw 0
pozy dw 0
x dw 0
y dw 0
la dd 0
lb dd 0
startx dd -618*256
starty dd -324*256
zla dw 768
zlb dw 791
paramx db 0
paramy db 0
;-----------------------liczenie fraktala
rysuj:
lea si,la
lea di,startx
mov eax,ds:[di]
mov [si],eax ;zmniejszenie - idzemy w prawo
;rysunek przesuwa sie w lewo
nexti:
lea si,lb
lea di,starty
mov eax,ds:[di]
mov [si],eax ;zmniejszenie - idziemy w dol
lea si,pozy ;rysunek przesuwa sie do gory
mov dword ptr[si],0
nextj:
xor ax,ax
lea si,x
lea di,paramx
mov al,ds:[di] ;pobierz paramx
mov word ptr [si],ax ;ustaw paramx
mov al,ds:[di+1] ;pobierz paramy
mov word ptr [si+2],ax ;ustaw paramy
mov cx,IloscPowtorzen
spr:
;push cx
;podnies x do kwadratu
dec cx
jz br
xor eax,eax
xor ebx,ebx
xor edx,edx
mov ax,[si] ;w ax - x
imul ax ; |
mov bx,ax ; |
mov ax,dx ; |
shl eax,16 ; |
or eax,ebx ; V
push eax ;x^2 - caly 32bit wynik w eax
;podnies y do kwadratu
xor ebx,ebx
xor edx,edx
xor eax,eax
mov ax,[si+2] ;w ax - y
imul ax ; |
mov bx,ax ; |
mov ax,dx ; |
shl eax,16 ; V
or eax,ebx ;y^2 - caly 32bit wynik w eax
mov ebx,eax ;w ebx - y^2
pop eax ;w eax - x^2
sub eax,ebx ;x^2-y^2
xor edx,edx
add eax,[si+4] ;x^2-y^2+la
shr eax,8 ;-
push eax ;zapamietaj x
xor eax,eax
xor ebx,ebx
xor edx,edx
mov ax,[si] ;w ax - x
mov bx,[si+2] ;w bx - y
imul bx ;y*x
xor ebx,ebx
mov bx,dx
shl ebx,16
or ebx,eax ;y*x - caly wynik z DX:AX w EBX
add ebx,ebx ;2*y*x
xor edx,edx
add ebx,[si+8] ;2*x*y+lb
shr ebx,8 ;-
mov [si+2],bx ;y=2*x*y+lb
pop eax
mov [si],ax ;x=x^2-y^2+la
push ebx ;zapamietaj y
;----------------------------podnies x do kwadratu
xor ebx,ebx ;najpirw zap. ebx potem wyzeruj
xor edx,edx ;potrzebne rejestry
imul ax ;x^2 - mnozenie ze znakiem
mov bx,ax ;mlodsze slowo do bx (wynik jest w DX:AX)
xor eax,eax ;wyzeruj eax
mov ax,dx ;
shl eax,16 ;dx do eax - starsze slowo wyniku
or eax,ebx ;bx do ax - mlodsze slowo wyniku
pop ebx ;odtworz y
push eax ;zapamieteaj x
xor eax,eax ;podnies y do kwadratu
xor edx,edx ;
mov eax,ebx ;y do eax
imul ax ;y^2
xor ebx,ebx
mov bx,ax ;mlodsze slowo wyniku do bx
xor eax,eax
mov ax,dx
shl eax,16 ;dx do eax - starsze slowo wyniku
or eax,ebx ;bx do ax - mlodsze slowo wyniku
mov ebx,eax ;caly wynik y^2 do ebx
pop eax ;odtworz x
add eax,ebx ;|Z|=sqrt(x^2+y^2)
shr eax,8 ;podziel |Z| przez 256
cmp ax,1024 ;-------------sprawdz warunek
jl spr
;pop cx
;-dec cx
;-jnz spr
;loop spr
br:
;brdalej:
;------
;retu:
lea si,pozx
mov bx,[si] ;w bx pozx
mov dx,[si+2] ;w dx pozy
;postaw punkt
shl dx,6
add bx,dx
shl dx,2
add bx,dx
mov es:[bx],cl ;postaw punkt x,y,al - kolor
;nastepna pozycja
lea si,lb
lea di,zlb
xor eax,eax
mov ax,ds:[di]
add dword ptr[si],eax ;-------------zwieksz licznik b
;zy ESC
in al,60h
cmp al,1
je wyjscie
;
lea si,pozy
add word ptr[si],1
cmp word ptr[si],200
jne nextj
lea si,la
lea di,zla
xor eax,eax
mov ax,ds:[di]
add dword ptr[si],eax ;-------------zwieksz licznik a
lea si,pozx
add word ptr[si],1
cmp word ptr[si],320
jne nexti
[...]
Teraz garść wyjaśnień - widać tu np. dzielenie przez 256 32-bitowego integera, więc w kodzie na C64 darowałem sobie 8-krotne (!) rolowanie czterech bajtów tylko po prostu odwoływałem się do drugiego bajtu 32-bit integer'a. Teraz spójrzmy na to:
shr eax,8 ;podziel |Z| przez 256
cmp ax,1024 ;-------------sprawdz warunek
jl spr
a więc mamy tutaj dzielenie i sprawdzenie 16-bitowej liczby i widać, że najstarsze 8 bitów jest 'obcinane' - z tego skorzystałem pisząc to na C64 - KAŻDY CYKL SIĘ LICZY! EAX jest przesuwany o 8 bitów, co daje z 32 zmniejszenie do 24 bitów, a następnie sprawdzana jest zawartość AX 16bitów! (KOLEJNE OBCIĘCIE!). Idźmy dalej wartość 1024 jest 16-bitowa i szesnastkowo wynosi ona $0400 - młodszy bajt #$00 starszy #$04. Sprawdzenie warunku jest większe LUB równe 1024 zatem wystarczy sprawdzać tylko starszy bajt, czy jest większy lub równy 4! Jak się nie ma 16-bitowych rejestrów i każdy cykl się liczy, to trzeba kombinować :-) Jest to żywy przykład dla Tomaaz'a - nadal utrzymuję, że programowanie na PC jest łatwiejsze niż 'gimnastykowanie się' na C64, gdzie do dyspozycji raptem są 3 8-bitowe rejestry bez rozkazów dzielenia i mnożenia. Z resztą, co mi po 8-bitowych rozkazach, jak potrzebuję SIGNED 16BIT z wynikiem SIGNED 32BIT!
Jeszcze jedno - przy obliczaniu Z podnosimy X i Y do kwadratu - marnotrastwem byłoby nie wykorzystanie tego przy kolejnej iteracji i ponowne potęgowanie - w wersji na C64 chętnie tak zrobiłem...
Teraz programy na C64 - nie są one napisane super optymalnie i zapewne mają wiele niedociągnięć, natomiast jakoś rysują ten zbiorek ;-) Można by napisać to 'ciurkiem' i pozbyć się JSR'ów, co obniżyłoby przejrzystość. Dzięki temu widać jak działa algorytm.
Pierwszy program nie używa sztuczek z ignorowaniem obcinanych końcówek, drugi jest bardziej zoptymalizowany i tą wersję poniżej zamieszczam. Trzeci jest z muzyką Tracker'a, aby nam się nie nudziło w oczekiwaniu na fraktal :-)
*= $0801
;--------
;FOR SPECIAL WISH
;FROM POLISH FORUM C64.PHORUM.PL
; (C) BY WEGI IN 2010.01.03
;--------
.BYTE $0B,$08,$90,$06,$9E,$32
.BYTE $30,$34,$39,$00,$A0,$00
;--------
WY = $D1
STOREPLOT = $D3
SCREEN = $2000
;---
SQUARE1LO = $4000
SQUARE1HI = $4200
SQUARE2LO = $4400
SQUARE2HI = $4600
;---
SEI
CLD
LDX #$FB
TXS
LDA #$37
STA $01
JSR $FDA3
JSR $FF5B
JSR SETTBADR
JSR GENTAB
;---
DRAW
SEI
JSR INITGRAPH
JSR FRAJDA
CLI
JSR $FFE4
BEQ *-3
LDA #$00
STA $C6
JMP DRAW
;-----
BIT32S
;-----
;--------
;THX 2 GEORGE TYLOR, JACKASSER, OSWALD
;FOR SHARING & EXPLAINED SERIOUSLY FAST
;MULTIPLICATION
;CODEBASE C64 RULES! :)
;--------
INC $D020 ;BLINK FOR YOU CAN
JSR BIT32U ;SEE HOW WORK MULT.
LDA T1+1
BPL DALEJ3
SEC
LDA PRODUCT+2
SBC T2
STA PRODUCT+2
LDA PRODUCT+3
SBC T2+1
STA PRODUCT+3
DALEJ3
LDA T2+1
BPL DALEJ4
SEC
LDA PRODUCT+2
SBC T1
STA PRODUCT+2
LDA PRODUCT+3
SBC T1+1
STA PRODUCT+3
DALEJ4
DEC $D020
RTS
;--------
BIT32U
LDA T1
STA SM1A+1
STA SM3A+1
STA SM5A+1
STA SM7A+1
EOR #$FF
STA SM2A+1
STA SM4A+1
STA SM6A+1
STA SM8A+1
LDA T1+1
STA SM1B+1
STA SM3B+1
STA SM5B+1
STA SM7B+1
EOR #$FF
STA SM2B+1
STA SM4B+1
STA SM6B+1
STA SM8B+1
LDX T2
SEC
SM1A LDA SQUARE1LO,X
SM2A SBC SQUARE2LO,X
STA PRODUCT
SM3A LDA SQUARE1HI,X
SM4A SBC SQUARE2HI,X
STA DAT1+1
SEC
SM1B LDA SQUARE1LO,X
SM2B SBC SQUARE2LO,X
STA DAT5+1
SM3B LDA SQUARE1HI,X
SM4B SBC SQUARE2HI,X
STA DAT4+1
LDX T2+1
SEC
SM5A LDA SQUARE1LO,X
SM6A SBC SQUARE2LO,X
STA DAT2+1
SM7A LDA SQUARE1HI,X
SM8A SBC SQUARE2HI,X
STA DAT3+1
SEC
SM5B LDA SQUARE1LO,X
SM6B SBC SQUARE2LO,X
STA DAT6+1
SM7B LDA SQUARE1HI,X
SM8B SBC SQUARE2HI,X
STA PRODUCT+3
;------
CLC
DAT1 LDA #$00
DAT2 ADC #$00
STA PRODUCT+1
DAT3 LDA #$00
DAT4 ADC #$00
STA PRODUCT+2
BCC DALEJ1
INC PRODUCT+3
CLC
DALEJ1
DAT5 LDA #$00
ADC PRODUCT+1
STA PRODUCT+1
DAT6 LDA #$00
ADC PRODUCT+2
STA PRODUCT+2
BCC DALEJ2
INC PRODUCT+3
DALEJ2
RTS
;--------
GENTAB
LDA #>SQUARE1HI
STA ML1+2
LDA #>SQUARE1LO
STA ML0+2
LDX #$00
STX ML9+1
TXA
.BYTE $C9
;---
LB1
TYA
ADC #$00
ML1
STA SQUARE1HI,X
TAY
CMP #$40
TXA
ROR A
ML9
ADC #$00
STA ML9+1
INX
ML0
STA SQUARE1LO,X
BNE LB1
INC ML0+2
INC ML1+2
CLC
INY
BNE LB1
LDX #$00
LDY #$FF
;---
JACK
;GREAT IDEA OF JACKASSER/INSTINCT
;---
LDA SQUARE1HI+1,X
STA SQUARE2HI+$0100,X
LDA SQUARE1HI,X
STA SQUARE2HI,Y
LDA SQUARE1LO+1,X
STA SQUARE2LO+$0100,X
LDA SQUARE1LO,X
STA SQUARE2LO,Y
DEY
INX
BNE JACK
RTS
;---
;--------
INITGRAPH
;LINES 5 - 90 FROM TOMAAZ BASIC
; LDA #$06
; STA 53280
LDA 53272
ORA #$08
STA 53272
LDA 53265
ORA #32
STA 53265
LDX #$00
LDA #246
FILL1
STA $0400,X
STA $0500,X
STA $0600,X
STA $06F8,X
INX
BNE FILL1
LDX #$20
STX $FC
LDY #$00
STY $FB
LDA #$FF
FILL2 STA ($FB),Y
INY
BNE FILL2
INC $FC
DEX
BNE FILL2
RTS
SETTBADR
LDX #$00
LDA #>SCREEN
STX $FB
STA $FC
SETTB2
LDA $FB
STA TBADLO,X
LDA $FC
STA TBADHI,X
LDA $FB
CLC
ADC #$40
STA $FB
LDA $FC
ADC #$01
STA $FC
INX
CPX #25
BCC SETTB2
RTS
;--------
TBBIT
.BYTE %10000000
.BYTE %01000000
.BYTE %00100000
.BYTE %00010000
.BYTE %00001000
.BYTE %00000100
.BYTE %00000010
.BYTE %00000001
;---
TBADLO
.BYTE 0,0,0,0,0
.BYTE 0,0,0,0,0
.BYTE 0,0,0,0,0
.BYTE 0,0,0,0,0
.BYTE 0,0,0,0,0
;---
TBADHI
.BYTE 0,0,0,0,0
.BYTE 0,0,0,0,0
.BYTE 0,0,0,0,0
.BYTE 0,0,0,0,0
.BYTE 0,0,0,0,0
;--------
;---------------------------------------
T1 .BYTE 0,0
T2 .BYTE 0,0
PRODUCT .BYTE 0,0,0,0
;---------------------------------------
;--------
;--------
;STARTX = (-618)*256 = $FFFD9600
;STARTY = (-324)*256 = $FFFEBC00
;ZLA = 768 = $0300
;ZLB = 791 = $0317
STARTX .BYTE $00,$96,$FD,$FF
STARTY .BYTE $00,$BC,$FE,$FF
ZLA .BYTE $00,$03
ZLB .BYTE $17,$03
LA .BYTE 0,0,0,0
LB .BYTE 0,0,0,0
POZX .BYTE 0,0
POZY .BYTE 0,0
PARAMX .BYTE $00,$00
PARAMY .BYTE $00,$00
X1 .BYTE $00,$00
Y1 .BYTE $00,$00
X2 .BYTE 0,0,0,0
Y2 .BYTE 0,0,0,0
X3 .BYTE 0,0,0,0
Y3 .BYTE 0,0,0,0
;--------
;--------
;-- X * X = X^2
XSQUARE
LDA X1
STA T1
STA T2
LDA X1+1
STA T1+1
STA T2+1
JSR BIT32S
;--
;--------
;-- RESULT TO X3
RES2X3
LDX #$03
LDA PRODUCT,X
STA X3,X
DEX
BPL *-7
RTS
;--
;--------
;-- Y * Y -> Y^2
YSQUARE
LDA Y1
STA T1
STA T2
LDA Y1+1
STA T1+1
STA T2+1
JSR BIT32S
;--
;--------
;-- RESULT TO Y3
RES2Y3
LDX #$03
LDA PRODUCT,X
STA Y3,X
DEX
BPL *-7
RTS
;--
;--------
;-- X2 = X^2 - Y^2 + LA
X3SUBY3
SEC
LDA X3
SBC Y3
STA X2
LDA X3+1
SBC Y3+1
STA X2+1
LDA X3+2
SBC Y3+2
STA X2+2
LDA X3+3
SBC Y3+3
STA X2+3
CLC
LDA X2
ADC LA
LDA X2+1
ADC LA+1
STA X2+1
LDA X2+2
ADC LA+2
STA X2+2
RTS
;--
;--------
;-- Y2 = Y * X * 2 + LB
MULXY
LDA X1
STA T1
LDA X1+1
STA T1+1
;IF LAST WAS Y^2 SO DO NOT
;MUST SET Y TO T2
JSR BIT32S
;Y*X*2 -> PRODUCT * 2 (24BIT)
LDA PRODUCT
ASL A
ROL PRODUCT+1
ROL PRODUCT+2
;ENOUGHT 24BIT
;ROL PRODUCT+3
;INA ACC LOWEST BYTE*2
;OF PRODUCT
CLC
ADC LB
;WITHOUT STORE ONLY CHECK CARRY!
;COS RESULT IN BIT 8 TO 23!
;DIVIDE 256 - CLEAR?
;-- Y = (Y * X * 2 + LB)/256
;NOWEY - NEWY!!! HERE
;--
LDA PRODUCT+1
ADC LB+1
STA Y1
LDA PRODUCT+2
ADC LB+2
STA Y1+1
;--
;--------
;-- X = (X^2 - Y^2 + LA)/256
;BELOW NEWX !!!
NOWEX
LDA X2+1
STA X1
LDA X2+2
STA X1+1
RTS
;--
;--------
;-- (X^2 + Y^2)/256/256
SUMSQUARE
JSR XSQUARE
JSR YSQUARE
CLC
LDA X3
ADC Y3
LDA X3+1
ADC Y3+1
LDA X3+2
ADC Y3+2
;ONE MORE TIME DIV 256
;SO NO CHECK >= 1024 ($0400)
;ONLY HIBYTE >= 4 ($0400)
;CLEAR??
CMP #$04
;CARRY IS FLAG
;IF CARRY IS SET SO Z^2+C
;IS RAISING UP!!
RTS
;--
;--------
;-- STARTX DO LA
LOADLA
LDX #$03
LDA STARTX,X
STA LA,X
DEX
BPL *-7
RTS
;--
;--------
;-- STARTX DO LB
LOADLB
LDX #$03
LDA STARTY,X
STA LB,X
DEX
BPL *-7
RTS
;--
;--------
;--
ZERUJPOZX
LDA #$00
STA POZX
STA POZX+1
RTS
;--
ZERUJPOZY
LDA #$00
STA POZY
STA POZY+1
RTS
;--
;--------
;-- LB = LB + ZLB
PLUSLB
CLC
LDA ZLB
ADC LB
STA LB
LDA ZLB+1
ADC LB+1
STA LB+1
LDA LB+2
ADC #$00
STA LB+2
LDA LB+3
ADC #$00
STA LB+3
RTS
;--
;--------
;-- LA = LA + ZLA
PLUSLA
CLC
LDA ZLA
ADC LA
STA LA
LDA ZLA+1
ADC LA+1
STA LA+1
LDA LA+2
ADC #$00
STA LA+2
LDA LA+3
ADC #$00
STA LA+3
RTS
;--
;--------
;-- X = PARAMX ; Y = PARAMY
STPRMS
LDA PARAMX
STA X1
LDA PARAMX+1
STA X1+1
LDA PARAMY
STA Y1
LDA PARAMY+1
STA Y1+1
RTS
;--
;--------
;--
;---------------------------------------
MYFRAC
LDA #51
STA ITERATOR
JSR XSQUARE
JSR YSQUARE
MYFRAC2
DEC ITERATOR
;IF NO RAISING UP - DRAW
;MANDELBROT FILE
BEQ STAWPLOT
JSR X3SUBY3
JSR MULXY
JSR SUMSQUARE
;AFTER SUMSQUARE X*X AND Y*Y
;WAS CALCULATED SO WE DO NOT
;MUST AGAIN JSR XSQUARE AND
;JSR YSQUARE
PHP
;SAVE CARRY
JSR STAWPLOT
PLP
;RESTORE CARRY
;WITHOUT XSQUARE AND YSQUARE
;BEFORE EXPLAINED WHY - IT IS NOT?
BCC MYFRAC2
;RAISING UP - THE END OF POINT
;ITERATION
RTS
STAWPLOT
LDA POZY
LSR A
LSR A
LSR A
TAX
LDA POZY
AND #$07
TAY
LDA POZX
AND #$F8
CLC
ADC TBADLO,X
STA STOREPLOT
LDA TBADHI,X
ADC POZX+1
STA STOREPLOT+1
LDA POZX
AND #$07
TAX
LDA (STOREPLOT),Y
EOR TBBIT,X
STA (STOREPLOT),Y
RTS
;--------
ITERATOR .BYTE 0
;---------------------------------------
FRAJDA
JSR ZERUJPOZX
JSR LOADLA
NEXTI
JSR LOADLB
JSR ZERUJPOZY
NEXTJ
JSR STPRMS
JSR MYFRAC
JSR PLUSLB
INC POZY
LDA POZY
CMP #200
BNE NEXTJ
JSR PLUSLA
INC POZX
BNE TRYFRAK
INC POZX+1
TRYFRAK
LDA POZX+1
BEQ NEXTI
LDA POZX
CMP #$40
BNE NEXTI
;X = 320 ($0140) - THE END!
;--------
;- ALL DONE :)
RTS
;-------
Takie są efekty działania programu.
Pobrać można go tutaj: mandelbrot.zip (90kB).
Jeżeli chodzi o pokolorowanie fraktala... ponieważ musiałem zająć się teorią, to pokolorowanie zostawiam do własnej przeróbki. A naszą wersję obiecał pokolorować spec od trybów graficznych Michał VEL Skull - powodzenia!
P.S. Można rysować mniejsze fraktale - wówczas nie zajmie to tyle czasu - trzeba wtedy również kontrolować max pozycje X i Y, aby nie liczyć obszaru poza zbiorem...
Autor:
Data realizacji:
Data publikacji:
Data modyfikacji:
Pierwsza publikacja:
|
|
Mr Wegi (Black Sun/Fatum/Samar Productions)
1.2010
12.1.2010
-
Filety on-line
|
|
#1 | Dzień 7-12-2010 | godz.07:35:47 | Autor: Komentarz testowy | Status: Brak błędów | AdrIP: Ukryty | Fajny artyluł:D! |
|
Instrukcja używania systemu komentarzy
- W polu "Podpisz się" umieszczasz swoje Imię, Nazwisko albo Pseudonim używając znaków alfanumerycznych: A-Z, 0-9 oraz znaków specjalnych, np.: !^<>" ' itp.
Tagi HTML są nieaktywne.
- W polu "Wpisz treść" umieszczasz komentarz używając znaków alfanumerycznych: A-Z, 0-9 oraz znaków specjalnych, np.: !^<>" ' itp. Klawisz ENTER tworzy nowy akapit.
Tagi HTML są aktywne. Możesz:
Możliwość:
|
Komenda:
|
Przykład:
|
a. Pogrubić tekst: |
<B></B> |
Pogrubiony |
b. Pochylić tekst: |
<I></I> |
Pochylony |
c. Podkreślić tekst: |
<U></U> |
Podkreślony |
d. Stworzyć indeks górny: |
<SUP></SUP> |
Indeks górny |
e. Stworzyć indeks dolny: |
<SUB></SUB> |
Indeks dolny |
f. Użyć czcionki maszynowej: |
<TT></TT> |
Czcionka maszynowa |
Adresy URL wpisujemy w postaci http://nazwastrony.pl, ftp://nazwastrony.pl.
Adresy email wpisujemy w postaci nazwa@nazwa.pl.
Adresy Gadu-Gadu wpisujemy w postaci gg:1234567 (bez spacji).
Proszę pamiętać o domykaniu otwartych tagów.
Przed naciśnięciem przycisku Komentuj, zaznacz checkboks przy jego prawym boku.
|
|
|