[PATCH] strverscmp fix

[PATCH] strverscmp fix

[Rich Felker]

[-- Attachment #1: Type: text/plain, Size: 472 bytes --]

Fixing strverscmp behavior to match glibc has been an open item for a
while. There's a patch (or rather replacement) from Sergey Dmitrouk
that's been pending review serious for a few months now, and while it
reportedly works, I found myself writing my own version in the process
of reviewing and trying to understand all the cases. The attached is
what I ended up with, and I believe it's correct and about 20%
smaller. I couldn't find any further ways to simplify.

Rich

[-- Attachment #2: strverscmp.diff --]
[-- Type: text/plain, Size: 2018 bytes --]

diff --git a/src/string/strverscmp.c b/src/string/strverscmp.c
index 6f37cc6..9c7fa33 100644
--- a/src/string/strverscmp.c
+++ b/src/string/strverscmp.c
@@ -2,6 +2,55 @@
 #include <ctype.h>
 #include <string.h>
 
+#if 1
+int strverscmp(const char *l0, const char *r0)
+{
+	const unsigned char *l = (const void *)l0;
+	const unsigned char *r = (const void *)r0;
+	size_t i, dp, j;
+	int z = 1;
+
+	/* Find maximual matching prefix and track its maximal digit
+	 * suffix and whether those digits are all zeros. */
+	for (dp=i=0; l[i]==r[i]; i++) {
+		int c = l[i];
+		if (!c) return 0;
+		if (!isdigit(c)) dp=i+1, z=1;
+		else if (c!='0') z=0;
+	}
+
+	/* This catches all cases where the mismatch is non-numeric --
+	 * either a matching digit sequence has just been completed and
+	 * is followed by non-digits in both strings, or at most one
+	 * of the two strings has an initial digit in the first
+	 * mismatched position and the other has a non-digit. */
+	if (!isdigit(l[i]) && !isdigit(r[i]) ||
+	    i==dp && (!isdigit(l[i]) || !isdigit(r[i])))
+		return l[i] - r[i];
+
+	/* If this point is reached, the comparison is numeric. */
+
+	/* The only way one of the conditions can hold without the other
+	 * is when dp==i, i.e. the mismatch is the start of a new 
+	 * digit sequence in both strings. */
+	if (l[dp]=='0' || r[dp]=='0') {
+		/* If the shared prefix is all zeros, 0<d<x; otherwise,
+		 * x<0<d, where d is any nonzero digit, x any non-digit.
+		 * Arrange for unsigned range check. */
+		unsigned adj = '0' + (z?0:10);
+		return l[i]-adj > r[i]-adj ? 1 : -1;
+	}
+
+	/* In the only remaining cases, neither number has leading zeros.
+	 * The longer is greater, with first mismatch breaking ties. */
+
+	for (j=i; isdigit(l[j]); j++)
+		if (!isdigit(r[j])) return 1;
+	if (isdigit(r[j])) return -1;
+
+	return l[i] - r[i];
+}
+#else
 int strverscmp(const char *l, const char *r)
 {
 	int haszero=1;
@@ -39,3 +88,4 @@ int strverscmp(const char *l, const char *r)
 		return (*l -  *r);
 	}
 }
+#endif

Re: [PATCH] strverscmp fix

[Rich Felker]

On Sun, Jun 21, 2015 at 12:30:18AM -0400, Rich Felker wrote:
> Fixing strverscmp behavior to match glibc has been an open item for a
> while. There's a patch (or rather replacement) from Sergey Dmitrouk
> that's been pending review serious for a few months now, and while it
> reportedly works, I found myself writing my own version in the process
> of reviewing and trying to understand all the cases. The attached is
> what I ended up with, and I believe it's correct and about 20%
> smaller. I couldn't find any further ways to simplify.

This was much more complex than it needed to be; I'm committing a new
version that barely affects the compiled code size now.

Rich