MSX Village forum

La Place des Développeurs Mettre une valeur au carré en ASM Méthode rapide pour mettre une valeur 16-bits au carré en assembleur

aoineko Membre non connecté

Conseiller Municipal

Rang

Avatar

Groupe : Shoutbox

Inscrit le : 02/01/2011 à 21h17

Messages: 2680

Le 15/08/2017 à 22h25
Salut,

Est-ce que quelqu'un connait une méthode efficace pour mettre une valeur 16-bits au carré en assembleur ?
Bizarrement j'ai trouvé plein d'exemple pour la racine carré (sqrt) mais rien pour la carré (pow2).
J'ai des fonctions pour multiplier 2 entiers, mais je suppose qu'une multiplication par lui-même devrait pouvoir être encore plus optimisé.

Voici le code généré par ma compilateur C quand j'essaye de récupérer une distance-carrée [font= courier new](x²+y²)[/font] (j'imagine que c'est pas du tout optim).

Code ASM :
 
;carwar.c:1365: lenSq = x*x + y*y; // get squared length
    ld    l,4 (ix)
    ld    h,5 (ix)
    push    hl
    ld    l,4 (ix)
    ld    h,5 (ix)
    push    hl
    call    __mulint_rrx_s
    pop    af
    ex    (sp),hl
    ld    l,6 (ix)
    ld    h,7 (ix)
    push    hl
    ld    l,6 (ix)
    ld    h,7 (ix)
    push    hl
    call    __mulint_rrx_s
    pop    af
    pop    af
    ld    b,h
    ld    c,l
    pop    de
    ld    a,e
    add    a,c
    ld    c,a
    ld    a,d
    adc    a,b
    ld    b,a
 


Avec le code de la fonction [font= courier new]__mulint_rrx_s[/font] :
Code ASM :
 
__mulint_rrx_s::
        ld      hl,#2
        add     hl,sp
        ld      e,(hl)
        inc     hl
        ld      d,(hl)
        inc     hl
        ld      a,(hl)
        inc     hl
        ld      h,(hl)
        ld      l,a
        ;; Fall through
__muluchar_rrx_hds::
__mulint_rrx_hds::
    ;; Parameters:
    ;;    HL, DE (left, right irrelivent)
    ld    b,h
    ld    c,l
    ;; 16-bit multiplication
    ;;
    ;; Entry conditions
    ;;   BC = multiplicand
    ;;   DE = multiplier
    ;;
    ;; Exit conditions
    ;;   DE = less significant word of product
    ;;
    ;; Register used: AF,BC,DE,HL
.mul16:
        ld      hl,#0
        ld      a,b
        ; ld c,c
        ld      b,#16
        ;; Optimise for the case when this side has 8 bits of data or
        ;; less.  This is often the case with support address calls.
        or      a
        jp      NZ,1$
        ld      b,#8
        ld      a,c
1$:
        ;; Taken from z88dk, which originally borrowed from the
        ;; Spectrum rom.
        add     hl,hl
        rl      c
        rla                     ;DLE 27/11/98
        jr      NC,2$
        add     hl,de
2$:
        djnz    1$
        ret
 


Pour être plus clair, je cherche le code assembleur le plus optimisé pour faire :
Code TEXT :
a = b²


On est toujours ignorant avant de savoir.
Github    
aoineko Membre non connecté

Conseiller Municipal

Rang

Avatar

Groupe : Shoutbox

Inscrit le : 02/01/2011 à 21h17

Messages: 2680

Le 15/08/2017 à 22h41
Et pour être encore plus précis, voici la méthode « brute force » que je comptais utiliser si y a pas de ruse de sioux plus efficace
Code TEXT :
 
// pseudo code to compute a=b²
a = 0
for(b times)
   a += b
 


On est toujours ignorant avant de savoir.
Github    
aoineko Membre non connecté

Conseiller Municipal

Rang

Avatar

Groupe : Shoutbox

Inscrit le : 02/01/2011 à 21h17

Messages: 2680

Le 15/08/2017 à 23h10
Je me réponds à moi-même, mais la « brute force » n'est PAS une option. :siffle Mettre 200 au carré oblige à faire 200 fois la boucle... ce qui est TRÈS mauvais en terme de performance. Je continue à chercher...


On est toujours ignorant avant de savoir.
Github    
aoineko Membre non connecté

Conseiller Municipal

Rang

Avatar

Groupe : Shoutbox

Inscrit le : 02/01/2011 à 21h17

Messages: 2680

Le 16/08/2017 à 01h17
Pour ceux que ça intéresse, voici les 2 fonctions que j'ai réussi a adapter pour obtenir un carré à partir d'un entier 8 bits et 16 bits.
Le passage de paramètres via ix, c'est pour l'interfaçage avec le code des fonctions C.

Code C :
i16 Pow2_16b(i16 a)
{
    a;
    // This routine performs the operation DEHL = BC*DE
    __asm
        ld        a, 4(ix)
        ld        c, a
        ld        e, a
        ld        a, 5(ix)
        ld        b, a
        ld        d, a
    Mul16:
        ld        hl, #0
        ld        a, #16
    Mul16Loop:
        add        hl, hl
        rl        e
        rl        d
        jp        nc, NoMul16
        add        hl, bc
        jp        nc, NoMul16
        inc        de //; This instruction(with the jump) is like an "ADC DE,0"
    NoMul16:
        dec        a
        jp        nz, Mul16Loop
    __endasm;
}
 
