Technique de masque binaire

09/08/2013

Une fois n’est pas coutume, j’ai décidé d’expliquer une technique courante mais souvent oubliée par les développeurs, cela sans aucune forme de critique. C’est le sytème de masque binaire pour créer des drapeaux (ou flag) d’option.

Ce post s’adresse surtout au développeurs qui débutent ou encore ceux qui ont perdu l’habitude de travailler avec des types primitifs. Si vous connaissez cette méthode je ne vous apprendrai rien.

L’idée d’écrire un post de blog sur le sujet me vient du fait que moi même j’ai commis l’erreur d’oublier d’utiliser cette méthode très propre lors de mon écriture d’implémentation de “VerbalExpression” en Go. C’est un certain surnommé “maurodec” qui m’a mis sur la voie avec son implémentation que je tente de fusionner à la mienne.

Le principe est connu, assez simple mais rarement utilisé si comme moi vous travaillez “trop vite” pour implémenter une librairie…

Je vais partir de mon implémentation de VerbalExpressions pour vous expliquer le principe.

VerbalExpression permet de construire des expressions régulières simplement. Elle permet d’utiliser des méthodes qui active ou non des options telles que:

  • ignorer la casse
  • capturer en multiligne
  • le caractère “.” prend aussi les n…

On ne va prendre que ces cas pour le moment.

Si on utilise la méthode ‘SearchOneLine(true)’ il faut ajouter “m” au modificateur d’expression régulière, si “WithCaseSensitive(true)’ on ajoute “i” au modificateur. Si on passe “false” à ces méthodes, on doit supprimer le modificateur associé. Pas d’inquiétude, je vais éclaircir tout ça.

Ma première idée était simple, avoir une “chaine” qui se concaténait avec les modificateurs… et supprimer la lettre correspondante via strings.Replace si on demandait la suppressions. C’est tout simplement pas du tout efficace.

Seconde idée, avoir un “slice” (genre de hash) qui avec pour chaque lettre “m” et “i” un booléen associé, puis concaténer selon le cas… encore une fois mauvais idée.

La troisième fut la bonne (merci à maurodec): utiliser les masques !

L’idée est simple: on crée des constante qui ont une valeur particulière. Ensuite je garde une variable qui opère de manière binaire, et enfin quand je veux vérifier les flags, je fais des masques.

Houlla je vous perds… on va y aller doucement.

D’abord, revenons à la base de nos vieux cours d’info.

Une variables est une valeur binaire, une représentation de 0 et de 1. Selon le type, le langage interprétera cette série pour l’utiliser de différente manière.

On lit de droite à gauche !

  • Prenons le nombre entier “1”, en binaire 4 bits c’est “0001”. Ok…
  • Le nombre entier 2 est “0010”
  • Pour le “3” : “0011”
  • etc…

Si l’on regarde ces nombres, plus on avance dans les nombres entiers, plus on assigne des “1” vers la gauche. Ainsi “8” est “1000”.

Bon, maintenant, regadons ces 4 représentations binaires:

  • 0001 = 1
  • 0010 = 2
  • 0100 = 4
  • 1000 = 8

Que des “0” + un “1” qui se décalle à gauche.

Le principe va être très simple, on regarde chaque bit du mot binaire, on imagine simplement que chaque bit est une colonne, ou une option, qui a une valeur 1 pour active, 0 pour inactive.

Les nombres 1, 2, 4, 8, 16… sont interssants car ils n’ont qu’un seul “1” dans leur représentation binaire. Du coup en les additionnant on a juste un “ou” binaire… et oui ! regardez 2+4 = 6

0 1 0 0 =4
0 0 1 0 =2
OR 0 1 1 0 =6

Bien… on continue.

Prenons ce fameux nombre “6” issue de notre opération. Il a deux “1”… un sur la colonne 2 (en partant de la droite) et un à la troisième…

Si on prend un à un ces nombres “1”, et qu’on élimine les autres, on trouve:

  • 0010
  • 0100

