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