Efficient In-Place UTF-16 Unicode Correction with ARM NEON

29 December 2024 · 8 min

Modern-day text in software can be expected to be Unicode. Unicode is stored in two formats: UTF-8 and UTF-16.

UTF-16 is an encoding system used by several platforms and applications to represent Unicode characters. Notably, Microsoft Windows employs UTF-16 for internal operations, file names, and registry keys, while Java and JavaScript use it for string representation.

UTF-16 is an encoding method for Unicode characters where each character is represented by one or two 16-bit code units. For characters in the Basic Multilingual Plane (BMP), which includes most commonly used characters from around the world, a single 16-bit unit suffices. However, for characters beyond this plane — in the supplementary planes — UTF-16 uses a pair of 16-bit units known as surrogate pairs. This dual approach allows UTF-16 to represent all of the Unicode’s over one million possible characters while keeping most characters within a 16-bit structure for efficiency.

Values making up surrogate pairs are either high surrogates (U+D800 to U+DBFF) or low surrogates (U+DC00 to U+DFFF). A pair is always made of a high surrogate followed by a low surrogate. Otherwise, we have error.

The need for replacement characters in UTF-16 arises from the complexity of this encoding system. We often put a replacement character (typically U+FFFD or �) wherever a high surrogate is not followed by a low surrogate and whenever a low surrogate is not preceded by a high surrogate. Using a replacement character is a in part a security issue When converting text from one encoding to another, or when dealing with potentially corrupted data, not all characters might map correctly or exist in both encodings. In such cases, using a replacement character ensures that the text processing continues without crashing or producing nonsensical output. It also signals to the user or developer that something went wrong during the encoding or transmission process, allowing for better management of data errors or security considerations by preventing misinterpretation or exploitation of malformed data.

bool is_high_surrogate(char16_t c) { 
  return (c >= 0xD800 && c <= 0xDBFF);
}

bool is_low_surrogate(char16_t c) { 
  return (c >= 0xDC00 && c <= 0xDFFF); 
}

void replace_invalid_utf16(char16_t *buffer, size_t length) {
  for (size_t i = 0; i < length; ++i) {
    if (is_high_surrogate(buffer[i])) {
      if (i + 1 < length && is_low_surrogate(buffer[i + 1])) {
        i++;
      } else {
        buffer[i] = 0xFFFD; // Replacement character
      }
    } else if (is_low_surrogate(buffer[i])) {
      buffer[i] = 0xFFFD; // Replacement character
    }
  }
}

The replace_invalid_utf16 function scans through a buffer of char16_t characters, ensuring that any high surrogate is followed by a low surrogate to form a valid pair; if not, or if a low surrogate appears without a preceding high surrogate, it replaces the invalid character with the Unicode replacement character (U+FFFD), effectively correcting the UTF-16 encoding in place. The function should be reasonable efficient.

Most of our processors have instructions able to process registers with eight 16-bit words per register. Most mobile processors today are 64-bit ARM processors with powerful ARM NEON instructions.

We can write a function targeting ARM NEON using intrinsic functions. These are special functions that given us low level access to the unique functionality of ARM NEON. There are comparable intrinsic functions for other processor families such as Intel/AMD, RISC-V, Loonson and so forth.

void replace_invalid_utf16_neon(char16_t *buffer, size_t length) {
  const size_t vec_size = 8;
  size_t i = 0;
  if (length >= vec_size) {
    uint16x8_t replacement = vdupq_n_u16(0xFFFD);
    uint16x8_t previous_high_surrogate_mask = vdupq_n_u16(0);
    for (; i + vec_size <= length; i += vec_size) {
      uint16x8_t vec = vld1q_u16((const uint16_t *)buffer + i);

      uint16x8_t low_surrogate_mask =
          vcleq_u16(vaddq_u16(vec, vdupq_n_u16(0x2400)), 
                     vdupq_n_u16(0x03ff));

      uint16x8_t high_surrogate_mask =
          vcleq_u16(vaddq_u16(vec, vdupq_n_u16(0x2800)), 
                     vdupq_n_u16(0x03ff));
      uint16x8_t offset_high_surrogate_mask =
          vextq_u16(previous_high_surrogate_mask, 
                              high_surrogate_mask, 7);
      uint16x8_t offset_low_surrogate_mask =
          (i + vec_size < length 
          && is_low_surrogate(buffer[i + vec_size]))
              ? vextq_u16(low_surrogate_mask, vdupq_n_u16(0xFFFF), 1)
              : vextq_u16(low_surrogate_mask, vdupq_n_u16(0), 1);

      uint16x8_t low_not_preceded_by_high =
          vbicq_u16(low_surrogate_mask, offset_high_surrogate_mask);

      uint16x8_t high_not_followed_by_low =
          vbicq_u16(high_surrogate_mask, offset_low_surrogate_mask);

      uint16x8_t invalid_pair_mask =
          vorrq_u16(low_not_preceded_by_high, high_not_followed_by_low);

      uint16x8_t result = vbslq_u16(invalid_pair_mask, replacement, vec);
      vst1q_u16((uint16_t *)buffer + i, result);
      previous_high_surrogate_mask = high_surrogate_mask;
    }
  }

  // Handle remaining elements or small buffers
  for (; i < length; ++i) {
    if (is_high_surrogate(buffer[i])) {
      if (i + 1 < length && 
      is_low_surrogate(buffer[i + 1])) {
        i++;
      } else {
        buffer[i] = 0xFFFD; // Replacement character
      }
    } else if (is_low_surrogate(buffer[i])) {
      buffer[i] = 0xFFFD; // Replacement character
    }
  }
}

