25

Réduction d’images avec NEON

nov

Ça fait un bout de temps que j’ai codé l’agrandissement bilinéaire d’une image. J’avais repoussé l’aspect réduction (qui utilise un algorithme assez différent en fait) à plus tard.
Nous y voilà !
L’algorithme est un peu plus complexe que pour l’agrandissement, mais d’un autre coté, j’ai capitalisé sur les expérimentations effectuée lors de l’agrandissement. Du coup la mise au point de ce code n’a pas pris trop de temps !
Repose-toi Mario, Ce coup-ci c’est Yoshi qui s’y colle…

Agrandissement vs Réduction

Lors du processus d’agrandissement bilinéaire d’une image, chaque pixel destination est produit à partir de 2 pixels sources (en tous cas si on ne s’intéresse qu’a un seul axe), et cela, quelque soit la taille final de l’image.
Dans le cas de la réduction, le problème n’est plus du tout aussi simple. Chaque pixel destination est produit à partir d’un nombre variable de pixels sources. Plus la réduction est forte et plus le nombre de pixels concernés pour produire un pixel destination augmente. C’est assez facile à comprendre.

  • Lorsque vous divisez par 2 la taille d’une image, il vous faut calculer la moyenne de 2 pixels pour obtenir le pixel destination
  • Lorsque vous divisez par 4 la taille d’une image, il vous faut calculer la moyenne de 4 pixels pour obtenir le pixel destination

Il est même courant que pour un même ratio de réduction que le nombre de pixels source impliqués dans le calcul ne soit pas le même d’un pixel à l’autre.
Par exemple, si vous réduisez une image en la faisant passer de 100 pixels de large à 65 pixels alors:

  • pixel_destination[0] = 0.65 * pixel_source[0] + 0.35 * pixel_source[1]
  • pixel_destination[1] = 0.30 * pixel_source[1] + 0.65 * pixel_source[2] + 0.05 * pixel_source[3]
  • pixel_destination[2] = 0.60 * pixel_source[3] + 0.45 * pixel_source[4]
  • pixel_destination[3] = 0.20 * pixel_source[4] + 0.65 * pixel_source[5] + 0.15 * pixel_source[6]

Je reviendrai un peu plus tard sur la façon de trouver ces coefficients.
N’allez pas non plus croire en voyant l’exemple ci dessus qu’un pixel sur 2 va nécessiter une source supplémentaire, ce n’est pas toujours le cas !

Tout cela n’est pas très cool et va induire des boucles et des tests supplémentaires par rapport à l’algorithme de réduction qui lui était inconditionnel et relativement répétitif.
Mais bon pas de panique, on va corriger tout ça pour que NEON puisse fonctionner de manière optimale :)

L’algorithme en C

L’algorithme de réduction d’image est assez simple à comprendre. Il l’est moins à implémenter.
Il consiste à réaliser la somme pondérée de tous les pixels entrant dans la composition du pixel final. Plus vous réduisez votre image et plus le nombre de pixels concernés va grandir…

Comme pour l’agrandissement nous allons utiliser uniquement des entiers.
Il nous faut une variable wPixelStep qui va nous permettre de connaitre pour chaque nouveau pixel destination, quel est le premier pixel source impliqué dans la calcul et dans quel proportion.
Il nous faut une deuxième variable wFullPix qui contient le coefficient maximal appliqué a un pixel (lorsque celui-ci est totalement impliqué dans la réduction).
Enfin il nous faut calculer le nombre de pixel wNbPix impliqué dans le calcul d’un pixel destination. Nous avons vu un peu plus haut que ce nombre pouvait être variable. Nous allons donc maximiser cette valeur.

	int wPixelStep = (wSrc < < 16) / wDst;
	int wFullPix = (((wDst << 16) / wSrc) + 128) >> 8;
	int wRest = wPixelStep & 0xffff;
	int wNbPix;
	if (wRest == 0)
		wNbPix = (wPixelStep >> 16)
	else
		wNbPix = (wPixelStep >> 16) + 2;

Dans notre exemple de réduction de Yoshi:
wSrc = 320 et wDst = 128

wPixelStep vaut donc 163840 (soit 2.5 * 65536)
wFullPix vaut donc 102. Cela veut dire que chaque pixel qui serait totalement impliqué dans le calcul d’un pixel source le serait dans une proportion et 102 * 100 / 256 % (soit ~ 40% ce qui est plutôt logique pour une réduction de facteur 2.5)
Enfin wNbPix représente le nombre de pixels impliqués dans le calcul d’un pixel destination. Deux cas de figures sont possibles:

  • Soit (wSrc /wDst) est une valeur entière. Dans ce cas wNbPix = (wSrc /wDst)
  • Soit (wSrc /wDst) n’est pas entier. Dans ce cas wNbPix = floor(wSrc /wDst) + 2.

Dans le cas de notre Yoshi, wNbPix vaut 4 car wSrc /wDst = 2.5

Chaque pixel destination utilisera donc au maximum 4 pixels source.
Nous allons pré-calculer les coefficients de chacun de ces pixels sources.
Nous allons également enregistrer le premier pixel impliqué dans le calcul d’un pixel car pour certaine réduction, nos 8 bits de précisions vont rapidement s’avérer insuffisant.
Donc, nous allons corriger l’erreur à chaque pixel.

Voila le code permettant la construction de notre table de coefficient sur l’axe des X.

	wStartPoint = 0;
	for (x = 0 ; x < wDst ; x++)
	{
		xLine = (wStartPoint >> 16);
		xCoef = wFullPix - (((wStartPoint & 0xffff) * wFullPix) >> 16);
		xEndCoef = 256 - xCoef;
		tCoefX[ptX++] = xLine;
		tCoefX[ptX++] = xCoef;
		for (pX = 1 ; pX < wNbPix; pX++)
		{
			if (xEndCoef >= wFullPix)
			{
				xCoef = wFullPix;
				xEndCoef -= wFullPix;
			}
			else if (xEndCoef > 0)
			{
				xCoef = xEndCoef;
				xEndCoef -= wFullPix;
			}
			else
			{
				xCoef = 0;
			}
			tCoefX[ptX++] = xCoef;
		}
		wStartPoint += wPixelStep;
	}

wStartPoint est notre accumulateur. C’est un nombre à virgule fixe donc la partie entière représente la coordonnée du premier pixel utile au calcul du pixel destination et la partie décimale le coefficient à appliquer sur ce premier pixel.
xLine est la partie entière de wStartPoint. Il s’agit donc de la coordonné du premier pixel qui sera utilisé pour calculer notre pixel destination.
xCoef vaut le coefficient à appliquer aux pixels. Il existe plusieurs cas de figure pou calculer xCoef:

  • xCoef du premier pixel vaut la partie décimale de wStartPoint * wFullPix
  • pour tous les pixels intermédiaires xCoef vaut wFullPix
  • pour le dernier pixel xCoef vaut 256 – la somme de tous les coefficients calculés précédemment.
  • Enfin, s’il reste des pixels alors leur coefficients vaut 0. Ce cas arrive lorsque le nombre de pixels impliqués dans le calcul est inférieur à wNbPix

Ce code nous permet dons de précalculer tous les coefficients nécessaires à l’interpolation sur l’axe des X.
On réalise exactement la même chose pour l’axe des Y (voir le code final).

Une fois que l’on a pré-calculé tous nos coefficients, il nous reste plus qu’à réaliser la somme pondéré de nos pixels.
C’est ce que fait le code suivant, qui est suffisamment simple pour se passer d’explication. (la vraie complexité étant dans le pré-calcul des coefficients).

	ptY = 0;
	for (y = 0 ; y < hDst ; y++)
	{
		yLine = tCoefY[ptY++];

		ptX = 0;
		for (x = 0 ; x < wDst ; x++)
		{
			xLine = tCoefX[ptX++];

			r = g = b = a = 0;
			for (pY = 0 ; pY < hNbPix; pY++)
			{
				yCoef = tCoefY[ptY + pY];
				for (pX = 0 ; pX < wNbPix; pX++)
				{
					xCoef = tCoefX[ptX + pX];
					fullCoef = xCoef * yCoef;

					pixel = *(bSrc + (yLine + pY) * wSrc + (xLine + pX));
					a += ((pixel >> 24) & 255) * fullCoef;				// a
					r += ((pixel >> 16) & 255) * fullCoef;				// r
					g += ((pixel >> 8) & 255) * fullCoef;				// g
					b += ((pixel >> 0) & 255) * fullCoef;				// b
				}
			}
			ptX += wNbPix;

			a = a >> 16;
			r = r >> 16;
			g = g >> 16;
			b = b >> 16;

			*bDst++ = (a < < 24) + (r << 16) + (g << 8) + (b);
		}
		ptY += hNbPix;
	}

Bon au final cela nous donne le code source en C complet suivant:

void reduce_c(unsigned int *bSrc, unsigned int *bDst, int wSrc, int hSrc, int wDst, int hDst)
{
	int x, y, pX, pY;
	int r, g, b, a, pixel;
	int wPixelStep = (wSrc < < 16) / wDst;
	int wFullPix = (((wDst << 16) / wSrc) + 128) >> 8;
	int wRest = wPixelStep & 0xffff;
	int wNbPix;
	if (wRest == 0)
		wNbPix = (wPixelStep >> 16)
	else
		wNbPix = (wPixelStep >> 16) + 2;

	int hPixelStep = (hSrc < < 16) / hDst;
	int hFullPix = (((hDst << 16) / hSrc) + 128) >> 8;
	int hNbPix = (hPixelStep >> 16) + 2;

	int wStartPoint, hStartPoint;
	int xLine, yLine;
	int xCoef, yCoef, fullCoef, alphaCoef, sumCoef;
	int xEndCoef, yEndCoef;

	int tCoefX[10000];
	int tCoefY[10000];
	int ptX = 0, ptY = 0;

	int useCorrection = 0;

	wStartPoint = 0;
	for (x = 0 ; x < wDst ; x++)
	{
		xLine = (wStartPoint >> 16);
		xCoef = wFullPix - (((wStartPoint & 0xffff) * wFullPix) >> 16);
		xEndCoef = 256 - xCoef;
		tCoefX[ptX++] = xLine;
		tCoefX[ptX++] = xCoef;
		for (pX = 1 ; pX < wNbPix; pX++)
		{
			if (xEndCoef >= wFullPix)
			{
				xCoef = wFullPix;
				xEndCoef -= wFullPix;
			}
			else if (xEndCoef > 0)
			{
				xCoef = xEndCoef;
				xEndCoef -= wFullPix;
			}
			else
			{
				xCoef = 0;
			}
			tCoefX[ptX++] = xCoef;
		}
		wStartPoint += wPixelStep;
	}

	hStartPoint = 0;
	for (y = 0 ; y < hDst ; y++)
	{
		yLine = (hStartPoint >> 16);
		yCoef = hFullPix - (((hStartPoint & 0xffff) * hFullPix) >> 16);
		yEndCoef = 256 - yCoef;
		tCoefY[ptY++] = yLine;
		tCoefY[ptY++] = yCoef;
		for (pY = 1 ; pY < hNbPix; pY++)
		{
			if (yEndCoef >= hFullPix)
			{
				yCoef = hFullPix;
				yEndCoef -= hFullPix;
			}
			else if (yEndCoef > 0)
			{
				yCoef = yEndCoef;
				yEndCoef -= hFullPix;
			}
			else
			{
				yCoef = 0;
			}
			tCoefY[ptY++] = yCoef;
		}
		hStartPoint += hPixelStep;
	}

	ptY = 0;
	for (y = 0 ; y < hDst ; y++)
	{
		yLine = tCoefY[ptY++];

		ptX = 0;
		for (x = 0 ; x < wDst ; x++)
		{
			xLine = tCoefX[ptX++];

			r = g = b = a = 0;
			for (pY = 0 ; pY < hNbPix; pY++)
			{
				yCoef = tCoefY[ptY + pY];
				for (pX = 0 ; pX < wNbPix; pX++)
				{
					xCoef = tCoefX[ptX + pX];
					fullCoef = xCoef * yCoef;

					pixel = *(bSrc + (yLine + pY) * wSrc + (xLine + pX));
					a += ((pixel >> 24) & 255) * fullCoef;				// a
					r += ((pixel >> 16) & 255) * fullCoef;				// r
					g += ((pixel >> 8) & 255) * fullCoef;				// g
					b += ((pixel >> 0) & 255) * fullCoef;				// b
				}
			}
			ptX += wNbPix;

			a = a >> 16;
			r = r >> 16;
			g = g >> 16;
			b = b >> 16;

			*bDst++ = (a < < 24) + (r << 16) + (g << 8) + (b);
		}
		ptY += hNbPix;
	}
}

Résultats! Il faut approximativement le même temps pour réduire une image que pour l’agrandir en C (avec évidement des résolution source et destination identiques), puisque le code ci-dessus permet la réduction de yoshi en 8.95ms.

Image source 248*320 Réduction au plus proche 100*128 Réduction bilinéaire 100*128

Implémentation en Assembleur

Comme pour la version de l'agrandissement, le code assembleur que j'ai implémenté réalise deux passes distinctes. L'une sur l'axe des X et l'autre sur l'axe des Y. Je reviendrai un peu plus loin sur l’intérêt (autre que la simplicité du code) de séparer les traitements en X et en Y.

Reduction sur l'axe des Y : Calcul des coefficients

Nous allons pré-calculer les coefficients avant de les utiliser. Ce calcul en amont des coefficients permet surtout de simplifier l'implémentation.
Pour chaque pixels destination nous allons enregistrer:

  • L'offset du premier pixel impliqué dans la réduction
  • Les coefficients de chaque pixel concerné par la réduction

Tout d'abord il nous faut calculer les 3 valeurs

  • hPixelStep: qui va contenir l'incrément de l'offset du pixel. Autrement dit, pour chaque pixel destination quel est le premier pixel impliqué dans le calcul
  • hNbPix: le nombre de pixels (maximum) impliqué dans le calcul.
  • hFullPix: le coefficient appliqué aux composantes d'un pixel, lorsqu'il est totalement utilisé dans le calcul du pixel destination
/**********************************************************/
/**																		**/
/**	neon_reduce_sprite_y											**/
/**	reduit une image 32bit sur l'axe des Y					**/
/**	r0 : *dst														**/
/**	r1 : src															**/
/**	r2 : sprite width												**/
/**	r3 : sprite height											**/
/**	r4 : dst height												**/
/**																		**/
/**********************************************************/

neon_reduce_sprite_y:
	push			{r4-r12, lr}
	ldr			r4, [sp, #40]								@ hDst

	push			{r0-r3}
	mov			r0, r3, lsl #16							@ spriteHeight < < 16
	mov			r1, r4										@ destination height
	bl          udiv
	mov			r5, r0										@ int hPixelStep = (hSrc << 16) / hDst;
	movt			r0, #0
	mov			r7, r5, lsr #16							@ int hNbPix = (hPixelStep >> 16) + 2;
	cmp			r0, #0
	addne			r7, r7, #2
	pop			{r0-r3}

	push			{r0-r3}
	mov			r0, r4, lsl #16
	mov			r1, r3
	bl          udiv
	add			r0, r0, #128
	mov			r6, r0, lsr #8								@ int hFullPix = (((hDst < < 16) / hSrc) + 128) >> 8;
	pop			{r0-r3}

Rappelons avant de continuer l’utilisation que nous allons avoir des registres:

    r0: dest pointer
    r1: source pointer
    r2: width of the source image
    r3: height of the source image
    r4: new wanted height
    r5: hPixelStep
    r6: hFullPix
    r7: hNbPix
    r8: hStartPoint
    r9: y
    r10: yEndCoef
    r11: tCoefY : le buffer ou l’on va enregistrer les coefficients
    r12: pY
    r14: 0

Nous pouvons à présent pré-calculer nos coefficients.
Comment j’ai mis en face des instructions l’équivalent C, il n’est guère utile de détailler.
Je n’aurai rien de mieux à dire que l’explication déjà fournie plus haut.

	push			{r0-r3}
	movw			r3, #0xffff									@ used to keep only float part of hStartPoint
	mov			r14, #0										@ r14: 0
	mov			r8, #0										@ hStartPoint = 0;
	mov			r9, r4										@ hDst

.neon_reduce_sprite_y_coef_loop:
	mov			r0, r8, lsr #16							@ yLine = (hStartPoint >> 16);
	str			r0, [r11], #4								@ tCoefY[ptY++] = yLine;
	and			r0, r8, r3									@ yCoef = hFullPix - (((hStartPoint & 0xffff) * hFullPix) >> 16);
	mul			r0, r0, r6
	mov			r0, r0, lsr #16
	rsb			r0, r0, r6
	rsb			r10, r0, #256								@ yEndCoef = 256 - yCoef;
	add			r0, r0, r0, lsl #8
	add			r0, r0, r0, lsl #16
	str			r0, [r11], #4								@ tCoefY[ptY++] = yCoef;
	str			r0, [r11], #4								@ tCoefY[ptY++] = yCoef;

	sub			r12, r7, #1
.neon_reduce_sprite_y_while_start:
	cmp			r10, #0										@ if (yEndCoef < 0)
	ble			.neon_reduce_sprite_y_while_zero

	cmp			r10, r6										@ if (yEndCoef >= hFullPix)
	movge			r0, r6
	movlt			r0, r10
	sub			r10, r10, r6
	add			r0, r0, r0, lsl #8
	add			r0, r0, r0, lsl #16
	str			r0, [r11], #4								@ tCoefY[ptY++] = yCoef;
	str			r0, [r11], #4								@ tCoefY[ptY++] = yCoef;
	subs			r12, r12, #1
	bgt			.neon_reduce_sprite_y_while_start
	b				.neon_reduce_sprite_y_while_exit

.neon_reduce_sprite_y_while_zero:
	str			r14, [r11], #4
	str			r14, [r11], #4
	subs			r12, r12, #1
	bgt			.neon_reduce_sprite_y_while_start
.neon_reduce_sprite_y_while_exit:
	add			r8, r8, r5									@ hStartPoint += hPixelStep;
	subs			r9, r9, #1
	bge			.neon_reduce_sprite_y_coef_loop
	pop			{r0-r3}

Alors qu’a t-on calculer au final.
Nous avons tout d’abord enregistré l’offset de la première ligne impliqué dans le calcul, puis les 4 coefficients à utiliser pour les 4 composantes de notre pixel que nous avons en plus dupliqué 2 fois car nous allons traiter deux pixels à la fois (soit 8 composantes).
Les premières valeurs de la table des coefficients sont donc:

0
0x6b6b6b6b
0x6b6b6b6b
0x6b6b6b6b
0x6b6b6b6b
0x2a2a2a2a
0x2a2a2a2a
0x00000000
0x00000000
2
0x42424242
0x42424242
0x6b6b6b6b
0x6b6b6b6b
0x53535353
0x53535353
0x00000000
0x00000000
...

qu’il faut lire comme

un mot 32 bit valant 0
8 octets valant 0x6b (107)
8 octets valant 0x6b (107)
8 octets valant 0x2a (42)
8 octets valant 0x00 (0)
un mot 32 bit valant 2
8 octets valant 0x42 (66)
8 octets valant 0x6b (107)
8 octets valant 0x53 (83)
8 octets valant 0x00 (0)
...

et ce qui veut dire :

Se placer sur la ligne 0
pour chaque composante
     cResult = (cLigne0 * 107 + cLigne1 * 107 + cLigne2 * 42 +  cLigne3 * 0)  / 256
Se placer sur la ligne 2
pour chaque composante
     cResult = (cLigne2 * 66 + cLigne3 * 107 + cLigne4 * 63 +  cLigne5 * 0)  / 256

Désolé, mais je ne vois pas trop comment être plus clair !
Je balance tout de suite le code assembleur. Il est un simple portage de la version C. J’expliquerai après les points un peu délicat !

Reduction sur l’axe des Y : Calcul des pixels

Le traitement sur l’axe des Y est comme d’habitude nettement plus simple que celui sur l’axe des X. Je ne reviens pas sur l’explication du pourquoi de la chose !

Grâce au pré calcul de nos coefficients, l’algorithme est assez simple.
On lit d’abord quelle est la première ligne concernée par le calcul, puis on charge les coefficients dans les registres NEON et enfin on lance l’interpolation qui est la partie la plus facile de l’algorithme.

L’utilisation des registres pour le tracé sera le suivant

    r0 : not used
    r1 : source ptr
    r2 : source width
    r3 : source height
    r4 : wanted height
    r5-r11: working source ptr
    r12 : ptr coef
    r14 : dest ptr

On peut remarquer que je réserve 7 registres pour les pointeurs source.
En fait, j’utilise du code généré. J’ai prévu 6 fonctions différentes selon que la réduction utilise, 2, 3, 4, 5, 6 ou 7 pixels source. (6 fonctions car la fonction qui utiliserai un seul pixel source n’existe pas).
Cela veut aussi dire que mon algorithme de réduction bilinéaire est limitée à une réduction d’un coefficient inférieur à 6.

Je donne ici le code pour une réduction utilisant 4 pixels source (puisque c’est celle utilisée dans le cas de la réduction par 2.5 que j’ai appliqué dans mon bench).
Les autres codes sont assez simple à écrire en se basant sur celui-ci.
Il est même assez simple de généraliser à n lignes si vous en avez envie, mais dans ce cas vous serez bon pour une boucle supplémentaire.
Personnellement, je suis allé directement aux performances maximum (puisque tel était mon besoin).

.neon_reduce_sprite_y_loop_y4:
	ldr			r5, [r12], #4								@ load first offset Y
	mov			r3, r2, lsl #2								@ r3 : image width * 4
	vld1.u32		{d0 - d3}, [r12]!							@ lecture des coefs
	mla			r5, r5, r3, r1								@ working source ptr on first line
	add			r6, r5, r2, lsl #2						@ working source ptr on next line
	add			r7, r6, r2, lsl #2						@ working source ptr on next line
	add			r8, r7, r2, lsl #2						@ working source ptr on next line
	mov			r3, r2
.neon_reduce_sprite_y_loop_x4:
	vld1.u32		{q8}, [r5]!									@ read 4 pixels
	vld1.u32		{q9}, [r6]!									@ read 4 pixels
	vld1.u32		{q10}, [r7]!								@ read 4 pixels
	vld1.u32		{q11}, [r8]!								@ read 4 pixels

	vmull.u8		q14, d16, d0
	vmull.u8		q15, d17, d0
	vmlal.u8		q14, d18, d1
	vmlal.u8		q15, d19, d1
	vmlal.u8		q14, d20, d2
	vmlal.u8		q15, d21, d2
	vmlal.u8		q14, d22, d3
	vmlal.u8		q15, d23, d3

	vqrshrn.u16 d4, q14, #8									@ reduce to 8 bit
	vqrshrn.u16 d5, q15, #8									@ reduce to 8 bit

	vst1.32		{q2}, [r14]!								@ write result
	subs			r3, r3, #4
	bgt			.neon_reduce_sprite_y_loop_x4
	subs			r4, r4, #1
	bgt			.neon_reduce_sprite_y_loop_y4
Image source 248*320 Réduction bilinéaire (axe Y) 248*128

Et voilà!
Ce n’est pas ultra pipeliné tout ça, mais sinon on n’y comprend rien !
Ce code (non pipeliné) réalise la réduction sur l’axe des Y en 0.66 ms

Au niveau performance, ce n’est pas très très bon. Ca n’est jamais que 13.5 fois plus rapide que le code C, alors qu’il n’aura échappé à personne qu’on a fait que le moitié du travail. Pour mémoire, à ce stade, l’agrandissement allait lui 49 fois plus vite !

A qui la faute ???
Au cache bien sur! Nous retrouvons ici le même problème que celui obtenu avec la transposition. C’est à dire, qu’il nous faut lire les données de plusieurs lignes en “même temps”. Ces données évidement se trouvent à des endroits différents de la mémoire. Les mécanismes de preload sont donc inutiles (voir parfois contre productifs) et les accès hors cache nombreux.

Comment optimiser ?
Bon, la première chose est de pipeliner correctement. On peut alors assez facilement tomber à 0.59 ms pour la conversion en Y! (10% de gain pour 5 minutes de travail, c’est toujours bon à prendre).
Mais la vraie solution serait celle qui resoudrait ce petit problème de cache !
Je pense avoir cette solution, sauf que pour le moment je ne l’ai pas tester. Il suffit de réorganiser les données de l’image source. Il suffit d’enregistrer l’image sous forme de bandes de 4 ou 8 pixels.
On aurait donc en mémoire:

  • les 8 premiers pixels de la première ligne
  • les 8 premiers pixels de la seconde ligne
  • les 8 premiers pixels de la troisième ligne
  • les 8 premiers pixels de la dernière ligne
  • les pixels 8 à 15 de la première ligne
  • les pixels 8 à 15 de la seconde ligne

Dans ce cas, la lecture des pixels pourrait non seulement se faire de façon consécutive en mémoire, mais en plus on pourrait utiliser moins d’instructions vld1 en lisant 2 registre Qn à la fois!
Pour le moment ça reste théorique, mais si j’ai le temps de tester, je vous tiendrai au courant.

Réduction sur l’axe des X

Bon. Ca fait des semaines que je suis sur l’écriture de ce post. Aussi, je vais faire quelques raccourcis sur la réduction sur l’axe des X.
Je dirai juste que: le calcul des coefficients est quasiment identique. Vous aurez juste besoin d’entrelacer les coefficients pour arriver à paralléliser le calcul avec NEON. Si vous avez compris l’algorithme de calculs des coefficients sur l’axe de Y, et que vous vous lancer dans le codage de la réduction sur l’axe des X, vous comprendrez vite ce que j’entends par entrelacer.

Je file le code brute de fonderie !!! Apres ce sera la sélection naturelle.
Y a ceux qui vont comprendre et puis il y aura les autres ;)

.neon_reduce_sprite_x_coef_loop:
	mov			r0, r8, lsr #16							@ xPixel = (wStartPoint >> 16); (adresse)

	mov			r0, r0, lsl #2								@ xPixel *= 4
	str			r0, [r11], #8								@ tCoefX[ptX++] = xPixel;
	and			r0, r8, r3									@ xCoef = wFullPix - (((wStartPoint & 0xffff) * wFullPix) >> 16);
	mul			r0, r0, r6
	mov			r0, r0, lsr #16
	rsb			r0, r0, r6
	rsb			r10, r0, #256								@ xEndCoef = 128 - xCoef;

	add			r0, r0, r0, lsl #8
	add			r0, r0, r0, lsl #16

	str			r0, [r11], #8								@ tCoefX[ptX++] = xCoef;

	sub			r12, r7, #1
.neon_reduce_sprite_x_while_start:
	cmp			r10, #0										@ if (yEndCoef < 0)
	ble			.neon_reduce_sprite_x_while_zero

	cmp			r10, r6										@ if (yEndCoef >= wFullPix)
	movge			r0, r6
	movlt			r0, r10
	sub			r10, r10, r6

	add			r0, r0, r0, lsl #8
	add			r0, r0, r0, lsl #16
	str			r0, [r11], #8								@ tCoefX[ptX++] = xCoef;
	subs			r12, r12, #1
	bgt			.neon_reduce_sprite_x_while_start
	b				.neon_reduce_sprite_x_while_exit

