util.c

   1 /*
   2  * Copyright (C) 2012
   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 = 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 = 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 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 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 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     size_t m = *a ? 2*_vec_beg(*a)+i : i+1;
 370     void  *p = mem_r((*a ? _vec_raw(*a) : NULL), s * m + sizeof(size_t)*2);
 371     if (!*a)
 372         ((size_t*)p)[1] = 0;
 373     *a = (void*)((size_t*)p + 2);
 374     _vec_beg(*a) = m;
 375 }
 376
 377 /*
 378  * Hash table for generic data, based on dynamic memory allocations
 379  * all around.  This is the internal interface, please look for
 380  * EXPOSED INTERFACE comment below
 381  */
 382 typedef struct hash_node_t {
 383     char               *key;   /* the key for this node in table */
 384     void               *value; /* pointer to the data as void*   */
 385     struct hash_node_t *next;  /* next node (linked list)        */
 386 } hash_node_t;
 387
 388 GMQCC_INLINE size_t util_hthash(hash_table_t *ht, const char *key) {
 389     const uint32_t       mix   = 0x5BD1E995;
 390     const uint32_t       rot   = 24;
 391     size_t               size  = strlen(key);
 392     uint32_t             hash  = 0x1EF0 /* LICRC TAB */  ^ size;
 393     uint32_t             alias = 0;
 394     const unsigned char *data  = (const unsigned char*)key;
 395
 396     while (size >= 4) {
 397         alias = *(uint32_t*)data;
 398
 399         alias *= mix;
 400         alias ^= alias >> rot;
 401         alias *= mix;
 402
 403         hash  *= mix;
 404         hash  ^= alias;
 405
 406         data += 4;
 407         size -= 4;
 408     }
 409
 410     switch (size) {
 411         case 3: hash ^= data[2] << 16;
 412         case 2: hash ^= data[1] << 8;
 413         case 1: hash ^= data[0];
 414                 hash *= mix;
 415     }
 416
 417     hash ^= hash >> 13;
 418     hash *= mix;
 419     hash ^= hash >> 15;
 420
 421     return (size_t) (hash % ht->size);
 422 }
 423
 424 hash_node_t *_util_htnewpair(const char *key, void *value) {
 425     hash_node_t *node;
 426     if (!(node = mem_a(sizeof(hash_node_t))))
 427         return NULL;
 428
 429     if (!(node->key = util_strdup(key))) {
 430         mem_d(node);
 431         return NULL;
 432     }
 433
 434     node->value = value;
 435     node->next  = NULL;
 436
 437     return node;
 438 }
 439
 440 /*
 441  * EXPOSED INTERFACE for the hashtable implementation
 442  * util_htnew(size)                             -- to make a new hashtable
 443  * util_htset(table, key, value, sizeof(value)) -- to set something in the table
 444  * util_htget(table, key)                       -- to get something from the table
 445  * util_htdel(table)                            -- to delete the table
 446  */
 447 hash_table_t *util_htnew(size_t size) {
 448     hash_table_t *hashtable = NULL;
 449     if (size < 1)
 450         return NULL;
 451
 452     if (!(hashtable = mem_a(sizeof(hash_table_t))))
 453         return NULL;
 454
 455     if (!(hashtable->table = mem_a(sizeof(hash_node_t*) * size))) {
 456         mem_d(hashtable);
 457         return NULL;
 458     }
 459
 460     hashtable->size = size;
 461     memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
 462
 463     return hashtable;
 464 }
 465
 466 void util_htseth(hash_table_t *ht, const char *key, size_t bin, void *value) {
 467     hash_node_t *newnode = NULL;
 468     hash_node_t *next    = NULL;
 469     hash_node_t *last    = NULL;
 470
 471     next = ht->table[bin];
 472
 473     while (next && next->key && strcmp(key, next->key) > 0)
 474         last = next, next = next->next;
 475
 476     /* already in table, do a replace */
 477     if (next && next->key && strcmp(key, next->key) == 0) {
 478         next->value = value;
 479     } else {
 480         /* not found, grow a pair man :P */
 481         newnode = _util_htnewpair(key, value);
 482         if (next == ht->table[bin]) {
 483             newnode->next  = next;
 484             ht->table[bin] = newnode;
 485         } else if (!next) {
 486             last->next = newnode;
 487         } else {
 488             newnode->next = next;
 489             last->next = newnode;
 490         }
 491     }
 492 }
 493
 494 void util_htset(hash_table_t *ht, const char *key, void *value) {
 495     util_htseth(ht, key, util_hthash(ht, key), value);
 496 }
 497
 498 void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
 499     hash_node_t *pair = ht->table[bin];
 500
 501     while (pair && pair->key && strcmp(key, pair->key) > 0)
 502         pair = pair->next;
 503
 504     if (!pair || !pair->key || strcmp(key, pair->key) != 0)
 505         return NULL;
 506
 507     return pair->value;
 508 }
 509
 510 void *util_htget(hash_table_t *ht, const char *key) {
 511     return util_htgeth(ht, key, util_hthash(ht, key));
 512 }
 513
 514 /*
 515  * Free all allocated data in a hashtable, this is quite the amount
 516  * of work.
 517  */
 518 void util_htdel(hash_table_t *ht) {
 519     size_t i = 0;
 520     for (; i < ht->size; i++) {
 521         hash_node_t *n = ht->table[i];
 522         hash_node_t *p;
 523
 524         /* free in list */
 525         while (n) {
 526             if (n->key)
 527                 mem_d(n->key);
 528             p = n;
 529             n = n->next;
 530             mem_d(p);
 531         }
 532
 533     }
 534     /* free table */
 535     mem_d(ht->table);
 536     mem_d(ht);
 537 }