Bitmap count distinct pixel color

Index > Main > Bitmap count distinct pixel color

Author

Thread

Abruzzi

Joined: 30 Sep 2019
Posts: 17

Abruzzi 28 Oct 2019, 10:53

I want to count all distinct pixels in a bitmap and I have something in my mind but I am a little bit confuse how to do it efficiently since I am quite new to assembly.

Let's say I have buffer that contains the colors of a bitmap with 6 pixels in format AARRGGBB
FF808080 FF808080 FF00FF00 FF808080 FF0000FF FF00FF00

and what I try to achieve is to count distinct colors like below
FF808080 3
FF0000FF 1
FF00FF00 2

Here is what I have in my mind but I am not sure it's the proper way to do it.

ESI = address of the buffer that contains the pixels color (4 bytes for each pixel)
EDI = address of the buffer that will contain the results in format [Color][Number of pixels][Color][Number of pixels] .... (8 Bytes for each identified color - 4 bytes pixel color - 4 bytes pixel count of that color)
ECX = 6 (Number of pixels in buffer)
EDX = 0 (Number of current distinct colors identified)

So I thought to loop through all pixels and for each pixel to make a second loop to check if the current pixel color has been already found before and just to increase the counter for that color otherwise to add a new color. This is how I visualize the algorithm:

Loop through all pixels this means 6 steps

Code:

Step#1
ESI: FF808080 FF808080 FF00FF00 FF808080 FF0000FF FF00FF00
EDI: FF808080        1
ECX: 5
EDX: 1

Step#2
ESI: FF808080 FF808080 FF00FF00 FF808080 FF0000FF FF00FF00
EDI: FF808080        2
ECX: 4
EDX: 1

Step#3
ESI: FF808080 FF808080 FF00FF00 FF808080 FF0000FF FF00FF00
EDI: FF808080        2 FF00FF00        1
ECX: 3
EDX: 2

Step#4
ESI: FF808080 FF808080 FF00FF00 FF808080 FF0000FF FF00FF00
EDI: FF808080        3 FF00FF00        1
ECX: 2
EDX: 2

Step#5
ESI: FF808080 FF808080 FF00FF00 FF808080 FF0000FF FF00FF00
EDI: FF808080        3 FF00FF00        1 FF0000FF        1
ECX: 1
EDX: 3

Step#6
ESI: FF808080 FF808080 FF00FF00 FF808080 FF0000FF FF00FF00
EDI: FF808080        3 FF00FF00        2 FF0000FF        1
ECX: 0
EDX: 3

Is there a better way to approach this task?

28 Oct 2019, 10:53

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20451
Location: In your JS exploiting you and your system

revolution 28 Oct 2019, 11:18

I don't know if it is better, but I would be very tempted to do a sort on all the pixels first, and then count the repetitions on a second pass.

Something like quicksort is O(n log n) on average.

28 Oct 2019, 11:18

Abruzzi

Joined: 30 Sep 2019
Posts: 17

Abruzzi 28 Oct 2019, 13:36

With your approach will be also easier to output a sorted array based on number of pixels for each color but it's a little bit hard for me to implement such an algorithm since I am new to this.

This is what I have so far:

Code:

use32
mov esi, dword[esp + 4]
mov edi, dword[esp + 8]
mov ecx, dword[esp + 12]

xor edx, edx

_NextPixel:

cmp ecx, 0
je _Exit

lodsd

cmp edx, 0
je _AddColor

mov ebx, 0
_NextColor:

cmp eax, [edi + ebx * 8]
je _UpdateCounter

add ebx, 1
cmp ebx, edx
jle _NextColor

jmp _AddColor

_UpdateCounter:
mov eax, 1
add [edi + ebx * 8 + 4], eax
sub ecx, 1
jmp _NextPixel

_AddColor:
mov [edi + edx * 8], eax
mov eax, 1
mov [edi + ebx * 8 + 4], eax
add edx, 1
sub ecx, 1
jmp _NextPixel

_Exit:
ret 12

I try yo figure out what's wrong and then to improve the code. This are parameters passed

Code:

ECX: 6
ESI: 0000FFFF 00FF00FF 0000FFFF 00FF00FF 0000FFFF FF0000FF
EDI: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

and this is what I get after

Code:

EDI: 0000FFFF 03000000 00FF00FF 01000000 FF0000FF 01000000 00000000 01000000 00000000 00000000 00000000 00000000

For some reason one pixel color is counted wrong and I have some trash in the result also.

28 Oct 2019, 13:36

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20451
Location: In your JS exploiting you and your system

revolution 28 Oct 2019, 13:42

I guess your problem is due to a wrong register name:

Code:

_AddColor:
mov [edi + edx * 8], eax
mov eax, 1
mov [edi + ebx * 8 + 4], eax ;<===== Use EDX here, not EBX
add edx, 1
sub ecx, 1

28 Oct 2019, 13:42

Abruzzi

Joined: 30 Sep 2019
Posts: 17

Abruzzi 28 Oct 2019, 13:48

Thank you, typo error.

28 Oct 2019, 13:48

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20451
Location: In your JS exploiting you and your system

revolution 28 Oct 2019, 16:18

If all your alpha values are 0xff then you could instead create a 64MB buffer of 2^24 dwords and directly index into it for incrementing.

If you want to do that for all possible 32-bit pixel values then the array might be too large at 16GB (4G colours x 4 bytes).

28 Oct 2019, 16:18

Abruzzi

Joined: 30 Sep 2019
Posts: 17

Abruzzi 28 Oct 2019, 17:15

