util.strbitop: Add common_prefix_bits() method

This returns the number of bits that two strings have in common. It is
significantly more efficient than similar calculations in Lua.

1 files changed, 37 insertions, 0 deletions

diff --git a/util-src/strbitop.c b/util-src/strbitop.c
index 75cfea81..2f6bf6e6 100644
--- a/util-src/strbitop.c
+++ b/util-src/strbitop.c
@@ -8,6 +8,8 @@
 #include <lua.h>
 #include <lauxlib.h>
 
+#include <sys/param.h>
+#include <limits.h>
 
 /* TODO Deduplicate code somehow */
 
@@ -74,11 +76,46 @@ static int strop_xor(lua_State *L) {
 	return 1;
 }
 
+unsigned int clz(unsigned char c) {
+#if __GNUC__
+	return __builtin_clz((unsigned int) c) - ((sizeof(int)-1)*CHAR_BIT);
+#else
+	if(c & 0x80) return 0;
+	if(c & 0x40) return 1;
+	if(c & 0x20) return 2;
+	if(c & 0x10) return 3;
+	if(c & 0x08) return 4;
+	if(c & 0x04) return 5;
+	if(c & 0x02) return 6;
+	if(c & 0x01) return 7;
+	return 8;
+#endif
+}
+
+LUA_API int strop_common_prefix_bits(lua_State *L) {
+	size_t a, b, i;
+	const char *str_a = luaL_checklstring(L, 1, &a);
+	const char *str_b = luaL_checklstring(L, 2, &b);
+
+	size_t min_len = MIN(a, b);
+
+	for(i=0; i<min_len; i++) {
+		if(str_a[i] != str_b[i]) {
+			lua_pushinteger(L, i*8 + (clz(str_a[i] ^ str_b[i])));
+			return 1;
+		}
+	}
+
+	lua_pushinteger(L, i*8);
+	return 1;
+}
+
 LUA_API int luaopen_prosody_util_strbitop(lua_State *L) {
 	luaL_Reg exports[] = {
 		{ "sand", strop_and },
 		{ "sor",  strop_or },
 		{ "sxor", strop_xor },
+		{ "common_prefix_bits", strop_common_prefix_bits },
 		{ NULL, NULL }
 	};