Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Nouveau membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2017
    Messages
    29
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 20
    Localisation : Belgique

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2017
    Messages : 29
    Points : 32
    Points
    32

    Par défaut Permutation bit pair/impair

    Bonjour,

    J'essaye de changer la position des bits pair/impaires entre eux, sans succès, j'essayes d'obtenir un résultat similaire à celui-ci:

    Nom : unknown.png
Affichages : 164
Taille : 3,4 Ko

    J'ai déjà tenté de soutirer des réponses à des connaissances, j'ai cru comprendre qu'il fallait utiliser la technique du ''masque" + un décalage gauche/droite + un OR. Cependant la méthode est encore flou pour moi, quelqu'un pourrait-il me donner davantage d'indication?

    Ce que je sais de la technique du masque, c'est qu'elle permet de cibler des bits en particulier, rien de plus.

    Merci beaucoup à ceux qui prendront le temps de m'aider.

  2. #2
    Expert éminent
    Avatar de Kannagi
    Homme Profil pro
    cyber-paléontologue
    Inscrit en
    mai 2010
    Messages
    2 536
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : cyber-paléontologue

    Informations forums :
    Inscription : mai 2010
    Messages : 2 536
    Points : 7 701
    Points
    7 701

    Par défaut

    Le décalage binaire , les masque , OR etc etc ,c'est pas spécifique a l'asm ! :p
    Si tu veux intervertir X0 et X1 par exemple : (X>>1)&0x01 | (X<<1)&0x02
    Et donc tu as la décalage droite/gauche , le OR et bien sur le masque (&0x01 et x0x02).

  3. #3
    Membre actif

    Homme Profil pro
    Retraité
    Inscrit en
    mars 2015
    Messages
    61
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 69
    Localisation : France, Loiret (Centre)

    Informations professionnelles :
    Activité : Retraité

    Informations forums :
    Inscription : mars 2015
    Messages : 61
    Points : 229
    Points
    229

    Par défaut Traitement du problème en assembleur

    C’est assez simple en assembleur malgré le fait que Kannagi s’acharne à voir du C/C++ partout, y compris sur le forum assembleur (éducation des masses, sans doute?) :
    Le process décrit ci-dessous utilise les instructions BT (Bit Test) et RCL (Rotate w/ Carry Left).
    La méthode s'apparente à l'"enfilage de perles".
    Je te renvoie à la doc Intel pour plus de détails.
    Voici ce que je te propose et que je n’ai pas testé (sinon déjà pratiqué dans d’autres programmes)
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    ;--- Conditions initiales
    	Xor ebx,ebx	; ebx = 0
    ; AL contient l’octet à traiter.
    ; le résultat sera dans BL
     
    ;--- Permutations
    	Bt  ax,1	; bit 1 dans Cf
    	Rcl bl,1	; Cf copié dans bit 0 de BL
    	Bt  ax,0	; bit 0 dans Cf
    	Rcl bl,1	; Cf copié dans bit 0 de BL
    	Bt  ax,3	; bit 3 dans Cf
    	Rcl bl,1	; Cf copié dans bit 0 de BL
    	Bt  ax,2	; bit 2 dans Cf
    	Rcl bl,1	; Cf copié dans bit 0 de BL
    	Bt  ax,5	; bit 5 dans Cf
    	Rcl bl,1	; Cf copié dans bit 0 de BL
    	Bt  ax,4	; bit 4 dans Cf
    	Rcl bl,1	; Cf copié dans bit 0 de BL
    	Bt  ax,7	; bit 7 dans Cf
    	Rcl bl,1	; Cf copié dans bit 0 de BL
    	Bt  ax,6	; bit 6 dans Cf
    	Rcl bl,1	; Cf copié dans bit 0 de BL
    Il y a d'autres méthodes et il me semble par ailleurs que les instructions SIMD gèrent certains problèmes de masque.
    Contacte-moi si tu rencontres un problème.

  4. #4
    Expert éminent
    Avatar de Kannagi
    Homme Profil pro
    cyber-paléontologue
    Inscrit en
    mai 2010
    Messages
    2 536
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : cyber-paléontologue

    Informations forums :
    Inscription : mai 2010
    Messages : 2 536
    Points : 7 701
    Points
    7 701

    Par défaut

    Citation Envoyé par Asmou Voir le message
    C’est assez simple en assembleur malgré le fait que Kannagi s’acharne à voir du C/C++ partout, y compris sur le forum assembleur (éducation des masses, sans doute?)
    Je me passerai de ce genre de commentaire ...
    Je lui ai répondu d'un point de vu algorithmique , vu que sa question c'est un probleme d'algo il me semble
    J'ai fait du pseudo code C-like et alors ? Je te rappel aussi que le but de ce forum c'est d'aider les intervenants pas faire leur devoir a leur place ! (et il ne précise pas l'asm utilisé , je pourrais le faire en 6502 ,68000 ou en MIPS etc etc , le choix est large en plus :p )
    Que ça soit en C/C++/ASM , java autre j'écris et je pense mes algo en français , c'est fou hein

  5. #5
    Nouveau membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2017
    Messages
    29
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 20
    Localisation : Belgique

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2017
    Messages : 29
    Points : 32
    Points
    32

    Par défaut

    Bonjour,

    Merci pour vos explications, j'en suis arrivé à ce code (Assembleur 80186) qui réalise correctement ce que j'ai demandé ci-dessus:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
    MOV EAX,36          ;entrée 36 (00 10 01 00)
    MOV EBX,36
    AND EAX,0xAA
    AND EBX,0x55
    ROR EAX,1
    ROL EBX,1
    OR EAX,EBX         ;sortie 24  (00 01 10 00)
    XOR EAX,EAX          
    RET

    Honnêtement, si j'ai réussi à réalisé le code Assembleur, c'est seulement grâce à l'algorithme de Kannagi, sans algorithme tout fait je n'aurai jamais pu y arriver et c'est ça qui me frustre.

    Je voudrais me donner un exercice plus complexe, je ne veux plus échanger les bits pairs/impairs mais je veux changer le bit d'indice 0 avec le bit d'indice 5.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    MOV EAX, 01000101b
    MOV EBX, 01000101b
    Comment réaliser la création du masque pour échanger le bit d'indice 0 avec le bit d'indice 4? Est-ce:

    - 00 01 00 01
    - 11 10 11 10 ?

    J'aimerai réaliser l'exercice (dont j'ai crée l'intitulé pour m'exercer) à vos côtés pour mieux manipuler les bits. Merci!

  6. #6
    Membre actif

    Homme Profil pro
    Retraité
    Inscrit en
    mars 2015
    Messages
    61
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 69
    Localisation : France, Loiret (Centre)

    Informations professionnelles :
    Activité : Retraité

    Informations forums :
    Inscription : mars 2015
    Messages : 61
    Points : 229
    Points
    229

    Par défaut

    Ton choix me paraît logique. Je pense que “ma” méthode est plus appropriée à un cas général de mélange de bits (shuffling) au moyen d’une table paramétrable. En tout cas, elle est certainement plus lente.
    Dans la situation que tu envisages, il faudrait que tu démontes complètement le mécanisme de l’algorithme que tu as utilisé. Une fois ce point bien assimilé, la solution te paraîtra évidente

  7. #7
    Nouveau membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2017
    Messages
    29
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 20
    Localisation : Belgique

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2017
    Messages : 29
    Points : 32
    Points
    32

    Par défaut

    Merci de nouveau pour votre réponse,

    Pouvez-vous me donner quelques indications sur le ''comment'' démonter l'algorithme? Pouvez-vous par exemple m'aiguiller sur le création du masque que j'ai énoncé ci-dessus?

    Merci à vous pour le suivi.

  8. #8
    Modérateur
    Avatar de Obsidian
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    septembre 2007
    Messages
    7 163
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2007
    Messages : 7 163
    Points : 22 758
    Points
    22 758

    Par défaut

    Hello,

    Citation Envoyé par Speakers Voir le message
    Merci pour vos explications, j'en suis arrivé à ce code (Assembleur 80186) qui réalise correctement ce que j'ai demandé ci-dessus:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    MOV EAX,36          ;entrée 36 (00 10 01 00)
    MOV EBX,36
    AND EAX,0xAA
    AND EBX,0x55
    Bravo, c'est ce qu'il fallait faire. Deux remarques cependant :

    — 0x55 et 0xAA sont (notoirement) les équivalents hexadécimaux des mots binaires 01010101 et 10101010, soit les masques des bits de rangs pairs et impairs, respectivement. Mais EAX et EBX sont larges de 32 bits (et même 64 pour RAX et RBX, en architecture x86_64). Par conséquent, tu peux faire une permutation de bits sur toute la largeur du registre en utilisant 0x55555555 et 0xAAAAAAAA, ou alors te restreindre explicitement à huit bit en utilisant AL et BL (sinon l'assembleur étendra automatiquement ton opérande à 32 bits) ;
    — Tu peux copier directement le contenu de EAX dans EBX (et réciproquement) à la première ligne si jamais ton paramètre vient de « l'extérieur ». Tu peux aussi de passer du XOR final puisque ton résultat n'a pas besoin d'être retourné sur 64 bits. Si c'est pour faire le ménage après avoir utilisé un registre, une bonne pratique consiste à empiler leur valeur en début de routine et à les restaurer en sortant.

    Honnêtement, si j'ai réussi à réalisé le code Assembleur, c'est seulement grâce à l'algorithme de Kannagi, sans algorithme tout fait je n'aurai jamais pu y arriver et c'est ça qui me frustre.
    Ça vient avec un peu de pratique. Une bonne chose pour se faire la main consiste également à essayer plusieurs micro-processeurs différents, dont des huit bits. C'est d'ailleurs un débat récurrent sur ce forum et je pense que Kannagi sera d'accord avec moi.


    Je voudrais me donner un exercice plus complexe, je ne veux plus échanger les bits pairs/impairs mais je veux changer le bit d'indice 0 avec le bit d'indice 5.
    Comment réaliser la création du masque pour échanger le bit d'indice 0 avec le bit d'indice 4? Est-ce:

    - 00 01 00 01
    - 11 10 11 10 ?
    Alors, sur le plan formel oui, mais en réalité, utiliser des masques + rotations n'est pas ce qu'il y a de plus efficace ici. Il y a plusieurs approches possibles, dont la fameuse astuce « while (n) n &= (n-1) » qui avait déjà été proposée comme quiz à l'embauche dans une compagnie (j'ai oublié laquelle) et qui demandait à ses candidats quels services elle était censée rendre.

    Si tu veux permuter le bit0 et le bit4, par exemple, tu peux exploiter le fait qu'ils divisent le champ en deux parties d'égale longueur et tu peux exploiter directement la rotation pour les positionner au bon endroit :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
            MOV     AL,<ta valeur initiale>
            MOV     AH,AL
            AND     AH,11h  ; 11h = 00010001
            ROR     AH,4
            AND     AL,eeh  ; eeh = 11101110
            OR      AL,AH
    L'avantage, c'est que tu peux utiliser cette approche pour permuter les demi-champs de n'importe quel registre, de longueur arbitraire pourvu qu'elle soit paire (ce qui est toujours le cas). C'est utile pour le big/little endian (même s'il existe pratiquement toujours des instructions pour travailler directement au niveau de l'octet, ce qui est plus efficace qu'une rotation) mais également pour traiter des nibbles, c'est-à-dire des demi-octets, pour travailler au niveau du chiffre hexadécimal (par exemple, pour traiter du BCD).

    Si tu veux permuter d'autres bits, il y a plein d'approches possibles. Dans un premier temps, tu peux toujours adopter une technique « naïve » et te débrouiller avec des sauts, en testant individuellement chaque bit et en décidant ou non de positionner l'état du bit de destination en fonction de sa valeur, mais si tu veux faire quelque chose de plus élégant, tu peux jouer avec les bits d'état C (Carry) et Z (Zero) et avec la congruence des incrémentations ou décrémentations.

    Par exemple, pour permuter les bits 0 et 5 comme demandé plus haut :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
            MOV     AL,<ta valeur initiale>
            MOV     BL,AL
            MOV     BH,BL
            AND     BX,0120h
            DEC     BL
            DEC     BH
            AND     BX,2001h
            XOR     BX,2001h
            AND     AL,0deh
            OR     AL,BL
            OR     AL,BH
    L'avantage des routines comme celles-ci est que d'une part, elles sont constituées d'expressions courtes et simples. Toute la routine entre dans le pipeline avec la garantie que leur déroulement ne dépendra pas des résultats intermédiaires (pas de sauts conditionnels), ce qui lui confère un temps d'exécution très rapide. En outre, la moité de ces instructions sont « inhérentes » et ne nécessitent donc aucun accès bus. Le micro-processeur peut donc les honorer sans interagir avec l'extérieur et l'efficacité est donc maximale.

    Un autre avantage est que les instructions utilisées font partie du « tronc commun », s'il on peut dire, de la grande famille des langages assembleurs et ont donc une grande chance de pouvoir être facilement portées vers des micro-contrôleurs ou des micro-processeurs plus modestes (environnements où le bit twiddling est généralement utile).

    Et le dernier et non des moindres : cette routine s'exécute en un temps fixe, indépendant de la donnée elle-même. Et ça, c'est extrêmement utile en environnement temps réel ou sur les machines trop lentes et/ou trop peu parallélisées. Par exemple, les disques durs depuis IDE ont tous leur propre contrôleur mais sur 8 bits comme sur PC, les disquettes, par exemple, ont été historiquement traitées directement par le CPU même (si le lecteur lui-même avait quand même un contrôleur). C'était donc notamment dans ses routines que l'on trouvait fréquemment ce genre de conception. Les autres cas étant les démos et les animations graphiques à l'écran qui se synchronisaient sur le raster (sur Thomson, par exemple, on simulait un effet copper, comme sur Amiga, en faisant une boucle dans laquelle on contrôlait précisément le nombre de cycles occupés par chacune de ses itérations).

Discussions similaires

  1. Variante des tours de Hanoï (disques pairs, impairs)
    Par loader dans le forum Débuter
    Réponses: 0
    Dernier message: 23/09/2008, 10h29
  2. Réponses: 3
    Dernier message: 10/04/2007, 19h09
  3. Réponses: 8
    Dernier message: 28/07/2006, 15h32
  4. [PL/SQL - PAIR/IMPAIR] Recherche fonction
    Par shaun_the_sheep dans le forum Oracle
    Réponses: 3
    Dernier message: 06/02/2006, 15h47
  5. [CR8.5] Détail Paires/Impaires
    Par PAC76 dans le forum Formules
    Réponses: 6
    Dernier message: 28/05/2004, 12h08

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo