GP2X Rgb888 To Sdl_surface?

[A_SN]

I got quite a problem with the way I do things in SDL. I internally use my own image format, which is RGB888 in a uint8_t *** array, and to blit it I turn my final screen image into a regular SDL_Surface, the problem being that the process of turning my custom made array into a SDL_Surface is extremely expensive. Here's how I do it :

void putpixel(SDL_Surface *surface, int x, int y, Uint32 pixel)
{
	int bpp = surface->format->BytesPerPixel;
	/* Here p is the address to the pixel we want to set */
	Uint8 *p = (Uint8 *)surface->pixels + y * surface->pitch + x * bpp;

	switch(bpp) {
	case 4:
		*(Uint32 *)p = pixel;
		break;

	case 3:
		if(SDL_BYTEORDER == SDL_BIG_ENDIAN) {
			p[0] = (pixel >> 16) & 0xff;
			p[1] = (pixel >> 8) & 0xff;
			p[2] = pixel & 0xff;
		} else {
			p[0] = pixel & 0xff;
			p[1] = (pixel >> 8) & 0xff;
			p[2] = (pixel >> 16) & 0xff;
		}
		break;

	case 2:
		*(Uint16 *)p = pixel;
		break;

	case 1:
		*p = pixel;
		break;
	}
}


void surf_array(SDL_Surface **surf, uint8_t ***image, uint16_t width, uint16_t height)
{
	uint16_t ix, iy;
 
	for (ix=0; ix<width; ix++)
		for (iy=0; iy<height; iy++)
			putpixel(*surf, ix, iy, SDL_MapRGB((*surf)->format, image[0][ix][iy], image[1][ix][iy], image[2][ix][iy]));
}

The first dimension of the array is the colour layer, the second the X axis and the third the Y axis. Of course I'm aware that calling putpixel this many times isn't good and should probably merge the two functions, but I don't think it will cut it.

Basically what I'd like to know is what's the very fastest way to blit my RGB888 array to the screen SDL_Surface, so if anyone has made any code that can apply in this type of situation, wlel feel free to share. And if I didn't make myself very clear well sorry about that it's the end of the day for me

 

[Gadget]

Personally I read the images into an SDL_Surface this way:-

EDIT: I guess what you are trying to get away from here is the usage of the array.

You should store your image in a file this way:-

Write the height of the image (using a 32 bit int - 4 bytes in size, which I think is just an int in C?) to your file.
Write the width of the image (using a 32 bit int - 4 byte in size) to your file.

Loop through your image and output each pixel in the order:-

for (int x=0;x<HEIGHT;x++)
{
	for (int y=0;y<WIDTH;y++)
	{
		Output your pixel data here, so 3 bytes for each pixel
	}

}

Your file will now contain effectively a bitmap, without the normal header. You can get clever later and add many bitmaps into a single file, if you keep track of the offset for each bitmap, using an index table of sorts.


If you read that file back into the surface buffer in the example below, you are recreating that bitmap for direct use in the SDL_Surface.

