#include <glib.h>
#include <string.h>

#define IDNA_ACE_PREFIX     "xn--"
#define IDNA_ACE_PREFIX_LEN 4

/* Punycode constants, from RFC 3492. */

#define PUNYCODE_BASE          36
#define PUNYCODE_TMIN           1
#define PUNYCODE_TMAX          26
#define PUNYCODE_SKEW          38
#define PUNYCODE_DAMP         700
#define PUNYCODE_INITIAL_BIAS  72
#define PUNYCODE_INITIAL_N   0x80

#define PUNYCODE_IS_BASIC(cp) ((guint)(cp) < 0x80)

/* Encode/decode a single base-36 digit */
static inline char
encode_digit (guint dig)
{
  if (dig < 26)
    return dig + 'a';
  else
    return dig - 26 + '0';
}

static inline guint
decode_digit (char dig)
{
  if (dig >= 'A' && dig <= 'Z')
    return dig - 'A';
  else if (dig >= 'a' && dig <= 'z')
    return dig - 'a';
  else if (dig >= '0' && dig <= '9')
    return dig - '0' + 26;
  else
    return G_MAXUINT;
}

/* Punycode bias adaptation algorithm, RFC 3492 section 6.1 */
static guint
adapt (guint delta, guint numpoints, gboolean firsttime)
{
  guint k;

  delta = firsttime ? delta / PUNYCODE_DAMP : delta / 2;
  delta += delta / numpoints;

  k = 0;
  while (delta > ((PUNYCODE_BASE - PUNYCODE_TMIN) * PUNYCODE_TMAX) / 2)
    {
      delta /= PUNYCODE_BASE - PUNYCODE_TMIN;
      k += PUNYCODE_BASE;
    }

  return k + ((PUNYCODE_BASE - PUNYCODE_TMIN + 1) * delta /
	      (delta + PUNYCODE_SKEW));
}

/* Punycode encoder, RFC 3492 section 6.3. The algorithm is
 * sufficiently bizarre that it's not really worth trying to explain
 * here.
 */
static gboolean
punycode_encode (const char *input_utf8, gsize input_utf8_length,
		 GString *output)
{
  guint delta, handled_chars, num_basic_chars, bias, j, q, k, t, digit;
  gunichar n, m, *input;
  glong input_length;
  gboolean success = FALSE;

  /* Convert from UTF-8 to Unicode code points */
  input = g_utf8_to_ucs4 (input_utf8, input_utf8_length, NULL,
			  &input_length, NULL);
  if (!input)
    return FALSE;

  /* Copy basic chars */
  for (j = num_basic_chars = 0; j < input_length; j++)
    {
      if (PUNYCODE_IS_BASIC (input[j]))
	{
	  g_string_append_c (output, g_ascii_tolower (input[j]));
	  num_basic_chars++;
	}
    }
  if (num_basic_chars)
    g_string_append_c (output, '-');

  handled_chars = num_basic_chars;

  /* Encode non-basic chars */
  delta = 0;
  bias = PUNYCODE_INITIAL_BIAS;
  n = PUNYCODE_INITIAL_N;
  while (handled_chars < input_length)
    {
      /* let m = the minimum {non-basic} code point >= n in the input */
      for (m = G_MAXUINT, j = 0; j < input_length; j++)
	{
	  if (input[j] >= n && input[j] < m)
	    m = input[j];
	}

      if (m - n > (G_MAXUINT - delta) / (handled_chars + 1))
	goto fail;
      delta += (m - n) * (handled_chars + 1);
      n = m;

      for (j = 0; j < input_length; j++)
	{
	  if (input[j] < n)
	    {
	      if (++delta == 0)
		goto fail;
	    }
	  else if (input[j] == n)
	    {
	      q = delta;
	      for (k = PUNYCODE_BASE; ; k += PUNYCODE_BASE)
		{
		  if (k <= bias)
		    t = PUNYCODE_TMIN;
		  else if (k >= bias + PUNYCODE_TMAX)
		    t = PUNYCODE_TMAX;
		  else
		    t = k - bias;
		  if (q < t)
		    break;
		  digit = t + (q - t) % (PUNYCODE_BASE - t);
		  g_string_append_c (output, encode_digit (digit));
		  q = (q - t) / (PUNYCODE_BASE - t);
		}

	      g_string_append_c (output, encode_digit (q));
	      bias = adapt (delta, handled_chars + 1, handled_chars == num_basic_chars);
	      delta = 0;
	      handled_chars++;
	    }
	}

      delta++;
      n++;
    }

  success = TRUE;

 fail:
  g_free (input);
  return success;
}

/* From RFC 3454, Table B.1 */
#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))

/* Scan @str for "junk" and return a cleaned-up string if any junk
 * is found. Else return %NULL.
 */
static char *
remove_junk (const char *str)
{
  GString *cleaned = NULL;
  const char *p;
  gunichar ch;

  for (p = str; *p; p = g_utf8_next_char (p))
    {
      ch = g_utf8_get_char (p);
      if (idna_is_junk (ch))
	{
	  if (!cleaned)
	    {
	      cleaned = g_string_new (NULL);
	      g_string_append_len (cleaned, str, p - str);
	    }
	}
      else if (cleaned)
	g_string_append_unichar (cleaned, ch);
    }

  if (cleaned)
    return g_string_free (cleaned, FALSE);
  else
    return NULL;
}

static inline gboolean
contains_uppercase_letters (const char *str)
{
  const char *p;

  for (p = str; *p; p = g_utf8_next_char (p))
    {
      if (g_unichar_isupper (g_utf8_get_char (p)))
	return TRUE;
    }
  return FALSE;
}

/* RFC 3454, Appendix C. ish. */
static inline gboolean
idna_is_prohibited (gunichar ch)
{
  switch (g_unichar_type (ch))
    {
    case G_UNICODE_CONTROL:
    case G_UNICODE_FORMAT:
    case G_UNICODE_UNASSIGNED:
    case G_UNICODE_PRIVATE_USE:
    case G_UNICODE_SURROGATE:
    case G_UNICODE_LINE_SEPARATOR:
    case G_UNICODE_PARAGRAPH_SEPARATOR:
    case G_UNICODE_SPACE_SEPARATOR:
      return TRUE;

    case G_UNICODE_OTHER_SYMBOL:
      if (ch == 0xFFFC || ch == 0xFFFD ||
	  (ch >= 0x2FF0 && ch <= 0x2FFB))
	return TRUE;
      return FALSE;

    case G_UNICODE_NON_SPACING_MARK:
      if (ch == 0x0340 || ch == 0x0341)
	return TRUE;
      return FALSE;

    default:
      return FALSE;
    }
}

/* RFC 3491 IDN cleanup algorithm */
static char *
nameprep (const char *hostname)
{
  char *cleaned, *lower1 = NULL, *normalized, *lower2 = NULL;
  char *str, *p;

  /* It would be nice if we could do this without repeatedly
   * allocating strings and converting back and forth between
   * gunichars and UTF-8...
   */

  str = (char *)hostname;

  /* Remove presentation-only characters */
  cleaned = remove_junk (str);
  if (cleaned)
    str = cleaned;

  /* Convert to lowercase */
  if (contains_uppercase_letters (str))
    str = lower1 = g_utf8_strdown (str, -1);

  /* Normalize */
  str = normalized = g_utf8_normalize (str, -1, G_NORMALIZE_NFKC);

  /* KC normalization may have created more capital letters (eg,
   * angstrom -> capital A with ring). So we have to lowercasify a
   * second time.
   */
  if (contains_uppercase_letters (str))
    str = lower2 = g_utf8_strdown (str, -1);

  /* Check for prohibited characters */
  for (p = str; *p; p = g_utf8_next_char (p))
    {
      if (idna_is_prohibited (g_utf8_get_char (p)))
	{
	  str = NULL;
	  goto done;
	}
    }

  /* FIXME: We're supposed to verify certain constraints on bidi
   * characters, but glib does not appear to have that information.
   */

 done:
  g_free (cleaned);
  g_free (lower1);
  if (str != normalized)
    g_free (normalized);
  if (str != lower2)
    g_free (lower2);

  return str;
}

/**
 * g_hostname_to_ascii:
 * @hostname: a UTF-8 hostname
 *
 * Encodes @hostname according to the <literal>ToASCII</literal>
 * operation of RFC 3490, returning an ASCII encoding of the hostname
 * that can be passed to the resolver. If @hostname is already fully
 * ASCII, it will be returned more-or-less unchanged.
 *
 * Return value: an ASCII hostname, which must be freed, or %NULL if
 * @hostname is in some way invalid.
 **/
char *
g_hostname_to_ascii (const char *hostname)
{
  char *name, *label;
  GString *out;
  gssize llen, oldlen;
  const char *p;
  gboolean unicode;

  out = g_string_new (NULL);
  name = label = nameprep (hostname);

  do
    {
      unicode = FALSE;
      for (p = label; *p && *p != '.'; p++)
	{
	  if ((guchar)*p > 0x80)
	    unicode = TRUE;
	}

      oldlen = out->len;
      llen = p - label;
      if (unicode)
	{
	  g_string_append (out, IDNA_ACE_PREFIX);
	  if (!punycode_encode (label, llen, out))
	    goto fail;
	}
      else
	{
	  if (llen >= IDNA_ACE_PREFIX_LEN &&
	      !g_ascii_strncasecmp (label, IDNA_ACE_PREFIX, IDNA_ACE_PREFIX_LEN))
	    goto fail;
	  g_string_append_len (out, label, llen);
	}

      if (out->len - oldlen > 63)
	goto fail;

      label += llen;
      if (*label)
	{
	  g_string_append_c (out, '.');
	  label++;
	}
    }
  while (*label);

  g_free (name);
  return g_string_free (out, FALSE);

 fail:
  g_free (name);
  g_string_free (out, TRUE);
  return NULL;
}

/**
 * g_hostname_needs_to_ascii:
 * @hostname: a hostname
 *
 * Tests if @hostname contains Unicode characters, such that it needs
 * to be encoded with g_hostname_to_ascii() before being passed to the
 * resolver.
 *
 * Return value: %TRUE if @hostname contains any non-ASCII characters
 **/
gboolean
g_hostname_needs_to_ascii (const char *hostname)
{
  while (*hostname)
    {
      if ((guchar)*hostname > 0x80)
	return TRUE;
    }
  return FALSE;
}

/* Punycode decoder, RFC 3492 section 6.2. As with punycode_encode(),
 * read the RFC if you want to understand what this is actually doing.
 */
static gboolean
punycode_decode (const char *input, gsize input_length, GString *output)
{
  GArray *output_chars;
  gunichar n;
  guint i, bias;
  guint oldi, w, k, digit, t;
  const char *split;

  n = PUNYCODE_INITIAL_N;
  i = 0;
  bias = PUNYCODE_INITIAL_BIAS;

  split = input + input_length - 1;
  while (split > input && *split != '-')
    split--;
  if (split > input)
    {
      output_chars = g_array_sized_new (FALSE, FALSE, sizeof (gunichar),
					split - input);
      input_length -= (split - input) + 1;
      while (input < split)
	{
	  gunichar ch = (gunichar)*input++;
	  if (!PUNYCODE_IS_BASIC (ch))
	    goto fail;
	  g_array_append_val (output_chars, ch);
	}
      input++;
    }
  else
    output_chars = g_array_new (FALSE, FALSE, sizeof (gunichar));

  while (input_length)
    {
      oldi = i;
      w = 1;
      for (k = PUNYCODE_BASE; ; k += PUNYCODE_BASE)
	{
	  if (!input_length--)
	    goto fail;
	  digit = decode_digit (*input++);
	  if (digit >= PUNYCODE_BASE)
	    goto fail;
	  if (digit > (G_MAXUINT - i) / w)
	    goto fail;
	  i += digit * w;
	  if (k <= bias)
	    t = PUNYCODE_TMIN;
	  else if (k >= bias + PUNYCODE_TMAX)
	    t = PUNYCODE_TMAX;
	  else
	    t = k - bias;
	  if (digit < t)
	    break;
	  if (w > G_MAXUINT / (PUNYCODE_BASE - t))
	    goto fail;
	  w *= (PUNYCODE_BASE - t);
	}

      bias = adapt (i - oldi, output_chars->len + 1, oldi == 0);

      if (i / (output_chars->len + 1) > G_MAXUINT - n)
	goto fail;
      n += i / (output_chars->len + 1);
      i %= (output_chars->len + 1);

      g_array_insert_val (output_chars, i++, n);
    }

  for (i = 0; i < output_chars->len; i++)
    g_string_append_unichar (output, g_array_index (output_chars, gunichar, i));
  g_array_free (output_chars, TRUE);
  return TRUE;

 fail:
  g_array_free (output_chars, TRUE);
  return FALSE;
}

/**
 * g_hostname_to_unicode:
 * @hostname: an ASCII hostname (possibly IDNA-encoded)
 *
 * Decodes @hostname according to the <literal>ToUnicode</literal>
 * operation of RFC 3490, returning a UTF-8 equivalent that can be
 * shown to the user. If @hostname is not an IDNA-encoded name, it
 * will be returned more-or-less unchanged.
 *
 * Return value: a UTF-8 hostname, which must be freed, or %NULL if
 * @hostname is in some way invalid.
 **/
char *
g_hostname_to_unicode (const char *hostname)
{
  GString *out;
  gssize llen;

  out = g_string_new (NULL);

  do
    {
      llen = strcspn (hostname, ".");
      if (!g_ascii_strncasecmp (hostname, IDNA_ACE_PREFIX, IDNA_ACE_PREFIX_LEN))
	{
	  hostname += IDNA_ACE_PREFIX_LEN;
	  llen -= IDNA_ACE_PREFIX_LEN;
	  if (!punycode_decode (hostname, llen, out))
	    {
	      g_string_free (out, TRUE);
	      return NULL;
	    }
	}
      else
	g_string_append_len (out, hostname, llen);

      hostname += llen;
      if (*hostname)
	{
	  g_string_append_c (out, '.');
	  hostname++;
	}
    }
  while (*hostname);

  return g_string_free (out, FALSE);
}

/**
 * g_hostname_needs_to_unicode:
 * @hostname: a hostname
 *
 * Tests if @hostname contains IDNA-encoded labels, such that it needs
 * to be decoded with g_hostname_to_unicode() before being displayed
 * to the user.
 *
 * Return value: %TRUE if @hostname contains any IDNA-encoded labels
 **/
gboolean
g_hostname_needs_to_unicode (const char *hostname)
{
  while (1)
    {
      if (!g_ascii_strncasecmp (hostname, IDNA_ACE_PREFIX, IDNA_ACE_PREFIX_LEN))
	return TRUE;
      hostname = strchr (hostname, '.');
      if (!hostname++)
	return FALSE;
    }
}