I don't especially need the alpha channel. I made a test with a bitmap with size 2044x892 and I am not impressed by my algorithm. At this size I need a 1823248 bytes for bitmap data and 3646496 for result buffer just in case all pixel colors are different. And it's very slow for every new pixel to loop through entire result buffer to verify if a specific pixel color is already there. In this case it takes 60 seconds, so I am a little bit disappointed.

Maybe it's faster as you said, to pass as a 64 MB result buffer for any possible color in RRGGBB format and loop through bitmap data just one time and update specific dwords in result buffer.

28 Oct 2019, 17:15

Abruzzi

Joined: 30 Sep 2019
Posts: 17

Abruzzi 28 Oct 2019, 17:55

Now I have a result buffer with size 67,108,860 bytes and tried something like this but I get an access violation error (C0000005) at line add [edi + eax * 4], edx

Code:

use32
mov esi, dword[esp + 4]
mov edi, dword[esp + 8]
mov ecx, dword[esp + 12]
mov edx, 1
_NextPixel:
lodsd
xor eax, 0xFF000000    ; strip alpha channel
add [edi + eax * 4], edx
sub ecx, 1
cmp ecx, 0
jge _NextPixel
ret 12

28 Oct 2019, 17:55

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20451
Location: In your JS exploiting you and your system

revolution 29 Oct 2019, 00:36

How are you allocating the buffer?

Also, I think using "and eax,0xffffff" instead of "xor eax,0xff000000" would be safer.

29 Oct 2019, 00:36

Abruzzi

Joined: 30 Sep 2019
Posts: 17

Abruzzi 29 Oct 2019, 08:23

It works if I use

Code:

and eax, 0xFFFFFF

instead of

Code:

xor eax, 0xFF000000

Why?

29 Oct 2019, 08:23

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20451
Location: In your JS exploiting you and your system

revolution 29 Oct 2019, 08:39

I guess you have some pixels with the alpha not equal to 0xff.

29 Oct 2019, 08:39

Abruzzi

Joined: 30 Sep 2019
Posts: 17

Abruzzi 29 Oct 2019, 09:04

It's strange, because I shouldn't have other apha channel values. Let me explain how I process the bitmaps. I use a high level language and GDI+ to load the image and prepare the buffers passed to my FASM function. The original bitmap is without alpha (24 bpp) and after I create the bitmap from file I use LockBits with PixelFormat32bppARGB format to access the bitmap pixels data. So this is the step where my bitmap start to have alpha channel and everything should be 0xFF. Actually I made a test with a smaller image and print out the content to make sure there is no other alpha channel value and still doesn't work if I use xor instead and. It's strange but I am glad it works now.

29 Oct 2019, 09:04

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20451
Location: In your JS exploiting you and your system

revolution 29 Oct 2019, 09:17

Put in some code like this to test it:

Code:

;...
xor eax,0xff000000
  cmp eax,0x00ffffff
  ja .alpha_error
inc dword [edi + eax * 4]
;...
.alpha_error:
  int3 ;create a fault here and see if the debugger triggers

29 Oct 2019, 09:17

Abruzzi

Joined: 30 Sep 2019
Posts: 17

Abruzzi 29 Oct 2019, 09:56

Well now I am really confused. Indeed now when I call it's clear for me that at some point a jump to .alpha_error is made since at return I have in eax the value 75148.

Code:

use32
mov esi, dword[esp + 4]
mov edi, dword[esp + 8]
mov ecx, dword[esp + 12]

_NextPixel:
lodsd
xor eax,0xff000000
cmp eax,0x00ffffff
ja .alpha_error
inc dword [edi + eax * 4]
sub ecx, 1
cmp ecx, 0
jge _NextPixel
jmp _Exit

.alpha_error:
mov eax, 75148

_Exit:
ret 12

My test picture is a 4x4 bitmap so in ESI I have the start address to a buffer with data like below

Code:

ESI: 0000FFFF 00FF00FF 0000FFFF 00F2FFFF 00FF00FF 0000FFFF FF0000FF 00F2FFFF 00F2FFFF 00F2FFFF 00F2FFFF 000000FF 00F2FFFF 00F2FFFF 00F2FFFF 000000FF
       RED     GREEN     BLUE    YELLOW   GREEN     RED      BLUE    YELLOW   YELLOW   YELLOW   YELLOW    BLACK   YELLOW   YELLOW   YELLOW    BLACK

As you can see all alpha channels are 0xFF, I really don't understand what happens there. I will replace lodsd with mov eax, [esi] to see if this has something to do.

EDIT: I think I got the problem, since I start with ECX = 16 and my condition and my loop condition is jge my loop will have 17 iterations not just 16 so in the last step some trash will be read in eax and for sure don't have alpha channel 0xFF.

Thank you for your help revolution.

Last edited by Abruzzi on 29 Oct 2019, 10:11; edited 1 time in total

29 Oct 2019, 09:56

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20451
Location: In your JS exploiting you and your system

revolution 29 Oct 2019, 10:09

Okay, I see that you are using JGE instead of JNE for your loop count, but I assume ECX is the pizel_count and not pizel_count-1. Try this:

Code:

;...
inc dword [edi + eax * 4]
dec ecx ;or sub ecx,1 if you want
jne _NextPixel
;...

29 Oct 2019, 10:09

Abruzzi

Joined: 30 Sep 2019
Posts: 17

Abruzzi 29 Oct 2019, 10:12

Yes, I just figured out how stupid I am with such a loop condition. Thank you for support.

29 Oct 2019, 10:12

< Last Thread | Next Thread >

Forum Rules:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum