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