快速检查一个字符串是否需要转义 – 丹尼尔·莱米尔的博客

在软件中，通常用引号(")包围字符串来表示。如果字符串本身包含引号，就需要转义字符串，例如引号字符(")或反斜杠字符()应被替换为\"或\。大多数程序员熟悉这个过程。

大多数字符串不需要转义，所以快速检查字符串是否需要转义很有用。

在流行的交互格式 JSON 中，如果字符串包含引号字符、反斜杠字符或任何 ASCII 控制字符（即代码点小于 32），则必须转义。

如何检查这样的字符串？假设使用 C++，一个合理的函数可能如下：

bool simple_needs_escaping(std::string_view v) {
  for (char c : v) {
    if ((uint8_t(c) < 32) | (c == '"') | (c == '\\')) {
      return true;
    }
  }
  return false;
}

该函数以std::string_view类型的v作为参数，遍历输入字符串v中的每个字符c，通过比较(uint8_t(c) < 32)检查字符的 ASCII 值是否小于 32（涵盖控制字符），(c == '"')检查字符是否为双引号，(c == '\\')检查字符是否为反斜杠，若有满足条件的字符则返回true，否则返回false。

重要的是，该函数一旦找到需要转义的字符就应退出。如果预期不会找到这样的字符，可以尝试另一种总是扫描整个输入的方法，这样编译器更可能使用自动向量化（如单指令多数据（SIMD）指令），这种函数被称为“无分支”。示例函数如下：

bool branchless_needs_escaping(std::string_view v) {
  bool b = false;
  for (char c : v) {
    b |= ((uint8_t(c) < 32) | (c == '"') | (c == '\\'));
  }
  return b;
}

还可以尝试使用查表的方法，构建一个包含所有可能字节值是否需要转义的表，这样每个字符只需从表中加载一次并进行一两个额外的指令检查，效率较高。示例代码如下：

static constexpr std::array<uint8_t, 256> json_quotable_character =
    []() constexpr {
  std::array<uint8_t, 256> result{};
  for (int i = 0; i < 32; i++) {
    result[i] = 1;
  }
  for (int i : {'"', '\\'}) {
    result[i] = 1;
  }
  return result;
}();

bool table_needs_escaping(std::string_view view) {
  uint8_t needs = 0;
  for (uint8_t c : view) {
    needs |= json_quotable_character[c];
  }
  return needs;
}

还可以使用 SIMD 指令（如 NEON 或 SSE2）来进一步优化，大多数计算机可能是支持至少 NEON 指令的 ARM 机器或支持至少 SSE2 指令的 x64 机器，可在编译时区分这两种情况。以 16 字节为块加载数据并进行比较，SIMD 指令可一次进行 16 次比较，比逐个字符处理快得多。NEON 代码示例：

bool simd_needs_escaping(std::string_view view) {
  if (view.size() < 16) {
    return simple_needs_escaping(view);
  }
  size_t i = 0;
  static uint8_t rnt_array[16] = {1, 0, 34, 0, 0,  0, 0, 0,
                                  0, 0, 0,  0, 92, 0, 0, 0};
  const uint8x16_t rnt = vld1q_u8(rnt_array);
  uint8x16_t running{0};
  for (; i + 15 < view.size(); i += 16) {
    uint8x16_t word = vld1q_u8((const uint8_t *)view.data() + i);
    running = vorrq_u8(
        running,
        vceqq_u8(vqtbl1q_u8(rnt, vandq_u8(word, vdupq_n_u8(15))), word));
    running = vorrq_u8(running, vcltq_u8(word, vdupq_n_u8(32)));
  }
  if (i < view.size()) {
    uint8x16_t word =
        vld1q_u8((const uint8_t *)view.data() + view.length() - 16);
    running = vorrq_u8(
        running,
        vceqq_u8(vqtbl1q_u8(rnt, vandq_u8(word, vdupq_n_u8(15))), word));
    running = vorrq_u8(running, vcltq_u8(word, vdupq_n_u8(32)));
  }
  return vmaxvq_u32(vreinterpretq_u32_u8(running))!= 0;
}

SSE2 代码示例：

inline bool simd_needs_escaping(std::string_view view) {
  if (view.size() < 16) {
    return simple_needs_escaping(view);
  }
  size_t i = 0;
  __m128i running = _mm_setzero_si128();
  for (; i + 15 < view.size(); i += 16) {
    __m128i word = _mm_loadu_si128((const __m128i *)(view.data() + i));
    running = _mm_or_si128(running, _mm_cmpeq_epi8(word, _mm_set1_epi8(34)));
    running = _mm_or_si128(running, _mm_cmpeq_epi8(word, _mm_set1_epi8(92)));
    running = _mm_or_si128(
        running, _mm_cmpeq_epi8(_mm_subs_epu8(word, _mm_set1_epi8(31)),
                                _mm_setzero_si128()));
  }
  if (i < view.size()) {
    __m128i word =
        _mm_loadu_si128((const __m128i *)(view.data() + view.length() - 16));
    running = _mm_or_si128(running, _mm_cmpeq_epi8(word, _mm_set1_epi8(34)));
    running = _mm_or_si128(running, _mm_cmpeq_epi8(word, _mm_set1_epi8(92)));
    running = _mm_or_si128(
        running, _mm_cmpeq_epi8(_mm_subs_epu8(word, _mm_set1_epi8(31)),
                                _mm_setzero_si128()));
  }
  return _mm_movemask_epi8(running)!= 0;
}

这些基于 SIMD 的函数可以进一步优化以减少指令数量，但在处理 16 字节的块时比传统函数使用的指令少得多。

对这些函数进行基准测试可能很棘手，结果取决于编译器和处理器，且对数据敏感。但经验表明，SIMD 方法通常快很多。作者编写了一个小基准测试[https://github.com/lemire/Cod...]，在不同系统下测试了简单、无分支、表和 SIMD 方法的速度，例如在 Linux GCC 12 的 Intel Ice Lake (3.2 GHz)上，速度分别为 0.65 GB/s、0.91 GB/s、1.9 GB/s、5.2 GB/s，在 Linux LLVM 16 的 Intel Ice Lake (3.2 GHz)上，速度分别为 0.91 GB/s、2.6 GB/s、2.5 GB/s、5.7 GB/s，表基方法很有竞争力，但在使用 LLVM/clang 时无分支方法由于能很好地自动向量化代码而更优，而所有情况下手工编码的 SIMD 函数至少快两倍。注意 ASCII 中代码点值为 127 的字符也是控制字符，且 Unicode 有很多控制字符。