4 files changed, 80 insertions, 18 deletions

diff --git a/lib/ldb/common/attrib_handlers.c b/lib/ldb/common/attrib_handlers.c
index 15470cf..3d13e4b 100644
--- a/lib/ldb/common/attrib_handlers.c
+++ b/lib/ldb/common/attrib_handlers.c
@@ -281,15 +281,36 @@ static int ldb_canonicalise_Boolean(struct ldb_context *ldb, void *mem_ctx,
 }
 
 /*
-  compare two Booleans
-*/
+ * compare two Booleans.
+ *
+ * According to RFC4517 4.2.2, "the booleanMatch rule is an equality matching
+ * rule", meaning it isn't used for ordering.
+ *
+ * However, it seems conceivable that Samba could be coerced into sorting on a
+ * field with Boolean syntax, so we might as well have consistent behaviour in
+ * that case.
+ *
+ * The most probably values are {"FALSE", 5} and {"TRUE", 4}. To save time we
+ * compare first by length, which makes FALSE > TRUE. This is somewhat
+ * contrary to convention, but is how Samba has worked forever.
+ *
+ * If somehow we are comparing incompletely normalised values where the length
+ * is the same (for example {"false", 5} and {"TRUE\0", 5}), the length is the
+ * same, and we fall back to a strncasecmp. In this case, since "FALSE" is
+ * alphabetically lower, we swap the order, so that "TRUE\0" again comes
+ * before "FALSE".
+ *
+ * ldb_canonicalise_Boolean (just above) gives us a clue as to what we might
+ * expect to cope with by way of invalid values.
+ */
 static int ldb_comparison_Boolean(struct ldb_context *ldb, void *mem_ctx,
 			   const struct ldb_val *v1, const struct ldb_val *v2)
 {
 	if (v1->length != v2->length) {
-		return v1->length - v2->length;
+		return NUMERIC_CMP(v2->length, v1->length);
 	}
-	return strncasecmp((char *)v1->data, (char *)v2->data, v1->length);
+	/* reversed, see long comment above */
+	return strncasecmp((char *)v2->data, (char *)v1->data, v1->length);
 }
 
 
@@ -300,7 +321,7 @@ int ldb_comparison_binary(struct ldb_context *ldb, void *mem_ctx,
 			  const struct ldb_val *v1, const struct ldb_val *v2)
 {
 	if (v1->length != v2->length) {
-		return v1->length - v2->length;
+		return NUMERIC_CMP(v1->length, v2->length);
 	}
 	return memcmp(v1->data, v2->data, v1->length);
 }
@@ -372,17 +393,27 @@ utf8str:
 	b2 = ldb_casefold(ldb, mem_ctx, s2, n2);
 
 	if (!b1 || !b2) {
-		/* One of the strings was not UTF8, so we have no
-		 * options but to do a binary compare */
+		/*
+		 * One of the strings was not UTF8, so we have no
+		 * options but to do a binary compare.
+		 */
 		talloc_free(b1);
 		talloc_free(b2);
 		ret = memcmp(s1, s2, MIN(n1, n2));
 		if (ret == 0) {
-			if (n1 == n2) return 0;
+			if (n1 == n2) {
+				return 0;
+			}
 			if (n1 > n2) {
-				return (int)ldb_ascii_toupper(s1[n2]);
+				if (s1[n2] == '\0') {
+					return 0;
+				}
+				return 1;
 			} else {
-				return -(int)ldb_ascii_toupper(s2[n1]);
+				if (s2[n1] == '\0') {
+					return 0;
+				}
+				return -1;
 			}
 		}
 		return ret;
@@ -404,7 +435,7 @@ utf8str:
 		while (*u1 == ' ') u1++;
 		while (*u2 == ' ') u2++;
 	}
-	ret = (int)(*u1 - *u2);
+	ret = NUMERIC_CMP(*u1, *u2);
 
 	talloc_free(b1);
 	talloc_free(b2);
