Fast_sqrt - Page 1

hello

j'ai trouvé cette routine en C sur internet qui sert a calculer rapidement des racines carrées et je l'ai convertie en 68000.

;-----------------------------------------------------------------------------
; fast_sqrt : compute a fast integer inverse square root
;	arg : d0
;	ret : d0
;-----------------------------------------------------------------------------
;  original C code by Jim Ulery :
;      static unsigned mborg_isqrt3(unsigned long val)
;      {
;        unsigned long temp, g=0, b = 0x8000, bshft = 15;
;        do {
;          if (val >= (temp = (((g<<1)+b)<<bshft--))) {
;            g += b;
;            val -= temp;
;          }
;        } while (b >>= 1);
;        return g;
;      }
;-----------------------------------------------------------------------------

fast_sqrt:
	movem.l		d1-d4,			-(sp)
	moveq		#0,				d1			; g = 0
	move.l		#$8000,			d2			; b = $8000
	moveq		#15,			d3			; bshft = 15
fast_sqrt_0:
	move.l		d1,				d4			; temp = g
	add.l		d1,				d4			; temp = g<<1
	add.l		d2,				d4			; temp = (g<<1)+b
	lsl.l		d3,				d4			; temp = ((g<<1)+b)<<bshft
	subq.l		#1,				d3			; bshft--
	cmp.l		d0,				d4			; val >= temp ?
	bhi.s		fast_sqrt_1					;	no -> fast_sqrt_1
	add.l		d2,				d1			; g += b
	sub.l		d4,				d0			; val -= temp
fast_sqrt_1:
	lsr.l		#1,				d2			; b >>= 1, b!=0 ?
	bne.s		fast_sqrt_0					;	yes -> fast_sqrt_0
	move.l		d1,				d0			; return g
	movem.l 	(sp)+,			d1-d4
	rts

j'ai pas cherché a l'optimiser plus que ca, si qqun veut le faire, je suis preneur !

edit : j'ai changé le tag 'code' en 'pre', avec un tab-size de 4 ca rendrait mieux !

Je l'ai fait pour ma boite, j'ai pas le source chez moi. Travailler en virgule fixe de préférence, puisque cette routine ne travaille que sur des entier. Donc en entrée, un p'tit LSL 4, et en sortie un ASR 4 si on ne veux pas utiliser les 4 bits de mantisse...

Kochise

Bon a avoir, merci mon Tobe !



GT Turbo (68xxx user !)

Comme promis, j'ai fait concis...

int IPOW(int x, int n){return (!n)?1: (n&1)?x*IPOW(x,n-1):IPOW(x*x,n>>1);}
int SQRT(int n){int r=0,b,t; b=(n>=0x10000)?1<<30:1<<14; do{t=r+b; if(n>=t){n-=t; r=t+b;} r>>=1; b>>=2;}while(b); return r;}

Kochise

PS : Concis, pas circoncis !

GT Perdu avec vos langages de barbares !!

Kochise :
Comme promis, j'ai fait concis...

int IPOW(int x, int n){return (!n)?1: (n&1)?x*IPOW(x,n-1):IPOW(x*x,n>>1);}
int SQRT(int n){int r=0,b,t; b=(n>=0x10000)?1<<30:1<<14; do{t=r+b; if(n>=t){n-=t; r=t+b;} r>>=1; b>>=2;}while(b); return r;}

Kochise

PS : Concis, pas circoncis !

je vais transformer ca en 68000

Moi barbare taper GT KC avec coup de HASH :

int HASH(const char* c, int s = 0){return (*c!=0)?HASH(c+1,s+1)+(((*c|0x20)-'a'+1)*IPOW(26,s)): 0; }

Kochise

;-----------------------------------------------------------------------------
;  original C code by Kochise :
;	int SQRT(int n)
;	{
;		int r=0,
;		int b,
;		int t;
;		b=(n>=0x10000)?1<<30:1<<14;
;		do
;		{
;			t=r+b;
;			if(n>=t)
;			{
;				n-=t;
;				r=t+b;
;			}
;			r>>=1;
;			b>>=2;
;		}
;		while(b);
;		return r
;	}
;-----------------------------------------------------------------------------

