/*
- * Copyright (C) 2012
+ * Copyright (C) 2012, 2013
* Dale Weiler
* Wolfgang Bumiller
*
#include "gmqcc.h"
/* TODO: remove globals ... */
-uint64_t mem_ab = 0;
-uint64_t mem_db = 0;
-uint64_t mem_at = 0;
-uint64_t mem_dt = 0;
+static uint64_t mem_ab = 0;
+static uint64_t mem_db = 0;
+static uint64_t mem_at = 0;
+static uint64_t mem_dt = 0;
+static uint64_t mem_pk = 0;
+static uint64_t mem_hw = 0;
struct memblock_t {
const char *file;
struct memblock_t *prev;
};
+#define PEAK_MEM \
+ do { \
+ if (mem_hw > mem_pk) \
+ mem_pk = mem_hw; \
+ } while (0)
+
static struct memblock_t *mem_start = NULL;
void *util_memory_a(size_t byte, unsigned int line, const char *file) {
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;
+ mem_hw += info->byte;
+
+ PEAK_MEM;
return data;
}
-void util_memory_d(void *ptrn, unsigned int line, const char *file) {
+void util_memory_d(void *ptrn) {
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_hw -= info->byte;
mem_dt++;
if (info->prev)
if (!ptrn)
return util_memory_a(byte, line, file);
if (!byte) {
- util_memory_d(ptrn, line, file);
+ util_memory_d(ptrn);
return NULL;
}
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);
+ util_memory_d(oldinfo+1);
return NULL;
}
mem_start = newinfo;
mem_ab -= oldinfo->byte;
+ mem_hw -= oldinfo->byte;
mem_ab += newinfo->byte;
+ mem_hw += newinfo->byte;
+
+ PEAK_MEM;
free(oldinfo);
return newinfo+1;
}
+static void util_dumpmem(struct memblock_t *memory, uint16_t cols) {
+ uint32_t i, j;
+ for (i = 0; i < memory->byte + ((memory->byte % cols) ? (cols - memory->byte % cols) : 0); i++) {
+ if (i % cols == 0) con_out(" 0x%06X: ", i);
+ if (i < memory->byte) con_out("%02X " , 0xFF & ((char*)(memory + 1))[i]);
+ else con_out(" ");
+
+ if ((uint16_t)(i % cols) == (cols - 1)) {
+ for (j = i - (cols - 1); j <= i; j++) {
+ con_out("%c",
+ (j >= memory->byte)
+ ? ' '
+ : (isprint(((char*)(memory + 1))[j]))
+ ? 0xFF & ((char*)(memory + 1)) [j]
+ : '.'
+ );
+ }
+ con_out("\n");
+ }
+ }
+}
+
+/*
+ * The following is a VERY tight, efficent, hashtable for integer
+ * values and keys, and for nothing more. We could make our existing
+ * hashtable support type-genericness through a void * pointer but,
+ * ideally that would make things more complicated. We also don't need
+ * that much of a bloat for something as basic as this.
+ */
+typedef struct {
+ size_t key;
+ size_t value;
+} size_entry_t;
+#define ST_SIZE 1024
+
+typedef size_entry_t **size_table_t;
+
+size_table_t util_st_new() {
+ return (size_table_t)memset(
+ mem_a(sizeof(size_entry_t*) * ST_SIZE),
+ 0, ST_SIZE * sizeof(size_entry_t*)
+ );
+}
+void util_st_del(size_table_t table) {
+ size_t i = 0;
+ for (; i < ST_SIZE; i++) if(table[i]) mem_d(table[i]);
+ mem_d(table);
+}
+size_entry_t *util_st_get(size_table_t table, size_t key) {
+ size_t hash = (key % ST_SIZE);
+ while (table[hash] && table[hash]->key != key)
+ hash = (hash + 1) % ST_SIZE;
+ return table[hash];
+}
+void util_st_put(size_table_t table, size_t key, size_t value) {
+ size_t hash = (key % ST_SIZE);
+ while (table[hash] && table[hash]->key != key)
+ hash = (hash + 1) % ST_SIZE;
+ table[hash] = (size_entry_t*)mem_a(sizeof(size_entry_t));
+ table[hash]->key = key;
+ table[hash]->value = value;
+}
+
+static uint64_t strdups = 0;
+static uint64_t vectors = 0;
+static uint64_t vector_sizes = 0;
+static uint64_t hashtables = 0;
+static size_table_t vector_usage = NULL;
+
void util_meminfo() {
struct memblock_t *info;
- if (!opts.memchk)
- return;
+ if (OPTS_OPTION_BOOL(OPTION_DEBUG)) {
+ for (info = mem_start; info; info = info->next) {
+ con_out("lost: %u (bytes) at %s:%u\n",
+ info->byte,
+ info->file,
+ info->line);
- 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)
- );
+ util_dumpmem(info, OPTS_OPTION_U16(OPTION_MEMDUMPCOLS));
+ }
+ }
+
+ if (OPTS_OPTION_BOOL(OPTION_DEBUG) ||
+ OPTS_OPTION_BOOL(OPTION_MEMCHK)) {
+ con_out("Memory information:\n\
+ Total allocations: %llu\n\
+ Total deallocations: %llu\n\
+ Total allocated: %f (MB)\n\
+ Total deallocated: %f (MB)\n\
+ Total peak memory: %f (MB)\n\
+ Total leaked memory: %f (MB) in %llu allocations\n",
+ mem_at,
+ mem_dt,
+ (float)(mem_ab) / 1048576.0f,
+ (float)(mem_db) / 1048576.0f,
+ (float)(mem_pk) / 1048576.0f,
+ (float)(mem_ab - mem_db) / 1048576.0f,
+
+ /* could be more clever */
+ (mem_at - mem_dt)
+ );
+ }
+
+ if (OPTS_OPTION_BOOL(OPTION_STATISTICS) ||
+ OPTS_OPTION_BOOL(OPTION_MEMCHK)) {
+ size_t i=0;
+ size_t e=1;
+
+ con_out("Additional Statistics:\n\
+ Total vectors allocated: %llu\n\
+ Total string duplicates: %llu\n\
+ Total hashtables allocated: %llu\n\
+ Total unique vector sizes: %llu\n",
+ vectors,
+ strdups,
+ hashtables,
+ vector_sizes
+ );
+
+ for (; i < ST_SIZE; i++) {
+ size_entry_t *entry;
+
+ if (!(entry = vector_usage[i]))
+ continue;
+
+ con_out(" %u| # of %3u (bytes) vectors: %u\n",
+ (unsigned)e,
+ (unsigned)entry->key,
+ (unsigned)entry->value
+ );
+ e++;
+ }
+ }
+
+ if (vector_usage)
+ util_st_del(vector_usage);
}
/*
* Some string utility functions, because strdup uses malloc, and we want
* to track all memory (without replacing malloc).
*/
-char *util_strdup(const char *s) {
+char *_util_Estrdup(const char *s, const char *file, size_t line) {
size_t len = 0;
char *ptr = NULL;
+ /* in case of -DNOTRACK */
+ (void)file;
+ (void)line;
+
if (!s)
return NULL;
- if ((len = strlen(s)) && (ptr = (char*)mem_a(len+1))) {
+ if ((len = strlen(s)) && (ptr = (char*)mem_af(len+1, line, file))) {
memcpy(ptr, s, len);
ptr[len] = '\0';
}
+ strdups++;
+ return ptr;
+}
+
+char *_util_Estrdup_empty(const char *s, const char *file, size_t line) {
+ size_t len = 0;
+ char *ptr = NULL;
+
+ /* in case of -DNOTRACK */
+ (void)file;
+ (void)line;
+
+ if (!s)
+ return NULL;
+
+ len = strlen(s);
+ if ((ptr = (char*)mem_af(len+1, line, file))) {
+ memcpy(ptr, s, len);
+ ptr[len] = '\0';
+ }
+ strdups++;
return ptr;
}
void util_debug(const char *area, const char *ms, ...) {
va_list va;
- if (!opts.debug)
+ if (!OPTS_OPTION_BOOL(OPTION_DEBUG))
return;
- if (!strcmp(area, "MEM") && !opts.memchk)
+ if (!strcmp(area, "MEM") && !OPTS_OPTION_BOOL(OPTION_MEMCHK))
return;
va_start(va, ms);
/*
* only required if big endian .. otherwise no need to swap
* data.
- */
+ */
#if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_BIG
static GMQCC_INLINE void util_swap16(uint16_t *d, size_t l) {
while (l--) {
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
/* 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;
}
#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);
- return (~h)%clamp;
+ return (~h)%clamp;
}
#endif
/* TODO: rewrite ... when I redo the ve cleanup */
void _util_vec_grow(void **a, size_t i, size_t s) {
- vector_t *d = vec_meta(*a);
- size_t m = *a ? 2 * d->allocated +i : i+1;
- void *p = mem_r((*a ? d : NULL), s * m + sizeof(vector_t));
-
- if (!*a)
+ vector_t *d = vec_meta(*a);
+ size_t m = 0;
+ size_entry_t *e = NULL;
+ void *p = NULL;
+
+ if (*a) {
+ m = 2 * d->allocated + i;
+ p = mem_r(d, s * m + sizeof(vector_t));
+ } else {
+ m = i + 1;
+ p = mem_a(s * m + sizeof(vector_t));
((vector_t*)p)->used = 0;
- *a = (vector_t*)p + 1;
+ vectors++;
+ }
+
+ if (!vector_usage)
+ vector_usage = util_st_new();
+
+ if ((e = util_st_get(vector_usage, s))) {
+ e->value ++;
+ } else {
+ util_st_put(vector_usage, s, 1); /* start off with 1 */
+ vector_sizes++;
+ }
+ *a = (vector_t*)p + 1;
vec_meta(*a)->allocated = m;
}
const unsigned char *data = (const unsigned char*)key;
while (size >= 4) {
- alias = *(uint32_t*)data;
-
+ alias = (data[0] | (data[1] << 8) | (data[2] << 16) | (data[3] << 24));
alias *= mix;
alias ^= alias >> rot;
alias *= mix;
return (size_t) (hash % ht->size);
}
-hash_node_t *_util_htnewpair(const char *key, void *value) {
+static hash_node_t *_util_htnewpair(const char *key, void *value) {
hash_node_t *node;
if (!(node = (hash_node_t*)mem_a(sizeof(hash_node_t))))
return NULL;
- if (!(node->key = util_strdup(key))) {
+ if (!(node->key = util_strdupe(key))) {
mem_d(node);
return NULL;
}
hashtable->size = size;
memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
+ hashtables++;
return hashtable;
}
return util_htgeth(ht, key, util_hthash(ht, key));
}
+void *code_util_str_htgeth(hash_table_t *ht, const char *key, size_t bin) {
+ hash_node_t *pair;
+ size_t len, keylen;
+ int cmp;
+
+ keylen = strlen(key);
+
+ pair = ht->table[bin];
+ while (pair && pair->key) {
+ len = strlen(pair->key);
+ if (len < keylen) {
+ pair = pair->next;
+ continue;
+ }
+ if (keylen == len) {
+ cmp = strcmp(key, pair->key);
+ if (cmp == 0)
+ return pair->value;
+ if (cmp < 0)
+ return NULL;
+ pair = pair->next;
+ continue;
+ }
+ cmp = strcmp(key, pair->key + len - keylen);
+ if (cmp == 0) {
+ uintptr_t up = (uintptr_t)pair->value;
+ up += len - keylen;
+ return (void*)up;
+ }
+ pair = pair->next;
+ }
+ return NULL;
+}
+
/*
* Free all allocated data in a hashtable, this is quite the amount
* of work.
*/
-void util_htdel(hash_table_t *ht) {
+void util_htrem(hash_table_t *ht, void (*callback)(void *data)) {
size_t i = 0;
for (; i < ht->size; i++) {
hash_node_t *n = ht->table[i];
while (n) {
if (n->key)
mem_d(n->key);
+ if (callback)
+ callback(n->value);
p = n;
n = n->next;
mem_d(p);
mem_d(ht);
}
+void util_htrmh(hash_table_t *ht, const char *key, size_t bin, void (*cb)(void*)) {
+ hash_node_t **pair = &ht->table[bin];
+ hash_node_t *tmp;
+
+ while (*pair && (*pair)->key && strcmp(key, (*pair)->key) > 0)
+ pair = &(*pair)->next;
+
+ tmp = *pair;
+ if (!tmp || !tmp->key || strcmp(key, tmp->key) != 0)
+ return;
+
+ if (cb)
+ (*cb)(tmp->value);
+
+ *pair = tmp->next;
+ mem_d(tmp->key);
+ mem_d(tmp);
+}
+
+void util_htrm(hash_table_t *ht, const char *key, void (*cb)(void*)) {
+ util_htrmh(ht, key, util_hthash(ht, key), cb);
+}
+
+void util_htdel(hash_table_t *ht) {
+ util_htrem(ht, NULL);
+}
+
+/*
+ * 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;
+ }
+
+ 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;
+ }
+
+ /* 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;
+ }
+
+ *dat = tmp;
+ return len;
+ #endif
+}
+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;
+}
+
+/*
+ * 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);
+ }
+
+ const char *util_strerror(int num) {
+ char *allocated = NULL;
+ static bool install = false;
+ static size_t tries = 0;
+ char **vector = util_strerror_allocated();
+
+ /* try installing cleanup handler */
+ while (!install) {
+ if (tries == 32)
+ return "(unknown)";
+
+ 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;
+ }
+
+ 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;
+ }
+
+ char *util_strcat(char *dest, const char *src) {
+ strcat_s(dest, strlen(src), src);
+ return dest;
+ }
+
+ 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);
+
+ return rt;
+ }
+
+ char *util_strcat(char *dest, const char *src) {
+ return strcat(dest, src);
+ }
+
+ char *util_strncpy(char *dest, const char *src, size_t num) {
+ return strncpy(dest, src, num);
+ }
+
+#endif /*! _MSC_VER */
+
/*
* Implementation of the Mersenne twister PRNG (pseudo random numer
* generator). Implementation of MT19937. Has a period of 2^19937-1
* 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.
+ * information on how this clever trick works.
*/
static const uint32_t matrix[2] = {
0x00000000,
* to [0, MT_SIZE) (634 iterations).
*/
for (i = 0; i < MT_SPACE; ++i) {
- y = (0x800000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
+ y = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1];
i ++; /* loop unroll */
- y = (0x800000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
+ y = (0x80000000 & mt_state[i]) | (0x7FFFFFF & mt_state[i + 1]);
mt_state[i] = mt_state[i + MT_PERIOD] ^ (y >> 1) ^ matrix[y & 1];
}
projects / xonotic / gmqcc.git / blobdiff