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:
13 * The above copyright notice and this permission notice shall be included in all
14 * copies or substantial portions of the Software.
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
37 struct memblock_t *next;
38 struct memblock_t *prev;
41 static struct memblock_t *mem_start = NULL;
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;
51 info->next = mem_start;
53 mem_start->prev = info;
56 util_debug("MEM", "allocation: % 8u (bytes) address 0x%08X @ %s:%u\n", byte, data, file, line);
63 void util_memory_d(void *ptrn, unsigned int line, const char *file) {
64 struct memblock_t *info = NULL;
67 info = ((struct memblock_t*)ptrn - 1);
69 util_debug("MEM", "released: % 8u (bytes) address 0x%08X @ %s:%u\n", info->byte, ptrn, file, line);
74 info->prev->next = info->next;
76 info->next->prev = info->prev;
77 if (info == mem_start)
78 mem_start = info->next;
83 void *util_memory_r(void *ptrn, size_t byte, unsigned int line, const char *file) {
84 struct memblock_t *oldinfo = NULL;
86 struct memblock_t *newinfo;
89 return util_memory_a(byte, line, file);
91 util_memory_d(ptrn, line, file);
95 oldinfo = ((struct memblock_t*)ptrn - 1);
96 newinfo = ((struct memblock_t*)malloc(sizeof(struct memblock_t) + byte));
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);
102 util_memory_d(oldinfo+1, line, file);
107 memcpy(newinfo+1, oldinfo+1, oldinfo->byte);
111 oldinfo->prev->next = oldinfo->next;
113 oldinfo->next->prev = oldinfo->prev;
114 if (oldinfo == mem_start)
115 mem_start = oldinfo->next;
118 newinfo->line = line;
119 newinfo->byte = byte;
120 newinfo->file = file;
121 newinfo->prev = NULL;
122 newinfo->next = mem_start;
124 mem_start->prev = newinfo;
127 mem_ab -= oldinfo->byte;
128 mem_ab += newinfo->byte;
135 void util_meminfo() {
136 struct memblock_t *info;
141 for (info = mem_start; info; info = info->next) {
142 util_debug("MEM", "lost: % 8u (bytes) at %s:%u\n",
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",
162 * Some string utility functions, because strdup uses malloc, and we want
163 * to track all memory (without replacing malloc).
165 char *util_strdup(const char *s) {
172 if ((len = strlen(s)) && (ptr = mem_a(len+1))) {
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)
184 char *util_strrq(const char *s) {
185 char *dst = (char*)s;
186 char *src = (char*)s;
188 while ((chr = *src++) != '\0') {
191 if ((chr = *src++) == '\0')
194 } else if (chr != '"')
202 * Chops a substring from an existing string by creating a
203 * copy of it and null terminating it at the required position.
205 char *util_strchp(const char *s, const char *e) {
206 const char *c = NULL;
214 return util_strdup(s);
218 * Returns true if string is all uppercase, otherwise
221 bool util_strupper(const char *str) {
231 * Returns true if string is all digits, otherwise
234 bool util_strdigit(const char *str) {
243 bool util_strncmpexact(const char *src, const char *ned, size_t len) {
244 return (!strncmp(src, ned, len) && !src[len]);
247 void util_debug(const char *area, const char *ms, ...) {
252 if (!strcmp(area, "MEM") && !opts.memchk)
256 con_out ("[%s] ", area);
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.
267 void util_endianswap(void *m, int s, int l) {
271 /* ignore if we're already LE */
275 for(; w < (size_t)l; w++) {
276 for(; i < (size_t)(s << 1); i++) {
277 unsigned char *p = (unsigned char *)m+w*s;
278 unsigned char t = p[i];
287 * only required if big endian .. otherwise no need to swap
290 #if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_BIG
291 static void util_swap16(uint16_t *d, size_t l) {
293 d[l] = (d[l] << 8) | (d[l] >> 8);
297 static void util_swap32(uint32_t *d, size_t l) {
300 v = ((d[l] << 8) & 0xFF00FF00) | ((d[l] >> 8) & 0x00FF00FF);
301 d[l] = (v << 16) | (v >> 16);
305 /* Some strange system doesn't like constants that big, AND doesn't recognize an ULL suffix
306 * so let's go the safe way
308 static void util_swap64(uint32_t *d, size_t l) {
312 v = ((d[l] << 8) & 0xFF00FF00FF00FF00) | ((d[l] >> 8) & 0x00FF00FF00FF00FF);
313 v = ((v << 16) & 0xFFFF0000FFFF0000) | ((v >> 16) & 0x0000FFFF0000FFFF);
314 d[l] = (v << 32) | (v >> 32);
318 for (i = 0; i < l; i += 2) {
327 void util_endianswap(void *_data, size_t length, unsigned int typesize) {
328 # if PLATFORM_BYTE_ORDER == -1 /* runtime check */
329 if (*((char*)&typesize))
332 /* prevent unused warnings */
337 # if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_LITTLE
343 util_swap16((uint16_t*)_data, length>>1);
346 util_swap32((uint32_t*)_data, length>>2);
349 util_swap64((uint32_t*)_data, length>>3);
352 default: abort(); /* please blow the fuck up! */
359 * CRC algorithms vary in the width of the polynomial, the value of said polynomial,
360 * the initial value used for the register, weather the bits of each byte are reflected
361 * before being processed, weather the algorithm itself feeds input bytes through the
362 * register or XORs them with a byte from one end and then straight into the table, as
363 * well as (but not limited to the idea of reflected versions) where the final register
364 * value becomes reversed, and finally weather the value itself is used to XOR the final
365 * register value. AS such you can already imagine how painfully annoying CRCs are,
366 * of course we stand to target Quake, which expects it's certian set of rules for proper
367 * calculation of a CRC.
369 * In most traditional CRC algorithms on uses a reflected table driven method where a value
370 * or register is reflected if it's bits are swapped around it's center. For example:
371 * take the bits 0101 is the 4-bit reflection of 1010, and respectfully 0011 would be the
372 * reflection of 1100. Quake however expects a NON-Reflected CRC on the output, but still
373 * requires a final XOR on the values (0xFFFF and 0x0000) this is a standard CCITT CRC-16
374 * which I respectfully as a programmer don't agree with.
376 * So now you know what we target, and why we target it, despite how unsettling it may seem
377 * but those are what Quake seems to request.
380 static const uint16_t util_crc16_table[] = {
381 0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5,
382 0x60C6, 0x70E7, 0x8108, 0x9129, 0xA14A, 0xB16B,
383 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF, 0x1231, 0x0210,
384 0x3273, 0x2252, 0x52B5, 0x4294, 0x72F7, 0x62D6,
385 0x9339, 0x8318, 0xB37B, 0xA35A, 0xD3BD, 0xC39C,
386 0xF3FF, 0xE3DE, 0x2462, 0x3443, 0x0420, 0x1401,
387 0x64E6, 0x74C7, 0x44A4, 0x5485, 0xA56A, 0xB54B,
388 0x8528, 0x9509, 0xE5EE, 0xF5CF, 0xC5AC, 0xD58D,
389 0x3653, 0x2672, 0x1611, 0x0630, 0x76D7, 0x66F6,
390 0x5695, 0x46B4, 0xB75B, 0xA77A, 0x9719, 0x8738,
391 0xF7DF, 0xE7FE, 0xD79D, 0xC7BC, 0x48C4, 0x58E5,
392 0x6886, 0x78A7, 0x0840, 0x1861, 0x2802, 0x3823,
393 0xC9CC, 0xD9ED, 0xE98E, 0xF9AF, 0x8948, 0x9969,
394 0xA90A, 0xB92B, 0x5AF5, 0x4AD4, 0x7AB7, 0x6A96,
395 0x1A71, 0x0A50, 0x3A33, 0x2A12, 0xDBFD, 0xCBDC,
396 0xFBBF, 0xEB9E, 0x9B79, 0x8B58, 0xBB3B, 0xAB1A,
397 0x6CA6, 0x7C87, 0x4CE4, 0x5CC5, 0x2C22, 0x3C03,
398 0x0C60, 0x1C41, 0xEDAE, 0xFD8F, 0xCDEC, 0xDDCD,
399 0xAD2A, 0xBD0B, 0x8D68, 0x9D49, 0x7E97, 0x6EB6,
400 0x5ED5, 0x4EF4, 0x3E13, 0x2E32, 0x1E51, 0x0E70,
401 0xFF9F, 0xEFBE, 0xDFDD, 0xCFFC, 0xBF1B, 0xAF3A,
402 0x9F59, 0x8F78, 0x9188, 0x81A9, 0xB1CA, 0xA1EB,
403 0xD10C, 0xC12D, 0xF14E, 0xE16F, 0x1080, 0x00A1,
404 0x30C2, 0x20E3, 0x5004, 0x4025, 0x7046, 0x6067,
405 0x83B9, 0x9398, 0xA3FB, 0xB3DA, 0xC33D, 0xD31C,
406 0xE37F, 0xF35E, 0x02B1, 0x1290, 0x22F3, 0x32D2,
407 0x4235, 0x5214, 0x6277, 0x7256, 0xB5EA, 0xA5CB,
408 0x95A8, 0x8589, 0xF56E, 0xE54F, 0xD52C, 0xC50D,
409 0x34E2, 0x24C3, 0x14A0, 0x0481, 0x7466, 0x6447,
410 0x5424, 0x4405, 0xA7DB, 0xB7FA, 0x8799, 0x97B8,
411 0xE75F, 0xF77E, 0xC71D, 0xD73C, 0x26D3, 0x36F2,
412 0x0691, 0x16B0, 0x6657, 0x7676, 0x4615, 0x5634,
413 0xD94C, 0xC96D, 0xF90E, 0xE92F, 0x99C8, 0x89E9,
414 0xB98A, 0xA9AB, 0x5844, 0x4865, 0x7806, 0x6827,
415 0x18C0, 0x08E1, 0x3882, 0x28A3, 0xCB7D, 0xDB5C,
416 0xEB3F, 0xFB1E, 0x8BF9, 0x9BD8, 0xABBB, 0xBB9A,
417 0x4A75, 0x5A54, 0x6A37, 0x7A16, 0x0AF1, 0x1AD0,
418 0x2AB3, 0x3A92, 0xFD2E, 0xED0F, 0xDD6C, 0xCD4D,
419 0xBDAA, 0xAD8B, 0x9DE8, 0x8DC9, 0x7C26, 0x6C07,
420 0x5C64, 0x4C45, 0x3CA2, 0x2C83, 0x1CE0, 0x0CC1,
421 0xEF1F, 0xFF3E, 0xCF5D, 0xDF7C, 0xAF9B, 0xBFBA,
422 0x8FD9, 0x9FF8, 0x6E17, 0x7E36, 0x4E55, 0x5E74,
423 0x2E93, 0x3EB2, 0x0ED1, 0x1EF0
426 /* Non - Reflected */
427 uint16_t util_crc16(uint16_t current, const char *k, size_t len) {
428 register uint16_t h = current;
429 for (; len; --len, ++k)
430 h = util_crc16_table[(h>>8)^((unsigned char)*k)]^(h<<8);
433 /* Reflective Varation (for reference) */
435 uint16_t util_crc16(const char *k, int len, const short clamp) {
436 register uint16_t h= (uint16_t)0xFFFFFFFF;
437 for (; len; --len, ++k)
438 h = util_crc16_table[(h^((unsigned char)*k))&0xFF]^(h>>8);
444 * Implements libc getline for systems that don't have it, which is
445 * assmed all. This works the same as getline().
447 int util_getline(char **lineptr, size_t *n, FILE *stream) {
452 if (!lineptr || !n || !stream)
455 if (!(*lineptr = (char*)mem_a((*n=64))))
463 int c = getc(stream);
466 *n += (*n > 16) ? *n : 64;
467 chr = *n + *lineptr - pos;
468 if (!(*lineptr = (char*)mem_r(*lineptr,*n)))
470 pos = *n - chr + *lineptr;
488 return (ret = pos - *lineptr);
491 size_t util_strtocmd(const char *in, char *out, size_t outsz) {
493 for (; *in && sz < outsz; ++in, ++out, ++sz)
494 *out = (*in == '-') ? '_' : (isalpha(*in) && !isupper(*in)) ? *in + 'A' - 'a': *in;
499 size_t util_strtononcmd(const char *in, char *out, size_t outsz) {
501 for (; *in && sz < outsz; ++in, ++out, ++sz)
502 *out = (*in == '_') ? '-' : (isalpha(*in) && isupper(*in)) ? *in + 'a' - 'A' : *in;
508 FILE *util_fopen(const char *filename, const char *mode)
512 if (fopen_s(&out, filename, mode) != 0)
516 return fopen(filename, mode);
520 void _util_vec_grow(void **a, size_t i, size_t s) {
521 size_t m = *a ? 2*_vec_beg(*a)+i : i+1;
522 void *p = mem_r((*a ? _vec_raw(*a) : NULL), s * m + sizeof(size_t)*2);
525 *a = (void*)((size_t*)p + 2);
530 * Hash table for generic data, based on dynamic memory allocations
531 * all around. This is the internal interface, please look for
532 * EXPOSED INTERFACE comment below
534 typedef struct hash_node_t {
535 char *key; /* the key for this node in table */
536 void *value; /* pointer to the data as void* */
537 struct hash_node_t *next; /* next node (linked list) */
540 GMQCC_INLINE size_t util_hthash(hash_table_t *ht, const char *key) {
541 const uint32_t mix = 0x5BD1E995;
542 const uint32_t rot = 24;
543 size_t size = strlen(key);
544 uint32_t hash = 0x1EF0 /* LICRC TAB */ ^ size;
546 const unsigned char *data = (const unsigned char*)key;
549 alias = *(uint32_t*)data;
552 alias ^= alias >> rot;
563 case 3: hash ^= data[2] << 16;
564 case 2: hash ^= data[1] << 8;
565 case 1: hash ^= data[0];
573 return (size_t) (hash % ht->size);
576 hash_node_t *_util_htnewpair(const char *key, void *value) {
578 if (!(node = mem_a(sizeof(hash_node_t))))
581 if (!(node->key = util_strdup(key))) {
593 * EXPOSED INTERFACE for the hashtable implementation
594 * util_htnew(size) -- to make a new hashtable
595 * util_htset(table, key, value, sizeof(value)) -- to set something in the table
596 * util_htget(table, key) -- to get something from the table
597 * util_htdel(table) -- to delete the table
599 hash_table_t *util_htnew(size_t size) {
600 hash_table_t *hashtable = NULL;
604 if (!(hashtable = mem_a(sizeof(hash_table_t))))
607 if (!(hashtable->table = mem_a(sizeof(hash_node_t*) * size))) {
612 hashtable->size = size;
613 memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
618 void util_htseth(hash_table_t *ht, const char *key, size_t bin, void *value) {
619 hash_node_t *newnode = NULL;
620 hash_node_t *next = NULL;
621 hash_node_t *last = NULL;
623 next = ht->table[bin];
625 while (next && next->key && strcmp(key, next->key) > 0)
626 last = next, next = next->next;
628 /* already in table, do a replace */
629 if (next && next->key && strcmp(key, next->key) == 0) {
632 /* not found, grow a pair man :P */
633 newnode = _util_htnewpair(key, value);
634 if (next == ht->table[bin]) {
635 newnode->next = next;
636 ht->table[bin] = newnode;
638 last->next = newnode;
640 newnode->next = next;
641 last->next = newnode;
646 void util_htset(hash_table_t *ht, const char *key, void *value) {
647 util_htseth(ht, key, util_hthash(ht, key), value);
650 void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
651 hash_node_t *pair = ht->table[bin];
653 while (pair && pair->key && strcmp(key, pair->key) > 0)
656 if (!pair || !pair->key || strcmp(key, pair->key) != 0)
662 void *util_htget(hash_table_t *ht, const char *key) {
663 return util_htgeth(ht, key, util_hthash(ht, key));
667 * Free all allocated data in a hashtable, this is quite the amount
670 void util_htdel(hash_table_t *ht) {
672 for (; i < ht->size; i++) {
673 hash_node_t *n = ht->table[i];