Stick to one hash function (no platform optimized versions)
[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 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 }