fast_sqrt:
	movem.l	d1/d3,			-(sp)
	moveq	#0,				d1		; r = 0
	move.l	#$4000,			d2		; b = 1<<14
	cmpi.l	#$10000,		d0		; n >= $10000 ?
	blt.s	fast_sqrt_0				; if n < $10000 : fast_sqrt_0
	swap	d2						; else          : b = 1<<30
fast_sqrt_0:						; do
	move.l	d1,				d3		; t = r
	add.l	d2,				d3		; t = r + b
	cmp.l	d0,				d3		; n >= t ?
	bgt.s	fast_sqrt_1				; if t > n : fast_sqrt_1
	sub.l	d3,				d0		; else     : n -= t
	move.l	d3,				d1		;            r = t
	add.l	d2,				d1		;            r = t + b
fast_sqrt_1:
	lsr.l	#1,				d1		; r >>= 1
	lsr.l	#2,				d2		; b >>= 2
	bne.s	fast_sqrt_0				; while (b)
	move.l	d1,				d0		; return r
	movem.l	(sp)+,			d1/d3
	rts

ptet que je me suis planté qqpart (j'ai du mal avec les cmp du 68k !!!), mais ca marche pô.
Kochise : tu peux verifier ?

avec un tab-size de 4 ca rends mieux

TabSize = 2, c'est suffisant... Bon, j'ai pas mon assembleur fétiche sous le coude, mais de p'tite tête :

int IPOW
( int x
, int n
)
{ return
  (!n)
  ? 1
  : (n & 1)
    ? x * IPOW(x, n - 1)
    : IPOW(x * x, n >> 1)
  ;
}

; IPOW by Kochise
               move.l          #2,D0           ; x
               move.l          #10,D1          ; n
               BSR             IPOW
               cmpi.l          #1024,D0        ; 2^10 = 1024
               ...

IPOW:          movem.l         D1-D2,-(SP)
               tst.l           D1
               BEQ             IPOW_POW0       ; (!n)==TRUE, n==0
               btst.b          #1,D1           ; (n & 1)
               BEQ             IPOW_RECURS     ; IPOW(x * x, n>>1)

               move.l          D0,D2
               subq.l          #1,D1           ; n - 1
               BSR             IPOW

               muls.l          D2,D0           ; x *

               BRA             IPOW_END

IPOW_RECURS:   muls.l          D0,D0           ; x * x
               asr.l           #1,D1           ; n >> 1
               BSR             IPOW

               BRA             IPOW_END

IPOW_POW0:     moveq.l         #1,D0           ; return 1
IPOW_END:      movem.l         (SP)+,D1-D2

               RTS

int SQRT
( int n
)
{
  int r = 0;
  int b;
  int t;
  
  b
  = (n >= 0x10000)
    ? 1 << 30
    : 1 << 14
  ;
  
  do
  {
    t = r + b;
    
    if(n >= t)
    {
      n -= t;
      r = t + b;
    }
    
    r >>= 1;
    b >>= 2;
  }while(b);
  
  return r;
}

; SQRT by Kochise
               move.l          #1024,D0        ; x
               BSR             IPOW
               cmpi.l          #32,D0          ; SQRT(1024) = 32
               ...

SQRT:          movem.l         D1-D3,-(SP)
               clr.l           D1
               cmpi.l          #$00010000,D0   ; n >= 0x10000
               BGE             SQRT_B30

               move.l          #$00004000,D2   ; b = 1 << 14

               BRA             SQRT_LOOP

SQRT_B30:      move.l          #$40000000,D2   ; b = 1 << 30

SQRT_LOOP:     move.l          D1,D3
               add.l           D2,D3

               cmp.l           D0,D3
               BLT             SQRT_NEXT

               sub.l           D3,D0           ; n -= t

               move.l          D2,D1
               add.l           D3,D1           ; r = t + b

SQRT_NEXT:     asr.l           #1,D1           ; r >>= 1
               asr.l           #2,D2           ; b >>= 2

               tst.l           D1
               BNE             SQRT_LOOP
               
               move.l          D1,D0           ; return r

SQRT_END:      movem.l         (SP)+,D1-D3

               RTS

int HASH
( const char* c
, int s = 0
)
{
  return
  (*c != 0)
  ? HASH(c + 1,s + 1)
    + (
        (
          (*c | 0x20)
          - 'a'
          + 1
        )
        * IPOW(26, s)
      )
  : 0
  ;
}

; HASH by Kochise
               lea             HASH_TEXT,A0
               BSR             HASH
               ...

HASH:          movem.l         D1-D3/A0-A1,-(SP)
               clr.l           D0
               clr.l           D2
               movea.l         A0,A1

HASH_LOOP:     move.b          (A1)+,D2
               BEQ             HASH_END        ; *c == 0

               ori.l           #$00000020,D2   ; *c | 0x20
               sub.l           #96,D2          ; - 'a' + 1
               move.l          D0,D3

               move.l          A1,D1
               move.l          A0,D0
               sub.l           D0,D1
               move.l          #26,D0
               BSR             IPOW            ; IPOW(26, s)

               muls.l          D2,D0
               add.l           D3,D0

               clr.l           D2

               BRA             HASH_LOOP

HASH_END:      movem.l         (SP)+,D1-D3/A0-A1

               RTS

               SECTION         DATA
HASH_TEXT:     dc.b            "Hash me steady",0

Kochise

sqrt ne marche toujours pas
j'ai lancé la meme discussion sur atari-forum, qq solutions interressantes que je vais tester !

(et ton C est vraiment les plus illisble que j'ai lu )

Azrael t'est passé ou ? Je comprends rien au C !

Voir si lui il capte quelque chose ou puisse optimisé la chose !



GT Turbo

Normal que mon C soit illisible, c'est du C PUNCH !

Kochise

lol, je me moquais, dans mes phases poete j'ecris des trucs completement esoteriques

tobe :
j'ai pas cherché a l'optimiser plus que ca, si qqun veut le faire, je suis preneur !

Faut que j'attrapes Azrael, on va tenté une optimisation et peut ètre un 'code de bourrin' quoique la dessus cela va etre chaud chaud !


GT Un gros bourrin

GT Turbo :

Faut que j'attrapes Azrael, on va tenté une optimisation et peut ètre un 'code de bourrin' quoique la dessus cela va etre chaud chaud !

Dr. Azrael s'il te plait !



bon, j'essaie de t'appeler désespérément depuis 2 jours, donc si t'es pas là non plus, comment on fait pour optimiser ?



Az... qui commence à enfler de la citrouille. Pas bon du tout...

j'ai codé un framework pour valider les routines et comparer les vitesses, donc des que vous avez qqchose je pourrais l'ajouter.
pour l'instant j'ai la routine que j'ai porté, celle proposé par Earx et celle proposé par Nyh. J'ai pas inclus celle de Protos car elle utilise des opcodes a partir du 68020.

@Kochise, la tienne semble prometteuse, dis, tu peux verfier le code que je l'ajoute ?

pour l'instant la routine de Earx est la plus rapide et la plus precise :

fast_sqrt:
	movem.l		d1-d3,			-(sp)
	moveq		#1,				d2
	ror.l		#2,				d2
	moveq		#$F,			d3
.loop1:
	cmp.l		d2,				d0
	bgt.s		.endloop1
	add.l		d0,				d0
	lsr.l		#1,				d2
	dbf			d3,.loop1
	moveq		#0,				d1
	bra.s		.is_null
.endloop1:
	sub.l		d2,				d0
	move.l		d2,				d1
	lsr.l		#1,				d2
.loop2:
	lsr.l		#1,				d2
	add.l		d2,				d1
	cmp.l		d1,				d0
	bgt.s		.endloop2
	sub.l		d2,				d1
	add.l		d0,				d0
	dbf			d3,.loop2
	bra.s		.end
.endloop2:
	sub.l		d1,				d0
	add.l		d2,				d1
	add.l		d0,				d0
	dbf			d3,.loop2
.end:
	add.l		d1,				d1
	addi.l		#$00008000,		d1
.is_null:
	swap		d1
	move.w		d1,				d0
	movem.l		(sp+),			d1-d3
	rts

en plus, si vous remplacez les deux lignes avant rts par : move.l d1, d0, vous obtenez le resultat dans le mot de poids fort et le reste dans le poids faible !

Kochise :
Comme promis, j'ai fait concis...

int IPOW(int x, int n){return (!n)?1: (n&1)?x*IPOW(x,n-1):IPOW(x*x,n>>1);}
int SQRT(int n){int r=0,b,t; b=(n>=0x10000)?1<<30:1<<14; do{t=r+b; if(n>=t){n-=t; r=t+b;} r>>=1; b>>=2;}while(b); return r;}

Kochise

PS : Concis, pas circoncis !

Pas concis, c'est tres crade ... les \n coutent pas cher aujourd'hui Enfin je dis ca mais je dis rien ;o)

skweek :
Pas concis, c'est tres crade ... les \n coutent pas cher aujourd'hui Enfin je dis ca mais je dis rien ;o)

Kochise :
Normal que mon C soit illisible, c'est du C PUNCH !

Kochise

A l'origine, je l'avait codé sous forme de macro, ce qui fait que c'est le compilo qui me générait un résultat fixe à la compilation, plutôt que de le calculer en runtime.

tobe :
@Kochise, la tienne semble prometteuse, dis, tu peux verfier le code que je l'ajoute ?

Je vais la vérifier et surtout l'optimiser un peu. Comme t'as pu le voir, je n'ai pas utilisé de SWAP ($4000 <-> $4000000) pour rester le plus proche possible du C afin d'aider les néophytes (genre GT) à bien voir les similitudes entre la version C et ASM

Mais je vais te faire ça dans la semaine si j'ai un peu de temps

Kochise

Je vais la vérifier et surtout l'optimiser un peu. Comme t'as pu le voir, je n'ai pas utilisé de SWAP ($4000 <-> $4000000) pour rester le plus proche possible du C afin d'aider les néophytes (genre GT) à bien voir les similitudes entre la version C et ASM

Mon cher Kochise, le méga néophyte que je suis en C, t'em.......betes ! Ce n'est pas la peine de te faire c.....r pour moi avec du C, j'en ai rien mais alors rien a f.... !

Dans les démos et les jeux c'est des tables, tu me diras cela permet de généré la table plus vite mais de combien ? Sur Falcon la table je la fais au 68882 et puis zoum !


GT En guerre contre le C ! Asm is the best, forget the rest !

Sachant que mon OS est/sera codé en majeure partie en C et TOP - PAS C++ - (les noyaux et autres gestionnaires, le reste en ASM natif à chaque plateforme), tu auras du mal à comprendre les sources une fois diffusées. Tu ferais mieux de t'y mettre, au C, au lieu de te la jouer Don Quichotte de l'ASM, tu me remercieras plus tard...

Kochise

GT : tous les Falcon n'ont pas de 68882 de mémoire.
Tu ferais mieux de te fixer un hard cible et de t'y tenir, genre STF

Sachant que mon OS est/sera codé en majeure partie en C et TOP - PAS C++ - (les noyaux et autres gestionnaires, le reste en ASM natif à chaque plateforme), tu auras du mal à comprendre les sources une fois diffusées. Tu ferais mieux de t'y mettre, au C, au lieu de te la jouer Don Quichotte de l'ASM, tu me remercieras plus tard...

Maintenant on sait pourquoi le GEM rame ! Il y a des fous furieux du C !

GT : tous les Falcon n'ont pas de 68882 de mémoire. Tu ferais mieux de te fixer un hard cible et de t'y tenir, genre STF

D'accord avec toi Fadest pour le 68882, mais hors de question que je retournes au STF Coding ! Malgré que j'adaptes certaines routines pour le STF (demande de certaines personnes), le simple fait de pouvoir utilisé les joypads me manquerait. Je sais c'est bete, mais je suis (encore) d'accord avec Cooper, le Jagpad est très pratique, regardez simplement le bouton pause, pas besoin de courir sur le clavier pour essayé d'appuyer sur Pause, et encore faut il se souvenir de la touche qui fait pause !

