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 = 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);
104 newinfo->line = line;
105 newinfo->byte = byte;
106 newinfo->file = file;
107 newinfo->next = oldinfo->next;
108 newinfo->prev = oldinfo->prev;
110 newinfo->next->prev = newinfo;
112 newinfo->prev->next = newinfo;
113 if (mem_start == oldinfo)
117 memcpy(newinfo+1, oldinfo+1, oldinfo->byte);
120 mem_db += newinfo->byte;
121 mem_db -= oldinfo->byte;
128 void util_meminfo() {
129 struct memblock_t *info;
134 for (info = mem_start; info; info = info->next) {
135 util_debug("MEM", "lost: % 8u (bytes) at %s:%u\n",
141 util_debug("MEM", "Memory information:\n\
142 Total allocations: %llu\n\
143 Total deallocations: %llu\n\
144 Total allocated: %llu (bytes)\n\
145 Total deallocated: %llu (bytes)\n\
146 Leaks found: lost %llu (bytes) in %d allocations\n",
155 * Some string utility functions, because strdup uses malloc, and we want
156 * to track all memory (without replacing malloc).
158 char *util_strdup(const char *s) {
165 if ((len = strlen(s)) && (ptr = mem_a(len+1))) {
173 * Remove quotes from a string, escapes from \ in string
174 * as well. This function shouldn't be used to create a
175 * char array that is later freed (it uses pointer arith)
177 char *util_strrq(const char *s) {
178 char *dst = (char*)s;
179 char *src = (char*)s;
181 while ((chr = *src++) != '\0') {
184 if ((chr = *src++) == '\0')
187 } else if (chr != '"')
195 * Chops a substring from an existing string by creating a
196 * copy of it and null terminating it at the required position.
198 char *util_strchp(const char *s, const char *e) {
199 const char *c = NULL;
207 return util_strdup(s);
211 * Returns true if string is all uppercase, otherwise
214 bool util_strupper(const char *str) {
224 * Returns true if string is all digits, otherwise
227 bool util_strdigit(const char *str) {
236 bool util_strncmpexact(const char *src, const char *ned, size_t len) {
237 return (!strncmp(src, ned, len) && !src[len]);
240 void util_debug(const char *area, const char *ms, ...) {
245 if (!strcmp(area, "MEM") && !opts_memchk)
249 con_out ("[%s] ", area);
255 * Endianess swapping, all data must be stored little-endian. This
256 * reorders by stride and length, much nicer than other functions for
257 * certian-sized types like short or int.
259 void util_endianswap(void *m, int s, int l) {
263 /* ignore if we're already LE */
268 for(; i < s << 1; i++) {
269 unsigned char *p = (unsigned char *)m+w*s;
270 unsigned char t = p[i];
278 * CRC algorithms vary in the width of the polynomial, the value of said polynomial,
279 * the initial value used for the register, weather the bits of each byte are reflected
280 * before being processed, weather the algorithm itself feeds input bytes through the
281 * register or XORs them with a byte from one end and then straight into the table, as
282 * well as (but not limited to the idea of reflected versions) where the final register
283 * value becomes reversed, and finally weather the value itself is used to XOR the final
284 * register value. AS such you can already imagine how painfully annoying CRCs are,
285 * of course we stand to target Quake, which expects it's certian set of rules for proper
286 * calculation of a CRC.
288 * In most traditional CRC algorithms on uses a reflected table driven method where a value
289 * or register is reflected if it's bits are swapped around it's center. For example:
290 * take the bits 0101 is the 4-bit reflection of 1010, and respectfully 0011 would be the
291 * reflection of 1100. Quakle however expects a NON-Reflected CRC on the output, but still
292 * requires a final XOR on the values (0xFFFF and 0x0000) this is a standard CCITT CRC-16
293 * which I respectfully as a programmer don't agree with.
295 * So now you know what we target, and why we target it, despite how unsettling it may seem
296 * but those are what Quake seems to request.
300 * This is an implementation of CRC32 & CRC16. The polynomials have been
301 * offline computed for faster generation at the cost of larger code size.
303 * CRC32 Polynomial: 0xEDB88320
304 * CRC16 Polynomial: 0x00001021
306 static const uint32_t util_crc32_table[] = {
307 0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F,
308 0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
309 0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91, 0x1DB71064, 0x6AB020F2,
310 0xF3B97148, 0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
311 0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9,
312 0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172,
313 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, 0x35B5A8FA, 0x42B2986C,
314 0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59,
315 0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423,
316 0xCFBA9599, 0xB8BDA50F, 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
317 0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 0x76DC4190, 0x01DB7106,
318 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433,
319 0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D,
320 0x91646C97, 0xE6635C01, 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E,
321 0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950,
322 0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65,
323 0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7,
324 0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0,
325 0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C, 0x270241AA,
326 0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
327 0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81,
328 0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A,
329 0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683, 0xE3630B12, 0x94643B84,
330 0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
331 0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB,
332 0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC,
333 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, 0xD6D6A3E8, 0xA1D1937E,
334 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
335 0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55,
336 0x316E8EEF, 0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
337 0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 0xC5BA3BBE, 0xB2BD0B28,
338 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D,
339 0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F,
340 0x72076785, 0x05005713, 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38,
341 0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242,
342 0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777,
343 0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69,
344 0x616BFFD3, 0x166CCF45, 0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2,
345 0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC,
346 0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
347 0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693,
348 0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94,
349 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
351 static const uint16_t util_crc16_table[] = {
352 0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5,
353 0x60C6, 0x70E7, 0x8108, 0x9129, 0xA14A, 0xB16B,
354 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF, 0x1231, 0x0210,
355 0x3273, 0x2252, 0x52B5, 0x4294, 0x72F7, 0x62D6,
356 0x9339, 0x8318, 0xB37B, 0xA35A, 0xD3BD, 0xC39C,
357 0xF3FF, 0xE3DE, 0x2462, 0x3443, 0x0420, 0x1401,
358 0x64E6, 0x74C7, 0x44A4, 0x5485, 0xA56A, 0xB54B,
359 0x8528, 0x9509, 0xE5EE, 0xF5CF, 0xC5AC, 0xD58D,
360 0x3653, 0x2672, 0x1611, 0x0630, 0x76D7, 0x66F6,
361 0x5695, 0x46B4, 0xB75B, 0xA77A, 0x9719, 0x8738,
362 0xF7DF, 0xE7FE, 0xD79D, 0xC7BC, 0x48C4, 0x58E5,
363 0x6886, 0x78A7, 0x0840, 0x1861, 0x2802, 0x3823,
364 0xC9CC, 0xD9ED, 0xE98E, 0xF9AF, 0x8948, 0x9969,
365 0xA90A, 0xB92B, 0x5AF5, 0x4AD4, 0x7AB7, 0x6A96,
366 0x1A71, 0x0A50, 0x3A33, 0x2A12, 0xDBFD, 0xCBDC,
367 0xFBBF, 0xEB9E, 0x9B79, 0x8B58, 0xBB3B, 0xAB1A,
368 0x6CA6, 0x7C87, 0x4CE4, 0x5CC5, 0x2C22, 0x3C03,
369 0x0C60, 0x1C41, 0xEDAE, 0xFD8F, 0xCDEC, 0xDDCD,
370 0xAD2A, 0xBD0B, 0x8D68, 0x9D49, 0x7E97, 0x6EB6,
371 0x5ED5, 0x4EF4, 0x3E13, 0x2E32, 0x1E51, 0x0E70,
372 0xFF9F, 0xEFBE, 0xDFDD, 0xCFFC, 0xBF1B, 0xAF3A,
373 0x9F59, 0x8F78, 0x9188, 0x81A9, 0xB1CA, 0xA1EB,
374 0xD10C, 0xC12D, 0xF14E, 0xE16F, 0x1080, 0x00A1,
375 0x30C2, 0x20E3, 0x5004, 0x4025, 0x7046, 0x6067,
376 0x83B9, 0x9398, 0xA3FB, 0xB3DA, 0xC33D, 0xD31C,
377 0xE37F, 0xF35E, 0x02B1, 0x1290, 0x22F3, 0x32D2,
378 0x4235, 0x5214, 0x6277, 0x7256, 0xB5EA, 0xA5CB,
379 0x95A8, 0x8589, 0xF56E, 0xE54F, 0xD52C, 0xC50D,
380 0x34E2, 0x24C3, 0x14A0, 0x0481, 0x7466, 0x6447,
381 0x5424, 0x4405, 0xA7DB, 0xB7FA, 0x8799, 0x97B8,
382 0xE75F, 0xF77E, 0xC71D, 0xD73C, 0x26D3, 0x36F2,
383 0x0691, 0x16B0, 0x6657, 0x7676, 0x4615, 0x5634,
384 0xD94C, 0xC96D, 0xF90E, 0xE92F, 0x99C8, 0x89E9,
385 0xB98A, 0xA9AB, 0x5844, 0x4865, 0x7806, 0x6827,
386 0x18C0, 0x08E1, 0x3882, 0x28A3, 0xCB7D, 0xDB5C,
387 0xEB3F, 0xFB1E, 0x8BF9, 0x9BD8, 0xABBB, 0xBB9A,
388 0x4A75, 0x5A54, 0x6A37, 0x7A16, 0x0AF1, 0x1AD0,
389 0x2AB3, 0x3A92, 0xFD2E, 0xED0F, 0xDD6C, 0xCD4D,
390 0xBDAA, 0xAD8B, 0x9DE8, 0x8DC9, 0x7C26, 0x6C07,
391 0x5C64, 0x4C45, 0x3CA2, 0x2C83, 0x1CE0, 0x0CC1,
392 0xEF1F, 0xFF3E, 0xCF5D, 0xDF7C, 0xAF9B, 0xBFBA,
393 0x8FD9, 0x9FF8, 0x6E17, 0x7E36, 0x4E55, 0x5E74,
394 0x2E93, 0x3EB2, 0x0ED1, 0x1EF0
398 * Implements a CRC function for X worth bits using (uint[X]_t)
399 * as type. and util_crc[X]_table.
401 * Quake expects a non-reflective CRC.
404 uint##X##_t util_crc##X(uint##X##_t current, const char *k, size_t len) { \
405 register uint##X##_t h= current; \
406 for (; len; --len, ++k) \
407 h = util_crc##X##_table[(h>>8)^((unsigned char)*k)]^(h<<8); \
415 uint##X##_t util_crc##X(const char *k, int len, const short clamp) { \
416 register uint##X##_t h= (uint##X##_t)0xFFFFFFFF; \
417 for (; len; --len, ++k) \
418 h = util_crc##X##_table[(h^((unsigned char)*k))&0xFF]^(h>>8); \
425 * Implements libc getline for systems that don't have it, which is
426 * assmed all. This works the same as getline().
428 int util_getline(char **lineptr, size_t *n, FILE *stream) {
433 if (!lineptr || !n || !stream)
436 if (!(*lineptr = (char*)mem_a((*n=64))))
444 int c = getc(stream);
447 char *tmp = (char*)mem_a((*n+=(*n>16)?*n:64));
451 memcpy(tmp, *lineptr, pos - *lineptr);
452 chr = *n + *lineptr - pos;
453 if (!(*lineptr = tmp)) {
457 pos = *n - chr + *lineptr;
475 return (ret = pos - *lineptr);
478 size_t util_strtocmd(const char *in, char *out, size_t outsz) {
480 for (; *in && sz < outsz; ++in, ++out, ++sz) {
483 else if (isalpha(*in) && !isupper(*in))
484 *out = *in + 'A' - 'a';
492 size_t util_strtononcmd(const char *in, char *out, size_t outsz) {
494 for (; *in && sz < outsz; ++in, ++out, ++sz) {
497 else if (isalpha(*in) && isupper(*in))
498 *out = *in + 'a' - 'A';
506 FILE *util_fopen(const char *filename, const char *mode)
510 if (fopen_s(&out, filename, mode) != 0)
514 return fopen(filename, mode);
518 void _util_vec_grow(void **a, size_t i, size_t s) {
519 size_t m = *a ? 2*_vec_beg(*a)+i : i+1;
520 void *p = mem_r((*a ? _vec_raw(*a) : NULL), s * m + sizeof(size_t)*2);
523 *a = (void*)((size_t*)p + 2);