Manipulation de bits : C vs ASM

Version imprimable

31/08/2008, 15h03
Obsidian

Manipulation de bits : C vs ASM

UPDATE : Fil déplacé (la discussion originale avait commencé ici : http://www.developpez.net/forums/d60...ilier-sprintf/ )

Citation:

Envoyé par Jean-Marc.Bourguet

Mince alors... je l'ai fait sans assembleur. Pire, je ne vois pas en quoi l'assembleur aide beaucoup -- enfin, un peu les perfs du calcul entier multiprécision qui est nécessaire, mais les drapeaux de controles de la FPU n'aident pas beaucoup pour cela.

Alors, d'un point de vue complètement parallèle à cette discussion, je peux témoigner qu'il est beaucoup plus confortable de coder en assembleur les routines de calcul arithmétique et logique, notamment grâce aux facilités de manipulation de bits. L'exemple le plus direct est la rotation des bits d'un entier de longueur arbitraire. Quand on fait un décalage d'un bit, on peut utiliser directement la retenue du processeur et faire des ROL en cascade. Sur Intel, il existe même des instruction de manipulation de chaîne, comme LODS, STOS, MOVS et le préfixe répétiteur REP. Bref, tout ce qu'il faut pour faire de la manipulation de données, principale tâche du CPU.

En C, il n'y a - à ma connaissance (quiquonque peut élargir le cercle de mes connaissances étant le bienvenu) - pas de manière facile d'extraire un bit sortant. Le plus rapide que j'ai trouvé pour récupérer la valeur du bit de poids fort d'un entier quelquonque et le ramener en première position en évitant les sauts conditionnels est :

Code:

((x & (~0 >> 1))-1)&1)

Ça a l'avantage d'utiliser des instructions fondamentales et implicites (potentiellement sans accès au bus) du microprocesseur. Par contre, ça s'éloigne beaucoup, dans la syntaxe, de l'algo initial et le compilateur aura bien du mal à faire les optimisations nécessaires.

Un autre exemple : les trois instructions de mon post #9 dans cette discussion : http://www.developpez.net/forums/d58...r/#post3552842

Difficile d'expliquer çà au C, même si celui-ci y met la meilleure volonté du monde.
31/08/2008, 17h39
Jean-Marc.Bourguet
Citation:

Envoyé par Obsidian

En C, il n'y a - à ma connaissance (quiquonque peut élargir le cercle de mes connaissances étant le bienvenu) - pas de manière facile d'extraire un bit sortant. Le plus rapide que j'ai trouvé pour récupérer la valeur du bit de poids fort d'un entier quelquonque et le ramener en première position en évitant les sauts conditionnels est :

Code:

((x & (~0 >> 1))-1)&1)

J'ai du mal à comprendre ce code. 0 est une typo pour 0U (sinon ~0 est signé et le déclage a un comportement indéfini, souvent ça conserve le signe et donc le décalage n'est pas très utile) mais 4 parenthèses qui se ferment, 3 qui s'ouvrent et je n'arrive pas à placer la parenthèse ouvrante manquante de manière à avoir le résultat demandé.

Si x est signé, l'expression évidente est

Code:

(x < 0)

Si x est non signé,
Code:

1 2 3 x >> 31 x >= 0x80000000 (x & 0x80000000) != 0
font l'affaire. 0x800000 peut être remplacé par ~(~0U >> 1)) de manière à être indépendant de la taille des entiers, mais je ne connais rien d'aussi simple pour remplacer le 31(CHAR_BIT*sizeof int -1 est le plus simple mais foire dans le cas conforme mais peu courant de présence de bits ne participant pas à la valeur dans l'int).

Dans chaque cas, gcc me génère le même code:
Code:

1 2 testl %edx, %edx js .L15
ou

Code:

shrl $31, %ebx

suivant le contexte (demandant un saut ou assignation). Ca qui me semble assez bon (mais cela fait 10 ans que je n'ai plus fait d'assembleur, je manque peut-être l'évident).
31/08/2008, 18h37
Obsidian
Citation:

Envoyé par Jean-Marc.Bourguet

mais 4 parenthèses qui se ferment, 3 qui s'ouvrent et je n'arrive pas à placer la parenthèse ouvrante manquante de manière à avoir le résultat demandé.

Faute de frappe de ma part, désolé !

Citation:

peut être remplacé par ~(~0U >> 1)) de manière à être indépendant de la taille des entiers, mais je ne connais rien d'aussi simple pour remplacer le 31(CHAR_BIT*sizeof int -1 est le plus simple mais foire dans le cas conforme mais peu courant de présence de bits ne participant pas à la valeur dans l'int).