Tien donc ! c’est bien 2 et 4…

Et oui, on sait donc à partir d’un résultat retrouver les nombres qui ont servis.

Et bien maintenant, tout le problème est de savoir décomposer les nombres qui ont composé le résultat. Et pour cela, on va faire un masque. on y arrive.

L’idée est de voir si on arrive à retrouver la composition binaire.

On a une première méthode, faire un “&” (“et binaire”) avec 1, 2, 4, 8…

Avec 1

0 1 1 0 =6
0 0 0 1 =1
AND 0 0 0 0 =0

Avec 2

0 1 1 0 =6
0 0 1 0 =2
AND 0 0 1 0 =2

Avec 4

0 1 1 0 =6
0 1 0 0 =4
AND 0 1 0 0 =4

Et avec 8

0 1 1 0 =6
1 0 0 0 =8
AND 0 0 0 0 =0

Donc, ça fonctionne: l’opération binaire a retourné une valeur supérieure à 0 seulement pour les nombres binaires composés d’un seul “1” qui partagent un bit en commun. C’est à dire 4 et 2.

Donc, voilà une première idée, on teste avec “&” chaque valeur:

const (
    MULTILINE  = 1
    IGNORECASE = 2
    DOTALL     = 4
)

// ... plus loin

flags := MULTILINE | DOTALL // ça donne un 5
if ( flags & MULTILINE != 0 ){
    // oui, on a MULTILINE
}
if ( flags & IGNORECASE != 0 ){
    // oui, on a IGNORECASE
}
if ( flags & DOTALL != 0 ){
    // oui, on a DOTALL
}

Bon ça marche, mais on peut aller encore plus loin.

On reviens à VerbalExpression et le fameux “modificateur” à créer. Chaque option correspond à une lettre:

  • MULTILINE : m
  • DOTALL : s
  • IGNORECASE : i

Donc:

  • Si je fais “MULTILINE | DOTALL” je dois générer “ms”
  • Si je fais “IGNORECASE | DOTALL” je dois générer “is”

Ok, maintenant j’ai besoin de regarder les options enregistrées tour à tour… mais je dois compter non pas de 0 à 2 en décimale, mais de 1 à 4 de manière binaire (1,2,4,8…)

Pour compter de cette manière on va utiliser le décallage de bit.

Comme vous l’avez vu, les nombres 1,2,4,8,16… sont des représentation d’un seul 1 binaire qui se décalle à gauche. L’opérateur “<<” décale les bits vers la gauche (en assignant des 0 à droite)

Ainsi:

  • 0001 = 1<<0 (1 décallé de 0 bit vers la gauche)
  • 0010 = 1<<1 (1 décallé de 1 bit vers la gauche)
  • 0100 = 1<<2 (1 décallé de 2 bits vers la gauche)
  • 1000 = 1<<3 (1 décallé de 3 bits vers la gauche)

0, 1, 2, 3… donne 0, 1, 2, 4… c’est pas génial ça ?

Donc l’idée c’est que chaque itération, je décalle “1” de “i” vers la gauche, et j’ai bien 1 puis 2 puis 4…:

flags := MULTILINE | DOTALL
for i:=0; i<4; i++ {
    if flags & (1<< uint(i) ) != 0 {
        // tour à tour je teste MULTILINE 
        // (quand i=1 => 1<<1 = 0001 = 1)
        // puis IGNORECASE 
        // (quand i=2 => 1<<2 = 0010 = 2)
        // puis DOTALL 
        // (quand i=3 => 1<<3 = 0100 = 4)
    }
}

Alors voilà comment on peut procéder:

const (
    MULTILINE  = 1
    IGNORECASE = 2
    DOTALL     = 4
)

// ... plus loin

flags := MULTILINE | DOTALL //on demande à avoir "m" et "s"

// rune correspond à un caractère, c'est plus simple
// en Go pour indexer les lettres, on transforme en string à la fin
totests := []rune("mis") // dans l'ordre exact de mes constantes

