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 /*
 180  * Remove quotes from a string, escapes from \ in string
 181  * as well.  This function shouldn't be used to create a
 182  * char array that is later freed (it uses pointer arith)
 183  */
 184 char *util_strrq(const char *s) {
 185     char *dst = (char*)s;
 186     char *src = (char*)s;
 187     char  chr;
 188     while ((chr = *src++) != '\0') {
 189         if (chr == '\\') {
 190             *dst++ = chr;
 191             if ((chr = *src++) == '\0')
 192                 break;
 193             *dst++ = chr;
 194         } else if (chr != '"')
 195             *dst++ = chr;
 196     }
 197     *dst = '\0';
 198     return dst;
 199 }
 200
 201 /*
 202  * Chops a substring from an existing string by creating a
 203  * copy of it and null terminating it at the required position.
 204  */
 205 char *util_strchp(const char *s, const char *e) {
 206     const char *c = NULL;
 207     if (!s || !e)
 208         return NULL;
 209
 210     c = s;
 211     while (c != e)
 212         c++;
 213
 214     return util_strdup(s);
 215 }
 216
 217 /*
 218  * Returns true if string is all uppercase, otherwise
 219  * it returns false.
 220  */
 221 bool util_strupper(const char *str) {
 222     while (*str) {
 223         if(!isupper(*str))
 224             return false;
 225         str++;
 226     }
 227     return true;
 228 }
 229
 230 /*
 231  * Returns true if string is all digits, otherwise
 232  * it returns false.
 233  */
 234 bool util_strdigit(const char *str) {
 235     while (*str) {
 236         if(!isdigit(*str))
 237             return false;
 238         str++;
 239     }
 240     return true;
 241 }
 242
 243 bool util_strncmpexact(const char *src, const char *ned, size_t len) {
 244     return (!strncmp(src, ned, len) && !src[len]);
 245 }
 246
 247 void util_debug(const char *area, const char *ms, ...) {
 248     va_list  va;
 249     if (!opts.debug)
 250         return;
 251
 252     if (!strcmp(area, "MEM") && !opts.memchk)
 253         return;
 254
 255     va_start(va, ms);
 256     con_out ("[%s] ", area);
 257     con_vout(ms, va);
 258     va_end  (va);
 259 }
 260
 261 /*
 262  * Endianess swapping, all data must be stored little-endian.  This
 263  * reorders by stride and length, much nicer than other functions for
 264  * certian-sized types like short or int.
 265  */
 266 #if 0
 267 void util_endianswap(void *m, int s, int l) {
 268     size_t w = 0;
 269     size_t i = 0;
 270
 271     /* ignore if we're already LE */
 272     if(*((char *)&s))
 273         return;
 274
 275     for(; w < (size_t)l; w++) {
 276         for(;  i < (size_t)(s << 1); i++) {
 277             unsigned char *p = (unsigned char *)m+w*s;
 278             unsigned char  t = p[i];
 279             p[i]             = p[s-i-1];
 280             p[s-i-1]         = t;
 281         }
 282     }
 283 }
 284 #endif
 285
 286 /*
 287  * only required if big endian .. otherwise no need to swap
 288  * data.
 289  */
 290 #if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_BIG
 291     static void util_swap16(uint16_t *d, size_t l) {
 292         while (l--) {
 293             d[l] = (d[l] << 8) | (d[l] >> 8);
 294         }
 295     }
 296
 297     static void util_swap32(uint32_t *d, size_t l) {
 298         while (l--) {
 299             uint32_t v;
 300             v = ((d[l] << 8) & 0xFF00FF00) | ((d[l] >> 8) & 0x00FF00FF);
 301             d[l] = (v << 16) | (v >> 16);
 302         }
 303     }
 304
 305     /* Some strange system doesn't like constants that big, AND doesn't recognize an ULL suffix
 306      * so let's go the safe way
 307      */
 308     static void util_swap64(uint32_t *d, size_t l) {
 309         /*
 310         while (l--) {
 311             uint64_t v;
 312             v = ((d[l] << 8) & 0xFF00FF00FF00FF00) | ((d[l] >> 8) & 0x00FF00FF00FF00FF);
 313             v = ((v << 16) & 0xFFFF0000FFFF0000) | ((v >> 16) & 0x0000FFFF0000FFFF);
 314             d[l] = (v << 32) | (v >> 32);
 315         }
 316         */
 317         size_t i;
 318         for (i = 0; i < l; i += 2) {
 319             uint32_t v1 = d[i];
 320             d[i] = d[i+1];
 321             d[i+1] = v1;
 322             util_swap32(d+i, 2);
 323         }
 324     }
 325 #endif
 326
 327 void util_endianswap(void *_data, size_t length, unsigned int typesize) {
 328 #   if PLATFORM_BYTE_ORDER == -1 /* runtime check */
 329     if (*((char*)&typesize))
 330         return;
 331 #else
 332     /* prevent unused warnings */
 333     (void) _data;
 334     (void) length;
 335     (void) typesize;
 336
 337 #   if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_LITTLE
 338         return;
 339 #   else
 340         switch (typesize) {
 341             case 1: return;
 342             case 2:
 343                 util_swap16((uint16_t*)_data, length>>1);
 344                 return;
 345             case 4:
 346                 util_swap32((uint32_t*)_data, length>>2);
 347                 return;
 348             case 8:
 349                 util_swap64((uint32_t*)_data, length>>3);
 350                 return;
 351
 352             default: abort(); /* please blow the fuck up! */
 353         }
 354 #   endif
 355 #endif
 356 }
 357
 358 /*
 359  * CRC algorithms vary in the width of the polynomial, the value of said polynomial,
 360  * the initial value used for the register, weather the bits of each byte are reflected
 361  * before being processed, weather the algorithm itself feeds input bytes through the
 362  * register or XORs them with a byte from one end and then straight into the table, as
 363  * well as (but not limited to the idea of reflected versions) where the final register
 364  * value becomes reversed, and finally weather the value itself is used to XOR the final
 365  * register value.  AS such you can already imagine how painfully annoying CRCs are,
 366  * of course we stand to target Quake, which expects it's certian set of rules for proper
 367  * calculation of a CRC.
 368  *
 369  * In most traditional CRC algorithms on uses a reflected table driven method where a value
 370  * or register is reflected if it's bits are swapped around it's center.  For example:
 371  * take the bits 0101 is the 4-bit reflection of 1010, and respectfully 0011 would be the
 372  * reflection of 1100. Quakle however expects a NON-Reflected CRC on the output, but still
 373  * requires a final XOR on the values (0xFFFF and 0x0000) this is a standard CCITT CRC-16
 374  * which I respectfully as a programmer don't agree with.
 375  *
 376  * So now you know what we target, and why we target it, despite how unsettling it may seem
 377  * but those are what Quake seems to request.
 378  */
 379
 380 /*
 381  * This is an implementation of CRC32 & CRC16. The polynomials have been
 382  * offline computed for faster generation at the cost of larger code size.
 383  *
 384  * CRC32 Polynomial: 0xEDB88320
 385  * CRC16 Polynomial: 0x00001021
 386  */
 387 static const uint32_t util_crc32_table[] = {
 388     0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F,
 389     0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
 390     0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91, 0x1DB71064, 0x6AB020F2,
 391     0xF3B97148, 0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
 392     0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9,
 393     0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172,
 394     0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, 0x35B5A8FA, 0x42B2986C,
 395     0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59,
 396     0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423,
 397     0xCFBA9599, 0xB8BDA50F, 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
 398     0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 0x76DC4190, 0x01DB7106,
 399     0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433,
 400     0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D,
 401     0x91646C97, 0xE6635C01, 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E,
 402     0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950,
 403     0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65,
 404     0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7,
 405     0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0,
 406     0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C, 0x270241AA,
 407     0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
 408     0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81,
 409     0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A,
 410     0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683, 0xE3630B12, 0x94643B84,
 411     0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
 412     0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB,
 413     0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC,
 414     0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, 0xD6D6A3E8, 0xA1D1937E,
 415     0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
 416     0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55,
 417     0x316E8EEF, 0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
 418     0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 0xC5BA3BBE, 0xB2BD0B28,
 419     0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D,
 420     0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F,
 421     0x72076785, 0x05005713, 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38,
 422     0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242,
 423     0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777,
 424     0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69,
 425     0x616BFFD3, 0x166CCF45, 0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2,
 426     0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC,
 427     0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
 428     0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693,
 429     0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94,
 430     0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
 431 };
 432 static const uint16_t util_crc16_table[] = {
 433     0x0000,     0x1021,     0x2042,     0x3063,     0x4084,     0x50A5,
 434     0x60C6,     0x70E7,     0x8108,     0x9129,     0xA14A,     0xB16B,
 435     0xC18C,     0xD1AD,     0xE1CE,     0xF1EF,     0x1231,     0x0210,
 436     0x3273,     0x2252,     0x52B5,     0x4294,     0x72F7,     0x62D6,
 437     0x9339,     0x8318,     0xB37B,     0xA35A,     0xD3BD,     0xC39C,
 438     0xF3FF,     0xE3DE,     0x2462,     0x3443,     0x0420,     0x1401,
 439     0x64E6,     0x74C7,     0x44A4,     0x5485,     0xA56A,     0xB54B,
 440     0x8528,     0x9509,     0xE5EE,     0xF5CF,     0xC5AC,     0xD58D,
 441     0x3653,     0x2672,     0x1611,     0x0630,     0x76D7,     0x66F6,
 442     0x5695,     0x46B4,     0xB75B,     0xA77A,     0x9719,     0x8738,
 443     0xF7DF,     0xE7FE,     0xD79D,     0xC7BC,     0x48C4,     0x58E5,
 444     0x6886,     0x78A7,     0x0840,     0x1861,     0x2802,     0x3823,
 445     0xC9CC,     0xD9ED,     0xE98E,     0xF9AF,     0x8948,     0x9969,
 446     0xA90A,     0xB92B,     0x5AF5,     0x4AD4,     0x7AB7,     0x6A96,
 447     0x1A71,     0x0A50,     0x3A33,     0x2A12,     0xDBFD,     0xCBDC,
 448     0xFBBF,     0xEB9E,     0x9B79,     0x8B58,     0xBB3B,     0xAB1A,
 449     0x6CA6,     0x7C87,     0x4CE4,     0x5CC5,     0x2C22,     0x3C03,
 450     0x0C60,     0x1C41,     0xEDAE,     0xFD8F,     0xCDEC,     0xDDCD,
 451     0xAD2A,     0xBD0B,     0x8D68,     0x9D49,     0x7E97,     0x6EB6,
 452     0x5ED5,     0x4EF4,     0x3E13,     0x2E32,     0x1E51,     0x0E70,
 453     0xFF9F,     0xEFBE,     0xDFDD,     0xCFFC,     0xBF1B,     0xAF3A,
 454     0x9F59,     0x8F78,     0x9188,     0x81A9,     0xB1CA,     0xA1EB,
 455     0xD10C,     0xC12D,     0xF14E,     0xE16F,     0x1080,     0x00A1,
 456     0x30C2,     0x20E3,     0x5004,     0x4025,     0x7046,     0x6067,
 457     0x83B9,     0x9398,     0xA3FB,     0xB3DA,     0xC33D,     0xD31C,
 458     0xE37F,     0xF35E,     0x02B1,     0x1290,     0x22F3,     0x32D2,
 459     0x4235,     0x5214,     0x6277,     0x7256,     0xB5EA,     0xA5CB,
 460     0x95A8,     0x8589,     0xF56E,     0xE54F,     0xD52C,     0xC50D,
 461     0x34E2,     0x24C3,     0x14A0,     0x0481,     0x7466,     0x6447,
 462     0x5424,     0x4405,     0xA7DB,     0xB7FA,     0x8799,     0x97B8,
 463     0xE75F,     0xF77E,     0xC71D,     0xD73C,     0x26D3,     0x36F2,
 464     0x0691,     0x16B0,     0x6657,     0x7676,     0x4615,     0x5634,
 465     0xD94C,     0xC96D,     0xF90E,     0xE92F,     0x99C8,     0x89E9,
 466     0xB98A,     0xA9AB,     0x5844,     0x4865,     0x7806,     0x6827,
 467     0x18C0,     0x08E1,     0x3882,     0x28A3,     0xCB7D,     0xDB5C,
 468     0xEB3F,     0xFB1E,     0x8BF9,     0x9BD8,     0xABBB,     0xBB9A,
 469     0x4A75,     0x5A54,     0x6A37,     0x7A16,     0x0AF1,     0x1AD0,
 470     0x2AB3,     0x3A92,     0xFD2E,     0xED0F,     0xDD6C,     0xCD4D,
 471     0xBDAA,     0xAD8B,     0x9DE8,     0x8DC9,     0x7C26,     0x6C07,
 472     0x5C64,     0x4C45,     0x3CA2,     0x2C83,     0x1CE0,     0x0CC1,
 473     0xEF1F,     0xFF3E,     0xCF5D,     0xDF7C,     0xAF9B,     0xBFBA,
 474     0x8FD9,     0x9FF8,     0x6E17,     0x7E36,     0x4E55,     0x5E74,
 475     0x2E93,     0x3EB2,     0x0ED1,     0x1EF0
 476 };
 477
 478 /*
 479  * Implements a CRC function for X worth bits using (uint[X]_t)
 480  * as type. and util_crc[X]_table.
 481
 482  * Quake expects a non-reflective CRC.
 483  */
 484 #define CRC(X) \
 485 uint##X##_t util_crc##X(uint##X##_t current, const char *k, size_t len) {  \
 486     register uint##X##_t h= current;                                  \
 487     for (; len; --len, ++k)                                           \
 488         h = util_crc##X##_table[(h>>8)^((unsigned char)*k)]^(h<<8);   \
 489     return h;                                                         \
 490 }
 491 CRC(32)
 492 CRC(16)
 493 #undef CRC
 494 /*
 495 #define CRC(X) \
 496 uint##X##_t util_crc##X(const char *k, int len, const short clamp) {  \
 497     register uint##X##_t h= (uint##X##_t)0xFFFFFFFF;                  \
 498     for (; len; --len, ++k)                                           \
 499         h = util_crc##X##_table[(h^((unsigned char)*k))&0xFF]^(h>>8); \
 500     return (~h)%clamp;                                                \
 501 }
 502 */
 503
 504
 505 /*
 506  * Implements libc getline for systems that don't have it, which is
 507  * assmed all.  This works the same as getline().
 508  */
 509 int util_getline(char **lineptr, size_t *n, FILE *stream) {
 510     int   chr;
 511     int   ret;
 512     char *pos;
 513
 514     if (!lineptr || !n || !stream)
 515         return -1;
 516     if (!*lineptr) {
 517         if (!(*lineptr = (char*)mem_a((*n=64))))
 518             return -1;
 519     }
 520
 521     chr = *n;
 522     pos = *lineptr;
 523
 524     for (;;) {
 525         int c = getc(stream);
 526
 527         if (chr < 2) {
 528             *n += (*n > 16) ? *n : 64;
 529             chr = *n + *lineptr - pos;
 530             if (!(*lineptr = (char*)mem_r(*lineptr,*n)))
 531                 return -1;
 532             pos = *n - chr + *lineptr;
 533         }
 534
 535         if (ferror(stream))
 536             return -1;
 537         if (c == EOF) {
 538             if (pos == *lineptr)
 539                 return -1;
 540             else
 541                 break;
 542         }
 543
 544         *pos++ = c;
 545         chr--;
 546         if (c == '\n')
 547             break;
 548     }
 549     *pos = '\0';
 550     return (ret = pos - *lineptr);
 551 }
 552
 553 size_t util_strtocmd(const char *in, char *out, size_t outsz) {
 554     size_t sz = 1;
 555     for (; *in && sz < outsz; ++in, ++out, ++sz)
 556         *out = (*in == '-') ? '_' : (isalpha(*in) && !isupper(*in)) ? *in + 'A' - 'a': *in;
 557     *out = 0;
 558     return sz-1;
 559 }
 560
 561 size_t util_strtononcmd(const char *in, char *out, size_t outsz) {
 562     size_t sz = 1;
 563     for (; *in && sz < outsz; ++in, ++out, ++sz)
 564         *out = (*in == '_') ? '-' : (isalpha(*in) && isupper(*in)) ? *in + 'a' - 'A' : *in;
 565     *out = 0;
 566     return sz-1;
 567 }
 568
 569
 570 FILE *util_fopen(const char *filename, const char *mode)
 571 {
 572 #ifdef _MSC_VER
 573     FILE *out;
 574     if (fopen_s(&out, filename, mode) != 0)
 575         return NULL;
 576     return out;
 577 #else
 578     return fopen(filename, mode);
 579 #endif
 580 }
 581
 582 void _util_vec_grow(void **a, size_t i, size_t s) {
 583     size_t m = *a ? 2*_vec_beg(*a)+i : i+1;
 584     void  *p = mem_r((*a ? _vec_raw(*a) : NULL), s * m + sizeof(size_t)*2);
 585     if (!*a)
 586         ((size_t*)p)[1] = 0;
 587     *a = (void*)((size_t*)p + 2);
 588     _vec_beg(*a) = m;
 589 }
 590
 591 /*
 592  * Hash table for generic data, based on dynamic memory allocations
 593  * all around.  This is the internal interface, please look for
 594  * EXPOSED INTERFACE comment below
 595  */
 596 typedef struct hash_node_t {
 597     char               *key;   /* the key for this node in table */
 598     void               *value; /* pointer to the data as void*   */
 599     struct hash_node_t *next;  /* next node (linked list)        */
 600 } hash_node_t;
 601
 602 /*
 603  * x86 and x86_64 optimized murmur hash functions for the hashtable
 604  * we have individual implementations for optimal performance.
 605  *
 606  * Forced inlined as we wrap these up in the actual utility function
 607  * below.  These should be autovectorized by gcc.
 608  */
 609 #ifdef __x86_64__
 610 GMQCC_INLINE uint32_t util_hthashfunc(hash_table_t *ht, const char *key, size_t seed) {
 611     const uint64_t       mix   = 0xC6A4A7935BD1E995;
 612     const int            rot   = 47;
 613     size_t               size  = strlen(key);
 614     uint64_t             hash  = seed ^ (size - mix);
 615     uint64_t             alias = 0;
 616     const uint64_t      *beg   = (const uint64_t*)key;
 617     const uint64_t      *end   = beg + (size / 8);
 618     const unsigned char *final = NULL;
 619
 620     while (beg != end) {
 621         alias = *beg++;
 622
 623         alias *= mix;
 624         alias ^= alias >> rot;
 625         alias *= mix;
 626
 627         hash  ^= alias;
 628         hash  *= mix;
 629     }
 630
 631     final = (const unsigned char *)beg;
 632
 633     switch (size & 7) {
 634         case 7: hash ^= (uint64_t)(final[6]) << 48;
 635         case 6: hash ^= (uint64_t)(final[5]) << 40;
 636         case 5: hash ^= (uint64_t)(final[4]) << 32;
 637         case 4: hash ^= (uint64_t)(final[3]) << 24;
 638         case 3: hash ^= (uint64_t)(final[2]) << 16;
 639         case 2: hash ^= (uint64_t)(final[1]) << 8;
 640         case 1: hash ^= (uint64_t)(final[0]);
 641                 hash *= mix;
 642     }
 643
 644     hash ^= hash >> rot;
 645     hash *= mix;
 646     hash ^= hash >> rot;
 647
 648     return (uint32_t)(hash % ht->size);
 649 }
 650
 651 #else
 652 GMQCC_INLINE uint32_t util_hthashfunc(hash_table_t *ht, const char *key, size_t seed) {
 653     const uint32_t       mix   = 0x5BD1E995;
 654     const uint32_t       rot   = 24;
 655     size_t               size  = strlen(key);
 656     uint32_t             hash  = seed ^ size;
 657     uint32_t             alias = 0;
 658     const unsigned char *data  = (const unsigned char*)key;
 659
 660     while (size >= 4) {
 661         alias = *(uint32_t*)data;
 662
 663         alias *= mix;
 664         alias ^= alias >> rot;
 665         alias *= mix;
 666
 667         hash  *= mix;
 668         hash  ^= alias;
 669
 670         data += 4;
 671         size -= 4;
 672     }
 673
 674     switch (size) {
 675         case 3: hash ^= data[2] << 16;
 676         case 2: hash ^= data[1] << 8;
 677         case 1: hash ^= data[0];
 678                 hash *= mix;
 679     }
 680
 681     hash ^= hash >> 13;
 682     hash *= mix;
 683     hash ^= hash >> 15;
 684
 685     return hash % ht->size;
 686 }
 687 #endif
 688
 689 /* we use the crc table as seeds for the murmur hash :P */
 690 size_t util_hthash(hash_table_t *ht, const char *key) {
 691     static   size_t seed = 0;
 692     register size_t hash = util_hthashfunc(ht, key, util_crc32_table[seed]);
 693
 694     /* reset seed */
 695     if (seed >= sizeof(util_crc32_table) / sizeof(*util_crc32_table))
 696         seed  = 0;
 697
 698     return hash;
 699 }
 700
 701 hash_node_t *_util_htnewpair(const char *key, void *value) {
 702     hash_node_t *node;
 703     if (!(node = mem_a(sizeof(hash_node_t))))
 704         return NULL;
 705
 706     if (!(node->key = util_strdup(key))) {
 707         mem_d(node);
 708         return NULL;
 709     }
 710
 711     node->value = value;
 712     node->next  = NULL;
 713
 714     return node;
 715 }
 716
 717 /*
 718  * EXPOSED INTERFACE for the hashtable implementation
 719  * util_htnew(size)                             -- to make a new hashtable
 720  * util_htset(table, key, value, sizeof(value)) -- to set something in the table
 721  * util_htget(table, key)                       -- to get something from the table
 722  * util_htdel(table)                            -- to delete the table
 723  */
 724 hash_table_t *util_htnew(size_t size) {
 725     hash_table_t *hashtable = NULL;
 726     if (size < 1)
 727         return NULL;
 728
 729     if (!(hashtable = mem_a(sizeof(hash_table_t))))
 730         return NULL;
 731
 732     if (!(hashtable->table = mem_a(sizeof(hash_node_t*) * size))) {
 733         mem_d(hashtable);
 734         return NULL;
 735     }
 736
 737     hashtable->size = size;
 738     memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
 739
 740     return hashtable;
 741 }
 742
 743 void util_htseth(hash_table_t *ht, const char *key, size_t bin, void *value) {
 744     hash_node_t *newnode = NULL;
 745     hash_node_t *next    = NULL;
 746     hash_node_t *last    = NULL;
 747
 748     next = ht->table[bin];
 749
 750     while (next && next->key && strcmp(key, next->key) > 0)
 751         last = next, next = next->next;
 752
 753     /* already in table, do a replace */
 754     if (next && next->key && strcmp(key, next->key) == 0) {
 755         next->value = value;
 756     } else {
 757         /* not found, grow a pair man :P */
 758         newnode = _util_htnewpair(key, value);
 759         if (next == ht->table[bin]) {
 760             newnode->next  = next;
 761             ht->table[bin] = newnode;
 762         } else if (!next) {
 763             last->next = newnode;
 764         } else {
 765             newnode->next = next;
 766             last->next = newnode;
 767         }
 768     }
 769 }
 770
 771 void util_htset(hash_table_t *ht, const char *key, void *value) {
 772     util_htseth(ht, key, util_hthash(ht, key), value);
 773 }
 774
 775 void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
 776     hash_node_t *pair = ht->table[bin];
 777
 778     while (pair && pair->key && strcmp(key, pair->key) > 0)
 779         pair = pair->next;
 780
 781     if (!pair || !pair->key || strcmp(key, pair->key) != 0)
 782         return NULL;
 783
 784     return pair->value;
 785 }
 786
 787 void *util_htget(hash_table_t *ht, const char *key) {
 788     return util_htgeth(ht, key, util_hthash(ht, key));
 789 }
 790
 791 /*
 792  * Free all allocated data in a hashtable, this is quite the amount
 793  * of work.
 794  */
 795 void util_htdel(hash_table_t *ht) {
 796     size_t i = 0;
 797     for (; i < ht->size; i++) {
 798         hash_node_t *n = ht->table[i];
 799         hash_node_t *p;
 800
 801         /* free in list */
 802         while (n) {
 803             if (n->key)
 804                 mem_d(n->key);
 805             p = n;
 806             n = n->next;
 807             mem_d(p);
 808         }
 809
 810     }
 811     /* free table */
 812     mem_d(ht->table);
 813     mem_d(ht);
 814 }