5
\$\begingroup\$

This is the complete rewrite of a function to decode an UTF-8 codepoints and return the encoding length (or 0 if the codepoint is \0). In response to the review of my previous version I decided that I needed a different approach and I should recognize ALL the invalid encodings (as per reviewer suggestion). If an invalid encoding is found, the first byte is returned with length 1.

I found a very good article about decoding UTF-8 by Bjoern Hoehrmann and followed the same approach which is based on the following Finite Automaton:

UTF8 Finite Automaton

I directly coded it in C:

#define fsm
#define fsmGOTO(x)    goto fsm_state_##x
#define fsmSTATE(x)   fsm_state_##x :
#define fsmSTART      

int utf8_cp(char * restrict txt, int32_t * restrict ch)
{
  int len;
  uint8_t *s = (uint8_t *)txt;
  uint8_t first = *s;

  fsm {
    fsmSTART {
      if (*s == 0x00) { *ch = *s;        len = 0; fsmGOTO(end); }
      if (*s <= 0xC1) { *ch = *s;        len = 1; fsmGOTO(end); }
      if (*s <= 0xDF) { *ch = *s & 0x1F; len = 2; fsmGOTO(2);   }
      if (*s == 0xE0) { *ch = *s & 0x0F; len = 3; fsmGOTO(4);   }
      if (*s <= 0xEC) { *ch = *s & 0x0F; len = 3; fsmGOTO(3);   }
      if (*s == 0xED) { *ch = *s & 0x0F; len = 3; fsmGOTO(5);   }
      if (*s <= 0xEF) { *ch = *s & 0x0F; len = 3; fsmGOTO(3);   }
      if (*s == 0xF0) { *ch = *s & 0x07; len = 4; fsmGOTO(6);   }
      if (*s <= 0xF3) { *ch = *s & 0x07; len = 4; fsmGOTO(7);   }
      if (*s == 0xF4) { *ch = *s & 0x07; len = 4; fsmGOTO(8);   }
      fsmGOTO(invalid);
    } 

    fsmSTATE(8) {
      s++; if ( *s < 0x80 || 0x8f < *s) fsmGOTO(invalid);
      *ch = (*ch << 6) | (*s & 0x3F);
      fsmGOTO(3);
    }

    fsmSTATE(7) {
      s++; if ( *s < 0x80 || 0xbf < *s) fsmGOTO(invalid);
      *ch = (*ch << 6) | (*s & 0x3F);
      fsmGOTO(3);
    }

    fsmSTATE(6) {
      s++; if ( *s < 0x90 || 0xbf < *s) fsmGOTO(invalid);
      *ch = (*ch << 6) | (*s & 0x3F);
      fsmGOTO(3);
    }

    fsmSTATE(5) {
      s++; if ( *s < 0x80 || 0x9f < *s) fsmGOTO(invalid);
      *ch = (*ch << 6) | (*s & 0x3F);
      fsmGOTO(2);
    }

    fsmSTATE(4) {
      s++; if ( *s < 0xA0 || 0xbf < *s) fsmGOTO(invalid);
      *ch = (*ch << 6) | (*s & 0x3F);
      fsmGOTO(2);
    }

    fsmSTATE(3) {
      s++; if ( *s < 0x80 || 0xbf < *s) fsmGOTO(invalid);
      *ch = (*ch << 6) | (*s & 0x3F);
      fsmGOTO(2);
    }

    fsmSTATE(2) {
      s++; if ( *s < 0x80 || 0xbf < *s) fsmGOTO(invalid);
      *ch = (*ch << 6) | (*s & 0x3F);
      fsmGOTO(end);
    }

    fsmSTATE(invalid) {*ch = first; len = 1;}

    fsmSTATE(end)   { }
  }
  return len;
}

The code above, not only handles the invalid encondings, it's also much faster (33%) than my previous version!

I also compared my code with one directly based on the original version by Bjoern Hoehrmann (using a table to represent the FSM) and I found them being equally fast but mine being much clearer in terms of understanding how it works.

Any comment, feedback or suggestion is greatly appreciated.

\$\endgroup\$
2
\$\begingroup\$

Overall, this seems like a pretty straightforward implementation of the FSM you show. It's understandable, which is great!

Document What It Is

The only thing is, what if someone reading this has never seen the image of the FSM? You should, at the very least, include a comment with a URL showing where the FSM comes from! Or, if you can easily explain it in words, do that.

Don't Do Nothing

What is the point of the fsm and fsmstart macros? They do nothing. I don't mind that you're starting new scope with each one, but an empty macro seems pointless. You could just as easily use a comment. It would be confusing to someone reading the code for the first time, thinking they did something.

Be Careful With Macros

While we're no the subject of macros... What's the point of the other macros? The fsmSTATE macro saves you no typing at all, and doesn't appear to have any other function. Just use the label directly in your code. The fsmGOTO label saves you a little typing but doesn't really seem all that useful. Macros are known to have a number of dangerous issues, so it's best to avoid them if at all possible.

Don't Use Magic Numbers

What is state 6? State 4? What is the significance of the numbers? Reading the linked page, it sounds like they are character classes or something like that. Would it be possible to have named constants that make this more obvious?

Be Careful With Multiple Statements in a Single Line

You have a lot of places where you've written several statements on the same line, like this:

s++; if ( *s < 0x80 || 0xbf < *s) fsmGOTO(invalid);

This can be problematic for a number of reasons. First, it's difficult to debug. When you're stepping through the code in a debugger, it can be very difficult to tell which statement had what effect. Second, it's hard to read.

\$\endgroup\$
  • \$\begingroup\$ Thanks for you comments. I will surely add more documentation and refer to a version of the FA with descriptive names. The use of the fsmXXX macros is to better convey the structure of the FSM. In this simple case the two macros are empty but I left them for clarity. I'll give a proper look at the other points you mentioned. Thanks again! \$\endgroup\$ – Remo.D Sep 25 '16 at 8:15

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.