Inverser l'ordre des bits - Page 1

Connaissez vous un algo rapide pour inverser les bits d'un integer en C sans utiliser de tableau ?

Voilà une fonction en assembleur A68k que tu peux linker avec ton fichier C (crée un fichier A68k dans ton projet TIGCC et mets mon code dedans).

 section ".data"
 xdef reverse_short
reverse_short:
 move.w 4(a7),d1
 moveq.l #15,d2
loop:
 add.w d1,d1
 roxr.w #1,d0
 dbra d2,loop
 rts

Le prototype en C corresponsant est: extern unsigned short reverse_short(unsigned short);.

Merci mais il n'y aurait pas une erreur ?

Et ça serait quoi, l'erreur?

roxr.w #1,d0 y a quoi dans d0 ?

Tu t'en fiches. Après les 16 (15 + 1) tours de la boucle, il ne reste plus rien de ce qu'il y avait dans d0.w à l'origine. Tous les 16 bits seront ceux du résultat. (Les autres 16 bits du registre d0 ne sont pas utilisés, on utilise juste d0.w, et c'est représenté en C par le fait que la fonction renvoie un unsigned short, pas un unsigned long.)
[edit]Edité par Kevin Kofler le 16-11-2001 à 22:02:46[/edit]

lol ça me dit quelque chose, hein Kevin

Je pense que ce qu'il voulait dire est que tu as fait une erreur. Cela ne serait pas add.w d1,d0 ? sinon autant faire un lsl.w et supprimer le rolx...

Non, non et encore non, c'est bien add.w d1,d1. Désolé Miles, mais tu n'as rien compris à mon algorithme.

Et effectivement, merci à Thibaut pour le add.w d1,d1 au lieu de lsl.w #1,d1. (C'était dans un topic qui parlait pratiquement de la même chose, mais avec un octet plutôt qu'un mot.) Je n'avais pas pensé à cette optimisation dans ce contexte précis.

Et pour que Jeanpull et Miles comprennent ce que je fais:
add.w d1,d1 "sort" un bit de d1.w par la gauche vers le flag X.
roxr.w #1,d0 "rentre" ce bit du flag X dans d0.w par la gauche (et en ressort un par la droite vers le flag X, mais il n'est pas utilisé - c'est là la "poubelle" pour le contenu d'origine de d0.w).
À la fin, le bit sorti en premier, qui était tout à gauche de d1.w, se retrouve tout au fond, donc tout à droite, de d0.w. Le deuxième se trouve à l'avant-dernière position etc... On a donc bien inversé l'ordre des bits.

