Thursday, April 23, 2009

there should be an OLE function to drag and drop colors.

so when configuring something, just drag a color from anywhere - another application that you're trying to make it look like, a color picker, a theme palette on the web, whatever.
efficient hashtable

i've never seen a hashtable implementation, but i don't see how it could be more efficient than what i've come up with. according to the chart at http://burtleburtle.net/bob/hash/doobs.html , the 'generalized' crc algorithm has by far the best uniformity, and is one of the faster ones on the list (depending on how long your keys are, i guess). most, almost all, of those functions like to have table sizes in powers of two. so here's the algorithm, in unoptimized quasi-psuedo-code:
def init(orig_size): # must be power of two!
table_size = orig_size
table = malloc(table_size*whatever)
current_hash_bitmask = table_size-1

def add_key(key, value):
if table_size < (num_keys+1)*2:
double_table_size()
_add_key(table, hash_function(key), key, value)
num_keys++

def del_key(key):
_del_key(key)
num_keys--
if table_size/2 > num_keys:
halve_table()

def double_table():
table_size *= 2
current_hash_bitmask = table_size-1
new_table = malloc(table_size)
for 32_bit_hash, key, value in table:
_add_key(new_table, 32_bit_hash & current_hash_bitmask, key, value)
table = new_table

def halve_table():
table_size /= 2
current_hash_bitmask = table_size-1
new_table = malloc(table_size)
for 32_bit_hash, key, value in table:
_add_key(new_table, 32_bit_hash & current_hash_bitmask, key, value)
table = new_table

def _add_key(table, 32_bit_hash, key, value);
insert 32_bit_hash, key and value into the linked list at
table[32_bit_hash & current_hash_bitmask]

def del_key(key):
should be obvious

def get_key(key):
should be obvious


---

i started making a very efficient asm version of this, but i haven't finished because i don't have a memory allocation function yet, and i'm really tired right now, so i'll put something up later. here's what i have so far:

