Merge remote branch 'gvdb/master'
[platform/upstream/glib.git] / glib / ghostutils.c
1 /* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
2
3 /* GLIB - Library of useful routines for C programming
4  * Copyright (C) 2008 Red Hat, Inc.
5  *
6  * This library is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Lesser General Public
8  * License as published by the Free Software Foundation; either
9  * version 2 of the License, or (at your option) any later version.
10  *
11  * This library is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General
17  * Public License along with this library; if not, write to the
18  * Free Software Foundation, Inc., 59 Temple Place, Suite 330,
19  * Boston, MA 02111-1307, USA.
20  */
21
22 #include "config.h"
23
24 #include <string.h>
25
26 #include "ghostutils.h"
27
28 #include "garray.h"
29 #include "gmem.h"
30 #include "gstring.h"
31 #include "gstrfuncs.h"
32 #include "glibintl.h"
33
34
35 /**
36  * SECTION:ghostutils
37  * @short_description: Internet hostname utilities
38  *
39  * Functions for manipulating internet hostnames; in particular, for
40  * converting between Unicode and ASCII-encoded forms of
41  * Internationalized Domain Names (IDNs).
42  *
43  * The <ulink
44  * url="http://www.ietf.org/rfc/rfc3490.txt">Internationalized Domain
45  * Names for Applications (IDNA)</ulink> standards allow for the use
46  * of Unicode domain names in applications, while providing
47  * backward-compatibility with the old ASCII-only DNS, by defining an
48  * ASCII-Compatible Encoding of any given Unicode name, which can be
49  * used with non-IDN-aware applications and protocols. (For example,
50  * "Παν語.org" maps to "xn--4wa8awb4637h.org".)
51  **/
52
53 #define IDNA_ACE_PREFIX     "xn--"
54 #define IDNA_ACE_PREFIX_LEN 4
55
56 /* Punycode constants, from RFC 3492. */
57
58 #define PUNYCODE_BASE          36
59 #define PUNYCODE_TMIN           1
60 #define PUNYCODE_TMAX          26
61 #define PUNYCODE_SKEW          38
62 #define PUNYCODE_DAMP         700
63 #define PUNYCODE_INITIAL_BIAS  72
64 #define PUNYCODE_INITIAL_N   0x80
65
66 #define PUNYCODE_IS_BASIC(cp) ((guint)(cp) < 0x80)
67
68 /* Encode/decode a single base-36 digit */
69 static inline gchar
70 encode_digit (guint dig)
71 {
72   if (dig < 26)
73     return dig + 'a';
74   else
75     return dig - 26 + '0';
76 }
77
78 static inline guint
79 decode_digit (gchar dig)
80 {
81   if (dig >= 'A' && dig <= 'Z')
82     return dig - 'A';
83   else if (dig >= 'a' && dig <= 'z')
84     return dig - 'a';
85   else if (dig >= '0' && dig <= '9')
86     return dig - '0' + 26;
87   else
88     return G_MAXUINT;
89 }
90
91 /* Punycode bias adaptation algorithm, RFC 3492 section 6.1 */
92 static guint
93 adapt (guint    delta,
94        guint    numpoints,
95        gboolean firsttime)
96 {
97   guint k;
98
99   delta = firsttime ? delta / PUNYCODE_DAMP : delta / 2;
100   delta += delta / numpoints;
101
102   k = 0;
103   while (delta > ((PUNYCODE_BASE - PUNYCODE_TMIN) * PUNYCODE_TMAX) / 2)
104     {
105       delta /= PUNYCODE_BASE - PUNYCODE_TMIN;
106       k += PUNYCODE_BASE;
107     }
108
109   return k + ((PUNYCODE_BASE - PUNYCODE_TMIN + 1) * delta /
110               (delta + PUNYCODE_SKEW));
111 }
112
113 /* Punycode encoder, RFC 3492 section 6.3. The algorithm is
114  * sufficiently bizarre that it's not really worth trying to explain
115  * here.
116  */
117 static gboolean
118 punycode_encode (const gchar *input_utf8,
119                  gsize        input_utf8_length,
120                  GString     *output)
121 {
122   guint delta, handled_chars, num_basic_chars, bias, j, q, k, t, digit;
123   gunichar n, m, *input;
124   glong input_length;
125   gboolean success = FALSE;
126
127   /* Convert from UTF-8 to Unicode code points */
128   input = g_utf8_to_ucs4 (input_utf8, input_utf8_length, NULL,
129                           &input_length, NULL);
130   if (!input)
131     return FALSE;
132
133   /* Copy basic chars */
134   for (j = num_basic_chars = 0; j < input_length; j++)
135     {
136       if (PUNYCODE_IS_BASIC (input[j]))
137         {
138           g_string_append_c (output, g_ascii_tolower (input[j]));
139           num_basic_chars++;
140         }
141     }
142   if (num_basic_chars)
143     g_string_append_c (output, '-');
144
145   handled_chars = num_basic_chars;
146
147   /* Encode non-basic chars */
148   delta = 0;
149   bias = PUNYCODE_INITIAL_BIAS;
150   n = PUNYCODE_INITIAL_N;
151   while (handled_chars < input_length)
152     {
153       /* let m = the minimum {non-basic} code point >= n in the input */
154       for (m = G_MAXUINT, j = 0; j < input_length; j++)
155         {
156           if (input[j] >= n && input[j] < m)
157             m = input[j];
158         }
159
160       if (m - n > (G_MAXUINT - delta) / (handled_chars + 1))
161         goto fail;
162       delta += (m - n) * (handled_chars + 1);
163       n = m;
164
165       for (j = 0; j < input_length; j++)
166         {
167           if (input[j] < n)
168             {
169               if (++delta == 0)
170                 goto fail;
171             }
172           else if (input[j] == n)
173             {
174               q = delta;
175               for (k = PUNYCODE_BASE; ; k += PUNYCODE_BASE)
176                 {
177                   if (k <= bias)
178                     t = PUNYCODE_TMIN;
179                   else if (k >= bias + PUNYCODE_TMAX)
180                     t = PUNYCODE_TMAX;
181                   else
182                     t = k - bias;
183                   if (q < t)
184                     break;
185                   digit = t + (q - t) % (PUNYCODE_BASE - t);
186                   g_string_append_c (output, encode_digit (digit));
187                   q = (q - t) / (PUNYCODE_BASE - t);
188                 }
189
190               g_string_append_c (output, encode_digit (q));
191               bias = adapt (delta, handled_chars + 1, handled_chars == num_basic_chars);
192               delta = 0;
193               handled_chars++;
194             }
195         }
196
197       delta++;
198       n++;
199     }
200
201   success = TRUE;
202
203  fail:
204   g_free (input);
205   return success;
206 }
207
208 /* From RFC 3454, Table B.1 */
209 #define idna_is_junk(ch) ((ch) == 0x00AD || (ch) == 0x1806 || (ch) == 0x200B || (ch) == 0x2060 || (ch) == 0xFEFF || (ch) == 0x034F || (ch) == 0x180B || (ch) == 0x180C || (ch) == 0x180D || (ch) == 0x200C || (ch) == 0x200D || ((ch) >= 0xFE00 && (ch) <= 0xFE0F))
210
211 /* Scan @str for "junk" and return a cleaned-up string if any junk
212  * is found. Else return %NULL.
213  */
214 static gchar *
215 remove_junk (const gchar *str,
216              gint         len)
217 {
218   GString *cleaned = NULL;
219   const gchar *p;
220   gunichar ch;
221
222   for (p = str; len == -1 ? *p : p < str + len; p = g_utf8_next_char (p))
223     {
224       ch = g_utf8_get_char (p);
225       if (idna_is_junk (ch))
226         {
227           if (!cleaned)
228             {
229               cleaned = g_string_new (NULL);
230               g_string_append_len (cleaned, str, p - str);
231             }
232         }
233       else if (cleaned)
234         g_string_append_unichar (cleaned, ch);
235     }
236
237   if (cleaned)
238     return g_string_free (cleaned, FALSE);
239   else
240     return NULL;
241 }
242
243 static inline gboolean
244 contains_uppercase_letters (const gchar *str,
245                             gint         len)
246 {
247   const gchar *p;
248
249   for (p = str; len == -1 ? *p : p < str + len; p = g_utf8_next_char (p))
250     {
251       if (g_unichar_isupper (g_utf8_get_char (p)))
252         return TRUE;
253     }
254   return FALSE;
255 }
256
257 static inline gboolean
258 contains_non_ascii (const gchar *str,
259                     gint         len)
260 {
261   const gchar *p;
262
263   for (p = str; len == -1 ? *p : p < str + len; p++)
264     {
265       if ((guchar)*p > 0x80)
266         return TRUE;
267     }
268   return FALSE;
269 }
270
271 /* RFC 3454, Appendix C. ish. */
272 static inline gboolean
273 idna_is_prohibited (gunichar ch)
274 {
275   switch (g_unichar_type (ch))
276     {
277     case G_UNICODE_CONTROL:
278     case G_UNICODE_FORMAT:
279     case G_UNICODE_UNASSIGNED:
280     case G_UNICODE_PRIVATE_USE:
281     case G_UNICODE_SURROGATE:
282     case G_UNICODE_LINE_SEPARATOR:
283     case G_UNICODE_PARAGRAPH_SEPARATOR:
284     case G_UNICODE_SPACE_SEPARATOR:
285       return TRUE;
286
287     case G_UNICODE_OTHER_SYMBOL:
288       if (ch == 0xFFFC || ch == 0xFFFD ||
289           (ch >= 0x2FF0 && ch <= 0x2FFB))
290         return TRUE;
291       return FALSE;
292
293     case G_UNICODE_NON_SPACING_MARK:
294       if (ch == 0x0340 || ch == 0x0341)
295         return TRUE;
296       return FALSE;
297
298     default:
299       return FALSE;
300     }
301 }
302
303 /* RFC 3491 IDN cleanup algorithm. */
304 static gchar *
305 nameprep (const gchar *hostname,
306           gint         len)
307 {
308   gchar *name, *tmp = NULL, *p;
309
310   /* It would be nice if we could do this without repeatedly
311    * allocating strings and converting back and forth between
312    * gunichars and UTF-8... The code does at least avoid doing most of
313    * the sub-operations when they would just be equivalent to a
314    * g_strdup().
315    */
316
317   /* Remove presentation-only characters */
318   name = remove_junk (hostname, len);
319   if (name)
320     {
321       tmp = name;
322       len = -1;
323     }
324   else
325     name = (gchar *)hostname;
326
327   /* Convert to lowercase */
328   if (contains_uppercase_letters (name, len))
329     {
330       name = g_utf8_strdown (name, len);
331       g_free (tmp);
332       tmp = name;
333       len = -1;
334     }
335
336   /* If there are no UTF8 characters, we're done. */
337   if (!contains_non_ascii (name, len))
338     {
339       if (name == (gchar *)hostname)
340         return len == -1 ? g_strdup (hostname) : g_strndup (hostname, len);
341       else
342         return name;
343     }
344
345   /* Normalize */
346   name = g_utf8_normalize (name, len, G_NORMALIZE_NFKC);
347   g_free (tmp);
348   tmp = name;
349
350   if (!name)
351     return NULL;
352
353   /* KC normalization may have created more capital letters (eg,
354    * angstrom -> capital A with ring). So we have to lowercasify a
355    * second time. (This is more-or-less how the nameprep algorithm
356    * does it. If tolower(nfkc(tolower(X))) is guaranteed to be the
357    * same as tolower(nfkc(X)), then we could skip the first tolower,
358    * but I'm not sure it is.)
359    */
360   if (contains_uppercase_letters (name, -1))
361     {
362       name = g_utf8_strdown (name, -1);
363       g_free (tmp);
364       tmp = name;
365     }
366
367   /* Check for prohibited characters */
368   for (p = name; *p; p = g_utf8_next_char (p))
369     {
370       if (idna_is_prohibited (g_utf8_get_char (p)))
371         {
372           name = NULL;
373           g_free (tmp);
374           goto done;
375         }
376     }
377
378   /* FIXME: We're supposed to verify certain constraints on bidi
379    * characters, but glib does not appear to have that information.
380    */
381
382  done:
383   return name;
384 }
385
386 /**
387  * g_hostname_to_ascii:
388  * @hostname: a valid UTF-8 or ASCII hostname
389  *
390  * Converts @hostname to its canonical ASCII form; an ASCII-only
391  * string containing no uppercase letters and not ending with a
392  * trailing dot.
393  *
394  * Return value: an ASCII hostname, which must be freed, or %NULL if
395  * @hostname is in some way invalid.
396  *
397  * Since: 2.22
398  **/
399 gchar *
400 g_hostname_to_ascii (const gchar *hostname)
401 {
402   gchar *name, *label, *p;
403   GString *out;
404   gssize llen, oldlen;
405   gboolean unicode;
406
407   label = name = nameprep (hostname, -1);
408   if (!name)
409     return NULL;
410
411   out = g_string_new (NULL);
412
413   do
414     {
415       unicode = FALSE;
416       for (p = label; *p && *p != '.'; p++)
417         {
418           if ((guchar)*p > 0x80)
419             unicode = TRUE;
420         }
421
422       oldlen = out->len;
423       llen = p - label;
424       if (unicode)
425         {
426           if (!strncmp (label, IDNA_ACE_PREFIX, IDNA_ACE_PREFIX_LEN))
427             goto fail;
428
429           g_string_append (out, IDNA_ACE_PREFIX);
430           if (!punycode_encode (label, llen, out))
431             goto fail;
432         }
433       else
434         g_string_append_len (out, label, llen);
435
436       if (out->len - oldlen > 63)
437         goto fail;
438
439       label += llen;
440       if (*label && *++label)
441         g_string_append_c (out, '.');
442     }
443   while (*label);
444
445   g_free (name);
446   return g_string_free (out, FALSE);
447
448  fail:
449   g_free (name);
450   g_string_free (out, TRUE);
451   return NULL;
452 }
453
454 /**
455  * g_hostname_is_non_ascii:
456  * @hostname: a hostname
457  *
458  * Tests if @hostname contains Unicode characters. If this returns
459  * %TRUE, you need to encode the hostname with g_hostname_to_ascii()
460  * before using it in non-IDN-aware contexts.
461  *
462  * Note that a hostname might contain a mix of encoded and unencoded
463  * segments, and so it is possible for g_hostname_is_non_ascii() and
464  * g_hostname_is_ascii_encoded() to both return %TRUE for a name.
465  *
466  * Return value: %TRUE if @hostname contains any non-ASCII characters
467  *
468  * Since: 2.22
469  **/
470 gboolean
471 g_hostname_is_non_ascii (const gchar *hostname)
472 {
473   return contains_non_ascii (hostname, -1);
474 }
475
476 /* Punycode decoder, RFC 3492 section 6.2. As with punycode_encode(),
477  * read the RFC if you want to understand what this is actually doing.
478  */
479 static gboolean
480 punycode_decode (const gchar *input,
481                  gsize        input_length,
482                  GString     *output)
483 {
484   GArray *output_chars;
485   gunichar n;
486   guint i, bias;
487   guint oldi, w, k, digit, t;
488   const gchar *split;
489
490   n = PUNYCODE_INITIAL_N;
491   i = 0;
492   bias = PUNYCODE_INITIAL_BIAS;
493
494   split = input + input_length - 1;
495   while (split > input && *split != '-')
496     split--;
497   if (split > input)
498     {
499       output_chars = g_array_sized_new (FALSE, FALSE, sizeof (gunichar),
500                                         split - input);
501       input_length -= (split - input) + 1;
502       while (input < split)
503         {
504           gunichar ch = (gunichar)*input++;
505           if (!PUNYCODE_IS_BASIC (ch))
506             goto fail;
507           g_array_append_val (output_chars, ch);
508         }
509       input++;
510     }
511   else
512     output_chars = g_array_new (FALSE, FALSE, sizeof (gunichar));
513
514   while (input_length)
515     {
516       oldi = i;
517       w = 1;
518       for (k = PUNYCODE_BASE; ; k += PUNYCODE_BASE)
519         {
520           if (!input_length--)
521             goto fail;
522           digit = decode_digit (*input++);
523           if (digit >= PUNYCODE_BASE)
524             goto fail;
525           if (digit > (G_MAXUINT - i) / w)
526             goto fail;
527           i += digit * w;
528           if (k <= bias)
529             t = PUNYCODE_TMIN;
530           else if (k >= bias + PUNYCODE_TMAX)
531             t = PUNYCODE_TMAX;
532           else
533             t = k - bias;
534           if (digit < t)
535             break;
536           if (w > G_MAXUINT / (PUNYCODE_BASE - t))
537             goto fail;
538           w *= (PUNYCODE_BASE - t);
539         }
540
541       bias = adapt (i - oldi, output_chars->len + 1, oldi == 0);
542
543       if (i / (output_chars->len + 1) > G_MAXUINT - n)
544         goto fail;
545       n += i / (output_chars->len + 1);
546       i %= (output_chars->len + 1);
547
548       g_array_insert_val (output_chars, i++, n);
549     }
550
551   for (i = 0; i < output_chars->len; i++)
552     g_string_append_unichar (output, g_array_index (output_chars, gunichar, i));
553   g_array_free (output_chars, TRUE);
554   return TRUE;
555
556  fail:
557   g_array_free (output_chars, TRUE);
558   return FALSE;
559 }
560
561 /**
562  * g_hostname_to_unicode:
563  * @hostname: a valid UTF-8 or ASCII hostname
564  *
565  * Converts @hostname to its canonical presentation form; a UTF-8
566  * string in Unicode normalization form C, containing no uppercase
567  * letters, no forbidden characters, and no ASCII-encoded segments,
568  * and not ending with a trailing dot.
569  *
570  * Of course if @hostname is not an internationalized hostname, then
571  * the canonical presentation form will be entirely ASCII.
572  *
573  * Return value: a UTF-8 hostname, which must be freed, or %NULL if
574  * @hostname is in some way invalid.
575  *
576  * Since: 2.22
577  **/
578 gchar *
579 g_hostname_to_unicode (const gchar *hostname)
580 {
581   GString *out;
582   gssize llen;
583
584   out = g_string_new (NULL);
585
586   do
587     {
588       llen = strcspn (hostname, ".");
589       if (!g_ascii_strncasecmp (hostname, IDNA_ACE_PREFIX, IDNA_ACE_PREFIX_LEN))
590         {
591           hostname += IDNA_ACE_PREFIX_LEN;
592           llen -= IDNA_ACE_PREFIX_LEN;
593           if (!punycode_decode (hostname, llen, out))
594             {
595               g_string_free (out, TRUE);
596               return NULL;
597             }
598         }
599       else
600         {
601           gchar *canonicalized = nameprep (hostname, llen);
602
603           if (!canonicalized)
604             {
605               g_string_free (out, TRUE);
606               return NULL;
607             }
608           g_string_append (out, canonicalized);
609           g_free (canonicalized);
610         }
611
612       hostname += llen;
613       if (*hostname && *++hostname)
614         g_string_append_c (out, '.');
615     }
616   while (*hostname);
617
618   return g_string_free (out, FALSE);
619 }
620
621 /**
622  * g_hostname_is_ascii_encoded:
623  * @hostname: a hostname
624  *
625  * Tests if @hostname contains segments with an ASCII-compatible
626  * encoding of an Internationalized Domain Name. If this returns
627  * %TRUE, you should decode the hostname with g_hostname_to_unicode()
628  * before displaying it to the user.
629  *
630  * Note that a hostname might contain a mix of encoded and unencoded
631  * segments, and so it is possible for g_hostname_is_non_ascii() and
632  * g_hostname_is_ascii_encoded() to both return %TRUE for a name.
633  *
634  * Return value: %TRUE if @hostname contains any ASCII-encoded
635  * segments.
636  *
637  * Since: 2.22
638  **/
639 gboolean
640 g_hostname_is_ascii_encoded (const gchar *hostname)
641 {
642   while (1)
643     {
644       if (!g_ascii_strncasecmp (hostname, IDNA_ACE_PREFIX, IDNA_ACE_PREFIX_LEN))
645         return TRUE;
646       hostname = strchr (hostname, '.');
647       if (!hostname++)
648         return FALSE;
649     }
650 }
651
652 /**
653  * g_hostname_is_ip_address:
654  * @hostname: a hostname (or IP address in string form)
655  *
656  * Tests if @hostname is the string form of an IPv4 or IPv6 address.
657  * (Eg, "192.168.0.1".)
658  *
659  * Return value: %TRUE if @hostname is an IP address
660  *
661  * Since: 2.22
662  **/
663 gboolean
664 g_hostname_is_ip_address (const gchar *hostname)
665 {
666   gchar *p, *end;
667   gint nsegments, octet;
668
669   /* On Linux we could implement this using inet_pton, but the Windows
670    * equivalent of that requires linking against winsock, so we just
671    * figure this out ourselves. Tested by tests/hostutils.c.
672    */
673
674   p = (char *)hostname;
675
676   if (strchr (p, ':'))
677     {
678       gboolean skipped;
679
680       /* If it contains a ':', it's an IPv6 address (assuming it's an
681        * IP address at all). This consists of eight ':'-separated
682        * segments, each containing a 1-4 digit hex number, except that
683        * optionally: (a) the last two segments can be replaced by an
684        * IPv4 address, and (b) a single span of 1 to 8 "0000" segments
685        * can be replaced with just "::".
686        */
687
688       nsegments = 0;
689       skipped = FALSE;
690       while (*p && nsegments < 8)
691         {
692           /* Each segment after the first must be preceded by a ':'.
693            * (We also handle half of the "string starts with ::" case
694            * here.)
695            */
696           if (p != (char *)hostname || (p[0] == ':' && p[1] == ':'))
697             {
698               if (*p != ':')
699                 return FALSE;
700               p++;
701             }
702
703           /* If there's another ':', it means we're skipping some segments */
704           if (*p == ':' && !skipped)
705             {
706               skipped = TRUE;
707               nsegments++;
708
709               /* Handle the "string ends with ::" case */
710               if (!p[1])
711                 p++;
712
713               continue;
714             }
715
716           /* Read the segment, make sure it's valid. */
717           for (end = p; g_ascii_isxdigit (*end); end++)
718             ;
719           if (end == p || end > p + 4)
720             return FALSE;
721
722           if (*end == '.')
723             {
724               if ((nsegments == 6 && !skipped) || (nsegments <= 6 && skipped))
725                 goto parse_ipv4;
726               else
727                 return FALSE;
728             }
729
730           nsegments++;
731           p = end;
732         }
733
734       return !*p && (nsegments == 8 || skipped);
735     }
736
737  parse_ipv4:
738
739   /* Parse IPv4: N.N.N.N, where each N <= 255 and doesn't have leading 0s. */
740   for (nsegments = 0; nsegments < 4; nsegments++)
741     {
742       if (nsegments != 0)
743         {
744           if (*p != '.')
745             return FALSE;
746           p++;
747         }
748
749       /* Check the segment; a little tricker than the IPv6 case since
750        * we can't allow extra leading 0s, and we can't assume that all
751        * strings of valid length are within range.
752        */
753       octet = 0;
754       if (*p == '0')
755         end = p + 1;
756       else
757         {
758           for (end = p; g_ascii_isdigit (*end); end++)
759             octet = 10 * octet + (*end - '0');
760         }
761       if (end == p || end > p + 3 || octet > 255)
762         return FALSE;
763
764       p = end;
765     }
766
767   /* If there's nothing left to parse, then it's ok. */
768   return !*p;
769 }