jeudi 10 avril

Accueil :: Dépêches :: Archives :: Proposer une dépêche :: Journaux :: Forums :: Astuces :: Suivi :: RDF

Articles précédents : Code

[43] Le développement d'ext4 a commencé
[6] Smalltalk: ESUG organise le Summertalk 2006
[2] Retour des KDE Commit Digest
[29] Sortie de Ogre3d 1.2
[69] Une pile Wi-Fi améliorée pour le noyau Linux ?
[238] 23 mars: Conférence au LORIA sur Lisaac, un nouveau langage
[70] Microsoft "vend" son code source
[52] Le noyau Linux 2.6.15 est arrivé
[56] Apple ouvre le CVS de WebCore
[54] Nouvelle avancée du port du Hurd sur L4

Liens connexes

Bit Twiddling Hacks (2086 hits)

Dépêche modérée par

Floxy

Dépêche éditée par

Code : La quintessence des algorithmes bit à bit

Posté par Ontologia (page perso, ). Modéré le 07 septembre 2006.

Jouer avec les bits lorsqu'on code est souvent un bonheur intense tant les possibilités sont larges malgré les axiomes 8/16/32/64 bits dont on dispose sur les processeurs (et donc) dans les langages.

De nombreux "grands maîtres", dont Brian Kernighan lui-même ont écrit de nombreux algorithmes utilitaires effectuant des travaux sur les champs de bits que sont nos mots mémoires.

On trouvera donc dans l'article cité, qui des comptage de bit (à 1 ou 0), des tests de parités parallélisables, des rotations de bits, des modulos, des log base 2 (et donc des log base n). L'article prévient en introduction que les problèmes de cache, bande passante mémoire doivent être pris en compte dans l'utilisation de l'algorithme sur l'architecture libre.

Un bien beau texte.

NdM : les extraits de code sont du domaine public d'après l'introduction du document.

Bit Twiddling Hacks (2086 hits)

> Lire la dépêche (45 commentaires, moyenne: 3,3).

Cette discussion est archivée, il n'est plus possible de laisser des commentaires.

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.

bonheur

Posté par Troy McClure (page perso, ) le 07/09/2006 à 14:41. (lien). Évalué à 10.

> Jouer avec les bits est souvent un bonheur intense tant les possibilités sont larges

Les big-endian procurent encore plus de plaisir !

[^]Re: bonheur

Posté par Ramón Perez (page perso, ) le 07/09/2006 à 14:47. (lien). Évalué à 7.
Enlarge your possibility.

Attendez, je retrouve la photo.
- [^]Re: bonheur
  
  Posté par dco () le 07/09/2006 à 15:47. (lien). Évalué à 1.
  cherche plus je l'ai... http://www.tatabotata.com/images/enlarge.jpg
  
  merci google image

[^]Re: bonheur

Posté par Croconux () le 07/09/2006 à 15:24. (lien). Évalué à 1.
Ca reste à vérifier. Pour infos les sexologues distinguent 3 formes de penis :
- La batte de baseball (big endian), plus large au bout qu'à la base
- La tour Eiffel (little endian), plus étroite au bout qu'à la base
- Le champignon (bon, là il n'y a pas d'équivalent informatique)

Après pour ce qui est de savoir s'il y a une forme "optimale"...
- [^]Re: bonheur
  
  Posté par viridis (page perso, ) le 07/09/2006 à 15:30. (lien). Évalué à 10.
  J'imagine que ca dépend si le/la partenaire aime le sport, le tourisme ou Mario...
