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