Track strdups too in the statistics
[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 static uint64_t mem_ab = 0;
30 static uint64_t mem_db = 0;
31 static uint64_t mem_at = 0;
32 static uint64_t mem_dt = 0;
33 static uint64_t mem_pk = 0;
34 static uint64_t mem_hw = 0;
35
36 struct memblock_t {
37     const char  *file;
38     unsigned int line;
39     size_t       byte;
40     struct memblock_t *next;
41     struct memblock_t *prev;
42 };
43
44 #define PEAK_MEM             \
45     do {                     \
46         if (mem_hw > mem_pk) \
47             mem_pk = mem_hw; \
48     } while (0)
49
50 static struct memblock_t *mem_start = NULL;
51
52 void *util_memory_a(size_t byte, unsigned int line, const char *file) {
53     struct memblock_t *info = (struct memblock_t*)malloc(sizeof(struct memblock_t) + byte);
54     void              *data = (void*)(info+1);
55     if (!info) return NULL;
56     info->line = line;
57     info->byte = byte;
58     info->file = file;
59     info->prev = NULL;
60     info->next = mem_start;
61     if (mem_start)
62         mem_start->prev = info;
63     mem_start = info;
64
65     mem_at++;
66     mem_ab += info->byte;
67     mem_hw += info->byte;
68
69     PEAK_MEM;
70
71     return data;
72 }
73
74 void util_memory_d(void *ptrn) {
75     struct memblock_t *info = NULL;
76
77     if (!ptrn) return;
78     info = ((struct memblock_t*)ptrn - 1);
79
80     mem_db += info->byte;
81     mem_hw -= info->byte;
82     mem_dt++;
83
84     if (info->prev)
85         info->prev->next = info->next;
86     if (info->next)
87         info->next->prev = info->prev;
88     if (info == mem_start)
89         mem_start = info->next;
90
91     free(info);
92 }
93
94 void *util_memory_r(void *ptrn, size_t byte, unsigned int line, const char *file) {
95     struct memblock_t *oldinfo = NULL;
96
97     struct memblock_t *newinfo;
98
99     if (!ptrn)
100         return util_memory_a(byte, line, file);
101     if (!byte) {
102         util_memory_d(ptrn);
103         return NULL;
104     }
105
106     oldinfo = ((struct memblock_t*)ptrn - 1);
107     newinfo = ((struct memblock_t*)malloc(sizeof(struct memblock_t) + byte));
108
109     /* new data */
110     if (!newinfo) {
111         util_memory_d(oldinfo+1);
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_hw -= oldinfo->byte;
138     mem_ab += newinfo->byte;
139     mem_hw += newinfo->byte;
140
141     PEAK_MEM;
142
143     free(oldinfo);
144
145     return newinfo+1;
146 }
147
148 static void util_dumpmem(struct memblock_t *memory, uint16_t cols) {
149     uint32_t i, j;
150     for (i = 0; i < memory->byte + ((memory->byte % cols) ? (cols - memory->byte % cols) : 0); i++) {
151         if (i % cols == 0)    con_out("    0x%06X: ", i);
152         if (i < memory->byte) con_out("%02X "   , 0xFF & ((char*)(memory + 1))[i]);
153         else                  con_out("    ");
154
155         if ((uint16_t)(i % cols) == (cols - 1)) {
156             for (j = i - (cols - 1); j <= i; j++) {
157                 con_out("%c",
158                     (j >= memory->byte)
159                         ? ' '
160                         : (isprint(((char*)(memory + 1))[j]))
161                             ? 0xFF & ((char*)(memory + 1)) [j]
162                             : '.'
163                 );
164             }
165             con_out("\n");
166         }
167     }
168 }
169
170 /*
171  * The following is a VERY tight, efficent, hashtable for integer
172  * values and keys, and for nothing more. We could make our existing
173  * hashtable support type-genericness through a void * pointer but,
174  * ideally that would make things more complicated. We also don't need
175  * that much of a bloat for something as basic as this.
176  */
177 typedef struct {
178     size_t key;
179     size_t value;
180 } size_entry_t;
181 #define ST_SIZE 1024
182
183 typedef size_entry_t **size_table_t;
184
185 size_table_t util_st_new() {
186     return (size_table_t)memset(
187         mem_a(sizeof(size_entry_t*) * ST_SIZE),
188         0, ST_SIZE * sizeof(size_entry_t*)
189     );
190 }
191 void util_st_del(size_table_t table) {
192     size_t i = 0;
193     for (; i < ST_SIZE; i++) if(table[i]) mem_d(table[i]);
194     mem_d(table);
195 }
196 size_entry_t *util_st_get(size_table_t table, size_t key) {
197     size_t hash = (key % ST_SIZE);
198     while (table[hash] && table[hash]->key != key)
199         hash = (hash + 1) % ST_SIZE;
200     return table[hash];
201 }
202 void util_st_put(size_table_t table, size_t key, size_t value) {
203     size_t hash = (key % ST_SIZE);
204     while (table[hash] && table[hash]->key != key)
205         hash = (hash + 1) % ST_SIZE;
206     table[hash]        = (size_entry_t*)mem_a(sizeof(size_entry_t));
207     table[hash]->key   = key;
208     table[hash]->value = value;
209 }
210
211 static uint64_t      strdups      = 0;
212 static uint64_t      vectors      = 0;
213 static uint64_t      vector_sizes = 0;
214 static size_table_t  vector_usage = NULL;
215
216 void util_meminfo() {
217     struct memblock_t *info;
218
219     if (OPTS_OPTION_BOOL(OPTION_DEBUG)) {
220         for (info = mem_start; info; info = info->next) {
221             con_out("lost: %u (bytes) at %s:%u\n",
222                 info->byte,
223                 info->file,
224                 info->line);
225
226             util_dumpmem(info, OPTS_OPTION_U16(OPTION_MEMDUMPCOLS));
227         }
228     }
229
230     if (OPTS_OPTION_BOOL(OPTION_DEBUG) ||
231         OPTS_OPTION_BOOL(OPTION_MEMCHK)) {
232         con_out("Memory information:\n\
233             Total allocations:   %llu\n\
234             Total deallocations: %llu\n\
235             Total allocated:     %f (MB)\n\
236             Total deallocated:   %f (MB)\n\
237             Total peak memory:   %f (MB)\n\
238             Total leaked memory: %f (MB) in %llu allocations\n",
239                 mem_at,
240                 mem_dt,
241                 (float)(mem_ab)           / 1048576.0f,
242                 (float)(mem_db)           / 1048576.0f,
243                 (float)(mem_pk)           / 1048576.0f,
244                 (float)(mem_ab -  mem_db) / 1048576.0f,
245
246                 /* could be more clever */
247                 (mem_at -  mem_dt)
248         );
249     }
250     
251     if (OPTS_OPTION_BOOL(OPTION_STATISTICS) ||
252         OPTS_OPTION_BOOL(OPTION_MEMCHK)) {
253         size_t i=0;
254         size_t e=1;
255         
256         con_out("Additional Statistics:\n\
257             Total vectors allocated:    %u\n\
258             Total string duplicates:    %u\n\
259             Total unique vector sizes:  %u\n",
260             (unsigned)vectors,
261             (unsigned)strdups,
262             (unsigned)vector_sizes
263         );
264         
265         for (; i < ST_SIZE; i++) {
266             size_entry_t *entry;
267             
268             if (!(entry = vector_usage[i]))
269                 continue;
270             
271             con_out("               %u| # of %3u (bytes) vectors: %u\n",
272                 (unsigned)e,
273                 (unsigned)entry->key,
274                 (unsigned)entry->value
275             );
276             e++;
277         }
278     }
279     
280     if (vector_usage)
281         util_st_del(vector_usage);
282 }
283
284 /*
285  * Some string utility functions, because strdup uses malloc, and we want
286  * to track all memory (without replacing malloc).
287  */
288 char *_util_Estrdup(const char *s, const char *file, size_t line) {
289     size_t  len = 0;
290     char   *ptr = NULL;
291
292     /* in case of -DNOTRACK */
293     (void)file;
294     (void)line;
295
296     if (!s)
297         return NULL;
298
299     if ((len = strlen(s)) && (ptr = (char*)mem_af(len+1, line, file))) {
300         memcpy(ptr, s, len);
301         ptr[len] = '\0';
302     }
303     strdups++;
304     return ptr;
305 }
306
307 char *_util_Estrdup_empty(const char *s, const char *file, size_t line) {
308     size_t  len = 0;
309     char   *ptr = NULL;
310
311     /* in case of -DNOTRACK */
312     (void)file;
313     (void)line;
314
315     if (!s)
316         return NULL;
317
318     len = strlen(s);
319     if ((ptr = (char*)mem_af(len+1, line, file))) {
320         memcpy(ptr, s, len);
321         ptr[len] = '\0';
322     }
323     strdups++;
324     return ptr;
325 }
326
327 void util_debug(const char *area, const char *ms, ...) {
328     va_list  va;
329     if (!OPTS_OPTION_BOOL(OPTION_DEBUG))
330         return;
331
332     if (!strcmp(area, "MEM") && !OPTS_OPTION_BOOL(OPTION_MEMCHK))
333         return;
334
335     va_start(va, ms);
336     con_out ("[%s] ", area);
337     con_vout(ms, va);
338     va_end  (va);
339 }
340
341 /*
342  * only required if big endian .. otherwise no need to swap
343  * data.
344  */
345 #if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_BIG
346     static GMQCC_INLINE void util_swap16(uint16_t *d, size_t l) {
347         while (l--) {
348             d[l] = (d[l] << 8) | (d[l] >> 8);
349         }
350     }
351
352     static GMQCC_INLINE void util_swap32(uint32_t *d, size_t l) {
353         while (l--) {
354             uint32_t v;
355             v = ((d[l] << 8) & 0xFF00FF00) | ((d[l] >> 8) & 0x00FF00FF);
356             d[l] = (v << 16) | (v >> 16);
357         }
358     }
359
360     /* Some strange system doesn't like constants that big, AND doesn't recognize an ULL suffix
361      * so let's go the safe way
362      */
363     static GMQCC_INLINE void util_swap64(uint32_t *d, size_t l) {
364         /*
365         while (l--) {
366             uint64_t v;
367             v = ((d[l] << 8) & 0xFF00FF00FF00FF00) | ((d[l] >> 8) & 0x00FF00FF00FF00FF);
368             v = ((v << 16) & 0xFFFF0000FFFF0000) | ((v >> 16) & 0x0000FFFF0000FFFF);
369             d[l] = (v << 32) | (v >> 32);
370         }
371         */
372         size_t i;
373         for (i = 0; i < l; i += 2) {
374             uint32_t v1 = d[i];
375             d[i] = d[i+1];
376             d[i+1] = v1;
377             util_swap32(d+i, 2);
378         }
379     }
380 #endif
381
382 void util_endianswap(void *_data, size_t length, unsigned int typesize) {
383 #   if PLATFORM_BYTE_ORDER == -1 /* runtime check */
384     if (*((char*)&typesize))
385         return;
386 #else
387     /* prevent unused warnings */
388     (void) _data;
389     (void) length;
390     (void) typesize;
391
392 #   if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_LITTLE
393         return;
394 #   else
395         switch (typesize) {
396             case 1: return;
397             case 2:
398                 util_swap16((uint16_t*)_data, length>>1);
399                 return;
400             case 4:
401                 util_swap32((uint32_t*)_data, length>>2);
402                 return;
403             case 8:
404                 util_swap64((uint32_t*)_data, length>>3);
405                 return;
406
407             default: exit(EXIT_FAILURE); /* please blow the fuck up! */
408         }
409 #   endif
410 #endif
411 }
412
413 /*
414  * CRC algorithms vary in the width of the polynomial, the value of said polynomial,
415  * the initial value used for the register, weather the bits of each byte are reflected
416  * before being processed, weather the algorithm itself feeds input bytes through the
417  * register or XORs them with a byte from one end and then straight into the table, as
418  * well as (but not limited to the idea of reflected versions) where the final register
419  * value becomes reversed, and finally weather the value itself is used to XOR the final
420  * register value.  AS such you can already imagine how painfully annoying CRCs are,
421  * of course we stand to target Quake, which expects it's certian set of rules for proper
422  * calculation of a CRC.
423  *
424  * In most traditional CRC algorithms on uses a reflected table driven method where a value
425  * or register is reflected if it's bits are swapped around it's center.  For example:
426  * take the bits 0101 is the 4-bit reflection of 1010, and respectfully 0011 would be the
427  * reflection of 1100. Quake however expects a NON-Reflected CRC on the output, but still
428  * requires a final XOR on the values (0xFFFF and 0x0000) this is a standard CCITT CRC-16
429  * which I respectfully as a programmer don't agree with.
430  *
431  * So now you know what we target, and why we target it, despite how unsettling it may seem
432  * but those are what Quake seems to request.
433  */
434
435 static const uint16_t util_crc16_table[] = {
436     0x0000,     0x1021,     0x2042,     0x3063,     0x4084,     0x50A5,
437     0x60C6,     0x70E7,     0x8108,     0x9129,     0xA14A,     0xB16B,
438     0xC18C,     0xD1AD,     0xE1CE,     0xF1EF,     0x1231,     0x0210,
439     0x3273,     0x2252,     0x52B5,     0x4294,     0x72F7,     0x62D6,
440     0x9339,     0x8318,     0xB37B,     0xA35A,     0xD3BD,     0xC39C,
441     0xF3FF,     0xE3DE,     0x2462,     0x3443,     0x0420,     0x1401,
442     0x64E6,     0x74C7,     0x44A4,     0x5485,     0xA56A,     0xB54B,
443     0x8528,     0x9509,     0xE5EE,     0xF5CF,     0xC5AC,     0xD58D,
444     0x3653,     0x2672,     0x1611,     0x0630,     0x76D7,     0x66F6,
445     0x5695,     0x46B4,     0xB75B,     0xA77A,     0x9719,     0x8738,
446     0xF7DF,     0xE7FE,     0xD79D,     0xC7BC,     0x48C4,     0x58E5,
447     0x6886,     0x78A7,     0x0840,     0x1861,     0x2802,     0x3823,
448     0xC9CC,     0xD9ED,     0xE98E,     0xF9AF,     0x8948,     0x9969,
449     0xA90A,     0xB92B,     0x5AF5,     0x4AD4,     0x7AB7,     0x6A96,
450     0x1A71,     0x0A50,     0x3A33,     0x2A12,     0xDBFD,     0xCBDC,
451     0xFBBF,     0xEB9E,     0x9B79,     0x8B58,     0xBB3B,     0xAB1A,
452     0x6CA6,     0x7C87,     0x4CE4,     0x5CC5,     0x2C22,     0x3C03,
453     0x0C60,     0x1C41,     0xEDAE,     0xFD8F,     0xCDEC,     0xDDCD,
454     0xAD2A,     0xBD0B,     0x8D68,     0x9D49,     0x7E97,     0x6EB6,
455     0x5ED5,     0x4EF4,     0x3E13,     0x2E32,     0x1E51,     0x0E70,
456     0xFF9F,     0xEFBE,     0xDFDD,     0xCFFC,     0xBF1B,     0xAF3A,
457     0x9F59,     0x8F78,     0x9188,     0x81A9,     0xB1CA,     0xA1EB,
458     0xD10C,     0xC12D,     0xF14E,     0xE16F,     0x1080,     0x00A1,
459     0x30C2,     0x20E3,     0x5004,     0x4025,     0x7046,     0x6067,
460     0x83B9,     0x9398,     0xA3FB,     0xB3DA,     0xC33D,     0xD31C,
461     0xE37F,     0xF35E,     0x02B1,     0x1290,     0x22F3,     0x32D2,
462     0x4235,     0x5214,     0x6277,     0x7256,     0xB5EA,     0xA5CB,
463     0x95A8,     0x8589,     0xF56E,     0xE54F,     0xD52C,     0xC50D,
464     0x34E2,     0x24C3,     0x14A0,     0x0481,     0x7466,     0x6447,
465     0x5424,     0x4405,     0xA7DB,     0xB7FA,     0x8799,     0x97B8,
466     0xE75F,     0xF77E,     0xC71D,     0xD73C,     0x26D3,     0x36F2,
467     0x0691,     0x16B0,     0x6657,     0x7676,     0x4615,     0x5634,
468     0xD94C,     0xC96D,     0xF90E,     0xE92F,     0x99C8,     0x89E9,
469     0xB98A,     0xA9AB,     0x5844,     0x4865,     0x7806,     0x6827,
470     0x18C0,     0x08E1,     0x3882,     0x28A3,     0xCB7D,     0xDB5C,
471     0xEB3F,     0xFB1E,     0x8BF9,     0x9BD8,     0xABBB,     0xBB9A,
472     0x4A75,     0x5A54,     0x6A37,     0x7A16,     0x0AF1,     0x1AD0,
473     0x2AB3,     0x3A92,     0xFD2E,     0xED0F,     0xDD6C,     0xCD4D,
474     0xBDAA,     0xAD8B,     0x9DE8,     0x8DC9,     0x7C26,     0x6C07,
475     0x5C64,     0x4C45,     0x3CA2,     0x2C83,     0x1CE0,     0x0CC1,
476     0xEF1F,     0xFF3E,     0xCF5D,     0xDF7C,     0xAF9B,     0xBFBA,
477     0x8FD9,     0x9FF8,     0x6E17,     0x7E36,     0x4E55,     0x5E74,
478     0x2E93,     0x3EB2,     0x0ED1,     0x1EF0
479 };
480
481 /* Non - Reflected */
482 uint16_t util_crc16(uint16_t current, const char *k, size_t len) {
483     register uint16_t h = current;
484     for (; len; --len, ++k)
485         h = util_crc16_table[(h>>8)^((unsigned char)*k)]^(h<<8);
486     return h;
487 }
488 /* Reflective Varation (for reference) */
489 #if 0
490 uint16_t util_crc16(const char *k, int len, const short clamp) {
491     register uint16_t h= (uint16_t)0xFFFFFFFF;
492     for (; len; --len, ++k)
493         h = util_crc16_table[(h^((unsigned char)*k))&0xFF]^(h>>8);
494     return (~h)%clamp;
495 }
496 #endif
497
498 size_t util_strtocmd(const char *in, char *out, size_t outsz) {
499     size_t sz = 1;
500     for (; *in && sz < outsz; ++in, ++out, ++sz)
501         *out = (*in == '-') ? '_' : (isalpha(*in) && !isupper(*in)) ? *in + 'A' - 'a': *in;
502     *out = 0;
503     return sz-1;
504 }
505
506 size_t util_strtononcmd(const char *in, char *out, size_t outsz) {
507     size_t sz = 1;
508     for (; *in && sz < outsz; ++in, ++out, ++sz)
509         *out = (*in == '_') ? '-' : (isalpha(*in) && isupper(*in)) ? *in + 'a' - 'A' : *in;
510     *out = 0;
511     return sz-1;
512 }
513
514 /* TODO: rewrite ... when I redo the ve cleanup */
515 void _util_vec_grow(void **a, size_t i, size_t s) {
516     vector_t     *d = vec_meta(*a);
517     size_t        m = 0;
518     size_entry_t *e = NULL;
519     void         *p = NULL;
520     
521     if (*a) {
522         m = 2 * d->allocated + i;
523         p = mem_r(d, s * m + sizeof(vector_t));
524     } else {
525         m = i + 1;
526         p = mem_a(s * m + sizeof(vector_t));
527         ((vector_t*)p)->used = 0;
528         vectors++;
529     }
530     
531     if (!vector_usage)
532         vector_usage = util_st_new();
533
534     if ((e = util_st_get(vector_usage, s))) {
535         e->value ++;
536     } else {
537         util_st_put(vector_usage, s, 1); /* start off with 1 */
538         vector_sizes++;
539     }
540
541     *a = (vector_t*)p + 1;
542     vec_meta(*a)->allocated = m;
543 }
544
545 /*
546  * Hash table for generic data, based on dynamic memory allocations
547  * all around.  This is the internal interface, please look for
548  * EXPOSED INTERFACE comment below
549  */
550 typedef struct hash_node_t {
551     char               *key;   /* the key for this node in table */
552     void               *value; /* pointer to the data as void*   */
553     struct hash_node_t *next;  /* next node (linked list)        */
554 } hash_node_t;
555
556 GMQCC_INLINE size_t util_hthash(hash_table_t *ht, const char *key) {
557     const uint32_t       mix   = 0x5BD1E995;
558     const uint32_t       rot   = 24;
559     size_t               size  = strlen(key);
560     uint32_t             hash  = 0x1EF0 /* LICRC TAB */  ^ size;
561     uint32_t             alias = 0;
562     const unsigned char *data  = (const unsigned char*)key;
563
564     while (size >= 4) {
565         alias  = (data[0] | (data[1] << 8) | (data[2] << 16) | (data[3] << 24));
566         alias *= mix;
567         alias ^= alias >> rot;
568         alias *= mix;
569
570         hash  *= mix;
571         hash  ^= alias;
572
573         data += 4;
574         size -= 4;
575     }
576
577     switch (size) {
578         case 3: hash ^= data[2] << 16;
579         case 2: hash ^= data[1] << 8;
580         case 1: hash ^= data[0];
581                 hash *= mix;
582     }
583
584     hash ^= hash >> 13;
585     hash *= mix;
586     hash ^= hash >> 15;
587
588     return (size_t) (hash % ht->size);
589 }
590
591 static hash_node_t *_util_htnewpair(const char *key, void *value) {
592     hash_node_t *node;
593     if (!(node = (hash_node_t*)mem_a(sizeof(hash_node_t))))
594         return NULL;
595
596     if (!(node->key = util_strdupe(key))) {
597         mem_d(node);
598         return NULL;
599     }
600
601     node->value = value;
602     node->next  = NULL;
603
604     return node;
605 }
606
607 /*
608  * EXPOSED INTERFACE for the hashtable implementation
609  * util_htnew(size)                             -- to make a new hashtable
610  * util_htset(table, key, value, sizeof(value)) -- to set something in the table
611  * util_htget(table, key)                       -- to get something from the table
612  * util_htdel(table)                            -- to delete the table
613  */
614 hash_table_t *util_htnew(size_t size) {
615     hash_table_t *hashtable = NULL;
616     if (size < 1)
617         return NULL;
618
619     if (!(hashtable = (hash_table_t*)mem_a(sizeof(hash_table_t))))
620         return NULL;
621
622     if (!(hashtable->table = (hash_node_t**)mem_a(sizeof(hash_node_t*) * size))) {
623         mem_d(hashtable);
624         return NULL;
625     }
626
627     hashtable->size = size;
628     memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
629
630     return hashtable;
631 }
632
633 void util_htseth(hash_table_t *ht, const char *key, size_t bin, void *value) {
634     hash_node_t *newnode = NULL;
635     hash_node_t *next    = NULL;
636     hash_node_t *last    = NULL;
637
638     next = ht->table[bin];
639
640     while (next && next->key && strcmp(key, next->key) > 0)
641         last = next, next = next->next;
642
643     /* already in table, do a replace */
644     if (next && next->key && strcmp(key, next->key) == 0) {
645         next->value = value;
646     } else {
647         /* not found, grow a pair man :P */
648         newnode = _util_htnewpair(key, value);
649         if (next == ht->table[bin]) {
650             newnode->next  = next;
651             ht->table[bin] = newnode;
652         } else if (!next) {
653             last->next = newnode;
654         } else {
655             newnode->next = next;
656             last->next = newnode;
657         }
658     }
659 }
660
661 void util_htset(hash_table_t *ht, const char *key, void *value) {
662     util_htseth(ht, key, util_hthash(ht, key), value);
663 }
664
665 void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
666     hash_node_t *pair = ht->table[bin];
667
668     while (pair && pair->key && strcmp(key, pair->key) > 0)
669         pair = pair->next;
670
671     if (!pair || !pair->key || strcmp(key, pair->key) != 0)
672         return NULL;
673
674     return pair->value;
675 }
676
677 void *util_htget(hash_table_t *ht, const char *key) {
678     return util_htgeth(ht, key, util_hthash(ht, key));
679 }
680
681 void *code_util_str_htgeth(hash_table_t *ht, const char *key, size_t bin) {
682     hash_node_t *pair;
683     size_t len, keylen;
684     int cmp;
685
686     keylen = strlen(key);
687
688     pair = ht->table[bin];
689     while (pair && pair->key) {
690         len = strlen(pair->key);
691         if (len < keylen) {
692             pair = pair->next;
693             continue;
694         }
695         if (keylen == len) {
696             cmp = strcmp(key, pair->key);
697             if (cmp == 0)
698                 return pair->value;
699             if (cmp < 0)
700                 return NULL;
701             pair = pair->next;
702             continue;
703         }
704         cmp = strcmp(key, pair->key + len - keylen);
705         if (cmp == 0) {
706             uintptr_t up = (uintptr_t)pair->value;
707             up += len - keylen;
708             return (void*)up;
709         }
710         pair = pair->next;
711     }
712     return NULL;
713 }
714
715 /*
716  * Free all allocated data in a hashtable, this is quite the amount
717  * of work.
718  */
719 void util_htrem(hash_table_t *ht, void (*callback)(void *data)) {
720     size_t i = 0;
721     for (; i < ht->size; i++) {
722         hash_node_t *n = ht->table[i];
723         hash_node_t *p;
724
725         /* free in list */
726         while (n) {
727             if (n->key)
728                 mem_d(n->key);
729             if (callback)
730                 callback(n->value);
731             p = n;
732             n = n->next;
733             mem_d(p);
734         }
735
736     }
737     /* free table */
738     mem_d(ht->table);
739     mem_d(ht);
740 }
741
742 void util_htrmh(hash_table_t *ht, const char *key, size_t bin, void (*cb)(void*)) {
743     hash_node_t **pair = &ht->table[bin];
744     hash_node_t *tmp;
745
746     while (*pair && (*pair)->key && strcmp(key, (*pair)->key) > 0)
747         pair = &(*pair)->next;
748
749     tmp = *pair;
750     if (!tmp || !tmp->key || strcmp(key, tmp->key) != 0)
751         return;
752
753     if (cb)
754         (*cb)(tmp->value);
755
756     *pair = tmp->next;
757     mem_d(tmp->key);
758     mem_d(tmp);
759 }
760
761 void util_htrm(hash_table_t *ht, const char *key, void (*cb)(void*)) {
762     util_htrmh(ht, key, util_hthash(ht, key), cb);
763 }
764
765 void util_htdel(hash_table_t *ht) {
766     util_htrem(ht, NULL);
767 }
768
769 /*
770  * Portable implementation of vasprintf/asprintf. Assumes vsnprintf
771  * exists, otherwise compiler error.
772  *
773  * TODO: fix for MSVC ....
774  */
775 int util_vasprintf(char **dat, const char *fmt, va_list args) {
776     int   ret;
777     int   len;
778     char *tmp = NULL;
779
780     /*
781      * For visuals tido _vsnprintf doesn't tell you the length of a
782      * formatted string if it overflows. However there is a MSVC
783      * intrinsic (which is documented wrong) called _vcsprintf which
784      * will return the required amount to allocate.
785      */
786     #ifdef _MSC_VER
787         if ((len = _vscprintf(fmt, args)) < 0) {
788             *dat = NULL;
789             return -1;
790         }
791
792         tmp = (char*)mem_a(len + 1);
793         if ((ret = _vsnprintf_s(tmp, len+1, len+1, fmt, args)) != len) {
794             mem_d(tmp);
795             *dat = NULL;
796             return -1;
797         }
798         *dat = tmp;
799         return len;
800     #else
801         /*
802          * For everything else we have a decent conformint vsnprintf that
803          * returns the number of bytes needed.  We give it a try though on
804          * a short buffer, since efficently speaking, it could be nice to
805          * above a second vsnprintf call.
806          */
807         char    buf[128];
808         va_list cpy;
809         va_copy(cpy, args);
810         len = vsnprintf(buf, sizeof(buf), fmt, cpy);
811         va_end (cpy);
812
813         if (len < (int)sizeof(buf)) {
814             *dat = util_strdup(buf);
815             return len;
816         }
817
818         /* not large enough ... */
819         tmp = (char*)mem_a(len + 1);
820         if ((ret = vsnprintf(tmp, len + 1, fmt, args)) != len) {
821             mem_d(tmp);
822             *dat = NULL;
823             return -1;
824         }
825
826         *dat = tmp;
827         return len;
828     #endif
829 }
830 int util_asprintf(char **ret, const char *fmt, ...) {
831     va_list  args;
832     int      read;
833     va_start(args, fmt);
834     read = util_vasprintf(ret, fmt, args);
835     va_end  (args);
836
837     return read;
838 }
839
840 /*
841  * These are various re-implementations (wrapping the real ones) of
842  * string functions that MSVC consideres unsafe. We wrap these up and
843  * use the safe varations on MSVC.
844  */
845 #ifdef _MSC_VER
846     static char **util_strerror_allocated() {
847         static char **data = NULL;
848         return data;
849     }
850
851     static void util_strerror_cleanup(void) {
852         size_t i;
853         char  **data = util_strerror_allocated();
854         for (i = 0; i < vec_size(data); i++)
855             mem_d(data[i]);
856         vec_free(data);
857     }
858
859     const char *util_strerror(int num) {
860         char         *allocated = NULL;
861         static bool   install   = false;
862         static size_t tries     = 0;
863         char        **vector    = util_strerror_allocated();
864
865         /* try installing cleanup handler */
866         while (!install) {
867             if (tries == 32)
868                 return "(unknown)";
869
870             install = !atexit(&util_strerror_cleanup);
871             tries ++;
872         }
873
874         allocated = (char*)mem_a(4096); /* A page must be enough */
875         strerror_s(allocated, 4096, num);
876     
877         vec_push(vector, allocated);
878         return (const char *)allocated;
879     }
880
881     int util_snprintf(char *src, size_t bytes, const char *format, ...) {
882         int      rt;
883         va_list  va;
884         va_start(va, format);
885
886         rt = vsprintf_s(src, bytes, format, va);
887         va_end  (va);
888
889         return rt;
890     }
891
892     char *util_strcat(char *dest, const char *src) {
893         strcat_s(dest, strlen(src), src);
894         return dest;
895     }
896
897     char *util_strncpy(char *dest, const char *src, size_t num) {
898         strncpy_s(dest, num, src, num);
899         return dest;
900     }
901 #else
902     const char *util_strerror(int num) {
903         return strerror(num);
904     }
905
906     int util_snprintf(char *src, size_t bytes, const char *format, ...) {
907         int      rt;
908         va_list  va;
909         va_start(va, format);
910         rt = vsnprintf(src, bytes, format, va);
911         va_end  (va);
912
913         return rt;
914     }
915
916     char *util_strcat(char *dest, const char *src) {
917         return strcat(dest, src);
918     }
919
920     char *util_strncpy(char *dest, const char *src, size_t num) {
921         return strncpy(dest, src, num);
922     }
923
924 #endif /*! _MSC_VER */
925
926 /*
927  * Implementation of the Mersenne twister PRNG (pseudo random numer
928  * generator).  Implementation of MT19937.  Has a period of 2^19937-1
929  * which is a Mersenne Prime (hence the name).
930  *
931  * Implemented from specification and original paper:
932  * http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf
933  *
934  * This code is placed in the public domain by me personally
935  * (Dale Weiler, a.k.a graphitemaster).
936  */
937
938 #define MT_SIZE    624
939 #define MT_PERIOD  397
940 #define MT_SPACE   (MT_SIZE - MT_PERIOD)
941
942 static uint32_t mt_state[MT_SIZE];
943 static size_t   mt_index = 0;
944
945 static GMQCC_INLINE void mt_generate() {
946     /*
947      * The loop has been unrolled here: the original paper and implemenation
948      * Called for the following code:
949      * for (register unsigned i = 0; i < MT_SIZE; ++i) {
950      *     register uint32_t load;
951      *     load  = (0x80000000 & mt_state[i])                 // most  significant 32nd bit
952      *     load |= (0x7FFFFFFF & mt_state[(i + 1) % MT_SIZE]) // least significant 31nd bit
953      *
954      *     mt_state[i] = mt_state[(i + MT_PERIOD) % MT_SIZE] ^ (load >> 1);
955      *
956      *     if (load & 1) mt_state[i] ^= 0x9908B0DF;
957      * }
958      *
959      * This essentially is a waste: we have two modulus operations, and
960      * a branch that is executed every iteration from [0, MT_SIZE).
961      *
962      * Please see: http://www.quadibloc.com/crypto/co4814.htm for more
963      * information on how this clever trick works.
964      */
965     static const uint32_t matrix[2] = {
966         0x00000000,
967         0x9908B0Df
968     };
969     /*
970      * This register gives up a little more speed by instructing the compiler
971      * to force these into CPU registers (they're counters for indexing mt_state
972      * which we can force the compiler to generate prefetch instructions for)
973      */
974     register uint32_t y;
975     register uint32_t i;
976
977     /*
978      * Said loop has been unrolled for MT_SPACE (226 iterations), opposed
979      * to [0, MT_SIZE)  (634 iterations).
980      */
981     for (i = 0; i < MT_SPACE; ++i) {
982         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
983         mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1];
984
985         i ++; /* loop unroll */
986
987         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
988         mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1];
989     }
990
991     /*
992      * collapsing the walls unrolled (evenly dividing 396 [632-227 = 396
993      * = 2*2*3*3*11])
994      */
995     i = MT_SPACE;
996     while (i < MT_SIZE - 1) {
997         /*
998          * We expand this 11 times .. manually, no macros are required
999          * here. This all fits in the CPU cache.
1000          */
1001         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
1002         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
1003         ++i;
1004         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
1005         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
1006         ++i;
1007         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
1008         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
1009         ++i;
1010         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
1011         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
1012         ++i;
1013         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
1014         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
1015         ++i;
1016         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
1017         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
1018         ++i;
1019         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
1020         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
1021         ++i;
1022         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
1023         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
1024         ++i;
1025         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
1026         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
1027         ++i;
1028         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
1029         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
1030         ++i;
1031         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
1032         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
1033         ++i;
1034     }
1035
1036     /* i = mt_state[623] */
1037     y                     = (0x80000000 & mt_state[MT_SIZE - 1]) | (0x7FFFFFFF & mt_state[MT_SIZE - 1]);
1038     mt_state[MT_SIZE - 1] = mt_state[MT_PERIOD - 1] ^ (y >> 1) ^ matrix[y & 1];
1039 }
1040
1041 void util_seed(uint32_t value) {
1042     /*
1043      * We seed the mt_state with a LCG (linear congruential generator)
1044      * We're operating exactly on exactly m=32, so there is no need to
1045      * use modulus.
1046      *
1047      * The multipler of choice is 0x6C07865, also knows as the Borosh-
1048      * Niederreiter multipler used for modulus 2^32.  More can be read
1049      * about this in Knuth's TAOCP Volume 2, page 106.
1050      *
1051      * If you don't own TAOCP something is wrong with you :-) .. so I
1052      * also provided a link to the original paper by Borosh and
1053      * Niederreiter.  It's called "Optional Multipliers for PRNG by The
1054      * Linear Congruential Method" (1983).
1055      * http://en.wikipedia.org/wiki/Linear_congruential_generator
1056      *
1057      * From said page, it says the following:
1058      * "A common Mersenne twister implementation, interestingly enough
1059      *  used an LCG to generate seed data."
1060      *
1061      * Remarks:
1062      * The data we're operating on is 32-bits for the mt_state array, so
1063      * there is no masking required with 0xFFFFFFFF
1064      */
1065     register size_t i;
1066
1067     mt_state[0] = value;
1068     for (i = 1; i < MT_SIZE; ++i)
1069         mt_state[i] = 0x6C078965 * (mt_state[i - 1] ^ mt_state[i - 1] >> 30) + i;
1070 }
1071
1072 uint32_t util_rand() {
1073     register uint32_t y;
1074
1075     /*
1076      * This is inlined with any sane compiler (I checked)
1077      * for some reason though, SubC seems to be generating invalid
1078      * code when it inlines this.
1079      */
1080     if (!mt_index)
1081         mt_generate();
1082
1083     y = mt_state[mt_index];
1084
1085     /* Standard tempering */
1086     y ^= y >> 11;              /* +7 */
1087     y ^= y << 7  & 0x9D2C5680; /* +4 */
1088     y ^= y << 15 & 0xEFC60000; /* -4 */
1089     y ^= y >> 18;              /* -7 */
1090
1091     if(++mt_index == MT_SIZE)
1092          mt_index = 0;
1093
1094     return y;
1095 }