C'était l'idée, effectivement.
Citation:
Dans chaque cas, gcc me génère le même code:

Code:

1 2 testl %edx, %edx js .L15

ou

Code:

shrl $31, %ebx

suivant le contexte (demandant un saut ou assignation). Ca qui me semble assez bon (mais cela fait 10 ans que je n'ai plus fait d'assembleur, je manque peut-être l'évident).
Imparable pour GCC, mais l'essentiel demeure : il reste difficile de faire proprement une transmission de bits d'un champs à l'autre et surtout, il n'y a pas moyen de l'exprimer proprement en C (ni dans d'autres langages). Ici, on s'est démerdé pour que le résultat final extraie un bit et GCC a été suffisamment performant pour le comprendre et appliquer la bonne technique, mais il n'est pas du tout certain qu'il soit capable de s'y retrouver dans une équation un peu plus compliquée.

Sémantiquement, c'est génant : dire que l'on fait un calcul qui se traduit dans les faits par un décalage de bits ne permet pas du tout d'affirmer clairement que c'est cela qu'on cherche à faire au final.

Et puis SHRL $31, c'est ce que je cherche à éviter : ça tient en une instruction mais le nombre de cycles est probablement élevé, et ça ne marche pas sur tous les CPU : bon nombre d'entre eux ne proposent qu'un décalage au niveau du bit et il faut alors 31 opcodes pour arriver à ses fins.
31/08/2008, 19h41
Jean-Marc.Bourguet

Citation:

Envoyé par Obsidian

Imparable pour GCC, mais l'essentiel demeure : il reste difficile de faire proprement une transmission de bits d'un champs à l'autre et surtout, il n'y a pas moyen de l'exprimer proprement en C (ni dans d'autres langages).

En C

Code:

x.f1 = y.f2;

En Ada

Code:

x.f1 := y.f2

Et même si on n'utilise pas les champs comme ça,

Code:

x = (x & NOT_X_MASK) | ((y & Y_MASK) >> XY_OFFSET);

est très proche de ce que j'écrirais en assembleur.

Une chose qui est plus compliquée, ce sont les rotations (bien que compilateurs les détectent généralement quand elles sont constantes).

Une autre c'est l'utilisation de résultats annexes des opérations qui ont généralement plusieurs résultats en assembleur (carry, partie haute d'une multiplication, reste d'une division, ...).

Citation:

Ici, on s'est démerdé pour que le résultat final extraie un bit et GCC a été suffisamment performant pour le comprendre et appliquer la bonne technique, mais il n'est pas du tout certain qu'il soit capable de s'y retrouver dans une équation un peu plus compliquée.

Sémantiquement, c'est génant : dire que l'on fait un calcul qui se traduit dans les faits par un décalage de bits ne permet pas du tout d'affirmer clairement que c'est cela qu'on cherche à faire au final.

Bizarre, j'ai quatres expressions qui la traduction directe en C des quatres sémantiques que je vois à la chose de plus bas niveau.

Citation:

Et puis SHRL $31, c'est ce que je cherche à éviter : ça tient en une instruction mais le nombre de cycles est probablement élevé, et ça ne marche pas sur tous les CPU : bon nombre d'entre eux ne proposent qu'un décalage au niveau du bit et il faut alors 31 opcodes pour arriver à ses fins.

L'optimiseur fait son boulot: tu écris x < 0, il génère un décalage parce que sur cette cible c'est le plus efficace et tu n'es pas content parce que sur une autre cible ça pourrait ne pas convenir?