ASM

Comment inverser les bits d'un octet ?

Recherche :

Mot : Pseudo : Filtrer
Page : 1 2 Page Suivante Page Précédente Bas de page
Auteur	Sujet : Comment inverser les bits d'un octet ?

AthlonSoldier

Feel the power

Salut,

J'aimerai par exemple passer de 01110001 à 10001110.
C'est à dire que le 1er bit se retrouve en 8ieme position, le 2nd en 7 ieme etc...
J'ai bien réfléchis et a pars faire un algo assez long je vois pas trop (avec des ror, and etc... et surtout en se servant de 2 registres (j'aimerai en avoir qu'un)).

Quelqu'un a une idée ?

Publicité

jesus_christ

votre nouveau dieu

si ton octet est dans al et que eax est utilisable :

xor ah, ah
REPEAT 8
shl ah, 1
shr al, 1
adc ah, 0
ENDM

le résultat est dans ah

Message édité par jesus_christ le 02-09-2004 à 17:10:29

AthlonSoldier

Feel the power

Ah oué voila c'est tres long [:zoutte]
Y'a vraiment rien de plus simple ? :??:

EDIT : Merci en tout cas

Message édité par AthlonSoldier le 02-09-2004 à 17:16:39

jesus_christ

votre nouveau dieu

AthlonSoldier a écrit :

Ah oué voila c'est tres long [:zoutte]
Y'a vraiment rien de plus simple ? :??:

de rien
long ?
t'as déjà fait du RISC ? ça c'est ce que j'appelle long.

Cette boucle est déroulée, enroulé avec un loop ça ferait 6 lignes. C'est pas énorme. Il y a des bonnes méthodes pour inverser les octets d'un WORD ou d'un DWORD, mais pas les bits, ou alors c'est un truc tordu que je connais pas.

Kristoph

Si c'est juste les bits d'un octet, je suggère soit la table de lookup à 256 entrées, soit une table à 16 entrées mais on fait 2 lookup dedans, une fois pour les 4 bits de poids faible et une fois pour ceux de poids fort

AthlonSoldier

Feel the power

C'est à dire ? :??:

Kristoph

AthlonSoldier a écrit :

C'est à dire ? :??:

Tu crée en mémoire une fois pour toute un tableau à 256 entrées représentant la transformation que tu veux faire. Après il suffit de faire ( exemple en C ) :

Code :

def inverser_bits(unsigned char octet)
{
return table_lookup[octet];
}

Message édité par Kristoph le 02-09-2004 à 17:54:36

AthlonSoldier

Feel the power

Je pense que c'est tres lent ca, vu qu'il y a acces mémoire :??:
Quelqu'un peut dire a vue d'oeuil si c plus rapide que de faire une boucle en asm (celle de jesus_christ) ? :??:

Kristoph

Une fois le tableau en cache ce qui n'est vraiment pas difficile pour un tableau de 256 octets, c'est certainement beaucoup plus rapide que la boucle vue ci dessus. Le seul point litigieux serait pour le cas ou le resultat obtenu influe sur la prediction de branchement dans les quelques instructions suivantes.

jesus_christ

votre nouveau dieu

ouais l'option de kris semble la meilleure, 256 octets ça rentre dans le L1. T'aura un AGI stall à chaque accès mais ça doit être + rapide qu'une boucle qui tourne 8 fois.

Publicité

prorel

jesus_christ a écrit :

si ton octet est dans al et que eax est utilisable :

xor ah, ah
REPEAT 8
shl ah, 1
shr al, 1
adc ah, 0
ENDM

le résultat est dans ah

on peut chippoter un peu et preferer utiliser
rol al,1
rcr ah,1

ca evite l'instruction adc, puisque la rotation passe par le carry

Message édité par prorel le 03-09-2004 à 00:23:10

AthlonSoldier

Feel the power

prorel a écrit :

on peut chippoter un peu et preferer utiliser
rol al,1
rcr ah,1

ca evite l'instruction adc, puisque la rotation passe par le carry

Merci :jap:

jesus_christ

votre nouveau dieu

prorel a écrit :

on peut chippoter un peu et preferer utiliser
rol al,1
rcr ah,1

ca evite l'instruction adc, puisque la rotation passe par le carry

bien vu !!! ça shift et ajoute le bit de poids faible en une instruction
je mettrai alors

shl al,1
rcr ah,1

vu que la première rotation ne sert à sortir le bit de poids fort, shift est suffisant et + rapide que la rotation sur la plupart des cpu (tous ?).

prorel

exact, rcr ne prend qu'1 cycle (a partir du p1), alors que shl en prend 3

bravo!

jesus_christ

votre nouveau dieu

prorel a écrit :

exact, rcr ne prend qu'1 cycle (a partir du p1), alors que shl en prend 3

bravo!

euh c'est pas le contraire ?

prorel

nan d'apres le bouquin, c'est bien "rcr reg,1" qui prend 1 cycle

jesus_christ

votre nouveau dieu

