util.c

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