6
\$\begingroup\$

You may see full code here (note that the link points to the specific commit).

Language is "clean C" (that is, a subset of C89, C99 and C++98 — it is intended to compile under all of these standards). The code must be portable between x86 and x86_64.

UTF-8 handling implemented based on information here and tested with data in this file.

First and foremost I'm interested in correctness. But I'm a bit worried about the length and readability of the code and its speed (I did not profile this thing yet though, so that particular worry is not motivated). I will accept any comments, including constructive nitpicks.

The function itself:

/*
* *Increments* len_bytes by the number of bytes read.
* Fails on invalid UTF-8 characters.
*/
static int ltsLS_eatutf8char(lts_LoadState * ls, size_t * len_bytes)
{
  unsigned char b = 0;
  signed char expected_length = 0;
  int i = 0;
  const unsigned char * origin = ls->pos;

  /* Check if we have any data in the buffer */
  if (!ltsLS_good(ls) || ltsLS_unread(ls) < 1)
  {
    ls->unread = 0;
    ls->pos = NULL;

    return LUATEXTS_ECLIPPED;
  }

  /* We have at least one byte in the buffer, let's check it out. */
  b = *ls->pos;

  /* We did just eat a byte, no matter what happens next. */
  ++ls->pos;
  --ls->unread;

  /* Get an expected length of a character. */
  expected_length = utf8_char_len[b];

  /* Check if it was a valid first byte. */
  if (expected_length < 1)
  {
    ls->unread = 0;
    ls->pos = NULL;

    return LUATEXTS_EBADUTF8;
  }

  /* If it was a single-byte ASCII character, return right away. */
  if (expected_length == 1)
  {
    *len_bytes += expected_length;

    return LUATEXTS_ESUCCESS;
  }

  /*
  * It was a multi-byte character. Check if we have enough bytes unread.
  * Note that we've eaten one byte already.
  */
  if (ltsLS_unread(ls) + 1 < expected_length)
  {
    ls->unread = 0;
    ls->pos = NULL;

    return LUATEXTS_ECLIPPED; /* Assuming it is buffer's fault. */
  }

  /* Let's eat the rest of characters */
  for (i = 1; i < expected_length; ++i)
  {
    b = *ls->pos;

    /* We did just eat a byte, no matter what happens next. */
    ++ls->pos;
    --ls->unread;

    /* Check if it is a continuation byte */
    if (utf8_char_len[b] != -1)
    {
      ls->unread = 0;
      ls->pos = NULL;

      return LUATEXTS_EBADUTF8;
    }
  }

  /* All bytes are correct, let's check out for overlong forms */
  if (
      expected_length == 2 && (
          (origin[0] & 0xFE) == 0xC0
        )
    )
  {
    ls->unread = 0;
    ls->pos = NULL;

    return LUATEXTS_EBADUTF8;
  }
  else if (
      expected_length == 3 && (
          origin[0] == 0xE0
            && (origin[1] & 0xE0) == 0x80
        )
    )
  {
    ls->unread = 0;
    ls->pos = NULL;

    return LUATEXTS_EBADUTF8;
  }
  else if (
      expected_length == 4 && (
          origin[0] == 0xF0
            && (origin[1] & 0xF0) == 0x80
        )
    )
  {
    ls->unread = 0;
    ls->pos = NULL;

    return LUATEXTS_EBADUTF8;
  }
  else if (
      expected_length == 5 && (
          origin[0] == 0xF8
            && (origin[1] & 0xF8) == 0x80
        )
    )
  {
    ls->unread = 0;
    ls->pos = NULL;

    return LUATEXTS_EBADUTF8;
  }
  else if (
      expected_length == 6 && (
          origin[0] == 0xFC
            && (origin[1] & 0xFC) == 0x80
        )
    )
  {
    ls->unread = 0;
    ls->pos = NULL;

    return LUATEXTS_EBADUTF8;
  }

  /* No overlongs, check for surrogates. */

  if (
      expected_length == 3 && (
          origin[0] == 0xED
            && (origin[1] & 0xE0) == 0xA0
        )
    )
  {
    ls->unread = 0;
    ls->pos = NULL;

    return LUATEXTS_EBADUTF8;
  }

  /*
  * Note: Not checking for U+FFFE or U+FFFF.
  *
  * Chapter 3 of version 3.2 of the Unicode standard, Paragraph C5 says
  * "A process shall not interpret either U+FFFE or U+FFFF as an abstract
  * character", but table 3.1B includes them among
  * the "Legal UTF-8 Byte Sequences".
  *
  * We opt to pass them through.
  */

  /* Phew. All done, the UTF-8 character is valid. */

  *len_bytes += expected_length;

  return LUATEXTS_ESUCCESS;
}

The function relies on this lookup table:

static const signed char utf8_char_len[256] =
{
   1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
   1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
   1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
   1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
   1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
   1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
   1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
   1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
   2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
   2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
   3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
   4,  4,  4,  4,  4,  4,  4,  4,  5,  5,  5,  5,  6,  6,  0,  0
};

The function works on lts_LoadState buffer "stream iterator", which should be prepared by caller. Relevant pieces of code:

typedef struct lts_LoadState
{
  const unsigned char * pos;
  size_t unread;
} lts_LoadState;

static void ltsLS_init(
    lts_LoadState * ls,
    const unsigned char * data,
    size_t len
  )
{
  ls->pos = (len > 0) ? data : NULL;
  ls->unread = len;
}

#define ltsLS_good(ls) \
  ((ls)->pos != NULL)

#define ltsLS_unread(ls) \
  ((ls)->unread)
\$\endgroup\$
  • 2
    \$\begingroup\$ This could be a lot simpler. Compare to the functions pg_utf8_islegal and pg_utf_mblen from PostgreSQL. A nice thing about these functions is that they aren't tangled up in a framework, so they're easier to understand by themselves and easier to reuse. \$\endgroup\$ – Joey Adams Apr 3 '11 at 7:16
  • \$\begingroup\$ @Joey: Ah, where were you when I asked this question... stackoverflow.com/questions/5517205/… :-) \$\endgroup\$ – Alexander Gladysh Apr 3 '11 at 12:16
  • \$\begingroup\$ @Joey: If you will post an answer for the linked question, I'll accept it for the sake of future readers. (I'm not sure that I want to rewrite my code though — too much of wasted work, need to think more about it...) \$\endgroup\$ – Alexander Gladysh Apr 3 '11 at 12:36
  • \$\begingroup\$ For the future readers: here is probably the simplest implementation: bjoern.hoehrmann.de/utf-8/decoder/dfa \$\endgroup\$ – Alexander Gladysh Mar 14 '14 at 5:26
7
\$\begingroup\$

One obvious issue - the longest valid Unicode character is represented by 4 bytes in UTF-8. Although it is possible to extend the logic to 5 or 6 bytes, there is no need since Unicode is a 21-bit codeset.

Be careful about using version 3.2 of the Unicode standard; the current version is 6.0. Granted, they keep them as backwards compatible as possible, but it is as well to use the latest version. Paragraph C5 in 6.0.0 bears no resemblance to the paragraph you quote. The bytes 0xC0, 0xC1, and 0xF5..0xFF cannot appear in valid UTF-8.

In view of that, you can modify your lookup table to:

static const signed char utf8_char_len[256] =
{
   1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
   1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
   1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
   1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
   1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
   1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
   1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
   1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
   0,  0,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
   2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
   3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
   4,  4,  4,  4,  4,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
};

The zeroes for the forbidden bytes will trigger an early exit.

The loadstate structure is odd; you have to have something else that keeps a record of where the start of the buffer is. However, since the code zaps the loadstate on encountering an error, there has to be another place where the information is stored, so maybe it isn't too critical.

A good compiler might well optimize:

  if (expected_length == 1)
  {
      *len_bytes += expected_length;
      return LUATEXTS_ESUCCESS;
  }

so that it is the same as:

  if (expected_length == 1)
  {
      *len_bytes++;
      return LUATEXTS_ESUCCESS;
  }

The overlong and surrogate testing is interesting. Table 3.7 from Chapter 3 of the 6.0.0 Unicode standard lists:

Table 3-7. Well-Formed UTF-8 Byte Sequences
Code Points         First Byte  Second Byte  Third Byte  Fourth Byte
U+0000..U+007F      00..7F
U+0080..U+07FF      C2..DF      80..BF
U+0800..U+0FFF      E0          A0..BF       80..BF
U+1000..U+CFFF      E1..EC      80..BF       80..BF
U+D000..U+D7FF      ED          80..9F       80..BF
U+E000..U+FFFF      EE..EF      80..BF       80..BF
U+10000..U+3FFFF    F0          90..BF       80..BF       80..BF
U+40000..U+FFFFF    F1..F3      80..BF       80..BF       80..BF
U+100000..U+10FFFF  F4          80..8F       80..BF       80..BF

You need to do some extra testing for 0xF4 as the first byte; your code allows through quite a lot of invalid characters. Otherwise, the tests you have do work, allowing through the surrogates, which you test for separately.

The test for the surrogates is incorrect. The bit masking operation is wrong, allowing through many surrogates. I think you could write:

if (expected_length == 3 && (origin[0] == 0xED && (origin[1] & 0xE0) != 0x80))

The conditions for overlong forms and surrogates can be reduced to:

/* All bytes are correct; check out for overlong forms and surrogates */
if ((expected_length == 2 && ((origin[0] &  0xFE) == 0xC0))                      ||
    (expected_length == 3 &&  (origin[0] == 0xE0 && (origin[1] & 0xE0) == 0x80)) ||
    (expected_length == 4 &&  (origin[0] == 0xF0 && (origin[1] & 0xF0) == 0x80)) ||
    (expected_length == 4 &&  (origin[0] == 0xF4 && (origin[1] > 0x8F)))         ||
    (expected_length == 3 &&  (origin[0] == 0xED && (origin[1] & 0xE0) != 0x80)))
{
    ls->unread = 0;
    ls->pos = NULL;
    return LUATEXTS_EBADUTF8;
}

This is vastly shorter and therefore more readable than the original. The near symmetry of the terms is made evident by the layout. It is wider than 80 characters; if that's a problem, I'd shorten the name expected_length (to maybe exp_len).

\$\endgroup\$
  • \$\begingroup\$ @Jonathan: Thank you for in-depth review. I'll leave comments below: \$\endgroup\$ – Alexander Gladysh Apr 3 '11 at 11:57
  • 1
    \$\begingroup\$ 1. On 5 and 6 byte characters. This file cl.cam.ac.uk/~mgk25/ucs/examples/UTF-8-test.txt (which is widely quoted and which I considered as an authoritative source) includes tests for such characters (2.1.5, 2.1.6, 2.2.5, 2.2.6), implying that they are legal. Well, I guess, to make code simpler, I will drop support for them by modifying the lookup table as you suggest. \$\endgroup\$ – Alexander Gladysh Apr 3 '11 at 12:01
  • \$\begingroup\$ 1.1. If someone can suggest a test-suite that I can reuse (directly or as an inspiration), please do: stackoverflow.com/questions/5519315/… \$\endgroup\$ – Alexander Gladysh Apr 3 '11 at 12:02
  • \$\begingroup\$ 2. Regarding U+FFFF and U+FFFE: so, according to 6.0 standard, are they legal or not? What I tried to google up left me confused on that point. \$\endgroup\$ – Alexander Gladysh Apr 3 '11 at 12:05
  • \$\begingroup\$ 3. On loadstate: the function we discuss operates on user-provided read-only string buffer of given length. The lts_LoadState structure is a thin abstraction over this; it can be considered as a half-baked "stream iterator". User knows the start of his buffer, so we don't have to -- reading in reverse direction is not needed or supported. \$\endgroup\$ – Alexander Gladysh Apr 3 '11 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.