SRL Archive - Development

Currently finding colors with CTS 2/CTS 3 is quite CPU-intensive. It translates every colour to another colorspace (HSL/XYZ) and then applies some fancy color-comparing algorithm.

What if we would cache the color compares of colors that are being searched a lot? This would be implemented by a buffer that stores the value for the compare of your color (with CTS X and Tol Y) with every other possible colour. (It only has to store 1 for "does compare" and 0 for "does not compare").
Such a buffer would be quite big in size: 256^3 bits (All the possible RGB combinations) which is around ~2mb. So for every colour+tol+cts we want to cache it will roughly cost 2mb of RAM. Which is not a shitload amount, but it still requires the scripter to think which color would benefit.

The only question is whether this actually speeds-up the colorfinding process. I can imagine that some CPUs are faster calculating the value than waiting on the memory, but then again the current CPUs probably have a cache big enough.

I would assume that finding such a colour in the cache would require binary searches and insertion sort or else having to search a very large buffer would take longer than just running the algorithm no?

Unless I misunderstand.

From: mastaraymond
Currently finding colors with CTS 2/CTS 3 is quite CPU-intensive. It translates every colour to another colorspace (HSL/XYZ) and then applies some fancy color-comparing algorithm.

What if we would cache the color compares of colors that are being searched a lot? This would be implemented by a buffer that stores the value for the compare of your color (with CTS X and Tol Y) with every other possible colour. (It only has to store 1 for "does compare" and 0 for "does not compare").
Such a buffer would be quite big in size: 256^3 bits (All the possible RGB combinations) which is around ~2mb. So for every colour+tol+cts we want to cache it will roughly cost 2mb of RAM. Which is not a shitload amount, but it still requires the scripter to think which color would benefit.

The only question is whether this actually speeds-up the colorfinding process. I can imagine that some CPUs are faster calculating the value than waiting on the memory, but then again the current CPUs probably have a cache big enough.

Confused me a bit here, are we talking about RAM to cache it or CPU cache? Because you mentioned that it would cost around 2MB RAM at first and later you said that "CPUs probably have a cache big enough".

I assume you meant RAM but I don't know that much about this sort of stuff. I think that 90% of the desktop PCs have atleast 4mb L3 cache & 4gb RAM nowadays.

I'm not sure if this would speed the searching up as it is extremely fast already as far as I have experienced. But it's worth a shot if it's worth the effort.

From: Brandon
I would assume that finding such a colour in the cache would require binary searches and insertion sort or else having to search a very large buffer would take longer than just running the algorithm no?

Unless I misunderstand.

Yes, it would indeed require a buffer of exactly 256^3 bits, which is around ~2mb. So if you pick colors selective it must nog be a bit issue.

Pseudo-code would look something like this

procedure setbit(ptr : pointer; index : integer; value : boolean)
var
  b,bb : integer;
  pbyte : PByte;
begin
  b := index / 8; //The byte in which the index lies
  bb := index mod 8; //The index of the bit inside the byte
  pbyte := (ptr + b);
  if (value)
    pbyte^ := pbyte^ or (1 shl bb);
  else
    pbyte^ := pbyte^ and not (1 shl bb); 
end;

function readbit(ptr : pointer; index : integer) : boolean;
var
  b,bb : integer;
  pbyte : PByte;
begin
  b := index / 8; //The byte in which the index lies
  bb := index mod 8; //The index of the bit inside the byte
  pbyte := (ptr + b);
  result := not ((pbyte^ and (1 shl bb)) == 0)
end;
//Result points to a buffer of size 256^3 bits, thus 256^3/8 bytes
function create_similar_buffer(color, cts, tol :integer) : Pointer;
var
  i : integer;
begin;
  result := calloc(256*256*256/8); //set data to 0
  for i := 0 to 256*256*256 - 1 do
    setbit(ptr,i,colorsame(color, i, cts, tol));
end;

//And then in findcolorstolerancebuffer
..
..
for x := 0 to width
  for y := 0 to height
     if (readbit(similar_buffer, ScreenCol[x][y], cts, tol))
       AddToTPA(result,x,y);