modifiers := []rune{} // on stoquera là dedans les caractères m, i, s...
for i, flag := range totests {
    // on le fait pour chaque lettre de totests
    if flags & (1 << uint(i) ) != 0 {
        modifiers = append(modifiers, flag) // on ajoute la lettre associée            
    }
}

fmt.Println(string(modifiers)) // affiche "ms"

Vous pouvez aller voir l’exemple http://play.golang.org/p/8J_tYrhUgq et changez la valeur de “flags”

Et pour les connaisseurs de Go, on peut déclarer nos constante via “iota”, c’est moins ennuyeux que de compter en binaire, surtout quand on commence à avoir un paquet de constantes…:

const {
    MULTILINE  = 1<<iota
    IGNORECASE = 1<<iota
    DOTALL     = 1<<iota
}

Reste un dernier point… il faut des méthodes pour ajouter les constantes ou les retirer. Rappelez vous: ajouter = faire un “ou”, retirer c’est faire un “bitclear” (l’un et pas l’autre) soit “&\^“, cela ne perd pas les autres bits…

Exemple, j’ai DOTALL et j’ajoute IGNORECASE

  • 0100 => DOTALL, 4
  • 0010 => ajout de IGNORECASE, 2
  • 0110 => donne 6 (4+2) par opération “ou”

On retire IGNORECASE

  • 0110 => DOTALL | IGNORECASE = 4+2 = 6
  • 0010 => on retire IGNORECASE
  • 0100 => bitclear, il faut un seul 1 dans la colonne, on revient à “4” soit DOTALL

Donc voilà une méthode d’exemple :

var flags unint = 0
func IgnoreCase(stat bool) {
        if stat {
            flags = flags | MULTILINE
        } else {
            flags = flags &^ MULTILINE
        }
}

Selon si on active ou non un mode, on ajoute ou retranche la valeur… on aurait put le faire avec “+” et “-” mais bien souvent on préfère retyper les constantes… du coup prenez l’habitude de la faire de manière binaire.

Voici un exemple avec les méthodes appliquées : http://play.golang.org/p/OICDEDceWN

Voilà, j’ai peut-être pas été super clair, mais les exemples peuvent vous donner de la lumière.

En espérant que je vous ai donné des billes…

Ça peut vous intéresser aussi


Assigner une variable lors de la compilation en Go

Je viens de faire une release de mon outil idok et ...


Mise à jour du blog en Go

Si vous connaissiez mon blog, vous avez remarqué qu’à ...


Golang, résoudre le souci d'indexation de type défini

Golang permet de créer ses prores types et notamment de ...


Un exemple Golang de résolution de tâche parallèle

J’ai participé aux BlendWebMix 2015 en tant que “...

Merci de m'aider à financer mes services

Si vous avez apprécié cet article, je vous serai reconnaissant de m'aider à me payer une petite bière :)

Si vous voulez en savoir plus sur l'utilisation de flattr sur mon blog, lisez cette page: Ayez pitié de moi

Commentaires

Ajouter un commentaire

Draeli - 28/08/2013

Je crois qu’il y a une légère coquille dans le cas :

Avec 2 0 1 1 0 =6 0 0 1 0 =1

& 0 0 1 0 =2

la deuxième ligne correspond à 2 et non pas 1.

Metal3d - 29/08/2013

Merci @Draeli, j’ai corrigé et viré les commentaires en trop… y’a un drôle de bug sur mon site qui remonte des tableaux de commentaire du post précédent. J’ai encore fait des trucs trop rapidement moi hein…

Ajouter un commentaire

(*) Votre e-mail ne sera ni revendu, ni rendu public, ni utilisé pour vous proposer des mails commerciaux. Il n'est utilisé que pour vous contacter en cas de souci avec le contenu du commentaire, ou pour vous prévenir d'un nouveau commentaire si vous avez coché la case prévue à cet effet.