Dans le pire des cas faites comme Templeton (Qui est encore en train de soudé ces prises ! lol !). Si je me fixes une 'hard-cible' c'est minimun le Ste et sinon Falcon (Mais de base, quitte a généré un fichier avec les racines carrés !). Je me suis assez embetez a écrire des routines joypads, maintenant je comptes bien les utilisez. En passant, la routine joypad que j'avais postez ici, cela interresse certaines personnes de pouvoir l'utilisez en Gfa ? Cela serait très vite adaptable et pourrait servir certaines personnes, attention routine Falcon (68030 mini), je ferais peut ètre pareil pour une routine Ste Gfa, mais il me faut assez de demande, je ne veux pas codé juste pour deux gars perdus du coté de Gisors !!


GT sans le turbo !

GT Turbo :
Maintenant on sait pourquoi le GEM rame ! Il y a des fous furieux du C !

Quand tu auras désassemblé un peu le TOS (pour jouer au docteur), tu comprendras qu'il est pas trop bien codé à la base. Ca aurait donné le même résultat en ASM. Plutôt que de faire des boucles itératives pour faire le clipping (c'est qu'un exemple), ils auraient pu par exemple faire un tri dichotomique. Résultat identique en C et ASM = vitesse de l'éclair en log(n).

De plus de gestionnaire de mémoire est une vraie tortue, et l'AES/VDI arretent pas d'y faire appel !

Kochise

Kochise
:

GT Turbo :
Maintenant on sait pourquoi le GEM rame ! Il y a des fous furieux du C !

Quand tu auras désassemblé un peu le TOS (pour jouer au docteur), tu comprendras qu'il est pas trop bien codé à la base. Ca aurait donné le même résultat en ASM. Plutôt que de faire des boucles itératives pour faire le clipping (c'est qu'un exemple), ils auraient pu par exemple faire un tri dichotomique. Résultat identique en C et ASM = vitesse de l'éclair en log(n).

De plus de gestionnaire de mémoire est une vraie tortue, et l'AES/VDI arretent pas d'y faire appel !

Kochise

Log(n) en asm est plus rapide qu'en C !! C'est une querelle de clocher mais bon faut bien s'occupé !!

GT Sous la pluie !!

GT Turbo :
Log(n) en asm est plus rapide qu'en C !! C'est une querelle de clocher mais bon faut bien s'occupé !!

J'ai pas dit calculer log(n), j'ai voulu dire que le temps de recherche dans un tri dichotomique n'est pas linéaire mais constant et égal à log(n) où n est la profondeur de recherche (le degré de complexité du tableau)...

Kochise

Kochise
:

GT Turbo :
Log(n) en asm est plus rapide qu'en C !! C'est une querelle de clocher mais bon faut bien s'occupé !!

J'ai pas dit calculer log(n), j'ai voulu dire que le temps de recherche dans un tri dichotomique n'est pas linéaire mais constant et égal à log(n) où n est la profondeur de recherche (le degré de complexité du tableau)...

Kochise

Je te rassure, je n'ai pas ton niveau, mais je sais que tu ne parlais pas de calculé log(n), j'ai eu l'occasion de faire quelques recherches la dessus, pour faire du tri de tableau !!

Ce que je voulais dire c'est que l'asm est quand meme plus rapide !! Hihi !! Et meme si je joues le don quichotte de l'asm, je resterais un fan de ce langage !!


GT Motorola !!

GT Turbo :
Ce que je voulais dire c'est que l'asm est quand meme plus rapide !! Hihi !! Et meme si je joues le don quichotte de l'asm, je resterais un fan de ce langage !!

Mais moi aussi, mon p'tit GT ASM, moi aussi... Simplement un bon outil appelé 'C' à été mis au point, et c'est pratique de l'utiliser quand c'est nécessaire !

Kochise

'C' e n'était pas necessaire de dvp un tel outil, vu mon super Q.I., l'asm me convient mieux, parce qu'il permet de faire des choses elementaires comme moi (Moi mangé, moi faire dodo, etc..) l'asm c'est pareil, c'est primaire mais c'est pour cela que j'aime ce langage !!


GT Un peu bete !!

Alors y'a des programmeurs (surtout C++, C#, XML, ...) qui ne savent pas/plus êtres bêtes !

Kochise