[Concours n°4] A la recherche du bit perdu...

A la recherche du bit perdu... [Concours n°4] - ASM - Programmation

Marsh Posté le 19-07-2004 à 21:01:17    

Voici un concours concret et assez court qui pourra servir à tous...
 
Il s'agit de lire un bit dans un flux d'octets (MP3). Cette une routine particulièrement utilisée dans les décodeurs.
C'est le code utilisé dans les flux MPEG.
 
La routine ci-dessous récupère un bit (pointé par BitBuffer_CurrentBit) du tableau BitBuffer et incrémente CurrentBit en appliquant également un ET de 4095 (tampon tournant).
 

Code :
  1. //Déclaration globale...
  2. unsigned char BitBuffer[4096];
  3. unsigned long BitBuffer_CurrentBit;
  4. unsigned long hget1bit ( void )
  5. {
  6.     unsigned char Bit;
  7.     //Récupération de l'octet en cours
  8.     Bit = BitBuffer[(BitBuffer_CurrentBit>>3)&4095];
  9.     //Récupération du bit nécessaire 1/2 : d‚calage
  10.     Bit = Bit>>(7-(BitBuffer_CurrentBit&7));
  11.     //Récupération du bit nécessaire 2/2 : masque
  12.     Bit = Bit&1;
  13.     //Augmente les positions
  14.     BitBuffer_CurrentBit = (BitBuffer_CurrentBit+1)&4095;
  15.     return Bit;
  16. }


 
Attention : Toutes les routines accédant à BitBuffer_CurrentBit appliquent d'office un ET de 4095 avant de s'en servir réellement.
 
Update> Attention, La routine hget1bit accède au bit spécifié par CurrentBit. Cette variable peut être considéré comme étant non-linéaire (aléatoire...).
 
La règle est la suivante :
Le code le plus rapide est gagnant et évidemment, on utilise de l'assembleur et tout est permis. Il est possible d'utiliser les extensions MMX/SSE... mais je préfère que chacun fournisse au moins un code x86 standard fonctionnant sur un Pentium normal.
 
Et qu'est ce qu'on gagne ?
Le meilleur code !
 
PS: J'espère ne pas avoir fait d'erreur.


Message édité par christophe_d13 le 24-07-2004 à 09:30:06
Reply

Marsh Posté le 19-07-2004 à 21:01:17   

Reply

Marsh Posté le 19-07-2004 à 21:42:51    

« appliquent d'office un ET de 4095 »
 
de l'algèbre modulaire en somme :o
 
ça fait bidon le & 4095 ...
 
 
et y en a marre du MMX/SSE, c'est un jeu d'instructions pourris et très pénalisant à l'utilisation par rapport à des vraies unités SIMD parallèles et indépendantess

Reply

Marsh Posté le 19-07-2004 à 21:55:34    

Taz a écrit :


et y en a marre du MMX/SSE, c'est un jeu d'instructions pourris et très pénalisant à l'utilisation par rapport à des vraies unités SIMD parallèles et indépendantess


le seul truc chiant pour le MMX, c'est que si tu l'utilises, tu peux pas utiliser la FPU en même temps :o
sinon ça booste les perfs sa mère avec le SSE !


---------------
J'ai un string dans l'array (Paris Hilton)
Reply

Marsh Posté le 20-07-2004 à 08:19:36    

Taz a écrit :

ça fait bidon le & 4095 ...


Peut-être mais c'est pour vous permettre d'optimiser au max la routine.
La ligne "BitBuffer_CurrentBit = (BitBuffer_CurrentBit+1)&4095;"
Pourrait également être "BitBuffer_CurrentBit++;"
 

Taz a écrit :

et y en a marre du MMX/SSE, c'est un jeu d'instructions pourris et très pénalisant à l'utilisation par rapport à des vraies unités SIMD parallèles et indépendantess


Rien ne t'oblige à utiliser le MMX/SSE.
Pour ma part, je le fais en fonctions CPU standard.


Message édité par christophe_d13 le 20-07-2004 à 08:20:37
Reply

Marsh Posté le 20-07-2004 à 19:10:57    

Je trouve pas d'idée :|

Reply

Marsh Posté le 20-07-2004 à 19:52:04    

Harkonnen a écrit :

