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 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 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  = (data[0] | (data[1] << 8) | (data[2] << 16) | (data[3] << 24));
469         alias *= mix;
470         alias ^= alias >> rot;
471         alias *= mix;
472
473         hash  *= mix;
474         hash  ^= alias;
475
476         data += 4;
477         size -= 4;
478     }
479
480     switch (size) {
481         case 3: hash ^= data[2] << 16;
482         case 2: hash ^= data[1] << 8;
483         case 1: hash ^= data[0];
484                 hash *= mix;
485     }
486
487     hash ^= hash >> 13;
488     hash *= mix;
489     hash ^= hash >> 15;
490
491     return (size_t) (hash % ht->size);
492 }
493
494 static hash_node_t *_util_htnewpair(const char *key, void *value) {
495     hash_node_t *node;
496     if (!(node = (hash_node_t*)mem_a(sizeof(hash_node_t))))
497         return NULL;
498
499     if (!(node->key = util_strdupe(key))) {
500         mem_d(node);
501         return NULL;
502     }
503
504     node->value = value;
505     node->next  = NULL;
506
507     return node;
508 }
509
510 /*
511  * EXPOSED INTERFACE for the hashtable implementation
512  * util_htnew(size)                             -- to make a new hashtable
513  * util_htset(table, key, value, sizeof(value)) -- to set something in the table
514  * util_htget(table, key)                       -- to get something from the table
515  * util_htdel(table)                            -- to delete the table
516  */
517 hash_table_t *util_htnew(size_t size) {
518     hash_table_t *hashtable = NULL;
519     if (size < 1)
520         return NULL;
521
522     if (!(hashtable = (hash_table_t*)mem_a(sizeof(hash_table_t))))
523         return NULL;
524
525     if (!(hashtable->table = (hash_node_t**)mem_a(sizeof(hash_node_t*) * size))) {
526         mem_d(hashtable);
527         return NULL;
528     }
529
530     hashtable->size = size;
531     memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
532
533     return hashtable;
534 }
535
536 void util_htseth(hash_table_t *ht, const char *key, size_t bin, void *value) {
537     hash_node_t *newnode = NULL;
538     hash_node_t *next    = NULL;
539     hash_node_t *last    = NULL;
540
541     next = ht->table[bin];
542
543     while (next && next->key && strcmp(key, next->key) > 0)
544         last = next, next = next->next;
545
546     /* already in table, do a replace */
547     if (next && next->key && strcmp(key, next->key) == 0) {
548         next->value = value;
549     } else {
550         /* not found, grow a pair man :P */
551         newnode = _util_htnewpair(key, value);
552         if (next == ht->table[bin]) {
553             newnode->next  = next;
554             ht->table[bin] = newnode;
555         } else if (!next) {
556             last->next = newnode;
557         } else {
558             newnode->next = next;
559             last->next = newnode;
560         }
561     }
562 }
563
564 void util_htset(hash_table_t *ht, const char *key, void *value) {
565     util_htseth(ht, key, util_hthash(ht, key), value);
566 }
567
568 void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
569     hash_node_t *pair = ht->table[bin];
570
571     while (pair && pair->key && strcmp(key, pair->key) > 0)
572         pair = pair->next;
573
574     if (!pair || !pair->key || strcmp(key, pair->key) != 0)
575         return NULL;
576
577     return pair->value;
578 }
579
580 void *util_htget(hash_table_t *ht, const char *key) {
581     return util_htgeth(ht, key, util_hthash(ht, key));
582 }
583
584 void *code_util_str_htgeth(hash_table_t *ht, const char *key, size_t bin) {
585     hash_node_t *pair;
586     size_t len, keylen;
587     int cmp;
588
589     keylen = strlen(key);
590
591     pair = ht->table[bin];
592     while (pair && pair->key) {
593         len = strlen(pair->key);
594         if (len < keylen) {
595             pair = pair->next;
596             continue;
597         }
598         if (keylen == len) {
599             cmp = strcmp(key, pair->key);
600             if (cmp == 0)
601                 return pair->value;
602             if (cmp < 0)
603                 return NULL;
604             pair = pair->next;
605             continue;
606         }
607         cmp = strcmp(key, pair->key + len - keylen);
608         if (cmp == 0) {
609             uintptr_t up = (uintptr_t)pair->value;
610             up += len - keylen;
611             return (void*)up;
612         }
613         pair = pair->next;
614     }
615     return NULL;
616 }
617
618 /*
619  * Free all allocated data in a hashtable, this is quite the amount
620  * of work.
621  */
622 void util_htrem(hash_table_t *ht, void (*callback)(void *data)) {
623     size_t i = 0;
624     for (; i < ht->size; i++) {
625         hash_node_t *n = ht->table[i];
626         hash_node_t *p;
627
628         /* free in list */
629         while (n) {
630             if (n->key)
631                 mem_d(n->key);
632             if (callback)
633                 callback(n->value);
634             p = n;
635             n = n->next;
636             mem_d(p);
637         }
638
639     }
640     /* free table */
641     mem_d(ht->table);
642     mem_d(ht);
643 }
644
645 void util_htrmh(hash_table_t *ht, const char *key, size_t bin, void (*cb)(void*)) {
646     hash_node_t **pair = &ht->table[bin];
647     hash_node_t *tmp;
648
649     while (*pair && (*pair)->key && strcmp(key, (*pair)->key) > 0)
650         pair = &(*pair)->next;
651
652     tmp = *pair;
653     if (!tmp || !tmp->key || strcmp(key, tmp->key) != 0)
654         return;
655
656     if (cb)
657         (*cb)(tmp->value);
658
659     *pair = tmp->next;
660     mem_d(tmp->key);
661     mem_d(tmp);
662 }
663
664 void util_htrm(hash_table_t *ht, const char *key, void (*cb)(void*)) {
665     util_htrmh(ht, key, util_hthash(ht, key), cb);
666 }
667
668 void util_htdel(hash_table_t *ht) {
669     util_htrem(ht, NULL);
670 }
671
672 /*
673  * Portable implementation of vasprintf/asprintf. Assumes vsnprintf
674  * exists, otherwise compiler error.
675  *
676  * TODO: fix for MSVC ....
677  */
678 int util_vasprintf(char **dat, const char *fmt, va_list args) {
679     int   ret;
680     int   len;
681     char *tmp = NULL;
682
683     /*
684      * For visuals tido _vsnprintf doesn't tell you the length of a
685      * formatted string if it overflows. However there is a MSVC
686      * intrinsic (which is documented wrong) called _vcsprintf which
687      * will return the required amount to allocate.
688      */
689     #ifdef _MSC_VER
690         if ((len = _vscprintf(fmt, args)) < 0) {
691             *dat = NULL;
692             return -1;
693         }
694
695         tmp = (char*)mem_a(len + 1);
696         if ((ret = _vsnprintf_s(tmp, len+1, len+1, fmt, args)) != len) {
697             mem_d(tmp);
698             *dat = NULL;
699             return -1;
700         }
701         *dat = tmp;
702         return len;
703     #else
704         /*
705          * For everything else we have a decent conformint vsnprintf that
706          * returns the number of bytes needed.  We give it a try though on
707          * a short buffer, since efficently speaking, it could be nice to
708          * above a second vsnprintf call.
709          */
710         char    buf[128];
711         va_list cpy;
712         va_copy(cpy, args);
713         len = vsnprintf(buf, sizeof(buf), fmt, cpy);
714         va_end (cpy);
715
716         if (len < (int)sizeof(buf)) {
717             *dat = util_strdup(buf);
718             return len;
719         }
720
721         /* not large enough ... */
722         tmp = (char*)mem_a(len + 1);
723         if ((ret = vsnprintf(tmp, len + 1, fmt, args)) != len) {
724             mem_d(tmp);
725             *dat = NULL;
726             return -1;
727         }
728
729         *dat = tmp;
730         return len;
731     #endif
732 }
733 int util_asprintf(char **ret, const char *fmt, ...) {
734     va_list  args;
735     int      read;
736     va_start(args, fmt);
737     read = util_vasprintf(ret, fmt, args);
738     va_end  (args);
739
740     return read;
741 }
742
743 /*
744  * These are various re-implementations (wrapping the real ones) of
745  * string functions that MSVC consideres unsafe. We wrap these up and
746  * use the safe varations on MSVC.
747  */
748 #ifdef _MSC_VER
749     static char **util_strerror_allocated() {
750         static char **data = NULL;
751         return data;
752     }
753
754     static void util_strerror_cleanup(void) {
755         size_t i;
756         char  **data = util_strerror_allocated();
757         for (i = 0; i < vec_size(data); i++)
758             mem_d(data[i]);
759         vec_free(data);
760     }
761
762     const char *util_strerror(int num) {
763         char         *allocated = NULL;
764         static bool   install   = false;
765         static size_t tries     = 0;
766         char        **vector    = util_strerror_allocated();
767
768         /* try installing cleanup handler */
769         while (!install) {
770             if (tries == 32)
771                 return "(unknown)";
772
773             install = !atexit(&util_strerror_cleanup);
774             tries ++;
775         }
776
777         allocated = (char*)mem_a(4096); /* A page must be enough */
778         strerror_s(allocated, 4096, num);
779     
780         vec_push(vector, allocated);
781         return (const char *)allocated;
782     }
783
784     int util_snprintf(char *src, size_t bytes, const char *format, ...) {
785         int      rt;
786         va_list  va;
787         va_start(va, format);
788
789         rt = vsprintf_s(src, bytes, format, va);
790         va_end  (va);
791
792         return rt;
793     }
794
795     char *util_strcat(char *dest, const char *src) {
796         strcat_s(dest, strlen(src), src);
797         return dest;
798     }
799
800     char *util_strncpy(char *dest, const char *src, size_t num) {
801         strncpy_s(dest, num, src, num);
802         return dest;
803     }
804 #else
805     const char *util_strerror(int num) {
806         return strerror(num);
807     }
808
809     int util_snprintf(char *src, size_t bytes, const char *format, ...) {
810         int      rt;
811         va_list  va;
812         va_start(va, format);
813         rt = vsnprintf(src, bytes, format, va);
814         va_end  (va);
815
816         return rt;
817     }
818
819     char *util_strcat(char *dest, const char *src) {
820         return strcat(dest, src);
821     }
822
823     char *util_strncpy(char *dest, const char *src, size_t num) {
824         return strncpy(dest, src, num);
825     }
826
827 #endif /*! _MSC_VER */
828
829 /*
830  * Implementation of the Mersenne twister PRNG (pseudo random numer
831  * generator).  Implementation of MT19937.  Has a period of 2^19937-1
832  * which is a Mersenne Prime (hence the name).
833  *
834  * Implemented from specification and original paper:
835  * http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf
836  *
837  * This code is placed in the public domain by me personally
838  * (Dale Weiler, a.k.a graphitemaster).
839  */
840
841 #define MT_SIZE    624
842 #define MT_PERIOD  397
843 #define MT_SPACE   (MT_SIZE - MT_PERIOD)
844
845 static uint32_t mt_state[MT_SIZE];
846 static size_t   mt_index = 0;
847
848 static GMQCC_INLINE void mt_generate() {
849     /*
850      * The loop has been unrolled here: the original paper and implemenation
851      * Called for the following code:
852      * for (register unsigned i = 0; i < MT_SIZE; ++i) {
853      *     register uint32_t load;
854      *     load  = (0x80000000 & mt_state[i])                 // most  significant 32nd bit
855      *     load |= (0x7FFFFFFF & mt_state[(i + 1) % MT_SIZE]) // least significant 31nd bit
856      *
857      *     mt_state[i] = mt_state[(i + MT_PERIOD) % MT_SIZE] ^ (load >> 1);
858      *
859      *     if (load & 1) mt_state[i] ^= 0x9908B0DF;
860      * }
861      *
862      * This essentially is a waste: we have two modulus operations, and
863      * a branch that is executed every iteration from [0, MT_SIZE).
864      *
865      * Please see: http://www.quadibloc.com/crypto/co4814.htm for more
866      * information on how this clever trick works.
867      */
868     static const uint32_t matrix[2] = {
869         0x00000000,
870         0x9908B0Df
871     };
872     /*
873      * This register gives up a little more speed by instructing the compiler
874      * to force these into CPU registers (they're counters for indexing mt_state
875      * which we can force the compiler to generate prefetch instructions for)
876      */
877     register uint32_t y;
878     register uint32_t i;
879
880     /*
881      * Said loop has been unrolled for MT_SPACE (226 iterations), opposed
882      * to [0, MT_SIZE)  (634 iterations).
883      */
884     for (i = 0; i < MT_SPACE; ++i) {
885         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
886         mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1];
887
888         i ++; /* loop unroll */
889
890         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
891         mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1];
892     }
893
894     /*
895      * collapsing the walls unrolled (evenly dividing 396 [632-227 = 396
896      * = 2*2*3*3*11])
897      */
898     i = MT_SPACE;
899     while (i < MT_SIZE - 1) {
900         /*
901          * We expand this 11 times .. manually, no macros are required
902          * here. This all fits in the CPU cache.
903          */
904         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
905         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
906         ++i;
907         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
908         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
909         ++i;
910         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
911         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
912         ++i;
913         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
914         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
915         ++i;
916         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
917         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
918         ++i;
919         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
920         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
921         ++i;
922         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
923         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
924         ++i;
925         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
926         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
927         ++i;
928         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
929         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
930         ++i;
931         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
932         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
933         ++i;
934         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
935         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
936         ++i;
937     }
938
939     /* i = mt_state[623] */
940     y                     = (0x80000000 & mt_state[MT_SIZE - 1]) | (0x7FFFFFFF & mt_state[MT_SIZE - 1]);
941     mt_state[MT_SIZE - 1] = mt_state[MT_PERIOD - 1] ^ (y >> 1) ^ matrix[y & 1];
942 }
943
944 void util_seed(uint32_t value) {
945     /*
946      * We seed the mt_state with a LCG (linear congruential generator)
947      * We're operating exactly on exactly m=32, so there is no need to
948      * use modulus.
949      *
950      * The multipler of choice is 0x6C07865, also knows as the Borosh-
951      * Niederreiter multipler used for modulus 2^32.  More can be read
952      * about this in Knuth's TAOCP Volume 2, page 106.
953      *
954      * If you don't own TAOCP something is wrong with you :-) .. so I
955      * also provided a link to the original paper by Borosh and
956      * Niederreiter.  It's called "Optional Multipliers for PRNG by The
957      * Linear Congruential Method" (1983).
958      * http://en.wikipedia.org/wiki/Linear_congruential_generator
959      *
960      * From said page, it says the following:
961      * "A common Mersenne twister implementation, interestingly enough
962      *  used an LCG to generate seed data."
963      *
964      * Remarks:
965      * The data we're operating on is 32-bits for the mt_state array, so
966      * there is no masking required with 0xFFFFFFFF
967      */
968     register size_t i;
969
970     mt_state[0] = value;
971     for (i = 1; i < MT_SIZE; ++i)
972         mt_state[i] = 0x6C078965 * (mt_state[i - 1] ^ mt_state[i - 1] >> 30) + i;
973 }
974
975 uint32_t util_rand() {
976     register uint32_t y;
977
978     /*
979      * This is inlined with any sane compiler (I checked)
980      * for some reason though, SubC seems to be generating invalid
981      * code when it inlines this.
982      */
983     if (!mt_index)
984         mt_generate();
985
986     y = mt_state[mt_index];
987
988     /* Standard tempering */
989     y ^= y >> 11;              /* +7 */
990     y ^= y << 7  & 0x9D2C5680; /* +4 */
991     y ^= y << 15 & 0xEFC60000; /* -4 */
992     y ^= y >> 18;              /* -7 */
993
994     if(++mt_index == MT_SIZE)
995          mt_index = 0;
996
997     return y;
998 }