Work on "did you mean? <ident>" support for errors. Using a three-part Bayes Theorem...
[xonotic/gmqcc.git] / util.c
1 /*
2  * Copyright (C) 2012, 2013
3  *     Dale Weiler
4  *     Wolfgang Bumiller
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a copy of
7  * this software and associated documentation files (the "Software"), to deal in
8  * the Software without restriction, including without limitation the rights to
9  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
10  * of the Software, and to permit persons to whom the Software is furnished to do
11  * so, subject to the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be included in all
14  * copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22  * SOFTWARE.
23  */
24 #include <stdarg.h>
25 #include <errno.h>
26 #include "gmqcc.h"
27
28 /* TODO: remove globals ... */
29 uint64_t mem_ab = 0;
30 uint64_t mem_db = 0;
31 uint64_t mem_at = 0;
32 uint64_t mem_dt = 0;
33
34 struct memblock_t {
35     const char  *file;
36     unsigned int line;
37     size_t       byte;
38     struct memblock_t *next;
39     struct memblock_t *prev;
40 };
41
42 static struct memblock_t *mem_start = NULL;
43
44 void *util_memory_a(size_t byte, unsigned int line, const char *file) {
45     struct memblock_t *info = (struct memblock_t*)malloc(sizeof(struct memblock_t) + byte);
46     void              *data = (void*)(info+1);
47     if (!info) return NULL;
48     info->line = line;
49     info->byte = byte;
50     info->file = file;
51     info->prev = NULL;
52     info->next = mem_start;
53     if (mem_start)
54         mem_start->prev = info;
55     mem_start = info;
56
57     #if 0
58     util_debug("MEM", "allocation:   % 8u (bytes) address 0x%08X @ %s:%u\n", byte, data, file, line);
59     #endif
60
61     mem_at++;
62     mem_ab += info->byte;
63
64     return data;
65 }
66
67 void util_memory_d(void *ptrn, unsigned int line, const char *file) {
68     struct memblock_t *info = NULL;
69
70     if (!ptrn) return;
71     info = ((struct memblock_t*)ptrn - 1);
72
73     #if 0
74     util_debug("MEM", "released:     % 8u (bytes) address 0x%08X @ %s:%u\n", info->byte, ptrn, file, line);
75     #endif
76
77     mem_db += info->byte;
78     mem_dt++;
79
80     if (info->prev)
81         info->prev->next = info->next;
82     if (info->next)
83         info->next->prev = info->prev;
84     if (info == mem_start)
85         mem_start = info->next;
86
87     free(info);
88 }
89
90 void *util_memory_r(void *ptrn, size_t byte, unsigned int line, const char *file) {
91     struct memblock_t *oldinfo = NULL;
92
93     struct memblock_t *newinfo;
94
95     if (!ptrn)
96         return util_memory_a(byte, line, file);
97     if (!byte) {
98         util_memory_d(ptrn, line, file);
99         return NULL;
100     }
101
102     oldinfo = ((struct memblock_t*)ptrn - 1);
103     newinfo = ((struct memblock_t*)malloc(sizeof(struct memblock_t) + byte));
104
105     #if 0
106     util_debug("MEM", "reallocation: % 8u -> %u (bytes) address 0x%08X -> 0x%08X @ %s:%u\n", oldinfo->byte, byte, ptrn, (void*)(newinfo+1), file, line);
107     #endif
108
109     /* new data */
110     if (!newinfo) {
111         util_memory_d(oldinfo+1, line, file);
112         return NULL;
113     }
114
115     /* copy old */
116     memcpy(newinfo+1, oldinfo+1, oldinfo->byte);
117
118     /* free old */
119     if (oldinfo->prev)
120         oldinfo->prev->next = oldinfo->next;
121     if (oldinfo->next)
122         oldinfo->next->prev = oldinfo->prev;
123     if (oldinfo == mem_start)
124         mem_start = oldinfo->next;
125
126     /* fill info */
127     newinfo->line = line;
128     newinfo->byte = byte;
129     newinfo->file = file;
130     newinfo->prev = NULL;
131     newinfo->next = mem_start;
132     if (mem_start)
133         mem_start->prev = newinfo;
134     mem_start = newinfo;
135
136     mem_ab -= oldinfo->byte;
137     mem_ab += newinfo->byte;
138
139     free(oldinfo);
140
141     return newinfo+1;
142 }
143
144 void util_meminfo() {
145     struct memblock_t *info;
146
147     if (!opts.memchk)
148         return;
149
150     for (info = mem_start; info; info = info->next) {
151         util_debug("MEM", "lost:       % 8u (bytes) at %s:%u\n",
152             info->byte,
153             info->file,
154             info->line);
155     }
156
157     util_debug("MEM", "Memory information:\n\
158         Total allocations:   %llu\n\
159         Total deallocations: %llu\n\
160         Total allocated:     %llu (bytes)\n\
161         Total deallocated:   %llu (bytes)\n\
162         Leaks found:         lost %llu (bytes) in %d allocations\n",
163             mem_at,   mem_dt,
164             mem_ab,   mem_db,
165            (mem_ab -  mem_db),
166            (mem_at -  mem_dt)
167     );
168 }
169
170 /*
171  * Some string utility functions, because strdup uses malloc, and we want
172  * to track all memory (without replacing malloc).
173  */
174 char *util_strdup(const char *s) {
175     size_t  len = 0;
176     char   *ptr = NULL;
177
178     if (!s)
179         return NULL;
180
181     if ((len = strlen(s)) && (ptr = (char*)mem_a(len+1))) {
182         memcpy(ptr, s, len);
183         ptr[len] = '\0';
184     }
185     return ptr;
186 }
187
188 void util_debug(const char *area, const char *ms, ...) {
189     va_list  va;
190     if (!opts.debug)
191         return;
192
193     if (!strcmp(area, "MEM") && !opts.memchk)
194         return;
195
196     va_start(va, ms);
197     con_out ("[%s] ", area);
198     con_vout(ms, va);
199     va_end  (va);
200 }
201
202 /*
203  * only required if big endian .. otherwise no need to swap
204  * data.
205  */   
206 #if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_BIG
207     static GMQCC_INLINE void util_swap16(uint16_t *d, size_t l) {
208         while (l--) {
209             d[l] = (d[l] << 8) | (d[l] >> 8);
210         }
211     }
212
213     static GMQCC_INLINE void util_swap32(uint32_t *d, size_t l) {
214         while (l--) {
215             uint32_t v;
216             v = ((d[l] << 8) & 0xFF00FF00) | ((d[l] >> 8) & 0x00FF00FF);
217             d[l] = (v << 16) | (v >> 16);
218         }
219     }
220
221     /* Some strange system doesn't like constants that big, AND doesn't recognize an ULL suffix
222      * so let's go the safe way
223      */
224     static GMQCC_INLINE void util_swap64(uint32_t *d, size_t l) {
225         /*
226         while (l--) {
227             uint64_t v;
228             v = ((d[l] << 8) & 0xFF00FF00FF00FF00) | ((d[l] >> 8) & 0x00FF00FF00FF00FF);
229             v = ((v << 16) & 0xFFFF0000FFFF0000) | ((v >> 16) & 0x0000FFFF0000FFFF);
230             d[l] = (v << 32) | (v >> 32);
231         }
232         */
233         size_t i;
234         for (i = 0; i < l; i += 2) {
235             uint32_t v1 = d[i];
236             d[i] = d[i+1];
237             d[i+1] = v1;
238             util_swap32(d+i, 2);
239         }
240     }
241 #endif
242
243 void util_endianswap(void *_data, size_t length, unsigned int typesize) {
244 #   if PLATFORM_BYTE_ORDER == -1 /* runtime check */
245     if (*((char*)&typesize))
246         return;
247 #else
248     /* prevent unused warnings */
249     (void) _data;
250     (void) length;
251     (void) typesize;
252
253 #   if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_LITTLE
254         return;
255 #   else
256         switch (typesize) {
257             case 1: return;
258             case 2:
259                 util_swap16((uint16_t*)_data, length>>1);
260                 return;
261             case 4:
262                 util_swap32((uint32_t*)_data, length>>2);
263                 return;
264             case 8:
265                 util_swap64((uint32_t*)_data, length>>3);
266                 return;
267
268             default: abort(); /* please blow the fuck up! */
269         }
270 #   endif
271 #endif
272 }
273
274 /*
275  * CRC algorithms vary in the width of the polynomial, the value of said polynomial,
276  * the initial value used for the register, weather the bits of each byte are reflected
277  * before being processed, weather the algorithm itself feeds input bytes through the
278  * register or XORs them with a byte from one end and then straight into the table, as
279  * well as (but not limited to the idea of reflected versions) where the final register
280  * value becomes reversed, and finally weather the value itself is used to XOR the final
281  * register value.  AS such you can already imagine how painfully annoying CRCs are,
282  * of course we stand to target Quake, which expects it's certian set of rules for proper
283  * calculation of a CRC.
284  *
285  * In most traditional CRC algorithms on uses a reflected table driven method where a value
286  * or register is reflected if it's bits are swapped around it's center.  For example:
287  * take the bits 0101 is the 4-bit reflection of 1010, and respectfully 0011 would be the
288  * reflection of 1100. Quake however expects a NON-Reflected CRC on the output, but still
289  * requires a final XOR on the values (0xFFFF and 0x0000) this is a standard CCITT CRC-16
290  * which I respectfully as a programmer don't agree with.
291  *
292  * So now you know what we target, and why we target it, despite how unsettling it may seem
293  * but those are what Quake seems to request.
294  */
295
296 static const uint16_t util_crc16_table[] = {
297     0x0000,     0x1021,     0x2042,     0x3063,     0x4084,     0x50A5,
298     0x60C6,     0x70E7,     0x8108,     0x9129,     0xA14A,     0xB16B,
299     0xC18C,     0xD1AD,     0xE1CE,     0xF1EF,     0x1231,     0x0210,
300     0x3273,     0x2252,     0x52B5,     0x4294,     0x72F7,     0x62D6,
301     0x9339,     0x8318,     0xB37B,     0xA35A,     0xD3BD,     0xC39C,
302     0xF3FF,     0xE3DE,     0x2462,     0x3443,     0x0420,     0x1401,
303     0x64E6,     0x74C7,     0x44A4,     0x5485,     0xA56A,     0xB54B,
304     0x8528,     0x9509,     0xE5EE,     0xF5CF,     0xC5AC,     0xD58D,
305     0x3653,     0x2672,     0x1611,     0x0630,     0x76D7,     0x66F6,
306     0x5695,     0x46B4,     0xB75B,     0xA77A,     0x9719,     0x8738,
307     0xF7DF,     0xE7FE,     0xD79D,     0xC7BC,     0x48C4,     0x58E5,
308     0x6886,     0x78A7,     0x0840,     0x1861,     0x2802,     0x3823,
309     0xC9CC,     0xD9ED,     0xE98E,     0xF9AF,     0x8948,     0x9969,
310     0xA90A,     0xB92B,     0x5AF5,     0x4AD4,     0x7AB7,     0x6A96,
311     0x1A71,     0x0A50,     0x3A33,     0x2A12,     0xDBFD,     0xCBDC,
312     0xFBBF,     0xEB9E,     0x9B79,     0x8B58,     0xBB3B,     0xAB1A,
313     0x6CA6,     0x7C87,     0x4CE4,     0x5CC5,     0x2C22,     0x3C03,
314     0x0C60,     0x1C41,     0xEDAE,     0xFD8F,     0xCDEC,     0xDDCD,
315     0xAD2A,     0xBD0B,     0x8D68,     0x9D49,     0x7E97,     0x6EB6,
316     0x5ED5,     0x4EF4,     0x3E13,     0x2E32,     0x1E51,     0x0E70,
317     0xFF9F,     0xEFBE,     0xDFDD,     0xCFFC,     0xBF1B,     0xAF3A,
318     0x9F59,     0x8F78,     0x9188,     0x81A9,     0xB1CA,     0xA1EB,
319     0xD10C,     0xC12D,     0xF14E,     0xE16F,     0x1080,     0x00A1,
320     0x30C2,     0x20E3,     0x5004,     0x4025,     0x7046,     0x6067,
321     0x83B9,     0x9398,     0xA3FB,     0xB3DA,     0xC33D,     0xD31C,
322     0xE37F,     0xF35E,     0x02B1,     0x1290,     0x22F3,     0x32D2,
323     0x4235,     0x5214,     0x6277,     0x7256,     0xB5EA,     0xA5CB,
324     0x95A8,     0x8589,     0xF56E,     0xE54F,     0xD52C,     0xC50D,
325     0x34E2,     0x24C3,     0x14A0,     0x0481,     0x7466,     0x6447,
326     0x5424,     0x4405,     0xA7DB,     0xB7FA,     0x8799,     0x97B8,
327     0xE75F,     0xF77E,     0xC71D,     0xD73C,     0x26D3,     0x36F2,
328     0x0691,     0x16B0,     0x6657,     0x7676,     0x4615,     0x5634,
329     0xD94C,     0xC96D,     0xF90E,     0xE92F,     0x99C8,     0x89E9,
330     0xB98A,     0xA9AB,     0x5844,     0x4865,     0x7806,     0x6827,
331     0x18C0,     0x08E1,     0x3882,     0x28A3,     0xCB7D,     0xDB5C,
332     0xEB3F,     0xFB1E,     0x8BF9,     0x9BD8,     0xABBB,     0xBB9A,
333     0x4A75,     0x5A54,     0x6A37,     0x7A16,     0x0AF1,     0x1AD0,
334     0x2AB3,     0x3A92,     0xFD2E,     0xED0F,     0xDD6C,     0xCD4D,
335     0xBDAA,     0xAD8B,     0x9DE8,     0x8DC9,     0x7C26,     0x6C07,
336     0x5C64,     0x4C45,     0x3CA2,     0x2C83,     0x1CE0,     0x0CC1,
337     0xEF1F,     0xFF3E,     0xCF5D,     0xDF7C,     0xAF9B,     0xBFBA,
338     0x8FD9,     0x9FF8,     0x6E17,     0x7E36,     0x4E55,     0x5E74,
339     0x2E93,     0x3EB2,     0x0ED1,     0x1EF0
340 };
341
342 /* Non - Reflected */
343 uint16_t util_crc16(uint16_t current, const char *k, size_t len) {
344     register uint16_t h = current;
345     for (; len; --len, ++k) 
346         h = util_crc16_table[(h>>8)^((unsigned char)*k)]^(h<<8);
347     return h;
348 }
349 /* Reflective Varation (for reference) */
350 #if 0
351 uint16_t util_crc16(const char *k, int len, const short clamp) {
352     register uint16_t h= (uint16_t)0xFFFFFFFF;
353     for (; len; --len, ++k) 
354         h = util_crc16_table[(h^((unsigned char)*k))&0xFF]^(h>>8);
355     return (~h)%clamp; 
356 }
357 #endif
358
359 size_t util_strtocmd(const char *in, char *out, size_t outsz) {
360     size_t sz = 1;
361     for (; *in && sz < outsz; ++in, ++out, ++sz)
362         *out = (*in == '-') ? '_' : (isalpha(*in) && !isupper(*in)) ? *in + 'A' - 'a': *in;
363     *out = 0;
364     return sz-1;
365 }
366
367 size_t util_strtononcmd(const char *in, char *out, size_t outsz) {
368     size_t sz = 1;
369     for (; *in && sz < outsz; ++in, ++out, ++sz)
370         *out = (*in == '_') ? '-' : (isalpha(*in) && isupper(*in)) ? *in + 'a' - 'A' : *in;
371     *out = 0;
372     return sz-1;
373 }
374
375 /* TODO: rewrite ... when I redo the ve cleanup */
376 void _util_vec_grow(void **a, size_t i, size_t s) {
377     vector_t *d = vec_meta(*a);
378     size_t    m = *a ? 2 * d->allocated +i : i+1;
379     void     *p = mem_r((*a ? d : NULL), s * m + sizeof(vector_t));
380
381     if (!*a)
382         ((vector_t*)p)->used = 0;
383     *a = (vector_t*)p + 1;
384
385     vec_meta(*a)->allocated = m;
386 }
387
388 /*
389  * Hash table for generic data, based on dynamic memory allocations
390  * all around.  This is the internal interface, please look for
391  * EXPOSED INTERFACE comment below
392  */
393 typedef struct hash_node_t {
394     char               *key;   /* the key for this node in table */
395     void               *value; /* pointer to the data as void*   */
396     struct hash_node_t *next;  /* next node (linked list)        */
397 } hash_node_t;
398
399 GMQCC_INLINE size_t util_hthash(hash_table_t *ht, const char *key) {
400     const uint32_t       mix   = 0x5BD1E995;
401     const uint32_t       rot   = 24;
402     size_t               size  = strlen(key);
403     uint32_t             hash  = 0x1EF0 /* LICRC TAB */  ^ size;
404     uint32_t             alias = 0;
405     const unsigned char *data  = (const unsigned char*)key;
406
407     while (size >= 4) {
408         alias = *(uint32_t*)data;
409
410         alias *= mix;
411         alias ^= alias >> rot;
412         alias *= mix;
413
414         hash  *= mix;
415         hash  ^= alias;
416
417         data += 4;
418         size -= 4;
419     }
420
421     switch (size) {
422         case 3: hash ^= data[2] << 16;
423         case 2: hash ^= data[1] << 8;
424         case 1: hash ^= data[0];
425                 hash *= mix;
426     }
427
428     hash ^= hash >> 13;
429     hash *= mix;
430     hash ^= hash >> 15;
431
432     return (size_t) (hash % ht->size);
433 }
434
435 hash_node_t *_util_htnewpair(const char *key, void *value) {
436     hash_node_t *node;
437     if (!(node = (hash_node_t*)mem_a(sizeof(hash_node_t))))
438         return NULL;
439
440     if (!(node->key = util_strdup(key))) {
441         mem_d(node);
442         return NULL;
443     }
444
445     node->value = value;
446     node->next  = NULL;
447
448     return node;
449 }
450
451 /*
452  * EXPOSED INTERFACE for the hashtable implementation
453  * util_htnew(size)                             -- to make a new hashtable
454  * util_htset(table, key, value, sizeof(value)) -- to set something in the table
455  * util_htget(table, key)                       -- to get something from the table
456  * util_htdel(table)                            -- to delete the table
457  */
458 hash_table_t *util_htnew(size_t size) {
459     hash_table_t *hashtable = NULL;
460     if (size < 1)
461         return NULL;
462
463     if (!(hashtable = (hash_table_t*)mem_a(sizeof(hash_table_t))))
464         return NULL;
465
466     if (!(hashtable->table = (hash_node_t**)mem_a(sizeof(hash_node_t*) * size))) {
467         mem_d(hashtable);
468         return NULL;
469     }
470
471     hashtable->size = size;
472     memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
473
474     return hashtable;
475 }
476
477 void util_htseth(hash_table_t *ht, const char *key, size_t bin, void *value) {
478     hash_node_t *newnode = NULL;
479     hash_node_t *next    = NULL;
480     hash_node_t *last    = NULL;
481
482     next = ht->table[bin];
483
484     while (next && next->key && strcmp(key, next->key) > 0)
485         last = next, next = next->next;
486
487     /* already in table, do a replace */
488     if (next && next->key && strcmp(key, next->key) == 0) {
489         next->value = value;
490     } else {
491         /* not found, grow a pair man :P */
492         newnode = _util_htnewpair(key, value);
493         if (next == ht->table[bin]) {
494             newnode->next  = next;
495             ht->table[bin] = newnode;
496         } else if (!next) {
497             last->next = newnode;
498         } else {
499             newnode->next = next;
500             last->next = newnode;
501         }
502     }
503 }
504
505 void util_htset(hash_table_t *ht, const char *key, void *value) {
506     util_htseth(ht, key, util_hthash(ht, key), value);
507 }
508
509 void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
510     hash_node_t *pair = ht->table[bin];
511
512     while (pair && pair->key && strcmp(key, pair->key) > 0)
513         pair = pair->next;
514
515     if (!pair || !pair->key || strcmp(key, pair->key) != 0)
516         return NULL;
517
518     return pair->value;
519 }
520
521 void *util_htget(hash_table_t *ht, const char *key) {
522     return util_htgeth(ht, key, util_hthash(ht, key));
523 }
524
525 void *code_util_str_htgeth(hash_table_t *ht, const char *key, size_t bin) {
526     hash_node_t *pair;
527     size_t len, keylen;
528     int cmp;
529
530     keylen = strlen(key);
531
532     pair = ht->table[bin];
533     while (pair && pair->key) {
534         len = strlen(pair->key);
535         if (len < keylen) {
536             pair = pair->next;
537             continue;
538         }
539         if (keylen == len) {
540             cmp = strcmp(key, pair->key);
541             if (cmp == 0)
542                 return pair->value;
543             if (cmp < 0)
544                 return NULL;
545             pair = pair->next;
546             continue;
547         }
548         cmp = strcmp(key, pair->key + len - keylen);
549         if (cmp == 0) {
550             uintptr_t up = (uintptr_t)pair->value;
551             up += len - keylen;
552             return (void*)up;
553         }
554         pair = pair->next;
555     }
556     return NULL;
557 }
558
559 /*
560  * Free all allocated data in a hashtable, this is quite the amount
561  * of work.
562  */
563 void util_htdel(hash_table_t *ht) {
564     size_t i = 0;
565     for (; i < ht->size; i++) {
566         hash_node_t *n = ht->table[i];
567         hash_node_t *p;
568
569         /* free in list */
570         while (n) {
571             if (n->key)
572                 mem_d(n->key);
573             p = n;
574             n = n->next;
575             mem_d(p);
576         }
577
578     }
579     /* free table */
580     mem_d(ht->table);
581     mem_d(ht);
582 }
583
584 /*
585  * A basic implementation of a hash-set.  Unlike a hashtable, a hash
586  * set doesn't maintain key-value pairs.  It simply maintains a key
587  * that can be set, removed, and checked for.
588  *
589  * See EXPOSED interface comment below 
590  */
591 #define GMQCC_HASHSET_PRIME0 0x0049
592 #define GMQCC_HASHSET_PRIME1 0x1391
593
594 static int util_hsput(hash_set_t *set, void *item) {
595     size_t hash = (size_t)item; /* shouldn't drop the bits */
596     size_t iter;
597
598     /* a == 0 || a == 1 */
599     if (hash >> 1)
600         return -1;
601
602     iter = set->mask & (GMQCC_HASHSET_PRIME0 * hash);
603
604     /* while (set->items[iter] != 0 && set->items[iter] != 1) */
605     while  (!(set->items[iter] >> 1)) {
606         if (set->items[iter] == hash)
607             return 0;
608
609         iter = set->mask & (iter + GMQCC_HASHSET_PRIME1);
610     }
611
612     set->total ++;
613     set->items[iter] = hash;
614
615     return 1;
616 }
617
618 static void util_hsupdate(hash_set_t *set) {
619     size_t *old;
620     size_t  end;
621     size_t  itr;
622
623     /* time to rehash? */
624     if ((float)set->total >= (size_t)((double)set->capacity * 0.85)) {
625         old = set->items;
626         end = set->capacity;
627
628         set->bits ++;
629         set->capacity = (size_t)(1 << set->bits);
630         set->mask     = set->capacity - 1;
631         set->items    = mem_a(set->capacity * sizeof(size_t));
632         set->total    = 0;
633
634         /*assert(set->items);*/
635
636         /*
637          * this shouldn't be slow?  if so unroll it a little perhaps
638          * (shouldn't be though)
639          */
640         for (itr = 0; itr < end; itr++)
641             util_hsput(set, (void*)old[itr]);
642
643         mem_d(old);
644     }
645 }
646
647 /*
648  * EXPOSED interface: all of these functions are exposed to the outside
649  * for use. The stuff above is static because it's the "internal" mechanics
650  * for syncronizing the set for updating, and putting data into the set.
651  */   
652 int util_hsadd(hash_set_t *set, void *item) {
653     int run = util_hsput(set, item); /* inlined */
654     util_hsupdate(set);
655
656     return run;
657 }
658
659 /* remove item in set */
660 int util_hsrem(hash_set_t *set, void *item) {
661     size_t hash = (size_t)item;
662     size_t iter = set->mask & (GMQCC_HASHSET_PRIME0 * hash);
663
664     while  (set->items[iter]) {
665         if (set->items[iter] == hash) {
666             set->items[iter] =  1;
667             set->total       --;
668
669             return 1;
670         }
671         iter = set->mask & (iter + GMQCC_HASHSET_PRIME1);
672     }
673
674     return 0;
675 }
676
677 /* check if item is set */
678 int util_hshas(hash_set_t *set, void *item) {
679     size_t hash = (size_t)item;
680     size_t iter = set->mask & (GMQCC_HASHSET_PRIME0 * hash);
681
682     while  (set->items[iter]) {
683         if (set->items[iter] == hash)
684             return 1;
685
686         iter = set->mask & (iter + GMQCC_HASHSET_PRIME1);
687     }
688
689     return 0;
690 }
691
692 hash_set_t *util_hsnew(void) {
693     hash_set_t *set;
694
695     if (!(set = mem_a(sizeof(hash_set_t))))
696         return NULL;
697
698     set->bits     = 3;
699     set->total    = 0;
700     set->capacity = (size_t)(1 << set->bits);
701     set->mask     = set->capacity - 1;
702     set->items    = mem_a(set->capacity * sizeof(size_t));
703
704     if (!set->items) {
705         util_hsdel(set);
706         return NULL;
707     }
708
709     return set;
710 }
711
712 void util_hsdel(hash_set_t *set) {
713     if (!set) return;
714
715     if (set->items)
716         mem_d(set->items);
717
718     mem_d(set);
719 }
720 #undef GMQCC_HASHSET_PRIME0
721 #undef GMQCC_HASHSET_PRIME1
722
723
724 /*
725  * Portable implementation of vasprintf/asprintf. Assumes vsnprintf
726  * exists, otherwise compiler error.
727  *
728  * TODO: fix for MSVC ....  
729  */
730 int util_vasprintf(char **dat, const char *fmt, va_list args) {
731     int   ret;
732     int   len;
733     char *tmp = NULL;
734
735     /*
736      * For visuals tido _vsnprintf doesn't tell you the length of a
737      * formatted string if it overflows. However there is a MSVC
738      * intrinsic (which is documented wrong) called _vcsprintf which
739      * will return the required amount to allocate.
740      */     
741     #ifdef _MSC_VER
742         char *str;
743         if ((len = _vscprintf(fmt, args)) < 0) {
744             *dat = NULL;
745             return -1;
746         }
747
748         tmp = mem_a(len + 1);
749         if ((ret = _vsnprintf(tmp, len+1, fmt, args)) != len) {
750             mem_d(tmp);
751             *dat = NULL;
752             return -1;
753         }
754         *dat = tmp;
755         return len;
756     #else
757         /*
758          * For everything else we have a decent conformint vsnprintf that
759          * returns the number of bytes needed.  We give it a try though on
760          * a short buffer, since efficently speaking, it could be nice to
761          * above a second vsnprintf call.
762          */
763         char    buf[128];
764         va_list cpy;
765         va_copy(cpy, args);
766         len = vsnprintf(buf, sizeof(buf), fmt, cpy);
767         va_end (cpy);
768
769         if (len < (int)sizeof(buf)) {
770             *dat = util_strdup(buf);
771             return len;
772         }
773
774         /* not large enough ... */
775         tmp = mem_a(len + 1);
776         if ((ret = vsnprintf(tmp, len + 1, fmt, args)) != len) {
777             mem_d(tmp);
778             *dat = NULL;
779             return -1;
780         }
781
782         *dat = tmp;
783         return len;
784     #endif
785     /* never reached ... */
786     return -1;
787 }
788 int util_asprintf(char **ret, const char *fmt, ...) {
789     va_list  args;
790     int      read;
791     va_start(args, fmt);
792     read = util_vasprintf(ret, fmt, args);
793     va_end  (args);
794
795     return read;
796 }
797
798 /*
799  * Implementation of the Mersenne twister PRNG (pseudo random numer
800  * generator).  Implementation of MT19937.  Has a period of 2^19937-1
801  * which is a Mersenne Prime (hence the name).
802  *
803  * Implemented from specification and original paper:
804  * http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf
805  *
806  * This code is placed in the public domain by me personally
807  * (Dale Weiler, a.k.a graphitemaster).
808  */
809
810 #define MT_SIZE    624
811 #define MT_PERIOD  397
812 #define MT_SPACE   (MT_SIZE - MT_PERIOD)
813
814 static uint32_t mt_state[MT_SIZE];
815 static size_t   mt_index = 0;
816
817 static GMQCC_INLINE void mt_generate() {
818     /*
819      * The loop has been unrolled here: the original paper and implemenation
820      * Called for the following code:
821      * for (register unsigned i = 0; i < MT_SIZE; ++i) {
822      *     register uint32_t load;
823      *     load  = (0x80000000 & mt_state[i])                 // most  significant 32nd bit
824      *     load |= (0x7FFFFFFF & mt_state[(i + 1) % MT_SIZE]) // least significant 31nd bit
825      *
826      *     mt_state[i] = mt_state[(i + MT_PERIOD) % MT_SIZE] ^ (load >> 1);
827      *
828      *     if (load & 1) mt_state[i] ^= 0x9908B0DF;
829      * }
830      *
831      * This essentially is a waste: we have two modulus operations, and
832      * a branch that is executed every iteration from [0, MT_SIZE).
833      *
834      * Please see: http://www.quadibloc.com/crypto/co4814.htm for more
835      * information on how this clever trick works. 
836      */
837     static const uint32_t matrix[2] = {
838         0x00000000,
839         0x9908B0Df
840     };
841     /*
842      * This register gives up a little more speed by instructing the compiler
843      * to force these into CPU registers (they're counters for indexing mt_state
844      * which we can force the compiler to generate prefetch instructions for)
845      */
846     register uint32_t y;
847     register uint32_t i;
848
849     /*
850      * Said loop has been unrolled for MT_SPACE (226 iterations), opposed
851      * to [0, MT_SIZE)  (634 iterations).
852      */
853     for (i = 0; i < MT_SPACE; ++i) {
854         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
855         mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1];
856
857         i ++; /* loop unroll */
858
859         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
860         mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1];
861     }
862
863     /*
864      * collapsing the walls unrolled (evenly dividing 396 [632-227 = 396
865      * = 2*2*3*3*11])
866      */
867     i = MT_SPACE;
868     while (i < MT_SIZE - 1) {
869         /*
870          * We expand this 11 times .. manually, no macros are required
871          * here. This all fits in the CPU cache.
872          */
873         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
874         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
875         ++i;
876         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
877         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
878         ++i;
879         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
880         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
881         ++i;
882         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
883         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
884         ++i;
885         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
886         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
887         ++i;
888         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
889         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
890         ++i;
891         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
892         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
893         ++i;
894         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
895         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
896         ++i;
897         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
898         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
899         ++i;
900         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
901         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
902         ++i;
903         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
904         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
905         ++i;
906     }
907
908     /* i = mt_state[623] */
909     y                     = (0x80000000 & mt_state[MT_SIZE - 1]) | (0x7FFFFFFF & mt_state[MT_SIZE - 1]);
910     mt_state[MT_SIZE - 1] = mt_state[MT_PERIOD - 1] ^ (y >> 1) ^ matrix[y & 1];
911 }
912
913 void util_seed(uint32_t value) {
914     /*
915      * We seed the mt_state with a LCG (linear congruential generator)
916      * We're operating exactly on exactly m=32, so there is no need to
917      * use modulus.
918      *
919      * The multipler of choice is 0x6C07865, also knows as the Borosh-
920      * Niederreiter multipler used for modulus 2^32.  More can be read
921      * about this in Knuth's TAOCP Volume 2, page 106.
922      *
923      * If you don't own TAOCP something is wrong with you :-) .. so I
924      * also provided a link to the original paper by Borosh and
925      * Niederreiter.  It's called "Optional Multipliers for PRNG by The
926      * Linear Congruential Method" (1983).
927      * http://en.wikipedia.org/wiki/Linear_congruential_generator
928      *
929      * From said page, it says the following:
930      * "A common Mersenne twister implementation, interestingly enough
931      *  used an LCG to generate seed data."
932      *
933      * Remarks:
934      * The data we're operating on is 32-bits for the mt_state array, so
935      * there is no masking required with 0xFFFFFFFF
936      */
937     register size_t i;
938
939     mt_state[0] = value;
940     for (i = 1; i < MT_SIZE; ++i)
941         mt_state[i] = 0x6C078965 * (mt_state[i - 1] ^ mt_state[i - 1] >> 30) + i;
942 }
943
944 uint32_t util_rand() {
945     register uint32_t y;
946
947     /*
948      * This is inlined with any sane compiler (I checked)
949      * for some reason though, SubC seems to be generating invalid
950      * code when it inlines this.
951      */
952     if (!mt_index)
953         mt_generate();
954
955     y = mt_state[mt_index];
956
957     /* Standard tempering */
958     y ^= y >> 11;              /* +7 */
959     y ^= y << 7  & 0x9D2C5680; /* +4 */
960     y ^= y << 15 & 0xEFC60000; /* -4 */
961     y ^= y >> 18;              /* -7 */
962
963     if(++mt_index == MT_SIZE)
964          mt_index = 0;
965
966     return y;
967 }