]> de.git.xonotic.org Git - xonotic/gmqcc.git/blob - util.c
mem_r to realloc
[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     unsigned int 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(unsigned int 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, unsigned int 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
90     oldinfo = ((struct memblock_t*)ptrn - 1);
91     newinfo = malloc(sizeof(struct memblock_t) + byte);
92
93     util_debug("MEM", "reallocation: % 8u -> %u (bytes) address 0x%08X -> 0x%08X @ %s:%u\n", oldinfo->byte, byte, ptrn, (void*)(newinfo+1), file, line);
94
95     /* new data */
96     if (!newinfo) {
97         util_memory_d(oldinfo+1, line, file);
98         return NULL;
99     }
100     newinfo->line = line;
101     newinfo->byte = byte;
102     newinfo->file = file;
103     newinfo->next = oldinfo->next;
104     newinfo->prev = oldinfo->prev;
105     if (mem_start == oldinfo)
106         mem_start = newinfo;
107
108     /* copy old */
109     memcpy(newinfo+1, oldinfo+1, oldinfo->byte);
110
111     /* drop old */
112     mem_db += newinfo->byte;
113     mem_db -= oldinfo->byte;
114     free(oldinfo);
115
116     /* update */
117     return newinfo+1;
118 }
119
120 void util_meminfo() {
121     struct memblock_t *info;
122
123     if (!opts_memchk)
124         return;
125
126     for (info = mem_start; info; info = info->next) {
127         util_debug("MEM", "lost:       % 8u (bytes) at %s:%u\n",
128             info->byte,
129             info->file,
130             info->line);
131     }
132
133     util_debug("MEM", "Memory information:\n\
134         Total allocations:   %llu\n\
135         Total deallocations: %llu\n\
136         Total allocated:     %llu (bytes)\n\
137         Total deallocated:   %llu (bytes)\n\
138         Leaks found:         lost %llu (bytes) in %d allocations\n",
139             mem_at,   mem_dt,
140             mem_ab,   mem_db,
141            (mem_ab -  mem_db),
142            (mem_at -  mem_dt)
143     );
144 }
145
146 /*
147  * Some string utility functions, because strdup uses malloc, and we want
148  * to track all memory (without replacing malloc).
149  */
150 char *util_strdup(const char *s) {
151     size_t  len = 0;
152     char   *ptr = NULL;
153
154     if (!s)
155         return NULL;
156
157     if ((len = strlen(s)) && (ptr = mem_a(len+1))) {
158         memcpy(ptr, s, len);
159         ptr[len] = '\0';
160     }
161     return ptr;
162 }
163
164 /*
165  * Remove quotes from a string, escapes from \ in string
166  * as well.  This function shouldn't be used to create a
167  * char array that is later freed (it uses pointer arith)
168  */
169 char *util_strrq(const char *s) {
170     char *dst = (char*)s;
171     char *src = (char*)s;
172     char  chr;
173     while ((chr = *src++) != '\0') {
174         if (chr == '\\') {
175             *dst++ = chr;
176             if ((chr = *src++) == '\0')
177                 break;
178             *dst++ = chr;
179         } else if (chr != '"')
180             *dst++ = chr;
181     }
182     *dst = '\0';
183     return dst;
184 }
185
186 /*
187  * Chops a substring from an existing string by creating a
188  * copy of it and null terminating it at the required position.
189  */
190 char *util_strchp(const char *s, const char *e) {
191     const char *c = NULL;
192     if (!s || !e)
193         return NULL;
194
195     c = s;
196     while (c != e)
197         c++;
198
199     return util_strdup(s);
200 }
201
202 /*
203  * Returns true if string is all uppercase, otherwise
204  * it returns false.
205  */
206 bool util_strupper(const char *str) {
207     while (*str) {
208         if(!isupper(*str))
209             return false;
210         str++;
211     }
212     return true;
213 }
214
215 /*
216  * Returns true if string is all digits, otherwise
217  * it returns false.
218  */
219 bool util_strdigit(const char *str) {
220     while (*str) {
221         if(!isdigit(*str))
222             return false;
223         str++;
224     }
225     return true;
226 }
227
228 bool util_strncmpexact(const char *src, const char *ned, size_t len) {
229     return (!strncmp(src, ned, len) && !src[len]);
230 }
231
232 void util_debug(const char *area, const char *ms, ...) {
233     va_list  va;
234     if (!opts_debug)
235         return;
236
237     if (!strcmp(area, "MEM") && !opts_memchk)
238         return;
239
240     va_start(va, ms);
241     fprintf (stdout, "DEBUG: ");
242     fputc   ('[',  stdout);
243     fprintf(stdout, "%s", area);
244     fputs   ("] ", stdout);
245     vfprintf(stdout, ms, va);
246     va_end  (va);
247 }
248
249 /*
250  * Endianess swapping, all data must be stored little-endian.  This
251  * reorders by stride and length, much nicer than other functions for
252  * certian-sized types like short or int.
253  */
254 void util_endianswap(void *m, int s, int l) {
255     size_t w = 0;
256     size_t i = 0;
257
258     /* ignore if we're already LE */
259     if(*((char *)&s))
260         return;
261
262     for(; w < l; w++) {
263         for(;  i < s << 1; i++) {
264             unsigned char *p = (unsigned char *)m+w*s;
265             unsigned char  t = p[i];
266             p[i]             = p[s-i-1];
267             p[s-i-1]         = t;
268         }
269     }
270 }
271
272 /*
273  * CRC algorithms vary in the width of the polynomial, the value of said polynomial,
274  * the initial value used for the register, weather the bits of each byte are reflected
275  * before being processed, weather the algorithm itself feeds input bytes through the
276  * register or XORs them with a byte from one end and then straight into the table, as
277  * well as (but not limited to the idea of reflected versions) where the final register
278  * value becomes reversed, and finally weather the value itself is used to XOR the final
279  * register value.  AS such you can already imagine how painfully annoying CRCs are,
280  * of course we stand to target Quake, which expects it's certian set of rules for proper
281  * calculation of a CRC.
282  *
283  * In most traditional CRC algorithms on uses a reflected table driven method where a value
284  * or register is reflected if it's bits are swapped around it's center.  For example:
285  * take the bits 0101 is the 4-bit reflection of 1010, and respectfully 0011 would be the
286  * reflection of 1100. Quakle however expects a NON-Reflected CRC on the output, but still
287  * requires a final XOR on the values (0xFFFF and 0x0000) this is a standard CCITT CRC-16
288  * which I respectfully as a programmer don't agree with.
289  *
290  * So now you know what we target, and why we target it, despite how unsettling it may seem
291  * but those are what Quake seems to request.
292  */
293
294 /*
295  * This is an implementation of CRC32 & CRC16. The polynomials have been
296  * offline computed for faster generation at the cost of larger code size.
297  *
298  * CRC32 Polynomial: 0xEDB88320
299  * CRC16 Polynomial: 0x00001021
300  */
301 static const uint32_t util_crc32_table[] = {
302     0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F,
303     0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
304     0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91, 0x1DB71064, 0x6AB020F2,
305     0xF3B97148, 0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
306     0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9,
307     0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172,
308     0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, 0x35B5A8FA, 0x42B2986C,
309     0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59,
310     0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423,
311     0xCFBA9599, 0xB8BDA50F, 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
312     0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 0x76DC4190, 0x01DB7106,
313     0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433,
314     0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D,
315     0x91646C97, 0xE6635C01, 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E,
316     0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950,
317     0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65,
318     0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7,
319     0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0,
320     0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C, 0x270241AA,
321     0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
322     0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81,
323     0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A,
324     0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683, 0xE3630B12, 0x94643B84,
325     0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
326     0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB,
327     0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC,
328     0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, 0xD6D6A3E8, 0xA1D1937E,
329     0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
330     0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55,
331     0x316E8EEF, 0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
332     0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 0xC5BA3BBE, 0xB2BD0B28,
333     0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D,
334     0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F,
335     0x72076785, 0x05005713, 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38,
336     0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242,
337     0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777,
338     0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69,
339     0x616BFFD3, 0x166CCF45, 0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2,
340     0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC,
341     0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
342     0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693,
343     0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94,
344     0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
345 };
346 static const uint16_t util_crc16_table[] = {
347     0x0000,     0x1021,     0x2042,     0x3063,     0x4084,     0x50A5,
348     0x60C6,     0x70E7,     0x8108,     0x9129,     0xA14A,     0xB16B,
349     0xC18C,     0xD1AD,     0xE1CE,     0xF1EF,     0x1231,     0x0210,
350     0x3273,     0x2252,     0x52B5,     0x4294,     0x72F7,     0x62D6,
351     0x9339,     0x8318,     0xB37B,     0xA35A,     0xD3BD,     0xC39C,
352     0xF3FF,     0xE3DE,     0x2462,     0x3443,     0x0420,     0x1401,
353     0x64E6,     0x74C7,     0x44A4,     0x5485,     0xA56A,     0xB54B,
354     0x8528,     0x9509,     0xE5EE,     0xF5CF,     0xC5AC,     0xD58D,
355     0x3653,     0x2672,     0x1611,     0x0630,     0x76D7,     0x66F6,
356     0x5695,     0x46B4,     0xB75B,     0xA77A,     0x9719,     0x8738,
357     0xF7DF,     0xE7FE,     0xD79D,     0xC7BC,     0x48C4,     0x58E5,
358     0x6886,     0x78A7,     0x0840,     0x1861,     0x2802,     0x3823,
359     0xC9CC,     0xD9ED,     0xE98E,     0xF9AF,     0x8948,     0x9969,
360     0xA90A,     0xB92B,     0x5AF5,     0x4AD4,     0x7AB7,     0x6A96,
361     0x1A71,     0x0A50,     0x3A33,     0x2A12,     0xDBFD,     0xCBDC,
362     0xFBBF,     0xEB9E,     0x9B79,     0x8B58,     0xBB3B,     0xAB1A,
363     0x6CA6,     0x7C87,     0x4CE4,     0x5CC5,     0x2C22,     0x3C03,
364     0x0C60,     0x1C41,     0xEDAE,     0xFD8F,     0xCDEC,     0xDDCD,
365     0xAD2A,     0xBD0B,     0x8D68,     0x9D49,     0x7E97,     0x6EB6,
366     0x5ED5,     0x4EF4,     0x3E13,     0x2E32,     0x1E51,     0x0E70,
367     0xFF9F,     0xEFBE,     0xDFDD,     0xCFFC,     0xBF1B,     0xAF3A,
368     0x9F59,     0x8F78,     0x9188,     0x81A9,     0xB1CA,     0xA1EB,
369     0xD10C,     0xC12D,     0xF14E,     0xE16F,     0x1080,     0x00A1,
370     0x30C2,     0x20E3,     0x5004,     0x4025,     0x7046,     0x6067,
371     0x83B9,     0x9398,     0xA3FB,     0xB3DA,     0xC33D,     0xD31C,
372     0xE37F,     0xF35E,     0x02B1,     0x1290,     0x22F3,     0x32D2,
373     0x4235,     0x5214,     0x6277,     0x7256,     0xB5EA,     0xA5CB,
374     0x95A8,     0x8589,     0xF56E,     0xE54F,     0xD52C,     0xC50D,
375     0x34E2,     0x24C3,     0x14A0,     0x0481,     0x7466,     0x6447,
376     0x5424,     0x4405,     0xA7DB,     0xB7FA,     0x8799,     0x97B8,
377     0xE75F,     0xF77E,     0xC71D,     0xD73C,     0x26D3,     0x36F2,
378     0x0691,     0x16B0,     0x6657,     0x7676,     0x4615,     0x5634,
379     0xD94C,     0xC96D,     0xF90E,     0xE92F,     0x99C8,     0x89E9,
380     0xB98A,     0xA9AB,     0x5844,     0x4865,     0x7806,     0x6827,
381     0x18C0,     0x08E1,     0x3882,     0x28A3,     0xCB7D,     0xDB5C,
382     0xEB3F,     0xFB1E,     0x8BF9,     0x9BD8,     0xABBB,     0xBB9A,
383     0x4A75,     0x5A54,     0x6A37,     0x7A16,     0x0AF1,     0x1AD0,
384     0x2AB3,     0x3A92,     0xFD2E,     0xED0F,     0xDD6C,     0xCD4D,
385     0xBDAA,     0xAD8B,     0x9DE8,     0x8DC9,     0x7C26,     0x6C07,
386     0x5C64,     0x4C45,     0x3CA2,     0x2C83,     0x1CE0,     0x0CC1,
387     0xEF1F,     0xFF3E,     0xCF5D,     0xDF7C,     0xAF9B,     0xBFBA,
388     0x8FD9,     0x9FF8,     0x6E17,     0x7E36,     0x4E55,     0x5E74,
389     0x2E93,     0x3EB2,     0x0ED1,     0x1EF0
390 };
391
392 /*
393  * Implements a CRC function for X worth bits using (uint[X]_t)
394  * as type. and util_crc[X]_table.
395
396  * Quake expects a non-reflective CRC.
397  */
398 #define CRC(X) \
399 uint##X##_t util_crc##X(uint##X##_t current, const char *k, size_t len) {  \
400     register uint##X##_t h= current;                                  \
401     for (; len; --len, ++k)                                           \
402         h = util_crc##X##_table[(h>>8)^((unsigned char)*k)]^(h<<8);   \
403     return h;                                                         \
404 }
405 CRC(32)
406 CRC(16)
407 #undef CRC
408 /*
409 #define CRC(X) \
410 uint##X##_t util_crc##X(const char *k, int len, const short clamp) {  \
411     register uint##X##_t h= (uint##X##_t)0xFFFFFFFF;                  \
412     for (; len; --len, ++k)                                           \
413         h = util_crc##X##_table[(h^((unsigned char)*k))&0xFF]^(h>>8); \
414     return (~h)%clamp;                                                \
415 }
416 */
417
418
419 /*
420  * Implements libc getline for systems that don't have it, which is
421  * assmed all.  This works the same as getline().
422  */
423 int util_getline(char **lineptr, size_t *n, FILE *stream) {
424     int   chr;
425     int   ret;
426     char *pos;
427
428     if (!lineptr || !n || !stream)
429         return -1;
430     if (!*lineptr) {
431         if (!(*lineptr = (char*)mem_a((*n=64))))
432             return -1;
433     }
434
435     chr = *n;
436     pos = *lineptr;
437
438     for (;;) {
439         int c = getc(stream);
440
441         if (chr < 2) {
442             char *tmp = (char*)mem_a((*n+=(*n>16)?*n:64));
443             if  (!tmp)
444                 return -1;
445
446             memcpy(tmp, *lineptr, pos - *lineptr);
447             chr = *n + *lineptr - pos;
448             if (!(*lineptr = tmp)) {
449                 mem_d (tmp);
450                 return -1;
451             }
452             pos = *n - chr + *lineptr;
453         }
454
455         if (ferror(stream))
456             return -1;
457         if (c == EOF) {
458             if (pos == *lineptr)
459                 return -1;
460             else
461                 break;
462         }
463
464         *pos++ = c;
465         chr--;
466         if (c == '\n')
467             break;
468     }
469     *pos = '\0';
470     return (ret = pos - *lineptr);
471 }
472
473 size_t util_strtocmd(const char *in, char *out, size_t outsz) {
474     size_t sz = 1;
475     for (; *in && sz < outsz; ++in, ++out, ++sz) {
476         if (*in == '-')
477             *out = '_';
478         else if (isalpha(*in) && !isupper(*in))
479             *out = *in + 'A' - 'a';
480         else
481             *out = *in;
482     }
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         if (*in == '_')
491             *out = '-';
492         else if (isalpha(*in) && isupper(*in))
493             *out = *in + 'a' - 'A';
494         else
495             *out = *in;
496     }
497     *out = 0;
498     return sz-1;
499 }
500
501 FILE *util_fopen(const char *filename, const char *mode)
502 {
503 #ifdef WIN32
504     FILE *out;
505     if (fopen_s(&out, filename, mode) != 0)
506         return NULL;
507     return out;
508 #else
509     return fopen(filename, mode);
510 #endif
511 }
512