le seul truc chiant pour le MMX, c'est que si tu l'utilises, tu peux pas utiliser la FPU en même temps :o
sinon ça booste les perfs sa mère avec le SSE !

ben oui, mais j'ai beau demander des tests applicatifs pour qu'il se rende compte des dégats et de l'impact sur le cache, mais rien y fait. c'est sur que si tu fais que des memcpy c'est tout de suite plus rapide. Si tu travailles à côté, le MMX tu vas vite le ranger

Reply

Marsh Posté le 20-07-2004 à 23:22:16    

mais arretez le MMX c'est nul ....
SSE 2 *a la riguer*
 

Reply

Marsh Posté le 21-07-2004 à 15:07:44    

D'ailleurs, si je ne me trompe pas, on ne saura plus faire de MMX (ni de x87 et de 3DNow) sur Windows x86-64. Il n'y aura plus que les entiers et le SSE(2).

Reply

Marsh Posté le 21-07-2004 à 19:36:45    

Le MMX c'est nul... C'est pour ça qu'intel l'a sorti de son chapeau.
Vous oubliez que l'on ne possède pas systèmatiquement l'ordinateur de dernière génération.
 
Pour ma part, je reste sur ceci : Il faut avant toute chose mesurer les perfs avec plusieurs solutions pour prendre la meilleure.
Taz> Les perfs globale, pas uniquement dans un memcpy où l'on saccage le cache.

Reply

Marsh Posté le 21-07-2004 à 19:53:34    

mais je ne demande que ça.

Reply

Marsh Posté le 21-07-2004 à 19:53:34   

Reply

Marsh Posté le 22-07-2004 à 09:22:49    

Personne pour ce petit bout de code ?
Cela se fait en 20 lignes max...

Reply

Marsh Posté le 24-07-2004 à 09:28:22    

A la demande, j'ai rajouter des détails sur le post de départ.

Reply

Marsh Posté le 24-07-2004 à 15:39:47    

C'est faisable en moins de 10 instructions (sans instructions MMX & Co)   :)

Reply

Marsh Posté le 24-07-2004 à 18:01:33    

Pour ma part, j'ai fait la routine en 10 instructions exactement, en comptant le RET. J'utilise également une LUT d'un QWORD.

Reply

Marsh Posté le 24-07-2004 à 19:40:37    

vi... un truc du genre:
 
unsigned char LookUp_Table[8] = { 0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01 };
 

Reply

Marsh Posté le 24-07-2004 à 19:46:23    

Idem pour moi.

Reply

Marsh Posté le 25-07-2004 à 01:35:21    

en static const :o

Reply

Marsh Posté le 29-07-2004 à 22:23:19    

Un concours qui ne passionne pas les foules...
 
Mais bon en ASM, c'est déjà plus sélectif.

Reply

Marsh Posté le 30-07-2004 à 23:55:46    

Je veux bien participer mais je pige pas le principe
Faut simplement écrire une procédure qui reçoit currentbit et qui renvoie bit ?

Reply

Marsh Posté le 31-07-2004 à 10:51:23    

taka montrer ta méthode et expliquer comment ca marche et un petit tutorial sur les instructions que tu utilises :D

Reply

Marsh Posté le 02-08-2004 à 23:31:44    

Voici un exemple de code ASM pour GCC
 
 