i16 Pow2_8b(i8 a)
{
    a;
    // This routine performs the operation HL = H*E
    __asm
        ld        a, 4(ix)
        ld        h, a
        ld        e, a
    Mul8b:
        ld        d, #0            //; clearing D and L
        ld        l, d
        ld        b, #8            //; we have 8 bits
    Mul8bLoop:
        add        hl, hl            //; advancing a bit
        jp        nc, Mul8bSkip    //; if zero, we skip the addition(jp is used for speed)
        add        hl, de            //; adding to the product if necessary
    Mul8bSkip:
        djnz    Mul8bLoop
    __endasm;
}
 


On est toujours ignorant avant de savoir.
Github    
Metalion Membre non connecté

Conseiller Municipal

Rang

Avatar

Inscrit le : 23/12/2009 à 15h32

Messages: 1482

Le 17/08/2017 à 10h06
J'allais te dire, il y a plein de routine de multiplication optimisées pour Z80, ça doit être facile de les adapter pour calculer un carré ...


MSX1: Daewoo DPC-200 / Yamaha CX5M
MSX2: Sony HB-F9P
MSXVR
Vidéo: V9990 (GFX-9)
Audio: MSX-Music (FM-PAC) / MSX-Audio (Audiowave) / OPL4 (Monster Sound FM Blaster) / OPNB (Neotron)
   
Metalion Membre non connecté

Conseiller Municipal

Rang

Avatar

Inscrit le : 23/12/2009 à 15h32

Messages: 1482

Le 17/08/2017 à 14h58
J'ai trouvé ça :

The following provides an optimized algorithm to square an 8-bit number, but it only returns the lower 8 bits.

Code :
L_sqrd:
;Input: L
;Output: L*L->A
;147 t-states
;36 bytes
    ld b,l
;First iteration, get the lowest 3 bits of -x^2
    sla l
    rrc b
    sbc a,a
    or l
    ld c,a
;second iteration, get the next 2 bits of -x^2
    rrc b
    sbc a,a
    xor l
    and $F8
    add a,c
    ld c,a
;third iteration, get the next 2 bits of -x^2
    sla l
    rrc b
    sbc a,a
    xor l
    and $E0
    add a,c
    ld c,a
;fourth iteration, get the eight bit of x^2
    sla l
    rrc b
    sbc a,a
    xor l
    and $80
    sub c
    ret


MSX1: Daewoo DPC-200 / Yamaha CX5M
MSX2: Sony HB-F9P
MSXVR
Vidéo: V9990 (GFX-9)
Audio: MSX-Music (FM-PAC) / MSX-Audio (Audiowave) / OPL4 (Monster Sound FM Blaster) / OPNB (Neotron)
   
aoineko Membre non connecté

Conseiller Municipal

Rang

Avatar

Groupe : Shoutbox

Inscrit le : 02/01/2011 à 21h17

Messages: 2680

Le 20/08/2017 à 20h17
Merci. :top
J'ai surtout besoin de récupérer du 16 bits (j'utilise un pseudo float 8b.8b) mais ça peut servir pour d'autre cas.


On est toujours ignorant avant de savoir.
Github    
Metalion Membre non connecté

Conseiller Municipal

Rang

Avatar

Inscrit le : 23/12/2009 à 15h32

Messages: 1482

Le 21/08/2017 à 11h18
Ceci dit, si c'est le calcul de la distance entre 2 points que tu cherches, il y a probablement moyen de l'approximer par des calculs plus simples que la différence des carrés ...

http://wiki.intellivision.us/index.php?title=Dist_fast.asm


MSX1: Daewoo DPC-200 / Yamaha CX5M
MSX2: Sony HB-F9P
MSXVR
Vidéo: V9990 (GFX-9)
Audio: MSX-Music (FM-PAC) / MSX-Audio (Audiowave) / OPL4 (Monster Sound FM Blaster) / OPNB (Neotron)
   
aoineko Membre non connecté

Conseiller Municipal

Rang

Avatar

Groupe : Shoutbox

Inscrit le : 02/01/2011 à 21h17

Messages: 2680

Le 23/08/2017 à 22h56
Intéressant. :top Je connaissais pas.
Pour les collisions entre voiture, je vais faire encore plus simple ; je vais tester l'overlap de deux boites (du coup, juste des tests <> sur les 2 axes).


On est toujours ignorant avant de savoir.
Github    
aoineko Membre non connecté

Conseiller Municipal

Rang

Avatar

Groupe : Shoutbox

Inscrit le : 02/01/2011 à 21h17

Messages: 2680

Le 26/08/2017 à 23h40
En fait c'est absolument génial comme méthode !! :|

Je m'étais pas rendu compte du gain astronomique par rapport à la somme de 2 valeurs au carré... et surtout du fait de se retrouver avec un longueur non-carré (comme si on avait pris la racine-carrée de la longueur).

Du coup, j'ai gagné pas mal de temps sur ma frame. :)
Ça ramouille encore un peu à 4 joueurs, mais ça vient surement des copies VRAM en 256 couleurs pour mes sprites.

Merci Metalion ! :top


On est toujours ignorant avant de savoir.
Github    
Répondre
Vous n'êtes pas autorisé à écrire dans cette catégorie