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