Fixes
[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         char *str;
692         if ((len = _vscprintf(fmt, args)) < 0) {
693             *dat = NULL;
694             return -1;
695         }
696
697         tmp = mem_a(len + 1);
698         if ((ret = _vsnprintf(tmp, len+1, fmt, args)) != len) {
699             mem_d(tmp);
700             *dat = NULL;
701             return -1;
702         }
703         *dat = tmp;
704         return len;
705     #else
706         /*
707          * For everything else we have a decent conformint vsnprintf that
708          * returns the number of bytes needed.  We give it a try though on
709          * a short buffer, since efficently speaking, it could be nice to
710          * above a second vsnprintf call.
711          */
712         char    buf[128];
713         va_list cpy;
714         va_copy(cpy, args);
715         len = vsnprintf(buf, sizeof(buf), fmt, cpy);
716         va_end (cpy);
717
718         if (len < (int)sizeof(buf)) {
719             *dat = util_strdup(buf);
720             return len;
721         }
722
723         /* not large enough ... */
724         tmp = (char*)mem_a(len + 1);
725         if ((ret = vsnprintf(tmp, len + 1, fmt, args)) != len) {
726             mem_d(tmp);
727             *dat = NULL;
728             return -1;
729         }
730
731         *dat = tmp;
732         return len;
733     #endif
734 }
735 int util_asprintf(char **ret, const char *fmt, ...) {
736     va_list  args;
737     int      read;
738     va_start(args, fmt);
739     read = util_vasprintf(ret, fmt, args);
740     va_end  (args);
741
742     return read;
743 }
744
745 /*
746  * Implementation of the Mersenne twister PRNG (pseudo random numer
747  * generator).  Implementation of MT19937.  Has a period of 2^19937-1
748  * which is a Mersenne Prime (hence the name).
749  *
750  * Implemented from specification and original paper:
751  * http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf
752  *
753  * This code is placed in the public domain by me personally
754  * (Dale Weiler, a.k.a graphitemaster).
755  */
756
757 #define MT_SIZE    624
758 #define MT_PERIOD  397
759 #define MT_SPACE   (MT_SIZE - MT_PERIOD)
760
761 static uint32_t mt_state[MT_SIZE];
762 static size_t   mt_index = 0;
763
764 static GMQCC_INLINE void mt_generate() {
765     /*
766      * The loop has been unrolled here: the original paper and implemenation
767      * Called for the following code:
768      * for (register unsigned i = 0; i < MT_SIZE; ++i) {
769      *     register uint32_t load;
770      *     load  = (0x80000000 & mt_state[i])                 // most  significant 32nd bit
771      *     load |= (0x7FFFFFFF & mt_state[(i + 1) % MT_SIZE]) // least significant 31nd bit
772      *
773      *     mt_state[i] = mt_state[(i + MT_PERIOD) % MT_SIZE] ^ (load >> 1);
774      *
775      *     if (load & 1) mt_state[i] ^= 0x9908B0DF;
776      * }
777      *
778      * This essentially is a waste: we have two modulus operations, and
779      * a branch that is executed every iteration from [0, MT_SIZE).
780      *
781      * Please see: http://www.quadibloc.com/crypto/co4814.htm for more
782      * information on how this clever trick works. 
783      */
784     static const uint32_t matrix[2] = {
785         0x00000000,
786         0x9908B0Df
787     };
788     /*
789      * This register gives up a little more speed by instructing the compiler
790      * to force these into CPU registers (they're counters for indexing mt_state
791      * which we can force the compiler to generate prefetch instructions for)
792      */
793     register uint32_t y;
794     register uint32_t i;
795
796     /*
797      * Said loop has been unrolled for MT_SPACE (226 iterations), opposed
798      * to [0, MT_SIZE)  (634 iterations).
799      */
800     for (i = 0; i < MT_SPACE; ++i) {
801         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
802         mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1];
803
804         i ++; /* loop unroll */
805
806         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
807         mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1];
808     }
809
810     /*
811      * collapsing the walls unrolled (evenly dividing 396 [632-227 = 396
812      * = 2*2*3*3*11])
813      */
814     i = MT_SPACE;
815     while (i < MT_SIZE - 1) {
816         /*
817          * We expand this 11 times .. manually, no macros are required
818          * here. This all fits in the CPU cache.
819          */
820         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
821         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
822         ++i;
823         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
824         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
825         ++i;
826         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
827         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
828         ++i;
829         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
830         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
831         ++i;
832         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
833         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
834         ++i;
835         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
836         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
837         ++i;
838         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
839         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
840         ++i;
841         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
842         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
843         ++i;
844         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
845         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
846         ++i;
847         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
848         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
849         ++i;
850         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
851         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
852         ++i;
853     }
854
855     /* i = mt_state[623] */
856     y                     = (0x80000000 & mt_state[MT_SIZE - 1]) | (0x7FFFFFFF & mt_state[MT_SIZE - 1]);
857     mt_state[MT_SIZE - 1] = mt_state[MT_PERIOD - 1] ^ (y >> 1) ^ matrix[y & 1];
858 }
859
860 void util_seed(uint32_t value) {
861     /*
862      * We seed the mt_state with a LCG (linear congruential generator)
863      * We're operating exactly on exactly m=32, so there is no need to
864      * use modulus.
865      *
866      * The multipler of choice is 0x6C07865, also knows as the Borosh-
867      * Niederreiter multipler used for modulus 2^32.  More can be read
868      * about this in Knuth's TAOCP Volume 2, page 106.
869      *
870      * If you don't own TAOCP something is wrong with you :-) .. so I
871      * also provided a link to the original paper by Borosh and
872      * Niederreiter.  It's called "Optional Multipliers for PRNG by The
873      * Linear Congruential Method" (1983).
874      * http://en.wikipedia.org/wiki/Linear_congruential_generator
875      *
876      * From said page, it says the following:
877      * "A common Mersenne twister implementation, interestingly enough
878      *  used an LCG to generate seed data."
879      *
880      * Remarks:
881      * The data we're operating on is 32-bits for the mt_state array, so
882      * there is no masking required with 0xFFFFFFFF
883      */
884     register size_t i;
885
886     mt_state[0] = value;
887     for (i = 1; i < MT_SIZE; ++i)
888         mt_state[i] = 0x6C078965 * (mt_state[i - 1] ^ mt_state[i - 1] >> 30) + i;
889 }
890
891 uint32_t util_rand() {
892     register uint32_t y;
893
894     /*
895      * This is inlined with any sane compiler (I checked)
896      * for some reason though, SubC seems to be generating invalid
897      * code when it inlines this.
898      */
899     if (!mt_index)
900         mt_generate();
901
902     y = mt_state[mt_index];
903
904     /* Standard tempering */
905     y ^= y >> 11;              /* +7 */
906     y ^= y << 7  & 0x9D2C5680; /* +4 */
907     y ^= y << 15 & 0xEFC60000; /* -4 */
908     y ^= y >> 18;              /* -7 */
909
910     if(++mt_index == MT_SIZE)
911          mt_index = 0;
912
913     return y;
914 }