stringprep.c

Go to the documentation of this file.

/* stringprep.c --- Core stringprep implementation.
   Copyright (C) 2002-2024 Simon Josefsson
 
   This file is part of GNU Libidn.
 
   GNU Libidn is free software: you can redistribute it and/or
   modify it under the terms of either:
 
     * the GNU Lesser General Public License as published by the Free
       Software Foundation; either version 3 of the License, or (at
       your option) any later version.
 
   or
 
     * the GNU General Public License as published by the Free
       Software Foundation; either version 2 of the License, or (at
       your option) any later version.
 
   or both in parallel, as here.
 
   GNU Libidn is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.
 
   You should have received copies of the GNU General Public License and
   the GNU Lesser General Public License along with this program.  If
   not, see <https://www.gnu.org/licenses/>. */
 
#ifdef HAVE_CONFIG_H
# include "config.h"
#endif
 
#include <stdlib.h>
#include <string.h>
 
#include "stringprep.h"
 
static int
_compare_table_element (const uint32_t *c, const Stringprep_table_element *e)
{
  if (*c < e->start)
    return -1;
  if (*c > e->end)
    return 1;
  return 0;
}
 
static ssize_t
stringprep_find_character_in_table (uint32_t ucs4,
                                    const Stringprep_table_element *table,
                                    size_t table_size)
{
  /* This is where typical uses of Libidn spends very close to all CPU
     time and causes most cache misses.  One could easily do a binary
     search instead.  Before rewriting this, I want hard evidence this
     slowness is at all relevant in typical applications.  (I don't
     dispute optimization may improve matters significantly, I'm
     mostly interested in having someone give real-world benchmark on
     the impact of libidn.)
     *
     * Answer (Tim Rühsen rockdaboot@gmx.de):
     * Testing the fuzz corpora just once via make check takes ~54 billion CPU cycles.
     * That is almost 20s on my Intel i3 3.1GHz !!!
     * That even makes fuzzing almost useless, eating up CPU cycles for nothing.
     *
     * The bsearch() approach takes ~3 billion CPU cycles.
     * Almost a factor of 20 faster (but still pretty slow).
     * There are still ~2 million calls to bsearch() which make ~30% of CPU time used.
     * Most time is spent in _g_utf8_normalize_wc().
 
     ssize_t i;
 
     for (i = 0; table[i].start || table[i].end; i++)
     if (ucs4 >= table[i].start &&
     ucs4 <= (table[i].end ? table[i].end : table[i].start))
     return i;
   */
 
  const Stringprep_table_element *p =
    bsearch (&ucs4, table, table_size, sizeof (Stringprep_table_element),
             (int (*)(const void *, const void *)) _compare_table_element);
 
  return p ? (p - table) : -1;
}
 
static ssize_t
stringprep_find_string_in_table (uint32_t *ucs4,
                                 size_t ucs4len,
                                 size_t *tablepos,
                                 const Stringprep_table_element *table,
                                 size_t table_size)
{
  size_t j;
  ssize_t pos;
 
  for (j = 0; j < ucs4len; j++)
    if ((pos =
         stringprep_find_character_in_table (ucs4[j], table,
                                             table_size)) != -1)
      {
        if (tablepos)
          *tablepos = pos;
        return j;
      }
 
  return -1;
}
 
static int
stringprep_apply_table_to_string (uint32_t *ucs4,
                                  size_t *ucs4len,
                                  size_t maxucs4len,
                                  const Stringprep_table_element *table,
                                  size_t table_size)
{
  ssize_t pos;
  size_t i, maplen;
  uint32_t *src = ucs4;         /* points to unprocessed data */
  size_t srclen = *ucs4len;     /* length of unprocessed data */
 
  while ((pos = stringprep_find_string_in_table (src, srclen,
                                                 &i, table,
                                                 table_size)) != -1)
    {
      for (maplen = STRINGPREP_MAX_MAP_CHARS;
           maplen > 0 && table[i].map[maplen - 1] == 0; maplen--)
        ;
 
      if (*ucs4len - 1 + maplen >= maxucs4len)
        return STRINGPREP_TOO_SMALL_BUFFER;
 
      memmove (src + pos + maplen, src + pos + 1,
               sizeof (uint32_t) * (srclen - pos - 1));
      memcpy (src + pos, table[i].map, sizeof (uint32_t) * maplen);
      *ucs4len = *ucs4len - 1 + maplen;
      src += pos + maplen;
      srclen -= pos + 1;
    }
 
  return STRINGPREP_OK;
}
 
