third_party/utf8_range: support arm neon (#18126)
Protobuf uses utf8_range library for utf8 string validation.
Currently, only SSE implementation is integrated.
This patch adapts utf8_range Neon implementation to protobuf.
Closes #18126
COPYBARA_INTEGRATE_REVIEW=https://github.com/protocolbuffers/protobuf/pull/18126 from cyb70289:utf8-neon 5edbcc26925f9fb1e2c7d8174639f77afce550b1
PiperOrigin-RevId: 680711032
diff --git a/ruby/.gitignore b/ruby/.gitignore
index 555af6c..9ff0545 100644
--- a/ruby/.gitignore
+++ b/ruby/.gitignore
@@ -9,5 +9,7 @@
tests/google/
ext/google/protobuf_c/third_party/utf8_range/utf8_range.h
ext/google/protobuf_c/third_party/utf8_range/utf8_range.c
+ext/google/protobuf_c/third_party/utf8_range/utf8_range_sse.inc
+ext/google/protobuf_c/third_party/utf8_range/utf8_range_neon.inc
ext/google/protobuf_c/third_party/utf8_range/LICENSE
lib/google/protobuf/*_pb.rb
\ No newline at end of file
diff --git a/ruby/Rakefile b/ruby/Rakefile
index 33fb568..fde98a9 100644
--- a/ruby/Rakefile
+++ b/ruby/Rakefile
@@ -81,7 +81,7 @@
# We need utf8_range in-tree.
utf8_root = '../third_party/utf8_range'
%w[
- utf8_range.h utf8_range.c LICENSE
+ utf8_range.h utf8_range.c utf8_range_sse.inc utf8_range_neon.inc LICENSE
].each do |file|
FileUtils.cp File.join(utf8_root, file),
"ext/google/protobuf_c/third_party/utf8_range"
diff --git a/third_party/utf8_range/BUILD.bazel b/third_party/utf8_range/BUILD.bazel
index 90b1088..47682a2 100644
--- a/third_party/utf8_range/BUILD.bazel
+++ b/third_party/utf8_range/BUILD.bazel
@@ -35,6 +35,8 @@
srcs = [
"utf8_range.c",
"utf8_range.h",
+ "utf8_range_neon.inc",
+ "utf8_range_sse.inc",
],
visibility = ["//:__subpackages__"],
)
@@ -44,7 +46,11 @@
srcs = [
"utf8_range.c",
],
- hdrs = ["utf8_range.h"],
+ hdrs = [
+ "utf8_range.h",
+ "utf8_range_neon.inc",
+ "utf8_range_sse.inc",
+ ],
strip_include_prefix = "/third_party/utf8_range",
)
diff --git a/third_party/utf8_range/utf8_range.c b/third_party/utf8_range/utf8_range.c
index 9564b07..6dc0dd1 100644
--- a/third_party/utf8_range/utf8_range.c
+++ b/third_party/utf8_range/utf8_range.c
@@ -21,12 +21,6 @@
#include <stdint.h>
#include <string.h>
-#ifdef __SSE4_1__
-#include <emmintrin.h>
-#include <smmintrin.h>
-#include <tmmintrin.h>
-#endif
-
#if defined(__GNUC__)
#define FORCE_INLINE_ATTR __attribute__((always_inline))
#elif defined(_MSC_VER)
@@ -143,7 +137,7 @@
return err_pos + (1 - return_position);
}
-#ifdef __SSE4_1__
+#if defined(__SSE4_1__) || (defined(__ARM_NEON) && defined(__ARM_64BIT_STATE))
/* Returns the number of bytes needed to skip backwards to get to the first
byte of codepoint.
*/
@@ -175,6 +169,12 @@
return data;
}
+#if defined(__SSE4_1__)
+#include "utf8_range_sse.inc"
+#elif defined(__ARM_NEON) && defined(__ARM_64BIT_STATE)
+#include "utf8_range_neon.inc"
+#endif
+
static FORCE_INLINE_ATTR inline size_t utf8_range_Validate(
const char* data, size_t len, int return_position) {
if (len == 0) return 1 - return_position;
@@ -187,274 +187,11 @@
return (return_position ? (data - (end - len)) : 0) +
utf8_range_ValidateUTF8Naive(data, end, return_position);
}
-#ifndef __SSE4_1__
+#if defined(__SSE4_1__) || (defined(__ARM_NEON) && defined(__ARM_64BIT_STATE))
+ return utf8_range_ValidateUTF8Simd(data, end, return_position);
+#else
return (return_position ? (data - (end - len)) : 0) +
utf8_range_ValidateUTF8Naive(data, end, return_position);
-#else
- /* This code checks that utf-8 ranges are structurally valid 16 bytes at once
- * using superscalar instructions.
- * The mapping between ranges of codepoint and their corresponding utf-8
- * sequences is below.
- */
-
- /*
- * 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
- */
-
- /* First we compute the type for each byte, as given by the table below.
- * This type will be used as an index later on.
- */
-
- /*
- * Index Min Max Byte Type
- * 0 00 7F Single byte sequence
- * 1,2,3 80 BF Second, third and fourth byte for many of the sequences.
- * 4 A0 BF Second byte after E0
- * 5 80 9F Second byte after ED
- * 6 90 BF Second byte after F0
- * 7 80 8F Second byte after F4
- * 8 C2 F4 First non ASCII byte
- * 9..15 7F 80 Invalid byte
- */
-
- /* After the first step we compute the index for all bytes, then we permute
- the bytes according to their indices to check the ranges from the range
- table.
- * The range for a given type can be found in the range_min_table and
- range_max_table, the range for type/index X is in range_min_table[X] ...
- range_max_table[X].
- */
-
- /* Algorithm:
- * Put index zero to all bytes.
- * Find all non ASCII characters, give them index 8.
- * For each tail byte in a codepoint sequence, give it an index corresponding
- to the 1 based index from the end.
- * If the first byte of the codepoint is in the [C0...DF] range, we write
- index 1 in the following byte.
- * If the first byte of the codepoint is in the range [E0...EF], we write
- indices 2 and 1 in the next two bytes.
- * If the first byte of the codepoint is in the range [F0...FF] we write
- indices 3,2,1 into the next three bytes.
- * For finding the number of bytes we need to look at high nibbles (4 bits)
- and do the lookup from the table, it can be done with shift by 4 + shuffle
- instructions. We call it `first_len`.
- * Then we shift first_len by 8 bits to get the indices of the 2nd bytes.
- * Saturating sub 1 and shift by 8 bits to get the indices of the 3rd bytes.
- * Again to get the indices of the 4th bytes.
- * Take OR of all that 4 values and check within range.
- */
- /* For example:
- * input C3 80 68 E2 80 20 A6 F0 A0 80 AC 20 F0 93 80 80
- * first_len 1 0 0 2 0 0 0 3 0 0 0 0 3 0 0 0
- * 1st byte 8 0 0 8 0 0 0 8 0 0 0 0 8 0 0 0
- * 2nd byte 0 1 0 0 2 0 0 0 3 0 0 0 0 3 0 0 // Shift + sub
- * 3rd byte 0 0 0 0 0 1 0 0 0 2 0 0 0 0 2 0 // Shift + sub
- * 4th byte 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 // Shift + sub
- * Index 8 1 0 8 2 1 0 8 3 2 1 0 8 3 2 1 // OR of results
- */
-
- /* Checking for errors:
- * Error checking is done by looking up the high nibble (4 bits) of each byte
- against an error checking table.
- * Because the lookup value for the second byte depends of the value of the
- first byte in codepoint, we use saturated operations to adjust the index.
- * Specifically we need to add 2 for E0, 3 for ED, 3 for F0 and 4 for F4 to
- match the correct index.
- * If we subtract from all bytes EF then EO -> 241, ED -> 254, F0 -> 1,
- F4 -> 5
- * Do saturating sub 240, then E0 -> 1, ED -> 14 and we can do lookup to
- match the adjustment
- * Add saturating 112, then F0 -> 113, F4 -> 117, all that were > 16 will
- be more 128 and lookup in ef_fe_table will return 0 but for F0
- and F4 it will be 4 and 5 accordingly
- */
- /*
- * Then just check the appropriate ranges with greater/smaller equal
- instructions. Check tail with a naive algorithm.
- * To save from previous 16 byte checks we just align previous_first_len to
- get correct continuations of the codepoints.
- */
-
- /*
- * Map high nibble of "First Byte" to legal character length minus 1
- * 0x00 ~ 0xBF --> 0
- * 0xC0 ~ 0xDF --> 1
- * 0xE0 ~ 0xEF --> 2
- * 0xF0 ~ 0xFF --> 3
- */
- const __m128i first_len_table =
- _mm_setr_epi8(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3);
-
- /* Map "First Byte" to 8-th item of range table (0xC2 ~ 0xF4) */
- const __m128i first_range_table =
- _mm_setr_epi8(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, 8);
-
- /*
- * Range table, map range index to min and max values
- */
- const __m128i range_min_table =
- _mm_setr_epi8(0x00, 0x80, 0x80, 0x80, 0xA0, 0x80, 0x90, 0x80, 0xC2, 0x7F,
- 0x7F, 0x7F, 0x7F, 0x7F, 0x7F, 0x7F);
-
- const __m128i range_max_table =
- _mm_setr_epi8(0x7F, 0xBF, 0xBF, 0xBF, 0xBF, 0x9F, 0xBF, 0x8F, 0xF4, 0x80,
- 0x80, 0x80, 0x80, 0x80, 0x80, 0x80);
-
- /*
- * Tables for fast handling of four special First Bytes(E0,ED,F0,F4), after
- * which the Second Byte are not 80~BF. It contains "range index adjustment".
- * +------------+---------------+------------------+----------------+
- * | First Byte | original range| range adjustment | adjusted range |
- * +------------+---------------+------------------+----------------+
- * | E0 | 2 | 2 | 4 |
- * +------------+---------------+------------------+----------------+
- * | ED | 2 | 3 | 5 |
- * +------------+---------------+------------------+----------------+
- * | F0 | 3 | 3 | 6 |
- * +------------+---------------+------------------+----------------+
- * | F4 | 4 | 4 | 8 |
- * +------------+---------------+------------------+----------------+
- */
-
- /* df_ee_table[1] -> E0, df_ee_table[14] -> ED as ED - E0 = 13 */
- // The values represent the adjustment in the Range Index table for a correct
- // index.
- const __m128i df_ee_table =
- _mm_setr_epi8(0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0);
-
- /* ef_fe_table[1] -> F0, ef_fe_table[5] -> F4, F4 - F0 = 4 */
- // The values represent the adjustment in the Range Index table for a correct
- // index.
- const __m128i ef_fe_table =
- _mm_setr_epi8(0, 3, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
-
- __m128i prev_input = _mm_set1_epi8(0);
- __m128i prev_first_len = _mm_set1_epi8(0);
- __m128i error = _mm_set1_epi8(0);
- while (end - data >= 16) {
- const __m128i input =
- _mm_loadu_si128((const __m128i*)(data));
-
- /* high_nibbles = input >> 4 */
- const __m128i high_nibbles =
- _mm_and_si128(_mm_srli_epi16(input, 4), _mm_set1_epi8(0x0F));
-
- /* first_len = legal character length minus 1 */
- /* 0 for 00~7F, 1 for C0~DF, 2 for E0~EF, 3 for F0~FF */
- /* first_len = first_len_table[high_nibbles] */
- __m128i first_len = _mm_shuffle_epi8(first_len_table, high_nibbles);
-
- /* First Byte: set range index to 8 for bytes within 0xC0 ~ 0xFF */
- /* range = first_range_table[high_nibbles] */
- __m128i range = _mm_shuffle_epi8(first_range_table, high_nibbles);
-
- /* Second Byte: set range index to first_len */
- /* 0 for 00~7F, 1 for C0~DF, 2 for E0~EF, 3 for F0~FF */
- /* range |= (first_len, prev_first_len) << 1 byte */
- range = _mm_or_si128(range, _mm_alignr_epi8(first_len, prev_first_len, 15));
-
- /* Third Byte: set range index to saturate_sub(first_len, 1) */
- /* 0 for 00~7F, 0 for C0~DF, 1 for E0~EF, 2 for F0~FF */
- __m128i tmp1;
- __m128i tmp2;
- /* tmp1 = saturate_sub(first_len, 1) */
- tmp1 = _mm_subs_epu8(first_len, _mm_set1_epi8(1));
- /* tmp2 = saturate_sub(prev_first_len, 1) */
- tmp2 = _mm_subs_epu8(prev_first_len, _mm_set1_epi8(1));
- /* range |= (tmp1, tmp2) << 2 bytes */
- range = _mm_or_si128(range, _mm_alignr_epi8(tmp1, tmp2, 14));
-
- /* Fourth Byte: set range index to saturate_sub(first_len, 2) */
- /* 0 for 00~7F, 0 for C0~DF, 0 for E0~EF, 1 for F0~FF */
- /* tmp1 = saturate_sub(first_len, 2) */
- tmp1 = _mm_subs_epu8(first_len, _mm_set1_epi8(2));
- /* tmp2 = saturate_sub(prev_first_len, 2) */
- tmp2 = _mm_subs_epu8(prev_first_len, _mm_set1_epi8(2));
- /* range |= (tmp1, tmp2) << 3 bytes */
- range = _mm_or_si128(range, _mm_alignr_epi8(tmp1, tmp2, 13));
-
- /*
- * Now we have below range indices calculated
- * Correct cases:
- * - 8 for C0~FF
- * - 3 for 1st byte after F0~FF
- * - 2 for 1st byte after E0~EF or 2nd byte after F0~FF
- * - 1 for 1st byte after C0~DF or 2nd byte after E0~EF or
- * 3rd byte after F0~FF
- * - 0 for others
- * Error cases:
- * >9 for non ascii First Byte overlapping
- * E.g., F1 80 C2 90 --> 8 3 10 2, where 10 indicates error
- */
-
- /* Adjust Second Byte range for special First Bytes(E0,ED,F0,F4) */
- /* Overlaps lead to index 9~15, which are illegal in range table */
- __m128i shift1;
- __m128i pos;
- __m128i range2;
- /* shift1 = (input, prev_input) << 1 byte */
- shift1 = _mm_alignr_epi8(input, prev_input, 15);
- pos = _mm_sub_epi8(shift1, _mm_set1_epi8(0xEF));
- /*
- * shift1: | EF F0 ... FE | FF 00 ... ... DE | DF E0 ... EE |
- * pos: | 0 1 15 | 16 17 239| 240 241 255|
- * pos-240: | 0 0 0 | 0 0 0 | 0 1 15 |
- * pos+112: | 112 113 127| >= 128 | >= 128 |
- */
- tmp1 = _mm_subs_epu8(pos, _mm_set1_epi8(-16));
- range2 = _mm_shuffle_epi8(df_ee_table, tmp1);
- tmp2 = _mm_adds_epu8(pos, _mm_set1_epi8(112));
- range2 = _mm_add_epi8(range2, _mm_shuffle_epi8(ef_fe_table, tmp2));
-
- range = _mm_add_epi8(range, range2);
-
- /* Load min and max values per calculated range index */
- __m128i min_range = _mm_shuffle_epi8(range_min_table, range);
- __m128i max_range = _mm_shuffle_epi8(range_max_table, range);
-
- /* Check value range */
- if (return_position) {
- error = _mm_cmplt_epi8(input, min_range);
- error = _mm_or_si128(error, _mm_cmpgt_epi8(input, max_range));
- /* 5% performance drop from this conditional branch */
- if (!_mm_testz_si128(error, error)) {
- break;
- }
- } else {
- error = _mm_or_si128(error, _mm_cmplt_epi8(input, min_range));
- error = _mm_or_si128(error, _mm_cmpgt_epi8(input, max_range));
- }
-
- prev_input = input;
- prev_first_len = first_len;
-
- data += 16;
- }
- /* If we got to the end, we don't need to skip any bytes backwards */
- if (return_position && (data - (end - len)) == 0) {
- return utf8_range_ValidateUTF8Naive(data, end, return_position);
- }
- /* Find previous codepoint (not 80~BF) */
- data -= utf8_range_CodepointSkipBackwards(_mm_extract_epi32(prev_input, 3));
- if (return_position) {
- return (data - (end - len)) +
- utf8_range_ValidateUTF8Naive(data, end, return_position);
- }
- /* Test if there was any error */
- if (!_mm_testz_si128(error, error)) {
- return 0;
- }
- /* Check the tail */
- return utf8_range_ValidateUTF8Naive(data, end, return_position);
#endif
}
diff --git a/third_party/utf8_range/utf8_range_neon.inc b/third_party/utf8_range/utf8_range_neon.inc
new file mode 100644
index 0000000..c78c9b4
--- /dev/null
+++ b/third_party/utf8_range/utf8_range_neon.inc
@@ -0,0 +1,117 @@
+#include <arm_neon.h>
+
+/* This code is almost the same as SSE implementation, please reference
+ * utf8-range-sse.inc for detailed explanation.
+ * The only difference is the range adjustment step. NEON code is more
+ * straightforward.
+ */
+
+static FORCE_INLINE_ATTR inline size_t utf8_range_ValidateUTF8Simd(
+ const char* data, const char* end, int return_position) {
+ const uint8x16_t first_len_tbl = {
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3,
+ };
+ const uint8x16_t first_range_tbl = {
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, 8,
+ };
+ const uint8x16_t range_min_tbl = {
+ 0x00, 0x80, 0x80, 0x80, 0xA0, 0x80, 0x90, 0x80,
+ 0xC2, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
+ };
+ const uint8x16_t range_max_tbl = {
+ 0x7F, 0xBF, 0xBF, 0xBF, 0xBF, 0x9F, 0xBF, 0x8F,
+ 0xF4, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+ };
+ /* Range adjustment in NEON uint8x16x2 table. Note that lanes are interleaved
+ * in register. The table below is plotted vertically to ease understanding.
+ * The 1st column is for E0~EF, 2nd column for F0~FF.
+ */
+ // clang-format off
+ const uint8_t range_adjust_tbl_data[] = {
+ /* index -> 0~15 16~31 <- index */
+ /* E0 -> */ 2, 3, /* <- F0 */
+ 0, 0,
+ 0, 0,
+ 0, 0,
+ 0, 4, /* <- F4 */
+ 0, 0,
+ 0, 0,
+ 0, 0,
+ 0, 0,
+ 0, 0,
+ 0, 0,
+ 0, 0,
+ 0, 0,
+ /* ED -> */ 3, 0,
+ 0, 0,
+ 0, 0,
+ };
+ // clang-format on
+ const uint8x16x2_t range_adjust_tbl = vld2q_u8(range_adjust_tbl_data);
+
+ const uint8x16_t const_1 = vdupq_n_u8(1);
+ const uint8x16_t const_2 = vdupq_n_u8(2);
+ const uint8x16_t const_e0 = vdupq_n_u8(0xE0);
+
+ uint8x16_t prev_input = vdupq_n_u8(0);
+ uint8x16_t prev_first_len = vdupq_n_u8(0);
+ uint8x16_t error = vdupq_n_u8(0);
+
+ const char* const data_original = data;
+ while (end - data >= 16) {
+ const uint8x16_t input = vld1q_u8((const uint8_t*)data);
+
+ const uint8x16_t high_nibbles = vshrq_n_u8(input, 4);
+
+ const uint8x16_t first_len = vqtbl1q_u8(first_len_tbl, high_nibbles);
+
+ uint8x16_t range = vqtbl1q_u8(first_range_tbl, high_nibbles);
+
+ range = vorrq_u8(range, vextq_u8(prev_first_len, first_len, 15));
+
+ uint8x16_t shift2 = vextq_u8(prev_first_len, first_len, 14);
+ shift2 = vqsubq_u8(shift2, const_1);
+ range = vorrq_u8(range, shift2);
+
+ uint8x16_t shift3 = vextq_u8(prev_first_len, first_len, 13);
+ shift3 = vqsubq_u8(shift3, const_2);
+ range = vorrq_u8(range, shift3);
+
+ uint8x16_t shift1 = vextq_u8(prev_input, input, 15);
+ shift1 = vsubq_u8(shift1, const_e0);
+ range = vaddq_u8(range, vqtbl2q_u8(range_adjust_tbl, shift1));
+
+ const uint8x16_t min_range = vqtbl1q_u8(range_min_tbl, range);
+ const uint8x16_t max_range = vqtbl1q_u8(range_max_tbl, range);
+
+ if (return_position) {
+ error = vcltq_u8(input, min_range);
+ error = vorrq_u8(error, vcgtq_u8(input, max_range));
+ if (vmaxvq_u32(vreinterpretq_u32_u8(error))) {
+ break;
+ }
+ } else {
+ error = vorrq_u8(error, vcltq_u8(input, min_range));
+ error = vorrq_u8(error, vcgtq_u8(input, max_range));
+ }
+
+ prev_input = input;
+ prev_first_len = first_len;
+
+ data += 16;
+ }
+
+ if (return_position && data == data_original) {
+ return utf8_range_ValidateUTF8Naive(data, end, return_position);
+ }
+ const int32_t prev = vgetq_lane_s32(vreinterpretq_s32_u8(prev_input), 3);
+ data -= utf8_range_CodepointSkipBackwards(prev);
+ if (return_position) {
+ return (data - data_original) +
+ utf8_range_ValidateUTF8Naive(data, end, return_position);
+ }
+ if (vmaxvq_u32(vreinterpretq_u32_u8(error))) {
+ return 0;
+ }
+ return utf8_range_ValidateUTF8Naive(data, end, return_position);
+}
diff --git a/third_party/utf8_range/utf8_range_sse.inc b/third_party/utf8_range/utf8_range_sse.inc
new file mode 100644
index 0000000..eaf2327
--- /dev/null
+++ b/third_party/utf8_range/utf8_range_sse.inc
@@ -0,0 +1,273 @@
+#include <emmintrin.h>
+#include <smmintrin.h>
+#include <tmmintrin.h>
+
+static FORCE_INLINE_ATTR inline size_t utf8_range_ValidateUTF8Simd(
+ const char* data, const char* end, int return_position) {
+ /* This code checks that utf-8 ranges are structurally valid 16 bytes at once
+ * using superscalar instructions.
+ * The mapping between ranges of codepoint and their corresponding utf-8
+ * sequences is below.
+ */
+
+ /*
+ * 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
+ */
+
+ /* First we compute the type for each byte, as given by the table below.
+ * This type will be used as an index later on.
+ */
+
+ /*
+ * Index Min Max Byte Type
+ * 0 00 7F Single byte sequence
+ * 1,2,3 80 BF Second, third and fourth byte for many of the sequences.
+ * 4 A0 BF Second byte after E0
+ * 5 80 9F Second byte after ED
+ * 6 90 BF Second byte after F0
+ * 7 80 8F Second byte after F4
+ * 8 C2 F4 First non ASCII byte
+ * 9..15 7F 80 Invalid byte
+ */
+
+ /* After the first step we compute the index for all bytes, then we permute
+ the bytes according to their indices to check the ranges from the range
+ table.
+ * The range for a given type can be found in the range_min_table and
+ range_max_table, the range for type/index X is in range_min_table[X] ...
+ range_max_table[X].
+ */
+
+ /* Algorithm:
+ * Put index zero to all bytes.
+ * Find all non ASCII characters, give them index 8.
+ * For each tail byte in a codepoint sequence, give it an index corresponding
+ to the 1 based index from the end.
+ * If the first byte of the codepoint is in the [C0...DF] range, we write
+ index 1 in the following byte.
+ * If the first byte of the codepoint is in the range [E0...EF], we write
+ indices 2 and 1 in the next two bytes.
+ * If the first byte of the codepoint is in the range [F0...FF] we write
+ indices 3,2,1 into the next three bytes.
+ * For finding the number of bytes we need to look at high nibbles (4 bits)
+ and do the lookup from the table, it can be done with shift by 4 + shuffle
+ instructions. We call it `first_len`.
+ * Then we shift first_len by 8 bits to get the indices of the 2nd bytes.
+ * Saturating sub 1 and shift by 8 bits to get the indices of the 3rd bytes.
+ * Again to get the indices of the 4th bytes.
+ * Take OR of all that 4 values and check within range.
+ */
+ /* For example:
+ * input C3 80 68 E2 80 20 A6 F0 A0 80 AC 20 F0 93 80 80
+ * first_len 1 0 0 2 0 0 0 3 0 0 0 0 3 0 0 0
+ * 1st byte 8 0 0 8 0 0 0 8 0 0 0 0 8 0 0 0
+ * 2nd byte 0 1 0 0 2 0 0 0 3 0 0 0 0 3 0 0 // Shift + sub
+ * 3rd byte 0 0 0 0 0 1 0 0 0 2 0 0 0 0 2 0 // Shift + sub
+ * 4th byte 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 // Shift + sub
+ * Index 8 1 0 8 2 1 0 8 3 2 1 0 8 3 2 1 // OR of results
+ */
+
+ /* Checking for errors:
+ * Error checking is done by looking up the high nibble (4 bits) of each byte
+ against an error checking table.
+ * Because the lookup value for the second byte depends of the value of the
+ first byte in codepoint, we use saturated operations to adjust the index.
+ * Specifically we need to add 2 for E0, 3 for ED, 3 for F0 and 4 for F4 to
+ match the correct index.
+ * If we subtract from all bytes EF then EO -> 241, ED -> 254, F0 -> 1,
+ F4 -> 5
+ * Do saturating sub 240, then E0 -> 1, ED -> 14 and we can do lookup to
+ match the adjustment
+ * Add saturating 112, then F0 -> 113, F4 -> 117, all that were > 16 will
+ be more 128 and lookup in ef_fe_table will return 0 but for F0
+ and F4 it will be 4 and 5 accordingly
+ */
+ /*
+ * Then just check the appropriate ranges with greater/smaller equal
+ instructions. Check tail with a naive algorithm.
+ * To save from previous 16 byte checks we just align previous_first_len to
+ get correct continuations of the codepoints.
+ */
+
+ /*
+ * Map high nibble of "First Byte" to legal character length minus 1
+ * 0x00 ~ 0xBF --> 0
+ * 0xC0 ~ 0xDF --> 1
+ * 0xE0 ~ 0xEF --> 2
+ * 0xF0 ~ 0xFF --> 3
+ */
+ const __m128i first_len_table =
+ _mm_setr_epi8(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3);
+
+ /* Map "First Byte" to 8-th item of range table (0xC2 ~ 0xF4) */
+ const __m128i first_range_table =
+ _mm_setr_epi8(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, 8);
+
+ /*
+ * Range table, map range index to min and max values
+ */
+ const __m128i range_min_table =
+ _mm_setr_epi8(0x00, 0x80, 0x80, 0x80, 0xA0, 0x80, 0x90, 0x80, 0xC2, 0x7F,
+ 0x7F, 0x7F, 0x7F, 0x7F, 0x7F, 0x7F);
+
+ const __m128i range_max_table =
+ _mm_setr_epi8(0x7F, 0xBF, 0xBF, 0xBF, 0xBF, 0x9F, 0xBF, 0x8F, 0xF4, 0x80,
+ 0x80, 0x80, 0x80, 0x80, 0x80, 0x80);
+
+ /*
+ * Tables for fast handling of four special First Bytes(E0,ED,F0,F4), after
+ * which the Second Byte are not 80~BF. It contains "range index adjustment".
+ * +------------+---------------+------------------+----------------+
+ * | First Byte | original range| range adjustment | adjusted range |
+ * +------------+---------------+------------------+----------------+
+ * | E0 | 2 | 2 | 4 |
+ * +------------+---------------+------------------+----------------+
+ * | ED | 2 | 3 | 5 |
+ * +------------+---------------+------------------+----------------+
+ * | F0 | 3 | 3 | 6 |
+ * +------------+---------------+------------------+----------------+
+ * | F4 | 4 | 4 | 8 |
+ * +------------+---------------+------------------+----------------+
+ */
+
+ /* df_ee_table[1] -> E0, df_ee_table[14] -> ED as ED - E0 = 13 */
+ // The values represent the adjustment in the Range Index table for a correct
+ // index.
+ const __m128i df_ee_table =
+ _mm_setr_epi8(0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0);
+
+ /* ef_fe_table[1] -> F0, ef_fe_table[5] -> F4, F4 - F0 = 4 */
+ // The values represent the adjustment in the Range Index table for a correct
+ // index.
+ const __m128i ef_fe_table =
+ _mm_setr_epi8(0, 3, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
+
+ __m128i prev_input = _mm_set1_epi8(0);
+ __m128i prev_first_len = _mm_set1_epi8(0);
+ __m128i error = _mm_set1_epi8(0);
+
+ // Save buffer start address for later use
+ const char* const data_original = data;
+ while (end - data >= 16) {
+ const __m128i input = _mm_loadu_si128((const __m128i*)(data));
+
+ /* high_nibbles = input >> 4 */
+ const __m128i high_nibbles =
+ _mm_and_si128(_mm_srli_epi16(input, 4), _mm_set1_epi8(0x0F));
+
+ /* first_len = legal character length minus 1 */
+ /* 0 for 00~7F, 1 for C0~DF, 2 for E0~EF, 3 for F0~FF */
+ /* first_len = first_len_table[high_nibbles] */
+ __m128i first_len = _mm_shuffle_epi8(first_len_table, high_nibbles);
+
+ /* First Byte: set range index to 8 for bytes within 0xC0 ~ 0xFF */
+ /* range = first_range_table[high_nibbles] */
+ __m128i range = _mm_shuffle_epi8(first_range_table, high_nibbles);
+
+ /* Second Byte: set range index to first_len */
+ /* 0 for 00~7F, 1 for C0~DF, 2 for E0~EF, 3 for F0~FF */
+ /* range |= (first_len, prev_first_len) << 1 byte */
+ range = _mm_or_si128(range, _mm_alignr_epi8(first_len, prev_first_len, 15));
+
+ /* Third Byte: set range index to saturate_sub(first_len, 1) */
+ /* 0 for 00~7F, 0 for C0~DF, 1 for E0~EF, 2 for F0~FF */
+ __m128i tmp1;
+ __m128i tmp2;
+ /* tmp1 = saturate_sub(first_len, 1) */
+ tmp1 = _mm_subs_epu8(first_len, _mm_set1_epi8(1));
+ /* tmp2 = saturate_sub(prev_first_len, 1) */
+ tmp2 = _mm_subs_epu8(prev_first_len, _mm_set1_epi8(1));
+ /* range |= (tmp1, tmp2) << 2 bytes */
+ range = _mm_or_si128(range, _mm_alignr_epi8(tmp1, tmp2, 14));
+
+ /* Fourth Byte: set range index to saturate_sub(first_len, 2) */
+ /* 0 for 00~7F, 0 for C0~DF, 0 for E0~EF, 1 for F0~FF */
+ /* tmp1 = saturate_sub(first_len, 2) */
+ tmp1 = _mm_subs_epu8(first_len, _mm_set1_epi8(2));
+ /* tmp2 = saturate_sub(prev_first_len, 2) */
+ tmp2 = _mm_subs_epu8(prev_first_len, _mm_set1_epi8(2));
+ /* range |= (tmp1, tmp2) << 3 bytes */
+ range = _mm_or_si128(range, _mm_alignr_epi8(tmp1, tmp2, 13));
+
+ /*
+ * Now we have below range indices calculated
+ * Correct cases:
+ * - 8 for C0~FF
+ * - 3 for 1st byte after F0~FF
+ * - 2 for 1st byte after E0~EF or 2nd byte after F0~FF
+ * - 1 for 1st byte after C0~DF or 2nd byte after E0~EF or
+ * 3rd byte after F0~FF
+ * - 0 for others
+ * Error cases:
+ * >9 for non ascii First Byte overlapping
+ * E.g., F1 80 C2 90 --> 8 3 10 2, where 10 indicates error
+ */
+
+ /* Adjust Second Byte range for special First Bytes(E0,ED,F0,F4) */
+ /* Overlaps lead to index 9~15, which are illegal in range table */
+ __m128i shift1;
+ __m128i pos;
+ __m128i range2;
+ /* shift1 = (input, prev_input) << 1 byte */
+ shift1 = _mm_alignr_epi8(input, prev_input, 15);
+ pos = _mm_sub_epi8(shift1, _mm_set1_epi8(0xEF));
+ /*
+ * shift1: | EF F0 ... FE | FF 00 ... ... DE | DF E0 ... EE |
+ * pos: | 0 1 15 | 16 17 239| 240 241 255|
+ * pos-240: | 0 0 0 | 0 0 0 | 0 1 15 |
+ * pos+112: | 112 113 127| >= 128 | >= 128 |
+ */
+ tmp1 = _mm_subs_epu8(pos, _mm_set1_epi8(-16));
+ range2 = _mm_shuffle_epi8(df_ee_table, tmp1);
+ tmp2 = _mm_adds_epu8(pos, _mm_set1_epi8(112));
+ range2 = _mm_add_epi8(range2, _mm_shuffle_epi8(ef_fe_table, tmp2));
+
+ range = _mm_add_epi8(range, range2);
+
+ /* Load min and max values per calculated range index */
+ __m128i min_range = _mm_shuffle_epi8(range_min_table, range);
+ __m128i max_range = _mm_shuffle_epi8(range_max_table, range);
+
+ /* Check value range */
+ if (return_position) {
+ error = _mm_cmplt_epi8(input, min_range);
+ error = _mm_or_si128(error, _mm_cmpgt_epi8(input, max_range));
+ /* 5% performance drop from this conditional branch */
+ if (!_mm_testz_si128(error, error)) {
+ break;
+ }
+ } else {
+ error = _mm_or_si128(error, _mm_cmplt_epi8(input, min_range));
+ error = _mm_or_si128(error, _mm_cmpgt_epi8(input, max_range));
+ }
+
+ prev_input = input;
+ prev_first_len = first_len;
+
+ data += 16;
+ }
+ /* If we got to the end, we don't need to skip any bytes backwards */
+ if (return_position && data == data_original) {
+ return utf8_range_ValidateUTF8Naive(data, end, return_position);
+ }
+ /* Find previous codepoint (not 80~BF) */
+ data -= utf8_range_CodepointSkipBackwards(_mm_extract_epi32(prev_input, 3));
+ if (return_position) {
+ return (data - data_original) +
+ utf8_range_ValidateUTF8Naive(data, end, return_position);
+ }
+ /* Test if there was any error */
+ if (!_mm_testz_si128(error, error)) {
+ return 0;
+ }
+ /* Check the tail */
+ return utf8_range_ValidateUTF8Naive(data, end, return_position);
+}
