[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20121206022640.GQ20323@brightrain.aerifal.cx>
Date: Wed, 5 Dec 2012 21:26:40 -0500
From: Rich Felker <dalias@...ifal.cx>
To: musl@...ts.openwall.com
Subject: Re: Fix strverscmp
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
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