.neon_reduce_sprite_x_while_zero:
	str			r14, [r11], #8
	subs			r12, r12, #1
	bgt			.neon_reduce_sprite_x_while_start
.neon_reduce_sprite_x_while_exit:
	add			r8, r8, r5									@ wStartPoint += wPixelStep;

	cmp			r2, #0
	subeq			r11, r11, r7, lsl #3
	sub			r11, r11, #4
	rsb			r2, r2, #1

	subs			r9, r9, #1
	bge			.neon_reduce_sprite_x_coef_loop

@	alignement des coefficients!
.neon_reduce_sprite_x_align_start:
	tst			r4, #7
	beq			.neon_reduce_sprite_x_align_end
	add			r12, r7, #1
.neon_reduce_sprite_x_align_loop:
	str			r14, [r11], #8								@ tCoefX[ptX++] = xCoef;
	subs			r12, r12, #1
	bgt			.neon_reduce_sprite_x_align_loop

	cmp			r2, #0
	subeq			r11, r11, r7, lsl #3
	sub			r11, r11, #4
	rsb			r2, r2, #1

	add			r4, r4, #1
	b				.neon_reduce_sprite_x_align_start
.neon_reduce_sprite_x_align_end:
	pop			{r0-r3}

Donc il y a deux principales différences:

  • r11 qui est le pointeur où je sauvegarde les coefficients fait le yoyo. Une iteration sur 2, il va intercaler des calculs de coefficients afin de pourvoir traiter (par la suite) deux pixels en parallèle avec NEON.
  • J’ai du ajouter un petit bout de code à la fin du calcul des coefficients (à partir du label .neon_reduce_sprite_x_align_start). NEON va itérer sur la largeur voulue de l’image après réduction (ici 100). Donc que se passerait il si on avait un nombre impair par exemple alors que le code de réduction va traiter 2 ou 4 pixel simultanément ? Et bien on irai tout simplement lire des pixels en dehors de l’image avec un risque assez prononcé d’un “segmentation fault”.