diff --git a/lib/ldb/common/ldb_dn.c b/lib/ldb/common/ldb_dn.c
index 601da57..8388fdb 100644
--- a/lib/ldb/common/ldb_dn.c
+++ b/lib/ldb/common/ldb_dn.c
@@ -1111,7 +1111,7 @@ int ldb_dn_compare_base(struct ldb_dn *base, struct ldb_dn *dn)
 
 		/* compare attr.cf_value. */
 		if (b_vlen != dn_vlen) {
-			return b_vlen - dn_vlen;
+			return NUMERIC_CMP(b_vlen, dn_vlen);
 		}
 		ret = strncmp(b_vdata, dn_vdata, b_vlen);
 		if (ret != 0) return ret;
@@ -1132,8 +1132,32 @@ int ldb_dn_compare(struct ldb_dn *dn0, struct ldb_dn *dn1)
 {
 	unsigned int i;
 	int ret;
+	/*
+	 * If used in sort, we shift NULL and invalid DNs to the end.
+	 *
+	 * If ldb_dn_casefold_internal() fails, that goes to the end too, so
+	 * we end up with:
+	 *
+	 * | normal DNs, sorted | casefold failed DNs | invalid DNs | NULLs |
+	 */
 
-	if (( ! dn0) || dn0->invalid || ! dn1 || dn1->invalid) {
+	if (dn0 == dn1) {
+		/* this includes the both-NULL case */
+		return 0;
+	}
+	if (dn0 == NULL) {
+		return 1;
+	}
+	if (dn1 == NULL) {
+		return -1;
+	}
+	if (dn0->invalid && dn1->invalid) {
+		return 0;
+	}
+	if (dn0->invalid) {
+		return 1;
+	}
+	if (dn1->invalid) {
 		return -1;
 	}
 
@@ -1190,7 +1214,7 @@ int ldb_dn_compare(struct ldb_dn *dn0, struct ldb_dn *dn1)
 
 		/* compare attr.cf_value. */
 		if (dn0_vlen != dn1_vlen) {
-			return dn0_vlen - dn1_vlen;
+			return NUMERIC_CMP(dn0_vlen, dn1_vlen);
 		}
 		ret = strncmp(dn0_vdata, dn1_vdata, dn0_vlen);
 		if (ret != 0) {
diff --git a/lib/ldb/common/ldb_msg.c b/lib/ldb/common/ldb_msg.c
index afddbe4..c334d70 100644
--- a/lib/ldb/common/ldb_msg.c
+++ b/lib/ldb/common/ldb_msg.c
@@ -93,7 +93,7 @@ struct ldb_val *ldb_msg_find_val(const struct ldb_message_element *el,
 static int ldb_val_cmp(const struct ldb_val *v1, const struct ldb_val *v2)
 {
 	if (v1->length != v2->length) {
-		return v1->length - v2->length;
+		return NUMERIC_CMP(v1->length, v2->length);
 	}
 	return memcmp(v1->data, v2->data, v1->length);
 }
@@ -749,9 +749,16 @@ int ldb_msg_element_compare(struct ldb_message_element *el1,
 	unsigned int i;
 
 	if (el1->num_values != el2->num_values) {
-		return el1->num_values - el2->num_values;
+		return NUMERIC_CMP(el1->num_values, el2->num_values);
 	}
-
+	/*
+	 * Note this is an inconsistent comparison, unsuitable for
+	 * sorting. If A has values {a, b} and B has values {b, c},
+	 * then
+	 *
+	 * ldb_msg_element_compare(A, B) returns -1, meaning A < B
+	 * ldb_msg_element_compare(B, A) returns -1, meaning B < A
+	 */
 	for (i=0;i<el1->num_values;i++) {
 		if (!ldb_msg_find_val(el2, &el1->values[i])) {
 			return -1;
diff --git a/lib/ldb/common/qsort.c b/lib/ldb/common/qsort.c
index 012aaf3..bae35e6 100644
--- a/lib/ldb/common/qsort.c
+++ b/lib/ldb/common/qsort.c
@@ -227,7 +227,7 @@ void ldb_qsort (void *const pbase, size_t total_elems, size_t size,
     while ((run_ptr += size) <= end_ptr)
       {
 	tmp_ptr = run_ptr - size;
-	while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, opaque) < 0)
+	while (tmp_ptr > base_ptr && (*cmp) ((void *) run_ptr, (void *) tmp_ptr, opaque) < 0)
 	  tmp_ptr -= size;
 
 	tmp_ptr += size;