Add entity property finding and L4D warp testing

This was a lot more code than expected, but it might be finally close to
time to release the next beta...

We'll see if any more rabbit holes present themselves to jump into,
though.

6 files changed, 417 insertions, 4 deletions

diff --git a/src/build/cmeta.c b/src/build/cmeta.c
index 3d9281a..bf18903 100644
--- a/src/build/cmeta.c
+++ b/src/build/cmeta.c
@@ -5,7 +5,7 @@
  * purpose with or without fee is hereby granted, provided that the above
  * copyright notice and this permission notice appear in all copies.
  *
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
+ * THE SOFTWARE IS PROVIDED “AS IS” AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  * AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
diff --git a/src/build/cmeta.h b/src/build/cmeta.h
index 20672f4..4757654 100644
--- a/src/build/cmeta.h
+++ b/src/build/cmeta.h
@@ -5,7 +5,7 @@
  * purpose with or without fee is hereby granted, provided that the above
  * copyright notice and this permission notice appear in all copies.
  *
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
+ * THE SOFTWARE IS PROVIDED “AS IS” AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  * AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
diff --git a/src/build/codegen.c b/src/build/codegen.c
index 6d5fc99..d96059d 100644
--- a/src/build/codegen.c
+++ b/src/build/codegen.c
@@ -5,7 +5,7 @@
  * purpose with or without fee is hereby granted, provided that the above
  * copyright notice and this permission notice appear in all copies.
  *
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
+ * THE SOFTWARE IS PROVIDED “AS IS” AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  * AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
diff --git a/src/build/mkentprops.c b/src/build/mkentprops.c
new file mode 100644
index 0000000..5dd2fea
--- /dev/null
+++ b/src/build/mkentprops.c
@@ -0,0 +1,208 @@
+/*
+ * Copyright © 2022 Michael Smith <mikesmiffy128@gmail.com>
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED “AS IS” AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
+ * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
+ * AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
+ * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
+ * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
+ * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+ * PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "../intdefs.h"
+#include "../kv.h"
+#include "../noreturn.h"
+#include "../os.h"
+#include "skiplist.h"
+#include "vec.h"
+
+#ifdef _WIN32
+#define fS "S"
+#else
+#define fS "s"
+#endif
+
+static noreturn die(const char *s) {
+	fprintf(stderr, "mkentprops: %s\n", s);
+	exit(100);
+}
+
+struct prop {
+	const char *varname; /* the C global name */
+	const char *propname; /* the entity property name */
+	struct prop *next;
+};
+struct vec_prop VEC(struct prop *);
+
+DECL_SKIPLIST(static, class, struct class, const char *, 4)
+struct class {
+	const char *name; /* the entity class name */
+	struct vec_prop props;
+	struct skiplist_hdr_class hdr;
+};
+static inline int cmp_class(struct class *c, const char *s) {
+	return strcmp(c->name, s);
+}
+static inline struct skiplist_hdr_class *hdr_class(struct class *c) {
+	return &c->hdr;
+}
+DEF_SKIPLIST(static, class, cmp_class, hdr_class)
+static struct skiplist_hdr_class classes = {0};
+static int nclasses = 0;
+
+struct parsestate {
+	const os_char *filename;
+	struct kv_parser *parser;
+	char *lastvar;
+};
+
+static noreturn badparse(struct parsestate *state, const char *e) {
+	fprintf(stderr, "mkentprops: %" fS ":%d:%d: parse error: %s",
+			state->filename, state->parser->line, state->parser->col, e);
+	exit(1);
+}
+
+static void kv_cb(enum kv_token type, const char *p, uint len, void *ctxt) {
+	struct parsestate *state = ctxt;
+	switch (type) {
+		case KV_IDENT: case KV_IDENT_QUOTED:
+			state->lastvar = malloc(len + 1);
+			if (!state->lastvar) die("couldn't allocate memory");
+			memcpy(state->lastvar, p, len); state->lastvar[len] = '\0';
+			break;
+		case KV_NEST_START: badparse(state, "unexpected nested block");
+		case KV_NEST_END: badparse(state, "unexpected closing brace");
+		case KV_VAL: case KV_VAL_QUOTED:;
+			struct prop *prop = malloc(sizeof(*prop));
+			if (!p) die("couldn't allocate memory");
+			prop->varname = state->lastvar;
+			char *classname = malloc(len + 1);
+			if (!classname) die("couldn't allocate memory");
+			memcpy(classname, p, len); classname[len] = '\0';
+			char *propname = strchr(classname, '/');
+			if (!propname) {
+				badparse(state, "network name not in class/prop format");
+			}
+			*propname = '\0'; ++propname; // split!
+			prop->propname = propname;
+			struct class *class = skiplist_get_class(&classes, classname);
+			if (!class) {
+				class = malloc(sizeof(*class));
+				if (!class) die("couldn't allocate memory");
+				*class = (struct class){.name = classname};
+				skiplist_insert_class(&classes, classname, class);
+				++nclasses;
+			}
+			// (if class is already there just leak classname, no point freeing)
+			if (!vec_push(&class->props, prop)) die("couldn't append to array");
+			break;
+		case KV_COND_PREFIX: case KV_COND_SUFFIX:
+			badparse(state, "unexpected conditional");
+	}
+}
+
+static inline noreturn diewrite(void) { die("couldn't write to file"); }
+
+#define _(x) \
+	if (fprintf(out, "%s\n", x) < 0) diewrite();
+#define F(f, ...) \
+	if (fprintf(out, f "\n", __VA_ARGS__) < 0) diewrite();
+#define H() \
+_( "/* This file is autogenerated by src/build/mkentprops.c. DO NOT EDIT! */") \
+_( "")
+
+static void decls(FILE *out) {
+	for (struct class *c = classes.x[0]; c; c = c->hdr.x[0]) {
+		for (struct prop **pp = c->props.data;
+				pp - c->props.data < c->props.sz; ++pp) {
+F( "extern bool has_%s;", (*pp)->varname)
+F( "extern int %s;", (*pp)->varname)
+		}
+	}
+}
+
+static void defs(FILE *out) {
+	for (struct class *c = classes.x[0]; c; c = c->hdr.x[0]) {
+		for (struct prop **pp = c->props.data;
+				pp - c->props.data < c->props.sz; ++pp) {
+F( "bool has_%s = false;", (*pp)->varname)
+F( "int %s;", (*pp)->varname)
+		}
+	}
+_( "")
+_( "static void initentprops(struct ServerClass *class) {")
+F( "	for (int needclasses = %d; class; class = class->next) {", nclasses)
+	char *else1 = "";
+	for (struct class *c = classes.x[0]; c; c = c->hdr.x[0]) {
+		// TODO(opt): some sort of PHF instead of chained strcmp, if we ever
+		// have more than a few classes/properties?
+F( "		%sif (!strcmp(class->name, \"%s\")) {", else1, c->name)
+_( "			struct SendTable *st = class->table;")
+				// christ this is awful :(
+F( "			int needprops = %d;", c->props.sz)
+_( "			for (struct SendProp *p = st->props; (char *)p -")
+_( "					(char *)st->props < st->nprops * sz_SendProp;")
+_( "					p = mem_offset(p, sz_SendProp)) {")
+		char *else2 = "";
+		for (struct prop **pp = c->props.data;
+				pp - c->props.data < c->props.sz; ++pp) {
+F( "				%sif (!strcmp(*(const char **)mem_offset(p, off_SP_varname), \"%s\")) {",
+		else2, (*pp)->propname) // ugh
+F( "					has_%s = true;", (*pp)->varname)
+F( "					%s = *(int *)mem_offset(p, off_SP_offset);", (*pp)->varname)
+_( "					if (!--needprops) break;")
+_( "				}")
+			else2 = "else ";
+		}
+_( "			}")
+_( "			if (!--needclasses) break;")
+_( "		}")
+		else1 = "else ";
+	}
+_( "	}")
+_( "}")
+}
+
+int OS_MAIN(int argc, os_char *argv[]) {
+	for (++argv; *argv; ++argv) {
+		int fd = os_open(*argv, O_RDONLY);
+		if (fd == -1) die("couldn't open file");
+		struct kv_parser kv = {0};
+		struct parsestate state = {*argv, &kv};
+		char buf[1024];
+		int nread;
+		while (nread = read(fd, buf, sizeof(buf))) {
+			if (nread == -1) die("couldn't read file");
+			if (!kv_parser_feed(&kv, buf, nread, &kv_cb, &state)) goto ep;
+		}
+		if (!kv_parser_done(&kv)) {
+ep:			fprintf(stderr, "mkentprops: %" fS ":%d:%d: bad syntax: %s\n",
+					*argv, kv.line, kv.col, kv.errmsg);
+			exit(1);
+		}
+		close(fd);
+	}
+
+	FILE *out = fopen(".build/include/entprops.gen.h", "wb");
+	if (!out) die("couldn't open entprops.gen.h");
+	H();
+	decls(out);
+
+	out = fopen(".build/include/entpropsinit.gen.h", "wb");
+	if (!out) die("couldn't open entpropsinit.gen.h");
+	H();
+	defs(out);
+	return 0;
+}
+
+// vi: sw=4 ts=4 noet tw=80 cc=80
diff --git a/src/build/mkgamedata.c b/src/build/mkgamedata.c
index d17d7df..ce6490e 100644
--- a/src/build/mkgamedata.c
+++ b/src/build/mkgamedata.c
@@ -5,7 +5,7 @@
  * purpose with or without fee is hereby granted, provided that the above
  * copyright notice and this permission notice appear in all copies.
  *
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
+ * THE SOFTWARE IS PROVIDED “AS IS” AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  * AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
diff --git a/src/build/skiplist.h b/src/build/skiplist.h
new file mode 100644
index 0000000..b747d89
--- /dev/null
+++ b/src/build/skiplist.h
@@ -0,0 +1,205 @@
+/*
+ * Copyright © 2022 Michael Smith <mikesmiffy128@gmail.com>
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED “AS IS” AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
+ * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
+ * AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
+ * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
+ * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
+ * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+ * PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifndef INC_SKIPLIST_H
+#define INC_SKIPLIST_H
+
+#include <stdlib.h>
+
+#include "../intdefs.h"
+#include "../os.h"
+
+#ifdef _WIN32
+static inline int _skiplist_ffs(uint x) {
+	uint ret;
+	// on Windows, sizeof(ulong) == sizeof(uint)
+	if (_BitScanForward((ulong *)&ret, x)) return ret + 1; else return 0;
+}
+#else
+#include <strings.h>
+#define _skiplist_ffs ffs
+#endif
+
+// WARNING: this is a really hacked-up version of the skiplist.h from cbits in
+// order to support windows. It probably isn't a good idea to plop straight into
+// your own use case.
+
+#if defined(__GNUC__) || defined(__clang__)
+#define _skiplist_unused __attribute__((unused)) // heck off gcc
+#else
+#define _skiplist_unused
+#endif
+
+// NOTE: using xoroshiro128++, a comparatively bad (i.e. non-cryptographic) prng
+// for the sake of simplicity; original cbits skiplist.h relies on libcpoly to
+// get arc4random() everywhere but since we're only using this at build time
+// that seemed like a silly dependency to bother with.
+//#define _skiplist_rng arc4random
+
+// ALSO NOTE: the PRNG code here is *decidedly not* thread safe. again, this
+// isn't a problem for our use case. just keep it in mind if reusing this header
+// for something else. or ideally, don't reuse this header for something else...
+static inline uvlong _skiplist_rotl(const uvlong x, int k) {
+	return (x << k) | (x >> (64 - k));
+}
+_skiplist_unused static uvlong _skiplist_rng(void) {
+	static uvlong s[2];
+	static bool init = false;
+	if (!init) { os_randombytes(s, sizeof(s)); init = true; }
+	uvlong s0 = s[0], s1 = s[1];
+	uvlong ret = _skiplist_rotl(s0 * 5, 7) * 9;
+	s1 ^= s0;
+	s[0] = _skiplist_rotl(s0, 24) ^ s1 ^ (s1 << 16);
+	s[1] = _skiplist_rotl(s1, 37);
+	return ret;
+}
+
+/*
+ * Declares the skiplist header struct skiplist_hdr##name, but none of the
+ * associated functions. Use when the structure needs to be passed around in
+ * some way but actual operations on the list are a private implementation
+ * detail. Otherwise, see DECL_SKIPLIST below.
+ */
+#define DECL_SKIPLIST_TYPE(name, dtype, ktype, levels) \
+typedef dtype _skiplist_dt_##name; \
+typedef ktype _skiplist_kt_##name; \
+enum { skiplist_lvls_##name = (levels) }; \
+struct skiplist_hdr_##name { dtype *x[levels]; };
+
+/*
+ * Declares the skiplist header struct skiplist_hdr_##name, with functions
+ * skiplist_{get,del,pop,insert}_##name for operating on the list. A single
+ * occurrence of DEF_SKIPLIST is required to actually implement the
+ * functions.
+ *
+ * This macro implies DECL_SKIPLIST_TYPE (both should not be used).
+ *
+ * mod should be either static or extern.
+ *
+ * dtype should be the struct type that the skiplist header will be embedded in,
+ * forming the linked structure.
+ *
+ * ktype should be the type of the struct member used for comparisons, for
+ * example int or char *.
+ *
+ * levels should be the number of levels in each node. 4 is probably a
+ * reasonable number, depending on the size of the structure and how many
+ * entries need to be stored and looked up.
+ *
+ * The resulting get, del, pop and insert functions are hopefully self-
+ * explanatory - get and del return the relevant node or a null pointer if
+ * no such node is found.
+ */
+#define DECL_SKIPLIST(mod, name, dtype, ktype, levels) \
+DECL_SKIPLIST_TYPE(name, dtype, ktype, levels) \
+\
+_skiplist_unused mod dtype *skiplist_get_##name(struct skiplist_hdr_##name *l, \
+		ktype k); \
+_skiplist_unused mod dtype *skiplist_del_##name(struct skiplist_hdr_##name *l, \
+		ktype k); \
+_skiplist_unused mod dtype *skiplist_pop_##name(struct skiplist_hdr_##name *l); \
+_skiplist_unused mod void skiplist_insert_##name(struct skiplist_hdr_##name *l, \
+		ktype k, dtype *node);
+
+/*
+ * Implements the functions corresponding to a skiplist - must come after
+ * DECL_SKIPLIST with the same modifier and name.
+ *
+ * compfunc should be a function declared as follows (or an equivalent macro):
+ * int cf(dtype *x, ktype y);
+ *
+ * hdrfunc should be a function declared as follows (or an equivalent macro):
+ * struct skiplist_hdr_##name *hf(dtype *l);
+ */
+#define DEF_SKIPLIST(mod, name, compfunc, hdrfunc) \
+static inline int _skiplist_lvl_##name(void) { \
+	int i; \
+	/* for 2 levels we get 1 50% of the time, 2 25% of the time, 0 25% of the
+	   time. loop if 0 to distribute this evenly (this gets less likely the more
+	   levels there are: at 4 levels, only loops 6% of the time) */ \
+	while (!(i = _skiplist_ffs(_skiplist_rng() & \
+			((1 << skiplist_lvls_##name) - 1)))); \
+	/* ffs gives bit positions as 1-N but we actually want an array index */ \
+	return i - 1; \
+} \
+\
+_skiplist_unused \
+mod _skiplist_dt_##name *skiplist_get_##name(struct skiplist_hdr_##name *l, \
+		_skiplist_kt_##name k) { \
+	for (int cmp, lvl = skiplist_lvls_##name - 1; lvl > -1; --lvl) { \
+		while (l->x[lvl] && (cmp = compfunc(l->x[lvl], k)) < 0) { \
+			l = hdrfunc(l->x[lvl]); \
+		} \
+		/* NOTE: cmp can be uninitialised here, but only if the list is
+		   completely empty, in which case we'd return 0 anyway - so it doesn't
+		   actually matter! */ \
+		if (cmp == 0) return l->x[lvl]; \
+	} \
+	/* reached the end, no match */ \
+	return 0; \
+} \
+\
+_skiplist_unused \
+_skiplist_dt_##name *skiplist_del_##name(struct skiplist_hdr_##name *l, \
+		_skiplist_kt_##name k) { \
+	_skiplist_dt_##name *ret = 0; \
+	/* ALSO NOTE: in *this* case, cmp DOES need to be initialised to prevent a
+	   possible null-deref via hdrfunc(l->x[lvl])->x */ \
+	for (int cmp = 1, lvl = skiplist_lvls_##name - 1; lvl > -1; --lvl) { \
+		while (l->x[lvl] && (cmp = compfunc(l->x[lvl], k)) < 0) { \
+			l = hdrfunc(l->x[lvl]); \
+		} \
+		if (cmp == 0) { \
+			ret = l->x[lvl]; \
+			/* just shift each link by 1 */ \
+			l->x[lvl] = hdrfunc(l->x[lvl])->x[0]; \
+			/* ... and update every level of links via loop */ \
+		} \
+	} \
+	/* reached the end, return whatever was found */ \
+	return ret; \
+} \
+\
+_skiplist_unused \
+mod _skiplist_dt_##name *skiplist_pop_##name(struct skiplist_hdr_##name *l) { \
+	_skiplist_dt_##name *cur = l->x[0]; \
+	if (!cur) return 0; \
+	l->x[0] = hdrfunc(cur)->x[0]; \
+	for (int lvl = 1; lvl < skiplist_lvls_##name; ++lvl) { \
+		if (l->x[lvl]) l->x[lvl] = hdrfunc(l->x[lvl])->x[lvl]; \
+	} \
+	return cur; \
+} \
+\
+_skiplist_unused \
+mod void skiplist_insert_##name(struct skiplist_hdr_##name *l, \
+		_skiplist_kt_##name k, _skiplist_dt_##name *node) { \
+	/* note: higher levels are unset but also skipped in other searches */ \
+	int inslvl = _skiplist_lvl_##name(); \
+	for (int lvl = skiplist_lvls_##name - 1; lvl > -1; --lvl) { \
+		while (l->x[lvl] && compfunc(l->x[lvl], k) < 0) { \
+			l = hdrfunc(l->x[lvl]); \
+		} \
+		if (lvl <= inslvl) { \
+			hdrfunc(node)->x[lvl] = l->x[lvl]; \
+			l->x[lvl] = node; \
+		} \
+	} \
+} \
+
+#endif
+
+// vi: sw=4 ts=4 noet tw=80 cc=80