7
\$\begingroup\$

I needed a function that would:

  • Decode, and return, the first character in an UTF8 encoded strings
  • Return the length of encoding with the special case that lenght of '\0' must be 0
  • Perfomance are important

I had no special requirement on what to do with invalid sequences so I opted for the following behaviour:

  • The first byte of an invalid sequences is considered as a single "character" (e.g. for the sequence "\xFF\x2F" it would return '\xFF' as value and 1 as length).
  • Overlong encoding are accepted

I wrote the following function:

static uint8_t LEN[] = {1,1,1,1,2,2,3,0};
static uint8_t MSK[] = {0,0,3,4,5,0,0,0};

static int utf8_cp(char *txt, int32_t *ch)
{
  int len = 0;
  int32_t val = 0;
  uint8_t first = (uint8_t)(*txt);

  len = (first > 0) * (1 + ((first & 0xC0) == 0xC0) * LEN[(first >> 3) & 7]);
  val = first & (0xFF >> MSK[len]);

  for (int k=len; k>1; k--) {
    if ((*++txt & 0xC0) != 0x80) {
      val = first;
      len = 1;
      break;
    }
    val = (val << 6) | (*txt & 0x3F);
  }

  *ch = val;
  return len;
}

So that a code like:

char *t; int l; int32_t c;

t = "aàも𫀔";
while(1) {
  l = utf8_cp(t, &c);
  printf("'%s' len:%d cp:0x%05x\n", t, l, c);
  if (*t == 0) break;
  t += l;
} 

Produces:

'aàも𫀔' len:1 cp:0x00061
'àも𫀔' len:2 cp:0x000e0
'も𫀔' len:3 cp:0x03082
'𫀔' len:4 cp:0x2b014
'' len:0 cp:0x00000

To make it faster I thought about unrolling the for loop (but I wonder how much could I gain) and introducing, at the beginning, some if to handle ASCII character (but I fear that branching could be more costly that just making a bunch of operation).

I will appreciate any comment you may have and any suggestion for improvement.

\$\endgroup\$
4
\$\begingroup\$

Rather than use narrow types, use fastest ones

// uint8_t first = (uint8_t)(*txt);
unsigned first = (uint8_t)(*txt);
// or
uint_fast8_t first = (uint8_t)(*txt);

Rather than lookup a value to shift, look up the shifted value.

// static uint8_t MSK[] = {0,0,3,4,5,0,0,0};
//  val = first & (0xFF >> MSK[len]);

static const uint8_t FF_MSK[] = {0xFF >>0, 0xFF >>0, 0xFF >>3, 
    0xFF >>4, 0xFF >>5, 0xFF >>0, 0xFF >>0, 0xFF >>0};
val = first & FF_MSK[len];

Some modern compilers can make additional optimizations if the pointers are known to not overlap - use restrict and const where applicable.

// int utf8_cp(char *txt, int32_t *ch)
int utf8_cp(const char * restrict txt, int32_t *restrict ch)

Coding the companion function would aid in testing for both functions.

int utf8_cp_encode(int32_t *ch, char *txt);

As code does not detect invalid encoding like surrogates, redundant patterns and values above max_Unicode, I see little value in handling only a subset of invalid sequences. Either detect them all (maybe in debug mode) or skip detection.

Suggest doing a 32-byte (or 256-byte) lookup for performance. Profile to find optimal.

// len = (first > 0) * (1 + ((first & 0xC0) == 0xC0) * LEN[(first >> 3) & 7]);
len = (first > 0) * LEN_32[first >> 3];
// or
len = LEN_256[first];

Could extend the above to do one lookup for both the len and val.

\$\endgroup\$
  • \$\begingroup\$ Thank you, chux. I tried to do the bare minimum to allow each invalid encoding as a sequence of 1-byte "character". I could change the test if ((*++txt & 0xC0) != 0x80) in if (*++txt) but this would mean that an invalid sequence would eat up more characters. Is there any portion of code I should look at? \$\endgroup\$ – Remo.D Sep 21 '16 at 17:01
  • \$\begingroup\$ @Remo.D Note: Your code allows some invalid encoding as a sequence of 1-byte, but not all. " Is there any portion of code I should look at?" --> It is work to find where code is wrong - need tests. Step 1 Try utf8_cp() all valid Unicode values, [0-0xD7FF] [E000-10FFFF] and see that they round-trip back to there original value noting the intermediate 1-4 byte UTF8 encoding. Step 2 Use the UTF8 values to mark off a 32-bit flag array considering UTF8 sequence like A or x41 marks off all x41 xx xx xx position. Remaining unmarked values should be detected by your code as invalid. \$\endgroup\$ – chux Sep 21 '16 at 17:57

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.