- [^]Re: bonheur
  
  Posté par Francois Revol (page perso, ) le 08/09/2006 à 11:24. (lien). Évalué à 2.
  A noter qu'il n'y a pas que 2 possibilités pour l'endianess... y a PDP aussi :)
  http://www.idiap.ch/~formaz/doc/glibdocs/glib-byte-order-mac(...)
  - [^]Re: bonheur
    
    Posté par Victor STINNER (page perso, ) le 10/09/2006 à 00:14. (lien). Évalué à 2.
    Moi ce que je préfère, c'est le terme bytesexual :-)
    http://fr.wikipedia.org/wiki/Endianess
    
    Haypo
  - [^]Re: bonheur
    
    Posté par Victor STINNER (page perso, ) le 10/09/2006 à 00:24. (lien). Évalué à 3.
    À noter aussi que la série des mini-ordinateurs PDP, avant le PDP-11, avait des mots de taille non multiple de 8. Un entier (int) n'avait pas 32 bits mais plutôt... (par exemple) 18 bits :-) C'est plus marrant hein. Surtout quand on veut écrire du texte !
    http://fr.wikipedia.org/wiki/RADIX-50
    (base 40 tant qu'à faire hein, pour utiliser du modulo & co)
    
    Tiens, au passage, un truc qui m'a bien fait marrer :
    http://fr.wikipedia.org/wiki/UTF-EBCDIC
    
    UTF-8, vous connaissez, mais EBCDIC ? « L'Extended Binary Coded Decimal Interchange Code (EBCDIC) est un mode de codage des caractères sur 8 bits créé par IBM à l'époque des cartes perforées » UTF-EBCDIC c'est donc retour vers le futur (Unicode sur carte perforée ? non mais presque).
    
    Haypo qui parle de choses qu'il n'a jamais connues

Merci

Posté par jjl (page perso, ) le 07/09/2006 à 15:31. (lien). Évalué à 9.

de m'avoir fait découvrir cette page ! Quand je vois la différence entre ces algos et ceux que j'ai pondu, je vais sans doute y retourner souvent.

Un gros problème quand on travaille dans l'industrie (au sens general) c'est qu'on a pas le temps de chercher d'aussi beaux algos. AMHA on perd du même coup un interet majeur de notre travail :(

[+] la quintessence ca n'a pas de sense

Posté par micka75014 () le 07/09/2006 à 20:43. (lien). Évalué à -10.

Alors, voila j'ai voulu tester du code bit à bit sur le link

Ouhaa, le typade est plus rapide ici que sous wordpress.

Je me marre, le gars de lafraise fait du zele sur ces 2 millions euros
Il aurait pas du vendre non il aurait gagner plus sur 10 ans non ?
il aurait du ce faire acheter chez google LOL

pff la vie tranquille, une maison n'importe na oke tous çà.
des enfants en plus

moi si ma mashup grimpe en bourse je vais direct vivre a moutain view
ou à SF ou a NY.

pour dire y a des paysans parmit les geek mais qui sait il rebondira
peut être

a oui j'aime pas trop les t-shirt c'est moche
le lapin de la ratp qui ce coince les doigts dans la porte ...

revenons a mes moutons,
j'ai voulu essayer le code j'ai ajouter un fonction main()
est les includes

#include <stdio.h>
#include <stdlib.h>

int main()

static const char LogTable256[] =
{
0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
};

gcc algo3.c -o algo3

/usr/lib/gcc/i686-pc-linux-gnu/4.1.1/../../../crt1.o: dans la fonction « _start »:
: référence indéfinie vers « main »
collect2: ld a retourné 1 code d'état d'exécution

comme je trouve pas de réponse pértinante dans google PR
si vous s'avez d'ou viens l'erreur, merci.

ps: les fautes ... j'accepte toute donnation de beschrelle, larousse,

[+] [^]Re: la quintessence ca n'a pas de sense

Posté par micka75014 () le 07/09/2006 à 20:45. (lien). Évalué à -10.
ps : pourquoi je trouve pas ou modifier mon password linuxfr
et pourquoi mon commentaire apparait fermé avec un +

[^]Re: la quintessence ca n'a pas de sense

Posté par Barnabé () le 07/09/2006 à 21:35. (lien). Évalué à 4.
En plus du Bescherelle, je te conseille un bon livre d'initiation au C....

Essaie avec des accolades....

int main(int argc, char **argv)
{
static const char LogTable256[] =
{
0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
};
/* .... */
return 0;
}

[^]Re: la quintessence ca n'a pas de sense

Posté par ColonelMoutarde () le 07/09/2006 à 21:39. (lien). Évalué à 5.
Va falloir apprendre le C je pense, parcequ'il manque visiblement des trucs après int main()

Pour les fautes, je crois que t'es irrécupérable. Quand au fait que ton commentaire apparaisse fermé avec un [+], c'est qu'il a été modéré négativement par les autres personnes, qui l'ont trouvé "inintéressant". Et franchement, je crois qu'ils n'ont pas vraiment tort.

--
Bow before me, for I am root

[^]Re: la quintessence ca n'a pas de sense

Posté par fork_bomb () le 08/09/2006 à 20:20. (lien). Évalué à 10.
Uhm, tu es C Lead Architect ?

Encore un coup des brevets

Posté par Bench () le 07/09/2006 à 23:07. (lien). Évalué à 10.

au sujet de la technique pour obtenir la valeur absolue :

int v; // we want to find the absolute value of v
int r; // the result goes here

r = (v ^ (v >> (sizeof(int) * CHAR_BIT - 1))) - (v >> (sizeof(int) * CHAR_BIT - 1));

Il est dit que :
Unfortunately, this method has been patented in the USA on June 6, 2000 by Vladimir Yu Volkonsky and assigned to Sun Microsystems

Heureusement peu après des liens sont donnés pour prouver que le brevet est invalide!
C'est dingue de breveter des techniques pareilles... je comprendrais jamais... heureusement que D.Knuth a ecrit ses bouquins sur l'art de la programmation, sinon on pourrai jamais utiliser de maths en informatique!

Bravo mais..

Posté par dbaelde (page perso, ) le 07/09/2006 à 23:42. (lien). Évalué à 3.

Je suis agréablement surpris par ce post, c'est rare que les amoureux de la programmation soient visés -- mais peut-être que je cherche pas au bon endroit pour ça.

Je me demande quand même combien de gens ont besoin d'écrire des algos bit à bit en C.. j'ai passé un certain nombre d'années à coder en C, ça m'est arrivé très rarement. Il y a des gens qui ne peuvent pas utiliser la libm pour le log ou la valeur absolue ?

[^]Re: Bravo mais..

Posté par lasher () le 08/09/2006 à 00:12. (lien). Évalué à 4.
En fait, dès que tu as des ressources matérielles très limitées, ce genre d'algorithmes peut faire gagner beaucoup de temps - ou bien de place, quand le problème tient plus au nombre de registres disponibles, par exemple (exemple tout bête : l'échange du contenu de deux variables à base de XOR).

Sinon, lorsqu'on entre en phase d'optimisation (et donc que le logiciel tourne déjà bien), et qu'une boucle doit être optimisée, parfois avoir recours à des opérations sur les bits peut accélérer les choses - mais j'ai l'impression que c'est très dépendant de l'architecture cible.
- [^]Re: Bravo mais..
  
  Posté par neologix (page perso, ) le 08/09/2006 à 14:26. (lien). Évalué à 10.
  
  exemple tout bête : l'échange du contenu de deux variables à base de XOR
  
  Je cite la faq sur le langage C:
  
  20.15c: How can I swap two values without using a temporary?
  
  A: The standard hoary old assembly language programmer's trick is:
  
  a ^= b;
  b ^= a;
  a ^= b;
  
  But this sort of code has little place in modern, HLL
  programming. Temporary variables are essentially free,
  and the idiomatic code using three assignments, namely
  
  int t = a;
  a = b;
  b = t;
  
  is not only clearer to the human reader, it is more likely to be
  recognized by the compiler and turned into the most-efficient
  code (e.g. perhaps even using an EXCH instruction). The latter
  code is obviously also amenable to use with pointers and
  floating-point values, unlike the XOR trick. See also questions
  3.3b and 10.3.
  
  De façon plus générale, je ne pense pas que ce osit une bonne idée de beaucoup bosser avec les bits:
  exemple, la divison par 2, que certains conseillent d'effectuer par un décalage.
  Le problème, c'est que si ton nombre est signé, et que tu fais un décalage à droite, bah le comportement est indéfini (décalage logique ou arithmétique?).
  C'est une grosse source de bugs.
  Tous ça, c'était surtout utile avant, quand les compilos étaient cons comme des balais. Aujourd'hui, ils optimisent tellement le code qu'il vaut mieux les laisser faire.
  
  Enfin, un argument sensé que j'ai lu je ne sais plus où:
  avec des "hacks" comme ça, tu gagnes un peu, mais ce peu va se réduire avec les années (progrès du compilo/métériel). Par contre, tu perds en lisibilité, et pour toujours...
  
  Attention, je ne dis pas que les manipulations de bits (en info :-) sont inutiles, je dis qu'il faut faire attention.
  - [^]Re: Bravo mais..
    
    Posté par lasher () le 08/09/2006 à 15:57. (lien). Évalué à 3.
    « Tous ça, c'était surtout utile avant, quand les compilos étaient cons comme des balais. Aujourd'hui, ils optimisent tellement le code qu'il vaut mieux les laisser faire. »
    
    Ben tout dépend de quel compilateur on parle. :-)
    Au risque de me répéter vis à vis de ce que j'ai pu dire dans d'autres réactions, gcc n'est pas (encore) le plus optimisant des compilos, et on peut clairement faire mieux à la main, si on a le temps et la volonté d'apprendre l'assembleur de la machine cible. Alors que pour faire mieux à la main que certains autres compilateurs, il faut se lever très tôt.
    
    « Enfin, un argument sensé que j'ai lu je ne sais plus où:
    avec des "hacks" comme ça, tu gagnes un peu, mais ce peu va se réduire avec les années (progrès du compilo/métériel). Par contre, tu perds en lisibilité, et pour toujours... »
    
    C'est vrai. C'est pour ça que les deux grandes règles de l'optimisation sont :
    1°) N'optimise pas.
    2°) (pour experts seulement) N'optimise pas encore.
    
    L'optimisation vient en toute fin de développement, lorsque ton code fonctionne déjà bien, sans bug, etc.
    
    Les manipulations de bits, en règle générale, sont tellement dépendants de la machine qu'il est sans doute plus « simple » si on connaît l'architecture cible d'éditer le code assembleur et de les faire soit-même (ou bien d'insérer le code ASM dans le source C, mais non seulement c'est crade, mais en plus les options d'optimisation sont désactivées automatiquement dans certains compilateurs quand ils détectent ce genre de magouille) :-)
    - [^]Re: Bravo mais..
      
      Posté par fmaz fmaz () le 08/09/2006 à 16:30. (lien). Évalué à 3.
      Ne pas optimiser, je veux bien mais il faut préciser ce qu'« optimiser » veut dire.
      
      Faire un tri à bulles parce que c'est lisible et qu'il ne faut pas optimiser et que le compilo fera le boulot, ce n'est pas demain que ça fonctionnera.
      
      Un certain nombre de personnes passent leur temps à ce genre d'optimisation pour que kde ou gnome fonctionnent plus vite.
      
      Maintenant, réécrire un code C en assembleur pour utiliser des trucs, je suis d'accord qu'il faut éviter et repousser ça à la fin.
      
      Frédéric
      - [^]Re: Bravo mais..
        
        Posté par lasher () le 08/09/2006 à 22:58. (lien). Évalué à 3.
        Par définition, lorsque tu optimises, tu risques de perdre en lisibilité.
        
        L'optimisation intervient tout à la fin, quand tu as déjà fait les bons choix pour ton logiciel (par exemple en utilisant un tri rapide ou un tri fusion pour trier tes éléments). Choisir un bon tri n'est pas faire de l'optimisation, c'est faire de bons choix de conception.
        
        Ce que j'appelle « optimisation » pourrait sans doute plutôt être appelée « micro-optimisation » : on se rend compte qu'on passe 90% du temps dans une boucle, alors on essaie de voir si on ne pourrait pas améliorer la façon dont elle s'exécute. Maintenant, si ta boucle est en réalité un tri à bulle, tu auras beau optimiser et gagner 10 ou 20 % en perfs, tu seras toujours plusieurs ordres de grandeur derrière un tri rapide ou fusion.
        
        C'est pour ça que les (micro-)optimisations viennent en fin de développement : on a déjà réglé le plus gros des détails, et on a déjà une application raisonnablement rapide.
        
        Donc, de mon point de vue, optimiser un tri à bulles ou un tri rapide, c'est *toujours* de l'optimisation. C'est juste que dans un cas, tu optimises un truc pas très efficace.
        
        [^]Re: Bravo mais..
        
        Posté par Thomas Douillard () le 09/09/2006 à 17:04. (lien). Évalué à 4.
        Optimisation locale vs optimisation globale.
        
        Pour généraliser un peu :
        
        Ingrédients : -> un problème à résoudre
        -> des solutions
        -> un (éventuellement des, mais c'est tout de suite plus compliqué) critères pour juger une solution
        
        Notre problème : Avoir un programme qui fait ce qu'on veut (autrement dit correct)
        
        Nos solutions : tous les programmes corrects possibles.
        
        Notre critère : la minimisation du temps de calcul.
        
        "l'optimisation" telle que tu l'entends peut se voir dans ce cadre comme de la "recherche locale" : on part d'une solution existante et on itère de petits changements sur cette solutions pour minimiser le temps de calcul. Le risque de ce genre d'optimisation est de tomber sur un "optimum local" qui ne soit bien moins bien que l'optimum global (globalement on changera pas grand chose à l'algo en optimisant au niveau assembleur).
        
        Une optimisation à un niveau plus global, tu vas considérer de plus gros changements dans le code (considérer le problème de manière plus abstraite, découper en des tâches, choisir l'algorithme connu le plus efficace pour résoudre les différentes tâches, etc.). C'est plus difficile de faire de l'optim globale automatiquement que de l'optim locale.
        
        Et ce cadre s'applique aussi bien à l'optimisation du code qu'a l'optimisation de pleins d'autres objets, c'est beau non ?
  - [^]Re: Bravo mais..
    
    Posté par neologix (page perso, ) le 08/09/2006 à 20:54. (lien). Évalué à 4.
    J'en profite pour donner des liens "intéressants" sur le langage C:
    le meilleur cours en ligne que je connais (et en plus il est en français):
    http://www-clips.imag.fr/commun/bernard.cassagne/Introductio(...)
    
    la FAQ Usenet, une vraie mine d'informations:
    http://c-faq.com/
    
    guide (pas) superflu du langage C:
    http://www.laas.fr/~matthieu/cours/c-superflu/
    
    Pour des débutants (et même les autres) c'est vraiment génial.
    - [^]Re: Bravo mais..
      
      Posté par Krunch (Jabber id, page perso, ) le 09/09/2006 à 02:24. (lien). Évalué à 2.
      Concernant l'optimisation, il y a le Graphics Programming Black Book.
      http://www.byte.com/abrash/
      
      --
      Free Softwares Users Group Arlon (Sud Luxembourg, Belgique)
      pertinent, e adj. Approprié ; qui se rapporte exactement à ce dont il est question.

[^]Re: Bravo mais..

Posté par jjl (page perso, ) le 08/09/2006 à 00:31. (lien). Évalué à 10.

Je me demande quand même combien de gens ont besoin d'écrire des algos bit à bit en C.. j'ai passé un certain nombre d'années à coder en C, ça m'est arrivé très rarement. Il y a des gens qui ne peuvent pas utiliser la libm pour le log ou la valeur absolue ?

Tous les gens qui ont vraiment besoin d'optimiser les perfs et l'occupation mémoire.

Alors bien sur quand tu bosse avec un x86, plein de mémoire et un gros os, tu t'en fiche un peu. Mais si tu fait de l'embarqué tu n'a pas forcement tout cela, pas de place pour des libs, un os minimalistique et très peu de mémoire.

[my life]
Depuis peu je suis passé d'applis en C++/Python sous Solaris à du C sur DSP. Ce sont deux mondes très différents qui demandent des manières de penser et de coder qui changent du tout au tout.
Quelques chiffres pour fixer les idées :
RAM : 4Go --> 1Mo (code + données)
Vitesse : 2x2.7 GHz --> 720 MHz

Dans ces cas la, loger plusieurs valeurs par octet ou gratter quelques cycles deviens vraiment nécessaire.
- [^]Re: Bravo
  
  Posté par Jimmy (page perso, ) le 08/09/2006 à 23:25. (lien). Évalué à 5.
  Je plussoie vigoureusement !
  J'ai parfois l'impression que tout le monde ici code des bases de données relationelles en J2EE sur des serveurs virtualisés ...
  Mais l'informatique embarquée est un des domaines où notre pingouin préféré a une très forte progression, et bouscule pas mal le marché établi.
  
  Pourtant dans ce domaine, malgré la Loi de Moore, on continue à avoir des besoins de compacité, de faible consommation (donc de faible fréquence, et faible quantité de mémoire) incompatibles avec la "grosse" informatique. Mais avec des besoins de performance quand même importants ! Par exemple, tous les téléphones mobiles modernes sont des systèmes multiprocesseurs, avec 2 à 4 processeurs RISC et DSP ...
  
  On se tourne alors vers des architectures spécifques, comme les DSP, qui présentent un rapport MIPS/Watt très intéressant.
  Je rajouterais le chiffre suivant :
  RAM : 4Go --> 1Mo (code + données)
  Vitesse : 2x2.7 GHz --> 720 MHz
  Consommation : 90W --> 0.9W
  
  Mais indépendamment des questions de ressources plus spartiates en embarqué, il y a un domaine où on ne coupe pas à la gestion des bits un par un : c'est quand on est en contact direct avec le hardware. Pour écrire un bit précis dans un registre (sans faire un ràz des autres bits), et même souvent faire une opération read-test-modify-write qu'on aimerait bien non-interruptible, c'est tout simplement indispensable.
  
  Une méthode pour cela est le "champ de bits", en fait une union entre une structure et la valeur globale du registre. On peut ainsi modifier indépendamment les champs de la structure, et lire/écrire la valeur complète dans le registre. Par contre, si on veut être portable il faut le définir deux fois : une fois en big endian, une fois en little endian.
  
  Exemple approximatif en Little Endian :
  
  typedef bitfield{
  typedef union{
        unsigned int register;
        struct{
          int field1 : 1; /* bit 0, LSB */
          int field2 : 3; /* bits 1 à 3 */
          int field3 : 4; /* bits 4 à 7 */
          int nothing : 24; /* bits 8 à 31, MSB */
        }bit
  }
  }
  
  Ensuite, il y a aussi des parties particulières du code, comme les routines d'interruption ou le bootloader, pour lesquelles les contraintes sont telles qu'on échappe rarement à l'écriture de quelques instructions en assembleur.
  - [^]Re: Bravo
    
    Posté par _alex () le 09/09/2006 à 00:33. (lien). Évalué à 2.
    A ce propos, j'ai en tête le projet Rockbox (firmware open source pour lecteur MP3/Ogg/etc).
    Les fonctions les plus solicitées de mise à jour de l'écran, des codec (et autre) sont optimisées en assembleur. La version C est en générale aussi présente : vu que le projet fonctionne sur différente architecture, ca facilite le portage.
    
    Ces appareils tournent souvent avec ~8Mo de RAM, et à ~80Mhz en vitesse de pointe, moins si possible pour économiser les batteries.
    
    Et là, point de malloc ou allocation de mémoire dynamique.
  - [^]Re: Bravo
    
    Posté par gpe () le 11/09/2006 à 13:11. (lien). Évalué à 1.
    Je plussoie ton plussoiment!
    
    Par exemple on fait tourner une stack GSM/GPRS/EDGE plus pas mal de chose autour sur un proc à 26MHz + un DSP à 78MHz et 512Ko de Ram. Et je peux te dire que toutes les optims sont les bien venues, même si il faut bien avouer que les compilos ARM (ADS et RVCT) sont particulièrement efficaces. Ils utilisent énormément les manipulations de bits. On utilise aussi GCC et il faut bien avouer que sur ARM il est à la ramasse en terme d'optim. Mais ça ne fait pas tout! Il ne gère pas par exemple la mise du code et/ou données en mémoire rapide, ni l'éclatement d'une boucle pour en accélérer le déroulement, ni le retournement d'une boucle (décrémenter plutôt qu'incrémenter). Donc oui bien souvent on peut faire confiance au compilo mais il ne fait pas tout non plus!

[^]Re: Bravo mais..

Posté par Matthieu C () le 08/09/2006 à 06:06. (lien). Évalué à 6.
Si tu regardes par example dans ffmpeg, tu en trouveras pas mal.

[^]Re: Bravo mais..

Posté par Ontologia (page perso, ) le 08/09/2006 à 07:41. (lien). Évalué à 4.
mais peut-être que je cherche pas au bon endroit pour ça.
Va voir chez Gcu...
http://gcu.info

D'aileurs en passant, merci à Klyr à qui j'ai honteusement piqué l'info...

[^]Re: Bravo mais..

Posté par reno () le 08/09/2006 à 09:30. (lien). Évalué à 2.
>Je me demande quand même combien de gens ont besoin d'écrire des algos bit à bit en C..

Ce n'est pas si fréquent mais ça arrive: un example ou ce serait utile:
http://primates.ximian.com/~federico/news-2005-10.html#31

J'ai essayé de le faire en faisant des manipulations de bit, mais je n'ai réussi a optimiser qu'en utilisant une instruction assembleur qui compte le nombre de bit mis a 1 dans un mot, ce qui n'existe pas sur x86, forcément ça limite beaucoup l'interet de "l'optimisation"..
- [^]Re: Bravo mais..
  
  Posté par thedidouille () le 09/09/2006 à 10:14. (lien). Évalué à 1.
  tu peux montrer le code que tu as (et l'algo) ?
  
  quelle archi dispose d'une instruction permettant de compter les bits ?
  
  Merci!
  - [^]Re: Bravo mais..
    
    Posté par reno () le 09/09/2006 à 19:20. (lien). Évalué à 3.
    En fait, l'instruction qui approxime la table n'est pas le compte du nombre de bit mais le compte du nombre de 1 au début de l'octet:
    
    si x est un octet pour 0<= x < 0xfe
    on peut calculer les valeurs de la table tres rapidement par count_leading_1(0x80 | x), ce qui doit se traduire sur les archis ayant count_leading_1 par deux/trois instructions assembleurs s'exécutant chacune en un cycle (difficile de faire mieux!).
    
    Le probleme c'est pour associer 1 a 0xfe et 0xff.
    
    En théorie c'est simple:
    (x >= 0xfe) || count_leading_1(0x80 | x)
    
    Mais le || par court-circuit n'est pas forcément efficace, c'est la ou je sèche pour trouver une formule efficace de manière "portable" (enfin efficace pour les archi qui ont count_leading_1, je ne sais pas si elles ont toutes CMOV)..
    
    J'avais envisagé aussi count_leading_1(0x81 | x) %7 mais le modulo ce n'est pas efficace non plus.
    
    count-leading-1 (ou count-leading-0, c'est la même chose a un non-binaire pres) existe sur PPC, ARMv5+, MIPS32, Alpha avec CIX, mais pas les x86 mais bon "x86 sucks" comme d'habitude :-(
    
    Voila, c'est de mémoire, je ne garanti pas qu'il n'y ait pas d'erreur..
    
    Tu peux m'envoyer un mail si tu veux discuter du sujet.
    - [^]Re: Bravo mais..
      
      Posté par ribwund () le 09/09/2006 à 19:48. (lien). Évalué à 2.
      
      man ffs
      
      C'est posix et ca donne le premier bit a 1.
      - [^]Re: Bravo mais..
        
        Posté par reno () le 10/09/2006 à 10:33. (lien). Évalué à 2.
        Euh le code C est trivial, le probleme c'est l'efficacité..
        J'ai fait un google sur ffs.c et je suis tombé sur:
        >>
        int ffs(mask)
        register int mask;
        {
        register int bit;
        
        if (mask == 0)
        return(0);
        for (bit = 1; !(mask & 1); bit++)
        mask >>= 1;
        return(bit);
        }
        <<
        Et je ne pense pas qu'un compilateur soit capable de remplacer ce code la, par l'instruction assembleur correspondante, pourtant la il s'agit de darwin qui tournait a l'origine sur PPC qui possède cette instruction (enfin l'équivalent qui compte le nombre de 0)..
        
        Quelqu'un a un PPC pour vérifier si ce code est bien compilé en assembleur par un not suivi de cntlzw?
        Si oui alors les compilateurs sont vraiment plus fort que je ne le pensais..
      - [^]Re: Bravo mais..
        
        Posté par reno () le 10/09/2006 à 10:58. (lien). Évalué à 2.
        J'ai répondu a coté: count_leading_1 est très différent de ffs:
        count_leading_1 te donne le nombre de 1 consécutif du coté poids fort, pas l'index du premier bit a 1 en partant du coté poids faible comme ffs..
        
        [^]Re: Bravo mais..
        
        Posté par ribwund () le 10/09/2006 à 12:24. (lien). Évalué à 3.
        alors dans ce cas il y'a a dans les builtins gcc [1]:
        
        — Built-in Function: int __builtin_ctz (unsigned int x)
        
        Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.
        
        et sinon dans /usr/src/linux/include/asm-i386/bitops.h, en 3 instructions assembleur:
        
        /**
        * fls - find last bit set
        * @x: the word to search
        *
        * This is defined the same way as ffs.
        */
        
        [1] http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#Other-(...)
        
        [^]Re: Bravo mais..
        
        Posté par thedidouille () le 10/09/2006 à 17:09. (lien). Évalué à 1.
        il y a du jnz dans ce truc là, c'est plus pire que du modulo non ?
        
        [^]Re: Bravo mais..
        
        Posté par reno () le 10/09/2006 à 18:20. (lien). Évalué à 2.
        Oui, je connaissais, mais j'ignorais qu'il y avait une implementation "efficace" possible sur x86 en utilisant bsr, enfin j'espere que bsr est efficace.
        
        Je vais tester ça.
        
        [^]Re: Bravo mais..
        
        Posté par thedidouille () le 10/09/2006 à 15:25. (lien). Évalué à 1.
        merci pour ta réponse, le coup du "modulo 7 pas efficace" m'a calmé :)
        
        c'est vrai que "count_leading_1" est une instruction vraiment utile (plus qu'un compteur de bits). je pensais que pour tout ce qui était manipulations de bits, l'architecture x86 était la plus aboutie.
        
        Si j'ai un jour une question de ce genre, je sais a qui la posée.
        
        [^]Re: Bravo mais..
        
        Posté par reno () le 10/09/2006 à 17:15. (lien). Évalué à 2.
        > merci pour ta réponse, le coup du "modulo 7 pas efficace" m'a calmé :)
        
        Euh, il ne faudrait pas me prendre pour un gourou, hein!
        Il me *semble* que le modulo ce n'est pas efficace (pas d'instruction pour ça directement) et faire mieux que la fonction de gtk n'est pas si facile, c'est quand même juste un load, la mémoire est lente certes, mais ça ne fait quand même pas beaucoup de cycle..
        
        > je pensais que pour tout ce qui était manipulations de bits, l'architecture x86 était la plus aboutie.
        
        Ah? Ca n'est pas ma perception..
        En tout cas, je ne l'ai pas trouvé 'count-leading-1' (ou 0) sur x86, ni sur SPARC d'ailleurs (pour ne pas taper que sur x86) et ni sur IA64 (Intel ne m'aide décidement pas).
        
        [^]Re: Bravo mais..
        
        Posté par reno () le 10/09/2006 à 18:45. (lien). Évalué à 2.
        Bon bah j'avais tout faux: sur x86 BSR trouve l'index du bit (en partant des poids forts) a 1, donc en faisant un not d'abord cela revient a 'count-leading-1'.
        
        Donc la formule peut valoir le cout sur x86, chouette!
        
        Reste a trouver une maniere efficace de traiter le cas particulier de 0xfe, 0xff, quelqu'un a une idée?
        
        (x >= 0xfe) || (__builtin_clz(~(0xffffff80 | x)) - 24)
        ou
        (__builtin_clz(~(0xffffff81 | x)) - 24) % 7
        ou ...
        
        [^]Re: Bravo mais..
        
        Posté par reno () le 11/09/2006 à 04:59. (lien). Évalué à 2.
        Bon le 0x80 | ne marche pas (j'avais déja fait l'erreur) ce qui fait en final:
        
        (x < 128) || (x >= 0xfe) || (__builtin_clz(~x) - 24)
        ou
        (((x+2)&0xff) < 130) + (__builtin_clz(0xfe & ~x) & 7)
        
        Et pas mal de variantes possibles..
        
        [^]Re: Bravo mais..
        
        Posté par benoar (Jabber id, ) le 13/09/2006 à 13:29. (lien). Évalué à 2.
        Pour le cas spécial, peut-être :
        !(x ^ 0xff) || !((x ^ 0xff) - 1)
        non ?
        Sinon, pourquoi est-ce que la comparaison ne serait "pas efficace" ?
- [^]Re: Bravo mais..
  
  Posté par ribwund () le 09/09/2006 à 14:02. (lien). Évalué à 3.
  Pourquoi ne pas utiliser le code existant du kernel ?
  
  (dans lib/hweight.c)

Revenir en haut de page

Articles précédents : Code

Liens connexes

Dépêche modérée par

Dépêche éditée par

Code : La quintessence des algorithmes bit à bit

bonheur

[^]Re: bonheur

[^]Re: bonheur

[^]Re: bonheur

[^]Re: bonheur

[^]Re: bonheur

[^]Re: bonheur

[^]Re: bonheur

Merci

[+] la quintessence ca n'a pas de sense

[+] [^]Re: la quintessence ca n'a pas de sense

[^]Re: la quintessence ca n'a pas de sense

[^]Re: la quintessence ca n'a pas de sense

[^]Re: la quintessence ca n'a pas de sense

Encore un coup des brevets

Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo

[^]Re: Bravo

[^]Re: Bravo

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..

[^]Re: Bravo mais..