implement mo file string lookup for translations

the core is based on a binary search; hash table is not used. both
native and reverse-endian mo files are supported. all offsets read
from the mapped mo file are checked against the mapping size to
prevent the possibility of reads outside the mapping.

this commit has no observable effects since there are not yet any
callers to the message translation code.

1 files changed, 38 insertions, 0 deletions

diff --git a/src/locale/__mo_lookup.c b/src/locale/__mo_lookup.c
new file mode 100644
index 00000000..8112d91c
--- /dev/null
+++ b/src/locale/__mo_lookup.c
@@ -0,0 +1,38 @@
+#include <stdint.h>
+#include <string.h>
+
+static inline uint32_t swapc(uint32_t x, int c)
+{
+	return c ? x>>24 | x>>8&0xff00 | x<<8&0xff0000 | x<<24 : x;
+}
+
+const char *__mo_lookup(const void *p, size_t size, const char *s)
+{
+	const uint32_t *mo = p;
+	int sw = *mo - 0x950412de;
+	uint32_t b = 0, n = swapc(mo[2], sw);
+	uint32_t o = swapc(mo[3], sw);
+	uint32_t t = swapc(mo[4], sw);
+	if (n>=size/4 || o>=size-4*n || t>=size-4*n || ((o|t)%4))
+		return 0;
+	o/=4;
+	t/=4;
+	for (;;) {
+		uint32_t os = swapc(mo[o+2*(b+n/2)+1], sw);
+		if (os >= size) return 0;
+		int sign = strcmp(s, (char *)p + os);
+		if (!sign) {
+			uint32_t ts = swapc(mo[t+2*(b+n/2)+1], sw);
+			if (ts >= size) return 0;
+			return (char *)p + ts;
+		}
+		else if (n == 1) return 0;
+		else if (sign < 0)
+			n /= 2;
+		else {
+			b += n/2;
+			n -= n/2;
+		}
+	}
+	return 0;
+}