From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/2419 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 21:26:40 -0500 Message-ID: <20121206022640.GQ20323@brightrain.aerifal.cx> References: <20121205110959.87b6111a.idunham@lavabit.com> <20121205193520.GN20323@brightrain.aerifal.cx> <20121205164329.c5cd3a20.idunham@lavabit.com> <20121206010000.GO20323@brightrain.aerifal.cx> <20121205182101.d997eb6e.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 1354760815 9590 80.91.229.3 (6 Dec 2012 02:26:55 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 6 Dec 2012 02:26:55 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-2420-gllmg-musl=m.gmane.org@lists.openwall.com Thu Dec 06 03:27:08 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 1TgRB2-0004Fr-VQ for gllmg-musl@plane.gmane.org; Thu, 06 Dec 2012 03:27:05 +0100 Original-Received: (qmail 1434 invoked by uid 550); 6 Dec 2012 02:26:52 -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 1421 invoked from network); 6 Dec 2012 02:26:52 -0000 Content-Disposition: inline In-Reply-To: <20121205182101.d997eb6e.idunham@lavabit.com> User-Agent: Mutt/1.5.21 (2010-09-15) Xref: news.gmane.org gmane.linux.lib.musl.general:2419 Archived-At: 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