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))) {
179 void util_debug(const char *area, const char *ms, ...) {
184 if (!strcmp(area, "MEM") && !opts.memchk)
188 con_out ("[%s] ", area);
194 * only required if big endian .. otherwise no need to swap
197 #if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_BIG
198 static void util_swap16(uint16_t *d, size_t l) {
200 d[l] = (d[l] << 8) | (d[l] >> 8);
204 static void util_swap32(uint32_t *d, size_t l) {
207 v = ((d[l] << 8) & 0xFF00FF00) | ((d[l] >> 8) & 0x00FF00FF);
208 d[l] = (v << 16) | (v >> 16);
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
215 static void util_swap64(uint32_t *d, size_t l) {
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);
225 for (i = 0; i < l; i += 2) {
234 void util_endianswap(void *_data, size_t length, unsigned int typesize) {
235 # if PLATFORM_BYTE_ORDER == -1 /* runtime check */
236 if (*((char*)&typesize))
239 /* prevent unused warnings */
244 # if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_LITTLE
250 util_swap16((uint16_t*)_data, length>>1);
253 util_swap32((uint32_t*)_data, length>>2);
256 util_swap64((uint32_t*)_data, length>>3);
259 default: abort(); /* please blow the fuck up! */
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.
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.
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.
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
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);
340 /* Reflective Varation (for reference) */
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);
351 * Implements libc getline for systems that don't have it, which is
352 * assmed all. This works the same as getline().
354 int util_getline(char **lineptr, size_t *n, FILE *stream) {
359 if (!lineptr || !n || !stream)
362 if (!(*lineptr = (char*)mem_a((*n=64))))
370 int c = getc(stream);
373 *n += (*n > 16) ? *n : 64;
374 chr = *n + *lineptr - pos;
375 if (!(*lineptr = (char*)mem_r(*lineptr,*n)))
377 pos = *n - chr + *lineptr;
395 return (ret = pos - *lineptr);
398 size_t util_strtocmd(const char *in, char *out, size_t outsz) {
400 for (; *in && sz < outsz; ++in, ++out, ++sz)
401 *out = (*in == '-') ? '_' : (isalpha(*in) && !isupper(*in)) ? *in + 'A' - 'a': *in;
406 size_t util_strtononcmd(const char *in, char *out, size_t outsz) {
408 for (; *in && sz < outsz; ++in, ++out, ++sz)
409 *out = (*in == '_') ? '-' : (isalpha(*in) && isupper(*in)) ? *in + 'a' - 'A' : *in;
415 FILE *util_fopen(const char *filename, const char *mode)
419 if (fopen_s(&out, filename, mode) != 0)
423 return fopen(filename, mode);
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);
432 *a = (void*)((size_t*)p + 2);
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
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) */
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;
453 const unsigned char *data = (const unsigned char*)key;
456 alias = *(uint32_t*)data;
459 alias ^= alias >> rot;
470 case 3: hash ^= data[2] << 16;
471 case 2: hash ^= data[1] << 8;
472 case 1: hash ^= data[0];
480 return (size_t) (hash % ht->size);
483 hash_node_t *_util_htnewpair(const char *key, void *value) {
485 if (!(node = mem_a(sizeof(hash_node_t))))
488 if (!(node->key = util_strdup(key))) {
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
506 hash_table_t *util_htnew(size_t size) {
507 hash_table_t *hashtable = NULL;
511 if (!(hashtable = mem_a(sizeof(hash_table_t))))
514 if (!(hashtable->table = mem_a(sizeof(hash_node_t*) * size))) {
519 hashtable->size = size;
520 memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
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;
530 next = ht->table[bin];
532 while (next && next->key && strcmp(key, next->key) > 0)
533 last = next, next = next->next;
535 /* already in table, do a replace */
536 if (next && next->key && strcmp(key, next->key) == 0) {
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;
545 last->next = newnode;
547 newnode->next = next;
548 last->next = newnode;
553 void util_htset(hash_table_t *ht, const char *key, void *value) {
554 util_htseth(ht, key, util_hthash(ht, key), value);
557 void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
558 hash_node_t *pair = ht->table[bin];
560 while (pair && pair->key && strcmp(key, pair->key) > 0)
563 if (!pair || !pair->key || strcmp(key, pair->key) != 0)
569 void *util_htget(hash_table_t *ht, const char *key) {
570 return util_htgeth(ht, key, util_hthash(ht, key));
574 * Free all allocated data in a hashtable, this is quite the amount
577 void util_htdel(hash_table_t *ht) {
579 for (; i < ht->size; i++) {
580 hash_node_t *n = ht->table[i];