From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/2416 Path: news.gmane.org!not-for-mail From: Rich Felker Newsgroups: gmane.linux.lib.musl.general Subject: Re: Fix strverscmp Date: Wed, 5 Dec 2012 20:00:00 -0500 Message-ID: <20121206010000.GO20323@brightrain.aerifal.cx> References: <20121205110959.87b6111a.idunham@lavabit.com> <20121205193520.GN20323@brightrain.aerifal.cx> <20121205164329.c5cd3a20.idunham@lavabit.com> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1354755612 3697 80.91.229.3 (6 Dec 2012 01:00:12 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 6 Dec 2012 01:00:12 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-2417-gllmg-musl=m.gmane.org@lists.openwall.com Thu Dec 06 02:00:26 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 1TgPpA-0002rD-N9 for gllmg-musl@plane.gmane.org; Thu, 06 Dec 2012 02:00:24 +0100 Original-Received: (qmail 9922 invoked by uid 550); 6 Dec 2012 01:00:12 -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 9913 invoked from network); 6 Dec 2012 01:00:12 -0000 Content-Disposition: inline In-Reply-To: <20121205164329.c5cd3a20.idunham@lavabit.com> User-Agent: Mutt/1.5.21 (2010-09-15) Xref: news.gmane.org gmane.linux.lib.musl.general:2416 Archived-At: On Wed, Dec 05, 2012 at 04:43:29PM -0800, Isaac Dunham wrote: > 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... 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