Code :
  1. unsigned char hget1bit_mask[8] = { 0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01 };
  2. unsigned long hgetbits ( unsigned long NbBits );
  3. asm ("
  4.                         .align 8
  5.     _hget1bit:
  6.                         movl _BitBuffer_CurrentBit,%edx   ;//U
  7.                         movl %edx, %eax                   ;//V
  8.                         shrl $3,%edx                      ;//U
  9.                         andl $7,%eax                      ;//V
  10.                         andl $4095,%edx                   ;//U
  11.                         movb _hget1bit_mask(%eax),%al     ;//V
  12.                         incl _BitBuffer_CurrentBit        ;//U mais 2 cycles car <incl m>
  13.                         andb _BitBuffer(%edx),%al         ;//V mais 2 cycles car <andl m,r>
  14.                         setnz %al                         ;//N
  15.                         ret                               ;//N 4 … 7 cycles
  16. " );

Reply

Marsh Posté le 05-08-2004 à 01:45:23    

J'ai relu trois fois ton code avant de me souvenir que ces cons d'at&t ils inversent les deux opérandes donc je me permets de le rappeller pour les débutants dans mon genre (j'espère que je suis pas le seul tiens)
 
Je ne comprends pas cette ligne

Code :
  1. andb _BitBuffer(%edx),%al         ;//V mais 2 cycles car <andl m,r>


Comment sais tu que Buffer[(CurrentBit>>3)&4095]=1 ?
 


Message édité par Champi Monochrome le 05-08-2004 à 02:00:24
Reply

Marsh Posté le 05-08-2004 à 01:51:44    

Code :
  1. movl _BitBuffer_CurrentBit,%edx   ;//U
  2. movl %edx, %eax                   ;//V


 
t'as pas l'impression de flinguer les dependances ?

Reply

Marsh Posté le 06-08-2004 à 10:27:19    

chrisbk> C'est une dépendance WAR donc les processeurs P3, Amd K6 et 6x86 n'ont pas de problèmes (register renaming).
 
Champi Monochrome> setnz al

Reply

Marsh Posté le 18-11-2005 à 13:22:14    

Voici une petite fonction delphi mais facilement reprenable dans tous les languages
 
function GetBit(IntegerValue: Integer;IntegerPosition: Integer):Integer;register;
    {
      Entrées  EAX (IntegerValue) EDX (IntegerPosition)
      Sorties  EAX
    }
    asm
{ 1C }mov ECX,EDX   // La fonction SHR a besoin du paramètre dans CL
{ 3C }shr EAX,CL      // On effectue le décalage
{ 1C }and EAX,$01   // On ne garde que le premier bit
    end;
 
Enfin, je n'ai pas compris ce 4095 ... c'est bien un seul bit que vous souhaitez ?
 
Bonne prog !

Reply

Marsh Posté le 18-11-2005 à 13:34:55    

sinon j'ai ca ...
 
unsigned char BitBuffer[4096];  
unsigned long BitBuffer_CurrentBit;  
unsigned char Bin[256,8]
//-------------------------
//|n°oct | n°bit | valeur|
//-------------------------
//|0 | 0 | 0 |
//|... | ... | ... |
//|128 | 7 | 1 |
//.... etc
 
et on utilise :
Bin[BitBuffer[BitBuffer_CurrentBit],BitBuffer_CurrentBit & 7];
 
pour avoir le bit recherché
 
Bonne prog

Reply

Marsh Posté le 18-11-2005 à 13:40:17    

oups, milles escuses ...
 
on utilise :  
Bin[BitBuffer[BitBuffer_CurrentBit>>3],BitBuffer_CurrentBit & 7];
 
Bonne prog !


---------------
Je suis et reste un éternel apprenti
Reply

Marsh Posté le 18-11-2005 à 14:12:17    

Bon ce n'es pas de l'assembleur mais ... suivant le contexte utilisé, mieux vaut ne pas mettre ce code dans une fonction mais plutot directement lors du traitement
 
style
 
unsigned char BitBuffer[4096];  
unsigned long BitBuffer_CurrentBit;
unsigned integer Bin[256,8] // mieux vaut finalement les avoir direct en integer 32 bit
 
int main (int argc,char*argv)
 
// Le code de traitement ...
unsigned int posByte;
unsigned int posbit;
 
// dans la boucle ...
asm {
  // ici mieux vaut déjà s'etre arrangé pour avoir BitBuffer_CurrentBit dans eax
  mov eax,BitBuffer_CurrentBit // 1cycle comme ca on zappe cette instruction
  mov ebx,eax  // 1 cycle
  shr eax,3  // a peu près 3 cycle
  and ebx,7 // 1 cycle
  // je ne sais pas si ca marche (pas testé)
  mov ecx, dword ptr [BitBuffer + EAX] // 1 cycle
  // si resultat attendu dans eax
  // syntaxe peut être incorrecte suivant les compilos
  // Manque de connaissance dans la variété des compilo pour vous aiguiller
  // essayer typeof
  // sizeof etc ...
  mov eax,dword ptr [Bin + EBX * Type int] // 1 cycle
 
  // soit 7-8 cycle par bit (7 dans le cas ou eax est déjà )
}
// fin de la boucle
 
equivaudrait à :
 
Bin[BitBuffer[BitBuffer_CurrentBit>>3],BitBuffer_CurrentBit & 7];
 
 


---------------
Je suis et reste un éternel apprenti
Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed