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