inverser des bit - Page 1

j'ai besoin d'inverser plusieurs mo de données, quelle est la methode la plus rapide ?
pour le moment j'ai ca:

for(unsigned long i=0;i<(unsigned long)size;i++)
   *(donnee2+i)=(unsigned char )(~(*(donnee2+i)));

j'ai tenté en asm mais ca marche pas

extern __inline__ void
reverse (unsigned char *donnee,unsigned long size)
{
  
  __asm__ __volatile__ ("  
mov ecx,%1
mov si,%0
bloop:
not.b [si+%1-cx]
loop bloop"
  : "0" (donee)
  : "1" (size));
}

dans tous les cas y'a pas une methode plus rapide ?

unsigned long * donnee3; // si le processeur est capable d'effectuer des ~ sur 32 bits.
...
donnee3 = donnee2;
for(unsigned long i=(unsigned long)size; i--; )
  donnee3 = ~(*(donnee3++));

Je ne sais pas s'il y a mieux (surement que oui), les dieux de l'optimisation de ce forum t'en diront plus que moi mais j'espere que ca t'aidera en attendant.

j'y ai pensé mais j'ai un probleme, mon nombre d'o est impaire et varie de 0 a 256^4-501
j'ai fait ceci :

  if(size>3)
   {
    unsigned long size1=(unsigned long)(size/4);
    unsigned char size2=(unsigned char)(size & 7);
    for(unsigned long i=0;i<size1;i++)
    *(((unsigned long*)donnee2)+i)=(unsigned long)(~(*(((unsigned long*)donnee2)+i)));
    for(unsigned char i=0;i<size2;i++)
    *(donnee2+i+size1)=(unsigned char )(~(*(donnee2+i+size1)));
   }
   else
   {
   for(unsigned char i=0;i<size;i++)
    *(donnee2+i)=(unsigned char )(~(*(donnee2+i)));
   }   

mais c'est encore vachement lent ...

on peut pas faire comme sur la ti, tous mettre dans les registres et tout inverser ?

Tu peux dérouler ta boucle aussi, si c'est toujours trop lent.

Avec les registres et instructions MMX, y'a pas moyen d'inverser par paquets de 128 bits ? il me semble
Par contre je crois qu'il y a une "activation" du mode MMX à faire, qui prend un certain temps, donc faudrait faire gaffe à ce que les données soient suffisamment longues pour que le temps gagné par le traitement 128 bits soit supérieur ou égal au temps d'activation.

sur les instructions SSE2 il n'y a pa d'activation ... ca m'étonnerait pour MMX alors

matthieu :
j'ai fait ceci :
...
mais c'est encore vachement lent ...

Est-ce que tu es sûr que "donnee2" est alignée ? (multiple de 4, quoi) Si c pas le cas, il faudrait que tu distingues encore des cas au début pour l'aligner (en faisant octet par octet, comme ce que tu fais à la fin).

Et tu n'as pas besoin de dupliquer la dernière boucle : au lieu de faire

if (size>3) {
  boucle_long(size1);
  boucle_char(size2);
} else
  boucle_char(size);

tu peux faire

if (size>3) {
  boucle_long(size1);
  size = size2;
}
boucle_char(size);

