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