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