error in _getpixel?
Neil Walker

I have a program that loops through a bitmap and extracts smaller bitmaps, e.g. 16x16 pixels - it's a tile extraction program. It then adds these to a list, but first checks the bitmap doesn't already exist in the list. The code to check if the bitmaps are the same (they are always the same depth) is :

bool IsBitmapSame(BITMAP* Checking,BITMAP* Current)
for(int y=0;y<Current->h;y++)
  for(int x=0;x<Current->w;x++)
      return false;
return true;

For an average bitmap which would have a few hundred tiled bitmaps within it works 99% of the time, however on certain extracted bitmaps it is returning a match on the very first bitmap in the list despite the bitmaps being completely different. If I change either of the above _getpixel to getpixel it works a treat, so it appears _getpixel is doing something when _getpixel is ran twice in succession? This was tested only on windows.

From analysis (well, somebody elses) it seems to be getting it wrong for bitmaps where oly the last 3 pixels on a line differ. Though this could be a red herring., but it's definitely something to do with the bitmap data.

Attached is a bitmap showing it. It is a cut down portion of a larger map. As you can see the version using getpixel finds all three tiles, but the version running _getpixel seems to match the first half of the circle with the first all blue tile. The larger image below shows a flag made up of 4 white parts, the bottom left tile is actually just 1 white pixel, but this is also skipped and the tile becomes the first all blue one again - hence why the comment above regarding the 3 pixels.

Tracing the code through for the two bitmaps passed in, for the ones that fail, it seems to be getting the same colour back for both images, despite their being different!

The code below is a snippet showing how the two bitmaps are generated:

1std::vector<BITMAP*> BitmapList; //array of unique bitmaps
2std::vector<BITMAP*>::const_iterator BitmapListIterator;
5BITMAP* Current=NULL;
6BITMAP* Checking=NULL;
7int same=false;
8int Unique,duplicate=0;
9int innercount=0;
10int outercount=0;
12//loop all rows in the bitmap
13//calcheight is the size of the large bitmap, currenttilesize is the tile size
14in pixels, e.g. 16
16for(int y=0;y<CalcHeight/CurrentTileSize;y++)
18 //loop through all the bitmaps from start to end
19 //loop all columns in each row
20 for(int x=0;x<CalcWidth/CurrentTileSize;x++)
21 {
22 Current=create_bitmap(CurrentTileSize,CurrentTileSize);
23 //loop through what we've got - blit to a temp bitmap
24just to make it easy
25 //loadedfile is the big bitmap we are mapping
29 innercount=0;
30 same=false;
32 //check if the bitmap has already been stored
36 {
37 //loop through all bitmaps from start upto the
38current outer loop
39 same=IsBitmapSame(*BitmapListIterator,Current);
40 if(same)
41 break;
43 innercount++;
44 }
45 //tile does not exist, add it
46 if(!same)
47 {
48 BitmapList.push_back(Current);
49 Unique++;
50 }
51 else
52 duplicate++;
54 }


According to the documentation, getpixel_ is for 8-bit bitmaps only, so my guess would be, not all your bitmaps are 8 bit. Is there any reason you want to use getpixel_ instead of getpixel?

Neil Walker

I thought _getpixel was a wrapper that called _getpixel8, _getpixel16, _getpixel32?

On testing, _getpixel was about 30% faster than get pixel.


No, there is no _getpixel8 from what I see, and the only difference to getpixel would be that it's missing the color depth and clipping checks.

If you need fast bitmap comparison, something like this might work, since memcmp is quite likely optimized by the compiler a lot (works for memory bitmaps only though):

bool is_same(BITMAP *b1, BITMAP *b2)
    if (not is_memory_bitmap(b1) or not is_memory_bitmap(b2)) return false;
    int d1 = bitmap_color_depth(b1);
    int d2 = bitmap_color_depth(b2);
    if (d1 != d2) return false;
    int len1 = b1->w * b1->h * ((d1 + 7) / 8);
    int len2 = b2->w * b2->h * ((d2 + 7) / 8);
    if (len1 != len2) return false;
    if (memcmp(b1->dat, b2->dat, len1)) return false;
    return true;

Neil Walker

I'll try it now, keep listening ;)

btw, I've just tried it again but altered the code so that instead of creating a new bitmap to check against the existing ones, it passes in the large bitmap with the startx/y instead. Doing this using _getpixel returns all bitmaps being the same as the first tile, but using getpixel works again. So there is definitely something wrong with _getpixel.

[edit]On testing an image with 22000 8x8 pixel tiles it took 45 seconds using getpixel, 35 using _getpixel and 40 using your new code.

I know we're digressing from the original problem, but I think the bottleneck is the way I create a new bitmap for comparison every time, so instead I use the above approach using the large bitmap passing in offsets, however I had to use getpixel because as mentioned _getpixel doesn't work so it took 45 seconds as well.

Could your code be improved by using a checksum perchance?


I've just tried it again but altered the code so that instead of creating a new bitmap to check against the existing ones, it passes in the large bitmap with the startx/y instead. Doing this using _getpixel returns all bitmaps being the same as the first tile, but using getpixel works again.

I don't have a clue what that means. Can you illustrate what you're trying to do with some example code?

Anyway, this is the implementation of _getpixel:

AL_INLINE(int, _getpixel, (BITMAP *bmp, int x, int y),
   uintptr_t addr;
   int c;

   addr = bmp_read_line(bmp, y);
   c = bmp_read8(addr+x);

   return c;

getpixel is a bit more involved, but reads

1/* _linear_getpixel:
2 * Reads a pixel from a linear bitmap.
3 */
4int FUNC_LINEAR_GETPIXEL(BITMAP *src, int sx, int sy)
6 ASSERT(src);
8 if ((sx < 0) || (sx >= src->w) || (sy < 0) || (sy >= src->h))
9 return -1;
10 else {
11 PIXEL_PTR s = OFFSET_PIXEL_PTR(bmp_read_line(src, sy), sx);
12 unsigned long c;
14 bmp_select(src);
15 c = GET_PIXEL(s);
16 bmp_unwrite_line(src);
18 return c;
19 }

where, for 8 bit bitmaps,

#define GET_PIXEL(p)           bmp_read8((uintptr_t) (p))
#define OFFSET_PIXEL_PTR(p,x)  ((PIXEL_PTR) (p) + (x))

So it looks pretty much the same to me...

Neil Walker

[EDIT]Ok, I've just taken in what elias said and evert mentioned. I was just blind to it, and I blame the fecking allegro file naming system ;)

I thought, like all other bpp specific functions, e.g. getcolor, _getpixel would call the relevant one, e.g. _getpixel16, _getpixel32, etc. I guess this goes back to 1986 when allegro was only 8bpp. Bring on allegro 4.3 :)


I don't have a clue what that means. Can you illustrate what you're trying to do with some example code?

Sure. I modified my check program to be as follows:

1bool IsBitmapSame2(BITMAP* Checking,BITMAP* source,int sourcex, int sourcey)
3 int p1, p2;
5 for(int y=0;y<Checking->h;y++)
6 {
7 for(int x=0;x<Checking->w;x++)
8 {
9 p1=getpixel(Checking,x,y);
10 p2=getpixel(source,x+sourcex,y+sourcey);
11 if(p1!=p2)
12 {
13 return false;
14 }
15 }
16 }
18 //the same
19 return true;

Using the example of the graphics mentioned: Checking is a 8x8 bitmap created by blitting a portion of 'source', i.e. we have a list of 8x8 unique bitmaps taken as tiles from 'source' and passing in new locations within 'source' using the sourcex/sourcey. The code above works fine and correctly identifies unique/duplicates. If I change getpixel to _getpixel it thinks it is a match for the first bitmap in the list,

The code for this is:

