font: unifont: compress binary data and link via ld directly

Instead of using the blown up UTERM_FORMAT_GREY binary data, we now use an
A1 1bit alpha channel and extract the data during runtime. This guarantees
that only used characters will be extracted into the full alpha channel.

We should add support for A1 formats in uterm to avoid this problem
entirely.

We also now link the binary file directly into the module via ld. This
avoids the long compile times for the huge C-array that we previously
generated. As a side effect, you no longer run out of memory linking this
file on small machines.

With this change we could even start making unifont a default font-backend
as it now works pretty well.

Signed-off-by: David Herrmann <dh.herrmann@googlemail.com>

4 files changed, 254 insertions, 198 deletions

diff --git a/.gitignore b/.gitignore
index 2695708..abdf069 100644
--- a/.gitignore
+++ b/.gitignore
@@ -32,7 +32,7 @@ genunifont
 src/static_shaders.c
 src/genshader.c
 src/githead.h
-src/text_font_unifont_data.c
+src/font_unifont_data.bin
 docs/reference/*.txt
 docs/reference/*.bak
 docs/reference/kmscon.????*
diff --git a/Makefile.am b/Makefile.am
index 1b221bb..30d8672 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -382,14 +382,15 @@ src/static_shaders.c: $(SHADERS) genshader$(EXEEXT)
 # This generates the unifont sources from raw hex-encoded font data.
 #
 
-UNIFONT = src/font_unifont_data.hex
+UNIFONT = $(top_srcdir)/src/font_unifont_data.hex
+UNIFONT_BIN = src/font_unifont_data.bin
 
 EXTRA_DIST += $(UNIFONT)
-CLEANFILES += src/font_unifont_data.c
+CLEANFILES += $(UNIFONT_BIN)
 genunifont_SOURCES = src/genunifont.c
 
-src/font_unifont_data.c: $(UNIFONT) genunifont$(EXEEXT)
-	$(AM_V_GEN)./genunifont$(EXEEXT) src/font_unifont_data.c $(UNIFONT)
+$(UNIFONT_BIN): $(UNIFONT) genunifont$(EXEEXT)
+	$(AM_V_GEN)./genunifont$(EXEEXT) $(UNIFONT_BIN) $(UNIFONT)
 
 #
 # Kmscon Modules
@@ -405,13 +406,13 @@ mod_unifont_la_SOURCES = \
 	src/githead.h \
 	src/font_unifont.c \
 	src/kmscon_mod_unifont.c
-nodist_mod_unifont_la_SOURCES = \
-	src/font_unifont_data.c
+EXTRA_mod_unifont_la_DEPENDENCIES = $(UNIFONT_BIN)
 mod_unifont_la_LIBADD = libshl.la
 mod_unifont_la_LDFLAGS = \
 	$(AM_LDFLAGS) \
 	-module \
-	-avoid-version
+	-avoid-version \
+	-Wl,--format=binary -Wl,$(UNIFONT_BIN) -Wl,--format=default
 
 if BUILD_ENABLE_FONT_FREETYPE2
 module_LTLIBRARIES += mod-freetype2.la
diff --git a/src/font_unifont.c b/src/font_unifont.c
index 0dbb1aa..b0ab693 100644
--- a/src/font_unifont.c
+++ b/src/font_unifont.c
@@ -28,37 +28,199 @@
  * SECTION:font_unifont.c
  * @short_description: Fixed unifont font
  * @include: font.h
- * 
+ *
  * This is a fixed font renderer backend that supports just one font which is
- * statically compiled into the file. This bitmap font has 8x16 and 16x16 
+ * statically compiled into the file. This bitmap font has 8x16 and 16x16
  * glyphs. This can statically compile in any font defined as a unifont style
- * hex format. This font is from the GNU unifont project available at: 
- * http://unifoundry.com/unifont.html
+ * hex format. This font is from the GNU unifont project available at:
+ *   http://unifoundry.com/unifont.html
  *
  * This file is heavily based on font_8x16.c
- * 
  */
 
 #include <errno.h>
