Cleanups
[xonotic/gmqcc.git] / util.c
diff --git a/util.c b/util.c
index 2b2f1b0e1ffa5d00d0e58c9d11a400cd692cea91..ecae50516514e45db673cd10966ac408a010b0d1 100644 (file)
--- a/util.c
+++ b/util.c
@@ -1,5 +1,5 @@
 /*
 /*
- * Copyright (C) 2012
+ * Copyright (C) 2012, 2013
  *     Dale Weiler
  *     Wolfgang Bumiller
  *
  *     Dale Weiler
  *     Wolfgang Bumiller
  *
  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  * SOFTWARE.
  */
  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  * SOFTWARE.
  */
-#include <stdarg.h>
-#include <errno.h>
-#include "gmqcc.h"
-
-uint64_t mem_ab = 0;
-uint64_t mem_db = 0;
-uint64_t mem_at = 0;
-uint64_t mem_dt = 0;
-
-struct memblock_t {
-    const char  *file;
-    unsigned int line;
-    size_t       byte;
-    struct memblock_t *next;
-    struct memblock_t *prev;
-};
-
-static struct memblock_t *mem_start = NULL;
-
-void *util_memory_a(size_t byte, unsigned int line, const char *file) {
-    struct memblock_t *info = malloc(sizeof(struct memblock_t) + byte);
-    void              *data = (void*)(info+1);
-    if (!info) return NULL;
-    info->line = line;
-    info->byte = byte;
-    info->file = file;
-    info->prev = NULL;
-    info->next = mem_start;
-    if (mem_start)
-        mem_start->prev = info;
-    mem_start = info;
-
-    util_debug("MEM", "allocation:   % 8u (bytes) address 0x%08X @ %s:%u\n", byte, data, file, line);
-    mem_at++;
-    mem_ab += info->byte;
-
-    return data;
-}
-
-void util_memory_d(void *ptrn, unsigned int line, const char *file) {
-    struct memblock_t *info = NULL;
-
-    if (!ptrn) return;
-    info = ((struct memblock_t*)ptrn - 1);
-
-    util_debug("MEM", "released:     % 8u (bytes) address 0x%08X @ %s:%u\n", info->byte, ptrn, file, line);
-    mem_db += info->byte;
-    mem_dt++;
-
-    if (info->prev)
-        info->prev->next = info->next;
-    if (info->next)
-        info->next->prev = info->prev;
-    if (info == mem_start)
-        mem_start = info->next;
-
-    free(info);
-}
-
-void *util_memory_r(void *ptrn, size_t byte, unsigned int line, const char *file) {
-    struct memblock_t *oldinfo = NULL;
-
-    struct memblock_t *newinfo;
-
-    if (!ptrn)
-        return util_memory_a(byte, line, file);
-    if (!byte) {
-        util_memory_d(ptrn, line, file);
-        return NULL;
-    }
+#include <string.h>
+#include <stdlib.h>
 
 
-    oldinfo = ((struct memblock_t*)ptrn - 1);
-    newinfo = ((struct memblock_t*)malloc(sizeof(struct memblock_t) + byte));
-
-    util_debug("MEM", "reallocation: % 8u -> %u (bytes) address 0x%08X -> 0x%08X @ %s:%u\n", oldinfo->byte, byte, ptrn, (void*)(newinfo+1), file, line);
-
-    /* new data */
-    if (!newinfo) {
-        util_memory_d(oldinfo+1, line, file);
-        return NULL;
-    }
-
-    /* copy old */
-    memcpy(newinfo+1, oldinfo+1, oldinfo->byte);
-
-    /* free old */
-    if (oldinfo->prev)
-        oldinfo->prev->next = oldinfo->next;
-    if (oldinfo->next)
-        oldinfo->next->prev = oldinfo->prev;
-    if (oldinfo == mem_start)
-        mem_start = oldinfo->next;
-
-    /* fill info */
-    newinfo->line = line;
-    newinfo->byte = byte;
-    newinfo->file = file;
-    newinfo->prev = NULL;
-    newinfo->next = mem_start;
-    if (mem_start)
-        mem_start->prev = newinfo;
-    mem_start = newinfo;
-
-    mem_ab -= oldinfo->byte;
-    mem_ab += newinfo->byte;
-
-    free(oldinfo);
-
-    return newinfo+1;
-}
-
-void util_meminfo() {
-    struct memblock_t *info;
-
-    if (!opts.memchk)
-        return;
-
-    for (info = mem_start; info; info = info->next) {
-        util_debug("MEM", "lost:       % 8u (bytes) at %s:%u\n",
-            info->byte,
-            info->file,
-            info->line);
-    }
-
-    util_debug("MEM", "Memory information:\n\
-        Total allocations:   %llu\n\
-        Total deallocations: %llu\n\
-        Total allocated:     %llu (bytes)\n\
-        Total deallocated:   %llu (bytes)\n\
-        Leaks found:         lost %llu (bytes) in %d allocations\n",
-            mem_at,   mem_dt,
-            mem_ab,   mem_db,
-           (mem_ab -  mem_db),
-           (mem_at -  mem_dt)
-    );
-}
+#include "gmqcc.h"
 
 /*
 
 /*
- * Some string utility functions, because strdup uses malloc, and we want
- * to track all memory (without replacing malloc).
+ * Initially this was handled with a table in the gmqcc.h header, but 
+ * much to my surprise the contents of the table was duplicated for
+ * each translation unit, causing all these strings to be duplicated
+ * for every .c file it was included into. This method culls back on
+ * it. This is a 'utility' function because the executor also depends
+ * on this for dissasembled bytecode.
  */
  */
