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 /* TODO: remove globals ... */
29 static uint64_t mem_ab = 0;
30 static uint64_t mem_db = 0;
31 static uint64_t mem_at = 0;
32 static uint64_t mem_dt = 0;
33 static uint64_t mem_pk = 0;
34 static uint64_t mem_hw = 0;
40 struct memblock_t *next;
41 struct memblock_t *prev;
46 if (mem_hw > mem_pk) \
50 static struct memblock_t *mem_start = NULL;
52 void *util_memory_a(size_t byte, unsigned int line, const char *file) {
53 struct memblock_t *info = (struct memblock_t*)malloc(sizeof(struct memblock_t) + byte);
54 void *data = (void*)(info+1);
55 if (!info) return NULL;
60 info->next = mem_start;
62 mem_start->prev = info;
74 void util_memory_d(void *ptrn) {
75 struct memblock_t *info = NULL;
78 info = ((struct memblock_t*)ptrn - 1);
85 info->prev->next = info->next;
87 info->next->prev = info->prev;
88 if (info == mem_start)
89 mem_start = info->next;
94 void *util_memory_r(void *ptrn, size_t byte, unsigned int line, const char *file) {
95 struct memblock_t *oldinfo = NULL;
97 struct memblock_t *newinfo;
100 return util_memory_a(byte, line, file);
106 oldinfo = ((struct memblock_t*)ptrn - 1);
107 newinfo = ((struct memblock_t*)malloc(sizeof(struct memblock_t) + byte));
111 util_memory_d(oldinfo+1);
116 memcpy(newinfo+1, oldinfo+1, oldinfo->byte);
120 oldinfo->prev->next = oldinfo->next;
122 oldinfo->next->prev = oldinfo->prev;
123 if (oldinfo == mem_start)
124 mem_start = oldinfo->next;
127 newinfo->line = line;
128 newinfo->byte = byte;
129 newinfo->file = file;
130 newinfo->prev = NULL;
131 newinfo->next = mem_start;
133 mem_start->prev = newinfo;
136 mem_ab -= oldinfo->byte;
137 mem_hw -= oldinfo->byte;
138 mem_ab += newinfo->byte;
139 mem_hw += newinfo->byte;
148 static void util_dumpmem(struct memblock_t *memory, uint16_t cols) {
150 for (i = 0; i < memory->byte + ((memory->byte % cols) ? (cols - memory->byte % cols) : 0); i++) {
151 if (i % cols == 0) con_out(" 0x%06X: ", i);
152 if (i < memory->byte) con_out("%02X " , 0xFF & ((char*)(memory + 1))[i]);
155 if ((uint16_t)(i % cols) == (cols - 1)) {
156 for (j = i - (cols - 1); j <= i; j++) {
160 : (isprint(((char*)(memory + 1))[j]))
161 ? 0xFF & ((char*)(memory + 1)) [j]
169 static uint64_t vectors = 0;
170 void util_meminfo() {
171 struct memblock_t *info;
173 if (OPTS_OPTION_BOOL(OPTION_DEBUG)) {
174 for (info = mem_start; info; info = info->next) {
175 con_out("lost: %u (bytes) at %s:%u\n",
180 util_dumpmem(info, OPTS_OPTION_U16(OPTION_MEMDUMPCOLS));
184 if (OPTS_OPTION_BOOL(OPTION_STATISTICS)) {
185 con_out("Additional Statistics:\n Total vectors used: %lu\n",
190 if (OPTS_OPTION_BOOL(OPTION_DEBUG) ||
191 OPTS_OPTION_BOOL(OPTION_MEMCHK)) {
192 con_out("Memory information:\n\
193 Total allocations: %llu\n\
194 Total deallocations: %llu\n\
195 Total allocated: %f (MB)\n\
196 Total deallocated: %f (MB)\n\
197 Total peak memory: %f (MB)\n\
198 Total leaked memory: %f (MB) in %llu allocations\n",
201 (float)(mem_ab) / 1048576.0f,
202 (float)(mem_db) / 1048576.0f,
203 (float)(mem_pk) / 1048576.0f,
204 (float)(mem_ab - mem_db) / 1048576.0f,
206 /* could be more clever */
213 * Some string utility functions, because strdup uses malloc, and we want
214 * to track all memory (without replacing malloc).
216 char *_util_Estrdup(const char *s, const char *file, size_t line) {
220 /* in case of -DNOTRACK */
227 if ((len = strlen(s)) && (ptr = (char*)mem_af(len+1, line, file))) {
234 char *_util_Estrdup_empty(const char *s, const char *file, size_t line) {
238 /* in case of -DNOTRACK */
246 if ((ptr = (char*)mem_af(len+1, line, file))) {
253 void util_debug(const char *area, const char *ms, ...) {
255 if (!OPTS_OPTION_BOOL(OPTION_DEBUG))
258 if (!strcmp(area, "MEM") && !OPTS_OPTION_BOOL(OPTION_MEMCHK))
262 con_out ("[%s] ", area);
268 * only required if big endian .. otherwise no need to swap
271 #if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_BIG
272 static GMQCC_INLINE void util_swap16(uint16_t *d, size_t l) {
274 d[l] = (d[l] << 8) | (d[l] >> 8);
278 static GMQCC_INLINE void util_swap32(uint32_t *d, size_t l) {
281 v = ((d[l] << 8) & 0xFF00FF00) | ((d[l] >> 8) & 0x00FF00FF);
282 d[l] = (v << 16) | (v >> 16);
286 /* Some strange system doesn't like constants that big, AND doesn't recognize an ULL suffix
287 * so let's go the safe way
289 static GMQCC_INLINE void util_swap64(uint32_t *d, size_t l) {
293 v = ((d[l] << 8) & 0xFF00FF00FF00FF00) | ((d[l] >> 8) & 0x00FF00FF00FF00FF);
294 v = ((v << 16) & 0xFFFF0000FFFF0000) | ((v >> 16) & 0x0000FFFF0000FFFF);
295 d[l] = (v << 32) | (v >> 32);
299 for (i = 0; i < l; i += 2) {
308 void util_endianswap(void *_data, size_t length, unsigned int typesize) {
309 # if PLATFORM_BYTE_ORDER == -1 /* runtime check */
310 if (*((char*)&typesize))
313 /* prevent unused warnings */
318 # if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_LITTLE
324 util_swap16((uint16_t*)_data, length>>1);
327 util_swap32((uint32_t*)_data, length>>2);
330 util_swap64((uint32_t*)_data, length>>3);
333 default: exit(EXIT_FAILURE); /* please blow the fuck up! */
340 * CRC algorithms vary in the width of the polynomial, the value of said polynomial,
341 * the initial value used for the register, weather the bits of each byte are reflected
342 * before being processed, weather the algorithm itself feeds input bytes through the
343 * register or XORs them with a byte from one end and then straight into the table, as
344 * well as (but not limited to the idea of reflected versions) where the final register
345 * value becomes reversed, and finally weather the value itself is used to XOR the final
346 * register value. AS such you can already imagine how painfully annoying CRCs are,
347 * of course we stand to target Quake, which expects it's certian set of rules for proper
348 * calculation of a CRC.
350 * In most traditional CRC algorithms on uses a reflected table driven method where a value
351 * or register is reflected if it's bits are swapped around it's center. For example:
352 * take the bits 0101 is the 4-bit reflection of 1010, and respectfully 0011 would be the
353 * reflection of 1100. Quake however expects a NON-Reflected CRC on the output, but still
354 * requires a final XOR on the values (0xFFFF and 0x0000) this is a standard CCITT CRC-16
355 * which I respectfully as a programmer don't agree with.
357 * So now you know what we target, and why we target it, despite how unsettling it may seem
358 * but those are what Quake seems to request.
361 static const uint16_t util_crc16_table[] = {
362 0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5,
363 0x60C6, 0x70E7, 0x8108, 0x9129, 0xA14A, 0xB16B,
364 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF, 0x1231, 0x0210,
365 0x3273, 0x2252, 0x52B5, 0x4294, 0x72F7, 0x62D6,
366 0x9339, 0x8318, 0xB37B, 0xA35A, 0xD3BD, 0xC39C,
367 0xF3FF, 0xE3DE, 0x2462, 0x3443, 0x0420, 0x1401,
368 0x64E6, 0x74C7, 0x44A4, 0x5485, 0xA56A, 0xB54B,
369 0x8528, 0x9509, 0xE5EE, 0xF5CF, 0xC5AC, 0xD58D,
370 0x3653, 0x2672, 0x1611, 0x0630, 0x76D7, 0x66F6,
371 0x5695, 0x46B4, 0xB75B, 0xA77A, 0x9719, 0x8738,
372 0xF7DF, 0xE7FE, 0xD79D, 0xC7BC, 0x48C4, 0x58E5,
373 0x6886, 0x78A7, 0x0840, 0x1861, 0x2802, 0x3823,
374 0xC9CC, 0xD9ED, 0xE98E, 0xF9AF, 0x8948, 0x9969,
375 0xA90A, 0xB92B, 0x5AF5, 0x4AD4, 0x7AB7, 0x6A96,
376 0x1A71, 0x0A50, 0x3A33, 0x2A12, 0xDBFD, 0xCBDC,
377 0xFBBF, 0xEB9E, 0x9B79, 0x8B58, 0xBB3B, 0xAB1A,
378 0x6CA6, 0x7C87, 0x4CE4, 0x5CC5, 0x2C22, 0x3C03,
379 0x0C60, 0x1C41, 0xEDAE, 0xFD8F, 0xCDEC, 0xDDCD,
380 0xAD2A, 0xBD0B, 0x8D68, 0x9D49, 0x7E97, 0x6EB6,
381 0x5ED5, 0x4EF4, 0x3E13, 0x2E32, 0x1E51, 0x0E70,
382 0xFF9F, 0xEFBE, 0xDFDD, 0xCFFC, 0xBF1B, 0xAF3A,
383 0x9F59, 0x8F78, 0x9188, 0x81A9, 0xB1CA, 0xA1EB,
384 0xD10C, 0xC12D, 0xF14E, 0xE16F, 0x1080, 0x00A1,
385 0x30C2, 0x20E3, 0x5004, 0x4025, 0x7046, 0x6067,
386 0x83B9, 0x9398, 0xA3FB, 0xB3DA, 0xC33D, 0xD31C,
387 0xE37F, 0xF35E, 0x02B1, 0x1290, 0x22F3, 0x32D2,
388 0x4235, 0x5214, 0x6277, 0x7256, 0xB5EA, 0xA5CB,
389 0x95A8, 0x8589, 0xF56E, 0xE54F, 0xD52C, 0xC50D,
390 0x34E2, 0x24C3, 0x14A0, 0x0481, 0x7466, 0x6447,
391 0x5424, 0x4405, 0xA7DB, 0xB7FA, 0x8799, 0x97B8,
392 0xE75F, 0xF77E, 0xC71D, 0xD73C, 0x26D3, 0x36F2,
393 0x0691, 0x16B0, 0x6657, 0x7676, 0x4615, 0x5634,
394 0xD94C, 0xC96D, 0xF90E, 0xE92F, 0x99C8, 0x89E9,
395 0xB98A, 0xA9AB, 0x5844, 0x4865, 0x7806, 0x6827,
396 0x18C0, 0x08E1, 0x3882, 0x28A3, 0xCB7D, 0xDB5C,
397 0xEB3F, 0xFB1E, 0x8BF9, 0x9BD8, 0xABBB, 0xBB9A,
398 0x4A75, 0x5A54, 0x6A37, 0x7A16, 0x0AF1, 0x1AD0,
399 0x2AB3, 0x3A92, 0xFD2E, 0xED0F, 0xDD6C, 0xCD4D,
400 0xBDAA, 0xAD8B, 0x9DE8, 0x8DC9, 0x7C26, 0x6C07,
401 0x5C64, 0x4C45, 0x3CA2, 0x2C83, 0x1CE0, 0x0CC1,
402 0xEF1F, 0xFF3E, 0xCF5D, 0xDF7C, 0xAF9B, 0xBFBA,
403 0x8FD9, 0x9FF8, 0x6E17, 0x7E36, 0x4E55, 0x5E74,
404 0x2E93, 0x3EB2, 0x0ED1, 0x1EF0
407 /* Non - Reflected */
408 uint16_t util_crc16(uint16_t current, const char *k, size_t len) {
409 register uint16_t h = current;
410 for (; len; --len, ++k)
411 h = util_crc16_table[(h>>8)^((unsigned char)*k)]^(h<<8);
414 /* Reflective Varation (for reference) */
416 uint16_t util_crc16(const char *k, int len, const short clamp) {
417 register uint16_t h= (uint16_t)0xFFFFFFFF;
418 for (; len; --len, ++k)
419 h = util_crc16_table[(h^((unsigned char)*k))&0xFF]^(h>>8);
424 size_t util_strtocmd(const char *in, char *out, size_t outsz) {
426 for (; *in && sz < outsz; ++in, ++out, ++sz)
427 *out = (*in == '-') ? '_' : (isalpha(*in) && !isupper(*in)) ? *in + 'A' - 'a': *in;
432 size_t util_strtononcmd(const char *in, char *out, size_t outsz) {
434 for (; *in && sz < outsz; ++in, ++out, ++sz)
435 *out = (*in == '_') ? '-' : (isalpha(*in) && isupper(*in)) ? *in + 'a' - 'A' : *in;
440 /* TODO: rewrite ... when I redo the ve cleanup */
441 void _util_vec_grow(void **a, size_t i, size_t s) {
442 vector_t *d = vec_meta(*a);
447 m = 2 * d->allocated + i;
448 p = mem_r(d, s * m + sizeof(vector_t));
451 p = mem_a(s * m + sizeof(vector_t));
452 ((vector_t*)p)->used = 0;
456 *a = (vector_t*)p + 1;
457 vec_meta(*a)->allocated = m;
461 * Hash table for generic data, based on dynamic memory allocations
462 * all around. This is the internal interface, please look for
463 * EXPOSED INTERFACE comment below
465 typedef struct hash_node_t {
466 char *key; /* the key for this node in table */
467 void *value; /* pointer to the data as void* */
468 struct hash_node_t *next; /* next node (linked list) */
471 GMQCC_INLINE size_t util_hthash(hash_table_t *ht, const char *key) {
472 const uint32_t mix = 0x5BD1E995;
473 const uint32_t rot = 24;
474 size_t size = strlen(key);
475 uint32_t hash = 0x1EF0 /* LICRC TAB */ ^ size;
477 const unsigned char *data = (const unsigned char*)key;
480 alias = (data[0] | (data[1] << 8) | (data[2] << 16) | (data[3] << 24));
482 alias ^= alias >> rot;
493 case 3: hash ^= data[2] << 16;
494 case 2: hash ^= data[1] << 8;
495 case 1: hash ^= data[0];
503 return (size_t) (hash % ht->size);
506 static hash_node_t *_util_htnewpair(const char *key, void *value) {
508 if (!(node = (hash_node_t*)mem_a(sizeof(hash_node_t))))
511 if (!(node->key = util_strdupe(key))) {
523 * EXPOSED INTERFACE for the hashtable implementation
524 * util_htnew(size) -- to make a new hashtable
525 * util_htset(table, key, value, sizeof(value)) -- to set something in the table
526 * util_htget(table, key) -- to get something from the table
527 * util_htdel(table) -- to delete the table
529 hash_table_t *util_htnew(size_t size) {
530 hash_table_t *hashtable = NULL;
534 if (!(hashtable = (hash_table_t*)mem_a(sizeof(hash_table_t))))
537 if (!(hashtable->table = (hash_node_t**)mem_a(sizeof(hash_node_t*) * size))) {
542 hashtable->size = size;
543 memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
548 void util_htseth(hash_table_t *ht, const char *key, size_t bin, void *value) {
549 hash_node_t *newnode = NULL;
550 hash_node_t *next = NULL;
551 hash_node_t *last = NULL;
553 next = ht->table[bin];
555 while (next && next->key && strcmp(key, next->key) > 0)
556 last = next, next = next->next;
558 /* already in table, do a replace */
559 if (next && next->key && strcmp(key, next->key) == 0) {
562 /* not found, grow a pair man :P */
563 newnode = _util_htnewpair(key, value);
564 if (next == ht->table[bin]) {
565 newnode->next = next;
566 ht->table[bin] = newnode;
568 last->next = newnode;
570 newnode->next = next;
571 last->next = newnode;
576 void util_htset(hash_table_t *ht, const char *key, void *value) {
577 util_htseth(ht, key, util_hthash(ht, key), value);
580 void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
581 hash_node_t *pair = ht->table[bin];
583 while (pair && pair->key && strcmp(key, pair->key) > 0)
586 if (!pair || !pair->key || strcmp(key, pair->key) != 0)
592 void *util_htget(hash_table_t *ht, const char *key) {
593 return util_htgeth(ht, key, util_hthash(ht, key));
596 void *code_util_str_htgeth(hash_table_t *ht, const char *key, size_t bin) {
601 keylen = strlen(key);
603 pair = ht->table[bin];
604 while (pair && pair->key) {
605 len = strlen(pair->key);
611 cmp = strcmp(key, pair->key);
619 cmp = strcmp(key, pair->key + len - keylen);
621 uintptr_t up = (uintptr_t)pair->value;
631 * Free all allocated data in a hashtable, this is quite the amount
634 void util_htrem(hash_table_t *ht, void (*callback)(void *data)) {
636 for (; i < ht->size; i++) {
637 hash_node_t *n = ht->table[i];
657 void util_htrmh(hash_table_t *ht, const char *key, size_t bin, void (*cb)(void*)) {
658 hash_node_t **pair = &ht->table[bin];
661 while (*pair && (*pair)->key && strcmp(key, (*pair)->key) > 0)
662 pair = &(*pair)->next;
665 if (!tmp || !tmp->key || strcmp(key, tmp->key) != 0)
676 void util_htrm(hash_table_t *ht, const char *key, void (*cb)(void*)) {
677 util_htrmh(ht, key, util_hthash(ht, key), cb);
680 void util_htdel(hash_table_t *ht) {
681 util_htrem(ht, NULL);
685 * Portable implementation of vasprintf/asprintf. Assumes vsnprintf
686 * exists, otherwise compiler error.
688 * TODO: fix for MSVC ....
690 int util_vasprintf(char **dat, const char *fmt, va_list args) {
696 * For visuals tido _vsnprintf doesn't tell you the length of a
697 * formatted string if it overflows. However there is a MSVC
698 * intrinsic (which is documented wrong) called _vcsprintf which
699 * will return the required amount to allocate.
702 if ((len = _vscprintf(fmt, args)) < 0) {
707 tmp = (char*)mem_a(len + 1);
708 if ((ret = _vsnprintf_s(tmp, len+1, len+1, fmt, args)) != len) {
717 * For everything else we have a decent conformint vsnprintf that
718 * returns the number of bytes needed. We give it a try though on
719 * a short buffer, since efficently speaking, it could be nice to
720 * above a second vsnprintf call.
725 len = vsnprintf(buf, sizeof(buf), fmt, cpy);
728 if (len < (int)sizeof(buf)) {
729 *dat = util_strdup(buf);
733 /* not large enough ... */
734 tmp = (char*)mem_a(len + 1);
735 if ((ret = vsnprintf(tmp, len + 1, fmt, args)) != len) {
745 int util_asprintf(char **ret, const char *fmt, ...) {
749 read = util_vasprintf(ret, fmt, args);
756 * These are various re-implementations (wrapping the real ones) of
757 * string functions that MSVC consideres unsafe. We wrap these up and
758 * use the safe varations on MSVC.
761 static char **util_strerror_allocated() {
762 static char **data = NULL;
766 static void util_strerror_cleanup(void) {
768 char **data = util_strerror_allocated();
769 for (i = 0; i < vec_size(data); i++)
774 const char *util_strerror(int num) {
775 char *allocated = NULL;
776 static bool install = false;
777 static size_t tries = 0;
778 char **vector = util_strerror_allocated();
780 /* try installing cleanup handler */
785 install = !atexit(&util_strerror_cleanup);
789 allocated = (char*)mem_a(4096); /* A page must be enough */
790 strerror_s(allocated, 4096, num);
792 vec_push(vector, allocated);
793 return (const char *)allocated;
796 int util_snprintf(char *src, size_t bytes, const char *format, ...) {
799 va_start(va, format);
801 rt = vsprintf_s(src, bytes, format, va);
807 char *util_strcat(char *dest, const char *src) {
808 strcat_s(dest, strlen(src), src);
812 char *util_strncpy(char *dest, const char *src, size_t num) {
813 strncpy_s(dest, num, src, num);
817 const char *util_strerror(int num) {
818 return strerror(num);
821 int util_snprintf(char *src, size_t bytes, const char *format, ...) {
824 va_start(va, format);
825 rt = vsnprintf(src, bytes, format, va);
831 char *util_strcat(char *dest, const char *src) {
832 return strcat(dest, src);
835 char *util_strncpy(char *dest, const char *src, size_t num) {
836 return strncpy(dest, src, num);
839 #endif /*! _MSC_VER */
842 * Implementation of the Mersenne twister PRNG (pseudo random numer
843 * generator). Implementation of MT19937. Has a period of 2^19937-1
844 * which is a Mersenne Prime (hence the name).
846 * Implemented from specification and original paper:
847 * http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf
849 * This code is placed in the public domain by me personally
850 * (Dale Weiler, a.k.a graphitemaster).
854 #define MT_PERIOD 397
855 #define MT_SPACE (MT_SIZE - MT_PERIOD)
857 static uint32_t mt_state[MT_SIZE];
858 static size_t mt_index = 0;
860 static GMQCC_INLINE void mt_generate() {
862 * The loop has been unrolled here: the original paper and implemenation
863 * Called for the following code:
864 * for (register unsigned i = 0; i < MT_SIZE; ++i) {
865 * register uint32_t load;
866 * load = (0x80000000 & mt_state[i]) // most significant 32nd bit
867 * load |= (0x7FFFFFFF & mt_state[(i + 1) % MT_SIZE]) // least significant 31nd bit
869 * mt_state[i] = mt_state[(i + MT_PERIOD) % MT_SIZE] ^ (load >> 1);
871 * if (load & 1) mt_state[i] ^= 0x9908B0DF;
874 * This essentially is a waste: we have two modulus operations, and
875 * a branch that is executed every iteration from [0, MT_SIZE).
877 * Please see: http://www.quadibloc.com/crypto/co4814.htm for more
878 * information on how this clever trick works.
880 static const uint32_t matrix[2] = {
885 * This register gives up a little more speed by instructing the compiler
886 * to force these into CPU registers (they're counters for indexing mt_state
887 * which we can force the compiler to generate prefetch instructions for)
893 * Said loop has been unrolled for MT_SPACE (226 iterations), opposed
894 * to [0, MT_SIZE) (634 iterations).
896 for (i = 0; i < MT_SPACE; ++i) {
897 y = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
898 mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1];
900 i ++; /* loop unroll */
902 y = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
903 mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1];
907 * collapsing the walls unrolled (evenly dividing 396 [632-227 = 396
911 while (i < MT_SIZE - 1) {
913 * We expand this 11 times .. manually, no macros are required
914 * here. This all fits in the CPU cache.
916 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
917 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
919 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
920 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
922 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
923 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
925 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
926 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
928 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
929 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
931 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
932 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
934 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
935 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
937 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
938 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
940 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
941 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
943 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
944 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
946 y = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
947 mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
951 /* i = mt_state[623] */
952 y = (0x80000000 & mt_state[MT_SIZE - 1]) | (0x7FFFFFFF & mt_state[MT_SIZE - 1]);
953 mt_state[MT_SIZE - 1] = mt_state[MT_PERIOD - 1] ^ (y >> 1) ^ matrix[y & 1];
956 void util_seed(uint32_t value) {
958 * We seed the mt_state with a LCG (linear congruential generator)
959 * We're operating exactly on exactly m=32, so there is no need to
962 * The multipler of choice is 0x6C07865, also knows as the Borosh-
963 * Niederreiter multipler used for modulus 2^32. More can be read
964 * about this in Knuth's TAOCP Volume 2, page 106.
966 * If you don't own TAOCP something is wrong with you :-) .. so I
967 * also provided a link to the original paper by Borosh and
968 * Niederreiter. It's called "Optional Multipliers for PRNG by The
969 * Linear Congruential Method" (1983).
970 * http://en.wikipedia.org/wiki/Linear_congruential_generator
972 * From said page, it says the following:
973 * "A common Mersenne twister implementation, interestingly enough
974 * used an LCG to generate seed data."
977 * The data we're operating on is 32-bits for the mt_state array, so
978 * there is no masking required with 0xFFFFFFFF
983 for (i = 1; i < MT_SIZE; ++i)
984 mt_state[i] = 0x6C078965 * (mt_state[i - 1] ^ mt_state[i - 1] >> 30) + i;
987 uint32_t util_rand() {
991 * This is inlined with any sane compiler (I checked)
992 * for some reason though, SubC seems to be generating invalid
993 * code when it inlines this.
998 y = mt_state[mt_index];
1000 /* Standard tempering */
1001 y ^= y >> 11; /* +7 */
1002 y ^= y << 7 & 0x9D2C5680; /* +4 */
1003 y ^= y << 15 & 0xEFC60000; /* -4 */
1004 y ^= y >> 18; /* -7 */
1006 if(++mt_index == MT_SIZE)