util.c

   1 /*
   2  * Copyright (C) 2012, 2013
   3  *     Dale Weiler
   4  *     Wolfgang Bumiller
   5  *
   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:
  12  *
  13  * The above copyright notice and this permission notice shall be included in all
  14  * copies or substantial portions of the Software.
  15  *
  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
  22  * SOFTWARE.
  23  */
  24 #include <stdarg.h>
  25 #include <errno.h>
  26 #include "gmqcc.h"
  27
  28 void util_debug(const char *area, const char *ms, ...) {
  29     va_list  va;
  30     if (!OPTS_OPTION_BOOL(OPTION_DEBUG))
  31         return;
  32
  33     if (!strcmp(area, "MEM") && !OPTS_OPTION_BOOL(OPTION_MEMCHK))
  34         return;
  35
  36     va_start(va, ms);
  37     con_out ("[%s] ", area);
  38     con_vout(ms, va);
  39     va_end  (va);
  40 }
  41
  42 /*
  43  * only required if big endian .. otherwise no need to swap
  44  * data.
  45  */
  46 #if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_BIG
  47     static GMQCC_INLINE void util_swap16(uint16_t *d, size_t l) {
  48         while (l--) {
  49             d[l] = (d[l] << 8) | (d[l] >> 8);
  50         }
  51     }
  52
  53     static GMQCC_INLINE void util_swap32(uint32_t *d, size_t l) {
  54         while (l--) {
  55             uint32_t v;
  56             v = ((d[l] << 8) & 0xFF00FF00) | ((d[l] >> 8) & 0x00FF00FF);
  57             d[l] = (v << 16) | (v >> 16);
  58         }
  59     }
  60
  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
  63      */
  64     static GMQCC_INLINE void util_swap64(uint32_t *d, size_t l) {
  65         /*
  66         while (l--) {
  67             uint64_t v;
  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);
  71         }
  72         */
  73         size_t i;
  74         for (i = 0; i < l; i += 2) {
  75             uint32_t v1 = d[i];
  76             d[i] = d[i+1];
  77             d[i+1] = v1;
  78             util_swap32(d+i, 2);
  79         }
  80     }
  81 #endif
  82
  83 void util_endianswap(void *_data, size_t length, unsigned int typesize) {
  84 #   if PLATFORM_BYTE_ORDER == -1 /* runtime check */
  85     if (*((char*)&typesize))
  86         return;
  87 #else
  88     /* prevent unused warnings */
  89     (void) _data;
  90     (void) length;
  91     (void) typesize;
  92
  93 #   if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_LITTLE
  94         return;
  95 #   else
  96         switch (typesize) {
  97             case 1: return;
  98             case 2:
  99                 util_swap16((uint16_t*)_data, length>>1);
 100                 return;
 101             case 4:
 102                 util_swap32((uint32_t*)_data, length>>2);
 103                 return;
 104             case 8:
 105                 util_swap64((uint32_t*)_data, length>>3);
 106                 return;
 107
 108             default: exit(EXIT_FAILURE); /* please blow the fuck up! */
 109         }
 110 #   endif
 111 #endif
 112 }
 113
 114 /*
 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.
 124  *
 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.
 131  *
 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.
 134  */
 135
 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
 180 };
 181
 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);
 187     return h;
 188 }
 189 /* Reflective Varation (for reference) */
 190 #if 0
 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);
 195     return (~h)%clamp;
 196 }
 197 #endif
 198
 199 size_t util_strtocmd(const char *in, char *out, size_t outsz) {
 200     size_t sz = 1;
 201     for (; *in && sz < outsz; ++in, ++out, ++sz)
 202         *out = (*in == '-') ? '_' : (isalpha(*in) && !isupper(*in)) ? *in + 'A' - 'a': *in;
 203     *out = 0;
 204     return sz-1;
 205 }
 206
 207 size_t util_strtononcmd(const char *in, char *out, size_t outsz) {
 208     size_t sz = 1;
 209     for (; *in && sz < outsz; ++in, ++out, ++sz)
 210         *out = (*in == '_') ? '-' : (isalpha(*in) && isupper(*in)) ? *in + 'a' - 'A' : *in;
 211     *out = 0;
 212     return sz-1;
 213 }
 214
 215 /*
 216  * Portable implementation of vasprintf/asprintf. Assumes vsnprintf
 217  * exists, otherwise compiler error.
 218  *
 219  * TODO: fix for MSVC ....
 220  */
 221 int util_vasprintf(char **dat, const char *fmt, va_list args) {
 222     int   ret;
 223     int   len;
 224     char *tmp = NULL;
 225
 226     /*
 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.
 231      */
 232     #ifdef _MSC_VER
 233         if ((len = _vscprintf(fmt, args)) < 0) {
 234             *dat = NULL;
 235             return -1;
 236         }
 237
 238         tmp = (char*)mem_a(len + 1);
 239         if ((ret = _vsnprintf_s(tmp, len+1, len+1, fmt, args)) != len) {
 240             mem_d(tmp);
 241             *dat = NULL;
 242             return -1;
 243         }
 244         *dat = tmp;
 245         return len;
 246     #else
 247         /*
 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.
 252          */
 253         char    buf[128];
 254         va_list cpy;
 255         va_copy(cpy, args);
 256         len = vsnprintf(buf, sizeof(buf), fmt, cpy);
 257         va_end (cpy);
 258
 259         if (len < (int)sizeof(buf)) {
 260             *dat = util_strdup(buf);
 261             return len;
 262         }
 263
 264         /* not large enough ... */
 265         tmp = (char*)mem_a(len + 1);
 266         if ((ret = vsnprintf(tmp, len + 1, fmt, args)) != len) {
 267             mem_d(tmp);
 268             *dat = NULL;
 269             return -1;
 270         }
 271
 272         *dat = tmp;
 273         return len;
 274     #endif
 275 }
 276 int util_asprintf(char **ret, const char *fmt, ...) {
 277     va_list  args;
 278     int      read;
 279     va_start(args, fmt);
 280     read = util_vasprintf(ret, fmt, args);
 281     va_end  (args);
 282
 283     return read;
 284 }
 285
 286 /*
 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.
 290  */
 291 #ifdef _MSC_VER
 292     static char **util_strerror_allocated() {
 293         static char **data = NULL;
 294         return data;
 295     }
 296
 297     static void util_strerror_cleanup(void) {
 298         size_t i;
 299         char  **data = util_strerror_allocated();
 300         for (i = 0; i < vec_size(data); i++)
 301             mem_d(data[i]);
 302         vec_free(data);
 303     }
 304
 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();
 310
 311         /* try installing cleanup handler */
 312         while (!install) {
 313             if (tries == 32)
 314                 return "(unknown)";
 315
 316             install = !atexit(&util_strerror_cleanup);
 317             tries ++;
 318         }
 319
 320         allocated = (char*)mem_a(4096); /* A page must be enough */
 321         strerror_s(allocated, 4096, num);
 322
 323         vec_push(vector, allocated);
 324         return (const char *)allocated;
 325     }
 326
 327     int util_snprintf(char *src, size_t bytes, const char *format, ...) {
 328         int      rt;
 329         va_list  va;
 330         va_start(va, format);
 331
 332         rt = vsprintf_s(src, bytes, format, va);
 333         va_end  (va);
 334
 335         return rt;
 336     }
 337
 338     char *util_strcat(char *dest, const char *src) {
 339         strcat_s(dest, strlen(src), src);
 340         return dest;
 341     }
 342
 343     char *util_strncpy(char *dest, const char *src, size_t num) {
 344         strncpy_s(dest, num, src, num);
 345         return dest;
 346     }
 347 #else
 348     const char *util_strerror(int num) {
 349         return strerror(num);
 350     }
 351
 352     int util_snprintf(char *src, size_t bytes, const char *format, ...) {
 353         int      rt;
 354         va_list  va;
 355         va_start(va, format);
 356         rt = vsnprintf(src, bytes, format, va);
 357         va_end  (va);
 358
 359         return rt;
 360     }
 361
 362     char *util_strcat(char *dest, const char *src) {
 363         return strcat(dest, src);
 364     }
 365
 366     char *util_strncpy(char *dest, const char *src, size_t num) {
 367         return strncpy(dest, src, num);
 368     }
 369
 370 #endif /*! _MSC_VER */
 371
 372 /*
 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).
 376  *
 377  * Implemented from specification and original paper:
 378  * http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf
 379  *
 380  * This code is placed in the public domain by me personally
 381  * (Dale Weiler, a.k.a graphitemaster).
 382  */
 383
 384 #define MT_SIZE    624
 385 #define MT_PERIOD  397
 386 #define MT_SPACE   (MT_SIZE - MT_PERIOD)
 387
 388 static uint32_t mt_state[MT_SIZE];
 389 static size_t   mt_index = 0;
 390
 391 static GMQCC_INLINE void mt_generate() {
 392     /*
 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
 399      *
 400      *     mt_state[i] = mt_state[(i + MT_PERIOD) % MT_SIZE] ^ (load >> 1);
 401      *
 402      *     if (load & 1) mt_state[i] ^= 0x9908B0DF;
 403      * }
 404      *
 405      * This essentially is a waste: we have two modulus operations, and
 406      * a branch that is executed every iteration from [0, MT_SIZE).
 407      *
 408      * Please see: http://www.quadibloc.com/crypto/co4814.htm for more
 409      * information on how this clever trick works.
 410      */
 411     static const uint32_t matrix[2] = {
 412         0x00000000,
 413         0x9908B0Df
 414     };
 415     /*
 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)
 419      */
 420     register uint32_t y;
 421     register uint32_t i;
 422
 423     /*
 424      * Said loop has been unrolled for MT_SPACE (226 iterations), opposed
 425      * to [0, MT_SIZE)  (634 iterations).
 426      */
 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];
 430
 431         i ++; /* loop unroll */
 432
 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];
 435     }
 436
 437     /*
 438      * collapsing the walls unrolled (evenly dividing 396 [632-227 = 396
 439      * = 2*2*3*3*11])
 440      */
 441     i = MT_SPACE;
 442     while (i < MT_SIZE - 1) {
 443         /*
 444          * We expand this 11 times .. manually, no macros are required
 445          * here. This all fits in the CPU cache.
 446          */
 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];
 449         ++i;
 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];
 452         ++i;
 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];
 455         ++i;
 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];
 458         ++i;
 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];
 461         ++i;
 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];
 464         ++i;
 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];
 467         ++i;
 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];
 470         ++i;
 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];
 473         ++i;
 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];
 476         ++i;
 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];
 479         ++i;
 480     }
 481
 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];
 485 }
 486
 487 void util_seed(uint32_t value) {
 488     /*
 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
 491      * use modulus.
 492      *
 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.
 496      *
 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
 502      *
 503      * From said page, it says the following:
 504      * "A common Mersenne twister implementation, interestingly enough
 505      *  used an LCG to generate seed data."
 506      *
 507      * Remarks:
 508      * The data we're operating on is 32-bits for the mt_state array, so
 509      * there is no masking required with 0xFFFFFFFF
 510      */
 511     register size_t i;
 512
 513     mt_state[0] = value;
 514     for (i = 1; i < MT_SIZE; ++i)
 515         mt_state[i] = 0x6C078965 * (mt_state[i - 1] ^ mt_state[i - 1] >> 30) + i;
 516 }
 517
 518 uint32_t util_rand() {
 519     register uint32_t y;
 520
 521     /*
 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.
 525      */
 526     if (!mt_index)
 527         mt_generate();
 528
 529     y = mt_state[mt_index];
 530
 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 */
 536
 537     if(++mt_index == MT_SIZE)
 538          mt_index = 0;
 539
 540     return y;
 541 }