2b2f1b0e1ffa5d00d0e58c9d11a400cd692cea91
[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 void util_debug(const char *area, const char *ms, ...) {
180     va_list  va;
181     if (!opts.debug)
182         return;
183
184     if (!strcmp(area, "MEM") && !opts.memchk)
185         return;
186
187     va_start(va, ms);
188     con_out ("[%s] ", area);
189     con_vout(ms, va);
190     va_end  (va);
191 }
192
193 /*
194  * only required if big endian .. otherwise no need to swap
195  * data.
196  */   
197 #if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_BIG
198     static void util_swap16(uint16_t *d, size_t l) {
199         while (l--) {
200             d[l] = (d[l] << 8) | (d[l] >> 8);
201         }
202     }
203
204     static void util_swap32(uint32_t *d, size_t l) {
205         while (l--) {
206             uint32_t v;
207             v = ((d[l] << 8) & 0xFF00FF00) | ((d[l] >> 8) & 0x00FF00FF);
208             d[l] = (v << 16) | (v >> 16);
209         }
210     }
211
212     /* Some strange system doesn't like constants that big, AND doesn't recognize an ULL suffix
213      * so let's go the safe way
214      */
215     static void util_swap64(uint32_t *d, size_t l) {
216         /*
217         while (l--) {
218             uint64_t v;
219             v = ((d[l] << 8) & 0xFF00FF00FF00FF00) | ((d[l] >> 8) & 0x00FF00FF00FF00FF);
220             v = ((v << 16) & 0xFFFF0000FFFF0000) | ((v >> 16) & 0x0000FFFF0000FFFF);
221             d[l] = (v << 32) | (v >> 32);
222         }
223         */
224         size_t i;
225         for (i = 0; i < l; i += 2) {
226             uint32_t v1 = d[i];
227             d[i] = d[i+1];
228             d[i+1] = v1;
229             util_swap32(d+i, 2);
230         }
231     }
232 #endif
233
234 void util_endianswap(void *_data, size_t length, unsigned int typesize) {
235 #   if PLATFORM_BYTE_ORDER == -1 /* runtime check */
236     if (*((char*)&typesize))
237         return;
238 #else
239     /* prevent unused warnings */
240     (void) _data;
241     (void) length;
242     (void) typesize;
243
244 #   if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_LITTLE
245         return;
246 #   else
247         switch (typesize) {
248             case 1: return;
249             case 2:
250                 util_swap16((uint16_t*)_data, length>>1);
251                 return;
252             case 4:
253                 util_swap32((uint32_t*)_data, length>>2);
254                 return;
255             case 8:
256                 util_swap64((uint32_t*)_data, length>>3);
257                 return;
258
259             default: abort(); /* please blow the fuck up! */
260         }
261 #   endif
262 #endif
263 }
264
265 /*
266  * CRC algorithms vary in the width of the polynomial, the value of said polynomial,
267  * the initial value used for the register, weather the bits of each byte are reflected
268  * before being processed, weather the algorithm itself feeds input bytes through the
269  * register or XORs them with a byte from one end and then straight into the table, as
270  * well as (but not limited to the idea of reflected versions) where the final register
271  * value becomes reversed, and finally weather the value itself is used to XOR the final
272  * register value.  AS such you can already imagine how painfully annoying CRCs are,
273  * of course we stand to target Quake, which expects it's certian set of rules for proper
274  * calculation of a CRC.
275  *
276  * In most traditional CRC algorithms on uses a reflected table driven method where a value
277  * or register is reflected if it's bits are swapped around it's center.  For example:
278  * take the bits 0101 is the 4-bit reflection of 1010, and respectfully 0011 would be the
279  * reflection of 1100. Quake however expects a NON-Reflected CRC on the output, but still
280  * requires a final XOR on the values (0xFFFF and 0x0000) this is a standard CCITT CRC-16
281  * which I respectfully as a programmer don't agree with.
282  *
283  * So now you know what we target, and why we target it, despite how unsettling it may seem
284  * but those are what Quake seems to request.
285  */
286
287 static const uint16_t util_crc16_table[] = {
288     0x0000,     0x1021,     0x2042,     0x3063,     0x4084,     0x50A5,
289     0x60C6,     0x70E7,     0x8108,     0x9129,     0xA14A,     0xB16B,
290     0xC18C,     0xD1AD,     0xE1CE,     0xF1EF,     0x1231,     0x0210,
291     0x3273,     0x2252,     0x52B5,     0x4294,     0x72F7,     0x62D6,
292     0x9339,     0x8318,     0xB37B,     0xA35A,     0xD3BD,     0xC39C,
293     0xF3FF,     0xE3DE,     0x2462,     0x3443,     0x0420,     0x1401,
294     0x64E6,     0x74C7,     0x44A4,     0x5485,     0xA56A,     0xB54B,
295     0x8528,     0x9509,     0xE5EE,     0xF5CF,     0xC5AC,     0xD58D,
296     0x3653,     0x2672,     0x1611,     0x0630,     0x76D7,     0x66F6,
297     0x5695,     0x46B4,     0xB75B,     0xA77A,     0x9719,     0x8738,
298     0xF7DF,     0xE7FE,     0xD79D,     0xC7BC,     0x48C4,     0x58E5,
299     0x6886,     0x78A7,     0x0840,     0x1861,     0x2802,     0x3823,
300     0xC9CC,     0xD9ED,     0xE98E,     0xF9AF,     0x8948,     0x9969,
301     0xA90A,     0xB92B,     0x5AF5,     0x4AD4,     0x7AB7,     0x6A96,
302     0x1A71,     0x0A50,     0x3A33,     0x2A12,     0xDBFD,     0xCBDC,
303     0xFBBF,     0xEB9E,     0x9B79,     0x8B58,     0xBB3B,     0xAB1A,
304     0x6CA6,     0x7C87,     0x4CE4,     0x5CC5,     0x2C22,     0x3C03,
305     0x0C60,     0x1C41,     0xEDAE,     0xFD8F,     0xCDEC,     0xDDCD,
306     0xAD2A,     0xBD0B,     0x8D68,     0x9D49,     0x7E97,     0x6EB6,
307     0x5ED5,     0x4EF4,     0x3E13,     0x2E32,     0x1E51,     0x0E70,
308     0xFF9F,     0xEFBE,     0xDFDD,     0xCFFC,     0xBF1B,     0xAF3A,
309     0x9F59,     0x8F78,     0x9188,     0x81A9,     0xB1CA,     0xA1EB,
310     0xD10C,     0xC12D,     0xF14E,     0xE16F,     0x1080,     0x00A1,
311     0x30C2,     0x20E3,     0x5004,     0x4025,     0x7046,     0x6067,
312     0x83B9,     0x9398,     0xA3FB,     0xB3DA,     0xC33D,     0xD31C,
313     0xE37F,     0xF35E,     0x02B1,     0x1290,     0x22F3,     0x32D2,
314     0x4235,     0x5214,     0x6277,     0x7256,     0xB5EA,     0xA5CB,
315     0x95A8,     0x8589,     0xF56E,     0xE54F,     0xD52C,     0xC50D,
316     0x34E2,     0x24C3,     0x14A0,     0x0481,     0x7466,     0x6447,
317     0x5424,     0x4405,     0xA7DB,     0xB7FA,     0x8799,     0x97B8,
318     0xE75F,     0xF77E,     0xC71D,     0xD73C,     0x26D3,     0x36F2,
319     0x0691,     0x16B0,     0x6657,     0x7676,     0x4615,     0x5634,
320     0xD94C,     0xC96D,     0xF90E,     0xE92F,     0x99C8,     0x89E9,
321     0xB98A,     0xA9AB,     0x5844,     0x4865,     0x7806,     0x6827,
322     0x18C0,     0x08E1,     0x3882,     0x28A3,     0xCB7D,     0xDB5C,
323     0xEB3F,     0xFB1E,     0x8BF9,     0x9BD8,     0xABBB,     0xBB9A,
324     0x4A75,     0x5A54,     0x6A37,     0x7A16,     0x0AF1,     0x1AD0,
325     0x2AB3,     0x3A92,     0xFD2E,     0xED0F,     0xDD6C,     0xCD4D,
326     0xBDAA,     0xAD8B,     0x9DE8,     0x8DC9,     0x7C26,     0x6C07,
327     0x5C64,     0x4C45,     0x3CA2,     0x2C83,     0x1CE0,     0x0CC1,
328     0xEF1F,     0xFF3E,     0xCF5D,     0xDF7C,     0xAF9B,     0xBFBA,
329     0x8FD9,     0x9FF8,     0x6E17,     0x7E36,     0x4E55,     0x5E74,
330     0x2E93,     0x3EB2,     0x0ED1,     0x1EF0
331 };
332
333 /* Non - Reflected */
334 uint16_t util_crc16(uint16_t current, const char *k, size_t len) {
335     register uint16_t h = current;
336     for (; len; --len, ++k) 
337         h = util_crc16_table[(h>>8)^((unsigned char)*k)]^(h<<8);
338     return h;
339 }
340 /* Reflective Varation (for reference) */
341 #if 0
342 uint16_t util_crc16(const char *k, int len, const short clamp) {
343     register uint16_t h= (uint16_t)0xFFFFFFFF;
344     for (; len; --len, ++k) 
345         h = util_crc16_table[(h^((unsigned char)*k))&0xFF]^(h>>8);
346     return (~h)%clamp; 
347 }
348 #endif
349
350 /*
351  * Implements libc getline for systems that don't have it, which is
352  * assmed all.  This works the same as getline().
353  */
354 int util_getline(char **lineptr, size_t *n, FILE *stream) {
355     int   chr;
356     int   ret;
357     char *pos;
358
359     if (!lineptr || !n || !stream)
360         return -1;
361     if (!*lineptr) {
362         if (!(*lineptr = (char*)mem_a((*n=64))))
363             return -1;
364     }
365
366     chr = *n;
367     pos = *lineptr;
368
369     for (;;) {
370         int c = getc(stream);
371
372         if (chr < 2) {
373             *n += (*n > 16) ? *n : 64;
374             chr = *n + *lineptr - pos;
375             if (!(*lineptr = (char*)mem_r(*lineptr,*n)))
376                 return -1;
377             pos = *n - chr + *lineptr;
378         }
379
380         if (ferror(stream))
381             return -1;
382         if (c == EOF) {
383             if (pos == *lineptr)
384                 return -1;
385             else
386                 break;
387         }
388
389         *pos++ = c;
390         chr--;
391         if (c == '\n')
392             break;
393     }
394     *pos = '\0';
395     return (ret = pos - *lineptr);
396 }
397
398 size_t util_strtocmd(const char *in, char *out, size_t outsz) {
399     size_t sz = 1;
400     for (; *in && sz < outsz; ++in, ++out, ++sz)
401         *out = (*in == '-') ? '_' : (isalpha(*in) && !isupper(*in)) ? *in + 'A' - 'a': *in;
402     *out = 0;
403     return sz-1;
404 }
405
406 size_t util_strtononcmd(const char *in, char *out, size_t outsz) {
407     size_t sz = 1;
408     for (; *in && sz < outsz; ++in, ++out, ++sz)
409         *out = (*in == '_') ? '-' : (isalpha(*in) && isupper(*in)) ? *in + 'a' - 'A' : *in;
410     *out = 0;
411     return sz-1;
412 }
413
414
415 FILE *util_fopen(const char *filename, const char *mode)
416 {
417 #ifdef _MSC_VER
418     FILE *out;
419     if (fopen_s(&out, filename, mode) != 0)
420         return NULL;
421     return out;
422 #else
423     return fopen(filename, mode);
424 #endif
425 }
426
427 void _util_vec_grow(void **a, size_t i, size_t s) {
428     size_t m = *a ? 2*_vec_beg(*a)+i : i+1;
429     void  *p = mem_r((*a ? _vec_raw(*a) : NULL), s * m + sizeof(size_t)*2);
430     if (!*a)
431         ((size_t*)p)[1] = 0;
432     *a = (void*)((size_t*)p + 2);
433     _vec_beg(*a) = m;
434 }
435
436 /*
437  * Hash table for generic data, based on dynamic memory allocations
438  * all around.  This is the internal interface, please look for
439  * EXPOSED INTERFACE comment below
440  */
441 typedef struct hash_node_t {
442     char               *key;   /* the key for this node in table */
443     void               *value; /* pointer to the data as void*   */
444     struct hash_node_t *next;  /* next node (linked list)        */
445 } hash_node_t;
446
447 GMQCC_INLINE size_t util_hthash(hash_table_t *ht, const char *key) {
448     const uint32_t       mix   = 0x5BD1E995;
449     const uint32_t       rot   = 24;
450     size_t               size  = strlen(key);
451     uint32_t             hash  = 0x1EF0 /* LICRC TAB */  ^ size;
452     uint32_t             alias = 0;
453     const unsigned char *data  = (const unsigned char*)key;
454
455     while (size >= 4) {
456         alias = *(uint32_t*)data;
457
458         alias *= mix;
459         alias ^= alias >> rot;
460         alias *= mix;
461
462         hash  *= mix;
463         hash  ^= alias;
464
465         data += 4;
466         size -= 4;
467     }
468
469     switch (size) {
470         case 3: hash ^= data[2] << 16;
471         case 2: hash ^= data[1] << 8;
472         case 1: hash ^= data[0];
473                 hash *= mix;
474     }
475
476     hash ^= hash >> 13;
477     hash *= mix;
478     hash ^= hash >> 15;
479
480     return (size_t) (hash % ht->size);
481 }
482
483 hash_node_t *_util_htnewpair(const char *key, void *value) {
484     hash_node_t *node;
485     if (!(node = mem_a(sizeof(hash_node_t))))
486         return NULL;
487
488     if (!(node->key = util_strdup(key))) {
489         mem_d(node);
490         return NULL;
491     }
492
493     node->value = value;
494     node->next  = NULL;
495
496     return node;
497 }
498
499 /*
500  * EXPOSED INTERFACE for the hashtable implementation
501  * util_htnew(size)                             -- to make a new hashtable
502  * util_htset(table, key, value, sizeof(value)) -- to set something in the table
503  * util_htget(table, key)                       -- to get something from the table
504  * util_htdel(table)                            -- to delete the table
505  */
506 hash_table_t *util_htnew(size_t size) {
507     hash_table_t *hashtable = NULL;
508     if (size < 1)
509         return NULL;
510
511     if (!(hashtable = mem_a(sizeof(hash_table_t))))
512         return NULL;
513
514     if (!(hashtable->table = mem_a(sizeof(hash_node_t*) * size))) {
515         mem_d(hashtable);
516         return NULL;
517     }
518
519     hashtable->size = size;
520     memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
521
522     return hashtable;
523 }
524
525 void util_htseth(hash_table_t *ht, const char *key, size_t bin, void *value) {
526     hash_node_t *newnode = NULL;
527     hash_node_t *next    = NULL;
528     hash_node_t *last    = NULL;
529
530     next = ht->table[bin];
531
532     while (next && next->key && strcmp(key, next->key) > 0)
533         last = next, next = next->next;
534
535     /* already in table, do a replace */
536     if (next && next->key && strcmp(key, next->key) == 0) {
537         next->value = value;
538     } else {
539         /* not found, grow a pair man :P */
540         newnode = _util_htnewpair(key, value);
541         if (next == ht->table[bin]) {
542             newnode->next  = next;
543             ht->table[bin] = newnode;
544         } else if (!next) {
545             last->next = newnode;
546         } else {
547             newnode->next = next;
548             last->next = newnode;
549         }
550     }
551 }
552
553 void util_htset(hash_table_t *ht, const char *key, void *value) {
554     util_htseth(ht, key, util_hthash(ht, key), value);
555 }
556
557 void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
558     hash_node_t *pair = ht->table[bin];
559
560     while (pair && pair->key && strcmp(key, pair->key) > 0)
561         pair = pair->next;
562
563     if (!pair || !pair->key || strcmp(key, pair->key) != 0)
564         return NULL;
565
566     return pair->value;
567 }
568
569 void *util_htget(hash_table_t *ht, const char *key) {
570     return util_htgeth(ht, key, util_hthash(ht, key));
571 }
572
573 /*
574  * Free all allocated data in a hashtable, this is quite the amount
575  * of work.
576  */
577 void util_htdel(hash_table_t *ht) {
578     size_t i = 0;
579     for (; i < ht->size; i++) {
580         hash_node_t *n = ht->table[i];
581         hash_node_t *p;
582
583         /* free in list */
584         while (n) {
585             if (n->key)
586                 mem_d(n->key);
587             p = n;
588             n = n->next;
589             mem_d(p);
590         }
591
592     }
593     /* free table */
594     mem_d(ht->table);
595     mem_d(ht);
596 }