SDL_Surface * LoadImage(char* FileName, int Index)//, u8 R, u8 G, u8 B, u8 A)
{

	SDL_Surface* TempSurface1;
	SDL_Surface* TempSurface2;

	//ADD YOUR CODE HERE TO OPEN AND READ YOUR FILE INTO A FILE BUFFER
	{YOUR CODE HERE}
  
	 //CREATE BITMAP SURFACE BUFFER
	bitmap = (char*) calloc (1,(height * width) * 2); //16 bit, you would need * 3 for 24 bit
  
	//READ YOUR BITMAP FROM YOUR FILE BUFFER INTO THE SURFACE BUFFER
   eg.  
   for (int x=0;x<HEIGHT;x++)
   {
	   for (int y=0;y<WIDTH;y++)
	   {
		   write 2 bytes (16 bit, or 3 for 24 bit) to my surface buffer
	   }
   }
	//ALTERNATIVELY, YOU MAY WANT TO CONVERT YOUR PIXELS TO 16 BIT AS YOU READ THE PIXEL DATA IN


	//CLOSE FILE AND FILE BUFFER
	{YOUR CODE HERE}

	//NOW CREATE AN RGB SURFACE USING THE POINTER TO YOUR BITMAP SURFACE BUFFER
	TempSurface1 = SDL_CreateRGBSurfaceFrom(bitmap,width,height,16,(width * 2),0,0,0,0); //AGAIN NEEDS * 3 for 24 bit
	//CREATE A HW SURFACE - COPIES THE SURFACE INTO UPPER 32Mb
	TempSurface2 = SDL_DisplayFormat(TempSurface1);

	//FREE TEMP SURFACE
	free(bitmap);
	TempSurface1->pixels = NULL;
	SDL_FreeSurface(TempSurface1);
	TempSurface1 = NULL;

	//RETURN A POINTER TO THE NEW HW SURFACE
	return TempSurface2;

}

 

[gfoot]

As Gadget implied, you really ought to store all your data in the same format that SDL is using for the display. Then you should do any (slow) conversion up front, and keep things nice and fast in your game loop.

If you absolutely must store your intermediate result with different colours in different bytes, the fastest way to read it back on this CPU is going to be storing it at 32bpp, not 24bpp, in an aligned array. Then at the low level the processor can read an entire pixel in one operation, and combine into the bottom 16 bits in another four operations, which is probably as tight as you're going to get. You can then read a second pixel, pack that too, and write out both destination pixels in one word write.

The code you posted probably compiles to three individual byte reads, some logic to combine them into a single word, then inside your function a switch per pixel and more logic to split the word into smaller types again (in some cases). You want to move as much of that out of the loop as possible, which really amounts to writing a separate surf_array routine for each target depth, calling separate putpixel routines (does SDL really not supply these?). Using templates you can do this without actually duplicating all the code, but a lot of people are scared of them. If you know you're using 16bpp targets, though, just write that routine - why bother with the others if you're not going to use them?

Just for fun, here's some untested example code... this converts 32bpp to 16bpp, two pixels at a time, and writes them out as a single word. You could flesh this out into a C-callable function fairly easily. In the comments, a dot means a zero bit, and an X means an unused bit which may contain any value. I think the code would be simpler if you could store your colour components in a different order...

Hmm, I have a feeling the hardware blitter might support this anyway - it can definitely convert up from 8bpp. If it can also convert down from 32 bpp, that would be a better way to do it.

	// r0 = input address (32bpp, word-aligned)
	// r1 = output address (16bpp, word-aligned)
	// r2 = number of pixels (must be even)
	// r7 = 0x001f001f = red/blue mask after shifting
	// r8 = 0x000003e0 = green mask after shifting

1:
	// read and pack first pixel
	ldr	   r5, [r0], #4		// bbbbbXXX ggggggXX rrrrrXXX
	and	   r3, r7, r5, lsr #3  // ...bbbbb ........ ...rrrrr
	orr 	  r3, r3, r3, lsr #5  // ...XXXXX bbbbb... ...rrrrr
	and	   r4, r8, r5, lsr #6  // ........ .....ggg ggg.....
	orr	   r5, r3, r4		  // ...XXXXX bbbbbggg gggrrrrr

	// read and pack second pixel
	ldr	   r6, [r0], #4		// bbbbbXXX ggggggXX rrrrrXXX
	and	   r3, r7, r6, lsr #3  // ...bbbbb ........ ...rrrrr
	orr	   r3, r3, r3, lsr #5  // ...XXXXX bbbbb... ...rrrrr
	and	   r4, r8, r6, lsr #6  // ........ .....ggg ggg.....
	orr	   r6, r3, r4		  // ...XXXXX bbbbbggg gggrrrrr

	// combine and write both pixels to output
	bic	   r5, r5, #0x00ff0000
	orr	   r5, r5, r6, asl #16
	str	   r5, [r1], #4

	// decrement pixel count and loop
	subs	  r2, r2, #2
	bne	   1b

 

