util.c

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