Bonsoir !

Je voudrais parler Blit rapide. Voyons l'image ci dessous : 

(vous aurez certainement reconnu... euh.... Sonic ? )

Bref. Imaginons que je sois dans un monde d'affichage par palette : un octet par pixel.

L'image fait 12 pixels de large. Bien souvent sur les vielles machines, on contraignait la largeur des sprites pour gagner en performance (1)

Je souhaite blitter l'image sur une autre (sur l'écran par exemple), je calcule l'offset sur l'image destination du point supérieur gauche, puis je fais un memcpy de 12 octets, pour chaque ligne.

Ce memcpy pourra par exemple, sur un processeur 32 bits, copier 4 pixels à la fois (je considère un octet par pixel), donc en 3 cycles, j'ai copié toute une ligne. 

((1) la contrainte de largeur permettait de copier des mots de 4 octets entiers sans avoir à découper la fin, toujours un multiple de 4 octets (padding), quit à mettre des pixels keycolors en dernier ci besoin)

Maintenant, je veux considérer la keycolor, c'est à dire ne pas blitter les pixels violets. Mettons pour simplifier que cette keycolor est de valeur 0

Je considère toujours le fait d'afficher la première ligne le plus rapidement possible : 

Une solution est de faire ça pixel par pixel, avec un if : 

Je fais alors un for, et si le pixel[i] != 0 alors je copie un octet, sinon je ne copie pas.

Mais la, je passe à 12 cycles (au lieu de 3), octets un par un, plus 4 par 4, et en plus un if qui casserait un éventuel pipeline.

Pour faire sauter ce if, il me faut un masque. Si on regarde la première ligne, j'ai : (avec 1 un pixel transparent, 0 un pixel à afficher)

111000001111

Si je veux toujours afficher les pixels 4 par 4, je devrais dire   

fond &= masque

puis 

fond |=sprite

(vu ici l'idée de le faire en 2 temps)

https://en.wikipedia.org/wiki/Bit_blit#Technique

Ce qui coince, c'est le calcul rapide du masque : si je prends mon premier segment :

[1110]00001111

Je dois calculer par exemple 0xFFFFFF00 à partir de 0x00000002     (en décomposant 0x00 00 00 02 en considérant par exemple que le rouge est d'indice 2)

Ce qu'il me manque est une opération binaire rapide pour transformer un 0x00000002   en   0xFFFFFF00     

ou bien un 0x51002500 en 0x00FF00FF

ou bien un 0x05060007 en 0x0000FF00

Etc....

D'une manière générale pour calculer mon masque si un octet est 00 je mets FF, sinon je mets 00

J'ai simplifié en mettant 1 octet = 1 pixel, mais il existait des systèmes 16 couleurs à 4 bits par octet, mais une fois que j'aurais compris comment créer mon masque à la volée, je saurai faire dans tous les cas je pense.

(en me relisant, je me demande si je suis très clair)

-
Edité par Fvirtman 10 mai 2023 à 23:44:59

Hello,

(en me relisant, je me demande si je suis très clair)

 Je sais pas, tu confirmes vouloir générer un masque binaire pour effectuer le processus de blitting efficacement ?

Je vois trois solutions, du plus efficace je pense au moins efficace,

• Utilisation des instructions SIMD, qui pourraient effectuer le masquage sur plusieurs octets à la fois.
• Une table de correspondance (lookup table), il faudrait créer une table de correspondance avec 256 entrées où chaque entrée est le masque correspondant pour cet octet.
• Utilisation des opérateurs bit à bit.

Salut !

Oui, effectivement je veux construire le masque binaire pour blitter le plus vite possible. 

Même si avec nos machines actuelles, l'optimisation n'est pas primordiale, je m'intéresse aux vieilles machines, vieux algos.

j'aime bien l'idée de la lookuptable, je pense que ça peut être pas mal ! Après je finirai avec des opérateurs bit à bit !

Je vais creuser vers les lookuptable ! Merci pour ta réponse !

Salut,

Cool, un défi.

Si je comprends bien, tu cherches une fonction telle que (ramenée à un octet) :

B<>0 = 00

B==0 = FF

avec le genre d'astuce qu'on trouve ici ou là.

J'ai bien résumé ?

Edit : regarde par là chapitre 6 si tu es un peu à l'aise avec de l'assembleur, il semble y avoir une piste.

Ok, ça donne ça au plus court :

#define M0 0x80808080
#define M1 0x7F7F7F7F

uint32_t FvirtmanMask(uint32_t val)
{
    uint32_t temp = (((((((val & M1) + M1) | val) & M0) >>7) + M1) & M1);
    return ((temp + temp) | temp);
}

Par contre, ça fait une variable à retenir, mais pas de branchement...

avec :

int main(void)
{
    uint32_t value = 0x2100AA00;

    printf("value = %08X\n", FvirtmanMask(value));

    return 0;
}

on obtient :

value = 00FF00FF

Process returned 0 (0x0)   execution time : 0.219 s
Press any key to continue.

Bonne continuation.

-
Edité par drx 15 mai 2023 à 15:53:59

Merci drx pour ta réponse ! Et pardon pour la réponse tardive !

Il faudra que j'essaie ça, faire des benchs entre plusieurs algos de blit pour avoir le truc le plus rapide possible

(Comme je disais, c'est même pas pour quelque chose de concret car maintenant on a des accélérations matérielles, mais pour du théorique ! )