6 files changed, 463 insertions, 0 deletions
diff --git a/util/array.c b/util/array.c
new file mode 100644
index 00000000..9ee39d33
--- /dev/null
+++ b/util/array.c
@@ -0,0 +1,21 @@
+#include <stdlib.h>
+#include <stdint.h>
+
+// https://www.geeksforgeeks.org/move-zeroes-end-array/
+size_t push_zeroes_to_end(uint32_t arr[], size_t n) {
+	size_t count = 0;
+
+	for (size_t i = 0; i < n; i++) {
+		if (arr[i] != 0) {
+			arr[count++] = arr[i];
+		}
+	}
+
+	size_t ret = count;
+
+	while (count < n) {
+		arr[count++] = 0;
+	}
+
+	return ret;
+}
diff --git a/util/log.c b/util/log.c
new file mode 100644
index 00000000..3ef5f484
--- /dev/null
+++ b/util/log.c
@@ -0,0 +1,91 @@
+#define _POSIX_C_SOURCE 199506L
+#include <errno.h>
+#include <stdarg.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include <unistd.h>
+#include <wlr/util/log.h>
+
+static bool colored = true;
+static enum wlr_log_importance log_importance = WLR_ERROR;
+
+static const char *verbosity_colors[] = {
+	[WLR_SILENT] = "",
+	[WLR_ERROR ] = "\x1B[1;31m",
+	[WLR_INFO  ] = "\x1B[1;34m",
+	[WLR_DEBUG ] = "\x1B[1;30m",
+};
+
+static void log_stderr(enum wlr_log_importance verbosity, const char *fmt,
+		va_list args) {
+	if (verbosity > log_importance) {
+		return;
+	}
+	// prefix the time to the log message
+	struct tm result;
+	time_t t = time(NULL);
+	struct tm *tm_info = localtime_r(&t, &result);
+	char buffer[26];
+
+	// generate time prefix
+	strftime(buffer, sizeof(buffer), "%F %T - ", tm_info);
+	fprintf(stderr, "%s", buffer);
+
+	unsigned c = (verbosity < WLR_LOG_IMPORTANCE_LAST) ? verbosity : WLR_LOG_IMPORTANCE_LAST - 1;
+
+	if (colored && isatty(STDERR_FILENO)) {
+		fprintf(stderr, "%s", verbosity_colors[c]);
+	}
+
+	vfprintf(stderr, fmt, args);
+
+	if (colored && isatty(STDERR_FILENO)) {
+		fprintf(stderr, "\x1B[0m");
+	}
+	fprintf(stderr, "\n");
+}
+
+static wlr_log_func_t log_callback = log_stderr;
+
+void wlr_log_init(enum wlr_log_importance verbosity, wlr_log_func_t callback) {
+	if (verbosity < WLR_LOG_IMPORTANCE_LAST) {
+		log_importance = verbosity;
+	}
+	if (callback) {
+		log_callback = callback;
+	}
+}
+
+void _wlr_vlog(enum wlr_log_importance verbosity, const char *fmt, va_list args) {
+	log_callback(verbosity, fmt, args);
+}
+
+void _wlr_log(enum wlr_log_importance verbosity, const char *fmt, ...) {
+	va_list args;
+	va_start(args, fmt);
+	log_callback(verbosity, fmt, args);
+	va_end(args);
+}
+
+// strips the path prefix from filepath
+// will try to strip WLR_SRC_DIR as well as a relative src dir
+// e.g. '/src/build/wlroots/backend/wayland/backend.c' and
+// '../backend/wayland/backend.c' will both be stripped to
+// 'backend/wayland/backend.c'
+const char *_wlr_strip_path(const char *filepath) {
+	static int srclen = sizeof(WLR_SRC_DIR);
+	if (strstr(filepath, WLR_SRC_DIR) == filepath) {
+		filepath += srclen;
+	} else if (*filepath == '.') {
+		while (*filepath == '.' || *filepath == '/') {
+			++filepath;
+		}
+	}
+	return filepath;
+}
+
+enum wlr_log_importance wlr_log_get_verbosity(void) {
+	return log_importance;
+}
diff --git a/util/meson.build b/util/meson.build
new file mode 100644
index 00000000..dca3e9a4
--- /dev/null
+++ b/util/meson.build
@@ -0,0 +1,12 @@
+lib_wlr_util = static_library(
+	'wlr_util',
+	files(
+		'array.c',
+		'log.c',
+		'region.c',
+		'shm.c',
+		'signal.c',
+	),
+	include_directories: wlr_inc,
+	dependencies: [wayland_server, pixman, rt],
+)
diff --git a/util/region.c b/util/region.c
new file mode 100644
index 00000000..61f9c7c7
--- /dev/null
+++ b/util/region.c
@@ -0,0 +1,250 @@
+#include <assert.h>
+#include <math.h>
+#include <limits.h>
+#include <stdlib.h>
+#include <wlr/types/wlr_box.h>
+#include <wlr/util/region.h>
+
+void wlr_region_scale(pixman_region32_t *dst, pixman_region32_t *src,
+		float scale) {
+	if (scale == 1) {
+		pixman_region32_copy(dst, src);
+		return;
+	}
+
+	int nrects;
+	pixman_box32_t *src_rects = pixman_region32_rectangles(src, &nrects);
+
+	pixman_box32_t *dst_rects = malloc(nrects * sizeof(pixman_box32_t));
+	if (dst_rects == NULL) {
+		return;
+	}
+
+	for (int i = 0; i < nrects; ++i) {
+		dst_rects[i].x1 = floor(src_rects[i].x1 * scale);
+		dst_rects[i].x2 = ceil(src_rects[i].x2 * scale);
+		dst_rects[i].y1 = floor(src_rects[i].y1 * scale);
+		dst_rects[i].y2 = ceil(src_rects[i].y2 * scale);
+	}
+
+	pixman_region32_fini(dst);
+	pixman_region32_init_rects(dst, dst_rects, nrects);
+	free(dst_rects);
+}
+
+void wlr_region_transform(pixman_region32_t *dst, pixman_region32_t *src,
+		enum wl_output_transform transform, int width, int height) {
+	if (transform == WL_OUTPUT_TRANSFORM_NORMAL) {
+		pixman_region32_copy(dst, src);
+		return;
+	}
+
+	int nrects;
+	pixman_box32_t *src_rects = pixman_region32_rectangles(src, &nrects);
+
+	pixman_box32_t *dst_rects = malloc(nrects * sizeof(pixman_box32_t));
+	if (dst_rects == NULL) {
+		return;
+	}
+
+	for (int i = 0; i < nrects; ++i) {
+		switch (transform) {
+		case WL_OUTPUT_TRANSFORM_NORMAL:
+			dst_rects[i].x1 = src_rects[i].x1;
+			dst_rects[i].y1 = src_rects[i].y1;
+			dst_rects[i].x2 = src_rects[i].x2;
+			dst_rects[i].y2 = src_rects[i].y2;
+			break;
+		case WL_OUTPUT_TRANSFORM_90:
+			dst_rects[i].x1 = src_rects[i].y1;
+			dst_rects[i].y1 = width - src_rects[i].x2;
+			dst_rects[i].x2 = src_rects[i].y2;
+			dst_rects[i].y2 = width - src_rects[i].x1;
+			break;
+		case WL_OUTPUT_TRANSFORM_180:
+			dst_rects[i].x1 = width - src_rects[i].x2;
+			dst_rects[i].y1 = height - src_rects[i].y2;
+			dst_rects[i].x2 = width - src_rects[i].x1;
+			dst_rects[i].y2 = height - src_rects[i].y1;
+			break;
+		case WL_OUTPUT_TRANSFORM_270:
+			dst_rects[i].x1 = height - src_rects[i].y2;
+			dst_rects[i].y1 = src_rects[i].x1;
+			dst_rects[i].x2 = height - src_rects[i].y1;
+			dst_rects[i].y2 = src_rects[i].x2;
+			break;
+		case WL_OUTPUT_TRANSFORM_FLIPPED:
+			dst_rects[i].x1 = width - src_rects[i].x2;
+			dst_rects[i].y1 = src_rects[i].y1;
+			dst_rects[i].x2 = width - src_rects[i].x1;
+			dst_rects[i].y2 = src_rects[i].y2;
+			break;
+		case WL_OUTPUT_TRANSFORM_FLIPPED_90:
+			dst_rects[i].x1 = height - src_rects[i].y2;
+			dst_rects[i].y1 = width - src_rects[i].x2;
+			dst_rects[i].x2 = height - src_rects[i].y1;
+			dst_rects[i].y2 = width - src_rects[i].x1;
+			break;
+		case WL_OUTPUT_TRANSFORM_FLIPPED_180:
+			dst_rects[i].x1 = src_rects[i].x1;
+			dst_rects[i].y1 = height - src_rects[i].y2;
+			dst_rects[i].x2 = src_rects[i].x2;
+			dst_rects[i].y2 = height - src_rects[i].y1;
+			break;
+		case WL_OUTPUT_TRANSFORM_FLIPPED_270:
+			dst_rects[i].x1 = src_rects[i].y1;
+			dst_rects[i].y1 = src_rects[i].x1;
+			dst_rects[i].x2 = src_rects[i].y2;
+			dst_rects[i].y2 = src_rects[i].x2;
+			break;
+		}
+	}
+
+	pixman_region32_fini(dst);
+	pixman_region32_init_rects(dst, dst_rects, nrects);
+	free(dst_rects);
+}
+
+void wlr_region_expand(pixman_region32_t *dst, pixman_region32_t *src,
+		int distance) {
+	if (distance == 0) {
+		pixman_region32_copy(dst, src);
+		return;
+	}
+
+	int nrects;
+	pixman_box32_t *src_rects = pixman_region32_rectangles(src, &nrects);
+
+	pixman_box32_t *dst_rects = malloc(nrects * sizeof(pixman_box32_t));
+	if (dst_rects == NULL) {
+		return;
+	}
+
+	for (int i = 0; i < nrects; ++i) {
+		dst_rects[i].x1 = src_rects[i].x1 - distance;
+		dst_rects[i].x2 = src_rects[i].x2 + distance;
+		dst_rects[i].y1 = src_rects[i].y1 - distance;
+		dst_rects[i].y2 = src_rects[i].y2 + distance;
+	}
+
+	pixman_region32_fini(dst);
+	pixman_region32_init_rects(dst, dst_rects, nrects);
+	free(dst_rects);
+}
+
+void wlr_region_rotated_bounds(pixman_region32_t *dst, pixman_region32_t *src,
+		float rotation, int ox, int oy) {
+	if (rotation == 0) {
+		pixman_region32_copy(dst, src);
+		return;
+	}
+
+	int nrects;
+	pixman_box32_t *src_rects = pixman_region32_rectangles(src, &nrects);
+
+	pixman_box32_t *dst_rects = malloc(nrects * sizeof(pixman_box32_t));
+	if (dst_rects == NULL) {
+		return;
+	}
+
+	for (int i = 0; i < nrects; ++i) {
+		double x1 = src_rects[i].x1 - ox;
+		double y1 = src_rects[i].y1 - oy;
+		double x2 = src_rects[i].x2 - ox;
+		double y2 = src_rects[i].y2 - oy;
+
+		double rx1 = x1 * cos(rotation) - y1 * sin(rotation);
+		double ry1 = x1 * sin(rotation) + y1 * cos(rotation);
+
+		double rx2 = x2 * cos(rotation) - y1 * sin(rotation);
+		double ry2 = x2 * sin(rotation) + y1 * cos(rotation);
+
+		double rx3 = x2 * cos(rotation) - y2 * sin(rotation);
+		double ry3 = x2 * sin(rotation) + y2 * cos(rotation);
+
+		double rx4 = x1 * cos(rotation) - y2 * sin(rotation);
+		double ry4 = x1 * sin(rotation) + y2 * cos(rotation);
+
+		x1 = fmin(fmin(rx1, rx2), fmin(rx3, rx4));
+		y1 = fmin(fmin(ry1, ry2), fmin(ry3, ry4));
+		x2 = fmax(fmax(rx1, rx2), fmax(rx3, rx4));
+		y2 = fmax(fmax(ry1, ry2), fmax(ry3, ry4));
+
+		dst_rects[i].x1 = floor(ox + x1);
+		dst_rects[i].x2 = ceil(ox + x2);
+		dst_rects[i].y1 = floor(oy + y1);
+		dst_rects[i].y2 = ceil(oy + y2);
+	}
+
+	pixman_region32_fini(dst);
+	pixman_region32_init_rects(dst, dst_rects, nrects);
+	free(dst_rects);
+}
+
+static void region_confine(pixman_region32_t *region, double x1, double y1, double x2,
+		double y2, double *x2_out, double *y2_out, pixman_box32_t box) {
+	double x_clamped = fmax(fmin(x2, box.x2 - 1), box.x1);
+	double y_clamped = fmax(fmin(y2, box.y2 - 1), box.y1);
+
+	// If the target coordinates are above box.{x,y}2 - 1, but less than
+	// box.{x,y}2, then they are still within the box.
+	if (floor(x_clamped) == floor(x2) && floor(y_clamped) == floor(y2)) {
+		*x2_out = x2;
+		*y2_out = y2;
+		return;
+	}
+
+	double dx = x2 - x1;
+	double dy = y2 - y1;
+
+	// We use fabs to avoid negative zeroes and thus avoid a bug
+	// with negative infinity.
+	double delta = fmin(fabs(x_clamped - x1) / fabs(dx), fabs(y_clamped - y1) / fabs(dy));
+
+	// We clamp it again due to precision errors.
+	double x = fmax(fmin(delta * dx + x1, box.x2 - 1), box.x1);
+	double y = fmax(fmin(delta * dy + y1, box.y2 - 1), box.y1);
+
+	// Go one unit past the boundary to find an adjacent box.
+	int x_ext = floor(x) + (dx == 0 ? 0 : dx > 0 ? 1 : -1);
+	int y_ext = floor(y) + (dy == 0 ? 0 : dy > 0 ? 1 : -1);
+
+	if (pixman_region32_contains_point(region, x_ext, y_ext, &box)) {
+		return region_confine(region, x1, y1, x2, y2, x2_out, y2_out, box);
+	} else if (dx == 0 || dy == 0) {
+		*x2_out = x;
+		*y2_out = y;
+	} else {
+		bool bordering_x = x == box.x1 || x == box.x2 - 1;
+		bool bordering_y = y == box.y1 || y == box.y2 - 1;
+
+		if ((bordering_x && bordering_y) || (!bordering_x && !bordering_y)) {
+			double x2_potential, y2_potential;
+			double tmp1, tmp2;
+			region_confine(region, x, y, x, y2, &tmp1, &y2_potential, box);
+			region_confine(region, x, y, x2, y, &x2_potential, &tmp2, box);
+			if (fabs(x2_potential - x) > fabs(y2_potential - y)) {
+				*x2_out = x2_potential;
+				*y2_out = y;
+			} else {
+				*x2_out = x;
+				*y2_out = y2_potential;
+			}
+		} else if (bordering_x) {
+			return region_confine(region, x, y, x, y2, x2_out, y2_out, box);
+		} else if (bordering_y) {
+			return region_confine(region, x, y, x2, y, x2_out, y2_out, box);
+		}
+	}
+}
+
+bool wlr_region_confine(pixman_region32_t *region, double x1, double y1, double x2,
+		double y2, double *x2_out, double *y2_out) {
+	pixman_box32_t box;
+	if (pixman_region32_contains_point(region, floor(x1), floor(y1), &box)) {
+		region_confine(region, x1, y1, x2, y2, x2_out, y2_out, box);
+		return true;
+	} else {
+		return false;
+	}
+}
diff --git a/util/shm.c b/util/shm.c
new file mode 100644
index 00000000..f7c7303e
--- /dev/null
+++ b/util/shm.c
@@ -0,0 +1,55 @@
+#define _POSIX_C_SOURCE 200112L
+#include <errno.h>
+#include <fcntl.h>
+#include <string.h>
+#include <sys/mman.h>
+#include <time.h>
+#include <unistd.h>
+#include <wlr/config.h>
+#include "util/shm.h"
+
+static void randname(char *buf) {
+	struct timespec ts;
+	clock_gettime(CLOCK_REALTIME, &ts);
+	long r = ts.tv_nsec;
+	for (int i = 0; i < 6; ++i) {
+		buf[i] = 'A'+(r&15)+(r&16)*2;
+		r >>= 5;
+	}
+}
+
+int create_shm_file(void) {
+	int retries = 100;
+	do {
+		char name[] = "/wlroots-XXXXXX";
+		randname(name + strlen(name) - 6);
+
+		--retries;
+		// CLOEXEC is guaranteed to be set by shm_open
+		int fd = shm_open(name, O_RDWR | O_CREAT | O_EXCL, 0600);
+		if (fd >= 0) {
+			shm_unlink(name);
+			return fd;
+		}
+	} while (retries > 0 && errno == EEXIST);
+
+	return -1;
+}
+
+int allocate_shm_file(size_t size) {
+	int fd = create_shm_file();
+	if (fd < 0) {
+		return -1;
+	}
+
+	int ret;
+	do {
+		ret = ftruncate(fd, size);
+	} while (ret < 0 && errno == EINTR);
+	if (ret < 0) {
+		close(fd);
+		return -1;
+	}
+
+	return fd;
+}
diff --git a/util/signal.c b/util/signal.c
new file mode 100644
index 00000000..39618465
--- /dev/null
+++ b/util/signal.c
@@ -0,0 +1,34 @@
+#include "util/signal.h"
+
+static void handle_noop(struct wl_listener *listener, void *data) {
+	// Do nothing
+}
+
+void wlr_signal_emit_safe(struct wl_signal *signal, void *data) {
+	struct wl_listener cursor;
+	struct wl_listener end;
+
+	/* Add two special markers: one cursor and one end marker. This way, we know
+	 * that we've already called listeners on the left of the cursor and that we
+	 * don't want to call listeners on the right of the end marker. The 'it'
+	 * function can remove any element it wants from the list without troubles.
+	 * wl_list_for_each_safe tries to be safe but it fails: it works fine
+	 * if the current item is removed, but not if the next one is. */
+	wl_list_insert(&signal->listener_list, &cursor.link);
+	cursor.notify = handle_noop;
+	wl_list_insert(signal->listener_list.prev, &end.link);
+	end.notify = handle_noop;
+
+	while (cursor.link.next != &end.link) {
+		struct wl_list *pos = cursor.link.next;
+		struct wl_listener *l = wl_container_of(pos, l, link);
+
+		wl_list_remove(&cursor.link);
+		wl_list_insert(pos, &cursor.link);
+
+		l->notify(l, data);
+	}
+
+	wl_list_remove(&cursor.link);
+	wl_list_remove(&end.link);
+}