From: Isaac Dunham <idunham@lavabit.com>
To: musl@lists.openwall.com
Subject: Re: Fix strverscmp
Date: Wed, 5 Dec 2012 18:21:01 -0800 [thread overview]
Message-ID: <20121205182101.d997eb6e.idunham@lavabit.com> (raw)
In-Reply-To: <20121206010000.GO20323@brightrain.aerifal.cx>
On Wed, 5 Dec 2012 20:00:00 -0500
Rich Felker <dalias@aerifal.cx> wrote:
> > 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.
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)
> I also don't understand what you mean about leading zero. If leading
> zeros are not considered equal to the number without leading zeros,
They are explicitly stated to be different in the man page:
"
What this function does is the following. If both strings are equal,
return 0. Otherwise find the position between two bytes with the prop-
erty that before it both strings are equal, while directly after it
there is a difference. Find the largest consecutive digit strings con-
taining (or starting at, or ending at) this position. If one or both
of these is empty, then return what strcmp(3) would have returned
(numerical ordering of byte values). Otherwise, compare both digit
strings numerically, where digit strings with one or more leading zeros
are interpreted as if they have a decimal point in front (so that in
particular digit strings with more leading zeros come before digit
strings with fewer leading zeros). Thus, the ordering is 000, 00, 01,
010, 09, 0, 1, 9, 10.
"
> 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)
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;
} else if (!isdigit(l[0])) {
nozero=0;
}
l++; r++;
}
if ((isdigit(l[0]) && isdigit(r[0]) && nozero) {
//return the one with the longer substring of numbers
} else {
return (l[0] - r[0]);
}
--
Isaac Dunham <idunham@lavabit.com>
next prev parent reply other threads:[~2012-12-06 2:21 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 [this message]
2012-12-06 2:26 ` Rich Felker
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=20121205182101.d997eb6e.idunham@lavabit.com \
--to=idunham@lavabit.com \
--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).