#define INVERTED(x) ((x) & ((~0UL) >> 1))
#define UNAPPLICAPLEFLAGS(flags, profileflags) \
  ((!INVERTED(profileflags) && !(profileflags & flags) && profileflags) || \
   ( INVERTED(profileflags) && (profileflags & flags)))
 
int
stringprep_4i (uint32_t *ucs4, size_t *len, size_t maxucs4len,
               Stringprep_profile_flags flags,
               const Stringprep_profile *profile)
{
  size_t i, j;
  ssize_t k;
  size_t ucs4len = *len;
  int rc;
 
  for (i = 0; profile[i].operation; i++)
    {
      switch (profile[i].operation)
        {
        case STRINGPREP_NFKC:
          {
            uint32_t *q = 0;
 
            if (UNAPPLICAPLEFLAGS (flags, profile[i].flags))
              break;
 
            if (flags & STRINGPREP_NO_NFKC && !profile[i].flags)
              /* Profile requires NFKC, but callee asked for no NFKC. */
              return STRINGPREP_FLAG_ERROR;
 
            q = stringprep_ucs4_nfkc_normalize (ucs4, ucs4len);
            if (!q)
              return STRINGPREP_NFKC_FAILED;
 
            for (ucs4len = 0; q[ucs4len]; ucs4len++)
              ;
 
            if (ucs4len >= maxucs4len)
              {
                free (q);
                return STRINGPREP_TOO_SMALL_BUFFER;
              }
 
            memcpy (ucs4, q, ucs4len * sizeof (ucs4[0]));
 
            free (q);
          }
          break;
 
        case STRINGPREP_PROHIBIT_TABLE:
          k = stringprep_find_string_in_table (ucs4, ucs4len,
                                               NULL, profile[i].table,
                                               profile[i].table_size);
          if (k != -1)
            return STRINGPREP_CONTAINS_PROHIBITED;
          break;
 
        case STRINGPREP_UNASSIGNED_TABLE:
          if (UNAPPLICAPLEFLAGS (flags, profile[i].flags))
            break;
          if (flags & STRINGPREP_NO_UNASSIGNED)
            {
              k = stringprep_find_string_in_table
                (ucs4, ucs4len, NULL, profile[i].table,
                 profile[i].table_size);
              if (k != -1)
                return STRINGPREP_CONTAINS_UNASSIGNED;
            }
          break;
 
        case STRINGPREP_MAP_TABLE:
          if (UNAPPLICAPLEFLAGS (flags, profile[i].flags))
            break;
          rc = stringprep_apply_table_to_string
            (ucs4, &ucs4len, maxucs4len, profile[i].table,
             profile[i].table_size);
          if (rc != STRINGPREP_OK)
            return rc;
          break;
 
        case STRINGPREP_BIDI_PROHIBIT_TABLE:
        case STRINGPREP_BIDI_RAL_TABLE:
        case STRINGPREP_BIDI_L_TABLE:
          break;
 
        case STRINGPREP_BIDI:
          {
            int done_prohibited = 0;
            int done_ral = 0;
            int done_l = 0;
            size_t contains_ral = SIZE_MAX;
            size_t contains_l = SIZE_MAX;
 
            for (j = 0; profile[j].operation; j++)
              if (profile[j].operation == STRINGPREP_BIDI_PROHIBIT_TABLE)
                {
                  done_prohibited = 1;
                  k = stringprep_find_string_in_table (ucs4, ucs4len,
                                                       NULL,
                                                       profile[j].table,
                                                       profile[j].table_size);
                  if (k != -1)
                    return STRINGPREP_BIDI_CONTAINS_PROHIBITED;
                }
              else if (profile[j].operation == STRINGPREP_BIDI_RAL_TABLE)
                {
                  done_ral = 1;
                  if (stringprep_find_string_in_table
                      (ucs4, ucs4len, NULL, profile[j].table,
                       profile[j].table_size) != -1)
                    contains_ral = j;
                }
              else if (profile[j].operation == STRINGPREP_BIDI_L_TABLE)
                {
                  done_l = 1;
                  if (stringprep_find_string_in_table
                      (ucs4, ucs4len, NULL, profile[j].table,
                       profile[j].table_size) != -1)
                    contains_l = j;
                }
 
            if (!done_prohibited || !done_ral || !done_l)
              return STRINGPREP_PROFILE_ERROR;
 
            if (contains_ral != SIZE_MAX && contains_l != SIZE_MAX)
              return STRINGPREP_BIDI_BOTH_L_AND_RAL;
 
            if (contains_ral != SIZE_MAX)
              {
                if (!(stringprep_find_character_in_table
                      (ucs4[0], profile[contains_ral].table,
                       profile[contains_ral].table_size) != -1
                      &&
                      stringprep_find_character_in_table (ucs4[ucs4len - 1],
                                                          profile
                                                          [contains_ral].table,
                                                          profile
                                                          [contains_ral].table_size)
                      != -1))
                  return STRINGPREP_BIDI_LEADTRAIL_NOT_RAL;
              }
          }
          break;
 
        default:
          return STRINGPREP_PROFILE_ERROR;
          break;
        }
    }
 
  *len = ucs4len;
 
  return STRINGPREP_OK;
}
 