j'ai vérifié dans mon bouquin (JB Emond) et les deux opérations

rcr reg, 1
shl reg, 1

prennent toutes les 2 un seul cycle.
Ca serait trop étrange qu'un rotate (peu utilisé) prennent plus de place qu'un shift (très utilisé)

prorel

pour quel proc??
j'ai pas le p4

atention il faut aussi tenir compte de la mise a jour du reg status,
d'apres ma doc
rcr met a jour carry et overflow, alors que shl met a jour Overflow, sign,zero, aux carry, parity, et carry
ca vient ptet de là??

christophe_d13

L'efficacité à tout prix.

Je viens de me creuser la cervelle... ça m'arrive :hello:

J'ai donc trouver une autre technique. Celle-ci est beaucoup plus rapide. Donc... (c) Christophe Gossa, Tous droits réservés.

En fait on va décomposer l'opération successivement. En 3 étapes :
- Permutation des 2 quartets (2x4 bits)
- Permutation des 4 paire de bits (4x2 bits)
- Permutation finale des 8 bits (8x1 bits)

Voici un exemple : On ne verra que la représentation des 8 bits (0 à 7)

La source :
76543210

Etape 1/3
Le paquet A = 7654xxxx
Le paquet B = xxxx3210
On effectu deux décalages et on finit par un OU :
S = (A SHR 4) OU (B SHL 4)
S = 32107654

Etape 2/3
Le paquet A = 32xx76xx
Le paquet B = xx10xx54
Idem...
S = (A SHR 2) OU (B SHL 2)
S = 10325476

Etape 3/3
Le paquet A = 1x3x5x7x
Le paquet B = x0x2x4x6
Idem...
S = (A SHR 1) OU (B SHL 1)
S = 01234567

(c) Christophe Gossa, Tous droits réservés.

Total des instructions :
- 6x décalages
- 6x masques (ET)
- 6x OU

Message édité par christophe_d13 le 03-09-2004 à 20:27:36

prorel

hum
je ne vois pas bien ton truc
pour que ca marche tu dois rajouter les masquage des bits inutiles, sinon avec tes OU tu vas avoir des 1 partout

christophe_d13

L'efficacité à tout prix.

Petit code vite fait pour illustrer avec l'explication...

Code :

mov al, Source //al = 76543210
mov bl, al //bl = 76543210
shr al, 4 //al = xxxx7654
shl bl, 4 //bl = 3210xxxx
or al, bl //al = 32107654
mov bl, al //bl = 32107654
and al, 0xCC //al = 32xx76xx
and bl, 0x33 //bl = xx10xx54
shr al, 2 //al = xx32xx76
shl bl, 2 //bl = 10xx54xx
or al, bl //al = 10325476
mov bl, al //bl = 10325476
and al, 0xAA //al = 1x3x5x7x
and bl, 0x55 //bl = x0x2x4x6
shr al, 1 //al = x1x3x5x7
shl bl, 1 //bl = 0x2x4x6x
or al, bl //al = 01234567
(c) Christophe Gossa, Tous droits réservés.

christophe_d13

L'efficacité à tout prix.

Résultat sur un Barton :
10 cycles en boucle.

On peut dire que le re-ordering du cpu est assez efficace, mais le code est plus efficace pour du 2 canaux que pour le 3 canaux des amd.

Mr Mala

je n'ai qu'une chose à dire : :jap:

prorel

christophe_d13 a écrit :

Résultat sur un Barton :
10 cycles en boucle.

On peut dire que le re-ordering du cpu est assez efficace, mais le code est plus efficace pour du 2 canaux que pour le 3 canaux des amd.

:jap: beau travail
et le programme "classique" il prend combien de cycles??

deumilcat

je débarque peut etre avec mes vieux souvenirs d assembleur zx80 mais.. un XOR ca existe pas sur ASMx86?

EDIT: faites pas attention j avais compris autre chose par "inverser les bits d un octet": mettre des O a la place des 1 et des 1 a la place des 0.. j avais pas lu la question en entier.. Je vais dormir :sleep:

Message édité par deumilcat le 03-09-2004 à 23:40:09

prorel

deumilcat a écrit :

je débarque peut etre avec mes vieux souvenirs d assembleur zx80 mais.. un XOR ca existe pas sur ASMx86?

si, mais tu veux le mettre ou??

deumilcat

prorel a écrit :

si, mais tu veux le mettre ou??

EDIT: faites pas attention j avais compris autre chose par "inverser les bits d un octet": mettre des O a la place des 1 et des 1 a la place des 0.. j avais pas lu la question en entier.. Je vais dormir :sleep:

Message édité par deumilcat le 03-09-2004 à 23:40:24

prorel

pas grave

AthlonSoldier

Feel the power

deumilcat a écrit :

C'est NOT ca [:ddr555]

christophe_d13

L'efficacité à tout prix.

Résultat de la comparaison :

Code :

Méthode #1
xor ah, ah
REPEAT 8
shl ah, 1
shr al, 1
adc ah, 0
ENDM

25 cycles !

Code :

Méthode #2
xor ah, ah
REPEAT 8
shl al,1
rcr ah,1
adc ah, 0
ENDM

24 cycles !

Code :

Méthode #3
Permutation à 3 étages de décomposition

10 cycles !

Code :

Méthode #4
Utilisation d'une LUT

3 cycles !

Sous forme de mini-tableau
#1 =========================
#2 ========================
#3 ==========
#4 ===

Toutes ces mesures sont faites dans une boucle de 1.000.000. Donc le code est dans le cache et se trouve paralélisé.

Message édité par christophe_d13 le 04-09-2004 à 00:07:26

prorel

dans le cas 2 tu n'a pas besoin du "adc ah,0"
mais bon, c'est chippoter

c'est clair que la table c'est le mieux si c'est juste avec 256 octets et qu'il y a un traitemnt lourd derriere

christophe_d13

L'efficacité à tout prix.

prorel> Tout dépend de l'usage. Dans le cas où la routine est appelé assez rarement, ou bien que juste avant le cache est altéré, il faudra choisir la meilleure routine.
Les pénalités sur AthlonXP+nForce2 si les données sont en :
RAM - >180 cycles
L2 - 20 cycles
L1 - 3 cycles.

Message édité par christophe_d13 le 04-09-2004 à 00:17:08

prorel

on peut faire un compromis

lancer la premiere fois le prog 1 qui charge la table, et les appels suivants on passe par la table

christophe_d13

L'efficacité à tout prix.

prorel> Oui, mais si pour les appels suivants la table n'est pas dans L1 ? On passe à 20 cycles !

A l'inverse si on sait que l'on parcourera toute la table, on peut faire un software-block-prefetch en lisant simplement les offsets 0, 32, 64, 96... jqà 224 pour un ligne de 32 octets et 0, 64, 128 et 192 pour une ligne de cache de 64 octets.

Message édité par christophe_d13 le 04-09-2004 à 00:34:01

prorel

vi, c'est clair

christophe_d13

L'efficacité à tout prix.

Il n'y a jamais de meilleures méthodes, juste des compromis.

Bonne nuit ! :sleep: :sleep: :sleep:

Message édité par christophe_d13 le 04-09-2004 à 00:35:05

prorel

:hello:

AthlonSoldier

Feel the power

C'est gentil d'essayer de faire le code le plus optimisé pour ma simple question :jap: :jap:

jesus_christ

votre nouveau dieu

je voudrais pas chipoter mais un rotate 4 sur al dans la méthode de chris (jolie d'ailleurs :jap: ) au lieu de la 1ere étape ça serait pas + rapide ?
et puis dans la méthode #2 il n'y a pas de adc, sinon le code est faux.

Message édité par jesus_christ le 04-09-2004 à 21:51:51

christophe_d13

L'efficacité à tout prix.

Bien vu mais bon c'est un premier jet, je n'ai pas cherché à faire le plus rapide. Juste expliquer en ASM ma méthode.
Up> Et puis il fallait vraiment voir les 3 étapes. Mais ceci dit en ajoutant la rotation, on gagne 2 cycles. soit 8 cycles seulement.
Il est encore posible d'améliorer le code... D'après mon analyse je pense que l'on peut tomber le nombre de rotation à 3 à cause de la récurence et il doit être possible de grouper l'étape 1 et 2.

Up #2> Et bien c'est fait, 7 cycles seulement, simplement en analyse.

Le code et l'explication

Code :

mov al, Source //al = 76543210
mov bl, al //al = 76543210
rol al, 1 //al = 65432107
rol bl, 5 //bl = 21076543
and al, 0x99 //al = 6xx32xx7
and bl, 0x66 //bl = x10xx54x
or al, bl //al = 61032547
mov bl, al //bl = 61032547
and al, 0x55 //al = x1x3x5x7
and bl, 0xAA //bl = 6x0x2x4x
rol bl, 2 //bl = 0x2x4x6x
or al, bl //al = 01234567

Aucune optimisation de bas niveau, juste une reflexion sur l'algo.
Donc, 7 cycles.

Message édité par christophe_d13 le 05-09-2004 à 09:43:06

Publicité

Page : 1 2

Page Suivante

Page Précédente

Haut de page

FORUM HardWare.fr

Programmation

ASM

Comment inverser les bits d'un octet ?

Sujets relatifs
Lire la valeur de la couleur d'un pixel en 800*600 en 32 bits ?	conversion en bits
conversion des décimaux en bits	[RESOLU]Convertir un entier en HEXA sur un nombre de bits
[PHP] Conversion fichier .tif en .png 24 bits	programmation 32 bits
Inverser l'axe Y de Graphics	[debutant] 1 ko = 1000 ou 1024 octet ?
[Visual c++] convertir une taille en Octet automatiquement 2	[Visual c++] convertir une taille en Octet automatiquement
Plus de sujets relatifs à : Comment inverser les bits d'un octet ?

Page générée en 0.098 secondes