En détail:
Soit %abcdefghijklmnop le mot à inverser.
move.w 4(a7),d1 et moveq.l #15,d2 ->
d0.w: %rstuvwxyzSTUVWXY
d1.w: %abcdefghijklmnop
d2.w: 15
X: Z
add.w d1,d1 ->
d0.w: %rstuvwxyzSTUVWXY
d1.w: %bcdefghijklmnop0
d2.w: 15
X: a
roxr.w #1,d0 ->
d0.w: %arstuvwxyzSTUVWX
d1.w: %bcdefghijklmnop0
d2.w: 15
X: Y
dbra d2,loop ->
d0.w: %arstuvwxyzSTUVWX
d1.w: %bcdefghijklmnop0
d2.w: 14
X: Y
add.w d1,d1 ->
d0.w: %arstuvwxyzSTUVWX
d1.w: %cdefghijklmnop00
d2.w: 14
X: b
roxr.w #1,d0 ->
d0.w: %barstuvwxyzSTUVW
d1.w: %cdefghijklmnop00
d2.w: 14
X: X
dbra d2,loop ->
d0.w: %barstuvwxyzSTUVW
d1.w: %cdefghijklmnop00
d2.w: 13
X: X
add.w d1,d1 ->
d0.w: %barstuvwxyzSTUVW
d1.w: %defghijklmnop000
d2.w: 13
X: c
roxr.w #1,d0 ->
d0.w: %cbarstuvwxyzSTUV
d1.w: %defghijklmnop000
d2.w: 13
X: W
dbra d2,loop ->
d0.w: %cbarstuvwxyzSTUV
d1.w: %defghijklmnop000
d2.w: 12
X: W
add.w d1,d1 ->
d0.w: %cbarstuvwxyzSTUV
d1.w: %efghijklmnop0000
d2.w: 12
X: d
roxr.w #1,d0 ->
d0.w: %dcbarstuvwxyzSTU
d1.w: %efghijklmnop0000
d2.w: 12
X: V
dbra d2,loop ->
d0.w: %dcbarstuvwxyzSTU
d1.w: %efghijklmnop0000
d2.w: 11
X: V
add.w d1,d1 ->
d0.w: %dcbarstuvwxyzSTU
d1.w: %fghijklmnop00000
d2.w: 11
X: e
roxr.w #1,d0 ->
d0.w: %edcbarstuvwxyzST
d1.w: %fghijklmnop00000
d2.w: 11
X: U
dbra d2,loop ->
d0.w: %edcbarstuvwxyzST
d1.w: %fghijklmnop00000
d2.w: 10
X: U
add.w d1,d1 ->
d0.w: %edcbarstuvwxyzST
d1.w: %ghijklmnop000000
d2.w: 10
X: f
roxr.w #1,d0 ->
d0.w: %fedcbarstuvwxyzS
d1.w: %ghijklmnop000000
d2.w: 10
X: T
dbra d2,loop ->
d0.w: %fedcbarstuvwxyzS
d1.w: %ghijklmnop000000
d2.w: 9
X: T
add.w d1,d1 ->
d0.w: %fedcbarstuvwxyzS
d1.w: %hijklmnop0000000
d2.w: 9
X: g
roxr.w #1,d0 ->
d0.w: %gfedcbarstuvwxyz
d1.w: %hijklmnop0000000
d2.w: 9
X: S
dbra d2,loop ->
d0.w: %gfedcbarstuvwxyz
d1.w: %hijklmnop0000000
d2.w: 8
X: S
add.w d1,d1 ->
d0.w: %gfedcbarstuvwxyz
d1.w: %ijklmnop00000000
d2.w: 8
X: h
roxr.w #1,d0 ->
d0.w: %hgfedcbarstuvwxy
d1.w: %ijklmnop00000000
d2.w: 8
X: z
dbra d2,loop ->
d0.w: %hgfedcbarstuvwxy
d1.w: %ijklmnop00000000
d2.w: 7
X: z
add.w d1,d1 ->
d0.w: %hgfedcbarstuvwxy
d1.w: %jklmnop000000000
d2.w: 7
X: i
roxr.w #1,d0 ->
d0.w: %ihgfedcbarstuvwx
d1.w: %jklmnop000000000
d2.w: 7
X: y
dbra d2,loop ->
d0.w: %ihgfedcbarstuvwx
d1.w: %jklmnop000000000
d2.w: 6
X: y
add.w d1,d1 ->
d0.w: %ihgfedcbarstuvwx
d1.w: %klmnop0000000000
d2.w: 6
X: j
roxr.w #1,d0 ->
d0.w: %jihgfedcbarstuvw
d1.w: %klmnop0000000000
d2.w: 6
X: x
dbra d2,loop ->
d0.w: %jihgfedcbarstuvw
d1.w: %klmnop0000000000
d2.w: 5
X: x
add.w d1,d1 ->
d0.w: %jihgfedcbarstuvw
d1.w: %lmnop00000000000
d2.w: 5
X: k
roxr.w #1,d0 ->
d0.w: %kjihgfedcbarstuv
d1.w: %lmnop00000000000
d2.w: 5
X: w
dbra d2,loop ->
d0.w: %kjihgfedcbarstuv
d1.w: %lmnop00000000000
d2.w: 4
X: w
add.w d1,d1 ->
d0.w: %kjihgfedcbarstuv
d1.w: %mnop000000000000
d2.w: 4
X: l
roxr.w #1,d0 ->
d0.w: %lkjihgfedcbarstu
d1.w: %mnop000000000000
d2.w: 4
X: v
dbra d2,loop ->
d0.w: %lkjihgfedcbarstu
d1.w: %mnop000000000000
d2.w: 3
X: v
add.w d1,d1 ->
d0.w: %lkjihgfedcbarstu
d1.w: %nop0000000000000
d2.w: 3
X: m
roxr.w #1,d0 ->
d0.w: %mlkjihgfedcbarst
d1.w: %nop0000000000000
d2.w: 3
X: u
dbra d2,loop ->
d0.w: %mlkjihgfedcbarst
d1.w: %nop0000000000000
d2.w: 2
X: u
add.w d1,d1 ->
d0.w: %mlkjihgfedcbarst
d1.w: %op00000000000000
d2.w: 2
X: n
roxr.w #1,d0 ->
d0.w: %nmlkjihgfedcbars
d1.w: %op00000000000000
d2.w: 2
X: t
dbra d2,loop ->
d0.w: %nmlkjihgfedcbars
d1.w: %op00000000000000
d2.w: 1
X: t
add.w d1,d1 ->
d0.w: %nmlkjihgfedcbars
d1.w: %p000000000000000
d2.w: 1
X: o
roxr.w #1,d0 ->
d0.w: %onmlkjihgfedcbar
d1.w: %p000000000000000
d2.w: 1
X: s
dbra d2,loop ->
d0.w: %onmlkjihgfedcbar
d1.w: %p000000000000000
d2.w: 0
X: s
add.w d1,d1 ->
d0.w: %onmlkjihgfedcbar
d1.w: %0000000000000000
d2.w: 0
X: p
roxr.w #1,d0 ->
d0.w: %ponmlkjihgfedcba
d1.w: %0000000000000000
d2.w: 0
X: s
dbra d2,loop ->
d0.w: %ponmlkjihgfedcba
d1.w: %0000000000000000
d2.w: -1
X: s
d2.w=-1, donc la boucle dbra termine.
La valeur de retour dans d0.w est bien %ponmlkjihgfedcba, qui est %abcdefghijklmnop inversé.
[edit]Edité par Kevin Kofler le 20-11-2001 à 04:01:40[/edit]

dsl, j'ai oublié de considérer les side-effects

juste pour savoir, ça peut servir a koi d'inverser l'ordre des bits (je pense que ça doit etre assez vaste)

A inverser verticalement un sprite p.ex.

Horizontalement !

Ta gueule. Tout est relatif

oui, tu ne couches jamais ta calc ? faut bien qu'elle dorme un peu

c vous qui avez fait la traduction de photoshop ?
vous faites la meme erreur (symetrie par / à un axe vert/hz )