+#include <pthread.h>
 #include <stdlib.h>
 #include <string.h>
 #include "font.h"
 #include "log.h"
+#include "shl_hashtable.h"
 #include "uterm_video.h"
 
 #define LOG_SUBSYSTEM "font_unifont"
 
-/* array is generated and compiled externally */
-extern const struct kmscon_glyph kmscon_font_unifont_data_hex_glyphs[];
-extern size_t kmscon_font_unifont_data_hex_len;
+/*
+ * Glyph data is linked to the binary externally as binary data. The data layout
+ * is a size-byte followed by 32 data bytes. The data bytes are padded with 0 if
+ * the size is smaller than 32.
+ * Sizes bigger than 32 are not used.
+ */
+
+struct unifont_data {
+	uint8_t len;
+	uint8_t data[32];
+} __attribute__((__packed__));
+
+extern const struct unifont_data _binary_src_font_unifont_data_bin_start[];
+extern const struct unifont_data _binary_src_font_unifont_data_bin_end[];
+
+/*
+ * Global glyph cache
+ * The linked binary glyph data cannot be directly passed to the caller as it
+ * has the wrong format. Hence, use a glyph-cache with all used glyphs and add
+ * new ones as soon as they are used.
+ */
+
+static pthread_mutex_t cache_mutex = PTHREAD_MUTEX_INITIALIZER;
+static struct shl_hashtable *cache;
+static unsigned long cache_refnum;
+
+static void cache_ref(void)
+{
+	pthread_mutex_lock(&cache_mutex);
+	++cache_refnum;
+	pthread_mutex_unlock(&cache_mutex);
+}
+
+static void cache_unref(void)
+{
+	pthread_mutex_lock(&cache_mutex);
+	if (!--cache_refnum) {
+		shl_hashtable_free(cache);
+		cache = NULL;
+	}
+	pthread_mutex_unlock(&cache_mutex);
+}
+
+static void free_glyph(void *data)
+{
+	struct kmscon_glyph *g = data;
+
+	free(g->buf.data);
+	free(g);
+}
+
+static void unfold(uint8_t *dst, uint8_t val)
+{
+	*dst = 0xff * !!val;
+}
+
+static int find_glyph(uint32_t id, const struct kmscon_glyph **out)
+{
+	struct kmscon_glyph *g;
+	int ret;
+	bool res;
+	const struct unifont_data *start, *end, *d;
+	unsigned int i, w;
+
+	pthread_mutex_lock(&cache_mutex);
+
+	if (!cache) {
+		ret = shl_hashtable_new(&cache, shl_direct_hash,
+					shl_direct_equal, NULL, free_glyph);
+		if (ret) {
+			log_error("cannot create unifont hashtable: %d", ret);
+			goto out_unlock;
+		}
+	} else {
+		res = shl_hashtable_find(cache, (void**)out,
+					 (void*)(long)id);
+		if (res) {
+			ret = 0;
+			goto out_unlock;
+		}
+	}
+
+	if (id > 0xffff) {
+		ret = -ERANGE;
+		goto out_unlock;
+	}
+
+	start = _binary_src_font_unifont_data_bin_start;
+	end = _binary_src_font_unifont_data_bin_end;
+	d = &start[id];
+
+	if (d >= end) {
+		ret = -ERANGE;
+		goto out_unlock;
+	}
+
+	switch (d->len) {
+	case 16:
+		w = 1;
+		break;
+	case 32:
+		w = 2;
+		break;
+	default:
+		ret = -EFAULT;
+		goto out_unlock;
+	}
+
+	g = malloc(sizeof(*g));
+	if (!g) {
+		ret = -ENOMEM;
+		goto out_unlock;
+	}
+	memset(g, 0, sizeof(*g));
+	g->width = w;
+	g->buf.width = w * 8;
+	g->buf.height = 16;
+	g->buf.stride = w * 8;
+	g->buf.format = UTERM_FORMAT_GREY;
+
+	g->buf.data = malloc(g->buf.stride * g->buf.height);
+	if (!g->buf.data) {
+		ret = -ENOMEM;
+		goto err_free;
+	}
+
+	for (i = 0; i < d->len; ++i) {
+		unfold(&g->buf.data[i * 8 + 0], d->data[i] & 0x80);
+		unfold(&g->buf.data[i * 8 + 1], d->data[i] & 0x40);
+		unfold(&g->buf.data[i * 8 + 2], d->data[i] & 0x20);
+		unfold(&g->buf.data[i * 8 + 3], d->data[i] & 0x10);
+		unfold(&g->buf.data[i * 8 + 4], d->data[i] & 0x08);
+		unfold(&g->buf.data[i * 8 + 5], d->data[i] & 0x04);
+		unfold(&g->buf.data[i * 8 + 6], d->data[i] & 0x02);
+		unfold(&g->buf.data[i * 8 + 7], d->data[i] & 0x01);
+	}
+
+	ret = shl_hashtable_insert(cache, (void*)(long)id, g);
+	if (ret) {
+		log_error("cannot insert glyph into glyph-cache: %d", ret);
+		goto err_data;
+	}
+
+	*out = g;
+	ret = 0;
+	goto out_unlock;
+
+err_data:
+	free(g->buf.data);
+err_free:
+	free(g);
+out_unlock:
+	pthread_mutex_unlock(&cache_mutex);
+	return ret;
+}
 
 static int kmscon_font_unifont_init(struct kmscon_font *out,
 				    const struct kmscon_font_attr *attr)
 {
 	static const char name[] = "static-unifont";
+	const struct unifont_data *start, *end;
 
 	log_debug("loading static unifont font");
 
+	start = _binary_src_font_unifont_data_bin_start;
+	end = _binary_src_font_unifont_data_bin_end;
+	if (start == end) {
+		log_error("unifont glyph information not found in binary");
+		return -EFAULT;
+	}
+
+
 	memset(&out->attr, 0, sizeof(out->attr));
 	memcpy(out->attr.name, name, sizeof(name));
 	out->attr.bold = false;
@@ -68,47 +230,36 @@ static int kmscon_font_unifont_init(struct kmscon_font *out,
 	kmscon_font_attr_normalize(&out->attr);
 	out->baseline = 4;
 
+	cache_ref();
 	return 0;
 }
 
 static void kmscon_font_unifont_destroy(struct kmscon_font *font)
 {
 	log_debug("unloading static unifont font");
+	cache_unref();
 }
 
 static int kmscon_font_unifont_render(struct kmscon_font *font, uint32_t id,
 				      const uint32_t *ch, size_t len,
 				      const struct kmscon_glyph **out)
 {
-	if (len > 1 || *ch >= kmscon_font_unifont_data_hex_len)
+	if (len > 1)
 		return -ERANGE;
 
-	*out = &kmscon_font_unifont_data_hex_glyphs[*ch];
-	return 0;
+	return find_glyph(id, out);
 }
 
 static int kmscon_font_unifont_render_inval(struct kmscon_font *font,
 					    const struct kmscon_glyph **out)
 {
-	if (0xfffd < kmscon_font_unifont_data_hex_len)
-		*out = &kmscon_font_unifont_data_hex_glyphs[0xfffd];
-	else if ('?' < kmscon_font_unifont_data_hex_len)
-		*out = &kmscon_font_unifont_data_hex_glyphs['?'];
-	else
-		*out = &kmscon_font_unifont_data_hex_glyphs[0];
-
-	return 0;
+	return find_glyph(0xfffd, out);
 }
 
 static int kmscon_font_unifont_render_empty(struct kmscon_font *font,
 					    const struct kmscon_glyph **out)
 {
-	if (' ' < kmscon_font_unifont_data_hex_len) {
-		*out = &kmscon_font_unifont_data_hex_glyphs[' '];
-		return 0;
-	} else {
-		return kmscon_font_unifont_render_inval(font, out);
-	}
+	return find_glyph(' ', out);
 }
 
 struct kmscon_font_ops kmscon_font_unifont_ops = {
diff --git a/src/genunifont.c b/src/genunifont.c
index b3c5121..caedf4a 100644
--- a/src/genunifont.c
+++ b/src/genunifont.c
@@ -2,7 +2,7 @@
  * kmscon - Generate Unifont data files
  *
  * Copyright (c) 2012 Ted Kotz <ted@kotz.us>
- * Copyright (c) 2012 David Herrmann <dh.herrmann@googlemail.com>
+ * Copyright (c) 2012-2013 David Herrmann <dh.herrmann@googlemail.com>
  *
  * Permission is hereby granted, free of charge, to any person obtaining
  * a copy of this software and associated documentation files
@@ -58,77 +58,35 @@ static uint8_t hex_val(char c)
 	return 0;
 }
 
-static void print_data_row(FILE *out, char c)
-{
-	static const char *line_map[16] = {
-		"0x00, 0x00, 0x00, 0x00,",
-		"0x00, 0x00, 0x00, 0xff,",
-		"0x00, 0x00, 0xff, 0x00,",
-		"0x00, 0x00, 0xff, 0xff,",
-		"0x00, 0xff, 0x00, 0x00,",
-		"0x00, 0xff, 0x00, 0xff,",
-		"0x00, 0xff, 0xff, 0x00,",
-		"0x00, 0xff, 0xff, 0xff,",
-		"0xff, 0x00, 0x00, 0x00,",
-		"0xff, 0x00, 0x00, 0xff,",
-		"0xff, 0x00, 0xff, 0x00,",
-		"0xff, 0x00, 0xff, 0xff,",
-		"0xff, 0xff, 0x00, 0x00,",
-		"0xff, 0xff, 0x00, 0xff,",
-		"0xff, 0xff, 0xff, 0x00,",
-		"0xff, 0xff, 0xff, 0xff,",
-	};
-	uint8_t idx;
-
-	idx = hex_val(c);
-	if (idx < 16) {
-		fputs(line_map[idx], out);
-	} else {
-		fprintf(stderr, "genunifont: invalid value %c\n", c);
-		fputs(line_map[0], out);
-	}
-}
-
 static void print_unifont_glyph(FILE *out, const struct unifont_glyph *g)
 {
-	int width;
 	size_t i;
+	uint8_t val;
 
 	switch (g->len) {
-	case 64:
-		width = 4;
-		break;
 	case 32:
-		width = 2;
+	case 64:
 		break;
 	default:
-		fprintf(stderr, "genunifont: invalid data size");
+		fprintf(stderr, "genunifont: invalid data size %d for %x",
+			g->len, g->codepoint);
 		return;
 	}
 
-	fprintf(out, "\t{ /* %d 0x%x */\n"
-		     "\t\t.width = %d,\n"
-		     "\t\t.buf = {\n"
-		     "\t\t\t.width = %d,\n"
-		     "\t\t\t.height = 16,\n"
-		     "\t\t\t.stride = %d,\n"
-		     "\t\t\t.format = UTERM_FORMAT_GREY,\n"
-		     "\t\t\t.data = (uint8_t[]){\n",
-		     g->codepoint,  g->codepoint, 1,
-		     width * 4, width * 4);
-
-	for (i = 0; i < g->len; ++i) {
-		fprintf(out, "\t\t\t\t");
-		print_data_row(out, g->data[i]);
-		fprintf(out, "\n");
+	fprintf(out, "%c", g->len / 2);
+	for (i = 0; i < g->len; i += 2) {
+		val = hex_val(g->data[i]) << 4;
+		val |= hex_val(g->data[i + 1]);
+		fprintf(out, "%c", val);
 	}
-
-	fprintf(out, "\t\t\t},\n\t\t},\n\t},\n");
+	for ( ; i < 64; i += 2)
+		fprintf(out, "%c", 0);
 }
 
 static int build_unifont_glyph(struct unifont_glyph *g, const char *buf)
 {
 	int val;
+	const char *orig = buf;
 
 	val = 0;
 	while (*buf && *buf != ':') {
@@ -137,7 +95,7 @@ static int build_unifont_glyph(struct unifont_glyph *g, const char *buf)
 	}
 
 	if (*buf++ != ':') {
-		fprintf(stderr, "genunifont: invalid file format\n");
+		fprintf(stderr, "genunifont: invalid file format: %s\n", orig);
 		return -EFAULT;
 	}
 
@@ -151,36 +109,15 @@ static int build_unifont_glyph(struct unifont_glyph *g, const char *buf)
 	return 0;
 }
 
-static void write_name(FILE *out, const char *name)
+static int parse_single_file(FILE *out, FILE *in)
 {
-	size_t i, len;
-
-	len = strlen(name);
-	for (i = 0; i < len; ++i) {
-		if ((name[i] >= 'A' && name[i] <= 'Z') ||
-		    (name[i] >= 'a' && name[i] <= 'z') ||
-		    (name[i] >= '0' && name[i] <= '9'))
-			fwrite(&name[i], 1, 1, out);
-		else
-			fwrite("_", 1, 1, out);
-	}
-}
-
-static int parse_single_file(FILE *out, FILE *in, const char *varname)
-{
-	struct unifont_glyph replacement = {
+	static const struct unifont_glyph replacement = {
 		.codepoint = 0,
 		.len = 32,
 		.data = "0000007E665A5A7A76767E76767E0000"
 	};
-	static const char c0[] = "const struct kmscon_glyph kmscon_";
-	static const char c1[] = "_glyphs[] = {\n";
-	static const char c2[] = "};\n\nconst size_t kmscon_";
-	static const char c3[] = "_len =\n\tsizeof(kmscon_";
-	static const char c4[] = "_glyphs) /\n\tsizeof(*kmscon_";
-	static const char c5[] = "_glyphs);\n";
 	char buf[MAX_DATA_SIZE];
-	struct unifont_glyph *g, *iter, *list, *last;
+	struct unifont_glyph *g, **iter, *list, *last;
 	int ret, num;
 	unsigned long status_max, status_cur;
 	unsigned long perc_prev, perc_now;
@@ -211,16 +148,20 @@ static int parse_single_file(FILE *out, FILE *in, const char *varname)
 	fprintf(stderr, "Finished: %3ld%%", perc_now);
 
 	while (fgets(buf, sizeof(buf) - 1, in) != NULL) {
+		/* print status update in percent */
 		perc_now = status_cur * 100 / status_max;
 		if (perc_now > perc_prev) {
 			perc_prev = perc_now;
 			fprintf(stderr, "\b\b\b\b%3ld%%", perc_now);
+			fflush(stderr);
 		}
 		status_cur += strlen(buf);
 
+		/* ignore comments */
 		if (buf[0] == '#')
 			continue;
 
+		/* allocate new glyph */
 		g = malloc(sizeof(*g));
 		if (!g) {
 			fprintf(stderr, "genunifont: out of memory\n");
@@ -228,102 +169,63 @@ static int parse_single_file(FILE *out, FILE *in, const char *varname)
 		}
 		memset(g, 0, sizeof(*g));
 
+		/* read glyph data */
 		ret = build_unifont_glyph(g, buf);
 		if (ret) {
 			free(g);
-			continue;
+			return ret;
 		}
 
-		if (!list || list->codepoint > g->codepoint) {
-			g->next = list;
-			list = g;
-			if (!last)
-				last = g;
-		} else if (list->codepoint == g->codepoint) {
-			fprintf(stderr, "glyph %d used twice\n",
-				g->codepoint);
-			free(g);
+		/* find glyph position */
+		if (last && last->codepoint < g->codepoint) {
+			iter = &last->next;
 		} else {
-			if (last->codepoint < g->codepoint) {
-				iter = last;
-			} else {
-				iter = list;
-				while (iter->next) {
-					if (iter->next->codepoint >= g->codepoint)
-						break;
-					iter = iter->next;
-				}
-			}
-
-			if (iter->next) {
-				if (iter->next->codepoint == g->codepoint) {
-					fprintf(stderr, "glyph %d used twice\n",
-						g->codepoint);
-					free(g);
-				} else {
-					g->next = iter->next;
-					iter->next = g;
-				}
-			} else {
-				iter->next = g;
-				last = g;
+			iter = &list;
+			while (*iter && (*iter)->codepoint < g->codepoint)
+				iter = &(*iter)->next;
+
+			if (*iter && (*iter)->codepoint == g->codepoint) {
+				fprintf(stderr, "glyph %d used twice\n",
+					g->codepoint);
+				free(g);
+				return -EFAULT;
 			}
 		}
-	}
 
-	fprintf(stderr, "\n");
+		/* insert glyph into single-linked list */
+		g->next = *iter;
+		if (!*iter)
+			last = g;
+		*iter = g;
+	}
 
-	fwrite(c0, sizeof(c0) - 1, 1, out);
-	write_name(out, varname);
-	fwrite(c1, sizeof(c1) - 1, 1, out);
+	fprintf(stderr, "\b\b\b\b%3d%%\n", 100);
 
+	/* print all glyph-data to output file */
 	num = 0;
 	while (list) {
-		iter = list;
-		list = iter->next;
+		g = list;
+		list = g->next;
 
-		while (num++ < iter->codepoint)
+		/* print replacements if glyphs are missing */
+		while (num++ < g->codepoint)
 			print_unifont_glyph(out, &replacement);
 
-		print_unifont_glyph(out, iter);
-		free(iter);
+		print_unifont_glyph(out, g);
+		free(g);
 	}
 
-	fwrite(c2, sizeof(c2) - 1, 1, out);
-	write_name(out, varname);
-	fwrite(c3, sizeof(c3) - 1, 1, out);
-	write_name(out, varname);
-	fwrite(c4, sizeof(c4) - 1, 1, out);
-	write_name(out, varname);
-	fwrite(c5, sizeof(c5) - 1, 1, out);
-
 	return 0;
 }
 
-static const char *get_basename(const char *path)
-{
-	const char *res;
-
-	res = strrchr(path, '/');
-	if (!res || !*++res)
-		return path;
-
-	return res;
-}
-
 int main(int argc, char **argv)
 {
 	FILE *out, *in;
-	size_t i;
-	static const char c0[] = "/* This file was generated "
-				 "by genunifont.c */\n\n"
-				 "#include <stdint.h>\n"
-				 "#include <stdlib.h>\n"
-				 "#include \"font.h\"\n\n";
-	int ret = EXIT_FAILURE;
-
-	if (argc < 2) {
-		fprintf(stderr, "genunifont: use ./genunifont <outputfile> [<inputfiles> ...]\n");
+	int ret;
+
+	if (argc < 3) {
+		fprintf(stderr, "genunifont: use ./genunifont <outputfile> <inputfiles>\n");
+		ret = EXIT_FAILURE;
 		goto err_out;
 	}
 
@@ -331,26 +233,28 @@ int main(int argc, char **argv)
 	if (!out) {
 		fprintf(stderr, "genunifont: cannot open output %s: %m\n",
 			argv[1]);
+		ret = EXIT_FAILURE;
 		goto err_out;
 	}
 
-	fwrite(c0, sizeof(c0) - 1, 1, out);
-	for (i = 2; i < argc; ++i) {
-		fprintf(stderr, "genunifont: parsing input %s\n", argv[i]);
-		in = fopen(argv[i], "rb");
-		if (!in) {
-			fprintf(stderr, "genunifont: cannot open %s: %m\n",
-				argv[i]);
-			continue;
-		}
-		ret = parse_single_file(out, in, get_basename(argv[i]));
-		if (ret)
+	fprintf(stderr, "genunifont: parsing input %s\n", argv[2]);
+	in = fopen(argv[2], "rb");
+	if (!in) {
+		fprintf(stderr, "genunifont: cannot open %s: %m\n",
+			argv[2]);
+		ret = EXIT_FAILURE;
+	} else {
+		ret = parse_single_file(out, in);
+		if (ret) {
 			fprintf(stderr, "genunifont: parsing input %s failed",
-				argv[i]);
+				argv[2]);
+			ret = EXIT_FAILURE;
+		} else {
+			ret = EXIT_SUCCESS;
+		}
 		fclose(in);
 	}
 
-	ret = EXIT_SUCCESS;
 
 	fclose(out);
 err_out: