Hello,
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++)
  {
                if(_getpixel(Current,x,y)!=_getpixel(Checking,x,y))
    {
      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:

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?

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;
}

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 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;

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

   return c;
})

getpixel is a bit more involved, but reads

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...

[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

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

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:

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

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.

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.

http://www.allegro.cc/manual/api/drawing-primitives/_getpixel

I did, and it was very useful

That's not the official manual though.

Indeed, looks like a bug in the a.cc manual.

The official documentation is at http://alleg.sf.net - simply type "getpixel" into the search box.

I wonder what happened to Matthew's plans to move the official documentation for 4.3 to allegro.cc, 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.

Neil:

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.

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.

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