Implemented roboust compile-time endianess check.
[xonotic/gmqcc.git] / 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 }