From: J J
Confused me a bit here, are we talking about RAM to cache it or CPU cache? Because you mentioned that it would cost around 2MB RAM at first and later you said that "CPUs probably have a cache big enough".

I assume you meant RAM but I don't know that much about this sort of stuff. I think that 90% of the desktop PCs have atleast 4mb L3 cache & 4gb RAM nowadays.

I'm not sure if this would speed the searching up as it is extremely fast already as far as I have experienced. But it's worth a shot if it's worth the effort.

We are talking about storing the similar_color cache in RAM. Yes, CPUs have a cache on their own whichto data from the RAM is copied. Sometimes calculating the value inside the CPU is faster than the CPU waiting on the data being copied from the RAM. (But as seeing probably the whole buffer fits into the CPU-cache that might nog be such a big problem).

I think it will be faster for CS3 since the algorithm is more complex than CS2(which is simple). Will write a simple explanation for your idea so everyone can follow ^^.

At this moment when you search for a color on the screen, with either CTS2 or CTS3, simba will go through every pixel on the screen and convert the color to the right color space, hsl/cieLab. So instead of red, green and blue you can now compare light/dark, hue and sat or the cie values. Let's say you search on an area of 200 by 200 pixels, it will have to convert 40000 pixels to the right color space. This takes massive amounts of cpu power and this is the main reason why CTS2 is slower then for example CTS1 or CTS0.

Raymond his idea was to stop converting every pixel on the screen to the new color space, but instead create a list of every color and the difference with your color. This list can then be stored in a buffer. This buffer is basically a Boolean array where the index is the color. So buffer[myColor] will be true or false. When you now search for a color which you created a buffer for you can pick the color out of the list and see how much the difference is, and if it is less the tolerance.

Possible implementation, note that raymond suggest a faster version of this in simba itself, not in the script.

function CreateBuffer(color, ctsMethod, tol:Integer): BooleanArray;
begin
  SetColorToleranceSpeed(ctsMethod);
  SetLength(Result, 16777216);
  
  for i := 0 to 16777215 do
    Result[i] := CompareColor(color, i, tol);
end;

var
  b: BooleanArray;
  myColor, tol: Integer;

begin
  myColor := 348290;
  tol := 10;
  b := CreateBuffer(myColor, 2, tol);

  if(findColorsBuffer(myColor, x1, y1, x2, y2)) then
   doStuff;
end;

A big con is that you will have to create a buffer for every color with every tolerance you want to search for.

A big pro is that the speed will probably go up since you can just create the buffers at the start of the script, no more conversions to other color spaces while the script is running.

Even better would be pre-calculating hash-table with pointers to next slot. Eliminates binary searches.

For example,

// The lookup table.
int hash[32487834];

int GetValue(int *pValue)
{
    int p = hash[256 + *pValue++];
    
    p = hash[p + *pValue++];

    return hash[p + *pValue++];
}

However, the algorithm to create the hash-table is a bit complex. The basic idea is to use prime-numbers in each step, to get unique value in iteration.

From: superuser
Even better would be pre-calculating hash-table with pointers to next slot. Eliminates binary searches.

For example,

// The lookup table.
int hash[32487834];

int GetValue(int *pValue)
{
    int p = hash[256 + *pValue++];
    
    p = hash[p + *pValue++];

    return hash[p + *pValue++];
}

However, the algorithm to create the hash-table is a bit complex. The basic idea is to use prime-numbers in each step, to get unique value in iteration.

Uh, what? We already have a clear indexer the color.

From: mastaraymond
Uh, what? We already have a clear indexer the color.

Uhh one problem with the psuedo code and the code suggested by BB is:

for i := 0 to 16777215 do
   //...........

That will take FOREVER!! Especially in pascal. The below already takes long:

var
  I, J: Integer;
begin
  for i := 0 to 16777215 do
    J := J + 1;
end.

How do you plan on fixing such a thing? I don't think anyone would wait 1-2 minutes for a buffer to be made or colour comparison? :l

From: Brandon
Uhh one problem with the psuedo code and the code suggested by BB is:

for i := 0 to 16777215 do
   //...........

That will take FOREVER!! The below already takes long:

var
  I, J: Integer;
begin
  for i := 0 to 16777215 do
    J := J + 1;
end.

How do you plan on fixing such a thing? I don't think anyone would wait 1-2 minutes for a buffer to be made or colour comparison? :l

Running it inside a binary shouldn't take that long, but I might be mistaken.

From: mastaraymond
Running it inside a binary shouldn't take that long, but I might be mistaken.

Oops lol I ran it in Simba :l In a dll, it finished immediately.

From: Brandon
Oops lol I ran it in Simba :l In a dll, it finished immediately.

Made a sample code in C (calculates the HSL values for all the colours).

#include <sys/time.h>
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#define MAX 256*256*256

float min(float a, float b) {
	if (a < b)
		return a;
	else
		return b;
}

float max(float a, float b) {
	if (a > b)
		return a;
	else
		return b;
}
float H_comp = 0.5;
float S_comp = 0.5;
float L_comp = 0.5; 
void rgb_to_hsl( unsigned char *ptr, int index, unsigned char R, unsigned char G, unsigned char B) {
	float var_R = ((float) R / 255.0 );                     //RGB from 0 to 255
	float var_G = ((float) G / 255.0 );
	float var_B = ((float) B / 255.0 );

	float var_Min = min(min( var_R, var_G) , var_B );    //Min. value of RGB
	float var_Max = max(max( var_R, var_G), var_B );    //Max. value of RGB
	float del_Max = var_Max - var_Min ;            //Delta RGB value
	float del_R;
	float del_G;
	float del_B;
	float L = ( var_Max + var_Min ) / 2;
	float H;
	float S;

	if ( del_Max == 0 )                     //This is a gray, no chroma...
	{
		 H = 0      ;                          //HSL results from 0 to 1
		 S = 0;
	}
	else                                    //Chromatic data...
	{
		 if ( L < 0.5 ) S = del_Max / ( var_Max + var_Min );
		 else           S = del_Max / ( 2 - var_Max - var_Min );

		 del_R = ( ( ( var_Max - var_R ) / 6 ) + ( del_Max / 2 ) ) / del_Max;
		 del_G = ( ( ( var_Max - var_G ) / 6 ) + ( del_Max / 2 ) ) / del_Max;
		 del_B = ( ( ( var_Max - var_B ) / 6 ) + ( del_Max / 2 ) ) / del_Max;

		 if      ( var_R == var_Max ) H = del_B - del_G;
		 else if ( var_G == var_Max ) H = ( 1 / 3 ) + del_R - del_B;
		 else if ( var_B == var_Max ) H = ( 2 / 3 ) + del_G - del_R;

		 if ( H < 0 ) H += 1;
		 if ( H > 1 ) H -= 1;
	}
	if ((H-H_comp < 0.1) && (S-S_comp < 0.1) && (L-L_comp < 0.1))  //Do something
	  ptr[index/8] = 1;
	else
	  ptr[index/8] = 0;
}
int main()
{
    struct timeval start, end;

    long mtime, seconds, useconds;    
    int i;
    unsigned char *ptr; 
    gettimeofday(&start, NULL);
    ptr = malloc(MAX/8);
    for (i =0; i < MAX; i++) {
    	rgb_to_hsl(ptr,i, *((char *) &i), *((char *) &i + 1), *((char *) &i + 2));
    }
    gettimeofday(&end, NULL);

    seconds  = end.tv_sec  - start.tv_sec;
    useconds = end.tv_usec - start.tv_usec;

    mtime = ((seconds) * 1000 + useconds/1000.0) + 0.5;

    printf("Elapsed time: %ld milliseconds\n", mtime);

    return 0;
}

Elapsed time: 739 milliseconds, so it takes about 1 second to create a buffer. Not that much, right?

From: mastaraymond
Elapsed time: 739 milliseconds, so it takes about 1 minute to create a buffer. Not that much, right?

Wat? You said 739 ms, so 0.8 seconds, not 1 minute :p Or am I missing something.

From: masterBB
Wat? You said 739 ms, so 0.8 seconds, not 1 minute :p Or am I missing something.

Woops, typo. Fixd now.