ast_binstore_codegen initialize left ir value to null for output left side used for...
[xonotic/gmqcc.git] / util.c
1 /*
2  * Copyright (C) 2012
3  *     Dale Weiler
4  *
5  * Permission is hereby granted, free of charge, to any person obtaining a copy of
6  * this software and associated documentation files (the "Software"), to deal in
7  * the Software without restriction, including without limitation the rights to
8  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
9  * of the Software, and to permit persons to whom the Software is furnished to do
10  * so, subject to the following conditions:
11  *
12  * The above copyright notice and this permission notice shall be included in all
13  * copies or substantial portions of the Software.
14  *
15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
21  * SOFTWARE.
22  */
23 #include <stdarg.h>
24 #include <errno.h>
25 #include "gmqcc.h"
26
27 uint64_t mem_ab = 0;
28 uint64_t mem_db = 0;
29 uint64_t mem_at = 0;
30 uint64_t mem_dt = 0;
31
32 struct memblock_t {
33     const char  *file;
34     unsigned int line;
35     size_t       byte;
36     struct memblock_t *next;
37     struct memblock_t *prev;
38 };
39
40 static struct memblock_t *mem_start = NULL;
41
42 void *util_memory_a(size_t byte, unsigned int line, const char *file) {
43     struct memblock_t *info = malloc(sizeof(struct memblock_t) + byte);
44     void              *data = (void*)(info+1);
45     if (!info) return NULL;
46     info->line = line;
47     info->byte = byte;
48     info->file = file;
49     info->prev = NULL;
50     info->next = mem_start;
51     if (mem_start)
52         mem_start->prev = info;
53     mem_start = info;
54
55     util_debug("MEM", "allocation:   % 8u (bytes) address 0x%08X @ %s:%u\n", byte, data, file, line);
56     mem_at++;
57     mem_ab += info->byte;
58
59     return data;
60 }
61
62 void util_memory_d(void *ptrn, unsigned int line, const char *file) {
63     struct memblock_t *info = NULL;
64
65     if (!ptrn) return;
66     info = ((struct memblock_t*)ptrn - 1);
67
68     util_debug("MEM", "released:     % 8u (bytes) address 0x%08X @ %s:%u\n", info->byte, ptrn, file, line);
69     mem_db += info->byte;
70     mem_dt++;
71
72     if (info->prev)
73         info->prev->next = info->next;
74     if (info->next)
75         info->next->prev = info->prev;
76     if (info == mem_start)
77         mem_start = info->next;
78
79     free(info);
80 }
81
82 void *util_memory_r(void *ptrn, size_t byte, unsigned int line, const char *file) {
83     struct memblock_t *oldinfo = NULL;
84
85     struct memblock_t *newinfo;
86
87     if (!ptrn)
88         return util_memory_a(byte, line, file);
89     if (!byte) {
90         util_memory_d(ptrn, line, file);
91         return NULL;
92     }
93
94     oldinfo = ((struct memblock_t*)ptrn - 1);
95     newinfo = ((struct memblock_t*)malloc(sizeof(struct memblock_t) + byte));
96
97     util_debug("MEM", "reallocation: % 8u -> %u (bytes) address 0x%08X -> 0x%08X @ %s:%u\n", oldinfo->byte, byte, ptrn, (void*)(newinfo+1), file, line);
98
99     /* new data */
100     if (!newinfo) {
101         util_memory_d(oldinfo+1, line, file);
102         return NULL;
103     }
104
105     /* copy old */
106     memcpy(newinfo+1, oldinfo+1, oldinfo->byte);
107
108     /* free old */
109     if (oldinfo->prev)
110         oldinfo->prev->next = oldinfo->next;
111     if (oldinfo->next)
112         oldinfo->next->prev = oldinfo->prev;
113     if (oldinfo == mem_start)
114         mem_start = oldinfo->next;
115
116     /* fill info */
117     newinfo->line = line;
118     newinfo->byte = byte;
119     newinfo->file = file;
120     newinfo->prev = NULL;
121     newinfo->next = mem_start;
122     if (mem_start)
123         mem_start->prev = newinfo;
124     mem_start = newinfo;
125
126     mem_ab -= oldinfo->byte;
127     mem_ab += newinfo->byte;
128
129     free(oldinfo);
130
131     return newinfo+1;
132 }
133
134 void util_meminfo() {
135     struct memblock_t *info;
136
137     if (!opts_memchk)
138         return;
139
140     for (info = mem_start; info; info = info->next) {
141         util_debug("MEM", "lost:       % 8u (bytes) at %s:%u\n",
142             info->byte,
143             info->file,
144             info->line);
145     }
146
147     util_debug("MEM", "Memory information:\n\
148         Total allocations:   %llu\n\
149         Total deallocations: %llu\n\
150         Total allocated:     %llu (bytes)\n\
151         Total deallocated:   %llu (bytes)\n\
152         Leaks found:         lost %llu (bytes) in %d allocations\n",
153             mem_at,   mem_dt,
154             mem_ab,   mem_db,
155            (mem_ab -  mem_db),
156            (mem_at -  mem_dt)
157     );
158 }
159
160 /*
161  * Some string utility functions, because strdup uses malloc, and we want
162  * to track all memory (without replacing malloc).
163  */
164 char *util_strdup(const char *s) {
165     size_t  len = 0;
166     char   *ptr = NULL;
167
168     if (!s)
169         return NULL;
170
171     if ((len = strlen(s)) && (ptr = mem_a(len+1))) {
172         memcpy(ptr, s, len);
173         ptr[len] = '\0';
174     }
175     return ptr;
176 }
177
178 /*
179  * Remove quotes from a string, escapes from \ in string
180  * as well.  This function shouldn't be used to create a
181  * char array that is later freed (it uses pointer arith)
182  */
183 char *util_strrq(const char *s) {
184     char *dst = (char*)s;
185     char *src = (char*)s;
186     char  chr;
187     while ((chr = *src++) != '\0') {
188         if (chr == '\\') {
189             *dst++ = chr;
190             if ((chr = *src++) == '\0')
191                 break;
192             *dst++ = chr;
193         } else if (chr != '"')
194             *dst++ = chr;
195     }
196     *dst = '\0';
197     return dst;
198 }
199
200 /*
201  * Chops a substring from an existing string by creating a
202  * copy of it and null terminating it at the required position.
203  */
204 char *util_strchp(const char *s, const char *e) {
205     const char *c = NULL;
206     if (!s || !e)
207         return NULL;
208
209     c = s;
210     while (c != e)
211         c++;
212
213     return util_strdup(s);
214 }
215
216 /*
217  * Returns true if string is all uppercase, otherwise
218  * it returns false.
219  */
220 bool util_strupper(const char *str) {
221     while (*str) {
222         if(!isupper(*str))
223             return false;
224         str++;
225     }
226     return true;
227 }
228
229 /*
230  * Returns true if string is all digits, otherwise
231  * it returns false.
232  */
233 bool util_strdigit(const char *str) {
234     while (*str) {
235         if(!isdigit(*str))
236             return false;
237         str++;
238     }
239     return true;
240 }
241
242 bool util_strncmpexact(const char *src, const char *ned, size_t len) {
243     return (!strncmp(src, ned, len) && !src[len]);
244 }
245
246 void util_debug(const char *area, const char *ms, ...) {
247     va_list  va;
248     if (!opts_debug)
249         return;
250
251     if (!strcmp(area, "MEM") && !opts_memchk)
252         return;
253
254     va_start(va, ms);
255     con_out ("[%s] ", area);
256     con_vout(ms, va); 
257     va_end  (va);
258 }
259
260 /*
261  * Endianess swapping, all data must be stored little-endian.  This
262  * reorders by stride and length, much nicer than other functions for
263  * certian-sized types like short or int.
264  */
265 void util_endianswap(void *m, int s, int l) {
266     size_t w = 0;
267     size_t i = 0;
268
269     /* ignore if we're already LE */
270     if(*((char *)&s))
271         return;
272
273     for(; w < (size_t)l; w++) {
274         for(;  i < (size_t)(s << 1); i++) {
275             unsigned char *p = (unsigned char *)m+w*s;
276             unsigned char  t = p[i];
277             p[i]             = p[s-i-1];
278             p[s-i-1]         = t;
279         }
280     }
281 }
282
283 /*
284  * CRC algorithms vary in the width of the polynomial, the value of said polynomial,
285  * the initial value used for the register, weather the bits of each byte are reflected
286  * before being processed, weather the algorithm itself feeds input bytes through the
287  * register or XORs them with a byte from one end and then straight into the table, as
288  * well as (but not limited to the idea of reflected versions) where the final register
289  * value becomes reversed, and finally weather the value itself is used to XOR the final
290  * register value.  AS such you can already imagine how painfully annoying CRCs are,
291  * of course we stand to target Quake, which expects it's certian set of rules for proper
292  * calculation of a CRC.
293  *
294  * In most traditional CRC algorithms on uses a reflected table driven method where a value
295  * or register is reflected if it's bits are swapped around it's center.  For example:
296  * take the bits 0101 is the 4-bit reflection of 1010, and respectfully 0011 would be the
297  * reflection of 1100. Quakle however expects a NON-Reflected CRC on the output, but still
298  * requires a final XOR on the values (0xFFFF and 0x0000) this is a standard CCITT CRC-16
299  * which I respectfully as a programmer don't agree with.
300  *
301  * So now you know what we target, and why we target it, despite how unsettling it may seem
302  * but those are what Quake seems to request.
303  */
304
305 /*
306  * This is an implementation of CRC32 & CRC16. The polynomials have been
307  * offline computed for faster generation at the cost of larger code size.
308  *
309  * CRC32 Polynomial: 0xEDB88320
310  * CRC16 Polynomial: 0x00001021
311  */
312 static const uint32_t util_crc32_table[] = {
313     0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F,
314     0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
315     0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91, 0x1DB71064, 0x6AB020F2,
316     0xF3B97148, 0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
317     0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9,
318     0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172,
319     0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, 0x35B5A8FA, 0x42B2986C,
320     0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59,
321     0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423,
322     0xCFBA9599, 0xB8BDA50F, 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
323     0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 0x76DC4190, 0x01DB7106,
324     0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433,
325     0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D,
326     0x91646C97, 0xE6635C01, 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E,
327     0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950,
328     0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65,
329     0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7,
330     0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0,
331     0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C, 0x270241AA,
332     0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
333     0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81,
334     0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A,
335     0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683, 0xE3630B12, 0x94643B84,
336     0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
337     0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB,
338     0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC,
339     0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, 0xD6D6A3E8, 0xA1D1937E,
340     0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
341     0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55,
342     0x316E8EEF, 0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
343     0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 0xC5BA3BBE, 0xB2BD0B28,
344     0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D,
345     0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F,
346     0x72076785, 0x05005713, 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38,
347     0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242,
348     0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777,
349     0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69,
350     0x616BFFD3, 0x166CCF45, 0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2,
351     0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC,
352     0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
353     0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693,
354     0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94,
355     0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
356 };
357 static const uint16_t util_crc16_table[] = {
358     0x0000,     0x1021,     0x2042,     0x3063,     0x4084,     0x50A5,
359     0x60C6,     0x70E7,     0x8108,     0x9129,     0xA14A,     0xB16B,
360     0xC18C,     0xD1AD,     0xE1CE,     0xF1EF,     0x1231,     0x0210,
361     0x3273,     0x2252,     0x52B5,     0x4294,     0x72F7,     0x62D6,
362     0x9339,     0x8318,     0xB37B,     0xA35A,     0xD3BD,     0xC39C,
363     0xF3FF,     0xE3DE,     0x2462,     0x3443,     0x0420,     0x1401,
364     0x64E6,     0x74C7,     0x44A4,     0x5485,     0xA56A,     0xB54B,
365     0x8528,     0x9509,     0xE5EE,     0xF5CF,     0xC5AC,     0xD58D,
366     0x3653,     0x2672,     0x1611,     0x0630,     0x76D7,     0x66F6,
367     0x5695,     0x46B4,     0xB75B,     0xA77A,     0x9719,     0x8738,
368     0xF7DF,     0xE7FE,     0xD79D,     0xC7BC,     0x48C4,     0x58E5,
369     0x6886,     0x78A7,     0x0840,     0x1861,     0x2802,     0x3823,
370     0xC9CC,     0xD9ED,     0xE98E,     0xF9AF,     0x8948,     0x9969,
371     0xA90A,     0xB92B,     0x5AF5,     0x4AD4,     0x7AB7,     0x6A96,
372     0x1A71,     0x0A50,     0x3A33,     0x2A12,     0xDBFD,     0xCBDC,
373     0xFBBF,     0xEB9E,     0x9B79,     0x8B58,     0xBB3B,     0xAB1A,
374     0x6CA6,     0x7C87,     0x4CE4,     0x5CC5,     0x2C22,     0x3C03,
375     0x0C60,     0x1C41,     0xEDAE,     0xFD8F,     0xCDEC,     0xDDCD,
376     0xAD2A,     0xBD0B,     0x8D68,     0x9D49,     0x7E97,     0x6EB6,
377     0x5ED5,     0x4EF4,     0x3E13,     0x2E32,     0x1E51,     0x0E70,
378     0xFF9F,     0xEFBE,     0xDFDD,     0xCFFC,     0xBF1B,     0xAF3A,
379     0x9F59,     0x8F78,     0x9188,     0x81A9,     0xB1CA,     0xA1EB,
380     0xD10C,     0xC12D,     0xF14E,     0xE16F,     0x1080,     0x00A1,
381     0x30C2,     0x20E3,     0x5004,     0x4025,     0x7046,     0x6067,
382     0x83B9,     0x9398,     0xA3FB,     0xB3DA,     0xC33D,     0xD31C,
383     0xE37F,     0xF35E,     0x02B1,     0x1290,     0x22F3,     0x32D2,
384     0x4235,     0x5214,     0x6277,     0x7256,     0xB5EA,     0xA5CB,
385     0x95A8,     0x8589,     0xF56E,     0xE54F,     0xD52C,     0xC50D,
386     0x34E2,     0x24C3,     0x14A0,     0x0481,     0x7466,     0x6447,
387     0x5424,     0x4405,     0xA7DB,     0xB7FA,     0x8799,     0x97B8,
388     0xE75F,     0xF77E,     0xC71D,     0xD73C,     0x26D3,     0x36F2,
389     0x0691,     0x16B0,     0x6657,     0x7676,     0x4615,     0x5634,
390     0xD94C,     0xC96D,     0xF90E,     0xE92F,     0x99C8,     0x89E9,
391     0xB98A,     0xA9AB,     0x5844,     0x4865,     0x7806,     0x6827,
392     0x18C0,     0x08E1,     0x3882,     0x28A3,     0xCB7D,     0xDB5C,
393     0xEB3F,     0xFB1E,     0x8BF9,     0x9BD8,     0xABBB,     0xBB9A,
394     0x4A75,     0x5A54,     0x6A37,     0x7A16,     0x0AF1,     0x1AD0,
395     0x2AB3,     0x3A92,     0xFD2E,     0xED0F,     0xDD6C,     0xCD4D,
396     0xBDAA,     0xAD8B,     0x9DE8,     0x8DC9,     0x7C26,     0x6C07,
397     0x5C64,     0x4C45,     0x3CA2,     0x2C83,     0x1CE0,     0x0CC1,
398     0xEF1F,     0xFF3E,     0xCF5D,     0xDF7C,     0xAF9B,     0xBFBA,
399     0x8FD9,     0x9FF8,     0x6E17,     0x7E36,     0x4E55,     0x5E74,
400     0x2E93,     0x3EB2,     0x0ED1,     0x1EF0
401 };
402
403 /*
404  * Implements a CRC function for X worth bits using (uint[X]_t)
405  * as type. and util_crc[X]_table.
406
407  * Quake expects a non-reflective CRC.
408  */
409 #define CRC(X) \
410 uint##X##_t util_crc##X(uint##X##_t current, const char *k, size_t len) {  \
411     register uint##X##_t h= current;                                  \
412     for (; len; --len, ++k)                                           \
413         h = util_crc##X##_table[(h>>8)^((unsigned char)*k)]^(h<<8);   \
414     return h;                                                         \
415 }
416 CRC(32)
417 CRC(16)
418 #undef CRC
419 /*
420 #define CRC(X) \
421 uint##X##_t util_crc##X(const char *k, int len, const short clamp) {  \
422     register uint##X##_t h= (uint##X##_t)0xFFFFFFFF;                  \
423     for (; len; --len, ++k)                                           \
424         h = util_crc##X##_table[(h^((unsigned char)*k))&0xFF]^(h>>8); \
425     return (~h)%clamp;                                                \
426 }
427 */
428
429
430 /*
431  * Implements libc getline for systems that don't have it, which is
432  * assmed all.  This works the same as getline().
433  */
434 int util_getline(char **lineptr, size_t *n, FILE *stream) {
435     int   chr;
436     int   ret;
437     char *pos;
438
439     if (!lineptr || !n || !stream)
440         return -1;
441     if (!*lineptr) {
442         if (!(*lineptr = (char*)mem_a((*n=64))))
443             return -1;
444     }
445
446     chr = *n;
447     pos = *lineptr;
448
449     for (;;) {
450         int c = getc(stream);
451
452         if (chr < 2) {
453             *n += (*n > 16) ? *n : 64;
454             chr = *n + *lineptr - pos;
455             if (!(*lineptr = (char*)mem_r(*lineptr,*n)))
456                 return -1;
457             pos = *n - chr + *lineptr;
458         }
459
460         if (ferror(stream))
461             return -1;
462         if (c == EOF) {
463             if (pos == *lineptr)
464                 return -1;
465             else
466                 break;
467         }
468
469         *pos++ = c;
470         chr--;
471         if (c == '\n')
472             break;
473     }
474     *pos = '\0';
475     return (ret = pos - *lineptr);
476 }
477
478 size_t util_strtocmd(const char *in, char *out, size_t outsz) {
479     size_t sz = 1;
480     for (; *in && sz < outsz; ++in, ++out, ++sz)
481         *out = (*in == '-') ? '_' : (isalpha(*in) && !isupper(*in)) ? *in + 'A' - 'a': *in;
482     *out = 0;
483     return sz-1;
484 }
485
486 size_t util_strtononcmd(const char *in, char *out, size_t outsz) {
487     size_t sz = 1;
488     for (; *in && sz < outsz; ++in, ++out, ++sz)
489         *out = (*in == '_') ? '-' : (isalpha(*in) && isupper(*in)) ? *in + 'a' - 'A' : *in;
490     *out = 0;
491     return sz-1;
492 }
493
494
495 FILE *util_fopen(const char *filename, const char *mode)
496 {
497 #ifdef WIN32
498     FILE *out;
499     if (fopen_s(&out, filename, mode) != 0)
500         return NULL;
501     return out;
502 #else
503     return fopen(filename, mode);
504 #endif
505 }
506
507 void _util_vec_grow(void **a, size_t i, size_t s) {
508     size_t m = *a ? 2*_vec_beg(*a)+i : i+1;
509     void  *p = mem_r((*a ? _vec_raw(*a) : NULL), s * m + sizeof(size_t)*2);
510     if (!*a)
511         ((size_t*)p)[1] = 0;
512     *a = (void*)((size_t*)p + 2);
513     _vec_beg(*a) = m;
514 }
515
516 /*
517  * Hash table for generic data, based on dynamic memory allocations
518  * all around.  This is the internal interface, please look for
519  * EXPOSED INTERFACE comment below
520  */
521 typedef struct hash_node_t {
522     char               *key;  /* the key for this node in table */
523     void               *value; /* allocated memory storing data  */
524     size_t              size; /* size of data                   */
525     struct hash_node_t *next; /* next node (linked list)        */
526 } hash_node_t;
527
528
529 size_t _util_hthash(hash_table_t *ht, const char *key) {
530     uint64_t val = 0;
531     size_t   len = strlen(key);
532     size_t   itr = 0;
533     
534     
535     while (val < ((uint64_t)~1) /* MAX SIZE OF UINT64 */ && itr < len) {
536         val  = val << 8;
537         val += key[itr];
538         
539         itr++;
540     }
541     
542     return val % ht->size;
543 }
544
545 hash_node_t *_util_htnewpair(const char *key, void *value, size_t size) {
546     hash_node_t *node;
547     if (!(node = mem_a(sizeof(hash_node_t))))
548         return NULL;
549         
550     if (!(node->key = util_strdup(key))) {
551         mem_d(node);
552         return NULL;
553     }
554     
555     if (!(node->value = mem_a(size))) {
556         mem_d(node->key);
557         mem_d(node);
558         return NULL;
559     }
560     
561     memcpy(node->value, value, size);
562     node->size = size;
563     node->next = NULL;
564     
565     return node;
566 }
567
568 /*
569  * EXPOSED INTERFACE for the hashtable implementation
570  * util_htnew(size)                             -- to make a new hashtable
571  * util_htset(table, key, value, sizeof(value)) -- to set something in the table
572  * util_htget(table, key)                       -- to get something from the table
573  * util_htdel(table)                            -- to delete the table
574  */
575 hash_table_t *util_htnew(size_t size) {
576     hash_table_t *hashtable = NULL;
577     if (size < 1)
578         return NULL;
579         
580     if (!(hashtable = mem_a(sizeof(hash_table_t))))
581         return NULL;
582         
583     if (!(hashtable->table = mem_a(sizeof(hash_node_t*) * size))) {
584         mem_d(hashtable);
585         return NULL;
586     }
587     
588     hashtable->size = size;
589     memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
590     
591     return hashtable;
592 }
593
594 void util_htset(hash_table_t *ht, const char *key, void *value, size_t size) {
595     size_t bin = 0;
596     hash_node_t *newnode = NULL;
597     hash_node_t *next    = NULL;
598     hash_node_t *last    = NULL;
599     
600     bin  = _util_hthash(ht, key);
601     next = ht->table[bin];
602     
603     while (next && next->key && strcmp(key, next->key))
604         last = next, next = next->next;
605     
606     /* already in table, do a replace */
607     if (next && next->key && !strcmp(key, next->key)) {
608         mem_d(next->value);
609         next->value = mem_a(size);
610         next->size  = size;
611         memcpy(next->value, value, size);
612     } else {
613         /* not found, grow a pair man :P */
614         newnode = _util_htnewpair(key, value, size);
615         if (next == ht->table[bin]) {
616             newnode->next  = next;
617             ht->table[bin] = newnode;
618         } else if (!next) {
619             last->next = newnode;
620         } else {
621             newnode->next = next;
622             last->next = newnode;
623         }
624     }
625 }
626
627 void *util_htget(hash_table_t *ht, const char *key) {
628     size_t       bin  = _util_hthash(ht, key);
629     hash_node_t *pair = ht->table[bin];
630     
631     while (pair && pair->key && strcmp(key, pair->key) > 0)
632         pair = pair->next;
633         
634     if (!pair || !pair->key || strcmp(key, pair->key) != 0)
635         return NULL;
636         
637     return pair->value;
638 }
639
640 /*
641  * Free all allocated data in a hashtable, this is quite the amount
642  * of work.
643  */
644 void util_htdel(hash_table_t *ht) {
645     size_t i = 0;
646     for (; i < ht->size; i++) {
647         hash_node_t *n = ht->table[i];
648         
649         /* free in list */
650         while (n) {
651             if (n->key)   mem_d(n->key);
652             if (n->value) mem_d(n->value);
653             n = n->next;
654         }
655         
656     }
657     /* free table */
658     mem_d(ht->table);
659     mem_d(ht);
660 }