[Gadget]

I agree. Will that ASM compile in code blocks? I haven't been able to compile any inline ASM yet...

Another point, coming back to my intial reply. If you know the width and height of the bitmap, you can read and write the whole thing directly to and from your buffer area.

Instead of looping through each pixel,

for (int x=0;x<height;x++)
{
for (int y=0;y<width;y++)
{
copy pixel to bitmap buffer area
}
}

//THIS WOULD BE BETTER:-
memcpy(&bitmap,&filebuffer[iPointer],iSize); //iPointer would be the offset for the file you are reading
//iSize would be ((w * h) * pitch). eg. (320 x 240) * 3

You could just copy the whole lot, by just telling the memcpy function the exact size. The order of the data will be correct. This of course isn't the case if you wanted to blit this way. ie. handle the blitting routine yourself, from SDL_Surface to screen SDL_Surface would require a little more work, but it would be rather slow without some nifty ASM routines, and hardware assitance.

Simple overview of what you need to do:-

1) First create your bitmap files instead of using a file that holds your data in the array type setup you have.
2) Open your test file and get the file size.
3) Create a buffer in memory.

  FILE * pFile;

	long lSize;
	char * buffer;

	Uint32 width = 0;
	Uint32 height = 0;


	Uint32 iBitmap = 0;
	char * bitmap;

	pFile = fopen (FileName,"rb" );
	if (pFile==NULL) exit (1);

	fseek (pFile , 0 , SEEK_END);
	lSize = ftell (pFile); //GET FILE SIZE
	rewind (pFile); //REWIND TO START OF FILE

	buffer = (char*) malloc (lSize); //CREATE A FILE BUFFER - THIS WILL HOLD THE WHOLE FILE IN RAM

	if (buffer == NULL) exit (2);
	fread (buffer,1,lSize,pFile);  //READ THE WHOLE FILE INTO RAM


	//READ THE WIDTH AND HEIGHT INFO
	long iPointer = 0;

	//GET W AND H
	memcpy(&width,&buffer[iPointer],4);
	iPointer+= 4; //INCREASE THE POINTER
	memcpy(&height,&buffer[iPointer],4);
	iPointer+= 4; //AND AGAIN

	//POINTER IS NOW POINTING AT PIXEL DATA
	int iBitmapSize = ((width * height) * 3);

	//CREATE A BUFFER IN RAM READY TO HOLD ALL THE PIXEL DATA
	bitmap = (char*) calloc (1,(height * width) * 3);

	//COPY BITMAP PIXEL DATA FROM FILE INTO THE BUFFER - bitmap)
	memcpy(&bitmap,&filebuffer[iPointer],iBitmapSize); 

	//THEN CALL THE SDL_CreateRGBSurfaceFrom, passing &bitmap as your pixels pointer.

	//THEN CALL SDL_DisplayFormat(TempSurface1); which I believe will format the surface to 16bpp or whatever you have set as your primary surface.

 

[gfoot]

I don't know about codeblocks, but presumably it's just passing your source code to gcc. If you want to embed the above stuff in a function, you can do this:

void convert_32bpp_to_16bpp( void *src_addr, void *dest_addr, int num_pixels )
{
	asm( "... pasted the code here..."
		:
		: "r" (src_addr), "r" (dest_addr), "r" (num_pixels)
		: "r3", "r4", "r5", "r6", "r7", "r8", "memory"
	);
}

and change the references to r0, r1, r2 into %0, %1, %2. As it's self-contained though, you could just write a function prolog and epilog for it and put it in a .s file instead. Something like:

	.text
	.global convert_32bpp_to_16bpp
	.align 2
convert_32bpp_to_16bpp:
	mov	ip, sp
	stmfd  sp!, { r4-r8, fp, ip, lr, pc }
	sub	 fp, ip, #4
	
	ldr r7, x001f001f
	mov r8, #0x000003e0

	...paste assembler code here...

	ldmfd  sp, { r4-r8, fp, sp, pc }

x001f001f:
	.word 0x001f001f

using the same function prototype as above to access it from C code. I haven't done much prolog/epilog stuff on arm before though, I may have got it wrong.

[Edit: I forgot to load r7 and r8 with the right constants - I've edited the code for the .s version, but not the inline one as it's a bit more awkward there...]

 

[Gadget]

I get this when compiling:-

Graphics.h:37: error: stray '#' in program
Graphics.h:38: error: stray '#' in program
Graphics.h:39: error: stray '#' in program
Graphics.h:40: error: stray '#' in program
Graphics.h:44: error: stray '#' in program
Graphics.h:45: error: stray '#' in program
Graphics.h:46: error: stray '#' in program
Graphics.h:47: error: stray '#' in program
Graphics.h:51: error: stray '#' in program
Graphics.h:52: error: stray '#' in program
Graphics.h:53: error: stray '#' in program
Graphics.h:56: error: stray '#' in program
In file included from main.cpp:22:
Graphics.h:57:15: error: invalid suffix "b" on integer constant
Graphics.h: In function 'void convert_32bpp_to_16bpp(void*, void*, int)':
Graphics.h:35: error: expected string-literal before numeric constant
Process terminated with status 1 (0 minutes, 7 seconds)

 

[A_SN]

Personally I read the images into an SDL_Surface this way:-

EDIT: I guess what you are trying to get away from here is the usage of the array.

You should store your image in a file this way:-

Write the height of the image (using a 32 bit int - 4 bytes in size, which I think is just an int in C?) to your file.
Write the width of the image (using a 32 bit int - 4 byte in size) to your file.

There's only one problem with it. The way I store my bitmaps doesn't matter at all. The reason for that is that I do operations on my images, for example, I will multiply each color byte with some byte and shift rightwards by 8 bits to have my image shaded, that's just an example. So basically what I'm doing internally is my own blitter/graphics engine. What I need to convert is the very final 3 colours x 320x240 screen.

So basically at some point I must have 3 separate colour bytes, and inside my game loop I must convert that..

 

[A_SN]

As Gadget implied, you really ought to store all your data in the same format that SDL is using for the display. Then you should do any (slow) conversion up front, and keep things nice and fast in your game loop.

Can't do that. The 3 colour bytes are getting *calculated* inside the game loop, so I have no choice but to convert at the end of the loop. The reason for that is that my values are calculated, I'm not just displaying sprites, I'm also making operation on them like shading them, or even create gradients or coloured circles from scratch, and that's stuff I must do inside my game loop since it's all real time.

And I'd like to avoid using ASM. I know that this is as fast as it could possibly get, but I'm not too familiar with ASM and most of all I'd like to keep it portable (actually right now I'm doing all the developpement purely on Windows, for obvious reasons of simplicity, and every once in a while I'll test how things go on the GP2X, until it'll be all done and that I'll release it for the GP2X)

So as I understand from your post, I should move from sprite[colour_layer][x_position][y_position] to sprite[x_position][y_position][colour_layer] so I have my colour bytes aligned contiguously? or would it be even better if I have a struct for my 3 colour bytes to put in?

By the way, I've just looked at my code again (although I got most of the code I posted from libsdl.org) and it seems that I could directly do p[0]=my_red_colour_byte; p[1]=my_green_colour_byte and so on, right? If I have my colour bytes aligned in my array I guess it should speed things up..

 

[Gadget]

There's only one problem with it. The way I store my bitmaps doesn't matter at all. The reason for that is that I do operations on my images, for example, I will multiply each color byte with some byte and shift rightwards by 8 bits to have my image shaded, that's just an example. So basically what I'm doing internally is my own blitter/graphics engine. What I need to convert is the very final 3 colours x 320x240 screen.

