ejecta color hash generator

gistfile1.c

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

typedef union {
	unsigned int hex;
	struct {
		unsigned char r, g, b, a;
	} rgba;
	unsigned char components[4];
} EJColorRGBA;

typedef struct {
	EJColorRGBA color;
	char *name;
	size_t length;
} CSSColor;

static CSSColor ColorNames[] = {
	{{0xff000000}, "invaid"},
	{{0xfffff8f0}, "aliceblue"},
	{{0xffd7ebfa}, "antiquewhite"},
	{{0xffffff00}, "aqua"},
	{{0xffd4ff7f}, "aquamarine"},
	{{0xfffffff0}, "azure"},
	{{0xffdcf5f5}, "beige"},
	{{0xffc4e4ff}, "bisque"},
	{{0xff000000}, "black"},
	{{0xffcdebff}, "blanchedalmond"},
	{{0xffff0000}, "blue"},
	{{0xffe22b8a}, "blueviolet"},
	{{0xff2a2aa5}, "brown"},
	{{0xff87b8de}, "burlywood"},
	{{0xffa09e5f}, "cadetblue"},
	{{0xff00ff7f}, "chartreuse"},
	{{0xff1e69d2}, "chocolate"},
	{{0xff507fff}, "coral"},
	{{0xffed9564}, "cornflowerblue"},
	{{0xffdcf8ff}, "cornsilk"},
	{{0xff3c14dc}, "crimson"},
	{{0xffffff00}, "cyan"},
	{{0xff8b0000}, "darkblue"},
	{{0xff8b8b00}, "darkcyan"},
	{{0xff0b86b8}, "darkgoldenrod"},
	{{0xffa9a9a9}, "darkgray"},
	{{0xffa9a9a9}, "darkgrey"},
	{{0xff006400}, "darkgreen"},
	{{0xff6bb7bd}, "darkkhaki"},
	{{0xff8b008b}, "darkmagenta"},
	{{0xff2f6b55}, "darkolivegreen"},
	{{0xff008cff}, "darkorange"},
	{{0xffcc3299}, "darkorchid"},
	{{0xff00008b}, "darkred"},
	{{0xff7a96e9}, "darksalmon"},
	{{0xff8fbc8f}, "darkseagreen"},
	{{0xff8b3d48}, "darkslateblue"},
	{{0xff4f4f2f}, "darkslategray"},
	{{0xff4f4f2f}, "darkslategrey"},
	{{0xffd1ce00}, "darkturquoise"},
	{{0xffd30094}, "darkviolet"},
	{{0xff9314ff}, "deeppink"},
	{{0xffffbf00}, "deepskyblue"},
	{{0xff696969}, "dimgray"},
	{{0xff696969}, "dimgrey"},
	{{0xffff901e}, "dodgerblue"},
	{{0xff2222b2}, "firebrick"},
	{{0xfff0faff}, "floralwhite"},
	{{0xff228b22}, "forestgreen"},
	{{0xffff00ff}, "fuchsia"},
	{{0xffdcdcdc}, "gainsboro"},
	{{0xfffff8f8}, "ghostwhite"},
	{{0xff00d7ff}, "gold"},
	{{0xff20a5da}, "goldenrod"},
	{{0xff808080}, "gray"},
	{{0xff808080}, "grey"},
	{{0xff008000}, "green"},
	{{0xff2fffad}, "greenyellow"},
	{{0xfff0fff0}, "honeydew"},
	{{0xffb469ff}, "hotpink"},
	{{0xff5c5ccd}, "indianred"},
	{{0xff82004b}, "indigo"},
	{{0xfff0ffff}, "ivory"},
	{{0xff8ce6f0}, "khaki"},
	{{0xfffae6e6}, "lavender"},
	{{0xfff5f0ff}, "lavenderblush"},
	{{0xff00fc7c}, "lawngreen"},
	{{0xffcdfaff}, "lemonchiffon"},
	{{0xffe6d8ad}, "lightblue"},
	{{0xff8080f0}, "lightcoral"},
	{{0xffffffe0}, "lightcyan"},
	{{0xffd2fafa}, "lightgoldenrodyellow"},
	{{0xffd3d3d3}, "lightgray"},
	{{0xffd3d3d3}, "lightgrey"},
	{{0xff90ee90}, "lightgreen"},
	{{0xffc1b6ff}, "lightpink"},
	{{0xff7aa0ff}, "lightsalmon"},
	{{0xffaab220}, "lightseagreen"},
	{{0xffface87}, "lightskyblue"},
	{{0xff998877}, "lightslategray"},
	{{0xff998877}, "lightslategrey"},
	{{0xffdec4b0}, "lightsteelblue"},
	{{0xffe0ffff}, "lightyellow"},
	{{0xff00ff00}, "lime"},
	{{0xff32cd32}, "limegreen"},
	{{0xffe6f0fa}, "linen"},
	{{0xffff00ff}, "magenta"},
	{{0xff000080}, "maroon"},
	{{0xffaacd66}, "mediumaquamarine"},
	{{0xffcd0000}, "mediumblue"},
	{{0xffd355ba}, "mediumorchid"},
	{{0xffd87093}, "mediumpurple"},
	{{0xff71b33c}, "mediumseagreen"},
	{{0xffee687b}, "mediumslateblue"},
	{{0xff9afa00}, "mediumspringgreen"},
	{{0xffccd148}, "mediumturquoise"},
	{{0xff8515c7}, "mediumvioletred"},
	{{0xff701919}, "midnightblue"},
	{{0xfffafff5}, "mintcream"},
	{{0xffe1e4ff}, "mistyrose"},
	{{0xffb5e4ff}, "moccasin"},
	{{0xffaddeff}, "navajowhite"},
	{{0xff800000}, "navy"},
	{{0xffe6f5fd}, "oldlace"},
	{{0xff008080}, "olive"},
	{{0xff238e6b}, "olivedrab"},
	{{0xff00a5ff}, "orange"},
	{{0xff0045ff}, "orangered"},
	{{0xffd670da}, "orchid"},
	{{0xffaae8ee}, "palegoldenrod"},
	{{0xff98fb98}, "palegreen"},
	{{0xffeeeeaf}, "paleturquoise"},
	{{0xff9370d8}, "palevioletred"},
	{{0xffd5efff}, "papayawhip"},
	{{0xffb9daff}, "peachpuff"},
	{{0xff3f85cd}, "peru"},
	{{0xffcbc0ff}, "pink"},
	{{0xffdda0dd}, "plum"},
	{{0xffe6e0b0}, "powderblue"},
	{{0xff800080}, "purple"},
	{{0xff0000ff}, "red"},
	{{0xff8f8fbc}, "rosybrown"},
	{{0xffe16941}, "royalblue"},
	{{0xff13458b}, "saddlebrown"},
	{{0xff7280fa}, "salmon"},
	{{0xff60a4f4}, "sandybrown"},
	{{0xff578b2e}, "seagreen"},
	{{0xffeef5ff}, "seashell"},
	{{0xff2d52a0}, "sienna"},
	{{0xffc0c0c0}, "silver"},
	{{0xffebce87}, "skyblue"},
	{{0xffcd5a6a}, "slateblue"},
	{{0xff908070}, "slategray"},
	{{0xff908070}, "slategrey"},
	{{0xfffafaff}, "snow"},
	{{0xff7fff00}, "springgreen"},
	{{0xffb48246}, "steelblue"},
	{{0xff8cb4d2}, "tan"},
	{{0xff808000}, "teal"},
	{{0xffd8bfd8}, "thistle"},
	{{0xff4763ff}, "tomato"},
	{{0xffd0e040}, "turquoise"},
	{{0xffee82ee}, "violet"},
	{{0xffb3def5}, "wheat"},
	{{0xffffffff}, "white"},
	{{0xfff5f5f5}, "whitesmoke"},
	{{0xff00ffff}, "yellow"},
	{{0xff32cd9a}, "yellowgreen"},
	{{0x00000000}, "transparent"}
};

const int numColors = sizeof(ColorNames)/sizeof(CSSColor);


#define HASH_TABLE_SIZE 1000
bool collisions[HASH_TABLE_SIZE];

static inline unsigned int ColorHashForString( const char *s, size_t length, int a, int b, int hashSize ) {
	unsigned int h = 0;
	for( size_t i = 0; i < length; i++ ) {
		h = (h << a) ^ h ^ (s[i] * b);
	}
	return (h % hashSize);
};

void printHash(int a, int b, int hashSize) {
	unsigned char *ColorHashesToColorNames = malloc(hashSize);
	memset(ColorHashesToColorNames, 0, hashSize);
	
	for( int i = 0; i < numColors; i++ ) {
		int hash = ColorHashForString(ColorNames[i].name, ColorNames[i].length, a, b, hashSize);
		ColorHashesToColorNames[hash] = i;
	}
	
	printf("Found: a:%d b:%d, size:%d\n", a, b, hashSize);
	printf(
		"static inline unsigned int ColorHashForString( const JSChar *s, size_t length ) {\n"
		"	unsigned int h = 0;\n"
		"	for( size_t i = 0; i < length; i++ ) {\n"
		"		h = (h << %d) ^ h ^ (tolower(s[i]) * %d);\n"
		"	}\n"
		"	return (h %% %d);\n"
		"};\n\n",
		a, b, hashSize
	);
	printf("static const unsigned char ColorHashesToColorNames[%d] = {\n", hashSize);
	
	for( int i = 0; i < hashSize; i++ ) {
		printf("%d,", ColorHashesToColorNames[i]);
		if( i % 50 == 50) {
			printf("\n");
		}
	}
	
	printf("};\n\n");
	free(ColorHashesToColorNames);
}

int main(int argc, const char * argv[]) {
	
	// Initialize string lengths
	for( int i = 0; i < numColors; i++ ) {
		ColorNames[i].length = strlen(ColorNames[i].name);
	}

	int smallestHash = HASH_TABLE_SIZE;
	while( true ) {
		int b = (rand()*rand())^(rand()*rand());
		int hashSize;
		for( int a = 1; a < 31; a++ ) {	
			for( hashSize = numColors; hashSize < smallestHash; hashSize++ ) {
				memset(collisions, 0, hashSize);
				bool hadCollision = false;

				for( int i = 0; i < numColors; i++ ) {
					int hash = ColorHashForString(ColorNames[i].name, ColorNames[i].length, a, b, hashSize);
					if( collisions[hash] ) {
						hadCollision = true;
						break;
					}
					collisions[hash] = true;
				}

				if( !hadCollision ) {
					// No collision? Print the hash function and hash table
					printHash(a, b, hashSize);
					smallestHash = hashSize;
					break;
				}
			}
		}
	}

	return 0;
}