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