Re: Fix strverscmp

[Isaac Dunham <idunham@lavabit.com>]

[-- 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]));
}