From: Rich Felker <dalias@aerifal.cx>
To: musl@lists.openwall.com
Subject: Re: Fix strverscmp
Date: Wed, 5 Dec 2012 21:26:40 -0500 [thread overview]
Message-ID: <20121206022640.GQ20323@brightrain.aerifal.cx> (raw)
In-Reply-To: <20121205182101.d997eb6e.idunham@lavabit.com>
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
next prev parent reply other threads:[~2012-12-06 2:26 UTC|newest]
Thread overview: 10+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-12-05 19:09 [PATCH] " Isaac Dunham
2012-12-05 19:35 ` Rich Felker
2012-12-06 0:43 ` Isaac Dunham
2012-12-06 1:00 ` Rich Felker
2012-12-06 2:14 ` Rich Felker
2012-12-06 2:21 ` Isaac Dunham
2012-12-06 2:26 ` Rich Felker [this message]
2012-12-06 3:18 ` Isaac Dunham
2012-12-06 4:14 ` Rich Felker
2012-12-07 0:36 ` Isaac Dunham
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20121206022640.GQ20323@brightrain.aerifal.cx \
--to=dalias@aerifal.cx \
--cc=musl@lists.openwall.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/musl/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).