From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/7975 Path: news.gmane.org!not-for-mail From: Rich Felker Newsgroups: gmane.linux.lib.musl.general Subject: [PATCH] strverscmp fix Date: Sun, 21 Jun 2015 00:30:18 -0400 Message-ID: <20150621043018.GB1173@brightrain.aerifal.cx> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="VMt1DrMGOVs3KQwf" X-Trace: ger.gmane.org 1434861040 11446 80.91.229.3 (21 Jun 2015 04:30:40 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 21 Jun 2015 04:30:40 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-7988-gllmg-musl=m.gmane.org@lists.openwall.com Sun Jun 21 06:30:40 2015 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1Z6Wtw-0003sQ-J0 for gllmg-musl@m.gmane.org; Sun, 21 Jun 2015 06:30:36 +0200 Original-Received: (qmail 26237 invoked by uid 550); 21 Jun 2015 04:30:34 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 26194 invoked from network); 21 Jun 2015 04:30:30 -0000 Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) Original-Sender: Rich Felker Xref: news.gmane.org gmane.linux.lib.musl.general:7975 Archived-At: --VMt1DrMGOVs3KQwf Content-Type: text/plain; charset=us-ascii Content-Disposition: inline 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 --VMt1DrMGOVs3KQwf Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="strverscmp.diff" 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 #include +#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 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 --VMt1DrMGOVs3KQwf--