2 * Copyright (C) 2012, 2013
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
28 void util_debug(const char *area, const char *ms, ...) {
30 if (!OPTS_OPTION_BOOL(OPTION_DEBUG))
33 if (!strcmp(area, "MEM") && !OPTS_OPTION_BOOL(OPTION_MEMCHK))
37 con_out ("[%s] ", area);
43 * only required if big endian .. otherwise no need to swap
46 #if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_BIG
47 static GMQCC_INLINE void util_swap16(uint16_t *d, size_t l) {
49 d[l] = (d[l] << 8) | (d[l] >> 8);
53 static GMQCC_INLINE void util_swap32(uint32_t *d, size_t l) {
56 v = ((d[l] << 8) & 0xFF00FF00) | ((d[l] >> 8) & 0x00FF00FF);
57 d[l] = (v << 16) | (v >> 16);
61 /* Some strange system doesn't like constants that big, AND doesn't recognize an ULL suffix
62 * so let's go the safe way
64 static GMQCC_INLINE void util_swap64(uint32_t *d, size_t l) {
68 v = ((d[l] << 8) & 0xFF00FF00FF00FF00) | ((d[l] >> 8) & 0x00FF00FF00FF00FF);
69 v = ((v << 16) & 0xFFFF0000FFFF0000) | ((v >> 16) & 0x0000FFFF0000FFFF);
70 d[l] = (v << 32) | (v >> 32);
74 for (i = 0; i < l; i += 2) {
83 void util_endianswap(void *_data, size_t length, unsigned int typesize) {
84 # if PLATFORM_BYTE_ORDER == -1 /* runtime check */
85 if (*((char*)&typesize))
88 /* prevent unused warnings */
93 # if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_LITTLE
99 util_swap16((uint16_t*)_data, length>>1);
102 util_swap32((uint32_t*)_data, length>>2);
105 util_swap64((uint32_t*)_data, length>>3);
108 default: exit(EXIT_FAILURE); /* please blow the fuck up! */
115 * CRC algorithms vary in the width of the polynomial, the value of said polynomial,
116 * the initial value used for the register, weather the bits of each byte are reflected
117 * before being processed, weather the algorithm itself feeds input bytes through the
118 * register or XORs them with a byte from one end and then straight into the table, as
119 * well as (but not limited to the idea of reflected versions) where the final register
120 * value becomes reversed, and finally weather the value itself is used to XOR the final
121 * register value. AS such you can already imagine how painfully annoying CRCs are,
122 * of course we stand to target Quake, which expects it's certian set of rules for proper
123 * calculation of a CRC.
125 * In most traditional CRC algorithms on uses a reflected table driven method where a value
126 * or register is reflected if it's bits are swapped around it's center. For example:
127 * take the bits 0101 is the 4-bit reflection of 1010, and respectfully 0011 would be the
128 * reflection of 1100. Quake however expects a NON-Reflected CRC on the output, but still
129 * requires a final XOR on the values (0xFFFF and 0x0000) this is a standard CCITT CRC-16
130 * which I respectfully as a programmer don't agree with.
132 * So now you know what we target, and why we target it, despite how unsettling it may seem
133 * but those are what Quake seems to request.
136 static const uint16_t util_crc16_table[] = {
137 0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5,
138 0x60C6, 0x70E7, 0x8108, 0x9129, 0xA14A, 0xB16B,
139 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF, 0x1231, 0x0210,
140 0x3273, 0x2252, 0x52B5, 0x4294, 0x72F7, 0x62D6,
141 0x9339, 0x8318, 0xB37B, 0xA35A, 0xD3BD, 0xC39C,
142 0xF3FF, 0xE3DE, 0x2462, 0x3443, 0x0420, 0x1401,
143 0x64E6, 0x74C7, 0x44A4, 0x5485, 0xA56A, 0xB54B,
144 0x8528, 0x9509, 0xE5EE, 0xF5CF, 0xC5AC, 0xD58D,
145 0x3653, 0x2672, 0x1611, 0x0630, 0x76D7, 0x66F6,
146 0x5695, 0x46B4, 0xB75B, 0xA77A, 0x9719, 0x8738,
147 0xF7DF, 0xE7FE, 0xD79D, 0xC7BC, 0x48C4, 0x58E5,
148 0x6886, 0x78A7, 0x0840, 0x1861, 0x2802, 0x3823,
149 0xC9CC, 0xD9ED, 0xE98E, 0xF9AF, 0x8948, 0x9969,
150 0xA90A, 0xB92B, 0x5AF5, 0x4AD4, 0x7AB7, 0x6A96,
151 0x1A71, 0x0A50, 0x3A33, 0x2A12, 0xDBFD, 0xCBDC,
152 0xFBBF, 0xEB9E, 0x9B79, 0x8B58, 0xBB3B, 0xAB1A,
153 0x6CA6, 0x7C87, 0x4CE4, 0x5CC5, 0x2C22, 0x3C03,
154 0x0C60, 0x1C41, 0xEDAE, 0xFD8F, 0xCDEC, 0xDDCD,
155 0xAD2A, 0xBD0B, 0x8D68, 0x9D49, 0x7E97, 0x6EB6,
156 0x5ED5, 0x4EF4, 0x3E13, 0x2E32, 0x1E51, 0x0E70,
157 0xFF9F, 0xEFBE, 0xDFDD, 0xCFFC, 0xBF1B, 0xAF3A,
158 0x9F59, 0x8F78, 0x9188, 0x81A9, 0xB1CA, 0xA1EB,
159 0xD10C, 0xC12D, 0xF14E, 0xE16F, 0x1080, 0x00A1,
160 0x30C2, 0x20E3, 0x5004, 0x4025, 0x7046, 0x6067,
161 0x83B9, 0x9398, 0xA3FB, 0xB3DA, 0xC33D, 0xD31C,
162 0xE37F, 0xF35E, 0x02B1, 0x1290, 0x22F3, 0x32D2,
163 0x4235, 0x5214, 0x6277, 0x7256, 0xB5EA, 0xA5CB,
164 0x95A8, 0x8589, 0xF56E, 0xE54F, 0xD52C, 0xC50D,
165 0x34E2, 0x24C3, 0x14A0, 0x0481, 0x7466, 0x6447,
166 0x5424, 0x4405, 0xA7DB, 0xB7FA, 0x8799, 0x97B8,
167 0xE75F, 0xF77E, 0xC71D, 0xD73C, 0x26D3, 0x36F2,
168 0x0691, 0x16B0, 0x6657, 0x7676, 0x4615, 0x5634,
169 0xD94C, 0xC96D, 0xF90E, 0xE92F, 0x99C8, 0x89E9,
170 0xB98A, 0xA9AB, 0x5844, 0x4865, 0x7806, 0x6827,
171 0x18C0, 0x08E1, 0x3882, 0x28A3, 0xCB7D, 0xDB5C,
172 0xEB3F, 0xFB1E, 0x8BF9, 0x9BD8, 0xABBB, 0xBB9A,
173 0x4A75, 0x5A54, 0x6A37, 0x7A16, 0x0AF1, 0x1AD0,
174 0x2AB3, 0x3A92, 0xFD2E, 0xED0F, 0xDD6C, 0xCD4D,
175 0xBDAA, 0xAD8B, 0x9DE8, 0x8DC9, 0x7C26, 0x6C07,
176 0x5C64, 0x4C45, 0x3CA2, 0x2C83, 0x1CE0, 0x0CC1,
177 0xEF1F, 0xFF3E, 0xCF5D, 0xDF7C, 0xAF9B, 0xBFBA,
178 0x8FD9, 0x9FF8, 0x6E17, 0x7E36, 0x4E55, 0x5E74,
179 0x2E93, 0x3EB2, 0x0ED1, 0x1EF0
182 /* Non - Reflected */
183 uint16_t util_crc16(uint16_t current, const char *k, size_t len) {
184 register uint16_t h = current;
185 for (; len; --len, ++k)
186 h = util_crc16_table[(h>>8)^((unsigned char)*k)]^(h<<8);
189 /* Reflective Varation (for reference) */
191 uint16_t util_crc16(const char *k, int len, const short clamp) {
192 register uint16_t h= (uint16_t)0xFFFFFFFF;
193 for (; len; --len, ++k)
194 h = util_crc16_table[(h^((unsigned char)*k))&0xFF]^(h>>8);
199 size_t util_strtocmd(const char *in, char *out, size_t outsz) {
201 for (; *in && sz < outsz; ++in, ++out, ++sz)
202 *out = (*in == '-') ? '_' : (isalpha(*in) && !isupper(*in)) ? *in + 'A' - 'a': *in;
207 size_t util_strtononcmd(const char *in, char *out, size_t outsz) {
209 for (; *in && sz < outsz; ++in, ++out, ++sz)
210 *out = (*in == '_') ? '-' : (isalpha(*in) && isupper(*in)) ? *in + 'a' - 'A' : *in;
216 * Portable implementation of vasprintf/asprintf. Assumes vsnprintf
217 * exists, otherwise compiler error.
219 * TODO: fix for MSVC ....
221 int util_vasprintf(char **dat, const char *fmt, va_list args) {
227 * For visuals tido _vsnprintf doesn't tell you the length of a
228 * formatted string if it overflows. However there is a MSVC
229 * intrinsic (which is documented wrong) called _vcsprintf which
230 * will return the required amount to allocate.
233 if ((len = _vscprintf(fmt, args)) < 0) {
238 tmp = (char*)mem_a(len + 1);
239 if ((ret = _vsnprintf_s(tmp, len+1, len+1, fmt, args)) != len) {
248 * For everything else we have a decent conformint vsnprintf that
249 * returns the number of bytes needed. We give it a try though on
250 * a short buffer, since efficently speaking, it could be nice to
251 * above a second vsnprintf call.
256 len = vsnprintf(buf, sizeof(buf), fmt, cpy);
259 if (len < (int)sizeof(buf)) {
260 *dat = util_strdup(buf);
264 /* not large enough ... */
265 tmp = (char*)mem_a(len + 1);
266 if ((ret = vsnprintf(tmp, len + 1, fmt, args)) != len) {
276 int util_asprintf(char **ret, const char *fmt, ...) {
280 read = util_vasprintf(ret, fmt, args);
287 * These are various re-implementations (wrapping the real ones) of
288 * string functions that MSVC consideres unsafe. We wrap these up and
289 * use the safe varations on MSVC.
292 static char **util_strerror_allocated() {
293 static char **data = NULL;
297 static void util_strerror_cleanup(void) {
299 char **data = util_strerror_allocated();
300 for (i = 0; i < vec_size(data); i++)
305 const char *util_strerror(int num) {
306 char *allocated = NULL;
307 static bool install = false;
308 static size_t tries = 0;
309 char **vector = util_strerror_allocated();
311 /* try installing cleanup handler */
316 install = !atexit(&util_strerror_cleanup);
320 allocated = (char*)mem_a(4096); /* A page must be enough */
321 strerror_s(allocated, 4096, num);
323 vec_push(vector, allocated);
324 return (const char *)allocated;
327 int util_snprintf(char *src, size_t bytes, const char *format, ...) {
330 va_start(va, format);
332 rt = vsprintf_s(src, bytes, format, va);
338 char *util_strcat(char *dest, const char *src) {
339 strcat_s(dest, strlen(src), src);
343 char *util_strncpy(char *dest, const char *src, size_t num) {
344 strncpy_s(dest, num, src, num);
348 const char *util_strerror(int num) {
349 return strerror(num);
352 int util_snprintf(char *src, size_t bytes, const char *format, ...) {
355 va_start(va, format);
356 rt = vsnprintf(src, bytes, format, va);
362 char *util_strcat(char *dest, const char *src) {
363 return strcat(dest, src);
366 char *util_strncpy(char *dest, const char *src, size_t num) {
367 return strncpy(dest, src, num);
370 #endif /*! _MSC_VER */
373 * Implementation of the Mersenne twister PRNG (pseudo random numer
374 * generator). Implementation of MT19937. Has a period of 2^19937-1
375 * which is a Mersenne Prime (hence the name).
377 * Implemented from specification and original paper:
378 * http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf
380 * This code is placed in the public domain by me personally
381 * (Dale Weiler, a.k.a graphitemaster).
385 #define MT_PERIOD 397
386 #define MT_SPACE (MT_SIZE - MT_PERIOD)
388 static uint32_t mt_state[MT_SIZE];
389 static size_t mt_index = 0;
391 static GMQCC_INLINE void mt_generate() {
393 * The loop has been unrolled here: the original paper and implemenation
394 * Called for the following code:
395 * for (register unsigned i = 0; i < MT_SIZE; ++i) {
396 * register uint32_t load;
397 * load = (0x80000000 & mt_state[i]) // most significant 32nd bit
398 * load |= (0x7FFFFFFF & mt_state[(i + 1) % MT_SIZE]) // least significant 31nd bit
400 * mt_state[i] = mt_state[(i + MT_PERIOD) % MT_SIZE] ^ (load >> 1);
402 * if (load & 1) mt_state[i] ^= 0x9908B0DF;
405 * This essentially is a waste: we have two modulus operations, and
406 * a branch that is executed every iteration from [0, MT_SIZE).
408 * Please see: http://www.quadibloc.com/crypto/co4814.htm for more
409 * information on how this clever trick works.
411 static const uint32_t matrix[2] = {
416 * This register gives up a little more speed by instructing the compiler
417 * to force these into CPU registers (they're counters for indexing mt_state
418 * which we can force the compiler to generate prefetch instructions for)
424 * Said loop has been unrolled for MT_SPACE (226 iterations), opposed
425 * to [0, MT_SIZE) (634 iterations).
427 for (i = 0; i < MT_SPACE; ++i) {
428 y = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
429 mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1];
431 i ++; /* loop unroll */
433 y = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
434 mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1];
438 * collapsing the walls unrolled (evenly dividing 396 [632-227 = 396
442 while (i < MT_SIZE - 1) {
444 * We expand this 11 times .. manually, no macros are required
445 * here. This all fits in the CPU cache.
447 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
448 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
450 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
451 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
453 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
454 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
456 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
457 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
459 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
460 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
462 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
463 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
465 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
466 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
468 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
469 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
471 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
472 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
474 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
475 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
477 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
478 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
482 /* i = mt_state[623] */
483 y = (0x80000000 & mt_state[MT_SIZE - 1]) | (0x7FFFFFFF & mt_state[MT_SIZE - 1]);
484 mt_state[MT_SIZE - 1] = mt_state[MT_PERIOD - 1] ^ (y >> 1) ^ matrix[y & 1];
487 void util_seed(uint32_t value) {
489 * We seed the mt_state with a LCG (linear congruential generator)
490 * We're operating exactly on exactly m=32, so there is no need to
493 * The multipler of choice is 0x6C07865, also knows as the Borosh-
494 * Niederreiter multipler used for modulus 2^32. More can be read
495 * about this in Knuth's TAOCP Volume 2, page 106.
497 * If you don't own TAOCP something is wrong with you :-) .. so I
498 * also provided a link to the original paper by Borosh and
499 * Niederreiter. It's called "Optional Multipliers for PRNG by The
500 * Linear Congruential Method" (1983).
501 * http://en.wikipedia.org/wiki/Linear_congruential_generator
503 * From said page, it says the following:
504 * "A common Mersenne twister implementation, interestingly enough
505 * used an LCG to generate seed data."
508 * The data we're operating on is 32-bits for the mt_state array, so
509 * there is no masking required with 0xFFFFFFFF
514 for (i = 1; i < MT_SIZE; ++i)
515 mt_state[i] = 0x6C078965 * (mt_state[i - 1] ^ mt_state[i - 1] >> 30) + i;
518 uint32_t util_rand() {
522 * This is inlined with any sane compiler (I checked)
523 * for some reason though, SubC seems to be generating invalid
524 * code when it inlines this.
529 y = mt_state[mt_index];
531 /* Standard tempering */
532 y ^= y >> 11; /* +7 */
533 y ^= y << 7 & 0x9D2C5680; /* +4 */
534 y ^= y << 15 & 0xEFC60000; /* -4 */
535 y ^= y >> 18; /* -7 */
537 if(++mt_index == MT_SIZE)