fast optimized murmur hash with crc seeding, literally zero collision, and roughly...
[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 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*)ket;
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 }