* utf-8 collation of domain names

* case insensitive comparison of domain names


git-svn-id: file:///home/lennart/svn/public/avahi/trunk@71 941a03a8-eaeb-0310-b9a0-b1bbd8fe43fe

8 files changed, 239 insertions, 198 deletions

diff --git a/avahi-core/avahi-test.c b/avahi-core/avahi-test.c
index ba9d7cd..553a021 100644
--- a/avahi-core/avahi-test.c
+++ b/avahi-core/avahi-test.c
@@ -71,7 +71,9 @@ int main(int argc, char *argv[]) {
 
      g = avahi_entry_group_new(avahi, entry_group_callback, NULL);  
     
-    avahi_server_add_text(avahi, g, 0, AF_UNSPEC, AVAHI_ENTRY_UNIQUE, NULL, "hallo", NULL); 
+    avahi_server_add_text(avahi, g, 0, AF_UNSPEC, AVAHI_ENTRY_UNIQUE, "HALLO", "hallo", NULL); 
+    avahi_server_add_text(avahi, g, 0, AF_UNSPEC, AVAHI_ENTRY_UNIQUE, "hallo", "waldo", NULL);
+    
     avahi_server_add_service(avahi, g, 0, AF_UNSPEC, "_http._tcp", "gurke", NULL, NULL, 80, "foo", NULL);  
     
     avahi_entry_group_commit(g);  
diff --git a/avahi-core/dns.c b/avahi-core/dns.c
index 531e3cf..41d645f 100644
--- a/avahi-core/dns.c
+++ b/avahi-core/dns.c
@@ -139,48 +139,6 @@ void avahi_dns_packet_inc_field(AvahiDnsPacket *p, guint index) {
 
 
 
-/* Read the first label from string *name, unescape "\" and write it to dest */
-gchar *avahi_unescape_label(gchar *dest, guint size, const gchar **name) {
-    guint i = 0;
-    gchar *d;
-    
-    g_assert(dest);
-    g_assert(size > 0);
-    g_assert(name);
-    g_assert(*name);
-
-    d = dest;
-    
-    for (;;) {
-        if (i >= size)
-            return NULL;
-
-        if (**name == '.') {
-            (*name)++;
-            break;
-        }
-        
-        if (**name == 0)
-            break;
-        
-        if (**name == '\\') {
-            (*name) ++;
-            
-            if (**name == 0)
-                break;
-        }
-        
-        *(d++) = *((*name) ++);
-        i++;
-    }
-
-    g_assert(i < size);
-
-    *d = 0;
-
-    return dest;
-}
-
 guint8* avahi_dns_packet_append_name(AvahiDnsPacket *p, const gchar *name) {
     guint8 *d, *saved_ptr = NULL;
     guint saved_size;
@@ -218,14 +176,15 @@ guint8* avahi_dns_packet_append_name(AvahiDnsPacket *p, const gchar *name) {
 
         pname = name;
         
-        if (!(avahi_unescape_label(label, sizeof(label), &name)))
+        if (!(avahi_unescape_label(&name, label, sizeof(label))))
             goto fail;
 
         if (!(d = avahi_dns_packet_append_string(p, label)))
             goto fail;
 
         if (!p->name_table)
-            p->name_table = g_hash_table_new_full((GHashFunc) avahi_domain_hash, (GEqualFunc) avahi_domain_equal, g_free, NULL);
+            /* This works only for normalized domain names */
+            p->name_table = g_hash_table_new_full((GHashFunc) g_str_hash, (GEqualFunc) g_str_equal, g_free, NULL);
 
         g_hash_table_insert(p->name_table, g_strdup(pname), d);
     }
@@ -333,42 +292,6 @@ gint avahi_dns_packet_is_query(AvahiDnsPacket *p) {
     return !(avahi_dns_packet_get_field(p, AVAHI_DNS_FIELD_FLAGS) & AVAHI_DNS_FLAG_QR);
 }
 
-/* Read a label from a DNS packet, escape "\" and ".", append \0 */
-static gchar *escape_label(guint8* src, guint src_length, gchar **ret_name, guint *ret_name_length) {
-    gchar *r;
-
-    g_assert(src);
-    g_assert(ret_name);
-    g_assert(*ret_name);
-    g_assert(ret_name_length);
-    g_assert(*ret_name_length > 0);
-
-    r = *ret_name;
-
-    while (src_length > 0) {
-        if (*src == '.' || *src == '\\') {
-            if (*ret_name_length < 3)
-                return NULL;
-            
-            *((*ret_name) ++) = '\\';
-            (*ret_name_length) --;
-        }
-
-        if (*ret_name_length < 2)
-            return NULL;
-        
-        *((*ret_name)++) = *src;
-        (*ret_name_length) --;
-
-        src_length --;
-        src++;
-    }
-
-    **ret_name = 0;
-
-    return r;
-}
-
 static gint consume_labels(AvahiDnsPacket *p, guint index, gchar *ret_name, guint l) {
     gint ret = 0;
     int compressed = 0;
@@ -412,7 +335,7 @@ static gint consume_labels(AvahiDnsPacket *p, guint index, gchar *ret_name, guin
             } else
                 first_label = 0;
 
-            if (!(escape_label(AVAHI_DNS_PACKET_DATA(p) + index, n, &ret_name, &l)))
+            if (!(avahi_escape_label(AVAHI_DNS_PACKET_DATA(p) + index, n, &ret_name, &l)))
                 return -1;
 
             index += n;
diff --git a/avahi-core/dns.h b/avahi-core/dns.h
index f1ecfe0..24f4ced 100644
--- a/avahi-core/dns.h
+++ b/avahi-core/dns.h
@@ -101,7 +101,5 @@ guint avahi_dns_packet_space(AvahiDnsPacket *p);
          ((guint16) (rd & 15)))
          
 
-gchar *avahi_unescape_label(gchar *dest, guint size, const gchar **name);
-
 #endif
 
diff --git a/avahi-core/domain-test.c b/avahi-core/domain-test.c
index 7f6bd7b..240f960 100644
--- a/avahi-core/domain-test.c
+++ b/avahi-core/domain-test.c
@@ -34,11 +34,15 @@ int main(int argc, char *argv[]) {
     g_message("%s", s = avahi_normalize_name("foo.foo."));
     g_free(s);
     
-    g_message("%s", s = avahi_normalize_name("foo.foo."));
+    g_message("%s", s = avahi_normalize_name("\\f\\o\\\\o\\..\\f\\ \\o\\o."));
     g_free(s);
 
-
     g_message("%i", avahi_domain_equal("\\aaa bbb\\.cccc\\\\.dee.fff.", "aaa\\ bbb\\.cccc\\\\.dee.fff"));
+    g_message("%i", avahi_domain_equal("\\A", "a"));
 
+    g_message("%i", avahi_domain_equal("a", "aaa"));
+
+    g_message("%u = %u", avahi_domain_hash("\\Aaaab\\\\."), avahi_domain_hash("aaaa\\b\\\\"));
+    
     return 0;
 }
diff --git a/avahi-core/rr.c b/avahi-core/rr.c
index cbc39a5..a9f6361 100644
--- a/avahi-core/rr.c
+++ b/avahi-core/rr.c
@@ -274,7 +274,10 @@ gboolean avahi_key_is_pattern(const AvahiKey *k) {
 guint avahi_key_hash(const AvahiKey *k) {
     g_assert(k);
 
-    return avahi_domain_hash(k->name) + k->type + k->class;
+    return
+        avahi_domain_hash(k->name) + 
+        k->type +
+        k->class;
 }
 
 static gboolean rdata_equal(const AvahiRecord *a, const AvahiRecord *b) {
@@ -305,8 +308,8 @@ static gboolean rdata_equal(const AvahiRecord *a, const AvahiRecord *b) {
 
         case AVAHI_DNS_TYPE_HINFO:
             return
-                !strcmp(a->data.hinfo.cpu, b->data.hinfo.cpu) &&
-                !strcmp(a->data.hinfo.os, b->data.hinfo.os);
+                !g_utf8_collate(a->data.hinfo.cpu, b->data.hinfo.cpu) &&
+                !g_utf8_collate(a->data.hinfo.os, b->data.hinfo.os);
 
         case AVAHI_DNS_TYPE_TXT:
             return avahi_string_list_equal(a->data.txt.string_list, b->data.txt.string_list);
@@ -439,7 +442,7 @@ static gint lexicographical_memcmp(gconstpointer a, size_t al, gconstpointer b,
     g_assert(b);
 
     c = al < bl ? al : bl;
-    if ((ret = memcmp(a, b, c)) != 0)
+    if ((ret = memcmp(a, b, c)))
         return ret;
 
     if (al == bl)
@@ -452,97 +455,37 @@ static gint uint16_cmp(guint16 a, guint16 b) {
     return a == b ? 0 : (a < b ? a : b);
 }
 
-static gint lexicographical_domain_cmp(const gchar *a, const gchar *b) {
-    g_assert(a);
-    g_assert(b);
-    
-
-    for (;;) {
-        gchar t1[64];
-        gchar t2[64];
-        size_t al, bl;
-        gint r;
-
-        if (!a && !b)
-            return 0;
-
-        if (a && !b)
-            return 1;
-
-        if (b && !a)
-            return -1;
-        
-        avahi_unescape_label(t1, sizeof(t1), &a);
-        avahi_unescape_label(t2, sizeof(t2), &b);
-
-        al = strlen(t1);
-        bl = strlen(t2);
-        
-        if (al != bl) 
-            return al < bl ? -1 : 1;
-
-        if ((r =  strcmp(t1, t2)) != 0)
-            return r;
-    }
-}
-
 gint avahi_record_lexicographical_compare(AvahiRecord *a, AvahiRecord *b) {
     g_assert(a);
     g_assert(b);
+    gint r;
 
     if (a == b)
         return 0;
-    
-/*     gchar *t; */
-
-/*     g_message("comparing [%s]", t = avahi_record_to_string(a)); */
-/*     g_free(t); */
-
-/*     g_message("and [%s]", t = avahi_record_to_string(b)); */
-/*     g_free(t); */
-
-    if (a->key->class < b->key->class)
-        return -1;
-    else if (a->key->class > b->key->class)
-        return 1;
 
-    if (a->key->type < b->key->type)
-        return -1;
-    else if (a->key->type > b->key->type)
-        return 1;
+    if ((r = uint16_cmp(a->key->class, b->key->class)) ||
+        (r = uint16_cmp(a->key->type, b->key->type)))
+        return r;
 
     switch (a->key->type) {
 
         case AVAHI_DNS_TYPE_PTR:
         case AVAHI_DNS_TYPE_CNAME:
-            return lexicographical_domain_cmp(a->data.ptr.name, b->data.ptr.name);
+            return avahi_binary_domain_cmp(a->data.ptr.name, b->data.ptr.name);
 
         case AVAHI_DNS_TYPE_SRV: {
-            gint r;
             if ((r = uint16_cmp(a->data.srv.priority, b->data.srv.priority)) == 0 &&
                 (r = uint16_cmp(a->data.srv.weight, b->data.srv.weight)) == 0 &&
                 (r = uint16_cmp(a->data.srv.port, b->data.srv.port)) == 0)
-                r = lexicographical_domain_cmp(a->data.srv.name, b->data.srv.name);
+                r = avahi_binary_domain_cmp(a->data.srv.name, b->data.srv.name);
             
             return r;
         }
 
         case AVAHI_DNS_TYPE_HINFO: {
-            size_t al = strlen(a->data.hinfo.cpu), bl = strlen(b->data.hinfo.cpu);
-            gint r;
-
-            if (al != bl)
-                return al < bl ? -1 : 1;
-
-            if ((r = strcmp(a->data.hinfo.cpu, b->data.hinfo.cpu)) != 0)
-                return r;
-
-            al = strlen(a->data.hinfo.os), bl = strlen(b->data.hinfo.os);
-
-            if (al != bl)
-                return al < bl ? -1 : 1;
 
-            if ((r = strcmp(a->data.hinfo.os, b->data.hinfo.os)) != 0)
+            if ((r = strcmp(a->data.hinfo.cpu, b->data.hinfo.cpu)) ||
+                (r = strcmp(a->data.hinfo.os, b->data.hinfo.os)))
                 return r;
 
             return 0;
@@ -553,7 +496,6 @@ gint avahi_record_lexicographical_compare(AvahiRecord *a, AvahiRecord *b) {
 
             guint8 *ma, *mb;
             guint asize, bsize;
-            gint r;
 
             ma = g_new(guint8, asize = avahi_string_list_serialize(a->data.txt.string_list, NULL, 0));
             mb = g_new(guint8, bsize = avahi_string_list_serialize(b->data.txt.string_list, NULL, 0));
diff --git a/avahi-core/util.c b/avahi-core/util.c
index fa97eec..086c041 100644
--- a/avahi-core/util.c
+++ b/avahi-core/util.c
@@ -43,19 +43,60 @@ gchar *avahi_get_host_name(void) {
     return avahi_normalize_name(t);
 }
 
+static gchar *unescape_uneeded(const gchar *src, gchar *ret_dest, size_t size) {
+    gboolean escaped = FALSE;
+    
+    g_assert(src);
+    g_assert(ret_dest);
+    g_assert(size > 0);
+    
+    for (; *src; src++) {
+
+        if (!escaped && *src == '\\')
+            escaped = TRUE;
+        else if (escaped && (*src == '.' || *src == '\\')) {
+
+            if ((size -= 2) <= 1) break;
+            
+            *(ret_dest++) = '\\';
+            *(ret_dest++) = *src;
+
+            escaped = FALSE;
+        } else {
+            if (--size <= 1) break;
+
+            *(ret_dest++) = *src;
+            escaped = FALSE;
+        }
+
+    }
+
+    *ret_dest = 0;
+    
+    return ret_dest;
+}
+
 gchar *avahi_normalize_name(const gchar *s) {
-    size_t l;
+    gchar tmp[256];
+    gchar *n, *t;
+    guint l;
     g_assert(s);
 
-    l = strlen(s);
+    unescape_uneeded(s, tmp, sizeof(tmp));
 
-    if (!l)
+    n = g_utf8_normalize(tmp, -1, G_NORMALIZE_DEFAULT);
+
+    if ((l = strlen(n)) == 0) {
+        g_free(n);
         return g_strdup(".");
+    }
 
-    if (s[l-1] == '.')
-        return g_strdup(s);
-    
-    return g_strdup_printf("%s.", s);
+    if (n[l-1] == '.')
+        return n;
+
+    t = g_strdup_printf("%s.", n);
+    g_free(n);
+    return t;
 }
 
 gint avahi_timeval_compare(const GTimeVal *a, const GTimeVal *b) {
@@ -158,50 +199,151 @@ gint avahi_age(const GTimeVal *a) {
     return avahi_timeval_diff(&now, a);
 }
 
-gboolean avahi_domain_cmp(const gchar *a, const gchar *b) {
-    int escaped_a = 0, escaped_b = 0;
-    g_assert(a);
-    g_assert(b);
+/* Read the first label from string *name, unescape "\" and write it to dest */
+gchar *avahi_unescape_label(const gchar **name, gchar *dest, guint size) {
+    guint i = 0;
+    gchar *d;
+    
+    g_assert(dest);
+    g_assert(size > 0);
+    g_assert(name);
 
-    for (;;) {
-        /* Check for escape characters "\" */
-        if ((escaped_a = *a == '\\'))
-            a ++;
+    if (!**name)
+        return NULL;
 
-        if ((escaped_b = *b == '\\'))
-            b++;
+    d = dest;
+    
+    for (;;) {
+        if (i >= size)
+            return NULL;
 
-        /* Check for string end */
-        if (*a == 0 && *b == 0)
-            return 0;
+        if (**name == '.') {
+            (*name)++;
+            break;
+        }
         
-        if (*a == 0 && !escaped_b && *b == '.' && *(b+1) == 0)
-            return 0;
+        if (**name == 0)
+            break;
+        
+        if (**name == '\\') {
+            (*name) ++;
+            
+            if (**name == 0)
+                break;
+        }
+        
+        *(d++) = *((*name) ++);
+        i++;
+    }
 
-        if (!escaped_a && *a == '.' && *(a+1) == 0 && *b == 0)
-            return 0;
+    g_assert(i < size);
+
+    *d = 0;
+
+    return dest;
+}
 
-        /* Compare characters */
-        if (escaped_a == escaped_b && *a != *b)
-            return *a < *b ? -1 : 1;
+/* Escape "\" and ".", append \0 */
+gchar *avahi_escape_label(const guint8* src, guint src_length, gchar **ret_name, guint *ret_size) {
+    gchar *r;
+
+    g_assert(src);
+    g_assert(ret_name);
+    g_assert(*ret_name);
+    g_assert(ret_size);
+    g_assert(*ret_size > 0);
+
+    r = *ret_name;
+
+    while (src_length > 0) {
+        if (*src == '.' || *src == '\\') {
+            if (*ret_size < 3)
+                return NULL;
+            
+            *((*ret_name) ++) = '\\';
+            (*ret_size) --;
+        }
 
-        /* Next characters */
-        a++;
-        b++;
+        if (*ret_size < 2)
+            return NULL;
         
+        *((*ret_name)++) = *src;
+        (*ret_size) --;
+
+        src_length --;
+        src++;
     }
+
+    **ret_name = 0;
+
+    return r;
+}
+
+static gint utf8_strcasecmp(const gchar *a, const gchar *b) {
+    gchar *ta, *tb;
+    gint r;
+    
+    g_assert(a);
+    g_assert(b);
+
+    ta = g_utf8_casefold(a, -1);
+    tb = g_utf8_casefold(b, -1);
+    r = g_utf8_collate(ta, tb);
+    g_free(ta);
+    g_free(tb);
+
+    return r;
 }
 
 gboolean avahi_domain_equal(const gchar *a, const gchar *b) {
-    return avahi_domain_cmp(a, b) == 0;
+    g_assert(a);
+    g_assert(b);
+
+    if (a == b)
+        return TRUE;
+    
+    for (;;) {
+        gchar ca[65], cb[65], *pa, *pb;
+
+        pa = avahi_unescape_label(&a, ca, sizeof(ca));
+        pb = avahi_unescape_label(&b, cb, sizeof(cb));
+
+        if (!pa && !pb)
+            return TRUE;
+        else if ((pa && !pb) || (!pa && pb))
+            return FALSE;
+
+        if (utf8_strcasecmp(pa, pb))
+            return FALSE;
+    }
+
+    return TRUE;
 }
 
-guint avahi_domain_hash(const gchar *p) {
-    char t[256];
-    strncpy(t, p, sizeof(t)-1);
-    t[sizeof(t)-1] = 0;
+gint avahi_binary_domain_cmp(const gchar *a, const gchar *b) {
+    g_assert(a);
+    g_assert(b);
+
+    if (a == b)
+        return 0;
+
+    for (;;) {
+        gchar ca[65], cb[65], *pa, *pb;
+        gint r;
+
+        pa = avahi_unescape_label(&a, ca, sizeof(ca));
+        pb = avahi_unescape_label(&b, cb, sizeof(cb));
 
-    return g_int_hash(t);
+        if (!pa && !pb)
+            return 0;
+        else if (pa && !pb)
+            return 1;
+        else if (!pa && pb)
+            return -1;
+        
+        if ((r = strcmp(pa, pb)))
+            return r;
+    }
 }
 
 void avahi_hexdump(gconstpointer p, guint size) {
@@ -237,3 +379,25 @@ void avahi_hexdump(gconstpointer p, guint size) {
         size -= 16;
     }
 }
+
+gint avahi_domain_hash(const gchar *s) {
+    guint hash = 0;
+    
+    for (;;) {
+        gchar c[65], *n, *m;
+
+        if (!avahi_unescape_label(&s, c, sizeof(c)))
+            return hash;
+
+        if (!c[0])
+            continue;
+        
+        n = g_utf8_normalize(c, -1, G_NORMALIZE_DEFAULT);
+        m = g_utf8_strdown(n, -1);
+
+        hash += g_str_hash(m);
+
+        g_free(m);
+        g_free(n);
+    }
+}
diff --git a/avahi-core/util.h b/avahi-core/util.h
index 1186cc2..6dcecfd 100644
--- a/avahi-core/util.h
+++ b/avahi-core/util.h
@@ -38,10 +38,18 @@ GTimeVal *avahi_elapse_time(GTimeVal *tv, guint msec, guint jitter);
 
 gint avahi_age(const GTimeVal *a);
 
-guint avahi_domain_hash(const gchar *p);
-gboolean avahi_domain_cmp(const gchar *a, const gchar *b);
 gboolean avahi_domain_equal(const gchar *a, const gchar *b);
+gint avahi_binary_domain_cmp(const gchar *a, const gchar *b);
 
 void avahi_hexdump(gconstpointer p, guint size);
 
+/* Read the first label from the textual domain name *name, unescape
+ * it and write it to dest, *name is changed to point to the next label*/
+gchar *avahi_unescape_label(const gchar **name, gchar *dest, guint size);
+
+/* Escape the domain name in *src and write it to *ret_name */
+gchar *avahi_escape_label(const guint8* src, guint src_length, gchar **ret_name, guint *ret_size);
+
+gint avahi_domain_hash(const gchar *s);
+
 #endif
diff --git a/todo b/todo
index 1a33d73..d3d2f0c 100644
--- a/todo
+++ b/todo
@@ -5,7 +5,6 @@ RFC MUSTs:
 	* Return to probing state on conflict
 	* fix flush bit when working on RRsets
 	* one RR too large for single packet
-	* case insensitve comparision
 
 * test against apple test suite
 
@@ -37,4 +36,5 @@ done:
 * support known answer suppresion for incoming unicast queries
 * check wether RRsets are supported correctly (i.e. that all records of an
   RRset are really sent if it is requested) (rfc 2181)
+* case insensitve comparision