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