Logicielsmoto.com http://www.logicielsmoto.com/phpBB/ |
|
atan2 http://www.logicielsmoto.com/phpBB/viewtopic.php?f=3&t=673 |
Page 1 sur 2 |
Auteur: | Bentoc [ 20 Mai 2022, 22:27 ] |
Sujet du message: | atan2 |
Bonjour, Je tiens à jour cette page avec la dernière version de la routine. Je suis reparti de celle-ci pour 6502 : https://codebase64.org/doku.php?id=base ... it_angle&s[]=atan Code: ; arctangent of y/x
; ----------------- ; Calculate the angle, in a 256-degree circle, between two points. ; The trick is to use logarithmic division to get the y/x ratio and ; integrate the power function into the atan table. Some branching is ; avoided by using a table to adjust for the octants. ; In otherwords nothing new or particularily clever but nevertheless ; quite useful. ; ; original 6502 code by Johan Forslof (doynax) ; computation is done on 9 bit signed values of x and y made by ; downscaling of 16 bit signed values ; ; input registers : ; D = y (16 bit signed value) ; X = x (16 bit signed value) ; ; output register : ; A = angle 0-255 (0 = 0 deg, $40 = 90 deg, $80 = 180 deg, $C0 = 270 deg) ; angle 0 start at (x=0, y<0) ; special case (0,0) return $40 tstd equ direct_page+121 x_h equ direct_page+123 y_h equ direct_page+124 x_l equ direct_page+125 y_l equ direct_page+126 octant equ direct_page+127 CalcAngle ; scale down 16 bit value to 9 bit sta y_h stb y_l tfr x,d sta x_h ; a loaded with x high byte stb x_l ldb y_h ; b loaded with y high byte bra @test @undoB decb ; undo incb @undoA deca ; undo inca asrb ; lower resolution ror y_l ; . asra ; . ror x_l ; end of lower resolution @test inca ; $00 => $01 or $ff => $00, every other value will have a bit set btw b7 and b1 bita #$fe ; do not change A, check if a bit is set btw b7 and b1 bne @undoA ; restore value and scale down incb bitb #$fe bne @undoB ldd x_l ; now values are computed to 8 bits and loaded in A:x ,B:y ; start of atan2 ; -------------- ; special cases bne > ldx x_h bne > lda #$40 ; x=0,y=0 rts ! tsta bne @y0 tst y_h bmi > lda #$80 ; x=0,y>0 rts ! lda #$00 ; x=0,y<0 rts @y0 tstb bne @run tst x_h bmi > lda #$40 ; x>0,y=0 rts ! lda #$C0 ; x<0,y=0 rts @run ; set x lda x_h ; test sign of x using the 16 bit input value asra ; cc=1 if x_h<0 rol octant ; set octant b2 if x is negative eora x_l ; set y ldb y_h ; test sign of y using the 16 bit input value asrb ; cc=1 if y_h<0 rol octant ; set octant b2 if y is negative eorb y_l ; compute ratio orcc #1 ldx #log2_tab lda a,x sbca b,x ; (dynamic instruction) compute y/x ratio bcs > ; branch if (x < y) nega andcc #$FE ; clear carry (x > y) ! ; retrieve the angle ldx #atan_tab lda a,x ; adjust octant ldx #octant_adjust ldb octant rolb ; set octant b0 if (x < y) andb #%111 ; modulo to keep usefull values eora b,x ; apply octant to angle ldx #octant_adjust2 adda b,x rts octant_adjust fcb %01000000 ;; x+,y+,|x|>|y| 40-5F T1 fcb %01111111 ;; x+,y+,|x|<|y| 60-7F T0 fcb %00111111 ;; x+,y-,|x|>|y| 20-3F T2 fcb %00000000 ;; x+,y-,|x|<|y| 00-1F T3 fcb %10111111 ;; x-,y+,|x|>|y| A0-BF T2 fcb %10000000 ;; x-,y+,|x|<|y| 80-9F T3 fcb %11000000 ;; x-,y-,|x|>|y| C0-DF T1 fcb %11111111 ;; x-,y-,|x|<|y| E0-FF T0 octant_adjust2 fcb 0 fcb 0 fcb 1 fcb 1 fcb 1 fcb 1 fcb 0 fcb 0 ;;;;;;;; atan(2^(x/32))*128/pi ;;;;;;;; fcb $02,$02,$02,$02,$02,$02,$02,$02 ; 80 fcb $03,$03,$03,$03,$03,$03,$03,$03 fcb $03,$03,$03,$03,$03,$04,$04,$04 ; 90 fcb $04,$04,$04,$04,$04,$04,$04,$04 fcb $05,$05,$05,$05,$05,$05,$05,$05 ; A0 fcb $06,$06,$06,$06,$06,$06,$06,$06 fcb $07,$07,$07,$07,$07,$07,$08,$08 ; B0 fcb $08,$08,$08,$08,$09,$09,$09,$09 fcb $09,$0a,$0a,$0a,$0a,$0b,$0b,$0b ; C0 fcb $0b,$0c,$0c,$0c,$0c,$0d,$0d,$0d fcb $0d,$0e,$0e,$0e,$0e,$0f,$0f,$0f ; D0 fcb $10,$10,$10,$11,$11,$11,$12,$12 fcb $12,$13,$13,$13,$14,$14,$15,$15 ; E0 fcb $15,$16,$16,$17,$17,$17,$18,$18 fcb $19,$19,$19,$1a,$1a,$1b,$1b,$1c ; F0 fcb $1c,$1c,$1d,$1d,$1e,$1e,$1f,$1f atan_tab fcb $00,$00,$00,$00,$00,$00,$00,$00 ; 00 fcb $00,$00,$00,$00,$00,$00,$00,$00 fcb $00,$00,$00,$00,$00,$00,$00,$00 ; 10 fcb $00,$00,$00,$00,$00,$00,$00,$00 fcb $00,$00,$00,$00,$00,$00,$00,$00 ; 20 fcb $00,$00,$00,$00,$00,$00,$00,$00 fcb $00,$00,$00,$00,$00,$00,$00,$00 ; 30 fcb $00,$00,$00,$00,$00,$00,$00,$00 fcb $00,$00,$00,$00,$00,$00,$00,$00 ; 40 fcb $00,$00,$00,$00,$00,$00,$00,$00 fcb $00,$00,$00,$00,$00,$01,$01,$01 ; 50 fcb $01,$01,$01,$01,$01,$01,$01,$01 fcb $01,$01,$01,$01,$01,$01,$01,$01 ; 60 fcb $01,$01,$01,$01,$01,$01,$01,$01 fcb $01,$01,$01,$01,$01,$02,$02,$02 ; 70 fcb $02,$02,$02,$02,$02,$02,$02,$02 ;;;;;;;; log2(x)*32 ;;;;;;;; fcb $df,$e0,$e0,$e1,$e1,$e1,$e2,$e2 ; 80 fcb $e2,$e3,$e3,$e3,$e4,$e4,$e4,$e5 fcb $e5,$e5,$e6,$e6,$e6,$e7,$e7,$e7 ; 90 fcb $e7,$e8,$e8,$e8,$e9,$e9,$e9,$ea fcb $ea,$ea,$ea,$eb,$eb,$eb,$ec,$ec ; A0 fcb $ec,$ec,$ed,$ed,$ed,$ed,$ee,$ee fcb $ee,$ee,$ef,$ef,$ef,$ef,$f0,$f0 ; B0 fcb $f0,$f1,$f1,$f1,$f1,$f1,$f2,$f2 fcb $f2,$f2,$f3,$f3,$f3,$f3,$f4,$f4 ; C0 fcb $f4,$f4,$f5,$f5,$f5,$f5,$f5,$f6 fcb $f6,$f6,$f6,$f7,$f7,$f7,$f7,$f7 ; D0 fcb $f8,$f8,$f8,$f8,$f9,$f9,$f9,$f9 fcb $f9,$fa,$fa,$fa,$fa,$fa,$fb,$fb ; E0 fcb $fb,$fb,$fb,$fc,$fc,$fc,$fc,$fc fcb $fd,$fd,$fd,$fd,$fd,$fd,$fe,$fe ; F0 fcb $fe,$fe,$fe,$ff,$ff,$ff,$ff,$ff log2_tab fcb $00,$00,$20,$32,$40,$4a,$52,$59 ; 00 fcb $60,$65,$6a,$6e,$72,$76,$79,$7d fcb $80,$82,$85,$87,$8a,$8c,$8e,$90 ; 10 fcb $92,$94,$96,$98,$99,$9b,$9d,$9e fcb $a0,$a1,$a2,$a4,$a5,$a6,$a7,$a9 ; 20 fcb $aa,$ab,$ac,$ad,$ae,$af,$b0,$b1 fcb $b2,$b3,$b4,$b5,$b6,$b7,$b8,$b9 ; 30 fcb $b9,$ba,$bb,$bc,$bd,$bd,$be,$bf fcb $c0,$c0,$c1,$c2,$c2,$c3,$c4,$c4 ; 40 fcb $c5,$c6,$c6,$c7,$c7,$c8,$c9,$c9 fcb $ca,$ca,$cb,$cc,$cc,$cd,$cd,$ce ; 50 fcb $ce,$cf,$cf,$d0,$d0,$d1,$d1,$d2 fcb $d2,$d3,$d3,$d4,$d4,$d5,$d5,$d5 ; 60 fcb $d6,$d6,$d7,$d7,$d8,$d8,$d9,$d9 fcb $d9,$da,$da,$db,$db,$db,$dc,$dc ; 70 fcb $dd,$dd,$dd,$de,$de,$de,$df,$df |
Auteur: | Bentoc [ 21 Mai 2022, 10:01 ] |
Sujet du message: | Re: atan2 |
Bon j'ai avancé ... Voici ce que j'ai corrigé : Code: orcc #1 ldx #log2_tab ldb b,x subb a,x bcs > negb andcc #$FE ! ldx #atan_tab ldb b,x ça fonctionne mieux, j'ai encore des erreurs aux bornes supérieures de chaque secteur, mais au moins les valeurs intermédiaires sont justes, j'ai testé pour les angles : 0, 7, 15.5, 22.5, 29.5, 38, 45(KO), 52, 60.5, 67.5, 74.5 83, 90 (KO), 97, 173, 180(KO), 359 J'ai du louper un truc dans le code d'origine mais je vais bien finir par trouver ... |
Auteur: | Bentoc [ 21 Mai 2022, 10:14 ] |
Sujet du message: | Re: atan2 |
Apparement en remplaçant le subb par sbcb ça a l'air de fonctionner pour de bon ... je ferai une batterie de tests dans l'après midi |
Auteur: | Samuel Devulder [ 21 Mai 2022, 13:19 ] |
Sujet du message: | Re: atan2 |
Le ORCC#1 ne sert à rien en cas de SUBB. A savoir: le 6502 est moins riche que nous pour les additions/soustractions. Il prends systématiquement la carry/borrow en entrée. En gros il n'a que ADCx et SBCx au lieu des simples ADDx et SUBx. C'est pourquoi on trouve plein de CLC/SEC chez eux juste avant les additions/soustractions. Au départ en lisant ton code je me disais que les ORCC/ANDCC venaient du portage strict depuis le 6502 et ne servaient donc à rien chez nous. Mais peut-être que non en fait: vu ta dernière remarque: le calcul serait fait moralement sur 9 bits en utilisant la retenue comme bit supplémentaire. Cela dit, il faudrait voir si la retenue n'est pas automatiquement positionnée ou retirée en fonction des instructions précédentes, auquel cas les ORCC/ANDCC seraient redondants. Les 6502 et 6809 ont l'air très voisins (8 bits, accumulateur, etc), mais en fait un code optimisé pour l'un ne l'est plus forcément pour l'autre. |
Auteur: | Bentoc [ 21 Mai 2022, 13:41 ] |
Sujet du message: | Re: atan2 |
Le ORCC#1 est utilisé par le rola un peu plus bas, sauf s'il est clear (juste apres le negb). Oui pas facile le 6502 ... Voila le résultat pour le moment : (Mise à jour avec la dernière version du code) Fichier(s) joint(s): resultat.png [ 173.23 Kio | Vu 7775 fois ] Il ne reste plus qu'un "aliasing" dont je ne sais pas s'il provient du jeu de test ou non. Pour moi c'est suffisant pour ce que j'ai prévu de faire je pense. |
Auteur: | Bentoc [ 21 Mai 2022, 14:05 ] |
Sujet du message: | Re: atan2 |
Le carry est utilisé pour alimenter un index sur le tableau octant. On a donc trois rol qui construisent l’index a l’aide du carry qu’on set ou qu’on clear. |
Auteur: | Bentoc [ 21 Mai 2022, 18:44 ] |
Sujet du message: | Re: atan2 |
Voila j'ai mis à jour le code et le résultat des tests. Ce n'est pas parfait mais ça s'en approche, si vous avez une idée pour corriger les dernières valeurs KO n'hésitez pas. a+ |
Auteur: | Samuel Devulder [ 21 Mai 2022, 20:20 ] |
Sujet du message: | Re: atan2 |
Je n'ai pas encore regardé de près la conversion 6502->6809, surtout que ca n'est pas exactement le même algo (ici on a pas deux points en entrée mais un vecteur de 2x16bits), mais je pense qu'on peut améliorer la conversion en 8 bits du vecteur 16bits en entrée. Si j'ai bien compris l'idée, on part d'un couple (x,y) sur 16 bits que l'on transforme en (x>>1, y>>1) tant que la partie haute de x et de y n'est pas $00, ou à $ff. On peut regrouper ces deux tests en un seul en remarquant que (A==0 ou A==$FF) <=> (A+1==1 ou A+1==0) [addition 8 bits] <=> ((A+1)>>1)==0 <=> tous les bits au dessus du bit de poids faible sont nuls. Code: @loop lda x inca lsra bne @shift ! lda y inca lsra beq > @shift asr x ; je crois que 2 rotations en mémoire sont plus rapide que LDD/STD+rotation registre ror x+1 asr y ror y+1 bra @loop ! <suite> Ensuite, si on aime pas trop les sauts, on peut même regrouper les tests sur x et y en une fois et n'avoir qu'un seul saut au sein de la boucle: Code: bra @test ; celui là ne compte pas car il n'est fait qu'une fois On a là un code compact, et pas trop lent je pense (j'ai pas compté les cycles). Le truc cool est de de voir que le pseudo TSTD permet de tester en une seule opération A==0 && B==0.
@shift asr x ; probablement plus rapide d'avoir 2 rotations en ror x+1 ; mémoire qu'un LDD/STD + rotation registres asr y ror y+1 @test lda x ldb y inca incb lsra ; ou asr ou anda #$fe, peu importe: on veut juste savoir si les bits 1 à 7 sont tous à 0 lsrb std -2,s ; c'est un TSTD ==> Z=0 ssi A=0 et B=0, donc les parties hautes de x et y sont à $00 ou $FF bne @shift |
Auteur: | Bentoc [ 21 Mai 2022, 20:58 ] |
Sujet du message: | Re: atan2 |
Cool ! Merci sam. j’ai appris encore plein de choses. Je peux utiliser une variable temp en direct page a la place de -2,s ce sera encore plus rapide j’imagine. |
Auteur: | Samuel Devulder [ 21 Mai 2022, 22:45 ] |
Sujet du message: | Re: atan2 |
Oui, mais le gain est marginal: 5 cycles au lieu de 6. A voir si ca change grand chose (je ne suis même pas certain qu'avoir un seul test fasse gagner beaucoup dans la mesure ou si cela se trouve c'est le 1er test sur le MSB de x qui fait majoritairement passer directement à @shift sans regarder celui de y). |
Auteur: | Bentoc [ 21 Mai 2022, 22:49 ] |
Sujet du message: | Re: atan2 |
Code: 7069 779F7B (./Engine/Math/Cal):00021 [7] 951 @shift asr x 706C 769F7C (./Engine/Math/Cal):00022 [7] 958 ror x+1 706F 779F7D (./Engine/Math/Cal):00023 [7] 965 asr y 7072 769F7E (./Engine/Math/Cal):00024 [7] 972 ror y+1 7075 (./Engine/Math/Cal):00025 CalcAngle 7075 B69F7B (./Engine/Math/Cal):00026 [5] 977 lda x 7078 4C (./Engine/Math/Cal):00027 [2] 979 inca 7079 44 (./Engine/Math/Cal):00028 [2] 981 lsra 707A 26ED (./Engine/Math/Cal):00029 [3] 984 bne @shift 707C B69F7D (./Engine/Math/Cal):00030 [5] 989 lda y 707F 4C (./Engine/Math/Cal):00031 [2] 991 inca 7080 44 (./Engine/Math/Cal):00032 [2] 993 lsra 7081 26E6 (./Engine/Math/Cal):00033 [3] 996 bne @shift C'est la variante la plus rapide. Le test en une seule fois est moins interressant (+3 cycles et on est obliger d'aller au bout, alors qu'avec les tests séparés on peut brancher sur le premier test on zappe donc 12 cycles ... et on est dans une boucle donc 8*12 au pire c'est bien venu !) Sur le shift on gagne 7 cycles avec ta méhode pareil *8 dans le pire des cas. C'est pas mal ! |
Auteur: | Samuel Devulder [ 21 Mai 2022, 23:01 ] |
Sujet du message: | Re: atan2 |
Est-ce que tu ne gagnerais pas à utiliser des variables en page direct plutôt que les variables globales x,y ? Genre Code: ldd x
sta >tmp stb >tmp+2 ; partie basse de x ldd y sta >tmp+1 stb >tmp+3 ; partie basse de y bra @test @shift ldd >tmp asra ror >tmp+2 asrb ror >tmp+3 std >tmp @test inca lsra bne @shift incb lsrb bne @shift |
Auteur: | Bentoc [ 21 Mai 2022, 23:10 ] |
Sujet du message: | Re: atan2 |
euh désolé, il manque le setdp je n'ai pas fait attention ... mais pourtant il est bien la dans le lst ... bon je regarde Le main est composé de plusieurs include et le SETDP (il n'y en a qu'un) était bien en début de fichier, j'ai du en rajouter un avant la routine pour qu'il me le prenne ... bref : Code: 7069 077B (./Engine/Math/Cal):00023 [6] 950 @shift asr x 706B 067C (./Engine/Math/Cal):00024 [6] 956 ror x+1 706D 077D (./Engine/Math/Cal):00025 [6] 962 asr y 706F 067E (./Engine/Math/Cal):00026 [6] 968 ror y+1 7071 (./Engine/Math/Cal):00027 CalcAngle 7071 967B (./Engine/Math/Cal):00028 [4] 972 lda x 7073 4C (./Engine/Math/Cal):00029 [2] 974 inca 7074 44 (./Engine/Math/Cal):00030 [2] 976 lsra 7075 26F2 (./Engine/Math/Cal):00031 [3] 979 bne @shift 7077 967D (./Engine/Math/Cal):00032 [4] 983 ! lda y 7079 4C (./Engine/Math/Cal):00033 [2] 985 inca 707A 44 (./Engine/Math/Cal):00034 [2] 987 lsra 707B 26EC (./Engine/Math/Cal):00035 [3] 990 bne @shift Voila ;-) |
Auteur: | Bentoc [ 21 Mai 2022, 23:19 ] |
Sujet du message: | Re: atan2 |
glb_tmp_var vaut $9F00 et le setdp $9F |
Auteur: | Samuel Devulder [ 21 Mai 2022, 23:23 ] |
Sujet du message: | Re: atan2 |
Oh, j'ai encore mieux je pense Code: [4] lda >x Il y a très peu d'accès mémoire durant la boucle car l'utilisation de BITA/BITB permet de ne pas être destructif sur le contenu de ces registres ce qui épargne plusieurs accès mémoire dans le code.
[4] ldb >y [3] bra @test ; --- magie --- [2] @undoB decb ; on annule le incb [2] @undoA asrb ; ancien @shift [6] ror >y+1 [2] deca ; on annule le inca [2] asra [6] ror >x+1 [2] @test inca [2] bita #$fe ; ne modifie pas A. Test juste si un bit est positionné entre b1 et b7 [3] bne @undoA ; donc on a qu'a annuler le inc pour retrouver la bonne valeur de A [2] incb [2] bitb #$fe [3] bne @undoB |
Page 1 sur 2 | Heures au format UTC + 1 heure |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |