From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/2415 Path: news.gmane.org!not-for-mail From: Isaac Dunham Newsgroups: gmane.linux.lib.musl.general Subject: Re: Fix strverscmp Date: Wed, 5 Dec 2012 16:43:29 -0800 Message-ID: <20121205164329.c5cd3a20.idunham@lavabit.com> References: <20121205110959.87b6111a.idunham@lavabit.com> <20121205193520.GN20323@brightrain.aerifal.cx> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="Multipart=_Wed__5_Dec_2012_16_43_29_-0800_hqwAGNdYnFSw9GHH" X-Trace: ger.gmane.org 1354754622 28609 80.91.229.3 (6 Dec 2012 00:43:42 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 6 Dec 2012 00:43:42 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-2416-gllmg-musl=m.gmane.org@lists.openwall.com Thu Dec 06 01:43:55 2012 Return-path: Envelope-to: gllmg-musl@plane.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1TgPZC-00067G-QJ for gllmg-musl@plane.gmane.org; Thu, 06 Dec 2012 01:43:54 +0100 Original-Received: (qmail 30683 invoked by uid 550); 6 Dec 2012 00:43:42 -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 30675 invoked from network); 6 Dec 2012 00:43:41 -0000 DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=lavabit; d=lavabit.com; b=fsg8y91VHvW0FYywRD13iP/Eer8LSIztKrcuDZKRZEQHCyFrUpBb8x/HteaUZF4JJhqXPHtZ0Hl/Vd1dJHttU9oRg1L5lqGzVjvWRYFaxVmaPIBFXP1CpUhvqvAO4USI7kP+kdWlfYWuuY5/D+C9zs8XU4TQQ915L5mJtSssG+w=; h=Date:From:To:Subject:Message-Id:In-Reply-To:References:X-Mailer:Mime-Version:Content-Type; In-Reply-To: <20121205193520.GN20323@brightrain.aerifal.cx> X-Mailer: Sylpheed 3.0.2 (GTK+ 2.20.1; i486-pc-linux-gnu) Xref: news.gmane.org gmane.linux.lib.musl.general:2415 Archived-At: This is a multi-part message in MIME format. --Multipart=_Wed__5_Dec_2012_16_43_29_-0800_hqwAGNdYnFSw9GHH Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit On Wed, 5 Dec 2012 14:35:21 -0500 Rich Felker 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 --Multipart=_Wed__5_Dec_2012_16_43_29_-0800_hqwAGNdYnFSw9GHH Content-Type: text/x-csrc; name="strvers.c" Content-Disposition: attachment; filename="strvers.c" Content-Transfer-Encoding: 7bit #define _GNU_SOURCE #define _XOPEN_SOURCE 700 #include #include #include #include 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 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) 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])); } --Multipart=_Wed__5_Dec_2012_16_43_29_-0800_hqwAGNdYnFSw9GHH--