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