So basically at some point I must have 3 separate colour bytes, and inside my game loop I must convert that..

void ColourBlit(SDL_Surface *Dest, SDL_Surface *Source, int DestX, int DestY, bool R, bool G, bool B)
{
	SDL_LockSurface(Source);
	SDL_LockSurface(Dest);
	short* SPixels = (short*)Source->pixels;
	short* DPixels = (short*)Dest->pixels;
	int SPitch = Source->pitch / 2; //could use >>
	int DPitch = Dest->pitch / 2;
	int mask = 0;
	if (B)
	{
		mask = 31;
	}
	if (G)
	{
		mask = (mask | (63 << 5));
	}
	if (R)
	{
		mask = (mask | (31 << 11));
	}

	int iWidth = Source->w-1;
	int iHeight = Source->h-1;

	int pixel = 0;
	short* SP = &SPixels[0 * SPitch];
	for(int x=0;x<iHeight;x++) //SCAN SOURCE
	{
	  //GET POINTER TO SOURCE AND DEST ROW
	  //LEFT
	  //short* SP = &SPixels[x * SPitch];
	  short* DP = &DPixels[(x + DestY) * DPitch];
	  DP+=DestX;
	  for(int y=iWidth;y>-1;y--)
	  {
		if (*SP != 0) //FOUND A NON TRANSPARENT PIXEL
		{
			pixel = *SP;
			*DP = (pixel & mask); //we could do allsorts of interesting things using bitmasks here, with shifts etc
		}
		DP++;
		SP++;
	  }
	}

	SDL_UnlockSurface(Source);
	SDL_UnlockSurface(Dest);
}

This example code (quickly thrown together) modifies the seperate colour channels. I use it to tint blit a sprite in my game. When the enemy ships get hit, it flashes red. You could adapt something like this to do other effects with pixels. It's slow and really needs to be done in ASM for larger sprites. If I can get inline ASM compiling I will give it a crack. From some of the ARM ASM examples I have seen you can load 8 (I think) or more registers and operate on all the registers at once. Just like the way MMX works. So you could tint blit a sprite much quicker that way. 16 bit is faster than 24 bit on the GP2X, (or so I believe) but that's not really a surprise. Granted that 24bit is easier to work with.

Of course the other posibility you have is to store 'master' copies of the images in 24 bit format, and then create 16bit versions in RAM, based on whatever colour manipulation routines you have. Converting to 16 bit from 24bit is pretty easy. Infact, here a nifty macro from Dzz:-

#define XRGB(r,g,B)  (((r) << 11) | ((g) << 5) | (B))

You could modify something like that to do the same thing for a passed 24bit value (instead of R,G,B). I guess you already know most of this, but it adds to the post for anyone else interested in this stuff.

My current challenge is to adapt the code above to 'border' a sprite. Like you see in some games when you hover the cursor over an enemy (eg. Diablo). Bordering a sprite is a bit of a challenge. I need to work out the fastest way of putting a 1 pixel border all the way around an image. I suppose my code could start from the middle of one axis and work outwards until a background pixel is found. Repeat for all rows / cols and both sides of the sprite in that axis, then flip the axis. Doing that every frame has got to suck, but at the end of the day it will only be used to highlighting one selected sprite.

 

[gfoot]

Gadget, when you're doing inline assembly you must write the whole assembler block as a string - e.g. asm( "mov r0, r1" ). For multi-line blocks it's common to embed newlines and start new strings for each line:

asm(
	"mov r0, r1	  \n"
	"mov r1, r2	  \n"
);

The preprocessor pastes adjacent strings together, so this is the same as having one string with an embedded newline.

I think the best way for this though is to use a separate assembly file with the .s extension. I've uploaded a working version here, along with a test program:

http://www.glost.eclipse.co.uk/gfoot/gp2x/...pp_to_16bpp.zip

There were also some silly mistakes in the code - I got some of the opcodes wrong! - shows how new I am to arm assembler... I'll edit the original post.