gencrctab:
dd 0x46d1e192, 0x66edf9aa, 0x927fc9e5, 0xa53baacc, 0x29b47658, 0x5a411a01
dd 0x0e66d5bd, 0x0dd5b1db, 0xcb38340e, 0x04d4ebb6, 0x98bc4f54, 0x36f20f2c
dd 0x4a3047ed, 0x1ec1e0eb, 0x568c0c1f, 0x6a731432, 0x81367fc6, 0xe3e25237
dd 0xe7f64884, 0x0fa59f64, 0x4f3109de, 0xf02d61f5, 0x5daec03b, 0x7f740e83
dd 0x056ff2d8, 0x2026cc0a, 0x7ac2112d, 0x82c55605, 0xb0911ef2, 0xa7b88e4c
dd 0x89dca282, 0x4b254d27, 0x7694a6d3, 0xd229eadd, 0x8e8f3738, 0x5bee7a55
dd 0x012eb6ab, 0x08dd28c8, 0xb5abc274, 0xbc7931f0, 0xf2396ed5, 0xe4e43d97
dd 0x943f4b7f, 0x85d0293d, 0xaed83a88, 0xc8f932fc, 0xc5496f20, 0xe9228173
dd 0x9b465b7d, 0xfda26680, 0x1ddeab35, 0x0c4f25cb, 0x86e32faf, 0xe59fa13a
dd 0xe192e2c4, 0xf147da1a, 0x67620a8d, 0x5c9a24c5, 0xfe6afde2, 0xacad0250
dd 0xd359730b, 0xf35203b3, 0x96a4b44d, 0xfbcacea6, 0x41a165ec, 0xd71e53ac
dd 0x835f39bf, 0x6b6bde7e, 0xd07085ba, 0x79064e07, 0xee5b20c3, 0x3b90bd65
dd 0x5827aef4, 0x4d12d31c, 0x9143496e, 0x6c485976, 0xd9552733, 0x220f6895
dd 0xe69def19, 0xeb89cd70, 0xc9bb9644, 0x93ec7e0d, 0x2ace3842, 0x2b6158da
dd 0x039e9178, 0xbb5367d7, 0x55682285, 0x4315d891, 0x19fd8906, 0x7d8d4448
dd 0xb4168a03, 0x40b56a53, 0xaa3e69e0, 0xa25182fe, 0xad34d16c, 0x720c4171
dd 0x9dc3b961, 0x321db563, 0x8b801b9e, 0xf5971893, 0x14cc1251, 0x8f4ae962
dd 0xf65aff1e, 0x13bd9dee, 0x5e7c78c7, 0xddb61731, 0x73832c15, 0xefebdd5b
dd 0x1f959aca, 0xe801fb22, 0xa89826ce, 0x30b7165d, 0x458a4077, 0x24fec52a
dd 0x849b065f, 0x3c6930cd, 0xa199a81d, 0xdb768f30, 0x2e45c64a, 0xff2f0d94
dd 0x4ea97917, 0x6f572acf, 0x653a195c, 0x17a88c5a, 0x27e11fb5, 0x3f09c4c1
dd 0x2f87e71b, 0xea1493e4, 0xd4b3a55e, 0xbe6090be, 0xaf6cd9d9, 0xda58ca00
dd 0x612b7034, 0x31711dad, 0x6d7db041, 0x8ca786b7, 0x09e8bf7a, 0xc3c4d7ea
dd 0xa3cd77a8, 0x7700f608, 0xdf3de559, 0x71c9353f, 0x9fd236fb, 0x1675d43e
dd 0x390d9e9a, 0x21ba4c6b, 0xbd1371e8, 0x90338440, 0xd5f163d2, 0xb140fef9
dd 0x52f50b57, 0x3710cf67, 0x4c11a79c, 0xc6d6624e, 0x3dc7afa9, 0x34a69969
dd 0x70544a26, 0xf7d9ec98, 0x7c027496, 0x1bfb3ba3, 0xb3b1dc8f, 0x9a241039
dd 0xf993f5a4, 0x15786b99, 0x26e704f7, 0x51503c04, 0x028bb3b8, 0xede5600c
dd 0x9cb22b29, 0xb6ff339b, 0x7e771c43, 0xc71c05f1, 0x604ca924, 0x695eed60
dd 0x688ed0bc, 0x3e0b232f, 0xf8a39c11, 0xbae6e67c, 0xb8cf75e1, 0x970321a7
dd 0x5328922b, 0xdef3df2e, 0x8d0443b0, 0x2885e3ae, 0x6435eed1, 0xcc375e81
dd 0xa98495f6, 0xe0bff114, 0xb2da3e4f, 0xc01b5adf, 0x507e0721, 0x6267a36a
dd 0x181a6df8, 0x7baff0c0, 0xfa6d6c13, 0x427250b2, 0xe2f742d6, 0xcd5cc723
dd 0x2d218be7, 0xb91fbbb1, 0x9eb946d0, 0x1c180810, 0xfc81d602, 0x0b9c3f52
dd 0xc2ea456f, 0x1165b2c9, 0xabf4ad75, 0x0a56fc8c, 0x12e0f818, 0xcadbcba1
dd 0x2586be56, 0x952c9b46, 0x07c6a43c, 0x78967df3, 0x477b2e49, 0x2c5d7b6d
dd 0x8a637272, 0x59acbcb4, 0x74a0e447, 0xc1f8800f, 0x35c015dc, 0x230794c2
dd 0x4405f328, 0xec2adba5, 0xd832b845, 0x6e4ed287, 0x48e9f7a2, 0xa44be89f
dd 0x38cbb725, 0xbf6ef4e6, 0xdc0e83fa, 0x54238d12, 0xf4f0c1e3, 0xa60857fd
dd 0xc43c64b9, 0x00c851ef, 0x33d75f36, 0x5fd39866, 0xd1efa08a, 0xa0640089
dd 0x877a978b, 0x99175d86, 0x57dfacbb, 0xceb02de9, 0xcf4d5c09, 0x3a8813d4
dd 0xb7448816, 0x63fa5568, 0x06be014b, 0xd642fa7b, 0x10aa7c90, 0x8082c88e
dd 0x1afcba79, 0x7519549d, 0x490a87ff, 0x8820c3a0

gencrc :
pop edi ; string object
mov ecx, [edi] ; str len
add edi, 4 ; start of str
pop eax ; hash function
gencrcloop:
mov ebx, eax
shr ebx, 8
xor al, [edi+ecx-1]
mov eax, [eax+gencrctab]
xor eax, ebx
loop gencrcloop

tablesize:
pop ecx ; number of entries
bsr ebx, ecx ; bsr == expensive
mov eax, 4
shl eax, ebx ; this should be the smallest power of 2 that's at least twice eax.
ret

addkey:
pop eax ; table object
pop edi ; string object
pop ebx ; value
mov ecx, [eax+4] ; number of keys
mov edx, [eax] ; table size
inc ecx
Efficient Malloc

So say you have some flat memory space and you're making a memory manager for it. It's not involved in page tables. This is something in the same vein as the "buddy block" system, only better.

Have an array of doubly-linked lists, the indexes to the array being steps of minimum amounts of memory to allocate. For example, the first linked list pointed to could be for chunks of at least 4 bytes, the second could be for chunks of at least 8, the third for chunks of at least 16, etc. Perhaps after a certain point we would stop doubling it, though, for example, 1024, 2048, 3072, 4096.., although we may still increase our granularity at certain points (while still making it possible to, via a formula, look directly to the right index without a search).

Each linked list is a linked list of available chunks of memory of a size in between its minimum size and the next-highest minimum size in the array. The end of the linked list simply runs off to the beginning of the next linked list, so that if all memory is taken for that chunk size then it automatically resorts to the next higher chunk size.

Of course, when a chunk is allocated it's removed from the linked list. When the chunk is freed it's inserted into the linked list. We can keep a hashtable of memory locations that remembers their sizes and locations of their list elements, or we can just return a memory object that contains more than just a pointer to the free memory.

Now, here's the method for consolidating otherwise adjacent blocks of free memory: when memory is freed, the addresses just before the beginning and just after the end of the chunk can be looked up in the hashtable. If the hashtable says that the memory chunk whose last byte is pointed to by the former is a free one, then the one we've just freed is conjoined with it (the exact location of the linked list item for the other block being stored within the hashtable value), and the same goes for if the memory chunk whose first memory location is pointed to by the latter is recorded as being free. Obviously we update the hashtable whenever we conjoin or split up some free memory, with both the chunk's first and last memory locations.

Oh, I forgot to mention: there is never any searching of these linked lists, because you always pop an item from the beginning of one to allocate a chunk, and insert one somewhere (for example, at the beginning of the appropriate linked list) to free one. (Obviously collisions can and will occur within the hashtable, but that only requires searching 2 or 3 elements now and then, by comparing ints.)

Tuesday, April 21, 2009

'Nother sort idea: Hash Sort

so if a hash function can distribute keys uniformly in slot space, then all we have to do is make a hash function that distributes uniformly and guarantees that the slots are in alphabetical order, then we can iterate over the slots and do compares for the ones with multiple entries in one slot. a hash function to distribute alphabetically for strings would be something like: num_slots*s[0]/256 + num_slots*s[1]/512 + num_slots*s[2]/1024 etc. of course this doesn't work very well if your strings actually have some sort of pattern to them, like for example they're readable. :p

since it's probably impossible to guarantee uniformity this way, you may want to use an n*n hash table. or perhaps an n*n*n. etc.

i guess you could say this algorithm is approximately O(n*log_256 k) where k is average element length in bytes? assuming you're not using unicode..