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 GMQCC_INLINE size_t util_hthash(hash_table_t *ht, const char *key) {
 603     const uint32_t       mix   = 0x5BD1E995;
 604     const uint32_t       rot   = 24;
 605     size_t               size  = strlen(key);
 606     uint32_t             hash  = util_crc32_table[10] ^ size;
 607     uint32_t             alias = 0;
 608     const unsigned char *data  = (const unsigned char*)key;
 609
 610     while (size >= 4) {
 611         alias = *(uint32_t*)data;
 612
 613         alias *= mix;
 614         alias ^= alias >> rot;
 615         alias *= mix;
 616
 617         hash  *= mix;
 618         hash  ^= alias;
 619
 620         data += 4;
 621         size -= 4;
 622     }
 623
 624     switch (size) {
 625         case 3: hash ^= data[2] << 16;
 626         case 2: hash ^= data[1] << 8;
 627         case 1: hash ^= data[0];
 628                 hash *= mix;
 629     }
 630
 631     hash ^= hash >> 13;
 632     hash *= mix;
 633     hash ^= hash >> 15;
 634
 635     return (size_t) (hash % ht->size);
 636 }
 637
 638 hash_node_t *_util_htnewpair(const char *key, void *value) {
 639     hash_node_t *node;
 640     if (!(node = mem_a(sizeof(hash_node_t))))
 641         return NULL;
 642
 643     if (!(node->key = util_strdup(key))) {
 644         mem_d(node);
 645         return NULL;
 646     }
 647
 648     node->value = value;
 649     node->next  = NULL;
 650
 651     return node;
 652 }
 653
 654 /*
 655  * EXPOSED INTERFACE for the hashtable implementation
 656  * util_htnew(size)                             -- to make a new hashtable
 657  * util_htset(table, key, value, sizeof(value)) -- to set something in the table
 658  * util_htget(table, key)                       -- to get something from the table
 659  * util_htdel(table)                            -- to delete the table
 660  */
 661 hash_table_t *util_htnew(size_t size) {
 662     hash_table_t *hashtable = NULL;
 663     if (size < 1)
 664         return NULL;
 665
 666     if (!(hashtable = mem_a(sizeof(hash_table_t))))
 667         return NULL;
 668
 669     if (!(hashtable->table = mem_a(sizeof(hash_node_t*) * size))) {
 670         mem_d(hashtable);
 671         return NULL;
 672     }
 673
 674     hashtable->size = size;
 675     memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
 676
 677     return hashtable;
 678 }
 679
 680 void util_htseth(hash_table_t *ht, const char *key, size_t bin, void *value) {
 681     hash_node_t *newnode = NULL;
 682     hash_node_t *next    = NULL;
 683     hash_node_t *last    = NULL;
 684
 685     next = ht->table[bin];
 686
 687     while (next && next->key && strcmp(key, next->key) > 0)
 688         last = next, next = next->next;
 689
 690     /* already in table, do a replace */
 691     if (next && next->key && strcmp(key, next->key) == 0) {
 692         next->value = value;
 693     } else {
 694         /* not found, grow a pair man :P */
 695         newnode = _util_htnewpair(key, value);
 696         if (next == ht->table[bin]) {
 697             newnode->next  = next;
 698             ht->table[bin] = newnode;
 699         } else if (!next) {
 700             last->next = newnode;
 701         } else {
 702             newnode->next = next;
 703             last->next = newnode;
 704         }
 705     }
 706 }
 707
 708 void util_htset(hash_table_t *ht, const char *key, void *value) {
 709     util_htseth(ht, key, util_hthash(ht, key), value);
 710 }
 711
 712 void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
 713     hash_node_t *pair = ht->table[bin];
 714
 715     while (pair && pair->key && strcmp(key, pair->key) > 0)
 716         pair = pair->next;
 717
 718     if (!pair || !pair->key || strcmp(key, pair->key) != 0)
 719         return NULL;
 720
 721     return pair->value;
 722 }
 723
 724 void *util_htget(hash_table_t *ht, const char *key) {
 725     return util_htgeth(ht, key, util_hthash(ht, key));
 726 }
 727
 728 /*
 729  * Free all allocated data in a hashtable, this is quite the amount
 730  * of work.
 731  */
 732 void util_htdel(hash_table_t *ht) {
 733     size_t i = 0;
 734     for (; i < ht->size; i++) {
 735         hash_node_t *n = ht->table[i];
 736         hash_node_t *p;
 737
 738         /* free in list */
 739         while (n) {
 740             if (n->key)
 741                 mem_d(n->key);
 742             p = n;
 743             n = n->next;
 744             mem_d(p);
 745         }
 746
 747     }
 748     /* free table */
 749     mem_d(ht->table);
 750     mem_d(ht);
 751 }