[Edit: I also profiled this crudely - it takes about 8.5ms to convet a 320x240 array - that's half of a 60Hz frame - still quite significant. You could easily run this code on the coprocessor, though maybe it's rather memory-heavy...]

A_SN: keeping related data together is an important part of optimizing cache usage, in particular, to relieve memory bandwidth problems. You need to trade off the best layout for your generating code against the best layout for the blitting code. For the blitting code it's definitely better to keep the colour components of a single pixel together in memory, but it's always possible that your generating code prefers to deal with one channel at a time.

You're probably best off keeping your pixel data together, and keeping your row data together - so index as data[y][x][component]. It doesn't make any difference whether you implement it as an array or as a struct, so long as it's tightly packed in memory.

 

[rabidcow]

As Gadget implied, you really ought to store all your data in the same format that SDL is using for the display. Then you should do any (slow) conversion up front, and keep things nice and fast in your game loop.

Can't do that. The 3 colour bytes are getting *calculated* inside the game loop, so I have no choice but to convert at the end of the loop. The reason for that is that my values are calculated, I'm not just displaying sprites, I'm also making operation on them like shading them, or even create gradients or coloured circles from scratch, and that's stuff I must do inside my game loop since it's all real time.

Convert as you finish each pixel instead of after accumulating an entire image. Shifts are all but free on arm and masks are cheap.

The inverse of the XRGB macro above is:
#define GET_RED(X) (((X)>>11)&31)
#define GET_GREEN(X) (((X)>>5)&63)
#define GET_BLUE(X) ((X)&31)

My current challenge is to adapt the code above to 'border' a sprite. Like you see in some games when you hover the cursor over an enemy (eg. Diablo). Bordering a sprite is a bit of a challenge. I need to work out the fastest way of putting a 1 pixel border all the way around an image. I suppose my code could start from the middle of one axis and work outwards until a background pixel is found. Repeat for all rows / cols and both sides of the sprite in that axis, then flip the axis. Doing that every frame has got to suck, but at the end of the day it will only be used to highlighting one selected sprite.

Use pregenerated art if you can, either another monochrome bitmap or a special color. Tracing the boundary would be faster than your method here, but both will fail if there are holes or disconnected pieces. If all else fails, you can scan the entire frame for edge pixels, which looks at a lot more data but has better cache locality.

 

[paeryn]

A_SN:
If you're using HW_SDL and writing directly to SDL surfaces in these amounts then make sure they are not HWSURFACES (this includes the main screen surface which is always a HWSURFACE even if you ask for SW) unless you're using the MMU-hack, as reading/writing to them is quite a lot slower.

gfoot:
I don't think SDL has individual get/put pixel routines - the overheads involved would be tremendous.

Gadget:
ARMV4 doesn't contain any SIMD instructions, only the VFP (Vector Floating Point) co-processor has them, and that doesn't support integers (nor is it included on the GP2X - if only they had...)
Saturated arithmetic and accumulate-add instructions weren't added until V5 (XScale), and SIMD came in with V6 (which is ARM11 and up)

 

[Gadget]

A_SN:
If you're using HW_SDL and writing directly to SDL surfaces in these amounts then make sure they are not HWSURFACES (this includes the main screen surface which is always a HWSURFACE even if you ask for SW) unless you're using the MMU-hack, as reading/writing to them is quite a lot slower.

gfoot:
I don't think SDL has individual get/put pixel routines - the overheads involved would be tremendous.

Gadget:
ARMV4 doesn't contain any SIMD instructions, only the VFP (Vector Floating Point) co-processor has them, and that doesn't support integers (nor is it included on the GP2X - if only they had...)
Saturated arithmetic and accumulate-add instructions weren't added until V5 (XScale), and SIMD came in with V6 (which is ARM11 and up)

I realise now I was think about Dzz's ASM code to blit. or clear a surface, moving x number of pixels at once. So you could blit faster that way, but would still need a per pixel manipulation first. I wish they had made the GP2X just that bit more powerful.

 