(plus tu dupliques ton code, plus ça va être chiant à maintenir -- même si ça a l'air facile à écrire avec un simple copier-coller)

matthieu :
j'ai tenté en asm mais ca marche pas

extern __inline__ void
reverse (unsigned char *donnee,unsigned long size)
{
  
  __asm__ __volatile__ ("  
mov ecx,%1
mov si,%0
bloop:
not.b [si+%1-cx]
loop bloop"
  : "0" (donee)
  : "1" (size));
}

La même chose en assembleur inline GCC x86 valide:

extern __inline__ void
reverse (unsigned char *donnee,unsigned long size)
{
  
  __asm__ __volatile__ ("  
movl %1,%%ecx
movl %0,%%esi
bloop:
notb -1(%%esi,%%ecx)
loop bloop"
 : : "r" (donee), "r" (size) : "ecx", "esi", "memory", "cc");
}

(Sache que le scale d'un registre peut être seulement 1, 2, 4 ou 8, pas -1. Tu ne peux donc pas calculer size-ecx, mais ecx-1 fera bien l'affaire.)

... je viens juste de me rendre compte que j'avais tout declarer en unsigned char alors que j'y accede en unsigned long ...
chuis un malade...
a moins que tout est fait pour avoir des adresse paire vu que j'ai pas eu de bug avec une bonne 50aine de test... ?


merci pour toutes vos reponses mais je comprendrais jamais rien a lasm inline gcc ...

pk on met "r" pour (donnee) et pas "toto" ?
%0 et %1 ca correspond a l'ordre dans lequel on donne les données ?
pk t'as utilisé memory et cc alors que tu ne les utilise pas dans ton code ? c'est pour dire que tu va chercher des trucs dans la ram?
et pk t'utilises esi et ecx et pas autre chose ?

et puis -1(%%esi,%%ecx) ca equivaut a *(donnee+size-1) ? non ? où est ce que tu decremente donnee ou size ?

et qu'est ce que ca donne en unsigned long ? ca ? (size est superieur a 3 forcemment)

extern __inline__ void 
reverse (unsigned char *donnee,unsigned long size) 
{ 
if((donnee & 1)==1){size--,*(donnee)=(unsigned char)~*(donnee++);} // si c impaire

 unsigned long size1=(unsigned long)(size/4);  // au fait qqun sait comment on fait des shifts avec dev c++ ? 
  __asm__ __volatile__ ("   
movl %1,%%ecx 
movl %0,%%esi 
 bloop: 
 notl -1(%%esi,%%ecx)  // est ce que ca decrement de 4 a chaque fois ? 
 loop bloop" 
  : : "r" (donnee), "r" (size1) : "ecx", "esi", "memory", "cc"); 
 

  donne+=size1;
  unsigned long size2=0; // je l'initialise a 0 , on sait jamais
  size2=(unsigned char)(size & 7); 
  __asm__ __volatile__ ("   
  movl %1,%%ecx  
  movl %0,%%esi 
  bloop: 
  notb -1(%%esi,%%ecx) 
  loop bloop" 
  : : "r" (donnee), "r" (size2) : "ecx", "esi", "memory", "cc"); 
 }

   

au fait, j'ai un processeur 64 bit .... ca existe un "not double long " ?

>>thibaut && neuroo ,j'ai pas trouvé grand chose sur MMX sur le net( a par une doc de intel qui fait 50 000 pages ...) comment on peut y acceder ?

ma ref sse2 http://folk.uio.no/botnen/intel/vt/reference/

long double

matthieu
: pk on met "r" pour (donnee) et pas "toto" ?

"r" = "registre quelconque" (sauf ceux marqués en "clobber")

%0 et %1 ca correspond a l'ordre dans lequel on donne les données ?

Oui.

pk t'as utilisé memory et cc alors que tu ne les utilise pas dans ton code ? c'est pour dire que tu va chercher des trucs dans la ram?

C'est pour dire que ton asm modifie la mémoire (ce qui est clairement le cas ici) et le condition code (en cas de doûte, toujours le mettre).

et pk t'utilises esi et ecx et pas autre chose ?

Parce que tu utilisais ça dans ton code.

et puis -1(%%esi,%%ecx) ca equivaut a *(donnee+size-1) ? non ?

Oui.

où est ce que tu decremente donnee ou size ?

loop décrémente le registre %ecx. Tu devrais avoir une doc d'assembleur x86 sous les yeux au lieu de copier-coller des fragments d'assembleur que tu ne comprends visiblement pas.

unsigned long size1=(unsigned long)(size/4); // au fait qqun sait comment on fait des shifts avec dev c++ ?

size>>2

notl -1(%%esi,%%ecx) // est ce que ca decrement de 4 a chaque fois ?

Non, il faut mettre notl -1(%%esi,%%ecx,4) (qui correspond à *(donnee+4*size-1)).

au fait, j'ai un processeur 64 bit .... ca existe un "not double long " ?

notq

ok merci kevin , ca marche super
et ca mets un peu - d'1 sec