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         char *str;
 692         if ((len = _vscprintf(fmt, args)) < 0) {
 693             *dat = NULL;
 694             return -1;
 695         }
 696
 697         tmp = mem_a(len + 1);
 698         if ((ret = _vsnprintf(tmp, len+1, fmt, args)) != len) {
 699             mem_d(tmp);
 700             *dat = NULL;
 701             return -1;
 702         }
 703         *dat = tmp;
 704         return len;
 705     #else
 706         /*
 707          * For everything else we have a decent conformint vsnprintf that
 708          * returns the number of bytes needed.  We give it a try though on
 709          * a short buffer, since efficently speaking, it could be nice to
 710          * above a second vsnprintf call.
 711          */
 712         char    buf[128];
 713         va_list cpy;
 714         va_copy(cpy, args);
 715         len = vsnprintf(buf, sizeof(buf), fmt, cpy);
 716         va_end (cpy);
 717
 718         if (len < (int)sizeof(buf)) {
 719             *dat = util_strdup(buf);
 720             return len;
 721         }
 722
 723         /* not large enough ... */
 724         tmp = (char*)mem_a(len + 1);
 725         if ((ret = vsnprintf(tmp, len + 1, fmt, args)) != len) {
 726             mem_d(tmp);
 727             *dat = NULL;
 728             return -1;
 729         }
 730
 731         *dat = tmp;
 732         return len;
 733     #endif
 734 }
 735 int util_asprintf(char **ret, const char *fmt, ...) {
 736     va_list  args;
 737     int      read;
 738     va_start(args, fmt);
 739     read = util_vasprintf(ret, fmt, args);
 740     va_end  (args);
 741
 742     return read;
 743 }
 744
 745 /*
 746  * Implementation of the Mersenne twister PRNG (pseudo random numer
 747  * generator).  Implementation of MT19937.  Has a period of 2^19937-1
 748  * which is a Mersenne Prime (hence the name).
 749  *
 750  * Implemented from specification and original paper:
 751  * http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf
 752  *
 753  * This code is placed in the public domain by me personally
 754  * (Dale Weiler, a.k.a graphitemaster).
 755  */
 756
 757 #define MT_SIZE    624
 758 #define MT_PERIOD  397
 759 #define MT_SPACE   (MT_SIZE - MT_PERIOD)
 760
 761 static uint32_t mt_state[MT_SIZE];
 762 static size_t   mt_index = 0;
 763
 764 static GMQCC_INLINE void mt_generate() {
 765     /*
 766      * The loop has been unrolled here: the original paper and implemenation
 767      * Called for the following code:
 768      * for (register unsigned i = 0; i < MT_SIZE; ++i) {
 769      *     register uint32_t load;
 770      *     load  = (0x80000000 & mt_state[i])                 // most  significant 32nd bit
 771      *     load |= (0x7FFFFFFF & mt_state[(i + 1) % MT_SIZE]) // least significant 31nd bit
 772      *
 773      *     mt_state[i] = mt_state[(i + MT_PERIOD) % MT_SIZE] ^ (load >> 1);
 774      *
 775      *     if (load & 1) mt_state[i] ^= 0x9908B0DF;
 776      * }
 777      *
 778      * This essentially is a waste: we have two modulus operations, and
 779      * a branch that is executed every iteration from [0, MT_SIZE).
 780      *
 781      * Please see: http://www.quadibloc.com/crypto/co4814.htm for more
 782      * information on how this clever trick works.
 783      */
 784     static const uint32_t matrix[2] = {
 785         0x00000000,
 786         0x9908B0Df
 787     };
 788     /*
 789      * This register gives up a little more speed by instructing the compiler
 790      * to force these into CPU registers (they're counters for indexing mt_state
 791      * which we can force the compiler to generate prefetch instructions for)
 792      */
 793     register uint32_t y;
 794     register uint32_t i;
 795
 796     /*
 797      * Said loop has been unrolled for MT_SPACE (226 iterations), opposed
 798      * to [0, MT_SIZE)  (634 iterations).
 799      */
 800     for (i = 0; i < MT_SPACE; ++i) {
 801         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
 802         mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1];
 803
 804         i ++; /* loop unroll */
 805
 806         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
 807         mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1];
 808     }
 809
 810     /*
 811      * collapsing the walls unrolled (evenly dividing 396 [632-227 = 396
 812      * = 2*2*3*3*11])
 813      */
 814     i = MT_SPACE;
 815     while (i < MT_SIZE - 1) {
 816         /*
 817          * We expand this 11 times .. manually, no macros are required
 818          * here. This all fits in the CPU cache.
 819          */
 820         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 821         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 822         ++i;
 823         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 824         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 825         ++i;
 826         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 827         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 828         ++i;
 829         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 830         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 831         ++i;
 832         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 833         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 834         ++i;
 835         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 836         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 837         ++i;
 838         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 839         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 840         ++i;
 841         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 842         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 843         ++i;
 844         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 845         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 846         ++i;
 847         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 848         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 849         ++i;
 850         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 851         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 852         ++i;
 853     }
 854
 855     /* i = mt_state[623] */
 856     y                     = (0x80000000 & mt_state[MT_SIZE - 1]) | (0x7FFFFFFF & mt_state[MT_SIZE - 1]);
 857     mt_state[MT_SIZE - 1] = mt_state[MT_PERIOD - 1] ^ (y >> 1) ^ matrix[y & 1];
 858 }
 859
 860 void util_seed(uint32_t value) {
 861     /*
 862      * We seed the mt_state with a LCG (linear congruential generator)
 863      * We're operating exactly on exactly m=32, so there is no need to
 864      * use modulus.
 865      *
 866      * The multipler of choice is 0x6C07865, also knows as the Borosh-
 867      * Niederreiter multipler used for modulus 2^32.  More can be read
 868      * about this in Knuth's TAOCP Volume 2, page 106.
 869      *
 870      * If you don't own TAOCP something is wrong with you :-) .. so I
 871      * also provided a link to the original paper by Borosh and
 872      * Niederreiter.  It's called "Optional Multipliers for PRNG by The
 873      * Linear Congruential Method" (1983).
 874      * http://en.wikipedia.org/wiki/Linear_congruential_generator
 875      *
 876      * From said page, it says the following:
 877      * "A common Mersenne twister implementation, interestingly enough
 878      *  used an LCG to generate seed data."
 879      *
 880      * Remarks:
 881      * The data we're operating on is 32-bits for the mt_state array, so
 882      * there is no masking required with 0xFFFFFFFF
 883      */
 884     register size_t i;
 885
 886     mt_state[0] = value;
 887     for (i = 1; i < MT_SIZE; ++i)
 888         mt_state[i] = 0x6C078965 * (mt_state[i - 1] ^ mt_state[i - 1] >> 30) + i;
 889 }
 890
 891 uint32_t util_rand() {
 892     register uint32_t y;
 893
 894     /*
 895      * This is inlined with any sane compiler (I checked)
 896      * for some reason though, SubC seems to be generating invalid
 897      * code when it inlines this.
 898      */
 899     if (!mt_index)
 900         mt_generate();
 901
 902     y = mt_state[mt_index];
 903
 904     /* Standard tempering */
 905     y ^= y >> 11;              /* +7 */
 906     y ^= y << 7  & 0x9D2C5680; /* +4 */
 907     y ^= y << 15 & 0xEFC60000; /* -4 */
 908     y ^= y >> 18;              /* -7 */
 909
 910     if(++mt_index == MT_SIZE)
 911          mt_index = 0;
 912
 913     return y;
 914 }