optimisation d'un modulo 10 - Page 1

chest encore moi chuis chiant hein ? .. dsl

j'essai tant bien que mal d'optimiser mon modulo 10, mais c'est vachement dur,
pour le moment j'ai ca :
d0 = le chiffre (positif) sur 2 octets

moveq.l #10,%d2
divu.w %d2,%d0
swap %d0

d0.w = le modulo

quelqun aurait - il un meilleur algo?
parce que le divu il est vachement lent...

ça dépend quelle plage de nombres te suffit en entrée...

move.w d0,d1
muls #6554,d1
swap d1
muls #10,d1
sub.w d1,d0

convient pour d0 € [0,16383]

Si le nombre est petit, alors cet algorithme-là devrait être plus rapide:

moveq.l #10,%d2
0:
sub.w %d2,%d0
bcc.s 0b
add.w %d2,%d0

oui, si il est très petit...

sinon, si tu veux d0 € [0,32767], tu peux rajouter "bpl \ok; moveq #9,d0; \ok"
si tu veux d0 € [0,65535], tu peux rajouter "bpl \ok; add.w #10,d0; \ok" (et tu peux mettre #10 dans un registre pour grapiller qques cycles et octets)

./4> C'est plus intéressant si le nombre est inférieur à environ 100.

Sinon, il y a aussi:

moveq.l #100,%d2
0:
sub.w %d2,%d0
bcc.s 0b
add.w %d2,%d0
moveq.l #10,%d2
1:
sub.w %d2,%d0
bcc.s 1b
add.w %d2,%d0

voire:

move.w #1000,%d2
0:
sub.w %d2,%d0
bcc.s 0b
add.w %d2,%d0
moveq.l #100,%d2
1:
sub.w %d2,%d0
bcc.s 1b
add.w %d2,%d0
moveq.l #10,%d2
2:
sub.w %d2,%d0
bcc.s 2b
add.w %d2,%d0

L'algo du ./3 de Pollux est environ 40% plus rapide que ce qu'utilise bidoo (oui, j'ai mis du temps à calculer....).

Ou alors:

move.w #40960,%d2
.rept 12
cmp.w %d2,%d0
bcs.s 0f
sub.w %d2,%d0
0:
lsr.w #1,%d0
.endr
cmp.w %d2,%d0
bcs.s 1f
sub.w %d2,%d0
1:

Mais je ne sais pas si ça vaut le coup par rapport à la routine de Pollux.

(Enfin bon, je pense que c'est ce que fait divu en interne, donc ça m'étonnerait que ce soit plus rapide...)

au fait, si on veut optimiser ./3, il vaut mieux utiliser mulu (6554 et 10 s'y prêtent mieux), et remplacer le mulu #10,d1;sub.w d1,d0 par add.w d1,d1;sub.w d1,d0;add.w d1,d1;add.w d1,d1;sub.w d1,d0 (mais par contre on perd un registre si on veut étendre ça au cas d0>=16384, ou alors on perd 10 cycles)

-> ça fait 75% de vitesse en plus au lieu de 40% ^^

wahou c'est genial, merci beaucoup beaucoup à tous!
(et en fait c'est juste pour un nombre <1023 environ)

bon, je vais essayer de comprendre vos algo

Essaie celui du ./7 alors, c'est peut-être celui qui donnera les meilleures performances...

J'y crois moyennement, pour un nombre <1000, ça fait 40+14*(somme des chiffres de x/10) cycles, alors que ./2 fait 88 cycles dans tous les cas, donc à moins d'avoir un nombre dans [0,39]u[100,129]u[200,219]u[300,309], ça devrait être plus lent (./7 fait 292 cycles dans le pire des cas )

Mais évidemment si on en a besoin surtout pour des très petits nombres (<40), ./7 est plus rentable, sinon c'est ./2.

j'avais prevu d'utiliser les 2 algo, celui de kevin et le tien pollux : je perd pas grand chose a faire un cmp #40,%d0;ble ./7

par contre, je voulais savoir, comment tu as fait pour trouver que le fait de multiplier par 6554 et de faire un swap (ou lsr.w #16) correspondait a une division par 10?
ca tient du genie !!!

aaa j'ai compris !! 6554 ~=~ 2^16/10 et on a (2^16/10)/2^16 = .1

trop baleze

par contre je ne comprend pas dans l'algo de kevin,
bcc c'a branche si le c-flag est nul n'est ce pas ?
mais le sub, je comprend pas ce qu'il lui fait au c-flag,
dans le 68kguide il est dit que :

Set if a loan was required from the most significant bit, else 0.

mon anglais est tres mediocre... (tout comme mon francais d'ailleurs)
qu'est ce que ca veut dire ?

bidoo :
par contre, je voulais savoir, comment tu as fait pour trouver que le fait de multiplier par 6554 et de faire un swap (ou lsr.w #16) correspondait a une division par 10?
ca tient du genie !!!

Euh j'ai aucun mérite, on en avait déjà parlé ici, hein ^^

bidoo :
aaa j'ai compris !! 6554 ~=~ 2^16/10 et on a (2^16/10)/2^16 = .1

trop baleze

Note que le "environ" ne suffit pas, en l'occurrence comme j'arrondis le résultat de mulu à l'inférieur, il faut que j'arrondisse ce par quoi je multiplie au supérieur, et ça ne marche que dans un domaine qui dépend de la qualité de la première approximation... (tu peux le trouver en faisant des simples encadrements, ici c'est x<16384, et si j'avais pris une approximation moins bonne, par exemple 6555 au lieu de 6554, ce serait seulement x<4682)

bidoo :
par contre je ne comprend pas dans l'algo de kevin,
bcc c'a branche si le c-flag est nul n'est ce pas ?
mais le sub, je comprend pas ce qu'il lui fait au c-flag,
dans le 68kguide il est dit que :

Set if a loan was required from the most significant bit, else 0.

mon anglais est tres mediocre... (tout comme mon francais d'ailleurs)
qu'est ce que ca veut dire ?

"Activé si une retenue était nécessaire pour le bit de poids fort, sinon mis à 0."
"bcc" est aussi synonyme de "bhs", "branch higher or same" qui est l'équivalent de "bge" mais en non signé...

merci pollux !

j'ai un nouveau petit probleme, voila, normalement la fonction suivante doit calculer le nombre de ligne que prend une chaîne de caractere en font 4x6 quant on l'affiche, mais ca marche pas du tout , j'ai beau chercher ds tous les sens, ca marche pas ... j'ai l'impression que ca vient de mon cmp.b #156,%d0 blt ... car dans mon tableau j'ai les numero de tous les caractere de ma chaîne...
quand on a :
cmp X,Y
blt label
ca correspond a : si Y<X , on blt non ?

| Assembly Source File
| Created 05/08/2004; 16:56:45
.text
 xdef getnblignes_fsmall

| Input :
| a0 = addresse de la chaîne
| a1 = pointeur vers un tableau unsigned char resultant d'un malloc(50)
| a2 = adresse du sprite de la 1ere lettre ds la rom 


getnblignes_fsmall:

 movem.l %d0-%d3/%a3,-(%a7)
 moveq.l #0  ,%d0 |=x
 moveq.l #0  ,%d3 |=compteur
 
getnblines_boucle:

 tst.b   1(%a0)      |si on arrive a la fin de la chaîne, on part
 bne     getnblines_pas_fin
 
 movem.l (%a7)+,%d0-%d3/%a3
 rts

getnblines_pas_fin: 
 add.b   #1,%d3        |compteur++
 
 moveq.l #0    ,%d1    |a3=a2+6*a0
 move.b  (%a0)+,%d1    |*(a3+1)==sprite du caractere
 move.w  %d1   ,%d2    |
 lsl.w   #3    ,%d1    |
 lsl.w   #1    ,%d2    |
 sub.w   %d2   ,%d1    |
 move.l  %d1   ,%a3    |
 adda.l  %a2   ,%a3    |
 
 add.b   (%a3) ,%d0    |x+=taille du caractere
 
 cmpi.b   #156  ,%d0    | si x > 156 ca fait une ligne

 blt     getnblines_boucle
 moveq.l #0    ,%d0    | on remet x a 0
 
 |sub.b   #1    ,%d3    |dans notre tableau on stocke le numero 
 move.b %d3,   (%a1)+  |du dernier caractere de la ligne 

 bra getnblines_boucle
 

pour info, si vous avez une ams 2.09 , mettez dans a2 (void*)0x207C78 et le prototype pour un fnc inline est :
void getnblignes_fsmall(void * string asm("a0"),void *dest asm("a1"),void * table asm("a2"))

et je veux pas utiliser FontCharWidth ni DrawStrWidthP

ok j'ai trouvé, en remplacant cmpi.b par cmpi.w ca marche (je ne comprend absolument pas pourquoi d'ailleurs ... )

Parce que ton blt est un test signé.

ah ba oui !!!! N=negative!!

et en utilisant bhi ca marche alors!