Logicielsmoto.com

Nous sommes le 19 Mar 2024, 08:01

Heures au format UTC + 1 heure




Poster un nouveau sujet Répondre au sujet  [ 23 messages ]  Aller à la page 1, 2  Suivante
Auteur Message
 Sujet du message: atan2
MessagePosté: 20 Mai 2022, 22:27 
Hors ligne

Inscription: 21 Avr 2019, 21:48
Messages: 432
Localisation: Var
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


Dernière édition par Bentoc le 22 Mai 2022, 16:40, édité 6 fois.

Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: atan2
MessagePosté: 21 Mai 2022, 10:01 
Hors ligne

Inscription: 21 Avr 2019, 21:48
Messages: 432
Localisation: Var
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 ...


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: atan2
MessagePosté: 21 Mai 2022, 10:14 
Hors ligne

Inscription: 21 Avr 2019, 21:48
Messages: 432
Localisation: Var
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


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: atan2
MessagePosté: 21 Mai 2022, 13:19 
Hors ligne

Inscription: 21 Aoû 2006, 09:06
Messages: 1800
Localisation: Brest
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.

_________________
Good morning, that's a nice Tnetennba


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: atan2
MessagePosté: 21 Mai 2022, 13:41 
Hors ligne

Inscription: 21 Avr 2019, 21:48
Messages: 432
Localisation: Var
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
resultat.png [ 173.23 Kio | Vu 7047 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.


Dernière édition par Bentoc le 22 Mai 2022, 16:44, édité 4 fois.

Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: atan2
MessagePosté: 21 Mai 2022, 14:05 
Hors ligne

Inscription: 21 Avr 2019, 21:48
Messages: 432
Localisation: Var
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.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: atan2
MessagePosté: 21 Mai 2022, 18:44 
Hors ligne

Inscription: 21 Avr 2019, 21:48
Messages: 432
Localisation: Var
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+


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: atan2
MessagePosté: 21 Mai 2022, 20:20 
Hors ligne

Inscription: 21 Aoû 2006, 09:06
Messages: 1800
Localisation: Brest
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
@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
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.

_________________
Good morning, that's a nice Tnetennba


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: atan2
MessagePosté: 21 Mai 2022, 20:58 
Hors ligne

Inscription: 21 Avr 2019, 21:48
Messages: 432
Localisation: Var
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.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: atan2
MessagePosté: 21 Mai 2022, 22:45 
Hors ligne

Inscription: 21 Aoû 2006, 09:06
Messages: 1800
Localisation: Brest
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).

_________________
Good morning, that's a nice Tnetennba


Dernière édition par Samuel Devulder le 21 Mai 2022, 22:57, édité 1 fois.

Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: atan2
MessagePosté: 21 Mai 2022, 22:49 
Hors ligne

Inscription: 21 Avr 2019, 21:48
Messages: 432
Localisation: Var
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 !


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: atan2
MessagePosté: 21 Mai 2022, 23:01 
Hors ligne

Inscription: 21 Aoû 2006, 09:06
Messages: 1800
Localisation: Brest
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

_________________
Good morning, that's a nice Tnetennba


Dernière édition par Samuel Devulder le 21 Mai 2022, 23:15, édité 3 fois.

Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: atan2
MessagePosté: 21 Mai 2022, 23:10 
Hors ligne

Inscription: 21 Avr 2019, 21:48
Messages: 432
Localisation: Var
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 ;-)


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: atan2
MessagePosté: 21 Mai 2022, 23:19 
Hors ligne

Inscription: 21 Avr 2019, 21:48
Messages: 432
Localisation: Var
glb_tmp_var vaut $9F00 et le setdp $9F


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: atan2
MessagePosté: 21 Mai 2022, 23:23 
Hors ligne

Inscription: 21 Aoû 2006, 09:06
Messages: 1800
Localisation: Brest
Oh, j'ai encore mieux je pense
Code:
[4]         lda   >x
[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
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.

_________________
Good morning, that's a nice Tnetennba


Dernière édition par Samuel Devulder le 22 Mai 2022, 08:33, édité 5 fois.

Haut
 Profil  
Répondre en citant le message  
Afficher les messages postés depuis:  Trier par  
Poster un nouveau sujet Répondre au sujet  [ 23 messages ]  Aller à la page 1, 2  Suivante

Heures au format UTC + 1 heure


Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 6 invités


Vous ne pouvez pas poster de nouveaux sujets
Vous ne pouvez pas répondre aux sujets
Vous ne pouvez pas éditer vos messages
Vous ne pouvez pas supprimer vos messages
Vous ne pouvez pas joindre des fichiers

Rechercher:
Aller à:  
cron
Développé par phpBB® Forum Software © phpBB Group
Traduction par phpBB-fr.com