static int
stringprep_4zi_1 (uint32_t *ucs4, size_t ucs4len, size_t maxucs4len,
                  Stringprep_profile_flags flags,
                  const Stringprep_profile *profile)
{
  int rc;
 
  rc = stringprep_4i (ucs4, &ucs4len, maxucs4len, flags, profile);
  if (rc != STRINGPREP_OK)
    return rc;
 
  if (ucs4len >= maxucs4len)
    return STRINGPREP_TOO_SMALL_BUFFER;
 
  ucs4[ucs4len] = 0;
 
  return STRINGPREP_OK;
}
 
int
stringprep_4zi (uint32_t *ucs4, size_t maxucs4len,
                Stringprep_profile_flags flags,
                const Stringprep_profile *profile)
{
  size_t ucs4len;
 
  for (ucs4len = 0; ucs4len < maxucs4len && ucs4[ucs4len] != 0; ucs4len++)
    ;
 
  return stringprep_4zi_1 (ucs4, ucs4len, maxucs4len, flags, profile);
}
 
int
stringprep (char *in,
            size_t maxlen,
            Stringprep_profile_flags flags, const Stringprep_profile *profile)
{
  int rc;
  char *utf8 = NULL;
  uint32_t *ucs4 = NULL;
  size_t ucs4len, maxucs4len, adducs4len = strlen (in) / 10 + 1;
 
  do
    {
      uint32_t *newp;
 
      free (ucs4);
      ucs4 = stringprep_utf8_to_ucs4 (in, -1, &ucs4len);
      if (ucs4 == NULL)
        return STRINGPREP_ICONV_ERROR;
      maxucs4len = ucs4len + adducs4len;
      newp = realloc (ucs4, maxucs4len * sizeof (uint32_t));
      if (!newp)
        {
          free (ucs4);
          return STRINGPREP_MALLOC_ERROR;
        }
      ucs4 = newp;
 
      rc = stringprep_4i (ucs4, &ucs4len, maxucs4len, flags, profile);
      adducs4len *= 2;
    }
  while (rc == STRINGPREP_TOO_SMALL_BUFFER);
  if (rc != STRINGPREP_OK)
    {
      free (ucs4);
      return rc;
    }
 
  utf8 = stringprep_ucs4_to_utf8 (ucs4, ucs4len, 0, 0);
  free (ucs4);
  if (!utf8)
    return STRINGPREP_ICONV_ERROR;
 
  if (strlen (utf8) >= maxlen)
    {
      free (utf8);
      return STRINGPREP_TOO_SMALL_BUFFER;
    }
 
  strcpy (in, utf8);            /* flawfinder: ignore */
 
  free (utf8);
 
  return STRINGPREP_OK;
}
 
int
stringprep_profile (const char *in,
                    char **out,
                    const char *profile, Stringprep_profile_flags flags)
{
  const Stringprep_profiles *p;
  char *str = NULL;
  size_t len = strlen (in) + 1, addlen = len / 10 + 1;
  int rc;
 
  for (p = &stringprep_profiles[0]; p->name; p++)
    if (strcmp (p->name, profile) == 0)
      break;
 
  if (!p || !p->name || !p->tables)
    return STRINGPREP_UNKNOWN_PROFILE;
 
  do
    {
      free (str);
      str = (char *) malloc (len);
      if (str == NULL)
        return STRINGPREP_MALLOC_ERROR;
 
      strcpy (str, in);
 
      rc = stringprep (str, len, flags, p->tables);
      len += addlen;
      addlen *= 2;
    }
  while (rc == STRINGPREP_TOO_SMALL_BUFFER);
 
  if (rc == STRINGPREP_OK)
    *out = str;
  else
    free (str);
 
  return rc;
}