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
 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  = (data[0] | (data[1] << 8) | (data[2] << 16) | (data[3] << 24));
 469         alias *= mix;
 470         alias ^= alias >> rot;
 471         alias *= mix;
 472
 473         hash  *= mix;
 474         hash  ^= alias;
 475
 476         data += 4;
 477         size -= 4;
 478     }
 479
 480     switch (size) {
 481         case 3: hash ^= data[2] << 16;
 482         case 2: hash ^= data[1] << 8;
 483         case 1: hash ^= data[0];
 484                 hash *= mix;
 485     }
 486
 487     hash ^= hash >> 13;
 488     hash *= mix;
 489     hash ^= hash >> 15;
 490
 491     return (size_t) (hash % ht->size);
 492 }
 493
 494 hash_node_t *_util_htnewpair(const char *key, void *value) {
 495     hash_node_t *node;
 496     if (!(node = (hash_node_t*)mem_a(sizeof(hash_node_t))))
 497         return NULL;
 498
 499     if (!(node->key = util_strdupe(key))) {
 500         mem_d(node);
 501         return NULL;
 502     }
 503
 504     node->value = value;
 505     node->next  = NULL;
 506
 507     return node;
 508 }
 509
 510 /*
 511  * EXPOSED INTERFACE for the hashtable implementation
 512  * util_htnew(size)                             -- to make a new hashtable
 513  * util_htset(table, key, value, sizeof(value)) -- to set something in the table
 514  * util_htget(table, key)                       -- to get something from the table
 515  * util_htdel(table)                            -- to delete the table
 516  */
 517 hash_table_t *util_htnew(size_t size) {
 518     hash_table_t *hashtable = NULL;
 519     if (size < 1)
 520         return NULL;
 521
 522     if (!(hashtable = (hash_table_t*)mem_a(sizeof(hash_table_t))))
 523         return NULL;
 524
 525     if (!(hashtable->table = (hash_node_t**)mem_a(sizeof(hash_node_t*) * size))) {
 526         mem_d(hashtable);
 527         return NULL;
 528     }
 529
 530     hashtable->size = size;
 531     memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
 532
 533     return hashtable;
 534 }
 535
 536 void util_htseth(hash_table_t *ht, const char *key, size_t bin, void *value) {
 537     hash_node_t *newnode = NULL;
 538     hash_node_t *next    = NULL;
 539     hash_node_t *last    = NULL;
 540
 541     next = ht->table[bin];
 542
 543     while (next && next->key && strcmp(key, next->key) > 0)
 544         last = next, next = next->next;
 545
 546     /* already in table, do a replace */
 547     if (next && next->key && strcmp(key, next->key) == 0) {
 548         next->value = value;
 549     } else {
 550         /* not found, grow a pair man :P */
 551         newnode = _util_htnewpair(key, value);
 552         if (next == ht->table[bin]) {
 553             newnode->next  = next;
 554             ht->table[bin] = newnode;
 555         } else if (!next) {
 556             last->next = newnode;
 557         } else {
 558             newnode->next = next;
 559             last->next = newnode;
 560         }
 561     }
 562 }
 563
 564 void util_htset(hash_table_t *ht, const char *key, void *value) {
 565     util_htseth(ht, key, util_hthash(ht, key), value);
 566 }
 567
 568 void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
 569     hash_node_t *pair = ht->table[bin];
 570
 571     while (pair && pair->key && strcmp(key, pair->key) > 0)
 572         pair = pair->next;
 573
 574     if (!pair || !pair->key || strcmp(key, pair->key) != 0)
 575         return NULL;
 576
 577     return pair->value;
 578 }
 579
 580 void *util_htget(hash_table_t *ht, const char *key) {
 581     return util_htgeth(ht, key, util_hthash(ht, key));
 582 }
 583
 584 void *code_util_str_htgeth(hash_table_t *ht, const char *key, size_t bin) {
 585     hash_node_t *pair;
 586     size_t len, keylen;
 587     int cmp;
 588
 589     keylen = strlen(key);
 590
 591     pair = ht->table[bin];
 592     while (pair && pair->key) {
 593         len = strlen(pair->key);
 594         if (len < keylen) {
 595             pair = pair->next;
 596             continue;
 597         }
 598         if (keylen == len) {
 599             cmp = strcmp(key, pair->key);
 600             if (cmp == 0)
 601                 return pair->value;
 602             if (cmp < 0)
 603                 return NULL;
 604             pair = pair->next;
 605             continue;
 606         }
 607         cmp = strcmp(key, pair->key + len - keylen);
 608         if (cmp == 0) {
 609             uintptr_t up = (uintptr_t)pair->value;
 610             up += len - keylen;
 611             return (void*)up;
 612         }
 613         pair = pair->next;
 614     }
 615     return NULL;
 616 }
 617
 618 /*
 619  * Free all allocated data in a hashtable, this is quite the amount
 620  * of work.
 621  */
 622 void util_htrem(hash_table_t *ht, void (*callback)(void *data)) {
 623     size_t i = 0;
 624     for (; i < ht->size; i++) {
 625         hash_node_t *n = ht->table[i];
 626         hash_node_t *p;
 627
 628         /* free in list */
 629         while (n) {
 630             if (n->key)
 631                 mem_d(n->key);
 632             if (callback)
 633                 callback(n->value);
 634             p = n;
 635             n = n->next;
 636             mem_d(p);
 637         }
 638
 639     }
 640     /* free table */
 641     mem_d(ht->table);
 642     mem_d(ht);
 643 }
 644
 645 void util_htrmh(hash_table_t *ht, const char *key, size_t bin, void (*cb)(void*)) {
 646     hash_node_t **pair = &ht->table[bin];
 647     hash_node_t *tmp;
 648
 649     while (*pair && (*pair)->key && strcmp(key, (*pair)->key) > 0)
 650         pair = &(*pair)->next;
 651
 652     tmp = *pair;
 653     if (!tmp || !tmp->key || strcmp(key, tmp->key) != 0)
 654         return;
 655
 656     if (cb)
 657         (*cb)(tmp->value);
 658
 659     *pair = tmp->next;
 660     mem_d(tmp->key);
 661     mem_d(tmp);
 662 }
 663
 664 void util_htrm(hash_table_t *ht, const char *key, void (*cb)(void*)) {
 665     util_htrmh(ht, key, util_hthash(ht, key), cb);
 666 }
 667
 668 void util_htdel(hash_table_t *ht) {
 669     util_htrem(ht, NULL);
 670 }
 671
 672 /*
 673  * Portable implementation of vasprintf/asprintf. Assumes vsnprintf
 674  * exists, otherwise compiler error.
 675  *
 676  * TODO: fix for MSVC ....
 677  */
 678 int util_vasprintf(char **dat, const char *fmt, va_list args) {
 679     int   ret;
 680     int   len;
 681     char *tmp = NULL;
 682
 683     /*
 684      * For visuals tido _vsnprintf doesn't tell you the length of a
 685      * formatted string if it overflows. However there is a MSVC
 686      * intrinsic (which is documented wrong) called _vcsprintf which
 687      * will return the required amount to allocate.
 688      */
 689     #ifdef _MSC_VER
 690         if ((len = _vscprintf(fmt, args)) < 0) {
 691             *dat = NULL;
 692             return -1;
 693         }
 694
 695         tmp = (char*)mem_a(len + 1);
 696         if ((ret = _vsnprintf_s(tmp, len+1, len+1, fmt, args)) != len) {
 697             mem_d(tmp);
 698             *dat = NULL;
 699             return -1;
 700         }
 701         *dat = tmp;
 702         return len;
 703     #else
 704         /*
 705          * For everything else we have a decent conformint vsnprintf that
 706          * returns the number of bytes needed.  We give it a try though on
 707          * a short buffer, since efficently speaking, it could be nice to
 708          * above a second vsnprintf call.
 709          */
 710         char    buf[128];
 711         va_list cpy;
 712         va_copy(cpy, args);
 713         len = vsnprintf(buf, sizeof(buf), fmt, cpy);
 714         va_end (cpy);
 715
 716         if (len < (int)sizeof(buf)) {
 717             *dat = util_strdup(buf);
 718             return len;
 719         }
 720
 721         /* not large enough ... */
 722         tmp = (char*)mem_a(len + 1);
 723         if ((ret = vsnprintf(tmp, len + 1, fmt, args)) != len) {
 724             mem_d(tmp);
 725             *dat = NULL;
 726             return -1;
 727         }
 728
 729         *dat = tmp;
 730         return len;
 731     #endif
 732 }
 733 int util_asprintf(char **ret, const char *fmt, ...) {
 734     va_list  args;
 735     int      read;
 736     va_start(args, fmt);
 737     read = util_vasprintf(ret, fmt, args);
 738     va_end  (args);
 739
 740     return read;
 741 }
 742
 743 /*
 744  * These are various re-implementations (wrapping the real ones) of
 745  * string functions that MSVC consideres unsafe. We wrap these up and
 746  * use the safe varations on MSVC.
 747  */
 748 #ifdef _MSC_VER
 749     static char **util_strerror_allocated() {
 750         static char **data = NULL;
 751         return data;
 752     }
 753
 754     static void util_strerror_cleanup(void) {
 755         size_t i;
 756         char  **data = util_strerror_allocated();
 757         for (i = 0; i < vec_size(data); i++)
 758             mem_d(data[i]);
 759         vec_free(data);
 760     }
 761
 762     const char *util_strerror(int num) {
 763         char         *allocated = NULL;
 764         static bool   install   = false;
 765         static size_t tries     = 0;
 766         char        **vector    = util_strerror_allocated();
 767
 768         /* try installing cleanup handler */
 769         while (!install) {
 770             if (tries == 32)
 771                 return "(unknown)";
 772
 773             install = !atexit(&util_strerror_cleanup);
 774             tries ++;
 775         }
 776
 777         allocated = (char*)mem_a(4096); /* A page must be enough */
 778         strerror_s(allocated, 4096, num);
 779
 780         vec_push(vector, allocated);
 781         return (const char *)allocated;
 782     }
 783
 784     int util_snprintf(char *src, size_t bytes, const char *format, ...) {
 785         int      rt;
 786         va_list  va;
 787         va_start(va, format);
 788
 789         rt = vsprintf_s(src, bytes, format, va);
 790         va_end  (va);
 791
 792         return rt;
 793     }
 794
 795     char *util_strcat(char *dest, const char *src) {
 796         strcat_s(dest, strlen(src), src);
 797         return dest;
 798     }
 799
 800     char *util_strncpy(char *dest, const char *src, size_t num) {
 801         strncpy_s(dest, num, src, num);
 802         return dest;
 803     }
 804 #else
 805     const char *util_strerror(int num) {
 806         return strerror(num);
 807     }
 808
 809     int util_snprintf(char *src, size_t bytes, const char *format, ...) {
 810         int      rt;
 811         va_list  va;
 812         va_start(va, format);
 813         rt = vsnprintf(src, bytes, format, va);
 814         va_end  (va);
 815
 816         return rt;
 817     }
 818
 819     char *util_strcat(char *dest, const char *src) {
 820         return strcat(dest, src);
 821     }
 822
 823     char *util_strncpy(char *dest, const char *src, size_t num) {
 824         return strncpy(dest, src, num);
 825     }
 826
 827 #endif /*! _MSC_VER */
 828
 829 /*
 830  * Implementation of the Mersenne twister PRNG (pseudo random numer
 831  * generator).  Implementation of MT19937.  Has a period of 2^19937-1
 832  * which is a Mersenne Prime (hence the name).
 833  *
 834  * Implemented from specification and original paper:
 835  * http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf
 836  *
 837  * This code is placed in the public domain by me personally
 838  * (Dale Weiler, a.k.a graphitemaster).
 839  */
 840
 841 #define MT_SIZE    624
 842 #define MT_PERIOD  397
 843 #define MT_SPACE   (MT_SIZE - MT_PERIOD)
 844
 845 static uint32_t mt_state[MT_SIZE];
 846 static size_t   mt_index = 0;
 847
 848 static GMQCC_INLINE void mt_generate() {
 849     /*
 850      * The loop has been unrolled here: the original paper and implemenation
 851      * Called for the following code:
 852      * for (register unsigned i = 0; i < MT_SIZE; ++i) {
 853      *     register uint32_t load;
 854      *     load  = (0x80000000 & mt_state[i])                 // most  significant 32nd bit
 855      *     load |= (0x7FFFFFFF & mt_state[(i + 1) % MT_SIZE]) // least significant 31nd bit
 856      *
 857      *     mt_state[i] = mt_state[(i + MT_PERIOD) % MT_SIZE] ^ (load >> 1);
 858      *
 859      *     if (load & 1) mt_state[i] ^= 0x9908B0DF;
 860      * }
 861      *
 862      * This essentially is a waste: we have two modulus operations, and
 863      * a branch that is executed every iteration from [0, MT_SIZE).
 864      *
 865      * Please see: http://www.quadibloc.com/crypto/co4814.htm for more
 866      * information on how this clever trick works.
 867      */
 868     static const uint32_t matrix[2] = {
 869         0x00000000,
 870         0x9908B0Df
 871     };
 872     /*
 873      * This register gives up a little more speed by instructing the compiler
 874      * to force these into CPU registers (they're counters for indexing mt_state
 875      * which we can force the compiler to generate prefetch instructions for)
 876      */
 877     register uint32_t y;
 878     register uint32_t i;
 879
 880     /*
 881      * Said loop has been unrolled for MT_SPACE (226 iterations), opposed
 882      * to [0, MT_SIZE)  (634 iterations).
 883      */
 884     for (i = 0; i < MT_SPACE; ++i) {
 885         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
 886         mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1];
 887
 888         i ++; /* loop unroll */
 889
 890         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
 891         mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1];
 892     }
 893
 894     /*
 895      * collapsing the walls unrolled (evenly dividing 396 [632-227 = 396
 896      * = 2*2*3*3*11])
 897      */
 898     i = MT_SPACE;
 899     while (i < MT_SIZE - 1) {
 900         /*
 901          * We expand this 11 times .. manually, no macros are required
 902          * here. This all fits in the CPU cache.
 903          */
 904         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 905         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 906         ++i;
 907         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 908         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 909         ++i;
 910         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 911         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 912         ++i;
 913         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 914         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 915         ++i;
 916         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 917         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 918         ++i;
 919         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 920         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 921         ++i;
 922         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 923         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 924         ++i;
 925         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 926         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 927         ++i;
 928         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 929         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 930         ++i;
 931         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 932         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 933         ++i;
 934         y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
 935         mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
 936         ++i;
 937     }
 938
 939     /* i = mt_state[623] */
 940     y                     = (0x80000000 & mt_state[MT_SIZE - 1]) | (0x7FFFFFFF & mt_state[MT_SIZE - 1]);
 941     mt_state[MT_SIZE - 1] = mt_state[MT_PERIOD - 1] ^ (y >> 1) ^ matrix[y & 1];
 942 }
 943
 944 void util_seed(uint32_t value) {
 945     /*
 946      * We seed the mt_state with a LCG (linear congruential generator)
 947      * We're operating exactly on exactly m=32, so there is no need to
 948      * use modulus.
 949      *
 950      * The multipler of choice is 0x6C07865, also knows as the Borosh-
 951      * Niederreiter multipler used for modulus 2^32.  More can be read
 952      * about this in Knuth's TAOCP Volume 2, page 106.
 953      *
 954      * If you don't own TAOCP something is wrong with you :-) .. so I
 955      * also provided a link to the original paper by Borosh and
 956      * Niederreiter.  It's called "Optional Multipliers for PRNG by The
 957      * Linear Congruential Method" (1983).
 958      * http://en.wikipedia.org/wiki/Linear_congruential_generator
 959      *
 960      * From said page, it says the following:
 961      * "A common Mersenne twister implementation, interestingly enough
 962      *  used an LCG to generate seed data."
 963      *
 964      * Remarks:
 965      * The data we're operating on is 32-bits for the mt_state array, so
 966      * there is no masking required with 0xFFFFFFFF
 967      */
 968     register size_t i;
 969
 970     mt_state[0] = value;
 971     for (i = 1; i < MT_SIZE; ++i)
 972         mt_state[i] = 0x6C078965 * (mt_state[i - 1] ^ mt_state[i - 1] >> 30) + i;
 973 }
 974
 975 uint32_t util_rand() {
 976     register uint32_t y;
 977
 978     /*
 979      * This is inlined with any sane compiler (I checked)
 980      * for some reason though, SubC seems to be generating invalid
 981      * code when it inlines this.
 982      */
 983     if (!mt_index)
 984         mt_generate();
 985
 986     y = mt_state[mt_index];
 987
 988     /* Standard tempering */
 989     y ^= y >> 11;              /* +7 */
 990     y ^= y << 7  & 0x9D2C5680; /* +4 */
 991     y ^= y << 15 & 0xEFC60000; /* -4 */
 992     y ^= y >> 18;              /* -7 */
 993
 994     if(++mt_index == MT_SIZE)
 995          mt_index = 0;
 996
 997     return y;
 998 }