flat assembler
Message board for the users of flat assembler.

Index > Main > Bitmap count distinct pixel color

Author
Thread Post new topic Reply to topic
Abruzzi



Joined: 30 Sep 2019
Posts: 16
Abruzzi
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?
Post 28 Oct 2019, 10:53
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17074
Location: In your JS exploiting you and your system
revolution
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.
Post 28 Oct 2019, 11:18
View user's profile Send private message Visit poster's website Reply with quote
Abruzzi



Joined: 30 Sep 2019
Posts: 16
Abruzzi
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.
Post 28 Oct 2019, 13:36
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17074
Location: In your JS exploiting you and your system
revolution
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    
Post 28 Oct 2019, 13:42
View user's profile Send private message Visit poster's website Reply with quote
Abruzzi



Joined: 30 Sep 2019
Posts: 16
Abruzzi
Thank you, typo error.
Post 28 Oct 2019, 13:48
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17074
Location: In your JS exploiting you and your system
revolution
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).
Post 28 Oct 2019, 16:18
View user's profile Send private message Visit poster's website Reply with quote
Abruzzi



Joined: 30 Sep 2019
Posts: 16
Abruzzi
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.
Post 28 Oct 2019, 17:15
View user's profile Send private message Reply with quote
Abruzzi



Joined: 30 Sep 2019
Posts: 16
Abruzzi
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        
Post 28 Oct 2019, 17:55
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17074
Location: In your JS exploiting you and your system
revolution
How are you allocating the buffer?

Also, I think using "and eax,0xffffff" instead of "xor eax,0xff000000" would be safer.
Post 29 Oct 2019, 00:36
View user's profile Send private message Visit poster's website Reply with quote
Abruzzi



Joined: 30 Sep 2019
Posts: 16
Abruzzi
It works if I use
Code:
and eax, 0xFFFFFF    
instead of
Code:
xor eax, 0xFF000000    
Why?
Post 29 Oct 2019, 08:23
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17074
Location: In your JS exploiting you and your system
revolution
I guess you have some pixels with the alpha not equal to 0xff.
Post 29 Oct 2019, 08:39
View user's profile Send private message Visit poster's website Reply with quote
Abruzzi



Joined: 30 Sep 2019
Posts: 16
Abruzzi
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.
Post 29 Oct 2019, 09:04
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17074
Location: In your JS exploiting you and your system
revolution
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    
Post 29 Oct 2019, 09:17
View user's profile Send private message Visit poster's website Reply with quote
Abruzzi



Joined: 30 Sep 2019
Posts: 16
Abruzzi
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
Post 29 Oct 2019, 09:56
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17074
Location: In your JS exploiting you and your system
revolution
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
;...    
Post 29 Oct 2019, 10:09
View user's profile Send private message Visit poster's website Reply with quote
Abruzzi



Joined: 30 Sep 2019
Posts: 16
Abruzzi
Yes, I just figured out how stupid I am with such a loop condition. Thank you for support.
Post 29 Oct 2019, 10:12
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< 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


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.