-char *util_strdup(const char *s) {
-    size_t  len = 0;
-    char   *ptr = NULL;
-
-    if (!s)
-        return NULL;
-
-    if ((len = strlen(s)) && (ptr = mem_a(len+1))) {
-        memcpy(ptr, s, len);
-        ptr[len] = '\0';
-    }
-    return ptr;
-}
+const char *util_instr_str[VINSTR_END] = {
+    "DONE",       "MUL_F",      "MUL_V",      "MUL_FV",
+    "MUL_VF",     "DIV_F",      "ADD_F",      "ADD_V",
+    "SUB_F",      "SUB_V",      "EQ_F",       "EQ_V",
+    "EQ_S",       "EQ_E",       "EQ_FNC",     "NE_F",
+    "NE_V",       "NE_S",       "NE_E",       "NE_FNC",
+    "LE",         "GE",         "LT",         "GT",
+    "LOAD_F",     "LOAD_V",     "LOAD_S",     "LOAD_ENT",
+    "LOAD_FLD",   "LOAD_FNC",   "ADDRESS",    "STORE_F",
+    "STORE_V",    "STORE_S",    "STORE_ENT",  "STORE_FLD",
+    "STORE_FNC",  "STOREP_F",   "STOREP_V",   "STOREP_S",
+    "STOREP_ENT", "STOREP_FLD", "STOREP_FNC", "RETURN",
+    "NOT_F",      "NOT_V",      "NOT_S",      "NOT_ENT",
+    "NOT_FNC",    "IF",         "IFNOT",      "CALL0",
+    "CALL1",      "CALL2",      "CALL3",      "CALL4",
+    "CALL5",      "CALL6",      "CALL7",      "CALL8",
+    "STATE",      "GOTO",       "AND",        "OR",
+    "BITAND",     "BITOR"
+};
 
 void util_debug(const char *area, const char *ms, ...) {
     va_list  va;
 
 void util_debug(const char *area, const char *ms, ...) {
     va_list  va;
-    if (!opts.debug)
+    if (!OPTS_OPTION_BOOL(OPTION_DEBUG))
         return;
 
         return;
 
-    if (!strcmp(area, "MEM") && !opts.memchk)
+    if (!strcmp(area, "MEM") && !OPTS_OPTION_BOOL(OPTION_MEMCHK))
         return;
 
     va_start(va, ms);
         return;
 
     va_start(va, ms);
@@ -193,15 +71,15 @@ void util_debug(const char *area, const char *ms, ...) {
 /*
  * only required if big endian .. otherwise no need to swap
  * data.
 /*
  * only required if big endian .. otherwise no need to swap
  * data.
- */   
+ */
 #if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_BIG
 #if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_BIG
-    static void util_swap16(uint16_t *d, size_t l) {
+    static GMQCC_INLINE void util_swap16(uint16_t *d, size_t l) {
         while (l--) {
             d[l] = (d[l] << 8) | (d[l] >> 8);
         }
     }
 
         while (l--) {
             d[l] = (d[l] << 8) | (d[l] >> 8);
         }
     }
 
-    static void util_swap32(uint32_t *d, size_t l) {
+    static GMQCC_INLINE void util_swap32(uint32_t *d, size_t l) {
         while (l--) {
             uint32_t v;
             v = ((d[l] << 8) & 0xFF00FF00) | ((d[l] >> 8) & 0x00FF00FF);
         while (l--) {
             uint32_t v;
             v = ((d[l] << 8) & 0xFF00FF00) | ((d[l] >> 8) & 0x00FF00FF);
@@ -212,7 +90,7 @@ void util_debug(const char *area, const char *ms, ...) {
     /* Some strange system doesn't like constants that big, AND doesn't recognize an ULL suffix
      * so let's go the safe way
      */
     /* Some strange system doesn't like constants that big, AND doesn't recognize an ULL suffix
      * so let's go the safe way
      */
-    static void util_swap64(uint32_t *d, size_t l) {
+    static GMQCC_INLINE void util_swap64(uint32_t *d, size_t l) {
         /*
         while (l--) {
             uint64_t v;
         /*
         while (l--) {
             uint64_t v;
@@ -256,7 +134,7 @@ void util_endianswap(void *_data, size_t length, unsigned int typesize) {
                 util_swap64((uint32_t*)_data, length>>3);
                 return;
 
                 util_swap64((uint32_t*)_data, length>>3);
                 return;
 
-            default: abort(); /* please blow the fuck up! */
+            default: exit(EXIT_FAILURE); /* please blow the fuck up! */
         }
 #   endif
 #endif
         }
 #   endif
 #endif
@@ -333,7 +211,7 @@ static const uint16_t util_crc16_table[] = {
 /* Non - Reflected */
 uint16_t util_crc16(uint16_t current, const char *k, size_t len) {
     register uint16_t h = current;
 /* Non - Reflected */
 uint16_t util_crc16(uint16_t current, const char *k, size_t len) {
     register uint16_t h = current;
-    for (; len; --len, ++k) 
+    for (; len; --len, ++k)
         h = util_crc16_table[(h>>8)^((unsigned char)*k)]^(h<<8);
     return h;
 }
         h = util_crc16_table[(h>>8)^((unsigned char)*k)]^(h<<8);
     return h;
 }
@@ -341,256 +219,363 @@ uint16_t util_crc16(uint16_t current, const char *k, size_t len) {
 #if 0
 uint16_t util_crc16(const char *k, int len, const short clamp) {
     register uint16_t h= (uint16_t)0xFFFFFFFF;
 #if 0
 uint16_t util_crc16(const char *k, int len, const short clamp) {
     register uint16_t h= (uint16_t)0xFFFFFFFF;
-    for (; len; --len, ++k) 
+    for (; len; --len, ++k)
         h = util_crc16_table[(h^((unsigned char)*k))&0xFF]^(h>>8);
         h = util_crc16_table[(h^((unsigned char)*k))&0xFF]^(h>>8);
-    return (~h)%clamp; 
+    return (~h)%clamp;
 }
 #endif
 
 }
 #endif
 
-/*
- * Implements libc getline for systems that don't have it, which is
- * assmed all.  This works the same as getline().
+/* 
+ * modifier is the match to make and the transpsition from it, while add is the upper-value that determines the
+ * transposion from uppercase to lower case.
  */
  */
-int util_getline(char **lineptr, size_t *n, FILE *stream) {
-    int   chr;
-    int   ret;
-    char *pos;
-
-    if (!lineptr || !n || !stream)
-        return -1;
-    if (!*lineptr) {
-        if (!(*lineptr = (char*)mem_a((*n=64))))
-            return -1;
+static GMQCC_INLINE size_t util_strtransform(const char *in, char *out, size_t outsz, const char *mod, int add) {
+    size_t sz = 1;
+    for (; *in && sz < outsz; ++in, ++out, ++sz) {
+        *out = (*in == mod[0])
+                    ? mod[1]
+                    : (util_isalpha(*in) && util_isupper(*in + add))
+                        ? *in + add
+                        : *in;
     }
     }
+    *out = 0;
+    return sz-1;
+}
 
 
-    chr = *n;
-    pos = *lineptr;
+size_t util_strtocmd(const char *in, char *out, size_t outsz) {
+    return util_strtransform(in, out, outsz, "-_", 'A'-'a');
+}
+size_t util_strtononcmd(const char *in, char *out, size_t outsz) {
+    return util_strtransform(in, out, outsz, "_-", 'a'-'A');
+}
+size_t util_optimizationtostr(const char *in, char *out, size_t outsz) {
+    return util_strtransform(in, out, outsz, "_ ", 'a'-'A');
+}
 
 
-    for (;;) {
-        int c = getc(stream);
+/*
+ * Portable implementation of vasprintf/asprintf. Assumes vsnprintf
+ * exists, otherwise compiler error.
+ *
+ * TODO: fix for MSVC ....
+ */
+int util_vasprintf(char **dat, const char *fmt, va_list args) {
+    int   ret;
+    int   len;
+    char *tmp = NULL;
+
+    /*
+     * For visuals tido _vsnprintf doesn't tell you the length of a
+     * formatted string if it overflows. However there is a MSVC
+     * intrinsic (which is documented wrong) called _vcsprintf which
+     * will return the required amount to allocate.
+     */
+    #ifdef _MSC_VER
+        if ((len = _vscprintf(fmt, args)) < 0) {
+            *dat = NULL;
+            return -1;
+        }
 
 
-        if (chr < 2) {
-            *n += (*n > 16) ? *n : 64;
-            chr = *n + *lineptr - pos;
-            if (!(*lineptr = (char*)mem_r(*lineptr,*n)))
-                return -1;
-            pos = *n - chr + *lineptr;
+        tmp = (char*)mem_a(len + 1);
+        if ((ret = _vsnprintf_s(tmp, len+1, len+1, fmt, args)) != len) {
+            mem_d(tmp);
+            *dat = NULL;
+            return -1;
+        }
+        *dat = tmp;
+        return len;
+    #else
+        /*
+         * For everything else we have a decent conformint vsnprintf that
+         * returns the number of bytes needed.  We give it a try though on
+         * a short buffer, since efficently speaking, it could be nice to
+         * above a second vsnprintf call.
+         */
+        char    buf[128];
+        va_list cpy;
+        va_copy(cpy, args);
+        len = vsnprintf(buf, sizeof(buf), fmt, cpy);
+        va_end (cpy);
+
+        if (len < (int)sizeof(buf)) {
+            *dat = util_strdup(buf);
+            return len;
         }
 
         }
 
-        if (ferror(stream))
+        /* not large enough ... */
+        tmp = (char*)mem_a(len + 1);
+        if ((ret = vsnprintf(tmp, len + 1, fmt, args)) != len) {
+            mem_d(tmp);
+            *dat = NULL;
             return -1;
             return -1;
-        if (c == EOF) {
-            if (pos == *lineptr)
-                return -1;
-            else
-                break;
         }
 
         }
 
-        *pos++ = c;
-        chr--;
-        if (c == '\n')
-            break;
-    }
-    *pos = '\0';
-    return (ret = pos - *lineptr);
+        *dat = tmp;
+        return len;
+    #endif
 }
 }
-
-size_t util_strtocmd(const char *in, char *out, size_t outsz) {
-    size_t sz = 1;
-    for (; *in && sz < outsz; ++in, ++out, ++sz)
-        *out = (*in == '-') ? '_' : (isalpha(*in) && !isupper(*in)) ? *in + 'A' - 'a': *in;
-    *out = 0;
-    return sz-1;
+int util_asprintf(char **ret, const char *fmt, ...) {
+    va_list  args;
+    int      read;
+    va_start(args, fmt);
+    read = util_vasprintf(ret, fmt, args);
+    va_end  (args);
+
+    return read;
 }
 
 }
 
-size_t util_strtononcmd(const char *in, char *out, size_t outsz) {
-    size_t sz = 1;
-    for (; *in && sz < outsz; ++in, ++out, ++sz)
-        *out = (*in == '_') ? '-' : (isalpha(*in) && isupper(*in)) ? *in + 'a' - 'A' : *in;
-    *out = 0;
-    return sz-1;
-}
+/*
+ * These are various re-implementations (wrapping the real ones) of
+ * string functions that MSVC consideres unsafe. We wrap these up and
+ * use the safe varations on MSVC.
+ */
+#ifdef _MSC_VER
+    static char **util_strerror_allocated() {
+        static char **data = NULL;
+        return data;
+    }
 
 
+    static void util_strerror_cleanup(void) {
+        size_t i;
+        char  **data = util_strerror_allocated();
+        for (i = 0; i < vec_size(data); i++)
+            mem_d(data[i]);
+        vec_free(data);
+    }
 
 
-FILE *util_fopen(const char *filename, const char *mode)
-{
-#ifdef _MSC_VER
-    FILE *out;
-    if (fopen_s(&out, filename, mode) != 0)
-        return NULL;
-    return out;
-#else
-    return fopen(filename, mode);
-#endif
-}
+    const char *util_strerror(int num) {
+        char         *allocated = NULL;
+        static bool   install   = false;
+        static size_t tries     = 0;
+        char        **vector    = util_strerror_allocated();
 
 
-void _util_vec_grow(void **a, size_t i, size_t s) {
-    size_t m = *a ? 2*_vec_beg(*a)+i : i+1;
-    void  *p = mem_r((*a ? _vec_raw(*a) : NULL), s * m + sizeof(size_t)*2);
-    if (!*a)
-        ((size_t*)p)[1] = 0;
-    *a = (void*)((size_t*)p + 2);
-    _vec_beg(*a) = m;
-}
+        /* try installing cleanup handler */
+        while (!install) {
+            if (tries == 32)
+                return "(unknown)";
 
 
-/*
- * Hash table for generic data, based on dynamic memory allocations
- * all around.  This is the internal interface, please look for
- * EXPOSED INTERFACE comment below
- */
-typedef struct hash_node_t {
-    char               *key;   /* the key for this node in table */
-    void               *value; /* pointer to the data as void*   */
-    struct hash_node_t *next;  /* next node (linked list)        */
-} hash_node_t;
-
-GMQCC_INLINE size_t util_hthash(hash_table_t *ht, const char *key) {
-    const uint32_t       mix   = 0x5BD1E995;
-    const uint32_t       rot   = 24;
-    size_t               size  = strlen(key);
-    uint32_t             hash  = 0x1EF0 /* LICRC TAB */  ^ size;
-    uint32_t             alias = 0;
-    const unsigned char *data  = (const unsigned char*)key;
-
-    while (size >= 4) {
-        alias = *(uint32_t*)data;
-
-        alias *= mix;
-        alias ^= alias >> rot;
-        alias *= mix;
-
-        hash  *= mix;
-        hash  ^= alias;
-
-        data += 4;
-        size -= 4;
+            install = !atexit(&util_strerror_cleanup);
+            tries ++;
+        }
+
+        allocated = (char*)mem_a(4096); /* A page must be enough */
+        strerror_s(allocated, 4096, num);
+
+        vec_push(vector, allocated);
+        return (const char *)allocated;
     }
 
     }
 
-    switch (size) {
-        case 3: hash ^= data[2] << 16;
-        case 2: hash ^= data[1] << 8;
-        case 1: hash ^= data[0];
-                hash *= mix;
+    int util_snprintf(char *src, size_t bytes, const char *format, ...) {
+        int      rt;
+        va_list  va;
+        va_start(va, format);
+
+        rt = vsprintf_s(src, bytes, format, va);
+        va_end  (va);
+
+        return rt;
     }
 
     }
 
-    hash ^= hash >> 13;
-    hash *= mix;
-    hash ^= hash >> 15;
+    char *util_strcat(char *dest, const char *src) {
+        strcat_s(dest, strlen(src), src);
+        return dest;
+    }
 
 
-    return (size_t) (hash % ht->size);
-}
+    char *util_strncpy(char *dest, const char *src, size_t num) {
+        strncpy_s(dest, num, src, num);
+        return dest;
+    }
+#else
+    const char *util_strerror(int num) {
+        return strerror(num);
+    }
+
+    int util_snprintf(char *src, size_t bytes, const char *format, ...) {
+        int      rt;
+        va_list  va;
+        va_start(va, format);
+        rt = vsnprintf(src, bytes, format, va);
+        va_end  (va);
 
 
-hash_node_t *_util_htnewpair(const char *key, void *value) {
-    hash_node_t *node;
-    if (!(node = mem_a(sizeof(hash_node_t))))
-        return NULL;
+        return rt;
+    }
 
 
-    if (!(node->key = util_strdup(key))) {
-        mem_d(node);
-        return NULL;
+    char *util_strcat(char *dest, const char *src) {
+        return strcat(dest, src);
     }
 
     }
 
-    node->value = value;
-    node->next  = NULL;
+    char *util_strncpy(char *dest, const char *src, size_t num) {
+        return strncpy(dest, src, num);
+    }
 
 
-    return node;
-}
+#endif /*! _MSC_VER */
 
 /*
 
 /*
- * EXPOSED INTERFACE for the hashtable implementation
- * util_htnew(size)                             -- to make a new hashtable
- * util_htset(table, key, value, sizeof(value)) -- to set something in the table
- * util_htget(table, key)                       -- to get something from the table
- * util_htdel(table)                            -- to delete the table
+ * Implementation of the Mersenne twister PRNG (pseudo random numer
+ * generator).  Implementation of MT19937.  Has a period of 2^19937-1
+ * which is a Mersenne Prime (hence the name).
+ *
+ * Implemented from specification and original paper:
+ * http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf
+ *
+ * This code is placed in the public domain by me personally
+ * (Dale Weiler, a.k.a graphitemaster).
  */
  */
-hash_table_t *util_htnew(size_t size) {
-    hash_table_t *hashtable = NULL;
-    if (size < 1)
-        return NULL;
 
 
-    if (!(hashtable = mem_a(sizeof(hash_table_t))))
-        return NULL;
+#define MT_SIZE    624
+#define MT_PERIOD  397
+#define MT_SPACE   (MT_SIZE - MT_PERIOD)
+
+static uint32_t mt_state[MT_SIZE];
+static size_t   mt_index = 0;
+
+static GMQCC_INLINE void mt_generate(void) {
+    /*
+     * The loop has been unrolled here: the original paper and implemenation
+     * Called for the following code:
+     * for (register unsigned i = 0; i < MT_SIZE; ++i) {
+     *     register uint32_t load;
+     *     load  = (0x80000000 & mt_state[i])                 // most  significant 32nd bit
+     *     load |= (0x7FFFFFFF & mt_state[(i + 1) % MT_SIZE]) // least significant 31nd bit
+     *
+     *     mt_state[i] = mt_state[(i + MT_PERIOD) % MT_SIZE] ^ (load >> 1);
+     *
+     *     if (load & 1) mt_state[i] ^= 0x9908B0DF;
+     * }
+     *
+     * This essentially is a waste: we have two modulus operations, and
+     * a branch that is executed every iteration from [0, MT_SIZE).
+     *
+     * Please see: http://www.quadibloc.com/crypto/co4814.htm for more
+     * information on how this clever trick works.
+     */
+    static const uint32_t matrix[2] = {
+        0x00000000,
+        0x9908B0Df
+    };
+    /*
+     * This register gives up a little more speed by instructing the compiler
+     * to force these into CPU registers (they're counters for indexing mt_state
+     * which we can force the compiler to generate prefetch instructions for)
+     */
+    register uint32_t y;
+    register uint32_t i;
 
 
-    if (!(hashtable->table = mem_a(sizeof(hash_node_t*) * size))) {
-        mem_d(hashtable);
-        return NULL;
-    }
+    /*
+     * Said loop has been unrolled for MT_SPACE (226 iterations), opposed
+     * to [0, MT_SIZE)  (634 iterations).
+     */
+    for (i = 0; i < MT_SPACE-1; ++i) {
+        y           = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
+        mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1];
 
 
-    hashtable->size = size;
-    memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
+        i ++; /* loop unroll */
 
 
-    return hashtable;
-}
+        y           = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
+        mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1];
+    }
 
 
-void util_htseth(hash_table_t *ht, const char *key, size_t bin, void *value) {
-    hash_node_t *newnode = NULL;
-    hash_node_t *next    = NULL;
-    hash_node_t *last    = NULL;
-
-    next = ht->table[bin];
-
-    while (next && next->key && strcmp(key, next->key) > 0)
-        last = next, next = next->next;
-
-    /* already in table, do a replace */
-    if (next && next->key && strcmp(key, next->key) == 0) {
-        next->value = value;
-    } else {
-        /* not found, grow a pair man :P */
-        newnode = _util_htnewpair(key, value);
-        if (next == ht->table[bin]) {
-            newnode->next  = next;
-            ht->table[bin] = newnode;
-        } else if (!next) {
-            last->next = newnode;
-        } else {
-            newnode->next = next;
-            last->next = newnode;
-        }
+    /*
+     * collapsing the walls unrolled (evenly dividing 396 [632-227 = 396
+     * = 2*2*3*3*11])
+     */
+    i = MT_SPACE;
+    while (i < MT_SIZE-2) {
+        /*
+         * We expand this 11 times .. manually, no macros are required
+         * here. This all fits in the CPU cache.
+         */
+        y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
+        mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
+        ++i;
+        y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
+        mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
+        ++i;
+        y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
+        mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
+        ++i;
+        y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
+        mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
+        ++i;
+        y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
+        mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
+        ++i;
+        y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
+        mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
+        ++i;
+        y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
+        mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
+        ++i;
+        y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
+        mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
+        ++i;
+        y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
+        mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
+        ++i;
+        y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
+        mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
+        ++i;
+        y           = (0x80000000 & mt_state[i]) | (0x7FFFFFFF & mt_state[i + 1]);
+        mt_state[i] = mt_state[i - MT_SPACE] ^ (y >> 1) ^ matrix[y & 1];
+        ++i;
     }
     }
-}
 
 
-void util_htset(hash_table_t *ht, const char *key, void *value) {
-    util_htseth(ht, key, util_hthash(ht, key), value);
+    /* i = mt_state[623] */
+    y                     = (0x80000000 & mt_state[MT_SIZE - 1]) | (0x7FFFFFFF & mt_state[MT_SIZE - 1]);
+    mt_state[MT_SIZE - 1] = mt_state[MT_PERIOD - 1] ^ (y >> 1) ^ matrix[y & 1];
 }
 
 }
 
-void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
-    hash_node_t *pair = ht->table[bin];
+void util_seed(uint32_t value) {
+    /*
+     * We seed the mt_state with a LCG (linear congruential generator)
+     * We're operating exactly on exactly m=32, so there is no need to
+     * use modulus.
+     *
+     * The multipler of choice is 0x6C07865, also knows as the Borosh-
+     * Niederreiter multipler used for modulus 2^32.  More can be read
+     * about this in Knuth's TAOCP Volume 2, page 106.
+     *
+     * If you don't own TAOCP something is wrong with you :-) .. so I
+     * also provided a link to the original paper by Borosh and
+     * Niederreiter.  It's called "Optional Multipliers for PRNG by The
+     * Linear Congruential Method" (1983).
+     * http://en.wikipedia.org/wiki/Linear_congruential_generator
+     *
+     * From said page, it says the following:
+     * "A common Mersenne twister implementation, interestingly enough
+     *  used an LCG to generate seed data."
+     *
+     * Remarks:
+     * The data we're operating on is 32-bits for the mt_state array, so
+     * there is no masking required with 0xFFFFFFFF
+     */
+    register size_t i;
 
 
-    while (pair && pair->key && strcmp(key, pair->key) > 0)
-        pair = pair->next;
+    mt_state[0] = value;
+    for (i = 1; i < MT_SIZE; ++i)
+        mt_state[i] = 0x6C078965 * (mt_state[i - 1] ^ mt_state[i - 1] >> 30) + i;
+}
 
 
-    if (!pair || !pair->key || strcmp(key, pair->key) != 0)
-        return NULL;
+uint32_t util_rand() {
+    register uint32_t y;
 
 
-    return pair->value;
-}
+    /*
+     * This is inlined with any sane compiler (I checked)
+     * for some reason though, SubC seems to be generating invalid
+     * code when it inlines this.
+     */
+    if (!mt_index)
+        mt_generate();
 
 
-void *util_htget(hash_table_t *ht, const char *key) {
-    return util_htgeth(ht, key, util_hthash(ht, key));
-}
+    y = mt_state[mt_index];
 
 
-/*
- * Free all allocated data in a hashtable, this is quite the amount
- * of work.
- */
-void util_htdel(hash_table_t *ht) {
-    size_t i = 0;
-    for (; i < ht->size; i++) {
-        hash_node_t *n = ht->table[i];
-        hash_node_t *p;
-
-        /* free in list */
-        while (n) {
-            if (n->key)
-                mem_d(n->key);
-            p = n;
-            n = n->next;
-            mem_d(p);
-        }
+    /* Standard tempering */
+    y ^= y >> 11;              /* +7 */
+    y ^= y << 7  & 0x9D2C5680; /* +4 */
+    y ^= y << 15 & 0xEFC60000; /* -4 */
+    y ^= y >> 18;              /* -7 */
 
 
-    }
-    /* free table */
-    mem_d(ht->table);
-    mem_d(ht);
+    if(++mt_index == MT_SIZE)
+         mt_index = 0;
+
+    return y;
 }
 }