1for(int y=0;y<CalcHeight/CurrentTileSize;y++)
3 //loop all columns in each row
4 //CurrentTileSize is 8 in our case, and CalcWidth/CalcHeight is the size of loadedfile
5 for(int x=0;x<CalcWidth/CurrentTileSize;x++)
6 {
7 same=false;
9 for(BitmapListIterator=BitmapList.begin();BitmapListIterator!=BitmapList.end();BitmapListIterator++)
10 {
11 same=IsBitmapSame2(*BitmapListIterator,loadedfile,x*CurrentTileSize+ProgramDetails.xoffset,y*CurrentTileSize+ProgramDetails.yoffset);
12 if(same)
13 break;
14 }
15 //tile does not exist, add it
16 if(!same)
17 {
18 Current=create_bitmap(CurrentTileSize,CurrentTileSize);
19 //loop through what we've got - blit to a temp bitmap just to make it easy
20 blit(loadedfile,Current,x*CurrentTileSize+ProgramDetails.xoffset,y*CurrentTileSize+ProgramDetails.yoffset,0,0,CurrentTileSize,CurrentTileSize);
22 BitmapList.push_back(Current);
23 Unique++;
24 }
25 else
26 {
27 duplicate++;
28 }
30 }


Ok, I've just taken in what elias said and evert mentioned. I was just blind to it

Ok, so I take it that if you call the one for the proper colour depth, it does work properly?


I thought, like all other bpp specific functions, e.g. getcolor, _getpixel would call the relevant one

Morale: if a function returns unexpected results, re-read TFM first. ;)

I agree that it would be more consistent to rename _getpixel to _getpixel8 and alias _getpixel to _getpixel8 though.

Neil Walker

Thanks all, this bug is now fixed. I also modified my code with some optimisations mentioned here and elsewhere by friends, on a map that used to take 5 minutes (90,000 tiles, 420 unique bitmaps) to process it now takes about 30 seconds. I also added an option to bypass creation of single bitmaps per tile (there is a sheet file option) and it knocks this down further to 3 seconds :)

I'll post an update later, if anyone's interested.


re-read TFM first.

I did, and it was very useful ;)


That's not the official manual though. ;)


Indeed, looks like a bug in the manual.

The official documentation is at - simply type "getpixel" into the search box.

I wonder what happened to Matthew's plans to move the official documentation for 4.3 to, and also make it user editable. Guess it's not the best route after all, and we'll have to discuss how to handle 4.3 documentation again at some point..


I personally don't see a problem with keeping the documentation bundled with Allegro, as it is now. I think that's a good thing, actually.

Richard Phipps


Would it help if you did something like this?

bool IsBitmapSame(BITMAP* Checking,BITMAP* Current)
  for(int y=0;y<Current->h;y++)
    for(int x=0;x<Current->w;x += 4)
     if ( ((long *)checking->line[y])[x] != ((long *)current->line[y])[x] ) return false;

  return true;

This would have to use memory bitmaps that have a width multiple of 4, but it would check 4 8-bit pixels at once.

Neil Walker

Rich, thanks. I've now tried all the permutations of speeding up the pixel check and what actually comes out best is to check the depth and use _getpixel, _getpixel16, _getpixel32. The reason why it is faster is that for the above optimised bitmap<>bitmap test requires two bitmaps, however creating each one from the large bitmap for comparison is time consuming and so what I now do in code is check the existing tile list of bitmaps with an area of the large map and only create bitmaps when they are unique.

As mentioned above, this took Dan Dare down to 3 seconds from 5 minutes.

I've also added two more features that I'll upload tonight.

1. Different sized width/height for tiles, e.g. 32x24. It's also useful for generating screens, e.g. 256x192. Mario world1-1 looks rather splendid ;)

2. Added ability to generate the sheet file as a power of 2, this, apparently will make it work properly with OpenGL.

Richard Phipps

Well, if you can use the above code, but checking directly against the tile list of bitmaps then that should be pretty fast.

Thread #587886. Printed from