[Gadget]

void convert_32bpp_to_16bpp( void *src_addr, void *dest_addr, int num_pixels )
{
asm( "... pasted the code here..."
:
: "r" (src_addr), "r" (dest_addr), "r" (num_pixels)
: "r3", "r4", "r5", "r6", "r7", "r8", "memory"
);
}

What is this line for here? And the reference to "memory" on the end?

 

[paeryn]

void convert_32bpp_to_16bpp( void *src_addr, void *dest_addr, int num_pixels )
{
asm( "... pasted the code here..."
:
: "r" (src_addr), "r" (dest_addr), "r" (num_pixels)
: "r3", "r4", "r5", "r6", "r7", "r8", "memory"
);
}

What is this line for here? And the reference to "memory" on the end?

It tells gcc which registers will be clobbered by your routine so it can either avoid using those registers around that part of the code, or to save them to the stack and restore them afterwards. The memory bit just says that your code will be reading/writing directly to memory and so gcc will make sure that any registers holding variables have to be flushed back to memory before it executes your code.

 

[A_SN]

following your advices I tried optimizing as much as I could, here is the code I'm now using that replaces the code I originaly used :

void surf_array_o(SDL_Surface *surface, uint8_t ***image, uint16_t width, uint16_t height)	//puts pixels from an array to a surface (optimized)
{
	uint16_t ix, ix3, iy, pitch_value=surface->pitch;
	uint8_t *p;
	void *pixels_start = surface->pixels;
 
	for (ix=0; ix<width; ix++)
	{
		ix3 = ix*3;
		for (iy=0; iy<height; iy++)
		{
			   p = (uint8_t *) pixels_start + (iy * pitch_value) + ix3;		//p == address to the pixel
			   p[0] = image[ix][iy][0];
			   p[1] = image[ix][iy][1];
			   p[2] = image[ix][iy][2];
		}
	}

}

I really cannot see how I could make it any faster in C, but if you do I'll be glad to know. I'll later modify it so that the ultimate modification brought to the pixels of my final screen array get directly written to the surface.

 

[gfoot]

Before optimizing, it's always worth profiling. It tells you how slow your code is at the moment, and which bits are slowest, and it's invaluable after optimizing because then it tells you how effective your optimizations were.

Looping over Y before X, and storing your image data in that order too (i.e. image[iy][ix][0] rather than image[ix][iy][0]) would improve cache coherency.

There's also potential for optimization that the compiler doesn't know about due to the nested pointer structure of your array - we know that the first and second level pointers are constant, but the compiler can't know that - as they're not local, it has to assume that your pixel writes might actually overwrite the pointer data. So it can't optimise out the array dereferencing, which means you're doing 9 unnecessary dereferences in your inner loop.

One way to get around this is to alias the pointers into local variables at the start of each level of loop. So at the start of your x loop (which ought to be y, as I said before) you'd store image_ix = image[ix] in a local variable. Then at the start of your y loop (which ought to be x) you'd store image_ix_iy = image_ix[iy]. Then do all your pixel writes relative to the last alias. Because the aliases are local variables which you never take the address of, the compiler can now assume their values don't change due to the other pointer writes, and better still, it can keep them in registers throughout.

Another point is that your nested pointer arrangement for your image data may not be ideal, depending on how you actually allocated it. If you allocated first an array of uint8_t**, then for each of those an array of uint8_t*, then for each of those an array of 3 uint8_t, then your actual pixel data could be randomly scattered around your heap, which is terrible for cache coherency and forces you to access the pixel data via nested pointer lookups.

If you allocate your entire root data as one chunk (width*height*3) and set up the nested pointers to point into that block, cache coherency will generally improve, and you can remove even more pointer lookups from the loop. In a way the pointers are then redundant, but they may still be useful for other areas of code.

 

[Gadget]

paeryn, thanks for the reply!

