diff --git a/ebtree/ebimtree.h b/ebtree/ebimtree.h
index 4a98c96..28a9f14 100644
--- a/ebtree/ebimtree.h
+++ b/ebtree/ebimtree.h
@@ -62,7 +62,7 @@
 		if (eb_gettag(troot) == EB_LEAF) {
 			node = container_of(eb_untag(troot, EB_LEAF),
 					    struct ebpt_node, node.branches);
-			if (memcmp(node->key + pos, x, len) != 0)
+			if (eb_memcmp(node->key + pos, x, len) != 0)
 				goto ret_null;
 			else
 				goto ret_node;
@@ -76,7 +76,7 @@
 			 * value, and we walk down left, or it's a different
 			 * one and we don't have our key.
 			 */
-			if (memcmp(node->key + pos, x, len) != 0)
+			if (eb_memcmp(node->key + pos, x, len) != 0)
 				goto ret_null;
 			else
 				goto walk_left;
diff --git a/ebtree/ebmbtree.h b/ebtree/ebmbtree.h
index be9eaef..e7dfb0b 100644
--- a/ebtree/ebmbtree.h
+++ b/ebtree/ebmbtree.h
@@ -154,7 +154,7 @@
 		if (eb_gettag(troot) == EB_LEAF) {
 			node = container_of(eb_untag(troot, EB_LEAF),
 					    struct ebmb_node, node.branches);
-			if (memcmp(node->key + pos, x, len) != 0)
+			if (eb_memcmp(node->key + pos, x, len) != 0)
 				goto ret_null;
 			else
 				goto ret_node;
@@ -168,7 +168,7 @@
 			 * value, and we walk down left, or it's a different
 			 * one and we don't have our key.
 			 */
-			if (memcmp(node->key + pos, x, len) != 0)
+			if (eb_memcmp(node->key + pos, x, len) != 0)
 				goto ret_null;
 			else
 				goto walk_left;
diff --git a/ebtree/ebtree.c b/ebtree/ebtree.c
index fb266ec..e82ed59 100644
--- a/ebtree/ebtree.c
+++ b/ebtree/ebtree.c
@@ -30,3 +30,21 @@
 {
 	return __eb_insert_dup(sub, new);
 }
+
+/* compares memory blocks m1 and m2 for up to <len> bytes. Immediately stops at
+ * the first non-matching byte. It returns 0 on full match, non-zero otherwise.
+ * One byte will always be checked so this must not be called with len==0. It
+ * takes 2+5cy/B on x86_64 and is ~29 bytes long.
+ */
+int eb_memcmp(const void *m1, const void *m2, size_t len)
+{
+	const char *p1 = (const char *)m1 + len;
+	const char *p2 = (const char *)m2 + len;
+	ssize_t ofs = -len;
+	char diff;
+
+	do {
+		diff = p1[ofs] - p2[ofs];
+	} while (!diff && ++ofs);
+	return diff;
+}
diff --git a/ebtree/ebtree.h b/ebtree/ebtree.h
index 1b15dab..cfb7851 100644
--- a/ebtree/ebtree.h
+++ b/ebtree/ebtree.h
@@ -908,6 +908,7 @@
 /* These functions are declared in ebtree.c */
 void eb_delete(struct eb_node *node);
 REGPRM1 struct eb_node *eb_insert_dup(struct eb_node *sub, struct eb_node *new);
+int eb_memcmp(const void *m1, const void *m2, size_t len);
 
 #endif /* _EB_TREE_H */