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 uint64_t mem_ab = 0;
  29 uint64_t mem_db = 0;
  30 uint64_t mem_at = 0;
  31 uint64_t mem_dt = 0;
  32
  33 struct memblock_t {
  34     const char  *file;
  35     unsigned int line;
  36     size_t       byte;
  37     struct memblock_t *next;
  38     struct memblock_t *prev;
  39 };
  40
  41 static struct memblock_t *mem_start = NULL;
  42
  43 void *util_memory_a(size_t byte, unsigned int line, const char *file) {
  44     struct memblock_t *info = malloc(sizeof(struct memblock_t) + byte);
  45     void              *data = (void*)(info+1);
  46     if (!info) return NULL;
  47     info->line = line;
  48     info->byte = byte;
  49     info->file = file;
  50     info->prev = NULL;
  51     info->next = mem_start;
  52     if (mem_start)
  53         mem_start->prev = info;
  54     mem_start = info;
  55
  56     util_debug("MEM", "allocation:   % 8u (bytes) address 0x%08X @ %s:%u\n", byte, data, file, line);
  57     mem_at++;
  58     mem_ab += info->byte;
  59
  60     return data;
  61 }
  62
  63 void util_memory_d(void *ptrn, unsigned int line, const char *file) {
  64     struct memblock_t *info = NULL;
  65
  66     if (!ptrn) return;
  67     info = ((struct memblock_t*)ptrn - 1);
  68
  69     util_debug("MEM", "released:     % 8u (bytes) address 0x%08X @ %s:%u\n", info->byte, ptrn, file, line);
  70     mem_db += info->byte;
  71     mem_dt++;
  72
  73     if (info->prev)
  74         info->prev->next = info->next;
  75     if (info->next)
  76         info->next->prev = info->prev;
  77     if (info == mem_start)
  78         mem_start = info->next;
  79
  80     free(info);
  81 }
  82
  83 void *util_memory_r(void *ptrn, size_t byte, unsigned int line, const char *file) {
  84     struct memblock_t *oldinfo = NULL;
  85
  86     struct memblock_t *newinfo;
  87
  88     if (!ptrn)
  89         return util_memory_a(byte, line, file);
  90     if (!byte) {
  91         util_memory_d(ptrn, line, file);
  92         return NULL;
  93     }
  94
  95     oldinfo = ((struct memblock_t*)ptrn - 1);
  96     newinfo = ((struct memblock_t*)malloc(sizeof(struct memblock_t) + byte));
  97
  98     util_debug("MEM", "reallocation: % 8u -> %u (bytes) address 0x%08X -> 0x%08X @ %s:%u\n", oldinfo->byte, byte, ptrn, (void*)(newinfo+1), file, line);
  99
 100     /* new data */
 101     if (!newinfo) {
 102         util_memory_d(oldinfo+1, line, file);
 103         return NULL;
 104     }
 105
 106     /* copy old */
 107     memcpy(newinfo+1, oldinfo+1, oldinfo->byte);
 108
 109     /* free old */
 110     if (oldinfo->prev)
 111         oldinfo->prev->next = oldinfo->next;
 112     if (oldinfo->next)
 113         oldinfo->next->prev = oldinfo->prev;
 114     if (oldinfo == mem_start)
 115         mem_start = oldinfo->next;
 116
 117     /* fill info */
 118     newinfo->line = line;
 119     newinfo->byte = byte;
 120     newinfo->file = file;
 121     newinfo->prev = NULL;
 122     newinfo->next = mem_start;
 123     if (mem_start)
 124         mem_start->prev = newinfo;
 125     mem_start = newinfo;
 126
 127     mem_ab -= oldinfo->byte;
 128     mem_ab += newinfo->byte;
 129
 130     free(oldinfo);
 131
 132     return newinfo+1;
 133 }
 134
 135 void util_meminfo() {
 136     struct memblock_t *info;
 137
 138     if (!opts.memchk)
 139         return;
 140
 141     for (info = mem_start; info; info = info->next) {
 142         util_debug("MEM", "lost:       % 8u (bytes) at %s:%u\n",
 143             info->byte,
 144             info->file,
 145             info->line);
 146     }
 147
 148     util_debug("MEM", "Memory information:\n\
 149         Total allocations:   %llu\n\
 150         Total deallocations: %llu\n\
 151         Total allocated:     %llu (bytes)\n\
 152         Total deallocated:   %llu (bytes)\n\
 153         Leaks found:         lost %llu (bytes) in %d allocations\n",
 154             mem_at,   mem_dt,
 155             mem_ab,   mem_db,
 156            (mem_ab -  mem_db),
 157            (mem_at -  mem_dt)
 158     );
 159 }
 160
 161 /*
 162  * Some string utility functions, because strdup uses malloc, and we want
 163  * to track all memory (without replacing malloc).
 164  */
 165 char *util_strdup(const char *s) {
 166     size_t  len = 0;
 167     char   *ptr = NULL;
 168
 169     if (!s)
 170         return NULL;
 171
 172     if ((len = strlen(s)) && (ptr = mem_a(len+1))) {
 173         memcpy(ptr, s, len);
 174         ptr[len] = '\0';
 175     }
 176     return ptr;
 177 }
 178
 179 void util_debug(const char *area, const char *ms, ...) {
 180     va_list  va;
 181     if (!opts.debug)
 182         return;
 183
 184     if (!strcmp(area, "MEM") && !opts.memchk)
 185         return;
 186
 187     va_start(va, ms);
 188     con_out ("[%s] ", area);
 189     con_vout(ms, va);
 190     va_end  (va);
 191 }
 192
 193 /*
 194  * only required if big endian .. otherwise no need to swap
 195  * data.
 196  */
 197 #if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_BIG
 198     static void util_swap16(uint16_t *d, size_t l) {
 199         while (l--) {
 200             d[l] = (d[l] << 8) | (d[l] >> 8);
 201         }
 202     }
 203
 204     static void util_swap32(uint32_t *d, size_t l) {
 205         while (l--) {
 206             uint32_t v;
 207             v = ((d[l] << 8) & 0xFF00FF00) | ((d[l] >> 8) & 0x00FF00FF);
 208             d[l] = (v << 16) | (v >> 16);
 209         }
 210     }
 211
 212     /* Some strange system doesn't like constants that big, AND doesn't recognize an ULL suffix
 213      * so let's go the safe way
 214      */
 215     static void util_swap64(uint32_t *d, size_t l) {
 216         /*
 217         while (l--) {
 218             uint64_t v;
 219             v = ((d[l] << 8) & 0xFF00FF00FF00FF00) | ((d[l] >> 8) & 0x00FF00FF00FF00FF);
 220             v = ((v << 16) & 0xFFFF0000FFFF0000) | ((v >> 16) & 0x0000FFFF0000FFFF);
 221             d[l] = (v << 32) | (v >> 32);
 222         }
 223         */
 224         size_t i;
 225         for (i = 0; i < l; i += 2) {
 226             uint32_t v1 = d[i];
 227             d[i] = d[i+1];
 228             d[i+1] = v1;
 229             util_swap32(d+i, 2);
 230         }
 231     }
 232 #endif
 233
 234 void util_endianswap(void *_data, size_t length, unsigned int typesize) {
 235 #   if PLATFORM_BYTE_ORDER == -1 /* runtime check */
 236     if (*((char*)&typesize))
 237         return;
 238 #else
 239     /* prevent unused warnings */
 240     (void) _data;
 241     (void) length;
 242     (void) typesize;
 243
 244 #   if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_LITTLE
 245         return;
 246 #   else
 247         switch (typesize) {
 248             case 1: return;
 249             case 2:
 250                 util_swap16((uint16_t*)_data, length>>1);
 251                 return;
 252             case 4:
 253                 util_swap32((uint32_t*)_data, length>>2);
 254                 return;
 255             case 8:
 256                 util_swap64((uint32_t*)_data, length>>3);
 257                 return;
 258
 259             default: abort(); /* please blow the fuck up! */
 260         }
 261 #   endif
 262 #endif
 263 }
 264
 265 /*
 266  * CRC algorithms vary in the width of the polynomial, the value of said polynomial,
 267  * the initial value used for the register, weather the bits of each byte are reflected
 268  * before being processed, weather the algorithm itself feeds input bytes through the
 269  * register or XORs them with a byte from one end and then straight into the table, as
 270  * well as (but not limited to the idea of reflected versions) where the final register
 271  * value becomes reversed, and finally weather the value itself is used to XOR the final
 272  * register value.  AS such you can already imagine how painfully annoying CRCs are,
 273  * of course we stand to target Quake, which expects it's certian set of rules for proper
 274  * calculation of a CRC.
 275  *
 276  * In most traditional CRC algorithms on uses a reflected table driven method where a value
 277  * or register is reflected if it's bits are swapped around it's center.  For example:
 278  * take the bits 0101 is the 4-bit reflection of 1010, and respectfully 0011 would be the
 279  * reflection of 1100. Quake however expects a NON-Reflected CRC on the output, but still
 280  * requires a final XOR on the values (0xFFFF and 0x0000) this is a standard CCITT CRC-16
 281  * which I respectfully as a programmer don't agree with.
 282  *
 283  * So now you know what we target, and why we target it, despite how unsettling it may seem
 284  * but those are what Quake seems to request.
 285  */
 286
 287 static const uint16_t util_crc16_table[] = {
 288     0x0000,     0x1021,     0x2042,     0x3063,     0x4084,     0x50A5,
 289     0x60C6,     0x70E7,     0x8108,     0x9129,     0xA14A,     0xB16B,
 290     0xC18C,     0xD1AD,     0xE1CE,     0xF1EF,     0x1231,     0x0210,
 291     0x3273,     0x2252,     0x52B5,     0x4294,     0x72F7,     0x62D6,
 292     0x9339,     0x8318,     0xB37B,     0xA35A,     0xD3BD,     0xC39C,
 293     0xF3FF,     0xE3DE,     0x2462,     0x3443,     0x0420,     0x1401,
 294     0x64E6,     0x74C7,     0x44A4,     0x5485,     0xA56A,     0xB54B,
 295     0x8528,     0x9509,     0xE5EE,     0xF5CF,     0xC5AC,     0xD58D,
 296     0x3653,     0x2672,     0x1611,     0x0630,     0x76D7,     0x66F6,
 297     0x5695,     0x46B4,     0xB75B,     0xA77A,     0x9719,     0x8738,
 298     0xF7DF,     0xE7FE,     0xD79D,     0xC7BC,     0x48C4,     0x58E5,
 299     0x6886,     0x78A7,     0x0840,     0x1861,     0x2802,     0x3823,
 300     0xC9CC,     0xD9ED,     0xE98E,     0xF9AF,     0x8948,     0x9969,
 301     0xA90A,     0xB92B,     0x5AF5,     0x4AD4,     0x7AB7,     0x6A96,
 302     0x1A71,     0x0A50,     0x3A33,     0x2A12,     0xDBFD,     0xCBDC,
 303     0xFBBF,     0xEB9E,     0x9B79,     0x8B58,     0xBB3B,     0xAB1A,
 304     0x6CA6,     0x7C87,     0x4CE4,     0x5CC5,     0x2C22,     0x3C03,
 305     0x0C60,     0x1C41,     0xEDAE,     0xFD8F,     0xCDEC,     0xDDCD,
 306     0xAD2A,     0xBD0B,     0x8D68,     0x9D49,     0x7E97,     0x6EB6,
 307     0x5ED5,     0x4EF4,     0x3E13,     0x2E32,     0x1E51,     0x0E70,
 308     0xFF9F,     0xEFBE,     0xDFDD,     0xCFFC,     0xBF1B,     0xAF3A,
 309     0x9F59,     0x8F78,     0x9188,     0x81A9,     0xB1CA,     0xA1EB,
 310     0xD10C,     0xC12D,     0xF14E,     0xE16F,     0x1080,     0x00A1,
 311     0x30C2,     0x20E3,     0x5004,     0x4025,     0x7046,     0x6067,
 312     0x83B9,     0x9398,     0xA3FB,     0xB3DA,     0xC33D,     0xD31C,
 313     0xE37F,     0xF35E,     0x02B1,     0x1290,     0x22F3,     0x32D2,
 314     0x4235,     0x5214,     0x6277,     0x7256,     0xB5EA,     0xA5CB,
 315     0x95A8,     0x8589,     0xF56E,     0xE54F,     0xD52C,     0xC50D,
 316     0x34E2,     0x24C3,     0x14A0,     0x0481,     0x7466,     0x6447,
 317     0x5424,     0x4405,     0xA7DB,     0xB7FA,     0x8799,     0x97B8,
 318     0xE75F,     0xF77E,     0xC71D,     0xD73C,     0x26D3,     0x36F2,
 319     0x0691,     0x16B0,     0x6657,     0x7676,     0x4615,     0x5634,
 320     0xD94C,     0xC96D,     0xF90E,     0xE92F,     0x99C8,     0x89E9,
 321     0xB98A,     0xA9AB,     0x5844,     0x4865,     0x7806,     0x6827,
 322     0x18C0,     0x08E1,     0x3882,     0x28A3,     0xCB7D,     0xDB5C,
 323     0xEB3F,     0xFB1E,     0x8BF9,     0x9BD8,     0xABBB,     0xBB9A,
 324     0x4A75,     0x5A54,     0x6A37,     0x7A16,     0x0AF1,     0x1AD0,
 325     0x2AB3,     0x3A92,     0xFD2E,     0xED0F,     0xDD6C,     0xCD4D,
 326     0xBDAA,     0xAD8B,     0x9DE8,     0x8DC9,     0x7C26,     0x6C07,
 327     0x5C64,     0x4C45,     0x3CA2,     0x2C83,     0x1CE0,     0x0CC1,
 328     0xEF1F,     0xFF3E,     0xCF5D,     0xDF7C,     0xAF9B,     0xBFBA,
 329     0x8FD9,     0x9FF8,     0x6E17,     0x7E36,     0x4E55,     0x5E74,
 330     0x2E93,     0x3EB2,     0x0ED1,     0x1EF0
 331 };
 332
 333 /* Non - Reflected */
 334 uint16_t util_crc16(uint16_t current, const char *k, size_t len) {
 335     register uint16_t h = current;
 336     for (; len; --len, ++k)
 337         h = util_crc16_table[(h>>8)^((unsigned char)*k)]^(h<<8);
 338     return h;
 339 }
 340 /* Reflective Varation (for reference) */
 341 #if 0
 342 uint16_t util_crc16(const char *k, int len, const short clamp) {
 343     register uint16_t h= (uint16_t)0xFFFFFFFF;
 344     for (; len; --len, ++k)
 345         h = util_crc16_table[(h^((unsigned char)*k))&0xFF]^(h>>8);
 346     return (~h)%clamp;
 347 }
 348 #endif
 349
 350 /*
 351  * Implements libc getline for systems that don't have it, which is
 352  * assmed all.  This works the same as getline().
 353  */
 354 int util_getline(char **lineptr, size_t *n, FILE *stream) {
 355     int   chr;
 356     int   ret;
 357     char *pos;
 358
 359     if (!lineptr || !n || !stream)
 360         return -1;
 361     if (!*lineptr) {
 362         if (!(*lineptr = (char*)mem_a((*n=64))))
 363             return -1;
 364     }
 365
 366     chr = *n;
 367     pos = *lineptr;
 368
 369     for (;;) {
 370         int c = getc(stream);
 371
 372         if (chr < 2) {
 373             *n += (*n > 16) ? *n : 64;
 374             chr = *n + *lineptr - pos;
 375             if (!(*lineptr = (char*)mem_r(*lineptr,*n)))
 376                 return -1;
 377             pos = *n - chr + *lineptr;
 378         }
 379
 380         if (ferror(stream))
 381             return -1;
 382         if (c == EOF) {
 383             if (pos == *lineptr)
 384                 return -1;
 385             else
 386                 break;
 387         }
 388
 389         *pos++ = c;
 390         chr--;
 391         if (c == '\n')
 392             break;
 393     }
 394     *pos = '\0';
 395     return (ret = pos - *lineptr);
 396 }
 397
 398 size_t util_strtocmd(const char *in, char *out, size_t outsz) {
 399     size_t sz = 1;
 400     for (; *in && sz < outsz; ++in, ++out, ++sz)
 401         *out = (*in == '-') ? '_' : (isalpha(*in) && !isupper(*in)) ? *in + 'A' - 'a': *in;
 402     *out = 0;
 403     return sz-1;
 404 }
 405
 406 size_t util_strtononcmd(const char *in, char *out, size_t outsz) {
 407     size_t sz = 1;
 408     for (; *in && sz < outsz; ++in, ++out, ++sz)
 409         *out = (*in == '_') ? '-' : (isalpha(*in) && isupper(*in)) ? *in + 'a' - 'A' : *in;
 410     *out = 0;
 411     return sz-1;
 412 }
 413
 414
 415 FILE *util_fopen(const char *filename, const char *mode)
 416 {
 417 #ifdef _MSC_VER
 418     FILE *out;
 419     if (fopen_s(&out, filename, mode) != 0)
 420         return NULL;
 421     return out;
 422 #else
 423     return fopen(filename, mode);
 424 #endif
 425 }
 426
 427 void _util_vec_grow(void **a, size_t i, size_t s) {
 428     size_t m = *a ? 2*_vec_beg(*a)+i : i+1;
 429     void  *p = mem_r((*a ? _vec_raw(*a) : NULL), s * m + sizeof(size_t)*2);
 430     if (!*a)
 431         ((size_t*)p)[1] = 0;
 432     *a = (void*)((size_t*)p + 2);
 433     _vec_beg(*a) = m;
 434 }
 435
 436 /*
 437  * Hash table for generic data, based on dynamic memory allocations
 438  * all around.  This is the internal interface, please look for
 439  * EXPOSED INTERFACE comment below
 440  */
 441 typedef struct hash_node_t {
 442     char               *key;   /* the key for this node in table */
 443     void               *value; /* pointer to the data as void*   */
 444     struct hash_node_t *next;  /* next node (linked list)        */
 445 } hash_node_t;
 446
 447 GMQCC_INLINE size_t util_hthash(hash_table_t *ht, const char *key) {
 448     const uint32_t       mix   = 0x5BD1E995;
 449     const uint32_t       rot   = 24;
 450     size_t               size  = strlen(key);
 451     uint32_t             hash  = 0x1EF0 /* LICRC TAB */  ^ size;
 452     uint32_t             alias = 0;
 453     const unsigned char *data  = (const unsigned char*)key;
 454
 455     while (size >= 4) {
 456         alias = *(uint32_t*)data;
 457
 458         alias *= mix;
 459         alias ^= alias >> rot;
 460         alias *= mix;
 461
 462         hash  *= mix;
 463         hash  ^= alias;
 464
 465         data += 4;
 466         size -= 4;
 467     }
 468
 469     switch (size) {
 470         case 3: hash ^= data[2] << 16;
 471         case 2: hash ^= data[1] << 8;
 472         case 1: hash ^= data[0];
 473                 hash *= mix;
 474     }
 475
 476     hash ^= hash >> 13;
 477     hash *= mix;
 478     hash ^= hash >> 15;
 479
 480     return (size_t) (hash % ht->size);
 481 }
 482
 483 hash_node_t *_util_htnewpair(const char *key, void *value) {
 484     hash_node_t *node;
 485     if (!(node = mem_a(sizeof(hash_node_t))))
 486         return NULL;
 487
 488     if (!(node->key = util_strdup(key))) {
 489         mem_d(node);
 490         return NULL;
 491     }
 492
 493     node->value = value;
 494     node->next  = NULL;
 495
 496     return node;
 497 }
 498
 499 /*
 500  * EXPOSED INTERFACE for the hashtable implementation
 501  * util_htnew(size)                             -- to make a new hashtable
 502  * util_htset(table, key, value, sizeof(value)) -- to set something in the table
 503  * util_htget(table, key)                       -- to get something from the table
 504  * util_htdel(table)                            -- to delete the table
 505  */
 506 hash_table_t *util_htnew(size_t size) {
 507     hash_table_t *hashtable = NULL;
 508     if (size < 1)
 509         return NULL;
 510
 511     if (!(hashtable = mem_a(sizeof(hash_table_t))))
 512         return NULL;
 513
 514     if (!(hashtable->table = mem_a(sizeof(hash_node_t*) * size))) {
 515         mem_d(hashtable);
 516         return NULL;
 517     }
 518
 519     hashtable->size = size;
 520     memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
 521
 522     return hashtable;
 523 }
 524
 525 void util_htseth(hash_table_t *ht, const char *key, size_t bin, void *value) {
 526     hash_node_t *newnode = NULL;
 527     hash_node_t *next    = NULL;
 528     hash_node_t *last    = NULL;
 529
 530     next = ht->table[bin];
 531
 532     while (next && next->key && strcmp(key, next->key) > 0)
 533         last = next, next = next->next;
 534
 535     /* already in table, do a replace */
 536     if (next && next->key && strcmp(key, next->key) == 0) {
 537         next->value = value;
 538     } else {
 539         /* not found, grow a pair man :P */
 540         newnode = _util_htnewpair(key, value);
 541         if (next == ht->table[bin]) {
 542             newnode->next  = next;
 543             ht->table[bin] = newnode;
 544         } else if (!next) {
 545             last->next = newnode;
 546         } else {
 547             newnode->next = next;
 548             last->next = newnode;
 549         }
 550     }
 551 }
 552
 553 void util_htset(hash_table_t *ht, const char *key, void *value) {
 554     util_htseth(ht, key, util_hthash(ht, key), value);
 555 }
 556
 557 void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
 558     hash_node_t *pair = ht->table[bin];
 559
 560     while (pair && pair->key && strcmp(key, pair->key) > 0)
 561         pair = pair->next;
 562
 563     if (!pair || !pair->key || strcmp(key, pair->key) != 0)
 564         return NULL;
 565
 566     return pair->value;
 567 }
 568
 569 void *util_htget(hash_table_t *ht, const char *key) {
 570     return util_htgeth(ht, key, util_hthash(ht, key));
 571 }
 572
 573 /*
 574  * Free all allocated data in a hashtable, this is quite the amount
 575  * of work.
 576  */
 577 void util_htdel(hash_table_t *ht) {
 578     size_t i = 0;
 579     for (; i < ht->size; i++) {
 580         hash_node_t *n = ht->table[i];
 581         hash_node_t *p;
 582
 583         /* free in list */
 584         while (n) {
 585             if (n->key)
 586                 mem_d(n->key);
 587             p = n;
 588             n = n->next;
 589             mem_d(p);
 590         }
 591
 592     }
 593     /* free table */
 594     mem_d(ht->table);
 595     mem_d(ht);
 596 }