EDIT
gfoot, thanks!!

I found this:- http://www.gp32x.de/board/index.php?showtopic=28490&hl=
But I am unsure if I am using gcc 4.1.0? How can I tell? I tried gcc /? and -? but nada...

 

[gfoot]

"gcc -v" should tell you the basic version of gcc.

When I said profiling though, I really just meant timing bits of your code...

PGO is mostly useful if you can exercise your whole program in a realistic way. Something I found interesting which I read somewhere (a paper about load-in-place?) was the idea of defining compound integer types with min/max values specified. They don't have to be stored differently to normal ints in hardware, but the ranges could be used by the optimiser to help it out in some cases. It would also be cool to have a type for an int which is usually zero, for example - the "usually" could hint the compiler what the result of certain calculations is likely to be, and make it bias its branches in that direction.

The penalties of braching vs conditional execution are interesting - it looks like a conditional instruction whose condition fails costs exactly 1 cycle, no matter what the instruction is, but a branch costs about 5 cycles, as the pipeline gets flushed and restarted, and we have a 5-deep pipe. So branching is still better than conditional execution if you're skipping more than 4 instructions.

 

[A_SN]

Before optimizing, it's always worth profiling. It tells you how slow your code is at the moment, and which bits are slowest, and it's invaluable after optimizing because then it tells you how effective your optimizations were.

Looping over Y before X, and storing your image data in that order too (i.e. image[iy][ix][0] rather than image[ix][iy][0]) would improve cache coherency.

There's also potential for optimization that the compiler doesn't know about due to the nested pointer structure of your array - we know that the first and second level pointers are constant, but the compiler can't know that - as they're not local, it has to assume that your pixel writes might actually overwrite the pointer data. So it can't optimise out the array dereferencing, which means you're doing 9 unnecessary dereferences in your inner loop.

One way to get around this is to alias the pointers into local variables at the start of each level of loop. So at the start of your x loop (which ought to be y, as I said before) you'd store image_ix = image[ix] in a local variable. Then at the start of your y loop (which ought to be x) you'd store image_ix_iy = image_ix[iy]. Then do all your pixel writes relative to the last alias. Because the aliases are local variables which you never take the address of, the compiler can now assume their values don't change due to the other pointer writes, and better still, it can keep them in registers throughout.

Another point is that your nested pointer arrangement for your image data may not be ideal, depending on how you actually allocated it. If you allocated first an array of uint8_t**, then for each of those an array of uint8_t*, then for each of those an array of 3 uint8_t, then your actual pixel data could be randomly scattered around your heap, which is terrible for cache coherency and forces you to access the pixel data via nested pointer lookups.

If you allocate your entire root data as one chunk (width*height*3) and set up the nested pointers to point into that block, cache coherency will generally improve, and you can remove even more pointer lookups from the loop. In a way the pointers are then redundant, but they may still be useful for other areas of code.

I did profiling with gprof. turned out my rotation function was taking about 52% of the time, and the rest was equally shared between surf_array and putpixel, but I guess you were talking about a more precise kind of profiling that that, weren't you?

There's something I don't understand tho, how can inverting the X and Y axis improve things? I mean it's not as if I had X first and always started my loop with Y, I do it in the correct order, so that if my data was aligned (which is probably not, thanks for pointing that out) it would be processed in the right order. is it because on the GP2X there's 320 X's as opposed to 240 Y's?

As for aliasing, sounds like a good optimization, but how do I call that next? image_ix_iy[0] up to image_ix_iy[2]? oh and also what are image_ix and image_ix_iy? unsigned shorts?

Oh and yeah I did allocate my image data the way you said. making it in one chunk sounds like a good idea when it comes to making sure the data's aligned, however instead of calling image[iy][ix][ic] I'd do one multiplication in the iy loop (no big deal), but i'd mostly do one multiplication by 3 and one addition, plus then 3 additions, all of that in each ix loop iteration, wouldn't there be a performance hit?