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