Re: Algorithm for right-to-left comparison of strings

ssg31415926 writes:
Is there a standard algorithm for right-to-left comparison of
(probably unequal-length) strings?

I want to be able to sort a collection of distinguishedNames. DNs are
right-to-left significant, if you see what I mean, like DNS names.
(...)

First walk through the strings once, generating the information you need
to sort them easily.

Maybe a struct {pointer to end of string, length}.
Or {number of components, reverse array {component, length}}.

Or reverse the order of the components of each DN:
"ou=one,dc=two,dc=three" -> {length, "dc=three\0dc=two\0ou=one\0"}.
Sort with memcmp, being careful to use the smallest string length + 1.
The \0's prevent the presumably-undesired sort order
ou=one,dc=two,dc=three (reversed ...,dc=two,ou=one)
dc=one more,dc=two,dc=three (reversed ...,dc=two,dc=one more)
cn=zero,ou=one,dc=two,dc=three (reversed ...,dc=two,ou=one,cn=zero)
wich you'd get if you kept the commas.

DNs are complex beasts though. Do you e.g. need to worry about
different spellings of DNs that compare equal? If so, part of the
preparation above should be to pick a normalized format and convert them
all to it before comparing. Upper->lowercase. Pick one of the several
ways to spell special chars. E.g. a DN component can contain an escaped
comma spelled as "\," or "\2C". (At least LDAP DNs, I don't know the
current details of spelling X.500 DNs). And so on.

That can still be fooled if someone tries to though, e.g. by feeding you
a DN component in "oid=#hex" format (see RFC 4514). So if you *really*
need correct sorting, you need to convert the DNs back to data
structures ((RDN = "attr=decoded value", ...), RDN, ...) and sort those.

--
Hallvard
.

Relevant Pages

  • Re: Algorithm for right-to-left comparison of strings
    ... First walk through the strings once, ... Sort with memcmp, being careful to use the smallest string length + 1. ... DNs are complex beasts though. ... preparation above should be to pick a normalized format and convert them ...
    (comp.programming)
  • Re: major DNS hiccup
    ... The hypothesis was that if ntl have put some sort of transparent cache into place, this /ought/ not to reach the root server - maybe! ... And I didn't know that it uses the remote port number to encode the attempt identification, icmp replies apparently not including enough data to match them to the particular sent packets. ... I'll keep it on the back burner - if ntl are intercepting DNS packets, there has to be a way to prove it! ...
    (comp.unix.bsd.freebsd.misc)
  • Re: [fw-wiz] New Script Kiddie tool ?
    ... UDP 53 is DNS. ... There's a detailed write-up of this sort of attack at ... http://www.grc.com under "Direct Reflected DoS". ... >Senior Security Engineer - Sydney ...
    (Firewall-Wizards)
  • Re: Algorithm for right-to-left comparison of strings
    ... I want to be able to sort a collection of distinguishedNames. ... right-to-left significant, if you see what I mean, like DNS names. ... One strategy is to reverse the strings before the compare. ...
    (comp.programming)
  • Re: mirroring domains
    ... I agree with Jorge that this is sort of asking for problems - especially ... when troubleshooting. ... type of resolution and make sure they are using only the DNS and WINS ... servers for the domain they are members of you wouldn't have a problem. ...
    (microsoft.public.win2000.active_directory)