[PATCH] Fix strverscmp

[PATCH] Fix strverscmp

[Isaac Dunham]

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

On the Puppy Linux forums, technosaurus mentioned that musl's strverscmp implementation was broken; he has a small version of strverscmp that works properly, which he placed under a CC0-like license.

This patch changes strverscmp to use his version.  Results are comparable to glibc.

-- 
Isaac Dunham <idunham@lavabit.com>

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

commit 21b9e883f440de900764a2e4077752268724c4db
Author: Isaac Dunham <idunham@lavabit.com>
Date:   Wed Dec 5 10:48:33 2012 -0800

    Fix strverscmp.
    
    The original version used strcmp, resulting in incorrect sorting order.
    This version, based on a version Brad Conroy (technosaurus) published,
    behaves similarly to the glibc version.

diff --git a/src/string/strverscmp.c b/src/string/strverscmp.c
index 7054967..bab3e64 100644
--- a/src/string/strverscmp.c
+++ b/src/string/strverscmp.c
@@ -1,7 +1,27 @@
+/*
+ * Based on an implementation by Brad Conroy (technosaurus) 
+ * published on the Puppy Linux forums.
+ *
+ * This work is released to the Public Domain.
+ * In locales that do not recognize public domain it is:
+ * Copyright Brad Conroy 2012, permission is hereby granted to use this work in
+ * accordance with any license approved by the Open Source Initiative for any 
+ * purpose without restriction in perpetuity.
+ */
 #include <string.h>
 
 int strverscmp(const char *l, const char *r)
 {
-	/* FIXME */
-	return strcmp(l, r);
+	int ret=0, buf=0;
+	while ( *l && *r && l[0]==r[0] ) {
+		l++;
+		r++;
+	}
+	do {
+		ret=(10 * ret) + l++[0] - '0'; 
+	} while ( '0' <= l[0] && l[0] <= '9') ;
+	do {
+		buf=(10 * buf) + r++[0] - '0'; 
+	} while ( '0' <= r[0] && r[0] <= '9');
+	return ret - buf;
 }

Re: [PATCH] Fix strverscmp

[Rich Felker]

On Wed, Dec 05, 2012 at 11:09:59AM -0800, Isaac Dunham wrote:
> On the Puppy Linux forums, technosaurus mentioned that musl's
> strverscmp implementation was broken; he has a small version of
> strverscmp that works properly, which he placed under a CC0-like
> license.
> 
> This patch changes strverscmp to use his version. Results are
> comparable to glibc.

I'm not opposed to adding this, but the code has some bugs, most
notably integer overflow. On filenames consisting of long digit
strings, it will invoke undefined behavior. If the results are
unpredictable, it might even cause qsort to invoke very bad undefined
behavior.

It would also, for example, cause these two names to compare equal:

- foobar-1.1.2
- foobar-1.01.3

just because the first component that differs textually compares equal
numerically.

It also shares the same issues (which we should arguably duplicate
anyway) with the original strverscmp, that names consisting of hex
values get sorted in a ridiculous and harmful way.

If we're to implement this function, some thought about getting it
correct is needed..

Rich

Re: Fix strverscmp

[Isaac Dunham]

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

On Wed, 5 Dec 2012 14:35:21 -0500
Rich Felker <dalias@aerifal.cx> wrote:

> I'm not opposed to adding this, but the code has some bugs, most
> notably integer overflow. On filenames consisting of long digit
> strings, it will invoke undefined behavior. If the results are
> unpredictable, it might even cause qsort to invoke very bad undefined
> behavior.
The  first I can see now (overflow -> l[-n]), 
but I'm not understanding the second.

> It would also, for example, cause these two names to compare equal:
> 
> - foobar-1.1.2
> - foobar-1.01.3
> 
> just because the first component that differs textually compares equal
> numerically.

This should not be equal, but not for the reason I'd expected: a leading 0 is supposed to be interpreted as "0.0".  Decimal points are not factored in...

> 
> It also shares the same issues (which we should arguably duplicate
> anyway) with the original strverscmp, that names consisting of hex
> values get sorted in a ridiculous and harmful way.

Per the specification, hex is unsupported. It would be possible to support it, but it may be rather expensive in terms of size...

The attached is an attempt to figure out how it should work (more notes than final implementation).
It seems to get the right sign consistently, which is all that the manpage indicates can be counted on.

-- 
Isaac Dunham <idunham@lavabit.com>

[-- Attachment #2: strvers.c --]
[-- Type: text/x-csrc, Size: 1803 bytes --]

#define _GNU_SOURCE
#define _XOPEN_SOURCE	700
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>


int str_vers_cmp(const char *l, const char *r){
	while ( *l && *r && l[0]==r[0] ){
		l++;
		r++;
	}

	/* strverscmp requires non-integer math */
	double ret =0, buf = 0;
	int pwrl=0, pwrr=0, scale=0;
	if ( !(isdigit(l[0]) && isdigit(r[0])) ) {
		return strcmp(l,r);
	}
	do {
		l--;
		r--; //This is also a number, see the start
	} while ( isdigit(l[0]) && isdigit(r[0]) ) ;

	while (l++[0] == '0') {
		pwrl--;
		scale--;
	}
	while (r++[0] == '0') {
		pwrr--;
		scale--;
	}

	if (!( pwrl == pwrr) ){
		return pwrl - pwrr;
	}

	do {
		ret += (l++[0] * 10^pwrl--) ;
	} while (isdigit(l[0] && (pwrl > INT_MAX * -1) ));
	
	do {
		buf += (r++[0] * 10^pwrr-- ) ;
	} while (isdigit(r[0] && (pwrr > INT_MAX * -1) ) );
	
//8 -> The number computed from the left  <= the right: l<r
//4 -> Left >= right: >
// 12: l == r
//2 -> len(l) <= len(r): <
//1 -> len(l) >= len(r): >
// 3: len(l) == len(r)
//    4 8  12
//  1 5 9  13
//  2 6 10 14
//  3 7 11 15
//
	switch ( 8*(ret > buf) + 4*(ret < buf) + 
		2*(pwrl < pwrr) + (pwrl > pwrr) ) {
	case 14: 		// l==r, len(l)<len(r)
				// 12 < 120
	case 11:		// l < r, len l==r
				// 012 < 120, 7 < 8
	case 10:	 	// l < r, len l < r
				// 1 < 90
	case 9: return -1;	// l < r, len l > r
		break;		// 012 < 12
	case 5:			// l > r, len l > r
				// 024 02
	case 7: 		// l > r, len l==r
				// 8 > 7, 08 07
	case 13: return 1; 	// l==r, len l > r
		break;		// 120 12
	case 6: 		// l > r, len l < r
				// 12 111, 012 0111: indeterminate
		return -2*(scale < 0) + 1 ;
		break;
	case 15: return 0;	//It's all the same
		 break;
	}
} 

int main(int argc, char **argv){
	printf("%d\n%d\n",str_vers_cmp(argv[1], argv[2]), strverscmp(argv[1], argv[2]));
}

Re: Fix strverscmp

[Rich Felker]

On Wed, Dec 05, 2012 at 04:43:29PM -0800, Isaac Dunham wrote:
> On Wed, 5 Dec 2012 14:35:21 -0500
> Rich Felker <dalias@aerifal.cx> wrote:
> 
> > I'm not opposed to adding this, but the code has some bugs, most
> > notably integer overflow. On filenames consisting of long digit
> > strings, it will invoke undefined behavior. If the results are
> > unpredictable, it might even cause qsort to invoke very bad undefined
> > behavior.
> The  first I can see now (overflow -> l[-n]), 
> but I'm not understanding the second.
> 
> > It would also, for example, cause these two names to compare equal:
> > 
> > - foobar-1.1.2
> > - foobar-1.01.3
> > 
> > just because the first component that differs textually compares equal
> > numerically.
> 
> This should not be equal, but not for the reason I'd expected: a
> leading 0 is supposed to be interpreted as "0.0". Decimal points are
> not factored in...

My understanding of the code is that, after it hits the first place
where the strings differ, it switches to reading a digit string as a
decimal number, and the result is the difference of those decimal
numbers. I just used the decimal point as an example because it
terminates the loop.

I also don't understand what you mean about leading zero. If leading
zeros are not considered equal to the number without leading zeros,
then a simple algorithm would be to, on the first mismatching byte,
remember the difference, then count the number of consecutive digits
starting at that position in both strings. If this count is the same
(possibly zero) for both strings, return the saved byte difference. If
the count is different, consider the string with fewer digits to be
less than the one with more digits. This is trivial to implement with
no arithmetic, but I'm not sure it matches the original semantics.






> 
> > 
> > It also shares the same issues (which we should arguably duplicate
> > anyway) with the original strverscmp, that names consisting of hex
> > values get sorted in a ridiculous and harmful way.
> 
> Per the specification, hex is unsupported. It would be possible to
> support it, but it may be rather expensive in terms of size...

I don't think we really want to "support" hex versions. My frustration
with the strverscmp interface is that it butchers the ordering of
directories containing hex filenames, and Thunar (xfce file manager)
insists on using it with no option to turn it off.

My thought for a possible solution to the problem would be only
interpreting decimal numbers where the number is delimited by
non-alphanumeric characters, and otherwise doing pure byte comparison
on digits. This would avoid lots of spurious misorderings. But I would
like to hear some opinions on whether it's harmful to differ from
glibc's behavior here...

> The attached is an attempt to figure out how it should work (more
> notes than final implementation).

I'll take a look.

> It seems to get the right sign consistently, which is all that the
> manpage indicates can be counted on.

Yes, only the sign matters.

Rich

Re: Fix strverscmp

[Rich Felker]

On Wed, Dec 05, 2012 at 08:00:00PM -0500, Rich Felker wrote:
> > This should not be equal, but not for the reason I'd expected: a
> > leading 0 is supposed to be interpreted as "0.0". Decimal points are
> > not factored in...
> 
> My understanding of the code is that, after it hits the first place
> where the strings differ, it switches to reading a digit string as a
> decimal number, and the result is the difference of those decimal
> numbers. I just used the decimal point as an example because it
> terminates the loop.
> 
> I also don't understand what you mean about leading zero. If leading
> zeros are not considered equal to the number without leading zeros,
> then a simple algorithm would be to, on the first mismatching byte,
> remember the difference, then count the number of consecutive digits
> starting at that position in both strings. If this count is the same
> (possibly zero) for both strings, return the saved byte difference. If
> the count is different, consider the string with fewer digits to be
> less than the one with more digits. This is trivial to implement with
> no arithmetic, but I'm not sure it matches the original semantics.

OK, I read the "spec" in the man page, and this seems to be the
simplest implementation:

1. Find the first mismatching bytes. During this search, keep 1 bit of
   state that's set when a '0' byte is encountered now following a
   digit, and cleared when any non-digit byte is encountered.

2. Upon finding the first mismatching bytes, if either is a non-digit
   or '0' or if above-described flag is set, return the difference of
   the mismatching bytes.

3. Otherwise, count the number of consecutive digits beginning with
   the first mismatching bytes. If the count differs for the two
   strings, the string with the lower count compares less. Otherwise,
   return the difference of the first mismatching bytes.

The rules in step 2 cover both the leading-zeros rule and non-numeric
cases. The rules in step 3 cover the simple numeric comparison rule
that the longer number is greater, with ties broken by comparing the
most-significant position that differs.

Does this sound correct to you? I like the concept of the flag in the
first phase, which we could easily extend to treat other cases as
non-numeric if desired.

Rich

Re: Fix strverscmp

[Isaac Dunham]

On Wed, 5 Dec 2012 20:00:00 -0500
Rich Felker <dalias@aerifal.cx> wrote:

> > This should not be equal, but not for the reason I'd expected: a
> > leading 0 is supposed to be interpreted as "0.0". Decimal points are
> > not factored in...
> 
> My understanding of the code is that, after it hits the first place
> where the strings differ, it switches to reading a digit string as a
> decimal number, and the result is the difference of those decimal
> numbers. I just used the decimal point as an example because it
> terminates the loop.
More-or-less, except that if the character is a number, it is expected to backtrack to the start of the longest substring which is purely numeric (the specification is rather insane, I think)

> I also don't understand what you mean about leading zero. If leading
> zeros are not considered equal to the number without leading zeros,
They are explicitly stated to be different in the man page:
"
What  this  function does is the following.  If both strings are equal,
return 0.  Otherwise find the position between two bytes with the prop-
erty  that  before  it  both strings are equal, while directly after it
there is a difference.  Find the largest consecutive digit strings con-
taining  (or  starting at, or ending at) this position.  If one or both
of these is empty, then  return  what  strcmp(3)  would  have  returned
(numerical  ordering  of  byte  values).  Otherwise, compare both digit
strings numerically, where digit strings with one or more leading zeros
are  interpreted  as  if they have a decimal point in front (so that in
particular digit strings with more  leading  zeros  come  before  digit
strings  with fewer leading zeros).  Thus, the ordering is 000, 00, 01,
010, 09, 0, 1, 9, 10.
"
> then a simple algorithm would be to, on the first mismatching byte,
> remember the difference, then count the number of consecutive digits
> starting at that position in both strings. If this count is the same
> (possibly zero) for both strings, return the saved byte difference. If
> the count is different, consider the string with fewer digits to be
> less than the one with more digits. This is trivial to implement with
> no arithmetic, but I'm not sure it matches the original semantics.
Hmm...
I'm getting the idea that that may actually work...in which case my last version is unneeded.
Except, it breaks here:
00123
001145 <-should be the lesser (the leading zeros)

OTOH, it could be done by recording the zero while walking up the chain:
/*NOT tested*/
while (*l && *r && l[0]==r[0]){
	if (l[0]='0'){
		nozero=1;
	} else if (!isdigit(l[0])) {
		nozero=0;
	}
	l++; r++;
}
if ((isdigit(l[0]) && isdigit(r[0]) && nozero) {
	//return the one with the longer substring of numbers
} else {
	return (l[0] -  r[0]);
}
-- 
Isaac Dunham <idunham@lavabit.com>

Re: Fix strverscmp

[Rich Felker]

On Wed, Dec 05, 2012 at 06:21:01PM -0800, Isaac Dunham wrote:
> > My understanding of the code is that, after it hits the first place
> > where the strings differ, it switches to reading a digit string as a
> > decimal number, and the result is the difference of those decimal
> > numbers. I just used the decimal point as an example because it
> > terminates the loop.
> More-or-less, except that if the character is a number, it is
> expected to backtrack to the start of the longest substring which is
> purely numeric (the specification is rather insane, I think)

Backtracking is not required. You can just keep minimal addtional
state.

> > then a simple algorithm would be to, on the first mismatching byte,
> > remember the difference, then count the number of consecutive digits
> > starting at that position in both strings. If this count is the same
> > (possibly zero) for both strings, return the saved byte difference. If
> > the count is different, consider the string with fewer digits to be
> > less than the one with more digits. This is trivial to implement with
> > no arithmetic, but I'm not sure it matches the original semantics.
> Hmm...
> I'm getting the idea that that may actually work...in which case my
> last version is unneeded.
> Except, it breaks here:
> 00123
> 001145 <-should be the lesser (the leading zeros)

Yes, I was unaware of the leading-zero semantics when I wrote that.
See my revised email with a proposed algorithm.

> OTOH, it could be done by recording the zero while walking up the chain:
> /*NOT tested*/
> while (*l && *r && l[0]==r[0]){
> 	if (l[0]='0'){
> 		nozero=1;

It can't set the flag unconditionally, only if the previous byte was
not a digit. Otherwise, non-leading zeros would break handling of
numeric differences.

Rich

Re: Fix strverscmp

[Isaac Dunham]

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

On Wed, 5 Dec 2012 21:26:40 -0500
Rich Felker <dalias@aerifal.cx> wrote:

> > I'm getting the idea that that may actually work...in which case my
> > last version is unneeded.
> > Except, it breaks here:
> > 00123
> > 001145 <-should be the lesser (the leading zeros)
> 
> Yes, I was unaware of the leading-zero semantics when I wrote that.
> See my revised email with a proposed algorithm.

Which is almost exactly the same as the method below:

> > OTOH, it could be done by recording the zero while walking up the chain:
> > /*NOT tested*/
> > while (*l && *r && l[0]==r[0]){
> > 	if (l[0]='0'){
> > 		nozero=1;
> 
> It can't set the flag unconditionally, only if the previous byte was
> not a digit. Otherwise, non-leading zeros would break handling of
> numeric differences.
Fortunately for us, that appears to be incorrect:
idunham@Caracal:~$ ./a.out jan012 jan0111
1
1
idunham@Caracal:~$ ./a.out jan0001 jan001
-1
-1
idunham@Caracal:~$ ./a.out 0001 001
-1
-1
idunham@Caracal:~$ ./a.out 001 0001
1
1
idunham@Caracal:~$ ./a.out 0012 00111
1
1
idunham@Caracal:~$ ./a.out 00012 00111
-1
-1
idunham@Caracal:~$ ./a.out 00120 00111
1
1

That's testing with the attached version.


-- 
Isaac Dunham <idunham@lavabit.com>

[-- Attachment #2: strvers.c --]
[-- Type: text/x-csrc, Size: 792 bytes --]

#define _GNU_SOURCE
#define _XOPEN_SOURCE	700
#include <stdio.h>
#include <string.h>
#include <ctype.h>


int str_vers_cmp(const char *l, const char *r){
	int haszero=0;
	while (*l && *r && l[0]==r[0]){
		if (l[0]=='0'){
			haszero=0;
		} else if (!isdigit(l[0])) {
			haszero=1;
		}
		l++; r++;
	}
	if ((isdigit(l[0]) && isdigit(r[0]) ) && haszero) {
	//return the one with the longer substring of numbers
		int lenl=0, lenr=0, firstl=l[0], firstr=r[0];
		while (isdigit(l++[0]) ) {
			lenl++;
		}
		while (isdigit(r++[0]) ) {
			lenr++;
		}
		if (lenl==lenr) {
			return (firstl -  firstr);
		} else {
			return (lenl - lenr);
		}
	} else {
		return (l[0] -  r[0]);
	}
} 

int main(int argc, char **argv){
	printf("%d\n%d\n",str_vers_cmp(argv[1], argv[2]), strverscmp(argv[1], argv[2]));
}

Re: Fix strverscmp

[Rich Felker]

On Wed, Dec 05, 2012 at 07:18:19PM -0800, Isaac Dunham wrote:
> > It can't set the flag unconditionally, only if the previous byte was
> > not a digit. Otherwise, non-leading zeros would break handling of
> > numeric differences.
> Fortunately for us, that appears to be incorrect:
> idunham@Caracal:~$ ./a.out jan012 jan0111
> 1
> 1
> idunham@Caracal:~$ ./a.out jan0001 jan001
> -1
> -1
> idunham@Caracal:~$ ./a.out 0001 001
> -1
> -1
> idunham@Caracal:~$ ./a.out 001 0001
> 1
> 1
> idunham@Caracal:~$ ./a.out 0012 00111
> 1
> 1
> idunham@Caracal:~$ ./a.out 00012 00111
> -1
> -1
> idunham@Caracal:~$ ./a.out 00120 00111
> 1
> 1
> 
> That's testing with the attached version.

All that means is that you missed testing any case where it differs.

./a.out s10212 s102102
2
-1

Rich

Re: Fix strverscmp

[Isaac Dunham]

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

On Wed, 5 Dec 2012 23:14:56 -0500
Rich Felker <dalias@aerifal.cx> wrote:

> All that means is that you missed testing any case where it differs.
> 
> ./a.out s10212 s102102
> 2
> -1

I realized what you meant just after sending the last email...
Anyhow, after working out how the state should change and a little bit of testing, I arrived at the attached version.

Logic for the upper part:
Start, assuming a non-numeric char (1)
--if initialized to 0, it will break the case where the first 2 characters are differing digits!
while walking down to the difference, 
-record 0 if char was last
-record 2 for any other digit if char was last
-Reset to 1 if a non-digit is found.
This records the leading digit of a sequence.
When the difference is reached, record 0 if one branch contains a leading zero.


-- 
Isaac Dunham <idunham@lavabit.com>

[-- Attachment #2: strvers.c --]
[-- Type: text/x-csrc, Size: 933 bytes --]

#define _GNU_SOURCE
#define _XOPEN_SOURCE	700
#include <stdio.h>
#include <string.h>
#include <ctype.h>


int str_vers_cmp(const char *l, const char *r){
	int haszero=1;
	while (*l && *r && l[0]==r[0]){
		if (l[0]=='0'){
			if (haszero==1) {
				haszero=0;
			}
		} else if (isdigit(l[0])) {
			if (haszero==1) {
				haszero=2;
			}
		} else {
			haszero=1;
		}
		l++; r++;
	}
	if (haszero==1 && (l[0]=='0' || r[0]=='0')) {
		haszero=0;
	}
	if ((isdigit(l[0]) && isdigit(r[0]) ) && haszero) {
	//return the one with the longer substring of numbers
		int lenl=0, lenr=0, firstl=l[0], firstr=r[0];
		while (isdigit(l++[0]) ) {
			lenl++;
		}
		while (isdigit(r++[0]) ) {
			lenr++;
		}
		if (lenl==lenr) {
			return (firstl -  firstr);
		} else {
			return (lenl - lenr);
		}
	} else {
		return (l[0] -  r[0]);
	}
} 

int main(int argc, char **argv){
	printf("%d\n%d\n",str_vers_cmp(argv[1], argv[2]), strverscmp(argv[1], argv[2]));
}