Date: Wed, 5 Dec 2012 21:14:38 -0500 From: Rich Felker <dalias@...ifal.cx> To: musl@...ts.openwall.com Subject: Re: Fix strverscmp On Wed, Dec 05, 2012 at 08:00:00PM -0500, Rich Felker 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. > > 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. OK, I read the "spec" in the man page, and this seems to be the simplest implementation: 1. Find the first mismatching bytes. During this search, keep 1 bit of state that's set when a '0' byte is encountered now following a digit, and cleared when any non-digit byte is encountered. 2. Upon finding the first mismatching bytes, if either is a non-digit or '0' or if above-described flag is set, return the difference of the mismatching bytes. 3. Otherwise, count the number of consecutive digits beginning with the first mismatching bytes. If the count differs for the two strings, the string with the lower count compares less. Otherwise, return the difference of the first mismatching bytes. The rules in step 2 cover both the leading-zeros rule and non-numeric cases. The rules in step 3 cover the simple numeric comparison rule that the longer number is greater, with ties broken by comparing the most-significant position that differs. Does this sound correct to you? I like the concept of the flag in the first phase, which we could easily extend to treat other cases as non-numeric if desired. 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.