This is a routine to find the closest match for a colour in an array of colours. It has been taken from ImageShop32 written by Eberhard Funck which you can find in the APPS section of this web site.
When I discover the name of the algorithm and the name of the guy that invented it I'll let you know.
#include <windows.h>
#include <stdio.h>
#include <intrinsics.h>
long ColorMatch_c(int * lpColor, int r, int g, int b, int nColor)
{
//-----------------------------------------------------------------------
// Returns the nearest match from an array of colours. lpColors points
// to the start of array of DWORDs, nColors are number of array elements.
// The nearest color is returned when mindist (MinDistance) = 0 or
// mindist has arrived at its minimum by ending the loop
//-----------------------------------------------------------------------
int bestcolor = 0;
int curdist = 0;
int mindist = 200000;
LPRGBQUAD pRGBQ;
int rr, gg, bb;
for (int i = 0; (i < nColor) && mindist; i++)
{
pRGBQ = (LPRGBQUAD)((LPBYTE)lpColor + 4 *
i);
rr = pRGBQ->rgbRed - r;
gg = pRGBQ->rgbGreen - g;
bb = pRGBQ->rgbBlue - b;
curdist = (rr*rr) + (gg*gg) + (bb*bb);
if (curdist < mindist)
{
mindist =
curdist;
bestcolor = i;
}
}
return (bestcolor);
}
int __declspec(naked) ColorMatch_asm(int * lpCol, int r, int g, int b, int
nColors)
{
//-----------------------------------------------------------------------
// Returns the nearest match from an array of colours. lpColors points
// to the start of array of DWORDs, nColors are number of array elements.
// The nearest color is returned when mindist (MinDistance) = 0 or
// mindist has arrived at its minimum by ending the loop
//-----------------------------------------------------------------------
_asm("pushl %ebp");
// save
_asm("movl %esp,%ebp"); // copy stack pointer to
%ebp
_asm("pushl %edi");
// save these regs
_asm("pushl %esi");
_asm("pushl %ebx");
_asm("xorl %edi,%edi"); // clear it (our counter)
_asm("movl $200000,%ecx"); // mindist = 200000
_asm("movl 8(%ebp),%esi"); // address of array
_asm(".start:");
_asm("cmpl 24(%ebp),%edi") // while i < nColor
_asm("je .done");
// jump if done
_asm("jecxz .done");
// while mindist <> 0
_asm("xorl %eax,%eax");
_asm("movb 2(%esi,%edi,4),%al");
_asm("subl 12(%ebp),%eax"); // subtract r
_asm("imul %eax,%eax"); // signed multiply
_asm("movl %eax,%ebx"); // save value
_asm("xorl %eax,%eax");
_asm("movb 1(%esi,%edi,4),%al");
_asm("subl 16(%ebp),%eax"); // g
_asm("imul %eax,%eax");
_asm("addl %eax,%ebx");
// add to value
_asm("xorl %eax,%eax");
_asm("movb 0(%esi,%edi,4),%al");
_asm("subl 20(%ebp),%eax"); // b
_asm("imul %eax,%eax");
_asm("addl %eax,%ebx");
_asm("cmpl %ecx,%ebx");
// curdist < mindist
_asm("jb .set");
// jump if below CF=1
_asm("addl $1,%edi");
// next loop
_asm("jmp .start");
_asm(".set:");
_asm("movl %ebx,%ecx");
// mindist = curdist
_asm("movl %edi,%edx");
// bestcolor) = i(%edi)
_asm("addl $1,%edi");
// next loop
_asm("jmp .start");
_asm(".done:");
_asm("movl %edx, %eax"); // return
(edx to eax)
_asm("popl %ebx");
// restore regs
_asm("popl %esi");
_asm("popl %edi");
_asm("popl %ebp");
_asm("ret");
// return with value in eax
}
int main(void)
{
#define NUM 256
long long t2,t1,t0;
int c, i, arr[NUM];
for (i = 0; i<NUM; i++)
arr[i] = RGB(i,i,i);
// put in a few colours
int r = 121, g = 33, b = 28; // colour to try and match
t2 = 0;
for(i=0; i<NUM; i++){
t0 = _rdtsc();
c = ColorMatch_c(arr, r, g, b, NUM);
t1 = _rdtsc();
t2 += t1 - t0;
}
xprintf("cycles C %lld\t%d\n", t2/i, c);
t2 = 0;
for(i=0; i<NUM; i++){
t0 = _rdtsc();
c = ColorMatch_asm(arr, r, g, b, NUM);
t1 = _rdtsc();
t2 += t1 - t0;
}
xprintf("cycles asm %lld\t%d\n", t2/i, c);
return 0;
}