mercredi 28 août 2013

Question de bits et de bytes

Mis à part que les pionniers de l’informatique auraient dut se préoccuper du français quand ils ont nommée leurs unités logique voici le problème que je me posais initialement:

Un booléen est habituellement stocké dans un octet (soit un unsigned char) alors qu'il ne peut prendre que deux états. Pour un seul booléen ou des milliers des booléens ça reste un gaspillage acceptable sur les ordinateurs modernes, où la mémoire ne manque pas. Mais pour certaines applications (par exemples de larges filtres de Bloom) il est souhaitable de compacter la place occupées par les milliers de booléens que l'on veut instancier. En d'autre thermes, peut-on instancier un tableau de bits?

Réponse, pas de base, il faut quitter sa zone de confort avec les jolis opérateur qu'on nous a appris en primaire ( + - ÷ × ) et s'attaquer à ces inquiétant opérateur dit bit à bit (et il est interdit de penser à une partouze)  ( & | ^ << >> ).

Heureusement ce tutoriel est là pour vous aider, on va même réaliser ensemble un jolis objet c++ qui va gérer tout ça pour nous! Voyons d'abords ces fameux opérateurs qu'on va utiliser:

&

AND, "et" logique, renvoie un bit à 1 si et seulement si les deux bits de même poids valent 1 sur les deux paramètres passés:

unsigned int a = 4 & 7;  //a = 4
unsigned int b = 7 & 9; //b = 1
unsigned int c = 4 & 9; //c = 0

unsigned int oct = 0203 & 0205; //oct = 0201
unsigned int hex = 0x000F02 & 0x00420F; //hex = 0x000202;


Vous l'aurez remarqué la clé du problème c'est la décomposition des nombre en puissance de deux. Pour accéder au nième bit d'un entier il suffit donc de réaliser nombre & (2 à la puissance n).

|

OR, "ou" simple fonctionne de la même manière mais il lui suffit qu'il seul des deux bits de même poids soient à 1 pour renvoyer 1:

unsigned int a = 4 | 7;  //a = 7
unsigned int b = 7 | 9; //b = 15
unsigned int c = 4 | 9; //c = 13

unsigned int oct = 0203 | 0205; //oct = 0207
unsigned int hex = 0x000F02 | 0x00420F; //hex = 0x004F0F;


^

XOR, "ou" exclusif, renvoie 1 si et seulement si un seul des bits de même poids vaut 1:

unsigned int a = 4 ^ 7;  //a = 3
unsigned int b = 7 ^ 9; //b = 14
unsigned int c = 4 ^ 9; //c = 13

unsigned int oct = 0203 ^ 0205; //oct = 0006
unsigned int hex = 0x000F02 ^ 0x00420F; //hex = 0x004C0C;


<< et >> 

représentent un décalage à gauche ou à droite ce qui revient à multiplier ou diviser par deux autant de fois que spécifié ( et dans la limite de la taille du type utilisé).

unsigned int a = 2 << 2;  //a = 8
unsigned int b = 1 << 3; //b = 8
unsigned int c = 2 >> 1; //c = 1


Leur principale utilité, combinés aux opérateurs précédents, est d'accéder à un bit donné.

unsigned int a = 1 << 0;  //a permet d'inspecter le bit 0
unsigned int b = 1 << 5; //b permet d'inspecter le bit 5

Il fut un temps les processeurs ne pouvaient pas réaliser directement les opérations arithmétiques de base, il fallait les implémenter grâce à ces opérateurs bits à bits. Par exemple le bon vieil algorithme d'addition en colonne devenait (la représentation assumée est celle dite complément à deux, la charge de détecter les dépassements n'est pas assumée par la fonction):

 int additionner (int pN1, int pN2){

      int n1 = pN1;
      int n2 = pN2;

      int r1 = n1 ^ n2; //addition directe
      int r2 = (n1 & n2) << 1; //retenue

      if(!r1)
            return r2;
      else if (!r2)
            return r1;
      else
            return additionner (r1, r2);

}


Donc on peut s'offrir un tableau de booléen compressé, voici en c++:

Définition:

 class BinaryKeeper{

    public:


        /** Default constructor */
        BinaryKeeper(unsigned int pSize);
        /** Default destructor */
        virtual ~BinaryKeeper();
        /** Copy constructor
         *  \param other Object to copy from
         */

        BinaryKeeper(const BinaryKeeper& other);
        /** Access size
         * \return The current value of size
         */

        unsigned int Getsize() const{ return size; }

        bool InIndex(unsigned int index) const;
        char CharInIndex(unsigned int index) const;

        void SetIndex(unsigned int index, bool pState);


    private:


        unsigned int size; //!< Member variable "size"
        unsigned char* datas; //!< Member variable "datas"


};


Premièrement le constructeur, il va essentiellement instancier un tableau d'unsigned char et le remplir de 0. Ce type offre l'avantage d'être de taille constantes selon les systèmes:

/** Default constructor */ 
BinaryKeeper::BinaryKeeper(unsigned int pSize){

    //ctor

    size = pSize;
    unsigned int cSize = size/8 + 1;

    try{

        datas = new unsigned char [cSize];

        for(unsigned int k = 0; k <
cSize; k++){
            datas[k] = 0;
        }

    }catch ( const std::bad_alloc & ) { // erreur d'allocatation.

        delete [] datas;
        size = 0;

    }
 

}

Ce code n'est pas très compliqué. Notez bien que pour être certain d'avoir assez de place pour inscrire le nombre de bits demandé qui n'est pas forcément un multiple de 8 vous devez ajouter un octet à la taille de votre tableau. Si ce dépassement anecdotique vous ennuie vous pouvez corriger size, personnellement j'alloue quelques bit de plus mais je tiens à ce que mon objet  encapsule la taille demandée.

Le destructeur lui, va juste libérer les allocations dynamiques:

/** Default constructor */ 
BinaryKeeper::~BinaryKeeper(){

    //dtor
 

    delete [] datas;
 

}


Viennent ensuite les accesseurs,  si accéder à une char donnée se fait de manière simple (libre à vous de définir un comportement quand vous dépasser la taille du tableau, personellement dans ce cas je renvoie le plus haut indice disponible). Pour accéder à l'état (true | false) d'un bit donné ça se corse un peu.

char BinaryKeeper::CharInIndex(unsigned int index) const{

    if (index <= size/8)
        return datas[index];
    else
        return
datas[size];
}


bool
BinaryKeeper::InIndex(unsigned int index) const{

    unsigned int i = index;

    if( i >= size)
        i = size-1;

    unsigned int cIndex = i >> 3 ;
    unsigned int cInside = i & 7 ;

    unsigned char v = datas[cIndex];

    unsigned char c = 1 << cInside;

    return (bool) (v & c);

}

Les index de notre tableau de bits fonctionnent comment ceux d'un tableau classique. Le premier bit est le bit de poids 0 (2^0) du char 0. Le dernier est donc le size-1 ème bits. On corrige donc l'index s'il est trop haut (on pourrait aussi lancer une exception, renvoyer faux ou vrai par défaut ... ).

Ensuite viennent ces deux lignes assez mystérieuses (je vous aide un peu et vous donne les équivalents classiques):

    unsigned int cIndex = i >> 3 ;
    unsigned int cInside = i & 7 ;


    //équivalent:
 

    unsigned int cIndex = i / 8 ;
    unsigned int cInside = i % 8 ;

cIndex est le char que l'on va inspecter, cInside le poids du bit à inspecter à l'intérieur. On les obtient le plus logiquement du monde en divisant par 8 et en prenant le modulo par 8 de l'indice demandé. Mais comme 8 est une puissance de 2 il y a plus "simple" (du moins en temps de calcul pour l'ordinateur). Diviser par 8 revient à diviser par 2^3 soit de décaler 3 fois à droite. Prendre le modulo revient à effacer tout les bits sauf ceux de poids 0, 1 et 2 ce qui se fait grâce à l'opérateur & 7.

unsigned char c = 1 << cInside;

 c servira à accéder au bit souhaité. Ce que l'on fait à la ligne suivante grâce à &:

return (bool) (v & c);


Enfin détaillons la fonction de changement d'état d'un bit donné, j'ai choisi volontairement de créer une fonction qui change le bit vers un état spécifié mais il serait possible d'en créer une qui inverse simplement l'ancien état:

void BinaryKeeper::SetIndex(unsigned int index, bool pState) {

    unsigned int i = index;

    if( i >= size)
        i = size-1;

    unsigned int cIndex = i >> 3 ;
    unsigned int cInside = i & 7 ;

    unsigned char c = 1 << cInside;


    if (pState){ // si on veut mettre l'état à true
        datas[cIndex] |= c; //alors on le met à 1
    } else { // si on veut mettre l'état à false;
        c ^= 255; //on place un zéro sur le bit du poids qui nous intéresse.
        datas[cIndex] &= c; //on le met à 0.
    }
}


Bien sûr cet objet reste relativement simple dans sa conception, il ne gère pas d'exceptions, ne permet pas d'utiliser d'itérateurs, etc... Néanmoins il réalise son travail correctement (du moins de ce que j'ai put tester) quand il s'agit de gérer un filtre de bloom ou un très grands tableau de booléens tout en économisant la mémoire. Il sera par contre légèrement plus lent qu'un simple bool*.

Libre à vous de l'améliorer, perso je ne le ferai que si j'en ai l'utilité. Puisque pour l'instant il me convient ainsi!

Who Am I ?

Je ne suis pas un geek, pas du moins selon la définition qui a été choisie expressément par des gens malheureux de ne rien comprendre à l'informatique:

geek npejorative (socially unskilled person) familierboulet, tocard, blaireau nm

gros coincé, intello coincé nm

nul, nulle n

traduction par http://www.wordreference.com

En clair je ne suis ni un blaireau coincé, ni un intello au sens péjoratif. Par contre je fais certains trucs de geek (mais je me soigne... aussi bien que je peux):

Comment je me soigne: avec des méthodes inattendues !

Pourquoi j'en parle: ça fait une psychanalyse gratuite!


Programmer:



Personnellement mon langage fétiche est le c++ pour la programmation en ligne de commande et le Java pour les programmes graphiques. Je suis néanmoins un touche à tout puisque je maîtrise également le php (et les classiques html et cie) et le ruby.

Comment je me soigne: en programmant des choses compliquées... comme ça on arrête de vous prendre pour un geek. On vous prend pour un vrai informaticien ^^.

Pourquoi j'en parle: de nos jours on utilise de plus en plus les nouvelles technologies. Il est donc important (selon moi) de transférer le savoir sur leur fonctionnement.


Du jeu de rôle:



En fait essentiellement le jeu de rôle sur table. Je me suis aussi intéressé à ce que l'on nomme le grandeur nature, mais malheureusement je ne me suis pas encore tant impliqué.

Comment je me soigne: je marque ma préférence pour les JDR plus "narratifs"! Comme ça on vous prends non plus pour un geek mais pour un futur écrivain ^^.

Pourquoi j'en parle: simplement une activité sociale et sans compétition malsaine mérite qu'on en parle.


Mission sauvetage de la terre et ineptie politique:



En politique je suis assez clairement vert (avec néanmoins des nuances de kaki, vert clair et turquoise voir verre de terre). Pour le reste je serais socio-libéral avec des tendances natio-communo-démocrato-anarchistes. Je vous rassure, je vous emmerderai le moins possible avec mes convictions, ce que j'aime c'est présenter les choses d'une manière originale.

Comment je me soigne: au vu de ce qui est écrit au dessus on dira que je n'ai plus aucune chance ^^.

Pourquoi j'en parle: parce que les raisonnements trops simples de certains populistes de tout bords me rendent nerveux! Et quand je suis nerveux faut que je parle.