This function, replace_invalid_utf16_neon, uses ARM NEON instructions to efficiently validate and correct UTF-16 encoded text in chunks of 8 characters. It initializes by setting up vectors for the replacement character (0xFFFD) and masks for tracking high surrogates. For each chunk, it loads the data, creates masks to identify high and low surrogates, shifts these masks to check for valid surrogate pairs across vector boundaries, and then replaces any invalid characters (those being lone low surrogates or high surrogates not followed by a low surrogate) with the replacement character. After handling as many full chunks as possible, it processes any remaining or smaller chunks using scalar operations to ensure all invalid UTF-16 sequences are corrected. Though reasonably efficient, I expect that it is possible to do much better than this function.

A reader proposed a faster alternative where we use the fact that ARM NEON has interleaved loads and stores. When loading the data, we put the most significant bytes in one register, and the least significant bytes in the other register. The most significant bytes are sufficient to check for errors and, thus, we can check 32 bytes of input data by validating just one 16-byte register. The code looks as follows:

void replace_invalid_utf16_neon_v2(char16_t *buffer, size_t length) {
  // if big endian, flip these:
  const int LOW_VEC = 0, HIGH_VEC = 1;
  const size_t vec_size = 32;
  size_t i = 0;
  if (length*2 >= vec_size) {
   uint8x16_t previous_high_surrogate_mask = vdupq_n_u8(0);
   uint8_t *buffer8 = (uint8_t *)buffer;
   for (; i < length*2 - vec_size; i += vec_size) {
    uint8x16x2_t pair = vld2q_u8(buffer8 + i);
    uint8x16_t vec = vshrq_n_u8(pair.val[HIGH_VEC], 2);
      
    uint8x16_t low_surrogate_mask = vceqq_u8(vec, vdupq_n_u8(0x37));
    uint8x16_t high_surrogate_mask = vceqq_u8(vec, vdupq_n_u8(0x36));
      
    uint8x16_t offset_high_surrogate_mask 
     = vextq_u8(previous_high_surrogate_mask, high_surrogate_mask, 15);
    uint8_t next_char_type = buffer8[i + vec_size + HIGH_VEC] >> 2;
    uint8x16_t offset_low_surrogate_mask = vextq_u8(low_surrogate_mask,
                  vmovq_n_u8(next_char_type == 0x37 ? 0xff : 0), 1);
      
    uint8x16_t low_not_preceded_by_high = vbicq_u8(low_surrogate_mask, 
                  offset_high_surrogate_mask);
    uint8x16_t high_not_followed_by_low = vbicq_u8(high_surrogate_mask,
                  offset_low_surrogate_mask);
      uint8x16_t invalid_pair_mask = vorrq_u8(low_not_preceded_by_high,
                  high_not_followed_by_low);
      
      pair.val[HIGH_VEC] = vorrq_u8(pair.val[HIGH_VEC], 
                    invalid_pair_mask);
      pair.val[LOW_VEC] = vbslq_u8(invalid_pair_mask, vdupq_n_u8(0xfd),
                    pair.val[LOW_VEC]);
      vst2q_u8(buffer8 + i, pair);
      previous_high_surrogate_mask = high_surrogate_mask;
    }
    i >>= 1;
  }
 
  // Handle remaining elements or small buffers
  for (; i < length; ++i) {
    uint16_t surrogate_type = (uint16_t)buffer[i] >> 10;
    if (surrogate_type == 0x36) {
      if (i + 1 < length && is_low_surrogate(buffer[i + 1])) {
        i++;
      } else {
        buffer[i] = 0xFFFD; // Replacement character
      }
    } else if (surrogate_type == 0x37) {
      buffer[i] = 0xFFFD; // Replacement character
    }
  }
}

You can do even better if you assume that the input rarely contains invalid characters but I am going to leave it as an exercise for the reader.

To benchmark these functions, I use a single string made of 10 million space characters. It is the easiest case as there is no replacement and no surrogate pairs. I suspect that it also represents a typical case: there are relatively few surrogate pairs in most text. Using LLVM 16 and an Apple M2 processor, I get the following results:

So the fast ARM NEON code is about 8 times faster than the conventional code.

My source code is available on GitHub.