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:
12 * The above copyright notice and this permission notice shall be included in all
13 * copies or substantial portions of the Software.
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
36 struct memblock_t *next;
37 struct memblock_t *prev;
40 static struct memblock_t *mem_start = NULL;
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;
50 info->next = mem_start;
52 mem_start->prev = info;
55 util_debug("MEM", "allocation: % 8u (bytes) address 0x%08X @ %s:%u\n", byte, data, file, line);
62 void util_memory_d(void *ptrn, unsigned int line, const char *file) {
63 struct memblock_t *info = NULL;
66 info = ((struct memblock_t*)ptrn - 1);
68 util_debug("MEM", "released: % 8u (bytes) address 0x%08X @ %s:%u\n", info->byte, ptrn, file, line);
73 info->prev->next = info->next;
75 info->next->prev = info->prev;
76 if (info == mem_start)
77 mem_start = info->next;
82 void *util_memory_r(void *ptrn, size_t byte, unsigned int line, const char *file) {
83 struct memblock_t *oldinfo = NULL;
85 struct memblock_t *newinfo;
88 return util_memory_a(byte, line, file);
90 util_memory_d(ptrn, line, file);
94 oldinfo = ((struct memblock_t*)ptrn - 1);
95 newinfo = ((struct memblock_t*)malloc(sizeof(struct memblock_t) + byte));
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);
101 util_memory_d(oldinfo+1, line, file);
106 memcpy(newinfo+1, oldinfo+1, oldinfo->byte);
110 oldinfo->prev->next = oldinfo->next;
112 oldinfo->next->prev = oldinfo->prev;
113 if (oldinfo == mem_start)
114 mem_start = oldinfo->next;
117 newinfo->line = line;
118 newinfo->byte = byte;
119 newinfo->file = file;
120 newinfo->prev = NULL;
121 newinfo->next = mem_start;
123 mem_start->prev = newinfo;
126 mem_ab -= oldinfo->byte;
127 mem_ab += newinfo->byte;
134 void util_meminfo() {
135 struct memblock_t *info;
140 for (info = mem_start; info; info = info->next) {
141 util_debug("MEM", "lost: % 8u (bytes) at %s:%u\n",
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",
161 * Some string utility functions, because strdup uses malloc, and we want
162 * to track all memory (without replacing malloc).
164 char *util_strdup(const char *s) {
171 if ((len = strlen(s)) && (ptr = mem_a(len+1))) {
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)
183 char *util_strrq(const char *s) {
184 char *dst = (char*)s;
185 char *src = (char*)s;
187 while ((chr = *src++) != '\0') {
190 if ((chr = *src++) == '\0')
193 } else if (chr != '"')
201 * Chops a substring from an existing string by creating a
202 * copy of it and null terminating it at the required position.
204 char *util_strchp(const char *s, const char *e) {
205 const char *c = NULL;
213 return util_strdup(s);
217 * Returns true if string is all uppercase, otherwise
220 bool util_strupper(const char *str) {
230 * Returns true if string is all digits, otherwise
233 bool util_strdigit(const char *str) {
242 bool util_strncmpexact(const char *src, const char *ned, size_t len) {
243 return (!strncmp(src, ned, len) && !src[len]);
246 void util_debug(const char *area, const char *ms, ...) {
251 if (!strcmp(area, "MEM") && !opts_memchk)
255 con_out ("[%s] ", area);
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.
265 void util_endianswap(void *m, int s, int l) {
269 /* ignore if we're already LE */
274 for(; i < s << 1; i++) {
275 unsigned char *p = (unsigned char *)m+w*s;
276 unsigned char t = p[i];
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.
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.
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.
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.
309 * CRC32 Polynomial: 0xEDB88320
310 * CRC16 Polynomial: 0x00001021
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
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
404 * Implements a CRC function for X worth bits using (uint[X]_t)
405 * as type. and util_crc[X]_table.
407 * Quake expects a non-reflective CRC.
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); \
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); \
431 * Implements libc getline for systems that don't have it, which is
432 * assmed all. This works the same as getline().
434 int util_getline(char **lineptr, size_t *n, FILE *stream) {
439 if (!lineptr || !n || !stream)
442 if (!(*lineptr = (char*)mem_a((*n=64))))
450 int c = getc(stream);
453 char *tmp = (char*)mem_a((*n+=(*n>16)?*n:64));
457 memcpy(tmp, *lineptr, pos - *lineptr);
458 chr = *n + *lineptr - pos;
459 if (!(*lineptr = tmp)) {
463 pos = *n - chr + *lineptr;
481 return (ret = pos - *lineptr);
484 size_t util_strtocmd(const char *in, char *out, size_t outsz) {
486 for (; *in && sz < outsz; ++in, ++out, ++sz) {
489 else if (isalpha(*in) && !isupper(*in))
490 *out = *in + 'A' - 'a';
498 size_t util_strtononcmd(const char *in, char *out, size_t outsz) {
500 for (; *in && sz < outsz; ++in, ++out, ++sz) {
503 else if (isalpha(*in) && isupper(*in))
504 *out = *in + 'a' - 'A';
512 FILE *util_fopen(const char *filename, const char *mode)
516 if (fopen_s(&out, filename, mode) != 0)
520 return fopen(filename, mode);
524 bool util_filexists(const char *file) {
525 FILE *fp = fopen(file, "rb");
526 if (!fp) return false;
533 void _util_vec_grow(void **a, size_t i, size_t s) {
534 size_t m = *a ? 2*_vec_beg(*a)+i : i+1;
535 void *p = mem_r((*a ? _vec_raw(*a) : NULL), s * m + sizeof(size_t)*2);
538 *a = (void*)((size_t*)p + 2);