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