Pour le tracé, il faut utiliser la même méthode que celle utilisée pour l’agrandissement. A savoir charger des 32 bits dans des registres ARM puis les pousser vers NEON grâce à des vmov.
Bon c’est un peu plus compliqué que pour l’axe des Y, j’en conviens.

.neon_reduce_sprite_x_loop_y4:
	mov			r8, r4
	ldr			r12, [r0]									@ ptr coef
.neon_reduce_sprite_x_loop_x4:
	pld			[r5, #0xC0]
	ldr			r5, [r12], #4								@ Offset pixel 1
	ldr			r6, [r12], #4								@ Offset pixel 2
	vld1.u32		{d0 - d3}, [r12]!							@ lecture des coefs
	add			r5, r5, r1
	add			r6, r6, r1

	ldr			r7, [r5], #4
	vmov			s16, r7
	ldr			r7, [r5], #4
	vmov			s18, r7
	ldr			r7, [r5], #4
	vmov			s20, r7
	ldr			r7, [r5], #4
	vmov			s22, r7

	ldr			r7, [r6], #4
	vmov			s17, r7
	ldr			r7, [r6], #4
	vmov			s19, r7
	ldr			r7, [r6], #4
	vmov			s21, r7
	ldr			r7, [r6], #4
	vmov			s23, r7

	vmull.u8		q14, d8, d0
	vmlal.u8		q14, d9, d1
	vmlal.u8		q14, d10, d2
	vmlal.u8		q14, d11, d3

	vqrshrn.u16 d4, q14, #8									@ reduce to 8 bit
	vst1.32		{d4}, [r14]!								@ write result

	subs			r8, r8, #2
	bgt			.neon_reduce_sprite_x_loop_x4
	sublt			r14, r14, #4								@ on interpolé un pixel de trop !!! il faut reculer.

	add			r1, r1, r2, lsl #2						@ on saute une ligne
	subs			r3, r3, #1
	bgt			.neon_reduce_sprite_x_loop_y4
	b				.neon_reduce_sprite_x_end

Et voilà le travail.

Image source 248*320 Réduction bilinéaire C 100*128 Réduction bilinéaire asm 100*128

En termes de performance, c’est pas très bon évidement !
Il faut 1.27 ms pour réduire Yoshi avec le code non pipeline. On notera par ailleurs que l’utilisation du preload est cette fois possible !
En pipelinant et en traitant 4 pixels à la fois (au lieu de 2 dans les codes fournis), on descend à 0.98 ms

Donc pour le moment, la réduction ne s’effectue que 9.13 fois plus rapidement en assembleur qu’en C :(

Conclusion

Contre toute attente, la version C de la réduction s’est avérée plus rapide que je ne l’aurai cru.
J’étais persuadé que l’écart entre le C et l’assembleur se serait creusé lors de la réduction bilinéaire. Et bien pas du tout, bien au contraire.

Le seul truc “cool”, c’est que j’ai quand même une piste pour optimiser tout ça en réorganisant la structure de l’image en mémoire !
Evidemment, cette réorganisation n’est pas toujours une bonne idée.
La structure que je vais tester (un jour) n’est intéressante que dans le cadre de la réduction sur l’axe des Y. Elle pourrait s’avérer totalement inadaptée à d’autre algorithme! Donc ce n’est pas une solution miracle.
Ou plus exactement, c’est une solution miracle pour des applications très particulières. J’en ai justement une en tête : Un jeu vidéo.

Le moteur 2D que je m’amuse à développer en ce moment, redimensionne les sprites selon des résolutions des smartphones.
Du coup, je suis totalement certain que le passage par le redimensionnement sur l’axe des Y juste avant l’affichage est obligatoire !

Bon j’ai d’autres trucs à optimiser avant de retoucher à cette routine !
Je garde donc cette piste pour gagner quelques ultimes cycles un de ces 4!

8 Responses to “Réduction d’images avec NEON”

  1. Sammy dit :

    Suggestion: You can resize first on X dimension, because you’ll have less cache misses (no jumps from a line to another), and then, when the number of columns is reduced with the resize factor, go on Y for reduction and you’ll have much less cache misses (reduced with the resize factor)

    (sorry, I’m not able to write a readable comment in french)

  2. Etienne SOBOLE dit :

    In fact Y reduction is still faster than X reduction, so it’s a best choice to do the Y reduction first. But of course, the best is to do the fastest first !

  3. Sammy dit :

    Just curious: Why Y reduction is faster than X? It’s a matter of input width/height, or something deeper?

  4. Etienne SOBOLE dit :

    That’s due to pixel memory organisation.
    Most of case you’ll not be able to use VLDx operation when you make calculation on X axis.

    You must then use some hint to load NEON register
    Please have a look to Agrandissement bilinéaire: Le retour.

    That’s not easy to explain into a comment !

  5. [...] décompressées, je converti tous les sprites en les réduisant (ou les agrandissant) grâce aux fonctions bilinéaires expliquées ici afin qu’ils soit adaptés à la résolution du device. Enfin je les réduis en 16 bits puis [...]

  6. Fabrice dit :

    Bravo pour le tuto. J’ai un problème qui me tracasse à vous soumettre :
    En streaming, j’affiche ma source à plusieurs endroits de ma mosaique avec différents facteurs de réduction. Quel est le facteur de réduction optimal à appliquer à la source en fonction des facteurs de réduction sur mosaique?
    Merci

  7. Etienne SOBOLE dit :

    J’arrive pas bien a comprendre ton problème. Il n’y a pas un ratio meilleur.
    Quant à streaming, tu veux réduire l’image au fur et a mesure que tu reçois l’image ? Hum dans ce cas il faudrait utiliser un algo en une seule passe qui réduise en X et en Y en même temps !

  8. Fabrice dit :

    Mon objectif est d’optimiser la bande passante. Pour cela il y a une fonction zoom/shrink au niveau de l’affichage sur la mosaique et à l’encodage de la source j’applique aussi une fonction shrink.
    La source peut être affichée plusieurs fois sur la mosaique avec différentes valeur de shrink et donc dans mon streaming je voudrais envoyer seulement les pixels affichés d’ou le besoin d’une fonction shrink à l’encodage qui me permet de supprimer les pixels inutiles.
    Tout à fait mon algo réduira en une seule passe en X et Y …
    Enfin j’espère que c’est un peu plus clair…

Répondre

Human control : 7 + 6 =